Пряме лінійне перетворення

Пряме лінійне перетворення (англ. Direct linear transformation, 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}$ виконується точно. У цих випадках для розв'язку можна використовувати метод найменших квадратів.

Посилання

• Homography Estimation by Elan Dubrofsky (§2.1 sketches the "Basic DLT Algorithm") (англ.)
• A DLT Solver based on MATLAB by Hsiang-Jen (Johnny) Chien (англ.)