Method and apparatus for video data compression using temporally adaptive motion interpolation

• US 5,592,226 A
• Filed: 01/26/1994
• Issued: 01/07/1997
• Est. Priority Date: 01/26/1994
• Status: Expired due to Fees

• Current Assignee: The Trustees of Princeton University (Princeton University)
• Original Assignee: BTG USA, Inc.
• Inventors: Dickinson, Bradley W., Lee, Jungwoo
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): Le, Vu
• Application Number:
  US08/187,595
• Time in Patent Office: 1,077 Days
• Field of Search: 348/700, 348/699, 348/416, 348/412, 348/413, 348/398, 348/407, 348/403, 348/405, 348/415, 348/384, 348/390, 348/401, 348/409, 348/402
• US Class Current: 375/240.14
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• 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/124 Quantisation
• CPC Class Codes: H04N 19/142 Detection of scene cut or scene change
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• 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/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/527 Global motion vector estimation
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• CPC Class Codes: H04N 19/577 Motion compensation with bidirectional frame interpolation, i.e. using B-pictures
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/85 using pre-processing or post-processing specially adapted for video compression
• CPC Class Codes: H04N 19/87 involving scene cut or scene change detection in combination with video compression
• CPC Class Codes: H04N 19/88 : involving rearrangement of data among different coding units, e.g. shuffling, interleaving, scrambling or permutation of pixel data or permutation of transform coefficient data among different blocks

Abstract

In a system for compressing video data, temporally adaptive motion interpolation based upon temporal characteristics of human vision is used for establishing threshold levels relative to the degree of motion as a whole (global motion) between frames. The global motion between successive frames in a group of pictures (GOP) is measured to determine if the motion is less or greater than the established threshold levels for determining the designation of I, P, and B frames, spacing between I and P reference frames, and the number of bits used for each frame, and B frames therebetween.

Claims

1. A method for compressing video data comprising the steps of:

determining the degree of global motion between frames of video data, where global motion is the motion between frames as a whole;

assigning reference frames based upon the global motion;

adjusting the temporal spacing between reference frames relative to the degree of global motion measured between frames relative to temporal masking in human vision, thereby determining the group of pictures (GOP) structure;

establishing different threshold magnitudes or levels of motion between frames as representing different scene change types;

assigning different bit rates to individual frames based upon said pre-established threshold levels of motion between frames;

said threshold establishing step including the steps of designating a Type 1 scene change between a pair of successive frames as occurring whenever the measured motion therebetween exceeds a value defining a T₁ threshold representing a substantial scene or picture change; and

designating and defining pursuant to the value of measured motion defining a Type 1 scene change, the first occurring or prior frame of the pair as a P2 frame, and the second occurring or past frame as an I2 frame, each being of predetermined bit rates via said assigning step.

2. The method of claim 1, further including the step of:

assigning a bit rate for video coding each frame based upon the degree of global motion measured between frames.

3. The method of claim 2, further including the step of:

assigning reference frames as intra (I) and predictive (P) based upon the degree of global motion measured between frames.

4. The method of claim 3, further including the step of:

assigning bidirectional (B) interpolated frames between reference frames.

5. The method of claim 1, further including the steps of:

said threshold establishing step including a step of designating and defining a Type 0 scene change between frames occurring whenever the measured motion therebetween exceeds a value defined as a T₀ threshold, whereby the T₀ threshold represents substantial motion in a scene or picture; and

detecting when the cumulative motion from an immediately preceding reference frame and a successive frame exceeds a T₀ threshold, for designating and defining the immediately prior frame to said successive frame as a P1 frame of predetermined bit rate via said assigning step, said P1 frame being a reference frame.

6. The method of claim 1, wherein said assigning step further assigns bit rates to said frames by using forward temporal masking in human vision, whereby at a scene change an immediately following frame is coarsely coded.

7. The method of claim 1, wherein said assigning step further assigns bit rates to said frames in a manner utilizing a backward temporal masking effect in a resulting coding scheme, whereby in instances where a scene change involves relatively large motion between two successive frames, the immediately past frame at the scene change and the immediately following frame are coarsely coded via the assignment of a relatively low bit rate.

8. The method of claim 1, wherein said global motion determining step uses any one of five different distance measures for temporal segmentation including difference of histograms (DOH), histograms of difference (HOD), block histogram difference (BH), block variance difference (BV), and motion compensation error (MCE).

9. The method of claim 1, wherein said assigning step includes the step of designating individual frames as intra frames (I), and/or predicted frames (P) based upon the magnitude of motion between associated frames exceeding a given threshold level.

10. The method of claim 1, further including the steps of:

said threshold establishing step including a step of designating a Type 0 scene change between frames occurring whenever the measured motion therebetween exceeds a value defined as a T₀ threshold representing substantial motion in a scene or picture; and

detecting when the cumulative motion from an immediately preceding reference frame and a successive frame exceeds a T₀ threshold, for designating and defining the immediately prior frame to said successive frame as a P1 frame of predetermined bit rate via said assigning step, said P1 frame being a reference frame.

11. The method of claim 10, further including the steps of:

designating successive frames between reference frames as bidirectional B frames, respectively.

12. The method of claim 10, wherein the magnitude of said T₁ threshold is made about four times greater than the magnitude of said T₀ threshold, whereby the T₁ threshold represents a complete scene or picture change between a pair of successive frames.

13. The method of claim 10, further including the step of:

optimally spacing said P1 designated frames for substantially optimizing the frame spacing between I1, I2, P1, and P2 reference frames.

14. The method of claim 13, wherein said optimally spacing step includes the step of conducting a binary search between frames to find substantially equidistant positions for Type 0 threshold change P1 designated frames.

15. The method of claim 13, wherein said optimal spacing step includes the steps of:

minimizing the deviation from the mean of distances between frame positions initially designated P1 through Type 0 threshold detection, and paired frame positions designated I2 and P2, respectively, via Type 1 threshold detection; and

determining the structure for each GOP based upon the optimally spaced P1 frames.

16. The method of claim 15, wherein said optimal spacing step includes the steps of exhaustively searching each frame for determining motion vectors.

17. The method of claim 15, wherein said optimal spacing step includes the steps of using a backward telescopic search for determining motion vector information between frames.

18. The method of claim 10, further including the steps of:

establishing a predetermined number of successive frames as a group of pictures (GOP) thereby grouping said successive frames into a plurality of successive GOP'"'"'s; and

designating the first frame of each of said plurality of GOP'"'"'s as an I1 frame of predetermined bit rate via said assigning step.

19. The method of claim 18, further including the steps of:

designating and defining frames as B1 frames between I₁ and P₁ reference frames in each of said plurality of GOP'"'"'s where at least one Type 0 scene change has been detected, said B1 frames each having a predetermined bit rate via said assigning step; and

designating and defining frames as B2 frames between reference frames in each of said plurality of GOP'"'"'s where no Type 0 scene changes have been detected, said B2 frames each having a predetermined bit rate via said assigning step.

20. The method of claim 19, wherein said I1 and I2 frames are intra frames, said P1 and P2 frames, are predicted frames, and said B1 and B2 frames are bidirectionally interpolated frames.

21. The method of claim 19, further including the step of gradually increasing to a full bit rate the bit rate of frames following a scene change to render the degradation of frames following a scene change imperceptible.

22. The method of claim 19, further including the step of computing the bit allocations for B2 frames to follow the equation:

##EQU22## where N is the number of |P1| frames, M is the number of frames in each GOP, |B1| is the bit allocation for B1 frames, and |P1| is the bit allocation for P1 frames.

23. The method of claim 19, wherein said assigning step further includes the steps of:

assigning the relatively highest bit rate to I1 designated frames;

assigning the second highest bit rate to P1 designated frames;

assigning the third highest bit rate to B2 designated frames; and

assigning relatively lower bit rates to I2, P2, and B1 designated frames.

24. The method of claim 23, wherein said assigning step includes assigning bit rates of 200kB/sec. for I1 frames, 100kB/sec. for P1 frames, greater than 10kB/sec. for B2 frames, and 10kB/sec. for B1, I2, and P2 frames, respectively.

25. The method of claim 23, further including the step of:

allocating the same number of bits from GOP to GOP for I1, I2, P1, and P2 designated frames, respectively.

26. The method of claim 23, further including the steps of:

varying the bit allocations for each I1, I2, P1, P2, and B1 frame types from GOP to GOP; and

retaining the bit rate constant for each of said frame types.

27. The method of claim 26, further including in said bit allocation varying step the step of assigning target bit allocations for each GOP in accordance with the following formula:

##EQU23## where D_t is the target bit allocation for picture Type t, t being either I1, I2, P1, P2, or B1;

C_I1, C_P1, and C_B1, respectively;

N is the number of P1 frames, M is the GOP size or number of frames in a GOP;

R=2G where G=[C_I1 +NC_P1 +(M-N-1)C_B1 ]X; and

X is a common factor determined from R and G.

28. The method of claim 23, further including the step of:

varying the number of bits allocated for I1, I2, P1, P2, B1, and B2 designated frames, respectively, from GOP to GOP in accordance with the number of detected Type 0 scene changes; and

maintaining the ratio of bit allocations between I1, I2, P1, P2, B1, and B2 designated frames constant from frame to frame within a GOP.

29. The method of claim 28, further including the step of:

inserting extra P1 frames into temporally busy regions, for producing a more constant perceptual picture quality.

30. The method of claim 29, wherein said inserting step further includes the step of satisfying the following equation:

##EQU24## where k is the number of P1 designated frames, M is the GOP size, R_i1, R_p1, and R_b1 are bit rate allocations for I1, P1, and B1 frames, respectively, and R is the channel bit rate per second, whereby R_i1, R_p1, and R_b1 are adjusted to keep R at a desired constant value.

31. The method of claim 23, further including the step of using the designated positions of P1 and/or P2, and B1, and/or B2 frames, for processing the frames through a motion compensated interpolation encoder, for encoding or compressing the associated video data.

32. The method of claim 31, further including the step of using a telescopic motion vector searching for determining motion between frames.

33. The method of claim 31, further including the steps of:

sensing the bit rate being employed in said encoder in processing frames; and

adjusting the coarseness of quantizing frames in said encoder in proportion to the deviation or error between an actual bit rate and a target bit rate.

34. The method of claim 33, further including the step of limiting the number of quantized P1 frames in high-motion segments between frames by replacing such P1 frames with B1 frames for substantially maximizing the quality of the resultant picture.

35. The method of claim 33, wherein said adjusting step is in accordance with the following equation:

##EQU25## where TB is target bit allocation, XTB is the target bit allocation for the previous frame, ABR_GOP is the actual GOP bit rate, and TBR_GOP is the target GOP bit rate.

36. The method of claim 31, further including the step of:

inserting N P1 frames into the structure of each GOP by default, for reducing encoding delays and distances between reference frames, where N is an integer number 1, 2, 3 . . . ; and

processing each GOP through said encoder via encoding the first frame through successive frames to the first P1 default, and through the next successive frames to the next occurring P1 default, in an iterative manner until all frames have been encoded.

37. The method of claim 36, further including the step of:

sizing each GOP to have an even number of frames whenever N is odd; and

sizing each GOP to have an odd number of frames whenever N is even.

38. A system for compressing video data comprising video data associated with groups of pictures (GOP) including a predetermined number of frames, said system comprising:

motion detection means for determining the degree of global motion between said frames, where global motion is the motion between frames as a whole, wherein said motion detection means includes Type 0 scene change detector means for detecting when the cumulative motion from an immediately preceding reference frame, and a successive frame exceeds a predetermined value defined as a T₀ threshold, whereby said designating means responds by designating and defining the immediately prior frame to said successive frame as a P1 frame;

means responsive to said global motion measurements from said motion detection means for both designating certain of said frames as reference frames, and adjusting the temporal spacing between reference frames, thereby determining the GOP structure, wherein said designating means includes means for coding said reference frames as I and/or P, and B frames relative to global motion between frames; and

encoder means for encoding said reference frames.

39. The system of claim 38, wherein said motion detection means includes:

Type 1 scene change detector means for detecting when the measured level of global motion between two successive frames exceeds a predetermined value defined as a T₁ threshold representing a substantial scene or picture change, whereby said designating means responds by designating and defining the first occurring of the two successive frames as a P2 frame, and the other or second occurring of the two successive frames as an I2 frame.

40. The system of claim 38, wherein said motion detection means further includes:

Type 1 scene change detector means for detecting when the global motion between two successive frames exceeds a predetermined T₁ threshold representing a substantial scene or picture change, whereby said designating means responds by designating the first occurring of the two successive frames as a P2 frame, and the other or second occurring of the two successive frames as an I2 frame.

41. The system of claim 40, wherein said frames are arranged in groups of pictures (GOP) each consisting of a predetermined number of successive frames, and said encoder means further includes:

bit rate controller means for insuring that the number of bits being utilized in encoding a given GOP do not exceed the bit capability of said system.

42. A method for compressing video data comprising the steps of:

determining the degree of global motion between frames of video data, where global motion is the motion between frames as a whole;

assigning reference frames based upon the global motion;

adjusting the temporal spacing between reference frames relative to the degree of global motion measured between frames relative to temporal masking in human vision, thereby determining the group of pictures (GOP) structure;

establishing different threshold magnitudes or levels of motion between frames as representing different scene change types; and

assigning different bit rates to individual frames based upon said pre-established threshold levels of motion between frames, wherein said assigning step further assigns bit rates to said frames in a manner utilizing a backward temporal masking effect in a resulting coding scheme, whereby in instances where a scene change involves relatively large motion between two successive frames, the immediately past frame at the scene change and the immediately following frame are coarsely coded via the assignment of a relatively low bit rate.

43. A system for compressing video data comprising video data associated with groups of pictures (GOP) including a predetermined number of frames, said system comprising:

motion detection means for determining the degree of global motion between said frames, where global motion is the motion between frames as a whole, wherein said motion detection means includes Type 1 scene change detector means for detecting when the measured level of global motion between two successive frames exceeds a predetermined value defined as a T₁ threshold representing a substantial scene or picture change, whereby said designating means responds by designating and defining the first occurring of the two successive frames as a P2 frame, and the other or second occurring of the two successive frames as an I2 frame;

means responsive to said global motion measurements from said motion detection means for both designating certain of said frames as reference frames, and adjusting the temporal spacing between reference frames, thereby determining the GOP structure; and

encoder means for encoding said reference frames.

44. A method for compressing video data comprising the steps of:

determining the degree of global motion between frames of video data, where global motion is the motion between frames as a whole;

assigning reference frames based upon the global motion;

adjusting the temporal spacing between reference frames relative to the degree of global motion measured between frames relative to temporal masking in human vision, thereby determining the group of pictures (GOP) structure;

establishing different threshold magnitudes or levels of motion between frames as representing different scene change types; and

assigning different bit rates to individual frames based upon said pre-established threshold levels of motion between frames, wherein said assigning step further assigns bit rates to said frames by using forward temporal masking in human vision, whereby at a scene change an immediately following frame is coarsely coded.