# Circle Detection for Fourier-Mellin Shear Estimation

**URL:** <https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674>\
**Category:** C++\
**Tags:** fourier-mellin, shear, hough\
**Created:** [February 21, 2022, 10:58pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674 "2022-02-21T22:58:47Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![der\_luftmensch](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@der\_luftmensch](https://forum.opencv.org/u/der_luftmensch)\
**Post date:** [February 21, 2022, 10:58pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/1 "2022-02-21T22:58:47Z")

</div>

I have the following cross-correlation image:

 ![FourierMellinShear](https://us1.discourse-cdn.com/flex020/uploads/opencv/original/2X/2/2807a4b5f7a06b96ddf5ac14097d892a755b90a3.jpeg)

This image is originally 0-1 floats. I need to detect the circle in the image, but I am having trouble doing so with `cv::HoughCircles`. Clearly, I’d prefer not to be forced to run Canny edges (preferring instead to binarize the image myself), but the functions give me no choice. Any ideas for parameters or alternative methods? The SNR of this image is representative of the typical problem I am trying to solve.

See this example of “self-binarizing” via simple thresholding that fails `cv::HoughCircles`:  
 ![SelfBinarized](https://us1.discourse-cdn.com/flex020/uploads/opencv/original/2X/3/37514fc4af0257ea31657a4e23816ffd817c6281.png)

See also [this post.](https://github.com/opencv/opencv/issues/11144#issuecomment-1047378569)

---

<div class="post-metadata">

**Author:** ![sturkmen](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.opencv.org/sturkmen/32/13_2.png) [@sturkmen](https://forum.opencv.org/u/sturkmen)\
**Post date:** [February 22, 2022, 6:45am UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/2 "2022-02-22T06:45:07Z")

</div>

see [opencv\_contrib/edge\_drawing.py at 4.x · opencv/opencv\_contrib · GitHub](https://github.com/opencv/opencv_contrib/blob/4.x/modules/ximgproc/samples/edge_drawing.py)

---

<div class="post-metadata">

**Author:** ![laurent.berger](https://avatars.discourse-cdn.com/v4/letter/l/ec9cab/32.png) [@laurent.berger](https://forum.opencv.org/u/laurent.berger)\
**Post date:** [February 22, 2022, 8:09am UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/3 "2022-02-22T08:09:25Z")

</div>

Try to calculate radial distribution

---

<div class="post-metadata">

**Author:** ![der\_luftmensch](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@der\_luftmensch](https://forum.opencv.org/u/der_luftmensch)\
**Post date:** [February 22, 2022, 8:54pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/5 "2022-02-22T20:54:42Z")

</div>

EdgeDrawing seems to work well, but quickly hangs on new input with the default parameters. This attached image is an example where the call to `detectEllipses` never returns (or takes too long for me to wait around for it to finish). Using 4.5.5. Any ideas?

![circles_input](https://us1.discourse-cdn.com/flex020/uploads/opencv/original/2X/3/3d79900ae0675edae76ac15b0524f8e8733fb3f1.png)

---

<div class="post-metadata">

**Author:** ![der\_luftmensch](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@der\_luftmensch](https://forum.opencv.org/u/der_luftmensch)\
**Post date:** [February 22, 2022, 8:56pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/6 "2022-02-22T20:56:37Z")

</div>

My circle of interest is not guaranteed to be centered at the image center, maybe that was something you were assuming. Though the global image maximum should lay on the ring. Could you expand on your suggestion? Thanks!

---

<div class="post-metadata">

**Author:** ![sturkmen](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.opencv.org/sturkmen/32/13_2.png) [@sturkmen](https://forum.opencv.org/u/sturkmen)\
**Post date:** [February 22, 2022, 10:19pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/7 "2022-02-22T22:19:51Z")

</div>

could you add the code you tested. i have no problem with your image.

---

<div class="post-metadata">

**Author:** ![der\_luftmensch](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@der\_luftmensch](https://forum.opencv.org/u/der_luftmensch)\
**Post date:** [February 23, 2022, 1:15pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/8 "2022-02-23T13:15:56Z")

</div>

```auto
#include <iostream>                                                                                                      
#include <opencv2/core.hpp>                                                     
#include <opencv2/highgui.hpp>                                                  
#include <opencv2/imgproc.hpp>                                                  
#include <opencv2/ximgproc/edge_drawing.hpp>                                    
                                                                                
static void about() {                                                           
  std::cout << "\ntest_edge_drawing\n";                                         
}                                                                               
                                                                                
int main(int argc, const char** argv) {                                         
  const cv::String keys =                                                       
      "{ h help | | print this message }"                                  
      "{ @image | | /path/to/image }";                                 
                                                                                
  cv::CommandLineParser parser(argc, argv, keys);                               
                                                                                
  if (parser.has("help")) {                                                     
    about();                                                                    
    parser.printMessage();                                                      
    std::cout << std::endl;                                                     
    return 0;                                                                   
  }                                                                             
                                                                                
  if (!parser.check()) {                                                        
    parser.printErrors();                                                       
    exit(1);                                                                    
  }                                                                             
                                                                                
  const auto image_path = parser.get<std::string>("@image");                    
  cv::Mat image = cv::imread(image_path, cv::IMREAD_GRAYSCALE);                 
                                                                                
  if (image.empty()) {                                                          
    std::cerr << "Failed to load image " << image_path;                         
    exit(1);                                                                    
  }                                                                             
                                                                                
  bool active = true;                                                           
  int32_t count = 0;
  while (active) {                                                              
    std::cout << "Run #" << count++ << std::endl;                               
                                                                                
    //                                                                          
    // Not efficient, but more closely mimics my initial case:                  
    //                                                                          
    auto ed = cv::ximgproc::createEdgeDrawing();                                
                                                                                
    ed->detectEdges(image);                                                     
    cv::Mat edges;                                                              
    ed->getEdgeImage(edges);                                                    
    cv::imshow("Edges", edges);                                                 
                                                                                
    std::vector<cv::Vec6d> ellipses;                                            
    ed->detectEllipses(ellipses);                                               
                                                                                
    cv::Mat viz = image.clone();                                                
    for(const auto& e : ellipses) {                                             
      cv::ellipse(viz, {e[0], e[1]}, {e[2] + e[3], e[2] + e[4]}, e[5], 0,       
      360, {128}, 2, cv::LINE_AA);                                              
    }                                                                           
    cv::imshow("Circles", viz);                                                 
                                                                                
    //                                                                          
    // ESC to terminate:                                                        
    //                                                                          
    if (cv::waitKey(1) == 27) {                                                 
      active = false;                                                           
    }                                                                           
  }                                                                             
                                                                                
  return 0;                                                                     
}

```

Strangely, I don’t see the hanging with this minimal example…

---

<div class="post-metadata">

**Author:** ![der\_luftmensch](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@der\_luftmensch](https://forum.opencv.org/u/der_luftmensch)\
**Post date:** [February 23, 2022, 1:21pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/9 "2022-02-23T13:21:10Z")

</div>

My failing code snippet is the following:

```auto
    cv::normalize(cross_correlation_centered_, cross_correlation_centered_, 0,  
                  1.0, cv::NORM_MINMAX);                                        
                                                                                
    // Circles experiment:                                                      
    Timer timer;                                                                
    timer.start();                                                              
    vision::soft_threshold(cross_correlation_centered_,                         
                           cross_correlation_centered_, 0.6, 4.0);              
    cv::Mat gray;                                                               
    cv::Rect roi(cv::Point(peak.x - 50, peak.y - 50),                           
                 cv::Point(peak.x + 50, peak.y + 50));                          
    vision::convert_and_scale(cross_correlation_centered_(roi), gray, CV_8U);   
    cv::GaussianBlur(gray, gray, {3, 3}, 0.0, 0.0);                             
                                                                                
    static int index = 0;                                                       
    cv::imwrite("circles_input" + std::to_string(index++) + ".png", gray);      
                                                                                
    auto ed = cv::ximgproc::createEdgeDrawing();                                
    ed->detectEdges(gray);                                                      
    cv::Mat edges;                                                              
    ed->getEdgeImage(edges);                                                    
    cv::imshow("Edges", edges);                                                 
    std::vector<cv::Vec6d> ellipses;                                            
    ed->detectEllipses(ellipses);                                               
                                                                                
    LOG(DEBUG) << "Found " << ellipses.size() << " ellipses";                   
    for(const auto& e : ellipses) {                                            
      cv::ellipse(gray, {e[0], e[1]}, {e[2] + e[3], e[2] + e[4]}, e[5], 0,      
      360, {128}, 2, cv::LINE_AA);                                              
    }                                                                           
                                                                                
    LOG(DEBUG) << "Circles: " << timer.stop().elapsed_ms() << "ms";             
    cv::imshow("Circles", gray);

```

Removing unnecessary calls to `cv::imshow`, `getEdgeImage`, and `cv::ellipse`, etc. makes no difference.

---

<div class="post-metadata">

**Author:** ![sturkmen](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.opencv.org/sturkmen/32/13_2.png) [@sturkmen](https://forum.opencv.org/u/sturkmen)\
**Post date:** [February 23, 2022, 2:26pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/10 "2022-02-23T14:26:22Z")

</div>

see the last update [improvements on EdgeDrawing · opencv/opencv\_contrib@081bebd · GitHub](https://github.com/opencv/opencv_contrib/commit/081bebdc4cd099aec942a802a3f72a754e2bd7da)

maybe input image is not CV\_8UC1

---

<div class="post-metadata">

**Author:** ![der\_luftmensch](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@der\_luftmensch](https://forum.opencv.org/u/der_luftmensch)\
**Post date:** [February 23, 2022, 3:40pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/11 "2022-02-23T15:40:42Z")

</div>

The image is 8UC1, the call to convert and scale does this and it doesn’t hang or crash on the first image it sees, but the second. Here is the gdb output:

```auto
#0 0x00007f1dbbc7e7c6 in cv::ximgproc::EdgeDrawingImpl::SplitSegment2Lines(double*, double*, int, int) ()
    at /opt/opencv4.5.5/lib/libopencv_ximgproc.so.405
#1 0x00007f1dbbc7fd71 in cv::ximgproc::EdgeDrawingImpl::detectEllipses(cv::_OutputArray const&) ()
    at /opt/opencv4.5.5/lib/libopencv_ximgproc.so.405

```

---

<div class="post-metadata">

**Author:** ![der\_luftmensch](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@der\_luftmensch](https://forum.opencv.org/u/der_luftmensch)\
**Post date:** [February 23, 2022, 4:25pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/12 "2022-02-23T16:25:39Z")

</div>

I changed my test program to run through a directory of saved images similar to that shared above and it reliably core dumps, though some images are processed just fine, either with no returned ellipses or a correct one. Here is an example offending image:  
 ![circles_input7](https://us1.discourse-cdn.com/flex020/uploads/opencv/original/2X/a/a857e1d9e4a80d4f02bd06880bfc757fb98b78b3.png)

---

<div class="post-metadata">

**Author:** ![sturkmen](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.opencv.org/sturkmen/32/13_2.png) [@sturkmen](https://forum.opencv.org/u/sturkmen)\
**Post date:** [February 23, 2022, 6:30pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/13 "2022-02-23T18:30:42Z")

</div>

seems there is a bug.

as a workaround you can call `detectLines()` first

```auto
vector<Vec4f> lines;
ed->detectLines(lines);
std::vector<cv::Vec6d> ellipses;                                            
ed->detectEllipses(ellipses);

```

---

<div class="post-metadata">

**Author:** ![der\_luftmensch](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@der\_luftmensch](https://forum.opencv.org/u/der_luftmensch)\
**Post date:** [February 23, 2022, 6:37pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/14 "2022-02-23T18:37:02Z")

</div>

> [@sturkmen](#):
>
> ```auto
> vector<Vec4f> lines;
> ed->detectLines(lines);
> 
> ```

Thanks! Adding this seems to fix it.

---

<div class="post-metadata">

**Author:** ![sturkmen](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.opencv.org/sturkmen/32/13_2.png) [@sturkmen](https://forum.opencv.org/u/sturkmen)\
**Post date:** [February 23, 2022, 6:47pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/15 "2022-02-23T18:47:14Z")

</div>

also i advice playing with params

for example

```auto
ed->params.GradientThresholdValue = 100;
ed->params.NFAValidation= false; // can return more lines and ellipses ( without internal filtering)

```

---

<div class="post-metadata">

**Author:** ![Steve\_in\_Denver](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Steve\_in\_Denver](https://forum.opencv.org/u/Steve_in_Denver)\
**Post date:** [February 23, 2022, 8:29pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/16 "2022-02-23T20:29:30Z")

</div>

> [@der\_luftmensch](#):
>
> rly, I’d prefer not to be forced to run Canny edges (preferring instead to binarize the image myself), but the functions give me no choice. Any ideas for parameters or alternative methods? The SNR of this image is representative of the typical problem I am trying to solve

Do you not want to run canny for performance reasons, or for some other reason?

Do you know where the circle is going to be in the image, or could you do a first pass to determine where it is? If so you could run canny only on the image ROI that is likely to contain the circle which could really save on processing time.

I have had luck searching for an appropriate canny parameter by starting at the center of a bounded range, and alternately searching higher / lower. When I get no edges back I stop searching higher, and when I get “too many” edges back, I stop searching lower. This might be too expensive for you to do, but I found it works well when you have to be robust to changes in edge intensity etc.

I implemented the circle detection described here:  
[http://www.cs.bsu.edu/homepages/kjones/kjones/circles.pdf](http://www.cs.bsu.edu/homepages/kjones/kjones/circles.pdf)

My notes say “II.8 - II.15” - I don’t recall why I chose this method from the paper, and I don’t recall why I chose this over hough circles, but it provides good results.

---

<div class="post-metadata">

**Author:** ![sturkmen](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.opencv.org/sturkmen/32/13_2.png) [@sturkmen](https://forum.opencv.org/u/sturkmen)\
**Post date:** [February 23, 2022, 9:45pm UTC](https://forum.opencv.org/t/circle-detection-for-fourier-mellin-shear-estimation/7674/17 "2022-02-23T21:45:25Z")

</div>

i created a [PR to fix the bug](https://github.com/opencv/opencv_contrib/pull/3181)