algorithm - 找到两张图像之间差异的边界框？

Question

我有 2 个位图图像，其中 1 个与另一个略有不同。现在我想尽快计算变化区域的边界框。是否有智能算法可以做到这一点，或者这只是一种暴力处理的情况？

编辑:图像将是屏幕截图。我想找到更改区域的最小边界框，如“在此框之外没有任何变化”。

Answer 1

如果您只想要一个边界框，您绝对可以比“蛮力”(始终检查所有像素，2*w*h 操作)做得更好，至少在图像之间存在任何差异的情况下。只需从 4 个不同的边框开始查找前 4 个不同的行/列像素。伪代码:

bounding_box_y1 = -1;
loop y = 1..h {
 loop x = 1..w {
   if image1(x,y) != image2(x,y) {
     bounding_box_y1 = y
     exit loops
   }
 }
}

上面的伪代码遍历图像行，从顶行开始直到找到不同的像素，返回 bounding_box_y1。只需再添加 3 个循环(行从底部开始 => bounding_box_y2，列从左开始 => bounding_box_x1，列从右开始 => bounding_box_x2)，你'将具有您的边界框的坐标。

该算法仍然对相同的图像执行 2*w*h 操作(请注意，在这种情况下，bounding_box_y1 将保持 -1，您可以跳过额外的 3 个循环)，但如果图像存在差异(在最佳情况下仅检查 4 个角像素)，速度会快得多。

编辑:在我看到你的问题编辑后，我有了另一种方法的想法:如果你将一个图像与其他图像多次比较，你可以存储额外的校验和信息，例如存储 16x16 像素区域的校验和会占用一些额外的存储空间，但比较校验和而不是像素要快得多，并且会给出一个边界框“估计”——如果你能接受它，你可以直接使用它，也可以在之后对其进行优化。在任何一种情况下，这都将比上述方法快得多，尤其是对于最坏的情况。但是，这取决于您的设置，并且是“速度大小”的权衡。