第6章 圖像編碼3

數(shù)字圖像處理基礎(chǔ)第5章圖像編碼（第四講）5.6變換編碼圖像編碼中另一類有效的方法是變換編碼。變換編碼的通用模型如下圖所示圖5—42圖像變換編碼模型映射變換量化器編碼器

變換編碼主要由映射變換、量化及編碼幾部分操作組成。映射變換是把圖像中的各個(gè)像素從一種空間變換到另一種空間，然后針對(duì)變換后的信號(hào)再進(jìn)行量化與編碼操作。在接收端，首先對(duì)接收到的信號(hào)進(jìn)行譯碼，然后再進(jìn)行反變換以恢復(fù)原圖像。

映射變換的關(guān)鍵在于能夠產(chǎn)生一系列更加有效的系數(shù)，對(duì)這些系數(shù)進(jìn)行編碼所需的總比特?cái)?shù)比對(duì)原始圖像進(jìn)行編碼所需要的總比特?cái)?shù)要少得多，因此，使數(shù)據(jù)率得以壓縮。映射變換的方法很多。圖像變換編碼基本可分為兩大類，

某些特殊的映射變換編碼法，函數(shù)變換編碼法。

5.6.1幾種特殊的映射變換編碼法特殊映射變換編碼法包括諸如行程編碼，輪廓編碼等一些變換編碼方法。它們特別適用于所謂二值圖像的編碼。這類圖像包括業(yè)務(wù)信件、公文、氣象圖、工程圖、地圖、指紋卡片及新聞報(bào)紙等。當(dāng)然在編碼技術(shù)上同樣可分為精確編碼和近似編碼兩類。精確編碼可以不引入任何畸變，在接收端可以從編碼比特流中精確恢復(fù)出原始圖像。近似編碼會(huì)引入一些畸變，但是，這種方法卻可以在保證可用性的前提下獲得較高的壓縮比。下面通過幾種具體的編碼方法說明這種變換編碼法的基本概念。

1、一維行程編碼

一維行程編碼的概念如圖5—42所示。假如沿著某一掃描行的像素為，它們所具有的灰度值可能為。在編碼之前，可以首先把這些像素映射為成對(duì)序列，和。

其中表示某一灰度值，表示第i次運(yùn)行的行程。也可以說是連續(xù)取值為灰度值的像素的個(gè)數(shù)。經(jīng)過這樣映射變換后就可以對(duì)編碼，而不必對(duì)像素直接編碼。

由于有些圖像如前面提到的二值圖像，連續(xù)取同一灰度級(jí)的像素很多，對(duì)映射后的序列進(jìn)行編碼會(huì)大大壓縮比特率。

圖5—42所示的例子可映射成表5—14所示的序列對(duì)。在這個(gè)例子中有8級(jí)灰度，24個(gè)像素。如果對(duì)編碼，總的比特?cái)?shù)至少要24×3=72bit。

如果對(duì)表5—14的序列對(duì)編碼，灰度值用3位碼，行程長度用4位碼，每對(duì)參數(shù)用7位碼，共4對(duì)，總比特?cái)?shù)只要28bit就夠了?？梢妷嚎s率是很可觀的。表5—14序列對(duì)

i1362510342486

行程編碼可分為行程終點(diǎn)編碼和行程長度編碼。如果行程終點(diǎn)的位置由掃描行的開始點(diǎn)算起，并且由到達(dá)行程終點(diǎn)的像素計(jì)數(shù)來確定，就稱為行程終點(diǎn)編碼。如果行程終點(diǎn)位置由這一終點(diǎn)與前一終點(diǎn)的相對(duì)距離確定，就稱為行程長度編碼。對(duì)于二值圖像來說采用行程長度編碼，甚至不需要傳送灰度信息。假定某一掃描線含有3個(gè)白色像素，其后是2個(gè)黑色像素，接著又是10個(gè)白色像素。這樣，在行程長度編碼中，只傳送行程長度3、2和10就可以了。每個(gè)行程長度告訴沿掃描線的下一個(gè)邊界點(diǎn)的相對(duì)位置。6．1．2二維行程編碼

二維行程編碼也叫預(yù)測微分量化器(PredictiveDifferentialQuantizer)，簡稱PDQ。其基本算法如圖5—43所示。

PDQ的基本算法是將圖像元素陣列變換為整數(shù)對(duì)△′和△″的序列。這里△′是相鄰掃描行上行程的開始點(diǎn)之間的差。圖中△′是Ａ點(diǎn)和Ｂ點(diǎn)的差。△″是這相鄰行行程的差。對(duì)應(yīng)于Ａ起始點(diǎn)的行程為

l1

，對(duì)應(yīng)于Ｂ起點(diǎn)的行程為

l2

，因此，△″＝

l2

—l1

。△′是相鄰掃描行上行程的開始點(diǎn)之間的差△″是這相鄰行行程的差“開始”“消失”另外，對(duì)于圖中的暗面積還要有一個(gè)“開始”和“消失”的標(biāo)記。這樣就把一幅圖像的像素陣列按相繼掃描行變換為△′、△″、開始、消失四個(gè)參量的序列，然后便可對(duì)這四個(gè)參量來編碼。PDQ法利用了掃描線間的相關(guān)性，因此，它有更大的壓縮潛力。

另外一種方法叫做雙重增量編碼（DoubleDeltacoding），簡稱DDC。它是對(duì)△′和進(jìn)行編碼而不是對(duì)△′和△″編碼。是前一掃描行的暗區(qū)后邊界與相繼掃描行暗區(qū)后邊界的差。實(shí)驗(yàn)證明，這種方法的壓縮比較PDQ法更大?！鳌涫窍噜彃呙栊猩闲谐痰拈_始點(diǎn)之間的差△///

是前一掃描行的暗區(qū)后邊界與相繼掃描行暗區(qū)后邊界的差“開始”“消失”

當(dāng)在圖像中有少數(shù)大的暗區(qū)時(shí)二維行程編碼更有效，對(duì)于有許多小暗區(qū)的圖像來說，一維行程編碼更有效。6．2正交變換編碼變換編碼中另一類方法是正交變換編碼法（或稱函數(shù)變換編碼法）。這種方法的基本原理是通過正交函數(shù)變換把圖像從空間域轉(zhuǎn)換為能量比較集中的變換域。然后對(duì)變換系數(shù)進(jìn)行編碼，從而達(dá)到縮減比特率的目的。6．2．1正交變換編碼的基本概念

正交變換編碼的基本原理框圖如圖5—50所示。編碼器由預(yù)處理、正交變換、量化與編碼幾部分組成，譯碼器由譯碼、反變換及后處理組成。在編碼操作中，模擬圖像信號(hào)首先送入預(yù)處理器，將模擬信號(hào)變?yōu)閿?shù)字信號(hào)。然后把數(shù)字信號(hào)分塊進(jìn)行正交變換，通過正交變換就使空間域信號(hào)變換到變換域。然后對(duì)變換系數(shù)進(jìn)行量化和編碼。

在信道中傳輸或在存儲(chǔ)器中存儲(chǔ)的是這些變換系數(shù)的碼字。這就是編碼端的處理過程。在譯碼端，首先將收到的碼字進(jìn)行譯碼，然后進(jìn)行反變換以使變換系數(shù)恢復(fù)為空間域樣值，最后經(jīng)過處理使數(shù)字信號(hào)變?yōu)槟M信號(hào)以供顯示。圖5—50正交變換編碼原理框圖預(yù)處理正交變換量化編碼傳輸、存儲(chǔ)解碼反變換后處理

正交變換編碼之所以能夠壓縮數(shù)據(jù)率，主要是它有如下一些性質(zhì)：（１）正交變換具有熵保持性質(zhì)。這說明通過正交變換并不丟失信息，因此，可以用傳輸變換系數(shù)來達(dá)到傳送信息的目的。（２）正交變換有能量保持性質(zhì)。這就是第三章提到的各種正交變換的帕斯維爾能量保持性質(zhì)。它的意義在于：只有當(dāng)有限離散空間域能量全部轉(zhuǎn)移到某個(gè)有限離散變換域后，有限個(gè)空間取樣才能完全由有限個(gè)變換系數(shù)對(duì)于基礎(chǔ)矢量加權(quán)來恢復(fù)。（３）能量重新分配與集中。這個(gè)性質(zhì)使我們有可能采用熵壓縮法來壓縮數(shù)據(jù)。也就是在質(zhì)量允許的情況下，可舍棄一些能量較小的系數(shù)，或者對(duì)能量大的譜點(diǎn)分配較多的比特，對(duì)能量較小的譜點(diǎn)分配較少的比特，從而使數(shù)據(jù)率有較大的壓縮。

（４）去相關(guān)特性。正交變換可以使高度相關(guān)的空間樣值變?yōu)橄嚓P(guān)性很弱的變換系數(shù)。換句話說，正交變換有可能使相關(guān)的空間域轉(zhuǎn)變?yōu)椴幌嚓P(guān)的變換域。這樣就使存在于相關(guān)性之中的多余度得以去除。

綜上所述，由于正交變換的結(jié)果，相關(guān)圖像的空間域可能變?yōu)槟芰勘３?、集中且為不相關(guān)的變換域。如果用變換系數(shù)來代替空間樣值編碼傳送時(shí)，只需對(duì)變換系數(shù)中能量比較集中的部分加以編碼，這樣就能使數(shù)字圖像傳輸或存貯時(shí)所需的碼率得到壓縮。

6．2．2變換編碼的數(shù)學(xué)模型分析

正交變換編碼的編碼過程主要是在變換域上進(jìn)行。在這個(gè)基礎(chǔ)上可以建立以下變換編碼的數(shù)學(xué)模型。設(shè)一圖像信源為一向量

(5—95)變換后輸出一向量(5—97)

(5—96)取正交變換為[T]，那么[X]與[Y]之間的關(guān)系為由于[T]是正交矩陣，所以

(5—98)這里[I]為單位矩陣，是[T]的轉(zhuǎn)置，是[T]的逆。反之也有

(5—99)也就是說在編碼端利用正變換得到[Y]，在譯碼端可用反變換來恢復(fù)[X]。

(5—100)如果在傳輸或存貯中只保留M個(gè)分量，M<N，則可由[Y]的近似值來恢復(fù)[X]。當(dāng)然是[X]的近似值。但是只要選取得當(dāng)，仍可保證失真在允許的范圍內(nèi)。

顯然，關(guān)鍵問題在于選取什么樣的正交變換[T]，才能既得到最大的壓縮率，又不造成嚴(yán)重的失真。

因此，有必要研究一下由正交變換得到[Y]的統(tǒng)計(jì)特性。[Y]的統(tǒng)計(jì)特性中最為重要的是協(xié)方差矩陣。下面討論一下正交變換后得到的[Y]的協(xié)方差矩陣采用何種形式。當(dāng)然，[X]的統(tǒng)計(jì)特性可以測得。

(5—101)設(shè)圖像信號(hào)是Ｎ維向量[X]

的協(xié)方差矩陣式中[CX]是[X]的協(xié)方差矩陣，是[X]的均值，E是求數(shù)學(xué)期望值。(5—102)又設(shè)變換系數(shù)向量為(5—103)

[CY]

為[Y]的協(xié)方差矩陣，所以

(5—104)式中

是[Y]的均值。

由正交變換的定義，有因此式(5—105)說明，變換系數(shù)的協(xié)方差矩陣可以通過空間域圖像的協(xié)方差矩陣的二維變換得到。由此可以得出結(jié)論：

(5—105)即

變換系數(shù)的協(xié)方差矩陣決定于變換矩陣[T]和空間域圖像的協(xié)方差矩陣[CX]。而[CX]是圖像本身所固有的，因此，關(guān)鍵在于尋求合適的[T]。我們希望的兩個(gè)結(jié)果:1)、如果[CY]是一個(gè)對(duì)角形矩陣，那就說明系數(shù)間的相關(guān)性完全解除了。也就是說解除了包含在相關(guān)性中的冗余度，為無失真壓縮編碼打下了基礎(chǔ)。

2)、還希望對(duì)角形矩陣中元素的能量盡量集中，以便使舍去若干系數(shù)后造成的誤差不致于太大，這樣，就為熵壓縮編碼提供了條件。綜上所述，變換編碼要解決的關(guān)鍵問題是合理地尋求變換矩陣[T]。

3.最佳變換問題

在研究各種變換矩陣[T]的過程中，自然要比較它們的優(yōu)劣，因此，就有一個(gè)比較準(zhǔn)則問題。下面討論最佳變換問題。（１）最佳變換應(yīng)滿足的條件

1).能使變換系數(shù)之間的相關(guān)性全部解除；2).能使變換系數(shù)之方差高度集中。

顯然，第一個(gè)條件希望變換系數(shù)的協(xié)方差矩陣為對(duì)角形矩陣；第二個(gè)條件希望對(duì)角形矩陣中對(duì)角線上的元素能量主要集中在前Ｍ項(xiàng)上，這樣就可以保證在去掉N-M項(xiàng)后的截尾誤差盡量小。（２）最佳的準(zhǔn)則常用的準(zhǔn)則仍然是均方誤差準(zhǔn)則。均方誤差由下式表示(5—106)式中f(x,y)代表原始圖像，g(x,y)為經(jīng)編譯碼后的恢復(fù)圖像。均方誤差準(zhǔn)則就是要使最小。最小的變換就是最佳變換。（３）均方誤差準(zhǔn)則下的最佳統(tǒng)計(jì)變換均方誤差準(zhǔn)則下的最佳統(tǒng)計(jì)變換也叫K-L變換(KarhunenloeveTransform)。設(shè)T是一正交變換矩陣(5—107)這是一個(gè)Ｎ×Ｎ矩陣，其中

是一個(gè)Ｎ維向量。這個(gè)矩陣是正交的，因此顯然

(5—108)

另外,設(shè)有一數(shù)據(jù)向量經(jīng)正交變換后

(5—109)而

(5—110)這里

于是(5—111)為了壓縮數(shù)據(jù)，在恢復(fù)X時(shí)不取完整的N個(gè)Y分量，而是僅取M個(gè)分量，其中M<N。這樣其中M個(gè)分量構(gòu)成一個(gè)子集，即：

用這M個(gè)分量去估計(jì)X，其余的用常量bi

來代替。于是可得到

(5—112)這里是X的估計(jì)。X的值與的誤差為

(5—13)設(shè)為均方誤差，則

(5—114)將代入由上述的正交條件可簡化為

(5—115)

根據(jù)最小均方誤差準(zhǔn)則，要使最小就要正確選取及。為了求得最佳的和，可分兩步來求：第一步把對(duì)求導(dǎo)并令其等于零，即

(5—116)又因?yàn)?/p>

所以

將代入，則(5—118)因?yàn)?/p>

所以

(5—119)第二步求最佳化的。為了求得最佳的，不僅要找出使最小，而且還要滿足的條件。因此，可用求條件極值的拉格朗日乘數(shù)法法則。根據(jù)拉格朗日乘數(shù)法，在求的條件極值時(shí)做一個(gè)新的函數(shù)。

(5—120)

(5—122)

(5—121)對(duì)求導(dǎo)，并注意到所以

(5—123)即

(5—124)由線性代數(shù)理論可知

(5—125)顯然，βi

就是CX

的特征根，

就是CX

的特征向量。

如CX

是對(duì)稱矩陣，就可找到一個(gè)變換[T]，使CY

成為對(duì)角形矩陣。

如果圖像信源是一階馬爾可夫模型的話，那么將是一個(gè)Toeplitz矩陣，即

(5—126)這是一個(gè)對(duì)稱矩陣。因此，通過正交變換可以使成為對(duì)角形矩陣。也就是說可以找到一個(gè)變換矩陣[T]而得到最佳變換結(jié)果。這就是K-L變換的核心。

(４)最佳變換的實(shí)現(xiàn)方法由上面的分析可見，K-L變換中的變換矩陣[T]不是一個(gè)固定的矩陣，它必須由信源來確定。當(dāng)給定一信源時(shí)，可用如下幾個(gè)步驟求得