如何无精度损失实现比现有方案更快的大图内小图匹配定位？

现有实现问题 #

当前基于GDI截屏获取屏幕大图、从文件加载待匹配小图后，采用逐像素遍历比对的方式做模板匹配，运行速度过慢。要求匹配过程无任何精度损失，此前尝试的灰度变换、逐列哈希比对等方案均存在精度损失，无法满足使用要求。
原有逐像素比对实现代码如下：

// input:big image,samll image,sim,dfcolor,rc
// output:a POINT,{-1,-1} means not found
PBYTE pSrc = _src.getBytes(); // _src is big image, pSrc is big image data pointer
PBYTE pPic = pic->getBytes(); // pic is small image, pPic issamll image data pointer
int max_error = (1. - sim) * pic->width() * pic->height();
int error_count = 0;
bool bad = false;
// rc is a rect,because use multithreading,every thread handle a block of big image
for (int i = rc.y1; i < rc.y2; ++i) {
    for (int j = rc.x1; j < rc.x2; ++j) {
        // stop is a std::atomic_bool variable,to notify other threads to stop if found
        if (stop) {
            return { -1, -1 };
        }
        // image data is stored as bgra,i just compare rgb
        // dfcolor is color deviation
        for (int y1 = 0; y1 < pic->height() && !bad; ++y1) {
            for (int x1 = 0; x1 < pic->width(); ++x1) {
                int index1 = ((i + y1) * _src.width() + j + x1) << 2; 
                int index2 = (y1 * pic->width() + x1) << 2;
                if (abs(*(pSrc + index1) - *(pPic + index2)) >= dfcolor.b ||
                    abs(*(pSrc + index1 + 1) - *(pPic + index2 + 1)) >= dfcolor.g ||
                    abs(*(pSrc + index1 + 2) - *(pPic + index2 + 2)) >= dfcolor.r) {
                    ++error_count;
                    if (error_count > max_error) { 
                        bad = true;
                        break;
                    }
                }
            }
        }
        // not found,continue
        if (bad) {
            error_count = 0;
            bad = false;
            continue;
        }
        // found
        stop = true;
        return { i, j };
    }
}
return { -1,-1 };

零精度损失优化方案 #

所有优化方案完全保留原有颜色容差、允许错误像素占比的判断逻辑，不会出现漏判、误判：

• SIMD指令集并行比对：使用SSE/AVX2指令集批量处理像素比对逻辑，单条指令可同时完成16/32个字节的差值计算、容差判断，单轮循环处理的像素数量是原有逐像素实现的8-16倍。整个比对逻辑和原有逐像素判断完全一致，没有任何精度损失，是提速幅度最大的优化点。
• 提前终止逻辑前置：原有逻辑需要遍历小图内大量像素才会触发不匹配退出，优化后优先比对小图的角点、边缘等辨识度最高的像素，候选位置只要出现第一个超出容差的像素就直接终止当前位置的比对，大部分无效候选位置仅需比对几个像素就会被淘汰，不用遍历整个小图区域。
• 缓存访问优化：调整内存访问顺序，将小图数据提前预取到CPU L1缓存，每个线程处理的大图分片大小调整到和CPU L2缓存匹配（256KB~1MB），避免跨缓存行的随机内存访问，大幅提升缓存命中率。减少原子变量stop的读取频率，每比对完一整行小图再读取一次状态即可，避免频繁原子操作带来的性能开销。
• 零开销预过滤：提取小图4个角点、边缘特征点的像素值，遍历大图候选位置时先校验这些特征点的像素是否在容差范围内，只要有一个特征点不满足要求直接跳过当前位置。该过滤逻辑不会漏掉任何符合匹配要求的位置，可提前过滤90%以上的无效候选位置，额外开销极低。
• 编译层优化：开启O2/O3最高编译优化等级，启用对应目标CPU的SIMD指令集编译选项，将代码中基于索引计算的像素访问改为指针递增访问，引导编译器自动做循环展开，减少索引计算的冗余开销。

内容的提问来源于stack exchange，提问作者asa