Another theoretical approach would be to compress both images into JPEGs and then parse the JPEG file for the 8x8 chunks
Calculate a hash for each of the chunks and then you could compare the list of hashes for each image.
Alternatively you could break each image up into 8x8 chunks and then "naively" quantise them (take it down to 12bit or even 9 bit colour depth).
Then calculate the average and median for each of the quantised chunks and compare the lists of values for each image.
Cheers
The Cat