Quantizer selection based on region complexities derived using a rate distortion model

• US 6,539,124 B2
• Filed: 08/17/1999
• Issued: 03/25/2003
• Est. Priority Date: 02/03/1999
• Status: Expired due to Term

• Current Assignee: MediaTek, Inc.
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Krishnamurthy, Ravi, Sethuraman, Sriram
• Primary Examiner(s): Wu, Jingge
• Application Number:
  US09/376,733
• Publication Number:
  US 20020034245A1
• Time in Patent Office: 1,316 Days
• Field of Search: 382/251, 382/245, 382/236, 375/240.03, 375/240.24, 375/240, 348/433, 348/606, 348/405
• US Class Current: 382/251
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/192 the adaptation method, adaptation tool or adaptation type being iterative or recursive
• CPC Class Codes: H04N 19/50 using predictive coding H04N19/61 takes precedence
• 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/587 involving temporal sub-sampling or interpolation, e.g. decimation or subsequent interpolation of pictures in a video sequence
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

For video compression processing, each frame in a video sequence is segmented into one or more different regions, where the macroblocks of each region are to be encoded using the same quantizer value, but the quantizer value can vary between regions in a frame. For example, for the videophone or video-conferencing paradigm of one or more “talking heads” in front of a relatively static background, each frame is segmented into a foreground region corresponding to the talking head, a background region corresponding to the static background, and an intervening transition region. An encoding complexity measure is generated for each macroblock of the previous frame using a (e.g., first-order) rate distortion model and the resulting macroblock-level encoding complexities are used to generate an average encoding complexity for each region. These region complexities are then used to select quantizer values for each region in the current frame, e.g., iteratively until the target bit rate for the frame is satisfied to within a specified tolerance range. The selected quantizer values may be modified based on spatial and/or temporal constraints to satisfy spatial requirements of the video compression algorithm and/or to provide temporal smoothness in quality, respectively.

Claims

1. A method for encoding a current frame in a video sequence, comprising the steps of:

(a) segmenting the current frame into one or more different regions;

(b) generating an encoding complexity measure for each corresponding region of a previously encoded frame in the video sequence;

(c) using the encoding complexity measure for each region of the previous frame to select a quantization level for the corresponding region of the current frame;

(d) applying a temporal constraint to modify the selected quantization level for at least one region of the current frame, wherein the temporal constraint imposes an absolute upper limit on magnitude of change in quantization level from one region in the previous frame to the corresponding region in the current frame; and

(e) encoding the current frame using the one or more modified quantization levels, wherein;

the temporal constraint when quantization level is increasing from the previous frame to the current frame is different from the temporal constraint when quantization level is decreasing from the previous frame to the current frame; and

the temporal constraint allows greater percentage increases in quantization level than percentage decreases from the previous frame to the current frame.

2. The invention of claim 1, wherein the current frame is segmented into a plurality of regions.

3. The invention of claim 2, wherein the current frame is segmented into a foreground region, a background region, and a transition region, wherein at least one macroblock in the transition region is between each macroblock in the foreground region and each macroblock in the background region following a raster scan pattern through the current frame.

4. The invention of claim 1, wherein, for each region in the current frame, the quantization level is identical for all macroblocks.

5. The invention of claim 1, wherein the encoding complexity measure is based on a first-order temporal prediction model.

6. The invention of claim 1, wherein the encoding complexity measure for each region in the previous frame is generated based on:

7. The invention of claim 6, wherein the distortion measure S is based on a sum of absolute differences (SAD) measure.

8. The invention of claim 6, wherein the encoding complexity measure for each region in the previous frame is generated by averaging the encoding complexity measure X for all of the macroblocks in the region.

9. The invention of claim 1, wherein the encoding complexity measure for each region in the previous frame is generated based on:

10. The invention of claim 9, wherein:

the distortion measure S is based on a sum of absolute differences (SAD) measure; and

the constant C is about 2.5.

11. The invention of claim 9, wherein the encoding complexity measure for each region in the previous frame is generated by averaging the encoding complexity measure X for all of the macroblocks in the region.

12. The invention of claim 1, wherein step (c) comprises the step of iteratively selecting one or more different quantization levels for each region until a frame target bit rate is satisfied to within a specified tolerance range according to:

13. The invention of claim 1, wherein a spatial constraint is applied to ensure that a magnitude of change in quantization level from one macroblock to a next macroblock in the current frame following a raster scan pattern is not greater than a specified maximum spatial change in quantization level.

14. The invention of claim 3, wherein:

the quantization level selected for the foreground region is constrained to be less than or equal to the quantization level selected for the transition region; and

the quantization level selected for the transition region is constrained to be less than or equal to the quantization level selected for the background region.

15. A machine-readable medium having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements the steps of:

(a) segmenting the current frame into one or more different regions;

(b) generating an encoding complexity measure for each corresponding region of a previously encoded frame in the video sequence;

(c) using the encoding complexity measure for each region of the previous frame to select a quantization level for the corresponding region of the current frame;

(d) applying a temporal constraint to modify the selected quantization level for at least one region of the current flame, wherein the temporal constraint imposes an absolute upper limit on magnitude of change in quantization level from one region in the previous frame to the corresponding region in the current frame; and

(e) encoding the current frame using the one or more modified quantization levels, wherein;

the temporal constraint when quantization level is increasing from the previous frame to the current frame is different from the temporal constraint when quantization level is decreasing from the previous from to the current frame; and

the temporal constraint allows greater percentage increases in quantization level than percentage decreases from the previous frame to the current frame.

23. The invention of claim 15, wherein the current frame is segmented into a foreground region, a background region, and a transition region, wherein at least one macroblock in the transition region is between each macroblock in the foreground region and each macroblock in the background region following a raster scan pattern through the current frame.

24. The invention of claim 23, wherein:

the quantization level selected for the foreground region is constrained to be less than or equal to the quantization level selected for the transition region; and

the quantization level selected for the transition region is constrained to be less than or equal to the quantization level selected for the background region.

25. The invention of claim 15, wherein the encoding complexity measure is based on a first-order temporal prediction model.

26. The invention of claim 15, wherein the encoding complexity measure for each region in the previous frame is generated based on:

27. The invention of claim 15, wherein the encoding complexity measure for each region in the previous frame is generated based on:

28. The invention of claim 15, wherein step (c) comprises the step of iteratively selecting one or more different quantization levels for each region until a frame target bit rate is satisfied to within a specified tolerance range according to:

29. The invention of claim 15, wherein a spatial constraint is applied to ensure that a magnitude of change in quantization level from one macroblock to a next macroblock following a raster scan pattern is not greater than a specified maximum spatial change in quantization level.

16. A method for encoding a current frame in a video sequence, comprising the steps of:

(a) segmenting the current frame into one or more different regions;

(b) generating an encoding complexity measure for each corresponding region of a previously encoded frame in the video sequence;

(c) using the encoding complexity measure for each region of the previous frame to select a quantization level for the corresponding region of the current frame; and

(d) encoding the current frame using the one or more selected quantization levels, wherein the encoding complexity measure for each region in the previous frame is generated based on;

17. The invention of claim 16, wherein the distortion measure S is based on a sum of absolute differences (SAD) measure.

18. The invention of claim 16, wherein the encoding complexity measure for each region in the previous frame is generated by averaging the encoding complexity measure X for all of the macroblocks in the region.

19. A method for encoding a current frame in a video sequence, comprising the steps of:

(a) segmenting the current frame into one or more different regions;

(b) generating an encoding complexity measure for each corresponding region of a previously encoded frame in the video sequence;

(c) using the encoding complexity measure for each region of the previous frame to select a quantization level for the corresponding region of the current frame; and

(d) encoding the current frame using the one or more selected quantization levels, wherein the encoding complexity measure for each region in the previous frame is generated based on;

20. The invention of claim 19, wherein:

the distortion measure S is based on a sum of absolute differences (SAD) measure; and

the constant C is about 2.5.

21. The invention of claim 19, wherein the encoding complexity measure for each region in the previous frame is generated by averaging the encoding complexity measure X for all of the macroblocks in the region.

22. A method for encoding a current frame in a video sequence, comprising the steps of:

(a) segmenting the current frame into one or more different regions;

(b) generating an encoding complexity measure for each corresponding region of a previously encoded frame in the video sequence;

(c) using the encoding complexity measure for each region of the previous frame to select a quantization level for the corresponding region of the current frame; and

(d) encoding the current frame using the one or more selected quantization levels, wherein step (c) comprises the step of iteratively selecting one or more different quantization levels for each region until a frame target bit rate is satisfied to within a specified tolerance range according to;

30. A method for encoding a current frame in a video sequence, comprising the steps of:

(a) segmenting the current frame into one or more different regions;

(b) generating an encoding complexity measure for each corresponding region of a previously encoded frame in the video sequence;

(c) using the encoding complexity measure for each region of the previous frame to select a quantization level for the corresponding region of the current frame;

(d) applying a temporal constraint to modify the selected quantization level for at least one region of the current frame, wherein;

the temporal constraint limits magnitude of change in quantization level from one region in the previous frame to the corresponding region in the current frame; and

the temporal constraint allows greater percentage increases in quantization level than percentage decreases from the previous frame to the current frame; and

(e) encoding the current frame using the one or more modified quantization levels.