Триангуляция (компьютерное зрение)

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

Проблема триангуляции в принципе тривиальна. Поскольку каждая точка изображения соответствует линии в трехмерном пространстве, все точки на линии в трехмерном пространстве проецируются на точку на изображении. Если можно найти пару соответствующих точек на двух или более изображениях, это должно быть так, что они являются проекцией общей трехмерной точки x . Набор линий, генерируемых точками изображения, должен пересекаться в точке x (3D-точка), а алгебраическая формулировка координат x (3D-точка) может быть вычислена различными способами, как представлено ниже.

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

Введение

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

Идеальный случай эпиполярной геометрии. Трехмерная точка x проецируется на изображения двух камер через линии (зеленые), которые пересекаются с фокусной точкой каждой камеры, **O ₁** и **O ₂** . Полученные точки изображения — **y ₁** и **y ₂** . Зеленые линии пересекаются в точке x .

На практике точки изображения **y ₁** и **y ₂** не могут быть измерены с произвольной точностью. Вместо этого точки **y' ₁** и **y' ₂** обнаруживаются и используются для триангуляции. Соответствующие линии проекции (синие), как правило, не пересекаются в трехмерном пространстве, а также могут не пересекаться с точкой x .

Изображение слева иллюстрирует эпиполярную геометрию пары стереокамер модели-обскуры . Точка x камеры (3D-точка) в трехмерном пространстве проецируется на соответствующую плоскость изображения вдоль линии (зеленого цвета), проходящей через фокус . $\mathbf {O} _{1}$ и $\mathbf {O} _{2}$ , в результате чего появляются две соответствующие точки изображения $\mathbf {y} _{1}$ и $\mathbf {y} _{2}$ . Если $\mathbf {y} _{1}$ и $\mathbf {y} _{2}$ заданы и известна геометрия двух камер, можно определить две линии проекции (зеленые линии), и должно быть так, чтобы они пересекались в точке x (3D-точка). Используя базовую линейную алгебру , эту точку пересечения можно определить простым способом.

Изображение справа показывает реальный случай. Положение точек изображения $\mathbf {y} _{1}$ и $\mathbf {y} _{2}$ невозможно точно измерить. Причиной является сочетание таких факторов, как

Геометрические искажения, например искажение объектива , означающие, что преобразование 3D в 2D камеры отличается от модели камеры-обскуры . В некоторой степени эти ошибки можно компенсировать, оставив остаточную геометрическую ошибку.
Одиночный луч света от точки x (3D-точки) рассеивается в системе линз камер в соответствии с функцией рассеяния точки . Восстановление соответствующей точки изображения по измерениям функции дисперсной интенсивности на изображениях дает ошибки.
В цифровой камере функция интенсивности изображения измеряется только в дискретных сенсорных элементах. Для восстановления истинной функции приходится использовать неточную интерполяцию дискретной функции интенсивности.
Изображение точки y ₁^' и y ₂ ', используемые для триангуляции, часто находятся с использованием различных типов экстракторов объектов, например углов или точек интереса в целом. Существует присущая ошибка локализации для любого типа извлечения признаков, основанного на операциях соседства .

Как следствие, измеренные точки изображения $\mathbf {y} '_{1}$ и $\mathbf {y} '_{2}$ вместо $\mathbf {y} _{1}$ и $\mathbf {y} _{2}$ . Однако их линии проекции (синие) не обязательно должны пересекаться в трехмерном пространстве или приближаться к x . Действительно, эти прямые пересекаются тогда и только тогда, когда $\mathbf {y} '_{1}$ и $\mathbf {y} '_{2}$ удовлетворять эпиполярному ограничению, определенному фундаментальной матрицей . Учитывая шум измерения в $\mathbf {y} '_{1}$ и $\mathbf {y} '_{2}$ весьма вероятно, что эпиполярное ограничение не выполняется и линии проекций не пересекаются.

Это наблюдение приводит к проблеме, которая решается в триангуляции. Какая трехмерная точка x _est является наилучшей оценкой x с учетом $\mathbf {y} '_{1}$ и $\mathbf {y} '_{2}$ а геометрия камер? Ответ часто находится путем определения меры ошибки, которая зависит от xest _, а затем минимизации этой ошибки. В следующих разделах кратко описаны некоторые из различных методов вычисления x _est, представленных в литературе.

Все методы триангуляции дают x _est = x в том случае, если $\mathbf {y} _{1}=\mathbf {y} '_{1}$ и $\mathbf {y} _{2}=\mathbf {y} '_{2}$ , то есть когда эпиполярное ограничение выполнено (за исключением особых точек, см. ниже). То, что происходит, когда ограничение не удовлетворяется, различается в зависимости от метода.

Характеристики

Метод триангуляции можно описать с помощью функции $\tau \,$ такой, что

\mathbf {x} \sim \tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2})

где $\mathbf {y} '_{1},\mathbf {y} '_{2}$ – однородные координаты обнаруженных точек изображения и $\mathbf {C} _{1},\mathbf {C} _{2}$ матрицы камер. x (3D-точка) — однородное представление полученной 3D-точки. $\sim \,$ знак означает, что $\tau \,$ требуется только для создания вектора, который равен x с точностью до умножения на ненулевой скаляр, поскольку задействованы однородные векторы.

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

Особенности

Некоторые методы не могут правильно вычислить оценку x (3D-точки), если она лежит в определенном подмножестве трехмерного пространства, соответствующем некоторой комбинации $\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2}$ . Точка в этом подмножестве является тогда особенностью метода триангуляции. Причиной неудачи может быть то, что какая-то система уравнений, которую необходимо решить, недостаточно определена или что проективное представление x _est становится нулевым вектором для особых точек.

Инвариантность

В некоторых приложениях желательно, чтобы триангуляция не зависела от системы координат, используемой для представления трехмерных точек; если задача триангуляции сформулирована в одной системе координат, а затем преобразована в другую, то результирующая оценка x _est должна преобразоваться аналогичным образом. Это свойство обычно называют инвариантностью . Не каждый метод триангуляции обеспечивает инвариантность, по крайней мере, для общих типов преобразований координат.

Для однородного представления трехмерных координат наиболее общим преобразованием является проективное преобразование, представленное $4\times 4$ матрица $\mathbf {T}$ . Если однородные координаты преобразовать по закону

\mathbf {\bar {x}} \sim \mathbf {T} \,\mathbf {x}

тогда матрицы камеры должны преобразоваться как ( C _k )

\mathbf {\bar {C}} _{k}\sim \mathbf {C} _{k}\,\mathbf {T} ^{-1}

для создания одинаковых однородных координат изображения ( y _k )

\mathbf {y} _{k}\sim \mathbf {\bar {C}} _{k}\,\mathbf {\bar {x}} =\mathbf {C} _{k}\,\mathbf {x}

Если функция триангуляции $\tau$ инвариантен к $\mathbf {T}$ тогда должно быть справедливо следующее соотношение

\mathbf {\bar {x}} _{\rm {est}}\sim \mathbf {T} \,\mathbf {x} _{\rm {est}}

из чего следует, что

\tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2})\sim \mathbf {T} ^{-1}\,\tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1}\,\mathbf {T} ^{-1},\mathbf {C} _{2}\,\mathbf {T} ^{-1}),

для всех

\mathbf {y} '_{1},\mathbf {y} '_{2}

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

Вычислительная сложность

Функция $\tau$ — это всего лишь абстрактное представление вычислений, которые на практике могут быть относительно сложными. Некоторые методы приводят к $\tau$ которая представляет собой непрерывную функцию в замкнутой форме, в то время как другие необходимо разложить на серию вычислительных шагов, включающих, например, SVD или поиск корней многочлена. Еще один класс методов приводит к $\tau$ который должен основываться на итеративной оценке некоторых параметров. Это означает, что как время вычислений, так и сложность выполняемых операций могут различаться в зависимости от метода.

Методы

Метод средней точки

Каждая из двух точек изображения $\mathbf {y} '_{1}$ и $\mathbf {y} '_{2}$ имеет соответствующую линию проекции (синюю на правом изображении выше), здесь обозначенную как $\mathbf {L} '_{1}$ и $\mathbf {L} '_{2}$ , что можно определить по матрицам камер $\mathbf {C} _{1},\mathbf {C} _{2}$ . Позволять $d\,$ быть функцией расстояния между (3D-линией) L и x (3D-точкой) такой, что $d(\mathbf {L} ,\mathbf {x} )$ это евклидово расстояние между $\mathbf {L}$ и $\mathbf {x}$ .Метод средней точки находит точку xest _, которая минимизирует

d(\mathbf {L} '_{1},\mathbf {x} )^{2}+d(\mathbf {L} '_{2},\mathbf {x} )^{2}

Оказывается, xest _. лежит точно в середине самого короткого отрезка, соединяющего две линии проекции

Прямое линейное преобразование

Через существенную матрицу

Проблема, которую необходимо решить, состоит в том, как вычислить $(x_{1},x_{2},x_{3})$ учитывая соответствующие нормализованные координаты изображения $(y_{1},y_{2})$ и $(y'_{1},y'_{2})$ . Если существенная матрица известна и соответствующие преобразования вращения и сдвига определены, этот алгоритм (описанный в статье Лонге-Хиггинса) обеспечивает решение.

Позволять $\mathbf {r} _{k}$ обозначим строку k матрицы вращения $\mathbf {R}$ :

\mathbf {R} ={\begin{pmatrix}-\mathbf {r} _{1}-\\-\mathbf {r} _{2}-\\-\mathbf {r} _{3}-\end{pmatrix}}

Объединение вышеуказанных отношений между 3D-координатами в двух системах координат и описанным ранее сопоставлением между 3D- и 2D-точками дает

y'_{1}={\frac {x'_{1}}{x'_{3}}}={\frac {\mathbf {r} _{1}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}{\mathbf {r} _{3}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}}={\frac {\mathbf {r} _{1}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}{\mathbf {r} _{3}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}}

или

x_{3}={\frac {(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {y} }}

Один раз $x_{3}$ определена, две другие координаты можно вычислить как

{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=x_{3}{\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}

Приведенный выше вывод не является уникальным. Также можно начать с выражения для $y'_{2}$ и вывести выражение для $x_{3}$ в соответствии с

x_{3}={\frac {(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {y} }}

В идеальном случае, когда камера отображает 3D-точки в соответствии с идеальной камерой-обскурой и полученные 2D-точки могут быть обнаружены без какого-либо шума, два выражения для $x_{3}$ равны. Однако на практике это не так, и может оказаться выгодным объединить две оценки $x_{3}$ , например, в терминах какого-то среднего.

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

Последнее замечание относится к тому факту, что если существенная матрица определяется по соответствующей координате изображения, что часто имеет место, когда трехмерные точки определяются таким способом, вектор перемещения $\mathbf {t}$ известен только с точностью до неизвестного положительного масштабирования. Как следствие, восстановленные 3D-точки также не определены в отношении положительного масштабирования.

См. также

Ссылки

Ричард Хартли и Эндрю Зиссерман (2003). Множественная геометрия в компьютерном зрении . Издательство Кембриджского университета. ISBN 978-0-521-54051-3 .

Внешние ссылки

Двухракурсная и многоракурсная триангуляция в Matlab