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 像素区域的校验和将需要一些额外的存储空间，但是比较校验和而不是像素要快得多，并给出一个边界框“估计” - 如果您可以使用它，您可以直接使用它，也可以在之后对其进行改进。无论哪种情况，这都比上述方法快得多，尤其是在最坏的情况下。但是，这取决于您的设置，并且是“速度换大小”的权衡。