US 6,535,251 B1Grant
Video encoder and method for adjusting quantization step in real time
Issue Date:2003-03-18
•26 Claims
•8 Drawing Sheets
Abstract
A video encoder for encoding a series of groups of frames with an adjustable quantization step, and a method for adjusting the quantization step. The method tracks a complexity parameter of the encoded scenes, and computes a first quantization value in dependence upon the generated complexity parameter. The method further computes a minimum and a maximum step size in dependence upon a number of the bits that have already been generated, and upon the preset target number of bits. The quantization step for the next group of pictures is set in accordance with the first quantization value, but subject to the range defined by the minimum and maximum step sizes. The method further adjusts the minimum and the maximum step sizes.
Metadata
Assignee
- Sharplabs of America, Inc.
Inventor
- Jordi Ribas-Corbera
Application Information
Application Number:US 09/427,889
Filing Date:1999-10-26
Priority Date:1999-10-26
Art Unit:7
Classifications
IPC:
H04N 718
Patent Drawings (8 sheets)
Description
Background of the Invention
[0002] 1. Field of the Invention
[0003] The present invention is related to the field of coding a digital video signal in bits, and more specifically to coding at variable bit rate and quantization step size in order to achieve compression and high image quality.
[0004] 2. Description of the Related Art
[0005] Encoders that code digital video in bits achieve compression by choosing optimally a parameter called the quantization step size, also known simply as quantization step. The quantization step size is chosen to address the trade-off between a minimum required image quality and a maximum bandwidth for processing and/or transmission of data.
[0006] More specifically, using a larger, coarser quantization step size requires fewer bits to store a scene, but decreases image quality. Conversely, using a smaller, finer quantization step size requires more bits to encode the scene, but produces higher image quality. That is because, although the number of pixels is always the same, with a finer quantization the pixel “values” are encoded more accurately. Additionally, for a given quantization step size, the pixel values in simpler scenes are more correlated, and can be described with fewer bits than those in more complex scenes.
[0007] There are two main sets of encoding methods in the prior art. The first set of encoding methods, a.k.a. variable bit rate (VBR) mode, is now described with reference to FIGS. 1 and 2. Referring to FIG. 1, the quantization step size is plotted throughout many successive groups of pictures (GOP). (Each “group of pictures” is usually a group of 12-30 successive frames. The step size can generally change at each frame or image block, in which case FIG. 1 would illustrate the average step size per GOP.)
[0008] As can be seen, the quantization step size is maintained nearly uniform, which results in uniform image quality. However, the bit rate (seen in FIG. 2) varies according to scene complexity, hence the name variable bit rate (VBR) mode. When the scene is simpler, the bit rate decreases, and when the scene is complex, the bit rate increases.
[0009] The VBR mode is useful in asynchronous transmission mode (ATM). There, the next quantization step size is usually computed by tracking and examining slowly moving average statistics about the complexity of the scene in the frames. As such, the quantization step size can not react quickly to flashes or sudden scene changes, in order to prevent the buffer in the encoder from bit overflow. The tracked statistics typically include the produced bit rate, the target average bit rate, the quantization parameters that are used in previous frames, and other related parameters. More advanced methods use histograms of instantaneous bit rate of typical VBR video, and of other statistics.
[0010] The VBR mode is most useful for storing compressed video in CD-ROM or DVD. There are many approaches. The most complex ones encode an entire video frame sequence multiple times, each time with different quantization step sizes. Then, after examining the entire recorded sequences, a single set is selected or created, that has optimized the trade-off between the desired image quality and the desired number of bits. These methods are called multiple pass VBR control methods, and are quite effective in maintaining nearly constant quantization throughout the video sequence. However, these methods are not applicable to real-time encoding, since they result in long delays from the high computational complexity, and require extra memory using these delays.
[0011] The second set of prior art encoding methods is now described with reference to FIGS. 3 and 4. These methods are called constant bit rate (CBR) mode, and are intended for transmission through channels with fixed bandwidth. As such, they are most useful for real-time encoding. As can be seen in FIG. 3, the bit rate can be maintained nearly constant for many groups of pictures. However, the quantization step size has to keep changing rapidly, and can end up evolving as shown in FIG. 4. Unfortunately, the rapid quantization changes result in annoying fluctuations of the video image quality, which is a major drawback of the CBR mode.
[0012] A difficulty in CBR mode encoding is that a decision has to be made on the quantization step size of an upcoming frame without knowing in advance how complex is the scene. An average value is chosen to begin with, and then various algorithms are used to project a useful quantization step size. In fact, the value of the step size is often modified at each image block of a frame in order to further guarantee that the number of bits produced is close to the desired target. These algorithms typically use statistics for the instantaneous complexity of the scene, and are used to project and adapt the step size for the next scene.
Brief Summary of the Invention
[0013] The present invention overcomes these problems and limitations of the prior art.
[0014] Generally, the present invention provides a video encoder for encoding a series of groups of frames with an adjustable quantization step, and a method for adjusting the quantization step. The method tracks a complexity parameter of the encoded scenes, and computes a first quantization value in dependence upon the generated complexity parameter. The method further computes a minimum and a maximum step size in dependence upon a number of the bits that have already been generated, and with a preset target number of bits. The quantization step for the next group of pictures is set in accordance with the first quantization value, but subject to the range defined by the minimum and maximum step sizes.
[0015] The method further adjusts the minimum and the maximum step sizes to achieve fine tuned performance. The foregoing and other features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment which proceeds with reference to the drawings.
Brief Description of the Drawings
[0016] FIG. 1 is a graph of the quantization step size in a first set of encoding methods of the prior art, that controls the quantization step size to be nearly uniform throughout a video sequence.
[0017] FIG. 2 is a graph of the variable bit rate that results from controlling the quantization step size to be nearly uniform in the first set of encoding methods of FIG. 1.
[0018] FIG. 3 is a graph of the bit rate in a second set of encoding methods of the prior art, that controls the bit rate to be nearly constant throughout a video sequence.
[0019] FIG. 4 is a graph of the quantization step size that results from maintaining the bit rate to be nearly constant in the second set of encoding methods of FIG. 3.
[0020] FIG. 5 is a block diagram of a system that embodies the teachings of the present invention.
[0021] FIG. 6 is a flowchart showing a method according to the invention.
[0022] FIG. 7 is a graph illustrating the results of a method according to the invention of controlling adjustable maxima and minima for the quantization step size as a function of an updated error variable.
[0023] FIG. 8 is a diagram of the quantization step size for a series of GOPs when the maxima and minima are controlled according to the method whose results are shown in the graph of FIG. 7.
[0024] FIG. 9 is a known table showing a relation between quantizer codes and scales for linear and non-linear quantization for MPEG2 type coding.
[0025] FIG. 10 is a graph showing preferred settings of maximum quantization steps in dependence upon an error variable, for linear or non linear quantization scales in MPEG2.
[0026] FIG. 11 is a graph showing preferred settings of minimum quantization steps in dependence upon an error variable, for linear quantization scales in MPEG2.
[0027] FIG. 12 is a graph showing alternate preferred settings of maximum quantization steps in dependence upon a buffer percentage fullness variable, for linear or non linear quantization scales in MPEG2.
[0028] FIG. 13 is a graph showing preferred values for a threshold QT1of FIG. 12 in terms of an average bit rate and a number of macroblocks in a frame, for non linear quantization scales in MPEG2.
[0029] FIG. 14 is a diagram describing an overall behavior of a system of the invention in dependence upon setting a Speed variable.
[0030] FIG. 15 is a graph showing preferred settings of minimum quantization steps in dependence upon an error variable, for non linear quantization scales in MPEG2.
[0031] FIG. 16 is a graph showing preferred values for a threshold QT1of FIG. 15 in terms of an average bit rate a number of macroblocks in a frame, for non linear quantization scales in MPEG2.
Detailed Description of the Preferred Embodiment(s)
[0032] As has been mentioned, the present invention provides a video encoder for encoding a series of groups of frames with an adjustable quantization step, and a method for adjusting the quantization step.
[0033] An exemplary embodiment of the present invention is now described with reference to FIG. 5. A system 40 includes an encoder unit 42 and a decoder unit 44. Unit 42 is coupled with unit 44, optionally through a channel 46, as is known in the art. Depending on the application, the channel can be anything from a long distance transmission to a set of connections within a single apparatus.
[0034] Encoder unit 42 includes a video encoder 52, an encoder buffer 54, and an encoder rate control unit 56 that is made according to the present invention. Decoder unit 44 includes a decoder buffer 62, and the video decoder 64. In addition, a channel rate control unit 68 may be provided as is known in the art.
[0035] Encoder 52 includes a controllable quantizer for encoding video data according to an adjustable quantization step, thereby generating bits. A video signal VIDEO IN, which is a series of frames arranged in groups, is received by video encoder 52, which can be an MPEG encoder. The encoder also receives data from encoder rate control unit 56 regarding quantization step size. This way unit 56 controls the quantizer by setting the quantization step of the encoding unit at an adjustable value for the frames of each group.
[0036] The encoder encodes the video signal according to the received quantization step size, thereby producing a digital signal CODED VIDEO. Signal CODED VIDEO is then input in encoder buffer 54 at the rate that it is being produced by encoder 52.
[0037] Data is fed from encoder buffer 54 into channel 46 at a constant or variable rate. The data is then input in decoder buffer 62, and from there into video decoder 64 for final decoding (signal VIDEO OUT).
[0038] Control unit 56 can be a chip with programmable software. It can also be implemented in conjunction with unit 52. Unit 56 includes features that can be implemented in software, as will be obvious to a person skilled in the art in view of the present description. Frames in a GOP are coded as I-, P-, or B-type frames. The MPEG standard allows many combinations, but the most used sequence consists of 15 frames in a GOP (group of frames) that follow the pattern:
[0039] IBBPBBPBBPBBPBB
[0040] Since there are 30 frames per second, there are two GOPs like that per second. The invention works regardless of the sequence selected by the designer.
[0041] The first frame is I or intra coded. That means that it is coded by itself, without using any inputs from other frames. There are four P frames in the GOP. The pixel values for a given P frame are predicted from pixels in the previously coded P (or I) frame. Only the prediction error is coded, which typically requires substantially fewer bits than encoding a frame in intra mode. It should be noted that there are two B frames between two P frames (or between the first I and the first P). Each B frame is interpolated from the two closest P (or I) frames.
[0042] The features of unit 56 include means for generating a complexity parameter X for a scene from statistics of encoded frames occurring before the selected frame. For example, the complexity of a P frame, XP, is found by multiplying the bits produced by the last encoded frame of type P, Bitsp, and the average quantization step size used in the frame, Qp. In other words:
[0043] XP=Bitsp*Qp
[0044] The means for generating the complexity parameter generates complexity parameters XI, XP, XB for Ni I-type frames, Np P-type frames and Nb B-type frames. The means for computing the first quantization value computes the first quantization value. It computes the first quantization value preferably as an average of products Np*XP, Nb*XB and Ni*XI, by ascribing equal weights to product Ni*XI and to product Np*XP, and less weight to product Nb*XB than to product Ni*XI. These features will be better understood in conjunction with the method of the invention that follows.
[0045] The features of unit 56 further include means for computing a first quantization value in dependence upon the generated complexity parameter, means for computing a minimum and a maximum step size in dependence upon a number of the bits associated with the frames occurring before the selected frame, and with a preset or predetermined target number of bits. The priorly occurring frames could be in groups occurring before the groups of the selected frame. The target number of bits is determined by the desired video image quality. The features further include means for setting the quantization step in accordance with the first quantization value if the first quantization value is within a range defined by the minimum and maximum step sizes.
[0046] Optionally, unit 56 further includes means for decreasing the computed maximum step size if the computed maximum step size exceeds a hard ceiling value, and means for increasing the computed minimum step size, if the computed minimum step size is lower than a hard floor value. The hard ceiling and floor values are preferably fixed.
[0047] The method of the invention is now described with reference to flowchart 100 of FIG. 6.
[0048] According to step 110, model parameters are considered for the upcoming initialization. The model parameters are made for a model GOP (group of frames or group of pictures), and are carried for all the other groups. The method encodes a GOP with similar quality using a typical video coder such as MPEG2. This can be achieved by encoding all frames with the same quantization step size Q.
[0049] The number of bits produced for the frame, Bits, decreases with large values of Q. The following typical model relates Bits and Q:
[0050]
[0051] where X is the complexity parameter for the frame, which is different for I, P and B frames. Hence, if BGOPis the total number of bits for a GOP:
[0052] where NI, NP, NBis the number of I, P, and B frames in the GOP. From Equation (2), Q is isolated to obtain an expression for the value of Q that will encode all the frames in a GOP with BGOPbits:
[0053] Then, according to step 120 of FIG. 6, values are initialized. In the preferred embodiment they are initialized as follows:
[0054] RMAX—Maximum bit rate of the channel or storing device.
[0055] RAVG—Target bit rate (in bits per second) desired on average (must be less than RMAX)
[0056] F—Frame rate. Typically F=30 frames per second.
[0057] N—Number of frames in a GOP, i.e., N=NI+Np+NB.
[0058] BAVG—Average number of bits for GOP, i.e., BAVG=N RAVG/F.
[0059] BMAX—Maximum value allowed for BGOP. We set BMAX=1/1.2 N RMAX/F.
[0060] Speed—Convergence speed to target bit rate.
[0061] Bfull—Fullness of the encoder buffer.
[0062] Bsize—Size of the encoder buffer.
[0063] ActualBGOP—Actual number of bits used in GOP.
[0064] Errorbits—Error number of bits from average.
[0065] In addition, the rate control parameters are initialized as follows:
[0066] BGOP=BAVGBGOPis initially set to the number of bits for a GOP.
[0067] Q=4 is the initial quantization step size or scale (it should depend on RAVG).
[0068] PrevQ=Q The value of the previous quantization step size is initialized to Q.
[0069] XI=XP=XB=0 The frame complexities are initialized to zero.
[0070] Speed=120 The convergence speed is 120 GOPs.
[0071] Bfull=0 The encoder buffer is assumed to be empty at the beginning.
[0072] VBVdelay=ffff VBVdelay must be set to this value (in hex.) for MPEG2 VBR video.
[0073] Qc=31 defines a hard ceiling for the quantization step size
[0074] QMAX=QCby default, start at the hard ceiling
[0075] QF=1 defines a hard floor for the quantization step size
[0076] QMIN=QFby default, start at the hard floor
[0077] Errorbits=0 counter for the group
[0078] Then a subprocess starts for each group of frames, until all groups in the series are processed. More specifically, according to step 130 of the invention, a counter is initialized for the group:
[0079] ActualBGOP=0 counter for the group
[0080] According to step 140 of the invention, the quantization step size Q for encoding the upcoming frame is selected. This is accomplished by computing a first quantization value Q1. This computation is in dependence upon the generated complexity parameters XI, Xp, XBfrom previous scenes.
[0081] If (XIXPXB>0) the first quantization value is computed by Equation (3) as was given above:
[0082] else Q=PrevQ.
[0083] The above formula gives the first quantization value as an average value sum. A preferred method is to alter slightly Equation (3), to take advantage of inter-frame dependencies. This is accomplished by decreasing the importance of the quantization step size of B frames relative to that of I and P frames. This technique improves the video quality because relatively more bits are spent in frames that are used to predict others. In order to keep the visual quality nearly uniform, the step size of the B frames can be increased only up to some point. Specifically, using experiments with human subjects, it was found that when the step size for B frames QBis computed by:
[0084]
[0085] There are no noticeable differences in image quality between B frames and the others. We will then use the formula for QBto set the quantization step size for B frames. To incorporate this into the general framework, Equation (3) is modified as follows:
[0086] In comparison to Equation (3), XBis multiplied by 4/5, and the value of Q for I and P frames is made smaller, thus these frames will be encoded with higher quality. Since the B frames will be perceived as having the same quality as the others, the overall video quality will improve.
[0087] Then, according to step 150, an adjustment occurs that places Q within the allowable range. In other words, the quantization step is set equal to the first quantization value Q1, computed immediately above, but subject to the condition that the quantization step size be within an allowable range.
[0088] The allowable range is between QMINand QMAX. It should be remembered that a feature of this invention is that QMAX, QMINcan be updated by computing. This updating is described with reference to a later step.
[0089] So, first set Q=Q1. Then, if Q>QMAX, set Q=QMAX. In other words, if the first quantization value exceeds the computed maximum step size, setting the quantization step size lower than the first quantization value. In addition, it is preferred to set Q=QMAXonly if BGOP<BMAX.
[0090] As a practical matter, the target number of bits for a given GOP, BGOP, will be below or above the average BAVG. If the encoder has encountered difficult scenes, Errorbits will likely be negative, and BGOPwill be lower than BAVG. On the other hand, if the previous scenes were easy to encode, Errorbits will be positive and hence BGOPwill be larger than BAVG. At high bit rates, cases were encountered where Errorbits was so large than BGOPwas larger than that allowed by the peak bit rate, and hence this caused the encoder buffer to overflow. In other words, the encoder had saved so many bits that it was spending too many at once. To avoid this, BGOPis limited to be less than or equal to BMAX. As such, when BGOPis equal to BMAX, it is preferable to not impose the QMAXlimitation on Q. This is because when the produced bit rate is so close to the maximum, adding any upper limit on Q can also easily result in buffer overflow.
[0091] Additionally, If Q1<QMIN, set Q=QMIN. In other words, if the first quantization value is lower than the computed minimum step size, the quantization step size is set higher than the first quantization value.
[0092] The minimum and maximum step sizes are also known simply as a minimum and a maximum step, respectively.
[0093] Then, according to step 160, the frame is encoded using the set quantization step size Q. The quantization step can be computed after every frame, or after every group of frames. Then bit counters are updated, and the scene complexity parameters X are also updated as is known in the art. Let Bits be the number of bits occupied by the current frame.
[0094] ActualBGOP=ActualBGOP+Bits.
[0095] Bfull=max(0, Bfull+Bits−RMAX/N).
[0096] XT=Q·Bits. T is the frame type,i.e.,T is in {I,P,B}.
[0097] PrevQ=Q.
[0098] According to a subsequent step 170, it is inquired if that were the last frame in the GOP. If not, the process returns to step 140, as above.
[0099] Once the last frame of the GOP has been processed, updating takes place as per step 180. Specifically,
[0100] Errorbits+=BAVG−ActUalBGOP.
[0101] BGOP=BAVG+Errorbits/Speed . If BGOP>BMAX, set BGOP=BMAX.
[0102] According to a next step 190 of the invention, a new maximum step size QMAXis computed in dependence upon a number of the bits associated with the frames of the group, and upon a preset target number of bits. In addition, a minimum step size QMINis computed in dependence upon the number of the bits associated with the frames of the group, and upon, the preset target number of bits. These new maximum and minimum step sizes will be used again for processing the frames of the next group, in step 150. Detailed processes for performing this step 190, along with results, are described below.
[0103] According to a subsequent step 200, it is inquired if that were the last GOP in the series. If not, the process continues to step 130, as above. Else the process terminates.
[0104] Detailed processes are now described for performing this step 190. In general, the computed maximum step size should not be allowed to exceed the precomputed or preset hard ceiling value QC, which is necessary for some encoding methods, such as MPEG2. Similarly, the computed minimum step size should not be allowed to be below the precomputed or preset hard floor value QF. As such, if the values for QMAX, QMINare computed to be outside that range, the computed values are adjusted accordingly.
[0105] The preferred method for controlling QMAX, QMINnow described also with reference to FIG. 7. A usage variable PERR, also known as percentage of error PERR, is defined as follows:
[0106] If PERRis positive, the produced bit rate is lower than the target bit rate. If negative, the rate is higher than the target. In general, and as a matter of good practice, PERRshould not be too far from zero, so that the produced bit rate is reasonably close to the target. Although this is relative to the value of Speed, i.e., the same value of PERRcorresponds to lower Errorbits when Speed is small.
[0107] Referring still to FIG. 7, QMAXand QMINare made to depend on PERR. Each dependency accomplishes a different function.
[0108] Adjusting the QMAXaccording to PERRaccomplishes quality protection. Using empirical experiments with human subjects, a maximum quantization step size threshold QT1was determined, that ensures good visual quality. It the step size is larger than QT1, compression noise is often visible and annoying. In order to protect image quality, if the produced bit rate is not far from the average (i.e., if BGOPis close to BAVG), the maximum quantization step size is set as QMAX=QT1, instead of as equal to QC. This could be set in the initialization step 120 of FIG. 6 as well.
[0109] In practice, using 15-20 percent higher or lower bit rate typically does not produce any noticeable improvements or degradations in visual image quality. This is because the changes in image quality are still within the visual threshold. To take advantage of this property, QMAX=QT1until the percentage of bit error is within 20 percent, as shown in FIG. 7.
[0110] When a video scene is complex, Q will be limited by QT1for some time, and PERRwill be negative and decreasing. If the scene is long, at some point QMAXwill have to be increased to avoid having a large (negative) bit error PERR. Then Q will likely take values larger than QT1, and compression artifacts will become noticeable. From experience, once compression noise is visible, it does not matter too much whether QMAXis a little higher or quite higher than QT1, since the user will notice annoying compression noise in both cases.
[0111] Adjusting the QMINaccording to PERRaccomplishes Bit rate protection. From experiments with human subjects, it was also observed that when the quantization step size Q is below some threshold QT2, the visual quality is already so good, that decreasing the step size does not produce a significant improvement in visual quality. The invention takes advantage of this property by making the minimum quantization step size QMINto be larger than or equal to QT2for most values of PERR. By keeping the step size above such limit, there is a “saving of bits” from easy video scenes, for future scenes that may need them. As in the previous section, this should be done only when PERRis small. If PERRis a positive large number, too many bits will have been saved, and hence QMINwill need to decrease, as seen in FIG. 7. Again, the hard floor value QFshould be respected.
[0112] As can be seen in FIG. 7, the resulting maximum and minimum step sizes allow a range DQ for the step size. The range changes as PERRchanges.
[0113] Referring to FIG. 8, the resulting algorithm is now discussed. In the horizontal axis there is time, as measured by groups of frames in the sequence. In the vertical axis there is the quantization step size Q that results from the process of the invention. It will be appreciated that Q initially varies between the thresholds QT1 and QT2. However, these thresholds are somewhat flexible and can be moved, as per the discussion associated with FIG. 7. In fact, it will be appreciated how FIGS. 7 and 8 cooperate.
[0114] If the value of Speed is small (e.g., 2 or 3), the method above will practically become a CBR rate control technique, because the bit errors in previous GOPs will promptly impact the selection of Q for the frames in the next GOP. But since Speed=120 is large, when the current GOP occupies more bits than the target average BAVG, the impact of spending those extra bits will be distributed within the next 120 GOPs. As a result, if there is a scene change or a flash, the method of the invention will not be affected as much. Nevertheless, since BGOPwill be fairly close to BAVG, the control unit of the invention will still increase or decrease Q rapidly according to scene complexity, because as soon as an I, P, and B frame of a new scene are encoded, the value of Q will be adapted to the new scene conditions.
[0115] As will be appreciated from this description, the preferred embodiment of the invention is a VBR method with the capability of reaction of a CBR method. Indeed, the method of the invention selects a quantization step Q using the above described near-CBR method, and limits Q when appropriate to operate in VBR mode. These limits only affect the quality bounds and the average bit rate, but not the method's capability of reaction.
[0116] Setting an optimum value for the Speed is also discussed below.
[0117] The above illustrate examples of how to adapt the maximum and minimum quantization step sizes QMAXand QMINwhile encoding for general cases. However, in many encoders (e.g., MPEG2) the step sizes are usually selected indirectly by setting quantization scales, and hence the above should be adapted to such scales, instead of the step sizes. Moreover, these curves should adapt to the different coding conditions such as the average bit rate RAVGand the maximum bit rate RMAX. For example, if RMAXis closer to RAVG, QMAXshould increase faster to reduce the instantaneous peaks of bit rate.
[0118] In MPEG2, the quantization step size for each DCT coefficient is determined by the quantization type, scale, and matrix. For instance, the type of quantization can be either linear or non-linear, and the quantization code determines the quantization scale as shown in Table 300 of FIG. 9.
[0119] For linear quantization scales in MPEG2, the values for QMAXare given in FIG. 10, and the values for QMINare given in FIG. 11. They are shown as they depend upon the error variable PERR. It can be seen that they are generally similar to the upper left and lower right portions of the graph of FIG. 7 respectively, except that they are particularized for MPEG2 encoding and decoding.
[0120] Whenever a rate control strategy limits the maximum value of the quantization step size, there is an increased danger of encoder buffer overflow. To avoid this problem, the encoder of the invention tracks the fullness of the encoder buffer, and makes adjustments when the buffer is nearly full. In another embodiment, the encoder monitors the fullness of the decoder buffer, since the fullness of decoder and encoder buffer are inversely related (e.g., when the encoder buffer overflows, the decoder buffer underflows).
[0121] To overcome the problem of encoder buffer overflow, the method of the invention is preferably adapted to react quickly, by increasing quantization whenever the encoder buffer becomes full. One of the key advantages of the invention is that it can so react, because it is a constrained CBR technique. Specifically, when there is danger of buffer overflow, QMAXcan be increased (i.e., relax the constraints), and the method will increase the quantization step size accordingly.
[0122] This is implemented as follows: A variable PBUFis defined to be the percentage of fullness in the encoder buffer. A second function is defined for QMAXas applied to MPEG2 encoding, that is seen in FIG. 12. The second function increases QMAXaccording to PBUFIn practice, the value of QMAXcan be set to be the largest of the values from FIGS. 10 and 12.
[0123] For more safety, one can measure the value of PBUFafter each frame is encoded (or even after each macroblock is encoded), and then modify the value of QMAXaccording to FIG. 12.
[0124] For additional safety, one could also increase QMINwhenever there is danger of buffer overflow.
[0125] Next, the method is adapted to different coding conditions, by adjusting the values of the parameters QT1, QT2, and Speed, in dependence upon the target average bit rate RAVGand the maximum or peak bit rate RMAX. These values remain fixed for the entire coding session, since RAVGand RMAXare also fixed.
[0126] Referring to FIG. 13, setting the value of QT1is discussed. QT1is discussed in terms of RAVG/(25M). RAVGis the average bit rate in bits per second and M is the number of macroblocks in a frame. If the video frame rate is 25 frames per second, the fraction RAVG/(25M) is the average number of bits per macroblock. When the video resolution is full-D1, 75 and 106 correspond to 2.5 and 3.5 Megabits per second (Mbps), respectively.
[0127] As seen in FIG. 13, it is advantageous to usually set QT1=4. This value was determined empirically by setting the quantization scale fixed to different values, and selecting the maximum scale that produced good visual image quality. At low bit rates QT1is increased, because then it is very difficult to maintain the quantization scale below 4.
[0128] The value Of QT2is preferably set at QT2=QT1−1. This choice is also based on empirical experiments. Fortuitously, in this linear case the range of quantization scales is only 1. As will be seen below, in non-linear quantization, there are more scales available for the same range, and hence there may have be some additional benefits for bit rate and quality control.
[0129] The last setting is that of the Speed variable. It can be either an input that can be adjusted, or set at a value. If set, its repercussions are described also with reference to FIG. 14. It is advantageous to consider the speed in terms of an additional variable P defined as follows:
[0130] P=10 RMAX/RAVG
[0131] Setting the Speed will ultimately result in CBR-type operation or VBR type operation, as seen from FIG. 14, which was tuned using empirical experiments. When the maximum bit rate RMAXis close to the average RAVG(i.e., P is closer to 10), the coding conditions become closer to those of CBR video. Hence, when P is closer to 10, it is best to adapt quantization faster, to protect from large instantaneous bit rates and encoder buffer overflow. This is accomplished by reducing the value of Speed for lower values of P, so that BGOPand PERRare more sensitive to bit rate errors. Since BGOPwill vary quickly, the quantization scale Q will adapt faster. Also, the QMAXand QMINconstraints will relax, since PERRwill usually fluctuate quickly between large positive and negative values.
[0132] From FIG. 14, it is observed that when P is smaller than 13, it can be advantageous to turn off the VBR mode of the encoder, and use true CBR rate control. This is because there is little benefit from using VBR rate control when the maximum and average bit rates are close.
[0133] Finally, it is noted that smaller values of Speed will also make the produced bit rate and the target average RAVGcloser on average, and hence Speed should be reduced for a more accurate video time length. For example, consider the case that the coded bit stream is being stored on a tape (or disc) of limited capacity. In order to guarantee that the tape will contain a given number of seconds of encoded video, Speed should be gradually reduced at the end of the tape.
[0134] Non linear quantization is now described. Non-linear quantization was adopted in MPEG2 in order to allow better quantization control when encoding video at high bit rates. To do this, the non-linear case provides smaller scale increments for the quantization codes between 1 and 8, as shown in Table 300 of FIG. 9. Additionally, non-linear quantization permits very large values of quantization scales, which may be useful when encoding video segments that are hard to compress.
[0135] It is experimentally found that the data of FIGS. 10, 12 and 14 applies equally well for non linear quantization. However, the data of FIGS. 11 and 13 is best replaced with that of FIGS. 15 and 16 respectively.
[0136] Further, for non-linear quantization, it is empirically determined that it is best to set QT2=QT1−2. Since non-linear quantization provides more scales for the same range, a wider range of quantization scales is available.
[0137] The results of tests were positive. When the scale increments are smaller in the non-linear case, the bit rate changes are also smaller, and hence the non-linear buffer does not fill as often. As a result, the chances that buffer overflow will occur are smaller for non-linear quantization.
[0138] As per the above, when the buffer is running rather full, e.g. above 30%, the maximum quantization value QMAXis controlled by the buffer fullness PBUF, as shown in FIG. 12. Since PBUFcan fluctuate wildly in the VBR case, QMAXand the quantization parameter Q will also fluctuate significantly from frame to frame. As a result, the video quality will fluctuate significantly as well.
[0139] Another embodiment of the invention is now described. The previously described VBR rate control technique is modified so that the quality of the encoded video is always high. This mode of operation is also known as the “quality-guaranteed” mode. For convenience, from now on the previous rate control mode will be referred to as VBR1, and the new (quality-guaranteed) mode as VBR2.
[0140] VBR2 is somewhat similar to VBR1, except that in VBR2 the quantization parameter Q is always constrained to be equal or lower than QMAX=QT1, even when the bit error is large. Consequently, the video image quality will always be good. The QMAX=QT1constraint is relaxed when there is danger of buffer overflow, i.e., when the produced bit rate is larger than the peak bit rate. Then, the video quality of the encoded video will degrade. Hence, in order to avoid bad quality video, the peak rate needs to be high enough to permit a quantizer below QT1for most video scenes.
[0141] A disadvantage of the VBR2 mode is that the time or bit error can be very large. In fact, with the VBR2 approach one can only guarantee a minimum time-length of recording time, which is determined by the peak bitrate.
[0142] As such, for VBR2 the diagram of FIG. 8 is shaped by the following maximum and minimum constraints:
[0143] For minimum, QMIN=QT2. This saves bits even when the percentage of bit error PERRis a large positive value. The rationale behind such change is that, since only a minimum recording time can be guaranteed, it may be just as well to save as many bits as possible to have the video recording time as long as possible.
[0144] For maximum, QMAX=QT1. As discussed above,this guarantees that the image quality is good, even when the percentage of bit error PERRis a large negative value. However, and only when the buffer fills up, QMAXwill increase above QT1according to FIG. 12, in order to prevent buffer overflow. In other words, the method for setting the quantization step also comprises storing the generated bits in the buffer, and tracking how many bits are stored in the buffer. Then a buffer fullness is monitored as the tracked number of bits stored in the buffer in relation to a preset buffer capacity. The maximum step is computed in dependence upon the buffer fullness. But even that is subject to a preset hard ceiling, as per FIG. 12.
[0145] A variation of the VBR2 method is as follows: The value of Errorbits is limited, so that PERRis never smaller than −30. This is done because PERRcan decrease too much the value of BGOP(which is the target average number of bits for a GOP). Specifically, if PERRhas a very large negative value, BGOPwill become quite small, and hence the reaction to The prevent buffer overflow could be too strong, producing unnecessarily high compression noise when the buffer is full.
[0146] In the VBR2 method, although the target average bit rate cannot be guaranteed (and that is because Q is constrained to take values between QT1and QT2), BGOPwill affect the “unconstrained” value of Q. As a result, Q will tend to be larger (i.e. closer to QT1) when the target average bit rate is low, and smaller (i.e. closer to QT2) when the target is high. Additionally, the error bits will affect the value of BGOPUP to some point (up until PERRis no less than −30). Therefore, the desired target average bit rate should be always set as a parameter in the encoder, in order to achieve a bit rate as close as possible to the desired target. More specifically, the average bit rate parameter should either be equal or maybe a little lower than the desired average target, but not larger.
[0147] The VBR2 mode was tested with different average and peak bit rates in a wide variety of video scenes. The default average and peak bit rates were set to 4.5 and 9 Mbps, respectively. It was observed that VBR2 encoded the scenes with good image quality, even throughout difficult segments, while preventing buffer overflow.
[0148] Yet another optional feature of the invention can ensure that the quality of pictures will not fluctuate quickly. This is implemented by computing a time integral of a buffer fullness indicator PBUF, and adjusting the base value QT1in dependence upon the time integral. In other words, the maximum step size is computed in further dependence upon the time integral of PBUF. More particularly, the base value of QMAX(QT1in FIG. 7) is increased when PBUFis above 30 percent for too long.
[0149] Specifically, the following technique is used before encoding a GOP
[0150] 1. Set a new variable INC=0. If this is the first GOP, set CPOS=CNEG=0. Otherwise, set CPOS equal to the number of frames in the previous GOP where the buffer fullness was above 30 percent, and set CNEG equal to the number of frames in the previous GOP where the buffer fullness was zero.
[0151] 2. Increase INC by one unit if CPOS is greater than ¼thof the frames in a GOP.
[0152] 3. Decrease INC by one unit if CNEG is equal to the number of frames in a GOP.
[0153] 4. Constrain INC to take values in {0,1,2}.
[0154] 5. Use QT1+INC instead of QT1in FIG. 7 (or 10), and also in FIG. 12. Note that the value of QT2depends only on QT1, and hence QT2should not change with INC.
[0155] A person skilled in the art will be able to practice the present invention in view of the present description, where numerous details have been set forth in order to provide a more thorough understanding of the invention. In other instances, well-known features have not been described in detail in order not to obscure unnecessarily the invention.
[0156] While the invention has been disclosed in its preferred form, the specific embodiments thereof as disclosed and illustrated herein are not to be considered in a limiting sense. Indeed, it should be readily apparent to those skilled in the art in view of the present description that the invention can be modified in numerous ways. Applicant regards the subject matter of the invention to include all combinations and sub-combinations of the various elements, features, functions and/or properties disclosed herein. The following claims define certain combinations and subcombinations, which are regarded as novel and non-obvious. Additional claims for other combinations and subcombinations of features, functions, elements and/or properties may be presented in this or a related application for patent. Such additional claims are also regarded as included within the subject matter of applicant's invention irrespectively of whether they are broader, narrower, or equal in scope to the original claims.
Claims
Certificate of Correction present
The claims shown below may not include correction changes. Use the corrected PDF for authoritative text.
The invention claimed is:
1. For use in a video encoding apparatus that receives a series of frames and encodes the frames according to an adjustable quantization step, the video encoding apparatus thereby generating bits associated with the frames, a method for setting the quantization step for encoding a current frame, the method comprising:
gent rating at least one complexity parameter for at least one encoded frame occurring prior to the current frame in the series;
computing a first quantization value in dependence upon the generated complexity parameter;
computing a range of allowable quantization values, the range dependent upon Perra measure of the variation between a preset target number of bits and an actual number of hits encoded; and
setting the quantization step for the current frame to the first quantization value, constrained by the range of allowable quantization values.
2. The method of claim 1, wherein the frames are arranged in groups, and wherein the quantization step is set once for each group.
3. The method of claim 1, wherein the frames are arranged in groups, further comprising computing the range of allowable quantization values once per group.
4. The method of claim 1, wherein
the maximum step is computed in further dependence upon a time integral of a buffer fullness indicator.
5. The method of claim 1, wherein:
the frames are designated as one of I-type, P-type and B-type,
complexity parameters XI, XP, XB are generated for Ni I-type frames, Np P-type frames and Nb B-type frames, and
the first quantization value is computed in dependence upon the complexity parameters XI, XP, XB.
6. The method of claim 5, wherein the first quantization value is computed as an average of products Np*XP, Nb*XB and Ni*XI, by ascribing equal weights to product Ni*XI and to product Np*XP, and less weight to product Nb*XB than to product Ni*XI.
7. A video encoder for encoding a series of frames, comprising:
an encoder unit including a controllable quantizer which encodes video data according to an adjustable quantization step, thereby generating bits; and
an encoder rate control unit for controlling the quantizer by setting the quantization step of the encoder unit at an adjustable value for encoding a current frame, the control unit including:
means for generating a complexity parameter for at least one encoded frame occurring prior to the current frame in the series,
means for computing a first quantization value in dependence upon the generated complexity parameter,
means for computing a range of allowable quantization values, the range dependent upon Perr, a measure of the variation between a preset target number of bits and an actual number of bits encoded, and
means for setting the quantization step in accordance with the first quantization value, constrained by the range of allowable quantization values.
8. The encoder of claim 7, wherein the frames are arranged in groups, and wherein the means for setting the quantization step sets the quantization step once for each group.
9. The method of claim 7, wherein the frames are arranged in groups, wherein the means for computing a range of allowable quantization values computes the range once per group.
10. The video encoder of claim 7, wherein the control unit further includes
means for computing a time integral of a buffer fullness indicator,
and wherein the means for computing the maximum step is responsive to the means for computing the time integral.
11. The video encoder of claim 7, wherein
the frames are designated as one of I-type, P-type and B-type,
the means for generating the complexity parameter generates complexity parameters XI, XP, XB for Ni I-type frames, Np P-type frames and Nb B-type frames, and
the means for computing the first quantization value computes the first quantization value in dependence upon the generated XI, XP, XB.
12. The video encoder of claim 11, wherein the means for computing the first quantization value computes the first quantization value as an average of products Np*XP, Nb*XB and Ni*XI, by ascribing equal weights to product Ni*XI and to product Np*XP, and less weight to product Nb*XB than to product Ni*XI.
13. The method of claim 1, wherein Perrcomprises a fraction of the total difference between the preset target number of bits and the actual number of bits encoded, the fraction scaled by a settable convergence speed parameter Speed.
14. The method of claim 13, wherein Speed depends on a channel overhead measure, the channel overhead measure expressing a ratio between a maximum channel bit rate and in average target bit rate.
15. The method of claim 13, wherein computing a range of allowable quantization values comprises setting the upper end of the range to a first constant that achieves a minimum perceived visual quality, for values of Perrabove a preset negative threshold.
16. The method of claim 15, wherein for values of Perrbelow the preset negative threshold, computing a range of allowable quantization values comprises increasing the upper end of the range towards a hard ceiling as Perrdecreases.
17. The method of claim 13, wherein computing a range of allowable quantization values comprises setting the lower end of the range to a second constant that achieves a maximum perceived visual quality, for values of Perrbelow a preset positive threshold.
18. The method of claim 17, wherein for values of Perrabove the preset positive threshold, computing a range of allowable quantization values comprises decreasing the lower end of the range towards a hard floor as Perrincreases.
19. The method of claim 1, further comprising:
track sing the used capacity of an encoded bit buffer,
calculating an alternate range of allowable quantization values in dependence upon the tracked capacity of the encoded bit buffer; and
when the alternate range of allowable quantization values is more restrictive than the computed range of allowable quantization values, decreasing the range of allowable quantization values to conform to the alternate range.
20. The encoder of claim 7, wherein the means for computing a range of allowable quantization values calculates Perras a fraction of the total difference between the preset number of bits and the actual number of bits encoded, the fraction scaled by a settable convergence speed parameter Speed.
21. The encoder of claim 20, wherein Speed depends on a channel overhead measure, the channel overhead measure expressing a ratio between a maximum channel bit rate and an average target bit rate.
22. The encoder of claim 20, wherein the means for computing a range of allowable quantization values sets the upper end of the range to a first constant that achieves a minimum perceived visual quality, for values of Perrabove a preset negative threshold.
23. The encoder of claim 22, wherein the means for computing a range of allowable quantization values increases the upper end of the range towards a hard ceiling as Perrdecreases, for values of Perrbelow the preset negative threshold.
24. The encoder of claim 20, wherein the means for computing a range of allowable quantization values sets the lower end of the range to a second constant that achieves a maximum perceived visual quality, for values of Perrbelow a preset positive threshold.
25. The encoder of claim 24, wherein the means for computing a range of allowable quantization values decreases the lower end of the range towards a hard floor as Perrincreases, for values of Perrabove the preset positive threshold.
26. The encoder of claim 7, further comprising:
means for tracking the used capacity of an encoded bit buffer; and
means for calculating an alternate range of allowable quantization values in dependence upon the tracked capacity of the encoded bit buffer;
wherein the means for computing a range of allowable quantization values decreases the range of allowable quantization values to conform to the alternate range of allowable quantization values, when the alternate range is more restrictive than the computed range.
Patent Citations (13)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US5028999(A) | 1991-07-01 | Vogel | Applicant |
| US5038209(A) | 1991-08-01 | Hang | Applicant |
| US5159447(A) | 1992-10-01 | Haskell et al. | Applicant |
| US5426463(A) | 1995-06-01 | Reininger et al. | Applicant |
| US5479210(A) | 1995-12-01 | Cawley et al. | Applicant |
| US5543853(A) | 1996-08-01 | Haskell et al. | Applicant |
| US5612900(A) | 1997-03-01 | Azadegan | Applicant |
| US5675384(A) | 1997-10-01 | Ramamurthy et al. | Applicant |
| US5754236(A) | 1998-05-01 | Lee | Applicant |
| US5764293(A) | 1998-06-01 | Uz et al. | Applicant |
| US5848057(A) | 1998-12-01 | Lee et al. | Applicant |
| US6173012(B1) | 2001-01-01 | Katta et al. | Examiner |
| US6229849(B1) | 2001-05-01 | Mihara | Examiner |
Non-Patent Literature (9)
- “A VBR rate control algorithm for MPEG-2 video coders with perceptually adaptive quantisation and traffic shaping,” by Mark R. Pickering et al., Signal Processing: Image Communications 11, 1997, pp. 1-19.Applicant
- “A Perceptually Efficient VBR Rate Control Algorithm,” by Mark R. Pickering et al., IEEE Transactions on Image Processing, vol. 3, No. 5, Sep. 1994, pp. 527-532.Applicant
- “Lexicographic Bit Allocation for MPEG Video,” by Dzung T. Hoang et al., Journal of Visual Communication and Image Representation, vol. 8, No. 4, Article No. VC970376, Dec. 1997, pp. 384-404.Applicant
- “A Lexicographic Framework for MPEG Rate Control,” by Dzung T. Hoang et al., 1997 IEEE Data Compression Conference, 1997, 10 pages.Applicant
- “VBR Video: Tradeoffs and Potentials,” by T.V. Lakshman, et al., Proceedings Of the IEE, vol. 86, No. 5, May 1998; pp. 952-973.Applicant
- “Jointly Optimal Video Coding and Rate Control for Variable-Bit-Rate Transmission,” by David W. Lin, 0-8186-8821-1/98 IEEE, 1998, pp. 939-943.Applicant
- “Maximally Flat Bandwidth Allocation for Variable Bit Rate Video,” by Sanghoon Lee et al., 0-8186-8821-1.98 IEEE, 1998, pp. 346-350.Applicant
- “Test Model 5, Rate Control and Quantization Contol,” printed Aug. 12, 1999 from website:www.mpeg.org/MPEG/MSSG/tm5/, 7 pages.Applicant
- “1 pass VBR control method for MPEG-2 Video Encoder,” by Yutaka Yokoyama et al., 1999 Conference on Electronics, Information, and Communication, 2 pages.Applicant