Clustering Algorithms for Perceptual Image Hashing

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.

Speaker Details

Vishal Monga received his B.Tech degree in electrical engineering from the Indian Institute of Technology (IIT), Guwahati in May 2001 and his M.S.E.E. degree from the University of Texas, Austin in May 2003. He is currently a PhD candidate at the University of Texas, Austin.Mr. Monga’s research interests lie broadly in the intersection of signal and image processing, data mining, and information theory. He has researched problems in color imaging – particularly halftoning and non-separable color transforms, information embedding in multimedia, and perceptual media hashing. His current research focuses on developing randomized algorithms for multimedia security and media mining.Mr. Monga received the IS&T Raymond Davis scholarship in 2004, a Texas Telecommunications Consortium (TxTec) Graduate Fellowship from the University of Texas for the year 2002-2003, and the President’s Silver medal in 2001 at IIT Guwahati. He is a member of IEEE, SPIE and IS&T.

Date:
Speakers:
Monga Vishal
Affiliation:
The University of Texas at Austin