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

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 矩形，您无法通过沿任一方向移动到相邻单元格来放大该矩形。
将该矩形添加到集合中，并删除处理过的区域；
对剩余单元格进行递归。

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

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

Answer 2

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

这与 'fill' 工具在 MS Paint 等软件中的作用非常接近。更准确地说，这是一个 flood fill algorithm，正如 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];
}

Answer 3

您可以执行两步算法：首先，您在图像中找到 8-connected components，然后计算每个组件的边界框。

这种方法可能会导致矩形重叠（想象两个相邻的 "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');

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

Algorithms: How to highlight image difference using rectangles?

algorithm

image-compression