Kit_Cat 11 ноя 2022 в 13:37

Введение в триангуляцию

4 мин

19K

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

Первое, что необходимо понять, что такое проективное пространство, плоскость и эпиполярные линии.

Проективное пространство

Проективное пространство над полем К — пространство, состоящее из прямых (одномерных подпространств) некоторого линейного пространства над данным полем. Простыми словами это: Просто пространство, где базовыми элементами являются прямые. Прямые из линейного пространства L(K) называются точками проективного пространства. То есть точки в проективном пространстве это прямые в линейном пространстве (например, в трехмерном пространстве). Если L имеет размерность n+1, то размерность проективного пространства является число n. Пример, если за основу линейного пространства взято трехмерное евклидово $R^{3}\,$ , тогда проективное пространство будет двухмерным (проективная плоскость). Само проективное пространство обозначается как $KP^{3}\,$

Проективная плоскость — двумерное проективное пространство. В проективных пространствах используются однородные координаты. Точки в проективной плоскости можно представить в виде однородных координат $[x, y, z]\,$ . При этом координаты $[x, y, z]\,$ и $[tx, ty, tz]\,$ , где t не равно 0, соответствуют одной и той же точке в проективном пространстве. Так как в трехмерном пространстве эти точки лежат на одной прямой, а в проективном пространстве точки это прямые, а прямая у нас одна, значит и точка одна и та же.

Прямые в проективном пространстве это плоскости в линейном пространстве, в качестве примера будем рассматривать $R^3\,$ . Прямые в проективном пространстве также представляются в виде однородных координат в формате $(a, b, c)\,$ , это соответствует плоскости в $R^{3}\,$ $ax+by+cz=0\,$ . Также имеет смысл отношение эквивалентности $(a, b, c) = (da, db, dc)\,$ , где d не равно 0.

В четырехмерном пространстве все тоже самое только у нас 4 координаты, а не 3.

Проективное преобразование — обратимое преобразование проективной плоскости (или пространства), которое переводит прямые в прямые.

Камеры описываются с помощью проективной модели камеры, которая определяется:

Центром камеры
Главной осью (луч, куда смотрит камера)
Плоскостью изображения (куда выполняется проецирование точек)
Системой координат на этой плоскости. Формула проецирования точки из трехмерного пространства на плоскость изображения имеет вид: $х=РХ\,$ , где Х — однородные координаты точки пространства, х — однородные координаты точки плоскости, Р — матрица камеры размера 3*4.

С математическими терминами почти разобрались, осталось еще немного и после можно переходить к делу.

Эпиполярные линии

Есть две камеры. Есть точка в пространстве, которая проецируется на плоскость первой камеры в точку $х_l\,$ , а также проецируется на плоскость второй камеры в точку $х_r\,$ (на прямую l). Точка $x_r\,$ лежит на эпиполярной линии (прямая l). Каждой точке одного изображения камеры соответствует эпиполярная линия.

Эпиполярную геометрию используют для проверки того, что пара точек может быть стереопарой (одной и той же точкой в пространстве). Пара точек является стереопарой тогда и только тогда, когда $x_r^{T}Fx=0\,$ , где F — фундаментальная матрица, зависит от исходных матриц камер (камеры откалиброваны). С помощью фундаментальной матрицы вычисляются уравнения эпиполярных линий ( $l=Fx\,$ ).

Триангуляция

Теперь непосредственно можно переходить к теме статьи и начнем, конечно же, с нудного определения.

Триангуляция (реконструкция) — процесс определения точки в трехмерном пространстве с учетом ее проекций на два или более изображений. Когда у нас есть много проекций на плоское изображение и мы восстанавливаем 3D координату. Наборы одинаковых точек на разных изображений генерируют набор линий в пространстве, которые пересекаются в точке х. Но из-за шума бывает так, что сгенерированные линии не пересекаются или же пересекаются не в той точке. То есть задача состоит в том, чтобы найти трехмерную точку, которая оптимально соответствует измеренными точками изображения.

Чтобы лучше запомнить понятие и применение триангуляции на практике, приведу пример. Есть датасет под названием AIST, который содержит в себе кучу видео, отснятых танцев. Танцор находится в центре сцены, а вокруг него установлено 9 камер. В разметке есть 2D координаты ключевых точек на теле человека (плечо, колено, нос и т.д.). Всего этих точек 17, но это не суть важно. Чтобы получить 3D координаты этих ключевых точек, как раз используют триангуляцию. С помощью 2D координат с девяти камер, восстанавливают координаты в пространстве (там используют метод на основе SVD)

Какие же существуют методы восстановления точки в пространстве.

Метод средний точки
Заключается в минимизации суммы расстояний между 3D точкой и проективных линий. Из точки Х опускаем проекции на проективные линии и вычисляем значение функции: Необходимо минимизировать значение функции f(x). После минимизации искомая точка будет лежать на середине отрезка, который соединяет проективные линии.
Этот метод не подходит, когда у нас больше двух камер. Но здесь можно посмотреть расширение метода на N камер.
Линейная триангуляция
У нас есть уравнения и , где Х — это точка в пространстве, а х — точка на изображении, Р — параметры камеры. Для нахождения координат точки X воспользуемся векторным произведением $x \times PX = 0$ и $x' \times (P'X)=0$
(прим. векторное произведение двух векторов равно нулю тогда и только тогда, когда один из сомножителей равен нулю или векторы коллинеарны).
С помощью векторного произведения получим:
Видно, что 3 строка эта линейная комбинация 1 и 2 строк. Остается первые 2 строки, получаем:
Данную операцию мы проделали для одного изображения, не забываем, что у нас их 2. Добавим 2 изображение и получим:
Данную систему можно решить с помощью SVD разложения.
Работает для любого количества соответствующих изображений.
1. Не линейной решение с помощью фундаментальной матрицы. Как известно, фундаментальная матрица переводит точку на эпиполярную линию. Имеет смысл уравнение $x'Fx=0\,$ . Будем минимизировать проекцию ошибки.