Содержание к диссертации
Введение
Глава 1. Анализ моделей и технологий стереореконструкции, формулировка задач исследования 10
1.1 Модель регистрации изображений 10
1.2 Модель формирования разноракурсных изображений 18
1.3 Методы, алгоритмы и технологии реконструкции 3D сцен 21
1.4 Конкретизация задачи сопоставления без ректификации 26
1.5 Выводы к главе 1 32
Глава 2. Разработка модели и алгоритмов сопоставления изображений при известных условиях съёмки 33
2.1 Общая модель сопоставления изображений с учетом эпиполярных ограничений 33
2.2 Сопоставление фрагментов изображений, соответствующих точкам на эпиполярных линиях 39
2.3 Алгоритм нахождения соответствующих точек на эпиполярных линиях с использование весовых коэффициентов штрафа 47
2.4 Метод и алгоритм прореживающей фильтрации 54
2.5 Выводы к главе 2 56
Глава 3. Алгоритмы 3D реконструкции при неизвестных условиях съёмки на основе согласованной идентификации 58
3.1 Технология реконструкции ЗО-сцен при неизвестных условиях регистрации разноракурсных изображений 58
3.2 Формулировка задачи идентификации фундаментальной матрицы 60
3.3 Метод согласованной идентификации 62
3.4 Метод и вычислительный алгоритм последовательного формирования множества согласованных оценок
3.5 Сравнение с алгоритмом RANSAC 66
3.6 Решение задачи автокалибровки 70
3.7 Выводы к главе 3 76
Глава 4. Экспериментальные исследования 78
4.1 Описание информационной технологии 78
4.2 Моделирование сцен и разноракурсных изображений 81
4.3 Результаты ЗО-реконструкции с использованием алгоритма поиска соответствий точкам на эпиполярных линиях 83
4.4 Построение цифровой модели местности по разноракурсным изображениям при учёте эпиполярных ограничений весовыми коэффициентами штрафа 88
4.5 Выводы к главе 4 91
Заключение 93
Список цитируемой литературы 94
- Модель формирования разноракурсных изображений
- Сопоставление фрагментов изображений, соответствующих точкам на эпиполярных линиях
- Метод и вычислительный алгоритм последовательного формирования множества согласованных оценок
- Результаты ЗО-реконструкции с использованием алгоритма поиска соответствий точкам на эпиполярных линиях
Модель формирования разноракурсных изображений
Применение метода основано на предположении, что карта диспарантности представляет собой несколько больших однородных участков постоянной диспарантности с небольшим числом переходов между ними. Благодаря вейвлет-преобразованию большие однородные участки могут быть представлены с помощью небольшого числа вейвлет-коэффициентов, при этом важнейшие коэффициенты кластеризуются (располагаются) в местах разрывов. Особенно важной в этом методе является задача выбора изначальных измерений.
Большое число публикаций посвящено нахождению соответственных точек на разноракурсных снимках ДЗЗ. Эти публикации, как правило, ориентированы на построение сцен городского сюжета, и ключевой задачей является как можно более точное и детальное восстановление объектов сцены.
В статье [17] сравниваются три метода установления соответствий между стереопарами высокого разрешения: метод наименьших квадратов, метод динамического программирования и полуглобального сопоставления (semiglobal matching). Метод наименьших квадратов представляет собой сравнение фрагментов изображений по критерию наименьшей суммы квадратов разностей. В результате использования этого метода границы на изображениях оказываются сглаженными.
При решении задачи с использованием метода динамического программирования осуществляется сопоставление соответствующих эпиполярных линий на изображениях. Обработка этим методом даёт четкие границы, но сохраняет мало деталей на поверхностях крыш зданий. Метод SGM (полуглобальное сопоставление) даёт много деталей, но при восстановлении возникают артефакты.
В статье [18] предлагается улучшенный алгоритм автоматического сопоставления снимков с малой высоты на основе оператора SIFT (Scale-invariant feature transform). Вместо традиционно использующегося в SIFT Евклидова расстояния используется коэффициент корреляции между шестнадцатью 8-мерными гистограммами.
Этап восстановления трёхмерной сцены по карте диспарантности как таковой не представляет особого научного интереса, поскольку довольно тривиален. Расстояние от камеры до объекта обратно пропорционально сдвигу соответствующих точек. В целом, процесс восстановления 3D сцены по известным соответствующим точкам подробно и с примерами описан в статье [19].
В статье [20] рассматривается создание ЦМР с помощью снимков с космического аппарата (КА) ALOS/PRISM, с помощью наземных опорных точек с GPS приёмниками определены параметры внешнего ориентирования снимков с точностью до субпикселя. Среднеквадратичное значение измеренных высот составило приблизительно 3,5 м. Это соответствует пределу теоретической точности, которую можно достичь при небольшом количестве наземных опорных точек и применении данных методов.
В статьях [21], [22] представлены алгоритмы формирования цифровых моделей рельефа с использованием разноракурсных изображений, полученных от КА «Ресурс-ДК». Сравниваются два подхода к обработке стереопар: идентификация отдельных одноименных точек с их последующим объединением в триангуляционную сеть; формирование карты диспарантности, задающей смещения координат одноименных точек для всех пикселей базового изображения, посредством алгоритма оптимизационного поиска. Вычислительный процесс оптимизирован под параллельное выполнение алгоритмов на многопроцессорных ЭВМ, это позволило значительно сократить время формирования выходной ЦМР. Время формирования выходной ЦМР с пространственным разрешением не менее 1 м для каждого изображения размером 25000x55000 пикселей составляет порядка трёх часов на 8-процессорной ЭВМ. Общим недостатком рассмотренных работ является отсутствие учета эпиполярных ограничений. Вследствие этого уменьшается надёжность сопоставления и ухудшается качество получаемых карт диспарантности, трёхмерной модели сцены или ЦМР в случае обработки ДЗЗ.
В работе [23] рассматривается задача восстановления 3D поверхности как с использованием признаков на основе освещения, так и с применением стерео сопоставления. Восстановление карты смещений производится на основе базовой поверхности, при этом гладкая базовая модель формируется с помощью традиционных технологий. Предложенный метод использует изменение освещения вследствие вращения объекта, позволяя восстанавливать смещения как на текстурированных, так и нетекстурированных участках одинаковым способом. В частности, информация об освещении добавляется в функцию цветопостоянства для стерео обработки нескольких изображений сцены
В статье [24] предлагается алгоритм реконструкции сцены, зарегистрированной с нескольких точек зрения. Метод основан на робастном бинокулярном стерео сопоставлении, за которым следует адаптивная поточечная фильтрация объединенных облаков точек и эффективная, высококачественная генерация сетки. Метод хорошо работает также при наличии в сцене поверхностей сильной кривизны.
Метод состоит из двух основных этапов: формирования облака точек посредством стерео сопоставления и восстановления трёхмерной сетки на облаке точек. В свою очередь, трёхмерное восстановление состоит из кластеризации облака точек, удаления шумов и пространственной триангуляции точек. Недостатком последних двух подходов является требование наличия большого числа изображений сцены.
Сопоставление фрагментов изображений, соответствующих точкам на эпиполярных линиях
В ситуации, когда направления эпиполярных линий примерно одинаковы, что характерно для космических изображений, более подходящим является второй способ учета эпиполярных ограничений. При этом принимаются во внимание следующие условия. 1) Множество сопоставляемых точек = {(w,v)} и Q = {(w ,v )} представляет собой множество дискретных отсчётов на изображениях в окрестностях эпиполярных линий, определяемых неравенством (2.9). 2) В качестве сопоставляемого фрагмента изображения D(u0,v0) ДЛЯ точки (w0,v0) принимается область вокруг этой точки с заданными фиксированными размерами и формой. 3) Дескриптором для точки (w0,v0) является множество значений яркостей отсчётов из области D(u0,v0) В окрестности этой точки. 4) Критерий j(u0,v0,D(u0,VQ),uf,vf,iy(i/y),F) представляет собой меру сходства двух фрагментов, которая учитывает значения координат, интенсивностей отсчётов, а также близость точки к соответствующей эпиполярной линии.
В условиях 1 и 4 содержатся эпиполярные ограничения, задаваемые соотношением (2.9), а также накладывается требование близости к эпиполярной линии. Рассмотрим вычислительный алгоритм, соответствующий указанным условиям и исследованный автором в работе [42 ].
Предположим, что фундаментальная матрица вычислена по известным параметрам камер и измеренным (в моменты регистрации разноракурсных изображений) параметрам движения платформы, на которой базируются камеры. В качестве прототипа будем рассматривать широко используемый алгоритм для сопоставления произвольных изображений SimpleFlow [43]. Рассмотрим, как, при известной фундаментальной матрице, в критерий близости при сопоставлении точек могут быть добавлены указанные эпиполярные ограничения.
Обозначим координаты точек на первом изображении (w,v), а координаты соответствующих им точек на втором - (w + Aw,v + Av), где Aw, Av - относительные сдвиги координат w,v соответственно. Пусть I(u,v) и Г(и + Aw,v + Av) - функции распределения яркости отсчётов на этих изображениях. Задача состоит в поиске для каждой точки (w,v) на первом изображении соответствующей точки (w + Aw,v + Av) на втором изображении. В качестве меры близости между значениями яркостей отсчётов будем использовать квадратичную норму: e(u,v, Aw, Av) = /(w,v) -Г(и + Aw,v + Av). (2.30) При этом задача нахождения наиболее подходящих значений координат сдвигов u,v может быть сформулирована как задача минимизации некоторого критерия сходства: заданная область вокруг точки (M0,V0), a a(u,v) - весовая функция, задаваемая в указанной области с целью повышения качества сопоставления. Задача минимизации в данном случае может решаться путём перебора всех возможных значений сдвигов в заданной области.
При построении процедур сопоставления точек с учётом эпиполярных ограничений необходимо учитывать, по крайней мере, следующие факторы, оказывающие влияние на качество сопоставления: - проективные искажения; -неточность определения координат точек, принадлежащих эпиполярным линиям, вследствие дискретизации. С учётом этого зададим весовую функцию a(u,v) в (2.31) в виде произведения трёх коэффициентов: a(u,v) = wc Wd-wf, (2.32) где wc, wd - коэффициенты, учитывающие влияние проективных искажений, a wf - коэффициент, обеспечивающий близость точки к эпиполярной линии.
Эти коэффициенты также являются функциями (w,v) в области D(u0,v0), НО для упрощения мы опускаем эти обозначения. Будем строить процедуры формирования этих коэффициентов так, чтобы увеличение каждого из них было направлено на уменьшение влияния указанных выше искажающих факторов, то есть так, чтобы увеличение a(u,v) в целом, как правило, приводило к улучшению качества сопоставления. Для ослабления влияния проективных искажений коэффициенты wd, wc зададим в виде =exp{-(wo,vo)-(w,v)2}, (U,V)BD, (2.33) wc =exp{-/(Wo,v0)-/ (w,v)2}, (w,v)eZ . (2.34) Множитель (2.33) - wd повышает вес центральных значений.
Необходимость такого взвешивания объясняется следующим. Дело в том, что характер проективных искажений для соответствующих точек на разноракурсных изображениях может быть существенно различным, притом эти различия возрастают по мере удаления от центральных точек фрагментов. В предыдущем разделе мы рассматривали способ, в котором для снижения влияния этого фактора применялись фрагменты с размерами в направлении, перпендикулярном эпиполярной линии, равными одному межпиксельному расстоянию [34]. Введение коэффициента wd обеспечивает похожее компромиссное решение: не отказываясь от использования всей информации на фрагменте, мы фактически уменьшаем размер эффективной площади фрагмента.
Множитель (2.34) - wc выполняет ту же функцию, однако для этого используется информация о значениях яркостей отсчётов. Во-первых, это позволяет расширить эффективную область сопоставления фрагментов в ситуациях, когда функция распределения яркости в окрестности точки (w0,v0) достаточно гладкая. Во-вторых, снижение влияния проективных искажений с помощью только одного коэффициента wd обычно недостаточно, поскольку априорная информация о размерах области существенных проективных искажений, как правило, отсутствует.
Указанные весовые коэффициенты были предложены в работе [43], однако там отсутствовал коэффициент, отвечающий за соблюдение эпиполярных ограничений. Аналогичные весовые функции также рассматривались в работе [44], где они имели форму пирамиды. Кроме того, для учёта эпиполярных ограничений мы вводим также весовой коэффициент близости к эпиполярной линии. Процедура строится следующим образом.
Метод и вычислительный алгоритм последовательного формирования множества согласованных оценок
Рассмотрим информационную технологию формирования трёхмерной модели по разноракурсным изображениям. Схема информационной технологии приведена на рисунке 4.1. Жёсткий диск Разноракурсные изображения Предварительное сопоставление изображений Предварительный оптический поток Разноракурсные изображения Построение фундаментальной матрицы Фундаментальная матрица Сопоставление изображений с учётом фундаментальной матрицы
Схема информационной технологии Информационная технология включает в себя алгоритмы сопоставления точек на паре разноракурсных изображений, формирование карты диспарантности и трёхмерной цифровой модели местности. Предлагаемая технология состоит из четырёх этапов: предварительное сопоставление изображений; формирование фундаментальной матрицы; точное сопоставление изображений с учетом эпиполярных ограничений; формирование карты диспарантности и цифровой модели местности. Предварительное сопоставление изображений состоит в нахождении множества соответствующих точек, расположенных по полю изображения так, чтобы исключить линейную зависимость координат этих точек. Процедура строится в виде иерархической схемы вычислений. Для обоих видов формируется так называемая «пирамида изображений», которая представляет собой набор изображений, полученных уменьшением разрешения в два раза по обеим координатам. Таким образом, на N-ш уровне пирамиды формируется изображение, разрешение которого в 2N раз меньше исходного разрешения.
На первом шаге алгоритма обрабатывается изображение с наименьшим разрешением. При этом начальный сдвиг принимается равным нулю. На каждом последующем этапе «разрешение» полученного сдвига увеличивается вдвое. При этом значения координат сдвига также удваиваются. При поиске соответствия уточняется уже имеющийся сдвиг. Такая процедура выполняется до получения соответствий на исходных изображениях.
Нахождение фундаментальной матрицы. Метод и алгоритм её определения с использованием метода согласованной идентификации описан в главе 3. Для её определения используются соответствующие точки, найденные на предыдущем этапе. Основное требование на этом этапе помехоустойчивость, так как точность определения фундаментальной матрицы определяет успешность реализации последующих этапов технологии.
Окончательное сопоставление изображений. На этом этапе сопоставление выполняется с учётом эпиполярных ограничений так, как описано в разделе 2.3. Как и на первом этапе, сопоставление производится иерархически. Особенность состоит в том, что на каждой итерации иерархического сопоставления координаты, используемые для определения близости к эпиполярным линиям, приводятся к координатам исходных изображений.
Построение карт диспарантности и ЦММ. Как было сказано выше, данная технология может применяться в общем случае, когда априорная информация о параметрах камер отсутствует. Заметим, что при этом отсутствует возможность точного определения 3D-координат ЦММ. В этом случае технология завершается построением карты диспарантности, то есть формированием изображения, яркости пикселов которого соответствуют разностям координат соответствующих точек.
Заметим, что при наличии дополнительной информации о параметрах съёмки некоторые этапы могут быть исключены из описанной выше технологии. Например, если известны координаты точек геопривязки, первый этап предварительного сопоставления не требуется, а фундаментальная матрица может быть найдена исходя из этих координат. Аналогично, в случае, когда точно известны параметры камер (внутренние и внешние), необходимость в идентификации фундаментальной матрицы отсутствует, поскольку она может быть точно найдена на основе этих параметров.
Предложенная информационная технология была реализована в программном комплексе формирования трёхмерной модели местности по разноракурсным изображениям [77 ], [78 ], [79 ]. Языком для разработки программы был выбран C++. Программа написана в виде консольного приложения для операционной системы Windows.
Работа программного комплекса гарантируется на компьютере со следующими техническими характеристиками:
Результаты ЗО-реконструкции с использованием алгоритма поиска соответствий точкам на эпиполярных линиях
Также при отладке алгоритма для задач построения ЦМР разработан метод моделирования последовательности рельефов [81 ,82 ], который может быть использован для формирования последовательности похожих рельефов, постепенно переходя от одного заданного типа рельефа к другому. Формирование полей высот для каждого рельефа требует довольно больших вычислительных ресурсов, поэтому для тестирования предложенных методов и алгоритмов целесообразной представляется стратегия, заключающаяся в «пересчёте» следующего изображения по известному текущему.
Наиболее простым способом формирования таких последовательностей является построение дискретного ряда изображений на основе соотношений, полученных путём линейной интерполяции между заданными изображениями. Задавая в предложенном алгоритме различные значения параметров, можно получать последовательности рельефов с заданными свойствами, при этом вычислительная сложность повышается незначительно, поскольку большая часть вычислений может быть выполнена предварительно, при задании исходных опорных рельефов
Для сопоставления точек на эпиполярных линиях использовались следующие четыре вида описаний:
Векторы размерности 3x1, составленные из характеристик яркости и двухкомпонентных векторов градиентов для одного элементарного фрагмента, «охватывающего» заданную точку на эпиполярной линии. 2. Векторы размерности 9x1, составленные только из характеристик яркости девяти расположенных вдоль эпиполярной линии элементарных фрагментов.
Векторы 18x1, составленные из характеристик яркости и норм градиентов на том же числе элементарных фрагментов.
Векторы 27x1, составленные из характеристик яркости и двухкомпонентных векторов градиентов, содержащих в качестве компонентов градиенты по направлениям, повернутые на угол между эпиполярными прямыми.
Для удобства и оперативности формирования указанных дескрипторов на изображениях обоих видов осуществлялось предварительное формирование полей градиентов по двум направлениям с использованием следующих масок: а величины градиентов формировались путём суммирования градиентов по направлениям с равными весами. Для оценки меры близости соответствующих точек использовался равномерный критерий, определяемый как сумма абсолютных величин разностей соответствующих признаков.
На рисунке 4.4 приведены результаты реконструкции показанной выше ЗО-сцены, полученные с использованием указанных выше четырёх видов описаний соответственных точек. Нетрудно заметить, что, по мере увеличения размерности векторов описаний соответствующих точек, качество реконструкции сцены возрастает, а интенсивность шумов, связанных с установлением ошибочных соответствий, уменьшается.
Тем не менее, во всех экспериментах величина составного фрагмента, включающего лишь девять единичных квадратов, расположенных вдоль эпиполярных линий, остается небольшой. Повышение информативности составных фрагментов достигается увеличением числа рассчитываемых характеристик. Ясно, что это сопровождается увеличением объёма вычислений, в обмен на качество.
По полученным изображениям можно видеть, что при увеличении числа сопоставляемых фрагментов и выборе дополнительных дескрипторов число ошибочно сопоставленных точек уменьшается. Следует отметить, что свободные от точек участки под восстановленными объектами представляют собой ту часть сцены, которая была перекрыта этими объектами и отсутствовала на изображениях. Очевидно, что восстановление этой части сцены не представляется возможным без получения как минимум двух снимков, содержащих ее. Был проведён эксперимент по реконструкции сцены на основе трёх пар разноракурсных изображений с различным расположением эпиполюсов на изображениях (рисунок 4.5). В явном виде ректификация не проводилась, а соответствия на эпиполярных линиях искались прямо на изображениях. Такой подход позволил обрабатывать изображения единообразно для всех смоделированных положений камер. Можно отметить, что качество реконструкции значительно падает при приближении к эпиполюсу, что легко объясняется значительно возрастающими ошибками при малом параллаксе.
Целью эксперимента было показать, что восстановление сцены предложенным методом возможно вне зависимости от расположения эпиполюса на изображениях. Однако следует отметить, что качество восстановления сцены падает при приближении к эпиполюсу вследствие сильных искажений вблизи него. На рисунке 4.6 (а, б) приведены результаты реконструкции ЗО-сцены до и после обработки прореживающим фильтром. В качестве параметров для сопоставления были выбраны следующие значения: фильтром Целью эксперимента было исследование влияния прореживающей фильтрации на результат сопоставления. По рисунку можно видеть, что число ошибочно сопоставленных точек (они представляют собой «шум» на изображениях сцены) уменьшено, а отсутствующие участки фона восстановлены. При проведении экспериментов число ошибочно сопоставленных точек уменьшалось с 10-15% до 1-3% при отсутствии потерь верно сопоставленных точек. 4.4 Построение цифровой модели местности по разноракурсным изображениям при учёте эпиполярных ограничений весовыми коэффициентами штрафа
В процессе выполнения НИР для ГНП РКЦ «ЦСКБ-ПРОГРЕСС» была поставлена задача создания информационной технологии построения цифровой модели рельефа по разноракурсным изображениям. Предложенная в данной диссертации информационная технология была применена к космическим снимкам.
Были проведены экспериментальные исследования метода и алгоритма построения цифровой модели местности по космическим изображениям при их сопоставлении с учетом эпиполярных ограничений. На рисунках 4.7 (а, б) приведены исходные космические разноракурсные изображения, на которых проводились эксперименты. Эксперименты по проверке качества сопоставления проводились в виде двух этапов: предварительное сопоставление (фундаментальная матрица неизвестна) и окончательное сопоставление с учётом эпиполярных ограничений, задаваемых фундаментальной матрицей.
