Method and apparatus for control of rate-distortion tradeoff by using Lagrange multiplier and visual mask

RELATED APPLICATIONS

The present patent application claims the benefit of the previous U.S. Provisional Patent Application entitled "<b>Method and apparatus for Control of Rate-Distortion Tradeoff by Mode Selection in Video Encoders</b>" having serial number <patcit id="pcit0001" dnum="US60424738B"><text>60/424,738</text></patcit> that was filed on November 7,2002 and the previous U.S. Non Provisional Patent Application entitled "<b>Method and apparatus for Control of Rate-Distortion Tradeoff by Mode Selection in Video Encoders</b>" having serial number <patcit id="pcit0002" dnum="US10615117B"><text>10/615,117</text></patcit> that was filed on July 7, 2003.

FIELD OF THE INVENTION

The present invention relates to the field of multi-media compression and encoding systems. In particular the present invention discloses methods and systems for controlling the rate-distortion tradeoff in a digital video encoder.

BACKGROUND OF THE INVENTION

Digital based electronic media formats are completely replacing the legacy analog electronic media formals. In the audio domain, digital compact discs (CDs) replaced analog vinyl recordings many years ago. Analog magnetic cassette tapes are becoming increasingly rare. Second and third generation digital audio systems such as Mini-discs and MP3 (MPEG Audio - layer 3) based formats are now taking away market share from the first generation digital audio format of compact discs.

Film-based still photography is rapidly being replaced by digital still photography. Immediate image availability and image distribution via the Internet have provided users with irresistible features.

However, the video domain has been slower to move to digital storage and transmission formats than audio and still images. This has been largely due to the massive amounts of digital information required to accurately represent video in digital form. The massive amounts of digital information needed to accurately represent video require very high-capacity digital storage systems and high-bandwidth transmission systems.

But the video domain is finally adopting digital stomge and transmission formats. Faster computer processors, high-density storage systems, high-bandwidth optical transmission lines, and new efficient video encoding algorifthms have finally made digital video systems practical at consumer price points, The DVD (Digital Versatile Disc), a digital video system, has been one of the fastest selling consumer electronic products ever. DVDs have been rapidly supplanting Video-Cassette Recorders (VCRs) as the pre-recorded video playback system of choice due their exceptional video quality, high quality 5.1 channel digital audio, convenience, and extra features. In the realm of video transmission systems, the antiquated analog NTSC (National Television Standards Committee) video transmission standard is finally being replaced with the digital ATSC (Advanced Television Standards Committee) video transmission system that uses digital compression and encoding technology.

Computer systems have been using various different digital video encoding formats for a number of years. Among the best digital video compression and encoding systems used by computer systems have been the digital video systems backed by the Motion Pictures Expert Group commonly known by the acronym MPEG. The three most well known and highly used digital video formats from MPEG are known simply as MPEG-1, MPEG-2, and MPEG-4. Video CDs and consumer-grade digital video editing systems use the early MPEG-1 format. Digital Versatile Discs (DVDs) and the Dish Network brand Direct Broadcast Satellite (DBS) television broadcast system use the MPEG-2 digital video compression and encoding system. The MPEG-4 encoding system is rapidly being adapted by the latest computer based digital video encoders and associated digital video players.

The MPEG-2 and MPEG-4 standards compress a series of video frames or video fields and then encode the compressed frames or fields into a digital bitstream. The rate of the digital bitstream must be carefully monitored in order not to overflow memory buffers, underflow memory buffers, or exceed the transmission channel capacity. Thus, a sophisticated rate control system must be implemented with the digital video encoder that provides the best possible image quality in the allotted channel capacity without overflowing or underflowing buffers.

SUMMARY OF THE INVENTION

A Method And Apparatus For Control of Rate-Distortion Tradeoff by Mode Selection in Video Encoders is Disclosed. The system of the present invention first selects a distortion value D near a desired distortion value. Next, the system determines a quantizer value Q using the selected distortion value D. The system then calculates a Lagrange multiplier lambda using the quantizer value Q. Using the selected Lagrange multiplier lambda and quantizer value Q, the system begins encoding pixelblocks.

If the system detects a potential buffer overflow, then the system will increase the Lagrange multiplier lambda. The potential buffer overflow may be detected when a memory buffer occupancy value exceeds an overflow threshold value. If the Lagrange multiplier lambda exceeds a maximum lambda threshold then the system will increase the quantizer value Q.

If the system detects a potential buffer underflow, then the system will decrease the Lagrange multiplier lambda. The potential buffer underflow may be detected when a memory buffer occupancy value falls below a buffer underflow threshold value. If the Lagrange multiplier lambda falls below a minimum lambda threshold then the system will decrease the quantizer value Q.

Other objects, features, and advantages of present invention will be apparent from the company drawings and from the following detailed description.

BRIEF DESCRIPTION OF THE DRAWINGS

The objects, features, and advantages of the present invention will be apparent to one skilled in the art, in view of the following detailed description in which: <ul id="ul0001" list-style="none"><li><figref idref="f0001"><b>Figure 1</b></figref> illustrates a high-level block diagram of one possible a digital video encoder system.</li><li><figref idref="f0002"><b>Figure 2</b></figref> illustrates a series of video pictures in the order that the pictures should be displayed wherein the arrows connecting different pictures indicate inter-picture dependency created using motion compensation.</li><li><figref idref="f0003"><b>Figure 3</b></figref> illustrates the series of video pictures from <figref idref="f0002"><b>Figure 2</b></figref> rearranged into a preferred transmission order of video pictures wherein the arrows connecting different pictures indicate inter-picture dependency created using motion compensation.</li><li><figref idref="f0004"><b>Figure 4</b></figref> graphically illustrates a family of R,D curves, with one curve for each different value of quantizer Q.</li></ul>

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

Modalities to control the rate-distortion tradeoff by mode selection in video encoders are disclosed. In the following description, for purposes of explanation, specific nomenclature is set forth to provide a thorough understanding of the present invention. However, it will be apparent to one skilled in the art that these specific details are not required in order to practice the present invention. For example, the present invention has been described with reference to the MPEG-4 Part 10 (H.264) multimedia compression and encoding system. However, the same techniques can easily be applied to other types of compression and encoding systems.

Multimedia Compression and Encoding Overview

<figref idref="f0001"><b>Figure 1</b></figref> illustrates a high-level block diagram of a typical digital video encoder <b>100</b> as is well known in the art. The digital video encoder <b>100</b> receives incoming video stream <b>105</b> at the left of the block diagram. Each video frame is processed by a Discrete Cosine Transformation (DCT) unit <b>110.</b> The video frame may be processed independently (an intra-frame) or with reference to information from other frames (an inter-frame) using motion estimation unit <b>160.</b> A Quantizer (Q) unit <b>120</b> then quantizes the information from the Discrete Cosine Transformation unit <b>110.</b> The quantized frame is then encoded with an entropy encoder (H) unit <b>180</b> to produce an encoded video bitstream.

Since an inter-frame encoded video frame is defined with reference to other nearby video frames, the digital video encoder <b>100</b> needs to create a copy of exactly how a referenced digital video frame will appear within a digital video decoder such that inter-frames may be encoded. Thus, the lower portion of the digital video encoder <b>100</b> is actually a digital video decoder. Specifically, Inverse quantizer (Q^-1) <b>130</b> reverses the quantization of the frame information and inverse Discrete Cosine Transformation (DCT^-1) unit <b>140</b> reverses the Discrete Cosine Transformation of the video frame information. After all the DCT coefficients are reconstructed from inverse Discrete Cosine Transformation, the motion compensation unit will use the information, along with the motion vectors, to reconstruct the video frame which then may be used as a reference video frame for the motion estimation of other video frames.

The decoded video frame may be used to encode inter-frames that are defined relative to information in the decoded video frame. Specifically, a motion compensation (MC) unit <b>150</b> and a motion estimation (ME) unit <b>160</b> are used to determine motion vectors and generate differential values used to encode inter-frames.

A rate controller <b>190</b> receives information from many different components in a digital video encoder <b>100</b> and uses the information to allocate a bit budget for each video frame to be encoded. The bit budget should be assigned in a manner that will generate the highest quality digital video bit stream that complies with a specified set of restrictions. Specifically, the rate controller <b>190</b> attempts to generate the highest quality of a compressed video stream without overflowing memory buffers (exceeding the amount of available buffer memory by sending video frame information much faster than the video frame information is displayed and subsequently deleted) or underflowing memory buffers (not sending video frame information fast enough such that a receiving digital video decoder runs out of video frame information to display).

Pixelblock Encoding

Many digital video coding algorithms first partition each video picture into small subsets of pixels that are generally referred to as pixelblocks. Specifically, the video picture is divided into a grid of rectangular pixelblocks. The terms Mocroblock, block, sub-block are also commonly used for subsets of pixels. This document will use theterm pixelblock to include all of these different but similar constructs. Different sized pixelblocks may be used by different digital video eacoding systems. For exarsple, different pixerblock sizes used include 8 pixel by 8 pixel pixelblocks, 8 pixel by 4 pixel pixelblocks, 16 pixel by 16 pixel pixelblocks, 4 pixel by 4 pixel pixelblocks, etc.

To encode a video picture, each individual pixelblock of the video picture is encoded using some sort of encoding method. Some pixelblocks known as iutra-blocks are encoded without reference to any other pixelblocks. Other pixelblocks are encoded using some predictive coding method such as motion compensation that refers to a closely matching pixelblock in the same or a different video picture.

Each individual pixelblook in a video picture is independently compressed and encoded. Some video coding standards, e,g., ISO MPEG or ITU H.264. use different types of predicted pixelblocks to encode digital video pictures. In one scenario, a pixelblock may be one of three types; <ol id="ol0001" compact="compact" ol-style=""><li>1. 1-pixelblock -An Intra (I) pixelblock uses no information from any other video pictures in its coding (Thus, an intra-pixelblock it is completely self-defined.);</li><li>2. P-pixelblock-A unidirectionally Predicted (P) pixelblock refers to picture information from an earlier video picture; or</li><li>3. B-pixelblock - A Bi-diyectional predicted (B) pixelblock uses information from both an earlier video picture and a later future video picture.</li></ol>

If all of the pixelblocks in an encoded digital video picture are Intra-pixelblocks (I-pixelblocks) then the encoded digital video picture frame is known as an Intra-frame. Note that an Intra-frame makes no reference to any other video picture such that the Intra-frame digital video picture is completely self-defined,

If a digital video picture frame only includes unidirectional predicted pixelblocks (P-pixelblocks) and intra-pixelblocks (I-pixelblocks) but no bidirectional predicted pixelblocks (B-pixelblocks), then the video picture frame is known as a P-frame, I-pixelblocks may appear in P-frames when using predictive encoding (P-Pixelblock encoding) requires more bits than an independently encoded pixelblock (an I-pixelblork).

If a digital video picture frame contains any bi-dinctioual predicted pixelblocks (B-pixelblocks), then the video picture frame is known as a B-frame. For the simplicity, this document will consider the case, where all pixelblocks within a given picture are of the same type. (Inta-frames only contain I-pixelblooks, P-frames only contain P-pixelblocks, and B-frmes only contain B-pixelblocks.)

An example sequence of video pictures to be encoded might be represented as: <ul id="ul0002" list-style="none" compact="compact"><li>I₁ B₂ B₃ B₄ B₅ B₆ B₇ B₈ B₉ B₁₀ B₁₁ B₁₂ B₁₃ B₁₄...</li></ul> where the letier (I, P, or B) represents if the digital video picture frame is an I-frame, P-frane, or B-frame and the numerical subscript represents the camera order of the video picture in the sequence of video pictures. The camera order is the order in which a camera recorded the video pictures and thus is also the order in which the video pictures should be displayed (the display order),

The preceding example series of video pictures is conceptually illustrated in <figref idref="f0002"><b>Figure 2</b></figref>. Referring to <figref idref="f0002"><b>Figure 2</b></figref><b>,</b> the arrows indicate, that pixelblocks from a stored picture (I-frame or P-frame in this case) are used in the motion compensated prediction of other digital video pictures (B-frmes and P-frames).

Referring to <figref idref="f0002"><b>Figure 2</b></figref><b>,</b> no information form any other video picture is used in the encoding of the first video picture frame, intra-frame video picture I₁. Video picture P₅ is a P-frame that uses video information from previous video picture I₁ in its encoding such that an arrow is drawn from intut-frame video picture I₁ to P-frame video picture P₅. Video picture B₁, video picture B₃, and video picture B₄ all use information from both video picture I₁ and video picture P₅ in their encoding, such that information dependency arrows are drawn from video picture I₁ and video picture P₅ to video picture B₂, video picture B₃, and video picture B₄,

Since B-frame video pictures use information from later video pictures (pictures that will be displayed later), the transmission order of a set of digital video pictures is usually different than the display order of the digital video pictures. Specifically, referenced video pictures that are needed to construct other video pictures should be transmitted before the video pictures that are dependent upon referenced video pictures. Thus, for the display order of <figref idref="f0002"><b>Figure 2</b></figref><b>,</b> the preferred transmission order might be: <ul id="ul0003" list-style="none" compact="compact"><li>I₁ P₅ B₂ B₃ B₄ P₁₀ B₆ B₇ B₈ B₉ P₁₂ B₁₁ B₁₃...</li></ul><figref idref="f0003"><b>Figure 3</b></figref> graphically illustrates this preferred transmission order of the video pictures from <figref idref="f0002"><b>Figure 2</b></figref><b>.</b> Again, the arrows in the figure indicate that pixelblocks from a referenced video picture (an I-frame or P-frame video picture in this case) are used in the motion compensated prediction of other video pictures (P-frame and B-frame video pictures).

Referring to <figref idref="f0003"><b>Figure 3</b></figref>, the transmitting system first transmits I-frame I₁ which does not depend on any other video frame. Next, the system transmits P-frame video picture P₅ that depends only upon previously transmitted video picture I_1. Next, the system transmits B-frame video picture B₂ after video picture P₅ even though video picture B₂ will be displayed before video picture P₅. The reason for this is that when it comes time to decode and render dependent video picture B₂, the digital video decoder will have already received and decoded the information in video picture I₁ and video picture P₅ necessary to decode dependent video picture B₂. Similarly, decoded video picture I₁ and decoded video picture P₅ are ready to be used to decode and render the next two dependent video pictures: dependent video picture B₃ and dependent video picture B₄.

The receiver/decode system then reorders the video picture sequence for proper display. In this operation, referenced video picture I₁ and referenced video picture P₅ are referred to as "stored pictures," Stored pictures are used to reconstruct other dependent video pictures that refer to the stored pictures. (Note that some digital video encoding system also allow B-frames to be used as stored pictures.)

P-Pictures

The encoding of P-Pictures typically utilizes Motion Compensation (MC), wherein a Motion Vector (MV) pointing to a location in a previous video picture is computed for each pixelblock in the current video picture. The Motion Vector refers to a closely matching pixelblock in a referenced video picture. Using the motion vector, a prediction pixelblock can be formed by translation of referenced pixels in the aforementioned previous video picture. The difference between the actual pixelblock in the P-Picture and the prediction pixelblock is then coded for transmission. This difference is then used to accurately reconstruct the original pixelblock.

Each motion vector may also be transmitted via a predictive encoding method. For example, a motion vector prediction may be formed using nearby motion vectors. In such a case, then the difference between the actual motion vector and a predicted motion vector is then coded for transmission. The difference is then used to ereate the actual motion vector from the predicted motion vector.

B-Pictures

Each B-pixelblock in a B-frame uses two different motion vectors: a first motion vector that references a pixelblock in an earlier video picture and a second motion vector that references another pixelblock in a later video picture. From these two motion vectors, two prediction pixelblocks are computed. The two predicted pixelblocks are then combined together, using some function, to form a final predicted pixelblock. (The two predicted pixelblocks may simply be averaged together.) As with P-pixelblocks, the difference between the actual desired pixelblock for the B-frame picture and the final predicted pixelblock is then encoded for transmission. The pixelblock difference will then used to accurately reconstruct the original desired pixelblock.

As with P-pixelblocks, each motion vector (MV) of a B-pixelblock may also be transmitted via a predictive encoding method, Specifically, a predicted motion vector may be formed using some combination of nearby motion vectors, Them, the difference between the actual motion vector and the predicted is encoded for transmission. The difference is then used to recreate the actual motion vector from the predicted motion vector.

However, with B-pixelblooks the opportunity exists for interpolating motion vectors from motion vectors in the collocated or nearby stored picture pixelblock. Such motion vector interpolation is carried out both in the digital video encoder and the digital video decoder. (Remember that a digital video encoder always includes a digital video decoder.)

In some cases, the interpolated motion vector is good enough to be used without any type of correction to the interpolated motion vector. In such cases, no motion vector data need be sent. This is referred to as 'Direct Mode' in the ITU H.263 and H.264 digital video encoding standards,

The technique of motion vector interpolation works particularly well on a series of digital video pictures from a video sequence created by a camera that is slowly panning across a stationary background. In fact, such motion vector interpolation may be good enough to be used alone. Specifically, this means that no differerential motion vector information needs be calculated or transmitted for these B-pixelblock motion vectors encoded using such motion vector interpolation.

Pixelblock Encoding

Within each video picture the pixelblocks may also be coded in different manners. For example, a pixelblock may be divided into smaller subblocks, with motion vectors computed and transmitted for each subblock. The shape of the subblocks may also vary and may not necessarily be square.

Within a P-picture or B-picture, some pixelblocks may be more efficiently encoded without using motion compensation if no closely matching pixelblock can be found in the stored reference picture. Such pixelblocks would then be coded as Intra-pixelblocks (I-pixelblocks). Within a B-picture, some pixelblocks may be better coded using unidirectional motion compensation instead of bidirectional motion compensation. Thus, those pixelblocks would be coded as forward predicted pixelblocks (P-pixelblocks) or backward predicted pixelblocks depending on whether the closest matching pixelblock was found in an earlier video picture or a later video picture.

Prior to transmission, the prediction error of a pixelblock or subblock is typically transformed by an orthogonal transform such as the Discrete Cosine Transform or an approximation thereto. The result of the transform operation is a set of transform coefficients equal in number to the number of pixels in the pixelblock or subblock being transformed. At the receiver/decoder, the received transform coefficients are inverse transformed to recover the prediction error values to be used further in the decoding. Not all the transform coefficients need be transmitted for acceptable video quality. Depending on the transmission bit-rate available, more than half or sometimes much more than half of the transform coefficients may be deleted and not transmitted. At the decoder the deleted coefficient values are replaced by zero values prior to inverse transform operation.

Furthermore, prior to transmission the transform coefficients are typically Quantized and Entropy Coded as set forth with reference to <figref idref="f0001"><b>Figure 1</b></figref><b>.</b> Quantization involves representstion of the transform coefficient values by a finite subset of possible values, which reduces the accuracy of transmission. Furthermore, the quantization often forces small transform coefficient values to zero, thus further reducing the number of transform coefficients values that are transmitted.

In the quantization step, each transform coefficient value is typically divided by a quantizer step size Q and rounded to the nearest integer. For example, the original transform coefficient C may be quantized into the quantized coefficient value Cq using the formula: <ul id="ul0004" list-style="none" compact="compact"><li>Cq = (C + Q/2)/Q truncated to an integer.</li></ul> After the quantization step, the integers are then entropy coded using variable length codes (VLC) such as Huffman codes or Arithmetic codes. Since many transform coefficient values will be truncated to zero, a good amount of compression will be achieved from the quantization and variable length coding steps.

Using a Lagrange Function to Select Bit Rate and Distortion Values

A digital video encoder must determine the best encoding method amongst all of the possible encoding methods (or encoding modes) that will be used to encode each pixelblock in a video picture. This encoding problem is commonly known as the mode selection problem. Many ad hoc solutions have been used in various digital video encoder implemetations to address the mode selection problem. The combination of the transform coefficient deletion, the quantization of the transform coefficients that are transmitted, and the mode selection leads to a reduction of the bit rate R used for transmission. However, these bit rate R reduction techniques also lead to a distortion D in the decoded video pictures.

Ideally, when designing a video encoder one would like to either fix the bit rote R to a constant value and minimize the coding distortion D or fix the coding distortion D to a constant value while minimizing the bit rate R. However, especially at the pixelblock level, the bit rate R and/or the distortion D value may vary considerably from the desired fixed value, thus making the constrained optimization approach untenable.

Instead what may be done is to use a Lagrange multiplier to convert the constrained optimization problem into an unconstrained optimization problem. Thus, instead of fixing one of the variables (bit rate R or the distortion D) and optimízing the other variable, one may instead simply minimize the Lagrange function: <maths id="math0001" num=""><math display="block"><mi mathvariant="normal">D</mi><mo>+</mo><mi>lambda</mi><mo>×</mo><mi mathvariant="normal">R</mi></math><img file="EP2271104A2_D0001.tif" /></maths> where lambda is the Lagrange multiplier. Thus, for each pixelblock in a video picture, the encoder selects the pixelblock encoding mode that minimizes the Lagrange function D + lambda × R.

In theory, a full optimization for each individual video picture would be carried out by repeatedly using all possible values of lambda, with each lambda producing a {D,R} pair. From this, for a desired bit rate R (or distortion D), the corresponding distortion D (or bit rate R) and lambda value can be found. Then the video picture would be finally encoded again using this selected lambda value, which would produce the desired result.

In practice, this ideal approach is usually too complicated and too resource intensive to perform for every video picture. What is usually done is to carry out many preliminary experiments with many video pictures using the complete optimization method above with a wide range of lambdas in order to determine approximate relationships between lambda, distortion D, and quantizer Q.

Preliminary experiments with a large number of video pictures using the complete optimization method with a wide range of lambdas determine approximate relationships between lambda, distortion D, and quantizer Q. In these experiments it is often advantageous to hold the quantizer Q constant while varying the lambda Lagrange multiplier. If quantizer Q is held constant during each experiment, the end result is a family of R,D curves, with one curve for each different value of quantizer Q. <figref idref="f0004"><b>Figure 4</b></figref> illustrates one example of such a family of R,D curves. For each different constant Q curve, at a particular {R,D} point obtained with a certain value of lambda the slope of the curve is (-lambda). The optimum {R,D} relationship is obtained by taking the minimum of all the R,D curves.

Following this, for each different quantiser Q value, a representative lambda value is chosen such as lambda_Q. For example, lambda_Q might be the value that provides a distortion D value half-way between the crossover points for Q+1 and Q-1 in <figref idref="f0004"><b>Figure 4</b></figref><b>.</b> Other methods that have been used to select a representative lambda value include lambda_Q = 0.85Q² and lambda_Q = 0.85×2^Q/3, For multiple B-pictures, much larger lambda_Q values are often chosen. Thus, we have <maths id="math0002" num=""><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>lambda</mi><mi mathvariant="normal">Q</mi></msub><mo mathvariant="normal">=</mo><mi mathvariant="normal">f</mi><mfenced><mi mathvariant="normal">Q</mi></mfenced></mtd></mtr><mtr><mtd><msub><mi mathvariant="normal">D</mi><mi mathvariant="normal">Q</mi></msub><mo mathvariant="normal">=</mo><mi mathvariant="normal">g</mi><mfenced><mi mathvariant="normal">Q</mi></mfenced><mspace width="1em" /><mi>from which one can obtain Q</mi><mo mathvariant="normal">=</mo><mi mathvariant="normal">h</mi><mfenced><msub><mi mathvariant="normal">D</mi><mi mathvariant="normal">Q</mi></msub></mfenced></mtd></mtr></mtable></math><img file="EP2271104A2_D0002.tif" /></maths> Then to encode a video picture sequence with a desired distortion D, one may first find the nearest D_Q from which one obtains Q = h(D_Q). Then the video picture encoding is performed using the corresponding lambda_Q = f(Q), which provides the optimum bit rate R for the distortion D_Q.

In many applications, the resulting bit rate R may be too large or too small necessitating the use of rate control to ensure that no buffer overflow or buffer underflow occurs. With most rate control algorithms, the usual method is to vary the quantizer Q from pixelblock to pixelblock and/or from video picture to video picture, When the encoder buffer threatens to get too full (and possibly overflow) the value of the quantizer Q is increased in order to reduce the bit rate R. When the encoder buffer is too empty (and will possibly underflow), the quantizer Q is reduced in order to increase the bit rate R.

However, the changing of the quantizer Q value may result in too large of a change in the bit rate R. Furthermore, changes in the Quantizer Q need to be signaled to the decoder, which adds to the amount of overhead bits that must be transmitted to the decoder. Moreover, changing Quantizer Q may have other effects relating to video picture quality, such as loop filtering.

An alternative to change the quantizer Q is to change the Lagrange multiplier lambda in order to achieve the desired rate control. A smaller value of the Lagrange multiplier lambda resets in a larger bit rate R (and smaller distortion D), and similarly a larger value of the Lagrange multiplier lambda decreases the bit rate R (and increases distortion D). The variation in the Lagrange multiplier lambda can be arbitrarily fine, as opposed to changes in the quantizer Q that is digitized and encoded such that the quantizer Q is limited to only certain values. In many digital video compression and encoding systems, including all of the MPEG video compression and encoding standards, not all integer values of the quantizer Q are allowed to be sent, in which case the abrupt change in bit rate R may be even more pronounced.

When the Lagrange multiplier lambda is required to be larger than a certain threshold Lambda_max(Q) to achieve a certain bit rate reduction, then the quantizer Q would be increased and the Lagrange multiplier lambda would return to its nominal value f(Q) using the newly increased quantizer Q value. When the Lagrange multiplier lambda is required to be smaller than a certain threshold Lambda_min(Q) to achieve a certain bit rate increase, then the quantizer Q would be decreased and the Lagrange multiplier lambda would return to its nominal value f(Q) using the newly decreased quantizer Q.

The values of Lambda_max(Q) and Lambda_min(Q) are determined by the crossover points on the bit rate-distortion relationship illustrated in <figref idref="f0004"><b>Figure 4</b></figref><b>.</b> If one defines D(lambda,Q) to be the distortion achieved when encoding with the Lagrange multiplier lambda and quantizer step size Q, then the operative relationships are <maths id="math0003" num=""><math display="block"><mtable columnalign="left"><mtr><mtd><mi mathvariant="normal">D</mi><mo>⁢</mo><mfenced separators=""><mi>lambda_min</mi><mo>⁢</mo><mfenced separators=""><mi mathvariant="normal">Q</mi><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mfenced><mo mathvariant="normal">,</mo><mi mathvariant="normal">Q</mi><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mfenced><mo mathvariant="normal">=</mo><mi mathvariant="normal">D</mi><mfenced separators=""><mi>lambda_max</mi><mfenced><mi mathvariant="normal">Q</mi></mfenced><mo mathvariant="normal">,</mo><mi mathvariant="normal">Q</mi></mfenced></mtd></mtr><mtr><mtd><mi>lambda_min</mi><mfenced><mi mathvariant="normal">Q</mi></mfenced><mo>&lt;</mo><mo>=</mo><mi mathvariant="normal">f</mi><mfenced><mi mathvariant="normal">Q</mi></mfenced><mo>&lt;</mo><mo>=</mo><mi>lambda_max</mi><mfenced><mi mathvariant="normal">Q</mi></mfenced></mtd></mtr></mtable></math><img file="EP2271104A2_D0003.tif" /></maths>

The detailed operation of such a rate control algorithm for a video encoding system is set forth in the following pseudo code: <pre listing-type="program-listing"> Start_encoding_picture: // Begin encoding a video picture input desired D; // Get the desired Distortion D value find DQ nearest to D; // Find the DQ value closest to the desired D Q = h(DQ); // Determine the quantizer value Q lambda = f(Q); // Determine the Lagrange multiplier lambda start_encoding_pixelblock: // Begin encoding a pixelblock from the picture code_pixelblock(lambda,Q); // Encode pixelblock using lambda and Q if (encoder_buffer &gt; Tfull){ // Buffer threatens to overflow? lambda = lambda+deltalambda; // deltalambda may depd on Q if (lambda &gt; Lambda_max(Q)}{ // if lambda too large, incr Q Q = Q+deltaQ; // Increase the Quantizer Q size lambda = f(O); // Set new Lagrange multiplier lambda } } if (encoder_buffer &lt; Ternpty){ // Buffer threatens to underflow? lambda=lambda-deltalambda; // Yes, so decrease lambda if (lambda &lt; Lambda_rnin(Q) ){ // if lambda too small, decr Q Q = Q-deltaQ; // Decrease Quantizer Q size lambda = f(Q); // Set new Lagrange multiplier lambda } } if (not last pixelblock) then goto start_encoding_pixelblock; //Next blok // Done with picture.</pre>

Variations on this general rate control algorithm could include multiple different thresholds for the encoder_buffer value, whereby if encoder_buffer greatly exceeded the Tfull threshold then Quantizer Q could be incremented immediately without waiting for the Lagrange multiplier lambda to exceed its threshold. Similarly, if encoder_buffer was significantly below the Tempty threshold then the Quantizer Q could be decremented immediately, Alternatively, the deltalambda step size could be increased if encoder_buffer greatly exceeded the Tfull threshold or greatly undershot the Tempty threshold.

The values of deltalmbda and deltaQ might vary with the quantizer Q or with video picture type (I-picture, P-picture, or B-picture). Furthermore, the increment operation on the Lagrange multiplier lambda might be replaced by a multiplication that could change the Lagrange multiplier lambda by a certain percentage amount. For example, the Lagrange multiplier lambda may be changed using the following equation for a lambda increase operation: <maths id="math0004" num=""><math display="block"><mi>lambda</mi><mo>=</mo><mfenced separators=""><mn>1</mn><mo>+</mo><mi>deltalambda</mi></mfenced><mo>×</mo><mi>lambda</mi></math><img file="EP2271104A2_D0004.tif" /></maths> Similarly, for the lambda decrement operation the following equation may be used <maths id="math0005" num=""><math display="block"><mi>lambda</mi><mo>=</mo><mfenced separators=""><mn>1</mn><mo>-</mo><mi>deltalambda</mi></mfenced><mo>×</mo><mi>lambda</mi></math><img file="EP2271104A2_D0005.tif" /></maths>

This simple rate control algorithm illustrates the use of varying lambda for this application. Other more complicated rate control algorithms have also been devised, and those other rate control algorithms too could benefit from varying the Lagrange multiplier lambda,

Visual Distortion Tradeoff

Another application for varying the Lagrange multiplier lambda is in the use of visual distortion criteria. The distortion D is often measured by summing the squared difference between the original pixel values and the decoded pixel values. However, this simple distortion measurement method is not well tuned to the actual visibility of pixel errors in a video picture. Thus, such a simple distortion measurement method may cause the preceding minimizations to provide give less than optimal results. Thus, an algorithm that takes subjective effects into account is often more useful.

The visibility of encoding noise may be taken into account by calculating a visual mask value M for each pixelblock or subblock that will be encoded in the video picture. The visual mask value M is based on spatial variations and temporal variations of the pixels within the region.

A larger value of visual mask M indicates greater masking that makes the distortion more difficult to visually detect. In such regions, the distortion D can be increased and the bit rate R reduced. This is conveniently accomplished by using M x lambda (the Lagrange multiplier) in the encoding optimization algorithm instead of the Lagrange multiplier lambda alone. The following pseudo code sets for the modified algorithm: <pre listing-type="program-listing"> Start_encoding_picture: // Begin encoding a video picture input desired D: // Get the desired Distortion D value find DQ nearest to D; // Find the D value closes to the desired D Qnorm = h(DQ); // Determine normal Q with no masking lambda = f(Qnorm); // Determine the Lagrange multiplier lambda stsrt_encoding_pixelblock: // Begin encoding a pixelblock from the picture Q = Qnorm; // Set Q to the normal Q with no masking calculate visual mask M; // Determine the visual masking amount while(Mxlambda &gt; Lambda_max(Q) ){// if strong masking, increase Q Q = Q+deltaQ; // Raise the Quantizer Q size code pixelblock(Mxlambda, Q); // Encode using Mxlambda and Q if (encoder_buffer &gt; Tfull){ // If buffer threatens to fill overflow lambda = lambda+deltalambda; // Increase lambda if (lambda &gt; Lambda_max(Qnorm){ // Test lambda Qnorm=Qnorm+deltaQ; //Increase Q if lambda too big lambda = f(Qnorm); // Calculate new lambda } } if (encoder_buffer &lt; Tempty){ // If buffer threatens to fill underflow lambda = lambda-deltalambda; // Decrease lambda if (lambda &lt; Lambda_min(Qnorm) ){ // Test lambda Qnorm = Qnorm-deltaQ; // Decr Q if lambda too small lambda = f(Qnorm); // Calculate new lambda } } if (not last pixelblock) then goto start_encoding_pixelblock //Next // Done with picture.</pre> This second simple visual masking algorithm illustrates the use of varying, lambda for this application, Other more complicated visual masking algorithms have also been devised, and those visual masking algorithms could also benefit from varying lambda.

Variation of the Lagrange multiplier lambda may also be useful in other encoding decisions. For example, the determination of how many B-pictures to encode when encoding a series of video pictures is often very difficult to answer. For a particular value of quantizer Q and lambda_Q = f(Q), the result of encoding with one B-picture per P-picture might be R₁,D₁ whereas the result of encoding with two B-pictures per P picture might be R₂,D₂.

If R₂&lt;R₁ and D₂&lt; D₁ then it is clear that the best answer is that two B-pictures are better. However, very often the result is R₂&lt; R₁ and D₂&gt; D₁ such that it is not clear number of B-pictures is better. In this case we can recode using two-B pictures per P picture with a smaller lambda that gives D₂ approximately equal to D₁. Then we simply compare the resulting values of R₂ and R₁ to see which bit rate is smaller.

Other scenarios may be similarly compared, e.g., interlace vs. progressive coding, coding with various motion search ranges, encoding with or without certain encoding modes, etc.

In conclusion, we present a simple but powerful method of rate-distortion tradeoff that has many applications in video coding. The foregoing has described a system for control of rate-distortion tradeoff by encoding mode selection in a multi-media compression and encoding system. It is contemplated that changes and modifications may be made by one of ordinary skill in the art, to the materials and arrangements of elements of the present invention without departing from the scope of the invention.

In particular, according to an aspect, the invention provides a method of controlling rate distortion in a video compression and encoding system as defined in item 1 below, the subsequent items 2 to 8 defining preferred embodiments thereof. <ul id="ul0005" list-style="none" compact="compact"><li>Item 1. A method of controlling rate distortion in a video compression and encoding system, said method comprising: <ul id="ul0006" list-style="none" compact="compact"><li>selecting a distortion value D near a desired distortion value;</li><li>determining a quantizer value Q using said distortion value D;</li><li>calculating a Lagrange multiplier lambda using said quantizer value Q; and</li><li>encoding a pixelblock using said Lagrange multiplier lambda and said quantizer value Q.</li></ul></li><li>Item 2. The method of item 1, said method further comprising: <ul id="ul0007" list-style="none" compact="compact"><li>increasing said Lagrange multiplier lambda when a buffer exceeds an overflow threshold value and increasing said quantizer value Q if said Lagrange multiplier lambda exceeds a maximum lambda threshold; and</li><li>decreasing said Lagrange multiplier lambda when a buffer falls below an undererflow threshold value and decreasing said quantizer value Q if said Lagrange multiplier lambda falls below a minimum lambda threshold.</li></ul></li><li>Item 3. The method of item 2, said method further comprising: <ul id="ul0008" list-style="none" compact="compact"><li>recalculating said Lagrange multiplier lambda if said quantizer value Q is adjusted.</li></ul></li><li>Item 4. The method of item 2, said method further comprising wherein said Lagrange multiplier lambda is increased or decreased by an amount dependent upon said quantizer value Q,</li><li>Item 5. The method of item 1, said method further comprising: <ul id="ul0009" list-style="none" compact="compact"><li>calculating a visual mask value M; and</li><li>increasing said Lagrange multiplier lambda when said visual mask value M times said Lagrange multiplier lambda is less than a maximum threshold for said Lagrange multiplier lambda.</li></ul></li><li>Item 6. The method of item 5 wherein said maximum threshold for said Lagrange multiplier lambda is dependent upon said quantizer value Q.</li><li>Item 7. The method of item 5, said method further comprising: <ul id="ul0010" list-style="none" compact="compact"><li>increasing said Lagrange multiplier lambda when a buffer exceeds an overflow threshold value and increasing said quantizer value Q if said Lagrange multiplier lambda exceeds a maximum lambda threshold; and</li><li>decreasing said Lagrange multiplier lambda when a buffer falls below an undererflow threshold value and decreasing said quantizer value Q if said Lagrange multiplier lambda falls below a minimum lambda threshold.</li></ul></li><li>Item 8. The method of item 7, said method further comprising: <ul id="ul0011" list-style="none" compact="compact"><li>recalculating said Lagrange multiplier lambda if said quantizer value Q is adjusted.</li></ul> According to another aspect, the invention provides a computer-readable medium as defined in item 9 below, the subsequent items 10 to 16 defining preferred embodiments thereof.</li><li>Item 9. A computer-readable medium, said computer-readable medium containing a set of computer instructions for implementing a method of controlling rate distortion in a video compression and encoding system with the following steps: <ul id="ul0012" list-style="none" compact="compact"><li>selecting a distortion value D near a desired distortion value;</li><li>determining a quantizer value Q using said distortion value D;</li><li>calculating a Lagrange multiplier lambda using said quantizer value Q; and encoding a pixelblock using said Lagrange multiplier lambda and said quantizer value Q.</li></ul></li><li>Item 10. The computer-readable medium of item 9 wherein said set of computer instructions further implement the steps of: <ul id="ul0013" list-style="none" compact="compact"><li>increasing said Lagrange multiplier lambda when a buffer exceeds an overflow threshold value and increasing said quantizer value Q if said Lagrange multiplier lambda exceeds a maximum lambda threshold; and</li><li>decreasing said Lagrange multiplier lambda when a buffer falls below an undererflow threshold value and decreasing said quantizer value Q if said Lagrangs multiplier lambda falls below a minimum lambda threshold.</li></ul></li><li>Item 11. The computer-readable medium of item 10 wherein said set of computer instructions further implement the steps of: <ul id="ul0014" list-style="none" compact="compact"><li>recalculating said Lagrange multiplier lambda if said quantizer value Q is adjusted.</li></ul></li><li>Item 12. The computer-readable medium of item 10 wherein said Lagrange multiplier lambda is increased or decreased by an amount dependent upon said quantizer value Q.</li><li>Item 13. The computer-readable medium of item 9 wherein said set of computer instructions further implement the steps of: <ul id="ul0015" list-style="none" compact="compact"><li>calculating a visual mask value M; and</li><li>increasing said Lagrange multiplier lambda when said visual mask value M times said Lagrange multiplier lambda is less than a maximum threshold for said Lagrange multiplier lambda.</li></ul></li><li>Item 14. The computer-readable medium of item 13 wherein said maximum threshold for said L-agrage multiplier lambda is dependent upon said quantizer value Q.</li><li>Item 15. The computer-readable medium of item 13 wherein said set of computer inactions further implement the steps of: <ul id="ul0016" list-style="none" compact="compact"><li>increasing said Lagrange multiplier lambda when a butter exceeds an overflow threshold value and increasing said quantizer value Q if said Lagrange multiplier lambda exceeds a maximum lambda threshold; and</li><li>decreasing said Lagrange multiplier lambda when a buffer falls below an undererflow threshold value and decreasing said quantizer value Q if said Lagrange multiplier lambda falls below a minimum lambda threshold.</li></ul></li><li>Item 16. The computer-readable medium of item 15 wherein said set of computer instructions further implement the steps of: <ul id="ul0017" list-style="none" compact="compact"><li>recalculating said Lagrange multiplier lambda if said quantizer value Q is adjusted.</li></ul></li></ul>

Before going on to set out the claims, we shall first provide a set of clauses describing embodiments of the invention: <ol id="ol0002" compact="compact" ol-style=""><li>1. A method for controlling rate distortion, the method comprising: <ol id="ol0003" compact="compact" ol-style=""><li>a. encoding at least one video picture based on an initial quantizer value and an initial Lagrange multiplier; and</li><li>b. adjusting the encoding of the video picture by changing the initial quantizer value or the initial Lagrange multiplier.</li></ol></li><li>2. The method of clause 1, wherein the initial quantizer value and the initial Lagrange multiplier are adjusted to achieve a particular distortion value.</li><li>3. The method of clause 2, wherein the particular distortion value is a distortion value that is closest to a desired distortion value.</li><li>4. The method of clause 1, wherein adjusting the encoding is based on a buffer flow criteria.</li><li>5. The method of clause 1, wherein adjusting the encoding is performed when a buffer exceeds an overflow threshold value.</li><li>6. The method of clause 1, wherein adjusting the encoding is performed when a buffer falls under an underflow threshold value.</li><li>7. The method of clause I, wherein the initial quantizer value is changed when the first Lagrange multiplier is above a maximum threshold value.</li><li>8. The method of clause 1, wherein adjusting the encoding comprises increasing the initial Lagrange multiplier to decrease a bit rate value.</li><li>9. The method of clause 1, wherein adjusting the encoding comprises decreasing the initial Lagrange multiplier to increase a bit rate value.</li><li>10. The method of clause 1, wherein adjusting the encoding comprises increasing the initial quantizer value to decrease a bit rate value.</li><li>11. The method of clause 1, wherein adjusting the encoding comprises decreasing the initial quantizer value to increase a bit rate value.</li><li>12. The method of clause 1, wherein adjusting the encoding comprises changing the Lagrange multiplier by a particular Lagrange delta value from a plurality of Lagrange delta values.</li><li>13. The method of clause 12, wherein the particular Lagrange delta value that is used is based on a particular quantizer value that is used from a plurality of quantizer values.</li><li>14. The method of clause 1, wherein adjusting the encoding comprises changing the quantizer value by a particular quantizer delta value from a plurality of quantizer delta values.</li><li>15. The method of clause 14, wherein the particular quantizer delta value that is used is based on a particular quantizer value that is used from a plurality of quantizer values.</li><li>16. The method of clause 1, wherein adjusting the encoding comprises changing the initial Lagrange multiplier by a particular Lagrange delta value that is multiplied by a particular multiplication factor.</li><li>17. A method for controlling rate distortion, the method comprising: <ol id="ol0004" compact="compact" ol-style=""><li>a. computing a visual mask value for at least one video picture; and</li><li>b. encoding at least one video picture based on the computed visual mask value.</li></ol></li><li>18. The method of clause 17, wherein encoding is further based on a quantizer value and a Lagrange multiplier.</li><li>19. The method of clause 18 further comprising adjusting the encoding of me video picture by changing the quantizer value.</li><li>20. The method of clause 19, wherein the quantizer value is changed when the visual mask value multiplied by the Lagrange multiplier is greater than a threshold value.</li><li>21. The method of clause 18 further comprising adjusting the encoding of the video picture by changing the Lagrange multiplier.</li><li>22. The method of clause 21, wherein the Lagrange multiplier is changed by a Lagrange delta value that is multiplier by the visual mask value.</li><li>23. The method of clause 17, wherein the visual mask value defines a visibility of encoding noise for at least one video picture.</li><li>24. The method of clause 17, wherein the visual mask value is based on spatial variations of at least one pixel within a region of a video picture.</li><li>25. The method of clause 17, wherein the visual mask value is based on temporal variations of at least one pixel within a region of a video picture.</li><li>26. A computer readable medium storing a computer program that is executable by at least one processor, the computer program comprising sets of instructions for implementing the method according to any of clauses 1-25.</li><li>27. An encoder comprising: <ol id="ol0005" compact="compact" ol-style=""><li>a. a quantizer unit for quantizing at least one video picture; and</li><li>b. a rate controller for changing a Lagrange multiplier and a quantizer value that is used by the quantizer unit.</li></ol></li><li>28. The encoder of clause 27, wherein the Lagrange multiplier is changed before the quantizer value is changed.</li><li>29. The encoder of clause 27 further comprising a buffer for storing video pictures.</li><li>30. The encoder of clause 27, wherein the rate controller changes the Lagrange multiplier when a buffer is above a threshold value.</li><li>31. The encoder of clause 27, wherein the rate controller changes the Lagrange multiplier when a buffer is below a threshold value.</li><li>32. The encoder of clause 27, wherein the rate controller changes the quantizer value when a buffer is above a threshold value.</li><li>33. The encoder of clause 27, wherein the rate controller changes the quantizer value when a buffer is below a threshold value.</li><li>34. The encoder of clause 27, wherein the rate controller is farther for computing a visual mask value for at least one video picture.</li></ol>