Zi Huang
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.
- Adjeroh, D. A., Lee, M.-C., and King, I. 1999. A distance measure for video sequences. Comput. Vis. Image Understand. 75, 1-2, 25--45. Google Scholar
Digital Library
- Berchtold, S., Böhm, C., and Kriegel, H.-P. 1998. The pyramid-technique: Towards breaking the curse of dimensionality. In Proceedings of the SIGMOD Conference. 142--153. Google ScholarDigital Library
- Berchtold, S., Keim, D. A., and Kriegel, H.-P. 1996. The x-tree: An index structure for high-dimensional data. In Proceedings of the VLDB. 28--39. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Böhm, C., Berchtold, S., and Keim, D. A. 2001. Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. ACM Comput. Surv. 33, 3, 322--373. Google ScholarDigital Library
- Chakrabarti, K. and Mehrotra, S. 2000. Local dimensionality reduction: A new approach to indexing high dimensional spaces. In Proceedings of VLDB. 89--100. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Chen, L. and Chua, T.-S. 2001. A match and tiling approach to content-based video retrieval. In Proceedings of ICME. 417--420.Google Scholar
- 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.Google ScholarDigital Library
- Chen, L., Özsu, M. T., and Oria, V. 2005. Robust and fast similarity search for moving object trajectories. In Proceedings of the SIGMOD Conference. 491--502. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Chiu, C.-Y., Li, C.-H., Wang, H.-A., Chen, C.-S., and Chien, L.-F. 2006. A time warping based approach for video copy detection. In Proceedings of ICPR. Vol. 3. 228--231. Google ScholarDigital Library
- Cui, B., Shen, J., Cong, G., Shen, H. T., and Yu, C. 2006. Exploring composite acoustic features for efficient music similarity query. In Proceedings of the ACM Multimedia Conference. 412--420. Google ScholarDigital Library
- Dadason, K., Lejsek, H., Ásmundsson, F. H., Jónsson, B. T., and Amsaleg, L. 2007. Videntifier: Identifying pirated videos in real-time. In Proceedings of the ACM Multimedia Conference. 471--472. Google ScholarDigital Library
- DeMenthon, D., Kobla, V., and Doermann, D. S. 1998. Video summarization by curve simplification. In Proceedings of the ACM Multimedia Conference. 211--218. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Franco, A., Lumini, A., and Maio, D. 2007. MKL-tree: An index structure for high-dimensional vector spaces. Multimed. Syst. 12, 6, 533--550.Google ScholarDigital Library
- Fukunaga, K. 1990. Introduction to Statistical Pattern Recognition, 2nd ed. Academic Press, New York, NY. Google ScholarDigital Library
- Gibbon, D. C. 2005. Introduction to video search engines. In Proceedings of WWW.Tutorial.Google Scholar
- Gionis, A., Indyk, P., and Motwani, R. 1999. Similarity search in high dimensions via hashing. In Proceedings of VLDB. 518--529. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Hoad, T. C. and Zobel, J. 2006. Detection of video sequences using compact signatures. ACM Trans. Inf. Syst. 24, 1, 1--50. Google ScholarDigital Library
- Houle, M. E. and Sakuma, J. 2005. Fast approximate similarity search in extremely high-dimensional data sets. In Proceedings of ICDE. 619--630. Google ScholarDigital Library
- Iyengar, G. and Lippman, A. 2000. Distributional clustering for efficient content-based retrieval of images and video. In Proceedings of ICIP. 81--84.Google Scholar
- Jagadish, H. V., Ooi, B. C., Tan, K.-L., Yu, C., and Zhang, R. 2005. IDistance: An adaptive B+-tree based indexing method for nearest neighbor search. ACM Trans. Database Syst. 30, 2, 364--397. Google ScholarDigital Library
- Jolliffe, I. T. 2002. principal component Analysis, 2nd ed. Springer-Verlag, Berlin, Germany.Google Scholar
- 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. Google ScholarDigital Library
- Keogh, E. J. 2002. Exact indexing of dynamic time warping. In Proceedings of VLDB. 406--417. Google ScholarDigital Library
- Kim, C. and Vasudev, B. 2005. Spatiotemporal sequence matching for efficient video copy detection. IEEE Trans. Circ. Syst. Video Tech. 15, 1, 127--132. Google ScholarDigital Library
- Law-To, J., Chen, L., Joly, A., Laptev, I., Buisson, O., Gouet-Brunet, V., Boujemaa, N., and Stentiford, F. 2007. Video copy detection: a comparative study. In Proceedings of CIVR. 371--378. Google ScholarDigital Library
- Lee, J., Oh, J.-H., and Hwang, S. 2005. STRG-index: Spatio-temporal region graph indexing for large video databases. In Proceedings of the SIGMOD Conference. 718--729. Google ScholarDigital Library
- Lee, S.-L., Chun, S.-J., Kim, D.-H., Lee, J.-H., and Chung, C.-W. 2000. Similarity search for multidimensional data sequences. In Proceedings of ICDE. 599--608. Google ScholarDigital Library
- Lienhart, R. 1999. Comparison of automatic shot boundary detection algorithms. In Proceedings of SPIE: Storage and Retrieval for Image and Video Databases. 209--301.Google Scholar
- Liu, X., Zhuang, Y., and Pan, Y. 1999. A new approach to retrieve video by example video clip. In Proceedings of the ACM Multimedia Conference. Vol. 2. 41--44. Google ScholarDigital Library
- Mohan, R. 1998. Video sequence matching. In Proceedings of the ICASSP. 3697--3700.Google ScholarCross Ref
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Rubner, Y., Puzicha, J., Tomasi, C., and Buhmann, J. M. 2001. Empirical evaluation of dissimilarity measures for color and texture. Comput. Vis. Image Understand. 84, 1, 25--43. Google ScholarDigital Library
- Santini, S. and Jain, R. 1999. Similarity measures. IEEE Trans. Patt. Anal. Mach. Intell. 21, 9, 871--883. Google ScholarDigital Library
- Sarukkai, R. 2005. Video search: Opportunities & challenges. In Proceedings of the Conference on Multimedia Information Retrieval. Keynote speech. Google ScholarDigital Library
- Sebe, N., Lew, M. S., and Huijsmans, D. P. 2000. Toward improved ranking metrics. IEEE Trans. Patt. Anal. Mach. Intell. 22, 10, 1132--1143. Google ScholarDigital Library
- Shen, H. T., Ooi, B. C., Zhou, X., and Huang, Z. 2005. Towards effective indexing for very large video sequence database. In Proceedings of the SIGMOD Conference. 730--741. Google ScholarDigital Library
- Shen, H. T., Zhou, X., Huang, Z., and Shao, J. 2007. Statistical summarization of content features for fast near-duplicate video detection. In Proceedings of the ACM Multimedia Conference. 164--165. Google ScholarDigital Library
- Smeulders, A. W. M., Worring, M., Santini, S., Gupta, A., and Jain, R. 2000. Content-based image retrieval at the end of the early years. IEEE Trans. Patt. Anal. Mach. Intell. 22, 12, 1349--1380. Google ScholarDigital Library
- Tuncel, E., Ferhatosmanoglu, H., and Rose, K. 2002. VQ-index: An index structure for similarity searching in multimedia databases. In Proceedings of the ACM Multimedia Conference. 543--552. Google ScholarDigital Library
- Vlachos, M., Gunopulos, D., and Kollios, G. 2002. Discovering similar multidimensional trajectories. In Proceedings of the ICDE. 673--684. Google ScholarDigital Library
- Weber, R., Schek, H.-J., and Blott, S. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proceedings of the VLDB. 194--205. Google ScholarDigital Library
- Wu, X., Hauptmann, A. G., and Ngo, C.-W. 2007. Practical elimination of near-duplicates from Web video search. In Proceedings of the ACM Multimedia Conference. 218--227. Google ScholarDigital Library
- Wu, Y., Zhuang, Y., and Pan, Y. 2000. Content-based video similarity model. In Proceedings of the ACM Multimedia Conference. 465--467. Google ScholarDigital Library
- Zhou, J. and Zhang, X.-P. 2005. Automatic identification of digital video based on shot-level sequence matching. In Proceedings of the ACM Multimedia Conference. 515--518. Google ScholarDigital Library
- 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.Google ScholarDigital Library
Index Terms
- Bounded coordinate system indexing for real-time video clip search
Recommendations
Clip-based similarity measure for query-dependent clip retrieval and video summarization
This paper proposes a new approach and algorithm for the similarity measure of video clips. The similarity is mainly based on two bipartite graph matching algorithms: maximum matching (MM) and optimal matching (OM). MM is able to rapidly filter ...
Clip based video summarization and ranking
CIVR '08: Proceedings of the 2008 international conference on Content-based image and video retrievalIn this paper, we present a new algorithm for video clip summarization and ranking, which is mainly based on a clip based video similarity measure and the affinity propagation clustering (AP) algorithm. We propose a proportional max-weighted bipartite ...
Video clip recommendation model by sentiment analysis of time-sync comments
AbstractWith the advent of video time-sync comments, users can not only comment the videos on the Internet, but also share their feelings with others. However, the number of the videos on the Internet is so huge that users do not have enough time and ...
Comments