2004 IEEE Int. Conference on Image Processing Robust Perceptual Image Hashing Using Feature Points Vishal Monga and Prof. Brian L. Evans October 25th , 2004 Embedded Signal Processing Laboratory The University of Texas at Austin Austin, TX 78712-1084 USA {vishal, bevans}@ece.utexas.edu http://signal.ece.utexas.edu 1 Introduction Hash Example Hash function: Projects value from set with large (possibly infinite) number of members to set with fixed number of (fewer) members Irreversible Provides short, simple representation of large digital message Example: sum of ASCII codes for characters in name modulo N (= 7), a prime number Database name search example
Name Hash Value Ghosh Monga Baldick Vishwanath Evans Geisler Gilbert 1 2 3 3 5 5 6 2 Introduction Perceptual Hash: Desirable Properties Perceptual robustness
Symbol Pr( H ( I ) H ( I ident )) 1 Fragility to distinct inputs Pr( H ( I ) H ( I diff )) 1 Unpredictability 1 Pr( H ( I ) v) m , v {0,1}m 2 Necessary in security applications to minimize vulnerability against malicious attacks H(I) Iident Idiff m Meaning Hash value extracted from image I Image identical in appearance to I Image clearly distinct in
appearance w.r.t I Length of hash (in bits) 3 Introduction Image Hashing: Motivation Applications Image database search and indexing Content dependent key generation for watermarking Robust image authentication: hash must tolerate incidental modifications yet be sensitive to content changes JPEG Compressed Original Image Same hash value h1 Tampered Different hash values h2 4 Related Work
Content Based Digital Signatures Extract signature from intensity statistics Intensity histograms of image blocks [Schneider et al., 1996] Mean, variance and kurtosis of intensity values extracted from image blocks [Kailasanathan et al., 2001] Preserve coarse representations Threshold low frequency DCT coefficients [Fridrich et al., 2001] Low-res wavelet sub-bands [Mihcak & Venkatesan, 2000, 2001] Relation based methods Invariant relationship between corresponding DCT coefficients in two 8 8 blocks [Lin & Chang, 2001] Interscale relationship of wavelet coefficients [Lu & Liao, 2003] 5 Perceptual Image Hashing Hashing Framework Two-stage hash algorithm Input Image I Final Hash Compression Extract visually robust Clustering of similar
feature vector feature vectors Feature vectors extracted from perceptually identical images must be close in distance metric 6 End-stopping and curvature Hypercomplex or End-Stopped Cells Cells in visual cortex that help in object recognition Respond strongly to line end-points, corners and points of high curvature End-stopping and Image Geometry, Dobbins, 1989 [Hubel et al.,1965; Dobbins, 1989] Develop filters/kernels that capture this behavior Robustness to changes in image resolution Use wavelet based approach
7 End-Stopped Wavelets [Vandergheynst et al., 2000] End-stopped wavelet basis Apply First Derivative of Gaussian (FDoG) operator to detect end-points of structures identified by Morlet wavelet Morlet wavelet along u frequency axis detects vertically oriented linear structures FDoG operator along v frequency axis applied on Morlet wavelet to detect end-points and corners L-shaped image Morlet End-stopped 8 Feature Extraction Computing Wavelet Transform Generalize end-stopped wavelet E ( x) ( FDoG)o( M ( x; )) Employ wavelet family i
( E ( ( x, y, k )) , , i Z Scale parameter = 2, i scale of the wavelet Discretize orientation range [0, ] into M intervals i.e. k = (k /M ), k = 0, 1, M - 1 End-stopped wavelet transform Wi ( x, y, ) I ( x1 , y1 ) E * ( i ( x x1 , y y1 ), ) dx1dy1 9 Feature Extraction Proposed Feature Detection Method 1. Compute wavelet transform of image I at suitably chosen scale i for several different orientations 2. Significant feature selection: Locations (x,y) in the image that are identified as candidate feature points satisfy * ' ' Wi ( x, y, ) ' max W ( x
, y , ) i ' ( x , y )N ( x , y ) 3. Avoid trivial (and fragile) features: Qualify a location as a final feature point if * max Wi ( x, y, ) T Randomization: Partition the image into N random regions using a secret key K, extract features from each random region Perceptual Quantization: Quantize features based on distribution (histogram) to enhance robustness 10 Feature Extraction Iterative Feature Extraction Algorithm 1. Extract feature vector f of length P from image I, quantize f perceptually to obtain a binary string bf1 (increase count*) 2. Remove weak image geometry: Compute 2-D order statistics (OS) filtering of I to produce Ios = OS(I;p,q,r) 3. Preserve strong image geometry: Perform low-pass linear shift
invariant (LSI) filtering on Ios to obtain Ilp 4. Repeat step 1 with Ilp to obtain bf2 5. IF (count = MaxIter) go to step 6. MaxIter, , P, and count are algorithm parameters. ELSE IF D(bf1, bf2) < go to step 6. * count = 0 to begin with ELSE set I = Ilp and go to step 1. fv(I) denotes quantized feature vector 6. Set fv(I) = bf2 D(.,.) normalized Hamming distance between its arguments 11 Feature Extraction Image Features at Algorithm Convergence Original Image
AWGN, = 10 JPEG, QF = 10 Stirmark local geometric attack 12 Feature Extraction Results: Feature Extraction Feature Vector Comparison D(fv(I), fv(Iident)) < 0.2 D(fv(I), fv(Idiff)) > 0.3 Table 1. Comparison of feature vectors Normalized Hamming distance between feature vectors of original and attacked images *Attacked images generated by Stirmark benchmark software
*Attack JPEG, QF = 10 AWGN, = 20 Contrast Enhancement Lena 0.04 0.04 0 Bridge Peppers 0.04 0.06 0.03 0.02 0.06 0.04 Gaussian Smoothing Median Filtering Scaling by 50% Rotation by 20 Rotation by 50 Cropping by 10% Cropping by 20%
0.01 0.03 0.05 0.02 0.08 0.12 0.18 0.12 0.21 0.03 0.14 0.15 0.20 0.13 0.22 0.07 0.11 0.14 0.19 0.15 0.24 13
Feature Extraction Results: Feature Extraction Attack JPEG, QF = 10 AWGN, = 20 Gaussian Smoothing Median Filtering Scaling 50% Rotation 2 degrees Cropping 10% Cropping 20% * Small object addition * Tamper with facial features Thresholding of Preserve low freq, Proposed coarse wavelet DCT coefficients feature point coefficients (Fridrich et al.) detector (Mihcak et al.) YES YES
YES YES YES YES YES YES YES YES YES YES YES YES NO NO YES NO NO NO YES YES YES YES YES
NO NO YES YES NO YES survives attack, i.e. hash was invariant *content changing manipulations, should be detected 14 Summary Highlights Invariant feature extraction
Wavelet kernels based on cells in visual cortex Any visually robust feature point detector is a good candidate to be used with the iterative algorithm Trade-offs facilitated Robustness vs. Fragility: select feature points such that T1 max Wi ( x, y, ) T2 that features are retained in several T1, T2 large enough ensures attacked versions of the image, else removed easily Robustness vs. Randomization: number of random regions Until N < Nmax, robustness largely preserved else random regions shrink to the extent that they do not contain significant chunks of image geometry 15 Questions and Comments! 16 Back up slides
17 Conclusion Conclusion & Future Work Decouple image hashing into Feature extraction and data clustering Feature point based hashing framework Iterative feature detector that preserves significant image geometry, features invariant under several attacks Trade-offs facilitated between hash algorithm goals Clustering of image features [Monga, Banerjee & Evans, 2004] Randomized clustering for secure image hashing Future Work Hashing under severe geometric attacks
Provably secure image hashing? 18 End-Stopped Wavelet Basis Morlet wavelets [Antoine et al., 1996] To detect linear (or curvilinear) structures having a specific orientation M (x) (e jk o . x e 1 |k o |2 2 )(e 1 |x|2 2 )
x (x,y) 2-D spatial co-ordinates ko (k0, k1) wave-vector of the mother wavelet Orientation control tan 1 k1 k0 End-stopped wavelet [Vandergheynst et al., 2000] Back Apply First Derivative of Gaussian (FDoG) operator to detect end-points of structures identified by Morlet wavelet 19 Feature Detection Feature Vector Extraction Randomization Partition the image into N regions using k-means segmentation extract feature points from each region
Secret key K is used to generate initial guesses for the clusters (centroids of random regions) Avoid very small regions since they would not yield robust image features Back 20 Wavelet Decomposition Back Examples of Perceptually Identical Images Original Image JPEG, QF = 10 Contrast Enhanced 10% cropping 2 degree rotation
3 degree rotation 21 Feature Detection Back Content Changing Manipulations Original image Maliciously manipulated image 22 Outline Outline Introduction: Motivation and applications Summary of digital signature methods Image statistics based approaches Relation based schemes (DCT/Wavelet) Perceptual hashing via image feature points Two stage hash algorithm: Feature extraction + clustering
End stopped wavelets for feature detection Iterative scheme for feature extraction based on preserving significant image geometry Experimental Results Incidental and malicious attacks Conclusion & Future Work 23
