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

редактировать

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

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

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

Содержание

1 Введение
2 Свойства методов триангуляции
- 2.1 Сингулярности
- 2.2 Инвариантность
- 2.3 Вычислительная сложность
3 Некоторые методы триангуляции, найденные в литературе
- 3.1 Mid- точечный метод
- 3.2 Прямое линейное преобразование
- 3.3 Через основную матрицу
- 3.4 Оптимальная триангуляция
4 Ссылки
5 Внешние ссылки

Введение

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

Идеальный случай эпиполярной геометрии. Трехмерная точка x проецируется на изображения двух камер через линии (зеленые), которые пересекаются с фокусными точками каждой камеры, O1и O2. Результирующие точки изображения: y1и y2. Зеленые линии пересекаются в точке x.

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

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

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

Геометрическое искажение, например искажение линзы, что означает, что преобразование камеры из 3D в 2D отличается от модели камеры-обскуры . В некоторой степени эти ошибки можно компенсировать, оставив остаточную геометрическую ошибку.
Один луч света из x (трехмерная точка) рассеивается в системе линз камер в соответствии с функция рассеяния точки. Восстановление соответствующей точки изображения из измерений функции рассеянной интенсивности в изображениях дает ошибки.
В цифровой камере функция интенсивности изображения измеряется только в дискретных элементах датчика. Чтобы восстановить истинную, необходимо использовать неточную интерполяцию дискретной функции интенсивности.
Точки изображения y1и y2', используемые для триангуляции, часто обнаруживаются с использованием различных типов экстракторов признаков, например углов или интересные места в целом. При любом типе извлечения признаков на основе операций по соседству.

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

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

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

Свойства методов триангуляции

Метод триангуляции можно описать в терминах функции $τ {\ displaystyle \ tau \,}$ $\ tau \,$ такой, что

Икс ∼ τ (Y 1 ', Y 2', C 1, C 2) {\ Displaystyle \ mathbf {x} \ sim \ tau (\ mathbf {y} '_ {1}, \ mathbf {y}' _ { 2}, \ mathbf {C} _ {1}, \ mathbf {C} _ {2})}

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

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

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

Особенности

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

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

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

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

x ¯ ∼ T x {\ displaystyle \ mathbf {\ bar {x}} \ sim \ mathbf {T} \, \ mathbf {x}}

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

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

C ¯ k ∼ C k T - 1 {\ displaystyle \ mathbf {\ bar {C}} _ ​​{k} \ sim \ mathbf {C} _ {k} \, \ mathbf {T} ^ {- 1}}

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

для получения одинаковых координат однородного изображения (yk)

yk ∼ C ¯ kx ¯ = C kx {\ displaystyle \ mathbf {y} _ {k} \ sim \ mathbf {\ bar {C }} _ {k} \, \ mathbf {\ bar {x}} = \ mathbf {C} _ {k} \, \ mathbf {x}}

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

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

x ¯ est ∼ T xest {\ displaystyle \ mathbf {\ bar {x}} _ {\ rm {est}} \ sim \ mathbf {T} \, \ mathbf {x} _ {\ rm {est}}}

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

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

τ (Y 1 ′, Y 2 ′, C 1, C 2) ∼ T - 1 τ (Y 1 ′, y 2 ′, C 1 T - 1, C 2 T - 1), {\ Displaystyle \ 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}),}

\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}}),

для всех

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

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

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

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

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

Некоторые методы триангуляции, найденные в литературе

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

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

d (L, x) = {\ displaystyle d (\ mathbf {L}, \ mathbf {x}) =}

d ({\ mathbf {L}}, { \ mathbf {x}}) =

евклидово расстояние между

L {\ displaystyle \ mathbf {L}}

{\ mathbf {L}}

x {\ displaystyle \ mathbf {x}}

\ mathbf {x}

Метод средней точки находит точку xest, которая минимизирует

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

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

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

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

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

Оптимальная триангуляция

Ссылки

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

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

Два вида и многовидовая триангуляция в Matlab