автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Компьютерный метод оценки достоверных соответствий на стереоснимках

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

ТУПИЦЫН ИЛЬЯ ВЛАДИМИРОВИЧ

КОМПЬЮТЕРНЫЙ МЕТОД ОЦЕНКИ ДОСТОВЕРНЫХ СООТВЕТСТВИЙ НА СТЕРЕОСНИМКАХ

05.13.01 - Системный анализ, управление и обработка информации (космические и информационные технологии)

Автореферат

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

1 6 МАЙ 2013

Красноярск - 2013

005058454

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева», г. Красноярск

Научный руководитель: доктор технических наук, доцент

Фаворская Маргарита Николаевна

Официальные оппоненты: Ступина Алена Александровна

доктор технических наук, профессор, ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнёва», профессор кафедры системного анализа

Соловьев Николай Владимирович

кандидат технических наук, доцент, ФГАОУ ВПО «Санкт-Петербургский государственный университет

аэрокосмического приборостроения», доцент кафедры вычислительных систем и сетей

Ведущая организация: ФГБОУ ВПО «Сибирский государственный

технологический университет»

Защита состоится 14 июня 2013 года в 14 часов на заседании диссертационного совета Д 212.249.02 при Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнева по адресу: 660014, г. Красноярск, пр. им. газеты «Красноярский рабочий», 31.

С диссертацией можно ознакомиться в научной библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева

Автореферат разослан Д °) Олул 2013 г. Ученый секретарь м ~

диссертационного совета Л.А. Кузнецов

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

Актуальность работы.

Задача сопоставления точек на изображениях является фундаментальной проблемой компьютерного зрения. Значимость методов сопоставления точечных особенностей связана с их использованием при решении широкого круга задач цифровой обработки изображений (трехмерная реконструкция, составление панорам, ГИС-системы, совмещение аэрофотоснимков, роботы, игры на мобильных устройствах со встроенной камерой). В настоящее время в мире разработано большое количество методов и алгоритмов извлечения и сопоставления точечных особенностей. Как правило, такие методы используются совместно с устойчивыми методами оценки параметров моделей (метод RANSAC и его модификации), повышающими устойчивость сопоставления к шумам, искажениям, изменениям масштаба.

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

Вклад в теорию и практику создания систем извлечения и сопоставления точечных особенностей с использованием как фото- или видеоизображений, так и дополнительного оборудования связан с именами C.B. Гришин, Д.С. Ватолин, A.C. Конушин, Д.В. Жук, M. Pollefeys, A. Zisserman, A. Akbarzadeh, R. Yang, P. Debevec и многих других. Существенные результаты в данной области получены в отечественных работах, выполненных в Институте прикладной математики РАН, Московском государственном университете, Московском физико-техническом институте и в др, организациях. Вместе с тем, существующие методы, алгоритмы и их программные реализации не в полной мере удовлетворяют основным требованиям, диктуемым практикой применения таких систем. К этим требованиям относятся: скорость обработки данных; геометрическая достоверность полученных моделей; устойчивость к шумам и искажениям. Изложенные обстоятельства свидетельствуют о необходимости дальнейших исследований проблемы создания методов, алгоритмов и программных средств для оценки достоверных изображений на фото- и видеоизображениях.

Цель работы. Целью диссертационной работы является повышение эффективности сопоставления точечных особенностей на стереоснимках.

Поставленная цель определяет необходимость решения следующих

задач:

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

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

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

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

Область исследования. Работа выполнена в соответствии с пунктом 12 «Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации» паспорта специальностей ВАК (технические науки, специальность 05.13.01 - системный анализ, управление и обработка информации).

Методы исследования.

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

Научная новизна.

1. Предложена модификация метода линейного автоконтраста, применение которой позволяет увеличить количество найденных значимых особенностей на 20-40% в сравнении с обычным методом линейного автоконтраста при одинаковых начальных условиях.

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

3. Разработан новый иерархический метод оценки попадания точек в массив достоверных соответствий, отличающийся ускоренной процедурой выбора, которая основана на одновременном анализе 4 соответствий в локальных регионах изображения, позволяющей значительно сократить время сопоставления по сравнению с известным методом Я АКБ АС и его модификациями.

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

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

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

Программа «Построение карты глубины по откалиброванной стереопаре» (DepthMapBuilder) зарегистрирована в реестре программ для ЭВМ г. Москва 19 января 2012 года (свидетельство №2012610861).

Получен акт внедрения алгоритмического и программного обеспечения для автоматизированного построения трехмерных моделей городских сооружений по нескольким изображениям в ФБУ Красноярская лаборатория судебной экспертизы Минюста России.

Разработанное алгоритмическое и программное обеспечение передано для использования в учебном процессе Сибирского государственного аэрокосмического университета им. академика М. Ф. Решетнева (СибГАУ).

Основные положения, выносимые на защиту:

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

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

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

Апробация работы и публикации.

Основные положения и результаты диссертации докладывались и обсуждались на межрегиональной научно-практической конференции «Молодежь Сибири - науке России» (Красноярск, 2008), всероссийской научно-практической конференции творческой молодежи «Актуальные проблемы авиации и космонавтики» (Красноярск, 2008), международной научной конференции «Решетневские чтения» (Красноярск, 2008, 2009), всероссийской научно-практической конференции студентов, аспирантов и молодых ученых с международным участием «Молодежь и современные информационные технологии» (Томск, 2009), всероссийской научной студенческой конференции молодых ученых «Наука технологии инновации» (Новосибирск, 2009), всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий», (Улан-Удэ, 2009), всероссийской научной

конференции молодых ученых «Теория и практика системного анализа» (Рыбинск, 2010), международной конференции «Цифровая обработка сигналов и ее применение - DSPA'2011» (Москва, 2011), научно-технической конференции «Техническое зрение в системах управления-2012» (Москва, 2012), международной конференции и выставке «Цифровая обработка сигналов и ее применение» - DSPA'2013 (Москва, 2013).

По результатам диссертационного исследования опубликовано 19 печатных работ, из них 4 статьи в изданиях, рекомендованных ВАК, 14 тезисов докладов, 1 свидетельство, зарегистрированное в Российском реестре программ для ЭВМ.

Структура работы.

Работа состоит из введения, трех глав, заключения и библиографического списка. Основной текст диссертации содержит 124 страницы, изложение иллюстрируется 31 рисунком и 6 таблицами. Библиографический список включает 144 наименования.

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

Во введении обоснована актуальность темы, поставлена цель и

сформулированы задачи диссертации.

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

Устойчивые методы оценки параметров моделей предназначены для построения модели соответствия точек на изображениях стереопары, называемой фундаментальной матрицей. В подавляющем большинстве случаев для вычисления фундаментальной матрицы используются алгоритмы семейства RANSAC (Random sample consensus) (табл. 2). Модификации алгоритма RANSAC направлены на устранение его недостатков: отсутствие верхней границы выполнения, также существует вероятность того, что за заданное количество шагов не будет найдено соответствующее исходным данным решение.

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

Таблш/а 1

Классификация методов извлечения и сопоставления особых точек

Категория Методы Примеры

Обнаружение точечных особенностей Уголковые детекторы - Детектор Харриса - Детектор Моравеца - FAST (Features from accelerated segment test) - FREAK (Fast retina keypoint)

Детекторы световых пятен (blob) - SURF (Speed up robust features) - SIFT (Scale invariant features transform) - LoG (Laplacian of Gaussian) - DoG (Difference of Gaussian)

Детекторы устойчивых областей - MSER (Maximally stable extremal regions)

Сопоставление точечных особенностей Пикселыго-блочное сопоставление - NCC (Normalized cross correlation) - ZNCC (Zero-mean normalized cross correlation) - SSD (Sum of squared differences)

Сопоставление дескрипторов - SIFT - SURF - BRIEF (Binary robust independent elementary features) - BRISK (Binary robust invariant scalable keypoints) - ORB (Oriented BRIEF)

Таблица 2

Классификация устойчивых методов оценки параметров моделей

Модификации Описание Примеры

Направленные на увеличение скорости — частичная оценка — оценка с помощью упрощенного алгоритма построения модели - оценка на основе выборки -оцепка некоторого заданного количества точек. -Randomized RANSAC -Progressive RANSAC -RANSAC with bail-out test -NAPSAC (N Adjacent Points SAmpIe Consensus)

Направленные на повышение надежности - адаптивное прекращение — остановка алгоритма по дополнительному условию - локальная оптимизация -выборка исходных данных на основе априорной информации. -MAPSAC (Maximum a posteriori sample consensus) -uMLESAC -AMLESAC (Adaptive MLESAC) -pbM-estimator (Projection based M-estimator)

Направленные на повышение точности - выборка исходных данных на основе априорной информации - использование для оценки функции потерь. -Locally optimized RANSAC -RANSAC for (quasi-) degenerate data - MLESAC (Maximum Likelihood Estimation Sample Consensus)

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

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

Пусть дана исходная сцена 6с и пара ее проекций на плоскости съемки /,/', а С и С' - центральные точки камер, которыми ведется съемка. Пусть X - вектор однородных координат точки сцены 5с, х -вектор однородных координат проекции этой точки на плоскости I, х'-

Рисунок 1. Эпиполярная геометрия

Плоскость, определяемая точками С, С', X, называется эпиполярной плоскостью. Пересечение эпиполярной плоскости с плоскостями проекций определяет эпиполярные линии (1, Г). Необходимо найти такое преобразование Б, которое каждой точке х изображения / ставит в соответствие эпиполярную линию Г, т.е.

1';Кх ■ (ч

х Кх=0.

Для этого с помощью преобразования Ас1 на плоскостях I, Г необходимо найти множество особых точек

РР = {1ри Гр2, ..., Гр„ ...} , 0 < / < Ы, (2) ЕР' = {ГР1', ÍP2', ■■■, --•} , о <; <М, (3) где Гр, - вектор однородных координат особых точек на плоскости /; Тривектор однородных координат особых точек на плоскости /'; Ы, М -

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

8 = {вь...,вь...} , 0<к<К, (4)

где - вектор соответствий, состоящий из индексов особых точек, К — количество соответствий. На последнем шаге с помощью преобразования Аг вычисляется матрица

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

шах .Упил / .Уггпп ' (5)

X — X .

Щах тт

где х - текущее значение яркости пиксела, а у - новое значение.

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

Таблица J

Сравнительная характеристика существующих систем совмещения стереоизображений

Название Описание системы

OpenCV (США) Библиотека алгоритмов компьютерного зрения, обработки изображений и численных алгоритмов общего назначения с открытым исходным кодом. Содержит функции извлечения и сопоставления особых точек, реализован алгоритм RANSAC.

Arc 3D (Бельгия) Веб-сервис, предназначенный для построения 3D моделей объектов по набору изображений. Построение может длиться несколько часов.

PhotoModeller (Канада) Программное средство для автоматизированного построения облака трехмерных точек объекта по стереопарным изображениям.

iWitnessPRO (США) Программно-аппаратный комплекс, предназначенный для построения трехмерных моделей реальных объектов. Используется как ПО, так и дополнительное маркировочное и измерительное оборудование.

MetaCreations Canoma (США) ПП для автоматического построения формы трехмерных объектов по набору изображений. Позволяет реконструировать только простые объекты.

Project Photofly (США) Веб-сервис Autodesk, для построения трехмерных моделей по набору изображений.

Для выделения особых точек используется определитель матрицы Гессе. Матрица Гессе получается с помощью дискретизированных масок, аппроксимирующих фильтр Гаусса-Лапласа. Использование дискретизированных масок позволяет добиться повышенной устойчивости к вращению, и его можно эффективно вычислить с помощью интегральной матрицы изображения. Поиск точечных особенностей производится на обоих изображениях стереопары. Следующий шаг — сопоставление найденных точечных особенностей. Для сопоставления точечных особенностей используется новый иерархический метод, обладающий высокой скоростью работы и инвариантностью к искажениям. Достижение устойчивости происходит за счет вычисления направлений градиента (Сгл, Су) в окрестности <Т2 особой точки размером (2к+ 1)х(2к+ 1) пиксел, используя оператор Собела:

"-1 0 г "-1 -2 -Г

-2 0 2 ООО (6)

-1 0 1 1 2 1

Однако оператор Собела применяется не непосредственно к исходному изображению, а к его Гауссиану <32:

с; = с^сх,о7; = с1*ау , (7)

1 *у > где =-г-у 2а'' - функция Гаусса.

2ла

Чем больше окрестность особой точки, тем точнее вычисляется направление градиента, однако при этом затрачивается больше вычислительных ресурсов. Фильтр Гаусса применяется для устранения посторонних шумов на изображении и снижения влияния мелких деталей изображения на вычисление общего направления. Для этого фильтр применяется с большим значением среднеквадратичного отклонения а (как правило, а = 2). Тогда направление вектора градиента в любой точке окрестности вычисляется как:

0 = агйап

хС?1 Ч у У

(8)

а длина вектора градиента определяется по формуле:

е^М^Г (9)

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

к к

X Z©(*0 +Uyü+j)

© =tdlt±--ПО)

(2k +1)2 - 6 ' 1 j

к к

Gmeo" = (2k + l y-b ' (11}

где (x0,y0) - координаты точечной особенности, Ь — количество так называемых «плохих» точек окрестности, т. е. точек, в которых значения G„ Gy равны нулю.

Также, помимо направления обобщенного вектора по окрестности точечной особенности, вычислим направления в окрестностях точек Ptu Pt2, координаты (х, у) которых равны: х = к* cosí© + а) + Хг. ,

(12)

у = к* sin(© + «) + >'„ , где © - направление вектора градиента в особой точке, а - угол поворота, к - величина шага. Для окрестности точки Pt\ угол а выбирается равным а = тс/2, a для окрестности точки PU а = Зп/2. На рис. 2 приведен пример изображения, на котором показаны векторы направлений в окрестностях точечных особенностей.

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

Рисунок 2. Вычисление направлений в окрестностях особых точек

Сравнение полученных областей производится с помощью нормализованной кросс-корреляции Ж7С:

хсс- .л'У (13)

2Л+1 , Лм 2 V ;=о

Далее для сопоставления всех найденных точечных особенностей строится матрица похожести размерностью где N - количество

точечных особенностей левого изображения, а М - количество точечных особенностей правого изображения. Элементы матрицы представляют собой результат вычисления функции нормализованной кросс-корреляции (выражение (13)), при этом минимальные элементы матрицы будут соответствовать наиболее похожим особым точкам. Следует учитывать, что одна особая точка на одном изображении может соответствовать только одной особой точке на другом изображении. Исходя из данного ограничения, построим алгоритм сопоставления точечных особенностей: Шаг 1. Вычисление матрицы похожести. Шаг 2. Вычисление максимального элемента матрицы. Шаг 3. Поиск минимального элемента матрицы:

3.1. Если минимальный элемент равен максимальному элементу, тогда алгоритм прекращает свою работу.

3.2. Если значение минимального элемента меньше максимального, тогда переход к шагу 4.

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

Шаг 5. Установить значения элементов строки и столбца матрицы равными максимальному элементу и перейти к шагу 3.

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

а) б) в)

Рисунок 3. Стереопара и построенное по ней векторное поле соответствий: а) левое изображение, б) правое изображение, в) поле соответствий

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

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

Шаг 1. Установить критерий попадания точек в массив достоверных соответствий (например, значение ЫСС меньше заданного порога).

Шаг 2. Случайным образом выбрать 8 точек, по которым с помощью восьмиточечного алгоритма строится гипотеза (при использовании семиточечного алгоритма необходимо выбрать 7 точек).

Шаг 3. С помощью полученной гипотезы вычислить соответствия для остальных точек.

Шаг 4. Для каждого вычисленного соответствия произвести оценку его попадания в массив достоверных соответствий.

Шаг 5. Шаги 2—4 повторить заданное количество раз.

Шаг 6. Выбрать модель с наибольшим количеством достоверных соответствий.

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

Разделим изображения стереопары на регионы с помощью сетки заданного размера, например 25% от ширины и высоты изображения. Таким образом, изображение делится на 16 областей <2, в каждой из которых выбирается 4 особых точки (рис. 4).

Рисунок 4, Деление изображения на регионы и выбор четырех особых точек в первом регионе

Выбранные четыре соответствия используются для построения четырех треугольных областей. Обозначим область на левом изображении как Reg,, а область на правом изображении - как Reg\. Для каждой пары из полученных треугольников вычислим соотношение ratio;.

ratio i =14. (14)

Reg',

Нормализация соотношений вида (14) производится путем их деления на максимальное значение из четырех для каждой из 16 областей:

ratio =-— кл fjo = {ratio,, ratio-,, ratio,, ratio 4}, (15)

' mwt{RATIO)

в результате чего итоговая величина соотношения ratioQ по области Q

будет определена как _ ____

ratioQ = шах{ЁШ0)- min{Штю), RATIO = ratio2,ratioъ,ratio,). (15)

Если значение ratio0 меньше некоторого заданного значения е, тогда все сопоставления выбранного региона помечаются как достоверные соответствия; в противном случае сопоставления считаются недостоверными. Таким образом, наиболее достоверная модель определяется по наибольшему количеству достоверных соответствий.

В третьей главе диссертации приводятся результаты экспериментов, проведенных с реализацией предлагаемых алгоритмов и их сравнение с ранее известными алгоритмами. Проведение экспериментов осуществлялось с помощью разработанного экспериментального программного обеспечения. Разработанное экспериментальное программное обеспечение имеет модульную структуру. Общая схема модулей представлена на рис. 5. Краткое описание модулей приведено в табл. 4. При проведении экспериментов использовались реализованные алгоритмы из библиотеки OpenCV 2.3.1, а также авторские реализации алгоритмов.

Рисунок 5. Схема модулей экспериментального программного продукта

Таблица 4

Описание модулей экспериментального программного обеспечения

Название модуля Функциональная характеристика

1. Интерфейсный модуль Обеспечивает взаимодействия экспериментального программного средства с внешней средой

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

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

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

3. Модуль обработки стереоизображений Включает в себя структуры, классы, методы и функции обработки стереоизображений

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

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

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

1. Открытая база стереоизображений NASA (более 200 стереоизображений).

2. Vision and Autonomous Systems Center's Image Database содержащая 1000 стереоизображений.

3. Amsterdam Library of Object Images, включающая в себя более 1500 изображений 750 объектов в разных масштабах.

4. Набор тестовых изображений Миддлберийского колледжа (40 тестовых стереопар).

Обработка экспериментальных стереоизображений показала значительное увеличение числа найденных точечных особенностей после применения алгоритма сегментного автоконтраста к исходным изображениям. Увеличение числа найденных особенностей позволяет повысить порог алгоритма их нахождения и увеличить количество значимых особых точек. В табл. 5 представлен результат эксперимента для изображений размером 1024x768.

Таблица 5

Зависимость количества обнаруженных особенностей от алгоритма

сегментации

Без обработки Пороговая сегментация Мультипороговая сегментация Алгоритм Краскала Пирамидальная сегментация

1350,59 1512,39 2175,4 2083,26 2028,49

SIFT 1373,42 1621,99 2089,3 2211,07 2087,3

SURF 1421,36 1644,1 2271,34 2285,55 2269,06

GLOH 1400,18 1481,97 2209,73 2240,83 2152,16

FAST 1370,3 1506,06 2174,58 2118,44 2123,72

MSER 1440,95 1515,77 2128,87 1986.5 2183,01

Также экспериментально подтверждена высокая степень инвариантности предлагаемого в диссертации дескриптора к повороту (рис. 6). Количество верно сопоставленных особенностей в среднем на 5% выше, чем у существующих аналогов. При этом инвариантность к размытию и изменению освещенности находится на уровне существующих дескрипторов. Скорость работы предлагаемого дескриптора при этом выше на 1%, чем у дескриптора SURF.

Рисунок б. График зависимости числа корректно сопоставленных особенностей от угла поворота изображений стереопары

£ 100

Поворот

В BRIEF

■ LAZY K ORB

■ RIFF 58 SIFT S SURF

B ripe/]/!. fleCKp.

30 40 45 50 60 70 80 90 100 110 120 130 135 140 150 160 170 180

Угол поворота, градусы _____

Предлагаемый в работе дескриптор показывает хорошую устойчивость к изменению яркости. Такой результат обусловлен нормализацией уровней яркости пикселов из окрестности сравниваемых особых точек. При уменьшении яркости минимальное значение находится между дескрипторами SIFT и SURF и составляет величину 54%. В случае увеличения яркости число верно сопоставленных особенностей равно 56% (рис. 7).

Рисунок 7. График зависимости количества верно сопоставленных особенностей от величины изменения яркости

Изменение яркости

■ BRIEF

■ LAZY

SORB

■ RIFF

■ SIFT

В SURF

и Предо, дескр.

Величина изменения

На рис. 8 показан график зависимости количества верно сопоставленных особенностей от радиуса размытия исходного изображения фильтром Гаусса. Результаты экспериментов показывают, что разработанный дескриптор обладает устойчивостью к размытию на уровне дескрипторов ORB и RIFF. Минимальное число верно сопоставленных особенностей составляет порядка 30% при радиусе размытия равном 15 пике., что вполне ожидаемо, так как дескриптор использует яркости пикселов в окрестности точечной особенности. Поскольку в большинстве случаев стереопарные изображения получаются цифровыми камерами с одинаковыми или близкими внутренними параметрами, либо одной камерой со стереообъективом, случаи, когда требуется повышенная устойчивость дескриптора к размытию, являются довольно редкими.

В табл. 6 представлены результаты экспериментов по оценке времени построения дескрипторов. Результат эксперимента показал, что разработанный дескриптор обладает в среднем на 1% меньшим временем вычисления, чем дескриптор SURF.

о 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Радиус размытия, пике

Рисунок 8. График зависимости числа верно сопоставленных особенностей от радиуса размытия фильтром Гаусса

Размытие

В BRIEF

■ LAZY a ORB

■ RIFF

■ SIFT SSSURF

В Предл. дескр.

Таблица 6

Время вычисления дескрипторов

Количество особых точек Время вычисления, мс

BRIEF LAZY ORB RIFF SIFT SURF Предлагаемый дескриптор

250 3,2 20,4 11,9 11,1 60,7 25,3 27,7

500 5,5 36,1 20,1 18,8 9 8,7 j 45,6 45,3

750 7,2 52,5 36,6 35,5 153,5 57,2 56,1

1500 13,1 90,4 65 64,4 241,4 110,9 100,4

2000 19,8 126 83,7 83,1 299,8 199,5 180,4

Для экспериментов с алгоритмами оценки параметров моделей были выбраны наиболее известные и хорошо зарекомендовавшие себя алгоритмы семейства КАШ АС. Оценивалось время выполнения алгоритма в миллисекундах, а также точность вычисления фундаментальной матрицы. Оценка достоверности фундаментальной матрицы на каждом изображении осуществлялась с помощью евклидового расстояния. На рис. 9 представлен результат оценки времени работы алгоритмов. Для эксперимента выбиралось различное исходное количество соответствий (от 500 до 15000).

Результат эксперимента показал, что предлагаемый иерархический алгоритм показывает значительно лучшую производительность в сравнении с аналогами. Время его выполнения меньше, чем у алгоритма ЯАКБАС в среднем в 3,2 раза.

■ RANSAC

■ RANSAC with Bail-out test Ш R-RANSAC Td,d test

■ R-RANSAC SPRT H PROSAC

95 GASAC В MAPSAC iluMLESAC Щ AMLESAC iS LO-RANSAC

m m sac

MLESAC

700

600

і и S00

0

Иерархический алгоритм '

15000 8000

¡000 2000 1000 Количество соответствий

500

Рисунок 9. Гистограмма зависимости времени вычисления фундаментальной матрицы от количества исходных соответствий.

На рис. 10 представлен результат вычисления величины ошибки при построении фундаментальной матрицы. Величина ошибки оценивалась с помощью функции евклидового расстояния между попаданиями для результирующей гипотезы. Гистограмма показывает, что быстрые модификации алгоритма RANSAC дают значительно более высокое значение ошибки, чем алгоритмы, направленные на увеличение точности. Например, R-RANSAC (Randomized RANSAC) with bail-out test, показывает величину ошибки в среднем на 10% больше, чем RANSAC, в то время как LO-RANSAC (Locally optimized RANSAC) показывает значительно меньшую величину. Следует отметить, что в случаях малого количества соответствий алгоритмы R-RANSAC with SPRT (Sequential Probability Ratio Test), PROSAC (Progressive RANSAC) и AMLESAC показывают большую величину ошибки в сравнении с другими алгоритмами. Это говорит о том, что указанные алгоритмы имеют более высокие требования к исходным данным. Величина ошибки при использовании иерархического алгоритма сопоставима с величинами ошибок аналогов и в среднем на 45% ниже, чем величина ошибки при использовании алгоритма RANSAC. Такой результат говорит о пригодности использования разработанного иерархического алгоритма в требовательных к времени выполнения системах стереозрения.

Как уже говорилось ранее, алгоритмы сопоставления стереоизображений являются довольно ресурсоемкими. Поскольку эксперименты проводились на ЭВМ с процессором, позволяющим производить параллельную обработку данных за счет многоядерной архитектуры и использования технологии Hyper-Threading, при реализации разработанных алгоритмов было решено учесть эту особенность. Параллельности обработки стереоснимков удалось достичь за счет их разделения на равные части с учетом обработки фильтрами границ и

обработки выделенных частей в отдельных потоках. На этапах сопоставления точечных особенностей и вычисления фундаментальной матрицы параллельность обработки достигается за счет формирования потоков обработки особых точек. Результаты сравнения скорости вычислений в процентном соотношении представлены на рис. 11. Аналогичное сравнение проводилось на ЭВМ с процессором AMD FX-8170, построенном на архитектуре Bulldozer.

140 120

60

20

--I- 1 і 1 -§-—

1 1 Jl і;__ДІЇ1

Í И І Ш'т ¡Hs.....її ■Ato,

15000

8000 2000 1000 Количество соответствий

В RANSAC

■ RANSAC with Bail-out test BR-RANSACTd.dtest

■ R-RANSAC SPRT aPROSAC

IS GASAC В MAPSAC IS uMLESAC Ш AMLESAC В LO-RANSAC m MSAC BMLESAC

а Иерархический алгоритм

Рисунок 10. Гистограмма зависимости величины ошибки от исходного количества соответствий.

Количество потоков

- Intel

AMD

—»—

б) в)

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

123456789 10 Количество потоков

123456789 10 Количество потоков

Отдельно оценивалось время предварительной обработки изображений (рис. 11а), время извлечения и сопоставления точечных особенностей (рис. 116), а также время выполнения алгоритма оценки параметров моделей (рис. 11 в). Как видно из графиков, в случаях, когда используется более 4 потоков, процессор AMD дает больший прирост производительности. При этом стоить отметить, что общее время выполнения алгоритма больше, чем на процессоре Intel. Также предложенный алгоритм был реализован с использованием технологии CUDA от NVidia. Технология CUDA позволяет использовать графический процессор для математических вычислений общего назначения. На рис. 12 представлен график зависимости изменения производительности от количества выполняемых потоков.

100 90 80 70 60 50 40 30 20 10 0

CUDA

- предварительная обработка извлечение и сопоставление робастные оценки

V.

13 5

7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 Количество потоков

Рисунок 12. Зависимость времени выполнения алгоритма от количества потоков на ГП с поддержкой технологии СИЛА

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

В заключении сформулированы основные результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Модифицирован метод линейного автоконтраста. Предложенная модификация позволяет компенсировать неравномерность диапазона контраста обрабатываемого изображения.

2. Разработан дескриптор особых точек, использующий направление и величину вектора градиента как в окрестности особой

точки, так и в окрестностях пары точек, расположенных на перпендикуляре к направлению градиента.

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

4. Разработан экспериментальный комплекс для тестирования алгоритмов извлечения и сопоставления точечных особенностей. Модули комплекса реализованы в виде программ для ЭВМ. Проведены эксперименты с различными типами стереопар.

5. Экспериментальные исследования показали, что предложенная модификация метода линейного автоконтраста позволяет увеличить количество значимых найденных особенностей на 20-40%. Предложенный дескриптор обладает в среднем на 5% большей устойчивостью к искажениям, при этом обладает на 1% лучшей производительностью, чем один из самых близких по характеристикам дескриптор SURF. Новый алгоритм оценки фундаментальной матрицы при сравнимой величине ошибки выполняется на 20% быстрее алгоритмов семейства RANSAC.

Основные положения и результаты диссертационной работы представлены в следующих работах автора (знаком * обозначены работы, опубликованные в издании, включенном в список изданий, рекомендованных ВАК для опубликования результатов диссертационных исследований):

1. Тупицын, И.В. Иерархический метод поиска соответствующих точек на стереоизображениях / М.Н. Фаворская, И.В. Тупицын // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - Красноярск, 2012. С. 62-67.

2. *Тупицын, И.В. Реконструкция трехмерной модели объекта на основе стереопары при решении задач 3D моделирования / И.В. Тупицын // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - Красноярск, 2011. С. 212-216.

3. * Тупицын, И.В. Извлечение и сопоставление точечных особенностей на неоткалиброванной стереопаре / И.В. Тупицын // Вестник РГАТА - Рыбинск, 2011. С. 199-202.

4. "'Тупицын, И.В. Быстрый алгоритм реконструкции промежуточных ракурсов по стереопаре / И.В. Тупицын // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - Красноярск, 2010. С. 55-59.

5. Тупицын, И.В. Построение системы совмещения стереоизображений //В материалах 15-й международной конференции и выставке «Цифровая обработка сигналов и ее применение», М. В 2 т. Т. 2, 2013. С. 35-38.

6. Тупицын, И.В. Быстрый алгоритм реконструкции трехмерной модели объекта по стереопаре // В материалах 13-й международной конференции «Цифровая обработка сигналов и ее применение -ББРА'гОП», М. В 2 т. Т. 2, 2011. С. 199-202.

7. Тупицын, И.В. Быстрый алгоритм совмещения изображений // В трудах I всероссийской научной конференции молодых ученых «Теория и практика системного анализа», в Т. 2. - Т.2. - Рыбинск: РГАТА, 2010. - С. 193-198.

8. Тупицын, И.В. Система реконструкции промежуточных ракурсов изображений по стереопаре // В материалах X Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий», Восточно-Сибирский государственный технологический университет. Улан-Удэ, 2009. - С. 469472.

9. Тупицын, И.В. Стерео реконструкция с использованием метода динамического программирования // В материалах всероссийской научной студенческой конференции молодых ученых «Наука технологии инновации», Новосибирский государственный технический университет. Новосибирск, 2009. - С. 248-250.

10. Тупицын, И.В. Классификация методов восстановления промежуточных ракурсов при стереосъемке // В сб. материалов XII Международной научной конференции Решетневские чтения, 2008. С. 361362.

11. Тупицын, И.В. Построение карты глубины по откалиброванной стереопаре (Бер^хМарВшИег) / И.В. Тупицын, М.Н. Фаворская // свидетельство №2012610861. Зарегистрировано в Реестре программ для ЭВМ г. Москва, 19 января 2012 года.

Тупицын Илья Владимирович Компьютерный метод оценки достоверных соответствий на стереоснимках

Автореферат

Подписано к печати Формат 60x84/16. Бумага писчая. Печ. л. 1.0 Тираж 100 экз. Заказ №

Отпечатано в отделе копировальной и множительной техники СибГАУ 660014 г. Красноярск, пр. им. газеты «Красноярский рабочий», 31

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева (СибГАУ)»

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

Тупицын Илья Владимирович

КОМПЬЮТЕРНЫЙ МЕТОД ОЦЕНКИ ДОСТОВЕРНЫХ СООТВЕТСТВИЙ НА СТЕРЕОСНИМКАХ

Специальность 05.13.01 - системный анализ, управление и обработка информации (космические и информационные технологии)

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

Научный руководитель -доктор технических наук Фаворская М. Н.

Красноярск - 2013

Содержание

ВВЕДЕНИЕ....................................................................................................5

1. Анализ существующих методов и систем сопоставления стереоизображений................................................................................................10

1.1. Общая схема решения задачи стереореконструкции....................10

1.2 Методы обнаружения точечных особенностей на изображениях 13

1.2.1 Детекторы углов.........................................................................13

1.2.2 Детекторы пятен.........................................................................17

1.3 Алгоритмы сопоставления точечных особенностей.................20

1.3.1 Алгоритмы, основанные на вычислении функции окрестности особой точки............................................................................22

1.3.2 Алгоритмы, использующие дескрипторы особых точек.....23

1.3.3 Вычисление дескрипторов в методах SIFT и SURF.............27

1.3.4 Дескриптор DAISY..................................................................32

1.3.5 Дескриптор BRIEF...................................................................34

1.3.6 Дескриптор BRISK.....................................................................35

1.4 Обзор методов оценки параметров моделей..............................37

1.5. Обзор существующих программных решений..............................43

1.5.1 Библиотека «OpenCV».............................................................43

1.5.2. Продукты «Leica Geosystems»..................................................44

1.5.3. Программа «AgiSoft StereoScan».............................................46

1.5.4. Пакет «Strata Foto 3D»..............................................................47

1.5.5. Программа «3D SOM»..............................................................48

1.5.6. Сервис «Project Photofly»..........................................................49

1.5.7. Программа «ARC 3D»...............................................................50

1.5.8. Программа «PhotoModeler»......................................................50

1.5.9. Программно-апапаратный комплекс «Photometrix iWitnessPRO»..................................................................................................51

1.5.10. Программный продукт «MetaCreations Canoma»..................51

Выводы по главе......................................................................................52

2. Метод построения трехмерной модели объекта по стереопаре.....54

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

2.2 Математическая модель стереореконструкции.........................56

2.3 Предварительная обработка........................................................59

2.4 Извлечение и сопоставление точечных особенностей.............62

2.5 Фундаментальная матрица..........................................................68

2.6 Применение метода оценки параметров моделей.....................70

2.7 Разработка алгоритма совмещения изображений стереопары 74

2.8 Выводы по главе...........................................................................76

3. Разработка программного обеспечения нахождения соответствующих точек на стереоизображениях и экспериментальные исследования................78

3.1. Структурная схема экспериментального программного обеспечения сопоставления стереоизображений...........................................78

3.2. Описание модулей экспериментального программного обеспечения........................................................................................................79

3.3. Использование параллельных вычислений при реализации модулей экспериментального программного продукта.................................82

3.4. Результаты экспериментальных исследований.............................87

3.4.1 Предварительная обработка....................................................88

3.4.2 Дескриптор точечных особенностей........................................90

3.4.3 Алгоритмы оценки параметров моделей.................................98

3.5. Внедрение экспериментального программного комплекса.......101

3.6. Выводы по главе.............................................................................103

ЗАКЛЮЧЕНИЕ..........................................................................................105

Библиографический список......................................................................110

ВВЕДЕНИЕ

Актуальность работы.

Задача сопоставления точек на изображениях является фундаментальной проблемой компьютерного зрения. Значимость методов сопоставления точечных особенностей связана с ее использованием при решении широкого круга задач цифровой обработки изображений (трехмерная реконструкция, составление панорам, ГИС-системы, совмещение аэрофотоснимков, роботы, игры на мобильных устройствах со встроенной камерой). В настоящее время в мире разработано большое количество методов и алгоритмов извлечения и сопоставления точечных особенностей. Как правило, разработанные алгоритмы используются совместно с устойчивыми методами оценки параметров моделей (метод RANSAC и его модификации), повышающими устойчивость сопоставления к шумам, искажениям, изменениям масштаба [12, 13, 139].

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

Вклад в теорию и практику создания систем извлечения и сопоставления точечных особенностей с использованием как фото- или видеоизображений, так и дополнительного оборудования связан с именами C.B. Гришин [8], Д.С. Ватолин, A.C. Конушин [17,37,38,39], Д.В. Жук [9,10], M. Pollefeys, A. Zisserman [73,111,132,134], A. Akbarzadeh, R.Yang [142], O.Chum [59, 60, 61] и многих других. Существенные результаты в данной области получены в отечественных работах, выполненных в Институте прикладной

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

Цель работы. Целью диссертационной работы является повышение эффективности сопоставления точечных особенностей на стереоснимках.

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

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

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

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

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

Методы исследования.

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

Научная новизна.

1. Предложена модификация метода линейного автоконтраста, применение которой позволяет увеличить количество значимых особенностей на 20-40% в сравнении с обычным методом линейного автоконтраста при одинаковых начальных условиях.

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

3. Разработан новый иерархический метод оценки попадания точек в массив достоверных соответствий, отличающийся ускоренной процедурой выбора, которая основана на одновременном анализе 4 соответствий в локальных регионах изображения, позволяющей значительно сократить время сопоставления по сравнению с известным методом ЯАКБАС и его модификациями.

Практическая значимость и реализация

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

Программа «Построение карты глубины по откалиброванной стереопаре» (ОерАМарВиПёег) зарегистрирована в реестре программ для ЭВМ г. Москва 19 января 2012 года (свидетельство №2012610861).

Получен акт внедрения алгоритмического и программного обеспечения для автоматизированного построения трехмерных моделей городских сооружений по нескольким изображениям в ФБУ Красноярская лаборатория судебной экспертизы Минюста России.

Разработанное алгоритмическое и программное обеспечение передано для использования в учебном процессе Сибирского государственного аэрокосмического университета им. академика М. Ф. Решетнева (СибГАУ).

Основные положения, выносимые на защиту:

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

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

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

Апробация работы и публикации

Основные положения и результаты диссертации докладывались и обсуждались на межрегиональной научно-практической конференции «Молодежь Сибири - науке России» (Красноярск, 2008), всероссийской научно-практической конференции творческой молодежи «Актуальные проблемы авиации и космонавтики» (Красноярск, 2008), международной научной конференции «Решетневские чтения» (Красноярск, 2008, 2009), всероссийской научно-практической конференции студентов, аспирантов и молодых ученых с международным участием «Молодежь и современные информационные технологии» (Томск, 2009), всероссийской научной студенческой конференции молодых ученых «Наука технологии инновации» (Новосибирск, 2009), всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий», (Улан-Удэ, 2009), всероссийской научной конференции молодых ученых «Теория и практика

системного анализа» (Рыбинск, 2010), международной конференции «Цифровая обработка сигналов и ее применение - 08РА'2011» (Москва, 2011, 2013), научно-технической конференции «Техническое зрение в системах управления-ТЗСУ-2012» (Москва, 2012).

По результатам диссертационного исследования опубликовано 19 печатных работ, из них 4 статьи в изданиях, рекомендованных ВАК, 14 тезисов докладов, 1 свидетельство, зарегистрированное в Российском реестре программ для ЭВМ.

Структура работы

Работа состоит из введения, трех глав, заключения и библиографического списка. Основной текст диссертации содержит 124 страницы, изложение иллюстрируется 31 рисунком и 6 таблицами. Библиографический список включает 144 наименования.

1. Анализ существующих методов и систем сопоставления стереоизображений

Области применения стереореконструкции достаточно широки: 3D-томография и рентген, графические рабочие станции CAD/CAM, отображение оперативной обстановки (авиадиспетчерские, аварийно-спасательные службы), роботы, развлекательная сфера, геоинформационные системы [109, 110, 127]. В настоящее время существует широкий спектр алгоритмов сопоставления стереоизображений, которые, как правило, разрабатываются для решения конкретных прикладных задач и имеют различные показатели. Но, несмотря на разнообразие методов и сфер применения систем сопоставления стереоизображений, существует общий подход к решению задачи стереореконструкции [1, 3, 5, 6, 7, 19, 41]. В главе подробно описана общая схема решения задачи стереореконструкции. Также рассмотрены существующие методы извлечения и сопоставления особых точек и методы оценки параметров моделей. Приведен обзор существующих программных решений.

1.1. Общая схема решения задачи стереореконструкции

Входными данными алгоритма стереореконструкции является стереопара - совокупность двух плоских перспективных изображений одного и того же объекта, полученных с двух разных точек зрения [140]. Основная проблема заключается в нахождении общих точек на изображениях стереопары, т. е. в их соответствии друг другу, в соответствии с установленными ограничениями на исходную стереопару. Решение задачи включает в себя несколько этапов, представленных на рис. 1.1. В настоящее время во всем мире ведутся работы по каждому из представленных этапов, и их можно рассматривать как отдельные проблемы компьютерного зрения.

/ Левое / изображение

\ /

Предварительная обработка

N

Поиск точечных особенностей

/ Правое / изображение

\ /

Предварительная обработка

N /

Поиск точечных особенностей

Рисунок 1.1. Общий алгоритм стереосопоставления.

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

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

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

Последний шаг состоит в построении модели отображения координат точек одного изображения в координаты точек другого. Для этого необходимо применение устойчивых методов оценок параметров модели. Подобные методы, как правило, выполняются итерационно, заданное количество шагов [33, 142, 144]. За одну итерацию метод выполняет выборку необходимого количества для построения модели данных, после чего строится модель и оцениваются ее параметры на основании оставшихся данных. По окончании вы-

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

1.2 Методы обнаружения точечных особенностей на

изображениях

Обнаружение точечных особенностей на изображениях являетс�