Die Hough-Transformation ist eine Technik zur Merkmalsextraktion, die in der Bildanalyse, im maschinellen Sehen, in der Mustererkennung und in der digitalen Bildverarbeitung eingesetzt wird. Ihr Zweck ist es, unvollkommene Instanzen von Objekten innerhalb einer bestimmten Klasse von Formen durch ein Abstimmungsverfahren zu finden. Dieses Abstimmungsverfahren wird in einem Parameterraum durchgeführt, aus dem Objektkandidaten als lokale Maxima in einem Akkumulatorraum gewonnen werden, der explizit vom Algorithmus konstruiert wird. Mathematisch handelt es sich um die Radon-Transformation in der Ebene, die seit mindestens 1917 bekannt ist, aber die Hough-Transformation bezieht sich speziell auf ihre Verwendung in der Bildanalyse.
Die klassische Hough-Transformation befasste sich mit der Erkennung von Linien in einem Bild, wurde aber seitdem auf die Erkennung von Positionen beliebiger Formen erweitert, am häufigsten von Kreisen oder Ellipsen. Die Transformation, wie sie heute allgemein verwendet wird, wurde 1972 von Richard Duda und Peter Hart erfunden, die sie als "verallgemeinerte Hough-Transformation" nach dem verwandten Patent von Paul Hough aus dem Jahr 1962 bezeichneten. Sie wurde in der Computer-Vision-Gemeinschaft durch Dana H. Ballard mit einem Journalartikel von 1981 mit dem Titel "Generalizing the Hough transform to detect arbitrary shapes" populär gemacht.
Geschichte
Die Hough-Transformation wurde ursprünglich von Paul Hough im Jahr 1959 für die maschinelle Analyse von Blasenkammerfotografien erfunden. Sie wurde 1962 als US-Patent 3.069.654 patentiert und der US-Atomenergiekommission unter dem Namen "Method and Means for Recognizing Complex Patterns" zugewiesen. Dieses Patent verwendete eine Steigungs-Achsenabschnitt-Parametrisierung für gerade Linien, was ungeschickt zu einem unbegrenzten Transformationsraum führte, da die Steigung gegen unendlich gehen kann.
Die heute allgemein verwendete Rho-Theta-Parametrisierung wurde erstmals in einem Artikel von Richard Duda und Peter Hart aus dem Jahr 1972 beschrieben, "Use of the Hough Transformation to Detect Lines and Curves in Pictures", veröffentlicht in Communications of the ACM. Diese Parametrisierung war bereits seit mindestens den 1930er Jahren Standard für die Radon-Transformation. Frank O'Gorman und M.B. Clowes veröffentlichten 1976 eine Variation in IEEE Transactions on Computers mit dem Titel "Finding Picture Edges Through Collinearity of Feature Points". Die Geschichte, wie die moderne Form erfunden wurde, wird in Peter Harts Artikel von 2009 "How the Hough Transform was Invented" in IEEE Signal Processing Magazine detailliert beschrieben.
Theorie
Bei der automatisierten Analyse digitaler Bilder tritt oft ein Teilproblem auf, nämlich die Erkennung einfacher Formen wie gerader Linien, Kreise oder Ellipsen. Ein Kantendetektor kann als Vorverarbeitungsstufe verwendet werden, um Bildpunkte auf der gewünschten Kurve zu erhalten. Aufgrund von Unvollkommenheiten in den Bilddaten oder im Kantendetektor kann es jedoch zu fehlenden Punkten oder räumlichen Abweichungen zwischen der idealen Form und verrauschten Kantenpunkten kommen. Die Hough-Transformation begegnet diesem Problem, indem sie ein explizites Abstimmungsverfahren über eine Menge parametrisierter Bildobjekte durchführt, wodurch es möglich wird, Kantenpunkte zu Objektkandidaten zu gruppieren.
Erkennung von Linien
Der einfachste Fall ist die Erkennung gerader Linien. Im Allgemeinen kann eine Linie y = mx + b als Punkt (b, m) im Parameterraum dargestellt werden, aber vertikale Linien stellen ein Problem dar, da die Steigungswerte unbegrenzt sind. Duda und Hart schlugen die Hesse-Normalform vor: r = x cos(theta) + y sin(theta), wobei r der Abstand vom Ursprung zum nächsten Punkt auf der Linie ist und theta der Winkel zwischen der x-Achse und der Linie, die den Ursprung mit diesem nächsten Punkt verbindet. Jeder Vektor auf der Linie ist senkrecht zum Liniensegment der Länge r vom Ursprung. Der Schnittpunkt liegt bei P0 = (r cos(theta), r sin(theta)). Für jeden Punkt P auf der Linie muss der Vektor P - P0 orthogonal zu P0 sein, was (P - P0) dot P0 = 0 erzwingt, was sich zu r(x cos(theta) + y sin(theta)) = r^2(cos^2(theta) + sin^2(theta)) vereinfacht.
Algorithmus und Abstimmungsverfahren
In der Praxis diskretisiert die Hough-Transformation den Parameterraum in ein Akkumulatorfeld. Für jeden Kantenpunkt im Bild berechnet der Algorithmus alle möglichen Parameterwerte (z. B. r und theta für Linien), die einer Form entsprechen könnten, die durch diesen Punkt verläuft, und erhöht die entsprechenden Akkumulatorzellen. Nach der Verarbeitung aller Punkte deuten lokale Maxima im Akkumulator auf wahrscheinliche Formkandidaten hin. Dieses Abstimmungsverfahren ist robust gegenüber Rauschen und fehlenden Daten, da es nicht erfordert, dass alle Punkte auf einer Form perfekt ausgerichtet sind.
Erweiterungen und Anwendungen
Die verallgemeinerte Hough-Transformation, eingeführt von Dana Ballard im Jahr 1981, erweitert die Technik auf beliebige Formen, indem sie einen Referenzpunkt und eine Tabelle von Kantenorientierungen verwendet. Dies ermöglicht die Erkennung komplexer Formen über Linien, Kreise und Ellipsen hinaus. Die Transformation wurde in Bereichen wie autonomes Fahren, medizinische Bildgebung und industrielle Inspektion weit verbreitet eingesetzt. In Computer-Vision-Systemen wird sie oft mit Kantenerkennungsalgorithmen kombiniert, um Objekte in digitalen Bildverarbeitungspipelines zu identifizieren. Ihre mathematische Grundlage in der Radon-Transformation verbindet sie mit breiteren Bildanalysetechniken, die in maschinellem Lernen und künstlicher Intelligenz verwendet werden.
Einschränkungen und Varianten
Eine Einschränkung der klassischen Hough-Transformation sind ihre Rechenkosten, insbesondere bei hochdimensionalen Parameterräumen. Varianten wie die probabilistische Hough-Transformation und die Hough-Kreistransformation wurden entwickelt, um die Effizienz zu verbessern. Die probabilistische Version sampelt eine Teilmenge von Kantenpunkten, um die Berechnung zu reduzieren, während die Kreistransformation einen dreidimensionalen Parameterraum (Mittelpunkt x, Mittelpunkt y, Radius) verwendet. Diese Varianten werden häufig in Bibliotheken wie OpenCV implementiert und in Echtzeitsystemen verwendet, einschließlich solcher in autonomen Fahrzeugen und Robotik.
Siehe auch
- Radon-Transformation
- Kantenerkennung
- Computer-Vision
- Bildverarbeitung