Scheme for detecting shot boundaries in compressed video data using inter-frame/inter-field prediction coding and intra-frame/intra-field coding

• US 5,911,008 A
• Filed: 04/29/1997
• Issued: 06/08/1999
• Est. Priority Date: 04/30/1996
• Status: Expired due to Fees

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Shimizu, Atsushi, Satoh, Takashi, Hamada, Hiroshi, Akutsu, Akihito, Tonomura, Yoshinobu, Taniguchi, Yukinobu, Niikura, Yasuhiro
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/841,200
• Time in Patent Office: 770 Days
• Field of Search: 382/232, 382/236, 382/238, 382/240, 382/248, 382/250, 358/432, 358/433, 348/384, 348/394, 348/395, 348/400-404, 348/407-416, 348/420, 348/421, 348/425, 348/430, 348/431, 348/231, 348/390
• 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/577 Motion compensation with bidirectional frame interpolation, i.e. using B-pictures
• CPC Class Codes: H04N 5/147 Scene change detection

Abstract

A scheme for detecting shot boundaries in the compressed video data at high speed and high accuracy. In this shot boundary detection scheme, a Predictive-picture (P picture) change is calculated from a P picture sequence in the input video data which is compressed by an inter-frame/inter-field forward direction prediction coding scheme, according to coded data contained in the P picture sequence, while an Intra-picture (I picture) change is calculated from an I picture sequence in the input video data which is compressed by an intra-frame/intra-field coding scheme, according to coded data contained in the I picture sequence. Then, a shot boundary is detected by evaluating both the P picture change and the I picture change.

Claims

1. A method for detecting a shot boundary from an input video data compressed by a coding scheme using both an inter-frame/inter-field prediction coding scheme and an intra-frame/intra-field coding scheme, comprising the steps of:

(a) calculating a Predictive-picture (P picture) change from a P picture sequence in the input video data which is compressed by an inter-frame/inter-field forward direction prediction coding scheme, according to coded data contained in the P picture sequence;

(b) calculating an Intra-picture (I picture) change from an I picture sequence in the input video data which is compressed by an intra-frame/intra-field coding scheme, according to coded data contained in the I picture sequence; and

(c) detecting a shot boundary by evaluating both the P picture change calculated at the step (a) and the I picture change calculated at the step (b).

2. The method of claim 1, wherein the step (a) calculates the P picture change as a rate of a region at which an inter-frame/inter-field prediction was incorrect with respect to an entire field.

3. The method of claim 1, wherein the step (a) includes the steps of:

obtaining a region at which a change occurred between adjacent images of a respective picture sequence as a changed region; and

applying a prescribed spatial computation with respect to a time series of the changed region sequentially in time to obtain a respective picture change.

4. The method of claim 1, wherein the step (c) detects the shot boundary by judging that the shot boundary exists at a timing at which either the P picture change exceeds a first threshold or the I picture change exceeds a second threshold.

5. The method of claim 1, wherein the step (c) includes the step of:

switching a procedure for evaluating the P picture change and the I picture change, according to frequencies of appearances of the P picture sequence and the I picture sequence in the input video data.

6. The method of claim 1, wherein the step (c) includes the step of:

controlling values of a first threshold for evaluating the P picture change and a second threshold for evaluating the I picture change, according to frequencies of appearances of the P picture sequence and the I picture sequence in the input video data.

7. The method of claim 1, wherein the step (c) includes the step of:

correcting the P picture change by using an information obtained from the I picture sequence, in evaluating the P picture change.

8. The method of claim 1, wherein the step (c) includes the step of:

correcting the I picture change by using an information obtained from the P picture sequence, in evaluating the I picture change.

9. The method of claim 1, further comprising the steps of:

(d) estimating a section S in which the shot boundary may possibly be existing, according to coded data of intra-frame/intra-field coded frames constituting the I picture sequence;

wherein the step (c) detects the shot boundary according to feature values obtained from coded data of inter-frame/inter-field coded frames constituting the P picture sequence which are contained within the section S.

10. The method of claim 9, wherein the step (d) includes the steps of:

calculating a difference in corresponding blocks between each intra-frame/intra-field coded frame and an immediately previous intra-frame/intra-field coded frame in the I picture sequence;

counting a number of blocks for which the difference calculated by the calculating step is greater than a first prescribed threshold; and

estimating frames between said each intra-frame/intra-field coded frame and the immediately previous intra-frame/intra-field coded frame as a part of the section S when the number of blocks counted by the counting step is greater than a second prescribed threshold.

11. The method of claim 9, further comprising the steps of:

(e) estimating a section S'"'"' at which the shot boundary may possibly be existing within the section S, by comparing an amount of coded data in each inter-frame/inter-field coded frame contained in the section S with at least one of an amount of coded data in an immediately previous inter-frame/inter-field coded frame of said each inter-frame/inter-field coded frame and an amount of coded data in an immediately following inter-frame/inter-field coded frame of said each inter-frame/inter-field coded frame;

wherein the step (c) detects the shot boundary according to feature values obtained from coded data of the inter-frame/inter-field coded frames contained within the section S'"'"'.

12. The method of claim 11, wherein the step (e) includes the steps of:

calculating a difference of the amount of coded data in said each inter-frame/inter-field coded frame with respect to a larger one of the amount of coded data in the immediately previous inter-frame/inter-field coded frame and the amount of coded data in the immediately following inter-frame/inter-field coded frame; and

estimating said each inter-frame/inter-field coded frame as a part of the section S'"'"' when the difference calculated by the calculating step is greater than a prescribed threshold.

13. The method of claim 11, wherein the step (c) includes the steps of:

decoding variable length codes of said each inter-frame/inter-field coded frame and counting a number of intra-frame/intra-field coded blocks in said each inter-frame/inter-field coded frame; and

judging that the shot boundary exists in said each inter-frame/inter-field coded frame when the number of intra-frame/intra-field coded blocks counted by the decoding step is greater than another prescribed threshold.

14. The method of claim 11, wherein when the section S'"'"' contains an intra-frame/intra-field coded frame, the step (c) detects the shot boundary according to the feature values obtained by decoding said intra-frame/intra-field coded frame and an immediately previous inter-frame/inter-field coded frame of said intra-frame/intra-field coded frame.

15. The method of claim 14, wherein the step (c) includes the steps of:

calculating a difference between said intra-frame/intra-field coded frame and the immediately previous inter-frame/inter-field coded frame;

counting a number of blocks/pixels for which the difference calculated by the calculating step is greater than a first prescribed threshold; and

judging that the shot boundary exists between said intra-frame/intra-field coded frame and the immediately previous inter-frame/inter-field coded frame when the number of blocks/pixels counted by the counting step is greater than a second prescribed threshold.

16. The method of claim 1, wherein the input video data is coded interlaced video data in which each frame has an odd field and an even field and the P picture sequence is compressed by an inter-field prediction coding scheme, and the step (a) includes the steps of:

calculating inter-field similarities of each field of each frame according to a reference field selection information indicating a reference field to be used for a motion compensation at a time of decoding as either the odd field or the even field; and

applying a prescribed computation to the inter-field similarities calculated from a plurality of fields, and setting a computation result as the P picture change; and

wherein the step (c) judges that the shot boundary exists when the P picture change is greater than a prescribed threshold.

17. The method of claim 16, wherein the calculating step calculates the inter-field similarities by applying another prescribed computation to difference data contained in blocks constituting each frame, and accumulating computation results of said another prescribed computation for each reference field separately.

18. The method of claim 16, wherein the applying step applies the prescribed computation which has a large computation result value when a first condition that the inter-field similarity between a field of interest and a past field is small and a second condition that the inter-field similarity between a field of interest and a future field is large are both satisfied.

19. The method of claim 16, wherein when the odd (or the even) field is older in time than the even (or the odd) field, the applying step applies the prescribed computation which has a large computation result value when a first condition that the inter-field similarity between one odd (or even) field of one frame and a past field is large but the inter-field similarity between said one odd (or even) field and a future field is small and a second condition that the inter-field similarity between one even (or odd) field of said one frame and a future field is large but the inter-field similarity between said one even (or odd) field and a past field is small are both satisfied.

20. The method of claim 16, further comprising the steps of:

applying a further prescribed computation which has a large computation result value when both of the inter-field similarity between a field of interest and a past field and the inter-field similarity between a field of interest and a future field have small values; and

judging that a temporal image change exists when a computation result of the further prescribed computation is greater than a prescribed threshold.

21. The method of claim 1, wherein the step (a) includes the steps of:

calculating a changing tendency of each frame from the P picture sequence, according to coded data contained in the P picture sequence; and

extracting a region at which the changing tendency calculated by the calculating step is uniform over a plurality of consecutive frames, as a gradually changing region; and

wherein the step (c) detects the shot boundary as a dissolve when a rate of the gradually changing region with respect to an entire field is greater than a prescribed threshold.

22. The method of claim 21, wherein the calculating step calculates the changing tendency according to a sign of difference data in a region at which a motion compensation prediction was correct among the coded data contained in the P picture sequence.

23. The method of claim 22, wherein the calculating step changes the sign of the difference data depending on whether the motion compensation prediction was made from a past direction or a future direction, in calculating the changing tendency.

24. The method of claim 21, wherein the calculating step calculates the changing tendency according to a value of difference data in a region at which a motion compensation prediction was correct among the coded data contained in the P picture sequence.

25. The method of claim 1, wherein the step (a) includes the steps of:

applying a spatial computation for contracting a region at which a motion compensation prediction was incorrect from a boundary with respect to a region at which the motion compensation prediction was correct, as much as a width corresponding to a range to which an influence of the motion compensation prediction reaches, according to the P picture sequence, so as to obtain a contracted region for each frame; and

calculating the P picture change according to the contracted region obtained by the applying step.

26. The method of claim 25, wherein the step (a) further includes the step of:

estimating the range to which an influence of the motion compensation prediction reaches, according to values of motion vectors recorded in difference data obtained by analyzing the P picture sequence.

27. The method of claim 25, wherein the calculating step calculates the P picture change by comparing a type of each block contained in the contracted region for each frame with types of corresponding blocks contained in adjacent frames of said each frame, and using only those blocks contained in the contracted region whose type is different from types of corresponding blocks contained in adjacent frames of said each frame.

28. The method of claim 27, wherein the calculating step includes the steps of:

counting a number of valid blocks in the contracted region for each frame, a valid block being an i block for which the motion compensation prediction was incorrect and corresponding blocks in the adjacent frames are p blocks for which the motion compensation prediction was correct; and

obtaining the P picture change as a rate of the number of valid blocks with respect to a total number of blocks in said each frame.

29. The method of claim 25, wherein the calculating step calculates the P picture change by comparing a number of i blocks in the contracted region for each frame with at least one of a number of i blocks in an immediately previous frame of said each frame and a number of i blocks in an immediately following frame of said each frame, the i block being a block for which the motion compensation prediction was incorrect.

30. The method of claim 29, wherein the calculating step further includes the steps of:

calculating a difference of the number of i blocks for said each frame with respect to a larger one of the number of i blocks for the immediately previous frame and the number i blocks for the immediately following frame; and

obtaining the P picture change as a rate of the difference with respect to a total number of blocks in said each frame.

31. The method of claim 1, wherein the step (c) checks whether the shot boundary exists between an I picture and a P picture by the steps of:

determining a largely changed region in the P picture sequence;

correcting the I picture change calculated at the step (b) by removing I picture change values obtained from the largely changed region determined by the determining step; and

evaluating the I picture change as corrected by the correcting step.

32. An apparatus for detecting a shot boundary from an input video data compressed by a coding scheme using both an inter-frame/inter-field prediction coding scheme and an intra-frame/intra-field coding scheme, comprising:

a picture judgement unit for judging types of coding schemes used in the input video data and separating a Predictive-picture (P picture) sequence in the input video data which is compressed by an inter-frame/inter-field forward direction prediction coding scheme and an Intra-picture (I picture) sequence in the input video data which is compressed by an intra-frame/intra-field coding scheme;

a P picture change calculation unit for calculating a P picture change from the P picture sequence, according to coded data contained in the P picture sequence;

an I picture change calculation unit for calculating an I picture change from the I picture sequence, according to coded data contained in the I picture sequence; and

a shot boundary detection unit for detecting a shot boundary by evaluating both the P picture change calculated by the P picture change calculation unit and the I picture change calculated by the I picture change calculation unit.

33. The apparatus of claim 32, wherein the shot boundary detection unit estimates a section S in which the shot boundary may possibly be existing, according to coded data of intra-frame/intra-field coded frames constituting the I picture sequence, and detects the shot boundary according to feature values obtained from coded data of inter-frame/inter-field coded frames constituting the P picture sequence which are contained within the section S.

34. The apparatus of claim 32, wherein the input video data is coded interlaced video data in which each frame has an odd field and an even field and the P picture sequence is compressed by an inter-field prediction coding scheme, and the P picture change calculation unit includes:

an inter-field similarity calculation unit for calculating inter-field similarities of each field of each frame according to a reference field selection information indicating a reference field to be used for a motion compensation at a time of decoding as either the odd field or the even field; and

a computation unit for applying a prescribed computation to the inter-field similarities calculated from a plurality of fields, and setting a computation result as the P picture change; and

wherein the shot boundary detection unit judges that the shot boundary exists when the P picture change is greater than a prescribed threshold.

35. The apparatus of claim 32, wherein the P picture change calculation unit includes:

a changing tendency calculation unit for calculating a changing tendency of each frame from the P picture sequence, according to coded data contained in the P picture sequence; and

a gradually changing region extraction unit for extracting a region at which the changing tendency calculated by the changing tendency calculation unit is uniform over a plurality of consecutive frames, as a gradually changing region; and

wherein the shot boundary detection unit detects the shot boundary as a dissolve when a rate of the gradually changing region with respect to an entire field is greater than a prescribed threshold.

36. The apparatus of claim 32, wherein the P picture change calculation unit includes:

a spatial computation unit for applying a spatial computation for contracting a region at which a motion compensation prediction was incorrect from a boundary with respect to a region at which the motion compensation prediction was correct, as much as a width corresponding to a range to which an influence of the motion compensation prediction reaches, according to the P picture sequence, so as to obtain a contracted region for each frame; and

a calculation unit for calculating the P picture change according to the contracted region obtained by the spatial computation unit.

37. An article of manufacture, comprising:

a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for detecting a shot boundary from an input video data compressed by a coding scheme using both an inter-frame/inter-field prediction coding scheme and an intra-frame/intra-field coding scheme, the computer readable program means including;

first computer readable program code means for causing the computer to function as a picture judgement unit for judging types of coding schemes used in the input video data and separating a Predictive-picture (P picture) sequence in the input video data which is compressed by an inter-frame/inter-field forward direction prediction coding scheme and an Intra-picture (I picture) sequence in the input video data which is compressed by an intra-frame/intra-field coding scheme;

second computer readable program code means for causing the computer to function as a P picture change calculation unit for calculating a P picture change from the P picture sequence, according to coded data contained in the P picture sequence;

third computer readable program code means for causing the computer to function as an I picture change calculation unit for calculating an I picture change from the I picture sequence, according to coded data contained in the I picture sequence; and

fourth computer readable program code means for causing the computer to function as a shot boundary detection unit for detecting a shot boundary by evaluating both the P picture change calculated by the second computer readable program code means and the I picture change calculated by the third computer readable program code means.

38. The article of manufacture of claim 37, wherein the fourth computer readable program code means estimates a section S in which the shot boundary may possibly be existing, according to coded data of intra-frame/intra-field coded frames constituting the I picture sequence, and detects the shot boundary according to feature values obtained from coded data of inter-frame/inter-field coded frames constituting the P picture sequence which are contained within the section S.

39. The article of manufacture of claim 37, wherein the input video data is coded interlaced video data in which each frame has an odd field and an even field, and the second computer readable program code means includes:

fifth computer readable program code means for causing the computer to function as an inter-field similarity calculation unit for calculating inter-field similarities of each field of each frame according to a reference field selection information indicating a reference field to be used for a motion compensation at a time of decoding as either the odd field or the even field; and

sixth computer readable program code means for causing the computer to function as a computation unit for applying a prescribed computation to the inter-field similarities calculated from a plurality of fields, and setting a computation result as the P picture change; and

wherein the fourth computer readable program code means judges that the shot boundary exists when the P picture change is greater than a prescribed threshold.

40. The article of manufacture of claim 37, wherein the second computer readable program code means includes:

seventh computer readable program code means for causing the computer to function as a changing tendency calculation unit for calculating a changing tendency of each frame from the P picture sequence, according to coded data contained in the P picture sequence; and

eighth computer readable program code means for causing the computer to function as a gradually changing region extraction unit for extracting a region at which the changing tendency calculated by the changing tendency calculation unit is uniform over a plurality of consecutive frames, as a gradually changing region; and

wherein the fourth computer readable program code means detects the shot boundary as a dissolve when a rate of the gradually changing region with respect to an entire field is greater than a prescribed threshold.

41. The article of manufacture of claim 37, wherein the second computer readable program code means includes:

ninth computer readable program code means for causing the computer to function as a spatial computation unit for applying a spatial computation for contracting a region at which a motion compensation prediction was incorrect from a boundary with respect to a region at which the motion compensation prediction was correct, as much as a width corresponding to a range to which an influence of the motion compensation prediction reaches, according to the P picture sequence, so as to obtain a contracted region for each frame; and

tenth computer readable program code means for causing the computer to function as a calculation unit for calculating the P picture change according to the contracted region obtained by the ninth computer readable program code means.