Содержание к диссертации
ВВЕДЕНИЕ 6
1. АНАЛИЗ МЕТОДОВ МНОГОМЕРНОГО МОДЕЛИРОВАНИЯ
ХАРАКТЕРИСТИК ДЛЯ СИСТЕМ ПОИСКА ИЗОБРАЖЕНИЙ ПО
СОДЕРЖАНИЮ 15
1.1. Анализ проблем и применений поиска изображений по содержанию „„ 16
1.2. Исследование возможности применения многомерного подхода к
современным схемам поиска 20
1.3. Сравнение многомерного подхода с другими методами обработки и
поиска изображений 23
! .4. Анализ существующих сисї-см поиска изображений по содержанию 28
1.5. Анализ методов многомерного моделирования пространства
характеристик 31
-
Схемы преобразонания многомерных векторов к одномерному виду 32
-
Методы многомерного хеширования 33
1.5.3. Методы иерархической декомпозиции многомерного
пространства 35
-
Постановка задачи исследования 36
-
Выводы 37
2. ФУНКЦИОНАЛЬНО-СТРУКТУРНОЕ МОДЕЛИРОВАНИЕ
ПРОЦЕССА ПОИСІСА ИЗОБРАЖЕНИЙ НА ОСНОВЕ МНОГОМЕРНОГО
ПОДХОДА 38
многомерного подхода 38
2.2. Предобработка изображений 42
-
Сегментация изображений 44
-
Формирование многомерного вектора характеристик 48
2.4.1. Критерии цвета 49
2,4.2- Критерии текстуры 58
2,43. Критерии контура 61
2.4.4. Критерии положения и формы 64
2.5. Многомерное индексирование векторов характеристик 66
2.6. Связь векторов многомерного пространства характеристик и
семантической сети 69
-
Подсистема взаимодействия с человеком 72
-
Выводы 74
3, МЕТОДЫ МОДЕЛИРОВАНИЯ МНОГОМЕРНОГО ПРОСТРАНСТВА
ХАРАКТЕРИСТИК 76
-
Общие принципы построения многомерного дерева 76
-
Ограничивающие фигуры узлов многомерного дерева 7Н
-
Решение проблемы большой размерности пространства 80
-
Распределение критерием по вершинам дерева 90
-
Композитная функция расстояния в многомерном пространстве 93
-
Решение проблемы нецелевых вершин 95
-
Проблема «проклятия измерений» 98
-
Критериальная балансировка многомерного дерева 104
-
Результирующие принципы многомерной структуры 111
3.10. Выводы 112
4- ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАКОТАННЫХ МЕТОДОВ И
АЛГОРИТМОВ 113
4.1. Алгоритмы обработки многомерного индекса 113
-
Алгоритмы поиска по многомерному индексу 113
-
Алгоритм добавления объекта в многомерное дерево 117
-
Алгоритм удаления объекта из многомерного дерева 123
-
Алгоритм балансировки многомерного дерева по критериям. 125
-
Глобальная оптимизация многомерного индекса 127
4.2. Программный комплекс поиска изображений по содержанию в
дизайнерских коллекциях «Дизайнер+» 130
-
Назначение и особенности реализации 130
-
Архитектура комплекса 132
-
Выбор и ранжирование изображений 136
4,2-4. Интерфейс web-подсистемы 137
4.3. Программный комплекс распознавания дефектов в эпитаксиальных
пленках кремниевых пластин (РДЭП) 139
-
Назначение системы и особенности реализации 139
-
Архитектура программ но-аппаратного комплекса 140
-
Связь с семантической сетью и модуль реакций 146
-
Пользовательский, интерфейс 147
4.3.5. Оценка результативности и эффективности применения ПК
«РДЭП» на предприятии 150
4.4. Выводы 152
5. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ И ПРОВЕРКА АДЕКВАТИОСТИ РАЗРАБОТАННЫХ МЕТОДОВ МОДЕЛИРОВАНИЯ, 153
-
Описание тестовых коллекций 153
-
Оценка релевантности поиска 155
-
Эксперименты на основе реальных коллекций 157
-
Эксперименты на основе синтезированной коллекции 159
5.3. Оценка производительности индекса 160
5,3. (.Высота внутреннего дерепа 161
5.3.2. Исследование алгоритмов балансировки 165
5.4. Исследование методов и алгоритмов на основе программного комплекса
РДЭП 168
5.4.1. Формирование коллекций изображений дефектов 169
-
Результаты экспериментов на синтезированных коллекциях с неизвестными параметрами кремниевой пластины 170
-
Результаты экспериментов иа синтезированных коллеіадиях с использованием семантической сети 172
5.4.4. Результаты экспериментов на реальных фотографиях 173
5.5. Тестирование отдельыых алгоритмов и положении 174
5.5.1. Алгоритм сегментации изображений 174
5.5.2. Алгоритм преобразования к палитре на основе карты
трансформации 177
5.5.3. Меры различия цветовых гистограмм 179
5.6. Выводы 182
За if л юч ен и е 183
Список литературы 185
При ложе н ия 198
Введение к работе
В современном мире информация играет первостепенную роль. Об этом говорили многие известные ученые, политики и философы — «кто владеет информацией, тот владеет миром» (Натан Ротшильд). Однако сама по cs5t информация в тех объемах, которые генерируются сегодня различными средствами, мала пригодна. Важно не только получать информацию» но и своевременно ее обрабатывать. Причем для обработки такого количества информации необходимы автоматические или полуавтоматические механизмы поиска и анализа интересующих данных. Самостоятельно человек уже не способен справиться с таким количеством информации, а без обработки, классификации и развитых механизмов поиска любые хранилища превращаются в неуправляемый и бесполезный инструмент [2, 80, 122],
Актуальность задачи, В последнее время появилось большое число задач, решение которых с использованием традиционных одномерных моделей данных является весьма трудоемким процессом. Это связано с тем, что объекты, рассматриваемые в таких областях, либо изначально являются многомерными, либо носят многокритериальный характер, что также соответствует многомерным задачам. Попытки преобразования характеристик таких объектов к одномерной модели, как правило, приводят к существенной потери информативности, а иногда — к неадекватному решению задачи. При этом моделирование в многомерной плоскости не только позволяет улучшить качество процесса обработки, но и повысить вычислительную эффективность математических методов, что может сыграть значительную роль при выборе алгоритма.
Актуальность работ в области многомерных моделей данных обуславливается большим числом прикладных задач, представление данных в которых преобразуется к многомерным векторам: медицина (многокритериальный анализ в диагностике), биология и генетика (базы геномов и анализ ДІЖ), экономика (многомерный анализ бизнес-процессов), распознавание речи (представление и поиск звуковых фрагментов), интеллектуальная обработка и поиск изображений (поиск подобньгх объектов с помощью векторов графических характеристик) и т.д. Перечисленные и многие другие задачи нуждаются в проработке и дальнейшем совершенствовании методов многомерного моделирования пространства характеристик.
Прикладные задачи накладывают на многомерные методы ряд дополнительных требований: наличие сложной, часто псевдометрической меры подобия (которая должна стать основой функции расстояния в многомерном пространстве характеристик); большая размерность пространства характеристик (это приводит к проблемам «проклятия измерений» и большого «перекрытия регионов» в структуре доступа); большой объем данных и необходимость поддержки работы с внешней памятью; адаптация математических методов под «неполные запросы», в которых параметры запроса определены частично или имеют разную важность с точки зрения процедур обработки; наличие механизма добавления к объектам многомерного пространства знаний прикладной области3 и т.д. Существующие на сегодняшний день структуры и математические методы не позволяют решить все перечисленные проблемы.
Тенденция перехода от одномерной модели данных к многомерному представлению особенно хорошо заметна в области обработки изображений. Размеры современных коллекций таковы, что без применения специальных математических методов многомерного моделирования обработать все данные за приемлемое время невозможно. С одной стороны, область интеллектуальной обработки мультимедийной информации бурно развивается. Каждый год публикуются диссертации в этом направлении, появляется множество статей в научных журналах [31, 24, 22, 5, 26 и др.]. С другой стороны большинство существующих методов обработки и поиска графической информации либо абсолютно не приспособлены к большим объемам информации, либо требуют больших вычислительных ресурсов для выполнения подобных задач [19, 77, 85, 35]. К тому же многие алгоритмы и методы поиска не приспособлены для задач с динамическим наполнением, в которых исходный набор изображений и поисковые запросы подвержены постоянному изменению. Примером систем, плохо подходящих для подобных применений, являются практически нес системы с обучением, т.к. они основаны па «запоминании» каких-то ключевых моментов определенного числа объектом и поиска в дальнейшем именно этого набора объектов 125, 59, 30, 109, 82],
Еще одной пробііемий графических поисковых систем является так называемый «семантический разрыв» [26, 40, 64, 91], Он заключается в том, что человек при анализе изображений оперирует высокоуровневыми понятиями, в то время как вычислительным устройствам доступны только значения отдельных пикселей. На уменьшение семантического разрыва направлено много работ и н нашей стране, и за рубежом. Однако общая методика для проектирования систем подобного класса пока отсутствует [129, 24, 36].
Таким образом, можно сделать вывод об актуальности работ, направленных на исследование и разработку математических .методов и алгоритмов многомерного моделирования пространства характеристик изображений, способных эффективно работать в пространствах большой размерности со сложной функцией расстояния.
Объект и предмет исследования. Объектом исследования данной диссертационной работы являются обработка и поиск изображений по содержанию. Предметом исследования является разработка и применение новых математических методов и алгоритмов многомерного моделирования пространства характеристик изображений, на основе которых можно создавать прикладные информационно-поисковые модели или системы обработки, распознавания или классификации изображений.
Цель и задачи диссертационной работы. Целмо работы является разработка ношх эффективных численных методов и алгоритмов многомерного моделирования пространства характеристик изображений. Данные методы позволят повысить скорость работы систем поиска изображений ло содержанию, расширить границы их применения, увеличить ограничения на объем индексированных коллекций, улучшить качество поиска за счет использования большего числа характеристик.
Для достижения поставленной цели рассматриваются следующие задачи:
Формирование требований к математическим методам многомерного моделирования пространства характеристик изображений. Анализ характеристик которые могут стать основой осей многомерного пространства, разработка нояьгх и адаптация существующих алгоритмов получения этих характеристик.
Исследование существующих математических методов многомерного моделирования пространства характеристик (в том числе индексов пространств большой размерности).
Разработка новых математических методов многомерного моделирования пространства, структур и алгоритмов индексирования и организации поиска изображений по содержанию.
Разработка принципов построения функции расстояния для многомерных моделей пространства характеристик изображений с разнородными компонентами.
Разработка принципов построения отношений между объектами многомерного пространства характеристик изображений и знаниями прикладной области, текстовыми описаниями, лексемами.
Разработка программных комплексов для обработки и поиска изображений, построенных на основе предложенных математических методов моделирования многомерного пространства, проверка адекватности и эффективности алгоритмов с помощью этих комплексов,
Методы исследования. При выполнении исследований и решении поставленных задач использовались основные научные положения многомерного моделирования, методов многомерного индексирования и сіруктур достуїіл, функционального анализа, численных методов кластеризации, теории графов, теории распознавания образов, численного дифференцирования и обработки изображений в частотной области, теории вероятности и статистической обработки.
При разработке программных комплексов использовались современные принципы организации комплексных систем с применением различных средств проектирования и языков программирования разного уровня, методы параллельного доступа к данным, основные положения объект! ю-ориентированного прогр аммирования.
Научная новизна. Научная новизна результатов диссертационного исследования заключается в следующем:
1. Разработан новый математический метод многомерного моделирования пространства характеристик изображений на основе иерархической декомпозиции, научную новизну которого составляет следующая совокупность оригинальных методов и алгоритмов: оригинальный метод сокращения размерности пространства її вершинах многомерною дерева за счет использования матриц сокращении, позволяющий [Юимсить эффективность операций доступа; - метод двойного упакованного многомерного дерева, лочноляющии уменьшить потери эффективности в нецелевых вершинах и сохранить положительные стороны сильноветвящегося дерева для внешней памяти.
Предложен метод формирования композитной функции расстояния в многомерном пространстве для векторов с разнородным набором компонент и алгоритмы использования этой функции в многомерной иерархической модели, позволяющие объединить достоинства хорошо известных методов подобия.
Разработан алгоритм критериальной балансировки дерева и целевая функция оптимизации, позволяющие улучшить структуру индекса и повысить процент отсечения альтернатив при поиске.
Предложен метод связи объектов многомерного пространства и концептов семантической сети с помощью нечетких отношений, позволяющий уменьшить «семантический разрыв».
Разработаны эффективные численные методы обработки изображений для систем на основе многомерного индекса: сегментация изображений, формирование адаптивной палитры, сравнения цветового исполнения с использованием компенсационного расстояния.
Положении, выносимые на защиту. На защиту выносятся следующие основные положения.
Математические методы и алгоритмы многомерного моделирования пространства характеристик большой размерности.
Принципы формирования матриц сокращения размерности пространства, композитной функции расстояния и построения двойного упакованного дерева.
Принципы использования многомерного подхода для построения систем поиска изображений по содержанию.
Метод сравнения цветового исполнения изображений с помощью предложенной палитры и компенсационного расстояния, которые можно использовать как функцию расстояния в многомерном пространстве характеристик изображений.
Архитектура и функциональные характеристики разработанных проблемно-ориентирован пых программных комплексов «Дизаинер+» и «РДЭП».
Практическая ценность. Основными положениями, составляющими практическую ценность, можно считать:
Предложенные математические методы и алгоритмы многомерного моделирования пространства характеристик изображений и принципы создания на их основе прикладных систем поиска изображений по содержанию.
Разработанный программігьтй комплекс поиска изображений по содержанию «Дизайнере».
Разработанный программный комплекс распознавания дефектов а эпитаксиальных пленках кремниевых пластин (РДЭП).
Практическое применение. Предложенные методы моделирования многомерного пространства характеристик легли в основу двух программных комплексов.
Программный комплекс распознавания дефектов в эпитаксиальныч пленках кремниевых пластин (РДЭП) зарегистрирован в Федеральной службе по интеллектуальной собственное]-и, патентам и товарным знакам |48], Он также внедрен в научно-исследовательскую деятельность отдела развития ЗАО «Группа Кремний Эл».
Разработанный программный комплекс поиска изображений по содержанию в дизайнерских коллекциях «Дизайн ер+» внедрен в практическую эксплуатацию в отдел дизайна и печатной подготовки ООО «ТетраТТром», а также используется в учебном процессе в рамках самостоятельной и исследовательской работы студентов и аспирантов соответствующих специальностей Брянского государственного технического университета,
Апробация результатов работы. Основные положения и наиболее важные научные и практические результаты диссертационной работы докладывались и обсуждались на 7 международных и российских конференциях, в том числе 58-й научной конференции профессорско-преподавательского состава БГТУ (г. Брянск, 2008); международной научно-практической конференции «Наука и производство — 2009» (г. Брянск, 2009); И научно-технической конференции «Информационные системы и технологии 2009» (г. Обнинск, 2009); международная научно-практическая конференция «Состояние, проблемы и перспективы автоматизации технической подготовки производства на промышленных предприятиях» (г. Брянск, 2009); научно -практической конференции «Современные проблемы информатики и прикладной математики» (г. Брянск, 2010); научно-практической конференции «Достижения молодых ученых в развитии инновационных процессов в экономике, науке, образовании» (г. Брянск, 2010); научно-технической конференция «Информационные технологии, энергетика и экономика» (г, Смоленск, 2011).
Публикации. По теме диссертации опубликовано 12 печатных работ, в том числе 1 монография и 3 статьи в научных журналах, рекомендованных В АТС,
Структура а объем работы. Цель и поставленные задачи определили следующую структуру работы,
В первой главе на основе анализа существующих систем поиска и обработки изображений, исследования их сильных и слабых мест, делается вывод о том» что одной из плохо проработанных сторон современных систем является поисковый индекс и его слабая ориентация на большие объемы информации. При этом работы 1-І. Катаяма, Е.В, Мясникова, Ю.И. Неймарка, И. Рубнера, М. Флиішера и др. позволяют сделать вывод о целесообразности применения методо и многомерного моделирования пространства характеристик для эффективного решения этой задачи.
Научные основы математических методов многомерного индексирования заложены в работах Д. Бентли, В. Гей да, А. Генри ча, А. Гуттмана, О, Гюнтера, Г. Крэйгала, К. Лин, И. Маналополуса, Д. Нивергелта, Г. Самета и др. Анализ этих работ позволяет сделать вывод о возможности разработки эффективного численного метода на основе многомерного пространства характеристик со сложной функцией расстояния для систем поиска изображений по содержанию,
Анализ работ Н.С. Васильевой, А. Вежневец^ Р. Вудса, А.Е. Ленского, В.В.Лукина, Б.А.Новикова, Н.Н Ліоном аренко, СВ. Поршнева, А.С. Потапова, П.Ю. Пытьсва, Дж, Стокмана, Л. Шапиро, Б. Яне, и др. позволил рассмотреть основные подходы к обработке и поиску изображений и место методов многомерного моделирования пространства характеристик в общем спектре технологий. Также в первой главе рассматриваются многомерілле методы на предмет того, что нового они могут внести в существующие классические подходы к поиску.
Во второй главе согласно работам ТА. Летова, А.П, Михайлова, А.В, Пантелеева, АА. Самарского, Б.Я, Советова, П.В. Трусова, С А, Яковлева и др. проведена декомпозиция сложной задачи поиска на ряд более простых подзадач и построена структурно функциональная модель. После этой декомпозиции каждая подсистема проанализирована отдельно, предложены методы и новые алгоритмы по её усовершенстгсонаїшю и адаптации для систем, основанных на поиске в многомерном пространстве характеристик изображений.
Также в этой главе рассмотрены основные критерии и характеристики, которые можно использовать в системах поиска но визуальному подобию, предложены собственные модификации методов оценки цветового подобия. Для стадии выделения однородных областей (сегментов) описывается новый алгоритм сегментации, предлагается метод связи многомерного индекса и семантической сети, который позволяет уменьшить «семантический разрыв» в процессе поиска.
Третьи глава полностью посвящена описанию предлагаемых методой и алгоритмов организации многомерного пространства характеристик. В пей описываются основные проблемы индексирования и предлагаемые пути их решения. Рассматривается возможность уменьшения размерности пространства с помощью матриц сокращения и использование структуры двойного дерева («упаковка» внутреннего дерева с малой арностью во внешнее сильноветвящееся}, позволяющее решить «противоречие арности».
Для улучшения качества поиска описывается предложенный метод использования сложной композитной функции и разработанные алгоритмы поиска по иерархической структуре с данными характеристиками, А для увеличения скорости поиска и уменьшения негативного эффекта «нецелевых вершин» предлагается использовать внутреннее дерево малой арности,
В четвертой главе формализованы основные алгоритмы, предложенные в данной работе. Также дано описание двух разработанных программных комплексов: программного комплекса поиска изображений по содержанию и дизайнерских коллекциях «Ди'щйиер+» и программного комплекса распознавания дефектов в эпитаксиальных пленках кремниевых пластин «РДЭП». Приводятся функциональные характеристики разработанных комплексов, описания их структур и принципов работы, а также описания входящих в их состав модулей,
Пятая глава посвящена описанию исследования эффективности применения разработанных программных комплексов для решения поставленных задач. В ней приведены результаты экспериментов но определению работоспособности разработанных методов и алгоритмов, адекватности выдаваемых программной реализацией данных, описана методика тестирования и проверки. Некоторые положения, выносимые на защиту, были проанализированы с использованием дополнительно разработанных средств, что также описано в пятой главе.
В заключении сделаны основные выводы по работе, сформулированы основные научные и практические результаты,
Похожие диссертации на Методы и алгоритмы многомерного моделирования пространства характеристик изображений
