0

我正在编写一个生成图像的程序。我想要的一种测量是图像中“自相似”的数量。我编写了以下代码，为图片中的每个 sizeWindow * sizeWindow 窗口查找 countBest-th 最佳匹配：

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 时，它不会添加另一个元素。我只担心算法速度。

我怎样才能加快速度？

4

2 回答 2

2

好的，首先，这种方法根本不稳定。如果在图像中添加随机噪声，则会大大降低两幅图像之间的相似性。更重要的是，从图像处理的角度来看，它效率不高或特别好。我建议另一种方法；例如，使用基于小波的方法。如果您在图像上执行几个级别的 2d DWT 并比较缩放系数，您可能会得到更好的结果。另外，离散小波变换是 O(n)。

缺点是小波是一个高级数学主题。这里有一些关于小波和滤波器组的优秀 OpenCourseWare 笔记。

于 2009-11-26T04:52:05.803 回答
1

您的问题强烈提醒我在视频压缩中必须进行运动补偿的计算。也许你应该仔细看看在那个领域做了什么。

正如 rlbond 已经指出的那样，计算窗口中颜色完全匹配的点数并不是比较图片时通常所做的。与使用离散余弦或小波变换相比，概念上更简单的方法是将差的平方相加

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

并使用sum而不是match作为相似度的标准（现在更小意味着更好）。

回到你真正问的问题：我认为可以将运行时间减少 2/sizeWindow 倍（可能是平方？），但这有点混乱。这是基于这样一个事实，即您比较的某些正方形对在将 y1 递增 1 时几乎保持不变。如果偏移量 xOff = x2-x1 和 yOff = y2-y1 相同，则只有顶部（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 加速。

于 2009-11-26T17:42:00.247 回答