3.8 小波變換編碼

小波變換與正交變換類似，是對信號進行分析的一種工具。我們知道，信號經傅氏變換（或余弦變換）后被分解成許多不同頻率的分量，即分析的結果在頻域內有精細的分辨率；但是從理論上講正弦波在時域（空間域）上是無限伸展的函數，因此傅氏分析在時域上不具有分辨能力，它只能刻畫信號在整個時間域（－∞，＋∞）上的頻譜特性，而不能反映信號在時間的局部區域上的頻率特征。與傅氏分析不同，小波分析在時域和頻域上同時具有良好的局部化性質，可以通過伸縮和平移對信號進行多尺度分析，解決傅氏變換等無法解決的許多問題。小波變換也因此被譽為“數學顯微鏡”。

3.8.1 多尺度分析

設函數Ψ∈L2（R），R為實數集，若Ψ滿足允許條件：

其中為Ψ（x）的傅氏變換，則稱Ψ為基小波，或母小波。由允許條件可知Ψ滿足）＝0和＝0，因此Ψ實質上為一帶通濾波器。

相應于Ψ的小波變換為

而

稱為小波，不難看出它是母小波經平移和伸縮后的結果，其中a和b分別為伸縮及平移因子。若將a，b離散化（a＝a0m，b＝nb0a0m），就可以得到離散的小波函數，例如取a0＝2，b0＝1時，就得到一個二進小波，，m，n∈Z，Z為整數集。二進小波變換是數字圖像處理中最常用的一類小波。

由（3-118）式可得，二進小波變換的變換系數為

由小波系數重構的原始信號則為

（3-120）式所示的變換稱為小波級數，其中小波系數為離散的，但信號f（x）仍為連續函數。當輸入信號f（x）和小波伸縮及平移因子（a和b）均為離散時，則變換稱為離散小波變換DWT（Discrete Wavelet Transform）。

設平方可積函數空間L2（R）上的閉子空間序列｛Vm｝，m∈Z，若滿足：

①…V1V0V－1…，即每一個子空間都包含在下一個尺度（分辨率增加一倍）的子空間內；

②＝L2（R），即子空間的并集在L2（R）中是稠密的；

③（∩m∈ZVm）＝0，即L2（R）中的每一個非零f（x）都具有非零尺度，當m→∞時，它的投影f（m）（x）在L2（R）意義上收斂于0；

④f（x）∈Vm→f（2x）∈Vm－1，m∈Z，即子空間Vm中的函數尺度增加一倍，則成為較高尺度Vm－1內的函數；

⑤f（x）∈Vmf（x-2mn）∈Vm，m，n∈Z，即Vm中的函數平移后仍在此子空間內（分辨率不變）；

⑥存在函數Φ（x）∈L2（R），使得｛Φ0，n（x）：n∈Z｝構成V0的一組標準正交基，其中Φm，n（x）＝；

則｛Vk｝形成一個二進多尺度分析，Φ（x）稱為尺度函數（Scalingfunction）。

由④、⑤、⑥可知，固定m，｛Φm，n（x）：n∈Z｝構成了Vm的一組正交基。Φ（x）的存在性也是顯而易見的，例如取Φ（x）區間[0，1]上的示性函數，即當x∈[0，1]時，Φ（x）＝1，其他情況Φ（x）＝0），就構成了V0的一組標準正交基。

當一組閉子空間序列滿足上述（1）～（6）時，可以證明存在L2（R）的一組小波正交基｛Ψm，n（x）：m，n∈Z｝，使得｛Ψm，n（x）：n∈Z｝為Vm－1中關于Vm的正交補空間Wm的一組標準正交基，即

既然m是任意整數，因此有

我們還可以以此類推，因此由多尺度分析可得或。

上面的式子說明，某一子空間中的任意函數（信號）可以分解為在較低尺度子空間的該信號的一個近似值，再加上一系列由小波分解產生的函數，后者可以認為是信號在Wm上的投影，代表了信號取近似值后損失的細節信息。

可以證明，尺度函數與小波函數之間存在雙尺度關系：

｛Ψm，n（x）：m，n＝∈Z｝構成L2（R）的標準正交小波基，也就是說，通過多尺度分析的尺度函數Φ（x）可以構造標準正交母小波Ψ（x）。（3-124）式和（3-125）式是下一節介紹的級聯算法的一個基礎，其中｛hn｝和｛gn｝是對應的數字低通濾波器和高通濾波器的沖激響應。

3.8.2 二進小波變換

1.二進小波分解

設｛c0，n｝，L0≤n≤L1為初始信號，｛hn｝和｛gn｝分別為二進小波分解低通濾波器和高通濾波器，也稱為分析濾波器，則有小波分解公式：

其中｛cm，n｝為第m次小波分解后所得到的低通信號，即在Vm上信號的近似值；｛dm，n｝為相應的高通信號，即在Wm上的細節信息。由于二進小波分解的每一個尺度分辨率降低一倍，所以兩個輸出信號分別以簡單的“2抽1”方式進行下取樣，然后對于在m尺度上的信號近似值cm，n進行m＋1尺度上的繼續分解……圖3-35的左側給出了一個三層的級聯分解過程。

2.二進小波重構

設和分別為二進小波重構低通濾波器和高通濾波器，也稱為綜合濾波器，m次小波分解后的信號如（3-126）式和（3-127）式，則有小波重構公式：

圖3-35右側給出了信號的重構過程。

對于正交小波，重構濾波器與分解濾波器是相同的。但是，由于對稱的正交小波只有簡單的Haar小波，而對稱小波濾波器在數字信號處理中具有保持線性相位和降低小波變換復雜度等優勢，所以在進行數字濾波時往往采用對稱雙正交小波濾波器，常用的有Daubechies5-3濾波器組和9-7濾波器組。

3.二維信號的小波分解

對于二維圖像信號的小波分解，通常先對二維信號按行做一維小波分解，然后再按列做一維小波分解。重構時，依次進行相應的列信號重構與行信號重構即可恢復原信號。

圖3-36（a）表示出二維小波分解過程。行方向分解生成左邊為低通子帶、右邊為高通子帶的中間結果；再經列方向分解后形成LL、LH、HL和HH4個子帶，其中LL是原始圖像的粗略近似，LH、HL和HH分別包含水平、垂直和45°傾斜的高頻分量。圖（b）給出兩層分解的子帶分布情況；圖（c）則給出一個實際圖像經過2層小波分解后的結果。由圖（c）看出，經小波變換后能量多集中在LL子帶內。

圖3-36 二維信號的小波分解

3.8.3 變換系數的排序和編碼

經小波變換后信號能量已經集中在少數系數上，將幅值很小的其他系數忽略（量化到0），則可達到數據壓縮的目的。不過在利用小波變換進行圖像編碼時一個值得注意的問題是，量化后的變換系數矩陣是一個具有少量非零值和大量零值的稀疏矩陣，在將此矩陣轉換成一維序列時，如何有效地組織非零系數和有效地表達零系數所在的位置，對數據壓縮的效率有重要的影響。本節討論與此有關的問題。

1.嵌入零樹小波編碼

人們發現，如果低頻子帶中某個系數為非零值，則在高頻子帶對應位置上的系數也為非零值的概率很大。根據這個特點，Lewis和Knowles在1992年提出了小波零樹編碼算法。在小波零樹編碼算法中，圖像經過N層離散二維小波變換后得到小波系數，這些系數按照子帶的相同方向形成小波樹結構。圖3-37為圖像經過三層離散二維小波變換后形成的小波樹結構示意圖。其中：

①低頻子帶LL3的每一個小波系數為樹的根節點，它在同層小波變換的高頻子帶HL3、LH3和HH3中相同空間位置上均有一個子節點；

②每個高頻子帶的小波系數在同方向較高頻子帶上具有4個子節點；

③最高頻子帶的每個小波系數沒有子節點，因此也被稱為葉節點；

④父節點是與子節點相對的一個稱呼，B是A的子節點，則稱A為B的父節點；

⑤一個節點的子節點及其子節點的子節點等稱為該節點的后代；

⑥一個節點的父節點及父節點的父節點等稱為該節點的祖先；

⑦小波系數與它的后代組成一個小波樹。

小波零樹編碼就是利用小波樹的強相關性，將父節點的絕對值與門限值進行比較，當父節點絕對值小于門限值時，認為該小波樹均不是顯著系數，因此將該小波樹都以零值編碼，形成大量的小波零樹，從而減少數據。零樹編碼不是十分完美，譬如父節點不顯著時，也存在后代節點是重要的情形，此時忽略子孫節點將造成較大的誤差。

1993年Shapiro在小波零樹編碼算法的基礎上提出了嵌入零樹小波編碼（Embedded Zerotree Wavelet，EZW）算法。在EZW算法中，用5種符號表示小波系數：正符號、負符號、孤立零值、小波零樹和零符號。正符號（PositiveSymbol，POS）表示絕對值大于門限值，且值為正的小波系數；負符號（NegativeSymbol，NEG）表示絕對值大于門限值，且值為負的小波系數；孤立零值（Isolated Zero，IZ）表示絕對值小于門限值，但是存在后代節點的絕對值大于門限值的小波系數；小波零樹（Zero tree，ZTR）表示絕對值小于門限值，且后代節點的絕對值都小于門限值的小波系數；零符號（Zero Symbol，Z）表示絕對值小于門限值的葉節點。由于在規定的掃描順序下小波樹的位置能完全確定下來，所以在實際編碼中小波零樹和零符號可以用同一符號來表示。

（1）門限值的選取

初始門限值；，其中VDWT表示小波系數，「·」表示取不超過該數的最大整數值。此后每次掃描的門限值：，n＝1，2，…。

（2）掃描順序

在編碼過程中，對小波系數通常采用如圖3-38所示的Zig-Zag（Z）順序進行多次掃描，前一次掃描獲得的數據比后一次更重要。

（3）編碼過程

編碼主要分為三個過程：主掃描過程（dominant pass），主要確定小波系數的符號；輔掃描過程（refinement pass），對小波顯著系數（正符號和負符號）進行加細量化；符號編碼過程（symbol encode），對符號進行熵編碼。

首先，在第i次主掃描過程中，根據門限Ti－1確定每個系數對應的符號。絕對值大于門限值的系數，稱為顯著系數，依據它的正、負賦予符號POS或NEG。絕對值小于門限值的系數，如果其子孫節點系數的絕對值均小于門限值，則它們構成零樹，賦予該節點ZTR，并不再對其子孫節點進行掃描；如果其子孫節點中有一個系數的絕對值大于門限值，則賦予該節點IZ，對其子孫節點的掃描照常進行。將掃描得到的符號按順序記錄在顯著系數表中。

第i次輔助掃描是對當前的顯著系數表進行掃描，以對符號為POS和NEG的系數的絕對值進行加細量化。將[Ti－1，2T0）劃分成[Ti－1，2Ti－1）大小的若干個區間，若系數的絕對值落入某一個區間的下半部（小于區間中點值），輸出“0”；否則，輸出“1”。將輸出的“0”和“1”按掃描順序記錄在加細量化表中。

然后，在新門限值Ti下進行第i＋1次主掃描和輔掃描。在這次主掃描中，前面已經確定為顯著系數的節點將不再掃描，同時將該節點的系數看成0，以確保更多的零樹產生。主掃描和輔掃描得到的結果將分別存入顯著系數表和加細量化表中（附加在第i次掃描結果之后）。

上述的兩步掃描過程繼續進行，直至門限值為1。最后，對所得的兩個表進行熵編碼得到EZW碼流。編碼中的符號IZ和Z可以合并為Z。

由上看出，EZW編碼對數據進行逐次逼近量化，將重要性高的數據優先編碼（在表的前面），而且可以在任意一點停止掃描編碼，形成重建質量不同的碼流，保留碼流越長，系數量化精度越細，重建圖像質量越高。這種編碼方式稱為嵌入式編碼。多尺度分析的特性使小波變換編碼具備良好的嵌入式編碼性能。

2.其他高性能的小波編碼算法

Said和Pearlman受EZW算法的啟發，在1996年提出了多級樹集合分裂算法（Set Partitioning In Hierarchical Trees，SPIHT）。SPIHT算法依然利用小波零樹特性進行編碼，盡管與EZW算法有很多相似之處，但也存在一些明顯的區別。第一，SPIHT算法在小波樹結構上與EZW算法有所不同，同時定義了兩種零樹，比EZW劃分的更為細致；第二，EZW編碼的掃描順序是一種固定的光柵掃描，而SPIHT編碼的掃描順序取決于以前編碼的樹的顯著性；第三，顯著性掃描過程與加細量化過程與EZW算法的順序相反。與EZW算法一樣，SPIHT算法也是一種嵌入式編碼方法，它可以在任意點截斷比特流，得到不同質量的圖像數據。

EZW算法和SPIHT算法都利用了小波變換中存在的父－子節點的相關性。然而更進一步的研究表明，基于小波變換的圖像編碼算法編碼增益更多的得益于小波變換的能量壓縮性質，而不是特定的圖像數據的相關性。因此，對每個子帶進行獨立的編碼也可以獲得良好的編碼性能。

Taubman在2000年提出的基于優化截斷嵌入式塊編碼（Embedded Block Coding with Optimal Truncation，EBCOT）就是一種對各子帶進行獨立編碼的方法。EBCOT算法將每個子帶分成相對較小的塊（64×64或32×32），這些塊稱為“碼塊（code-block）”，每個碼塊獨立進行編碼，產生基本的嵌入式流。最后由這些基本嵌入式比特流可以合成一個總嵌入式流，稱為“組合流（pack-et-stream）”。合成組合流時，每個碼塊截斷點比特流長度與失真的關系是已知的，可以根據這種關系優化截斷各碼塊比特流以獲得效率更高的組合流，這種優化截斷方法稱為壓縮后率失真優化（Post-Compression Rate-Distortion optimization，PCRD-opt）方法。EBCOT算法是對每個碼塊進行獨立編碼的，因此通過EBCOT算法不僅可以實現失真的可伸縮性，通過選擇不同子帶的碼塊比特流還可以實現分辨率的可伸縮性，結構比EZW和SPIHT算法要更靈活。同時對每個碼塊進行獨立編碼也為在硬件中實現并行算法提供了可能性。當壓縮比特流出現誤碼時，誤碼的影響也僅出現在相應的碼塊中，并不影響其他碼塊的解碼，因此EBCOT算法還具有良好的抗誤碼性能，適合在網絡中進行傳輸。EBCOT算法的這些特性促成了JPEG2000采用EBCOT編碼方法。