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

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

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

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

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

\mathbf{d}' = \mathbf{d} - 2(\mathbf{d}\cdot\mathbf{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{,}7\left(1 - \frac{A_{\mathrm{blind}}}{N}\right),G_{\mathrm{norm}} = \min\left(1,\ \frac{G - 1}{0{,}5}\right).

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

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

Возьмём комнату 16\times 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), то есть в видимой половине комнаты, причём его нормаль смотрит в сторону левой стены. Сетка 10\times 10\times 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_A\left(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(\Delta\Phi / 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, импорт треугольных мешей. Репозиторий.

Комментарии (0)