# hough transform

A Hough transform is an algorithm used in computer vision (image processing) application.  A computer image is a 2D array of values.  To identify a particular object in an image, we see if it matches a model for the object.  If we have an explicit mathematical model for the object, then we can seek to find the parameters for that model.  In the most common case for Hough transforms, Hough lines, we're seeking to find the slope and intercept of a line from a binary (1s and 0s) image (generally generated from edge detection).

We could take every subset of pixels (1s) and try and fit a line and then check the goodness of fit versus some criteria, but this would be computationally prohibitive.  A Hough transform takes each pixel and finds all the parameters that are consistent with a point at that location (a "1" at that pixel coordinate).  If there's a "1" at pixel $(x_0, y_0)$ then all $(m, b)$ such that $y_0 = m x_0 + b$ or $b = -x_0 m + y_0$ are consistent with a line through that point.

Note that $b = -x_0 m + y_0$ is a line.  The point $(x_0, y_0)$ in image space becomes a line "Hough space."  The parameters m and b in image space become the axes in Hough space, so it's also called "parameter space."  Here we have used m and b because the object of interest is a line, but it could be a different set of parameters for a different object.  (There are also Hough circles for instance where the parameters are the center and the radius.)

Each point in the image space maps to a line in Hough space.  All the points on a line in image space will correspond to a family of lines in m-b space that intersect.  We can find these intersections by discretizing m-b space and added up the values in each bin.  Each point in image space "votes" for a line in Hough space.  When these votes accumulate for a particular (m, b) past a threshold, we declare that such a line exists.

In practice, we don't use m and b because they can't handle vertical lines so the polar representation of a line is used.  A point at $(x_0, y_0)$ votes for $d = x_0 \cos \theta - y_0 \sin \theta$ where d and $\theta$ are the polar coordinate of the line.  $d-\theta$ space is discretized and an accumulator array filled with the "votes" to determine whether a line with those parameters exists.

References

1. http://www.cc.gatech.edu/~afb/classes/CS4495-Fall2012/slides/CS4495-03Hough.pdf
This entry was posted in somethingnew. Bookmark the permalink.