Robustly find N circles with the same diameter: alternative to bruteforcing Hough transform threshold

Question

I am developing application to track small animals in Petri dishes (or other circular containers). Before any tracking takes place, the first few frames are used to define areas. Each dish will match an circular independent static area (i.e. will not be updated during tracking). The user can request the program to try to find dishes from the original image and use them as areas.

Here are examples:

In order to perform this task, I am using Hough Circle Transform. But in practice, different users will have very different settings and images and I do not want to ask the user to manually define the parameters. I cannot just guess all the parameters either.

However, I have got additional informations that I would like to use:

I know the exact number of circles to be detected.

• All the circles have the almost same dimensions.
• The circles cannot overlap.
• I have a rough idea of the minimal and maximal size of the circles.
• The circles must be entirely in the picture.

I can therefore narrow down the number of parameters to define to one: the threshold. Using these informations and considering that I have got N circles to find, my current solution is to test many values of threshold and keep the circles between which the standard deviation is the smallest (since all the circles should have a similar size):

//at this point, minRad and maxRad were calculated from the size of the image and the number of circles to find.
//assuming circles should altogether fill more than 1/3 of the images but cannot be altogether larger than the image.
//N is the integer number of circles to find.
//img is the picture of the scene (filtered).

//the vectors containing the detected circles and the --so far-- best circles found.
std::vector<cv::Vec3f> circles, bestCircles;

//the score of the --so far-- best set of circles
double bestSsem = 0;

 for(int t=5; t<400 ; t=t+2){
//Apply Hough Circles with the threshold t
    cv::HoughCircles(img, circles, CV_HOUGH_GRADIENT, 3, minRad*2, t,3, minRad, maxRad );

    if(circles.size() >= N){
//call a routine to give a score to this set of circles according to the similarity of their radii
        double ssem = scoreSetOfCircles(circles,N);
//if no circles are recorded yet, or if the score of this set of circles is higher than the former best
        if( bestCircles.size() < N ||  ssem > bestSsem){
//this set become the temporary best set of circles
                bestCircles=circles;
                bestSsem=ssem;
        }
    }
}

With:

 //the methods to assess how good is a set of circle (the more similar the circles are, the higher is ssem)
    double scoreSetOfCircles(std::vector<cv::Vec3f> circles, int N){
    double ssem=0, sum = 0;
        double mean;
        for(unsigned int j=0;j<N;j++){
            sum = sum + circles[j][2];
        }
        mean = sum/N;
        for(unsigned int j=0;j<N;j++){
            double em = mean - circles[j][2];
            ssem = 1/(ssem + em*em);
        }
    return ssem;

}

I have reached a higher accuracy by performing a second pass in which I repeated this algorithm narrowing the [minRad:maxRad] interval using the result of the first pass.

For instance minRad2 = 0.95 * average radius of best circles and maxRad2 = 1.05 * average radius of best circles.

I had fairly good results using this method so far. However, it is slow and rather dirty. My questions are:

• Can you thing of any alternative algorithm to solve this problem in a cleaner/faster manner ?
• Or what would you suggest to improve this algorithm?
• Do you think I should investigate generalised Hough transform ?

Thank you for your answers and suggestions.

Answer 1

The following approach should work pretty well for your case:

1. Binarize your image (you might need to do this on several levels of threshold to make algorithm independent of the lighting conditions)
2. Find contours
3. For each contour calculate the moments
4. Filter them by area to remove too small contours

5. Filter contours by circularity:

   double area = moms.m00;
   double perimeter = arcLength(Mat(contours[contourIdx]), true);
   double ratio = 4 * CV_PI * area / (perimeter * perimeter);
   

   ratio close to 1 will give you circles.

6. Calculate radius and center of each circle

   center = Point2d(moms.m10 / moms.m00, moms.m01 / moms.m00);
   

And you can add more filters to improve the robustness.

Actually you can find an implementation of the whole procedure in OpenCV. Look how the SimpleBlobDetector class and findCirclesGrid function are implemented.