Cap'n Steve~

Have you consider using a binary equivalent of the diff algorithm. I know that it exists and can be implemented highly effeciently. This will give you not only an idea of what parts of the image are identical, but which parts differ. You could modify the part of the algorithm that checks for "identical"-ness and use your own custom similarity function, which would allow you to control the results a bit more.

You might want to perform the diff in the pixel space of the images rather than the binary space of the encoding, but this should also be a relatively painless change...