Содержание к диссертации
Введение 6
1. Актуальность, новизна и направление исследования 6
2. Краткое содержание работы 12
1. Системы индексации, хранения и поиска изображений , 16
1Л. Визуальные информационные системы 16
L2. Представление изображений, , * 18
1.2Л. Модель изображения 18
1,2.2- Визуальные характеристики изображений 19
1.3. Поиск изображений 24
1.3 Л- Понятие поиска изображений 24
1.3.2. Типы поиска изображений по визуальным индексам 24
1.3.3. Методы поиска по визуальным индексам 28
1.3.4. Многомерные индексные структуры 31
1.4. Виды визуальных запросов 32
Ь5. Типовая архитектура систем индексации, хранения и поиска изображений 34
1.6. Классификация систем индексации, хранения и поиска изображений 37
1.7. Критерии оценки эффективности систем индексации, хранения и поиска изображений 42
1.8. Выводы 44
2. Схема индексирования и поиска изображений на основе интегральных одномерных визуальных индексов 46
2.1. Метод многомасштабного позиционного разделения изображений 47
2ЛЛ. Структура преобразований 48
2Л.2. Масштабирование изображения 49
2Л.З- Разделение на кадры > 50
2Л.4- Ограничение количества кадров 52
2.2. Способ построения индексов изображений на основе ранжированных визуальных характеристик 54
2-2,1. Формирование интегральных одномерных индексов 55
2.2,2, Иерархическая организация интегральных одномерных индексов 56
2-2.3, Поиск изображений в иерархической структуре интегральных одномерных индексов 57
2.3. Метод построения интегральных одномерных индексов изображений на основе Wavelet-разложения 61
2.3.1. Структура преобразований 61
2.3.2, Wavelet-разложение изображений 62
2.3.3. Метрические характеристики Wavelet-коэффициентов изображений 64
2.3.4, Квантование метрических характеристик Wavelet-коэффициентов изображений 70
2.4. Метод построения интегральных одномерных индексов изображений на основе доминирующих цветов 75
2.4.1. Структура преобразований 75
2.4.2. Выбор основных цветов 78
2.4.3. Квантование цветов изображения 79
2.5» Выводы 82
3. Анализ эффективности систем индексации, хранения и поиска изображений 83
3.1. Методика оценки точности поиска в системах индексации, хранения и поиска изображений 84
3.2. Анализ точности поиска изображений комплексов дистанционного мониторинга по интегральным одномерным визуальным индексам „88
3.2.1, Тестовое множество изображений комплексов дистанционного мониторинга 88
3.2.2, Точность поиска изображений комплексов дистанционного мониторинга 89
3.3. Анализ точности поиска изображений различных классов (WWW) по
интегральным одномерным визуальным индексам 97
3.3 Л. Тестовое множество изображений различных классов (WWW). „97
3.3.2. Точность поиска изображений различных классов (WWW) 98
3.4 Анализ статистической кластеризации изображений по интегральным одномерным визуальным индексам 106
3.4Л. Статистическая кластеризация изображений по интегральным одномерным визуальным индексам на основе Wavelet- разложения 106
3.4.2, Статистическая кластеризация изображений по интегральным одномерным визуальным индексам на основе доминирующих цветов ПО
3.5, Выводы 113
Программный комплекс индексации, хранения и поиска изображений 115
4.1 Архитектура программного комплекса индексации, хранения и поиска изображений..Л 16
4.2 Источник визуальной информации 117
4.3 Подсистема индексирования изображений., 119
4.3Л Диаграмма потоков данных подсистемы индексирования изображений 119
43.2 Описание потоков данных подсистемы индексирования изображений 121
4.3,3 Спецификации процессов подсистемы индексирования изображений 122
4.4 Подсистема поиска изображений 131
4.4.1 Диаграммы потоков данных подсистемы поиска изображений.Л 32
4.4.2 Описание потоков данных подсистемы поиска изображений,.. Л 36
4.4.3 Спецификации процессов подсистемы поиска изображений по визуальным индексам 137
4.4-4 Спецификации процессов подсистемы просмотра Ч изображений 141
4.4.5 Спецификации процессов подсистемы структурированного просмотра изображений 143
4.5 Выводы 144
Заключение 146
Список литературы 149
Приложения 157
Введение к работе
Актуальность, новизна и направление исследования
С появлением новых приложений средств управления визуальной информацией, таких как экологический мониторинг, дистанционное зондирование природных ресурсов Земли, воздушная разведка, системы связи, обработка географических данных, картография, обработка и архивация медицинских данных, интерактивное машинное проектирование, робототехника, автоматизация офисов, проблема эффективного хранения и гибкого поиска визуальной информации становится все более актуальной [1-16].
В настоящее время активно исследуется проблема поиска изображений по визуальным характеристикам (цвет, тексіура, форма) [1-4]. Визуальные характеристики определяются методами первичного анализа и обработки изображений или формируются вручную экспертами предметной области. На основе визуальных хараістеристик вычисляются индексы изображений. В общем случае визуальный индекс является подмножеством множества физических и семантических визуальных характеристик изображения и представляется в виде вектора. Поиск изображений выполняется по визуальным индексам, при этом визуальное сходство изображений отождествляется с понятием меры сходства индексов изображений (например, евклидова мера).
Наиболее актуальными задачами [1-4, 17-20], связанными с созданием систем индексации, хранения и поиска изображений, являются: восприятие изображений, описание изображений (физические и семантические визуальные характеристики), сегментация изображений, поиск изображений по визуальным индексам, описание визуальных запросов, анализ эффективности алгоритмов первичной обработки и схем индексирования изображений.
К таким системам обычно предъявляются следующие требования:
- уменьшение объема хранимой визуальной информации;
- эффективная организация хранения изображений в базе данных;
- наличие развитой системы запросов визуальной информации;
- обеспечение устойчивости визуальных индексов к деформациям и искажающим факторам изображений;
- повышение качества визуального поиска;
- уменьшение времени доступа к визуальной информации.
В известных системах индексации, хранения и поиска изображений можно выделить ряд проблем, которые решаются в данной работе.
В настоящее время в литературе предложено множество различных визуальных характеристик, используемых для построения индексов изображений [1-4, 19, 21-31]. Часть характеристик заимствуется из теории распознавания образов [32-38], Для вычисления визуальных характеристик изображений используются статистические методы, методы вычисления информационных характеристик, пространственно-частотные и геометрические методы преобразования изображений, [1-4, 19, 21-50]. На этапе первичной обработки применяются методы сегментации, методы улучшения качества и препарирования изображений [39, 46]. К основным недостаткам визуатьных характеристик в системах индексации и поиска изображений [1-4] можно отнести следующие:
- не отражают визуальное сходство изображений - для визуально схожих изображений не принимают близкие значения;
- не устойчивы к искажающим факторам изображений: смещение, масштабирование, поворот, зашумление, расфокуссировка, изменение яркости и контрастности и т.д;
- являются узкоспециализированными характеристиками, ориентированными на определенный класс изображений;
- алгоритм вычисления характеристик достаточно сложен и требует больших затрат машинного времени;
- определение характеристик требует привлечения экспертов предметной области.
дной из основных функций исследуемых систем является поиск изображений по визуальным индексам. При этом поиск осуществляется в многомерном пространстве индексов (векторов визуальных характеристик). Актуальными являются задачи поиска по совпадению, по интервалу, по сходству [51, 52]. В информационных системах обычно используются последовательный поиск, хеширование и дихотомический поиск [51-53]. Однако в системах индексирования, хранения и поиска изображений хеширование обычно не используется, так как поддерживает только один тип поиска - точный поиск- Методы последовательного и дихотомического поиска поддерживают все три основных типа поиска изображений. В последовательном методе поиска для всех изображений базы данных вычисляется количественная мера сходства (например, евклидово расстояние). Недостатком последовательного метода поиска является низкая скорость поиска, пропорциональная размеру базы данных изображений. Дихотомический поиск состоит в последовательном уменьшении размера области поиска примерно в два раза после каждой проверки. Это достигается при использовании деревьев [51, 52]. В основе древовидных индексных структур, предназначенных для управления многомерной информацией, лежит разделение многомерного пространства визуальных индексов (векторов визуальных характеристик) на многомерные интервалы, которые сохраняются в узлах дерева [54-57]. В качестве многомерных индексных структур обычно используются R-деревья, Р-деревья, SS-деревья и SR-деревья. Эти структуры отличаются друг от друга способом разделения пространства визуальных характеристик при формировании многомерных интервалов, представляющих узлы дерева. Многомерные интервалы, соответствующие соседним узлам дерева, могут перекрываться. В результате этого эффективность поиска снижается, так как существует несколько способов доступа к целевой информации (листьям дерева). При большой размерности визуальных индексов время поиска приближается к времени последовательного просмотра всех объектов визуальной базы данных. Основными недостатками использования многомерных индексных структур при организации поиска являются: экспоненциальная зависимость времени поиска от размерности визуальных индексов, необходимость выделения памяти для размещения индексных структур (деревьев), сложность реализации многомерных индексных структур Таким образом, технологии, используемые для реализации функций просмотра, индексирования, хранения и поиска изображений, всё еще недостаточно развиты и не удовлетворяют требованиям большинства практических приложений.
Предмет исследования
Предметом исследования является схема индексации и поиска изображений по визуальным характеристикам (цвет, текстура, форма) в визуальных информационных системах [1-4]- В англоязычной литературе для данной области исследования используется термин «Content-Based Image Retrieval» [2-4,6-12, 14-18, 22-25].
Цель работы и задачи исследований
Целью исследования является разработка методов и алгоритмов первичной обработки и анализа изображений, обеспечивающих построение визуальных индексов, наиболее эффективно отражающих визуальное сходство изображений; разработка методов поиска изображений по визуальным индексам, эффективных по времени доступа к информации.
Для достижения цели диссертационной работы поставлены и решены следующие задачи:
исследование и классификация методов первичного анализа и обработки изображений, методов поиска и типов запросов изображений в визуальных информационных системах;
разработка методов построения эффективных визуальных индексов изображений; - разработка метода поиска изображений по визуальным индексам, эффективного по времени доступа к информации;
- разработка частных алгоритмов и моделей (преобразование и обработка изображений, статистический, Wavelet-анализ» анализ информационных характеристик изображений);
- разработка архитектуры системы индексирования, хранения и поиска изображений и ее программная реализация.
Методы исследования
В теоретических исследованиях использованы методы цифровой обработки изображений [39-45], математической статистики [58, 59], анализа информационных характеристик [1, 59J, Wavelet-анализа [13, 60]. Для формализации моделей использован теоретико-множественный подход общей теории систем [71]. Разработка и описание программного комплекса индексации, хранения и поиска изображений производились средствами структурного системного анализа [72]. Экспериментальные исследования проводились методом компьютерного моделирования. Оценка эффективности результатов визуального поиска проведена методами математической статистики и обработки данных.
Научная новизна
В работе получены следующие новые научные результаты:
- разработан метод многомасштабного позиционного разделения изображений, который обеспечивает эффективный поиск фрагментов изображений вне зависимости от их масштаба и положения;
- предложен способ построения индексов изображений на основе ранжированных визуальных характеристик, позволяющих применить эффективные алгоритмы поиска;
- разработаны методы построения интегральных одномерных индексов изображений на основе Wavelet-разложения и доминирующих цветов, обеспечивающих более высокую точность визуального поиска по сравнению с известными методами;
- разработана методика оценки точности поиска в системах индексации, хранения и поиска изображений.
Практическая ценность
# Практическая ценность диссертационной работы заключается в следующем:
- предложена классификация визуальных характеристик изображений, типов и методов поиска изображений по визуальным индексам, видов визуальных запросов изображений;
- разработан эффективный метод индексирования изображений на основе Wavelet-анализа;
- определены наиболее эффективные визуальные индексы для систем индексации, хранения и поиска изображений в комплексах дистанционного мониторинга;
- разработан программный комплекс индексации, хранения и поиска изображений, являющийся инструментальной средой для исследования эффективности методов первичного анализа и обработки изображении и методов формирования визуальных индексов.
Реализация и внедрение результатов исследований
Основные результаты работы использованы при разработке комплекса программных средств первичной обработки фоноцелевой информации с информационно-программным обеспечением АРМ комплекса «ТИПЧАК и системы автоматизации документирования компьютерных экспериментов на модели системы передачи изображений в ФГУП «КБ «Луч» ( г.Рыбинск), а также в учебном процессе кафедры МПО ЭВС РГАТА им. ПА- Соловьева ари обучении студентов по специальности 220400 Программное обеспечение вычислительной техники и автоматизированных систем.
Апробация
Основные научные положения и результаты диссертационной работы докладывались и обсуждались на III Всероссийской научно-технической конференции «Информационные технологии в науке, проектировании и производстве» (Нижний Новгород, 2001), на конференции молодых ученых (Рыбинск, 2001), на Всероссийской научно-технической конференции «Аэрокосмические технологии и образование на рубеже веков» (Рыбинск,
2002), на семинарах ФГУП «КБ «Луч» (Рыбинск), на заседаниях кафедры МПО ЭВС Рыбинской государственной авиационной технологической академии.
Публикации
Основной материал диссертации опубликован в 8 печатных работах.
Структура и объем диссертации
Диссертация состоит из введения, четырех разделов с выводами по каждому из них, заключения, списка литературы и приложений- Содержит 148 страниц основного текста, 53 рисунка, 11 таблиц, список литературы из 101 наименования и 5 приложений на 12 страницах.
Основные положения, выносимые на защиту
В диссертации защищаются:
- метод многомаснгтабного позиционного разделения изображений;
- способ построения индексов изображений на основе ранжированных визуальных характеристик;
- метод построения интегральных одномерных индексов изображений на основе Wavelet-разложения;
- метод построения интегральных одномерных индексов изображений на основе доминирующих цветов;
- методика оценки точности поиска в системах индексации, храпения и поиска изображений.
2. Краткое содержание работы
Во введении обоснована актуальность темы исследования, сформулированы цели, основные задачи и методы исследования, дана оценка научной новизны и практической ценности полученных результатов, приведены основные положения, выносимые на защиту, кратко изложено содержание работы.
В первой главе рассмотрены системы индексации, хранения и поиска изображений, которые являются подсистемами визуальных информационных систем (ВИС) и предназначены для выполнения функций обработки, храпения и выборки изображений. В виду того, что тема исследования является достаточ но новой, введены ключевые понятия систем индексации, хранения и поиска изображений, включая модель изображения, визуальный индекс, поиск изображение визуальное сходство, визуальный запрос изображений [73].
Выполнен анализ и классификация визуальных характеристик, составляющих индексы изображений, что позволило выделить наиболее важные факторы при их выборе. Предложена классификация типов поиска изображений по визуальным индексам. Выполнен анализ и классификация методов поиска изображений по визуальным индексам. Предложена классификация типов визуальных запросов в системах индексации, хранения и поиска изображений.
На основе обзора существующих систем индексации, хранения и поиска изображений выявлена типовая архитектура таких систем. Предложены признаки классификации и формальные модели компонент систем индексации, хранения и поиска изображений.
Выполнен анализ критериев оценки эффективности систем индексации, хранения и поиска изображений, который показал, что не существует общепринятых методов оценки эффективности таких систем. Используемые критерии оценки заимствованы из теории информационного поиска в информационно-поисковых системах, предназначенных для автоматизированного отыскания документов, и обладают рядом недостатков в применении к задаче поиска изображений.
Вторая глава посвящена разработке эффективной схемы индексирования, алгоритмов и методов индексирования и поиска изображений.
Для обеспечения возможности поиска фрагментов изображений вне зависимости от их масштаба и положения, разработан метод многомасштабного позиционного разделения изображения [74], применяемый в системе индексации, хранения и поиска изображений на этапе первичной обработки.
Для уменьшения времени поиска изображений по визуальным индексам предложен способ построения индексов изображений на основе ранжированных визуальных характеристик [73, 75]. При этом из упорядоченного (ранжированного) множества метрических визуальных характеристик изображения формируется интегральный одномерный визуальный индекс. Одномерные индексы организованы в иерархическую структуру (бинарное дерево), позволяющую использовать эффективные методы поиска изображений- При этом реализованы все типы поиска: точный поиск, поиск по интервалу, поиск по сходству.
Дня эффективной организации изображений в визуальной базе данных и обеспечения более высокой точности визуального поиска по сравнению с известными методами, разработаны метод построения интегральных одномерных индексов изображений на основе Wavelet-разложения [73, 75], отражающих визуальные характеристики изображений - текстуру и форму, и метод построения визуальных индексов изображений на основе доминирующих цветов, представляющих информацию о цветовом распределении изображений. Таким образом, достигается комплексное решение по индексации изображений, учитывающее все глобальные визуальные характеристики изображений (цвет, текстура, форма).
Третья глава посвящена анализу эффективности систем индексации, хранения и поиска изображений. Для определения оценки точности поиска, адаптированной к задаче поиска изображений, предложена методика оценки точности поиска в системах индексации, хранения и поиска изображений.
Получены оценки эффективности схемы индексирования и поиска изображений на основе интегральных одномерных визуальных индексов для изображений комплексов дистанционного мониторинга и изображений различных классов (WWW) в соответствии с разработанной методикой. Определены наиболее эффективные визуальные индексы. Оценена эффективность применения сложных визуальных запросов при совместном использовании визуальных индексов, учитывающих совокупность визуальных характеристик: цвет, текстура, форма. Произведен сравнительный анализ мер эффективности с другими системами индексации и поиска изображений. Результаты исследования позволяют сделать вывод о том, что разработанные методы вычисления интегральных одномерных визуальных индексов обеспечивают высокие показатели точности визуального поиска системы индексации и поиска изображений, превосходящие приводимые в литературе оценки эффективности других систем.
Выполнен анализ статистической кластеризации (упорядочивания и группировки) изображений по интегральным одномерным визуальным индексам на основе Wavelet-разложения и доминирующих цветов, который показал, что разработанные визуальные индексы позволяют определить категории изображений, соответствующие семантически значимым категориям классам изображений, что является показателем эффективности использования данных визуальных индексов при поиске изображений.
В четвертой главе представлен программный комплекс индексации, хранения и поиска изображений (ВИС), включающий следующие подсистемы: источник визуальной информации, индексирование изображений, поиск изображений. [76]» Источником визуальной информации является программный комплекс организации и управления тестированием процесса первичной обработки фоноцелевой информации. Архитектура программного комплекса индексации, хранения и поиска изображений отличается от типовой и включает дополнительные инструменты взаимодействия с источником визуальной информации, инструменты анализа эффективности используемой схемы индексирования и поиска изображений,
К диссертации прилагаются:
- классификация методов первичного анализа и обработки изображений в визуальных информационных системах;
- квантование цветовых пространств RGB, IISV, HLS;
- типичные представители изображений тестовых множеств;
- примеры результатов визуальных запросов системы индексации, хранения и поиска изображений;
- схемы построения экспериментов, схема базы данных экспериментов программного комплекса организации и управления тестированием процесса первичной обработки фоноцелевой информации.
