So verbessern Sie die Effizienz eines Sobel Kantendetektors

Question

Ich schreibe ein computer vision library von Grund auf in Python mit einer rpi Kamera zu arbeiten. Im Moment habe ich die Konvertierung in greyscale und einige andere grundlegende img Operationen, die beide relativ schnell laufen auf meiner model Brpi3 implementiert.

Allerdings ist meine Kantendetektion mit dem Operator sobel (wikipedia description) viel langsamer als die anderen Funktionen, obwohl es funktioniert. Hier ist sie:

def sobel(img): 
    xKernel = np.array([[-1,0,1],[-2,0,2],[-1,0,1]]) 
    yKernel = np.array([[-1,-2,-1],[0,0,0],[1,2,1]]) 
    sobelled = np.zeros((img.shape[0]-2, img.shape[1]-2, 3), dtype="uint8") 
    for y in range(1, img.shape[0]-1): 
     for x in range(1, img.shape[1]-1): 
      gx = np.sum(np.multiply(img[y-1:y+2, x-1:x+2], xKernel)) 
      gy = np.sum(np.multiply(img[y-1:y+2, x-1:x+2], yKernel)) 
      g = abs(gx) + abs(gy) #math.sqrt(gx ** 2 + gy ** 2) (Slower) 
      g = g if g > 0 and g < 255 else (0 if g < 0 else 255) 
      sobelled[y-1][x-2] = g 
    return sobelled 

und es mit diesem greyscale Bild einer Katze läuft:

ich diese Antwort erhalten, die richtig scheint:

Die Anwendung der Bibliothek, und diese Funktion ist insbesondere auf einem Schachspielroboter, in dem die Kante erkennt Ion wird helfen, den Ort der Stücke zu erkennen. Das Problem ist, dass es >15 Sekunden dauert, um zu laufen, was ein signifikantes Problem ist, da es zu der Zeit hinzufügen wird, die der Roboter braucht, um sich viel zu bewegen.

Meine Frage ist: Wie kann ich es beschleunigen?

Bisher habe ich ein paar Dinge ausprobiert:

1. Statt squaring dann adding, dann square rooting die gx und gy Werte die Gesamt Steigung zu bekommen, ich habe gerade sum die absolute Werte. Dies verbesserte die Geschwindigkeit um einen ordentlichen Betrag.

2. Mit einem niedrigeren resolution Bild von der rpi Kamera. Dies ist natürlich ein einfacher Weg, um diese Operationen schneller zu machen, aber es ist nicht wirklich so brauchbar, da es immer noch ziemlich langsam bei der minimal nutzbaren Auflösung von 480x360 ist, die massiv von der Kamera max 3280x2464 reduziert ist.

3. Schreiben verschachtelte for-Schleifen, um die anstelle der np.sum(np.multiply(...)) zu tun. Dies endete leicht langsamer, die ich als von np.multiply überrascht, da ein neues Array zurückgibt, dachte ich, dass es schneller sein sollte, es mit loops zu tun. Ich denke jedoch, dass dies aufgrund der Tatsache sein kann, dass numpy meist in C geschrieben wird oder dass das neue Array nicht wirklich gespeichert wird, so dauert es nicht lange, aber ich bin mir nicht sicher.

Jede Hilfe wäre sehr geschätzt - ich glaube, die Hauptsache für Verbesserung Punkt ist 3, das heißt die matrix Multiplikation und Summierung.

Answer 1

Obwohl Sie Ihre eigene Bibliothek aufbauen, sollten Sie wirklich Bibliotheken für Convolution verwenden, sie werden die resultierenden Operationen in C oder Fortran im Backend durchführen, was viel, viel schneller sein wird.

Aber, wenn Sie möchten, verwenden Sie lineare separierbare Filter. Hier ist die Idee:

Image:

1 2 3 4 5 
2 3 4 5 1 
3 4 5 1 2 

Sobel x kernel:

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

Ergebnis:

8, 3, -7 

An der ersten Position der Faltung, werden Sie werden Rechen 9 Werte. Erstens, warum? Sie werden nie die mittlere Spalte hinzufügen, nicht die Mühe, es zu multiplizieren. Aber das ist nicht der Punkt linear trennbarer Filter. Die Idee ist einfach. Wenn Sie den Kernel an der ersten Position platzieren, multiplizieren Sie die dritte Spalte mit [1, 2, 1]. Aber zwei Schritte später multiplizieren Sie die dritte Spalte mit [-1, -2, -1]. Was für eine Verschwendung! Sie haben das bereits berechnet, Sie müssen es jetzt einfach negieren. Und das ist die Idee mit einem linearen trennbaren Filter. Beachten Sie, dass Sie den Filter in eine Matrix äußere Produkt zweier Vektoren brechen kann:

[1] 
[2] * [-1, 0, 1] 
[1] 

Unter dem äußeren Produkt hier ergibt sich die gleiche Matrix. Die Idee besteht also darin, die Operation in zwei Teile aufzuteilen. Zuerst multipliziere das ganze Bild mit dem Zeilenvektor, dann dem Spaltenvektor. Unter dem Zeilenvektor

-1 0 1 

über das Bild, wir am Ende mit

2 2 2 
2 2 -3 
2 -3 -3 

Und dann dem Bestehen des Spaltenvektor durch multipliziert und summiert werden, bekommen wir wieder

8, 3, -7 

One andere raffinierte Tricks, die hilfreich sein können oder auch nicht (hängt von Ihren Kompromissen zwischen Speicher und Effizienz ab):

Beachten Sie, dass Sie bei der einreihigen Multiplikation den mittleren Wert ignorieren und nur die rechten von den linken Werten subtrahieren. Dies bedeutet, dass effektiv, was Sie tun, ist, diese beiden Bilder subtrahieren:

3 4 5  1 2 3 
4 5 1 - 2 3 4 
5 1 2  3 4 5 

Wenn Sie die ersten beiden Spalten von Ihrem Bild schneiden Sie die linke Matrix erhalten, und wenn Sie schneiden Sie die letzten beiden Spalten, Sie weg Holen Sie sich die richtige Matrix. So können Sie einfach berechnen, diesen ersten Teil der Faltung einfach als

result_h = img[:,2:] - img[:,:-2] 

und dann können Sie eine Schleife durch für die verbleibende Spalte des Sobel-Operator. Oder Sie können sogar weitermachen und dasselbe tun, was wir gerade getan haben. Diesmal müssen Sie für den vertikalen Fall nur die erste und dritte Zeile und zweimal die zweite Zeile hinzufügen. oder, mit numpy addition:

result_v = result_h[:-2] + result_h[2:] + 2*result_h[1:-1] 

Und du bist fertig! Ich werde hier in naher Zukunft einige Zeitpunkte hinzufügen. Für einige Rückseite des Umschlags Berechnungen (d eilten Jupyter Notebook-Timings auf einem 1000x1000 Bild):

neue Methode (Summen der Bilder): 8,18 ms ± 399 & mgr; s pro Schleife (Mittelwert ± STD dev..von 7 läuft, 100 Schleifen jeweils)

alte Methode (double for-Schleife): 7,32 s ± 207 ms pro Schleife (Mittelwert ± STD dev von 7 verläuft, 1-Schleife jeweils)

Ja.. Du hast das richtig gelesen: 1000x Beschleunigung.

---

Hier einige Code die beiden zu vergleichen:

import numpy as np 

def sobel_x_orig(img): 
    xKernel = np.array([[-1,0,1],[-2,0,2],[-1,0,1]]) 
    sobelled = np.zeros((img.shape[0]-2, img.shape[1]-2)) 
    for y in range(1, img.shape[0]-1): 
     for x in range(1, img.shape[1]-1): 
      sobelled[y-1, x-1] = np.sum(np.multiply(img[y-1:y+2, x-1:x+2], xKernel)) 
    return sobelled 

def sobel_x_new(img): 
    result_h = img[:,2:] - img[:,:-2] 
    result_v = result_h[:-2] + result_h[2:] + 2*result_h[1:-1] 
    return result_v 

img = np.random.rand(1000, 1000) 
sobel_new = sobel_x_new(img) 
sobel_orig = sobel_x_orig(img) 

assert (np.abs(sobel_new-sobel_orig) < 1e-12).all() 

Natürlich 1e-12 ist einige ernsthafte Toleranz, aber das ist pro Element so sollte es in Ordnung sein. Aber ich habe auch ein float Bild, Sie werden natürlich größere Unterschiede für uint8 Bilder haben.

Beachten Sie, dass Sie dies für jeden linearen trennbaren Filter tun können! Dazu gehören Gaußsche Filter. Beachten Sie auch, dass dies im Allgemeinen eine Menge Operationen erfordert. In C oder Fortran oder was auch immer, wird es normalerweise nur als zwei Faltungen der einzelnen Zeilen/Spalten-Vektoren implementiert, weil es am Ende sowieso jedes Element jeder Matrix durchlaufen muss; ob du sie einfach hinzufügst oder multiplizierst, also ist es in C nicht schneller, es auf diese Weise zu tun, wenn du die Bildwerte hinzufügst, als wenn du nur die Faltungen machst. Aber das Durchschleifen von numpy Arrays ist sehr langsam, daher ist diese Methode in Python viel schneller.