检测图像在大图中的位置
如何在一张大图中找到一张小图的位置？我有一张没有修改过的小图。这张小图会被调整到任意的分辨率，然后随机放置在一张更大的图里，而这张大图的大小也是随意的。除了这个，其他的变换都没有进行。用Python代码来实现最好，可能需要用到libgd这个库。如果你知道一个好的解决方法，给你个赞！
4 个回答
我第一反应是去看看这个链接：http://en.wikipedia.org/wiki/Autocorrelation。
你可能想要了解一下交叉相关。自相关是把一个信号和它自己进行比较，而交叉相关则是把两个不同的信号进行比较。
相关性分析的好处在于，它不仅仅是检查两个信号是否完全相同，而是能告诉你最匹配的地方在哪里，以及匹配的程度有多好。不过，对于一个二维图像来说，这个过程的复杂度大约是O(N^3)，算法也不是那么简单。但一旦你搞定了它，就会觉得非常神奇。
编辑：哎呀，你提到的是任意的调整大小。这会导致任何基于相关性的算法都无法正常工作。抱歉，这超出了我的经验范围，而且Stack Overflow不允许我删除这个回答。
这里有一个简单粗暴的解决办法，就是在目标图像上滑动一个窗口，计算每个位置的相似度，然后选择相似度最高的位置。接着，你把这个相似度和一个设定的阈值进行比较，如果分数高于这个阈值，就说明图像在那儿，那个位置就是你要找的；如果分数低于阈值，那就说明图像不在那儿。
作为相似度的衡量标准，你可以使用归一化相关性或者平方差和（也叫L2范数）。正如大家提到的，这种方法无法处理尺度变化。所以你还需要把原始图像缩放多次，然后对每个缩放后的版本重复上述过程。根据输入图像的大小和可能的缩放范围，这种方法可能就足够了，而且实现起来也比较简单。
更合适的解决方案是使用仿射不变特征。可以查一下“宽基线立体匹配”，人们在这个背景下研究过这个问题。通常使用的方法大致是这样的：
原始图像的预处理
- 运行一个“兴趣点检测器”。这个检测器会在图像中找到一些容易定位的点，比如角落。有很多种检测器，其中一个叫“哈里斯-仿射”的检测器效果不错，而且很流行（所以可能已经有现成的实现）。另一个选择是使用高斯差分（DoG）检测器，它是为SIFT开发的，也效果很好。
- 在每个兴趣点上，提取一个小的子图像（比如30x30像素）。
- 对于每个子图像，计算一个“描述符”，也就是这个窗口内图像内容的某种表示。同样，有很多种描述符。需要关注的是描述符对图像内容的描述能力（你希望只有相似的描述符才能匹配）以及它的尺度不变性（即使缩放后也希望保持一致）。在你的情况下，我推荐使用SIFT。虽然它的尺度不变性不如其他一些描述符，但在处理尺度变化方面表现不错，而在你的情况中，尺度是唯一变化的因素。
在这个阶段结束时，你将会得到一组描述符。
测试（使用新的测试图像）
- 首先，运行和第一步相同的兴趣点检测器，得到一组兴趣点。然后为每个点计算相同的描述符，和之前一样。现在你也有了目标图像的一组描述符。
- 接下来，寻找匹配。理想情况下，原始图像的每个描述符在目标图像中都会有一个非常相似的描述符。（由于目标图像更大，也会有一些“剩余”的描述符，也就是那些在原始图像中没有对应点的点。）所以如果足够多的原始描述符匹配得足够相似，那么你就知道目标图像在那儿。此外，由于描述符是位置特定的，你也会知道原始图像在目标图像中的具体位置。