Acelerando la auto-similitud en una imagen.

Question

Estoy escribiendo un programa que generará imágenes. Una medida que quiero es la cantidad de "auto-similitud" en la imagen Escribí el siguiente código que busca las mejores coincidencias de countBest-th para cada ventana sizeWindow * sizeWindow en la imagen:

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 buena noticia es que el algoritmo hace lo que quiero que haga: devolverá un valor de 0.0 a 1.0 sobre cómo es una imagen "auto-similar".

La mala noticia, como estoy seguro de que ya has notado, es que el algoritmo es extremadamente lento. Toma los pasos (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * sizeWindow * sizeWindow para una carrera.

Algunos valores típicos para las 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.)

En este momento, no me preocupa la huella de memoria tomada por pvecount. Más tarde, puedo usar un conjunto de datos ordenados que no agrega otro elemento cuando es más pequeño que countBest. Solo me preocupa la velocidad del algoritmo.

¿Cómo puedo acelerar esto?

Answer 1

Su problema me recuerda fuertemente los cálculos que deben realizarse para compensación de movimiento en compresión de video. Tal vez deberías echar un vistazo más de cerca a lo que se hace en esa área.

Como rlbond ya señaló, contar el número de puntos en una ventana donde los colores coinciden exactamente no es lo que normalmente se hace al comparar imágenes. Un método conceptualmente más simple que usar transformaciones discretas de coseno o wavelet es agregar los cuadrados de las diferencias

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

y use sum en lugar de match como criterio de similitud (ahora más pequeño significa mejor).

Volviendo a lo que realmente preguntó: creo que es posible reducir el tiempo de ejecución por el factor 2 / sizeWindow (¿quizás al cuadrado?), pero es un poco desordenado. Se basa en el hecho de que ciertos pares de cuadrados que usted compara permanecen casi iguales al incrementar y1 en 1. Si los desplazamientos xOff = x2-x1 y yOff = y2-y1 son iguales, solo las rayas verticales superiores (rsp. Bottom) de los cuadrados ya no se igualan (rsp. ahora, pero no antes). Si mantiene los valores que calcula para la coincidencia en una matriz bidimensional indizada por los desplazamientos xOff = x2-x1 y yOff = y2-y1, puede calcular el nuevo valor para la coincidencia [xOff] [yOff] para y1 incrementado en 1 y x1 se mantiene igual en 2 * sizeWindow comparaciones:

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

(como los valores posibles para yOff cambiaron incrementando y1 del intervalo [y2 - y1, k_maxY - sizeWindow - y1 - 1] al intervalo [y2 - y1 - 1, k_maxY - sizeWindow - y1 - 2] puede descartar las coincidencias con el segundo índice yOff = k_maxY - sizeWindow - y1 - 1 y tiene que calcular las coincidencias con el segundo índice yOff = y2 - y1 - 1 de manera diferente). Tal vez también pueda mantener los valores según cuánto aumente / disminuya la coincidencia [] [] durante el ciclo en una matriz para obtener otra aceleración de 2 / sizeWindow.

Answer 2

Ok, primero, este enfoque no es estable en absoluto. Si agrega ruido aleatorio a su imagen, disminuirá en gran medida la similitud entre las dos imágenes. Más importante aún, desde el punto de vista del procesamiento de imágenes, no es eficiente ni particularmente bueno. Sugiero otro enfoque; por ejemplo, utilizando un enfoque basado en wavelet. Si realizó un DWT 2d en su imagen para unos pocos niveles y comparó los coeficientes de escalado, probablemente obtendría mejores resultados. Además, la transformada wavelet discreta es O (n).

La desventaja es que las wavelets son un tema matemático avanzado. Hay algunas buenas notas de OpenCourseWare sobre wavelets y filterbanks aquí .