基于FPGA的提升小波變換聯合SPIHT編解碼方法*

趙柏山，徐 麗，張 帆

（沈陽工業大學，遼寧 沈陽 110870）

0 引 言

隨著科學技術的日益發展，圖像分辨率提高，圖像的數據量逐漸增加，對圖像壓縮技術的要求也越來越高。近年來，離散小波變換（DWT）已經廣泛應用于圖像壓縮領域，具有良好的自適應時頻窗口特性和多分辨率分析特性。Sweldens提出小波變換的提升算法[1]（Lifting Scheme），結構簡單、運算量小、所需內存少、易于硬件實現，且能實現整數小波變換，成為目前小波變換的常用算法。

小波變換將圖片分解成高頻和低頻部分。低頻部分還可以繼續分解，再分別對高頻和低頻進行編碼。小波變換壓縮的核心是編碼。1993年，Sharpio M Jerome提出了嵌入式零數小波編碼算法（EZW）[2]。1996年，said A和 Pearlman W A在EZW算法的基礎上提出了SPIHT算法，得到了更好的壓縮性能[3]。

本文基于FPGA實現了提升9/7小波變換結合SPIHT編碼的圖片壓縮解壓系統，將小波變換和SPIHT算法進行改進，進一步處理高頻系數，去除冗余，提高了壓縮率。

1 系統總體設計

本設計采用三級9/7提升小波變換SPIHT算法進行實現。壓縮編碼方案主要包括提升小波變換和SPIHT編碼兩部分，而數據解壓過程就是壓縮的逆過程。具體流程如圖1所示。

圖1 壓縮系統流程

FPGA中實現的過程采用流水線結構。使用流水線技術，可以將復雜的操作分步執行，提高系統的并行度，減小每個部分的處理時間，加快系統的處理速度。流水線設計的代價是增加了寄存器邏輯，即增加了芯片資源的耗用。

2 9/7提升小波變換

2.1 提升小波變換

小波變換在圖像壓縮方面的性能較好，應用廣泛。傳統的離散小波變換基于卷積進行運算，計算量大，處理速度慢[4]，且對存儲的要求高。提升小波變換有效解決了這個問題，不僅計算量小、復雜度低，而且得到的結果與傳統的離散小波相同，更易于硬件實現[5]。

提升小波算法由三步基本運算構成：分裂、預測和更新，如圖2所示。

圖2 提升小波算法

第一步，分裂。把原始離散采樣通過間隔抽取采樣分裂成奇數采樣0和偶數采樣。

第二步，預測。分裂后的兩組數據具有很大的相關性，需要利用預測來消除分裂后的冗余，即用偶數樣本采用插值細分的方法預測奇數樣本。奇數樣本與測值之差為細節系數：

其中P為預測算子。

第三步，更新。用更新的奇數樣本更新偶數樣本：

其中U為更新算子。

2.2 9/7小波變換的提升算法

9/7小波在圖像壓縮方面的性能比較優異。因此，本設計采用的小波為9/7小波。在提升結構中，9/7小波具有兩個提升步，結構如圖3所示。

圖3 9/7小波變換結構

圖3 中，P1和P2是預測步的運算，U1和U2是更新步的運算：

圖3中的α、β、γ、δ、K1、K2均為濾波器參數，值為：

將預測步和更新步的運算式應用到圖3，可得9/7小波的分步驟計算公式。

第一步：分裂，即：

第二步：第一次預測，即：

第三步：第一次更新，即：

第四步：第二次預測，即：

第五步：第二次更新，即：

第六步：伸縮，即：

2.3 9/7提升小波的改進

一維9/7提升小波在FPGA中實現的結構流程，如圖4所示。

圖4 9/7提升小波的FPGA結構

一個9/7提升小波濾波器由兩個提升步級聯實現。每個提升步由預測步和更新步組成。圖4中，（1）和（3）是預測步，（2）和（4）是更新步。

小波變換的每一級都是將待變換部分的圖像分量分別進行變換和列變換，分解成LL、HL、LH、HH四個子帶，分別代表低頻分量和水平、垂直、對角線方向的高頻分量。圖像的大部分能量集中到LL分量。下一級小波分解是把上一級的LL子帶再進行分解產生四個子帶，三級9/7整數小波變換將圖像分為10個子帶。

小波變換的行變換和列變換結構完全一樣，只是輸入數據不同，通過控制地址變量控制輸入行和列的數據。因此，二維小波變換可以拆分為兩個一維小波變換，三級二維小波變換就相當于六個一維的小波變換。本設計FPGA的流水線結構，進一步提高了小波變換的壓縮速度。

三級的二維圖像提升小波變換依次以第一級行變換、第一級列變換、第二級行變換、第二級列變換、第三級行變換、第三級列變換的順序進行。圖5為FPGA中三級小波變換處理數據順序的結構。

圖5 三級小波編碼的順序結構

3 SPIHT編碼

3.1 SPIHT傳統算法

SPIHT（Set Partitioning in Hierarchical Trees）算法是分級樹的集合劃分算法，是對嵌入式零樹編碼（Embedded Zero-tree Wavelet，EZW）算法的改進和擴展[6]。它繼承了EZW算法的思想，通過方向樹最有效地表示重要系數，并通過對樹的劃分將盡可能多的非重要系數匯集在一個子集中，用一個單位符號表示[7]。

SPIHT算法是一種很好的漸進傳輸編碼方法。SPIHT算法可以在任意點停止編碼，能夠滿足特定壓縮率和失真度的要求；也可以隨時解碼，在圖像解碼的任意時刻，所顯示的圖像質量都是當時解碼器輸入位數所能獲得的最佳數據。

SPIHT算法中采用三個鏈表保存編碼信息：保存重要系數坐標的鏈表LSP（List of Insignificant Pixels）；保存不重要系數坐標的鏈表LIP（List of Significant Pixels）；保存不重要系數集合坐標的鏈表 LIS（List of Insignificant Sets）。

算法中還定義了幾個集合，對于任意的節點(i,j)都有：

O(i, j)：節點(i, j)的直接后代；

D(i, j)：節點(i, j)的所有后代；

L(i, j)節點(i, j)的除了直接后代的所有后代，即L(i, j)=D(i, j)-O(i, j)。

SPIHT算法的基本運算是判斷一個集合是否重要，即一個集合中所有系數都是重要系數。定義：Sn(T)為T是否重要的標志位：

其中Xi,j表示節點(i, j)的值。集合中如果只包含一個節點，即T={(i, j)}時，簡寫為Sn(i, j)。

SPIHT編碼的流程圖如圖6所示。

SPIHT算法編碼主要分為以下四個步驟。

（1）初始化：將LSP置為空集；將時間方向樹的根節點的序號放入LIP，將除最低頻子帶以外的根節點的序號放入LIS，同時標以A類。設置初始閾值為2n。

（2）排序掃描：應用集合分裂排序規則將小波變換后的系數序號分別送入LIP、LIS和LSP中。

對LIP中的所有節點(i, j)輸出Sn(i, j)，若Sn(i,j)=1，則將節點(i, j)移到LSP中，并輸出C(i, j)的符號；

對LIS中的所有節點(i, j)：

①如果節點屬于A類，則輸出Sn(D(i, j))。如果Sn(D(i, j))=1，則對O(i, j)中所有節點(k, l)輸出Sn(k, l)；如果Sn(k, l)=1，則將節點(k, l)加入到LSP中并輸出X(k, l)的符號；如果L(k, l)非空，則將節點(i, j)移到LIS的尾部，并標記為B類；否則，將節點移出LIS；

②如果該節點屬于B類，則輸出Sn(L(i, j))。如果Sn(L(i, j))，則將O(i, j)以A類型加入到LIS，并將節點(i, j)移出LIS；

（3）精細掃描：輸出LSP所表示的小波系數的最重要的第n位比特值。

（4）更新閾值指數：將閾值指數n減至n-1，返回步驟（2）進行下一級編碼掃描。

解碼過程中，SPIHT解碼器和編碼器的掃描工作相同，不同的是根據輸入的碼流來恢復小波系數表。在同一時刻，解碼器的三個鏈表與編碼器的三個鏈表是相同的，即解碼器是根據編碼時的搜索路徑恢復數據序列的。解碼器的每次迭代都更新閾值，在排序掃描和精細掃描過程中改善系數矩陣，從而改善圖像質量，等效地減少了失真。

圖6 SPIHT編碼實現結構

3.2 SPIHT的改進

小波變換后，在SPIHT編碼時，當閾值進行判決后，會存在大量無效系數，從而使各個鏈表的體積呈級數級增加。在鏈表插入環節進行改進，對高頻系數做位寬截取處理。因為小波系數是按照重要程度排序，最重要的比特先輸出，所以保留高位數據，舍棄最不重要的低位數據，進一步去除冗余。這個步驟可以表示為：

例如，在FPGA中的二進制處理過程中，有一個不重要系數是32'h0000_0045，進行截位處理，保留高16位，那么該系數就變為0，不參與編碼，從而提高了編碼效率。

4 實驗結果

采用512×512的Lena圖，將改進后的壓縮算法用MATLAB編寫程序，用軟件仿真圖像的壓縮過程，并對壓縮以后的碼流解壓，以驗證壓縮算法，同時為硬件仿真提供參照依據。然后，利用VerilogHDL編程，在Quartus II中進行驗證。圖7為FPGA在壓縮率0.5的情況下進行壓縮，解壓后數據用MATLAB恢復的圖像與原圖像的對比。

圖7 壓縮前后圖像對比

Modelsim的時序仿真圖，如圖8所示。

本設計將不同壓縮率下改進前和改進后的壓縮數據進行對比。在原算法壓縮率為0.75的情況下，改進后的字符數為177 505，壓縮率為0.677 12；原算法壓縮率為0.5的情況下，改進后的字符數為114 135，壓縮率為0.435 39；原算法壓縮率為0.25的情況下，改進后的字符數為56 606，壓縮率為0.213 6。表1為改進前后壓縮率與PSNR（峰值信噪比）的對比結果。

圖8 時序仿真圖

表1 改進前后數據對比表

從表1得出的結果可以看出，本設計采用的提升9/7小波變換結合SPIHT改進算法的圖像壓縮方案切實可行，獲得了較改進前高的壓縮率，且PSNR沒有明顯的差異。

5 結 語

基于小波變換和傳統SPIHT算法編解碼原理，利用FPGA，對傳統算法進行改進：將二維提升小波變換改為一維，提高了并行度，減小了運行速度；在SPIHT算法中對不重要的高頻系數進行截位處理，提高了SPIHT的編碼效率。實驗結果表明，與傳統SPIHT算法相比，改進系統所得的數據壓縮率更高，更易于硬件實現。

[1] Sweldens W.The Lifting Scheme:A Construction of Second Generation Wavelets[J].Journal of Appl. and Comput Harmonic Analysis,1997,29(02):511-546.

[2] Shapiro J M.Embedded Image Coding Using Zerotrees of Wavelet Coefficients[J].IEEE Trans. Signal Processi ng,1993,41(12):3445-3462.

[3] Said A,Pearlman W A.A New,Fast,and Efficient Image Code Based on Set Partitioning in Hierarchical Trees[J].IEEE Trans. Circuits Syst.& Video Technol.,1996,6(03):243-249.

[4] 王綱毅.基于提升機構的二維離散小波的FPGA設計[D].武漢:華中科技大學,2005.WANG Gang-yi.FPGA Design of Two-Dimensional DWT Based on the Lifting Scheme[D].Wuhan:Huazhong University of Science and Technology,2015.

[5] 王鳴哲.星載圖像壓縮系統中高速小波變換的FPGA設計與實現[D].合肥:中國科學院大學,2017 WANG Ming-zhe.FPGA Design and Implementation of High Speed Discrete Wavelet Transform in Space Image Compression System[D].Hefei:The University of Chinese Academy of Sciences,2017.

[6] 王驥.基于SPIHT算法的圖像壓縮卡的研制[D].哈爾濱:哈爾濱工業大學,2007.WANG Ji.Design of Image Compression Card Based on SPIHT Algorithm[D].Harbin:Harbin Institute of Technology,2007.

[7] 李玲遠,詹翠麗,黃林.基于9-7提升小波的SPIHT編碼算法[J].通信技術,2008,41(02):83-85.LI Ling-yuan,ZHAN Cui-li,HUANG Lin.SPIHT Algorithm Based on 9-7 Lifting Wavelet[J].Communications Technology,2008,41(02):83-85.