Выбор наиболее рассеянных точек из набора точек

15

Существует ли какой-либо (эффективный) алгоритм для выбора поднабора из точек из набора из точек ( ), чтобы они «покрывали» большую часть области (по всем возможным подмножествам размера )?MNM<NM

Я предполагаю, что точки находятся в 2D плоскости.

Наивный алгоритм прост, но непомерен с точки зрения временной сложности:

for each subset of N points
    sum distance between each pair of points in the subset
    remember subset with the maximum sum

Я ищу более эффективный или даже приблизительный метод.

Пример, вот плоскость с некоторыми случайными точками в ней:

введите описание изображения здесь

Для я ожидаю выбора точек, подобных этим:Mзнак равно5

введите описание изображения здесь

Обратите внимание, что выбранные точки (красные) разбросаны по всей плоскости.

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

ЛИБОР
источник
2
Для случая посмотрите это из StackOverflow: Алгоритм, чтобы найти точки, которые находятся дальше друг от друга - лучше, чем O (n ^ 2)? , Mзнак равно2
hardthth
К сожалению, обычно составляет 1500-5000, а составляет 10-50. MNM
Либор
Являются ли значения и фиксированными, или вы также меняете (например, потому что вы хотите максимизировать среднее расстояние, и в этом случае дальнейшее увеличение может привести к уменьшению)? Н М МMNMM
Вольфганг Бангерт
1
Я сильно подозреваю, что это NP-трудно. Это очень похоже на задачу клики с максимальным весом, когда вес ребра между двумя вершинами является евклидовым расстоянием между ними. (Я полагаю, что для max-clique известны практически эффективные эвристики. Я не уверен, какие они есть.)
tmyklebu
1
@hardmath Извините, это была опечатка. Я попытался проиллюстрировать, чего мне нужно достичь. Проблема заключается в извлечении объектов изображения, когда мне нужно получить только несколько точечных объектов, но разбросать их по всему изображению, потому что они используются для оценки преобразования и когда они пространственно разбросаны, оценка более стабильна. Возможно, «энтропия» - лучшая мера - я бы хотел выбрать точек, чтобы они были повсюду, как газ в состоянии максимальной энтропии. С другой стороны, я стараюсь избегать кластеризации выбранных точек. M
Либор

Ответы:

11

Вот примерное решение. Поскольку N так велико, а M так мало, как насчет следующего:

  1. Вычислить выпуклую оболочку N
  2. Выберите до M точек от корпуса, которые удовлетворяют вашим критериям максимального расстояния.
  3. Если на шаге 2 у вас меньше M точек, выберите 1 точку изнутри, которая максимизирует расстояние от ранее выбранных точек.
  4. Повторите шаг 3, пока количество выбранных точек не станет М

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

Также, начиная с корпуса, вы уменьшаете начальный поиск с N до N 1/2 .


ОБНОВИТЬ

Если шаги 3 и 4, описанные выше, занимают слишком много времени (поскольку вы итеративно тестируете внутреннюю часть своего набора данных), мне пришло в голову еще две идеи, чтобы ускорить вашу проблему.

  1. Рандомизированный поиск : скажем, вы нашли P точек на корпусе на шаге 2. Затем случайным образом нарисуйте M - P точек изнутри. Выберите лучший набор после X испытаний.
  2. Имитация отжига : вычисление наименьшего ограничивающего прямоугольника, который покрывает ваш набор данных (не обязательно должен быть выровнен с осями, может быть наклонен). Затем определите набор из M равномерно распределенных точек сетки на этой ограничительной рамке. Обратите внимание, что эти точки не обязательно совпадают ни с одной из ваших точек набора данных. Затем для каждой точки сетки найдите k- ближайших соседей в вашем наборе данных. Пройдите каждую комбинацию M x k и выберите ту, которая удовлетворяет вашим критериям максимального расстояния. Другими словами, вы используете начальную сетку в качестве начальной загрузки, чтобы найти хорошее начальное решение.
dpmcmlxxvi
источник
Благодарю. Может быть, сформулировал вопрос неправильно. Я стремлюсь к тому, чтобы множество точек «охватывало» большую часть области. Я думал, что достаточно критериев расстояния, но, похоже, нужно добавить еще кое-что.
Либор
M
1
Возможно, более формальный способ сформулировать вашу проблему состоит в том, что вы хотите тесселяцию размера M, которая покрывает N и минимизирует среднюю площадь фасета тесселяции? Минимизация областей фасетов, кажется, способ распределить точки вокруг и убедиться, что они не слипаются.
dpmcmlxxvi
Да. Я хотел избежать использования сетки, потому что если точки могут быть случайно сгруппированы вокруг линий сетки, то они будут сгруппированы в выделении.
Либор
Одна проблема с вашим жадным алгоритмом, который вы упомянули, заключается в том, что он будет очень чувствителен к начальной начальной точке. Алгоритмы выращивания семян (где вы начинаете изнутри) имеют эту проблему. Подход к корпусу, о котором я упоминаю, вероятно, будет более стабильным, поскольку он работает снаружи.
dpmcmlxxvi
6

NM

MM

M1Mзнак равно3,4,5

Mзнак равно31Mзнак равно4Mзнак равно51

Если мы хотим избежать преобладающего выбора точек на периферии, другая цель может оказаться полезной. Максимизация минимального расстояния между точками является таким критерием. Связанные проблемы обсуждались в StackOverflow , Computer Science SE , Math.SE и MathOverflow .

MDMD

hardmath
источник
1

Итак, вы хотите выбрать M точек из заданного набора из N точек на евклидовой плоскости, чтобы сумма парных расстояний выбранных точек была максимальной, верно?

Стандартный алгоритм локального поиска довольно быстрый и предлагает довольно хорошее приближение. Время выполнения является линейным по N и квадратичным по M. Его отношение аппроксимации составляет 1 - 4 / M. Это означает, что отношение становится лучше с ростом М. Например, для M = 10 он получает оптимальное значение в 60%, а для M = 50 - оптимальное значение в 92%.

Алгоритм работает также для евклидовых пространств общей размерности. В этом случае проблема NP-трудна. Но в самолете неизвестно, является ли он NP-сложным.

Источник этой статьи . Надеюсь это поможет! Бест, Альфонсо


Alfonso
источник
1
Я уже решил эту проблему, используя алгоритм «Подавление с помощью покрытия диска» из статьи «Эффективный выбор пространственно распределенных ключевых точек для визуального отслеживания» 2011 18-я Международная конференция IEEE по обработке изображений. IEEE, 2011
Libor
1
Альфонсо, пожалуйста, укажите свою принадлежность к предложенному документу.
Никогуаро
0

Одним из решений является:

  • О(N)

  • Сделайте M искусственно распределенными точками внутри этого ограничивающего прямоугольника, некоторые M сложнее, чем другие. В вашем случае четыре в углах прямоугольника и один в центре

  • О(N(Lограмм(N)))

  • О(м(Lограмм(N)))

О(N(Lограмм(N)))MN

Ян Хакенберг
источник