Прямое линейное преобразование

Прямое линейное преобразование ( DLT ) — это алгоритм, который решает набор переменных из набора отношений подобия:

$\mathbf {x} _{k}\propto \mathbf {A} \,\mathbf {y} _{k}$ для $\,k=1,\ldots ,N$

где $\mathbf {x} _{k}$ и $\mathbf {y} _{k}$ являются известными векторами, $\,\propto$ обозначает равенство с точностью до неизвестного скалярного умножения, а $\mathbf {A}$ — это матрица (или линейное преобразование), содержащая неизвестные, которые необходимо решить.

Этот тип отношений часто встречается в проективной геометрии . Практические примеры включают связь между 3D-точками сцены и их проекцией на плоскость изображения камеры-обскуры . и гомографии .

Введение

Обыкновенная система линейных уравнений

$\mathbf {x} _{k}=\mathbf {A} \,\mathbf {y} _{k}$ для $\,k=1,\ldots ,N$

можно решить, например, переписав его в виде матричного уравнения $\mathbf {X} =\mathbf {A} \,\mathbf {Y}$ где матрицы $\mathbf {X}$ и $\mathbf {Y}$ содержат векторы $\mathbf {x} _{k}$ и $\mathbf {y} _{k}$ в соответствующих столбцах. Учитывая, что существует единственное решение, оно имеет вид

$\mathbf {A} =\mathbf {X} \,\mathbf {Y} ^{T}\,(\mathbf {Y} \,\mathbf {Y} ^{T})^{-1}.$

Решения также могут быть описаны в случае, если уравнения переопределены или недостаточно определены.

Что отличает задачу прямого линейного преобразования от приведенного выше стандартного случая, так это тот факт, что левая и правая части определяющего уравнения могут отличаться на неизвестный мультипликативный коэффициент, который зависит от k . Как следствие, $\mathbf {A}$ не может быть вычислено, как в стандартном случае. Вместо этого отношения подобия переписываются как собственные линейные однородные уравнения, которые затем можно решить стандартным методом. Сочетание переписывания уравнений подобия в виде однородных линейных уравнений и решения их стандартными методами называется алгоритмом прямого линейного преобразования или алгоритмом DLT . DLT приписывается Ивану Сазерленду.

Пример

Предположим, что $k\in \{1,...,N\}$. Позволять $\mathbf {x} _{k}=(x_{1k},x_{2k})\in \mathbb {R} ^{2}$ и $\mathbf {y} _{k}=(y_{1k},y_{2k},y_{3k})\in \mathbb {R} ^{3}$ — два известных вектора, и мы хотим найти $2\times 3$ матрица $\mathbf {A}$ такой, что

$\alpha _{k}\,\mathbf {x} _{k}=\mathbf {A} \,\mathbf {y} _{k}$

где $\alpha _{k}\neq 0$ — неизвестный скалярный коэффициент, связанный с уравнением k .

Чтобы избавиться от неизвестных скаляров и получить однородные уравнения, определим антисимметричную матрицу

$\mathbf {H} ={\begin{pmatrix}0&-1\\1&0\end{pmatrix}}$

и умножим обе части уравнения на $\mathbf {x} _{k}^{T}\,\mathbf {H}$ слева

${\begin{aligned}(\mathbf {x} _{k}^{T}\,\mathbf {H} )\,\alpha _{k}\,\mathbf {x} _{k}&=(\mathbf {x} _{k}^{T}\,\mathbf {H} )\,\mathbf {A} \,\mathbf {y} _{k}\\\alpha _{k}\,\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {x} _{k}&=\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}\end{aligned}}$

С $\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {x} _{k}=0,$ под рукой имеются следующие однородные уравнения, которые уже не содержат неизвестных скаляров

$\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}=0$

Чтобы решить $\mathbf {A}$ из этой системы уравнений рассмотрим элементы векторов $\mathbf {x} _{k}$ и $\mathbf {y} _{k}$ и матрица $\mathbf {A}$:

$\mathbf {x} _{k}={\begin{pmatrix}x_{1k}\\x_{2k}\end{pmatrix}}$,   $\mathbf {y} _{k}={\begin{pmatrix}y_{1k}\\y_{2k}\\y_{3k}\end{pmatrix}}$, и $\mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\end{pmatrix}}$

и приведенное выше однородное уравнение принимает вид

$0=a_{11}\,x_{2k}\,y_{1k}-a_{21}\,x_{1k}\,y_{1k}+a_{12}\,x_{2k}\,y_{2k}-a_{22}\,x_{1k}\,y_{2k}+a_{13}\,x_{2k}\,y_{3k}-a_{23}\,x_{1k}\,y_{3k}$ для $\,k=1,\ldots ,N.$

Это также можно записать в матричной форме:

$0=\mathbf {b} _{k}^{T}\,\mathbf {a}$ для $\,k=1,\ldots ,N$

где $\mathbf {b} _{k}$ и $\mathbf {a}$ оба являются 6-мерными векторами, определяемыми как

$\mathbf {b} _{k}={\begin{pmatrix}x_{2k}\,y_{1k}\\-x_{1k}\,y_{1k}\\x_{2k}\,y_{2k}\\-x_{1k}\,y_{2k}\\x_{2k}\,y_{3k}\\-x_{1k}\,y_{3k}\end{pmatrix}}$ и $\mathbf {a} ={\begin{pmatrix}a_{11}\\a_{21}\\a_{12}\\a_{22}\\a_{13}\\a_{23}\end{pmatrix}}.$

На данный момент у нас есть 1 уравнение и 6 неизвестных. Совокупность однородных уравнений можно записать в матричной форме

$\mathbf {0} =\mathbf {B} \,\mathbf {a}$

где $\mathbf {B}$ это $N\times 6$ матрица, содержащая известные векторы $\mathbf {b} _{k}$ в своих рядах. Неизвестное $\mathbf {a}$ может быть определена, например, путем разложения по сингулярным значениям $\mathbf {B}$; $\mathbf {a}$ является правым сингулярным вектором $\mathbf {B}$ соответствующее сингулярному значению, равному нулю. Один раз $\mathbf {a}$ определены элементы матрицы $\mathbf {A}$ можно переставить из вектора $\mathbf {a}$. Обратите внимание, что масштабирование $\mathbf {a}$ или $\mathbf {A}$ не имеет значения (за исключением того, что оно должно быть отличным от нуля), поскольку определяющие уравнения уже допускают неизвестное масштабирование.

На практике векторы $\mathbf {x} _{k}$ и $\mathbf {y} _{k}$ может содержать шум, а это означает, что уравнения подобия верны только приблизительно. Как следствие, вектора может не быть. $\mathbf {a}$ которое решает однородное уравнение $\mathbf {0} =\mathbf {B} \,\mathbf {a}$ точно. В этих случаях полное решение методом наименьших квадратов , выбрав можно использовать $\mathbf {a}$ как правый сингулярный вектор, соответствующий наименьшему сингулярному значению $\mathbf {B} .$

Более общие случаи

В приведенном выше примере есть $\mathbf {x} _{k}\in \mathbb {R} ^{2}$ и $\mathbf {y} _{k}\in \mathbb {R} ^{3}$, но общую стратегию переписывания отношений подобия в однородные линейные уравнения можно обобщить на произвольные размерности как для $\mathbf {x} _{k}$ и $\mathbf {y} _{k}.$

Если $\mathbf {x} _{k}\in \mathbb {R} ^{2}$ и $\mathbf {y} _{k}\in \mathbb {R} ^{q}$ предыдущие выражения все еще могут привести к уравнению

$0=\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}$ для $\,k=1,\ldots ,N$

где $\mathbf {A}$ сейчас это $2\times q.$ Каждый k представляет собой одно уравнение в $2q$ неизвестные элементы $\mathbf {A}$ и вместе эти уравнения можно записать $\mathbf {B} \,\mathbf {a} =\mathbf {0}$ для известных $N\times 2\,q$ матрица $\mathbf {B}$ и неизвестный 2q -мерный вектор $\mathbf {a} .$ Этот вектор можно найти аналогично предыдущему способу.

В самом общем случае $\mathbf {x} _{k}\in \mathbb {R} ^{p}$ и $\mathbf {y} _{k}\in \mathbb {R} ^{q}$. Основное отличие от предыдущего заключается в том, что матрица $\mathbf {H}$ сейчас это $p\times p$ и антисимметричный. Когда $p>2$ пространство таких матриц уже не одномерно, оно имеет размерность

$M={\frac {p\,(p-1)}{2}}.$

Это означает, что каждое значение k дает M однородных уравнений типа

$0=\mathbf {x} _{k}^{T}\,\mathbf {H} _{m}\,\mathbf {A} \,\mathbf {y} _{k}$ для $\,m=1,\ldots ,M$ и для $\,k=1,\ldots ,N$

где $\mathbf {H} _{m}$ является M -мерным базисом пространства $p\times p$ антисимметричные матрицы.

Пример р = 3

В случае p = 3 следующие три матрицы $\mathbf {H} _{m}$ можно выбрать

$\mathbf {H} _{1}={\begin{pmatrix}0&0&0\\0&0&-1\\0&1&0\end{pmatrix}}$,   $\mathbf {H} _{2}={\begin{pmatrix}0&0&1\\0&0&0\\-1&0&0\end{pmatrix}}$,   $\mathbf {H} _{3}={\begin{pmatrix}0&-1&0\\1&0&0\\0&0&0\end{pmatrix}}.$

В этом частном случае однородные линейные уравнения можно записать в виде

$\mathbf {0} =[\mathbf {x} _{k}]_{\times }\,\mathbf {A} \,\mathbf {y} _{k}$ для $\,k=1,\ldots ,N$

где $[\mathbf {x} _{k}]_{\times }$ — матричное представление векторного векторного произведения . Обратите внимание, что последнее уравнение имеет векторное значение; левая часть — это нулевой элемент в $\mathbb {R} ^{3}$.

Каждое значение k дает три однородных линейных уравнения с неизвестными элементами $\mathbf {A}$. Однако, поскольку $[\mathbf {x} _{k}]_{\times }$ имеет ранг = 2, не более двух уравнений линейно независимы. Поэтому на практике принято использовать только две из трех матриц. $\mathbf {H} _{m}$, например, для m =1, 2. Однако линейная зависимость между уравнениями зависит от $\mathbf {x} _{k}$, а это значит, что в неудачных случаях лучше было бы выбрать, например, m =2,3. Как следствие, если количество уравнений не имеет значения, возможно, лучше использовать все три уравнения, когда матрица $\mathbf {B}$ построен.

Линейная зависимость между полученными однородными линейными уравнениями представляет собой общую проблему для случая p > 2, и ее приходится решать либо путем сокращения набора антисимметричных матриц $\mathbf {H} _{m}$ или позволив $\mathbf {B}$ стать больше, чем необходимо для определения $\mathbf {a} .$

Ссылки

• Ричард Хартли и Эндрю Зиссерман (2003). Множественная геометрия в компьютерном зрении . Издательство Кембриджского университета. ISBN  978-0-521-54051-3 .

Внешние ссылки

• Оценка гомографии Элана Дубровски (в §2.1 описывается «Базовый алгоритм DLT»)

• Решатель DLT на основе MATLAB Сян-Джена (Джонни) Чиена