Содержание к диссертации
Введение
ГЛАВА 1. Проблемы анализа изображений в задачах компьютерного зрения 9
1.1. Природа сложности компьютерного зрения 9
1.2. Специфика задач классификации изображений 14
1.3. Проблемы использования дескрипторов локальных особенностей 18
1.4. Специфика задач извлечения информации о геометрии 20
1.5. Выводы 25
ГЛАВА 2. Методы и алгоритмы автоматического построения обучающей выборки 26
2.1. Основные понятия и определения 26
2.2. Выделение понятий и формирование обучающей выборки 27
2.3. Выбор метода работы классификатора
2.3.1. Анализ методов, основанных на подходе Bag-of-Words 30
2.3.2. Анализ методов, основанных на подходе NBNN 31
2.3.3. Результаты выбора подхода к классификации
2.4. Извлечение визуальных особенностей и формирование словаря 33
2.5. Классификация на основе модели Bag-of-Words
2.5.1. Анализ классификации на основе наивного байесовского классификатора 36
2.5.2. Анализ классификации на основе метода опорных векторов 37
2.5.3. Выбор классификатора
2.6. Оценка качества автоматически сгенерированной обучающей выборки 38
2.7. Фильтрация выдачи поисковой системы 40
2.8. Выводы 44
ГЛАВА 3. Методы семантической коррекции в задачах классификации сложных изображений 46
3.1. Семантическое представление понятий 47
3.2. Связь между визуальной и семантической близостью классов 53
3.3. Схема работы метода 58
3.4. Верификация на основе семантических связей 60
3.5. Коррекция результатов классификации
3.5.1. Результат работы классификатора с учетом семантического графа 63
3.5.2. Объединение пересекающихся понятий в кластеры 65
3.5.3. Результаты 67
3.6. Выводы 70
ГЛАВА 4. Методы сопоставления изображений в задачах извлечения информации о геометрии 72
4.1. Схема работы метода 72
4.2. Сегментирование изображений 74
4.3. Попарное сравнение сегментов 76
4.4. Построение модели преобразования 81
4.5. Верификация соответствия сегментов 84
4.6. Выводы 89
Основные заключения и выводы 91
Список литературы 93
- Проблемы использования дескрипторов локальных особенностей
- Анализ методов, основанных на подходе Bag-of-Words
- Верификация на основе семантических связей
- Попарное сравнение сегментов
Введение к работе
Актуальность работы. Компьютерное зрение - важный предмет в рамках эмуляции некоторых процессов, происходящих в сознании живых существ. Большие измерения изображений и потенциально большое число связанных между собой изображений приводят к тому, что практически никакие методы, интуитивно кажущиеся простыми, не могут использоваться без глубокого пересмотра со стороны возможных оптимизаций, обусловленных большими временными и ресурсными затратами.
Различные области компьютерного зрения обладают отличающимися источниками сложности, для такой важной задачи, как классификация изображений, ими являются допустимая визуальная и структурная изменчивость предметов, относящихся к определенной категории. Можно выделить также характерные присущие ей проблемы: обучающая выборка традиционно строится на основе вручную созданных библиотек; увеличение количества классов приводит к снижению релевантности результатов; классы не связаны друг с другом и отсутствуют методы анализа семантической зависимости между ними. Попытка автоматизировать получение обучающей выборки была сделана в работах Fergus R. и Zisserman A., однако предлагаемый ими метод накладывал существенное ограничение на визуальное представление объектов в плане относительного расположения частей. Таким образом задача автоматического получения обучающей выборки остается открытой.
В течении последних лет было показано, что удобным представлением изображений для их анализа является совокупность векторов, описывающих окрестности точек интереса - дескрипторов локальных особенностей изображений. Важнейшие результаты в развитии концепции дескрипторов были получены в работах C.Harris, T.Lindeberg, C.Schmid, D.Lowe и G.Csurka. На сегодняшний день дескрипторы применяются во многих направлениях компьютерного зрения. Однако существующие методы их использования имеют также недостатки: не применяется информации о контексте из-за сути дескрипторов как хеш-сумм окрестностей и не используется цветовая информация изображений, что приводит к снижению дискриминационных свойств. В силу компромиссной специфики принципов работы дескрипторов и необходимости имитировать процессы, протекающие в сознании живых существ, в настоящее время не существует разработанных методов окончательного решения задач анализа изображений с применением дескрипторов.
Таким образом актуальной является разработка эффективных методов анализа изображений на основе дескрипторов с использованием более высокоуровневой информации о контексте. В данной диссертационной работе внимание концентрируется на двух аспектах использования дескрипторов: задаче классификации изображений и задаче извлечения геометрии из наборов изображений. В задаче классификации изображений внимание обращается на проблемы, связанные с ручным механизмом формирования обучающей выборки и на проблемы, связанные с отсутствием отношений классов между собой. В задаче извлечения информации о геометрии объектов внимание обращается на проблему избыточной фильтрации соответствий дескрипторов при поиске соотношений изображений между собой.
Цель работы и задачи исследования. Настоящее диссертационное исследование посвящено разработке методов улучшения работы дескрипторов в задачах поиска структуры из движений и в задачах классификации сложных изображений путем использования информации о контексте.
Для достижения поставленной цели в работе решаются следующие задачи:
-
Исследование возможности использования автоматически полученной обучающей выборки для задач классификации и сравнительный анализ различных подходов к классификации в этом случае.
-
Разработка метода фильтрации поисковой выдачи от нерепрезентативных экземпляров изображений.
-
Исследование возможности использования семантического графа как источника информации о контексте в задачах классификации изображений;
-
Разработка методов верификации и коррекции результатов классификации на основе семантического графа.
-
Сравнительный анализ и разработка эффективных алгоритмов поиска соответствий между дескрипторами.
-
Разработка модели представления изображений в виде сегментов для задач структуры из движения.
Методы исследования. В данной работе при проведении исследований применялись методы компьютерной графики, методы теории обработки сигналов и теории графов, методы математической статистики и теории вероятности.
Научная новизна работы. К основным новым результатам, полученным в диссертации, можно отнести следующие:
-
Предложена методика автоматического построения обучающей выборки на основе информации из сети Интернет, включающая выбор метода классификации изображений в целом и разработку алгоритма фильтрации несвязных изображений.
-
При анализе сложных изображений на основе предложенной методики формирования и обработки обучающей выборки впервые был предложен алгоритм семантической верификации и коррекции результатов визуальной классификации на основе лингвистической информации.
-
Разработана модификация алгоритма сопоставления изображений на основе массивов дескрипторов в задачах извлечения информации о геометрии, позволяющая существенно увеличить количество извлекаемой полезной информации в сравнении с общепринятым методом D.Lowe. Практическая ценность работы. Полученные в диссертационной работе
алгоритмы и модели предназначены для практического применения в программно-аппаратных комплексах анализа изображений, таких как системы интеллектуальной каталогизации, системы принятия решений на основе содержимого изображений, системы реконструкции моделей объектов по наборам изображений.
Реализация и внедрение результатов работы. На основе полученных в работе результатов было разработано программное обеспечение для анализа содержимого микрофотографий, данное программное обеспечение было использовано при выполнении задания №13.773.2014/К Министерства образования РФ на кафедре Химической техники и инженерной экологии в Алтайском государственном техническом университете. Также результаты работы внедрены в учебный процесс на кафедре Прикладной математики АлтГТУ в программу курса «Интеллектуальные технологии обработки изображений». В ООО «Алавар Студиос» было внедрено написанное на основе предложенного метода поиска соответствий программное обеспечение для автоматизированного моделирования геометрии сцен из набора фотографий.
Достоверность полученных результатов подтверждается проведенными экспериментами и моделированием, а также согласованностью с данными, имеющимися в отечественной и зарубежной литературе.
Апробация работы. Материалы работы докладывались на следующих научных конференциях: XIII международной научно-практической конференции «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности и экономике» (г. Санкт-Петербург, 2012); Всероссийской конференции с международным участием «Знания- Онтологии-Теории» (г. Новосибирск, 2013); XV международной научнотехнической конференция “Измерение, Контроль, Информатизация” (г. Барнаул, 2014); XI Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых “Наука и Молодежь” (г. Барнаул, 2014); V международной научно-практической конференции “Новые задачи технических наук и пути их решения” (г. Уфа, 2015); II международной научно-практической конференции “Актуальные проблемы естественных и математических наук в России и за рубежом” (г. Новосибирск, 2015); XI международной научнопрактической конференции «Перспективные научные исследования - 2015» (г. София, 2015); на семинаре “Информационные Технологии и Системы” в Институте автоматики и электрометрии СО РАН (г. Новосибирск, 2015).
Публикации. По теме диссертационной работы опубликовано 12 печатных работ, включая 3 статьи в журналах из списка ВАК, получено 2 свидетельства о регистрации программы для ЭВМ: № 2014616393 и № 2015615114.
Основные положения диссертации, выносимые на защиту.
-
Модели и алгоритмы автоматического извлечения обучающей выборки в задачах классификации изображений; алгоритмы фильтрации и обучения на основе изображений, полученных поисковыми запросами в сети Интернет;
-
Алгоритмы анализа, фильтрации и коррекции на основе использования семантического графа понятий в задачах классификации сложных изображений;
-
Алгоритмы эффективного анализа изображений на основе массивов дескрипторов для сопоставления изображений в задачах извлечения геометрических данных.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех разделов, заключения, списка использованных источников, содержащего 93 наименования, и 3 приложений. Общий объем работы составляет 109 страниц, в том числе 36 рисунков, 21 таблица.
Проблемы использования дескрипторов локальных особенностей
Человек способен с легкостью воспринимать окружающий его реальный мир с помощью визуальной информации получаемой от органов зрения. Наш мозг способен достраивать плоское изображение, получаемое глазами, до трехмерного изображения в сознании, например, человек без труда понимает, что ваза имеет форму тела вращения, наблюдая ее столько с одной точки. Глядя на фотографию, сознание практически мгновенно выдает информацию о людях, изображенных на ней, включая весь спектр сопутствующих данных, например, связанные с людьми события. Мы способны достраивать изображение на основе лишь частичных, либо даже схематически изображенных отрывков, при этом используя как весь физиологический функционал, так и знания, и опыт накопленные ранее при жизни.
Компьютерное зрение – раздел информационных технологий, исследующий возможности машин извлекать информацию из изображений, полученных с различных сенсоров и таким образом в некоторой степени эмулировать человеческое визуальное восприятие. Данной науке уже несколько десятков лет, и она продемонстрировала значительные результаты в задачах одних классов, в то время как во многих других прогресс относительно низок. Основной проблематикой данной области можно назвать то, что она пытается эмулировать поведение, в общем, малоизученных и слабо понятных процессов происходящих при восприятии человеком визуальной информации. В то время как человек может использовать весь багаж накопленного опыта и знаний для принятия решений относительно интерпретаций визуального изображения (и, следовательно, любое такое восприятие является субъективным), подавляющее число алгоритмов в компьютерном зрении являются детерминированными и результат их работы зависит только от входных данных. По этой причине компьютерное зрение на сегодняшний день невозможно рассматривать как комплексную теорию, скорее это множество подходов, методов и алгоритмов, направленных на решение различных теоретических и прикладных задач, слабо связанных между собой, либо же иногда использующих прямо противоположные подходы для достижения результата в различных задачах.
Сложность, присущая компьютерному зрению, отчасти проистекает из расположения это области на стыке многих наук и сфер, среди которых можно перечислить: - Физика, в первую очередь оптика, а также все другие связанные с распространением света разделы; - Нейробиология, как наука занимающаяся изучением принципов работы человеческого восприятия; - Искусственный интеллект, например, для использования элементов поиска по шаблону и методов обучения; - Обработка сигналов, многие методы компьютерного зрения требуют первоначальной обработки и трансформации входных данных; - Машинное обучение и прикладная математика. В компьютерном зрении решается широкий спектр вычислительных задач, которые требуют эффективного математического аппарата для работы с большими объемами данных. Так же следует отдельно отметить особенности сферы, вытекающие из объемов обрабатываемой информации. Большие размерности изображений, помноженные на потенциально немалое число связанных между собой изображений и на необходимость работать в разных масштабах, приводят к тому, что практически никакие методы, интуитивно кажущиеся простыми, не могут использоваться без глубокого пересмотра со стороны возможных оптимизаций. Практически никакие методы, работающие «в лоб», не представляются возможными к использованию из-за неприемлемых временных и ресурсных затрат. Из этого протекает та особенность, что многие методы компьютерного зрения были получены «от противного» - т.е. максимальная возможная результативность исходя из текущего развития доступной вычислительной техники (пусть и со множественными допущениями и погрешностями), а не исходя из прямого моделирования, к примеру, физических процессов. Среди крупных областей, рассматриваемых компьютерным зрением, можно условно выделить следующие: - задачи распознавания; - задачи реконструкции сцены; - задачи анализа видео. Данное деление довольно свободное, так как в областях иногда используются пересекающиеся наборы подходов и методов, так же пересекающийся фундаментальный инструментарий, связанный с обработкой изображений. Рассмотрим содержание данных областей более подробно. Задачи распознавания. Компьютерное зрение выделяет определенные разрезы среди задач распознавания, которые отличаются используемым аппаратом: - идентификация объекта – поиск экземпляров объекта на представленном изображении, возможно в искаженном виде, однако с сохранением визуальных особенностей объекта. Эти задачи могут решаться различными способами, в зависимости от конкретной области применения; - задачи обнаружения – поиск каких-либо областей по заданным критериям, без четких визуальных особенностей. Областями применения можно назвать диагностику в медицине и системы видеонаблюдения, системы поиска людей и лиц на фотографиях; - задачи сегментирования изображений – выделение связанных областей, возможно отделение фона от находящегося перед ним предмета; - задачи классификации изображений – присвоение входящим изображениям меток из набора классов, исходя из содержания изображений; - задачи классификации через локализацию – одновременный поиск расположения экземпляров различных классов на изображении с последующим присвоением меток исходя из найденных экземпляров.
Задачи реконструкции сцены. В широком понимании под этими задачами можно понимать извлекание информации из связанных между собой (возможно, неизвестным образом) изображений. Среди разделов этого класса задач можно выделить следующие: - “сшивание” изображений – простейший случай данного класса задач, при котором не требуется вычислять геометрию сцены, а только взаимное расположение пересекающихся изображение и соответствующее преобразование, переводящее координаты одного изображение в координаты другого; - структура из движения – простейший случай извлечения информации о геометрии объекта из набора его изображений из разных точек. Включает в себя задачи калибровки камеры, задачи построения расширенной реальности, задачи извлечения простейшей геометрии основанной на линиях и плоскостях; - реконструкция 3D модели из набора изображений – широкий спектр задач реконструкции сцены, который предполагает извлечение информации об объемной геометрии предметов из набора изображений этих предметов (сцены). Может значительно отличаться в подходах исходя из масштаба задачи – от моделирования небольшого предмета с помощью обычной камеры, до моделирования больших пространств (large scale reconstruction) используя большое количество несвязанных между собой изображений полученных с разных камер.
Анализ методов, основанных на подходе Bag-of-Words
Для формирования обучающей выборки был использован, в данном конкретном случае, Google Search. Поисковый сервис выдает набор изображений по данному запросу. Для каждого выбранного понятия опционально задается слово для запроса в поисковую систему, это необходимо из-за того, что определенные слова могут иметь совершенно разную выдачу при различных формах этого слова в запросе. Традиционное количество обучающих изображений в задачах классификации может варьироваться в диапазоне от 10 до 30, таким образом, текущий лимит Google Custom Search на 100 первых результатов поискового запроса [30] не привносит ограничений на возможности обучения, что подтверждается результатами полученных матрицами неточностей (confusion matrix) ниже. Стоит также отметить, что при таком формировании обучающей выборки, отсутствует информация о расположении объектов внутри изображений (ground truth), и эта выборке не может быть использована для решения задач categorization by localization.
Стоит отметить, что современные поисковые системы поддерживают указание в поисковом запросе типов изображений, это могут быть, к примеру, фотографии и клипарт («синтетические» изображения, либо фотографии в значительной степени измененные графическим редактором). Для получения обучающей выборки используются запросы с указанием поиска фотографий, однако опыт данной работы показал, что клипарт изображения так же могут анализироваться классификаторами, предлагаемыми в данной работе, с приемлемыми результатами. При этом, разумеется, необходимо выбирать один из типов изображений, так как их характеристики значительно отличаются и их совместное использование в обучающей выборке может привести к плохо обученному классификатору.
Были проанализированы устоявшиеся на сегодняшний день подходы к использованию локальных визуальных особенностей для классификации изображений, условно их можно разбить на некоторые группы: Bag Of Words (BoW) [15], Naive Bayesian Nearest Neighbor (NNBN) [9], Part-Based [21,23] и основанные на сегментировании [25]. Part-based подход, учитывающий взаимное расположение визуальных особенностей, и подходы, основанные на сегментировании, являются специализированными для определенных задач и поэтому не могут быть использованы в общей задаче классификации.
Для работы с обучающей выборкой, полученной автоматически, классификатор должен обладать, в первую очередь, устойчивостью результата работы при незначительных изменениях обучающей выборки - при появлении в выборке «плохих» экземпляров общий результат работы не должен кардинально ухудшаться. Рассмотрим подходы BoW и NNBN с точки зрения поставленной задачи.
В данном методе все визуальные особенности (представляющие из себя многомерные векторы - 128-мерные в случае SIFT) из всей обучающей выборки объединяются в общий массив, который затем разбивается на заданное количество V визуальных слов [67]. Значения визуальных слов в пространстве дескрипторов примем за W. Пусть визуальные слова w представляют собой V-мерный вектор с один компонентом равным единице и остальными равными нулю:
Полученные наборы визуальных слов используются для принятия решения о принадлежности анализируемого изображения к определенному классу. Для принятия решения применяются обобщающие либо дискриминирующие методы. В качестве примера обобщающего метода можно привести Nave Bayesian классификатор, а в качестве дискриминирующего - классификатор на основе метода опорных векторов. При использовании дискриминирующего классификатора следующем этапе вычисляется представление изображения в виде гистограммы распределения визуальных слов:
Эксперименты по сравнению работы NB и SVM на примере автоматически полученной обучающей выборки приведено параграфе 2.6. Среди плюсов этой модели с точки зрения предлагаемого метода можно отметить устойчивость ее результатов при незначительных изменениях обучающей выборки. При этом усредняющая суть данного метода хорошо вписывается в подход с автоматически полученной обучающей выборкой. Среди недостатков стоит отметить принципиальную проблемность тех ситуаций, когда в анализируемом изображении представлено более одного экземпляра объекта из обучающей выборки либо этот объект представлен частично. Так же среди минусов можно выделить высокую вычислительную сложность на этапе обучения, особенно процесс кластеризации исходного набора визуальных особенностей, и наличие этапа квантования, которое снижает дискриминационную возможность дескрипторов.
Верификация на основе семантических связей
В процессе классификации, при наличии высоких результатов у классов, соответствующих семантически близким понятиям, можно говорить о возникающем при этом контексте. Контекст позволяет усиливать результат этих понятий, исходя из той предпосылки, что близкие понятия при одновременном нахождении имеют большую важность нежели отдельные независимые понятия. При анализе сложных с точки зрения наполнения изображений могут возникать ситуации когда классификаторы разных классов выдают примерно одинаковые значения. При этом соизмеримые значения могут выдавать как классификаторы классов, реально присутствующих на изображении, так и классификаторы, ложно выдающие высокий результат. При наличии известных семантических связях между классами подобные ситуации можно отдельно обрабатывать, повышая общую релевантность выдачи системы анализа. Основной тезис, на котором основывается дальнейшая логика работы, заключается в том, что при наличии двух и более семантически близких классов с высокой выдачей их классификаторов, эти классы можно объединить в кластер с более высоким значением, нежели у классов по отдельности. 3.5.1. Результат работы классификатора с учетом семантического графа
Помимо непосредственной семантической близости между понятиями, для выделения контекста важна их окрестность и степень ее пересечения, так как она учитывает структуру отношений между понятиями. На рис. 3.7 приводится пример семантически близких понятий, которые имеют пересекающуюся окрестность. Окрестность при этом формируется исходя из семантической близости к понятиям.
Перейдем к определению степени близости между классами при анализе конкретного изображения. Пусть rt - результат независимой классификации. Введем функцию F(Q) - степень подобия класса Q соответствующему понятию st в семантическом графе, зависящую от rt. Удобным механизмом для определения степени близости классов с учетом их окрестности является обход семантического графа в ширину от каждого конкретного класса. Обход в ширину учитывает веса ребер (в данной реализации наилучший результат показали значения 0,3 для отношений определения и 0,75 для ассоциативных связей), а также расстояние от класса, для чего применяется коэффициент демпфирования при прохождении очередного понятия. При прохождении каждого очередного понятия рассчитывается его функция сходства с оригинальным понятием-классом и, когда она становится меньше порогового значения, обход в этом направлении завершается. Для обхода используется алгоритм Дейкстры [19]. Значение близости S очередного смежного понятия Ъ к предыдущему а вычисляется по формуле: где Е - функция сходства при переходе от одного понятия к другому - получается из словаря понятий, D - константный коэффициент демпфирования при каждом очередном удалении от изначального понятия, Т - пороговое значение близости к изначальному понятию.
Значение степени подобия понятия х является фиксированным относительно класса значением: при первоначальном обходе оно принимается за единицу, при обходах с учетом результата работы визуального классификатора, оно может быть соответствующим образом скорректировано. Таким образом, визуальное соответствие транслируется в обход семантического графа. Пусть
Так как в семантическом графе понятия располагаются с неравномерной плотностью, требуется система нормирования для каждого отдельного класса, иначе сравнение величин не будет иметь смысла. Базой нормализации принята ширина класса, полученная при обходе со значением степени подобия понятия равным единице, то есть W(C, 1).
Для получения сравнимых величин в терминах семантического графа, на основе ширин классов и учитывая полученный ранее результат независимой визуальной классификации г, используется следующее преобразование: где гс- результат работы классификатора класса С, rmn - минимальный результат работы всех классификаторов, rmax - максимальный результат работы всех классификаторов. Таким образом, наиболее близкий, исходя из результатов независимой визуальной классификации, класс получит степень подобия равную 1,0, а наименее близкий получит степень подобия равную 0,5.
На сложных изображениях могут присутствовать экземпляры различных семантически связанных классов. При этом классификаторы работают независимо, и каждый из них определяет наличие объектов своего класса на изображении. Пусть вероятность появления объектов соответствующих классов Р(С1) и Р(С2) пропорциональна соответствующим результатам независимой классификации гс и гС2. Тогда при наличии пересекающейся окрестности, т.е. при (С1 П С2) 0, вероятность появления на изображении совмещенного объекта из двух классов должна быть выше вероятностей в отдельности: Р(С1 U С2) тах(Р(С1), Р(С2)). (3.15) В процессе объединения понятий производится сравнение классов «каждый с каждым» и вычисляется степень пересечения на основе семантических связей и изначальной выдачи классификаторов для этих классов. При этом идет переход от отдельных классов к кластерам классов, изначально состоящих из одних классов, потом, возможно, укрупняющихся за счет объединения
Попарное сравнение сегментов
Существуют в целом два подхода к решению задачи поиска преобразования одного набора векторов в другой при потенциальном наличии неправильных соответствий – повторяющийся выбор базовых векторов случайным образом и голосование векторов за положение объекта.
Схема голосования использует подход Hough Transform, при котором составляется многомерное (в простейшем случае четырехмерное – две координаты позиции центра, ориентация и масштаб) пространство «корзин для голосования» и каждый дескриптор голосует за возможные смежные квантованные положения объекта (pose estimation) во втором изображении, исходя из его отношения к центру объекта (смещение, отношение масштаба и разница ориентации) в первом изображении. Такой подход хорошо работает при задаче локализации объекта (object localization), однако он имеет существенные минусы. Выбор шагов «корзин» и соответствующего квантования в значительной мере влияет на то, попадет ли очередной дескриптор в модель и какое количество неверных соответствий останется после голосования. Широкие шаги «корзин» в данной задаче приводят к тому, что несогласованные сегменты могут получить больше количество согласований, с другой стороны, уменьшение шага приводит к избыточной фильтрации верных соответствий в согласованных сегментах. Таким образом, в данной работе предлагается использовать метод базовых векторов с последующей верификацией, как более гибкий и точнее соответствующий задаче - увеличению финального количества соответствий между изображениями.
В противоположность методу Hough Transform (который рассматривает множество дескрипторов как целостный объект), при использовании базовых элементов на этом этапе производится попытка поиска перспективного преобразования координат дескрипторов (т.е. не объект в целом, а отдельные координаты), имеющих соответствие для каждой пары сегментов первого и второго изображения. Такое преобразование должно перевести координаты дескрипторов сегмента первого изображения в координаты соответствующих дескрипторов сегмента второго изображения. При этом для вычисления гомографии на этом этапе учитываются только координаты дескрипторов, но не учитываются их ориентации и размеры. Эти данные можно использовать для формирования дополнительной координаты на каждый дескриптор, и фактически преобразования их из одной координаты в вектор, и далее вычислять преобразование, переводящее один набор векторов в другой. Однако, подобная дополнительная информация ведет к дополнительным требованиям к преобразованию, и в конечном итоге к чрезмерной фильтрации.
Для вычисления гомографии используется статистическая модель RANSAC [26], суть которой заключается в том, чтобы N раз выбрать случайные базовые элементы, по которым будет строиться максимально приближенная модель преобразования. Минимально необходимое количество базовых элементов для поиска гомографии - 4 точки, но проведенные эксперименты показали гораздо более стабильные результаты при использовании 5 точек. Преобразование находится путем решения системы уравнений, приведенных к однородному виду, с использованием сингулярного разложения (Singular value decomposition - SVD) [33]. Пусть Xt = (Хі,уі) и Х і = {х[,у {) - соответствующие друг другу точки в изображениях. Тогда задачу можно сформулировать как нахождение такой матрицы преобразования Н , которая переводит координаты точек первого изображения в координаты точек второго: \х Л Г/00 01 где используется представление в виде однородных координат и Н определяется с точностью до масштаба. Используя подход direct linear transformation (DLT) [33], перепишем уравнения последовательно представив элементы матрицы Н в виде вектора h: , где n - количество пар соответствующих координат; иначе говоря приведем к виду Ah = 0. Поиск значения h, минимизирующего значение ошибки, производится с помощью сингулярного разложения матрицы АТА: ATA = UDUT, (4.6) где D - диагональная матрица, состоящая из сингулярных чисел, а U - матрица состоящая из сингулярных векторов. Вектор h таким образом равен сингулярному вектору, соответствующему минимальному сингулярному числу. После того, как построена матрица преобразования, все соответствия опорных точек проверяются на согласованность с ограничением модели: Г - НХ\\ d, (4.7) где d - граничная величина погрешности преобразования координат. Учитывая, что координаты точек нормированы в диапазоне [-1..1], d принимается равным 0,03. Те соответствия, координаты которых после преобразования отличаются от целевых менее чем на максимальную погрешность, считаются удовлетворяющими модели - “не-выбросами” (inliers), остальные считаются неверными - "выбросами” (outliers). Влияние значения максимальной погрешности модели на общую Рисунок 4.8. Влияние максимальной погрешности суммарную погрешность показана на рис. 4.8. После всех бросков кубиков, выбирается тот вариант, который имел наибольшее количество удовлетворяющих модели соответствий, и он принимается как потенциальное преобразование одного сегмента в другой. На рис. 4.9 изображен пример удовлетворяющих модели соответствий дескрипторов.