автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка и реализация математической модели графической поисковой системы

На правах рукописи

Мирошкин Алексей Владимирович

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

Специальность 05.13.01 - «Системный анализ, управление и обработка информации»

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва - 2005

Работа выполнена в Российском Университете Дружбы Народов

Научный руководитель Кандидат технических наук,

Гостев Иван Михайлович

Официальные оппоненты Доктор технических наук,

Аведьян Эдуард Дзеронович

Кандидат технических наук, доцент Данилина Алла Николаевна

Ведущая организация Объединенный Институт Ядерных

Исследований, лаборатория вычислительной техники, г. Дубна

Защита состоится «30» июня 2005 года в 14 часов на заседании диссертационного совета Д 212.133.01 в Московском Государственном Институте Электроники и Математики по адресу: 109028, Москва, Большой Трехсвятительский пер., д. 3/12

С диссертацией можно ознакомиться в библиотеке Московского Государственного Института Электроники и Математики

Автореферат разослан «27» мая 2005 года

Ученый секретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Развитие высокотехнологичного общества во многом сдерживается принципиальными недостатками существующих методов доступа к информации. Информация является одной из основных потребностей современного человека. В 20 веке она накапливалась человечеством такими темпами, что без специальных технических средств становится невозможно успешно проводить поиск необходимых данных.

Традиционно основная часть существующей информации была записана на бумаге, накапливалась в библиотеках и отыскивалась вручную. С середины 20-го века для автоматической обработки и поиска информации начали использоваться различные механические и электронные средства.

Широкое и повсеместное применение сети интернет в повседневной жизни человека приводит к усложнению запросов пользователей. В настоящее время, когда в сети расположены не только текстовые, но и всевозможные мультимедийные ресурсы (аудио, фото, видео и т.п.), необходимо создание новых средств поиска и навигации по ним. Развитие информационных технологий вызвало лавинообразное увеличение объемов информации, доступной отдельно взятому человеку.

Изобретение печатного станка сделало письменные источники, а следовательно, информацию, доступными большему количеству людей, а информационные технологии расширили круг тех, кто является не только потребителями, но и производителями информации, причем не только в текстовой форме. Поисковые системы, осуществляющие контекстный поиск информации, уже не могут удовлетворить потребности человека. В настоящее время имеется устойчивый интерес к осуществлению поиска по содержанию мультимедийных объектов.

Однако, пока не существует удовлетворительных с точки зрения пользователя программных средств, которые позволяют осуществлять такую навигацию и поиск. Подобное положение дел обусловлено рядом существенных проблем. Во-первых, отсутствует метод однозначного описания свойств мультимедиа объектов. Во-вторых, слабо развит математический аппарат для работы с семантикой изображений. Следствием этого является недостаточная проработка общих методик построения подобных систем на основе фундаментальных математических моделей. Практически все существующие разработки основаны на реализации некоторых эвристических алгоритмов.

Цель диссертационной работы состоит в формализации и развитии методов построения поисковых систем (ПС) по содержанию изображений и реализации программного средства, предназначенного для поиска изображений по содержанию. Для достижения поставленной цели решались следующие основные задачи:

• Анализ современного состояния области исследований.

• Построение математической модели поисковой системы по содержанию

изображений.

• Создание архитектуры ПС по содержанию изображений на основе

математической модели.

• Анализ существующих методов построения числового описания содержания

изображения и создание новых.

• Создание программного обеспечения, предназначенного для поиска

изображений по содержанию.

• Экспериментальные исследования по оценке результатов поиска и

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

Научная новизна работы. В работе осуществлена разработка математической модели поисковой системы по содержанию изображений, формализован процесс построения подобной системы. Построена архитектура программной реализации поисковой системы на основе математической модели. Разработаны методы построения числового описания объекта на изображении, предложен метод оптимизации поиска по структуре инвертированных списков. Построена модель распределенной поисковой системы, предложены механизмы взаимодействия компонент в такой системе.

Практическая ценность. Разработанная математическая модель и построенная на ее основе ПС может применяться для поиска изображений. Такая ПС может использоваться в научной и производственной деятельности, в областях, связанных с обработкой большого объема графической информации, например в банках данных, проектных организациях и дизайнерских бюро.

Практическое применение. Разработанная программная реализация была внедрена в исследовательском центре компании Reasoning Mind, Inc. Компания занимается созданием обучающих систем дистанционного обучения, ориентированных на школьников. Поисковая система используется в работе с учебными пособиями, содержащими большое количество графических материалов.

Апробация результатов работы. Основные положения и результаты диссертации были представлены на Межрегиональной научно-технической конференции "Интеллектуальные информационные системы" в 2003 г. (г. Тула), XL Всероссийской конференции по проблемам математики, информатики, физики и химии, секция «Оптические, математические и электронные методы обработки изображений и сигналов» в 2004 г.(г. Москва, РУДН), Международной конференции 'Таспределенные вычисления и грид-технологии в науке и образовании" в 2004 г. (г. Дубна), научном семинаре МНТОРС им. Попова в 2004 г. (г. Москва).

Публикации. По материалам диссертационной работы имеется 6 публикаций. Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа изложена на 117 стр. машинописного текста, содержит 12 таблиц, 28 рисунков, библиографический список включает в себя включает 83 наименования.

На защиту выносятся следующие основные результаты:

• Математическая модель поисковой системы по содержанию изображений.

• Архитектура поисковой системы.

• Методы построения числового описания объекта на изображении.

• Методы индексации и поиска изображений.

• Подход к построению распределенной поисковой системы.

• Программная реализация поисковой системы по содержанию изображений.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность исследуемых вопросов, определена цель и задачи диссертационного исследования.

Первая глава посвящена анализу задачи построения поисковых систем по содержанию изображений. Задача построения поисковой системы по содержанию изображений является частным случаем задачи информационного поиска (Information Retrieval, IR), целью которого является нахождение неструктурированной информации. Предметом поиска выступает

информационная потребность пользователя, описанная в поисковом запросе. Критерии поиска обычно плохо поддаются формализации. Этими признаками информационный поиск отличается от поиска данных, оперирующего набором формально заданных предикатов и выполняется на структурированной информации. Теория информационного поиска изучает все составляющие процесса поиска, а именно, предварительную обработку (индексирование), обработку и исполнение запроса, ранжирование, пользовательский интерфейс и обратную связь с пользователем.

В главе дается введение в проблематику поисковых систем, рассмотрены основные понятия и изложены принципы их функционирования.

Рассмотрены различные типы поиска по содержанию, такие как точное соответствие, композиционное сходство и семантическое соответствие.

Под ПС обычно понимается программный комплекс, предоставляющий услуги поиска информации по запросу. Функционирование ПС включает в себя формирование запроса пользователем, его интерпретацию, поиск по запросу, ранжирование полученных результатов и их представление пользователю.

ПС можно рассматривать как четверку

(1)

где V - множество документов, известных поисковой системе, Q - множество поисковых запросов, F - множество операций над элементами множеств V и Q, ® (vj' 4j)'viе Q - функция ранжирования. Для системы, осуществляющей поиск по содержанию изображения, множества V и Q состоят из изображений Im или их частей. Ниже рассматривается построение F и R^v^q^ для случая поиска

по содержанию изображений.

На рис. 1 приведена диаграмма состояний поисковой системы в нотации UML, на которой отражена процедура поиска информации при помощи ПС.

{v,Q,F,R(v1>qj)}

Рис. 1. Диаграмма состояний поисковой системы.

Далее в главе и механизмы поиска информации, рассмотрены основные модели построения поисковых систем - булевская, векторная и вероятностная. Рассмотрены сильные и слабые стороны каждой модели для поиска по содержанию изображений.

Затем в главе освещены вопросы обработки изображений и их описания. При этом использованы такие понятия, как цвет, цветовые пространства (линейные, нелинейные, равномерные), текстура. Приведены примеры применения линейных фильтров для обработки изображений и методы определения границ объектов на изображении, в частности, применение лаплассиана и детекторов границ на основе градиентов.

Предложен подход к организации поиска изображений по содержанию на основе графических примитивов, в качестве которых использованы такие характеристики изображения, как цвет, текстура и контуры. Поисковый образ изображения, сгенерированный из графических примитивов, невелик по размеру в сравнении с самим изображением и удобен для организации поиска. Вычисление подобия между поисковым образцом и изображениями, известными поисковой системой осуществляется на основании сравнения значений отдельных графических примитивов. Поиск на таком уровне абстракции не предполагает полную и точную идентификацию объектов, как при распознавании образов.

Далее в главе рассмотрены несколько наиболее известных поисковых систем по содержанию изображений - Excalibur Visual RetrievalWare, ImageFinder, Imatch, QBIC, VIR Image Engine. Описаны общие принципы их функционирования.

Рассмотрена парадигма контекстно-зависимого распознавания. В настоящий момент точность и скорость распознавания визуальных объектов человеком в произвольной ситуации в сотни раз превышает показатели лучших систем распознавания образов и машинного зрения. Многие исследователи объясняют это способностью человека «производить вычисления» параллельно. При этом, при

решении специфических задач системы машинного зрения могут работать лучше человека.

Не известно как точно происходит узнавание визуальных образов в сознании человека, но можно построить модель, которая объясняет точность и скорость этой операции в человеческом сознании. Она основывается на следующих постулатах.

• Распознавание контекстно-зависимо. Человек обычно знает контекст, в

котором он находится, т.е. место, обстановку и т.п.

• В памяти человека существует набор семантических связей между

предметами для конкретного контекста и некоторое количество внеконтекстных связей. Проблема заключается в том, что системы распознавания общего назначения не располагают информацией о текущем контексте, в отличии от специализированных систем. Более того, кроме знания такого контекста необходимо иметь их иерархию, информацию о предметах окружающего мира и семантические связи между ними в рамках контекстов или вне их.

Становится понятно, что построить поисковую систему, которая могла бы корректно распознавать произвольные образы и осуществлять их поиск очень сложно. Поэтому был избран путь использования графических примитивов в качестве семантических объектов.

Во второй главе диссертационной работы изложены методы построения поисковой системы по содержанию изображений.

Представлена математическая модель поисковой системы, описан подход к формализации построения поисковой системы. В модели введены понятия: процесс обработки изображения; семантический объект изображения; процесс получения множества семантических объектов; множество свойств изображения; функционал вычисления числовых характеристик изображения; метрики для сравнения изображений; индекс и поисковый функционал.

Процесс обработки изображения Ы представим как некоторую последовательность функций:

где f¡ - функции преобразования изображений, образующие множество ¥;

811={а1,аг,...,ат)- вектор параметров для функции /, из множества Э; а

= .....(д,)бТ - вектор номеров функций /, из ¥, определяющий

последовательность их вызова.

Процесс получения множества характеристических объектов изображения ¡аы = (ды^1 = \ТЙ) из Ы запишем как

®1п,=0(1т,/„(?/,?/)> 1=1Ъ\ , (3)

где О - некоторый функционал, определяющий последовательность применения функций /, в процессе обработки изображения Ы, N - число полученных объектов из Ы, a Ь - число использованных функций в (2). Заметим, что в результате выполнения (3) получается множество состоящее из некоторого количества характеристических объектов изображения. Например, могут быть

выделены все замкнутые контуры, совокупность которых и будет образовывать множество шЬп.

Определение 2. Пусть Рг есть множество всех видов свойств изображения. Для каждого элемента ды определим множество всех его свойств ВсРг, где:

1. В состоит из подмножеств Вы с В, г = 0, п и индекс г означает уровень

Л ___

подмножества так что В =ив<"; В<-"{\В'П =0; у, В'Л =у1(В°'п), 1=1, и; 1-0

2. Элементы (свойства) Ье В такие что Ь ={Д, где Д - конкретное свойство объекта причем Д я = 1>£4), что означает, что некоторое элементарное свойство может характеризоваться множеством чисел у,е ^ ■

ОпуеделениеЗ. Пусть дано множество функций О, которые допустимо использовать для получения векторов значений свойств объекта. Это множество состоит из элементов ¿(Ь)еО, которые вычисляют вектора значений свойств объекта по некоторому вектору свойств, запишем в виде

а{Ъ) = {у„,к=Щ, (4)

где Уде Последовательность применения таких функций назовем характеристической функцией

= {5)

Определение 4. Введем функционал вычисления числовых характеристик изображения для расчета значений векторов свойств по некоторому набору характеристических объектов сы из изображения 1т

вЬа=сфьЛ,0)> (6)

где Вы - множество векторов типа р = = Сокращенно обозначим (6) как С1ш и будем записывать его как С^ если в нем заменить Л( ) на одну фиксированную функцию [1,р].

Будем считать, что для каждого В'1т=С,1ш(1пг,^1,е) существует некоторая метрика рДВ^.В^), которую будем использовать для сравнения изображений. Способ её вычисления будет описан ниже.

Пусть имеется множество изображений №, тогда для двух из них 1т, и 1т2 запишем меру близости как:

й(1т1,1т2) = |;йг„р„(ВС1,В^2), (7)

(71=1

где «„ей - весовой коэффициент меры рт смысл, которого заключается в придании некоторому свойству большего значения. Простейшим примером такой меры может служить эвклидово расстояние в п-мерном пространстве.

Определение 5 (Индекса). Для множества изображений И' = у = 1, У) и соответствующего ему множества векторов свойств £ = (#¿,,7 = 1,/), где

В^ = C(ImJtA,G), полученных применением (б) к каждому элементу W, введем биективную функцию и(В'ы), такую, что

Im^u(Bi), Vimj<=W, VS¿,eZ, j = U (8)

Формула (6) означает, что для выбранных свойств изображения можно вычислить набор его числовых характеристик, а (8) - что по этим числовым характеристикам можно однозначно идентифицировать это изображение. Определим индекс IDX, который будет связывать множества W и Z через биективную функцию.

IDX={W,Z,u] (9)

Число J из (8) будем называть мощностью индекса.

Определение 5 (Поискового функционала). Сформулируем задачу поиска изображений Im по образцу Im, удовлетворяющих условиям:

1. Л(1га„1ту)<£- ImyeW j = l7 (10а)

2. 5¿,eZ, j=U, (10b)

в виде поискового функционала S(lmr,R,IDX,£), возвращающего

множество (Im^ln^.....Ь11^)» где £ - поисковый допуск, задающий диапазон

изображений, удовлетворяющий условиям поиска.

Представленная модель в наиболее общем виде математически описывает элементы ПС по содержанию изображений. Она определяет 5 основных компонент такой системы.

• Низкоуровневая обработка изображения.

• Выделение объектов на изображении.

• Получение свойств объектов.

• Рассчет числовых характеристик объектов.

• Метрики сравнения объектов и изображений.

• Методы поиска.

Функционирование любой ПС разделяется на два этапа. Первый этап включает в себя сбор данных и индексирование их свойств, второй этап - поиск искомых данных по индексу. В предложенной модели на первом этапе формируется множество числовых описаний для множества изображений, по которым затем будет проводиться поиск. Сопоставление этих множеств обычно называют индексом поисковой системы, хранение которого обычно осуществляется в БД или просто в файловой системе. На втором этапе работы поисковой системы по парам свойства - изображение (Z-W) на основании поискового функционала 5( ) производится поиск свойств удовлетворяющих (10). Результаты выполнения запроса представляются пользователю, как результат работы функции «(В^) в виде изображений из W.

Приведём пример работы такой поисковой системы согласно рассмотренной модели. Определим набор функций из (2) для проведения процесса обработки изображений в виде метода Canny, который включает в себя четыре функции и дополним его функцией сканирования контуров и перевода их в текстовое представление. Это текстовое представление и будет множеством

характеристических объектов шы (3). Для выбранного типа элементов дta (например, контуры объектов) из множества 0Ш определим набор свойств В, который в рассматриваемом ниже примере состоял из площади контура и второго момента инерции контура относительно оси, проходящей через центр тяжести перпендикулярно к плоскости контура.

Построим набор функций d(b) из (4). Роль этих функций - вычислить числовое описание для каждого из свойств по которому будет

осуществляться поиск в индексе поисковой системы.

Теперь необходимо вычислить функционал С( ) по (б) - операция, которая заключается в выполнении полного цикла обработки изображения в поисковой системе. Заметим, что это цикл может использоваться многократно, а по его результатам будет осуществляться поиск по запросу пользователя. Далее, необходимо реализовать функцию м( ), которая получает изображение по его числовому описанию, т.к. пользователь манипулирует изображениями, а поисковая система - данными из его числового описания.

Построение функционала (10) основано на выборе пользователем некоторого изображения, по которому будет происходить процесс перебора индекса и вычисление меры расстояния между поисковым запросом и элементами индекса. Эта теоретически тривиальная задача, достаточно сложна при практической реализации, так как способов задания изображений много, а для каждого необходимо определять свой набор функций в (3) и, особенно (6). Кроме того, особенное внимание необходимо уделять вопросам оптимизации поиска по всему пространству состояний, так как оно может иметь размерность 108-1012 объектов. Часто для этого используются различные эвристические алгоритмы, основанные на априорном знании свойств данных в индексе.

Далее в главе описаны два специально разработанных алгоритма построения числового описания объектов на изображении - модифицированный алгоритм arch height и алгоритм SDBMA.

Алгоритм SDBMA. Входными данными для метода является контур

т.е. совокупность точек двумерного пространства. Результатом является действительное число, которое рассматривается как описание контура.

Контур может состоять из достаточно большого количества точек. Как будет показано ниже, объем вычислений в приведенном алгоритме пропорционален количеству точек контура. Поэтому с целью уменьшения объема вычислений необходимо апроксимировать С вершинами выпуклого многоугольника описывающего контур.

Введем величину Dc - числовое описание контура С, положив ее равной:

где S - площадь многоугольника С, а щ - момент инерции (момент второго порядка) для вершин многоугольника С относительно оси, проходящей через центр тяжести С и перпендикулярной плоскости многоугольника.

Тогда площадь S многоугольника С можно вычислить по следующей формуле:

1 "

Найдем координаты центра тяжести сс{хс,ус) многоугольника с, распределив вес, равный 1 в каждой узловой точке многоугольника:

X к

Вычислим момент инерции второго порядка для узловых точек многоугольника С относительно центра тяжести С, положив вес каждой точки равным 1.

Шз = —

N

(14)

где r:,i=l,N - расстояние от точки с, до центра тяжести сс, вычисляемое по формуле:

г,=^-хс)2 + (У,-Ус)2 (15)

Модифицированный алгоритм arch height применяется для построения численного описания контура фигуры. Основная идея этого алгоритма заключена в перемещении хорды по контуру, как показано на рис. 2.

Рис. 2. Иллюстрация алгоритма arch height.

Входными данными для метода является

C = (Cj,j = 1, ЛО,сj = (Xj, Xj e R, уj 6 R, т.е. набор точек двумерного пространства. Результатом работы метода является вектор действительных чисел F-(/„,m = l,M),fmeR. Рассмотрим сначала вычисление /„ в одной точке А.

и

Хорда АВ фиксированной длины / размещается на контуре в выбранной точке. Через ее центр (точка О) проводится перпендикуляр и находится точка пересечения с контуром (точка С). Будем считать числовой характеристикой контура в точке А отношение длин отрезков ОС к АВ. Тогда положим /я =<г(А), где функция а определяется следующим образом

а(А) = Ш=Ш (1б)

\АВ\ I '

Теперь рассмотрим вычисление числовых характеристик для всего контура.

Последовательно выбирая в качестве точки А каждую точку с, строим вектор, содержащий характеристики формы контура. Размерность полученных векторов будет зависеть от числа точек в контуре, что не позволяет корректно сравнивать полученные описания. Для решения этой проблемы зафиксируем размер вектора-описания, т.е. число точек контура, для которых производится вычисление характеристик. Тогда полученный вектор можно рассматривать как координаты точки в n-мерном пространстве. Поэтому в качестве критерия близости графических объектов можно использовать, например, евклидово расстояние.

Т.к. длина хорды АВ для отдельного контура является фиксированной, то будем рассматривать ее как значение функции от количества точек контура. При этом желательно разместить точки, в которых проводятся вычисления, равномерно по контуру, обеспечив тем самым полноту его описания.

Обозначим подмножество точек контура С, в которых

будем проводить вычисления fm. Опишем процедуру его построения. Введем вектор содержащий набор индексов элементов С, который входят в

множество С, т.е.

(17)

и сформируем этот вектор следующим образом

г, =1;г, = (18)

где

s = N+M, (19)

где операция + означает деление нацело.

Значение s означает "сдвиг" точки вычисления в векторе С. Тогда значение / определяется

1=4 í20)

2

Таким образом, согласно приведенным формулам мы формируем для контура С набор его точек, в которых будем производить вычисления и определяем величину /. В итоге для любого контура мы получаем вектор действительных чисел размерности М.

В третьей глава полученные в диссертации теоретические результаты применяются для построения поисковой системы по содержанию изображений, а также рассматривается архитектура, созданная на основе математической модели.

Рассмотрим самую общую схему организации ПС. Прежде всего, необходимо определить по каким документам будет проводиться поиск, определить операции над ними, построить модель данных и процедуру построения описания документа, согласно выбранной модели. В данном случае мы рассматриваем один тип документов, которыми оперирует поисковая система - это изображения. Затем строится поисковой индекс, в который добавляются изображения и по которому будет осуществляться поиск. Эта сущность необходима для обеспечения операций поиска на больших объемах данных в приемлемые временные рамки. На стадии поиска пользователь должен описать, используя средства, представленные системой, какую информацию он желает получить. После этого запрос трансформируется в форму, которая оптимальна для осуществления поиска по индексу. Перед предоставлением результатов пользователю система выполняет ранжирование найденных изображений. После получения результатов поиска пользователь может уточнить свой запрос, вернувшись, таким образом, в начальную точку цикла взаимодействия с поисковой системой.

Далее в главе анализируются требования к реализации поисковой системы. Затем описана общая архитектура системы, рассмотрены ее основные компоненты которые представлены на рис. 3.

Рис. 3. Основные компоненты поисковой системы.

Рассмотрены операции над поисковыми запросами, которые строятся на основе изображения, предоставляемого пользователем (Query By Example, запрос по примеру). Введен целый ряд операций над запросами такого рода, как для формирования, так и для их уточнения.

Обсуждены алгоритмы формирования индекса поисковой системы и организации поиска в индексе, рассматривается модель инвертированных списков. Предложен метод оптимизации поиска в модели инвертированных списков.

Далее в главе рассматривается проблема построения распределенных поисковых систем, способы построения распределенного индекса, предложена модель распределенной поисковой системы. При реализации поисковых систем возникает проблема совершения поисковых операций на больших объемах данных. Время индексирования и поиска данных растет вместе с объемом информации, доступной поисковой системе, что может существенно снизить эффективность подобной системы. Для повышения быстродействия и устранения зависимости времени выполнения запроса от объема данных в настоящее время используются распределенные технологии. Описаны три основных способа построения распределенного индекса - распределение коллекции документов, словаря и инвертированного листа.

Для повышения быстродействия и устранения зависимости времени выполнения запроса от объема данных в настоящее время используются распределенные технологии, которые позволяют отдельным частям приложения и данным, которыми оперирует приложение, размещаться на разных компьютерах. Основными задачами, которые решают распределенные системы, являются:

• Обеспечение масштабируемости.

• Надежность и отказоустойчивость.

• Возможность непрерывной работы в течение длительного времени.

• Высокий уровень безопасности.

При построении распределенных систем большое значение имеют методы взаимодействия компонент системы и координация вычислений на узлах распределенной системы. В главе рассмотрена модель организации распределенной поисковой системы, в которой могут быть реализованы различные методы построения распределенного индекса. Данная модель построена на основе архитектуры JXTA Search. Она позволяет организовывать полностью централизованные, децентрализованные и гибридные поисковые системы. Модель определяет элементы распределенной поисковой системы и основные методы взаимодействия между ними, формализуя их в описании протокола QRP (Query Routing Protocol - Протокол Маршрутизации Поисковых Запросов). Использование ее в GRID сети вполне естественно, т.к. она предполагает обмен XML сообщениями по протоколам TCP или HTTP в качестве транспортного уровня.

Ниже предлагается модель построения распределенной поисковой системы для технологии GRID, построенная на основе JXTA Search.

В распределенной поисковой сети можно выделить три основных роли. При этом один компонент системы может выступать в разных ролях.

• Information Provider (поставщик информации) - управляет некоторой информацией, получает поисковые запросы и обрабатывает их.

• Search Consumer (потребитель информации) - посылает поисковые запросы и получает результаты поиска.

• Search Hub (поисковый посредник) - обеспечивает маршрутизацию поисковых запросов между потребителем и поставщиками информации, регистрирует поставщиков информации, получает запросы от потребителей.

Распределенная система - это прежде всего совокупность сервисов, каждый из которых играет одну или более описанных выше ролей, в состав которой входят следующие сервисы.

• Search Provider Service (сервис поискового провайдера). Этот сервис получает

запросы от поискового посредника или непосредственно от клиента. Сервис производит индексирование и поиск информации, размещенной на этом узле, выполняет роль Information Provider.

• Search Consumer Service (сервис потребителя услуг поиска). Этот сервис

отсылает запросы поисковому посреднику или непосредственно поисковому провайдеру и ожидает получения ответа. В его обязанности входит также обработка ответа и его представление пользователю в удобной для него форме. Сервис играет роль Information Consumer.

• Search Registration Service (сервис регистрации). Сервис, который отвечает за

формирование и отсылку информации о поисковом провайдере поисковому посреднику. Является вспомогательным для функций роли Search Hub.

• Search Hub Service (сервис поискового посредника). Сервис отвечает за

маршрутизацию запросов от потребителя до поставщика информации. Он получает запросы, направляет их подходящим поставщикам. Этот сервис играет роль Search Hub. Он состоит из двух компонент.

• Search Router (маршрутизатор запросов). Маршрутизирует и управляет запросами, собирает результаты поиска от различных провайдеров и перенаправляет клиенту.

• Search Resolver (разрешитель запросов). Отвечает за поиск подходящих запросу поставщиков информации, который осуществляется на основе полнотекстового поиска по метаданным поисковых провайдеров.

Взаимодействие между узлами системы происходит по протоколу QRP, запросы в котором описываются на языке XML. QRP определяет способы формирования запроса и ответа на запрос, а также методы управления метаданными.

Данные распределенного индекса размещаются на стороне сервиса Search Provider. При этом может использоваться любой из описанных способов распределения индекса. Брокером в данной модели выступает сервис Hub и его компоненты.

Четвертая глава посвящена реализации поисковой системы. В ней изложены общие принципы, заложенные в разработанное ПО, рассмотрены технологии, которые применялись при этом. Описана программная архитектура поисковой системы с использованием нотации UML, даны пояснения по аспектам реализации.

Основная задача ПС - поиск информации по запросу. Она, в свою очередь, распадается на ряд более простых задач. Сценарий взаимодействия пользователя с ПС начинается с составления поискового запроса. ПС должна обеспечивать возможность выбора изображения, максимально похожее на искомое или содержащего искомую информацию. Затем пользователь запускает поиск по коллекции ПС и получает изображения, соответствующие запросу, отсортированные по убыванию значения меры близости. Пользователь должен иметь возможность уточнить запрос. Это осуществляется следующим образом. В списке найденных изображений он может выделить некоторые из них и пометить как подходящие или же наоборот. Также ПС предоставляет возможность контроля над порогом точности поиска, который используется при определении подобия объектов на изображении. ПС показывает числовое описание, построенное для поискового образца. После уточнения запроса пользователь может снова инициировать поиск.

ПС была реализована на языке С# на основе технологии Microsoft .NET. Поисковая система представляет собой программное приложение для ОС Windows. Система построена на принципах объектно-ориентированного программирования. При ее создании использовалась свободно распространяемая библиотека обработки и анализа изображений Open Computer Vision, разработанная компанией Intel, которая содержит как базовые алгоритмы обработки изображения, так и высокоуровневые методы анализа. Из этой библиотеки использовались методы чтения изображений в различных форматах, перевод в полутоновое изображение и алгоритмы выделения контуров.

Остальные элементы поисковой системы были реализованы без использования сторонних библиотек, средствами языка и на основе классов .NET Framework 1.1. Пользовательский интерфейс реализован на основе технологии Win Forms.

Индекс создан по модели инвертированных списков. Словарь терминов реализован на основе хэш-таблицы, что обеспечивает быстрый и эффективный доступ к искомым данным. Инвертированные списки позволяют добавлять элементы на любую позицию и поддерживают динамическое расширение. Реализовано сохранение в файловую систему всего индекса и отдельных его элементов, например, словаря данных или отдельного инвертированного списка. Это позволяет проводить динамическую загрузку в целях экономии оперативной памяти. При индексации изображения кроме числового описания также создавалась уменьшенная копия изображения, которая используется для представления результатов поиска. Уменьшенная копия занимает небольшой объем, а ее генерация требует вычислительных затрат, поэтому эффективнее сгенерировать ее один раз при индексации.

ПС предоставляет методы создания индекса. Пользователь может выбрать файлы или целые каталоги и проиндексировать их. Таким образом, он добавит эти изображения в коллекцию ПС и они будут учитываться при поиске. Пользователь может указать служебный каталог ПС, который используется для хранения данных индекса и служебной информации.

Далее в главе изложена методика оценки качества поиска, исследованы вопросы производительности системы и приведен анализ результатов работы поисковой системы.

В заключении сформулированы основные выводы по работе.

Основные результаты

Основными теоретическими и практическими результатами являются:

• Построена математическая модель поисковой системы по содержанию изображений

• Создана универсальная архитектура поисковой системы по содержанию изображений

• Предложены два новых метода построения числового описания объекта на изображении

• Предложены методы оптимизации поиска изображений

• Описан подход к построению распределенной поисковой системы, создана ее модель и описаны протоколы взаимодействия компонент такой системы

• Разработана программная реализация поисковой системы по содержанию изображений

• Проведены экспериментальные исследования по оценке результатов поиска и характеристик производительности поисковой системы

Основные положения диссертации опубликованы в следующих работах:

1. Мирошкин А. В. Применение алгоритма Arch height в системе поиска изображений // Тезисы всероссийской конференции по проблемам математики, информатики, физики и химии. М.:РУДН 2002, с.14-16.

2. Мирошкин А.В. Об одном методе ранжирования формы объектов в графических поисковых системах // Тезисы межрегиональной научно-техническая конференции "Интеллектуальные информационные системы", г. Тула, 2003, с.48-50.

3. Мирошкин А.В. О вопросе построения поисковых систем по содержанию изображений // Тезисы XL всероссийской конференции по проблемам математики, информатики, физики и химии. Москва, 2004, с.63-65.

4. Гостев ИМ., Мирошкин А.В. О методах индексации в больших потоках графической информации на основе систем распределенных вычислений // Тезисы международной конференции 'Таспределенные вычисления и грид-технологии в науке и образовании" Дубна, 2004, с.62-63.

5. Гостев И.М. Мирошкин А.В. Математическая модель одного класса поисковых систем // Вести. РУДН, сер. «Прикладная и компьютерная математика». Т. 3. № 1,2004 с.93-98.

6. Гостев ИМ., Мирошкин А.В. О методах индексации в больших потоках графической информации на основе систем распределенных вычислений // ТР межд. конф. «Распределенные вычисления и грид-технологии в науке и образовании» г. Дубна, ОИЯИ, июнь 2004 с.74-78.

Подписано в печать 25.05.2005. Формат 60x84/16. Бумага типографская № 2. Печать"-ризография. Усл. печ. л. 1,1 Тираж 100 экз. Заказ^?.

Московский государственный институт электроники и математики 109028, Москва, Б.Трехсвятительский пер., 3/12.

Центр оперативной полиграфии (095)916-88-04,916-89-25

1630

Список иллюстраций

Список таблиц

Введение

ГЛАВА 1. Анализ задачи построения поисковой системы по содержанию изображений

1.1. Введение в поиск изображений по содержанию.

1.1.1. Области применения.

1.1.2. Типы поиска по содержанию изображений.

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.4.1. Цветовые характеристики.

1.4.2. Характеристики текстуры

1.4.3. Характеристики контура.

1.5. Обзор поисковых систем по содержанию изображений

1.5.1. Excalibur Visual Retrieval Ware.

1.5.2. ImageFinder.

1.5.3. IMatch.

1.5.4. QBIC.

1.5.5. VIR Image Engine.

1.6. Парадигма контекстно-зависимого распознавания

1.7. Выводы.

ГЛАВА 2. Модель поисковой системы

2.1. Математическая модель поисковой системы

2.2. Анализ изложенной модели.

2.3. Методы построения числового описания графического объекта.

2.3.1. Модифицированный алгоритм arch height.

2.3.2. Алгоритм SDBMA.

Развитие высокотехнологичного общества во многом сдерживается принципиальными недостатками существующих методов доступа к информации. Информация является одной из основных потребностей современного человека, однако в 20 веке она накапливается человечеством такими темпами, что без специальных технических средств становится все труднее справиться с поиском необходимых данных.

Системы накопления и поиска данных собирают, анализируют, организуют, хранят, отыскивают и распространяют информацию. Традиционно основная часть существующей информации была записана на бумаге, накапливалась в библиотеках и отыскивалась вручную. С середины 20-го века для автоматической обработки и поиска информации начали использоваться различные механические и электронные средства.

Актуальность темы. Широкое и повсеместное применение интернет в повседневной жизни человека привело к усложнению запросов пользователей. В настоящее время, когда в сети расположены не только текстовые, но и всевозможные мультимедийные ресурсы (аудио, фото, видео и т.п.), необходимы новые средства поиска и навигации по ним. Развитие информационных технологий вызвало лавинообразное увеличение объемов информации, доступной отдельно взятому человеку. Изобретение печатного станка сделало письменные источники, а следовательно, информацию, доступными большему количеству людей, а информационные технологии расширили круг тех, кто является не только потребителями, но и производителями информации, причем не только в текстовой форме. Поисковые системы, осуществляющие контекстный поиск информации, уже не могут удовлетворить потребности человека. Появляется интерес к осуществлению поиска по содержанию мультимедийных объектов.

Однако, пока не существует удовлетворительных с точки зрения пользователя программных средств, которые позволяют осуществлять такую навигацию и поиск [1]. Подобное положение дел обусловлено рядом существенных проблем. Во-первых, отсутствует метод однозначного описания свойств мультимедиа объектов. Во-вторых, слабо развит математический аппарат для построения такого описания. Следствием этого является недостаточная проработка общих методик построения подобных систем на основе фундаментальных математических моделей. Практически все существующие разработки основаны на реализации некоторых эвристических алгоритмов.

Цель диссертационной работы состоит в формализации и развитии методов построения поисковых систем (ПС) по содержанию изображений и реализации программного средства, предназначенного для поиска изображений по содержанию. Для достижения поставленной цели решались следующие основные задачи:

• Анализ современного состояния области исследований.

• Построение математической модели поисковой системы по содержанию изображений.

• Создание архитектуры ПС по содержанию изображений на основе математической модели.

• Анализ существующих методов построения числового описания содержания изображения и создание новых.

• Создание программного обеспечения, предназначенного для поиска изображений по содержанию.

• Экспериментальные исследования по оценке результатов поиска и характеристик производительности поисковой системы.

Методы исследования. Для выполнения поставленной задачи применялись методы функционального анализа, математического моделирования, теории информации, теории алгоритмов, численные методы, методы объектно-ориентированного анализа и проектирования программного обеспечения.

Научная новизна работы. В работе осуществлена разработка математической модели поисковой системы по содержанию изображений, формализован процесс ее построения. Предложена архитектура программной реализации поисковой системы на основе математической модели. Разработаны методы построения числового описания объекта на изображении, предложен метод оптимизации поиска по структуре инвертированных списков. Построена модель распределенной поисковой системы, предложены протоколы взаимодействия компонент в такой системе.

Практическая ценность. Разработанная математическая модель и построенная на ее основе ПС может применяться для поиска изображений. Такая ПС может использоваться в научной и производственной деятельности, в областях, связанных с обработкой большого объема графической информации, например в банках данных, проектных организациях и дизайнерских бюро.

Практическое применение. Разработанная программная реализация была внедрена в исследовательском центре компании Reasoning Mind, Inc. Компания занимается созданием систем дистанционного обучения, ориентированных на школьников разных стран. Поисковая система используется в работе с учебными пособиями, содержащими большое количество графических материалов.

Апробация результатов работы. Основные положения и результаты диссертации были представлены на Всероссийской конференции по проблемам математики, информатики, физики и химии в 2002 г. (г. Москва, РУДЫ), Межрегиональной научно-технической конференции „Интеллектуальные информационные системы" в 2003 г. (г. Тула), ХЬ Всероссийской конференции по проблемам математики, информатики, физики и химии, секция „Оптические, математические и электронные методы обработки изображений и сигналов" в 2004 г. (г. Москва, РУДН), Международной конференции „Распределенные вычисления и грид-технологии в науке и образовании" в 2004 г. (г. Дубна), научном семинаре МНТОРС им. Попова в 2004 г. (г. Москва).

Публикации. По материалам диссертационной работы имеется 6 публикаций.

Диссертация состоит из 4 глав. Первая глава посвящена анализу постановки задачи построения поисковых систем по содержанию изображений. В разделе 1.1. дается введение в проблематику поисковых систем, рассмотрены основные понятия и изложены принципы их функционирования. Описаны области применения ПС и типы поиска по содержанию, такие как точное соответствие, композиционное сходство и семантическое соответствие. Само понятие ПС и принципы поиска информации представлены в разделе 1.2., рассмотрены основные модели построения поисковых систем - булевская (раздел 1.2.1.), векторная (раздел 1.2.2.) и вероятностная (раздел 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 диссертации, имеют прикладное значение и используются при проектировании и практической реализации поисковой системы.

Третья глава посвящена применению полученных в диссертации теоретических результатов в построении поисковой системы по содержанию изображений , рассматривается архитектура, построенная на основе математической модели. В разделе 3.1. приведена общая архитектура системы, описаны основные функциональные требования и компоненты ПС. В разделе 3.2. рассматриваются алгоритмы формирования индекса поисковой системы и организации поиска в индексе, рассматривается модель инвертированных списков и предлагаются способы повышения эффективности поиска. Раздел 3.4. посвящен проблемам построения распределенных поисковых систем, рассмотрены способы построения распределенного индекса, предложена модель распределенной поисковой системы.

Четвертая глава посвящена реализации поисковой системы и анализу ее эффективности. В разделе 4.1. описана функциональность ПС и основные сценарии взаимодействия пользователя с ПС. В разделе 4.2. приведена программная архитектура поисковой системы с использованием нотации 11МЬ, даны пояснения по аспектам реализации. В разделе 4.3. изложены общие принципы реализации системы, рассмотрены технологии, которые применялись при реализации. В разделе 4.4. приведен анализ результатов работы поисковой системы.

ЗАКЛЮЧЕНИЕ

Основными теоретическими и практическими результатами являются:

• Построена математическая модель поисковой системы по содержанию изображений

• Создана универсальная архитектура поисковой системы по содержанию изображений

• Предложены два новых метода построения числового описания объекта на изображении

• Предложены методы оптимизации поиска изображений

• Описан подход к построению распределенной поисковой системы, создана ее модель и описаны протоколы взаимодействия компонент такой системы

• Создана программная реализация поисковой системы по содержанию изображений

• Проведены экспериментальные исследования по оценке результатов поиска и характеристик производительности поисковой системы.

1. Люггер Д. Искусственный интеллект. — М.: Вильяме, 2003.

2. Gudivada V., Raghavan V., Grosky W. Information retrieval on the World Wide Web // IEEE Transactions Internet Computing. — No 10. — 1997.

3. Chang С. C., Lee S. Retrieval of Similar Pictures on Pictorial Databases // Pattern Recognition. — No 7. — 1991.

4. Enser P. G. B. Query Analysis in a Visual Information Retrieval Context // Journal of Document and Text Management. — No 1. 1993.

5. Kato T. Database Architecture for Content-Based Image Retrieval // Proceedings of Society of the Photo-Optical Instrumentation Engineers: Image Storage and Retrieval. — San Jose, California, USA, 1992.

6. Bimbo A. D. Visual Information Retrieval. — New York: Morgan Kaufmann, 1999.

7. Rui Y., Huang T. S., Chang S.-F. Image Retrieval: Current Techniques, Promising Directions, and Open Issues // Journal of Visual Communication and Image Representation. — No 1. — 1999.

8. Batley S. Visual Information Retrieval: Browsing Strategies in Pictorial Databases // 12th International Online Information Meeting: ONLINE88 Information. — London, England, 1988.

9. Cavnar W., Gillies A. Data retrieval and realities of document donversion // 1st Annual Conference on the Teory and Practice of Digital Libraries. — College Station, TX, USA, 1994.

10. Agnew В., Faloustos C. Multimedia index over Web // SPIE Conference on Storage and retrieval. — Pittsburgh, PA USA, 1997.

11. Jacobs C., Finkelstein A., Basri R. Fast multiresolution image querying // SIGGRAPH-95. 1995.

12. Enser P. Query analysis in a visual information retrieval context // Document and Text Management. — No 1. — 1993.

13. Benitez A., Beigi M. Using relevance feedback in content-based image metasearch // IEEE Internet Computing. — No 4. — 1998.

14. Booch G., Rumbaugh J., Jacobson I. The Unified Modelling Language User Guide. — MA: Addison-Wesley, 1998.

15. Booch G.} Rumbaugh J., Jacobson I. The Unified Modelling Language Reference Manual. — MA: Addison-Wesley, 1998.

16. Baeza-Yates R., Riberio-Neto B. Modern Information Retrieval. — New York: Addison-Wesley, 1999.

17. Klass W., Sheth A. Special issue on metadata for digital media // SIGMOD Record. No 4. - 1994.

18. Новиков Ф. Дискретная математика для программистов. — СПб: Питер, 2001.

19. Bookstein A. Implication of Boolean structure for probabalistic retrieval // 8th Annual International ACM/SIGIR Conference. — Denver, USA, 1985.

20. Salton G. The SMART retrieval system. Experiments in Automatic Document Processing. — MA: Prentice Hall, 1971.

21. Saltón G., Lesk E. Computer evaluation of indexing and text processing // Journal of ACM. — No 8. — 1968.

22. Robertson S., Jones K. Relevance weighting of search terms // Journal of American Society for Information Sciences. — No 3. — 1976.

23. Fuhr N. Probabilistic models in information retrieval // Information Processing and Management. — No 25. — 1989.

24. Croft W., Harper D. Using probabilistic models of retrieval without relevance information // Information Technology: Research and Development. — No 2. — 1983.

25. Furuta R. Defining and using structure in digital documents // 1st Annual Conference on the Teory and Practice of Digital Libraries. College Station, TX, USA, 1994.

26. Swain M., Ballard D. Color Indexing // Int. Journal of Computer Vision. No 1. - 1991.

27. Nathans J., Thomas D., Hogness D. Molecular genetics of human color vision: The genes encoding blue, green and red pigments // Science 232. — No 1. 1986.

28. Marr D., Hildreth E. Theory of edge detection // Proceedings of Royal Society of London, B207. — 1980.

29. Canny J. A Computational Approach to Edge Detection // IEEE Trans, on PAMI. No 8. - 1986.

30. Ma W., Manjuhath B. Texture features and learning similarity // IEEE Conference on Computer Vision and Pattern Recognition. — Chicago, 1996.

31. Card S., MacKinlay J., Shneiderman B. Readings in Information Visualisation. — NY: Morgan Kauffman, 1998.

32. Swain M. J., Ballard D. H. Color indexing // International Journal of Computer Vision. — No 7. — 1991.

33. Flickner M., Sawhney H., Niblack W. Query by image and video content: the QBIC system // IEEE Computer. — No 9. — 1995.

34. Strieker M., Orengo M. Similarity of color images // Conference Storage and Retrieval for Image and Video Databases III. — San Jose, CA, USA, 1995.

35. Rubner Y., Tomasi C., Guibas L. The earth movers distance as a metric for image retrieval // International Journal of Computer Vision. — No 2. — 1999.

36. Pass G., Zabih R., Miller J. Comparing images using color coherence vectors // ACM International Conference on Multimedia. — Boston, MA, USA, 1996.

37. Strieker M., Dimai A. Color indexing with weak spatial constraints // Storage and Retrieval for Image and Video Databases IV. San Jose, CA, USA, 1996.

38. Huang J., Kumar S., Mitra M. Spatial color indexing and applications // IEEE International Conference on Computer Vision (ICCV). Bombay, India, 1998.

39. Ashley J., Barber R., Flickner M. Automatic and semi-automatic methods for image annotation and retrieval in QBIC // Conference Storage and Retrieval for Image and Video Databases III. — San Jose, CA, USA, 1995.

40. Chang J. S. S. Local color and texture extraction and spatial query // IEEE International Conference on Image Processing. — Lausanne, Switzerland, 1996.

41. Wang J., Li J., Wiederhold G. SIMPLIcity: Semantics-sensitive integrated matching for picture libraries // Advances in Visual Information Systems (VISUAL). — Lyon, France, 2000.

42. Liu F., Picard R. Periodicity, directionality, and randomness: wold features for image modeling and retrieval // IEEE Transactions on PAMI. — No 7. — 1996.

43. Puzicha J., Rubner Y., Buhmann J. Empirical evaluation of dissimilarity measures for color and texture // IEEE International Conference on Computer Vision (ICCV). — Kerkyra, Greece, 1999.

44. Dimai A. Rotation invariant texture description using general moment invariants and Gabor filters // Scandinavian Conference on Image Analysis (SCIA). — Kangerlussuaq, Greenland, 1999.

45. Chen C. H. A study of texture classification using spectral features // In Proceedings of the 6th International Conference on Pattern Recognition. — Boston, MA, 1982.

46. Carlucci L. A formal system for texture languages // Pattern Recognition. — No 1. — 1972.

47. Haralick R. M., Shanmugam K., Dinstein I. Textural features for image classification // IEEE Transactions on Systems, Man and Cybernetics. — No 3. — 1973.

48. Veltkamp R., Hagedoorn M. State-of-the-art in shape matching // Technical Report UU-CS. No 27. - 1999.

49. Hu M. Visual pattern recognition by moment invariants // IEEE Trans, on Information Theory. — Vol. IT-8. — 1962.

50. Zahn C., Roskies R. Fourier descriptors for plane closed curves // IEEE Transactions on Computers. — No 3. — 1972.

51. Mehra P., Wah В. Artificial Neural Networks: Concepts and Theory. — IEEE Computer Society Press, 1992.

52. Уоссермен Ф. Нейрокомпьютерная техника. — СПб: Мир, 1992.

53. Кальоти Д. От восприятия к мысли. — М.: Мир, 1998.

54. Gordon I. Theories of Visual Perceptions. — John Wiley and Son, 1997.

55. Мирошкин А. О вопросе построения поисковых систем по содержанию изображений // Тезисы XL Всероссийской конференции по проблемам математики, информатики, физики и химии. Москва: РУДН, 2004.

56. Мирошкин А., Гостев И. Математическая модель одного класса поисковых систем // Вестник Российского Университета Дружбы Народов, серия 'Прикладная и компьютерная математика', Т. 3, № 1. — 2004.

57. Гостев И. М. О методах распознавания графических образов // Изв. РАН ТиСУ. № 1. - 2004.

58. Дейт К. Д. Введение в системы баз данных. — М.: Вильяме, 1999.

59. Мирошкин А. Об одном методе ранжирования формы объектов в графических поисковых системах // Тезисы межрегиональной научно-технической конференции 'Интеллектуальные информационные системы'. — Тула, 2003.

60. Saltón G. Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer. — MA: Addison-Wesley, 1989.

61. Bates M. The design of browsing and berrypicking techniques for online search interface // Online Review. — No 2. — 1989.

62. Мирошкин А. Применение алгоритма Arch height в системе поиска изображений // Тезисы межрегиональной всероссийской конференции по проблемам математики, информатики, физики и химии. — Москва, 2002.

63. Croft W. What do people want from information retrieval? // D-Lib Magazine. — No 11. — 1995.

64. Arms W., Blanchi C., Overly E. An Architecture for Informtaion in digital libraries // D-Lib magazine. — No 2. — 1997.

65. Bertino E., Martino L. Object-Oriented Database Systems. — Addison-Wesley, 1993.

66. Abiteboul S. Querying semi-structured data. // Int. Conference on Database Theory. — 1997.

67. Hancock-Вeaulieu M., Fieldhouse M. An evaluation of interactive query expansion in online library catalogue with a graphical user interface // Journal of Documentation. — No 5. — 1995.

68. Berchtold S., Boehm C. Fast similarity search in multimedia databases // ACM SIGMOD Int. Conf. on Management of Data. — Tucson, Arizona, USA, 1997.

69. Hildreht C. The use and understanding of keyword searching in an university online catalog // Information Technology and Libraries. — No 16. — 1997.

70. Byers D. Full-text indexing of non-textual resources // 7th WWW Conference. 1998.

71. Кнут Д. Э. Искусство программирования. — М.: Addison-Wesley, 2000.

72. Fernandez M., Forescu D., Levy A. A query language for a Website management system // SIGMOD Record. — No 3. — 1997.

73. Bartell В., Cottrell G. Latent semantic indexing is an optimal special case of multidemensional scaling // 15th annual international ACM SGIR conference. — 1992.

74. Tanenbaum A. S., van Steen M. Distributed Systems: Principles and Paradigms. — Prentice Hall, 2002.

75. Coulouris G., Dollimore J., Kindberg T. Distributed Systems: Concepts and Design. — Addison-Wesley, 2000.

76. Dolin R.} Agrawal D. Pharos: a scalable distributed architecture for locating heterogeneus information sources // 6th CIKM Conference. — Las Vegas, Nevada, USA, 1997.

77. Мирошкин А., Гостев И. О методах индексации больших потоков информации на основе систем распределенных вычислений. Дубна ОИЯИ, 2004.

78. Jeyong В., Omiecinski Е. Inverted file partitioning schemes in multiple disk systems // IEEE Transactions. — No 2. — 1995.

79. Gauch S., Wang G., Gomez M. ProFusion: Intelligent fusion from multiple distributed search engines // Journal of Universal Computing. — No 2. — 1996.

80. Мирошкин А., Гостев И. О методах индексации больших потоков информации на основе систем распределенных вычислений // Международная конференция 'Распределенные вычисления и грид-технологии в науке и образовании'. — Дубна ОИЯИ, 2004.

81. Wilson В. J. JXTA. NY: New Riders Publishing, 2002.

82. Gamma E., Helm R. Design Patterns. Elements of reusable Object-Oriented Software. — Addison-Wesley, 1995.

83. Робинсон С. для профессиналов. — M.: Лори, 2003.

84. Cooper A. About Face: The Essentials of User Interface design. — Boston: IDG Books, 1995.

85. Tague-Sutcliffe J. Measuring the informativeness of a retrieval process // 15th annual int. ACM SIGIR Conference on reasearch and development in information retrieval. — Copenhagen, Denmark, 1992.