DC programming for solving a sparse modeling problem of video key frame extraction

Extracting key frames from a video can reduce redundancies in continuous scenes and pithy represent the entire video. This technique copes with the issue of how to efficiently manage a large amount of video data and has many applications such as video indexing, querying, and browsing. Current key frame extraction methods often utilize sparse modeling, which assumes that each video frame can be expressed as a linear combination of a few representative key frames. Although these methods are successful, they are less aware of the fact that videos have spatio-temporal structure and used ℓ1 norm based sparsity measure. In this paper, we propose a key frame extraction method that considers spatio-temporal information of videos. We employ a sparsity measure that is based on the determinant of the Gram matrix computed from entire video frames. The determinant sparsity measure is computed for the entire matrix, not for single frames, and thus it reflects the spatial or joint sparseness of the entire video. With this measure, the solutions are sparser than conventional sparseness measures but the cost function is non-convex and optimization becomes harder. Then, utilizing the fact that the proposed cost function is the difference of two convex functions, we employ an efficient algorithm based on the difference-of-convex (DC) programming, which often finds the global solution of the non-convex cost function. Experiments show that the proposed algorithm generates high-quality, high-compression key frames, compared with the existing key frame extraction method with the ℓ1 norm. The determinant sparsity measure was recently proposed and can be utilized for more video processing applications such as video saliency detection.