Stackoverflow exception in floodfill function with OpenCV C++

Question

I'm trying to floodfill a thresholded image. I created a simple floodfill function. The function, finds the white spots from first image and then flodfills their location in another blank image. It's a recursive function so once it finds a white spot, it do not exit it until sign all the spots. Function firstly checks the right of the pixel, then down side, then left and finally up side.

Problem is when I include the "up" section to the floodfill function, it throws an exception at imshow function. But when I deleted it, there is no exception at all. I have no idea why it causes this.

Exception:

Unhandled exception at 0x00007FF82DCCA2AF (opencv_world343d.dll) in DIP.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x0000002040E73FE0).

Floodfill function:

void floodFill(cv::Mat src_8uc1,cv::Mat& index_8uc1,cv::Mat& done_8uc1,int y,int x,int index) {//recursive floodfill function
    
    cv::imshow("INDEX IN FLOODFILL", index_8uc1); //IT THROWS THE EXCEPTION RIGHT HERE!!!
    cv::waitKey(8);

    index_8uc1.at<unsigned char>(y, x) = index;
    
    //right
    if ((y < src_8uc1.rows) && (x+1 < src_8uc1.cols)) {
        if (src_8uc1.at<unsigned char>(y, x + 1) == 255) {
            if (index_8uc1.at<unsigned char>(y, x + 1) == 0) {
                x += 1;
                floodFill(src_8uc1, index_8uc1, done_8uc1, y, x, index);
            }
        }
        
    }

    //down
    if ((y+1 < src_8uc1.rows) && (x < src_8uc1.cols)) {
        if (src_8uc1.at<unsigned char>(y + 1, x) == 255) {
            if (index_8uc1.at<unsigned char>(y + 1, x) == 0) {
                y += 1;
                floodFill(src_8uc1, index_8uc1, done_8uc1, y, x, index);
            }
        }
    }

    //left
    if ((y < src_8uc1.rows) && (x - 1 < src_8uc1.cols)) {
        if (x > 0) {
            if (src_8uc1.at<unsigned char>(y, x - 1) == 255) {
                if (index_8uc1.at<unsigned char>(y, x - 1) == 0) {
                    x -= 1;
                    floodFill(src_8uc1, index_8uc1, done_8uc1, y, x, index);
                }
            }
        }

    }

    //up
    if ((y - 1 < src_8uc1.rows) && (x < src_8uc1.cols)) {
        if (y > 0) {
            if (src_8uc1.at<unsigned char>(y - 1, x) == 255) {
                if (index_8uc1.at<unsigned char>(y - 1, x) == 0) {
                    y -= 1;
                    floodFill(src_8uc1, index_8uc1, done_8uc1, y, x, index);
                }
            }
        }
    }
}

And where I defined the images:

int main( int argc, char** argv )
{

    // Read image
    cv::Mat src = cv::imread("images2/train.png", cv::IMREAD_GRAYSCALE);
    cv::Mat dst2;


    // Thresholding with threshold value set 127
    threshold(src, dst2, 127, 255, cv::THRESH_BINARY);
    if (dst2.empty()) {
        printf("Unable to read input file (%s, %d).", __FILE__, __LINE__);
    }


    cv::Mat src_8uc1 = src.clone(); //FIRST IMAGE
    cv::Mat index_8uc1 = src.clone();
    index_8uc1 = cv::Mat::zeros(src.rows, src.cols, CV_8UC1); //indexed image (0)
    cv::Mat done_8uc1 =src.clone(); //result


    int index = 40;


    for (int y = 0; y <= src_8uc1.size().height; y++)
        for (int x = 0; x <= src_8uc1.size().width; x++)
        {
            if ((y < src_8uc1.rows) && (x < src_8uc1.cols)) {
                if (dst2.at<uchar>(y, x) == 255) {
                    if (index_8uc1.at<unsigned char>(y, x) == 0) {
                        //done_8uc1.at<uchar>((x, y))= 255;
                        floodFill(dst2, index_8uc1, done_8uc1, y, x, index);
                        index += 1;
                    }
                }
            }
        }



    cv::waitKey(0); // wait until keypressed


}

--------------------------------UPDATE!!!-----------------------------

It's not a exact solution but I had to bypass the error by increasing the "Stack reserve size" in the debugger settings. See here

`Stack overflow` means that your recursion is to deep. Implement BFS (currently you have DFS). Check the callstak, you will see lots of `floodFill` on it. — Marek R, Mar 25 '22 at 12:22
yeah, push work into an explicit stack/queue (or even a set) and take work from there until empty. make sure you aren't queueing work that you know you've visited or queued already. — Christoph Rackwitz, Mar 25 '22 at 12:25
@Christoph Rackwitz I don't think so. The "x" and y" values are below the image size when exception happen. (My comment is for the first comment) — Tim's, Mar 25 '22 at 12:25
change your algorithm to fill line by line, not pixel by pixel. — Marek R, Mar 25 '22 at 12:39
I would recommend that too. scanline filling is fun. take a little thought. payoff is great. code will be cleaner and faster (less duplicated work). — Christoph Rackwitz, Mar 25 '22 at 13:39

wohlstad · Answer 1 · 2023-03-20T17:13:54.570

floodFill is a recursive function. Each recursive call adds a frame to the stack. The maximum depth of the stack usage depends on the size of the image. When the stack exceeds it's size you'll get a stack overflow exception. Since all functions calls within a thread share the stack, it could very well be that by the time imshow is called the stack is already almost full.

You can try to reduce the image size, to verify that this is indeed the cause of the problem.
You can try an iterative implementation instead of recursive to avoid stack overflow.
Why do you need to call imshow from within a recursive function that is called recursivly quite a lot of time anyway ?

Stackoverflow exception in floodfill function with OpenCV C++

1 Answers1