c++ - 图片/"most resembling pixel"搜索优化？

Question

情况:

假设我有一个图像 A，例如 512x512 像素和图像 B，5x5 或 7x7 像素。两个图像都是 24 位 rgb，B 有 1 位 alpha 掩码(所以每个像素要么完全透明要么完全实心)。

我需要在图像 A 中找到一个像素(及其相邻像素)与图像 B 最相似的像素，或者可能与图像 B 最相似的像素。

相似度计算为“距离”，即非透明 B 的像素与 A 的像素之间的“距离”之和除以非透明 B 的像素数。以下是用于解释的示例 SDL 代码:

struct Pixel{
    unsigned char b, g, r, a;
};

void fillPixel(int x, int y, SDL_Surface* dst, SDL_Surface* src, int dstMaskX, int dstMaskY){
    Pixel& dstPix = *((Pixel*)((char*)(dst->pixels) + sizeof(Pixel)*x + dst->pitch*y));

    int xMin = x + texWidth - searchWidth;
    int xMax = xMin + searchWidth*2;
    int yMin = y + texHeight - searchHeight;
    int yMax = yMin + searchHeight*2;


    int numFilled = 0;
    for (int curY = yMin; curY < yMax; curY++)
        for (int curX = xMin; curX < xMax; curX++){
            Pixel& cur = *((Pixel*)((char*)(dst->pixels) + sizeof(Pixel)*(curX & texMaskX) + dst->pitch*(curY & texMaskY)));
            if (cur.a != 0)
                numFilled++;
        }

    if (numFilled == 0){
        int srcX = rand() % src->w;
        int srcY = rand() % src->h;
        dstPix = *((Pixel*)((char*)(src->pixels) + sizeof(Pixel)*srcX + src->pitch*srcY));
        dstPix.a = 0xFF;
        return;
    }

    int storedSrcX = rand() % src->w;
    int storedSrcY = rand() % src->h;
    float lastDifference = 3.40282347e+37F;

    //unsigned char mask = 

    for (int srcY = searchHeight; srcY < (src->h - searchHeight); srcY++)
        for (int srcX = searchWidth; srcX < (src->w - searchWidth); srcX++){
            float curDifference = 0;
            int numPixels = 0;
            for (int tmpY = -searchHeight; tmpY < searchHeight; tmpY++)
                for(int tmpX = -searchWidth; tmpX < searchWidth; tmpX++){
                    Pixel& tmpSrc = *((Pixel*)((char*)(src->pixels) + sizeof(Pixel)*(srcX+tmpX) + src->pitch*(srcY+tmpY)));
                    Pixel& tmpDst = *((Pixel*)((char*)(dst->pixels) + sizeof(Pixel)*((x + dst->w + tmpX) & dstMaskX) + dst->pitch*((y + dst->h + tmpY) & dstMaskY)));
                    if (tmpDst.a){
                        numPixels++;
                        int dr = tmpSrc.r - tmpDst.r;
                        int dg = tmpSrc.g - tmpDst.g;
                        int db = tmpSrc.g - tmpDst.g;
                        curDifference += dr*dr + dg*dg + db*db;
                    }
                }
            if (numPixels)
                curDifference /= (float)numPixels;
            if (curDifference < lastDifference){
                lastDifference = curDifference;
                storedSrcX = srcX;
                storedSrcY = srcY;
            }
        }

    dstPix = *((Pixel*)((char*)(src->pixels) + sizeof(Pixel)*storedSrcX + src->pitch*storedSrcY));
    dstPix.a = 0xFF;
}

这个东西应该用于纹理生成。

现在，问题是:
最简单的方法是暴力搜索(在示例例程中使用)。但它很慢 - 即使使用 GPU 加速和双核 cpu 也不会使它更快。由于 B 的掩码，我似乎无法使用修改后的二进制搜索。那么，我怎样才能更快地找到所需的像素呢？

附加信息:

1. 允许使用 2 个内核、GPU 加速、CUDA 和 1.5..2 GB 的 RAM 来完成任务。
2. 我宁愿避免某种需要 30 分钟才能完成的冗长预处理阶段。

想法？

Answer 1

您需要了解运动估计，它在视频编码中用于查找先前编码图片中与要编码的 block 最相似的 block 的位置。

(注意:我没有足够的声誉来发布 2 个链接，因此您必须在维基百科中查找运动估计)。

可以找到一些简单的 block 匹配算法here .这些方法仅通过分析搜索区域中的一部分点来工作。

如果您想找到最小化匹配函数的特定点，则必须进行全搜索。全搜索加速通常通过提前终止来实现——如果已经不可能改进之前的最佳结果，则结束对点的评估。

min_sad = INT_MAX  // minimum sum of absolute difference
min_point = {0, 0}

foreach (point p : all_search_points )
{         
    sad = 0
    for( y = 0; y < block_height; ++y )
        for( x = 0; x < block_width && sad < min_sad; ++x ):
            sad += abs( block_b[y,x] - block_a[p.y+y, p.x+x] )
        if( sad < min_sad )
            min_sad = sad
            min_point = p
}

在仅检查搜索点的子集时，提前终止也很有用，尽管加速比不上完整搜索。