Search code examples
computer-visionhough-transform

Searching for plus sign in binary image using Hough Transform

I have a binary image with white and dark pixels. I need to search for a plus sign (3x3) in that binary image.

0: for white pixels

1: for dark pixels

00000000
01000100
01001110
00000100
00000000
01000000
00100110
00000000

There is one plus sign in the binary image above. How can I find that using hough transform? What would be the dimension of the hough space?

My approach was to find two lines in the image above but I am not sure. I am not looking for code, just an explanation for how I can find that plus sign.

Solution

  • A point in Hough space needs to fully describe the object you are trying to locate. If you are looking for unbounded lines, you typically store the line's polar coordinates (angle and distance to the origin) in Hough space. When trying to locate 3x3 plus signs, the location of the central pixel of such a sign happens to fully describe it. After all, if you know where the central pixel is, you know where its other black pixels are. Therefore, you store central pixel locations in Hough space, so its dimensionality is 2.

    Now, the way you populate your Hough space is generally as follows:

    For every black pixel in a B/W image you encounter, you assume it's part of an object of interest. However, knowing that a pixel at (x, y) is part of your object of interest is insufficient to locate that object in Hough space. To be more precise, there are going to be multiple objects in Hough space that all contain that particular pixel at (x, y). At this point you need to figure out how to enumerate all of those objects. Once you do that, you simply increment the value in Hough space for each object you have enumerated.

    In your case, enumerating the objects is really simple, as all you need to do is enumerating all the black pixels in a 3x3 plus sign pattern, and for each such pixel to figure out the vector from that pixel to the central one. Once you have the location of some pixel of a plus sign and a vector to the central pixel, you know the location of the central pixel as well. That location is a point in Hough space you need to increment.