Skip to content

Using the Hough Transform for Circle Detection

by Stephen on June 22nd, 2010

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.

A low contrast, raw, phantom mammogram.

Low Contrast Phantom Mammogram

A noisy, processed, phantom mammogram

Noisy Phantom Mammogram

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.

The result of applying a median filter on a low-contrast phantom mammogram.

Median Filter on Low Contrast Phantom Mammogram

The result of applying a median filter on a noisy phantom mammogram.

Median Filter on Noisy Phantom Mammogram

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.

The result of a sobel filter applied to a low-contrast phantom mammogram.

Sobel Filter on Low Contrast Phantom Mammogram

The result of a sobel filter applied to a noisy phantom mammogram.

Sobel Filter on Noisy Phantom Mammogram

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.

The result of applying the Hough transform on a low-contrast phantom mammogram.

Hough Transform on Low Contrast Phantom Mammogram

The result of applying the Hough transform on a noisy phantom mammogram.

Hough Transform on Noisy Phantom Mammogram

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.

The results of the Hough transform circle detection algorithm on a noisy phantom mammogram.

Circle Detection on Noisy Phantom Mammogram

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!

No comments yet

Leave a Reply

Note: XHTML is allowed. Your email address will never be published.

Subscribe to this comment feed via RSS