Решения PnP проблемы

Авторы:

Александр Кравцов

Авторы:

Владимир Вежневец

Содержание

Решения PnP (n≥4) проблемы

Решение P4P проблемы для модели полной перспективы.

1.1 Определение матрицы A1
1.2 Определение матрицы A2
Вычисление величин θ и φ
Вычисление величины dx

Решение PnP проблемы (n≥5).

Библиография

Как уже было сказано, наибольший интерес представляет P3P проблема в связи с минимальными требованиями к числу соответствий точек изображения и объекта сцены. К сожалению, вплоть до четырех различных конфигураций точек может быть получено в результате аналитического решения с моделью полной перспективы, а решения для упрощенных моделей перспективы при определенных условиях могут быть существенно неточными. В связи с этим некоторое внимание исследователей было уделено исследованию и решению PnP проблемы при n≥4.

Решение P4P проблемы для модели полной перспективы.

Рассмотрим аналитическое решение, предложенное Хораудом и Конио [3] для случая четырех не лежащих в одной плоскости точек. Обозначим данные точки модели через M₀, M₁, M₂ и M₃. Авторы решения предлагают перейти от системы четырех точек модели к пучку из трех не копланарных линий (см. рис. 10). Пусть для определенности, все три линии пересекаются в точке M₀. Обозначим единичные вектора, параллельные линиям M₁M₀, M₂M₀ и M₃M₀ через L₁, L₂ и L₃ соответственно. Тогда l₁, l₂, l₃ – это проекции данных векторов на картинную плоскость. Далее мы будем использовать l₁, l₂, l₃ как для обозначения проекций векторов, так и для представления проекций линий M₁M₀, M₂M₀ и M₃M₀. Введем три координатные системы: первая связана с камерой, вторая с изображением, а третья с объектом сцены. Как именно определяются данные координатные системы будет рассмотрено ниже. Для решения задачи достаточно найти матрицу A перехода от координатной системы объекта к системе координат камеры. Матрица A представима в виде произведения матриц A₁ и A₂, где A₁ определяет переход от системы координат изображения к координатам камеры, а A₂ задает преобразование координат, связанных с объектом сцены, к координатам изображения

Рисунок 10. Замена четырех точек пучком из трех линий.

Определим координатные системы объекта, камеры и изображения следующим образом:

Координатная система объекта. Начало координат поместим в точку M₀. Пусть вектор L₃ задает направление оси Х. Ось Y определяет некоторый вектор P₃, расположенный в плоскости перпендикулярной L₃. Направление оси Z совпадает с направлением векторного произведения L₃ и P₃. Теперь вектора L₁ и L₂ можно разложить по базисным следующим образом:

(21)

где α₁ – угол между L₁ и L₁’(проекция L₁ на плоскость OXY), а α₂ – величина угла между L₂ и L₂’(проекция L₂ на плоскость OXY). Угол между L₁’ и L₂’ полагаем равным 2β. Заметим, что θ - это неизвестная величина, которая позже будет вычислена.

Точку отсчета координатной системы камеры поместим в центр перспективы O. Ось Z совпадает с оптической осью. Плоскость OXY параллельна картинной плоскости и расположена на расстоянии f от нее. (Считаем, что фокусное расстояние камеры известно).
Координатная система изображения вводится таким образом, что она оказывается жестко привязанной к проекциям точек объекта сцены. Центр перспективы O и линия l₁ определяют плоскость, называемую интерпретационной. Стоит отметить, что все возможные пространственные интерпретации l₁ принадлежат этой плоскости. Пусть P₁ – это единичный вектор нормали к интерпретационной плоскости. Вернемся к определению координатной системы связанной с объектом сцены. В качестве вектора P₃ возьмем единичный вектор нормали к интерпретационной плоскости, определяемой прямой l₃ и центром перспективы O. Обозначим точку пересечения линий l₁, l₂, l₃ как J. Ось Х направим вдоль прямой FJ. Пусть k’ – это единичный вектор оси X. k’ принадлежит всем трем интерпретационным плоскостям и, следовательно, перпендикулярен векторам P₁, P₂, P₃. Из этого можно сделать вывод, что вектора P₁, P₂ и P₃ копланарны. Ось Y направим вдоль вектора P₃, а ось Z – вдоль векторного произведения P₃ и k’.

Рисунок 11. Координатная система объекта.

Каждая из матриц A₁, A₂ и A имеет размерность 4х4. (Используем однородные координаты). Для вычисления каждой из матриц необходимо определить 9 коэффициентов вращения и 3 величины, определяющие параллельный перенос.

1.1 Определение матрицы A₁

Для вычисления коэффициентов матрицы A₁ достаточно разложить k’, P₃, k’ЧP₃ по базисным векторам координатной системы камеры.

(22)

Коэффициенты параллельного переноса определяются координатами точки J в системе координат камеры. Таким образом A₁ представлена следующей матрицей:

(23)

1.2 Определение матрицы A₂

Матрица A₂ (матрица перехода от координатной системы объекта к системе координат изображения) определяется девятью коэффициентами вращения и тремя величинами параллельного переноса. Коэффициенты вращения есть коэффициенты разложения векторов L₃, P₃ и L₃ЧP₃ по базисным векторам координатной системы изображения.
На рисунке 12 изображена интерпретационная плоскость прямой l₃. Легко видеть, что вектор L₃ представим в следующем виде:

(24)

Рисунок 12. Интерпретационная плоскость прямой l₃.

Коэффициенты параллельного переноса определяются вектором JM₀, который сонаправлен k’. Таким образом матрица A₂ имеет следующий вид:

(25)

Теперь P4P проблема сведена к задаче определения неизвестных величин θ, φ и d_x.

Вычисление величин θ и φ

Для определения углов достаточно использовать следующие ограничения: так как L₁ принадлежит интерпретационной плоскости, то вектор L₁ ортогонален P₁, то есть:

(26)

Применив преобразование (25) к L₁ и L₂ , представленным выражениями (21), получим:

(27)

(28)

Как мы уже отмечали, вектор k’ перпендикулярен P₁ и P₂, следовательно

(29)

(30)

Углы γ₁ и γ₂ могут быть вычислены следующим образом:

(31)

(32)

(33)

(34)

Подставим полученные выражения для L₁, L₂, P1 и P₂ в (26) и получим соотношения:

(35)

(36)

Из (35) и (36) можно выразить sinθ и cosθ как функции от sinφ и cosφ. Далее, применив ограничение,

получим уравнение четвертой степени относительно cosφ. Это уравнение можно решать в явном виде или итерационно.

Вычисление величины d_x

Определим длину OM₀ (см. рис. 12). Так как

(37)

(38)

то

(39)

Также имеем

(40)

(41)

Подставив (40) и (41) в (39) получим выражение для OM₀, а d_x может быть вычислено таким образом:

Решение PnP проблемы (n≥5).

Отедльного аналитического решения P5P проблемы не встретилось автору в изученной литературе. Некоторые исследователи предлагают подразбивать множество 5 точек объекта на подмножества, состоящие из 3, 4 точек, и для них решать P3P и P4P задачи. Конечное решение заключается в области пересечения решений P3P и P4P задач, но, возможно, подобное пересечение будет сложно найти при условии искаженных начальных данных.
Шести соответствий точек объекта и их проекций на картинную плоскость достаточно, для составления и однозначного решения системы линейных уравнений относительно неизвестных величин углов поворота и параллельного переноса перехода из координатной системы объекта в систему координат камеры.

Библиография

Martin A. Fischler, Robert C. Bolles "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography", Communications of the ACM, June 1981, vol. 24(6): 381-395 (1981)
William J, Wolfe, Donald Mathis "The Perspective View of Three Points", IEEE Transactions on Pattern Analysis and Machine Intelligence, January 1991, vol. 13(1): 66-73 (1991)
Radu Horaud, Bernard Conio "An Analytic Solution for the Perspective 4-Point Problem", Computer Vision, Graphics and Image Processing volume 47 pages 33--44 1989
Daniel DeMenthon, Larry S. Davis, "Exact and Approximate Solutions of the Perspective-Three-Point Problem". IEEE Transactions on Pattern Analysis and Machine Intelligence 14(11): 1100-1105 (1992)
Rodrigo L. Carceroni, Christopher M. Brown "Numerical Methods for Model-Based Pose Recovery", TR659, Computer Science Dept., U. Rochester, August 1997.
Philippe Ballard, George C. Stockman "Controlling a Computer via Facial Aspect", IEEE Trans. Sys,Man and Cybernetics, 25(4):669-677, 1995.
T. D. Alter "3D Pose From 3 Corresponding points under weak-Perspective Projection", Technical Report 1378, MIT Artificial Intelligence Laboratory, 1992.
Vera Bakic, George Stockman "Menu Selection by Facial Aspect", Proceedings of Vision Interface 99, Trois Rivieres, Quebec, CAN (19-21 May 99)

Дополнительная информация

Ссылка:

Александр Кравцов, Владимир Вежневец. Решения PnP проблемы. Компьютерная графика и мультимедиа. Выпуск №1(3)/2003. http://cgm.computergraphics.ru/content/view/42

Выпуск:

Выпуск №1(3)/2003

Компьютерная Графика и Мультимедиа Сетевой журнал

Разделы

Содержание