OpenCV Leistung auf template-matching

Ich versuche zu tun, template-matching grundsätzlich auf java. Ich verwendete einfache Algorithmus zu finden, übereinstimmen. Hier ist der code:

minSAD = VALUE_MAX;
//loop through the search image
for ( int x = 0; x <= S_rows - T_rows; x++ ) {
    for ( int y = 0; y <= S_cols - T_cols; y++ ) {
        SAD = 0.0;

        //loop through the template image
        for ( int i = 0; i < T_rows; i++ )
            for ( int j = 0; j < T_cols; j++ ) {

                pixel p_SearchIMG = S[x+i][y+j];

                pixel p_TemplateIMG = T[i][j];

                SAD += abs( p_SearchIMG.Grey - p_TemplateIMG.Grey );
            }
    }

    //save the best found position 
    if ( minSAD > SAD ) {
        minSAD = SAD;
        //give me VALUE_MAX
        position.bestRow = x;
        position.bestCol = y;
        position.bestSAD = SAD;
    }
}

Dieser ist aber sehr langsam Vorgehen. Getestet habe ich 2 Bilder (768 × 1280) und das subimage (384 x 640). Das dauert Ewigkeiten.
Tut openCV durchführen template-matching viel schneller oder nicht mit ready-Funktion cvMatchTemplate()?

InformationsquelleAutor AraZZ | 2011-08-21

  1. 38

    Finden Sie openCV cvMatchTemplate() ist viel Brei schneller als die Methode, die Sie umgesetzt haben. Was Sie geschaffen haben, ist eine statistische template-matching-Methode. Es ist die häufigste und am einfachsten zu implementieren, ist jedoch sehr langsam bei großen Bildern. Werfen wir einen Blick auf die grundlegende Mathematik Sie haben ein Bild, das 768x1280 Sie eine Schleife durch jedes dieser Pixel minus der Kante, als du das template limits (768 - 384) x (1280 - 640) , 384 x 640 = 245'760 Operationen, in denen Sie eine Schleife durch jedes pixel der Vorlage (einem anderen 245'760-Operationen), daher, bevor Sie irgendwelche Mathe-Ihre Schleife, die Sie bereits haben (245'760 x 245'760) 60'397'977'600 Operationen. Über 60 Milliarden Operationen nur eine Schleife über dein Bild, Es ist mehr erstaunlich, wie schnell die Maschinen dies tun können.

    Erinnern, aber die 245'760 x (245'760 x Mathematik-Operationen), so gibt es viele weitere Operationen.

    Nun cvMatchTemplate() tatsächlich verwendet die Fourier-Analyse Template-matching-Vorgang. Dies funktioniert durch die Anwendung einer Schnellen Fourier-Transformation (FFT) auf dem Bild, in dem die Signale der pixel änderungen in der Intensität, sind segmentiert sich in jedem der entsprechenden Wellenformen. Die Methode ist schwer zu erklären, gut, aber das Bild wird umgewandelt in ein signal, Darstellung der komplexen zahlen. Wenn Sie verstehen möchten, mehr bitte Suche bei goggle für die fast-fourier-Transformation. Nun der gleiche Vorgang wird ausgeführt, auf die Vorlage der Signale, die form der Vorlage verwendet werden, um herauszufiltern, alle anderen Signale aus dem Bild.

    In einfachen, es unterdrückt alle features im Bild, die nicht über die gleichen Funktionen wie Ihre Vorlage. Das Bild wird dann umgewandelt zurück mit einer inversen fast-fourier-Transformation zur Erstellung einer Bilder wo hohe Werte bedeuten eine übereinstimmung und niedrige Werte bedeuten das Gegenteil. Dieses Bild wird oft normiert, so dass 1 repräsentieren, eine übereinstimmung und 0 ist, oder gibt es etwa bedeuten, das Objekt ist nicht, wo in der Nähe.

    Aber sei gewarnt: wenn Sie das Objekt nicht in das Bild und es wird normalisiert fehldetektionen auftreten, da der höchste Wert berechnet werden als übereinstimmung behandelt. Ich könnte noch Ewigkeiten darüber, wie die Methode funktioniert und seine Vorteile oder Probleme, die auftreten können, aber...

    Der Grund für diese Methode ist, so schnell ist: 1) opencv ist hoch optimierten c++ - code. 2) Die fft-Funktion ist einfach und schnell für Ihren Prozessor zu handhaben, da ein Großteil hat die Fähigkeit zum ausführen dieser operation in hardware. GPU-Grafikkarten entwickelt, um Millionen von fft-Operationen pro Sekunde, da diese Berechnungen sind genau so wichtig im high-performance-gaming-Grafiken oder video-encoding. 3) Die Anzahl der Operationen, die erforderlich ist, weit weniger.

    Im sommerlichen statistische template-matching-Methode ist langsam und dauert eine Ewigkeit, in der Erwägung, dass opencv FFT oder cvMatchTemplate() ist schnell und hoch optimiert.

    Statistische template-matching wird nicht Fehler produzieren, wenn ein Objekt nicht gibt, in der Erwägung, dass opencv-FFT können, es sei denn, Sorgfalt bei seiner Anwendung.

    Ich hoffe, das gibt Ihnen ein grundlegendes Verständnis und beantwortet deine Frage.

    Cheers

    Chris

    [BEARBEITEN]

    Weiter und beantworten Ihre Fragen:

    Hallo,

    cvMatchTemplate kann die Arbeit mit CCOEFF_NORMED und CCORR_NORMED und SQDIFF_NORMED einschließlich der nicht-normalisierten version dieser. Hier zeigt die Art von Ergebnissen Sie erwarten können, und gibt Ihr den code, um mit zu spielen.

    http://dasl.mem.drexel.edu/~noahKuntz/openCVTut6.html#Schritt%202

    Den drei Methoden sind gut zitiert werden und viele Artikel sind verfügbar über Google scholar. Ich habe ein paar Papiere unten. Jeder verwendet einfach eine andere Gleichung zu finden, die Korrelation zwischen den FFT-Signale, die form der Vorlage und die FFT-Signale, die vorhanden sind in dem Bild der Korrelationskoeffizient neigt dazu, bringen bessere Ergebnisse in meiner Erfahrung und ist leichter zu finden, Verweise auf. Summe der Quadrierten Differenz ist eine weitere Methode, die verwendet werden können, mit vergleichbaren Ergebnissen. Ich hoffe, einige der diese Hilfe:

    Schnell normalisierte Kreuz-Korrelation für die Fehlererkennung
    Du-Ming Tsai; Chien-Ta-Lin;
    Pattern Recognition Letters
    Band 24, Ausgabe 15, November 2003, Seiten 2625-2631

    Template-Matching mit Schnellen Normierte Kreuz-Korrelation
    Kai Briechle; Uwe D. In Denen Sich Hanebecks;

    Die Relative Leistung der zwei-dimensionalen speckle-tracking-Techniken: normierte Korrelation, nicht-normalisierten Korrelation und die Summe-absoluter-Unterschied
    Friemel, B. H.; Bohs, L. N.; Trahey, G. E.;
    Ultrasonics Symposium, 1995. Proceedings., 1995 IEEE

    Eine Klasse von Algorithmen für Schnelle Digitale Bild-Registrierung
    Barnea, Daniel I.; Silverman, Harvey F.;

    Computer, IEEE Transactions on Feb. 1972

    Ist es oft bevorzugt, um die Verwendung der normalisierten version von diese Methoden, wie alles, das gleich 1 ist ein Spiel jedoch, wenn kein Objekt vorhanden ist, die Sie bekommen können falsch positive Ergebnisse. Die Methode funktioniert schnell, einfach aufgrund der Art und Weise es wird angeregt, in der computer-Sprache. Die beteiligten Betriebe sind ideal für die Prozessor-Architektur, was bedeutet, es kann führen Sie jeden Vorgang mit ein paar Taktzyklen anstatt die Verlagerung von Speicher-und information um und über mehrere Taktzyklen. Prozessoren der Lösung des FFT-Probleme seit vielen Jahren kennen und wie ich sagte, es ist die eingebaute hardware zu tun. Hardware-Basis ist immer schneller als die software-und die statistische Methode des template-matching ist in der Basis-software basiert. Gute Lektüre für die hardware finden Sie hier:

    Digital-signal-Prozessor
    Obwohl eine Wiki-Seite die Referenzen sind einen Blick Wert, eine effektiv diesem ist der hardware führt, dass die FFT-Berechnungen

    Einen neuen Ansatz für die Pipeline-FFT-Prozessor
    Shousheng Er, Matten Torkelson;
    Ein Favorit von mir, da es zeigt, was passiert im Prozessor

    Eine Effiziente Lokal Pipeline-FFT-Prozessor
    Liang Yang; Kewei Zhang; Liu Hongxia; Jin, Huang; Shitan Huang;

    Diese Papiere wirklich zu zeigen, wie Komplex die FFT ist bei der Umsetzung jedoch der Rohr-Auskleidung der Prozess ermöglicht die operation durchgeführt werden, in ein paar Taktzyklen. Dies ist der Grund, Echtzeit-vision-Systeme nutzen FPGA (insbesondere Prozessoren, können Sie das design zur Umsetzung einer gestellten Aufgabe) wie können Sie die design extrem parallelen in der Architektur-und Rohr-Futter ist einfacher zu implementieren.

    Obwohl ich erwähnen muss, dass für die FFT eines Bildes, das Sie eigentlich mit FFT2, die die FFT-Analyse der horizontalen Ebene und der FFT-Analyse der vertikalen Ebene, nur damit es keine Verwirrung gibt, wenn Sie finden Verweis auf. Ich kann nicht sagen, dass ich ein Experte zu wissen, wie die Gleichungen umgesetzt und die FFT implementiert ist, habe ich versucht zu finden, gute guides noch die Suche nach einer guten Anleitung ist sehr hart, so viel habe ich noch nicht gefunden (Nicht das ich verstehen kann, zumindest). Eines Tages, ich kann Sie verstehen, aber weiß, dass ich ein gutes Verständnis von, wie Sie arbeiten und die Art der Ergebnisse, die erwartet werden kann.

    Anderen als dieses kann ich nicht wirklich helfen, Sie mehr, wenn Sie wollen, um Ihre eigene version oder verstehen, wie es funktioniert, dann ist es an der Zeit, zu der Bibliothek, aber ich warne Sie die opencv-code ist so gut optimiert, Sie werden kämpfen, um seine Leistung zu steigern aber wer weiß, Sie können herausfinden, einen Weg, um zu erhalten bessere Ergebnisse, alles gute und viel Glück

    Chris

    Ausgezeichnete Antwort, Chris. Vielen Dank!
    Ausgezeichnete Antwort, Chris. Vielen Dank! Ich zum ersten mal hören (FFT). In meinem Programm verwende ich cvMatchTemplate() und geworden davon überzeugt, über seine Leistung. Ich nehme an, diese Methode ist über die normierte Kreuz-Korrelation. Nach der Lektüre mehrere Artikel fand ich diese Formel=CV_TM_CCORR_NORMED: R(x,y)=sumx',y'[T(x',y')•I(x+x',y+y')]/sqrt[sumx',y 'T(x',y') - 2•sumx',y 'I(x+x',y+y')2] Tatsächlich auch hier 4 Variablen und 4 Schleifen, Denke ich. Wie es schnell wirkt? Wissen Sie etwas über diesen Zusammenhang? Ich werde froh sein, Wenn Sie Lob für Ihre Antwort.
    Hi Arazz ich habe aktualisiert die Frage mit, was Sie anzubieten oder zumindest das, was ich beantworten könnte, ich hoffe es hilft.
    Hallo Chris. Haben Sie gute Materialien darüber, wie FFT erhöht die Rechengeschwindigkeit des cvMatchTemplate. Sie haben das folgende geschrieben "Jetzt cvMatchTemplate() tatsächlich verwendet die Fourier-Analysis Template matching-operation". Also, ich bin versuchen zu finden, jede Bezugnahme auf den Satz. Leider fand ich nur die Formeln zur Berechnung von NCC. Aber, keine Verwendung von FFT in der cvMatchTemplate(). Können Sie eine Referenz? Es wäre auch sehr hilfreich. Danke im Voraus
    Oh, danke Chris, fand ich Verweis jetzt einfach. Das Hotel liegt an der OpenCV-Referenz-Handbuch. auf dft-Funktion. danke

    InformationsquelleAutor Chris

Schreibe einen Kommentar