Search code examples
algorithmimage-compression

Algorithms: How to highlight image difference using rectangles?

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.

Solution

  • You could do a two-step algorithm: First, you find 8-connected components in your image, then you calculate the bounding box for each of the component.

    This approach may lead to overlapping rectangles (imagine two nearby "L"-shapes), which you could solve by either merging the overlapping rectangles or by zeroing out non-connected components from each rectangle (so that you can sum all the rectangles and reconstruct the difference image appropriately).

    If you go with the second choice, you can get the rectangles in Matlab as follows:

    %# 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');