Algorithms: How to highlight image difference using rectangles?

Question

I need to compare two images and create rectangles of the difference. I can build a difference matrix like this:

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

where 1 is diff pixel. I need to find the way to create rectangles for areas of image diff. In my example, I have three areas to highlight.

# # #
# 1 #
# # #

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

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

So I'm looking for an algorithm to do that in a convenient way.

Answer 1

I'm assuming that the problem is as follows. Given a 0/1-matrix, cover the regions containing 1s with disjoint rectnagles (i.e. the rectangles must no intersect). In particular, non-rectangular shapes---for example, an L-shaped domino---are disallowed.

Here's an idea for an algorithm:

• start at the origin, at index (0,0), and expand out until the expanded region contains a single rectangle of 1s that you cannot enlarge by moving to adjacent cells in either direction.
• add that rectangle to the collection, and remove the processed region;
• recurse on the remaining cells.

The running time should be linear in the number of cells; however, depending on whether there are additional specifications on the type of the output, you may need to change the first step.

I like the problem a lot. Notice that many different solutions may exist for a problem instance. A natural variation would be to require a cover comprised of as few rectangles as possible (i.e. a minimal cover); in this case, too, there may exist many different solutions. (The counting version of the problem looks interesting from the complexity-theoretic viewpoint.)