基于DSP平臺的JPEG2000 EBCOT-Tier2算法實現及優化

宋璐雯

（西安科技大學 電氣與控制工程學院，陜西 西安 710054）

0 引言

JPEG2000圖像壓縮標準在高幀率的遙感圖像傳輸中有重要應用[1-2]。目前JPEG2000的應用軟件主要有 JasPer，JJ2000，Kakadu。硬件芯片有 ADI推出的ADV212，以及國內自主研發的編解碼芯片[3]。

JPEG2000的可伸縮性嵌入式碼流可以滿足不同要求下的信息傳遞[4-6]。其中EBCOT-Tier2編碼是JPEG2000嵌入式碼流組織的最終體現。分析JasPer中的源代碼，在JPEG2000的EBCOT-Tier1模塊計算后得到位平面信息、編碼通道總數、通道長度、RD斜率。根據硬件平臺特點，將實現EBCOT-Tier2編碼的功能函數依次歸為：讀取編碼參數模塊，主標頭編碼模塊，初始化Tile模塊，拼接塊標頭編碼模塊，讀取碼流信息和碼流數據模塊，讀取Tile信息模塊，碼率控制模塊，碼流打包模塊以及結束編碼模塊。

1 EBCOT-Tier2算法分析

EBCOT-Tier2最核心的是碼率控制模塊，其采用PCRD算法尋找最優截斷點[7,8]。PCRD算法的實質是在滿足累積碼字長度不大于目標碼率的前提下對EBCOT-Tier1編碼后所有的碼塊通道進行截斷，使得圖像的失真度最小[9]。

1.1 RD 斜率

通常將碼塊i的第 ni個編碼通道的率失真斜率定義為 RD斜率，它是碼塊通道被截斷后，對圖像帶來的失真度的減小量與當前編碼通道的長度增加量的比值。

1.2 碼率控制

碼率控制算法是在整個Tile的圖像數據編碼完成后，根據率失真信息判定最優分層截斷點。用數學模型描述碼率控制算法，即：目標碼率定義為Rmax，各個碼塊的截斷位置定義為 ni，圖像失真度定義為D。

目標函數：

約束條件：引入拉格朗日乘子λ，將上述問題轉化為在約束條件下求取公式（4）式的極小值。

可以將（4）式進一步轉化為（5），（6）式：

目標函數：

約束條件：

對目標函數求取偏導數并結合 RD斜率公式進行化簡，最后得到（7），（8）式：

根據最后化簡的表達式，實際就將PCRD碼率控制算法轉化為，尋找一個最優 RD斜率截斷閾值λ，對編碼通道的 RD斜率大于λ的通道進行EBCOT-Tier2打包運算，使得最后的壓縮碼字長度最接近目標碼率maxR 。

2 EBCOT-Tier2算法實現

2.1 碼率控制算法

該模塊是通過二分法尋找最優 RD截斷點。通過比較法得到當前 tile的最大和最小 RD斜率，取二者均值作為第一次搜索的初值，對 RD斜率大于搜索值的所有通道進行標記。之后對標記的通道進行打包，依次進行0位平面tagtree編碼，包含信息tagtree編碼，計算被包含的通道數，長度增量指標，以及寫入該碼塊的通道數據長度，如圖1所示。

圖1 碼率控制流程Fig.1 Code rate control process

通過 out_cur_point（表示當前壓縮文件對應的指針位置）在編碼過程中的指針變換，以及累加當前寫入碼塊的有效通道長度 datalen，來計算 length（表示當前截斷閾值thresh對應的累積碼字長度）的大小。將length與目標碼率tilelen進行比較，判定該截斷點是否最優。如果是最優截斷點，則以該截斷點的值再標記一次通道，以備最后打包使用。為了減少碼率控制的時間，每次搜索只計算要寫入最終壓縮文件的數據長度。如果不是最優截斷點，通過算法調整其值的大小并重新搜索，直至找到最優截斷點。一般情況下，搜索7~8次就可以找到最優截斷點。

2.2 tagtr ee編碼

在EBCOT-Tier2算法實現中碼塊的包含信息和0位平面的計算需要建立 tagtree。tagtree的編碼過程分為兩個步驟[10][11]。在對碼塊建立了四叉數結構后，首先進行第一步父子節點的差值編碼，編碼規則是：在初始化時，最初表中的所有值都是 0，從level0開始編碼，將上一級的編碼值作為下一級編碼的初值。編碼一個0表示加1，編碼一個1表示保持原值不變。在差值編碼結束后，進行第二步tagtree的葉節點編碼。沿著葉節點到父節點的方向進行搜索，若找到根節點或是第一個已經編碼的節點，則停止搜索，并從該位置開始進行tagtree編碼，即沿著搜索的反方向，依次排列組合差值編碼的值，就得到tagtree葉節點的編碼值。

由于在搜索和打包過程中，要頻繁調用 tagtree編碼條件判斷函數，為了避免破壞DSP內部的流水線工作模式，在循環中應該盡量減少跳轉指令，所以要對tagtree編碼函數進行優化，其C語言的實現框圖如圖2所示。

圖2 C 語言實現tagtree編碼Fig.2 Achieve tagtree encoding by C language

3 EBCOT-Tier2算法優化[12-17]

3.1 DSP cache的優化設計

C64x DSP具有兩級存儲器結構，其采用哈佛結構，一級存儲器L1P/L1D cache和L1P/L1D SRAM是固定大小，不可軟件配置。二級存儲器L2，是由程序和數據共享。L2共有1MB的空間大小，具有可配置cache大小的功能。

在對 EBCOT-Tier2打包程序不進行任何 cache優化時，即將 L2配置為 768KB SRAM，256KB cache，使用CACHE_CCFG_L2MODE_256KC語句設置。將EBCOT-Tier2的程序和數據都放在EMIFB CE0對應的片外存儲空間，在cmd文件設置時，將所有段都放在0x60000000~0x63FFFFFF的空間范圍內。對于輸入256*256 lena_gray圖像的碼流信息和碼流數據，壓縮10倍，進行9/7小波變換，EBCOTTier2的編碼打包時間是 0.008918s，即處理速度是112f/s。由于程序和數據都放在外部存儲器，在每次訪問數據信息時都要經歷外部存儲器—L2 cache—L1 cache的過程，所以代碼的運行效率不高。

分析代碼，在只對一幅圖像進行處理時，程序占用59KB空間。碼流信息，碼流數據和壓縮參數，這三組數據共占251KB空間。而此時L2有足夠大的空間以存放這些程序和數據，所以將L2都設置成為 SRAM，CACHE_FSET（CCFG，L2MODE，CACHE_CCFG_L2MODE_0KC）。

此外，在 C64x DSP中 long型的數據位寬是40bits。如果程序中可以使用short型數據就避免使用int型數據，因為L1D的行大小是64B，采用short型就可以存放比int型多一倍的數據，這樣可以提高L1D的使用效率，降低cache miss的發生以及miss所帶來的stall數。

對EBCOT-Tier2編碼打包程序進行上述優化，輸入256*256的lena_gray圖像的碼流信息和碼流數據，壓縮10倍，進行9/7小波變換。統計cache的使用情況如下表1所示。

從上表數據可以看出，cache的命中率較高。這是因為沒有信息存放在外部存儲器，而是按照 L2 SRAM—L1 cache的順序訪問數據。其EBCOT-Tier2的運行時間是0.004566 s，處理速度是219 f/s。與上未優化的處理速度比較，代碼的運行效率有明顯提高。

3.2 碼率控制算法優化

使用DSP的內部Timer0定時器對EBCOT-Tier2程序的每個子模塊函數計時，發現碼率控制函數是最耗費時間，它運行了2277128個CPU時鐘。對碼率控制函數進行具體分析，如下表2所示。

表1 Cache統計Tab.1 Cach e statistics

表2 碼率控制函數運行時間統計Tab.2 The time statistics of code rate control

從上表可以明顯看出，計算包頭信息耗費了大量時間，而在包頭信息計算中tagtree編碼最耗費時間。這是因為在碼率控制尋找最優截斷點時，每刷新一次搜索值，都要進行一次相當于打包的計算量，要對所有標記的通道進行編碼。

為提高搜索效率，首先考慮對EBCOT-Tier1輸出的碼流信息進行處理，列一個256項的統計表，將圖像分成了256個質量層。然后從最高項依次向下累加，若累加的碼字長度開始大于目標碼率長度，則此時的 RD斜率值，定為最優截斷點。當輸入圖像是256×256灰度lena圖像，壓縮10倍時，根據最初的二分法搜索，測得的最優RD截斷值是149。在以該方法確定最優截斷點時，發現搜索的復雜度降低了，但是搜索的次數增多，效率變慢，而且最后得到的最優 RD截斷值要比原始的測量方法小2~3。由于該搜索方法，只依賴于 EBCOT-Tier1編碼的壓縮碼流長度，而忽略了EBCOT-Tier2的所有編碼信息。而在一般情況下，基于 JPEG2000標準的壓縮文件的包頭信息占壓縮文件的5%~10%。

基于以上論述，從另一角度分析搜索過程。包頭信息是由6部分構成的，SOP Marker標志位信息，零長度包標志，碼塊包含信息，0位平面包含信息，每個碼塊包含在包中的編碼通道數以及每個碼塊對壓縮碼流貢獻的字節長度編碼。在搜索過程中，最耗費時間的模塊是tagtree編碼，即碼塊包含信息和0位平面包含信息?？紤]在搜索的過程中，簡化包頭計算，即先不計算包頭信息的兩個tagtree編碼，但是保留其他包頭信息的計算。這樣在搜索過程中，對標記的通道計算被該層包含的通道數，計算寫入的長度增量以及計算寫入的該碼塊被截斷的通道數據長度，最后通過指針變換，計算出累積碼字長度，并與目標碼率進行對比，根據對比結果判定是否需要進行下一次二分法搜索，若確定此時的截斷值為最優 RD斜率截斷點，則碼率控制函數不需要再以該 RD斜率值標記一次通道，這是因為在最后一次搜索中通道已經被標記過，所以不用再進行冗余計算。最后，根據每個碼塊的每個通道的標記信息就可以進行完整的打包運算得到.jpc壓縮文件。

以輸入256×256 lena灰度圖像，進行9/7小波變換，壓縮 10倍為例進行說明。發現改進算法的tagtree編碼耗費時間明顯降低，據統計耗費了119264個時鐘周期。進行多次試驗觀察比較在不同壓縮倍數下，改進算法與原始算法在確定最優截斷點的差異，統計結果如下表3所示。

表3 RD 斜率最優截斷點對比Tab.3 Comparison of RD slope optimal cut-off points

觀察上表的統計結果，發現改進算法的最優截斷點的值通常會比原始算法的值小 1。接著，通過測量PSNR值進一步定性分析改進算法的特性。分別測試由JasPer軟件打包的PSNR的標準值和改進算法得到的PSNR值，如表4所示。

表4 PSNR 對比Tab.4 The comparison of PSNR

從以上數據可以分析得到，改進算法的 PSNR值比JasPer軟件的標準值略大，但是二者PSNR值的差異一般最大不超過 0.2dB。再以對比改進算法與原始算法的EBCOT-Tier2運行效率來說明改進算法的性能提升，結果如表5所示。

表5 EBCOT-Tier2運行效率對比Tab.5 The comparison of EBCOT-Tier2 operating efficiency

從以上數據可以看出，改進算法的運行速度有顯著的提高，速度基本上是原始算法的2倍左右。綜合考慮壓縮圖像質量和打包速率這兩大因素，認為簡化包頭計算的改進型碼率控制算法可用于JPEG2000圖像的實時編碼打包。

4 結語

針對 C64x DSP的硬件平臺，首先分析實現JPEG2000的 EBCOT-Tier2編碼打包功能。接著根據DSP的兩級cache特點進行代碼優化。最后使用DSP的內部定時器找到碼率控制模塊中最耗時的計算模塊，根據PCRD的算法特點，提出了一種簡化包頭信息計算的碼率控制算法，通過驗證仿真，該算法提高了EBCOT-Tier2的編碼打包效率。

[1] 楊雪, 陳凡勝. 基于預測和JPEG2000的紅外圖像無損壓縮方法[J]. 紅外技術, 2016, 38(2): 144-148.

[2] Dong K K, Kim E Y, Yang K H, et al. A mobile tele-radiology imaging system with JPEG2000 for an emergency care.[J]. Journal of Digital Imaging, 2011, 24(4): 709-18.

[3] Liu L, Li D, Li Z, et al. A VLSI Architecture of EBCOT Encoder for JPEG2000[J]. Journal of Beijing University of Posts & Telecommunications, 2003, 2: 882-885 Vol.2.

[4] 孫水發, 張華熊, 仇佩亮. JPEG2000--新的靜止圖像壓縮標準[J]. 計算機輔助設計與圖形學學報, 2003, 15(11):1339-1346.

[5] Singh A, Nirala N K, Narula A, et al. JPEG2000: The upcoming still image compression standard[J]. Pattern Recognition Letters, 2001, 22(12): 1337-1345.

[6] 劉方敏, 吳永輝, 俞建新. JPEG2000圖像壓縮過程及原理概述[J]. 計算機輔助設計與圖形學學報, 2002, 14(10): 905-911.

[7] 茅文深, 俞劍, 劉文松,等. JPEG2000碼率控制截斷預測算法及VLSI設計[J]. 計算機與數字工程, 2016, 44(1): 189-192.

[8] 莊懷宇, 吳成柯, 鄧家先, 等. JPEG2000 T_2編碼快速算法及硬件實現[J]. 系統工程與電子技術, 2004, 26(12):1939-1942.

[9] 李其虎, 任國強, 吳欽章,等. 一種率失真最優的JPEG2000碼率自適應控制算法[J]. 測繪學報, 2011, 40(2): 204-208.

[10] 胡高軍, 任廣輝, 吳芝路. JPEG2000中Tag-tree編碼分析及實現[J]. 電視技術, 2004(10): 13-15.

[11] 吳宗澤, 鄭南寧, 黃宇, 等. 基于JPEG2000的TAGTREE編碼算法分析及其FPGA實現[J]. 小型微型計算機系統, 2005,26(3): 478-481.

[12] 賀文靜, 胡堅, 李子揚,等. 基于多DSP的遙感圖像實時壓縮系統設計[J]. 電子技術應用, 2015, 41(5): 46-49.

[13] 曾勇. JPEG2000新型碼率控制算法及其DSP實現[J]. 電子科技, 2011, 24(7): 122-125.

[14] Tan K C B, Arslan T. Low power embedded extension algorithm for lifting-based discrete wavelet transform in JPEG2000[J]. Electronics Letters, 2002, 37(22): 1328-1330.

[15] Du W, Sun J, Ni Q. Fast and efficient rate control approach for JPEG2000[J]. IEEE Transactions on Consumer Electronics,2004, 50(4): 1218-1221.

[16] Son C H, Kim J W, Song S G, et al. Low complexity embedded compression algorithm for reduction of memory size and bandwidth requirements in the JPEG2000 encoder[J].IEEE Transactions on Consumer Electronics, 2010, 56(4):2421-2429.

[17] An J, Cai Z. Efficient Rate Control for Lossless Mode of JPEG2000[J]. IEEE Signal Processing Letters, 2008, 15: 409-412.