Bit rate control mechanism for digital image and video data compression

A bit rate control mechanism for a digital image or video compression system estimates a complexity parameter for a current picture, or block of samples, of a video signal as a function of parameters for a prior picture of the video signal, which parameters include a bit rate. From the complexity parameter a quality factor for the current picture is determined and applied to a quantizer to compress the current picture. A complexity pre-processor may also be used to detect scene changes in the video signal prior to estimating the complexity parameter. If there is a scene change detected, then the rate control mechanism is reset prior to estimating the complexity parameter for the first picture in the new scene. Also a video buffer verifier is controlled so that the buffer occupancy at the end of a specified image sequence is at a target value so that looping and editing applications are facilitated.

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
Not applicable. 
BACKGROUND OF THE INVENTION 
The present invention relates to data compression, and more particularly to 
a bit rate control mechanism for digital image and video data compression 
that estimates the number of bits required to represent a digital image or 
a video at a particular quality in compressed form or alternatively 
estimates the quality achievable for a digital image or a video when 
compressed to a given number of bits, which estimates are used to control 
the number of bits generated by a video compression system. 
Visual information may be represented by digital pictures using a finite 
amount of digital data for still images, and by a finite data rate for 
time-varying images. Such data in its uncompressed form contains a 
considerable amount of superfluous information. Image compression 
techniques attempt to reduce the superfluous information by minimizing the 
statistical and subjective redundancies present in digital pictures. Pulse 
code modulation, predictive coding, transform coding, 
interpolative/extrapolative coding and motion compensation are some of the 
tools used in image compression techniques. 
A digital video/image compression technique may be either lossy or 
lossless. The lossy compression techniques introduce an irreversible 
amount of distortion into the picture data. In these techniques a 
trade-off is made between the amount of distortion added to the original 
picture input and the number of bits the compressed picture occupies. A 
rate controller in a video/image compression system controls the number of 
bits generated by altering the amount of distortion added to the original 
input by the compression system. In other words a rate controller in a 
video/image encoder controls the number of bits needed to represent the 
compressed image by changing the quality of the decompressed image. 
Transform coding techniques take a block of samples as the input, transform 
this block into a number of transform coefficients, quantize the transform 
coefficients, and variable or fixed length encode the quantized transform 
coefficients. The input to the transform coding system may be either the 
original picture elements (pixels), such as in JPEG and intra-MPEG, or the 
temporal differential pixels, such as in inter-MPEG. An adaptive still 
image coding technique using a transform coder with a rate controller is 
shown in FIG. 1. An input image block is transformed by a discrete cosine 
transform (DCT) function, quantized and variable length coded (VLC). The 
rate controller observes R(n-1), the number of bits generated by the 
previous block, and selects a quantizer scale factor Q(n) for the current 
block. A still image coding scheme, such as JPEG, may be used on a motion 
picture, as shown in the simplified block diagram of FIG. 2. In these 
schemes the rate controller observes R(n-1), the number of bits generated 
by the previous frame (field), and selects a quantizer scale factor Q(n) 
for the current frame (field). A simplified block diagram of an MPEG 
encoder is shown in FIG. 3, where R(n-1) is the typical number of bits 
generated in the previous macroblock. For JPEG Q(n) is referred to as a 
factor or quality factor, and for MPEG it is referred to as mquant. 
In all of the schemes shown in FIGS. 1-3 Q(n) is used to scale the step 
sizes of the quantizers of transform coefficients (quantizer matrices). 
Increasing Q(n) reduces R(n) and vice versa. Q(n) is selected so that 
R(n), the number of bits generated with this quantizer scale factor Q(n), 
is close to the targeted rate for the block, frame or field. Q(n) also is 
an indication of the quality of the decoded block, frame or field. To 
perform efficiently, a rate control algorithm requires a good estimate of 
the rate-quality relationships for the input data, i.e., R(n) vs. Q(n). A 
good rate controller would come up with a Q(n) that results in a targeted 
R(n). The targeted R(n) for a block, frame or field could vary with n. For 
example it might take into account the visual characteristic of the block 
in question, whether the coding is variable bit rate (VBR) or constant bit 
rate (CBR). A good rate controller tries to keep the Q(n) smooth over n so 
that the resulting quality of the decoded picture is smooth as well. 
Given actual R(n-1), the actual bits generated for the preceding block 
number n-1, Chen et al, as described in "Scene Adaptive Coder" from IEEE 
Trans. Communications March 1984, compute Q(n) in the following manner. A 
buffer status B(n-1) after coding block n-1 is recursively computed using 
EQU B(n-1)=B(n-2)+R(n-1)-R 
where R is the average coding rate in bits per block. From the buffer 
status B(n-1) the quality factor Q(n) is computed through 
EQU Q(n)=(1-.gamma.)*.phi.(B(n-1)/B)+.gamma.*Q(n-1) 
where .phi.{ } is an empirically determined normalization factor versus 
buffer status curve and B is the rate buffer size in bits. This produces a 
smoothly varying Q(n) depending on .gamma.. .gamma. is taken to be less 
than unity. 
Alternatively the Test Model Editing Committee, International Organization 
for Standardization, Test Model 3 (Draft), December 1992 computes Q(n) in 
a similar way as follows. First the virtual buffer status B(n-1) is 
computed as above. Then Q(n) is computed through the linear relation 
EQU Q(n)=K.sub.R *B(n-1) 
where K.sub.R is a constant that depends on the targeted average bit rate. 
This Q(n) may be further scaled based on the visual complexity of the 
block being coded. 
Using these techniques Q(n) could change rapidly, and there is no estimate 
of the quality achievable for a particular block, frame or field with a 
given number of bits. What is desired is a rate control mechanism that 
estimates the quality achievable for a digital image or video when 
compressed to a given number of bits or alternatively estimates the number 
of bits required to represent a digital image or video at a particular 
quality in a compressed form. 
BRIEF SUMMARY OF THE INVENTION 
Accordingly the present invention provides a bit rate control mechanism for 
video data compression that either estimates the number of bits required 
to represent a digital image or video at a particular quality in a 
compressed form or estimates the quality achievable for a digital image or 
video when compressed to a given number of bits. A quantizer for 
compressing the transform coefficients for a current block of samples of a 
video signal is controlled by a quality factor that is a function of a bit 
rate for a prior block of samples of the video signal as determined by a 
rate controller. In the rate controller a complexity parameter is 
determined as a function of the prior block of samples including the bit 
rate. The complexity parameter is then used together with the bit rate to 
generate the quality factor. The rate controller may also include a scene 
detector for resetting the rate controller at the beginning of each scene. 
The objects, advantages and novel features of the present invention are 
apparent from the following detailed description when read in light of the 
appended claims and attached drawing.

DETAILED DESCRIPTION OF THE INVENTION 
The relationship between the quality factor Q of a compressed video and the 
average bits R generated by a block, frame or field of samples is modeled 
through 
EQU R=.alpha.*Q.sup.-.beta., Q&gt;0, .alpha..gtoreq.0, .beta.&gt;0 
where .alpha. gives an indication of the complexity of the block being 
compressed, which may vary from block to block (frame/field to 
frame/field), and .beta., which empirically has significantly less 
variations, may be treated as a constant. This model is applicable to a 
number of image and video compression techniques, including JPEG, MPEG and 
MPEG-2. The quality factor Q may be used to generate the qfactor in JPEG 
or mquant in MPEG through simple scale and saturation operations. 
If .alpha. and .beta. for block n equal .alpha.(n) and .beta.(n) 
respectively, the targeted bits R(n) for block n may be achieved by using 
a quality factor Q(n) given by 
EQU Q(n)=(R(n)/.alpha.(n)).sup.-1/.beta.(n). 
In general .alpha.(n) and .beta.(n) are not known in advance, but .beta.(n) 
may be assumed to be a constant .beta.. Then the quality factor is given b 
y 
EQU Q(n)=(R(n)/.alpha.(n)).sup.-1/.beta.. 
In motion JPEG and all-I MPEG coding schemes all the pictures in the video 
are compressed the same way, and only one complexity metric needs to be 
maintained. An input video signal is input to an MPEG or motion JPEG 
encoder 12 as shown in FIG. 4 to obtain an actual R(n-1) for the prior 
frame. The actual R(n-1) is input to a processor 14. The processor 14 has 
a complexity processor 16 which uses the previous history to estimate 
.alpha.(n): 
EQU .alpha.(n)=(1-.gamma.)*R(n-1)*Q(n-1).sup..beta. +.gamma.*.alpha.(n-1) 
where .gamma. is the smoothing factor in the estimation of .alpha., R(n-1) 
is the actual number of bits used for picture n-1. Depending upon the 
application, a value for .gamma. is selected from the range 
0.ltoreq..gamma..ltoreq.1. If .gamma.=1, .alpha.(n) is a constant with 
respect to n, and if .gamma.=0, .alpha.(n) depends only on the preceding 
block coding results. Once .alpha.(n) is estimated, then it is input to a 
quality processor 18 where the quality factor Q(n) may be computed as 
above. In MPEG the average rate R is used to obtain Q(n), as well as the 
targeted R(n) for a particular picture. Q(n) is used to obtain results in 
actual R(n), which is used for updating .alpha.(n). In motion JPEG, as 
well as in all-I MPEG, targeted R(n) is usually the same for every 
picture, i.e., equal to the average required rate R. This R is used to 
obtain Q(n), which is used to obtain actual R(n) for updating .alpha.(n). 
In a more general compression of video using MPEG the coded pictures may be 
categorized into three types: I, B and P. An Intra-coded (I) picture is 
coded using information only from itself. A Predictive-coded (P) picture 
is coded using motion compensated prediction from a past reference frame 
or past reference field. A Bidirectionally-coded (B) picture is coded 
using motion compensated prediction from a past and/or future reference 
frame(s). A given picture (field/frame) of video has a different coding 
complexity depending upon whether it is coded as an I, B or P picture. 
Therefore three picture complexity measures are used for the video, 
.alpha..sub.I, .alpha..sub.B and .alpha..sub.P for I, B and P pictures 
respectively. Upon compressing the picture n-1with a quality factor 
Q(n-1), the actual output bits R(n-1) are measured. Then depending upon 
the coded picture type t(n-1) the corresponding picture complexity is 
updated: 
EQU .alpha..sub.t(n-1) (n)=(1-.gamma.)*R(n-1)*Q.sup..beta. 
(n-1)+.gamma.*.alpha..sub.t(n-1) (n-1) 
The other two picture complexities remain unchanged: 
EQU .alpha..sub.s (n)=.alpha..sub.s (n-1), s.epsilon.{I,B,P}.backslash.t(n-1) 
Then the target number of bits R(n) and the quality factor Q(n) for the 
current picture n may be computed through one of two methods: overlapping 
window method and non-overlapping window method. In both methods, as 
usually done in the MPEG world, the assumptions are: 
EQU Q.sub.B =K.sub.B *Q.sub.I 
EQU Q.sub.P =K.sub.P *Q.sub.I 
where K.sub.B and K.sub.P are known constants, and Q.sub.I, Q.sub.B and 
Q.sub.P are the quality factors used for I, B and P pictures respectively. 
In the overlapping window method, also known as the sliding window method, 
the stream of pictures (fields/frames) to be compressed, in coding order 
as opposed to the display order, are blocked into overlapping windows of 
size N as shown in FIG. 5. In this method pictures 0 through N-1 form the 
first window (WINDOW 0), pictures 1 through N form the second window 
(WINDOW 1), etc. After compressing each picture, the window is moved to 
the right by one picture. If N.sub.I, N.sub.B and N.sub.P represent the 
number of I, B and P pictures remaining in the current window, then for 
the overlapping window method 
EQU N.sub.I +N.sub.B +N.sub.P .ident.N 
EQU E(n) .DELTA. TargetedR(n)-ActualR(n) 
EQU E(-1)=0 
EQU Q.sub.I (n)=((.alpha..sub.I N.sub.I +.alpha..sub.B N.sub.B 
K.sub.B.sup.-.beta. +.alpha..sub.P N.sub.P K.sub.P.sup.-.beta.)/((N.sub.I 
+N.sub.B +N.sub.P)*R+E(n-1))).sup.1/.beta. 
where R is the average coding rate in bits per picture. From Q.sub.I values 
of Q.sub.B and Q.sub.P may be computed. 
Finally the target rate R(n) for the picture n is computed through 
EQU TargetedR(n)=.alpha..sub.t(n) *Q.sub.t(n).sup.-.beta. (n) 
where t(n) is the coding type of picture n. 
In summary the overlapping window method has the following steps: 
1. Initialize: E(-1)&lt;-0; select values for .alpha.'s, .beta., .gamma. and 
N; n&lt;-0 
2. Before coding picture n 
(a) update N.sub.I, N.sub.B and N.sub.P 
(b) compute Q.sub.I 
(c) compute Q.sub.B or Q.sub.P if needed 
(d) compute the target rate R(n) 
3. After coding picture n with a quality factor Q.sub.t(n), measure the 
actual bits generated by picture n 
4. Compute E(n)&lt;-TargetedR(n)-ActualR(n) 
5. Update .alpha.'s 
6. Move the window by one picture, increment n, and go to step 2 
In the non-overlapping window method the stream of pictures to be 
compressed, in coding order rather than display order, is blocked into 
non-overlapping segments or windows of a preselected size N, as shown in 
FIG. 6. Each picture belongs to one and only one window. Then pictures 0 
through N-1 form the first window, pictures N through 2N-1 form the second 
window, etc. If WinBits represents the bits available to the remaining 
pictures in the window and N.sub.I, N.sub.B and N.sub.P represent the 
number of I, B and P pictures remaining in the current window, then for 
the non-overlapping windows method 
EQU N.sub.I +N.sub.B +N.sub.P .ltoreq.N 
and Q(n) and R(n) are computed as follows: 
1. Initialize: WinBits&lt;-0; select values for .alpha.'s, .beta., .gamma. and 
N; n&lt;-0 
2. Beginning of window: WinBits&lt;-WinBits+N*R 
3. Before coding picture n 
(a) update N.sub.I, N.sub.B and N.sub.P 
(b) compute Q.sub.I (n)=((.alpha..sub.I N.sub.I +.alpha..sub.B N.sub.B 
K.sub.B.sup.-.beta. +.alpha..sub.P N.sub.P 
K.sub.P.sup.-.beta.)/WinBits).sup.1/.beta. 
(c) compute Q.sub.B or Q.sub.P if needed 
(d) compute the target rate R(n) 
4. After coding picture n with a quality factor Q.sub.t(n), measure the 
actual bits generated by picture n 
5. Update WinBits&lt;-WinBits-ActualR(n) 
6. Update .alpha.'s 
In MPEG one of the requirements for generating a correctly coded bitstream 
is that the Video Buffer Verifier (VBV) is not violated. The VBV is a 
hypothetical decoder, described in ISO/IEC 13818-2 Annex C, which is 
conceptually connected to the output of an MPEG encoder. The VBV has an 
input buffer known as the VBV buffer of size B.sub.max bits. The target 
rate R(n) computed in step 2(d) above in the overlapping window method, or 
in step 3(d) in the non-overlapping window method, may have to be adjusted 
so as not to overflow or underflow the VBV buffer. The occupancy of the 
VBV buffer for a constant bit-rate operation of MPEG is shown in FIG. 7 in 
idealized form. The VBV buffer occupancy B is updated recursively as 
follows: 
If Ba(n-1) is the buffer occupancy right after decoding picture (n-1), the 
buffer occupancy just before decoding picture n, Bb(n), is given by 
EQU Bb(n)=Ba(n-1)+R 
where R is the average bits per picture. 
The occupancy Ba(n) just after decoding picture n is given by 
EQU Ba(n)=Bb(n)-R(n) 
where R(n) is the number of bits used for picture n. 
The relationship between the number of bits per picture, R(n), and the 
quality factor Q(n), described above may be used by an MPEG encoder to 
1. maintain the constraints imposed by the VBV, 
2. keep the VBV buffer occupancy operating point centered, i.e., away from 
being nearly full or empty, 
3. enable VBV buffer occupancy terminal conditions to be achieved, and 
4. predict and avoid any potential VBV overflow and underflow condition. 
To use this VBV based rate control strategy, the encoder keeps track of the 
following: 
1. the current VBV buffer occupancy at picture n in coding order just 
before it is removed from the VBV buffer, i.e., Bb(n), 
2. the number of pictures of each picture type (I, P and B) remaining in 
the current window, 
3. the target VBV buffer occupancy at the end of a window, this occupancy 
being the VBV buffer occupancy just before the last picture within the 
window is removed from the VBV buffer, i.e., Bb(n+N.sub.I +N.sub.P 
+N.sub.B), and 
4. the average number of bits per picture, R, assuming a constant bit rate 
coding. 
The number of available bits to code all pictures remaining in the window, 
either overlapping or non-overlapping methods, is given by 
EQU WinBits=Bb(n)+(N.sub.I +N.sub.P +N.sub.B)*R-Bb(n+N.sub.I +N.sub.P +N.sub.B) 
. 
Using the model described above the quality factor Q(n) for the remainder 
of the window is estimated by 
EQU Q.sub.I (n)=((.alpha..sub.I N.sub.I +.alpha..sub.P N.sub.P 
K.sub.P.sup.-.beta. +.alpha..sub.B N.sub.B 
K.sub.B.sup.-.beta.)/WinBits).sup.1/.beta.. 
Then the target bits for each picture type within the window are given by: 
EQU TargetR.sub.I =.alpha..sub.I Q.sub.I.sup.-.beta., 
EQU TargetR.sub.P =.alpha..sub.P K.sub.P.sup.-.beta. Q.sub.I.sup.-.beta., and 
EQU TargetR.sub.B =.alpha..sub.B K.sub.B.sup.-.beta. Q.sub.I.sup.-.beta.. 
Using these target sizes for each picture type, simulated VBV buffer 
occupancy trajectory over the window may be computed, i.e., Bb(n) and 
Ba(n)'s for all remaining pictures of the window are projected. If the 
trajectory indicates a VBV buffer overflow or underflow or comes close to 
causing the overflow or underflow, then the window is shortened such that 
it ends at the point where the overflow or underflow was indicated. A 
target VBV buffer occupancy is chosen such that no overflow or underflow 
occurs. With the shortened window Q.sub.I (n) and TargetR's are 
recomputed. This is shown in FIG. 4 where the quality factor Q(n) is input 
to a buffer occupancy predictor 32 to project the Bb's and Ba's, which are 
then input to a VBV comparator 34. 
When a satisfactory VBV buffer occupancy trajectory is obtained, then the 
current picture is coded. When the coding is completed, the actual size of 
the picture is then used to update the complexity estimates for the 
current picture type: 
EQU .alpha..sub.t(n-1) (n)=(1-.gamma.)*R(n-1)*Q.sup..beta. 
(n-1)+.gamma.*.alpha..sub.t(n-1) (n-1). 
For cases where there is no a priori target VBV buffer occupancy to 
terminate the window, the size of the window is chosen such that it ends 
on a "Group of Pictures" boundary. In this case Bb(n+N.sub.I +N.sub.P 
+N.sub.B) is chosen to be: 
EQU Bb(n+N.sub.I +N.sub.P +N.sub.B)=0.5*(B.sub.max +TargetR.sub.I). 
To compensate for the fact that the at parameter does not adapt in a 
relatively fast manner at scene changes in the input video, the input 
video as shown in FIG. 4 also is input to an activity estimator 20. The 
detected activity is input to comparator 22 to determine whether there has 
been an abrupt change corresponding to a scene change. The activity 
estimator 20, as shown in more detail in FIG. 8, measures the activity 
.zeta. of the picture to be coded in determining the complexity of the 
picture being compressed. A picture (field/frame) to be coded is broken 
into four bands by a subband analyzer 24. The variance of the energy in 
the low-high (LH) and high-low (HL) bands is determined by appropriate 
variance computational circuits 26, 28, and the two variances are input to 
a multiplier 30. The measure of activity .zeta. is calculated as the 
energy product in low-high and high-low bands: 
EQU .zeta.=.sigma..sub.LH.sup.2 *.sigma..sub.HL.sup.2 
Any abrupt changes in .zeta. from picture to picture indicate a scene 
change in the video signal. When a scene cut or change is detected, the 
comparator 22 provides a signal to the processor 14 to flush the old 
value(s) of .alpha.(n) and .gamma. is temporarily made equal to 0, i.e., 
the system is reset. Other forms of scene cut detections are possible and 
may be used with the rate control mechanism of the present invention. 
In general there is no relationship between Bb(0) and Bb(NSEQ), the VBV 
buffer occupancy at the beginning of consecutive sequences, and they may 
be arbitrary. For some applications, such as obtaining loopable bitstreams 
where a single finite size compressed bitstream may be repeatedly fed to 
an MPEG video decoder without violating the constraints imposed by the 
VBV, obtaining bitstreams with exact rate requirements, and obtaining 
splicable bitstreams for editing applications including advertisement 
insertion, some constraints on these two numbers is applicable. If the 
video has a total of NSEQ pictures, for the first two mentioned 
applications the usual requirement is to have Bb(0)=Bb(NSEQ). The term 
Bb(NSEQ) refers to the decoder buffer occupancy if the transmission 
continues beyond NSEQ pictures at the constant channel rate of R bits per 
picture duration. 
Given the targets Bb(0) and Bb(NSEQ), the number of bits available for 
compressing the sequence for a constant bit rate coding may be computed as 
: 
EQU SeqBits=NSEQ*R+Bb(0)-Bb(NSEQ). 
This is used in the following procedure for achieving the target terminal 
VBV condition in the non-overlapping window method described above. This 
procedure attempts to avoid violation of the VBV. This procedure starts 
with an initial guess for .alpha.'s and preselected constants .beta., 
K.sub.P and K.sub.B, and continuously updates the estimated .alpha.'s. As 
above, t(n) refers to the coded picture type n. The procedure uses control 
parameters .delta.Q1, .delta.Q2 and .delta.Q3, described below. 
1. Initialize: 
(a) select initial values for .alpha.'s and .beta.; 
(b) n.rarw.0 
(c) SeqBits=NSEQ*R+Bb(0)-Bb(NSEQ) 
2. Beginning of Window: 
(a) compute N.sub.I SEQ, N.sub.B SEQ and N.sub.P SEQ, the number of I, B 
and P pictures left in the sequence respectively; 
(b) compute Q.sub.I =((.alpha..sub.I *N.sub.I SEQ+.alpha..sub.B *N.sub.B 
SEQ*K.sub.B.sup.-.beta. +.alpha..sub.P *N.sub.P 
SEQ*K.sub.P.sup.-.beta.)/SeqBits).sup.1/.beta. ; 
(c) compute the target bits for each picture type for the pictures 
remaining in the sequence: TargetR.sub.I =.alpha..sub.I 
Q.sub.I.sup.-.beta.TargetR.sub.P =.alpha..sub.P K.sub.P.sup.-.beta. 
Q.sub.I.sup.-.beta.TargetR.sub.B =.alpha..sub.B K.sub.B.sup.-.beta. 
Q.sub.I.sup.-.beta. ; 
(d) compute N.sub.I, N.sub.B and N.sub.P, the number of I, B and P pictures 
in the window; 
(e) WinBits.rarw.N.sub.I *TargetR.sub.I +N.sub.P *TargetR.sub.P +N.sub.B 
*TargetR.sub.B. 
3. Before coding picture n 
(a) update N.sub.I, N.sub.B and N.sub.P ; 
(b) compute Q.sub.I (n)=((.alpha..sub.I *N.sub.I +.alpha..sub.B *N.sub.B 
*K.sub.B.sup.-.beta. +.alpha..sub.P *N.sub.P 
*K.sub.P.sup.-.beta.)/WinBits).sup.1/.beta. ; 
(c) use projection onto convex sets (POCS) to adjust Q.sub.I (n): if 
(.vertline.Q.sub.I (n)-Q.sub.I (n-1).vertline.&lt;=.delta.Q1*Q.sub.I (n-1), 
then Q.sub.I (n).fwdarw.Q.sub.I (n-1), 
i.e., retain old Q.sub.I ; 
(d) compute Q.sub.B if t(n)=B; compute Q.sub.P if t(n)=P; 
(e) simulate VBV buffer occupancy trajectory for this picture: if the 
trajectory indicates a VBV buffer overflow or underflow, then either (1) 
shorten the window as discussed above, or (2) modify Q.sub.t(n) such that 
overflow or underflow does not happen; 
(f) compute the target rate R(n) for the current picture, called 
TargetBits. 
4. While coding the picture, optionally modulate Q: 
(a) if (remaining bits in picture&gt;0) then localQ.rarw.((# of remaining 
macroblocks*.alpha. of current picture) 
/(remaining bits in picture*# of macroblocks in picture)).sup.1/.beta. * 
spatial modulation, 
else 
localQ.rarw.31; 
(b) if (localQ&gt;(.delta.Q2*pictureQ)), then 
localQ.rarw.(.delta.Q2*pictureQ); 
(c) if (localQ&lt;(.delta.Q3*pictureQ)), then local 
Q.rarw.(.delta.Q3*pictureQ). 
5. Compute the harmonic mean of the localQ's used within the picture in 
coding macroblocks of the picture, called ActualQ.sub.t(n). 
6. If (t(n)=I) then 
EQU Q.sub.I (n)=ActualQ.sub.t(n) 
else if (t(n)=P) then 
EQU Q.sub.I (n)=ActualQ.sub.t(n) /K.sub.P 
else if (t(n)=B) then 
EQU Q.sub.I (n)=ActualQ.sub.t(n) /K.sub.B 
7. Measure the actual bits generated by picture n 
8. Update WinBits.rarw.WinBits-ActualR(n) 
9. Update SeqBits.rarw.SeqBits-ActualR(n) 
10. Update .alpha.'s 
11. Move to the next picture and repeat above. 
Step 2 above assures that the VBV path evolves from Bb(0) towards Bb(NSEQ) 
in a smooth fashion. 
Step 3c above makes the quality factor change smoothly, be unaffected by 
small variations in the picture complexity, and adjust quickly in cases of 
scene changes. The term .delta.Q1 in step 3c is a parameter that controls 
the quality factor variation from picture to picture. This factor should 
be large at the beginning of the sequence so that the quality does not 
fluctuate unnecessarily, and be small at the end of the sequence so that 
the exact bit rate targets may be achieved. The values of .delta.Q1 in one 
particular implementation are shown in FIG. 9. 
Step 4 is optional, and is similar to the Test Model. Q is modulated around 
the Q determined in step 3 above so that the picture target rates are 
achieved and/or perform spatial masking. The parameters .delta.Q2 and 
.delta.Q3 constrain the quality variation within a picture. Again only 
smaller variations should be allowed at the beginning of the sequence, and 
larger variations may be permitted at the end of the sequence. The values 
of .delta.Q2 and .delta.Q3 in one particular implementation are shown in 
FIGS. 10 and 11 respectively. 
To update the .alpha.'s in step 10 ActualR(n) is the actual bits generated 
by coding the picture with an average (harmonic mean) quality factor 
ActualQ.sub.t(n). Let .alpha..sub.I, .alpha..sub.P and .alpha..sub.B be 
the current estimates of .alpha.'s for the three picture types. First the 
.alpha. of the current picture type is updated as follows: 
Method 1. 
1. Tmp.alpha..sub.t(n) .rarw.ActualR(n)*ActualQ.sub.t(n).sup..beta. 
2. if (((Tmp.alpha..sub.t(n) 
-.alpha..sub.t(n))/Tmp.alpha..sub.t(n))&gt;.delta..alpha.) then 
EQU .alpha..sub.t(n) .rarw.(1.0-.delta..alpha.)*Tmp.alpha..sub.t(n) 
else if (((Tmp.alpha..sub.t(n) 
-.alpha..sub.t(n))/Tmp.alpha..sub.t(n))&lt;-.alpha.) then 
EQU .alpha..sub.t(n) .rarw.(1.0+.delta..alpha.)*Tmp.alpha..sub.t(n) 
else 
retain the old value of .alpha..sub.t(n) 
endif 
The parameter .delta..alpha. controls how much deviation in .alpha. is 
expected from picture to picture without any scene change. This type of 
projection makes the update immune to minor variations in the picture 
complexity due to noise, while making it quick to adjust in cases of scene 
changes. The particular value for one implementation of the rate 
controller is .delta..alpha.=0.05. 
Method 2. 
In this method additional state information is maintained from picture to 
picture. A 2.times.1 vector per picture type denoted by .theta. is 
initialized as: 
EQU .theta..sub.I =[1, (.alpha..sub.I -RQ.sub.I.sup..beta.)] 
EQU .theta..sub.P =[1, (.alpha..sub.P -RQ.sub.P.sup..beta.)] 
EQU .theta..sub.B =[1, (.alpha..sub.B -RQ.sub.B.sup..beta.)] 
In the absence of a-priori information a 2.times.2 matrix per picture type 
denoted by P is initialized as: 
EQU P.sub.I =[1, 0; 0, 1] 
EQU P.sub.P =[1, 0; 0, 1] 
EQU P.sub.B =[1, 0; 0, 1] 
After coding a picture the following steps are followed for the current 
picture type: 
1. .phi.=[Prior Encoder Fullness, Q.sup.-.beta.] 
2. .theta..sub.t(n) =.theta..sub.t(n) +(1.0.phi..sup.T P.sub.t(n) 
.phi.)(Current Encoder Fullness-.phi..sup.T .theta.)P.sub.t(n) .phi. 
3. P.sub.t(n) =P.sub.t(n) -(1.0/.phi..sup.T P.sub.t(n) .phi.)P.sub.t(n) 
.phi..phi..sup.T P.sub.t(n) 
4. .theta..sub.t(n) =.theta..sub.t(n) +((1-.theta.(1))/P.sub.t(n) 
(1,1))P.sub.t(n) e.sub.1 
where e.sub.1 =[1, 0] and P.sub.t(n) (1,1) is the first element of first 
row in P.sub.t(n) 
5. .alpha..sub.t(n) =.theta..sub.t(n) (2)+ActualQ.sub.t(n).sup..beta. R 
where .theta..sub.t(n) (2) is the second element of .theta..sub.t(n). 
where "T" denotes the matrix or vector transpose function. 
After updating the .alpha. of the current picture type using either of the 
two methods described above, the other two .alpha.'s are updated as 
follows. If the current picture type is I, then based on the just updated 
.alpha..sub.I, .alpha..sub.P and .alpha..sub.B are updated through: 
1. if (.alpha..sub.P &lt;(L.sub.PI..alpha..sub.I)) then .alpha..sub.P 
=L.sub.PI..alpha..sub.I 
2. if (.alpha..sub.B &lt;(L.sub.BI..alpha..sub.I)) then .alpha..sub.B 
=L.sub.BI..alpha..sub.I 
Similarly if the current picture type is P, then based on the just updated 
.alpha..sub.P, .alpha..sub.I and .alpha..sub.B are updated through: 
1. if (.alpha..sub.I &lt;(L.sub.IP..alpha..sub.P)) then .alpha..sub.I 
=L.sub.IP..alpha..sub.P 
2. if (.alpha..sub.B &lt;(L.sub.BP..alpha..sub.P)) then .alpha..sub.B 
=L.sub.BP..alpha..sub.P, and if the current picture type is B, then based 
on the just updated .alpha..sub.B, .alpha..sub.I and .alpha..sub.P are 
updated through: 
1. if (.alpha..sub.I &lt;(L.sub.IB..alpha..sub.B)) then .alpha..sub.I 
=L.sub.IB..alpha..sub.B 
2. if (.alpha..sub.P &lt;(L.sub.PB..alpha..sub.B)) then .alpha..sub.P 
=L.sub.PB..alpha..sub.B 
These projections ensure that in the case of a scene cut in the input 
video, all the .alpha.'s are updated. The constants L.sub.PI, L.sub.BI, 
L.sub.IP, L.sub.BP, L.sub.IB and L.sub.PB are predetermined, such as 0.2, 
0.1, 1.11, 0.11, 2.0 and 1.8 respectively. FIG. 12 shows the performance 
of one implementation of the above described rate control process for a 
sequence coded at different bit rates and multiple NSEQ according to 
Method 1 for updating .alpha.'s. 
Thus the present invention provides a rate control mechanism for video 
compression that uses a special relationship model between the quality 
factor and the average bits generated using an indication of complexity of 
the block being processed.