Hough-Transformation
Verwendung der Gradientenrichtung zur Verringerung der Anzahl der StimmenBearbeiten
Eine von O’Gorman und Clowes vorgeschlagene Verbesserung kann zur Erkennung von Linien verwendet werden, wenn man berücksichtigt, dass der lokale Gradient der Bildintensität notwendigerweise orthogonal zur Kante verläuft. Da bei der Kantenerkennung im Allgemeinen der Betrag des Intensitätsgradienten berechnet wird, wird die Richtung des Gradienten oft als Nebeneffekt ermittelt. Wenn ein gegebener Koordinatenpunkt (x,y) tatsächlich auf einer Linie liegt, dann ergibt die lokale Richtung des Gradienten den θ-Parameter, der der besagten Linie entspricht, und der r-Parameter ergibt sich dann unmittelbar. (Shapiro und Stockman, 305) Die Richtung der Steigung kann mit einer Genauigkeit von 20° geschätzt werden, wodurch die Sinuskurve von vollen 180° auf etwa 45° verkürzt wird. Dies verringert die Berechnungszeit und hat den interessanten Effekt, dass die Anzahl der nutzlosen Abstimmungen reduziert wird, wodurch die Sichtbarkeit der Spikes, die echten Linien im Bild entsprechen, erhöht wird.
Kernel-basierte Hough-Transformation (KHT)
Fernandes und Oliveira schlugen ein verbessertes Abstimmungsschema für die Hough-Transformation vor, das es einer Software-Implementierung ermöglicht, selbst bei relativ großen Bildern (z. B. 1280×960) eine Echtzeitleistung zu erzielen. Die Kernel-basierte Hough-Transformation verwendet die gleiche ( r , θ ){\displaystyle (r,\theta )}
von Duda und Hart vorgeschlagene Parametrisierung, arbeitet aber mit Clustern von annähernd kollinearen Pixeln. Für jeden Cluster werden die Stimmen mit einem orientierten elliptisch-gaußschen Kernel abgegeben, der die Unsicherheit modelliert, die mit der am besten passenden Linie in Bezug auf den entsprechenden Cluster verbunden ist. Dieser Ansatz verbessert nicht nur die Leistung des Abstimmungsschemas erheblich, sondern führt auch zu einem wesentlich saubereren Akkumulator und macht die Transformation robuster gegenüber der Erkennung von Störlinien.
3D-Kernel-basierte Hough-Transformation für die Ebenendetektion (3DKHT)Edit
Limberger und Oliveira schlugen ein deterministisches Verfahren für die Ebenendetektion in unorganisierten Punktwolken vor, dessen Kosten n log ( n ) {\displaystyle n\log(n)} sind
in der Anzahl der Abtastwerte liegt und eine Echtzeitleistung für relativ große Datensätze (bis zu 10 5 {\displaystyle 10^{5}}
Punkte auf einer 3,4 GHz CPU). Es basiert auf einer schnellen Hough-Transformations-Abstimmungsstrategie für ebene Regionen, inspiriert von der Kernel-basierten Hough-Transformation (KHT). Diese 3D-Kernel-basierte Hough-Transformation (3DKHT) verwendet einen schnellen und robusten Algorithmus zur Segmentierung von Clustern annähernd koplanarer Proben und gibt Stimmen für einzelne Cluster (statt für einzelne Proben) auf einer ( θ , ϕ , ρ {\displaystyle \theta ,\phi ,\rho }
) sphärischen Akkumulator unter Verwendung eines trivariaten Gaußschen Kerns. Der Ansatz ist um mehrere Größenordnungen schneller als bestehende (nicht-deterministische) Techniken zur Erkennung von Ebenen in Punktwolken, wie RHT und RANSAC, und skaliert besser mit der Größe der Datensätze. Es kann für jede Anwendung verwendet werden, die eine schnelle Erkennung von ebenen Merkmalen in großen Datensätzen erfordert.
Hough-Transformation von Kurven und ihre Verallgemeinerung für analytische und nicht-analytische FormenBearbeiten
Obwohl die oben beschriebene Version der Transformation nur für die Erkennung von Geraden gilt, kann eine ähnliche Transformation für die Erkennung jeder Form verwendet werden, die durch einen Satz von Parametern dargestellt werden kann. Ein Kreis zum Beispiel kann in einen Satz von drei Parametern transformiert werden, die seinen Mittelpunkt und Radius darstellen, so dass der Hough-Raum dreidimensional wird. Auch beliebige Ellipsen und Kurven können auf diese Weise gefunden werden, ebenso wie jede Form, die sich leicht durch eine Reihe von Parametern ausdrücken lässt.
Die Verallgemeinerung der Hough-Transformation zur Erkennung analytischer Formen in Räumen beliebiger Dimensionalität wurde von Fernandes und Oliveira vorgeschlagen. Im Gegensatz zu anderen auf der Hough-Transformation basierenden Ansätzen für analytische Formen hängt die Technik von Fernandes weder von der Form ab, die man erkennen will, noch von der Art der Eingabedaten. Die Erkennung kann durch Änderung des angenommenen Geometriemodells, in dem die Daten kodiert wurden (z. B. euklidischer Raum, projektiver Raum, konforme Geometrie usw.), auf eine Art von analytischer Form ausgerichtet werden, während die vorgeschlagene Formulierung unverändert bleibt. Außerdem garantiert sie, dass die beabsichtigten Formen mit der kleinstmöglichen Anzahl von Parametern dargestellt werden, und sie ermöglicht die gleichzeitige Erkennung verschiedener Arten von Formen, die am besten zu einem Eingabesatz von Einträgen mit unterschiedlichen Dimensionalitäten und unterschiedlichen geometrischen Definitionen passen (z. B. die gleichzeitige Erkennung von Ebenen und Kugeln, die am besten zu einem Satz von Punkten, Geraden und Kreisen passen).
Für kompliziertere Formen in der Ebene (d. h., Für kompliziertere Formen in der Ebene (d. h. Formen, die nicht analytisch in einem 2D-Raum dargestellt werden können) wird die verallgemeinerte Hough-Transformation verwendet, die es einem Merkmal ermöglicht, für eine bestimmte Position, Orientierung und/oder Skalierung der Form mit Hilfe einer vordefinierten Nachschlagetabelle zu stimmen.
Die Hough-Transformation akkumuliert Beiträge von allen Pixeln in der erkannten Kante.
Die Änderung des Algorithmus zur Erkennung von Kreisformen anstelle von Linien ist relativ einfach.
- Zunächst wird der Akkumulatorraum erstellt, der aus einer Zelle für jedes Pixel besteht. Zu Beginn wird jede Zelle auf 0 gesetzt.
- Für jeden Kantenpunkt (i, j) im Bild werden alle Zellen inkrementiert, die gemäß der Gleichung eines Kreises ( i – a ) 2 + ( j – b ) 2 = r 2 {\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}
könnte der Mittelpunkt eines Kreises sein. Diese Zellen werden durch den Buchstaben a {\displaystyle a}
in der Gleichung dargestellt.
- Finde für jeden möglichen Wert von a {\displaystyle a}
, der im vorherigen Schritt gefunden wurde, alle möglichen Werte von b {\displaystyle b}
, die die Gleichung erfüllen.
- Suche nach lokalen Maxima im Akkumulatorraum. Diese Zellen stellen Kreise dar, die vom Algorithmus erkannt wurden.
Wenn wir den Radius des Kreises, den wir zu finden versuchen, nicht im Voraus kennen, können wir einen dreidimensionalen Akkumulatorraum verwenden, um nach Kreisen mit einem beliebigen Radius zu suchen. Dies ist natürlich rechenaufwändiger.
Diese Methode kann auch Kreise erkennen, die teilweise außerhalb des Akkumulatorraums liegen, solange noch genügend Fläche des Kreises darin vorhanden ist.
Erkennung von 3D-Objekten (Ebenen und Zylinder)Bearbeiten
Die Hough-Transformation kann auch zur Erkennung von 3D-Objekten in Entfernungsdaten oder 3D-Punktwolken verwendet werden. Die Erweiterung der klassischen Hough-Transformation zur Erkennung von Ebenen ist recht einfach. Eine Ebene wird durch ihre explizite Gleichung z = a x x + a y y + d {\displaystyle z=a_{x}x+a_{y}y+d}
, wofür wir einen 3D-Hough-Raum verwenden können, der a x {\displaystyle a_{x}}
, a y {\displaystyle a_{y}}
und d {\displaystyle d}
. Diese Erweiterung leidet unter denselben Problemen wie ihr 2D-Gegenstück, d. h., nahe horizontale Ebenen können zuverlässig erkannt werden, während sich die Leistung verschlechtert, wenn die Richtung der Ebene vertikal wird (große Werte von a x {\displaystyle a_{x}}
und a y {\displaystyle a_{y}}
verstärken das Rauschen in den Daten). Diese Formulierung der Ebene wurde für die Erkennung von Ebenen in Punktwolken verwendet, die durch Laserscanning aus der Luft gewonnen wurden, und funktioniert sehr gut, da in diesem Bereich alle Ebenen nahezu horizontal sind.
Für die verallgemeinerte Ebenendetektion mittels Hough-Transformation kann die Ebene durch ihren Normalenvektor n {\displaystyle n} parametrisiert werden.
(unter Verwendung sphärischer Koordinaten) und ihren Abstand vom Ursprung ρ {\displaystyle \rho }
ergibt einen dreidimensionalen Hough-Raum. Dies führt dazu, dass jeder Punkt in den Eingabedaten für eine sinusförmige Fläche im Hough-Raum stimmt. Der Schnittpunkt dieser sinusförmigen Flächen zeigt das Vorhandensein einer Ebene an. Ein allgemeinerer Ansatz für mehr als 3 Dimensionen erfordert Suchheuristiken, um praktikabel zu bleiben.
Die Hough-Transformation wurde auch verwendet, um zylindrische Objekte in Punktwolken mit einem zweistufigen Ansatz zu finden. Im ersten Schritt wird die Ausrichtung des Zylinders ermittelt und im zweiten Schritt die Position und der Radius.
Verwendung gewichteter MerkmaleBearbeiten
Eine gemeinsame Variante ist ein Detail. Das heißt, die Suche nach den Bins mit der höchsten Anzahl in einem Schritt kann verwendet werden, um den Bereich der gesuchten Werte im nächsten Schritt einzuschränken.
Sorgfältig gewählter ParameterraumBearbeiten
Ein hochdimensionaler Parameterraum für die Hough-Transformation ist nicht nur langsam, sondern kann, wenn er ohne Voraussicht implementiert wird, leicht den verfügbaren Speicher überfordern. Selbst wenn die Programmierumgebung die Zuweisung eines Arrays erlaubt, das größer ist als der verfügbare Speicherplatz durch virtuellen Speicher, wird die Anzahl der dafür erforderlichen Seitenwechsel sehr anspruchsvoll sein, weil das Akkumulator-Array in einer zufälligen Zugriffsweise verwendet wird und selten in einem zusammenhängenden Speicher stehen bleibt, wenn es von Index zu Index springt.
Betrachten Sie die Aufgabe, Ellipsen in einem 800×600 Bild zu finden. Unter der Annahme, dass die Radien der Ellipsen entlang der Hauptachsen orientiert sind, ist der Parameterraum vierdimensional. (x,y) definiert den Mittelpunkt der Ellipse, und a und b bezeichnen die beiden Radien. Wenn der Mittelpunkt an einer beliebigen Stelle im Bild liegen kann, wird die Bedingung 0<x<800 und 0<y<600 hinzugefügt. Wenn die Radien die gleichen Werte wie die Randbedingungen erhalten, bleibt ein spärlich gefülltes Akkumulatorfeld mit mehr als 230 Milliarden Werten übrig.
Ein so konzipiertes Programm wird wahrscheinlich nicht genügend Speicher zuweisen können. Das bedeutet nicht, dass das Problem nicht gelöst werden kann, sondern nur, dass neue Wege gefunden werden müssen, um die Größe des Akkumulator-Arrays einzuschränken, so dass es machbar wird. Zum Beispiel:
- Wenn man davon ausgehen kann, dass die Ellipsen jeweils vollständig im Bild enthalten sind, kann der Bereich der Radien reduziert werden. Am größten können die Radien sein, wenn der Mittelpunkt der Ellipse in der Mitte des Bildes liegt, so dass sich die Ränder der Ellipse bis zu den Kanten erstrecken. In diesem Extremfall können die Radien jeweils nur halb so groß sein wie die Bildgröße, die in dieselbe Richtung ausgerichtet ist. Wenn man den Bereich von a und b auf diese Weise reduziert, verringert sich das Akkumulatorfeld auf 57 Milliarden Werte.
- Wenn man bei der Schätzung der Hough-Transformation Genauigkeit gegen Platz tauscht, werden Beiträge von allen Pixeln in der erkannten Kante akkumuliert. Die Hough-Transformation akkumuliert Beiträge von allen Pixeln in der erkannten Kante. der Mitte: Wenn der Mittelpunkt sowohl auf der x- als auch auf der y-Achse um 3 verschoben wird, verringert sich die Größe des Akkumulatorfelds auf etwa 6 Milliarden Werte.
- Gegengenauigkeit für den Raum bei der Schätzung der Radien: Wenn die Radien so geschätzt werden, dass sie jeweils um 5 abweichen, verringert sich die Größe des Akkumulatorfelds um etwa 256 Millionen Werte.
- Beschneiden Sie das Bild auf die Bereiche, die Sie interessieren. Dies ist bildabhängig und daher nicht vorhersehbar, aber stellen Sie sich einen Fall vor, in dem alle interessanten Kanten eines Bildes im oberen linken Quadranten des Bildes liegen. Das Akkumulatorfeld kann in diesem Fall noch weiter verkleinert werden, indem alle 4 Parameter um den Faktor 2 eingeschränkt werden, so dass sich ein Gesamtverkleinerungsfaktor von 16 ergibt.
Wenn man nur die ersten drei dieser Einschränkungen auf das genannte Beispiel anwendet, wird die Größe des Akkumulatorfeldes um fast den Faktor 1000 verringert, so dass es auf eine Größe reduziert wird, die viel eher in den Speicher eines modernen Computers passt.
Effizienter Algorithmus zur Erkennung von EllipsenBearbeiten
Yonghong Xie und Qiang Ji zeigen einen effizienten Weg zur Implementierung der Hough-Transformation für die Erkennung von Ellipsen, indem sie die Speicherprobleme überwinden. Wie im Algorithmus (auf Seite 2 des Papiers) erläutert, verwendet dieser Ansatz nur einen eindimensionalen Akkumulator (für die Nebenachse), um Ellipsen im Bild zu erkennen. Die Komplexität ist O(N3) für die Anzahl der Punkte im Bild, die nicht Null sind.
Leave a Reply