18 июля 2014
Машинное зрение в 3D: технологии, алгоритмы, возможности. Часть 3. 3D-реконструкция – погрешности и ограничения
А.Ю. Соколов,
Начальник отдела перспективных разработок
компании Вокорд
Д.Н. Заварикин
Президент ГК Вокорд
Теоретические и реальные погрешности и ограничения трёхмерной реконструкции
Для теоретической оценки точности 3D-реконструкции для простоты предположим, что две камеры с фокусным расстоянием f расположены на расстоянии D до объекта в одной плоскости и имеют стереобазу S (см. Рис.9).
|
Рис.9. Геометрическое построение для расчета теоретической оценки точности реконструкции.
На рисунке: внизу (x1 и x2) - плоскости матриц видеосенсоров, горизонтальная линия вверху - реконструируемый объект.
|
Имеем из геометрического построения (см. Рис.9): x1*D/f + x2*D/f=S
откуда:
D = S*f/(x1+x2) = S*f/X (4.1)
где: X=(x1+x2) (x1 и x2 имеют разные знаки в выбранной системе координат!)
Величина X называется диспаратностью изображения. Диспаратность показывает сдвиг одной сопряженной точки относительно другой в паре стереоснимков.
Поскольку сенсоры камер состоят из пикселов, диспаратность не может иметь произвольные значения – ее значения дискретные и определяются с точностью +/- (½) пиксела. Дифференцируя величину D по X, получим точность определения расстояния в глубину стереокамерами:
ΔD = S*f*ΔX/X2 = (1/2)*a*S*f/X2 = (1/2)*a*D2/(S*f) (4.2)
Здесь a – размер пиксела сенсора камеры.
Пример. Камера имеет видеосенсор размером H=7 мм по горизонтали и с числом пикселов в строке (по горизонтали) N=1280, f=16 мм, S=214 мм, D=1.3 м = 1300 мм. Определить теоретическую погрешность 3D-реконструкции.
ΔD = 0.5*(7/1280)*(1300^2)/(214*16) = 1.3 мм.
Данное рассмотрение показывает, что 3D-реконструкция не может использоваться на слишком больших расстояниях.
Если при увеличении расстояния отношение стереобазы к расстоянию не меняется (сохраняется тот же угол ракурса камеры), D/S=const, то погрешность 3D-реконструкции растет линейно с расстоянием между камерой и реконструируемым объектом.
Есть теоретически-предельное максимальное расстояние, определяемое размером пиксела, на котором диспаратность равна 1 пикселу, и 3D-реконструкция становится невозможной:
Dmax = S*f/a = S*f *H/N (4.3)
Рассчитаем максимальное расстояние для рассмотренного выше примера:
Dmax = S*f/a = S*f *H/N = 214 мм * 16 мм * 1280 / 7 мм > 600 метров
Также определим минимальный параллакс, соответствующий этому максимальному расстоянию:
Pmin = a/S = H/(N*S) > 26 миллирадиан.
Сравним это значение с минимальным угловым разрешением, определяемым дифракционным пределом для выбранного объектива:
Rmin = 1,22 * w / A > 30 милирадиан.
где: w = 550 нм – длина волны света, которую примем равной длине волны зелёного света;
A = 18 мм – максимальный диаметр входного отверстия объектива, ограниченный диаметром резьбы C/CS-mount.
Таким образом, максимальное теоретически-предельное расстояние 3D-реконструкции превышает теоретически предельное расстояние, ограниченное дифракционным пределом.
Оценим минимальное теоретическое расстояние 3D-реконструкции. Очевидно, оно определяется максимальной диспаратностью, которая ограничена размером выбранного видеосенсора:
Dmin = S*f/Xmax = S*f/H = S*f/(N*a) (4.4)
Для выбранного нами примера оптической системы минимальное расстояние равно Dmin < 0,5 метров, что меньше, чем минимальное расстояние до объекта (M.O.D.), записанное в паспорте выбранного объектива, равное 0.6 метра:
Dmin = 214 мм * 16 мм / 7 мм = 489 мм < 0,5 метра .
3D-реконструкция с субпиксельной точностью
Вообще говоря, формулу (4.1) следует написать в более общей форме:
ΔD = ΔХ * D2/(S*f) (5.1)
где: ΔХ – погрешность, с которой измеряется диспаратность и которая, кстати говоря, необязательно равна линейному размеру пиксела.
Бытует наивная точка зрения, что информация на масштабах, меньших, чем размер пиксела, теряется. Однако в действительности можно измерить с заранее вычисленной погрешностью геометрические величины с точностью, превышающей размер пиксела. Интуитивно понятные и очевидные основы подходов, позволяющих получать субпиксельную точность, следующие:
1) Модели ожидаемых пространственных форм сигнала от известных структур. (Например, резкие кромки или линии дают характерные формы сигналов, аппроксимируя которые, можно с высокой точностью измерить геометрические параметры этих структур).
2) Пространственная интеграция во время процедуры дискретизации. Видеосенсоры обычно интегрируют непрерывный сигнал в каком-то чётко ограниченном интервале (времени или пространства), что даёт возможность провести измерения некоторых величин, значения которых зависят от их относительного положения внутри интервала интегрирования.
3) Форма сигнала, получаемая от точечного объекта (функция рассеяния точки - ФРТ). Знание этой функции может быть использовано, например, для восстановления смазанного изображения.
Точность субпиксельного измерения зависит от множества факторов, таких как ФРТ, модель и уровень шума, спектр пространственных частот изображения. Часто употребляется правило, что максимально достижимая точность составляет 0.1 пиксела. Но можно достигнуть и более точных измерений, например, точность 0,02 пиксела показана в измерении местоположении полосы в [6].
Существуют 4 общих метода измерений с субпиксельной точностью:
1) Интерполяция. Для примера формула линейной интерполяции
2) Интеграция. Простейший пример интеграции – нахождение координат точки, изображение которой размыто ФРТ, – это просто «центр масс» яркостей некоторой области изображения:
3) Аппроксимация последовательными приближениями. Простой пример: определение местоположения характерного элемента с помощью метода SIFT (Scale invariant Feature Transform) [3]. D(x+δ) – гауссиан, аппроксимированный рядом Тейлора по двум пространственным координатам.
Координаты расположения элемента с субпиксельной точностью:
4) Фазовая корреляция. Ключевая идея метода фазовой корреляции – это предположение, что пространственно-частотные взаимосвязи между пикселами во всём выбранном окне более чёткие, чем данные об отдельных пикселах. F- функция преобразования Фурье.
Максимум функции T определяет координаты наилучшей аппроксимации с субпиксельной точностью.
Одним из методов, используемым компанией Вокорд для достижения субпиксельной точности 3D-реконструкции – передискретизация изображения с шагом 1/4. В качестве алгоритма субпиксельной передискретизации изображений реализован один из наиболее качественных алгоритмов для компенсации движения между кадрами в стандарте цифрового кодирования H.264. В этом стандарте передискретизация до 1/2 пиксела выполняется с использованием фильтра (1, -5, 20, 20, -5, 1) по шести соседним точкам, а последующая передискретизация до 1/4 пиксела выполняется коротким фильтром с использованием промежуточных значений в точках 1/2 пиксела (см. Рис.10, Рис.11).
Рис.10. Маска фильтра передискретизации до 1/4 пиксела согласно стандарту H.264.
Рис.11. Формулы передискретизации до 1/4 пиксела согласно стандарту H.264.
Для задачи вычисления диспаратностей с субпиксельной точностью в [7] была доказана теорема, что теоретически-предельная достижимая точность субпиксельной аппроксимации равна 1/20 пиксела.
Литература.
[6] Alexander, B. F., Ng, K. C. (1991). Elimination of systematic error in subpixel accuracy centroid estimation. Optical Engineering 30(9):1320-1331.
[7] N. Sabater , J.-M. Morel , A. Almansa, How Accurate Can Block Matches Be in Stereo Vision?, SIAM Journal on Imaging Sciences, v.4 n.1, p.472-500, February 2011 [doi>;10.1137/100797849]
