Bounded coordinate system indexing for real-time video clip search

ABSTRACT

Recently, video clips have become very popular online. The massive influx of video clips has created an urgent need for video search engines to facilitate retrieving relevant clips. Different from traditional long videos, a video clip is a short video often expressing a moment of significance. Due to the high complexity of video data, efficient video clip search from large databases turns out to be very challenging. We propose a novel video clip representation model called the Bounded Coordinate System (BCS), which is the first single representative capturing the dominating content and content—changing trends of a video clip. It summarizes a video clip by a coordinate system, where each of its coordinate axes is identified by principal component analysis (PCA) and bounded by the range of data projections along the axis. The similarity measure of BCS considers the operations of translation, rotation, and scaling for coordinate system matching. Particularly, rotation and scaling reflect the difference of content tendencies. Compared with the quadratic time complexity of existing methods, the time complexity of measuring BCS similarity is linear. The compact video representation together with its linear similarity measure makes real-time search from video clip collections feasible. To further improve the retrieval efficiency for large video databases, a two-dimensional transformation method called Bidistance Transformation (BDT) is introduced to utilize a pair of optimal reference points with respect to bidirectional axes in BCS. Our extensive performance study on a large database of more than 30,000 video clips demonstrates that BCS achieves very high search accuracy according to human judgment. This indicates that content tendencies are important in determining the meanings of video clips and confirms that BCS can capture the inherent moment of video clip to some extent that better resembles human perception. In addition, BDT outperforms existing indexing methods greatly. Integration of the BCS model and BDT indexing can achieve real-time search from large video clip databases.

REFERENCES

• 1: Donald A. Adjeroh , M. C. Lee , Irwin King, A distance measure for video sequences, Computer Vision and Image Understanding, v.75 n.1-2, p.25-45, July/Aug. 1999 [doi>10.1006/cviu.1999.0764]
• 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: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 4: Bertini, M., Bimbo, A. D., and Nunziati, W. 2006. Video clip matching using mpeg-7 descriptors and edit distance. In Proceedings of the CIVR. 133--142.
• 5: 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]
• 6: 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
• 7: Chang, H. S., Sull, S., and Lee, S. U. 1999. Efficient video indexing scheme for content-based retrieval. IEEE Trans. Circ. Syst. Video Tech. 9, 8, 1269--1279.
• 8: Chen, L. and Chua, T.-S. 2001. A match and tiling approach to content-based video retrieval. In Proceedings of ICME. 417--420.
• 9: Chen, L., Özsu, M. T., and Oria, V. 2004. Mindex: An efficient index structure for salient-object-based queries in video databases. Multimed. Syst. 10, 1, 56--71.
• 10: Lei Chen , M. Tamer Özsu , Vincent Oria, Robust and fast similarity search for moving object trajectories, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066213]
• 11: Cheung, S.-C. S. and Zakhor, A. 2003. Efficient video similarity measurement with video signature. IEEE Trans. Circ. Syst. Video Tech. 13, 1, 59--74.
• 12: Cheung, S.-C. S. and Zakhor, A. 2005. Fast similarity search and clustering of video sequences on the world-wide-Web. IEEE Trans. Multimed. 7, 3, 524--537.
• 13: Chih-Yi Chiu , Cheng-Hung Li , Hsiang-An Wang , Chu-Song Chen , Lee-Feng Chien, A Time Warping Based Approach for Video Copy Detection, Proceedings of the 18th International Conference on Pattern Recognition, p.228-231, August 20-24, 2006 [doi>10.1109/ICPR.2006.187]
• 14: Bin Cui , Jialie Shen , Gao Cong , Heng Tao Shen , Cui Yu, Exploring composite acoustic features for efficient music similarity query, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA [doi>10.1145/1180639.1180725]
• 15: Kristleifur Dadason , Herwig Lejsek , Fridrik Ásmundsson , Björn Jónsson , Laurent Amsaleg, Videntifier: identifying pirated videos in real-time, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291346]
• 16: Daniel DeMenthon , Vikrant Kobla , David Doermann, Video summarization by curve simplification, Proceedings of the sixth ACM international conference on Multimedia, p.211-218, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290773]
• 17: Ferman, A. M. and Tekalp, A. M. 2003. Two-stage hierarchical video summary extraction to match low-level user browsing preferences. IEEE Trans. Multimed. 5, 2, 244--256.
• 18: Franco, A., Lumini, A., and Maio, D. 2007. MKL-tree: An index structure for high-dimensional vector spaces. Multimed. Syst. 12, 6, 533--550.
• 19: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 20: Gibbon, D. C. 2005. Introduction to video search engines. In Proceedings of WWW.Tutorial.
• 21: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 22: Hampapur, A., Hyun, K.-H., and Bolle, R. M. 2002. Comparison of sequence matching techniques for video copy detection. In Proceedings of SPIE: Storage and Retrieval for Image and Video Databases. 194--201.
• 23: Ho, Y.-H., Lin, C.-W., Chen, J.-F., and Liao, H.-Y. M. 2006. Fast coarse-to-fine video retrieval using shot-level spatio-temporal statistics. IEEE Trans. Circ. Syst. Video Tech. 16, 5, 642--648.
• 24: Justin Zobel , Timothy C. Hoad, Detection of video sequences using compact signatures, ACM Transactions on Information Systems (TOIS), v.24 n.1, p.1-50, January 2006 [doi>10.1145/1125857.1125858]
• 25: Michael E. Houle , Jun Sakuma, Fast Approximate Similarity Search in Extremely High-Dimensional Data Sets, Proceedings of the 21st International Conference on Data Engineering, p.619-630, April 05-08, 2005 [doi>10.1109/ICDE.2005.66]
• 26: Iyengar, G. and Lippman, A. 2000. Distributional clustering for efficient content-based retrieval of images and video. In Proceedings of ICIP. 81--84.
• 27: H. V. Jagadish , Beng Chin Ooi , Kian-Lee Tan , Cui Yu , Rui Zhang, iDistance: An adaptive B⁺-tree based indexing method for nearest neighbor search, ACM Transactions on Database Systems (TODS), v.30 n.2, p.364-397, June 2005 [doi>10.1145/1071610.1071612]
• 28: Jolliffe, I. T. 2002. principal component Analysis, 2nd ed. Springer-Verlag, Berlin, Germany.
• 29: Kashino, K., Kurozumi, T., and Murase, H. 2003. A quick search method for audio and video signals based on histogram pruning. IEEE Trans. Multimed. 5, 3, 348--357.
• 30: Eamonn Keogh, Exact indexing of dynamic time warping, Proceedings of the 28th international conference on Very Large Data Bases, p.406-417, August 20-23, 2002, Hong Kong, China
• 31: Kim, C. and Vasudev, B. 2005. Spatiotemporal sequence matching for efficient video copy detection. IEEE Trans. Circ. Syst. Video Tech. 15, 1, 127--132.
• 32: Julien Law-To , Li Chen , Alexis Joly , Ivan Laptev , Olivier Buisson , Valerie Gouet-Brunet , Nozha Boujemaa , Fred Stentiford, Video copy detection: a comparative study, Proceedings of the 6th ACM international conference on Image and video retrieval, p.371-378, July 09-11, 2007, Amsterdam, The Netherlands [doi>10.1145/1282280.1282336]
• 33: JeongKyu Lee , JungHwan Oh , Sae Hwang, STRG-Index: spatio-temporal region graph indexing for large video databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066239]
• 34: Similarity Search for Multidimensional Data Sequences, Proceedings of the 16th International Conference on Data Engineering, p.599, February 28-March 03, 2000
• 35: Lienhart, R. 1999. Comparison of automatic shot boundary detection algorithms. In Proceedings of SPIE: Storage and Retrieval for Image and Video Databases. 209--301.
• 36: Xiaoming Liu , Yueting Zhuang , Yunhe Pan, A new approach to retrieve video by example video clip, Proceedings of the seventh ACM international conference on Multimedia (Part 2), p.41-44, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319878.319889]
• 37: Mohan, R. 1998. Video sequence matching. In Proceedings of the ICASSP. 3697--3700.
• 38: Naphade, M. R., Yeung, M. M., and Yeo, B.-L. 2000. A novel scheme for fast and efficient video sequence matching using compact signatures. In Proceedings of SPIE: Storage and Retrieval for Image and Video Databases. 564--572.
• 39: Peng, Y. and Ngo, C.-W. 2006. Clip-based similarity measure for query-dependent clip retrieval and video summarization. IEEE Trans. Circ. Syst. Video Tech. 16, 5, 612--627.
• 40: Yossi Rubner , Jan Puzicha , Carlo Tomasi , Joachim M. Buhmann, Empirical evaluation of dissimilarity measures for color and texture, Computer Vision and Image Understanding, v.84 n.1, p.25-43, October 2001 [doi>10.1006/cviu.2001.0934]
• 41: Simone Santini , Ramesh Jain, Similarity Measures, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.9, p.871-883, September 1999 [doi>10.1109/34.790428]
• 42: Ramesh Sarukkai, Video search: opportunities & challenges, Proceedings of the 7th ACM SIGMM international workshop on Multimedia information retrieval, p.2-2, November 10-11, 2005, Hilton, Singapore [doi>10.1145/1101826.1101828]
• 43: Nicu Sebe , Michael S. Lew , Dionysius P. Huijsmans, Toward Improved Ranking Metrics, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.10, p.1132-1143, October 2000 [doi>10.1109/34.879793]
• 44: Heng Tao Shen , Beng Chin Ooi , Xiaofang Zhou, Towards effective indexing for very large video sequence database, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066240]
• 45: Heng Tao Shen , Xiaofang Zhou , Zi Huang , Jie Shao, Statistical summarization of content features for fast near-duplicate video detection, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291271]
• 46: Arnold W. M. Smeulders , Marcel Worring , Simone Santini , Amarnath Gupta , Ramesh Jain, Content-Based Image Retrieval at the End of the Early Years, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.12, p.1349-1380, December 2000 [doi>10.1109/34.895972]
• 47: Ertem Tuncel , Hakan Ferhatosmanoglu , Kenneth Rose, VQ-index: an index structure for similarity searching in multimedia databases, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France [doi>10.1145/641007.641117]
• 48: Michail Vlachos , Dimitrios Gunopoulos , George Kollios, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
• 49: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 50: Xiao Wu , Alexander G. Hauptmann , Chong-Wah Ngo, Practical elimination of near-duplicates from web video search, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291280]
• 51: Yi Wu , Yueting Zhuang , Yunhe Pan, Content-based video similarity model, Proceedings of the eighth ACM international conference on Multimedia, p.465-467, October 2000, Marina del Rey, California, United States [doi>10.1145/354384.376380]
• 52: Jian Zhou , Xiao-Ping Zhang, Automatic identification of digital video based on shot-level sequence matching, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101265]
• 53: Zhu, X., Wu, X., Fan, J., Elmagarmid, A. K., and Aref, W. G. 2004. Exploring video content structure for hierarchical summarization. Multimed. Syst. 10, 2, 98--115.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Abstracting methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Retrieval models

General Terms:
Algorithms, Design, Experimentation

Keywords:
Video search, indexing, query processing, summarization