Восьмиточковий алгоритм

Запишемо

${\displaystyle \mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}}$ і ${\displaystyle \mathbf {y} '={\begin{pmatrix}y'_{1}\\y'_{2}\\1\end{pmatrix}}}$ і ${\displaystyle \mathbf {E} ={\begin{pmatrix}e_{11}&e_{12}&e_{13}\\e_{21}&e_{22}&e_{23}\\e_{31}&e_{32}&e_{33}\end{pmatrix}}}$

тоді умову компланарності можна переписати як

${\displaystyle y'_{1}y_{1}e_{11}+y'_{1}y_{2}e_{12}+y'_{1}e_{13}+y'_{2}y_{1}e_{21}+y'_{2}y_{2}e_{22}+y'_{2}e_{23}+y_{1}e_{31}+y_{2}e_{32}+e_{33}=0\,}$

або

${\displaystyle \mathbf {e} \cdot {\tilde {\mathbf {y} }}=0}$

де

${\displaystyle {\tilde {\mathbf {y} }}={\begin{pmatrix}y'_{1}y_{1}\\y'_{1}y_{2}\\y'_{1}\\y'_{2}y_{1}\\y'_{2}y_{2}\\y'_{2}\\y_{1}\\y_{2}\\1\end{pmatrix}}}$ і ${\displaystyle \mathbf {e} ={\begin{pmatrix}e_{11}\\e_{12}\\e_{13}\\e_{21}\\e_{22}\\e_{23}\\e_{31}\\e_{32}\\e_{33}\end{pmatrix}}}$

це, ${\displaystyle \mathbf {e} }$ представляє істотну матрицю у вигляді 9-мірного вектора, і цей вектор повинен бути ортогональним вектору ${\displaystyle {\tilde {\mathbf {y} }}}$.

Кожна пара відповідних точок зображення створює вектор ${\displaystyle {\tilde {\mathbf {y} }}}$ . Дано набір 3D-точок ${\displaystyle \mathbf {P} _{k}}$ що відповідає набору векторів ${\displaystyle {\tilde {\mathbf {y} }}_{k}}$, всі вони повинні задовольнити

${\displaystyle \mathbf {e} \cdot {\tilde {\mathbf {y} }}_{k}=0}$

для вектора ${\displaystyle \mathbf {e} }$ . Якщо надано достатньо (принаймні вісім) лінійно незалежних векторів ${\displaystyle {\tilde {\mathbf {y} }}_{k}}$ вектор ${\displaystyle \mathbf {e} }$ можна визначити вирішивши систему лінійних рівнянь. Запишемо усі вектори ${\displaystyle {\tilde {\mathbf {y} }}_{k}}$ як стовпці матриці ${\displaystyle \mathbf {Y} }$ і тоді:

${\displaystyle \mathbf {e} ^{T}\,\mathbf {Y} =\mathbf {0} }$

Це означає що ${\displaystyle \mathbf {e} }$ є рішенням системи лінійних однорідних рівнянь.

Стандартний підхід до вирішення цього рівняння передбачає, що ${\displaystyle \mathbf {e} }$ є лівим сингулярним вектором ${\displaystyle \mathbf {Y} }$ якому відповідає нульове сингулярне значення. За умови, що принаймні вісім лінійно незалежних векторів ${\displaystyle {\tilde {\mathbf {y} }}_{k}}$ використовуються для побудови ${\displaystyle \mathbf {Y} }$ випливає, що цей особливий вектор є унікальним і, отже, ${\displaystyle \mathbf {e} }$ і ${\displaystyle \mathbf {E} }$ можна визначити.

У випадку, коли для побудови ${\displaystyle \mathbf {Y} }$ використовується більше восьми відповідних точок не виключено, що вона не має жодного особливого значення, рівного нулю. Цей випадок трапляється на практиці, коли на координати зображення впливають різні типи шумів. Поширеним підходом до вирішення цієї задачі є використання методу найменших квадратів; знаходиться ${\displaystyle \mathbf {e} }$ що мінімізує

${\displaystyle \|\mathbf {e} ^{T}\,\mathbf {Y} \|}$

коли ${\displaystyle \|\mathbf {e} \|=1}$ . Роз'язок полягає у виборі ${\displaystyle \mathbf {e} }$ як лівого сингулярного вектора, що відповідає найменшому особливому значенню ${\displaystyle \mathbf {Y} }$. Переписавши цей вектор ${\displaystyle \mathbf {e} }$ знову як матрицю ${\displaystyle 3\times 3}$ отримаємо результат цього кроку, що далі позначено як ${\displaystyle \mathbf {E} _{\rm {est}}}$

Іншим наслідком роботи з шумними координатами зображень є те, що отримана матриця може не задовольняти внутрішнім обмеженням істотної матриці, тобто два її особливих значення є рівними і ненульовими, а інше дорівнює нулю. Залежно від імплементації, менші або більші відхилення від внутрішніх обмежень можуть бути, а можуть і не бути проблемою. Якщо критично важливо, щоб знайдена матриця задовольняла внутрішнім обмеженням, це може бути досягнуто шляхом пошуку матриці ${\displaystyle \mathbf {E} '}$ рангу 2, яка мінімізує

${\displaystyle \|\mathbf {E} '-\mathbf {E} _{\rm {est}}\|}$

де ${\displaystyle \mathbf {E} _{\rm {est}}}$ є матрицею отриманою на кроці 2 та використовується норма матриці Фробеніуса . Рохзвʼязок задається обчисленням сингулярного розкладу значення ${\displaystyle \mathbf {E} _{\rm {est}}}$ :

${\displaystyle \mathbf {E} _{\rm {est}}=\mathbf {U} \,\mathbf {S} \,\mathbf {V} ^{T}}$

де ${\displaystyle \mathbf {U} ,\mathbf {V} }$ є ортогональними матрицями та ${\displaystyle \mathbf {S} }$ є діагональною матрицею, яка містить особливі значення ${\displaystyle \mathbf {E} _{\rm {est}}}$ . В ідеальному випадку один з діагональних елементів ${\displaystyle \mathbf {S} }$ має бути нульовим або принаймні малим порівняно з двома іншими, які повинні бути однаковими. У будь-якому випадку вважаємо

${\displaystyle \mathbf {S} '={\begin{pmatrix}s_{1}&0&0\\0&s_{2}&0\\0&0&0\end{pmatrix}},}$

де ${\displaystyle s_{1},s_{2}}$ - найбільше та друге за величиною сингулярні значення ${\displaystyle \mathbf {S} }$ відповідно. Нарешті, ${\displaystyle \mathbf {E} '}$

${\displaystyle \mathbf {E} '=\mathbf {U} \,\mathbf {S} '\,\mathbf {V} ^{T}}$

Матриця ${\displaystyle \mathbf {E} '}$ є результуючою оцінкою істотної матриці, отриманою за допомогою алгорита.