Structure from motion


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

Перед прочитанням цієї статті не завадить уважно прочитати статтю «Основи стереозору».

Отже, перед нами стоїть завдання перетворення послідовності двовимірних зображень в тривимірну структуру. Завдання це не проста, і потрібно її спрощувати.
По-перше, припустимо, що кадру у нас лише два. Позначимо їх як A і B.
По-друге, будемо працювати з кінцевим безліччю точок, відповідних один одному на кадрах A і B. Точки на зображенні позначимо як . Тоді точки на кадрах A і B будуть . Кожна пара точок відповідає точці в тривимірному просторі .

Тепер необхідно визначитися як шукати . Для цього на першому кадрі виберемо точки, з найбільшою контрастністю — «особливі» точки (features). Для цього можна використовувати surf, fast або що-небудь інше. Ці точки і будуть . Потім необхідно знайти відповідності цим точкам на другому кадрі за допомогою того ж алгоритму surf або оптичного потоку. А це вже точки .

А тепер ми підійшли до центрального питання цієї статті: як з точок (точок-відповідностей, point correspondences) отримати координати точок та положення камери в просторі? Спочатку необхідно розібратися з тим, як же точка вона потрапляє на зображення. Потрібно побудувати математичну модель камери.

Модель проективної камери
Так як ви, ймовірно, вже прочитали статтю «Основи стереозору», ця формула повинна бути знайома:
.
Або якщо описати більш повно:
.
Тут X — це тривимірна точка в просторі.
x — координата точки на зображенні однорідних координатах , тобто переведення в звичайні координати зображення буде таким: .
Процес перекладу точки в просторі координати зображення можна розбити на два етапи, які реалізуються двома матрицями у формулою:
  1. [R|t] — R і t являють собою положення камери в просторі. На цьому етапі координати точок переводяться в локальні координати камери. R — матриця повороту розміром 3x3, t — тривимірний вектор зміщення — разом вони складають матрицю переходу [R|t] (розміром 3x4), вона визначає положення камери в кадрі. [R|t] — це те ж, що і видова матриця в тривимірній графіці (якщо не брати в розрахунок, що вона має розмір не 4x4).
    — це матриця повороту камери, — тривимірні координати точки розташування камери в просторі. R і t називають зовнішніми параметрами камери.
  2. K — матриця камери. Локальні координати точок переводяться в однорідні координати зображення. fx, fy — фокальна відстань у пікселях, cx, cy — оптичний центр камери (зазвичай це координати центру зображення). Ці параметри називають внутрішніми параметрами камери.
Важливою властивістю цієї моделі є те, що точки лежать на одній прямій у просторі будуть лежати на одній прямій на зображенні.
Насправді, описувана модель може бути дуже неточною. У реальних камерах вступають в гру лінзові спотворення, з-за яких прямі лінії стають кривими. Це спотворення називаються дисторсией. Існують різні моделі, виправляють ці спотворення. Тут є деякі їх реалізації. Параметри цієї моделі також входить в поняття внутрішніх параметрів камери.
З урахуванням деформації наша формула ускладнюється:
, де D(X) — функція, що приймає однорідні координати точок зображення і повертає звичайні координати на зображенні. Також пізніше нам знадобиться зворотна функція — InvD(ix).
Внутрішні параметри камери повинні бути відомі заздалегідь. З'ясування цих параметрів — це окрема тема, будемо вважати, що вони вже є.

Спотворення дисторсії не залежить від глибини видимих точок, а тільки координат на зображенні. А значить «виправити» зображення (отримавши прямі лінії там, де вони і повинні бути) можна не знаючи зовнішніх параметрів камери і координат точок у просторі. Далі тоді можна використовувати модель камери без функції D.

Зображення з дісторсиєю ліворуч, і праворуч — «виправлене» від лінзових спотворень зображення. Видно, що лінії стали прямими.

Нормалізація точок
Ми домовилися, що внутрішні параметри нам відомі, відомі і координати точок на зображенні, а значить, залишається знайти [R|t] і Xі (положення камери і точок у просторі).
Наша формула виходить вже трохи складною, її треба спрощувати. Для початку зробимо так:

Вираз залишається справедливим. Продовжимо:

Позначимо (а якщо без об'єктива, то ). Так як всі параметри відомі, nxі можна порахувати заздалегідь. Згадавши як виглядає матриця K, можна зрозуміти, що nxz = 1. Це допоможе при подальших розрахунках. В результаті формула стає простіше:


nxі — це нормалізовані точки зображення.

Фундаментальна та сутнісна матриці
Отже, припустимо, у нас є два зображення, отримані від однієї камери. Нам невідомі положення камер і координати точок у просторі. Домовимося ввести розрахунки щодо першого кадру. Так виходить, що RA = I (I — одинична матриця), tA = (0, 0, 0). Положення камери в кадрі B позначимо просто як R і t (тобто RB = R, tB = t). [R|t] — це матриця координат другого кадру, і воно ж — матриця зміщення положення камери від кадру A до кадру B. У підсумку маємо отримуємо таку систему (без врахування дисторсії!):

Використовуючи фундаментальну матрицю F (fubdamental matrix), отримаємо таке рівняння:

Також зауважимо, що F має розмір 3х3 і повинна мати ранг рівний 2.
З фундаментальної матриці F вже можна отримати необхідні нам R і t. Однак дисторсія все псує, з урахуванням її залежність точок між кадрами буде нелінійна, і це вже не буде працювати.
Але перейдемо до нормалізованим точках і використовуємо сутнісну матрицю E (essential matrix). Все буде майже тим же, але простіше:
— система рівнянь для сутнісної матриці;
— рівняння для неї ж.
А тут ми можемо спокійно брати в розрахунок дисторсію.
Фундаментальна та сутнісна матриці пов'язані таким чином:

Тепер перед нами постала задача знаходження або фундаментальної матриці F, або сутнісної матриці E, з якої пізніше зможемо отримати на R і t.

Обчислення сутнісної матриці (8-мі точковий алгоритм)
Повернемося до рівняння:

Цю ж формулу можна переписати в такому вигляді (згадуємо, що ):
, тут вказано параметр i заради зручності, але маємо на увазі, що це справедливо для кожної точки.
Введемо вектор e і матрицю M:


Тоді всю систему рівнянь можна представити у вигляді:

Отримуємо однорідну систему рівнянь, розв'язавши яку, отримаємо E з е. Очевидним рішенням тут є нульовий вектор, але нас явно цікавить не він. Для рішення необхідно мінімум 8 точок.

Розв'язок систем однорідних рівнянь за допомогою сингулярного розкладання
Сингулярне розкладання — це декомпозиція матриці, приводить її до такого виду:
, де U, V — ортогональні матриці, W — діагональна матриця. При цьому діагональні елементи матриці W прийнято розташовувати в порядку убування. Також ранг матриці W — це і ранг матриці M. А так як W — діагональна матриця, то її ранг — це кількість ненульових діагональних елементів.

Отже, було дано рівняння виду:
, де M — відома матриця, e — вектор, який необхідно знайти.

Рядки VT, яким відповідає нульовий діагональний елемент W на цьому ж рядку, є нуль-просторами матриці M, тобто в даному випадку є лінійно-незалежними рішеннями нашої системи. А так як елементи W розташовуються в порядку убування, то потрібно дивитися останній елемент матриці W. І рішенням буде останній рядок .
При розрахунку сутнісної матриці, використовуючи 8 точок, останній елемент матриці W повинен бути дорівнює нулю — W99=0, але на практиці, внаслідок помилок, там буде будь-яке ненульове значення, і за величиною цього значення можна оцінити величину цієї помилки. При цьому ми отримаємо найкращі рішення.
Тим не менш, знайдене нами рішення — не єдине, більше того, рішень буде нескінченно багато. Якщо помножити знайдене рішення на який-небудь коефіцієнт, воно все-одно залишиться рішенням. Таким чином в рівнянні сховався коефіцієнт s (який може бути будь-яким):
.
Щоправда, всі ці рішення будуть лінійно залежними, а цікавити нас лише одне з них.
Звідси і матриця E може масштабуватися. Ось тільки розрахунки ведуться в однорідному просторі і, як наслідок, від масштабування (тобто від коефіцієнта s) не залежать.
Напевно, варто масштабувати отриману матрицю E так, щоб E33 = 1.

Обчислення сутнісної матриці (7-мі точковий алгоритм)
Можна обійтися і 7-ма точками.
Якщо ми візьмемо тільки 7 точок, то M буде матрицею розміром 7x9.
Повернемося до висловом:

W — буде також матрицею розміром 9x9, як і раніше, але тепер не тільки W99 дорівнюватиме нулю (ну знову ж таки без урахування помилок обчислень), але і W88. Це означає, що маємо два лінійно-незалежних рішення рівняння . З них отримаємо дві матриці E1 E2. Рішенням буде вираз .
Сутнісна матриця, як і фундаментальна, повинна мати ранг рівний двом, а так як вона маємо розмір 3x3, то значить визначник матриці дорівнює 0 — . Отже . Якщо розписати це рівняння, то отримаємо кубічне рівняння, що має 1 або 3 рішення . А значить отримаємо одну або три матриці E.
Розписувати рішення цього рівняння я не буду (воно об'ємне, ну і вважайте це домашнім завданням). В крайньому випадку можете просто подивитися відразу реалізацію в opencv.

Уточнення сутнісної (фундаментальної) матриці
Так як все в цьому світі недосконале, то ми будемо постійно отримувати помилки, з якими нам необхідно боротися. Так сутнісна матриця повинна мати ранг рівний 2 і отже . На практиці, однак, це буде не так.
Щоб побачити в чому це виражається, візьмемо фундаментальну матрицю. Сутнісна матриця / фундаментальна матриця — різниця лише в тому, з якими точками ми працюємо (нормализованными або крапками на зображенні).
Промінь, випущений з точки кадру A, ляже в кадр B як пряма лінія (або не зовсім з-за деформації, але забудемо про неї). Припустимо матриця F — це фундаментальна матриця кадрів A і B ().
Тоді якщо випустити промінь з точки , то отримаємо пряму l на кадрі B — . Ця пряма називається эпиполярной лінією, тобто , де ix, iy — координати точки на зображенні. І те ж умова для точки на зображенні з однорідними координатами — . Точка буде лежати на цій прямій, тому . Звідси і виходить загальна формула — .

На картинці зображено приклад эпиполярных ліній, отриманих з правильної фундаментальної матриці (ранг якої дорівнює 2, картинка праворуч) і неправильною (ліворуч).
Щоб отримати правильну фундаментальну матрицю, скористаємося властивістю сингулярного розкладання — наближати матрицю до заданого рангу:
. В ідеалі W33 (останній елемент діагоналі) повинен бути рівний нулю. Введемо нову матрицю W', яка дорівнює W, тільки у якої елемент W'33 = 0.
Тоді виправлений варіант: .
Рівно той же принцип працює і для сутнісної матриці.

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

А матриці TA, B мають вигляд: , де c — середня координата точок кадрів, s — коефіцієнт масштабу.
Після цього обчислюємо сутнісну матрицю як зазвичай. Після необхідно її уточнити, як було описано вище. Позначимо отриману матрицю як Et.
Підсумкова сутнісна матриця — .
У результаті:
Знову ж таки, якщо необхідно знайти фундаментальну матрицю, всі принципи зберігаються.

Отримання положення камери з сутнісної матриці
Введемо матрицю H:
Використовуємо сингулярне розкладання на сутнісної матриці:
Тоді отримуємо такі рішення:



, де — координати положення камери.
Нам же необхідно положення камери в локальних координатах самої камери: .
Виходить чотири рішення: .
У разі 8-ми точкового алгоритму, вибираємо з 4-ьох рішень. У випадку 7-ми точкового алгоритму, вийде три сутнісні матриці, з яких вийде 12 рішень. Вибрати треба тільки одне, те, яке буде давати менше помилок.

Вироджені випадки
Знову повернемося до обчислення сутнісної матриці. У нас було рівняння:

Далі ми його вирішували за допомогою сингулярного розкладання:

Рішення цього рівняння залежить від рангу матриці W, ну або від кількості нулів в діагоналі цієї матриці (ми ж пам'ятаємо, що це відображає ранг матриці). Ось тільки з урахуванням похибки, вважаємо нулем в даному випадку число, досить близьке до нуля.
Маємо такі варіанти:
  • Нулів немає. Немає рішень, ймовірно помилка вийшла занадто великий.
  • Один нуль. Одне рішення, випадок при якому число точок більше, або дорівнює восьми.
  • Два нуля. Одне чи три рішення. Використовувалося сім або більше точок.
  • Три нуля. Тоді має бути вірно умова . Таке можливо, якщо камера не зсувалася від кадру до кадру, був тільки поворот, тобто t = (0, 0, 0). Або всі точки лежать на одній площині. У другому випадку ще є можливість знайти координати цих точок і положення камери, але вже іншими способами.


Обчислення координат точок у просторі
Припустимо зараз у нас є більше, ніж два кадри — A, B, C,…
— положення камер кадрів A, B, C,…
— нормалізовані точки
Необхідно знайти точку

Уявімо цю систему так:


У матричному вигляді:


З допомогою сингулярного розкладання знаходимо вектор , який (способом, описаному вище). Тоді , де s — якийсь невідомий коефіцієнт. Виходить .

Оціночна функція
Оціночні функції (cost functions) необхідні, щоб отримавши якісь результати, оцінити наскільки достовірними вони є, або порівняти їх з іншими.
Візьмемо нашу модель:
— передбачуваний результат.
— реальне значення точки.
Звідси квадрат помилки для i-ої точки буде: .
На практиці одні точки будуть давати більш достовірні результати, ніж інші. А деякі взагалі явно будуть давати неправильні. В результаті виникає необхідність вибрати з загального масиву точок тільки ті точки, яким можна довіряти, а решта просто викинути розрахунків.
Найпростіший спосіб вибрати «достовірні» точки — вибрати якийсь ліміт (наприклад, 5 пікселів), та брати тільки ті точки, які дають помилку менше цього ліміту (). Тут же слід зазначити, що необхідно враховувати, що точка має лежати перед камерою в обох кадрах, інакше її явно необхідно відкинути.
Таким чином, можна ввести оціночну функцію — кількість достовірних точок. І при порівнянні, вибирати той результат, який дає більшу кількість «достовірних» точок.
А можна скористатися іншим, більш «тонкої» функцією:
, де limit — це обраний нами ліміт (5 пікселів).
Кращим буде той варіант, який буде давати менше значення. Зрозуміло, що і тут слід прибирати «недостовірні» точки для майбутніх розрахунків.

Метод RANSAC
  1. При обчисленні сутнісної матриці необхідно відкидати «недостовірні» точки, так як вони призводять до суттєвих помилок в розрахунках. Визначити набір відповідних точок можна за допомогою алгоритму RANSAC.
    Повторюємо цикл задану кількість разів (наприклад, 100, 400):
    • Вибираємо випадковим чином мінімальний набір точок для розрахунків (у нас це 7);
    • Обчислюємо сутнісні матриці з цього набору (нагадую, може вийде або одна матриця, або три)

    • Оціночної функцією обчислюємо вірогідність кожної матриці
  2. З попереднього циклу вибираємо сутнісну матрицю, яка дає кращий результат;
  3. Вибираємо точки для розрахунків, які дають помилку при отриманої сутнісної матриці помилку менше заданого порогу;
  4. З отриманого набору точок обчислюємо загальну сутнісну матрицю.


Загальний алгоритм
  1. Знаходимо «особливі» точки на першому кадрі
  2. Визначаємо точки-відповідності між двома зображеннями.
  3. Знаходимо сутнісну (чи все-ж фундаментальну) матрицю, що відповідає цим двом зображень за допомогою RANSAC.
  4. У нас буде одне або три рішення, з яких отримаємо 4 або 12 можливих матриць [R|t]. Маючи положення камер в обох кадрах, розраховуємо координати точок у просторі для кожної можливої матриці. З них вибираємо кращу, використовуючи оцінну функцію.


Що далі?
Спочатку ми виходили з припущення, що кадру у нас було всього два.
Щоб працювати з послідовністю кадрів, потрібно просто розбити послідовність на послідовні пари кадрів. Обробляючи пари кадрів, ми отримуємо зміщення камери від одного кадру до іншого. З цього можна отримати координати положення камери в інших кадрах.

Отримавши головне — положення камер, можна діяти по-різному:
  • По точках-відповідностям отримати тривимірні координати точок у просторі, вийде хмара точок, яку можна перетворити в тривимірну модель
  • Використовувати фундаментальну матрицю для розрахунку карти глибини.
  • За допомогою двох кадрів ініціалізувати карту для SLAM, використовуючи розраховані координати точок у просторі, можна простіше і швидше отримати координати положення в наступних кадрах.
  • ну і інше
Загалом, можна діяти по-різному, застосовуючи різні методи, в тому числі і ті алгоритми, які були описані — не єдині.

Література
Fundamental matrix, Essential matrix, Eight-point algorithm — більше інформації у вікіпедії
Hartley, Zisserman — Multiple View Geometry in Computer Vision — спонсор цієї статті
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.