Алгоритмы: как выделить разницу изображений с помощью прямоугольников?

Мне нужно сравнить два изображения и создать прямоугольники разницы. Я могу построить матрицу различий следующим образом: 

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  #
Поэтому я ищу алгоритм, чтобы сделать это удобным способом.
3 3
algorithm image-compression

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');
1

Я предполагаю, что проблема заключается в следующем. Учитывая матрицу 0/1, покройте области, содержащие 1s, непересекающимися прямоугольниками (т. е. прямоугольники не должны пересекаться). В частности, запрещены непрямоугольные формы-например, Г-образное домино.

Вот идея для алгоритма:

  • Начните с начала координат, с индекса (0,0), и расширяйте до тех пор, пока развернутая область не будет содержать один прямоугольник 1s, который вы не можете увеличить, перемещаясь в соседние ячейки в любом из них. направление.
  • Добавьте этот прямоугольник в коллекцию и удалите обработанную область;
  • рекурсия по оставшимся ячейкам.

Время выполнения должно быть линейным по числу ячеек; однако, в зависимости от наличия дополнительных спецификаций на тип вывода, может потребоваться изменить первый шаг.

Мне очень нравится эта проблема. Обратите внимание, что для экземпляра задачи может существовать множество различных решений. Естественной вариацией было бы: требуется обложка, состоящая из как можно меньшего количества прямоугольников (т. е. минимальная обложка); в этом случае также может существовать много различных решений. (Счетная версия задачи выглядит интересной с точки зрения теории сложности.)

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];
}
1