Efficient video identification based on locality sensitive hashing and triangle inequality

Abstract

Searching for duplicated version video clips in large video database, or video identification, requires fast and robust similarity search in high-dimensional space. Locality sensitive hashing, or LSH, is a well-known indexing method for efficient approximate similarity search in such space. In this thesis, we present a highly efficient video identification method for transcoded video content based on locality sensitive hashing and triangle inequality. To store large volume of videos, we design a small feature dataset and index the dataset using improved locality sensitive hashing. In addition, we employ triangle inequality to further enhance the system efficiency. Experimental results demonstrate that once the features of a given 8s query video are extracted, it takes about 0.17s to retrieve it from a 96-hour video database. Furthermore, our system is robust to the changes of the query videos on frame size, frame rate and compression bit-rate.