Towards effective indexing for very large video sequence database

ABSTRACT

With rapid advances in video processing technologies and ever fast increments in network bandwidth, the popularity of video content publishing and sharing has made similarity search an indispensable operation to retrieve videos of user interests. The video similarity is usually measured by the percentage of similar frames shared by two video sequences, and each frame is typically represented as a high-dimensional feature vector. Unfortunately, high complexity of video content has posed the following major challenges for fast retrieval: (a) effective and compact video representations, (b) efficient similarity measurements, and (c) efficient indexing on the compact representations. In this paper, we propose a number of methods to achieve fast similarity search for very large video database. First, each video sequence is summarized into a small number of clusters, each of which contains similar frames and is represented by a novel compact model called Video Triplet (ViTri). ViTri models a cluster as a tightly bounded hypersphere described by its position, radius, and density. The ViTri similarity is measured by the volume of intersection between two hyperspheres multiplying the minimal density, i.e., the estimated number of similar frames shared by two clusters. The total number of similar frames is then estimated to derive the overall similarity between two video sequences. Hence the time complexity of video similarity measure can be reduced greatly. To further reduce the number of similarity computations on ViTris, we introduce a new one dimensional transformation technique which rotates and shifts the original axis system using PCA in such a way that the original inter-distance between two high-dimensional vectors can be maximally retained after mapping. An efficient B⁺-tree is then built on the transformed one dimensional values of ViTris' positions. Such a transformation enables B⁺-tree to achieve its optimal performance by quickly filtering a large portion of non-similar ViTris. Our extensive experiments on real large video datasets prove the effectiveness of our proposals that outperform existing methods significantly.

REFERENCES

• 1: http://www.virtualdub.org/.
• 2: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.142-153, June 01-04, 1998, Seattle, Washington, United States
• 3: Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
• 4: Kaushik Chakrabarti , Sharad Mehrotra, Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces, Proceedings of the 26th International Conference on Very Large Data Bases, p.89-100, September 10-14, 2000
• 5: H. Chang, S. Sull, and S. Lee. Efficient video indexing scheme for content-based retrieval. In IEEE Transactions on Circuits and Systems for Video Technology, 1999.
• 6: S. Cheung and A. Zakhor. Efficient video similarity measurement with video signature. In IEEE Transactions on Circuits and Systems for Video Technology, 2003.
• 7: P. Indyk, G. Iyengar, and N. Shivakumar. Finding pirated video sequences on the internet. In Tech. Rep., Stanford Infolab, 1999.
• 8: G. Iyengar and A. Lippman. Distributional clustering for efficient content-based retrieval of images and video. In ICIP, pages 81--84, 2000.
• 9: J. Jacquelin. Problem of hyperspace. In http: //maths-express.ifrance.com/mathsexpress/articles/voir/hyperchevre.htm, 2004.
• 10: C. Jensen, D. Lin, and B. C.Ooi. Query and update efficient b+-tree based indexing of moving objects. In VLDB, 2004.
• 11: H. Jin, B. Ooi, H. Shen, C. Yu, and A. Zhou. An Adaptive and Efficient Dimensionality Reduction Algorithm for High-Dimensional Indexing. In ICDE, pages 87--98, 2003.
• 12: Sang-Wook Kim , Charu C. Aggarwal , Philip S. Yu, Effective nearest neighbor indexing with the euclidean metric, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502588]
• 13: M. R. Naphade, R. Wang, and T. S. Huang. Multimodal pattern matching for audio-visual query and retrieval. In SPIE, pages 188--195, 2001.
• 14: N. Vasconcelos. On the complexity of probabilistic image retrieval. In ICCV, 2001.
• 15: Cui Yu , Beng Chin Ooi , Kian-Lee Tan , H. V. Jagadish, Indexing the Distance: An Efficient Method to KNN Processing, Proceedings of the 27th International Conference on Very Large Data Bases, p.421-430, September 11-14, 2001