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

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

Чумаченко Александр Викторович

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

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

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

Таганрог 2014

005561345

005561345

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

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

Официальные оппоненты:

Ведущая организация:

Гузик Вячеслав Филиппович,

доктор технических наук, профессор, ФГАОУ ВО«Южиый федеральный университет», кафедра вычислительной техники, заведующий

Ковалев Олег Федорович,

доктор технических наук, профессор, ФГБОУ ВПО «Южно-Российский государственный политехнический университет (НПИ) имени М.И. Платова», кафедра «Информационная безопасность, телекоммуникационные системы и информатика», профессор, г. Новочеркасск

Саблина Виктория Александровна, кандидат технических наук, доцент, ФГБОУ ВПО «Рязанский государственный радиотехнический университет», кафедра электронных вычислительных машин, доцент, г. Рязань Открытое акционерное общество «Научно-копструкторское бюро вычислительных систем», г. Таганрог

Защита состоится «20» февраля 2015 г. в 16-30 на заседании диссертационного совета Д 212.208.21 при Южном федеральном университете по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 34410^15£Хостов-на-Дону, ул. Зорге, 21 Ж.

Диссертация в http://hub.sfedu.ru/diss/announcert:

электраша

Н А У 1с

ЭЕ СБР

ЕДЕ

доступна

адресу:

----- >. о?

Автореферат разослан Ученый секретарь диссертационного сов доктор технических А ,

УйГ*

Боженюк А.В.

ш

Общая характеристика работы

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

Одним из главных этапов построения модели местности по нескольким изображениям является оценка удаленности наблюдаемых объектов. Главным признаком удаленности служит параллакс движения - более близкие к точке съемки объекты характеризуются большей величиной параллакса на изображениях стереопары и наоборот. Величина параллакса определяется посредством идентификации пикселов изображений стереопары. Идентификация пикселов смежных снимков - один из основных процессов цифровой стереофотограмметрии и машинного зрения, точность которого в значительной степени определяет качество последующих этапов. Идея автоматизации этого процесса была сформулирована профессором A.C. Скиридовым в 1924 году и базировалась на сравнении фотографических плотностей соответственных зон смежных снимков. До практической реализации эта идея была доведена лишь в середине 1980-х годов при создании цифровых фотограмметирических систем.

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

. Величина d=xrx¡ является параллаксом проекции точки М на изображениях стереопары. Эту величину также называют диспаритетом (анг. - disparity). Упорядоченную совокупность величин параллакса для всех пикселов стереопары называют картой диспаритетов (анг. - disparity map), стереосоответствием (анг. - stereocorrespondance), картой глубины (анг. - depth шар).

Задача вычисления стереосоответствий стереопар активно изучается с середины 70-х годов прошлого века. Для её решения разработано и адаптировано множество подходов, методов и алгоритмов. Среди них находят применение динамическое программирование в работах Hirschmuller Н. и Deng Y., билатеральная фильтрация (анг. - bilateral filtering) в работах К. J. Yoon и Mattoccia S., алгоритмы из теории графов в работе Колмогорова В. и Зэбих Р., методы цифровой обработки

сигналов в работе ВЬаш А. и ЫаЬауапсН Б. Многие из существующих подходов имеют высокую точность и быстродействие. Однако достижение высокой точности одновременно с высокой скоростью обработки стереопар - нетривиальная алгоритмическая и техническая задача.

Рисунок 1 - Пространственная модель формирования изображений стереопары

Реализация высокоточных трудоемких методов на специализированных вычислителях, таких как GPU (анг. - Graphics Processing Unit), позволяет достичь высокой производительности, как показано в работах Котюжанского JI., Xing М. и др. Однако конечные системы могут иметь ограничения энергопотребления и массо-габаритных характеристик, несовместимые с применением специализированных вычислителей, например GPU. В связи с этим можно выделить направление исследований, связанное с задачами уменьшения вычислительной сложности и/или повышения точности существующих методов и алгоритмов, ориентированных на вычислители общего назначения.

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

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

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

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

Оптический центр

Оптическая ось

м

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

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

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

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

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

4. Разработан и исследован быстродействующий комплексный алгоритм поиска пиксельных соответствий на стереопарах, отличающийся от существующих тем, что изначально ориентирован на универсальный вычислитель и не задействует векторные инструкции (типа SIMD, анг. - Single Instruction Multiple Data) или средства многопоточных вычислений. При этом время работы программной модели алгоритма в среднем в 2 раза меньше аналогов, сопоставимых по точности.

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

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

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

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

1. Комплексный алгоритм установления пиксельных соответствий стереопар.

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

3. Статистический метод оценки границ значений диспаритетов стереопар.

4. Метод оптимизации контекстно-независимых функций сравнения опорных окон с помощью интегральных массивов.

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

6. Приложение структуры данных «Система непересекающихся множеств» в методе слияния малых сегментов метода сегментации изображения. Реализация и использование результатов работы. Результаты

диссертационного исследования использовались при выполнении г/б НИР №12252 «Разработка теории и принципов построения интеллектуальных высокопроизводительных реконфигурируемых многопроцессорных вычислительных систем на основе аппаратных мультипрограммных средств и специализированных трансляторов алгоритмов в аппаратные программы», а также в учебном процессе по курсу «Проектирование проблемно-ориентированных вычислительных систем» кафедры «Вычислительной техники» федерального государственного автономного образовательного учреждения высшего образования «Южный федеральный университет» (ФГАОУ ВО «Южный федеральный университет»).

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

Апробация работы. Основные результаты работы докладывались на:

1. VII Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии системный анализ и управление», 2009.

2. III Всероссийская научная конференция молодых ученых, аспирантов и студентов «Современные технологии, естествознание, педагогика», СТЕПЬ-2014.

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

Структура н объем работы. Диссертационная работа состоит из введения, четырех глав основного раздела, заключения, списка литературы и приложений. Основное содержание работы изложено на 113 страницах, включая список литературы из 69 наименований, материалы приложений изложены на 21 странице.

СОДЕРЖАНИЕ РАБОТЫ Во введении приводится обоснование актуальности темы диссертационной работы. С учетом нерешенных проблем определяется цель работы, определяется круг задач, методы исследований, аргументируется научная новизна. Сформулированы основные положения, выносимые на защиту, а также научная и практическая ценность исследования.

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

где / - фокусное расстояние камеры, В - величина стереобазы (расстояние между точками съемки), d=X2-xt — разность координат соответствующих пикселов па изображениях стереопары, Z — расстояние от плоскости съемки до точки М. Оценка точности стереосоответствий, как правило, опирается на две величины:

• доля пикселов у которых, значение диспаритета отличается более чем на 6,j от корректного значения;

• среднеквадратическое отклонение от корректного значения величины диспаритета для всех пикселов стереопары.

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

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

Для экспериментов используются 10 стереопар из работы D. Scharstein, находящиеся в свободном доступе на сайте коллежда Миддлбери, США, в части портала компьютерного зрения (URL: http://vision.middlebury.cdu/sterco/data). Разрешение изображений варьируется от 384x288 до 695x555, стереопары разделенны на два множества, здесь и далее именуемые набор-1 и набор-2. Для стереопар из набора-2 известны параметры съемки: фокусное расстояние¡=3740 пике., стереобаза В- 160мм. На практике фокусное расстояние цифровых фотокамер /< 1м, а для большинства объективов составляет 35-120мм. В силу этого, наибольший вклад в значение выражения (1) вносит второе слагаемое. Тогда удаленность объекта можно оценить по упрощенной формуле (2), а разрешение по глубине вычислять по формуле

(3).

d Р)

AZ(d, е) = I Z(d) - Z(d + e)\ =

f-B f-B

d d + e d-(d + e) (3)

d d + e

Оценка удаленности объектов сцены по формуле (2) для стереопары 2005 Art дает приблизительный диапазон расстояний [2,77.. 7,48] м. Разрешение по глубине падает при удалении объектов от плоскости съемки. При половинном разрешении изображения (555x695 пикселов), стереобазе В=0,04м, ошибке определения диспаритета Sj=l, разрешение по глубине составляет [0,099 .. 0,680] м.

Вычислительная сложность основного этапа идентификации пикселов, как правило, может быть описана выражением Ofxd), где ¿/-максимальное значение диспаритета пикселов, х - множитель, включающий зависимости от других параметров стереопары. В общем случае значения диспаритета лежат в интервале [0..W], где W - ширина изображения стереопары в пикселах (при горизонтальном парралаксе). На практике, при сравнительно небольших значениях стереобазы, величины параллаксов могут составлять не более 1/20 от ширины изображения. Определение фактического диапазона значений диспаритетов сужает область поиска соответствующих пикселов с [0..WJ до [dm,„..dmaJ. Также это делает возможным применение различных методов оптимизации, например приемов динамического программирования для вычисления значений функции сравнения опорных областей.

Разработанный метод оценки границ диспаритета стереопары состоит из трех этапов. На первом этапе по малой статистической выборке вычисляется приблизительная оценка максимального значения диспаритета dm.,x. На втором этапе вычисляются вспомогательные интегральные массивы для всех значений диспаритета в пределах [0..dmaJ, позволяющие ускорить расчет функции сравнения опорных областей на два порядка. На третьем этапе размер статистической выборки увеличивается приблизительно в 10 раз, что позволяет уточнить границы диспаритета

по сравнению с первым этапом. Метод статистической оценки границ диспаритета опирается на следующие неравенства (4) и (5):

Выражение (4) назвают неравенством Чебышёва. Оно дает грубую оценку вероятности Р отклонений значений случайной величины (СВ) X от её математического ожидания ¡л через дисперсию а. Выражение (5) называют неравенством Высочанского-Петунина. Оно уточняет неравенство (4) для одномодальных выборок (см. Высочанский Д. Ф., Петунии Ю. И. Обоснование правила трех сигм для одномодальных распределений. Теория вероятностей и мат. статистика, 1979, вып. 21, С. 23-35). Соответственно в алгоритме, реализующем метод, неравенство (4) применяется для многомодальных статистических выборок (принимается h=4), неравенство (5) - для одномодальных (принимается к=3). На практике чаще всего задействуется второе неравенство, так как выборки в большинстве случаев одномодальны.

Рассмотрим пример возможного распределения значений диспаритета. Пусть существует выборка S такая, что \S\=*20 и S=flxl8, 10x2}, то есть число «1» встречается 18 раз, а число «10» встречается 2 раза. Для такой выборки математическое ожидание СВ ц-1,9, а стандартное отклонение а=2,77. Выборка смещена в сторону меньших по модулю значений. Но даже в таком «неблагоприятном» случае правило трех сигм приводит к корректной оценке верхней границы (fj+3 cr)=10,21.

Подробное описание алгоритмов, соответствующих первому и третьему этапу метода оценки, приведено в диссертации (стр. 34-39). По результатам экспериментов точность оценки верхней и нижней границы диспаритетов после трех этапов составляет не менее 94%, в среднем 98%, что хорошо согласуется с теоретическими оценками. Время работы программной модели ачгоритма не превышает 65мс на стереопару.

Во второй главе рассмотрен комплекс вопросов, связанных с оптимизацией н точностью результатов известных функций сравнения опорных областей. Исследование этих вопросов является актуальной научной задачей и нашло отражение в работах Аргутина В., Hirschmuller H. и др. В данной главе разработан метод оптимизации вычисления контекстно-независимых функций с помощью интегральных массивов и определены границы его применимости. В частности показано, что метод применим к функциям SAD (анг. - Sum of Absolute Différencies, рус. - сумма абсолютных значений разностей) и SSD (анг. - Sum of Squared Différencies, рус. - сумма квадратов разностей). Альтернативой методу интегральных массивов может быть метод скользящего окна. Однако он имеет ряд недостатков: опорное окно должно быть константного размера, порядок обхода опорных окон

(4)

4

(5)

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

Наибольшая точность идентификации пикселов достигается при использовании функций ранговой оценки (анг. - Rank), Census и ZSAD (анг. - Zeroed Sum of Absolute Différencies, рус. - сумма абсолютных разностей с коррекцией по среднему), однако оптимизация указанными выше методами для них невозможна в силу свойства контекстной зависимости. Свойство контекстной зависимости означает, что вклад некоторого пиксела изображения и значение функции сравнения опорных областей не может быть расчитан заранее для произвольной опорной области в силу зависимости от её параметров (положения, размеров и т.д.).

То есть метод интегральных массивов и метод скользящего окна применимы только для контекстно-независимых функций. Вычислительная сложность предварительных расчетов и основного шага установления пиксельных соответствий в данном случае сокращается с O(Nnmd) до 0(N-d), где N - число пикселов стереопары, ¿-число возможных значений диспаритета.

Функция Census формирует для опорной области «двоичный отпечаток» или двоичный вектор. При сравнении опорных областей фактически вычисляется расстояние Хэмминга между двумя двоичными векторами. По своей сути функция Census соответствует функциям типа «перцептивный хэш». Вычисление знзчения функции Census может быть оптимизировано «упаковкой» опорных областей в двоичные векторы фиксированного размера с последующим применением побитовых операций. Вычислительная сложность предварительных расчетов и основного шага установления пиксельных соответствий в данном случае составит 0(N-n-m)+0(?l-dmaJ, где N - число пикселов изображения стереопары, п,m - размеры опорного окна.

Таким образом, в связи с возможностью применения оптимизаций множество исследуемых в данной диссертационной работе функций составляют SAD, SSD и Census. Рассмотрим подробнее схему сопоставления опорных окон, метод скользящего окна и метод интегральных массивов. Пусть пикселы pt и р2 являются смежными и лежат на одной горизонтальной прямой в координатах изображения, как показано на рисунке 2.

Опорные множества пересекаются и образуют непустое множество Р,ЛР,. При наложении опорных окрестностей базового изображения на второе в позиции x+d и х+d+lдля пикселов р, и р2 соответственно, множество Р1ЛР2 будет наложено на одну и ту же область второго изображения. Вычисление вклада пикселов в значение функции по отдельности приводит к повторному вычислению функции для одних и тех же подмножеств наложений. Таким образом, задача оптимизации вычисления значений целевой функции S(P,d), где Р - можество пикселов опорного окна, d -значение диспаритета, заключается в исключении повторных вычислений для

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

Р[ и Р2 обозначают опорные множества для пикселов и р2 соответственно. Используя обозначения из теории множеств, выразим наложение множества Р2 в позицию х+с!+1 через 5(Р/,с1), как показано в формуле (6):

\7?,</+1) (б)

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

Базовое изображение

Второе изображение

Рисунок 2- Пересечение областей Р/иР^и их общее подмножество Для пояснения сути метода интегральных массивов рассмотрим пример. Пусть задан некоторый массив чисел А\

А = {3, 12,-1,0, 28, 5,7,-10, 2, 7} Пусть массив не изменяется и необходимо отвечать на запросы вида: какова сумма элементов массива, начиная с индекса / и заканчивая индексом г. Рассчитаем

вспомогательный массив В, в котором элемент В, равен сумме элементов B0...Bj. Для приведенного примера массив будет иметь вид:

В = {0, 3, 15, 14, 14, 42,47, 54, 44. 46, 53} Теперь сумму элементов на отрезке [!,г] можно вычислить за O(I):

Сумма(1, г) = 5[г] - В[1 -1] (7)

Этот подход обобщается и для случая произвольной размерности. Прямоугольные опорные области описываются двумя координатами (х,у), а функция сравнения опорных областей вычисляется для различных значений диспаритета d. Следовательно, вспомогательный интегральный массив D должен быть трехмерным. Произвольный элемент D[d,i,j] должен быть равен сумме значений функции для всех пикселов с координатами (x6l..j, у el.Л):

WJ] = iZS(P(x,y),d) (8)

х=1 у=I

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

Значения элементов массива D для некоторого d можно вычислять за O(l), используя приём динамического программирования. Для расчета D[d,i,j] использовать уже вычисленные значения для меньших i и у:

D[d, i, j] = D[d, i -1, j] + D[d, ij-1] - £>[<*, i -1,7 -1] + 5"(Р(г, у), J) (9)

Прямоугольную опорную область пиксела р обозначим как R, её границы по оси X обозначим хтШ и хтах, по оси Yymb, и утах, как показано на рисунке 3. Тогда значение функции для всей опорной области можно вычислить за 0(1) по формуле:

S(R,d) = D[d,уш,xmax ] - D[d, ут№,хтт -1]-D[d,ymin -l,xmaJ + D[d,ymb-l,xmin -1] 0,0

Хтах ]

* "И

(10)

Рисунок 3 - Опорная область К, вспомогательные области для вычисления значения функции сравнения опорных областей Таким образом, метод интегральных массивов требует ОСЫЛтах) дополнительной памяти для вспомогательных таблиц и 0(Ы^тш) операций для их расчета, а также 0(Ы-Лпах) операций на основном шаге поиска стереосоответствий.

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

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

В современных наиболее точных методах идентификации пикселов в том или ином виде в вычислительный процесс включается дополнительная пространственно-цветовая информация групп пикселов, позволяющая повысить точность стереосоответствий. Такой подход отражен в работах Wang Z. (статья «А region based stereo matching algorithm using cooperative optimization»), Xing Mei et al. (статья «On building an accurate stereo matching system on graphics hardware») и Klaus A. et al. (статья «Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure»). Методы из этих работ погалаются на то, что близкорасположенные пикселы похожего цвета принадлежат одному предмету и равноудалены от плоскости съемки. Для выделения групп пикселов схожего цвета применяется сегментация изображения. В рассмотренных работах авторы используют «Mean-shiftw-ссгмснтацию (рус. - сдвиг среднего), представленную в работе D. Comaniciu и Р. Meer «Mean shift: A robust approach toward feature space analysis». Такой подход приводит к увеличению точности стереосоответствий, однако время работы программной модели в части сегментации составляет около 10 секунд на стереопару. Разработанный в данном исследовании многокритериальный метод сегментации имеет линейную сложность, а его программная реализация затрачивает не более 65 мс на стереопару.

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

где Ад - нормировочный коэффициент расстояния пикселов, 1С -нормировочный коэффициент цветового расстояния пикселов в пространстве RGB (анг. - Red Green Blue, рус. - красный зеленый синий), D(p,p*) и С(р,р*) - функции вычисления оценок обычного и цветового расстояния пикселов р ир*.

Сегменты строятся из начального пиксела р„ а вновь добавяемые пикселы Pj должны быть смежными с уже включенными пикселами и удовлетворять условию:

F(Pi,Pj)>T (12)

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

xcij=s-(i+0.5), yc,]=s-(j+0.5) (13)

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

На обоих этапах для функции (11) в части сравнения цвета вместо цвета узлового пиксела р, передается среднее значение цвета RGB по текущей построенной окрестности L. Это снижает зависимость сегментации от выбора узлового пиксела. Приведем метод сегментации базового изображения (БИ) в виде псевдокода алгоритма:

Сегментация изображения стереопары (БИ)

1 Сформировать пустой список подмножеств S

2 Для всех л: из интервала 'As<x < БИ.Ширина

3 Для всех у из интервала Vzs<y< БИ.Высота

4 Если Пиксел Р(х,у) какому-либо S,

5 S„ *— Окрестность пиксела Р(х,у)

6 Добавить S„ в S

7 jw-y+i

8 x*—x+s

9 Для всех х из интервала 0 < х < БИ.Ширина

10 Для всех у из интервала 0 <у < БИ.Высота Н Если Пиксел Р(х,у) 0 какому-либо St

12 S„<— Окрестность пиксела Р(х,у)

13 Добавить S„aS

14 у*-у+1

15 лч-х+]

16 Вернуть список подмножеств S Получить окрестность пиксела Р(х,у)

1 Сформировать пустую окрестность пикселов L

2 Сформировать пустую очередь (FIFO) пикселов Queue

3 L <- Р(х,у); Queue*—P(x,y)

4 ARGB*—P(x,y)

5 Пока в очереди Queue есть элементы

6 Рг*— первый пиксел из очереди

7 Для каждого р смежного с Р2

8 Если (Пиксел р g какому-либо SJ И (Ffp, Р(х, у))

9 L *—р; Queue <— р

Ю Перерасчитать ARGB с учетом р

11 Вернуть окрестность пикселов L

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

FIFO (First in First out - aiir. первым пришел, первым ушел). Для произвольного связного графа сложность обхода в ширину составляет 0(N+M), где N - число вершин, М — число ребер. В рассматриваемом графе для каждой вершины существует не более 4-х смежных с ней вершин. При условии, что операции с очередью и вычисление функции F(x) производятся за 0(1), итоговая сложность алгоритма составляет 0(N), где ¿V - количество вершин в графе (число пикселов в базовом изображении стереопары).

На практике данный алгоритм сегментации генерирует много небольших сегментов, снижающих «информативность» кластеризации. Для уменьшения их числа в данном исследовании разработан двухэтапный метод слияния малых сегментов. На первом этапе для каждого сегмента S, с числом пикселов менее Т находится наиболее подходящий по цвету из ближайших сегментов Sm. На втором этапе для всех малых сегментов Ss производится слияние с соответствующими Sm. Для эффективного слияния применяется «Система непересекающихся множеств», описанная в книге Кормена Т.Х. и др. «Алгоритмы: построение и анализ». Вычислительная сложность сегментации с учетом слияния малых сегментов составляет O(N), где N - число пикселов на изображении стереопары.

В основе предлагаемого метода аппроксимации (уточнения) лежит предположение, что в пределах сегментов корректные значения диспаритета составляют существенную часть из всех возможных. Значение диспаритета d¡ для группы пикселов в пределах сегмента считается корректным, если их доля составляет не менее Х% от общего числа пикселов сегмента. В экспериментах данного диссертационного исследования принято Х-20%.

Программная модель соответствующих алгоритмов работает до 10 раз быстрее модели, основанной на методе сегментации SLIC-SP из работы Achanta R. и др. «SLIC Superpixels Compared to State-of-the-Art Superpixel Methods», при более высокой точности стереосоответствий. Число неверно найденных пиксельных соответствий снижается на величину от от 4% до 11% в зависимости от входных данных. Таким образом, экспериментальная проверка разработанных методов доказывает корректность исходных посылок, предположений и оценок вычислительной сложности их алгоритмической реализации.

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

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

Начало

Ввод изображений стереопары

Оценка dmax (алгоритм-1)

J Вычисление вспомогательных j интегральных массивов

Оценка [dm!„; dmeLK\ (алгорнтм-2)

Основной шаг совмещения стереопар

Сегментация и уточнение (МКСУ-1-МФ)

Локализация оценок диспаритета (алгоритм-3)

/ 5 / стереос!

Вывод ереосоответствия

^_Конец_

Рисунок 4 - Трехмерная визуализация рельефа стереопары 2005_Ап (слева) и блок-схема комплексного алгоритма установления стереосоответствий (справа) Таблица 1 - Варианты комплексного алгоритма КАУС

Локализация\Целевая ф-ия SAD SSD SAD+Census SSD+Census

С локализацией КАУС-1.1 КАУС-1.2 КАУС-1.3 КАУС-1.4

Без локализации КАУС-2.1 КАУС-2.2 КАУС-2.3 КАУС-2.4

В качестве вычислительного устройства использован универсальный процессор Intel(R) Coretm i7-ß820 с частотой З.бГГц (операционная система Microsoft™ Windows 7). Программная модель разработана на языке С++, для сборки в исполняемый файл использован компилятор и сборщик Microsoft"™ Visual С++ 9.0, многопоточность вычислений не задействована.

В экспериментах задействованы стереопары из набора-1 и набора-2. Критериями эффективности являются доля неверно-найденных соответствий (% ошибок), среднеквадратическое отклонение значений диспаритета всех пикселов от «эталона» (СКО) и суммарное для двух наборов время работы программной модели (время (сек.)). Результаты экспериментов приведены в таблице 2.

Таблица 2 — Итоговые показатели эффективности различных алгоритмов установления стереосоответствий для стереопар из набора-1 и набора-2 (10 стереопар)

Алгоритм % ошибок время (сек.) СКО

КАУС-1.1(8АО+лок.) 9,69% 2,800 1,606

КАУС-1.2(SSD+noK.) 9,86% 2,800 1,650

КАУС-1,3(S AD+MioK.+Census) 7,95% 4,656 1,496 •

КАУС-1.4(SSD+noK.+Census) 9,08% 4,374 1,616

КАУС-2.1 (SAD) •• 9,77% 4,704 1,974

КАУС-2.2 (SSD) 11,00% 4,743 2,209

КАУС-2.3 (SAD+Census) 8,27% 7,453 1,841

КАУС-2.4 (SSD+Census) 9,88% 7,177 2,157

По результатам экспериментов можно сделать следующие выводы.

1. Наименьшее время обработки стереопары достигается в режимах с применением простых контекстно-независимых целевых функций (SAD, SSD) совместно с методом локализации границ диспаритета (КАУС-1.1,-1.2). Среднее время обработки стереопары в таких режимах составляет около 300 миллисекунд.

2. Предложенный метод локализации границ диспаритета увеличивает как быстродействие програмной модели в 1,6 раза, так и точность стереосоответствий на величину от 0,1% до 1,14%. Кроме того, применение данного подхода позволяет применить контекстно-зависимую функцию без потери быстродействия (см. КАУС-1.3 иКАУС-2.1).

3. Наибольшая точность достигается в режиме КАУС-1.3. Это подтверждает большую точность контекстно-зависимой целевой функции Census по сравнению с контекстно-независимыми SAD и SSD. Среднее время обработки стереопары при этом возрастает на 66%, несмотря на применение оптимизаций битовыми векторами.

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

5. Точность установления стереосоответствий предложенного комплексного алгоритма (КАУС-1.1) сопоставима (набор-1) или выше (набор-2) по сравнению с наиболее точными существующими методами на основе функции SAD. Фактически совокупность всех предложенных оптимизаций доводит точность комплексного алгоритма на основе функции SAD до уровня существующих высокоточных алгоритмов, таких как SGM и GC с функциями Rank и Census. При этом

проиводительность программной модели составляет 2-4 кадра/сек. без применения специализированных вычислителей.

ЗАКЛЮЧЕНИЕ

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

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

Предложенный метод оптимизации вычисления контекстно-независимых целевых функций (SAD и SSD) с помощью интегральных массивов снижает вычислительную сложность основного шага установления стереосоответствий с 0(Nn-m-d„laJ до 0(Ndma). Метод позволяет использовать прямоугольные опорные окна любых размеров без увеличения вычислительной сложности основного шага совмещения стереопар. Метод локализации границ диспаритета позволяет еще больше снизить вычислительную сложность основного шага. При этом экспериментально подтверждено сопутствующее локализации границ диспаритетов повышение точности стереосоответствий.

Предложенный метод сегментации изображения и статистического уточнения стереосоответствий (МКСУ-1-МФ) снижает долю неверно-найденных соответствий в среднем в 1,5-2 раза при доказанной вычислительной сложности 0(N) его алгоритмической реализации. Кроме того, экспериментально подтверждена его большая эффективность в задаче совмещения стереопар в сравнении с существующим аналогичным методом, а именно SLIC-SP из работы Achanta R. и др.

Комплексный алгоритм поиска стереосоответствий сочетает в себе как низкую вычислительную сложность, так и высокую точность, не уступающую современным более трудоёмким алгоритмам типа GC или SGM.

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

Производительность программной модели алгоритма КАУС составляет несколько кадров в секунду (от 2 до 4). Это лучше, чем у программных моделей, представленных в аналогичных исследованиях при сопоставимом уровне точности. Но для некоторых задач может потребоваться более высокие точность

стереосоответствий и производительность модели. В таком случае применение специализированных вычислителей может быть целесообразным. В части применения видеоускорителей с интерфейсом CUDA есть ограничения, отмеченные во введении к данной диссертации. Альтернативой видеоускорителям могут служить платы расширения на основе программируемых логических интегральных схем (ПЛИС), как показано в работах Woodfill J. I., Tomasi M. и Ambrosch К. Устройства на базе ПЛИС-вычислителей могут сочетать в себе как высокую производительность, так и низкое энергопотребление. Это достигается за счет высокой степени адаптации алгоритма решения поставленной задачи под структуру вычислителя и наоборот. Основная сложность состоит в «переводе» существующих алгоритмов и методов в базис ПЛИС-архитектуры.

В разделе 4.4 диссертации приведено сравнение разрешения по глубине существующего контроллера Microsoft Kinect с ИК-дальномером и программной модели КАУС с различным уровнем погрешности значения диспаритета. Дальномер Kinect состоит из модуля ИК-подсветки сцены и ИК-сенсора, работающего при разрешении 640x480 с максимальной частотой 30 кадров в секунду. Рассмотренные в данном исследовании стереопары из набора-2 имеют сопоставимое разрешение изображений (695x555 пикселов), но при этом обеспечивают точность меньшую, чем Kinect если уровень погрешности с принять равным одному пикселу. В соответствии с формулой (1.5) точность определения удаленности объектов (разрешение по глубине) может быть улучшена за счет увеличения разрешения изображений, за счет увеличения стереобазы В и за счет уменьшения ошибки вычисления значений диспаритетов е.

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

Третий подход может быть реализован с помощью аппроксимации целевой функции для поиска дробных значений диспаритета. В существующих исследованиях для этого применяются параболические или кубические сплайны, например в работах Fisher R.B. et al. и Bailey D.G. Такое решение применимо, если функция сравнения опорных областей в рассматриваемой локальности представима полиномом 2-й или 3 й степени. В работе Shimizu М. и Okutomi М. для трех различных функций сравнения опорных областей выявлено, что применение пораболнческого сплайна при определенных условиях приводит к накоплению ошибки. В работе Haller I. и Nedevschi S. предложены две методологии разработки аппроксимирующих функций, учитывающих особенности функций. По результатам экспериментов точность идентификации пикселов возрастает до 5 раз по сравнению с существующими методами. Применяя аналогичный подход для алгоритма КАУС, теоретически можно повысить его разрешение по глубине до уровня контроллера Microsoft Kinect без увеличения разрешения изображений или величины стереобазы.

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

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

Публикации в изданиях, рекомендованных ВАК

1 Гузик В.Ф. Статистический метод оптимизации локальных алгоритмов установления пиксельных соответствий на стереопарах / В.Ф. Гузик, А.В.Чумаченко // Известия высших учебных заведений. Северо-Кавказский регион. Серия: Технические науки. 2011. — № 4. - С. 20-25.

2 Чумаченко A.B. Оптимизация вычисления SAD для задачи восстановления рельефа по изображениям стереопар в высокопроизводительных системах стереозрения / A.B. Чумаченко // Известия ЮФУ. Технические науки. 2013. — №3(140).-С. 89-96.

3 Гузик В.Ф. Метод оценки диспаритета стереопар / В.Ф.Гузик, А.В.Чумаченко // Известия ЮФУ. Технические науки, 2014. - №5 (154). - С. 229-234.

Публикации в других изданиях

4 Гузик В.Ф. Алгоритм поиска соответственных точек на стереопарах / В.Ф. Гузик, А.В.Чумаченко // Материалы VII Всероссийской научной конференции молодых ученых и аспирантов «Информационные технологии, системный анализ и управление». - Таганрог: Изд-во ТТИ ЮФУ, 2009 - С. 99-105.

5 Чумаченко A.B. Алгоритм многокритериальной сегментации изображений для решения задачи совмещения стереопар / А.В.Чумаченко // Материалы III Всероссийской научной конференции молодых ученых, аспирантов и студентов «Современные технологии, естествознание, педагогика». Том 1. -Элиста, 2014-С. 57-62.

В работах, написанных в соавторстве, личный вклад автора состоит в следующем: в [1] проведен анализ существующих алгоритмов установления пиксельных соответствий на стереопарах, сформулированы основные проблемы локальных алгоритмов и разработан метод их статистической оптимизации, реализована программная модель метода, проведены эксперименты; в [3] разработан метод оценки границ значений диспаритетов для всей стереопары в целом и принципы локализации оценок значений диспаритета в пределах выделенных фрагментов изображения; в [4] проведен анализ существующих подходов установления пиксельных соответственна стереопарах.

Соискатель iЧумаченко A.B.

Типогр. ИПК ЮФУ Заказ №£ЗОтир/0€>экз.