Содержание к диссертации
Введение
Глава 1. Обзор современного состояния проблем интерпретации в автоматическом анализе изображений 15
1.1. Введение 15
1.2. Представления изображений в виде необработанных данных 17
1.3. Низкоуровневые представления 19
1.3.1. Функциональные модели 20
1.3.2. Вероятностные модели 22
1.3.3. Сопоставления изображений на пиксельном уровне 25
1.4. Средний уровень: структурные методы 26
1.4.1. Контурные представления изображений 28
1.4.2. Непроизводные структурные элементы 31
1.4.3. Составные структурные элементы 34
1.4.4. Сопоставление символьных описаний 35
1.5. Верхний уровень: методы, основанные на знаниях 36
1.6. Иерархические представления изображений 40
Выводы из первой главы 44
Глава 2. Разработка методов автоматического построения иерархических структурных описаний изображений 45
2.1. Введение 45
2.2. Критерий сравнения гипотез в индуктивном выводе 46
2.2.1. Байесовский вывод 46
2.2.2. Принцип минимальной длины описания 47
2.2.3. Интерпретация изображений как минимизация длины описания 48
2.2.4. Выводы 50
2.3. Модели общих типов 50
2.3.1. Регрессионные модели 50
2.3.2. Модели, использующиеся в задачах распознавание и группирование 56
2.3.3. Модели сегментация 57
2.3.4. Выводы 59
2.4. Формирование пространства моделей изображений 60
2.4.1. Предположения Д. Марра 60
2.4.2. Сведение предположений Д. Марра к моделям общих классов 61
2.4.3. Выводы 63
2.5. Сегментация изображений как переход к контурным представлениям... 64
2.5.1. Построение целевой функции 64
2.5.2. Алгоритм сегментации 66
2.5.3. Расширение класса регрессионных моделей в алгоритме сегментации 67
2.5.4. Выводы 70
2.6. Построение структурных элементов на основе контуров 70
2.6.1. Выбор представления контуров 70
2.6.2. Алгоритм сегментации контуров 72
2.6.3. Выводы 74
2.7. Верхний структурный уровень 74
2.7.1. Подходы к объединению структурных элементов 74
2.7.2. Группирование элементов по их подобию и регулярности расположения 76
2.7.3. Формирование составных структурных элементов 82
2.7.4. Выводы 85
Выводы из второй главы 85
Глава 3. Автоматическое структурное сопоставление изображений в условиях их сезонно-суточного и спектрального несоответствия 86
3.1. Компоненты методов сопоставления изображений 86
3.2. Определение пространства поиска 87
3.2.1. Выбор характерных признаков изображений для сопоставления 87
3.2.2. Выбор класса взаимных пространственных преобразований 88
3.2.3. Выводы 89
3.3. Стратегия поиска оптимального сопоставления 89
3.3.1. Критерий качества сопоставления 89
3.3.2. Многоуровневый алгоритм поиска оптимального сопоставления 92
3.3.3. Выводы 97
3.4. Экспериментальная проверка метода сопоставления изображений 97
3.4.1. Сопоставление изображений, полученных в разное время года и при использовании сенсоров различных типов 97
3.4.2. Робастность алгоритма структурного сопоставления 107
3.4.3. Временные характеристики алгоритма сопоставления 110
3.4.4. Выводы 110
Выводы из третьей главы 110
Глава 4. Метод локальной корреляции для совмещения изображений с высокой точностью 112
4.1. Введение 112
4.2. Метод локальной корреляции 113
4.2.1. Установление соответствия между опорными точками 113
4.2.2. Алгоритм локальной корреляции 115
4.2.3. Выводы 119
4.3. Экспериментальная проверка метода локальной корреляции 119
4.3.1. Исправление ошибок структурного сопоставления и расширение класса допустимых взаимных пространственных преобразований изображений 119
4.3.2. Устойчивость и точность алгоритма локальной корреляции 125
4.3.3. Выводы 127
4.4. Практическое применение 127
4.4.1. Введение 127
4.4.2. Синтез панорамных снимков 127
4.4.3. Восстановление информации в загороженных областях изображений 128
4.4.4. Выявление изменений 129
4.4.5. Геокодирование 130
4.4.6. Автоматическое извлечение изображений из баз данных 132
4.4.7. Распознавание отпечатков пальцев 133
4.4.8. Выводы 133
Выводы из четвертой главы 133
Основные результаты и выводы. 135
Л итерату ра 138
Приложение А
- Низкоуровневые представления
- Формирование пространства моделей изображений
- Стратегия поиска оптимального сопоставления
- Экспериментальная проверка метода локальной корреляции
Введение к работе
Актуальность проблемы
Исследование Земли с использованием космических и авиационных систем наблюдения служит мощным инструментом в различных областях хозяйственной и научной деятельности. Возрастающие возможности бортовых оптических и радиолокационных сенсоров и увеличивающаяся пропускная способность каналов беспроводной связи приводят к постоянному росту объемов данных изображений, поступающих в наземные центры обработки. В этих условиях все более актуальной становится автоматизация, по крайней мере, части тех операций анализа и интерпретации аэрокосмических снимков, которые по сей день выполняются квалифицированными экспертами-дешифровщиками.
Одной из наиболее важных из подлежащих автоматизации операций представляется сопоставление (отождествление идентичных элементов) двух снимков, полученных с разных ракурсов, в разное время, возможно, разными типами сенсоров (инфракрасных, видимого диапазона, радиолокационных и других), поскольку эта операция зачастую предшествует выполнению других операций анализа аэрокосмических снимков. Такое сопоставление необходимо для записи снимков в единой системе координат (т.е. для их совмещения) с целью либо синтеза карт больших размеров на основе локальных снимков, либо дополнения информации, содержащейся в одном снимке, данными из других снимков того же фрагмента земной поверхности, либо выявления произошедших изменений. В практических задачах сопоставление зачастую требуется выполнять с высокой точностью.
В отличие от большинства классических задач автоматического анализа изображений в промышленной робототехнике, медицине, криминалистике, охранных системах и т.п. аэрокосмические видеоданные характеризуются значительно большей априорной неопределенностью. Эта неопределенность связана с сезонными и суточными изменениями наблюдаемых ландшафтов, специфическими отличиями изображений, сформированных различными типами видеодатчиков, и огромным многообразием подлежащих у автоматическому анализу и интерпретации сюжетов. При этом идентичность содержания одной и той же сцены, присутствующей на разных изображениях, сохраняется независимо от условий съемки.
Группой методов, позволяющих использовать содержательную идентичность изображений и преодолевать указанную априорную „ неопределенность при сопоставлении изображений, являются структурные методы анализа. Однако существовавшие на момент начала данной работы структурные методы не позволяли достичь требуемой в практических приложениях точности и робастности сопоставления. Устранение этих недостатков могло быть осуществлено с помощью проведения анализа изображений на различных уровнях (пиксельном, контурном и структурном), то есть с помощью иерархического подхода. Таким образом, перспективным для решения задачи сопоставления аэрокосмических изображений являлось дальнейшее развитие иерархических структурных методов.
Цель работы
Высокоточное сопоставление аэрокосмических изображений, полученных с разных ракурсов, подверженных сезонно-суточным изменениям или содержащих различия, вызванные использованием сенсоров различных типов; разработка методов извлечения из изображений информации, инвариантной к возможным изменениям условий съемки.
Основные задачи:
создание иерархического структурного представления изображений, в котором учитываются общие допущения о свойствах видимого мира;
вывод критерия оптимальности описания изображения в рамках предложенного представления и разработка методов построения структурного описания изображений путем оптимизации выработанного критерия;
разработка методов сопоставления изображений через соотнесение их иерархических структурных описаний;
разработка методов повышения точности сопоставления и расширение возможных типов взаимных пространственных преобразований изображений путем коррекции результатов структурного сопоставления.
На зашиту выносятся:
1) Теоретико-информационный подход и методы построения иерархических структурных описаний изображений, позволяющие максимизировать количество извлекаемой из изображений информации, инвариантной к изменению условий съемки.
2) Метод сопоставления аэрокосмических изображений, полученных с разных ракурсов, в разное время суток и года, с помощью сенсоров различных типов. Сопоставление выполняется иерархически на основе адаптивно корректируемых структурных описаний за время, полиномиально зависящее от количества структурных элементов.
3) Метод локальной корреляции как способ достижения более высокой точности совмещения изображений и расширения класса их допустимых взаимных пространственных преобразований в задачах структурного сопоставления и совмещения изображений.
4) Аналитические выражения оптимального фильтра пространственного спектра для операции фазовой корреляции, устанавливающие необходимость учета гармоник пространственного спектра с весом, обратно пропорциональным их номеру, поскольку фазы гармоник смещаются при геометрических искажениях изображения тем быстрее, чем выше номер гармоники.
5) Многоэтапный способ итеративной оптимизации информационной целевой функции в задачах построения структурных описаний изображений, включающий этап получения приближенного решения с использованием упрощенных моделей, этап получения решения в расширенном пространстве моделей и этап уточнения решения.
Научная новизна работы
• Предложен способ иерархической декомпозиции задачи структурного сопоставления, использующий результаты сегментации изображений и позволяющий уменьшить вычислительную сложность задачи сопоставления.
• Разработан метод адаптивной коррекции структурных описаний в процессе их сопоставления.
• Разработан механизм распространения информации о положении опорных точек в методе локальной корреляции.
• Выведены аналитические выражения для фильтрации пространственного спектра изображений, увеличивающей отношение сигнал/шум на кросс корреляционном поле в присутствии взаимных геометрических искажений изображений.
• Разработано иерархическое структурное представление изображений, различные уровни которого объединены общей информационной целевой функцией.
• Получены формулы, определяющие качество структурного описания, а также выражения, определяющие степень сходства структурных элементов.
Научная и практическая значимость
Автоматические методы и алгоритмы иерархического структурного сопоставления аэрокосмических изображений, позволяющие достигать высокой точности совмещения и осуществлять робастное сопоставление пар изображений, снятых с разных ракурсов, в разное время суток и года и с помощью сенсоров различного типа, могут найти широкое применение в фотограмметрии, дистанционном сборе данных. В первую очередь это относится к таким практическим задачам, как геокодирование и экономический и экологический мониторинг поверхности Земли.
Реализация результатов работы
Результаты диссертационной работы были использованы в НИР 12200-060-03 «Разработка и создание методов, алгоритмов и программ автоматического текстурного и структурного анализа изображений в задачах измерения, контроля и сопоставления изображений», проводимой по заказу Министерства науки, а также при постановке и проведении ОКР «Сатрап», выполняемой по заказу М.О. РФ. Результаты диссертационной работы были также использованы в ОКР «Сфера», проводимой в ЗАО НИИВЦ «Карат».
Акты внедрения приложены к диссертации.
Личный вклад автора построение иерархического структурного представления изображений на основе теоретико-информационного подхода;
модернизация метода построения структурного описания изображений на основе теоретико-информационного подхода;
усовершенствование метода структурного сопоставления: расширение класса допустимых взаимных пространственных преобразований изображений с группы подобия до аффинной группы, разработка механизма адаптивной коррекции структурных описаний изображений в ходе их сопоставления;
вывод аналитических выражений для оптимального фильтра пространственных спектров изображений, использующегося при решении задачи локальной корреляции;
воплощение разработанных методов в форме компьютерных программ;
проведение экспериментальной проверки разработанных методов на большой выборке реальных аэрокосмических снимков. Апробация работы Основные результаты работы докладывались на следующих научных форумах:
• конференции "Battlespace digitization and network-centric warfare П" в рамках международного симпозиума "AeroSence-2002" (Orlando, 2002);
• конференции "Image and signal processing for remote sensing IX" в рамках международного симпозиума "Remote Sensing - 2003" (Barcelona, 2003);
• VII-ой международной конференции "І Іеразрушающие методы контроля и компьютерное моделирование в науке и технике" NDTCS-2003 (Санкт-Петербург, 2003);
• конференции "Automatic target recognition XIV" в рамках международного симпозиума "Defense and Security-2004" (Orlando, 2004);
• VIII-ой международной конференции "Неразрушающие методы контроля и компьютерное моделирование в науке и технике", NDTCS-2004 (Санкт-Петербург, 2004);
• VIII-ой общероссийской научной конференции "Современная логика: проблемы теории, истории и применения в науке" (С.-Петербург, 2004);
• конференции "Automatic target recognition XV" в рамках международного симпозиума "Defense and Security - 2005" (Orlando, 2005).
Публикации
По материалам диссертации опубликовано 10 научных работ:
1. Lutsiv V.R., Malyshev LA., Pepelka V., Potapov A.S. Target independent algorithms for description and structural matching of aerospace photographs II Proc. SPIE, 2002, Vol. 4741, pp. 351-362.
2. Lutsiv V., Malyshev L, Potapov A. Hierarchical structural matching algorithms for registration of aerospace images II Proc. SPIE, 2003, Vol. 5238, pp. 164-175.
3. Potapov A.S., Lutsiv V.R. Informationheoretic approach to image description and interpretation II Proceedings of SPIE, 2003, Vol. 5400, pp. 277-283.
4. Потапов A.C., Малышев И.А., Луцив В.Р. Совмещение аэрокосмических изображений с субпиксельной точностью методом локальной корреляции // Оптический журнал, 2004, т. 71, № 5, с. 31-36.
5. Потапов А.С. Влияние взаимных геометрических искажений изображений на возможность их пространственного совмещения методом локальной корреляции // Оптический журнал, 2004, т. 71, № 8, с. 74-80.
6. Potapov A.S. Image matching with the use of the minimum description length approach II Proc. SPIE, 2004, Vol. 5426, pp. 164-175.
7. Potapov A.S., Gamayunova O.S. Information criterion for constructing the hierarchical structural representations of images II Proc. SPIE, 2005, Vol. 5807, pp. 443-454.
8. Lutsiv V., Potapov A., Novikova Т., Lapina N. Hierarchical 3D structural matching in the aerospace photographs and indoor scenes II Proc. SPIE, 2005, Vol. 5807, pp. 455-466.
9. Potapov A.S., Luciv V.R., Malyshev LA. Sub-pixel precise image analysis in the industrial environment II Proceedings of SPIE, 2004, Vol. 5831, pp. 199-203.
Ю.Потапов А.С. Принцип минимальной длины описания и сравнение гипотез // Современная логика: проблемы теории, истории и применения в науке. Материалы VIII Общероссийской научной конференции, Санкт-Петербург, 2004, с. 409-412.
9. ю Министерства науки, 2004, 22 стр.
Структура и объем диссертации
Диссертация состоит из введения, четырех глав, заключения и списка цитируемой литературы. Она содержит 158 страниц машинописного текста, 38 рисунков и 2 таблицы. Список цитируемой литературы содержит 129 наименований. Нумерация формул самостоятельная в каждой главе, нумерация рисунков и таблиц сквозная по всей диссертации.
Во введении обосновывается актуальность темы и сформулированы цель, научная новизна и практическая значимость работы. Представлены основные результаты и положения, выносимые на защиту, а также кратко изложено содержание разделов диссертации.
Первая глава диссертации носит обзорный характер. В ней рассмотрена проблема представления изображений в задачах их автоматического анализа. Описаны основные классы представлений в зависимости от уровня абстракции: низкоуровневые, или пиксельные, представления, промежуточные символьные представления, включающие уровень контуров, непроизводных структурных элементов и составных структурных элементов, и представления, основанные на знаниях. Представления каждого из классов используются как в задачах сопоставления изображений, так и в других задачах их интерпретации. На основании проведенного анализа литературных источников сделан вывод, что наиболее перспективными представлениями изображений являются иерархические структурные представления.
Во второй главе описан разработанный в процессе выполнения работы подход к интерпретации изображений на основе теории информации и принципа минимальной длины описания (МДО). Интерпретация изображений рассмотрена как поиск наиболее информативной модели из некоторого семейства, задающегося выбранным представлением изображений. В начале главы рассмотрены общие методы построения моделей: регрессии, распознавания, группирования и сегментации, — которые в дальнейшем используются при разработке методов интерпретации изображений. Далее производится построение иерархического структурного представления изображений, инвариантного к условиям съемки, на основе предположений о свойствах видимого мира, сформулированных Д. Марром. Для этого словесно сформулированные предположения трактуются как ограничения, накладываемые на модели группирования и сегментации. Далее разрабатываются методы и алгоритмы формирования структурных описаний изображений в рамках построенного представления, включающего уровень контуров, уровень структурных элементов и уровень их групп.
В третьей главе решена проблема структурного сопоставления аэрокосмических изображений, различающихся из-за смены ракурса, смены типа сенсора, сезонно-суточных изменений. В проблеме сопоставления выделены три аспекта: 1) тип характерных признаков, выделяемых на изображениях и являющихся основой для сопоставления; 2) класс взаимного пространственного преобразования изображений (пространство поиска); 3) целевая функция, определяющая оптимальность сопоставления, и алгоритм оптимизации. Далее рассмотрен каждый из этих аспектов. В качестве характерных признаков выбраны структурные элементы, методы построения которых приведены во второй главе. В качестве модели взаимного пространственного преобразования выбрана аффинная модель, линейно аппроксимирующая проективное преобразование, характерное для аэрокосмических изображений. Подробнее разобран вопрос построения целевой функции и алгоритма оптимизации. В качестве целевой функции разработана эвристическая аппроксимация количества взаимной информации, содержащейся в структурных описаниях в зависимости от гипотезы сопоставления. Далее описан разработанный в ходе выполнения работы метод поиска лучшего сопоставления, представляющий собой обход дерева вариантов сопоставления с отсечением неперспективных гипотез. Отсечение ветвей позволяет осуществлять обход дерева и находить субоптимальную гипотезу сопоставления за время, полиномиально зависящее от количества структурных элементов. В заключение главы приведены результаты экспериментальной проверки метода на реальных аэрокосмических снимках.
Четвертая глава посвящена разработке метода локальной корреляции, предназначенного для улучшения результатов робастного структурного сопоставления изображений и уточнения линейной (аффинной) аппроксимации взаимного пространственного преобразования и дополнения его проективной компонентой и полем локальных смещений. Данный метод итеративно измеряет смещения между фрагментами двух изображений на основе фазовой корреляции. Точки с измеренными положениями на каждой итерации используются для расчета параметров пространственного преобразования и предсказания положения точек, для которых еще не было определено соответствие на двух изображениях. В конце главы приведены результаты тестирования метода совмещения на реальных парах изображений и рассмотрен вопрос точности метода.
В заключении сформулированы основные результаты, достигнутые в диссертационной работе, и сформулированы вытекающие из них выводы.
Низкоуровневые представления
Представления на пиксельном уровне не говорят нам о том, как следует работать с изображениями. В связи с этим возникает естественное желание представить изображение как элемент некоторого математического пространства. Часто отображение из пиксельного представления в выбранное математическое пространство является взаимнооднозначным и непосредственно выражается через исходные значения интенсивностей, а результаты математических операций над изображениями снова представляются в виде изображения. Из-за этого интерпретации изображений в качестве массивов пикселей и в качестве математических объектов часто смешивают, объединяя их в один класс [9, 11], а сам процесс такой переработки изображений выделяют в отдельный тип задач — обработка изображений [12, стр. 140]. Хотя математические модели изображений можно условно отнести к пиксельному уровню, между ними существуют принципиальные отличия.
Интерпретация изображения в качестве элемента математического пространства позволяет распространить формальные операции, введенные на этом пространстве, и на изображения. Это дает обширный набор строгих внутренне непротиворечивых средств анализа и преобразования изображений. К примеру, если выбранное пространство является метрическим, то появляется возможность формального определения "расстояния" (т.е. степени сходства) между изображениями.
К сожалению, существующие на данный момент строгие математическиеS модели изображений являются достаточно низкоуровневыми и имеютограниченную область применения.
Два основных класса математических моделей изображений включают [13]: представления в виде случайных полей и функциональные представления.
При использовании функциональных моделей изображение интерпретируется как функция из некоторого (например, Гильбертова)пространства:где G — область определения функции, а V — область ее значений. Величина п - размерность изображения (обычно равная двум), а т — размерность вектора физических величин, измеренных для каждой точки. Например, для полутоновых изображений т = 1, а для цветных RGB изображений т = 3. Функциональное представление является базовым для проведения таких s операций над изображениями, как пространственное преобразованиеизображений, преобразования яркости, фильтрация и др. Пространственное преобразование изображения (масштабирование, вращение и т.д.) осуществляется с помощью смены системы координат в области G : где g — это функция, ставящая в соответствие каждой точке из области N определения G исходного изображения / точку в области определения G2 преобразованного изображения /2. Преобразование яркости (например, изменение яркости или контраста для всего изображения) или преобразования цвета (если V - это цветовое пространство) может быть представлено следующим образом: где h - это функция, зависящая только от значения функции / в данной точке N и ставящая в соответствие этому значению новое значение, возможно, из другой области V2. Изменению яркости соответствует функция h. Фильтрация изображений является более широким понятием, чем два приведенных выше преобразования, так как в общем случае зависит от всего содержимого изображения. Если Ф = {/1 /: G - V) - это функциональное пространство, к которому принадлежит данное изображение, а Ф2 — пространство, к которому принадлежит обработанное изображение, то фильтрация изображения - это произвольное отображение из пространства Ф в Ф2: Г:Ф-»Ф2. Наиболее часто привлекаемой является линейная фильтрация, которая представима в виде операции свертки с некоторым ядром q : К примеру, с помощью линейной фильтрации представляются такие операции, как сглаживание изображения или его дифференцирование. Еще одной важной возможностью, предоставляемой функциональными моделями изображений, является смена базиса в исходном функциональном пространстве Ф. Частным, но очень важным, примером является преобразование Фурье:F&) = J/(x)e", :,:VJc. (1.6)G Функциональные (и другие математические) представления позволяют формально ввести понятие инварианта. Желание работать с представлениями, инвариантными к некоторому типу преобразований, совершенно естественно проистекают из того факта, что сцена с одним и тем же содержанием может совершенно по-разному (при пиксельном представлении) выглядеть при разных условиях наблюдения. Примером теоретического подхода к анализу сцен, привлекающим понятие инварианта, является подход на основе групп Ли на плоскости (см., напр., [14]). Поскольку каждое изображение исходно представляется в виде набора точек с соответствующими им значениями интенсивностей (конечного массива данных), а число функций данного класса, как правило, бесконечно, то необходимо вводить некоторые ограничения, позволяющие из множества всех подходящих функций выбрать лучшую. Часто это достигается тем, что рассматривается ограниченный класс функций, так что по набору точек, образующих данное изображение, выбор функции однозначен. Однако в ряде случаев удобнее накладывать интегральные ограничения из некоторых модельных соображений. Эти ограничения часто представляются в виде минимизации некоторого функционала, и задача построения модели изображения превращается в задачу вариационного исчисления. Наиболее простыми функционалами, подвергающимися минимизации, являются следующие [15]: Последняя норма является наиболее широко используемой (это т.н. регуляризация Тихонова, см., напр., [16]). Выбор минимизируемого функционала (также называемого мерой сложности изображения) часто осуществляется на основе исследований, посвященных определению статистических свойств естественных изображений и особенностей зрительного восприятия животных и человека (см., напр., [17, 18]). Этот подход также применяется при привлечении статистических моделей изображений: если изображение представляется в виде случайной функции, то выбор ее наиболее вероятной реализации осуществляется посредством минимизации некоторого функционала при соблюдении ограничений, налагаемых исходными данными.
Формирование пространства моделей изображений
Перейдем теперь к решению первой проблемы, поставленной в начале главы, а именно к проблеме построения пространства моделей изображений. В рамках целевого подхода в иконике, противопоставляемого реконструкционнои парадигме, такие пространства моделей строятся, исходя из той конкретной прикладной задачи, для которой разрабатывается система машинного зрения, тогда как в самом реконструкционном подходе используются общие ограничения, накладываемые физическим миром [4]. Впервые достаточно подробный список таких физических ограничений был сформулирован Д. Марром [6, стр. 57-63]. Мы приведем этот список для того, чтобы затем переформулировать эти ограничения в терминах пространств моделей сегментации и группирования. 1. Поверхности как реальные объекты: весь видимый мир можно рассматривать как некоторую композицию гладких поверхностей, функции отражательной способности которых могут отличаться сложной пространственной структурой. 2. Иерархическая организация: пространственная организация функции отражательной способности некоторой поверхности часто порождается совместным воздействием целого ряда различных процессов, каждый из которых относится к отдельному уровню. 3. Подобие: объекты, появляющиеся на некоторой поверхности в результате некоторого процесса порождения отражательной способности, действующего на некотором определенном масштабном уровне, обычно обладают большим сходством по размерам, локальному контрасту, цвету и пространственной организации между собой, чем с другими объектами этой же поверхности. 4. Пространственная непрерывность: характерные объекты, возникающие на некоторой поверхности в результате действия какого-то одного процесса, помимо того, что они обладают «внутренним» подобием, часто образуют определенную пространственную организацию, принимающую вид кривых, прямых и, возможно, более сложных конфигураций. 5. Непрерывность нарушений непрерывности: геометрическое место разрывов по глубине или ориентации поверхности почти везде гладко. 6. Непрерывность движения: при наличии любого нарушения непрерывности движения более чем в одной точке, например, вдоль некоторой прямой, следует считать, что имеет место граница объекта. Эти пункты могут дополняться законами распространения излучения, с помощью которых можно построить, например, модели стереозрения или процесса затенения и образования теней. Однако здесь рассматривается проблема анализа аэрокосмических фотографий, которые обычно можно считать изображениями равномерно освещенной плоской поверхности. Хотя в некоторых задачах (например, при анализе инфраструктуры городов) такое приближение неприменимо, мы ограничимся использованием допущений, введенных Д. Марром. Как уже отмечалось выше, реконструкция сцены по ее изображению равносильна построению представления изображений, инвариантного условиям съемки. Действительно, в предположениях Д. Марра речь ведется о видимых поверхностях и их границах, взаимное расположение которых не должно зависеть от условий съемки. Рассмотрим первое предположение. Заметим, что каждая видимая поверхность представлена на изображении некоторой областью. Функция отражательной способности этой поверхности под воздействием освещения порождает распределение яркости внутри соответствующей области изображения, специфическое для данной области. Иными словами, первое предположение говорит о том, что для описания изображения необходимо использовать модели сегментации. Изображение должно быть разбито на области, и распределения яркости внутри каждой из них необходимо описать с помощью отдельной регрессионной модели. Сам Д. Марр критиковал идею сегментации изображений [6, стр. 275-276], широко распространенную в компьютерном зрении. Однако тогда под сегментацией понималось разделение изображения на объекты и фон. Именно неопределенность этих понятий и была причиной критики. Здесь же сегментация рассматривается с точки зрения построения модели и не привлекает понятия объекта и фона. Более того, если первое предположение Д. Марра соблюдается, то оптимальная модель сегментации выделит как раз те области на изображении, которые соответствуют видимым поверхностям. При обсуждении задачи сегментации было указано, что корректный выбор числа сегментов, каждый из которых описывается наилучшей регрессионной моделью, позволяет минимизировать суммарную длину описания. Этот критерий и будет использована в данной работе. Рассмотрим пятое предположение. Геометрическое место точек разрывов по глубине или ориентации поверхностей соответствует на изображении границам областей (контурам). Данное предположение говорит о том, что границы областей почти всюду гладки, а значит, для их описания также должны использоваться модели сегментации: точки нарушения гладкости разделяют сегменты на контурах, каждый из которых описывается некоторой гладкой функцией. В данной работе для сегментации контуров с целью построения структурных элементов, как и для сегментации самого изображения, будет использован информационный критерий. Второе, третье и четвертое предположения Д. Марра также можно интерпретировать с позиции уменьшения длины описания. Эти предположения указывают на то, какие регрессионные модели следует использовать для описания содержимого областей. Характерные детали, присутствующие на видимых поверхностях, должны иерархически группироваться на основе подобия их внутренних признаков (размеры, ориентация и т.д.) и местоположения (если они образуют некоторые регулярные структуры). Последовательное группирование характерных деталей вполне соответствует построению составных структурных элементов. Сходство структурных элементов, как и регулярности в их взаимном расположении, подразумевает наличие общей информации в их описаниях. Значит, для выработки корректного критерия формирования составных структурных элементов может быть использован принцип минимальной длины описания, что также является предметом настоящего исследования. Шестое предположение имеет отношение к динамическим сценам. Хотя здесь мы рассматриваем вопросы интерпретации лишь отдельных изображений статических сцен, описание движения также может быть включено в общую схему, в которой принцип МДО привлекается в качестве критерия [116, 117]. Принцип МДО применялся для решения и других задач компьютерного зрения, например, для распознавания рукописных текстов [118], сопоставления изображений [119], восстановления фундаментальной матрицы [120], описания плоских форм [121, 122] и т.д. Эти применения достаточно ограниченны и относятся лишь к одному из элементов анализа изображений, тем не менее, они отчетливо продемонстрировали перспективность применения принципа МДО в компьютерном зрении. Для выделения границ видимых поверхностей, положение которых инвариантно условиям съемки, необходимо привлекать модели сегментации. Положение точек нарушения гладкости на границах также не зависит от условий съемки и может быть выявлено путем сегментации границ. Взаимное расположение построенных в результате сегментации структурных элементов может быть описано на основе моделей группирования. Целевая функция во всех случаях может базироваться на принципе МДО, но ее вид требуется уточнить для каждой из задач.
Стратегия поиска оптимального сопоставления
Для создания метода сопоставления изображений после выбора пространства поиска необходимо определить целевую функцию, указывающую качество сопоставления (степень соответствия изображений при выбранной гипотезе о пространственном преобразовании), а затем разработать алгоритм ее оптимизации в выбранном пространстве поиска.
Целевая функция задается, исходя из выбранных характеристических признаков изображений. Однако задача выбора адекватного критерия редко ставится строго с указанием условий применимости этого критерия. К примеру, коэффициент корреляции двух изображений, вычисленный по всей их площади, дает адекватную меру их сходства, только если интенсивности соответствующих пикселей на двух изображениях совпадают с точностью до линейного преобразования (общего для всех пикселей), что не выполняется для аэрокосмических изображений.
Как и построение описания отдельного изображения, проблему сопоставления изображений можно рассмотреть с точки зрения принципа минимальной длины описания как задачу построения совместного описания двух изображений.
Действительно, изображения одной и той же местности, даже полученные с разных ракурсов и с помощью различных сенсоров, обладают ненулевой взаимной информацией. Извлечение этой информации возможно только при правильном совмещении изображений. Степень сжатия, которая достигается путем совместного описания изображений по сравнению с их независимым описанием, является корректным критерием качества совмещения.
Пусть каждое из двух изображений представлено набором структурных элементов: {( ,,.у,,,)}, [, и {О .л Д )}", соответственно. Пусть (х,у) = g( ,/) —гипотеза о пространственном преобразовании, действующем от второго изображения к первому. С помощью функции g(x,y) можно перевести структурные элементы из одной системы координат в другую и составить общее описание {(x,,y,,z,)} , где M = N + N , (x,,y,,zl) = g(x l,y l,z l),i = N..M -преобразованные элементы второго изображения. Теперь можно оценить длину совместного описания структуры двух изображений.
Если считать, что каждый элемент описывается лишь своими координатами, то, как мы уже отмечали в разделе 2.7.2, длина их описания может быть оценена через построение минимального остового дерева. Именно такой подход используется в работе [69]. Однако в общем случае необходимо описать не только положение структурных элементов, но и другие их признаки. Эту задачу можно рассмотреть в том же ключе, что и задачу построения составных структурных элементов (см. параграф 2.7).
Для определения критерия качества сопоставления будем считать, что все структурные элементы {( ,, ,,2,)) , описываются раздельно, кроме тех, для которых установлено соответствие. Элементы, которые считаются тождественными на двух изображениях, описываются совместно.
При группировании структурных элементов было представлено (см. раздел 2.7.1) две схемы: в первой совместно описывались параметры элементов, во второй параметры элементов считались идентичными, но при этом менялись величины невязок, с которыми элементы аппроксимировали контуры. При совмещении изображений ситуация аналогичная: совместное описание сопоставленных элементов может быть выполнено как совместное описание их параметров, либо же параметры элементов могут быть приняты тождественными, но это вызовет изменение качества описания элементами соответствующих им участков контуров. Именно этот второй путь представляет интерес, поскольку изображения считаются тождественными по содержанию.
Поскольку в процессе структурного описания из-за ошибок и шумов контуры могут отклоняться и рваться, следует не только корректировать параметры отдельных элементов, но и допускать разделение одного элемента на два новых или слияние двух элементов в один, чтобы согласовать структурные описания двух изображений.
Таким образом, для данного пространственного преобразования g(x,y) следует определить пары соответствующих элементов, совместное описание положения и параметров которых уменьшает общую длину описания. Также следует скорректировать соответствующие друг другу элементы, если это приводит к уменьшению длины описания за счет уменьшения отличий между элементами в большей степени, чем увеличение длины описания за счет возрастания энтропии невязок для точек контуров. Это необходимо для более точной оценки качества текущей гипотезы сопоставления, а не в целях самой коррекции элементов.
Здесь будет использован эвристический критерий качества структурного сопоставления, полученный в более ранней нашей работе [39]:где N — количество структурных элементов, для которых установлены соответствия; AD - суммарная ошибка в положении, М. — суммарная ошибка в азимуте ориентации, AL — суммарная ошибка в длине элементов, wD,wA,wl — веса, с которыми учитываются различные ошибки. Значение критерия (3.1) пропорционально числу сопоставленных элементов, но добавление произвольного сопоставления в гипотезу приводит к увеличению ошибок, которые могут перевесить выигрыш от увеличения количества сопоставленных элементов. Таким образом, ищется компромисс между числом сопоставленных элементов и ошибками этого сопоставления, определяющимися тем, насколько хорошо соответствуют друг другу сопоставленные структурные элементы.
В наших работах [126, 127] показывается, что критерий (3.1) является эвристической аппроксимацией длины описания, и что он может быть улучшен, однако формально обоснованная реализация уточненного критерия с применением принципа МДО является одной из задач, которую предстоит решить в будущих исследованиях. На основе принципа МДО в данной работе решается только часть задачи сопоставления: выполняется адаптивная коррекция структурных элементов в процессе их сопоставления.
Разработаем последний компонент метода сопоставления — алгоритм поиска оптимального пространственного преобразования. Вместо того чтобывести поиск в пространстве параметров преобразования, будем осуществлять перебор возможных соответствий структурных элементов одного изображения элементам другого изображения.
Представим, что мы берем первый элемент на одном изображении и ставим ему в соответствие некоторый элемент на другом изображении (либо считаем, что ему никакой элемент не соответствует). Далее берем следующий элемент и ставим ему в соответствие еще не выбранный элемент. И так далее. Получаем дерево выбора. Каждый из листьев определяет,)}
Экспериментальная проверка метода локальной корреляции
Разработанный алгоритм улучшения совмещения изображений на основе использования их локальной корреляции был практически испытан на множестве пар реальных авиационных и космических снимков. При этом размер фрагментов был взят 64x64 пикселя, а для достижения предельной точности оказалось достаточно трех итераций.
Эксперименты показали, что применение этого алгоритма обеспечивает значительное улучшение качества совмещения как для изображений, отличающихся в основном общим взаимным проективным преобразованием, так и в более сложных случаях, связанных с локальными отклонениями взаимного преобразования координат от глобальной проективной модели. Проиллюстрируем характерные достоинства и недостатки разработанного алгоритма на основе двух приведенных ниже примеров.
На паре изображений, представленных на рис. 22, земная поверхность с разных сторон реки наклонена под различными углами, поэтому переход от одного изображения к другому для каждого из склонов описывается своим проективным преобразованием. После применения общего глобального преобразования координат остаются ошибки, возрастающие к краям изображений по мере удаления от реки и достигающие 10 пикселей. Эти ошибки иправляются методом локальной корреляции. Без компенсации локальных сдвигов данные изображения затруднительно использовать для последующего анализа, например, для выявления изменений.На рис. 23 приведены изображения, связанные достаточно сильным взаимным глобальным проективным преобразованием. При выполнении грубого предварительного совмещения опорные точки были построены, исходя из аффинной модели их взаимного преобразования (именно по такой модели работает структурный классификатор), поэтому рассчитанное начальное грубое преобразование обладает существенными ошибками, которые достигаютвеличины 37 пикселей (см. рис. 24). На рис. 24 также приведены результаты улучшенного совмещения.. Результаты совмещения изображений, представленных на рис.23. Слева - совмещение структурным классификатором (стрелкой указана не совмещенная деталь на паре изображений), справа - уточненное совмещение методом локальной корреляции с компенсацией ошибок до 30 пикселей и более (указанная деталь совмещена с точностью до 2 пикселей).
Видно, что улучшенное проективное преобразование достаточно хорошо в целом описывает переход от одного изображения к другому, то есть методом локальной корреляции были исправлены ошибки совмещения, составлявшие несколько десятков пикселей. Однако на исходных изображениях присутствуют высокие сооружения, снятые с разных ракурсов, что вызвало разрывы в измеренном поле локальных смещений. Подобные отклонения от глобального преобразования не могут быть исправлены методом локальной корреляции, что хорошо заметно на рис. 24. Это является основным ограничением его применимости.
Процедура локальной корреляционной коррекции совмещения показала работоспособность для пар изображений, полученных в разных спектральных полосах и в разные сезоны (см. рис. 25-27). Однако совмещение радиолокационных изображений с отическими ненадежно, и субпиксельная точность, как правило, не достигается. Рис. 26. Результаты совмещения изображений разныхмодальностей, представленных на рис. 17а, 176 (карта высот отображена с повышенным контрастом в целях улучшения иллюстрации). Сверху - результат структурного сопоставления (линейная ошибка порядка 10 пикселей, ошибка масштаба- 0.1). Снизу - результат нахождения точногосоответствия между изображениями методом локальной корреляции.- результат предварительного совмещения с ошибкой до 40 пикселей в правом нижнем углу и до 15 пикселей - в правом верхнем углу; г) -уточненное совмещение методом локальной корреляции с ошибкой менее 3 пикселей.r) Экспериментальные исследования, подкрепленные формуламиразрушения корреляционного отклика, которое вызвано некомпенсированнымипространственными искажениями, позволили установить допустимую ошибкупредварительного совмещения, которая может быть исправлена методомлокальной корреляции. Допустимое отклонение параметров аффинного» преобразования от тождественного отображения составило 0.1-0.15, что \ соответствует ошибке по масштабу в 10-15% или ошибке по углу взаимного вращения 5-10 градусов. Эта величина, однако, сильно зависит от содержания анализируемой сцены, в частности, от распределения энергии в пространственном спектре. При смещении энергии в область низких гармоник допустимы большие ошибки предварительного совмещения, в то время как при смещении энергии в область высоких гармоник алгоритм оказывается неустойчивым по отношению к меньшим ошибкам совмещения (см. уравнение Б. 13 в приложении Б). Дополнительный фактор, приводящий к понижению устойчивости алгоритма, связан с возможными различиями между самими изображениями. В частности, это касается совмещения оптических и радиолокационных изображений. При определенном содержании изображений алгоритм может вовсе не приводить к улучшению результатов совмещения даже при достаточно точном предварительном совмещении. На данный момент это остается ограничением метода, но мы видим следующий путь его преодоления. ч Метод локальной корреляции может рассматриваться в качестве нижнего уровня системы сопоставления изображений в рамках предложенного в этой работе иерархического подхода. Как и сопоставление на структурном уровне, сопоставление на пиксельном уровне может рассматриваться с теоретико информационной точки зрения. Действительно, поиск корреляционного максимума является частным случаем максимизации взаимной информации (см., напр., [128, 129]) или минимизации совместной длины описания. При » использовании корреляции неявно предполагается, что интенсивности
