Accélération de l'auto-similarité dans une image

Question

J'écris un programme qui va générer des images. Une mesure que je veux est la quantité de "soi-similitude". dans l'image. J'ai écrit le code suivant qui recherche les meilleurs résultats countBest-th pour chaque fenêtre sizeWindow * sizeWindow de l'image:

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 bonne nouvelle est que l'algorithme fait ce que je veux: il renvoie une valeur comprise entre 0.0 et 1.0 indiquant à quel point une image est similaire à celle d'une personne.

La mauvaise nouvelle, comme vous l'avez sans doute déjà noté, est que l'algorithme est extrêmement lent. Il faut (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * sizeWindow * sizeWindow pour une exécution.

Quelques valeurs typiques pour les variables:

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

Pour le moment, je ne suis pas inquiet à propos de l'empreinte mémoire prise par pvecount. Plus tard, je peux utiliser un ensemble de données triées qui n'ajoute pas d'élément lorsqu'il est inférieur à countBest. Je ne m'inquiète que de la vitesse de l'algorithme.

Comment puis-je accélérer le processus?

Answer 1

Votre problème me rappelle fortement les calculs à effectuer pour la compensation de mouvement en compression vidéo. Peut-être devriez-vous regarder de plus près ce qui se fait dans ce domaine.

Comme l'a déjà souligné rlbond, compter le nombre de points dans une fenêtre où les couleurs correspondent exactement n'est pas ce qui est normalement fait lors de la comparaison des images. Une méthode conceptuellement plus simple que l’utilisation de transformations discrètes en cosinus ou en ondelettes consiste à ajouter les carrés des différences

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

et utilisez sum au lieu de match comme critère de similarité (maintenant, plus petit signifie mieux).

Revenons à ce que vous avez vraiment demandé: Je pense qu’il est possible de réduire le temps de fonctionnement du facteur 2 / sizeWindow (peut-être au carré?), mais c’est un peu compliqué. Cela est basé sur le fait que certaines paires de carrés que vous comparez restent presque les mêmes lorsque vous incrémentez y1 de 1. Si les décalages xOff = x2-x1 et yOff = y2-y1 sont identiques, seules les rayures verticales supérieures (inférieures) sont des carrés ne sont plus (rsp. maintenant, mais pas avant) appariés. Si vous conservez les valeurs que vous avez calculées dans un tableau à deux dimensions indexé par les décalages xOff = x2-x1 et yOff = y2-y1, vous pouvez alors calculer la nouvelle valeur de correspondance [xOff] [yOff] pour y1 augmentée de 1 et x1 restant les mêmes de 2 * comparaisons sizeWindow:

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

(comme les valeurs possibles pour yOff ont changé - en incrémentant y1 - de l'intervalle [y2 - y1, k_maxY - sizeWindow - y1 - 1] à l'intervalle [y2 - y1 - 1, k_maxY - sizeWindow - y1 - 2] vous pouvez ignorer les correspondances avec le second index yOff = k_maxY - sizeWindow - y1 - 1 et calculer les correspondances avec le second index yOff = y2 - y1 - 1 différemment). Peut-être que vous pouvez aussi garder les valeurs de combien vous augmentez / diminuez la correspondance [] [] pendant la boucle dans un tableau pour obtenir une autre accélération de 2 / sizeWindow.

Answer 2

Ok, d’abord, cette approche n’est pas stable du tout. Si vous ajoutez du bruit aléatoire à votre image, la similarité entre les deux images en sera grandement réduite. Plus important encore, du point de vue du traitement des images, ce n'est ni efficace ni particulièrement efficace. Je suggère une autre approche. par exemple, en utilisant une approche basée sur les ondelettes. Si vous réalisiez une image DWT en 2D sur votre image pour quelques niveaux et compariez les coefficients de mise à l'échelle, vous obtiendrez probablement de meilleurs résultats. De plus, la transformée en ondelettes discrète est O (n).

L’inconvénient est que les ondelettes sont un sujet mathématique avancé. Il existe de bonnes notes OpenCourseWare sur les ondelettes et les filtres, ici .