A stochastic framework for optimal key frame extraction from MPEG video databases

A video content representation framework is proposed in this paper for extr acting limited, but meaningful, information of video data, directly from th e MPEG compressed domain. A hierarchical color and motion segmentation sche me is applied to each video shot, transforming the frame-based representati on to a feature-based one. The scheme is based on a multiresolution impleme ntation of the recursive shortest spanning tree (RSST) algorithm. Then, all segment features are gathered together using a fuzzy multidimensional hist ogram to reduce the possibility of classifying similar segments to differen t classes. Extraction of several key frames is performed for each shot in a content-based rate-sampling framework. Two approaches are examined for key frame extraction. The first is based on examination of the temporal variat ion of the feature vector trajectory; the second is based on minimization o f a cross-correlation criterion of the video frames. For efficient implemen tation of the latter approach, a logarithmic search (along with a stochasti c version) and a genetic algorithm are proposed. Experimental results are p resented which illustrate the performance of the proposed techniques, using synthetic and real life MPEG video sequences. (C) 1999 Academic Press.