Applied Science, Faculty of
Electrical and Computer Engineering, Department of
DSpace
UBCV
Malek Esmaeili, Mani
Doctor of Philosophy - PhD
University of British Columbia
Asmultimedia-sharing websites are becoming increasingly popular, content providers get more concerned about the illegal distribution of their copyrighted contents. The recent content-based multimedia fingerprinting technology has evolved as an important tool for automatically detecting illegal copies of audio, image, and video signals. Multimedia fingerprints are signatures that are extracted from an audio, image, or video signal as a compact identifier of the signal. Therefore fingerprints should have enough discriminating ability to identify a multimedia object among others. At the same time they should be robust to modifications a multimedia signal might be subjected, such as compression, cropping, format change, scaling, and other signal processing operations. Robustness requires the fingerprints of a signal to only depend on the signals perceptual content and not on its format, size, quality, etc. This thesis proposes copy detection systems for audio and video signals and addresses the robustness as well as the discrimination ability of these systems. We first address audio fingerprinting and propose an algorithm that can detect small snippets of audio signals. Simulation results show that, the extracted fingerprints are robust to audio modifications including pitch shift and tempo change. For severe modifications that existing algorithms have poor detection rates (around 20%), our proposed algorithm yields detection rates above 80%. We then address video fingerprinting and propose an algorithm that extracts robust and discriminant binary fingerprints. Simulation results show that the proposed algorithm is faster and more accurate than the state-of-the-art with a high true positive rate of over 97% and a low false positive rate below 1%. Another challenge in multimedia fingerprinting is fingerprint retrieval, i.e. searching a huge fingerprint database (millions of fingerprints), for an accurate match for a query fingerprint in a fast fashion. We propose a fast and accurate Nearest Neighbour (NN) search algorithm for binary fingerprints (Hamming space). Tested on a very large database of 80 million images, we showed that the proposed algorithm is about 3 times faster than the state-of-the-art while at the same time it is 10 times more accurate.
Multimedia copy detection by Mani Malek Esmaeili B.Sc., University of Tehran, 2004 M.Sc., University of Tehran, 2007 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Doctor of Philosophy in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering) The University of British Columbia (Vancouver) June 2013 c© Mani Malek Esmaeili, 2013 Abstract As multimedia-sharing websites are becoming increasingly popular, content providers get more concerned about the illegal distribution of their copyrighted contents. The recent content-based multimedia fingerprinting technology has evolved as an im- portant tool for automatically detecting illegal copies of audio, image, and video signals. Multimedia fingerprints are signatures that are extracted from an audio, image, or video signal as a compact identifier of the signal. Therefore fingerprints should have enough discriminating ability to identify a multimedia object among others. At the same time they should be robust to modifications a multimedia signal might be subjected, such as compression, cropping, format change, scaling, and other signal processing operations. Robustness requires the fingerprints of a signal to only depend on the signals perceptual content and not on its format, size, quality, etc. This thesis proposes copy detection systems for audio and video signals and addresses the robustness as well as the discrimination ability of these systems. We first address audio fingerprinting and propose an algorithm that can detect small snippets of audio signals. Simulation results show that, the extracted finger- prints are robust to audio modifications including pitch shift and tempo change. For severe modifications that existing algorithms have poor detection rates (around 20%), our proposed algorithm yields detection rates above 80%. We then address video fingerprinting and propose an algorithm that extracts robust and discriminant binary fingerprints. Simulation results show that the pro- posed algorithm is faster and more accurate than the state-of-the-art with a high true positive rate of over 97% and a low false positive rate below 1%. Another challenge in multimedia fingerprinting is fingerprint retrieval, i.e. search- ii ing a huge fingerprint database (millions of fingerprints), for an accurate match for a query fingerprint in a fast fashion. We propose a fast and accurate Nearest Neigh- bour (NN) search algorithm for binary fingerprints (Hamming space). Tested on a very large database of 80 million images, we showed that the proposed algorithm is about 3 times faster than the state-of-the-art while at the same time it is 10 times more accurate. iii Preface This thesis presents the research conducted by Mani Malek Esmaeili, in collabo- ration with Prof. Rabab K. Ward and Dr. Mehrdad Fatourechi. Below is the list of the scientific papers by Mani Malek Esmaeili that were published (or submit- ted) through the course of his studies as a Doctor of Philosophy (PHD) candidate at University of British Columbia (UBC). J1 M. Malekesmaeili, R. K. Ward,“A local fingerprinting approach for audio copy detection,” submitted, May. 2013. J2 M. Malekesmaeili, R. K. Ward, M. Fatourechi, “A Fast Approximate Nearest Neighbor Search Algorithm in the Hamming Space,” IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI), Vol. 34, pp. 2481– 2488, Dec. 2012. J3 M. Fatourechi, X. Lv, M. Malek Esmaeili, Z. J. Wang, and R. K. Ward, Image and Video Copy Detection Using Content-Based Fingerprinting, in Multimedia Image and Video Processing, 2nd ed., edited by Ling Guan , Yifeng He and Sun-Yuan Kung, pp. 459–487, CRC Press 2012. J4 M. Malekesmaeili, M. Fatourechi, R. K. Ward, “A Robust and Fast Video Copy Detection System Using Content-Based Fingerprinting,” IEEE Trans- actions on Information Forensics and Security, Vol. 6., pp. 213–226, Mar. 2011 C1 M. Malekesmaeili, R. K. Ward, “A novel local audio fingerprinting algo- rithm,” IEEE International Workshop on Multimedia Signal Processing (MMSP),pp. 136–140, Sep. 2012. iv C2 M. Malekesmaeili, R. K. Ward, M. Fatourechi, “Fast matching for video/au- dio fingerprinting algorithms,” IEEE International Workshop on Information Forensics and Security (WIFS), Nov. 2011. C3 M. Malekesmaeili, R. K. Ward, “Robust Video Hashing Based on Tempo- rally Informative Representative Images,” IEEE International Conference on Consumer Electronics (ICCE), pp. 179–180, Las Vegas,January 2010. C4 M. Malekesmaeili, M. Fatourechi, R. K. Ward, “Video Copy Detection Us- ing Temporally Informative Representative Images,” IEEE International Con- ference on Machine Learning and Applications (ICMLA), pp. 69–74, Miami, Florida, Dec 2009. J1, C1: Mani Malek Esmaeili (primary author and the main contributor of the papers) proposed the algorithms, implemented them, and performed the eval- uations. Prof. Ward provided technical feedback as well as editorial comments throughout writing of these papers. J2, C2: Mani Malekesmaeili (the primary author and the main contributor of the papers) proposed the algorithms, implemented them, and performed the eval- uations. Prof. Ward provided extensive technical and editorial feedback during throughout writing of these papers. Data used for parts of the evaluations of the paper were gathered by Raymond Huang under the supervision of Dr. Fatourechi. J3: Mani Malek Esmaeili and Xudong Lv provided writings for most of the book chapter. Dr. Fatourechi supervised the writing of the text and wrote some parts of it. Prof. Ward and Dr. Wang provided editorial comments on the paper. J4, C3, C4: Mani Malekesmaeili (the primary author and the main contribu- tor of the papers) proposed the algorithms, implemented them, and performed the evaluations. Prof. Ward provided extensive feedback during the writing process as well as the revision process of the paper. Dr. Fatourechi provided comments on the experimental results as well as editorial comments. v Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Multimedia fingerprinting . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Extracting fingerprints . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Types of fingerprints . . . . . . . . . . . . . . . . . . . . 3 1.2.2 Properties of fingerprints . . . . . . . . . . . . . . . . . . 5 1.2.3 Attacks on multimedia signals . . . . . . . . . . . . . . . 6 1.3 Fingerprint matching . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Motivations and contributions . . . . . . . . . . . . . . . . . . . 8 1.4.1 Audio fingerprinting . . . . . . . . . . . . . . . . . . . . 9 1.4.2 Video fingerprinting . . . . . . . . . . . . . . . . . . . . 10 1.4.3 Fingerprint retrieval . . . . . . . . . . . . . . . . . . . . 11 1.5 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 vi 2 Audio Fingerprinting . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Audio representation: Time-chroma image . . . . . . . . . . . . . 19 2.3.1 Time-chroma image . . . . . . . . . . . . . . . . . . . . 19 2.3.2 The parameters of the time-chroma image . . . . . . . . . 22 2.4 Fingerprint extraction . . . . . . . . . . . . . . . . . . . . . . . . 24 2.4.1 Algorithm 1 . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4.2 Algorithm 2 . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4.3 Evaluation of the proposed fingerprinting algorithms . . . 30 2.5 Song identification . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5.1 Algorithm 3 . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5.2 Performance evaluation . . . . . . . . . . . . . . . . . . . 40 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3 Video Fingerprinting . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.3 Extracting robust and discriminant fingerprints . . . . . . . . . . 47 3.3.1 Spatio-temporal fingerprinting using 3D-Discrete Cosine Transform (DCT) . . . . . . . . . . . . . . . . . . . . . . 48 3.3.2 Spatio-temporal fingerprinting using Temporally Informa- tive Representative Image (TIRI) . . . . . . . . . . . . . . 49 3.4 Fast matching of fingerprints . . . . . . . . . . . . . . . . . . . . 51 3.4.1 Inverted file-based similarity search . . . . . . . . . . . . 54 3.4.2 Cluster-based similarity search . . . . . . . . . . . . . . . 58 3.5 Performance evaluation . . . . . . . . . . . . . . . . . . . . . . . 62 3.5.1 Performance evaluation of the fingerprint extraction algo- rithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.5.2 Performance evaluation of the similarity search algorithms 69 3.6 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 vii 4 Fingerprint Matching . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.3 Fast copy detection for audio and video signals . . . . . . . . . . 81 4.3.1 Windowing scheme and the matching algorithm . . . . . . 82 4.3.2 Evaluation of the proposed windowing scheme . . . . . . 89 4.4 Approximate nearest neighbour search . . . . . . . . . . . . . . . 93 4.4.1 Initialization . . . . . . . . . . . . . . . . . . . . . . . . 95 4.4.2 Error Weighted Hashing (EWH) . . . . . . . . . . . . . . 97 4.4.3 Analytical study of the algorithm . . . . . . . . . . . . . 98 4.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.5.1 Performance evaluation on synthetic databases . . . . . . 111 4.5.2 Performance evaluation on real-world databases . . . . . . 115 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . 121 5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 viii List of Tables Table 2.1 Average percentage of correct song association. . . . . . . . . 36 Table 3.1 Attack parameter values used in the evaluation of the proposed algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Table 3.2 Comparing TIRI-DCT with 3D-DCT when exhaustive search is used. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Table 3.3 Hash extraction time (in mS) for different segment sizes . . . . 68 Table 3.4 Comparison of the performance of exhaustive search (Exh.), in- verted file-based similarity search (Inv.), and cluster-based sim- ilarity search (Clu.). . . . . . . . . . . . . . . . . . . . . . . . 69 Table 3.5 Performance of the system after adding the post-processing mod- ule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 ix List of Figures Figure 2.1 The process of generating the time-chroma representation of an audio signal. . . . . . . . . . . . . . . . . . . . . . . . . . 20 Figure 2.2 Logarithmically spaced filters used to create the time-chroma representation. . . . . . . . . . . . . . . . . . . . . . . . . . 22 Figure 2.3 Percentage of the matching local maxima (left) and the corre- lation score (right) for different values of l and lo. . . . . . . . 23 Figure 2.4 Percentage of the matching local maxima (left) and the corre- lation score (right) for different values of nch, noct , and f0. . . 24 Figure 2.5 The overall system view of the local fingerprint extraction al- gorithms proposed. . . . . . . . . . . . . . . . . . . . . . . . 25 Figure 2.6 The feature extraction phase of the Algorithm 1. . . . . . . . 27 Figure 2.7 The patterns used to classify the feature points in Algorithm 2 29 Figure 2.8 The percentage of correctly matched points (TPR) (a),(b) and the percentage of correctly scaled (matching) points (c),(d) as the tempo of the song is varied. . . . . . . . . . . . . . . . . 32 Figure 2.9 The percentage of correctly matched points (TPR) (a),(b) and the percentage of the correctly scaled (matching) points (c),(d) as the pitch of the song is varied. . . . . . . . . . . . . . . . . 33 Figure 2.10 The percentage of correctly matched points (TPR) (a),(b) and the percentage of correctly scaled (matching) points (c),(d) as the speed of the song is varied. . . . . . . . . . . . . . . . . . 34 x Figure 2.11 The percentage of correctly matched points (TPR) (a) and the percentage of correctly scaled matching points (b) as the amount of noise in the query is varied. . . . . . . . . . . . . . . . . . 35 Figure 2.12 The ID’s of the detected songs and their corresponding time in- tervals (results of the pre-processing step) for a query contain- ing (a) tempo changed (−20%) and (b) pitch shifted (−2/12 octave) copies of the songs in a database. . . . . . . . . . . . 38 Figure 2.13 Localization and parameter estimation . . . . . . . . . . . . . 40 Figure 2.14 Song identification rate (a), scale identification rate (b), and pitch identification rate (c) for different tempo change values. 41 Figure 2.15 Song identification rate (a), scale identification rate (b), and pitch identification rate (c) for different pitch shift values. . . . 42 Figure 2.16 Song identification rate (a), scale identification rate (b), and pitch identification rate (c) for different speed-up factors. . . . 43 Figure 3.1 The schematic of a complete fingerprinting system. . . . . . . 45 Figure 3.2 Pre-processing applied to the videos before fingerprinting. . . 48 Figure 3.3 The schematic of the 3D-DCT algorithm proposed in [1]. . . . 49 Figure 3.4 Frames (a) 61, (b) 75, and (c) 90 of the sequence COASTGUARD- QCIF [2] and the resulting TIRIs with different weighting func- tions: (d) wk = 1 (constant), (e) wk = k (linear), (f) wk = 1.2k (exponential). . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Figure 3.5 The schematic of the TIRI-DCT algorithm. . . . . . . . . . . . 52 Figure 3.6 TIRI-DCT algorithm. . . . . . . . . . . . . . . . . . . . . . . 53 Figure 3.7 Range of (non-DC) DCT coefficients corresponding to different (normalized) frequencies. . . . . . . . . . . . . . . . . . . . . 54 Figure 3.8 (a) Dividing the fingerprint into words, (b) Sample inverted file for the fingerprint database. . . . . . . . . . . . . . . . . . . 55 Figure 3.9 Histogram of the number of exactly matching words between two similar fingerprints (a) 3D-DCT, (b) TIRI-DCT. . . . . . . 56 Figure 3.10 (a) Clustering the fingerprints for TIRI-DCT, (b) Expanding a cluster head to compare it with a fingerprint. . . . . . . . . . . 60 xi Figure 3.11 Comparing the runtime of the clustering-based search method with that of the inverted file-based method for different values of m (L = 128, th = 16) (a) Approximate percentage of fin- gerprints examined with each attempt (b) Probability of failing the first attempt. . . . . . . . . . . . . . . . . . . . . . . . . . 61 Figure 3.12 (a) Distribution of the Hamming distance between fingerprints corresponding to similar (copied) and different video sequences. (b) Receiver Operating Characteristic (ROC) curve for TIRI- DCT for w = 4 : 32 and γ = 0.65, (c) Maximum F0.5 for 0 < γ ≤ 1 and w = 16, (d) Maximum F0.5 for w = 4 : 4 : 32 and γ = 0.65. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Figure 3.13 False Positive Rate (FPR) versus threshold for w = 4 : 32 (TIRI- DCT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Figure 3.14 F-score of 3D-DCT and TIRI DCT for different attack parame- ters from Table 3.1: (a) Noise addition, (b) Change in bright- ness, (c) Rotation, (d) Time shift, (e) Spatial shift, (f) Frame loss. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Figure 3.15 Error vs. search time for different search algorithms applied on fingerprints derived by TIRI-DCT. . . . . . . . . . . . . . . 70 Figure 3.16 F-score for different keys for different parameter values when the video is attacked by (a) frame loss (b) time shift. . . . . . 73 Figure 3.17 Amount of change in the average True Positive Rate (TPR), FPR, and F0.5 when the security is added to the system. . . . . 74 Figure 4.1 Conventional windowing strategy for (a) database videos (50% overlap), (b) query videos (50% overlap). The proposed win- dowing strategy for (c) database videos video (no overlap) (d) query videos (maximum overlap). . . . . . . . . . . . . . . . 84 xii Figure 4.2 An illustration of an output of a window-based fingerprinting algorithm when the input video contains repeated or slowly changing scenes (a) True time correspondence between the query video (bottom) and the database video (top) (b) The found matches between different time windows using the fin- gerprinting algorithm. . . . . . . . . . . . . . . . . . . . . . 85 Figure 4.3 Schematic of a multimedia copy detection system based on the proposed windowing scheme. . . . . . . . . . . . . . . . . . 86 Figure 4.4 An example of the Matching State Machine (MSM). The state machine is terminated when the last query fingerprint is exam- ined. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Figure 4.5 Performance results when the overlap changes, (a) Detection rate, (b) Detection jitter, (c) Retrieval time. . . . . . . . . . . 91 Figure 4.6 Performance results for different Bit Error Rate (BER)s, (a) De- tection rate, (b) Detection jitter, (c) Retrieval time. . . . . . . 92 Figure 4.7 Detected time location for video segments of a randomly cropped 40-second snippet in a mash-up. . . . . . . . . . . . . . . . . 93 Figure 4.8 The process of adding a database fingerprint to the index table. 96 Figure 4.9 A demonstration of Error Weighted Hashing (EWH) with e= 2: How the hash vectors (here qk1 ) are processed. The process continues for all query hash vectors qk2 ,qk3 . . .qkn . . . . . . . 99 Figure 4.10 Probability of having an r-bit difference between correspond- ing hash vectors of two fingerprints f and q with a normalized Hamming distance of τ (shown as labels), m = 20, and l = 1024.100 Figure 4.11 Comparison of the experimental and the estimated Cumulative Distribution Function (CDF) of s for l = 1024, m = 10, n = 20, and e = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Figure 4.12 Two [similar] fingerprints divided into sub-vectors of m bits (different bits are shaded). . . . . . . . . . . . . . . . . . . . 103 Figure 4.13 The value of the error εe,m,τ of the average score s with respect to the ideal similarity 1− τ for different values of e. . . . . . . 105 Figure 4.14 The value of the threshold s0 for 1≤ e≤ 4 when Rre j = 2%. . 108 xiii Figure 4.15 (a)-(c) Minimum TPR as a function of n, m, and e, respectively. (d) Minimum TPR , the optimum value of m, and the number of accesses to the table (#) as e changes. The default values are n = 20, τdet = 0.2, τre j = 0.3, and Rre j = 2%. . . . . . . . . . 109 Figure 4.16 Comparing the performance of different search algorithms for 10 ≤ n ≤ 40, m = 10, l = 1024, and NND = 0.2 (a) Average False Rejection Rate (FRR) (b) Average number of candidates in the list (c) Time taken to generate the candidate list (d) Total retrieval time. . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Figure 4.17 Comparing the performances of different search algorithms for 8 ≤ m ≤ 15, n = 20, l = 1024, and NND = 0.2 (a) Average false rejection rate (FRR) (b) Average number of candidates returned for a query (c) Time taken to generate the candidate list (d) Total retrieval time. . . . . . . . . . . . . . . . . . . . 114 Figure 4.18 Comparing the performances of different search algorithms for 0<NND< 0.4, m= 10, n= 20, and l = 1024 (a) Average FRR (b) Average number of candidates returned for a query. . . . . 115 Figure 4.19 The effects of the database size on the performance of Lo- cality Sensitive Hashing (LSH) , Randomized Beacon Guided Search (RBGS) , and EWH , when l = 1024, m = 10, n = 20, and NND = 0.2 (a) Average FRR (b) Average number of can- didates returned for a query. . . . . . . . . . . . . . . . . . . 116 Figure 4.20 Comparing the performance of the algorithms for 8≤m≤ 12, n = 20, and l = 640 (a) Retrieval error rate (FRR+FPR) (b) Average total retrieval time for a query. . . . . . . . . . . . . 117 Figure 4.21 Comparing the performance of the algorithms for 10≤ n≤ 40, m = 10, and l = 336 (a) Retrieval error rate (FRR + FPR) (b) Relative retrieval speed of EWH (e = 2), LSH and the exhaus- tive search. . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 xiv Glossary TIRI Temporally Informative Representative Image DFT Discrete Fourier Transform DCT Discrete Cosine Transform DWT Discrete Wavelet Transform SIFT Scale-invariant feature transform,a local image feature extraction technique proposed by David. G. Low, 1999. STFT Short Time Fourier Transform MFCC Mel Frequency Cepstral Coefficient PCP Pitch Class Profile MSM Matching State Machine NN Nearest Neighbour K-NN k Nearest Neighbours NND Nearest Neighbour Distance LSH Locality Sensitive Hashing LSHP Locality Sensitive Hashing based on Permutations EWH Error Weighted Hashing xv BGS Beacon Guided Search RBGS Randomized Beacon Guided Search FPR False Positive Rate FRR False Rejection Rate TPR True Positive Rate BER Bit Error Rate PDF Probability Distribution Function CDF Cumulative Distribution Function HAS Human Auditory System RAM Random Access Memory SNR Signal to Noise Ratio LPF Low Pass Filter QCIF Quarter Common Intermediate Format RBT Random Basis Transform ROC Receiver Operating Characteristic xvi Acknowledgements I would not have been able to make it to this point without the support of my su- pervisor Prof. Rabab K. Ward. Her patience, generous help, and wise suggestions helped me a lot during my PhD studies with her. Other than her scientific guid- ance throughout my research work, she taught me a lot about technical writing and technical presentation skills. I would also like to thank anonymous reviewers of my research papers for their comments which helped me improve the quality of my works. Thanks to Raymond Huang for creating the video dataset used in this work. Also thanks to NSERC Canada which supported most of this work through Grant STPGP 365164-08. True friends are very hard to come by; I am happy that I have two of them sitting right next to me in the ISPL lab. Thank you Simon Fauvel and Tanaya Guha. The current economical and political situation of Iran has forced many Iranian citizens to leave their beloved country. I, amongst them, immigrated to Canada. Canada is now my home away from home, and I am very happy that I immigrated to this wonderful country with its rich multicultural basis. However, I still miss my parents, my only grandmother, and my old friends. This painful separation is part of the life of all the immigrants. Here I would like to thank Liu Bei (Reza estekaan), Guan Yu (Soroush pash- maloo), and Pang Tong (Askar tala) for being such close friends to me even though distance have parted us for ages. Many thanks to my beloved parents for their never ending love that always filled my heart with energy. Mom and Dad, I love you forever and ever, and I wish we will have the chance to live close to each other again. xvii Last but not least, I thank my beautiful, lovely Mona, for her emotional support as a wife, her sincere suggestions as a friend, and her technical advices as a col- league throughout my PhD and through the hard times of switching my research topic and supervisor at UBC. And I start this thesis in the name of God ... xviii Chapter 1 Introduction 1.1 Multimedia fingerprinting Multimedia has become an integral part of digital entertainment and social net- working websites such as Facebook, Google+, and MySpace. Multimedia sharing web-sites such as YouTube allow easy sharing of multimedia contents such as mu- sic, images, or videos regardless of their originality. The widespread use of these web-sites has made copyright protection of digital media an issue of great concern for content providers. Thus an effective multimedia copy detection system has become a necessity for all content distributors. To know whether or not a specific multimedia object (video, audio, or image) or parts of it have been copied, a multimedia copy detection system is used. Differ- ent technologies have been sought for developing such a system. The two widely known approaches are fingerprinting and watermarking. Watermarking requires adding some information (code) to the content of the multimedia signal (video, audio, or image). The code is not added to the signal as a side information (meta-data) but embedded in the content of the signal. Thus removing a watermark is not easy and requires changing or attacking the content of the multimedia object. The code is later used to track and trace the content. Watermark may contain information about the identity of the owner, the identity of the distributor, IP address of the device downloading the multimedia asset, etc. The embedding process should be robust against the common modifications a digital 1 media signal may have been subjected to before being shared. Some examples of these operations are changes in the frame-size or frame-rate of a video signal, temporal cropping of an audio or video signal, changes in the pitch or tempo of an audio signal, rotation of an image, added noise, etc. A problem with the watermarking approach is that embedding extra informa- tion in a signal, can reduce its quality. Moreover, watermarking is done using extra software and hardware and requires a set of compatible devices both on the distributor and the consumer side, which is not always feasible. Another impor- tant drawback of watermarking which limits its use is that it is not applicable to contents that have already been distributed and have many existing copies shared on-line. For these reasons, watermarking is not a viable option for copy detection systems in on-line multimedia sharing websites. Content-based multimedia fingerprinting, also known as robust hashing, has been introduced as an alternative to watermarking [3]. Its aim is to identify a multimedia signal solely based on its content and without embedding any extra in- formation. Content-based fingerprinting is done by extracting features, also known as fingerprints, from the perceptual content of the multimedia signal. Fingerprints are in fact compact signatures that are used to identify the content of a multimedia signal regardless of its form of presentation or any content-preserving distortions that may have affected it. A multimedia fingerprinting algorithm is designed so that two perceptually different (audio, image, or video) contents result in different fingerprints while the original content and its copy result in similar fingerprints. The alternative name, robust hashing, may suggest similarities between a fin- gerprint and a hash value as referred to by conventional file hashing algorithms. However, there is a major difference between a fingerprint and such a hash value. A hash value of a file (which can be a multimedia signal as well), may completely change when a single bit in the file is changed [4]. However, as mentioned above, fingerprints of a multimedia object and its modified version should remain simi- lar. This property of fingerprints is referred to as robustness. While robustness is a requirement for content-based fingerprints, fingerprints should be able to distin- guish between multimedia objects that are perceptually different. This property of fingerprints is referred to as discrimination ability. A multimedia copy detection system that is based on fingerprinting consists of 2 two main phases: 1) extracting fingerprints from the query multimedia content as well as from the original contents in the given database and 2) searching the set of the fingerprints extracted from the original objects in the database for possible matches of the fingerprints extracted from the query object. The first phase is responsible for extracting robust and discriminant fingerprints and should meet certain requirements that will be discussed in Section 1.2. Usually the fingerprints of the original contents in the database are extracted in advance and stored as a fingerprint database. Thus for copy detection, first the fingerprints of the query multimedia object are extracted, and then a search is run on the fingerprint database to find possible matches for the extracted query fingerprints. Multimedia databases are usually very large, resulting in fingerprint databases that contain billions of fingerprints. This fact makes the matching process the computational bottleneck of the copy detection system. We will discuss the matching process in more details in Section 1.3. In Section 1.4 we explain the motivation behind this research work and identify our contributions. The organization of the thesis is summarized in Section 1.5. 1.2 Extracting fingerprints A fingerprint is a vector whose elements can be integer, real, or binary values depending on the fingerprinting algorithm. As mentioned, fingerprints should be robust to modifications or attacks that do not change the content of a multimedia signal. We will explain more about such modifications later in this section. Before discussing the attacks we will provide more details about the different types of fingerprints and their properties. 1.2.1 Types of fingerprints Regardless of the type of the multimedia content, i.e. video, audio, or image, fingerprints can be classified as direct domain fingerprints, transform domain fin- gerprints, or mixed domain fingerprints. The direct domain fingerprinting methods extract content-based signatures form the domain the signal is perceived in. For audio signals, the direct domain is the time domain. Every audio signal is a set of [voltage] values that change over time. The number of the elements in the set is 3 the number of audio channels. Each element in the set is a time series. Finger- prints extracted to represent the tempo variations of a song are examples of direct domain fingerprints for audio signals. For images, the direct domain is the spa- tial domain. Each image is a collection of pixel values in the two dimensional space. Fingerprints extracted from the color distribution of an image are exam- ples of direct domain fingerprints for images. For videos, the direct domain is the spatio-temporal domain. A video is a collection of pixel values in the two dimen- sional space while the value of each pixel changes over time. Fingerprints extracted to represent the temporal characteristics of shots in a video are examples of direct domain fingerprints for videos. One can apply a transform function on the direct domain representation of a signal and represent the signal in an alternative domain. Transform domain fin- gerprinting methods extract fingerprints from such transformed domains. Discrete Fourier Transform (DFT), Discrete Cosine Transform (DCT), and Discrete Wavelet Transform (DWT) are the transform functions most widely used in the literature. For example, using the DFT, an image can be represented as a collection of fre- quency coefficients. Fingerprints formed by the low-frequency DCT coefficients of images are examples of such fingerprints. Mixed domain fingerprinting algo- rithms use both direct and transform domains. Example of such algorithms are fingerprints that are extracted from the spectrogram of an audio signal where the frequency contents of the audio are presented over time. From another perspective, the fingerprints can be classified as global or local. Global fingerprints are extracted from the whole signal representation (regardless of the domain) while the local fingerprints are extracted from a local neighbour- hood of the signal. For example, an image fingerprinting algorithm that extracts global fingerprints considers all the pixel values of the image when extracting the fingerprints, while a local image fingerprinting algorithm only considers the values of the pixels that are around certain points in the image when extracting the fin- gerprints. Since only parts of the signal are used in local fingerprinting algorithms, multiple fingerprints should to be extracted so that the algorithm can detect the in- tegrity of the query signal. For applications where the integrity of the multimedia is very important, global fingerprints can provide better detection results. For ap- plications involving multimedia contents that have been cropped or partly copied, 4 local fingerprinting is the only viable option. For video signals, fingerprints can be local or global in each dimension. For example, they can be global across the spatial dimension and local along the time dimension. Local fingerprints can be extracted either from specifically chosen points in the representation domain of the signal called salient points, or based on a determin- istic or randomly defined pattern. Examples of the former are fingerprints that are extracted from the corners of the objects in an image. Examples of the latter are window-based fingerprinting algorithms for video or audio signals, where finger- prints are extracted from a specific time-window of the signal, we denote these algorithms as window-based algorithms. Salient points result in very robust fin- gerprints but they require an extra pre-processing step in the fingerprint extraction phase to detect these points. They also require an extra post-processing step in the matching phase to aggregate the detection results from individual detections. Win- dow based algorithms do not require these extra steps but are less robust in general. To increase their robustness, overlapping windows are usually employed. 1.2.2 Properties of fingerprints Fingerprints should be robust to content-preserving distortions that can affect mul- timedia signals. They should also be discriminant, easy to compute, compact, and easy to search for in a large database. In some applications such as copyright pro- tection, fingerprints should also be secure. Robustness of a fingerprint requires the fingerprint to change as little as pos- sible when the multimedia signal is subjected to content-preserving distortions, i.e., distortions that do not affect the perceptual content of the multimedia asset. Content-preserving distortions (attacks) are changes that are made to the multi- media unintentionally or intentionally by users of multimedia-sharing websites. These changes can include format change, signal processing operations, change in brightness/contrast of video, change in pitch or tempo of audio, added noise, rota- tion, cropping, logo insertion, compression, etc. We will discuss these attacks in more details in Section 1.2.3. The fingerprints should also be discriminant, to ensure that two perceptually different multimedia signals have distinguishable fingerprints. There is a trade- 5 off between robustness and discrimination. As a fingerprinting algorithm becomes more robust to distortions, it becomes less sensitive to changes in the content, i.e., it will have less discrimination ability. The fingerprints should also be easy to compute. Specifically, for on-line ap- plications, a fingerprinting algorithm should be able to extract the fingerprints as the video or audio is being uploaded. A computationally demanding algorithm is not suitable for on-line applications for which thousands of videos need to be examined simultaneously in order to find possible copyright infringements. For the same reason, fingerprints should also be compact, i.e. represented by short vectors. If a fingerprint is not compact, finding a match for it in a very large database can become a time-consuming process. It should be noted that the com- pactness of a fingerprint does not guarantee that it can be easily matched or found in a large database. The fingerprints should be designed in a way that allows uti- lization of fast approximate search algorithms. For some applications, the fingerprinting system should also be secure, pre- venting an adversary from tampering with the system. If a fingerprinting system is not secure, an intelligent adversary may be able to modify an illegal copy without introducing distinguishable artefacts and have it approved (as being original) by the copy detection system. Security is specifically important for high profile copy right protection applications. The more secure a multimedia fingerprinting system is, the more difficult it is for an adversary to generate similar fingerprints for differ- ent videos and thus deceive the copy-detection system. For indexing applications, however, security of a fingerprinting system does not pose a problem. 1.2.3 Attacks on multimedia signals Multimedia signals can be modified before being copied and shared. These modifi- cations can happen as a result of cropping, compression, mixing different contents, multimedia editing software, etc. We denote these modifications as attacks regard- less of being intentional or not. We briefly pointed out some of these attacks in the previous section. Here we categorize them based on the type of media (audio, image, or video) and provide more details. The attacks on audio signals can be categorized as temporal attacks, frequency 6 attacks, or signal processing artefacts. Tempo change and time shift are exam- ples of temporal attacks. Pitch shift and equalization are examples of frequency attacks. Signal processing artefacts include compression, noise, down sampling, etc. Conventionally many audio copy detection algorithms have only targeted sig- nal processing artefacts1 . However, with widespread availability of audio editing software other types of attacks such as tempo change and pitch shift are becoming serious threats to accurate copy detection. The attacks on images can be signal processing artefacts or geometric attacks. Examples of the former are image blurring, edge sharpening, compression, and added noise. Examples of the latter are rotation, spatial shift, cropping, and scal- ing2. The attacks on video signals can be categorized as temporal, spatial, or spatio- temporal attacks. Frame dropping, frame rate change, slow/fast motion, time shift, and time cropping are examples of temporal attacks. In these attacks the temporal axis the video signal is modified and individual frames are not affected. For ex- ample, in the time shift attack the video is shifted along its time axis, which can inversely affect the performance of window-based fingerprinting systems. Spatial attacks are those attacks that are applied on individual frames of a video signal and thus include geometric attacks as well as other signal processing operations as mentioned above for images. Spatio-temporal attacks are those that affect both time and space at the same time. Caption overlays or video overlays are examples of such attacks. Please note that any combination of the mentioned attacks are possible for all types of multimedia signals. Such combined attacks are usually referred to as composite attacks. 1.3 Fingerprint matching As mentioned in the first section, there are two main computing engines in a multi- media copy detection system: the fingerprinting engine and the matching (search) 1Please note that all the attacks on audio signals can be performed using signal processing op- erations and this is actually how audio editing softwares simulate these attacks. The distinction we make here is meant for better understanding of the issues in each category of the audio attacks. 2These attacks can happen through re-capturing of an image, however, most of these attacks can be simulated by signal processing operations. The distinction we make here is meant for better understanding of the issues in each category of the image attacks. 7 engine. The fingerprinting engine is responsible for finding robust but unique-to- the-content fingerprints while the matching engine is responsible for searching for a match for the extracted query fingerprints in the database of original fingerprints. The fingerprint database is generated by applying the fingerprinting engine to all contents in the original multimedia database. The robustness property of the fin- gerprints requires that the fingerprints of an attacked signal remain similar to those extracted from the original signal. It, however, does not require them to be exactly the same. This implies that the distance between a query fingerprint and its true match in the database should be small but not necessarily zero. Thus the matching engine of a multimedia copy detection system is a Nearest Neighbour (NN) search algorithm. There is no accurate solution known to the problem of NN search in high dimensional spaces other than the exhaustive search which is O(n), with n being the number of fingerprints in the database. An exhaustive search on a very large fingerprint database puts too much com- putational load on the copy detection system and renders the system impractical for real time applications. To overcome this barrier, one can resort to faster ap- proximate solutions. Not many research papers have addressed the problem of NN search for multimedia fingerprinting systems. Existing fingerprinting systems have either ignored this problem or have adopted general purpose approximate solutions for fast retrievals that were already known. Fast and accurate matching is a criti- cal issue in implementing a practical system, therefore devising fast and accurate search methods that are optimized for fingerprints is deeply needed. 1.4 Motivations and contributions In this thesis we target all the aspects of a multimedia copy detection system in- cluding both fingerprint extraction and fingerprint matching. Our focus is on video and audio signals. We start the thesis by proposing a novel audio fingerprinting al- gorithm. We then propose a video fingerprinting algorithm and develop a complete copy detection system. Finally, we target the problem of fingerprint matching and propose fast and accurate searching methods for fingerprint retrieval. Below we briefly explain the motivation behind each work and briefly list our contributions in each area. 8 1.4.1 Audio fingerprinting Audio signals are one dimensional signals in the time domain. It is not easy to extract robust fingerprints from the time domain representation of an audio signal. Usually a mixed domain (time domain + transform domain) representation is used. Most existing mixed domain representations, such as the spectrogram of the audio signal, are robust to signal processing attacks such as compression or noise. How- ever, they are not robust to time and frequency scales (mainly tempo change and pitch shift), thus most of the existing applications of audio fingerprinting are not able to detect pitch-shifted or tempo-changed audio signals. These attacks are be- coming popular in multimedia sharing websites like YouTube. The other problem is that while some of the shared content contain a whole song, a large number of them contain partial segments of a song or even a mixture of short snippets of dif- ferent songs known as mash-ups. Existing pitch and tempo invariant fingerprinting algorithms require a long enough portion of an audio signal to conduct an accurate detection. We were therefore motivated to find a copy detection solution that is robust to pitch shift and tempo change attacks and at the same time can perform the detection on small mashed-up song snippets. Our contributions in the area of audio fingerprinting are as follows: • We developed a novel mixed domain representation for audio signals called the time-chroma image. This image provides a platform for extracting audio fingerprints robust to pitch shifts and tempo changes. • We proposed a local audio fingerprinting algorithm that extracts local finger- prints from the time-chroma image. Our choice of local fingerprints enables us to detect short snippets of audio signals. Tested on a database 260 songs collected by our research group at UBC, the proposed algorithm is shown to outperform the state-of-the-art by a great extent. For example, for severe pitch shift and tempo change attacks for which existing algorithms can only detect about 20% of the fingerprints, our algorithm is able to detect above 80% of them with a slightly increased computational cost. • We proposed a song identification and localization algorithm that uses the proposed fingerprints to localize the copied song segments in a given query. 9 The proposed song identification also estimates the amount of pitch shift or tempo change the copy was subjected to. 1.4.2 Video fingerprinting A major problem with video fingerprinting algorithms is the excessive amount of information that exists in a video signal. Videos are three dimensional signals and extracting a compact robust fingerprint that is fast to compute is not easy. Therefore, we focused on reducing the fingerprint computation time and finger- print retrieval time, while considering robustness and discrimination abilities. Our contributions in the area of video fingerprinting are summarized as follows: • We devised a new compact representation for video signals. A strength point of the proposed representation is that it has only two dimensions and allows faster computation of fingerprints. The representation called Temporally In- formative Representative Image (TIRI), is an image that represents a short segment of consecutive frames in the video and contains temporal as well as spatial information about the video segment. • Based on TIRI, we proposed a novel robust video fingerprinting algorithm. The resulting fingerprints are very compact (126 bits) and are shown to be robust to many modifications on video signals. Tested on a database of 200 videos, the proposed fingerprinting algorithm is shown to be able to achieve a True Positive Rate (TPR) of about 98% and a low False Positive Rate (FPR) of 1%. • We also proposed a fast search algorithm specifically designed and optimized for the proposed fingerprints. Tested on the same database, it is shown that the proposed search algorithm decreases the retrieval time by an order of magnitude with a negligible reduction in accuracy. • We also addressed the security of the proposed copy detection system and developed a secure version of the proposed fingerprints. Tested on the same database, we showed that security is achieved with less than 1% reduction in the TPR of the system. 10 By combining all the developed features, to the best of our knowledge, we proposed the first complete video copy detection system that addresses all the requirements of a fingerprinting system. 1.4.3 Fingerprint retrieval We noticed that the problem of fingerprint retrieval has not yet received the at- tention it deserves in existing copy detection systems. Most research papers on multimedia copy detection have been tested on medium sized datasets without any concern about retrieval speed. However, for a practical copy detection application where the multimedia database contains millions of objects, there is no value to an approach that neglects the importance of fast retrievals. Motivated by this short- coming in the literature, we tried to find effective solutions that allow fast retrievals for fingerprints. We also worked on effective retrieval processes, i.e. search algo- rithms. The general purpose NN search algorithms such as the Locality Sensitive Hashing (LSH) family have been optimised for the Euclidean space. However, re- cently many fingerprinting algorithms have migrated to binary fingerprints and the problem of NN search for binary vectors has not been adequately addressed in the literature. Thus, we were motivated to develop a fast approximate NN search for binary data. Our contributions in the area of fingerprint retrieval are listed below: • We proposed a windowing scheme and a search strategy for time-based mul- timedia signals, i.e. video and audio signals. The proposed scheme is general and any fingerprinting algorithm that extracts fingerprints from overlapping windows of a video3 or an audio can use this scheme. Tested on a database of 1000 videos, it is shown that using our proposed scheme, speed-ups up to three orders of magnitude compared to exhaustive search are achieved. • We proposed a novel NN search algorithm for the Hamming (i.e. binary) space. The proposed algorithm called Error Weighted Hashing (EWH), facil- itates the real-time application of a fingerprinting system when the database contains tens of millions of fingerprints. Tested on a database of 1000 videos and a database of 80 million images, our proposed EWH is shown to be about 3A window in a video is collection of consecutive frames. 11 10 times faster than the popular LSH family of algorithms while providing the same retrieval accuracy, or 15 times more accurate with the same speed4. Our algorithm achieves this performance at the cost of an extra memory re- quirement compared to the LSH family of algorithms. Our algorithm also works well even for the case when the nearest neighbour distance is large5; for which LSH fails. 1.5 Organization Every chapter starts with a properly explained problem description followed by a review of the related background. Our proposed solution for the described prob- lem is explained next followed by the evaluation and comparison of the proposed solution against the state of the art. A summary of each chapter is given in the final section. More details about the organization of each chapter are listed below: • In Chapter 2 the problem of audio copy detection is addressed. Two audio fingerprint extraction algorithms robust to various modifications including severe pitch shift and tempo changes are proposed. A novel song identifi- cation algorithm that uses the proposed fingerprints to identify and localize song snippets is also introduced. The proposed system is evaluated using a database of over 200 songs in presence of severe pitch shift and tempo change attacks. The results are presented and the proposed system is com- pared to the state-of-the-art. • In Chapter 3 a video copy detection system is proposed. The system can be used for video indexing and copyright applications. The system com- prises of a novel video fingerprint extraction algorithm and a novel fast fin- gerprint matching algorithm. The proposed system is tested on a dataset of 200 videos in the presence of different types of distortions such as noise, changes in brightness/contrast, frame loss, shift, rotation and time shift. The results are presented and the proposed system is compared to the state-of- the-art. A secure version of the system is also proposed and evaluated at the 4Accuracy can be traded off for speed by changing the parameters of the algorithm 5Large nearest neighbour distances can occur in many copy detection systems. 12 end of the chapter. • In Chapter 4 a general windowing scheme and its accompanied matching strategy are proposed. The proposed scheme can be applied to any window- based local fingerprinting algorithm. The scheme is then compared to the conventional approach. An approximate NN search algorithm is also proposed for fast matching of binary fingerprints. The proposed algorithm can be used for any retrieval application that uses binary descriptors. The proposed NN search is evaluated on a video database with more than 1000 videos and on an image database with about 80 million images. The results are presented and the proposed algorithm is compared to the state-of-the-art. • In Chapter 5 we conclude this thesis and provide a summary of our contribu- tions. We also discuss about the future work and present potential opportuni- ties for making improvements and/or extensions to the algorithms proposed in this thesis. 13 Chapter 2 Audio Fingerprinting 2.1 Problem description Audio copy detection has become a building block of many multimedia sharing websites. Whether users are searching for their favourite songs or whether content providers are looking for illegally distributed copies of their copyrighted songs, an audio copy detection system should be able to retrieve the sought-after songs, even when the songs have been subjected to content preserving modifications. These modifications could be compression, noise addition, frequency changes, time scale changes, and mash-ups. • Compression effects result from the use of audio coding schemes and differ- ent quantization levels. • Noise may be due to background voices recorded through a microphone, faulty song copying systems, etc. • The most common frequency modification is the pitch shift, where pitches of a song are moved up or down without affecting the time characteristics of the signal. A pitch shift results from a change in the scale of the frequency axis (frequencies are shifted in the octave space). For example, with a 100% pitch shift, an audio signal is played at one octave higher, with the same speed. 14 • Time scale attacks include speed change and tempo change. When the speed of a song is modified both its tempo and its pitch are changed. A tempo change, on the other hand only increases or decreases the pace and has no effect on the pitches. In other words, the song is scaled along time without any change in its pitches. • Mash-up is another class of modifications where short snippets of different songs are put together to form a single mashed-up song. Most of the proposed solutions for audio copy detection are based on content- based fingerprinting [5], [6]. Audio, image, and video fingerprinting have recently become a popular research topic due to the great interest from industry. Audio fin- gerprints refer to compact signatures (extracted from an audio signal) that can dis- tinguish between different songs based on their musical content. Conventionally, audio fingerprinting research, has mainly focused on developing algorithms that are robust to effects such as noise, compression, equalization, echo, etc [7]. Due to the present availability of powerful audio editing software, copy detection should now be extended beyond these traditionally studied effects [8] to other challenging ones such as pitch shift and tempo change. New audio fingerprinting algorithms should be able to cope with these effects as well as the conventional ones. A practical audio fingerprinting algorithm should be robust to all content-preserving modifications including noise, compression effects, pitch shifts, and tempo changes. Moreover, to be able to deal with song mash-ups and other demands involving short snippets of audio, the audio fingerprinting algorithm should be based on local fin- gerprints (i.e. local features) of the audio signal. Local features are signatures that represent a short segment of an audio signal (regardless of the contents of the rest of the signal). In the literature, a lot of research on local feature extraction for images and videos have been reported and have resulted in powerful and effective algorithms. However, not many studies have considered the use of local features for audio signals. In this chapter, two local fingerprinting algorithms are proposed for music sig- nals. The fact that the proposed fingerprints are local, enables us to detect small snippets of a song mashed up with other songs. These two proposed algorithms are based on a new time-frequency representation of audio signals which we denote 15 as the time-chroma image. Chroma, also known as the Pitch Class Profile (PCP), was originally proposed in [9]. It is the set of all pitches that are perceived by the human ear to have similar musical notes. In terms of frequency, a chroma is a set of frequencies that are apart by one or more octaves. A chroma set is usually repre- sented by a value such as its main pitch or the sum of the energies of all its pitches. It follows from the definition of the chroma that shifting all the pitches of an au- dio signal by any multiple of an octave does not change the chroma values of the signal. In other words, chroma is a single octave representation of the frequency (pitch) content of an audio signal (at a certain instance of time). The time-chroma image is a two dimensional representation of an audio signal that shows its chroma values at different time instances. Shifting the pitch of the audio by one or more octaves has no effect on the time-chroma image. Sifting the pitches of the audio by a fraction of an octave, circularly shifts the time-chroma image along the chroma axis. Generally, if C is the width of the image along the chroma axis and the pixel I(t,c) of the time-chroma image has a certain value, after a pitch shift of ∆p, the pixel at I[t,mod(c+∆p,C)] will have this value1. If the tempo of the audio signal is changed, its time-chroma image scales accordingly along the time axis. Since both of our proposed algorithms extract local fingerprints from the time-chroma image, their fingerprints are thus robust against pitch shift attacks. Other com- monly studied audio representations of audio signals such as the Bark scale [10] and the Mel scale [11] are non-linearly distorted after a pitch shift attack. Thus, the original representation of the audio signal cannot be retrieved from its distorted version. However, for the the time-chroma image a shift along the chroma axis can generate the original representation. This makes the time-chroma image a suitable platform for designing pitch invariant audio detection algorithms. The rest of this chapter is organized as follows: in the next section some of the related work is reviewed. In Section 2.3 we introduce the proposed time chroma image. In Section 2.4, two local audio fingerprinting methods that use the time- chroma image are proposed. The second algorithm is more complicated, but results in extremely better performance compared to the state-of-the-art. The algorithms are both evaluated in Section 2.4.3. In Section 2.5, an audio copy detection system 1Here, and mod is the modulo operator. 16 is proposed. The system can precisely locate the query audio in a given music database using the proposed fingerprinting algorithms. The system can further estimate the value of any pitch shift as well as the value of any tempo change that might have affected a copied song. The proposed copy detection system is also evaluated through a series of severe audio attacks in Section 2.5.2. The chapter is summarized in Section 2.6. 2.2 Related work Probably the most well-known publicly available audio fingerprinting algorithm is Shazam [12]. Shazam, is based on local audio fingerprints. Shazam uses the peaks (maxima) observed in the spectrogram of an audio signal as the local feature points of a song. Feature descriptors (fingerprints) are then generated from the attributes of pairs of these points. The frequency coordinates of the points in each pair along with the difference between their time coordinates form a compact fingerprint for each pair. These fingerprints are shown to be highly robust to audio compression, foreground noises, and other types of noise. However, they are not robust to tempo changes or pitch shifts. An audio copy detection algorithm based on features globally extracted from the spectrogram of the audio has been proposed by Haitsma et al. [13]. Because the human auditory system (HAS) operates on approximately logarithmic bands, in [13] the frequency axis of the spectrogram is transformed to a subjectively de- veloped scale called the Bark scale. The sign of the energy difference between adjacent bands (in time and frequency) generate the fingerprints in [13]. The pro- posed fingerprints are proven to be very robust to compression. As in [12], they are not robust to large tempo changes and pitch shifts and they can only tolerate very small amounts of such modifications (up to around 4%). The generated fingerprints are also very long (8 kbits). Miller et al. [14] have proposed a fast and accurate search algorithm to facilitate the search for these fingerprints. Two time-based fingerprinting algorithms have been proposed by in [15]. Both algorithms derive a periodicity score from a given audio stream to generate finger- prints. In [15] a spectrogram-based fingerprinting algorithm, using Mel Frequency Cepstral Coefficient (MFCC) is also proposed. The time-based periodicity score is 17 shown to have promising results for speech signals. However, as shown in [15], for music signals the MFCC based approach outperforms the periodicity based ap- proaches. All the methods are tested in presence of noise as well as very small pitch shifts (up to 2%) and time scales (up to 6%). A wavelet based audio fingerprinting algorithm called Waveprint was proposed by Baluja et al. [16]. Waveprint divides the logarithmically scaled spectrogram (based on the Bark scale) into smaller spectral images along time. The top t- wavelet coefficients of such images are then binary embedded to generate inter- mediate fingerprints. The final fingerprints are the Min-Hash [17] values of these intermediate fingerprints. For fast retrieval, an LSH-based [18] algorithm is ap- plied to find the closest matches for the given query fingerprints. The proposed system is tested in the presence of different distortions including speed changes up to 2% and tempo changes up to 10%. Zhu et al. [19] have proposed an algorithm based on the scale invariant feature transform (SIFT) [20]. Because SIFT extracts features from images, Zhu et al. ap- plied SIFT on the logarithmically scaled spectrogram of the audio signal to extract audio fingerprints. As SIFT extracts local features, it helps in detecting random short snippets of audio, which is not possible with global features. Applying SIFT on the logarithmically scaled spectrogram also provides robustness against pitch shift attacks, therefore, making the algorithm in [19] a better option compared to Shazam. Serra et al. [21] have proposed a global audio feature extraction algorithm based on a two dimensional representation of the audio signal which we call the time-chroma image. The time-chroma represents the chroma content [9] of an audio signal over time. Through extensive experiments Serra et al. have shown that time-chroma representation of an audio signal is a promising platform for de- signing audio detection algorithms. However, the use of global features does not extend this method to mash-up attacks. We will discuss the time-chroma represen- tation later in the next section. A thorough review of different audio fingerprinting algorithms can be found in [22]. 18 2.3 Audio representation: Time-chroma image It is not efficient to extract fingerprints from the time representation of a song, i.e. its waveform. Fingerprints are usually extracted from some type of time-frequency representation of the audio signal. Spectrogram is used by Wang in [12] to extract audio features. Haitsma and Kalker have used time-Bark scale for extracting au- dio fingerprints [13]. Serra et al. in [21] have used another representation, which we denote as time-chroma image. Because of the many properties the chroma scale has, we have used this representation as well. However, the time-chroma representation we propose here, is different from that is proposed in [21], although conceptually the same. In Section 2.3.1 we explain our algorithm for extracting the time-chroma image. In Section 2.3.2 we explore the parameters of the algorithm for optimizing the image for our copy detection task. Fig. 2.1 demonstrates a sys- tem view of the time-chroma image generation phase. In the following section we explain how this image is generated. 2.3.1 Time-chroma image The chroma as defined in [9] and [21], is the set of all pitches (frequencies) that are apart by a whole number of octaves2. An octave is the interval between two pitches whose frequencies have a ratio of 2 or 1/2. Before explaining the concept of chroma in more details, we clarify what is pitch and what is its relation to frequency. Pitch is a perceptual concept repre- senting a frequency. More accurately, ”pitch is defined as the frequency of a sine wave that is matched to the target sound by human listeners” [23]. Although there are infinite number of frequencies per octave, when analysing audio signals only a limited number of pitches are considered per octave. Each pitch can be considered as the perceptual value of a musical note. When a pitch is shifted up by one oc- tave its corresponding frequency doubles thus pitch has a logarithmic relation with frequency. To encapsulate all of these properties and to be able to mathematically repre- sent the pitches, we assume p0 as the lowest pitch considered in the system and 2This is actually the definition of a pitch class, all the pitches in the same pitch class have the same chroma. 19 Figure 2.1: The process of generating the time-chroma representation of an audio signal. associate it with the frequency f0. Any pitch, pi in the system, is then associated with the frequency 2 im f0, where m is the number of pitches that are considered per octave of an audio signal3. Having a clear notion for pitches, the definition of chroma becomes straight forward. As defined, a chroma set is the set of all pitches apart by one or more octave, e.g. {p0, pm, p2m, p3m, . . .} is the chroma set that includes all the frequen- cies, { f0,2 f0,22 f0,23 f0, . . .}. It follows from the definition that in a system that considers m pitches per octave, there are m distinct chroma sets for an audio signal. To represent the chroma content of a song, a value is assigned to each chroma set. To assign a value to a chroma set, one calculates the sum of the energies of all the pitches (of the song) that belong to that chroma set. The time-chroma image is a plot of the chroma distribution of an audio signal 3In other words, pi ∼ 2 im f0. 20 over time. With the above definition of chroma, an audio signal can be repre- sented in an octave independent way, i.e. all the pitches are summarized in one octave. This representation is robust against many attacks including low pass fil- tering, high pass filtering, equalization, etc. However, (as our studies show) it is not discriminant enough, i.e., two different songs can have very similar time-chroma images. To address this problem, we introduce a new concept denoted by chroman. Chroman is the set of all pitches that are apart by n octaves. For example, p0 belongs to the chroman set {p0, pmn, p2mn, p3mn, . . .} that includes the frequencies { f0,2n f0,22n f0,23n f0, . . .}. Therefore, chroma1 is a special case of chroman that is equivalent to the conventional notion of chroma. As in the case of the conventional chroma, a chroman set is represented by the sum of the energies of all the pitches it includes. It can now be seen that if all the pitches in an audio signal are shifted by ∆p pitches, the values assigned to the chroma sets are circularly shifted by ∆p causing a circular shift along the chroma axis in the time-chroma image. In the proposed time-chroma image, the chroman distribution of the signal is plotted along time. In other words, instead of representing the song with a single octave as with the conventional time-chroma representation, we represent it with n octaves. By increasing n, one can achieve better discrimination ability. However, increasing n also increases the sensitivity of the resulting time-chroma image to changes in the audio signal rendering a less robust representation. In Section 2.3.2, we explore the effects of using different values for n and m. To calculate the value of a chroman set, the energy of every pitch should be calculated. Pitch energies are calculated from the spectrogram of the audio signal. The spectrogram is generated using the Short Time Fourier Transform (STFT) on windows of length l of the audio signal. The windows overlap by lo. Before ap- plying STFT, each window is weighted using a Hanning window. The phase values of the STFT coefficients are discarded as the Human Auditory System (HAS) is rel- atively insensitive to phase [13]. Frequencies below f0 (corresponding to p0, the lowest pitch considered in a system) are discarded4 . This is consistent with the fact that HAS is not sensitive to very low frequencies. We will explore the values of l, lo and f0 in Section 2.3.2. 4Both p0 and f0 are parameters of the system as well as m and n. 21 50 100 150 200 250 300 350 400 0 0.5 1 Freq. (Hz.) W ei gh t Figure 2.2: Logarithmically spaced filters used to create the time-chroma rep- resentation. To extract the energy of a certain pitch, a narrow-band filter is used. To deal with small variations in the pitch frequencies from different musical instruments, a flat-top narrow-band filter is used (we used a cosine-based filter in our experi- ments). In our set-up, m logarithmically scaled filters are used per octave of the frequency axis (starting from f0). Fig. 2.2 shows an example of the filters when 12 pitches (m = 12) are extracted per octave. For example, the value of the chroma1 set that includes the pitch of frequency 75Hz is calculated by summing the energy of the signal at the frequency bands centred around {37.5Hz,75Hz,150Hz, . . .} (plotted by solid lines in Fig. 2.2). 2.3.2 The parameters of the time-chroma image In this section, appropriate values for the time-chroma image parameters are es- timated. Since many local audio feature points (including the ones that will be proposed) are derived from local maxima of the time-frequency representation of the audio, we choose parameter values that result in the most robust local maxima. First we study the STFT parameters l and lo. To study the effect of these parame- ters, we generate a mash-up of 20 different songs and create 5 attacked versions of this mash-up: 2 pitch-shifted versions (±2/12 octaves5), 2 tempo changed versions (1.1±3 times) and 1 noisy version (SNR= 40db). For each set of parameter values, we find the local maxima in the spectrogram of the original mash-up and its 5 at- tacked copies. Then, for each local maximum in the original mash-up, we check the corresponding point in every attacked version. If this point is a local maximum 5There are 12 pitches (keys) on a regular piano per octave, shifting the pitches by 2/12 is equiv- alent to playing a song with an offset of 2 keys. 22 00.2 0.4 0.4 0.6 0.8 1 0.2 0.4 0.6 0.8 1 l lo % o f m at ch es 0.1 0.2 0.3 0.4 0.5 0.4 0.6 0.8 1 0.92 0.94 0.96 0.98 l lo % C or re la tio n Figure 2.3: Percentage of the matching local maxima (left) and the correla- tion score (right) for different values of l and lo. of the attacked version, we count it as a match. The original local maximum and its matching local maximum from the attacked version are called a matching pair. Fig. 2.3 (left), shows the percentage of such local maxima averaged over all the attacks. To carry a more qualitative evaluation of robustness, we calculate the correla- tion between patches centred around matching local maxima. To do so, for each matching pair, we select one rectangular patch around the original local maximum and another one around the matching local maximum from the attacked version. Both patches have the same height (size along the chroma axes). However, the sizes of the patches along the temporal axis (the width) is set according to the amount of tempo change in the attacked version. Since two patches can have dif- ferent widths, we find the correlation between the vectors of their low frequency discrete cosine transform (DCT) coefficients. We then calculate the average of the correlation values over all the matching pairs. Fig. 2.3 (right) shows the correlation score averaged over all the attacks for different values of l and lo. The values l = 0.1 fs and lo = 0.75l result in the best correlation score, and also have a high percentage of matching local maxima. Please note that we used the spectrogram and not the time-chroma representation to evaluate the values of l and lo. This means that the values of n, m and f0 had no effect on the selection of l and lo. Now we explore the appropriate values for n (the number of octaves 23 0 50 100 1 2 3 4 0.65 0.7 0.75 0.8 n ch n oct % o f m at ch es f0=40Hz f0=60Hz f0=80Hz f0=100Hz 0 50 100 1 2 3 4 0.94 0.96 0.98 1 n ch n oct Co rre la tio n f0=40Hz f0=60Hz f0=80Hz f0=100Hz Figure 2.4: Percentage of the matching local maxima (left) and the correla- tion score (right) for different values of nch, noct , and f0. used to define a chroman), m (the number of pitches per octave), and f0 (the cut-off frequency). We set l and lo to 0.1 fs and 0.75l, and generate the proposed time- chroma representation for different values of n, m and f0. To evaluate each set of parameter values, we follow the same procedure adopted for l and lo. Fig. 2.4 plots the percentage of robust local maxima of the time-chroma image for different parameter values. It also plots the average correlation between the patches of the original and the attacked audio (patches around such maxima). The values m = 72, n = 4, and f0 = 80Hz result in the best correlation score. For these values, over 66% of the local maxima of the original audio were detected as the local maxima of the distorted versions. 2.4 Fingerprint extraction Many audio fingerprinting algorithms have used the local maxima of different types of time-frequency representations of audio signals as robust feature points for ex- tracting fingerprints. For example, Shazam [12] uses the relative time and fre- quency information of pairs of local maxima as local fingerprints for audio copy detection. Fingerprints based on the frequency of the local maxima are robust to background noise, quantization effects, filtering, and compression but not to pitch shift and tempo change. It is not uncommon, however, for users of on-line multi- 24 Figure 2.5: The overall system view of the local fingerprint extraction algo- rithms proposed. media sharing websites to vary the pitch or tempo of a song before sharing it. In this section we introduce two algorithms for extracting local fingerprints6 from the time-chroma image. Both fingerprints are time-scale invariant by design. This means that they are robust to tempo change attacks. Also, the fact that they are local makes them robust to shifts in the time-chroma image. A shift along the time axis can be caused by cropping an audio signal. A shift along the chroma axis represents a frequency scale that can be caused by pitch shift or speed change. Fig. 2.5, shows a general system view of both algorithms. The details of each algorithm 6Locality of a fingerprint means that it is extracted based on the content of the audio in a small region around a specific point called the key point 25 will be discussed in the following two subsections. 2.4.1 Algorithm 1 Local maxima have been used as stable key points in all types of time frequency representations [13], [12]. Therefore, we start by considering the local maxima of the time-chroma image of the audio signal. However, we treat these points as candidates and then only select those who satisfy certain conditions (explained below). For a local maximum (candidate) we look for its neighbouring local maxima that are within a certain range of the its chroma value. Only the local maxima that belong to different time instants from that of the candidate are considered. For each candidate we select the k nearest maxima for further processing. We found experimentally that k = 10 results in accurate detections. We first compare the energies of the selected maxima to that of the candidate. If the candidate’s energy is larger than the majority (> 50%) of its neighbours’, we consider it as a feature point otherwise we discard it. For a selected feature point, the average temporal distance between the point and its neighbouring local maxima is assigned as its scale. The scale for each feature is used to adaptively extract a fingerprint (feature descriptor) for it. Fig. 2.6 demonstrates the above process. Time and chroma of a feature point along with its assigned scale are stored as its attributes for detection purposes. A fingerprint is extracted on the basis that it describes (ideally uniquely) the time-chroma neighbourhood around the feature point it corresponds to. First a rectangular patch centred around the feature point is selected. The patch height is m (one octave along the chroma axis). Along the time axis, the patch extends equally on both sides of the feature point by the scale assigned to the corresponding feature point. If the tempo of an audio signal is changed (stretched or squeezed), the scales assigned to its feature points are changed accordingly, providing robustness against tempo changes. The fingerprint is generated by extracting the q× r low frequency DCT coefficients of the patch (excluding the DC value). We used q = 12 and r = 12 in our set-up. The extracted coefficients are scaled and translated to result in a zero-mean unit-variance vector (of size 143). This vector is used as the 26 Figure 2.6: The feature extraction phase of the Algorithm 1. fingerprint of the feature point. We will evaluate this algorithm on a song database in Section 2.4.3. 2.4.2 Algorithm 2 Similar to Algorithm 1, we start with the local maxima of the time-chroma image as the candidate feature points. We then examine the time-chroma pattern around each candidate point. To do this, for each point, we extract multiple rectangular patches (from the time-chroma image) centred around each point. All these patches have the same height, i.e. they do not change size along the chroma axis, and they only vary along the time axis. We start with a patch with a small time width and gradually increase the time width to extract new patches. We use about 30 patches to cover a time range of about 1s to 4s around each candidate point. A candidate point is called stable over a certain range of time widths, if all the patches whose widths are in that time range, have similar patterns. By similar, we mean that if the patches are scaled to the same time width, they will look similar. An equivalent way to find patches is to vary the scale of the time axis of the time 27 chroma image and extract patches of the same width. From now on, we call the time width of a patch its time scale. We will quantify the similarity between two patches of different scales by defining some standard representative patterns, i.e. a dictionary of patterns. The dictionary contains c representative patterns. We will explain how we generate this dictionary shortly. In our algorithm, two patches are said to be similar if they are mapped to the same pattern in the dictionary. If most of the patches around a candidate feature point are similar to a specific pattern in the dictionary, the point is selected as a feature point. Each feature point is then assigned a scale value and a type value. The scale value is the time scale of the patch that is most similar to the pattern in the dictionary, and the type is the pattern itself (represented by a numeric value). Time and chroma coordinates of a feature point along with its assigned type and scale values are stored as attributes of the feature point for detection purposes. The c patterns in the dictionary are representative patches generated from the original songs in the database. To generate these patterns, a rectangular patch of fixed size centred around each local maximum of the time-chroma image (of each song in the database) is extracted. The patches are windows of size wt ×wp where wt is the width along the time axis and wp is the height along the chroma axis. We have experimentally found that wt = 2 seconds and wp = m (one octave) give good results. A standard k-means algorithm is then applied to classify the extracted patches into c classes. Fig. 2.7 shows the representative patterns when c= 10 (used in our set-up). We generated patterns from different subsets of songs (subsets as small as 50 out of 250 songs), and we found that for a specific value of c, the generated representative patterns remain almost identical regardless of the number of songs in the database. This finding shows that to get accurate detections, one does not have to update the patterns as new songs are added to the database. To examine a patch of a certain scale against a representative pattern, the corre- lation of the patch and the pattern is calculated. The patterns in the dictionary have a fixed height and width, but patches extracted around the candidate points can vary in their width along the temporal axis (depending on the scale). Therefore, to compare a patch and a pattern, we use the correlation of their low-frequency DCT coefficients as the similarity metric. The pattern that results in the highest correlation with the patch is selected (at each time scale). If for a candidate point, 28 Figure 2.7: The patterns used to classify the feature points in Algorithm 2 a certain pattern is selected in more than 50% of the scales, the point is considered stable and is selected as a feature point. The pattern is assigned as the type of the feature point and the scale that resulted in the highest correlation is assigned as its scale. In our set-up, on average, about 20 candidate points are extracted for each second of a song, and about 40% of them are selected as feature points. To generate a fingerprint from a feature point, we follow a procedure similar to what was proposed in Algorithm 1. First, a rectangular patch of size s×m cen- tred around the feature point (where s is the scale assigned to the feature point) is selected. Fingerprints are generated by extracting q× r low frequency DCT coef- ficients from each patch (excluding the DC value). We used q = 12 and r = 12 in our set-up. Each fingerprint is scaled and translated to result in a vector of zero mean and unit variance (of size 143). If the tempo of an audio signal is changed, the time-chroma image is stretched or squeezed along the time axis. This affects the scales assigned to the feature points accordingly, but has no effect on the contents of the patches around them, thus providing tempo invariance. Also, if a song is pitch-shifted, the time-chroma 29 image circularly shifts along the chroma axis. This moves the feature points verti- cally (along with the whole image), thus has no effect on the content of the patches around them and provides pitch invariance. In practice, because of the cut-off fre- quency f0, pitches of low frequencies (around f0) may be added or lost as a result of a pitch shift attack. This reduces the robustness to pitch shifts. 2.4.3 Evaluation of the proposed fingerprinting algorithms Robustness of the proposed fingerprints In this section we evaluate the proposed local audio fingerprinting methods. We compare them with the widely adopted audio copy detection algorithm Shazam, and to another algorithm which we call AudioSIFT. AudioSIFT is the same as the algorithm proposed in [19]. It, however, applies Scale-invariant feature trans- form (SIFT) on the more robust time-chroma image of the audio signal instead of the logarithmically scaled spectrogram (as done in [19]). The initial experiments showed that using our time-chroma image resulted in better detection performance than the logarithmically scaled spectrogram in [19]. To carry out the comparisons, we selected a total of 260 songs from different genres. For each song we generated multiple attacked versions by varying the pitch, tempo, speed, and noise level (a total of about 50 attacked versions for each song). In this subsection we only eval- uate the robustness of the proposed feature points. In the next section we evaluate their uniqueness. For each algorithm, the extracted feature points from the original songs and from the attacked versions are compared. Let X be the set of fingerprints extracted from the original song and Y be the set of fingerprints extracted from an attacked version. A fingerprint x ∈ X is matched to y ∈ Y if it is closer to y than any other fingerprint in X by a factor of α . To measure the distance between two fingerprints, we measure the angle between them7. Mathematically speaking, x is matched to y if: arccos(yT x)≤ α arccos(yT x′) ,∀x′ ∈ X −{x} (2.1) 7The matching criteria of Shazam [12] is different. 30 We set α = 0.6 as in [19] and [20]. Any two matched fingerprints are further analysed for correct correspondence between the attributes of the feature points they correspond to. As mentioned in Section 2.4.2, these attributes are time, chroma, scale, and type. For each feature point of the original song, the time and chroma coordinates of the corresponding feature point in each of the attacked version are projected (knowing the attack parameters). If there exist discrepancies between the projected coordinates and the actual coordinates of the matching feature point, a false positive is declared. Otherwise a correct match is declared if the matched points also have the same type value (this is only checked for Algorithm 2). Fig. 2.8 (a) and (b) show the percentages of the correct matches (TPR) as the tempo of the song changes. It can be seen that the proposed feature points are more robust than the state-of-the-art by a great extent. Fig. 2.8 (c) and (d) show the percentages of the correct matches that had correct scale ratios, i.e. the ratio of the scale values of the matched points is equal to the ratio of the tempos (tempo of the original song and that of the attacked version). Since Shazam does not assign a scale to the extracted fingerprints it is not included in these comparisons. We will see in Section 2.5 that the scales assigned to the feature point contribute positively to song identification, localization, and estimation of the attack parameters. This implies that correct scale assignment plays an important role in copy detection. As Fig. 2.8 (c) and (d) show, for Algorithm 2, the majority of the matches are assigned the correct scale. It can be seen that AudioSIFT is not very robust to tempo changes. This is because of the fact that the original SIFT algorithm can only handle uniform scaling (scaling that preserves the aspect ratio). If the image is scaled only along the horizontal axis (as it is the case for the tempo change attack), SIFT is not able to extract robust fingerprints from the feature points. Figures 2.9 (a) and (b) show the percentage of correct matches as the song is subjected to varying amounts of pitch shifts. It can be seen from the figures that the proposed methods have high detection rates that are almost independent of the pitch shift value. Fig. 2.9 (c) and (d) show the percentage of correct matches that had correct scale ratios. Under the pitch shift attack the temporal scale of the song does not change, which means that for a correct scale assignment the ratio of the scales of the matching feature points should be equal to one. It can be seen from the figures that for the proposed method, about 90% of the correct matches had 31 1.2 1.4 1.7 2.1 2.5 3 0 20 40 60 80 100 tempo change (increase) (a) Co rre ct m at ch es (% ) Algorithm 2 Algorithm 1 Audio SIFT SHAZAM 0.8 0.7 0.6 0.5 0.4 0.3 0 20 40 60 80 100 tempo change (decrease) (b) Co rre ct m at ch es (% ) Algorithm 2 Algorithm 1 Audio SIFT SHAZAM 1.2 1.4 1.7 2.1 2.5 3 0 20 40 60 80 100 tempo change (increase) (c) Co rre ct s ca le s (% ) Algorithm 2 Algorithm 1 Audio SIFT 0.8 0.7 0.6 0.5 0.4 0.3 0 20 40 60 80 100 tempo change (decrease) (d) Co rre ct s ca le s (% ) Algorithm 2 Algorithm 1 Audio SIFT Figure 2.8: The percentage of correctly matched points (TPR) (a),(b) and the percentage of correctly scaled (matching) points (c),(d) as the tempo of the song is varied. correct scale ratios regardless of the pitch shift value. Fig. 2.10 (a) and (b) show the results as the speed of the audio is changed. A change in speed results is changes in both tempo and pitch of the song. To be more precise, if the time is scaled by a the tempo increases by 1/a times and the frequency axis is scaled by 1/a, i.e. the pitches and the chroma are shifted down by log2 a of an octave. Fig. 2.10 (c) and (d) show the percentage of the correct matches that had correct ratios. It can be seen from the figures that Algorithm 2 greatly outperforms the other methods. Fig. 2.11 (a) plots the results when the query is a noisy version of the original 32 1.1 1.1 1.2 1.3 1.3 1.4 0 20 40 60 80 100 pitch shift (increase) (a) Co rre ct m at ch es (% ) Algorithm 2 Algorithm 1 Audio SIFT SHAZAM 0.9 0.9 0.8 0.8 0.7 0.7 0 20 40 60 80 100 pitch shift (decrease) (b) Co rre ct m at ch es (% ) Algorithm 2 Algorithm 1 Audio SIFT SHAZAM 1.1 1.1 1.2 1.3 1.3 1.4 0 20 40 60 80 100 pitch shift (increase) (c) Co rre ct s ca le s (% ) Algorithm 2 Algorithm 1 Audio SIFT 0.9 0.9 0.8 0.8 0.7 0.7 0 20 40 60 80 100 pitch shift (decrease) (d) Co rre ct s ca le s (% ) Algorithm 2 Algorithm 1 Audio SIFT Figure 2.9: The percentage of correctly matched points (TPR) (a),(b) and the percentage of the correctly scaled (matching) points (c),(d) as the pitch of the song is varied. song. It can be seen that even when there is no pitch shift or tempo change, Shazam has the lowest performance. Fig. 2.11 (b) plots the percentage of correctly scaled matching points. It can be seen that the AudioSIFT and Algorithm 2 are the most robust one, with Algorithm 2 having a negligibly lower performance. It can be concluded (from figures 2.8, 2.9, 2.10, and 2.11) that, in general, Algorithm 2 is very robust compared to the state-of-the-art, resulting in a high percentage of correctly matched feature points as well as a high percentage of correctly scaled ones. In the rest of this chapter, we only compare Algorithm 2 to AudioSIFT. 33 1.2 1.4 1.7 2.1 2.5 3 0 20 40 60 80 100 speed [time scaleing] (increase) (a) Co rre ct m at ch es (% ) Algorithm 2 Algorithm 1 Audio SIFT SHAZAM 0.8 0.7 0.6 0.5 0.4 0.3 0 20 40 60 80 100 speed [time scaleing] (decrease) (b) Co rre ct m at ch es (% ) Algorithm 2 Algorithm 1 Audio SIFT SHAZAM 1.2 1.4 1.7 2.1 2.5 3 0 20 40 60 80 100 speed [time scaleing] (increase) (c) Co rre ct s ca le s (% ) Algorithm 2 Algorithm 1 Audio SIFT 0.8 0.7 0.6 0.5 0.4 0.3 0 20 40 60 80 100 speed [time scaleing] (decrease) (d) Co rre ct s ca le s (% ) Algorithm 2 Algorithm 1 Audio SIFT Figure 2.10: The percentage of correctly matched points (TPR) (a),(b) and the percentage of correctly scaled (matching) points (c),(d) as the speed of the song is varied. Discrimination ability of the proposed fingerprints In the previous subsection we examined the robustness of the fingerprints. In this section we evaluate the uniqueness of the extracted features. In other words, we examine how discriminant are the features extracted from a song. To do so, a fin- gerprint database of all the fingerprints extracted from all the 260 songs is created. To form queries, first a single mash-up of 100 randomly selected snippets of length 10 to 20 seconds is generated from the songs in the dataset. The queries are gen- erated by attacking this mash-up and by modifying its speed, pitch, tempo, etc. To find a potential match for a local fingerprint extracted from a query, the fingerprint 34 26.8 32.2 38.6 46.3 55.6 66.7 0 20 40 60 80 100 SNR (db) (a) Co rre ct m at ch es (% ) Algorithm 2 Algorithm 1 Audio SIFT SHAZAM 26.8 32.2 38.6 46.3 55.6 66.7 0 20 40 60 80 100 SNR (db) (b) Co rre ct s ca le s (% ) Algorithm 2 Algorithm 1 Audio SIFT Figure 2.11: The percentage of correctly matched points (TPR) (a) and the percentage of correctly scaled matching points (b) as the amount of noise in the query is varied. database is searched for the nearest neighbour of the query fingerprint. This way the query fingerprints are compared against the fingerprints from all the songs so as to evaluate how uniquely they can identify a song. The matching criteria is the same as Eq. 2.1 but with X being the database of all fingerprints extracted from all of the original songs. The database contains 260 songs while the query contains snippets from 100 songs. If a matching fingerprint form the database belongs to a song different from those existing in the query, a false positive is declared. Table 2.1 compares the performance of Algorithm 2 and AudioSIFT for attacks commonly studied in the literature. It can be seen from this table that except for the equalization attack, more than 98% of the fingerprints extracted using Algorithm 2 correspond to the right song, i.e. less than 2% of the detected feature points correspond to the wrong song (FPR < 2%). For AudioSIFT the false positive rate can be as high as 58%. For the equalization attack, the proposed method has a false positive rate of about 8%, while for AudioSIFT this value is about 22%. It can be concluded from the table that our proposed algorithm greatly outperforms AudioSIFT in terms of false positive rates. 35 Table 2.1: Average percentage of correct song association. Attack Algorithm 2 AudioSIFT Speed increase (20%) 98.86 72.5 Speed decrease (20%) 98.84 56.00 Tempo increase (20%) 98.13 44.00 Tempo decrease (20%) 99.62 41.38 Pitch increase (2/12 octave) 98.23 69.50 Pitch decrease (2/12 octave) 98.01 64.00 Low Pass Filter (1kHz) 99.79 92.95 High Pass Filter (200Hz) 99.70 82.96 Compression (64kbps) 99.67 89.86 Compression (32kbps) 99.53 88.89 Equalization (40db) 92.55 78.17 2.5 Song identification In Section 2.4, we only evaluated our proposed local audio fingerprint extraction al- gorithms. In other words, we only performed feature point detection and retrieval. For audio copy detection, however, the algorithm needs to perform the detection at a higher level, i.e. information from individual fingerprint detections should be aggregated and the algorithm should be able to state whether or not any part of a query song is copied from the database. It should also accurately locate the copied parts in the database. In other words, an output of the system should be able to state:” ... the segment t ′0 to t ′1 in the query is copied from t0 to t1 of song s in the database ... ”. Below we propose an audio copy detection algorithm that uses the output of the fingerprint detection phase and accomplishes the above task. The pro- posed algorithm can also estimate the amount of pitch shift and/or tempo change that a copy may have gone through. 2.5.1 Algorithm 3 The song identification algorithm starts with a pre-processing step. The output of this step is: 1) the ID of the songs that are believed to be (partly) copied to the query and 2) the approximate locations of each of these songs in the query. The 36 output of the pre-processing step is then, used by the main algorithm 1) to estimate the pitch shift and the tempo change value and 2) to find the exact location of the copies in the query as well as their corresponding detected song snippets in the database. Pre-processing First a local fingerprinting method is applied to find matching feature points be- tween the query and the songs in the database. As mentioned before, to carry out this, for each fingerprint of the query song, the fingerprint database is searched to find the nearest neighbour. If the nearest neighbour distance is less than a pre- defined threshold the feature point corresponding to the nearest neighbour is re- turned as a match for the query feature point (from which the query fingerprint was extracted). The query feature point and its match (from the database) are called a matching pair. We denote the set of query feature points for whom a match is found by F . Every query feature pint f ∈ F , is assigned the same song as its match in the database. After assigning songs to the feature points, a voting scheme is applied on them and most occurring songs in different time intervals are found. More specifically, the devised method moves a window of length ∆ seconds over the query song. If at least r%(> 50%) of feature points contained in a window are assigned the same song, that song is assigned to the window. Nothing is assigned to a window that has no song occurring in more than r% of the feature points it contains. Values of ∆ and r are experimentally chosen to be 10s and 70% for the experiments in this thesis. Windows are then used to find continuous (approximate) intervals for songs detected in the query. Thus for every query, the result is a set of detected songs S = {s0,s1, . . .} and a corresponding set of time intervals T = {(t0,d0),(t1,d1), . . .}, where ti and di are the starting time and the duration of the time interval (in the query) corresponding to song si. Fig. 2.12 shows a sample of the detected songs along with their corresponding true and estimated time intervals for queries that contain pitch shifted and tempo changed snippets of the original songs. As seen in the figure, the estimated time intervals include the actual time intervals. 37 0 50 100 150 0 50 100 150 200 250 300 time (a) So ng ID proposed Original 0 50 100 150 0 50 100 150 200 250 300 time (b) So ng ID proposed Original Figure 2.12: The ID’s of the detected songs and their corresponding time in- tervals (results of the pre-processing step) for a query containing (a) tempo changed (−20%) and (b) pitch shifted (−2/12 octave) copies of the songs in a database. Song identification and localization We now propose an algorithm that uses the set of detected songs S along with the corresponding set of time intervals T (obtained from the pre-processing stage above) to further increase the accuracy of the detection. That is for each interval, the algorithm finds the accurate time relation between the query song and the de- tected database songs. We now explain what do we mean by the accurate time relation: For each si ∈ S, let tdb be the time coordinate in the detected database song si, and let tq be the corresponding time coordinate in the query song. Then, the algorithm finds the best tempo change value a that satisfies tq = atdb + b for the interval (ti,di) ∈ T of the query. The offset b accounts for the time differences between the query and the database song (a snippet can be arbitrarily extracted from a song in the database, be modified and then inserted in an arbitrary position in the query). By knowing the tempo change value a, and the offset value b, one can accurately locate the copied interval in the database. The algorithm also estimates the amount of pitch shift value ∆p. The algorithm uses a set of attributes corresponding to each detected query feature point f ∈ F . The attributes are either extracted from the query feature point 38 itself or from its matching feature point in the database. The attributes are 1) ID(f ): the ID of the song in the database, 2) â( f ): the ratio between the scales assigned to the query feature point and that of its match, 3) ˆ∆p( f ): the difference between the chroma coordinate of the query feature point and that of its match, 4) tq( f ): the time coordinate of the query feature point, 5) tdb( f ): the time coordinate of the matching feature point in the database song. The algorithm is shown in Fig. 2.13. First, for each interval (ti,di) ∈ T , the feature points that do not correspond to the detected song si ∈ S are discarded. The algorithm also discards the ones whose â values are invalid, i.e. their values are outliers in relation to the scale values of other feature points in (ti,di). To find the outliers, first the histogram of the â values is found. The histogram is then smoothed using a Low Pass Filter (LPF)8. We used a Gaussian LPF to smooth the histogram. Outliers are those feature points, whose â values do not fall within δa of the maximum point in the smoothed histogram. The algorithm then prunes more points based on their ˆb values. The ˆb value is the offset between tq and tdb after considering the estimated tempo change â. By removing the mean values of tdb and tq in each interval, one can remove the offset (or more accurately bring the expected offset towards zero) and thus increase the accuracy of detections. After pruning the detected feature points, the algorithm estimates the amount of tempo change a and the offset b by applying a linear regression (based on min- imizing the sum of squared errors). For estimating the pitch shift value ∆p, the algorithm chooses the most frequent value within the ˆ∆p values of the pruned fea- ture points. Experimentally, we have found that most of the detected feature points whose scale and offset values are close to a and b of the corresponding interval, have the exact correct pitch shift value. This is why we used mode of the pitch shift values instead of their mean value for estimating the pitch shift parameter. To further refine the detected boundaries, the first and last feature points in the time interval (ti,di) that are compatible with the estimated values of a and b are found. These two points along with their scales define the boundaries of the detected snip- pet. 8Filtering reduces the sensitivity of the histogram to the location of its bins. 39 Input: Detected song si, its estimated time interval (ti,di), the set of the detected features F and their attributes (ID, â, ˆ∆p, tq, tdb). Output: the amount of tempo change a, the offset value b, and the amount of pitch shift ∆p. 1: F = F−{ f ∈ F | ID( f ) 6= si} 2: hâ = Histogram(â( f )| f ∈ F) 3: ã = argmaxLPF(hâ) 4: F = F−{ f ∈ F | â( f ) 6∈ (ã−δa, ã+δa)} 5: Find ˆb( f ), where ˆb( f ) = tq− ãtdb, ∀ f ∈ F 6: h ˆb = Histogram(ˆb( f ) | f ∈ F) 7: ˜b = argmaxLPF(h ˆb) 8: F = F−{ f ∈ F | ˆb( f ) 6∈ (˜b−δb, ˜b+δb)} 9: (a,b) = argmina,b ∑ f∈F(tq( f )−atdb( f )−b)2 10: ∆p = mode{ ˆ∆p( f ) | f ∈ F} Figure 2.13: Localization and parameter estimation 2.5.2 Performance evaluation In this section we evaluate the performance of the proposed audio copy detection system. Similar to the evaluations in Section 2.4.3, we first use the feature extrac- tion algorithm (the proposed Algorithm 2 or AudioSIFT) to detect the matching pairs of feature points between the query song and the songs in the database. The detected feature points are then passed to the song identification algorithm (Algo- rithm 3). The output of the song identification algorithm is formed of: 1) The ID of the songs in the database that were (partly) copied to the query. 2) The estimated time interval for each detected song in the query. 3) The amount of pitch shift or tempo change (if any) that was applied to each part of the song (that was copied into the query). To evaluate the performance of the system, we used the same settings used in Section 2.4.3, i.e. the query was an attacked version of a song, formed by mashing up 100 song snippets that were randomly extracted from the songs in the database (about 250 songs). Figures 2.14, 2.15, 2.16 compare the correct song identification rate, correct tempo change estimation rate, and the correct pitch shift estimation rate of our algorithm to those of AudioSIFT. Estimated tempo change and pitch 40 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 0 20 40 60 80 100 tempo change (a) So ng id en tif ica tio n (% ) proposed AudioSIFT 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 0 20 40 60 80 100 tempo change (b) Sc al e id en tif ica tio n (% ) proposed AudioSIFT 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 0 20 40 60 80 100 tempo change (c) Pi tc h id en tif ica tio n (% ) proposed AudioSIFT Figure 2.14: Song identification rate (a), scale identification rate (b), and pitch identification rate (c) for different tempo change values. shift values are considered correct if they agree with the true values at least to two decimal points. It can be seen that the proposed algorithm significantly out- performs AudioSIFT for the whole range of attacks. It can also be seen that Au- dioSIFT is actually ineffective when the time scale of the signal is manipulated by a tempo or speed change, while the proposed feature points can lead to correct song identification and accurate attack estimation even for severe time scale attacks. 2.6 Summary In this chapter, we proposed an audio copy detection system that is robust to severe tempo change and pitch shift attacks. The system is based on local audio finger- 41 0.7 0.8 0.9 1 1.1 1.3 1.4 0 20 40 60 80 100 pitch shift (a) So ng id en tif ica tio n (% ) proposed AudioSIFT 0.7 0.8 0.9 1 1.1 1.3 1.4 0 20 40 60 80 100 pitch shift (b) Sc al e id en tif ica tio n (% ) proposed AudioSIFT 0.7 0.8 0.9 1 1.1 1.3 1.4 0 20 40 60 80 100 pitch shift (c) Pi tc h id en tif ica tio n (% ) proposed AudioSIFT Figure 2.15: Song identification rate (a), scale identification rate (b), and pitch identification rate (c) for different pitch shift values. prints and can be used to detect randomly extracted snippets of songs in a song database. We proposed a new representation for audio signals (which we called the time-chroma image) as the platform to extract the local audio fingerprints. The time chroma image has these properties: a pitch shift in the audio signal appears as a circular shift along the chroma axis in the time-chroma image and a tempo change in the audio signal appears as a scale change along the time axis in this image. We also proposed two novel algorithms to extract local feature points of an audio signal from its time-chroma image. These feature points are used to generate local fingerprints that are robust to tempo change and pitch shift attacks applied 42 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 0 20 40 60 80 100 speed change (a) So ng id en tif ica tio n (% ) proposed AudioSIFT 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 0 20 40 60 80 100 speed change (b) Sc al e id en tif ica tio n (% ) proposed AudioSIFT 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 0 20 40 60 80 100 speed change (c) Pi tc h id en tif ica tio n (% ) proposed AudioSIFT Figure 2.16: Song identification rate (a), scale identification rate (b), and pitch identification rate (c) for different speed-up factors. to a song. We then proposed an algorithm that uses the proposed fingerprints to detect whether or not original songs (or parts of them) are present in a query song; if they exit it also determines their accurate location in the query song as well as in the database. The choice of extracting local fingerprints allows the detection of an arbitrarily extracted snippet of a song that might have been used as a part of a mash-up of different songs. The proposed algorithm also estimates the amount of pitch shift or the amount of tempo change that a song or a part of it has been subjected to. It was shown that our proposed copy detection system outperforms existing algorithms by a great margin. 43 Chapter 3 Video Fingerprinting 3.1 Problem description Tens of thousands of videos are added and shared on the World Wide Web every day. A considerable number of these videos, however, are illegal copies or manipu- lated versions of existing media. This makes copyright management of the Internet a complicated process. Today’s widespread copyright infringements of videos, call for the development of fast and accurate copy-detection systems. As video is the most complex type of digital media. Because videos are avail- able in different formats, it is more efficient to base the copy detection process on the content of the video rather than its name, description, or binary representa- tion. Video fingerprinting (also known as robust video hashing) has been recently adopted for this purpose [24]. A fingerprint is a content-based signature derived from a video, that specifically represents the video. To find a copy of a query video in a video database, one searches for a close match of its fingerprint in the fingerprint database (that corresponds to the videos in the database). Closeness of two fingerprints represents a similarity between the videos from which the finger- prints were extracted from; two perceptually different videos should have different fingerprints. Many of the existing algorithms for video fingerprinting have focused on the extraction of robust and discriminant features from a video. However, when de- signing a practical fingerprinting system for video databases with a huge number 44 of videos, the computational bottleneck is the search time required to find the fin- gerprint in the database that matches that of the query video. We will address this problem as well. Our final proposed fingerprinting system along with the search algorithm, is shown to be robust, discriminant, and fast. Fig. 3.1 shows the overall structure of this fingerprinting system. Figure 3.1: The schematic of a complete fingerprinting system. The security of fingerprinting has been addressed by only few studies so far [1, 25–27]. It is however important for copyright protection applications as the system may be compromised by fake fingerprints generated by an adversary who knows the algorithm. By using a secret key, we show in Section 3.6 that the security of our fingerprinting system can be increased. We also articulate the trade-off between security and robustness. The rest of this chapter is organized as follows: in Section 3.2, we present an overview of related work. In Section 3.3 we explain our fingerprinting approach. In Section 3.4, two fast search algorithms are proposed and analysed. The perfor- mance results of the system are presented in Section 3.5. In Section 3.6, a secure version of the proposed fingerprinting system is introduced and analysed, and fi- nally, the chapter is summarized in Section 3.7. 3.2 Related work Existing video fingerprint extraction algorithms can be classified into four groups based on the features they extract: color-space based, temporal, spatial, and spatio- temporal (see [28] and [29] for a survey of existing video fingerprinting methods). 45 Color-space based fingerprints are among the first feature extraction methods used for video fingerprinting [28]. They are mostly derived from the histograms of colors in specific regions in time and/or space within the video. Since color features change with different video formats [30], these features have not been very popular. Another drawback of color features is that they are not applicable to black and white videos. For this reason, most of the video fingerprinting systems apply to the gray scale representation of the frames. Temporal fingerprints are extracted from the characteristics of a video sequence over time [31]. These features usually work well with long video sequences, but do not perform well for short video clips since they do not contain sufficient discriminant temporal information. Because short video clips occupy a large share of on-line video databases, temporal fingerprints alone are not suitable for on-line applications. Spatial fingerprints are features derived from each frame or from a key frame. They are widely used for both video and image fingerprinting. There is a large body of research in the area of image fingerprinting and many researchers have extended the concepts developed for image fingerprinting to the video fingerprinting field [32–39]. Spatial fingerprints can be further subdivided into global and local finger- prints. Global fingerprints depict the global properties of a frame or a sub-section of it (e.g., image histograms), while local fingerprints usually represent local in- formation around some interest points within a frame (e.g., edges, corners, etc). These interest-points are conventionally used in the multimedia retrieval commu- nity mainly for object retrieval purposes. However, with adequate post-processing they can also be applied to multimedia copy detection and many researchers have recently considered them for this task [40–43]. Many of these works use SIFT features [20] which are proven to be very robust against many distortions and have been successfully applied for retrieval purposes. SIFT features provide ro- bustness to content-changing attacks, which is not achievable with global features. However, for a short segment (e.g. 1 second) of a video, there are a large number (thousands) of SIFT features. This makes them impractical from a memory man- agement point of view, when applied to large video databases containing billions of hours of videos [44]. Furthermore, the amount of post-processing required by these methods makes them less appealing for copy detection purposes. Therefore, in this work, we use global features, as they do not have the above limitations. 46 One shortcoming of spatial fingerprints is their inability to capture the video’s temporal information, which is an important discriminating factor. Spatio-temporal fingerprints that contain both spatial and temporal information about the video are thus expected to perform better than fingerprints that use only spatial or tempo- ral fingerprints. We have adopted spatio-temporal fingerprints because of their comprehensiveness. Some spatio-temporal algorithms consider a video as a three- dimensional (3D) matrix and extract 3D transform-based features [1, 45]. Others use spatio-temporal descriptors of specific interest-points to generate the finger- prints [46, 3]. Ordinal spatio-temporal features have also been used in the literature [47]. Applying a 3D transform to a video is a computationally demanding process and may pose problems in on-line applications. In this chapter, we propose a method for forming Temporally Informative Rep- resentative Image (TIRI)s from a video sequence. A TIRI contains both spatial and temporal information of a short segment of a video sequence, and thus the spatial feature extracted from a TIRI will also contain temporal information. Based on TIRIs, we propose an efficient fingerprinting algorithm (TIRI-DCT) and compare it to that proposed by Coskun et al. in [1] (3D-DCT). We show that our proposed algorithm outperforms 3D-DCT except when the video have been subjected to a geometric attack. We will discuss these algorithms in Section 3.3 and demonstrate that our proposed algorithm yields consistently better performance compared to 3D-DCT. 3.3 Extracting robust and discriminant fingerprints In this section, we briefly explain an established fingerprinting algorithm [1], which will be used as the basis of the comparisons in our simulations. We then describe how we generate a Temporally Informative Representative Image (TIRI), and dis- cuss the details of our proposed fingerprinting algorithm. Before extracting the fingerprints, we pre-process the video signals. Because copies of the same video but different frame sizes and frame rates usually exist in the same video database, a fingerprinting algorithm should therefore, be robust to changes in frame size as well as frame rate. Down-sampling can increase the robustness of a fingerprinting algorithm to these changes. As shown in Fig. 3.2, each video is down-sampled 47 Figure 3.2: Pre-processing applied to the videos before fingerprinting. both in time and space. Prior to down-sampling, a Gaussian smoothing filter is ap- plied in both domains to prevent aliasing. This down-sampling process results in a fixed size (W ×H pixels) and fixed rate (F frames/second) video signal. We chose W = 144, H = 176 (the size of QCIF sequences used widely in the video processing community), and F = 4. These parameter values have been chosen experimentally. After preprocessing, the video down-sampled frames are divided into overlapping segments of fixed-length, each containing J frames. The fingerprinting algorithm is applied to these segments. The amount of overlapping is experimentally chosen to be 50%. Overlapping reduces the sensitivity of the fingerprints to time shift at- tacks. In the next section, we briefly explain the algorithm proposed in [1], referred to as the 3D-DCT. 3.3.1 Spatio-temporal fingerprinting using 3D-DCT Coskun et al. considered a video as a three-dimensional (3D) matrix of luminance values [1]. After the pre-processing phase described above, they applied a three di- mensional discrete cosine transform (3D-DCT) to videos to extract spatio-temporal features. Binary fingerprints were then derived by thresholding the low-frequency coefficients of the transform, as shown in Fig. 3.3. The threshold is the median value of the selected coefficients. As a result, the generated fingerprint (hash) had equal numbers of 0’s and 1’s. With this property, the maximum number of different fingerprints that can be generated from a binary vector of length L drops from 2L to ( L L/2 ) . This property increases the robustness of the fingerprint, but decreases its discrimination ability. The robustness and discrimination of a fingerprint also 48 depend on L, which is determined by the size of the low-frequency block. In [1], the 3D-DCT was shown to be resistant to different types of distortions that can happen to video signals, including changes in brightness/contrast, added Gaussian noise, rotation, spatial/temporal shift, and frame loss. A secure version of the algo- rithm, called Random Basis Transform (RBT) was also proposed in [1]. It is based on randomizing the frequency of the cosine basis functions of the DCT transform. This secure version, however, had a lower performance compared to the insecure version. In the rest of this section, we first discuss generating the TIRI images to capture the temporal information in a video. We then provide the details of our proposed fingerprinting algorithm based on these TIRIs. Figure 3.3: The schematic of the 3D-DCT algorithm proposed in [1]. 3.3.2 Spatio-temporal fingerprinting using TIRI Generating temporally informative representative images (TIRIs) This method (also used in [48]) calculates a weighted average of the frames to generate a representative image. The resulting image is basically a blurred image that contains information about possible existing motions in a video sequence. The TIRI is thus generated as follows: let lm,n,k be the luminance value of the (m,n)th pixel of the kth frame in a set of J frames. The pixels of TIRI are then obtained as a weighted sum of the frames: l′m,n = J ∑ k=1 wk lm,n,k (3.1) We have examined different weight factors (constant, linear, and exponen- tial) and observed that exponential weighting generates images that best capture the motion. Fig. 3.4.(a)-(c) show the first, the middle, and the last frames re- 49 spectively, of a 1-second video segment (30 frames) extracted from the sequence COASTGUARD-QCIF ([2]). The corresponding TIRIs obtained using three differ- ent weighting functions are shown in Fig. 3.4(d)-(f): constant (Fig. 3.4.(d)), linear (Fig. 3.4.(e)), and exponential (Fig. 3.4.(f)). As mentioned earlier, Fig. 3.4 shows that the exponential weighting function produces perceptually better results. Our experiments with different videos led to the same conclusion, thus we have cho- sen the exponential weighting function (wk = γk) for generating the TIRIs. A very large γ , or one close to 0, generates a TIRI with detailed spatial information and low temporal information, resulting in a more discriminant representative. On the other hand, a γ close to 1 (i.e. giving the same weight to all the frames along the time line) results in a blurred image that is a more robust representative (containing averaged temporal information). By changing γ from 0 to 1, we can move from a single frame selection (high spatial information) to selecting all frames with equal weights (high temporal information). The effect of using different γ values on the performance of the fingerprinting system is demonstrated in Section 3.5. TIRI-DCT Algorithm Fig. 3.5 shows the block diagram of our proposed approach based on TIRIs [48]. Fig. 3.6 shows the details of this algorithm. As explained in Fig. 3.6, features are derived by applying a 2D-DCT on overlapping blocks of size 2w× 2w of each TIRI (with 50% overlap). The first horizontal and the first vertical DCT coefficients (features) are then extracted from each block. The value of the features from all the blocks are concatenated to form the feature vector. Each feature is then com- pared to a threshold (which is the median value of the feature vector) and a binary fingerprint is generated. A drawback of 3D-DCT is its binarization phase, where coefficients of different frequencies are binarized based on their median value. Fig. 3.7 shows the range of DCT coefficients belonging to different frequencies derived from 200 video frames. It can be seen that different coefficients have different ranges, thus having a com- mon threshold for the binarization process is far from optimal. This problem does not exist with our proposed TIRI-DCT. For TIRI-DCT, all features are in the same frequency range, and binarization based on a common threshold is thus justified. 50 ( a ) ( b ) ( c ) ( d ) ( e ) ( f ) Figure 3.4: Frames (a) 61, (b) 75, and (c) 90 of the sequence COASTGUARD-QCIF [2] and the resulting TIRIs with different weighting functions: (d) wk = 1 (constant), (e) wk = k (linear), (f) wk = 1.2k (exponential). 3.4 Fast matching of fingerprints As shown in Fig. 3.1, in order to determine whether or not a query video is an attacked version of a video in a database, its fingerprint is first extracted. The database of fingerprints (previously created from the fingerprints of the video database) is then searched for the fingerprint closest to the extracted query fingerprint. It should be mentioned that in copy detection, the problem is to determine if a spe- cific query video is a pirated version of any video in the database. On the other hand, the problem of finding all copies of a video in a database is called copy retrieval and requires a different approach. Fingerprints of two different copies of the same video content are similar but not necessarily identical. This is why we seek a close match of the query in the fingerprint database and not an exact match. This problem is a similarity search problem or a nearest neighbour problem in the binary space [24]. The trivial solu- tion to this problem is to apply an exhaustive search which unfortunately imposes 51 Figure 3.5: The schematic of the TIRI-DCT algorithm. a large computational load on the fingerprinting system. Therefore, instead of the time-consuming exact nearest neighbour search, a fast approximate algorithm is deployed. In real-world applications, the size of on-line video databases can reach tens of millions of videos, which translates into a very large database of fingerprints. This means that even if the fingerprint of a query video can be extracted very quickly, searching the fingerprint database to find a match may take a long time. For on- line applications, however, a reliable match should be found in real-time. This is why fingerprint matching forms a practical bottleneck for on-line fingerprinting systems. There is a large body of research on fast and reliable similarity search. Muja et al. have conducted a comprehensive study on state-of-the-art similarity search algorithms in Euclidean spaces [49]. There are a number of studies on similarity search on binary spaces as well [24, 50, 51]. However, only few papers in the video fingerprinting area have considered the fast search aspect in their design. Most of them have used a simple exhaustive search method which has a complexity of 52 1: Generate TIRIs from each segment of J frames using wk = γk (Eq. 3.1). 2: Segment each TIRI into overlapping blocks of size 2w× 2w, as fol- lows: Bi, j = {l′x,y |x ∈ iw±w,y ∈ jw±w} where, i ∈ {0,1,2, . . . ,W/w− 1} and j ∈ {0,1,2, . . . ,H/h− 1}. The TIRI image l′ is padded with zeros where the indexes are outside of the image boundaries. 3: Extract two DCT coefficients from each block. These are the first hor- izontal and vertical coefficients adjacent to the DC coefficient. The first vertical frequency, αi, j , can be found for Bi, j as follows: αi, j = vT Bi, j 1 Where v = [cos(0.5pi/2w),cos(1.5pi/2w), . . . ,cos(pi − 0.5pi/2w)]T and 1 is a column vector of all ones. Similarly, the first horizontal frequency βi, j can be found as follows: βi, j = 1T Bi, j v 4: Concatenate all the coefficients to form vector f . 5: Find m, which is the median of the elements of f . 6: Generate the binary hash h from f using the following formula: hk = { 1, fk ≥ m 0, fk < m Figure 3.6: TIRI-DCT algorithm. O(N), where N is the number of the fingerprints in the database. As an example of a fast search algorithm, Oostveen et al. proposed a search algorithm for their video fingerprinting algorithm, based on the inverted file technique [24]. In Section 3.4.1, we develop a modified version of [24] so that the algorithm can be used in any fin- gerprinting search. In Section 3.4.2, we propose a similarity search algorithm that uses a fingerprint clustering approach. We show the results of applying these two algorithms on the fingerprints derived by TIRI-DCT in Section 3.5.2. We should 53 0 0.2 0.4 0.6 0.8 1−10 −5 0 5 10 Freq. R an ge Figure 3.7: Range of (non-DC) DCT coefficients corresponding to different (normalized) frequencies. state that unlike many fingerprinting algorithms, both 3D-DCT and TIRI-DCT gen- erate binary fingerprints (vectors). This means that the Hamming distance (which is found using the simple XOR binary operation) can be used as a metric for mea- suring the similarity of the fingerprints. This has the advantage of requiring less search time than algorithms that derive numerical features and subsequently use the Euclidean distance to measure similarities. We will have a detailed discussion on nearest neighbour search in the Hamming space in Chapter 4. In the remaining of this chapter, we will touch the surface with some specifically designed algorithms. 3.4.1 Inverted file-based similarity search This search method is based on the idea that when two fingerprints are similar enough to be considered matches, then the probability of two smaller sub-blocks of them being exactly the same is high [24]. We divide each fingerprint into small non-overlapping blocks of m bits. We call these small blocks words (thus, there are 2m possible words). Words are then used to create an inverted file from the fingerprints of database. All fingerprints have equal lengths, so the inverted file can be represented as a table of size 2m × n, where n is the number of words in a fingerprint of length L (n = ⌊L/m⌋). Thus each column, represents a possible position of a word inside a fingerprint (Fig. 3.8). Each row represents a possible 54 (decimal) value of the word. To generate this table, we start with the first word of each fingerprint (Fig. 3.8.(a)), and add the index of the fingerprint to the entry of the first column that corresponds to the value of this word. We continue this process for all the words in each fingerprint and all the columns in the inverted file table. Figure 3.8: (a) Dividing the fingerprint into words, (b) Sample inverted file for the fingerprint database. A sample of the generated inverted file is shown in Fig. 3.8(b). Entry (i, j) in the table is a list of the indices of all the fingerprints that their jth word has the value i. To find a query fingerprint in the database, first the fingerprint is divided into n words (of m bits). The query is then compared to all the fingerprints that start with the same word. The indices of these fingerprints are fetched from the corre- 55 sponding entry in the first column of the inverted file table. The Hamming distance between these fingerprints and the query is then calculated. If a fingerprint has a Hamming distance of less than some pre-defined threshold, it will be announced as the match. If no such match is found, the procedure is repeated for the fingerprints that have exactly the same second word as the query’s second word (the indices of these fingerprints are read from the corresponding entry in the second column of the inverted file table). This procedure is continued until a match is found or the last word is examined. When no match is found in the end, it is concluded that the query does not belong to the database. The above algorithm can be used for finding the nearest neighbour of any binary fingerprint within a database. To show the validity of the assumption that two similar fingerprints have at least one exactly matching word, we ran some simulations. Fig. 3.9 shows the experimental prob- ability distribution of the number of identical words between fingerprints of two similar videos (two different copies of the same video content) for both 3D-DCT and TIRI-DCT. It can be seen from the figure that the probability of not having any pair of identical words between two similar fingerprints is almost zero for both al- gorithms. In Section 3.5, we will demonstrate the results of applying the proposed search to TIRI-DCT and compare the results to the exhaustive search both in terms of search time and performance. 0 5 10 15 20 25 30 35 400 0.02 0.04 0.06 0.08 0.1 0.12 0.14 3D−DCT No. of exact word matches ( a ) Ex pe rim en ta l p ro b. 0 5 10 15 20 25 30 350 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 TIRI−DCT No. of exact word matches ( b ) Ex pe rim en ta l p ro b. Figure 3.9: Histogram of the number of exactly matching words between two similar fingerprints (a) 3D-DCT, (b) TIRI-DCT. If the word length is chosen correctly, then the worst case scenario where the 56 algorithm examines every word of the query will require searching O( L m2m N) fin- gerprints. For an extremely robust fingerprinting algorithm that has a very low threshold, a large m can be chosen to reduce the search speed by several orders of magnitude. However, there is a trade-off between the speed and the required memory for storing the inverted file table. It is not practical for word lengths larger than 16 bits to have a complete inverted file and only the existing words should be indexed. An analysis of a similar search algorithm used in a different context can be found in [52]. Assuming that there are no pair of fingerprints in the database that are closer than a Hamming distance of th, the algorithm is guaranteed to find the correct match, if th < n(= L m ). However, if th >= n, then the algorithm may generate false negatives due to the fact that there may exist a mismatch in each word. To calculate the probability of false negative, we assume that there exists a fingerprint in the database that has a Hamming distance of th from the query fingerprint (i.e. they both belong to the same perceptual content). We also assume that unequal bits (errors) are uniformly distributed along the fingerprint (a pseudo-random permuta- tion can assure that this assumption holds true). Here, pFR (the probability of false rejection) can be computed as: pFR = kmax∑ k=0 (−1)k ( n k )(L−k∗m th ) (L th ) (3.2) which is upper bounded by UbFR = kmax∑ k=0 (−1)k(1− m L− th+1) k∗th (3.3) and lower bounded by LbFR = kmax∑ k=0 (−1)k(1− m L )k∗th (3.4) where kmax = max{k|L−k∗m≥ th}. Finally, it is worth mentioning that when the query belongs to the database, the algorithm most likely returns the result after examining the first few words. The probability that the algorithm continues its 57 search by examining the second word, i.e. the probability that the first word has an error (denoted by pw1 ), is: pw1 = 1− pw1 = 1− (L−m th ) (L th ) (3.5) The probability that the algorithm continues its search to the third word is even lower. If there exists a fingerprint in the database that has a distance of less than th with the query, by examining the first two words, the algorithm searches an ex- pected number of N2m (1+ pw1) fingerprints. In the next section, we propose another approximate search algorithm and we compare the estimated run-time of both al- gorithms in terms of the expected number of fingerprints that must be searched. 3.4.2 Cluster-based similarity search In this section, we propose another similarity search algorithm for binary finger- prints. Our main idea is to use clustering of fingerprints in the database to reduce the number of fingerprints that are examined for each search. By assigning each fingerprint to one cluster (out of K clusters), the fingerprints in the database will be clustered into K non-overlapping groups. To do so, a centroid is chosen for each cluster, termed the cluster head. A fingerprint will be assigned to cluster k if it is closest to this cluster’s head (see Fig. 3.10(a)). To determine if a query fingerprint matches a fingerprint in the database, the cluster head closest to the query is first found. All the fingerprints (of the videos in the database) belonging to this cluster are then searched to find a match, i.e. the one which has the minimum Hamming distance (of less than a certain threshold) from the query. If a match is not found, the cluster that is the second closest to the query is examined. This process contin- ues until a match is found or the farthest cluster is examined. In the latter case, the query is declared to be out of the database. The cluster heads should be chosen such that a small change in the fingerprint does not result in the fingerprint being assigned to another cluster. In our general setting, we choose cluster heads (centres) as all the binary vectors with length l ≪ L. To assign a fingerprint to a cluster, the fingerprint is first divided into segments (words) of length m = L/l. Each word is then represented by one bit in the l-bit 58 cluster head, depending on the majority of word’s bit values, e.g., it is represented by 1, if it has more than (or equal to) m/2 1’s and it is represented by 0, if it has less than m/2 1’s. Equivalently, each bit of the cluster head can be replicated m times and the Hamming distance between the expanded L = m∗ l bit version of all the cluster heads and the fingerprint is calculated. The cluster head closest to the fingerprint is then assigned to that fingerprint (at the end of this section, we will explain a version of cluster assignment developed for TIRIs). As stated earlier, if the query is not matched to any fingerprint in a certain clus- ter, the algorithm continues its search over other clusters starting from the closer ones. For this algorithm, in the worst case scenario, all the fingerprints will be searched. So unlike the case of the inverted-file based search, the clustering-based search is guaranteed to return a match if it exists. Thus, in the worst case sce- nario, this algorithm has a runtime of O(N), which is not better than the exhaustive search. However, similar to the case of the inverted-file based search, the algorithm in practice returns a match (if one exists) after examining the first few clusters, thus reducing the actual number of comparisons to O(N/2l) fingerprints. The probabil- ity that the algorithm fails to find the fingerprint in the closest (first) cluster is upper-bounded by the probability that a word in a fingerprint has approximately an equal number of 1’s and 0’s multiplied by the expected number of words that have errors. This probability, denoted by pchange can be approximated as: pchange = 1− (1− erf ( 1√2m).(1− e −m.th/L))l (3.6) The first component erf ( 1√2m) is derived using a Gaussian approximation as- suming m is 7 bits or more. The second component (1− e−m.th/L) is derived by approximating the spatial distance between two errors by an exponential distribu- tion assuming that errors happen rarely and independently with an average of th/L. The above approximation is not good for small m’s and the actual probability has a complicated form. Fig. 3.11.(a) shows the approximate number of finger- prints that are examined in each attempt for the proposed cluster-based approach as well as the inverted file-based approach (assuming that the fingerprints are spread randomly in the binary space). Fig. 3.11.(b) shows the probability that each ap- proach fails in the first attempt. The higher this probability, the more likely it is 59 for the algorithm to continue its search through other attempts (next clusters, or table columns). It can be seen that the cluster-based approach is very likely to find the match in its first attempt when m is large (low probability of failing), however percentage of the total fingerprints that should be examined in the first cluster is very large compared to when m’ is small. Please note that an exhaustive approach searches 100% of the fingerprints. For the inverted file-based method this trade-off can also be seen, e.g. when the word length is small the algorithm is likely to find a match in the first attempt, but it has to search a larger number of fingerprints. Figure 3.10: (a) Clustering the fingerprints for TIRI-DCT, (b) Expanding a cluster head to compare it with a fingerprint. To increase the performance of the search, an improved version of clustering 60 1 2 3 4 5 60 5 10 15 20 25 log2 m (a) % o f t ot al q ue rie s se ar ch ed in e ac h at te m pt Inv. Clu. 1 2 3 4 5 60 0.2 0.4 0.6 0.8 1 log2 m (b) Pr ob . o f f ai lin g in th e fir st a tte m pt Inv. Clu. Figure 3.11: Comparing the runtime of the clustering-based search method with that of the inverted file-based method for different values of m (L = 128, th = 16) (a) Approximate percentage of fingerprints exam- ined with each attempt (b) Probability of failing the first attempt. for TIRI-based fingerprinting is used. The cluster heads are chosen as those bi- nary vectors of even length l ≪ L with an equal number (l/2) of 0’s and 1’s. This procedure will result in fingerprints being divided into ( l l/2 ) clusters. We need to determine which cluster head is closest to a fingerprint. To compare two binary vectors of different length, we propose the following procedure adapted for finger- prints derived by TIRI-DCT. As presented, to derive an L-bit fingerprint, TIRI-DCT divides the TIRI image into L/2 overlapping blocks. Two bits are then derived from each block (one representing a horizontal feature and one representing a ver- tical one). To compare a fingerprint to a cluster head, we use only one of these features for simplicity, e.g., horizontal bits. We then expand each cluster head of length l to a bit vector of length L/2. To do so, we first assign each n adjacent blocks to a larger block (n = L/(2l)), as shown in Fig. 3.10(b). We then assign each bit of the cluster head to one of these larger blocks. Finally, we assign all the original blocks with a bit value equal to their corresponding large block and concatenate all these bit values to form an expanded cluster head of length L/2. Fig. 3.10(b) demonstrates how this expansion is done. Following this process, the Hamming distance can be calculated to measure the closeness of the fingerprints and the cluster heads. The proposed cluster-based search reduces the search time 61 approximately proportional to the number of clusters. 3.5 Performance evaluation In this section, we evaluate the performance of the proposed algorithms using a video database. We first compare the raw performance of TIRI-DCT with 3D-DCT in Section 3.5.1. For comparisons, we use an exhaustive search as it gives the most accurate results. We will show that TIRI-DCT is faster than 3D-DCT while maintaining a very good performance over the range of the studied attacks. Next, in Section 3.5.2 we evaluate the performance of the approximate search techniques proposed in Section 3.4. We have implemented these algorithms and used them as the search engine for video copy detection based on the fingerprints derived using the proposed TIRI-DCT, and compared the results to the exhaustive search. We show that the cluster-based search method outperforms the inverted file-based method both in search time and detection performance. To evaluate the performance of the proposed algorithms, a database of 200 videos (collected from ReefVid [53]) was created. TIRI-DCT and 3D-DCT were separately applied to each video in the database. A fingerprint database was then formed from all of the generated fingerprints for each of these two algorithms. Next, videos in the database were distorted (attacked) to generate query videos. The attacks studied included added Gaussian noise, change in brightness/contrast, frame loss, shift in time/space, and rotation. Table 3.1 shows the attacks and their corresponding parameter values. Table 3.1: Attack parameter values used in the evaluation of the proposed algorithms. Attack Effect Min Max Noise (σ ) l′m,n,k = lm,n,k +G(0,σ) 0 100 Brightness (b) l′m,n,k = lm,n,k + b µk −0.7 0.7 Contrast (c) l′m,n,k = c(lm,n,k− 127.5) 0.5 2 Rotate (r) Rotates the whole frame r ◦ −5 5 Time shift (δ ) Video is shifted δ seconds in time −0.5 0.5 Spatial shift (sr,sd) Shifts the frame sr% right and sd% down −4 4 Frame loss ( f d) f d% of the frames are randomly dropped 0 70 Before extracting the fingerprints, every video was filtered and down-sampled 62 to a frame rate of 4 frames/second and a frame size of 144× 176. Videos were then segmented to 50% overlapping J frame sequences. We used J = 8, equivalent to 2-second segments. This value ensures that our fingerprinting algorithm is able to detect clips as short as 2 seconds. Note that smaller clips of the copyrighted videos may be cut and used within other videos (called mash-ups). This is why a fingerprinting algorithm should be able to recognize very short copies of videos as well. To determine the values of γ (the exponential weighting basis for generating TIRIs) and w (half of the width of the blocks in TIRIs), we ran some simulations on a small database of 14 videos, separately collected from [2]. We generated 280 videos out of these videos by applying random combined attacks from Table 3.1 to them. For different values of γ and w, the experimental probability distribution of the Hamming distance between the similar and different videos was then calcu- lated. Fig. 3.12 (a) shows an example of this distribution for γ = 0.65 and w = 16. Fig. 3.12 (b) shows the Receiver Operating Characteristic (ROC) curve [54] for different values of w (4≤ w≤ 32) when γ = 0.65. The figure also quantifies the trade-off between the robustness and the discrim- ination ability of our copy detection system. To evaluate the system’s performance and to determine the suitable parameter values, we require a single combined met- ric. Here, we used the F-score (Fβ ), defined as follows [55]: Fβ = (1+β 2) precision.recallβ 2 precision+ recall (3.7) In (3.7), β defines how much weight should be given to recall vs. precision. Recall is the same as true positive rate (a measure of robustness of the system). Precision is a measure of discrimination and is defined as the percentage of correct hits within all the detected copies. The F-score of a clustering method is a number between 0 and 1, with 1 representing a perfect classification system that is completely robust and completely discriminant (100% precision and 100% recall). A low F-score close to 0 represents a poor system in terms of both robustness and discrimina- tion. With a proper choice of β , the F-score can be a valuable single measure to summarize the detection performance. A copy detection system should have high precision to minimize the amount of human interaction required. We used β = 0.5, which gives twice as much importance to precision as to recall. Fig. 3.12 (c) 63 0 0.2 0.4 0.6 0.8 10 0.05 0.1 0.15 0.2 Normalized Hamming distance ( a ) Ex pe rim en ta l P ro b. D ist . Similar videos Different videos 0 0.2 0.4 0.6 0.8 10 0.2 0.4 0.6 0.8 1 FPR(%) ( b ) TP R (% ) w=4 8 12 16 20 24 28 32 0.2 0.4 0.6 0.8 1 0.92 0.925 0.93 0.935 0.94 0.945 γ ( c ) M ax F 0. 5 0 5 10 15 20 25 30 350.88 0.9 0.92 0.94 0.96 0.98 1 w ( d ) M ax F 0. 5 Figure 3.12: (a) Distribution of the Hamming distance between fingerprints corresponding to similar (copied) and different video sequences. (b) ROC curve for TIRI-DCT for w = 4 : 32 and γ = 0.65, (c) Maximum F0.5 for 0 < γ ≤ 1 and w = 16, (d) Maximum F0.5 for w = 4 : 4 : 32 and γ = 0.65. and (d) show the maximum F0.5 for 0 < γ ≤ 1 at w = 16 and for 4 ≤ w ≤ 32 at γ = 0.65. Our experiments show that γ = 0.65 and w = 16 give the best results, so we used these values in the TIRI-DCT algorithm. These parameter values result in a 126-bit fingerprint for TIRI-DCT (ignoring the marginal blocks). For 3D-DCT, the first 6×6×4 low frequency 3D-DCT coefficients were chosen to generate fin- gerprints of length 144 bits. 6× 6× 4 is chosen through simulations so that both algorithms have approximately the same fingerprint length and at the same time the performance of the 3D-DCT is maximized. Experiments show that extracting more 64 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 Threshold FP R (% ) w=4 8 12 16 20 24 28 32 Figure 3.13: FPR versus threshold for w = 4 : 32 (TIRI-DCT) features (for 3D-DCT) from the temporal domain did not increase the precision and recall even for time shift attacks. This is because the temporal domain of a video is basically a low frequency domain (e.g. 3D-DCT’s F0.5 decreases by 16% if we used the first 4×4×8 block instead). To see if a query video is a pirated copy of a video content in the database, first the fingerprints of the query were extracted and then their nearest neighbour fingerprints were sought in the fingerprint database. If the Hamming distance of this nearest neighbour with respect to the query fingerprint was less than some pre-defined threshold, the corresponding video was announced to be a match. Figure 3.13 shows FPR versus the threshold value for different block sizes. It can be seen that when w is very small there is a sharp transition in FPR. The threshold was set to 0.24 for TIRI-DCT to make sure that for a large range of block sizes the FPR is at most 2%. The threshold was set 0.31 for 3D-DCT respectively. Each of the two fingerprinting algorithms was then used to locate all the attacked videos in the video database and the detection performance of each algorithm was evaluated. 3.5.1 Performance evaluation of the fingerprint extraction algorithm To get the most accurate results, in this section, we compare the performance of TIRI-DCT and 3D-DCT when an exhaustive search is used for searching the 65 database. Table 3.2 shows the results of applying TIRI-DCT and 3D-DCT to the test database. Attacks were applied independently on the videos to generate the queries. For each attack parameter, 10 equally spaced values were chosen from the corresponding range in Table 3.1. Table 3.2 reports the average True Positive Rate (TPR), False Positive Rate (FPR), and the F0.5 for these values. As mentioned, we chose β = 0.5 to give precision twice the importance of recall. Fig. 3.14 shows the F-score for different attack parameters: noise addition, change in brightness, rotation, temporal/spatial shift, and frame loss. Table 3.2: Comparing TIRI-DCT with 3D-DCT when exhaustive search is used. Attack TPR (%) FPR (%) F-score 3D-DCT TIRI 3D-DCT TIRI 3D-DCT TIRI Noise 99.52 99.24 0.00 0.66 1.00 0.99 Brightness 99.90 99.40 0.01 0.60 1.00 0.99 Contrast 99.96 99.02 0.01 0.75 1.00 0.99 Rotation 99.99 99.57 0.00 0.43 1.00 1.00 Time shift 78.90 95.8 1.29 1.73 0.91 0.98 Spatial shift 99.71 96.25 0.03 1.85 1.00 0.98 Frame loss 93.21 98.39 0.42 0.78 0.98 0.99 Average 95.88 98.24 0.25 0.97 0.99 0.99 Table 3.2 shows that both TIRI-DCT and 3D-DCT have an average F-score of 0.99. So both algorithms have a very good performance on average, but as can be seen from the table, TIRI-DCT maintains this high performance for all the attacks, while the performance of 3D-DCT degrades for time domain attacks. Fig. 3.14 shows that both algorithms are robust to noise addition, changes in brightness/contrast, and rotation with high F-scores. It can be seen from Table 3.2 and Fig. 3.14 that 3D-DCT is robust to geometrical and signal processing attacks, but is sensitive to time shifts and frame loss, both of which happen frequently when dealing with on-line video databases. Time shift can happen regularly when the beginning of a query video segment is not aligned with the beginning of the reference video segment in the video database. Frame loss is also a common type of attack that can happen with on-line video streams. This is because 3D-DCT relies on extracting too much detail along the time axis, which decreases the robustness of the algorithm. TIRI-DCT demonstrates an acceptable performance for all attacks 66 0 20 40 60 80 1000.985 0.99 0.995 1 1.005 Noise σ ( a ) F 0 .5 3D−DCT TIRI−DCT −1 −0.5 0 0.5 10.975 0.98 0.985 0.99 0.995 1 1.005 Brightness b ( b ) F 0 .5 3D−DCT TIRI−DCT −5 0 50.985 0.99 0.995 1 1.005 Rotation r ( c ) F 0 .5 3D−DCT TIRI−DCT −0.5 0 0.50.7 0.75 0.8 0.85 0.9 0.95 1 Time shift δ ( d ) F 0 .5 3D−DCT TIRI−DCT −0.04 −0.02 0 0.02 0.040.88 0.9 0.92 0.94 0.96 0.98 1 Shift sr=sd ( e ) F 0 .5 3D−DCT TIRI−DCT 0.1 0.2 0.3 0.4 0.5 0.6 0.70.94 0.95 0.96 0.97 0.98 0.99 1 Frame loss fd ( f ) F 0 .5 3D−DCT TIRI−DCT Figure 3.14: F-score of 3D-DCT and TIRI DCT for different attack parame- ters from Table 3.1: (a) Noise addition, (b) Change in brightness, (c) Rotation, (d) Time shift, (e) Spatial shift, (f) Frame loss. 67 studied here. However, it should be noted that TIRI-DCT is more sensitive to spatial shifts than 3D-DCT. Again this is because 3D-DCT relies too much on temporal information and thus it is more robust to spatial attacks such as shift. However, we should note that with digital transmission, spatial shift does not occur within digital video databases. The performance (of TIRI-DCT) reported above is achieved using short finger- print lengths of 126 bits. By increasing the fingerprint length to 640 bits we were able to decrease the FPR on average by about 70% (to a maximum of about 0.4%) without affecting the TPR, resulting in a 0.6% increase in the F-score. As men- tioned in Section 3.3.2, the problem with the binarization scheme in the 3D-DCT method limits the number of DCT coefficients (and thus the fingerprint length) that can be used with this method. Our results show that increasing the fingerprint length used in the 3D-DCT method to about 600 bits has a negative effect on the TPR resulting in an approximate 7% decrease in the F-score. Another important property of TIRI-DCT is that it is computationally less de- manding than 3D-DCT. The latter applies a 3D-DCT transform requiring O(WHJ log(W HJ)) computation time, whereas, TIRI-DCT applies a two-dimensional block DCT re- quiring O(WH log(W H)) computation time. The above computational complexi- ties are calculated based on the assumption that all the DCT coefficients are derived. In practice, only the coefficients that are used should be computed and therefore the actual complexity depends on the number of coefficients used. For L-bit fin- gerprints, the computational complexity of the 3D-DCT is therefore O( 3 √ LWHJ) whereas the computational complexity of TIRI-DCT is O(max( √ L,J)W H). Table 3.3: Hash extraction time (in mS) for different segment sizes Segment length in msec Method 1 2 3 4 3D-DCT 3.3 4.6 6.0 7.4 TIRI-DCT 1.4 1.5 1.6 1.8 Table 3.3 shows the fingerprint extraction time in msec (for a practical imple- mentation) for different segment lengths. Algorithms were implemented and run in Matlab R2008b on a 64-bit PC with a 2.4 GHz CPU and 4GB of RAM. Note that the proposed algorithms have a primary step of generating the TIRIs. This involves 68 weighted averaging of the frames in a video segment, which is also included in the fingerprint extraction times shown in Table 3.3. It can thus be seen that TIRI- DCT is more than 3 times faster than 3D-DCT for 2-second segments used in our evaluations. 3.5.2 Performance evaluation of the similarity search algorithms As discussed earlier, an important property of a fingerprinting system is its ability to detect the presence of a query video within a large database in a fast and reliable fashion. In this section we evaluate the performance of the two proposed approx- imate search methods (the inverted file-based search and the cluster-based search algorithms) and compare them with that of the exhaustive search method (as the reference). The fingerprints are derived by using the proposed TIRI-DCT method. Fig. 3.15 shows the speed vs. total error-rate (false positive rate + false negative rate) for all the three methods. Each point is the average result of over 1800 query fingerprints (extracted from the attacked version of the videos in the database and searched in a database of the same size). In the simulations, the words are 4 bits for the inverted file-based search, and the cluster heads are 6 bits for the cluster-based search. It can be seen that both approximate search algorithms are much faster than the exhaustive search when error rates are low (the desired operation point of the system). It can also be seen that the proposed cluster-based approach is faster than the inverted file-based search. Table 3.4: Comparison of the performance of exhaustive search (Exh.), in- verted file-based similarity search (Inv.), and cluster-based similarity search (Clu.). Attack TPR FPR F-score Exh. Clu. Inv. Exh. Clu. Inv. Exh. Clu. Inv. Noise 99.24 98.62 98.19 0.66 1.21 1.63 0.99 0.99 0.98 Brightness 99.40 99.22 99.20 0.60 0.75 0.77 0.99 0.99 0.99 Contrast 99.02 98.83 98.81 0.75 0.78 0.80 0.99 0.99 0.99 Rotation 99.57 98.93 98.45 0.43 1.06 1.54 1.00 0.99 0.98 Time shift 95.8 93.46 93.08 1.73 2.12 2.49 0.98 0.97 0.96 Spatial shift 96.25 92.61 91.86 1.85 2.61 3.37 0.98 0.96 0.95 Frame drop 98.39 96.94 96.54 0.78 1.41 1.81 0.99 0.98 0.98 Average 98.24 96.94 96.59 0.97 1.42 1.77 0.99 0.98 0.98 69 1 2 3 4 5 6 70 5 10 15 20 25 30 Time (ms) Er ro r i n m at ch in g (% ) Exhaustive Inverted file−based search Cluster−based search Figure 3.15: Error vs. search time for different search algorithms applied on fingerprints derived by TIRI-DCT. Table 3.4 presents the average performance of the proposed approximate simi- larity search algorithms on the queries used for generating Table 3.2 results. Table 3.4 and Fig 3.15 highlight the trade-off between the system’s performance and its detection speed, where decreasing the detection time by about 4 times has re- duced the F-score by about 1%. Table 3.4 shows that both search methods have a performance close to the exhaustive search for noise addition, brightness and con- trast change, and rotation. The performance of the search algorithms, however, decreases for attacks such as time shift or spatial shift. To further increase the performance of the search algorithms, we have deployed a simple post-processing approach. The post-processing module exploits the ex- isting temporal dependency between adjacent fingerprints to correct the detection results. It corrects the index of a video segment (current segment) by looking at its adjacent segments (here 4 segments before and 4 segments after the current segment). If more than 50% (here, 5 or more) of these segments have the same video index, the segment is assigned the same index. Using this post-processing approach, we were able to boost the performance as shown in Table 3.5. It can be seen from Table 3.5 that the applied post-processing has boosted the system’s performance by increasing the TPR as well as decreasing the FPR. The effect of the 70 Table 3.5: Performance of the system after adding the post-processing mod- ule Attack TPR (%) FPR (%) F-score Clu. Inv. Clu. Inv. Clu. Inv. Noise 99.12 98.98 0.80 0.94 0.99 0.99 Brightness 99.07 99.06 0.91 0.92 0.99 0.99 Contrast 98.61 98.61 0.98 0.99 0.99 0.99 Rotation 99.19 99.13 0.81 0.87 0.99 0.99 Time shift 95.00 94.88 1.19 1.32 0.98 0.98 Spatial shift 93.82 93.56 1.53 1.77 0.97 0.97 Frame loss 98.39 98.37 0.80 0.83 0.99 0.99 Average 97.60 97.50 1.00 1.09 0.99 0.99 applied post-processing step can specifically be seen for more severe attacks such as time shift and spatial shift, where the FPR is decreased to about half its original value. Tables 3.5, 3.4, and Fig. 3.15 show that the cluster-based search algorithm is faster than the inverted file-based approach while it also has a better detection performance. We thus adopt the cluster-based algorithm as the search engine for our copy detection system. In the next Section, we propose and evaluate a secure version of the proposed fingerprinting algorithm. 3.6 Security We mentioned that the security of a fingerprinting system is important for appli- cations such as copyright protection where the performance may be compromised by adversaries. First, let us explain how an adversary can compromise the perfor- mance of the system. If the adversary knows the algorithm, he can modify a copied video to generate a desired fingerprint and thus have it approved by the system as an original video. Alternatively, if he has a video in the database, he can modify another video that does not belong to the database to result in the same (similar) fingerprints and thus have it approved as a copy. For example, with TIRI-DCT, the attacker can find the blocks whose first horizontal or vertical coefficients are close to the median value and slightly change them to generate a complete different fin- gerprint. However, if the coefficients are selected randomly (using a randomly generated secret key), the attacker will not know the set of coefficients to calculate 71 the median and thus cannot compromise the system. In this section we propose a secure version of our fingerprinting algorithm that uses such a technique to pre- vent adversaries from tampering with the system. This algorithm is denoted as the Secure TIRI-DCT. To have a secure algorithm, randomness is introduced to the algorithm via two secret keys. Each key is a randomly selected vector of integers defining a certain procedure to be performed. We explained in Section 3.3.2, that the TIRI-DCT algorithm generates fingerprints by segmenting a TIRI image into n overlapping blocks and extracting two feature (the first two non-DC DCT coef- ficients) from each block. In the Secure TIRI-DCT one feature is extracted from each block. This feature is selected from the set of the first three non-DC DCT coefficients, and the first key defines the coefficient to be selected. The second key permutes all the selected coefficients and generates a randomly arranged fea- ture vector. The feature vector is then binarized using the same method used for the original TIRI-DCT. Assuming that a TIRI image is divided into L blocks. For Secure TIRI-DCT, there would be 3L ×L! different possibilities of feature combi- nations (as there are 3 choices for each block, 3L is then multiplied by the number of permutations for L blocks). This randomization procedure results in a highly secure fingerprinting system, which makes it almost computationally impossible for an intruder to extract the same fingerprints from a video without knowing the keys. To analytically evaluate the security of a fingerprinting system from the point of view of an adversary, Swaminathan et al. have proposed the use of entropy (or the differential entropy) of the generated fingerprints [25]. The entropy shows how hard it would be for an intruder who knows the algorithm but does not have any in- formation about the secret keys to estimate the fingerprint. For our proposed secure TIRI algorithm, the entropy of the intermediate fingerprints (before binarization) is L log 3+∑Lk=1 log k, which is derived for the case when the keys are independently drawn from a uniform distribution. However, the entropy of the final fingerprint N(hL), after binarization, is much lower and is equal to log (L/2 L ) . This entropy can be found using a recursive formula: N (hL) = N (hL−2)+ log(L(L−1))−2log(L/2) (3.8) 72 The entropy of the final-stage fingerprints determines the actual amount of ran- domness in the generated fingerprints. This entropy is usually much lower than the entropy of the intermediate features studied in [25]. Last but not least, entropy is not a good measure, because it does not consider the prior knowledge of the ad- versary. In fact, it should be practically impossible for an intruder who knows the fingerprinting algorithm to estimate the fingerprints without knowing the secret key even though he has some sample fingerprints. For example, for Secure TIRI-DCT, the use of the two secret keys mentioned above decreases the amount of informa- tion revealed by the sample fingerprints about the keys. If only the permutation (first) key were used, the key could be found with a high probability, given enough sample fingerprints. When both keys are used, it is much harder for the intruder to guess them (based on the available samples) although the entropy does not change (by adding the second key). We now show that the performance of the system is independent of the selected keys. Fig. 3.16 shows the performance of Secure TIRI-DCT for frame losses of 5% to 70% and time shifts of −0.5Sec to 0.5Sec, when different keys are used (1000 keys were randomly selected). Each key is used for generating the database as well as extracting the query fingerprints from the attacked videos. 0.1 0.2 0.3 0.4 0.5 0.6 0.93 0.94 0.95 0.96 0.97 0.98 0.99 1 Frame loss fd ( a ) F 0 .5 −0.5 0 0.5 0.84 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1 Time shift δ ( b ) F 0 .5 Figure 3.16: F-score for different keys for different parameter values when the video is attacked by (a) frame loss (b) time shift. Fig. 3.16 shows how small the F-score is affected by choosing different DCT coefficients (features) as the result of using the selection key. The bars on the 73 plots show the variance of the F-score for different parameters and different keys. Similar observations apply to other attacks, which further demonstrates that Secure TIRI-DCT performance is not significantly affected by the selected keys. Figure 3.17: Amount of change in the average TPR, FPR, and F0.5 when the security is added to the system. Fig. 3.17 quantifies the trade-off between security and the system’s perfor- mance, represented by TPR, FPR, and F-score. The bars in the chart show the amount of change in TPR, FPR and the F-score. On average, TPR decreases by about 3%, FPR increases by about 1.2%, and F-score increases by about 1.7%. These results indicate that security is gained at the expense of a slight reduction in the system’s performance. The gap in the performance can be improved further by increasing the length of the fingerprint. The above results represent the perfor- mance of secure 64-bit fingerprints versus that of non-secure 126-bit fingerprints. When comparing secure and non-secure systems with fingerprints of lengths 320 and 640, we observe that, on average, the TPR of the secure system decreases by 1%, FPR increases by 0.3%, and F-score decreases by 0.5%. These results show that security can be achieved with a small detection performance loss by using a larger fingerprint length. It is, however, worth mentioning that longer fingerprints result in a decrease in detection speed as they require more computation when cal- culating the Hamming distances between the fingerprints. 74 3.7 Summary This chapter proposes a fingerprinting system for video copy detection. The sys- tem can be used for copyright management and indexing applications. The system consists of a fingerprint extraction algorithm which we call TIRI-DCT followed by a fast search method. The proposed (TIRI-DCT) algorithm extracts robust, dis- criminant, and compact fingerprints from videos in a fast and reliable fashion. These fingerprints are extracted from temporally informative representative im- ages (TIRIs) containing both spatial and temporal information about a video seg- ment. We demonstrated (on a database of 200 videos) that TIRI-DCT generally outperforms the well-established (3D-DCT) algorithm and maintains a good per- formance for different attacks on video signals, including noise addition, change in brightness/contrast, rotation, spatial/temporal shift, and frame loss. It is shown that TIRI-DCT has a high average true positive rate of 98.2% and a low average false positive rate of 0.97%. We also proposed two fast approximate search al- gorithms: the inverted file-based method which is a generalization of an existing search method, and another method based on a novel clustering-based approach. Analytical and experimental studies demonstrated that both algorithms are very fast compared to an exhaustive search and maintain a good performance. The cluster-based method is shown to be superior to the inverted file-based method in terms of detection performance and the retrieval time. We have thus adopted the cluster-based method as the search engine of our fingerprinting system. By apply- ing a simple post-processing method, the final system performance yields a high average TPR of 97.6% and a low average FPR of 1.1%. As security of the fingerprinting system is important for some applications such as copyright protection, we also introduced a secure version of our algorithm, de- noted as Secure TIRI-DCT. We showed that the use of this algorithm makes it extremely difficult for an adversary to tamper with the fingerprinting system. The increase in the security is, however, associated with a slight decrease in the perfor- mance. Security is an area of research that still needs much more attention. 75 Chapter 4 Fingerprint Matching 4.1 Problem description Nearest Neighbour (NN) or k Nearest Neighbours (K-NN) search is the problem of finding the closest match or matches for a given query signal in a set of reference signals. Many signal processing applications, such as digital rights management or biometric authentication involve NN search. For example, to identify a person in the airport using his iris, his eye scan is fed to a biometric authentication system. This system searches for a potential close match (to the eye scan) in a database of hundreds of thousands of eye scans, in a fast and accurate fashion. Another exam- ple is detecting copies of multimedia assets using content-based fingerprints which is the topic of this dissertation. A multimedia fingerprinting system detects whether or not a given query object (audio, video, or image) is a copy of another multime- dia object by comparing their fingerprints1 . To do so, first, a fingerprinting process extracts fingerprints from the query. Then the retrieval process runs a search on the fingerprint database (previously extracted from the multimedia objects in the database) to find a match for the extracted query fingerprints. A match between the fingerprints represents a match between their corresponding multimedia objects. As mentioned in Chapter 1, the fingerprints of a multimedia object and its copy are very similar but they are not necessarily identical. Therefore, the retrieval pro- 1As mentioned in Chapters 1, 2, and 3 fingerprints are compact signatures that are extracted from a multimedia object based on its perceptual content. 76 cess should look for the closest fingerprint in the fingerprint database (not an exact match) and is basically a NN search process. Multimedia copy detection systems, usually deal with very large databases of multimedia objects, e.g. YouTube’s huge video database. This makes NN search the computational bottleneck of these sys- tems. We have extensively talked about the challenges in fingerprint extraction in Chapters 2 and 3. We also discussed the problem of search for a specific video fingerprinting algorithm in Chapter 3. In this chapter we discuss the problem of fingerprint retrieval in more details and in a general scenario. First we introduce a novel strategy to extract fingerprints of time-based multi- media signals (audio and video) that facilitates a fast search process. Unlike im- ages, audio and video signals are spread along time. Thus, a copy of audio or video may contain only parts of the original signal cropped along the time axis. To be able to detect copies of videos and audio, many existing algorithms extract fingerprints from different windows (along time) of audio or video signals. Because copies can be extracted form any part of the original signal, time windows are forced to have overlaps to deal with time misalignments (between the boundaries of a windows of the original signal and those of the cropped copy). To increase the accuracy of detections time overlaps between adjacent windows should be large enough. This in return results in an increase in the size of the fingerprint database and a decreases in the search retrieval speed. However, if the overlapping scheme applied on the query signal is allowed to be different from that of the objects in the database, one can minimize the time misalignments and at the same time keep the database size minimal. We propose such an overlapping scheme. We then propose a novel state machine-based matching algorithm that uses the proposed window overlap- ping scheme to significantly increase the search speed. The overall performance of the proposed scheme is analysed in Section 4.3.2. We also consider the problem of NN search in a general fingerprinting system, i.e. finding the closest match for a given fingerprint in a database of fingerprints. We propose a fast approximate NN search algorithm for the Hamming space, i.e. for binary fingerprints. Similar to the video fingerprinting algorithm that we proposed in Chapter 3, many fingerprinting and in general feature extraction algorithms are resorting to binary descriptors. The applications of the proposed NN search are 77 not limited to fingerprinting systems. Examples of possible application areas are biometric authentication, object recognition, information retrieval and any other systems that use an NN search in the Hamming distance. The proposed algorithm reduces the retrieval time by an order of magnitude compared to the state-of-the- art, without any decrease in the detection accuracy. With the same retrieval speed it is an order of magnitude more accurate than existing approaches. The proposed NN search algorithm is discussed in Section 4.4, and the results are presented in Section 4.5. The rest of this chapter is organized as follows: in the next section, we give an overview of the related work in the area of fingerprint retrieval. In Section 4.3, we we will present our novel fingerprinting strategy that facilitates fast fingerprint retrievals for audio and video signals. We evaluate the proposed system using the fingerprints proposed in Chapter 3. In Section 4.4 we propose and mathematically analyse our proposed NN search algorithm. In Section 4.5, we evaluate the perfor- mance of the proposed search algorithm and compare it to the state-of-the-art for NN search in the Hamming space. We summarize the chapter in Section 4.6. 4.2 Related work Many fingerprinting algorithms generate binary fingerprints to reduce the storage space, to increase the robustness, and to facilitate the search process [56, 57]. Vari- ous video, audio, and image algorithms that use binary fingerprints have been pro- posed for different applications such as copyright protection [58, 24] and biometric authentication [59]. Object recognition based on local feature points of images is another application area that is moving towards using binary descriptors for fast computations [60–62]. Recently, machine learning-based approaches have been proposed for convert- ing the high dimensional feature vectors used in document retrieval and machine vision (usually in Euclidean space) to low dimensional binary vectors. For exam- ple, a graphical model to learn a binary embedding called semantic hashing for efficient document retrieval has been proposed [63]. Semantic hashing defines the binary embedding of a document in such a way that the Hamming distance between binary hash vectors of similar documents has a small value. Spectral hashing is an- 78 other embedding technique that generates concise binary hashes [64]. The binary hashes generated by the spectral hashing method are balanced, i.e. they have equal number of 0’s and 1’s. Weiss et al. perform spectral hashing by thresholding the set of the eigenvectors corresponding to minimal eigenvalues of the Laplacian of the similarity graph. Chaudhry et al. [65] extend spectral hashing to non-Euclidean manifolds. A binary embedding scheme proposed in [57], generates the hash vec- tors by solving an optimization problem that minimizes the error between the ob- jects distance and the Hamming distance between their reconstructed hash vectors. Because of their simplicity, binary hashes are becoming more and more popular in many signal processing and machine learning tasks. Although many papers have studied NN search for Euclidean spaces, only a handful of papers have focused on the Hamming (i.e. binary) space [18, 66–68, 58, 24]. Locality Sensitive Hashing (LSH) is a prominent algorithm in the NN search literature [18]. The majority of existing NN search algorithms for binary vectors are based on the popular LSH algorithm. Unfortunately, the improvements offered by these methods over the original algorithm in terms of accuracy or speed are not significant. LSH is built on a simple idea: assume two binary fingerprints (vectors) that are close in the Hamming space, i.e. they differ only in few bits. If a sub- vector is extracted from each of them in the same fashion, then the probability of these sub-vectors being identical will be high. LSH reduces the search space by considering only those fingerprints that have identical sub-vectors with the query fingerprint. LSH builds a hash table of fingerprints for each sub-vector as the key, to accelerate the retrieval process. Charikar et al., proposed another LSH-based search algorithm in [66]. In their method, all the database fingerprints whose permuted versions are lexicograph- ically close to the permuted versions of the query are retrieved. We study and compare these two versions in Section 4.5. References [58] and [24] propose ap- proaches similar to the original LSH, but instead of choosing the sub-vectors ran- domly they divide each fingerprint into non-overlapping segments (called words and sub-fingerprints). A kernelized LSH is proposed in [69]. In the original LSH algorithm, some fingerprints are read multiple times from different hash tables. Hao et al. [59] took advantage of this property to further reduce the number of candidates. In their algorithm, called Beacon Guided Search (BGS), they only con- 79 sider the candidates that have occurred at least a specific number of times defined by the collision count parameter. This solution significantly reduces the number of candidates and decreases the retrieval time. However, it also decreases the detec- tion accuracy as we will explain later. For the original LSH and similar algorithms, if none of the hash vectors of the query are identical to those of the nearest neighbour, the algorithm fails to include the nearest neighbour in the candidate list. This failure can happen for the LSH algorithm in [66] when there are errors in the first few bits of the hash vectors. Depending on the application, this failure can lead to a false positive or a false rejection. The probability of such a misdetection depends on the distance of the query from its nearest neighbour in the database. The probability of misdetection for LSH increases as the NN distance increases. To alleviate this problem, Haitsma et al. proposed the notion of ”weak bits” [50]. In their algorithm, a stability score is assigned to each bit. Less stable (weaker) bits are each toggled to generate multiple pseudo queries from a single query. The results from all the generated queries are then aggregated. The algorithm requires that the stable bits of the query are correctly identified, otherwise it fails [70]. Since weak bits are highly dependent on the distortions that the query has gone through and cannot be identified with high confidence for all fingerprinting algorithms, the weak bit scenario is not reliable. In this chapter, we propose a new approximate search scheme that significantly increases both the search speed and its accuracy, using the notion of error-weighted hashes. The proposed algorithm can be optimized to work under arbitrary large NN distances. The problem of copy detection for audio and video signals is even more compli- cated because each signal contains many fingerprints. After finding nearest neigh- bours for each of the extracted fingerprints, a post-processing module is required to aggregate the results. For example, in [71] a real time system for finding dupli- cates in TV broadcasts has been proposed. The system finds one-second long du- plicate sequences and a post-processing algorithm then assembles these (short) de- tected segments and exactly determines the first and the last frames of each copied sequence. In their algorithm, however, the query fingerprints are still matched independently. Before proposing our NN search algorithm, we first introduce a new fingerprinting scheme that facilitates fast searches for audio and video signals. 80 We also propose a matching algorithm that eliminates the required post-processing module by reducing the need for matching each fingerprint independently. 4.3 Fast copy detection for audio and video signals Video and audio contents change along the time axis. A user can crop parts of an audio asset or a set of consecutive frames in a video and share them with other people. The copy detection system should be able to detect and localize the time position of such copies within the original content. To fulfil this objective, multiple fingerprints are extracted from an audio or a video asset [58, 72, 24, 34, 45, 71, 48]. Different fingerprints extracted from an asset should be able to accommodate the content temporal changes. For simplicity, here, we focus our attention on video fingerprinting systems. However, the same idea applies to audio fingerprinting systems as well. While some proposed fingerprinting systems extract the fingerprints from cer- tain key-frames, many of the algorithms use window-based approaches, i.e. a fin- gerprint is extracted from every consecutive T seconds of the video/audio asset. Because copies are usually cropped from the original videos, a copied version and the original video may have different windows’ starting points. This difference decreases the accuracy of a fingerprinting system. To cope with this problem, win- dows are forced to have overlaps. For example in the algorithm we proposed in Chapter 3, at every second of the video t, a fingerprint is extracted from a 2-second window (t, t + 2). This creates an overlap of one second (50%) between adjacent windows. To increase the detection rate the overlap may be increased, but this in return results in an increase in the size of the database and a decreases in the search time. Apart from the database size issue, video/audio segments that have overlaps (or contain similar scenes) usually have similar fingerprints. This similarity be- tween the fingerprints can have an adverse effect such that the query segments are matched to the wrong window within the original video. Such misalignments in- crease as the amount of overlap increases. For conventional approaches, every fin- gerprint in a query is searched in the database independently. When there are many misalignments, a post-processing algorithm is required to re-align and aggregate 81 the detection results. In the following section we propose an effective windowing scheme and an accompanied search process that not only reduces the database size, but also eliminates the need for a post-processing step. In Section 4.3.2, we test our proposed scheme on the TIRI-DCT algorithm we proposed in Chapter 3. We also compare our proposed approach to the conventional approach (where query object and database objects have the same windowing scheme) in terms of accuracy and speed. 4.3.1 Windowing scheme and the matching algorithm The conventional approach for increasing the detection accuracy and coping with temporal misalignments in window-based fingerprinting algorithms is to force large overlaps between adjacent windows. The overlap is forced for both when gener- ating the fingerprint database from the original videos and when extracting finger- prints from the query video. For example, in the proposed TIRI-DCT algorithm in Chapter 3, we applied a 50% overlap between the video segments that were used to generate TIRI’s both for videos in the database videos and for the query videos. Fig. 4.1 (a) and (b) show a video from the database and a query video, each with 50% overlap between their segments. Because of cropping, the windows of the query and the original video may not be aligned. Misalignments are studied under the time shift attack as mentioned in Chapter 3. The larger the overlap, the more robust will be the algorithm to time shifts. Increasing the overlap, on the other hand, decreases the retrieval speed by increasing the fingerprint database size. For example increasing the overlap between the windows from 50% to 75% doubles the size of the database (this can cause storage problems as well). Increasing the overlap also decreases the chance of accurate localization of copied segments in the database. This is due to fact that a large amount of overlap between adjacent windows, results in creating many similar fingerprints. In this case even if all the query windows are assigned to the correct song, there might be many miss-alignments caused by matching a window in the query to another location in the original video that is visually similar. Since copies are usually formed by modified versions of the original videos, the true matching window might have a more distant fingerprint than that of another window which is similar 82 to the true match. The problem is doubled when dealing with videos that have repeating scenes. Fig. 4.2 shows an example of how the output of the search can look like in such a situation. We measure these misalignments in terms of detection jitter. Jitter measures the time difference between the location of the true match in the original signal corresponding to a time window in the query signal and the location of the match that was detected by the algorithm. When the jitter is high, the copied segment in the query video cannot be accurately localized in the original video or (even worse) it cannot be localized at all. To address the above problems, we propose applying a windowing strategy for original videos in the database that is different from that for the query videos. In our proposed strategy, the fingerprint database is generated from the videos in the database with no overlap between adjacent windows. This minimizes the size of the fingerprint database. The query video, on the other hand, is fingerprinted using large overlaps between adjacent windows. Fig. 4.1 (c) shows the windowing process on a video in database and Fig. 4.1 (d) shows the corresponding process on the query video for the proposed approach. Note that fingerprint extraction algorithms are usually fast and extracting many fingerprints from the query does not severely affect the computational efficiency of the copy detection system. The proposed strategy minimizes the size of the fingerprint database as well as the amount of dependencies between the database entries. The generated database can therefore be stored and searched more efficiently. The large overlap between the fingerprints of the query video, on the other hand, enables accurate localization of the copies within the database. However, the problem of jitter still exists and a rigorous post-processing is required before generating a tangible output. Moreover, although the search time for a single fingerprint is reduced due to a smaller database size (compared to the conventional approach), more fingerprints are generated per query video and the total search time can be even larger. We now propose a copy detection system, using the above windowing strategy, that addresses the above problems, i.e. decreases the jitter, increases the search speed, and at the same time eliminates the need for post-processing. Fig. 4.3 shows the proposed copy detection system based on the discussed windowing strategy. The system starts with creating the fingerprint database from the original videos in the database. Every video in the database goes through some 83 Figure 4.1: Conventional windowing strategy for (a) database videos (50% overlap), (b) query videos (50% overlap). The proposed windowing strategy for (c) database videos video (no overlap) (d) query videos (maximum overlap). pre-processing operations such as filtering, de-noising, scaling, etc. It is then seg- mented into ”non-overlapping” windows of length T seconds. Each segment is then passed to the fingerprint extraction engine to generate its fingerprint. The fingerprint along with some associated meta-data such as the video ID and exact 84 Figure 4.2: An illustration of an output of a window-based fingerprinting algorithm when the input video contains repeated or slowly changing scenes (a) True time correspondence between the query video (bottom) and the database video (top) (b) The found matches between different time windows using the fingerprinting algorithm. temporal location of the corresponding segment within the video is then stored in the fingerprint database. The system follows the same procedure for extracting fin- gerprints from the query. The only difference is in the windowing strategy. For a given query, each T second-long segment is extracted every τ seconds (T > τ). Therefore, there is an overlap of T − τ between consecutive segments. The finger- prints of the query video are otherwise generated using the same parameter values used to generate the fingerprint database. The query fingerprints are then passed to a matching block, where the search for possible matches between the extracted query fingerprints and the fingerprints stored in the database happens. The match- ing block also precisely localizes the copied segments in the query and in the video database. This matching block is called the Matching State Machine (MSM). Fig. 4.4 illustrates an example of an MSM with 9 states: 4 no match states, a test state, and 4 match states. The number of the states can be chosen as described later. In the no match states, we assume that no potential match has been found yet. Therefore, each state tries to find a match for the requested query fingerprint in the database. When a candidate match is found by any of these states, the process enters a tran- sient test state. The test state determines if the found candidate is actually a match. If this is confirmed, the process enters the match states, starting from state ’11’. The match states, are responsible for extending the match to consecutive segments of query and the candidate video as well as further tuning the temporal position of 85 Figure 4.3: Schematic of a multimedia copy detection system based on the proposed windowing scheme. the matched windows within the query so that the query sequence and the detected segments in the original video are synchronized. If at any point this process fails, it returns to the no match states. Let us now explain the operation of MSM in more details using the example shown in Fig. 4.4. Please note that for ease of repre- sentation, Fig. 4.4 does not show all the conditions and the operations explained below. For a new sequence of query fingerprints, the MSM always starts at state ’01’, i.e. the default state. For a fingerprint that is in state ’01’ (top left), its near- est neighbour in the fingerprint database is found. To find the nearest neighbour, one can perform an exhaustive search or other fast approximate search algorithms available including Locality Sensitive Hashing (LSH) [18], or inverted table search [58, 24] or the algorithm that we will propose in Section 4.4. The nearest neigh- bour search algorithm returns the closest fingerprint in the database along with its distance to the query fingerprint. If the nearest neighbour distance, D, is greater than some pre-defined threshold, σF , the next fingerprint in the query sequence (ex- tracted from a window τ seconds later) is examined in state ’02’. State ’02’ runs the nearest neighbour search algorithm on this fingerprint. If the nearest neighbour distance is still greater than σF , the process enters state ’03’. Here, the fingerprint that is ατ (α > 1) away from the current fingerprint is analysed. Until some match is found, the process is continued by going to higher no match states. In each no 86 Figure 4.4: An example of the Matching State Machine (MSM). The state machine is terminated when the last query fingerprint is examined. match state, the step size determines the next query fingerprint to be examined. Each time the machine jumps to a higher no match state, the step size is multiplied by α . In the final no match state, the step size does not change (the state loops back to itself). In Fig. 4.4, there are 4 no match states and T is the maximum step size. A maximum step of T , causes the entire query video to be scanned. The number of no match states and the maximum step size can, however, have any values based on the accuracy and the speed required. If the nearest neighbour distance is found to be less than or equal to σF in any of the no match states, the corresponding fin- gerprint qt in the query, and its corresponding nearest neighbour in the database, fi, j are passed to the test state. For fi, j, i, j means that the fingerprint belongs to database video whose Id is i and is extracted from its jth segment, i.e. from the frames between times ( j−1)T and jT . In the test state, the fingerprint qt of the query and the set of fingerprints of the query that were extracted from adjacent windows up to T seconds far from t, i.e. 87 {qt ′ |t−T < t ′ < t+T}, are compared to the detected nearest neighbour fi, j. If any of the fingerprints has a distance of less than or equal to the pre-defined thresh- old σD then a match with the database at the corresponding location is confirmed. Please note that, the amount of misalignment is being minimized so σD ≤ σF . Now, let us assume this happens at time t∗. The process then enters a series of match states. The match states are responsible for extending the detected match to consecutive segments of both original video (i in this case) and the query video. They also minimize the amount of misalignment as they proceed with this exten- sion. To be more specific, qt∗ and fi, j are passed from the test state to state ’11’. In this state all query fingerprints {qt̃} in the vicinity of T/β from qt∗ , i.e. {qt̃ |t∗− T/β < t̃ < t∗+T/β}, are compared to fi, j. The one with the shortest distance, e.g. q∗∗t is then registered as a match to fi, j. If t∗∗ in state ’11’ is within T/β 2 range of t∗, the machine enters state ’12’. Otherwise, it remains in state ’11’. Regardless of the match state, for the next set of comparisons, both query and the potential match are advanced by T seconds, i.e. qt∗∗+T and fi, j+1 are examined next. Note that due to distortions, the query sequence may not be exactly time- aligned with its corresponding original video. This time-gap shrinks as the match- ing process enters higher states ’12’, ’13’, and so on. Ultimately, it reaches 0 in the final match state, which loops back to itself (here ’14’). The number of the match states depends on the accuracy and the speed required. In our implementation, we used four states as shown in Fig. 4.4. All match states conduct the same task. However, they use a different range for which the query fingerprints are compared against the potential match in the database. This range eventually decreases for higher states. If the shortest distance query in a match state is within the range of a higher state, the machine enters the higher state, otherwise it remains in the current state. In any match state, if all the query fingerprints in the current range have a distance greater than σD or when the last fingerprint in the detected original video (here i) is examined (i.e. when the match is lost) the process switches back to the no match state ’01’. The state machine is terminated when the last query fingerprint is examined. In our implementation, we have used the same number of states as shown in the Fig .4.4. we have also chosen the rest of the parameter val- ues as follows: τ = 0.25, T = 2, α = 2, and β = 2. In the next section, we present 88 the performance results of the proposed algorithm and compare them against those obtained from the conventional approach. 4.3.2 Evaluation of the proposed windowing scheme In this section, we compare our proposed windowing and search strategy against the conventional strategy where the fingerprinting windows have the same overlap for both the query as well as the videos in the database and each query fingerprint is independently searched in the database, e.g. the approach followed in [58] or [71]. For simulations we used the binary video fingerprinting algorithm proposed in Chapter 3. For the database, we used over a 1000 videos collected by our re- search group at UBC [73]. We present the results in two parts. In the first part, we have control over how much distortion to introduce in the copied windows. A number of 100 videos are used as the database and the performance is analysed as a function of the amount of window overlap and the Bit Error Rate (BER). Here, BER represents the number of erroneous bits between the fingerprints of an original video segment and that of its distorted copy. We assume that errors happen due to distortions such as noise, frame dropping, changes in the brightness, etc (but not as a result of time shifts). We measure the performance in terms of the detection rate (TPR) and the detection jitter. Detection jitter is defined as the average amount of time misalignments be- tween the consecutive query segments and the corresponding detected segments of the original video in the database. In the second part of our analysis, we conduct a real-world situation analysis. We compare the algorithms over the whole database (over 1000 videos). The query fingerprints are extracted from mash-ups created by mixing random segments of the videos in the database and applying video compression to the whole mash-up. Therefore, in this study we have no control over the introduced BER. Mash-ups are becoming more and more common on video sharing websites. The compression emulates the distortions that happen to the cropped videos due to different video codecs. 89 Detection rate and detection jitter For the simulations in this section, we randomly select 100 videos from the database. For precise comparison of the algorithms, we use a brute-force approach to find the nearest neighbour in the no match states. First, we compare the performance of our proposed method to the conventional approach when the amount of over- lapping increases. Please note that increasing the amount of overlap has no effect on our proposed method, however, it affects the performance of the conventional approach. For queries we randomly extract 40 second snippets from the selected videos and apply random errors on the extracted fingerprints. Using this scenario, we had control over the number of erroneous bits. For this study, the bit error rate was set to 0.1. Fig. 4.5 shows the detection performance, the detection jitter, and the retrieval time for a range of window overlap values of about 90% to 0%. It can be seen from the figures that the proposed approach has a high steady detection rate (> 95%). The detection performance of the conventional approach is higher for large amounts of overlap, which in turn leads to upto about three orders of magnitude longer search times compared to the proposed approach (which is upto 900 times faster). The conventional approach also has a high jitter. For our proposed method, the jitter is almost negligible (below 100ms per second). A high jitter means that the detected windows in the query have large temporal differences and there have been many time misalignments. For the conventional approach, where a post-processing block should aggregate the detected results, large jitters can make this task almost impossible and make the detections useless. For compa- rable detection performance rate, happening at 50% overlap, our proposed method is more than 70 times faster, while it has a very low jitter compared to the conven- tional method. We now compare the algorithms when the bit error rate changes from 0 to 0.2. An overlap of 50% is used for the conventional method in this study. Results in Fig. 4.6 show the same performance trend. The proposed method has a steady performance with a low jitter, a high detection rate, and a very low retrieval time. On the other hand, the conventional method has an increasing jitter, a steady large retrieval time, and a detection rate that abruptly drops for large bit error rates. 90 87.5% 75% 50% 25% 0% 0.75 0.8 0.85 0.9 0.95 1 Overlap (a) D et ec tio n ra te (T PR ) Propsed Conventional 87.5% 75% 50% 25% 0% 0 0.2 0.4 0.6 0.8 1 1.2 1.4 Overlap (b) D et ec tio n jitt er (s) Propsed Conventional 87.5% 75% 50% 25% 0% 0 1 2 3 4 5 Overlap (c) R et rie va l t im e (s) Propsed Conventional Figure 4.5: Performance results when the overlap changes, (a) Detection rate, (b) Detection jitter, (c) Retrieval time. Performance evaluation using mash-ups In this section, we compare the two algorithms in a real-world setting where there is no control over the amount of BER. We use all the 1016 videos available from [73]. For the queries, we create mash-ups composed of 40 to 60 second snippets cropped randomly from the videos in the database. Each snippet was excessively compressed (with an output bit-rate of below 200kb/s). For the search algorithm in the no match states in this study, we used the fast approximate search algorithm proposed in Section 4.4. Fig. 4.7 shows an example of the detection results on a random 40-second snippet in one of the mash-ups. It can be seen that for the conventional method, the detected segments have 91 0 0.05 0.1 0.15 0.2 0.85 0.9 0.95 1 Bit error rate (a) D et ec tio n ra te (T PR ) Propsed Conventional 0 0.05 0.1 0.15 0.2 0 0.5 1 1.5 2 Bit error rate (b) D et ec tio n jitt er (s) Propsed Conventional 0 0.05 0.1 0.15 0.2 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 Bit error rate (c) R et rie va l t im e (s) Propsed Conventional Figure 4.6: Performance results for different BERs, (a) Detection rate, (b) De- tection jitter, (c) Retrieval time. large jitters and the true temporal relation between the snippet in the query and the detected original video in the database is not clear. A post-processing step, is then required to estimate the best time alignment for this case. As seen from Fig. 4.7, the proposed approach does not have this problem at all. For our proposed method the average detection rate (TPR) is 95.5%. For the conventional method TPR is 96.5%. The retrieval time for our method is 0.78s while it is 24.5s for the conventional approach, .i.e. our method is about 30 times faster. Averaged over all the detected time windows in the query, our method has a 40ms jitter (2% of the window length) while the conventional method has a 800ms jitter (40% of the window length). It can be seen that the proposed windowing 92 0 10 20 30 40 50 235 240 245 250 255 260 265 270 275 280 time (query) tim e (or igi na l v ide o) Propsed Conventional Figure 4.7: Detected time location for video segments of a randomly cropped 40-second snippet in a mash-up. strategy along with the proposed state machine-based matching algorithm offers a much faster solution with almost no jitter with only a slight decrease in the detec- tion rate. Please note that a high detection rate for the conventional method is not necessarily an advantage as the final results should be tangible and excessive jitters can render the whole detection results useless. 4.4 Approximate nearest neighbour search As mentioned in the introduction, searching for the nearest neighbour of a query fingerprint, in a pool of previously extracted fingerprints is at the heart of any copy detection system. The fact that this pool (called fingerprint database) can be hu- mongous, raises practical concerns for real time operation of copy detection sys- tems. In this section we study the problem of Nearest Neighbour (NN) search in the fingerprints space. More specifically we study the NN search problem in the Ham- ming space, as many emerging fingerprinting and feature extraction algorithms are based on binary descriptors. As of today, there has been no sub-linear (of order O(n1−ε) for any ε > 0) exact solution to the nearest neighbour search problem in high dimensional spaces. The only known existing solution is the brute-force search which is linear (O(n)) in time. For very large fingerprint databases, brute force search can be the bottle neck of copy detection, preventing real time oper- 93 ation of the system. As mentioned in Section 4.2 there has been a few papers that proposed approximate sub-linear alternatives to brute-force search. LSH is the prominent among them and many proposed algorithms are either conceptually similar to it or are its extensions. LSH is built on a simple idea: assume two binary fingerprints (vectors) that are close in the Hamming space, i.e. they differ only in few bits. If a sub-vector is randomly extracted from each of them in the same fashion, then the probability of these sub-vectors being identical will be high2. In LSH , a sub-vector is formed by concatenating m individual bits which are extracted (using a random key) from a fingerprint whose length is l (l > m). The sub-vector can thus be considered as a simple hash vector. LSH extracts such a hash vector from the query signal as well as from each fingerprint in the database. It then compares the hash vector extracted from the query to the corresponding hash vec- tors extracted from the fingerprints in the database. Any fingerprint in the database whose hash vector is identical to that of the query is selected as a candidate. This process is repeated n times. LSH runs an exhaustive search over all the selected candidates and returns the closest one to the query as the nearest neighbour. In essence, LSH reduces the search time by reducing the search space from the whole database to a small set of candidates. To accomplish this in a time efficient manner, LSH conducts a pre-processing step to generate inverted index tables (hash tables) from the fingerprints of the database objects. The inverted index table is used to find those database fingerprints who have identical hash vectors with a query. To search for a match for a query, LSH extracts n hash vectors from the query using the same parameters used for generating the database index tables. It then finds the fingerprints that have identical hash vectors to those of the query (by sim- ply reading their indexes) from the index table, adds them to the list of candidates, and finally runs an exhaustive search on the list. To further decrease the search time, the algorithm stops looking for more candidates, after a certain number of candidates have already been added to the list. One problem with LSH and similar algorithms is that they fail if there happens 2By the same fashion, we mean that for example if the first bit of a sub-vector corresponds to the fifth of one original fingerprint, then the first bit of the second sub-vector should correspond to the fifth bit of the second fingerprint and so on. 94 to be errors in all the hash vectors of the query. The probability of failure increases as the nearest neighbour distance increases. We propose a NN search algorithm that resolves this failure by taking erroneous hash vectors into consideration and by using them to generate a refined candidate list. Our proposed EWH is both faster and more accurate than the family of LSH algorithms. The size of the generated candidate list in EWH is much smaller compared to that of LSH. Similar to LSH, EWH has a pre-processing step, which is explained in Section 4.4.1. This step generates an index table from the fingerprints of the database objects. The novelty of the algorithm is in the way it retrieves the candidates from the index table as will be explained in Section 4.4.2. We will also analyse the proposed algorithm mathematically in Section 4.4.3. 4.4.1 Initialization To accomplish the detection task in a time efficient manner (similar to [24] and [18]), the fingerprints of the database objects (videos, audio, images,...) are pre- processed to generate an index table. Algorithm 1 shows how the index table is generated. The index table has M rows and n columns. The table is initialized by assigning a random key to each column (n keys in total). Each random key ki (i = 1 . . .n) determines the positions of the m bits in a fingerprint that will form one of the n hash vectors. The hash vectors determine where a certain fingerprint should be stored in the index table. The fingerprints whose corresponding hash vectors are identical, are stored in the same entry of the index table. Because an entry may contain more than one fingerprint, it is referred to as a bucket. Each column of the table has M buckets, corresponding to the M different values that an m-bit hash vector can have. Ideally M = 2m, but if m is large, the number of buckets can be too large to handle. In such a case, a practical value for M and a mapping function are used. A mapping function can be a traditional hash func- tion that maps the m-bit combination to an integer value between 1 and M [18]. The integer value defines the bucket where the corresponding fingerprint should be stored. As we will show later, m is not large in our studies, and thus we set M to 2m. With this setting, the integer value of the m-bit hash vector leads to a simple one-to-one mapping between the hash vector and a row. 95 Algorithm 1 Initialization/pre-processing of the error weighted hashing (EWH) algorithm Input: A set of distinct binary fingerprints of length l bits: F, key length: m, the number of keys: n Output: A two dimensional index table T with 2m rows and n columns. 1: for i = 1 to n do 2: Generate a random key ki = z1z2 . . .zm with z j ∈ {1,2, . . . l} for 1≤ j ≤ m 3: for all f ∈ F do 4: Add f to row H ( fki) and column i of T 5: end for 6: end for Figure 4.8: The process of adding a database fingerprint to the index table. Please note that for memory management purposes, instead of a fingerprint, its index, a unique number assigned to each fingerprint, is stored in the buckets of the table. For simplicity, however, we refer to both a fingerprint and its index as the fingerprint. In Algorithm 1, the hash vector derived from the fingerprint f using the key ki is denoted by fki . The hash value of fki (an integer between 1 and M) is represented by H ( fki) . The above process is also demonstrated in Fig. 4.8. 96 4.4.2 Error Weighted Hashing (EWH) The proposed EWH algorithm is shown as Algorithm 2. For a query q, the algorithm initially assigns a similarity score of 0 to all the fingerprints in the database. The algorithm starts with the first key, k1 and generates the hash vector qk1 from the query q. It then computes its integer hash value h0 [= H (qk1)] and assigns a similarity score α0 to all fingerprints stored in bucket h0 of column 1 of the index table. The algorithm then generates m pseudo hash vectors, such that each vector differs from qk1 by 1 bit, and calculates their m corresponding hash values, the set {h1}. It then assigns a similarity score of α1 to all the fingerprints stored in the m buckets of column 1 corresponding to rows {h1}. The algorithm continues by generating pseudo hash vectors that differ from qk1 by 2 bits, extracting their hash values {h2} and assigning a score of α2 to all the fingerprints stored in the buckets of column 1 corresponding to the rows {h2}. This procedure is repeated e times, i.e. for all hash vectors that differ from qk1 by 1,2, . . .e bits. As a result, fingerprints are weighted based on the distance between their hash vectors and the corresponding query hash vector. Fig. 4.9 demonstrates the above process for e = 2. The above procedure is repeated for all query hash vectors and all the columns of the index table. Each time the generated hash value hr (0 ≤ r ≤ e) of a query points to a bucket in the index table, the scores of all the fingerprints in that bucket are increased by the appropriate weight αr. Thus, the algorithm results in a scored list of indices, with each score representing a level of similarity between the query and the corresponding fingerprint in the database. It can be seen that the list gen- erated by EWH can be orders of magnitude larger than the one generated by LSH. Thus LSH is more memory efficient than EWH. However, this does not mean that EWH runs the exhaustive search on a larger set. In fact, EWH only selects the fin- gerprints with high scores, e.g. those with a score greater than s0, as the potential candidates. This potential candidate list as we show later, is orders of magnitude smaller than the list generated by LSH making EWH much faster. Similar to LSH, EWH calculates the actual Hamming distance between these candidates and the query and returns the candidate nearest to the query. Large values of e and m can create combinatorial explosion of the pseudo- 97 Algorithm 2 Error weighted hashing (EWH) Input: Query fingerprint q, fingerprint database F, index table T (2m rows and n columns), a set of weights {αr} (0≤ r ≤ e), the similarity threshold s0 Output: Nearest neighbour(s) of q 1: Initialize the score to 0 for all the fingerprints in the database 2: for i = 1 to n do 3: Find h0 [= H (qki)] the hash value for qki 4: Add α0 to the score of each fingerprint in column i and row h0 5: for r = 1 to e do 6: Find {hr}, the set of hash values for all binary vectors that have r-bit difference with qki . 7: Add αr to the score of all fingerprints in buckets in column i correspond- ing to rows {hr}. 8: end for 9: end for 10: Choose the fingerprints whose score is greater than s0, as candidates. 11: Run an exhaustive search on the candidates [based on the Hamming distance] and return the nearest neighbour(s). hash generation phase. We will show, however, that for even very large databases, rather small values of m and e generate very accurate results. On the other hand, if a stability measure is available for individual bits of the query fingerprint, this extra information can be used to decrease the number of pseudo hash vectors generated by a great extent. To be general, we do not assume availability of such measure and thus examine all the possible pseudo hash vectors. To speed up the search process, we pre-calculate and tabulate the pseudo hash values for every possible hash vector. 4.4.3 Analytical study of the algorithm In this section, we mathematically analyse the EWH algorithm and explain how the parameters of the algorithm (m,n,e,{αr},s0) should be determined. For finding the optimal values for these parameters we need to know the distribution of the similarity score s that is assigned to the fingerprints by the algorithm. We first drive an estimation for the distribution of s in the next section and then continue with finding the optimal values for the parameters. 98 Figure 4.9: A demonstration of EWH with e = 2: How the hash vectors (here qk1) are processed. The process continues for all query hash vectors qk2 ,qk3 . . .qkn . The distribution of the similarity score s Assume xr is the number of hash vectors in a query q that differ from their cor- responding hash vectors in a database fingerprint f by r bits. i.e. they have r erroneous bits. EWH assigns the following score s to f : s = e ∑ r=0 αrxr (4.1) To find the Probability Distribution Function (PDF) of s, p(s), we first need to determine the probability that a hash vector of a query contains r errors compared to the corresponding hash vector of a fingerprint in the database. Assume two fingerprints f and q are of length l and differ by d bits. Now consider a hash vector of length m extracted from q by randomly choosing m bits from it. The probability that this hash vector contains r out of the d different bits is as follows: pr = (d r )( l−d m−r ) ( l m ) (4.2) 99 0 5 10 15 20 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 r Pr ob ab ilit y τ= 0.8 τ= 0.4 τ= 0.2 τ= 0.1 τ= 0.05 Upper bound Lower bound Estimate p r Figure 4.10: Probability of having an r-bit difference between corresponding hash vectors of two fingerprints f and q with a normalized Hamming distance of τ (shown as labels), m = 20, and l = 1024. By expanding the above expression, pr is found to be bounded as follows: Lowerbound : ( m r ) (1− dl−m) m−r( d− r l−m) r Upperbound : ( m r ) (1− dl ) m−r( d l−m) r (4.3) For m≪ l, a good approximation for pr would be: pr ≈ ( m r ) (1− τ)m−r(τ)r (4.4) where τ = d/l is the normalized Hamming distance. Fig. 4.10 shows an ex- ample of true values, the bounds, and the approximate values of pr for r ≤ 20 and 0.05 ≤ τ ≤ 0.8 (l = 1024 and m = 20). This figure and our evaluations for other values of l and m show that in fact the approximation of Eq. 4.4 is very accurate and we can therefore use it to simplify our calculations. The next step for obtaining p(s) is to find the probability distribution of x = x0x1 . . .xe, where xr (0 ≤ r ≤ e) is the number of words in q that contain r of d 100 different bits between f and q. Each xr has a binomial distribution: p(xr = i) = ( n i ) pir(1− pr)n−i (4.5) For x = x0x1 . . .xe, where ∑er=0 xr ≤ n, the probability distribution is therefore multinomial: p(x0 = i0,x1 = i1, . . . ,xe = ie) = n!× ∏ e r=0 pirr ∏er=0 ir! × (1−∑ e r=0 pr)n−∑ e r=0 ir (n−∑er=0 ir)! (4.6) Each xr and accordingly s take discrete values. To find the probability p(s = s0), every x whose entries xr’s satisfy ∑er=0 αrxr = s0 should be found and the cor- responding probabilities of all these x’s from Eq. 4.6 should be summed together. This is rather a complex operation. Eq. 4.5 can, however, be approximated by a normal distribution N (npr,npr(1− pr)) when npr is large enough. Assuming e is small, one can assume that xr’s (0 ≤ r ≤ e) are independent. Approximating each p(xr) by a normal distribution s would be a weighted sum of independent nor- mally distributed variables and thus p(s) could also be approximated by a normal distribution N (µs,σ 2s ) with the following mean and standard deviation values: µs = n∑er=0 αr pr σ 2s = n∑er=0 α2r pr(1− pr) (4.7) The assumption of independence is not practically accurate for small values of τ . Considering the dependency between xr’s, the approximated distribution for s would still be normal with the same µ . However, the variance of the distribution should be updated to take the dependency into account. Assuming COV(xr,xk) is the covariance between xr and xk (r 6= k), the variance of s would be σ 2s = ∑er=0 α2r σ 2xr +2∑er=0 ∑ek=r+1 αrαkCOV(xr,xk). Here, COV(xr,xk) can be calculated as follows: 101 p(xr,xk) = n!pxrr p xk k (1− pr− pk)n−xr−xk xr!xk!(n− xr − xk)! (4.8) COV(xr,xk) = E{xrxk}−nprnpk (4.9) E{xrxk}= n ∑ xr=0 n−xr∑ xk=0 xrxk n!pxrr p xk k (1− pr− pk)n−xr−xk xr!xk!(n− xr− xk)! = n−1 ∑ xr=1 n−1−xr∑ xk=1 n!pxrr p xk k (1− pr− pk)n−xr−xk (xr−1)!(xk −1)!(n− xr− xk)! = n(n−1)pr pk× n−2 ∑ xr=0 n−2−xr∑ xk=0 (n−2)!pxrr pxkk (1− pr− pk)n−2−xr−xk xr!xk!(n−2− xr− xk)! = n(n−1)pr pk (4.10) COV(xr,xk) = n(n−1)pr pk−n2 pr pk =−npr pk (4.11) The variance of s is then: σ 2s = n e ∑ r=0 α2r pr(1− pr)−2n e ∑ r=0 e ∑ k=r+1 αrαk pr pk = n e ∑ r=0 α2r pr−n ( e ∑ r=0 αr pr )2 (4.12) Fig. 4.11 shows the approximated normal distribution of s (normalized) versus its experimental discrete-value distribution for different values of τ when l = 1024, m = 10, n = 20, and e = 2. We have got similar results for other values of l,m,n, and e. It can be seen that the approximated normal distribution is in fact a good estimation especially for lower values of τ . The accuracy of the estimation can be increased for larger τ’s by increasing the values of e. Optimizing {αr} We first show that with some modifications, the EWH algorithm can generate ex- actly the same results as the exhaustive search for the smallest Hamming distance. Let us assume two binary vectors f and q of length l that differ in d bits, i.e. their 102 Figure 4.11: Comparison of the experimental and the estimated CDF of s for l = 1024, m = 10, n = 20, and e = 2. normalized Hamming distance is τ = d/l. For an arbitrary m, divide both vectors to l/m non-overlapping sub-vectors of length m. Fig. 4.12 shows a straight forward example. Without loss of generality, we assume that l is a multiple of m (otherwise both vectors can be padded with zeros). Let x′r be the number of sub-vectors in q that differ from the corresponding sub-vector in f by r bits (0 ≤ r ≤ m). It is obvious that τ = ∑mr=0 rl x′r. Figure 4.12: Two [similar] fingerprints divided into sub-vectors of m bits (dif- ferent bits are shaded). We now define the similarity score s′ as s′ = 1− τ . The similarity score s′ has a negative linear relationship with the normalized Hamming distance τ . It can be easily shown that s′ = ∑mr=0 m−rl x′r. By setting e = m, n = l/m, αr = (m− r)/l, and using the above sub-vectors instead of randomly generated hash vectors in EWH, we will have xr = x′r and accordingly s = s′. With these values, EWH can be used to find the exact nearest neighbour. 103 We now derive the expected value of the s-score assigned by the original EWH (as proposed in Algorithm 2) to a fingerprint when αr ∝ (m− r). Let us assume, without loss of generality, that αr = m−rmn . From Eq. 4.1, the similarity score w.r.t. the query assigned by EWH to a database fingerprint is: E{s} = E{ e ∑ r=0 m− r nm xr} = e ∑ r=0 m− r nm E{xr} (4.13) where, E{xr}= npr. Using pr from Eq. 4.4: E{s} = e ∑ r=0 m− r nm npr = e ∑ r=0 m− r m ( m r ) τ r(1− τ)m−r = (1− τ) e ∑ r=0 ( m−1 r ) τ r(1− τ)m−r−1 = (1− τ)(1− εe,m,τ) (4.14) where, εe,m,τ = ∑m−1r=e+1 ( m−1 r ) τ r(1−τ)m−1−r. In fact, εe,m,τ , is the relative error from the desired linear relation (0 ≤ εe,m,τ ≤ 1). Fig. 4.13 shows the εe,m,τ values when m = 10 (used in our studies) for different values of e and τ . When e is equal to m, εe,m,τ becomes 0. This means that even for random hash vectors, the expected value of the similarity score s assigned by EWH , is linear with τ . In other words, EWH and the exhaustive search will generate the same results on average. However, when e = m, EWH will examine all the rows and columns of the index table, resulting in the same computational complexity as the exhaustive search, which is not desired. On the other hand, lim τ→0 εe,m,τ = 0 as well. Thus we can claim that even for e < m, for small τ’s, E{s} converges to (1−τ). As the Hamming distance between two fingerprints, τ , increases, E{s} becomes smaller than (1−τ), boosting the dis- similarity between the fingerprints. This property coincides with the requirements 104 0 0.1 0.2 0.3 0.4 0.5 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 e=1→ e=2→ e=3→ e=4→ e=5→ ε e ,m ,τ τ Figure 4.13: The value of the error εe,m,τ of the average score s with respect to the ideal similarity 1− τ for different values of e. of many retrieval tasks, where the acceptable nearest neighbour distance is small. For this reason and to eliminate the requirement for a computationally expensive learning process we choose αr ∝ (m− r). Specifically, we set αr = m−rnm so that s ∈ [0,1]. It will be shown in the results section that with this choice of αr, even when e ≪ m, EWH maintains a very high detection accuracy with significantly lower computational complexity compared to the state-of-the-art. Optimizing m and n We showed that the probability distribution of the similarity score s assigned by EWH can be approximated by a normal distribution, N (µ ,σ 2) with: µ = n e ∑ r=0 αr pr σ 2 = n e ∑ r=0 α2r pr−µ2/n (4.15) where, pr = ( m r ) (1− τ)m−r(τ)k is the probability that a hash vector of q differs 105 from that of f by r bits where τ is the normalized Hamming distance between q and f . To formulate a problem for finding the best values for m and n in EWH , we make the following two practical assumptions. First, if a query has a match in the database, its distance to its nearest neighbour is at most τdet with a high probabil- ity. In fact, in many practical cases, the neighbour(s) within τdet of the query are considered as the nearest match(es). Second, if two fingerprints are extracted from two different subjects, i.e. they are not a match, their distance is higher than τre j (τre j ≥ τdet ) with a high probability. In practice, the search algorithm should filter out any fingerprint that has a distance above τre j with the query. The values of τdet and τre j depend on the appli- cation and on the fingerprint extraction algorithm applied. Ideally, we would like to have τre j = τdet , but we will show that this is not achievable in practice. For now, we assume that τre j > τdet . Let s0 for EWH be the minimum score for which a fingerprint f can be con- sidered as a candidate NN for the query q. An optimization problem can then be formulated as follows: argmax m,n,e p(s ≥ s0) ∀ f : H( f ,q)≤ τdet s.t. p(s ≥ s0)≤ Rre j ∀ f : H( f ,q)≥ τre j (4.16) Here, H( f ,q) represents the normalized Hamming distance τ between the two fingerprints f and q. In Algorithm 2, if the score s of a fingerprint f with respect to query q is at least s0, f is added to the candidate list. The first line of Eq. 4.16 states that the probability of such a fingerprint being added to the candidate list should be maximized for those ones who have a Hamming distance of at most τdet with q. In other words, first line means maximization of the True Positive Rate (TPR). Since we cannot maximize TPR for all τ ≤ τdet at the same time, we maximize the minimum TPR. Whenever s ≥ s0, EWH returns f as a candidate. However, if τ ≥ τre j, f and q belong to two different contents and thus a false positive is added to the candidate list. The second line of the Eq. 4.16, limits the False Positive Rate (FPR) to Rre j. The value of Rre j depends on the application. As the Hamming distance between a f and q increases, the expected value of 106 s, µ decreases. Thus if the constraint in Eq. 4.16 is satisfied for the worst case of τ = τre j, it will be satisfied for any τ > τre j. Thus to meet the constraint, we set s0 = µτre j + zRre j στre j where µτre j and στre j are the mean and the variance from Eq. 4.15 when τ = τre j. Here, zRre j is the value at which a standard normal CDF has a probability equal to the rejection rate Rre j. With such s0, it is guaranteed that FPR remains below Rre j. Similarly, the objective function in Eq. 4.16 is maximized for τ = τdet to consider the worst case scenario, thus: argmax p(s ≥ s0) = argmax p(s̃ ≥ s0−µτdetστdet ) = argmax p(s̃ ≥ µτre j + zRre j στre j −µτdet στdet ) = argmin µτre j + zRre j στre j −µτdet στdet = argmin F (m,n,e) (4.17) In Eq. 4.17, s̃ is the zero-mean unit-variance form of s when τ = τdet . To derive Eq. 4.17 from Eq. 4.16 , we evaluated p(s ≥ s0) at τ = τdet assuming that this is the minimum among all p(s ≥ s0) at τ ≤ τdet . For this to be true, p(s ≥ s0) should increase for lower τdet ’s. We assumed this to be true relying only on the expected value of s, µ , and not considering its standard deviation σ . Now let us see what happens to its standard deviation. The standard deviation of s increases as τ increases from 0 but it starts decreasing at a mid point between 0 and 1. The value of this mid point increases with e but it is less than the commonly used values for τdet (< 0.3) which proves our point. In fact we are maximizing the minimum TPR in Eq. 4.16. Same discussion holds for setting τ = τre j for finding an appropriate value for s0 in second line of Eq. 4.16. We show this one by an example. We set Rre j to 2%, thus the threshold s0 is set to s0 = µτre j + 2.054στre j as the worst case scenario for FPR . For this to hold true, s0 should decrease for larger τre j’s. Fig. 4.14 shows that this is in fact the case. The optimization problem in Eq. 4.17 can be used to design the parameters m, n, and e of the EWH. It limits the probability of false matches being included in the candidate list, while maximizes the probability of the true match being included in 107 0.2 0.4 0.6 0.8 0 0.2 0.4 0.6 0.8 1 τ rej s 0 e=1 e=2 e=3 e=4 Figure 4.14: The value of the threshold s0 for 1≤ e ≤ 4 when Rre j = 2%. the candidate list. To find the optimal parameter values, one can evaluate F in Eq. 4.17 for different values of m, n, and e and choose the best solution that satisfies other requirements such as computational complexity. It can be seen from Eq. 4.17 that if τre j = τdet , TPR cannot be maximized and it will be equal to Rre j. However, if τre j > τdet , the objective function in Eq. 4.16 can be maximized over m, n, and e. The function, F , is strictly increasing with n. Larger n, however, means more calculations and a larger index table which translates to longer retrieval times and extra memory requirements. Once the optimal m and e for a specific value of n are found, the threshold s0 can be set accordingly. Alternatively, instead of using a fixed s0, one can choose all those fingerprints whose scores are within some percentage of the maximum score, e.g. within 80% of the maximum score. Please note that the optimization in Eq. 4.16 is an integer programming problem and cannot be solved mathematically for a given τre j, τdet , and Rre j. However, given the total number of feasible points (a few hundred thousands), a brute-force search returns the optimal solution in a matter of seconds. For a required, τre j, τdet , and Rre j, the solution needs to be found once and off-line. Therefore, the complexity of the optimization problem does not affect the time efficiency of the algorithm. Fig. 4.15 shows p(s > s0), when τ = τdet for different values of n, m, and e. 108 10 15 20 25 30 35 40 0.7 0.75 0.8 0.85 0.9 0.95 1 n (a) p(s >s 0) m=8, e=1 m=8, e=4 m=20, e=1 m=20, e=4 8 10 12 14 16 18 20 0.7 0.75 0.8 0.85 0.9 0.95 1 m (b) p(s >s 0) n=10, e=1 n=10, e=4 n=40, e=1 n=40, e=4 0 1 2 3 4 0.5 0.6 0.7 0.8 0.9 1 e (c) p(s >s 0) n=10, m=8 n=10, m=20 n=40, m=8 n=40, m=20 0 1 2 3 4 5 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1 m:8 #20 m:8 #180 m:10 #1120 m:12 #5980 m:14 #29420 e (d) p(s >s 0) Figure 4.15: (a)-(c) Minimum TPR as a function of n, m, and e, respectively. (d) Minimum TPR , the optimum value of m, and the number of ac- cesses to the table (#) as e changes. The default values are n = 20, τdet = 0.2, τre j = 0.3, and Rre j = 2%. Please note that since we are evaluating p(s ≥ s0) at τ = τdet not τ ≤ τdet , we are finding the minimum TPR . It can be seen from Fig. 4.15 (a) that as the number of keys n increases, TPR increases as well. However, one cannot choose an arbitrary large n as the retrieval time linearly increases with n. We should note that TPR does not necessarily increase with m as shown in Fig. 4.15(b). The reason is that for a specific value of e, as m increases the probability that hash vectors have less errors than e decreases. Moreover, large values of m drastically increase the memory requirement of the algorithm, as the size of the 109 hash table exponentially grows with m. TPR does not necessarily increase with e either as demonstrated in Fig. 4.15 (c). Large values of e on one hand increase the retrieval time by increasing the number of times the table is accessed and on the other hand decrease the accuracy of the approximated values of στdet and στre j . Fig. 4.15 (d) shows the TPR values corresponding to the values of m that max- imize the TPR in Eq. 4.16. It also shows the number of times that the table is accessed. This number, #, equals n∑er=0 ( m r ) . Value of # is also proportional to the number of calculations (score updates) that the algorithm should perform. It can be seen from Fig. 4.15 (d) that as e increases, the number of access times for the optimal algorithm increases exponentially. It can be seen that by accessing the table only about 180 times for m = 8, n = 20, and e = 1 the algorithm can achieve a worst case theoretical TPR value of above 98% and a worst case theoretical FPR of 2%. Based on the application, one can define a proper cost function that achieves the desired performance in terms of both detection performance (TPR, FPR , etc) and computational complexity. 4.5 Results Both EWH and LSH return a candidate list and run an exhaustive search on these candidates to find the fingerprint with the minimum Hamming distance from the query. However, they differ in the way these candidates are chosen. For any appli- cation there is a detection threshold τdet for which a candidate nearest neighbour is considered a match, if its distance to the query is less than τdet . If all the candidates have a Hamming distance greater than τdet with the query, no match is returned for the query. A miss-detection happens when the actual nearest neighbour (with a Hamming distance not greater than τdet ) is not chosen as a candidate. Two types of miss-detections may occur for both EWH or LSH . The first type occurs when all the candidates have a Hamming distance greater than τdet with the query. In this case, both algorithms report a ”no match”, which results in a false rejection. The second type of miss-detection occurs when there exists a fingerprint in the candidate list with a Hamming distance less than or equal to τdet . In this case, the algorithm returns this fingerprint as a ”match” resulting in a false positive. Having a false positive means that two different fingerprints in the original database were close 110 to each other (closer than 2τdet ). No false positives will occur for any legitimate query that has only one neighbour with a Hamming distance less than or equal to τdet . This property, however, cannot be achieved in practice. To make sure that no false positive occurs and to have control over some database/query parameters (not controllable in practical applications) we use synthetically generated finger- print databases in the first part of our evaluations. For this part, we only compare the algorithms based on their False Rejection Rate (FRR). In the second part of our evaluations, we use two real-world databases and evaluate the algorithms based on the resulting FPR and FRR as well as the retrieval time. 4.5.1 Performance evaluation on synthetic databases In this section, datasets are (randomly) synthesized with the following property: with each query one and only one fingerprint in the database has a Hamming dis- tance less than or equal to the detection threshold τdet , i.e. FPR =0. False rejections, however, occur for both algorithms whenever the nearest neighbour is not included in the candidate list. We thus evaluate the detection performance based on the FRR. We compare the performance of the algorithms for different parameter values. For each experiment, we synthesize 10 different databases of 104 fingerprints each. For each database, we also generate 1000 queries. Each point in the figures of this section is then the average results of all queries over all databases (104 values). In the following simulations, the proposed EWH evaluated for e = 1,2 is com- pared to the original LSH algorithm [18], the LSH algorithm based on permutation of the whole fingerprint [66] (noted as Locality Sensitive Hashing based on Permu- tations (LSHP)), and a modified version of the BGS algorithm [59]. When no error (in the hashes) is considered for EWH, i.e. e = 0, the similarity score s assigned to a fingerprint in the database is simply the number of hash vectors extracted from the fingerprint that are identical to the corresponding hash vectors of the query. This extreme case for EWH , named Randomized Beacon Guided Search (RBGS) , represents the randomized version of the BGS algorithm proposed in [59] for iris code detection. For RBGS s0 is the equal to the collision count parameter in BGS . When s0 ≤ 1, the detection results for RBGS and LSH will be exactly the same. We thus set s0 = 2 so that RBGS achieves the highest possible detection rate different 111 from that of LSH . As discussed in Section 4.4.3, the value of s0 for EWH (e = 1,2) is calculated as s0 = µτre j + zRre j στre j with τre j = 0.4. We evaluate the algorithms for different parameter values: the hash length m and the number of hashes (per fingerprint) n. Please remember that n is also equiv- alent to the number of columns of the index table. Fig. 4.16 (a) compares the average FRR for different values of n. The NND parameter represents the average Nearest Neighbour Distance (NND) for a query. It can be seen that as n increases, the FRR decreases for all the three algorithms. On the other hand, as shown in Fig. 4.16 (b) while for EWH , the number of candidates has a decreasing trend with n, it increases linearly for LSH . The number of candidates has a linear relationship with the computation time associated with the exhaustive search phase. If the num- ber of candidates is large, these operations could account for the main portion of the retrieval time and consequently represent the time efficiency of the algorithm. Fig. 4.16 (c) shows the time taken by the algorithms to generate the candidate list, while Fig. 4.16 (d) shows the total retrieval time (algorithms were implemented in MATLAB on a 2.4GHz PC with 4GB of Random Access Memory (RAM)). It can be seen that while LSH has a lower generation time for the candidate list, it results in larger retrieval times compared to EWH because of the long list of candidates it returns. Fig. 4.17 compares the algorithms for different values of hash length, m. In- creasing m has an adverse affect on the FRR values of both LSH and RBGS as ex- pected. For EWH as expected, depending on m, the FRR can have a decreasing or an increasing trend. For n = 20 to maximize the TPR , the theoretical values from Eq. 4.17 yield m = 9 for e = 1 and m = 10 for e = 2 which matches the results in Fig. 4.17 (b). It can be seen from Fig. 4.17 (b) that the number of candidates for LSH exponentially decreases as m increases, making it much faster than EWH for large values of m. However this increase in speed for LSH is drastically compen- sated with its detection accuracy, as LSH has a much higher FRR for large values of m compared to EWH . The sudden changes observed on the EWH performance curves when e = 1 in Fig. 4.17 (b) and (d) are due to the Gaussian approximation of the discrete random variable s. When m is large, this approximation and thus the resulted optimum s0 is not accurate. We now study how different properties of database and queries affect the per- 112 10 15 20 25 30 35 40 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 n (a) Fa ls e re jec tio n r ate RBGS LSHP LSH EWH (e=1) EWH (e=2) 10 15 20 25 30 35 40 0 50 100 150 200 250 300 350 400 n (b) N um be r o f c an di at es RBGS LSHP LSH EWH (e=1) EWH (e=2) 10 15 20 25 30 35 40 0 0.002 0.004 0.006 0.008 0.01 n (c) Ca nd id at e lis t r et rie va l t im e (s) RBGS LSHP LSH EWH (e=1) EWH (e=2) 10 15 20 25 30 35 40 0 0.002 0.004 0.006 0.008 0.01 0.012 n (d) To ta l r et rie va l t im e (s) RBGS LSHP LSH EWH (e=1) EWH (e=2) Figure 4.16: Comparing the performance of different search algorithms for 10 ≤ n ≤ 40, m = 10, l = 1024, and NND = 0.2 (a) Average FRR (b) Average number of candidates in the list (c) Time taken to generate the candidate list (d) Total retrieval time. formance of LSH, LSHP, RBGS and EWH . Fig. 4.18 (a) shows the performance of these algorithms as a function of the average NN distance (NND). As NND increases, the FRR for all the algorithms increase. However, it can be seen that EWH is much more robust to large nearest neighbour distances compared to LSH or RBGS. Fig. 4.18 (b) shows the number of candidates generated by different al- gorithms. Because of the randomness property of the fingerprints, they are evenly distributed in the buckets of the index table. Therefore, the number of candidates generated by the three algorithms is not affected by NND. 113 8 9 10 11 12 13 14 15 0 0.2 0.4 0.6 0.8 1 m (a) Fa ls e re jec tio n r ate RBGS LSHP LSH EWH (e=1) EWH (e=2) 8 9 10 11 12 13 14 15 0 100 200 300 400 500 600 700 800 m (b) N um be r o f c an di at es RBGS LSHP LSH EWH (e=1) EWH (e=2) 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 x 10 −3 m (c) Ca nd id at e lis t r et rie va l t im e (s) RBGS LSHP LSH EWH (e=1) EWH (e=2) 8 9 10 11 12 13 14 15 0 0.005 0.01 0.015 0.02 m (d) To ta l r et rie va l t im e (s) RBGS LSHP LSH EWH (e=1) EWH (e=2) Figure 4.17: Comparing the performances of different search algorithms for 8≤m≤ 15, n = 20, l = 1024, and NND = 0.2 (a) Average false rejec- tion rate (FRR) (b) Average number of candidates returned for a query (c) Time taken to generate the candidate list (d) Total retrieval time. One might argue that both the detection performance and the retrieval time de- pend on the size of the database as well. We examined different database sizes, ranging from 4K to 256K fingerprints. Fig. 4.19 shows the FRR as well as the number of candidates generated as a function of the database size. It can be seen that in all cases except from LSHP , the detection performance is almost indepen- dent of the size of the database. As the size of the database increases, lexicographic ordering of the permuted hash vectors becomes less effective, deteriorating the de- tection accuracy of the LSHP . As shown in Fig. 4.19 (b), for most of the algorithms 114 0.05 0.1 0.15 0.2 0.25 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 average NND (a) Fa ls e re jec tio n r ate RBGS LSHP LSH EWH (e=1) EWH (e=2) 0.05 0.1 0.15 0.2 0.25 0 50 100 150 200 average NND (b) N um be r o f C an di da te s RBGS LSHP LSH EWH (e=1) EWH (e=2) Figure 4.18: Comparing the performances of different search algorithms for 0 < NND < 0.4, m = 10, n = 20, and l = 1024 (a) Average FRR (b) Average number of candidates returned for a query. the number of candidates increases with the size of the database which in turn in- creases the retrieval time. This, however, affects EWH far less than RBGS and LSH. For LSHP , the number of candidates is independent of the size of the database. We also studied the effect of the fingerprint length l on the performance of LSH and EWH. As expected, neither the number of candidates nor the FRR were affected by this parameter. However, the overall retrieval time is affected. This is because calculating the Hamming distance in the exhaustive search phase takes more time for longer fingerprints. This affects the retrieval time of the LSH algorithm more than that of the EWH . 4.5.2 Performance evaluation on real-world databases In this section, we further evaluate our proposed approximate search algorithm EWH on two real-world examples: a medium sized video database with 1016 videos of different genres available from [73], and a large image database with 79,302,017 tiny images available from [74]. In this section, we only compare EWH with LSH which had the best performance compared to the other algorithms. 115 0.5 1 1.5 2 2.5 x 105 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 size of database (a) Fa ls e re jec tio n r ate RBGS LSHP LSH EWH (e=1) EWH (e=2) 0.5 1 1.5 2 2.5 x 105 0 1000 2000 3000 4000 5000 6000 size of database (b) N um be r o f C an di da te s RBGS LSHP LSH EWH (e=1) EWH (e=2) Figure 4.19: The effects of the database size on the performance of LSH , RBGS , and EWH , when l = 1024, m = 10, n = 20, and NND = 0.2 (a) Average FRR (b) Average number of candidates returned for a query. Video database The video fingerprinting algorithm from Chapter 3 was applied on the videos to generate a fingerprint database of more than 88,000 fingerprints of length 640 bits. More than 70 videos were also randomly selected from the database to generate the query videos. To generate the query videos, these videos were distorted by frame rate and size changes, text insertion, and compression. The query videos were used to generate more than 6,000 query fingerprints. The normalized Hamming distance between the generated query fingerprints and the corresponding database fingerprints (as a result of the distortions) ranges from 0.01 to 0.36. About 0.44% of the queries have a Hamming distance above 0.25. To build the basis of our comparison, we launched an exhaustive search to find the nearest neighbour and the nearest neighbour distance for each query3. Fig. 4.20 shows the total average retrieval time as well as the error rate (FPR + FRR) for both algorithms. When m = 10 (the optimal value for m when e = 2) EWH retrieves a query in about 16ms with an average error of about 0.09%, while LSH retrieves it in about 49ms with an average error of 0.9%. For smaller values of m, e.g. 8, LSH has an error rate about 3 times of EWH and it is more than 7 times 3Since we were concerned about the performance of the search algorithm (not the fingerprinting algorithm) we did not use our prior knowledge of the true matches. 116 8 9 10 11 12 0 0.005 0.01 0.015 0.02 m (a) R et rie va l e rro r r at e LSH EWH (e=1) EWH (e=2) 8 9 10 11 12 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 m (b) R et rie va l t im e (s) LSH EWH (e=1) EWH (e=2) Figure 4.20: Comparing the performance of the algorithms for 8 ≤ m ≤ 12, n = 20, and l = 640 (a) Retrieval error rate (FRR+FPR) (b) Average total retrieval time for a query. slower. For larger values of m, e.g. m = 12, EWH is about 1.5 times faster than LSH while it has about 15 times lower error rate. Image database The same fingerprinting algorithm in from Chapter 3 was modified for the 32× 32× 3 images from the Tiny Images Dataset. The length of the extracted finger- prints were 336 bits. A total of 79,302,017 fingerprints were extracted. With this large sized database, each column of the table requires about 1GB of memory and we had to store the fingerprints and the generated hash tables in the hard drive of the computer. Please note that tables’ memory requirements of EWH and LSH are the same and thus the hard drive access time has affected the retrieval time for both algorithms. For retrieval both algorithms require an in-memory vector that has the same length as the number of fingerprints in the database. The only difference is that the vector used with LSH can be a binary vector (simply indicating if the fin- gerprint is in the candidate list or not) while the vector for EWH is a floating point vector. First, we compare the algorithms for different numbers of Hash vectors. For this test, to generate queries, randomly selected fingerprints from the database were distorted with an average bit-error-rate of 0.2. Fig. 4.21 (a) shows the detection 117 10 15 20 25 30 35 40 0 0.1 0.2 0.3 0.4 0.5 n (a) R et rie va l e rro r r at e LSH EWH (e=2) 10 15 20 25 30 35 40 0 5 10 15 20 25 30 n (b) R et rie va l s pe ed LSH/EXH EWH/EXH EWH/LSH Figure 4.21: Comparing the performance of the algorithms for 10 ≤ n ≤ 40, m = 10, and l = 336 (a) Retrieval error rate (FRR + FPR) (b) Relative retrieval speed of EWH (e = 2), LSH and the exhaustive search. error for LSH and EWH (with e = 2). As discussed in Section 4.4.3, for either of the algorithms, both the accuracy and the retrieval time should increase when more hashes are extracted. It can be seen that EWH, has significantly less number of errors compared to LSH. Actually for n≥ 25 EWH shows no detection error, while it is at least two times faster than LSH. Fig. 4.21 (b), shows the relative speed of the algorithms w.r.t exhaustive search as well as to each other. It can be seen that EWH is 2 to 4 times faster than LSH for different values of n, it can also be seen that it is about 20 times faster than exhaustive search with the same detection results. Please remember that the retrieval speeds are highly affected by the fact that for both EWH and LSH, the tables are stored in the hard disk of the computer. This issue affects EWH more severely as it accesses the tables hundreds of times more than LSH. With enough RAM memory (about 32GB), we expect much greater retrieval speed-ups for EWH. We also used the proposed EWH algorithm to find the nearest neighbour of 200 query images randomly selected from other databases. By running an exhaustive search, the queries were found to have nearest neighbour distances ranging from 0.09 to 0.3. The average nearest neighbour distance error was 0.05% for EWH while it was 0.4% for LSH . Also 99% of the nearest neighbours were detected correctly with EWH while 90% were detected using LSH. EWH also was more than 118 2.5-times faster than LSH in terms of the retrieval time. In terms of memory usage, EWH and LSH are very similar. To select candidate 4.6 Summary We first, presented a windowing scheme along with a state machine-based match- ing process for matching the windows based on their temporal adjacency. The proposed technique can be used for any window-based video or audio fingerprint- ing system. Tested on a database of 1000 videos, we showed that this approach significantly decreases the search time by 1 to 3 orders of magnitude compared to the conventional approach where query videos undergo the same windowing scheme as the videos in the database and each window of the query is indepen- dently searched in the database. We also showed that the proposed method main- tains a high copy detection rate (above 95%). While the detection rate is slightly decreased compared to the conventional approach (about 2−3%), we showed that our approach yields much higher localization accuracy (lower jitter) compared to the conventional method. The high jitter in the conventional approach calls for a post-processing step to re-align and aggregate the detected segments of the query sequence. This step further increases the search time. For highly distorted copies the jitter resulting from the conventional approach can become so large that it ren- ders the detected results useless. We also focused on the more general problem of Nearest Neighbour (NN) search for binary fingerprints which are becoming more and more common in copy detection and retrieval applications. We proposed a new approximate NN search algorithm called Error Weighted Hashing (EWH) for the Hamming (binary) space. EWH can be used in may different applications that involve binary vectors includ- ing digital rights management, content-based retrieval, and biometric authentica- tion. Like the popular LSH algorithm, the proposed algorithm has a pre-processing step for generating an index table. In the retrieval phase, however, (by exploiting the erroneous hash vectors of the query) it creates a much smaller list of candi- dates compared to LSH and has a significantly better detection accuracy. For large nearest neighbour distances, EWH has a significantly higher detection performance compared to LSH , while it requires a lower search time as well. For example, 119 by considering the hash vectors with only one-bit error, for an average normalized Nearest Neighbour Distance (NND) of about 0.25, EWH results in almost half the false rejections generated by LSH while it is twice as fast as LSH. The detection per- formance of LSH cannot be kept high when the NND increases, even at the expense of a higher computational complexity. EWH algorithm, however, can be tuned, to maintain a high detection performance at the expense of increased retrieval time for arbitrary large NNDs. When applied on a real-world database of video fingerprints (extracted from 1000 videos collected by our research group at UBC), EWH was shown to be up to 8 times faster than LSH with almost the same error rate, or up to 15 times more accurate with the same retrieval speed. For optimal parameter values, EWH was shown to be more than 3 times faster than LSH while resulting in an error rate of of about 0.1% compared to 0.9% for LSH . We also applied EWH and LSH to find the nearest neighbour of query images in a large database of about 80 million images. We showed that EWH was almost 10 times more accurate than LSH while it was 2.5 times faster as well. 120 Chapter 5 Conclusion and Future Work 5.1 Conclusion We addressed the problem of video and audio copy detection using multimedia fin- gerprinting technology. Fingerprints are content-based signatures extracted from a multimedia signal to represent the perceptual content of the signal in a very com- pact fashion. Fingerprints are used to detect similarities or differences between a query multimedia object (video or audio) and the registered original multimedia objects. A direct application of the work in this thesis is the automatic detection of pirated contents in multimedia sharing websites such as YouTube and Facebook. Both video and audio signals are time based signal. It is possible that only parts of them (cropped in time) are shared or copied. A bold example of such copies are videos created by users of on-line video sharing websites by mixing snippets of dif- ferent videos (referred to as mash-up). Thus an important requirement in video and audio copy detection is the ability to detect short snippets extracted from video or audio signals (referred to as granularity). Beside cropping, the shared content can be subjected to modifications that change the representation of the signal. Exam- ples of these modifications are brightness/contrast change in videos, tempo change in audio, noise, etc. A multimedia copy detection system should be robust to these modifications as well. We have addressed both robustness and granularity in mul- timedia copy detection systems and proposed novel fingerprinting algorithms for both audio and video signals. 121 Other than robustness and granularity, a multimedia copy detection system sys- tem should support fast retrieval, i.e. it should be able to search a large fingerprint database for possible matches for a query fingerprint in a fast and accurate fashion. This supports real-time applications of the system. We have addressed this require- ment as well. Below we summarize our contributions (categorized by topic). Audio fingerprinting We contributed to the audio fingerprinting research by proposing: 1. A two dimensional representation for audio signals denoted as the time- chroma image. 2. Two local audio fingerprinting algorithms that are robust to tempo change and pitch shift. 3. A song identification algorithm that uses the proposed fingerprinting algo- rithms to localize songs and to estimate the amount of pitch shift and tempo change. The proposed time-chroma image is a novel two dimensional representation of the audio signal that represents (a modified version of) the chroma content of an audio signal over time. This image has the following two characteristics: 1) a pitch shift on the audio signal (circularly) shifts the time chroma image along the chroma axis and 2) a tempo change on the audio signal scales the time-chroma image along the time axis. The proposed audio fingerprinting algorithms, extract tempo and pitch invari- ant features from an audio signal. The extracted fingerprints are local, which means that they do not depend on the whole signal representation and only a small snippet of a song is enough to perform an accurate detection. One of the algorithms is com- putationally more complex but much more robust than the other. Both algorithms extract their fingerprints from patches around salient points in the proposed time- chroma image. The size of the patches are determined by the algorithms based on the local content of the audio. The size and location of the patches are used to estimate the amount of pitch shift and tempo change applied to a song. 122 The proposed song identification algorithm uses the proposed fingerprints to identify and localize song snippets. We showed (on a dataset of 260 songs) that that our proposed fingerprinting and song identification algorithms outperform the state-of-the-art by a great extent. In the presence of severe pitch and tempo modi- fications, where similar algorithms have a detection rate of about 20%, our system has a detection rate of above 80%. Video fingerprinting We contributed to the video fingerprinting research by proposing: 1. A two dimensional image representation of a video signal called Temporally Informative Representative Image (TIRI). 2. A robust video fingerprinting algorithm that generates compact and discrim- inant video fingerprints from TIRIs. 3. A fast and approximate cluster-based search algorithm. 4. A secure version of the proposed video fingerprints. The proposed TIRI’s contain both spatial and temporal information about a seg- ment of a video signal. They are used to decrease the dimensionality of a video sig- nal from three to two and thus decrease the computational load of the fingerprinting algorithm. The proposed video fingerprinting method is a block-DCT based algo- rithm and generates binary fingerprints that are compact, robust, and discriminant. The proposed search algorithm effectively reduces the retrieval time by reduc- ing the number of fingerprints that should be searched. It does so by using a clus- tering approach to divide the fingerprints in the database to smaller groups. The proposed cluster-based search is adapted to the proposed fingerprints and facilitates their use on large databases. The proposed secure version makes it almost impossible for an adversary to manipulate the copy detection system. The final system is comprised of a secure fingerprint extraction algorithm and a fast and accurate search engine and can be used for video indexing and video copyright protection. 123 The proposed system was evaluated on a database of 200 videos in the presence of different types of attacks such as noise, change in brightness/contrast, frame loss, spatial shift, rotation, and time shift. We demonstrated that the algorithm outperformed the state-of-the-art in most of the cases. The proposed copy detection system yields a high average true positive rate of about 98% and a low average false positive rate of 1% using fingerprints only 126 bits long. Fingerprint matching Fingerprint matching or fingerprint retrieval is the process of searching a database of fingerprints for matches for the given query fingerprint. We contributed to fast retrieval of fingerprints by proposing: 1. A time-windowing method and a search strategy for fast retrieval of audio and video fingerprints. 2. A fast and accurate NN search algorithm for finding the nearest neighbours of a binary fingerprint in a very large database. The proposed time-windowing method can be applied to any audio and video fingerprinting algorithm that extracts fingerprints from temporal windows of an au- dio or a video signal. It is accompanied by a state-machine based search algorithm that reduces the search time by using the temporal correlations between adjacent windows. The proposed system is shown to result in speed-ups up to three orders of magnitude in the search retrieval time (on a database of 1000 videos). The proposed approximate NN search can be used for fast matching of binary fingerprints and in general any binary descriptor. Because of the their compact- ness and robustness, binary descriptors are becoming increasingly popular with content-based retrieval systems. However, they are only a few NN search algo- rithms like ours that are optimised for binary descriptors. The proposed search algorithm, called EWH, is optimised for binary descriptors and can be used for any NN search application in the Hamming (binary) space. EWH is evaluated on a fin- gerprint database with more than 1000 videos. For a specific detection accuracy, we demonstrated that EWH is about 10 times faster than the state-of-the-art. For the same retrieval time, we showed that EWH has a significantly better detection 124 accuracy with a 15 times lower error rate. We also evaluated EWH on a very large dataset of 80 million images and showed that it is both faster and more accurate than the existing options. 5.2 Future work Possible continuation of the works in this thesis are explained below (categorized by topic): Audio fingerprinting The proposed audio fingerprinting approach is proved to be both very robust and discriminant. However, the extracted fingerprints are real valued vectors with a long length. This creates a computational bottleneck for the retrieval phase when the system is applied to large audio databases. Therefore, an improvement on the current algorithm is reducing the dimension of the extracted fingerprints without affecting their robustness and discrimination ability. A possible approach would be to design a binary embedding scheme that generates binary fingerprints and reduces the comparison domain from the Euclidean space to the Hamming space. Security As discussed in Chapter 3, security analysis of fingerprinting systems has not re- ceived enough attention in the literature. Currently used evaluation metrics such as the entropy do not provide appropriate metrics for the security of a video fin- gerprinting algorithm because they do not consider the information available to an adversary. A detailed analytical study of the security of multimedia copy detection systems could open new doors to designing new secure fingerprints. Video fingerprinting Improving the robustness of the proposed video fingerprints to geometric attacks such as rotation, is an area that the proposed algorithm needs improvement on. Another class of attacks, studied mainly in the video retrieval community, are the content-changing attacks such as changing the background or picture in picture 125 attacks. Robustness against such attacks is not achievable via global fingerprints such as the proposed video fingerprints. Such attacks can only be handled using local fingerprints. Including such capabilities to a copy detection system is defi- nitely an important step towards improving the system proposed in this thesis. One can combine global and local fingerprinting algorithms together and have a system the performs well for a much wider range of modifications. In addition, one can integrate audio and video fingerprinting systems together and use information from both systems to enhance the detection results. Fingerprint retrieval In Chapter 4, a state machine-based matching strategy was proposed for window- based fingerprinting algorithms for audio and video signals. It was shown that the proposed strategy could result in speed-ups up to about three orders of magnitude in the retrieval time. A possible expansion of the proposed strategy is to adapt it for local fingerprinting techniques that are based on salient points such as the audio fingerprinting algorithm proposed in Chapter 2. In Chapter 4, we also proposed a NN search algorithm for binary fingerprints (based on Hamming distance). Although many recent fingerprinting algorithms have resorted to binary fingerprints, a majority of the available approaches still generate real-valued or integer-valued fingerprints. Many local feature extraction and local fingerprinting algorithms are amongst the latter group. Since the pro- posed system has demonstrated great improvements (in terms of both speed and accuracy) over the existing options, it is very beneficial to extend the proposed algorithm so that it can be applied to other commonly used distance metrics. 126 Bibliography [1] B. Coskun, B. Sankur, and N. Memon. Spatiotemporal transform based video hashing. IEEE Transactions on Multimedia, 8(6):1190–1208, Dec. 2006. ISSN 1520-9210. → pages xi, 45, 47, 48, 49 [2] Video Traces Research Group, Arizona State University. [Online]. Available: http://trace.eas.asu.edu/index.html. → pages xi, 50, 51, 63 [3] Alexis Joly, Olivier Buisson, and Carl Frelicot. Content-based copy retrieval using distortion-based probabilistic similarity search. IEEE Transactions on Multimedia, 9(2):293–306, Feb. 2007. ISSN 1520-9210. doi:10.1109/TMM.2006.886278. → pages 2, 47 [4] Alfred Menezes, Paul van Oorschot, and Scott Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. → pages 2 [5] K. J. Ray Liu. Multimedia Fingerprinting Forensics for Traitor Tracing. Hindawi Publishing Corporation, 2005. → pages 15 [6] Wenjun Zeng, Hong Heather Yu, and Ching-Yung Lin. Multimedia Security Technologies for Digital Rights Management. Academic Press, 2006. → pages 15 [7] P. Cano, E. Batlle, E. Gómez, L. Gomes, and M. Bonnet. Audio Fingerprinting Concepts and Applications., pages 233–245. Springer-Verlag, 2005. → pages 15 [8] Todd Souvignier. The World of DJs and the Turntable Culture. Hal Leonard, 2003. → pages 15 [9] T Fujishima. Realtime chord recognition of musical sound: A system using common lisp music. In Proc. of ICMC, volume 9, pages 464–467, 1999. URL http://ci.nii.ac.jp/naid/10013545881/. → pages 16, 18, 19 127 [10] E. Zwicker. Subdivision of the audible frequency range into critical bands (frequenzgruppen). The Journal of the Acoustical Society of America, 33(2): 248–248, 1961. doi:10.1121/1.1908630. URL http://link.aip.org/link/?JAS/33/248/1. → pages 16 [11] S. S. Stevens, J. Volkmann, and E. B. Newman. A scale for the measurement of the psychological magnitude pitch. The Journal of the Acoustical Society of America, 8(3):185–190, 1937. doi:10.1121/1.1915893. URL http://link.aip.org/link/?JAS/8/185/1. → pages 16 [12] Avery L. Wang. An industrial-strength audio search algorithm. In Symposium Conference on Music Information Retrieval (ISMIR), pages 7–13. The International Society for Music Information Retrieval, ISMIR, Oct. 2003. → pages 17, 19, 24, 26, 30 [13] Jaap Haitsma and Ton Kalker. A highly robust audio fingerprinting system. In Symposium on Music Information Retrieval (ISMIR), pages 107–115, 2002. → pages 17, 19, 21, 26 [14] Matthew Miller, Manuel Rodriguez, and Ingemar Cox. Audio fingerprinting: Nearest neighbor search in high dimensional binary spaces. The Journal of VLSI Signal Processing, 41:285–291, 2005. URL http://dx.doi.org/10.1007/s11265-005-4152-2. 10.1007/s11265-005-4152-2. → pages 17 [15] Hamza ¨Ozer, Bülent Sankur, Nasir Memon, and Emin Anarim. Perceptual audio hashing functions. EURASIP J. Appl. Signal Process., pages 1780–1793, January 2005. ISSN 1110-8657. → pages 17, 18 [16] Shumeet Baluja and Michele Covell. Waveprint: Efficient wavelet-based audio fingerprinting. Pattern Recognition, 41(11):3467–3480, 2008. → pages 18 [17] Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, Jeffrey D. Ullman, and Cheng Yang. Finding interesting associations without support pruning. IEEE Transactions on Knowledge and Data Engineering, 13(1):64–78, January 2001. ISSN 1041-4347. → pages 18 [18] Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In International Conference on Very Large Data Bases (VLDB), pages 518–529, San Francisco, CA, USA, 1999. 128 Morgan Kaufmann Publishers Inc. ISBN 1-55860-615-7. → pages 18, 79, 86, 95, 111 [19] Bilei Zhu, Wei Li, Zhurong Wang, and Xiangyang Xue. A novel audio fingerprinting method robust to time scale modification and pitch shifting. In Proceedings of the international conference on Multimedia, pages 987–990, New York, NY, USA, 2010. ACM. → pages 18, 30, 31 [20] David G. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91–110, 2004. ISSN 0920-5691. doi:http://dx.doi.org/10.1023/B:VISI.0000029664.99615.94. → pages 18, 31, 46 [21] J. Serra, E. Gomez, P. Herrera, and X. Serra. Chroma binary similarity and local alignment applied to cover song identification. IEEE Transactions on Audio, Speech, and Language Processing, 16(6):1138 –1151, Aug. 2008. ISSN 1558-7916. doi:10.1109/TASL.2008.924595. → pages 18, 19 [22] Pedro Cano, Eloi Batlle, Ton Kalker, and Jaap Haitsma. A review of audio fingerprinting. J. VLSI Signal Process. Syst., 41:271–284, November 2005. ISSN 0922-5773. doi:10.1007/s11265-005-4151-3. → pages 18 [23] Anssi Klapuri. Introduction to music transcription. In Anssi Klapuri and Manuel Davy, editors, Signal Processing Methods for Music Transcription, pages 3–20. Springer, New York, 2006. ISBN 0-387-30667-6. → pages 19 [24] Job Oostveen, Ton Kalker, and Jaap Haitsma. Feature extraction and a database strategy for video fingerprinting. In International Conference on Recent Advances in Visual Information Systems (VISUAL), pages 117–128, London, UK, 2002. Springer-Verlag. ISBN 3-540-43358-9. → pages 44, 51, 52, 53, 54, 78, 79, 81, 86, 95 [25] A. Swaminathan, Yinian Mao, and Min Wu. Robust and secure image hashing. IEEE Transactions on Information Forensics and Security, 1(2): 215 – 230, June 2006. → pages 45, 72, 73 [26] Avinash L. Varna and Min Wu. Modeling and analysis of content identification. In ICME, pages 1528–1531, 2009. → pages [27] Baris Coskun and Nasir Memon. Confusion/diffusion capabilities of some robust hash functions. In Proc. of Conf. on Information Sciences and Systems (CISS), 2006. → pages 45 129 [28] Jian Lu. Video fingerprinting for copy identification: from research to industry applications. volume 7254, page 725402. SPIE, 2009. doi:10.1117/12.805709. URL http://link.aip.org/link/?PSI/7254/725402/1. → pages 45, 46 [29] Julien Law-To, Li Chen, Alexis Joly, Ivan Laptev, Olivier Buisson, Valerie Gouet-Brunet, Nozha Boujemaa, and Fred Stentiford. Video copy detection: a comparative study. In Proceedings of the ACM international conference on Image and video retrieval, pages 371–378, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-733-9. doi:http://doi.acm.org/10.1145/1282280.1282336. → pages 45 [30] Arun Hampapur and Rudolf M. Bolle. Videogrep: Video copy detection using inverted file indices. Technical report, IBM Research Division Thomas. J. Watson Research Center, 2001. → pages 46 [31] Li Chen and F. W. M. Stentiford. Video sequence matching based on temporal ordinal measurement. Pattern Recogn. Lett., 29(13):1824–1831, 2008. ISSN 0167-8655. doi:http://dx.doi.org/10.1016/j.patrec.2008.05.015. → pages 46 [32] R. Radhakrishnan and C. Bauer. Content-based video signatures based on projections of difference images. In Proceedings of MMSP, pages 341–344, Oct. 2007. → pages 46 [33] C. De Roover, C. De Vleeschouwer, F. Lefebvre, and B. Macq. Robust video hashing based on radial projections of key frames. IEEE Transactions on Signal Processing, 53(10):4020–4037, Oct. 2005. ISSN 1053-587X. doi:10.1109/TSP.2005.855414. → pages [34] Sunil Lee and C.D. Yoo. Robust video fingerprinting for content-based video identification. IEEE Transactions on Circuits and Systems for Video Technology, 18(7):983–988, July 2008. ISSN 1051-8215. doi:10.1109/TCSVT.2008.920739. → pages 81 [35] Xing Su, Tiejun Huang, and Wen Gao. Robust video fingerprinting based on visual attention regions. In Proceedings of ICASSP, pages 1525–1528, Washington, DC, USA, 2009. IEEE Computer Society. ISBN 978-1-4244-2353-8. → pages [36] Alexis Joly, Olivier Buisson, and Carl Frelicot. Content-based copy retrieval using distortion-based probabilistic similarity search. IEEE Transactions on 130 Multimedia, 9(2):293–306, Feb. 2007. ISSN 1520-9210. doi:10.1109/TMM.2006.886278. → pages [37] Josef Sivic and Andrew Zisserman. Video google: A text retrieval approach to object matching in videos. In IEEE International Conference on Computer Vision (ICCV), page 1470, Washington, DC, USA, 2003. IEEE Computer Society. ISBN 0-7695-1950-4. → pages [38] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Hamming embedding and weak geometric consistency for large scale image search. In European Conference on Computer Vision (ECCV), pages 304–317, Berlin, Heidelberg, 2008. Springer-Verlag. ISBN 978-3-540-88681-5. doi:http://dx.doi.org/10.1007/978-3-540-88682-2 24. → pages [39] Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In International Conference on Very Large Data Bases (VLDB), pages 518–529, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1-55860-615-7. → pages 46 [40] Zhu Liu, Behzad Shahraray, and Tao Liu. AT&T research at TRECVID 2009 content-based copy detection. In TRECVID, November 2009. → pages 46 [41] Maguelonne Hritier, Vishwa Gupta, Langis Gagnon, Gilles Boulianne, Samuel Foucher, and Patrick Cardinal. CRIMs content-based copy detection system for TRECVID. In TRECVID, November 2009. → pages [42] Apostol Natsev, Matthew Hill, John R. Smith, Lexing Xie, Rong Yan, Shenghua Bao, Dong Wang, Michele Merler, and Yi Zhang. IBM research TRECVID-2009 video retrieval system. In TRECVID, November 2009. → pages [43] Uan Cao, Yong-Dong Zhang, Bai-Lan Feng, Lei Bao, Ling Pang, Jin-Tao Li, Ke Gao, Xiao Wu, Hon-Ttao Xie, Wei Zhang, and Zhen-Dong Mao. TRECVID 2009 of MCG-ICT-CAS. In TRECVID, November 2009. → pages 46 [44] Personal communication with prof. David Lowe, August 2010. → pages 46 [45] R. Radhakrishnan and C. Bauer. Robust video fingerprints based on subspace embedding. In Proceedings of ICASSP, pages 2245–2248, April 2008. → pages 47, 81 131 [46] Geert Willems, Tinne Tuytelaars, and Luc Van Gool. Spatio-temporal features for robust content-based video copy detection. In Proceeding of ACM international conference on Multimedia information retrieval, pages 283–290, New York, NY, USA, 2008. ACM. → pages 47 [47] Changick Kim and B. Vasudev. Spatiotemporal sequence matching for efficient video copy detection. IEEE Transactions on Circuits and Systems for Video Technology, 15(1):127–132, Jan. 2005. ISSN 1051-8215. doi:10.1109/TCSVT.2004.836751(410)1. → pages 47 [48] Mani Malekesmaeili and Rabab K. Ward. Robust video hashing based on temporally informative representative images. In IEEE International Conference on Consumer Electronics, pages 179–180, Jan. 2010. → pages 49, 50, 81 [49] Marius Muja and David G. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. In International Conference on Computer Vision Theory and Applications, pages 331–340, 2009. → pages 52 [50] Jaap Andre Haitsma, Antonius Adrianus Cornelis Maria Kalker, Constant Paul Marie Jozef Baggen, and Job Cornelis Oostveen. Generating and matching hashes of multimedia content. US 2002/0178410, Nov. 2002. → pages 52, 80 [51] Matthew L. Miller. Audio fingerprinting: Nearest neighbour search in high dimensional binary spaces. In Multimedia Signal Processing, 2002 IEEE Workshop on , 2002, pages 182–185, 2002. → pages 52 [52] Baris Coskun and Nasir Memon. Online sketching of network flows for real-time stepping-stone detection. In Annual Computer Security Applications Conference, pages 473–483, Los Alamitos, CA, USA, 2009. IEEE Computer Society. → pages 57 [53] ReefVid: A resource of free coral reef video clips for educational use. [Online]. Available: http://www.reefvid.org, Dec. 2010. → pages 62 [54] John A. Swets. Signal Detection Theory and ROC Analysis in Psychology and Diagnostics Collected Papers. Lawrence Erlbaum Associates, 1996. → pages 63 [55] C.J. van Rijsbergen. Information Retrieval. Butterworth, 1979. → pages 63 132 [56] Avinash L. Varna, Ashwin Swaminathan, and Min Wu. A decision theoretic framework for analyzing binary hash-based content identification systems. In Proceedings of the ACM workshop on Digital rights management, DRM ’08, pages 67–76, New York, NY, USA, 2008. ACM. ISBN 978-1-60558-290-0. doi:http://doi.acm.org/10.1145/1456520.1456532. URL http://doi.acm.org/10.1145/1456520.1456532. → pages 78 [57] Brian Kulis and Trevor Darrell. Learning to hash with binary reconstructive embeddings. In Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 1042–1050. 2009. → pages 78, 79 [58] Mani Malek Esmaeili, Mehrdad Fatourechi, and Rabab K. Ward. A robust and fast video copy detection system using content-based fingerprinting. IEEE Transactions on Information Forensics and Security, 6(1):213 –226, March 2011. ISSN 1556-6013. doi:10.1109/TIFS.2010.2097593. → pages 78, 79, 81, 86, 89 [59] Feng Hao, J. Daugman, and P. Zielinski. A fast search algorithm for a large fuzzy database. IEEE Transactions on Information Forensics and Security, 3 (2):203 –212, June 2008. ISSN 1556-6013. doi:10.1109/TIFS.2008.920726. → pages 78, 79, 111 [60] E. Rublee, V. Rabaud, K. Konolige, and G. Bradski. Orb: An efficient alternative to sift or surf. In IEEE International Conference onComputer Vision (ICCV), pages 2564 –2571, nov. 2011. doi:10.1109/ICCV.2011.6126544. → pages 78 [61] Michael Calonder, Vincent Lepetit, Christoph Strecha, and Pascal Fua. Brief: binary robust independent elementary features. In European conference on Computer vision, ECCV’10, pages 778–792, Berlin, Heidelberg, 2010. Springer-Verlag. ISBN 3-642-15560-X, 978-3-642-15560-4. URL http://dl.acm.org/citation.cfm?id=1888089.1888148. → pages [62] S. Leutenegger, M. Chli, and R.Y. Siegwart. Brisk: Binary robust invariant scalable keypoints. In IEEE International Conference on Computer Vision (ICCV), pages 2548 –2555, nov. 2011. doi:10.1109/ICCV.2011.6126542. → pages 78 [63] Ruslan R. Salakhutdinov and Geoffrey E. Hinton. Semantic hashing. In Proceedings of the SIGIR Workshop on Information Retrieval and Applications of Graphical Models. Elsevier, 2007. → pages 78 133 [64] Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral hashing. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), Dec. 2008. URL http://people.csail.mit.edu/torralba/publications/spectralhashing.pdf. → pages 79 [65] Rizwan Chaudhry and Yuri Ivanov. Fast approximate nearest neighbor methods for non-euclidean manifolds with applications to human activity analysis in videos. In Proceedings of the European conference on Computer vision, ECCV, pages 735–748, Berlin, Heidelberg, 2010. Springer-Verlag. → pages 79 [66] Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In ACM Symposium on Theory of Computing (STOC), pages 380 – 388, May 2002. URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.4064. → pages 79, 80, 111 [67] M. Muja and D.G. Lowe. Fast matching of binary features. In Conference on Computer and Robot Vision (CRV), pages 404 –410, may 2012. doi:10.1109/CRV.2012.60. → pages [68] Mohammad Norouzi, Ali Punjani, and David Fleet. Fast search in hamming space with multi-index hashing. In IEEE Computer Vision and Pattern Recognition (CVPR), 2012. → pages 79 [69] B. Kulis and K. Grauman. Kernelized locality-sensitive hashing for scalable image search. In IEEE International Conference onComputer Vision, pages 2130 –2137, Oct. 2009. doi:10.1109/ICCV.2009.5459466. → pages 79 [70] C. Bauer, R. Radhakrishnan, and Wenyu Jiang. Optimal configuration of hash table based multimedia fingerprint databases using weak bits. In IEEE International Conference on Multimedia and Expo (ICME), pages 1667 –1672, july 2010. doi:10.1109/ICME.2010.5583568. → pages 80 [71] Ina Dhring and Rainer Lienhart. Mining tv broadcasts 24/7 for recurring video sequences. In Dan Schonfeld, Caifeng Shan, Dacheng Tao, and Liang Wang, editors, Video Search and Mining, volume 287 of Studies in Computational Intelligence, pages 327–356. Springer Berlin / Heidelberg, 2010. → pages 80, 81, 89 [72] Mani Malekesmaeili, Mehrdad Fatourechi, and Rabab K. Ward. Video copy detection using temporally informative representative images. In 134 International Conference on Machine Learning and Applications, pages 69–74, Dec. 2009. → pages 81 [73] http://ipl.ece.ubc.ca/multimedia.html, Jan. 2012. → pages 89, 91, 115 [74] http://groups.csail.mit.edu/vision/tinyimages/, Aug. 2012. → pages 115 135
Thesis/Dissertation
eng
Electrical and Computer Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivs 3.0 Unported
Graduate
Multimedia copy detection
Text