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

Восьмиточковий алгоритм — це алгоритм, який використовується в комп'ютерному баченні для оцінки істотної матриці або фундаментальної матриці, що відповідає парі камер, за допомогою множини відповідних точок двох зображень. ^[en] запропонував цей алгоритм у випадку істотної матриці у 1981 році. Теоретично цей алгоритм може бути використано і для визначення фундаментальної матриці, але на практиці нормалізований восьмиточковий алгоритм, описаний Річардом Хартлі 1997 року, більше підходить для цього випадку.

Назва алгоритму походить від того факту, що він оцінює істотну матрицю або фундаментальну матрицю по множині з восьми (або більше) відповідних точок зображення. Однак варіації алгоритму можуть бути використані у випадку менш ніж на восьми точок.

Умова копланарності

Приклад епіполярної геометрії. Дві камери з відповідними центрами проєкційних точок O _L і O _R спостерігають точку P. Проєкція P на кожну з площин зображення позначається p _L і p _R. Точки E _L і E _R є епіполями.

Можна виразити епіполярну геометрію двох камер та точки простору за допомогою алгебраїчного рівняння. Зверніть увагу, незалежно від того де знаходиться точка ${\displaystyle P}$ у просторі, вектори ${\displaystyle {\overline {O_{L}P}}}$, ${\displaystyle {\overline {O_{R}P}}}$ і ${\displaystyle {\overline {O_{R}O_{L}}}}$ належать одній площині. Позначимо як ${\displaystyle X_{L}}$ координати точки ${\displaystyle P}$ у системі координат лівого ока та як ${\displaystyle X_{R}}$ координати точки ${\displaystyle P}$ у системі координат правого ока; позначимо як ${\displaystyle R,T}$ обертання та переміщення при переході між системами координат, тобто ${\displaystyle X_{R}=R(X_{L}-T)}$ - це співвідношення між координатами ${\displaystyle P}$ у двох системах координат. Наступне рівняння завжди виконується, оскільки вектор, отриманий як ${\displaystyle T\wedge X_{L}}$ є ортогональним до обох векторів ${\displaystyle T}$ і ${\displaystyle X_{L}}$ :

${\displaystyle X_{L}^{T}T\wedge X_{L}-T^{T}T\wedge X_{L}=(X_{L}-T)^{T}T\wedge X_{L}=0}$

Оскільки матриця обертання є ортогональною, тобто ${\displaystyle I=R^{T}R}$, ми отримуємо

${\displaystyle (X_{L}-T)^{T}R^{T}RT\wedge X_{L}=0}$ .

Замінивши ${\displaystyle (X_{L}-T)^{T}R^{T}}$ на ${\displaystyle X_{R}^{T}}$, ми отримуємо

${\displaystyle X_{R}^{T}RT\wedge X_{L}=X_{R}^{T}RSX_{L}=X_{R}^{T}EX_{L}=0}$

Зверніть увагу на те, що векторний добуток ${\displaystyle T\wedge }$ може розглядатися як множення вектора на матрицю; Символом ${\displaystyle S}$ було позначено цю матрицю. Добуток ${\displaystyle RT\wedge =RS}$ часто називають істотною матрицею і позначають ${\displaystyle E}$ .

Вектори ${\displaystyle {\overline {O_{L}p_{L}}},{\overline {O_{R}p_{R}}}}$ паралельні векторам ${\displaystyle {\overline {O_{L}P}},{\overline {O_{R}P}}}$ і тому обмеження копланарності виконується, якщо ми підставляємо ці вектори. Якщо ми позначимо як ${\displaystyle y,y'}$ координати проєкцій ${\displaystyle P}$ на площини лівого та правого зображення, тоді умова копланарності може бути записана як

${\displaystyle y'^{T}\mathbf {E} y=0}$

Базовий алгоритм

Далі описано базовий восьмиточковий алгоритм для оцінки істотної матриці ${\displaystyle \mathbf {E} }$ . Він складається з трьох кроків. Спочатку формулюється однорідне лінійне рівняння, де розв'язком є матриця ${\displaystyle \mathbf {E} }$, а потім розв’язується це рівняння, враховуючи, що воно може не мати точного розвʼязку. Нарешті, накладаються внутрішні обмеження результуючої матриці. Перший крок описаний у роботі Лонгет-Гіггінса, другий і третій кроки є стандартними підходами в теорії оцінки.

Умова компланарності накладена суттєвою матрицею ${\displaystyle \mathbf {E} }$:

${\displaystyle (\mathbf {y} ')^{T}\,\mathbf {E} \,\mathbf {y} =0}$

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

Крок 1: Формулювання однорідного лінійного рівняння

Запишемо

${\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} }$ є рішенням системи лінійних однорідних рівнянь.

Крок 2: Розв’язок рівняння

Стандартний підхід до вирішення цього рівняння передбачає, що ${\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}}}$

Крок 3: Накладення внутрішніх обмежень

Іншим наслідком роботи з шумними координатами зображень є те, що отримана матриця може не задовольняти внутрішнім обмеженням істотної матриці, тобто два її особливих значення є рівними і ненульовими, а інше дорівнює нулю. Залежно від імплементації, менші або більші відхилення від внутрішніх обмежень можуть бути, а можуть і не бути проблемою. Якщо критично важливо, щоб знайдена матриця задовольняла внутрішнім обмеженням, це може бути досягнуто шляхом пошуку матриці ${\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} '}$ є результуючою оцінкою істотної матриці, отриманою за допомогою алгорита.

Реалізації

Восьмиточковий алгоритм реалізовано в бібліотеці OpenCV, де йому відповідає функція cv::findFundamentalMat [ 4 березня 2021 у Wayback Machine.], яка викликається із параметром cv::FM_8POINT.

Див. також

• Фундаментальна матриця
• Епіполярна геометрія
• Істотна матриця
• Трифокальний тензор

Посилання

• Richard I. Hartley (June 1997). In Defense of the Eight-Point Algorithm. IEEE Transactions on Pattern Recognition and Machine Intelligence. 19 (6): 580—593. doi:10.1109/34.601246.

• Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. Cambridge University Press. ISBN .

• H. Christopher Longuet-Higgins (September 1981). A computer algorithm for reconstructing a scene from two projections. Nature. 293 (5828): 133—135. doi:10.1038/293133a0.