Quantization(Jan 21, 2003)• Optimal Quantizer• Uniform Quantizer01/21/01Quantization 2Image Quantizationu(continuous )Quantizeru’ ε {r1,r2,r3,....,rL}u’ut1tL+1tktk+1rk01/21/01Quantization 3Decision/Reconstruction Levelsu ε [tk,tk+1 ]rk{tk: k=1,2,....,L+1} Transition or decision levelsrkkthreconstruction levelExample:Uniform quantizer u ε [0,10.0]We wantu’ ε {0,1,.....,255}t1= 0; t257= 10.0; uniformly spaced, tk= (k-1).10/256k = 1,2,.....,257)01/21/01Quantization 4Example: quantizationrt tqtt rrkk kkkk kk=+FHGIKJ=+=− =−= ⇒−−1210256525611Quantization intervalConstant Uniform quantizer01/21/01Quantization 5MMSE QuantizerMinimise the mean squared error, MSE = Expected value of (u-u’)2given the number ofquantization levels L.Assume that the density function pu(u) is known (or can be approximated by a normalisedhistogram).Note that for images, u==image intensity. pu(u) isthe image intensity ditribution.01/21/01Quantization 6Optimum MSE quantizerΕΕ() (), (( )) ( )() ( )()[, ] ,()();uupuduMSE uu uupudu uupuduur uttur pudurtuuutkkkittiLukkLii==−′=−′=−′′=∈=−==∞∞∞∞+=zzzz∑++ Expected value of u =Since if we can rewrite this as Conditions for minimisation of are: --t1εεε∂ε∂∂ε∂22 2121110001/21/01Quantization 7MMSE (contd.)∂ε∂∂ε∂ttr pt tr pttrt tr rt trrrur pudurup u dupuduuu t tkk k uk k k ukkkk kk kk kkkkkuttkuttuttkkkkkkkk=− − − =≤< ⇒ −=−⇒ =+LNMOQP=−− =⇒ ==∈−+−−++++zzz( ) () ( ) ()()()()()()()(| [, ])12211110221 0111Now ---(A) -------(B)Ε01/21/01Quantization 8Optimum transition/reconst.(1) Optimal transition levels lie halfway between the optimumreconstruction levels.(2) Optimum reconstruction levels lie at the center of mass of theprobabality density in between the transition levels.(3) A and B are simultaneous non-linear equations (in general)Closed form solutions normally don’t exist usenumerical techniques01/21/01Quantization 9Uniform optimal quantizerConsider OtherwiseThen putttutrup u dupuduttuduttduuuttttrtttrrtuLLkuttuttLttLttttttkkkkkkkkkkkkkkkkkkkkkk()()()()();=−≤≤RS|T|==−−=FHGIKJ=−−=+ =+=⋅ ++++++++−+++++++zzzz10112212212121111111121221111111111bgbgtttttkkkkk++ =+−+−111201/21/01Quantization 10Uniform Quantizer Constant Quantization error is uniformly distributed over the interval Mean squared error u - u = u 2-q2q2tt t t qttLtt q rtqeuuqqqqkk k kLkk kk−=−= =−=+
View Full Document