Вопрос стоит в том, что будет затратнее: сжатие N-частей и сравнение хешей сжатого, или попиксельное/хешовое сравнение разжатых байтов.

В принципе никто не мешает объединить оба подхода. Как я понимаю, для маленьких кусков изображения быстрее будет попиксельное сравнение, а вот большую картинку можно для начала поделить на много кусков, сжать их, и сравнить их хеши с хешами предыдущих.