# Alternatives to Hough transform for detecting a grid-like structure

I have an image which is composed of multiple 'angles' which form a grid shape:

After some searching, Hough seemed like a good fit, because it isn't troubled by breaks in lines. However, the problem I have is that my lines are 'fat', and any edge detection I run (Canny in this case), picks out the edges of the line, and not the middle:

This means that the Hough transform ends up picking out one (or both) of the 'sides' of my grid lines, and not the middle.

Given that I know what I'm looking for (this grid-like shape, always in roughly the same orientation), is there a better way to perform the 'edge detection' part to give me the centre lines, or should I be looking at a totally different method?

• For context, this grid will be compared to a nominal grid to perform Tsai camera calibration. – Benjol May 21 '12 at 10:02
• "edge detection I run, picks out the edges of the line" Yes, because edge detection converts edges to ridges, and your image is already ridges. An edge is a boundary between light and dark. – endolith Oct 5 '12 at 17:46

The Hough Transform would indeed help in picking up the Grid in this case. To "thin" the lines, you might want to consider the operation of Skeletonization

That would produce an image like this one:

Due to the way that skeletonization works, it will still produce some lines that will seem irrelevant to the grid but these lines towards "erroneous" directions are not that many (at least in the given image) to confuse the line detection of the Hough Transform too much and it will clearly pick the two main sets of lines at distinct directions. (Here is how the HT output looks like: )

If you are using MATLAB, you might want to check this help page

• Thanks! This helps a lot. Haven't got my MATLAB licence yet, but I tried it out using AForge's SimpleSkeletonization, and it works better... Though still not perfect. I'll be revisiting this subject later when I get some real data to test it on. – Benjol May 21 '12 at 14:03
• You might want to try thresholding your original image first at some threshold that seems to be producing "optimal" fat grid lines. What i mean by optimal is that they are at least connected. That could improve the performance of the skeletonization but you would have an extra parameter to determine (the threshold). Maybe it's also worth looking into how to improve the image acquisition as well. – A_A May 21 '12 at 14:11
• yes, as I said, when I have the real data to play with, it'll be worth my time to fine tune the system. One major doubt I have about Hough in general is that the discretization of theta is going to work against the sub-pixel precision we need. (That, and I'm not completely convinced that lens aberrations won't mean that the lines could be curved, no straight...) – Benjol May 22 '12 at 5:57

An alternative to the Hough Transform would be the Radon Transform (1, 2). A rough description of an algorithm to detect a grid-like structure could look like this:

1. Perform Radon Transform from 0 to 180 degrees.
2. Find the two highest maxima in the angle bins.
3. For the two angles with maximal amplitude find the local maxima within the bin.
4. You can use the constraint that the maxima should have even spacing to deal with outliers.


EDIT:

Here is a small matlab snippet to illustrate step 1-3:

im = imread('grid.png');
imagesc(0:180, xp, R)


plot(max(R)) % the two maxima are at 65 & 117 degrees


plot(R(:, 65))


plot(R(:,117))


To answer your question from the comments: It appears to me from the one example image that you provided, that this method is more robust against small defects in the detected grid. Skeletons will rarely yield straight lines which might be a disadvantage for the subsequent Hough Transform.

• Thanks, could you tell me in a few words what advantage you would expect the Radon Transform to give me, compared to the Hough Transform? – Benjol May 25 '12 at 5:34
• @benjol, I updated my answer. – bjoernz May 25 '12 at 7:02
• Very nice, thanks a lot. Once IT give me access to Matlab I'll be giving it a try! – Benjol May 25 '12 at 7:29
• – endolith Oct 5 '12 at 17:42