Hough transform

generated by

Hough Transform

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.

Hough Line Transform

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

$$y=mx+b,$$ (1)

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

$$b=y-mx$$

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.

$$x\cos \theta +y\sin \theta =\rho$$ (2)

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 than (1), as it is numerically stable for lines of any angle.

The Accumulator

To generate the Hough transform for 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.

Hough Circle Transform

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

$${(x-a)}^2+{(y-b)}^2=r^2$$

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.

General Hough Transform

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 features in the original image to some set of parameters in the Hough transform space.

Title	Hough transform
Canonical name	HoughTransform
Date of creation	2013-03-22 12:37:17
Last modified on	2013-03-22 12:37:17
Owner	madmortigan (9776)
Last modified by	madmortigan (9776)
Numerical id	14
Author	madmortigan (9776)
Entry type	Definition
Classification	msc 68T10
Classification	msc 68U10