Method of selecting key-frames from a video sequence

• US 7,184,100 B1
• Filed: 03/24/1999
• Issued: 02/27/2007
• Est. Priority Date: 03/24/1999
• Status: Expired due to Fees

• Current Assignee: Anxin Mate Holding Ltd. (Anxin-China Holdings Ltd.)
• Original Assignee: Mate-Media Access Technologies Limited
• Inventors: Menadeva, Ovadya, Wilf, Itzhak, Greenspan, Hayit
• Primary Examiner(s): Natnael; Paulos M.
• Application Number:
  US09/647,199
• Time in Patent Office: 2,897 Days
• Field of Search: 348/722, 348/107, 348/171, 348/173, 348/225
• US Class Current: 348/700
• CPC Class Codes: G06V 40/167 using comparisons between temporally consecutive images
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence
• CPC Class Codes: H04N 5/9205 the additional signal being at least another television signal

Abstract

A method of selecting key-frames (230) from a video sequence (210, 215) by comparing each frame in the video sequence with respect to its preceding and subsequent key-frames for redundancy where the comparison involves region and motion analysis. The video sequence is optionally pre-processed to detect graphic overlay. The key-frame set is optionally post-processed (250) to optimize the resulting set for face or other object recognition.

Claims

1. A method of selecting key-frames from a video sequence to produce a subset of key-frames for indexing, archiving, browsing and/or searching purposes, comprising the following steps:

(a) producing an initial set of frames from said video sequence;

(b) introducing each frame of said initial set sequentially into a 3-frame buffer to include a middle frame M, its preceding frame L, and its succeeding frame R;

(c) testing for redundancy each M frame with respect to its preceding L frame and its succeeding R frame; and

(d) selecting as a key-frame for inclusion in the subset those M frames tested to be non-redundant.

2. The method according to claim 1, wherein each M frame is tested for redundancy, with respect to its preceding L frame and its succeeding R frame, by:

representing the M frame as a combination of geometric transformations applied to selected regions in the L and R frames;

subtracting the geometric transformation of the L and R frames from the M frame to produce difference images; and

determining from the difference images whether or note the M frame is redundant.

3. The method according to claim 1, wherein each M frame is tested for redundancy, with respect to its preceding L frame and its succeeding R frame, by:

iteratively identifying motion entities having relative motion between the M frame, its preceding L frame, and its succeeding R frame;

utilizing the identified motion entities for identifying regions in the M frame that can be transformed from the L and R frames into the M frame;

transforming said identified regions in the M frame to the corresponding regions in the L and R frames;

measuring the difference between said identified regions and said corresponding transformed regions in the M frame to produce difference images;

measuring the areas of said difference images by counting the number of pixels of an intensity value above a predetermined threshold; and

discarding the M frame when said measured areas are less than a prespecified area threshold.

4. The method according to claim 1, wherein:

some of the frames in the initial set include overlayed frames having graphic overlays superimposed on live video content, and non-overlayed frames having only live video content;

before step (c), a mask is produced of the graphic overlay in each overlayed frame and is utilized to remove the graphic overlay from the live video content in the respective overlayed frame;

step (c) tests for redundancy the live video content in both the overlayed frames and the non-overlayed frames; and

step (d) discards those M frames tested to be redundant in both the overlayed frames and the non-overlayed frames, such that a subset of key-frames is produced based on live video content in the overlayed frames and the non-overiayed frames in the initial set.

5. The method according to claim 4, wherein at least one overlayed frame is selected as an overlay key-frame and is merged with the subset of key-frames produced based on live video content.

6. The method according to claim 1, wherein at least some of said frames in the initial set include frames containing an image of a predetermined object and wherein at least one such image frame is used for selecting a key-frame for inclusion in the subset.

7. The method according to claim 6, wherein said at least one image frame is used for selecting as a key-frame by:

detecting at least one such image in a frame in the initial set;

tracking said at least one image through the video sequence to produce a series of image frames;

computing at least one image-based metric for said image from said series of image frames; and

selecting a key-frame from said series of image frames based on said at least one image-based metric.

8. A method according to claim 7, wherein said at least one image-based metric includes an image self-similarity index and is used to select a plurality of interim key-frames.

9. The method according to claim 8, wherein an image quality index is applied to said interim key-frames to select a key-frame for inclusion in said subset.

10. The method according to claim 1, wherein said initial set of frames is the entire video sequence.

11. The method according to claim 1, wherein said initial set of frames is produced by selecting every nth frame from the video sequence where n is greater than 1.

12. The method according to claim 1, wherein said initial set of frames is produced by selecting frames from the video sequence based on a distance metric between frames.

13. A method of selecting key-frames from an initial set of frames to produce a subset of key-frames for indexing, archiving, browsing and/or searching purposes, comprising:

testing for redundancy each frame of the initial set with respect to at least its preceding frame by;

representing the tested frame as a combination of geometric transformations applied to selected regions in the preceding frame;

subtracting the geometric transformation of the preceding frame from the tested frame to produce difference images; and

determining from the difference images whether or not the tested frame is redundant, wherein said redundancy test is made by;

iteratively identifying motion entities having relative motion between the tested frame and its preceding frame;

utilizing the identified motion entities for identifying regions in the tested frame that can be transformed from the preceding frame into the tested frame;

transforming said identified regions in the tested frame to the corresponding regions in the preceding frame;

measuring the differences between said identified regions and said corresponding transformed regions in the tested frames to produce difference images;

measuring the areas of the difference images by counting the number of pixels of an intensity value above a predetermined threshold; and

discarding the tested frame when said measured areas are less than a prespecified area threshold.

14. The method according to claim 13, wherein each frame is tested for redundancy also with respect to its succeeding frame in the initial set of frames and is discarded if redundancy is found in either the succeeding frame or in the preceding frame.

15. A method of selecting key-frames from a video sequence, which includes overlayed frames having graphic overlays superimposed on live video content, and non-overlayed frames having only live video content, said method comprising:

masking out from said overlayed frames the superimposed graphic overlays;

testing for redundancy the live video content of neighboring overlayed frames and non-overlayed frames;

selecting as key-frames the overlayed frames and non-overlayed frames whose live video contents were tested to be non-redundant, selecting at least one overlayed frame as an overlay key-frame; and

merging each selected overlay key-frame with the key-frames selected on live video content.

16. A method of selecting key-frames from a video sequence for inclusion in a subset of key-frames, comprising:

detecting at least one predetermined image in the video sequence;

tracking said at least one image through the video sequence to produce a series of image frames;

computing at least one image-based metric for said image from said series of image frames; and

selecting a key-frame from said series of image frames based on said at least one image-based metric, wherein said at least one image-based metric includes an image self-similarity index and is used to select a plurality of interim key-frames.

17. The method according to claim 16, wherein an image-quality index is applied to said interim key-frames to select a key-frame for inclusion in said subset.

18. The method according to claim 16, wherein said predetermined image is a face, graphic or other object image.

19. A method of selecting key-frames from a video sequence, comprising:

selecting one subset of key-frames which represent at least one feature of the video sequence;

selecting at least one other subset of key-frames which represent at least one other feature of the video sequence; and

combining said at least two subsets of key-frames to produce a combined set of key-frames, wherein said combining of the at least two subsets of key-frame comprises merging said subsets of key-frames to produce said combined set of key-frames;

testing pairs of adjacent key-frames in said combined set of key-frames for redundancy; and

discarding one of the pair of adjacent key-frames where redundancy is found to be present in a tested pair.

20. A method as claimed in claim 19, where said combined set of key-frames includes a subset of key-frames selected on the basis of live video content.

21. The method as claimed in claim 20, where said combined set of key-frames includes a subset of key-frames selected on the basis of graphic overlays.

22. The method as claimed in claim 20, where said combined set of key-frames includes a subset of key-frames selected on the basis of face content.

23. The method according to claim 20, wherein the key-frame of a pair which is discarded when redundancy is found to be present is the key-frame of the pair found to have the lower quality index with respect to said live video content.

24. A method of processing a video sequence of frames including graphic overlayed frames having a graphic overlay super imposed on live-video content, comprising:

detecting regions of the graphic overlay in said sequence;

generating a mask image of said graphics overlay;

utilizing said mask image for separating said graphics overlay from at least one overlayed frame in the sequence for also generating thereby a live video content image in addition to said mask image; and

selecting at least one key frame from said video sequence based on analysis of said live video content.

25. The method according to claim 24, wherein said mask image is used for selecting a graphic overlay key-frame from said video sequence.

26. A method of selecting key-frames from a video sequence for inclusion in a subset, comprising:

detecting at least two frames in the video sequence having a predetermined face image;

applying an image-quality metric to said detected frames; and

selecting as a key-frame, for inclusion in said subset, the detected frame having the higher image-quality metric;

applying prior to said step of applying an image-quality metric an image-similarity metric to select a plurality of interim key-frames; and

applying the image-quality metric to said interim key-frames to select the key-frame to be included in said subset.