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

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

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

Содержание

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

Введение диссертации (часть автореферата) на тему «Компьютерный метод оценки достоверных соответствий на стереоснимках»

ВВЕДЕНИЕ

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

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

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

Обнаружение точечных особенностей на изображениях является фундаментальной проблемой компьютерного зрения и используется при решении большого количества задач [101]. Все современные детекторы можно разделить на детекторы углов, детекторы пятен (blob) и детекторы устойчивых областей. Краткая классификация существующих методов представлена в табл. 1.1.

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

Одним из первых угловой детектор предложил Г. Моравец в своей работе [101]. Предложенный им алгоритм производит проверку каждого пиксела изображения, является ли тот углом. Это делается с помощью сравнения области проверяемого пиксела с соседними областями. Сравнение производится вычислением функции отклика, которая представляет собой сумму квадратов разностей сравниваемых областей. Чем меньше величина, тем больше похожи области. Если пиксел располагается в области с равномерной интенсивностью, то величина функции отклика будет мала. Если пиксел находится на ребре, то функция отклика даст большое отличие в направлении, перпендикулярном ребру. Области, расположенные на ребре не будут иметь заметных различий. Если пиксел принадлежит углу, то в большинстве направлений будут получены большие значения функции отклика. Это и является признаком обнаружения угла. Основным недостатком этого алгоритма явля-

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

Таблица 1.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)

В 1986 г. Фёрстнер представил свой инвариантный к поворотам угловой детектор [67]. Инвариантность к поворотам достигается за счет критерия, основанного на отношении определителя и следа ц. В 1989 г. Э. Нобель предложил аналогичный критерий определения углов на изображениях [108]. К. Pop в 1987 г. предложил инвариантный к повороту дескриптор, использующий определитель // [116]. Помимо этого, Рором и другими авторами был использован градиент в изображениях трехмерной томографии [69, 115].

Предложенный Г. Моравецом подход был улучшен Харрисом и Стивен-сом в 1988 г. [71]. Они предложили вместо простого сравнения областей изображений производить дифференциальную оценку угла в заданном направлении. Авторами метода было предложено использовать матрицу, состоящую из частных производных в направлениях хну, называемую структурным тензором. Признаком нахождения угла на изображении является наличие у структурного тензора двух собственных чисел большой величины.

В 1992 г. Томаси и Канаде доработали алгоритм нахождения углов Хар-риса, в 1994 г. Ши и Томаси использовали эти результаты для разработки нового детектора углов [121, 131]. Предложенное улучшение коснулось критерия выбора особых точек. Если детектор Харриса определял угол с помощью функции R:

К = &е\М-к{касеМ)2 ,

&&М = Л]Л2 , (1.1)

іїасеМ = Я, + Я2 ,

где Х\, Л2 ~ собственные числа структурного тензора, М - матрица автокорреляции [71], то Ши и Томаси предложили для определения угла использовать функцию

Я = шіп (Я,, Я2 ) . (1.2)

В своей работе Ши и Томаси показывают, что такой критерий оценки имеет лучшие показатели. В дальнейшем работу над развитием методов обнаружения углов на изображениях продолжили Канни [80] и Триггс [135]. Ими были разработаны алгоритмы обнаружения углов, инвариантные к масштабу, углу поворота и аффинным преобразованиям. Методы нахождения углов в инвариантном к масштабу пространстве были разработаны также Линдбергом [90]. Предложенный им метод использовал теоретические разработки авторов [66,91] в области анализа разномасштабных структур на изображениях, используемых в компьютерном зрении. В более поздних работах Баумберга, Миколайчука и Лове [45, 92, 100] также представлены детекторы, инвариантные к изменениям масштаба. Устойчивость к изменениям масштаба достигается за счет построения пирамиды детальностей исходного изображения и применения детектора к каждому уровню пирамиды. Это зна-

чительно увеличивает количество найденных значимых особенностей. [78 ,79,81]

В настоящее время направление, основанное на использовании уголковых детекторов, также активно развивается. Одним из наиболее известных и широко используемых современных детекторов является детектор FAST (Features from Accelerated Segment Test) [119]. Проверки пиксела на то, является ли он углом, осуществляется за счет сравнения его яркости с яркостями 16 пикселов {хь...^С16} вокруг точки-кандидата (рис. 1.2). Отклик S в точкер принимает одно из трех состояний, определяющихся следующим образом:

d, s, Ь,

S, I р ~t<Ix <Ip+t , VXG {*,,...,*16} ,

(1.3)

Ip+t<Ix

где 1Х - яркость пиксела на окружности вокруг проверяемого пиксела, 1Р - яркость проверяемого пиксела, t - порог.

1И1

Рисунок 1.2 . Проверка точки-кандидата на то, является ли она углом.

На втором шаге алгоритма вводится бинарная переменная Кр, истинное значение которой указывает на то, что проверяемый пиксел является углом. Значение Кр определяется алгоритмом, описанным в работе [113], который вводит понятие энтропии проверяемых пикселов. Определение углов происхо-

дит сведением энтропии к нулю. Для снижения влияния шумов на результат работы алгоритма перед его применением авторами рекомендуется произвести размытие изображения фильтром Гаусса.

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

Классическим подходом к нахождению пятен является использование функции, называемой Лаплассиан Гауссианы (ЬоС). Эта функция, применительно к цифровой обработке изображений, представляет собой свертку с ядром:

ЬоС (х,у,сг) =---

4

КО

2 . 2 1 _ Х + У

2а2

V"

2а2

е . (1.4)

Применение такой функции дает большой положительный отклик при обнаружении темных пятен, и отрицательный отклик при нахождении светлых пятен. Применение свертки с таким ядром требует больших вычислительных ресурсов, поэтому в настоящее время для нахождения пятен используют аппроксимирующие функции. Лове в работах [92, 93] для аппроксимации Лаплассиана Гауссианы предлагает использовать разность Гауссиан (Оов), когда две копии исходного изображения сворачиваются с ядром Гаусса разных значений а и вычитаются полученные результаты.

Ь(х,у,а) = С(х,у,а)* 1(х,у) , ^ ^

И{х,у,а)= (Сг(х,у.ка)- С(х,_у,сг))* 1(х,у)= Ь(х, у.ка)- Ь{х,у,а) .

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

же. Если проверяемая точка больше/меньше остальных точек, то она признается особенностью и заносится в список найденных особенностей (рис. 1.3).

Масштаб

/ / / /

- —/■---✓---У--У"

/ / / /

. ^__^__^___/-

/ / / / / / / /

)---7---у--/- -

' ' ' '

Рисунок 1.3. Определение локального максимума.

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

В ряде работ [89, 90, 91] для нахождения пятен предлагается использовать определитель матрицы Гессе. Матрица Гессе имеет вид:

Н(Г(х,у))

2 д 2

ох оу

(1.6)

где х, у — координаты пиксела изображения. Теоретически, вычисление матрицы Гессе сводится к нахождению Лапласиана Гауссиан. Элементы матри-

цы Гессе вычисляются как свертка (сумма произведений) пикселов изображения на фильтры, изображенные на рис. 1.4.

Рисунок 1.4. Фильтры для вычисления матрицы Гессе.

Экстремумы функции указывают на точечные особенности. В работах [46, 47] авторы используют аппроксимирующие маски для построения матрицы Гессе, называемые Fast Hessian чтобы увеличить быстродействие алгоритма.

0 1 1 1 1 1 0 (Г ГО 0 0 0 0 0 0 0 (Г ґо 0 0 0 0 0 0 0 °1

0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 -1 -1 -1 0

0 0 1 1 1 1 1 0 0 1 1 1 -2 -2 -2 1 1 I 0 1 1 1 0 -1 -1 -1 0

0 0 -2 -2 -2 -2 -2 0 0 1 1 1 -2 -2 -2 1 1 1 0 1 1 I 0 -1 -1 -1 0

0 0 -2 -2 -2 -2 -2 0 0 1 1 1 -2 -2 -2 1 1 1 0 0 0 0 0 0 0 0 0

0 0 -2 -2 -2 -2 -2 0 0 1 1 1 -2 -2 -2 1 1 1 0 -1 -1 -1 0 1 1 1 0

0 0 1 1 1 1 1 0 0 1 1 1 -2 -2 -2 1 1 1 0 -1 -1 -1 0 I 1 1 0

0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 1 1 1 0

,0 0 1 1 1 1 1 0 0, ,0 0 0 0 0 0 0 0 о, ,0 0 0 0 0 0 0 0 0,

Пространственный масштаб составляет 9x9 пиксел. Такой фильтр устойчив к вращению, его можно эффективно вычислить с помощью интегральной матрицы. Таким образом, в методе SURF (Speed Up Robust Features), гессиан вычисляется следующим образом:

^Шарргох) = »xxDyy - (0,9 • Dxyf . (1.7)

Применение таких масок позволяет эффективно использовать интегральные матрицы [16], помимо этого, устраняется основной недостаток алгоритма - искажение результата при повороте объекта на 45°.

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

Основным шагом алгоритма решения задачи совмещения нескольких изображений является задача сопоставления найденных на предыдущем шаге точечных особенностей. Для качественного совмещения изображений требуется поставить друг другу в соответствие как можно больше особых точек, при этом задача должна выполняться за приемлемое время. В настоящее время широкое распространение получили дескрипторы точечных особенностей. Дескриптор - это идентификатор ключевой точки, выделяющий её из остальной массы особых точек. Дескриптор является вектором числовых характеристик окрестности особенности ¿Xх) ~ Дескрипторы должны обеспечивать инвариантность нахождения соответствия между особыми точками относительно преобразований изображений.

Простейшим дескриптором особой точки являются нормированные значения яркости пикселов, записанные в виде вектора [14, 138]. Такой дескриптор является очень простым в вычислении, но он не инвариантен к повороту, поэтому для окрестности каждой особой точки вычисляют вектор направленности. Чаще всего это доминирующий градиент окрестности особой точки. Дескриптор необходимо строить относительно полученного направления.

Сами по себе дескрипторы не обладают инвариантностью к масштабу изображения, поэтому для исходных изображений стереопары строятся пирамиды детальностей для разных масштабов исходных изображений [42, 43, 44]. На каждом из уровней производится поиск особых точек, и строятся дескрипторы, которые затем сопоставляются друг с другом (SIFT -Scale Invariant Features Transform, SURF - Speeded Up Robust Features, BRIEF - Bi-

nary Robust Independent Elementary Features, ORB - Oriented BRIEF и т.д.). Помимо инвариантности к масштабу представленные дескрипторы в некоторой степени обладают устойчивостью к аффинным искажениям. Основным их недостатком является высокая вычислительная сложность. В табл. 1.2 представлена краткая классификация существующих методов сопоставления особых точек.

Таблица 1.2

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

Пиксельно-блочное сопоставление - 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) - GLOH (Gradient Location and Orientation Histogram)

Одной из последних разработок в области сопоставления особых точек является дескриптор BRIEF. Данный дескриптор представляет собой вектор, состоящий из 128 - 512 булевых значений. За счет этого и из-за особенностей дескриптора для вычисления каждого значения вектора требуется лишь одна операция сравнения, что позволяет применять его в системах реального времени. Несмотря на его простоту, BRIEF обладает точностью сопоставления на уровне дескрипторов SIFT и SURF, но только для случаев, когда не требуется инвариантность к масштабу и повороту. Существуют инвариантные модификации дескриптора BRIEF, позволяющие сопоставлять особые точки, но они уже не обладают столь высокой точностью сопоставления.

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

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

В кросскорреляционном методе используется коэффициент корреляции (р, который равен

лД 11 ^22

где Я,, = м{хх - У = /Эх,, Х22 = м(х2 - )2 = £>х2, Я,2 = М(х] - £,) (х2 -€2) - соу(хь х2), = Мх\, = Мх2, xi и х2 - изображения участков соответствующих снимков; М{х) - математическое ожидание, £) (х) - дисперсия.

Для ускорения работы алгоритма можно сравнивать не все особенности второго изображения, а только те, которые находятся в определенной окрестности особенности первого изображения. Теоретически коэффициент сходства между правильно сопоставленными особенностями должен быть равен 1. Но в действительности коэффициент корреляции будет меньше [14].

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

■ С-9)

'•У

где С!и и С и - нормированная яркость пиксела окрестности особой точки на первом и втором изображения соответственно. В общем случае метод евклидовых расстояний зависит от изменения освещенности, поэтому вместо ярко-

сти пиксела берется его нормированная величина по окрестности вокруг рассматриваемой особенности:

сч =

f \

/;/-тт(/)

V '•-/■ J

(1.10)

где 1ц - яркость пиксела из окрестности особой точки.

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

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

Использование scale-space детектора особенностей [73, 102] позволяет добиться инвариантности к изменению масштаба. Для этого достаточно перед вычислением дескриптора произвести нормирование в соответствии с локальным масштабом особенности. Например, если с особенностью ассоциирован масштаб 2, то окрестность особенности следует масштабировать с коэффициентом '/4 и т. д. Если дескриптор состоит из выражений, в которых используются исключительно нормированные производные, то масштабировать окрестность не обязательно. Достаточно рассчитывать значения производных для значения масштаба <7, который ассоциирован с особенностью.

Для достижения инвариантности к повороту используются устойчивые дескрипторы. Приведем пример дескриптора из [102], каждая компонента которого инвариантна к повороту. Все производные в выражении являются нормированными производными.

44 + 44

^XV + 4 т ЬХХЬХЬ + 2Ь ЬЬ +І..І.І,,

хх XX ДІЛІ ІЛ' \ і'

4*4*

^4у4у + 4ф4Т

4**444 + ^ 4™ 4 4 4 зьхх>ЬхЬу¿,,,¿,¿,4 4«444 + 4*,(- 2444 + 444)+ 4, (- 2444 + 444)+ 4- 444 4д> 444 + 244 4)+ 4іт 2 + 44 4)- + ьхххьхьхьу

4**444 + 444 + ^4п 44 4 + 4т» 4 44

где £ - гауссиан частной производной по окрестности точки.

Серьезным недостатком этого метода является то, что в дескрипторе нельзя использовать компоненты, которые не инвариантны к повороту, а число операторов, которые инвариантны к повороту, и при этом применимы на практике, ограничено. Известен еще одни способ достижения инвариантности к повороту, который заключается в предварительном нормировании окрестности точки особым образом (для компенсации поворота), и лишь потом вычислении дескрипторов для данной особенности. Для того чтобы нормировать окрестность по повороту, требуется оценить ориентацию особенности. Существует много методов оценки локальной ориентации особенности, все они, так или иначе, используют направление векторов градиентов в окрестности особенности. Рассмотрим метод, предложенный Лове в работе [93]. Он состоит из следующих шагов:

Шаг 1. Разделить множество углов от 0° до 360° на 36 одинаковых участков, каждый по 10°. Каждому из участков сопоставим ячейку в гистограмме Н.

Шаг 2. Для каждой точки х0 из некоторой окрестности особенности а вычислить фазу и модуль вектора градиента:

где г'е - индекс ячейки, которая соответствует фазе градиента, а - весовой коэффициент точки х0. В качестве весового коэффициента можно использовать, значение 1 (это простейший случай), но более качественных и устойчивых результатов оценки удается добиться при использовании в качестве весовых значений Гауссиана с центром в точке а.

Шаг 3. После того, как шаги 1-2 выполнены для каждой точки окрестности особенности, в качестве ориентации особенности следует выбрать ф = /* 10°, где г - индекс элемента гистограммы с наибольшим значением.

После вычисления ориентация особенности производится нормировка. Для этого достаточно повернуть особенность на угол ср вокруг центра особенности. К сожалению, для некоторой части особенностей ориентация оценивается неверно (обычно 10-20%) и дескрипторы этих особенностей оказываются абсолютно непригодными к сопоставлению. Именно этот факт является основным недостатком данного подхода.

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

Реально процессы, происходящие в пикселах при изменении освещенности,

(1.12)

. Эта модель не очень точно соответствует действительности.

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

гдє mean (l{w (*))) И std(l(w(x))) обозначают выборочное среднее и среднее

пенсированная по переносу, а Іге5иі, - результирующая окрестность, скомпенсированная по освещенности. Именно по особенности Ігезиі, следует вычислять дескриптор особенности, чтобы добиться инвариантности к изменениям освещенности.

Также можно составлять дескриптор из функций, которые инвариантны к аффинным изменениям освещенности, далее строится инвариантный к повороту дескриптор из [102], преобразованный таким образом, чтобы его компоненты были инвариантны к изменениям освещенности. Стоит отметить, что инвариантность дескриптора к изменениям освещенности требует удаления первых двух его компонент (выражение 1.14). Все производные в выражении являются нормированными производными. Использование такого дескриптора позволяет достичь хороших результатов при сопоставлении точечных особенностей.

LneaSAx)) = 7М*)) - rnear(l(w(x)))

(1.13)

(¿„¿л + 2^,1,1, ч-^лО/С^Л +

(LMLXL^ + 31,„¿^Л -3 LmLLL-LwLxLxLx)l(LxL+L,Ly

+1 ¿,)2

(¿A+^J

(LlnLxLxLx+3L^LyLxLx + 3ZniL,L,I, + ImI,L,I, )/(l,Z, + I,I, )2

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

Как было отмечено выше, методы SIFT и SURF позволяют не только находить точечные особенности на изображениях, но и создавать дескрипторы, инвариантные к повороту и масштабу. Перед построением дескрипторов необходимо вычислить направление особой точки. В методе SIFT направление особой точки вычисляется исходя из направлений градиентов точек, соседних с ней. Все вычисления градиентов производятся на изображении в пирамиде Гауссианов, с масштабом наиболее близким к масштабу ключевой точки. Величина и направление градиента в точке (х, у) вычисляются по формулам:

т(х, у) = V (Ь(х +1 ,у)~ L(x -1, у))2 + (L(x, у + l) - L(x, у -1))2

в(х,у) = tan"

L(x + l,y)-L(x-l,y)

где т - величина градиента, в — направление.

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

равен 1,5 s, где s - масштаб ключевой точки. Для Гауссова ядра действует так называемое правило «трех сигм». Оно состоит в том, что значение гауссова ядра очень близко к нулю на расстоянии, превышающем За. Таким образом, радиус окна определяется как За.

Направление ключевой точки находится с помощью гистограммы направлений О. Гистограмма состоит из 36 компонент, которые равномерно покрывают промежуток в 360°, и формируется она следующим образом: каждая точка окна (х, у) вносит вклад, равный mG{x, у, а), в ту компоненту гистограммы, которая покрывает промежуток, содержащий направление градиента в(х, у).

Направление ключевой точки лежит в промежутке, покрываемом максимальной компонентой гистограммы. Значения максимальной компоненты и двух соседних с ней интерполируются параболой, и точка максимума этой параболы выбирается в качестве направления ключевой точки. Если в гистограмме присутствуют компоненты с величинами не меньше 0,8 тах, то они аналогично интерполируются и дополнительные направления приписываются ключевой точке.

В методе SURF сначала вычисляются точечные градиенты в пикселах, расположенных рядом с особой точкой. Для рассмотрения берутся пикселы в окружности радиуса 65 вокруг особой точки. Для первой октавы берутся точки из окрестности радиусом 12. Для вычисления градиента, используется фильтр Хаара. Размер фильтра берется равным 4s. Все найденные значения dX и dY, условно наносятся в виде точек на плоскость, как показано на рис. 1.5.

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

Рисунок 1.5. Плоскость с нанесенными градиентами в виде точек в пространстве о\XciY

Вычисление направления особой точки выполняется для достижения инвариантности к повороту. В обоих методах для вычисления дескриптора используется окно вокруг особой точки. Инвариантность относительно поворота достигается за счет поворота окна на угол направления особой точки. На рис. 1.6 схематично показан метод построения дескриптора, который использует метод SIFT.

Пикселы на рисунке 1.6 (а) обозначены малыми квадратами. Эти пикселы берутся из квадратного окна дескриптора, которое в свою очередь поделено ещё на четыре равных региона. Стрелки в центрах пикселов обозначают направления градиентов. Центр этого окна находится между пикселами. Его надо выбирать как можно ближе к точным координатам особой точки. Круг обозначает окно свертки с гауссовым ядром (аналогично окну для вычисления направления ключевой точки). Значение каждой точки окна дескриптора умножается на значение гауссова ядра в этой точке как на весовой коэффициент.

На рис. 1.6 б схематически изображенный дескриптор особой точки, размерности 2x2x8. Первые две цифры в значении размерности - это количество регионов по горизонтали и вертикали. Те квадраты, которые охватывали

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

Шаг 1. Каждая гистограмма также покрывает участок в 360°, но делит его на 8 частей.

Шаг 2. В качестве весового коэффициента берется значение гауссова ядра, общего для всего дескриптора.

ШагЗ. В качестве дополнительных весовых коэффициентов берутся коэффициенты кубической интерполяции.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Тупицын, Илья Владимирович

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

Был проведен анализ существующих методов и алгоритмов извлечения точечных особенностей на изображениях. Существующие особенности на цифровых изображениях (углы, грани, световые перепады и т.д.) приводят к разделению детекторов на три основные группы: уголковые детекторы; детекторы световых пятен (blob); детекторы устойчивых областей (MSER). Уголковые детекторы производят проверку каждого пиксела на то, является ли он углом или гранью. Это происходит путем сравнения региона вокруг каждого пиксела с соседними регионами. Существуют различные модификации уголковых детекторов, обладающие устойчивостью к повороту и изменению масштаба.

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

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

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

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

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

Для извлечения точечных особенностей используется детектор на основе аппроксимированного Гессиана, называемого «быстрый Гессиан». Использование матрицы Гессе, по сути, сводится к нахождению Лаплассиана Гаусси-ан, что относит рассматриваемый детектор в категорию детекторов световых пятен. Для сопоставления точечных особенностей используется разработанный детектор, вычисляющий направления и величины векторов градиентов как по окрестности самой точки, так и по окрестности пары точек, находящихся на расстоянии от нее. Точки выбираются таким образом, чтобы они лежали на перпендикуляре к направлению вектора градиента особенности на расстоянии, пропорциональном его величине. Векторы градиентов пары дополнительных точек образуют четырехугольную область, которая затем приводится к прямоугольному виду с помощью проективного преобразования, что позволяет компенсировать искажения на изображениях стереопары. Сопоставления полученных дескрипторов осуществляется метрикой нормированной кросс-корреляции.

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

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

Проведено тестирование модулей разработанного ПО как по отдельности, так и в совокупности на различных видах стереопар (естественного и искусственного происхождения, полученных с разных ракурсов, в различных условиях освещенности). Экспериментальные исследования показали, что использование нового иерархического метода для оценки полученных гипотез позволяет на 20% снизить время вычисления фундаментальной матрицы в сравнении с алгоритмами семейства ЯА№АС, сохраняя при этом ее достоверность.

Список литературы диссертационного исследования кандидат технических наук Тупицын, Илья Владимирович, 2013 год

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

1. Аленин В. А. Трехмерная реконструкция объектов из последовательности изображений / В. А. Аленин // Молодой ученый. — 2011. — №3. Т.1. — С. 33-36.

2. Боресков, A.B., Харламов A.A. - Основы работы с технологией CUDA. - М.: ДМК Пресс, 2010. - 232 с.

3. Волегов, Д.Б., Юрин Д.В. Грубое совмещение изображений по найденным на них прямым линиям / Труды конференции. 16-я Международная Конференция по Компьютерной Графике и её приложениям Гра-фиКон'2006 -С. 463-466. Новосибирск, 2006.

4. Вудс Р., Гонсалес Р., Цифровая обработка изображений — М.: Техносфера — 2005.

5. Гаганов В. А., Игнатенко А. В. Реконструкция плоских объектов по изображениям с микроскопа // Программные продукты и системы. 2009. Т. 3. С. 78-82.

6. Гаганов В. А., Игнатенко А. В. Трехмерная реконструкция плоских граней прозрачных минералов по набору изображений с микроскопа // Труды конференции Графиком. 2008. С. 227 -233.

7. Гаганов В. А., Игнатенко А. В. Устойчивое построение трехмерных моделей объектов по набору изображений с микроскопа // Информационные технологии п проектировании и производстве. 2009. Т. 4. С. 5G-G4.

8. Гришин, В.А., Белинская, Е.В. Сравнение спектральных представлений образов окрестностей точек для решения задач установления соответствия / в сб. шестой всероссийской открытой ежегодной конференции «Современные проблемы дистанционного зондирования Земли из космоса» Москва, ИКИ РАН, 2008 г.

9. Жук Д.В., Тузиков A.B. Реконструкция трехмерной модели по двум цифровым изображениям // Информатика. - 2006. - № 1. - С. 16-26.

10. Жук Д.В., Тузиков A.B., Бородач A.B. Восстановление трёхмерной модели сцены по цифровым изображениям // «Искусственный интеллект». -2006 - №2.-С. 142-146

11. Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ. -МЦНМО 1990 г.

12. Костюк, Ю. Л., Парамонов, А. С., Гриценко, В. Г. Технология создания трехмерных моделей объектов по плоским проекциям и ее применение в геоинформатике // Геоинформатика. Теория и практика. Вып.1 - Томск: Изд-во Томск, ун-та, 1998. С.96-106.

13. Кривовязь Г., Черников А., Велижев А. Автоматическое сопоставление изображений и облака трехмерных точек // Труды конференции Графиков 2011.С. 208-211.

14. Кудряшов, А.П. Извлечение и сопоставление точечных особенностей // Электронный научный журнал «Исследовано в России», 2007 г. С 1095- 1104.

15. Лукьяница, A.A. "Эффективный алгоритм восстановления промежуточных ракурсов по стереопары" // В сб. Труды конференции. 16-я Международная Конференция по Компьютерной Графике и её приложениям Гра-фиКон'2006 -С. 375-377. Новосибирск, 2006.

16. Макаров, А.О., Старовойтов В.В. Быстрая обработка изображений на основе интегральных матриц изображений // 2006 г. С. 597-602.

17. О. Баринова, В. Конушин, А. Соболев, А. Кузьмишкина, А. Якубен-ко, А. Конушин. Быстрая автоматическая трехмерная реконструкция городских сцен по одному изображению. // в трудах конференции Графикон 2008, том 1., стр. 234-242.

18. О. Баринова. Трехмерная реконструкция городских сцен по одному изображению. // Вестник Компьютерных и информационных технологий, издательство «Машиностроение», Номер 5, 2010.

19. Скворцов A.B. Триангуляция Делоне и ее применение. - Томск: Изд-во ТГУ, 2002 - 128 стр.

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

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

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

23. Тупицын, И.В. Восстановление промежуточных ракурсов изображений по стереопаре // В материалах IV всероссийской научно-практической конференции творческой молодежи «Актуальные проблемы авиации и космонавтики». - Красноярск, 2008. С. 60-62.

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

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

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

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

28. Тупицын, И.В. Реконструкция промежуточных ракурсов изображений по стереопаре // В сб. материалов всероссийской научной конференции аспирантов и молодых ученых «Молодежь и наука. Третье тысячелетие». -Красноярск, 2007. С. 445-448.

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

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

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

32. Фаворская М.Н., Тупицын И.В. Метод повышения устойчивости сопоставлений на стереоизображениях // В трудах научно-технической конф. «Техническое зрение в системах управления-2012», М., ИКИ РАН, 2012. С. 139-144

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

34. Форсайт, Д.А., Понс, Ж. Компьютерное зрение: современный подход. - М.: Вильяме. 2004. - 928 с.

35. Хорн Б. К. П. Зрение роботов: Пер. с англ. — М.: Мир, 1989. — 487

стр.

36. Лемиицкий В. Решение задачи трехмерной реконструкции по изображениям при помощи разрезов на графах // Тезисы международного семинара по компьютерной алгебре и информатике, pages 7-8, 2005.

37. Конушин А. Реконструкция модели объекта по силуэтам и по согласованию цветов. Компьютерная графика и мультимедиа. Выпуск №1(3)/2003.

38. Конушин А., Мариничев К., Вежневец В. Обзор робастных схем оценки параметров моделей на основе случайных выборок // Труды конференции Graphicon-2004, с.275-278, Москва, сентябрь 2004.

39. Лисицин Е., Конушин А., Вежневец В. Отслеживание точечных особенностей в видеопоследовательностях с изменениями резкости // Труды конференции Graphicon-2004, с.233-236, Москва, сентябрь 2004.

40. Поздеев Д.М., Меженин А.В., Тозик В.Т. Получение квазистереоскопических изображений // Научно-технический вестник СПбГУ ИТМО. 2007. Вып. 45 «Информационные технологии: инженерная и компьютерная графика». С. 208-210.

41. Фурса М.В. Исследование и разработка математического и программного обеспечения оптических систем слежения реального времени для приложений виртуального окружения // Автореферат дисс. на соискание ученой степени к.т.н. - М.: 2009.

42. Agrawal М., Konolige К., and Blas М. R. CenSurE: Center surround extremas for realtime feature detection and matching // In Proceedings of the European Conference on Computer Vision (ECCV), 2008.

43. Alahi A., Ortiz R., Vandergheynst P., FREAK: Fast Retina Keypoint // IEEE Conference on Computer Vision and Pattern Recognition, Rhode Island, Providence, USA, June 16-21, 2012.

44. Alahi A., Vandergheynst P., Bierlaire M., and Kunt M. Cascade of descriptors to detect and track objects across any network of cameras // Computer Vision and Image Understanding, 114(6):624-640, 2010.

45. Baumberg A. Reliable feature matching across widely separated views // In Proc. of IEEE Conference on Computer Vision and Pattern Recognition, pages 774-781, Hilton Head Island, South Carolina, June 2000.

46. Bay H., Ess A., Tuytelaars T., Van Gool L. SURF: Speeded Up Robust Features // Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, pp. 346-359, 2008.

47. Bay H., Tuytelaars T. and van Gool L. SURF: Speeded Up Robust Features // Proceedings of the 9th European Conference on Computer Vision, Springer LNCS volume 3951, part 1. pp. 404-417, 2006.

48. Ben J. Tordoff and David W. Murray. Guided-MLESAC: Faster image transform estimation by using matching priors // IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(10):1523-1535, October 2005.

49. Bobick A. F., Intille S.S. Large Occlusion Stereo // International Journal of Computer Vision 33(3), 181-200, 1999.

50. Bradski G., Kaehler A. Learning OpenCV: Computer Vision with the OpenCV Library. O'Reilly Media, ISBN 0596516134 , 556 pp, 2008.

51. Brown MZ, Burschka D, Hager GD: Advances in Computational Stereo // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2003; 25(8):993-1008.

52. Brown, M., Lowe, D.: Invariant features from interest point groups // In: BMVC, 2002.

53. Calonder M., Lepetit V., Strecha C., and Fua P. Brief: Binary robust independent elementary features // In European Conference on Computer Vision, 2010.

54. Candes E., Eldar Y., Needell D., and Randall P. Compressed sensing with coherent and redundant dictionaries. Applied and Computational Harmonic Analysis, 31(l):59-73, 2011.

55. Capel, D.: An effective bail-out test for RANSAC consensus scoring // In: Proc. BMVC, pp. 629-638, 2005.

56. Chen H. and Meer P. "Robust regression with projection based M-estimators" // In 9th Intl. Conf. on Computer Vision, (Nice, France), Oct 2003, pp. 878-885.

57. Chli M. and Davison A. J. Active Matching // InProceedings of the European Conference on Computer Vision (ECCV), 2008.

58. Choi S. and Kim J.-H. Robust regression to varying data distribution and its application to landmark-based localization // Proceedings of the IEEE Conference on Systems, Man, and Cybernetics, October 2008.

59. Chum O. and Matas J. Matching with PROSAC - Progressive Sample Consensus // In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2005.

60. Chum O. Two-View Geometry Estimation by Random Sample and Consensus, 2005.

61. Chum O., Matas J., and Obdrzalek S. Enhancing RANSAC by generalized model optimization // In Proceedings of the Asian Conference on Computer Vision (ACCV), 2004.

62. David A. Forsyth and Jean Ponce Computer Vision, a modern approach. — Prentice Hall, 2003. — ISBN ISBN 0-13-085198-1.

63. Davison A. J., Molton N. D., Reid I., and Stasse O. MonoSLAM: Realtime single camera SLAM // IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 29(6): 1052-1067, 2007.

64. Ebrahimi M. and Mayol-Cuevas W. Susure: Speeded up surround extrema feature detector and descriptor for realtime applications. 2009.

65. Feng C.L. and Hung Y.S. A robust method for estimating the fundamental matrix // Proceedings of the 7th Digital Image Computing: Techniques and Applications, number 633-642, December 2003.

66. Florack L. M. J., terHaar Romeny B. M., Koenderink J. J., and Viergever M. A. Scale and the differential structure of images // Image and Vision Computing, 10(6):376-388, July/August 1992.

67. Forstner W. A feature based correspondence algorithm for image matching // In International Archives of Photogrammetry and Remote Sensing, volume 26, pages 150-166, 1986.

68. Frahm J.-M. and Pollefeys M. RANSAC for (quasi-)degenerate data (QDEGSAC) // Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2006.

69. Frantz S., Rohr K., and Stiehl H.S. Multi-step differential approaches for the localization of 3D point landmarks in medical images // Journal of Computing and Information Technology, 6(4):435^147, 1998.

70. Gluckman J. and Nayar S.K. Rectifying transformations that minimize resampling effects // CVPR, 1:111, 2001.

71. Harris, C. and Stephens, M. A combined corner and edge detector // In Fourth Alvey Vision Conference, Manchester, UK, 1988, pp. 147-151.

72. Hartley R. I. In Defense of the 8-Point Algorithm // GE-Corporate Research and Development, Schenectady , NY, 1995.

73. Hartley R., Zisserman A. Multiple View Geometry // In Computer Vision. — 2nd. — Cambridge University Press, 2003.

74. Hartley R.I. In defense of the eight-point algorithm // IEEE TP AMI Intelligence, 19(6):, 1997.

75. Hirschmuller H. Stereo Vision Based Mapping and Immediate Virtual Walkthroughs. PhD thesis, School of Computing, De Montfort University, Leicester, UK, 2003.

76. Hirschmuller, H. Scharstein, D. Evaluation of Cost Functions for Stereo Matching // Computer Vision and Pattern Recognition, 2007. CVPR '07. IEEE.

77. Huber P. J. Projection pursuit. Annals of Statistics, 13:433-475, 1985.

78. Kadir, T., Brady, M.: Scale, saliency and image description // IJCV 45(2) (2001) 83 - 105.

79. Ke Y. and Sukthankar R. PCA-SIFT: A more distinctive representation for local image descriptors // In Computer Vision and Pattern Recognition, pages 506-513, 2004.

80. Kenney C., Manjunath B., Zuliani M., Hewer G., and Van Nevel A. A condition number for point matching with application to registration and postregistration error estimation // IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(11): 1437-1454, November 2003.

81. Klein G. and Murray D. Improving the agility of keyframebased SLAM // In European Conference on Computer Vision, 2008.

82. Klein G. and Murray D. Parallel tracking and mapping on a camera phone // In Proc. Eigth IEEE and ACM International Symposium on Mixed and Augmented Reality (ISMAR'09), Orlando, October 2009.

83. Koch R. Pollefeys M. and Van Gool L. A simple and efficient rectification method for general motion // ICCV, 1:496-501, 1999.

84. Konouchine A., Gaganov V., Vezhnevets V. AMLESAC: A New Maximum Likelihood Robust Estimator // Proc. Graphicon-2005, Novosibirsk, 2005. -PP. 93-100.

85. Lazebnik S., Schmid C., and Ponce J. Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories // In Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on, volume 2, pages 2169-2178. IEEE, 2006.

86. Lepetit, V., Fua, P.: Keypoint Recognition Using Randomized Trees // IEEE Transactions on Pattern Analysis and Machine Intelligence 28 (2006) 14651479.

87. Leutenegger S., Chli M. and Siegwart R. BRISK: Binary Robust Invariant Scalable Keypoints // Proceedings of the IEEE International Conference on Computer Vision (ICCV) — 2011.

88. Lim, Ser-Nam; Mittal, Anurag; Davis, Larry; Paragios, Nikos. Uncali-brated stereo rectification for automatic 3D surveillance // International Conference on Image Processing 2: 1357. Retrieved 2010.

89. Lindeberg T. and Garding J. Shape-adapted smoothing in estimation of 3-D depth cues from affine distortions of local 2-D structure // International Journal of Computer Vision 15: pp 415-434, 1997.

90. Lindeberg T. Feature detection with automatic scale selection (abstract page) // International Journal of Computer Vision 30 (2): pp 77-116, 1998.

91. Lindeberg T. Scale-Space Theory in Computer Vision. Springer. ISBN 0-7923-9418-6, 1994.

92. Lowe, D. G., Distinctive Image Features from Scale-Invariant Keypoints // International Journal of Computer Vision, 60, 2, pp. 91-110, 2004.

93. Lowe, David G. (1999). Object recognition from local scale-invariant features // Proceedings of the International Conference on Computer Vision. 2. pp. 1150-1157. doi: 10.1109/ICCV. 1999.790410.

94. Mair E., Hager G. D., Burschka D., Suppa M., and Hirzinger G. Adaptive and generic corner detection based on the accelerated segment test // In Proceedings of the European Conference on Computer Vision (ECCV), 2010.

95. Marc E. and Stuart H. Lateral information processing by spiking neurons: A theoretical model of the neural correlate of consciousness // Computational Intelligence and Neuroscience, 2011.

96. Martin A. Fischler and Robert C. Bolles, Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography // Comm. Of the ACM 24: 381-395. DOLlO.l 145/358669.358692., 1981.

97. Martinez M., Collet A., and Srinivasa S.S. MOPED: A Scalable and low Latency Object Recognition and Pose Estimation System // In IEEE International Conference on Robotics and Automation. IEEE, 2010.

98. Matas, J., Chum, O.: Randomized RANSAC with sequential probability ratio test // Proc. ICCV, pp. 1727-1732, 2005.

99. Matas, J., Chum, O.: Randomized RANSAC with Td,d test // Image and Vision Computing 22(10), 837-842, 2004.

100. Mikolajczyk K. and Schmid C. An affine invariant interest point detector // In European Conference on Computer Vision, pages 128-142, Copenhagen, Den-mark, 2002. Springer.

101. Mikolajczyk K. and SchmidC. Indexing based on scale invariant interest points // In Proc. of IEEE 8th International Conference on Computer Vision, pages 525-531, Vancouver, Canada, 2001.

102. Mikolajczyk K., Detection of local features invariant to affine transformations, 2002.

103. Monasse P., Morel J.-M., and Tang Z. Three-step image rectification. In Frédéric Labrosse, Reyer Zwiggelaar, Yonghuai Liu, and Bernie Tiddeman, editors // Proceedings of the British Machine Vision Conference, pages 89.1-89.10. BMVA Press, September 2010. doi:10.5244/C.24.89.

104. Moravec H., Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover // Tech Report CMU-RI-TR-3 Carnegie-Mellon University, Robotics Institute, 1980.

105. Muja M. and Lowe D. G. Fast approximate nearest neighbors with automatic algorithm configuration // VISAPP, 2009.

106. Myatt D.R., Torr P.H.S, Nasuto S.J., Bishop J.M., and Craddock R. NAPS AC: High noise, high dimensional robust estimation - it's in the bag // In Preceedings of the 13th British Machine Vision Conference (BMVC), pages 458467, 2002.

107. Nister D. and Stewenius H. Scalable recognition with a vocabulary tree // In CVPR, 2006.

108. Noble A. Descriptions of Image Surfaces. PhD thesis, Department of Engineering Science, Oxford University, 1989.

109. Ozuysal, M., Calonder, M., Lepetit, V., Fua, P.: Fast Keypoint Recognition Using Random Ferns // IEEE Transactions on Pattern Analysis and Machine Intelligence 32 (2010) 448-461.

110. Peters R.A. II A New Algorithm for Image Noise Reduction using Mathematical Morphology // IEEE Transactions on Image Processing, Volume 4, Number 3, pp. 554-568, May 1995.

111. Philbin J., Chum O., Isard M., Sivic J., and Zisserman A. Object retrieval with large vocabularies and fast spatial matching // In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1-8. IEEE, 2007.

112. Press W.H., Teukolsky S.A., Vetterling W.T., and Flannery B.P. Numerical Recipes. The Art of Scientific Computing. Third Edition. Cambridge University Press, 2007.

113. Quinlan, J.R.: Induction of decision trees // Machine Learning 1 (1986) 81-106.

114. Rodehorst V. and Hellwich O. Genetic Algorithm Sample Consensus (GASAC) - a parallel strategy for robust parameter estimation // In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshop (CVPRW), 2006.

115. Rohr K. Extraction of 3D anatomical point landmarks based on invariance principles // Pattern Recognition, 32:3-15, 1999.

116. Rohr K. Localization properties of direct corner detectors // Journal of Mathematical Imaging and Vision, 4(2): 139-150, 1994.

117. Rosin P. L. Measuring corner properties // Computer Vision and Image Understanding, 73(2):291 - 307, 1999.

118. Rosten E., Porter R., and Drummond T. Faster and better: A machine learning approach to corner detection // IEEE Trans. Pattern Analysis and Machine Intelligence, 32:105-119, 2010.

119. Rosten, E., Drummond, T.: Machine Learning for High-Speed Corner Detection // European Conference on Computer Vision, 2006.

120. Ruble E., Rabaud V., Gary K.K. ORB: an efficient alternative to SIFT or SURF // Proceedings of 13th International Conference on Computer Vision, Barcelona, 2011.

121. Shi J. and Tomasi C. Good Features to Track // 9th IEEE Conference on Computer Vision and Pattern Recognition, Springer, 1994.

122. Sinha S.N., Frahm J.M., Pollefeys M., and Gene Y. Gpu-based video feature tracking and matching. Technical report // In Workshop on Edge Computing Using New Commodity Architectures, 2006.

123. Snavely N., Seitz S. M., and Szeliski R. Skeletal sets for efficient structure from motion // In Proc. Computer Vision and Pattern Recognition, 2008.

124. Snavely N., Seitz S., and Szeliski R. Photo tourism: exploring photo collections in 3d // In ACM Transactions on Graphics (TOG), volume 25, pages 835846. ACM, 2006.

125. Subbarao R. and Meer P. Heteroscedastic projection based M-estimators // In Workshop on Empirical Evaluation Methods in Computer Vision, San Diego, CA in conjunctio.n with IEEE CVPR, 2005.

126. Subbarao R. and Meer P. Subspace estimation using projection-based M-estimator over Grassmann manifolds // In Proceedings of the 9th European Conference on Computer Vision (ECCV), pages 301-312, May 2006.

127. Szeliski R. Computer Vision: Algorithms and Applications Springer. -New York, 2010.-812 p.

128. Szeliski R., Zabih E., Scharstein D., Veksler O., Kolmogorov V., Agrawala A., Tappen M., and Rother C. A comparative study of energy minimization methods for Markov random fields // In Proc. ECCV, volume 2, pages 16-29, 2006.

129. Tola E, Lepetit V., Fua P. Daisy: an efficient dense descriptor applied to wide baseline stereo // IEEE Trans, on pattern analysis and machine intelligence PAMI(32), No. 5, May 2010, pp. 815-830.

130. Tolstaya E., Rychagov M., Kang K. M., Kim S. H Fusion of high dynamic range scene photos // Proceedings of 2009 IS&T/SPIE Electronic Imaging — V. 7250 72500Y —2009.

131. Tomasi C. and Kanade T. Shape and motion from image streams under orthography - a factorization method // International Journal on Computer Vision, 9(2): 137-154, November 1992.

132. Torr P., Zisserman A. Robust Computation and Parametrization of Multiple View Relations // ICCV Proc, p.727, 1998.

133. Torr P.H.S., and Murray D.W. The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix // International Journal of Computer Vision 24: 271-300. DOI: 10.1023/A: 1007927408552, 1997.

134. Torr, P., Zisserman, A.: MLESAC: A new robust estimator with application to estimating image geometry // CVIU, 138-156, 2000.

135. Triggs B. Detecting keypoints with stable position, orientation, and scale under illumination changes // In Proc. of the 8th European Conference on Computer Vision, volume 4, pages 100-113, 2004.

136. Trucco E., Plakas K., Brandenburg N., Kauff P., Karl M., Oliver Schreer Real-Time Disparity Maps For Immersive 3-D Teleconferencing By Hybrid Recursive Matching and Census Transform.

137. Tsai R.Y. and Huang T.S., Uniqueness and Estimation of Three Dimensional Motion Parameters of Rigid Objects With Curved Surfaces // IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, pp. 13-27, 1984.

138. Tuytelaars T. and Mikolajczyk K. Local invariant feature detectors: a survey. Foundations and Trends // In Computer Graphics and Vision, 3(3): 177280, 2008.

139. Tuzel O., Porikli F., and Meer P. Region covariance: A fast descriptor for detection and classification // Computer Vision-ECCV 2006, pages 589-600, 2006.

140. Veksler O. Stereo correspondence by dynamic programming on a tree // Proc. CVPR. Vol. 2. 2005. PP. 384-390.

141. Wald A. Sequential analysis. Dover, New York, 1947.

142. Weimert A., Tan X., and Yang X. Natural feature detection on mobile phones with 3D FAST. Int. J. of Virtual Reality, 9:29-34, 2010.

143. Wright W. D. Professor Wright's Paper from the Golden Jubilee Book: The Historical and Experimental Background to the 1931 CIE System of Colorim-

etry, in Colorimetry: Understanding the CIE System (ed J. Schanda). Hoboken, NJ, USA: John Wiley & Sons, Inc., 2007, 496 C.

144. Yu G. and Morel J. A fully affine invariant image comparison method // In Acoustics, Speech and Signal Processing, 2009. ICASSP 2009 IEEE International Conference on, pages 1597-1600. IEEE, 2009.