×

Dimensionality reduction for heterogeneous dataset in rushes editing. (English) Zbl 1181.68248

Summary: Rushes editing enables the computer to edit the film like a professional film cutter based on the raw footage. The most important issue in rushes editing is the generation of the effective, efficient, and robust descriptors for footage content analysis. Dimensionality reduction technology provides the means to generate such descriptors by seeking a low-dimensional equivalence of the high-dimensional video data using intelligent algorithms. However, existing dimensionality reduction techniques are not directly applicable to the editing of rushes because of the heterogeneity of rushes data. To deal with this heterogeneity, this paper proposes a novel non-linear dimensionality reduction algorithm called multi-layer isometric feature mapping (ML-Isomap).
First, a clustering algorithm is utilized to partition the high-dimensional data points into a set of data blocks in the high-dimensional feature space. Second, intra-cluster graphs are constructed based on the individual character of each data block to build the basic layer for the ML-Isomap. Third, the inter-cluster graph is constructed by analyzing the interrelation among these isolated data blocks to build the hyper-layers for the ML-Isomap. Finally, all the data points are mapped into the unique low-dimensional feature space by maintaining to the greatest extent the corresponding relations of the multiple layers in the high-dimensional feature space. Comparative experiments on synthetic data as well as real rushes editing tasks demonstrate that the proposed algorithm can reduce the dimensions of various datasets efficiently while preserving both the global structure and the local details of the heterogeneous dataset.

MSC:

68T10 Pattern recognition, speech recognition

Software:

clusfind
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Crittenden, R., Film and Video Editing (1995), Blueprint: Blueprint New York
[2] Dmytryk, E., On Film Editing: An Introduction to the Art of Film Construction (1984), Focal Press: Focal Press Boston
[3] Dancyger, K., The Technique of Film and Video Editing: History, Theory, and Practice (2007), Focal Press: Focal Press Burlington, MA, USA
[4] \( \langle;\) http://www-nlpir.nist.gov/projects/tv \(2007/ \rangle;\); \( \langle;\) http://www-nlpir.nist.gov/projects/tv \(2007/ \rangle;\)
[5] Over, P.; Smeaton, A. F.; Kelly, P., The TRECVID 2007 BBC rushes summarization evaluation pilot, (Proceedings of ACM International Workshop on TRECVID Video Summarization (2007)), 1-15
[6] Wang, F.; Ngo, C., Rushes video summarization by object and event understanding, (Proceedings of ACM International Workshop on TRECVID Video Summarization (2007)), 25-29
[7] Byrne, D.; Kehoe, P.; Lee, H.; Conaire, C.ó.; Smeaton, A. F.; Connor, N. E.; Jones, G. J., A user-centered approach to rushes summarisation via highlight-detected keyframes, (Proceedings of ACM International Workshop on TRECVID Video Summarization (2007)), 35-39
[8] Koskela, M.; Sjoberg, M.; Laaksonen, J.; Viitaniemi, V.; Muurinen, H., Rushes summarization with self-organizing maps, (Proceedings of ACM International Workshop on TRECVID Video Summarization (2007)), 45-49
[9] Liu, Y.; Liu, Y.; Zhang, Y., The Hong Kong Polytechnic University at TRECVID 2007 BBC rushes summarization, (Proceedings of ACM International Workshop on TRECVID Video Summarization (2007)), 50-54
[10] Dumont, E.; Merialdo, B., Split-screen dynamically accelerated Video Summaries, (Proceedings of ACM International Workshop on TRECVID Video Summarization (2007)), 55-59
[11] Chen, F.; Cooper, M.; Adcock, J., Video summarization preserving dynamic content, (Proceedings of the ACM International Workshop on TRECVID Video Summarization (2007)), 40-44
[12] Beran, V.; Hradis, M.; Herout, A.; Sumec, S.; Potúcek, I.; Zemcik, P.; Mlích, J.; Láník, A.; ChmelaD, P., Video summarization at Brno University of Technology, (Proceedings of the ACM International Workshop on TRECVID Video Summarization (2007)), 16-19
[13] Detyniecki, M.; Marsala, C., Video rushes summarization by adaptive acceleration and stacking of shots, (Proceedings of the ACM International Workshop on TRECVID Video Summarization (2007)), 65-69
[14] Pan, C.; Chuang, Y.; Hsu, W. H., NTU TRECVID-2007 fast rushes summarization system, (Proceedings of the ACM International Workshop on TRECVID Video Summarization (2007)), 74-78
[15] Wang, T.; Gao, Y.; Li, J.; Wang, P. P.; Tong, X.; Hu, W.; Zhang, Y.; Li, J., THU-ICRC at rush summarization of TRECVID 2007, (Proceedings of the ACM International Workshop on TRECVID Video Summarization (2007)), 79-83
[16] Valdés, V.; Martínez, J. M., On-line video skimming based on histogram similarity, (Proceedings of the ACM International Workshop on TRECVID Video Summarization (2007)), 94-98
[17] Hauptmann, A. G.; Christel, M. G.; Lin, W.; Maher, B.; Yang, J.; Baron, R. V.; Xiang, G., Clever clustering vs. simple speed-up for summarizing rushes, (Proceedings of the ACM International Workshop on TRECVID Video Summarization (2007)), 20-24
[18] Bailer, W.; Lee, F.; Thallinger, G., Skimming rushes video using retake detection, (Proceedings of the ACM International Workshop on TRECVID Video Summarization (2007)), 60-64
[19] Le, D.; Satoh, S., National institute of informatics, Japan at TRECVID 2007: BBC rushes summarization, (Proceedings of the ACM International Workshop on TRECVID Video Summarization (2007)), 70-73
[20] M.A. Carreira-Perpinan, A review of dimension reduction techniques, Technical Report CS-96-09, January 1997.; M.A. Carreira-Perpinan, A review of dimension reduction techniques, Technical Report CS-96-09, January 1997.
[21] Seung, H. S.; Lee, D. D., The manifold ways of perception, Science, 290, 2268-2269 (2000)
[22] Tenenbaum, J. B.; Silva, V.; Langford, J. C., A global geometric framework for nonlinear dimensionality reduction, Science, 290, 2319-2323 (2000)
[23] Stich, T.; Magnor, M., Keyframe animation from video, (Proceedings of IEEE International Conference on Image Processing (2006)), 2713-2716
[24] Zhu, L.; Li, G.; Katsaggelos, A. K., Locally embedded linear subspaces for efficient video indexing and retrieval, (Proceedings of ICME (2006)), 1765-1768
[25] Roweis, S. T.; Saul, L. K., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 2323-2326 (2000)
[26] Belkin, M.; Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput., 15, 6, 1373-1396 (2003) · Zbl 1085.68119
[27] Donoho, D. L.; Grimes, C., Hessian eigenmaps: new locally linear embedding techniques for high-dimensional data, Proc. Nat. Acad. Sci., 102, 21, 7426-7431 (2005) · Zbl 1405.42043
[28] Pless, R., Image spaces and video trajectories: using Isomap to explore video sequences, (Proceedings of IEEE International Conference on Computer Vision (2003))
[29] Apté, C.; Hong, S. J.; Hosking, J. R.M.; Lepre, J.; Pednault, E. P.D.; Rosen, B. K., Decomposition of heterogeneous classification problems, Intell. Data Anal., 2, 1-4, 81-96 (1998)
[30] Hotelling, H., Analysis of a complex of statistical variables into principal components, J. Edu. Psychol., 24 (1933), 417-441, 498-520
[31] Fisher, R. A., The use of multiple measurements in taxonomic problems, Ann. Eugen., 7, 179-188 (1936)
[32] Kruskal, J. B.; Wish, M., Multidimensional Scaling (1977), Sage Publications: Sage Publications Beverly Hills, CA
[33] Young, F. W.; Hamer, R. M., Theory and Applications of Multidimensional Scaling (1994), Eribaum Associates: Eribaum Associates Hillsdale, NJ
[34] Loog, M.; Duin, R. P.W.; Haeb-Umbach, R., Multiclass linear dimension reduction by weighted pairwise Fisher criteria, IEEE Trans. Pattern Anal. Mach. Intell., 23, 7, 762-766 (2001)
[35] Tao, D.-C.; Li, X.-L.; Wu, X.-D.; Maybank, S. J., General averaged divergences analysis, (IEEE International Conference on Data Mining (ICDM) (2007)), 302-311
[36] Tao, D.-C.; Li, X.-L.; Wu, X.-D.; Maybank, S. J., General tensor discriminant analysis and gabor features for gait recognition, IEEE Trans. Pattern Anal. Mach. Intell. (TPAMI), 29, 10, 1700-1715 (2007)
[37] Bronstein, A. M.; Bronstein, M. M.; Kimmel, R., Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching, Proc. Nat. Acad. Sci. (PNAS), 103/5, 1168-1172 (2006) · Zbl 1160.65306
[38] Chan, K. C.C.; Wong, A. K.C., A statistical technique for extracting classificatory knowledge from databases, (Piatesky-Shapiro, G.; Frawley, W. J., Knowledge Discovery in Databases (1991), AAAI Press/MIT Press: AAAI Press/MIT Press Cambridge, MA), 108-123
[39] Au, W. H.; Chan, K. C.C.; Wong, A. K.C.; Yang, W., Attribute clustering for grouping, selection and classification of gene expression data, IEEE/ACM Trans. Comput. Biol. Bioinformatics, 2, 2, 83-101 (2005)
[40] Peng, H. C.; Long, F.; Ding, C., Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy, IEEE Trans. Pattern Anal. Mach. Intell., 27, 8, 1226-1238 (2005)
[41] Zhang, J.; Li, S. Z.; Wang, J., Manifold Learning and Applications in Recognition, Intelligent Multimedia Processing with Soft Computing (2004), Springer: Springer Heidelberg
[42] Scholkopf, B.; Smola, A. J.; Muller, K. R., Nonlinear component analysis as a kernel eigenvalue problem, Neural Comput., 10, 5, 1299-1319 (1998)
[43] Baudat, G.; Anouar, F., Generalized discriminant analysis using a kernel approach, Neural Comput., 12, 10, 2385-2404 (2000)
[44] Kohonen, T., Self-organizing Maps (2001), Springer: Springer Berlin · Zbl 0957.68097
[45] Kégl, B.; Krzyzak, A.; Linder, T.; Zeger, K., Learning and design of principal curves, IEEE Trans. Pattern Anal. Mach. Intell., 22, 3, 281-297 (2000)
[46] de Silva, V.; Tenenbaum, J. B., Global versus local methods in nonlinear dimensionality reduction, Proc. Adv. Neural Inf. Process. Syst., 15, 705-712 (2003)
[47] Bruno, R., Data Structures and Algorithms: With Object Oriented Design Patterns in \(C ++ (1999)\), Wiley: Wiley New York
[48] Agnarsson, G.; Greenlaw, R., Graph Theory (2007), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1179.05001
[49] Mardia, K. V.; Kent, J. T.; Bibby, J. M., Multivariate Analysis (1979), Academic Press: Academic Press London, UK · Zbl 0432.62029
[50] Jenkins, O.; Mataric, M., A spatio-temporal extension to Isomap nonlinear dimension reduction, (Proceedings of 21st International Conference Machine Learning (2004))
[51] Vlachos, M.; Domeniconi, C.; Gunopulos, D.; Kollios, G.; Koudas, N., Non-linear dimensionality reduction techniques for classification and visualization, (Proceedings of 8th SIGKDD (2002))
[52] Geng, X.; Zhan, D.; Zhou, Z., Supervised nonlinear dimensionality reduction for visualization and classification, IEEE Trans. SMC—Part B, 35, 6, 1098-1107 (2005)
[53] Chen, J.; Wang, R.; Shan, S.; Chen, X.; Gao, W., Isomap based on the image Euclidean distance, (Proceedings of 18th International Conference on Pattern Recognition (2006))
[54] Sahouria, E.; Zakhor, A., Content analysis of video using principal components, IEEE Trans. CSVT, 9, 8, 1290-1298 (1999)
[55] Jain, A. K., Algorithms for Clustering Data (1988), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0665.62061
[56] Kaufman, L.; Rousseeuw, P. J., Finding Groups in Data: An Introduction to Cluster Analysis (1990), Wiley: Wiley New York · Zbl 1345.62009
[57] MacQueen, J. B., Some methods for classification and analysis of multivariate observations, (Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, vol. 1 (1967), University of California Press: University of California Press Berkeley, CA), 281-297
[58] Ng, R. T.; Han, J., CLARANS: a method for clustering objects for spatial data mining, IEEE Trans. Knowl. Data Eng., 14, 5, 1003-1016 (2002)
[59] Ester, M.; Kriegel, H. P.; Sander, J.; Xu, X., A density-based algorithm for discovering clusters in large spatial databases with noise, (Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD) (1996))
[60] Johnson, S. C., Hierarchical clustering schemes, Psychometrika, 2, 241-254 (1967) · Zbl 1367.62191
[61] A.K. Jain, M.N. Murty, P.J. Flynn, Data clustering: a review, in: ACM Computing Surveys (CSUR), Volume 31(3), ACM Press, New York, 1999, pp. 264-323.; A.K. Jain, M.N. Murty, P.J. Flynn, Data clustering: a review, in: ACM Computing Surveys (CSUR), Volume 31(3), ACM Press, New York, 1999, pp. 264-323.
[62] Baumgartner, C.; Plant, C.; Kailing, K.; Kriegel, H. P.; Kroger, P., Subspace selection for clustering high-dimensional data, (Proceedings of the 4th IEEE International Conference on Data Mining ICDM (2004))
[63] Peltier, M. A.; Dubuisson, B., A fuzzy clustering algorithm based on the k-nearest neighbors rule for the detection of evolution, Proc. Int. Conf. Syst. Man Cybern., 4, 696-701 (1993)
[64] Battiato, S.; Blasi, G. D.; Reforgiato, R. D., Advanced indexing schema for imaging applications: three-case studies, IET Image Process., 1, 3, 249-268 (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.