Содержание к диссертации
Введение
ГЛАВА 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
1.5. Обзор поисковых систем по содержанию изображений . 41
1.5.1. Excalibur Visual Retrieval Ware 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
4.2. Архитектура программной реализации 91
4.3. Обсуждение программной реализации 96
4.4. Анализ результатов работы поисковой системы . 99
4.4.1. Анализ затрат памяти 99
4.4.2. Анализ качества поиска 100
4.5. Заключение 108
Заключение 109
Библиография 110
- Понятие поисковой системы и принципы поиска информации
- Математическая модель поисковой системы
- Операции над поисковым запросом
- Архитектура программной реализации
Введение к работе
Развитие высокотехнологичного общества во многом сдерживается принципиальными недостатками существующих методов доступа к информации. Информация является одной из основных потребностей современного человека, однако в 20 веке она накапливается человечеством такими темпами, что без специальных технических средств становится все труднее справиться с поиском необходимых данных.
Системы накопления и поиска данных собирают, анализируют, организуют, хранят, отыскивают и распространяют информацию. Традиционно основная часть существующей информации была записана на бумаге, накапливалась в библиотеках и отыскивалась вручную. С середины 20-го века для автоматической обработки и поиска информации начали использоваться различные механические и электронные средства.
Актуальность темы. Широкое и повсеместное применение интернет в повседневной жизни человека привело к усложнению запросов пользователей. В настоящее время, когда в сети расположены не только текстовые, но и всевозможные мультимедийные ресурсы (аудио, фото, видео и т.п.), необходимы новые средства поиска и навигации по ним. Развитие информационных технологий вызвало лавинообразное увеличение объемов информации, доступной отдельно взятому человеку. Изобретение печатного станка сделало письменные источники, а следовательно, информацию, доступными большему количеству людей, а информационные технологии расширили круг тех, кто является не только потребителями, но и производителями информации, причем не только в
текстовой форме. Поисковые системы, осуществляющие контекстный поиск информации, уже не могут удовлетворить потребности человека. Появляется интерес к осуществлению поиска по содержанию мультимедийных объектов.
Однако, пока не существует удовлетворительных с точки зрения пользователя программных средств, которые позволяют осуществлять такую навигацию и поиск [1]. Подобное положение дел обусловлено рядом существенных проблем. Во-первых, отсутствует метод однозначного описания свойств мультимедиа объектов. Во-вторых, слабо развит математический аппарат для построения такого описания.. Следствием этого является недостаточная проработка общих методик построения подобных систем на основе фундаментальных математических моделей. Практически все существующие разработки основаны на реализации некоторых эвристических алгоритмов.
Цель диссертационной работы состоит в формализации и развитии методов построения поисковых систем (ПС) по содержанию изображений и реализации программного средства, предназначенного для поиска изображений по содержанию. Для достижения поставленной цели решались следующие основные задачи:
Анализ современного состояния области исследований.
Построение математической модели поисковой системы по содержанию изображений.
Создание архитектуры ПС по содержанию изображений на основе математической модели.
Анализ существующих методов построения числового описания содержания изображения и создание новых.
Создание программного обеспечения, предназначенного для поиска изображений по содержанию.
Экспериментальные исследования по оценке результатов поиска и характеристик производительности поисковой системы.
Методы исследования. Для выполнения поставленной задачи применялись методы функционального анализа, математического моделирования, теории информации, теории алгоритмов, численные методы, методы объектно-ориентированного анализа и проектирования программного обеспечения.
Научная новизна работы. В работе осуществлена разработка математической модели поисковой системы по содержанию изображений, формализован процесс ее построения. Предложена архитектура программной реализации поисковой системы на основе математической модели. Разработаны методы построения числового описания объекта на изображении, предложен метод оптимизации поиска по структуре инвертированных списков. Построена модель распределенной поисковой системы, предложены протоколы взаимодействия компонент в такой системе.
Практическая ценность. Разработанная математическая модель и построенная на ее основе ПС может применяться для поиска изображений. Такая ПС может использоваться в научной и производственной деятельности, в областях, связанных с обработкой большого объема графической информации, например в банках данных, проектных организациях и дизайнерских бюро.
Практическое применение. Разработанная программная реализация была внедрена в исследовательском центре компании Reasoning Mind, Inc. Компания занимается созданием систем ди-
станционного обучения, ориентированных на школьников разных стран. Поисковая система используется в работе с учебными пособиями, содержащими большое количество графических материалов.
Апробация результатов работы. Основные положения и результаты диссертации были представлены на Всероссийской конференции по проблемам математики, информатики, физики и химии в 2002 г. (г. Москва, РУДЫ), Межрегиональной научно-технической конференции „Интеллектуальные информационные системы" в 2003 г. (г. Тула), XL Всероссийской конференции по проблемам математики, информатики, физики и химии, секция „Оптические, математические и электронные методы обработки изображений и сигналов" в 2004 г. (г. Москва, РУДН), Международной конференции „Распределенные вычисления и грид-технологии в науке и образовании" в 2004 г. (г. Дубна), научном семинаре МНТОРС им. Попова в 2004 г. (г. Москва).
Публикации. По материалам диссертационной работы имеется 6 публикаций.
Диссертация состоит из 4 глав. Первая глава посвящена анализу постановки задачи построения поисковых систем по содержанию изображений. В разделе 1.1. дается введение в проблематику поисковых систем, рассмотрены основные понятия и изложены принципы их функционирования. Описаны области применения ПС и типы поиска по содержанию, такие как точное соответствие, композиционное сходство и семантическое соответствие. Само понятие ПС и принципы поиска информации представлены в разделе 1.2., рассмотрены основные модели построения поисковых систем - булевская (раздел 1.2.1.), векторная (раздел 1.2.2.)
и вероятностная (раздел 1.2.3.). Раздел 1.3. посвящен вопросам описания и обработки изображений. В разделе 1.3.1. рассматривается понятие цвета и цветовых пространств, описываются линейные, нелинейные и равномерные цветовые пространства. В 1.3.2. описано применение линейных фильтров для обработки изображений. В разделе 1.3.3. рассматривается вопрос определения границ объектов на изображении, в частности, детекторы границ на основе лапласиана и градиентов. Раздел 1.3.4. посвящен применению текстур для описания содержания изображения. В разделе 1.4. предлагается подход к организации поиска изображений по содержанию на основе графических примитивов, таких как цвет, текстура и контуры. Обзор существующих поисковых систем по содержанию изображений приведен в разделе 1.5. В последнем разделе главы описана парадигма контекстно-зависимого распознавания.
Понятие поисковой системы и принципы поиска информации
Под ПС обычно понимается программный комплекс, предоставляющий услуги поиска информации по запросу. Функционирование ПС включает в себя формирование запроса пользователем, его интерпретацию, поиск по запросу, ранжирование полученных результатов и их представление пользователю. При разработке ПС возникает необходимость оперировать специальными терминами, некоторые из которых будут введены ниже.
Введем понятие релевантности поиска. Под релевантностью обычно понимается мера соответствия полученного результата желаемому. В теории ПС это мера соответствия результатов поиска задаче, поставленной в запросе.
ПС управляет достаточно большим объемом информации, при этом она редко работает непосредственно с данными, интересующими пользователя, т.к. они являются неструктурированной информацией. ПС необходимо прежде обработать эти данные и построить из них структуры, позволяющие осуществлять поиск по запросам пользователя. Проводить такую обработку при каждом поисковом запросе является неприемлемым с точки зрения вычислительных затрат, поэтому для каждого документа в ПС эта процедура применяется лишь один раз, а ее результаты сохраняются в структуре, которая называется индексом. При этом следует помнить, что индекс уменьшает время, требуемое на поиск, но увеличивает объем постоянно хранимой информации.
Приступая к поиску, пользователь должен описать при помощи средств, предоставленных ПС, какую информацию он желает получить. ПС трансформирует пользовательский запрос в форму, которая оптимальна для осуществления операций над индексом и производит поиск. Затем осуществляется ранжирование результатов поиска согласно некоторой метрики. После получения результатов пользователь может уточнить свой запрос, запустив следующую итерацию поиска.
На рисунке 1.2. приведена диаграмма состояний поисковой системы в нотации UML [15] [16], на которой отражена выше описанная процедура поиска информации при помощи ПС.
Согласно [17], ПС представляется в виде четверки где V - множество документов, известных поисковой системе, Q - множество поисковых запросов, F - множество операций над элементами множеств и R(vi,qj), Vi EV, qj Є Q - функция ранжирования. Для системы, осуществляющей поиск по содержанию изображений, множества V и Q состоят из изображений 1т или их частей.
Задачу поиска информации можно интерпретировать как задачу кластеризации [17], если рассматривать поисковый запрос как спецификацию множества А С V, которое содержит документы, релевантные запросу. Таким образом, задача поиска сводится к получению множества А. Для этого необходимо решить две проблемы. Во-первых, требуется сформировать множество свойств, которые лучше описывают элементы множества А. Во-вторых, выделить множество свойств, по которым лучше всего разделять документы из V на принадлежащие и не принадлежащие множеству А. Первое множество содержит свойства, описывающие внутри кластерное сходство, тогда как второе - меж кластерное различие.
Рассмотрим классификацию ПС на основе описания данных, по которым производится поиск. Выделяют 4 основных типа, детальное описание которых приведено в таблице 1.1. ПС независимые от содержания осуществляют поиск на основе информации, не имеющей отношения к содержанию документа, например поиск по имени владельца документа. Этот тип поиска часто реализуется в различных информационных системах, например в системах документооборота. Реализуется достаточно просто - сравнением значений атрибута документа [18].
Их антиподом являются ПС, поиск в которых основан только на основе информации, содержащейся в документе. Этот тип ПС является наиболее сложным в реализации, но предоставляет очень большие возможности пользователю.
Оставшиеся два типа являются в некотором смысле „промежуточными" типами относительно двух ранее описанных. Они в разной степени опираются на метаданные документа (атрибуты) и на его содержание. Но следует помнить, что наличие атрибутов требует дополнительной работы с данными, т.к. требуется формировать и поддерживать метаданные документа.
Математическая модель поисковой системы
В теории искусственного интеллекта задача распознавания описывается как поиск на множестве состояний [1]. Пользуясь этими постулатами можно кардинально увеличить точность и скорость поиска, уменьшив количество анализируемых состояний в тысячи раз.
Поясним на примере. Пусть испытуемый встречается с мужчиной для деловой беседы. Он видит идущего навстречу человека - причем это даже не распознавание, назовем этот процесс скорее верификацией, т.к. испытуемый точно знает с кем и зачем он встречается (контекст) и достаточно быстрого сравнения по простым критериям, чтобы установить, что это ожидаемый мужчина. Затем извлекается контекст деловой встречи с мужчиной - и мы получаем набор предметов, которые имеют семантические связи. Например, пиджак, белая рубашка под пиджаком, галстук поверх рубашки и т.д. Естественно, мы намеренно упрощаем ситуацию, чтобы обрисовать основную идею. Скорее всего, определение контекста основывается на множестве факторов - информация в сознании, первичные результаты визуального распознавания и т.п. Контексты могут в свою очередь содержать другие контексты -при взгляде на часы мы переходим из контекста внешнего вида собеседника, в который часы входят и „загружаем" контекст самих часов - циферблат, поверх него несколько стрелок, все убрано под стекло - в данном случае не требуется сравнивать со всеми известными объектами, а только с входящими в контекст или даже достаточно просто верифицировать увиденное, т.к. сознание уже обладает информацией об объекте.
Иногда бывают ситуации, когда контекст неизвестен. Тогда распознается один объект, например, наиболее крупный, а по нему ищется наиболее вероятный контекст для загрузки. Например, если мы видим высокую дымящую трубу, то скорее всего имеем дело с индустриальным пейзажем, а распознав стоящий самолет можно попытаться проверить контекст аэропорта. При этом легко представить, что происходит, когда некий объект выпадает из контекста. Достаточно вспомнить фразу „уставился как баран на новые ворота". Исходя из нашей гипотезы, это можно будет описать как обнаружение объекта, который не вписывается в загруженный контекст, что вызывает последовательный поиск этого объекта в памяти, попытку оценить существующий контекст и найти новый или установить новые семантические связи с обнаруженным объектом.
Хороший пример такой ситуации - визуальный анализ изображений, случайно выбранных из некоторой коллекции. В данном случае в сознании не имеется контекста конкретного изображения. Можно подобрать такие изображения, для понимания содержания которых у человека может уйти не одна секунда, а некоторые будут совершенно непонятны без дополнительных объяснений. Еще более сильным примером являются различные оптические обманы, когда в зависимости от выбранного контекста разные люди видят разные изображения (рис. 1.9, 1.10).
Все эти эффекты можно объяснить выбором разного контекста [54]. Такого рода неоднозначные образы привлекают внимание психологов давно, приблизительно с 30-х голов XIX века, когда немецким психологом Неккером был изобретен первый такой образ („куб Неккера"). С того времени особенности восприятия такого рода изображений были исследованы очень детально. Между тем, долгое время сами неоднозначные по содержанию образы и их восприятие относились психологами к разряду курьезных явлений, не имеющих никакого отношения к реальной работе мозга.
Подобные наблюдения привели к возникновению школы гештальт-психологии. Ее приверженцы отвергали изучение реакции на внешние раздражители и делали акцент на понятии „группировки" как основе для понимания зрительного восприятия. Под группировкой в данном случае понимается способность человека собирать некоторые компоненты изображения в единое целое и воспринимать их именно как целое. К примеру, группировкой объясняется оптическая иллюзия Мюллера-Лайера (см. рисунок 1.11), т.к. зрительная система воспринимает горизонтальные линии не как отдельные объекты, а как компоненты стрелок. Важную роль играет и понятие гештальтквалиата - совокупности внутренних отношений, которые делают гештальт целым. Были попытки описать набор правил, по которым элементы изображений будут группироваться и восприниматься как единое целое, была сделана попытка построить алгоритмы использования этих правил [55].
Операции над поисковым запросом
Блок обработки проводит операции по улучшению качества изображения, переводу его в подходящий формат и подготавливает изображение к следующему этапу обработки, если для него существуют ограничения по формату или структуре изображения. Например, на этом этапе могут быть убраны шумы и уменьшено число цветов.
Блок анализа получает изображение от блока обработки и проводит операции более высокого уровня для выделения семантических объектов на изображении. Примерами подобных объектов могут служить контуры, гистограмма распределения цветов, выделенные текстуры и т.п. Результатом работы этого блока являются информационные структуры, уже не являющиеся элементами изображения.
Блок построения числового описания получает выделенные семантические объекты от блока анализа и строит числовые характеристики для каждого из полученных объектов. Например, для контура можно вычислить координаты центра тяжести, величины периметра и площади или более сложные характеристики. Этот блок является последним в процессе обработки изображения, хотя, строго говоря, не работает непосредственно с изображением. Некоторые методы построения этого блока описаны в разделе 2.3.
Рассмотренные три компонента образуют систему полной обработки изображения в поисковой системе. Индекс является хранилищем структурированной информации [66]. В нем хранятся числовые описания изображений и информация о принадлежности элемента описания тому или иному изображению. Структура индекса создается таким образом, чтобы проводить поисковые операции максимально эффективно. При этом она должна обеспечивать и эффективное добавление элементов, т.к. индекс обычно дополняется во время работы системы. Подход к построению индекса изложен в разделе 3.2.
Индексатор - компонент, отвечающий за политику управления индексом, в частности, за добавление изображений в индекс поисковой системы. Прежде чем будет вызван индексатор, проводится полный цикл обработки изображения, результатом которого является набор числовых характеристик изображения. Эти данные передаются индексатору, который сохраняет их в индексе.
Блок формирования запроса получает данные от пользователя и формирует на их основе запрос. Также он обеспечивает операции модификации запроса для уточнения критериев поиска. Т.к. в качестве поисковых запросов используются изображения, то этот компонент взаимодействует с системой обработки изображения и формирует на основе полученных числовых описаний поисковый запрос. Подход к построению запросов на основе изображения и некоторые операции над запросами описаны в разделе 3.3.
Система поиска получает запрос, сформированный соответствующим компонентом и проводит поиск элементов индекса. Результатом его работы является набор изображений, каждому из которых присвоен коэффициент соответствия поисковому запросу. Некоторые методы оптимизации поиска описаны в разделе 3.2.
Компоненты системы могут быть размещены как на одном компьютере, так и на нескольких узлах распределенной системы. Более подробно вопрос построения распределенной системы описан в разделе 3.4.. 3.2. Методы индексации и поиска
Для поиска по содержанию изображений важным фактором является поддержка частичной релевантности запросу [67] [68], т.к., в ином случае будут найдены лишь изображения, абсолютно совпадающие с поисковым запросам, что является очень сильным ограничением.
Поэтому в графических ПС часто используется векторная модель [61], в которой семантические объекты имеют веса. В этой модели подразумевается вычисление меры близости между поисковым запросом и всеми документами индекса, что при больших объемах индекса является практически невыполнимой задачей [69]. Для решения этой проблемы обычно применяется метод инвертированных списков, который состоит в следующем.
Создается словарь терминов, в который входят все объекты, обнаруженные в проиндексированных документах [70]. Каждый элемент словаря адресует список, в котором содержатся идентификаторы изображений, содержащие соответствующий семантический объект и вес объекта в данном изображении. На иллюстрации 3.3 изображена схема словаря терминов. Получив запрос, ПС перебирает все семантические объекты в нем, получая для каждого объекта список изображений, которые содержат этот объект. Таким образом отпадает проблема перебора всех документов в индексе, анализируются лишь те, которые точно имеют семантические объекты, содержащиеся в запросе. Идентификатор каждого найденного документа добавляется в список результатов.
Архитектура программной реализации
Программные продукты призваны решать определенные задачи пользователя. В данном разделе будет подробно рассмотрена функциональность ПС и задачи, которые она решает.
Основная задача ПС - поиск информации по запросу. Она, в свою очередь, распадается на ряд более простых задач. Сценарий взаимодействия пользователя с ПС начинается с составления поискового запроса. ПС должна обеспечивать возможность выбора изображения, максимально похожего на искомое или содержащего искомую информацию. Затем пользователь запускает поиск по коллекции ПС и получает набор изображений, соответствующих запросу и отсортированных по убыванию значения релевантности.
Пользователь должен иметь возможность уточнить запрос. Это осуществляется следующим образом. В списке найденных изображений он может выделить некоторые из них и пометить как подходящие или же наоборот.
ПС предоставляет возможность контроля над порогом точности поиска, который используется при определении подобия объектов на изображении. Также ПС показывает числовое описание, построенное для поискового образца. После уточнения запроса пользователь может снова инициировать поиск.
При создании ПС необходимо предоставить методы создания индекса. Пользователь может выбрать файлы или целые каталоги и проиндексировать их. Таким образом он добавит эти изображения в коллекцию ПС и они будут учитываться при поиске. Пользователь может указать служебный каталог ПС, который используется для хранения данных индекса и служебной информации.
В настоящем параграфе рассматривается описание архитектуры реализованной поисковой системы на языке UML [15] [16], в виде диаграмм классов и последовательностей. Диаграмма классов отражает статическую структуру системы. Она состоит из описания классов и взаимосвязей между ними - наследование, агрегация, композиция и т.п. Диаграмма последовательностей отражает динамические связи в системе, в частности последовательность вызовов методов при выполнении операций.
На рисунке 4.1 приведена диаграмма классов-сущностей, которые являются объектным представлением данных, которыми управляет поисковая система. Класс Shape предназначен для хранения контура на изображении. Контур состоит из набора точек, которые представлены классом ShapePoint. Как видно из диаграммы, Shape содержит массив объектов ShapePoint. Класс ImagePattern является объектным представлением обработанного изображения в системе. Он содержит массив объектов ImagePatternltem, в котором содержится информация о терме. Этот класс содержит собственно числовое описание терма (семантического объекта) и вес этого терма в этом изображении. В качестве поискового запроса в данной реализации используются изображения, т.е. запрос тоже представлен в системе экземпляром этого класса. Класс SpaceUtils является коллекцией вспомо
На рисунке 4.2 изображены основные классы поисковой системы. Методы класса ImageProcessor выполняют обработку изображения, получая на вход изображение как массив байт или имя файла в локальной файловой системе, создают объект класса ImagePattern, т.е. объектное представление обработанного изображения. Класс Engine является ядром поисковой системы и предоставляет интерфейс ко всем основным функциям системы. Он реализован по шаблону проектирования Facade (фасад) [83]. Этот класс получает запросы от пользовательского интерфейса приложения и выступает в качестве брокера, перенаправляя запрос на соответствующий объект. Класс Engine управляет объектом Dictionary, который представляет собой реализацию словаря данных поисковой системы. Словарь данных реализован как хэш-таблица, ключами которой служат числовые описания семантических объектов, а значениями - указатели на списки, состоящие из идентификаторов изображений. Сам список представлен классом Valuelndex, а его элементы - экземпляры класса Valuelndexltem, который является наследником класса Weightltem. Этот класс является основой для классов, представляющих данные с весами, как например, Valuelndexltem, который содержит значение веса семантического объекта в изображении. Эти классы используются как при поиске, так и при индексации. Класс SearchResult представляет собой результаты поиска и включает в себя объекты класса SearchResultltem, которые содержат идентификатор изображения и информацию о релевантности этого изображения поисковому запросу. Класс Accumulator используется при поиске и содержит промежуточные данные поиска, на основе которых в этом объекте строится экземпляр SearchResult.
![Научное обоснование и разработка модели прогнозирования исходов болезней системы кровообращения на уровне популяции на основании оценки индивидуального риска [Электронный ресурс]](/i/i/4472/168245.png "Научное обоснование и разработка модели прогнозирования исходов болезней системы кровообращения на уровне популяции на основании оценки индивидуального риска [Электронный ресурс] Леонов Николай Вячеславович")
