このアルゴリズムを改善するにはどうすればよいですか？ （画像処理）

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

私はあなたのコードを分析した：

次の2つのグラデーションフィルター、方向xに1つ、yのための1つを適用しています。

これらのフィルタは次のようになります。

-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

の概念を使って理論的なランタイムを改善することができます。例えば、FFTを使用する場合、ランタイムはO(n^2*log^2(n))に下げることができます。

ただし、フィルタ方法をscipy - convolveまたはopencv - filter2Dにすると、パフォーマンスが大幅に向上します。 これらは非常に優れたランタイムを持ち、さらに重要なことに、C言語で実装されており、Pythonループを使用したときほど劇的に減速しません。