Publicité E▼
⇨ voir la définition de Wikipedia
Publicité ▼
Wikipedia
Die Hough-Transformation (Sprechweise [hʌf]) ist ein robustes globales Verfahren zur Erkennung von Geraden, Kreisen oder beliebigen anderen parametrisierbaren geometrischen Figuren in einem binären Gradientenbild, also einem schwarz/weiß Bild, nach einer Kantenerkennung. Das Verfahren wurde 1962 von Paul V. C. Hough unter dem Namen „Method and Means for Recognizing Complex Patterns“ patentiert.
Zur Erkennung von geometrischen Objekten wird ein Dualraum erschaffen (speziell: Parameterraum, Hough-Raum), in den für jeden Punkt im Bild, der auf einer Kante liegt, alle möglichen Parameter der zu findenden Figur im Dualraum eingetragen werden. Jeder Punkt im Dualraum entspricht damit einem geometrischen Objekt im Bildraum. Bei der Gerade kann das z. B. die Steigung und der y-Achsen-Abschnitt sein, beim Kreis der Mittelpunkt und Radius. Danach wertet man den Dualraum aus, indem man nach Häufungen sucht, die dann der gesuchten Figur entsprechen.
Inhaltsverzeichnis |
Bei der Geradenerkennung mittels der Hough-Transformation muss man zuerst geeignete Parameter für eine Gerade finden. Steigung und y-Achsen-Abschnitt eignen sich nur bedingt, da zur y-Achse parallele Geraden eine unendliche Steigung haben und daher im (für die Berechnung zwangsläufig) endlichen Parameterraum nicht mehr abgebildet werden können. Dieses Problem kann man umgehen, wenn man eine zweite Hough-Transformation auf dem um 90° gedrehten Bildraum durchführt, was aber recht umständlich ist. In der neueren Literatur überwiegt daher der Ansatz, Geraden durch ihre Hessesche Normalform zu repräsentieren. Als Parameter wählt man den Winkel und den (euklidischen) Abstand d, wobei der Winkel zwischen der Normalen der Gerade (= Lot) und der x-Achse ist, und den Abstand vom Ursprung zum Lotfußpunkt auf der Gerade bezeichnet.
Damit haben wir die Parametergleichung , mit der wir für alle Punkte auf Kanten im Bild die entsprechende Kurve im Dualraum einzeichnen. Dabei bezeichnen und die Variablen, während x und y jetzt zu Parametern umfunktioniert wurden. x und y sind die Koordinaten der vorher detektierten Kantenpunkte. Das Ausgangsbild wird zunächst einem Kantendetektor-Algorithmus unterzogen (z. B. Canny- oder Sobel-Filter) und dadurch der zu untersuchende Punktraum auf mögliche Kanten eingeschränkt.
Der Dualraum wird nun also von und aufgespannt. Zu jedem errechneten Wert wird jetzt im Dualraum (repräsentiert als Matrix) an der Stelle der Wert um 1 erhöht, also quasi für die dadurch repräsentierte Gerade "gevotet". Deshalb nennt man die Matrix auch oft "Voting-Matrix".
Der nächste Schritt besteht in der Analyse des Dualraums, bei der man nach Häufungspunkten in der Voting-Matrix sucht. Diese Häufungspunkte im Dualraum repräsentieren mögliche Geraden im Bildraum, da sie offensichtlich unter dem gleichen Winkel mit der gleichen Entfernung vom Ursprung repräsentiert werden.
Aufgrund der Unabhängigkeit der einzelnen Zellen des Parameterraumes zueinander bei der Berechnung der Häufungspunkte ist die Hough-Transformation leicht parallelisierbar.
Ein einfacher Algorithmus um eine Hough-Akkumulation durchzuführen könnte etwa so aussehen:
max_d := sqrt((1/2 * bildhöhe)^2 + (1/2 * bildbreite)^2); min_d := max_d * -1; houghRaum[0...][min_d...max_d] := 0 foreach pixel != 0 do for := 0 to do d := pixelx * cos() + pixely * sin() houghRaum[][d]++ end end
Das Resultat der Akkumulation ist ein zweidimensionales Array, welches die Häufigkeit des Auftretens für jede Kombination aus und enthält. Weil die Geraden nicht gerichtet sind, muss nur der Bereich von 0 bis ausgewertet werden, da sich danach die Geraden mit den bereits berechneten decken. In der Praxis wird häufig die Bildmitte als Koordinatenursprung verwendet.
Wie oben erwähnt kann die Hough-Transformation – in abgewandelter Weise – nicht nur für das Detektieren von Geraden, sondern z. B. auch von Kreisen eingesetzt werden. Ausgehend vom Kantenbild wird jedes Kantenpixel als von Kreisen eines bestimmten Radius erzeugt angesehen. Die Transformation in den Hough-Raum funktioniert so, dass man im Akkumulator alle Kreismittelpunkte einträgt, die zu diesem Kantenpixel führen könnten (jedes Akkumulatormittelpunktpixel um 1 erhöhen). Wenn nun die Punkte im Kantenbild einen Kreis repräsentieren, ist in der Akkumulatormatrix ein besonders hoher Wert an der dazugehörigen Stelle des Kreismittelpunkts eingetragen, da dort sehr viele Kantenpixel des Kreises für den Mittelpunkt abgestimmt haben. Die Maxima im Hough-Raum repräsentieren also die Kreismittelpunkte.
Die ersten zwei Dimensionen des Hough-Raums entsprechen in diesem Fall denen des Bildraums, da die (x,y)-Koordinaten in beiden Fällen die Lage des Kreismittelpunktes beschreiben. Zusätzlich dazu ist laut der Kreisgleichung der Radius r der 3. Parameter, der beachtet werden muss. Man spricht bei Kreisen daher von einem 3-dimensionalen Hough-Raum (xc, yc, r). Die Wertegrenzen für den Radius müssen fest vorgegeben werden (z. B. mittels a priori-Wissen).
Für Ellipsen und jede andere, durch eine parametrische Gleichung darstellbare Form, kann dieses Verfahren ebenfalls angewendet werden. Jedoch steigt die Dimension des Hough-Raums mit der Variablenzahl (bei Ellipsen: 5), was den Rechenaufwand deutlich steigert.
Es ist ebenfalls möglich, eine nicht durch parametrische Repräsentation darstellbare Struktur zu finden. Dieses Verfahren wird generalisierte Hough-Transformation (GHT) genannt. So können beliebige Formen in einem Bild gefunden werden. Das Prinzip hierbei ist, dass man eine formabhängige Lookup-Tabelle errechnet. In dieser sind die möglichen Vektoren zu einem Referenzpunkt den unterschiedlichen Gradientenrichtungen zugeordnet. Durch einige Umformungen der Tabelle kann man auch rotierte bzw. skalierte Versionen der gesuchten Formen finden, was zu einer hohen Robustheit führt. Mittels der Lookup-Tabelle kann man nun das Kantenbild in den Hough-Raum überführen; Maxima stellen die gefundenen Referenzpunkte dar.
In ihrer ursprünglichen Form ist die Hough-Transformation daher selbst in einem Parallelrechner z. B. nicht zur Analyse von Videosequenzen in Echtzeit geeignet, wie sie zur Erkennung von Fahrbahnmarkierungen beim autonomen Fahren notwendig ist. Es gibt jedoch eine kaum überschaubare Zahl von Weiterentwicklungen der Hough-Transformation, häufig „Fast Hough Transform“ benannt, die sich dieses Problems annehmen (siehe z. B. Fast Hough Transform).
Applets zur Visualisierung der Hough-Transformation:
Contenu de sensagent
dictionnaire et traducteur pour sites web
Alexandria
Une fenêtre (pop-into) d'information (contenu principal de Sensagent) est invoquée un double-clic sur n'importe quel mot de votre page web. LA fenêtre fournit des explications et des traductions contextuelles, c'est-à-dire sans obliger votre visiteur à quitter votre page web !
Essayer ici, télécharger le code;
SensagentBox
Avec la boîte de recherches Sensagent, les visiteurs de votre site peuvent également accéder à une information de référence pertinente parmi plus de 5 millions de pages web indexées sur Sensagent.com. Vous pouvez Choisir la taille qui convient le mieux à votre site et adapter la charte graphique.
Solution commerce électronique
Augmenter le contenu de votre site
Ajouter de nouveaux contenus Add à votre site depuis Sensagent par XML.
Parcourir les produits et les annonces
Obtenir des informations en XML pour filtrer le meilleur contenu.
Indexer des images et définir des méta-données
Fixer la signification de chaque méta-donnée (multilingue).
Renseignements suite à un email de description de votre projet.
Jeux de lettres
Les jeux de lettre français sont :
○ Anagrammes
○ jokers, mots-croisés
○ Lettris
○ Boggle.
Lettris
Lettris est un jeu de lettres gravitationnelles proche de Tetris. Chaque lettre qui apparaît descend ; il faut placer les lettres de telle manière que des mots se forment (gauche, droit, haut et bas) et que de la place soit libérée.
boggle
Il s'agit en 3 minutes de trouver le plus grand nombre de mots possibles de trois lettres et plus dans une grille de 16 lettres. Il est aussi possible de jouer avec la grille de 25 cases. Les lettres doivent être adjacentes et les mots les plus longs sont les meilleurs. Participer au concours et enregistrer votre nom dans la liste de meilleurs joueurs ! Jouer
Dictionnaire de la langue française
Principales Références
La plupart des définitions du français sont proposées par SenseGates et comportent un approfondissement avec Littré et plusieurs auteurs techniques spécialisés.
Le dictionnaire des synonymes est surtout dérivé du dictionnaire intégral (TID).
L'encyclopédie française bénéficie de la licence Wikipedia (GNU).
Copyright
Les jeux de lettres anagramme, mot-croisé, joker, Lettris et Boggle sont proposés par Memodata.
Le service web Alexandria est motorisé par Memodata pour faciliter les recherches sur Ebay.
La SensagentBox est offerte par sensAgent.
Traduction
Changer la langue cible pour obtenir des traductions.
Astuce: parcourir les champs sémantiques du dictionnaire analogique en plusieurs langues pour mieux apprendre avec sensagent.
calculé en 0,046s