Method of frame-by-frame calculation of quantization matrices

A method of reducing distortion in a video signal by coding a video frame utilizing a quantization matrix specifically determined for the video frame. The method includes the steps of determining the degree to which the video signal is spread about an average value, determining an average quantizer scale-value Q for the video frame, determining a reference weighted distortion for all DCT frequency bands in the video frame, determining the quantization parameter through a normalized distortion function, determining each weight for each DCT frequency band and coding the video frame taking into account the determined weights in the quantization matrix.

FIELD OF THE INVENTION 
The present invention relates to digital video compression techniques in 
general, and in particular, to a method of minimizing the distortion in a 
video by selective calculation of quantization matrices. 
DESCRIPTION OF THE RELATED ART 
In an MPEG2 intra-only encoder, such as an encoder that generates 
MPEG2-conformant bitstreams, the compression process consist of DCT 
transform, scalar quantization and run-length coding. Among these three 
steps, quantization is the core of compression and the primary phase where 
distortion is introduced. In a well-designed quantization scheme, the 
amount of compression distortion tolerable is weighed against the 
available bit-rate transmission capabilities. That is, given a 
coefficient, the smaller the quantization step-size, the smaller the 
distortion introduced. However, achieving a smaller step size requires 
additional bits to code the coefficient. 
The ultimate goal of any quantization scheme designed for image or video 
compression is to achieve the best visual quality under the given bit 
budget. The article entitled "Image Coding Applications of Vision Models, 
by D. J. Sakrison, and published in Image Transmission Techniques, W. K. 
Pratt, Ed., New York Academic Press, May, 1979, pp.21-51, highlights that 
it is known that the human visual system (HVS) responds differently to 
distortion in an image in different frequency-bands, and therefore, it is 
desirable that the encoder has control over the distribution of distortion 
in all the frequency-bands. The present invention takes advantage of the 
fact that MPEG2 provides for the transmission of quantization matrices on 
a frame-by-frame basis to enable processing each frequency-band 
differently. 
A quantization matrix consists of sixty-four entries, each entry being 
designated a weight, which, together with a quantizer scale-value, 
determine quantization step-sizes for a block of DCT coefficients. The 
sixty-four (64) entries, each being an 8-bit integer ranging from 1 to 
255, correspond to 8.times.8 DCT coefficients in a block. Because a DCT 
coefficient is divided by its corresponding weight, larger weights imply 
coarser quantization, and consequently require fewer bits to code that 
coefficient. By adjusting the entries in the quantization matrix relative 
to each other, the encoder can control both the distortion in DCT 
frequency-bands and the number of bits needed for that band. 
Many factors, among them contrast masking and error pooling, can impact the 
amount of perceived distortion in different frequency-bands. Additionally, 
contrast sensitivity, which is the varying sensitivity of the HVS to even 
the same amount of distortion in different frequency-bands, impacts the 
amount of perceived distortion. This phenomenon was recognized in 
Sakrison's work and can be described by a Modulation Transfer Function 
(MTF). Also impacting the amount of perceived distortion is the fact that 
quantization distortion across different frequency-bands can differ even 
if the same quantization scheme is used for all bands, because DCT 
coefficients from a range of frequency-bands have different statistics. 
Therefore, in designing optimal quantization matrices, contrast 
sensitivity and quantization distortion must be considered to achieve a 
better visual quality. 
Calculation of quantization matrices has been widely investigated. In the 
Grand Alliance HDTV system, the quantization matrix is adjusted such that 
the distribution of DCT coefficients in each frequency-band best matches 
the "optimal" distribution for the Variable-Length-Code table provided by 
the MPEG standard. A Laplacian model is used to describe the distribution 
of the DCT coefficients. 
The aforementioned "Image Coding Applications of Vision Models" article 
also describes an "or" system to model the human perception of distortion 
in a picture. Specifically, the perceptually weighted distortion for each 
frequency band is compared to a threshold, and if any of the distortion 
exceeds that threshold, then the altered image can be distinguished from 
the original, or the altered image is said to be perceptually distorted 
from the original. Based on this model, in an article entitled "Signal 
Compression Based on Models of Human Perception" by Messrs. Jayant, 
Johnston and Safranek, and published in the Proceedings of the IEEE, Vol. 
81, No. 10, October, 1993, a perceptual distortion measure, called JND 
(Just Noticeable Difference) or MND (Maximum Noticeable Difference) is 
proposed. This proposal describes the subjective quality of a picture and 
a method that utilizes the MND measure to optimize image quality. In other 
works on computing quantization matrices for individual pictures, such as 
"DCT Quantization Matrices Visually Optimized For Individual Images", 
Human Vision, Visual Processing and Digital Display IV, (B. E. Rogowitz, 
Ed. Proceedings of the SPIE, 1993, pp. 1913-14) by A. B. Watson, there is 
an incorporation of contrast sensitivity, contrast masking and error 
pooling. However, this known method is achieved through undesirably large 
amounts of computation which is avoided by the present invention. 
Therefore, while there are several ways to tune the quantization scheme in 
an MPEG2 encoder, such as changing the quantizer scale-value on a 
macroblock-by-macroblock basis, arbitrarily determining the quantization 
boundaries (used to decide on what levels to quantize the coefficients) by 
the encoder, a method to control (or regulate) distortion across frequency 
bands by updating the quantization matrix on a frame by frame basis and an 
improved method to calculate a quantization matrix, is desired. 
SUMMARY OF THE INVENTION 
In accordance with the invention, a method of reducing distortion in a 
video signal by coding a video frame utilizing a quantization matrix 
specifically determined for the video frame is provided. The method 
preferably includes the steps of determining the degree to which the video 
signal is spread about an average value, determining the average quantizer 
scale-value Q for the video frame, determining a reference weighted 
distortion for all DCT frequency bands in the video frame to which the 
weighted distortion of every AC frequency band shall be equal, determining 
the quantization parameter through a normalized distortion function 
f(.beta.), determining each weight W.sub.k,l for each DCT frequency band, 
and coding the video frame taking into account the determined weights in 
the quantization matrix. 
In an alternative embodiment, the method in accordance with the invention 
includes initially generating a look-up table for determining 
.beta..sub.k,l as a function of f(.beta..sub.k,l), determining an average 
quantizer scale value Q for a video frame, determining a reference 
weighted distortion by fixing the weight for the first frequency band to a 
predetermined value, and thereafter repeating only the steps of 
determining the degree to which an input signal is spread about an average 
value (.lambda.) of the DCT coefficients, determining the normalized 
weighted distortion f(.beta..sub.k,i), looking up .beta.(.sub.k,l) of as a 
function of f(.beta..sub.k,l) from the table, computing the weights for 
the respective frequency bands, and coding the video frame using the 
calculated matrix. 
Therefore, in accordance with the invention, a method of reducing 
distortion in a video signal by coding a video frame utilizing a 
quantization matrix specifically determined for the video frame is 
provided. 
Accordingly, an object of the present invention is to provide an improved 
method of minimizing the distortion resulting from each frequency band in 
a video frame. 
Still a further object of the present invention is to reduce the perceived 
visual distortion in a video picture. 
Another object of the invention is to provide an improved method of 
computing quantization matrices so as to achieve an improved video picture 
via a reduction in perceived visual distortion. 
Still other objects of the invention will in part be obvious and will in 
part be apparent from the specification. 
The invention accordingly comprises the several steps and the relation of 
one or more of such steps with respect to each of the others, and the 
apparatus embodying features of construction, combination of elements, and 
arrangement of parts which are adapted to effect such steps, all as 
exemplified in the following detailed disclosure, and the scope of the 
invention will be indicated in the claims.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
Reference is now made to FIG. 1, wherein a coding system, generally 
indicated at 100, constructed in accordance with the present invention, is 
depicted. System 100 is particularly suited for performing the method of 
the present invention which includes the calculation of the quantization 
matrix on a frame by frame basis. For the embodiment depicted in FIG. 1, a 
video signal is inputted to a redundant field/frame detector 105. Detector 
105 is coupled to a discrete cosine transformer 110, an adaptive 
field/frame decision block 115, a ME/ME Mode Selector 120 and a buffer 
125, the functions of which would be well understood by one of ordinary 
skill in the art. Likewise, as would be understood by one of skill in the 
art, selector 120 is coupled to decision block 115 and a second discrete 
cosine transformer 130. Still further, transformer 110 is coupled to a 
first pass coder 135, which itself is coupled to a matrix calculator 140 
and an adaptive quantization controller 145. A second pass coder 150 is 
coupled to the outputs of calculator 140 and controller 145. As would also 
be understood in the art, coder 150 is coupled to a frame storer 155 
(which itself is coupled to selector 120), buffer 125, a history block 
160, transformers 110 and 130 and coder 135, the interrelationship 
therebetween all being understood by one of ordinary skill in the art. 
Lastly, a rate allocator 165 is provided and coupled to history block 160, 
buffer 125 and controller 145. 
In operation, a video input signal is organized into frames. Motion 
estimation is performed if the current picture type is Non-Intra. The 
frame is then divided into blocks and DCT transformed depending on whether 
frame-DCT or field-DCT should be used for each macroblock. First-pass 
coding is carried out, and an average quantizer-scale Q for this frame is 
estimated as a function of the bit-allocation for this frame. Quantization 
matrices are calculated for Intra pictures and used in coding the 
Intra-pictures. 
Generally speaking, In any DCT based coding method that permits updating 
quantization matrices, such as MPEG2, DCT transform is performed on 
blocks, each of which contains 8.times.8 pixels. The 8.times.8 DCT 
coefficients are then quantized according to the quantizer scale-value for 
that macroblock, the quantization matrix (or matrices, in the case of 
4:2:2 or 4:4:4 chroma resolution), and the decision boundaries. 
To measure the visually perceived deviation of the compressed image from 
the original, a weighted-distortion measure is used. The mean-squared 
(unweighted) distortion is first calculated for all frequency-bands, and 
then weighted by a perceptual-weighting table based on the MTF function 
for the particular viewing condition. Since the original MTF function was 
obtained for Fourier Transform coefficients, it must be modified in order 
to be used on DCT coefficients. These steps have been proposed in an 
article entitled "A Visual Model Weighted Cosine Transform for Image 
Compression and Quality Assessment", by N. B. Nill IEEE Trans. Comm., Vol. 
Com-33, No. 6, June, 1985, using a modification function for the MTF. 
Additionally, calculation of quantization matrices involves minimizing the 
summation of perceptually weighted distortion over all macroblocks for a 
picture while being constrained by a bit budget. The distortion weighting 
is based on contrast sensitivity. 
There are two types of usage for quantization matrices due to different 
chrominance resolutions. Therefore, the data set needed to calculate each 
quantization matrix is not always the same. For example, in the case of 
4:2:0 chrominance resolution, where luminance and chrominance signals 
share one quantization matrix, the set of data used to calculate the 
quantization matrix is the set of all three components, i.e., Y, U and V. 
In the case of 4:2:2 or 4:4:4 chrominance resolution, a separate 
quantization matrix is allowed for chroma, where the data needed to 
calculate one of the two matrices is either luma or chroma. 
If d.sub.k,l represents the weighted-distortion for the (k,l)th 
frequency-band, the (k,l)th entry in the perceptual-weighting table being 
denoted .alpha..sub.k,l and the (k,l)th DCT coefficient in block Number b 
being denoted C.sub.k,l.sup.b, then the weighted distortion for the 
(k,l)th frequency band d.sub.k,l is 
##EQU1## 
This quantity represents the summation of quantization distortion of the 
(k,l)th frequency band over the entire frame after being weighted by the 
corresponding perceptual-weighting factor .alpha..sub.k,l, where 
.alpha..sub.k,l is a constant set in dependence on viewing conditions, B 
is the total number of blocks in the frame, and C.sub.k,l.sup..about.b is 
the quantized DCT coefficient for the (k,l)th frequency band. 
Two approaches can be used to obtain d.sub.k,l as a function of the 
quantization matrix. One less than desirable approach is to actually 
quantize the coefficients using a large number of well-chosen matrices and 
calculate the distortion, which requires a large amount of computation. 
The other approach is to mathematically model the statistical properties 
of the DCT coefficients and find an analytical expression for the 
distortion in terms of the parameters of the quantizer. Although the 
effectiveness of the analytical approach depends on the accuracy of the 
model, an explicit expression is much easier to manipulate and evaluate. 
It is known from work published in a book entitled Digital Pictures, pp. 
206-218, by Netravali and Haskell (Plenum Press, 1995) that the statistics 
of AC DCT coefficients can be modeled by Laplacian distribution. By 
modeling the data using Laplacian distribution, the statistics of the DCT 
coefficients of a particular frequency-band can be described by a single 
variable which can be estimated from the data in the current frame. 
Further, with the same model, there is a closed-form relationship between 
the quantization error and the quantization step-size, and this greatly 
saves computation. Therefore, the Laplacian model for DCT coefficients is 
preferred. 
The probability-distribution function of a Laplacian random variable X with 
parameter .lambda. is: 
##EQU2## 
The variance of X, .sigma..sub.X,.sup.2 is 2.lambda..sup.2, and 
##EQU3## 
where B is the block index. Lambda (.lambda.) represents how spread out 
the signal is around the average value of the DCT coefficients. Therefore, 
.lambda. for the (k,l)th frequency band is denoted .lambda..sub.k,l and 
the corresponding variance is .sigma..sub.k,l.sup.2 
=2.lambda..sub.k,l.sup.2. 
The reconstruction levels, mandated by the MPEG Standard, represent (are a 
function of) the reconstructed quantized, DCT coefficient and, for the 
(k,l)th frequency-band are r.sub.k,l.sup.i, i=0,.+-.1.+-.2,.+-.3,.+-.4 
where i indexes the reconstruction level closest to x. The 
weighted-distortion for the (k,l)th frequency-band is then 
##EQU4## 
where a.sub.i and b.sub.i, which are commonly used in MPEG-2Test Model 5, 
are the lower and upper quantization boundaries respectively. Therefore, 
r.sub.k,l.sup.i for an intra picture as mandated by the MPEG2 standard is: 
##EQU5## 
W.sub.k,l is the (k,l)th weight entry of the quantization matrix. Q is used 
as the quantizer scale-value for every macroblock as an approximation, as 
the quantizer scale-value for each macroblock varies according to the 
local complexity and the buffer fullness. Nevertheless, Q serves as a good 
approximation for the entire picture. 
As stated above, with the MPEG-2 Test-Model 5 quantizer being used, the 
values a.sub.i and b.sub.i are 
EQU a.sub.i =r.sub.k,l.sup.i -0.5 .DELTA..sub.k,l (Eq. 5) 
EQU b.sub.i =r.sub.k,l.sup.i +0.5 .DELTA..sub.k,l. (EQ. 6) 
.DELTA..sub.k,l is the quantization step-size for the (k,l)th band and 
##EQU6## 
Replacing a.sub.i from Eq. 5, b.sub.i from Eq. 6 and p.sub.x (x) from Eq. 
2, the weighted distortion (see Eq. 3) for the (k,l)th frequency can be 
stated as: 
##EQU7## 
where .beta..sub.k,l is defined as 
##EQU8## 
The maximal noticeable difference (MND) of the picture therefore is 
EQU MND=max.sub.k,l (d.sub.k,l) (Eq. 10) 
It can be established that the minimization of MND requires all d.sub.k,l 
's to be equal. This can be established by considering the alternative, 
that is, if one or more d.sub.k,l 's is (are) larger than the others. The 
maximum of these "larger" d.sub.k,l 's can always be reduced by raising 
the smaller distortions and reducing these "larger" ones. Accordingly, it 
can be seen that the minimization of the maximum distortion can be 
achieved by equating all the d.sub.k,l 's. 
Accordingly, it is subsequently necessary to find the minimum possible 
weighted distortion to which all d.sub.k,l 's should be equal. However, 
because it is the relative magnitudes of the matrix entries that determine 
how to quantize the several DCT frequency bands, it is possible to select 
a reference frequency band with a fixed quantization weight, for example, 
16, and use the reference frequency band to calculate the reference 
weighted distortion. However, it should be understood that other values 
could be selected. 
It is preferable to use one of the lowest frequency bands other than DC as 
the reference frequency band. If this selected frequency band is 
designated 0,1 and .alpha..sub.0,l is set equal to one (1) and the 
corresponding quantization matrix entry is set to 16, then the reference 
weighted distortion can be characterized as: 
##EQU9## 
As stated above, Q can be estimated from the coding history or from the 
first pass coding, both of which should be understood by one of ordinary 
skill in the art. Since the value of Q reflects the bit allocation to the 
current frame as well as the complexity of the picture, it determines the 
minimum possible perceptual distortion given the number of bits and the 
current picture being coded. 
Now that d.sub.0 has been solved, the weighted distortion for all other 
frequency bands can be found from the relationship 
EQU d.sub.k,l =d.sub.0, (k,l).noteq.(0,0). (Eq. 12) 
That is, 
##EQU10## 
and, since .alpha..sub.k,l is a constant and .lambda..sub.k,l can, as 
stated above, be estimated from the unquantized DCT coefficients, a 
normalized distortion function f(.beta..sub.k,l) can be derived as: 
##EQU11## 
Referring now to FIG. 3, it can be seen that f(.beta..sub.k,l) 
monotonically increases from 0 to 1, which is consistent with the 
appreciation that the quantization distortion increases with the step 
sizes and is never greater than the variance of the input data. Therefore, 
the expression for f(.beta..sub.k,l) becomes: 
##EQU12## 
As can be observed from FIG. 3 and Equation 15, it is possible for 
f(.beta..sub.k,l) to be greater than 1, in which case Eq. 15 does not have 
a solution. This can be seen when Q is large, especially for high 
frequency-bands. However, if such a situation occurs, it can be 
appreciated that even though W.sub.k,l is infinity, i.e., every 
coefficient in that frequency-band is quantized to 0, the 
weighted-distortion for that band is still lower than the reference 
weighted-distortion. Hence the entire frequency-band can be quantized to 
0. In other words, the value of f(.beta..sub.k,l) can be used as a 
criterion to drop coefficients. 
For clarity, reference is now made to FIG. 2A which depicts the method 
steps in accordance with the present invention. Specifically, the method 
of reducing distortion in a video signal by coding a video frame utilizing 
a quantization matrix specifically determined for the video frame, 
includes a first step of determining the degree to which the video signal 
is spread about an average value of the DCT coefficients (step 10), then 
determining the weighted distortion for all DCT frequency bands in the 
video frame (step 20), and thereafter determining the individual weights 
in a quantization matrix in each of the DCT frequency bands such that the 
weighted distortion across all the frequency bands is minimized (step 30). 
This third step can be achieved by further carrying out the steps of 
determining a normalized distortion function f(B.sub.k,l), where 
##EQU13## 
(step 40), determining the average quantizer scale-value Q for the video 
frame (step 50), and determining each weight W.sub.k,l for each DCT 
frequency band from the relationship: 
##EQU14## 
(step 60). Lastly, the video frame is coded taking into account the 
determined weights in the quantization matrix (step 70). That is, with the 
quantization matrix being calculated, one skilled in the art would know 
how to code the video frame, and for brevity, such explanation will be 
omitted herein. 
The step of determining the average quantizer scale-value Q (step 50) may 
include the substeps of estimating Q from the first coding pass in a 
two-pass coding system or estimating Q from the coding history. 
In an alternate embodiment, the method of reducing distortion for each 
frequency band on an outputted video signal can be carried out by the 
steps indicated in FIG. 2B. Initially, a look-up table, a portion of which 
is depicted below 
__________________________________________________________________________ 
f 0.040483 
0.041273 
0.042070 
0.042874 
0.043684 
0.044502 
0.045327 
0.046158 
0.046996 
0.047841 
__________________________________________________________________________ 
.beta. 
1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 
__________________________________________________________________________ 
may be generated for determining .beta..sub.k,l as a function of 
f(.beta..sub.k,l), where 
##EQU15## 
(step 100), an average quantizer scale value Q is determined for a video 
frame (step 110) and a reference weighted distortion is determined (step 
120) by preferably fixing the weight for the first frequency band to 16. 
The method need not again repeat steps 100, 110 and 120, but need only, if 
applicable, repeat steps 130-170, wherein step 130 includes determining 
the degree to which an input signal is spread about an average value 
(.lambda.) of the DCT coefficients, step 140 includes determining the 
normalized weighted distortion f(.beta..sub.k,l), wherein: 
##EQU16## 
step 150 includes looking up .beta..sub.k,l of as a function of 
f(.beta..sub.k,l) step 160 includes computing the weights for the 
respective frequency bands from the relationship: 
##EQU17## 
and step 170 includes coding the video frame using the calculated matrix. 
Utilizing the method as claimed herein achieves a significant reduction in 
the visual distortion. For example, FIGS. 4 and 5 illustrate the 
significant improvements in distortion minimization utilizing the claimed 
method. All the intra coding has been performed on standard definition 
(SD) as well as high definition (HD) video sequences. The coded sequences 
depicted in the solid lines utilized the MPEG2 default intra matrix, while 
the dashed lines illustrate the reduced distortion achieved by the claimed 
method. For the SD sequences, the bit-rate is 30 Mbits/second, while for 
the HD sequences, the bit rate was 129 Mbits/second. The chroma resolution 
was 4:2:2 for all coding simulations. Two quantization matrices are 
computed for the three luminance and chrominance components. The reference 
weighted-distortion for chrominance is selected to be the same as that of 
the luminance component. 
In particular, FIGS. 4 and 5 illustrate the distribution of the 
perceptually-weighted distortion by frequency-band of luma and chroma for 
"table tennis" and "winter trees" . As stated above, the dashed lines 
represent the results obtained by using the calculated quantization 
matrices as disclosed herein, while the solid lines stand for the result s 
obtained by using the default intra matrix. 
More specifically, FIGS. 4A and 5A illustrate the weighted-distortion of 
luma while FIGS. 4B and 4B illustrate the maximum of the 
weighted-distortion of the two chrominance components. In both cases, the 
variation of the weighted-distortion is much smaller and the maximum of 
the weighted distortion is much smaller if the calculated quantization 
matrices are used as disclosed herein. 
The contrast illustrated in FIG. 4 is quite visible for luminance, while in 
FIG. 5, the distinction is somewhat less due to the MPEG2 default matrix 
being similar to those calculated in accordance with the invention. 
Although the weighted-distortion for chrominance is higher if the 
calculated quantization matrices are used than if the MPEG2 default matrix 
is used, this is so because when computing the quantization matrices, t he 
target weighted-distortion for chrominance is set to be equal to that of 
the luminance, which is higher than the weighted-distortion for 
chrominance if the default matrix is used to quantize both luma and 
chroma. By updating the quantization matrices dynamically using the 
claimed method, the encoder can control the quantization of luma and 
chroma depending on the requirement of applications.