Video storyboard design using Delaunay graphs

Design of video storyboards has emerged as a popular research area in the multimedia community. Different pattern clustering techniques are applied to extract the key frames from a video sequence to form a storyboard. In this paper, we propose an automatic method for the selection of key frames of a video sequence using Delaunay graphs. We prune certain edges from the Delaunay graph using an iterative strategy where overall reduction in the global standard deviation of edge lengths is maximized. Resulting connected components in the graph correspond to the separate clusters. The proposed algorithm also utilizes edge information in addition to the color histogram information to achieve semantic dependency between different video frames. Performance of our algorithm is evaluated using Fidelity, Shot Reconstruction Degree and Compression Ratio. Experiments on standard video datasets indicate the supremacy of the proposed method over a previous Delaunay clustering-based key frame extraction algorithm.