Авторы: Sven FORSTMANN, Yutaka KANOU,JunOHYA, Sven THUERING, Alfred SCHMITT
Перевод: Чигарёв И. А.
Источник (оригинал): http://www.gpstraces.com/sven/main/publications/stereo.prmu.pdf
В данной работе прадлагается алгоритм стереосопоставления изображений основанный на динамическом программировании, работает в режиме реального времени, достигает высокого качества сопоставления. Использование расчетов от грубого до качественного, а так же использование команд MMX позволили увеличить производительность алгоритма. Вертикальное сглаживание и объединение данных динамического программирования позволило избавится от горизонтальных штрихов, что повысило качество результатов. Текущая реализация работает около 30 кадров в секунду на персональном компьютере с частотой процессора 2 ГГц, чего вполне достаточно для использования в приложениях реального времени.
Ключевые слова: стерео, реальном времени, 3D-реконструкция.
Трехмерная реконструкция на основе стереоизображений имеет большую историю и является одной из главных областей исследований на протяжении 20 лет. Обычно, данная технология используется в машинном зрении, как в этой и в [12] статье, для построения карт высот участков земли по снимкам со спутников, трехмерной реконструкции [8,9] или помощь при вождении автомобилей. В данной работе предлагается новый алгоритм, достигающий в режиме реального времени высокого качества стерео соответствия.
Наиболее распространенным методом сопоставления изображений является корреляционный метод. Благодаря своей надежности данный метод имеет даже аппаратную реализацию [2,3]. Так же часто используется в программах реального времени, как в [5,6] и т.д. Одним из самых известных исследовательских проектов является проект трехмерной реконструкции в Канаде [8,9], использующий 51 откалиброванную камеру. Предлагаемый метод имеет так же приемущество в том, что производится сопоставление изображений даже с небольшим вертикальным сдвигом. Данный метод относительно надежен и обеспечивает хорошие результаты в случае текстурированных изображений. Единственным недостатком является локальные погрешности, но не глобальные. Характероной чертой результирующих изображений является то, что они выглядят немного размытыми.
Динамическое программирование (ДП) часто используется для расчета карты диспарантности (соответствия, сдвигов, глубин). Метод, описанный в [1] может справляется как с вертикальными, так и с горизонтальными сдвигами, но в нем ДП было применено три раза, что замедлило вычисления в отличие от предлагаемого алгоритма. Первые два вычисления были произведены для нахождения вертикальных соответствий, которые затем используются улучшения последнего результирующего ДП. Реализаций подобных алгоритмов в режиме реального времени всего несколько, один из них [10]. Преимущество этого метода в том, что вычисления производятся быстро и за однинаковые промежутки времени, что делает его подходящим для приложений реального времени. Еще одно приемущество в том, что каждая линия будет глобально оптимальной, так же хорошо обрабатываются незначительные участки без текстур. Недостатками являются горизонтальные штрихи на карте соответствий. Это происходит потому, что, как правило, все линии расчитываются независимо друг от друга. Таким образом, если камеры плохо откалиброваны, то будет увеличиватся количество ошибок вычислений.
Проблема стерео-соответствия также моделируется как задача максимального потока в графе. В настоящее время это самый известный способ. Одна из наиболее эффективных реализаций [7], в настоящее время на первом месте в опросе Scharstein и Szeliski [4]. Кроме того, это самый сложный и самый медленный из рассмотренных. Даже самая быстрая реализация, по крайней мере в 20 раз медленнее, чем выше описанные методы. По этой причине данным метод не подходит для приложений реального времени.
Далее представлен алгоритм расширенного ДП, оптимизированный по скорости для достижения производительности реального времени, но при этом модификация нарпавлена на улучшение качества. ДП было выбрано потому, что является простым в реализации методом и хорошо подходит для использования в реальном времени.
ДП является алгоритмом, который производит поиск наилучшего соответствия между двумя последовательностями данных (в данном случае - двумя линиями изображений). Для исходных последовательностей, элементов матрицы А ДП для линии y расчитывается следующим образом:
Minimum = Min( A[i-1,j], A[i,j-1], A[i-1,j-1] )
ColorL = LeftImage[i,y]
ColorR = RightImage[j,y]
A[i,j] = Minimum + Dif(ColorR,ColorL)
После выполнения данного шага можно искать путь с минимальной величиной начиная в матрице ДП с элемента А[n,n] и заканчивая А[0,0]. Вертикальные и горизонтальные отклонения в матрице ДП от диагональных элементов указывают на искомый сдвиг между точками левого и правого изображений. При прохождении указанного пути выбирается всегда соседний элемент с наименьшим значением в A[i,j], в случае одинаковых значений выбирается диагональное направление. Ниже представлен псевдокод, отображающий описанные действия.
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) определяет положение в матрице ДП.
Так как классический алгоритм ДП не может оптимизировать вертикальные линии, вызывающие типичные для данного алгоритма штрихи, первые оптимизации направлены на повышение качества результата. Были сделаны следующие улучшения:
Повторное использование вычисленных путей
Данная оптимизация использует отдельную матрицу, которая содержит взвешенные пути предыдущей y-линии. Значения данной отдельной матрицы вычитается из текущей матрицы до того, как будет производится поиск по матрице. Отдельная матрица не стирается на каждом этапе, а постепенно обнуляется. Данное действие производит сглаживание вертикальных линий и помогает избавляться от горизонтальных штрихов.
Сглаживание значений карты соответствий
Следующая оптимизация применяемая для сглаживания вертикальных линий заключается в объединении расчитанных цветовых разностей между линией y и y+1. Веса для сглаживания выбираются в зависимости от разницы в цвете между двумя вертикальными линиями. Если разница невелика, то слаживание сильное, если разница большая, то сглаживание слабое. В настоящее время используется три различных уровня. Использование различных уровней сглаживаня повышает качество в плохо тектурированных (однородных) областях и сохраняет резкость углов. Если скорость работы не важна, то лучшим решением будет применение сглаживающей функции в зависимости от величины цветовой разности.
Следующим шагом повышения качества соответствия изображений является сибпиксельная точность. Данный шаг в предлагаемом методе не применяется в реальном времени, потому что он слишком медленный, но при этом является хорошим и простым решением повышения качества результатов. Добиться этого можно простым увеличением исходного изображения в x раз с применением сглаживания. Результирующая карта соответствий также будет иметь размер увеличенный в x раз. Данный эффект будет заметен только при увеличении ихображения по горизонтали, увеличение по вертикали не дает улучшения качества.
В данном случае ДП было применено дважды. В первом проходе происходит поиск соответствий горизонтальных линий слева направо, а затем справа налево. Такой пождод позволят более точно находить точки без соответствий. Второй проход не используется в предлагаемом методе, так как он расчитан на максимальную производительность. Данный шаг является полезным в случае важности качества в ущерб скорости.
Довольно часто изображения, полученные с фотоаппарата, имеют небольшой шум. Для уменьшения этого шума можно применить любой из методов фильтрации шума, но можно также "взвесить" яркостную разницу. Это делается в предлагаемом алгоритме с помощью применения веса к вычисленной яркостной разнице точек изображения. Данный подход является быстрым и не приводит к потере качества. Оптимальный выбор весов зависит от изображений.
Другим параметром, зависящим от изображения, является применение весов к направлению поиска решения. Это может быть легко осуществлено путем применения трех весов для трех возможных направлений во время обратного прохода по матрице ДП.
Следующая оптимизация направлена на скорость, так как алгоритм расчитан на работу в режиме реального времени.
Первая примененная оптимизация заключается в уменьшении матрицы ДП, остается только та часть, в которой должно находится решение. Величина, на которую может быть уменьшена матрица по не главной диагонали, равна числу n, где n - максимально допустимое несоответствие изображений. Прирост производительности в данном случае равен величине результата деления ширины изображения на выбранное число n. Рекомендуется уменьшить все используемые части матрицы до минимально возможного, это позволит сократить потребление памяти и улучшить работу кеша процессора.
В рассматриваемом алгоритме предлагается осуществить поиск решения от грубого к точному с помощью пропуска линий. В начале алгоритм рассматривает каждые n-ые горизонтальные линии для вычисления границ возможных несоответствий изображений. После этого производится уменьшение матрицы ДП до найденной максимальной величины.
Благодаря такой оптимизации, пропуска 8 линий и использование 16 уровней разности, скорость может быть удвоена. Идея использования половины ширины изображения принесла большее ускорение, но была отброшена, так как в последствии терялось много деталей, точность. Описанная предобработка так же улучшает качество результата.
Главные части алгоритма были написаны на языке Assembler, так же были использованы расширенные команды мультимедиа MMX, доступных на любом современном компьютере. При использовании данных команд, зазность между 6 значениями можно вычислить всего с помощью 4-х команд. Следует сказать, что достичь значительного прироста производительности для данной части, так как компилятор сам довольно хорошо оптимизирует код. Описанная реализация позволяет получить прирост производительности на 30%.
MMX команды, использовавшиеся для вычисления разности между 6-тью точками:
movq mm0,[right] ;rgbrgb правого изображения
movq mm1,[left] ;rgbrgb левого изображения
movq mm2,mm0 ;копия mm0
psubusb mm0,mm1 ;вычитание 1
psubusb mm1,mm2 ;вычитание 2
por mm0,mm1 ;объединение результатов
movq [abs],mm0 ;сохранение результатов
Так же не стоит забывать об оптимизациях компилятора GCC. Применяя опцию умеренной оптимизации O2 удалось повысить производительность вдвое. Так же желательно поставить выравнивание данных по 16, 32 байт и т.д.
Для расчета качества вычислений используются целевые снимки (groundtruth), то есть то, что должно получится в идеальном случае [15]. Точность полученных карт соответствий могут быть измерены, оценивая разницу между целевым изображением. Если разность больше некоторого порога, то точка считается неправильной. При увеличении данного порога до 2 и более, как в [4,15], иногда более плохие по качеству изображения получали больший рейтинг. Рассмотренный алгоритм расчитан на сцены реального мира. Тестовые снимки, такие как Tsukuba, показывали хорошие результаты, в то время как некоторые искусственные сцены, а также из набора Middlebury, имели больше ошибок. Результаты с фиксированными параметрами алгоритма приведены в таблице 1.
| Изображение | SSD | DP | RT | GC |
|---|---|---|---|---|
| Tsukuba | 5.23 | 4.12 | 2.82 | 1.94 |
| Sawtooth | 2.21 | 4.84 | 6.60 | 1.30 |
| Venus | 3.74 | 10.10 | 5.09 | 1.79 |
| Map | 0.66 | 3.33 | 6.65 | 0.31 |
Таблица 1 – Сравнение количества ошибок различных алгоритмов (предложенный RT)
Максимально достигнутая скорость со всеми оптимизациями составила 36 кадров в секунду. Этого вполне достаточно, учитывая тот факт, что большинство современных камер снимают видео со скоростью 30 кадров в секунду. Для осуществления обработки стерео-сопоставления в режиме реального времени достаточно одного обычного компьютера.
Исходные данные камеры подвергались обработке, а именно коррекция искажений камеры, размытие изображения для удаления шума. После построения карты соответствий, возможно было даже строить текстурированную трехмерную модель наблюдаемой сцены. Количество кадров в секунду изменялось от 11 до 30 в зависимости от входных параметров стерео-сопоставления и разрешения изображений. Конфигурация, которая хорошо работает в большинстве случаев, было разрешение 256х256 для изображения и 32 для вычисления разностей. В данном случае скорость достигала 20 кадров в секунду. Примеры сопоставления приведены на рисунке 1.
Рисунок 1 – Результаты сопоставления реальных сцен
Предложенный алгоритм является одним из разновидностей динамического программирования, специализированный для работы в режиме реального времени, так как корреляционный алгоритм чаще всего используется в подобных целях [2,3,5,6,8,9]. Достигнутые результаты показывают хорошие результаты вычисления карты соответствия для реальных сцен, а так же высокое быстродействие, что очень важно для применения в устройствах реального времени. Достигнутой скорости достаточно для вычисления соответствий, фильтрации и отображения двух видео потоков на обычном компьютере в реальном времени, возможна даже генерация текстурированной трехмерной модели наблюдаемой сцены. Максимальная производительность для изображения Tsukuba 36 кадров в секунду, и 15-20 кадров при использовании динамически настраеваемых параметров и проведения фильтрации изображения. Горизонтальные штрихи, характерные для ДП, не были удалены полностью, но их количество значительно уменьшилось по сравнению с классическим вариантом алгоритма.
В будущем можно повысить качество сопоставления учитывая ранее полученную карту соответствий, изменение данных во времени. В данном случае так же можно получить более точные данные о размере максимального несоответствия. Алгоритм может в дальнейшем использоваться для трехмерной реконструкции объектов, может быть полезен и для интеграции объекта в сцену. Для следующего поколения компьютеров может использоваться внутри-корреляционный метод [1] или предварительные корреляции [11], что позволит улучшить качество. В предложенном алгоритме происходит сглаживание горизонтальное и вертикальное только в одном направлении, проход во всех направлениях позволит улучшить качество. Другим улучшением является интеграция автоматического конфигуратора параметров. Часто каждая сцена имеет свои оптимальные параметры, в случае с видео потоком оптимальные параметры значительно изменяются.
1. Yuichi Ohta, Takeo Kanade Stereo by Intra- and Inter-
Scanline Search Using Dynamic Programming IEEE Trans-
actions on Pattern Analysis and Machine Intelligence,1985
2. Takeo Kanade,Hiroshi Kano,Shigeru Kimura,Atsushi
Yoshida,Kazuo Oda Development of a Video-Rate Stereo
Machine Proc. of International Robotics and Systems Con-
ference (IROS ’95), Human Robot Interaction and Cooper-
ative Robots, Vol. 3, August, 1995, pp. 95 - 100.
3. John Woodfill,Briam Von Herzen Real-Time Stereo Vi-
sion on the PARTS Recon?gurable Computer Originally
published in IEEE Symposium on FPGAs for Custom Com-
puting Machines, IEEE Symposium on FPGAs for Custom
Computing Machines,1997
4. Daniel Scharstein,Richard Szeliki A Taxonomy and
Evaluation of Dense Two-Frame Stereo Correspondence In
Proceedings of the IEEE Workshop on Stereo and Multi-
Baseline Vision, Kauai, HI, Dec. 2001
5. Ruigang Yang and Marc Pollefeys Multi-Resolution
Real-Time Stereo on Commodity Graphics Hardware Multi-
Resolution Real-Time Stereo on Commodity Graphics
Hardware, page 211-217, CVPR 2003
6. Ruigang Yang and Marc Pollefeys Real-time Correla-
tion Based Stereo Vision CVPR 2001 Stereo Workshop /
IJCV 2002
7. Michael H. Lin, Carlo Tomasi Surfaces with Occlusions
from Layered Stereo Stanford University, 2002.,CVPR
2003
8. Masatoshi, Takeo Kanade A Multiple Baseline Stereo
IEEE Transactions on Pattern Analysis and Machine In-
telligence 1993
9. P.J. Narayanan, Peter W. Rander, Takeo Kanade
Constructing Virtual Worlds Using Dense Stereo Proc.
ICCV, pp. 3-10, 1998.
10. Yi Lu Murphey, Jie Chen, Jacob Crossman, Janxin
Zhang, Paul Richardson, Larry Sieh Depth?nder, A
Real-time Depth Detection System for Aided Driving
Depth?nder, A Real-time Depth Detection System for Aided
Driving IVS 2000
11. A.F. Bobick and S.S. Intille Large occlusion stereo In
Vismod, 1999
12. Steven B. Goldberg, Mark W.Maimone, Larry
Matthies Stereo Vision and Rover Navigation Soft-
ware for Planetary Exploration IEEE Conference Proceed-
ings,March 2002,Big Sky,Montana,USA
13. Vladimir Kolmogorov and Ramin Zabih Computing Vi-
sual Correspondence with Occlusions using Graph Cuts
In International Conference on Computer Vision (ICCV),
July 2001
14. Intel Corporation Intel Architecture Optimization Man-
ual Chapter 4.6.7,page 78
15. Daniel Scharstein, Richard Szeliski Middlebury Stereo
Vision Research Page http://cat.middlebury.edu/stereo/