46
`
`Image and Video Compressio11 for Multimedi a Engineering
`
`y
`
`2.1519_ ...
`
`1 .. 3439- •
`
`0.7560- ...
`
`0.2451 ___
`
`.......
`
`'
`-1.7479
`
`•
`
`'
`-1.0500 -0-5~0:.x.,O·c;~~
`
`•
`
`I
`
`0.5005
`
`1.0500
`
`'
`l .7479
`
`00
`
`y -
`
`I '
`
`....
`
`...
`
`. ..
`
`•
`
`FlGURE 2.13
`lnp ·ut-output characteristic of the optimal quantizer for Gaussian distribution \>.1ith z.ero mean,
`unit variance, and N = 8.
`
`decision levels are d'ensely distributed in the region having a higher probability of occurrence and
`coarsely distributed in other regions. A logarithmic companding technique also allocates decisio11
`levels densely in the small-magnitude region, which corresponds to a high occurrence probabilily,
`but in a different way. We conclude that nonunifonn quantization achieves 1ninimu1n n1ean square
`quantization error by distributing decision levels according to the statistics of the input random
`variable.
`These two types of nonuniforrn quantizers are both time-invariant. That is, they are not designed
`for nonstationary input signals. Moreover, even for a stationary input signal, if its pdf deviates from
`r.hat with \vhich the optimum quantizer is designed, then what is called 111is111c1tc/1 wi 11 take plat,;e
`and the perfor 111ance of the quantizer will deteriorate. There are two main type.s of mismatch. One
`is called. variance mismalcl1. That is, tl1e p'(if of input signal is matched, while the variance is
`mismatched. Another type is pdf mismatcl1. Noted that these two kinds of mis1natch also oc.ct1r in
`optimum uniform quantization, since there the optimization is also achieved based on the input
`statistics as-sumption. For a detailed analysis of the effects of the two t_y·pes of mismatch 0 11
`quantization, readers are referred to (Jayant and Noll, 1984).
`Adaptive quantization attempts to make the quantizer design adapt to tl1e varying input statis tics
`in order to achieve better performance. lt is a means to combat tl1e mis1natch proble1.11 discu sse·d
`above . By statistic .s, we m.ean the statistical n1·ean, variance (or the dynamic range), and type of
`input pdf When the mean o·f the input changes, differential coding (dis.cussed in the 11ext cl1apter)
`is a suit~ble method to handle the variation. For other types of cases, adaptive quantization is ·four1d
`to be effective. The price paid for adapt'ive quantization is processing delays and an extra storage
`re.quirement as see.n belcw .
`There are two different types of adaptive quantization: forward adaptation and backward
`adaptation. Before we discuss the-se, howeve.r, let us describe an alte.rnative way to defi11e quanti(cid:173)
`zatjon (Jayant and Noll, 1984 ). Look at Figure 2.14. Quantization can be viewed as a two-stage
`
`IPR2021-00827
`Unified EX1008 Page 72
`
`

`

`Quantization
`
`47
`
`In purx
`
`Quantization
`encoder
`
`-
`
`Interval index
`
`Quantization
`decoder
`
`-
`
`Outputy
`
`-
`Rcconstructio n
`level
`
`FIGURE 2.14 A two-stage model of c1uantization.
`
`proce ss . Tl1e first stage is tl1e quantiz .ation e11code·r and tl1e seco nd stage is tl1e quanti.zation decoder.
`In tl1e encoder, the input to quantizati o11 is co11verted to the i11dex of an i11terval into which the
`inpu t .,r falls. This index is mapped to (the codeword that represe nts) the reconstruction level
`corre 'ponding to the interva l in the decoder. Roug hly speaking, this definition considers a quantizer
`as a co n11Tiunication systen, in \vl1icl1 the quantization encoder is on tl1e transmitter side while the
`quantization decoder is on tl1e receiver side. I11 tl1is sense, this definit ion is broader than that for
`quan tizatio11 defined in Figur e 2.3(a).
`
`2.4.1
`
`FORWARD ADAPTIVE QUANTIZATION
`
`A block dia grrrrn or forward adaptive qua11tization is shown in Figure 2. 15. 'fhere, the input to tl1e
`quan tizer, .. r, is first split into blocks , each ,vitl1 a cer tajn length . Blocks are stored in a buffer one
`tati tical analy sis is then car ried out with respect to tl1e block in the buffer. Based on
`at a tin1e. A
`the analysis, tl1e quantization encoder is set up, and the input data witl1in tl1e block are assigned
`indexes o·f res pective intervals. In add itior1 to these indexes, the encoder setting parameters, derived
`from tl1e statistict1l a11alysis, are sent to tl1e qua ntization decode r as side inform·atio n. The term side
`comes fro 1n the f,1ct that tl1e amount of bits used 1~or coding tll'e setting parari1eter is usually a sma ll
`fract ion of the tota l an1ount of bits used.
`Se lection of tl1e b·lock size is a crit ical issue. If tl1e size is sn1all, the adaptatio r1 to the local
`statistics will be effective, but tl1e side infor111ation needs to be sent freque ntly. Tl1at is, more bits
`are used for sending tl1e side inforn·1ation. If tl1e size is large, the bits used for side inforn1ation
`decrease . On tl1e other l1and, the adapta tion becomes less sensitive to cha.nging statistics, and bot11
`processing delays and storage required ir1crease. Ih practice, a proper con1pron1ise between the
`quant ity of side i11for111ation ,111d the effectiveness of adaptation produces a good se lection of tl1e
`'block size.
`Exan1p les of using tl1e forward ,1pproacJ1 to adapt quantizatior1 to a changing input varia11ce (to
`comb at variance mismatcl1) can be fou11.d in (Jaya nt and Noll, 1984; Say·ood, 1996) .
`
`.
`
`Statistical parameters
`
`Input ;c
`
`Buffering
`
`-
`
`Statistical
`analysis
`
`-
`
`Quantization
`encoder
`
`11
`
`I
`
`•
`
`Interval
`index
`
`I
`
`Quantization Outputy
`ciecoder
`
`Reconsttuctio n
`level
`
`'-....
`
`--v(cid:173)
`transmitter
`
`_,,I
`
`\...
`
`/
`
`y
`•
`receiver
`
`FIGURE 2.15
`
`Forward adaptive quantization.
`
`IPR2021-00827
`Unified EX1008 Page 73
`
`

`

`48
`
`Image and Video Cornpression for Multi111edia Engineering
`
`Outpuly
`
`Quantization
`decoder
`
`I
`
`'
`
`I
`
`Buffering
`
`Buffering
`
`lnputx
`
`,.·
`
`Quantization
`encoder
`
`'
`
`'
`
`.
`
`Statistical
`analysis
`
`Statistical
`analysis
`
`,,
`
`'
`
`I
`
`I
`
`___ __ _,.,) \______
`
`\_____
`y
`transmitter
`
`___ ___ ,)
`V
`receiver
`
`•
`
`FIGURE 2.16 Bat k\vard adaptive quantization.
`
`2.4.2
`
`BACKWARD AD ,APTIVE QUANTIZATION
`
`Figure 2.16 sho\vs a block diagram of back\vard adaptive quantization . A close look at the block
`diagram reveals that in both the quantization encoder and decoder the b,ut~ferin.g and the stati stical
`analysis are carried out \Vith respect to the output of the qu.antizati on encoder. In thi s \vay, there
`is no need to se .nd side ·infor1nation . The sensitivity of adaptation to the ch-angi ng stati stics wi 11 be
`degraded, however; since instead of the original input, only the output of the quantization e ncoder
`is used in. the statistical analysis. That is, the quantization noise is involved in the statistical analysis.
`
`2.4.3
`
`ADAPTIVE QUANTIZATION WITH A ONE-WORD MEMORY
`
`it is expected that observance of a sufficiently large number of input or output (quantized)
`Intuitively,
`data is necessary
`in order to track the changing statistics and then adapt the q·uanti ze r setting
`in
`adaptive quantizatio ·n. Through an &.nalysis, Jayant showed that effective adaptations can be reali ze d
`with an explicit memory of o.nly one woro. That is, either one input samp le, x~ in forward adaptive
`is sufficient (Jayant, 1973).
`quantization
`or a quantized output,) ', in ·backward adaptive quantization
`In (Jayant, 1984), examples on step-s .ize adaptati0n (with the number of total reconstru ction
`levels larger than four) were given. The idea is as follows . If at moment t; the input sample X; t·t\lls
`into the outer interval,
`then the step size at the next moment t; .. 1 will be .enlarged by a factor ·of ,rz;
`the current step size by nz;, t1z; > 1). On the other hand, if the input x; falls into an
`(multiplying
`is less than 1, i.e., 11i; < l. That is , the multiplier
`interval clo ·se to x = 0 the .a, the multiplier
`inner
`in the interval near x = 0 and monotonically
`nz; is small
`increases for an increa sed x. Its range
`varies from a small positive number less than 1 to a number larger than 1. In this way, the quantize .r
`to th.e input to avoid overload as well as u11derload to achieve better performance.
`adapts
`itself
`
`2.4.4
`
`SWITCHED QUANTIZATION
`
`scheme . A block diagram is shown in ,Figure 2 .17. It co nsists
`This is another adaptive quantization
`of a bank of L quantizers4 Each quantizer
`they forn1 a ba11k
`in the bank is fixed, b.ut collectively
`
`•
`
`IPR2021-00827
`Unified EX1008 Page 74
`
`

`

`Quantiz ation
`
`-- ---------
`
`49
`
`inputx
`
`outputy
`
`Buffering
`
`Statistical
`analysis
`
`•
`
`• • •
`
`• • •
`
`FIGURE 2.17 Switcl1ed quantization.
`
`of qua ntizers wi tl1 a variety of input-output characteristics. Based on a statistical analysis of recent
`input or output samples, a switch connects the current input to one of tl1e quanti zers in the bank
`sucl1 that the best possible. performance may be achieved. It is reported that in both video and
`speech applications, this scl1en1e has st,own improved perfor:n1ance even when the number of
`quantizers in the bank, L, is two (Jayant and Noll, 1984). Interestingly, it is n.oted tl1at as L -) oo,
`the switched quar1tization converges to the adaptive quantizer discussed above.
`
`2.5 PCM
`
`Pulse code modulatior1 (PCM) is closely related to quantization, the focus of this chapter. Further(cid:173)
`more, as poi11ted out ir1 (Jaya11t, 1984), PCM is tl1e earliest, best establisl1ed, and most frequently
`applied cod ing syste111 despite the fact that it is tl1e 1nost bit-consu1ning digitizing syste1n (since it
`encodes eact1 pixel independently) as well as being a very dema11ding systen1 in ter rn.s o.f the bit
`error rate 011 tl1e digital channel. Tl1erefore, we discuss tl1e PC,M tecJ1nique in this section.
`PCM is ·now the most in1portant, form. of pulse modulation. Tl1e other t'om1s of pulse modulation
`are pulse amplitude n1odulation (PAM), pulse widtl1 n1odulation (PWM), and pul-se position mod(cid:173)
`ulation (PPM ), wl1ich are covered in n10st comn1unications texts. B1·iefly speaking , pulse modulation
`links an analog signal to a pulse train in the follo\ving way. The analog signal is firsl sampled (a
`discretization in tl1e tin1e don1ain). The sampled values are used to 1n·odulate a pulse trai11. If the
`modulation is carried out 1hrougl1 the amplitude of the pulse train, it is called PAM. If th,e n1odified
`parameter of the pulse train is tl1e pulse width, we then l1ave PWM. If tl1e pulse width and inagnitude
`onl·y the position of pulses is n1odulated by the sample values we then encounter
`are constant
`PPM . An illustration of these pulse modulations is shown in Figure 2.18.
`In PCM , an analog signal is first sampled. The sampled value is then quantized. Finally tl1e
`quantized value is encoded, resulting in a bit steam. Figure 2.19 provides an exa1nple of PCM . We
`see tl1at tl1rough a sampling and a uniforrn quantizatibn the PCM system converts tl1e input ar1atog
`signal, 'vv.hich is continuous in ho.th tirne and magnilude, into a digital sig11al (discretized in both
`time and magnitude) in the form of a natural binary c;ode sequence. In this way, an a·nalog signal
`n1odulates a pulse train with a natural binary code.
`By far, PCM is n1ore popular than other types .of pulse modulation since the c.ode modulation
`is mucl1 more robust against various noises than amplitude modulation, widtl1 modulatio11, and
`position modulatior1. In fact, almost all coding teol1niques include a PCM component. In digital
`in1age processing, g-iven digital i111ages usually appear in PCM forrnat. It is known tl1at an acceptable
`PCM representation of a monocl1rome pictore requires six to eight bits per pixel (Huang, 1975).
`It is used so commonly in practice that its performan ce normally serves as a standard against \Vhicl1
`0th.er coding techniques are con1pared.
`
`•
`
`IPR2021-00827
`Unified EX1008 Page 75
`
`

`

`50
`
`Image and Video Compression for Multimedia Engineering
`
`'
`
`/
`
`/
`
`-
`
`-
`
`'
`
`-
`
`f(t)
`
`'
`
`•
`
`I •
`
`'
`
`I
`
`•
`
`The _pulse train
`-
`-
`
`_ ,
`
`0
`
`0
`
`PAM
`
`'
`
`,
`
`/
`
`1,
`
`/
`
`"'
`
`~
`
`I•
`
`:\.
`
`I
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`...
`
`... ~
`
`- -
`• ... - .... -
`-
`
`,;
`
`,
`
`,
`
`~
`
`~-
`' '
`
`•
`
`,
`
`,
`
`,
`~
`
`,
`
`,
`
`,
`, ....
`
`,;
`
`,
`
`..
`' '
`'
`
`~
`
`...
`' ' ' ' ,....,
`
`0
`
`0
`
`- PWM
`
`-
`
`-
`
`....
`
`.... -
`
`-
`
`--
`
`-
`
`- -
`
`"
`•
`\
`
`PPM
`
`i '
`
`-
`
`0
`
`-
`
`-
`
`-
`
`-
`
`~
`
`-
`
`-
`
`-
`
`1,
`
`l
`
`-
`
`I
`
`-
`
`-
`
`~
`
`-
`
`I
`
`1
`
`FIGURE 2.18 Pulse modulation.
`
`I
`
`I
`
`I
`
`' '
`
`-'
`
`' • •
`
`I•
`
`-
`
`Recall the false contouring phenomenon discussed in Chapter 1, \vhen we discussed texture
`masking. It ·states that our eyes are more sensitive to relatively uniform regions in an image plane.
`If the number of reconstruction levels is not large enough (coarse quantiz·ation), then some unnatural
`contours will appear. When fr:equency masking was discussed, it was. noted that by adding son1e
`high-frequency signal before quantization; the false conto.uring can be eliminated to a great exte11t.
`This technique is called dithering. The high-frequency s.ignal used is referred to as a dither signal.
`Both false contouring and dithering were first reporte,d in (Goodall, l 951 ).
`
`2.6 SUMMARY
`Quantization ·is a process in which a ·quantity having poss,i.bly an infinite number of different values
`js converted to. another quantity having only finite many values. It is an important element in source
`encoding that has significant im.pact on both bit rate an.d distorlion of reconstructed images and
`video in visual co.mmu,nieation systems. Depend.ing on whether the quantity· is a scalar or a vector,
`quantization is called either scalar quantization or vector quantization. In this chapter we considered
`only scalar quantization.
`Unifo11n quantization is the sitnplest and yet the most important case. In uniforJTI quantizat,ion,
`except for outer intervals, both dec.ision levels and reconstruction levels are uniformly spaced.
`Mor.eover, a reconstructi on level is the arithmetic averag~ of the two con·espo,nding decision levels .
`In unifor111 quanti zation design, th.e step size is usually lne only param,eter that needs to be specified.
`
`IPR2021-00827
`Unified EX1008 Page 76
`
`

`

`Quantizatior,
`
`0000 Y1
`
`0001 Y2
`
`0010 Yl
`
`0011 Y4
`0100 Y5
`0101 Y6
`0110 Y1
`0111 Ya
`1000 Y9
`1001 Y10
`
`1010 Y11
`
`1011 Y12
`
`1100 Ytl
`
`1101 Yi•
`1110 Y1s
`
`1111 Yl6
`
`y
`
`d1
`
`d2
`
`d3
`
`<4
`
`d5
`
`I 2 J 4 5/
`~
`'
`
`9/
`
`8/
`
`1/
`,
`
`L
`
`-/
`
`d1
`
`ds
`
`~ • .
`
`d
`10
`
`d
`I I
`
`d
`12
`
`d
`13
`
`d
`14
`
`d
`15
`
`d
`16
`
`'
`
`d 17
`
`·-------------
`
`5 1
`
`10_11 _12
`....... 13
`' '\. rs
`
`14
`
`'
`
`•
`
`.
`
`\
`
`'
`
`16
`
`\
`' 17
`
`' ' \
`
`18
`
`X
`
`19
`
`\
`
`2~
`
`\
`2 1 \
`
`22 4
`'-
`-23~"-
`
`' ~
`
`,,
`29
`28
`
`27
`
`24
`-25-24-
`
`Output code (from left to right, from top to bottom) :
`
`0101
`
`0101
`
`0101
`
`0101
`
`0101
`
`0100
`
`0011
`
`0011
`
`0010
`
`0001
`
`0001
`
`0001
`
`0010
`
`0010
`
`0011
`
`0100
`
`0101
`
`1000 I
`
`1010
`
`1100
`
`110 I
`
`1110
`
`1110
`
`1111
`
`1111 '
`
`1111
`
`1111
`
`1110
`
`1110
`
`FIG URE 2.19 Pulse code modt1lation (PCM).
`
`Optimun1 quantization in1plies n1inimization 9f the mean square quantization ·error. Wl1en the
`input has a u11iform distribution ; uniform quantization is optimum. For the sake of simplicity, a
`uniform optimu m quantizer is sometimes desired even whe11 the input does not obey unifom1
`distribution. The desigr1 under tl1ese circumstances i.nvolves a11 iterative procedure. The design
`prob lem in cases where tl1e input l1as Gaussian, Lapacian, or Gamma distribution was solved and
`the parameters are available.
`When the constraint of un.iform quantizatio n is removed, the conditions for optimum quanti(cid:173)
`zatio n are derived. TI1e resultant optimum quantizer is no1111ally nonuniform. An iterative procedure
`to solve tl1e design is establisl1ed and tl1e optin1t1n1 design ·parameters for Gaussian, Laplacian, and
`Gamma distrib ution are tabulated.
`The compandi'ng technique is an alternative w·ay to implen1ent nonu11iform quantization. Botl1
`11on·uniform quanti zatior1 and con1pa11di11g are tjn1e-invarjant and l1ence 116t suitable for nonstation(cid:173)
`ary input. Adaptive quantization deals with nonstatio11ary input and con1bats the mismatch tl1at
`occurs in optimurn quanti,zation design.
`In adapti.ve quantization, buffering is 11ecessary to store some recent input or sampled output
`data. A statistical analysis is carried out with respec t to the stored recer1t data. Based 0 11 the analysis,
`the quantizer's paran1eters are adapted to changing i11put statistics to act1ieve better quantization
`p~rforn1a.nce. There are t\.VO types of adaptive quanti2atio11: forward and bac·k\vard adaptive quan(cid:173)
`tization. With the forward type, the statistical analysis is derived from the original input data, \.Vhile
`with tl1e backward type, quantizatio11 noise is involved in tl1e ar1alysis. Therefore, the forward
`
`•
`
`I
`
`IPR2021-00827
`Unified EX1008 Page 77
`
`

`

`52
`
`Image and Video Compression for Multimedia Engineerin g
`
`tecl1nique usually ·achieves more effective adaptation than the backward rnanner. The latter, however,
`does not need to send quantizer setting paran1eters as side infor1nation to the receiver side, since
`the 9utput values of the quantization encoder (based on wl1ich the statistics are analyzed and the
`quantizer's parameters are adapted) are available in both the tr,1nsn1 itt.er and rece iver sides.
`Switched quantization is another type of adaptive qua11tization. In this schen1e, a bank of fixed
`quantizers is utilized, each quantizer having differe11t input.;.oulput characteris tics. A statistical
`analy~is based on recent input decides wli1ich quantizer in the bank is suitable for the prese 11t input.
`The systen1 then connects tl1e input lo this particular quar1tizer.
`Nowadays, pulse code 111.odulation is the most frequently used forn1 of pulse 111odulation due
`to its robustness against noise. PCM consists of tl1ree stages: sampling, quantization, and e11coding.
`Analog signals are first sampled \vith a proper san1pling ·frequency. The sa111pled data are then
`quantized using a unifo1111 quantizer . Finally, the quantized vall1es are encoded \Vith natural binary
`code. It is the best established and mo st applied coding system. Despite its bit-con. u 111 i ng feature,
`it is utilized in almosJ all coding systems .
`
`2.7 EXERCISES
`
`2-1. Using your O\Vn \vords, define quantization and unil'or1n quantization. Wh at are lhe t\ VO
`features of uniform qua11tizati9n?
`2-2. What is optimum quantization ? Why is u1lifonn quantization sometimes desired, eve11
`\vhen the .input has a pdf different from uniform? How was this problem olved'? Draw
`an input-output cl1aracteristic of an optimum unifo1111 quantizer \vith an input obey ing
`Gaussian pdf having 2iero mean,, unit variance, and the nun1ber of reco11struction leve ls,
`N, equal to 8.
`2-3. What are the conditions of optimum nonunifor·m quantization? Fro111 Tab.le 2.2 , wl·1at
`observations can you make?
`2-4. Define variance mismatch and pdf misn1atch. Discuss ho\v you can resolve the r11ismatch
`problem.
`~5. What is the difference bet\veen forward a11d bac'k\vard adaptive quantizati on? Con1n1enl
`on the merits and dra,vbacks for each.
`2-6. What are PAM, PWM, PPM, and PCM? Why is PCM the most popular type of pulse
`modulation?
`
`R6FERENCES
`
`Fleischer. P. E. Sufficient conditions for achieving minimum distortion in quantizer, IEEE Jrzt. Co11ve11tio11
`Rec.~ 12, 104-111 , 1964.
`Gersbo, A. Quanti·zalion, IEEE Co111111Ll11. Mag., pp. 6-29, September, 1977.
`
`Gonzalez, R. C. and R. E. Woods. Digirc,l !,,,age Processi,ig, Addison-Wesley, Reading, MA. I 992.
`Goodall, W. M. Televisio·n by pulse code modulation, Bell S),st. Teel,. J., 33·49, January 195 1.
`Huang, T. S. PCM p·icture trans.mission, IEEE SJJec1r,,111, 2, 57-63, 1965.
`Jayan.t, N. S. Adaptive delta modulation with one--bit memory, Bell Sysr. Teclz. J., 49, 321-342, 1970.
`Jayant. N. S. Adaptive quantization with one word memory, Bell Syst. Tec/1. J., 52, 1119-1144, 1973.
`Jayant, N. S. and P~ Noll, Digital Codi11g of Wc,vefor111s, Prentice-Hall, Englewood Cljffs , NJ, .I 984.
`Li, W. and Y.-Q. Zhang, Vector-based signal processing and qunatization for image and video compression,
`l'roc~ IEEE~ 83(2), 317-335, 1995.
`Lloyd, S. P. Least squares quantization in PCM, Inst. Ma_thematical Statistics Meet., Atlantic City, NJ.
`September 1957; IEEE T,·a,zs. /11/ TJzeor)', pp. 129-136, March 1982.
`Max., J. Quantizing for minimum di.stortion, iRE Tra11s. /11f. Tlzeo1),, it-6, 7-12, 1960.
`Mu,smann, H. G. Predictive Image Coding, in /11,age Traris111ission Tec/111iq,,es, W. K. Pratt (Ed.), Academic
`Press. New York. 1979,
`
`IPR2021-00827
`Unified EX1008 Page 78
`
`

`

`Quantizatior,
`
`53
`
`Paez, M . D . and T. H . Gli sson, Mini111um n1ean squared error qunatizalion in speech PCM and DPCM Sysrems,
`IEEE Trc111s. Co,111111111. , 225-230, April 1972.
`Panter, P. F. and W. Dit e, Qu anti zation di stortion in pltlse cou nl modul atio n \Vith nonuniforn1 spacin g of level s,
`Pro c. IRE. 39, 44-48 , 195 1.
`Sayood, K. /111rocl1,cti ori to Date, Co111pression, M organ K aufmann Publi shers, San Francisco, CA , 1996.
`Sk lar, B. Di git r1/ Co1111111,11icc1tio11s: Ft,nclc1111e111a/s c111cl AJJp/icc11io11s, Prenti ce-Hall, Engl ewoo d Cliffs. NJ. 1988.
`Smi tl1, 8 . In sta11taneous co mpa11ding of quant ized signals, Bell S),st. Tec/1. J., 36, 653-709, 1957.
`
`•
`
`•
`
`•
`
`•
`
`IPR2021-00827
`Unified EX1008 Page 79
`
`

`

`•
`
`Unified EX1008 Page 80
`
`IPR2021-00827
`
`IPR2021-00827
`Unified EX1008 Page 80
`
`

`

`•
`
`•
`
`Instead of cncocling a signal directly, tl1e diffe1·e1ztial cocli1ig tech11ique codes the diff ere nee between
`tl1e signal itscl f a11d its prcdictior1. Therefore it is also known as p1·edictive codi1zg. By utilizing
`spatial a11d/or ten1poral i11terpixcl co11·elation, differential codir1g is an efficient and yet computalio11-
`,1ll.)1 si1n1)lc codi11g tech11ic1ue. I11 Ll1is cl1,1pter, \Ve first describe the differential tecl1nique in general.
`T,;vo compo11cnls of differential coding, prediction and qu.a11Lization, are discussed. There is an
`c111pJ1asis on (optimun1) predictio11, since quantization was discussed in CJ1apter 2. Wl1e11 Lhe differ(cid:173)
`ence signal (al o known as predictio11 error) is qL1antized, tl1e differential coding is called differential
`pt1lse code moclulalion (DPCM). Son1e issues in DPCtv1 are discussed, after which delta modulation
`(DM ) as a special case of DPCM is covered. The idea of differential coding involving image
`seque11ces is brieny discussed in tl1is cl1apter. More detailed coverage is presented in Sections Ill
`and IV, starting fro111 Cl1apte.r I 0. ] f quantization is not .included, the differential coding is referred
`to as inf or,naLion-preservj ng differential cod i11g. This is discussed at the end of the chapter.
`
`3.1
`
`INTRODUCTION TO DPCM
`
`As d·epict~d 1n Figure 2.3 1 a source e11coder consists of tl1e following tt1ree components: transt·or-
`1nati on, quantizatio11, and codeword assign111ent. The transfo1mation converts input into a format
`for quan tizatio11 follo\ved by codeword assig11me11t. In ott1er words, tl1e component of lransforrnation
`decides \Vl1ich forrnat ot· i.nput is to be encoded. As mentioned in tl1e previous ch·apter, inpu-t itself
`is not ncces ari I y the n1ost ui table format for encodi11g.
`Consider tl1e case of monocl1ro·me in1age encoding. The input is usually a 2-D array of gray
`level values of ar1 image obtained via PCM coding. The concept of spatial redundancy, discussed
`in Sec tion 1.2. J. I , tells us that 11.eighboring pixels of a11 i1nage are usually l1ighly correlated.
`Therefo re, jt is n1ore efficient to encode rl1e gray difference between two neigl1boring pixels instead
`of e11codi 11g the gray level values of each pixel. At the receiver, tl1e decoded difference is added
`back to reconsLruct tl1e gray level value of the pixel. Since 11eigl1borihg pixels are t1ighly co1Telated,
`Ll1e.ir gray level values .bear a great si111ilarity. He11ce, we expect that tl1e varia11ce of the difference
`signal wi 11 be s111aller than tl1at of tl1c original sign~!. Assume uni form quantiz ation and natural
`binary coding for the sake of sirnplicity. Tl1en we see that for the san1e bit rate (bits per sample)
`tl1e qua11tizatio11 error will be s111aller, i.e., a higher quality of reco11structed signal can be achieved.
`Or, for tl1e san1e quality of reconstructed signal, we need a lower bit rate.
`
`3 .1.1
`
`SIMPLE PtXEL-TO-PIXEL DPCM
`
`Denote. the gray level values of pixels along a row of an image as Z;, i = 1, · ·, M, where M is the
`total i1umber of pixels within tl1e row. Using the immedi.ately preceding pixel's gray l·evel value,
`Z;_1, as a prediction of tl1at or the present pixel. Z;, i.e.,
`
`•
`
`we then have the difference signal
`
`" Z -
`7
`• - ~ · I
`I-
`I
`
`(3.1)
`
`(3. 2.)
`
`55
`
`d. = z. - Z-= z. - Z- I
`
`I
`
`I
`
`I
`
`I
`
`I-
`
`IPR2021-00827
`Unified EX1008 Page 81
`
`

`

`56
`
`Im age and Video Com pression fo r ML1lt11n eclia Engin eering
`
`•
`
`0.012
`
`0.01
`
`Cl)
`
`-n,
`
`'-
`Cl) 0.008
`(.)
`C
`Cl)
`t: 0.006
`:::,
`0
`0
`0 0.004
`
`0.002
`
`1 16 31 46 61 76 91 106 121 136 151 166 181 196 211 22 6 241 256
`-
`
`.
`
`(a)
`
`Gray le\€1 \0 1ue
`
`0.18 ·--
`0.16
`
`--------
`
`-
`
`--
`
`-------
`
`----,
`
`0.14
`
`CD
`~ 0.12
`8 0.1
`C
`CD ....
`0,08
`~
`0.06
`0.04
`
`0 .02
`0.L-..------
`-255
`
`(b)
`
`---
`
`0
`Dff erence value
`
`255
`
`0 .18
`
`0.16
`
`0.14
`-as ....
`CD 0.12
`CD 0.1
`~
`CD
`t 0.08
`:,
`~ 0.06
`0.04
`
`0 .02
`
`0
`
`C
`
`•
`
`-9
`
`-8 · 7
`
`.
`-6 -5 -4
`
`.
`-3 -2 -1 0 + 1 +2 +3 +4 +6 +6 +7 +8 +9
`Off erence value
`
`FIGURE 3.1
`(a) Histogram of the original "boy and girl " image. (b) Hi stogram of the difference in1age
`obtained by using horizontal pixel-to-pix el diff erencing. (c) A close-up of the central portion of tl1e hislogram
`of the difference image.
`
`Assume -a bit rate of eight bits per sample in the quantization. We can see that although the dynamic
`range of the difference signal is theoretically doubled, from 256 to 512, the variance of the difference
`signal js actually much smaller. This can be confirmed from the histograms of the '' boy and girl''
`image (refer to Figure 1. 1) and its difference image obtained by horizontal pixel-to-pixel differ(cid:173)
`encing ., shown in Figure 3.1 (a) and (b), respectively. Figure 3. l(b) and its close-up (c) i11dicate that
`by a rate of 42.44o/o tl1e difference values fall into the range of - 1, 0, and + l . I11 other words, the
`histogram of the difference signal is much more narro,vly concentrated tl1a11 tl1at of the origin al
`signal.
`
`IPR2021-00827
`Unified EX1008 Page 82
`
`

`

`Diffe ren·rial Coding
`
`57
`
`z
`
`(
`
`+
`. L
`,.
`z,_1 = z, ' -
`
`d,
`
`Quantization
`
`-
`d,
`
`,.
`d, +
`'t,
`+ .
`-z,_,
`
`•
`
`Delay
`
`-z,
`
`.
`
`(a) Encoder
`
`•
`
`(b) Decoder
`
`FIGURE 3.2 Block diagram or a pixe l-to-pixel clif ferential coding system.
`
`A block diagram of the sc·heme described above is shown in Figure 3.2. There z. denotes the
`sequence of pixels along a row, d; is the corresponding difference signal, and d; is the quantized
`version of tl1e di fference, i.e.,
`
`"'
`
`I
`
`d. = Q(cl.) = d. + e
`
`I
`
`I
`
`I
`
`(/
`
`(.3 .3)
`
`•
`
`wl1ere eq represents the quantization error. In the decoder, Z; represenlS tl1e reconstructed pixel gray
`value, a11d we l1ave
`
`z. = Z, I + d.
`
`I
`
`/ -
`
`"
`I
`
`(3 .4)
`
`This sirnple schen1e, however, suffers fron1 an accun1ulated quantization error. We can see this
`clearly fron1 the followj ng derivation (Sayood, 1996), wl1ere we assutne the initia.1 value z0 is
`avai table for both the encoder ar1d the decoder .
`
`"
`z1 = z0 + d 1 = z0 + d 1 + eq.i = z 1 + eq.i
`
`•
`
`Sitni larly, w e can have
`
`and, in general,
`
`•
`I
`
`z. = z. + ~ e .
`.L..J t/,}
`j=I
`
`I
`
`I
`
`(3 .5)
`
`•
`
`(3 .6)
`
`•
`
`(3 .7)
`
`This problem can be re111edied by tl1e following sche.me, sl10\.vn i 11 Figure 3.3. Now we see that
`in both the encoder and the decoder, tl1e reconstru·cted signal is generated in the same ,vay, i.e.,
`
`z. = z. I + d.
`
`,...
`
`I
`
`I
`
`/ -
`
`.
`
`(3 .8)
`
`and i·n the encod~r the djff erence signal changes to
`
`d, = z. - z. J
`
`I
`
`I -
`
`I
`
`IPR2021-00827
`Unified EX1008 Page 83
`
`

`

`58
`
`linage and Video Compression for Multimedia Engineering
`
`z,
`
`A
`
`+ ,,~, d;
`l:
`-
`-
`z, = z,_1
`•
`
`•
`
`•
`
`Quantization
`
`A
`
`d,
`
`-
`
`-
`z,_, ·+ ,
`+
`'
`\. l:
`
`-z {
`
`Delay
`
`-z,
`
`A
`
`d, +
`-
`-
`l:,
`-.+
`•
`-z,_,
`
`Delay
`
`(a) Encoder
`
`(b) Decoder
`
`FIGURE 3.3 Block diagram of a practical pixel-to-pixel differential coding systen1.
`
`Thus, the previously reconstructed Z;_1 is used as the predictor, Z;, i.e.,
`
`.
`
`A
`
`7 -z
`
`A
`
`~ .~ -
`I
`
`-
`
`.. 1 •
`1-
`
`In this \Vay, ,ve have
`
`Similarly, we have
`
`•
`
`. as
`
`i =2,
`
`-
`
`q,
`
`,..
`d, = d2 + e 2
`z2 = i 1 + d,, = z2 + e 2
`
`A
`
`-
`
`q.
`
`In gene.ral,
`
`-Z- = z. + e .
`
`I
`
`I
`
`qJ
`
`(3 . 10)
`
`(3.11)
`
`(3 .12)
`
`(3 .13)
`
`Thus, we see that the problem of the quantization error accumulation has been resolved by
`having both the e.ncoder and the decode·r work in the same fashion, as i.ndicated in Figure 3.3, or
`in Equations 3.3, 3.9, and 3.10 .
`
`3.1.2
`
`G .ENERAL OPCM SYSTEMS
`
`In the above discussionJ we can view the reconstructed neighboring pixel's gray value as a prediction
`of that of the pixel being coded. Now, we generalize this simple pixel-to-pixel BPCM. ln a general
`DPCM system , a pixel's gray level value is first predicted from the preceding reconstructed pix.els'
`gray level values. The difference between tfie pixel',s gray level value and the predicted value is
`then quantized. Finally, the quantized difference is encoded and transmitted to the receiver. A block
`
`IPR2021-00827
`Unified EX1008 Page 84
`
`

`

`Differential Coding
`
`z I
`
`+
`
`-
`
`~ d ,
`l:
`-
`
`•
`
`..
`d ,
`
`Quaotizalion
`
`z, = I,.a j zl-J
`
`n
`
`/a. I
`
`..
`Z1 +
`
`59
`
`-z,
`
`.
`
`•
`
`, ,
`
`+
`
`.
`
`l: '
`•
`' +
`..
`z,
`
`.._ l: - -z,
`Prediction - Delay -
`
`... Prediction
`
`Delay -
`
`FIGURE 3.4 Block diagram of a general DPCM system.
`
`d iagra m of tl1is general clifferential coding scheme is Shown in ·Figure 3.4, where the codeword
`,1ssignment in Lhe encoder and its counterpart i11 decoder are not .included.
`It is noted that, instead of using the previously reconstructed san1ple, z~_1, as a predictor, we
`110w ~1ave the predicted version of Z;, Z;, as a function of tl1e n previously recon structed
`san1ples, z,_1, z,_2 , · · · , z,_,1
`• That is,
`
`z,. = f ( z,._, , f;_2 , · · · , Z;-n)
`
`(3.14)
`
`Linear prediction, i.e., that tl1e function fin Equation 3. 14 is linear, is of particular i.nterest and
`is widely used in differential coding. I11 linear prediction, we have
`
`n
`
`,.. L -
`z. =
`
`I
`
`a .z . .
`J 1- J
`
`(3.15)
`
`j= l
`
`where c1i are real paran1eters. J-Ience, we see that the simple pixel-to-pixel differential codjng is a
`specia l case of general differential coding with linear prediction, i.e., 11 = l and a1 = l.
`In Figure 3.4, di is the difference sign.al and is equal to the difference between the original
`signal, Z;, and tl1e prediction Z;, TJ1at js,
`
`C.. = z. - z.
`"
`f
`
`I
`
`I
`
`I
`
`(3.16)
`
`"
`The quantized version O'f cl,. is denoted by d;. The re.constructed version of Z; is represented
`by Z;, and
`
`z. == z. + d.
`
`I
`
`I
`
`A
`
`I
`
`(3.17)
`
`Note that this is true for botl1 tl1e encoder and the decod.er. Recall that the accumu lation of the
`quantization error can be remedied by using this method.
`Tl1e difference between the original input and the predicted input is called prediction error,
`,. That is,
`which is denoted by e1
`
`(3.18)
`
`where the e,, is understood as the prediction error associated witl1 the index i. Quantization error,
`e", is equal to the reconstruc.tior1 error or coding error, e,, defined as the difference ·bet\veen the
`original signal, z,., and tl1e reconstructed signal, Z;, when the transmission is error t·ree:
`
`IPR2021-00827
`Unified EX1008 Page 85
`
`

`

`60
`
`Image and Video Compression for Multim~di a Engineering
`
`,.
`e = d. - (/.
`q
`
`I
`
`I
`
`· I
`
`I
`
`I
`
`I
`
`= (z. - z.)-(z. - z.)
`-
`= z. - z. = e
`
`(3. 19)
`
`· 1
`
`I
`
`r
`
`•
`
`This indicates that quantization error is the 011ly source of inforn1ation loss with a,1 error-free
`transmission channel.
`The DPCM system depicted in Figure 3.4 is also called closed-loop DPCM \vith feedback
`around the. quantizer (Jayant, 1984). This ter 111 reflects the feature in DPCM structure.
`Before \Ve leave this section, let us take a look at the history of the developn1ent of di1·rerential
`image coding. According to an excellent early article on differential i1nage coding (Mus mann,
`1979), tl1e first theoretical and e.xperimental approaches to in1age codi 11g involving Ii n.ear pred iction
`began in 1952 at the Bell Telephone Laboratories (Oliver, l 952 ; Kretzmer1 1952 ; Ha