Как стать автором
Обновить

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

Время на прочтение 4 мин
Количество просмотров 14K

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

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

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

Проективное пространство над полем К — пространство, состоящее из прямых (одномерных подпространств) некоторого линейного пространства над данным полем. Простыми словами это: Просто пространство, где базовыми элементами являются прямые. Прямые из линейного пространства 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.

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

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

  1. Центром камеры

  2. Главной осью (луч, куда смотрит камера)

  3. Плоскостью изображения (куда выполняется проецирование точек)

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

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

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

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

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

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

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

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

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

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

  1. Метод средний точки
    Заключается в минимизации суммы расстояний между 3D точкой и проективных линий. Из точки Х опускаем проекции на проективные линии и вычисляем значение функции: f(x) = d(L_1', x)^2 + d(L_2', x)^2 Необходимо минимизировать значение функции f(x). После минимизации искомая точка будет лежать на середине отрезка, который соединяет проективные линии.

    Этот метод не подходит, когда у нас больше двух камер. Но здесь можно посмотреть расширение метода на N камер.

  2. Линейная триангуляция
    У нас есть уравнения x=PX и x'=P'X, где Х — это точка в пространстве, а х — точка на изображении, Р — параметры камеры. Для нахождения координат точки X воспользуемся векторным произведением x \times PX = 0 и x' \times (P'X)=0
    (прим. векторное произведение двух векторов равно нулю тогда и только тогда, когда один из сомножителей равен нулю или векторы коллинеарны).

    P=\left[ \begin{matrix}   p_{11} p_{12} p_{13} p_{14}\\   p_{21} p_{22} p_{23} p_{24} \\  p_{31} p_{32} p_{33} p_{34}  \end{matrix} \right] = \left[ \begin{matrix}   p_1^{T}\\   p_2^{T}  \\  p_3^{T}  \end{matrix} \right] \,

    С помощью векторного произведения получим:

    \left[\begin{matrix} x\\ y\\1\end{matrix} \right] \times  \left[\begin{matrix} p_1^{T}\\ p_2^{T}  \\p_3^{T}\end{matrix} \right] =  \left[\begin{matrix} yp_3^TX - p_2^TX\\ p_1^TX-xp_3^TX  \\xp_2^TX - yp_1^TX\end{matrix} \right] =  \left[\begin{matrix} 0\\0  \\0\end{matrix} \right] \,

    Видно, что 3 строка эта линейная комбинация 1 и 2 строк. Остается первые 2 строки, получаем:

    A_iX=0\,

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

    \left[ \begin{matrix}   yp_3^T - p_2^T\\   p_1^T-xp_3^T \\   y'p_3'^T - p_2'^T\\   p_1'^T-x'p_3'^T  \end{matrix} \right]X =  AX=0\,

    Данную систему можно решить с помощью SVD разложения.
    Работает для любого количества соответствующих изображений.

    1. Не линейной решение с помощью фундаментальной матрицы. Как известно, фундаментальная матрица переводит точку на эпиполярную линию. Имеет смысл уравнение x'Fx=0\,. Будем минимизировать проекцию ошибки.

    cost(X) = dist(x, \hat x)^{2} + dist(x', \hat x')^{2}

Теги:
Хабы:
+12
Комментарии 3
Комментарии Комментарии 3

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн
PG Bootcamp 2024
Дата 16 апреля
Время 09:30 – 21:00
Место
Минск Онлайн
EvaConf 2024
Дата 16 апреля
Время 11:00 – 16:00
Место
Москва Онлайн