第2章多媒體數(shù)據(jù)壓縮編碼技術(shù)2.1多媒體數(shù)據(jù)壓縮的必要性和可行性2.2多媒體數(shù)據(jù)壓縮理論基礎(chǔ)2.3壓縮算法的分類及性能評價(jià)2.4熵編碼2.5預(yù)測編碼第2章多媒體數(shù)據(jù)壓縮編碼技術(shù)2.6變換編碼2.7矢量量化編碼2.8壓縮編碼新技術(shù)2.9本章小結(jié)思考練習(xí)題在多媒體系統(tǒng)中，處理、傳輸、存儲的多媒體信息主要包括文字、聲音、圖形、圖像、視頻等媒體類型，這些媒體以大量數(shù)據(jù)的形式存在，如果不對它們進(jìn)行壓縮，是無法在計(jì)算機(jī)中存儲、處理和傳輸?shù)?。所以，多媒體數(shù)據(jù)的壓縮編碼技術(shù)是網(wǎng)絡(luò)多媒體技術(shù)中的重要基礎(chǔ)。本章主要討論多媒體數(shù)據(jù)編碼基本原理、常用壓縮編碼方法以及新型壓縮編碼技術(shù)。

2.1.1多媒體數(shù)據(jù)壓縮的必要性

信息時(shí)代的重要特征是信息的數(shù)字化，而數(shù)字化后的視頻和音頻等媒體信息具有媒體海量性，這與當(dāng)前硬件技術(shù)所能提供的計(jì)算機(jī)存儲資源和網(wǎng)絡(luò)帶寬之間有很大差距。這樣，就對多媒體信息的存儲和傳輸造成了很大困難，成為阻礙人們有效獲取和利用信息的一個(gè)瓶頸問題。不能對多媒體數(shù)據(jù)進(jìn)行有效的壓縮，就難以保證通信的順利進(jìn)行。數(shù)字化了的視頻和音頻信號的數(shù)據(jù)量是非常驚人的。下面舉例來說明。2.1多媒體數(shù)據(jù)壓縮的必要性和可行性對于音頻信息來說，人在正常說話時(shí)的音頻一般為200Hz~3.4kHz，即人類語音的寬度約為3.4kHz。同樣依據(jù)采樣定理，并設(shè)數(shù)字化精度為8bit，則每秒的數(shù)據(jù)量為

3.4×2×8＝54.4kb

即在上述采樣條件下講1分鐘話的數(shù)據(jù)量約為400kb。

以一般彩色電視信號為例，設(shè)代表光強(qiáng)、色彩和色飽和度的YIQ空間中各分量的帶寬分別為4MHz、1.3MHz和0.5MHz。根據(jù)采樣定理，僅當(dāng)采樣頻率大于或等于2倍的原始信號的頻率時(shí)，才能保證采樣后的信號可被無失真地恢復(fù)為原始信號。再設(shè)各樣點(diǎn)均被數(shù)字化為8bit，從而1秒鐘的電視信號的數(shù)據(jù)量為

(4＋1.3＋0.5)×2×8＝92.8MB

因而一張640MB容量的CD-ROM能夠存放的原始電視數(shù)據(jù)(每字節(jié)附有2位校驗(yàn)位)為

也就是說，一張普通光盤只能存放44s的原始數(shù)據(jù)。

表2-1列出了支持語音、圖像、視頻等多媒體信號高質(zhì)量存儲和傳輸所必需的未壓縮速率以及信號特性。

表2-1各種信號的特性和未壓縮速率從以上兩個(gè)例子以及表2-1可以看出：未進(jìn)行任何形式的編碼和壓縮的多媒體信息數(shù)據(jù)量龐大，如果不進(jìn)行壓縮處理，計(jì)算機(jī)系統(tǒng)幾乎無法對其進(jìn)行存取和交換。因此，對多媒體數(shù)據(jù)進(jìn)行壓縮十分必要。2.1.2多媒體數(shù)據(jù)壓縮的可行性

從信息論觀點(diǎn)來看，描述信源的數(shù)據(jù)是信息量(信源熵)和信息冗余量之和。數(shù)據(jù)壓縮編碼的本質(zhì)就是減少這些冗余量，從而可以減少數(shù)據(jù)量而不是減少信源的信息量。一般而言，圖像、視頻、音頻數(shù)據(jù)中存在的數(shù)據(jù)冗余類型主要有以下這些：

(1)空間冗余。在同一幅圖像中，規(guī)則物體和規(guī)則背景的表面物理特性具有相關(guān)性，這些相關(guān)性的光成像結(jié)果在數(shù)字化圖像中就表現(xiàn)為數(shù)據(jù)冗余。

(2)時(shí)間冗余。時(shí)間冗余反映在圖像序列中就是相鄰幀圖像之間有較大的相關(guān)性，一幀圖像中的某物體或場景可以由其他幀圖像中的物體或場景重構(gòu)出來。音頻的前后樣值之間也同樣有時(shí)間冗余。

(3)信息熵冗余。信源編碼時(shí)，當(dāng)分配給第i個(gè)碼元類的比特?cái)?shù)b(yi)＝－lbPi(Pi為第i個(gè)碼元類的概率)時(shí)，才能使編碼后的單位數(shù)據(jù)量等于其信源熵，即達(dá)到其壓縮極限。但實(shí)際中各碼元類的先驗(yàn)概率很難預(yù)知，比特分配不能達(dá)到最佳，因而使實(shí)際單位數(shù)據(jù)量大于信源熵，即存在信息熵冗余。

(4)視覺冗余。人眼對于圖像場的注意是非均勻的，人眼并不能察覺圖像場的所有變化。事實(shí)上人類視覺的一般分辨能力為26灰度等級，而一般圖像的量化采用的是28灰度等級，即存在著視覺冗余。

(5)聽覺冗余。人耳對不同頻率的聲音的敏感度是不同的，并不能察覺所有頻率的變化，因此存在聽覺冗余。

(6)其他冗余，包括結(jié)構(gòu)冗余、知識冗余等。

在實(shí)際編碼中，人們總是利用這些冗余進(jìn)行壓縮。例如圖2-1中，F(xiàn)1幀中有一輛汽車和一個(gè)路標(biāo)P，經(jīng)過時(shí)間T后，圖像F2仍包含以上兩個(gè)物體，只是小車向前行駛了一段路程。此時(shí)，F(xiàn)1和F2是時(shí)間相關(guān)的，后一幅圖像F2在參照圖像F1的基礎(chǔ)上只需很少數(shù)據(jù)量即可表示出來，從而減少了存儲空間，實(shí)現(xiàn)了數(shù)據(jù)壓縮。再比如人臉的圖像有固定的結(jié)構(gòu)，嘴的上方有鼻子，鼻子的上方有眼睛，鼻子位于臉的中線上，等等。根據(jù)已有的這些知識，可以構(gòu)造其基本模型，因而圖像的存儲只需要保存一些特征參數(shù)，從而可以大大減少數(shù)據(jù)量。

隨著對人類視覺系統(tǒng)和圖像模型的進(jìn)一步研究，人們可能會發(fā)現(xiàn)更多的冗余性，使圖像數(shù)據(jù)壓縮編碼的可行性越來越大，從而推動(dòng)圖像壓縮技術(shù)的進(jìn)一步發(fā)展。圖2-1時(shí)間冗余

多媒體數(shù)據(jù)壓縮編碼必須在保持信息源內(nèi)容不變或損失不大的前提下才有意義，這就必然涉及信息的度量問題。下面首先討論信源模型及其熵，然后介紹無失真編碼理論和有失真編碼理論。2.2多媒體數(shù)據(jù)壓縮理論基礎(chǔ)2.2.1信源模型及其熵

在信息論中，信息往往用隨機(jī)出現(xiàn)的符號來表示，由一系列的隨機(jī)變量所代表。輸出這些符號集的源為信源。由信源輸出的隨機(jī)符號，如果其取值于某一連續(xù)區(qū)間，則稱此源為連續(xù)信源；如果其取值于某一離散集合，則稱此源為離散信源；若有一部分取值于連續(xù)區(qū)間，另一部分取值于離散集合，則稱此源為混合信源。很多實(shí)際信源輸出的信息往往是由按一定概率選取的符號序列所組成的，所以可以看成時(shí)間上或空間上離散的一系列隨機(jī)變量，即隨機(jī)矢量。這樣，信源的輸出可以用M維隨機(jī)矢量X＝(X1，X2，…，XM)來描述，其中M為有限正整數(shù)。若隨機(jī)矢量X的每個(gè)隨機(jī)變量Xi(i＝1，2，…，M)都是取值離散的離散型隨機(jī)變量，且在任意兩個(gè)不同時(shí)刻Xi的概率分布都相同，則這樣的信源稱為離散平穩(wěn)信源。在離散平穩(wěn)信源情況下，若信源發(fā)出的一個(gè)個(gè)符號彼此是統(tǒng)計(jì)獨(dú)立的，即前一個(gè)符號的出現(xiàn)不會影響以后任何一個(gè)符號出現(xiàn)的概率，則該信源為離散無記憶信源；若信源在不同時(shí)刻發(fā)出的符號之間是相互依賴的，即在信源輸出的平穩(wěn)隨機(jī)序列X中，各隨機(jī)變量Xi之間是有依賴的，則該信源為離散有記憶信源。下面只討論離散無記憶信源的情況。

設(shè)離散無記憶信源X可發(fā)出的信息集合為A＝{ai|i＝1，2，…，m}，并且記字符ai出現(xiàn)的概率為P(ai)，簡記為Pi，那么按概率的公理化定義必有

0≤Pi≤1(i＝1，2，…，m) (2-1)

香農(nóng)信息論把字符ai出現(xiàn)的自信息量定義為

I(ai)＝－logPi (2-2)

上述公式中，對數(shù)的底不同，則計(jì)算的值不同。當(dāng)?shù)讛?shù)取大于1的整數(shù)r時(shí)，則自信息量的單位稱做r進(jìn)制信息單位。當(dāng)r＝2時(shí)，相應(yīng)的單位為比特；當(dāng)r＝e(自然對數(shù))時(shí)，相應(yīng)的單位稱為奈特(Nat)；當(dāng)r＝10時(shí)，相應(yīng)的單位稱為哈特(Hart)。在后面的公式中，取r＝2，log2用lb表示。對信源X的各符號的自信息量取統(tǒng)計(jì)平均，即ai的數(shù)學(xué)期望，可得平均信息量：

(2-3)

稱H(X)為信息源X的熵，單位為bit/字符，通常也稱為X的一階熵，它可以理解為信源X發(fā)出任意一個(gè)符號的平均信息量。假設(shè)離散無記憶信源發(fā)出兩個(gè)符號X和Y,X可發(fā)出的信息集合為A＝{ai|i＝1，2，…，m}，ai出現(xiàn)的概率為P(ai)，而Y可發(fā)出的信息集合為B＝{bj|j＝1，2，…，m}，bj出現(xiàn)的概率為P(bj)，則接收到該符號后所得到的平均信息量稱為聯(lián)合熵，定義為

(2-4)

其中，P(aibj)為符號ai和bj同時(shí)發(fā)生的聯(lián)合概率。由于X和Y相互獨(dú)立，因此

P(aibj)＝P(ai)·P(bj) (2-5)

則 H(X·Y)＝H(X)＋H(Y) (2-6)

可以將上面的結(jié)果推廣到多個(gè)符號的情況，得到如下結(jié)論：離散無記憶信源所產(chǎn)生的符號序列的熵等于各符號熵之和。下面給出一些定義和描述信源的性能指標(biāo)。

(1)聯(lián)合概率P(xi，yj)：聯(lián)合信源(X，Y)取值為(xi，yj)的概率。

(2)邊緣概率：

(2-7)

(2-8)

(3)條件概率：

(2-9)

(2-10)2.2.2無失真編碼理論

無失真編碼方法(或稱無損壓縮算法)是指編碼后的圖像可經(jīng)譯碼完全恢復(fù)為原圖像的壓縮編碼方法。在編碼系統(tǒng)中，無失真編碼也稱為熵編碼。

無失真編碼定理：對于離散信源X，對其編碼時(shí)每個(gè)符號能達(dá)到的平均碼長滿足以下不等式：

H(X)≤ ≤H(X)＋

(2-11)

式中， 為編碼的平均碼長，單位為每符號比特?cái)?shù)(b/符號)；

為任意小的正數(shù)；H(X)為信源X的信息熵。該定理一方面指出了每個(gè)符號平均碼長的下限為信源的熵，另一方面說明存在任意接近該下限的編碼。對于獨(dú)立信源，該定理既適用于單個(gè)符號編碼的情況，又適用于對符號塊編碼的情況。

無失真編碼定理指出了等于或接近信源的熵的編碼是可以實(shí)現(xiàn)的，但它并沒有告訴我們?nèi)绾卧O(shè)計(jì)這樣的編碼。通常，這樣的編碼可通過不等長編碼(或稱為變字長編碼)來實(shí)現(xiàn)。

變字長編碼在編碼時(shí)對概率大的符號用短碼，對概率小的符號用長碼，從而提高編碼效率。其編碼、譯碼過程都比較復(fù)雜。首先，編碼前要知道各符號的概率P(xi)，為了具有實(shí)用性，還要求碼字具有唯一可譯性和即時(shí)可譯性。此外，還要求輸入、輸出的速率匹配。構(gòu)造不等長碼的方法有很多種，其中以哈夫曼提出的編碼方法最佳，它在圖像編碼中經(jīng)常使用，后面會詳細(xì)介紹。2.2.3有失真編碼理論

失真不超過某給定條件下的編碼可稱為限失真編碼。能使限失真條件下比特?cái)?shù)最少的編碼則為最佳編碼。1948年香農(nóng)(Shannon)的經(jīng)典論文《通信的數(shù)學(xué)原理》中首次提到信息率失真函數(shù)的概念，1959年他又進(jìn)一步確立了率失真理論，從而奠定了信源編碼的理論基礎(chǔ)。在此，我們只討論離散無記憶信源的情況。

在實(shí)際應(yīng)用中，盡管信息提供的內(nèi)容很豐富，但人們由于各種因素的限制，并不能完全感覺到信息的內(nèi)容，因此一定程度的失真是允許的。那么，在給定的失真條件下，至少需要多大的碼率，才能保證不超過允許的失真呢？為了解答這個(gè)問題，首先引入條件信息量和互信息量。在此只考慮離散信源，設(shè)信源發(fā)出符號為xi，編碼輸出為yj，用P(xi,yj)表示聯(lián)合概率；用P(xi|yj)表示已知編碼輸出為yj，估計(jì)信源發(fā)出xi的條件概率；用Q(yj|xi)表示發(fā)出xi而編碼輸出為yj的概率。

定義條件信息量為

I(xi|yj)＝－logP(xi|yj) (2-12)

I(yj|xi)＝－logQ(yj|xi) (2-13)

它們的物理意義可類似于自信息量的解釋。

定義互信息量為

I(xi，yj)＝I(xi)－I(xi|yj) (2-14)式中，I(xi)是xi所含的信息量，I(xi|yj)表示已知yj后xi還保留的信息量。它們的差，即互信息量就代表了信源符號yj為xi所提供的信息量。

對于無損編碼，由于編碼前的符號xi與編碼后的符號yj之間存在一一對應(yīng)的關(guān)系，因此，P(xi|yj)＝1，Q(yj|xi)＝1，從而I(xi|yj)＝0，I(yj|xi)＝0，I(xi，yj)＝I(xi)，這表明yj為接收者提供了與xi相同的信息量。當(dāng)編碼允許失真后，兩個(gè)符號集失去了一一對應(yīng)的關(guān)系。這時(shí)，P(xi|yj)不等于1，I(xi|yj)也不等于零。因此可以說，互信息量是扣除了信道中的噪聲干擾或失真損失的信息量。平均互信息量定義為

(2-15)

可以證明：

I(X，Y)＝H(X)－H(X|Y) (2-16)

上式表示每個(gè)編碼符號為信源X提供的信息量。H(X)為信源的一階熵，H(X|Y)為條件熵，表示由編碼引入的對信源的不確定性，它是由于編碼造成的信息丟失。由式(2-2)、式(2-12)、式(2-14)得

(2-17)

將上式代入式(2-15)，并由式(2-8)和式(2-10)可得

(2-18)

從式(2-18)可見，平均互信息量由信源符號概率P(xi)、編碼輸出符號概率Q(yj)及已知信源符號出現(xiàn)的條件概率Q(yj|xi)所確定。在信源一定的條件下，P(xi)是確定的。編碼方法的選擇實(shí)際上是改變Q(yj|xi)，它同時(shí)也決定了引入失真的大小。我們希望找出在一定允許失真D條件下的最低平均互信息量，稱之為率失真函數(shù)，記為R(D)，即

R(D)是在平均失真小于允許失真D時(shí)能夠編碼的碼率下界。式中，D'代表平均失真，可將其寫為

其中，d(xi,yj)表示信源發(fā)出xi，而被編碼成yj時(shí)的信息量。可見，平均失真量D'是條件概率控制的量，故可記為D(Q)。把率失真函數(shù)寫成更為緊湊的式子：

這里，QD＝Q(D(Q)<D)，表示在所有允許失真范圍D內(nèi)的條件概率的集合，亦即各種編碼方法。

從上式我們可以看出，對于任意給定的失真度D，可能找到一個(gè)編碼方案，其編碼比特率任意接近R(D),而平均失真度任意接近D；反之，不可能找到一種編碼，使失真度不大于D時(shí)，其編碼比特率低于R(D)。這個(gè)結(jié)論已經(jīng)作為定理形式描述，稱為香農(nóng)的信源編碼的逆定理。研究率失真函數(shù)是為了解決在已知信源和允許失真度D的條件下，使信源傳送給接收端的信息量最小。也可以說在一定失真度D的條件下，盡可能用最少的碼符號來傳送信源消息，提高通信的效率。

2.3.1壓縮算法的分類

數(shù)據(jù)壓縮的方法有許多種，從不同的角度出發(fā)，有不同的分類方法。根據(jù)解碼后的數(shù)據(jù)與原始數(shù)據(jù)是否一致，壓縮方法可分為無損壓縮和有損壓縮兩大類。2.3壓縮算法的分類及性能評價(jià)無損壓縮又稱冗余度壓縮、信息保持編碼或熵編碼，是一種可逆編碼方法。該方法利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，去除信源在空間和時(shí)間上的相關(guān)性，解碼時(shí)可以完全恢復(fù)原始數(shù)據(jù)而不引入任何失真，但其壓縮率受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制。目前，常用的無損壓縮方法主要有Shannon-Fano編碼、哈夫曼編碼、行程(Run-length)編碼、LZW(Lempel-Ziv-Welch)編碼和算術(shù)編碼等。有損壓縮又稱信息量壓縮、失真度編碼或熵壓縮編碼。該方法利用了人類視覺和聽覺對某些頻率成分不敏感的特性，允許壓縮過程中損失一定的信息，解碼時(shí)雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的信息對理解原始信息影響較小，能夠獲得很大的壓縮比。有損壓縮適用于重構(gòu)信號不一定和原始信號完全相同的場合。如圖像和聲音的壓縮就可以采用有損壓縮，因?yàn)槠渲邪臄?shù)據(jù)往往多于視覺和聽覺系統(tǒng)所能接收的信息，丟掉一些數(shù)據(jù)不會影響對聲音或者圖像的理解。常見的有損壓縮方法主要有預(yù)測編碼、變換編碼、子帶編碼、統(tǒng)計(jì)編碼、基于模型的壓縮編碼、神經(jīng)網(wǎng)絡(luò)編碼、分形編碼和小波編碼等。2.3.2壓縮算法的性能評價(jià)

評價(jià)一種數(shù)據(jù)壓縮技術(shù)的性能好壞主要有三個(gè)關(guān)鍵的指標(biāo)：壓縮比、重現(xiàn)質(zhì)量、壓縮和解壓縮的速度。除此之外，主要考慮壓縮算法所需要的軟件和硬件環(huán)境。

1. 壓縮比

壓縮性能常常用壓縮比來定義，也就是壓縮過程中輸入數(shù)據(jù)量和輸出數(shù)據(jù)量之比。壓縮比越大，說明數(shù)據(jù)壓縮的程度越高。在實(shí)際應(yīng)用中，壓縮比可以定義為比特流中每個(gè)樣點(diǎn)所需要的比特?cái)?shù)。對于圖像信息，壓縮比可使用公式(2-19)計(jì)算：

(2-19)式中，Ls為原圖像的平均碼長，Lc為壓縮后圖像的平均碼長。

平均碼長L的計(jì)算公式為

(2-20)

其中，βi為數(shù)字圖像第i個(gè)碼字的長度(二進(jìn)制代碼的位數(shù))，其相應(yīng)的出現(xiàn)概率為Pi。

除壓縮比之外，編碼效率和冗余度也是衡量信源特性以及編/解碼設(shè)備性能的重要指標(biāo)，其定義如下。編碼效率：

(2-21)

其中，H為信息熵，計(jì)算公式如式(2-3)所示，L為平均碼長。冗余度：

(2-22)由信源編碼理論可知，當(dāng)L≥H條件時(shí)，可以設(shè)計(jì)出某種無失真編碼方法。如果所設(shè)計(jì)出的編碼的L遠(yuǎn)大于H，則表示這種編碼方法所占用的比特?cái)?shù)太多，編碼效率很低。例如，在圖像信號數(shù)字化過程中，采用PCM對每個(gè)樣本進(jìn)行編碼，其平均碼長L就遠(yuǎn)大于圖像的熵H。

因此，編碼后的平均碼長L等于或很接近H的編碼方法就是最佳編碼方案。此時(shí)并未造成信息的丟失，而且所占的比特?cái)?shù)最少，例如熵編碼。

如果L＜H時(shí)，必然會造成一定信息的丟失，從而引起圖像失真，這就是限失真條件下的編碼方案。

2.重現(xiàn)質(zhì)量

重現(xiàn)質(zhì)量是指比較重現(xiàn)時(shí)的圖像、聲音信號與原始圖像、聲音信號之間有多少失真，這與壓縮的類型有關(guān)。壓縮方法可以分為無損壓縮和有損壓縮。無損壓縮是指壓縮和解壓縮過程中沒有損失原始圖像和聲音的信息，所以對無損系統(tǒng)不必?fù)?dān)心重現(xiàn)質(zhì)量。有損壓縮雖然可獲得較大的壓縮比，但若壓縮比過高，還原后的圖像、聲音質(zhì)量就可能降低。圖像和聲音質(zhì)量的評估常采用主觀評估和客觀評估兩種方法。

以圖像信息壓縮為例。圖像的主觀評價(jià)采用5分制，其分值在1~5分情況下的主觀評價(jià)如表2-2所示。

表2-2圖像主觀評價(jià)性能表而客觀尺度通常有以下幾種：

均方誤差：

信噪比：

峰值信噪比：

其中，x(i)為原始圖像信號，

為重建圖像信號，xmax為x(i)的峰值，

為信號的方差，

為噪聲方差，

。

3. 壓縮和解壓縮的速度

壓縮與解壓縮的速度是兩項(xiàng)單獨(dú)的性能度量。在有些應(yīng)用中，如電視會議的圖像傳輸中，壓縮與解壓縮都需要實(shí)時(shí)進(jìn)行，這稱為對稱壓縮；在另一些應(yīng)用中，如多媒體CD-ROM的節(jié)目制作，壓縮可以用非實(shí)時(shí)壓縮，而只要解壓縮是實(shí)時(shí)的即可，這種壓縮稱為非對稱壓縮。從目前開發(fā)的壓縮技術(shù)看，一般壓縮的計(jì)算量要比解壓縮大。在靜止圖像中，壓縮速度沒有解壓縮速度要求嚴(yán)格。但對于動(dòng)態(tài)視頻的壓縮與解壓縮，速度問題是至關(guān)重要的。動(dòng)態(tài)視頻為保證幀間變化的連貫性要求，必須有較高的幀速。對于大多數(shù)情況來說，動(dòng)態(tài)視頻至少為15幀/s，而全動(dòng)態(tài)視頻則要求有25幀/s或30幀/s。因此，壓縮和解壓縮速度的快慢直接影響實(shí)時(shí)圖像通信的完成。

此外，還要考慮軟件和硬件的開銷。有些數(shù)據(jù)的壓縮和解壓縮可以在標(biāo)準(zhǔn)的PC硬件上用軟件實(shí)現(xiàn)，有些則因?yàn)樗惴ㄌ珡?fù)雜或者質(zhì)量要求太高而必須采用專門的硬件。這就需要在占用PC上的計(jì)算資源或者另外使用專門硬件的問題上作出選擇。

熵編碼是一種最佳的無損壓縮編碼方法，它所能達(dá)到的比特率的下界就是圖像的熵值。不同的熵編碼方法只是去除冗余數(shù)據(jù)的程度不同而已。常用的熵編碼有哈夫曼編碼、算術(shù)編碼和行程編碼。2.4熵編碼2.4.1哈夫曼編碼

哈夫曼(Huffman)編碼是由哈夫曼(D.S.Huffman)于1952年提出的一種不等長編碼方法。這種編碼的碼字長度的排列與符號的概率大小的排列是嚴(yán)格逆序的。理論上已經(jīng)證明，哈夫曼編碼的平均碼長最短，因此被稱為最佳碼。

1.編碼步驟

(1)將信源符號的概率由大到小排列；

(2)將兩個(gè)最小的概率組合相加，得到新概率；

(3)對未相加的概率及新概率重復(fù)(2)，直到概率達(dá)到1.0；

(4)將每對組合中概率小的指定為1,概率大的指定為0(或相反)；

(5)記下由概率1.0處到每個(gè)信源符號的路徑，對每個(gè)信源符號都寫出1、0序列,得到非等長的Huffman碼。

下面以一個(gè)具體的例子來說明其編碼方法，如圖2-2所示。

表2-3列出了各個(gè)信源符號的概率、哈夫曼編碼及碼長。表2-3各個(gè)信源符號的概率、哈夫曼編碼及碼長圖2-2哈夫曼(Huffman)編碼的示例

2.前例哈夫曼編碼的編碼效率計(jì)算

根據(jù)式(2-3)求出前例的信息熵為

根據(jù)式(2-20)求出平均碼字長度為

根據(jù)式(2-21)求出編碼效率為

可見哈夫曼編碼效率很高。

3. 哈夫曼編碼的特點(diǎn)

(1)編碼不唯一，但其編碼效率是唯一的。由于在編碼過程中，分配碼字時(shí)對0、1分配的原則可以不同，而且當(dāng)出現(xiàn)相同概率時(shí)，排序不固定，因此哈夫曼編碼不唯一。但對于同一信源而言，其平均碼長不會因?yàn)樯鲜鲈蚋淖?，因此編碼效率是唯一的。

(2)編碼效率高，但是硬件實(shí)現(xiàn)復(fù)雜，抗誤碼力較差。哈夫曼編碼是一種變長碼，因此硬件實(shí)現(xiàn)復(fù)雜，并且在存儲、傳輸過程中，一旦出現(xiàn)誤碼，易引起誤碼的連續(xù)傳播。

(3)編碼效率與信源符號概率分布相關(guān)。當(dāng)信源各符號出現(xiàn)的概率相等時(shí)，信源具有最大熵Hmax＝lbn，編碼為定長碼，其編碼效率最低。當(dāng)信源各符號出現(xiàn)的概率為2－n(n為正整數(shù))時(shí)，哈夫曼編碼效率最高，可達(dá)100%。由此可知，只有當(dāng)信源各符號出現(xiàn)的概率很不均勻時(shí)，哈夫曼編碼的編碼效果才顯著。因此，編碼前必須有信源的先驗(yàn)知識，這往往限制了哈夫曼編碼的應(yīng)用。

(4)只能用近似的整數(shù)位來表示單個(gè)符號。哈夫曼編碼只能用近似的整數(shù)位來表示單個(gè)符號而不是理想的小數(shù)，因此無法達(dá)到最理想的壓縮效果。2.4.2算術(shù)編碼

在信源概率分布比較均勻的情況下，哈夫曼編碼的效率較低，而此時(shí)算術(shù)編碼的編碼效率要高于哈夫曼編碼；同時(shí)，算術(shù)編碼又無需向變換編碼那樣，對數(shù)據(jù)進(jìn)行分塊。因此在JPEG擴(kuò)展系統(tǒng)中以算術(shù)編碼代替哈夫曼編碼。

算術(shù)編碼也是一種熵編碼。當(dāng)信源為二元平穩(wěn)馬爾可夫源時(shí)，可以將被編碼的信息表示成實(shí)數(shù)軸0～1之間的一個(gè)間隔。這樣，如果一個(gè)信息的符號越長，編碼表示它的間隔就越小，同時(shí)表示這一間隔所需的二進(jìn)制位數(shù)也就越多。下面對此作具體分析。

1. 碼區(qū)間的分割

設(shè)在傳輸任何信息之前信息的完整范圍是［0，1］，算術(shù)編碼在初始化階段預(yù)置一個(gè)大概率p和一個(gè)小概率q。如果信源所發(fā)出的連續(xù)符號組成序列為Sn，那么其中每個(gè)Sn對應(yīng)一個(gè)信源狀態(tài)。對于二進(jìn)制數(shù)據(jù)序列Sn，可以用C(S)來表示其算術(shù)編碼，可以認(rèn)為它是一個(gè)二進(jìn)制小數(shù)。隨著符號串中“0”、“1”的出現(xiàn)，所對應(yīng)的碼區(qū)間也發(fā)生相應(yīng)的變化。

如果信源發(fā)出的符號序列的概率模型為m階馬爾可夫鏈，那么表明某個(gè)符號的出現(xiàn)只與前m個(gè)符號有關(guān)，因此其所對應(yīng)的區(qū)間為［C(S)，C(S)＋L(S))，其中L(S)代表子區(qū)間的寬度，C(S)是該半開子區(qū)間中的最小數(shù)，而算術(shù)編碼的過程實(shí)際上就是根據(jù)符號出現(xiàn)的概率進(jìn)行區(qū)間分割的過程，如圖2-3所示。圖中假設(shè)“0”碼出現(xiàn)的概率為

，“1”碼出現(xiàn)的概率為

，因而

，

。如果在“0”碼后面出現(xiàn)的仍然是“0”碼，這樣，“00”出現(xiàn)的概率為

，即

。同理，如果第三位碼仍然為“0”碼，則“000”出現(xiàn)的概率為

，該區(qū)間的范圍為

。

圖2-3碼區(qū)間的分割

2.算術(shù)編碼規(guī)則

在進(jìn)行編碼過程中，隨著信息的不斷出現(xiàn)，子區(qū)間按下列規(guī)律減?。?/p>

新子區(qū)間的左端＝前子區(qū)間的左端＋當(dāng)前子區(qū)間的左端×前子區(qū)間長度

新子區(qū)間長度＝前子區(qū)間長度×當(dāng)前子區(qū)間長度

下面以一個(gè)具體的例子來說明算術(shù)編碼的編碼過程。

例已知信源分布為

，如果要傳輸?shù)臄?shù)據(jù)序列為

1011，寫出算術(shù)編碼過程。解(1)已知小概率事件

，大概率事件 。

(2)設(shè)C為子區(qū)間左端起點(diǎn)，L為子區(qū)間的長度。

根據(jù)題意，符號“0”的子區(qū)間為

，因此C＝0，L＝

；符號“1”的子區(qū)間為

，因此C＝

，L＝

。

(3)編碼計(jì)算過程。

編碼的結(jié)果應(yīng)位于子區(qū)間的頭尾之間，取值為0.011，則

算術(shù)編碼 011 占三位

原碼 1011 占四位

3. 算術(shù)編碼效率

(1)算術(shù)編碼的模式選擇直接影響編碼效率。算術(shù)編碼的模式有固定模式和自適應(yīng)模式兩種。固定模式是基于概率分布模型的；而在自適應(yīng)模式中，其各符號的初始概率都相同，但隨著符號出現(xiàn)的順序而改變。在無法進(jìn)行信源概率模型統(tǒng)計(jì)的條件下，非常適于使用自適應(yīng)模式的算術(shù)編碼。

(2)在信道符號概率分布比較均勻的情況下，算術(shù)編碼的編碼效率高于哈夫曼編碼。從前面關(guān)于積累概率p(S)的計(jì)算中可以看出，隨著信息碼長度的增加，表示間隔變小，而且每個(gè)小區(qū)間的長度等于序列中各符號概率p(S)。算術(shù)編碼是用小區(qū)間內(nèi)的任意點(diǎn)來代表這些序列的，設(shè)取L位編碼，則

其中，［X］代表取小于或等于X的最大整數(shù)。例如，在上例中

由上面的分析可見，對于長序列，p(S)必然很小，因此概率倒數(shù)的對數(shù)與L值幾乎相等，即取整數(shù)后所造成的差別很小，平均碼長接近序列的熵值，因此可以認(rèn)為概率達(dá)到匹配，其編碼效率很高。

(3)硬件實(shí)現(xiàn)時(shí)的復(fù)雜程度高。算術(shù)編碼的實(shí)際編碼過程也與上述計(jì)算過程有關(guān)，需設(shè)置兩個(gè)存儲器，起始時(shí)一個(gè)為“0”，另一個(gè)為“1”，分別代表空集和整個(gè)樣本空間的積累概率。隨后每輸入一個(gè)信源符號就更新一次，同時(shí)獲得相應(yīng)的碼區(qū)間。然后按前述的方法求出最后的碼區(qū)間，并在此碼區(qū)間上選定L值。解碼過程也是逐位進(jìn)行的。可見算術(shù)編碼的計(jì)算過程要比哈夫曼編碼的計(jì)算過程復(fù)雜，因而硬件實(shí)現(xiàn)電路也要復(fù)雜一些。2.4.3行程編碼

現(xiàn)實(shí)中有許多這樣的圖像，在一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的像素都具有相同的顏色值。在這種情況下就不需要存儲每一個(gè)像素的顏色值，而僅需存儲一個(gè)像素的顏色值，以及具有相同顏色的像素?cái)?shù)目即可；或者存儲一個(gè)像素的顏色值，以及具有相同顏色值的行數(shù)。這種壓縮編碼稱為行程編碼(RunLengthEncoding，RLE)。具有相同顏色并且是連續(xù)的像素?cái)?shù)目稱為行程長度。下面以兩值圖像為例進(jìn)行說明。兩值圖像是指圖像中的像素值只有兩種取值，即“0”和“1”，因而在圖像中這些符號會連續(xù)地出現(xiàn)。通常將連“0”這一段稱為“0”行程，而連“1”的一段則稱為“1”行程，它們的長度分別為L(0)和L(1)。往往“0”行程與“1”行程會交替出現(xiàn)，即第一行程為“0”行程，第二行程為“1”行程，第三行程又為“0”行程。

下面以一個(gè)具體的二值序列為例進(jìn)行說明。已知一個(gè)二值序列00101110001001…，根據(jù)行程編碼規(guī)則，可知其行程序列為21133121…。如果已知二值序列的起始比特為“0”，而且占2個(gè)比特，則行程序列的首位為2，又因?yàn)?個(gè)“0”行程之后必定為“1”行程，上述給出的二值序列只有一個(gè)1，因此第二位為1，后面緊跟的應(yīng)該是“0”行程，0的個(gè)數(shù)為一個(gè)，故第三位也為1，接下去是“1”行程，1的個(gè)數(shù)為3，所以第四位為3……依此類推，最終獲得行程編碼序列。可見當(dāng)圖像中具有相同灰度(或顏色)的圖像塊越大、越多時(shí)，壓縮的效果就越好；反之，當(dāng)圖像越復(fù)雜，即其中的顏色層次越多時(shí)，其壓縮效果越不好。因此對于復(fù)雜的圖像，通常采用行程編碼與哈夫曼編碼的混合編碼方式，即首先進(jìn)行二值序列的行程編碼，然后根據(jù)“0”行程與“1”行程長度的分布概率，再進(jìn)行哈夫曼編碼。以上是一個(gè)二值序列的行程編碼的例子，對于多元序列也同樣存在行程編碼。與二值序列的行程序列不同，在多元序列某個(gè)行程的前后所出現(xiàn)的符號是不確定的，需要增加一個(gè)標(biāo)志來說明后一行程的符號，但這樣一來，所增加的附加標(biāo)志就抵消了壓縮編碼的好處。

預(yù)測編碼的基本思想是分析信號的相關(guān)性，利用已處理的信號預(yù)測待處理的信號，得到預(yù)測值；然后僅對真實(shí)值與預(yù)測值之間的差值信號進(jìn)行編碼處理和傳輸，以達(dá)到壓縮的目的，并能夠正確恢復(fù)原信號。如在視頻編碼中，預(yù)測編碼可以去掉相鄰像素之間的冗余度，只對不能預(yù)測的信息進(jìn)行編碼。2.5預(yù)測編碼相鄰像素指在同一幀圖像內(nèi)上、下、左、右的像素之間的空間相鄰關(guān)系，也可以指該像素與相鄰的前幀、后幀圖像中對應(yīng)于同一位置上的像素之間時(shí)間上的相鄰關(guān)系。預(yù)測編碼的方法易于實(shí)現(xiàn)，編碼效率高，應(yīng)用廣泛，可以達(dá)到大比例壓縮數(shù)據(jù)的目的。預(yù)測編碼有線性預(yù)測和非線性預(yù)測兩類，目前應(yīng)用較多的是線性預(yù)測。線性預(yù)測法通常稱為差分脈沖編碼調(diào)制(DifferentialPulseCodeModulation，DPCM)。2.5.1差分脈沖編碼調(diào)制

差分脈沖編碼調(diào)制(DPCM)的中心思想是對信號的差值而不是對信號本身進(jìn)行編碼。這個(gè)差值是指信號值與預(yù)測值的差值。預(yù)測值可以由過去的采樣值進(jìn)行預(yù)測，其計(jì)算公式如下：

(2-23)

(2-24)

差分脈沖編碼調(diào)制就是將上述每個(gè)樣點(diǎn)的差值量化編碼，而后用于存儲或傳送。由于相鄰采樣點(diǎn)有較大的相關(guān)性，預(yù)測值常接近真實(shí)值，故差值一般都比較小，從而可以用較少的數(shù)據(jù)位來表示，這樣就減少了數(shù)據(jù)量。在接收端或數(shù)據(jù)回放時(shí)，可用類似的過程重建原始數(shù)據(jù)。差分脈沖編碼調(diào)制系統(tǒng)的方框圖如圖2-4所示。

圖2-4差分脈沖編碼調(diào)制系統(tǒng)

(2-25)

對式(2-25)中各個(gè)ai求導(dǎo)數(shù)并使方程等于0，最后解聯(lián)立方程可以求出ai。預(yù)測系數(shù)與輸入信號特性有關(guān)，也就是說，采樣點(diǎn)同其前面采樣點(diǎn)的相關(guān)性有關(guān)。只要預(yù)測系數(shù)確定，問題便可迎刃而解。通常一階預(yù)測系數(shù)ai的取值范圍為0.8～1。

DPCM編碼性能的優(yōu)劣，很大程度上取決于預(yù)測器的設(shè)計(jì)，而預(yù)測器的設(shè)計(jì)主要是確定預(yù)測器的階數(shù)N以及各個(gè)預(yù)測系數(shù)。階數(shù)N即公式(2-23)中的樣值個(gè)數(shù)。對于一般圖像，取N＝4就足夠了。當(dāng)N>5時(shí)，預(yù)測效果的改善程度已不明顯。由于在預(yù)測編碼中，接收端是以接收的前N個(gè)樣本為基準(zhǔn)來預(yù)測當(dāng)前樣本的，因而如果信號傳輸過程中一旦出現(xiàn)誤碼，就會影響后續(xù)像素的正確預(yù)測，從而出現(xiàn)誤碼擴(kuò)散現(xiàn)象?？梢姴捎妙A(yù)測編碼可以提高編碼效率，但它是以降低其系統(tǒng)性能為代價(jià)的。2.5.2自適應(yīng)差分脈沖編碼調(diào)制

為了進(jìn)一步提高編碼的性能，人們將自適應(yīng)量化技術(shù)和自適應(yīng)預(yù)測技術(shù)結(jié)合在一起，用于差分脈沖編碼調(diào)制中，從而實(shí)現(xiàn)了自適應(yīng)差分脈沖編碼調(diào)制(AdaptiveDifferencePulseCodeModulation，ADPCM)。ADPCM的簡化編碼原理如圖2-5所示。

圖2-5自適應(yīng)差分脈沖編碼調(diào)制的編碼原理自適應(yīng)量化的基本思路是：使量化間隔Δ的變化與輸入信號的方差相匹配，也就是使量化器階距隨輸入信號的方差而變化，且量化階距正比于量化器輸入信號的方差。自適應(yīng)量化的方式可以采用所謂的前向自適應(yīng)量化，也可以采用后向自適應(yīng)量化。無論使用哪種方式，都可以改善信號的動(dòng)態(tài)范圍和信噪比。2.5.3運(yùn)動(dòng)估計(jì)與補(bǔ)償

對于視頻圖像，當(dāng)圖像內(nèi)容變化或攝像機(jī)運(yùn)動(dòng)不劇烈時(shí)，前后幀圖像基本保持不變，相鄰幀圖像具有很強(qiáng)的時(shí)間相關(guān)性。如果能夠充分利用相鄰幀圖像像素進(jìn)行預(yù)測，將會得到比幀內(nèi)像素預(yù)測更高的預(yù)測精度，預(yù)測誤差也更小，可以進(jìn)一步提高編碼效率。這種基于時(shí)間相關(guān)性的相鄰幀預(yù)測方法就是幀間預(yù)測編碼。

在幀間預(yù)測編碼中，為了達(dá)到較高的壓縮比，最關(guān)鍵的就是要得到盡可能小的幀間誤差。在普通的幀間預(yù)測中，實(shí)際上僅在背景區(qū)進(jìn)行預(yù)測時(shí)可以獲得較小的幀間誤差。如果要對運(yùn)動(dòng)區(qū)域進(jìn)行預(yù)測，首先要估計(jì)出運(yùn)動(dòng)物體的運(yùn)動(dòng)矢量V，然后再根據(jù)運(yùn)動(dòng)矢量進(jìn)行補(bǔ)償，即找出物體在前一幀的區(qū)域位置，這樣求出的預(yù)測誤差才比較小。這就是運(yùn)動(dòng)補(bǔ)償幀間預(yù)測編碼的基本機(jī)理。簡而言之，通過運(yùn)動(dòng)補(bǔ)償，可減少幀間誤差，提高壓縮效率。理想的運(yùn)動(dòng)補(bǔ)償預(yù)測編碼應(yīng)由以下幾個(gè)步驟組成：

圖像劃分：將圖像劃分為靜止部分和運(yùn)動(dòng)部分。

運(yùn)動(dòng)檢測與估值：檢測運(yùn)動(dòng)的類型(平移、旋轉(zhuǎn)或縮放等)，并對每一個(gè)運(yùn)動(dòng)物體進(jìn)行運(yùn)動(dòng)估計(jì)，找出運(yùn)動(dòng)矢量。

運(yùn)動(dòng)補(bǔ)償：利用運(yùn)動(dòng)矢量建立處于前后幀的同一物體的空間位置對應(yīng)關(guān)系，即用運(yùn)動(dòng)矢量進(jìn)行運(yùn)動(dòng)補(bǔ)償預(yù)測。

預(yù)測編碼：對運(yùn)動(dòng)補(bǔ)償后的預(yù)測誤差、運(yùn)動(dòng)矢量等信息進(jìn)行編碼，作為傳送給接收端的信息。

由于實(shí)際的序列圖像內(nèi)容千差萬別，把運(yùn)動(dòng)物體以整體形式劃分出來是極其困難的，因此有必要采用一些簡化模型。例如把圖像劃分為很多適當(dāng)大小的小塊，再設(shè)法區(qū)分是運(yùn)動(dòng)的小塊還是靜止的小塊，并估計(jì)出小塊的運(yùn)動(dòng)矢量，這種方法稱為塊匹配法。目前塊匹配法已經(jīng)在H.261、H.263、MPEG-1以及MPEG-4等國際標(biāo)準(zhǔn)中被廣泛采用。2.5.4塊匹配運(yùn)動(dòng)估計(jì)

運(yùn)動(dòng)估計(jì)從實(shí)現(xiàn)技術(shù)上可以分為像素遞歸法(PixelRecursiveAlgorithm，PRA)和塊匹配法(BlockMatchingMotionEstimation，BMME)。像素遞歸法的基本思想是對當(dāng)前幀的某一像素在前一幀中找到灰度值相同的像素，然后通過該像素在兩幀中的位置差求解出運(yùn)動(dòng)位移。塊匹配的思想是將圖像劃分為許多互不重疊的子圖像塊，并且認(rèn)為子塊內(nèi)所有像素的位移幅度都相同，這意味著每個(gè)子塊都被視為運(yùn)動(dòng)對象。對于k幀圖像中的子塊，在k－1幀圖像中尋找與其最相似的子塊，這個(gè)過程稱為尋找匹配塊，并認(rèn)為該匹配塊在第k－1幀中所處的位置就是k幀子塊位移前的位置，這種位置的變化就可以用運(yùn)動(dòng)矢量來表示。

1. 基本思想及研究現(xiàn)狀

在一個(gè)典型的塊匹配算法中，一幀圖像被分割為M×N或者是更為常用的N×N像素大小的塊；在(N＋2w)×(N＋2w)大小的匹配窗中，將當(dāng)前塊與前一幀中對應(yīng)的塊相比較；基于匹配標(biāo)準(zhǔn)，找出最佳匹配，得到當(dāng)前塊的替代位置。常用的匹配標(biāo)準(zhǔn)有平均平方誤差(MeanSquareError,MSE)和平均絕對誤差(MeanAbsoluteError,MAE)，它們的定義如下：

(2-26)

(2-27)

其中，f(m,n)表示當(dāng)前塊在位置(m,n)處，f(m＋i,n＋j)表示相應(yīng)的塊在前一幀中的位置為(m＋i,n＋j)。全搜索算法(FullSearchAlgorithm，F(xiàn)SA)通過在搜索窗(N＋2w)×(N＋2w)內(nèi)計(jì)算所有的像素來尋找具有最小誤差的最佳匹配塊。對于當(dāng)前幀的一個(gè)待匹配塊的運(yùn)動(dòng)向量的搜索要計(jì)算(2w＋1)×(2w＋1)次誤差值，如圖2-6所示。由于全搜索算法的計(jì)算復(fù)雜度過大，近年來，快速算法的研究得到了廣泛的關(guān)注，研究人員提出了很多快速算法。

很多運(yùn)動(dòng)估計(jì)的快速算法從降低匹配函數(shù)復(fù)雜度和搜索點(diǎn)數(shù)等方面進(jìn)行了改進(jìn)。早期的運(yùn)動(dòng)估計(jì)改進(jìn)算法主要有三步搜索法(Three-StepSearch，TSS)、二維對數(shù)搜索法(Two-DimensionalLogarithmSearch，TDLS)和變方向搜索法(ConjugateDirectionSearch，CDS)。圖2-6塊匹配原理圖這些快速算法主要建立在誤差曲面呈單峰分布，存在唯一的全局最小點(diǎn)假設(shè)上。后來為了進(jìn)一步提高計(jì)算速度和預(yù)測矢量精度，利用運(yùn)動(dòng)矢量的中心偏移分布特性來設(shè)計(jì)搜索樣式，相繼又提出了新三步搜索法(NewThreeStepSearch，NTSS)、四步搜索法(Four-StepSearch，F(xiàn)SS)、梯度下降搜索法(BlockBasedGradientDescentSearch，BBGDS)、菱形搜索法(DiamondSearch，DS)、六邊形搜索法(HexagonBasedSearch，HEXBS)、運(yùn)動(dòng)矢量場自適應(yīng)搜索技術(shù)(MotionVectorFieldAdaptiveSearchTechnique，MVFAST)和預(yù)測運(yùn)動(dòng)矢量場自適應(yīng)搜索技術(shù)(PredictiveMotionVectorFieldAdaptiveSearchTechnique，PMVFAST)等算法。

實(shí)際上，快速運(yùn)動(dòng)估計(jì)算法就是在運(yùn)動(dòng)矢量的精確度和搜索過程中的計(jì)算復(fù)雜度之間進(jìn)行折中，尋找最優(yōu)平衡點(diǎn)。下面介紹簡單、常用的典型搜索算法。

2. 運(yùn)動(dòng)估計(jì)中的搜索算法

(1)三步搜索算法(TSS)。三步搜索算法第一步以w/2為步長，測試以原點(diǎn)為中心的8點(diǎn)。第二步以最小匹配誤差點(diǎn)為中心，步長折半，測試新的8點(diǎn)。第三步重復(fù)第二步得到最后的運(yùn)動(dòng)向量。TSS算法對于每一塊的測試點(diǎn)為固定的(9＋8＋8)＝25個(gè)。當(dāng)位移大小w＝7時(shí)，TSS相對于全搜索算法的加速因子為9。該算法示意圖如圖2-7所示，其中數(shù)字表示搜索順序，帶圈的數(shù)字表示搜索到的最小匹配誤差點(diǎn)。圖2-7TSS算法示意圖

(2)交叉搜索算法。1990年，Ghanbari提出了交叉搜索算法，它是在二維對數(shù)搜索算法(TDLS)及三步搜索算法(TSS)基礎(chǔ)上為進(jìn)一步減少計(jì)算量而發(fā)展起來的快速搜索法。二維對數(shù)搜索(TDLS)以跟蹤最小均方差所在的方向?yàn)榛舅枷?。初始化?jì)算5點(diǎn)，其中1點(diǎn)為原點(diǎn)，其他4點(diǎn)為(±w/2,±w/2)。再以相同的步長，以上一步搜索到的最小點(diǎn)為中心測試3點(diǎn)，然后步長折半重復(fù)以上步驟，直到步長大小變?yōu)?時(shí)為止。基于對數(shù)步長搜索策略，交叉搜索算法進(jìn)一步減少了測試點(diǎn)的個(gè)數(shù)，降低了計(jì)算的復(fù)雜度。該算法不同于其他的對數(shù)搜索方法的地方是，在每一個(gè)循環(huán)中，4個(gè)新增候選測試點(diǎn)的位置成X形交叉，而不是十字形交叉。設(shè)當(dāng)前搜索塊的左上角的坐標(biāo)為(i，j)，前一幀相應(yīng)的參考塊的坐標(biāo)為(0，0)，具體算法如下：

①與坐標(biāo)為(0，0)的參考塊計(jì)算塊誤差(BlockDistortionMeasure，BDM)，如果BDM小于預(yù)先設(shè)定的閾值，則認(rèn)為該塊為靜止的；否則，轉(zhuǎn)入②。

②初始化最小BDM的位置點(diǎn)(m,n)＝(0,0),令搜索步長p為最大運(yùn)動(dòng)范圍w的一半。

③移動(dòng)坐標(biāo)(i,j)到最小BDM的位置，即(i,j)＝(m,n)。

④以(i,j)、(i－p,j－p)、(i－p,j＋p)、(i＋p,j－p)四點(diǎn)當(dāng)中的最小值作為(m,n)。

⑤如果p＝1,轉(zhuǎn)⑥；否則，p＝p/2,轉(zhuǎn)③。⑥如果最后的最小值坐標(biāo)(m,n)為(i,j)、(i－1,j－1)、(i＋1,j＋1)之一，則轉(zhuǎn)⑦；否則，轉(zhuǎn)⑧。

⑦在(m,n)、(m－1,n)、(m,n－1)、(m＋1,n)、(m,n＋1)五點(diǎn)中尋找最小值(十字形交叉搜索)。

⑧在(m,n)、(m－1,n－1)、(m－1,n＋1)、(m＋1,n＋1)、(m＋1,n－1)五點(diǎn)中尋找最小值(X形交叉搜索)。

圖2-8給出了一個(gè)利用交叉搜索算法在w＝8的窗內(nèi)進(jìn)行搜索的例子。我們可以看到在每一步只測試4個(gè)新點(diǎn)，最后一步再多增加4個(gè)測試點(diǎn)，加上最初增加的測試點(diǎn)原點(diǎn)，總共測試了5＋4lbw個(gè)點(diǎn)。

圖2-8交叉搜索算法示意圖

(3)新三步搜索算法(NTSS)。圖2-9是NTSS算法的示意圖，圖中數(shù)字表示搜索順序，用圈圈出的數(shù)字表示搜索到的最小塊誤差(BlockDistortionMeasure，BDM)點(diǎn)。

圖2-9NTSS算法示意圖NTSS對于三步搜索算法的改進(jìn)之處在于對外圍大模板進(jìn)行搜索時(shí)，同時(shí)對內(nèi)側(cè)的小模板進(jìn)行搜索。外圍大模板由原點(diǎn)周圍步長為4的8個(gè)點(diǎn)組成，內(nèi)側(cè)小模板由原點(diǎn)以及原點(diǎn)周圍步長為1的9個(gè)點(diǎn)組成。NTSS在第1步就同時(shí)搜索大小模板，進(jìn)行塊匹配計(jì)算并比較，找到最小BDM點(diǎn)。如果最小BDM點(diǎn)是原點(diǎn)，則停止搜索。如果最小BDM點(diǎn)是原點(diǎn)外的小模板上的點(diǎn)，則以最小BDM為中心計(jì)算其8個(gè)鄰域點(diǎn)，找出最小BDM后停止搜索。如果最小BDM點(diǎn)為大模板中的點(diǎn)，則后面的步驟同TSS一樣，即步長減半搜索其8個(gè)鄰域點(diǎn)，直到步長為1時(shí)，找到最小BDM點(diǎn)。

NTSS算法最多要測試33個(gè)點(diǎn)。但是由于它采用了半途終止的策略，因此常常在第1步或是第2步就終止，即對于靜止的塊只要測試17個(gè)點(diǎn)，對于亞靜止的塊(運(yùn)動(dòng)范圍在±2個(gè)像素內(nèi))只要測試20或22個(gè)點(diǎn)。所以說NTSS對于估計(jì)靜止及亞靜止的塊的運(yùn)動(dòng)向量是非常有效的。NTSS相對于TSS的加速因子為18%。

圖2-10給出了一個(gè)圖像序列使用NTSS進(jìn)行運(yùn)動(dòng)估計(jì)的結(jié)果。運(yùn)動(dòng)估計(jì)是為運(yùn)動(dòng)補(bǔ)償作準(zhǔn)備的，運(yùn)動(dòng)估計(jì)精度越高，預(yù)測誤差信號差值就越小，幀間預(yù)測編碼效率也越高，所以運(yùn)動(dòng)估計(jì)精度是評價(jià)運(yùn)動(dòng)估計(jì)性能的一個(gè)重要指標(biāo)。運(yùn)動(dòng)估計(jì)是搜索最匹配的圖像塊，而搜索速度決定了編碼能否具有實(shí)時(shí)性，因此搜索速度也是其另一個(gè)重要指標(biāo)。

以上介紹的快速搜索算法都基于這樣一個(gè)假設(shè)：當(dāng)匹配點(diǎn)偏離最佳匹配點(diǎn)時(shí)，估計(jì)誤差值將呈單調(diào)上升的趨勢。因此，在搜索時(shí)，總是沿著估計(jì)誤差下降的方向搜索。然而，在搜索區(qū)內(nèi)的誤差值并不是簡單的單調(diào)，它可能有多個(gè)極值點(diǎn)存在，而且這種情況更為普遍。因此，快速算法在減少復(fù)雜度的同時(shí)，往往容易陷入局部最小點(diǎn)，這將導(dǎo)致匹配精度的下降。圖2-10NTSS對常用測試序列的估計(jì)結(jié)果

對圖像數(shù)據(jù)進(jìn)行某種形式的正交變換，并對變換后的數(shù)據(jù)進(jìn)行編碼，從而達(dá)到數(shù)據(jù)壓縮的目的，這就是變換編碼。無論是單色圖像還是彩色圖像，靜止圖像還是運(yùn)動(dòng)圖像，都可以用變換編碼進(jìn)行處理。變換編碼是一種被實(shí)踐證明了的有效的圖像壓縮方法，它是所有有損壓縮國際標(biāo)準(zhǔn)的基礎(chǔ)。2.6變換編碼變換編碼不直接對原圖像信號壓縮編碼，而首先將圖像信號映射到另一個(gè)域中，產(chǎn)生一組變換系數(shù)，然后對這些系數(shù)進(jìn)行量化、編碼、傳輸。在空間上具有強(qiáng)相關(guān)性的信號，反映在頻域上時(shí)能量常常被集中在某些特定的區(qū)域內(nèi)，或是變換系數(shù)的分布具有規(guī)律性。利用這些規(guī)律，在不同的頻率區(qū)域上分配不同的量化比特?cái)?shù)，可以達(dá)到壓縮數(shù)據(jù)的目的。

圖像變換編碼一般采用統(tǒng)計(jì)編碼和視覺心理編碼。前者是把統(tǒng)計(jì)上彼此密切相關(guān)的像素矩陣，通過正交變換變成彼此相互獨(dú)立，甚至完全獨(dú)立的由變換系數(shù)所構(gòu)成的矩陣。為了保證平穩(wěn)性和相關(guān)性，同時(shí)也為了減少運(yùn)算量，在變換編碼中，一般在發(fā)送端先將原始圖像分成若干個(gè)子像塊，然后對每個(gè)子像塊進(jìn)行正交變換。后者即對每一個(gè)變換系數(shù)或主要的變換系數(shù)進(jìn)行量化和編碼，量化特性和變換比特?cái)?shù)由人的視覺特性確定。前后兩種處理相結(jié)合，可以獲得較高的壓縮率。在接收端經(jīng)解碼、反量化后得到帶有一定量化失真的變換系數(shù)，再經(jīng)反變換就可恢復(fù)圖像信號。顯然，恢復(fù)圖像具有一定的失真，但只要系數(shù)選擇器和量化編碼器設(shè)計(jì)得好，這種失真可限制在允許的范圍內(nèi)。因此，變換編碼是一種限失真編碼。經(jīng)過變換編碼而產(chǎn)生的恢復(fù)圖像的誤差與所選用的正交變換的類型、圖像類型和變換塊的尺寸、壓縮方式和壓縮程度等因素有關(guān)。在變換方式確定以后，還應(yīng)選擇變換塊的大小。因?yàn)橹荒苡眯K內(nèi)的相關(guān)性來進(jìn)行壓縮，所以變換塊的尺寸選得太小，不利于提高壓縮比。當(dāng)N小到一定程度時(shí)，可能在塊與塊之間邊界上會存在被稱為“邊界效應(yīng)”的不連續(xù)點(diǎn)。對于離散余弦變換(DCT)，當(dāng)N<8時(shí)，邊界效應(yīng)比較明顯，所以應(yīng)選N≥8。變換塊選得越大，計(jì)入的相關(guān)像素也越多，壓縮比就會提高，但計(jì)算也變得更復(fù)雜，而且，距離較遠(yuǎn)的像素間的相關(guān)性減少，壓縮比提高不大。所以，一般選擇變換塊的大小為8×8或16×16。由于圖像內(nèi)容千變?nèi)f化，即圖像結(jié)構(gòu)各不相同，因而變換類型和圖像結(jié)構(gòu)的匹配程度決定了編碼的效率。非自適應(yīng)變換編碼與圖像數(shù)據(jù)的統(tǒng)計(jì)平均結(jié)構(gòu)特性匹配，而自適應(yīng)的變換編碼則與圖像的局部結(jié)構(gòu)特性匹配。

因?yàn)檎蛔儞Q的變換核(變換矩陣)是可逆的，且逆矩陣與轉(zhuǎn)置矩陣相等，能夠保證解碼運(yùn)算有解且運(yùn)算方便，所以變換編碼總是選用正交變換。正交變換的種類有多種，例如傅立葉變換、沃爾什—哈達(dá)瑪變換、哈爾變換、余弦變換、正弦變換、KarhunenLoeve變換(簡稱K-L變換)和小波變換等。其中K-L變換后的各系數(shù)相關(guān)性小，能量集中，舍棄低值系數(shù)所造成的誤差最小，但它存在著計(jì)算復(fù)雜、速度慢等缺點(diǎn)，因此一般只將它作為理論上的比較標(biāo)準(zhǔn)，即作為一種參照物，用來對一些新方法、新結(jié)果進(jìn)行分析和比較。由此可見，K-L變換的理論價(jià)值高于實(shí)際價(jià)值。由于離散余弦變換與K-L變換的性質(zhì)最為接近，且計(jì)算復(fù)雜度適中，具有快速算法等特點(diǎn)，因此離散余弦變換在圖像數(shù)據(jù)壓縮編碼中被廣泛采用。下面對離散余弦變換作簡要介紹。設(shè)f(x,y)是M×N子圖像的空域表示，則二維離散余弦變換定義為

(u＝0,1,…，M－1；v＝0，1，…，N－1)(2-28)

逆向余弦變換(IDCT)的公式為

(x＝0,1,…，M－1；y＝0，1，…，N－1)(2-29)

以上兩式中，c(u)和c(v)的定義為

二維DCT和IDCT的變換核是可分離的，即可將二維計(jì)算分解成一維計(jì)算，從而解決了二維DCT和IDCT的計(jì)算問題。空域圖像f(x，y)經(jīng)過式(2-28)正向離散余弦變換后得到的是一幅頻域圖像。當(dāng)f(x，y)是一幅M＝N＝8的子圖像時(shí)，其F(u,v)可表示為

(2-30)其中64個(gè)矩陣元素稱為f(x，y)的64個(gè)DCT系數(shù)。正向DCT變換可以看成是一個(gè)諧波分析器，它把f(x，y)分解成64個(gè)正交的基信號，分別代表著64種不同的頻率成分。第一個(gè)元素F00是直流系數(shù)(DC)，其他63個(gè)都是交流系數(shù)(AC)。矩陣元素的兩個(gè)下標(biāo)之和小者(即矩陣左上角部分)代表低頻成分，大者(即矩陣右下角部分)代表高頻成分。由于大部分圖像區(qū)域中相鄰像素的變化很小，因此大部分圖像信號的能量都集中在低頻成分，高頻成分中可能有不少數(shù)值為0或接近0值。圖2-11為DCT變換編碼的示例。(a)為原圖，將原圖分為8×8的塊進(jìn)行DCT變換，對于變換后的每個(gè)塊的64個(gè)系數(shù)只保留10個(gè)，其余的設(shè)為0。(b)為對每個(gè)塊進(jìn)行反變換后重建的圖像。從圖像中可以看出，雖然近85%的DCT系數(shù)被舍棄了，但是重建的圖像質(zhì)量只是略有下降。

圖2-11DCT變換編碼示例

20世紀(jì)80年代初期，國際學(xué)術(shù)界開展了矢量量化(VectorQuantization，VQ)技術(shù)的研究。矢量量化實(shí)際上是一種限失真編碼，它的理論基礎(chǔ)是香農(nóng)的速率失真理論，其基本原理是用碼本中與輸入矢量最匹配的碼字的索引(下標(biāo))代替輸入矢量進(jìn)行傳輸和存儲，而解碼時(shí)只需簡單地查表操作即可。實(shí)現(xiàn)矢量量化的關(guān)鍵技術(shù)有兩個(gè)：一個(gè)是如何設(shè)計(jì)一個(gè)優(yōu)良的碼本；另一個(gè)是量化編碼準(zhǔn)則。矢量量化編碼及解碼的原理如圖2-12所示。2.7矢量量化編碼圖2-12矢量量化編碼及解碼原理在發(fā)送端，先將信號的樣值數(shù)據(jù)序列按某種方式進(jìn)行分組，每個(gè)組假定有k個(gè)數(shù)據(jù)。這樣的一組數(shù)據(jù)就構(gòu)成了一個(gè)k維矢量，這個(gè)k維矢量稱為輸入矢量。把計(jì)算(訓(xùn)練)好的信號樣值矢量按照某種方法集中在一起所形成的表或字典稱為碼本。碼本中的每一個(gè)矢量視為一個(gè)碼字；其矢量維數(shù)與輸入矢量相同。在矢量量化編碼方法中，所傳輸?shù)牟皇菍?yīng)的矢量，而是對應(yīng)每個(gè)矢量在碼本中的下標(biāo)。由于下標(biāo)的數(shù)據(jù)相比于矢量本身來說要小得多，因此這種方式就實(shí)現(xiàn)了數(shù)據(jù)的壓縮。在圖2-12中，對應(yīng)編碼端的輸入信號序列是待編碼的樣值序列。將這些樣值序列按時(shí)間順序分成相等長度的段，每一段含有若干個(gè)樣值，每一段就構(gòu)成了一組數(shù)據(jù)；這樣一組數(shù)據(jù)就形成了一個(gè)矢量，對應(yīng)的很多組就會有很多的矢量。搜索的目的是要在事先計(jì)算(或叫訓(xùn)練)好的矢量碼本中找到一個(gè)與輸入矢量最接近的碼字。搜索就是將輸入矢量與矢量碼本中的碼字逐個(gè)進(jìn)行比較，比較的結(jié)果用某種誤差的方式來表示。用比較結(jié)果誤差最小的碼字來代替輸入的矢量，就是輸入的最佳量化值。每一個(gè)輸入矢量都用搜索到的最佳量化值來表示，進(jìn)行編碼時(shí)，只需對碼本中最佳量化值的位置(用下標(biāo)來表示)進(jìn)行編碼就可以了，也就是說在信道中傳輸?shù)牟皇谴a本中對應(yīng)的碼字本身，而是對應(yīng)碼字的下標(biāo)。顯然，與傳送原始數(shù)據(jù)相比，傳送下標(biāo)的數(shù)據(jù)量要小很多，這樣就實(shí)現(xiàn)了數(shù)據(jù)壓縮的目的。在解碼端，有一個(gè)與編碼端完全一樣的矢量碼本。當(dāng)解碼端收到發(fā)送端傳來的矢量下標(biāo)時(shí)，就可以根據(jù)下標(biāo)的數(shù)值，在解碼端的矢量碼本中搜索到相應(yīng)的碼字，以此碼字作為重建數(shù)據(jù)。

在對碼本的描述中，構(gòu)成碼本的碼字的數(shù)量稱為碼本的長度，用N來表示，則每個(gè)碼字的位置(即其下標(biāo))可以用lbN的二進(jìn)制位來表示，每個(gè)碼字是由k個(gè)原始數(shù)據(jù)構(gòu)成的。所以，矢量量化編碼的編碼速率可以低到 lbN。假設(shè)k＝16，表示每個(gè)碼字是由16個(gè)樣值數(shù)據(jù)構(gòu)成的一個(gè)矢量；N＝256，表示碼本的長度是256，碼本的下標(biāo)用二進(jìn)制來表示，共有l(wèi)b256＝8bit。由于對每組數(shù)據(jù)只需要傳送下標(biāo)，假定此時(shí)碼本已經(jīng)構(gòu)造好，則比特率 lbN＝ lb256＝0.5bit/sample。

矢量碼本的構(gòu)造即設(shè)計(jì)一個(gè)優(yōu)良的碼本是矢量量化編碼的關(guān)鍵技術(shù)之一,一般可通過反復(fù)迭代、不斷修正的方法完成。目前最常用的是一種稱為LBG的算法。這個(gè)算法是三位學(xué)者Y.Linde、A.Buzo和R.M.Gray共同提出的，故以他們的名字命名。采用LGB算法的步驟為：

(1)采集用于構(gòu)造碼本的訓(xùn)練數(shù)據(jù)。數(shù)據(jù)越多，采集對象越廣泛，則訓(xùn)練出的碼本越好。當(dāng)然，數(shù)據(jù)越多，訓(xùn)練時(shí)間越長，因而必須在性能和訓(xùn)練代價(jià)之間尋求一個(gè)折中。

(2)構(gòu)造初始碼本?？捎迷S多方法構(gòu)造初始碼本，例如常用的隨機(jī)碼本、白噪聲碼本等。

(3)訓(xùn)練數(shù)據(jù)對已有的碼本進(jìn)行矢量量化編碼，對每個(gè)碼字形成數(shù)據(jù)聚類。

(4)根據(jù)量化得到的聚類結(jié)果修正碼字，即尋找每一類的新的代表性碼字。

(5)判斷(3)中的量化編碼誤差是否小于規(guī)定數(shù)值，或者迭代次數(shù)是否超過規(guī)定值。若是，訓(xùn)練結(jié)束；否則，轉(zhuǎn)(3)繼續(xù)。矢量量化編碼的關(guān)鍵技術(shù)的另一個(gè)方面是量化編碼準(zhǔn)則問題，這與被編碼對象的特性有關(guān)。對于圖像信息，兩矢量間最常用的誤差測度是均方誤差，相當(dāng)于兩者之間歐幾里德(Euclid)距離的平方。該誤差雖不完全和視覺結(jié)果一致，但由于計(jì)算簡單而得到廣泛應(yīng)用。

2.8.1小波變換編碼

1.小波變換

近年來，小波變換作為一種數(shù)學(xué)工具廣泛應(yīng)用于圖像紋理分析、圖像編碼、計(jì)算機(jī)視覺、模式識別、語音處理、地震信號處理、量子物理以及眾多非線性科學(xué)領(lǐng)域，被認(rèn)為是近年來分析工具及方法上的重大突破。2.8壓縮編碼新技術(shù)原則上講，凡是使用傅立葉分析的地方，都可以用小波分析取代。小波分析優(yōu)于傅立葉分析的地方是它在時(shí)域和頻域同時(shí)具有良好的局部化性質(zhì)，而且由于對高頻成分采用逐漸精細(xì)的時(shí)域或空域(對圖像信號處理)取樣步長，因而可以聚焦到分析對象的任意細(xì)節(jié)。小波分析的這一特性被譽(yù)為“數(shù)學(xué)顯微鏡”。不僅如此，小波變換還有許多優(yōu)異的性能，總結(jié)如下：

小波變換是一個(gè)滿足能量守恒方程的線性變換，能夠?qū)⒁粋€(gè)信號分解成其對空間和時(shí)間的獨(dú)立貢獻(xiàn)，同時(shí)又不丟失原始信號所包含的信息。

小波變換相當(dāng)于一個(gè)具有放大、縮小和平移等功能的數(shù)學(xué)顯微鏡，通過檢查不同放大倍數(shù)下信號的變化來研究其動(dòng)態(tài)特性。

小波函數(shù)簇(即通過一個(gè)基本小波函數(shù)在不同尺度下的平移和伸縮而構(gòu)成的一簇函數(shù)，用以表示或逼近一個(gè)信號或一個(gè)函數(shù))的時(shí)間和頻率窗的面積較小，且在時(shí)間軸和頻率軸上都很集中，即小波變換后系數(shù)的能量較為集中。

小波變換的時(shí)間、頻率分辨率的分布非均勻性較好地解決了時(shí)間和頻率分辨率的矛盾，即在低頻段用高的頻率分辨率和低的時(shí)間分辨率(寬的分析窗口)，而在高頻段則用低的頻率分辨率和高的時(shí)間分辨率(窄的分析窗口)，這種變焦特性與時(shí)變信號的特性一致。

小波變換可以找到正交基，從而可方便地實(shí)現(xiàn)無冗余的信號分解。

小波變換具有基于卷積和正交鏡像濾波器組(QWF)的塔形快速算法，易于實(shí)現(xiàn)。該算法在小波變換中的地位相當(dāng)于FFT在傅立葉變換中的地位。

小波變換也可以分為連續(xù)小波變換(有的文獻(xiàn)中也稱為積分小波變換)和離散小波變換兩類。

(2-31)

小波逆變換為

(2-32)

上面兩式中：a,b∈R，a≠0，Ψb,a(x)是由基本小波通過

伸縮和平移而形成的函數(shù)簇，

為Ψb,a的共軛復(fù)數(shù)。常見的基本小波有：

(1)高斯小波：

(2)(3)墨西哥帽狀小波：

如果f(x)是離散的，記為f(k)，則離散小波變換為

(2-33)

相應(yīng)地，小波逆變換的離散形式為

(2-34)

式(2-33)和式(2-34)中,Ψm,n(k)是Ψa,b(x)對a和b按a＝am0，b＝nb0am0取樣而得到的，即

其中，a0>1,b0∈R,m,n∈Z。

2. 小波變換圖像編碼

小波變換圖像編碼的主要工作是選取一個(gè)固定的小波基，對圖像作小波分解，在小波域內(nèi)研究合理的量化方案、掃描方式和熵編碼方式。其關(guān)鍵問題是怎樣結(jié)合小波變換域的特性，提出有效的處理方案。一般而言，小波變換的編/解碼具有如圖2-13所示的統(tǒng)一框架結(jié)構(gòu)。

熵編碼主要有游程編碼、哈夫曼編碼和算術(shù)編碼。而量化是小波編碼的核心，其目的是更好地進(jìn)行小波圖像系數(shù)的組織。圖2-13小波編/解碼框圖小波變換采用二維小波變換快速算法，就是以原始圖像為初始值，不斷將上一級圖像分解為四個(gè)子帶的過程。每次分解得到的四個(gè)子帶圖像，分別代表頻率平面上不同的區(qū)域，它們分別含有上一級圖像中的低頻信息和垂直、水平及對角線方向的邊緣信息。從多分辨率分析出發(fā)，一般每次只對上一級的低頻子圖像進(jìn)行再分解。圖2-14中給出了對實(shí)際圖像進(jìn)行一級小波分解的實(shí)例。采用可分離濾波器的形式很容易將一維小波推廣到二維，以用于圖像的分解和重建。二維小波變換用于圖像編碼，實(shí)質(zhì)上相當(dāng)于分別對圖像數(shù)據(jù)的行和列進(jìn)行一維小波變換。圖2-15給出了四級小波分解示意圖。圖中HHj相當(dāng)于圖像分解后的

分量，LHj相當(dāng)于

分量，HLj相當(dāng)于

分量。這里H表示高通濾波器，L表示低通濾波器。圖2-14對實(shí)際圖像進(jìn)行一級小波分解的實(shí)例圖2-15四級小波分解示意圖以四級小波分解為例，小波變換將圖像信號分割成三個(gè)高頻帶系列HHj、LHj、HLj和一個(gè)低頻帶LL4。圖像的每一級小波分解總是將上級低頻數(shù)據(jù)劃分為更精細(xì)的頻帶。其中HLj是通過先將上級低頻圖像數(shù)據(jù)在水平方向(行方向)低通濾波后，再經(jīng)垂直方向(列方向)高通濾波而得到的，因此，HLj頻帶中包括了更多垂直方向的高頻信息。相應(yīng)地，在LHj頻帶中則主要是原圖像水平方向的高頻成分，而HHj頻帶是圖像中對角方向高頻信息的體現(xiàn)，尤其以45°或135°的高頻信息為主。對一幅圖像來說，其高頻信息主要集中在邊緣、輪廓和某些紋理的法線方向上，代表了圖像的細(xì)節(jié)變化。在這種意義上看，可以認(rèn)為小波圖像的各個(gè)高頻帶是圖像中邊緣、輪廓和紋理等細(xì)節(jié)信息的體現(xiàn)，并且各個(gè)頻帶所表示的邊緣、輪廓等信息的方向是不同的。其中，HLj表示了垂直方向的邊緣、輪廓和紋理，LHj表示的是水平方向的邊緣、輪廓和紋理，而對角方向的邊緣、輪廓等信息則集中體現(xiàn)在HHj頻帶中。小波變換應(yīng)用于圖像的這一特點(diǎn)表明小波變換具有良好的空間方向選擇性，與HVS(人眼的視覺特性)十分吻合，我們可以根據(jù)不同方向的信息對人眼作用的不同來分別設(shè)計(jì)量化器，從而得到很好的效果。小波變換的這種方向選擇性是DCT變換所沒有的。經(jīng)小波變換后的圖像的各個(gè)頻帶分別對應(yīng)了原圖像在不同尺度、最小分辨率下的細(xì)節(jié)以及一個(gè)由小波變換分解級數(shù)決定的最小尺度和最小分辨率下對原始圖像的最佳逼近。以四級分解為例，最終的低頻帶LL4是圖像在尺度為1/16、分辨率為1/16時(shí)的一個(gè)逼近，圖像的主要內(nèi)容都體現(xiàn)在這個(gè)頻帶的數(shù)據(jù)中；HHj、LHj、HLj則分別是圖像在尺度為1/2j、分辨率為1/2j(j＝1,2,3,4)下的細(xì)節(jié)信息，而且分辨率越低，其中有用信息的比例也越高。從多分辨率分析的角度考慮小波圖像的各個(gè)頻帶時(shí)，這些頻帶之間并不是純粹無關(guān)的。特別是對于各個(gè)高頻帶，由于它們是圖像同一個(gè)邊緣、輪廓和紋理信息在不同方向、不同尺度和不同分辨率下由細(xì)到粗的描述，因此它們之間必然存在著一定的關(guān)系，其中很顯然的是這些頻帶中對應(yīng)邊緣、輪廓的相對位置都應(yīng)是相同的。此外，低頻小波子帶的邊緣與同尺度下高頻子帶中所包含的邊緣之間也有對應(yīng)關(guān)系。小波變換應(yīng)用于圖像的這種對邊緣、輪廓信息的多分辨率描述給我們較好地編碼這類信息提供了基礎(chǔ)。由于圖像的邊緣、輪廓類信息對人眼觀測圖像時(shí)的主觀質(zhì)量影響很大，因此這種機(jī)制無疑會使編碼圖像在主觀質(zhì)量上得到改善。從以上分析可以看出，小波變換的本質(zhì)是采用多分辨率或多尺度的方式分析信號，非常適合視覺系統(tǒng)對頻率感知的對數(shù)特性。因此，從本質(zhì)上說，小波變換非常適合于圖像信號的處理。利用小波變換對圖像進(jìn)行壓縮的原理與子帶編碼方法是十分相似的，即將原圖像信號分解成不同的頻率區(qū)域(在對原圖像進(jìn)行多次分解時(shí)，總的數(shù)據(jù)量與原數(shù)據(jù)量一樣，不增不減)，然后根據(jù)HVS(人眼的視覺特性)及原圖像的統(tǒng)計(jì)特性，對不同的頻率區(qū)域采取不同的壓縮編碼手段，從而使圖像數(shù)據(jù)量減少，在保證一定的圖像質(zhì)量的前提下，提高壓縮比。由于小波變換是一種全局變換，因此可免除DCT之類正交變換中產(chǎn)生的“方塊效應(yīng)”，其主觀質(zhì)量較好。鑒于此，小波圖像編碼在較高壓縮比的圖像編碼領(lǐng)域很受重視，MPEG-4和JPEG2000等國際圖像編碼標(biāo)準(zhǔn)均采用了小波編碼方法。2.8.2分形編碼

經(jīng)典的幾何學(xué)一般適用于處理比較規(guī)則和簡單的形狀。但是自然界的實(shí)際景象絕大部分卻是由非常不規(guī)則的形狀組成的曲線，很難用一個(gè)數(shù)學(xué)表達(dá)式來表示。在這樣的情況下，提出了分形幾何學(xué)。

分形幾何學(xué)是由數(shù)學(xué)家Mandelbort于1973年提出的。分形的含義是某種形狀、結(jié)構(gòu)的一個(gè)局部或片斷。它可以有多種大小、尺寸的相似形。例如樹，樹干分為枝，枝又分枝，直至最細(xì)小的枝杈。這些分枝的方式、樣子都類似，只有大小、規(guī)模不同。再如綿延無邊的海岸線，無論在什么高度、何種分辨率條件下去觀看它的外貌，其形狀都是相似的。當(dāng)在更高的分辨率條件下去觀看它的外貌時(shí)，雖會發(fā)現(xiàn)一些前面不曾見過的新的細(xì)節(jié)，但這些新出現(xiàn)的細(xì)節(jié)和整體上海岸線的外貌總是相似的。也就是說，海岸線形狀的局部和其總體具有相似性。對于這類圖形，自相似性是其最重要的性質(zhì)。分形就是指那些沒有特征長度的圖形的總稱。分形還沒有明確的定義，但是分形集合一般具有下述特征：

· 該集合具有精細(xì)結(jié)構(gòu)，在任意小的尺度內(nèi)包含整體。

· 分形集很不規(guī)則，其局部或整體均無法用傳統(tǒng)的幾何方法進(jìn)行描述、逼近或度量。

· 通常分形集都有某種自相似性，表現(xiàn)在局部嚴(yán)格近似或統(tǒng)計(jì)意義下與整體相似。

· 分形集的分形維數(shù)一般大于其拓?fù)渚S數(shù)。

· 在很多情況下，分形可以用簡單的規(guī)則逐次迭代生成。只要符合上述特征，即可認(rèn)為是一個(gè)分形圖形或集合。因此從分形的角度看，許多視覺上感覺非常復(fù)雜的圖像其信息量并不大，可以用算法和程序集來表示，再借助計(jì)算機(jī)可以顯示其結(jié)合狀態(tài)，這就是可以用分形的方法進(jìn)行圖像壓縮的原因。

分形最顯著的特點(diǎn)是自相似性，即無論幾何尺度怎樣變化，景物的任何一小部分的形狀都與較大部分的形狀極其相似。這種尺度不變性在自然界中廣泛存在。圖2-16是用計(jì)算機(jī)生成的分形圖?？梢哉f分