# algorithm - Detecting circles in binary image

What algorithm would you suggest for detecting black circles in binary image? The image I'm working with is white, there are some other objects as well plus the black circles I'm interested in.

I've implemented hough transform method for circle detection. The question is how much faster any algorithm can be than hough transform?

These are not perfect circles, plus I only know the lower and upper limit of what their radius can be: You must first detect the shapes. This can be done by "connected components analysis".

Either you have such a tool available ready-made, or you can craft a simple one for your purpose: implement a flood filling algorithm, and use it as follows: scan the image row by row, until you meet a black pixel. Then flood fill from this pixel, painting in white. This will make the shape completely disappear. Continue the scan. In the end the image will be completely white.

But of course, this would be completely useless if you didn't keep a track of what happens. While you fill a shape, you will keep a trace of the minimum/maximum abscissa and ordinate of the pixels you visit. In the end, you will know the bounding box of the shape. And then, you can use this very simple criterion to tell rectangles from circles: for a rectangle, the starting pixel is the upper left corner of the bounding box; not for a circle. (Actually, it even suffices to keep the minimum abscissa).

You get the idea. If you are in a more complex situation (say with triangles as well), keep this principle: perform blob detection and measure some geometric characteristics of the blobs; use these characteristics (they are called "blob features") to discriminate between your shapes.

UPDATE:

A very discriminant test can be as follows: find the bounding box and find all outline pixels. Then for every outline pixel check that `(X-Xc)²/W²+(Y-Yc)²/H²=1/4`, i.e. they are on the ellipse centered on the bounding box and with axes `(W/2, H/2)`. Due to the digital nature of the shape, you will need to add a +/-1 pixel tolerance.

I've got a simple code that utilizes some of the hints from the previous answer, but uses OpenCV functions:

``````#include <iostream>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/core/core.hpp>
#include <opencv2/imgproc/imgproc.hpp>

using namespace std;
using namespace cv;

int main(int argc, char **argv){

Mat img = imread("test.png", 0);

Mat edge, out;

Canny(img, edge, 1, 1);
cvtColor(img, out, CV_GRAY2BGR);

vector<vector<Point> > contours;
vector<Vec4i> hierachy;

findContours(edge, contours, hierachy, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_NONE, Point(0, 0));

for(int i = 0; i < (int)contours.size(); i++){
double p = (double)contours[i].size();
double a = contourArea(contours[i]);

if(fabs(1-pow(p,2)/(4*CV_PI*a)) < 0.2){
drawContours(out, contours, i, Scalar(0,0,255), 2);
}
}

imshow("out", out);
waitKey(0);
return 0;
}
``````

The basic idea is simple. You retrieve all external (outer-most, hence `CV_RETR_EXTERNAL`) contours in the edge image in a pixel-wise manner (hence `CV_CHAIN_APPROX_NONE`). Once you have them, you can use the area and the perimeter to decide if they are circles. In this example I used a the simple measurement `C=(P^2)/(4*PI*A)`, with the perimeter `P` and the area `A`. For a perfect circle this will be 1 and everything that deviates from that is rather not a circle. This of course only works for non-overlapping shapes.

It could be that the simple compactness measurement isn't sufficient to differentiate circles from other shapes that might be in the image. But for this I would suggest to look into this paper, that gives an overview over some circularity and compactness measures, or to look at some image moments (e.g. eccentricity) and the implementation in OpenCV. Maybe you could come up with your own criterion.

Here is the output of the code above given your test image. 