找到两个图像之间的差异的边界框？

Question

我有2个位图图像，其中1是另一个的轻微变化。 现在我想尽可能快地计算出变化区域的边界框。 有没有一个聪明的算法来做到这一点，或者它只是一个蛮力处理的案例？

编辑： 图像将是screencaptures。我想找到更改区域的最小边界框，如“此框外部没有任何更改”。

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像素区域的校验和需要一些额外的存储空间，但是比较校验和而不是像素速度要快得多，并且给出了一个布局框“估计” - 您可以直接使用它，如果您可以使用它或在之后进行优化。无论哪种情况，这都会比上述方法快得多，特别是对于最差情况。但是，这取决于您的设置，并且是“速度的大小”折衷。