Самая маленькая связанная сфера, содержащая x% точек

Question

Учитывая 3D облако точек, как я могу найти наименьшую ограничительную сферу, которая содержит заданный процент точек?

I.e. если у меня есть облако точек с некоторым шумом, и я хочу игнорировать 5% выбросов, как я могу получить наименьшую сферу, содержащую 95% оставшихся очков, если я не знаю, какие точки являются выбросами?

Пример: Я хочу найти зеленую сферу, а не красный шар:

Я ищу достаточно быстрый и простой алгоритм. Он не должен найти оптимальное решение, разумное приближение тоже хорошо.

Я знаю, как рассчитать приблизительную границу шара для 100% точек, например. с алгоритмом Риттера.

Как я могу обобщить это на алгоритм, который находит наименьшую сферу, содержащую x% точек?

Answer 1

Просто идея: двоичный поиск.

Во-первых, используйте одну из ограничивающих сфер algorithms, чтобы сначала найти ограничительную сферу 100%.

Исправить центральную точку сферы 95%, чтобы она была такой же, как и центральная точка сферы 100%. (Нет никакой гарантии, но вы говорите, что вы в порядке с приблизительным ответом.) Затем используйте бинарный поиск по радиусу сферы, пока не получите 95% +- epsilon точек внутри.

Предполагая, что точки сортируются по расстоянию (или квадрат расстояния, чтобы быть немного быстрее) от центральной точки, при фиксированном радиусе r он принимает O(log n) операций, чтобы найти число точек внутри сферы с радиусом r, например, используя другой бинарный поиск. Бинарный поиск для права r сам по себе требует логарифмического числа такой оценки. Поэтому весь поиск должен принимать только O (log n) шаги после того, как вы нашли сферу 100%.

Edit:, если вы думаете, что центр уменьшенной сферы может быть слишком далеко от полной сферы, можно пересчитать ограничивающую сферу, или только центр масс множества точек, каждый раз после броска прочь некоторые моменты. Каждая рекакуляция должна занимать не более O (n). После перерасчета используйте точки на расстоянии от новой центральной точки. Поскольку вы ожидаете, что они будут уже почти отсортированы, вы можете положиться на сортировку пузырьков, которая для почти сортированных данных работает в O (n + epsilon). Помните, что для этого потребуется только логарифмическое число этих тестов, поэтому вы должны уйти с близким к O (n log n) для всего этого.

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

Answer 2

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

алгоритм может выглядеть примерно так:

1. Найти ограничивающую сферу точек
2. Найти среднее расположение
3. точки Выберите точку на ограничивающей сфере, которая в наибольшей степени удалена от среднего места, удалите его как выбросом
4. Повторите шаги 1-3 до тех пор, пока вы удалили 5% очков

Answer 3

Найти в ЕС минимальное остовное дерево клида и проверить края в порядке убывания длины. Для каждого ребра рассмотрим множества точек точек в двух связанных деревьях, которые вы получите, удалив край.

Если меньший набор точек меньше 5% от общего числа, а ограничивающая сфера вокруг большего набора точек не перекрывает его, то удалите меньший набор точек. (Это условие необходимо, если у вас есть «оазис» пустого пространства в центре облака точек).

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

Answer 4

Алгоритм ryann не так уж плох. Я предложил robustifying с геометрическим медианой затем пришел в этот эскиз:

1. вычислить NxN интер-расстояния в O (N^2)
2. сумма в каждой строке этой матрицы (= расстояние от одной точки к другие) в O (N^2)
3. рода полученный «толпы» расстояние в O (N * войти N)
   (точка с наименьшим расстоянием является приближением геометрической средней)
4. удалить 5% самый большой в O (1)
   здесь мы просто рассматриваем наибольшую дистанцию ​​толпы как выбросы,
   вместо того, чтобы занимать наибольшее расстояние от медианного. Радиус
5. вычисления полученной сферы в O (N)

Конечно, она также страдает от суб-оптимальности, но должен выполнить немного лучше в случае дальней выброса. Общая стоимость O (N^2).

Answer 5

я бы итерацию следующие два шага до сходимости:

1) С учетом группы точек, найти наименьший сферу, охватывающую 100% точек и выработать свой центр.

2) С учетом центра найдите группу точек, содержащую 95% исходного номера, который находится ближе всего к центру.

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

Фактически, я бы перебирал несколько случайных запусков, каждый из которых начинался с поиска наименьшей сферы, содержащей все небольшое подмножество точек. Я отмечаю, что если у вас 10 выбросов, и вы разделите свой набор очков на 11 частей, по крайней мере одна из этих частей не будет иметь никаких выбросов.

(Это очень свободно основано на https://en.wikipedia.org/wiki/Random_sample_consensus)