張浩宇，徐建軍，張　南

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

JPEG2000的MQ模塊在DSP環(huán)境下的優(yōu)化實現(xiàn)

張浩宇，徐建軍，張南

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

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

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

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

1　引言

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

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

圖1　JPEG2000編碼流程

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

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

圖2　MQ編碼器流程

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

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

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

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

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

2　改寫過程中的線性匯編優(yōu)化

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

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

圖3　使用條件執(zhí)行機制消除跳轉

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

圖4　使用條件執(zhí)行機制展開循環(huán)

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

3　MQ編碼器模塊優(yōu)化

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

3.1編碼流程簡化

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

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

圖5　MQ編碼器編碼流程

圖6　優(yōu)化后的MQ編碼流程

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

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

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

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

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

圖8　優(yōu)化后輸出過程

4　試驗及測試結果

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

圖9　圖像測試集

表1　壓縮測試結果

5　結束語

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

[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] 劉奇衛(wèi). 基于JPEG2000二進制算術編碼器的研究與設計[D]. 浙江大學, 2006.

[4] 王鎮(zhèn)道, 章兢等. 一種JPEG2000算術編碼器的優(yōu)化算法與實現(xiàn)[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