Acelerar auto-similaridade em uma imagem

Question

Eu estou escrevendo um programa que irá gerar imagens. Uma medida que eu quero é a quantidade de "auto-similaridade" na imagem. Eu escrevi o seguinte código que procura a countBest-th melhores partidas para cada janela sizeWindow * sizeWindow na imagem:

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

A boa notícia é que o algoritmo faz o que eu quero que ele: ele irá retornar um valor de 0.0 a 1.0 sobre como 'auto-similar' uma imagem

.

A má notícia - como eu tenho certeza que você já observou - é que o algoritmo é extremamente lento. Ele toma medidas (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * sizeWindow * sizeWindow para uma corrida.

Alguns valores típicos para as variáveis:

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

Agora, eu sou não preocupado com o consumo de memória tomada por pvecount. Mais tarde, eu posso usar um conjunto de dados classificados que não adiciona um outro elemento quando ele é menor do que countBest. Estou apenas preocupado com a velocidade do algoritmo.

Como posso acelerar isso?

Answer 1

Seu problema me lembra fortemente dos cálculos que têm que ser feitas para compensação de movimento em compressão de vídeo. Talvez você deve dar uma olhada mais de perto o que está feito nessa área.

Como já rlbond apontou, contando o número de pontos em uma janela onde as cores exatamente jogo não é o que normalmente é feito em comparação fotos. Um método conceitualmente mais simples do que usar cosseno discreta ou transformações wavelet é adicionar os quadrados das diferenças

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

e usar sum em vez de jogo como critério para a semelhança (agora significa menores melhor).

Voltar para o que você realmente perguntou: Eu acho que é possível reduzir o tempo de execução pelo fator 2 / sizeWindow (talvez ao quadrado?), Mas é um pouco confuso pouco. Ele é baseado no fato de que determinados pares de quadrados que você comparar estadia quase o mesmo quando incrementando y1 por 1. Se o offsets xDesligado = x2-x1 e Yoff = Y2-Y1 são os mesmos, apenas a parte superior (RSP. Baixo) listras verticais das praças não são mais (RSP. agora, mas não antes) correspondida. Se você mantiver os valores que você calcular para o jogo em uma matriz bidimensional indexada pelo offsets xDesligado = x2-x1 e Yoff = y2-y1, em seguida, pode-se calcular o novo valor para o jogo [xDesligado] [Yoff] para y1 aumentou 1 e x1 permanecer o mesmo por 2 * sizeWindow comparações:

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 os valores possíveis para YOFF mudado - incrementando y1 - a partir do intervalo [y2 - y1, k_maxY - sizeWindow - Y1 - 1] para o intervalo [y2 - Y1 - 1, k_maxY - sizeWindow - Y1 - 2] você pode descartar os jogos com o segundo índice de Yoff = k_maxY - sizeWindow - y1 - 1 e tem que calcular os jogos com o segundo índice de Yoff = y2 - y1 - 1 de forma diferente). Talvez você também pode manter os valores por quanto você aumentar / diminuir jogo [] [] durante o ciclo em uma matriz para obter outro 2 / sizeWindow velocidade-up.

Answer 2

Ok, em primeiro lugar, esta abordagem não é estável em tudo. Se você adicionar ruído aleatório à sua imagem, ele irá diminuir consideravelmente a semelhança entre as duas imagens. Mais importante, do ponto de vista de processamento de imagem, não é eficiente ou particularmente bom. Sugiro uma outra abordagem; por exemplo, usando uma abordagem baseada em wavelet. Se você executou uma DWT 2d em sua imagem por alguns níveis e comparados os coeficientes escala, você provavelmente obter melhores resultados. Além disso, a Transformada Wavelet Discreta é O (n).

A desvantagem é que ondas são um tópico matemático avançado. Há algumas notas boas OpenCourseWare em wavelets e bancos de filtros aqui .