Straight Line Detection

A straight line in 2D space described by this parametric equation:

$$f(x,y,\rho_0,\theta_0)=x\; cos\; \theta_0 + y\; sin\; \theta_0 -\rho_0 = 0$$

can be represented in the 2D parameter space by a point $(\rho_0, \theta_0)$, where $\rho_0$ is the distance between the straight line and the origin, and $\theta_0$ is the angle between the distance vector and the positive x-direction.

To find the Hough transform of a certain point $(x_0,y_0)$ in the image space, we solve the equation above for $\rho$ and get

$$\rho = x_0\; cos \;\theta + y_0\; sin\; \theta = \sqrt{x_0^2+y_0^2}\;\; ... ...rt{x_0^2+y_0^2}}\;cos\; \theta + \frac{y_0}{\sqrt{x_0^2+y_0^2}}\; sin\; \theta)$$

$$= r_0\; (cos\; \alpha_0\; cos\; \theta + sin\; \alpha_0\; sin\; \theta) = r_0\; cos (\alpha_0-\theta)$$

where

$$\left\{ \begin{array}{l} r_0 \stackrel{\triangle}{=} \sqrt{... ...stackrel{\triangle}{=} tan^{-1} (y_0/x_0) \end{array} \right.$$

• Forward Hough transform

  We see from the equation above that any point $(x_0,y_0)$ in the image space is transformed into a sinusoidal curve in the parameter space. On the other hand, a point $(\theta, \rho)$ on this sinusoidal curve represents a straight line passing through the point $(x_0,y_0)$ in the image space, as shown in the figures below, where $x_0=y_0=1$, i.e., $r_0=\sqrt{2}=1.4142$, $\alpha_0=tan^{-1} y_0/x_0=\pi/2$. Note that the four particular directions labeled as 2, 3, 4 and 1 in the image (left) correspond respectively to the points in the Hough space (right):

  
  

  $$\begin{tabular}{l\vert\vert c\vert c\vert c\vert c} \hline ... ...785 \hline \rho & 1 & 0 & 1 & 1.4142 \hline \end{tabular}$$
  
  

  

• Inverse Hough Transform

  Any given point $(\rho_0, \theta_0)$ in the parameter space can be inverse transformed to the spatial domain to represent a straight line specified by the equation
  

  $$x\; cos\; \theta_0 + y\; sin\; \theta_0 -\rho_0 = 0$$
  
  

  The figures below show an example of three image points $A=(0,2)$, $B=(1,1)$, and $C=(2,0)$ all on a straight line. These points are mapped to the parameter space as three sinusoidal curves in blue, red and green, respectively. The fact that these points are on a straight line guarantees that the corresponding curves intersect at a point ( $\rho=\sqrt{2}=1.4142$ and $\theta=\pi/4=0.79$) representing the straight line
  

  $$\rho=x \; cos(\theta) + y \;sin(\theta) \;\;\; \mbox{i.e.} \;... ...\; cos(\pi/4) + y \;sin(\pi/4)\;\;\; \mbox{i.e.} \;\;\; x+y=2$$
  
  

  

The ddetection of all straight lines in the image can be carried out by the following steps:

1. Make available an $n=2$ dimensional array $H(\rho,\theta)$ for the parameter space;
2. Find the gradient image: $G(x,y)=\vert G(x,y)\vert \angle G(x,y)$;
3. For any pixel satisfying $\vert G(x,y)\vert > T_s$, increment all elements on the sinusoidal curve $\rho=x\; cos\; \theta + y\; sin\; \theta$ in the parameter space represented by the H array:

   for all $\theta$ {
   

   $$\rho=x\; cos\; \theta + y\; sin\; \theta;$$
   
   
   
   
   $$H(\rho, \theta)=H(\rho, \theta)+1;$$
   
   
   }

4. In the parameter space, any element $H(\rho, \theta) > T_h$ represents a straight line detected in the image.

This algorithm can be improved by making use of the gradient direction $\angle G$, which, in this particular case, is the same as the angle $\theta$. Now for any point $\vert G(x,y)\vert > T_s$, we only need to increment the elements on a small segment of the sinusoidal curve. The third step in the above algorithm can be modified as:

1. (same as above)
2. (same as above)
3. For any pixel satisfying $\vert G(x,y)\vert > T_s$,

   for all $\theta$ satisfying $\angle G(x, y)-\Delta \theta \leq \theta \leq \angle G(x, y)+\Delta \theta$

   {
   

   $$\rho=x\; cos\; \theta + y\; sin\; \theta;$$
   
   
   
   
   $$H(\rho, \theta)=H(\rho, \theta)+1;$$
   
   
   }

   where $\Delta \theta$ defines a small range in $\theta$ to allow some room for error in $\angle G$.

4. (same as above)

Check out this online demo.