US 6,366,704 B1Grant

Method and apparatus for a delay-adaptive rate control scheme for the frame layer

Issue Date:2002-04-02

•12 Claims

•6 Drawing Sheets

Abstract

A digital video encoder and method for its operation are disclosed. This encoder comprises a frame-layer rate controller that bases a rate-distortion-optimized target bit assignment T_jon an energy estimate for frame j, an average energy estimate for a group of frames, and the desired overall bit rate. If the encoder uses motion compensation, motion bits used for frame j and an average motion bits estimate for a group of frames may also be used by the frame-layer rate controller. Preferably, the desired delay in the system affects how average estimates are computed by the encoder. The frame-layer rate controller of the video encoder above may also utilize buffer protection logic during target bit assignment. This logic adjusts an initial target bit assignment T_jbased on the transmission bit rate and desired delay. A primary benefit of the frame-layer rate controller disclosed herein is its basis in a rate-distortion optimal solution to the frame-layer rate control problem. Additional benefits are provided by the explicit consideration of buffer delay during selection of a target bit assignment: rate control robustness allows one controller to be used in a range of delay situations (or even a varying delay situation); and buffer underflow/overflow can be largely eliminated, even in very low delay implementations.

Metadata

Assignee

Sharp Laboratories of America, Inc.

Inventors

Jordi Ribas-Corbera
Shaw-Min Lei

Application Information

Application Number:US 09/192,831

Filing Date:1998-11-16

Priority Date:1997-12-01

Art Unit:7

Classifications

IPC:

G06K 936H04N 712

Field of Search:

382232382239382236382251382250375240043752400337524002375240013752401237524006375240247092473881093483841

Patent Drawings (6 sheets)

Description

[0002] This application claim benefit to provisional application No. 60/067,692 Dec. 1, 1997.

Field of the Invention

[0003] This invention pertains generally to digital video encoders, and more particularly to frame-adaptive bit rate control of such encoders.

Background of the Invention

[0004] Uncompressed video requires a relatively high transmission bandwidth. Almost all human-viewable video sequences, however, contain a large amount of redundant and/or visually unimportant information. Digital video allows the use of complex algorithms that remove redundant and relatively unimportant information from a digital video bitstream. With this information removed, video transmission bandwidth may be reduced to acceptable levels. A system that implements video compression algorithms is known as a digital video encoder.

[0005] FIG. 1 shows a digital video encoder 36 that employs motion compensation to reduce bandwidth. An image sequence 20, consisting of M frames F₁, F₂, . . . F_j, . . . F_M, provides the input to encoder 36. Motion compensator 24 is often crucial for effective bandwidth reduction. Motion compensator 24 produces a prediction frame {tilde over (F)}_jfor each input frame F_jby comparing regions of F_jto regions from previously encoded frames for similarity. To be more concrete, given a region in frame F_j, the encoder searches for regions in previously encoded frames that are good matches for such region and combines these good matches to form the region's prediction. Thus {tilde over (F)}_jrepresents an approximation of F_jbased on combinations and/or translations of regions of previously encoded frames. This approximated image can be encoded by merely sending the combination and/or translation instructions, or motion vectors MV_j, for frame j.

[0006] Before an image F_jis encoded, approximation {tilde over (F)}_jis subtracted from it in image summer 22. The remaining motion-compensated frame, i.e., the difference image F_j−{tilde over (F)}_j, represents the portion of the input image F_jframe that cannot be easily predicted from previous frames.

[0007] The motion-compensated frame is compressed to a target size of approximately T bits by image encoder 26. The motion vectors are likewise compressed in motion encoder 28. When the image sequence is to be transmitted directly to a viewer through channel or interface 34 without intermediate storage (e.g., storage to a disk or other storage media), a buffer 30 is often used to allow the “bursty” encoder outputs to be smoothly transmitted as bitstream 32.

[0008] At the receiving end of interface 34, bitstream 32 is received by a video decoder 38. Video decoder 38 often places bitstream 32 in a decoder buffer 47 and then parses bitstream 32 to a motion decoder 42 and an image decoder 40. Image summer 44 combines the output of decoders 40 and 42 to produce an output image sequence 46. Depending on whether image encoder 26 is lossless or lossy, output image sequence 46 may or may not be an exact representation of image sequence 20.

[0009] In a digital video encoder 36, and more specifically its embedded image coder 26, it is often preferable to vary the target size T from image frame to image frame. A process that varies T is known as a “frame-layer rate control.” A large body of work on frame-layer rate control has been reported in the patent and academic literature [1-14, Appendix A]. Typically, all of these methods decide the target number of bits for a frame using some formula that depends on the energy in that frame, the number of bits used for encoding previous frames, and the current fullness of the encoder buffer 30 (or that of the decoder buffer 47, which is equivalent since both buffers are related).

[0010] For example, the frame-layer rate control described in [1] uses a formula for the frame target that depends on the energy of the pixels in the frame and the number of bits used in a previous frame with similar energy. In [13], the energy and previous bits are combined in a different formula to select the target and in [14] such formula depends on the product of quantization values and bits used for a previous frame of the same type. In [3], the frame target depends on a formula that increases in inverse proportion to the fullness of the encoder buffer. Finally, the method in [12] assigns a fixed target number of bits per frame (equal to the channel rate divided by the frame rate) and skips frames when the encoder buffer is close to buffer overflow.

Summary of the Invention

[0011] Even though all frame-layer rate control techniques in the prior art measure similar parameters to determine the target number of bits for a frame [1-14], the formula or method chosen for combining these measurements is the key for an effective bit allocation. Typically, these formulas are ad hoc and are not optimized in a rate-distortion sense and, as a result, they do not minimize image distortion (i.e., maximize image quality) for the available bit rate. Additionally, the desired communication delay, which increases with the size of the encoder buffer, is not taken directly into account when deciding the frame target. At low delay, the latter produces large fluctuations of the fullness level in the encoder buffer that lead to undesired buffer overflow, underflow, and frame skipping.

[0012] The present invention provides a frame-layer rate control mechanism that is based on a rate-distortion optimization. And the present invention further teaches modifications to this basic mechanism that allow a digital video encoder rate controller to respond to differences in communication delay. In addition to the benefits of the rate-distortion optimal solution provided by the basic mechanism, these modifications add robustness to a rate controller, such that one controller can be used in a range of delay situations (or even a varying delay situation).

[0013] A digital video encoder is disclosed herein. This encoder comprises a frame-layer rate controller that bases a target bit assignment T_jon an energy estimate for frame j, an average energy estimate for a group of frames, and the desired overall bit rate. If the encoder uses motion compensation, motion bits used for frame j and an average motion bits estimate for a group of frames may also be used by the frame-layer rate controller. Preferably, the desired delay in the system affects how average estimates are computed by the encoder.

[0014] The rate controller of the video encoder above may also use buffer protection logic during target bit assignment. This logic corrects an initial target bit assignment T_j, based on the transmission bit rate, desired delay, and current buffer fullness.

[0015] In a further aspect of the invention, methods for combining the parameters and estimates described above are also disclosed. For example, an initial target bit assignment can be computed by multiplying the desired overall average bit assignment by the ratio of the frame energy estimate to the average energy estimate. Preferably, the average energy estimate is calculated by filtering frame energy estimates with a filter having a time constant dependent on the desired system delay.

Brief Description of the Drawing

[0016] The invention may be best understood by reading the disclosure with reference to the drawing, wherein:

[0017] FIG. 1 illustrates a block diagram of a prior art digital video encoder;

[0018] FIG. 2 shows a corresponding block diagram of a prior art digital video decoder;

[0019] FIG. 3 illustrates the concept of a block coder;

[0020] FIGS. 4-6 show suggested delay-adaptive relationships for several parameters of frame-adaptive bit rate control;

[0021] FIG. 7 shows a digital video encoder embodiment of the present invention; and

[0022] FIG. 8 shows the improvement in image quality in terms of PSNR (peak signal-to-noise ratio) obtained using frame layer rate control according to the present invention, in comparison to the frame layer rate control in [14].

Detailed Description of the Preferred Embodiments

[0023] A typical block-based image coder will be used to describe the following preferred embodiments. The present invention can, however, be used for assigning the target number of bits per frame within any image or video coder.

[0024] In block-based image coding, the image to be encoded is decomposed into image blocks of the same size, typically 16×16 pixels per block, and each block is encoded with bits using some coding technique, for example a DCT-based coder. FIG. 3 illustrates the process of encoding the ith block in the jth frame of a video sequence having M frames.

[0025] In FIG. 3, B_i,jis the number of bits produced when encoding the ith image block in the jth frame and D_i,jis the loss in quality or distortion introduced in that block. In many types of block coders, the distortion is controlled by the user with one or several parameters and is typically measured by computing the mean squared error (MSE) between the original and the encoded block. For example, in H.263 and MPEG encoders, the distortion at each image block is controlled by a parameter called the block's quantization step and the MSE distortion is proportional to the square of that parameter. Encoding a block with higher distortion (i.e., lower quality) produces fewer bits for the block. In other words, B_i,jdecreases with larger D_i,j. The present invention uses the following mathematical model for the relationship between B_i,jand D_i,j.

[0026] Bit-Distortion Model

[0027] U.S. patent application Ser. No. 09/008,137, filed Jan. 16, 1998, (now U.S. Pat. No. 6,111,991) by J. Ribas-Corbera and S. Lei, and incorporated herein by reference, discloses an analytical study of typical block-based coders, including formulas for the number of bits produced for a block (B_i,j) and the MSE distortion in the block (D_i,j), as a function of several parameters. A combination of these formulas expresses a direct relationship between B_i,jand D_i,j:

\begin{matrix} B_{i, j} = \frac{{AK}_{j}}{12} \frac{α_{i, j}^{2} σ_{i, j}^{2}}{D_{i, j}} + A C_{j}, & (1) \end{matrix}

[0028] where A is the number of pixels in an image block (e.g., in MPEG and H.263 A=16²pixels), K_jis a parameter that depends on the encoder's coding efficiency and frame pixels' distribution (K_jwill not be needed), C_jis the rate (in bits per pixel) of the motion and syntax in the jth frame, and σ_i,j²is the variance or energy of the pixels in the block, i.e.,

\begin{matrix} σ_{i, j}^{2} = \frac{1}{A} \sum_{l = 1}^{A} {(P_{i, j} (l) - {\overline{P}}_{i, j})}^{2}, & (2) \end{matrix}

[0029] where A is the number of pixels in a block, P_i,j(l) is the value of the l-th pixel in the block, and {overscore (P)}_i,jis the average of the pixel values in the block,

\begin{matrix} {\overline{P}}_{i, j} = \frac{1}{A} \sum_{l = 1}^{A} P_{i, j} (l) . & (3) \end{matrix}

[0030] For color images, the P_i,j(l)'s are the values of the luminance and chrominance components at the respective pixels. Finally, α_i,j²is a distortion weight chosen by the encoder designer (as described in U.S. patent application Ser. No. 09/008,137) and typically takes values between 1 and σ_i,j².

[0031] Equation (1) indicates that the number of bits B_i,jproduced when encoding the ith block (in the jth frame) is inversely proportional to the block's distortion D_i,j.

[0032] The Rate-Distortion Optimization Problem

[0033] Let N be the number of image blocks in a frame (with A pixels per block). Then, the total number of image blocks in the video sequence is MN, since there are M frames. We define the overall MSE distortion D as the average of the distortions for all the blocks, i.e.,

\begin{matrix} D = \frac{1}{MN} \sum_{j = 1}^{M} \sum_{I = 1}^{N} D_{i, j} = \frac{1}{MN} \sum_{j = 1}^{M} \sum_{i = 1}^{N} \frac{{AK}_{j}}{12} α_{i, j}^{2} \frac{σ_{i, j}^{2}}{(B_{i, j} - A C_{j})}, & (4) \end{matrix}

[0034] using the relationship between B_i,jand D_i,jfrom (1). Now, let T be the total number of bits available for the M frames and T_jthe number of bits for the jth frame. T is the sum of the bits for the frames or, equivalently, the sum of the bits for all the blocks, i.e.,

\begin{matrix} T = \sum_{i = 1}^{N} T_{j} = \sum_{j = 1}^{M} \sum_{i = 1}^{N} B_{i, j} . & (5) \end{matrix}

[0035] Our objective is to find the values of the optimal target number of bits for each frame in the sequence, T₁*, T₂*, . . . , T_M*, that minimize the distortion in (4) subject to the bit budget constraint in (5), i.e.,

\begin{matrix} T_{i}^{*}, T_{2}^{*}, \dots, T_{M}^{*} = \underset{\underset{T = \sum_{j = 1}^{M} T_{j}}{T_{1}, T_{2}, \dots, T_{M}}}{\arg \min} D = \underset{\underset{T = \sum_{j = 1}^{M} T_{j} = \sum_{j = 1}^{M} \sum_{i = 1}^{N} B_{i, j}}{T_{1}, T_{2}, \dots, T_{M}}}{\arg \min} \sum_{j = 1}^{M} \sum_{i = 1}^{N} \frac{{AK}_{j}}{12} \frac{α_{i, j}^{2} σ_{i, j}^{2}}{(B_{i, j} - A C_{j})} . & (9) \end{matrix}

[0036] Since Equation (6) involves the minimization of a convex function on a convex set, a unique solution to Equation (6) may be found using the method of Lagrange multipliers:

\begin{matrix} T_{i}^{*}, T_{2}^{*}, \dots, T_{M}^{*} = \underset{T_{1}, T_{2}, \dots, T_{M}}{argmin} \sum_{j = 1}^{M} \sum_{i = 1}^{N} \frac{{AK}_{j}}{12} α_{i, j}^{2} \frac{σ_{i, j}^{2}}{(B_{i, j} - A C_{j})} + λ (T - \sum_{j = 1}^{M} \sum_{i = 1}^{N} B_{i, j}), & (7) \end{matrix}

[0037] where λ is the Lagrange multiplier. We solve the minimization problem in Equation (6) by setting partial derivatives of Equation (7) to zero to obtain the following expression for the optimum target number of bits for a frame:

\begin{matrix} T_{j}^{*} = \frac{S_{j}}{\hat{S}} \frac{(T - AN \sum_{m = 1}^{M} C_{m})}{M} + {ANC}_{j}, & (8) \end{matrix}

[0038] where S_jis the following weighted sum of the standard deviations in the jth frame,

\begin{matrix} S_{j} = \sum_{i = 1}^{N} α_{i, j} σ_{i, j}, & (9) \end{matrix}

[0039] which can be interpreted as the energy in the jth frame, and Ŝ is the average of all the frame energies,

\begin{matrix} \hat{S} = \frac{1}{M} \sum_{i = 1}^{M} S_{j} . & (10) \end{matrix}

[0040] The formula in Equation (8) is the basis in the invention for assigning a target number of bits to frames of a video sequence. Equation (8) makes sense intuitively. If all the frames have approximately the same energy and motion-syntax overhead, i.e.,

[0041] S₁≈S₂≈ . . . ≈S_j≈ . . . ≈S_M,

[0042] C₁≈C₂≈ . . . ≈C_j≈ . . . ≈C_M,

[0043] then T_j* in Equation (8) is approximately T/M, and hence each frame is assigned the same number of bits (recall that T and M are the total number of bits and frames, respectively, for the video sequence). If different frames have different energy and motion activity, those with higher energy and motion (i.e., larger S_jand C_j) will be assigned more bits.

[0044] In order to compute the value of Ŝ in Equation (10), the energy in each frame of the M frame-sequence must be computed. This computation would introduce large delays in the encoding process, since it would require the encoder to wait for M frames before encoding the first one (Ŝ would also be inaccurate without recursion, as frame energy for a frame depends on the target bit rate used for predictive frames). These drawbacks are often not acceptable; preferably then, the encoder estimates Ŝ with an averaging technique (described in the next section). Similarly, the sum of the C_j's in Equation (8) cannot be known in advance and will also preferably be estimated.

[0045] Frame Target Selection

[0046] Practical implementations of Equation (8) can take a variety of forms. For example, in MPEG2-type applications Equation (8) could be used for selecting the bit targets in groups of frames (i.e., patterns of I, P, and B frames). In the following embodiment, low-delay type applications, where all frames are predicted from the previous ones, and information for future frames is not available, are considered. The goal in this type of application is to select an adequate target number of bits for the current frame to be encoded.

[0047] Based on Equation (8), the following low-delay formula can be used for assigning a target number of bits T₀for the current frame:

\begin{matrix} T_{o} = {\begin{matrix} \frac{S}{\hat{S}} (B - \hat{V}) + V; & B > \hat{V} \\ \frac{S}{\hat{S}} B; & otherwise \end{matrix} & (11) \end{matrix}

[0048] The parameters B, S, {circumflex over (V)} and V in Equation (11) correspond to T/M, S_j, ANΣ_mC_m/M, and ANC_jin Equation (8), respectively. The formula in Equation (11) for B>{circumflex over (V)} is the same as that in Equation (8). However, {circumflex over (V)} is estimated and may be inaccurate at times—when B<{circumflex over (V)}, the estimate for {circumflex over (V)} is too large. In that case, a second estimate S{circumflex over (V)}/Ŝ=V reduces Equation (8) to the simple formula at the bottom of Equation (11). The values of the parameters in Equation (11) can be computed as follows:

[0049] B—Average Number of Hits Per Frame

[0050] B is the number of bits accepted by the communication channel during a frame interval. Specifically:

\begin{matrix} B = \frac{R}{F}, & (12) \end{matrix}

[0051] where R is the channel or target bit rate (in bits per second) and F is the frame rate of the video source (in frames per second). For example, 10 encoded frames per second of digital video at 64 Kilobits per second results in B=6400 bits.

[0052] S—Energy of the Current Frame

[0053] In this example a frame to be encoded is decomposed into N blocks of a fixed size, e.g., 16×16 pixels per block. S is the sum of the empirical standard deviations of the pixels in the blocks and can be obtained as described in Equation (9). Preferably, α_i,jis set to σ_i,j, resulting in the simplification

S_{j} = \sum_{i = 1}^{N} σ_{i, j}^{2} .

[0054] Ŝ—Average Frame Energy

[0055] Ŝ is the average energy of the frames in the video sequence as defined in Equation (10). But, as explained earlier, in practice it is often impractical to look ahead to find the value of the energies of future frames and hence the value of Ŝ needs to be estimated. At the first frame, Ŝ=S can be used as the estimate. In the next frames, the value of Ŝ can be updated using a weighted average, e.g., a first-order filtered version of S:

[0056] Ŝ=aŜ+(1−a)S, (13)

[0057] where the weight parameter a is a function of the desired maximum delay d (in seconds) introduced by the encoder buffer; for example:

\begin{matrix} a = {\begin{matrix} \frac{0.9}{0.5} d; & d < 0.5 \\ 0.9; & otherwise \end{matrix} & (14) \end{matrix}

[0058] In this example, when the delay d is below 0.5 seconds, the value of a decreases linearly with d. The formula for a is plotted in FIG. 4.

[0059] Typically, the buffer delay d is directly proportional to the size (in bits) of the encoder buffer, Buff, defined herein as Buff=d R.

[0060] V—Motion and Syntax Bit Overhead

[0061] V is the number of bits spent in motion and syntax for the current frame. This number can be directly measured in some encoders, or can be estimated by the number of motion and syntax bits spent in the previous frame.

[0062] {circumflex over (V)}—Average Motion and Syntax Bit Overhead

[0063] {circumflex over (V)} is the average number of bits per frame used for motion vectors and codec syntax in the video sequence,

\begin{matrix} \hat{V} = \frac{1}{M} \sum_{m = 1}^{M} V_{m}, & (15) \end{matrix}

[0064] with M the total number of frames and V_mthe number of motion and syntax bits used for the m-th frame. However, as in the case of Ŝ, in practice it is often impractical to look ahead to find the value of future V_m's—hence, the value of {circumflex over (V)} needs to be estimated. At the first frame, {circumflex over (V)}=V can be used as the estimate. In succeeding frames, the value of {circumflex over (V)} can be updated using the same type of weighted average used for Ŝ in Equation (13):

[0065] {circumflex over (V)}=a{circumflex over (V)}+(1−a)V, (16)

[0066] where the weight parameter a is a function of the desired buffer delay d (in seconds) in the communication system, as described above.

[0067] Frame Target Selection for Very Low Delay

[0068] The frame target selection system described above reduces the range of values taken by T₀when the user desires lower communication delay. This is because the value of a becomes smaller for lower delay, and hence the values of the estimates Ŝ Equation (13), and {circumflex over (V)}, Equation (15) become closer to S and V, respectively. Actually, when the buffer delay d is close to 0, a is also close to 0, and as a result Ŝ≈S and {circumflex over (V)}≈V. Consequently, with very low d the frame target Equation (11) is approximately constant and equal to the average channel bits per frame,

\begin{matrix} T_{o} \approx B = \frac{R}{F}, & (17) \end{matrix}

[0069] which is the best strategy for frame-layer rate control at very low delay. This is because the number of bits per frame matches those taken by the channel and hence few or no bits are accumulated in the buffer. As a result, the buffer size and delay can be very small.

[0070] Buffer Protection

[0071] The objective of a buffer protection subsystem is to maintain the number of bits in the buffer close to a desired level. If the buffer fullness is too high or low, the buffer may overflow or underflow, respectively. Also, even if a target number of bits would not overflow or underflow the buffer, typical block-layer rate control schemes do not achieve the target exactly; thus a danger of overflow or underflow still exists. Two separate buffer protection levels, disclosed below, can help protect the buffer from such problems. These levels can be used together (for maximum protection) or independently.

[0072] Level 1

[0073] In this level, a factor Δ, which depends on the fullness of the encoder buffer, corrects the target number of bits per frame. Specifically, Δ adds to the initial frame target T₀, forming the target T₁, with level-1 protection,

[0074] T₁=T₀+Δ, (18)

[0075] where

\begin{matrix} Δ = {\begin{matrix} - \frac{W}{F}; & W > G \\ \frac{G - W}{F^{'}}; & otherwise \end{matrix}, & (19) \end{matrix}

[0076] and where:

[0077] W—Current number of bits in the encoder buffer

[0078] F—Frame rate of the video sequence in frames per second (e.g., 30 fps)

[0079] G—Desired number of bits in the encoder buffer.

[0080] The goal of Equation (19) is to decrease the frame target if the current number of bits in the buffer, W, is above the goal G, or to decrease it otherwise. The value of G can be selected in terms of the buffer delay d and the buffer size Buff as follows:

\begin{matrix} G = {\begin{matrix} 0.5 Buff; & d > 0.5 \\ d Buff; & 0.1 < d \leq 0.5 \\ 0.1 Buff; & d \leq 0.1 \end{matrix} . & (20) \end{matrix}

[0081] The formula for G indicates that for delays larger than 0.5 seconds, the rate control should aim to keep the buffer fullness at 50 percent, but at lower delays the fullness should be lower (down to 10 percent). This is because when the delay is very small, the buffer size is also very small (recall that Buff=d R), and keeping the buffer fullness to 50 percent may easily produce buffer overflow. The formula for G in Equation (20) is illustrated in FIG. 5.

[0082] F′—A parameter that depends on the frame rate F and the delay d, as follows:

\begin{matrix} F^{'} = {\begin{matrix} F; & d > 0.5 \\ \frac{F - 1}{0.4} (d - 0.1) + 1; & 0.1 < d \leq 0.5 \\ 1; & d \leq 0.1 \end{matrix} . & (21) \end{matrix}

[0083] The value of F′ is set using Equation (21), which is illustrated in FIG. 6, throughout the video sequence. The rationale in Equation (21) is that when the buffer delay d (or buffer size) is small, since G in Equation (20) is also small, the buffer fullness will be low and there is danger of buffer underflow. To prevent underflow, F′ can be made smaller for lower d, which in turn will make the target increase Δ in Equation (19) larger.

[0084] Level 2

[0085] The buffer protection at this level is also done before encoding the current frame. This level assumes that T₁bits will be spent for encoding that frame and checks whether that may produce buffer overflow or underflow. To do this, the encoder computes the number of bits expected to be in the buffer after encoding the current frame as follows:

[0086] W′=max(W+T₁−B,0), (22)

[0087] where W is the current number of bits in the buffer, T₁is the target number of bits for the current frame (with level-1 protection), and B is the number of bits accepted by the communication channel per frame interval. If the current frame occupies T₁bits, the number of bits or fullness of the buffer after encoding this frame will be the current fullness W plus T₁and minus the B bits sent through the channel. If B is larger than W+T₁there is buffer underflow, because the channel accepts more bits than those available in the buffer. In this situation, the max operator in Equation (22) sets the content of the buffer to zero.

[0088] To prevent buffer overflow, H Buff is selected to be the desired maximum number of bits in the encoder buffer (the value of H is typically between 0.85 and 0.95—hence, H Buff is 85 to 95 percent of the buffer size). If the expected number of bits in the buffer W′, Equation (22) is larger than the desired maximum H Buff, the buffer is almost full and the frame target is decreased to prevent buffer overflow. Conversely, if W′ is zero, there will be buffer underflow and the target is increased. This process can be described as follows:

[0089] if (W′>HBuff) T₂=HBuff−W+B;

[0090] else if (W′=0) T₂=−W+B;

[0091] else T₂=T₁. (23)

[0092] where T₂is the new target number of bits per frame (with level-2 protection) and H is the buffer threshold that can be set to a fixed value, or found using either of the two formulas below:

\begin{matrix} a) H = {\begin{matrix} 0.95 & R > 112000 \\ \frac{0.1}{0.102} R + \frac{85.7}{102} & 10000 < R \leq 112000 \\ 0.85 & R \leq 10000 \end{matrix} & (24) \\ b) H = 1 - \frac{p}{Fd}, & (25) \end{matrix}

[0093] where R, F, and d are the bit rate, frame rate, and delay, respectively, and p is a number between 0 and 1 (e.g., 0.1).

[0094] The rationale behind Equations (24) and (25) is that the buffer threshold H can be larger with larger buffer size Buff, where recall that Buff=R d. H increases with larger R in Equation (24) and larger d in Equation (25). Equation (24) was designed using empirical experiments. Equation (25) was derived by isolating the value of H from the following constraint:

[0095] Buff−HBuff=p R/F,

[0096] (1−H)R d=p R/F, (26)

[0097] in which Buff−H Buff is the safety number of bits kept above the desired maximum buffer fullness H Buff, and p R/F is a percentage of the average number of bits per frame. For example, if p=0.1, Equation (25) would select the value of H that would keep 10 percent of the average bits per frame as the safety margin.

[0098] Encoder Block Diagram

[0099] Frame target selection and buffer protection as described above can be implemented in conjunction with any image or video encoder. For generality, FIG. 7 shows a video encoder 60 that includes an image encoder 62, a motion encoder 56, and a buffer 68. The motion compensator 24 and summer 22 of FIG. 1 are not shown to aid clarity, but such would typically exist in encoder 60. Neither motion compensation nor buffering need be present in a specific implementation in order for the invention to be used.

[0100] In operation, motion-compensated frames are routed to energy estimator 70. Energy estimator 70 implements, e.g., Equation (9) and routes its output S_jboth to frame-layer rate controller 66 and average energy estimator 72. Average energy estimator implements, e.g., Equations (13) and (14), and routes its output Ŝ to frame-layer rate controller 66. In a basic system, frame-layer rate controller 66 ratios these values and multiplies the result by the desired average bits per frame B to produce target bit rate T_j. Image encoder 62 then uses T_jto adjust its compression to the desired target.

[0101] In a system employing motion compensation (and more generally, prediction), prediction bit totals can be supplied to frame-layer rate controller 66. Motion encoder 56 sends its count of motion bits for the current frame, C_j, both to frame-layer rate controller 66 and average motion bits estimator 58. Average motion bits estimator 58, e.g., implementing Equations (15) and (16), also sends its output Ĉ to frame-layer rate controller 66. Frame-layer rate controller uses these additional variables, e.g., to form an estimate for T_jas described in equation (11). Note that T_jincludes C_j; image encoder 62 must comprehend that these C_jbits are not available to it for coding the motion-compensated image.

[0102] In a system employing buffer protection, buffer 68 can supply feedback on its current fullness level W to frame-layer rate controller 66. Controller 66 can use, e.g., Level 1 and/or Level 2 buffer protection to adjust T_j.

[0103] Particular estimates in each estimation block of encoder 60 will generally be application-dependent, although the delay adaptive implementations described herein are preferred.

[0104] Experimental Results

[0105] The frame target selection and buffer protection of the present invention were implemented in the frame layer of a rate control technique that encoded frames of real video sequences using an MPEG∝codec. This codec also used the block and data selection layers as described in co-pending U.S. patent application Ser. No. 09/008,137 (now U.S. Pat. No. 6,111,991) incorporated above, and Ser. No. 09/052,882, filed Mar. 31, 1998, by J. Ribas-Corbera and S. Lei, also incorporated herein by reference. The methods described in these two applications were used as block and data selection layers, respectively. The frame layer included the frame target selection system and Level 2 buffer protection (Level 1 buffer protection was also implemented and tested in a different codec). Equation (24) was used to select the value of H. The performance of this method (referred to as SLA rate control) was compared to VM7 rate control, which is a well-known rate control method from Sarnoff Corporation [13].

[0106] Table 1 describes the name of the video sequences, format, bit rates and frame rates used in each experiment, and assigns a name to each experiment. All video sequences contained 300 frames and were downsampled at the encoding frame rate specified in the experiments. Overall, 1400 frames were encoded. In the tests, the fullness of the encoder buffer was simulated. Rate control was tested with two different buffers:

[0107] Buffer 1: a buffer of size 0.125 times the bit rate of each sequence, Buff=0.125*R, which corresponds to a buffer delay of d=0.125 seconds. This buffer size is often used for low delay video communications.

[0108] Buffer 2: a buffer of size 0.05 times the bit rate, Buff=0.050*R, which corresponds to a delay d=0.050. This is a very small buffer size that is not typically used in practice, but was selected here in order to explore the performance of the SLA rate control method in such a challenging case.

[0109] Tables 2 and 3 show the percentage of times that the buffers overflow and underflow, respectively, with SLA and VM7 rate control. Buffer overflow is an important problem that forces the encoder to slow down or drop image blocks—preferably, overflow should rarely occur. On the other hand, buffer underflow is less critical, but should also be avoided if possible since it wastes channel bandwidth.

[0110] Table 2 shows the percentage of times that the buffer overflows (with respect to the number of frames encoded) when Buffer 1 and Buffer 2 are used with SLA and VM7 rate control. For Buffer 1, SLA rate control controls the bit rate so well that the buffer practically never overflows. In fact, overflow occurred only once in “fmn112_c” (and only a few bits overflowed), which would have barely affected the encoder. For the challenging Buffer 2, the SLA rate control method suffers overflow in only 4 of the 1400 encoded frames—again, only a few bits overflowed in each case. This is particularly impressive, since it is very difficult to control the bit rate fluctuations within such a small buffer. In order to appreciate the benefits of the SLA procedure, observe that overflow is much more common in both buffers with VM7 rate control. Further, with VM7 it was found that the number of bits that overflow is sometimes as large as twice the size of the buffer.

[0111] Table 3 shows the percentages of buffer underflow. Observe that SLA rate control underflows the buffers occasionally, but much less often than VM7 rate control. In particular, VM7 rate control underflows the buffer above 80 percent of the time in most of the experiments for Buffer 2.

[0112] Overall, SLA rate control is very robust for controlling the bit rate with small buffer sizes and overflows and underflows the buffer much less often than VM7's.

TABLE 1

Description of the video sequences, formats, bit rates and frame
rates used in the experiments. Each video sequence contained 300
frames at 30 frames per second and was downsampled at the encoding
frame rate. The left-most column shows the name given to each of
the experiments.

TABLE 2

Percentage of times that buffer overflow occurs in an MPEG4 codec
using SLA rate control (SLA) and VM7's (VM7) [13].

TABLE 3

Percentage of times that buffer underflow occurs in an MPEG4
codec using SLA rate control (SLA) and VM7's (VM7) [13].

[0113] Alternative Implementations

[0114] Several variations on the basic invention are described below.

[0115] One-pass

[0116] If the computation of the σ_k's used for finding S_jin Equation (9) cannot be done in advance, a good estimate for Sj such as the value of S from the previous video frame may be substituted.

[0117] Low-complexity Estimation of σ_i

[0118] In order to further reduce computational complexity, the formula for the standard deviation in Equation (2) may be approximated as

σ_{i, j} = \frac{1}{A} \sum_{l = 1}^{A} abs (P_{i, j} (l) - {\overline{P}}_{i, j}),

[0119] where abs(x) is the absolute value of x. In video coding, the mean value of pixels in motion-compensated blocks is usually zero and hence this formula may be further simplified by setting {overscore (P)}_i,j=0.

[0120] Encoding Intra and Inter Blocks

[0121] If some of the blocks to be encoded are of class intra and some are inter, as described in U.S. patent application Ser. No. 09/008,137, the performance of the frame target selection method can be improved by dividing the standard deviation of the intra blocks by a factor {square root over (γ)}. Specifically, after computing the value for the σ_k's in Step 1, set:

σ_{k} = {\begin{matrix} \frac{σ_{k}}{\sqrt{γ}} & if k th block is intra \\ σ_{k} & otherwise \end{matrix} .

[0122] The factor γ is

γ = \frac{K_{P}}{K_{I}},

[0123] where K_Iand K_Pare the averages of the K's from Equation (1) measured for the intra and inter blocks, respectively. The value of γ can be estimated and updated during encoding. In practice, a constant γ=3 works quite well.

[0124] Encoding a Group of Pictures (GOP)

[0125] In MPEG and H.263+codecs, there are different types of frames:

[0126] I frames, whose pixel values are encoded by themselves (or intracoded) without using a prediction from other frames in the video sequence.

[0127] P frames, whose pixels are predicted from a previous frame in the video sequence.

[0128] B frames, whose pixels are bi-directionally predicted using previous and future frames in the sequence.

[0129] A simple variation of equation (8) can be used to assign a target number of bits for each type of frame. For example, consider the typical case where the sequence or pattern of frame types is:

[0130] I,B, . . . ,B,P,B, . . . ,B,P,B, . . . ,B,P,B, . . . ,B,P, . . . (27)

[0131] The set of frames “B, . . . ,B,P” is repeated periodically after the first I frame. In MPEG, such a set (or any other that repeats periodically) is called a group of pictures or GOP.

[0132] GOP Type B, . . . ,B,P

[0133] Let N_Bbe the number of B frames in the GOP above. The target number of bits for the P picture in that GOP, T_P, and the target for each of the B frames, T_B, can be computed from Equation (8) as follows:

\begin{matrix} T_{P} = \frac{S_{P}}{\hat{S}} \frac{(T - {ANMC}_{PB})}{N_{B} + 1} + {ANC}_{P}, & (28) \\ T_{B} = \frac{S_{B}}{\hat{S}} \frac{(T - {ANMC}_{PB})}{N_{B} + 1} + {ANC}_{B}, & (29) \end{matrix}

[0134] where the parameters in Equations (28) and (29) are equivalent to those in Equation (8). Specifically:

[0135] S_Pis the energy, Equation (9), for the P frame in the current GOP, which can either be measured or estimated as the average of the energies of P frames in previous GOP's.

[0136] S_Bis the average of the energies, Equation (9), for the B frames in the current GOP, which again can either be measured or estimated as the average of B frame energy in previous GOP's.

[0137] S is the (estimated) average of the energy in the GOP, i.e.,

\hat{S} = \frac{S_{P} + N_{B} S_{B}}{1 + N_{B}} .

[0138] C_Pand C_Bare the motion and syntax rate (in bits per pixel) for the P and B frames, respectively, as defined in Equation (1), and they can also either be measured or estimated. C_PBis their average in the GOP, i.e.,

C_{PB} = \frac{C_{P} + N_{B} C_{B}}{1 + N_{B}} .

[0139] Finally, T, M, and N are the total number of bits (for the GOP), frames (in the GOP), and macroblocks in a frame.

[0140] Equations (28) and (29) may be rearranged in an implementation. For example, after some lengthy but straightforward manipulations, equations (28) and (29) can be rewritten as follows:

\begin{matrix} T_{B} = \frac{T - AN (C_{P} - β C_{B})}{β + N_{B}}, & (30) \end{matrix}

T_P=T−N_BT_B, (31)

[0141] where

β = \frac{S_{P}}{S_{B}} .

[0142] Alternative Formulas for Estimating β

[0143] The value off β is the ratio S_P/S_B. In Equations (30) and (31), β is a key parameter that has strong influence on how many bits are assigned to P and B frames. For example, if β is close to 1, the number of bits for each frame in the GOP is similar, i.e., T_P≈T_B, and if β is larger than 1, then T_Pis also larger than T_B. Since β is a key parameter, its value must be estimated carefully. Two methods for estimating β are presented here:

[0144] Method 1:

[0145] Set β equal to S_P/S_B, where S_Pis the average of the energies in the M previously encoded P frames and S_Bis the average of the energies in the N previously encoded B frames. If available, the energy of the frame that is being encoded could be used as well in the respective average.

[0146] Method 2:

[0147] After a given frame is encoded, update the value of β as follows:

\begin{matrix} β = b β_{prev} + (1 - b) F \frac{S_{P}}{S_{B}}, & (32) \end{matrix}

[0148] where here β_previs the previous value of β, and S_Pand S_Bare the energies of the last encoded P and B frames, respectively. F and are b filter or weight parameters. Typically F takes values between 1 and 5, and b between 0.7 and 0.9.

[0149] When F is 1, experiments show that the image quality (in terms of MSE) is similar for P and B frames. However, in some cases, the average image quality can be increased by allowing some frames to have better quality than others. For example, increasing F would result in a larger β, which in turn would increase both T_Pand the quality of the P frame. This would appear to reduce the quality of the B frames, since T_Bwould be smaller. But since the P frame has higher quality and is used to predict the B's by motion compensation, the quality of the B frames could also increase. Using empirical tests, the value of F that optimizes MSE performance decreases with bit rate. This effect can be modeled with the following formula:

\begin{matrix} F = \frac{c}{{Bpp}^{ψ}} + d, & (33) \end{matrix}

[0150] where Bpp is the rate in bits per pixel for the given video sequence, and c, d, and ψ are constant parameters whose value can be set for a given video codec. For example, in an H.263+ encoder, we empirically found that c=1.35, d=−0.4, and ψ=0.5, are good choices.

[0151] We implemented a frame layer rate control based on Equations (30), (31), (32) and (33), and Thomson's frame layer from [14] in a video encoder compliant to the H.263+ standard. The method in [14] is known as TM5 rate control and is a very popular technique used as a benchmark for comparisons in the rate control literature. For a fair comparison, the rate control at the block layer was the same for both cases. We turned on the advanced prediction, extended motion range, and true B frame options (annexes D, F, and O) in the H.263+ encoder, and selected GOPs with either one (N_B=1) or two (N_B=2) B frames. The tests are described in Table 4 and the results are in Table 5. FIG. 8 plots the peak signal-to-noise ratio or PSNR per video frame for one of the tests. The PSNR is the typical measure of image quality used in the image and video compression literature and is given in dB's, and a PSNR improvement of 1 dB corresponds to bit rate savings of about 20 percent. Observe that our new frame layer improves the average PSNR up to 1.38 dB with respect to TM5's. Our superior performance is because our frame target formulas are based on a rate-distortion optimization.

TABLE 4

Description of the experiments: names assigned to each experiment,
original video sequences, GOP pattern of frames, and target bit rates.
The spatial resolution of the video frames was QCIF and the frame rate
was of 15 frames per second. The bit rate achieved was very close to
the target in all cases. A total of five seconds were encoded for each
video sequence.

	TABLE 5

	TM5 Frame Layer	New Frame Layer

[0152] General GOP Type

[0153] Observe that equations similar to Equations (28) and (29) can be derived from Equation (8) for any GOP frame pattern. For example, consider a GOP where the number of I, P, and B frames is respectively N_I, N_P, and N_B. Then the target number of bits for each frame type is:

\begin{matrix} T_{I} = \frac{S_{I}}{\hat{S}} \frac{(T - {ANMC}_{IPB})}{N_{I} + N_{P} + N_{B}} + {ANC}_{I}, & (34) \\ T_{P} = \frac{S_{P}}{\hat{S}} \frac{(T - {ANMC}_{IPB})}{N_{I} + N_{P} + N_{B}} + {ANC}_{P}, & (35) \\ T_{B} = \frac{S_{B}}{\hat{S}} \frac{(T - {ANMC}_{IPB})}{N_{I} + N_{P} + N_{B}} + {ANC}_{B}, & (36) \end{matrix}

[0154] which, once again, after some manipulations, can be re-written as follows:

\begin{matrix} T_{I} = \frac{(T - {ANMC}_{IPB})}{N_{I} + \frac{N_{P}}{β_{IP}} + \frac{N_{B}}{β_{IP} β_{PB}}} + {ANC}_{I}, & (37) \\ T_{P} = \frac{(T - {ANMC}_{IPB})}{N_{I} β_{IP} + N_{P} + \frac{N_{B}}{β_{PB}}} + {ANC}_{P}, & (38) \\ T_{B} = \frac{(T - {ANMC}_{IPB})}{N_{I} β_{IP} + N_{P} β_{PB} + N_{B}} + {ANC}_{B} . & (39) \end{matrix}

[0155] The parameters in Equations (37), (38), and (39) have the same meaning as in previous formulas. For example, {C_I, C_P, C_B} are the respective C's for I, P, and B frames, and:

\begin{matrix} C_{IPB} = \frac{N_{I} C_{I} + N_{P} C_{P} + N_{B} C_{B}}{N_{I} + N_{P} + N_{B}} . & (40) \end{matrix}

[0156] The values of the β's can be estimated with either Method 1 or 2 above. For example,

\begin{matrix} β_{IP} = b_{IP} β_{IP, prev} + (1 - b_{IP}) F_{IP} \frac{S_{I}}{S_{P}}, & (41) \\ β_{PB} = b_{PB} β_{PB, prev} + (1 - b_{PB}) F_{PB} \frac{S_{P}}{S_{B}}, & (42) \end{matrix}

[0157] where {b_IP, F_IP} and {b_PB, F_PB} are the respective estimator parameters, as in Equation (32).

[0158] After reading this disclosure, one of ordinary skill in the art will recognize that many advantageous modifications to the disclosed embodiments are enabled by the concepts taught herein. In particular, estimation of the parameters used in the calculation of a frame target bit allocation is typically a design choice, and practically will be based on encoder structure and block timing. Such obvious modifications are intended to fall within the scope of the invention as claimed.

Claims

Certificate of Correction present

The claims shown below may not include correction changes. Use the corrected PDF for authoritative text.

What is claimed is:

1. A method for allocating, among the image frames in an image frame sequence, the bits available for representing the image frame sequence, said method comprising the steps of:

defining a desired average frame target bit allocation B for a group of image frames;

estimating the frame energy S_iof an individual image frame i selected from said group, wherein said step of estimating the frame energy S_iof an individual image frame i comprises computing a weighted sum of the absolute value of pixels in image frame i;

estimating an average frame energy Ŝ using individual frame energy estimates for frames in the image frame sequence up to image frame i;

setting an individual frame target bit allocation T_ifor said individual image frame as

T_{i} = \frac{S_{i}}{\hat{S}} B,

and wherein for at least some values of i, individual image frame i utilizes a portion of its individual target bit allocation T_iin transmitting overhead bits V_i, wherein the individual frame target bit allocation T_ifor said individual image frame i compensates for overhead bits V_iby computing the individual frame target bit allocation as

T_{i} = \frac{S_{i}}{\hat{S}} (B - \hat{V}) + V_{i},

where {circumflex over (V)} is obtained by estimating the average overhead bits per image frame for said group.

2. A method for allocating, among the image frames in an image frame sequence, the bits available for representing the image frame sequence, said method comprising the steps of:

defining a desired average frame target bit allocation B for a group of image frames;

estimating the frame energy S_iof an individual image frame i selected from said group;

estimating an average frame energy Ŝ using individual frame energy estimates for frames in the image frame sequence up to image frame i, wherein said step of estimating the average frame energy Ŝ comprises initializing Ŝ−S_ifor a first frame i in said group, and updating Ŝ on subsequent frames in said group using a first order filter of the form Ŝ=aŜ+(1−a)S_i, where 0.0<a>1.0;

setting an individual frame target bit allocation T_ifor said individual image frame as

T_{i} = \frac{S_{i}}{\hat{S}} B,

wherein for at least some values of i, individual image frame i utilizes a portion of its individual target bit allocation T_iin transmitting overhead bits V_i, wherein the individual frame target bit allocation T_ifor said individual image frame i compensates for overhead bits V_iby computing the individual frame target bit allocation as

T_{i} = \frac{S_{i}}{\hat{S}} (B - \hat{V}) + V_{i},

where {circumflex over (V)} is obtained by estimating the average overhead bits per image frame for said group.

3. The method of claim 2, further comprising the steps of encoding each of said individual image frames and storing each encoded image frame in an encoder buffer for transmission, wherein the value of a is a function of a maximum transmission delay d introduced by the encoder buffer.

4. The method of claim 3, wherein

a = {\begin{matrix} \frac{0.9}{0.5} d; & d < 0.5 \\ 0.9; & otherwise \end{matrix} .

5. A method for allocating, among the image frames in an image frame sequence, the bits available for representing the image frame sequence, said method comprising the steps of:

defining a desired average frame target bit allocation B for a group of image frames;

estimating the frame energy S_iof an individual image frame i selected from said group;

estimating an average frame energy Ŝ using individual frame energy estimates for frames in the image frame sequence up to image frame i;

setting an individual frame target bit allocation T_ifor said individual image frame as

T_{i} = \frac{S_{i}}{\hat{S}} B,

T_{i} = \frac{S_{i}}{\hat{S}} (B - \hat{V}) + V_{i},

where {circumflex over (V)} is obtained by estimating the average overhead bits per image frame for said group, and wherein said step of estimating the average overhead bits per image frame {circumflex over (V)} comprises initializing {circumflex over (V)}=V_ifor a first frame i in said group, and updating {circumflex over (V)} on subsequent frames in said group using a first order filter of the form {circumflex over (V)}=a{circumflex over (V)}+(I−a) V_i, where 0.0<a<1.0.

6. The method of claim 5, further comprising the steps of encoding each of said individual image frames and storing each encoded image frame in an encoder buffer for transmission, wherein the value of a is a function of a maximum transmission delay d introduced by the encoder buffer.

7. The method of claim 6, wherein

a = {\begin{matrix} \frac{0.9}{0.5} d; & d < 0.5 \\ 0.9; & otherwise \end{matrix} .

8. A method for allocating, among the image frames in an image frame sequence, the bits available for representing the image frame sequence, said method comprising the steps of:

defining a desired average frame target bit allocation B for a group of image frames;

estimating the frame energy S_iof an individual image frame i selected from said group;

estimating an average frame energy Ŝ using individual frame energy estimates for frames in the image frame sequence up to image frame i;

setting an individual frame target bit allocation T_ifor said individual image frame as

T_{i} = \frac{S_{i}}{\hat{S}} B,

T_{i} = \frac{S_{i}}{\hat{S}} (B - \hat{V}) + V_{i},

where {circumflex over (V)} is obtained by estimating the average overhead bits per image frame for said group;

obtaining the current number of bits in an encoder buffer;

comparing the current number of bits in the encoder buffer to a desired number of bits in the encoder buffer, wherein said desired number of bits in the encoder buffer is a function of buffer delay;

computing an individual target bit allocation correction based on the comparing step; and

adding the individual target bit allocation correction to the individual frame target bit allocation T_i.

9. The method of claim 8, wherein G is the desired number of bits in the encoder buffer, d is a specified buffer delay, and Buff is the size of the encoder buffer,

G = {\begin{matrix} 0.5 Buff; & d > 0.5 \\ d Buff; & 0.1 < d \leq 0.5 \\ 0.1 Buff; & d \leq 0.1 \end{matrix} .

10. A digital video encoder comprising:

a frame-layer rate controller;

an image encoder that encodes images in a video sequence based on a target bit assignment supplied by said frame-layer rate controller;

a frame energy estimator that operates on said images to produce frame energy estimates;

an average frame energy estimator that operates on frame energy estimates obtained from the frame energy estimator for previous images in the video sequence to produce average frame energy estimates;

wherein said frame-layer rate controller adjusts said target bit assignment based on a ratio of one of said frame energy estimates to one of said average frame energy estimates; and

a buffer for buffering images encoded by said image encoder for a known average buffer delay, wherein said average frame energy estimator comprises a frame energy estimate filter, said filter having a time constant that is a function of the said buffer delay.

11. The digital video encoder of claim 10, wherein said buffer reports its fullness to said frame-layer rate controller, and wherein said frame-layer rate controller adjusts said target bit assignment based on said fullness to avoid buffer underflow and overflow.

12. A digital video encoder comprising:

a frame-layer rate controller;

an image encoder that encodes images in a video sequence based on a target bit assignment supplied by said frame-layer rate controller;

a frame energy estimator that operates on said images to produce frame energy estimates;

an average frame energy estimator that operates on frame energy estimates obtained from the frame energy estimator for previous images in the video sequence to produce average frame energy estimates;

wherein said frame-layer rate controller adjusts said target bit assignment based on a ratio of one of said frame energy estimates to one of said average frame energy estimates; and

a predictor that computes a prediction vector for a current image based on previously encoded images;

a prediction vector encoder that codes said prediction vector and produces an encoded vector bit size; and

an average prediction vector bit size estimator that operates on said encoded vector bit size to produce an average encoded vector bit size,

wherein said frame-layer rate controller adjusts said target bit assignment for average encoded vector bit size and encoded vector bit size.

Patent Citations (17)

Patent	Date	Inventor	Cited By
US4984076(A)	1991-01-01	Watanabe et al.	Examiner
US5038209(A)	1991-08-01	Hang	Applicant
US5159447(A)	1992-10-01	Haskell et al.	Applicant
US5231484(A)	1993-07-01	Gonzales et al.	Applicant
US5241383(A)	1993-08-01	Chen et al.	Applicant
US5274443(A)	1993-12-01	Dachiku et al.	Applicant
US5283646(A)	1994-02-01	Bruder	Applicant
US5323187(A)	1994-06-01	Park	Applicant
US5426463(A)	1995-06-01	Reininger et al.	Applicant
US5506686(A)	1996-04-01	Auyeung et al.	Applicant
US5532746(A)	1996-07-01	Chang	Applicant
US5550590(A)	1996-08-01	Sakazawa et al.	Applicant
US5617150(A)	1997-04-01	Nam et al.	Applicant
US5719986(A)	1998-02-01	Kato et al.	Examiner
US5847761(A)	1998-12-01	Uz et al.	Examiner
EP655867(A1)	1994-11-01		Applicant
WO96/04646	1996-02-01		Applicant

Non-Patent Literature (2)

Video Codec Test Model, TMN5, Telnor Research, Jan. 31, 1995 (13 pages).Applicant
MPEG-4 Video Verification Model Version 7.0, Coding of Moving Pictures and Associated Audio Information, Apr. 1997 (title page {p. 1}, table of contents {pp. 3-5}, 3.7 Rate Control section {82-88}).Applicant

Abstract

Description

[0002] This application claim benefit to provisional application No. 60/067,692 Dec. 1, 1997.

Field of the Invention

[0003] This invention pertains generally to digital video encoders, and more particularly to frame-adaptive bit rate control of such encoders.

Background of the Invention

Summary of the Invention

Brief Description of the Drawing

[0016] The invention may be best understood by reading the disclosure with reference to the drawing, wherein:

[0017] FIG. 1 illustrates a block diagram of a prior art digital video encoder;

[0018] FIG. 2 shows a corresponding block diagram of a prior art digital video decoder;

[0019] FIG. 3 illustrates the concept of a block coder;

[0020] FIGS. 4-6 show suggested delay-adaptive relationships for several parameters of frame-adaptive bit rate control;

[0021] FIG. 7 shows a digital video encoder embodiment of the present invention; and

Detailed Description of the Preferred Embodiments

[0026] Bit-Distortion Model

\begin{matrix} B_{i, j} = \frac{{AK}_{j}}{12} \frac{α_{i, j}^{2} σ_{i, j}^{2}}{D_{i, j}} + A C_{j}, & (1) \end{matrix}

\begin{matrix} σ_{i, j}^{2} = \frac{1}{A} \sum_{l = 1}^{A} {(P_{i, j} (l) - {\overline{P}}_{i, j})}^{2}, & (2) \end{matrix}

[0029] where A is the number of pixels in a block, P_i,j(l) is the value of the l-th pixel in the block, and {overscore (P)}_i,jis the average of the pixel values in the block,

\begin{matrix} {\overline{P}}_{i, j} = \frac{1}{A} \sum_{l = 1}^{A} P_{i, j} (l) . & (3) \end{matrix}

[0031] Equation (1) indicates that the number of bits B_i,jproduced when encoding the ith block (in the jth frame) is inversely proportional to the block's distortion D_i,j.

[0032] The Rate-Distortion Optimization Problem

\begin{matrix} D = \frac{1}{MN} \sum_{j = 1}^{M} \sum_{I = 1}^{N} D_{i, j} = \frac{1}{MN} \sum_{j = 1}^{M} \sum_{i = 1}^{N} \frac{{AK}_{j}}{12} α_{i, j}^{2} \frac{σ_{i, j}^{2}}{(B_{i, j} - A C_{j})}, & (4) \end{matrix}

\begin{matrix} T = \sum_{i = 1}^{N} T_{j} = \sum_{j = 1}^{M} \sum_{i = 1}^{N} B_{i, j} . & (5) \end{matrix}

\begin{matrix} T_{i}^{*}, T_{2}^{*}, \dots, T_{M}^{*} = \underset{\underset{T = \sum_{j = 1}^{M} T_{j}}{T_{1}, T_{2}, \dots, T_{M}}}{\arg \min} D = \underset{\underset{T = \sum_{j = 1}^{M} T_{j} = \sum_{j = 1}^{M} \sum_{i = 1}^{N} B_{i, j}}{T_{1}, T_{2}, \dots, T_{M}}}{\arg \min} \sum_{j = 1}^{M} \sum_{i = 1}^{N} \frac{{AK}_{j}}{12} \frac{α_{i, j}^{2} σ_{i, j}^{2}}{(B_{i, j} - A C_{j})} . & (9) \end{matrix}

[0036] Since Equation (6) involves the minimization of a convex function on a convex set, a unique solution to Equation (6) may be found using the method of Lagrange multipliers:

\begin{matrix} T_{i}^{*}, T_{2}^{*}, \dots, T_{M}^{*} = \underset{T_{1}, T_{2}, \dots, T_{M}}{argmin} \sum_{j = 1}^{M} \sum_{i = 1}^{N} \frac{{AK}_{j}}{12} α_{i, j}^{2} \frac{σ_{i, j}^{2}}{(B_{i, j} - A C_{j})} + λ (T - \sum_{j = 1}^{M} \sum_{i = 1}^{N} B_{i, j}), & (7) \end{matrix}

\begin{matrix} T_{j}^{*} = \frac{S_{j}}{\hat{S}} \frac{(T - AN \sum_{m = 1}^{M} C_{m})}{M} + {ANC}_{j}, & (8) \end{matrix}

[0038] where S_jis the following weighted sum of the standard deviations in the jth frame,

\begin{matrix} S_{j} = \sum_{i = 1}^{N} α_{i, j} σ_{i, j}, & (9) \end{matrix}

[0039] which can be interpreted as the energy in the jth frame, and Ŝ is the average of all the frame energies,

\begin{matrix} \hat{S} = \frac{1}{M} \sum_{i = 1}^{M} S_{j} . & (10) \end{matrix}

[0041] S₁≈S₂≈ . . . ≈S_j≈ . . . ≈S_M,

[0042] C₁≈C₂≈ . . . ≈C_j≈ . . . ≈C_M,

[0045] Frame Target Selection

[0047] Based on Equation (8), the following low-delay formula can be used for assigning a target number of bits T₀for the current frame:

\begin{matrix} T_{o} = {\begin{matrix} \frac{S}{\hat{S}} (B - \hat{V}) + V; & B > \hat{V} \\ \frac{S}{\hat{S}} B; & otherwise \end{matrix} & (11) \end{matrix}

[0049] B—Average Number of Hits Per Frame

[0050] B is the number of bits accepted by the communication channel during a frame interval. Specifically:

\begin{matrix} B = \frac{R}{F}, & (12) \end{matrix}

[0052] S—Energy of the Current Frame

S_{j} = \sum_{i = 1}^{N} σ_{i, j}^{2} .

[0054] Ŝ—Average Frame Energy

[0056] Ŝ=aŜ+(1−a)S, (13)

[0057] where the weight parameter a is a function of the desired maximum delay d (in seconds) introduced by the encoder buffer; for example:

\begin{matrix} a = {\begin{matrix} \frac{0.9}{0.5} d; & d < 0.5 \\ 0.9; & otherwise \end{matrix} & (14) \end{matrix}

[0058] In this example, when the delay d is below 0.5 seconds, the value of a decreases linearly with d. The formula for a is plotted in FIG. 4.

[0059] Typically, the buffer delay d is directly proportional to the size (in bits) of the encoder buffer, Buff, defined herein as Buff=d R.

[0060] V—Motion and Syntax Bit Overhead

[0062] {circumflex over (V)}—Average Motion and Syntax Bit Overhead

[0063] {circumflex over (V)} is the average number of bits per frame used for motion vectors and codec syntax in the video sequence,

\begin{matrix} \hat{V} = \frac{1}{M} \sum_{m = 1}^{M} V_{m}, & (15) \end{matrix}

[0065] {circumflex over (V)}=a{circumflex over (V)}+(1−a)V, (16)

[0066] where the weight parameter a is a function of the desired buffer delay d (in seconds) in the communication system, as described above.

[0067] Frame Target Selection for Very Low Delay

\begin{matrix} T_{o} \approx B = \frac{R}{F}, & (17) \end{matrix}

[0070] Buffer Protection

[0072] Level 1

[0074] T₁=T₀+Δ, (18)

[0075] where

\begin{matrix} Δ = {\begin{matrix} - \frac{W}{F}; & W > G \\ \frac{G - W}{F^{'}}; & otherwise \end{matrix}, & (19) \end{matrix}

[0076] and where:

[0077] W—Current number of bits in the encoder buffer

[0078] F—Frame rate of the video sequence in frames per second (e.g., 30 fps)

[0079] G—Desired number of bits in the encoder buffer.

\begin{matrix} G = {\begin{matrix} 0.5 Buff; & d > 0.5 \\ d Buff; & 0.1 < d \leq 0.5 \\ 0.1 Buff; & d \leq 0.1 \end{matrix} . & (20) \end{matrix}

[0082] F′—A parameter that depends on the frame rate F and the delay d, as follows:

\begin{matrix} F^{'} = {\begin{matrix} F; & d > 0.5 \\ \frac{F - 1}{0.4} (d - 0.1) + 1; & 0.1 < d \leq 0.5 \\ 1; & d \leq 0.1 \end{matrix} . & (21) \end{matrix}

[0084] Level 2

[0086] W′=max(W+T₁−B,0), (22)

[0089] if (W′>HBuff) T₂=HBuff−W+B;

[0090] else if (W′=0) T₂=−W+B;

[0091] else T₂=T₁. (23)

[0092] where T₂is the new target number of bits per frame (with level-2 protection) and H is the buffer threshold that can be set to a fixed value, or found using either of the two formulas below:

\begin{matrix} a) H = {\begin{matrix} 0.95 & R > 112000 \\ \frac{0.1}{0.102} R + \frac{85.7}{102} & 10000 < R \leq 112000 \\ 0.85 & R \leq 10000 \end{matrix} & (24) \\ b) H = 1 - \frac{p}{Fd}, & (25) \end{matrix}

[0093] where R, F, and d are the bit rate, frame rate, and delay, respectively, and p is a number between 0 and 1 (e.g., 0.1).

[0095] Buff−HBuff=p R/F,

[0096] (1−H)R d=p R/F, (26)

[0098] Encoder Block Diagram

[0103] Particular estimates in each estimation block of encoder 60 will generally be application-dependent, although the delay adaptive implementations described herein are preferred.

[0104] Experimental Results

[0112] Overall, SLA rate control is very robust for controlling the bit rate with small buffer sizes and overflows and underflows the buffer much less often than VM7's.

TABLE 1

Description of the video sequences, formats, bit rates and frame
rates used in the experiments. Each video sequence contained 300
frames at 30 frames per second and was downsampled at the encoding
frame rate. The left-most column shows the name given to each of
the experiments.

TABLE 2

Percentage of times that buffer overflow occurs in an MPEG4 codec
using SLA rate control (SLA) and VM7's (VM7) [13].

TABLE 3

Percentage of times that buffer underflow occurs in an MPEG4
codec using SLA rate control (SLA) and VM7's (VM7) [13].

[0113] Alternative Implementations

[0114] Several variations on the basic invention are described below.

[0115] One-pass

[0116] If the computation of the σ_k's used for finding S_jin Equation (9) cannot be done in advance, a good estimate for Sj such as the value of S from the previous video frame may be substituted.

[0117] Low-complexity Estimation of σ_i

[0118] In order to further reduce computational complexity, the formula for the standard deviation in Equation (2) may be approximated as

σ_{i, j} = \frac{1}{A} \sum_{l = 1}^{A} abs (P_{i, j} (l) - {\overline{P}}_{i, j}),

[0120] Encoding Intra and Inter Blocks

σ_{k} = {\begin{matrix} \frac{σ_{k}}{\sqrt{γ}} & if k th block is intra \\ σ_{k} & otherwise \end{matrix} .

[0122] The factor γ is

γ = \frac{K_{P}}{K_{I}},

[0124] Encoding a Group of Pictures (GOP)

[0125] In MPEG and H.263+codecs, there are different types of frames:

[0126] I frames, whose pixel values are encoded by themselves (or intracoded) without using a prediction from other frames in the video sequence.

[0127] P frames, whose pixels are predicted from a previous frame in the video sequence.

[0128] B frames, whose pixels are bi-directionally predicted using previous and future frames in the sequence.

[0129] A simple variation of equation (8) can be used to assign a target number of bits for each type of frame. For example, consider the typical case where the sequence or pattern of frame types is:

[0130] I,B, . . . ,B,P,B, . . . ,B,P,B, . . . ,B,P,B, . . . ,B,P, . . . (27)

[0131] The set of frames “B, . . . ,B,P” is repeated periodically after the first I frame. In MPEG, such a set (or any other that repeats periodically) is called a group of pictures or GOP.

[0132] GOP Type B, . . . ,B,P

\begin{matrix} T_{P} = \frac{S_{P}}{\hat{S}} \frac{(T - {ANMC}_{PB})}{N_{B} + 1} + {ANC}_{P}, & (28) \\ T_{B} = \frac{S_{B}}{\hat{S}} \frac{(T - {ANMC}_{PB})}{N_{B} + 1} + {ANC}_{B}, & (29) \end{matrix}

[0134] where the parameters in Equations (28) and (29) are equivalent to those in Equation (8). Specifically:

[0135] S_Pis the energy, Equation (9), for the P frame in the current GOP, which can either be measured or estimated as the average of the energies of P frames in previous GOP's.

[0136] S_Bis the average of the energies, Equation (9), for the B frames in the current GOP, which again can either be measured or estimated as the average of B frame energy in previous GOP's.

[0137] S is the (estimated) average of the energy in the GOP, i.e.,

\hat{S} = \frac{S_{P} + N_{B} S_{B}}{1 + N_{B}} .

C_{PB} = \frac{C_{P} + N_{B} C_{B}}{1 + N_{B}} .

[0139] Finally, T, M, and N are the total number of bits (for the GOP), frames (in the GOP), and macroblocks in a frame.

[0140] Equations (28) and (29) may be rearranged in an implementation. For example, after some lengthy but straightforward manipulations, equations (28) and (29) can be rewritten as follows:

\begin{matrix} T_{B} = \frac{T - AN (C_{P} - β C_{B})}{β + N_{B}}, & (30) \end{matrix}

T_P=T−N_BT_B, (31)

[0141] where

β = \frac{S_{P}}{S_{B}} .

[0142] Alternative Formulas for Estimating β

[0144] Method 1:

[0146] Method 2:

[0147] After a given frame is encoded, update the value of β as follows:

\begin{matrix} β = b β_{prev} + (1 - b) F \frac{S_{P}}{S_{B}}, & (32) \end{matrix}

\begin{matrix} F = \frac{c}{{Bpp}^{ψ}} + d, & (33) \end{matrix}

TABLE 4

Description of the experiments: names assigned to each experiment,
original video sequences, GOP pattern of frames, and target bit rates.
The spatial resolution of the video frames was QCIF and the frame rate
was of 15 frames per second. The bit rate achieved was very close to
the target in all cases. A total of five seconds were encoded for each
video sequence.

	TABLE 5

	TM5 Frame Layer	New Frame Layer

[0152] General GOP Type

\begin{matrix} T_{I} = \frac{S_{I}}{\hat{S}} \frac{(T - {ANMC}_{IPB})}{N_{I} + N_{P} + N_{B}} + {ANC}_{I}, & (34) \\ T_{P} = \frac{S_{P}}{\hat{S}} \frac{(T - {ANMC}_{IPB})}{N_{I} + N_{P} + N_{B}} + {ANC}_{P}, & (35) \\ T_{B} = \frac{S_{B}}{\hat{S}} \frac{(T - {ANMC}_{IPB})}{N_{I} + N_{P} + N_{B}} + {ANC}_{B}, & (36) \end{matrix}

[0154] which, once again, after some manipulations, can be re-written as follows:

\begin{matrix} T_{I} = \frac{(T - {ANMC}_{IPB})}{N_{I} + \frac{N_{P}}{β_{IP}} + \frac{N_{B}}{β_{IP} β_{PB}}} + {ANC}_{I}, & (37) \\ T_{P} = \frac{(T - {ANMC}_{IPB})}{N_{I} β_{IP} + N_{P} + \frac{N_{B}}{β_{PB}}} + {ANC}_{P}, & (38) \\ T_{B} = \frac{(T - {ANMC}_{IPB})}{N_{I} β_{IP} + N_{P} β_{PB} + N_{B}} + {ANC}_{B} . & (39) \end{matrix}

[0155] The parameters in Equations (37), (38), and (39) have the same meaning as in previous formulas. For example, {C_I, C_P, C_B} are the respective C's for I, P, and B frames, and:

\begin{matrix} C_{IPB} = \frac{N_{I} C_{I} + N_{P} C_{P} + N_{B} C_{B}}{N_{I} + N_{P} + N_{B}} . & (40) \end{matrix}

[0156] The values of the β's can be estimated with either Method 1 or 2 above. For example,

\begin{matrix} β_{IP} = b_{IP} β_{IP, prev} + (1 - b_{IP}) F_{IP} \frac{S_{I}}{S_{P}}, & (41) \\ β_{PB} = b_{PB} β_{PB, prev} + (1 - b_{PB}) F_{PB} \frac{S_{P}}{S_{B}}, & (42) \end{matrix}

[0157] where {b_IP, F_IP} and {b_PB, F_PB} are the respective estimator parameters, as in Equation (32).

Claims

Certificate of Correction present

The claims shown below may not include correction changes. Use the corrected PDF for authoritative text.

What is claimed is:

1. A method for allocating, among the image frames in an image frame sequence, the bits available for representing the image frame sequence, said method comprising the steps of:

defining a desired average frame target bit allocation B for a group of image frames;

estimating an average frame energy Ŝ using individual frame energy estimates for frames in the image frame sequence up to image frame i;

setting an individual frame target bit allocation T_ifor said individual image frame as

T_{i} = \frac{S_{i}}{\hat{S}} B,

T_{i} = \frac{S_{i}}{\hat{S}} (B - \hat{V}) + V_{i},

where {circumflex over (V)} is obtained by estimating the average overhead bits per image frame for said group.

2. A method for allocating, among the image frames in an image frame sequence, the bits available for representing the image frame sequence, said method comprising the steps of:

defining a desired average frame target bit allocation B for a group of image frames;

estimating the frame energy S_iof an individual image frame i selected from said group;

setting an individual frame target bit allocation T_ifor said individual image frame as

T_{i} = \frac{S_{i}}{\hat{S}} B,

T_{i} = \frac{S_{i}}{\hat{S}} (B - \hat{V}) + V_{i},

where {circumflex over (V)} is obtained by estimating the average overhead bits per image frame for said group.

4. The method of claim 3, wherein

a = {\begin{matrix} \frac{0.9}{0.5} d; & d < 0.5 \\ 0.9; & otherwise \end{matrix} .

5. A method for allocating, among the image frames in an image frame sequence, the bits available for representing the image frame sequence, said method comprising the steps of:

defining a desired average frame target bit allocation B for a group of image frames;

estimating the frame energy S_iof an individual image frame i selected from said group;

estimating an average frame energy Ŝ using individual frame energy estimates for frames in the image frame sequence up to image frame i;

setting an individual frame target bit allocation T_ifor said individual image frame as

T_{i} = \frac{S_{i}}{\hat{S}} B,

T_{i} = \frac{S_{i}}{\hat{S}} (B - \hat{V}) + V_{i},

7. The method of claim 6, wherein

a = {\begin{matrix} \frac{0.9}{0.5} d; & d < 0.5 \\ 0.9; & otherwise \end{matrix} .

8. A method for allocating, among the image frames in an image frame sequence, the bits available for representing the image frame sequence, said method comprising the steps of:

defining a desired average frame target bit allocation B for a group of image frames;

estimating the frame energy S_iof an individual image frame i selected from said group;

estimating an average frame energy Ŝ using individual frame energy estimates for frames in the image frame sequence up to image frame i;

setting an individual frame target bit allocation T_ifor said individual image frame as

T_{i} = \frac{S_{i}}{\hat{S}} B,

T_{i} = \frac{S_{i}}{\hat{S}} (B - \hat{V}) + V_{i},

where {circumflex over (V)} is obtained by estimating the average overhead bits per image frame for said group;

obtaining the current number of bits in an encoder buffer;

comparing the current number of bits in the encoder buffer to a desired number of bits in the encoder buffer, wherein said desired number of bits in the encoder buffer is a function of buffer delay;

computing an individual target bit allocation correction based on the comparing step; and

adding the individual target bit allocation correction to the individual frame target bit allocation T_i.

9. The method of claim 8, wherein G is the desired number of bits in the encoder buffer, d is a specified buffer delay, and Buff is the size of the encoder buffer,

G = {\begin{matrix} 0.5 Buff; & d > 0.5 \\ d Buff; & 0.1 < d \leq 0.5 \\ 0.1 Buff; & d \leq 0.1 \end{matrix} .