CODEWITHSUNDEEP
pythonalgorithmopencvimage-processingbig-o
Mimi
Mimi

Reputation: 95

What is the algorithmic efficency of findContours method implemented in OpenCV?

I have a question about algorithmic efficiency of findContours method, which is implemented in OpenCV. Lets say that I have a code more or less looking like that (in Python 3.6, but it looks almost identical in C++):

# ... Some image processing code ...
_, contour, _ = cv2.findContours(img_mtx_binary, 
                                 cv2.RETR_TREE, 
                                 cv2.CHAIN_APPROX_NONE)
# ... More image processing code ...

where img_mtx_binary may be Numpy matrix or C++ Mat object, which contains binary 0 or 255 image and contour is the list of founded contours. The image is size of NxM.

What is the efficiency (or range of efficiencies) of implemented algorithm in Big O notation? I found that it uses Suzuki algorithm [1], but in official paper [2] I can't find the clear information about this.

All the best,

Miłosz

Upvotes: 3

Views: 1870

Answers (1)

user1196549
user1196549

Reputation:

As the algorithm finds all contours, it has to look at every pixel at least once. For outline following, it looks at at most 8 neighbors of every pixel, and by a marking process avoids processing the same several times. The number of operations per pixel is bounded.

So the running time is O(NM), if you prefer linear in the image area, and this is optimal. This term most probably dominates (asymptotically) the additional bookeeping.

Upvotes: 5

Related Questions