Введение в триангуляцию
Когда возникла необходимость понять, что из себя представляет триангуляции (не визуализация поверхности, а реконструкция), к моему удивление найти удалось не так много материалов. После изучения темы было решено собрать все, что мне удалось накопать, в одну статью, в надежде, что кому-то это может пригодится и поможет в будущем. Прежде чем сразу бросаться терминами, что такое триангуляция, побросаемся другими не менее сложными пояснениями.
Первое, что необходимо понять, что такое проективное пространство, плоскость и эпиполярные линии.
Проективное пространство
Проективное пространство над полем К — пространство, состоящее из прямых (одномерных подпространств) некоторого линейного пространства над данным полем. Простыми словами это: Просто пространство, где базовыми элементами являются прямые. Прямые из линейного пространства L(K) называются точками проективного пространства. То есть точки в проективном пространстве это прямые в линейном пространстве (например, в трехмерном пространстве). Если L имеет размерность n+1, то размерность проективного пространства является число n. Пример, если за основу линейного пространства взято трехмерное евклидово
Проективная плоскость — двумерное проективное пространство. В проективных пространствах используются однородные координаты. Точки в проективной плоскости можно представить в виде однородных координат
Прямые в проективном пространстве это плоскости в линейном пространстве, в качестве примера будем рассматривать
В четырехмерном пространстве все тоже самое только у нас 4 координаты, а не 3.
Проективное преобразование — обратимое преобразование проективной плоскости (или пространства), которое переводит прямые в прямые.
Камеры описываются с помощью проективной модели камеры, которая определяется:
Центром камеры
Главной осью (луч, куда смотрит камера)
Плоскостью изображения (куда выполняется проецирование точек)
Системой координат на этой плоскости. Формула проецирования точки из трехмерного пространства на плоскость изображения имеет вид:
, где Х — однородные координаты точки пространства, х — однородные координаты точки плоскости, Р — матрица камеры размера 3*4.
С математическими терминами почти разобрались, осталось еще немного и после можно переходить к делу.
Эпиполярные линии
Есть две камеры. Есть точка в пространстве, которая проецируется на плоскость первой камеры в точку
Эпиполярную геометрию используют для проверки того, что пара точек может быть стереопарой (одной и той же точкой в пространстве). Пара точек является стереопарой тогда и только тогда, когда
Триангуляция
Теперь непосредственно можно переходить к теме статьи и начнем, конечно же, с нудного определения.
Триангуляция (реконструкция) — процесс определения точки в трехмерном пространстве с учетом ее проекций на два или более изображений. Когда у нас есть много проекций на плоское изображение и мы восстанавливаем 3D координату. Наборы одинаковых точек на разных изображений генерируют набор линий в пространстве, которые пересекаются в точке х. Но из-за шума бывает так, что сгенерированные линии не пересекаются или же пересекаются не в той точке. То есть задача состоит в том, чтобы найти трехмерную точку, которая оптимально соответствует измеренными точками изображения.
Чтобы лучше запомнить понятие и применение триангуляции на практике, приведу пример. Есть датасет под названием AIST, который содержит в себе кучу видео, отснятых танцев. Танцор находится в центре сцены, а вокруг него установлено 9 камер. В разметке есть 2D координаты ключевых точек на теле человека (плечо, колено, нос и т.д.). Всего этих точек 17, но это не суть важно. Чтобы получить 3D координаты этих ключевых точек, как раз используют триангуляцию. С помощью 2D координат с девяти камер, восстанавливают координаты в пространстве (там используют метод на основе SVD)
Какие же существуют методы восстановления точки в пространстве.
Метод средний точки
Заключается в минимизации суммы расстояний между 3D точкой и проективных линий. Из точки Х опускаем проекции на проективные линии и вычисляем значение функции:Необходимо минимизировать значение функции f(x). После минимизации искомая точка будет лежать на середине отрезка, который соединяет проективные линии. Этот метод не подходит, когда у нас больше двух камер. Но здесь можно посмотреть расширение метода на N камер.
Линейная триангуляция
У нас есть уравненияи , где Х — это точка в пространстве, а х — точка на изображении, Р — параметры камеры. Для нахождения координат точки X воспользуемся векторным произведением и
(прим. векторное произведение двух векторов равно нулю тогда и только тогда, когда один из сомножителей равен нулю или векторы коллинеарны).С помощью векторного произведения получим:
Видно, что 3 строка эта линейная комбинация 1 и 2 строк. Остается первые 2 строки, получаем:
Данную операцию мы проделали для одного изображения, не забываем, что у нас их 2. Добавим 2 изображение и получим:
Данную систему можно решить с помощью SVD разложения.
Работает для любого количества соответствующих изображений.Не линейной решение с помощью фундаментальной матрицы. Как известно, фундаментальная матрица переводит точку на эпиполярную линию. Имеет смысл уравнение
. Будем минимизировать проекцию ошибки.