算法 : How to highlight image difference using rectangles?

Question

我需要比较两个图像并创建差异矩形。我可以像这样构建差异矩阵:

0  0  0  0  0  0  0  0 
0  0  0  0  0  1  1  1 
0  0  0  1  0  0  0  0 
0  0  0  0  0  0  0  0 
0  0  0  0  1  0  0  0 
0  0  0  0  0  1  0  0 
0  0  0  0  1  1  1  0 
0  0  0  0  1  1  0  0

其中 1 是差异像素。我需要找到为图像差异区域创建矩形的方法。在我的示例中，我要突出显示三个区域。

# # #
# 1 #
# # #

#  #  #  # 
#  1  1  1 
#  #  #  #

#  #  #  #  #
#  1  0  0  # 
#  0  1  0  # 
#  1  1  1  # 
#  1  1  0  #

所以我正在寻找一种算法来以方便的方式做到这一点。

Answer 1

我假设问题如下。给定一个 0/​​1 矩阵，用不相交的矩形覆盖包含 1 的区域(即矩形不能相交)。特别是，非矩形形状(例如 L 形多米诺骨牌)是不允许的。

这里有一个算法的想法:

• 从原点开始，在索引 (0,0) 处扩展，直到扩展区域包含单个 1 矩形，您无法通过移动来放大该矩形到任一方向的相邻单元格。
• 将该矩形添加到集合中，并删除处理过的区域；
• 递归剩余的单元格。

运行时间应与单元格数量成线性关系；但是，根据输出类型是否有其他规范，您可能需要更改第一步。

我很喜欢这个问题。请注意，一个问题实例可能存在许多不同的解决方案。一个自然的变化是需要一个由尽可能少的矩形组成的覆盖层(即最小覆盖层)；在这种情况下，也可能存在许多不同的解决方案。 (从复杂性理论的角度来看，问题的计数版本看起来很有趣。)