Грант РФФД - 01-07-90308

ТЕХНОЛОГІЯ РОЗПІЗНАВАННЯ ОБРАЗІВ НА ОСНОВІ ШВИДКОГО ПОШУКУ НАЙБЛИЖЧИХ ЕТАЛОНІВ У словниковому кодів ДЕРЕВІ

Автори: к.т.н. М.М. Ланге *,
інженер-дослідник А.М. Ланге **

* Наукова рада з комплексної проблеми "Кібернетика" РАН, 117333, Москва, вул. Вавилова 40, e-mail: [email protected]
** Інститут оптико-нейронних технологій РАН, 117333, Москва, вул. Вавилова 44/2,

призначення

Пропонована технологія призначена для розпізнавання образів і аналізу сцен в організованому середовищі (деталі на складальному конвеєрі, жести рук на зображеннях з вираженим фоном і т.п.). Технологія орієнтована на розпізнавання двовимірних геометричних форм у вигляді твердих тіл, що мають однотонну забарвлення і довільні розміри і орієнтацію на зображеннях. Можливо узагальнення алгоритмів для розпізнавання образів з напівтонової забарвленням.

Основні функції

-виділення компактних образів на зображенні сцени;
побудова деревовидних уявлень виділених образів;
-формування кодових описів деревовидних уявлень образів;
-пошук в словнику еталонів найближчих представників для пропонованих образів по їх кодовою описам.

Короткий опис

Виділення образів на зображенні проводиться методом сегментації найменшого числа компактних об'єктів. Сегментація виконується на квадродерева [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 GM and Steiglitz K., Operation on Images Using Quadtrees, IEEE Transaction on PAMI, 1970, vol.1, no. 2, pp. 145-153.

3. Lange MM, 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 MM and Lange AM, 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 DL, Experiments in Encoding of Multilevel Images as Quadtrees, NASA Technical Paper, 1987, no. 2 722.

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.