Auswählen der meisten verstreuten Punkte aus einer Reihe von Punkten

15

Gibt es einen (effizienten) Algorithmus, um eine Teilmenge von Punkten aus einer Menge von Punkten ( ) so auszuwählen, dass sie den größten Bereich "abdecken" (über alle möglichen Teilmengen der Größe )?MNM<NM

Ich gehe davon aus, dass die Punkte in der 2D-Ebene liegen.

Der naive Algorithmus ist einfach, aber in Bezug auf die zeitliche Komplexität unerschwinglich:

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

Ich suche nach einer effizienteren oder sogar ungefähren Methode.

Beispiel: Hier ist eine Ebene mit einigen zufälligen Punkten:

Bildbeschreibung hier eingeben

Für erwarte ich folgende Punkte:M=5

Bildbeschreibung hier eingeben

Beachten Sie, dass die ausgewählten Punkte (rot) über die gesamte Ebene verteilt sind.

Ich habe einen Artikel " EFFIZIENTE AUSWAHL VON SPATIALLY DISTRIBUTED KEYPOINTS FÜR VISUAL TRACKING " gefunden, der sich auf dieses Problem bezieht. Dies setzt jedoch voraus, dass die Punkte gewichtet sind.

Libor
quelle
Leider liegt normalerweise bei 1500 bis 5000 und bei 10 bis 50. NM
Libor
Sind und beide fest oder variieren Sie auch (z. B. weil Sie den Durchschnitt der Abstände maximieren möchten ; in diesem Fall kann eine weitere Erhöhung von einer Verringerung führen)? MNMM
Wolfgang Bangerth
1
Ich vermute sehr, dass dies NP-schwer ist. Es ähnelt stark einem Cliquenproblem mit maximaler Gewichtung, bei dem das Gewicht der Kante zwischen zwei Scheitelpunkten der euklidische Abstand zwischen ihnen ist. (Ich glaube, es gibt praktisch wirksame Heuristiken, die für max-clique bekannt sind. Ich bin nicht sicher, welche es sind.)
tmyklebu
1
@hardmath Sorry das war ein Tippfehler. Ich habe versucht zu veranschaulichen, was ich erreichen muss. Das Problem ergibt sich aus der Extraktion von Bildmerkmalen, bei der ich nur eine Handvoll Punktmerkmale erhalten muss, diese jedoch über das gesamte Bild verstreut haben muss, da sie für die Transformationsschätzung verwendet werden und die Schätzung bei räumlicher Streuung stabiler ist. Vielleicht ist "Entropie" ein besseres Maß - ich möchte Punkte so auswählen, dass sie überall sind, wie ein Gas im Zustand maximaler Entropie. Andererseits versuche ich zu vermeiden, dass die ausgewählten Punkte zu Clustern zusammengefasst werden. M
Libor

Antworten:

11

Hier ist eine ungefähre Lösung. Da N so groß und M so klein ist, wie wäre es mit Folgendem:

  1. Berechnen Sie die konvexe Hülle von N
  2. Wählen Sie bis zu M Punkte aus dem Rumpf aus, die Ihren Kriterien für die maximale Entfernung entsprechen.
  3. Wenn Sie in Schritt 2 weniger als M Punkte haben, wählen Sie 1 Punkt aus dem Innenraum aus, der den Abstand zu den zuvor ausgewählten Punkten maximiert.
  4. Wiederholen Sie Schritt 3, bis die Anzahl der ausgewählten Punkte M beträgt

Die Intuition dahinter ist, dass, da N >> M und Sie Punkte so weit wie möglich voneinander entfernt haben möchten, diese wahrscheinlich nahe an den Rändern der Daten liegen, sodass Sie genauso gut mit dem Rumpf und dann iterativ beginnen können Arbeite dich von dort aus ein.

Wenn Sie mit dem Rumpf beginnen, reduzieren Sie außerdem Ihre anfängliche Suche von N auf N 1/2 .


AKTUALISIEREN

Wenn die obigen Schritte 3 und 4 zu lange dauern (da Sie das Innere Ihres Datasets iterativ testen), sind mir zwei weitere Ideen eingefallen, um Ihr Problem zu beschleunigen.

  1. Suchen Randomisierte : Sagen Sie gefunden P Punkte auf dem Rumpf in Schritt 2. Dann zufällig ziehen M - P Punkte aus dem Inneren. Wählen Sie den besten Satz nach X Versuchen.
  2. Simuliertes Tempern : Berechnen Sie den kleinsten Begrenzungsrahmen, der Ihren Datensatz abdeckt (muss nicht an den Achsen ausgerichtet sein, kann geneigt sein). Definieren Sie dann eine Menge von M gleichmäßig verteilten Gitterpunkten auf diesem Begrenzungsrahmen. Beachten Sie, dass diese Punkte nicht unbedingt mit einem Ihrer Datenmengenpunkte übereinstimmen. Dann finden Sie für jeden Gitterpunkt die k -nächsten Nachbarn in Ihrem Datensatz. Durchlaufen Sie jede M x k- Kombination und wählen Sie die aus, die Ihre Kriterien für die maximale Entfernung erfüllt. Mit anderen Worten, Sie verwenden das anfängliche Raster als Bootstrap, um eine gute anfängliche Lösung zu finden .
dpmcmlxxvi
quelle
Vielen Dank. Vielleicht hat man die Frage falsch formuliert. Ich bemühe mich um eine Reihe von Punkten, so dass sie den meisten Bereich "abdecken". Ich dachte, nur die Entfernungskriterien sind ausreichend, aber es scheint, als müsste noch etwas hinzugefügt werden.
Libor
Okay, ich habe die Frage aktualisiert. Ihre vorgeschlagene Methode kann gut funktionieren. Ich dachte auch über den Algorithmus der gierigen Version nach, der wie folgt funktionieren sollte: 1) Zufallspunkt A auswählen, 2) Punkt B am weitesten von A auswählen, 3) Punkt C am weitesten von A und B auswählen, 4) ... fortfahren bis Punkte ausgewählt sind. M
Libor
1
Vielleicht ist es eine formalere Art, Ihr Problem zu formulieren, dass Sie eine Tessellation der Größe M wünschen , die N abdeckt und die durchschnittliche Facettenfläche der Tessellation minimiert? Das Minimieren der Facettenbereiche scheint eine Möglichkeit zu sein, die Punkte zu verteilen und sicherzustellen, dass sie nicht zusammenklumpen.
dpmcmlxxvi
Ja. Ich wollte die Verwendung von Gittern vermeiden, da Punkte, die sich versehentlich um Gitternetzlinien gruppieren lassen, in der Auswahl gruppiert werden.
Libor
Das einzige Problem bei Ihrem gierigen Algorithmus, das Sie erwähnen, ist, dass er sehr empfindlich auf den anfänglichen Startpunkt reagiert. Algorithmen für die Samenproduktion (bei denen Sie von innen nach außen beginnen) haben dieses Problem. Der Rumpfansatz, den ich erwähne, wird wahrscheinlich stabiler sein, da er von außen nach innen funktioniert.
dpmcmlxxvi
6

Bei einer sehr großen Anzahl von Punkten und einer kleinen zu wählenden Teilmenge kann es hilfreich sein, zu überlegen, was über kontinuierliche Versionen des Problems in zwei Dimensionen bekannt ist.NM

L. Fejes Tóth (Acta Math. Acad. Sci. Hungar., 7: 397–401, 1956) zeigte, dass die Menge der Punkte auf einem Kreis die Summe der Punkte maximiert paarweise Abstände werden durch Eckpunkte eines regulären Gons erreicht, das in den Kreis eingeschrieben ist. MM

Anschließend stellte er (L. Fejes Tóth, "Über eine Punktverteilung auf der Kugel", Acta Math. Acad. Sci. Hungar., 10: 13-19, 1959) das schwierigere Problem der Maximierung der Summe der paarweisen Abstände für Punkte in der Ebene, deren Durchmesser (maximaler paarweiser Abstand) beträgt . Dieses Problem bleibt im Allgemeinen offen, obwohl Friedrich Pillichshammer eine obere Schranke angegeben und gezeigt hat, dass sie für scharf ist ( "Über Extremalpunktverteilungen in der euklidischen Ebene" , Acta Mathematica Hungarica, 98 (4): 311–321, 2003).M1M=3,4,5

Diese wenigen Fälle legen nahe, dass die Punkte solcher extremer Verteilungen dazu neigen, an der Peripherie einer Region aufzutreten. Für die Lösung ein gleichseitiges Dreieck mit Kantenlänge . Für drei der Punkte wieder ein gleichseitiges Dreieck und der vierte Punkt liegt auf dem Mittelpunkt eines Kreisbogens durch zwei der Punkte, zentriert auf dem dritten Punkt. Für die Lösung ein regelmäßiges Fünfeck mit Durchmesser . Keines von diesen zeigt eine "Streuung" von Punkten durch das Innere einer Figur.M=31M=4M=51

Wenn wir eine vorherrschende Auswahl von Punkten an der Peripherie vermeiden wollen, kann sich ein anderes Ziel als nützlich erweisen. Die Maximierung des Mindestabstands zwischen Punkten ist ein solches Kriterium. Verwandte Probleme wurden bei angeschnitten Stackoverflow , bei Informatik SE , bei Math.SE und bei MathOverflow .

Betrachten Sie die grobe Entsprechung dieser Methode zum Packen von KreisenM mit einem Durchmesser von innerhalb einer Figur, um einen Einblick zu erhalten, warum diese Methode Punkte innerhalb einer Figur ergibt . Die Zentren sind dann Punkte, von denen keine zwei näher als der Abstand . Das Bild in dieser Math.SE-Antwort ist wahrscheinlich einen Blick wert und zeigt, wie man am besten zehn Punkte in einem Quadrat anordnet .DMD

Hardmath
quelle
1

OK, Sie möchten also M Punkte aus einer gegebenen Menge von N Punkten in der euklidischen Ebene auswählen, sodass die Summe der paarweisen Abstände der ausgewählten Punkte maximal ist. Richtig?

Der standardmäßige lokale Suchalgorithmus ist ziemlich schnell und bietet eine ziemlich gute Annäherung. Die Laufzeit ist in N linear und in M ​​quadratisch. Das Näherungsverhältnis beträgt 1 - 4 / M. Dies bedeutet, dass das Verhältnis mit zunehmendem M besser wird. Zum Beispiel wird für M = 10 ein optimaler Wert von 60% und für M = 50 ein optimaler Wert von 92% erhalten.

Der Algorithmus funktioniert auch für euklidische Räume allgemeiner Dimension. In diesem Fall ist das Problem NP-schwer. Aber im Flugzeug ist nicht bekannt, ob es NP-schwer ist.

Die Quelle ist dieses Papier . Hoffe das hilft! Beste, Alfonso


Alfonso
quelle
1
Ich habe dies bereits mithilfe des Algorithmus "Suppression via Disk Covering" aus dem Artikel "Räumlich verteilte Schlüsselpunkte für visuelles Tracking effizient auswählen" gelöst. 2011 18. IEEE International Conference on Image Processing. IEEE, 2011
Libor
1
Alfonso, geben Sie bitte ausdrücklich Ihre Zugehörigkeit zu dem vorgeschlagenen Artikel an.
Nicoguaro
0

Eine Lösung ist:

  • Ö(n)

  • Machen M künstliche sogar verteilte Punkte in diesem Begrenzungsrechteck, einige M sind schwieriger als andere. In Ihrem Fall vier in den Ecken des Rechtecks ​​und eine in der Mitte

  • Ö(n(lÖG(n)))

  • Ö(m(lÖG(n)))

Ö(n(lÖG(n)))MN

Jan Hackenberg
quelle