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: enter image description here

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.

They are beatles, but the program will work with many different bugs :) — Quentin Geissmann, Jun 03 '12 at 20:33
Nothing about algorithm, but you could take advantage of C++11 if you're not already using it (standard containers are faster), and functions like std::fma to have a higher precision with some stuff. And use "a += b" instead of "a = a + b". All that is just about C++ syntax so it won't improve the algorithm but just its C++ implmentation. — Morwenn, Jun 03 '12 at 20:47
@Morwenn: `a = a + b` is the same as `a += b`. Compilers are smart. — , Jun 03 '12 at 20:52
@ Morwenn: Thank you for these advices, as you can see I am only beginner in C++... Obviously, as far as I can tell, the slow part is to call cv::HoughCircles iteratively (and twice with a second pass)... — Quentin Geissmann, Jun 03 '12 at 20:54
@VladLazarenko Yeah, you're right. Compilers are smart. But doesn't it depend on the type of a and b? Anyway, it would work for simple types. I find it cleaner, but that's not objective at all. — Morwenn, Jun 03 '12 at 20:55
I don't think this guy is at the stage of worrying about shaving off CPU cycles yet — James, Jun 03 '12 at 22:09
Why do you want to identify the dishes? If you are computing the movement of those critters (I'm guessing through image subtraction) a bounding circle around the path you detected will start small but eventually resemble the dish. Shaking may or may not reduce the time until that happens. — Darcara, Jun 03 '12 at 22:36
@Darcara I need to identify the area a priori because: 1) My tracking algorithm will only work with one animal at a time. 2) It will use the fact that if something moves in an area, it must be the animal 3) It learns the shape/colour of the animal present in each zone independently 4) The animals could stay immobile for 24 h. I will probably ask a question about that in the future, but so far, it is needed to detect the area. :) Thank you — Quentin Geissmann, Jun 04 '12 at 07:22

score 10 · Answer 1 · answered Jun 03 '12 at 21:02

The following approach should work pretty well for your case:

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

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.

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.

Thank you, I like your suggestion. My only problem, is the fact that, as far as I understand it, it requires a good and predictable contrast between the inside and outside of the circles (or continuous edges). I did not take picture of cases in which the contrast will be low yet, but, for instance, the experimenter could work with plates like this one : http://www.pioneerscientific.com/Merchant5/graphics/00000002/12%20well%20plates%20full-1.jpg and put an animal in each well... In addition, the experimenter could work with clear animal in dark backgrounds. — Quentin Geissmann, Jun 03 '12 at 21:44

score 5 · Answer 2 · answered Jun 03 '12 at 21:48

Within the current algorithm, the biggest thing that sticks out is the for(int t=5; t<400; t=t+2) loop. Trying recording score values for some test images. Graph score(t) versus t. With any luck, it will either suggest a smaller range for t or be a smoothish curve with a single maximum. In the latter case you can change your loop over all t values into a smarter search using Hill Climbing methods.

Even if it's fairly noisy, you can first loop over multiples of, say, 30, and for the best 1 or 2 of those loop over nearby multiples of 2.

Also, in your score function, you should disqualify any results with overlapping circles and maybe penalize overly spaced out circles.

Thank you, I am going to see the shape of Score(t) vs t and see if I can use such an optimisation technique in most cases. — Quentin Geissmann, Jun 04 '12 at 07:30

score 3 · Answer 3 · answered Jun 04 '12 at 16:19

You don't explain why you are using a black background. Unless you are using a telecentric lens (which seems unlikely, given the apparent field of view), and ignoring radial distortion for the moment, the images of the dishes will be ellipses, so estimating them as circles may lead to significant errors.

All and all, it doesn't seem to me that you are following a good approach. If the goals is simply to remove the background, so you can track the bugs inside the dishes, then your goal should be just that: find which pixels are background and mark them. The easiest way to do that is to take a picture of the background without dishes, under the same illumination and camera, and directly detect differences with the picture with the images. A colored background would be preferable to do that, with a color unlikely to appear in the dishes (e.g. green or blue velvet). So you'd have reduced the problem to bluescreening (or chroma keying), a classic technique in machine vision as applied to visual effects. Do a google search for "matte petro vlahos assumption" to find classic algorithms for solving this problem.

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

3 Answers3

Linked