Триангуляция — это процесс определения точки в трёхмерном пространстве на основе её проекций на два или более изображений. Для решения этой задачи необходимо знать параметры функции проекции камеры из 3D в 2D для задействованных камер, в простейшем случае представленные . Триангуляция иногда называется реконструкцией.
Задача триангуляции в принципе тривиальна. Поскольку каждая точка на изображении соответствует линии в 3D-пространстве, все точки на этой линии в 3D проецируются в одну точку на изображении. Если можно найти пару на двух или более изображениях, они должны быть проекцией общей 3D-точки x. Набор линий, образованных точками изображения, должен пересекаться в 3D-точке x, и алгебраическая формулировка координат 3D-точки x может быть вычислена различными способами, как показано ниже.
На практике, однако, координаты точек изображения не могут быть измерены с произвольной точностью. Вместо этого различные типы шума, такие как геометрический шум от искажения объектива или ошибка обнаружения ключевых точек, приводят к неточностям в измеренных координатах изображения. Как следствие, линии, образованные соответствующими точками изображения, не всегда пересекаются в 3D-пространстве. Задача, тогда, состоит в том, чтобы найти точку в трёхмерном пространстве, которая оптимально подходит измеренным точкам изображения. В литературе имеется много предложений как определить оптимальность и как найти оптимальную 3D-точку. Поскольку они основаны на разных критериях оптимальности, различные методы дают разные оценки 3D-точки x при наличии шума.
Введение
Далее предполагается, что триангуляция выполняется по соответствующим точкам изображения, полученным с двух точек .
Изображение слева иллюстрирует пары стереокамер (). Точка x в трёхмерном пространстве проецируется на соответствующую плоскость изображения вдоль линии, которая проходит через фокусные точки камер focal point, и , в результате чего получаются две соответствующие точки изображения и . Если и заданы и геометрия двух камер известна, две проекционные линии могут быть определены, и они должны пересекаться в точке x. Используя базовую линейную алгебру можно определить эту точку пересечения простым способом.
Изображение справа показывает реальный случай. Положение точек изображения и не может быть измерено точно. Причина заключается в сочетании таких факторов, как
Геометрические искажения, например, дисторсия линз, означают, что отображение трёхмерного пространства в двумерное изображение камерой отличается от . В некоторой степени эти погрешности можно компенсировать, однако остается остаточная геометрическая ошибка. Один луч света из трёхмерной точки x рассеивается в оптической системе камеры согласно функции рассеяния точки функция рассеяния точки. Восстановление соответствующей точки изображения по измерениям функции рассеянной интенсивности в изображениях приводит к ошибкам. В цифровой камере функция интенсивности изображения измеряется только в дискретных элементах датчика. Для восстановления истинной функции приходится использовать неточную интерполяцию дискретной функции интенсивности. Точки изображения y1' и y2', используемые для триангуляции, часто определяются с помощью различных типов экстракторов признаков, например, углов или точек интереса в целом. Любой тип извлечения признаков, основанный на , имеет присущую ему ошибку локализации.
Вследствие этого, измеренные точки изображения являются и вместо и . Однако их проекционные линии (синие) не обязательно пересекаются в трёхмерном пространстве или не обязательно приближаются к x. Фактически, эти линии пересекаются тогда и только тогда, когда и удовлетворяют , определяемому . Учитывая шум измерений и , весьма вероятно, что эпиполярное ограничение не выполняется, и проекционные линии не пересекаются.
Это наблюдение приводит к проблеме, которая решается триангуляцией. Какая трёхмерная точка xest является наилучшей оценкой точки x, учитывая и и геометрию камер? Ответ часто находится путем определения меры ошибки, зависящей от xest, и последующей минимизации этой ошибки. В следующих разделах кратко описаны некоторые из различных методов вычисления xest, представленных в литературе.
Все методы триангуляции дают xest = x, в случае, когда и , есть когда выполняются эпиполярные ограничения (за исключением особых точек, см. ниже). Различия между методами заключаются в том, что происходит, когда ограничение не выполняется.
Свойства
Метод триангуляции можно описать в терминах функции такой что
где — однородные координаты обнаруженных точек изображения, а — матрицы камер. Трёхмерная точка x — это однородное представление результирующей трёхмерной точки. Знак означает, что требуется лишь для получения вектора, который равен x с точностью до умножения на ненулевой скаляр, поскольку используются однородные векторы.
Прежде чем перейти к конкретным методам, то есть к конкретным функциям , необходимо объяснить некоторые общие концепции, связанные с этими методами. Выбор метода триангуляции для конкретной задачи в некоторой степени зависит от этих характеристик.
Сингулярности
Некоторые методы некорректно вычисляют оценку трёхмерной точки x, если она попадает в определённое подмножество пространства, соответствующее некоторой комбинации . Точка в этом подмножестве является тогда сингулярностью метода триангуляризации. Причиной сбоя может быть недоопределенность решаемой системы уравнений или то, что проективное представление xest становится нулевым вектором для сингулярных точек.
Инвариантость
В некоторых приложениях, желательно, чтобы триангуляция не зависела от системы координат, используемой для представления трёхмерных точек. Если задача триангуляции сформулирована в одной системе координат, а затем преобразована в другую, то полученная оценка xest должна преобразовываться аналогичным образом. Это свойство обычно называют инвариантностью. Не все методы триангуляции обеспечивают инвариантность, по крайней мере, не для общих типов преобразований координат.
Для однородного представления трёхмерных координат наиболее общим преобразованием является проективное преобразование, которое описывается матрицей matrix . Если однородные координаты преобразуются согласно соотношению
то матрицы камер должны преобразоваться как
чтобы получить те же однородные координаты
Если функция триангуляции инварианта к , то следующее отношение должно быть верным
из которого следует, что
для всех
Для каждого метода триангуляции можно определить, справедливо ли последнее соотношение. Если оно справедливо, то это может быть выполнено только для подмножества проективных преобразований, например, для жёстких или аффинных преобразований.
Вычислительная сложность
Функция — это лишь абстрактное представление вычисления, которое на практике может быть достаточно сложным. Некоторые методы дают , в виде замкнутой непрерывной функции, тогда как другие требуют разложения на ряд вычислительных шагов, включающих, например, разложение по сингулярным значениям или нахождение корней полинома. Ещё один класс методов приводит к которая должна основываться на итерационной оценке некоторых параметров. Это означает, что время вычисления и сложность задействованных операций могут различаться между разными методами.
Методы
Метод средней точки
Каждая из двух точек изображения и имеет соответствующую проекционную линию (синюю на правом изображении выше), здесь обозначенную как и , которую можно определить, зная матрицы камеры . Пусть — функция расстояния между прямой L и точкой x в трёхмерном пространстве, такая что является евклидовым расстоянием между и . Метод средней точки находит точку xest, которая минимизирует
Оказывается, что 'xest лежит точно посередине кратчайшего отрезка, соединяющего две проекционные линии.
Прямое линейное преобразование
Посредством существенной матрицы
Проблема, которую необходимо решить, заключается в том, как вычислить по соответствующим нормализованным координатам изображения и . Если известна и определены соответствующие преобразования вращения и параллельного переноса, этот алгоритм (описанный в статье Лонге-Хиггинса) предоставляет решение.
Пусть обозначает строку k'' матрицы вращения :
Комбинируя отношения выше между трёхмерными координатами в двух системах отсчёта и описанного ранее отображения трёхмерных точек на двумерные даёт
или
Как только координата определена, две другие координаты можно вычислить как
Представленный вывод не является единственным. Также возможно начать с выражения для и вывести выражение для , согласно которому
В идеальном случае, когда камера проецирует трёхмерные точки по модели идеальной камеры-обскуры, а полученные двумерные точки могут быть обнаружены без шумов, оба выражения для будут совпадать. Однако на практике это не так, и может быть выгодно объединить две оценки , например, путём некоторого усреднения.
Существуют и другие типы расширений вышеуказанных вычислений. Они начинались с выражения для координат изображения со штрихом и выводили трёхмерные координаты в системе без штриха. Также возможно начать с координат изображения без штриха и получить трёхмерные координаты со штрихом, которые в конечном итоге могут быть преобразованы в трёхмерные координаты без штриха. Опять же, в идеальном случае результат должен совпадать с приведёнными выше выражениями, но на практике они могут отличаться.
Последнее замечание касается того факта, что если существенная матрица определяется по соответствующим координатам изображения, что часто происходит при определении трёхмерных точек таким образом, то вектор переноса известен лишь с точностью до неизвестного положительного масштаба. Как следствие, реконструированные трёхмерные точки также неопределенны относительно положительного масштаба
См. также
Блочное уравнивание Пересечение прямых
Примечания
Литература
Ссылки Two view and multi-view triangulation in Matlab
Категория:Геометрия в компьютерном зрении