采用FPGA技術(shù)高速實(shí)現(xiàn)無(wú)鏈表SPIHT圖像壓縮算法的設(shè)計(jì)

1、引言

基于變換的圖像壓縮方法當(dāng)前應(yīng)用最為廣泛。小波變換以其優(yōu)秀的能量集中能力而被JPEG2000標(biāo)準(zhǔn)所采用。而當(dāng)前諸如countourlet、directionlets等具有多方向性的變換由于具有非常高的非線性逼近能力很可能使圖像壓縮性能得到較大提高。然而非線性逼近能力強(qiáng)并不能直接使圖像壓縮性能得以提高，因?yàn)橹匾禂?shù)的位置還需要進(jìn)行有效的熵編碼。SPIHT和EBCOT是熵編碼器中最具代表性的編碼方案。它們都具有編碼效率高，生成的碼流具有嵌入式的特點(diǎn)。

EBCOT是JPEG200中的核心編碼器。它采用的是塊編碼技術(shù)，根據(jù)信源的特性對(duì)信源進(jìn)行分類，然后進(jìn)行MQ算術(shù)編碼，利用壓縮后率失真優(yōu)化（PCRD）策略產(chǎn)生嵌入式碼流。SPIHT則是基于子帶之間的自相似的特點(diǎn)通過(guò)零樹(shù)結(jié)構(gòu)進(jìn)行重要性信息的編碼。算法對(duì)集合進(jìn)行重要性測(cè)試并按照一定的規(guī)則分裂．如果集合中所有元素的幅值小于某閾值（即該集合是不重要的），則使用一個(gè)比特即可表示，這樣就大大簡(jiǎn)化了集合的表示．由于變換系數(shù)在空間定位樹(shù)結(jié)構(gòu)中的相似性，使這種算法具有極高的效率，即使不使用算術(shù)編碼也能達(dá)到較高的壓縮效率。SPIHT與EBCOT相比，雖然沒(méi)有EBCOT碼流極其靈活的特點(diǎn)，但由于算法復(fù)雜度相對(duì)較低并且可以省去自適應(yīng)算術(shù)編碼過(guò)程，適用于對(duì)編碼實(shí)時(shí)性要求較高的場(chǎng)合．因此研究SPIHT算法的FPGA實(shí)現(xiàn)具有重要意義。

但是，原始的SPIHT算法是通過(guò)3個(gè)有序的鏈表存儲(chǔ)重要性信息實(shí)現(xiàn)對(duì)圖像的編碼．鏈表操作包括動(dòng)態(tài)分配鏈表、添加和刪除結(jié)點(diǎn)等，這非常不適于FPGA的有效實(shí)現(xiàn)。F. W. Wheeler和W. A. Pearlman隨后提出了無(wú)鏈表SPIHT，并稱之為NLS。NLS則可以用FPGA加以實(shí)現(xiàn)。本文在深入研究無(wú)鏈表SPIHT圖像壓縮算法的基礎(chǔ)上，設(shè)計(jì)了該算法的FPGA實(shí)現(xiàn)結(jié)構(gòu)。

2、無(wú)鏈表SPIHT圖像壓縮算法

為了使SPIHT算法適應(yīng)硬件的實(shí)現(xiàn)，無(wú)鏈表SPIHT算法對(duì)原算法進(jìn)行了一些改進(jìn)。在改進(jìn)算法中采用了寬度優(yōu)先的搜索策略。這是由于相對(duì)應(yīng)深度優(yōu)先的搜索策略，寬度優(yōu)先的搜索策略會(huì)使重要系數(shù)更可能先被掃描到，從而能夠提高壓縮性能。

在無(wú)鏈表SPIHT算法中，采用特定的標(biāo)志符來(lái)代替原SPIHT算法中的鏈表。當(dāng)新的不重要集合生成時(shí)，這些稀疏的標(biāo)志符就會(huì)被相應(yīng)更新。通過(guò)稀疏的標(biāo)志符標(biāo)識(shí)，圖像中的大部分不重要塊被跳過(guò)，從而使編碼時(shí)間大大減少。為了能夠高效實(shí)現(xiàn)圖像中不重要塊被跳過(guò)，無(wú)鏈表SPIHT算法采用一維線性索引的尋址方式代替二維的尋址方式。

對(duì)于無(wú)鏈表SPIHT算法，集合結(jié)構(gòu)、分割規(guī)則和SPIHT相同。每個(gè)位平面有三個(gè)過(guò)程，不重要系數(shù)過(guò)程、重要集合過(guò)程、精細(xì)化過(guò)程。在編碼過(guò)程中為了避免重復(fù)掃描系數(shù)，使用最大值表存儲(chǔ)器來(lái)解決這個(gè)問(wèn)題。在開(kāi)始編碼前，首先要計(jì)算出兩個(gè)后代集合的最大值表。這兩個(gè)最大值表分別存儲(chǔ)后代集合最大值（記為DMax）和除了兒子外的后代集合最大值（記為GMax）。這兩個(gè)最大值表可由下面兩個(gè)公式求出。在求的過(guò)程中，按照從后向前的順序掃描系數(shù)。其中在求DMax時(shí)，當(dāng)GMax超出圖像邊界后應(yīng)把它算作零。最大值函數(shù)max實(shí)際上可以用按位或運(yùn)算來(lái)代替，這也非常利于硬件實(shí)現(xiàn)。

當(dāng)完成最大值表求取完成后，接著對(duì)標(biāo)志符存儲(chǔ)器進(jìn)行初始化。最后就可以進(jìn)行正式編碼了。編碼的算法主流程請(qǐng)參考［3］。

3、FPGA算法實(shí)現(xiàn)結(jié)構(gòu)

根據(jù)無(wú)鏈表SPIHT算法，設(shè)計(jì)了具體的FPGA實(shí)現(xiàn)結(jié)構(gòu)。圖2所示為系統(tǒng)的總體框圖。整個(gè)系統(tǒng)以NLS Encoder為中心實(shí)現(xiàn)對(duì)小波系數(shù)的掃描編碼。Coefficients存儲(chǔ)了經(jīng)過(guò)小波變換后的系數(shù)，而且按照線性索引的順序已排列好。DMax用于存儲(chǔ)所有結(jié)點(diǎn)的后代最大系數(shù)。GMax用于存儲(chǔ)所有結(jié)點(diǎn)的除了兒子外的所有后代的最大系數(shù)。Marker存儲(chǔ)了各個(gè)系數(shù)的當(dāng)前狀態(tài)標(biāo)志，且在編碼過(guò)程中相應(yīng)的更新。

圖2無(wú)鏈表SPIHT算法FPGA實(shí)現(xiàn)總體框圖

算法實(shí)現(xiàn)中，使用一個(gè)有限狀態(tài)機(jī)實(shí)現(xiàn)對(duì)編碼過(guò)程的有效控制。圖3所示為NLS編碼器狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換圖。系統(tǒng)復(fù)位后進(jìn)入Idle狀態(tài)，當(dāng)start信號(hào)有效后開(kāi)始對(duì)圖像系數(shù)進(jìn)行編碼處理進(jìn)入Initial狀態(tài)。在Initial狀態(tài)里對(duì)標(biāo)志符存儲(chǔ)器進(jìn)行初始化設(shè)置，設(shè)置完成后進(jìn)入GetMax狀態(tài)。在GetMax狀態(tài)里對(duì)圖像系數(shù)進(jìn)行掃描，求出DMax和GMax并把他們存儲(chǔ)到對(duì)應(yīng)的存儲(chǔ)器里，全部求完后進(jìn)入SortingPixel狀態(tài)。在SortingPixel狀態(tài)里，完成對(duì)不重要系數(shù)的掃描編碼并把編碼結(jié)果輸出，掃描完成后進(jìn)入SortingSet狀態(tài)。在SortingSet狀態(tài)里，對(duì)不重要集合進(jìn)行掃描測(cè)試，按照算法的規(guī)則輸出相應(yīng)的編碼，完成相應(yīng)掃描后，進(jìn)入Refinement狀態(tài)。在Refinement狀態(tài)里對(duì)重要系數(shù)進(jìn)行精細(xì)化過(guò)程，完成相應(yīng)掃描后進(jìn)入NextBitPlane狀態(tài)。在NextBitPlane里把位平面測(cè)試變量切換到下一個(gè)位平面，并回到SortingPixel狀態(tài)。其中在SortingPixel、SortingSet和Refinement狀態(tài)里，都要判斷輸出的壓縮碼流是否達(dá)到了目標(biāo)碼率，如果達(dá)到則都直接返回到Idle狀態(tài)，完成這幅圖像的壓縮編碼，等待下一幅圖像壓縮的開(kāi)始。

圖3 NLS編碼器狀態(tài)機(jī)狀態(tài)轉(zhuǎn)換圖

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

為了驗(yàn)證該算法FPGA實(shí)現(xiàn)的正確性和高效性，采用了Altera公司的FPGA開(kāi)發(fā)板。板上FPGA為Stratix II 系列，具體型號(hào)為EP2S60F672C5。首先，使用MATLAB對(duì)圖像進(jìn)行小波變換，然后把經(jīng)過(guò)小波變換的系數(shù)以存儲(chǔ)器初始化文件（*.mif格式）存儲(chǔ)到Coefficients存儲(chǔ)器中［4］。系統(tǒng)工作后，通過(guò)按鍵產(chǎn)生start信號(hào)啟動(dòng)一次壓縮過(guò)程。為了觀察壓縮結(jié)果，把壓縮后的碼流仍然存儲(chǔ)到片內(nèi)存儲(chǔ)器中，且把該存儲(chǔ)器中的“Allow In-System Memory Content Editor to capture and update content independently of the system clock”選項(xiàng)設(shè)置為有效。那么當(dāng)壓縮完成后，就可以通過(guò)JTAG下載電纜，把該存儲(chǔ)器的數(shù)據(jù)通過(guò)Quartus II 軟件的In-System Memory Content Editor功能讀回到計(jì)算機(jī)，并同樣可以存儲(chǔ)為*.mif格式文件。這樣利用MATLAB讀取該*.mif格式文件，進(jìn)行解碼操作，并進(jìn)行小波逆變換，即可恢復(fù)解壓縮的圖像。

使用FPGA實(shí)現(xiàn)該算法時(shí)，完全使用FPGA片內(nèi)存儲(chǔ)器。對(duì)于256x256大小的圖像，表1列出了FPGA片內(nèi)存儲(chǔ)器的使用情況，總計(jì)需要200K字節(jié)的存儲(chǔ)器即可。如果把圖像的壓縮比設(shè)為8:1，則壓縮碼流存儲(chǔ)器需要的存儲(chǔ)容量為8K字節(jié)。

表1 FPGA片內(nèi)存儲(chǔ)器使用情況

5、結(jié)論

SPIHT算法是公認(rèn)的高性能的圖像壓縮算法。為了能采用FPGA進(jìn)行有效的高速實(shí)現(xiàn)，本文深入分析了其改進(jìn)算法：無(wú)鏈表SPIHT算法（NLS）。由于無(wú)鏈表SPIHT算法采用狀態(tài)標(biāo)示符取代動(dòng)態(tài)鏈表操作來(lái)記錄集合分割信息，進(jìn)而把整個(gè)編碼過(guò)程都簡(jiǎn)化為簡(jiǎn)單的邏輯運(yùn)算。在此基礎(chǔ)上設(shè)計(jì)了NLS編碼器的FPGA實(shí)現(xiàn)的高速高效硬件結(jié)構(gòu)。并在Altera公司的FPGA上進(jìn)行了實(shí)際驗(yàn)證。實(shí)驗(yàn)表明，該FPGA實(shí)現(xiàn)方案可以應(yīng)用到高速實(shí)時(shí)圖像壓縮系統(tǒng)中。

本文作者創(chuàng)新點(diǎn)：使用FPGA實(shí)現(xiàn)了無(wú)鏈表SPIHT算法，該方案可以應(yīng)用到高速實(shí)時(shí)圖像壓縮系統(tǒng)中。

責(zé)任編輯：gt