Введение к работе
Актуальность темы. Развитие вычислительной техники в 20 веке стало одним из величайших достижений человека. Оказалось, что компьютер способен решать огромное количество задач, и человек поручил ему значительную часть своей повседневной работы. Однако достижения в решении некоторых классов решаемых компьютером задач являются достаточно скромными. К ним, прежде всего, относятся задачи, требующие интеллектуальной обработки и в частности задача распознавания образов. Постановка данной задачи появилась в конце 50-х годов 20 века. Большой вклад в развитие теории распознавания образов внесли отечественные ученые В. Н. Вапник, В. М. Глушков, А. Л. Горелик, Ю. И. Журавлев, Н. Г. Загоруйко и др., а также зарубежные Ф. Розенблатт, Б. Уидроу, Л. Рабинер, К. Фукунага, П. Харт, А. Ро-зенфельд, Дж. Хопфилд и др.
Среди систем распознавания особенно широкое распространение в настоящее время получили системы автоматического распознавания изображений. В современных условиях все большее число прикладных задач требуют решения данной проблемы. К ним относятся системы распознавание текста, лиц и других биометрических данных, автомобильных номеров, диагностики, робототехники и т. д. В настоящее время активно создаются электронные графические коллекции (базы данных для хранения изображений), в которых также требуется решение задачи распознавания для организации поиска информации. Однако данная задача является достаточно сложной и на сегодняшний день не решена до конца. На практике удается решить эту проблему только для конкретных предметных областей.
Одним из подходов к решению задачи распознавания является применение структурного подхода, особенностью которого является описание объектов с точки зрения их структуры с выделением отдельных составных элементов и связей между данными элементами. Основоположниками данной теории считаются Л. Заде, Е. Каху, В. Миллер, К. Фу и др. Такая идея является привлекательной из-за того, что позволяет составлять простые описания достаточно сложных изображений. Также структурный подход обеспечивает высокое быстродействие, так как задача распознавания сводится к сравнению символьных описаний структур, а не исходных изображений, что дает ему неоспоримое преимущество при решении задачи поиска в больших коллекциях графических документов.
Одним из вариантов описания изображений является представление их в виде скелетов. Впервые данная идея была предложена X. Блюмом. Большой вклад в развитие принципов построения и использования скелетов также внесли У. Монтанари, Э. Калаби, С. Форчуне, Д. Ли и др. С момента выхода первой работы по скелетам опубликованы сотни статей, показывающие широкие возможности их использования при анализе и распознавании изображений.
Цель работы: разработка и реализация алгоритмов поиска в электронных коллекциях бинарных изображений.
Для достижения цели были поставлены следующие задачи:
исследование и анализ существующих методов на предмет эффективного построения и обработки скелетов бинарных изображений;
разработка модели представления скелетов бинарных изображений;
разработка алгоритма структурного поиска в коллекции бинарных изображений с использованием скелетов;
4) компьютерная реализация алгоритма структурного поиска.
Методы исследования. В диссертационной работе используются
методы цифровой обработки изображений, аналитической и вычислительной геометрии, математического моделирования. Основные результаты, выносимые на защиту:
разработана модель скелетов бинарных изображений в виде цепочки примитивов;
разработан алгоритм структурного поиска в коллекции бинарных изображений с использованием скелетов и компьютерная реализация алгоритма структурного поиска;
определены значения параметров алгоритма поиска для коллекции изображений петроглифов Карелии и показаны его преимущества перед известными методами;
даны рекомендации по выбору значений параметров алгоритма для других коллекций бинарных изображений.
Научная новизна работы заключается в следующем:
разработан алгоритм структурного поиска в коллекции бинарных изображений с использованием скелетов, позволяющий искать изображения с одинаковыми частями;
получены численные характеристики параметров алгоритмов на коллекции изображений петроглифов Карелии;
на основании полученных результатов выработаны рекомендации по выбору параметров алгоритмов для других коллекций бинарных изображений.
Практическая значимость. Разработанный алгоритм структурного поиска с использованием скелетов может быть использован при решении задачи поиска в различных коллекциях бинарных изображений.
Публикации и апробация работы. Материалы диссертационного исследования докладывались и обсуждались на XIII Всероссийской научной конференции «Математические методы распознавания образов» (Санкт-Петербург, 2007); X Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции «RCDL'2008» (Дубна, 2008); XI Всероссийской конференции ассоциации «История и компьютер» (Москва, 2008); Ежегодном международном научном семинаре «Передовые методы информационных и коммуникационных технологий» (Петрозаводск, 2008); XI Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции «RCDL'2009» (Петрозаводск, 2009); XL научной конференции аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2009); XII Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции «RCDL'2010» (Казань, 2010). По теме диссертации опубликовано двенадцать научных работ, из них две входят в список ВАК. Разработанное программное обеспечение было апробировано на коллекции бинарных изображений петроглифов Карелии и зарегистрировано в Объединенном фонде электронных ресурсов «Наука и образование» (ОФЭРНиО) № 16964 от 07.04.2011 г. Работа поддержана грантами РГНФ № 05-01-12118в, № 08-01-12116в (руководитель Н. В. Лобанова).
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, библиографического списка использованной литературы (102 наименования) и двух приложений, имеет объем 125 страниц машинописного текста и 6 страниц приложений, содержит 58 рисунков и 5 таблиц.
