c++ - 加快图像的自相似性

我正在写一个程序来生成图像我想要的一个衡量标准是图像中“自相似性”的数量我编写了以下代码，为图片中的每个sizeWindow*sizeWindow窗口查找倒数第四个最佳匹配：

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

好消息是，该算法实现了我想要的功能：它将返回一个从0.0到1.0的值，用于说明图片的“自相似”程度。
坏消息——我相信你已经注意到了——是算法非常慢跑步需要(k_maxX - sizeWindow) * (k_maxY - sizeWindow) * (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * sizeWindow * sizeWindow步。
变量的一些典型值：

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

现在，我不担心pvecount占用的内存。稍后，我可以使用排序的数据集，当它小于countBest时，不添加其他元素我只担心算法的速度。
我怎样才能加快速度？

最佳答案

你的问题强烈地提醒我在视频压缩中必须对motion compensation进行计算也许你应该仔细看看这方面的情况。
正如rlbond已经指出的那样，在一个颜色完全匹配的窗口中计算点的数量并不像通常比较图片那样与使用离散余弦或小波变换相比，概念上更简单的方法是将差的平方相加

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

使用和而不是匹配作为相似性的标准（现在更小意味着更好）。
回到你真正问的问题：我认为可以将运行时间减少2/sizewindow（可能是平方？），但有点乱。这是基于这样一个事实：当y1递增1时，所比较的某些正方形对几乎保持不变。如果偏移量xOff=x2-x1和yOff=y2-y1相同，则仅顶部（rsp）底部）方块的垂直条纹不再是（RSP。现在，但不是以前）匹配。如果将为匹配计算的值保留在二维数组中，该数组的索引为偏移量xOff=x2-x1和yOff=y2-y1，则可以计算y1的match[xOff][yOff]的新值，该值增加1，x1保持不变，并进行2*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
    }
}

（由于yoff的可能值已更改-通过将y1从间隔[y2-y1，k廑maxy-sizewindow-y1-1]递增到间隔[y2-y1-1，k廑maxy-sizewindow-y1-2]可以放弃具有第二个索引yoff=k廑maxy-sizewindow-y1-1的匹配，并且必须以不同的方式计算具有第二个索引yoff=y2-y1-1的匹配）。也许您还可以通过在数组中循环期间增加/减少match[][]的数量来保留值，以获得另一个2/sizeWindow加速。