Irrelevant frame removal for scene analysis using video hyperclique pattern and spectrum analysis


  • Yuchou Chang University of Wisconsin - Milwaukee
  • Hong Lin Yale University





Content-Based Video Retrieval, Fibonacci Lattice, Hyperclique Pattern, Irrelevant Removal, Log Spectrum.


Video often include frames that are irrelevant to the scenes for recording. These are mainly due to imperfect shooting, abrupt movements of camera, or unintended switching of scenes. The irrelevant frames should be removed before the semantic analysis of video scene is performed for video retrieval. An unsupervised approach for automatic removal of irrelevant frames is proposed in this paper. A novel log-spectral representation of color video frames based on Fibonacci lattice-quantization has been developed for better description of the global structures of video contents to measure similarity of video frames. Hyperclique pattern analysis, used to detect redundant data in textual analysis, is extended to extract relevant frame clusters in color videos. A new strategy using the k-nearest neighbor algorithm is developed for generating a video frame support measure and an h-confidence measure on this hyperclique pattern based analysis method. Evaluation of the proposed irrelevant video frame removal algorithm reveals promising results for datasets with irrelevant frames.

Author Biography

Yuchou Chang, University of Wisconsin - Milwaukee

I am a PhD candidate in Electrical Engineering and Computer Science Department, University of Wisconsin - Milwaukee, USA. My research areas include pattern recognition, image processing, computer vision, biomedical imaging, machine learning, signal processing. I have around 30 peer-reviewed publications.


[1] A.Angelova, “Data Pruningâ€, Thesis, California Institute of Technology, (2004).

[2] A. Angelova, Y. Abu-Mostafa, and P. Perona, “Pruning Training Sets for Learning of Object Categoriesâ€, IEEE International Conference on Computer Vision and Pattern Recognition, vol.1, (2005), pp.494-501.

[3] D. Angluin, and P. Laird, “Learning from Noisy Examplesâ€, Machine Learning, vol.2, no.4, (1988), pp.343-370.

[4] R.A. Baeza-Yates, and B. Ribeiro-Neto, “Modern Information Retrievalâ€, Addison-Wesley Longman Publishing, (1999).

[5] S. Basu, M. Naphade, and J.R. Smith, “A Statistical Modeling Approach to Content Based Retrievalâ€, IEEE International Conference on Acoustics, Speech, and Signal Processing, vol.4, (2002), pp.480-483.

[6] Brodley, C.E., and Friedl, M.A., Identifying Mislabeled Training Data, Journal of Artificial Intelligence Research, vol.11, pp.131-167, 1999.

[7] Y. Chi, and M.K.H. Leung, “Part-Based Object Retrieval in Cluttered Environmentâ€, IEEE Transactions on Analysis and Machine Intelligence, vol.29, no.5, (2007), pp.890-895.

[8] B.V. Dasarathy, “Nearest Neighbor (NN) Norms: NN Pattern Classification Techniquesâ€, IEEE Computer Society Press, (1990).

[9] T. Deselaers, D. Keysers, and H. Ney, “Clustering Visually Similar Images to Improve Image Search Enginesâ€, Informatiktage 2003 der Gesellschaft für Informatik, Germany, (2003).

[10] L.Y. Duan, M. Xu, Q. Tian, C.S. Xu, and J.S. Jin, “A Unified Framework for Semantic Shot Classification in Sports Videoâ€, IEEE Transactions on Multimedia, vol.7, no. 6, (2005), pp.1066-1083.

[11] L. Ertoz, M. Steinbach, and V. Kumar, “Finding Clusters of Different Sizes, Shapes and Densities in Noisy, High Dimensional Dataâ€, Proceedings of SIAM International Conference on Data Mining, (2003).

[12] M. Fischler, and R. Bolles, “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartographyâ€, Communications of the ACM, vol.24, no.6, (1981), pp.381-395.

[13] S. Guha, R. Rastogi, and K. Shim, “Cure: An Efficient Clustering Algorithm for Large Databasesâ€, In Proceedings of ACM SIGMOD International Conference on Management of Data, (1998), pp.73-84.

[14] A.N. Hirani, and T. Totsuka, “Combining Frequency and Spatial Domain Information for Fast Interactive Image Noise Removalâ€, ACM International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), (1996), pp.269-276.

[15] A.K. Jain, “Fundamentals of Digital Image Processingâ€, Prentice Hall Information and System Sciences Series, (1989).

[16] A.K. Jain, and R.C. Dubes, “Algorithms for Clustering Dataâ€, Prentice Hall, (1998).

[17] K. Kaewbuadee, Y. Temtanapat, and R. Peachavanish, “Data Cleaning Using FD From Data Mining Processâ€, IADIS International Journal on Computer Science and Information System, vol.1, (2006), pp.117-131.

[18] M. Kearns, and M. Li, “Learning in the Presence of Malicious Errorsâ€, Annual ACM Symposium on Theory of Computing, (1988), pp.267-280.

[19] L.J. Li, G. Wang, and F.F. Li, “OPTIMOL: Automatic Online Picture Collection via Incremental Model Learningâ€, IEEE International Conference on Computer Vision and Pattern Recognition, (2007), pp.1-8.

[20] D. Makris, and T. Ellis, “Learning Semantic Scene Models From Observing Activity in Visual Surveillanceâ€, IEEE Transactions on Systems, Man, and Cybernetics-Part B, vol.35, no.3, (2005), pp.397-408.

[21] A. Mojsilovic, and E. Soljanin, “Color Quantization and Processing by Fibonacci Latticesâ€, IEEE Transactions on Image Processing, vol.10, no.11, (2001), pp.1712-1725.

[22] A. Oliva, and A. Torralba, “Modeling the Shape of the Scene: A Holistic Representation of the Spatial Envelopeâ€, International Journal of Computer Vision, vol.42, no.3, (2001), pp.145-175.

[23] J. Sander, M. Ester, H.P. Kriegel, and X. Xu, “Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applicationsâ€, International Journal of Data Mining and Knowledge Discovery, vol.2, no.2, (1998), pp.169-194.

[24] G. Shakhnarovich, T. Darrell, and P. Indyk, “Nearest-Neighbor Methods in Learning and Vision: Theory and Practiceâ€, MIT Press, (2005).

[25] C.G.M. Snoek, M. Worring, D.C. Koelma, and A.W.M. Smeulders, “A Learned Lexicon-Driven Paradigm for Interactive Video Retrievalâ€, IEEE Transactions on Multimedia, vol.9, no. 2, (2007), pp.280-292.

[26] C.G.M. Snoek, B. Huurnink, L. Hollink, M. de Rijke, G. Schreiber, and M. Worring, “Adding Semantics to Detectors for Video Retrievalâ€, IEEE Transactions on Multimedia, vol.9, no.5, (2007), pp.975-986.

[27] D.L. Swets, and J. Weng, “Hierarchical Discriminant Analysis for Image Retrievalâ€, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.21, no.5, (1999), pp.386-401.

[28] A. Torralba, and A. Oliva, “Depth Estimation from Image Structureâ€, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.24, no. 9, (2002), pp.1226-1238.

[29] A. Torralba, and A. Oliva, “Statistics of Natural Image Categoriesâ€, Network: Computation in Neural Systems, vol.14, no.3, (2003), pp.391-412.

[30] A. Torralba, “Modeling Global Scene Factors in Attentionâ€, Journal of the Optical Society of America, vol.20, no.7, (2003), pp.1407-pp.1418.

[31] TRECVID, available online:

[32] C.J. Wu, H.C. Zeng, S.H. Huang, S.H. Lai, and W.H. Wang, “Learning-Based Interactive Video Retrieval Systemâ€, IEEE International Conference on Multimedia and Expo, (2006), pp.1785-1788.

[33] H. Xiong, P.N. Tan, and V. Kumar, “Mining Strong Affinity Association Patterns in Data Sets with Skewed Support Distributionâ€, IEEE International Conference on Data Mining, (2003), pp.387-394.

[34] H. Xiong, G. Pandey, M. Steinbach, and V. Kumar, “Enhancing Data Analysis with Noise Removalâ€, IEEE Transactions on Knowledge and Data Engineering, vol.18, no.3, (2006), pp.304-319.

[35] T. Zhang, R. Ramakrishnan, and M. Livny, “BIRCH: An Efficient Data Clustering Method for Very Large Databasesâ€, ACM SIGMOD International Conference on Management of Data, (1996), pp.103-114.

View Full Article: