System and method for automatically detecting shot boundary and key frame from a compressed video data

• US 6,393,054 B1
• Filed: 04/20/1998
• Issued: 05/21/2002
• Est. Priority Date: 04/20/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Altunbasak, Yucel, Zhang, HongJiang
• Primary Examiner(s): Kelley, Chris
• Assistant Examiner(s): An, Shawn S.
• Application Number:
  US09/062,868
• Time in Patent Office: 1,492 Days
• Field of Search: 395/140, 395/155, 345/328, 345/348, 345/349, 345/356, 345/440, 348/700, 348/722, 348/416, 348/701, 348/699, 382/173, 382/236, 382/305, 382/225, 375/240
• US Class Current: 375/240
• 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 19/142 Detection of scene cut or scene change
• CPC Class Codes: H04N 19/179 the unit being a scene or a shot
• CPC Class Codes: H04N 19/87 involving scene cut or scene change detection in combination with video compression
• CPC Class Codes: H04N 5/147 Scene change detection

Abstract

A system for detecting shot boundary in a compressed video data without decompression includes a difference detector that detects content difference between frames. When the difference detector determines that a first content difference between a current frame of the current group of frames and a previous frame of a first previous group of frames is greater than a first threshold, a sharp shot boundary detector detects a sharp shot boundary within the current group of frames. When the difference detector determines that the first content difference is not greater than the first threshold but a second content difference between the current frame and a previous frame of a second previous group of frames is greater than a second threshold, a gradual shot boundary detector detects a gradual shot boundary within the current group of frames. The gradual shot boundary detector includes a pan frame detector that detects pan boundaries, a zoom detector that detects zoom boundaries, and key frame detector that detects key frames. A threshold selection unit is coupled to the difference detector to select the thresholds in accordance with the content difference detected such that the sharp shot boundary detector, the gradual shot boundary detector, and the key frame function efficiently and effectively.

Claims

1. A system for detecting shot boundaries in a compressed video data, comprising:

(A) a difference detector that detects content differences between a current frame and previous frames of previous groups of frames;

(B) a sharp shot boundary detector to detect a sharp shot boundary between the current frame and a previous frame of a first previous group of frames when the difference detector determines that a first content difference between the current frame and the previous frame of the first previous group of frames is greater than a first threshold;

(C) a gradual shot boundary detector that detects a gradual shot boundary between the current frame and a previous frame of a second previous group of frames when the difference detector determines that (1) the first content difference is not greater than the first threshold and (2) a second content difference between the current frame and the previous frame of the second previous group of frames is greater than a second threshold; and

(D) a key frame extractor that extracts multiple key frames from a detected shot using an iterative algorithm, wherein the iterative algorithm allows the key frame extractor to extract the multiple key frames from the shot by

(a) selecting the multiple key frames within the shot at a constant interval;

(b) adjusting the location of the selected key frames based on their histograms and the histograms of their adjacent frames within the shot until the histogram of a key frame is substantially the same as that of its subsequent frames.

2. The system of claim 1, wherein the gradual shot boundary detector further comprises

(a) a pan detector that detects pan frames;

(b) a zoom detector that detects zoom frames;

(c) a key frame extractor that extracts a video frame as a key frame using compression information from the compressed video data.

3. The system of claim 2, wherein the pan detector uses macro block information in the compressed video to detect if the current frame is a pan frame.

4. The system of claim 3, wherein the pan detector detects if the current frame is a pan frame by determining if the macro block information at borders of the current frame is different from the macro block information within the frame, wherein the current frame is a pan frame if the macro block information at borders of the current frame is different from the macro block information within the frame according to a predetermined criteria.

5. The system of claim 4, wherein the pan detector determines the reliable motion vectors by

(I) selecting all the forward and backward motion vectors that have substantially the same magnitude and direction as the reliable motion vectors if the current frame is a B type frame;

(II) selecting the motion vector of a macro block as the reliable motion vector if high frequency components of discrete cosine transform are detected in the macro block and if the current frame is a P type frame.

6. The system of claim 2, wherein the pan detector further comprises a state machine that detects whether a pan exists by

(I) determining that the pan has started if there are a predetermined number of successive pan frames;

(II) determining that the pan has stopped if there are a predetermined number of successive non-pan frames.

7. The system of claim 2, wherein the pan detector further comprises a key frame selector that selects key frames from a pan based on pan direction and magnitude of the pan.

8. The system of claim 2, wherein the zoom detector uses macro block information in the compressed video to detect if the current frame is a zoom frame.

9. The system of claim 8, wherein the zoom detector detects if the current frame is a zoom frame by determining if the macro block information at borders of the current frame is different from the macro block information within the frame, wherein the current frame is a zoom frame if the macro block information at borders of the current frame is different from the macro block information within the frame.

10. The system of claim 2, wherein the zoom detector further comprises a state machine that detects whether a zoom exists by

(I) determining that the zoom has started if there are a predetermined number of successive zoom frames;

(II) determining that the zoom has stopped if there are a predetermined number of successive non-zoom frames.

11. The system of claim 2, wherein the zoom detector farther comprises a key frame selector that selects key frames from a zoom based.

12. The system of claim 1, further comprising a threshold selection unit coupled to the difference detector and the shot boundary detectors to select and adjust the thresholds in accordance with all prior first content differences detected by the difference detector.

13. A system for detecting shot boundary and key frame in a compressed video data, comprising:

(A) a difference detector that detects content difference between a current frame and a prior frame of a previous group of frames using a first and a second threshold, wherein the difference detector determines the content difference between the current frame and the prior frame by

(a1) calculating the histograms of the current and prior frames;

(a2) modifying the histograms of the current and prior frames;

(a3) offsetting a highest histogram component value in either of the histograms by values of neighboring histogram components;

(B) a boundary detection and key frame extraction module coupled to the difference detector to detect shot boundaries and extract key frames within the current group of frames using a third threshold in accordance with the content differences detected; and

(C) a threshold selection unit coupled to the difference detector and the module to generate the thresholds, wherein the threshold selection unit selects and adjusts the thresholds in accordance with the content differences detected by the difference detector.

14. The system of claim 13, wherein the threshold selection unit also adjusts the thresholds to control density of the key frames.

15. The system of claim 13, wherein the threshold selection unit also adjusts the thresholds in accordance with space constraint of a storage buffer that stores all key frames extracted from the compressed video data such that all the key frames can fit into the storage buffer.

16. The system of claim 13, wherein the threshold selection unit further comprises

(I) a statistics collector that collects all the content differences detected between all current groups of frames and their respective previous groups of frames to obtain mean and standard deviation of the content differences;

(II) a threshold calculator that computes the thresholds as function of mean and standard deviation and also as function of the space constraint of the storage buffer.