CN1708991B - Method and apparatus for controlling rate-distortion tradeoff using lagrange multiplier and visual masking - Google Patents

Abstract

The present invention discloses a method and apparatus for controlling rate-distortion trade-off by mode selection in a video encoder. The system of the present invention first selects a distortion value D around the expected distortion value. Next, the system determines a quantizer value Q using the selected distortion value D. The system then calculates the Lagrangian multiplier lambda using the quantizer value Q. With the selected lagrange multiplier lambda and quantizer value Q, the system begins encoding the prime module. If the system detects a potential buffer overflow, the system will increase the Lagrangian multiplier lambda. If the Lagrangian multiplier lambda exceeds the maximum lambda threshold, the system will increase the quantizer value Q. If the system detects a potential buffer underflow, the system will decrease the Lagrangian multiplier lambda. If the Lagrangian multiplier lambda falls below the minimum lambda threshold, the system will decrease the quantizer value Q.

Description

Method and apparatus for controlling rate-distortion tradeoff using Lagrangian multipliers and visual masking

technical field

The invention relates to the field of multimedia compression and coding systems. Among other things, the present invention discloses a method and system for controlling the rate-distortion tradeoff in a digital video encoder.

Background technique

Digital-based electronic media formats are completely replacing traditional analog electronic media formats. In the audio world, digital compact discs (CDs) replaced analog vinyl records many years ago. Analog cassette tapes are also becoming increasingly rare. Second and third generation digital audio systems such as compact disc based formats and mp3 (MPEG Audio-Layer 3) formats are taking market share from first generation digital audio format compact discs.

Digital-based still photography is rapidly replacing film-based still photography. Immediate availability and distribution of images with an irresistible character is provided to users via the Internet.

However, the video world has been slower to move toward digital storage and transmission formats than audio and still photography. This is mainly due to the large amount of digital information required to accurately represent video in digital format. Accurately representing the large amounts of digital information required for video requires very high-capacity digital storage systems and high-bandwidth transmission systems.

But the video domain eventually adopted digital storage and transmission formats. Faster computer processors, high-density storage systems, high-bandwidth optical transmission lines, and new high-efficiency video encoding algorithms are finally making digital video systems practical at consumer prices. DVD (Digital Versatile Disc), digital video system has become one of the fastest-selling consumer electronics products. Due to its outstanding video quality, high-quality 5.1-channel digital audio, convenience, and other features, DVDs have rapidly replaced video recorders (VCRs) as the pre-recorded video playback system of choice. In the field of video transmission systems, the outdated analog NTSC (National Television Standards Committee) video transmission standard was eventually replaced by the digital ATSC (Advanced Television Standards Committee) video transmission system using digital compression and encoding techniques.

Over the years, computer systems have used a variety of different digital video encoding formats. The best digital video compression and encoding system used by computer systems is the well known digital video system supported by the Moving Picture Experts Group with its acronym MPEG. The three most well-known and very heavily used digital video formats of MPEG are the well-known simple MPEG-1, MPEG-2 and MPEG-4. Video CDs, as well as consumer standard digital video editing systems, use the early MPEG-1 format. Digital Versatile Disc (DVD) and Dish Network brand Direct Broadcast Satellite Broadcasting (DBS) use the MPEG-2 digital video compression and encoding system. The latest computer-based digital video encoders and associated digital video players are rapidly adopting the MPEG-4 encoding system.

The MPEG-2 and MPEG-4 standards compress a series of video frames or fields and then compile the compressed frames or fields into a digital bit stream. The rate of the digital bit stream must be closely monitored so that it does not overflow buffers, underflow buffers, or exceed transmission channel capacity. Therefore, complex rate control systems must be implemented with digital video encoders that provide the best possible picture quality within the allocated channel capacity without overflowing or underflowing buffers.

Contents of the invention

The present invention discloses a method and apparatus for controlling rate-distortion tradeoff through mode selection in a video encoder. The system of the present invention first selects the distortion value D around the expected distortion value. Next, the system uses the selected distortion value D to determine a quantizer value Q. The system then computes the Lagrangian multiplier lambda using the quantizer value Q. With the selected Lagrangian multiplier lambda and quantizer value Q, the system begins encoding pixel blocks.

If the system detects a potential buffer overflow, the system will increase the Lagrangian multiplier lambda. A potential buffer overflow can be detected when the occupancy value of the buffer exceeds an overflow threshold. If the Lagrangian multiplier lambda exceeds the maximum lambda threshold, the system will increase the quantizer value Q.

If the system detects a potential buffer underflow, the system will decrease the Lagrangian multiplier lambda. A potential buffer underflow may be detected when the occupancy value of the buffer drops below a buffer underflow threshold. If the Lagrange multiplier lambda falls below the minimum lambda threshold, the system will decrease the quantizer value Q.

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

Description of drawings

Objects, features and advantages of the present invention will be apparent to those skilled in the art through the following detailed description, wherein:

Figure 1 depicts a high-level block diagram of a possible digital video coding system;

What Figure 2 describes is a series of video pictures to be displayed, wherein the arrows connecting different pictures represent the correlation of interactive pictures generated by motion compensation;

Fig. 3 represents the video picture of the preferred transmission sequence obtained by rearranging the video pictures in Fig. 2, wherein the arrows connecting different pictures represent the correlation of interactive pictures generated by motion compensation;

What Fig. 4 describes is a family of R, D curves, and each curve corresponds to each different value of the quantizer Q.

Detailed ways

The present invention discloses modes to control the rate-distortion tradeoff through mode selection in a video encoder. In the following description, for convenience of explanation, specific terms are set forth to provide a complete understanding of the present invention. It will be apparent, however, to one skilled in the art that these specific details are not required in order to practice the present invention. For example, the invention has been described with reference to the MPEG-4 Part 10 (H.264) multimedia compression and coding system. However, the same techniques can be easily applied to other types of compression and encoding systems.

A Survey of Multimedia Compression and Coding

FIG. 1 depicts a high-level block diagram of a typical digital video encoder 100 known in the art. Digital video encoder 100 receives an input video stream 105 located on the left of the block diagram. Each video frame is processed by a discrete cosine transform (DCT) unit 110 . Video frames may be processed independently (intra) or with motion estimation unit 160 with reference to information from other frames (inter). A quantizer (Q) unit 120 then quantizes the information from the discrete cosine transform (DCT) unit 110 . The quantized frames are then encoded by an entropy encoder (H) 180 to generate an encoded video bitstream.

Since an inter-coded video frame is determined with reference to other nearby video frames, the digital video encoder 100 needs to copy how the referenced digital video frame actually appears in the digital video decoder so that the inter-frame can be coded. Thus, the lower part of the digital video encoder 100 is actually a digital video decoder. In particular, the inverse quantizer (Q ⁻¹ ) 130 inverts the quantization of the frame information, and the inverse discrete cosine transform (DCT ⁻¹ ) unit 140 inverts the discrete cosine transform of the video frame information. After all the DCT coefficients are reconstructed from the Inverse Discrete Cosine Transform, the motion compensation unit will use this information together with the motion vectors to reconstruct a video frame which can be used as a reference video frame for motion estimation of other video frames.

The decoded video frame may be used to encode inter-frames defined relative to information in the decoded video frame. In particular, a motion compensation (MC) unit 150 and a motion estimation (ME) unit 160 are used to determine motion vectors and generate differential values for encoding inter-frames.

Rate controller 190 receives information from many different components in digital video encoder 100 and uses this information to allocate a bit budget for each video frame to be encoded. The bit budget is allocated in such a way as to produce the highest quality digital bit stream that obeys a certain set of constraints. In particular, the rate controller 190 attempts to produce the highest quality compressed video stream without overflowing the buffer (exceeding the available buffer by sending video frame information faster than it can be displayed and then deleted) amount) or underflow buffer (video frame information is not sent fast enough for the receiving digital video decoder to run out of video frame information for display).

pixel block coding

Many digital video coding algorithms first divide each video image into small subsets of pixels, often called pixel blocks. In particular, video images are divided into a grid of rectangular pixel modules. The terms macroblock, block, subblock are also commonly used for a subset of pixels. This document will use the term pixel module to cover all these different but similar concepts. Pixel modules of different sizes can be used by different digital video coding systems. For example, different pixel block sizes used include 8x8 pixel blocks, 8x4 pixel blocks, 16x16 pixel blocks, 4x4 pixel blocks, and the like.

To encode a video image, each individual pixel block of the video image is encoded using a certain encoding method. Some pixel blocks, called internal blocks, can be encoded without reference to any other pixel blocks. Other pixel blocks are encoded using some predictive coding method, such as motion compensation, which refers to the closest matching pixel block in the same or a different video image.

Each individual pixel block in a video image is compressed and encoded independently. Some video coding standards, such as ISO MPEG or ITU.264, use different types of predictive pixel blocks to code digital video images. In one aspect, pixel modules can be one of the following 3 types:

1. I pixel module - an internal (I) pixel module that does not use any other video image information in its encoding (thus, the internal pixel module is completely self-defined);

2. P-pixel module - a unidirectional predictive (P) pixel module that references image information from earlier video images; or

3. B-pixel module - a bidirectional predictive (B)-pixel module that utilizes information from earlier video images or later video images.

If all pixel modules in the encoded digital video image are intra pixel modules (I pixel modules), the encoded digital video image frame is called intraframe. Note that Intra does not reference any other video images, making Intra digital video images completely customizable.

If a digital video image frame only includes a unidirectional predictive pixel module (P pixel module) and an internal pixel module (I pixel module) but does not include a bidirectional predictive pixel module (B pixel module), then the visual image It is called a P frame. I-pixel blocks can occur in P-frames when coding using prediction (P-pixel block coding) requires more bits than independently coding pixel blocks (I-pixel blocks).

A video frame is called a B frame if it includes any bidirectionally predictive pixel blocks (B pixel blocks). For simplicity, this application will consider the case where all pixel modules within a given image area are of the same type. (the frame only includes I pixel modules, the P frame only includes P pixel modules, and the B frame only includes B pixel modules.)

An example of a sequence of video images to be encoded can be represented as:

I ₁ B ₂ B ₃ B ₄ P ₅ B ₆ B ₇ B ₈ B ₉ P ₁₀ B ₁₁ P ₁₂ B ₁₃ I ₁₄ ...

Wherein if the digital video image frame is an I frame, a P frame or a B frame, it is represented by a letter I, P or B, and the digital subscript indicates the shooting order of the video images in the video image sequence. The shooting order is the order in which the cameras record the video images and thus the order in which the video images should be displayed (display order).

A series of video images of the foregoing embodiments are conceptually described in FIG. 2 . Referring to Figure 2, arrows indicate that pixel blocks from stored pictures (in this case I or P frames) are used in motion compensated prediction of other digital video pictures (B and P frames).

Referring to FIG. 2, no information from any other video picture is used in the encoding of the first video picture frame, intra video picture _I1 . Video picture _P5 is a P-frame that utilizes video information from the previous video picture _I1 in encoding, so an arrow is drawn from intra-frame video picture _I1 to P-frame video picture _P5 . In their coding, video image B ₂ , video image B ₃ and video image B ₄ all utilize information from video image I ₁ and video image P ₅ , so the information dependency arrows from video image I ₁ and video image P ₅ is drawn to video image B ₂ , video image B ₃ and video image B ₄ .

Since B-frame video images utilize information from subsequent video images (pictures that are subsequently displayed), the transmission order of a set of digital video images is usually not the same as the display order of the digital video images. In particular, the reference video pictures needed to construct other video pictures should be transmitted before the video pictures determined from the reference video pictures. Thus, for the display order in Figure 2, the preferred transmission order may be:

I ₁ P ₅ B ₂ B ₃ B ₄ P ₁₀ B ₆ B ₇ B ₈ B ₉ P ₁₂ B ₁₁ I ₁₄ B ₁₃ …

FIG. 3 depicts a preferred transmission sequence of the video images in FIG. 2 . Arrows in the figure indicate that pixel blocks from a reference video picture (in this case an I-frame or P-frame video picture) are used in motion compensated prediction of other video pictures (P-frame and B-frame video pictures).

Referring to FIG. 3 , the transmission system first transmits an I frame I ₁ that does not depend on any other video frames. Next, the system transmits P frames of video image P ₅ , relying only on the previously transmitted video image I ₁ . Next, even though video image _B2 is displayed before video image _P5 , the system transmits B frames of video image _B2 after video image _P5 . The reason is that when the associated video image _B2 is to be decoded and delivered, the digital video decoder has already received and decoded the information necessary for decoding the associated video image _B2 in the video image _I1 and the video image _P5 . Likewise, the decoded video picture I ₁ and the decoded video picture P ₅ are ready for decoding and delivering the next two related video pictures: related video picture B ₃ and related video picture B ₄ .

The receiver/decoder system then records the video images in the proper display sequence. In this operation, the reference video picture _I1 and the reference video picture _P5 are referred to as "stored pictures". The stored image is used to reconstruct other related video images that reference the stored image. (Note that some digital video coding systems also allow B-frames to be used as stored images.)

Picture-in-picture (P-picture)

Coding of picture-in-picture typically utilizes motion compensation (MC), where a motion vector (MV) is calculated for each pixel block in the current video image pointing to a location in the previous video image. Motion vectors refer to closely matching pixel blocks in a reference video image. Using motion vectors, predictive pixel blocks can be formed by transforming reference pixels from the previous video picture as described above. The difference between the actual pixel block and the predicted pixel block in the picture-in-picture is then encoded for transmission. This difference is then used to accurately construct the initial pixel module.

Each motion vector can also be transmitted by a predictive coding method. For example, neighboring motion vectors can be utilized to form a motion vector prediction. In this case, the difference between the actual motion vector and the predicted motion vector is then encoded for transmission. This difference is then used to generate the actual motion vector from the predicted motion vector.

Bi-directional picture (B-picture)

Each B-pixel block in a B-frame uses two different motion vectors: a first motion vector and a second motion vector, where the first motion vector refers to the pixel block in an earlier video image, and the second motion vector refers to Another pixel block later in the video image. From these two motion vectors, two predicted pixel blocks are calculated. The two predicted pixel blocks are joined together using some function to form the final predicted pixel block. (The two pixel blocks can simply be averaged together.) As with the P pixel block, the difference between the actual expected pixel block and the final predicted pixel block of the B-frame video image is encoded for transmission. This pixel block difference is then used to accurately reconstruct the original pixel block.

As with P-pixel blocks, each motion vector (MV) of a B-pixel block can also be transmitted by a predictive coding method. In particular, some combination of adjacent motion vectors may be used to form the predicted motion vector. The difference between the actual motion vector and the predicted motion vector is then encoded for transmission. This difference is then used to recreate the actual motion vector from the predicted motion vector.

However, for B pixel blocks, there is an opportunity to interpolate motion vectors from motion vectors in configured or adjacently stored image pixel blocks. Interpolation of such motion vectors is performed in digital video encoders and digital video decoders. (Note that digital video encoders always include digital video decoders.)

In some cases, the interpolated motion vector is good enough to be used without any type of modification to the interpolated motion vector. In such cases, there is no need to send motion vector data. In the ITU H.263 and H.264 digital video coding standards, this is called "direct mode".

The motion vector interpolation technique works particularly well on a sequence of video images from a video sequence generated by a camera that is slowly panning a static background. In fact, such motion vector interpolation is good enough to be used alone. In particular, this means that for these B-pixel block motion vectors coded by motion vector interpolation no differential motion vector information is required for calculation or transmission.

pixel block coding

Pixel blocks can also be coded differently within each video image. For example, the pixel block can be divided into smaller sub-blocks, and a motion vector is calculated and transmitted for each sub-block. The shape of the sub-blocks may also vary and may not necessarily be square.

In picture-in-picture or bidirectional pictures, some pixel blocks can be efficiently coded without motion compensation if no close matching pixel block is found in the stored reference picture. Such pixel blocks are then coded as intra-pixel blocks (I-pixel blocks). In bidirectional pictures, some pixel blocks can be encoded better by using unidirectional motion compensation instead of bidirectional motion compensation. Therefore, depending on whether the closest matching pixel blocks are found in an earlier video image or a later video image, those pixel blocks are coded as forward predicted pixel blocks (P pixel blocks) or backward predicted pixel blocks. element module.

Prediction errors of pixel blocks or sub-blocks are typically transformed by an orthogonal transform such as a discrete cosine transform or an approximation thereof prior to transmission. The result of the transformation operation is a set of transformation coefficients that are numerically equal to the number of pixels in the pixel block or subblock being transformed. At the receiver/decoder, the received transform coefficients are inverse transformed to recover the prediction error values used further in decoding. Not all conversion factors need to be transferred for acceptable video quality. Depending on the available transmission bit rate, half or sometimes more than half of the conversion coefficients can be deleted and not transmitted. At the decoder, the deleted coefficient values are replaced by 0 before the inverse transform operation.

Also, before transmission, the transform coefficients are typically quantized and entropy encoded as described in FIG. 1 . Quantization involves representing conversion coefficient values with a limited subset of possible values, which reduces the accuracy of transmission. Also, the quantization often makes small transform coefficient values zero, thereby further reducing the number of transformed transform coefficient 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 initial conversion coefficient C can be quantized into a quantized coefficient value C _q using the following formula:

C _q =(C+Q/2)/Q truncated to an integer.

After the quantization step, these integers are entropy coded using variable length coding such as Huffman coding or arithmetic coding. Since many transform coefficient values are truncated to 0, a lot of compression will be gained from the quantization and variable length coding steps.

Selecting Bit Rate and Distortion Values Using Lagrangian Functions

A digital video encoder must determine the best encoding method among all possible encoding methods (or encoding modes) for encoding each pixel block in a video image. This encoding problem is often referred to as a mode selection problem. A number of specific methods are used in different digital video encoder implementations to deal with the mode selection problem. The combination of transform coefficient deletion, quantization of the transmitted transform coefficients and mode selection results in a reduction of the bit rate R for transmission. However, these bit rate R reduction techniques also result in distortions D in the decoded video images.

Ideally, when designing a video encoder, one would like to either fix the bitrate R to a constant value and reduce the coding distortion D or fix the coding distortion D to a constant value while reducing the bitrate R. However, especially at the pixel block level, the bit rate R and/or distortion D values may differ considerably from the expected fixed values, thus making the defined optimization method untenable.

What can be done, however, is to transform the bounded optimization problem into an unbounded optimization problem using Lagrange multipliers. Thus, instead of fixing one of the variables (bitrate R or distortion D) and optimizing the other, one can just minimize the Lagrange equation:

D+lambda×R

where lambda is the Lagrangian multiplier. Thus for each pixel block in the video image, the encoder selects the pixel block coding mode to minimize the Lagrangian equation D+lambda*R.

In theory, full optimization for each individual video image is achieved by reusing all possible lambda values, each lambda generating a {D, R} pair. The expected bit rate R (or distortion D), the corresponding distortion D (or bit rate R) and the lambda value can be obtained therefrom. The video image is then finally encoded again using the selected lambda value, which will generate the expected result.

In practice, this ideal approach is usually too complex and resource intensive to implement per video image. In order to determine the approximate relationship between lambda, distortion D and quantizer Q, it is common practice to perform many preliminary experiments with multiple video images using a full optimization method with a wide range of lambda values.

The approximate relationship between lambda, distortion D, and quantizer Q is determined by preliminary experimentation with multiple video images using a full optimization method at a wide range of lambda values. In these experiments it is often advantageous to keep the quantizer Q constant while varying the lambda Lagrange multipliers. If you keep the quantizer Q constant in each experiment, the end result is a family of R,D curves, one curve for each different value of quantizer Q. Figure 4 depicts an example of such a family of R, D curves. For each different constant Q curve, at a particular {R, D} point obtained by some value of lambda, the slope of the curve is (-lambda). The optimal {R, D} relationship is obtained by extracting the minimum of all R, D curves.

Thereafter, for each different quantizer Q value, a typical lambda value such as lambda _Q is selected. For example, lambda _Q may be a value that provides a distortion D value in the halfway portion between the intersection points of Q+1 and Q-1 of FIG. 4 . Other methods used to select typical lambda values include lambda _Q =0.85Q ² and lambda _Q =0.85×2 ^Q/3 . For multiple bidirectional pictures, a larger value of lambda _Q is usually chosen. Thus, we have

lambda _Q = f(Q)

D _Q = g(Q) from which Q = h(D _Q ) can be obtained

Then to encode a sequence of video images with the expected distortion D, the closest D _Q can be found first, from which Q=h(D _Q ) can be obtained. The video image is then encoded with the corresponding lambda _Q = f(Q), which provides an optimal bit rate R for the distortion _DQ .

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. As with most rate control algorithms, the usual approach is to change the quantizer Q from pixel blocks to pixel blocks and/or from video image to video image. When there is a sign that the encoder buffer may become too full (and possibly overflow), the value of the quantizer Q is increased to decrease the bit rate R. When the encoder buffer is likely to run out (and will likely underflow), the value of the quantizer Q is decreased to increase the bit rate R.

However, a change in the value of the quantizer Q may result in too large a change in the bit rate R. Furthermore, changes in the Q value of the quantizer need to be signaled to the decoder, which increases the amount of additional bits that must be transmitted to the decoder. Also, changing the quantizer Q may have other effects on video image quality such as in-loop filtering.

An alternative to changing the quantizer Q in order to obtain the desired rate control is to change the Lagrangian multiplier lambda. Smaller values of Lagrange multiplier lambda result in larger bitrate R (and smaller distortion D), likewise larger values of Lagrange multiplier lambda reduce bitrate R (and increase distortion D ). The variation in the Lagrangian multiplier lambda can be arbitrarily small, as opposed to the variation in the quantizer Q which is digitized and coded so that the quantizer Q is limited to certain values. In many digital video compression and coding systems, including all MPEG video compression and coding standards, not all integer values of the quantizer Q are allowed to be sent, in which case sudden changes in the bit rate R can be more significant.

When the Lagrangian multiplier lambda is required to be greater than a certain threshold lambda_max(Q) to obtain a certain amount of bit rate reduction, the quantizer Q will increase, and using the newly increased quantizer Q value, the Lagrange multiplier The lambda will return its nominal value f(Q). When the Lagrangian multiplier lambda is required to be less than a certain threshold lambda_min(Q) to obtain a certain bit rate increase, the quantizer Q will be reduced, and with the newly reduced quantizer Q, the Lagrange multiplier lambda will return its nominal value f(Q).

The values of lambda_max(Q) and lambda_min(Q) are determined by the intersection point on the bit rate-distortion relationship in Figure 4. If D(lambda, Q) is determined to be the distortion obtained when encoding with the Lagrangian multiplier lambda and the quantizer step size Q, the operational relation is:

D(lambda_min(Q+1), Q+1)=D(lambda_max(Q), Q)

lambda_min(Q)<=f(Q)<=lambda_max(Q)

The detailed operation of such a rate control algorithm for a video coding system is set forth in the following pseudocode:

Start_encoding_picture: //Start encoding video image

** input desired D; // get the expected distortion D value

find D _Q nearest to D; //Find the D _Q value closest to the expected D value

Q=h(D _Q ); //Determine the quantizer value Q

Lambda＝f(Q); //Determine the Lagrangian multiplier lambda

start_encoding_pixelblock: //Start encoding pixel block from the image

code_pixelblock(lambda, Q);//Use lambda and Q to encode the pixel block

if(encoder_buffer＞Tfull){ //Is there any sign of buffer overflow?

Lambda＝lambda+deltalambda; //deltalambda can depend on the threshold Q

If(lambda＞Lambda_max(Q)){ //If lambda is too large, increase Q

       Q＝Q+deltaQ;                                

Lambda＝f(Q); //Set the new Lagrangian multiplier lambda

}

}

if(encoder_buffer<Tempty){ //Is there any sign of underflow in the buffer?

Lambda = lambda-deltalambda; // yes, so reduce lambda

If(Lambda<Lambda_min(Q)){ //If lambda is too small, reduce Q

      Q＝Q-deltaQ;                                              

Lambda＝f(Q); //Set a new Lagrangian multiplier lambda

}

}

if(not last pixelblock) then goto start_encoding_pixelblock;//Then process the image

Variations of the usual bitrate control algorithm can include various thresholds for the encoder buffer value, whereby if the encoder buffer exceeds the Tfull threshold by a large amount, it can immediately Increase the quantizer Q. Similarly, if the encoder buffer is significantly below the Tempty threshold, the quantizer Q can be reduced immediately. Alternatively, the step size of delta lambda can be increased if the encoder buffer exceeds the Tfull threshold greatly or falls well short of the Tempty threshold.

The values of Deltalambda and deltaQ can vary with quantizer Q or with video picture type (single picture, picture-in-picture or bidirectional picture). Also, the operation of increasing the Lagrangian multiplier lambda can be replaced by multiplication, which can change the Lagrangian multiplier lambda by a certain percentage. For example, the Lagrangian multiplier lambda can be varied using the following equation for the operation of increasing lambda:

Lambda＝(1+delta lambda)×lambda

Similarly, the following equation can be used to reduce the lambda operation

Lambda＝(1-delta lambda)×lambda

This simple rate control algorithm describes different lambdas for this application. Other more complex rate control algorithms have also been devised and these other rate control algorithms may also benefit from different Lagrangian multipliers lambda.

Visual Distortion Tradeoff

Another application of the different Lagrangian multipliers lambda is in the use of visual distortion criteria. The distortion D is usually measured by summing the squared error between the original pixel value and the decoded pixel value. However, this simple measure of distortion does not do a good job of adjusting for the actual visibility of pixel errors in video images. Thus, such a simple distortion measurement method can make the prior minimization yield less than optimal results. Thus, algorithms that take subjective effects into account are often more useful.

The visibility of coding noise can be taken into account by computing a visual masking value M for each pixel block or sub-block to be coded in the video image. The visual masking value M is based on the spatial and temporal variables of the pixels within the region.

A larger visual masking value M indicates a larger masking, which makes the distortion more difficult to detect visually. In such regions, the distortion D can be increased and the bit rate R can be decreased. This is conveniently done using M*lambda (Lagrangian multiplier) instead of only Lagrangian multiplier lambda in the coding optimization algorithm. The pseudocode below describes the modified algorithm.

Start_encoding_picture://Start encoding video image

  input desired D//Get the expected distortion D value

find D _Q nearest to D;//Find the D value closest to the expected D value

Qnorm=h(D _Q )//determine normal Q without masking

   lambda＝f(Qnorm);//Determine the Lagrangian multiplier lambda

start_encoding_pixelblock: //Start encoding the pixel block from the image

  Q = Qnorm; //Set Q to normal Q without masking

Calculate visual mask M;//Determine the amount of visual masking

  while(M×lambda＞Lambda_max(Q))//{If there is strong masking,

Increase Q

     Q＝Q+deltaQ;//Increase the Q step size of the quantizer

}

  code pixelblock((M×lambda, Q)//use M×lambda and Q to encode

If(encoder_buffer＞Tfull){ //Is there any sign of buffer overflow?

Lambda＝lambda+deltalambda; //increase lambda

If(lambda＞Lambda_max(Q)){ //Test lambda

    Qnorm＝Qnorm+deltaQ; //If lambda is too large, increase Q

`` lambda=f(Qnorm); //calculate new lambda

}

}

If(encoder_buffer<Tempty){ //Is there any sign of underflow in the buffer?

Lambda=lambda-deltalambda;//decrease lambda

If(Lambda<Lambda_min(Qnorm)){ //Test lambda

     Qnorm＝Qnorm-deltaQ;//If lambda is too small, reduce Q

Lambda＝f(Qnorm);//Calculate new lambda

}

}

if(not last pixelblock) then goto start_encoding_pixelblock;//Then process the image

The second simple visual masking algorithm describes the use of different lambdas for this application. Other more complex visual masking algorithms have also been devised and these other visual masking algorithms may also benefit from different Lagrangian multipliers lambda.

Variations of the Lagrangian multiplier lambda may also be useful in other coding decisions. For example when encoding a sequence of video images, it is often very difficult to determine how many bidirectional pictures to encode. For a specific value of quantizer Q and lambda _Q = f(Q), the encoding result of one bidirectional picture per picture-in-picture can be R ₁ , D ₁ , and the encoding result of two bidirectional pictures per picture-in-picture can be R ₂ , D ₂ .

If R ₂ < R ₁ and D ₂ < D ₁ , then obviously the best answer is that two bidirectional pictures are better. However, it often turns out that R ₂ < R ₁ and D ₂ > D ₁ , so it is not clear that the number of bidirectional pictures is better. In this case, we can re-encode using two bidirectional pictures per picture-in-picture with a smaller lambda given D ₂ approximately equal to D ₁ . We can then simply compare the resulting value _R2 with _R1 to see which has the lower bit rate.

Other schemes can be similarly compared, such as interleaved coding versus continuous coding, coding of different motion search ranges, coding with or without a certain coding mode, and so on.

In summary, we provide a simple yet effective approach to the rate-distortion tradeoff, which has diverse applications in video coding. The above describes a system for controlling the rate-distortion trade-off through coding mode selection in a multimedia compression and coding system. It is expected that those of ordinary skill in the art may make changes and modifications in the materials and configuration of the elements of the invention without departing from the scope of the invention.

Claims (14)

1. A method of controlling rate-distortion in a video compression and coding system, said method comprising: Select the distortion value D around the expected distortion value; using said distortion value D to determine a quantizer value Q; Computing a Lagrangian multiplier lambda using said quantizer value Q; encoding pixel blocks using said Lagrangian multiplier lambda and said quantizer value Q; When the occupancy value of the buffer area exceeds the overflow threshold, increase the Lagrangian multiplier lambda, and when the Lagrangian multiplier lambda exceeds the maximum lambda threshold, increase the quantizer value Q, wherein said buffer area is used to store the digital bit stream; and When the occupancy value of the buffer area falls below the underflow threshold, reduce the Lagrangian multiplier lambda, and when the Lagrangian multiplier lambda falls below the minimum lambda threshold, reduce The quantizer value Q. 2. The method according to claim 1, further comprising recalculating the Lagrangian multiplier lambda when the quantizer value Q is adjusted. 3. The method of claim 1, wherein, depending on the quantizer value Q, the Lagrangian multiplier lambda is increased or decreased by an amount. 4. A method of controlling rate-distortion in a video compression and coding system, said method comprising: Select the distortion value D around the expected distortion value; using said distortion value D to determine a quantizer value Q; Computing a Lagrangian multiplier lambda using said quantizer value Q; encoding pixel blocks using said Lagrangian multiplier lambda and said quantizer value Q; For the pixel block, calculating a visual masking value M based on the temporal and spatial variables of the pixels in the pixel block to quantify the visual masking of the pixel block, wherein the visual masking of the pixel block the visibility of coding noise representing the pixel block; and The quantizer value Q is increased when the visual masking value M multiplied by the Lagrangian multiplier lambda is greater than a maximum threshold of the Lagrangian multiplier lambda. 5. The method according to claim 4, wherein the minimum threshold value lambda_min based on the first quantizer value Q+1 and based on the second The maximum threshold lambda_max for the quantizer value Q, where the bitrate-distortion relationship is expressed by: D(lambda_min(Q+1), Q+1)=D(lambda_max(Q), Q). 6. The method of claim 4, further comprising: When the occupancy value of the buffer area exceeds the overflow threshold, increase the Lagrangian multiplier lambda, and when the Lagrangian multiplier lambda exceeds the maximum lambda threshold, increase the quantizer value Q, wherein said buffer area is used to store the digital bit stream; and When the occupancy value of the buffer area falls below the underflow threshold, reduce the Lagrangian multiplier lambda, and when the Lagrangian multiplier lambda falls below the minimum lambda threshold, reduce The quantizer value Q. 7. The method according to claim 6, further comprising recalculating the Lagrangian multiplier lambda if the quantizer value Q is adjusted. 8. An apparatus for controlling rate distortion, the apparatus comprising: means for selecting a distortion value D around an expected distortion value; means for determining a quantizer value Q using said distortion value D; means for calculating a Lagrangian multiplier lambda using said quantizer value Q; means for encoding a block of pixels using said Lagrangian multiplier lambda and said quantizer value Q; Used to increase the Lagrangian multiplier lambda when the occupancy value of the buffer exceeds the overflow threshold, and increase the quantizer value Q when the Lagrange multiplier lambda exceeds the maximum lambda threshold means, wherein the buffer area is used to store a digital bit stream; and Used for reducing the Lagrangian multiplier lambda when the occupancy value of the buffer zone falls below the underflow threshold, and when the Lagrangian multiplier lambda falls below the minimum lambda threshold, means for decreasing said quantizer value Q. 9. The apparatus of claim 8, further comprising: means for recomputing said Lagrangian multiplier lambda when said quantizer value Q is adjusted. 10. The apparatus of claim 8, wherein depending on the quantizer value Q, the Lagrangian multiplier lambda is increased or decreased by an amount. 11. An apparatus for controlling rate distortion, the apparatus comprising: means for selecting a distortion value D around an expected distortion value; means for determining a quantizer value Q using said distortion value D; means for calculating a Lagrangian multiplier lambda using said quantizer value Q; means for encoding a block of pixels using said Lagrangian multiplier lambda and said quantizer value Q; For said pixel module, calculate the visual masking value M based on the temporal variable and spatial variable of the pixels in said pixel module to quantify the visual masking means of said pixel module, wherein said pixel module the visual mask represents the visibility of coding noise for the pixel block; and means for increasing said quantizer value Q when said visual masking value M multiplied by said Lagrangian multiplier lambda is greater than a maximum threshold of said Lagrangian multiplier lambda. 12. The apparatus according to claim 11 , wherein the minimum threshold lambda_min based on the first quantizer value Q+1 and based on the second The maximum threshold lambda_max for the quantizer value Q, where the bitrate-distortion relationship is expressed by: D(lambda_min(Q+1), Q+1)=D(lambda_max(Q), Q). 13. The apparatus of claim 11, further comprising: A device for increasing the Lagrangian multiplier lambda when the occupancy value of the buffer exceeds an overflow threshold, and increasing the quantizer value Q when the Lagrangian multiplier lambda exceeds a maximum lambda threshold , wherein the buffer area is used to store a digital bit stream; and Used for reducing the Lagrangian multiplier lambda when the occupancy value of the buffer area falls below the underflow threshold, and reducing the Lagrangian multiplier lambda when the Lagrange multiplier lambda falls below the minimum lambda threshold means for small the quantizer value Q. 14. The apparatus of claim 13, further comprising: means for recomputing said Lagrangian multiplier lambda when said quantizer value Q is adjusted.

Images