phoughlines

Detects straight lines from a set of contours.

Synopsis

phoughlines lines minangle maxangle thickness [-m mask] [im_in|-] [im_out|-]

Description

phoughlines detects straight lines from contours given in the input image im_in. A contour is a chain of connected non null pixels. The output image is composed of detected straight lines.

Hough Line Transform:

The Hough transform is a general technique for identifying the location and orientation of certain types of features in a digital image.

To use the Hough transform to extract line, we consider the general equation of straight line in normal form:

   x cos theta + y sin theta = rho.

where rho is the perpendicular distance from the origin and theta the angle with the normal.

For any given point (x, y), we can obtain lines passing through that point by solving for rho and theta. A line in the image is represented as a point in the polar coordinates (rho, theta). Conversely, a point in the image is represented as a sinusoid in the polar coordinates since infinitely many lines pass through this point.

The hough transform is based on an accumulator (rho, theta). Each cell of the accumulator is the number of occurrence (rho, theta) for points of the perpendicular line, ie. the number of lines with the same parameters (rho, theta) that can passed through each contour of the input image.

The algorithm is as follows:

initialize the accumulator
For each point (x,y) in the image, increment accumulator(r,o) for each possible line that passes through (x,y):
```
   for theta =0 to 360 do
      rho =x*cos(theta)+y*sin(theta)
      accumulator[rho][theta] ++;
```
For the number of wanted lines:
- Find maximum in the accumulator.
- Draws related line in the output image.
- Remove the maximum in the accumulator

To solve the problem of the "phantom lines" due to the discretization of the contour lines, the maximum is not only removed, but all the contour points of the detected line, plus all lines that are at a minimal distance of thickness pixels from it, are removed from the initial image and the accumulator is recomputed with the remain lines (in fact, an improvement of this solution).

Parameters

lines specifies the number of lines in the output image.
minangle and minangle control the angle of research. Only lines that are comprise between these two angle are retained. The values are specified in degree unit and are between -360 + 360. Uses minangle=0 and maxangle=180 to retain all lines.
linethickness defines the minimal distance between two lines.

Inputs

im_in: a 2D grayscale image (Img2duc).

Outputs

im_out: an image of the same type as the input image.

Result

Returns the number of detected lines.

Examples

Extracts straight lines from the set of contours yielded by a simple edge detection of tangram.pan. The result is superimposed to the image of contours :

   psobel tangram.pan b.pan
   pbinarization 45 1e30  b.pan c.pan
   pskeletonization c.pan d.pan 
   ppostthinning d.pan e.pan
   phoughlines 10 0 180 2 e.pan f.pan
   pimg2imc 0 f.pan c.pan c.pan out.pan

C++ prototype

Errc PHoughLines( const Img2duc &im_in, Img2duc &im_out, int lines, int minagle, int maxangle, in tthickness );

Version française

Détection et localisation des segments de droite dans une image de contours par la transformée de Hough.

Author: Laurent Quesnel