Canny边缘检测算法的时间复杂度

Question

我正在撰写一篇关于新隐写算法的研究论文。在我的算法中，某些部分使用了Canny边缘检测器。在论文中，我需要写出这种新方法的时间复杂度，这依赖于Canny边缘检测器的时间复杂度。

问题在于，我在网上找不到任何有关Canny时间复杂度的参考资料。我甚至阅读了原始的Canny论文。我无法正确推导出它，需要在这里寻求帮助。

- Mangat Rai Modi

Answer 1

Canny边缘检测包括：

1. 将图像与一个模糊核进行卷积，
2. 将图像分别与四个边缘检测器核进行卷积，
3. 计算梯度方向，
4. 非极大值抑制，以及
5. 带有滞后阈值的二值化，

步骤（1）、（2）、（3）和（4）都是使用固定大小的核对图像进行卷积实现的。使用FFT可以在O（n log n）的时间内实现卷积，在图像具有尺寸m x n的情况下，这些步骤的时间复杂度为O（mn log mn）。

最后一步通过对图像进行后处理来去除所有高值和低值，然后丢弃与其他像素不接近的所有其他像素。这可以在O（mn）的时间内完成。

因此，总体时间复杂度为O（mn log mn）。

希望对您有所帮助！

- templatetypedef

---

非常感谢！虽然这个问题几个月前就被问过了，但这个答案将作为很多人的参考。因为Canny算法的时间复杂度没有得到适当的分析。 - Mangat Rai Modi

@templatetypedef 你能估计一下你的Canny算法的O空间复杂度吗？ - Léo Léopold Hertz 준영

@templatetypedef 非极大值抑制在卷积方面如何实现？我无法弄清楚如何做到这一点。 - TheWaveLad