Accelerare l'auto-somiglianza in un'immagine

Question

Sto scrivendo un programma che genererà immagini. Una misura che desidero è la quantità di "auto-somiglianza" nell'immagine. Ho scritto il seguente codice che cerca le migliori corrispondenze countBest-th per ogni finestra Window * sizeWindow nell'immagine:

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;
}

La buona notizia è che l'algoritmo fa quello che voglio: restituirà un valore da 0,0 a 1,0 su quanto sia "auto-simile" un'immagine.

La cattiva notizia - come sono sicuro che hai già notato - è che l'algoritmo è estremamente lento. Sono necessari i passaggi (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * sizeWindow * sizeWindow per una corsa.

Alcuni valori tipici per le variabili:

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.)

In questo momento, non sono non preoccupato per l'impronta di memoria presa da pvecount. Successivamente, posso utilizzare un set di dati ordinati che non aggiunge un altro elemento quando è più piccolo di countBest. Sono solo preoccupato per la velocità dell'algoritmo.

Come posso accelerarlo?

Answer 1

Il tuo problema mi ricorda fortemente i calcoli che devono essere fatti per compensazione del movimento nella compressione video. Forse dovresti dare un'occhiata più da vicino a ciò che è stato fatto in quella zona.

Come già sottolineato da rlbond, il conteggio del numero di punti in una finestra in cui i colori corrispondono esattamente non è quello che si fa normalmente nel confrontare le immagini. Un metodo concettualmente più semplice rispetto all'utilizzo di trasformazioni discrete di coseno o wavelet è quello di aggiungere i quadrati delle differenze

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

e usa somma invece di trova come criterio di somiglianza (ora più piccolo significa meglio).

Tornando a ciò che hai veramente chiesto: penso che sia possibile ridurre il tempo di esecuzione del fattore 2 / sizeWindow (forse al quadrato?), ma è un po 'disordinato. Si basa sul fatto che alcune coppie di quadrati confrontate rimangono quasi le stesse quando si incrementa y1 di 1. Se gli offset xOff = x2-x1 e yOff = y2-y1 sono uguali, solo le strisce verticali superiori (rsp. In basso) dei quadrati non sono più (rsp. ora, ma non prima) abbinati. Se si mantengono i valori calcolati per la corrispondenza in un array bidimensionale indicizzato dagli offset xOff = x2-x1 e yOff = y2-y1, è possibile calcolare il nuovo valore per la corrispondenza [xOff] [yOff] per y1 aumentato di 1 e x1 restano uguali per 2 * dimensioni Confronti di Windows:

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
    }
}

(poiché i possibili valori di yOff sono cambiati - aumentando y1 - dall'intervallo [y2 - y1, k_maxY - sizeWindow - y1 - 1] all'intervallo [y2 - y1 - 1, k_maxY - sizeWindow - y1 - 2] puoi scartare le partite con il secondo indice yOff = k_maxY - sizeWindow - y1 - 1 e devi calcolare le partite con il secondo indice yOff = y2 - y1 - 1 in modo diverso). Forse puoi anche mantenere i valori di quanto aumenti / diminuisci match [] [] durante il loop in un array per ottenere un altro 2 / sizeWindow speed-up.

Answer 2

Ok, innanzitutto, questo approccio non è affatto stabile. Se aggiungi disturbo casuale all'immagine, diminuirà notevolmente la somiglianza tra le due immagini. Ancora più importante, dal punto di vista dell'elaborazione delle immagini, non è efficiente o particolarmente buono. Suggerisco un altro approccio; ad esempio, usando un approccio basato su wavelet. Se hai eseguito un DWT 2d sull'immagine per alcuni livelli e confrontato i coefficienti di ridimensionamento, probabilmente otterrai risultati migliori. Inoltre, la trasformata wavelet discreta è O (n).

Il rovescio della medaglia è che le wavelet sono un argomento matematico avanzato. Ci sono alcune buone note OpenCourseWare su wavelet e filterbanks qui .