Eine Beschleunigung Selbstähnlichkeit in einem Bild

Question

Ich schreibe ein Programm, das Bild generieren. Eine Messung, die ich will, ist die Menge der „Selbstähnlichkeit“ im Bild. Ich schrieb den folgenden Code, der für jede Sizewindow für die countBest-ten besten Matches sieht * Sizewindow-Fenster in dem Bild:

double Pattern::selfSimilar(int sizeWindow, int countBest) {
    std::vector<int> *pvecount;

    double similarity;
    int match;
    int x1;
    int x2;
    int xWindow;
    int y1;
    int y2;
    int yWindow;

    similarity = 0.0;

    // (x1, y1) is the original that's looking for matches.

    for (x1 = 0; x1 < k_maxX - sizeWindow; x1++) {
        for (y1 = 0; y1 < k_maxY - sizeWindow; y1++) {
             pvecount = new std::vector<int>();

             // (x2, y2) is the possible match.
             for (x2 = 0; x2 < k_maxX - sizeWindow; x2++) {
                 for (y2 = 0; y2 < k_maxY - sizeWindow; y2++) {
                     // Testing... 
                     match = 0;

                     for (xWindow = 0; xWindow < sizeWindow; xWindow++) {
                         for (yWindow = 0; yWindow < sizeWindow; yWindow++) {
                             if (m_color[x1 + xWindow][y1 + yWindow] == m_color[x2 + xWindow][y2 + yWindow]) {
                                 match++;
                             }
                         }
                     }

                     pvecount->push_back(match);
                 }
             }

             nth_element(pvecount->begin(), pvecount->end()-countBest, pvecount->end());

             similarity += (1.0 / ((k_maxX - sizeWindow) * (k_maxY - sizeWindow))) *
                 (*(pvecount->end()-countBest) / (double) (sizeWindow * sizeWindow));

             delete pvecount;
        }
    }

    return similarity;
}

Die gute Nachricht ist, dass der Algorithmus tut, was ich will, es zu: es wird einen Wert von 0,0 bis 1,0 um zurückzukehren, wie ‚selbstähnlich‘ ist ein Bild

.

Die schlechte Nachricht - wie ich sicher bin, dass Sie bereits bemerkt - ist, dass der Algorithmus extrem langsam ist. Es dauert (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * sizeWindow * sizeWindow Schritte für einen Lauf.

Einige typische Werte für die Variablen:

k_maxX = 1280
k_maxY = 1024
sizeWindow = between 5 and 25
countBest = 3, 4, or 5
m_color[x][y] is defined as short m_color[k_maxX][k_maxY] with values between 0 and 3 (but may increase in the future.)

Im Moment bin ich nicht Sorgen um den Speicherbedarf von pvecount genommen. Später kann ich eine sortierte Datensatz verwenden, der nicht ein weiteres Element hinzufügt, wenn es kleiner als countBest. Ich bin nur besorgt über Algorithmus Geschwindigkeit.

Wie kann ich das beschleunigen?

Answer 1

Ihr Problem erinnert mich stark an den Berechnungen, die für Bewegung getan werden müssen in Videokompression. Vielleicht sollten Sie einen genaueren Blick, was in diesem Bereich getan hat.

Wie rlbond bereits darauf hingewiesen, die Anzahl der Punkte in einem Fenster zu zählen, wo die Farben genau ist keine Übereinstimmung, was normalerweise in dem Vergleich Bilder gemacht. Eine konzeptionell einfachere Methode als diskreten Cosinus oder Wavelet-Transformationen ist die Quadrate der Differenzen

hinzufügen

diff = (m_color[x1 + xWindow][y1 + yWindow] - m_color[x2 + xWindow][y2 + yWindow]);
sum += diff*diff;

und verwendet Summe statt Spiel als Kriterium für die Ähnlichkeit (jetzt kleinere Mittel besser).

Zurück zu dem, was Sie wirklich gefragt: Ich denke, es möglich ist, die Laufzeit um den Faktor 2 / Sizewindow (vielleicht zum Quadrat?) Zu reduzieren, aber es ist ein wenig chaotisch. Es basiert auf der Tatsache, dass bestimmte Paare von Quadraten Sie fast vergleichen bleiben die gleichen, wenn y1 um 1 erhöht wird Wenn die Offsets xAus = x2-x1 und YOFF = y2-y1 sind die gleichen, nur die obere (rsp. Unten) vertikale Streifen die Quadrate nicht mehr (rsp. jetzt jedoch nicht vor) abgestimmt. Wenn Sie die Werte halten berechnen Sie für Spiel in einer zweidimensionalen Anordnung durch die Offsets indiziert xAus = x2-x1 und YOFF = y2-y1, dann können Sie den neuen Wert für Spiel [xAus] [YOFF] für y1 um 1 erhöht berechnen und x1 das gleiche von 2 * Sizewindow Vergleiche zu bleiben:

for (int x = x1; x < x1 + sizeWindow; x++) {
    if (m_color[x][y1] == m_color[x + xOff][y1 + yOff]) {
        match[xOff][yOff]--; // top stripes no longer compared
    }

    if (m_color[x][y1+sizeWindow] == m_color[x + xOff][y1 + sizeWindow + yOff]) {
        match[xOff][yOff]++; // bottom stripe compared not, but wasn't before
    }
}

(wie die möglichen Werte für Yoff geändert - durch y1 Inkrementieren - aus dem Intervall [y2 - y1, k_maxY - Sizewindow - y1 - 1] auf das Intervall [y2 - y1 - 1, k_maxY - Sizewindow - y1 - 2] Sizewindow - - y1 - 1 und müssen die Spiele mit dem zweiten Index berechnet YOFF = y2 - y1 - 1 unterschiedlich) können Sie die Spiele mit dem zweiten Index YOFF = k_maxY verwerfen. Vielleicht können Sie auch die Werte von halten, wie viel Sie erhöhen / verringern Spiel [] [], während die Schleife in einem Array einen weiteren 2 / Sizewindow Speed-up zu erhalten.

Answer 2

Ok, zunächst ist dieser Ansatz überhaupt nicht stabil. Wenn Sie zufälliges Rauschen zu Ihrem Bild hinzufügen, wird es erheblich die Ähnlichkeit zwischen den beiden Bildern verringern. Noch wichtiger ist, von einer Bildverarbeitungs Sicht ist es nicht effizient oder besonders gut. Ich schlage vor, einen anderen Ansatz; zum Beispiel unter Verwendung einer Wavelet-basierten Ansatz. Wenn Sie einen 2D-DWT auf dem Bild für ein paar Stufen durchgeführt und verglichen die Skalierungskoeffizienten, würden Sie wahrscheinlich bessere Ergebnisse. Außerdem wird die diskrete Wavelet-O (n).

Der Nachteil ist, dass Wavelets ein erweiterte mathematisches Thema ist. Es gibt einige gute Opencourseware Hinweise auf Wavelets und Filterbänke hier .