图像/"最像像素"搜索优化？

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千兆字节的RAM来完成任务.
2. 我宁愿避免某种冗长的预处理阶段,需要30分钟才能完成.

想法？

Answer 1

回答我自己的问题。

简短的回答：我能够删除 alpha 通道，所以我决定使用图像金字塔（请参阅网上的金字塔和高斯金字塔）。它带来了巨大的速度提升。

长答案：

我最初的目标是纹理合成。Alpha用于生成尚未填充的像素，B表示已生成图像的一部分。（即A是样本图案，B是生成图像）

经过一番研究后，我发现要么没有快速的方法在 N 维空间中进行搜索（例如，3x3 像素区域基本上是一个 24 分量向量（不包括中心像素），而 7x7 将会是 144-组件，搜索该区域将是24维或144维搜索）。好吧，有一些方法（例如，名为“ I-COLLIDE：适用于大型环境的交互式精确碰撞检测系统”的论文使用 3 个排序数组（每个数组在不同维度上排序）进行 3 维搜索），但它们显然对于浮点数和维度数较少的情况会更好。

使用运动检测的建议没有用，因为（似乎）运动检测假设像素代表移动对象（在我的情况下并非如此），并且至少一些优化依赖于此。

最后，我找到了名为“使用树结构矢量量化进行快速纹理合成”（Li-Yi Wei，Marc Levoy，斯坦福大学）的论文，该论文使用的技术基于与我使用的算法类似的算法。要搜索的图像被下采样多次（类似于 mip-map 生成），首先在最低级别执行搜索，然后在下一个级别执行搜索。它可能不是为其他应用程序进行实际图像搜索的最佳方式，但它非常适合我的目的。这篇论文相对较旧，但对我有用。

同一篇论文提到了一些进一步加速搜索的技术。其中之一是“树结构矢量量化（TSVQ）”，尽管我无法提供更多有关它的信息（尚未检查它 - 当前纹理生成器在我的硬件上以可接受的速度工作，所以我可能不会看进一步优化）。