The circle Hough Transform (CHT) is a basic feature extraction technique used in digital image processing for detecting circles in imperfect images. The circle candidates are produced by “voting” in the Hough parameter space and then selecting local maxima in an accumulator matrix.
It is a specialization of the Hough transform.
In a two-dimensional space, a circle can be described by:
\left(x-a\right)2+\left(y-b\right)2=r2 (1)
If the radius is fixed, then the parameter space would be reduced to 2D (the position of the circle center). For each point (x, y) on the original circle, it can define a circle centered at (x, y) with radius R according to (1). The intersection point of all such circles in the parameter space would be corresponding to the center point of the original circle.
Consider 4 points on a circle in the original image (left). The circle Hough transform is shown in the right. Note that the radius is assumed to be known.For each (x,y) of the four points (white points) in the original image, it can define a circle in the Hough parameter space centered at (x, y) with radius r. An accumulator matrix is used for tracking the intersection point. In the parameter space, the voting number of points through which the circle passing would be increased by one. Then the local maxima point (the red point in the center in the right figure) can be found. The position (a, b) of the maxima would be the center of the original circle.
Multiple circles with same radius can be found with the same technique.
Note that, in the accumulator matrix (right fig), there would be at least 3 local maxima points.
In practice, an accumulator matrix is introduced to find the intersection point in the parameter space. First, we need to divide the parameter space into “buckets” using a grid and produce an accumulator matrix according to the grid. The element in the accumulator matrix denotes the number of “circles” in the parameter space that passing through the corresponding grid cell in the parameter space. The number is also called “voting number”. Initially, every element in the matrix is zeros. Then for each “edge” point in the original space, we can formulate a circle in the parameter space and increase the voting number of the grid cell which the circle passes through. This process is called “voting”.
After voting, we can find local maxima in the accumulator matrix. The positions of the local maxima are corresponding to the circle centers in the original space.
Since the parameter space is 3D, the accumulator matrix would be 3D, too. We can iterate through possible radii; for each radius, we use the previous technique. Finally, find the local maxima in the 3D accumulator matrix.Accumulator array should be A[x,y,r] in the 3D space. Voting should be for each pixels, radius and theta A[x,y,r] += 1
The algorithm :
The Incrementing for Best Candidate :
For each A[a,b,r] = 0; // fill with zeroes initially, instantiate 3D matrix For each cell(x,y) For each theta t = 0 to 360 // the possible theta 0 to 360 b = y – r * sin(t * PI / 180); //polar coordinate for center (convert to radians) a = x – r * cos(t * PI / 180); //polar coordinate for center (convert to radians) A[a,b,r] +=1; //voting end end
The original picture (right) is first turned into a binary image (left) using a threshold and Gaussian filter. Then edges (mid) are found from it using canny edge detection. After this, all the edge points are used by the Circle Hough Transform to find underlying circle structure.
Since the parameter space of the CHT is three dimensional, it may require lots of storage and computation. Choosing a bigger grid size can ameliorate this problem.
However, choosing an appropriate grid size is difficult. Since too coarse a grid can lead to large values of the vote being obtained falsely because many quite different structures correspond to a single bucket. Too fine a grid can lead to structures not being found because votes resulting from tokens that are not exactly aligned end up in different buckets, and no bucket has a large vote.
Also, the CHT is not very robust to noise.
J. Illingworth and J. Kittler[1] introduced this method for implementing Hough Transform efficiently. The AHT uses a small accumulator array and the idea of a flexible iterative "coarse to fine" accumulation and search strategy to identify significant peaks in the Hough parameter spaces. This method is substantially superior to the standard Hough Transform implementation in both storage and computational requirements.
Since the head would be similar to a circle in an image, CHT can be used for detecting heads in a picture, so as to count the number of persons in the image.[2]
Modified Hough Circle Transform (MHCT) is used on the image extracted from Digital Subtraction Angiogram (DSA) to detect and classify aneurysms type.