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

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

МЕТОДЫ И АЛГОРИТМЫ МНОГОМЕРНОГО

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

ИЗОБРАЖЕНИЙ

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

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

АВТОРЕФЕРАТ

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

Брянск – 2011

Работа выполнена на кафедре «Информатика и программное обеспечение»

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

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

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

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

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

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

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

Ученый секретарь диссертационного совета Шкаберин В.А.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 страниц.

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

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

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

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

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

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

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

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

() = (1),, где () – изображение, после выполнения l-о этапа обработки;

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

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

где, – вес ребра графа между i-й и j-й вершинами; K1, K2, K3 – весовые коэффициенты влияния среднего цвета (Col(v)), цвета на границе областей (Col(b)) и размера областей (Sz); (… ) – формула разности двух цветов. Исследование качества предложенного алгоритма проводилось на основе специально предназначенных для подобных целей базы изображений университета Беркли.

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

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

где k – число кластеров; Cli – полученные кластеры ( = 1, ); i – центр масс векторов. После выполнения алгоритма кластеризации i-й цвет палитры определяется как средний цвет i-о кластера i. В качестве меры расстояния для алгоритма кластеризации предлагается использовать CIEDE2000 (мера международной комиссией по освещенности (МКО)), что позволяет создать палитру, адаптированную под человеческое восприятие. При этом для быстрого преобразования предлагается ввести понятие карты трансформации (массив коэффициентов прямого перевода из равномерной палитры в адаптивную).

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

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

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

Это позволило сократить размерность многомерного вектора, отбросив малозначащие и дублирующие характеристики.

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

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

где = {1, 2, … } – набор изображений, каждому из которых соответствует набор однородных сегментов 1, 2, … ; = {1, 2, … } – соответствующий сегментам набор векторов характеристик; ( ) – биективная функция соответствия векторов и графических образов (сегментов), такая, что:

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

где – сегмент шаблона, для которого производится поиск лучшего совпадения;

– наилучший вариант для шаблона.

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

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

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

где Vi – вектор многомерного пространства из множества V; Ci – концепт из множества C; wi – вес связи, отвечающий за точность описания данного графического объекта выбранным концептом; disti – вспомогательная мера согласования связи. Связь индекса и семантической сети представлена на рис. 1.

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

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

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

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

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

MBR вершин дерева задаются в виде набора MBR={E1,E2,…,Ed}, где Ei – это интервал с закрытыми концами [a,b], характеризующий размер объекта по соответствующей оси координат i.

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

Для решения этой проблемы предлагается перейти от общей функции расстояния к композитной функции, которая включает хорошо исследованные и проверенные части. Для подобного перехода общий вектор характеристик V = {K1,K2,…} разбивают на логические группы V = {G1,G2,…} = {{K1,K2,…},{Ki,Ki+1,…},…}. При этом необходимо выполнение следующих условий:

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

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

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

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

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

Эти матрицы используются для разбиения вектора V на группы {1, 2, … }.

Формируются матрицы сокращения следующим образом: пусть имеется логическая группа = {1, 2, … }, где l – номер ключа в исходном векторе характеристик V. Тогда k-я матрица сокращения Mk для этой группы Gk примет вид:

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

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

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

большая размерность пространства d влечет за собой большие пересечения MBR внутренних узлов (lim = 100%), что может привести к полной деградации индексной структуры;

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

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

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

В рамках работы было введено понятие нецелевой вершины: вершина Vнц называется нецелевой для запроса, если матрица сокращения этой вершины Mk выделяет такую группу характеристик = {1, 2, … }, компоненты которой неопределенны в векторе Vtmpl ( ).

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

Получаем, что чем больше арность, тем меньше скорость поиска.

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

Для решения противоречия требований к выбору арности m в работе предложено использовать двойное упакованное дерево (рис. 3), по аналогии с LSD-деревом.

малоарным (например, m=2). Это значительно уменьшает негативные последствия наличия нецелевых вершин Vнц и позволяет при Рис. 3. Двойная структура дерева Внутреннее дерево упаковывается и уплотняется с помощью группировки ряда узлов в один блок, названный в работе суперузлом. Этот суперузел соответствует одной вершине внешнего дерева, которая хранится во внешней памяти. Таким образом, внешнее дерево получается сильноветвящимся, что обеспечивает его эффективность в качестве структуры внешней памяти.

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

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

Для оценки эффективности узла предлагается в каждую вершину дерева добавить два дополнительных поля: число запросов и суммарный процент отсечения. В процессе выполнения поиска во всех затронутых узлах происходит увеличение первого поля на 1, а второго – на количество отброшенных потомков ( = +, где – суммарный процент отсечения после выполнения i запросов; Ecur – число отброшенных потомков вершины при выполнении текущей поисковой операции). Таким образом происходит накопление статистики эффективности разных узлов дерева. Результирующие условия балансировки примут вид:

1. Число запросов Nsearch в вершине V и в каждом из его потомков Child(V) должно быть больше порогового значения :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

пользователь Рис. 5. Архитектура программного комплекса «Дизайнер+»

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

Также web-компонент поддерживает функции авторизации и администрирования.

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

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

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

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

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

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

В разнородной коллекции результат оказался следующим: strongweak-or – 88%, strong-and – 22%. Из этих данных можно сделать вывод, что в среднем из первых изображений только одно, по мнению всех асессоров, попало в результат не обосновано (полностью не похоже на заданный шаблон). Также исследовалась работа программного комплекса на реальных коллекциях изображений, для которых результат оказался чуть лучше (strongweak-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. Формат 60х84 1/16.

Бумага офсетная. Офсетная печать. Печ.л. 1. Т.100 экз. Заказ 130. Бесплатно.

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