CN102833538B - Multi-pass video encoding - Google Patents

Abstract

Some embodiments of the invention provide a multi-pass encoding method that encodes several images (e.g., several frames of a video sequence). The method iteratively performs an encoding operation that encodes these images. The encoding operation is based on a nominal quantization parameter, which the method uses to compute quantization parameters for the images. During several different iterations of the encoding operation, the method uses several different nominal quantization parameters. The method stops iterations when it reaches a terminating criterion (e.g., it identifies an acceptable encoding of the images).

Description

Multi-pass Video Coding

This application is a divisional application of an invention patent application with an application date of June 24, 2005, an application number of 200580006363.5, and an invention title of "multi-channel video coding".

Background technique

A video encoder encodes a sequence of video images (eg, video frames) by utilizing various encoding schemes. Video coding schemes typically encode video frames or portions of video frames (eg, sets of pixels within a video frame) in an intraframe or interframe manner. Intra-coded frames or sets of pixels are encoded independently of other frames or sets of pixels within other frames. An inter-coded frame or set of pixels is encoded by reference to one or more other frames or sets of pixels within other frames.

When compressing video frames, some encoders implement a "rate controller" that provides a "bit budget" for the video frame or set of video frames to be encoded. The bit budget specifies the number of bits that have been allocated to encode the video frame or set of video frames. By efficiently allocating the bit budget, the rate controller attempts to generate the highest quality compressed video stream taking into account certain constraints (eg target bitrate, etc.).

So far, various single-pass and multi-pass rate controllers have been proposed. A single-pass rate controller provides a bit budget for encoding schemes that encode a series of video images in a single pass, while a multi-pass rate controller provides a bit budget for encoding schemes that encode a series of video images in multiple passes.

Single-pass rate controllers are effective under real-time encoding conditions. Multipass rate controllers, on the other hand, optimize encoding for a specific bitrate based on a set of constraints. To date, not many rate controllers take into account the spatial or temporal complexity of a frame or pixel set within a frame in controlling their bit rate. Also, most multi-pass rate controllers do not adequately search the solution space for encoding solutions that use optimal quantization parameters for frames and/or sets of intra-frame pixels taking into account the desired bit rate.

Therefore, there is a need in the art for a rate controller using novel techniques to take into account the spatial or temporal complexity of video images and/or portions of video images while controlling the bit rate used to encode a set of video images . There is also a need in the prior art for a multi-pass rate controller that adequately examines various coding schemes to identify the coding scheme that uses the optimal set of quantization parameters for a video image and/or portions of a video image.

Contents of the invention

Some embodiments of the invention provide a multi-pass encoding method for encoding multiple images (eg, multiple frames of a video sequence). The method repeatedly performs the encoding operation for encoding these images. The encoding operation is based on a nominal quantization parameter, which is used by the method to calculate the quantization parameters of the images. During several different iterations of the encoding operation, the method uses several different nominal quantization parameters. The method stops its iterative process when a termination criterion is reached (eg, it identifies an acceptable image encoding).

Some embodiments of the invention provide a method for encoding a video sequence. The method identifies a first property that quantifies complexity of a first image in the video. It also identifies a quantization parameter for encoding the first image based on the identified first property. The method then encodes a first image based on said identified quantization parameters. In some embodiments, this method performs these three operations for multiple images in the video.

Some embodiments of the invention encode a sequence of video images based on a "visual masking" property of the video images and/or portions of the video images. The visual masking of an image or portion of an image is an indication of how much coding artifact can be tolerated in the image or portion of an image. To express the visual masking properties of an image or portions of an image, some embodiments calculate a visual masking strength that quantifies the luminance energy of the image or portions of an image. In some embodiments, the luminance energy is measured as a function of the average luma or pixel energy of the image or portions of the image.

Instead of or in combination with this luminance energy, the visual masking strength of the image or portions of the image can also quantify the activity energy of the image or portions of the image. Activity energy represents the complexity of the image or parts of the image. In some embodiments, activity energy includes a spatial component quantifying the spatial complexity of an image or parts of an image, and/or a motion component quantifying the amount of distortion that can be tolerated/masked due to movement between images.

Some embodiments of the invention provide a method for encoding a video sequence. The method identifies visual masking properties of a first image in a video. It also identifies quantization parameters for encoding the first image based on the identified visual masking properties. The method then encodes a first image based on said identified quantization parameters.

Description of drawings

The novel features of the invention are set forth in the appended claims. For purposes of explanation, however, various embodiments of the invention are set forth in the following figures.

Fig. 1 has given the process of conceptually illustrating the encoding method of some embodiments of the present invention;

Figure 2 conceptually illustrates the codec system of some embodiments;

Figure 3 is a flowchart illustrating an encoding process of some embodiments;

Figure 4a is a graph of the difference between the nominal removal time and final arrival time of a picture versus the number of pictures illustrating an underflow condition in some embodiments;

Figure 4b illustrates a graph of the difference between the nominal removal time and final arrival time versus the number of pictures for the same picture as shown in Figure 4a after eliminating the underflow condition;

Figure 5 illustrates a process used by an encoder to perform underflow detection in some embodiments;

Figure 6 illustrates the process used by an encoder to eliminate an underflow condition in a single segment of a picture in some embodiments;

Figure 7 illustrates the application of buffer underflow management in video streaming applications;

Figure 8 illustrates the application of buffer underflow management in HD-DVD system.

FIG. 9 shows a computer system with which an embodiment of the present invention is implemented.

Detailed ways

In the following detailed description of the invention, numerous details, examples and embodiments of the invention are presented and described. It is, however, clear and obvious to a person skilled in the art that the invention is not limited to the described embodiments and that the invention may be practiced without some of the specific details and examples discussed.

I. Definition

This section provides definitions for several symbols used in this document.

RT stands for Target Bit Rate, which is the desired bit rate for encoding a sequence of frames. Typically, this bit rate is expressed in bits per second and is calculated from the desired final file size, the number of frames in the sequence, and the frame rate.

Rp represents the bit rate of the coded bit stream at the end of path p.

Ep represents the percentage error in the bit rate at the end of pass p. In some cases, this percentage is calculated as

ε represents the tolerance range of errors in the final bit rate.

ε _C represents the error tolerance in the bit rate for the first QP search stage.

QP stands for quantization parameter.

QP _Nom(p) represents the nominal quantization parameter used in pass p encoded for the sequence of frames. The value of QP _{Nom (p)} is adjusted by the inventive multi-pass encoder in the first QP adjustment stage to achieve the target bit rate.

MQP _p (k) represents the masked frame QP, which is the quantization parameter (QP) of frame k in pass p. Some embodiments calculate this value by utilizing the nominal QP and frame-level visual masking.

MQP _MB(p) (k,m) stands for masked macroblock QP, which is the quantization parameter (QP) of a single macroblock (with macroblock index m) of frame k and pass p. Some embodiments compute MQP _MB(p) (k,m) by utilizing MQP _p (k) and macroblock-level visual masking.

φ _F (k) represents a value that becomes the masking strength of frame k. The masking strength φ _F (k) is a measure of complexity for that frame, and in some embodiments, this value is used to determine how visual coding artifacts/noise will appear and to compute the MQP _p (k) for frame k.

φ _R(p) represents the reference shielding strength in path p. This reference masking strength is used to compute the MQP _p (k) for frame k, and it is adjusted in the second stage by the inventive multi-pass encoder to reach the target bitrate.

φ _MB (k,m) represents the masking strength of the macroblock with index m in frame k. The masking strength φ _MB (k,m) is a measure of the complexity of the macroblock, and in some embodiments it is used to determine how visual coding artifacts/noise will appear and to calculate the MQP _MB(p) (k , m). AMQPp represents the average masked QP over frames in pass p. In some embodiments, this value is calculated as the average MQP _p (k) over all frames in pass p.

II. Overview

Some embodiments of the invention provide encoding methods that achieve the best visual quality for encoding a sequence of frames at a given bit rate. In some embodiments, the method uses a visual masking process that assigns a quantization parameter QP to each macroblock. This assignment is based on the recognition that coding artifacts/noise in brighter or spatially complex regions of an image or video frame are less pronounced than in darker or planar regions.

In some embodiments, this visual masking process is performed as part of the inventive multi-pass encoding process. Such an encoding process adjusts the nominal quantization parameter and controls the visual masking process by referring to the masking strength parameter _φR in order to achieve the target bitrate for the final encoded bitstream. As described further below, adjusting the nominal quantization parameter and controlling the masking algorithm adjusts the QP value per picture (ie, typically each frame in a video coding scheme) and per macroblock within each picture.

In some embodiments, the multi-pass encoding process globally adjusts the nominal QP and φ _R for the entire sequence. In other embodiments, this process divides the video sequence into slices, adjusting each slice with a nominal QP and _φR . The following description relates to a sequence of frames on which the multi-pass encoding process is applied. Those of ordinary skill will appreciate that in some embodiments this sequence includes the entire sequence, while in other embodiments it includes only a fragment of the sequence.

In some embodiments, the method has three encoding stages. The three phases are: (1) the initial analysis phase performed in pass 0, (2) the first search phase performed in pass 1 to pass N ₁ , and (3) in pass N ₁ + 1 to N ₁ The second search phase performed in +N ₂ .

In the initial analysis phase (ie, during pass 0), the method identifies an initial value for a nominal QP (QP _Nom(1) , to be used in pass 1 of the encoding). During the initial analysis phase, the method also identifies the value of the reference masking strength _φR , which is used in all passes in the first search phase.

In the first search phase, the method performs _N1 iterations (ie, _N1 passes) of the encoding process. For each frame k in pass p, the process encodes the frame by using a specific quantization parameter MQP _p (k) and a specific quantization parameter MQP _MB(p) (k,m) for each macroblock m within frame k, where This MQP _MB(p) (k,m) is calculated using MQP _p (k).

In the first search stage, the quantization parameter MQP _p (k) is varied between passes as it is derived from the nominal quantization parameter QP _{Nom (p) that} is varied between passes. In other words, at the end of each pass p during the first search phase, the process calculates a nominal QP _{Nom(p+1) for pass p+1} . In some embodiments, the nominal QP _Nom(p+1) is based on nominal QP values and bit rate errors from previous passes. In other embodiments, the nominal QP _{Nom (p+1)} value is calculated differently at the end of each pass in the second search phase.

In the second search phase, the method performs _N2 iterations (ie, _N2 passes) of the encoding process. As in the first search stage, the process is performed in each pass p by using the specific quantization parameter MQP _p (k) and the specific quantization parameter MQP _MB(p) (k,m) Each frame k is coded during, where MQP _{MB (p)} (k,m) is obtained from MQP _p (k).

Also, as in the first search phase, the quantization parameter MQP _p (k) varies between passes. However, during the second search phase, this parameter changes because it is calculated using a reference masking strength φ _R(p) that varies between passes. In some embodiments, the reference masking strength φ _R(p) is calculated based on errors in the bit rate and φ _R values from previous passes. In other embodiments, the reference masking strength is calculated as a different value at the end of each pass in the second search phase.

Although the multi-pass encoding process is described in conjunction with the visual masking process, one of ordinary skill in the art will appreciate that the encoder need not use these two processes together at the same time. For example, in some embodiments, by ignoring _φR and omitting the second search stage described above, a multi-pass encoding process is used to encode bitstreams around a given target bitrate without visual masking.

The visual masking and multi-pass encoding process is further described in Sections III and IV of this application.

III. Visual Masking

Given a nominal quantization parameter, the visual masking process first computes the masked frame quantization parameter (MQP) for each frame using the reference masking strength (φ _R ) and the masking strength of this frame (φ _F ). The process then calculates the masked macroblock quantization parameter (MQP _MB ) for each macroblock based on the frame and macroblock level masking strengths (φ _F and φ _MB ). When applying the visual masking process in a multi-pass encoding process, the reference masking strength (φ _R ) in some embodiments is identified in the first encoding pass as described above and further below.

A. Calculating frame-level shielding strength

1. The first method

To calculate the frame-level masking strength φ _F (k), some embodiments use the following formula (A):

φ _F (k) = C*power(E*avgFrameLuma(k),β)*power(D*avgFrameSAD(k), _αF ), (A)

in:

●avgFrameLuma(k) is the frame k calculated using the bxb area

Average pixel intensity, where b is an integer greater than or equal to 1 (for example, b=1 or b=4);

●avgFrameSAD(k) is the average value of MbSAD(k,m) of all macroblocks in frame k;

MbSAD(k,m) is the sum of the values of all 4x4 blocks in the macroblock with index m given by the function Calc4x4MeanRemovedSAD(4x4_block_pixel_value);

● α _F , C, D, and E are constant and/or adjusted according to local statistics; and

● power (a, b) means a ^b .

The pseudocode for the function Calc4x4MeanRemovedSAD is as follows:

2. The second method

Other embodiments calculate frame-level masking strengths differently. For example, the above formula (A) basically calculates the frame masking strength as follows:

φ _F (k)＝C*power(E*Brightness_Attribute,exponent0)*

power(scalar*Spatial_Activity_Attribute,exponentl)

In formula (A), the Brightness_Attribute of a frame is equal to avgFrameLuma(k), and the Spatial_Activity_Attribute is equal to avgFrameSAD(k), which is the average macroblock SAD (MbSAD(k,m)) value of all macroblocks in the frame, where the average The macroblock SAD is equal to the sum of the absolute values of the mean removed 4x4 pixel changes (as given by Calc4x4MeanRemovedSAD) of all 4x4 blocks within the macroblock. The Spatial_Activity_Attribute measures the amount of spatial correction in the region of pixels within the frame being encoded.

Other embodiments extend the activity metric to include the number of temporal corrections in a pixel region across many consecutive frames. In particular, these embodiments compute the frame masking strength as follows:

φ _F (k)＝C*power(E*Bfightness_Attribute,expouent0)*

power(scalar*Activity_Attribute, exponentl) (B)

In this formula, Activity_Attribu is given by the following formula (C):

E*power(F*Temporal_Activity_Attribuc, exponent_delta)(C)

In some embodiments, the Temporal_Activity_Attribute quantifies the amount of distortion due to motion between frames that can be tolerated (ie masked). In some of these embodiments, the Temporal_Activity_Attribute of a frame is equal to a constant multiple of the sum of absolute values of motion compensation error signals for pixel regions defined within the frame. In other embodiments, Temporal_Activity_Attribute is provided by the following formula (D):

$\mathrm{<span\; class="notranslate">\; Temporal</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; Activity</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; Attribute</span>}<span\; class="notranslate">\; =</span>$

$\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; avgFrameSAD</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; avgFrameSAD</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; avgFrameSAD</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; )</span>$

In formula (D), "avgFrameSAD" represents (as above) the average macroblock SAD (MbSAD(k,m)) value within a frame, avgFrameSAD(0) is the avgFrameSAD of the current frame, and the negative j points to the current frame A previous time instance, while a positive j points to a time instance after the current frame. Thus, avgFrameSAD (j=-2) represents the average frame SAD of two frames before the current frame, and avgFrameSAD (j=3) represents the average frame SAD of three frames after the current frame.

Also, in formula (D), the variables N and M refer to the number of frames before and after the current frame, respectively. Instead of simply selecting the values N and M based on a particular number of frames, some embodiments calculate the values N and M based on a particular time period before or after the time of the current time frame. Associating a motion mask with a spatial duration is more advantageous than associating a motion mask with a set number of frames. This is because associating moving masks with time periods directly corresponds to the observer's time-based visual perception. On the other hand, associating such masking with the number of frames suffers from variable display durations since different display devices render video at different frame rates.

In formula (D), "W" refers to a weighting factor which, in some embodiments, decreases as frame j moves further away from the current frame. Also, in this formula, the first sum represents the amount of movement that can be masked before the current frame. The second sum represents the amount of movement that can be masked after the current frame, while the final expression (avgFrameSAD(0)) represents the frame SAD of the current frame.

In some embodiments, weighting factors are adjusted to account for scene changes. For example, some embodiments address an upcoming scene change within the lookahead range (ie, within M frames), but not any frames after the scene change. For example, these embodiments may set the weight factors of frames in the look-ahead range after a scene change to zero. Also, some embodiments do not address frames that precede or lie within a look-back range (ie, within N frames) of a scene change. For example, these embodiments may set the weighting factor to zero for frames that refer to the previous scene or fall within the look-behind range before the previous scene change.

3. Variation of the second method

a) Limit the influence of past frames and future frames on Temporal_Activity_Attribute

The above formula (D) basically expresses Temporal_Activity_Attribute from the following conditions:

Temporal_Activity_Attribute = Past_Frame_Activity + Future_Frame_Activity +

Current_Frame_Activity,

Here Past_Frame_Activity(PFA) is equal to Future_Frame_Activity (FFA) is equal to And Current_Frame_Activity (CFA) is equal to avgFrameSAD (current).

Some embodiments modify the calculation of Temporal_Activity_Attribute so that neither Past_Frame_Activity nor Future_Frame_Activity over-dominates the value of Temporal_Activity_Attribute. For example, some embodiments initially define PFA equal to $\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}(W_i\&Center\; Dot;\mathrm{avgFrameSAD}\left(i\right)),$ while FFA is equal to $\underset{j=1}{\overset{m}{\mathrm{\&Sigma;}}}(W_j\&Center\; Dot;\mathrm{avgFrameSAD}\left(j\right)).$

These embodiments then determine whether PFA is greater than scalar time FFA. If so, these embodiments set the PFA equal to the upper PFA value (eg, scalar time FFA). In addition to setting PFA equal to the upper PFA value, some embodiments may perform a combined setting of FFA to zero and CFA to zero. Other embodiments may set one or both of PFA and CFA as a weighted combination of PFA, CFA, and FFA.

Similarly, after initially defining the PFA and FFA values based on the weighted sum, some embodiments also determine whether the FFA value is greater than the scalar time PFA. If so, these embodiments set the FFA equal to the FFA upper limit (eg, scalar time PFA). In addition to setting FFA equal to the upper FFA value, some embodiments may perform a combined setting of PFA to zero and CFA to zero. Other embodiments may set one or both of FFA and CFA as a weighted combination of FFA, CFA, and PFA.

Potential subsequent adjustments of the PFA and FFA values (after the initial estimation of these values based on a weighted sum) prevent either of these values from overdoing the Temporal_Activity_Attribute.

b) Limiting the influence of Spatial_Activity_Attribute and Temporal_Activity_Attribute on Activity_Attribute The above formula (C) basically expresses Activity_Attribute from the following conditions: Activity_Attribute=Spatia_Activity+Temporal_ctivity

Among them, Spatial_Activity is equal to scalar*(scalar*Spatial_Activity_Attribute) ^β , and Temporal_Activity is equal to scalar*(scalar*Temporal_Activity_Attribute) ^Δ .

Some embodiments modify the calculation of Activity_Attribute so that neither Spatial_Activity nor Temporal_Activity overdominates the value of Activity_Attribute. For example, some embodiments initially define Spatial_Activity(SA) equal to scalar*(scalar*Spatial_Activity_Attribute) ^β , and define Temporal_Activity(TA) equal to scalar*(scalar*Temporal_Activity_Attribute) ^Δ .

These embodiments then determine whether it is greater than a scalar time TA, and if so, these embodiments set SA equal to an upper SA value (eg, a scalar time TA). In addition to the case where SA is set equal to the SA upper limit, some embodiments may also set the TA value to zero or to a weighted combination of TA and SA.

Similarly, after initially defining SA and TA values based on exponential equations, some embodiments also determine whether the TA value is greater than a scalar time SA. If so, these embodiments set TA equal to the TA ceiling value (eg, scalar time SA). In addition to the case where TA is set equal to the TA upper limit, some embodiments may also set the SA value to zero or to a weighted combination of SA and TA.

Potential subsequent adjustments of the SA and TA values (after the initial calculation of these values based on exponential equations) prevent excessive domination of the Activity_Attribute by one of these values.

B. Calculation of macroblock-level masking strength

1. The first method

In some embodiments, the macroblock-level masking strength φ _MB (k,m) is calculated as follows:

φ _MB (k, m) = A*power(C*avgMbLuma(k, m), β)*power(B*MbSAD(k, m), α _MB ), (F)

in:

avgMbLuma(k,m) is the average pixel intensity within frame k, macroblock m; α _MB , β, A, B, and C are constants and/or fit local statistics.

2. The second method

Formula (F) described above basically calculates the macroblock masking strength as follows:

φ _MB (k, m) = D*power(E*Mb_Brightness_Attribute, exponent0)*

power(scalar*Mb_Spatial_Activity_Attribute, cxponentl)

In formula (F), Mb_Brightness_Attribute of a macroblock is equal to avgMbLuma(k, m), and Mb_Spatial_Activity_Attribute is equal to avgMbSAD(k). The Mb_Spatial_Activity_Attribute measures the amount of spatial modification in the area of pixels within the macroblock being coded.

As in the case of frame masking strength, some embodiments may expand the activity metric in macroblock masking strength to include the number of temporal corrections in pixel regions across many consecutive frames. In particular, these embodiments will calculate the macroblock masking strength as follows:

φ _MB (k, m) = D*power(E*Mb_Brightness_Attribute, exponent0)*

power(scalar*Mb_Activity_Attribute, exponentl), (G)

where Mb_Activity_Attribute is given by the following formula (H):

Mb_Activity_Attribute＝F*power(D*Mb_Spatial_Activity_Attribute,exponent_beta)+

G*power(F*Mb_Temporal_Activity_Attribute,exponent_dclta)(H)

The calculation of Mb_Temporal_Activity_Attribute of a macroblock may be similar to the calculation of Mb_Temporal_Activity_Attribute of a frame described above. For example, in some of these embodiments, Mb_Temporal_Activity_Attribute is provided by the following formula (1):

$\mathrm{<span\; class="notranslate">\; MB</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; Temporal</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; Activity</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; Attribute</span>}<span\; class="notranslate">\; =</span>$

$\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; MbSAD</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; MbSAD</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; MbSAD</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; )</span>$

The variables in formula (I) are defined in Section III. In formula (F), macroblock m in frame i or j may be a macroblock in the same position as macroblock m in the current frame, or may be a frame initially predicted to correspond to macroblock m in the current frame macroblock in i or j.

The Mb_Temporal_Activity_Attribute provided by Equation (I) may be modified in a similar manner to the modification of the frame Temporal_Activity_Attribute provided by Equation (D) (discussed in Section III.A.3 above). In particular, the Mb_Temporal_Activity_Attribute provided by formula (I) can be modified to limit the excessive influence of macroblocks in past and future frames.

Similarly, the Mb_Activity_Attribute provided by Equation (H) may be modified in a manner similar to the modification of the Frame Activity_attribute provided by Equation (C) (discussed in section above). In particular, Mb_Activity_Attribute provided by formula (H) can be modified to limit the excessive influence of Mb_Spatial_Activity_Attribute and Mb_Temporal_Activity_Attribute.

C. Calculating masked QP values

Based on the masking strength (φ _F and φ _MB ) values and the reference masking strength (φ _R ) value, the visual masking process can calculate frame-level and macroblock-level masking QP values by using two functions CalcMQP and CalcMQPforMB. The pseudocode of these two functions is as follows:

In the above functions, β _F and β _MB can be preset constants or suitable for local statistics.

IV. Multi-pass encoding

Figure 1 shows a process 100, which conceptually illustrates the multi-pass encoding method of some embodiments of the present invention. As shown in the figure, process 100 has three phases, described in the following three sections.

A. Analysis and Initial QP Selection

As shown in Figure 1, the process 100 initially calculates initial values for the reference masking strength (φ _R(1) ) and the nominal quantization parameter (QP _{Nom (1 )} ) initial value (step 105). The initial reference strength (φ _R(1) ) is used during the first search stage, while the initial nominal quantization parameter (QP _Nom(1) ) is used during the first pass of the first search stage (i.e., the during pathway 1).

At the beginning of pass 0, φ _R(0) may be some arbitrary value or a value chosen based on experimental results (eg, the middle value of a typical range of φ _R values). During the analysis of the sequence, the masking strength φ _F (k) is calculated for each frame, then at the end of pass 0 the reference masking strength φ _{R(1 )} is set equal to avg(φ _F (k)). Other determinations of the reference shielding strength φ _R are also possible. For example, it may calculate an intermediate value or other arithmetic function as a value φ _F (k), such as a weighted average of the values φ _F (k).

There are several approaches to initial QP selection with varying complexity. For example, the initial nominal QP can be chosen as an arbitrary value (eg 26). Alternatively, known values may be chosen based on encoding experiments to produce acceptable quality for the target bitrate.

An initial nominal QP value may also be selected from a look-up table based on spatial resolution, frame rate, space/time complexity, and target bitrate. In some embodiments, this initial nominal QP value is selected from a table using a distance metric dependent on each of these parameters, or it may be selected using a weighted distance metric for these parameters.

This initial nominal QP value can also be set as an adjusted average of the frame QP values as they were chosen during fast encoding using the rate controller (without masking), where this average has been based on the bitrate percent rate error for lane 0 E ₀ adjustment. Similarly, the initial nominal QP can also be set as a weighted adjusted average of frame QP values, where each frame's weight is determined by the percentage of macroblocks in that frame that are not coded as skipped macroblocks. Optionally, the initial nominal QP can be set as an adjusted average or adjusted weighted average of the frame QP values as they are chosen during fast encoding using the rate controller (with masking), taking into account the reference masking strength from φ The effect of changing _R(0) to _φR(1) .

B. Fast Search Phase: Nominal QP Adjustment

After step 105, the multi-pass encoding process 100 enters the first search phase. In the first search stage, process 100 performs _N1 encoding of the sequence, where _N1 represents the number of passes through the first search stage. During each pass of the first stage, the process uses a varying nominal quantization parameter with a constant reference masking strength.

In particular, during each pass p of the first-level search phase, the process 100 computes (step 107) the specific quantization parameter MQP _p (k) for each frame k, and computes the Specific quantization parameters MQP _MB(p) (k,m). The calculation of the parameters MQP _p (k) and MQP _{MB (p)} (k,m) given the nominal quantization parameter QP _{Nom (p)} and the reference masking strength φ _{R (p)} is described in Section III (where MQP _p (k) and MQP _MB(p) (k,m) are calculated by using the functions CalcMQP and CalcMQPforMB, which are described in Section III above). In the first pass (i.e., pass 1) through step 107, the nominal quantization parameter and the first-stage reference masking strength are the parameter QP _Nom(1) and the reference masking strength φ _R(1) , which were obtained in the preliminary analysis stage 105 period calculation.

After step 107, the process encodes the sequence based on the quantization parameter values calculated at step 107 (step 110). Next, the encoding process 100 determines whether it should end (step 115). Different embodiments have different conditions for ending the entire encoding process. Examples of exit conditions that completely end the multipass encoding process include:

• |Ep|<ε, where ε is the error tolerance in the final bit rate.

●QP _{Nom (p)} is the upper boundary and lower boundary of the valid range of QP value.

• The number of paths exceeds the allowed maximum number of paths P _MAX .

Some embodiments may use all of these exit conditions, while other embodiments may only use some of them. However other embodiments may use other exit conditions for ending the encoding process.

When the multi-pass encoding process decides to end (step 115 ), process 100 omits the second search stage and moves to step 145 . At step 145, the process saves the bitstream from the last pass p as the final result and ends.

On the other hand, when the process determines (step 115 ) that it cannot end, it then determines (step 120 ) whether the first search phase should end. Also, different embodiments have different conditions for ending the first search phase. Examples of exit conditions that end the first search phase of the multi-pass encoding process include:

• QP _Nom(p+1) is the same as QP _Nom(q) , and q≤p, (in this case, the error in the bit rate cannot be further reduced by modifying the nominal QP).

●|Ep|< _εc , _εc >ε, where _εc is the error tolerance range in the bit rate of the first search stage.

• The number of paths has exceeded P ₁ , where P ₁ is less than P _MAX .

• The number of paths has exceeded P ₂ , which is smaller than P ₁ , and |Ep|<ε ₂ , ε ₂ >ε _C .

Some embodiments may use all of these exit conditions, while other embodiments may only use some of them. However other embodiments may use other exit conditions for ending the first search phase.

When the multi-pass encoding process decides (step 120) to end the first search phase, the process 100 proceeds to the second search phase, which is described in the following sections. On the other hand, when the process determines (step 120) that it should not end the first search phase, it updates (step 125) the nominal QP of the next pass in the first search phase (i.e., defines QP _{Nom(p+ 1)} ). In some embodiments, the nominal QP _Nom(p+1) is updated as follows. At the end of Passage 1, these examples define:

QP _Nom(p+1) =QP _Nom(p) +χE _p ,

where χ is a constant. At the end of each pass from pass 2 to pass N ₁ , these embodiments then define:

QP _Nom(p+1) = InterpExtrap(0, E _q1 , E _q2 , QP _Nom(q1) , QP _Nom(q2) ),

where InterpExtrap is a function as further described below. Likewise, in the above formula, q1 and q2 correspond to the number of paths with the lowest bit error among all paths up to path p, and q1, q2 and p have the following relationship:

1≤q ₁ <q ₂ ≤p

The following is the pseudocode of the InterpExtrap function. Note that if x is not between x1 and x2, this function is an extrapolation function. Otherwise, it is an interpolation function.

Nominal QP values are usually rounded to integer values and limited to the valid range of QP values. One of ordinary skill in the art will recognize that other embodiments may calculate the nominal QP _Nom(p+1) in a different way than that described above.

After step 125, the process transfers back to step 107 to start the next pass (i.e., p:=p+1), and for this pass, the specific quantization parameter MQP _p (k ), and a specific quantization parameter MQP _MB(p) (k,m) for each individual macroblock m within frame k (step 107). Next, the process encodes the sequence of frames based on these newly calculated quantization parameters (step 110). The process then transitions from step 110 to step 115, which has been described above.

C. Second search stage: reference shielding strength adjustment

When process 100 determines that it should end the first search phase (step 120 ), it transfers to step 130 . In the second search stage, process 100 performs _N2 encoding of the sequence, where _N2 represents the number of passes through the second search stage. The process uses the same nominal quantization parameters and varying reference masking strengths during each pass.

At step 130, process 100 calculates the reference shielding strength φ _R(p+1) for the next pass, pass p+1, which is pass N ₁ +1 . In pass N ₁ +1 , process 100 encodes a sequence of frames in step 135 . Different embodiments calculate the reference shielding strength φ _R(p+1) (step 130 ) at the end of pass p in different ways. Two alternative implementation methods are described below.

Some embodiments calculate the reference masking strength φ _R(p) based on the error in the bit rate and the value of φ _R from previous passes. For example, at the end of path _N1 , some embodiments define:

φ _R(N1+1) ＝φ _R(N1) +φ _R(N1) × Konst × E _N1

At the end of the path N1+m, where m is an integer greater than 1, some embodiments define

φ _R(N1+m) ＝ InterpExtrap(0, E _N1+m-2 , E _N1+m-1 , φ _R(N1+m-2) , φ _R(N1+m-1) )

Alternatively, some embodiments define:

φ _R(N1+m) ＝ InterpExtrap(0, E _N1+m-q2 , E _N1+m-q1 , φ _R(N1+m-q2) , φ _R(N1+m·q1) )

where q1 and q2 are the paths that gave the optimal error before.

Other embodiments compute the reference masking strength at the end of each pass in the second search phase by utilizing AMQP, which is defined in Section I. The following describes one way of computing AMQP given a nominal QP and some value of _φR with reference to the pseudocode of the function GetAvgMaskedQP:

Some embodiments using AMQP calculate the desired AMQP for pass p+1 based on the error in the bit rate from the previous pass and the value of AMQP. The φ _R(p+1) corresponding to this AMQP is then found by the search procedure given by the function Search(AMQP _(p+1) , φ _R(p) ), the pseudocode of which is given at the end of this section out.

For example, some embodiments compute AMQP _N1+1 at the end of pass _N1 , where:

AMQP _N1+1 = InterpExtrap(0, E _N1-1 , E _N1 , AMQP _N1-1 , AMQP _N1 ), when N ₁ >1,

and

AMQP _N1+1 =AMQP _N1 , when N ₁ =1,

These examples then define:

φ _R(N1+1) ＝Search(AMQP _N1+1 ，φ _R(N1) )

At the end of the path N ₁ +m (where m is an integer greater than 1), some embodiments define:

AMQP _N1+m = InterpExtrap(0, E _N1+m-2 , E _N1+m-1 , AMQP _N1+m-2 , A·MQP _N1+m-1 ),

as well as

φ _R(N1+m) ＝Search(AMQP _N1+m ，φ _R(N1+m-1) )

Given the desired AMQP and some default values for _φR , _φR corresponding to the desired AMQP can be found using the Search function, which in some embodiments has the following pseudocode:

In the pseudocode above, the numbers 10, 12 and 0.05 can be replaced with appropriately chosen thresholds.

After calculating the reference masking strength for the next pass (pass p+1) through the sequence of encoded frames, the process 100 moves to step 132 and starts the next pass (ie, p:=p+1). During each encoding pass p, for each frame k and each macroblock m, the process computes the specific quantization parameter MQP _p (k) for each frame k and the specific quantization parameter MQP for the individual macroblock m in frame k _MB(p) (k,m) (step 132). The calculation of the parameters MQP _p (k) and MQP _{MB (p)} (k,m) given the nominal quantization parameter QP _{Nom (p)} and the reference masking strength φ _{R (p)} is described in Section III (where MQP _p (k) and MQP _MB(p) (k, m) are calculated by utilizing the functions CalcMQP and CalcMQPforMB, which are described in Section III above). During the first pass through step 132 , the reference shielding strength is exactly the value calculated at step 130 . Also, during the second search phase, the nominal QP remains constant throughout the second search phase. In some embodiments, the nominal QP within the second search phase is the nominal QP obtained by the optimal encoding solution (ie, in the encoding solution with the lowest bit rate error) during the first search phase.

After step 132, the process encodes the sequence of frames using the quantization parameters calculated at step 130 (step 135). After step 135, the process determines (step 140) whether the second search phase should end. Different embodiments use different conditions for ending the first search phase at the end of pass p. Examples of such conditions are:

• |Ep|<ε, where ε is the error tolerance in the final bit rate.

• The number of paths exceeds the allowed maximum number of paths P _MAX .

Some embodiments may use all of these exit conditions, while other embodiments may only use some of them. However other embodiments may use other exit conditions for ending the first search phase.

When the process 100 determines (step 140) that the second search phase should not end, it returns to step 130 to recalculate the reference masking strength for the next encoding pass. The process moves from step 130 to step 132 to calculate a quantization parameter, and then to step 135 to encode the video sequence by using the newly calculated quantization parameter.

On the other hand, when the process decides (step 140 ) to end the second search phase, then it transfers to step 145 . At step 145, the process 100 saves the bitstream from the last pass p as the final result, and then ends.

V. Decoder input buffer underflow control

Some embodiments of the invention provide a multi-pass encoding process that examines various encodings of a video sequence against a target bitrate, in order to identify an optimal encoding scheme with respect to the usage of the input buffer used by the decoder. In some embodiments, this multi-pass process follows the multi-pass encoding process 100 of FIG. 1 .

Decoder input buffers ("decoder Buffer") usage varies to some extent during the decoding of a sequence of encoded pictures (eg, frames).

Decoder buffer underflow is important in cases where the decoder is ready to decode the next picture before the picture has fully arrived at the decoder side. The multi-pass encoder of some embodiments simulates a decoder buffer and re-encodes selected segments in the sequence to prevent decoder buffer underflow.

Figure 2 conceptually illustrates an encoding system 200 of some embodiments of the invention. The system includes a decoder 205 and an encoder 210 . In this figure, encoder 210 has a number of components that enable it to simulate the operation of similar components of decoder 205 .

In particular, the decoder 205 has an input buffer 215 , a decoding process 220 , and an output buffer 225 . Decoder 210 simulates these modules by maintaining simulated decoder input buffer 230 , simulated decoding process 235 , and simulated decoder output buffer 240 . In order not to obstruct the description of the present invention, FIG. 2 is simplified to show decoding process 220 and encoding process 245 as a single block. Also, in some embodiments, analog decoding process 235 and analog decoder output buffer 240 are not utilized for buffer underflow management and are thus illustrated in this figure by way of example only.

The decoder maintains an input buffer 215 to smooth out rate and time-of-arrival variations of incoming encoded pictures. If the decoder runs out of data (underflow) or fills up the input buffer (overflow), there will be visual decoding interruptions such as picture decoding interruption or input data being discarded. Both of these situations are undesirable.

To eliminate the underflow condition, encoder 210 first encodes the sequence of images and stores them to memory 255 in some embodiments. For example, the encoder 210 uses the multi-pass encoding process 100 to obtain a first encoding of the sequence of images. It then simulates the decoder input buffer 215 and re-encodes images that may cause buffer underflow. After all buffer underflow conditions have been eliminated, the re-encoded image is provided to decoder 205 via connection 255, which can be a network connection (Internet, cable, PSTN line, etc.), non-network direct connection, media (DVD, etc. )wait.

Figure 3 illustrates an encoding process 300 of an encoder of some embodiments. This process attempts to find the optimal encoding scheme that does not cause the decoder buffer to underflow. As shown in FIG. 3 , process 300 identifies (step 302 ) a first encoding of a sequence of images that meets a desired target bitrate (eg, an average bitrate of each image in the sequence that meets a desired average target bitrate). For example, process 300 may use (step 302 ) the multi-pass encoding process 100 to obtain a first encoding of a sequence of images.

After step 302, the encoding process 300, by considering various factors such as the connection speed (i.e., the speed at which the decoder is used to receive encoded data), the size of the decoder input buffer, the size of the encoded image, the speed of the decoding process, etc., Vary the analog decoder input buffer 215 (step 305). At step 310, process 300 determines whether any segment of the encoded image would cause the decoder input buffer to underflow. The technique used by the encoder to determine (and subsequently eliminate) an underflow condition is described further below.

If the process 300 determines (step 310) that the encoded picture did not cause an underflow condition, the process ends. On the other hand, if the process 300 determines (step 310) that a buffer underflow condition exists in any segment of the encoded image, it refines the encoding parameters based on the values of these parameters from the previous encoding pass (step 315). The process then re-encodes (step 320) the segment with underflow to reduce the bit size of the segment. After re-encoding the segment, process 300 checks (step 325) the segment to determine if the underflow condition has been eliminated.

When the process determines (step 325) that the segment would still result in underflow, process 300 moves to step 315 to further refine the encoding parameters to eliminate underflow. Optionally, when the process determines (step 325) that the segment does not result in any underflow, the process designates (step 330) the starting point for re-examining and re-encoding the video sequence as the last iteration of step 320 Frame after the end of the re-encoded segment in . Next, at step 335 , the process re-encodes the portion of the video sequence specified at step 330 up to (and excluding) the first IDR frame following the underflow segment specified at steps 315 and 320 . After step 335, the process transfers back to step 305 to simulate the decoder buffer to determine whether the remaining video sequence will still cause buffer underflow after re-encoding. The flow of the process 300 starting from step 305 has been described above.

A. Determining Underflow Fragments in an Encoded Image Sequence

As described above, the encoder simulates decoder buffer conditions to determine whether any segment in the sequence of encoded or re-encoded pictures would cause an underflow in the decoder buffer. In some embodiments, the encoder uses a per-image display time, etc.) of the simulation model.

In some embodiments, decoder input buffer conditions are simulated using the MPEG-4 AVC Coded Picture Buffer (CPB) model. CPB is a term used in the MPEG-4H.264 standard to refer to the analog input buffer of the ideal reference decoder (HRD). The HRD is an ideal decoder model that specifies constraints on the variability of the eligible data streams that the encoding process may produce. The CPB model is well known and is described in Section 1 below for convenience. A more detailed description of CPB and HRD can be found in the draft ITU-T recommendation and the final draft of the International Standard of Joint Video Specification (ITU-TRec.H.264/ISO/IEC14496-10AVC).

1. Simulate the decoder buffer using the CPB model

The following paragraphs describe how the CPB model is used to simulate the decoder input buffer in some embodiments. The time at which the first bit of image n starts to enter the CPB is called the initial arrival time t _ai (n), which is derived as follows:

t _ai (0)=0, when the image is the first image (ie, image 0);

●t _ai (n)=Max(t _af (n-1), t _ai , earliest(n)), when the image is not regular

When the first image in the encoded or re-encoded sequence (i.e., n>0).

In the above formula:

t _ai , earliest(n)=t _{r, n} (n)-initial_cpb_removal_delay,

where t _r,n (n) is the nominal removal time for picture n to be removed from the CPB as specified below, and initial_cpb_removal_delay is the initial buffering period.

The final arrival time of image n is derived by the following formula:

t _af (n)=t _ai (n)+b(n)/BitRate,

where b(n) is the size of image n in bits.

In some embodiments, the encoder does its own calculation of the nominal removal time as described below, rather than reading from an optional part of the bitstream as in the H.264 specification. For image 0, the nominal removal time for image removal from the CPB is specified as:

t _{r, n} (0) = initial_cpb_removal_delay

For image n (n>0), the nominal removal time for image removal from the CPB is specified as:

t _r,n (n)=t _r,n (0)+sum _{i=0 to n-1} (ti)

where t _r,n (n) is the nominal removal time of image n, and t _i is the display duration of picture i.

The removal time for image n is specified as follows:

●t _r (n)=t _{r, n} (n), when t _{r, n} (n)>=t _af (n),

●t _r (n)=t _af (n), when t _r,n (n)<t _af (n)

The latter case indicates that the size b(n) of image n is so large that it prevents removal at the nominal removal time.

2. Detection of underflow fragments

As described in the previous section, the encoder is able to simulate the decoder input buffer state and fetch the number of bits in the buffer at an immediate given time instant. Optionally, the encoder can keep track of how each individual image traveled through the difference between its nominal removal time and final arrival time (i.e., t _b (n) = t _{r, n} (n) - t _af ( n)) to change the decoder input buffer state. When t _b (n) is less than 0, the buffer will be between time instants t _r,n (n) and t _af (n), and may be before t _r,n (n) and t _af (n ) then encounters underflow.

Images that fall directly into underflow can be easily found by testing whether t _b (n) is less than zero. However, an image with t _b (n) smaller than 0 does not necessarily lead to underflow, and conversely, t _b (n) of an image that leads to underflow does not necessarily have to be smaller than 0. Some embodiments define an underflow segment as the stretch of consecutive pictures (in decoding order) that cause underflow by continuously draining the decoder input buffer until the underflow reaches its lowest point.

Figure 4 is a graph of the difference between nominal removal time and final arrival time for image t _b (n) versus number of images in some embodiments. The curve is plotted for a sequence of 1500 encoded images. Figure 4a illustrates an underflow segment whose start and end are marked with arrows. Note that another underflow segment occurs after the first underflow segment in Fig. 4a, which is not clearly marked with an arrow for simplicity.

FIG. 5 illustrates a process 500 for an encoder to perform the underflow detection operation at step 305 . Process 500 first determines (step 505 ) the final arrival time t _af and nominal removal time t _r,n for each picture by simulating decoder input buffer conditions as explained above. Note that since this process may be called several times in an iterative process of buffer underflow management, it receives the image number as a starting point and starts checking the sequence of images from this given starting point. Obviously, for the first iteration, the starting point is the first image in the sequence.

At step 510, process 500 compares, by the decoder, the final arrival time of each picture at the decoder's input buffer to the nominal removal time for that picture. If the process determines that there are no images with a final arrival time after the nominal removal time (ie, no underflow condition exists), the process exits. On the other hand, when an image is found whose final arrival time is after the nominal removal time, the process determines that underflow exists and branches to step 515 to identify underflow segments.

At step 515, process 500 identifies an underflow segment as a segment of the picture where the decoder buffer begins to drain continuously until the next global minimum, at which point the underflow condition begins to improve (i.e., t _b (n) during picture stretching no more negative values). Process 500 then exits. In some embodiments, the start of the underflow segment is further adjusted to start with an I-frame, which is an intra-coded picture marking the start of a group of related intra-coded pictures. Once one or more underflow-causing fragments have been identified, the encoder proceeds to eliminate the underflow. Section B below describes underflow elimination for the single-segment case (ie, when the encoded entire image sequence contains only a single underflowed segment). Section C then describes underflow cancellation for the case where multiple fragments underflow.

B. Single Fragment Underflow Elimination

Referring to Figure 4(a), if the curve of _tb (n) versus n has a downward slope and crosses the n-axis only once, then there is only one underflow segment in the entire sequence. The underflow segment starts at the nearest local maximum of the previous zero crossing and ends at the next global minimum point between the zero crossing and the end of the sequence. If the buffer recovers from underflow, the end point of the segment can follow another zero-crossing point of a curve with a rising slope.

Figure 6 illustrates a process 600 used by a decoder (steps 315, 320 and 325) to eliminate underflow conditions within a single slice of a picture in some embodiments. At step 605, process 600 estimates the amount to reduce within the underflow segment by calculating the output of the input bitrate into the buffer and the longest delay found at the end of the segment (e.g., minimum _tb (n)). Total number of bits (ΔB).

Next, at step 610, process 600 estimates the desired AMQP to achieve the desired number of bits for the segment using the average masked frame QP (AMQP) and the total number of bits in the current segment from the previous encoding pass (or passes). , B _T =B-ΔB _p , where p is the current iteration number of the process 600 for this segment. If this iteration is the first iteration of process 600 for this particular segment, the AMQP and total number of bits is the AMQP and total number of bits identified at step 302 for that segment derived from the initial encoding solution. On the other hand, when the iteration is not the first iteration of the process 600, these parameters can be derived from the coded solution or the solution obtained in the last pass or passes of the process 600.

Next, at step 615 , the process 600 modifies the average masked frame QP, MQP( _{n) based on the masking strength φ F(n)} using the desired AMQP so that more masked images can tolerate more bit deductions. The process then re-encodes (step 620 ) the video segment based on the parameters defined at step 315 . The process then checks (step 625) the segment to determine if the underflow condition has been removed. Figure 4(b) illustrates the elimination of the underflow condition of Figure 4(a) after applying the process 600 to the underflow segment to re-encode it. The process exits when the underflow condition is removed. Otherwise, the process transfers back to step 605 to further adjust the encoding parameters to reduce the total bit size.

C. Underflow Elimination of Multiple Underflow Fragments

When there are multiple underflowing fragments in the sequence, the re-encoding of the fragments changes the buffer fullness time _tb (n) for all guaranteed frames. To account for the modified buffer condition, the encoder starts from the first zero-crossing point with a falling slope (i.e., at the nadir n) and searches for one underflow segment at a time.

The underflow segment starts at the nearest local maximum preceding the zero crossing and ends at the interval between the zero crossing and the next zero crossing (or at the end of the sequence if there are no more zero crossings). the next global minimum. After finding a segment, the encoder ideally removes the underflow within this segment and estimates an updated buffer fullness by setting _tb (n) to 0 at the end of the segment and re-running the buffer simulation for all sequence frames.

The encoder then proceeds to search for the next segment using the modified buffer fullness. Once all underflowing fragments are identified as described above, the encoder derives AMQP and modifies the masked frame QP of each fragment independently of the other fragments as in the case of a single fragment.

Those of ordinary skill will realize that other embodiments may be implemented in different ways. For example, some embodiments will not identify multiple fragments that cause the decoder's input buffer to underflow. Some embodiments will instead perform a buffer simulation as described above to identify the first fragment that caused the underflow. After identifying such a segment, the embodiments modify the segment to correct the underflow condition within that segment, and then proceed to perform subsequent encoding of the corrected portion. After encoding the remainder of the sequence, these embodiments will repeat this process for the next underflow segment.

D. Application of buffer underflow management

The decoder buffer underflow technique described above is used in many encoding and decoding systems. Several examples of such systems are described below.

Figure 7 illustrates a network 705 connecting a video streaming server 710 with several client decoders 715-725. Clients connect to network 705 through links with different bandwidths, such as 300Kb/sec and 3Mb/sec. Video streaming server 710 controls the streaming of encoded video images from encoder 730 to client decoders 715-725.

A streaming video server can decide to stream encoded video images using the lowest bandwidth in the network (ie, 300Kb/s) and smallest client buffer size. In this case, the streaming server 710 only needs a set of encoded images optimized for a target bitrate of 300Kb/sec. On the other hand, the server can generate and store different encodings optimized for different bandwidths and different client buffer conditions.

Figure 8 illustrates another application example of decoder underflow management. In this example, HD-DVD player 805 receives encoded video images from HD-DVD 840 that has stored encoded video data from video encoder 810. The HD-DVD player 805 has an input buffer 815 , a set of decoding modules shown as one component 820 for simplicity, and an output buffer 825 .

The output of the player 805 is sent to a display device such as a TV 830 or a computer display terminal 835. HD-DVD players can have very high bandwidth, eg 29.4Mb/sec. In order to maintain a high quality image on a display device, the encoder ensures that the video images are encoded in such a way that there are no fragments of the image sequence that are too large to be delivered to the decoder input buffer on time.

VI. Computer system

Figure 9 illustrates a computer system implementing an embodiment of the present invention. Computer system 900 includes bus 905 , processor 910 , system memory 915 , read only memory 920 , persistent storage 925 , input device 930 , and output device 935 . The bus 905 collectively represents all the system, peripheral, and chipset busses that seamlessly connect the numerous internal devices of the computer system 900 . For example, bus 905 fluidly connects processor 910 with read only memory 920 , system memory 915 , and persistent storage device 925 .

To perform the various processes of the present invention, processor 910 retrieves instructions to be executed and data to be processed from these various memory locations. Read Only Memory (ROM) 920 stores static data and instructions needed by processor 910 and other modules of the computer system.

Persistent storage device 925, on the other hand, is a read-write memory device. This device is a non-volatile memory unit that stores instructions and data even when computer system 900 is off. Some embodiments of the invention use mass storage devices such as magnetic or optical disks and their corresponding disk drives as persistent storage 925 .

Other embodiments use removable storage devices, such as floppy disks or compact disks, and their corresponding disk drives, as permanent storage. Like persistent storage 925, system memory 915 is a read-write memory device. However, unlike the storage device 925, the system memory is a non-permanent read-write memory, such as random access memory. System memory stores some instructions and data needed by the processor at runtime. In some embodiments, various processes of the present invention are stored in system memory 915 , persistent storage 925 , and/or read-only memory 920 .

Bus 905 is also connected to input and output devices 930 and 935 . Input devices enable a user to communicate information with and select commands to the computer system. Input device 930 includes an alphanumeric keypad and a cursor controller. The output device 935 displays images generated by the computer system. Output devices include printers and display devices such as cathode ray tubes (CRT) or liquid crystal displays (LCD).

Finally, as shown in FIG. 9, the bus 905 also connects the computer 900 to the network 965 through a network adapter (not shown). In this manner, the computer may be part of a computer network, such as a local area network ("LAN"), wide area network ("WAN"), or intranet, or part of a network of networks, such as the Internet. Any or all components of computer system 900 may be used in conjunction with the present invention. However, one of ordinary skill in the art will understand that any other system configuration may also be used in conjunction with the present invention.

Although the invention has been described with reference to various specific details, those skilled in the art will recognize that the invention may be practiced in other specified ways without departing from the spirit of the invention. For example, instead of using the H264 method that simulates the input buffer of the decoder, other simulation methods that take into account the size of the buffer, the arrival and removal times of images in the buffer, and the number of decoding and display times of the images can also be used.

The various embodiments described above calculate the average removed SAD to obtain an indication of image variation in a macroblock. However, other embodiments may identify image changes in different ways. For example, some embodiments may predict expected image values for pixels of a macroblock. These embodiments then generate the macroblock SAD by subtracting the predicted value from the luminance values of the pixels of the macroblock and adding the absolute value of the subtracted portion. In some embodiments, the predictive value is based not only on pixel values within the macroblock, but also on pixel values within one or more neighboring macroblocks.

Also, the embodiments described above directly use the derived spatial and temporal masking values. Other embodiments apply smoothing filtering to these values before using them in order to pick out general trends in continuous spatial mask values and/or continuous temporal mask values among video images. Thus, it will be understood by those of ordinary skill in the art that the invention is not limited to the details set forth above.

Claims (28)

1. An apparatus for encoding a plurality of images, said apparatus comprising: In the first stage involving the first multiple encoding passes: means for defining a nominal quantization parameter for encoding said image; means for deriving at least one image-specific quantization parameter for at least one image based on said nominal quantization parameter; means for encoding said picture based on said picture-specific quantization parameter; and means for iteratively performing said defining, deriving and encoding operations to optimize said encoding, wherein said iteratively performing said defining comprises changing said nominal quantization after each encoding pass of a first plurality of encoding passes parameters; and In a second stage comprising a second plurality of coding passes: means for defining a reference masking strength for encoding said image; means for deriving at least one image-specific quantization parameter for at least one image based on a reference masking strength used to quantify the complexity of said plurality of images; means for encoding the plurality of pictures based on picture-specific quantization parameters derived for the second stage; and means for iteratively performing said defining, deriving and encoding operations to optimize said encoding, wherein said iteratively performing said defining comprises changing said reference masking strength after each encoding pass of a second plurality of encoding passes . 2. The apparatus according to claim 1, further comprising means for stopping said iterations when the encoding operation satisfies a set of termination criteria. 3. The apparatus of claim 2, wherein said set of termination criteria includes an identification of an acceptable encoding of said image. 4. The apparatus of claim 3, wherein said acceptable encoding of said image is an encoding of an image within a certain target bitrate range. 5. An apparatus for encoding a plurality of images, said apparatus comprising: means for identifying a plurality of image attributes, each particular image attribute quantifying at least the complexity of a particular portion of a particular image, wherein each of said image attributes is an indication of how much can be tolerated in said image or a portion of said image Encoding the strength of visual masking artifacts; means for identifying a reference attribute quantifying the complexity of the plurality of images; means for identifying quantization parameters for encoding said plurality of pictures based on the identified picture properties, said reference property and a nominal quantization parameter; means for encoding the plurality of images based on the identified quantization parameters; and Means for iteratively performing said identifying and encoding operations to optimize said encoding, wherein a plurality of different iterations use a plurality of different reference attributes. 6. The apparatus of claim 5, wherein in indicating the complexity of the portion of the image, the visual masking strength quantifies an amount of distortion that can be tolerated due to movement between images. 7. A method of iteratively encoding a video sequence comprising a plurality of images using a plurality of encoding passes, the method comprising: specifying, by the video encoder, a first nominal quantization parameter for the first encoding pass; During the first encoding pass, each picture is encoded by (i) using the first nominal quantization parameter to generate a first picture-specific quantization for the picture during the first encoding pass parameter, and (ii) encoding said picture based on said first picture-specific quantization parameter; specifying a second nominal quantization parameter different from said first nominal quantization parameter for a second coding pass; and During the second encoding pass, each picture is encoded by (i) using the second nominal quantization parameter to generate a second picture-specific quantization for the picture during the second encoding pass parameter, and (ii) encode the picture based on the second picture-specific quantization parameter, wherein, for each picture in a set of pictures, the second quantization parameter specified during the second encoding pass is specific to The quantization parameter of the picture is different from the first picture-specific quantization parameter specified during said first encoding pass. 8. The method of claim 7, further comprising stopping the encoding pass when an acceptable encoding for the plurality of images is identified. 9. The method of claim 8, wherein said acceptable encoding of said plurality of images is an encoding of said images within a particular target bitrate range for encoding said video sequence. 10. The method of claim 7, wherein said image-specific quantization parameters of an image are derived based on average pixel intensities in said image. 11. The method of claim 7, wherein said image-specific quantization parameter of an image is derived based on a power function of the average pixel intensity in said image. 12. The method according to claim 7, wherein an image comprises groups of pixels, wherein said image-specific quantization parameter of an image is based on a sum of absolute differences (SAD) of pixel values of all groups of pixels in said image derived from the power function of the mean. 13. The method of claim 7, wherein the image-specific quantization parameter of an image is derived based on a temporal attribute quantifying an amount of distortion that can be tolerated due to movement between images. 14. The method of claim 7, wherein said image-specific quantization parameter of an image is derived based on a sum of absolute values of motion compensation error signals for a plurality of pixel regions defined in said image. 15. The method according to claim 7, wherein said image-specific quantization parameter of the current image is derived based on: the mean value of the sum of absolute differences (SAD) of the pixel values of the current image, temporally The average of the sum of absolute differences (SAD) of pixel values of a group of images preceding the current image and the sum of absolute differences of pixel values of a group of images temporally subsequent to the current image (SAD) mean. 16. A method of iteratively encoding a video sequence comprising a plurality of images using a plurality of encoding passes, the method comprising: defining, by the video encoder, a first nominal quantization parameter for the first encoding pass; identifying a first coding scheme for said video sequence by performing a quantization operation on each picture using picture-specific quantization parameters derived for each particular picture from said first nominal quantization parameter; identifying a second nominal quantization parameter for a second encoding pass based on the first nominal quantization parameter for the first encoding pass; and Identifying a second coding scheme for said video sequence by performing a quantization operation on each picture using picture-specific quantization parameters derived for each specific picture from said second nominal quantization parameter, wherein said video sequence of Each encoding scheme comprises encoding for each picture in said video sequence, wherein said first encoding scheme assigns for each picture in a set of pictures in said video sequence the same as said second encoding scheme different encoding. 17. The method of claim 16, further comprising stopping said iterating upon identifying an acceptable encoding for said plurality of images. 18. The method of claim 16, wherein said second nominal quantization parameter is also based on measurements taken during said first encoding pass. 19. The method of claim 18, wherein an acceptable encoding of the image is an encoding of the image that is within a particular target bitrate range for encoding the plurality of images. 20. The apparatus according to claim 16 , wherein said image-specific quantization parameter for each particular image is derived based on: the mean value of the sum of absolute differences (SAD) of pixel values of said particular image, The average of the sum of absolute differences (SAD) of pixel values of a group of images temporally preceding the particular image, and the absolute difference of pixel values of a group of images temporally subsequent to the particular image The average of the sum (SAD). 21. A method of encoding a video sequence comprising a plurality of images using multiple coding passes, the method comprising: specifying, by the video encoder, a first reference masking strength for the first encoding pass; During the first encoding pass, each picture is encoded by (i) using the first reference masking strength and a picture-specific visual masking strength to generate a picture-specific quantization parameter, the picture-specific The visual masking strength quantifies the amount of encoding artifacts that will be perceptible in the image, and (ii) performs quantization on the image using the image-specific quantization parameters generated during the first encoding pass operate to encode the image; assigning a second reference masking strength different from said first reference masking strength for a second encoding pass; and During said second encoding pass, each picture is encoded by (i) generating a picture-specific quantization parameter using said second reference masking strength and a picture-specific visual masking strength for said picture, and (ii) encoding said image by performing a quantization operation on said image using said image-specific quantization parameter generated during said second encoding pass, wherein, for a group of images in said video sequence For each picture of , the picture-specific quantization parameter produced during said second encoding pass is different from the picture-specific quantization parameter produced during said first encoding pass. 22. The method of claim 21, wherein the second reference masking strength is based on an error in bit rate from the first encoding pass. 23. The method of claim 21, wherein said second reference masking strength is based on an average picture-specific quantization parameter over said plurality of pictures during said first encoding pass. 24. The method of claim 21, wherein the visual masking strength of each image is for a portion of the image that is less than the entire image. 25. The method of claim 21, wherein the visual masking strength of each image is for the entire image. 26. The method of claim 21, wherein the image-specific quantization parameters for each image are for a portion of the image that is less than the entire image. 27. The method of claim 21, wherein said picture-specific quantization parameters for each picture are for the whole picture. 28. An encoding device comprising means for performing the steps of the method according to any one of claims 7-27.