Schnelles Finden grober Linien in Punktmengen

12

In einer bestimmten Detektorklasse werden unsere Daten als Punktpaare in zwei Dimensionen ausgegeben, und wir möchten diese Punkte zu Linien zusammenfassen.

Die Daten sind verrauscht und werden in die eine, aber nicht in die andere Richtung zusammengefasst. Wir können nicht garantieren, dass jeder Behälter einen Treffer enthält, auch wenn jedes Detektorelement funktioniert, daher kann es zu Auslassungen kommen.

Unsere aktuelle Analysekette sieht so aus

  1. Passen Sie die Treffer für die Kalibrierung der einzelnen Detektorelemente an
  2. Finden Sie Cluster
  3. Grobe Fit-Linien zu den Clustern
  4. Verbinden Sie Cluster zu längeren linienartigen Strukturen
  5. ...

Diese Frage betrifft Schritt (3).

Wir haben für diesen Schritt eine Hough-Transformation verwendet, die gut funktioniert, aber wenn wir versuchen, vom Prüfstand zur Simulation eines vollständigen Projekts zu skalieren, wird sie unannehmbar langsam.

Ich suche einen schnelleren Weg.

Für diejenigen, die den tatsächlichen Anwendungsfall interessieren könnten, ist hier eine Flüssig-Argon-Zeitprojektionskammer

regression computer-vision pattern-recognition dmckee --- Ex-Moderator Kätzchen
quelle
1
Wir haben bei FermiLab auch eine rekursive Hough-Transformationsmethode für die Pfadverfolgung durch Proportional-Mehrdrahtkammern durchgeführt. Erik Kangas 'Abschlussarbeit enthält alle Details. Ich denke, das ist immer noch der beste Weg, dies zu tun.
Matt Knepley
1
Meinten Sie im ersten Satz "... Punktpaare ..." oder "... Punktpaare ..."?
Bill Barth

Antworten:

2

Es gibt eine probabilistische Version der Hough-Transformation (PHT), die schneller ist. Wie von Bradski & Kaehler in ihrem OpenCV-Buch beschrieben:

Die Idee ist, dass der Peak ohnehin hoch genug sein wird, dann reicht es aus, ihn nur in einem Bruchteil der Zeit zu treffen, um ihn zu finden.

Die OpenCV-Bibliothek präsentiert eine Implementierung für das PHT.

Es gibt andere Alternativen. Es ist nicht schwierig, eine verteilte Version der Hough-Transformation zu erstellen . Teilen Sie Ihre Punktmenge einfach in kleinere Teile auf und verwenden Sie das MapReduce-Framework, um alle Akkumulatoren zusammenzufassen. Eine andere Idee ist, eine grobe Version der Hough-Transformation unter Verwendung eines Parameterraums mit niedriger Auflösung durchzuführen . Wählen Sie Ihre besten Kandidaten aus und führen Sie eine feinere Iteration aus, indem Sie einen Parameterraum mit einer höheren Auflösung verwenden. Vielleicht ist dies die Idee hinter der FHT des Gandalf.

TH.
quelle
1
Die PHT wurde vorgeschlagen in: Matas, J. und Galambos, C. und Kittler, JV, Robuster Nachweis von Linien unter Verwendung der progressiven probabilistischen Hough-Transformation. CVIU 78 1, S. 119-137 (2000).
TH.
Das Verfahren kann dann auf mehrere Schritte verallgemeinert werden, was Gandalf tut.
dmckee --- Ex-Moderator Kätzchen
Übrigens - In der Zeit, seit ich diese Frage gestellt habe, hat ein Kollege unserem Code ein Modul hinzugefügt, das die progressive probabilistische Version der Transformation verwendet. Dies war mit mehreren damit verbundenen Änderungen verbunden, so dass es schwierig ist, genau zu bestimmen, welchen Unterschied es machte, aber es ist Teil eines Pakets, das einige Schritte der Analyse erheblich beschleunigt hat. Also werde ich dies als den "gewinnenden" Rat annehmen.
dmckee --- Ex-Moderator Kätzchen
5

Ich Kollege hat die Fast Hough Transformation gefunden in der Gandalf-Bibliothek gefunden , die sehr vielversprechend aussieht, aber möglicherweise sehr viel Integrationsarbeit erfordert. Deshalb suche ich nach anderen Ansätzen.

Interessant ist die Gandalf-Implementierung: Sie wertet den Speicherplatz rekursiv aus, als würde sie einen Quad- oder Oct-Baum durchqueren. Regionen ohne große Dichte werden im Laufe der Zeit verworfen.

dmckee --- Ex-Moderator Kätzchen
quelle