Robust video fingerprinting via structural graphical models

Applications of video fingerprinting range from traditional video retrieval and authentication to the more recent problem of anti-piracy search brought about by the emergence of video websites such as Youtube. Video fingerprints offer the potential of identifying in a robust and scalable manner - illegal or undesirable uploads of copyrighted video content. The principal challenge in video fingerprinting is to extract reduced dimensionality descriptors that can withstand incidental spatial and temporal distortions to the video while still allowing the discrimination of distinct videos. To address this fundamental problem, we propose to first represent a video as a graphical structure which can encode temporal relationships between video shots that are crucial to uniquely identifying the video. Next, we leverage ideas from graph theory, namely the normalized cuts graph partitioning method to divide the video representation into sub-graphs. Robust dimensionality reduction applied to these sub-graphs yields the final video hash/fingerprint. Experimental results in the form of receiver operating characteristic (ROC) curves on video databases acquired from YouTube reveal that the proposed video fingerprinting can enable a much more favorable robustness vs. discriminability trade-off over state-of-the art algorithms in video hashing.