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,.

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) oraz na wykrywanie dowolnych kształtów (Dana H. Ballard, 1981).

Historia

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

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.