基于FPGA的提升小波變換聯(lián)合SPIHT編解碼方法*

趙柏山，徐 麗，張 帆

（沈陽工業(yè)大學(xué)，遼寧 沈陽 110870）

0 引 言

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

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

本文基于FPGA實(shí)現(xiàn)了提升9/7小波變換結(jié)合SPIHT編碼的圖片壓縮解壓系統(tǒng)，將小波變換和SPIHT算法進(jìn)行改進(jìn)，進(jìn)一步處理高頻系數(shù)，去除冗余，提高了壓縮率。

1 系統(tǒng)總體設(shè)計(jì)

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

圖1 壓縮系統(tǒng)流程

FPGA中實(shí)現(xiàn)的過程采用流水線結(jié)構(gòu)。使用流水線技術(shù)，可以將復(fù)雜的操作分步執(zhí)行，提高系統(tǒng)的并行度，減小每個(gè)部分的處理時(shí)間，加快系統(tǒng)的處理速度。流水線設(shè)計(jì)的代價(jià)是增加了寄存器邏輯，即增加了芯片資源的耗用。

2 9/7提升小波變換

2.1 提升小波變換

小波變換在圖像壓縮方面的性能較好，應(yīng)用廣泛。傳統(tǒng)的離散小波變換基于卷積進(jìn)行運(yùn)算，計(jì)算量大，處理速度慢[4]，且對存儲(chǔ)的要求高。提升小波變換有效解決了這個(gè)問題，不僅計(jì)算量小、復(fù)雜度低，而且得到的結(jié)果與傳統(tǒng)的離散小波相同，更易于硬件實(shí)現(xiàn)[5]。

提升小波算法由三步基本運(yùn)算構(gòu)成：分裂、預(yù)測和更新，如圖2所示。

圖2 提升小波算法

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

第二步，預(yù)測。分裂后的兩組數(shù)據(jù)具有很大的相關(guān)性，需要利用預(yù)測來消除分裂后的冗余，即用偶數(shù)樣本采用插值細(xì)分的方法預(yù)測奇數(shù)樣本。奇數(shù)樣本與測值之差為細(xì)節(jié)系數(shù)：

其中P為預(yù)測算子。

第三步，更新。用更新的奇數(shù)樣本更新偶數(shù)樣本：

其中U為更新算子。

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

9/7小波在圖像壓縮方面的性能比較優(yōu)異。因此，本設(shè)計(jì)采用的小波為9/7小波。在提升結(jié)構(gòu)中，9/7小波具有兩個(gè)提升步，結(jié)構(gòu)如圖3所示。

圖3 9/7小波變換結(jié)構(gòu)

圖3 中，P1和P2是預(yù)測步的運(yùn)算，U1和U2是更新步的運(yùn)算：

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

將預(yù)測步和更新步的運(yùn)算式應(yīng)用到圖3，可得9/7小波的分步驟計(jì)算公式。

第一步：分裂，即：

第二步：第一次預(yù)測，即：

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

第四步：第二次預(yù)測，即：

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

第六步：伸縮，即：

2.3 9/7提升小波的改進(jìn)

一維9/7提升小波在FPGA中實(shí)現(xiàn)的結(jié)構(gòu)流程，如圖4所示。

圖4 9/7提升小波的FPGA結(jié)構(gòu)

一個(gè)9/7提升小波濾波器由兩個(gè)提升步級聯(lián)實(shí)現(xiàn)。每個(gè)提升步由預(yù)測步和更新步組成。圖4中，（1）和（3）是預(yù)測步，（2）和（4）是更新步。

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

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

三級的二維圖像提升小波變換依次以第一級行變換、第一級列變換、第二級行變換、第二級列變換、第三級行變換、第三級列變換的順序進(jìn)行。圖5為FPGA中三級小波變換處理數(shù)據(jù)順序的結(jié)構(gòu)。

圖5 三級小波編碼的順序結(jié)構(gòu)

3 SPIHT編碼

3.1 SPIHT傳統(tǒng)算法

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

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

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

算法中還定義了幾個(gè)集合，對于任意的節(jié)點(diǎn)(i,j)都有：

O(i, j)：節(jié)點(diǎn)(i, j)的直接后代；

D(i, j)：節(jié)點(diǎn)(i, j)的所有后代；

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

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

其中Xi,j表示節(jié)點(diǎn)(i, j)的值。集合中如果只包含一個(gè)節(jié)點(diǎn)，即T={(i, j)}時(shí)，簡寫為Sn(i, j)。

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

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

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

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

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

對LIS中的所有節(jié)點(diǎn)(i, j)：

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

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

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

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

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

圖6 SPIHT編碼實(shí)現(xiàn)結(jié)構(gòu)

3.2 SPIHT的改進(jìn)

小波變換后，在SPIHT編碼時(shí)，當(dāng)閾值進(jìn)行判決后，會(huì)存在大量無效系數(shù)，從而使各個(gè)鏈表的體積呈級數(shù)級增加。在鏈表插入環(huán)節(jié)進(jìn)行改進(jìn)，對高頻系數(shù)做位寬截取處理。因?yàn)樾〔ㄏ禂?shù)是按照重要程度排序，最重要的比特先輸出，所以保留高位數(shù)據(jù)，舍棄最不重要的低位數(shù)據(jù)，進(jìn)一步去除冗余。這個(gè)步驟可以表示為：

例如，在FPGA中的二進(jìn)制處理過程中，有一個(gè)不重要系數(shù)是32'h0000_0045，進(jìn)行截位處理，保留高16位，那么該系數(shù)就變?yōu)?，不參與編碼，從而提高了編碼效率。

4 實(shí)驗(yàn)結(jié)果

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

圖7 壓縮前后圖像對比

Modelsim的時(shí)序仿真圖，如圖8所示。

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

圖8 時(shí)序仿真圖

表1 改進(jìn)前后數(shù)據(jù)對比表

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

5 結(jié) 語

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

[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] 王綱毅.基于提升機(jī)構(gòu)的二維離散小波的FPGA設(shè)計(jì)[D].武漢:華中科技大學(xué),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] 王鳴哲.星載圖像壓縮系統(tǒng)中高速小波變換的FPGA設(shè)計(jì)與實(shí)現(xiàn)[D].合肥:中國科學(xué)院大學(xué),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].哈爾濱:哈爾濱工業(yè)大學(xué),2007.WANG Ji.Design of Image Compression Card Based on SPIHT Algorithm[D].Harbin:Harbin Institute of Technology,2007.

[7] 李玲遠(yuǎn),詹翠麗,黃林.基于9-7提升小波的SPIHT編碼算法[J].通信技術(shù),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.