門愛東教授

menad@第8講變換編碼TransformCoding2內(nèi)容提要Outline正交變換正交展開可分離酉變換二維圖像正交分解與基圖像酉變換的特性能量保持與旋轉(zhuǎn)能量集中與去相關作用K-L變換DCT變換定義DCT系數(shù)的量化和比特分配DCT失真DCT的快速算法DCT變換與DFT變換的關系33正交變換變換編碼是通過去除空間相關性來壓縮圖像及視頻碼率的一個有效方法。通過變換編碼，將空間域的像素點變換為特定變換域的變換系數(shù)，以實現(xiàn)去相關和能量集中。本章介紹變換編碼中的正交變換。首先以一維離散時間信號的展開與塊正交變換為例，介紹與空間及信號分解有關的數(shù)學知識，然后講述數(shù)字圖像處理中用到的二維正交變換及其特性。二維正交變換有多種正交基可以選擇，如離散傅立葉變換（DFT）、離散余弦變換（DCT）、離散正弦變換（DST）、沃爾什（Walsh）變換、哈達瑪（Hadamard）變換以及哈爾（Haar）變換等。重點介紹實際圖像壓縮中常用的DCT，在那之前講述最高編碼增益意義下的最佳變換KL（Karhunen－Loève）變換。4變換編碼的系統(tǒng)構(gòu)成信源序列變換量化掃描存儲和傳輸反量化反變換重建序列塊變換編碼的原則正交變換的特性K-L變換離散余弦變換變換系數(shù)比特分配門限設置典型的塊失真DCT的快速算法變換編碼(TransformCoding)是一種函數(shù)變換，從一個信號域變換到另一個信號域，將信源輸出分解/變換為其組成部分，然后根據(jù)每個成分的特性分別進行編碼，去除視頻信號的空間冗余，使能量集中。5變換編碼6酉（Unitary）變換概念線性變換v=Au，系數(shù)矩陣A稱為此變換的基矩陣如果A是一個酉矩陣，則：且其中，*表示對A的每個元素取共軛復數(shù)，T

表示轉(zhuǎn)置如果A是酉矩陣，且所有元素都是實數(shù)，則它是一個正交矩陣，且滿足且上式表明：當i=j時，內(nèi)積為1；否則內(nèi)積為0，所以，A的各行是一組正交向量任何兩個酉變換之間的差別在于基函數(shù)（即A的行向量）的選擇。正交矩陣是酉矩陣，但酉矩陣不需要是正交矩陣。7正交矩陣的特點正交矩陣的特點每一行元素的平方和等于1兩個不同行的對應元素乘積之和等于零上述兩條對于列也成立例如第一行第二行乘積用前面的正交矩陣定義計算上述例子y2x2y1x18正交變換正交變換u(m,n)表示N×N的原始圖象v(k,l)表示變換系數(shù)akl(m,n)是離散正交變換基函數(shù)正變換(ForwardTransform)矩陣表示：N×N輸入信號塊，向量排列N2×N2變換矩陣N×N變換系數(shù)線性：v(k,l)描述為“基函數(shù)(BasisFunction)”的線性組合9基函數(shù)滿足正交完備條件正交條件—必要性正交變換完備條件—充分性10正交展開截尾，其誤差平方和最小，不同基最小值不同正交變換

前述的正交完備性條件將保證：當P=Q=N

時，截尾誤差為零

其中，誤差平方和11可分離的正交變換酉變換基函數(shù)分解表示為：12可分離的正交變換可分離的酉變換的正變換可分離的酉變換的反變換13可分離的正交變換可分離的酉變換的矩陣表示。N×N正交變換矩陣N×N變換系數(shù)反變換重要的實際意義：用2個N×N矩陣乘法代替了1個1×N2

矢量和N2×N2

矩陣的乘法，實現(xiàn)變換。使其復雜性(乘法次數(shù)）從O(N4)減少為O(N3)。N×N輸入信號14例如快速傅里葉變換根據(jù)DFT公式，直接計算N點一維傅里葉變換需要N2次復數(shù)乘法，N(N-1)≈N2次復數(shù)加法運算?？焖俑道锶~變換只需要Nlog2N

次加法，0.5Nlog2N

次乘法。例如M=1024，直接傅里葉變換需要大約106次操作，快速傅里葉變換只需要104次操作。2D-FFT計算量15可分離的正交變換二維變換通過2個一維變換實現(xiàn)沿著信號塊的行、列方向進行；先對行進行運算，再對列進行運算，從而達到快速的目的。NNN×N象素塊行方向N-變換列方向N-變換xAxAxAT16正交基分解：基圖象基圖象：通過對只含有一個非零元素(令其值為1）的變換系數(shù)矩陣進行反變換而得到。共有N2

個這樣的矩陣，產(chǎn)生N2

幅基圖象，設其中的一個變換系數(shù)矩陣為vp,q=|δk-p,l-q|，其中k和l分別是行和列的下標，p和q是表明非零元素位置的整數(shù)，則通過反變換求得基圖象。對于一個可分離的酉變換，每幅基圖象就是變換矩陣某兩行的外積（矢量積）[A*kl]表示基圖象a*k

表示[A*kl]的第k行a*l

表示[A*kl]的第l列17正交基分解：基圖象

應用：信息傳送原理發(fā)端分解：傳送v(k,l)，即將信號向量分解成它的各個基圖象，變換系數(shù)則規(guī)定了原信號中各基圖象所占的數(shù)量。如果一個信號，或其一部分可以近似地匹配上某一基函數(shù)，則在變換后，會產(chǎn)生一個對應于那個基函數(shù)的較大的變換系數(shù)。由于基函數(shù)是正交的，則這個信號對應于其它的基函數(shù)將產(chǎn)生較少的系數(shù)。收端合成：通過將一組被適當加權(quán)的基圖象求和而重構(gòu)圖象，用上面的式子合成。變換系數(shù)就是其對應的基圖象在求和時所乘的加權(quán)系數(shù)。

舉例說明以上概念：給定正交矩陣A和圖象矩陣U：變換系數(shù)：反變換為：18正交基分解

基圖象：

分解：

合成：19酉變換特性：能量保持與旋轉(zhuǎn)酉變換信號能量不變——U矢量長度在N維空間中不變酉變換——在N維空間簡單地旋轉(zhuǎn)U矢量酉變換是基坐標的旋轉(zhuǎn)，V分量是U在在新基坐標中的投影。1-D2-D20酉變換特性：能量集中與變換系數(shù)方差酉變換：能量轉(zhuǎn)到少數(shù)系數(shù)上，總能量不變

變換前后平均能量相等：μu、Ru

分別表示U矢量的均值和協(xié)方差RV

矩陣對角線元素給出變換系數(shù)方差:最后得：矩陣的跡，矩陣對角線上元素的總和。21酉變換特性：去相關U變換

輸入矢量U的相關RU

變換系數(shù)V的相關RV

（非對角系數(shù)變?。?/p>

酉變換的特性舉例：能量集中與去相關設其酉變換：ρ表示u(0)和u(1)的相關性22酉變換特性：去相關總能量2σ2

不變，但v(0)上的能量大于v(1)的，如ρ=0.95，則91.1%的總能量集中在v(0)上。

從RU

可見：即總能量相等的分布在u(0)及u(1)上

從RV

可見：

能量集中方面

V的協(xié)方差：23酉變換特性：去相關當ρ=0.95，說明：97.5%的能量集中在V(0)ρV（0,1)=0，說明：V(0)與V(1)不相關

相關方面：u(0)與u(1)間相關為ρ；v(0)與v(1)間相關為：若ρ=0.95，則ρV=0.83<ρ，變換系數(shù)之間的相關性減弱。

變換矩陣的影響：若則酉變換特性：編碼增益變量編碼增益增益與系數(shù)方差的集中程度有關若每個系數(shù)的方差相等，則沒有增益24幾何均值算術均值25變換編碼的選擇原則變換編碼的種類K-L變換KLT離散傅立葉變換DFT離散正弦變換DST離散余弦變換DCT哈達瑪變換HadamardWalsh變換Haar變換Slant變換小波變換Wavelet去相關，能量集中（例如，KLT、DCT、Wavelat）計算復雜度低26變換編碼的比較27變換編碼的比較28K-L變換（KLT）Karhunen–LoèveTransform(卡胡南-列夫變換)亦稱為HotellingTransform，Hottelling于1933年用于數(shù)據(jù)去相關；Karhunen、

Loève分別于1947、48年用于連續(xù)函數(shù)分析；Kramer和Mathews、Huang和Schultheiss分別于1956年、1963年用于數(shù)據(jù)壓縮（變換編碼）在統(tǒng)計分析中，稱為主成份分析（PrincipalComponentsAnalysis，PCA）29K-L變換（KLT）KLT變換產(chǎn)生去相關的變換系數(shù)KLT基函數(shù)是輸入信號協(xié)方差矩陣的特征向量，因此，它是以統(tǒng)計特性為基礎的，也稱為特征向量變換。最優(yōu)的正交變換：特征向量矩陣指向數(shù)據(jù)變化最大的方向，能夠達到最優(yōu)的能量集中。缺點：計算過程復雜，變換速度慢。KLT依賴信號統(tǒng)計特性，但很難實時計算視頻的統(tǒng)計特性；KLT基函數(shù)不是固定的，是隨圖像內(nèi)容改變的；KLT對圖象塊是不可分離；變換矩陣不能分解為稀疏矩陣。30矩陣的特征值和特征向量特征值：對于一個N×N的矩陣A，有N個標量λk，滿足：則λk稱為矩陣A的一組特征值（唯一的）。特征值定義沒有規(guī)定λk

的順序，但一般按幅值由大到小排序，即|λk|≥|λk

＋1|.每個特征值可以認為是這樣的一些數(shù)：當矩陣的每個對角元素都減去它時，矩陣將變?yōu)槠娈惥仃?。特征向量定義：

若N×1的向量φk

滿足下式：

則稱φk為A的特征向量。一共有N組這樣的向量，每組對應于某一個特征值λk。如果A是對稱矩陣，那么λk也是實數(shù)。31矩陣的特征值和特征向量求法：求A的特征方程求得A的特征值λk：λ1=1，λ2=4。當λ1=1時，對應的特征向量應滿足方程：其基礎解系為：ξ1=(-2，1)T，因此特征值λ1=1對應的特征向量

φ1

為k1ξ1（k1

為不等于0的常數(shù)）32矩陣的特征值和特征向量當λ2=4時，對應的特征向量應滿足方程：其基礎解系為：ξ2=(1，1)T，因此特征值λ2=4對應的特征向量φ2

為k2ξ2（k2

為不等于0的常數(shù)）33協(xié)方差矩陣L個向量集合u中，平均向量值為：協(xié)方差矩陣為：

式中平均向量mu

是N2

維向量；協(xié)方差矩陣Ru

是N2×N2

的方陣。協(xié)方差矩陣是實對稱的，對角元素是單個隨機變量的方差，非對角元素是它們的協(xié)方差。34協(xié)方差矩陣Ru

的特征向量求出協(xié)方差矩陣Ru

的特征值λi和對應的特征向量φi，i=1,2,…,N2

，并將特征值按減序排列。特征值λ1

對應的特征向量φ1:特征值λ2

對應的特征向量φ2:特征值λi

對應的特征向量φi:依此類推，特征值λN2

對應的特征向量φN2:35KLT變換的基核矩陣和定義協(xié)方差矩陣Ru

的特征向量可以構(gòu)成一個N2×N2

的矩陣Φ，Φ的共軛轉(zhuǎn)置Φ*T

稱K-L變換的核矩陣

KLT變換的定義：正變換反變換K-L變換基核是隨信號而變化的，不是固定的——自適應的。變換過程為：圖像隨機變量u→協(xié)方差矩陣Ru→K-L基核矢量Φ*T。事實上，在線性代數(shù)中已經(jīng)學過，K-L變換基核的求法就是先求出圖象的協(xié)方差矩陣R

的特征值，然后求出特征向量，從而得到基核。中心化后圖象向量36KLT變換的特征－去相關去相關——最佳的變換編碼KLT變換系數(shù){v(k),k=0,1,….,N-1}是不相關的，而且具有零均值，即：證明：協(xié)方差矩陣37KLT變換的特征－去相關經(jīng)過KLT變換后，所得的變換系數(shù)v是一個平均向量為零的向量集，其坐標原點移到中心位置。將mv=0代入Rv

表達式：Φ*T

矩陣由協(xié)方差矩陣Ru

的特征向量φi

的轉(zhuǎn)置構(gòu)成，即38KLT變換的特征－去相關由于Φ矩陣是正交矩陣，所以ΦΦT=I同時，矩陣Ru

與其特征向量φi

應符合以下關系代入上述Rv

中39KLT變換的特征－去相關

結(jié)論：

v向量的平均向量為0，直流分量為0。

v的協(xié)方差矩陣

協(xié)方差等于0

方差對角線按減序排列KLT的變換系數(shù)是由互不相關的隨機變量組成的，因此，KLT變換起到了去除變量間相關性的作用。簡而言之，每個λk

都是變換后第k個系數(shù)vk

的方差。40KLT

變換的特征－降維忽略特征值較小的那些特征向量，從而減少u的維數(shù)。令B*T

表示刪去Φ*T

最下面的N-M（M<N)行后得到的M×N矩陣，這樣，變換生成的向量維數(shù)就小一些（M×1大?。?，由下式生成：向量u仍然可由下式近似重構(gòu)出來：這種近似的均方誤差等于刪去的那些特征向量所對應的特征值之和41KLT變換舉例設3×1隨機向量u有以下的協(xié)方差矩陣：該矩陣的特征值和特征向量為：42KLT變換舉例對某個均值為0的向量uT＝(2,1,-0.1)有：變換后的向量v的協(xié)方差矩陣Rv

為：43KLT變換舉例降維：因為λ3

明顯比其它兩個向量小，因此，假設將矩陣Φ的第三行去掉從而將v變成二維向量。近似重構(gòu)的原向量：可以看到

u^和u有微小的差別，近似的均方誤差為λ3=0.146，也就是去掉的特征向量所對應的特征值。44KLT變換舉例Lena原始圖象相鄰象素(x,y)的灰度電平值相鄰象素

x的直方圖相鄰象素

y的直方圖45KLT變換舉例座標旋轉(zhuǎn)后相鄰象素(x,y)的灰度電平值座標旋轉(zhuǎn)后相鄰象素

x的直方圖座標旋轉(zhuǎn)后相鄰象素

y的直方圖Lena圖象的KLT基圖象46KLT變換舉例10:1Lena圖象失真(PSNR)和比特率的關系47DCT變換DCT（DiscreteCosineTransform）變換，即離散余弦變換。它在性能上最接近最佳變換——KLT變換，并且具有高效的快速算法。在目前的多數(shù)圖像和視頻壓縮標準中都用到了DCT技術。DCT變換壓縮的主要思想是通過對圖像的變換使分散在各個像素上的能量集中在少數(shù)系數(shù)上，進而甩掉零或近似于零的系數(shù)，以達到壓縮的目的。4748一維離散余弦變換(1D-DCT)1D-DCT的基為：則正變換可表示為：反變換可表示為：特點：（1）無虛數(shù)部分；（2）正變換核與反變換核一樣49二維離散余弦變換(2D-DCT)2D-DCT的基為：則正變換可表示為：反變換可表示為：v(0,l)v(0,0)v(k,0)v(k,l)502D-DCT基圖象k、l為變換頻率；m,n為空間座標v(k,l)為DCT系數(shù);u(m,n)原始圖象信號v(k,l)中v(0,0)稱為直流系數(shù)，其它的稱為交流系數(shù)。51離散余弦變換(DCT)的矩陣算法

一維離散余弦變換：正變換：反變換：

二維離散余弦變換：正變換：反變換：C為離散余弦變換矩陣，CT為C的轉(zhuǎn)置矩陣DCT52離散余弦變換(DCT)的矩陣算法

變換矩陣C：當N=2時，變換矩陣C為：當N=4時，變換矩陣C為：53離散余弦變換(DCT)的矩陣算法

離散余弦變換的矩陣算法舉例：已知：用矩陣算法求其DCT。由此例可看出：DCT將能量集中于頻率平面的左上角。54舉例：對以下圖像塊進行可分離的二維DCT變換54離散余弦變換(DCT)的矩陣算法容易驗證，該結(jié)果與直接使用二維變換式得到的結(jié)果是相同的。從中還可以看到，實數(shù)的原始圖像經(jīng)過DCT變換后得到的變換系數(shù)仍為實數(shù)，而且從前面DCT的定義可知，DCT正、反變換的基函數(shù)是一樣，這樣DCT處理就簡單。解：二維DCT是可分離的，可先對各行進行一維的行變換，得到系數(shù)矩陣如下：再進行列變換，最終的DCT系數(shù)矩陣為：55在變換域中，低頻系數(shù)的能量遠大于高頻系數(shù)的能量，變換系數(shù)的相關性將大大去除。2D-DCT舉例56DCT系數(shù)的幅度分布下圖是從測試圖象得到的8×8DCT系數(shù)幅度的直方圖。直流DC系數(shù)的分布類似于原始圖像，一般是典型的均勻分布。交流AC系數(shù)的分布類似于LaplacianpdfW.Mauersberger.Generalisedcorrelationmodelfordesigning2-dimensionalimagecoders.ElectronicsLetters,15(20):664{665,September197957DCT系數(shù)的量化-空域量化vs.變換域量化原始序列為x=[100,110,120,130,140,150,160,170]T8點DCT變換后的結(jié)果為：

y=[381.84,-64.42,

0,-6.73,0,-2.01,0,-0.507]

能量主要集中在前兩個系數(shù)7電平的中平量化器58方案1：直接對原始數(shù)據(jù)進行量化方案2：對DCT系數(shù)進行量化△=6，量化后的DCT系數(shù)：[64

-110-10000]3個非0DCT系數(shù)MSE:w/oDCT:3.0w/DCT:1.5DCT系數(shù)的量化-空域量化vs.變換域量化59DCT系數(shù)的量化-空域量化vs.變換域量化△=20，2個非0DCT系數(shù)：[19

-3000000]DCT系數(shù)重構(gòu)效果仍然很平滑直接方法開始產(chǎn)生塊/mosaic效應MSE:w/oDCT:50.0w/DCT:9.0760DCT系數(shù)的量化-空域量化vs.變換域量化△=100，2個非0DCT系數(shù)：[4

-1000000]DCT系數(shù)重構(gòu)效果仍然平滑直接方法產(chǎn)生的塊/mosaic效應更多MSE:w/oDCT:1000w/DCT:20561DCT系數(shù)的量化-空域量化vs.變換域量化輸入數(shù)據(jù)：大多數(shù)能量集中在左上角2-DDCT變換系數(shù)（取整）：62DCT系數(shù)的量化-空域量化vs.變換域量化

在變換域量化通常能得到更好的結(jié)果還可以做得更好對不同的DCT系數(shù)采取不同的量化步長

63人眼對信號強度的變化，慢變化部分（低頻部分）比細節(jié)部分（高頻部分）更敏感，亮度比色度更敏感。DCT系數(shù)能量集中在低頻系數(shù)（特別是直流系數(shù)），需要進行細量化（量化步長/臺階?。?，而高頻系數(shù)能量很少，可以對高頻系數(shù)粗量化。高頻系數(shù)量化后許多變?yōu)?，這就為數(shù)據(jù)壓縮打下了基礎。每個DCT變換系數(shù)都有一個自己的量化器，這些量化器構(gòu)成了量化矩陣。MPEG1、MPEG2、H.261等有其各自的亮度和色度量化矩陣。經(jīng)逆量化和逆DCT恢復圖象?；謴偷膱D象與原圖象相比失真不大，但有失真。這失真主要是量化產(chǎn)生的，因為量化是一個電平對多個電平的映射，信息的丟失是不可避免的，而DCT變換理論上講并不丟失信息。DCT變換系數(shù)的量化64DCT變換系數(shù)的量化1391441491531551551551551441511531561591561561561501551601631581561561561591611621601601591591591591601611621621551551551611611611611601571571571621621611631621571571571621621611611631581581581611101624405161121214192658605514131624405769561417222951878062182237566810910377243555648110411392496478871031211201017292959811210010399790-100000-2-1000000-1-1000000-100000000000000000000000000000000000000012640-1000000-24-12000000-14-13000000-14000000000000000000000000000000000000000(a)原圖象(b)DCT系數(shù)(c)量化矩陣(d)已量化DCT系數(shù)(f)重建圖象(e)逆量化系數(shù)65DCT變換系數(shù)的比特分配基本原則變換系數(shù)的方差是不相等的，因此，每個系數(shù)需要不同的量化比特。把給定的總的比特率RT

分配給M×M=N個變換系數(shù)，使整體的失真度DT(R)達到最小。每個系數(shù)的平均比特率為R。討論的變換為正交變換變換過程中能量守恒，所以，總的誤差=量化誤差每個變換系數(shù)的能量：每個量化器的量化誤差：總的量化誤差：Rk

表示第k

個系數(shù)的平均碼率（bit/sample）σvk2

表示量化器第k個輸入的DCT系數(shù)方差，因子ε取決于輸入分布和量化器66DCT變換系數(shù)的比特分配比特分配問題：計算{Rk}，使得總的量化噪聲最小并滿足比特率：變換系數(shù)能量：為協(xié)方差矩陣對角線元素σvk2

為Rvv

對角線上第k個元素67DCT變換系數(shù)的比特分配用Lagrangian代價函數(shù)得到最佳的比特分配對所有的k，令

每個變換系數(shù)的量化誤差的方差盡可能相等68DCT變換系數(shù)的比特分配代入比特率約束每個系數(shù)的碼率和最小失真分別為：一個變換系數(shù)的方差越大，分配給它的比特數(shù)越多69DCT變換系數(shù)的比特分配變換編碼的總的最小失真為假設對原始信號的碼率失真函數(shù)為則變換編碼增益為70DCT變換系數(shù)的比特分配變換編碼增益為σu2為Ruu對角線的元素，對平穩(wěn)過程，Ruu每個(i,i)相等增益與系數(shù)方差的集中程度有關若每個系數(shù)的方差相等，則沒有增益上述最佳Rk

不一定為整數(shù)，甚至不能保證為正數(shù)

Rk<0Rk=0但增大了平均碼率，還需均勻減小非0的Rk

幾何均值算術均值71DCT變換系數(shù)的遞歸比特分配滿足約束：Rk≥0且Rk

為整數(shù)所以碼率分配算法為：計算每個系數(shù)的方差σvk2

初始所有的Rk=0，k=0,1,2,….,N-1

對所有的方差σvk2

排序，對有最大方差的系數(shù)k’

分配1比特若比特數(shù)用盡，停止；否則轉(zhuǎn)第3步上述算法稱為

zonalsampling（區(qū)域編碼）8*8變換的比特分配72DCT變換系數(shù)的閾值編碼

ThresholdCoding區(qū)域編碼

Zonalsampling基于平均值進行比特分配局部變化可能不能很好重構(gòu)如邊緣像素閾值編碼：對所有大于閾值的系數(shù)進行編碼，而丟棄所有低于門限的變換系數(shù)。傳送的系數(shù)位置隨圖像內(nèi)容而變化，具有一定的自適應性。非零變換系數(shù)的位置與它們的幅度值一起傳送(a)區(qū)域編碼屏蔽矩陣

(b)區(qū)域比特分配表

(c)閾值編碼屏蔽矩陣73對于不同的變換系數(shù)塊，傳送的變換系數(shù)可能不同。閾值編碼常用均勻量化器和熵編碼，即變長碼。DCT變換系數(shù)的閾值編碼閾值編碼的量化特性曲線閾值編碼也是一種自適應編碼，量化編碼自適應于圖像內(nèi)容，比系數(shù)屏蔽矩陣不隨圖像變化的區(qū)域編碼有更高的壓縮比。目前

MPEGx和

H.26x系列的國際圖像壓縮標準都采用閾值編碼方式。74更有效的傳輸非零變換系數(shù)位置的方法：“之”字型掃描和游程-幅度二維熵編碼?！爸弊中螔呙枋棺儞Q系數(shù)所代表的頻率分量由高到低排列，增加連零的個數(shù)，提高變字長游程編碼效率，將二維8×8變換系數(shù)排列成一維1×64數(shù)據(jù)串。對于隔行掃描圖象，可以采用其它替代的“之”字形掃描。塊結(jié)束發(fā)送EOB（EndofBlock）標識DCT變換系數(shù)的游程編碼75基于DCT塊變換的編碼系統(tǒng)DCTZig-zagQuantize游程-幅度編碼Huffman

Code011010001011101...76原始圖象DCTDCcomponentACcomponentsQuantizezigzagrun-length-ValuecodeHuffmancode10011011100011...codedbitstream<10bits(0.55bits/pixel)基于DCT的編碼系統(tǒng)－編碼游程(連0的個數(shù))幅度77originalblockreconstructedblockerrorsUncompressed

(262KB)Compressed(50)

(22KB,12:1)Compressed(1)

(6KB,43:1)基于DCT的編碼系統(tǒng)－解碼78基于DCT塊變換的編碼系統(tǒng)79DCT系數(shù)的傳輸圖象塊圖象塊DCT系數(shù)量化的圖象塊DCT系數(shù)重建圖象塊80典型的DCT編碼失真－塊效應DCT本身沒有失真，是可逆變換，如果計算精度保證的話，變換前后的結(jié)果是一樣的。DCT變換固有的缺點：塊效應：變換編碼是一種塊結(jié)構(gòu)編碼方法，易出現(xiàn)塊與塊之間的不連續(xù)性。如下圖中的“階梯效應”和后面圖中的“蚊子效應”。圖像的邊界、紋理處易出現(xiàn)較明顯的損傷。81典型的DCT編碼失真－蚊子效應82典型的DCT編碼失真－高頻損傷83自適應變換編碼對每一類圖象，分別優(yōu)化量化和熵編碼分類：沒有細節(jié)的塊水平結(jié)構(gòu)垂直結(jié)構(gòu)對角結(jié)構(gòu)無方向的紋理84DCT變換的尺寸2*24*48*816*1632*3264*64子塊尺寸位/象素2.52.01.51.0DCT編碼效率和尺寸之間的關系是單調(diào)曲線，其拐點在4×4、8×8、16×16區(qū)段。85DCT變換的尺寸2*24*48*816*1632*3264*64子塊尺寸位/象素2.52.01.51.0需要根據(jù)圖像分辨率（QCIF、CIF、SDTV、HDTV或數(shù)字電影）選擇DCT變換塊的大小。MPEG1/2/4、H261/2/3選擇了8×8H.264中選擇4×4：更適宜于小尺寸圖像，相應的塊效應主觀感覺也會減弱更好的運動補償，意味著更小的空間相關性HEVC：4×4、8×8、16×16、32×32、64×6486DCT

快速算法直接進行DCT計算：每個系數(shù)需要64次乘法、63次加法，8×8DCT將需要1024次乘法，896次加法。DCT有快速算法：2D-DCT的行列運算，每一次運算變?yōu)?D-DCT運算，1D-DCT采用fastDCT。一般的1D-DCT的快速算法使運算量降低為Nlog2N數(shù)量級的實數(shù)乘法。1stdimension轉(zhuǎn)置2stdimension系數(shù)ROM矩陣表NN′矩陣表NN′BTBUCC行列B=CUVT=VBTVT87DCT

快速算法DCT快速算法是中國人陳文雄(1977)提出的ChenW.H.,et.,”Afastcomputationalalgorithmforthediscretecosinetransform”,IEEEtransactionsonCommunications,COM-25,1004-1009.N＝8時的算法如圖cx對應于cosx，sx對應于sinx。88DCT

快速算法DCT矩陣因數(shù)分解為稀疏矩陣（Chenet.al.,1977）（對應上述信號流圖）將碼位倒置序列轉(zhuǎn)變成順序序列的輸出向量89DCT

快速算法AAN快速DCT算法（Arai，AguiandNakajima，1988）：矩陣分解為稀疏矩陣90DCT

快速算法Arai，AguiandNakajima算法的快速8-DCT信號流圖（此算法需要13次乘法，29次加法）91DCT

快速算法LLM快速DCT算法

(Loeffler,LigtenbergandMoschytz)C.Loeffler,A.LigtenbergandG.Moschytz,"PracticalFast1-DDCTAlgorithmswith11Multiplications",Proc.Int'l.Conf.onAcoustics,Speech,andSignalProcessing1989,pp.988-991此算法需要11次乘法和29次加法。92DCT

和DFT比較DCT是實的正交變換，但不對稱。DCT不是DFT的實部因為cos(x)=(ejx+e-jx)/2，因此，對于DCT可用2N點DFT計算。93DCT

和DFT比較對0≤k≤N-1，其中x等價于將x(n)補零成2N點序列。上式第二項等價于第一項作下標為（－k）的運算。因此，實際上只需要計算2N點DFT。94DFT:DCT:函數(shù)的不連續(xù)影響Fourier級數(shù)的收斂，從而需要更多基函數(shù)，影響壓縮DCT更連續(xù)DFT在邊界不連續(xù)DCT

和DFT比較95DCT變換后的能量更集中更適合壓縮DCT

和DFT比較96DCT次最佳變換－一階Markov過程如果一個靜態(tài)序列中每個元素的條件概率只依賴于它的前一個元素，則此靜態(tài)隨機序列稱為一階馬爾可夫序列。通常遇到的圖象都能滿足這個馬爾可夫假設。對于那些可以用一階馬爾可夫(Markov)過程來模擬的圖象，DCT是KLT變換的很好的近似，尤其是當ρ接近于1的情況下。因此，對于通常遇到的圖象，都可以用更容易計算的DCT來近似KLT變換。一個N元素零均值一階馬爾可夫序列的協(xié)方差矩陣為其中0≤ρ≤1特征值λk

和特征向量φk

為:97wk

是如下超越方程的正根:只要給出ρ的一個值，就可以計算出KLT變換的基向量。對于自然景物，通常ρ≈1，這時DCT的基向量可以很好地近似KLT變換地基向量，因此，DCT經(jīng)常代替KLT。盡管DCT在降低相關性方面不如KLT有效，但是其好處是它的基函數(shù)是固定的，而且對于強相關圖象來講，DCT可以近似KLT，所以，DCT是次最佳的變換。DCT次最佳變換－一階Markov過程98DCT次最佳變換對相關性較強的數(shù)據(jù)，它有優(yōu)良的能量集中（次最佳變換）方向DCT（DirectionalDCT）傳統(tǒng)的基于塊的DCTNxN大小的方塊分別按照垂直和水平方向進行處理——首先行或列沒有區(qū)別當圖像塊中水平和/或垂直邊緣占支配地位時，這很可能是最好的選擇。但對那些對角邊緣占支配地位的圖像塊，效果如何？結(jié)果1：產(chǎn)生了一些不必要的非零AC系數(shù)，因此需要更多的比特；結(jié)果2：對角邊緣遭到徹底破壞，從而導致質(zhì)量惡化。99ABCD方向DCT方向信息方向信息對主客觀質(zhì)量評價是非常關鍵的。方向信息的利用已經(jīng)研究了很長時間—谷歌搜索可以發(fā)現(xiàn)超過100萬項結(jié)果。在各種應用中取得了顯著進步。新的DDCT框架完全限制為N×N方塊——與大多數(shù)的編碼標準兼容。能夠處理每一個圖像塊中所有有意義的方向邊緣。這里只簡要介紹框架，許多問題需要進一步的研究。100方向DCT8種基于塊的DDCT模式101可以推廣到N×N塊大小!Horizontalup(Mode8)Vertical(Mode0)Horizontal(Mode1)Diagonaldown-left(Mode3)Diagonaldown-right(Mode4)Verticalright(Mode5)Horizontaldown(Mode6)Verticalleft(Mode7)

DDCT的實現(xiàn)DDCT提供了9種4×4變換，9種8×8變換，4種16×16變換；對于每種幀內(nèi)預測模式，DDCT包括兩個階段：

Stage1–—一維方向DCT：沿著預測方向進行不同長度的1DDCT變換。N×N圖像塊，沿著左下對角線進行不同長度的1DDCT變換（模式3）沿著預測方向，把像素排列組合到一起，并進行1DDCT變換。第一個1DDCT是真正的方向變換。DCT變換的長度是不同的。方向DCTStage2–一維水平DCT：數(shù)據(jù)組織、再次1DDCT變換和數(shù)據(jù)掃描作為對第一次方向

1DDCT變換的補充，按水平重排第一次1DDCT變換的系數(shù)，再次進行不同長度的1DDCT后，然后把變換系數(shù)移動左對齊，進行修正的“之”字形掃描。方向DCT模式3DDCT的實現(xiàn)(a,b,…,p)=4x4塊的2D空間域像素(A,B,…,P)=1D系數(shù)DCT變換的長度L=1,2,3,4,3,2,1,沿著模式3的主導方向STEP1STEP2STEP3重排第一次1DCT變換系數(shù)STEP4=1DDCT系數(shù)水平DCT變換的長度L=7,5,3,1STEP5重排第二次1DDCT變換系數(shù)，并zigzag掃描。方向DCT獲得基圖像的過程在步驟3后，對于每個基圖像，用1代替相應位置的系數(shù)，其余位置的系數(shù)置為0，重復步驟4。對于4×4塊，獲得16個基圖像。同樣的過程適用于所有其它的DDCT模式。方向DCT模式0/1DDCT,模式3DDCT和模式5DDCT，8×8塊的基圖像模式3DDCT,4x4block的基圖像基圖像方向DCT由模式3翻轉(zhuǎn)（水平或垂直）得到模式4方向DCT方向DCT108模式5DDCT的實現(xiàn)8×8塊大小的模式5方向DCT第一個方向的方向DCT第二個方向的水平DCT修正的zig-zag掃描DCT長度：48888888499998888DCT長度方向DCT由模式5得到模式6方向DCT由模式5得到模式7方向DCT由模式5得到模式8DDCT的壓縮效率使變換尺寸更加平衡，DDCT把角落里的像素組織到一起，以使用更長的DCT變換，因此更高效的壓縮。DDCT的特性

適應性AdaptivityDDCT為每一種預測模式分配一個不同的變換和掃描圖案，不像整數(shù)DCT那樣都是相同的。

方向性Directionality沿著預測的方向進行DCT變換，DDCT有潛力減少目標邊界的失真。

對稱性Symmetry對于22種預測模式，雖然有22種DDCT

(9種4×4，9種8×8、4種16×16)，但這些變換可以通過簡單的運算，例如旋轉(zhuǎn)和/或反射，由僅有的7個不同核心變換得到。

16x16:所有的16×16，只有一種變換；8x8和4x4:

模式0,1:和DCT類似，先行后列；

模式3和4：模式4可由模式3獲得；

模式5到8：模式6-8可由模式5通過反射和旋轉(zhuǎn)獲得。

方向DCT113JPEG：左邊DCT，右邊DDCT方向DCTHaoXu,JizhengXu,FengWu，“LIFTING-BASEDDIRECTIONALDCT-LIKETRANSFORMFORIMAGECODING”，Univ.ofScienceandTechnologyofChina，ICIP2007客觀評測114JPEG：左邊DCT，右邊DDCT方向DCT離散正弦變換DiscreteSineTransform，DST）變換矩陣為sine的函數(shù)：類似DCT，有很好的性質(zhì)當很小時，DST的性能接近KLT的性能在圖像/語音編碼應用中，與DCT變換互補115AnkurSaxenaandFelixC.Fernandes，“ModeDependentDCT-DSTforIntraPredictioninBlock-basedVideoCoding”，201118thIEEEInternationalConferenceonImageProcessing。116變換編碼：小結(jié)Summary正交變換：信號空間中坐標系統(tǒng)的旋轉(zhuǎn)；變換目的：去相關，能量集中；KLT是最佳的變換，但依賴于信號的統(tǒng)計特性，并且因此沒有快速算法；DCT是次最佳的變換，相對于DFT，DCT減少了塊效應；比特分配與方差的對數(shù)成正比；DCT變換有不少快速算法，可硬件實現(xiàn)；相比于DFT，DCT減少了塊效應；“8×8DCT＋門限編碼(量化)＋Zig-zag掃描”廣泛應用于各種標準中（例如，JPEG、MPEGx和ITU-TH.26x）；DDCT和斜邊緣圖像更匹配，能獲得增益。DST具有類似DCT的性質(zhì)，當很小時，DST的性能接近KLT的性能。參考資料Wiegand,Schwarz,Chapter7Marcellin,Taubman,sections4.1,4.3V.K.Goyal,“Theoreticalfoundationsoftransformcoding,”IEEESignalProcessingMagazine,vol.18,no.5,pp.9-21,Sept.2001W.-H.Chen,W.Pratt,“SceneAdaptiveCoder,”IEEETransactionsonCommunications,vol.32,no.3,pp.225-232,March1984.E.Y.Lam,J.W.Goodman,“AMathematicalAnalysisoftheDC