Создание бесшовного изображения

Эта страница является черновиком статьи.

Введение

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

Область применения полученных данных постоянно расширяется, не ограничиваясь только специфическими задачами государственного уровня, а проникая в тесное взаимодействие практически со всеми сферами общественной жизни. Для управленческой и предпринимательской деятельности существенно необходимо знание о месторасположении для достижения наиболее быстрых и правильных решений. Исследование процессов движения земной коры, рельефа, анализ изменения погоды, прокладывание дорог и планирование строительства, предсказывание природных катастроф, проведение спасательных операций — все это трудно проводить в отсутствие надежных средств ориентирования. Уже невозможно представить жизнь людей без доступности использования подробных карт, панорам различных достопримечательностей и улиц городов, таких средств геопространственного ориентирования, как GPS и ГЛОНАСС. Портативные устройства с использованием карт местности с большим успехом используются для отслеживания положения и вычисления оптимального пути, встраиваются в смартфоны, коммуникаторы и автомобильные бортовые компьютеры.

В частности, в настоящее время осуществляется сбор большого количества данных ДЗЗ (Дистанционное зондирование Земли) с БПЛА (Беспилотный летательный аппарат) и самолетов. В большинстве случаев эти данные представляют собой кадровую съемку, представляющую собой набор отдельных фотографий. Иногда может предоставляться 3D модель рельефа, параметры камеры и глобальные координаты. Таким образом, среди многих направлений в эффективной обработке большого количества геопространственных данных возникает задача формирования мозаики — бесшовного единого изображения, полученного путем сопоставления перекрывающихся изображений, в то же самое время имеющего географическую привязку и максимальное совпадение с рельефом. При этом, встает задача поиска связующих точек изображений на маршруте и межмаршрутных изображений или просто создание панорам.

Существует библиотека GDAL (Geospatial Data Abstraction Library), которая используется многими системами по обработке геопространственных данных. Но сейчас в ней отсутствует алгоритм для полного автоматического создания мозаики, и остро стоит необходимость во включении в базовый функционал библиотеки такого алгоритма с реализацией пользовательского интерфейса в виде плагина для QuantumGIS (свободная кроссплатформенная геоинформационная система).

Постановка задачи

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

В процессе достижения поставленных целей возникают следующие задачи:

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

Вводимые ограничения:

1. Отсутствие удаления искажений, вызванных оптикой (дисторсии).
2. Применение аффинных преобразований.
3. Обработка только 2х изображений.
4. Использование метода градиентного спуска.

Проект участвует в программе Google Summer Of Code 2012, планируется дальнейшее развитие и интеграция в GDAL с реализацией пользовательского плагина.

Анализ задачи

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

Одним из самых трудоемких этапов является процесс нахождения и сопоставления связующих точек — характерных особенностей на изображениях («feature points»). Этот этап предлагается полностью автоматизировать, исключив участие человека, применив специализированные алгоритмы. Также предлагается оптимизировать параметры для трансформации фотографий в единую мозаику. При этом задача оптимизации в общем случае включает использование телеметрии, то необходимо учитывать также и эту информацию.

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

Анализ предметной области

Для геопространственных систем необходима так называемая ортофотомозаика — единое изображение, имеющее ортогональную проекцию. Для построения ортофото и выпрямления в соответствии с поверхностью Земли используются специальные наземные измерения, применяются алгоритмы триангуляции и стереозрения для восстановления рельефа по перекрывающимся изображениям — происходит создание так называемой DEM (Digital Elevation Model). В том числе применяется уравнивание сети точек по блоку изображений. Также производится учет данных телеметрии для географической привязки фотографий к местности при помощи GCP (Ground Control Points) — это точки, которые имеют координаты как на фотографии, так и соответствующие глобальные координаты на карте.

Анализ существующих решений

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

1. Сегментация изображений — разбиение изображений на области с примерно одинаковыми фотометрическими характеристиками.
2. Полученные области переводятся в аппроксимированные контурные фигуры.
3. Для каждой пары перекрывающихся изображений вычисляются коэффициенты корреляции определенным образом выбранного подмножества пар фигур.
4. С помощью оптимизированного переборного алгоритма, использующего рассчитанный коэффициент корреляции, а также дополнительные геометрические особенности расположения фигур, производится окончательное сопоставление фигур пары снимков и вычисление приблизительного соответствия точек на паре изображений.
5. Результаты этапа 4 поступают на вход иерархическому площадному коррелятору, с помощью которого полностью автоматически вычисляется необходимое число точек. После этого применяются различные критерии отбраковки, тем самым исключаются потенциально ошибочные точки.

Далее происходит расположение фотографий согласно полученным расчетам.

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

HUGIN Software

Данная программа позволяет производить множество сложных преобразований: создание мозаики из перекрывающихся изображений и особенно панорам, нахождение контрольных точек, HDR (High dynamic range imaging). Проект ориентирован на любительские и профессиональные цели и не предназначен для обработки геопространственной информации.

Ceres-Solver

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

Описание и структура алгоритма

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

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

Общая последовательность работы алгоритма предлагается следующей (некоторые пункты в данной работе не рассматриваются):

1. Исправление искажений, вызванное оптикой.
2. Компрессия изображений в случае сверхвысоких разрешений для ускорения оптимизации.
3. Нахождение связующих точек на изображениях.
4. Анализ и сопоставление полученных на предыдущем этапе точек, создание пар совпавших точек.
5. Использование первоначальной информации о местоположении и углах съемки для предварительной ориентации изображений и определения начальных параметров для проведения более быстрого и надежного способа оптимизации.
6. Расчет минимально необходимых параметров трансформации для каждой пары точек для достижения заданной степени погрешности конечной мозаики при помощи итеративного метода градиентного спуска.
7. Применение полученных параметров по отношению к точкам к целым изображениям и окончательное формирование единой мозаики.
8. Выравнивание яркости изображений и сглаживание швов.

В прототипе реализованы и используются пункты 3, 4, 6, 7, при этом пункты 3-4 - с использованием стандартных средств библиотеки компьютерного зрения OpenCV.

Нахождение связующих (особых) точек («feature points»)

Связующие (или особые, «feature») точки — это точки на изображении, которые отличаются от остальных по какому-либо признаку. Они называются связующими в связи с тем, что используются для связи и дальнейшего сопоставления фотографий друг с другом. Обычно для каждой точки оценивается некоторая уникальным образом характеризующая ее окрестность. Другими словами, такую окрестность какой-либо точки (и соответственно саму такую точку) можно отличить от других окрестностей остальных точек изображения. Существует достаточно много алгоритмов для поиска особых точек, например FAST corner detection, SIFT, SUSAN и т.д. В прототипе используется алгоритм SURF (Speeded up Robust Features).

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

Рис.1. Пример нахождения feature points на фотографии с БПЛА

Сопоставление и создание пар связующих точек

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

Одним из быстрых и надежных алгоритмов является алгоритм «ближайшего соседа» (NNS - Nearest Neighbor Search). Он позволяет в разы увеличить производительность по сравнению с методами простого перебора (brute force). В данной реализации используется специализированная библиотека FLANN (Fast Library for Approximate Nearest Neighbors) для сопоставления точек.

Рис.2. Результат сопоставления точек

Используемые преобразования

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

${\begin{array}{c}x'={a}_{0}+{a}_{1}\ast x+{a}_{2}\ast y\\y'={b}_{0}+{b}_{1}\ast x+{b}_{2}\ast y\end{array}}$	(1)

где $\left(x,y\right)$ – координаты точки до преобразования,

$\left(x',y'\right)$- преобразованные координаты

$\left({a}_{\mathrm {0,} }{a}_{\mathrm {1,} }{a}_{2}\right),\left({b}_{\mathrm {0,} }{b}_{\mathrm {1,} }{b}_{2}\right)$- параметры трансформации для 1-го и 2-го изображений соответственно.

Если представить в более удобном матричном виде, получим:

$\left({\begin{array}{c}x'\\y'\\1\end{array}}\right)=\left({\begin{array}{ccc}{a}_{1}&{a}_{2}&{a}_{0}\\{b}_{1}&{b}_{2}&{b}_{0}\\0&0&1\end{array}}\right)\times \left({\begin{array}{c}x\\y\\1\end{array}}\right)$	(2)

Аффинные преобразования позволяют осуществлять линейные искажения, такие как поворот, масштабирование, растяжение и параллельный перенос.

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

1. Осуществление поворота на угол$\alpha$
2. Масштабирование и растяжение.
3. Параллельный перенос.

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

Рис. Первоначальное внутреннее ориентирование изображений

Для осуществления преобразований введем вектор параметров $\theta$:

$\theta =\left(\alpha ,{s}_{x},{s}_{y},{\mathit {sk}}_{x},{\mathit {sk}}_{y},{x}_{\mathrm {0,} }{y}_{0}\right)$	(3)

$\alpha$- угол поворота,

${s}_{x},{s}_{y}$- масштабирование изображения,

${\mathit {sk}}_{x},{\mathit {sk}}_{y}$- искажение (растяжение и перекос),

${x}_{\mathrm {0,} }{y}_{0}$- координаты нового центра изображения относительно старой системы координат (параллельный перенос).

В данной работе будем применять такие аффинные преобразования:

1. Матрица поворота на угол альфа.

${M}_{\mathit {rotation}}=\left({\begin{array}{cc}\cos \alpha &-\sin \alpha \\\sin \alpha &\cos \alpha \end{array}}\right)$	(4)

1. Матрица для изменения размеров изображения и перекоса.

${M}_{\mathit {scaling}}=\left({\begin{array}{cc}{s}_{x}&{\mathit {sk}}_{y}\\{\mathit {sk}}_{x}&{s}_{y}\end{array}}\right)$	(5)

1. Матрица переноса изображения. Координаты новой системы координат в старой системе координат.

${M}_{\mathit {translation}}=\left({\begin{array}{c}{x}_{0}\\{y}_{0}\end{array}}\right)$	(6)

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

$\left({\begin{array}{c}x'\\y'\end{array}}\right)=\left({\begin{array}{cc}{s}_{x}&{\mathit {sk}}_{y}\\{\mathit {sk}}_{x}&{s}_{y}\end{array}}\right)\times \left(\left({\begin{array}{cc}\cos \alpha &-\sin \alpha \\\sin \alpha &\cos \alpha \end{array}}\right)\times \left({\begin{array}{c}x\\y\end{array}}\right)\right)-\left({\begin{array}{c}{x}_{0}\\{y}_{0}\end{array}}\right)={M}_{\mathit {Transform}}\times \left({\begin{array}{c}x\\y\end{array}}\right)$

(7)

где

$x,y$- пиксельные координаты точки на исходном изображении

$x',y'$- новые, преобразованные координаты точки

${M}_{\mathit {Transform}}$- сформированная матрица трансформации, отражающая порядок преобразования, имеет вид:

${M}_{\mathit {Transform}}=\left({\begin{array}{ccc}\left({s}_{x}\ast \cos \alpha +{\mathit {sk}}_{y}\ast \sin \alpha \right)&\left(-{s}_{x}\ast \sin \alpha +{\mathit {sk}}_{y}\ast \cos \alpha \right)&-{x}_{0}\\\left({\mathit {sk}}_{x}\ast \cos \alpha +{s}_{y}\ast \sin \alpha \right)&\left(-{\mathit {sk}}_{x}\ast \sin \alpha +{s}_{y}\ast \cos \alpha \right)&-{y}_{0}\\0&0&1\end{array}}\right)$	(8)

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

Использование данных телеметрии

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

1. Использование известного угла поворота$\alpha$, подстановка его в неизменном виде в начальные параметры преобразования.
2. Использование координат GPS, определяющих местоположение фотографии для расчета относительных параметров$\left({x}_{0},{y}_{0}\right)$во внутренней системе координат для параллельных переносов изображений на свои приближенные позиции.
3. Нахождение и сопоставление точек только в тех областях изображений, которые перекрываются, исходя из ориентирования во внутренней системе координат. Данный шаг может значительно увеличить производительность алгоритма.

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

${\begin{array}{c}\alpha \in \left\lbrack \alpha -\epsilon ;\alpha +\epsilon \right\rbrack \\{x}_{0}\in \left\lbrack {x}_{0}-{\xi }_{1};{x}_{0}+{\xi }_{1}\right\rbrack \\{y}_{0}\in \left\lbrack {y}_{0}-{\xi }_{2};{y}_{0}+{\xi }_{2}\right\rbrack \end{array}}$	(9)

где $\epsilon ,{\xi }_{\mathrm {1,} }{\xi }_{2}$- константы для ограничения соответствующих параметров.

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

Определение функции стоимости (Cost Function)

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

Рис.3. Величина ошибки (квадрат расстояния) между соответствующими точками

Тогда расстояние будет определяться выражением:

${d}^{2}={\left({p}_{1}'-{p}_{2}'\right)}^{2}={\left({x}_{1}'-{x}_{2}'\right)}^{2}+{\left({y}_{1}'-{y}_{2}'\right)}^{2}$	(10)

Или, если добавить матрицы преобразований (8):

${d}^{2}={\left({M}_{\mathit {Transform}}^{1}\times \left({x}_{\mathrm {1,} }{y}_{1}\right)-{M}_{\mathit {Transform}}^{2}\times \left({x}_{\mathrm {2,} }{y}_{2}\right)\right)}^{2}$	(11)

Так как расчет производится для нескольких пар точек, произведем суммирование по m — количеству найденных пар связующих точек.

Функция стоимости для 2х перекрывающихся изображений будет иметь вид:

$J\left(\theta \right)={\frac {1}{2\ast m}}\ast \sum _{i=1}^{m}\left({d}_{i}^{2}\right)={\frac {1}{2\ast m}}\ast \sum _{i=1}^{m}{\left({M}_{T}^{1}\times \left({x}_{1}^{\left(i\right)},{y}_{1}^{\left(i\right)}\right)-{M}_{T}^{2}\times \left({x}_{2}^{\left(i\right)},{y}_{2}^{\left(i\right)}\right)\right)}^{2}$	(12)

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

Введем дополнительное слагаемое для регулирования параметров, определяемое как сумму квадратов величин значений параметров:

$R={\frac {\lambda }{2\ast m}}\ast \sum _{j=1}^{N}{\theta }_{i}^{2}$	(13)

Где $\lambda$- параметр, влияющий на величину изменения параметров. Чем он больше, тем меньшие параметры будет находить алгоритм;

N – количество параметров трансформации (длина вектора$\theta$).

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

$J\left(\theta \right)={\frac {1}{2\ast m}}\ast \sum _{i=1}^{m}{\left({M}_{T}^{1}\times \left({x}_{1}^{\left(i\right)},{y}_{1}^{\left(i\right)}\right)-{M}_{T}^{2}\times \left({x}_{2}^{\left(i\right)},{y}_{2}^{\left(i\right)}\right)\right)}^{2}+{\frac {\lambda }{2\ast m}}\ast \sum _{j=1}^{N}{\theta }_{i}^{2}$	(14)

Метод градиентного спуска (Gradient descent method)

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

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

${\theta }_{j}={\theta }_{j}-\gamma \ast {\frac {\partial J\left(\theta \right)}{\partial {\theta }_{j}}}$	(15)

, где $\gamma$- параметр, влияющий на скорость сходимости алгоритма — чем он больше, тем за меньшее количество итераций метод достигнет оптимума.

Более подробно, применительно к нашим вычислениям, для вектора параметров необходимо вычислить следующие производные:

${\frac {\partial J\left(\theta \right)}{\partial \theta }}=\left({\begin{array}{c}{\frac {\partial J\left(\theta \right)}{\partial \alpha }};{\frac {\partial J\left(\theta \right)}{\partial {s}_{x}}};{\frac {\partial J\left(\theta \right)}{\partial {s}_{y}}};{\frac {\partial J\left(\theta \right)}{\partial {\mathit {sk}}_{x}}};{\frac {\partial J\left(\theta \right)}{\partial {\mathit {sk}}_{y}}};{\frac {\partial J\left(\theta \right)}{\partial {x}_{0}}};{\frac {\partial J\left(\theta \right)}{\partial {y}_{0}}}\end{array}}\right)$

(16)

Необходимо учитывать, что эти частные производные только для изменения параметров одного изображения. В случае двух и более изображений нам необходимо одновременно пересчитывать параметры для каждого изображения, таким образом число производных будет равно $k\times N$, где N — количество параметров, k — число изображений.

Так как в данном случае для двух фотографий число параметров возрастает до 14, на графике работу градиентного спуска сложно отобразить. Упрощенно метод можно проиллюстрировать на примере графика зависимости функции стоимости от вектора $\theta$ в случае 2х параметров:

Рис.4. Иллюстрация принципа работы градиентного спуска (Движение от большого значения ошибки к минимуму)

На вертикальной оси показана величина функции стоимости ($J\left({\theta }_{\mathrm {0,} }{\theta }_{1}\right)$, на горизонтальных — величины параметров${\theta }_{\mathrm {0,} }{\theta }_{1}$. Как видно из рисунка, алгоритм начинает свою работу с первоначальных параметров (${\theta }_{0}=\mathrm {0,7} ,{\theta }_{1}=\mathrm {0,3}$) и соответствующей им «вершины» поверхности (где величина функции стоимости является большой) и за несколько итераций достигает минимума («спускается» к минимуму) в точке со значениями${\theta }_{0}=\mathrm {0,1} ,{\theta }_{1}=\mathrm {0,4}$.

Дальнейшие улучшения

Так как представленный проект является прототипом (proof-of-concept), то существуют способы для ускорения и совершенствования работы алгоритма. Основным проблемным местом является метод градиентного спуска, который имеет тенденцию к очень медленному схождению и к нахождению локального минимума. В будущем предполагается реализация быстрого алгоритма Левенберга — Марквардта, направленного на решение задач о наименьших квадратах, а также, что является наиболее важным, переход от обычных аффинных преобразований к перспективным, которые позволят существенно повысить точность конечной мозаики и ее правдоподобность. Также представляется возможным расширение алгоритма для случая с большим количеством изображений.

Средства реализации

Основной алгоритм написан на языке Python в среде Eclipse с использованием плагина PyDev, тестирование проводилось на дистрибутиве Linux Xubuntu. Для использования вспомогательных алгоритмов применялась библиотека компьютерного зрения OpenCV и библиотека NumPy для проведения быстрых вычислений над матрицами.

Заключение

В рамках данной курсовой работы был разработан прототип (proof-of-concept) программы для создания бесшовной мозаики для случая 2х изображений. Были реализованы такие задачи, как:

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

Прототип успешно выполняет работу по сопоставлению изображений за достаточно небольшое время.

Дальнейшие планируемые изменения и дополнения для интеграции в GDAL в рамках GSoC 2012:

• Реализация алгоритмов поиска и сопоставления точек.
• Расширение алгоритма для большего числа изображений.
• Применение более совершенных методов по минимизации функции стоимости (Conjugate gradient, L-BFGS, алгоритм Левенберга-Марквардта или др.)
• Реализация пользовательского плагина к Quantum GIS.

Список литературы

1. Gary Bradski, Adrian Kaehler. Learning OpenCV. Computer Vision with the OpenCV Library- O'Reilly Media - September 2008 – 580 с.
2. Robert Laganière. Opencv 2 Computer Vision. Application Programming Cookbook - Packt Publishing – 298c.
3. Lengyel E. Mathematics for 3D Game Programming and Computer Graphics, Third Edition - 2011 – 546c.
4. Mark Lutz. Programming Python, 4th Edition - December 2010 – 1632c.
5. Безменов В.М. Фотограмметрия. Построение и уравнивание аналитической фототриангуляции — КГУ, Казань — 86с.
6. Документация по NumPy - (http://numpy.scipy.org/)
7. Andrew Ng. Курс онлайн лекций по машинному обучению — (http://ml-class.org)
8. А.Ю. Сечин, М.А. Дракин, А.С. Киселева. Беспилотные летательные аппараты: применение в целях аэрофотосъемки для картографирования. «Ракурс», Москва, Россия
9. Herbert Bay, Andreas Ess, Tinne Tuytelaars, and Luc Van Gool. Speeded-Up Robust Features (SURF) – 2008 – 14с.
10. Marcus ARTHUR, Barbados, Raid AL-TAHIR, and Dexter DAVIS. Rapid Processing of Unmanned Aerial Vehicles Imagery for Disaster Management.
11. U. Niethammer, S. Rothmund, U. Schwaderer, J. Zeman, M. Joswig. Open source image-processing tools for low-cost uav-based landslide investigations – 2011

Приложение A

Приложение Б

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