15 июля 2014
Машинное зрение в 3D: технологии, алгоритмы, возможности. Часть 2. Объёмное зрение: алгоритмы трёхмерной реконструкции сцены по нескольким 2D-снимкам
А.Ю. Соколов,
Начальник отдела перспективных разработок
компании Вокорд
Д.Н. Заварикин
Президент ГК Вокорд
1. Алгоритм SIFT
Существуют различные алгоритмы нахождения сопряженных точек на стереопарах. Одним из наиболее эффективных считается алгоритм SIFT (Scale Invariant Feature Transform) – алгоритм поиска характерных точек на двух или более изображениях, инвариантный к масштабу изображений и изменениям яркости. SIFT также достаточно устойчив к изменениям ракурса изображения. Этот алгоритм описан в литературе [1, 2, 3, 4].
Идея алгоритма SIFT заключается в нахождении особенных точек на каждом изображении, в последующем сравнении и парном отборе этих точек по некоторым характерным признакам. Для этого для каждого изображения вычисляются так называемые пирамиды сглаженных изображений на разных масштабах:
L(x, y, σ) = G(x, y, σ) * I(x, y)
Здесь I(x, y) – исходное двумерное изображение, G(x, y, σ) – сглаживающий гауссиан, L(x, y, σ) – результат свертки изображения с гауссианом.
В алгоритме вводится параметр степени размытия k. Для каждого разрешения исходного изображения параметр k варьируется, и строятся пирамиды c различным сглаживанием (см. Рис.4). После этого вычисляется разность гауссианов двух соседних слоев, которая обозначается через D.
D(x, y, σ) = (G(x, y, k σ) - G(x, y, σ)) * I(x, y) = L(x, y, k σ) - L(x, y, σ)
Такая процедура повторяется для изображения исходного разрешения, уменьшенного вдвое, вчетверо и т.д. Обычно параметр k выбирается таким, чтобы в пределах одной октавы по разрешению получалось 4-5 слоев гауссианов.
Рис.4. Построение разности гауссианов в SIFT
После построения пирамиды гауссианов и их разностей определяются такие особенные точки, которые являются экстремумами, как внутри каждого слоя, так и между слоями (см. Рис.5).
Рис.5. Поиск экстремума между слоями и внутри слоя. Экстремум помечен крестиком.
Для каждой особенной точки экстремума, найденной выше, в зависимости от параметра σ строится окружность, содержащая соседние точки изображения, и изучаются градиенты яркости в данных точках. Эти градиенты усредняются. Относительно среднего градиента вычисляются отклонения градиентов в окружающих точках, которые сводятся к некоторой упрощенной модели описания, называемой дескриптором (см. Рис.6).
В результате получается множество особенных точек на каждой паре изображений с набором своих дескрипторов. Эти точки сравниваются попарно на соседних изображениях, и если дескрипторы двух выбранных точек совпадают в переделах заданной точности, то две точки принимаются как сопряженные. Можно считать, что эти точки были получены как проекция одной и той же трехмерной точки на плоскости двух камер.
Рис.6. Описание точек экстремумов по направлению вектора градиента в соседних точках.
Различные эксперименты показывают, что SIFT хорошо находит сопряженные точки, дает малое количество ложных точек. Однако покрытие изображения сопряженными точками не является плотным [1]. Обычно для изображений лица разрешением порядка 400 х 600 пикселов в лучшем случае удается найти порядка 100-150 сопряженных точек. На Рис.7 приведен результат расчета SIFT в зависимости от чувствительности (порога) алгоритма. Эта особенность объясняется структурой самого алгоритма – среди всего множества точек выбираются лишь наиболее характерные точки-экстремумы на разных масштабах, которыми не могут быть все точки изображения одновременно.
Вывод, который можно сделать из анализа алгоритма SIFT, таков: с помощью данного алгоритма удается найти неплотное покрытие сопряженными точками, хотя и с высокой степенью достоверности их совпадения. Поэтому, как правило, SIFT используют в задачах компьютерного зрения для определения траекторий движения и сопряжения различных снимков, полученных под разным углом ракурса.
(а)
(b)
(с)
Рис.7. Сопряжение точек алгоритмом SIFT. (а) порог = 10, (b) порог = 3 (с) Порог = 1.5.
2. Анализ совпадающих текстур.
Для построения качественной трехмерной модели такого сложного объекта как лицо человека, количество точек, реконструированных на лице, должно быть велико. Это приводит к необходимости поиска алгоритма «плотного» построения сопряженных точек и «плотной» 3D-реконструкции.
Один их известных таких алгоритмов - это алгоритм, основанный на анализе совпадающих текстур на участках изображения, по-другому он называется алгоритм корреляций [5]. В алгоритме корреляций поиск сопряженных точек ведется некоторым окном заданного размера (от 3х3 до 19х19 точек) вдоль эпиполярных линий. Критерием совпадения является совпадение функции корреляции, посчитанной для заданного окна. Возможно использование разных функций корреляций, нормализованных либо ненормализованных на среднее значение яркости в двух сравниваемых окнах (см. Табл.1).
Табл.1. Различные виды функции корреляции для критерия совпадения
|
|
ненормализованная средне-квадратичная разность
|
|
|
метрика корреляции
|
|
|
нормализованная среднеквадратичная разность
|
|
|
нормализованная корреляция
|
В работе [5] показано, что С2-С4 дают близкие результаты, а С1- несколько худший результат (см. Рис.8).
|
Рис.8. Сравнение эффективности различных метрик сравнения для корреляции.
По оси y отложена вероятность правильного обнаружения сопряженных точек.
С2-С4 дают близкие результаты, С1- худший результат [5].
|
3. 3D-алгоритмы компании Вокорд.
Алгоритм 3D-реконструкции VOCORD отличается от алгоритма SIFT. Его особенностью является плотный поиск сопряженных точек и плотная трехмерная реконструкция.
Основные идеи алгоритма VOCORD:
а) Иерархический поиск сопряженных точек корреляционным методом на различных масштабах изображения, с уточнением реконструкции при переходе к более высокому разрешению;
б) Интеллектуальный анализ вероятности разброса сопряженных точек, соседних на изображениях проекций;
в) Эффективная фильтрация выбросов ложных точек и заполнение пробелов (дырок).
Алгоритм 3D-реконструкции VOCORD является оригинальной разработкой компании, защищенной патентами.
Литература.
[1] Lowe, David G. (1999). «Object recognition from local scale-invariant features». Proceedings of the International Conference on Computer Vision 2: 1150–1157.
[2] Lindeberg, Tony (1998). «Feature detection with automatic scale selection». International Journal of Computer Vision 30 (2): 79–116.
[3] Lowe, David G. (2004). «Distinctive Image Features from Scale-Invariant Keypoints». International Journal of Computer Vision 60 (2): 91–110.
[4] Mikolajczyk, K.; Schmid, C. (2005). «A performance evaluation of local descriptors». IEEE Transactions on Pattern Analysis and Machine Intelligence 27: 1615–1630.
[5] P. Fua. A parallel stereo algorithm that produces dense depth maps and preserves image features. Machine Vision Applications, 6(1), 1993.
