Using the Hough Transform for Circle Detection
The Hough transform is a powerful feature recognition algorithm that was originally designed (by Paul Hough of IBM) to extract lines from images. In this post, I’m going to describe a very simple modification that allows for the extraction of not lines, but circles.
Note: I will not discuss the theory behind the Hough transform, as both Wikipedia and PlanetMath have excellent in-depth descriptions. Instead I’m going to simply provide a quick and dirty implementation for circle detection.
The most important aspect of this algorithm is that the radius of the circle you are looking to detect needs to be known before-hand. While there is a little wiggle room, the algorithm is about as precise as your guess is close to the radius of the circle you are trying to detect. In my case I wanted to detect a small high-density disc in a series of phantom mammograms (shown below), which is more or less always going to be about 1 inch in diameter.
Step 1: Noise Suppression
The crux of the algorithm is going to rely upon detecting the silhouette of the circle (each pixel that belongs to its edge counts as a “vote”, to use the academic lingo). Most edge-detecting algorithms tend to be sensitive to noise – especially the simpler-to-implement ones, so some blurring is required. While it is perfectly legitimate to use a naive box or gaussian filter, my suggestion is to use something like the median filter which suppresses noise whilst preserving edges.
Step 2: Edge Detection
In order to extract features from our image, we need to obtain feature sillouhettes. For best results, the type of edge detector to use depends on the composition of the image you’re working with. For the phantom mammograms I use a slightly modified Sobel operator. The resulting edge map should be a binary image – either a pixel belongs to the silhouette or it doesn’t.
Step 3: Build Hough Map
The idea here is to count the number of pixels that belong to each edge in the image. If we do things right, the feature with the highest number of votes (pixels) is the bounding edge of our circle, allowing us to calculate a center position. However, with the edge map we calculated in the previous step we have no information as to which pixels belong to what feature. To remedy this we’ll take advantage of one very nice property of a circle – it is a completely uniform shape. Because of this, if you were to draw circles all around the perimeter of another circle of equal radius, the point of greatest overlap would be the very center of that circle. Very convenient! To accomplish this, at each non-zero pixel in our edge map we additively plot a circle (this is why we needed to know the radius beforehand!) centered over that pixel in our Hough map.
Step 4: Detect the Origin
Extracting the origin of our detected circle from the Hough map is a relatively simple process – scan for the pixel of highest intensity, and you’re done! However due to factors like noise, the Hough map is unlikely to be clean enough for such an approach. In my instance I ended up searching for the pixel of highest intensity and region-filling at that value (using a very simple blob fill), and taking the center point of that region as my circle origin.
Results
So far, I’ve been very happy with this algorithm in my current implementation. An image has to be very, very noisy in order for things to be tripped up. The algorithm also runs fairly quickly (the median filter is the greatest bottleneck), but optimization of convolution filters is a good topic for another day!