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

門愛東教授

第5講

率失真理論

量化

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

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

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

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

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

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

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

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

，設(shè)計(jì)一個(gè)

L

個(gè)輸出電平的量化器，以均方誤差作為評(píng)判標(biāo)準(zhǔn)，使其最小：結(jié)果：Lloyd-Max最佳均方量化器（MMSE，Lloyd1957;Max1960）L-1

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

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

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

及yi

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

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

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

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

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

倍。當(dāng)輸入信號(hào)的均方差σx2=1時(shí)，f(B)

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

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

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

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

的求解是一個(gè)相互依賴的過程。問題：如何同時(shí)計(jì)算最佳的xi

和yi

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

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

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

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

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

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

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

為均勻分布、高斯分布、拉普拉斯或雷利分布，且均值E[x]=0，標(biāo)準(zhǔn)方差σx

=1時(shí)，得到最佳量化器量化電平y(tǒng)k(k=1,2,.,L)標(biāo)準(zhǔn)表。問題：當(dāng)隨機(jī)變量x’

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

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

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

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

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

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

和xi

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

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

均勻量化誤差與輸入信號(hào)的關(guān)系如圖。處在均勻量化范圍內(nèi)的量化誤差大小為[-0.5△,+0.5△]，稱之為顆粒失真，或者顆粒噪聲，表示為Dgran顆粒失真和過載失真26平均顆粒失真：代入得顆粒失真和過載失真27若輸入信號(hào)x先經(jīng)過歸一化處理，使其范圍在x∈[0,1]，即b-a=1，則上面等式成為：信噪比為：說明：量化級(jí)數(shù)每增加1bit，則步長(zhǎng)減小一半，均方量化噪聲減為?，SNR增加6dB。人眼視覺對(duì)圖像中變化不大、較為均勻的區(qū)域（低頻）比較敏感，而對(duì)細(xì)節(jié)（高頻）部分的敏感程度相對(duì)較弱。因此，通常對(duì)圖像信號(hào)中的低頻部分采用較大的量化級(jí)數(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顆粒失真和過載失真當(dāng)分布不再是均勻分布時(shí)，需要考慮信源的pdf不同分布的信源，均勻量化時(shí)的SNR和最優(yōu)步長(zhǎng)30輸入信號(hào)幅度為無界(-∞,∞)時(shí)在兩個(gè)區(qū)間（-∞,x1]和[xL-1,∞)產(chǎn)生過載失真

Dol

（OverloadNoise）；在其它的

L-2

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

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

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

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

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

則在信號(hào)x

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

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

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

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

利用近似條件

對(duì)

yi

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

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

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

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

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

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

Entropy-constrainedScalarquantizer,

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

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

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

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

在最小化

J(λ)中λ

的作用較大的λ

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

，使得H(Q)=R

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

：更新pi

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

定長(zhǎng)編碼：熵約束標(biāo)量量化器SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.SchwarzP121-12342所有的實(shí)驗(yàn)中使用相同Lagrange乘子λ初始化A：初始化為15個(gè)均勻區(qū)間

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

在迭代過程逐步減少

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

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

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

在迭代過程逐步減少

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

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

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

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

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

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

取xi

和xi+1

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

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

的概率為：量化器輸出電平的熵：IntroductiontoDataCompressionbyKhalidSayood，p26748當(dāng)Δi

較小時(shí)，高碼率下ECSQ的性能微分熵，近似為量化器輸入信號(hào)x

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

所以如果使用邊界條件得到這就是均勻量化器所對(duì)應(yīng)的壓擴(kuò)器特性，為線性所以，高碼率下，最優(yōu)量化器為均勻量化器將該壓擴(kuò)函數(shù)的導(dǎo)數(shù)代入高碼率下ECSQ的性能51碼率為失真-碼率函數(shù)為是Shannon下界的，即高碼率的均勻ECSQ量化器的SNR與Shannon下界差1.53dB（對(duì)任何平滑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)看成“碼率”，那么無論在失真約束下最小化碼率，還是在碼率約束下最小化失真，均勻量化都是或接近于最佳的。因此，在圖像和視頻壓縮標(biāo)準(zhǔn)中，都采用了均勻量化器和熵編碼聯(lián)合的方法。JPEG2000：ImageCompression，F(xiàn)undamentals，StandardsandPracticebyDavidS.Taubman，p108Lloyd-Max55自適應(yīng)量化器思想不是靜態(tài)方法，而是與真實(shí)數(shù)據(jù)的統(tǒng)計(jì)特性相適應(yīng)均值、方差、pdf前向自適應(yīng)(離線)將信源分塊分析塊的統(tǒng)計(jì)特性設(shè)置量化方案邊信道（Sidechannel）后向自適應(yīng)(在線)基于量化器輸出自適應(yīng)無需邊信道56前向自適應(yīng)量化器（FAQ）選擇塊大?。赫壑刑蠓直媛什粔?，不能抓住輸入的變化延遲增大太小需要傳輸更多的邊信息假設(shè)均值為0方差估計(jì)FAQ問題：需要緩存分析統(tǒng)計(jì)特性，造成延時(shí)邊信息的同步57例：語音量化16比特3比特定長(zhǎng)碼失真較大前向自適應(yīng)量化器（FAQ）男聲“test”IntroductiontoDataCompressionbyKhalidSayood，24558例：語音量化（2）16比特3比特FAQ塊大?。?28個(gè)樣本標(biāo)準(zhǔn)方差進(jìn)行8比特量化，并傳送給接收端失真較小紅色區(qū)域還有提升空間前向自適應(yīng)量化器（FAQ）59改進(jìn)的前向自適應(yīng)量化器（FAQ）迄今為止，我們假設(shè)均勻pdf改進(jìn)假設(shè)均勻pdf，但記錄每塊的最大/最小值例：Sena圖像

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

量化的輸入矢量iff

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

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

軸，得到2D輸入的量化器當(dāng)量化器有兩個(gè)輸入x1、x2

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

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

64個(gè)點(diǎn)里面的減少過載概率減少的負(fù)載概率

>增大的負(fù)載概率

總過載概率減小SNR:11.44dB

12.22dB這樣獲得的好處稱為邊界增益矢量維數(shù)增加，過載噪聲進(jìn)一步減少。塔式/球形VQ的原型SQ不足VQ優(yōu)勢(shì)787878SourceCoding：PartIofFundamentalsofSourceandVideoCoding,FoundationsandTrendsinSignalProcessingbyT.Wiegand,H.Schwarz，P143例：?jiǎn)挝环讲畹母咚?/p>

iid

信源的二維矢量量化，碼率R=2bit/樣本LBG算法的第8和49次迭代的量化結(jié)果：8次迭代后，矢量量化和標(biāo)量量化的SNR近似相等（9.3dB），因?yàn)槭噶苛炕瘑卧茷榫匦?，?biāo)量量化器也可構(gòu)造出來49次迭代后，矢量量化單元形狀在中心位置近似為正六邊形，VQ

SNR增加到了9.67dB，但標(biāo)量量化無法產(chǎn)生這樣的圖案更高的碼率，收斂趨于更完美的正六邊形。SQ：標(biāo)量量化SQ不足VQ優(yōu)勢(shì)例：?jiǎn)挝环讲畹木鶆蚍植嫉膇id

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

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

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

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

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

：轉(zhuǎn)到第2步這個(gè)算法非常不實(shí)用，因?yàn)橛?jì)算失真需要積分，以及質(zhì)心位于n維矢量的畸形區(qū)域。通常，這些積分計(jì)算非常困難，使得它更多的是學(xué)術(shù)興趣。更實(shí)際的算法是帶訓(xùn)練集的LBG算法，用求和代替積分。85LBG算法（帶訓(xùn)練集）給定訓(xùn)練集T={X1,X2,…,XN}，初始化所有的量化電平更新所有的量化區(qū)域：計(jì)算訓(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個(gè)樣本，K=16個(gè)碼字，相當(dāng)于每個(gè)樣本2

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

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

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

信源，單位方差，二維矢量量化器，即L=2個(gè)樣本K=16，R=2bit/樣本，VQSNR=8.87dB，比相同碼率的SQ高1.32dBK=256，R=4bit/樣本，VQSNR=19.4dB，比SQ高1.84dB。92LBG算法優(yōu)化過程能保證收斂，但可能收斂于局部極小值非常依賴于初始碼書的選取初始碼書的選取隨機(jī)選擇：重復(fù)多次，取失真最小的結(jié)果分裂：從一個(gè)類開始，每次將失真最大/數(shù)量最多的類分裂成兩個(gè)合并：從N個(gè)類開始，每次將兩個(gè)失真最小的類合并空類的問題：去掉空類，并將失真最大/數(shù)量最多的類分裂成兩個(gè)93LBG用于圖像壓縮每塊大小為L(zhǎng)=4×4，用K=16,64,256,1024個(gè)碼字的碼書對(duì)圖像進(jìn)行矢量量化碼率：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ù)雜性高：需要全搜索存儲(chǔ)要求高，碼書指數(shù)增長(zhǎng)例：目標(biāo)碼率：R比特/樣本每個(gè)矢量包含L個(gè)樣本(如4×4像素一起編碼，則L=16)碼字索引：RL比特碼書中可能的碼字有2RL

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

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

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

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

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

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