Circle Hough Transform (CHT)

The Hough transform can be used to determine the parameters of a circle when a number of points that fall on the perimeter are known. A circle with radius R and center (a,b) can be described with the parametric equations

x=a+R cos(t)
y=b+R sin(t)

When the angle t sweeps through the full 360 degree range the points (x,y) trace the perimeter of a circle.

If an image contains many points, some of which fall on perimeters of circles, then the job of the search program is to find parameter triplets (a,b,R) to describe each circle. The fact that the parameter space is 3D makes a direct implementation of the Hough technique more expensive in computer memory and time. There is value in finding techniques to limit the size of the search space. We will begin with the most simple case and progress to some that are more complicated.

The program is implemented in IDL as

If the circles in an image are of known radius R, then the search can be reduced to one in two dimensions. The objective is to find the (a,b) coordinates of the centers.

a=x-R cos(t)
b=y-R sin(t)

The locus of (a,b) points in the parameter space fall on a circle of radius R centered at (x,y). The true center point will be common to all parameter circles, and can be found with a Hough accumulation array.

Multiple circles with the same radius can be found with the same technique. The centerpoints are represented as red cells in the parameter space drawing. Overlap of circles can cause spurious centers to also be found, such as at the blue cell.

Spurious circles can be removed by matching to circles in the original image.

If the radius is not known, then the locus of points in parameter space will fall on the surface of a cone. Each point (x,y) on the perimeter of a circle will produce a cone surface in parameter space. The triplet (a,b,R) will correspond to the accumulation cell where the largest number of cone surfaces intersect.

The drawing at the right illustrates the generation of a conical surface in parameter space for one (x,y) point. A circle with a different radius will be constructed at each level, r.

The search for circles with unknown radius can be conducted by using a three dimensional accumulation matrix.

Example: Points on overlapping circles of known radius.

A set of 20 points on circles of radius 1 and centers [2,3] and [3,2.5] were generated. These are displayed at the right.

This data set was submitted to the CHT program with the radius R=1 given.
The CHT accumulation matrix is shown in a surface plot at the right. Two peaks are very clear. These correspond to the locations of the centers of the circles.

The circles were selected using a threshold value of thresh=7.

The data for the circles is shown below. The circles are plotted from this data over the given data points in the figure below right.

N R Cx Cy
1 1.00 1.94 2.99
2 1.00 2.99 2.43

Example: Search for circles in the coins1 image.

Since the coins are round, we would expect to be able to find circles to match their edges. This example will illustrate a sequence of preprocessing steps and then a CHT search.

We need to find the edges in the original image. The first step is to convert it to a binary image with a threshold operation. That is followed by a morphological closing to remove many of the holes in the binary image. The closing is followed with an erosion with a small structuring element to remove small noise pixels in the background. The result is shown at the right.

The points found by the edge processing are shown at the right. These were submitted to the CHT program. The coordinates found are listed below. The coordinate data was used to draw the circle plots below right. The circles have been labeled with the indexes in the corresponding table.

N R Cx Cy
1 64 301 372
2 73 569 126
3 73 90 372
4 52 164 180
5 54 327 87
6 54 625 329
7 54 327 80
8 54 388 237
9 73 504 408
10 54 164 180
11 54 164 176
12 54 620 333
13 73 500 411

The CHT search finds the peaks in the A matrix. The peaks can be seen by looking at surface plots of the A matrix for each radius value. These are shown in the four plots below. Note that the peaks at R=73, which corresponds to the quarter, are quite clear and distinct. There are three clear peaks for the three quarters. The peak for R=64 is also very distinct. This is the radius of the lone nickle. The peaks for R=52 and R=54, however, are less distinct. These radius values are quite close, and the cells near the center of the penny and dime objects get populated by both radius counters.