Сканування LiDAR: Перетворення лазерних відбитків у карту

Визначення часу польоту світла

Лідар (Light Detection and Ranging) вимірює відстань, тимлючи час повернення лазерного імпульсу до поверхні та назад. Оскільки світло подорожує приблизно зі швидкістю 3×10⁸ м/с, електроніка таймінгу потребує точності на пікосекунди для розрізнення відстаней у сантиметри – час повернення до стіни на відстані 15 метрів становить лише близько 100 наносекунд. Обертальна 2D система постійно обертає цю систему вимірювання, створюючи тисячі імпульсів за секунду під трохи різними кутами, і кожен повернутий діапазон у поєднанні з кутом запуску стає однією точкою в скануванні 360°.

distance = c · t_roundtrip / 2

c = speed of light ≈ 3×10⁸ m/s
t_roundtrip = time between pulse emission and detected return

Ray marching і точковий хід

У симуляційному або програмному забезпеченні LiDAR, фізичне вимірювання часу замінюється геометрією: кожен промінь (або аналітично пересікається) віддаляється від датчика доти, поки не зустріне найближчий об'єкт, точно відтворюючи те, що повідомляє про повернення реального променя. Координата кінця кожного променя — конвертована з місцевих полярних координат (кут, дальність) датчика у декартові координати світу за допомогою положення та напрямку датчика — стає однією точкою в хмарці точок, необробленим розсипом зразків поверхні без явного зв’язку між ними.

Від точок до сітки: карта зайнятості

Одиночна хмара точок є шумною та розрідженою — справжні сенсори можуть помилятися, відбиватися від скла або фіксувати рухому перешкоду. Роботи ж накопичують скани в карту зайнятості: середовище розділене на невеликі комірки, кожна з яких містить переконання про те, чи вона вільна чи зайнята. Один промінь надає двох видів доказів одночасно — його кінець є ймовірним об’єктом зайнятості, а кожна комірка, через яку він пройшов у дорозі туди, за визначенням, була достатньо вільна для того, щоб промінь досягнув кінця, отже ці комірки є доказом вільного простору.

Лог-шанси: об’єднання доказів дешево

Об’єднання повторних, незалежних, шумливих спостережень однієї клітинки з використанням теореми Байєса прямо означає множення ймовірностей — це математично незручно та повільно. Стандартна техніка, яка використовується практично в кожній системі картографування від початкового планування Ельфа (1989), полягає у відстеженні лог-шансу кожної клітинки, оскільки оновлення Байєса в просторі лог-шансів спрощується до простого додавання:

l(клітинка) = log( p(зайнята) / (1 − p(зайнята)))

на промені, що проходить через клітинку з вільною областю: l += l_free (l_free < 0)

коли промінь закінчується (попадає) в кінцеву клітинку: l += l_hit (l_hit > 0)

відновити ймовірність будь-коли: p = 1 / (1 + e^(−l))

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

l(cell) = log( p(occupied) / (1 − p(occupied)) )

on a ray passing through a free cell:      l += l_free    (l_free < 0)
on a ray ending (hit) at the endpoint cell: l += l_hit     (l_hit > 0)

recover probability any time: p = 1 / (1 + e^(−l))

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте LiDAR Scanning і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.