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

На правах рукописи

Камаев Александр Николаевич

ПОСТРОЕНИЕ ФОТОГРАФИЧЕСКИХ КАРТ ПОДВОДНОГО ДНА НА ОСНОВЕ БОЛЬШИХ МАССИВОВ ИЗОБРАЖЕНИИ

Специальность 05.13.11 -Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата технических щук

11 НОЯ 2014

Иркутск-2014

005556057

005556057

Работа выполнена в Федеральном государственном бюджетном учреждении науки Вычислительном центре Дальневосточного отделения Российской академии наук (ВЦ ДВО РАН).

Научный руководитель: член-корреспондент РАН,

профессор, директор ВЦ ДВО РАН Смагин Сергей Иванович

Официальные оппоненты: доктор технических наук,

доцент, старший научный сотрудник лаборатории математических ^етодов обработки изображений ИСОИ[ РАН Куприянов Александр Викторович

кандидат технических наук, доцент, заведующий лабораторией комплексных информационных систем ИДСТУ СО РАН Хмельно» Алексей Евгеньевич

Ведущая организация: Институт проблем морских

технологий ДВО РАН (г. Владивосток)

Защита состоится 23 декабря 2014 г. в 15 ч. 30 мин. на заседании диссертационного совета Д 003.021.01 в ИДСТУ СО РАН по адресу: 664033, г. Иркутск, ул. Лермонтова, 134.

С диссертацией можно ознакомиться в библиотеке и на официальном сайте www.idstu.irk.ru ИДСТУ СО РАН1.

Автореферат разослан 21 ноября 2014 г.

Ученый секретарь диссертационного совета, к.ф.-м.н.

>-7

Т.В. Груздева

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Подводное дно - интересный и вместе с тем труднодоступный для изучения объект. Перспективным методом исследования дна является его фотографирование с помощью автономных необитаемых подводных аппаратов (АНПА). Поскольку глубоко под водой освещение отсутствует, для получения качественных снимков необходимо производить съемку на небольшом удалении от поверхности дна. Это приводит к тому, что каждый снимок охватывает малый участок территории, следовательно, для покрытая больших участков необходимо большое количество снимков. Так как работать с общей фотографической картой исследуемого участка подводного дна значительно удобнее, чем с набором из тысяч разрозненных изображений, актуальной представляется задача сшивки подводных изображений в такие карты. Кроме того задача сшивки подводных изображений тесно пересекается с задачей навигации АНПА по фото или

видеоинформации.

Фотографические карты дна могут быть использованы для салак

различных целей, но основные перечислены ниже:

1. Изучение поверхности дна, флоры и фауны, обитающей на дне.

2. Мониторинг подводной инфраструктуры (кабели, трубопроводы, подводные постройки и др.).

3. Поиск затонувших объектов.

4. Навигация АНПА по построенной фотографической карте.

Задача построения фотографических карт дна не нова и имеет ряд решений. Одними из первых расчет траектории АНПА по видеоданным произвели Aguirre R-, Boucher J.M. и Jacq J.J. в 1990 году. Позже многие ученью использовали похожие подходы для сшивки последовательных изображений, среди них: Fleischer S.D., Marks R.L., Garcia R., Battle J., а также российские ученые из ИПМТ ДВО РАН. Современный подход к построению фотографических карт дна или мозаик основывается на упорядоченном поступлении изображений с АНПА и описан в работах Garcias N.R., Bernardino A., Eustice R.M., Pizzarro О. и в работах многих других ученых. Можно выделить следующие этапу построения карт, характерные для современного подхода: сопоставление последовательных изображений, сопоставление остальных пересекающихся пар изображений, вычисление движения камер и смешение изображений, спроецированных на поверхность карты. При этом процесс сопоставления непоследовательных пар использует приближенную структуру движения, полученную на основе сопоставления последовательных пар. Эта структура движения позволяет с некоторой точностью определить места, в которых пересекаются непоследовательные

пары изображений. После обнаружен^ набора дополнительных пар структура

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

Рассмотрим три случая, когда последовательная сшивка изображений невозможна либо неточна. Первый случай - обследование большой зоны, когда между пересечениями своей траектории АНПА проходит большие расстояния. Накапливающаяся при последовательной сшивке ошибка легко может дойти до 10 и более метров, что потребует сравнения большого числа пар изображений между собой для замыкания траектории. Второй случай - недостаточно пересекающиеся последовательные изображения. Когда АНПА идет быстро или редко выполняет фотографирование, между многими соседними снимками не будет обнаружено соответствий, что приведет к более быстрому накоплению ошибки. Третий случай - особенности дна. На дне могут быть большие однородные зоны, не содержащие особенностей для сопоставления последовательных снимков.

С другой стороны, задача сшивки изображений хорошо исследована для построения панорам (Brown М., Lowe D., Szeliski R.). При этом отсутствуют какие-либо требования к упорядоченности. Но специфика подводных изображений: их большое количество, низкая четкость, сложные условия освещения, нетипичный для стандартных панорам характер движения камеры не дает использовать методы сшивки изображений в панорамы для задачи составления фотографических карт дна без адаптации. В связи с этим важной представляется задача адаптации существующих и разработки новых методов построения фотографических карт дна для любых последовательностей изображений, независимо от разрывов и пропусков данных, а также от размера исследуемой территории. Для этого необходим механизм обнаружения положения каждого изображения, не предъявляющий никаких требований к порядку этих изображений. Разработка такого механизма на сегодняшний момент является актуальной задачей, требующей решения большого числа сопутствующих проблем.

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

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

покрытия.

3. Задача ориентирования и позиционирования снимков на основе визуальных особенностей. Для сшивки изображений в единую карту дна необходимо найти положение и ориентацию каждого снимка на карте. Алгоритм поиска положения и ориентации должен быть достаточно быстрым, чтобы справляться с большими объемами входных данных.

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

четкую карту подводного дна.

5. Разработка и тестирование программного средства, реализующего все алгоритмы построения фотографической карты.

Объектом исследования являются методы, алгоритмы и программные средства автоматической сшивки изображений.

Предметом исследования являются методы, алгоритмы и программные средства сшивки изображений подводного дна, получаемых с АНПА.

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

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

Все предлагаемые в работе методы и алгоритмы решения задач проверяются на основе экспериментов.

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

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

3. Предложен алгоритм инициализации параметров нелинейной задачи вычисления положений и ориентаций изображений.

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

5. Разработано программное средство «AUV photo stitcher», предназначенное для составления фотографических карт подводного дна на основе больших массивов изображений.

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

Практическая значимость работы заключается в том, что на базе предложенных в ней алгоритмов можно создавать системы построения фотографических карт подводного дна на основе изображений, поступающих с АНПА после разведывательных миссий. В ходе работы над диссертацией была разработана такая система — «AUV photo stitcher».

Другим возможным применением результатов работы является построение систем навигации АНПА на основе фото- либо видеоинформации. Использование алгоритмов, описанных в данной работе, может стать базой для построения подобных систем.

Исследования по теме диссертации проводились в рамках следующих программ: комплексная целевая программа фундаментальных прикладных исследований ДВО РАН «Перспективные методы и средства изучения и освоения ресурсов Мирового океана на 2014-2018 годы», комплексная программа фундаментальных исследований ДВО РАН «Дальний Восток» (42П, раздел 2.37 «Система навигации необитаемого подводного аппарата по фотоизображениям, устойчивая к пропускам данных»).

Соответствие диссертации паспорту специальности. Полученные в диссертации результаты соответствуют области исследования специальности 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей, включающей в себя модели, методы, алгоритмы и программные средства обработки изображений (пункт 7 области исследований).

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

• Всероссийская научно-практическая конференция «Информационные технологии и высокопроизводительные вычисления», 2013, Хабаровск, Россия;

• ХХШ Международная конференция по компьютерной графике и зрению «Графикон», 2013, Владивосток, Россия;

• V Всероссийская научно-техническая конференция «Технические проблемы освоения Мирового океана», 2013, Владивосток, Россия;

• IV Всероссийская конференция «Математическое моделирование и вычислительно-информационные технологии в междисциплинарных научных исследованиях», 2014, Иркутск, Россия.

Публикации. По теме диссертации опубликовано 5 научных работ. Из них две статьи в журналах, входящих в перечень ВАК. На программное средство «AUV photo stitcher», разработанное на основе диссертационного исследования, получено свидетельство о государственной регистрации программы для ЭВМ № 2014613051 от 17.03.2014. Все результаты диссертации, выносимые на защиту, получены автором лично.

Структура и объем диссертации. Диссертация состоит из списка условных сокращений, введения, четырех глав, заключения и списка литературы. Содержание работы изложено на 148 страницах. В текст работы включены 43 рисунка, 3 таблицы. Список литературы содержит 113 источников, 101 из них на иностранном языке.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, обозначена цель, задачи и методология исследования, раскрыта научная новизна и практическая значимость работы. Приведены данные об апробации результатов исследования, дан перечень публикаций автора по теме диссертации и описана структура и объем работы.

В первой главе дается определение фотографических карт дна и ставится задача построения этих карт. Описывается процедура получения изображений с помощью АНПА для построения фотографических карт дна. Выявляется специфика построения этих карт: ограниченная высота съемки из-за необходимости использования искусственного освещения; нелинейные изменения освещения между соседними снимками; большое число снимков (до нескольких десятков тысяч); невозможность определения координат АНПА в момент получения каждого снимка с достаточной точностью; низкая четкость снимков; большое число однотипных объектов на дне; нетипичная для стандартных панорам модель движения АНПА в промежутках времени между

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

Выделяются основные этапы автоматической сшивки изображений: 1) сопоставление изображений; 2) калибровка камер; 3) вычисление положения и ориентации камер; 4) проекция изображений на одну поверхность; 5) совмещение изображений. Для каждого этапа рассматриваются существующие методы решения и дается заключение о возможности применения отдельных методов к задаче построения фотографических карт. Также в главе рассматриваются возможности применения таких распространенных систем автоматической сшивки изображений, как AutoStitch, Hugin - Panorama photo stitcher, PTgui, Microsoft Research Image Composite Editor для сшивки подводных изображений.

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

1) устранение неравномерного освещения, вызванного осветительными приборами АНПА;

2) обнаружение особенностей на слабокошрастных изображениях;

3) надежное сопоставление пар изображений, учитывающее большой процент ложных соответствий и использующее дополнительные данные, предоставляемые навигационной системой АНПА;

4) быстрый поиск связанных изображений в наборе из большого числа изображений с ненадежными особенностями;

5) поиск приблизительного положения и ориентации снимков для инициализации нелинейной задачи глобальной оптимизации;

6) эффективное решение глобальной задачи нелинейной оптимизации для большого числа параметров;

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

Во второй главе описывается процедура установления связей между снимками в больших наборах изображений, учитывающая специфику подводной съемки. В качестве входных данных рассматриваются т изображений, полученных после обследовательской миссии АНПА. При этом из навигационной системы известны: глубина diy курс у,-, высота над дном /г,-аппарата в момент получения каждого i-го изображения, z = 1,2, ...,т.

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

8

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

В главе исследовано три способа компенсации нелинейных изменений

освещенности:

R(x, у) = Y(x, у) - LO, у), О)

„г ^ , т

Здесь Y(x, у) - яркостная составляющая исходного изображения, R(x,y) -яркосгная составляющая изображения ср скомпенсированной освещенностью, а L(X) у) - яркосгная компонента, обусловленная освещением (низкие частоты яркостной компоненты изображения). С помощью вычислительного эксперимента показано, что компенсация нелинейных изменений освещенности играет ключевую роль при сопоставлении. В ходе этого эксперимента на одной и той же исходной выборке данных было обнаружено 160Q связанных пар изображений без коррекции, 3591 пара с коррекцией (1), 4146 и 4185 пар с коррекциями (2) и (3) соответственно.

В качестве визуальных особенностей в диссертационном исследовании используются SIFT особенности и дескрипторы. При этом в качестве ориентации дескрипторов рассматривается не приоритетное направление градиентов окрестности особенности, а величина, обратная курсу АНПА -7/. Это позволяет повысить точность сопоставления и избавиться от особенностей с множественными ориентациями.

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

u¡ = UisV cosYíj - ViSi¡ sinyiJ + tú7. (-4)

v¡ = UiSi¡ sinyv + ViSij cosy0' + •

Здесь i,j <r {1,2,...,m} - номера связанных изображений, (ut,v¡) и (uj.Vj) -координаты сопоставленных точек на i-м и ]-м изображении, slJ = hjh¡, ■fi = Yí — У], а вектор ti; = - неизвестный параметр модели.

Использование подобной модели связи допустимо ввиду плоского характера движения АНПА, однако требует большого порога допустимой погрешности, чтобы удовлетворять небольшим перепадам рельефа дна в рамках одного снимка. Модель связи может быть рассчитана по одной паре сопоставленных особенностей. Для фильтрации ложных соответствий во второй главе

9

предлагается рассчитать параметр tl> для всех найденных точечных соответствий и выбрать t1', согласующийся с наибольшим числом этих соответствий. Решение о связи пары изображений принимается на основе сравнения количества соответствий, лежащих в зоне пересечения снимков, и количества соответствий, удовлетворяющих выбранному параметру tÍJ. После установления связи с помощью простой плоской модели может быть применена любая, более точная фильтрация при необходимости.

Задача обнаружения связанных пар изображений решается во второй главе с помощью построения списков кандидатов на сопоставления для каждого изображения. Обозначим дескриптор j-й особенности i-ro изображения за g}, i = 1,2, ...,т, j = 1,2,... Д(г), где Л(г') - количество особенностей на i-м изображении. При этом дескрипторы всех особенностей на всех изображениях будем хранить в виде гибридного sp-дерева (spill tree). Такая структура хранения позволит для дескриптора gj найти вектор lj, состоящий из номеров изображений, содержащих первые к особенностей с дескрипторами, максимально близкими к дескриптору gj: Ij = Од.'/г«— >l¡k)- Подобная задача называется задачей поиска fc-ближайших соседей и может быть решена за время, не зависящее от размеров дерева, при условии использования алгоритма best bin first, ограничивающего количество просматриваемых узлов дерева до некоторого заданного числа наиболее вероятных узлов.

Зная lj, можно составить искомые списки кандидатов на сопоставление для каждого изображения. Для этого введем матрицу W = (wpb), p,b = 1,2,... ,т, где wpb — количество похожих дескрипторов между парой изображений pub. Изначально все wpb приравниваются к нулю. Далее перебираются все элементы 1}п, i = 1,2, ...,т, ] = 1,2,... Д(г), п = 1,2, ...,к, и компоненты матрицы W: w, ,¡ и w,¡ , увеличиваются на

' jn ljn'

единицу. В список предполагаемых кандидатов на сопоставление каждого изображения S¡ = (sí,s2» 1 = 1.2, ...,m, помещаютсят| номеров столбцов

наибольших элементов из i-й строки матрицы W. Каждое i-e изображение сопоставляется лишь с изображениями из списка S¡.

Для случая ограниченной оперативной памяти, недостаточной для размещения дерева дескрипторов всех особенностей на всех изображениях, во второй главе предлагается проводить разбиение множества входных изображений на перекрывающиеся подмножества. Разбиение проводится на основе приблизительных координат снимков, известных из навигационной системы АНПА, по пространственному признаку.

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

1Q

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

В третьей главе рассматривается задача вычисления положений и ориентаций снимков совместно с задачей определения положений точек дна, соответствующих особенностям, видимым одновременно на двух и более изображениях. Задача вычисления положения и ориентаций снимков состоит из двух этапов: поиск начального приближения решения и уточнение решения. Положение каждого снимка обозначается через сг = (cix, ciy, ciz), i = 1,2,... ,m, а для обозначения параметров ориентации использованы три эйлеровых угла: ri — (.ai>ßi>Yi)- При этом сама ориентация определяется произведением матриц поворота по трем осям: R(r-) = Rz(Y,)Ry (ß^Rj-Ca,). Дтя начальных приближений векторов с( и rf используются следующие обозначения:

С? = (4, С? , 4) и г° = (с4, ß°ylY°z).

Для вычисления начального приближения решения принимается плоский характер движения АНПА над дном. При этом связь между каждой 1-й парой изображений, где I = 1,2,..., п, а п - общее количество найденных связанных пар, характеризуется вектором timi(,), где i(i).jO) 6 {1,2, ...,т} - номера изображений, образующих 1-ю связанную пару. Нахождение этого вектора описывается во второй главе. Поскольку каждый вектор t1®'® представлен в системе координат j(Z)-ro изображения, описывается его перевод в глобальную систему координат:

di(0i(/) = V)fcosYv sinY;W)K0 (S)

f V-SinY; cosy¡J ' v '

Здесь через f обозначается нормализованное фокусное расстояние камеры (в диссертационной работе для представления координат изображений используется нормализованная система координат, согласно которой каждое изображение равномерно отмасштабировано до ширины 2, а начало координат сдвинуто в центр изображения). Из (4) и (5) следует, что d'^'O — вектор, направленный из центра j(i)-ro изображения в центр i(Z)-ro, что дает следующее уравнение относительно q®^ и с^у:

d«0K0 = (jp* (6)

Совокупность уравнений (6) для всех I приводит к системе линейных алгебраических уравнений Ах = Ь, где х = (с$х, с%у, с°х, с°у,..., c^_hx, b = (dSd2,...,dn), А = (ац), а с£х = 0 и с°,у = О (начало координат фотографической карты удобно выбрать в центре ш-го изображения). Блок а.ц описьшается следующим образом:

Здесь 02х2 — матрица размерности 2x2, состоящая из нулевых элементов. В общем случае система Ах - Ь будет переопределенной, так как число связей обычно больше, чем число изображений, поэтому вместо точного решения будем искать решение, минимизирующее ошибку е:

Вектор х, минимизирующий е, можно найти из нормального уравнения Qx = ATb, где Q = АТА. Матрица Q = (qу) - симметричная, положительно определенная и состоит из блоков qi;, i,j = 1,2,..., m-1, имеющих размерность 2x2. Общее число блоков в этой матрице равно (m-1)2. Каждый блок qi7- имеет ненулевые элементы только тогда, когда изображения с номерами i и j непосредственно связаны (31: i(i) = i, j(Z) = j или i(Z) =;', j(Z) = i). В большинстве задач компьютерного зрения количество связей между изображениями имеет порядок 2т -=- 8т, что приводит к разреженной структуре матрицы Q.

Далее в третьей главе рассматриваются различные методы решения систем линейных алгебраических уравнений с учетом их разреженности. Рассматривается LDLT декомпозиция матрицы системы Q, где D — диагональная матрица, a L — нижняя унитреугольная матрица. В результате LDLT разложения решение системы может быть найдено за три шага: 1) Lx' = ATb (прямая подстановка), 2) х" = D-1*', 3) LTx = х" (обратная подстановка). Особенность LDLT разложения заключается в сохранении нулевых элементов в начале каждой строки матрицы Q в матрице L. Данные нулевые элементы могут быть учтены в алгоритме решения. Чтобы получить много нулей в начале строк матрицы Q, необходимо упорядочить номера изображений таким образом, чтобы связанные изображения имели по возможности близкие номера. Для упорядочивания изображений в главе рассматривается обратный алгоритм Катхилла-Макки, метод вложенных сечений, модифицированный метод вложенных сечений с подбором разделителя и метод параллельных сечений.

Найденные в результате решения системы параметры с°х, с°у, j = 1,2,..., т, совместно с данными навигационной системы сД = d;-, = У] > а также вместе с предположением о близком к плоскому характеру движения АНПА (а?. - 0, = 0) дают начальные значения векторов cf и If. Для нахождения точных значений положений и ориентаций снимков в главе используется метод итеративного уточнения bundle adjustment. В данном

ц

методе относительно параметров положения Су, ориентации ij и координат точек пространства Xf, i = 1,2, ...,N, где N - количество точек, видимых одновременно на двух и более изображениях, решается задача минимизации ошибки Е:

N т i=lj=l

Здесь xj - двумерные координатные векторы особенности j-го изображения, соответствующие £-й точке дна, ах{ - координаты, полученные посредством проецирования точки X,- на j-e, изображение с использованием рассчитываемых параметров с;- и ij .

Поскольку координаты точки Xh видимой на изображениях }=h>h>->jm(!)> участвуют в задаче минимизации ошибки Я наравне с положениями и ориентациями снимков, в главе предлагается простой способ вычисления их начальных значений X?:

jm (О

v° - 1 V -уоi

Xi~m(i)LXi-

i=h

Здесь X°f определяются следующим образом:

. / cosy,- sin у,- 0\ , X°i=|-sin у, cosyу +

1 V о о 1/ 1

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

В завершение третьей главы описываются результаты тестирования алгоритмов решения разреженных систем линейных алгебраических уравнений на реальных и синтетических данных. Алгоритм вычисления начальных и точных значений ориентаций и положений изображений, а также координат точек пространства тестируется на реальных данных. Ошибка, даваемая данным алгоритмом, составляет в среднем 3 мм (при средней ширине зоны, охватываемой изображением в 1—2 м). Отметим, что данная ошибка лишь описывает рассогласование найденных особенностей и их вычисленных

положений. Реальная ошибка целиком зависит от плотности покрытия дна изображениями.

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

Алгоритм простой сшивки заключается в том, что для каждого изображения строится плоскость, аппроксимирующая участок рельефа, видимый на этом изображении. Далее изображение, описываемое данной плоскостью, проецируется на плоскость фотографической карты г = 0. Аппроксимирующая плоскость строится на основе точек Хк = (хк>Ук>2к)у гДе к € Щ, а Щ - множество номеров точек, видимых на у-м изображении, где ] = 1,2,..., т. Каждая точка Хк должна удовлетворять уравнению плоскости для /-го изображения

А]Хк + В]Ук + = -1. (7)

Перебрав все индексы к 6 Щ, получим систему линейных алгебраических уравнений с матрицей А, построенной из строк Ак ~ Ук* 2к). Вектор

правых частей В = (— 1,— 1,...,— 1)т имеет размерность \Щ |. Система с матрицей А может иметь множество решений при \Щ | < 3, может иметь единственное решение при \Щ | = 3 и не иметь точного решения в общем случае при | > 3. Для случая множественного решения в четвертой главе предлагается альтернативный подход. В случае единственного решения и в общем случае решение системы (7) можно найти, домножив левую и правую части системы слева на Ат:

АТА(А7,В,.(С,)Т = АТВ. (8)

Система (8) - система с тремя линейными алгебраическими уравнениями и тремя неизвестными, может быть однозначно решена. Решение данной системы в совокупности с коэффициентом Dj = 1 дает четыре коэффициента уравнения искомой аппроксимирующей плоскости для^го изображения.

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

ц

площадь, на которой располагаются точки Хк. Если обозначить площадь участка дна, видимого на у-м изображении, за а площадь, на которой сосредоточены все точки Хк, за то коэффициент надежности плоскости запишется следующим образом: г|у = ¿у/.^.

Значение т]у > 0.5 говорит о том, что плоскость рассчитана с достаточной точностью, тогда как значение г)у < 0.5 указывает на необходимость корректировки аппроксимирующей плоскости. Процедуры расчета площадей ¿у и ^ описываются в четвертой главе.

В случае, когда г|;- < 0.5, необходимо скорректировать полученную для ]-го изображения аппроксимирующую плоскость (либо найти ее в случае, когда [ < 3). Процедура коррекции предлагается в четвертой главе диссертационной работы. Коррекция заключается в использовании дополнительного предположения о перпендикулярности участка рельефа, охватываемого изображением, и оси 2 камеры, с которой это изображение получено.

Вектор, определяющий направление камеры в момент получения /-го изображения — третий столбец матрицы 11(1}). Данный вектор совпадает с нормалью аппроксимирующей плоскости в альтернативном решении:

4- = Щ = щъз. с) = 1*05)33.

Коэффициенты альтернативной аппроксимирующей плоскости у'-го изображения будем обозначать А], В'¡, Су, Зная первые три коэффициента, найдем четвертый:

Ц = 1*}Г X {.-¿¡Хк-Щ-Ук -кек)

Плоскость (А], В), С], £>;) следует использовать в качестве решения тогда, когда | < 3. Для других случаев решение получается комбинированием уравнений (7) и дополнительных уравнений, требующих параллельности вектора нормали аппроксимирующей плоскости (А], Щ, Су) и оси камеры (А], В'¡, Су). Дополнительные уравнения описываются как приравненное нулю векторное произведение этих векторов:

4Д МЛ (ВА~СА\ /о\ в> N 4 Ы са-АА = о .

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

O Cj -Bj

м = | —Cj o Áj B¡ -Áj o

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

(Ат А + a¡ Мт М) (Aj ,BJ,CJY = АТВ. (9)

Здесь <Xj — коэффициент, определяющий вклад дополнительных уравнений в общее решение. Данный коэффициент должен учитывать отношение площадей

Чу

В этой главе cl¡ = £¡SjPj, где Sj = (—5r|¡ + 2.5)3 - коэффициент разницы площадей, p¡ = ({Aj + Bf + tf) sin2 j - нормирующий фактор для дополнительных уравнений, fy - наименьший угол между прямыми, задаваемыми векторами (Aj, B¡, C¡) и (Á¡, B¡, Cj), a £¡ определяется так:

e¡ = 2 (xkAj + УкЩ + zkC¡ + Djf.

keK)

Такой коэффициент хорошо зарекомендовал себя на практике.

Зная аппроксимирующие плоскости, для каждого изображения можно определить функцию í)(u,w), проецирующую точку с координатами (u,w) на )-м изображении в точку на плоскости фотографической карты:

1 Cjx

+ t¡ (и, w)R(ij)iV;- (и, w)\ ij(u,w) = I Cjy + tj (u, w) R(i} )zVj (u, w) j.

Vjz + tj (u, w)R(x})3v;- (u, w)/ Здесь Vy(u,w) используется для обозначения трехкомпонентного вектора

Vj (и, w) = (и, w, fjY, а функция tj (и, w) задана следующим образом:

, __~Aj Ci* ~ BiCjy ~ CJCjz ~ DJ_

' W) AjR(ifavj (U, w) + BjR(Tj)2v¡(u, w) + C¡R(i;)3vy (u, w)" Функция íj(u,w) используется в четвертой главе для определения границ каждого j-го изображения на общей фотографической карте. Для определения цветового вклада каждой точки }-го изображения в точку фотографической карты с координатами (х, у) используется функция обратной проекции

ГЧх.уУ-

(f¡ +Rfo)21y + +

ГЧх.У) =

33Zj(.X.y) + Cjz fj (И(ГД2* + К6/)22У + R(.ri\2ZJ<x-y) + 5у)

Здесь % = , с;у, ) = —а для определения координаты щ использована функция

ч

В качестве альтернативы для простой сшивки применительно к рельефу с резким перепадом высот в четвертой главе рассматривается алгоритм сшивки на основе трехмерной модели дна. Трехмерная модель строится с помощью триангуляции облака точек Хь I — 1,2,..., /V. Для триангуляции используется итеративный алгоритм с динамическим кэшированием треугольников.

Особенности структуры задачи позволяют не определять функции прямого и обратного проецирования напрямую в случае сшивки на основе трехмерной модели. Функция прямого проецирования ^•(•и.и') нужна исключительно для того, чтобы оценить границы зоны на плоскости г = 0, куда проецируется ;'-е изображение. В случае, когда на плоскость г = О проецируется не все изображение, а только треугольники, содержащие точки Х/с, кеЩ, видимые на /-м изображении, границы можно определить как координаты крайней левой, крайней правой, крайней верхней и крайней нижней точек, входящих в треугольники, содержащие точки Хк.

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

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

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

РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

1. Предложен алгоритм для поиска связанных изображений в больших наборах изображений. Данный алгоритм учитывает низкую четкость снимков, нелинейное изменение освещения, высокую повторяемость однотипных объектов и другие особенности, характерные для подводных изображений. Для работы алгоритма не требуется упорядоченности изображений и априорного знания об их положениях.

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

3. Разработано программное средство «AUV photo stitcher», предназначенное для построения фотографических карт подводного дна на основе больших массивов подводных изображений, получаемых с АНПА.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

i

1. Камаев А.Н. Относительное ориентирование снимков низкой контрастности, полученных с АНПА, на основе точечных особенностей // Ученые заметки ТОГУ. - 2011. - Т. 2, № 2. - С. 32-42.

2. Камаев А.Н. Исследование алгоритмов упорядочивания коэффициентов систем линейных алгебраических уравнений, возникающих в задачах компьютерного зрения // Информатика и системы управления. — 2013. — № 3. -С. 32-44.

3. Камаев А.Н. Автоматическая сшивка изображений, полученных с АНПА при исследовании подводного дна // Тр. конф. ТТЮМО-5 (Владивосток, 30 сентября - 4 октября 2013 г.). - Владивосток, 2013. - С. 474-479.

4. Камаев А.Н. Создание панорамных карт подводного дна на основе больших массивов изображений // Тр. конф. Графикон 2013 (Владивосток, 16-20 сентября 2013 г.). - Владивосток, 2013. - С. 298-301.

5. Камаев АЛ. Позиционирование изрбражений морского дна, полученных с помощью АНПА // Подводные исследования и робототехника. — 2013. — № 2/16. — С. 38-47.

6. Камаев А.Н. AUV photo stitcher: Свидетельство о государственной регистрации программы для ЭВМ № 2014613051 от 17.03.2014. - М.: Федеральная служба по интеллектуальной собственности, 2014.

Камаев Александр Николаевич

ПОСТРОЕНИЕ ФОТОГРАФИЧЕСКИХ КАРТ ПОДВОДНОГО ДНА НА ОСНОВЕ БОЛЬШИХ МАССИВОВ ИЗОБРАЖЕНИЙ

Автореферат диссертации на соискание ученой степени кандидата технических наук

Редакционно-издательский отдел Федерального государственного бюджетного учреждения науки Института динамики систем и теории управления Сибирского отделения Российской академии наук 664033, Иркутск, ул. Лермонтова, д. 134 E-mail: rio@icc.ru

Подписано в печать 17.10.2014 г. Формат 60x84 1/16. Бумага писчая. Гарнитура Times New Roman. Печать цифровая.

Усл. печ. л. 1,1. Тираж 130 экз. Заказ 287. Отдел оперативной полиграфии издательства Тихоокеанского государственного университета 680035, Хабаровск, yjj. Тихоокеанская, 136.