Содержание к диссертации
Введение
1. Обзор методов и алгоритмов компьютерного зрения, сопоставления изображений, визуальной навигации 12
1.1 Математические основы компьютерного зрения, задача калибровки камеры 12
1.1.1 Математическая модель цифровой камеры, дисторсия оптических объективов 12
1.1.2 Калибровка камеры 16
1.1.3 Математические основы стереозрения 19
1.1.4 Алгоритм Левенберга-Марквардта 29
1.2 Методы выделения и сопоставления особенностей на изображениях 30
1.2.1 Методы выделения особенностей 32
1.2.2 Методы сопоставления особенностей 35
1.3 Методы навигации беспилотных аппаратов по изображениям 39
Выводы по 1 главе 48
2. Алгоритм сопоставления снимков сцены с фрагментарным многомасштабным представлением эталонных изображений 52
2.1 Модель земного эллипсоида и связанные с ним системы координат 52
2.2 Фрагментарное многомасштабное представление эталонного изображения 59
2.2.1 Преобразование координат пикселей между слоями пирамиды изображений 63
2.2.2 Процедура подготовки исходных данных для решения задачи сопоставления 66
2.3 Сужение области поиска особых точек на фрагментарном представлении эталонных изображений 67
2.4 Алгоритмы сопоставления особых точек, найденных на кадре видеоряда и на фрагментарном представлении эталонных изображений 74
Выводы по 2 главе 80
3. Метод взаимной привязки видеоснимков сцены на основе поиска опорных точек с применением вейвлетов Габора 81
3.1 Вейвлеты Габора 82
3.2 Подготовка данных, связанных с опорными точками 83
3.3 Метод поиска опорных точек на видеокадре с применением вейвлетов Габора
3.3.1 Использование билинейной интерполяции для повышения точности локализации опорных точек 94
3.3.2 Обеспечение инвариантности к преобразованиям яркости изображений 96
3.3.3 Оптимизация вычисления джетов Габора с использованием быстрого преобразования Фурье 97
3.4 Позиционирование камеры на основе решения задачи внешней калибровки 98
Выводы по 3 главе 100
4. Разработка системы распараллеливания вычислений для решения задач взаимной привязки изображений земной поверхности. Проведение экспериментальных исследований 101
4.1 Подсистема моделирования полета БПЛА и генерации видеоряда 101
4.2 Система распараллеливания вычислений 110
4.2.1 Программная библиотека, содержащая реализации разработанных
4.2.2 Логическая схема и высокоуровневый программный модуль для параллельной подготовки эталонных данных 121
4.2.3 Логическая схема и высокоуровневый программный модуль для параллельного решения задачи взаимной привязки 123
4.3 Проведение экспериментальных исследований 125
4.3.1 Исследование разработанного алгоритма сопоставления видеоснимков местности с фрагментарным многомасштабным представлением эталонных изображений 125
4.3.2 Исследование метода локализации опорных точек на снимках местности, метода навигации по видео 133
4.3.3 Эксперименты по параллельной предобработке эталонных изображений земной поверхности 139
4.3.4 Эксперименты по параллельной обработке нескольких видеорядов 141
4.3.5 Исследование зависимости между использованием различных наборов фильтров Габора и итоговой точностью позиционирования 143
Выводы по 4 главе 146
Основные результаты работы 149
Список литературы
- Алгоритм Левенберга-Марквардта
- Фрагментарное многомасштабное представление эталонного изображения
- Использование билинейной интерполяции для повышения точности локализации опорных точек
- Исследование метода локализации опорных точек на снимках местности, метода навигации по видео
Введение к работе
Актуальность темы исследования. Методы и алгоритмы обработки и анализа изображений и видео применяются для решения широкого спектра задач, в том числе для визуальной навигации беспилотных летательных аппаратов (БПЛА). Актуальность развития методов визуальной навигации обусловлена тем, что точность спутниковых навигационных систем зависит от качества радиосигнала, а для инерциальных навигационных систем характерно накопление ошибки в вычислениях.
Задачами навигации БПЛА по изображениям занимаются как отечественные (Ю. Визильтер, Б. Алпатов, Н. Ким), так и зарубежные ученые (S. Grzonka, A. Bachrach, G. Conte, P. Doherty, A. Cesetti). Решение задачи визуальной навигации основано на поиске и сопоставлении особенностей на эталонном и на обрабатываемом изображениях сцены (взаимная привязка изображений). Однако существующие подходы обладают определенными недостатками, ограничивающими возможность их применения: необходимость наличия выраженных структурных особенностей на изображениях или достаточного числа эталонных изображений, слабая инвариантность к геометрическим искажениям снимков, работоспособность только при движении над достаточно плоскими территориями.
Анализ источников также показал слабую проработанность следующей проблемы: если эталонное изображение сцены имеет большие размеры, то взаимная привязка становится ресурсоемкой задачей. Актуальной является разработка методов и алгоритмов навигации БПЛА по видео, работоспособных в широком диапазоне рабочих условий (работа, как с плоскими, так и с неплоскими сценами; взаимная привязка при отсутствии выраженных структурных особенностей; значительный размер эталонных изображений).
Требуется выполнить комплексное тестирование разработанных алгоритмов визуальной навигации для принятия решений о выборе наилучших алгоритмов и их настроек в зависимости от характеристик камеры, высоты полета и др. В предыдущих исследованиях, алгоритмы тестировались на обычных персональных компьютерах. Актуальной является разработка системы управления распараллеливанием вычислений (в частности, для кластерной вычислительной установки – КВУ) для задач навигации БПЛА по видео. Использование КВУ позволит ускорить тестирование и отладку алгоритмов, предобработку эталонных изображений местности, а также принять решение о выборе наиболее эффективных алгоритмов и их настроек для различных исходных данных.
Работа выполнена в рамках одного из основных научных направлений ИПС им. А.К. Айламазяна РАН «Теория и технология систем, основанных на знаниях; интеллектуальные методы обработки информации».
Цель и задачи исследования. Цель работы – разработка методов и алгоритмов обработки и анализа изображений земной поверхности для навигации БПЛА по видеопоследовательностям. Для достижения поставленной цели решались следующие задачи:
– анализ существующих методов и алгоритмов сопоставления изображений, навигации беспилотных аппаратов по изображениям;
– разработка метода сопоставления кадров видеоряда с эталонным изображением земной поверхности, имеющим значительные размеры;
– разработка метода навигации БПЛА по видеоснимкам подстилающей поверхности, работоспособного в широком диапазоне рабочих условий;
– разработка системы управления распараллеливанием вычислений, позволяющей решать задачи навигации по видео с помощью КВУ для ускоренного тестирования алгоритмов и предобработки эталонных данных;
– программная реализация разработанных методов и алгоритмов, проведение экспериментальных исследований с целью оценки точности и надежности предлагаемых решений.
Методы исследований базируются на разделах математического анализа, линейной алгебры, методах оптимизации, теории обработки и анализа изображений, искусственного интеллекта. Экспериментальные исследования выполнялись на синтезированных видеопоследовательностях с использованием методов компьютерного моделирования.
Тематика работы соответствует следующим пунктам паспорта специальности 05.13.01: п. 5 «Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации», п. 12 «Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации».
Научная новизна работы:
– модифицированный алгоритм сопоставления видеопоследовательности снимков сцены с эталонным изображением сцены, основанный на фрагментарном многомасштабном представлении эталонных изображения и включающий в себя разработанный метод принятия решения о выборе подмножества фрагментов эталонного изображения. От существующих решений алгоритм отличается меньшей вычислительной сложностью при использовании эталонных изображений больших размеров.
– модифицированный метод локализации и сопоставления точечных особенностей на видеокадрах и на эталонном изображении, основанный на использовании вейвлетов Габора и отличающийся применением геометрического выравнивания видеокадра с использованием вычисленного положения и ориентации камеры для предыдущего кадра. Метод позволяет находить точечные особенности со средней погрешностью в 0.5 пикселей.
– модифицированный метод навигации БПЛА по видео, основанный на фрагментарном многомасштабном представлении эталонного изображения и разработанном методе локализации и сопоставления точечных особенностей. От существующих решений метод отличается более широким диапазоном рабочих условий (работа, как с плоскими, так и с неплоскими сценами; взаимная привязка при отсутствии выраженных структурных особенностей на снимках; значительный размер эталонных изображений).
– структура системы управления распараллеливанием вычислений, отличающаяся подключением объектно-ориентированных модулей генерации, обработки и анализа изображений и обеспечивающая ускорение решения задач предобработки эталонных изображений и тестирования алгоритмов визуальной навигации БПЛА за счет использования КВУ. На основании результатов экспериментальных исследований, предложена система принятия решения о выборе наилучших настроек алгоритмов для решения задач позиционирования по видео.
Практическая значимость работы:
– в ходе полунатурных экспериментов, погрешность в позиционировании по видео составила не более 0.15% от высоты полета (не более 3 м. при высоте полета до 2400 м.). Использование фрагментарного многомасштабного представления позволило в 4-16 раз уменьшить объем ресурсов, необходимых для сопоставления изображений. Разработанные методы и алгоритмы навигации по видео работоспособны в более широком диапазоне условий, чем предыдущие решения. Применение разработанных методов и алгоритмов в системах навигации БПЛА позволит повысить их эффективность и точность, расширить диапазон рабочих условий.
– разработанная система управления распараллеливанием вычислений для задач взаимной привязки изображений обеспечивает ускорение обработки одновременно нескольких наборов данных (видеопоследовательностей снимков сцены), а также подготовки эталонных данных. Система управления распараллеливанием может быть использована для разработки и ускоренного тестирования алгоритмов навигации по изображениям.
Внедрение результатов исследований. Результаты были использованы при выполнении двух научно-исследовательских работ, выполняемых в ИПС им. А.К. Айламазяна РАН (государственный контракт № 07.514.11.4033 и соглашение №14.607.21.0012), результаты исследований отражены в 4 отчетах о НИР. Весной 2013 года соискатель вошел в число победителей программы «Участник молодежного научно-инновационного конкурса (“УМНИК”)», тема представленного проекта соответствует теме диссертационного исследования. Теоретические результаты внедрены в учебный процесс ЧОУ ВО Институт программных систем «УГП имени А.К. Айламазяна» (дисциплина «Математические основы обработки сигналов»).
Апробация работы. Основные результаты докладывались на следующих
конференциях: научно-техническая международная молодежная конференция
«Системы, методы, техника и технологии обработки медиаконтента» (Москва,
МГУП им. Ивана Федорова, 2011), всероссийская конференция с
международным участием «Информационно-телекоммуникационные
технологии и математическое моделирование высокотехнологичных систем» (Москва, РУДН, 2012), V Всероссийская научно-техническая конференция «Актуальные проблемы ракетно-космического приборостроения и информационных технологий» (Москва, ОАО «Российские космические системы», 2012), XVI и XVII Молодежная научно-практическая конференция «Наукоёмкие информационные технологии» (Переславль-Залесский, УГП
имени А. К. Айламазяна, 2012-2013), XIV национальная конференция по искусственному интеллекту с международным участием КИИ-2014 (Казань, 2014), IV международная конференция «Robot Intelligence Technology and Applications» (Южная Корея, Bucheon, 2015).
Публикации. Основные результаты опубликованы в 11 печатных работах, в том числе 4 статьи в изданиях из Перечня ВАК и 1 статья в журнале, индексируемом SCOPUS. В работах, опубликованных в соавторстве, соискателю принадлежит: в [5] - описание разработанного подхода и алгоритма позиционирования БПЛА по видео, описание способа предобработки эталонных изображений; [6, 7, 11] - программные модули моделирования полета БПЛА и генерации видеоряда; [8] – алгоритм выбора наилучшего опорного снимка; [10] – алгоритм сужения области поиска особых точек, описание использования фрагментарного многомасштабного представления эталонных изображений; [13] – способ генерации траектории и порождения видеоряда, алгоритм поиска пар общих точек на снимках с БПЛА и эталонных изображениях.
Структура и объём работы. Диссертация изложена на 168 страницах, из них 161 страница основного текста, 45 рисунков, 16 таблиц. Состоит из введения, четырех глав, заключения, списка литературы из 108 наименований и приложения на 7 страницах.
Алгоритм Левенберга-Марквардта
Точка (x, y) считается «углом», если оба собственных значения матрицы H(x, y) больше некоторого порога. Недостатком подобного алгоритма является то, что они не инвариантны к масштабированию: при разных масштабах одного и того же изображения на них могут быть найдены разные угловые точки. Кроме того, они слабо инвариантны к поворотам.
В задаче выделения и прослеживания особенностей между последовательными кадрами некоторого видеоряда, изменение ракурса или масштаба между кадрами обычно незначительное, и здесь часто применяется алгоритм GoodFeaturesToTrack [35], основанный на детекторе углов Харриса. После выделения углов, выполняется процедура немаксимального подавления: остаются только те угловые точки, значение отклика которых на детектор углов Харриса является локальным максимумом в окрестности 3x3. Далее, вычисляется значение maxQuality – максимальный отклик всех пикселей на детектор. Убираются все угловые точки, отклик которых меньше чем maxQuality qualityLevel, где qualityLevel – параметр алгоритма. Оставшиеся угловые точки сортируются в порядке убывания значений отклика. В итоге, остаются только те угловые точки, которые являются локальными максимумами среди всех остальных угловых точек, находящихся в радиусе maxDistance от нее (еще один параметр алгоритма). Более совершенные алгоритмы выделения особенностей обладают инвариантностью к изменению освещенности, к аффинным и в определенной степени к проективным преобразованиям [32]. Примерами таких алгоритмов являются SIFT [36], SURF [37], GLOH [38], MSER [39] и др. Во всех этих алгоритмах для каждой особой точки вычисляется ее дескриптор, который в определенной мере инвариантен к изменениям яркости, аффинным и перспективным преобразованиям.
Алгоритм SURF (Speeded Up Robust Features) является развитием алгоритма SIFT. За счет использования не аналитических, а приближенных методов для вычисления вторых производных и определения ориентации особой точки, SURF обладает лучшей производительностью, чем SIFT [40], и при определенных настройках может использоваться в режиме реального времени. Как утверждают авторы алгоритма, SURF обычно находит несколько меньше особых точек на изображениях, чем SIFT, но они более устойчивы к геометрическим преобразованиям.
Основным инструментом является матрица Гессе, чей определитель (гессиан) достигает экстремума в точках максимального изменения градиента яркости. Он хорошо детектирует пятна, углы и края линий, но не инвариантен к масштабированию, поэтому SURF использует разномасштабные фильтры для нахождения гессианов. Для каждой особой точки вычисляется направление максимального изменения яркости (градиент) и масштаб, взятый из масштабного коэффициента матрицы Гессе. Градиент вычисляется с помощью фильтров Хаара.
Дескриптор особой точки представляет собой набор из 64-х (либо 128-ми) чисел. Эти числа отображают флуктуации градиента вокруг особой точки. Так как особая точка представляет собой максимум гессиана, то это гарантирует, что в окрестности точки должны быть участки с разными градиентами, что обеспечивает различие дескрипторов для разных особых точек. Флуктуации градиента окрестностей ключевой точки считаются относительно направления градиента вокруг точки в целом (по всей окрестности ключевой точки). Так достигается инвариантность дескриптора относительно вращения. Размер же области, на которой считается дескриптор, определяется масштабом матрицы Гессе, что обеспечивает инвариантность относительно масштаба. Флуктуации градиента также считаются с помощью фильтра Хаара.
Для нахождения особых точек, SURF пробегается по пикселям изображения и ищет локальный максимум гессиана. Если вычисленное значение для пикселя выше некоторого порога, то пиксель рассматривается как кандидат на особую точку. Поскольку гессиан выражается через производные и зависит только от перепада яркости, но не от абсолютного ее уровня, то он инвариантен по отношению к сдвигу яркости изображения.
В алгоритме SURF все множество масштабов разбивается на так называемые октавы. Каждая октава покрывает определенный интервал масштабов, и имеет свой характерный размер фильтра. При нахождении локального максимума гессиана используется пирамида гессианов. В дополнение к дескриптору, для описания точки используется знак следа матрицы Гессе. Заметим, что две особые точки с двух изображений не могут быть соответствующими, если знак следа матрицы Гессе у них разный. Это свойство можно использовать при построении процедуры сопоставления точек.
Фрагментарное многомасштабное представление эталонного изображения
Чаще всего, ах = /3у = 0, пара \8х,8у\ определяет координаты левого верхнего угла эталонного изображения в системе ППГК, а пара (кх,ку) пространственное разрешение каждого пикселя по горизонтали и вертикали. В зависимости от используемого географической системы координат (способа отображения криволинейной поверхности земного эллипсоида на плоское изображение), используются различные уравнения для перехода из системы ППГК в геодезическую, и наоборот. Например, описание уравнений для системы координат UTM доступно в статье [91].
Введем понятия нормальной и связанной систем координат [92]. Начало нормальной система координат OXgYgZg (рисунок 2.1.3) привяжем к центру проекции (оптическому центру) видеокамеры, которая наблюдает сцену. Направление оси OZg совпадает с направлением нормали к поверхности наблюдаемой сцены. Ось OYg направлена с севера на юг по касательной к географическому меридиану. Ось OXg расположена параллельно касательной к параллели в направлении с запада на восток. Начало связанной система координат OXYsZs также привяжем к центру проекции камеры. Направление оси OZs совпадает с направлением оптической оси. Ось OYs направлена вниз от камеры, а ось OXs - вправо от камеры (что совпадает с направлением координатных осей пиксельной системы координат изображения).
Нормальная и связанная система координат Взаимная ориентация связанной и нормальной систем координат определяет угловое положение камеры относительно поверхности наблюдаемой сцены с помощью углов рыскания, тангажа и крена: угол рыскания в - угол между осью OY нормальной системы координат и проекцией оси OYs на горизонтальную плоскость OXgYg. Угол положителен, когда ось OYg совмещается с указанной проекцией продольной оси поворотом вокруг оси OZg по часовой стрелке, если смотреть в направлении оси OZg. угол тангажа ср - угол между осью OYs и горизонтальной плоскостью OXgYg нормальной системы координат. Угол положителен, если ось OY направлена вниз. угол крена у/ - угол между осью OXs и осью ОХ смещенной в положение, соответствующее нулевому углу рыскания. Угол положителен, когда смещенная ось OXg совмещается с поперечной осью поворотом по часовой стрелке, если смотреть в направлении, противоположном OYs . Ориентацию камеры относительно нормальной системы координат можно задать как тремя углами, так и матрицей поворота: (2.1.3) ГП Г\2 Г\Ъ Rg = Г2\ 22 23 _ГЪ\ ГЪ2 ГЪЪ _ " cos6 -sin 9 0 10 0 cos 0 sin sin 6 cos6 0 0 cos p smcp 0 1 0 0 0 1 0 -sinq coscp smy/ 0 cosy/ [cos 6 cos -sin 6 sin j? sin -sin cos - cos 6 sin -sin 6 sin j? cos Л = sin 6 cos +cos 6 sin j? sin cos cos -sin sin + cos sin cos . _ COS 7Sin -Sin COS COS / J Заметим, что cos p = 0 только в том случае, если угол тангажа равен +90 или -90: в таких случаях оптическая ось камеры будет перпендикулярна поверхности наблюдаемой сцены, и сцена просто не попадет в поле зрения камеры. Для декомпозиции матрицы R можно применить следующие формулы: #? = asin(-r32), і//= atan2(r31,r33), # = atan2(-r12,r22). (2.1.4) Ориентация нормальной системы координат относительно ГСК определяется положением камеры в геодезической системе координат. Пусть (В,Ь) - широта и долгота точки пространства, в которой находится камера. Ориентацию можно задать с помощью следующей матрицы поворота i путем композиции элементарных матриц поворота вокруг координатных осей: о A R cosL -sinL 0 cosB 0 -sinB sinL cosL 0 0 1 0 0 l__sin5 0 cosB ] J\ 0 0 cos , 2У -sin 2 і 0 sin л лЛv 2j 1 COS 2J cos sin Л v2y 0 -sin v y 01 v y \ J 0 cos 0-1 1 о 0 0-10 (2.1.5) Здесь матрица R определяет ориентацию камеры, находящейся в точке с нулевыми значениями долготы и широты. Таким образом, чтобы вычислить ориентацию камеры в ГСК при известных значениях широты, долготы, тангажа, крена и рысканья, достаточно сделать следующее: R = R(B,L, p,y/,e) = R0(B,L)-Rg( p,y/,e). (2.1.6) Если известно положение и ориентация камеры в ГСК, то можно восстановить ее положение и ориентацию в геодезической системе координат, а также вычислить три навигационных угла (тангаж, крен и рысканье). Вначале необходимо перевести геоцентрические координаты в геодезические, вычислить матрицу R0 , матрицу R = RQR, далее для вычисления навигационных углов применяются уже описанная в данной главе процедура декомпозиции R. Предположим, что видеокамера закреплена на днище летательного аппарата и смотрит вниз. На рисунке 2.1.4 показана взаимная ориентация связанной системы координат и локальной системы координат, привязанной к летательному аппарату. Столбцами матрицы R являются базисные векторы связанной системы координат OXYZ камеры, выраженными в ГСК.
Как уже говорилось, в ходе аналитического обзора научной литературы по теме диссертационной работы было выявлено, что недостаточное внимание уделяется проблеме сопоставления снимков сцены с эталонными изображениями, если последние имеют значительные размеры. Предлагается использовать так называемую пирамиду эталонных изображений, каждый слой которой разрезается на небольшие квадратные фрагменты - тайлы (англ. tiles). Данный подход широко используется во многих геоинформационных системах для обеспечения возможности просмотра больших спутниковых снимков в различных масштабах.
В основании пирамиды лежит исходное изображение, а каждый следующий слой по ширине и высоте в 2 раза меньше предыдущего. Размер каждого тайла обычно составляет 256x256 пикселей (рисунок 2.2.1). Многомасштабное представление призвано также решить проблему в различии масштабов эталонных и обрабатываемых изображений: алгоритмы наподобие SURF хотя и являются инвариантными к масштабированию, но в ограниченных пределах.
Использование билинейной интерполяции для повышения точности локализации опорных точек
Как уже упоминалось в 1 главе, если некоторая сцена не является плоской и наблюдаема с двух камер (или одной и той же камерой, но в разные моменты времени), то взаимное положение и ориентация камер связывается фундаментальной матрицей. Эту матрицу можно разложить на матрицу поворота и вектор параллельного переноса, но вектор будет определен только с точностью до неизвестного положительного коэффициента. Для разрешения данной неоднозначности, необходимы или данные со вспомогательных средств (например, ИНС), которые позволят вычислить расстояние, пройденное камерой между двумя моментами съемки, или же какие-то априорные сведения о наблюдаемой сцене. К таким сведениям могут относиться известные расстояния между объектами сцены (опорными объектами), или же трехмерные координаты объектов в некоторой глобальной системе координат [11]. Если удастся найти несколько таких опорных объектов на снимке сцены, то задачу взаимной привязки можно свести к задаче внешней калибровки камеры. Исходными данными для алгоритма внешней калибровки является набор пар вида «двумерные координаты опорной точки на видеокадре – трехмерные координаты этой точки в глобальной системе координат».
В данной главе представлено математическое описание вейвлетов Габора, возможности которых использованы для поиска опорных точек. Представлена процедура подготовки исходных данных, необходимая для решения задачи взаимной привязки на основе поиска опорных точек. Описан метод поиска опорных точек, одним из этапов которого является геометрическое выравнивание видеокадра. Финальным этапом решения задачи взаимной привязки является внешняя калибровка камеры.
В различных алгоритмах обработки и анализа изображений широко применяются фильтры (вейвлеты) Габора: например, для распознавания радужной оболочки или отпечатков пальцев в биометрических системах безопасности. Вейвлеты относительно устойчивы к изменениям яркости и геометрическим искажениям [96]. Импульсная переходная характеристика таких фильтров в разных источниках может иметь различный параметрический вид [97], приведем один из вариантов [98]: Л У) = -е[АЖІ 2 ]{co,{kv.xu)-e- \ jc.=jccos(%) + j;sin(%), Ая (3.1.1) v = , pu=u--, v = {0,1...4}, i/ = {0,1...7}. 2 (л/2 )V Заметим, что функция Габора является комплексной, выше приведена только действительная ее часть. Значение параметра v влияет на масштаб фильтра, значение параметра и - на его ориентацию. Таким образом, получаем семейство из 5x8 = 40 фильтров Габора. Результаты свертки некоторой области изображения с каждым из фильтров образуют 40-мерный вектор - так называемый джет, который можно использовать в качестве дескриптора того пикселя, который лежал в центре области. Сравнение джетов с двух изображений (с помощью некоторой метрики или меры близости) позволяет сопоставлять точечные особенности между ними. В работе [99] описан успешный опыт применения фильтров Габора в задаче создания трехмерных моделей объектов по паре фотографий, которая основана на сопоставлении пикселей с двух изображений: джет А, построенный для точки с первого изображения, сравнивается с джетами точек со второго изображения (В). В качестве меры близости между джетами использовалась корреляционная функция следующего вида: S E)= 40i=1 40 . (3.1.2)
В данной работе предлагается подход к взаимной привязки изображений, основанный на поиске так называемых опорных точек с применением вейвлетов Габора. Опорные точки предварительно выделяются на эталонном изображении, каждая точка имеет свою 3D-координату в глобальной системе координат, а задача вычисления положения и ориентации камеры сводится к задаче внешней калибровки.
Теоретически, для решения задачи внешней калибровки камеры достаточно найти всего три точки на снимке, для каждой из которых известны ее 3D-координаты в глобальной системе координат. Но поскольку мы имеем дело с дискретными изображениями, для которых невозможна точная локализация искомых точек, то данные всегда будут в большей или меньшей степени зашумлены. Известным подходом к решению проблемы является использование большего количества точек, а задача внешней калибровки камеры сводится к оптимизационной задаче, которая решается по методу наименьших квадратов.
На эталонном изображении необходимо выбрать ряд опорных точек таким образом, чтобы на кадрах видеоряда точки были наблюдаемы в количестве, достаточном для решения задачи внешней калибровки. Кроме того, точки должны быть распределены по эталонному изображению достаточно равномерно, чтобы они попадали в видеокадры в необходимом количестве. Наконец, каждая опорная точка должна выделяться на фоне пикселей-соседей.
Для выполнения всех вышеперечисленных требований к выбору опорных точек, был разработан следующий подход. В ходе предварительной подготовки исходных данных, а именно: поиске особых точек на каждом тайле с помощью алгоритма SURF, среди всех особых точек тайла выбирается несколько точек с наибольшими значениями определителя матрицы Гессе. Определитель является одним из описателей особой точки: чем он больше, тем более «особой» является точка (тем сильнее она выделяется на фоне пикселей-соседей) [37]. Эти точки принимаются в качестве опорных. Эксперименты показали, что для успешного решения задачи позиционирования для относительно небольших расстояний до наблюдаемой сцены (150-300 метров), каждый тайл можно разделить на 4 равных части, и в каждой из частей выбирать по одной опорной точке. Для больших расстояний до наблюдаемой сцены, достаточно на каждом тайле выбрать по две опорных точки. Также эксперименты показали, что для достижения приемлемой точности взаимной привязки, достаточно найти на видеокадре около 10 опорных точек.
Исследование метода локализации опорных точек на снимках местности, метода навигации по видео
Исследование разработанного алгоритма сопоставления видеоснимков местности с фрагментарным многомасштабным представлением эталонных изображений
Для экспериментов, использовался спутниковый снимок размером 10000x10000 пикселей (пространственное разрешение - 1 метр на пиксель) и карта высот размером 1000x1000 пикселей (10 метров на пиксель). Центр спутникового снимка расположен в точке 4742 40.19" с.ш., 12420 26.88" з. д. (район северо-запада США, недалеко от города Сиэтл и границы с Канадой). Местность содержит как равнинные природные территории, так и возвышенности. Разрешение сгенерированных видеокадров составляло 1024x768 пикселей, фокальная длина для виртуальной камеры была выбрана равной 300 пикселей. Это соответствует камере с широкоугольным объективом, имеющим углы обзора 120 х 104. Камера двигалась в виртуальном пространстве с постоянной скоростью 33 м./с. (примерно 120 км./ч.) - максимальная скорость многих небольших и средних БПЛА. Камера выполняла снимки местности с частотой 1 кадр в секунду. Количество особых точек, которые алгоритм SURF находил на снимках с камеры, составляло от 2500 до 7000 для разных высот полета (время счета — 1.3-3.0 сек., без проведения оптимизаций). Для тестирования разработанного метода сопоставления кадров видеоряда с фрагментарным представлением эталонного спутникового снимка, использовались три типовых траектории движения камеры с генерацией видеоряда с учетом рельефа поверхности (карты высот), а также три аналогичных траектории, но с генерацией видеоряда при полете над плоской местностью (та же самая территория, но без использования карты высот): 1) горизонтальный полет в северном направлении на постоянной высоте над плоской местностью. Самый простой случай, в котором ориентация эталонного снимка и видеокадра совпадают. 2) горизонтальный полет в северном направлении на постоянной высоте над местностью с рельефом. 3) горизонтальный полет на постоянной высоте в северо-восточном направлении над плоской местностью. Здесь эталонный снимок и видеокадр имеют различную ориентацию (в данном случае, ориентация отличается на 45). 4) горизонтальный полет на постоянной высоте в северо-восточном направлении над местностью с рельефом. 5) полет в северо-восточном направлении с набором высоты над плоской местностью. Здесь эталонный снимок и видеокадры имеют не только разную ориентацию, но и разный масштаб. 6) полет в северо-восточном направлении с набором высоты над местностью с рельефом.
Сравнение алгоритмов сопоставления особых точек только по критерию быстродействия является недостаточным, поскольку важнейшим показателем, в конечном счете, является точность позиционирования и взаимной привязки (погрешность в вычислении положения и ориентации). Точность зависит от качества исходных данных для алгоритма решения задачи внешней калибровки камеры, которая, в свою очередь, зависит от результатов работы алгоритма поиска опорных точек на видеокадре с помощью вейвлетов Габора. А результаты его работы зависят от того, насколько точно с помощью 5-точечного алгоритма и методики RANSAC вычислена фундаментальная матрица F, связывающая изображение с камеры на БПЛА и эталонный снимок.
Совместное использование 5-точечного алгоритма и методики RANSAC позволяет не только вычислить матрицу F, но и пометить пары соответствующих точек, которые не удовлетворяют фундаментальной матрице. Эксперименты показали, что если после вычисления матрицы F остается слишком мало пар точек (как правило, менее 20-25), то матрица F в подавляющем большинстве случаев вычислена неверно.
Алгоритм FLANN_separateTiles оказался неспособным корректно сопоставлять особые точки: время сопоставления было слишком велико (3 секунды и более для одного кадра видеоряда), находилось слишком много ложных соответствий, что негативно сказывалось на времени вычисления фундаментальной матрицы (несколько секунд и даже несколько десятков секунд 128 для одного кадра). Результаты вычисления матрицы F во всех случаях оказывались весьма далеки от истинных значений, что делало невозможным решение задачи визуальной навигации. Для остальных алгоритмов, задача взаимной привязки решалась довольно успешно. В таблице 4.3.1.1 приведено сравнение пяти алгоритмов, для каждой из шести тестовых траекторий полета. Вычисления выполнялись на одном из ядер процессора Intel Xeon E5410. По времени сопоставления наиболее эффективными оказались алгоритмы FLANN_mergeTiles и FLANN_useFrame, затем идут алгоритмы BF_mergeTiles и BF_useFrame, наименее эффективен алгоритм BF_separateTiles. По времени последующего вычисления матрицы F, наиболее эффективными оказались алгоритмы BF_mergeTiles и BF_useFrame, затем идут алгоритмы BF_separateTiles и FLANN_mergeTiles, наименее эффективен алгоритм FLANN_useFrame. Но в целом, для всех подходов характерен недостаток: в случае наличия значительных проективных искажений (тест №6) между эталонными данными (спутниковый снимок) и тестовыми (видеокадр с БПЛА) удается найти недостаточно пар точек-«инлайеров», что не позволяет решить задачу позиционирования.
Алгоритм Времясопоставления , сек. Кол-во найденных пар точек Время вычисления матрицы F, сек. Кол-во пар точек-инлайеров Примечание BFseparateTiles 1.0-1.25 632-654 403-468 200-225 171-191 132-142 120-140 0.12-0.27 0.28-0.55 0.21-0.51 0.70-0.95 0.05-0.33 0.12-0.28 400-430200-24060-8349-6125-4614-29 В тесте №6 инлайеров оказалось мало, ошибка в позиционирова нии составила 19 м. BFmergeTiles 0.7-1 486-510247-29280-10254-6938-4724-33 0.06-0.21 0.08-0.17 0.06-0.10 0.03-0.07 0.02-0.04 0.02-0.05 345-384127-16445-5430-3520-2615-21 BFuseFrame 0.50-0.75 515-538 273-309 100-134 70-80 0.08-0.15 0.09-0.19 0.06-0.18 0.10-0.14 326-403 162-188 42-66 30-35 В тесте №6 инлайеров оказалось мало, ошибка в 34-46 25-38 0.04-0.07 0.03-0.05 18-2612-22 позиционирова нии составила 8 м. FLANN mergeTi les 0.15-0.18 (без учетапостроения индекса поиска — 0.09-0.11) 640-659 420-484 238-240 185-199 129-160 126-148 0.21-0.31 0.26-0.46 0.41-0.49 0.17-1.10 0.02-0.28 0.13-0.31 393-476195-24219-10248-6833-5014-34 В тестах №3 и №6 инлайеров оказалось мало, вычислить положение БПЛА не удалось. FLANN_useFra me 0.14-0.18 714-738 503-532 279-321 241-276 150-182 159 0.29-0.36 0.28-0.48 0.62-1.59 0.20-1.58 0.14-1.75 0.04 387-425235-26596-10953-8140-5612 В тесте №6инлайеровоказалосьмало,вычислитьположениеБПЛА неудалось.
Перейдем к сравнению предложенных алгоритмов в случае, когда все особые точки и на тайлах пирамиды эталонных изображений, и на видеокадре, разбивались на две группы, в зависимости от знака следа матрицы Гессе (таблица 4.3.1.2). Процессорное время, необходимое на разбиение, оказалось невелико (не более 1 миллисекунды), поэтому это существенно не повлияло на быстродействие всех шести алгоритмов. По времени сопоставления наиболее эффективными оказались алгоритмы FLANN_mergeTiles и FLANN_useFrame (основанные на использовании поисковых индексов), затем идут алгоритмы BF_mergeTiles и BF_useFrame, наименее эффективен алгоритм BF_separateTiles. По времени вычисления матрицы F (выполняется после сопоставления точек) наиболее эффективны алгоритмы BF_mergeTiles и BF_useFrame, затем идут алгоритмы BF_separateTiles и FLANN_mergeTiles, наименее эффективен алгоритм FLANN_useFrame. Как видим, разбиение множества особых точек на два подмножества по знаку следа матрицы Гессе позволило повысить количество найденных пар примерно в 1,5-2 раза, увеличилось и количество найденных пар-«инлайеров», что повысило точность вычисления фундаментальной матрицы (но даже в этом случае алгоритм 6 дал сбой).