The Hough transform is a general technique for identifying the locations and orientations of certain types of features in a digital image. Developed by Paul Hough in 1962 and patented by IBM, the transform consists of parameterizing a description of a feature at any given location in the original image’s space. A mesh in the space defined by these parameters is then generated, and at each mesh point a value is accumulated, indicating how well an object generated by the parameters defined at that point fits the given image. Mesh points that accumulate relatively larger values then describe features that may be projected back onto the image, fitting to some degree the features actually present in the image.

The simplest form of the Hough transform is the Hough line transform. Suppose we are attempting to describe lines that match edges in a two-dimensional image. If we perform an edge-detection technique on the image, we might obtain an image like the following.

To use the Hough transform, we need a way to characterize a line. One representation of a line is the slope-intercept form

where $m$ is the slope of the line and $b$ is the $y$-intercept (that is, the $y$ component of the coordinate where the line intersects the $y$-axis). Given this characterization of a line, we can then iterate through any number of lines that pass through any given point $(x,y)$. By iterating through fixed values of $m$, we can solve for $b$ by

However, this method is not very stable. As lines get more and more vertical, the magnitudes of $m$ and $b$ grow towards infinity. A more useful representation of a line is its normal form.

This equation specifies a line passing through $(x,y)$ that is perpendicular to the line drawn from the origin to $(\rho,\theta)$ in polar space (i.e., $(\rho\cos\theta,\rho\sin\theta)$ in rectangular space). For each point $(x,y)$ on a line, $\theta$ and $\rho$ are constant.

Now, for any given point $(x,y)$, we can obtain lines passing through that point by solving for $\rho$ and $\theta$. By iterating through possible angles for $\theta$, we can solve for $\rho$ by (2) directly. This method proves to be more effective than (1), as it is numerically stable for matching lines of any angle.

To generate the Hough transform for matching lines in our image, we choose a particular granularity for our lines (e.g., $10^{\circ}$), and then iterate through the angles defined by that granularity. For each angle $\theta$, we then solve for $\rho=x\cos\theta+y\sin\theta$, and then increment the value located at $(\rho,\theta)$. This process can be thought of as a “vote” by the point $(x,y)$ for the line defined by $(\rho,\theta)$, and variations on how votes are generated exist for making the transform more robust.

The result is a new image defined on a polar mesh, such as the one below (generated from the previous image).

Note that in this representation we have projected the polar space onto a rectangular space. The origin is in the upper-left corner, the $\theta$ axis extends to the right, and the $\rho$ axis extends downward. The image has been normalized, so that each pixel’s intensity represents the ratio of the original value at that location to the brightest original value.

The intensity of a pixel corresponds to the number of votes it received relative to the pixel that received the most votes.

Iterating through each value of $\theta$ for a particular $(x,y)$ in the original image generates a curve in the rectangular representation of the Hough transform. Lines that intersect in the same location are generated by collinear points. Thus, if we locate the brightest points in the image, we will obtain parameters describing lines that pass through many points in our original image. Many methods exist for doing this; we may simply threshold the Hough transform image, or we can locate the local maxima. We then get a set of infinite lines, as below. This notion corresponds neatly with the notion of a voting process; the brighter pixels represented coordinates in $(\rho,\theta)$ space that got the most votes, and thus are more likely to generate lines that fit many points.

For each $(\rho,\theta)$ that we deem bright enough in the Hough transform, we can then generate a line from the parameterization given earlier. Here is the projection of some lines obtained from the previous image’s Hough transform, drawn on top of the original image.

We can also use this information to break these lines up into line segments that fit our original binary image well. Below is an example of the line segments we might obtain, drawn on top of the original image.

The Hough transform can be used for representing objects besides lines. For instance, a circle can be parameterized as

Here, $(a,b)$ is the coordinate of the center of the circle that passes through $(x,y)$, and $r$ is its radius. Since there are three parameters for this equation, it follows that the Hough transform will be a three-dimensional image. Therefore circles require more computation to find than lines. For this reason the Hough transform is more typically used for simpler curves, such as straight lines and parabolas.

The general Hough transform is used when an analytical description of the feature we are searching for is not possible. Instead of a parametric equation describing the feature, we use some sort of lookup table, correlating locations and orientations of potential features in the original image to some set of parameters in the Hough transform space.