Тріангуляція (комп'ютерний зір)

У задачах комп'ютерного зору тріангуляція — процес визначення точки в тривимірному просторі за її проєкціями на двох або більше зображеннях. Для вирішення цієї задачі необхідно знати параметри функції проєкції камери з 3D в 2D, у найпростішому випадку представленою матрицею камери. Тріангуляцію іноді називають реконструкцією.

Задача тріангуляції в теорії тривіальна. Кожній точці зображення відповідає пряма в тривимірному просторі, всі точки, що лежать на цій прямій проєктуються в одну й ту саму точку на зображенні. Якщо можна знайти пару відповідних точок на двох або більше зображеннях, які є проєкціями точки x у тривимірному просторі, набір ліній, утворених точками зображень мають перетинатися в точці x, а алгебраїчне значення координат точки x можна розрахувати багатьма шляхами.

На практиці, однак, координати точки зображення не можна визначити з великою точністю. Різні типи спотворень, такі як геометрична дисторсія об'єктиву, шум або помилка визначення положення локальних ознак, призводять до неточності визначення координат відповідних точок зображень. Як наслідок, лінії, утворені відповідними точками не завжди перетинаються в тривимірному просторі. Задачею тоді стає знаходження координат тривимірної точки яка оптимально проєктується в точки на зображеннях. У літературі є кілька пропозицій щодо визначення оптимальності і методів знаходження оптимальної точки. Оскільки вони ґрунтуються на різних критеріях оптимальності, різні методи дають різні оцінки тривимірної точки x у випадках наявності спотворень і шуму.

Методи

Метод середньої точки

Кожна з двох точок зображення y $\mathbf {y} '_{1}$ та $\mathbf {y} '_{2}$ має відповідну проекційну лінію, позначемо їх як $\mathbf {L} '_{1}$ та $\mathbf {L} '_{2}$, які можна визначити враховуючи матриці камер $\mathbf {C} _{1},\mathbf {C} _{2}$. Нехай $d\,$ — функція відстані між лінією L та точкою x така, що d(L, x) — евклідова відстань між L та x. Метод середньої точки знаходить точку $x_{est}$, яка мінімізує

$(L'_{1},x)^{2}+d(L'_{2},x)^{2}$

Виявляється, перетин $x_{est}$ лежить точно в середині найкоротшого відрізка, який з'єднує дві проєкційні лінії.

Річард І. Хартлі та Пітер Штурм у своїй статті «Тріангуляция» відзначають, що цей метод не є ані афінним ані проективним інваріантом, оскільки такі поняття як перпендикуляр та середня точка не є афінними концепціями. Цей метод відзначено як найгірший з усіх розглянутих у цій статті.

За допомогою істотної матриці

Задачею, яку потрібно вирішити, є обчислення тривимірних координат у просторі $(x_{1},x_{2},x_{3})$ з відповідних нормованих координат зображення $(y_{1},y_{2})$ та $(y'_{1},y'_{2})$. Якщо істотна матриця відома й були визначені відповідні перетворення повороту та зсуву, можна використати алгоритм описаний у роботі Лонгуе-Гіггінса.

Нехай $\mathbf {r} _{k}$ позначає рядок k матриці обертання $\mathbf {R}$:

$\mathbf {R} ={\begin{pmatrix}-\mathbf {r} _{1}-\\-\mathbf {r} _{2}-\\-\mathbf {r} _{3}-\end{pmatrix}}$

Поєднуючи наведені вище співвідношення між тривимірними координатами в двох системах координат та проєкцією 3D точок на 2D зображення

$y'_{1}={\frac {x'_{1}}{x'_{3}}}={\frac {\mathbf {r} _{1}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}{\mathbf {r} _{3}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}}={\frac {\mathbf {r} _{1}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}{\mathbf {r} _{3}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}}$

або

$x_{3}={\frac {(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {y} }}$

Після знаходження $x_{3}$ дві інші координати можуть буди знайдені як

${\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=x_{3}{\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}$

Наведений розв'язок не є унікальним. Почавши із $y'_{2}$, можна отримати $x_{3}$ відповідно

$x_{3}={\frac {(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {y} }}$

В ідеальному випадку, коли камера відповідає ідеальній камері-обскурі, а шум відсутній і точки можуть бути визначені точно, ці два значення для $x_{3}$ співпадатимуть. На практиці, однак, це не завжди так, і може бути корисним об'єднати значення $x_{3}$, наприклад, як середнє арифметичне.

Джерела

• Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. Cambridge University Press. ISBN 978-0-521-54051-3.

Див. також

• Перетин прямих
• Істотна матриця
• Пряме лінійне перетворення
• Налаштування пучка