OpenCV中实现的findContours方法的算法效率是多少？

Question

我有一个关于findContoursOpenCV 中实现的方法的算法效率的问题。假设我有一段代码或多或少看起来像这样（在 Python 3.6 中，但在 C++ 中看起来几乎相同）：

\n\n

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

\n\n

其中img_mtx_binary可以是 Numpy 矩阵或 C++ Mat 对象，其中包含二进制 0 或 255 图像，轮廓是建立的轮廓的列表。图像大小为NxM。

\n\n

用Big O表示法实现的算法的效率（或效率范围）是多少？我发现它使用了 Suzuki 算法[1]，但是在官方论文[2]中我找不到这方面的明确信息。

\n\n

一切顺利，

\n\n

米\xc5\x82osz

\n

Answer 1

当算法找到所有轮廓时，它必须至少查看每个像素一次。对于轮廓跟踪，它最多查看每个像素的 8 个邻居，并且通过标记过程避免多次处理相同的内容。每个像素的操作数量是有限的。

因此，如果您喜欢图像区域中的线性，则运行时间为 O(NM)，这是最佳的。该术语很可能（渐进地）主导额外的簿记。