What is the algorithm that opencv uses for finding contours?

Question

I need to use cv::FindContours() in a program and I have to know the algorithm behind that.

What algorithm does openCV use to find contours?

How does it work?

Solution 1

If you read the documentation it is mentioned this function implements the algorithm of:

Suzuki, S. and Abe, K., Topological Structural Analysis of Digitized Binary Images by Border Following. CVGIP 30 1, pp 32-46 (1985)

OpenCV is open source if you want to see how this is implemented just need to read the code: https://github.com/opencv/opencv/blob/master/modules/imgproc/src/contours.cpp#L1655

One of the answers to this question has the link to the paper in question, that link is dead and the paper is behind a pay wall, perhaps google can help with finding a free copy.

Solution 2

As of Sep. 2018, the paper is available through Google Scholar. Nonetheless, here is the abstract in case the paper is taken down:

Two border following algorithms are proposed for the topological analysis of digitized binary images. The first one determines the surroundness relations among the borders of a binary image. Since the outer borders and the hole borders have a one-to-one correspondence to the connected components of l-pixels and to the holes, respectively, the proposed algorithm yields a representation of a binary image, from which one can extract some sort of features without reconstructing the image. The second algorithm, which is a modified version of the first, follows only the outermost borders (i.e., the outer borders which are not surrounded by holes). These algorithms can be effectively used in component counting, shrinking, and topological structural analysis of binary images, when a sequential digital computer is used.