ДонНТУ   Портал магистров

Чигарёв Иван Александрович

Институт информатики и искусственного интеллекта

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

Специальность «Программное обеспечение систем»

Анализ и разработка алгоритма определения взаимного расположения объектов на изображениях

Научный руководитель: к.т.н., доц. Волченко Елена Владимировна

Резюме Биография Реферат Библиотека Ссылки Отчет о поиске Индивидуальный раздел

Реферат по теме: «Анализ и разработка алгоритма определения взаимного
расположения объектов на изображениях»

Содержание

• Введение
• 1. Актуальность темы
• 2. Цель и задачи исследования, планируемые результаты
• 3. Обзор исследований и разработок
• 4. Подходы к решению задачи совмещения стереоизображений
• 4.1 Исходные данные и результаты
• 4.2 Способы ректификации изображений
• 4.3 Алгоритмы построения карты диспарантности
• 5. Анализ алгоритма динамического программирования и выделения однородных областей
• Выводы
• Список источников

Введение

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

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

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

1. Актуальность темы

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

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

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

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

2. Цель и задачи исследования, планируемые результаты

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

Объектом исследования является процесс выявления соответствий на изображениях стереопары.

Предмет работы – существующие алгоритмы выявления соответствий на изображениях стереопары.

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

3. Обзор исследований и разработок

Исследования в данной области в Украине и странах СНГ слабо развиты, но данная тема хорошо раскрывается многочисленными публикациями зарубежных ученных.

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

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

Из локальных работ можно отметить работы Агаркова А.В. из Института проблем искусственного интеллекта [6,7], в которых предлагается метод представления изображений в виде графов и поиск соответствий изображений основанный на сравнении полученных графов.

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

Эффективный поиск соответствий на маленьких изображениях после уменьшения без сглаживания описан в [8]. В [9] рассмотрен быстрый корреляционный алгоритм. В [10,11] предлагается сопоставлять изображения по силуэтам, контурам. В работе [12] рассматривается улучшение корреляционного алгоритма работающего в режиме реального времени. Еще один корреляционный алгоритм с учетом информации о цвете [13]. Есть и другие не корреляционные алгоритмы, например, [14] основан на минимизации энергии глобальной функции с разрывами, в [15] используется метод разрезов на графах, в [16] для построения карты диспарантности учитываются однородности сегментов изображения.

Для нахождения ключевых точек часто используются алгоритмы SIFT [17], SURF [18]. Хорошим методом неточного сопоставления похожих последовательностей является динамическое программирование [19].

4. Подходы к решению задачи совмещения стереоизображений

4.1 Исходные данные и результаты

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

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

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

На рисунке 4.1 изображены два ректифицированных стереоизображения.

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

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

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

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

Такое графическое представление решения называется карта диспарантности (disparity map), карта глубин (depth map), карта сдвигов, карта несоответствий.

Карта диспарантности представлена на рисунке 4.3.

4.2 Способы ректификации изображений

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

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

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

Характерные (ключевые) точки могут находиться на углах объектов, на изгибах контуров, резких перепадах яркости, в центре однородных областей и т.д. Одними из популярных методов нахождения ключевых точек являются методы SIFT, SURF и детектор Харриса.

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

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

4.3 Алгоритмы построения карты диспарантности

На рисунке 4.4 представлена анимация ручного сопоставления двух строк изображения. Как видно из анимации, когда совпадают одни части изображения, другие не совпадают. Задача сопоставления заключается в сопоставлении всех участков изображения.

Основная масса работ по этой теме посвящена развитию методов, основанных на корреляционном подходе, и методов на основе минимизации энергии.

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

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

Для наглядного отображения результата такого сравнение, на рисунке 4.5 приведена матрица корреляций.

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

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

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

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

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

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

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

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

Алгоритм ДП прост в реализации и дает хорошие результаты. Рассмотрим алгоритм подробнее.
В качестве входных данных используется две горизонтальных строки левого и правого изображения. Пусть L(x,y), R(x,y) – яркость точки с координатами (x,y) для левого и правого изображения соответственно.

Исходными данными для ДП является матрица корреляций Dif[i,j], которая возвращает значение разности пикселя L(i,y) и пикселя R(j,y). О данной матрице говорилось ранее (Рис. 4.5). Обычно сравнение производится не по одному пикселю, а сразу несколько соседних, это уточняет результаты и уменьшает количество неоднозначных вариантов решения.

Следующим шагом является вычисление матрицы динамического программирования A[i,j]. В начале алгоритма A[0,0]=0. Вычисление производится для i=1..n, j=1..n, где n – ширина изображения. Элементы данной матрицы вычисляются следующим образом:

Minimum = Min( A[i-1,j], A[i,j-1], A[i-1,j-1] )

A[i,j] = Minimum + Dif[i,j].

Функция  Min(a,b,c) возвращает минимальное значение аргументов. Матрица разностей (корреляций) и матрица динамического программирования отображены на рисунке 5.1.

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

DisparityMapL [i,y] = j-i

DisparityMapR [j,y] = i-j

Up = A[i-1,j]

Left = A[i,j-1]

UpLeft = A[i-1,j-1]

Minimum = Min( Up,Left,UpLeft )

case Minimum of

UpLeft : i=i-1;j=j-1

Left : j=j-1

Up : i=i-1

end

В начале алгоритма i=n и j=n. В дальнейшем описанные выше шаги применяются до тех пор, пока i и j примут нулевые значения. (i,j) определяет положение в матрице ДП. DisparityMapR[x,y] и DisparityMapL[x,y] являются вычисленными картами диспарантности для правого и левого изображений соответственно (достаточно одной карты).

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

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

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

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

Примером таких однородных областей могут быть области, указанные на рисунке 5.3.

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

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

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

Выводы

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

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

На момент написания реферата магистерская работа еще не является завершенной. Готовый вариант работы может быть получен у автора или его руководителя после 20 декабря 2012 года.

Список источников

1. Гришин В. А Оценка точности установления соответствия // Доклады 10-ой Международной конференции и выставки "Цифровая обработка сигналов и ее применение", 26-28 марта 2008 года. Серия: Цифровая обработка сигналов и ее применение. Выпуск: Х-2. С. 428-431.
2. Юрин Д. В. , Крылов А. С. , Волегов Д. Б. , Насонов А . В. , Свешникова Н. В. Методы и алгоритмы совмещения изображений и их применение в задачах восстановления трехмерных сцен и панорам, анализе медицинских изображений, Москва, В МиК МГУ
3. Волегов Д.Б. , Юрин Д.В. Грубое совмещение изображений по найденным на них прямым линиям // Труды конференции Графикон 2006, Новосибирск., с . 463–466. http://www.graphicon.ru
4. Свешникова Н.В. Уточнение сеточной модели трехмерной сцены, предварительно восстановленной по малому количеству характеристических точек // Труды конференции Графикон 2007, Москва 2007, http://www.graphicon.ru
5. Свешникова Н.В. , Юрин Д.В. Алгоритмы факторизации: достоверность результата и применение для восстановления эпиполярной геометрии // Труды конференции Графикон 2006, Новосибирск., с. 158–165.
6. А.В. Агарков Построение карты диспаратности на основе сравнения графов, Институт проблем искусственного интеллекта, г. Донецк, Украина , 2006
7. А.В. Агарков Иерархическое представление изображения  с помощью графа, Институт проблем искусственного интеллекта, г. Донецк, Украина, 2003
8. Henkel R.D. Fast Stereovision by Coherence Detection / Ed. by G. Sommer, K. Daniilidis, J. Pauli // Proc. of the 7th International Conf. on Computer Analysis of Images and Patterns, CAIP'97 in Kiel, LNCS 1296, Springer. – Berlin. – 1997. – P. 297-304.
9. Stefano L.D., Marchionni M., Mattoccia S., Neri G. A Fast Area-Based Stereo Matcting Algorithm //  Proc. of 15th International Conf. on Vision Interface. – 2002. – P. 146-153.
10. Egnal G., Mintz M., Daniilidis K. Limiting the Search Rang of Correlation Stereo Using Silhouettes // Proc. of 15th International Conf. on Vision Interface. – 2002. – P. 170-177.
11. Boufama B., Jin K. Towards a Fast and Reliable Dense Matcing Algorithm // Proc. of 15th International Conf. on Vision Interface. – 2002. – P. 178-185.
12. Hirschmuller H. Improvements in Real-Time Correlation-Based Stereo Vision // CVPR 2001 Stereo Workshop / IJCV. – 2002.
13. Muhlmann K., Maier D., Hesser J., Manner R. Calculating Dense Disparity Maps from Color Stereo Images, an Efficient Implementation // CVPR 2001 Stereo Workshop / IJCV 2002.
14. Boykov Yu., Veksler O., Zabih R. A New Algorithm for Energy Minimization with Discontinuities // EMMCVPR. – 1999. – P. 205-220.
15. Kolmogorov V., Zabih R. Computing Visual Correspondence with Occlusions via Graph Cuts  // ICCV. – 2001. – P. 508-515.
16. Kawai Y., Ueshiba T., Ishiyama Y., Sumi Y., Tomita F. Stereo Correspondence Using Segment Connectivity // Proc. 14th International Conf. on Pattern Recognition, ICPR'98.  – Brisbane (Australia). – 1998. – P. 648-651.
17. Построение SIFT дескрипторов и задача сопоставления изображений [электронный ресурс]. – Режим доступа: http://habrahabr.ru/post/106302/
18. Обнаружение устойчивых признаков изображения: метод SURF [электронный ресурс]. – Режим доступа: http://habrahabr.ru/post/103107/
19. Динамическое программирование [электронный ресурс]. – Режим доступа: http://rain.ifmo.ru/cat/view.php/...
20. Чигарев И.А. Разработка алгоритма сопоставления стереоизображений и построения карты диспарантности // Современная информационная Украина: информатика, экономика, философия / Материалы VI Международной научно-практической конференции молодых ученых, аспирантов, студентов. - Донецк, ДонНТУ - 2012.