Comments 23
Берем случайные три точки, вычисляем по ним параметры плоскости (гипотезу).
Оцениваем, насколько гипотеза хороша — сколько точек с учетом заданного порога
можно отнести к плоскости дороги, а сколько нужно признать «выбросами».
думаю, второе действие затратно по cpu, т.к. оценивает весь объем точек. И между ними стоит вставить менее затратный тупой фильтр. Например:
наклоны плоскости относительно машины не могут быть более Х градусов (как минимум потому, что машина не сможет по ним ехать).
Вторая идея — т.к. при приближении угла наклона плоскости к идеальной дороге, метрика «число точек выбросов» будет убывать и достигнет наименьшего значения при совпадении — то к этой функции хорошо подходит градиентный спуск. Это позволит не тупо перебирать все варианты, а выбрать правильное направление движения точек и идти по нему до идеального результата. И для скорости я бы попробовал уменьшающийся шаг градиента.
Вычислительная сложность алгоритма O(k · n), где k — число итераций, а n — число точек. Фильтрация плоскостей по параметрам и точек по положению поможет уменьшить константу.
Эта метрика имеет локальные максимумы — если у нас есть две плоскости, искомая и ложная, и начальное приближение оказалось ближе к ложной, то движение к ней будет давать улучшение.
Берём преобразование Хафа, но только запиливаем его не для 2D, а для 3D.
Преобразование Хафа — мощный инструмент, который гарантированно даст в этой задаче правильный ответ (в отличие от RANSAC, для которого существует вероятность не выбрать ни одной приемлемой гипотезы). Но его вычислительная сложность в быстрой версии для плоскостей, если не ошибаюсь, O(n3 · log(n)), где n — число дискретов в одном направлении в пространстве параметров.
Если б я была царица… то подумал бы вот о чём.
Дорога находится ниже выступающих над ней объектов. Это значит, что можно поискать какую-нибудь выпуклую оболочку и плоскость под ней.
И наверное, это будет дешевле, чем перебирать все тройки точек с кубической сложностью.
Понятно, что лидар может быть сориентирован как угодно.
Но его система координат — это одна из осей примерно вертикальна.
Поэтому нижнюю плоскость надо искать с шести сторон максимум.
Ещё один подход — это вокселизация.
Нарезаем параллелограммную оболочку облака на кубики, для каждого кубика считаем ковариацию, и если там что-то похожее на плоскость, — берём вектор нормали.
Потом усредняем нормали всех кубиков, взвешивая их по количеству точек в кубиках.
Как вариант, — строим гистограмму направлений (потому что у нас будет много направлений "вверх от дороги" и много — "вперёд от стены") и выбираем моду.
P.S.
Не до контеста мне сейчас, а так бы поигрался, конечно.
Пойду дальше пилить пайплайн для яндексовского лидара.
Какова цель предлагаемой к решению задачи? Добавить к обществу ударенных математикой дополнительную группу участников?
Машина едет по реальной дороге, а не по плоскости, если кто-то вдруг со своей математикой об этом забыл.
Математика в теме нужна, но не в таком виде.
В условии слишком много отрицаний. Я мозг сломал, пока перевел на более понятный мне язык. Лучше заменить «не более» на «менее»и «не менее» на «более»
2д с глубиной — это и есть 3д.
Потому что мы именно 3д информацию извлекаем (что смогли, то и извлекли, конечно: лидар за препятствие или за сектор обзора не может заглянуть).
Во-вторых, у точек есть ещё и яркость, и это тоже может оказаться полезной информацией.
В-третьих, лидарное зрение — всегда с синтезированной апертурой. Даже для одного лидара: машина движется, и там что-то типа rolling shutter где-то вредит, а где-то, пожалуй, и помогает заглядывать за угол. А если лидаров несколько?
Естественно, что некоторые задачи удобно решать в системе координат с центром в лидаре. Например, вычленение маленьких объектов.
А другие задаче — в системе с центром в машине (например, распознавание и сопровождение автомобилей).
Или даже в глобальной системе координат (например, топопривязка: "вот дерево, вот мужик!")
P.S.
Учить компьютерному зрению человека из команды разработки беспилотных автомобилей… нуу, такое.
Надо же понимать, что эта статья — развлекалочка, сильно упрощённая и выхолощенная задачка.
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 является приблизительным методом. Он ищет решение среди множества плоскостей, проходящих через точки исходного облака, и опирается на два предположения:
- плоскости, построенные по "не-выбросам" (инлаерам), близки к искомому решению;
- число рассматриваемых гипотез обеспечивает достаточную вероятность найти решение.
Мы считаем, что для наших данных первое предположение выполняется. Вероятность в таком случае найти решение для большого числа точек можно упрощенно оценить следующим образом. Пусть 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.
Можно порешать: задача про лидарное облако от команды беспилотных автомобилей Яндекса