Software & Systems

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

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

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

Существующие подходы

Все известные алгоритмы бинокулярного стерео можно разбить на две большие группы – локальные и глобальные. В первую входят методы, использующие для вычисления диспаритета в каждой точке информацию лишь с части пикселей изображения, как правило, из окрестности данной точки. Простейший подобный алгоритм подразумевает сравнение квадратных окон по одной из метрик, например SAD (Sum of Absolute Diffe­rences – сумма абсолютных значений разностей яркости), и выбор в каждой точке диспаритета, для которого величина сравнения, называемая также стоимостью, минимальна. Более сложные алгоритмы, например [2] и [3], используют окна с адаптивными весами или адаптивной структурой. Большинство локальных методов отличаются высокой вычислительной эффективностью, однако качество их работы в среднем хуже, чем у глобальных алгоритмов. Некоторые алгоритмы сопоставимы с глобальными методами и по качеству, и по времени работы.

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

Приобретают популярность методы, пытающиеся совместить сильные стороны локальных и глобальных алгоритмов. Решение в каждом пикселе принимается независимо, однако влияние на него оказывают либо все остальные пиксели изображения, либо часть пикселей, не ограниченных локальной окрестностью данной точки. К числу подобных методов относятся алгоритмы, использующие общую идею поиска оптимального решения в каждом пикселе путем применения динамического программирования на дереве [6, 7]. К данной группе относится и подход [8], рассматриваемый в данной работе как базовый, поскольку от него отталкивается предлагаемый алгоритм.

Алгоритм [8] использует понятие минимального покрывающего дерева. Пусть G – некоторый граф с заданными на нем весами ребер. Минимальным покрывающим деревом для графа G называется такое дерево, которое включает в себя все вершины графа и сумма весов ребер которого минимальна. Для вычисления минимального покрывающего дерева известны эффективные алгоритмы, например [9]. Идея алгоритма [8] заключается в агрегации стоимостей присвоения пикселю того или иного диспаритета не по окну, как принято в локальных алгоритмах, а по дереву, покрывающему все изображение. Дерево является минимальным покрывающим деревом для графа изображения, то есть графа, в котором вершины соответствуют пикселям изображения и соединены ребрами по принципу четырехсвязности, а вес ребра равен абсолютному значению разности яркостей соединяемых им пикселей: wrs=½Ir–Is½. Расстояние Dpq между двумя произвольными пикселями p и q определяется как сумма весов вдоль кратчайшего пути между соответствующими вершинами дерева. Выражение для агрегированной стоимости присвоения диспаритета d пикселю p имеет вид , где Cq(d) – штраф за диспаритет d в точке q; s – параметр алгоритма, влияющий на гладкость решения. В качестве решения в каждом пикселе выбирается значение, дающее наименьшую агрегированную стоимость: .

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

Предложенный алгоритм

Рассмотрим алгоритм, основывающийся на вычислительно эффективном подходе базового метода, но лишенный указанного выше недостатка. Решение ищется не в пространстве диспаритетов, а в пространстве плоскостей. Набор плоскостей, присутствующих в сцене, вычисляется по контрольным точкам (ground control points, GCP) –разреженным точкам, для которых с высокой степенью уверенности известно правильное значение диспаритета. Контрольные точки используются также для регуляризации решения.

Представление решения в виде разметки плоскостями. Решение d в каждом пикселе p представим в виде плоскости f в пространстве {x, y, d}:. Такое представление уже встречалось ранее [10]. Пусть F – некоторый набор плоскостей, тогда выражение для агрегированной стоимости отнесения пикселя p к плоскости fÎF можно записать следующим образом:

Вычисление набора плоскостей. Одна из клю­чевых проблем, связанных с переходом из пространства диспаритетов в пространство плос- костей, – получение набора плоскостей F, из которых будет осуществляться выбор в каждом пикселе. Чтобы решение считалось качественным, этот набор должен быть не слишком большим и содержать все основные плоскости, присутствующие в сцене.

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

Множество контрольных точек GCP представляет собой облако трехмерных точек в пространстве {x, y, d}. Поэтому задачу вычисления набора плоскостей F можно сформулировать как задачу сегментации облака трехмерных точек на плоскости. Для этого в данной работе применяется жадный алгоритм, состоящий из следующих шагов.

1. Вычисление алгоритмом RANSAC [12] параметров плоскости, поддерживаемой наибольшим числом точек из GCP. Добавление плоскости в множество F.

2. Исключение поддерживающих плоскость точек из множества GCP.

3. Повторение шагов 1 и 2, пока существуют плоскости, поддерживаемые достаточным числом точек.

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

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

Для вычисления DGCP воспользуемся той же процедурой агрегации стоимостей по минимальному покрывающему дереву, на которой основан базовый алгоритм, но видоизменим функцию Cq(d) так, чтобы агрегированная стоимость в пикселе p имела вид

,

где

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

Имея регуляризирующее решение, полученное описанным выше способом, введем дополнительный штраф за отклонение итогового решения от карты диспаритета DGCP в пикселе p:

,

где h и g – параметры функции.

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

Итоговая стоимость присвоения плоскости f пикселю p в предлагаемом алгоритме примет вид

Здесь l – параметр, контролирующий степень влияния карты диспаритета DGCP на итоговое решение. В каждом пикселе выбирается плоскость, для которой стоимость Ep(f) минимальна.

Основные шаги предложенного алгоритма представлены на рисунке 2.

Экспериментальная оценка

Тестирование предложенного алгоритма проводилось на наборе данных KITTI (Karlsruhe Institute of Technology and Toyota Technological Institute) [13], содержащем 194 пары ректифицированных изображений и эталонные карты диспаритета, полученные путем лазерного сканирования. По сравнению с более популярным на сегодняшний день набором Middlebury [14] тестовый набор KITTI содержит более интересные и более сложные с точки зрения практических задач данные: изображения были получены не в лабораторных условиях, а съемкой с автомобиля при проезде по улицам города. При этом характер представленных в наборе сцен позволяет лучше продемонстрировать преимущества предложенного алгоритма.

Тестирование проходило при следующих значениях параметров алгоритма: s=0,1, h=0,005, g=2, l=40. В роли критерия качества использовался процент пикселей, для которых разница между найденным и эталонным значениями диспаритета превысила порог t при значении t=3. Контрольные точки были получены путем сопоставления ректифицированных изображений с использованием особых точек Харриса [15] и дескрипторов SIFT [16]. В таблице представлены средняя ошибка по всей базе, а также минимальная и максимальная ошибки по всем парам изображений для базового и предложенного алгоритмов.

Результаты сравнения алгоритмов

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

Дальнейшие исследования

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

Другим узким местом алгоритма является шаг вычисления набора плоскостей F. Неточная оценка параметров плоскостей, нахождение лишних или, наоборот, пропуск плоскостей, присутствующих в сцене, приведут к ошибкам в карте диспаритета. Одним из способов устранения данного недостатка может стать итерационное применение алгоритма с дополнительным этапом уточнения параметров плоскостей между итерациями подобно тому, как это делается в работе [10]. Использование алгоритмов геометрического разбора изображений, например [17], позволило бы получить более точный начальный набор плоскостей. Также возможно дополнение множества контрольных точек другими примитивами, например отрезками, для которых найдены надежные соответствия между двумя изображениями. Наконец, применение более сложных, чем описанный жадный алгоритм, методов сегментации плоскостей в облаке трехмерных точек, например на основе работы [18], тоже может дать улучшение результатов.

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

Литература

1.     Scharstein D., Szeliski R. A Taxonomy and Evaluation of Dense Two-Frame StereoCorrespondenceAlgorithms, Int. Journ. of Computer Vision, 2002, Vol. 47, no. 1–3, pp. 7–42.

2.     Hosni A., Bleyer M., Gelautz M., Rhemann C. Local stereo matching using geodesic support weights, Proc. of the 16th IEEE Int. Conf. on Image Processing (ICIP), 2009, pp. 2093–2096.

3.     Hirschmuller H., Innocent P., Garibaldi J. Real-time correlation-based stereo vision with reduced border errors, Int. Journ. of Computer Vision, 2002, Vol. 47, no. 1–3, pp. 229–246.

4.     Woodford O., Torr P., Reid I., Fitzgibbon A. Global Stereo Reconstruction under Second-Order Smoothness Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, Vol. 31, no. 12, pp. 2115–2128.

5.     Bleyer M., Rother C., Kohli P. Surface Stereo with Soft Segmentation, Proc. of IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2010, pp. 1570–1577.

6.     Hirschmuller H. Stereo processing by semi-global matching and mutual information, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, Vol. 30, no. 2, pp. 328–341.

7.     Bleyer M., Gelautz M. Simple But Effective Tree Structures for Dynamic Programming-Based Stereo Matching, Int. Conf. on Computer Vision Theory and Applications (VISAPP), 2008, Vol. 2, pp. 415–422.

8.     Yang Q. A Non-Local Cost Aggregation Method for Stereo Matching, Proc. of IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2012, pp. 1402–1409.

9.     Kruskal J. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proc. of the American Math. Society, 1956, Vol. 7, no. 1, pp. 48–50.

10.  Bleyer M., Rhemann C., Rother C. PatchMatch Stereo – Stereo Matching with Slanted Support Windows, Proc. of the British Machine Vision Conf. (BMVC), 2011, pp. 14.1–14.11.

11.  Wang L., Yang R. Global stereo matching leveraged by sparse ground control points, Proc. of IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2011, pp. 3033–3040.

12.  Fischler M., Bolles R. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Transactions of ACM – Graphics and Image Proc. 1981, Vol. 24, pp. 381–395.

13.  The KITTI Vision Benchmark Suite. URL: http://www. cvlibs.net/datasets/kitti/eval_stereo_flow.php?benchmark=stereo (дата обращения: 04.08.2012).

14.  The Middlebury Stereo Dataset. URL: http://vision.midd­lebury.edu/stereo/ (дата обращения: 04.08.2012).

15.  Harris C., Stephens M. A combined corner and edge detector, Proc. of the Fourth Alvey Vision Conf. 1988, pp. 147–151.

16.  Lowe D.G. Distinctive image features from scale-invariant keypoints, Int. Journ. of Computer Vision, 2004, Vol. 60, no. 2, pp. 91–110.

17.  Tretiak E., Barinova O., Kohli P., Lempitsky V. Geometric image parsing in man-made environments, Int. Journ. of Computer Vision, 2012, Vol. 97, no. 3, pp. 305–321.

18.  Delong A., Osokin A., Isack H., Boykov Y. Fast Approximate Energy Minimization with Label Costs, Int. Journ. of Computer Vision, 2012, Vol. 96, no. 1, pp. 1–27.