Keyframe Extraction Method Based on Dominating Set

Keyframe extraction is one of the important steps in video processing, and it is popularly used in video content analysis. A keyframe extraction method is proposed in this paper for the content-based video summarization. In order to well depict the structure and relation among the frames of a video, we firstly model the video as an undirected weighted graph, where the frames of the video are taken as vertices, and the lines among vertices are taken as edges. The weights of edges are computed using the Hausdorff distances between pairs of speed-up features frame-by-frame which are local and robust features of frames. Subsequently, based on the representation of the keyframe, the process of keyframe extraction is equivalent to the selection of minimum dominating set in a graph, and integral linear programming is used to select the minimum dominating set in the graph. Finally, the keyframes are extracted according to the vertices in the obtained dominating set. We execute the proposed method on different types of videos, and evaluate the performance of the fidelity and compression ratios. Compared with the traditional methods, the proposed method is depended on video content rather than time and video shots. The experimental results show that the keyframes extracted by the proposed method have good representation and discrimination, and they also have high fidelity and compression ratios.