... Maybe just split the screen in 4 and scan every one of them, then send a maximum number of 4 rectangles.
This takes us back to the previous idea of dividing into sub-rectangles (I suggested 8x8 pixels) and only sending the changed ones. Obviously you can play with the size vs number of sub-images - maybe 80 blocks 128*128 would be better. IMHO this is still the best way to reduce the number of kbytes to transfer (I would still use ImageIO/png to send the sub-images).