Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 1 of 22 PageID #: 157
`Case 1:17-cv—01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 1 of 22 PageID #: 157
`
`
`
`
`
`
`
`
`EXHIBIT B
`EXHIBIT B
`
`
`
`
`
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 2 of 22 PageID #: 158
`I IIIII IIIIIIII Ill lllll lllll lllll lllll lllll lllll lllll lllll 111111111111111111
`US008634462B2
`
`c12) United States Patent
`N arroschke et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,634,462 B2
`Jan.21,2014
`
`(54) QUANTIZATION FOR HYBRID VIDEO
`CODING
`
`2006/0233239 Al
`2007/0133891 Al
`2010/0220784 Al
`
`10/2006 Sethi et al.
`6/2007 Jeong
`9/2010 Tanimoto et al.
`
`(76)
`
`Inventors: Matthias Narroschke, Schaafheim
`(DE); Hans-Georg Musmann, Salzgitter
`(DE)
`
`( *) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 627 days.
`
`(21) Appl. No.:
`
`12/531,025
`
`(22) PCT Filed:
`
`Mar. 10, 2008
`
`(86) PCT No.:
`
`PCT /EP2008/052824
`
`§ 371 (c)(l),
`(2), ( 4) Date: Mar. 5, 2010
`
`(87) PCT Pub. No.: W02008/110535
`
`PCT Pub. Date: Sep. 18, 2008
`
`(65)
`
`Prior Publication Data
`
`US 2010/0189180Al
`
`Jul. 29, 2010
`
`(51)
`
`Int. Cl.
`H04N7/18
`(52) U.S. Cl.
`............ 375/240.04; 375/240.25; 375/240.26;
`USPC
`375/240.24
`
`(2006.01)
`
`( 58) Field of Classification Search
`USPC
`........................................ 375/240.01-240.29
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,691,770 A
`7,203,374 B2
`7,929,776 B2 *
`2002/0114392 Al
`2006/0098733 Al
`
`11/1997 Keesman et al.
`4/2007 Hatabu .......................... 382/248
`4/2011 Sethi et al. .................... 382/232
`8/2002 Sekiguchi et al. ....... 375/240.15
`5/2006 Matsumura et al.
`
`FOREIGN PATENT DOCUMENTS
`
`WO
`WO
`
`96/34495
`2007079964 Al
`
`10/1996
`7 /2007
`
`OTHER PUBLICATIONS
`
`Lim et al., "Text Description of Joint Model Reference Encoding
`Methods and Decoding Concealment Methods," Study of ISO/IEC
`14496-10 and ISO/IEC 14496-5/AMD6, Mar. 2004, pp. 2-45.
`Narroschke, "Adaptive coding of the prediction error for H.264/
`AVC," Institut fiir Informationsverarbeitung Universitiit Hannover,
`Dec. 2, 2005, 15 pages.
`Narroschke et al., "Adaptive prediction error coding in spatial and
`frequency domain for H.264/ AVC" ITU-Telecommunications
`Standardization Sector Study Group 16 Question 6 Video Coding
`Experts Group (VCEG), 29th Meeting, Bangkok, Thailand, Jan.
`16-20, 2006, 14 pages.
`
`(Continued)
`
`Primary Examiner - Andy Rao
`(74) Attorney, Agent, or Firm - Robert Iannucci; Seed IP
`Law Group PLLC
`
`ABSTRACT
`(57)
`Method for coding a video signal using hybrid coding, com(cid:173)
`prising: reducing temporal redundancy by block based
`motion compensated prediction in order to establish a predic(cid:173)
`tion error signal; performing quantization on samples of the
`prediction error signal or on coefficients resulting from a
`transformation of the prediction error signal into the fre(cid:173)
`quency domain to obtain quantized values, representing
`quantized samples or quantized coefficients respectively; cal(cid:173)
`culating a quantization efficiency for the quantized values;
`calculating a zero efficiency for a quantization, when the
`quantized values are set to zero; selecting the higher effi(cid:173)
`ciency; and maintaining the quantized values or setting quan(cid:173)
`tized values to zero, for further proceeding, depending on the
`selected efficiency.
`
`14 Claims, 8 Drawing Sheets
`
`c'k. ,J
`4
`3
`2
`1
`
`-1
`-2
`-3
`-4
`
`-311
`
`211
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 3 of 22 PageID #: 159
`
`US 8,634,462 B2
`Page 2
`
`(56)
`
`References Cited
`
`OTHER PUBLICATIONS
`Narroschke, "Adaptive prediction error coding in the spatial and
`frequency domain
`in the KTA reference model" International
`Organisation for Standardisation, Montreux, CH, Apr. 2006, 16
`pages.
`Narroschke, "Extending the prediction error coder ofH.264/ AVC by
`a vector quantizer" Proceedings of the SPIE, SPIE, Bellingham, WA
`5960: Jul. 2005, 12 pages.
`
`Ostermann et al., "Video coding with H.264/AVC: Tools, Perfor(cid:173)
`mance, and Complexity" IEEE Circuits and Systems Magazine 4( 1 ):
`7-28, 2004.
`International Search Report, mailed Aug. 13, 2008, for PCT/EP2008/
`052824, 4 pages.
`Written Opinion, mailed Aug. 13, 2008, for PCT/EP2008/052824, 8
`pages.
`
`* cited by examiner
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 4 of 22 PageID #: 160
`
`U.S. Patent
`
`Jan.21,2014
`
`Sheet 1 of 8
`
`US 8,634,462 B2
`
`-3 Ll
`
`-2 Ll .....-----=-~=...
`
`2~
`
`4
`3
`2
`1
`
`-1
`-2
`-3
`-4
`
`Fig.1
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 5 of 22 PageID #: 161
`
`U.S. Patent
`
`Jan.21,2014
`
`Sheet 2 of 8
`
`US 8,634,462 B2
`
`0
`N
`
`0
`'r'"
`
`co
`
`Fig.2
`
`N
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 6 of 22 PageID #: 162
`
`U.S. Patent
`
`Jan.21,2014
`
`Sheet 3 of 8
`
`US 8,634,462 B2
`
`Samples of error
`prediction signal
`
`302
`
`Macroblock
`in subblocks
`
`301:t
`
`Samples
`
`Transform l~to 306
`freq. domrnn
`
`Coefficients
`
`Quant.
`
`308
`
`Eval. Effl.
`
`310
`
`Yes
`
`Quant Val. 314
`=0
`
`No
`
`316
`
`Eval. overoll eff. 318
`
`Yes Quant. Val. 322
`=0
`
`Fig. 3
`
`Opt.Quant. Val. for encoder
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 7 of 22 PageID #: 163
`
`U.S. Patent
`
`Jan.21,2014
`
`Sheet 4 of 8
`
`US 8,634,462 B2
`
`.
`
`.
`
`. . . . .
`
`r--
`
`T'"
`T'"
`
`....
`Q)
`"O
`0
`(.)
`"O
`
`.§ c
`"E .Q
`ct! (/)
`"O c::
`c Q) E><
`~w
`
`("')
`0 ,-
`
`N
`0 ..-
`
`.
`.
`
`I•""••••••"•••
`
`I
`
`e • •
`
`• •
`
`• •
`
`• • •
`
`• ••
`
`• e IO••••••••••••••••"•••••••••"'•••••••••••••
`
`•
`
`•
`
`••••••••
`
`••••••••••••••••"'••••••••••••••,
`
`. .
`. .
`. : ... .,:
`: ..... ~ ~ ~--·
`......
`·--..: . &. •••
`
`•....
`o
`I
`
`·'
`i
`
`I
`I
`
`LO .....
`..... .
`' I
`, .. -... -..
`'
`
`....
`/ ............. .
`.............................
`......
`
`N
`
`•
`A
`
`·~
`
`I
`
`I
`
`I . I . . . .
`N• :;: :--·········-IIM
`.......... ,.:
`:N
`'
`. .
`:~
`.......
`.
`~--··· ... .
`I . . I .
`,..-, .. . . . . I ••••
`. .
`. co
`. 0 .....
`.
`. .
`. . (!)
`. 0 ,-
`.
`Li"): o: .... :
`
`0
`N
`
`~-••
`
`'O)• :o:
`
`I'-
`0 ,-
`
`....
`
`......
`
`.....
`0 .....
`
`Fig.4
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 8 of 22 PageID #: 164
`
`U.S. Patent
`
`Jan.21,2014
`
`Sheet 5 of 8
`
`US 8,634,462 B2
`
`0 ...-
`N
`
`CJ')
`0
`N
`
`.
`.
`.
`.
`.
`.
`...............................................................
`.
`.
`.
`.
`.
`.
`+-------~
`N
`..-
`. . ...................................
`N ·····-~---····· ... ················· ...................................... .
`.
`.
`
`co:
`
`o: N: . .
`r,..:
`o:
`IN: .
`
`-.:l"
`0
`N
`
`<O
`0
`N
`
`M
`0
`N
`
`CJ: •
`
`,..._
`Q) c:
`"C O
`0
`·-
`(.)
`(/)
`Q) c:
`"C Cl)
`"C x
`~ Cl)
`·-
`"'C
`.... (/)
`"C Q)
`ttl O
`"C Q.
`c: 0
`ttl
`,.._
`....
`ci5 c.
`
`t :
`
`,· -.. •,
`.
`..... ..;Lt'):
`:
`: 0 ~---······
`:
`.............. ~ :
`•NI
`.
`............ - ........... -,-_J .....
`
`• :
`
`I
`
`D
`
`.....
`0
`N
`
`Fig.5
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 9 of 22 PageID #: 165
`
`U.S. Patent
`
`Jan.21,2014
`
`Sheet 6 of 8
`
`US 8,634,462 B2
`
`2-··· ·--~
`.,,'
`
`Q ••.••• JJ
`,,·"'
`., .. "
`
`. .i'J
`j1,.. .. ·· ,:,.-_ .... o· ___
`e:::'. ---<,···· cf· .... o
`
`.............. 2, 1,0,-1,o,o,o,o,9,o,o,o,o,o,o,o
`
`Fig.6
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 10 of 22 PageID #: 166
`
`U.S. Patent
`
`Jan.21,2014
`
`Sheet 7 of 8
`
`US 8,634,462 B2
`
`0-·· ···O··· ····O··· ··-0
`
`. .
`@··· ···-O··· ···-0··· ···O
`
`s-.--· ···1s·- ··ta
`·.
`.
`·.
`:
`·.,
`:
`J2-· ····2-··· .. :~5 io
`
`0-· ---0··· ····0··· ···0
`
`0··· ···-O··· ····O··· ···6
`~\· ···O···· ... 1
`:
`....
`0··· ···O··· .'::-o 3
`
`(a)
`
`..,_ 3,1,0,-1,0,0,0,0,0,0,0,0,0,0,0,0
`
`(b)
`
`Fig.?
`
`a
`:4
`
`a
`
`a
`
`.. : .. ~;-.
`• I •I
`I ..
`....,.! c :...... _..: c :..- .......: c !+-
`
`I
`
`I
`
`I
`
`I
`
`•
`
`I
`•
`
`I
`I
`
`f
`•
`
`I
`•
`
`b·a
`.. : ...
`•I
`
`.. : ..
`.
`. ~: ...
`a
`•;•
`• I • I • I •
`..
`:
`:
`:
`:
`__..; c :..._ ._..: c !...--_.: c :.-.
`
`a
`
`a
`
`.,..
`
`I ....
`
`I
`
`I
`
`I
`
`I
`
`0
`
`Fig.8
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 11 of 22 PageID #: 167
`
`U.S. Patent
`
`Jan.21,2014
`
`Sheet 8 of 8
`
`US 8,634,462 B2
`
`. ...
`: .
`\
`.
`: .
`.l.. ... :
`
`••o
`
`50
`
`60
`
`(a)
`
`(b)
`
`:
`
`8
`
`4
`
`:
`}
`:
`
`:
`~
`:
`
`J .......
`
`:
`j
`j
`i
`:
`...... ·· ...... 1 ...............
`
`1 ..............
`!.. . ...........
`20
`10
`
`30
`
`40
`
`r,
`
`Fig.9
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 12 of 22 PageID #: 168
`
`US 8,634,462 B2
`
`1
`QUANTIZATION FOR HYBRID VIDEO
`CODING
`
`FIELD OF THE INVENTION
`
`The invention relates to a method of coding, coder and
`decoder involving quantization for hybrid video coding and
`data signals.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`Up to date standardized video coding methods are based on
`hybrid coding. Hybrid coding provides a coding step in the
`time domain and a coding step in the spatial domain. First, the
`temporal redundancy of video signals is reduced by using a 15
`block based motion compensated prediction between the
`image block to be coded and a reference block from an image
`that has already been transmitted determined by a motion
`vector. The remaining prediction error samples are arranged
`in blocks and are transformed into the frequency domain 20
`resulting in a block of coefficients. These coefficients are
`quantized and scanned according to a fixed and well-known
`zigzag scanning scheme, which starts with the coefficient
`representing the DC value. According to a typical represen(cid:173)
`tation, this coefficient is positioned among the low frequency
`coefficients in the top left comer of a block. The zigzag
`
`2
`description of Joint Model Reference Encoding Methods and
`Decoding Concealment Methods", Joint Video Team (NT),
`doc. NT-K049, Munich, Germany, March 2004.
`In the case of an 8x8 transform the quantization is per(cid:173)
`formed in the official reference software as follows. For each
`of the four 8x8 prediction error blocks BJ (j=O, ...
`, 3) of a
`macro block the transform is performed resulting in a block of
`8x8 coefficients ckJ (k=O, ... , 63). Each coefficient is quan(cid:173)
`tized by a scalar quantizer as shown in FIG. 1. The quantized
`coefficients c'kJ (k=O, ... , 63, j=O, ... , 3) are scanned by the
`well known Zigzag scan starting at the DC-coefficient result(cid:173)
`ing in a one dimensional array of 64 quantized coefficients
`c'kJ·
`Subsequent to these coding steps, a second quantization
`step is performed in order to prevent that single quantized
`coefficients unequal to zero in an 8x8 block are coded. The
`coding of these single quantized coefficients unequal to zero
`may require a high data rate and may reduce the distortion
`only marginally. For this purpose, a value IkJ' characterizing
`the importance of the quantized coefficient, is associated to
`each of the 64 quantized coefficients. Three cases are distin(cid:173)
`guished. If a quantized coefficient has an absolute value of
`one, the value IkJ is dependent on the number NkJ of preced(cid:173)
`ing zero coefficients. The dependency between IkJ and NkJ is
`shown in the following table 1:
`
`TABLE 1
`
`0
`
`2
`
`4
`
`2
`
`2
`
`2
`
`7
`
`2
`
`9
`
`2
`
`2
`
`10 11 12
`
`13
`
`14 15
`
`2
`
`2
`
`16 17
`
`18
`
`19 20 21 22
`
`23
`
`24 25 26 27 28
`
`29
`
`30 31
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`45
`
`Accordingly, if a quantized coefficient has an absolute
`value of one and there are 3 or less preceding zero coeffi(cid:173)
`cients, the value characterizing the importance of the corre(cid:173)
`sponding quantized coefficient is set to 3. If there are 24 or
`more preceding zero coefficients the value characterizing the
`importance of the corresponding coefficient is set to 0.
`For each of the 64 quantized coefficients c'kJ' which has an
`absolute value larger than one, IkJ is set to a very large value
`such as 999999. For each of the 64 quantized coefficients c'kJ'
`50 which is zero, IkJ is set to zero. All 64 values IkJ are added
`resulting in the sum
`
`scanning produces a one-dimensional array of coefficients, 40
`which are entropy-coded by a subsequent coder. The coder is
`optimised for an array of coefficients with decreasing energy.
`Since the order of coefficients within a block is predetermined
`and fixed, the zigzag scanning produces an array of coeffi(cid:173)
`cients of decreasing energy, if the prediction error samples are
`correlated. The subsequent coding step may then be opti(cid:173)
`misedfor such a situation. For this purpose, the latest standard
`H.264/AVC proposes Context-Based Adaptive Binary Arith(cid:173)
`metic Coding (CABAC) or Context-Adaptive Variable(cid:173)
`Length Coding (CAVLC). However, the coding efficiency of
`the transform is only high, if the prediction error samples are
`correlated. For samples being only marginally correlated in
`the spatial domain, the transform is less efficient.
`The spatial redundancy may be reduced by blockwise 55
`transform coding of the resulting prediction error. For the
`purpose of transform coding, H.264/AVC applies an integer
`transform for coding a macroblock of 16x16 picture ele(cid:173)
`ments, which is similar to the Discrete Cosine Transform. The
`size of the transform can be changed for each macro block 60
`between 8x8 or 4x4 picture elements, signaled by side infor(cid:173)
`mation. In the first case, 4 8x8 transforms and in the second
`case, 16 4x4 transforms are applied for the macroblock.
`Dependent on the size of the applied transform different
`quantizations procedures are performed. Most of the encod-
`ing strategies that are applied in the official reference software
`are described in K.-P. Lim, G. Sullivan, T. Wiegand, "Text
`
`63
`
`11 = ~ Ik.J·
`
`k=O
`
`In the case that the sum IJ is smaller than the threshold 5, all
`quantized coefficients of the 8x8 block are set to zero and
`consequently IJ is also set to zero.
`After the determination of the values Ii, I2 , I3 , and I4 of the
`four 8x8 prediction error blocks 8 1 , 8 2 , 8 3 , andB 4 these four
`values are added resulting in the sum IMB for the whole Mac(cid:173)
`ro block. In the case that I MB is smaller than the threshold 6, all
`256 quantized coefficients of the Macroblock are set to zero.
`In case of an 4x4 transform the quantization is performed
`as follows. Each 8x8 predication error block BJ (j=O, ...
`, 3)
`
`65
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 13 of 22 PageID #: 169
`
`US 8,634,462 B2
`
`3
`into four 4x4 blocks P1,,
`is divided
`of a Macroblock
`(j=O, ... , 3, i=O, ... , 3). For each of the four 4x4 blocks, the
`transform is performed resulting in a block of 4x4 coefficients
`ck,i,, (k=O, ... , 15, j=O, ... , 3, i=O, ... 3). Each coefficient is
`quantized by a scalar quantizer as shown in FIG. 1. The
`quantized coefficients c'k,1,, of each of the four 4x4 blocks are
`zigzag scanned starting at the DC-coefficient resulting in a
`one dimensional array of 16 quantized coefficients c'k,1,,·
`Subsequent to these coding steps, a second quantization
`step is performed in order to prevent that single quantized
`coefficients unequal to zero in an 8x8 block are coded. In this
`second quantization step, all 64 quantized coefficients of the
`four 4x4 blocks of the 8x8 block are taken into account. For
`the quantization purpose, a value IkJ,i is associated to each of
`the 64 coefficients. Three cases are distinguished. If a quan(cid:173)
`tized coefficient has an absolute value of one, the value Ik,1,, is
`dependent on the number Nk,1,, of preceding zero coefficients.
`The dependency between Ik,1,, and Nk,1,, is shown in the fol(cid:173)
`lowing table 2:
`
`4
`error signal, performing a quantization on the prediction error
`signal or on coefficients resulting from a transformation of the
`prediction error signal into the frequency domain to obtain
`quantized values, representing quantized samples or quan(cid:173)
`tized coefficients respectively calculating a quantization effi(cid:173)
`ciency for the quantized values calculating a zero efficiency
`for a quantization, when the quantized values are set to zero,
`selecting the higher efficiency and maintaining the quantized
`values or setting the quantized values to zero, for further
`10 proceeding, depending on the selected efficiency.
`Accordingly, for reducing temporal redundancy a predic(cid:173)
`tion error signal is established by block based motion com(cid:173)
`pensated prediction. For the coding a quantization is fulfilled
`based on this prediction error signal to obtain quantized val-
`15 ues. This quantization can be performed directly on the pre(cid:173)
`diction error signal resulting in first quantized samples in the
`spatial domain. According to a further possibility the predic(cid:173)
`tion error signal is first transformed
`into the frequency
`domain, resulting in coefficients. Subsequently, the quantiza-
`
`TABLE2
`
`N
`
`7
`
`0
`
`0
`
`9
`
`0
`
`0
`
`10
`
`11
`
`12 13 14 15
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`2
`
`2
`
`2
`
`4
`
`For each of the 64 quantized coefficients c'k,1,,, which has an
`absolute value larger than one, Ik,1,, is set to a very large value
`such as 999999. For each of the 64 quantized coefficients
`c'k,1,,, which is zero, Ik,1,, is set to zero. All 64 values Ik,1,, are
`added for each 8x8 prediction error block B1 resulting in the
`sum
`
`In the case that the sum 11 is smaller than the threshold 5, all
`quantized coefficients of the 8x8 block are set to zero and
`consequently 11 is also set to zero.
`After the determination of the values Ii, 12 , 13 and 14 of the
`four 8x8 prediction error blocks Bi, 8 2 , 8 3 , and 8 4 , these four 45
`values are added resulting in the sum IMB for the whole mac-
`ro block. In the case that IMB is smaller than the threshold 6, all
`256 quantized coefficients of the macroblock are set to zero.
`Accordingly, in the case of an 8x8 transform as well as in
`the case of an 4x4 transform coefficients of prediction error
`blocks are quantized and a further quantization step is per(cid:173)
`formed in order to prevent that single quantized coefficients
`unequal to zero in a 8x8 block are coded. Therefore, rules are
`given for setting some coefficients to zero, which are consid(cid:173)
`ered to be of minor relevance, in order to significantly reduce
`the data rate while at the same time the distortion would only
`be increased marginally. However, this known procedure is
`unsatisfactory.
`
`tion is performed on these coefficients, resulting in quantized
`30 coefficients. In a further step, the result of this quantization
`should be enhanced. I.e. some values (samples or coeffi(cid:173)
`cients) should be set to zero before being coded. This is useful
`for samples or coefficients respectively, that require a high
`data rate but may reduce the distortion_only marginally.
`35 Therefore, a quantization efficiency for the quantization is
`calculated. I.e. a calculation is performed, taking into account
`the effort and the benefit of maintaining the quantized values.
`This quantization efficiency is compared with a zero effi(cid:173)
`ciency. The zero efficiency is calculated for the case, when the
`40 quantized values ( samples or coefficients respectively) are set
`to zero. I.e. comparing with a zero efficiency takes into
`account, that the effort for coding samples or coefficients
`might be small but on the other hand, there is also provided a
`disadvantage with respect to the quality of the coded signal.
`Subsequently, the quantization efficiency and the zero effi-
`ciency are compared to each other. Accordingly, if the effi(cid:173)
`ciency for maintaining the quantized values of the quantiza(cid:173)
`tion is better than the efficiency for setting all the quantized
`values to zero, than the quantized values are kept as they are.
`50 On the other hand, if the efficiency for setting the first quan(cid:173)
`tization values to zero is better, than the corresponding quan(cid:173)
`tized values are set to zero.
`Accordingly, to proper decide whether to set all quantized
`values (samples or coefficients) to zero or to keep them as
`55 they are an efficiency is calculated for both possibilities.
`Accordingly, the invention provides an optimization of the
`quantization of samples or coefficients respectively which
`always selects the best out of two solutions with respect to an
`calculated efficiency. The method takes both possibilities to
`60 proceed into account and thus avoids selecting a choice,
`which is alleged to be a good choice even if the other choice
`turns out to be even better.
`According to an aspect of the present invention the error
`signal comprises macroblocks. The method for coding is
`performed for one macro block at a time. Each macro block is
`subdivided into a plurality of subblocks. E.g. a macroblock
`comprises 16xl 6 picture elements and is subdivided into four
`
`65
`
`SUMMARY OF THE INVENTION
`
`Therefore, an object of the present invention is to provide
`an enhanced quantization for hybrid video coding.
`According to an aspect of the present invention a method is
`provided for coding a video signal using hybrid coding, com-
`prising reducing temporal redundancy by block based motion
`compensated prediction in order to establish a prediction
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 14 of 22 PageID #: 170
`
`US 8,634,462 B2
`
`5
`8x8 subblocks. The first quantization is then performed on
`each of these subblocks. If a transformation into the fre(cid:173)
`quency domain is involved, this is performed on the sub(cid:173)
`blocks before quantization.
`Subsequently, for each subblock a quantization efficiency
`for the first quantization and a zero efficiency for a quantiza(cid:173)
`tion are calculated, when all quantized values (samples or
`coefficients) are set to zero. These efficiencies are compared
`for each sub block, in order to decide if the quantized values of
`the corresponding subblock are maintained or set to zero. 10
`Subsequently, an overall quantization efficiency for the quan(cid:173)
`tization of all sub blocks of the macro block and an overall zero
`efficiency for an overall quantization when all values
`(samples or coefficients) of the macro block are set to zero are
`calculated. These overall efficiencies for the macroblock are 15
`compared and accordingly, quantized values for the further
`proceeding are determined. I.e. the quantized values are kept
`as they are, if the overall quantization efficiency is better than
`the overall zero efficiency and all the quantized values
`(samples or coefficients) are set to zero in the other case.
`According to an aspect of the invention the calculation of
`the efficiency is based on a cost function. Such a cost function
`takes negative and positive effects of the corresponding quan(cid:173)
`tization or setting to zero of values into account.
`According to one aspect the cost function is based on rate
`distortion costs, whereby the rate distortion costs are calcu(cid:173)
`lated depending on the required rate on the one hand and the
`resulting distortion on the other hand. The required rate_for
`coding is the sum of all bits required for coding of the values
`of the corresponding block, which may include some bits for
`side information.
`A further aspect of the invention provides, that the rated
`distortion costs are based on the sum of the required rate and
`a rated distortion. Therefore, a value for each efficiency will
`be obtained by adding the required rate and the distortion,
`whereby the distortion is weighted. The weighting of the
`distortion may depend on one or more parameters such as the
`quantizer step size. Of course, the required rate can also be
`rated or the required rate can be rated instead of rating the
`distortion.
`According to an aspect of the invention the rate distortion
`costs CJ are calculated using the equation CJ=DJ+L *Ri'
`whereby DJ represents the distortion resulting from the quan(cid:173)
`tization, RJ represents the rate required for the coding of the
`quantized values, L is a Lagrange parameter and the Index j
`depicts the corresponding subblock. The distortion may be
`calculated as the sum of the squared quantization errors or the
`mean absolute quantization error. Of course, there are other
`possibilities to evaluate the distortion.
`According to one aspect of the invention the method pro(cid:173)
`vides deciding, whether to transform the prediction error
`signal into the frequency domain or to maintain the prediction
`error signal in the spatial domain. Additionally the method
`provides to check a third possibility i.e. setting the values
`( samples or coefficients) of the prediction error signal to zero. 55
`Accordingly, the invention according to this aspect provides
`to select between this three possibilities. This selection is
`done for each block, such as a macroblock for which a pre(cid:173)
`diction error signal has been generated.
`If it is selected, to set the values ( samples or coefficients) of
`the prediction error signal to zero, i.e. of the current block, the
`result can be handled as a prediction error signal in the spatial
`domain or as a transformed prediction error signal in the
`frequency domain.
`According to one aspect of the present invention a coder for
`coding a video signal using hybrid coding is provided, com(cid:173)
`prising: means for reducing the temporal redundancy by
`
`6
`block based motion compensated prediction in order to estab(cid:173)
`lish a prediction error signal, quantization means for quantiz(cid:173)
`ing the prediction error signal in order to establish quantized
`samples or coefficients, control means adapted to calculate
`and to compare a quantization efficiency and a zero efficiency
`in order to select the quantization resulting in the higher
`efficiency and to either maintain the quantized samples or
`quantized coefficients respectively or to set them to zero,
`depended on the selected quantization.
`According to an aspect of the present invention, a method
`for coding a video signal is provided being based on hybrid
`coding. The method comprises the steps of reducing temporal
`redundancy by block based motion compensated prediction
`in order to establish a prediction error signal, and deciding
`whether to transform the prediction error signal into the fre(cid:173)
`quency domain, or to maintain the prediction error signal in
`the spatial domain.
`According to a corresponding aspect of the present inven(cid:173)
`tion, a coder is provided, which is adapted to apply hybrid
`20 coding of a video signal. The coder includes means for reduc(cid:173)
`ing the temporal redundancy by block based motion compen(cid:173)
`sated prediction in order to establish a prediction error signal,
`and means for deciding whether to transform the prediction
`error signal into the frequency domain, or to maintain the
`25 prediction error signal in the spatial domain. According to this
`aspect of the invention, a concept and corresponding appara(cid:173)
`tuses, signals and semantics are provided to decide adaptively
`whether to process the prediction error signal in the frequency
`or in the spatial domain. If the prediction error samples have
`30 only small correlation, the subsequent steps of coding the
`samples may be more efficient and they would lead to a
`reduced data rate compared to coding the coefficients in the
`frequency domain. Therefore, an adaptive deciding step and
`adaptive control means to make the decision are implemented
`35 by the present invention. Accordingly, in view of the predic(cid:173)
`tion error signal, it is decided whether to use frequency
`domain transform or to maintain the prediction error signal in
`the spatial domain. The subsequent coding mechanisms may
`be the same as for the frequency domain, or they may be
`40 adapted especially to the needs of the samples in the spatial
`domain.
`According to another aspect of the invention, the method
`for coding a video signal, and in particular the deciding step
`is based on a cost function. Generally, the decision whether to
`45 use the coefficients in the frequency domain or the samples in
`the spatial domain may be based on various kinds of deciding
`mechanisms. The decision may be made for all samples
`within a specific portion of a video signal at once, or e.g. even
`for a specific number of blocks, macroblocks, or slices. The
`50 decision may be based on a cost function, as for example a
`Lagrange function. The costs are calculated for both, coding
`in the frequency domain and coding in the spatial domain.
`Additionally, the costs are calculated for setting the values to
`zero. The decision is made for the coding with lower costs.
`According to another aspect of the present invention, the
`cost function includes the rate distortion costs for the coding
`in the spatial and in the frequency domain. According to still
`another aspect of the invention, the rate distortion costs may
`be calculated by the required rate and the resulting distortion
`60 weighted by a Lagrange parameter. Further, the distortion
`measure may be the mean square quantization error or the
`mean absolute quantization error.
`According
`to an aspect of the present invention, the
`samples in the spatial domain may be coded by essentially the
`65 same methods as being used for the coefficients in the fre(cid:173)
`quency domain. These methods may include the CABAC or
`CAVLC coding methods. CABAC stands for context-based
`
`

`

`Case 1:17-cv-01693-JFB-SRF Document 1-2 Filed 11/21/17 Page 15 of 22 PageID #: 171
`
`US 8,634,462 B2
`
`7
`adaptive binary arithmetic coding and CAVLC stands for
`context-adaptive variable length coding. These kinds of cod(cid:173)
`ing are presented in the latest standard H.264/AVC. Accord(cid:173)
`ingly, only little or no adaption of the coding mechanisms is
`necessary, if the adaptive control means decide to switch
`between the frequency and the spatial domain. However, it
`might also be provided to use different coding schemes for the
`coefficients in the two domains.
`According to another aspect of the invention, a method for
`coding a video signal is provided, which is based on hybrid 10
`coding. According to this aspect of the invention, the tempo-
`ral redundancy is reduced by block based motion compen(cid:173)
`sated prediction, and the samples of the prediction error sig(cid:173)
`nal are provided in the prediction error block in the spatial 15
`domain. The samples are scanned from the prediction error
`block in order to provide an array of samples in a specific
`order. According to this aspect of the invention it is provided
`that the scanning scheme is derived from a prediction error
`image or a prediction image. The scanning scheme according 20
`to this aspect of the invention takes account of the effect that
`the zigzag scan according to prior art for the frequency
`domain may not be the most efficient scanning order for the
`spatial domain. Therefore, an adaptive scanning scheme is
`provided, which takes account of the distribution of the 25
`samples and the magnitude of the samples in the spatial
`domain. The scanning scheme may preferably be based on a
`prediction error image or a prediction image. This aspect of
`the invention takes account of the most probable positions of
`the samples having the highest magnitude and samples being 30
`most probably zero. As the coding gain for the frequency
`domain is mainly based on the phenomenon that the low
`frequency components have larger magnitudes, and most of
`the high frequency coefficients are zero, a very effective,
`variable code length coding scheme like CABAC or CAVLC 35
`may be applied. However, in the spatial domain, the samples
`having the highest magnitude may be located anywhere
`within a block. However, as the prediction error is usually the
`highest at the edges of a moving object, the prediction image
`or the prediction error image may be used to establish the 40
`most efficient scanning order.
`According to an aspect of the present invention, the gradi(cid:173)
`ents of the prediction image may be used to identify the
`samples with large magnitudes. The scanning order follows
`the gradients within the prediction image in their order of 45
`magnitude. The same scanning order is then applied to the
`prediction error image, i.e. the samples in the prediction error
`image in the spatial domain.
`Further, according to still another aspect of the present
`invention, the scanning scheme may be based on a motion 50
`vector in combination with the prediction error image of the
`reference block. The scan follows the magnitudes of the pre(cid:173)
`diction