Anpassen von Linien durch große Punktwolken

8

Ich habe eine große Menge von Punkten (in der Größenordnung von 10.000 Punkten), die durch Teilchenspuren (Bewegung in der xy-Ebene in der Zeit, die von einer Kamera aufgenommen wurde, also 3d - 256 x 256 Pixel und ca. 3.000 Bilder in meinem Beispielsatz) und Rauschen gebildet werden. Diese Partikel bewegen sich auf ungefähr geraden Linien ungefähr (aber nur ungefähr) in die gleiche Richtung, und deshalb versuche ich für die Analyse ihrer Trajektorien, Linien durch die Punkte zu ziehen. Ich habe versucht, Sequential RANSAC zu verwenden, kann jedoch kein Kriterium finden, um zuverlässig falsch positive Ergebnisse sowie T- und J-Verknüpfungen, die zu langsam und auch nicht zuverlässig genug waren, zuverlässig herauszufinden.

Hier ist ein Bild eines Teils des Datensatzes mit guten und schlechten Anpassungen, die ich mit sequentiellem Ransac erhalten habe: Geben Sie hier die Bildbeschreibung ein Ich verwende hier die Schwerpunkte der Partikel-Blobs, die Blob-Größen variieren zwischen 1 und etwa 20 Pixel.

Ich fand heraus, dass Teilproben, die zum Beispiel nur jeden 10. Frame verwenden, auch ziemlich gut funktionieren, so dass die zu verarbeitende Datengröße auf diese Weise reduziert werden kann.

Ich habe einen Blog-Beitrag über alles gelesen, was neuronale Netze leisten können, und möchte Sie fragen, ob dies eine praktikable Anwendung für eine solche ist, bevor ich mit dem Lesen beginne (ich komme aus einem nicht-mathematischen Hintergrund, also müsste ich ziemlich viel tun ein bisschen lesen)?

Oder könnten Sie eine andere Methode vorschlagen?

Vielen Dank!

Nachtrag: Hier ist Code für eine Matlab-Funktion zum Generieren einer Beispielpunktwolke mit 30 parallelen verrauschten Linien, die ich noch nicht unterscheiden kann:

function coords = generateSampleData()
coords = [];
for i = 1:30
    randOffset = i*2;
    coords = vertcat(coords, makeLine([100+randOffset 100 100], [200+randOffset 200 200], 150, 0.2));
end

figure
scatter3(coords(:,1),coords(:,2),coords(:,3),'.')

function linepts = makeLine(startpt, endpt, numpts, noiseOffset)
    dirvec = endpt - startpt;
    linepts = bsxfun( @plus, startpt, rand(numpts,1)*dirvec); % random points on line
    linepts = linepts + noiseOffset*randn(numpts,3); % add random offsets to points
end

end
Lukas K.
quelle
Wenn Sie uns einen Beispieldatensatz oder einen gefälschten Datensatz geben, der Ihrem realen Datensatz ausreichend ähnelt, oder ein Bild eines realen oder gefälschten Datensatzes, erhalten Sie möglicherweise eine bessere Antwort. Sie sagen nicht, ob es 2d oder 3d - oder 4d ...
Spacedman
Ich hätte nicht gedacht, dass es so spezifisch sein muss. Aktualisiert es trotzdem
Lukas K.
Oh, das ist viel interessanter als ich dachte. Sie haben eine ganze Wolke von Punkten, die zu einer großen Anzahl verschiedener Linien gehören, und einige verrauschte Punkte, die dies nicht tun, und im Idealfall möchten Sie alle Linien finden, auch die kleinen wie die 3 oder 4 unten rechts ...
Spacedman
Ich bin froh, dass das Problem interessant ist, jetzt hoffe ich, dass mir jemand dabei helfen kann :)
Lukas K.
ah, aber es sind keine stetigen x-, y-, T-Punktkoordinaten, sondern eine Reihe von binären (0/1) Rastern? Und wenn sich zwei Spuren kreuzen, erhalten Sie möglicherweise ein Pixel, das zu mehr als einer Spur gehört ...
Spacedman

Antworten:

3

Basierend auf dem Feedback und dem Versuch, einen effektiveren Ansatz zu finden, entwickelte ich den folgenden Algorithmus unter Verwendung eines speziellen Abstandsmaßes.

Folgende Schritte werden ausgeführt:

1) Definieren Sie eine zurückgebende Entfernungsmetrik :

Null - wenn die Punkte nicht zu einer Linie gehören

Euklidischer Abstand der Punkte - wenn die Punkte eine Linie gemäß den definierten Parametern bilden, d. H.

  • ihr Abstand ist größer oder gleich der min_line_length und

  • ihr Abstand ist kleiner oder gleich der max_line_length und

  • Die Linie besteht aus mindestens min_line_points Punkten mit einem Abstand, der kleiner als line_width / 2 von der Linie ist

2) Berechnen Sie die Abstandsmatrix mit diesem Abstandsmaß (verwenden Sie ein Beispiel der Daten für große Datenmengen; passen Sie die Linienparameter entsprechend an).

3) Finden Sie die Punkte A und B mit maximalem Abstand - brechen Sie zu Schritt 5), wenn der Abstand Null ist

Beachten Sie, dass die Punkte A und B eine Linie basierend auf unserer Definition bilden, wenn der Abstand größer als Null ist

4) Holen Sie sich alle zur Linie AB gehörenden Punkte und entfernen Sie sie aus der Distanzmatrix. Wiederholen Sie Schritt 3), um eine andere Zeile zu finden

5) Überprüfen Sie die Abdeckung des Punkts mit den ausgewählten Linien. Wenn eine erhebliche Anzahl von Punkten nicht abgedeckt ist, wiederholen Sie den gesamten Algorithmus mit angepassten Linienparametern.

6) Falls diese Datenprobe verwendet wurde, weisen Sie alle Punkte den Linien neu zu und berechnen Sie die Grenzpunkte neu.

Folgende Parameter werden verwendet:

Linienbreite - Linienbreite / 2 ist der zulässige Abstand des Punktes von der idealen Linie = r line_width

Mindestlinienlänge - Punkte mit kürzerem Abstand gehören nicht zur selben Linie = r min_line_length

maximale Linienlänge - Punkte mit größerer Entfernung gehören nicht zur selben Linie = r max_line_length

Mindestpunkte auf einer Linie - Linien mit weniger Punkten werden ignoriert =r min_line_points

Mit Ihren Daten (nach einigem Herumspielen mit Parametern) habe ich ein gutes Ergebnis erzielt, das alle 30 Zeilen abdeckt.

Geben Sie hier die Bildbeschreibung ein

Weitere Details finden Sie im Knitr-Skript

Marmite Bomber
quelle
2

Ich löste eine ähnliche, wenn auch einfachere Aufgabe mit einem Brute-Force-Ansatz. Die Vereinfachung bestand in der Annahme, dass die Linie eine lineare Funktion ist (in meinem Fall lagen sogar die Koeffizienten und der Achsenabschnitt in einem bekannten Bereich).

Dies wird daher Ihr Problem im Allgemeinen nicht lösen, wenn sich ein Partikel orthogonal zur Achse x bewegen kann (dh es verfolgt keine Funktion), aber ich poste die Lösung als mögliche Inspiration.

1) Nehmen Sie alle Kombinationen von zwei Punkten A und B mit A (x)> B (x) + Konstante (um die Symmetrie und einen hohen Fehler bei der Berechnung des Koeffizienten zu vermeiden)

2) Berechnen Sie den Koeffizienten c und den Schnittpunkt i der Linie AB

 A(y) = i + c * A(x)
 B(y) = i + c * B(x)
 A(y) - B(y) = c * (A(x) - B(x))
 c = (A(y) - B(y)) / (A(x) - B(x))
 i = A(y) - c * A(x)

3) Runden Sie den Koeffizienten und den Achsenabschnitt (dies sollte die Probleme mit Fehlern beseitigen / verringern, die durch die Punkte in einem Gitter verursacht werden).

4) Berechnen Sie für jeden Achsenabschnitt und Koeffizienten die Anzahl der Punkte auf dieser Linie

5) Betrachten Sie nur Linien mit Punkten über einem bestimmten Schwellenwert.

Einfaches Beispiel siehe hier

Marmite Bomber
quelle
Das ist im Grunde das, was ich mit RANSAC mache (außer dass ich Zufallsstichproben verwende, anstatt alle Kombinationen auszuprobieren). Das Problem für mich ist, dass ich einige Linien nicht anpasse. Das Problem ist, dass ich zu viele Linien anpasse, weil nur bei so vielen Nahpunkten selbst eine verzerrte Linie genügend Lieferanten innerhalb eines vernünftigen Schwellenwerts findet. Ich suche also nach einem Kriterium, um Linien, die zu "echten" Linien passen, von anderen zu unterscheiden.
Lukas K.
1
Ich bin mir nicht sicher, ob es wirklich der gleiche Ansatz ist. Ich unterscheide nicht zwischen dem Punkt auf einer Linie und dem Ausreißer . Ich überlege, ob zwei Vektoren zu derselben Linie gehören können oder nicht. Ich denke, das könnte viel genauer sein. Zusätzlich verwende ich die Parameter Linienbreite , minimale Linienlänge und minimale Linienpunkte , um die Auswahl zu steuern.
Marmite Bomber
OK, ich verstehe. Obwohl mit 10k Punkten und (10E + 5 wählen Sie 2) = 5E + 11 möglichen Paaren, muss ich zufällige Stichproben machen. Auch dies ist wahrscheinlich sehr empfindlich bei Abweichungen von einer geraden Linie, die den Achsenabschnitt verändern könnten. Aber ich werde es versuchen! Denkt wie minimale Länge und minimale Nr. Anzahl der Online-Punkte, die ich bereits bei meinen Versuchen verwendet habe, die Ergebnisse zu bereinigen.
Lukas K.