Методы поиска глобального оптимума для этой задачи предлагаются в некоторых академических статьях (например, 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.
Преобразование Хафа — мощный инструмент, который гарантированно даст в этой задаче правильный ответ (в отличие от RANSAC, для которого существует вероятность не выбрать ни одной приемлемой гипотезы). Но его вычислительная сложность в быстрой версии для плоскостей, если не ошибаюсь, O(n3 · log(n)), где n — число дискретов в одном направлении в пространстве параметров.
Вычислительная сложность алгоритма O(k · n), где k — число итераций, а n — число точек. Фильтрация плоскостей по параметрам и точек по положению поможет уменьшить константу.
Эта метрика имеет локальные максимумы — если у нас есть две плоскости, искомая и ложная, и начальное приближение оказалось ближе к ложной, то движение к ней будет давать улучшение.
Спасибо за комментарий.
Методы поиска глобального оптимума для этой задачи предлагаются в некоторых академических статьях (например, 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.
Преобразование Хафа — мощный инструмент, который гарантированно даст в этой задаче правильный ответ (в отличие от RANSAC, для которого существует вероятность не выбрать ни одной приемлемой гипотезы). Но его вычислительная сложность в быстрой версии для плоскостей, если не ошибаюсь, O(n3 · log(n)), где n — число дискретов в одном направлении в пространстве параметров.
Вычислительная сложность алгоритма O(k · n), где k — число итераций, а n — число точек. Фильтрация плоскостей по параметрам и точек по положению поможет уменьшить константу.
Эта метрика имеет локальные максимумы — если у нас есть две плоскости, искомая и ложная, и начальное приближение оказалось ближе к ложной, то движение к ней будет давать улучшение.