CODEWITHSUNDEEP
algorithmimage-processing
AC John
AC John

Reputation: 51

Find Different area between two images

My purpose is to compare pixels between two images and find out minimal(optimized) rectangular area that contains all different pixels between images. Simply, I compared all pixels(for example 1024*768 pixels) of two images and found out different part ,but it is not good idea because of speed. I need to do this compare at least fifteen times per second. Do you know any more effective algorithms for it?

Upvotes: 1

Views: 1568

Answers (2)

Mark Setchell
Mark Setchell

Reputation: 208013

Subtract one image from the other. Identical pixels will become zero, i.e. black.

Find a corner that is black and use a trim (trim border/edges) type of command to trim the black border which will tell you the area of difference.

It's pretty simple to do in two lines of ImageMagick if you can use that - it is available on many platforms for C/C++, Python, Perl...

Let's take two images, a.jpg and b.jpg:

enter image description here

enter image description here

Did you see what I did there? :-)

Now we can use ImageMagick, to find the differences and the different area. I am using the command-line, but as I said, you can use C/C++, Perl, Python, .NET or whatever floats your boat.

Either use this to find the differences:

convert a.jpg b.jpg \
       -compose difference \
       -composite \
       -threshold 0 \
       -separate \
       -evaluate-sequence Add \
        diff.jpg

which gives this:

enter image description here

Or use this:

composite a.jpg b.jpg  -compose difference diff.jpg

which gives this:

enter image description here

Or use this for a simple subtraction:

convert a.jpg b.jpg -compose minus -composite diff.jpg

enter image description here

Now you can use ImageMagick's border-trim function to evaluate what would be left if you trimmed all the black borders off, like this:

convert a.jpg b.jpg \
       -compose difference \
       -composite \
       -threshold 0 \
       -separate \
       -evaluate-sequence Add \
       -format "%w %h %@" \
        info:

which outputs this:

400 463 264x240+80+176

telling you that the image is 400x463, and if you cropped the border you would be left with a rectangle 264x240 with its top left pixel offset 80,176 from top-left of the image.

Just for fun, I will draw that rectangle onto the image in red, with this command:

convert diff.jpg \
       -stroke red \
       -fill transparent \
       -draw "rectangle 80,176 344,416" \
        rect.jpg

which gives this:

enter image description here

Essentially you can do all I have explained here in one or two lines of shell, or 8-10 lines of C/C++. Note that the bounding box is slightly large because the cartoons I superimposed have transparent, rectangular backgrounds. You can also use -fuzz 5% to allow for a minor differences in the images if you need to allow a degree of "sloppiness" in the differencing.

Another way of detecting the bounding box is to squidge the difference image till it is a tall image, just one pixel wide, like this:

convert diff.jpg -scale 1x! -threshold 1% t.jpg

Resulting image below:

enter image description here

now you can find the first white pixel easily if you convert the output to text format (you wouldn't do it this way in a program - you would write a loop instead - but I am showing the concept here):

convert diff.jpg -scale 1x! -threshold 1% txt: | grep -m1 white

 0,176: (255,255,255)  #FFFFFF  white

The grep -m1 white looks for the first line with white in it and then stops looking (matches are limited to 1). That shows the first line with a white pixel in it is 176 - compare with the red box above. Now we can find the last white pixel, using:

convert diff.jpg -scale 1x! -threshold 1% txt: | grep white | tail -1

 0,415: (255,255,255)  #FFFFFF  white

and we know that row 415 is the bottom of the bounding box.

Now you squidge the image to a wide, flat version just 1 pixel high, and find the left and right limits of your bounding box:

convert diff.jpg -scale x1! -threshold 1% txt: | grep -m1 white

 80,0: (255,255,255)  #FFFFFF  white

convert diff.jpg -scale x1! -threshold 1% txt: | grep white | tail -1

 343,0: (255,255,255)  #FFFFFF  white

So the left-right limits of your bounding box are 80 and 343 - as per the red rectangle.

Upvotes: 9

TravisJ
TravisJ

Reputation: 1622

If your pixel values are stored in a 2D array (say gray scale for the moment, 0-255) what you could do is treat the arrays like matrices and start by subtracting the two. Entries in the result that are zero are pixels that are the same and non-zero means they are different. Then you find the top row containing a non-zero entry as your y-MAX, the lowest row with a non-zero for your y-MIN, first column with a non-zero for x-MIN and last column with non-zero for x-MAX. Then the rectangle has 4 coordinates:

  • (x-MIN, y-MIN) --lower left corner
  • (x-MAX, y-MIN) --lower right corner
  • (x-MAX, y-MAX) --top right corner
  • (x-MIN, y-MAX) --top left corner

If you happened to know that all the entries were at least zero (could be done by taking absolute value, but that will add cost) then you could Multiply the matrix by the all 1's column vector on the right. This will give you row-sums. Then you find the first and last non-zero row-sum (search top down and bottom up). If you multiply on the left by an all 1's row vector you'll get the same thing, but column sums. Again look for those that are non-zero.

The matrix operations are nice because there are optimized libraries out there that can help speed up that computation (and your matrices are not that big)... especially if you have a GPU you can use to do the computation. But even in serial, small matrix-vector computations are not that time consuming.

Upvotes: 1

Related Questions