# How to do De-Houghing of a Hough transform'ed Image?

I'm working with code found at Rosetta Code for creating a Hough transform. I now want to find all the lines in an image. To do so I need the ρ and θ values of each of the peaks in the Hough space. A sample output for a pentagon looks like this:

How can I find a single [θ,ρ] coordinate for each of the 'hot spots' visible in the Hough space?

You are finding the coordinates of the peaks and then uses the axis to scale those into [θ,ρ] coordinates.

Depending on how noisy the data, how many false peaks you expect and how much time you have, there are a few ways of doing it. Easiest is to pick some level that is a a real peak, cut of all data below that and then do a center of gravity on each peak to get it's center.

You could also erode/dialte the image until each peak is a single pixel.

• +1 for precise answer. How do you define/compute center of gravity? – Dipan Mehta Mar 30 '12 at 13:48
• For more accuracy, find the maximum, then fit a paraboloid to that point and its neighboring points, then find the peak of the paraboloid, which will generally be between pixels. – endolith Mar 30 '12 at 13:59
• @endolith - generally with Hough transforms the accuracy is limited by the identification of edges in the initial image and the 'discretization' of the result in Hough space. If you need a more accurate result it's normal to go back and redo the transform for a more limited range of [θ,ρ] coordinates to get a higher resolution Hough space around the course solution you found – Martin Beckett Mar 30 '12 at 15:26
• @DipanMehta - simply sum over (xvalue of each pixel) and (y..) then divide by the X,Y width of the box you are searching - but see comment to endolith – Martin Beckett Mar 30 '12 at 15:27

This code on the File Exchange will help you find all the local maxima. http://www.mathworks.com/matlabcentral/fileexchange/14498-local-maxima-minima

If you have some knowledge about how many lines you want to find (in this case five), you simply select the five local maxima with the highest Hough scores.

You can locate the local maxima for a given radius. For example, you scan the Hough image taking peaks as maxima only when they are maximal in a $3\times 3$ window.

The second step could be refining the peak position to sub-pixel accuracy. This can be done by parabola fitting.

Suppose the value in Hough image is $f(x)$ where $x$ is the 2D position. Now you would like to find a correcting vector $p$ that maximizes $f(x + p)$. This can be written using Taylor expansion:

$$f(x+p)\approx f(x)+p^{\mathbb{T}}f'(x)+\frac{1}{2}p^{\mathbb{T}}f''(x)+p$$

The correcting vector is then

$$p=-f''(x)^{-1}f'(x)$$

The derivatives can be computed from the Hough image by finite differencing.

Note that $f''(x)$ is a $2\times2$ Hessian matrix and $f'(x)$ is a 2-vector (horizontal and vertical gradient), hence the $p$ is also a 2-vector specifying a sub-pixel shift to get accurate position of the local maximizer.

The above equation may occasionally yield shifts of more than 1 pixel. In such case, the maximizer neighborhood does not have a parabolic shape and you may not want to do the correction or should even drop the candidate maximizer.

There is a very good technique developed back in the mid-80 by Gerig and Klein. It is a backmapping procedure that analyses the Hough space to identify the most likely point associated with each edge point and then constructs a second Hough space where the mapping of edge points to parameters is one-to-one rather than one-to-many which is the usual first stage. I don't have the reference to hand but look in the seminal Hough review paper of Illingworth and Kittler (about 1987?)