Сопоставление полигональных объектов на основе независимой фрагментации контуров Выполнил: Ю. М. Плотников Научный руководитель: канд. ф.-м. наук К. В. Вяткина Рецензент: Н. С. Васильева

Цель работы Алгоритм фрагментации и сопоставления частей контура для многоугольников общего вида Фрагментация контура Сопоставление частей

Актуальность Альтернативные методы поиска изображений Поиск изображений по содержанию (CBIR - Content-Based Image Retrieval)

Исследование предметной области Фрагментация простого многоугольника фрагментация контура (рис. 2) фрагментация многоугольника (со внутренностью) Рис. 1Рис. 2 Рисунки взяты из диссертации М. Танасе, 2005 г.

Обобщение предыдущих подходов Обобщение многоугольника (рис. 1) Скелет для произвольного многоугольника (рис. 2) Рис. 1Рис. 2

Предлагаемый алгоритм Независимая фрагментация контуров на основе скелетов Генерация скелета для внешнего многоугольника и дырок Разбиение многоугольников Сопоставление фрагментов с помощью скелета для обобщённого многоугольника Генерация скелета многоугольника Сопоставление фрагментов

Пример работы алгоритма Рис. 1 Рис. 2 Рис. 3

Альтернативный подход Фрагментация основана только на скелете для многоугольника с «дырками» Рис. 1Рис. 2

Результаты Выполнен анализ предметной области Разработан алгоритм, расширяющий область обрабатываемых данных Исследованы возможности библиотеки CGAL (Computation Geometry Algorithms Library) Реализован алгоритм на языке С++ (с использованием библиотеки CGAL)

Область применения Система управления базами данных, хранящих изображения Индексирование изображений в базе данных Организация запроса