ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2015, Vol. 52 ›› Issue (12): 2879-2887.doi: 10.7544/issn1000-1239.2015.20140701

Previous Articles    

Keyframe Extraction Method Based on Dominating Set

Nie Xiushan1,2, Chai Yan’e1, Teng Cong3   

  1. 1(School of Computer Science and Technology, Shandong University of Finance and Economics, Jinan 250014); 2(Shandong Engineering & Technology Center of Financial Informatization, Jinan 250014); 3(School of Mathematic and Quantitative Economics, Shandong University of Finance and Economics, Jinan 250014)
  • Online:2015-12-01

Abstract: 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.

Key words: video summarization, keyframe extraction, graph modeling, dominating set, integral programming, speed-up robust feature

CLC Number: