Desynchronization resilient video fingerprinting via randomized, low-rank tensor approximations

The problem of summarizing videos by short fingerprints or hashes has garnered significant attention recently. While traditional applications of video hashing lie in database search and content authentication, the emergence of websites such as YouTube and DailyMotion poses a challenging problem of anti-piracy video search. That is, hashes or fingerprints of an original video (provided to YouTube by the content owner) must be matched against those uploaded to YouTube by users to identify instances of "illegal" or undesirable uploads. Because the uploaded videos invariably differ from the original in their digital representation (owing to incidental or malicious distortions), robust video hashes are desired. In this paper, we model videos as order-3 tensors and use multilinear subspace projections, such as a reduced rank parallel factor analysis (PARAFAC) to construct video hashes. We observe that unlike most standard descriptors of video content, tensor based subspace projections can offer excellent robustness while effectively capturing the spatio-temporal essence of the video for discriminability. We further randomize the construction of the hash by dividing the video into randomly selected overlapping sub-cubes to prevent against intentional guessing and forgery. The most significant gains are seen for the difficult attacks of spatial (e.g. geometric) as well as temporal (random frame dropping) desynchronization. Experimental validation is provided in the form of ROC curves and we further perform detection-theoretic analysis which closely mimics empirically observed probability of error.