improved version of HoughCircles (HOUGH_GRADIENT_ALT method) #16561

vpisarev · 2020-02-12T03:17:21Z

relates #16187 (on one image the eye is not detected with param2=0.9, need to lower it down to 0.85). Overall, the quality is much better than the existing HOUGH_GRADIENT method.

Usage:

Mat smoothed;
GaussianBlur(grayscale_image, smoothed, Size(7, 7), 1.5, 1.5);
HoughModes method = HOUGH_GRADIENT_ALT;
double dp = 1.5;
double minDist = 10;
double cannyThreshold = 300;
double minCos2 = 0.9; // 0.85 for one of the eye images
int minRadius = 7;
int maxRadius = 500;
std::vector<Vec3f> circles;
HoughCircles(smoothed, circles, method, dp, minDist,
           cannyThreshold, minCos2, minRadius, maxRadius);

this code detects circles on most of the images that I have (~100 images; the proper regression test will be added later). When it does not, try to narrow down the radius search range [minRadius, maxRadius] and decrease a bit minCos2 from 0.9 down to 0.85..0.75.

I agree to contribute to the project under OpenCV (BSD) License.
To the best of my knowledge, the proposed patch is not based on a code under GPL or other license that is incompatible with OpenCV
The PR is proposed to proper branch
There is reference to original bug report and related work
(need to add more tests in the future) There is accuracy test, performance test and test data in opencv_extra repository, if applicable
Patch to opencv_extra has the same branch name.
The feature is well documented and sample code can be built with the project CMake

* make use of param2. make it minCos2 (minimal value of squared cosine between the gradient at the pixel edge and the vector connecting it with circle center). with minCos2=0.85 we can detect some more eyes :)

alalek

New algorithm is interesting, but linked issue doesn't ask for that.
The issue blames on regression(changes) in implementation of existed algorithm between OpenCV versions.

alalek · 2020-02-12T14:34:59Z

modules/imgproc/include/opencv2/imgproc.hpp

@@ -473,7 +473,8 @@ enum HoughModes {
    /** multi-scale variant of the classical Hough transform. The lines are encoded the same way as
    HOUGH_STANDARD. */
    HOUGH_MULTI_SCALE   = 2,
-    HOUGH_GRADIENT      = 3 //!< basically *21HT*, described in @cite Yuen90
+    HOUGH_GRADIENT      = 3, //!< basically *21HT*, described in @cite Yuen90
+    HOUGH_GRADIENT_ALT  = 4


documentation

alalek · 2020-02-12T14:36:18Z

modules/imgproc/src/hough.cpp

+static int circle_popcnt(uint64 mask)
+{
+    int count = 0;
+    for(int b = 0; b < 64; b++, mask >>= 1)
+        count += (mask & 1) != 0;


reuse existed popcnt implementations.

I have not found simple inline function that takes uint64(_t) on input, just universal intrinsic that I do not need. I improved the implementation to use CV_POPCOUNT_U64 if possible. Someone (maybe me) in some subsequent patch can move it to some of core headers and rename cv::circle_popcnt() to cv::popcount() or cvPopCount64() or something like that.

alalek · 2020-02-12T14:37:47Z

modules/imgproc/src/hough.cpp

+    if( maxRadius <= 0 ) maxRadius = std::min(img.cols, img.rows)*0.5;
+    if( minRadius > maxRadius ) std::swap(minRadius, maxRadius);


Avoid merging of if's conditions and if's body.
Let make code coverage reports more useful.

alalek · 2020-02-12T14:39:38Z

modules/imgproc/src/hough.cpp

+    Mat Dx, Dy, edges;
+    Scharr(img, Dx, CV_16S, 1, 0);
+    Scharr(img, Dy, CV_16S, 0, 1);
+    Canny(Dx, Dy, edges, cannyThreshold/2, cannyThreshold, true);


I believe such pre-processing should be optional.

it's not preprocessing. Canny edge detector is the essential part of HoughCircles that takes grayscale image on input. HOUGH_GRADIENT method does the same.

alalek · 2020-02-12T14:42:13Z

modules/imgproc/src/hough.cpp

+    {
+        for( int x = 0; x < edges.cols; x++ )
+        {
+            if(!edgeData[y*estep + x] || mdata[y*mstep + x])


Avoid manual address arithmetic.
There is still efficient .at(y, x) method for release builds and there are extra checks in debug builds.

This is the inner loop where performance matters. Address arithmetic is faster here and will not be replaced with .at

alalek · 2020-02-12T14:43:35Z

modules/imgproc/src/hough.cpp

+    circles.clear();
+    std::vector<Vec4f> nz;
+
+    std::vector<Point> stack;


There is std::stack for that.

std::stack is an adapter on top of std::vector (or list or deque). Why use this adapter instead of plain simple std::vector?

alalek · 2020-02-12T14:45:07Z

modules/imgproc/src/hough.cpp

+                int sx = cvRound(vx * 1024 / mag);
+                int sy = cvRound(vy * 1024 / mag);
+
+                int x0 = cvRound((p.x * idp) * 1024);
+                int y0 = cvRound((p.y * idp) * 1024);


What is 1024 magic number?
Consider declaring this constant separately with descriptive name.

Same notes are about 64, 7, 3 below.

alalek · 2020-02-12T14:47:58Z

modules/imgproc/src/hough.cpp

+            }
+            while(!stack.empty());


Don't add line break before while in do while statements.

alalek · 2020-02-12T14:51:18Z

modules/imgproc/src/hough.cpp

+                int prev = prev_idx[j];
+                prev_idx[j] = i;
+
+                if( std::abs(rij - r_arc) < (r_arc + 80)*0.03 && prev+1 == i && !stop_marker )


80
0.03

and below

4000
0.06

"magic numbers"

alalek · 2020-02-12T14:56:35Z

modules/imgproc/test/test_houghcircles.cpp

+    for( int k = 1; k < 2; k++ )
+    {
+        int method = k == 0 ? HOUGH_GRADIENT : HOUGH_GRADIENT_ALT;


It is better to split/parametrize test itself instead of internal loops.

* cleaned up the implementation; added comments, replaced built-in numeic constants with symbolic constants * rewrote circle_popcount() to use built-in popcount() if possible * modified some of HoughCircles tests to use method parameter instead of the built-in loop

vpisarev · 2020-02-12T23:55:59Z

@alalek, the original issue complains about HoughCircles quality on some particular images, but the problem is much deeper. For a long time I knew that cv::HoughCircles() does not work well. But I was not sure about the effects of the latest modifications, if they improved or degraded quality and if there is some good revision of this implementation. So, for confirmation I took several revisions of OpenCV and ran them on a dataset of ~100 images (mostly from here: https://github.com/AlanLuSun/Circle-detection, but also my little collection of circles images and photos from Internet). The results are really bad. The existing implementation is very advanced in terms of speed optimization efforts, but it's fundamentally wrong. The newly proposed algorithm, on which I spent the whole week, uses the similar first phase with 2D accumulator update, but the center selection and the radius estimation are completely different. It's not compatible with the existing implementation. It needs somewhat higher cannyThreshold (param1). It treats minRadius a bit differently. It treats param2 completely differently, because accumThreshold is very difficult to set to some "universally good" value, you need to vary it from image to image and too bad if you have circles of very different size in the same image - there is no good accumThreshold value in such case. It does not have "center only" mode, because any Hough-based algorithm for circle detection, be it HOUGH_GRADIENT or HOUGH_GRADIENT_ALT, produce a lot of fake centers. So I decided to make a separate algorithm without having to keep compatibility with the previous version. In OpenCV 5.0, perhaps, HOUGH_GRADIENT can be removed completely.

catree · 2020-02-14T11:01:07Z

If HOUGH_GRADIENT_ALT performs significantly better than HOUGH_GRADIENT with comparable speed performance, add somewhere in the documentation that HOUGH_GRADIENT_ALT method should be preferred?
Otherwise, a note that HOUGH_GRADIENT_ALT is more accurate while HOUGH_GRADIENT is faster?

Also, it would be great to have some numbers to evaluate the performance of the new method on a ground truth dataset.

vpisarev · 2020-02-14T15:43:13Z

@catree, thanks! More detailed test that evaluates performance over a real dataset is being developed.

feature-engineer · 2020-06-14T13:06:50Z

@vpisarev When will a test evaluating the performance of the Hough circles implementations be published?

nadavv · 2020-06-25T08:33:55Z

Hi,
As I am new here, could you please explain what it would take for this version to be available in python?
Muchas gracias

* improved version of HoughCircles (HOUGH_GRADIENT_ALT method) * trying to fix build problems on Windows * fixed typo * * fixed warnings on Windows * make use of param2. make it minCos2 (minimal value of squared cosine between the gradient at the pixel edge and the vector connecting it with circle center). with minCos2=0.85 we can detect some more eyes :) * * added description of HOUGH_GRADIENT_ALT * cleaned up the implementation; added comments, replaced built-in numeic constants with symbolic constants * rewrote circle_popcount() to use built-in popcount() if possible * modified some of HoughCircles tests to use method parameter instead of the built-in loop * fixed warnings on Windows

vpisarev added 4 commits February 12, 2020 06:13

improved version of HoughCircles (HOUGH_GRADIENT_ALT method)

6bd22fa

trying to fix build problems on Windows

289ce52

fixed typo

7b88ec5

* fixed warnings on Windows

6a0ecc3

* make use of param2. make it minCos2 (minimal value of squared cosine between the gradient at the pixel edge and the vector connecting it with circle center). with minCos2=0.85 we can detect some more eyes :)

alalek reviewed Feb 12, 2020

View reviewed changes

fixed warnings on Windows

0d39a8f

asmorkalov added Hackathon https://opencv.org/opencv-hackathon-starts-next-week/ category: imgproc labels Feb 14, 2020

alalek approved these changes Feb 14, 2020

View reviewed changes

alalek merged commit cc259e4 into opencv:master Feb 14, 2020

vpisarev mentioned this pull request May 24, 2020

HoughCircles accuracy decreased in opencv 4.1.1 after upgrade from 3.1.0 #16187

Closed

vpisarev deleted the better_hough_circles branch May 28, 2020 18:21

alalek mentioned this pull request Dec 31, 2020

Different shape of result of the method HOUGH_GRADIENT_ALT in Python #19238

Closed

4 tasks

alalek mentioned this pull request Aug 22, 2021

Fix hough circles alt dimensions #20584

Merged

6 tasks

		if( maxRadius <= 0 ) maxRadius = std::min(img.cols, img.rows)*0.5;
		if( minRadius > maxRadius ) std::swap(minRadius, maxRadius);

Uh oh!

improved version of HoughCircles (HOUGH_GRADIENT_ALT method) #16561

improved version of HoughCircles (HOUGH_GRADIENT_ALT method) #16561

Uh oh!

Conversation

vpisarev commented Feb 12, 2020 • edited by alalek Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

alalek left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vpisarev Feb 12, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vpisarev Feb 12, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vpisarev commented Feb 12, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

catree commented Feb 14, 2020

Uh oh!

vpisarev commented Feb 14, 2020

Uh oh!

feature-engineer commented Jun 14, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

nadavv commented Jun 25, 2020

Uh oh!

Uh oh!

vpisarev commented Feb 12, 2020 •

edited by alalek

Loading

vpisarev Feb 12, 2020 •

edited

Loading

vpisarev Feb 12, 2020 •

edited

Loading

vpisarev commented Feb 12, 2020 •

edited

Loading

feature-engineer commented Jun 14, 2020 •

edited

Loading