如何改进这个算法？（图像处理）

Question

好的，在完成了几个小时的图像处理文档后（我是一个初学者），我决定实现一个我自己的边缘检测函数，以便更好地理解它背后的数学原理。幸运的是我能做到，但是我的算法太慢了（O（n^2））。我将用下面的帧处理部分发布代码：

ret, frame = cap.read()
grayed  = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
rows, cols = grayed.shape
for row in range(rows-2):
    for col in range(cols-2):
        Gx = grayed.item(row+2,col)+2*grayed.item(row+2,col+1)+grayed.item(row+2,col+1)-(grayed.item(row,col)+2*grayed.item(row,col+1)+grayed.item(row,col+2))
        Gy = grayed.item(row,col+2)+2*grayed.item(row+1,col+2)+grayed.item(row+2,col+1)-(grayed.item(row,col)+2*grayed.item(row+1,col)+grayed.item(row+2,col))
        grad = math.sqrt(Gx**2 + Gy**2)
        grayed.itemset((row, col), grad)
cv2.imshow('frame', grayed)
if cv2.waitKey(1) & 0xFF == ord('q'):
    break

提前谢谢！你知道吗

Answer 1

我分析了你的代码：

您将应用两个渐变过滤器，一个用于方向x，另一个用于y。你知道吗

这些过滤器看起来像：

-1 -2 -1
 0  0  0
 1  3  0

以及

-1 0 1
-2 0 2
-1 1 0

我猜这些是打字错误（？）你很想拥有这些：

Gx：

-1 -2 -1
 0  0  0
 1  2  1

对于Gy

-1 0 1
-2 0 2
-1 0 1

这个过滤过程也称为convolution。事实上，由于内核也是2d的，所以运行时是O(4)。网上有很多资源，比如in this answer

通过使用convolution的概念，您确实可以改进理论运行时。例如，如果使用FFT，运行时可以降到O(n^2*log^2(n))。你知道吗

但是，通过使用scipy - ^{}或opencv - ^{}的过滤方法，可以获得更多的性能提升。 它们将有一个非常好的运行时，而且可能更重要的是，它们是用C实现的，不会像使用python循环时那样显著地减慢速度。你知道吗