Model Parameter Estimation for a Rate- or Distortion-Quantization Model Function
Description
The present invention relates to model parameter estimation for a rate-quantization or
distortion-quantization model function so as to approximate an actual rate-quantization or
distortion-quantization function of a video encoder for a frame sequence such as, for
example, for real-time video encoding.
Rate control tasks in video encoding can be greatly enhanced if the rate-quantization
characteristic R(QP) of the current frame is known, i.e. which quantizer yields which rate.
This obviously holds, for example, for low delay rate control where it is important to
match a given target bitrate very closely. However, in real-time applications it is usually
not possible to determine R{QP) exactly as this would require to encode the frame with all
possible quantization parameters. Therefore, models were introduced that try to predict the
relationship between rate and quantization. That is, the rate-quantization function R(QP)
is modeled as

where p is a vector containing the parameters of the model.
Sufficiently accurate models are already available for the distortion-quantization function
(see [21]).
However, the task of modeling the rate-quantization relation is much more difficult.
Several different models aiming to represent the R-Q characteristic of H.264/AVC coded
video frames have emerged in the literature. The most popular one (e.g. used in [11]) is the
quadratic model proposed by [5]. It has two adjustable parameters and often uses MAD
(mean absolute difference) to predict the new frame complexity [22]. It is defined as

where the relation between quantization parameter and quantization step size (QStep) is
defined in the H.264/AVC standard [14], Some further proposals of different complexity
are the linear model [12], the exponential model in [24], the p - domain model based on
the number of non zero coefficients [8] or a piecewise defined model given by [7].
Even more essential than the potential accuracy of the R-Q model is the reliable estimation
of its parameters [6], Besides the use of statistical measures (like e.g. the previously
mentioned MAD ) the parameters of these models are usually determined by means of
linear regression e.g. [5] [10], Furthermore there are a few approaches using the Kalman
filter e.g. [23], [4].
However all of the models mentioned previously have shortcomings concerning model
accuracy, complexity, smoothness or convexity. Similarly none of the published
algorithms used to determine the model parameters provides a sufficiently accurate and
straightforward estimation.
Thus, it is the object of the present invention to provide a model parameter estimation
scheme for a rate- or distortion-quantization model function which enables more accurate
estimation and thus, a more efficient video encoding.
This object is achieved by the subject matter of the independent claims.
In accordance with a first aspect, the present invention is based oh the finding that a more
accurate model parameter estimation may be achieved if a Kalman filter is used for
discretely estimating the model parameters between the consecutive frames of the frame
sequence and if the correction step of the time-discrete Kalman filter is performed twice
per frame, namely first using a measurement value which depends on a complexity
measure (one or more) of the current frame so as to obtain a primarily corrected state of the
time-discrete Kalman filter, and secondly using a measurement value which depends on an
actual coding rate or distortion of the video encoder in encoding the current frame using a
predetermined quantization which, in turn, may have been determined by use of an
estimation of the actual rate- or distortion-quantization function according to the primarily
corrected state.
In accordance with another aspect of the present invention, the present invention is based
on the finding that a better compromise between a to complicated rate-quantization model
function on the one, which leads to unstable model parameter estimations, and a too simple
rate-quantization model function, which leads to a stable but inaccurate rate-quantization
function approximation, is achieved if a rate-quantization model function is used which
relates the quantization of the video encoder to the coding rate of the video encoder and is
piecewise defined so as to exhibit a quadratic function in a finer quantization interval, and
an exponential function in a coarser quantization interval.
The ideas and advantages of the two aspects may be exploited individually. Alternatively,
embodiments of the present invention take advantage of both aspects.
Preferred embodiments of the present application are described below with respect to the
figures, among which
Fig. 1 shows a block diagram of an apparatus for estimating model parameters of a
rate-quantization model function so as to approximate an actual rate-
quantization function of a video encoder for a frame sequence and a
possible integration thereof into a system along with a video encoder
according to an embodiment;
Fig. 2 shows a shape of the rate-quantization curve for one frame of the mobile
sequence;
Fig. 3 shows the rate-quantization curve of video frames coded with H.264/AVC
in order to illustrate that same can be quite different for different sequences
so that the model chosen should be quite adaptable;
Fig. 4 shows a comparison of the approximation quality of the quadratic and the
piecewise defined rate-quantization model according to an embodiment;
Fig. 5 shows the absolute approximation error of the quadratic and the piecewise
defined rate-quantization model according to an embodiment;
Fig. 6 shows the approximation of the R-Q relationship of frames of different
sequences using the piecewise defined rate-quantization model and
approximation technique according to an embodiment, wherein the
corresponding relative approximation error is depicted in the bottom figure;
Fig. 7 illustrates the fact that the error in the complexity measure based prediction
is usually sequentially correlated;
Fig. 8 shows the design of one cycle of a Kalman filter based algorithm executable
on the apparatus of Fig. 1, wherein the R-Q model parameters are estimated
in three steps which are repeated for every frame k;
Fig. 9 shows a visualization of one cycle of the defined rate-quantization model
and approximation technique according to an embodiment;
Fig. 10 shows a model estimation example in case of a scene change with the goal
of constant bitrate (500 kbits per Frame); and
Fig. 11 shows model based QP and rate selection over a period of 200 frames when
a constant bitrate of 500 kbits per Frame (« 0.54 bits per pixel in case of
720p) should be achieved.
Fig. 1 shows an apparatus 10 for estimating model parameters of a rate-quantization model
function so as to approximate an actual rate-quantization function of a video encoder 12 for
a frame sequence 14. Together, encoder 12 and apparatus 10 form a system for encoding
the frame sequence 14. Optionally, the system 16 may also comprise a rate controller 18,
the function of which will be outlined in more detail below.
The frame sequence 14 may be any video or any other spatio-temporal sampling of a
scene. The sample values of the frames of the frame sequence 14 may be luminance or
luma values, color values, depth values or the like, or even a combination thereof.
The video encoder 12 may be of any type, such as a temporally predictive coder using, for
example, motion-compensated prediction with choosing motion parameters on a frame
block basis. In particular, video encoder 12 may be a hybrid encoder deciding on a block-
by-block basis, as to whether blocks into which the frames of the frame sequence 14 are
subdivided, are to be predicted using temporal prediction based on previously encoded
frames and/or spatial prediction based on previously encoded neighboring blocks of the
current frame. In accordance with a more detailed description of an embodiment outlined
below, the encoder 12 is, for example, a video encoder configured to generate a H.264
compliant data stream. However, encoder 12 may alternatively operate in accordance with
the JPEG 2000 standard or in accordance with the upcoming H.265 video standard.
The video encoder 12 has a certain characteristic in encoding frame sequences such as
frame sequence 14. Owing to the prescription of the data stream which the video encoder
12 has to obey in encoding the inbound frame sequences, video encoder 12 exhibits a
characteristic relation between the quantization used by the video encoder 12 to encode the
frame sequence 14 and the coding rate, i.e. number of bits needed for encoding, with this
characteristic curve in turn depending on the complexity of the frame sequence itself. To
be more precise, the video encoder 12 is configured to encode the frame sequence 14 in a
lossy manner by use of quantization such as quantizing sample values and/or transform
coefficients, such as sample values and/or transform coefficients representing the frames to
be encoded, or the prediction residual thereof. Naturally, the coding quality decreases
when increasing the quantization amount, i.e. the coarser the quantization is the lower the
coding quality is. However, on the other hand, video encoder 12 is able to achieve the
decreased coding quality at coarser quantizations using lower coding rates, and accordingly
an actual rate-quantization function R(q), which relates the coding rate R to the
quantization q and vice versa, is usually a monotonically decreasing function of the
quantization q. However, as already mentioned above, this relation also depends on the
complexity of the material to be encoded. It goes without saying that the complexity of the
frames within a frame sequence tend to be non-constant. Accordingly, the rate-quantization
function of encoder 12 for frame sequence 14 is also subject to time variation. For
illustration purposes, Fig. 1 shows an exemplary rate-quantization function of encoder 12
for frame k of frame sequence 14 at reference sign 20, i.e. Rk(q), along with the rate-
quantization function Rk.1(q) for the previous frame k-1 at reference sign 22 in a common
diagram 24, the horizontal axis of which spans the quantization q and the vertical axis of
which spans the coding rate R. As a minor note, it is mentioned that the quantization q
could be any measure for the amount of quantization used by encoder 12. Accordingly, q -
0 could either mean that encoder 12 does not use any quantization or a some minimum
quantization such as operating on bit level. Moreover, although Fig. 1 suggests that
encoder 12 would be able to continuously change the quantization q, it could be possible
that the encoder 12 merely allows for a discrete setting of the quantization q. The same
applies with respect to the coding rate R. Any measure could be used in order to measure
the coding rate R, such as the number of bits used to encode the respective frame.
Due to the dependency of the rate-quantization function 20 on the content of the frame
sequence 14, the rate-quantization function 20 is not known a priori. Of course, encoder 12
could perform many trials in setting the coding options available, including the amount of
quantization, in order to sample the rate-quantization function 20 for each frame of the
frame sequence 14 in order to finally select an optimum amount of quantization based on
the thus sampled R-Q curve, but this would be a cumbersome task for encoder 12 and
depending on the application there is not enough time to do so for the encoder 12. This is
true, for example, in case of real time applications where the encoder 12 is for encoding the
frame sequence 14 in real time, such as in camcorders or the like. In such a case it is
advantageous to be able to forecast the rate-quantization function of encoder 12 for the
current frame in order to minimize the number of trials, or to even streamline the encoding
of the current frame by encoder 12 to the extent that encoder 12 adopts the optimum
quantization as determined, for example, by rate controller 18 based on the estimated rate-
quantization function. For example, rate controller 18 has to guarantee that the data stream
generated by encoder 12 obeys some rate constraints imposed onto system 16 due to, for
example, some transmission capacity via which the data stream has to be transmitted such
as the storing rate of some non-volatile memory or the transmission of a wireless or wire
communication path via which the data stream is to be transmitted. The better the
estimation of the rate-quantization function 20 is, the higher the probability is that the
quantization obeying the prescribed coding rate in accordance with the estimated rate-
quantization function actually leads to a data stream having an actual coding rate which
obeys the coding rate constraints.
As already described above, it is the task of apparatus 10 to estimate model parameters of a
rate-quantization model function such that the same approximates the actual rate-
quantization function 20 of video encoder 12 as close as possible. That is, the
approximation performed by apparatus 10 is restricted by the parameterizable states of the
rate-quantization model function underlying apparatus 10. In the more detailed
embodiments described below, this rate-quantization model function is a piecewise
function comprising a quadratic function portion/piece within a finer quantization interval,
and an exponential function portion/piece within a coarser quantization interval and with a
manifold of the model parameters having five dimensions, i.e. five independently
selectable model parameters. However, the embodiment of Fig. 1 is not restricted to any
rate-quantization model function and could be used in connection with other rate-
quantization model functions as well. Generally speaking, the rate-quantization model
function used by apparatus 10 is a model for approximating the actual rate-quantization
function 20, i.e. R(q) ˜ f(q, X), with X denoting the model parameters of the rate-
quantization model function f. Preferably, a bijective function maps the model parameters
X onto the set of possible/available rate-quantization model function instantiations and
vice versa. For illustration purposes, Fig. 1 shows such a rate-quantization model function
26 of certain model parameters for approximating the actual rate-quantization function 20
of the current frame k. The way apparatus 10 determines or estimates the corresponding
model parameters is outlined below.
Apparatus 10 comprises an updater 28, a first corrector 30 and a second correction 32. As
will be outlined in more detail below, updater 28, first corrector 30 and second correction
32 together form an extended time-discrete Kalman filter and are sequentially connected,
to this end, into a loop.
Apparatus 10 has an input 34 for receiving the frame sequence 14. As can be seen from
Fig. 1, first corrector 30 has an input connected to this input 34. Updater 28 and second
corrector 32 may, optionally, have input thereof also connected to input 34. Further,
apparatus 10 is interactively connected to encoder 12 either directly or via optional rate
controller 18 so as to provide the encoder 12 or rate controller 18 with an estimate of the
model parameters and receive from encoder 12 an actual coding rate as obtained by
actually encoding a current frame, as will be outlined in more detail below.
In particular, updater 28 is configured to perform a prediction step of the time-discrete
Kalman filter, the internal state of which defines a parameter estimate for the model
parameters to obtain a predicted state of the time-discrete Kalman filter for the current
frame k of the frame sequence 14 from a state of the time-discrete Kalman filter for
the previous frame k - 1 of the frame sequence 14. That is, updater 28 performs the first
step in connection with the iteration step of the time-discrete Kalman filter concerning the
current frame k and receives, to this end, the final state at the end of the preceding iteration
regarding the previous frame k-1, namely
As will be outlined in more detail below, the updater 28 may be configured to, in
performing the prediction step of the time-discrete Kalman filter, use an identity matrix as
the state transition matrix so that the predicted state adopts the parameter estimate
defined by the final state of the previous frame k - 1. concurrently, updater 28
increases the uncertainty of the predicted state relative to the final state. As a measure for
the uncertainty, a covariance matrix may be used. In particular, the updater 28 may be
configured to determine a similarity measure between the current frame k and the previous
frame k -1 and increase the uncertainty of the predicted state by an amount which
depends on the similarity measure. In case of an abrupt scene change between the
consecutive frames k - 1 and k, for example, these frames will have approximately no
similarity and the amount of uncertainty increase by predicting the current Kalman state
from the previous state will be maximally high. In contrast, in case of a static
scene, it is very likely that the uncertainty increase by the prediction by updater 28 will be
close to zero. Updater 28 may use any descriptive statistic measure in order to measure the
similarity between consecutive frames. The similarity measure may be determined between
the current frame k and the previous frame k - 1 such that the motion between these frames
increases the similarity measure, and/or with eliminating/disregarding the motion between
these frames. For example, updater 28 could use a predicted frame predicted from the
previous frame k - 1 in order to determine the similarity between the current frame k and
the predicted frame. The predicted frame could stem from encoder 12 as is illustrated by
dashed arrow 36 in Fig. 1. Encoder 12 may have determined the predicted frame by use of
motion-compensated prediction, but, for example, at a motion resolution lower than the
motion resolution finally used in order to encode the current frame. That is, the motion
vectors underlying this predicted frame may have been determined by encoder 12 in a
resolution lower than the motion vectors finally used in order to encode the current frame k
and being introduced into the data stream as side information along with a quantized
prediction residual. Alternatively, another frame of sequence 14 than frame k-1 may serve
as reference frame wherein frames close to frame k in presentation time t are preferred.
Additionally, the similarity between frame k and frame k-1 without motion compensation
therebetween may be used for obtaining the similarity measure.
As is known for the time-discrete Kalman filter, each iteration step has a correction step
following the prediction step as performed by updater 28. In case of apparatus 10, this
correction step is performed twice per iteration. The first corrector 30 is for performing the
correction step the first time during the iteration concerning the current frame k. In
particular, the first corrector 30 is configured to determine a complexity measure of the
current frame and perform the correction step of the time-discrete Kalman filter using a
measurement value which depends on the complexity measure determined so as to obtain a
primarily corrected state of the time-discrete Kalman filter from the predicted state
The first corrector 30 may be configured to, in determining the complexity measure,
determine a measure for a deviation between a provisionally predicted frame determined
by motion-compensated prediction and the current frame and/or a measure for a dispersion
of a spread of sample values of the current frame around a central tendency thereof.
Accordingly, as illustrated by dashed arrow 38, first corrector 30 may receive the
provisionally predicted frame from video encoder 12. In fact, this provisionally predicted
frame may be the same as optionally received by updater 28 according to 36. Examples for
the respective measures mentioned will be outlined in more detail below. In principle, the
measure for the deviation may be the range, the mean deviation, the variance or the like.
The same applies to the measure of dispersion with respect to the current frame. All of
these statistical measures may be determined locally such as on a block-by-block basis
with taking the average or some other measure of the central tendency as the final hint for
the complexity measure of interest.
To be slightly more precise, the first corrector 30 is configured to try to coarsely predict
model parameters for the rate-quantization model function 26 so as to approximate the
actual rate-quantization function 20 as close as possible, based on the complexity measure
only, i.e. without using any of the preceding states of the time-discrete Kalman filter, that
is, also independent on the current state Of course, this prediction is very coarse, but
first corrector 30 may perform the correction step of the time-discrete Kalman filter using a
measurement value equal to a difference between the thus coarsely predicted model
parameters and a result of a prediction of the model parameters as obtained by first
corrector 30 for the previous frame k - 1 based on a complexity measure determined for
this previous frame k - 1, applied to a correlation matrix. In other words, in a previous
iteration step, first corrector 30 has already performed the coarse prediction of the model
parameters of the rate-quantization model function for the previous frame k -1 based on a
respective complexity measure determined for this previous frame k - 1. In order to obtain
the measurement value for the correction step, the first corrector 30 may apply these
coarsely predicted model parameters of the previous frame k- 1 to a correlation matrix and
determine a difference between the result of this application and the coarsely predicted
model parameters of the current frame k. By this measure, the first corrector 30 takes into
account the sequential correlation of the noise of the coarse predictions so as to obtain a
better measurement value. Accordingly, the first corrector 30 may use a measurement
matrix equal to the identity matrix minus the used correlation matrix. The correlation
matrix may be an identity matrix times a scalar ?k and the first corrector 30 may be
configured to set the scalar depending on a similarity between the current frame k and the
previous frame k- 1. First corrector 30 may determine the similarity in line with updater
28 as mentioned before with respect to arrow 36.
Finally, the second corrector 32 is configured to perform the correction step of the time-
discrete Kalman filter a second time using a measurement value which depends on the
actual coding rate of the video encoder 12 in encoding the current frame k using a
predetermined quantization. In other words, second corrector 32 performs the correction
another time on the primarily corrected state as output by first corrector 30. In order to
obtain the actual coding rate needed by video encoder 12 in order to encode the current
frame k into the data stream as output by encoder 12 at output 40, second corrector 32 may
inspect the data stream itself or alternatively, receive the actual coding rate from video
encoder 12 separately as illustrated in Fig. 1 by arrow 42. The predetermined quantization
which the video encoder 12 used in order to encode the current frame k at the actual coding
rate 42 may have been determined using the rate-quantization model function as defined by
the model parameters of the primarily corrected state Video encoder 12 may perform
the determination of the predetermined quantization itself. Alternatively, optional rate
controller 18 determines the predetermined quantization and controls the video encoder 12
externally by use of the thus determined predetermined quantization 44. For example, the
rate controller 18 may have to obey some coding rate constraints and seeks to find an
optimum predetermined quantization 44 based on the rate-quantization model function as
determined by the model parameters of the primarily corrected state The optimum may
be defined by minimizing the coding rate or some cost function depending on both coding
rate and coding quality. The second corrector 32 performs the correction step of the time-
discrete Kalman filter using the measurement value depending on the actual coding rate 42,
and a measurement matrix which depends on a linearized version of a relation between the
model parameters X and a coding rate of the video encoder 12 in accordance with the rate-
quantization model function for the predetermined quantization 44, linearized at the
primarily corrected state In even other words, the second corrector 32 linearizes f(q, X)
at the predetermined quantization used by encoder 12 in encoding the current frame at the
actual coding rate 42 and the model parameters and this linearized relation is used by
the second corrector 32 as the measurement matrix in the correction step of the time-
discrete Kalman filter. The result of this second correction step performed by second
corrector 32 represents a twice-corrected state of the time-discrete Kalman filter and thus
represents an even better estimation of the model parameters for a better approximation of
the actual rate-quantization function 20 of the current frame: The second corrector 32
passes on this twice-corrected state as the reference state for the performance of the
prediction step with regard to the next frame k + 1 by updater 28.
After having described the embodiment of Fig. 1 rather coarsely, in the following a
possible implementation of the embodiment of Fig. 1 is described in more detail by use of
an explicit example for the rate-quantization model function. It goes without saying that
the details outlined below are readily transferable to other rate-quantization model
functions as well and that, accordingly, the details outlined below shall also represent a
detailed implementation of the embodiment described above as far as other rate-
quantization model functions are concerned. Similarly, the discussion outlined below often
assumes the video encoder 12 to be a H.264 encoder. However, the discussion outlined
below is not restricted to that type of encoder and in fact, it is readily derivable from the
discussion below that all of the details are readily transferable to other video encoders as
well.
However, in order to ease the mathematical description of the details outlined below, first,
the specific embodiment for the R-Q model is introduced and it is shown how the model
parameters of this R-Q model can be interpreted as the state of a dynamic system, i.e. the
dynamic system which the time-discrete Kalman filter operates on. Thereafter, Kalman
filter basics are presented. After that, the information available to determine the R-Q model
is described in a following section. In section IV, it is explained how this information is
processed by the modified Kalman filter in order to get an accurate estimate of the model
parameters. Some noteworthy remarks are then presented in section V. In section VI,
results demonstrating the quality of the presented model in combination with the
estimation algorithm are provided. Interspersed within this detailed description, reference
is made to Fig. 1 in order to associate the details presented above as possible
implementation details for the entities shown in Fig. 1 and described so far. It should be
noted that the details presented below pertain to the elements in Fig. 1 individually.
I. R-Q Model
Usually it is not possible to encode a frame with all possible quantization parameter to get
the actual R-Q function. Instead models are used to provide an approximate knowledge of
the relation between quantization parameter and bitrate to the rate control.
Due to the temporal prediction in motion compensated video coding, the rate-quantization
characteristic of a frame strongly depends on the quantization parameters used for the
reference frames. However, this would make it much more difficult to find an appropriate
model, as the R-Q curve would be even more variable. To avoid this complexity it is
assumed that the model is valid for a constant quantizer. That means Rk(QP) is the rate for
frame k quantized with QP given that the reference frames were coded with the same
quantization parameter QP.
Many models separate between texture/source bits and header bits (see e.g. [9]). The
texture bits are the bits used to model the actual picture data. The header bits provide the
necessary side information like motion vectors, prediction modes and quantization
parameters. However it is usually not necessary to have this distinction nor does it simplify
the modeling problem. Therefore, the rate-quantization model presented now considers the
total rate (texture bits + header bits).
In H.264/AVC the selectable quantization parameters depend on the chosen bit depth. The
model now presented in the following is able to approximate R-Q function for all possible
bit depths. Therefore, the quantization parameter QP is defined as

where the bit-depth offset (BDO) is defined as BDO = 6• (bit_depth _lunta-8).
A. R-Q Model Function
The rate-quantization curve R(QP) of an H.264/AVC encoded video frame can look quite
different for different frames. This is especially true for higher bit depths and higher
quantization step sizes. To be able to approximate all these curves well enough, the often
used quadratic function (Eq. (2)) is not sufficient. Therefore, more complex models like in
[7] were proposed.
The model derived here is based on the observation that the R(QP) -curves resemble a
linear or quadratic function at low quantization parameters. At higher QP values in contrast
they usually have an exponential shape. This is visualized in Fig. 2.
Accordingly, the following, heuristically determined, piecewise function may be used as
the model function 26 in Fig. 1:

where the first interval is covered by the quadratic function

and the second interval is modeled by the exponential function

The parameter vector ß is defined as ß = [a1'b1'c1'm,a2'b2,c2] and N = 51 + BDO. The
relation between the actual quantization parameter QP and the model parameter q which
is introduced for notational simplicity is:

That means q represents just the actual quantization parameter QP shifted by BDO.
Note that the model f(q,ß) always represents the rate in bits per pixel. To get the actual
number of bits expected, f(q,ß) simply has to be multiplied with the number of pixels
(NP) within the frame or slice. Accordingly the R-Q function is modeled as

The parameters a1'b1'c1'm,a2'b2,c2 and m are used to fit the function to the rate-quantization
curve. Note that the location m (quantization parameter) where the first interval ends and
the second begins is itself adjustable. This is advantageous as the location of the transition
point between the quadratic and exponential model can be quite different for different
sequences as demonstrated in Fig. 3 (The transition points were determined using the curve
fitting in (10)).
Since f(q,ß) should be smooth it is required to be continuously differentiable. Therefore
only such values for ß are allowed for which

hold. According to this a1 -exp(a2) and b1 = b2.a1' which means that there are actually
only 5 freely selectable parameters which can be used to fit the function given by equation
(4) to the actual rate-quantization curve of the frame.
The approximation quality of the quadratic model is compared with the just presented
model for an exemplary R-Q curve of a frame of the mobile sequence in Fig. 4. Note that
the parameters of the quadratic model and the just presented model were determined by
using the least squares method. It can be seen that the just presented model is able to
approximate the rate-quantization relationship very well. Although not perfect, the
quadratic model also seems to be reasonable. However, as we may be seen in Fig. 5, the
corresponding absolute error is considerably large. The potential accuracy of the just
presented model has the drawback that it is rather complex. This means also that it is more
difficult to reliably estimate its parameters. Indeed, the parameters of simple models can be
predicted fast and reliably [6]. However, the model should be valid for the whole quantizer
range. And as we will show in the next sections it is still possible to estimate the
parameters with high quality. Furthermore, as such a model usually only makes sense on
the frame (and maybe slice) layer, the additional computations required are insignificant.
B. Approximation
The model function given by (4) shall approximate the actual R(QP) relationship
properly. In order to have an appropriate model for the entire QP range, the inventors
found that it is more important to have a small relative rather than a small absolute
approximation error. By first doing a log transformation and then using the method of least
squares acceptable relative errors have been achieved. Accordingly, the optimal parameter
vector is defined as:

where it is assumed that only valid vectors according to (9) are considered. A logarithmic
transform is applied to take into account that the relative error is more important.
Indeed the model given by is found to be a very accurate approximation of the
actual R-Q function R(QP). This is also confirmed by the examples depicted in Fig. 6,
where the model parameters were determined according to the previously described
method. It also shows that the relative error remains similar for all QPs, i.e. the
approximation quality is good over the entire domain.
Although the model approximates the actual R-Q function very well there is still
some error left. This can be expressed as

where the approximation error uq is normally distributed with zero mean and variance U,
i.e.

C. State Formulation
According to (10), an appropriate parameter vector may be found for every frame k.
Using the model approximately describes the rate-quantization characteristic
Rk {QP) of the corresponding frame. Now, suppose that , can be represented by
the vector xk. Then, we can interpret this vector xk as the state of the R-Q model of frame
k. We chose the following definition of xk:

Actually, we could have taken as the state. The reason for choosing it this way is that
xt is only of size 5x1 as the used model function has only 5 independent parameters.
Furthermore, this gives robust results and also enables the relatively easy calculation of the
parameters al'b1,c1 and a2,b2,c2. Taking the logarithm of and
ensures that the model function has a positive range (f(q, x) > 0).
For notational simplicity the time subscript k in the remainder of this section is omitted,
i.e. x1 is the first element of the vector x. The function parameters are determined from
the elements of the state vector x as

Therefore, the R-Q model 26 can be rewritten in terms of the state as

D. Model Constraints
Obviously the rate-quantization model should be positive over the whole range of
quantization parameter. Furthermore, it should be monotonously decreasing with
increasing QP. And finally, although in practice not perfectly true, the rate-distortion
function should be convex. This is necessary for some algorithms in video coding see e.g
[15] and moreover complies with rate distortion theory [1]. Accordingly, x is required to
fulfill

Due to the exponentials involved in (16), (17) and given that f'(q,x)<0 actually
f(q,x) > 0 is guaranteed. The remaining constraints can be given as

where the first two inequalities ensure f'(q,x)<0 and the last two f''(q,x)>0.
II. Kalman Filter
As will be described in a later section, the problem of finding the optimum parameters for
the R-Q model can be considered as the problem of determining the state of a dynamic
system. An optimum state of a linear dynamic system can be found using the Kalman
filter. Accordingly, the Kalman filter is also the basis of the model parameter estimation
algorithm presented in Sec. IV. This, in turn, is the reason why some Kalman filter
fundamentals are explained in the remainder of this section.
A linear discrete time system can be defined as

with the measurement equation

where wk is the process noise and vk is the measurement noise, both white, zero mean,
uncorrelated and with covariance E[wkwTk] = Qk or E[ykyTk]=Vk, respectively. The
vector xk represents the state of the system, Fk-1 is the state transition matrix and Ht
relates the state to the measurement yk, For such a system an optimal state xk is found by
applying the discrete time Kalman filter algorithm.
A. Discrete Time Kalman Filter
The discrete time Kalman filter (for a derivation see [17]) can be used to solve a linear
discrete time system of the form described previously. It comprises the following
computations for every time step or iteration k:
1) Prediction (State and Covariance Propagation)

2) Correction (State and Covariance Update)

B. Sequential Kalman Filtering
The Kalman filter assumes that there are r separate measurements at time k. That is, there
is an rx1 measurement vector yk which is used for correction in (25). However, there is
no need to process all measurements at once. Instead, it is also possible to handle one
measurement after another - which is the idea of the Sequential Kalman filter of Fig. 1.
That means first y0k is processed, than y1k and so on until all r measurements were
considered. Although this requires computing the Kalman filter correction equations r
times this can still be very useful as the inverse in (24) simply becomes a division, i.e. no
matrix inversion required.
The sequential Kalman filter can be especially beneficial if the measurement noise
covariance matrix Vk is diagonal. For other types of Vk additional, time-consuming
computations may be necessary. In this cases the classical batch algorithm is usually better.
A more detailed description of the sequential Kalman filter can be found in [17].
C. Colored Measurement Noise
Sometimes the noise corrupting a measurement is sequentially correlated, that is

where ?k is zero mean white noise with covariance

As mentioned previously, the standard Kalman filter assumes vA to be white. There are
two general ways to solve this problem, either by augmenting the state or by measurement
differencing (see [2, 3]). As will be described later the preferred approach for the problem
considered here is a slightly modified version of the measurement differencing approach
which was proposed by Petovello et. al. [13].
The measurement differencing approach presented by Bryson and Henrikson [3] defines a
new measurement y'k

Substituting (21) into (29) yields

According to [13] we rearrange (20) as follows

and plug it into (30): ..

Using (27) we can rewrite this as
where
The noise V'k of the auxiliary measurement y'k is no longer sequentially correlated, i.e.

where dkJ is the Kronecker-Delta defined as
and
The introduced correlation between the new measurement noise v'k and the process noise
Wk-1 is

This correlation can be handled by the general discrete Kalman filter which considers
cross-correlation between disturbance input and measurement noise (see [17],[20]).
D. Extended Kalman Filter
The extended Kalman filter can be used if the measurement and the state are related in a
nonlinear way, i.e.

The idea of the extended Kalman filter is to linearize the measurement equation around the
current state
Setting
we get
This linear approximation is in the form which can be handled by the Kalman filter.
III. Measurements
Here, the measurements which are used in the next section to determine the parameters of
the R-Q model are described. First, there are the so called complexity measures which can
give an indication how complex it is to encode a frame. Same are determined and used by
corrector 30. Second, we have the bitrate obtained after coding which reveals estimation
errors of the current model. Same are determined and used by corrector 32.
A. Complexity measures
There are various statistical measures which can be calculated by corrector 30 before the
coding of a frame. This includes the mean value, the variance (a2) and the mean squared
difference between predicted and the actual frame (A). The latter one is only available if at
least a rough motion estimation had been done such as in encoder 12. Alternatively, the
popular MAD (mean absolute difference) used in several rate-distortion model estimation
approaches could be used as a difference value.
Furthermore, variations of these measures, namely the mean logarithmic variance (s2log)
and the mean logarithmic difference (?log), may be used. The advantage of the latter two is
that single outliers (e.g. macroblocks which can not be properly predicted) have not that
much influence on the final value.
Unlike the variance-like measures, the prediction difference measures clearly depend on
the coding of the last frame. That is, if the last frame was coded very badly, there is a
prediction error even if nothing has changed between the two original frames. To
overcome this dependency, the corruption which is due to the distortion of the reference
frames has to be removed from the measured prediction difference. This is approximately
possible by taking the QP and distortion of the reference frames as well as the variance into
account. The result is just an estimate of the prediction difference measure which would
have been obtained if the original frames had been used as reference.
The described complexity measures can indicate the coding characteristics of the
corresponding frame. That means there is a relation between these measures and the
parameters of the rate-quantization model. Accordingly, it is possible for corrector 30 to
estimate the parameters or the state of the rate-quantization model, respectively as:

The relationship hi'hp was obtained empirically by computing the rate-quantization
relationship for various sequences. Note that hp also produces reasonable estimates when
the current frame is the first frame of a new scene, i.e. ? and ?log are very bad.
Using the state estimate xk we can formulate the following measurement equation for the
frame k:

where the 5 x 1 vector vk can be considered as the prediction error or the noise. According
to the empirical derivation of (44) it can be assumed that vk - N(o,vk), Since xk is an
estimate of the state, the matrix Hk is just the identity matrix i.e.

Usually, the prediction error vk is highly correlated in time. The reason for this is that the
complexity measures, like the rate-quantization characteristics, are similar for succeeding
frames. This means for example that if the predicted state xk underestimates the
complexity of the frame k, then it is very likely that the state ik+l predicted for frame
k + l also underestimates the complexity. Accordingly, \k is actually colored noise
(compare Sec. II-C), i.e.

with gk being uncorrelated in time and normally distributed with zero mean and
covariance Zk. That is

where Zk was determined empirically. For simplicity we defined the 5x5 correlation
matrix Yft as

where the scalar 0 < y/k < 1. That is, the same correlation y/k for every parameter
xkni = 1,...,5 is assumed. This is reasonable as the correlation depends on the amount of
change in the R-Q characteristic between the last and the current frame (which is the same
for every parameter). In case of a scene change for example y/k - 0.
The sequential correlation of the prediction error is visualized for the parameter x, (first
element of state vector x) in Fig. 7. As can be seen, the prediction xx constantly
overestimates the actual value. The error (jc,-^) is therefore sequentially correlated.
Using (47) it is possible to get rid of the correlation and extract the remaining white noise.
Although not perfectly true (since all state parameters are predicted from the same
complexity measures) it is assumed that there is no cross-correlation between the predicted
parameters, i.e. Zk is a diagonal matrix. This gives the benefit that the Kalman filter
equations can be calculated computationally efficient (without matrix inversion) by
processing each measurement sequentially.
B. Coding Bitrate
Succeeding frames of a video sequence are in general very similar. Accordingly the R-Q
characteristic of neighboring frames is highly correlated. This means, the more accurate the
model at frame k the more accurately one can estimate the model for frame k+l.
Therefore, it makes sense in Fig. 1 that the second corrector updates the model of frame k
even if the frame was already encoded.
Consequently, the bitrate Bk measured after coding of frame k with quantization
parameter QP% is used as feedback to correct the R-Q model. Unfortunately, if the
reference frames were coded with different quantization parameters, this rate may deviate
from Rk {QP k ) (the rate which would have been measured if the reference frames were
also coded with QPk, recall Sec. I). As the model, however, should approximate the
actual R-Q curve Rk (QP)> a new bitrate is defined as

where the goal of the function yk is to estimate Rk(QP^ as good as possible from the
actually measured rate Bk, that is y* (#*> QPk) * &k (2^* )¦ A simple choice would be y^B^
QPf) - Bh i.e. ignore the temporal dependency and just use the measured rate. However,
based on statistical measures and the quantization parameter of the main reference frame it
is also possible to calculate a Sk, which is more close to ^*(0^ )• The rate Bk can then be
used to correct the model. According to (11), the following relationship exists between
bitrate and state

Note that this equation considers the errors between model and actual R-Q function for a
sequence of frames (one specific QP per frame), whereas (11) considers the errors between
model and actual R-Q function for various QPs (but only one frame).
As mentioned previously the error uk represents the inability of the model to perfectly
represent the R-Q curve. The error due to different quantization off the reference frames is
modeled by tk. Obviously, this error is zero if the reference frames were coded with QPk as
well. It is practically adequate to merge uk and tk into and consider it random white
noise with zero mean and variance

IV. Model Parameter Estimation
In most papers the parameters of the quadratic R-Q model seem to be determined by liner
least squares. The Kalman filter, however although to a certain degree similar to
(recursive) linear least squares [19], has some decisive advantages for this particular
problem. These are mainly the inherent ability to adapt to variations, the consideration of
uncertainty (noise) and the possibility of incorporating several measurements.
As mentioned previously the rate-quantization characteristic of video frames is, except for
scene changes, highly correlated in time. That means the R-Q function of one frame is
usually similar to the one of the next frame. Consequently, this correlation can be exploited
to enhance the accuracy of the model. Naturally, however, video and by that its rate-
quantization characteristic is dynamic. That means it changes, usually slowly, with time.
Naturally the model must be adapted to the changed R-Q relationship.
Accordingly, the problem of estimating the R-Q model is considered as the problem of
estimating the state of the following dynamic discrete time system

The state vector xk represents the parameters of the R-Q model as defined in Sec. I-C.
Since there is no deterministic change of the R-Q characteristic from one frame to the next
the state transition matrix Ofc is the identity matrix i.e.

The process noise wt is defined as

with the disturbance noise covariance matrix Qk which models the uncertainty that the last
state also holds for the current frame.
To find an optimum estimate of the state of the dynamic system given by (52) with the
measurements (45) and (50) the apparatus 10 implements a modified version of the
discrete Kalman filter. The principal working of this modified Kalman filter as well as the
involved data is visualized for a frame k in Fig. 8. A detailed description of the individual
algorithm steps is given in the following.
That is, Fig. 8 shows steps which may be performed by the elements of Fig. 1 in
accordance with a specific implementation further outlined below. In accordance with this
implementation, elements 28,30 and 32 realize the extended Kalman filter.
A. Prediction
The first step in the cycle of the algorithm, concerning the current frame k, shown in Fig.
8 is the prediction step 50 performed by updater 28, for example.
In the prediction step 50 the corrected state and covariance matrix of the last frame are
used to predict same for the current frame in time, i.e. for the current frame k. Using (53)
in (22) and (23) we get

As can be seen, without more information the best estimate of the state for the current
frame k is just the a posteriori state estimate of the last frame k - 1. However the
uncertainty in the state has increased by Qk-1.
These computations 55 and 56 are performed by updater 28 within prediction step 50.
B, Correction
As already outlined above, the correction of the modified Kalman filter algorithm of Fig. 8
is split-up into two correction steps 52 and 54 performed by the first corrector 30 and the
second corrector 32, respectively.
In this phase 52, 54 the measurements are used to correct the state. As described in Sec. III
we have two types of measurements. The state predicted from the complexity measures
and the bitrate obtained after encoding. Usually all measurements are packed into the
measurement vector and are then used for updating the state. However, in this case the
state predicted from the complexity measures is available before actually coding the frame,
whereas the bitrate is only available after that. However, it is important to have a good
rate-quantization model before coding as it may be used by the rate control such as
controller 18 to determine the quantization parameter. Obviously the model and by that the
rate control would not be as good as they could be if we consider the complexity measures
only after coding. Therefore, unlike the classic Kalman Filter, the correction phase is
divided into two steps. In the first step 52 the complexity measures and in the second step
54 the bitrate are used to update the state.
This division is indeed possible according to the sequential Kalman filter described in II-B.
Furthermore, a two-step correction can be easily employed as no correlation between the
error of the elements of the predicted state vk and the error of the measured bitrate vk is
assumed, i.e.

This assumption is admissible as the two types of errors originate from completely
different shortcomings. The error of the predicted state is due to the limitations of the
complexity measure prediction, whereas the error of the measured rate is due to the
inability of the model to perfectly match the actual R-Q function. That means that a
correlation between these two types of measurements is very unlikely. Indeed practical
experiments showed no significant correlation between the predicted state and the
measured bitrate.
1) Correction Step 1: The first correction step 52 performed by first corrector 30 involves a
step 56 of determining the complexity measure by first corrector 30. As mentioned
above, the best determination may involve encoder 12 performing a coarse temporal
prediction 58 such as performing a full pel motion estimation so as to predict the current
frame k from the previous frame k - 1. It should be noted that encoder 12 does not
necessarily use the immediately previously encoded frame as reference frame. The
reference is also not restricted to being the immediately preceding one in terms of
presentation time sequence. Encoder 12 is free to choose the reference index, i.e. is free to
index any previously encoded frame as reference frame. Then, in the first step 52, the state
predicted from the complexity measures as defined in (44) is used to improve the
estimation quality of the R-Q model for the current frame. To address the sequential
correlation of the prediction error, the measurement differencing approach described in
Sec. II-C may be used. According to (29) an auxiliary measurement y'k is defined as

Plugging (53), (46) into equation (34) the new measurement matrix H'k becomes

The Kalman gain K'k for this step is
where
This was obtained by using (46) and (53) in (38) and (39) respectively. Note that (60) is
just the formula for the Kalman gain in case of cross-correlated disturbance and
measurement input as given in [17] or [20]. Using the Kalman gain K'k we can get the
intermediate state estimate by updating the state as follows

Similar the process noise covariance update for this step becomes

That is, first corrector 30 may compute (58) in order to obtain the measurement value y'k
and may correct the Kalman state according to (62) along with the associated uncertainty
according to (63) by setting the measurement matrix according to (59) and setting the
Kalman gain according to (60) and (61).
2) Correction Step 2: The outcome of the first correction step 52 is the primarily corrected
state x0k and as described above, this estimate of the model parameters may be used to
control the coding rate of the encoder by, for example, rate controller 18 or some internal
entity of encoder 12 itself (this alternative is not shown in Fig. 1). The rate control step is
shown in Fig. 8 with reference sign 60. In particular, step 60 involves choosing a
predetermined quantization QPk for encoding the current frame k based on the rate-
quantization model function as determined by x0k. The actual encoding is performed in step
62 by encoder 12 using this predetermined quantization. As a result, the actual coding rate
Bk resulting from the use of the chosen predetermined quantization QPk as known and may
be used in the second correction step 54. In this step 54 the bitrate obtained after coding is
used as feedback for the R-Q model 26. That means the state is corrected according to the
relation (50b). As this relation is nonlinear (due to log(f(q,x))) the extended Kalman
filter (see Sec. II-D) is used, according to which the measurement equation around the
current state is linearized according to:

Now we define to be the gradient of f(qk, x) at ij

then we can rewrite (64) as

Using the left side as the measurement in (25) the measurement update for this step
becomes
(67)
The Kalman gain as well as the updated covariance matrix Pt+ are computed according
to the usual formulas (24) and (26), i.e.

That is, the second corrector 32 linearizes the rate-quantization model function f at the
used quantization qk and the primarily predicted state of the model parameters x0k,
according to (65) in order to obtain the measurement matrix and computes (67) in order to
update the Kalman state and (69) in order to update the corresponding uncertainty
according to (64), (66) and (68).
As mentioned above with respect to (50a) and (50b), the second corrector 32 may be
configured such that the measurement value depends on the measured coding rate 42 of the
video encoder 12 in a manner dependent on a relationship between the predetermined
quantization qk used in encoding the current frame k and a further quantization used by the
video encoder 12 in encoding a previously encoded reference frame, from a reconstructed
version of which the video encoder 12 predicted the current frame by motion compensated
prediction.
In the above discussion of Fig. 8, it has been neglected that updater 28 has to somehow
predict the disturbance noise covariance matrix Qk, and that the same applies for the first
corrector 30 who has to additionally select the measurement noise covariance matrices Zk
and Vk. In the following section C, possible selections are discussed along with a possible
selection for the correlation matrix ?k.
C. Controlling the Estimation
The appropriate fusion of the different information available is controlled by Qk, Zk,
and ?k. The matrices model the uncertainty in the measurements and the state. By
selecting them properly a reasonable estimate of the state and by that of the rate-
quantization model may be obtained. Due to the variability of the R-Q characteristic of
video frames they may, advantageously, be adapted for every frame.
The matrix Qk-1, represents the uncertainty that is also a good estimate for frame k.
This uncertainty is due to the change of the coding characteristic from one frame to
another. That means if two succeeding frames (and by that the corresponding R-Q
functions) are very different the uncertainty increase should be high. If on the other hand
two frames are almost identical the state of the last frame is very likely appropriate for the
current frame too. Similarly, the correlation between the parameter estimate and
and by that the appropriate selection of?k and Zk can also be considered as depending on
the amount of change in the R-Q relation from one frame to the next.
Suppose the example of a scene change between frame k - 1 and k. In this case the main
diagonal elements of the process noise covariance Qk-1, should become infinite so that
there is no certainty in the state anymore. This is necessary as the rate-distortion
characteristics of frames beyond scene changes are not correlated. By a similar reasoning
we can conclude that the correlation parameter ?k should become zero and Zk = Vk in that
case. Accordingly if there is a scene change all temporal information is neglected and the
state predicted from the complexity measures becomes the best possible state estimate.
The value of does not directly depend on the change in the R-Q model. If it would only
model the error between the model function and the actual R-Q relationship could be
kept constant. However, as it also has to model the possible deviation of from Rk(QPk),
it may be increased advantageously in case that the reference frames were coded with other
QPs.
V. Remarks
As indicated in Fig. 8 the rate control 60 uses the rate-quantization model based on the
state estimate obtained after the first correction step 52. That means the rate control
assumes that represents the relationship between the quantization parameter and
the rate for frame k.
Assuming no correlation in the approximation error of succeeding frames (Eq. (51))
actually possesses some remarkable consequences. If always a similar QP is chosen for
encoding, the model will become more accurate in the range of the used quantization
parameter. This means the model might not longer be optimal over the whole QP range but
it is likely to be better around the QP values currently used. This is a very useful behavior
as often only a small range of QP values is considered by the rate control. On the other
hand if QPs from the whole possible range [-BDO,5l] are used than the model will
become globally optimal in the sense of (10), i.e. the model has the same estimation quality
for all quantization parameter. This means that the accuracy of the model automatically
adjusts to the QP selection behavior.
Both the correction and the prediction and by that the estimated model assume that the
coding of the current frame does not depend on the coding of the previous frame. As
described in Sec. I this is however not true. The deviation between the actual operational
rate-quantization curve from the estimated rate-quantization model can again be modeled.
This is, however, only important if the exact bitrate must be known. If the bitrate must fit
only in the long-term then the raw rate-quantization model actually is sufficient or even
gives the better information.
Besides the method proposed in Sec. II-C there are other ways to handle sequentially
correlated measurements, for example state augmentation or the classical measurement
differencing approach. Whereas the state augmentation approach would involve 10x10
matrix computations and might be numerically unstable, the classical measurement
differencing approach is difficult to apply sequentially. The disadvantage of the used
approach is usually that it needs the inverse of the state transition matrix ?. As in this
case, however, ?-1 = I-1 = I this is no problem.
Similarly, the extended Kalman filter is not the only method to handle nonlinear systems.
Further approaches are, for example, described in [17]. However, the extended Kalman
filter is regarded adequate for the specific problem considered in this paper. This is due to
its computational simplicity and the fact that it provides appropriate results despite the
linearization error.
Although very seldom, it might happen that the updated state returned by the Kalman Filter
violates one or more of the constraints (19). In this case a valid state can be obtained by
using on of the approaches to constrained Kalman filtering described in [16].
Note that the measurements can be processed sequentially avoiding the need for matrix
inversion. In addition many matrices are sparse and or symmetric. This can be exploited to
reduce the processing time.
The rate-distortion characteristic of I pictures is different from that of P or B pictures.
Therefore, measurements for I pictures should not be used to update the rate-quantization
model for temporally predicted pictures.
The rate-quantization characteristic of a frame also depends on the picture type and the
temporal distance to the reference frames. If, for example, the frame prediction structure
IbBbPbBbP is used, the R-Q relation of the P-frames is very different from that of the b-
frames. In such a case there should be one instance of the algorithm for each picture type
(4 for the previous example). An instance includes the state estimate and the
corresponding error covariance matrix P. Of course, the index k-1 refers in this case to the
previously coded frame of the same type. In other words, the apparatus 10 of Fig. 1 could
be configured such that the frame sequence it operates on is a proper subset of the video
sequence 14 in that the frame sequence merely comprises frames of a specific prediction
type and excludes frames of differing prediction type of sequence 14. Either several
apparatuses 10 would be provided in parallel, each for a different prediction type, or the
apparatus would manage different Kalman states and associated uncertainties, i.e. one pair
for each prediction type.
VI. Results
To demonstrate the potential accuracy of the proposed model, we computed the actual rate-
quantization curve R(QP) for the frames of various sequences. After that we fitted the
quadratic as well as the just presented model to the measured R-Q functions. The fitting
was done according to (10) for both models in order to get comparable figures. The mean
approximation error was measured as follows:

with M being the number of frames considered. Results for various sequences for the
quadratic model (The quadratic model is usually only defined for the 8 bit case. For the 12
bit case we used what we believe is the straightforward extension) (Eq. (1)) and for the
proposed model (Eq. (4)) are summarized in Table 1.
Table 1: Comparison of the mean approximation error of the quadratic and the
proposed model

As can be seen in this table the just presented model clearly outperforms the quadratic
model, especially for the case of 12 bit sample depth.
To get an impression of the presented estimation algorithm, an example step is visualized
in Fig. 9. Note that this big difference between the rate-quantization characteristic of two
consecutive frames is rather unusual. For demonstration purposes it is, however, a good
example. As can be seen, the correction step 1 already recognizes that the current frame is
more complex to encode than the last one. However, the measured rate indicates that
still underestimates the true rate-quantization characteristic. Therefore, the
correction step 2 drags the model function even higher. Note that the corrected R-Q curve
does not run through the sample used for correction exactly. This is due to the fact that we
use which prevents the model from oscillating (the bitrate often oscillates from
frame to frame).
In Figs. 10 and 11 we see the estimation from another perspective. There we see an
exemplary use of the R-Q model in a low delay scenario. The rate control wants to find
that QP which results in the given target rate (in this case 500 kbits per frame). That is the
optimal QP would be

the rate control uses that quantization parameter for which
-target_atelNP? is minimized. In these figures we compare the optimal QP
choice, with the QP chosen according to the R-Q model and with the QP chosen if only the
state predicted from complexity measures is considered (Cor 1 only) or if only the rate
measured after coding is used for correcting the model (Cor 2 only).
From Fig. 10 we see that in case of a scene change we can only rely on the state prediction
from complexity measures. The correction using the measured rate is important to get rid
of the bias in the predicted state. This is shown in Fig. 11 where the selected QP and the
corresponding rate is displayed for a longer period. By combining both corrections a
solution which is rather close to the optimum can be found (see Figs. 10 and Fig. 11).
VII. Conclusion
Thus, the above described model is able to approximate the various possible rate-
quantization curves resulting by coding with H.264/AVC very accurately. This holds true
for the whole quantizer range. Comparisons with the commonly used quadratic model
show that it provides a considerable better quality. The problem of estimating the
parameters for this and other models may be solved by using a modified version of the
Kalman filter. This allows consideration of the temporal correlation as well as the available
complexity measures. The result is a sophisticated yet straightforward algorithm which is
perfectly controllable via the noise covariance matrices and the correlation parameter. The
excellent quality of this model and its estimation could be confirmed by various
simulations and tests.
Thus, in even other words, the above embodiments combined both aspects in the form of a
Kalman filter based estimation of a piecewise defined rate-quantization model for a
H.264/AVC. On the one hand, an advantageous frame layer rate-quantization (R-Q) model
for the H.264/AVC video coding standard has been used. In particular, both the
advantageous model function along with an advantageous parameter estimation algorithm
has been used in the embodiment outlined above. The piecewise defined model function is
able to represent the various different shapes of rate-quantization curves very well. For the
model parameter estimation, an algorithm has been used which is based on a modified
version of the Kalman filter. By this, the temporal correlation of successive frames can be
exploited and at the same time the complexity measures as well as the bit rate obtained
from the coding can be considered. Using the described model and parameter estimation
algorithm the actual rate-quantization curve can be predicted with high accuracy. A high
quality R-Q model can be very beneficial for various one pass rate control problems, like
e.g. low delay rate control as well as for rate-distortion optimization problems. In other
words, the model is able to accurately represent the rate-quantization relationship of a
H.264/AVC encoded frame. Furthermore, the algorithm described is able to estimate the
parameters of this model properly. Unlike many other approaches, the above embodiment
strictly separates between rate control and an R-Q model. The rate-quantization model
along with the parameter estimation allows for the rate control to decide which quantizer to
use. Obviously, this has the advantage that different rate control types can use the same R-
Q model.
However, both aspects, namely the model function and the parameter estimation based on
the Kalman filter are advantageous even if exploited isolated from the other. That is, the
piecewise model function outlined above could be used in an apparatus for estimating
model parameters which does not use or implement a Kalman based parameter estimation
comprising the first and the second corrector as outlined above. The advantages result from
the well defined compromise between a to high number of model parameters so that the
stability in estimating the model parameters would be endangered, and a to low number of
model parameters so that the approximation is bad. On the other hand, the Kalman based
model parameter estimation comprising the first and second correctors as outlined above
may also be used in connection with other rate-quantization model functions than the
piecewise one outlined above, and the advantage results from splitting-up the correction
process into two steps so as to exploit as precise measurement values as possible in each
correction step. The Kalman based model parameter could even be used for estimating
model parameters of a distortion-quantization model function so as to approximate an
actual distortion-quantization function of a video encoder. In that case, the actual coding
distortion at the predetermined quantization as obtained, for example, by the primarily
corrected Kalman filter state, would be used for the secondary correction step. The rate
control would still control the coding rate with using, however, the distortion-quantization
model function, or both rate-quantization and distortion-quantization model function.
The rate-quantization model function outlined above approximates the R-Q relationship in
form of a piecewise defined function. It consists of, or comprises at least, two pieces. The
first, i.e. finer quantization piece, is a quadratic function which covers the low quantizer
range. The second, a coarser quantization piece, is an exponential function which
represents the R-Q relationships at high QPs. This function is heuristically determined.
However, it has been motivated by the characteristic of the actual R-Q relationship. The
transition point between the quadratic and exponential function piece is itself variable. By
this, the model becomes very adaptable. This is advantageous as the shape of the actual R-
Q function can be quite different. This is also due to the fact that the model function can be
used for the case of 8, 10 and 12 bits bit-depth, for example. By placing restrictions on the
parameter, it is ensured that the function is continuously differentiable (C1). The remaining
five parameters can be used to the fit the model to the actual R-Q function with high
accuracy.
On the other hand, the above described R-Q model parameter estimation considers the
problem of estimating the model parameters as the problem of estimating the state of a
dynamic discrete time system. This is valid as the R-Q characteristic of succeeding frames
is highly correlated, however, may change slightly.
Accordingly, a modified Kalman filter is used to determine an optimum state of the system
and by that the optimum parameter of the respective R-Q model. The Kalman filter based
algorithm described above comprises three major steps which are executed for every frame
and are briefly summarized again here:
1) Time update: There is no deterministic change of the R-Q characteristic from one frame
to the other. Therefore the state of the last frame is taken as the first estimate for the
current frame. The uncertainty of the state, however, is increased.
2) First Correction: Complexity measures are, for example, the variance and the prediction
error. These measures are available before coding and can be used to directly predict the
parameter of the model for the current frame. Unfortunately, this prediction itself is very
inaccurate (due to the limitations of the complexity measures). Therefore the predicted
parameter are taken as a measurement in the Kalman filter algorithm. There they are used
to correct the current state. Due to the sequential correlation of the noise of the predicted
parameters, a measurement differencing approach is used advantageously.
3) Second Correction: After the coding of the current frame, the number of bits needed for
coding can be used to correct the state. Due to the nonlinear relation between measurement
and state, the measurement equation around the current state is linearized (approach of the
extended Kalman filter). This correction makes sense although the frame was already
coded. The reason for this is the high correlation between successive frames, i.e. the better
the model for the current frame the better the model for the next frame. Naturally, also a
linear R-Q model (linear in the model parameter) could be used in connection with the
above embodiments. In this case, the linearization just results in a standard Kalman Filter
based algorithm, and the linearization would not be needed though same does not change
anything. In other words, the above embodiment may be extended to operate with a
standard Kalman Filter rather than an extended Kalman Filter. The linearization at the
second corrector is not performed. Rather, the relation between the model parameters and
the coding rate in accordance with the rate- or distortion-quantization model function 26
for the tested or chosen quantization at the primarily corrected state would be already
linear.
The rate-control uses the model based on the state obtained after step 2. It usually makes
sense to use this model for the frame and slice layer. An exact model is especially useful
for low delay scenarios. If the frame QP is already optimal than only few changes have to
be done on the macroblock level which avoids a significant drop in R-D performance. This
also justifies the overhead of computations compared to simpler models.
Usually the Kalman filter consists of only two steps. However due to the fact that step 1
one can done before but step 2 only after coding we divided the correction phase into two
steps to provide the most accurate model possible to the rate-control. This is possible
according to the sequential Kalman filter and the fact that there is no cross correlation
between the measurement of step 1 and the measurement of step 2.
The uncertainties of the state can be accurately modeled by the noise covariance matrices
of the Kalman filter. This allows to adapt the state and by that the model to the varying R-
Q characteristic. For example, one can react to scene changes by just increasing the
uncertainty of the current state. Note that in this case one can only rely on the predicted
parameter mentioned in step 2.
It has been found out that it is more important to have small relative rather than small
absolute errors. This is considered in the algorithm by using a logarithmic transformation.
By that, an accurate model over the whole QP range results.
Due to the assumption that the bitrate used in step 3 is corrupted by white noise the model
accuracy automatically adapts to the QP selection behavior of the rate control. That means
if always similar QPs are used the model will become locally accurate whereas if random
QPs are used the model will become globally optimal.
Although some aspects have been described in the context of an apparatus, it is clear that
these aspects also represent a description of the corresponding method, where a block or
device corresponds to a method step or a feature of a method step. Analogously, aspects
described in the context of a method step also represent a description of a corresponding
block or item or feature of a corresponding apparatus. Some or all of the method steps may
be executed by (or using) a hardware apparatus, like for example, a microprocessor, a
programmable computer or an electronic circuit. In some embodiments, some one or more
of the most important method steps may be executed by such an apparatus.
Depending on certain implementation requirements, embodiments of the invention can be
implemented in hardware or in software. The implementation can be performed using a
digital storage medium, for example a floppy disk, a DVD, a Blue-Ray, a CD, a ROM, a
PROM, an EPROM, an EEPROM or a FLASH memory, having electronically readable
control signals stored thereon, which cooperate (or are capable of cooperating) with a
programmable computer system such that the respective method is performed. Therefore,
the digital storage medium may be computer readable.
Some embodiments according to the invention comprise a data carrier having
electronically readable control signals, which are capable of cooperating with a
programmable computer system, such that one of the methods described herein is
performed.
Generally, embodiments of the present invention can be implemented as a computer
program product with a program code, the program code being operative for performing
one of the methods when the computer program product runs on a computer. The program
code may for example be stored on a machine readable carrier.
Other embodiments comprise the computer program for performing one of the methods
described herein, stored on a machine readable carrier.
In other words, an embodiment of the inventive method is, therefore, a computer program
having a program code for performing one of the methods described herein, when the
computer program runs on a computer.
A further embodiment of the inventive methods is, therefore, a data carrier (or a digital
storage medium, or a computer-readable medium) comprising, recorded thereon, the
computer program for performing one of the methods described herein. The data carrier,
the digital storage medium or the recorded medium are typically tangible and/or non-
transitionary.
A further embodiment of the inventive method is, therefore, a data stream or a sequence of
signals representing the computer program for performing one of the methods described
herein. The data stream or the sequence of signals may for example be configured to be
transferred via a data communication connection, for example via the Internet.
A further embodiment comprises a processing means, for example a computer, or a
programmable logic device, configured to or adapted to perform one of the methods
described herein.
A further embodiment comprises a computer having installed thereon the computer
program for performing one of the methods described herein.
A further embodiment according to the invention comprises an apparatus or a system
configured to transfer (for example, electronically or optically) a computer program for
performing one of the methods described herein to a receiver. The receiver may, for
example, be a computer, a mobile device, a memory device or the like. The apparatus or
system may, for example, comprise a file server for transferring the computer program to
the receiver.
In some embodiments, a programmable logic device (for example a field programmable
gate array) may be used to perform some or all of the functionalities of the methods
described herein. In some embodiments, a field programmable gate array may cooperate
with a microprocessor in order to perform one of the methods described herein. Generally,
the methods are preferably performed by any hardware apparatus.
The above described embodiments are merely illustrative for the principles of the present
invention. It is understood that modifications and variations of the arrangements and the
details described herein will be apparent to others skilled in the art. It is the intent,
therefore, to be limited only by the scope of the impending patent claims and not by the
specific details presented by way of description and explanation of the embodiments
herein.
References
[1] Toby Berger. Rate Distortion Theory (Prentice-Hall series in information and system
sciences). Prentice Hall, 1971.
[2] Jr. Arthur E. Bryson and Yu-Chi Ho. Applied Optimal Control: Optimization,
Estimation and Control. Ginn and Company, 1969.
[3] Bryson, A. B., Jr. and Henrikson, L. J. Estimation using sampled-data containing
sequentially correlated noise. Journal of Spacecraft and Rockets, 5(6):662-665,1967.
[4] Din-Yuen Chan and Shou-Jen Lin and Chun-Yuan Chang. A rate control scheme
using Kalman filtering for H.263. Journal of Visual Communication and Image
Representation, 16(6):734-748,2005.
[5] Tihao Chiang and Ya-Qin Zhang. A new rate control scheme using quadratic rate
distortion model. IEEE Transactions on Circuits and Systems for Video Technology,
7(l):246-250, 1997.
[6] Jianpeng Dong and Nam Ling. On Model Parameter Estimation for H.264/AVC Rate
Control. IEEE International Symposium on Circuits and Systems, ;289 -292,2007.
[7] ThomaszGrajekandMarekDoman'ski. New Model of MPEG-4 AVC/H.264 Video
Encoders. International Conference on Image Processing, pages 961-964, Honk Kong,
2010.
[8] Zhihai He and Mitra, S.K. p -domain bit allocation and rate control for real time video
coding. International Conference on Image Processing, 3:546-549,2001.
[9] Do-Kyoung Kwon and Mei-Yin Shen and Kuo, C.-CJ. Rate Control for H.264 Video
With Enhanced Rate and Distortion Models. IEEE Transactions on Circuits and Systems
for Video Technology, 17(5):517-529,2007.
[10] Hung-Ju Lee and Tihao Chiang and Ya-Qin Zhang. Scalable rate control for MPEG-
4 video. IEEE Transactions on Circuits and Systems for Video Technology, 10(6):878 -
894,2000.
[11] Zhengguo Li and Feng Pan and Keng Pang Lim and Genan Feng and Xiao Lin and
Susanto Rahardja. Adaptive Basic Unit Layer Rate Control for JVT. Joint Video Team
(JVT) of ISO/IEC MPEG & ITU-T VCEG, 2003. JVT-G012.
[12] Ma, S. and Wen Gao and Yan Lu. Rate-distortion analysis for H.264/AVC video
coding and its application to rate control. IEEE Transactions on Circuits and Systems for
Video Technology, 15(12):1533-1544,2005.
[13] Petovello, M. and OaKeefe, K. and Lachapelle, G. and Cannon, M. Consideration of
time-correlated errors in a Kalman filter applicable to GNSS. Journal of Geodesy, 83:51-
56, 2009.
[14] Rec. ITU-T H.264 and ISO/IEC 14496-10 (MPEG4-AVC). Advanced video coding
for generic audiovisual services. 2010.
[15] Sermadevi, Y. and Hemami, S.S. and Masry, M. Convex Programming Formulations
for Rate Allocation in Video Coding. IEEE Transactions on Circuits and Systems for
Video Technology, 16(8):947-959,2006.
[16] Simon, D. and Tien Li Chia. Kalman filtering with state equality constraints. IEEE
Transactions on Aerospace and Electronic Systems, 38(1): 128 -136,2002.
[17] Dan Simon. Optimal State Estimation: Kalman, H Infinity, and Nonlinear
Approaches. Wiley-Interscience, 2006.
[18] Devinderjit Sivia and John Skilling. Data Analysis: A Bayesian Tutorial. Oxford
University Press, USA, 2 edition, 2006.
[19] H. W. Sorenson. Least-squares estimation; from Gauss to Kalman. IEEE Spectrum,
7:63-68, 1970.
[20] Robert F. Stengel. Optimal Control and Estimation (Dover Books on Advanced
Mathematics). Dover Publications, 1994.
[21] Koichi Takagi and Yasuhiro Takishima and Yasuyuki Nakajima. A study on rate
distortion optimization scheme for JVT coder. Proc. SPIE, 5150:914-923, 2003.
[22] Vetro, A. and Huifang Sun and Yao Wang. MPEG-4 rate control for multiple video
objects. IEEE Transactions on Circuits and Systems for Video Technology, 9(1):186-199,
1999.
[23] Webb, J.L.H. and Oehler, K. A simple rate-distortion model, parameter estimation,
and application to real-time rate control for DCT-based coders. International Conference
on Image Processing. Proceedings.,2:13-16, 1997.
[24] Yimin Zhou and Yu Sun and Zhidan Feng and Shixin Sun. New rate-distortion
modeling and efficient rate control for H.264/AVC video coding. Signal Processing:
Image Communication, 24(5):345 - 356,2009.
Claims
1. Apparatus for estimating model parameters of a rate- or distortion-quantization
model function (26) so as to approximate an actual rate- or distortion-quantization
function (20) of a video encoder (12) for a frame sequence (14), comprising
an updater (28) configured to perform a prediction step (50) of a time-discrete
Kalman filter, a state of which defines a parameter estimate for the model
parameters to obtain a predicted state of the time-discrete Kalman filter for a
current frame (k) of the frame sequence (14) from a state of the time-discrete
Kalman filter for a previous frame (k-1) of the frame sequence (14);
a first corrector (30) configured to determine a complexity measure of the current
frame k, and perform a correction step (52) of the time-discrete Kalman filter using
a measurement value which depends on the complexity measure determined so as
to obtain a primarily corrected state of the time-discrete Kalman filter from the
predicted state and
a second corrector (32) configured to perform a correction step (54) of the time-
discrete Kalman filter using a measurement value which depends on an actual
coding rate or distortion (42) of the video encoder (12) in encoding the current
frame (k) using a predetermined quantization.
2. Apparatus in accordance with claim 1, wherein the updater (28) is configured to, in
performing the prediction step of the time-discrete Kalman filter, use an identity
matrix as state transition matrix so that the predicted state adopts the parameter
estimate defined by the state of the time-discrete Kalman filter for the previous
frame and increase an uncertainty of the predicted state relative to the state of the
time-discrete Kalman filter for the previous frame.
3. Apparatus according to claim 2, wherein the updater (28) is configured to
determine a similarity measure between the current frame (k) and the previous
frame (k - 1) and increase the uncertainty of the predicted state by an amount which
depends on the similarity measure.
4. Apparatus according to any of claims 1 to 3, wherein the first corrector (30) is
configured to, in determining the complexity measure, determine a measure for a
deviation between a provisionally predicted frame determined by motion
compensated prediction, and the current frame and/or a measure for a dispersion of
a spread of sample values of the current frame around a central tendency of the
spread.
5. Apparatus according to any of claims 1 to 4, wherein the first corrector (30) is
configured to predict the model parameters of the rate- or distortion-quantization
model function for the current frame (k) based on the complexity measure
determined, and to perform the correction step using a measurement value
depending on a difference between the predicted model parameters and a result of a
prediction of the model parameters for the previous frame based on a complexity
measure determined for the previous frame, applied to a correlation matrix, and a
measurement matrix equal to the identity matrix minus the correlation matrix.
6. Apparatus according to claim 5, wherein the first corrector (30) is configured to set
the correlation matrix depending on a similarity between the current frame and the
previous frame.
7. Apparatus in accordance with any of claims 1 to 6, wherein the second corrector is
configured to perform the correction step of the time-discrete Kalman filter using
the measurement value using a measurement matrix which depends on a
linearversion of a linear relation between the model parameters and the coding rate
or distortion in accordance with the rate- or distortion-quantization model function
(26) for the predetermined quantization, at the primarily corrected state
8. Apparatus in accordance with any of claims 1 to 6, wherein the second corrector is
configured to perform the correction step of the time-discrete Kalman filter using
the measurement value using a measurement matrix which depends on a linearized
version of a relation between the model parameters and the coding rate or distortion
in accordance with the rate- or distortion-quantization model function (26) for the
predetermined quantization, linearized at the primarily corrected state
9. Apparatus according to claim 8, wherein the rate- or distortion-quantization model
function is a rate-quantization model function and the first corrector is configured
to predict the model parameters of the rate-quantization model function for the
current frame k based on the complexity measure determined and to determine the
measurement value for the correction step depending on the predicted model
parameters, and the second corrector is configured to determine the measurement
matrix dependent on the linearized version of the relation between the model
parameters and the coding rate in accordance with the rate-quantization model
function, both such that the rate-quantization model function / relating the
quantization q by the video encoder to the coding rate of the video encoder is a
piecewise function comprising a quadratic function piece within a finer
quantization interval, and an exponential function piece within a coarser
quantization interval.
10. Apparatus according to any of claims 8 and 9, wherein the first corrector is
configured to predict the model parameters of the rate-quantization model function
for the current frame k based on the complexity measure determined and to
determine the measurement value for the correction step depending on the predicted
model parameters, and the second corrector is configured to determine the
measurement matrix dependent on the linearized version of the relation between the
model parameters and the coding rate in accordance with the rate-quantization
model function, both such that the rate-quantization model function/relating the
quantization q by the video encoder to the coding rate of the video encoder is

with ß = [a1'b1'c1'm,a2'b2,c2] and N defining a range for quantization q so that 0