`US 6,668,088 B1
`(10) Patent No.:
`Dec. 23, 2003
`(45) Date of Patent:
`Werneret al.
`
`
`US006668088B1
`
`.
`
`<
`
`(75)
`
`(54) DIGITAL SIGNAL COMPRESSION
`ENCODING WITH IMPROVED
`QUANTISATION
`aon
`Inventors: Craydon(GB):NicholasDomainic
`7
`N
`Wells, Brighton (GB); Michael James
`Knee,Petersfield (GB)
`(73) Assignees: British Broadcasting Corporation,
`London (GB); Snell & Wilcox Limited,
`Middlesex (GB)
`
`(*) Notice:
`
`(21) Appl. No.:
`
`Subject to anydisclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C, 154(b) by 0 days.
`09/380,047
`
`(22)
`
`PCTFiled:
`
`Feb. 25, 1998
`
`(86) PCT No.:
`
`PCT/GB98/00582
`
`§ 371 (c)(1),
`(2), (4) Date:
`
`Nov. 29, 1999
`
`(87) PCT Pub. No.: WO98/38800
`
`PCT Pub. Date: Sep. 3, 1998
`
`(30)
`
`Foreign Application Priority Data
`
`Feb. 25, 1997
`Teb. 25, 1997
`
`(GB) ooceeceeceeccesecseceseetecseseneeeeees 9703831
`(GB) woceeceeceeccesccseceseetecseseneeeeees 9703834
`
`Int. Ch? ieee G06K 9/36; GO6K 9/46
`(51)
`(52) U.S.C oe 382/239; 375/240.03; 382/251
`(58) Field of Search oo... 382/236, 239,
`382/245, 246, 248, 250, 251; 375/240.02-240.07,
`240.18, 240.2, 240.23; 348/404.1, 405.1,
`419.1, 395.1
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`3/1994 Feig etal. we. 382/234
`5,293,434 A *
`4/1994 Gonzales etal.
`......... 382/239
`5,301,242 A *
`
`5/1995 Glover .......
`.. 375/240.11
`5,412,429 A *
`5/1996 Yim veeeesseeesseessseeeessees 348/419
`5,521,643 A
`
`6/1998 Keesman ve. 382/248
`5,768,436 A *
`7/1998 Schusteret al.
`........... 709/247
`5,778,192 A *
`
`5,933,194 A *
`8/1999 Kimetal. veces 348/403.1
`!
`imeta
`933,
`!
`FOREIGN PATENT DOCUMENTS
`35 11 659
`10/1986
`eeseeseeee H03M/7/38
`
`... HO4N/7/30
`0 478 230
`4/1992
`10/1992 HOAN/7/133
`0 509 576
`11/1992 eee HOAN/7/133
`0 513 520
`0 599 258 ee HO4N/7/133
`Oat 030
`3)to0e
`ttees
`oo HOAN/TD6
`0 711 079
`5/1996
`............ HOAN/7/50
`0 720 375
`F/A996 .. HO4N/7/26
`0 739 138
`10/1996
`vase.
`.. HO4N/7/26
`95 35628
`12/1995
`asses
`... HOAN/7/26
`96 34496
`LO/1996aeseessee HO4N/7/30
`
`DE
`EP
`EP
`EP
`EP
`bp
`EP
`EP
`EP
`wo
`wo
`
`* cited by examiner
`
`Primary Examiner—limothy M. Johnson
`(74) Attorney, Agent, or Firm—McDermott, Will & Emery
`
`(57)
`
`ABSTRACT
`
`In compression encoding of a digital signal, such as
`MPEG?,transform coefficients are quantised with the lower
`bound of each interval being controlled by a parameter 4. In
`the MPEG2 reference coder, for example, }=0.75. Because
`the quantised coefficients are variable length coded,
`improved quality or reduced bit rates can be achieved by
`controlling 4 so as to vary dynamically the bound of each
`interval with respect to the associated representation level.
`The parameter } can vary with coefficient amplitude, with
`frequency, or with quantisation step size. In a transcoding
`operation, ” can also vary with parameters in the initial
`coding operation.
`
`5,245,427 A *
`
`9/1993 Kunihiro ......... 348/400.1
`
`4 Claims, 3 Drawing Sheets
`
`DCT
`COEFFS.
`
`LINEAR
`QUANTIZER
`
`64
`
` TRUNCATE
`QUANTIZER
`
`
`SCALE
`
`
`
` COMPARATORSa CALCULATE|658
`
`
`
`ESTIMATE
`pdi
`
`PARAMETERS
`
`
`LAMBDA/2
`
`IPR2022-01227
`IPR2022-01227
`EXHIBIT 1022 - PAGE 0001
`EXHIBIT 1022 - PAGE 0001
`
`
`
`U.S. Patent
`
`Dee. 23, 2003
`
`Sheet 1 of 3
`
`US 6,668,088 B1
`
`Fig.1.
`
`qi
`
`|
`
`x
`
`di}
`
`ri
`
`d4(l41)
`
`1 (+1)
`
`d4(l+2)
`
`Fig.2.
`
`DCT
`
`COEFF.||=MULTIPLY
`BY 32/W
`
`
`
`
`
`QUANTIZER
`SCALE
`
`DIVIDE BY
`2q
`
`CALCULATE
`q’LAMBDA
`
`IPR2022-01227
`IPR2022-01227
`EXHIBIT 1022 - PAGE 0002
`EXHIBIT 1022 - PAGE 0002
`
`
`
`U.S. Patent
`
`Dee. 23, 2003
`
`Sheet 2 of 3
`
`US 6,668,088 B1
`
`Fig.3.
`
`DCT
`COEFF.
`
`
`DIVIDE BY W
`
`
`QUANTIZER SCALE
`
`TRUNCATE
`
`DIVIDE BY q
`
`
`
`LAMBDA/2
`
`
`Fig.4.
`
`SCALED DCT COEFF.
`
`CODE
`
`
`OUTPUT
`
`TRUNCATE
`
`LAMBDA/2
`
`IPR2022-01227
`IPR2022-01227
`EXHIBIT 1022 - PAGE 0003
`EXHIBIT 1022 - PAGE 0003
`
`
`
`U.S. Patent
`
`Dee. 23, 2003
`
`Sheet 3 of 3
`
`US 6,668,088 B1
`
`Fig.5.
`
`
`DCT
`COEFFS.
`TRUNCATE
`
`
`QUANTIZER
`
`SCALE
`
`
`COMPARATORS-| CALCULATE
`
` LINEAR
`QUANTIZER
`
`
`
`
`ESTIMATE
`
`BUILD
`pdi
`
`HISTOGRAM
`PARAMETERS
`
`
`
`
`
`LAMBDA/2
`
`Fig.6.
`
`OUTPUT
`
`CODE
`
` SCALED( DCTCOEFF.
`
`
`
`
`
`
`CODING COST
`CALCULATE
`-O O A Cc v
`LAMBDA/2
`
`
`TABLE
`
`
`TRUNCATE
`
`TRUNCATE
`
`
`
`70
`
`IPR2022-01227
`IPR2022-01227
`EXHIBIT 1022 - PAGE 0004
`EXHIBIT 1022 - PAGE 0004
`
`
`
`US 6,668,088 B1
`
`1
`DIGITAL SIGNAL COMPRESSION
`ENCODING WITH IMPROVED
`QUANTISATION
`
`FIELD OF THE INVENTION
`
`This invention relates to the compression of digital video,
`audio or other signals.
`
`BACKGROUND OFTHE INVENTION
`
`Compression encoding generally involves a number of
`separate techniques. These will usually include a
`transformation, such as the block-based discrete cosine
`transform (DCT) of MPEG-2; an optional prediction step; a
`quantisation step and variable length coding. This invention
`1s particularly concerned in this context with quantisation.
`The quantisation step maps a range of original amplitudes
`onto the same representation level. The quantisation process
`is therefore irreversible. MPEG-2, (in common with other
`compression standards such as MPEG-1, JPEG, CCITT/
`ITU-T Rec.H.261 and ITU-T Rec.H.263) defines represen-
`tation levels and leaves undefined the manner in which the
`original amplitudes are mapped onto a given set of repre-
`sentation levels.
`
`
`
`In general terms, a quantizer assigns to an input value,
`which may be continuous or may previously have been
`subjected to a quantisation process, a code usually selected
`rom quantization levels immediately above and immedi-
`ately below the input value. The error in such a quantization
`will generally be minimised if the quantization level closest
`o the input value is selected. In a compression system,it is
`further necessary to consider the efficiency with which
`respective quantization levels may be coded. In variable
`ength coding, the quantization levels which are employed
`most frequently are assigned the shortest codes.
`Typically, the zero level has the shortest code. A decision
`o assign a higher quantization level, on the basis that it is
`he closest, rather than a lower level (and especially the zero
`evel) will therefore decrease coding efficiency. In MPEG2,
`he overall bit rate of the compressed signal is maintained
`beneath a pre-determined limit by increasing the separation
`of quantization levels in response to a tendency toward
`higher bit rate. Repeated decisions to assign quantization
`evels on the basis of which is closest, may through coding
`inefficiency thus lead to a coarser quantization process.
`The behaviour of a quantizer in this respect may be
`characterised through a parameter ) whichis arithmetically
`combined with the input value, with one value of A”
`(typically X=1) representing the selection of the closest
`quantization level or “rounding”. A different value of A
`(typically 1=0) will
`in contrast represent
`the automatic
`choice of the lowerof the two nearest quantization levels, or
`“truncating”. In the MPEG2 reference coder, an attempt is
`made to compromise between the nominal reduction in error
`whichis the attribute of rounding and the tendency toward
`bit rate efficiency which is associated with truncating, by
`setting a standard value for \ of X=0.75.
`Whilst particular attention has here been paid to MPELG2
`coding, similar considerations apply to other methods of
`compression encoding of a digital signal, which including
`the steps of conducting a transformation process to generate
`values and quantising the values through partitioning the
`amplitude range of a value into a set of a adjacent intervals,
`wherebyeach interval is mapped onto a respective one of a
`set of representation levels which are to be variable length
`
`10
`
`15
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`coded, such that a bound of cach interval is controlled by a
`parameter >. The transformation process may take a large
`variety of forms, including block-based transforms such as
`the DCT of MPEG2, and sub-band coding.
`SUMMARY OF THE INVENTION
`
`It is an object of one aspect of the present invention to
`provide an improvement in such a method which enables
`higher quality to be achievedat a given bitrate or a reduction
`in bitrate for a given level of quality.
`Accordingly, the present invention is in one aspect char-
`acterised in that ) is controlled so as to vary dynamically the
`bound of each interval with respect to the associated repre-
`sentation level.
`
`Suitably, wherein each value is arithmetically combined
`with i.
`
`Advantagcously, } is:
`a function of the quantity represented by the value;
`where the transformation is a DCT, a function of hori-
`zontal and vertical frequency;
`a function of the quantisation step size; or
`a function of the amplitude of the value.
`In a particular form of the present invention, the digital
`signal to be encoded has been subjected to previous encod-
`ing and decoding processes and %is controlled as a function
`of a parameter in said previous encoding and decoding
`processes.
`In a further aspect, the present invention consists in a (q,
`2) quantiser operating on a set of transform coefficients x,
`representative of respective frequency indices f, in which A
`is dynamically controlled in dependence upon the values of
`x, and f,.
`Advantageously, 4 is dynamically controlled to minimise
`acost function D+4#H where D is a measure ofthe distortion
`introduced by the quantisation in the uncompressed domain
`and H is a measure of compressed bitrate.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The invention will now be described by way of example
`with reference to the accompanying drawings, in which:
`FIG. 1 is a diagram illustrating the relationships between
`representation levels, decision levels and the value of 5
`FIG. 2 is a block diagram representation of the quantiza-
`tion process in the MPEG2 reference coder;
`FIG. 3 is a block diagram representation of a simplified
`and improved quantization process;
`FIG. 4 is a block diagram representation of the core
`elements of FIG. 3;
`TIG. 5 is a block diagram representation of a quantization
`process according to one aspect of the present invention; and
`FIG. 6 is a block diagram representation of a quantization
`process according to a further aspect of the present inven-
`tion.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`In the specifically mentioned compression standards, the
`original amplitude x results from a discrete cosine transform
`(DCT) andis thus related to a horizontal frequency index
`f,, and a vertical frequency index f,... Whilst this approach
`is taken as an example in what follows, the invention is not
`restricted in this regard.
`In general, a quantiser describes a mapping from an
`r
`original amplitude x of frequencies [,,, and [,.,. onto an
`
`IPR2022-01227
`IPR2022-01227
`EXHIBIT 1022 - PAGE 0005
`EXHIBIT 1022 - PAGE 0005
`
`
`
`US 6,668,088 B1
`
`3
`amplitude y=Q(x). The mapping performed by the quantiser
`is fully determined by the set of representation levels {r,}
`and by the corresponding decision levels {d,} as illustrated
`in FIG. 1. All original amplitudes in the range d;=x<dy,1)
`are mappedonto the samerepresentation level y=Q(x)=r1;. AS
`can be seen from FIG. 1, consecutive decision levels are
`related by the quantisation step size q: and for a given
`representation level r,, the corresponding decision level is
`
`Ays=atg
`
`calculated as:
`
`A
`dan-5-4
`
`()
`
`10
`
`A
`(2)
`
`15
`
`The quantiser is fully specified by the quantisation step-
`size q and the parameter i for a given set of representation
`levels {r,}. Therefore, a quantiser that complies with equa-
`tions (1) and (2) can be referred to as a (q,A) quantiser.
`Currently proposed quantisers, as described in the refer-
`ence coders for the II.261, 11.263, MPEG-1 and MPEG-2
`standards, all apply a special type of (q, 4) quantiser in that
`a fixed value of % is used: for example 4=0.75 in the
`MPEG-2reference coder or A=1.0 in the MPEG-1 reference
`
`coder for quantisation of intra-DCT-coefficients.
`According to one aspect of this invention, 4 is not
`constant but is a function that depends on the horizontal
`frequency index f,., the vertical frequency index f,.,, the
`quantisation step-size q and the amplitude x:
`
`A=MEsore Euers G: X)
`
`(3)
`
`Examples of ways in which the function may usefully be
`derived to improve picture quality in video compression at
`a given bit-rate—orto reduce the requiredbit-rate at a given
`picture quality—will be set out below.
`The invention extends also to the case of transcoding
`whena first generation amplitude y,=Q,(x) is mapped onto
`a second generation amplitude y,=Q.(y,) to further reduce
`the bit-rate from the first to the second generation without
`having access to the original amplitude x. Inthis case, the
`first generation quantiser Q, and the second generation
`quantiser Q, are described as a (q,, A,)-type quantiser and
`a (qo, A5)-type quantiser, respectively. The second genera-
`tion , value is described as a function:
`
`ho=ho(fhor: fers Cir Ans Gos Aorep yi)
`
`4
`
`The parameter ,,.¢ that appears in Eqn. (4) is applied in
`a reference (q>, A,,.,)-type quantiser. This reference quan-
`tiser bypasses the first generation and directly maps an
`original amplitude x onto a second generation reference
`amplitude y,,.=QsAX).
`The functional relationship of Eqn. (4) can be used to
`minimise the error (y—Y>,,,) or the error (y,—x). In thefirst
`case, the resulting second generation quantiser may becalled
`a maximum a-posteriori (MAP) quantiser. In the second
`case, the resulting second generation quantiser may be called
`a mean squared error (MSE) quantiser. Examples of the
`second generation (q3, A»yap)-type and (qp, A.agse)-type
`quantisers are given below. lor a more detailed explanation
`of the theoretical background, reference is directed to the
`paper “Transcoding of MPEG-2 intra frames”’—Oliver
`Werner—IEEE Transactions on Image Processing 1998,
`which will for ease of reference be referred to hereafter as
`
`“the Paper’. A copy of the Paper is appended to British
`patent application No. 9703831 from which the present
`application claims priority.
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`The present invention refers specifically to quantization of
`‘intra’ DCT coefficients in MPEG2video coding but can be
`applied to non-intra coefficients, to other video compression
`schemes and to compression of signals other than video. In
`MPEG2?,the prior art is provided by what is knownas Test
`Model 5 (TMS5). The quantization scheme of TMS5 for
`positive intra coefficients is illustrated in FIG. 2.
`In order to simplify the description, the above diagram
`will be replaced by FIG. 3, which illustrates essentially the
`same quantizer except for small values of gq, where it
`corrects an anomalyas described in the Paper.
`In this quantizer,
`the incoming coefficients are first
`divided by quantizer weighting matrix values, W, which
`depend on the coefficient frequency but which are fixed
`across the picture, and then by a quantizer scale value q
`which can vary from one macroblock to the next but which
`is the sameforall coefficient frequencies. Prior to the adder,
`the equivalent inverse quantizer reconstruction levels are
`simply the integers 0, 1,2 ....A fixed number2/2,is then
`added to the value and the result truncated. The significance
`of 2X is that a value of 0 makes the quantizer (of the value
`input to the adder) a simple truncation, while a value of 1
`makesit a rounding operation. In TMS, the value of >’ is
`fixed at 0.75.
`
`Attention will hereafter be focused on the operation of the
`‘core’ quantizer shownin FIG.4.
`In a class of MPEG-2 compatible quantisers for, intra
`frame coding, non-negative original dct-coefficients x (or
`the same coefficients after division by weighting matrix
`values W) are mapped onto the representation levels as:
`
`y=oo=|=+5)-4
`
`©)
`
`The floor function| a| extracts the integer partof the given
`argumenta.
`Negative values are mirrored:
`y=-Oh)
`
`(6)
`
`The amplitude range of the quantisation step-size q in eq.
`(1) is standardised; q has to be transmitted as side informa-
`tion in every MPEG-2 bit stream. This does not hold for the
`parameter 4 in eq. (1). This parameter is not needed for
`reconstructing the det-coefficients from the bit stream, and is
`therefore not transmitted. However, the -value controls the
`mapping of the original dct-coefficients x onto the given set
`of representation levels
`nal
`
`1)
`
`Accordingto eq. (1), the (positive) x-axis is partitioned by
`the decision levels
`
`d=(I-5)-g 121.2...
`
`(8)
`
`Each x e[d,d,,,) is mapped onto the representation level
`y=r,. As a special case, the interval [0, d,) is mapped onto
`y=0.
`The parameter > can be adjusted for each quantisation
`step-size q, resulting in a distortion rate optimised quanti-
`sation: the mean-squared-error
`D=E(x-y)"]
`
`2)
`
`is minimised under a bit rate constraint imposed on the
`coefficients y. In order to simplify the analysis, the first order
`source enlropy
`
`IPR2022-01227
`IPR2022-01227
`EXHIBIT 1022 - PAGE 0006
`EXHIBIT 1022 - PAGE 0006
`
`
`
`H=3-P,, log, P;
`
`(10)
`
`and further from eq. (16)
`
`US 6,668,088 B1
`
`of the coefficients y instead of the MPEG-2 codeword table
`is taken to calculate the bit rate. It has been verified in the
`
`Paper that the entropy H can be used to derive a reliable
`estimate for the numberofbits that result from the MPEG-2
`
`codeword table. In Eqn. (10), P, denotes the probability for
`the occurrence of the coefficient y=r,.
`The above constrained minimisation problem can be
`solved by applying the Lagrange multiplier method, intro-
`ducing the Lagrange multiplier «. One then gets the basic
`equation to calculate the quantisation parameter A:
`
`oH
`aD
`bye al
`se
`aa tH ay
`=O
`
`(11)
`
`15
`
`Note, that the solution for % that one obtains from Eqn.
`(11) dependsonthe value of wv. The value of x is determined
`by the bit rate constraint.
`
`HEH,
`
`(12)
`
`where Hy specifies the maximum allowedbit rate for encod-
`tog the coefficients y. In general, the amplitude range of the
`Lagrange multiplier is 0<je<o0. In the special case of Hp,
`one obtains “0. Conversely for H,—0, one obtains in
`general n>.
`The Laplacian probability density function (pdf) is an
`appropriate model for describing the statistical distribution
`of the amplitudes of the original dcet-coefficients. This model
`is now applicd to cvaluate analytically Eqn. (11). One then
`obtains a distortion-rate optimised quantiser characteristic
`by inserting the resulting value for % in eq. (5).
`Due to the symmetric quantiser characteristic for positive
`and negative amplitudes in Eqns. (5) and (6), we introduce
`a pdfp for describing thedistribution ofthe absolute original
`amplitudes|x|. The probability P, for the occurrence ofthe
`coefficient y=0 can then be specified as
`
`he
`
`Po= f
`0)
`
`p(xy)dx
`
`(13)
`
`Similarly, the probability P, for the coefficient |y| becomes
`
`Pr=
`
`ti-h}a
`q
`2
`(-3}.
`
`p(x)dx (=1,2,...
`
`(14)
`
`30
`
`35
`
`40
`
`45
`
`50
`
`With Eqns. (13) and (14), the partial derivative of the
`entropy H of eq. (10) can be written after a straightforward
`calculation as
`
`55
`
`a -3. » p14) 4): lows
`0
`
`From eq. (9) one can first deduce
`
`D=
`
`Lye
`f x +p(x) xt)!bl
`
`d.
`
`fe
`
`“OH Lg) «pdx
`
`(15)
`
`(16)
`
`60
`
`65
`
`Fee eed alter 3)
`f=0
`
`It can be seen from eq. (17) that
`
`10
`
`>Uif 0<sAsl
`
`Oa
`
`a7)
`
`(18)
`
`Thus, when A is increased from zero to one, the resulting
`distortion D is monotonically decreasing until the minimum
`value is reached for A=1. The latter is the solution to the
`unconstrained minimisation of the mean-squared-error,
`however, the resulting entropy H will in general not fulfil the
`bit rate constraint of eq. (12).
`Under the assumption of P;=P,,, in eq. (15), we see that
`dH/di20. Thus, there is a monotonic behaviour: when X is
`increased from zero to one, the resulting distortion D mono-
`tonically decreases, at the same time the resulting entropy H
`monotonically increases.
`Immediately, an iterative algo-
`rithm can be derived from this monotonic behaviour. The
`parameterA is initially set to A=1, and the resulting entropy
`H is computed. If H is larger than the target bit rate Ho, the
`value of 2. is decreased in further iteration steps until the bit
`rate constraint, eq. (12) is fulfilled. While this iterative
`procedure forms the basis of a simplified distortion-rate
`method proposedfor transcoding of I-frames, we continue to
`derive an analytical solution for i.
`Eqns. (15) and (17) can be evaluated for the Laplacian
`model:
`
`p(x) = B-a-eif xed =(1-4)-9
`
`(19)
`
`After inserting the model pdf of Eqn. (19) in Eqns. (15)
`and (17), it can be shownthat the basic equation (11) leads
`then to the analytical solution for A,
`
`A= 1-4. [ata + 1 -2)-logs(; Pall
`
`with z=e"*? and the ‘z’-entropy
`h(z)=-z.logyz—(1-z). log(1-z)
`
`(20)
`
`(21)
`
`Eqn. (20) provides only an implicit solution for i, as the
`probability P, on the right hand side depends on A according
`to eq. (13). In general, the value of Py can be determined
`only for known i by applying the quantiser characteristic of
`Eqns. (5) and (6) and counting therelative frequency of the
`event y=0. However, eq. (20) is a fixed-point equation for 4
`which becomes more obvious if the right hand side is
`described by the function
`
`ga 1- 5. [i+ -9- toes=]
`
`(22)
`
`resulting in the classical fixed-point form A=g(A). Thus, it
`follows from the fixed point theorem of Stefan Banach that
`the solution for 4 can be found by an iterative procedure
`with
`
`Anta)
`in the (j+1)-th iteration step. The iteration of (23) converges
`towards the solution for an arbitrary initial value A) if the
`
`(23)
`
`IPR2022-01227
`IPR2022-01227
`EXHIBIT 1022 - PAGE 0007
`EXHIBIT 1022 - PAGE 0007
`
`
`
`US 6,668,088 B1
`
`7
`i.c. Lipschitz-continuous
`function g is ‘sclf-contracting’,
`with a Lipschitz-constant smaller than one. As an applica-
`tion of the mean theorem for the differential calculus, it is
`notdifficult to prove that g is always‘self-contracting’ if the
`absolute value of the partial derivative is less than one. This
`yields the convergence condition
` 1 ag
`
`_
`@
`ra
`_ oa
`l> Ise
`—z) Po
`rind qg
`
`(24)
`
`Adistortion-rate optimised quantisation method will now
`be derived based on the results obtained above. As an
`
`
`
`example, a technique is outlined for quantising the
`AC-coefficients of MPEG-2 intra frames. It is straightfor-
`ward to modify this technique for quantising the det-
`coefficients of MPEG-2 inter frames, i.e. P- and B-frames.
`Firstly, one has to take into account
`that
`the 63
`AC-coefficients of an 8x8 dct-block do not share the same
`distribution.
`‘Thus, an individual Laplacian model pdt
`according to eq. (19) with parameter a, is assigned to each
`AC-frequency index 1. This results in an individual quantiser
`characteristic according to Eqns. (5) and (6) with parameter
`i,. Furthermore, the quantisation step-size q; depends on the
`visual weight w, and a frequency-independent qscale param-
`eter as
`
`8
`Where 4’ is now an a priori constant linking distortion to bit
`Tale.
`
`A theoretical argument based on coding white noise gives
`a law of 6 dB per bit per coefficient. In practice, observation
`of actual coding results at different bit rates gives a law of
`k dB per bit, where k takes values from about 5 to about 8
`depending on the overall bit rate. In practice, the intuitive ‘6
`dB’ law corresponds well with observation.
`Additionally, the qscale parameter can be changed to meet
`the bit rate constraint of Eqn. (25). In principle, the visual
`weights w, offer another degree of freedom but for simplicity
`we assume a fixed weighting matrix as in the MPEG-2
`reference decoder. This results in the following distortion
`rate optimised quantisation technique which can be stated in
`a ‘C’-language-like form:
`
`10
`
`15
`
`/* Begin of quantising the AC-coefficients in MPEG-2 intra frames*/
`min = 5
`for (qscale = qmin; qscale =
`/* linear qscale table*/
`
`qmax; qscale = qscale + 2)
`
`h=0;
`do {
`
`Step 1: determine Ay, Aj,... , Ags by minimising D + zw: H;
`Step 2: calculate H = 2 H,(A,);
`= + 8, /*8 to be selected appropriately*/
`}while (H > H,);
`Step 3: calculate D =c- =D, (A,
`if (D < Daiw{
`gscalegn = qscale;
`for @ = 1; i S 63;i=i+4+ 1)Aiopr = Ag
`Dain = D;}
`
`for G@= 1,1 S$ 63;isi+1)
`
`35
`
`{
`
`Wi -qscaleyy
`Giopt =6
`
`w; -gscale
`16
`
`gi =
`
`(25)
`
`30
`
`the quantisation results in a
`For a given step-size q,,
`distortion D,Q,) and a bit rate H(4,) for the AC-coefficients
`of the same frequency index 1. As the det is an orthogonal
`transform, and as the distortion is measured by the mean-
`squared-error,
`the resulting distortion D in the spatial
`(sample/pixel) domain can be written as
`
`D= ce)! D;(A;)
`
`(26)
`
`40
`
`with some positive normalising constant c. Alternatively the
`distortion can measured in the weighted coefficient domain
`in order to compensate for the variation in the human visual
`response at different spatial frequencies.
`Similarly, the total bit rate H becomes
`
`=)" AA)
`
`@7)
`
`45
`
`50
`
`For a distortion rate optimised quantisation, the 63 param-
`eters A, have to be adjusted such that the cost function
`
`DiuH
`
`(28)
`
`55
`
`is minimised. The non-negative Lagrange multiplier u is
`determined by the bit rate constraint
`
`HEH
`
`(29)
`
`60
`
`Alternatively, if the distortion is expressed in the logarithmic
`domainas:
`
`D'=20 logy, D dB
`
`The cost function to be minimised becomes:
`
`B=D1NH
`
`(28a)
`
`65
`
`(28b)
`
`y=Q(0) -|
`
`
`Isl
`Ay
`i,opt
`
`
`
`+ |ope“ SEN)
`
`quantise all AC-coefficients of frequency-index i by
`
`/*End of quantising the AC-coefficients in MPEG-2 intra frames*/
`
`There are several options for performing Step 1-Step 3:
`1. Options for performing Step 1
`The parameters ),, 25, .. . Ags can be determined
`a) analytically by applying Eqns. (20)-(23) of Section 3.
`b) iteratively by dynamic programming of D+w-II, where
`either of the options described in the next points can be
`used to calculate D and H.
`2. Options for performing Step 2
`H=xH{A,) can be calculated
`a) by applying the Laplacian modelpdf, resulting in
`
`A(z)
`1-Z"
`
`H = )) A(Pos) += Pog):
`
`(32)
`
`where h(P,,) and h(Z;) are the entropies as defined in
`eq. (21) of Po; (eq. (13)) and Z,=e"%;7,, respectively.
`Note that P,, in Eqn.
`(32) can be determined by
`counting for each det-frequency index i the relative
`frequency of the zero-amplitude y=Q,(x)=0.
`Interestingly, eq. (32) shows that
`the impact of the
`quantisation parameters 2, on the resulting bit rate H
`only consists in controlling the zero-amplitude prob-
`abilities P,;.
`
`IPR2022-01227
`IPR2022-01227
`EXHIBIT 1022 - PAGE 0008
`EXHIBIT 1022 - PAGE 0008
`
`
`
`US 6,668,088 B1
`
`9
`b) from a histogram ofthe original dct-cocfficicnts,result-
`ing with Eqns. (10), (13) and (14) in
`
`H= -») » Pij ‘logPii
`i
`£
`
`(33)
`
`10
`
`Pei
`Kt
`q
`wel)
`A(x) = Ay = 1 - = - log, — ],
`
`G9)
`
`c) by applying the MPEG-2 codewordtable
`3. Options for performing Step 3
`D=c-XD, (A,) can be calculated
`a) by applying the Laplacian model pdf of Eqn. (19) and
`evaluating Egn. (16).
`b) by calculating D=E[(x-y)’] directly from a histogram
`of the original dct-coefficients x.
`Depending on which options are chosen for Step 1-Step
`3, the proposed method results in a single pass encoding
`schemeif the Laplacian model pdf is chosen or in a multi
`pass scheme if the MPEG-2 codeword table is chosen.
`Furthermore, the method can be applied on a frame, mac-
`roblock or on a 8x8-block basis, and the options can be
`chosen appropriately. The latter is of particular interest for
`any rate control schemethatsets the target bit rate Hy either
`locally on a macroblock basis or globally on a frame basis.
`Furthermore, we note that the proposed method skips >
`automatically high-frequency dct-coefficients if this is the
`best option in the rate-distortion sense. This is indicated if
`the final quantisation parameter2,,, has a valuc close to
`one for low-frequency indices i but a small value, e.g. zero,
`for high-frequency indices.
`A distortion-rate optimised quantisation method for
`MPEG-2 compatible coding has been described, with sev-
`eral options for an implementation. The invention can imme-
`diately be applied to standalone(first generation) coding. In
`particular, the results help designing a sophisticated rate
`contro] scheme.
`The quantiser characteristic of eqs. (5) and (6) can be
`generalised to
`
`10
`
`15
`
`5,
`
`30
`
`35
`
`d=1,...,L)
`Similar to eqs. (13), (14), the probabilities in eq. (39)
`depend on the lambda parameters,
`
`veer
`
`Pyo= f
`0
`
`p(x) dx and
`
`A
`P hay
`y=
`nL,(34
`
`p(xydx l=1
`
`(40)
`
`41
`a)
`
`Therefore, eq. (39) represents a system of non-linear
`equations for determining the lambda parameters A,,...,A;.
`In general, this system can only be solved numerically.
`However, eq. (39) can be simplified if the term log,(P,.
`1/P,) is interpreted as the difference
`
`=
`Joe,( 2!
`Nnha= 10m,—5*)
`
`of optimum codeword lengths
`
`I=-log,P, T1=—logsP1
`
`(42)
`
`(43)
`
`associated with the representation levels r,, 11.
`A practical implementation of the above will now be
`described.
`Once the probability distribution, parametric or actual, of
`the unquantized coefficients is known,
`il
`is possible to
`choose a set of quantizer decision levels that will minimise
`the cost function B, because both the entropy H and the
`distortion D are knownas functions ofthe decision levels for
`
`a given probability distribution. This minimization can be
`performedoff-line and the calculated sets of decision levels
`
`40
`G4)
`SA|M9) yp
`stored for each of a set of probability distributions.
`ysamera+|—+5
`In general, it will be seen that the optimum value of 4
`corresponding to each decisionlevelis different for different
`coefficient amplitudes. In practice, it appears that the great-
`est variation in the optimum value of > with amplitude is
`apparent between the innermost quantizer level (the one
`whosereconstructionlevel is 0) andall the other levels. This
`meansthat it may be sufficient in some cases to calculate, for
`each coefficient
`index and for each value (suitably
`quantized) of the probability distribution parameter,
`two
`values of i, one for the innermost quantizer level and one for
`all the others.
`A practical approach following the above description is
`shown in FIG. 5.
`
`for non-negative amplitudes x. The floor-function | a] in eq.
`(34) returns the integer part of the argument a. Negative
`amplitudes are mirrored,
`
`45
`
`y=-O(x)
`
`(35)
`
`The generalisation is reflected by the amplitude dependent
`values A(x), q(x), r(x) in eq.
`(34). For a given set of
`representation levels .
`.
`. <r,4<I<t),4< ... and a given
`amplitude x, the pair of consecutive representation levels is
`selected that fulfils
`
`PySx<ry
`
`(36)
`
`The value of the local representation level is then set to
`
`r(x)=ty4
`
`(37)
`
`60
`
`The value of the local quantisation step-size results from
`
`I)=htris
`
`(38)
`
`Astraightforward extension of the rate-distortion concept
`detailed above yields for the local lambda parameter, very
`similar to eq. (20).
`
`The DCT coefficients are taken to a linear quantizer 52
`providing the input to a histogram building unit 54. The
`histogram is thus based on linearly quantized versionsof the
`inpul DCT coeflicients. The level spacing of that linear
`quantizer 52 is notcritical but should probably be about the
`same as the average value of q. The extent of the histogram
`function required depends on the complexity of the para-
`metric representation of the pdf; in the case of a Laplacian
`or Gaussian distribution it maybe sufficient to calculate the
`mean or variance of the cocfficicnts, while in the ‘zcro
`excluded’ Laplacian used in the Paper it is sufficient
`to
`calculate the mean and the proportion of zero values. This
`histogram, which maybe built up over a picture period or
`longer, is used in block 56 as the basis of an estimate of the
`
`IPR2022-01227
`IPR2022-01227
`EXHIBIT 1022 - PAGE 0009
`EXHIBIT 1022 - PAGE 0009
`
`
`
`US 6,668,088 B1
`
`11
`pdf parameter or parameters, providing onc of the inputs to
`the calculation of % in block 58.
`Another input to the calculation of d is from a set of
`comparators 60 which are in effect a coarse quantizer,
`determining in which range of values the coefficient to be
`quantized falls. In the most likely case described above, it is
`sufficient to compare the value with the innermost non-zero
`reconstruction level. The final input required to calculate
`is the quantizer scale.
`In general, an analytical equation for % cannot be
`obtained. Instead, a set of values can be calculated numeri-
`cally for various combinations of pdf parameters, compara-
`tor outputs and quantizer scale values, and the results stored
`ina lookup table. Such a table need not be very large (it may,
`for example, contain fewer than 1000 values) because the
`optima are not very sharp.
`The value of
`calculated is then divided by 2 and added
`in adder 62 to the coefficient prior to the final truncation
`operation in block 64.
`Instead of using variable codewordlengths that depend on
`the current probabilities according to eq. (43), a fixed table
`of variable codeword lengths C,, ... , C, can be applied to
`simplify the process. The values of C,,..., C, can be
`determined in advance by designing a single variable length
`code, ie. a Huffman code, for a set of training signals and bit
`rates. In principle, they can also be obtained dircetly from ,
`the MPEG2 variable-length code table. The only complica-
`tion is the fact that MPEG2 variable-length coding is based
`on combinations of runs of zero coefficients termina