The present application is directed to new methods for automatically and effectively combining multiple metrics to select interesting, or key, frames from a video sequence. In one aspect, the methods include selecting a reference frame from a video sequence and iteratively computing the improvement or gain in the combined metrics for candidate frames with respect to that reference frame. In another aspect, a master list of reference key frames is determined, quality metrics are calculated for each of a plurality of candidate frames associated with each reference key frame, and each reference key frame in the master list is replaced with a candidate frame that yields the greatest aggregate quality improvement over that reference key frame.