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

У Вікіпедії є статті про інші значення цього терміна: Тріангуляція.

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

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

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

Методи

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

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

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

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

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

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

Докладніше: Істотна матриця

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

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

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

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

${\displaystyle 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})}}}$

або

${\displaystyle 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} }}}$

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

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

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

${\displaystyle 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} }}}$

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

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

Докладніше: Пряме лінійне перетворення

Джерела

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

Див. також

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

Примітки

1. Richard I. Hartley. (PDF). COMPUTER VISION AND IMAGE UNDERSTANDING. Архів оригіналу (PDF) за 14 вересня 2021. Процитовано 14 вересня 2021.