1、引言

基于變換的圖像壓縮方法當前應用最為廣泛。小波變換以其優秀的能量集中能力而被JPEG2000標準所采用。而當前諸如countourlet、directionlets等具有多方向性的變換由于具有非常高的非線性逼近能力很可能使圖像壓縮性能得到較大提高。然而非線性逼近能力強并不能直接使圖像壓縮性能得以提高，因為重要系數的位置還需要進行有效的熵編碼。SPIHT和EBCOT是熵編碼器中最具代表性的編碼方案。它們都具有編碼效率高，生成的碼流具有嵌入式的特點。

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

但是，原始的SPIHT算法是通過3個有序的鏈表存儲重要性信息實現對圖像的編碼．鏈表操作包括動態分配鏈表、添加和刪除結點等，這非常不適于FPGA的有效實現。F. W. Wheeler和W. A. Pearlman隨后提出了無鏈表SPIHT，并稱之為NLS。NLS則可以用FPGA加以實現。本文在深入研究無鏈表SPIHT圖像壓縮算法的基礎上，設計了該算法的FPGA實現結構。

2、無鏈表SPIHT圖像壓縮算法

為了使SPIHT算法適應硬件的實現，無鏈表SPIHT算法對原算法進行了一些改進。在改進算法中采用了寬度優先的搜索策略。這是由于相對應深度優先的搜索策略，寬度優先的搜索策略會使重要系數更可能先被掃描到，從而能夠提高壓縮性能。

在無鏈表SPIHT算法中，采用特定的標志符來代替原SPIHT算法中的鏈表。當新的不重要集合生成時，這些稀疏的標志符就會被相應更新。通過稀疏的標志符標識，圖像中的大部分不重要塊被跳過，從而使編碼時間大大減少。為了能夠高效實現圖像中不重要塊被跳過，無鏈表SPIHT算法采用一維線性索引的尋址方式代替二維的尋址方式。

對于無鏈表SPIHT算法，集合結構、分割規則和SPIHT相同。每個位平面有三個過程，不重要系數過程、重要集合過程、精細化過程。在編碼過程中為了避免重復掃描系數，使用最大值表存儲器來解決這個問題。在開始編碼前，首先要計算出兩個后代集合的最大值表。這兩個最大值表分別存儲后代集合最大值（記為DMax）和除了兒子外的后代集合最大值（記為GMax）。這兩個最大值表可由下面兩個公式求出。在求的過程中，按照從后向前的順序掃描系數。其中在求DMax時，當GMax超出圖像邊界后應把它算作零。最大值函數max實際上可以用按位或運算來代替，這也非常利于硬件實現。

當完成最大值表求取完成后，接著對標志符存儲器進行初始化。最后就可以進行正式編碼了。編碼的算法主流程請參考［3］。

3、FPGA算法實現結構

根據無鏈表SPIHT算法，設計了具體的FPGA實現結構。圖2所示為系統的總體框圖。整個系統以NLS Encoder為中心實現對小波系數的掃描編碼。Coefficients存儲了經過小波變換后的系數，而且按照線性索引的順序已排列好。DMax用于存儲所有結點的后代最大系數。GMax用于存儲所有結點的除了兒子外的所有后代的最大系數。Marker存儲了各個系數的當前狀態標志，且在編碼過程中相應的更新。

圖2無鏈表SPIHT算法FPGA實現總體框圖

算法實現中，使用一個有限狀態機實現對編碼過程的有效控制。圖3所示為NLS編碼器狀態機的狀態轉換圖。系統復位后進入Idle狀態，當start信號有效后開始對圖像系數進行編碼處理進入Initial狀態。在Initial狀態里對標志符存儲器進行初始化設置，設置完成后進入GetMax狀態。在GetMax狀態里對圖像系數進行掃描，求出DMax和GMax并把他們存儲到對應的存儲器里，全部求完后進入SortingPixel狀態。在SortingPixel狀態里，完成對不重要系數的掃描編碼并把編碼結果輸出，掃描完成后進入SortingSet狀態。在SortingSet狀態里，對不重要集合進行掃描測試，按照算法的規則輸出相應的編碼，完成相應掃描后，進入Refinement狀態。在Refinement狀態里對重要系數進行精細化過程，完成相應掃描后進入NextBitPlane狀態。在NextBitPlane里把位平面測試變量切換到下一個位平面，并回到SortingPixel狀態。其中在SortingPixel、SortingSet和Refinement狀態里，都要判斷輸出的壓縮碼流是否達到了目標碼率，如果達到則都直接返回到Idle狀態，完成這幅圖像的壓縮編碼，等待下一幅圖像壓縮的開始。

圖3 NLS編碼器狀態機狀態轉換圖

4、實驗結果

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

使用FPGA實現該算法時，完全使用FPGA片內存儲器。對于256x256大小的圖像，表1列出了FPGA片內存儲器的使用情況，總計需要200K字節的存儲器即可。如果把圖像的壓縮比設為8:1，則壓縮碼流存儲器需要的存儲容量為8K字節。

表1 FPGA片內存儲器使用情況

5、結論

SPIHT算法是公認的高性能的圖像壓縮算法。為了能采用FPGA進行有效的高速實現，本文深入分析了其改進算法：無鏈表SPIHT算法（NLS）。由于無鏈表SPIHT算法采用狀態標示符取代動態鏈表操作來記錄集合分割信息，進而把整個編碼過程都簡化為簡單的邏輯運算。在此基礎上設計了NLS編碼器的FPGA實現的高速高效硬件結構。并在Altera公司的FPGA上進行了實際驗證。實驗表明，該FPGA實現方案可以應用到高速實時圖像壓縮系統中。

本文作者創新點：使用FPGA實現了無鏈表SPIHT算法，該方案可以應用到高速實時圖像壓縮系統中。

責任編輯：gt