Transformacja Hougha

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Transformacja Hougha (ang. Hough transform) – metoda wykrywania regularnych kształtów w widzeniu komputerowym. Jest szczególnym przypadkiem transformaty Radona znanej od 1917 roku[1], [2].

Oryginalna metoda Hougha służy do wykrywania prostych. Metodę tę później uogólniono na wykrywanie kształtów dających się opisać analitycznie np. okręgów (Richard Duda and Peter Hart, 1972)[3] oraz na wykrywanie dowolnych kształtów (Dana H. Ballard, 1981)[4].

Historia[edytuj | edytuj kod]

Transformata jako metoda detekcji prostych została wprowadzona w 1962 roku przez Paula Hougha i opatentowana (US Patent Office No. 3.069.654[5])[6].

Zasada wykrywania prostych[edytuj | edytuj kod]

Każda z prostych może być jednoznacznie przedstawiona w tzw. przestrzeni Hougha, która opisana jest w układzie współrzędnych θ, ρ

Obraz (np. z kamery) jest reprezentowany przez piksele o współrzędnych kartezjańskich x, y. Prostą można zapisać jako kąt nachylenia θ i odległość od początku układu współrzędnych ρ.

\, x\cos (\phi)+\, y\sin (\phi) =\rho

Są to też dwie współrzędne, dlatego można utworzyć prostokątny zbiór punktów w układzie współrzędnych θ, ρ (przestrzeń parametrów), w którym każdy punkt reprezentuje prostą. Ponieważ oryginalny obraz ma ograniczone rozmiary, współrzędne ρ i θ zbioru punktów reprezentujących proste są ograniczone: 0 < θ < π, -R < ρ < R, gdzie R – przekątna obrazu, więc zbiór ten można ograniczyć, z założoną dokładnością, do skończonej liczby punktów. Wykrywanie linii opiera się na głosowaniu – charakterystyczny piksel (wykryty np. w wyniku wykrywania krawędzi) "głosuje" tj. dodaje pewną jednostkową liczbę do wartości tych punktów w zbiorze prostych, które reprezentują proste przechodzące przez ten piksel. Wynikowy zbiór, potraktowany jako obraz, zawiera maksima (jasne punkty), reprezentujące proste wykryte w oryginalnym obrazie.

Przypisy

  1. Johann Radon. Über die Bestimmung von Funktionen durch ihre Integralwerte längs gewisser Mannigfaltigkeiten. „Ber. Verh. Säche. Akad. Wiss.”. 69, s. 262-277, 1917. Leipzig. 
  2. S. R. Deans, Hough transform from the Radon transform, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 3, no. 2, 1981, 185-188.
  3. Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11–15 (January, 1972)
  4. Ballard, D.H., "Generalizing the Houghtransform to detectarbitraryshapes," Pattern Recognition, Elsevier, Volume 13, Issue 2, pp. 111–122 (1981)
  5. US Patent No. 3.069.654
  6. Hough P.V.C, Method and means for recognizing complex patterns. U.S. Patent 3,069,654, Dec. 18, 1962.