Clustering Algorithms for Perceptual Image Hashing

Опубликовано 6 сентября 2016, 5:14

A perceptual image hash function maps an image to a short binary string based on an image's appearance to the human eye. Perceptual hashing is useful in image databases, watermarking, and content authentication in adversarial scenarios. In this talk, we decouple image hashing into feature extraction (intermediate hash) followed by data clustering (final hash). We prove that the decision version of our clustering problem is NP complete. Then, for any perceptually significant feature extractor, we present a polynomial-time clustering algorithm based on a greedy heuristic, which automatically determines the final hash length needed to satisfy a specified distortion. Based on the proposed algorithm, we develop two variations to facilitate perceptual robustness vs. fragility trade-offs. We validate the perceptual significance of our hash by testing under Stirmark attacks. Finally, we develop randomized clustering algorithms for the purposes of secure image hashing. We demonstrate the hardness of generating malicious inputs by means of experimental results.