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

采用FPGA技術(shù)高速實(shí)現(xiàn)無鏈表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)通過零樹結(jié)構(gòu)進(jìn)行重要性信息的編碼。算法對(duì)集合進(jìn)行重要性測(cè)試并按照一定的規(guī)則分裂．如果集合中所有元素的幅值小于某閾值（即該集合是不重要的），則使用一個(gè)比特即可表示，這樣就大大簡(jiǎn)化了集合的表示．由于變換系數(shù)在空間定位樹結(jié)構(gòu)中的相似性，使這種算法具有極高的效率，即使不使用算術(shù)編碼也能達(dá)到較高的壓縮效率。SPIHT與EBCOT相比，雖然沒有EBCOT碼流極其靈活的特點(diǎn)，但由于算法復(fù)雜度相對(duì)較低并且可以省去自適應(yīng)算術(shù)編碼過程，適用于對(duì)編碼實(shí)時(shí)性要求較高的場(chǎng)合．因此研究SPIHT算法的FPGA實(shí)現(xiàn)具有重要意義。但是，原始的SPIHT算法是通過3個(gè)有序的鏈表存儲(chǔ)重要性信息實(shí)現(xiàn)對(duì)圖像的編碼．鏈表操作包括動(dòng)態(tài)分配鏈表、添加和刪除結(jié)點(diǎn)等，這非常不適于FPGA的有效實(shí)現(xiàn)。F.W.Wheeler和W.A.Pearlman隨后提出了無鏈表SPIHT，并稱之為NLS。NLS則可以用FPGA加以實(shí)現(xiàn)。本文在深入研究無鏈表SPIHT圖像壓縮算法的基礎(chǔ)上，設(shè)計(jì)了該算法的FPGA實(shí)現(xiàn)結(jié)構(gòu)。2、無鏈表SPIHT圖像壓縮算法為了使SPIHT算法適應(yīng)硬件的實(shí)現(xiàn)，無鏈表SPIHT算法對(duì)原算法進(jìn)行了一些改進(jìn)。在改進(jìn)算法中采用了寬度優(yōu)先的搜索策略。這是由于相對(duì)應(yīng)深度優(yōu)先的搜索策略，寬度優(yōu)先的搜索策略會(huì)使重要系數(shù)更可能先被掃描到，從而能夠提高壓縮性能。在無鏈表SPIHT算法中，采用特定的標(biāo)志符來代替原SPIHT算法中的鏈表。當(dāng)新的不重要集合生成時(shí)，這些稀疏的標(biāo)志符就會(huì)被相應(yīng)更新。通過稀疏的標(biāo)志符標(biāo)識(shí)，圖像中的大部分不重要塊被跳過，從而使編碼時(shí)間大大減少。為了能夠高效實(shí)現(xiàn)圖像中不重要塊被跳過，無鏈表SPIHT算法采用一維線性索引的尋址方式代替二維的尋址方式。對(duì)于無鏈表SPIHT算法，集合結(jié)構(gòu)、分割規(guī)則和SPIHT相同。每個(gè)位平面有三個(gè)過程，不重要系數(shù)過程、重要集合過程、精細(xì)化過程。在編碼過程中為了避免重復(fù)掃描系數(shù)，使用最大值表存儲(chǔ)器來解決這個(gè)問題。在開始編碼前，首先要計(jì)算出兩個(gè)后代集合的最大值表。這兩個(gè)最大值表分別存儲(chǔ)后代集合最大值（記為DMax）和除了兒子外的后代集合最大值（記為GMax）。這兩個(gè)最大值表可由下面兩個(gè)公式求出。在求的過程中，按照從后向前的順序掃描系數(shù)。其中在求DMax時(shí)，當(dāng)GMax超出圖像邊界后應(yīng)把它算作零。最大值函數(shù)max實(shí)際上可以用按位或運(yùn)算來代替，這也非常利于硬件實(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ù)無鏈表SPIHT算法，設(shè)計(jì)了具體的FPGA實(shí)現(xiàn)結(jié)構(gòu)。圖2所示為系統(tǒng)的總體框圖。整個(gè)系統(tǒng)以NLSEncoder為中心實(shí)現(xiàn)對(duì)小波系數(shù)的掃描編碼。Coefficients存儲(chǔ)了經(jīng)過小波變換后的系數(shù)，而且按照線性索引的順序已排列好。DMax用于存儲(chǔ)所有結(jié)點(diǎn)的后代最大系數(shù)。GMax用于存儲(chǔ)所有結(jié)點(diǎn)的除了兒子外的所有后代的最大系數(shù)。Marker存儲(chǔ)了各個(gè)系數(shù)的當(dāng)前狀態(tài)標(biāo)志，且在編碼過程中相應(yīng)的更新。圖2無鏈表SPIHT算法FPGA實(shí)現(xiàn)總體框圖算法實(shí)現(xiàn)中，使用一個(gè)有限狀態(tài)機(jī)實(shí)現(xiàn)對(duì)編碼過程的有效控制。圖3所示為NLS編碼器狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換圖。系統(tǒng)復(fù)位后進(jìn)入Idle狀態(tài)，當(dāng)start信號(hào)有效后開始對(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ì)化過程，完成相應(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)，完成這幅圖像的壓縮編碼，等待下一幅圖像壓縮的開始。圖3NLS編碼器狀態(tài)機(jī)狀態(tài)轉(zhuǎn)換圖4、實(shí)驗(yàn)結(jié)果為了驗(yàn)證該算法FPGA實(shí)現(xiàn)的正確性和高效性，采用了Altera公司的FPGA開發(fā)板。板上FPGA為StratixII系列，具體型號(hào)為EP2S60F672C5。首先，使用MATLAB對(duì)圖像進(jìn)行小波變換，然后把經(jīng)過小波變換的系數(shù)以存儲(chǔ)器初始化文件（*.mif格式）存儲(chǔ)到Coefficients存儲(chǔ)器中［4］。系統(tǒng)工作后，通過按鍵產(chǎn)生start信號(hào)啟動(dòng)一次壓縮過程。為了觀察壓縮結(jié)果，把壓縮后的碼流仍然存儲(chǔ)到片內(nèi)存儲(chǔ)器中，且把該存儲(chǔ)器中的“AllowIn-SystemMemoryContentEditortocaptureandupdatecontentindependentlyofthesystemclock”選項(xiàng)設(shè)置為有效。那么當(dāng)壓縮完成后，就可以通過JTAG下載電纜，把該存儲(chǔ)器的數(shù)據(jù)通過QuartusII軟件的In-SystemMemoryContentEditor功能讀回到計(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é)。表1FPGA片內(nèi)存儲(chǔ)器使用情況5、結(jié)論SPIHT算法是公認(rèn)的高性能的圖像壓縮算法。為了能采用FPGA進(jìn)行有效的高速實(shí)現(xiàn)，本文深入分析了其改進(jìn)算法：無鏈表SPIHT算法（NLS）。由于無鏈表SPIHT算法采用狀態(tài)標(biāo)示符取代動(dòng)態(tài)鏈表操作來記錄集合分割信息，進(jìn)而把