Find the differences between two images and the locations of the differences

[Clawsy]

Hi I'm writing a client/server remote viewer application where screenshots of the desktop are sent across the network over a socket. I'd like to reduce the size of the transfer by getting the difference between the two images and then sending the difference. The difference would be at least a rectangle, no? So I need to locate where the change is and send only the "update rectangle" to the client.
How can I do that? I need performance... (can't loop through pixels... too much time consuming)

[JamesCherrill]

Somebody somewhere is going to have to loop thru the pixels to find differences. Are you sure it's too time consuming? If you haven't tried it, I would not jump to conclusions about performance. You'll simply be comparing two arrays of ints in a tiny loop - that's about as fast as anything can be.

[Clawsy]

Really? That means you know better how to do it. Can you give me a link or code please? I looped through the pixels taking the array with getRGB() and I looped through it comparing every value with the array from the second image. It took a long time... too long. Maybe I don't know how to do it. I would apreciate your help. Thanks!

[JamesCherrill]

I'd use the PixelGrabber class to convert the images to simple int arrays, then compare those arrays. Each int is 1 pixel , and there's no need to decode the individual rgb values.

[Clawsy]

Ok, but I wonder... this would help me detecting the location of the difference? I need the rectangle(s) that contains the differens(es)

[JamesCherrill]

Yo. Loop thru the x/y coords iin a nested loop and record the first and last x and the first and last y where there is a difference. Those 4 numbers will define the smallest rectangle that contains the pixels that are different

[Clawsy]

Got the array of those 2 different images and I compare them but I think the comparison is not good... I don't know how to find the coords... cause its a array, not a matrix. I get printed the same element 30 times or so. Can you help me out please? I want to do this and see what is the performance I get. Cause every millisecond is important to me. Thanks in advance.

//pixel array is grabber first, then pixel2
    int[] pixels2 = new int[w * h];
	    PixelGrabber pg2 = new PixelGrabber(img, 0, 0, w, h, pixels2, 0, w);
            pg2.grabPixels();
          
                           for (int i = 0; i < w; i++)
                            for (int j = 0; j < h; j++){
                                if(pixels2[i]!=pixels[i]){
                                    System.out.println("changed="+i);
                                }
                            }

[JamesCherrill]

line 8:
the index into the arrays is i + j* w
(the arrays ate in row order)

[Clawsy]

Thanks... however it seems I get infinite values... even if on my screen nothing happenes.

[JamesCherrill]

Dunno what you mean by "infinite values", but maybe you should get things working one at a time, starting with easy data.
What I would do is to create two small bitmap images (no compression artefacts) say 16 * 8 pixels with just a couple of known pixels different, and use these to test my compare routine.
When that's working 100% I'd move on to bigger images until I was at full size. From that I'd get a relationship between image size and execution time, and have a test bed for any perfomance tuning.
I wouldn't attempt to do any of the above in the context of the full working program.

[Clawsy]

OK, thanks for advice. I will do as you said. When I get some results I will post back.

[Clawsy]

I made it! I determined the changed rectangle... Now... I don't know what delay I would have when I scan a desktop bitmap... huge?
At least one thing I need... an advice how to detect several "changed rectangles" in an image... split the image in several parts and scan each part separately? Is there an optimized scan algorithm... to make things faster? Think about a nested loop with 1310720 loops (1024*1280 pixel aria).

Thanks.

[JamesCherrill]

Just get a 1024*1280 image and try it ! It's only a million integer compares - on a multi-Gig processor.
It's such a common mistake that it has its own name: "premature optimisation".
Confirm that it really is a problem, then let's discuss optimisations.

[JamesCherrill]

Just for fun I created two int arrays 1280*1024 and compared them in a simple nested loop.
The followin code executes in 20 milliSecs on my old laptop

final int w=1280, h=1024;
int[] array1 = new int[w*h];
int[] array2 = new int[w*h];
long start = new Date().getTime();
int mismatches = 0;
int index = 0;
for (int x = 0; x< w; x++) {
	for (int y = 0; y< h; y++) {
		if (array1[index] != array2[index]) mismatches++;
		index ++;
	}
}
System.out.println(new Date().getTime() - start);

[Clawsy]

I have AMD Athlon X2 5000+ processor. At that resolution it takes me between 110 and 125 ms. And if add add tha grabbing takes me... 260ms. So the grabbing is slowing down. (I take desktop screenshots continously). However this is my code:

//bmp1 and bmp2 are to bitmap Screenshots 1280x1024... BufferedImage type.
            boolean first_x = false;
          
            int x1 = -2, x2 = -2,y1,y2;
            int minx1=-1,maxx2=-1,miny1=-1,maxy2=-1;

            int w = bmp1.getWidth();
            int h = bmp1.getHeight();
            pixels1 = new int[w * h];
            pixels2 = new int[w * h];

            long start = new Date().getTime();
            pg1 = new PixelGrabber(bmp1, 0, 0, w, h, pixels1, 0, w);
            pg2 = new PixelGrabber(bmp2, 0, 0, w, h, pixels2, 0, w);

           

            pg1.grabPixels();
            pg2.grabPixels();
            System.out.println("//start//");
            
            
            for (int i = 0; i < w; i++) {
                for (int j = 0; j < h; j++) {
                    if (pixels2[i + j * w] != pixels1[i + j * w]) {
                        if(!first_x){ minx1=i; miny1=j;  maxx2=i; maxy2=j;  first_x = true; }

                        if(minx1>i) minx1 = i;
                        if(miny1>j) miny1 = j;

                        if(maxx2<i) maxx2 = i;
                        if(maxy2<j) maxy2 = j;
                        
                       // System.out.println(i +"x"+ j);
                    }
                }
            }
           
            if(minx1==maxx2 && maxy2==miny1) System.out.println("Un singur pixel modificat");
            else{
             System.out.println("Modified part (rectangle): "+minx1+","+miny1+"<->"+maxx2+","+maxy2);
            }

            long end = new Date().getTime();
            

            System.out.println("//finish//:"+(end-start)+"ms elapsed");

[JamesCherrill]

You'll notice I replaced the i+j*w repeated calc with a simple index counter. That reduced my benchmark from 68 ms to 20. Suggest you try that.

[Clawsy]

Wow, you-re so right... reduced from 250 tp 150ms! :) (I remember numeric calculation course... care about every penny in the loop and every computation possible :) )

Do you think a good mode to obtain multiple rectangles would be to scan the image in 8 separate threads or so?

[JamesCherrill]

I don't think multiple threads will help much unless you have a quad processor! You already have GUI and socket IO running (presumably) on different threads. I'm still surprised by your lomg timings - my 20 mSec was on a 1.66 GHz core 2 laptop.

Also, in your benchmark code you grab both sets of pixels - in the real case you can just grab the latest image and pass the previous one forwards.

[JamesCherrill]

Multiple rectanges: I hate the idea of trying to find a variable number of rectanges of variable size that minimise the total area that conatins all modified pixels. Sounds like a programming nightmare, and the overheads will probably exceed he gains.
But: how about dividing the image into fixed 8x8 pixel cells and finding the cells that have changed? That's like MPEG, and really fast & easy.

boolean[][] cellChanged = new boolean[w >> 3][h >> 3];

int index = 0;
for (int x = 0; x < w; x++) {
	for (int y = 0; y < h; y++) {
		if (array1[index] != array2[index])
			cellChanged[x >> 3][y >> 3] = true;
		index++;
	}
}
	
for (int y = 0; y < (h >> 3); y++) {
	for (int x = 0; x < (w >> 3); x++) {
		System.out.print(cellChanged[x][y] ? "1" : "0");
	}
	System.out.println("");
}

Now you've also got an easy starting place for transmitting only the cells that have changed, and each cell is small enough that you can just transmit it all.

[Clawsy]

Nice idea but I sould extract each cell images from the big image no? Something like 'image.getSubimage(x1,y1,w,h);' and then send it. I done that but it is very very slow. Sorry, maybe I didn't understand well enough.

for (int y = 0; y < (h >> 3); y++) {
	for (int x = 0; x < (w >> 3); x++) {
		if(cellChanged[x][y]){
                    BufferedImage cellImg = img.getSubimage(x,y,8,8);
                   //here I send this cell to the stream.... very slow
                }
	}