Магистерская работа

Тема: Разработка и реализация математической модели графической поисковой системы

Содержание:

ОГЛАВЛЕНИЕ
Стр.
Список иллюстраций 3
Список таблиц 5
Введение 7
ГЛАВА 1. Анализ задачи построения поисковой системы по
содержанию изображений 13
1.1. Введение в поиск изображений по содержанию... 14
1.1.1. Области применения... 14
1.1.2. Типы поиска по содержанию изображений... 15
1.2. Понятие поисковой системы и принципы поиска информации ... 16
1.2.1. Булевская модель... 23
1.2.2. Векторная модель... 24
1.2.3. Вероятностная модель... 25
1.3. Вопросы описания и обработки изображений... 26
1.3.1. Цвет... 26
1.3.2. Применение линейных фильтров для обработки изображений ... 29
1.3.3. Определение границ объектов на изображении ... 31
1.3.4. Текстура... 33
1.4. Поиск на основе графических примитивов... 35
1.4.1. Цветовые характеристики... 35
1.4.2. Характеристики текстуры ... 38
1.4.3. Характеристики контура... 39
2
1.5. Обзор поисковых систем по содержанию изображений . 41
1.5.1. Excalibur Visual RetrievalWare... 41
1.5.2. ImageFinder... 42
1.5.3. IMatch... 43
1.5.4. QBIC... 44
1.5.5. VIR Image Engine... 44
1.6. Парадигма контекстно-зависимого распознавания ... 45
1.7. Выводы... 50
ГЛАВА 2. Модель поисковой системы 51
2.1. Математическая модель поисковой системы ... 51
2.2. Анализ изложенной модели... 55
2.3. Методы построения числового описания графического объекта... 60
2.3.1. Модифицированный алгоритм arch height... 61
2.3.2. Алгоритм SDBMA... 63
2.4. Заключение... 68
ГЛАВА 3. Архитектура поисковой системы 69
3.1. Общая архитектура... 69
3.2. Методы индексации и поиска... 74
3.3. Операции над поисковым запросом ... 77
3.4. Построение распределенной поисковой системы ... 82
3.4.1. Построение распределенного индекса... 82
3.4.2. Модель распределенной поисковой системы ... 84
3.5. Заключение... 88
ГЛАВА 4. Реализация поисковой системы 90
4.1. Функциональность ПС... 90
3
4.2. Архитектура программной реализации... 91
4.3. Обсуждение программной реализации... 96
4.4. Анализ результатов работы поисковой системы ... 99
4.4.1. Анализ затрат памяти... 99
4.4.2. Анализ качества поиска... 100
4.5. Заключение... 108
Заключение 109
Библиография 110
СПИСОК ИЛЛЮСТРАЦИЙ
1.1 Диаграмма состояний поисковой системы... 18
1.2 RGB-куб... 28
1.3 Симметричное гауссово ядро в двумерном пространстве ... 30
1.4 Лапласиан гауссова ядра фильтра... 32
1.5 Изображение и его гистограмма... 36
1.6 Изображение и выделенные на нем контуры ... 39
1.7 Момент инерции... 40
1.8 Полярная сигнатура... 41
1.9 Оптическая иллюзия 1... 47
1.10 Оптическая иллюзия 2... 48
1.11 Оптическая иллюзия Мюллера-Лайера... 49
2.1 Обработанное изображение с выделенными контурами 59
2.2 Иллюстрация алгоритма arch height... 61
2.3 Гистограмма распределения значений числового описания контуров... , . 67
3.1 Диаграмма прецедентов... 70
3.2 Компоненты поисковой системы... 71
3.3 Словарь терминов... 75
3.4 Роли в распределенной поисковой системе... 85
3.5 Сервисы распределенной поисковой системы ... 87
4.1 Диаграмма классов-сущностей... 92
4.2 Диаграмма классов-сервисов... 94
4.3 Диаграмма последовательности для поиска... 95
4.4 Диаграмма последовательности для индексирования 97
5
4.5 Множество релевантных документов... 101
4.6 Первый запрос - автомобиль... 103
4.7 Второй запрос - кот... 104
4.8 Третий запрос - серфингист... 105
4.9 Четвертый запрос - поезд... 106
б
СПИСОК ТАБЛИЦ
1.1 Типы поисковых систем... 21
4.1 Объем индекса поисковой системы...100
4.2 Достоверность и точность для запроса 1...103
4.3 Достоверность и точность для уточненного запроса 1103
4.4 Достоверность и точность для запроса 2...104
4.5 Достоверность и точность для уточненного запроса 2 105
4.6 Достоверность и точность для запроса 3...105
4.7 Достоверность и точность для уточненного запроса 3 106
4.8 Достоверность и точность для запроса 4...106
4.9 Достоверность и точность для уточненного запроса 4107
4.10 Средняя достоверность и точность...107
4.11 Средняя достоверность и точность для уточненных запросов...107

Выдержки из работы:

ВВЕДЕНИЕ
Развитие высокотехнологичного общества во многом сдерживается принципиальными недостатками существующих методов доступа к информации. Информация является одной из основных потребностей современного человека, однако в 20 веке она накапливается человечеством такими темпами, что без специальных технических средств становится все труднее справиться с поиском необходимых данных.
Системы накопления и поиска данных собирают, анализируют, организуют, хранят, отыскивают и распространяют информацию. Традиционно основная часть существующей информации была записана на бумаге, накапливалась в библиотеках и отыскивалась вручную. С середины 20-го века для автоматической обработки и поиска информации начали использоваться различные механические и электронные средства.
Актуальность темы. Широкое и повсеместное применение интернет в повседневной жизни человека привело к усложнению запросов пользователей. В настоящее время, когда в сети расположены не только текстовые, но и всевозможные мультимедийные ресурсы (аудио, фото, видео и т.п.), необходимы новые средства поиска и навигации по ним. Развитие информационных технологий вызвало лавинообразное увеличение объемов информации, доступной отдельно взятому человеку. Изобретение печатного станка сделало письменные источники, а следовательно, информацию, доступными большему количеству людей, а информационные технологии расширили круг тех, кто является не только потребителями, но и производителями информации, причем не только в
8
текстовой форме. Поисковые системы, осуществляющие контекстный поиск информации, уже не могут удовлетворить потребности человека. Появляется интерес к осуществлению поиска по содержанию мультимедийных объектов.
Однако, пока не существует удовлетворительных с точки зрения пользователя программных средств, которые позволяют осуществлять такую навигацию и поиск [1]. Подобное положение дел обусловлено рядом существенных проблем. Во-первых, отсутствует метод однозначного описания свойств мультимедиа объектов. Во-вторых, слабо развит математический аппарат для построения такого описания.. Следствием этого является недостаточная проработка общих методик построения подобных систем на основе фундаментальных математических моделей. Практически все существующие разработки основаны на реализации некоторых эвристических алгоритмов.
Цель диссертационной работы состоит в формализации и развитии методов построения поисковых систем (ПС) по содержанию изображений и реализации программного средства, предназначенного для поиска изображений по содержанию. Для достижения поставленной цели решались следующие основные задачи:
• Анализ современного состояния области исследований.
• Построение математической модели поисковой системы по содержанию изображений.
• Создание архитектуры ПС по содержанию изображений на основе математической модели.
• Анализ существующих методов построения числового описания содержания изображения и создание новых.
9
• Создание программного обеспечения, предназначенного для поиска изображений по содержанию.
• Экспериментальные исследования по оценке результатов поиска и характеристик производительности поисковой системы.
Методы исследования. Для выполнения поставленной задачи применялись методы функционального анализа, математического моделирования, теории информации, теории алгоритмов, численные методы, методы объектно-ориентированного анализа и проектирования программного обеспечения.
Научная новизна работы. В работе осуществлена разработка математической модели поисковой системы по содержанию изображений, формализован процесс ее построения. Предложена архитектура программной реализации поисковой системы на основе математической модели. Разработаны методы построения числового описания объекта на изображении, предложен метод оптимизации поиска по структуре инвертированных списков. Построена модель распределенной поисковой системы, предложены протоколы взаимодействия компонент в такой системе.
Практическая ценность. Разработанная математическая модель и построенная на ее основе ПС может применяться для поиска изображений. Такая ПС может использоваться в научной и производственной деятельности, в областях, связанных с обработкой большого объема графической информации, например в банках данных, проектных организациях и дизайнерских бюро.
Практическое применение. Разработанная программная реализация была внедрена в исследовательском центре компании Reasoning Mind, Inc. Компания занимается созданием систем ди-
10
станционного обучения, ориентированных на школьников разных стран. Поисковая система используется в работе с учебными пособиями, содержащими большое количество графических материалов.
Апробация результатов работы. Основные положения и результаты диссертации были представлены на Всероссийской конференции по проблемам математики, информатики, физики и химии в 2002 г. (г. Москва, РУДН), Межрегиональной научно-технической конференции „Интеллектуальные информационные системы" в 2003 г. (г. Тула), XL Всероссийской конференции по проблемам математики, информатики, физики и химии, секция „Оптические, математические и электронные методы обработки изображений и сигналов" в 2004 г.(г, Москва, РУДН), Международной конференции „Распределенные вычисления и грид-технологии в науке и образовании" в 2004 г. (г. Дубна), научном семинаре МНТОРС им. Попова в 2004 г. (г. Москва).
Публикации. По материалам диссертационной работы имеется б публикаций.
Диссертация состоит из 4 глав. Первая глава посвящена анализу постановки задачи построения поисковых систем по содержанию изображений. В разделе 1.1. дается введение в проблематику поисковых систем, рассмотрены основные понятия и изложены принципы их функционирования. Описаны области применения ПС и типы поиска по содержанию, такие как точное соответствие, композиционное сходство и семантическое соответствие. Само понятие ПС и принципы поиска информации представлены в разделе 1.2., рассмотрены основные модели построения поисковых систем - булевская (раздел 1.2.1.), векторная (раздел 1.2.2.)
11
и вероятностная (раздел 1.2.З.). Раздел 1.3. посвящен вопросам описания и обработки изображений. В разделе 1.3.1. рассматривается понятие цвета и цветовых пространств, описываются линейные, нелинейные и равномерные цветовые пространства. В 1.3.2. описано применение линейных фильтров для обработки изображений. В разделе 1.3.3. рассматривается вопрос определения границ объектов на изображении, в частности, детекторы границ на основе лапласиана и градиентов. Раздел 1.3.4. посвящен применению текстур для описания содержания изображения. В разделе 1.4. предлагается подход к организации поиска изображений по содержанию на основе графических примитивов, таких как цвет, текстура и контуры. Обзор существующих поисковых систем по содержанию изображений приведен в разделе 1.5. В последнем разделе главы описана парадигма контекстно-зависимого распознавания.
Глава 2 диссертационной работы посвящена решению поставленной задачи в части разработки методов построения поисковой системы по содержанию изображений. В разделе 2.1. представлена математическая модель поисковой системы, сделана попытка формализации процесса построения поисковой системы. Раздел 2.2. посвящен анализу деталей математической модели и содержит указания к методике построения поисковой системы. В разделе 2.3. описаны методы построения числового описания объектов на изображении, разработанные в рамках диссертационной работы. Это модифицированный алгоритм arch height и алгоритм SDBMA. Результаты главы 2 диссертации, имеют прикладное значение и используются при проектировании и практической реализации поисковой системы.
12
Третья глава посвящена применению полученных в диссертации теоретических результатов в построении поисковой системы по содержанию изображений , рассматривается архитектура, построенная на основе математической модели. В разделе 3.1. приведена общая архитектура системы, описаны основные функциональные требования и компоненты ПС. В разделе 3.2. рассматриваются алгоритмы формирования индекса поисковой системы и организации поиска в индексе, рассматривается модель инвертированных списков и предлагаются способы повышения эффективности поиска. Раздел 3.4. посвящен проблемам построения распределенных поисковых систем, рассмотрены способы построения распределенного индекса, предложена модель распределенной поисковой системы.
Четвертая глава посвящена реализации поисковой системы и анализу ее эффективности. В разделе 4.1. описана функциональность ПС и основные сценарии взаимодействия пользователя с ПС. В разделе 4.2. приведена программная архитектура поисковой системы с использованием нотации UML, даны пояснения по аспектам реализации. В разделе 4.3. изложены общие принципы реализации системы, рассмотрены технологии, которые применялись при реализации. В разделе 4.4. приведен анализ результатов работы поисковой системы.
13
ГЛАВА 1
АНАЛИЗ ЗАДАЧИ ПОСТРОЕНИЯ ПОИСКОВОЙ СИСТЕМЫ ПО СОДЕРЖАНИЮ ИЗОБРАЖЕНИЙ
Задача построения ПС по содержанию изображений является частным случаем задачи информационного поиска (Information Retrieval, IR), целью которого является нахождение неструктурированной информации [2]. Критерии информационного поиска обычно плохо поддаются формализации. Этим информационный поиск отличается от поиска данных, который оперирует набором формально заданных предикатов и выполняется на структурированной информации. Теория информационного поиска изучает все составляющие процесса поиска, а именно, предварительную обработку (индексирование), интерпретацию и исполнение запроса, ранжирование, пользовательский интерфейс и обратную связь с пользователем.
Решению проблем поиска изображений по содержанию посвящен ряд научных трудов. Первые работы в этой области следовали традиционным парадигмам построения систем контекстного поиска, например [3]. Из опыта этих разработок стало известно, что подобные методы не очень хорошо применимы из-за особенностей изображений как информационного ресурса [4]. В последующие годы усилия разработчиков были сфокусированы на поиске изображений по их содержанию. Первые эксперименты в этой области были сделаны Като [5] в работе, посвященной поиску изображений по информации о цвете и форме контуров. Ряд работ был посвящен формированию запросов пользователей к поисковой системе, среди них наибольшее распространение получи-
14
ла парадигма „запрос на основе изображения-примера" (query by visual example, QVE), где запросом является изображение, предоставленное пользователем, возможно скетч, нарисованный им [6]. Значительное число работ посвящено методам извлечения семантической информации из изображений для нужд поисковых систем [6] [7] [8] [9]. Тем не менее, задача поиска изображений по содержанию изображений еще далека от окончательного решения и еще долго будет оставаться актуальной [10].
1.1. Введение в поиск изображений по содержанию
1.1.1. Области применения В настоящее время существуют сотни крупных библиотек цифровых изображений и тысячи более мелких [11]. Генерация описания для каждого изображения в коллекции достаточно сложный процесс, более того, часто получить адекватное и полное описание изображения просто невозможно. Поэтому большое значение получают методы эффективного поиска по содержанию изображений. Перечислим типичные сферы применения этой технологии.
• Обработка снимков со спутника.
• Архивы фотографий.
• Архивы цифровых изображений музеев и аукционов.
• Защита торговых марок и авторских прав.
• Поиск изображений в интернет.
• Медицинские системы.
• Системы наблюдения.
• Конструкторские бюро.
• Дизайнерские студии.
15 • Журналистика и полиграфия.
1.1.2. Типы поиска по содержанию изображений
Существует три основных типа поиска изображений по содержанию - точное соответствие, где сравнение идет по значениям пикселей изображения, похожесть на композиционном уровне, где оценивается общий вид изображения и поиск на уровне семантики объектов, содержащихся на изображении.
Точное соответствие В данном случае ищутся изображения, совпадающие по точкам с поисковым образцом. Идеально соответствующее изображение будет совпадать с поисковым образцом в каждой точке. Одна из самых известных систем такого поиска описана в работе [12].
Подобный поиск имеет смысл в том случае, если пользователь точно знает и может описать как выглядит искомое изображение. Обычно это бывает очень редко, но есть несколько областей, например защита авторских прав, где такой поиск очень полезен. Так автор фотографии может искать сайты в сети интернет, которые используют его работы без разрешения.
Композиционное сходство Данный тип поиска используется в том случае, если пользователю важна структура искомого изображения. Например, если ищутся изображения заката или рассвета и не важно какие объекты присутствуют на нем, можно вести поиск по композиции, т.к. цветовая гамма и взаиморасположение областей разного цвета в этом случае достаточно характерны. В этом подходе изображение рассматривается как упоря-
16
доменный набор областей разных цветов.
Семантическое соответствие Наиболее востребованный поиск в коллекциях изображений - поиск по семантике, например, пользователь желает найти изображение коптильного аппарата для рыбы [13]. Обработать подобные запросы крайне сложно [14]. Пока еще не существует систем, которые бы в полной мере реализовывали подобный тип поиска.
1.2. Понятие поисковой системы и принципы поиска информации
Под ПС обычно понимается программный комплекс, предоставляющий услуги поиска информации по запросу. Функционирование ПС включает в себя формирование запроса пользователем, его интерпретацию, поиск по запросу, ранжирование полученных результатов и их представление пользователю. При разработке ПС возникает необходимость оперировать специальными терминами, некоторые из которых будут введены ниже.
Введем понятие релевантности поиска. Под релевантностью обычно понимается мера соответствия полученного результата желаемому. В теории ПС это мера соответствия результатов поиска задаче, поставленной в запросе.
ПС управляет достаточно большим объемом информации, при этом она редко работает непосредственно с данными, интересующими пользователя, т.к. они являются неструктурированной информацией. ПС необходимо прежде обработать эти данные и построить из них структуры, позволяющие осуществлять поиск по