Hough Transform

Problem

If I have an image like below, how do I actually figure out the slope and y-intercept of the line?

As a human, we’d just recognize the line as an object, choose any two points along it, and then we’ve got two x -> y mappings and two unknowns y = m*x + b, so we can easily solve for m and b.

But how do we do this computationally?

Hough Transforms

One approach is to just try every y-intecerpt and every slope, linearly spaced, and try to find one that looks similar to the input image.

Once you have this image attempt, you can find the intersection of your input image with this attempted image, then calculate the sum of the resulting intersection. This gives you a score for how well a particular m and b fit the input data.

If we do this many times, we can start to visualize what is called “Hough Space”, a space defined by the parameters of the line, rather than x and y.

When looking at the Hough plot, the brightest spot corresponds to the true slope and y-intercept of the input image’s line.

You’ll also notice that there are large slightly brighter regions across the resulting Hough plot. This is because other lines that don’t actually match, may still intercept the line in the original image, so they’ll have a small, but non-zero score.

Mapping Between

Let’s look at a slightly more complicated example.

Here we have a shorter line with a different slope and y-intercept. You can still see this line’s impact in the Hough plot, but since we’re scoring based on total number of matching pixels, it will never get as bright as the longer line does.

A final super interesting property here is the line-like slightly bright region in the top of the image.

This line (in Hough space) corresponds to the point we have in regular XY space!

Lines in XY space correspond to points in Hough space, and lines in Hough space correspond to points in XY space. This means that any point in the Hough line, corresponds to a line in XY space that intersects the given point, nifty!

Looking Beyond

This approach is the basis of OpenCV’s Hough* functions.

Hough Lines uses this technique on images after extracting image edges to find lines. You’ll notice that it doesn’t use our classic y = m*x + b formula for a line, but instead uses a polar representation that avoids problems with vertical lines.

Hough Circles also uses this approach. You can imagine that the “model” you search for in your image doesn’t just have to be a line, but it could be a point and a radius.