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[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]
Obraz (np. z kamery) jest reprezentowany przez piksele o współrzędnych kartezjańskich . Prostą można zapisać jako kąt nachylenia i odległość od początku układu współrzędnych .
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: , gdzie – 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[edytuj | edytuj kod]
- ↑ 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, pp. 11–15 (January, 1972)
- ↑ Ballard, D.H., "Generalizing the Houghtransform to detectarbitraryshapes," Pattern Recognition, Elsevier, Volume 13, Issue 2, pp. 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.