Ich würde gerne eine Variable Blockgröße Summe der absoluten Differenz Berechnung mit einem 2-D-Array von 16 Bit durchführen Ganzzahlen in einem C ++ Programm so effizient wie möglich. Ich bin an einem Echtzeit-Block-Matching-Code interessiert. Ich habe mich gefragt, ob es dafür Softwarebibliotheken gibt? Der Code läuft unter Windows XP, und ich verwende Visual Studio 2010, um das Kompilieren durchzuführen. Die CPU ist ein 2-Kern AMD Athlon 64 x2 4850e.
Mit der Summe der Summe der absoluten Differenz (SAD) der Variablen Blockgröße meine ich Folgendes:
Ich habe ein kleineres 2-D-Array, das ich das template_grid nennen werde, und ein größeres 2-D-Array, das ich das image nennen werde. Ich möchte die Region im Bild finden, die die Summe der absoluten Differenz zwischen den Pixeln in der Vorlage und den Pixeln in der Region im Bild minimiert.
Die einfachste Methode zur Berechnung der SAD in C ++ wäre wie folgt:
%Vor%Die SAD-Berechnung für bestimmte Array-Größen wurde in der Intel-Bibliothek für Leistungselemente optimiert. Die Arrays, mit denen ich arbeite, passen jedoch nicht zu den Größen in diesen Bibliotheken.
Es gibt zwei Suchbereiche, mit denen ich arbeite,
ein großer Bereich: Bereich Y = 45, Bereich X = 10
ein kleiner Bereich: Bereich Y = 4, Bereich X = 2
Es gibt nur eine Vorlagengröße und es ist: lenTemplateY = 61, lenTemplateX = 7
Kleinere Optimierung:
%Vor%Kann eine verrückte Idee für Ihre Konfiguration sein (C ++ - Compiler macht mir Sorgen), aber es kann funktionieren. Ich biete keine Garantien, aber versuchen Sie es.
Die Idee funktioniert vielleicht, weil Ihre template_grid Größen und die Bereiche konstant sind - also zum Zeitpunkt der Kompilierung bekannt sind.
Damit dies auch funktioniert, müssen Ihre image und template_grid mit demselben Layout organisiert sein (Spalte zuerst oder Zeile zuerst) - die Art, wie Ihr "Beispielcode" in der Frage dargestellt wird, mischt die SAD x/y mit template_grid y/x .
Im Folgenden nehme ich eine "Spalte zuerst" -Organisation an, so dass SAD[ix] die ix th -Spalte Ihrer SAD** -Matrix bezeichnet. Der Code geht für "row first" genauso, nur dass der Name der Variablen nicht mit der Bedeutung der Array-Werte übereinstimmt.
Also, fangen wir an:
%Vor% Warum ein Funktor struct - struct mit Operator? Das C ++ erlaubt keine partielle Spezialisierung von Funktionsvorlagen .
Was der sad1D_simple tut: entrollt einen for -Zyklus, der die SAD von zwei Arrays in der Eingabe ohne jegliche Verrechnung berechnet, basierend auf der Tatsache, dass die Länge Ihres template_grid -Arrays eine zur Kompilierungszeit bekannte Konstante ist. Es ist in der gleichen Weise wie "Berechnung der Fakultät der Kompilierzeit mit C ++ Vorlagen"
Wie hilft das?
Anwendungsbeispiel im folgenden Code:
Mmmm ... können wir es besser machen? Nein, es wird nicht das Abrollen der X-Achse sein, wir wollen immer noch im 1D-Bereich bleiben, aber ... nun, vielleicht, wenn wir ein entferntes sad1D erstellen und eine weitere Schleife auf derselben Achse abrollen?
Es funktioniert wenn f auch rangeX ist konstant.
Und so verwenden Sie es:
%Vor%Ja ... aber die Frage ist: wird das die Leistung verbessern? ? Zum Teufel, wenn ich es weiß. Für eine kleine Anzahl von Schleifen innerhalb eines Zyklus und für eine starke Datenlokalität (Werte, die so nahe beieinander liegen, dass sie sich in den CPU-Caches befinden), sollte Schleifenabwickeln die Leistung verbessern. Bei einer größeren Anzahl von Schleifen können Sie die CPU-Verzweigungsvorhersage und andere Hokuspokus-I-Know-Mai-Impact-Performance-aber-Ich-nicht-Know-how negativ beeinflussen.
Gefühl von Mut: Selbst wenn die gleiche Abwicklungsmethode für die anderen beiden Schleifen funktioniert, kann die Verwendung dieser Funktion zu einer Leistungsminderung führen: Wir müssen von einem zusammenhängenden Vektor (eine image -Spalte) zu springen der andere - das gesamte Bild passt möglicherweise nicht in den CPU-Cache.
Hinweis: Wenn Ihre template_grid -Daten ebenfalls konstant sind (oder Sie haben eine endliche Menge von konstanten Vorlagenrastern), können Sie einen Schritt weiter gehen und Strukturfunktoren mit dedizierten Masken erstellen. Aber mir geht es heute nicht gut.
Sie können es mit dem OpenCV-Template-Matching mit dem Square-Difference-Parameter versuchen, siehe Tutorial hier . OpenCV ist mit OpenCL optimiert, aber ich kenne diese spezielle Funktion nicht. Ich denke, du solltest es versuchen.
Ich bin mir nicht sicher, wie sehr Sie auf die Verwendung von SAD beschränkt sind oder ob Sie generell daran interessiert sind, die Region in dem Bild zu finden, die der Vorlage am besten entspricht. Im letzten Fall können Sie eine Faltung anstelle von SAD verwenden. Dies kann in der Fourier-Domäne in O (N log N) gelöst werden, einschließlich der Fourier-Transformation (FFT).
Kurz gesagt, können Sie die FFT (z. B. mit Ссылка ) verwenden, um sowohl die Vorlage als auch das Bild in die Frequenzdomäne zu konvertieren , dann multiplizieren Sie sie und konvertieren Sie zurück in die Zeitdomäne.
Das ist natürlich alles egal, wenn Sie SAD verwenden müssen.
Tags und Links algorithm c++ computer-vision