如何改进这个算法？(图像处理)

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。实际上，您有一个O(4)运行时，因为内核也是2d。网络上有很多资源，比如在这个答案中

通过使用卷积的概念，您确实可以改进理论运行时。例如，如果使用快速傅立叶变换，运行时可以降到O(n^2*log^2(n))。

但是，使用convolve或filter2D的过滤方法可以提高性能。它们将有一个非常好的运行时，而且可能更重要的是，它们是用C实现的，并且不会像使用python循环时那样显着地减慢速度。