Transformacja Hougha

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

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

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

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

x\cos(\theta )+\,y\sin(\theta )=\rho .

Są to też dwie współrzędne, dlatego można utworzyć prostokątny zbiór punktów w układzie współrzędnych $\theta ,\rho$ (przestrzeń parametrów), w którym każdy punkt reprezentuje prostą. Ponieważ oryginalny obraz ma ograniczone rozmiary, współrzędne $\rho$ i $\theta$ zbioru punktów reprezentujących proste są ograniczone: $0<\theta <\pi ,\ -R<\rho <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

↑ 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.
↑ S.R. Deans, Hough transform from the Radon transform, „IEEE Transactions on Pattern Analysis and Machine Intelligence”, vol. 3, no. 2, 1981, 185-188.
↑ Duda R.O. and P.E. Hart, Use of the Hough Transformation to Detect Lines and Curves in Pictures, Comm. ACM, Vol. 15, s. 11–15 (January, 1972).
↑ Ballard, D.H., Generalizing the Houghtransform to detectarbitraryshapes, „Pattern Recognition”, Elsevier, Volume 13, Issue 2, s. 111–122 (1981).
↑ US Patent No. 3.069.654.
↑ Hough P.V.C, Method and means for recognizing complex patterns, U.S. Patent 3,069,654, Dec. 18, 1962.

[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, s. 11–15 (January, 1972).

[4] Ballard, D.H., Generalizing the Houghtransform to detectarbitraryshapes, „Pattern Recognition”, Elsevier, Volume 13, Issue 2, s. 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.

[1]

[2]

[3]

[4]

[5]

[6]