JPEG2000 MQ編碼算法的優化和FPGA實現

摘要: MQ編碼是一種無損數據壓縮技術，已被JPEG2000標準采用，其高復雜度成為JPEG2000系統實現的速度瓶頸。本文在分析MQ編碼算法軟件流程的基礎上提出了一種優化的基于流水線處理的MQ編碼算法；并利用Xilinx FPGA的可編程特性詳細地將此算法模塊化，最后實現仿真驗證。結果表明，該算法在有限資源消耗情況下最高運算時鐘頻率可達89.8 MHz，算法對于壓縮速度要求嚴格的JPEG2000實現具有一定實用價值。

JPEG2000是新一代靜止圖像壓縮標準[12]，通過多項創新技術的引入，JPEG2000可以提供比JPEG 更優質的壓縮效果和更多的新功能。MQ算術編碼器是一種基于上下文的自適應二進制算術編碼器，作為JPEG2000 的關鍵技術之一，具有比傳統 Huffman 編碼好的壓縮性能，但頻繁的重歸一化和串行處理也使得軟件實現JPEG2000效率很低。隨著高性能的FPGA發展和大分辨的圖像壓縮需求不斷增加，JPEG2000高速硬件處理已成必然。

為了滿足MQ編碼的高速處理，專家們對MQ編碼硬件實現進行了研究，提出了一些有效方案[2,3,5]。本文對標準的MQ算法進行梳理，在MQ編碼的反饋和循環、區間更新條件判斷方面提出優化，并對MQ編碼進行模塊化劃分，詳細實現了一種基于流水線處理的MQ編碼FPGA架構。

1 MQ編碼原理及FPGA實現

MQ編碼屬于JPEG2000中的Tierl編碼，原始圖像小波變換后的數據經量化后以碼塊為單位，首先根據數據位寬被劃分為一系列的位平面，通過位平面編碼的通道掃描生成上下文；然后MQ編碼器將上下文CX與原始數據D編碼生成壓縮碼流CD。圖1是MQ編碼輸入/輸出數據圖。

圖1 MQ編碼輸入/輸出數據圖

MQ編碼器工作流程為：首先根據上下文CX查找上下文狀態表(I表)，找出當前概率索引值 I（CX）以及大概率符號MPS。接著,根據當前概率索引值I（CX），查找概率估值表，得到Qe、NMPS、NLPS和SWITCH值。然后根據當前區間的概率間隔A、編碼字符串C、原始數據D以及Qe綜合判斷，比較進行A、C和I的更新。為使A始終保持在0.75～1.5，當A<0.75 時，采用重歸一化策略，即A、C同時左移加倍，以保證概率間隔足夠大。最后,為防止重歸一化造成C溢出，C的最高位字節將被定期移到外部緩存中,并輸出即形成壓縮碼流CD。

本文對編碼過程進行模塊化流水線設計，包括：概率估計模塊，編碼區間更新模塊，重歸一化模塊及字節輸出模塊。

1.1 概率估計模塊設計
在概率估計模塊，主要完成的是對CX的概率估計QE，根據當前區間的概率間隔A、編碼字符串C以及Qe,綜合判斷原始數據D是屬于大概率區間MPS,還是小概率區間LPS。概率估計模型是具有47個狀態的有限狀態機[4]，每個上下文CX對應于其中某個狀態。在FPGA中這47個狀態可通過查找表實現，如表1所列。

表1 改進后的概率估計表

?

查找表的輸入Index為概率索引值 I（CX），查找表輸出分別為Qe、NMPS、NLPS和SWITCH值。如上文提到當A<0.75（0x8000）時,需要進行區間更新。JPEG2000標準中，區間重整采用循環判斷方式，每次判斷然后一位位移位操作。這里可以采用前導零的方法提前檢測概率間隔A的前兩位有多少個零，進而一次性移位，減少移位周期。因此在查找表中增加了一項Bit_Shift輸出。

1.2 編碼區間更新設計
編碼區間更新根據更新前的A和C以及當前的QE綜合判斷。JPEG2000標準中，判斷條件較為復雜，進行優化后如圖2所示。

圖2 改進的區間更新流程

其中,ShiftA為A左移Nbshift位后的結果；ShiftC為C左移Nbshift位后的結果；Nbshift為一次性具體左移多少位；Bit_Shift為概率估計查找表輸出，Bit_ShiftA_QE為A_QE的高16、15位零的個數；C_carry為更新后的C的最高位字節。對于Nbshift可以理解為：A選擇為QE時，即需要移位QE的高bit位含零個數；A選擇為A_QE時即需要移位A_QE的高bit位含零個數。

在進行編碼區間更新的同時，需要判斷原始數據D是大概率還是小概率，進而更新概率索引值I（CX）。對JPEG2000標準中的此處判斷條件進行優化，如圖3所示。這里NMPS、NLPS和SWITCH為概率估計表輸出，6bit位寬的I_reg和1bit位寬的MPS_reg合并即為更新后的I（CX），具體I（CX）結構可見參考文獻[1]。

?

圖3 改進的區間更新流程

1.3 重歸一化及字節輸出設計
字節輸出實際上是對C_carry在一定條件下的輸出，即當C_carry湊夠整字節時輸出為CD（或B）。JPEG2000標準中字節輸出流程是串行執行的，效率較低。為了充分利用硬件并行執行的優勢，我們對流程進行了一些調整及優化，以加速字節輸出的實現。調整后的流程如圖 4所示。

圖4 調整后字節輸出流程

這里設置一個專用計數器CT 來進行字節輸出的控制， 當重歸一化發生時，概率間隔寄存器 A 每左移Nbshift位，CT 加Nbshift，當 CT ≥20 時，MQ 算術編碼器輸出一個字節。字節輸出的過程中，若字節緩存 B 中值為 0xFF，則需進行比特填充，以防止進位的傳播影響已編碼字節。當需字節輸出時，根據字節緩沖 B中字節及寄存器 C最高位C_carry的值，進行相應的字節輸出操作。由于C_carry由Nbshift移位得到，而Nbshift最大值為15，也就是說C_carry可能輸出1或2個字節。

2 仿真結果及分析

按照上述系統，選用Xilinx公司的FPGA芯片xc7z020-2clg484，分別實現各個模塊并編程在ISE運行，處理速度達到89.8 MHz。由于該編碼器的工作效率為每個時鐘可編碼1位，該編碼器的工作速度可以達到89.8Mb/s，遠優于軟件實現的MQ編碼。相比參考文獻[6]～[8]較大地提高了編碼效率，對比結果如表2所列。

表2 多種實現方式的時序結果比較

?

方案占用的FPGA資源情況如表3所列，資源占用情況和參考文獻[6]～[8]基本相同。

表3 FPGA資源使用情況

圖5為FPGA實現后的Modelsim仿真所得的數據。由圖5可知，本文提及到的一些寄存器初始值情況，還可以看出CT等于20時已經滿足壓縮字節輸出條件，輸出B（仿真圖中的data_ram_wdata）為0x17。

圖5 FPGA 實現后環路鎖定相位抖動

結語
本文介紹了MQ編碼流程，詳細對其中幾個流程進行了相應的算法優化并使用FPGA實現MQ編碼。

結果顯示優化的MQ編碼在利用有限資源的情況下可以較大幅度提高MQ編碼器的速度，能滿足JPEG2000系統的要求。本論文中所采取的優化設計已經在FPGA硬件平臺驗證通過，并在航拍大分辨率圖像處理的JPEG2000壓縮中得到應用。