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
                }
	}

[JamesCherrill]

Where's the slowdown - is it in the getSubImage or in the sending? - because if it's in the sending I can't see how you would speed that up (I assume you're using one connection for all the subImages, not creating a new connection for each)
Since you have the subimage already as a string of consecutive ints (in the grabber array) maybe it would be faster to send that and reconstruct the image at the receiver?

[Clawsy]

I'm almost sure it's from sending the image... it's a delay for each send, cause thay are in separate packets and there are so many cells. And yes... I use the same connection for sending images.
As for the idea with the receiver... you mean I would send the int array and set the RGB values calculated from that array at the receiver? I have this idea before.. but I should use an ObjectOutputStream to send the array, which is quite slow. In the end... I'm sending a byte array with image infomation.. and byte array should be sent faster that int array no?
However thanks for help James, you really helped me a lot. It is only the rectangleS problem that remains... :)

[JamesCherrill]

After our discussions I realised that I could make good use of a similar thing myself, so I did a quick implementation and have the following performance info for you:
The server is a low-end desktop, 1280x1024 screen.
The client is an old laptop, WiFi g connection.
The process being bechmarked is as follows:
Client opens new socket connection to server
Client sends request to server.
Server uses Robot to get full screen image
Server sends image to client
Client closes connection.
Client displays image in scrolling window

End to end timing for that whole process is under a second, but I haven't tried to break down the individual parts.
<1 sec is more than good enough for me, and compares well with commercial remote desktop software I have used. What performance goal do you have?

[musthafa.aj]

james are sending it over internet or in lan...

because in LAN it is like what you said but in Internet its not...

then please send codes ....

[Clawsy]

Basically, my aplication works as u said. I make a socket connection at server then start listening. Then I connect the client (TCP/IP). I use robot for screenshot, then compress it using JPEG encoder and send it as byte array (I use DataOutputStream). I have also a delay of < or = to 1 second in LAN, but I make this as an Internet application where i have somewhere about 3-10 secind delay depending on the internet transfer. I should have it realtime.. and at that delay is not realtime... After I saw that, I thought how TeamViewer is made... I think it sends only the part that change.. using Windows API which is quite impossible for me. I also have a post on C# forum in which I use API to het the desktop and use GetUpdateRect() to get the rectangle chat changed in WM_PAINT event but always returns 0,0,0,0 coordonates (see http://www.daniweb.com/forums/thread253622.html).
So I use my application for internet, thats why the timing is killing me.

[JamesCherrill]

Yeah, its a lan connection - server 100 ethernet to router, client WiFi g to router. Tehre's nothing special in the code... I started by sending the image via an Object Stream, but that was nearly 3 secs. The "final" version uses ImageIO.write in png format.
I think the connection speed is the limiting factor, so obviously a 1 meg ADSL link would slow it right down!

[musthafa.aj]

yea definitely it is working speed at LAN but not in Internet.
it will take 5-15 seconds for sending screen shot with 0.5 compression level...

so took lot of image processing technique all but vain...

my conclusion is we need do compress any size of image into around 40 kb..

in TeamViewer also coming slow when it send image size as 1024 x 768.. but it is good and acceptable delay...

still i vague about how do make it fast using java..

i spent around 3 months oopps.....:(

[Clawsy]

Well, I also spend a lot of time but at the moment this is the most important project fo me so... if I make it to be fast in Java it's ideal because it works in many operating sistems. I if make it Windonws based using API, would be nice too but I would be limited to Windows, as TeamViewer is. If we send the parts of the screenshot we can use UDP, the images being smaler. It's useless just to compress the images and send it. At the moment I can send onyl a part the changes... I must get rig of the space between the "changed rectangles" or just select the rectangles... Maybe just split the screen in 4 and scan every one of them, then send a maximum number of 4 rectangles.

[musthafa.aj]

fine, then i look into your idea...
you split it 4 but the changes may be in anywhere ..within one or two or combination of anything...are you get it what i come to say?

some time your start menu occurring at left and clock going at right..

this is ambiguous again...

so still we need to discuss lot....

another thing i can traverse NAT device by forwarding port how do skip firewall and make it allow my socket connection...

you can create connection behind firewall...:-O

[Clawsy]

Hehe, a lot of strugle with firewall I had, depends on your router, forwanding.. can't say nothing now.
About the idea with spliting... you don't knwo how I get the rectangle, that's why you don't undestand my idea. I get the minimum coords and maximum coords of the rectangle. Thinks I woudl have screnn splited int 2. I get the menu rectangle at the left and another rectangle with the clock at right = 2 small images. If I don't split it I woudl have a much more bigger rectagle with the minimum x,y at the menu left-top and the maximum x,y at the clock right bottom. Hard to explain...