Real-Time, Adaptive, and Locality-Based Graph Partitioning Method for Video Scene Clustering

We propose in this paper an efficient, adaptive, and locality-based graph partitioning method for video scene clustering. First, a graph partitioning method is proposed to group video shots into scenes, and a peer-group filtering (PGF) scheme is used to identify all the shots similar to each particular shot based on Fisher's discriminant analysis. To work with computable shot similarity measures that have only limited discriminating power, we develop a graph partitioning scheme to cluster the shots by maximizing the likeness of shots within the same cluster and minimizing that between different clusters. Second, considering that video data are normally obtained and viewed sequentially, we propose to perform a locality-based PGF and graph partitioning on video segments with 50 shots, 100 shots, and so on. This proposed locality-based method has the advantage that the number of scene clusters is not required to be known a priori, and it can achieve performance comparable to that processing on the whole video sequence. Experimental results are presented to demonstrate the effectiveness and efficiency of the proposed method.

I. Introduction

After SHOT boundary detection, a common next step in content-based video analysis is to group the shots into different scene clusters, each comprising shots with similar contents. One or a few shots can then be selected from each scene cluster to form a compact representation of the video content for such purpose as video indexing, browsing, and understanding [1].