As far as actually finding the regions which have changed, as ImageMagick has done for you, you can compute a pixel by pixel difference (e.g. XOR). Regions with a difference of 0 have not changed.
It is not clear from your question whether the painting itself is slow or just the transmission of the repainting data. It is also not clear what kind of encoding/decoding can be done on the other end of the transmission. Do you have to send your data as you specified or can you encode it in another way if you wish?
Your data packets have a 8 byte overhead per rectangle "(one byte for magic word, one byte for checksum, six bytes for region coordinates, two bytes for each pixel)". I take it from the two bytes for each pixel that the color depth is 16-bit? So, due to the overhead, some of the smallest rectangles you outlined actually cost you more than combining them with other rectangles and resending some data on non-updated regions.
The actual problem of finding rectangles where each has an overhead is analogous to the "Strawberry Fields" hiring problem put forth by ITA Software. The original link is dead, but here is someone's solution with problem description.
At 57600 baud, you get to send 7200 bytes per second, which would be 3600 pixels at two bytes per pixel. As a square, this is a measly 60x60. You've certainly outlined more than that in your example, and this does not count the overhead.
The refresh rate of the monitor on the receiving end also needs to be considered. If the monitor is refreshing 60 times per second and you are only able to send one 60x60 square per second, how will this look?
Things to consider:
- reduce color depth
- run length encode pixel differences per scan line
- attempt more ambitious compression per region, but watch the overhead
- send non-graphic data and let the receiver compute the graphics (e.g. in this example, send the text that has changed, the updated time, etc. and let the receiver draw the progress bar, etc.)
- abandon this insanity
