СПОСОБ АВТОМАТИЧЕСКОЙ КОМПОНОВКИ ЛАНДШАФТНЫХ ПАНОРАМНЫХ ИЗОБРАЖЕНИЙ
METHOD FOR AUTOMATIC LINKING PANORAMIC LANDSCAPE IMAGES

Изобретение относится к области фотографии, более конкретно к редактированию цифровых изображений, и может найти наиболее широкое применение в задачах обработки и печати панорамных фотографий.
Цифровое представление изображения открывает новые возможности в области фотографии. При этом одной из особенностей цифровой фотографии является возможность объединения небольших снимков в большую панораму. В этом случае технические параметры цифровых камер приближаются к параметрам человеческого панорамного восприятия изображений. Построение панорамного изображения включает в себя три основных этапа: выравнивание изображений и установление соответствий, коррекция проективных искажений, преобразования цвета и получение результирующей панорамы. Выравнивание изображений может быть затруднено, если в процессе фотографирования изменяется сцена. Согласование цветов - дополнительный шаг, который может быть выполнен для улучшения качества результата.
Способам получения панорамных изображений посвящено ряд исследований. Многие современные фотокамеры сопровождаются программным обеспечением, в которое входят программы построения панорамных изображений. Геометрия проблемы хорошо изучена и заключается в получении оценки матрицы гомографии размерности 3×3 для каждого изображения. Однако этот процесс оценки нуждается в инициализации. В коммерческих приложениях, как правило, в этих целях используется интерактивный интерфейс пользователя.
Например, программное обеспечение Photo Stitch, поставляемое с цифровыми камерами Canon, требует горизонтальной или вертикальной стыковки изображений. Компоновщик REALVIZ снабжен пользовательским интерфейсом, который обеспечивает грубое позиционирование изображения с помощью мышки перед началом автоматической сшивки панорамы. В научной литературе методы автоматического поиска сопряженных точек (установления соответствий) и оценки геометрии условно разделяются на две группы: прямые методы и методы, основанные на использовании характерных особенностей. При этом вторая группа методов предусматривает предварительное установление соответствия между точками, линиями и иными геометрическими фигурами.
Обычно на первом этапе определяют углы с помощью алгоритма Харриса [1] и затем используют нормализованную меру корреляционного сходства локальных интенсивностей для установления соответствий между найденными углами.
Прямые методы итеративно оценивают параметры камеры, посредством минимизации функции ошибки, основанной на разнице интенсивности в области перекрытия изображений. Преимущество прямых методов состоит в том, что они оперируют всем объемом данных и поэтому могут обеспечивать очень высокую точность совмещения, но устойчивость их работы определяется в первую очередь предположением об одинаковой яркости всех изображений. Эти методы требуют также инициализации итерационного процесса.
Однако ни один из этих методов не является устойчивым к изменению масштаба, освещения или наличию шумов.
В последнее время значительный прогресс достигнут в использовании инвариантных особенностей в распознавании образов и поиске сопряженных точек. Инвариантные особенности являются более надежными, чем традиционные методы, такие как корреляционный поиск и углы Харриса. Углы Харриса не являются инвариантными к изменению масштаба, а кросс-корреляция не инвариантна к вращению. В то же время, инвариантные особенности обладают устойчивостью к этим преобразованиям. Предложенные Лоу [2, 3] SIFT-инварианты геометрически инвариантны к преобразованию подобия и также инвариантны к аффинному изменению интенсивности.
Сшивка панорамных фотографий является по существу достаточно сложной задачей. Исходные фотографии могут иметь произвольную природу. Корректная оценка проективных искажений - важный шаг, который сложно выполнить, например, когда на изображении присутствуют обширные области одинаковой яркости или периодической текстуры. В таких ситуациях затруднительно удалять неправильно установленные соответствия. Кроме того, установленные соответствия могут относиться не ко всем частям изображений, что повлечет за собой неточную оценку проективных искажений.
Известные решения проблемы построения панорамных изображений, описанные ниже, не рассматривают таких ситуаций и не предлагают никаких специальных способов для их решения. Таким образом, они могут работать нестабильно в случае возникновения одной из указанных ситуаций.
Среди публикаций, посвященных проблеме сшивки нескольких фрагментов в один панорамный снимок, следует, в первую очередь, отметить следующие:
С.Harris (1992). “Geometry from visual motion”, in A. Blake and A. Yuille: Active Vision. MIT Press, Cambridge MA. [1]; M. Brown and D. Lowe. Invariant Features from Interest Point Groups. // Proceedings of the 13th British Machine Vision Conference, pages 253-262, Cardiff, 2002 [2]; D. Lowe. Object Recognition from Local Scale-Invariant Features. // Proceedings of the International Conference on Computer Vision, pages 1150-1157, Corfu, Greece, September 1999 [3]; H. Moravec (1980). “Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover”. Tech Report CMU-RI-TR-3 Carnegie-Mellon University, Robotics Institute [4]; C. Harris and M. Stephens (1988). “A combined corner and edge detector”. Proceedings of the 4th Alvey Vision Conference: pages 147-151 [5]; J. Shi and C. Tomasi (June 1994). “Good Features to Track,”. 9th IEEE Conference on Computer Vision and Pattern Recognition, Springer [6]; H. Wang and M. Brady (1995). “Real-time corner detection algorithm for motion estimation.”. Image and Vision Computing 13: 695-703 [7]; R.I.Hartley and A.Zisserman. Multiple View Geometry // Computer Vision. Cambridge University Press, ISBN: 0521623049, 2000 [8]; P.Torr and A.Zisserman. Feature Based Methods for Structure and Motion Estimation // B.Triggs, A.Zisserman, and R.Szeliski, editors, Vision Algorithms: Theory and Practice, number 1883. LNCS, pages 278-294. Springer-Verlag, Corfu, Greece, September 1999 [9]; M.Irani and P.Anandan. About Direct Methods. // B.Triggs, A.Zisserman, and R.Szeliski, editors, Vision Algorithms: Theory and Practice, number 1883. LNCS, pages 267-277. Springer-Verlag, Corfu, Greece, September 1999 [10]; Radke R. Ramadge P. Echigo T. Iisaku S. Efficiently estimating projective transformations // Proceedings International Conference on Image Processing 2000. Vancouver. Canada, 2000. - vol.1.- p 232-235 [11]; Capel D., Zisserman A. Computer vision applied to super resolution // IEEE Signal Processing Magazine, 2003.- May.- p.75-86 [12]; Capel D. P. Image Mosaicing and Super-resolution. PhD thesis, University of Oxford, 2001 [13].
Известны также некоторые запатентованные решения в этой области. Так в патенте США №7271822 [14] предлагаются системы и способы для построения мозаичных изображений в принтере, чтобы сформировать единое составное изображение без швов. Использование нескольких лазерных излучателей и нескольких сканирующих объективов с одним или более сканеров и различные методы сшивки изображений позволяют получить более качественное скомпонованное бесшовное изображение, по сравнению с более ранними принтерами, использующими один лазерный источник света и один сканирующий объектив. К положительным качествам такого подхода можно отнести возможность получения более широкоформатного изображения, более мелкозернистого изображения, более дешевой стоимости отпечатка и более компактных размеров принтера. Однако используемые системы отличаются высокой сложностью конструкции, что ограничивает сферу их применении.
Альтернативные подходы к решению рассматриваемой проблемы описаны в других патентах США, в частности, в патентах №№6411742 [15], 7095905 [16], 7006111 [17], 7197192 [18].
Наиболее близким по своим признакам к заявляемому изобретению является техническое решение, описанное в патенте США №6486908 [19], в котором предложены способ построения сферических панорам для систем виртуальной реальности, основанных на использовании изображений. Такие сферические панорамы могут быть повернуты в любом желаемом направлении (360°) с использованием любого подходящего трехмерного браузера или иной программы для просмотра. Метод и система также включают вычисление количества необходимых фотографий, а также азимутальных углов и точки съемки для каждой фотографии для построения сферической карты, отражающей сферическую панораму.
Задача, на решение которой направлено заявляемое изобретение, состоит в том, чтобы разработать способ автоматической сшивки заснятой по частям панорамы для получения полномасштабной ландшафтной панорамы путем компенсации проективных искажений.
Технический результат достигнут за счет того, что предложен новый способ автоматического построения ландшафтной панорамы из отдельных фотографий, заключающийся в том, что сшивку фотографий выполняют путем формирования квадратной решетки, установления соответствий для узлов решетки, удаления неправильных соответствий с использованием процедуры верификации, основанной на определении изначального расположения узлов решетки, оценки проективных преобразований между всеми изображениями, и последующего формирования глобального изображения с помощью процедуры адаптивного смешивания.
Камера с идеализированным точечным отверстием формирует изображения перспективным проектированием. Наиболее подходящей моделью для описания геометрических искажений, возникающих между снимками, полученными пользователем, который находится в одной точке пространства, являются проективные преобразования. Связь между декартовыми координатами соответствующих точек [х,у] и [х',у'] на двух плоских снимках описывается проективными геометрическими преобразованиями:
где
и
33=1
Матрицы А и В являются прямой и обратной матрицами проективного преобразования, k - нормирующая константа, выбираемая из условия b. Проективное преобразование взаимно однозначно, если detA≠0.
При проективных преобразованиях изображения трансформируются существенным образом: изменяются расстояния и углы, нарушается параллельность линий и т.п. Поэтому традиционные методы верификации сопряженных точек утрачивают свою устойчивость. Вместе с тем в проективной геометрии определены свойства объектов, которые остаются неизменными при проективных искажениях. В частности, при проективных преобразованиях прямые остаются прямыми и две прямые пересекаются в одной точке. Данный способ использует эти особенности для верификации установленных соответствий.
Для лучшего понимания существа заявляемого изобретения далее приводится его детальное описание с привлечением графических материалов.
Фиг.1. Схема процесса сшивки панорамы.
Фиг.2. Схема поиска соответствий (сопряженных точек).
Фиг.3. Схема процесса верификации соответствий.
Фиг.4 (вид 4.1). Первое изображение, на котором точки заданы на квадратной решетке.
(вид 4.2). Второе изображение, на котором найдены точки первого столбца корреляционно-экстремальным методом.
Фиг.5. Направления, связывающие сопряженные точки в столбце (помечены сплошными стрелками).
Фиг.6. Допустимые диапазоны изменения углов (помечены пунктирными стрелками).
Фиг.7. Пример успешной сшивки ландшафтной панорамы (без обрезания краев).
Фиг.8. Пример успешной сшивки ландшафтной панорамы (с обрезанием краев).
На шаге 100 на первом изображении задаются точки на квадратной решетке с предопределенным числом узлов и расстоянием между ними. Блок 101 осуществляет поиск сопряженных точек на втором изображении. Сопряженными точками являются проекции одной физической точки сцены на различные изображения. Поиск сопряженных точек осуществляется методом сравнения шаблонов. Этот алгоритм представлен на Фиг.2. Сопряженные точки, найденные на этом шаге, могут содержать ошибки. Поэтому на шаге 102 выполняется верификация найденных точек. Этот шаг представлен в деталях на Фиг.3. Блок 103 оценивает параметры проективного преобразования, которое переводит точки на одном изображении в соответствующие точки на втором изображении. Для оценки параметров проективных искажений используются все найденные и верифицированные сопряженные точки. Параметры проективных искажений получаются в результате решения переопределенной системы уравнений, линейных относительно коэффициентов матрицы проективного преобразования, которые были описаны выше. Система выглядит следующим образом:
i
i
i
i
где [x, y] и [x', y']  - координаты верифицированных сопряженных точек на первом и втором изображениях. На шаге 104 вычисляется размер панорамного изображения. Его можно вычислить, отобразив все изображения в систему координат центрального изображения. Когда размер изображения вычислен, блок 105 отображает локальные фрагменты в глобальную панораму, используя процедуру блендирования.
Фиг.2 описывает процесс поиска соответствий (сопряженных точек). На шаге 200 задаются точки на квадратной решетке для первого изображения, и создается список сопряженных точек. Блок 201 создает квадратные шаблоны предопределенного размера вокруг каждой точки из списка. Блок 202 вычисляет математические ожидания и среднеквадратические отклонения каждого из шаблонов. В блоке 203 из списка исключаются точки (как неинформативные), среднеквадратическое отклонение шаблонов которых меньше предопределенного порога. На шаге 204 берется из списка сопряженная точка, затем блок 205 вычисляет карту нормированной корреляции функции, двигая шаблон по части второго изображения и вычисляя нормированную корреляцию в каждой точке. Блок 206 ищет максимум на карте нормированной корреляционной функции; на шаге 207 координаты исходной точки и найденного максимума добавляются в список соответствий.
Фиг.3 демонстрирует процесс верификации найденных сопряженных точек. Легко увидеть, что структура размещения сопряженных точек может быть нарушена из-за ошибок корреляционно-экстремального метода (см. Фиг.4). В связи с этим возникает задача верификации сопряженных точек. Алгоритм верификации сопряженных точек использует свойство проективных преобразований - прямые линии остаются прямыми. Поскольку при поиске сопряженных точек на втором изображении известны строка и столбец эталонной сетки, в которые они входят (а значит и прямые, которым они должны принадлежать), то становится возможной проверка каждой из точек на предмет принадлежности определенной прямой. Верификация выполняется в несколько этапов. На первом этапе осуществляется верификация по столбцам. Блок 301 создает список точек второго изображения, принадлежащих соответствующему столбцу квадратной решетки (см. Фиг.4. 1). Блок 302 определяет принадлежность этих точек прямой в соответствии со следующим алгоритмом:
- для каждой пары точек в столбце рассчитывается вектор направления (угол) (см. Фиг.5);
- для каждого рассчитанного направления задается допустимый диапазон изменения углов, величина которого предопределена (см. Фиг.6);
- каждый вектор направления в столбце проверяется на предмет попадания в каждый из допустимых диапазонов;
- подсчитывается количество векторов, принадлежащих каждому из диапазонов;
- за истинное направление прямой принимается то направление, диапазону которого принадлежит наибольшее количество векторов. На Фиг.6 за истинное направление принято направление, связывающее точки 2 и 3.
Блок 303 исключает из списка точки, не принадлежащие прямой (на Фиг.6 точки 1 и 7 удалены). Этот процесс верификации выполняют для всех столбцов решетки. Аналогичным образом работают блоки 304…306, проверяющие принадлежность сопряженных точек строкам решетки. Блок 307 проверяет каждую точку второго изображения на правильность ее положения в столбце/строке (поскольку изначально известно ее порядковое место в столбце/строке). Неправильно расположенные точки исключаются из списка. Этот блок предназначен для исключения ситуации, когда нарушается последовательность строк или столбцов в целом, возникающей тогда, когда на изображении много параллельных структур, похожих друг на друга (например, окна на домах).
Затем, блок 308 оценивает параметры проективного преобразования. На этапе 309 отображают координаты сопряженных точек второго изображения в координаты первого. Это выполняется путем использования следующей формулы:
где N - это число верифицированных точек соответствия.
В блоке 310 вычисляется среднеквадратическая ошибка совмещения сопряженных точек
Если ошибка совмещения  больше предопределенного порога (условие 1) и число сопряженных точек больше предопределенного числа (условие 2), то в блоке 311 вычисляется ошибка совмещения для каждой пары сопряженных точек
Далее в блоке 312 из списка сопряженных точек удаляется точка с максимальной ошибкой совмещения . Эту процедуру повторяют до тех пор, пока условия 1 и 2 выполняются.
Практическое применение заявляемый способ может найти в сфере цифровой печати, как промышленной, так и художественной.