Десятников, Игорь Евгеньевич. Модель и алгоритмы поиска изображений в графических базах данных на основе теории активного восприятия

brief description

Десятников, Игорь Евгеньевич. Модель и алгоритмы поиска изображений в графических базах данных на основе теории активного восприятия : диссертация ... кандидата технических наук : 05.13.17 / Десятников Игорь Евгеньевич; [Место защиты: Нижегор. гос. техн. ун-т им Р.Е. Алексеева].- Нижний Новгород, 2013.- 127 с.: ил. РГБ ОД, 61 13-5/1956

Министерство образования Российской федерации
Нижегородский государственный технический университет им. Р.Е. Алексеева
На правах рукописи
04201360754
Десятников Игорь Евгеньевич
МОДЕЛЬ И АЛГОРИТМЫ ПОИСКА ИЗОБРАЖЕНИЙ В ГРАФИЧЕСКИХ БАЗАХ ДАННЫХ НА ОСНОВЕ ТЕОРИИ АКТИВНОГО ВОСПРИЯТИЯ
Специальность: 05.13.17 - Теоретические основы информатики Диссертация на соискание ученой степени кандидата технических наук
Научный руководитель д.т.н., профессор Утробин В.А.
Нижний Новгород, 2013
СОДЕРЖАНИЕ
ВВЕДЕНИЕ 4
ГЛАВА 1. АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОДОВ И СИСТЕМ ПОИСКА ИЗОБРАЖЕНИЙ 9
1.1. Обзор методов поиска изображений 9
1.1.1. Методы на базе цветовой классификации 13
1.1.2. Методы на базе анализа текстур 18 ^
1.1.3. Методы на базе анализа формы объектов 26
1.1.4. Методы на базе комбинации признаков 37
1.2. Обзор существующих систем 38
1.2.1. Архитектура CBIR-систем 38
1.2.2. Сравнительный анализ CBIR-систем 39
1.3. Цель и задачи исследования 42
ГЛАВА 2. ТЕОРЕТИЧЕСКИЙ ПОДХОД К ПОСТРОЕНИЮ СИСТЕМЫ ПОИСКА ИЗОБРАЖЕНИЙ НА ОСНОВЕ ТЕОРИИ АКТИВНОГО ВОСПРИЯТИЯ 45
2.1. Основные подходы при построении систем поиска изображений 45
2.2. Формирование признакового описания изображения 54
2.3. Формирование пространства классов изображений 60
2.4. Разработка информационной модели системы поиска 76
2.5. Выводы 87
ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ 88
3.1. Программная реализация комплекса поиска изображения 88
3.2. Алгоритм «Грубый» поиск изображений 93
3.3. Алгоритм помехоустойчивого поиска изображений 94
3.4. Алгоритм «Многоуровневый» поиск изображений 99
3.5. Алгоритм поиска похожих изображений 101
3.6. Сравнение разработанной поисковой системы с существующими аналогами 104
Выводы 110
ЗАКЛЮЧЕНИЕ 112
БИБЛИОГРАФИЯ 114
Приложение А. Акты о внедрении результатов кандидатской диссертационной работы 125
ВВЕДЕНИЕ
Актуальность работы. С каждым годом растёт объём обрабатываемой информации, что требует формализации и последующей алгоритмизации процессов, ранее выполнявшихся вручную. Одним из ключевых понятий в автоматической обработке информации является распознавание объектов определённого класса, в частности поиск изображений в больших базах данных. Когда алгоритмы выполняют распознавание на уровне эксперта- человека, автоматизация ведёт к ускорению работы систем обработки данных и повышению их эффективности.
За последние годы объем мультимедиа-данных вырос в несколько раз. Все большее количество людей используют поиск изображений в больших базах данных и сети Интернет для оформления презентаций, публикаций и просто для общения. При этом классифицированной является лишь незначительная часть этих изображений (в основном, это касается коммерческих и узкоспециализированных баз данных).
Существует разновидность задачи - поиск изображений в базе данных по текстовым аннотациям, размещенным рядом с изображением. Данный подход не рассматривается в работе. Он может являться дополнительной опцией к системе автоматического поиска изображений.
По некоторым подсчетам, количество изображений в сети Интернет на
13
сегодняшний день составляет более 10 и с каждым годом увеличивается в геометрической прогрессии. Однако, вся эта информация бесполезна без точного, удобного и быстрого поиска по ней.
Можно уверенно прогнозировать, что по мере расширения доступа к электронным архивам изображений и видео будет возрастать значимость поиска изображения по его содержанию. Для обоснования этого прогноза достаточно привести два веских аргумента: во-первых, значительная часть информации, поступающей из окружающего мира, воспринимается нами именно в зрительной форме, что стимулирует технический прогресс в этой области, во-вторых, исследования в области машинного зрения щедро финансируются почти всеми ведущими компаниями и продолжаются во многих исследовательских центрах мира.
Возможность поиска изображений по их содержанию может стать еще одним связующим звеном в создании той самой информационной структуры, которую Б. Гейтс назвал «электронной нервной системой» [1]. Благодаря этой системе можно будет быстро реагировать на любые изменения в окружающем мире и своевременно принимать правильные решения.
Целью работы является исследование и разработка информационной модели и алгоритмов системы поиска изображений на основе теории активного восприятия для графических баз данных размером не менее 106 объектов. Поисковая система должна обладать высокой производительностью (малое время отклика системы на запрос) и достоверностью поиска (корректность результата).
Для достижения поставленной цели необходимо решить следующие задачи:
1. обзор и анализ современного состояния проблемы поиска изображений по визуальному подобию и обзор информационных признаков изображений;
2. обзор и анализ существующих систем поиска изображений и их архитектур;
3. разработка информационной модели системы поиска для графических баз данных;
4. разработка алгоритмов поиска оригинальных, а также зашумлённых и похожих по визуальному подобию изображений;
5. разработка алгоритмов поиска поврежденных изображений;
6. разработка экспериментальной поисковой системы для оценки полученных в ходе исследования результатов.
Объект исследования - методы поиска растровых изображений в графических базах данных по визуальному подобию.
Предметом исследования являются модель базы данных и алгоритмы поиска растровых изображений по визуальному подобию.
Методы исследования. Для решения поставленных задач в работе использованы методы распознавания образов, теории активного восприятия, методов цифровой обработки изображений, теории баз данных.
Научная новизна работы состоит в следующем:
1. Разработана информационная модель системы поиска изображений, позволяющая строить графические базы данных с общим количеством изображений более 106 объектов и отличающаяся высокой производительностью и достоверностью выполняемого поиска.
2. Разработан алгоритм поиска изображений в больших базах данных и сети Интернет, обеспечивающий высокую производительность (малое время отклика системы на поисковый запрос) и позволяющий работать с зашумленными изображениями.
3. Разработан алгоритм поиска изображения, часть которого потеряна, загорожена другим объектом или стерта, отличающийся высокой производительностью.
Практическая ценность работы заключается в повышении эффективности средств автоматизированной обработки и поиска изображений в графических базах данных. Предложенные методы поиска можно применять в системах технического зрения, системах контроля качества продукции приборостроения, системах распознавания образов, системах управления и поиска изображений в базах данных. Разработанные в диссертационной работе алгоритмы могут быть использованы для поиска изображений в сети Интернет, а также поиска сопутствующих материалов, размещенных с искомым изображением: поиск автора и названия изображения, поиск изображения с более высоким качеством, поиск похожих изображений, контроль авторских прав.
Апробация работы. Основные материалы и результаты диссертационной работы докладывались на следующих научных конференциях:
• XV международная научно-техническая конференция «Информационные системы и технологии», г. Н.Новгород, 2009;
• XVI международная научно-техническая конференция
«Информационные системы и технологии», г. Н.Новгород, 2010;
• XVII международная научно-техническая конференция
«Информационные системы и технологии», г. Н.Новгород, 2011;
• Вторая Всероссийская конференция «Нелинейная динамика в когнитивных исследованиях», г. Н. Новгород, 2011;
• 16-я Нижегородская сессия молодых ученых (технические науки), г. Семенов, 2011;
• X Всероссийская научная конференция молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», г. Таганрог, 2012.
• XIX международная научно-техническая конференция
«Информационные системы и технологии», г. Н.Новгород, 2013. Публикации. По теме диссертации опубликовано 9 работ, в том числе 2
статьи в рецензируемых изданиях, свидетельство о государственной регистрации программы для ЭВМ.
На защиту выносятся следующие результаты работы:
1. Информационная модель системы поиска изображений, на основе которой можно проектировать графические базы данных с общим количеством изображений более 106 объектов. При этом обеспечивается высокая производительность и достоверность выполняемого поиска.
2. Алгоритм поиска изображений в базе данных, обеспечивающий высокую производительность (малое время отклика системы) и позволяющий работать с зашумленными изображениями.
3. Алгоритм поиска изображений, часть которых потеряна, загорожена другим объектом или стерта.
4. Алгоритм поиска похожих по визуальному подобию изображений, который по производительности и достоверности не уступает
существующим алгоритмам поиска изображений в больших базах данных и сети Интернет.
і
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, библиографического списка. Общий объем работы 127 страниц текста, содержащего 62 рисунка и 3 таблицы. Список литературы содержит 105 наименований.

bibliography

ЗАКЛЮЧЕНИЕ
В процессе проведения теоретических и практических исследований получены следующие основные результаты и выводы:
1. Проведен анализ современного состояния проблемы поиска изображений по визуальному подобию и доступных поисковых систем, позволивший обобщить результаты исследований низкоуровневых признаков изображений.
2. Разработана информационная модель системы поиска изображений для графических баз данных на основе теории активного восприятия. Разработанная на основе данной модели система поиска позволяет эффективно выполнять поиск при количестве объектов больше 106.
3. Разработаны алгоритмы поиска оригинальных, а также зашумлённых изображений.
4. Разработан алгоритм поиска изображения, часть которого потеряна, загорожена другим объектом или стерта.
5. Разработан алгоритм поиска похожих по визуальному подобию изображений.
6. На основе предложенных модели базы данных и алгоритмов поиска изображений разработан прототип поисковой системы, в которой реализованы разработанные алгоритмы поиска изображений. Разработанная экспериментальная система необходима в первую очередь для оценки полученных в ходе исследования результатов и демонстрации работы поиска.
7. Проведено сравнение эффективности поиска изображений с уже существующими системами поиска. Как показали эксперименты, разработанные алгоритмы поиска показывают отличные результаты и могут конкурировать с существующими алгоритмами поиска по производительности и достоверности.
Также стоит отметить, что у работы заложен большой потенциал для дальнейших исследований. В будущем следует выполнить тестирование
разработанной поисковой системы для базы данных размером более 109 изображений. Для этого потребуется специальное оборудование и, возможно, небольшая модификация используемых алгоритмов. Однако отметим, что в данной работе сделан основной задел на будущее - построена информационная модель поисковой системы и разработаны поисковые алгоритмы.
БИБЛИОГРАФИЯ
[1] Гейтс, Б. Бизнес со скоростью мысли / Б. Гейтс. - 2-е изд., исправленное. - М.: ЭКСМО-Пресс, 2001. - 480 с.
[2] Google Scholar [Электронный ресурс]. - Режим доступа: http://scholar.google.ru/ (дата обращения: 19.07.12).
[3] Демидов, В.Е. Как мы видим то, что видим / В.Е. Демидов. - 2-е изд. - М.: Знание, 1987. - 242 с.
[4] Grosky, W. An image data model / W. Grosky, P. Stanchev // In Proceedings of Advances in Visual Information Systems: 4th International Conference. - 2000. - Pp. 227-243.
[5] Safar, M. Image retrieval by shape: a comparative study / M. Safar, C. Shahabi, X. Sun // IEEE International Conference on Multimedia and Expo. - 2000. - Vol. 1. -Pp. 141-144.
[6] Rubner, Y. A Metric for Distributions with Applications to Image Databases / Y. Rubner, C. Tomasi, L. Guibas // In Proceedings of the Sixth International Conference on Computer Vision, IEEE Computer Society. - 1998. - P. 59.
[7] Гонсалес, P. Цифровая обработка изображений / P. Гонсалес, P. Вудс. - М.: Техносфера, 2005. - 1072 с.
[8] Color space // Wikipedia, the free encyclopedia [Электронный ресурс]. - Режим доступа: http://en.wikipedia.org/wiki/Color space (дата обращения: 14.07.12).
[9] Marshall, S. Advances in nonlinear signal and image processing / S. Marshall, G.L. Sicuranza. - New York, USA: Hindawi Publishing Corporation, 2006. - 361 pp.
[10] Color-based image retrieval using compact binary signatures: technical report TR 01-08 / Chitkara V. - University of Alberta Edmonton, 2001.
[11] Strieker, M. Color indexing with weak spatial constraint / M. Strieker,
A. Dimai // SPIE Conference on Visual Communications. - 1996. - Vol. 2670. - Pp. 29-40.
[12] Strieker, M. Spectral covariance and fuzzy regions for image indexing / M. Strieker, A. Dimai // Machine Vision and Applications. - 1997. - Vol. 10, no. 2. - Pp. 66-73.
[13] Swain, MJ. Color indexing / MJ. Swain, D.H. Ballard // International Journal of Computer Vision. - 1991.-Vol. 7, no. l.-Pp. 11-32.
[14] Smith, J.R. Single color extraction and image query / J.R. Smith, S.-F. Chang // International Conference on Image Processing (ICIP-95). - 1995. - Vol. 3. - Pp. 528- 531.
[15] Long, F. Fundamentals of content-based image retrieval / F. Long, H. Zhang,
D. Feng // Multimedia Information Retrieval and Management. - 2003. - Pp. 1-26.
[16] Pass, G. Histogram refinement for content-based image retrieval / G. Pass, R. Zabih // IEEE Workshop on Applications of Computer Vision, 1996. - Pp. 96-102.
[17] Hancock, P.J. The principal components of natural images / P.J. Hancock,
R.J. Baddeley, L.S. Smith // Network. - 1992. - Vol. 3. - Pp. 61-70.
[18] Strieker, M. Similarity of color images / M. Strieker, M. Orengo // Storage and Retrieval for Image and Video Databases (SPIE). - 1995. - Pp. 381-392.
[19] Стандарт MPEG-7: Дескриптор доминантного цвета [Электронный
ресурс]. - Режим доступа: http://book.itep.ru/2/25/mpeg 7.htm, (дата обращения:
14.07.12).
[20] Histogram // Wikipedia, the free encyclopedia [Электронный ресурс]. - Режим доступа: http://en.wikipedia.Org/wiki/Histogram#Cumulative histogram
(дата обращения: 14.07.12).
[21] Haralick, R. Textural features for image classification / R. Haralick,
K. Shanmugam, I. Dienstein // IEEE Transactions on Systems, Man and Cybernetics - 1973. - Vol. 3, no. 6. - Pp. 610-621.