22 июля 2014

Машинное зрение в 3D: технологии, алгоритмы, возможности. Часть 4. Математическая модель камеры и алгоритм 3D-реконструкции

А.Ю. Соколов,
Начальник отдела перспективных разработок
компании Вокорд

Д.Н. Заварикин
Президент ГК Вокорд

Трёхмерное зрение – это восстановление в трёхмерном пространстве координат всех точек сцены наблюдения по группе 2D-снимков.

2D-снимок – это цифровое изображение, которое является перспективной проекцией трёхмерной области пространства (сцены наблюдения) на плоскость видеосенсора.

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

Рис. 12. Устройство камеры

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

Следует отметить, что для выполнения указанной процедуры все камеры должны быть откалиброваны. Что такое калибровка камеры? Рассмотрим этот вопрос более подробно.

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

Изображение, формируемое объективом, образуется согласно модели перспективной проекции. По модели считается, что все лучи света проходят через одну точку - фокус, расположенную на заданном расстоянии F от плоскости изображения (Рис 13). Проекцией трехмерной точки А с координатами X,Y,Z на сенсор является точка а с координатами x,y.

(a)

(б)

(в)

Рис 13. Модель перспективной проекции. Координаты в плоскости камеры выражаются через трехмерные координаты как x=X/Z, y=Y/Z

Поскольку координаты, в которых вычисляются все элементы сцены, могут быть заданы относительно произвольной трехмерной системы координат, то для пересчета к системе координат камеры выполняется преобразование координат на вектор трансляции и поворот на заданные углы (см. Рис. 14).

Рис. 14 Пересчет от системы координат сцены к координатам камеры. R – матрица поворота, T – вектор трансляции. С – матрица пересчета

Можно показать, что с учетом указанных преобразований, трансляции координат на заданный вектор и поворота уравнения перспективной проекции записываются в однородных координатах (X,Y,Z) сцены и координат (u,v) в плоскости сенсора камеры в матричном виде с использованием матрицы проекции P размером (3 х 4):

(6.1)

Данный вид уравнений называется однородным. Запись 1 в последней строке (6.1) означает, что при вычислении u и v в левой части результат нужно поделить на последнюю третью строку (в которой после деления, очевидно, получится 1). Важно запомнить: матрица проекции имеет размер 3х4 и позволяет однозначно по 3D-координатам (X,Y,Z) вычислить проекции точки на сенсор камеры (u,v).

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

Согласно своему построению, матрицу P можно разбить на произведение матриц с параметрами внешней калибровки С=(R,T) и матрицу К с параметрами внутренней калибровки. Задачей калибровки является, в общем случае, определение коэффициентов матрицы P (общая калибровка камеры) и выделение в них значений фокусного расстояния (внутренняя калибровка), плюс матрицы поворота R, вектора трансляции T (внешняя калибровка). Это можно записать в следующем виде:

Как же вычисляется матрица проекции и находятся внутренние параметры камеры? Оказывается, эта задача давно решена, и в литературе описана масса различных методов ее решения! Большее распространение получил алгоритм Tsai [13, 14], который одновременно с калибровкой позволяет дополнительно учесть нелинейные параметры дисторсии объектива камеры. (Для простоты в данной статье мы не будем подробно затрагивать тему дисторсии).

Для выполнения калибровки методом Tsai в поле зрения камеры под некоторым углом устанавливают тестовый шаблон, координаты контрольных пикселов которого хорошо известны в заданной системе координат (например, в системе координат, привязанной к самому шаблону). Калибровочным шаблоном может служить чередующиеся белые и черные квадраты заданного размера, уголки которых образуют набор точек (см. Рис 15).

Рис. 15 «Шахматный» калибровочный шаблон в поле зрения камеры

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

Есть два основных подхода к решению задачи триангуляции.

1. Первый подход.

Задача решается по проекциям на 2-х или более 2D-снимков с помощью системы уравнений. Рассмотрим эту процедуру более подробно.

Для простоты рассмотрим случай только двух камер (при большем числе камер задача обобщается). Обозначим через P матрицу проекции первой камеры, через Q – матрицу проекции второй камеры, а через u1, v1 – координаты точки проекции на сенсор в первой камеры, через u2,v2 – координаты точки проекции на сенсор второй камеры. Из уравнений проекции (6.1) имеем (помним, что результат нужно поделить на последнюю строку):

u1=(P11*X+P12*Y+P13*Z+P14)/ (P31*X+P32*Y+P33*Z+P34)

v1=(P21*X+P22*Y+P23*Z+P24)/ (P31*X+P32*Y+P33*Z+P34)

u2=(Q11*X+Q12*Y+Q13*Z+Q14)/ (Q31*X+Q32*Y+Q33*Z+Q34)

v2=(Q21*X+Q22*Y+Q23*Z+Q24)/ (Q31*X+Q32*Y+Q33*Z+Q34)

Эти уравнения удобно переписать иначе. Для первой камеры:

(P11-u1*P31)*X+(P12-u1*P32)*Y + (P13-u1*P33)*Z =(u1*P34-P14)

(P21-v1*P31)*X+(P22-v1*P32)*Y + (P23-v1*P33)*Z =(v1*P34-P24) (6.2)

Для второй камеры:

(Q11-u2*Q31)*X+(Q12-u2*Q32)*Y + (Q13-u2*Q33)*Z =(u2*Q34-Q14)

(Q21-v2*Q31)*X+(Q22-v2*Q32)*Y + (Q23-v2*Q33)*Z =(v2*Q34-Q24) (6.3)

Имеются 4 уравнения для 3-х неизвестных X,Y,Z. Казалось бы, система уравнений переопределена и в общем случае может не иметь решений. На самом деле, это не так.

Если посмотреть на каждое уравнение относительно неизвестных X,Y,Z, то легко убедиться, что оно имеет вид

A*X + B*Y + C* Z =D

Из аналитической геометрии известно, что данное уравнение описывает плоскость с нормалью в направлении вектора n=(A,B,C)^T.

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

Поэтому решением системы двух уравнений для одной камеры является некоторая прямая (луч). Физический смысл этого решения – множество точек, проходящих через точку проекции u,v на плоскости сенсора и точку фокуса камеры.

Для двух камер (уравнений 4-х «плоскостей») решением является точка пересечения двух лучей. Эта точка по смыслу является исходной 3D-точкой (см. рис 3 раздел 2). Поэтому если матрицы проекции были определены правильно, а точки проекции вычислены без ошибок, система уравнений должно иметь одно решение в точке пересечения этих лучей.

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

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

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

Рис.16. Определение 3D точки в случае наличия погрешностей триангуляции

Для решения задачи аналитически с переопределенным числом линейных уравнений в математике давно разработан алгоритм решения с использованием псевдо-обратной матрицы. Запишем 4 уравнения для вектора X={X,Y,Z}^T в виде

W*X=D

Здесь W – матрица из 3 столбцов и 4 строк, в которую входят коэффициенты матрицы калибровки двух камер и координаты точек проекции, а вектор D – правая часть уравнения 6.2-6.3. Именно такой вид имеют уравнения (6.2-6.3) для X,Y,Z.

Это матричное уравнение решается следующим образом: домножаем слева на транспонированную матрицу W^T

(W^T W)*X = W^T D

Матрица W^T W имеет размер 3х3, более того, имеет обратную матрицу. В данной записи уравнений ровно столько, сколько и неизвестных. Решение, очевидно, есть:

X = (W^TW)^-1 W^T D

Можно показать, что решение, найденное таким образом, дает наименьшую среднеквадратичную невязку в правой части исходных уравнений 6.2-6.3 (метод наименьших квадратов). Интересующимся предоставим возможность самим проверить это.

Обратите внимание, что таким образом можно было бы решить систему уравнений для любого количества камер! В этом случае число строк в матрице W равнялось бы удвоенному числу камер, а псевдо-обратная матрица (W^T W)^-1 существовала и имела бы размер 3х3. Кроме того, чем больше задано уравнений (т.е. чем больше камер), тем, очевидно, меньше статистическая погрешность вычисления искомых координат трехмерной точки.

2. Второй подход применяется для стереосистем. В данном случае находятся геометрические взаимосвязи между видеосенсорами стереопары [8] и рассматривается эпиполярная геометрия 3D-пространства, наблюдаемого стереопарой [9]. В этом случае можно упростить поиск сопряженных точек на соседних кадрах.

Математическая модель видеокамеры снова рассматривается в качестве «проективной камеры» (projective camera, pinhole camera). Рассмотрим математическую модель проекции в эпиполярной геометрии:

Рис.17. Эпиполярная геометрия для двух камер

Здесь:

Стереобаза – линия OO’, соединяющая центры камер;

Эпиполи – точки e и e’ пересечения стереобазы с плоскостями изображений

Эпиполярная плоскость – плоскость, образованная векторами OP и OP’

Эпиполярная линия – линия l, лежащая в плоскости изображений и соединяющая эпилоли e и протекцию точи P на плоскость изображений p .

Точка пространства P проецируется в p на плоскость изображения левой камеры, а также в p' на плоскость изображения Pp'. Этот луч проецируется на плоскость второй камеры в прямую l', называемую эпиполярной линией. Образ точки P на плоскости изображения второй камеры обязательно лежит на эпиполярной линии l'.

Важное заключение состоит в том, что каждой точке p на изображении левой камеры соответствует единственная эпиполярная линия l' на изображении правой камеры. Аналогично, каждой точке p' на правом изображении соответствует эпиполярная линия l на левом.

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

Основанная теорема эпиполярной геометрии утверждает:

Существует такая матрица F размера 3 × 3, что пара точек p, p' является стереопарой тогда и только тогда, когда:

(6.2)

Как показала практика, для большего удобства следует немного «довернуть» изображения двух камер, а именно, «перепроицировать» изображения двух камер на общую плоскость. В этом случае, эпиполярные линии будут лежать в двух камерах на одной прямой! Если выбрать систему координат так, чтобы это прямая оказалась горизонтальной, поиск вдоль эпиполярных линий будет соответствовать перемещению вдоль одной из координат в плоскости кадра (по горизонтали). На компьютере с линейной моделью хранения данных в памяти это выполняется наиболее быстро. Такой «пересчет» изображений называется ректификацией кадров. (См. для пояснения рис. 18)

Итак, с использованием эпиполярной геометрии процесс 3D-реконструкции разделяется на 3 чётких стадии:

1) Ректификация изображений;

2) Нахождение (вычисление) сопряжённых точек;

3) Вычисление (восстановление) 3D-координат точек путём триангуляции (рассмотренной выше).

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

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

А вот ректификация и триангуляция представляют собой чисто технические задачи.

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

Пример ректификации стереопары изображений показан на Рис.18.

Рис.18. Построение ректифицированных изображений

Разработаны десятки методов вычисления фундаментальной матрицы F. Основные и самые популярные методы: «7-точек», «M-оценка», «LMedS», «RANSAC» и другие [10].

Компания Вокорд в своей системе 3D-зрения и распознавания лиц VOCORD FaceControl 3D комбинирует различные методы для того, чтобы предоставить заказчику оптимальный баланс между производительностью и точностью.

В настоящее время пространственная точность плотной 3D-реконструкции по всем трём координатам составляет 0.5 мм. Выполняются эти ресурсоёмкие операции в реальном масштабе времени для видеосенсоров FullHD, т.е. 60 МегаПиксел в секунду [11], [12].

Литература.

[8] O. D. Faugeras. Three-dimensional computer vision. The MIT Press, Cambridge, Massachusetts, 1993.

[9] H. C. Longuet-Higgins. A Computer Algorithm for Reconstructing a Scene from Two Projections. Nature, vol. 293, pages 133-135, 1981.

[10] X. Armangu, J. Salvi and J. Batlle. A Comparative Review of Camera Calibrating Methods with Accuracy Evaluation. In Proceedings of the 5th Ibero-American Symposium on Pattern Recognition, Lisboa, Portugal, September 11-13 2000.

[11] Д.Н. Заварикин, А.И. Кадейшвили, С.В. Коробкова, А.Ю. Соколов, О.В. Степаненко “Системы некооперативной биометрической идентификации людей”. Всероссийская конференция с элементами научной школы. МГТУ имени Н.Э.Баумана, Москва, 2011.

[12] А.Ю. Соколов, Д.Н.Заварикин «Компьютерные 3D методы анализа фото и видеоизображений для криминалистических экспертиз», Вестник Московского Университета МВД России, 2013, №4.

[13] http://www.cse.iitd.ernet.in/~suban/vision/geometry/node40.html

[14] http://people.csail.mit.edu/bkph/articles/Tsai_Revisited.pdf

Просмотров: 2905