算法：如何使用矩形突出图像差异？

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  #

所以我正在寻找一种方便的算法来完成这个任务。

- Finkelson

---

@j_random_hacker，所以我需要构建一个图，对吧？ - Finkelson

@Finkelson：你不需要显式地构建一个图形——你可以使用由网格隐式定义的图形，其中每个1单元格都与其4（或可能8）个邻居中也是1单元格的任何一个相连。 - j_random_hacker

我非常喜欢这个问题。有很多解决方案。一个有趣的变化是计算可能解决方案的数量；或者，更好的是，计算用最少数量的矩形描述感兴趣区域的解决方案的数量（一般情况下可能存在许多这样的解决方案）。 - blazs

@Finkelson：不，图表应该是无向的。请搜索“泛洪填充算法”以获取更多帮助。 - j_random_hacker

@blazs 是的，没错。不过，边框可能会重叠。 - Finkelson

Answer 1

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

以下是算法的一个想法：

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

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

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

- blazs

Answer 2

以下是一些JS演示代码，用于查找矩形，每次从下一个剩余的非空单元格开始，并以递归方式探索所有路径。当访问单元格时，它们将被清除。

这与MS Paint等工具中的“填充”工具非常接近。更准确地说，这是一种泛洪填充算法，如评论中j-random-hacker所提到的。

该代码将找到矩形的内部边界。如果您想要外部边界，则需要稍微更新一下。

var W = 8, H = 8;
var matrix = [
//  0  1  2  3  4  5  6  7
  [ 0, 0, 0, 0, 0, 0, 0, 0 ], // 0
  [ 0, 0, 0, 0, 0, 1, 1, 1 ], // 1
  [ 0, 0, 0, 1, 0, 0, 0, 0 ], // 2
  [ 0, 0, 0, 0, 0, 0, 0, 0 ], // 3
  [ 0, 0, 0, 0, 1, 0, 0, 0 ], // 4
  [ 0, 0, 0, 0, 0, 1, 0, 0 ], // 5
  [ 0, 0, 0, 0, 1, 1, 1, 0 ], // 6
  [ 0, 0, 0, 0, 1, 1, 0, 0 ]  // 7
];
var dir = [
  [ -1, -1 ], [ 0, -1 ], [ 1, -1 ], [ 1, 0 ], [ 1, 1 ], [ 0, 1 ], [ -1, 1 ], [ -1, 0 ]
];

var x, y, rect;

for(y = 0; y < H; y++) {
  for(x = 0; x < W; x++) {
    if(diffAt(x, y)) {
      rect = { x0:x, y0:y, x1:x, y1:y };
      recurse(x, y, rect);
      console.log(
        'Found rectangle: ' +
        '(' + rect.x0 + ',' + rect.y0 + ') -> ' +
        '(' + rect.x1 + ',' + rect.y1 + ')'
      );
    }
  }
}

function recurse(x, y, rect) {
  rect.x0 = Math.min(rect.x0, x);
  rect.y0 = Math.min(rect.y0, y);
  rect.x1 = Math.max(rect.x1, x);
  rect.y1 = Math.max(rect.y1, y);
  matrix[y][x] = 0;

  for(var d = 0; d < 8; d++) {
    if(diffAt(x + dir[d][0], y + dir[d][1])) {
      recurse(x + dir[d][0], y + dir[d][1], rect);
    }
  }
}

function diffAt(x, y) {
  return x < 0 || x >= W || y < 0 || y >= H ? 0 : matrix[y][x];
}

- Arnauld

Answer 3

你可以使用两步算法：首先，在图像中找到8连通组件，然后计算每个组件的边界框。这种方法可能会导致重叠的矩形（想象一下两个附近的“L”形），你可以通过合并重叠的矩形或将每个矩形中的非连接组件清零（以便可以对所有矩形求和并适当重构差异图像）来解决这个问题。如果你选择第二个选项，可以在Matlab中按如下方式获得矩形：

%# each element of the struct array rectangles contains a field
%# .Image, which is the rectangle, and 
%# .BoundingBox, which is the coordinates of the rectangle.    
rectangles = regionprops(differenceImage,'Image','BoundingBox');

- Jonas