Hough Transform

Hough Transform jest bardzo prostą metodą wykrywania regularnych kształtów (okręgów, prostych) na zdjęciu. Opiera się ona na wyznaczeniu prawdopodobieństwa wystąpienia danego obiektu w każdym punkcie obrazu. Jedną z największych wad Hough Transform jest wysoka złożoność obliczeniowa.

Wykrywanie prostych

Oryginalna metoda Hougha służy do wykrywania prostych. 

Proste najczęściej są parametryzowane za pomocą prostego równania:

\[y=mx+c\],

gdzie $m \in \mathbb{R}$ jest parametrem nachylenia prostej oraz $c \in \mathbb{R}$ wyznacza punkt przecięcia z osią OY.
Prostą można też sparametryzować za pomocą:

\[Ay + Bx + 1 = 0,\]

gdzie $A=-\frac{1}{c}$ oraz $B=\frac{m}{c}$.

Niestety taka parametryzacja nie bierze pod uwagę pewnych prostych (np. prostych pionowych). Dlatego też, w przypadku operacji Houg wykorzystuje się troszeczkę zmieniony wzór: 

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

gdzie:

  • $\theta$ to kąt miedzy prostą prostopadłą do linii (przechodzącą przez punkt (0,0)),
  • $\rho$ to odległość prostej od punktu (0,0),

patrz poniższy rysunek.


Ilustracja. 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$

.

Dzięki prostym przekształceniom możemy otrzymać wzory:

\[ c = \frac{\rho}{\sin(\theta)}, \quad m = \frac{1}{\tan(\theta)} \].

Ponadto:

\[ \theta \in (0,180), \quad \rho \in (0,\sqrt{N^2+M^2} ) \],

gzie N, M to wymiary obrazka.

Aby znaleźć linię na obrazie, przedstawiamy binarny obraz w przestrzeni Hough. W tej przestrzeni główne osie opisują $\rho$ oraz $\theta$. Każda prosta występująca na obrazie jest sparametryzowana za pomocą tych dwóch liczb. W konsekwencji, każdej prostej występującej na obrazie odpowieda jeden punkt w przestrzeni Hough. Jeżeli ustalimy punkt $(x_{0}, y_{0})$ to rodzina wszystkich prostych przechodzących przez ten punkt tworzy wykres w kształcie sinusa w przestrzeni Hougha.

Ilustracja. Wszystki proste przechodzące przez zadany punkt można przedstawić za pomocą krzywej w kształcie sinusa.

Aby wyznaczyć pełną przestrzeń Hougha dla binarnego obrazu, musimy przejść po całym obrazie i dla każdego piksela krawędzi (białe piksele) musimy w przestrzeni Hougha zaznaczyć wszystkie proste przechodzące przez ten punkt, patrz poniższy pseudokod.

%Polar Hough Transform for Lines
function HTPLine(inputimage)

%image size
[rows,columns]=size(inputimage);

%accumulator
rmax=round(sqrt(rows^2+columns^2));
acc=zeros(rmax,180);

%image
for x=1:columns
  for y=1:rows
    if(inputimage(y,x)==0)
      for m=1:180
        r=round(x*cos((m*pi)/180)+y*sin(m*pi)/180));
        if(r>0) acc(r,m)=acc(r,m)+1; end
      end
    end
  end
end

Przestrzeń Hough można wygenerować za pomocą kodu w OpenCV (C++).

  

 

Ilustracja. Efekt algorytmu Hough.

Gdy mamy już wyznaczoną przestrzeń Hougha, maksymalne wartości (w tej przestrzeni) odpowiadają liniom na obrazie. Wartość w danym punkcie może być interpretowana jako ilość punktów, które leżą na danej prostej.

Wykrywanie prostych w OpenCV (C++)

Poniższy film pokazuje jak wygląda transformacja punktów z obrazu do przestrzeni Hougha. 

 

Wykrywanie okręgów

Okrąg możemy sparametryzować za pomocą następującego wzoru:

\[ (x−x_0)^2+(y−y_0)^2=r^2 \]

gdzie $(x_0,y_0)\in \mathbb{R}$, to środek okręgu oraz $r \in \mathbb{R}$, to promień. 

Jeżeli ustalimy promień $r$, to okrąg jest sparametryzowany tylko za pomocą dwóch liczb (środka).

W przypadku gdy wyznaczamy okręgi o różnych promieniach, przestrzeń zwiększa się o jeden wymiar. Wraz z tą zmianą złożoność algorytmu rośnie, gdyż musimy przeszukiwać większą przestrzeń.

W przypadku wyszukiwania okręgów często używa się parametryzacji w biegunowym układzie współrzędnych.

\[ x=x_0+r\cos(\theta)\] \[ y=y_0+r \sin(\theta)\]

Pozwala to otrzymać proste wzory:

\[x_0=x−r\cos(\theta)\] \[y_0=y−r\sin(\theta)\]

Podobnie jak w przypadku wyszukiwania linii algorytm najpierw wyznacza przestrzeń Hougha, a następnie wyznacza maksymalne wartości w tej przestrzeni. Aby wyznaczyć przestrzeń Hougha mozemy użyć poniższego algorytmu:

%Hough Transform for Circles
function HTCircle(inputimage,r)

%image size
[rows,columns]=size(inputimage);

%accumulator
acc=zeros(rows,columns);

%image
for x=1:columns
  for y=1:rows
    if(inputimage(y,x)==0)
      for ang=0:360
        t=(ang*pi)/180;
        x0=round(x-r*cos(t));
        y0=round(y-r*sin(t));
        if(x0>0 & y0>0)
          acc(y0,x0)=acc(y0,x0)+1;
        end
      end
    end
  end
end

  

Ilustracja. Efekt algorytmu Hough.

Wykrywanie okręgów w OpenCV (C++)

Wykrywanie elips

Elipsę możemy sparametryzować za pomocą następującego wzoru:

\[ \frac{(x-x_0)^2}{a^2}+\frac{(y-y_0)^2}{b^2}=1 \],

gdzie $(x_0,y_0)\in \mathbb{R}$, to środek elipsy oraz $a,b \in \mathbb{R}$, to promienie.

Podobnie jak wcześniej, w przypadku elips również będziemy używać układu biegunowego: 

\[ x=x_0+a x \cos(\theta)+bx \sin(\theta) \] \[ y=y_0+ay \cos(\theta)+b y \sin(θ)\]

Wykrywanie ogólnych kształtów

Algorytm Hough Transform można użyć do wykrywania dowolnych kształtów. W takim przypadku musimy zapamiętać kształt szukanego obiektu. Do przechowywania takich kształtów przeznaczone są tak zwane R-table. Dla zadanego kształtu najpierw wyznaczany jest punkt początkowy (reference point) $x_R$, względem którego kształt będzie wyznaczany, patrz poniższy obrazek.

Punkt referencyjny może się znajdować w dowolnym miejscu, ale przeważnie wybiera się środek danych. Położenie wszystkich pozostałych punktów zapisywane jest względem punktu referencyjnego. Właśnie to położenie jest zapisywane w R-table, patrz poniższy obrazek.

R-table zawiera tablicę list (po jednej dla każdej możliwej orientacji $\phi$). Każda z list zawiera pary $(r, \alpha)$, gdzie $r$ jest odległością danego punktu od punktu referencyjnego oraz $\alpha$ jest kątem nachylenia prostej przechodzącej przez dany punkt i punkt referencyjny. Liczba orientacji musi być skończona, dlatego tez używa się skwantyzowanych wartości.