Image Delta Compression

Hello,

I'm new to image processing and image compression in general, and I hope
that the experts here can point me to the right direction. Here's my
problem:

Given two 32-bit images with the same dimensions, find a lossless algorithm
that will produce a delta between the two, detecting moving parts.

The algorithm needs to be fast (primary requirement) and needs to produce
a reasonably small, but not necessarily optimal delta.

I have something that works, but it's far from being fast enough. I was
tinkering with an RSYNC-like solution, and came up with a generic binary
diff implementation that, while producing very small results, takes a
relatively long time to do so.

It first takes Image A, divides it into N strings of length X each, and
calculates a checksum for each string. The checksums and offsets pointing
to the actual string are stored in a hash table.

Next, the algorithm goes through Image B byte-by-byte while keeping a
rolling checksum. For example, at position Z, the checksum represents
bytes of index Z, Z+1, ..., Z+X-1. Then a hash lookup is performed, and
if the checksum is found in the hash table an actual comparison is done
between the bytes in Image B at the current position and the bytes in
Image A at the offset that corresponds to the checksum. If there are
a reasonable number of matching bytes then the delta stream will simply
store the offset into Image A and the number of bytes that will need to
be copied when reconstructing Image B. (The algorithm is actually smart
enough to deal with multiple checksum matches and will use the longest
matching string in these cases.)

While this gives a very small delta, and handles image data that has moved
from one coordinate to another, the amount of byte-by-byte comparisons that
have to be performed make it slow enough for me to look for another
solution.

One could argue that I should simply build checksums for, say, 8x8 pixel
sized blocks in Image A, then go through Image B:

for (y=0; y<height; y++)
    for (x=0; x<width; x++)
        sum = calc_checksum(ImageB, x, y);
        if (coords = hash_lookup(sum))
            if (compare(ImageA, coords->x, coords->y, ImageB, x, y))
                store_match();

However, this implies a huge amount of time spent calculating checksums for
ImageB, and also presents various other issues, such as skipping certain
iterations of the second loop when, for example, (y=1 && x=0) and a match
has already been stored for an overlapping block, such as (y==0 && x==1).

I was wondering if anyone could point me in the right direction for solving
this problem. I'm not looking for source code (but if there's already an
implementation it's very welcome), any papers or books that deal with the
matter will do perfectly.

Thanks,

Marton Anka