Комментарии 23
Берем случайные три точки, вычисляем по ним параметры плоскости (гипотезу).

Оцениваем, насколько гипотеза хороша — сколько точек с учетом заданного порога
можно отнести к плоскости дороги, а сколько нужно признать «выбросами».


думаю, второе действие затратно по cpu, т.к. оценивает весь объем точек. И между ними стоит вставить менее затратный тупой фильтр. Например:
наклоны плоскости относительно машины не могут быть более Х градусов (как минимум потому, что машина не сможет по ним ехать).

Вторая идея — т.к. при приближении угла наклона плоскости к идеальной дороге, метрика «число точек выбросов» будет убывать и достигнет наименьшего значения при совпадении — то к этой функции хорошо подходит градиентный спуск. Это позволит не тупо перебирать все варианты, а выбрать правильное направление движения точек и идти по нему до идеального результата. И для скорости я бы попробовал уменьшающийся шаг градиента.

Вычислительная сложность алгоритма O(k · n), где k — число итераций, а n — число точек. Фильтрация плоскостей по параметрам и точек по положению поможет уменьшить константу.


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

Все так, да. У градиентного спуска есть проблема застревания в локальных максимумах. Но, думаю, все равно можно использовать эту стратегию как первый быстрый поиск. Учитывая, ограничение в задаче «Больше 50% точек принадлежат дороге» — итак будет понятно, что мы застряли на локальном максимуме, а не дошли до реальной дороги.

Преобразование Хафа — мощный инструмент, который гарантированно даст в этой задаче правильный ответ (в отличие от RANSAC, для которого существует вероятность не выбрать ни одной приемлемой гипотезы). Но его вычислительная сложность в быстрой версии для плоскостей, если не ошибаюсь, O(n3 · log(n)), где n — число дискретов в одном направлении в пространстве параметров.

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

Если б я была царица… то подумал бы вот о чём.
Дорога находится ниже выступающих над ней объектов. Это значит, что можно поискать какую-нибудь выпуклую оболочку и плоскость под ней.
И наверное, это будет дешевле, чем перебирать все тройки точек с кубической сложностью.


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


Ещё один подход — это вокселизация.
Нарезаем параллелограммную оболочку облака на кубики, для каждого кубика считаем ковариацию, и если там что-то похожее на плоскость, — берём вектор нормали.
Потом усредняем нормали всех кубиков, взвешивая их по количеству точек в кубиках.
Как вариант, — строим гистограмму направлений (потому что у нас будет много направлений "вверх от дороги" и много — "вперёд от стены") и выбираем моду.


P.S.
Не до контеста мне сейчас, а так бы поигрался, конечно.
Пойду дальше пилить пайплайн для яндексовского лидара.

А дело быдо не в бобине…

Какова цель предлагаемой к решению задачи? Добавить к обществу ударенных математикой дополнительную группу участников?

Машина едет по реальной дороге, а не по плоскости, если кто-то вдруг со своей математикой об этом забыл.

Математика в теме нужна, но не в таком виде.
Это ведь обычный RANSAC, и один из самых простых кейсов для него.

P.S. Прошлогодний митап понравился, давайте еще как ковид уйдет.

В условии слишком много отрицаний. Я мозг сломал, пока перевел на более понятный мне язык. Лучше заменить «не более» на «менее»и «не менее» на «более»

Особенности русского языка. Более это ">", для ">=" нужно «не менее» или «больше или равно».
Для этой задачи разве есть принципиальная разница ">" или ">="?
Вы даете облако точек с x,y,z. И тем самым игнорируете важное обстоятельство, что каждая точка есть пересечение луча с поверхностью. И луч у каждой точки выпущен из общей точки (лидар). Т.е. все это облако на самом деле не облако в 3д, а облако 2д на некоторой поверхности, из каждой точки которой можно провести луч в одну общую. Т.о. все это облако 3д точек на самом деле есть 2д битмап с глубиной. Это важная инфа, и задача совсем другая. И алгоритмы уже можно применять другие, из области изображений например. Например, появляется понятие соседства точек, которое трудно выяснить на 3д облаке точек.
С удешевлением лидаров, их может быть несколько на автомобиле + другие датчики тоже могут добавлять точки.

2д с глубиной — это и есть 3д.
Потому что мы именно 3д информацию извлекаем (что смогли, то и извлекли, конечно: лидар за препятствие или за сектор обзора не может заглянуть).
Во-вторых, у точек есть ещё и яркость, и это тоже может оказаться полезной информацией.
В-третьих, лидарное зрение — всегда с синтезированной апертурой. Даже для одного лидара: машина движется, и там что-то типа rolling shutter где-то вредит, а где-то, пожалуй, и помогает заглядывать за угол. А если лидаров несколько?


Естественно, что некоторые задачи удобно решать в системе координат с центром в лидаре. Например, вычленение маленьких объектов.
А другие задаче — в системе с центром в машине (например, распознавание и сопровождение автомобилей).
Или даже в глобальной системе координат (например, топопривязка: "вот дерево, вот мужик!")


P.S.
Учить компьютерному зрению человека из команды разработки беспилотных автомобилей… нуу, такое.
Надо же понимать, что эта статья — развлекалочка, сильно упрощённая и выхолощенная задачка.

>Учить компьютерному зрению человека из команды разработки беспилотных автомобилей… нуу, такое

Это хабр так то, а не заседание титулованых.

Еще я бы подумал над статичным положением лидара на машине. А значит можно один раз измерить, где под ним машина стоит на дороге. Искомая плоскость то должна проходить через эту точку, которая всегда фиксирована. А значит одну из 3х искомых точек уже можно не искать — считать ее всегда под лидаром на уровне соприкоснования колес (хоть она и не в видимой его зоне).
А еще положение дороги относительно машины довольно статично, а значит можно переносить предрассчитанную плоскость с прошлого расчета как «стартовую гипотезу». И переборы делать не всех точек, а по увеличению расстояния от этой плоскости. Так мы довольно быстро дойдем до искомого наклона и в большинстве случаев различия будут минимальны.
НЛО прилетело и опубликовало эту надпись здесь
Координаты относительно машины ведь? Проводим предполагаемую плоскость дороги, так как знаем, где колеса в пространстве наших координат и выбираем точки, ближайшие к этой плоскости, но не дальше, чем определенная погрешность.

А об этом в задаче не сказано :)
Собственно, смысл нахождения плоскости — в том, чтобы пересчитать систему лидара в систему машины.
Если лидар крепко прикручен, то это делается один раз и называется калибровкой.


Конечно, в реальной жизни калибровку проводят по-другому, но вот так тоже возможно.

Кажется предлагаемое решение не всегда работает, вот подадим на вход
0.05
7
0 0 0
0 100 0
100 0 0
0 0 0.09
100 100 10
-25 75 10
90 -10 10
Плюсовый код выдает
0 0 -1 -0
по сути это плоскость z=0, она покрывает только три точек из семи. Но ее можно приподнять на 0.05
0 0 1 -0.05
и вот она уже покрывает четыре из семи точек, то есть выглядит правильным решением. Думаю совсем правильное решение задачи несколько сложнее.

Спасибо за комментарий.


Методы поиска глобального оптимума для этой задачи предлагаются в некоторых академических статьях (например, 1, 2), но они обладают слишком большой вычислительной сложностью, чтобы применять их на практике.


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


RANSAC является приблизительным методом. Он ищет решение среди множества плоскостей, проходящих через точки исходного облака, и опирается на два предположения:


  1. плоскости, построенные по "не-выбросам" (инлаерам), близки к искомому решению;
  2. число рассматриваемых гипотез обеспечивает достаточную вероятность найти решение.

Мы считаем, что для наших данных первое предположение выполняется. Вероятность в таком случае найти решение для большого числа точек можно упрощенно оценить следующим образом. Пусть w — вероятность выбрать один инлаер из облака точек. Тогда вероятность независимо выбрать 3 инлаера w3, а вероятность, что в выборке есть хотя бы одна выбросовая точка, 1 - w3. Вероятность, что за k итераций не будет встречено ни одной гипотезы, состоящей из инлаеров, (1 - w3)k. Вероятность ps выбрать за k итераций хотя бы одну гипотезу, состоящую только из инлаеров, 1 - (1 - w3)k. В нашем примере w = 0.5, а k = 100, т.е. ps = 1 - (1 - 0.53)100 ≈ 0.9999984.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.
Информация
Дата основания

23 октября 1997

Местоположение

Россия

Численность

свыше 10 000 человек

Дата регистрации

9 августа 2008

Блог на Хабре