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

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

МЕТОДЫ СТРУКТУРНОГО АНАЛИЗА ИЗОБРАЖЕНИЙ ТРЕХМЕРНЫХ СЦЕН

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

АВТОРЕФЕРАТ

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

Санкт-Петербург - 2014

005557782

005557782

Работа выполнена в Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики

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

Луцнв Вадим Ростиславович

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

доктор технических наук, профессор, ОАО «Научно-производственное объединение «Карат», заместитель генерального директора по научной работе

Паламарь Ирина Николаевна

кандидат технических наук, доцент, Рыбинский государственный авиационный технический университет имени П.А. Соловьева, профессор кафедры «Вычислительные системы»

Ведущая организация: Филиал ОАО "Корпорация космических

систем специального назначения "Комета"-"Научно-проектный Центр оптоэлектронных комплексов наблюдения"

Зашита состоится «11» декабря 2014 г. в 17 часов 30 минут на заседании диссертационного совета Д 212.227.03 при Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д.49., ауд. 285.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики по адресу: 19710], Санкт-Петербург, Кронверкский пр., д.49 и на сайте ffapo.ifmo.ru.

Автореферат разослан « _2» ^^^ 2014

года

Ученый секретарь

диссертационного совета / Дударенко Наталия Александровна

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

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

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

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

Основные задачи:

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

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

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

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

1. Предложен способ верификации кластерных гипотез сопоставлений локальных признаков с помощью модифицированного алгоритма ЯАНЗАС и метода наименьших квадратов. Низкая вычислительная сложность алгоритма И-АК^АС достигается за счет проверки случайных выборок сопоставлений на их согласованность по параметрам между собой и с параметрами восстановленного по ним преобразования группы подобия (Ш'П).

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

3. Предложен способ генерации сопоставлений КТ по гистограммам визуальных слов (ГВС). При поиске изображений трехмерных сцен в использованной базе данных (БД) предлагаемые методы структурного анализа параметров сгенерированных сопоставлений КТ обеспечивают уменьшение количества ошибок второго рода на 36% и десятикратное уменьшение количества ошибок первого рода.

4. Усовершенствованы «энергетические» алгоритмы построения плотных карт глубины за счет использования диспаратностей сопоставленных

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

Практическая значимость работы. Разработанные методы и алгоритмы полезны при автоматическом анализе изображений в условиях априорной неопределенности сюжета изображения, при наличии сложных ракурсных и яркостных искажений. Они позволяют надежно сопоставлять изображения трехмерных сцен, причем допускается значительное изменение позиции фотокамеры при съемке сцен, а также перемещение отдельных объектов в сцене. Возможно сопоставление аэрокосмические снимков, сделанных сенсорами различающихся типов, при наличии сезонно-суточных и антропогенных изменений местности. Это позволяет выявлять изменения и комплексировать изображения. Предложены способы использования информации о смещен™ сопоставленных локальных признаков в целях увеличения эффективности алгоритмов построения плотных карт глубины. Также разработаны алгоритмы поиска изображений в БД с использованием ГВС, которые позволяют сократить время поиска и объемы памяти, необходимые для хранения БД.

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

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

На защиту выносятся следующие положения и результаты:

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

2. Алгоритм удаления сопоставлений «многие-к-одному», который позволяет увеличить пропорцию корректных сопоставлений, а также уменьшить количество кластеров некорректных сопоставлений.

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

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

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

Апробация работы. Результаты работы были представлены: на международной конференции «Third international topical meeting «Optical sensing and Artificial Vision» (СПб, 2012), I международной научной школе «Методы цифровой обработки изображений в оптике и фотонике» (СПб, 2014), 1 и II конференциях молодых ученых и специалистов «Будущее оптики» (СПб, 2012, 2013), II Всероссийской научно-практической конференция молодых ученых и специалистов «Инновационные подходы к развитию вооружения, военной и специальной техники» (Москва, 2011), III молодежной школе-семинаре «Управление и обработка информации в технических системах»

(Таганрог, 2011), научной сессии ГУАП (СПб, 2011), 68-й региональной конференции студентов, аспирантов и молодых ученых в СПб ГУТ (СПб, 2014), на XLII и XLIII научных и учебно-методических конференциях профессорско-преподавательского и научного состава в Университете ИТМО (СПб, 2013,2014). Два доклада были отмечены:

- дипломом за первое место в конкурсе докладов «Управление и обработка информации в технических системах» третьей молодежной школы-семинара в г. Таганроге в 2011 г;

- дипломом победителя конкурса «за лучший доклад на научной школе» в рамках конгресса молодых ученых в г. Санкт-Петербурге в 2014 г.

В 2014 за работу на тему «Структурный анализ изображений трехмерных сцен» в «ГОИ им. С.И. Вавилова» решением конкурсной комиссии автору диссертации была назначена стипендия имени академика Рождественского первой степени.

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

Реализация результатов работы. Результаты работы использованы в разработках ОАО «ГОИ им. С. И. Вавилова», компаниях «LG Electronics» и ООО «Пекод», что подтверждают полученные акты о внедрении. Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 172 наименований. Содержание работы изложено на 155 страницах. В работе содержится 31 рисунок и 3 таблицы.

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

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

В первой главе диссертации проведен обзор современных методов структурного анализа изображений. Было показано, что при анализе изображений трехмерных сцен целесообразно использовать методы, оперирующие локальными признаками, поскольку локальные участки изображения подвержены ракурсным искажениям в меньшей степени, чем всё изображение целиком, а локальные признаки могут быть сопоставлены независимо друг от друга. Первые три этапа СА изображений при использовании локальных признаков, как правило, включают: обнаружите КТ на изображениях, описание КТ с помощью дескрипторов и сопоставление дескрипторов двух изображений. Наиболее известные методы обнаружения, описания и сопоставления локальных признаков - SIFT и SURF. Во многих случаях подавляющая часть сопоставлений дескрипторов оказывается ошибочной, поэтому необходимо учитывать пространственное положение сопоставленных КТ, чтобы удалить ошибочные сопоставления. Анализ методов СА сопоставлений КТ показал, что в настоящее время используемые алгоритмы учета геометрии трехмерных сцен являются либо недостаточно робастными, либо накладывают слишком жесткие ограничения на анализируемые сцены. В частности, показывается, что восстановление адекватной эпиполярной геометрии не возможно, если количество ошибок сопоставления дескрипторов КТ больше 70-75% от общего числа сопоставлений. По результатам проведенного анализа была поставлена задача разработки методов учета геометрии трехмерных сцен.

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

Предварительная «отбраковка» сопоставлений. Для исследования возможностей разных методов были выбраны 20 достаточно «сложных» для сопоставления пар изображений трехмерных сцен, которые были сопоставлены

с помощью метода SURF. Среди всей совокупности полученных сопоставлений KT вручную были отмечены корректные сопоставления. В общей сложности было автоматически сопоставлено и вручную промаркировано приблизительно 24000 сопоставлений KT, из них около 1000 оказались корректными.

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

• Исходные сопоставления -Обработанные сопоставления ^ (б)

0.2 0,4 0,6 0,8 Соотношение расстояний

50 200 350 500 650 Количество анализируемых сопоставлений, ед.

Рисунок 1 - (а) - плотности вероятности правильных и ошибочных сопоставлений в зависимости от соотношения расстояний до двух ближайших соседей; (б) - количество ложных кластеров из трех и более сопоставлений до и после удаления структурных соответствий «многие-к-одному»

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

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

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

Таблица 1 - Повышение точности процедуры «отбраковки» сопоставлений

Метод tP Ф tn fii Точность (Precision) Полнота (Recall) Fi-мера

Б/о 961 23295 0 0 0,039 1,000 0,076

Ml 584 8003 15292 377 0,068 0,607 0,122

М2 231 1202 22093 730 0,161 0,240 0,192

Ml +М2 241 1089 22206 720 0,181 0,250 0,210

Обозначения: «Б/о» - без обработки, «М1» - удаление сопоставлений «многие-к-одному», «М2» - использование соотношения расстояний до двух ближайших соседей, «tp» - правильные сопоставления (true positives), «fp» -ошибки первого рода (false positives), «tn» - неправильные, но корректно

отвергнутые сопоставления (true negatives), «fn» - ошибки второго рода (false negatives).

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

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

кластерной гипотезы

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

ПГП адресует точке [х,у] другую точку [и, у] и может быть представлено в виде набора более примитивных операций: масштабирования на коэффициент 5, поворота на угол ¡5 и сдвига на [1Х, /,.]:

Известен способ восстановления параметров ПГП по сопоставлениям ключевых точек, попавшим в один кластер. Для этого в формулах (1) принимается сое/?, п=8-5\хф, тогда можно составить следующую систему линейных алгебраических уравнений (СЛАУ):

где [и„у,] и [х„_у,] - это координаты сопоставленных KT. Решая эту систему методом наименьших квадратов (МНК), можно восстановить неизвестные параметры ПГП т, п, tx, ty, которые затем использовать для удаления сопоставлений, не согласующихся с ними. Эксперименты показали, что такой метод восстановления ПГП кластера является недостаточно надежным, поскольку выброс со значительным отклонением дает больший вклад в значение целевой функции, чем сумма отклонений нескольких корректных сопоставлений (пропорционально квадрату невязхи). В связи с этим диссертации были также исследованы другие способы восстановления параметров 11111 кластера:

u=xScosß-y-Ssiaß+tx, v=>x-Ssinß+y-Scosß+t,

■у

(1)

mx0-ny0+tx=u 0 nx0+my0+ty=v0 mxx -nyx+tx=ux

(2)

- с помощью МНК, no при использовании в уравнениях (1) в качестве угла ß «среднего» угла разворота сопоставленных KT;

- за счет выбора «средних» параметров ПГП всех сопоставлений KT, образовавших кластер;

- с помощью метода, основанного на случайных выборках (RANSAC).

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

Количество случайных выборок (итераций) к, которые необходимо проанализировать с помощью алгоритма RANSAC, определяется вероятностью Р получения хотя бы одной безошибочной выборки

P = l-[l-(/)2]\ (3)

где / - пропорция корректных сопоставлений в кластере. Если задать ограничение Р > 1 - а, то к можно определить по формуле

Ä>log1(/)2(a). (4)

В данной диссертационной работе экономия вычислительных ресурсов достигается за счет проверки случайных выборок сопоставлений на их согласованность по параметрам между собой и с параметрами восстановленного по ним ПГП. Показывается, что при 50% ошибочных сопоставлений в кластере такие проверки обеспечивают достаточно высокую вероятность получения безошибочной выборки, что позволяет отказаться от традиционного для RANSAC этапа проверки корректности выборок за счет подсчета сопоставлений кластера, поддерживающих восстановленные параметры 11111. Для уточнения параметров 11111 по сопоставлениям, отклоняющимся от найденных параметров ПГП в установленных пределах, предлагается составлять и решать СЛАУ (2) с помощью МНК.

В третьей главе рассмотрена задача поиска изображений трехмерных сцен в БД. Была использована концепция визуальных слов, в рамках которой изображения описываются с помощью ГВС, а также словаря визуальных слов. В классической концепции визуальных слов сопоставление изображений осуществляется без учёта взаимного положения КТ (соответствующих определенным визуальным словам) на изображении, что позволяет системе быть устойчивой, если объекг имеет сильноизменчивую форму, но понижает ее различающие способности. Для преодоления этого недостатка предлагается по двум ГВС генерировать сопоставления КТ, а затем проводить СА этих сопоставлений с помощью методов, предложенных в главе 2.

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

Гистограмма 1

Гистограмма 2

ш

ш

Визуальное слово ( Параметры КТ,

__С™!? --- — попавших I

соответствующие ячейки ГВС

Сопоставления КТ Рисунок 2 - Генерация сопоставлений КТ по двум ГВС

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

дескрипторов общее количество требуемой памяти снижается более чем на порядок. Также по двум ГВС можно получать сопоставления КТ быстрее, чем за счет сравнения дескрипторов КТ.

Предложен альтернативный способ преодоления «граничного эффекта» при проведении преобразования Хафа с помощью использования нескольких аккумуляторов, смещенных в пространстве параметров по каждому измерению на длину половины ячейки аккумулятора в каждом измерении. Показано, что при частичном игнорировании граничного эффекта, возможно значительное повышение быстродействия разработанных алгоритмов кластерного анализа за счет уменьшения количества ложных кластеров. При этом в соответствии с проведенными экспериментами наблюдается уменьшение количества корректно сопоставленных изображений лишь на 0,3%.

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

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

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

для которых посредством ручной маркировки были рассчитаны эталонные фундаментальные матрицы, используя которые, проверялось, лежат ли автоматически сопоставленные КТ на соответствующих эпиполярных линиях. Для сравнения возможностей разных методов использовались следующие критерии: среднее отклонение сопоставленных КТ от эталонных эпиполярных линий (Л); пропорция корректных сопоставлений (находящихся вблизи эталонных эпиполярных линий) (а); количество «правильно сопоставленных пар изображений», на которых корректных сопоставлений КТ больше 50% (И). Результаты для нескольких из исследованных алгоритмов обнаружения, описания и сопоставления КТ, приведенные в таблице 2, показывают, что предложенные алгоритмы значительно превосходят методы, основанные на учете эпиполярной геометрии, а разработанная программа имеет лучшие характеристики, чем альтернативное платное программное обеспечение.

Таблица 2 - Результаты сопоставления изображений трехмерных сцен

Детектор Дескриптор Метод CA N о,% А, пике.

SURF SURF ЭГ 205 53,76 106,92

ERSP Library 286 79,21 43,77

SIFT SIFT КА 300 82,85 32,73

SURF SURF КА 309 83,09 33,10

SURF BoW(SURF) КА 273 88,37 20,12

SURF BRISK КА 307 82,82 36,40

Обозначения: ЭГ - эпиполярная геометрия, КА - разработанные алгоритмы кластерного анализа параметров сопоставленных KT, ERSP Library -закрытое платное программное обеспечение для сопоставления изображений, BoW(SURF) - словарь визуальных слов на основе дескрипторов SURF. Пример сопоставленных изображений приведен на рисунке 3.

Рисунок 3 - Сопоставления признаков вШ^ до и после удаления ошибок. Количество корректных сопоставлений КТ до проведения кластерного анализа — 5,1%, после - 96,9%. Корректность сопоставлений КТ определялась экспертом

Поиск изображений трехмерных сцен в БД с использованием ГВС. В таблице 2 (Во\у(8иКР)) приведены результаты применения разработанных алгоритмов кластерного анализа к сопоставлениям КТ, сгенерированным по ГВС. Эти результаты позволяют говорить, о том, что такой способ генерации сопоставлений КТ может быть полезен при сопоставлении изображений трехмерных сцен, по крайней мере, в задачах, в которых критичны время и объем памяти, занимаемый БД. Показывается, что существует потенциал для развития подхода. В таблице 3 приведены результаты поиска изображений в БД из 300 изображений при использовании ГВС совместно с разработанными методами СА на основе параметров сопоставленных КТ и при использовании только ГВС.

Таблица 3 — Поиск изображений в базе данных

Метод Запросов Распознано Ошибочно распознано Не распознано

ГВС 44 22 22 0

ГВС+СА 44 30 2 12

Эксперименты подтвердили высокие скоростные характеристики разработанных алгоритмов - генерация сопоставлений КТ и проведение структурной верификации двух ГВС на стационарном компьютере занимает в среднем 3 мс.

Построение плотных карт глубины. Восстановление глубины при использовании стереокамеры сводится к решению задачи сопоставления пикселей левого и правого изображений. В настоящее время для построения плотных карт глубины популярны «энергетические» подходы, которые используют предположение о преимущественной гладкости карт глубины. Задача отождествления пикселей двух изображений в этом случае формулируется как задача минимизации корреляционной энергии и энергии связи. Такие методы принимают на вход матрицу корреляционной энергии размерами ЛхО£, где К'С - размер изображения стереопары, I - разница между минимальным и максимальным значением диспаратности в стереопаре (ширина диапазона допустимых диспаратностей О). Поскольку правильная оценка диапазона £> позволяет сократить время, необходимое для восстановления карты глубины, то предлагается использование диспаратностей сопоставленных КТ для уточнения этого диапазона: ¿) = [тшй?, ,тах^], где с1:-

г /

диспаратность, соответствующая 1-му сопоставлению.

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

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

Рисунок 4 - Результат модификации матрицы корреляционной энергии с помощью диспаратностей сопоставленных отрезков прямых линий, (а) - левое изображение стереопары, (б) - карта глубины, восстановленная с помощью алгоритма Graph Cut, (в) — результат использования опорного списка диспаратностей для модификации матрицы корреляционной энергии

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

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

по 0,1% от общего числа сопоставлений. Примеры сопоставленных изображений приведены на рисунке 5.

Рисунок 5 - Отображение одного из сопоставленных изображений в систему координат другого изображения с помощью преобразования, восстановленного по координатам сопоставленных локальных признаков, (а) - сопоставление в условиях сезонно-суточных изменений (для лучшего визуального восприятия результатов

группы строк первого и второго изображения чередуются), (б) - результат последовательного автоматического совмещения аэрокосмических снимков, сделанных в 1942, 1979 и 2014 годах, соответственно

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

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

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

1. Для удаления ошибок сопоставления локальных признаков целесообразно использование алгоритмов кластерного анализа параметров сопоставленных КТ, которые позволяют сопоставлять изображения трехмерных сцен при наличии до 95% ошибочно сопоставленных дескрипторов КТ.

2. Верификацию кластеров сопоставлений целесообразно проводить в пространстве параметров ПГП, а не более общих аффинных и проективных

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

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

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

5. Совместное использование параметров КТ и ГВС позволяет значительно снизить потребляемые при структурном анализе вычислительные ресурсы без существенного уменьшения надежности сопоставления.

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

СПИСОК ПУБЛИКАЦИЙ В изданиях, рекомендуемых ВАК:

1. Малашин, P.O. Сопоставление изображений трехмерных сцен с помощью кластеризации сопоставленных локальных признаков посредством преобразования Хафа [Текст] / P.O. Малашин // Оптический журнал. - 2014. -Том 81. - №6 - С. 34-42. - 1,1 п.л.

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

[Текст] / P.O. Малашин, В.Р. Луцив // Оптический журнал. - 2013. - Том 80. -№11 - С. 57-63. - 0,8/0,4 п.л.

3. Malashin, R. Application of structural methods for stereo depth map improvement [Текст] / R. Malashin, M. Peterson, V. Lutsiv // Proceedings of International Topical Meeting on Optical Sensing and Artificial Vision. - 2013. - P. 27-33. - 0,45/0,15 пл. Прочие издания:

4. Малашин, P.O. Технология трехмерного представления зрительной информации на плоском экране с помощью видеокамеры [Текст] / P.O. Малашин, A.C. Рожков // Материалы Шестой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» и третьей молодежной школы-семинара «Управление и обработка информации в технических системах» [Текст]. - 2011. - С. 447-451. - 0,3/0,15 пл.

5. Малашин, P.O. Псевдо-ЗО монитор на мобильном устройстве // Сборник докладовнаучнойсессииГУАП[Текст]/Р.О.Малашин.-2011.-С.76-78.-0,2п.л.

6. Малашин, P.O. Использование структурных методов для построения плотных карт глубины [Текст] / P.O. Малашин // Сборник трудов I конференции молодых ученых «Будущее оптики» для молодых специалистов, кандидатов наук, аспирантов и студентов оптической отрасли и смежных дисциплин из Санкт-Петербурга и Ленинградской области. - 2012. - С. 63-65. - 0,2 п,л.

7. Малашин, P.O. Методы сопоставления изображений трёхмерных сцен [Текст] / P.O. Малашин // Сборник трудов II конференции молодых ученых «Будущее оптики» для молодых специалистов, кандидатов наук, аспирантов и студентов оптической отрасли и смежных дисциплин. - 2013. - С.42-45.-0,25 пл.

8. Малашин, P.O. Ускоренная индексация изображений на основе их содержания [Текст] / В.Р. Луцив, P.O. Малашин, А.Б. Кадыков, H.A. Деготинский // Альманах научных работ молодых ученых Х1ЛП научной и учебно-методической конференции Университета ИТМО. - 2014. - С. 264-266. -0,2/0,05 пл.

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., 14 Тел. (812) 233 46 69. Объем 1,0 у.п.л. Тираж 100 экз.