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

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

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

Методи

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

Кожна з двох точок зображення y та має відповідну проекційну лінію, позначемо їх як та , які можна визначити враховуючи матриці камер . Нехай  — функція відстані між лінією L та точкою x така, що d(L, x) — евклідова відстань між L та x. Метод середньої точки знаходить точку , яка мінімізує

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

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

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

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

Нехай позначає рядок k матриці обертання :

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

або

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

Наведений розв'язок не є унікальним. Почавши із , можна отримати відповідно

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

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

Метод прямого лінійного перетворення (ПЛП) розв'язує задачу тріангуляції як однорідну систему лінійних рівнянь. Рівняння проєкції для камери з матрицею та відповідною точкою зображення має вигляд , де — шукана однорідна тривимірна точка, а знак означає рівність з точністю до невідомого масштабного множника. Узявши векторний добуток , цей множник виключають, і для кожної камери, на якій видно точку, отримують два незалежні лінійні рівняння відносно координат .Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. Cambridge University Press. ISBN 978-0-521-54051-3. Об'єднавши такі рівняння від усіх камер (двох і більше, в яких точку видно), формують перевизначену однорідну систему . За наявності шуму її наближеним розв'язком, з точністю до масштабу, є одиничний вектор, що мінімізує , тобто сингулярний вектор матриці , який відповідає найменшому сингулярному значенню; його знаходять за допомогою сингулярного розкладу (SVD).

Метод ПЛП простий у реалізації й природно узагальнюється на довільну кількість камер, однак мінімізована величина не має геометричного змісту й не відповідає похибці репроєкції. Тому його розв'язок часто використовують як початкове наближення, яке уточнюють мінімізацією похибки репроєкції: за моделі незміщеного гаусового шуму найімовірнішою є реконструкція, що мінімізує суму квадратів відстаней між виміряними точками зображень та їхніми репроєкціями, і такий результат оптимальний, якщо матриці камер відомі точно. Термін «пряме лінійне перетворення» використано в роботі Абдель-Азіза та Карари 1971 року, присвяченій близькодіапазонній фотограмметрії. Перевидання:

Джерела

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

Примітки