JPEG2000的MQ模塊在DSP環境下的優化實現

張浩宇，徐建軍，張　南

（國防科學技術大學 計算機學院，長沙　410072）

JPEG2000的MQ模塊在DSP環境下的優化實現

張浩宇，徐建軍，張南

（國防科學技術大學 計算機學院，長沙410072）

隨著航空技術和專用CCD/CMOS成像技術的飛速發展，星載系統中圖像的大小和清晰度都成倍的提高，由此帶來的數據量和帶寬要求也呈指數級增長，如何在星載高性能的計算平臺下有效壓縮圖像成為了星載系統面臨的最主要挑戰之一。經典的JPEG2000圖像壓縮算法，其模塊并不適應高性能DSP中編譯器進行流水線排布的要求，導致運行效率無法達到要求。本文面向JPEG2000圖像壓縮算法，提出一種在DSP環境下，JPEG2000算法中MQ編碼器的優化算法。優化算法使用了多種線性匯編語言流水線排布的通用優化技術對MQ編碼器進行DSP環境適應性優化，并根據MQ編碼器算法特點，進行了編碼流程簡化和二次重歸一化過程中冗余分支的消除。圖像壓縮試驗表明，該算法提高了MQ編碼器的吞吐率，提升了JPEG2000的壓縮效率。

數字信號處理器；JPEG2000；算術編碼器；線性匯編

本文著錄格式：張浩宇，徐建軍，張南. JPEG2000的MQ模塊在DSP環境下的優化實現[J]. 軟件，2016，37（9）：130-135

1　引言

在航天偵測領域，隨著圖像處理技術的進步和應用需求的發展，海量的探測數據和有限的空地數傳帶寬之間的矛盾亟待解決。高性能DSP[1]的出現使得高速在軌圖像壓縮成為可能，依靠多個功能部件并發執行指令和軟件流水排布技術，高性能 DSP顯著提升了程序代碼尤其是其中循環代碼的執行效率。但是其編譯器在進行軟件流水線排布時有著諸如循環中的代碼不能過長，一般不能超過250條線性匯編指令；循環中不能有函數調用；循環中不能有跳轉指令；循環中的條件判讀不能過多，一般不能超過6個；循環不能有嵌套；程序執行時不能有中斷產生等限制[1]，這就對程序代碼的編寫提出了嚴格的要求。

JPEG2000是新一代的圖像壓縮算法，具有壓縮速度快，信噪比高，同時支持有損和無損壓縮，可同時生成多種分辨率等優點。JPEG2000的壓縮過程如圖1所示，其中的嵌入式塊編碼過程（EBCOT）把經過離散小波變化（DWT）得到的小波系數分成互相不重疊且大小相同的編碼塊，然后將編碼塊按比特位高低分成多個位平面，然后從最高有效位平面到最低有效位平面，對于每個位平面進行基于上下文的算術編碼（MQ編碼）。

圖1　JPEG2000編碼流程

圖2是MQ編碼器的一個簡要工作流程。它的輸入是當前的數據位D和當前位的上下文（如前文表述概念）決定的類型CX組成的一個決定對，而輸出是單個的壓縮碼字，也就是壓縮數據CD。壓縮數據CD也叫做一個“MQ碼段”，只是被壓縮的碼流中的一部分。當數據位D和類型CX組成的數據對（CX，D）從位平面編碼器到達時，壓縮數據位CD增量的產生。

MQ編碼器使用了狀態變量來實現算術編碼，這些變量包括A，C，temp，t和L。A和C是分別用來表示概率區間長度和下限，他們一起表示出當前的概率子區間。temp為一臨時的字節緩沖器，用來保存輸出的編碼。t用作一個計數器，當這個計數器減少到零時，部分產生的編碼位應被移出C寄存器，并移入臨時字節緩沖器temp中。L代表到當前為止所產生的編碼字節數。

圖2　MQ編碼器流程

由于不同碼流引起的輸出序列是不同且唯一的，所以MQ編碼器對于不同的碼流概率估計值也不可能是固定的，必須能夠實現隨著碼流數據變化而隨時調整。MQ編碼器通過使用概率值表和上下文狀態表能夠實現隨碼流變化自適應的功能。

其中概率估計表是一個可以對原始數據快速適應的概率估計模型。概率估計表包括47個索引值。每個索引都對應著不同的狀態，每個狀態有28位，其中6位是當前符號是大概率符號（MPS）時下一個索引（NMPS）；6位是當前符號是小概率符號（LPS）時下一個索引（NLPS）；一位是交換位（SWITCH）來確定本輪是否發生大概率符號的交換，只有當前符號是小概率符號的時候才有可能用到；15位是小概率符號的概率值（Qe），它體現了序號值Index和對類型CX的LPS最不可能符號的估計概率之間的關系。大概率符號（MPS）就是在之前的碼流中出現的次數多的符號，它就是0或者1，隨著碼流輸入不斷變化。

上下文概率映射表包括19個不同的狀態，每個狀態包括索引值（index）和大概率符號值（MPS）。Index是一個范圍從0到46的6比特量，對應于概率估計表中的一項，用于標識對當前類型的符號集合做的概率估計。

MQ編碼器大體可以分為兩個主要階段[2]，第一階段是編碼階段，根據輸入的上下文判斷當前的編碼符號的類型是大概率符號（MPS）還是小概率符號（LPS），并根據該類型當前保存的索引取出當前該類型符號的概率估計值（Qe），并根據Qe值按照輸入D進行新概率計算，更新A、C寄存器和該類型的索引。第二階段是重歸一化階段，主要進行碼流的輸出和概率的重歸一化。

針對MQ編碼器的性能問題，不少學者提出了優化方案，劉奇衛[3]等人設計了4級流水線的2符號并發編碼結構，王振道[4]等人設計實現了一種部分并行的優化算法，但這些優化都是針對算法本身的改進，沒有針對DSP應用平臺，仍無法改變其不適應DSP環境的問題。本文基于TI的C6000系列DSP，消除了JPEG2000在DSP環境下對流水線排布影響較大的上下文機制，將MQ編碼器模塊進行適應性改造，大幅提高了程序的運行速度。

2　改寫過程中的線性匯編優化

首先對于MQ編碼器使用線性匯編語言進行改寫，但僅僅對原模塊進行簡單的線性匯編改造，并沒有體現出本文選擇DSP處理器的初衷。為了充分發揮DSP并行優勢，提高程序性能，使用了以下方法：

（1）使用DSP環境下的指令條件執行機制來取代原有跳轉指令。根據不同的DSP型號，在DSP中一般會提供5-6個條件寄存器，儲存在該寄存器中的變量可用于作為其它指令的條件：即當條件寄存器內變量非0時，使用它作為條件的指令就會被執行，否則則不執行，具體改造示例如圖3所示：

圖3　使用條件執行機制消除跳轉

（2）循環展開。由于編譯器進行流水排布時只對最內層循環進行排布，因此在程序改造中通過條件執行機制將嵌套循環的外層循環每次迭代后的參數變化改為條件執行語句，從而展開這一層循環，擴大流水排布范圍，達到進一步改善流水排布效果的目的。具體改造示例如圖4所示：

圖4　使用條件執行機制展開循環

（3）通過數據預取與打包減少流水空閑。流水線排布的成功與否主要受到程序 的結構影響，而排布成功之后的流水線的執行時間則主要受制于訪存指令多少。訪存指令需要多個周期執行，且往往與其后的指令有較高的相關性，很多時候會導致流水線因等待數據而停滯。對此，本文主要采用一次存取多個數據和提前讀取數據的方法減少訪存指令的數量及其造成的流水線空白期。C6000系列一次可以存取64位數據，而一般程序中處理的數據以16位和32位為主，這樣通過64位的存取操作指令和數據處理指令我們可以一次讀取多個數據從而減少存取指令的數量。同時，我們將循環中的讀取指令提前，即在進入循環前預取第一次循環所要用到的數據，以后每次循環都在做本次循環的數據處理的同時預取下次循環即將用到的數據，減少因等待數據而造成的流水線停滯。

3　MQ編碼器模塊優化

針對DSP獨特的體系結構，為了提高MQ模塊在DSP環境下的效率，不僅僅需要在匯編語言級別進行適應性優化，而且需要對MQ編碼器的流程進行優化改造，使之在目標平臺上具有更高的效率。

3.1編碼流程簡化

MQ的編碼階段的算法流程如圖5所示，算法有五條執行路徑，在原有算法的運行情況下DSP的匯編優化器難以排布并行流水線，效率會大大降低。而如果基于前述的DSP并行流水排布規則進行優化，為了消除分支指令，相當于將5條路徑全部展開串行執行，將導致循環單次迭代長度過長且相關性較高，即使排布出流水也極大的影響流水線排布效果。因此，需要對算法的執行流程進行優化。

將圖中的左路分支合并入右路后MQ編碼器的重歸一化流程如圖6所示，其中，當t=0時的字節輸出過程在一次重歸一化過程中最多執行2次，輸出字節時有兩種情況主要是因為MQ編碼器當0xFF字節被輸出到字節緩沖器時，會將一多余的冗余位插入到變化的碼字中，保證來自之前編碼中對C寄存器的算術操作所產生的進位不會傳播到已經被發送到字節緩沖中的字節。在發生第一次字節輸出時，由于C寄存器的值來源于編碼階段，在發生C=C+D的操作時可能會產生進位，故8位的temp寄存器的值在與進位相加時出現了3種可能會大于等于0xFF的情況，這就使得不僅需要對輸出進行獨立，使temp=0x100時輸出0xFF，還需要在寄存器向temp中移入值時考慮進位的存在，導致這一分支比較復雜。但是在第二次字節輸出發生時，寄存器C和t的值都來源于上一次字節輸出后的更新，這種情況下，上一次字節輸出后的處理保證了這一次t=0時C一定不會產生進位，故不需要考慮特殊的輸出，也不需要考慮保留進位，其過程可簡化成如，從而減少冗余分支，提高性能。

圖5　MQ編碼器編碼流程

圖6　優化后的MQ編碼流程

圖7　重歸一化階段算法流程圖

3.2二次重歸一化的冗余分支消除

首先將圖7中的左路分支合并入右路后MQ編碼器的重歸一化流程。其中，當t=0時的字節輸出過程在一次重歸一化過程中最多執行2次，輸出字節時有兩種情況主要是因為MQ編碼器當0xFF字節被輸出到字節緩沖器時，會將一多余的冗余位插入到變化的碼字中，保證來自之前編碼中對C寄存器的算術操作所產生的進位不會傳播到已經被發送到字節緩沖中的字節。

在發生第一次字節輸出時，由于C寄存器的值來源于編碼階段，在發生C=C+D的操作時可能會產生進位，故8位的temp寄存器的值在與進位相加時出現了3種可能會大于等于0xFF的情況，這就使得不僅需要對輸出進行獨立，使temp=0x100時輸出0xFF，還需要在寄存器向temp中移入值時考慮進位的存在，導致這一分支比較復雜。

但在第二次字節輸出發生時，寄存器C和t的值都來源于上一次字節輸出后的更新，這種情況下，上一次字節輸出后的處理保證了這一次t=0時C一定不會產生進位，故不需要考慮特殊的輸出，也不需要考慮保留進位，其過程可簡化成如圖8，從而減少冗余分支，提高性能。

圖8　優化后輸出過程

4　試驗及測試結果

選用不同分辨率下的圖像壓縮的標準測試樣本中Lena的黑白二值圖片作為測試集合。對于使用原始MQ編碼器模塊的JPEG2000程序及使用優化后版本的JPEG2000程序分別進行壓縮測試并利用Profiler獲取其總執行時間及MQ模塊執行時間。各程序版本編譯選項為-opt-level=3。測試結果如下表所示。測試結果表明，本文提出的MQ模塊優化改造有效提高了MQ模塊及壓縮程序的執行效率。

圖9　圖像測試集

表1　壓縮測試結果

5　結束語

本文提出了一種星載DSP環境下JPEG2000的算術編碼模塊的優化方案，該方案采用循環展開等方法解決原程序無法排布軟件流水的問題，另外通過算法執行路徑和垂直提升算法進行優化改造，從而大大提高了MQ模塊的單次執行效率以及JPEG2000壓縮算法的整體壓縮效率。另外，該方法在實際使用中還有若干問題有待解決，如MQ編碼器軟件流水排布效率問題以及JPEG2000中其他模塊的優化問題等，都有待于進一步研究。

[1] Texas Instruments Incorporated. TMS320C6000系列DSP編程工具與指南[M]. 田黎育, 何佩琨. 出版地: 北京清華大學出版社, 2006. 9: 235-240.

[2] Skodras A, Christopoulos C, Ebrahimi T. The Jpeg 2000 Still Image Compression Standard[J]. IEEE Signal Processing Magazine, 2010, 18(5): 36-58.

[3] 劉奇衛. 基于JPEG2000二進制算術編碼器的研究與設計[D]. 浙江大學, 2006.

[4] 王鎮道, 章兢等. 一種JPEG2000算術編碼器的優化算法與實現[J]. 湖南大學學報(自然科學版), 2007, 34(4).

Optimization and Implementation of MQ Encoder of JPEG2000 in DSP

ZHANG Hao-yu, XU Jian-jun, ZHANG Nan
(Academy of Computer Science and Technology, National University of Defense Technology, Changsha 410072)

With the rapid development of aviation technology and a dedicated CCD/CMOS imaging technology, space borne system image size and clarity are increased exponentially, which lead to the exponential growing of the magnitude of data and bandwidth requirements. Therefore, how to compress images effectively in space borne systems have become a hot topic and a serious challenge. The classic JPEG2000 image compression algorithm is not designed to run on DSP, so the perfermance decline rapidly. This paper present a optimized MQ-encoder in DSP based on JPEG2000 compression algorithm. The optimizations used in the paper include serval common optimized techonologies in order to let the compiler construct pipeline properly. Furthermore, based on the characters of MQ encoder, we simplify the encoding flow and cut some paths in the secondary normalization. According to the experiment results, the optimized MQ-encode algorithm applying our method achieves higher throughput compared to the classical algorithm.

DSP; JPEG2000; MQ; Arithmetic-Encoder

TP391.41

A

10.3969/j.issn.1003-6970.2016.09.031