Clustering-based shot change detection and fast exhaustive search algorithms for effective video retrieval

Abstract

In many interactive multimedia systems, efficient retrieval of multimedia information in a digital form is becoming an important issue. Among all multimedia types (text, image, graphic, audio, and video), video is the most challenging one since all other media information can be combined into a single data-stream of video. Thanks to the lowered cost of digital storage media, increased transmission rates, and improved compression techniques, the use of digital videos has increased tremendously for the last few years. However, tools available for video retrieval still remain primitive. To solve this problem, efficient video analysis and summarization techniques are required. In this dissertation, we consider two key issues for effective video retrieval: video shot change detection and fast exhaustive image search. As the first issue, automatic shot change detection has been recognized as an important research topic for video classification because manual approaches have too slow processing speed and expensive cost to be accepted in practice. Therefore, we propose an automatic clustering-based algorithm for shot change detection in MPEG-compressed videos with a small number of user-defined parameters. For accurate detection of abrupt and gradual shot changes, the proper selection and extraction of features are important. We first propose a fast edge image extraction scheme in the DCT domain on the basis of AC prediction. Then, by using the features extracted from the edge images and DC images, a two-stage clustering-based algorithm is proposed for shot change detection. In the first stage, the algorithm detects abrupt shot changes by employing 2-means clustering on the 2-D feature space of histogram and pixel differences between two neighboring DC frames. In the next stage, it subsequently explores gradual shot changes between two adjacent abrupt shot changes by performing a 2-step clustering scheme, which uses multiple features such as an edge energy diagram and ...