## Randomized Hough Transform

The Hough transform can be used to extract shapes from images.

As an example, consider a binary image (pixel values can be only 0 – black, belonging to the background – or 1 – white, belonging to the shape) from which one wants to extract segments of straight lines.

The 2D polar equation of a straight line is

$x cos(\theta) + y sin (\theta) - d = 0$

where

$x, y$ are the coordinates of a point on the line;

$\theta$ is the angle between the normal to the line and the $x$ axis;

$d$ is the distance of the line from the origin.

The Hough transform maps the image space $x, y$ into the parameter space $\theta, d$; a straight line in the image space is mapped into a single point in the parameter space, while a single point $x_P, y_P$ in the image space is mapped into the curve $d = x_P cos(\theta) + y_P sin(\theta)$ in the parameter space.

All the curves in parameter space corresponding to points which are aligned in image space will cross in the point $\theta, d$ corresponding to their joining line. So there will be many more crossings in or near a parameter point corresponding to a straight sequence of many pixels in image space, than in a parameter point corresponding to a line which only contains a few isolated pixels.

The parameter space is quantized into counting bins of size $\Delta \theta, \Delta d$. Each white pixel in the image is examined and its transformed curve is sampled, increasing the counts of the bins crossed by the curve. At the end, bins having high counts will reveal straight sequences of pixels in the image.

The algorithm, as described, is very expensive in terms of memory (all the bins in parameters space must be stored, even those which will reach low or zero count) and time (for each white pixel a curve must be sampled).

The Randomized Hough Transform (RHT) is a variant which worked very well for me. No bin is stored, and white pixels are not examined one at a time. Rather, couples of white pixels are randomly chosen and their joining line is computed. If it is sufficiently similar to a line already computed and stored, the score of this line is increased and its parameters are somehow averaged with those of the new line; otherwise the new line is stored separately with an initial score of 1. When enough couples of white pixels have been examined, lines with high scores do emerge, corresponding to true lines in the image.

Of course, when looking for shapes other than lines, a different number of pixels must be examined at once; eg when looking for a circumference triples of pixels must be chosen, because a circumference is determined by three points.

This modified algorithm is fast and effective, but some detail needs special care:

• one must be able to tell if two shapes are sufficiently close in parameter space to be considered the same shape. This means, first, to define a distance in parameter space, what is not always straightforward, and second, to choose a suitable threshold value;
• one must somehow decide how many tuples of pixels must be examined.

I adapted this algorithm for finding the directions of rows and columns of a grid in an image. Directions have one single parameter, an angle, so that in this case it is easy to define the distance in parameter space.

I have implemented the algorithm in C++. The obvious data structure is an stl multimap having the score as key and the direction as value, but multimap is highly inefficient. It is much better to use a list of structures containing both the direction and the score.

There is a certain similarity between RHT and Teuvo Kohonen’s Self-Organizing Maps (SOM); in both cases a new pattern is compared to all the existing patterns and it can be merged with the most similar one (winner); in both cases the winner is adjusted toward the new pattern. An important difference is that in classical SOM the number of existing patterns (neurons) is fixed since the beginning, while in RHT one starts with zero existing patterns and new patterns are added when there is no winner; also, the adjustment rules are more sophisticated in SOM than in RHT.

It looks very interesting to me that algorithms stemming from different fields and having different justifications could be so similar; this reminds me of convergent evolution.