Automatic scene decomposition and optimization of MPEG compressed video

• US 5,774,593 A
• Filed: 02/26/1997
• Issued: 06/30/1998
• Est. Priority Date: 07/24/1995
• Status: Expired due to Term

• Current Assignee: Washington University In St Louis
• Original Assignee: University of Washington
• Inventors: Liu, Hain-Ching H., Zick, Gregory L.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Tadayon, Bijan
• Application Number:
  US08/806,395
• Time in Patent Office: 489 Days
• Field of Search: 348/403, 348/395, 348/420, 348/700, 348/701, 348/699, 348/169, 348/170, 348/171, 348/172, 348/416, 348/412, 348/413, 348/421, 358/433, 358/432, 358/431, 358/430, 358/429, 358/428, 358/426, 358/427, 358/261.3, 358/261.2, 358/261.1, 358/262.1, 382/232, 382/233, 382/235, 382/236, 382/237, 382/238, 382/239, 382/244, 382/248, 382/250, 382/251, 382/252, 382/253, 382/107, 382/166, 382/171, 382/172, 382/240, 382/270, 382/278
• US Class Current: 382/236
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: H04N 19/114 Adapting the group of pictures [GOP] structure, e.g. number of B-frames between two anchor frames H04N19/107 takes precedence
• CPC Class Codes: H04N 19/142 Detection of scene cut or scene change
• CPC Class Codes: H04N 19/177 the unit being a group of pictures [GOP]
• CPC Class Codes: H04N 19/179 the unit being a scene or a shot
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/87 involving scene cut or scene change detection in combination with video compression

Abstract

Analysis of video data in an MPEG compressed format to identify scene changes to facilitate indexing to access specific video frames and to improve data compression and/or quality of the compressed video. MPEG compressed video data include I-pictures, P-pictures, and B-pictures. Scene changes are identified by analyzing P-pictures using average error power, based upon direct cosine transform components in the compressed data, and/or using an interframe correlation between a P-picture and its past reference frame. When a scene change occurs, average error power becomes large and interframe correlation between frames becomes substantially zero. Alternatively (or in addition), B-pictures in a video slot can be analyzed, in terms of interframe correlation between past and future reference frames, using either an AND analysis technique or an OR analysis technique. The AND analysis identifies a scene change when two or more B-pictures between two reference frames defining the video slot all imply a scene change, while the OR analysis indicates that a scene change has not occurred in the video slot if one B-picture implies that a scene change has not occurred. Once the scene changes have been identified, all I-pictures not occurring at a scene change are converted to P-pictures, and all P-pictures immediately following a scene change are converted to I-pictures. This step improves compression and/or quality of the compressed video, since P-pictures require less data than do I-pictures, and fewer I-pictures will be used in the compressed data following this step.

Claims

1. A method for detecting a scene change in compressed video data that represent a plurality of successive video frames, comprising the steps of:

(a) determining an interframe correlation between successive video frames of the compressed video data;

(b) determining a measure indicative of a scene change between two successive video frames as a function of the interframe correlation between the two successive video frames; and

(c) comparing the measure to a threshold value, and as a function of a difference between the measure and the threshold value, indicating whether the scene change has occurred between the two successive video frames.

2. The method of claim 1, further comprising the step of determining an error power between the successive video frames to serve as an additional measure indicative of a scene change.

3. The method of claim 2, wherein the step of determining the error power between successive video frames comprises the steps of:

(a) dividing each of the successive video frames into a plurality of macroblocks, each macroblock including a defined number of contiguous pixels, said plurality of macroblocks including a plurality of forward-predicted macroblocks;

(b) for each forward-predicted macroblock comprising the successive video frames;

(i) applying a discrete cosine transform to at least a portion of the forward-predicted macroblock to determine a plurality of spectral components; and

(ii) determining a sum of the spectral components of the forward-predicted macroblock squared, said sum being equal to a total error power of the forward-predicted macroblock; and

(c) determining an average total error power for each of the successive video frames by summing the total error power for the forward-predicted macroblocks in each video frame to produce a video frame error power and dividing the video frame error power by the number of forward-predicted macroblocks for which the total error power was summed, so that there is an indication that a scene cut occurred between an immediately previous video frame and a current video frame if said average total error power for the current frame exceeds the threshold.

4. The method of claim 1, wherein the compressed video data represent the successive video frames using intra-pictures (I-pictures), predicted-pictures (P-pictures), and bidirectional-predicted pictures (B-pictures), each of said I-pictures being independent of any other type of pictures, each of said P-pictures being related to a previous I-picture or a previous P-picture, and each of said B-pictures being related to the previous I-picture or P-picture and to a next I-picture or a next P-picture, wherein the step of determining the interframe correlation between successive video frames comprises the steps of:

(a) dividing each of the I-pictures, P-pictures, and B-pictures into a number N(T) of macroblocks, each macroblock including a defined number of contiguous pixels, each of said P-pictures including a number N(F) of forward-predicted macroblocks, and each of said B-pictures including in addition, a number N(B) of backward-predicted macroblocks and a number N(A) of bidirectional-predicted macroblocks;

(b) for each P-picture, determining the interframe correlation between the P-picture and a past reference picture, said interframe correlation being equal to N(F)/N(T); and

(c) for each B-picture, determining an indicator of scene changes between the B-picture and one of a past reference picture and a future reference picture for the B-picture as a function of the interframe correlation between the past reference picture and the future reference picture of the B-picture.

5. The method of claim 4, wherein said indicator comprises a function of a difference D, which is equal to N(F)-N(B) for the B-picture.

6. The method of claim 5, wherein the difference D is weighted, producing a weighted difference W(D), which is equal to D/N(A) for the B-picture.

7. The method of claim 4, wherein the interframe correlation between each B-picture and its past reference picture, C(P), is a function of N(F), N(A), and N(T);

and wherein the interframe correlation between each B-picture and its future reference picture, C(F), is a function of N(B), N(A), and N(T).

8. The method of claim 7, wherein a measure of continuity for the B-picture is equal to a minimum of C(P) and C(F) for the B-picture.

9. The method of claim 8, wherein the indicator of the scene change between the B-picture and one of its past and future reference pictures is an inverse of the measure of continuity for the B-picture.

10. The method of claim 4, wherein the interframe correlation for the B-picture is determined as a function of motion vectors between contiguous macroblocks in the B-picture.

11. The method of claim 1, further comprising the step of adaptively determining the threshold as a time varying function of the measure.

12. The method of claim 11, wherein the step of adaptively determining the threshold comprises the steps of:

(a) filtering the measure over time to remove peaks in the measure, producing a time varying filtered signal; and

(b) determining the threshold as a function of the time varying filtered signal.

13. The method of claim 11, wherein the compressed video data are motion compensated before being processed to detect the scene change.

14. The method of claim 13, wherein the threshold is a function of at least a current measure, a past measure, and a future measure relative to a current video frame.

15. The method of claim 11, wherein the compressed video data are processed to detect the scene change before a compression process is completed.

16. The method of claim 15, wherein the threshold is a function of a current measure and a plurality of past measures.

17. The method of claim 1, further comprising the step of generating a list of scene changes, each scene change being identified by reference to a video frame number.

18. A system for detecting scene changes in compressed video data representing a plurality of successive video frames, comprising:

(a) a processor that executes machine instructions embodied in software, to carry out processing of the video data so as to implement functions that are determined by the machine instructions;

(b) a volatile memory that is accessible by the processor, for temporarily storing the machine instructions executed by the processor and for temporarily storing the video data;

(c) a nonvolatile storage device for storing the machine instructions executed by the processor and for storing the compressed video data and output data that include a list of the scene changes detected in the compressed video data; and

(d) said machine instructions causing the processor to implement the following functions;

(i) determine an interframe correlation between successive video frames;

(ii) determine a measure indicative of a scene change between two successive video frames as a function of the interframe correlation between the two successive video frames;

(iii) compare the measure to a threshold value, and as a function of a difference between the measure and the threshold value, indicate whether the scene change has occurred between the two successive video frames; and

(iv) add the scene change to the list of scene changes for the compressed video data.

19. An article of manufacture that is adapted for use by a computer to detect a scene change in compressed video data representing a plurality of successive video frames, comprising:

a nonvolatile memory device in which are stored a plurality of machine instructions that are executable by the computer, said plurality of machine instructions comprising a computer program that causes the computer to implement the following functions;

(a) determine an interframe correlation between successive video frames of the compressed video data;

(b) determine a measure indicative of a scene change between two successive video frames as a function of the interframe correlation between the two successive video frames; and

(c) compare the measure to a threshold value, and as a function of a difference between the measure and the threshold value, indicate whether the scene change has occurred between the two successive video frames.

20. A method for increasing at least one of a compression and a quality of compressed video data that represent successive video frames, said compressed video data including intra-pictures (I-pictures), predicted-pictures (P-pictures), and bidirectional-predicted pictures (B-pictures), said I-pictures each being independent of any other type of picture, said P-pictures each being related to a previous I-picture or a previous P-picture, and said B-pictures each being related to the previous I-picture or the previous P-picture and to a next I-picture or a next P-picture, said method comprising the steps of:

(a) identifying scene changes between successive video frames of the compressed video;

(b) ensuring that I-pictures always immediately follow a scene change and do not occur at any other points in the compressed video data; and

(c) ensuring that P-pictures do not immediately follow a scene change.

21. The method of claim 20, wherein the compressed video data are produced in a contemporaneous process, just before steps (a) through (c).

22. The method of claim 21, wherein the step of identifying scene changes between successive video frames comprises the step of using spatial matching between successive video frames of a video slot to determine the video frame within the video slot at which a scene change occurs.

23. The method of claim 22, wherein the step of using spatial matching comprises the steps of:

(a) determining color histograms for each video frame comprising a video slot, each color histogram comprising a plurality of color bins that indicate a frequency for a use of each of a plurality of colors in the video frame;

(b) determining differences between corresponding bins of the color histograms for successive video frames within the video slot; and

(c) identifying a scene change where the differences between the corresponding bins of the color histograms for two successive video frames is a maximum.

24. The method of claim 20, wherein the compressed video data are produced in a separate process that is generally not contemporaneous with steps (a) through (c), which are subsequently executed.

25. The method of claim 24, wherein the step of ensuring that I-pictures always immediately follow a scene change comprises the step of changing any I-picture that does not immediately follow a scene change to a P-picture, and wherein the step of ensuring that P-pictures do not immediately follow a scene change comprises the step of changing any P-picture that immediately follows a scene change to an I-picture.

26. The method of claim 20, further comprising the step of identifying video slots, each video slot including a plurality of video frames, each video slot beginning and ending with a reference frame, each reference frame comprising one of an I-picture and a P-picture.

27. The method of claim 26, wherein all video frames occurring between reference frames at the beginning and the end of a video slot are encoded in the compressed video data as B-pictures.

28. A system for increasing at least one of a compression and a quality of compressed video data that represent successive video frames, said compressed video data including intra-pictures (I-pictures) and predicted-pictures (P-pictures), said I-pictures each being independent of any other type of picture, and said P-pictures each being related to a previous I-picture or a previous P-picture, said system comprising:

(a) a processor that executes machine instructions embodied in software, to carry out processing of the video data so as to implement functions that are determined by the machine instructions;

(b) a volatile memory that is accessible by the processor, for temporarily storing the machine instructions executed by the processor and for temporarily storing the compressed video data;

(c) a nonvolatile storage device for storing the machine instruction executed by the processor and for storing the compressed video data; and

(d) said machine instructions causing the processor to implement the following functions;

(i) identify scene changes between successive video frames;

(ii) ensure that the I-pictures always immediately follow a scene change and do not occur at any other points in the compressed video data; and

(iii) ensure that the P-pictures do not immediately follow a scene change.

29. An article of manufacture that is adapted for use by a computer to detect a scene change in compressed video data representing a plurality of successive video frames, said compressed video data including intra-pictures (I-pictures) and predicted-pictures (P-pictures), said I-pictures each being independent of any other type of picture and said P-pictures each being related to a previous I-picture or a previous P-picture, said article of manufacture comprising:

a nonvolatile memory device in which are stored a plurality of machine instructions that are executable by the computer, said plurality of machine instructions comprising a computer program that cause the computer to implement the following functions;

(a) identify scene changes between successive video frames;

(b) ensure that the I-pictures always immediately follow a scene change and do not occur at any other points in the compressed video data; and

(c) ensure that the P-pictures do not immediately follow a scene change.