cv2.findChessboardCorners() running endlessly on certain images

[JeremyKeusters]

System Information

OpenCV python version: both 3.4.18.65 and 4.7.0.72
Operating System / Platform: Ubuntu 18.04 and macOS 13.2.1
Python version: 3.7

Detailed description

I’m using OpenCV to find chessboard corners on an image using cv2.findChessboardCorners(). It can happen that an image is passed into the function that is of bad quality or almost completely black. When this happens, the function just endlessly runs, trying to find the corners.

I initially opened a topic on the OpenCV forum, but there it was confirmed that it's a bug, hence why I'm also opening a bug report here.

This issue is a problem to me because it completely blocks my application when this happens.

Steps to reproduce

This issue can easily be reproduced.

You can use the code snippet below:

import cv2

test = cv2.imread("/path/to/the/image/27-04-2023_14-13-21_494.png")

found, corners = cv2.findChessboardCorners(image=test,
                                           patternSize=(26, 16),
                                           flags=(cv2.CALIB_CB_FAST_CHECK +
                                                  cv2.CALIB_CB_ADAPTIVE_THRESH +
                                                  cv2.CALIB_CB_NORMALIZE_IMAGE))

print(found)

in combination with the image below:

You will notice that the function just endlessly keeps running and consuming resources (I’ve let it run for +15 minutes already).

Issue submission checklist

• I report the issue, it's not a question
• I checked the problem with documentation, FAQ, open issues, forum.opencv.org, Stack Overflow, etc and have not found any solution
• I updated to the latest OpenCV version and the issue is still there
• There is reproducer code and related data files (videos, images, onnx, etc)

[Daniyal98]

I ran a test on this and found out that the testChessboardCorners function eventually returns. It is not running endlessly. It takes a lot of time in functions like processQuads and it is running in a loop so it takes around 3 minutes for the function to return.

[JeremyKeusters]

Even if it returns after some time (it did not return after 20 minutes on my MacBook Pro 2020 i5), I guess it's still not expected behaviour that it takes so long, especially since the cv2.CALIB_CB_FAST_CHECK flag is provided? I can't believe that it is not able to determine faster that this image does not contain a chessboard.

[AleksandrPanov]

checked, findChessboardCorners() just works for a very long time.

There are two problems:

1. cv.adaptiveThreshold finds a lot of noise to an almost black picture.
   
2. findContours finds many little contours (about 30k), then part of the contours is filtered out (90%), and then processed for a long time. The function needs to filter out more contours, maybe should to increase the threshold for the size of the contours (now int min_size = 25 - empiric bound for minimal allowed perimeter for squares).

[thewoz]

The problems in my opinion are two:

• The first that CALIB_CB_FAST_CHECK fails.
  Even though there is no checkChessboardBinary() in the image it returns positive and the rest of the findChessboardCorners code is called.

• The second that once the adaptive threshold is applied all the noise comes out and generateQuads starts to find several contours in the order of 200K that in turn generate 26159 quads.
  This situation slowing down the execution of the function quite a bit.
  Especially as several rounds of adaptive thresholds and dilations are performed before the function exits.

In my opinion there are two possible things that can be done to mitigate the situation in this and similar cases.

The first, more expensive, is to figure out why checkChessboardBinary() fails.

The second, as already suggested, is to change the threshold that is used to filter quads.
This solution does not completely solve the problem, but it improves it by quite a bit in that it speeds up code execution time.
Ad esempio passare da 25 a 400 change the execution time from 570 sec to 130 sec on my machine.

The threshold is now defined in this way:

// empirical bound for minimal allowed perimeter for squares
int min_size = 25; //cvRound( image->cols * image->rows * .03 * 0.01 * 0.92 );

To me 25 is a ridiculous number.
By the way it is not as written the minimum perimeter of the quad but the minimum area of the quad as seen just below:

Rect contour_rect = boundingRect(contour);
        if (contour_rect.area() < min_size)
            continue;

25 therefore means a quad of side 5 pixels!

I don't know why this part of the code was commented out and what the various multiplicative factors mean but it made more sense.
int min_size = 25; //cvRound( image->cols * image->rows * .03 * 0.01 * 0.92 );
In my opinion the solution is to pass to generateQuads() the size of the checkerboard and calculate min_size in the following way:
int min_size = ((image->cols * image->rows) * 0.25 / (pattern_size.width * pattern_size.height)) * 0.8;
That is, as if checkerboard occupies at least 25% of the image and that each square occupies roughly 80% of the space it has available

If it makes sense I make a pull request on this

[JeremyKeusters]

Thanks for your input @thewoz ! In my opinion, the most critical problem is the failing CALIB_CB_FAST_CHECK. For me, the second problem is more a 'performance issue', while the first one is a bug. It's super obvious that no chessboard will ever be found on the image that is visible enough to work, and so in my expectation, the function should immediately skip the image.

Nevertheless, any contributions that work towards solving the issue are of course more than welcome, so would be great if you're willing to spend time in this @thewoz !

[spdfghi]

To takle this problem, I think controling threshold for the size of the contours or binarization is less ensential, since we can make a binary background whitch contains small size contours already. Maybe we can do downsampling/blur operations in fast check, which can eliminate small contours in image.
The below code I used run more faster, like 1-2 seconds, for test image of this issue.

if (flags & CALIB_CB_FAST_CHECK)
{
    //perform new method for checking chessboard using a binary image.
    //image is binarised using a threshold dependent on the image histogram
    int max_cols = 1000;
    cv::Mat small_img;
    if (thresh_img_new.cols > max_cols)
    {
        small_img = thresh_img_new.clone();
        cv::resize(small_img, small_img, cv::Size(max_cols, img.rows * max_cols / (float)img.cols));
    }
    if (checkChessboardBinary(small_img, pattern_size) <= 0) //fall back to the old method
    {
        if (!checkChessboard(small_img, pattern_size))
        {
            corners_.release();
            return false;
        }
    }
}