System information (version)

• OpenCV => 3.3.1 (latest main)
• Operating System / Platform => Windows 64 Bit
• Compiler => Visual Studio 2015

Detailed description

HoughCircles performance is very slow finding circles in an image with many small circles. Our application needs to find approximately 9,000 to 10,000 circles in an image.

The primary problem is the EstimateRadius code does a linear search for all non-zero edge points (the nz list) within range of each center point. See: hough.cpp#L1220. This can be optimized by changing the nz list to a matrix. The matrix is the same size as the image, initially set to zeros. An element is set to 1 if there is a non-zero edge at that position. Finding non-zero edge points within range of a center point requires iterating over a range of elements +/- max_radius from the center point. Because the matrix approach may be optimal only for small circles, I wrapped it in a class that hides the implementation details, and provided a vector-based implementation with the same API. This makes it easy to switch data structures. It would be good to have some input on what would work best for other developers.

A second performance problem is the code for checking the minimum distance between circles. It is in a ParallelLoopBody but the distance check requires exclusive access to the common circles list. It's a little more complicated than that because the distance check is performed in two places, but basically the code was spending a lot of time waiting on the mutex and not really running in parallel. The second performance problem can be fixed by performing the distance check after the parallel EstimateRadius loop. The approach I am using is single-threaded. It compacts the circles list in place.

Another issue with the minimum distance check is that which of the two circles was preserved depended on order of evaluation, and was essentially random. I changed the EstimateRadius output format to include a Vec3f for the circle and an int for the accumulator value. The circles are sorted with the highest accumulator values first. This way the minimum distance check preserves the circles with higher accumulator values.

The HoughCircles API documentation says "Circles, corresponding to the larger accumulator values, will be returned first." But the code has not worked that way for a while. Now it will.

The cvHoughCircles wrapper function specified a circles_max limit for the size of the output array. The EstimateRadius loop was checking if the max number of circles had been reached. That seemed like unnecessary overhead in the common case when circles_max is INT_MAX. And it conflicted with the requirement to return the best circles first. I changed the code so it applies the circles_max limit at the end, after sorting the circles and the minimum distance check, when copying the circles to the output array.

There is a what looks like a typo at hough.cpp#L1441. The code returns a list of centers only, if maxCircles == 0. The HoughCircles API documentation says "you may set maxRadius to 0 to return centers only without radius search". I'm pretty sure the code meant to check maxRadius and that maxCircles is a typo. However, there is other code that sets maxRadius to a default if it is <= 0. I have not tried to fix it. It would be simple to change, but there could be existing code that depends on the current behavior, even though the current behavior is not as documented. Maybe the best thing would be to update the API documentation.

The proposed fixes are in hough.cpp on a branch. If and when they seem okay, I can submit a PR.

Steps to reproduce

I didn't see any unit tests for HoughCircles, so I added some. test_houghCircles.cpp

The regression test finds circles in the "stuff.jpg" image.

The MaxRadiusZeroCentersOnly test demonstrates the bug where setting maxRadius to 0 does not stop the code from doing the radius search.

The Beads test is for an image with many small circles. The test image is 1/4 size of the actual images used for our application.

I don't have a unit test for the bug where the circles are not returned in order with higher accumulator values first.

There should also be a performance test, but I haven't written one yet.

Test data is in on a branch in testdata/cv/imgproc.