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

Введение Базы данных, хранящие изображения, широко используются В медицине В криминалистике В науке и искусстве Поиск изображений по содержанию (Content Based Image Retrieval, CBIR) : сопоставление по Цветовым характеристикам Текстуре Форме объектов Пример: Найти в домашнем альбоме все фотографии Вашей кошки

Введение Базы данных, хранящие изображения, широко используются В медицине В криминалистике В науке и искусстве Поиск изображений по содержанию (Context Based Image Retrieval, CBIR) : сопоставление по Цветовым характеристикам Текстуре Форме объектов Пример: Найти в домашнем альбоме все фотографии Вашей кошки

Постановка задачи Цель работы Цель работы Разработка эффективных методов сопоставления контуров полигональных объектов Основные задачи Основные задачи Анализ существующих алгоритмов и границ их применимости Разработка алгоритмов декомпозиции контуров многоугольников для их сопоставления по частям

Обзор существующих подходов Декомпозиция на основе скелетов многоугольника (M.Tanase) Декомпозиция на основе скелетов многоугольника (M.Tanase) Хорошие результаты могут быть получены с использованием срединной оси Были рассмотрены только простые многоугольники

Алгоритм Входные данные Входные данные Произвольные многоугольникиПроизвольные многоугольники Принципиальное отличие Принципиальное отличие Необходимо рассматривать в совокупности как внешнюю, так и внутренние границы многоугольникаНеобходимо рассматривать в совокупности как внешнюю, так и внутренние границы многоугольника Идея Идея Алгоритм итеративный – на каждой итерации обрабатывается определенный фрагмент скелетаАлгоритм итеративный – на каждой итерации обрабатывается определенный фрагмент скелета

Пример

Пример с кошкой

Область применения Эффективное сопоставление объектов на основе полученной декомпозиции контуров Эффективное сопоставление объектов на основе полученной декомпозиции контуров Использование в сочетании с другими методами поиска изображений Использование в сочетании с другими методами поиска изображений Достижение соответствия компьютерного разбиения человеческому восприятию Достижение соответствия компьютерного разбиения человеческому восприятию

Результаты Проанализированы алгоритмы и подходы, предложенные ранее для простых многоугольников Проанализированы алгоритмы и подходы, предложенные ранее для простых многоугольников Разработан новый алгоритм для декомпозиции произвольных многоугольников Разработан новый алгоритм для декомпозиции произвольных многоугольников Доказана корректность алгоритма Доказана корректность алгоритма Алгоритм протестирован на наглядных примерах Алгоритм протестирован на наглядных примерах Реализован прототип программного продукта Реализован прототип программного продукта