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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особенности

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

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

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

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

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

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

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

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

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

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

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

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

${\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}),}$   для всех ${\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2}}$

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

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

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

Методы

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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})}}}$

или

${\displaystyle 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} }}}$

После определения две другие координаты можно вычислить как ${\displaystyle x_{3}}$

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

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

${\displaystyle 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-точки могут быть обнаружены без какого-либо шума, два выражения для равны. Однако на практике это не так, и может оказаться выгодным объединить две оценки , например, с помощью некоторого среднего значения. ${\displaystyle x_{3}}$ ${\displaystyle x_{3}}$

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

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

Смотрите также

• Регулировка связки
• Пересечение линий

Рекомендации

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

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

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