Плоское зеркало для лидара: от двумерной комнаты к трёхмерной сцене

в 15:07, , рубрики: c++, Embree, Алгоритмы, воксели, зеркало, оптимизация, покрытие, трассировка лучей

Лидар видит только то, куда доходит луч. Поле зрения конечно, а стена закрывает пространство за собой. Второй сенсор закрывает часть таких зон, но занимает место, питание и отдельный канал. Плоское зеркало лучей не добавляет: оно разворачивает уже испущенные.

На плоской сцене один лидар и одно зеркало-отрезок. Свободны три числа: две координаты центра и угол. Подбор ставит зеркало так, что часть лучей уходит в половину комнаты вне поля зрения. Та же задача в трёх измерениях — треугольный меш, несколько лидаров и прямоугольных зеркал, часть приборов едет вместе с носителем. Ниже числа плоского расчёта и схема объёмного: поверхностные воксели, Intel Embree на процессоре, Vulkan на видеокарте.

Плоская модель

Сцена — набор отрезков. Луч из точки mathbf{O} в направлении mathbf{d} пересекает отрезок, если оба параметра решения лежат в нужном диапазоне: вдоль луча — в пределах дальности, вдоль отрезка — между его концами. Все лучи проверяются против всех отрезков сразу. Ближайшее пересечение — минимум по дистанции.

Зеркало — отрезок фиксированной длины. Нормаль получается поворотом направления отрезка на 90°. Отражённое направление

mathbf{d}'=mathbf{d} - 2(mathbf{d}cdotmathbf{n}),mathbf{n}.

Если зеркало ближе препятствия, из точки попадания выпускается новый луч. Иначе записывается прямое попадание.

Свободны три параметра: центр и угол. Угол берётся на полуинтервале [0, pi): отрезок симметричен, поворот на 180° даёт то же зеркало. Длина в опыте ниже равна 3 м. Положение, где зеркало пересекает стену или накрывает сенсор, отбрасывается.

Поиск идёт в два шага. Сначала равномерная сетка по центру и углу. Затем несколько лучших узлов уточняет симплекс Нелдера–Мида из SciPy. Спускаться по градиенту здесь почти некуда: попадание в ячейку скачком меняет оценку, а между скачками она постоянна. Для трёх параметров и сотен узлов сетки этого хватает.

Чем измеряется скан

Оптимизатору нужна одна величина. Четыре слагаемых отвечают разным дефектам.

Метрика

Что считает

Лучше, когда

p

доля угловых секторов с хотя бы одним попаданием

больше

A_{mathrm{blind}}

число ячеек без единой точки попадания

меньше

U

равномерность промежутков между углами попаданий

больше

G

занятые ячейки с зеркалом, делённые на занятые ячейки без него

больше

G нормируется и насыщается, когда зеркало добавляет половину новых ячеек. Дальнейший рост не перетягивает оценку на себя. Составная оценка прототипа:

Phi=0{,}3,(0{,}25,p + 0{,}15,U + 0{,}60,G_{mathrm{norm}}) + 0{,}7left(1 - frac{A_{mathrm{blind}}}{N}right),G_{mathrm{norm}}=minleft(1, frac{G - 1}{0{,}5}right).

Больший вес стоит на доле пустых ячеек. На сцене ниже этот член почти не двигается: метрика смотрит не на ту величину.

Комната с перегородкой

Комната 16times 16 м. Перегородка стоит на линии x=0, проём высотой 3 м симметричен относительно начала координат. Лидар в точке (-4, 0): 360 лучей в секторе 180°, сектор смотрит в сторону +x, дальность 20 м. Левая стена для него вне поля зрения.

Сетка метрик шире комнаты. Границы сцены — квадрат от -9 до 9 м, ячейка 0{,}25 м, всего N=5184 ячейки. Угловых секторов 72, на полный круг.

Сравнение скана без зеркала и с подобранным зеркалом

Комната с перегородкой: прямой скан, скан с зеркалом, ход оценки

Рис. 1. Слева — только прямые лучи. По центру — подобранное зеркало: янтарная черта и стрелка нормали, зелёные точки — попадания после отражения. Справа — лучшая оценка по ходу поиска. Подписи на рисунке округлены.

Без зеркала

С зеркалом

Угловое покрытие p

0,500

0,708

Ячеек без попадания

5064

5040

Равномерность U

0

0

Выигрыш зеркала G

1,000

1,655

Оценка Phi

0,054

0,253

Зеркало легло отрезком от (-3{,}64; -3{,}57) до (-1{,}26; -1{,}75): в видимой половине, нормаль смотрит в сторону левой стены. Сетка 10times 10times 8 и симплекс вместе сделали 2773 оценки за 1,7 с. Основной подъём даёт сетка, до 0,250. Симплекс добавляет около 0,003: рядом с удачной ячейкой ландшафт уже плоский.

Подробный скан с подобранным зеркалом

Лучи прямого скана и лучи после отражения

Рис. 2. Те же лучи крупнее. Синие попадания остаются на перегородке и правой стене. Зелёные — на левой, куда прямой сектор не смотрит.

Рост Phi с 0,054 до 0,253 не стоит читать как «в несколько раз лучше». База близка к нулю, и относительная цифра раздувается. Сдвинулись два понятных члена. Угловое покрытие выросло с 36 секторов из 72 до 51: зеркало заняло ещё 15 секторов за пределами исходного полукруга. Выигрыш G=1{,}66 значит, что ячеек с точкой попадания стало примерно на две трети больше. Нормированный выигрыш при этом уже насыщен: добавка больше 50 % новых ячеек дальше G_{mathrm{norm}} не увеличивает.

Два члена не сдвинулись, и оба показывают, что менять в трёхмерной метрике.

Равномерность осталась нулём. Промежутки считаются по полному кругу. Сектор 180° оставляет пустую дугу около pi, разброс большой, формула обрезается нулём и улучшения внутри сектора не видит. В объёмной постановке секторы вне заявленного поля зрения в равномерность не входят.

Пустых ячеек было 5064, стало 5040, из 5184. Попадания — точки на стенах. Ячейка 0{,}25 м в комнате и в метровом поле вокруг неё почти всегда пуста, даже если стена уже видна. Семь десятых веса Phi стоят на величине, которая здесь плохо отличает увиденную стену от неувиденной. Считать надо площадь наблюдаемой поверхности.

Что в объёме устроено иначе

Отрезки становятся треугольным мешем. Попарная проверка луч–отрезок на десятках граней ещё терпима. На сотнях тысяч треугольников ближайшее пересечение ищет иерархия ограничивающих объёмов.

Одно зеркало в объёме — уже не три числа. Центр даёт три координаты, ориентация прямоугольника — ещё два или три угла. Восемь узлов на каждую ось при пяти параметрах — 8^5=32,768 трассировок, и это один прибор в одном кадре. Несколько лидаров, несколько зеркал и точки траектории делают полную сетку непригодной. Грубая фаза строит короткий каталог, а не решётку.

Приборы двух типов. Неподвижный задаётся позой в сцене. Закреплённый на носителе — лидар на крыше, штатное боковое зеркало — задаётся позой относительно кузова и в мире едет вместе с ним. Ищется одна поза в системе носителя, оценивается она во всех выбранных положениях вдоль пути. Элемент поверхности увиден, если до него дошёл хотя бы один засчитанный луч хотя бы в одной точке пути. Рядом хранится покрытие в отдельных точках: схема, хорошая в среднем, не должна оставлять провал на конкретном участке.

Свободны только те позы, которые разрешено менять. Размеры зеркал заданы заранее. Если сенсоры уже стоят, подбираются зеркала. Если зеркала заданы кузовом, подбираются сенсоры. Если свободно и то и другое, они ищутся вместе: куда уйдёт отражённый луч, зависит от того, куда смотрит лидар.

Трёхмерный запрос

Сцена — треугольный меш. Если носитель сам закрывает лучи, его геометрия входит в тот же меш и движется вместе с закреплёнными приборами. Файл читает Assimp: в расчёт попадают треугольники.

Лидар задаётся позицией, ориентацией, диаграммой направлений в своей системе, масштабом углов этой диаграммы и максимальной дальностью. Диаграмма — равномерная сетка по горизонтали и вертикали. Нулевой вертикальный угол оставляет один плоский веер, тот же случай, что в плоском расчёте. Масштаб углов и дальность входят в ту же позу поиска: их можно менять отдельно или вместе с положением. Плоский опыт уже показал, что одного положения зеркала достаточно, чтобы открыть половину комнаты вне сектора.

Зеркало — прямоугольник: центр, ориентация, ширина и высота. Ориентация строит репер. Две оси лежат в плоскости, третья — нормаль. Луч отражается только от лицевой стороны и только внутри прямоугольника. С тыльной стороны он останавливается. Направление после удара то же, что на плоскости. Новый отрезок начинается чуть впереди точки попадания, иначе луч сразу попадает в то же зеркало. Пройденный путь вычитается из дальности: бюджет один на всю цепочку. Число отражений ограничено. Одного хватает, когда на пути одно зеркало. Предел больше единицы нужен, если луч идёт от одного зеркала к другому.

Попадание в поверхность засчитывается, если путь не длиннее дальности и косинус угла падения не ниже порога. Порог отсекает скользящие лучи: они плохо детализируют элемент.

Наблюдаемость относится к поверхности. Область интереса режется на воксели, в расчёт входят те, через которые проходит меш. У каждого хранится площадь поверхности внутри него. Воксель наблюдаем, если в него пришёл хотя бы один засчитанный луч, прямой или отражённый. Слепая зона — сумма площадей остальных. Пустой воздух в знаменатель не входит. Сетка дискретизирует оценку, а не шаг луча: точку на треугольнике уже даёт пересечение, обходить пустые ячейки вдоль луча незачем.

Оценка снова одна:

Phi=w_C C + w_U U + w_G G_{mathrm{norm}} + w_Aleft(1 - frac{A_{mathrm{blind}}}{A_{Sigma}}right).

C — доля наблюдаемых поверхностных вокселей, {A_{Sigma}} — площадь всех целевых вокселей, G — отношение наблюдаемой площади с зеркалами к площади прямого скана. Нормировка G та же, насыщение на добавке в 50 %. Веса неотрицательны и в сумме дают единицу. В постановке w_C=0{,}25, w_U=0{,}15, w_G=0{,}35, w_A=0{,}25: больший вес на новом обзоре от зеркала. Равномерность считается по секторам внутри поля зрения. Рядом смотрится коэффициент вариации числа лучей по наблюдаемым вокселям, чтобы детализация не собралась в одном пятне.

Плотность и равномерность облака уже связывали с качеством расстановки Цай и соавторы. Здесь они стоят в Phi рядом с выигрышем зеркала, а не вместо площади поверхности.

Зеркал мало, треугольников много. Прямоугольники проверяются аналитически и сравниваются с дистанцией до меша. Если какое-то зеркало ближе и удар лицевой, луч отражается, запрос повторяется. Иначе записывается попадание в сцену. Зеркало в меш не запекается: поза меняется на каждом кандидате, иерархию меша выгодно построить один раз.

Embree и Vulkan

На процессоре ближайшее пересечение с мешем считает Intel Embree 4. Иерархию объёмов и запрос ближайшего попадания даёт само ядро. Его устройство описали Вальд и соавторы. Меш загружается в буферы один раз. На каждого кандидата меняются лучи и аналитические зеркала.

Тот же запрос на видеокарте делится на две части. Пересечение луча с мешем — трассировка в Vulkan. Разнесение попаданий по вокселям и свёртка метрик кандидата — вычислительный шейдер. Оба пути дают одну и ту же Phi: процессор служит эталоном, видеокарта ускоряет перебор.

Запрос к сцене — ray query, расширение VK_KHR_ray_query. Отражение остаётся снаружи ускоряющей структуры: зеркало лежит вне меша, число отражений и остаток дальности задаёт расчёт. Структура возвращает ближайший треугольник.

На траектории меш сцены между кадрами тот же, меняется поза носителя. Иерархию треугольников перестраивать не нужно: у Embree для этого есть экземпляр с преобразованием. Отдельное дерево объёмов под эту задачу не требуется. Embree и Vulkan отделяют его от постановки, а постановка — какая поза лучше покрывает поверхность.

Порядок расчёта покрытия и подбора позы

Шесть шагов: меш, каталог, пересечение, оценка, жадный выбор, уточнение

Рис. 3. Прямая модель покрытия и два шага подбора. Пересечение с мешем на процессоре считает Embree, на видеокарте — Vulkan ray query. Оценка Phi у обоих путей одна.

Поиск позы без полной сетки

Каталог заменяет решётку. Зеркало попадает в него, если прямоугольник лежит в свободном месте, не пересекает меш и не накрывает сенсор. Центры берутся среди точек, которые хотя бы один лидар видит напрямую: зеркало в слепой зоне лучей не получит. Нормали выбираются так, чтобы отражённый пучок смотрел в воксели с нулевым прямым покрытием. Поза лидара попадает в каталог, если сенсор лежит в отведённой области и не оказывается внутри меша.

Каждый кандидат после трассировки даёт множество покрытых вокселей. Жадный шаг берёт позу с наибольшим числом ещё не покрытых и фиксирует её. Так устроена жадная схема задачи о покрытии множеств, её разобрал Хватал. Шаг повторяется, пока прирост не упадёт ниже порога. Если свободен один прибор, схема совпадает с выбором лучшего элемента каталога. На траектории одна поза в системе носителя оценивается во всех выбранных положениях движения. Набор выбранных поз — старт непрерывного уточнения.

Phi кусочно-постоянна, градиент по позе почти всюду нулевой. Уточнение безынградное.

Имитация отжига хранит текущую позу и температуру T. Сосед получается малым сдвигом координат и углов. Улучшение принимается всегда. Ухудшение принимается с вероятностью exp(DeltaPhi / T). Температура снижается геометрически. В начале поиск может уйти от позы, которая смотрит в уже покрытый фасад. К концу остаются только улучшения. Метод Киркпатрика, Джелатта и Векки, 1983.

CMA-ES решает ту же непрерывную задачу иначе: выборка из нормального распределения, обновление среднего и ковариации по лучшим точкам. Ковариация вытягивается вдоль направлений, где Phi растёт. Это как раз зеркало у стены. Сдвиг вдоль стены почти ничего не меняет, поворот нормали меняет покрытие резко. Исходная статья Хансена и Остермайера 2001 года плотная. Отдельный разбор Хансена читается легче.

Генетический алгоритм с вещественным кодированием позы Кини применялся к расстановке нескольких LiDAR на автомобиле. Он остаётся третьим безынградным вариантом. Зеркал в той работе нет, прямой и отражённый вклад не разделяются.

Близкие постановки

Близкие работы закрывают соседние вопросы. Позу физического зеркала по покрытию произвольной трёхмерной сцены, вместе с лидарами и с приборами на носителе, не ищет ни одна из них.

Работа

Что размещают

Чем меряют

Вишневский, Фёдоров, 2026

виртуальный зеркальный канал

плотность и калибровка

Ли, Ли, Ким, Ло, 2021

плоские зеркала сканера

охват одной поверхности

Цай и соавторы, 2023

инфраструктурные LiDAR

точность детектора

Кини, 2020

один и несколько LiDAR на машине

занятость облака

эта работа

лидары и зеркала, в том числе на носителе

поверхностные воксели сцены

Вишневский и Фёдоров повышают разрешение механического LiDAR виртуальным зеркальным каналом и калибровкой по плоскости пола. Канал уплотняет уже существующую развёртку и не отправляет луч в закрытую область. Положение зеркала по слепым зонам сцены там не ищется.

Ли и соавторы ставят плоские зеркала к лазерному сканеру, чтобы увеличить дальность и охват при контроле плоскостности. Зеркало физическое и действительно добавляет лучи туда, куда прямая видимость не достаёт. Раскладка подчинена одной поверхности. Оптимизатора позы под произвольную геометрию нет.

Цай и соавторы ищут места инфраструктурных LiDAR в симуляторе CARLA. На типовой полосе подобранная схема подняла среднюю точность детекторов примерно на 15 % при том же числе и типе сенсоров. Плотность и равномерность облака в области интереса у них коррелируют с точностью восприятия. Отражений в постановке нет.

Кини решает, куда ставить один и несколько LiDAR на грузовике и легковом автомобиле, тоже в CARLA. Целевая функция — занятость облака вокруг машины, поиск — генетический алгоритм. Это ближайшая постановка по вопросу, где стоит сенсор.

Отсюда постановка объёмного расчёта. Несколько лидаров и несколько конечных прямоугольников. Часть едет с носителем. Оценка геометрическая: доля наблюдаемой поверхности, площадь слепых зон, равномерность внутри поля зрения и отдельный выигрыш зеркал над прямым сканом.

Источники

  1. Вишневский М. Р., Фёдоров И. Ю. Повышение пространственного разрешения механических LiDAR-систем с использованием виртуального зеркального канала и автоматической калибровки. Труды ИСП РАН, 2026, т. 38, № 3, с. 101–114. Текст, DOI.

  2. Li F., Li H., Kim M.-K., Lo K.-C. Laser Scanning Based Surface Flatness Measurement Using Flat Mirrors for Enhancing Scan Coverage Range. Remote Sensing, 2021, vol. 13, no. 4, article 714. Текст.

  3. Cai X., Jiang W., Xu R., Zhao W., Ma J., Liu S., Li Y. Analyzing Infrastructure LiDAR Placement with Realistic LiDAR Simulation Library. IEEE ICRA, 2023. arXiv:2211.15975.

  4. Kini R. R. Sensor Position Optimization for Multiple LiDARs in Autonomous Vehicles. Master thesis, KTH, TRITA-EECS-EX 2020:896. DiVA.

  5. Wald I., Woop S., Benthin C., Johnson G. S., Ernst M. Embree: A Kernel Framework for Efficient CPU Ray Tracing. ACM Transactions on Graphics, 2014, vol. 33, no. 4, article 143. DOI. Сайт ядра: embree.org.

  6. Khronos Group. Ray Tracing in Vulkan. Заметка. Запрос ближайшего пересечения: VK_KHR_ray_query.

  7. Chvátal V. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research, 1979, vol. 4, no. 3, pp. 233–235. DOI.

  8. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by Simulated Annealing. Science, 1983, vol. 220, no. 4598, pp. 671–680. DOI.

  9. Hansen N., Ostermeier A. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation, 2001, vol. 9, no. 2, pp. 159–195. DOI. Разбор: Hansen N. The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

  10. Assimp, импорт треугольных мешей. Репозиторий.

Автор: Who_Cares727

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js