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



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

Трубаков Андрей Олегович

МЕТОДЫ И АЛГОРИТМЫ МНОГОМЕРНОГО МОДЕЛИРОВАНИЯ ПРОСТРАНСТВА ХАРАКТЕРИСТИК ИЗОБРАЖЕНИЙ

Специальность 05.13.18 - «Математическое моделирование, численные методы и

комплексы программ»

АВТОРЕФЕРАТ

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

Брянск-2011 1 6 нюн М11

4850371

Работа выполнена на кафедре «Информатика и программное обеспечение» ГОУ ВПО «Брянский государственный технический университет»

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

кандидат технических наук, профессор ГУ ЛАКОВ Василий Константинович

Официальные оппоненты

доктор технических наук, профессор КАМАЕВ Валерий Анатольевич

кандидат технических наук, доцент КАЗАКОВ Павел Валерьевич

Ведущая организация

ГОУ ВПО «Брянский государственный университет имени академика И.Г. Петровского»

Защита состоится « 21 » июня 2011 года в 16 часов на заседании диссертационного совета Д 212.021.03 при ГОУ ВПО «Брянский государственный технический университет» по адресу: 241035, г. Брянск, бульвар 50-летия Октября, 7, учебный корпус №2, ауд. 220.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Брянский государственный технический университет».

Автореферат разослан « 20 » мая 2011 года.

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

Шкаберин В. А.

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

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

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

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

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

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

Если учесть, что к настоящему моменту методы выделения характеристик из изображения достаточно хорошо исследованы, а методы оперирование большими объемами векторов этих характеристик в многомерном пространстве находятся в

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

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

2. Исследование существующих математических методов многомерного моделирования пространства характеристик (в том числе индексов пространств большой размерности).

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

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

5. Разработка принципов построения отношений между объектами многомерного пространства характеристик изображений и знаниями прикладной области, текстовыми описаниями, лексемами.

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

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

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

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

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

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

тодов и алгоритмов:

• оригинальный метод сокращения размерности пространства в вершинах многомерного дерева за счет использования матриц сокращения, позволяющий повысить эффективность операций доступа;

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

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

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

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

5. Разработаны эффективные численные методы обработки изображений для систем на основе многомерного индекса: сегментация изображений, формирование адаптивной палитры, сравнения цветового исполнения с использованием компенсационного расстояния.

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

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

2. Разработанный программный комплекс поиска изображений по содержанию «Дизайнер+».

3. Разработанный программный комплекс распознавания дефектов в эпитаксиальных пленках кремниевых пластин (РДЭП).

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

• Программный комплекс распознавания дефектов в эпитаксиальных пленках кремниевых пластин «РДЭП» зарегистрирован в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам. Он также внедрен в научно-исследовательскую деятельность отдела развития ЗАО «Группа Кремний Эл».

• Разработанный программный комплекс поиска изображений по содержанию в дизайнерских коллекциях «Дизайнер+» внедрен в отдел дизайна и печатной подготовки ООО «ТетраПром» для создания полиграфической продукции. Также он используется в учебном процессе в рамках самостоятельной и исследовательской работы студентов и аспирантов кафедры «Информатика и программное обеспечение» Брянского государственного технического университета.

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

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

2. Принципы формирования матриц сокращения размерности пространства,

композитной функции расстояния и построения двойного упакованного дерева.

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

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

5. Архитектура и функциональные характеристики разработанных проблемно-ориентированных программных комплексов «Дизайнер+» и «РДЭП».

Апробация результатов работы. Основные положения и наиболее важные научные и практические результаты диссертационной работы докладывались и обсуждались на 7 международных и российских конференциях, в том числе 58-й научной конференции профессорско-преподавательского состава БГТУ (г. Брянск, 2008); международной научно-практической конференции «Наука и производство - 2009» (г. Брянск, 2009); II научно-технической конференции «Информационные системы и технологии 2009» (г. Обнинск, 2009); международная научно-практическая конференции «Состояние, проблемы и перспективы автоматизации технической подготовки производства на промышленных предприятиях» (г. Брянск, 2009); научно-практической конференции «Современные проблемы информатики и прикладной математики» (г. Брянск, 2010); научно-практической конференции «Достижения молодых ученых в развитии инновационных процессов в экономике, науке, образовании» (г. Брянск, 2010); научно-технической конференции «Информационные технологии, энергетика и экономика» (г. Смоленск, 2011).

Публикации. По теме диссертации опубликовано 12 печатных работ, в том числе 1 монография и 3 статьи в научных журналах, рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, библиографического списка, содержащего 131 наименование и приложений. Работа изложена на 197 страницах, содержит 40 рисунков и 11 таблиц. Общий объем работы составляет 214 страниц.

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

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

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

Научные основы математических методов многомерного индексирования заложены в работах Д. Бентли, В. Гейда, А. Генрича, А. Гуггмана, О. Гюнтера, Г. Крэйгала, К. Лин, И. Маналополуса, Д. Нивергелта, Г. Самета и др. Анализ этих работ позволяет сделать вывод о возможности разработки эффективного численного

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

На основе работ Н.С. Васильевой, А. Вежневец, Р. Вудса, А.Е. Лепского, В.В.Лукина, Б.А.Новикова, H.H.Пономаренко, С.В.Поршнева, А.С.Потапова, П.Ю. Пытьева, Дж. Стокмана, Л. Шапиро, Б. Яне, и др. рассмотрены основные подходы к обработке и поиску изображений и место методов многомерного моделирования пространства характеристик в общем спектре технологий. Также в первой главе рассматриваются многомерные методы на предмет того, что нового они могут внести в существующие классические подходы к поиску.

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

Согласно работам Т.А. Летова, А.П. Михайлова, A.B. Пантелеева, A.A. Самарского, Б.Я. Советова, П.В. Трусова, С.А. Яковлева и др. проведена декомпозиция сложной задачи поиска на ряд более простых подзадач и построена структурно функциональная модель. После этой декомпозиции каждая подсистема проанализирована отдельно, предложены методы и новые алгоритмы по её усовершенствованию и адаптации для систем, основанных на поиске в многомерном пространстве характеристик изображений.

Предобработка. Основная цель данной стадии - убрать помехи и шумы. Предобработку предлагается делать с помощью итерационного наложения фильтров: /О = /¡(/(!~Ч 0[), где - изображение, после выполнения 1-о этапа обработки; f¡ - 1-я функция обработки; 8¡ - дополнительные параметры, необходимые для выполнения /[. В качестве основных предлагается использовать линейные пространственные фильтры и обработку в частотной области. Сам по себе этот этап не накладывает ограничений на методы индексирования, а только позволяет произвести более точную оценку характеристик изображения.

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

W3ij = (tfi ■ DistCE (Col¡"\ Coljv)) + Kz ■ DistCE (Col¡b), Coí-tb))j ■

. ^_g-Кз'пйп {5ztlSzy} + ^

где wg¿j - вес ребра 1рафа между i-й и j-й вершинами; К], К2, К3 - весовые коэффициенты влияния среднего цвета (Col(v>), цвета на границе областей (Col®) и размера областей (Sz); DistCE{...~) - формула разности двух цветов. Исследование качества предложенного алгоритма проводилось на основе специально предназначенных для подобных целей базы изображений университета Беркли.

Цветовое исполнение. В этом подразделе анализируются способы оценки цве-

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

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

к

£ (С°Ь-*)2> (2)

где к - число кластеров; С1; - полученные кластеры (I = 1, к); - центр масс векторов Со1е С7(. После выполнения алгоритма кластеризации 1-й цвет палитры определяется как средний цвет ¡-о кластера В качестве меры расстояния для алгоритма кластеризации предлагается использовать СГЕБЕ2000 (мера международной комиссией по освещенности (МКО)), что позволяет создать палитру, адаптированную под человеческое восприятие. При этом для быстрого преобразования предлагается ввести понятие карты трансформации (массив коэффициентов прямого перевода из равномерной палитры в адаптивную).

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

ДН=Н1-Н2, ДЯ = АНТ ■ Сот, Я2) = у/АН • ЕнТ, (3)

где Я - гистограмма; Сот - матрица компенсаций, учитывающая возможность замены одних оттенков (элементов гистограммы) другими. Это расстояние подобно часто используемому расстоянию Махаланобиса, но имеет лучшую разграничивающую способность для гистограмм с ярко выраженной модой.

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

Форма, контур и положение сегментов. В качестве критериев контура, формы и положения используются: относительная площадь, центр масс, приближение аппроксимирующими фигурами, центральные моменты, среднее радиальное расстояние, компактность Харалика. Все эти критерии оцениваются, нормализуются, и

формируется набор коэффициентов для многомерного вектора характеристик.

Индекс. Одной из ключевых частей всего процесса поиска является многомерный индекс:

INDEX =<l,V,u>. (4)

где I = {/1( ¡2,...} - набор изображений, каждому из которых соответствует набор

однородных сегментов js^s^» ••■]; У = {Vj, V2,...} - соответствующий сегментам набор векторов характеристик; u(Vj) - биективная функция соответствия векторов и графических образов (сегментов), такая, что:

Si =u(V,),VSt €S,VV( ev. (5)

При этом поиск подобных изображений сводится к поиску рядом расположенных векторов в многомерном пространстве характеристик согласно некоторой функции расстояния Dist(...):

Search(Smpl) = [Snear | VS":Dist(s",Stmpl) > DlstiS^.S^)}, (6) где Stmpi - сегмент шаблона, для которого производится поиск лучшего совпадения; Snear - наилучший вариант для шаблона Stmpi.

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

Связь с семантической сетью. По мнению большинства исследователей одной из сложнейших проблем поиска изображений является проблема «семантического разрыва». В данной работе предлагается для её решения использовать связь многомерного индекса с семантической сетью

SemanticNet = < С,R>, (7)

где С - множество понятий; R - множество отношений между понятиями. Для связи многомерных векторов и понятий предлагается ввести базу нечетких отношений:

Relations =<V,C, Link >, (8)

где V - множество листовых вершин многомерного иерархического индекса (соответствующих графическим объектам); С - множество концептов семантической сети; Link - множество связей между множествами Уи С:

Link = ¿2i — }> Lt = {Vl,Ct,wl) distt}, (?)

где Vj - вектор многомерного пространства из множества V; Cj - концепт из множества С; Wj - вес связи, отвечающий за точность описания данного графического объекта выбранным концептом; distj - вспомогательная мера согласования связи. Связь индекса и семантической сети представлена на рис. 1.

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

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

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

Древовидный индекс векторов характеристик

|Уб|у^1^|УИУц||Уц| |У12|У1З1|УИ1У1?У^у

Концепт С2

Концепт С\

Концепт С4

---1 Концепт Сз |||---—

Семантическая сеть

I

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

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

Каждый узел дерева представляет собой массив, элементы которого содержат ссылки на потомков и минимальные ограничивающие прямоугольники (МЕЖ) связанного с ними пространства:

[МВЯ_потомка, ссылка_на_потомка]. МВЛ вершин дерева задаются в виде набора МВ11={ЕьЕ2,...,Еа}, где Е; - это интервал с закрытыми концами [а,Ь], характеризующий размер объекта по соответствующей оси координат

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

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

Для решения этой проблемы предлагается перейти от общей функции расстояния к композитной функции, которая включает хорошо исследованные и проверенные части. Для подобного перехода общий вектор характеристик У= {К1Д2,...} разбивают на логические группы У= {Сьвг,...} = {{К^Кг,...},^,К;+1,...},...}. При этом необходимо выполнение следующих условий:

1. Множество критериев V состоит из подмножеств в*:

С* сУ. У = ■ (10)

к

2. В каждой группе С* = {^1,^2. —} должно быть как можно меньше компонентов. В идеальном случае размер группы должен быть равен 3-7. Это связано с проблемой перекрытия регионов, характерной для всех многомерных структур.

3. В пределах одной группы критериев = {К1,К2,...} должна применяться одна общая групповая функция расстояния дк — (К'1, К2,...).

4. Критерии одной группы должны быть логически совместимы и имел, общее представление в итоговой композитной функции расстояния 01зЬ(д1,д2, —), в которую будут подставляться результаты вычисления расстояний в каждой группе.

Однако большинство современных методов не позволяют использовать такие сложные функции для построения многомерного дерева. Для решения этой проблемы в работе предлагается использовать сокращенное пространство в каждом узле дерева. Для этого вводится понятие матрицы сокращения М размером 3. X й (<1 -размерность исходного пространства, 3. - размерность сокращенного пространства). Эти матрицы используются для разбиения вектора Уна группы {С1( С2, — }.

Формируются матрицы сокращения следующим образом: пусть имеется логическая группа = {А"®, К2 — }> гДе '- номер ключа К® в исходном векторе характеристик V. Тогда к-я матрица сокращения Мк для этой группы примет вид:

Мк[ип =

0, если I Ф I для К,

(О

V

г(0

(П)

К1

1, если I = I для Ку

В процессе построения индекса и его использования при поиске для получения к-го сокращения V, необходимо исходный вектор V перемножить с матрицей М^:

V = V7 ■ Мк. (12)

Пример дерева с матрицами сокращения показан на рис. 2. В работе предложены новые алгоритмы для этого дерева, позволяющие:

• обеспечить произвольное следование матриц сокращения (это дает разработчику свободу выбора последовательности матриц и ориентацию системы на те критерии, которые более важны в данный момент времени);

• рост дерева сверху вниз, позволяю-

Рис. 2. Дерево с матрицами сокращения

--V V?

J 1 Уз —

(

.'Яъ..

,\7„'

щий производить отдельную балансировку частей и не перестраивать все дерево.

Помимо всего прочего в диссертационной работе показано, что использование в узле дерева пространства меньшей размерности позволяет решить две проблемы:

• большая размерность пространства <1 влечет за собой большие пересечения МВЯ внутренних узлов (Нп^-коШДМВЯОО]) = 100%), что может привести к полной деградации индексной структуры;

• для практических реализаций с заданным размером внутренней вершины арность т пропорциональна размерности (т~1/й), а в свою очередь высота дерева зависит от арности Л » N. Поэтому скорость поиска по дереву и эффективность структуры имеют косвенную зависимость от размерности пространства.

Матрицы сокращения уменьшают размерность <1 пространства в вершине дерева до приемлемого значения 3., что позволяет избавиться от обеих проблем.

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

В рамках работы было введено понятие нецелевой вершины: вершина УВ!( называется нецелевой для запроса (¿(УШр1), если матрица сокращения этой вершины Мк выделяет такую группу характеристик Ск = {К^К^...}, компоненты К1 которой неопределенны в векторе Ущц (уК( е вк •■ £ У1тр1).

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

Однако разработка методов и алгоритмов индексирования графических данных сталкивается с еще одной важной проблемой - противоречивые требования к выбору арности дерева ш. С одной стороны описанные проблемы приводят к необходимости малого значения т (при т=2 описанные проблемы не сильно влияют на производительность). С другой стороны в работе показано, что высота дерева (следовательно, и количество обращений к внешней памяти) К ~ 1ойт N (где N - число объектов). Таким образом, уменьшение т губительно сказывается на скорости.

Для решения противоречия требований к выбору арности ш в работе предложе-

но использовать двойное упакованное дерево (рис. 3), по аналогии с иЗО-дерсвом. Внутреннее дерево, в котором хранятся критерии и матрицы сокращения Мъ является малоарным (например, ш=2). Это значительно уменьшает негативные последствия наличия нецелевых вершин Чнц и позволяет при небольшом количестве объектов ввести в

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

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

Для еще большего повышения производительности в работе предлагается периодически производить критериальную балансировку. Если некоторому узлу V' сопоставлена матрица Мц, которая сокращает вектор до группы Ск1, а его потомкам - матрица Мк2, причем группа позволяет получить больше отсечений альтернатив в процессе поиска, то необходимо произвести обмен матрицами сокращения на этих двух уровнях. Таким образом происходит перемещение более релевантных критериев вверх по дереву, что позволяет повысить эффективность структуры.

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

Для оценки эффективности узла предлагается в каждую вершину дерева добавить два дополнительных поля: число запросов М$еатс д и суммарный процент отсечения Е5итп. В процессе выполнения поиска во всех затронутых узлах происходит увеличение первого поля на 1, а второго - на количество отброшенных потомков = Дялл + Есит > гДе Ешт ~ суммарный процент отсечения после выполнения 1 запросов; Есиг - число отброшенных потомков вершины при выполнении текущей поисковой операции). Таким образом происходит накопление статистики эффективности разных узлов дерева. Результирующие условия балансировки примут вид:

1. Число запросов Нетгсь в вершине V и в каждом из его потомков СЫИ(У) должно быть больше порогового значения Л?'1агсЛ:

™5еагсЛ>лС,Л л ЧУ е сыы(у): У'.м,еагск > ы?еагск. (13)

2. Среднее значение целевой функции в потомках вершины V должно быть больше значения этой функции в самом узле:

мвди(к) = у МВй(К') ,МВПп(У) = £ мвя(Опмвк(и").

/еСЫИОО у'етш(у), г\*г\

ч" 6ШШ(Ю, ^

3. Все потомки V должны иметь один и тот же номер матрицы сокращения (во всех потомках должна использоваться одна и та же группа критериев).

Если все эти условия выполнены для некоторого узла V, то критериальная ба-

(14)

V Е

Рипст = — ■ (1 - Оуег1ап(У}),

(15)

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

Еще одним моментом, которому уделяется особое внимание в работе, является общая функция подобия 01з1(д1,д2, ...)• В нее подставляются результаты групповых функций (КЪК2,...). Большинство предлагаемых на сегодняшний день функций используют для комбинации различные аддитивные методики. Однако такие функции условно можно отнести к группе реализующих связку «логическое ИЛИ», а для поиска изображений это не всегда подходит (в работе разобран ряд примеров, демонстрирующих данный факт).

Для реализации в разрабатываемых методах индексирования предлагается использовать комбинацию следующих двух функций. Для связки критериев по принципу «логкческое И» предлагается мультипликативная функция:

п

= Р]((1 - IV;) + IV, ■ Ю , (18)

í=l

где - результат функции 01з1д1(К1,К2,...) для ьй группы критериев, нормализованный таким образом, что для совпадающих элементов он выдает значение 1, а для абсолютно разных - 0; н^ - вес 1-й группы критериев в данном запросе.

Однако в случае необходимости связки «логическое ИЛИ» можно использовать взвешенную свертку:

л

Тг, -= (19)

1=1

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

Также в работе затрагивается проблема «проклятия измерений» - с ростом размерности пространства эффективность любой структуры падает. Однако введенные принципы позволяют значительно снизить негативный эффект. Во-первых, это происходит за счет того, что в качестве общей функции 015^дг,д2,...) используется мультипликативная функция, которая меньше подвержена данному влиянию. Во-вторых, в каждом узле дерева применяются матрицы сокращения, которые позволяют оперировать подпространствами меньшего размера.

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

Программный комплекс распознавания дефектов в эпитакснальных пленках кремниевых пластин (РДЭП). Для проверки математических методов моделирования многомерного пространства характеристик изображений был разработан и внедрен проблемно-ориентированный программный комплекс «РДЭП». Разработка проводилась для отдела развития ЗАО «Группа Кремний Эл». Эффект от внедрения ПК РДЭП достигается за счет сокращения временных и ресурсных затрат и повышения точности обработки изображений опытных образцов кремниевых пластин, используемых для аттестации новых технологических процессов.

На основе этого комплекса удалось провести детальное исследование параметров предложенных методов, а также развить идеи связи векторов многомерного

пространства и семантической сети. Архитектура комплекса представлена на рис. 4.

Аппаратная составляющая

С.> Электронный^ микроскоп )

ъ

С, Камера- Л Т окуляр )

Г Подсистема получения 1 I

| _фотографий I I

| С Подсистема

. I управления

I4-

¡->ч1[ Построение ^ „„яыога

^|и^фаШткВИ™^ 0Д

отображения

I

)!

галучение конвертирование кадров Подсистема |

_Подсистема обработки_

(Диффврвнцироеа- Л-/* Подсистема Выравнивание Л

у нио изображения фшьпюации освещдцности )

С Поиск технологи- Л /" Пороговая V/' ЛвтппХ,япЛП1 Л чвских областей ) Автоповорот )

освещ^цности

1 I | I

Получение характеристик

Яркость^ Контур ^ ^ Форма ^Текстура^ ^Положенив^

а?

эо

05

в ~ 39 1° Ч

(П з

£ о 'э §

с 3

II

¡з=й

1 Интерфейс ] пользователя

Индекс

Семантическая сеть

, - < Формирование —! отчета

Рис. 4. Архитектура программного комплекса РДЭП Подсистема получения фотографий предназначена для автоматического получения видеопотока с микроскопа и формирования отдельных кадров для дальнейшего анализа. Для получения видеопотока используется технология БпейВЬоху.

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

Подсистема индексирования и распознавания дефектов является ядром программного комплекса РДЭП. В ней происходит расчет параметров изображений дефектов и их распознавание на основе предложенного в диссертационной работе многомерного индекса.

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

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

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

нологического процесса.

Подсистема управления отчетами предназначена для хранения и управления отчетами и базой предыдущих экспериментов.

Программный комплекс РДЭП зарегистрирован в Роспатенте. Разработка модулей велась в среде MS Visual Studio 2008. Подсистемы получения фотографий и их обработки написаны на языке С-н-, так как заложенные в них алгоритмы требовательны к вычислительным ресурсам. Остальные части комплекса разрабатывались на языке С#. Для связи подсистем использовалась прослойка на языке C-H-/CLI.

Программный комплекс поиска изображений по содержанию «Дизайнер+». Данная разработка предназначена для поиска изображений по визуальному подобию в дизайнерских коллекциях. Комплекс внедрен в отдел дизайна и печатной подготовки ООО «ТетраПром». Экономический эффект от внедрения достигается за счет повышения качества подготавливаемой полиграфической продукции и сокращения временных и ресурсных затрат на разработку дизайнов новой продукции. Архитектура программного комплекса представлена на рис. 5.

Г ~угёЫгомпонён7 ~ I Г

I ^ графический ^ (С; ^ ^ I

( подсистема Л .

II Ф< I V сегментирования J '

ядро

подсистема фильтрации ^

пользователь

сервисные подсистемы (авторизация, упр. польз., мат. и т.д.)

' ~ "компонент индексирования

подсистема управления индексированием

'подсистема обработки и конвертирования граф. ч информации

Рис. 5. Архитектура программного комплекса «Дизайнера» У/еЪ-компонент является клиентской частью. Он позволяет производить поиск по готовому изображению или эскизу (имеется встроенный графический редактор). Также weЪ-кoмпoнeнт поддерживает функции авторизации и администрирования.

Компонент индексирования выполнен в виде отдельного консольного приложения. Это позволяет администратору запускать индексирование в фоновом режиме, по определенным событиям или в планировщике. Основная задача данного компонента - рассчитать характеристики для всех переданных изображений и добавить получившиеся вектора в многомерный индекс.

Компонент обработки является ядром системы. В нем сосредоточены все функции по обработке изображений, сегментации, получения характеристик. Также в нем организована система поддержки поиска в многомерном пространстве. Этот компонент выполнен в виде отдельного <111-модуля, что позволяет использовать его и в \уеЬ-компоненте, и в компоненте индексирования.

Компонент хранения предназначен для хранения настроек и данных программного комплекса. Многомерный индекс (многомерное дерево векторов харак-

теристик) хранится в виде индексного файла разбитого на блоки, каждый из которых представляет собой вершину внешнего дерева. Сами графические файлы находятся в файловом хранилище и на них организованы ссыпки в листовых вершинах многомерного дерева. Для сервисных нужд web-компонента (настроек, дополнительной информации) используется СУБД MS SQL Express.

Разработка модулей велась в среде MS Visual Studio 2008. При этом использовались языки программирования ASP.NET (web-компонент), С# (некритичные к вычислительным ресурсам участки кода), C++/CLI (обработка графики и операции, критичные к вычислительным ресурсам).

В пятой главе приводится результат исследования эффективности предложенных математических методов и их опытная проверка на основе разработанных программных комплексов «Дизайнер+» и «РДЭП».

Для оценки точности поиска использовался программный комплекс «Дизай-нер+». Методика оценки и тестовая база использованы от Российского семинара оценки методов информационного поиска (РОМИП). В качестве метрики выбрана Precision(lO). Результат обрабатывался асессорами, которые каждой паре изображений выставляли одну из трех оценок: strong (похожи), weak (отдаленно похожи), не похожи. Для слияния оценок использовалась методика согласования (and - сильная согласованность, vote - средняя согласованность, or - слабая согласованность).

В разнородной коллекции результат оказался следующим: strongVweak-or -88%, strong-and - 22%. Из этих данных можно сделать вывод, что в среднем из 10 первых изображений только одно, по мнению всех асессоров, попало в результат не обосновано (полностью не похоже на заданный шаблон). Также исследовалась работа программного комплекса на реальных коллекциях изображений, для которых результат оказался чуть лучше (strongVweak-or - 95%, strong-and - 36%). Это связано с тем, что система разрабатывалась и адаптировалась именно для таких коллекций.

Проверка идей связи многомерного индекса и семантической сети проводилась с помощью программного комплекса РДЭП. Эксперименты на реальных фотографиях кремниевых пластин показали, что результат распознавания одиночных ярко выраженных дефектов типичной структуры составляет более 99%. Дефекты на нечетких снимках с большим искажением или дефекты с неярко выраженными визуальными характеристиками распознаются многомерным индексом хуже (количество ошибок возрастает до 20-30%). Однако использование дополнительных знаний семантической сети позволяет повысить качество до приемлемого уровня в 95-98%.

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

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

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

2. Разработаны эффективные численные методы: поиск в многомерном пространстве большой размерности; преобразования в адаптивную палитру; балансировка и оптимизация структуры дерева; сегментация. Проведено тестирование этих методов с применением современных компьютерных технологий и обоснована их адекватность.

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

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

5. Разработан программный комплекс «Дизайнер+», предназначенный для поиска изображений по визуальному подобию в дизайнерских коллекциях изображений. Комплекс может быть использован в прикладных целях (например, он внедрен в отдел дизайна и печатной подготовки ООО «ТетраПром»), а также в образовательных целях для соответствующих дисциплин.

6. Разработан программный комплекс РДЭП, предназначенный для исследования дефектов в эпитаксиальных пленках, автоматической проверки кремниевых пластин и определении типа брака. Ядром этого комплекса является поисковая подсистема на основе методов многомерного моделирования пространства визуальных характеристик дефектов. Исследования показали, что точность определения отдельно стоящих дефектов в случае известных параметров технологического процесса и типа пластины составляет 95-98%.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в журналах, рекомендуемых ВАК:

1. Гулаков, В. К. Использование многомерных деревьев для обработки многомерной информации / В. К. Гулаков, А. О. Трубаков, Е. О. Трубаков // Вестник БГТУ. - 2007. - № 3. - С. 46-54.

2. Гулаков, В. К. Сравнение производительности многомерных структур файлов-решеток и хеширования PLOP / В. К. Гулаков, А. О. Трубаков // Вестник БГТУ. - 2010. -№ 1.-С. 91-97.

3. Гулаков, В. К. Проблема большого объема векторов характеристик в задаче многомерного индексирования графической информации / В. К. Гулаков, А. О. Трубаков // Известия Волгоградского государственного технического университета. -Волгоград, 2010.-№11.-С. 133-137.

Монографии:

4. Гулаков, В. К. Многомерные структуры данных: монография / В. К. Гулаков, А. О. Трубаков. - 2010. - 386 с.

Прочие публикации:

5. Трубаков, А. О. Классификация многомерных структур данных / А. О. Трубаков; под ред. С. П. Сазонова, И. В. Говорова // материалы 58-й научной конференции профессорско-преподавательского состава. - Брянск, 2008. - С. 304-305.

6. Трубаков, А. О. Многомерная модель поиска изображений в хранилищах данных / А. О. Трубаков // Материалы межрегиональной научно-технической конференции «Информационные системы и технологии 2009». - Обнинск, 2009. - С. 166-167.

7. Гулаков, В. К. Использование многомерного анализа изображений для систем определения брака на производстве / В. К. Гулаков, А. О. Трубаков И Материалы международной научно-практической конференции «Состояние, проблемы и перспективы автоматизации технической подготовки производства на промышленных предприятиях». - Брянск: БГТУ, 2009. - С. 37-38.

8. Трубаков, А. О. Многомерный подход при решении проблемы контекстного поиска изображений на основе гистограммного метода / А. О. Трубаков // Сборник докладов международной научно-практической конференции «Наука и производство - 2009». - Брянск: БГТУ, 2009. - С. 181-183.

9. Гулаков, В. К. Контекстный поиск изображений, как основа современных систем машинного зрения / В. К. Гулаков, А. О. Трубаков // Вестник славянских вузов. - Брянск, 2010. - № 2. - С. 175-181.

10. Трубаков, А. О. Композитная функция подобия для систем поиска изображений на основе многомерной модели / А. О. Трубаков // Материалы международной научно-практической конференции «Достижение молодых ученых в развитии инновационных процессов в экономике, науке, образовании». - Брянск: БГТУ, 2010. - С. 154-155.

11. Трубаков, А. О. Семантический поиск изображений на основе многомерного пространства характеристик / А. О. Трубаков // Сборник трудов международной научно-технической конференции «Информационные технологии, энергетика и экономика». - Смоленск, 2011. - С. 116-119.

12. Свидетельство Роспатента об официальной регистрации программы для ЭВМ №2011611245. Программный комплекс распознавания дефектов в эпитакси-альных пленках кремниевых пластин (РДЭП) / Трубаков А.О.

Трубаков Андрей Олегович

МЕТОДЫ И АЛГОРИТМЫ МНОГОМЕРНОГО МОДЕЛИРОВАНИЯ ПРОСТРАНСТВА ХАРАКТЕРИСТИК ИЗОБРАЖЕНИЙ

Специальность 05.13.18 - Математическое моделирование, численные методы и

комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 10.05.11. Формат 60x841/16. Бумага офсетная. Офсетная печать. Печл. 1. Т. 100 экз. Заказ 130. Бесплатно.

Брянский государственный технический университет, 241055, г. Брянск, бульвар 50-летия Октября, 7. Лаборатория оперативной полиграфии БГТУ, ул. Институтская, 16.

ВВЕДЕНИЕ.

1. АНАЛИЗ МЕТОДОВ МНОГОМЕРНОГО МОДЕЛИРОВАНИЯ ХАРАКТЕРИСТИК ДЛЯ СИСТЕМ ПОИСКА ИЗОБРАЖЕНИЙ ПО

СОДЕРЖАНИЮ.

1.1. Анализ проблем и применений поиска изображений по содержанию

1.2. Исследование возможности применения многомерного подхода к современным схемам поиска.

1.3. Сравнение многомерного подхода с другими методами обработки и поиска изображений.

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

1.5. Анализ методов многомерного моделирования пространства характеристик.

1.5.1. Схемы преобразования многомерных векторов к одномерному виду.

1.5.2. Методы многомерного хеширования.

1.5.3. Методы иерархической декомпозиции многомерного пространства.

1.6. Постановка задачи исследования.

1.7. Выводы.

2. ФУНКЦИОНАЛЬНО-СТРУКТУРНОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССА ПОИСКА ИЗОБРАЖЕНИЙ НА ОСНОВЕ МНОГОМЕРНОГО ПОДХОДА.

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

2.2. Предобработка изображений.

2.3. Сегментация изображений.

2.4. Формирование многомерного вектора характеристик.

2.4.1. Критерии цвета.

2.4.2. Критерии текстуры.

2.4.3. Критерии контура.

2.4.4. Критерии положения и формы.

2.5. Многомерное индексирование векторов характеристик.

2.6. Связь векторов многомерного пространства характеристик и семантической сети.

2.7. Подсистема взаимодействия с человеком.

2.8. Выводы.

3. МЕТОДЫ МОДЕЛИРОВАНИЯ МНОГОМЕРНОГО ПРОСТРАНСТВА ХАРАКТЕРИСТИК.

3.1. Общие принципы построения многомерного дерева.

3.2. Ограничивающие фигуры узлов многомерного дерева.

3.3. Решение проблемы большой размерности пространства.

3.4. Распределение критериев по вершинам дерева.

3.5. Композитная функция расстояния в многомерном пространстве.

3.6. Решение проблемы нецелевых вершин.

3.7. Проблема «проклятия измерений».

3.8. Критериальная балансировка многомерного дерева.

3.9. Результирующие принципы многомерной структуры.

3.10. Выводы.

4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ МЕТОДОВ И АЛГОРИТМОВ.

4.1. Алгоритмы обработки многомерного индекса.

4.1.1. Алгоритмы поиска по многомерному индексу.

4.1.2. Алгоритм добавления объекта в многомерное дерево.

4.1.3. Алгоритм удаления объекта из многомерного дерева.

4.1.4. Алгоритм балансировки многомерного дерева по критериям.

4.1.5. Глобальная оптимизация многомерного индекса.

4.2. Программный комплекс поиска изображений по содержанию в дизайнерских коллекциях «Дизайнер+».

4.2.1. Назначение и особенности реализации.

4.2.2. Архитектура комплекса.

4.2.3. Выбор и ранжирование изображений.

4.2.4. Интерфейс web-подсистемы.

4.3. Программный комплекс распознавания дефектов в эпитаксиальных пленках кремниевых пластин (РДЭП).

4.3.1. Назначение системы и особенности реализации.

4.3.2. Архитектура программно-аппаратного комплекса.

4.3.3. Связь с семантической сетью и модуль реакций.

4.3.4. Пользовательский интерфейс.

4.3.5. Оценка результативности и эффективности применения ПК «РДЭП» на предприятии.

4.4. Выводы.

5. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ И ПРОВЕРКА АДЕКВАТНОСТИ РАЗРАБОТАННЫХ МЕТОДОВ МОДЕЛИРОВАНИЯ.

5.1. Описание тестовых коллекций.

5.2. Оценка релевантности поиска.

5.2.1. Эксперименты на основе реальных коллекций.

5.2.2. Эксперименты на основе синтезированной коллекции.

5.3. Оценка производительности индекса.

5.3.1. Высота внутреннего дерева.

5.3.2. Исследование алгоритмов балансировки.

5.4. Исследование методов и алгоритмов на основе программного комплекса РДЭП.

5.4.1. Формирование коллекций изображений дефектов.

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

5.4.3. Результаты экспериментов на синтезированных коллекциях с использованием семантической сети.

5.4.4. Результаты экспериментов на реальных фотографиях.

5.5. Тестирование отдельных алгоритмов и положений.

5.5.1. Алгоритм сегментации изображений.

5.5.2. Алгоритм преобразования к палитре на основе карты трансформации.

5.5.3. Меры различия цветовых гистограмм.

5.6. Выводы.

В современном мире информация играет первостепенную роль. Об этом говорили многие известные ученые, политики и философы — «кто владеет информацией, тот владеет миром» (Натан Ротшильд). Однако сама по себе информация в тех объемах, которые генерируются сегодня различными средствами, мала пригодна. Важно не только получать информацию, но и своевременно ее обрабатывать. Причем для обработки такого количества информации необходимы автоматические или полуавтоматические механизмы поиска и анализа интересующих данных. Самостоятельно человек уже не способен справиться с таким количеством информации, а без обработки, классификации и развитых механизмов поиска любые хранилища превращаются в неуправляемый и бесполезный инструмент [2, 80, 122].

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

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

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

Тенденция перехода от одномерной модели данных к многомерному представлению особенно хорошо заметна в области обработки изображений. Размеры современных коллекций таковы, что без применения специальных математических методов многомерного моделирования обработать все данные за приемлемое время невозможно. С одной стороны, область интеллектуальной обработки мультимедийной информации бурно развивается. Каждый год публикуются диссертации в этом направлении, появляется множество статей в научных журналах [31, 24, 22, 5, 26 и др.]. С другой стороны большинство существующих методов обработки и поиска графической информации либо абсолютно не приспособлены к большим объемам информации, либо требуют больших вычислительных ресурсов для выполнения подобных задач [19, 77, 85, 35]. К тому же многие алгоритмы и методы поиска не приспособлены для задач с динамическим наполнением, в которых исходный набор изображений и поисковые запросы подвержены постоянному изменению. Примером систем, плохо подходящих для подобных применений, являются практически все системы с обучением, т.к. они основаны на «запоминании» каких-то ключевых моментов определенного числа объектов и поиска в дальнейшем именно этого набора объектов [25, 59, 30, 109, 82].

Еще одной проблемой графических поисковых систем является так называемый «семантический разрыв» [26, 40, 64, 91]. Он заключается в том, что человек при анализе изображений оперирует высокоуровневыми понятиями, в то время как вычислительным устройствам доступны только значения отдельных пикселей. На уменьшение семантического разрыва направлено много работ и в нашей стране, и за рубежом. Однако общая методика для проектирования систем подобного класса пока отсутствует [129, 24, 36].

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

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

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

Для достижения поставленной цели рассматриваются следующие задачи:

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

2. Исследование существующих математических методов многомерного моделирования пространства характеристик (в том числе индексов пространств большой размерности).

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

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

5. Разработка принципов построения отношений между объектами многомерного пространства характеристик изображений и знаниями прикладной области, текстовыми описаниями, лексемами.

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

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

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

Научная новизна. Научная новизна результатов диссертационного исследования заключается в следующем:

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

• оригинальный метод сокращения размерности пространства в вершинах многомерного дерева за счет использования матриц сокращения, позволяющий повысить эффективность операций доступа;

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

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

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

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

5. Разработаны эффективные численные методы обработки изображений для систем на основе многомерного индекса: сегментация изображений, формирование адаптивной палитры, сравнения цветового исполнения с использованием компенсационного расстояния.

Положения, выносимые на защиту. На защиту выносятся следующие основные положения.

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

2. Принципы формирования матриц сокращения размерности пространства, композитной функции расстояния и построения двойного упакованного дерева.

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

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

5. Архитектура и функциональные характеристики разработанных проблемно-ориентированных программных комплексов «Дизайнер+» и «РДЭП».

Практическая ценность. Основными положениями, составляющими практическую ценность, можно считать:

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

2. Разработанный программный комплекс поиска изображений по содержанию «Дизайнер+».

3. Разработанный программный комплекс распознавания дефектов в эпитаксиальных пленках кремниевых пластин (РДЭП).

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

• Программный комплекс распознавания дефектов в эпитаксиальных пленках кремниевых пластин (РДЭП) зарегистрирован в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам [48]. Он также внедрен в научно-исследовательскую деятельность отдела развития ЗАО «Группа Кремний Эл».

• Разработанный программный комплекс поиска изображений по содержанию в дизайнерских коллекциях «Дизайнер+» внедрен в практическую эксплуатацию в отдел дизайна и печатной подготовки ООО «ТетраПром», а также используется в учебном процессе в рамках самостоятельной и исследовательской работы студентов и аспирантов соответствующих специальностей Брянского государственного технического университета.

Апробация результатов работы. Основные положения и наиболее важные научные и практические результаты диссертационной работы докладывались и обсуждались на 7 международных и российских конференциях, в том числе 58-й научной конференции профессорско-преподавательского состава БГТУ (г. Брянск, 2008); международной научно-практической конференции «Наука и производство — 2009» (г. Брянск, 2009); II научно-технической конференции «Информационные системы и технологии 2009» (г. Обнинск, 2009); международная научно-практическая конференция «Состояние, проблемы и перспективы автоматизации технической подготовки производства на промышленных предприятиях» (г. Брянск, 2009); научно-практической конференции «Современные проблемы информатики и прикладной математики» (г. Брянск, 2010); научно-практической конференции «Достижения молодых ученых в развитии инновационных процессов в экономике, науке, образовании» (г. Брянск, 2010); научно-технической конференция «Информационные технологии, энергетика и экономика» (г. Смоленск, 2011).

Публикации. По теме диссертации опубликовано 12 печатных работ, в том числе 1 монография и 3 статьи в научных журналах, рекомендованных ВАК.

Структура и объем работы. Цель и поставленные задачи определили следующую структуру работы.

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

Научные основы математических методов многомерного индексирования заложены в работах Д. Бентли, В. Гейда, А. Генрича, А. Гуттмана, О. Гюнтера, Г. Крэйгала, К. Лин, И. Маналополуса, Д. Нивергелта, Г. Самета и др. Анализ этих работ позволяет сделать вывод о возможности разработки эффективного численного метода на основе многомерного пространства характеристик со сложной функцией расстояния для систем поиска изображений по содержанию.

Анализ работ Н.С. Васильевой, А. Вежневец, Р. Вудса, А.Е. Лепского, В.В. Лукина, Б.А. Новикова, H.H. Пономаренко, C.B. Поршнева, A.C. Потапова, П.Ю. Пытьева, Дж. Стокмана, Л. Шапиро, Б. Яне, и др. позволил рассмотреть основные подходы к обработке и поиску изображений и место методов многомерного моделирования пространства характеристик в общем спектре технологий. Также в первой главе рассматриваются многомерные методы на предмет того, что нового они могут внести в существующие классические подходы к поиску.

Во второй главе согласно работам Т.А. Летова, А.П. Михайлова, A.B. Пантелеева, A.A. Самарского, Б.Я. Советова, П.В. Трусова, С.А. Яковлева и др. проведена декомпозиция сложной задачи поиска на ряд более простых подзадач и построена структурно функциональная модель. После этой декомпозиции каждая подсистема проанализирована отдельно, предложены методы и новые алгоритмы по её усовершенствованию и адаптации для систем, основанных на поиске в многомерном пространстве характеристик изображений.

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

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

Для улучшения качества поиска описывается предложенный метод использования сложной композитной функции и разработанные алгоритмы поиска по иерархической структуре с данными характеристиками. А для увеличения скорости поиска и уменьшения негативного эффекта «нецелевых вершин» предлагается использовать внутреннее дерево малой арности.

В четвертой главе формализованы основные алгоритмы, предложенные в данной работе. Также дано описание двух разработанных программных комплексов: программного комплекса поиска изображений по содержанию в дизайнерских коллекциях «Дизайнер+» и программного комплекса распознавания дефектов в эпитаксиальных пленках кремниевых пластин «РДЭП». Приводятся функциональные характеристики разработанных комплексов, описания их структур и принципов работы, а также описания входящих в их состав модулей.

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

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

5.6. Выводы

1. Проведено тестирование предложенных методов и алгоритмов с помощью разработанного программного комплекса «Дизайнер+». Рассчитана релевантность поиска по визуальному подобию, как для однородных коллекций, так и для коллекций без определенной тематики.

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

3. Проведено тестирование предложенного метода связи конечных объектов многомерного пространства характеристик и концептов семантической сети на основе разработанного программного комплекса РДЭП. Исследована возможность получения практической пользы от использования знаний семантической сети при выполнении поиска.

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

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

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

7. Исследована предлагаемая в работе мера сравнения цветовых гистограмм на основе компенсационного расстояния.

ЗАКЛЮЧЕНИЕ

На основании проведенного диссертационного исследования решена актуальная научно-техническая задача разработки математических методов и алгоритмов компьютерного моделирования многомерного пространства характеристик для систем поиска изображений по содержанию. На основе этих методов были созданы два проблемно-ориентированных комплекса: программный комплекс поиска изображений по содержанию «Дизайнер+» и программный комплекс распознавания дефектов в эпитаксиальных пленках кремниевых пластин (РДЭП), имеющих существенное значение в области повышения эффективности обработки фотографий на производстве. К основным выводам и результатам относятся:

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

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

3. Разработаны эффективные вычислительные методы: поиск в многомерном пространстве большой размерности; преобразования в адаптивную палитру; балансировка и оптимизация структуры дерева; сегментация. Проведено тестирование этих методов с применением современных компьютерных технологий и обоснование их адекватности.

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

5. Разработан программный комплекс «Дизайнер+», предназначенный для поиска изображений по визуальному подобию в дизайнерских коллекциях изображений. Комплекс может быть использован в прикладных целях (например, он внедрен в отдел дизайна и печатной подготовки ООО «ТетраПром»), а так же в образовательных целях для соответствующих дисциплин. Исследование релевантности поиска по методике РОМИП (мера Ргес~шоп(10)), проведенная с привлечением внешних асессоров, показал релевантность от 22% (АИО-ЗТЯОЫС), до 88% (ОЯ-ЖЕАК).

6. Разработан программный комплекс РДЭП, который может быть использован для исследования дефектов в эпитаксиальных пленках, автоматической проверки кремниевых пластин и определении типа брака. Основой этого комплекса является графическое поисковое ядро на основе методов моделирования многомерного пространства визуальных характеристик дефектов. Исследования показали, что точность определения отдельно стоящих дефектов в случае известных параметров технологического процесса и типа пластины составляет 95%.

Разработанный программный комплекс распознавания дефектов в эпитаксиальных пленках кремниевых пластин (РДЭП) зарегистрирован в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам [48].

1. Аверченков, В. И. Информационный поиск в сети интернет / В. И. Аверченков, В. В. Мирошников, С. М. Рощин. Брянск: БГТУ, 2001. - 204 с.

2. Аверченков, В. И. Мониторинг и системный анализ информации в сети Интернет: монография / В. И. Аверченков, С. М. Рощин. Брянск: БГТУ, 2006. -160 с.

3. Айфичер, Э. С., Джервис Б.У. Цифровая обработка сигналов: практический подход / Э. С. Айфичер, Б. У. Джервис; изд. 2-е. — С.П.: Вильяме,2008. 992 с.

4. Байгарова, Н. С. Некоторые подходы к организации содержательного поиска изображений и видеоинформации / Н. С. Байгарова и др. // Препринт ИПМ им. М.В.Келдыша РАН. № 78. - Москва, 2002.

5. Васильева, Н. С. Выбор шага квантования при построении цветовой гистограммы в задаче поиска изображений / Н. С. Васильева // Вестник СПбГУ. Сер. 10: Прикладная математика, информатика, процессы управления. — СПбГУ,2009. Вып. 2. - С. 155-164.

6. Введение в математическое моделирование: учеб. пособие / Под ред. П. В. Трусова. М: Логос, 2005. - 440 с.

7. Вежневец, А. Методы сегментации изображений: автоматическая сегментация / А. Вежневец, О. Баринова // Компьютерная графика и мультимедиа. 2006. - № 4.

8. ГОСТ Р 50779.10-2000. Статистические методы. Вероятность и основы статистики. Термины и определения.

9. Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. —

10. М.: Техносфера, 2005. — 1072 с.

11. Гулаков, В. К. Использование многомерных деревьев для обработки многомерной информации / В. К. Гулаков, А. О. Трубаков, Е. О. Трубаков // Вестник БГТУ. 2007. - № 3 (15). - С. 46-54.

12. Гулаков, В. К. Многомерные структуры данных: монография / В. К. Гулаков, А. О. Трубаков. — 2010. — 386 с.

13. Гулаков, В. К. Сравнение производительности многомерных структур файлов-решеток и хеширования PLOP / В. К. Гулаков, А. О. Трубаков // Вестник БГТУ.-2010.-№ 1 (25).-С. 91-97.

14. Гулаков, В. К. Контекстный поиск изображений, как основа современных систем машинного зрения / В. К. Гулаков, А. О. Трубаков // Вестник славянских вузов. Брянск, 2010. — № 2. — С. 175-181.

15. Гулаков, В. К. Информативная значимость текстурных характеристик на основе матрицы смежности уровней яркости пикселей изображения / В. К. Гулаков, А. О. Трубаков // Вестник БГТУ. — Брянск: БГТУ, 2011.

16. Гаврилова, Т.А. Базы знаний интеллектуальных систем / Т. А. Гаврилова, В. Ф. Хорошевский. — СПб: Питер, 2000. — 384 с.

17. Дорогов, А. Ю. Быстродействующий алгоритм семантической классификации ХРЕО-изображений / А. Ю. Дорогов, Р. Г. Курбанов, В. В. Разин // Нейроинформатика. 2006. - Т. 1, № 2. - С. 124-144.

18. Евстигнеев, В.А. Теория графов: алгоритмы обработки деревьев / В. А. Евстигнеев, В. Н. Касьянов. — Новосибирск: Наука, 1994. — 360 с.

19. Калачик, Р. А. Методы поиска графической информации в информационных системах / Р. А. Калачик // Диссертация на соискание ученой степени кандидата технических наук. — 2008. — 162 с.

20. Кнут, Д. Э. Искусство программирования. Сортировка и поиск / Д. Э. Кнут. М.: Вильяме, 2000. - 832 с.

21. Левашкина, А. О. Разработка методов поиска изображений на основе вычислительных моделей визуального внимания / А. О. Левашкина // Автореферат диссертации на соискание ученой степени кандидата технических наук. 2009. - 24 с.

22. Лепский, А. Е. Математические методы распознавания образов: курс лекций / А. Е. Лепский, А. Г. Броневич. — Таганрог: изд-во ТТИ ЮФУ, 2009. — 155 с.

23. Марков, И. Синтез цветовых и текстурных признаков при поиске изображений по содержанию / И. Марков, Н. Васильева // Труды Российского семинара по Оценке Методов Информационного Поиска РОМИП 2007-2008. —2008.-С. 135-144.

24. Мельниченко, А. Методы поиска изображений по визуальному подобию и детекции нечетких дубликатов изображений / А. Мельниченко, А. Гончаров // Труды Российского семинара по Оценке Методов Информационного Поиска. —2009.-С. 108-121.

25. Местецкий, Л. М. Математические методы распознавания образов: курс лекций / Л. М. Местецкий. ВМиК МГУ, 2004. - 85 с.

26. Методы компьютерной обработки изображений / под ред. В. А. Сойфера. -М.: Физматлит, 2001 784 с.

27. Мирошкин, А. В. Разработка и реализация математической модели графической поисковой системы / А. В. Мирошкин // Диссертация на соискание ученой степени кандидата технических наук. — 2005. — 122 с.

28. Мицель Л. Л. Непараметрический алгоритм текстурного анализа аэрокосмических снимков / Л. Л. Мицель, Н. В. Колодникова, К. Т. Протасов // Известия ТПУ. 2005. - № 1. - С. 65-70.

29. Мясников, Е. В. Навигация по коллекциям цифровых изображений на 5 основе методов автоматической классификации / Е. В. Мясников // Сборник работ участников конкурса "Интернет-Математика 2007". — 2007. — С. 144-152.

30. Мясников, Е. В. Анализ методов снижения размерности в задаче представления коллекций цифровых изображений / Е. В. Мясников // Компьютерная оптика. — 2008. — № 32. — С. 296-301.

31. Некрестьянов, И. РОМИП'2010: отчет организаторов / И. Некрестьянов, М. Некрестьянова // Труды Российского семинара по Оценке Методов Информационного Поиска. — 2010. — С. 5-27.

32. Неймарк, Ю. И. Многомерная геометрия и распознавание образов / Ю. И. Неймарк // Соросовский образовательный журнал. — 1996. — № 7. — С. 119123.

33. Пантелеев, A.B. Методы оптимизации в примерах и задачах / А. В. Пантелеев, Т. А. Летова. — М.: Высшая школа, 2005. — 544 с.

34. Пономаренко, Н. Н. Оптимизация весов многопараметровой меры подобия для поиска изображений / Н. Н. Пономаренко, С. К. Абрамов, В. В.

35. Лукин, А. С. Царан // Системы обработки информации. — 2007. 31-35 с.

36. Потапов, А. С. Распознавание образов и машинное восприятие / А. С. Потапов. С.П.: Политехника, 2007. — 552 с.

37. Поршнев С. В. Универсальная классификация алгоритмов сегментации изображений / С. В. Поршнев, А. О. Левашкина // Журнал научных публикаций аспирантов и докторантов. — 2008. — № 3 — С. 163-172.

38. Представление и использование знаний: пер. с япон. / Под ред. X. Уэно, М. Исидзука. М.: Мир., 1989. - 220 с.

39. Пытьев, Ю. П. Методы морфологического анализа изображений / Ю. П. Пытьев, А. И. Чуличков. М.: ФИЗМАТЛИТ, 2010. - 342 с.

40. Скворцов, А. В. Глобальные алгоритмы построения Я-деревьев // Геоинформатика: Теория и практика. — Томск: изд-во Том. ун-та, 1998. Вып. 1. — С. 67-83.

41. Самарский, А. А. Математическое моделирование: Идеи. Методы. Примеры / А. А. Самарский, А. П. Михайлов. М.: Физматлит, 2005. — 2-е изд. -320 с.

42. Советов, Б. Я. Моделирование систем / Б. Я. Советов, С. А. Яковлев. — М.: Высш. шк., 2007. — 5-е изд. — 343 с.

43. Свидетельство Роспатента об официальной регистрации программы для ЭВМ №2011611245. Программный комплекс распознавания дефектов в эпитаксиальных пленках кремниевых пластин (РДЭП) / Трубаков А.О.

44. Трубаков, А. О. Классификация многомерных структур данных / А. О. Трубаков; под ред. С. П. Сазонова, И. В. Говорова // материалы 58-й научной конференции профессорско-преподавательского состава. — Брянск, 2008. — С. 304305.

45. Трубаков, А. О. Многомерная модель поиска изображений в хранилищах данных / А. О. Трубаков // Материалы межрегиональной научно-технической конференции «Информационные системы и технологии 2009». — Обнинск, 2009. С. 166-167.

46. Тюхов, Б.П. Полуавтоматическое семантическое аннотирование мультимедиаресурсов / Б. П. Тюхов, С. В. Новиков // Программные продукты и системы. №2. - 2010.

47. Форсайт, Д. Компьютерное зрение. Современный подход / Д. Форсайт, Ж. Понс. М.: Вильяме, 2004. - 928 с.

48. Шапиро, Л. Компьютерное зрение / Л. Шапиро, Д. Стокман. — М.: Бином, 2006. 752 с.

49. Эсбенсен, К. Анализ многомерных данных: пер. с англ. / под ред. О. Родионовой. ИПХФ РАН, 2005. - 160 с.

50. Яне, Б. Цифровая обработка изображений / Б. Яне. — М.: Техносфера, 2007. 584 с.

51. Amit, Y. Shape quantization and recognition with randomized trees / Y. Amit, D. Geman // Neural Computation. 1996. - 9(7). - pp. 1545-1588.

52. Agarwal, P.K. k-Means Projective Clustering / P. K. Agarwal, N. H. Mustafa

53. Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. New York, USA, 2004. — pp. 155-165.

54. Bach, J. Virage image search engine: an open framework for image management / J. Bach, C. Fuller, A. Gupta et. all. // In Proceedings of the SPIE, Storage and Retrieval for Image and Video Databases IV. — San Jose, 1996. — PP. 7687.

55. Bellmann, R. Adaptive Control Processes: A Guided Tour / R. Bellmann // Princeton University Press. — 1961. — 255 p.

56. Bentley, J. L. Multidimensional binary search tree used for associative searching / J. L. Bentley // Communications of the ACM. 1975. - 18 (9) - pp. 509517.

57. Benitez, A. Using relevance feedback in content-based image metasearch / A. Benitez, M. Beigi, S. Chang // IEEE Internet Computing. 1998. - No. 4. - pp. 59-69.

58. Beyer, K. When is nearest neighbor meaningful / K. Beyer, J. Goldstein, R. Ramakrishnan, U. Shaft // Proc. Int. Conf. Database Theory. 1999. - pp. 217-235.

59. Bradsky, G. Learning OpenCV: Computer Vision with the OpenCV Library / G. Bradsky, A. Kaehler. O'Reilly Media, 2008. - 576 p.

60. Berchtold, S. The X-tree: An Index Structure for High-Dimensional / S. Berchtold, D. A. Keim, H.-P. Kriegel // Data. In Proc. of the 22nd International Conference on Very Large Data Bases (VLDB). Bombay, 1996. — pp. 28-39.

61. Beckmann, N. The R*-tree: An efficient and robust access method for points and rectangles / N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger // ACM SIGMOD International Conference on Management of Data. 1990. - pp. 322-331.

62. Brakatsoulas, S. Revisiting R-tree Construction Principles / S. Brakatsoulas, D. Pfoser, Y. Theodoridis // Proceedings of the 6th East European Conference on Advances in Databases and Information Systems. — 2002. — pp. 149-162.

63. Baeza-Yates, R. Modern Information Retrieval / R. Baeza-Yates, B. Ribeiro-Neto. — New York: Addison Wesley, 1999. — pp. 534.

64. Carreira-Perpinan, M. A. A review of dimension reduction techniques / M. A. Carreira-Perpinan // Technical Report CS—96—09, Dept. of Computer Science, University of Sheffield. 1997. - 69 P.

65. Carson, C. Storage and retrieval of feature data for a very large online image collection / C. Carson, V. E. Ogle // IEEE Computer Society Bulletin of the Technical Committee on Data Engineering. — 1996. — PP. 19—27.

66. Chalasani, S. Graph Based Image Segmentation / S. Chalasani // Department of Electrical & Computer Engineering Clemson University. — June 2004. — pp. 1-5.

67. Chung, K. Efficient algorithms for coding Hilbert curve of arbitrary-sized image and application to window query / K. Chung, Y. Huang, Y. Liu // Information Sciences. 2007. - vol. 177. - pp. 2130-2151.

68. Devroye, L. On the variance of the height of random binary search trees / L. Devroye, B. Reed // SIAM Journal on Computing. 1995. - pp. 1157-1162.

69. Donoho, D. L. High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality / D. L. Donoho // American Mathematical Society "Math Challenges of the 21st Century". 2008. - 33 p.

70. Durranta, R. J. When is 'nearest neighbour' meaningful: A converse theorem and implications / R. J. Durranta, A. Kaban // Complexity. — 2009. — No 25(4). — pp. 385-397.

71. Enser, P. Query Analysis in a Visual Information Retrieval Context / P. Enser // Journal of Document and Text Management. — 1993. — No 1. — pp. 25-52.

72. Flickner, M. Query by image and video content: the QBIC system / M. Flickner, H. Sawhney, W. Niblack et al. // IEEE Computer. 1995. - No 9 - pp. 2332.

73. Fodor, I. A survey of dimension reduction techniques / I. Fodor // Technical report UCRL-ID-148494. 2002. - 18 P.

74. Fonzo, V. Hidden Markov Models in Bioinformatics / V. Fonzo, F. Aluffi-Pentini, V. Parisi // Current Bioinformatics. — January 2007. — Vol. 2. — pp. 49-61.

75. Guttman, A. R-trees: A dynamic index structure for spatial searching / A. Guttman // ACM SIGMOD International Conference on Management of Data. 1984. -pp. 47-54.

76. Gaede, V. Multidimensional Access Methods / V. Gaede, O. Gunther // ACM Computing Surveys. 1998. - Vol. 30, № 2. - pp. 170-231.

77. Glotin, H. Fast image auto-annotation with visual vector approximation clusters / H. Glotin, S. Tollari // Proc. of Fourth International Workshop on Content

78. Based Multimedia Indexing. 2005. - 8 p.

79. Huffman, D. A. Approximation polyhedral with spheres for time-critical collision detection / D. A. Huffman // ACM transactions on Graphics. 1996. - 15 (3). -pp. 179-210.

80. Han, J. Rotation-invariant and scale-invariant Gabor features for texture image retrieval / J. Han, Ma. Kai-Kuang // Image and Vision Computing. — 2007. Vol.25, Issue 9-pp. 1474-1481.

81. Henrich, A. The LSD tree: Spatial access to.multidimensional point and nonpoint objects / A. Henrich, H.-W. Six, P. Widmayer // Fifteenth International Conference on Very Large Data Bases. 1989. - pp. 45-53.

82. Jagadish, S.H. Spatial search with polyhedral / S. H. Jagadish // In Proc. of the 6th IEEE International Conference on Very Large Databases (VLDB). — 1990. pp. 311-319.

83. Jain, A. K. Shape-Based Retrieval: A Case Study with Trademark Image Databases / A. K. Jain, A. Vailaya // Pattern Recognition. 1998. - Vol. 31, No. 9. -pp. 1369-1390.

84. Karam, O. Exploring the Semantic Gap in Content-Based Image Retrieval: with application to Lung CT / O. Karam, A. Hamad, M. Attia // GVIP 05 Conference.-2005.-pp. 422-427.

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

86. Kanungo, T. An efficient k-means clustering algorithm: Analysis andimplementation / T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, A. Y. Wu // IEEE Trans. Pattern Analysis and Machine Intelligence. — 2002. -pp. 881-892.

87. Katayama, N. The sr-tree: an index structure for highdimensional nearest neighbor queries / N. Katayama, S. Satoh // ACM SIGMOD international conference on Management of data. — 1997. — pp. 369-380.

88. Lee, D. J. Similarity measurement using polygon curve representation and Fourier descriptors for shape-based vertebral image retrieval / D. J. Lee, S. Antani, L. R. Long // Proc. of SPIE. 2003. - Vol. 5032. - pp. 1283-1291.

89. Lin, K. I. The tv-tree: an index structure for highdimensional data / K. I. Lin, H. V. Jagadish, C. Faloutsos // The VLDB Journal. 1994. - No 3(4). - pp. 517-542.

90. Liu, Y. A survey of content-based image retrieval with high-level semantics / Y. Liu, D. Zhang, G. Lu, W. Ma // Pattern Recognition. 2007. - Vol. 40. - pp. 262282.

91. Mackowiak, S. Practical Realization of the Content-Based Image Retrieval j System Using Sketch and Example / S. Mackowiak, T. Jaminski // Content-Based Multimedia Indexing. 2007. - No 7. - pp. 307-314.

92. Marfil, R. Pyramid segmentation algorithms revisited / R. Marfil, L. Molina-Tanco, A. Bandera, J. A. Rodraguez, F. Sandoval // Pattern Recognition. — August 2006. Vol. 39, Iss. 8. - pp. 1430-1451.

93. Marr, D. Early processing of visual information / D. Marr // Proceedings of the Royal Society of London. 1976.

94. Manolopoulos, Y. R-Trees: Theory and Applications / Y. Manolopoulos, A. Nanopoulos, A. N. Papadopoulos, Y. Theodoridis // Springer. — Verlag New York, Inc, 2005. 194 p.

95. Michael, O. Relevance feedback techniques in the MARS image retrieval systems / O. Michael, S. Mehrotra // Multimedia Systems. 2004. - PP. 535-547.

96. Niblack, C. W. QBIC project: querying images by content, using color, texture, and shape / C. W. Niblack, R. Barber, W. Equitz et al. // Proc. SPIE, Storage and Retrieval for Image and Video Databases. 1993. - Vol. 1908. - pp. 173-187.

97. Osadebey, M. E. Integrated content-based image retrieval using texture, shape and spatial information / M. E. Osadebey // Master Thesis Report in Media Signal Processing. — Sweden, 2006. — 173 p.

98. Orenstein, J. A class of data structures for associative searching / J. Orenstein, T. H. Merrett // In Proc. 3rd ACM SIGACT-SIGMOD Symp. on Principles of Database Systems. 1984. - pp. 181-190.

99. Piamsa-nga, P. In-picture search algorithm for content-based image retrieval / P. Piamsa-nga, N.A. Alexandridis, S. Srakaew et. all // Image Processing. — 1999. — Vol. 1-pp. 129-133.

100. Popescu, D. Texture Classification and Defect Detection by Statistical Features / D. Popescu, R. Dobrescu, M. Nicolae // NAUN International Journal Of Circuits, Systems And Signal Processing. 2007. - Vol. 1 - pp. 79-84.

101. Popescu, D. Carriage Road Pursuit Based On Statistical And Fractal Analysis Of The Texture / D. Popescu, R. Dobrescu // NAUN International Journal of Education and Information Technologies. — 2008. Vol. 2 — pp. 62-70.

102. Rabiner, L. R. A tutorial on hidden markov models and selected applications in speech recognition / L. R. Rabiner // Morgan Kaufmann Publishers Inc. — San Francisco, CA, USA, 1990. pp. 267-296.

103. Rui, Y. Image Retrieval: Current Techniques, Promising Directions, and Open Issues / Y. Rui, T. S. Huang, S. F. Chang // Journal of Visual Communication and Image Representation. 1999. - Vol. 10, Issue 1. — pp. 39-62.

104. Ross, K.A. Cost-based Unbalanced R-Trees / K. A. Ross, I. Sitzmann, P.J. Stuckey // Proceedings of the 13th International Conference on Scientific and Statistical Database Management. 2001. — pp. 203-212.

105. Rubner, Y. The Earth Mover's Distance as a Metric for Image Retrieval / Y. Rubner, C. Tomasi, L. J. Guibas // International Journal of Computer Vision. — 2000. -Vol. 40, Issue 2. pp. 99-121.

106. Rui, Y. Content-based image retrieval with relevance feedback in MARS / Y. Rui, T. S. Huang, S. Mehrotra // Image Processing. 1997. - Vol. 2. - PP. 815-818.

107. Samet, H. Foundations of Multidimensional and Metric Data Structures / H.

108. Samet 11 Imprint: Morgan Kaufmann. — 2006. — 1024 p.

109. Samet, H. The design and analysis of spatial data structures / H. Samet // Reading. MA: Addison-Wesley, 1989. - 510 p. '

110. Sebastian, T. B. Metric-based shape retrieval in large databases / T. B. Sebastian, B. B. Kimia // In Proc. of the 16th International Conference on Pattern Recognition. 2002. - pp. 291-296.

111. Smith, J. R. Querying by color regions using the VisualSEEk content-based visual query system / J. R. Smith, S.-F. Chang // In M. T. Maybury, editor, Intelligent Multimedia Information Retrieval. — AAAI Press, 1997.

112. Smith, J. R. Integrated Spatial and Feature Image Systems: Retrieval, Compression and Analysis / J. R. Smith // PhD thesis, Graduate School of Arts and Sciences, Columbia University, 1997.

113. Strieker, M. A. Similarity of color images / M. A. Strieker, M. Orengo // Proc. SPIE, Storage and Retrieval for Image and Video Databases III. — 1995. Vol. 2420.-pp. 381-392.

114. Sharma, G. The CIEDE2000 Color-Difference Formula: Implementation Notes, Supplementary Test Data, and Mathematical Observations / G. Sharma, W. Wu, E. Dalai // Color Research and Application. February 2004. - Vol. 30. No. 1. - 24 p.

115. Takei, R. A New Grey-Scale Template Image Matching Algorithm Using the Cross-Sectional Histogram Correlation Method / R. A. Takei // Dynax Corporation. -2003.-pp. 1-12.

116. Vassilieva, N. Content Based Image Retrieval / N. Vassilieva // Russian Summer School in Information Retrieval. 2008.

117. Veltkamp, R. C. Content-Based Image Retrieval Systems: A Survey / R. C. Veltkamp, M. Tanase // Technical Report UU-CS-2000-34. 2002. - 62 p.

118. Wang, B.-H. An Efficient Search Algorithm for High-Dimensional Indexing Using Cell Based MBR / B.-H. Wang, B.-W. Lee // Springer Berlin, Heidelberg. -2006. pp. 946-954.

119. Wang, L. Automatic image annotation and retrieval using weighted feature selection / L. Wang, L. Khan // Multimedia Tools Appl. 2006. - PP. 55-71.

120. White, D. A. Similarity indexing with the ss-tree / D. A. White, R. Jain // Twelfth International Conference on Data Engineering. — 1996. — pp. 516-523.

121. Международная конференция по компьютерной графике, машинному зрению, обработке изображений и видео (GraphiCon). Электронный ресурс. Режим доступа: http://www.graphicon.ru/.

122. Российская летняя школа по информационному поиску. Электронный ресурс. Режим доступа: http://romip.ru/russir2010/.

123. Российский семинар по Оценке Методов Информационного Поиска. Электронный ресурс. Режим доступа: http://romip.ru/.

124. Электронные библиотеки: Перспективные Методы и Технологии, Электронные коллекции. Электронный ресурс. Режим доступа: http://rcdl.ru/.

125. The Berkeley Segmentation Dataset and Benchmark. Электронный ресурс. Режим доступа:http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/.