python - 在 OpenCV 中实现的 findContours 方法的算法效率如何？

Question

我对 findContours 方法的算法效率有疑问，该方法是在 OpenCV 中实现的。假设我有一个或多或少看起来像那样的代码(在 Python 3.6 中，但它在 C++ 中看起来几乎相同):

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

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

Big O 表示法中实现算法的效率(或效率范围)是多少？我发现它使用的是 Suzuki 算法 [1] , 但在官方论文中 [2]我找不到关于此的明确信息。

祝一切顺利

米沃什

Answer 1

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

所以运行时间是O(NM)，如果你更喜欢图像区域的线性，这是最优的。这一项很可能支配(渐进地)额外的簿记。