Задача привязки изображений для некоторых

УДК 621.391 ЗАДАЧА ПРИВЯЗКИ ИЗОБРАЖЕНИЙ ДЛЯ НЕКОТОРЫХ СЛУЧАЕВ РАКУРСНОЙ ФОТОСЪЕМКИ © 2008 г. , , Москва, ФГУП ГосНИИАС Поступила в редакцию 15.02.08 г., после доработки 07.05.08 г. Рассматривается современное состояние задачи привязки цифровых изображений. Привязка изображений предполагает процесс совмещения и наложение двух или более изображений, полученных в разное время, с различных ракурсов и, может быть, от разных сенсоров. При этом должно достигаться наиболее точное геометрическое соответствие. Детально рассмотрены основные этапы решения задачи привязки. Анализируются сильные стороны и недостатки решений, предложенных в этой области различными исследователями. Использованы наиболее удачные, с точки зрения авторов, из разработанных ранее решений, а также предложены оригинальные решения некоторых задач. Для надежного контроля и отбраковки неверно сопоставленных точек авторами разработаны оригинальные алгоритмы метрической фильтрации и итеративной стохастической фильтрации SwarmSAC. Целью статьи является разработка и представление методики отождествления и привязки фрагментов цифровых изображений, полученных при очень широком варьировании условий съемки. Введение. В современных технических системах, основанных на использовании принципов машинного зрения, возможность эффективного решения целого ряда прикладных задач связана с созданием устойчивых и быстрых алгоритмов автоматической идентификации и привязки изображений, полученных в разное время, с различных ракурсов и от разных фотокамер. Как правило, задача привязки изображений возникает во всех случаях, когда конечный результат получается в итоге использования разных источников данных, как, например, при слиянии данных, анализе данных от сенсоров разных спектральных диапазонов, детектировании изменений пространственной сцены во времени, синтезе изображений повышенного разрешения и т.п. В настоящей работе детально рассматривается решение задачи привязки для случаев, когда цифровые изображения получаются в результате съемки трехмерных объектов или пространственных сцен с разных ракурсов. Как правило, рассматривают отдельно случаи дальней, средней и ближней съемки. При дальней съемке расстояние до объекта значительно превышает базис съемки, для ближней съемки характерны значения базиса, сравнимые или даже превышающие расстояние до объекта. Случай дальней съемки детально рассмотрен в . Случай ближней съемки характеризуется не только отличием масштабов изображения и углов поворота, здесь могут возникать заметные ракурсные искажения локальных фрагментов, что значительно усложняет задачу их идентификации. Решение задачи идентификации и координатной привязки изображений означает возможность решения многих интересных практических задач. Реализация такого решения связана с созданием ряда алгоритмов, поз воляющих автоматически идентифицировать объект или фрагмент местности на основе изображений, полученных в результате авиационной или космической съемки, а также при необходимости осуществить высокоточную координатную привязку фрагмента по ортофотоплану местности. С другой стороны, она позволяет автоматически строить мозаики из снимков для формирования обзорных панорам, создавать пространственные модели архитектурных объектов и скульптуры и т.п. При постановке задачи автоматической идентификации предполагается, что существует исходный эталон двумерного информационного поля и на основе некоторого численного алгоритма производится сопоставление этого эталона и текущего цифрового изображения. В большинстве реализованных алгоритмов такого типа текущие данные представляют собой фрагмент растрового изображения, яркостные свойства, масштаб и геометрия которого незначительно отличаются от масштаба и геометрии эталонного изображения. Однако в реальных задачах оба эти условия, как правило, нарушаются. Поэтому необходима разработка и реализация алгоритмов, функционирующих устойчиво на изображениях, полученных в различных масштабах и с различных ракурсов. Возможны два принципиально разных подхода к решению данной задачи: исследовать возможности трансформирования растровых эталонов для приведения их к масштабу и геометрии идентифицируемого изображения на основе некоторых априорных данных об источниках формирования изображений; разработать устойчивые алгоритмы идентификации, использующие в качестве исходных не растровые, а векторные признаки — точки, линии, области и пространственные соотношения между ними. Алгоритмы этого класса характеризуются более высокой устойчивостью к различным геометрическим и радиометрическим искажениям, но являются более наукоемкими, так как требуют предварительной обработки изображений и последующего анализа на уровне задач искусственного интеллекта. Данная работа целиком посвящена разработке и реализации второго подхода. Задача нахождения соответствий между изображениями включает в себя четыре этапа. На первом этапе необходимо выявить особенности (точки, углы, контуры, области). На втором этапе определяются численные характеристики особенностей: это могут быть как чисто геометрические параметры (площадь, периметр, кривизна границы), так и параметры, учитывающие фотометрические характеристики. На третьем этапе особенности со схожими численными характеристиками на парах изображений ставятся друг другу в соответствие (привязываются). На четвертом этапе производится отбраковка неверно найденных соответствий на основе анализа пространственных отношений между особенностями. В данной работе исследуется один тип особенностей — характерные точки. В первом разделе рассматривается метод обнаружения характерных точек изображения (так называемых «точек интереса»), основанный на производных яркости. Во втором разделе описана процедура определения численных характеристик точек интереса — дескрипторов, не меняющихся при простых геометрических и фотометрических трансформациях изображения. В третьем разделе изучается вопрос о поиске соответствий путем сравнения дескрипторов точек. Четвертый раздел посвящен отбраковке (фильтрации) неверно найденных соответствий, основанной на использовании геометрической модели расположения точек. Наконец, пятый раздел содержит описание базы изображений, на которой тестировались алгоритмы, а также основные результаты исследования. 1. Обнаружение характерных точек. Выделение характерных точек на изображении является начальным и ключевым этапом в задаче отождествления, от которого зависит результат работы всего алгоритма. Основное достоинство использования характерных точек для задач обнаружения — простота и скорость выделения (по сравнению с другими характерными признаками). Кроме того, на изображениях не всегда удается выделить иные характерные черты (четкие контуры или области), в то время как локальные особенности в подавляющем большинстве случаев выделить можно. Исследования возможности привязки изображений с использованием набора локальных точек ин тереса начались в 1981г. с работы Моравека по стереопривязке с использованием детектора углов. Автор рассмотрел изменение яркости небольшого фрагмента вокруг интересующей точки при сдвиге фрагмента на один пиксель в восьми направлениях. Точки, в которых такое изменение максимально, считаются углами. Детектор Моравека очень быстр, но он не изотропен, поскольку используется всего восемь направлений сдвига для анализа изменения яркости фрагмента. Как следствие решение о том, является ли точка углом или нет, зависит от ориентации снимка и может меняться. В дальнейшем работы Моравека были продолжены Ферстнером . Оба алгоритма поиска углов основаны на исследовании свойств так называемой матрицы локальной структуры M wxy,() I x 2 I x I y I x I y I y 2 , xy, ? = где I(x, y) — функция яркости в точке (x, y), I x и I y значения производных в этой точке, а w(x, y) функция окна (прямоугольного или Гауссова). Использование производных яркости является логичным продолжением идеи Моравека об исследовании изменений яркости по множеству направлений. Ферстнер предложил вести поиск локальных максимумов величины R detM trM ————— .= Здесь для нахождения характерных точек мы использовали метод Харриса . Как и другие детекторы углов, он находит не собственно углы, а любые участки изображения, в которых имеется большое изменение градиента во всех направлениях при заданном масштабе. Метод изящен и достаточно быстр, поскольку сводится к дифференцированию яркости изображения, суммированию производных яркости в локальной окрестности каждой точки и нахождению «меры отклика угла» R = det M — k(tr M) 2 , где k — эмпирически найденный параметр порядка 0.04-0.06. При отрицательном отклике R < 0 точка (x, y) классифицируется как попавшая на край; при отклике, близком к нулю, точка считается попавшей в "плоскую" область. При больших R > 0 считается, что точка (x, y) является углом, так как в ней яркость сильно меняется во всех направлениях. Детектор Харриса инвариантен к вращению и сдвигу изображения, а также к сдвигу и равномерному линейному изменению яркости. На практике для нахождения характерных точек детектором Харриса необходимо сначала в каждой точке изображения вычислить меру R, затем рассмотреть те точки, в которых мера отклика угла больше некоторого положительного порога, и сре ди них найти локальные максимумы в окне заданного размера. Стремясь к равномерному покрытию изображений найденными углами, авторами экспериментально было обнаружено, что на изображениях 1000 ? 1000 пикселей размер окна, равный 20 пикселям, оптимален для поиска локальных максимумов меры отклика угла. 2. Вычисление дескрипторов точек. Как было отмечено выше, корреляция, которая применяется для сравнения фрагментов изображений при малых искажениях, не дает устойчивых результатов в случае ракурсных искажений и масштабирования. Поэтому необходимо описать локальные окрестности характерных точек такими параметрами (дескрипторами), которые бы мало менялись при различных геометрических и фотометрических преобразованиях изображения. Наиболее ч сто для этого используются инварианты Ху , основанные на теории алгебраических инвариантов. Часто также применяются инварианты на основе преобразования Фурье или Фурье — Меллина . В данной работе в качестве дескрипторов точек были приняты инварианты Флюссера , которые представляют собой комплексные моменты + ? + ? c pq xi y+() p xi y–() q fxy,() xdy ,d ?– ? = ? ?– где i — мнимая единица, f(x, y) — яркость изображения в точке. В дискретном случае интегрирование заменяется на суммирование. Всего существует 11 инвариантов ? 1 = c 11 , ? 2 = c 21 c 12 , ? 3 Re c 20 c 12 2 () , ? 4 Im c 20 c 12 2 () ,== ? 5 Re c 30 c 12 3 () , ? 6 Im c 30 c 12 3 () , ? 7 c 22 , ? 8 Re c 31 c 12 2 () ,== ? 9 Im c 31 c 12 2 () , ? 10 Im c 40 c 12 4 () , ? 11 Im c 40 c 12 4 () .= Для каждого фрагмента яркость изображения нормализуется путем вычитания среднего значения яркости по фрагменту и деления результата на среднеквадратическое отклонение яркости. Такая процедура не только позволяет компенсировать эффект от разной освещенности, но и повышает численную устойчивость вычислений инвариантов. Для изображений, использованных в данной работе, опытным путем было найдено, что восьми инвариантов достаточно для получения необходимого числа правильно сопоставленных точек. Отдельного рассмотрения требует вопрос, по какой области вычислять инварианты. Как правило, в случае малых ракурсных искажений инварианты рассчитываются по круглой окрестности характерной точки. Однако в случае больших ракурсных искажений в круглую окрестность одной и той же точки на паре изображений могут попасть разные элементы изображения. Учет и частичная компенсация геометрических искажений производится следующим образом. По круглой окрестности характерной точки подсчитываются геометрические моменты с учетом яркости m 11 1 S — fxy,() xx –() yy –() , ? R ? = m 20 1 S — fxy,() xx –() 2 , ? R ? = m 02 1 S — fxy,() yy –() 2 , ? R ? = где S = — сумма яркости по круглой fxy,() ? R ? окрестности ? R точки радиуса R. По геометрическим моментам подсчитываются длины полуосей эллипса с центром в характерной точке, направление поворота которого зависит от яркостных характеристик изображения в его окрестности xy,() a 2 m 20 m 02 D++() ,= b 2 m 20 m 02 D–+() ,= ? 1 2 —2m 11 m 20 m 02 – ———————?? ?? ,arctg= m 20 m 02 –() 2 4m 11 2 +. где D = Далее, зная размеры полуосей для каждого эллипса, приводим все эллипсы к окружностям одинакового радиуса. Это делается путем поворота фрагмента изображения, содержащегося внутри эллипса и его масштабирования вдоль основных осей эллипса . При масштабировании происходит перевыборка (resampling) изображения с использованием билинейной интерполяции. Как показывает опыт, использование других более совершенных методов интерполяции, таких как бикубическая интерполяция Кейса или Б-сплайнов, практически не влияет на точность работы алгоритма сравнения точек. 3. Сравнение и поиск соответствий. Вычислив наборы инвариантов для пары изображений, необходимо их сравнить, чтобы найти максимально схожие фрагменты. В данной работе мы использовали расстояние Махаланобиса. Оно представляет собой аналог расстояния между векторами в евклидовом пространстве, взвешенного матрицей, обратной к матрице ковариации d xy,() xy –() T C 1– xy –() ,= A 3 A 1 A 1 A 2 A N Рис. 1. Распределение точечных особенностей на изображении где x и y — векторы инвариантов сравниваемых фрагментов изображений, C — матрица ковариации C ij = cov(X i , X j ) = E, X k — вектор значений k-го инварианта для всех рассматриваемых точек в обоих изображениях, µ k = = E(X k ) — среднее значение (математическое ожидание) k-го инварианта. Преимущество расстояния Махаланобиса перед евклидовым заключается в том, что инварианты, имеющие различный порядок величины, взвешиваются пропорционально их масштабу. В качестве дополнительного критерия для нахождения соответствий мы использовали характеристики эллиптических окрестностей вокруг точек. Отношение длин малой и большой полуосей k = b/а, называемое коэффициентом сжатия, определяет вытянутость эллипса. При изменении масштаба изображения, а также при его сдвиге или вращении эта характеристика неизменна. При изменении ракурса она колеблется в определенных пределах, которые можно вычислить экспериментально на базе изображений. Далее всюду считается, что две области из разных изображений не могут образовывать пару (т.е. не могут соответствовать друг другу), если их коэффициенты сжатия отличаются друг от друга более чем в 1.5-2.0 раза. Пусть фрагменты L i и R j , находящихся на первом и втором изображении, наиболее близки в пространстве параметров. Будем считать, что фрагменты образуют пару, если одновременно выполняется два условия: для L i не существует фрагмента во втором изображении «ближе», чем R j , и то же верно для R j . В реальных задачах высокая схожесть не всегда означает, что фрагмент-аналог действительно является искомой парой. Поэтому обычно необходимо рассматривать набор из нескольких ближайших аналогов и, исходя