ТЕХНОЛОГИЯ РАСПОЗНАВАНИЯ ОБРАЗОВ НА ОСНОВЕ БЫСТРОГО ПОИСКА БЛИЖАЙШИХ ЭТАЛОНОВ В СЛОВАРНОМ КОДОВОМ ДЕРЕВЕ

Назначение

Основные функции

-выделение компактных образов на изображении сцены;
-построение древовидных представлений выделенных образов;
-формирование кодовых описаний древовидных представлений образов;
-поиск в словаре эталонов ближайших представителей для предъявляемых образов по их кодовым описаниям.

Краткое описание

Выделение образов на изображении производится методом сегментации наименьшего числа компактных объектов. Сегментация выполняется на квадродереве [2] с использованием критерия связности фрагментов изображения. Применение квадродревовидного представления для исходных изображений сцен существенно снижает вычислительные затраты на сегментацию и тем самым ускоряет процесс выделения образов.

Построение древовидных представлений выделенных образов основано на оригинальных разработках авторов, выполненных в 1999-2002 годах в рамках проектов РФФИ [3-6]. Представление строится с помощью рекурсивного разбиения образов на областные сегменты и их аппроксимации с допустимой погрешностью эллиптическими примитивами. Выбор центров, ориентации и размеров примитивов производится с использованием метода моментов. Процедура наилучшего согласования примитива с аппроксимируемым сегментом аналогична методу инвариантной подгонки плоских объектов примитивами, предложенному в работе [9]. Сочетание рекурсивного разбиения и аппроксимации, оптимальной на каждом шаге рекурсии, дает древовидные представления образов, инвариантные к преобразованиям смещения, поворота и изменения масштаба.

Для построения кодовых описаний древовидных представлений образов разработан способ независимого префиксного кодирования деревьев, сходный с известными схемами кодирования квадродеревьев [7,8]. Длины кодовых слов определяются числами вершин в соответствующих деревьях. Предлагаемый способ кодирования асимптотически оптимален, поскольку с ростом числа образов M средняя длина их кодовых описаний стремится к минимально возможному значению log M, где основание логарифма равно размеру кодового алфавита. В отличие от оптимального кода Хаффмана, используемого в стратегиях поиска [1], предлагаемая схема кодирования не требует априорного знания полного списка кодируемых деревьев и их вероятностей. Независимое построение кодовых описаний позволяет дополнять словарь эталонных образов в процессе обучения классификатора без перекодирования ранее записанных эталонов.

Применяемый алгоритм распознавания (классификации) образов реализует процедуру поиска в словаре ближайших эталонов для предъявляемых образов. Поиск ближайшего эталона производится по мере сходства или различия, определенной в пространстве древовидных представлений образов. Вычисление любой из этих мер выполняется на кодовых описаниях эталонных и распознаваемых образов. Для списка, содержащего M эталонов, поиск решения требует в среднем затрат памяти и вычислений порядка M log M. Структуризация эталонов в форме кодового дерева позволяет уменьшить объем памяти до O(M), а объем вычислений до O(logM).

Примеры последовательных этапов распознавания

Этап 1. Анализируемая сцена, содержащая четыре образа (число образов на изображении заранее не известно)

Этап 2. Квадродревовидное представление изображения сцены

Этап 3. Результат выделения образов методом сегментации связных фрагментов на квадродереве

Этап 4. Инвариантное представление образов бинарными деревьями эллиптических примитивов

Этап 5. Результат распознавания образов по кодовым описаниям их древовидных представлений

Скачать демонстрационную программу (2,2 мБ)

Список литературы

1. Альсведе Р., Вегенер И., Задачи поиска, М.: Мир, 1982.

2. Hunter G.M. and Steiglitz K., Operation on Images Using Quadtrees, IEEE Transaction on PAMI, 1970, vol.1, no. 2, pp. 145-153.

3. Lange M.M., Hierarchical Structures for Fast Recognition of Multidimensional Patterns, Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications, Nauka/Interperiodica Russia, 1999, vol. 9, no. 4, pp.654-661.

4. Lange M.M. and Lange A.M., Invariant Representation and Tree Encoding of Patterns for Their Fast Search in a Dictionary, Proceedings of The 5th International Conference on Pattern Recognition and Image Analysis, PRIA-5-2000, Samara, 2000, vol. 2, pp. 428-433.

5. Ланге М.М., Ланге А.М., Решающее дерево для древовидно структурированных изображений на основе эпсилон-сети эталонов и префиксного кодирования, Доклады 10-й Всероссийской конференции по математическим методам распознавания образов, ММРО-10, Москва, 2001, с. 238-241.

6. Ланге М.М., Ланге А.М., Инвариантное представление полутоновых образов деревьями геометрических примитивов, Труды 6-й Международной конференции по распознаванию образов и анализу изображений, РОАИ-6-2002, Великий Новгород, 2002, т. 1, с. 342-346.

7. Lansing D.L., Experiments in Encoding of Multilevel Images as Quadtrees, NASA Technical Paper, 1987, no. 2722.

8. Stroabach P. Tree-Structured Scene Adaptive Code, IEEE Transactions on Communications, 1990, vol. 38, no. 4, pp. 477-486.

9. Voss K. and Suesse H., Invariant Fitting of Planar Objects by Primitives, IEEE Proceedings of ICPR’96, 1996, pp. 508-512.