數(shù)字視頻通信-dvt05b圖像的量化

門愛東教授

第5講

率失真理論

量化

2本章內(nèi)容Outlines標量量化的原理量化失真的客觀度量Loy-Max量化器—最佳均方量化器(MMSE)均勻量化器高分辨率量化近似熵約束量化器矢量量化3量化模擬信號數(shù)字化中的量化：在實際中，信號的波形都是典型的連續(xù)幅度和連續(xù)時間，因此模數(shù)（A/D）變換用來產(chǎn)生波形的離散表示形式。經(jīng)過抽樣后的樣值在幅度上仍然是連續(xù)的，幅度量化過程是用來把可能的幅度數(shù)目限制到有限個數(shù)目。由于幅度量化在很大程度上決定了系統(tǒng)總失真，以及把波形傳送到接收端所必需的比特率。因此，量化是數(shù)字通信中關(guān)鍵的過程。量化在圖象領(lǐng)域常有兩種用途一是將模擬信號轉(zhuǎn)變成數(shù)字信號，以便于隨后進行數(shù)字處理，一般采用線性量化器，量化區(qū)間均勻劃分，以區(qū)間的中間值做量化輸出值。另一種用途是數(shù)據(jù)壓縮，如在DPCM系統(tǒng)中對預(yù)測差值的量化，這種場合常用不均勻量化。量化類型標量(Scalar)量化：對每一個樣值做獨立的量化。矢量(Vector)量化：由K個樣值構(gòu)成K維空間的一個矢量，然后對其進行一次性量化。4標量量化的原理量化實質(zhì)上可以看作是一個映射的過程。將所有取值落在Ri

范圍內(nèi)的輸入信號映射到輸出一點yi

上。5標量量化器的設(shè)計量化器的設(shè)計要求，通常設(shè)計量化器有下述兩種情況：給定量化分層級數(shù)L，使得量化誤差D最小。限定量化誤差D，確定分層級數(shù)L，滿足以盡量小的平均比特數(shù)表示量化輸出，即碼率R最小。標量量化又可分為:均勻量化、非均勻量化和自適應(yīng)量化非均勻量化特性曲線均勻量化特性曲線6量化噪聲（誤差）輸入x與輸出

y之間的誤差是量化過程中所固有的，稱為量化誤差。量化誤差(噪聲）是數(shù)字小信號失真的主要來源。量化處理是多個對一個的處理過程，是個不可逆過程，有信息丟失，或者說，會產(chǎn)生量化噪聲。不同于信道噪聲或熱噪聲，量化噪聲不是隨機引入的，一般說來，它與被量化的信號相關(guān)。度量量化誤差時，首先需要一個衡量的標準，比如，均方誤差準則（MSE）、絕對值誤差準則等。下面的討論都基于廣泛使用的均方誤差準則。7量化的失真測度均值表示，設(shè)輸入隨機變量x

的概率分布函數(shù)為p(x)。d[x,Q(x)]

用均方誤差表示，稱為均方量化誤差

(Meansquaredquantizationerror,MSQE)。設(shè)量化Q(x)={yi，Ri，i=1，…，L}，則失真D為:8Lloyd-Max標量量化器-最佳均方量化器MMSE問題：信號x

的概率密度函數(shù)為p(x)

，設(shè)計一個

L

個輸出電平的量化器，以均方誤差作為評判標準，使其最?。航Y(jié)果：Lloyd-Max最佳均方量化器（MMSE，Lloyd1957;Max1960）L-1

個判決電平(門限)精確地位于輸出電平之間的中點→最近鄰L

個量化輸出電平位于p(x)函數(shù)在兩個連續(xù)判決門限之間的質(zhì)心必要條件，但不充分9證明：根據(jù)上節(jié)講述的量化失真度量公式，得

現(xiàn)在要對此多元方程求D的極小值，根據(jù)拉格郎日極值定理，分別對xi

及yi

求偏導(dǎo)，并使之為0，得：求解上述方程得：Lloyd-Max標量量化器10下面進一步分析最佳均方量化器的三個主要特點：設(shè)y=Q(x)

，量化誤差ε=y-x=Q(x)–x

，則Lloyd-Max標量量化器特性量化誤差的均值為0，量化誤差無直流分量量化誤差和重建信號不相關(guān)，正交量化誤差的方差為輸入、輸出信號方差的差值，因此，量化輸出信號方差減少A.K.Jain，F(xiàn)undamentalsofdigitalimageprocessing，p10311證明：(1)Lloyd-Max標量量化器特性令則(2)輸出電平位于p(x)函數(shù)在兩個連續(xù)判決門限之間的質(zhì)心12說明：（1）E[ε]=0，量化誤差沒有直流分量。用ε=x-Q[x]=x–y

替換，得到E[x]=E[y]。這表明MMSE量化器的輸出電平y(tǒng)是輸入電平x的的無偏估計。（2)E[Q(x)ε]=0，量化誤差正交于量化器的輸出電平。（3）E[ε2]=σε2=σx2-σy2

，做數(shù)學(xué)代換得到，如圖所示，經(jīng)過最佳量化器以后，信號的均方差減小了f(B)

倍。當輸入信號的均方差σx2=1時，f(B)

就等于B比特最佳量化器的均方失真。Lloyd-Max標量量化器特性(3)前面已經(jīng)證明：13Lloyd-Max標量量化器的設(shè)計基本思想：前面介紹的最佳量化器條件，即最小均方誤差（MMSE）量化器的最近鄰條件和質(zhì)心條件。給定xi

，可以計算對應(yīng)的最佳yi給定yi

，可以計算對應(yīng)的最佳xi顯然，判決電平xi

和量化電平y(tǒng)i

的求解是一個相互依賴的過程。問題：如何同時計算最佳的xi

和yi

？答案：迭代，或查表法14Lloyd-Max標量量化器設(shè)計的迭代法迭代法就是選擇參量，以同時達到最佳分區(qū)（最鄰近條件）和最佳碼表（質(zhì)心條件）的算法。Lloyd-Max迭代算法的具體步驟如下：

15Lloyd-Max算法舉例Ix是均值為0，方差為1的高斯分布，即x~N(0,1)設(shè)計一個4電平的量化器，使得失真D*

最小用Lloyd-Max算法得到最佳量化器判決電平（邊界）：-0.98,0,0.98量化（重建）水平：–1.51,-0.45,0.45,1.51Lloyd-Max標量量化器設(shè)計的迭代法SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.SchwarzP114-11616收斂情況初始化A：判決邊界為：–3,0,3初始化B：判決邊界為：–1/2,0,1/2Lloyd-Max標量量化器設(shè)計的迭代法在兩種情況下，經(jīng)過6次迭代后，17Lloyd-Max算法舉例IIx是均值為0，方差為1的Laplacian分布設(shè)計一個4電平的量化器，使得失真D*

最小用Lloyd-Max算法得到最佳量化器判決電平（邊界）：-1.13,0,1.13量化（重構(gòu)）水平：-1.83,-0.42,0.42,1.83一個好的預(yù)測器輸出的預(yù)測差值信號通常滿足0周圍高峰值的分布，如Laplacian分布Lloyd-Max標量量化器設(shè)計的迭代法18初始化A：判決邊界為：–3,0,3初始化B：判決邊界為：–1/2,0,1/2收斂情況在兩種情況下，經(jīng)過6次迭代后，Laplacian分布的尾巴更長，外側(cè)步長大；同時，內(nèi)側(cè)步長小，因為在中心附近概率大。Lloyd-Max標量量化器設(shè)計的迭代法194比特Laplacian最優(yōu)量化器當輸入方差小于假定方差，SNR下降很快。均方量化噪聲MSQE減小，因為過載噪聲減小。但是由于輸入方差小，SNR中的信號/噪聲比率減小很快。當輸入方差大于假定方差，均方量化噪聲MSQE相應(yīng)增大，但是由于輸入信號的能量增大，信號/噪聲比率減小緩慢。當真實的數(shù)據(jù)方差和假設(shè)的方差不匹配時造成的影響Lloyd-Max標量量化器設(shè)計的迭代法20當信號x

的概率密度函數(shù)p(x)

不是均勻分布時，需要采用上述的反復(fù)迭代方法設(shè)計最佳均方量化器。這種迭代過程是比較麻煩的，Max已經(jīng)針對不同分布的p(x)，計算出了最佳量化電平和判決電平。在某些情況可以直接套用。Lloyd-Max標量量化器設(shè)計的查表法判決門限輸出電平21Lloyd-Max標量量化器設(shè)計的查表法22Lloyd-Max標量量化器設(shè)計的查表法已知輸入信號x

的概率密度函數(shù)p(x)

為均勻分布、高斯分布、拉普拉斯或雷利分布，且均值E[x]=0，標準方差σx

=1時，得到最佳量化器量化電平y(tǒng)k(k=1,2,.,L)標準表。問題：當隨機變量x’

的均值μ=E[x’]≠0，標準差σx’≠1時，如何由標準表轉(zhuǎn)換出相應(yīng)的量化電平？具體步驟如下圖：23均勻量化器當信號x

的概率密度函數(shù)p(x)

在整個范圍內(nèi)是均勻分布時，即p(x)

為常數(shù)c時，上述Lloyd-Max最佳均方量化器變?yōu)榫鶆蛄炕?，其輸出的量化電平為?/p>

判決電平仍為：（在輸入?yún)^(qū)間上等間隔分布）

表明：對于均勻分布，均勻量化是最佳量化器對應(yīng)輸入信號區(qū)間(xi-1，xi）的中值，換言之，量化電平是判決電平xi-1

和xi

的算術(shù)平均值。量化電平是等間隔分布的。24均勻量化器當輸出電平數(shù)L為偶數(shù)時，為中升型(Midrise)均勻量化器，0不是是一個輸出電平；L為奇數(shù)時，為中平型(Midtread)均勻量化器，0是一個輸出電平，圖像、視頻和音頻中常采用的。當輸入信號具有直流分量時，將其直流分量減去，然后通過圖示的關(guān)于原點奇對稱的均勻量化器，最后再將其直流分量加上。LL=4LL=525以均勻分布的均勻量化器為例輸入：均勻分布的信源，幅度有界[a,b]，則pdf為輸出：L個等間隔電平（L

又稱為量化級數(shù)，L=2R）量化步長：判決電平和量化電平：顆粒失真（GranularNoise）：

均勻量化誤差與輸入信號的關(guān)系如圖。處在均勻量化范圍內(nèi)的量化誤差大小為[-0.5△,+0.5△]，稱之為顆粒失真，或者顆粒噪聲，表示為Dgran顆粒失真和過載失真26平均顆粒失真：代入得顆粒失真和過載失真27若輸入信號x先經(jīng)過歸一化處理，使其范圍在x∈[0,1]，即b-a=1，則上面等式成為：信噪比為：說明：量化級數(shù)每增加1bit，則步長減小一半，均方量化噪聲減為?，SNR增加6dB。人眼視覺對圖像中變化不大、較為均勻的區(qū)域（低頻）比較敏感，而對細節(jié)（高頻）部分的敏感程度相對較弱。因此，通常對圖像信號中的低頻部分采用較大的量化級數(shù)。顆粒失真和過載失真28變暗、只保留輪廓1比特量化：[0,127]64[128,255]1962比特量化：邊界：{[0,64,128,196,255}重構(gòu)水平{32,96,160,2243比特量化例：81,2,3bits/pixel顆粒失真和過載失真2929顆粒失真和過載失真當分布不再是均勻分布時，需要考慮信源的pdf不同分布的信源，均勻量化時的SNR和最優(yōu)步長30輸入信號幅度為無界(-∞,∞)時在兩個區(qū)間（-∞,x1]和[xL-1,∞)產(chǎn)生過載失真

Dol

（OverloadNoise）；在其它的

L-2

個區(qū)間(x1,xL-1)產(chǎn)生顆粒噪聲，即量化失真大小在[-0.5△,+0.5△]內(nèi)的誤差。一般而言，顆粒失真幅度相對較小、產(chǎn)生的概率隨著輸入樣值的不同而不同；過載失真幅度大，但只要量化器的負載因子γ設(shè)計合理，其產(chǎn)生的概率非常小。假設(shè)輸入隨機信號零均值、對稱量化器，則該均勻量化器的噪聲D為：顆粒失真和過載失真31顆粒失真和過載失真負載因子γ定義為：負載因子確定了無過載失真的量化器的最大半幅度范圍，即（0，xoe）。xoe是被量化信號的均方根σx

的倍數(shù)，常常取值xL-1

或者yL，或者對于常用的對稱量化器取xoe=(xL-1-x1)/2。負載因子的典型取值范圍是2~4。例如，p(x)

為高斯分布，當γ=2時，其過載概率P{|x|≥xoe}為0.46；當γ=4時，其過載概率為0.000064，此時的過載失真可忽略。負載因子反映輸入信號和量化器之間的匹配程度。在實際應(yīng)用中，必須調(diào)整輸入信號的電平增益以獲得合適的負載因子，以保證均勻量化器的信噪比；換言之，均勻量化器的性能對輸入信號電平很敏感。因此，當輸入信號的功率電平范圍未知或者是時變信號時，需要高分辨率的量化器，以保證得到滿意的性能指標。

32輸入信源：Gaussian，均值為0，4比特Gaussian均勻量化器當輸入方差小于假定方差，SNR下降很快，MSQE減小，因為過載噪聲減小，但是由于輸入方差小，SNR中的信號/噪聲比率減小很快。當輸入方差大于假定方差，MSQE相應(yīng)增大，但是由于輸入信號的能量增大，信號/噪聲比率減小很慢顆粒失真和過載失真方差不匹配的影響8電平量化器SNR設(shè)計的步長逐漸比“正確的”步長大，性能下降很快（類似方差比預(yù)計的方差?。?3高分辨率量化近似在一般高分辨率（或高碼率）量化時，L≥32

則在信號x

的概率密度函數(shù)p(x)

的不同分段區(qū)間內(nèi)，可用常數(shù)代替，如下圖所示：p(x)

可用分段恒常數(shù)代替，每一區(qū)間均勻量化xp(x)xi’ixi-1xipx)≈p(xi’)均勻量化對于輸入是均勻分布的信號而言是最佳量化器（MMSE）；當輸入信號不是均勻分布時，也可以使用均勻量化器，只要量化級數(shù)L足夠高，其效果近似于MMSE。與MMSE量化器相比，均勻量化器的優(yōu)點是設(shè)計實現(xiàn)簡單，可以避免求解MMSE的非線性方程組。34高分辨率量化近似基于上述近似簡化，根據(jù)最小均方誤差準則得到的量化電平y(tǒng)i

，正好是均勻量化器的條件，即：證明：

利用近似條件

對

yi

求偏導(dǎo)，使，可解得：證畢。

35高分辨率量化近似設(shè)，則其中

稱這種量化方法為高分辨率近似最佳均勻量化器。結(jié)論：對于方差為σ2

的高斯信源，下面文獻證明，其均勻量化誤差為:一般性結(jié)論：均勻量化誤差具有形式，其中，c為常數(shù)，取決于信號概率密度函數(shù)。也稱為Panter

andDite公式。SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.SchwarzP125，p12636Lloyd-Max量化器是對固定碼率編碼的優(yōu)化，對于變字長（變碼率）編碼，怎樣做更好？量化的三個部分選擇判決邊界選擇重構(gòu)電平（量化電平）選擇碼字前面討論的：給定L個重構(gòu)電平，以均方量化誤差(MSQE)最小來衡量量化器的性能，所有區(qū)間用固定碼率編碼：log2L

比特?，F(xiàn)在討論另一個問題：用碼率R(bit/sample）或者“熵”衡量量化器的性能采用同樣設(shè)計的量化器(Lloyd-Max量化器)，對量化輸出用變長碼編碼?？紤]判決的選擇會影響碼率，重新設(shè)計量化器（熵約束量化器）。熵約束標量量化器37低碼率情況下，定長碼與熵編碼之間的差異并不大高碼率情況下，定長碼與熵編碼之間的差異增大Laplacian分布的32電平均勻量化器，定長碼需5比特，熵編碼只需3.779比特定長碼與均勻量化輸出熵編碼之間的差異大于定長碼與非均勻量化輸出熵編碼之間的差異非均勻量化器在大概率區(qū)域步長小，在小概率區(qū)域步長大使得每個區(qū)間的概率相近增大非均勻量化輸出的熵分布越接近均勻分布，上述差異越小。NumberofLevels定長碼(bit)GaussianLaplacianUniformNonUniformUniformNonUniform421.9041.9111.7511.72862.4092.4422.1272.207832.7592.8242.3942.4791643.6023.7653.0633.4733254.4494.7303.7794.427Outputentropiesinbitspersamplesforminiummeansquarederrorquantizes熵約束標量量化器對Lloyd-Max量化器的輸出進行熵編碼38熵約束標量量化器

Entropy-constrainedScalarquantizer,

ECSQ用量化器輸出結(jié)果的熵作為碼率的度量對量化輸出電平用熵編碼技術(shù)編碼量化器輸出電平的熵定義為所以輸出電平y(tǒng)i

的選擇不影響碼率，只影響失真。但判決邊界xi

既影響失真，也影響碼率，因此需要引入一個參數(shù)λ均方量化誤差MSQEP.A.Chou,T.Lookabaugh,R.M.Gray,“Entropy-constrainedvectorquantization,”IEEETrans.SignalProcessing,vol.37,no.1,pp.31-42,Jan1989熵約束標量量化器39給定碼率限制H(Q)≤R0，求得{xi},

{yi}和二進制碼字，使Lagrange代價函數(shù)最?。禾珡?fù)雜，不能直接求解用迭代法求解

在最小化

J(λ)中λ

的作用較大的λ

H(Q)的權(quán)重更大只保留較小的熵H(Q)隨著λ的增加減小可以用二分法求解最佳的λ

，使得H(Q)=R

H(Q)熵約束標量量化器40ECSQ算法（二重循環(huán)）選擇一個初始的λ≥0（外層循環(huán)，控制碼率H(Q)）初始化所有的yi，j=0，D0=∞（里層循環(huán)，控制失真D）計算判決邊界：更新所有的yi

：更新pi

：計算MSE：若，轉(zhuǎn)第8步；否則j=j+1，轉(zhuǎn)第3步若，調(diào)整λ，轉(zhuǎn)第2步熵約束標量量化器JPEG2000：ImageCompression，F(xiàn)undamentals，StandardsandPracticebyDavidS.Taubman，p10541ECSQ算法的應(yīng)用(I)x是均值為0，方差為1的高斯分布，即x~N(0,1)設(shè)計一個R≈2的ECSQ，使得期望失真D*最小11個區(qū)間（[-6，6]內(nèi)）：幾乎是均勻

定長編碼：熵約束標量量化器SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.SchwarzP121-12342所有的實驗中使用相同Lagrange乘子λ初始化A：初始化為15個均勻區(qū)間

初始化區(qū)間數(shù)量足夠多，

在迭代過程逐步減少

初始化B：初始化為4個均勻區(qū)間

對于給定的λ值，初始的區(qū)間數(shù)目太少，在迭代20次時沒有達要求的量化器性能R=2熵約束標量量化器43ECSQ算法的應(yīng)用(II)x是均值為0，方差為1的Laplacian分布設(shè)計一個R≈2的ECSQ，使得期望失真D*最小21個區(qū)間（[-10，10]內(nèi)），幾乎是均勻的熵約束標量量化器44熵約束標量量化器所有的實驗中使用相同Lagrange乘子λ初始化A：初始化為25個均勻區(qū)間

初始化區(qū)間數(shù)量足夠多，

在迭代過程逐步減少

初始化B：初始化為4個均勻區(qū)間

對于給定的λ值，初始的區(qū)間數(shù)目太少，在迭代20次時沒有達要求的量化器性能R=245高碼率下ECSQ的性能對均方量化誤差(MSQE)和高碼率（高分辨率），均勻量化器（緊跟熵編碼）是最佳的

[Gish,Pierce,1968]由前所述，如果概率密度函數(shù)不是均勻分布的，那么所得到的最佳量化器是一個非均勻量化器。H.GishandJ.N.Pierce,“Asymptotically.efficientquantizing,”IEEETrans.Inform.Theory,.vol.IT-14,pp.676-683,Sept.1968.

非均勻量化器可由一個均勻量化器和壓擴器表示，希望找到一個最佳的壓擴函數(shù)，使得在給定的失真下熵最佳。非均勻量化器的非線性程度可以由壓擴曲線c(x)表示，其動態(tài)范圍為[-xmax,xmax]、級數(shù)為L，當L足夠大時，c(xk)的斜率，即c(xk)在xk

處的導(dǎo)數(shù)c‘(xk)近似為均勻量化器和非均勻量化器的量化臺階之比：其中Δk=xi+1-xi

是第k個量化臺階46高碼率下ECSQ的性能在高碼率下（L足夠大），每個量化區(qū)間[xi,xi+1]內(nèi)p(x)近似為常數(shù)，且yi

取xi

和xi+1

的平均值，則每個量化區(qū)間內(nèi)的均方量化誤差為：總的均方量化誤差為：IntroductiontoDataCompressionbyKhalidSayood，p263當Δi

較小時，求和表示為積分47高碼率下ECSQ的性能同樣，在高碼率下（L足夠大），每個量化區(qū)間內(nèi)概率密度函數(shù)p(x)近似為常數(shù)，則量化器輸出電平為yi

的概率為：量化器輸出電平的熵：IntroductiontoDataCompressionbyKhalidSayood，p26748當Δi

較小時，高碼率下ECSQ的性能微分熵，近似為量化器輸入信號x

的熵H(X)IntroductiontoDataCompressionbyKhalidSayood，p26749高碼率下ECSQ的性能令則所以，則變成拉格朗日函數(shù)的極值問題：IntroductiontoDataCompressionbyKhalidSayood，p26750

所以如果使用邊界條件得到這就是均勻量化器所對應(yīng)的壓擴器特性，為線性所以，高碼率下，最優(yōu)量化器為均勻量化器將該壓擴函數(shù)的導(dǎo)數(shù)代入高碼率下ECSQ的性能51碼率為失真-碼率函數(shù)為是Shannon下界的，即高碼率的均勻ECSQ量化器的SNR與Shannon下界差1.53dB（對任何平滑pdf）高碼率下ECSQ的性能JPEG2000：ImageCompression，F(xiàn)undamentals，StandardsandPracticebyDavidS.Taubman，p10652相同碼率R下，ECSQ的失真比Lloyd-Max量化器更小高碼率下ECSQ的性能Gaussian信源的量化器均勻量化器+熵編碼53高碼率下ECSQ的性能Gaussian信源的量化器JPEG2000：ImageCompression，F(xiàn)undamentals，StandardsandPracticebyDavidS.Taubman，p10954高碼率、IID信源的Lloyd-Max量化器和熵約束量化器的MSE失真—碼率函數(shù)均可以表示為：縮放因子ε2

的數(shù)值均勻1Laplacian9/2=4.5gaussian√(3π)/2=2.721高碼率下ECSQ的性能ECSQ熵約束最佳量化器ECSQ是在給定H(Q)的條件下，求判決電平和輸出電平，使得均方量化誤差σd2為最小。在ECSQ量化器和熵編碼聯(lián)合優(yōu)化中，將熵H(Q)看成“碼率”，那么無論在失真約束下最小化碼率，還是在碼率約束下最小化失真，均勻量化都是或接近于最佳的。因此，在圖像和視頻壓縮標準中，都采用了均勻量化器和熵編碼聯(lián)合的方法。JPEG2000：ImageCompression，F(xiàn)undamentals，StandardsandPracticebyDavidS.Taubman，p108Lloyd-Max55自適應(yīng)量化器思想不是靜態(tài)方法，而是與真實數(shù)據(jù)的統(tǒng)計特性相適應(yīng)均值、方差、pdf前向自適應(yīng)(離線)將信源分塊分析塊的統(tǒng)計特性設(shè)置量化方案邊信道（Sidechannel）后向自適應(yīng)(在線)基于量化器輸出自適應(yīng)無需邊信道56前向自適應(yīng)量化器（FAQ）選擇塊大?。赫壑刑蠓直媛什粔?，不能抓住輸入的變化延遲增大太小需要傳輸更多的邊信息假設(shè)均值為0方差估計FAQ問題：需要緩存分析統(tǒng)計特性，造成延時邊信息的同步57例：語音量化16比特3比特定長碼失真較大前向自適應(yīng)量化器（FAQ）男聲“test”IntroductiontoDataCompressionbyKhalidSayood，24558例：語音量化（2）16比特3比特FAQ塊大?。?28個樣本標準方差進行8比特量化，并傳送給接收端失真較小紅色區(qū)域還有提升空間前向自適應(yīng)量化器（FAQ）59改進的前向自適應(yīng)量化器（FAQ）迄今為止，我們假設(shè)均勻pdf改進假設(shè)均勻pdf，但記錄每塊的最大/最小值例：Sena圖像

8×8塊每個像素3比特量化每個塊中邊信息最大值/最小值各用8bit表示，則每個像素平均為每個像素共：3.25bits/pixel和原始圖像幾乎難以區(qū)別對于高碼率，前向自適應(yīng)量化是個非常好的選擇原始圖像：8bits/pixel量化：3.25bits/pixel60后向自適應(yīng)量化器（BAQ）觀察解碼器只能看到量化器的輸出只能根據(jù)量化器輸出進行自適應(yīng)問題只根據(jù)輸出，如何減少不匹配信息如果知道pdf，這是可能的……耐心：觀察長時間的量化器輸出，推測是否發(fā)生了不匹配現(xiàn)象如果匹配，落入某區(qū)間的概率與預(yù)定的pdf一致，否則，發(fā)生了不匹配現(xiàn)象。失配時，如果步長比應(yīng)有的步長小，輸入落入外側(cè)區(qū)間的數(shù)目偏大；相反，輸入落入內(nèi)側(cè)區(qū)間的數(shù)目偏大。Jayant量化器不需要觀察長時間的量化器輸出，在觀察單個輸出后就可調(diào)整量化步長，Jayant稱之為“quantizationwithonewordmemory”。61嵌入式量化器動機：不同碼率、不同質(zhì)量的可伸縮（scalable）解碼隨著比特流的解碼，漸近地精化重構(gòu)數(shù)據(jù)對低帶寬有用是JPEG2000的一個關(guān)鍵特征嵌入式量化：低碼率量化器的區(qū)間被再分割，以產(chǎn)生更高碼率的量化器，即高碼率的量化器嵌入在低碼率量化器中。通常，只有其中一個量化器是最優(yōu)的(除了均勻量化外)?？梢酝ㄟ^截斷量化索引獲得較粗糙的量化EmbeddedscalarquantizersQ0,Q1andQ2,ofrateR=1,2,and3bits/sample62例1：均勻量化器嵌入式量化器63例2：Deadzonequantizer假設(shè)deadzone量化器的量化區(qū)間的索引用4個比特表示如果收到了所有4個比特步長為Δ如果只收到了前3個比特步長為2Δ如果只收到了前2個比特步長為4Δ嵌入式量化器6464例3：高斯分布的Lloy-Max量化器、2bit和3bit最優(yōu)量化器是非最優(yōu)的嵌入量化的性能損失嵌入式量化器65矢量量化VectorQuantization主要內(nèi)容基本思想標量量化的不足之處定長碼VQ的LBG算法變長碼VQ的CLG結(jié)構(gòu)化VQ樹結(jié)構(gòu)VQ（Tree-structuredVQ）格型量化（Latticequantization）網(wǎng)格編碼量化（Trelliscodedquantization,TCQ）IntroductiontoDataCompressionbyKhalidSayood66矢量量化矢量量化編碼是圖像、語音等編碼技術(shù)中采用的一種量化編碼方法。矢量量化編碼方法一般是有失真編碼方法。壓縮符號串比壓縮單個符號在理論上可產(chǎn)生更好的效果如圖像和聲音的相鄰數(shù)據(jù)項一般存在相關(guān)性矢量量化：量化時不是處理信源單個符號，而是一次處理一組符號（矢量）得到更好的壓縮性能：碼率/失真更小矢量量化編碼解碼框圖67矢量量化以圖像編碼為例查表搜索距離最近的碼字非對稱編碼：編碼：在輸入與碼本匹配過程中需大量計算解碼：只需查表68矢量量化——碼率碼書（codebook）中共有K個碼字（codeword），則表示碼字索引需log2K比特假設(shè)矢量大小為L個樣本，因此碼率（表示每個樣本所需比特）為例：對8比特256級的灰度圖像進行矢量編碼每個矢量大小為L=4×4，用K=1024個碼字的碼書對圖像進行矢量量化則碼率為R=[log2K]/L=10/16=0.63bpp壓縮比為：8:0.63=12.8:1可以通過對碼字索引采用熵編碼技術(shù)得到更高的壓縮比69矢量量化——失真采用均方誤差作為量化失真度量定義：碼書C，包含K個碼字矢量Yj輸入矢量X與碼字矢量Yj最近，量化輸出Yj定義為其中量化區(qū)域（判決邊界）：表示所有可以被Yj

量化的輸入矢量iff

當且僅當70矢量量化問題：為什么矢量量化(VQ)比標量量化（SQ）好？怎樣產(chǎn)生碼書？對每個輸入矢量，怎樣找到與其最匹配的碼字？標量量化效率可以繼續(xù)提升利用樣本之間的相關(guān)性即使不存在相關(guān)性，通過降低量化中存在的兩種誤差（噪聲）過載誤差（邊界處）顆粒誤差71SQ不足VQ優(yōu)勢優(yōu)勢1：相關(guān)性的利用。在相同的給定碼率下，矢量量化比標量量化具有更低的失真。例：考慮量化信源的兩個樣本（重量和身高）重量和身高各用3bit均勻量化，共6bit比特率：3比特/樣本每個樣本8個量化電平若對每個樣本采用均勻標量量化，則2-D樣本空間被分成64個長方形均勻區(qū)域（Voronoi區(qū)域）身高和體重的關(guān)系，在一定身高[40,80英寸]和重量[40,240磅]范圍內(nèi)各用3bit均勻量化。72若考慮二者之間的相關(guān)性（例如身高和體重），對x1、x2

一起量化，則輸出點數(shù)量一樣，但輸出點位于輸入的聚集區(qū)域。實際中，一個80英寸身高40磅體重，或者身高42英寸體重200磅的人，很少出現(xiàn)。因此，圖中的均勻量化效率不高。一個人的身高和體重是相關(guān)的，不再單獨量化，在同樣的量化比特數(shù)時，為輸入提供了更細致的量化。SQ不足VQ優(yōu)勢SQ不足VQ優(yōu)勢對于有記憶信源，樣本之間具有線性或非線性相關(guān)。在優(yōu)化的VQ設(shè)計中，把N維空間劃分為量化單元時，可以利用這些相關(guān)性。Gauss-Markov過程，相關(guān)系數(shù)ρ=0.9L=2二維矢量量化，采用熵約束矢量量化（ECVQ）的CLG算法（見后），CLG算法中Lagrange參數(shù)λ取不同的2個值。SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P14574SQ不足VQ優(yōu)勢對于有記憶信源，高碼率的矢量量化可以獲得相關(guān)增益。Gauss-Markov過程，不同的相關(guān)系數(shù)N維矢量量化視頻信號具有很強的相關(guān)性VQ具有更高的相關(guān)增益在視頻編碼中，如何更好地利用像素間的相關(guān)性，是最重要的之一實際中，標量量化和預(yù)測編碼或線性變換、熵編碼聯(lián)合，也可以利用信源的相關(guān)性。75優(yōu)勢2：空間填充SpaceFillingAdvantage分析表明，更高的N維標量量化最終把N維空間劃分成N維超矩形（間距的笛卡爾乘積）。但對于矢量量化，我們有很大的自由去選擇量化單元的形狀。獲得的編碼增益叫SpaceFillingAdvantage.例：考慮Laplacian分布的8量化電平的一維的均勻標量量化器，已知△=0.7309，同一個輸入落入不同量化區(qū)間的概率是不同的，例如：直接擴展到x1、x2

軸，得到2D輸入的量化器當量化器有兩個輸入x1、x2

時，構(gòu)成如圖的兩維量化器，圓點表示兩維樣本的量化輸出。各區(qū)間的概率不同，例如最右上區(qū)域的概率：SQ不足VQ優(yōu)勢IntroductiontoDataCompressionbyKhalidSayood76上述最右上區(qū)域概率非常小，幾乎不可能發(fā)生，簡單地將它放在別處，可能更有用。若將其移到概率最大區(qū)域—原點附近，得到修正的量化器SQ不足VQ優(yōu)勢但如果對標量量化器做類似操作，將3.5Δ移至原點，則兩種情況下信源的均方值一樣，SNR增加了，意味著均方誤差減少。這種SNR提高是否有意義取決于特定應(yīng)用，但重要的是通過微小的改變，得到了正面的效果。改變了中心位置的量化圖案，不再是均勻量化了。對原來是非均勻的量化器做同樣的處理，會得到類似的結(jié)果。矢量量化修正的矢量量化77另一種修正方案，不改變點的位置，而是保留等概線|x1|+|x2|=5Δ

內(nèi)的點：60個點沒有改變等概線內(nèi)部的量化形狀，只改變了量化器的外部邊界。去掉原來8×8空間64個點中不滿足條件的12個點(圓形標注)增大過載概率增加8個（方形標注），不是原來8×8=

64個點里面的減少過載概率減少的負載概率

>增大的負載概率

總過載概率減小SNR:11.44dB

12.22dB這樣獲得的好處稱為邊界增益矢量維數(shù)增加，過載噪聲進一步減少。塔式/球形VQ的原型SQ不足VQ優(yōu)勢787878SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P143例：單位方差的高斯

iid

信源的二維矢量量化，碼率R=2bit/樣本LBG算法的第8和49次迭代的量化結(jié)果：8次迭代后，矢量量化和標量量化的SNR近似相等（9.3dB），因為矢量量化單元近似為矩形，標量量化器也可構(gòu)造出來49次迭代后，矢量量化單元形狀在中心位置近似為正六邊形，VQ

SNR增加到了9.67dB，但標量量化無法產(chǎn)生這樣的圖案更高的碼率，收斂趨于更完美的正六邊形。SQ：標量量化SQ不足VQ優(yōu)勢例：單位方差的均勻分布的iid

信源的二維矢量量化，A=10標量量化：K=10，碼率（熵）為3.32bit/樣本，SNR為19.98VQ的LBG算法：L=2，K=100時，達到上述碼率3.32bit/樣本最終，VQ聚類趨于正六邊形，SNR也提高到了20.08dB。由于單元密集，獲得的空間填充增益與輸入信號的分布或統(tǒng)計相關(guān)性無關(guān)。

空間填充增益的上界是1.53dB，如果矢量量化器的維數(shù)趨于無窮，對高碼率VQ，可以漸進達到此增益上限。797979SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P143SQ不足VQ優(yōu)勢8080優(yōu)勢3：分布形狀ShapeAdvantage優(yōu)化的VQ量化單元將更適應(yīng)于信源概率密度分布下圖顯示了高斯和拉普拉斯iid信源的VQ維數(shù)和失真之間的關(guān)系。在實際中，可以利用標量量化器和熵編碼的聯(lián)合，也可以獲得shapeadvantage。在上述三個優(yōu)勢種，空間填充是VQ獨有的，相關(guān)和分布形狀是SQ和VQ都可以利用的，只是SQ需要和其它技術(shù)結(jié)合。

SQ不足VQ優(yōu)勢81優(yōu)勢4：顆粒噪聲顆粒失真標量量化：由量化步長決定矢量量化：由量化區(qū)域大小和形狀決定立方體區(qū)域vs.球形區(qū)域體積相同時，在所有的形狀中，球形區(qū)域的最大顆粒誤差最小體積相同時，在所有的形狀中，球形量化區(qū)域的平均顆粒誤差最小面積：1邊長：1最大誤差：面積：1半徑=最大誤差=SQ不足VQ優(yōu)勢參見DavidS.Taubman《JPEG2000：ImageCompression，F(xiàn)undamentals，StandardsandPractice》，p117，3.4.1節(jié)82定長碼的矢量量化—LBG算法對于定長碼的矢量量化器，可以將相應(yīng)的定長碼的標量量化的Lloyd-Max算法推廣到矢量量化，所以亦稱為推廣的Lloyd算法(GeneralizedLloydAlgorithm,GLA)[Linde,Buzo,Gray,1980]，亦稱為LBG算法給定訓(xùn)練集：收集的訓(xùn)練集需有代表性碼字(量化輸出電平)判決邊界訓(xùn)練矢量量化區(qū)域QuantizationCell83定長碼的標量量化的Lloyd-Max算法初始化所有的量化電平更新所有的判決邊界：計算MSE：如果(D(j-1)-D(j))/D(j-1)<ε，停止；否則k=k+1，更新所有的yj(k)

：轉(zhuǎn)到第2步84定長碼的VQ的LBG算法初始化所有的量化電平更新所有的判決邊界：計算MSE：如果(D(j-1)-D(j))/D(j-1)<ε，停止；否則

k=k+1，更新所有的Yj(k)

：轉(zhuǎn)到第2步這個算法非常不實用，因為計算失真需要積分，以及質(zhì)心位于n維矢量的畸形區(qū)域。通常，這些積分計算非常困難，使得它更多的是學(xué)術(shù)興趣。更實際的算法是帶訓(xùn)練集的LBG算法，用求和代替積分。85LBG算法（帶訓(xùn)練集）給定訓(xùn)練集T={X1,X2,…,XN}，初始化所有的量化電平更新所有的量化區(qū)域：計算訓(xùn)練矢量和量化電平之間的平均失真MSE：如果(D(j-1)-D(j))/D(j-1)<ε，停止；否則

k=k+1，更新所有的Yj(k)

：同聚類中的K-means聚類（假設(shè)沒有量化區(qū)域是空類）86舉例LBG1HeightWeight721806512059119641506516257887217544416211460110569170172HeightWeight14550245117375117480180LBG算法訓(xùn)練樣本集初始碼書87LBG算法最后的矢量量化器一次迭代后的矢量量化器失真：60.1788LBG算法SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P138舉例LBG2：高斯

iid信源，單位方差二維矢量量化器，即L=2個樣本，K=16個碼字，相當于每個樣本2

bit（標量）R=(log2K)/L=2LBG算法的初始化、第8和49次迭代的量化結(jié)果8989LBG算法SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P138相同碼率(R=2bit/樣本)的標量量化和矢量量化性能比較：8次迭代后，兩者失真近似（9.3dB），因為矢量量化單元近似為矩形，標量量化器也可構(gòu)造出來49次迭代后，矢量量化單元形狀，標量量化器是無法產(chǎn)生的，因此矢量量化SNR增加到了9.67dB。比SQ高0.37dB。SQ：標量量化9090LBG算法舉例LBG3：高斯iid

信源，單位方差，二維矢量量化器，即L=2個樣本，K=256個碼字，相當于每個樣本4

bit（標量）R=(log2K)/L=4LBG算法的第49次迭代的量化單元和重建矢量量化失真：49次迭代后，標量量化SNR20.64dB，比VQ低0.9dB。表明更高的碼率R，VQ比SQ有更高的SNR增益。919191LBG算法舉例LBG4：拉普拉斯iid

信源，單位方差，二維矢量量化器，即L=2個樣本K=16，R=2bit/樣本，VQSNR=8.87dB，比相同碼率的SQ高1.32dBK=256，R=4bit/樣本，VQSNR=19.4dB，比SQ高1.84dB。92LBG算法優(yōu)化過程能保證收斂，但可能收斂于局部極小值非常依賴于初始碼書的選取初始碼書的選取隨機選擇：重復(fù)多次，取失真最小的結(jié)果分裂：從一個類開始，每次將失真最大/數(shù)量最多的類分裂成兩個合并：從N個類開始，每次將兩個失真最小的類合并空類的問題：去掉空類，并將失真最大/數(shù)量最多的類分裂成兩個93LBG用于圖像壓縮每塊大小為L=4×4，用K=16,64,256,1024個碼字的碼書對圖像進行矢量量化碼率：Sinan圖像訓(xùn)練得到碼書原始圖像94LBG用于圖像壓縮傳輸碼書（overhead）的bit消耗：K=1024,overhead=2,為編碼內(nèi)容碼率(0.625)的3倍用通用碼書，無需傳碼書，但質(zhì)量可能稍差收集代表性的訓(xùn)練集CodebookSizeBitsforaCodewordBits/PixelCompressionRatioOverheadinBits/Pixel1640.2532:10.031256460.37521.33:10.12525680.316:10.51024100.62512.8:12.095LBG算法的缺陷碼字中缺少結(jié)構(gòu)編碼復(fù)雜性高：需要全搜索存儲要求高，碼書指數(shù)增長例：目標碼率：R比特/樣本每個矢量包含L個樣本(如4×4像素一起編碼，則L=16)碼字索引：RL比特碼書中可能的碼字有2RL

個碼字例：R=0.25比特/樣本，L=16個樣本/矢量每個碼字索引需RL=4比特碼書中共有24=16個詞條R=2比特/樣本，L=16個樣本/矢量每個碼字索引需RL=32比特碼書中共有232=40億個詞條在高碼率下，VQ不太實用熵編碼的矢量量化熵約束矢量量化

entropy-constrainedvectorquantizer，ECVQ為熵編碼矢量量化，擴展了熵約束的Lloyd-Max算法（ECSQ），稱為

Chou-Lookabaugh-Gray(CLG)[1989]Lagrangian代價函數(shù)：給定碼率下使得失真D最小平均碼字長度作為熵H，即類似于ECSQ，ECVQ判決邊界和量化電平的必要條件96P.A.Chou,T.Lookabaugh,R.M.Gray,“Entropy-constrainedvectorquantization,”IEEETrans.SignalProcessing,vol.37,no.1,pp.31-42,Jan198997ECVQ的CLG算法對于足夠大的訓(xùn)練集{xn}和給定的拉格朗日參數(shù)λ初始化所有的量化電平更新所有的判決邊界：更新量化電平計算平均碼長計算MSE：如果(D(j-1)-D(j))/D(j-1)<ε，停止；否則

k=k+1，轉(zhuǎn)到第2步98989898ECVQ的CLG算法舉例ECVQCLG：高斯和拉普拉斯iid

信源，單位方差，二維矢量量化器，即L=2個樣本，作為熵的平均碼率為R=2bit/樣本高斯分布，ECVQ的SNR比相同碼率的ECSQ高0.26dB拉普拉斯分布，ECVQ的SNR比ECSQ高0.37dB高斯拉普拉斯9999999999性能比較不同維數(shù)的CLG和標量量化的性能比較Gauss-Markov信源，相關(guān)系數(shù)ρ=0.9維數(shù)L=2,5,10和100的VQ標注為“VQK=L(e)”L=100時，理論上VQ性能已非常逼近R(D)限。事實上，當維數(shù)L趨于無窮時，VQ漸進達到率失真界限。SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P147100100100100100100性能比較矢量量化可以解釋為一個最通用的有時真源編碼系統(tǒng)。每個源編碼系統(tǒng)可映射為一個矢量量化。盡管具有很好的編碼效率，但矢量量化很少用于視頻編碼主要原因是復(fù)雜一是巨大的碼書存儲，特別是當視頻編解碼器需要不同碼率時，這更成為問題；二是計算復(fù)雜，相對于標量量化，要想獲得一個率失真下最好的重建矢量，需要大量的計算。減少存儲和計算復(fù)雜度的方法是利用結(jié)構(gòu)化約束的矢量量化器，例如Tree-structuredVQ，TransformVQ，MultistageVQ，Shape-gainVQ，LatticecodebookVQ，PredictiveVQ。實際中，視頻編解碼更多是采用中平型均勻量化器，然后結(jié)合熵編碼和線性預(yù)測或變換編碼，去利用信源分布形狀和統(tǒng)計相關(guān)性。而矢量量化，包括哪些結(jié)構(gòu)化的VQ，相對于獲得的好處而言，還是太復(fù)雜了。101改進的矢量量化樹結(jié)構(gòu)（Tree-structured）矢量量化搜索快，但存儲量大格型矢量量化LatticeVQ網(wǎng)格編碼矢量量化（TrellisCodedVQ）102樹結(jié)構(gòu)VQ在碼書組織中引入結(jié)構(gòu)，快速決定哪個部分包含所需輸出矢量（重構(gòu)電平）通過搜索一系列小碼書降低搜索復(fù)雜性，復(fù)雜性線性增長logK但需要更多存儲（約兩倍）：測試矢量(testvector)103樹結(jié)構(gòu)VQ可以通過Linde等提出的分裂方法實現(xiàn)首先將所有訓(xùn)練集視為一個類，計算類中心（均值）作為測試矢量和輸出水平將一個類分裂成兩個子類，子類中心為將原父中心的均值分別+/-一個擾動LBG算法中也是采用類似分裂方法解決初值問題其他：剪枝碼書減小碼率減小但失真可能增大104格型VQ在前面的討論中，我們知道球形量化區(qū)域是最佳的（顆粒噪聲最?。┑蛐翁畛洌╰ile）要么有重疊，要么有空洞需要找到某種高效的量化區(qū)域結(jié)構(gòu)化碼字，以近似球體并填滿球體結(jié)構(gòu)化：省存儲/計算量小有規(guī)律格型Lattice球體：顆粒誤差最小Lattice：令為L維線性獨立的L維矢量，集合中為整數(shù)，則集合為一個lattice105格型VQLattice量化器：將lattice點集的子集作為VQ的輸出點最近鄰LatticeVQ：Λ的基本量化區(qū)域：0

附近的單元106舉例：D2lattice性質(zhì)：對所有的lattice點，菱形量化區(qū)域格型VQ107舉例：A2lattice:六邊形量化區(qū)域：2D上最佳格型VQ108格型VQ的性質(zhì)不必存儲碼字比LBG算法更容易找到最近鄰但是，Lattice量化器沒有了LBG聚類的性質(zhì)設(shè)計準則：最小化顆粒誤差對2-DVQ，六邊形lattice是最佳的對Gaussian信源，熵編碼的lattice量化器離D(R)邊界有1.36dB109TrellisCoded量化（TCQ）計算效率高的矢量量化中等計算復(fù)雜度理論優(yōu)勢：對任何平滑pdf，熵編碼的TCQ能在任何碼率下達到D(R)函數(shù)的0.2dB以內(nèi)（性能超過24維以下的最佳lattice量化）基于TrellisCodedModulation(TCM)TCQ在JPEG2000II中用到110Trellis編碼網(wǎng)格(trellis)是一個有限狀態(tài)機隨時間的進化例：一個帶有二進制I/O的4狀態(tài)的有限狀態(tài)機T0和t1為移位寄存器狀態(tài)表示為t1t04個狀態(tài)狀態(tài)轉(zhuǎn)換圖u/z1z0111Trellis編碼在狀態(tài)轉(zhuǎn)換圖中加入時間因素112Trellis編碼