范文晶，王召利，王惠娟，費聚鋒，李蕭蕭

(1.上海機電工程研究所 6室，上海 201109；2. 上海無線電設(shè)備研究所，上海 200090)

?

基于FPGA的無損圖像壓縮算法實現(xiàn)

范文晶1，王召利2，王惠娟1，費聚鋒2，李蕭蕭1

(1.上海機電工程研究所 6室，上海 201109；2. 上海無線電設(shè)備研究所，上海 200090)

針對采用傳統(tǒng)硬件方法實現(xiàn)JPEG-LS無損圖像壓縮算法時延時較多、實時性較差的問題，文中提出了一種基于FPGA的全流水線結(jié)構(gòu)來實現(xiàn)JPEG-LS算法。該結(jié)構(gòu)以提高最大吞吐量為主要目標(biāo)，通過多級流水線降低每一級運算的延遲，大幅提高了壓縮算法的實時性，硬件電路操作頻率可達120MHz。

全流水線；無損圖像壓縮；大吞吐量；FPGA

傳統(tǒng)硬件方法在實現(xiàn)JPEG-LS無損圖像壓縮算法時延時較多、實時性差，為滿足高速圖像傳感器系統(tǒng)的吞吐量需求[1-2]，選用FPGA來實現(xiàn)無損圖像壓縮算法，以提高最大吞吐量為主要目標(biāo)，通過全流水線降低每一級運算的延遲，從而滿足嚴(yán)格的時序約束，大幅提高了壓縮算法的實時性。

1 無損壓縮算法

JPEG-LS無損壓縮算法的基本思想為[3-5]：由當(dāng)前像素的幾個已經(jīng)出現(xiàn)過的近鄰，用其作為當(dāng)前像素的上下文，用上下文來預(yù)測誤差，從幾個這樣的概率分布中選擇一個，并根據(jù)該分布用一個特殊的Golomb碼字來編碼預(yù)測誤差。JPEG-LS圖像壓縮標(biāo)準(zhǔn)規(guī)定的無損和近無損編碼處理的主要組成部分如圖1所示。

圖1 JPEG-LS編碼器模型

JPEG-LS圖像壓縮標(biāo)準(zhǔn)采用差分預(yù)測編碼技術(shù)，同時建立了匹配上下文模型，高效地實現(xiàn)了One-pass編碼器[6～7]，具體算法實現(xiàn)過程如圖2所示。

圖2 JPEG-LS 壓縮算法框圖

該編碼器基于光柵掃描順序，每次對一個像素進行編碼。具體的編碼方式分為兩種，即正常模式和游長模式，且這兩種模式之間是自適應(yīng)切換的[8-10]。

在正常編碼模式下，首先采用簡單的邊緣檢測器初步確定一個預(yù)測值[11-12]；然后再與上下文自適應(yīng)的預(yù)測校正值相結(jié)合得到校正預(yù)測值；最后使用當(dāng)前待編碼原始像素值減去校正預(yù)測值就能得到預(yù)測殘差，該預(yù)測殘差的分布滿足雙邊幾何分布，利用上下文模型可求得預(yù)測殘差的編碼參數(shù)k，熵編碼器采用參數(shù)k完成Golomb快速一元編碼[13-15]。當(dāng)編碼器進入游長編碼模式時，完成游長計數(shù)后，熵編碼器采用效率更高的游長編碼，從而對平滑圖像可進行大倍率的壓縮[16]。

2 JPEG-LS無損壓縮算法的FPGA實現(xiàn)

采用標(biāo)準(zhǔn)JPEG-LS算法進行無損壓縮硬件實現(xiàn)時存在一些不足：

(1)在計算上下文Q時，需要多步串行計算才能得到Q值，關(guān)鍵路徑較長，難以滿足實時處理的要求；

(2)在計算誤差以及誤差量化時，采用標(biāo)準(zhǔn)算法時用到浮點乘法，計算精度不能保證，計算復(fù)雜度較高，難以滿足快速處理的要求；

(3)參數(shù)變量更新時，標(biāo)準(zhǔn)算法涉及較多的加減運算和邏輯判斷，且諸多操作是串行運算，計算復(fù)雜度較高，影響了整個系統(tǒng)運行速度的提升。

JPEG-LS算法包括較多順序運算步驟，如果直接按照算法實現(xiàn)為硬件邏輯，將會產(chǎn)生較大的延遲時間，嚴(yán)重阻礙時鐘頻率的提高。

針對以上問題，本文提出的JPEG-LS實現(xiàn)結(jié)構(gòu)以提高最大吞吐量為主要目標(biāo)，通過多級流水線降低每一級運算的延遲，從而滿足更嚴(yán)格的時序約束。除流水線機制外，通過在較細(xì)的粒度上實現(xiàn)運算的并行，提高了每一級運算的速度。

2.1 并行運算降低硬件資源消耗

設(shè)計采用FPGA片內(nèi)的Block Ram或Rom資源以存儲計算所得的變量值，在JPEG-LS標(biāo)準(zhǔn)中，計算量化梯度合并時，若矢量(Q1,Q2,Q3)的第一個非零元素是一個負(fù)數(shù)，則必須將該矢量的符合反轉(zhuǎn)得到(-Q1,-Q2,-Q3)，此時變量SIGN被設(shè)置為-1，反之為+1；在這種可能的合并之后，矢量(Q1,Q2,Q3)以一對一的方式被映射到一個整數(shù)Q，其表示采樣X的上下文。

然而在JPEG-LS標(biāo)準(zhǔn)中并沒有規(guī)定此映射過程的具體函數(shù)，為了能簡單實現(xiàn)查找A[Q]、B[Q]、C[Q]、N[Q]表值，將Qi做了優(yōu)化修改，根據(jù)輸入的Ra、Rb、Rc、Rd分別計算Rd-Rb、Rb-Rc和Rc-Ra，根據(jù)JPEG-LS標(biāo)準(zhǔn)，以這3個梯度值為索引，查表得到3個梯度的量化梯度值id1、id2、id3，在FPGA中使用量化公式

Q=id1×92+id2×9+id3

(1)

映射后可通過Q值判斷SIGN值，若Q>0，則SIGN為1，若Q<0，則SIGN為-1；變量Q則成為索引A[Q]、B[Q]、C[Q]、N[Q]的地址值，此次優(yōu)化降低了算法復(fù)雜度，提高了效率。在計算得到預(yù)測值,根據(jù)預(yù)測值通過量化后得到誤差值以及量化誤差值的過程如下

if(Errval)>0

Errval=(Errval+NEAR)/(2*NEAR+1)

else

Errval=-(Errval-NEAR)/(2*NEAR+1)

(2)

此過程實現(xiàn)較為復(fù)雜，且周期較長，使得整個過程實時性降低。針對此處計算，設(shè)計查詢表的方式替代原浮點乘法運算，由于誤差Errval的范圍在-255～+256之間，所以將Errval之間的值通過上述方法提前算好建立一張Table表存儲在FPGA內(nèi)部資源ROM中，每次只需以誤差值為地址去ROM中查找對應(yīng)的量化誤差值即可。通過以上方法，將復(fù)雜的算法以及耗時的計算變?yōu)榱艘淮尾楸砭湍芡瓿?，大幅降低了計算量，提高了實時性。

對某一像素 編碼的最后一步是更新變量A[Q]、B[Q]、C[Q]、N[Q]，但該變量更新處理必須在編碼過程的最后。為提高編碼實時性，使變量的更新周期減少，設(shè)計了一種新的變量更新方式，如圖3所示。

圖3 變量更新結(jié)構(gòu)圖

根據(jù)以上變量更新的方法，得到一組新的A[Q]、B[Q]、C[Q]、N[Q]值，并且將其分別存儲在FPGA內(nèi)存雙口RAM中，在下一次計算來臨時可根據(jù)當(dāng)前計算得到的Q值作為地址，從4個雙口RAM中讀取上一次更新的A[Q]、B[Q]、C[Q]、N[Q]值，再通過變量更新模塊獲得新的更新值存入RAM中。

2.2 算法流水線結(jié)構(gòu)

為提高硬件平臺操作速率以及考慮到系統(tǒng)的實時性，選用流水線結(jié)構(gòu)是實現(xiàn)此算法的必要途徑，如圖4所示。為了完全實現(xiàn)此流水線結(jié)構(gòu)，使用了10個時鐘周期的流水線階段。為避免結(jié)構(gòu)圖過于復(fù)雜，此處僅是正常模式下的流水線結(jié)構(gòu)圖，并未給出游程模式結(jié)構(gòu)圖。運用此流水線模式可使得硬件電路操作頻率達到120 MHz。

圖4 JPEG-LS流水線硬件結(jié)構(gòu)圖

如圖4所示，10個流水線階段分別完成以下步驟：

階段1 完成預(yù)測值計算以及局部梯度值計算；

階段2 局部梯度值量化；

階段3 查詢變量Q地址；

階段4 讀取環(huán)境變量(上下文)值；

階段5 更新環(huán)境變量值；

階段6～8 3個周期除法器；

階段9 以及預(yù)測誤差值計算；

階段10 誤差映射及產(chǎn)生bit流輸出。

在FPGA中利用流水線的方式來實現(xiàn)算法，各模塊的計算復(fù)雜度基本相同，且?guī)讉€模塊可同時進行計算，減少了每一級的運算時間，提高了系統(tǒng)實時性。

圖5 常規(guī)編碼和帶有前向預(yù)判機制的上下文參數(shù)更新時序圖

3 實驗及結(jié)果

為完成整個編碼系統(tǒng)，包括預(yù)測器和熵編碼器兩部分功能，選用Altera公司Stratix 系列FPGA，在Quartus軟件環(huán)境下使用Verilog HDL語言進行編程實現(xiàn)。將傳統(tǒng)硬件實現(xiàn)方法和前流水線的JPEG-LS硬件實現(xiàn)的內(nèi)存消耗、消耗邏輯門單元和硬件操作頻率做對比，對比結(jié)果如表1所示。

表1 傳統(tǒng)硬件方法實現(xiàn)JPEG-LS和全流水線的JPEG-LS硬件實現(xiàn)比較

由表1可知，采用了全流水線結(jié)構(gòu)來實現(xiàn)JPEG-LS算法，大幅降低了FPGA內(nèi)存空間占用，內(nèi)存空間占用被降低了26%。該流水線模式也使得硬件電路操作頻率由105 MHz提高到120 MHz，滿足嚴(yán)格的時序約束，且提高了壓縮算法的實時性。

4 結(jié)束語

為滿足高速圖像傳感器系統(tǒng)的吞吐量需求，本文在FPGA中采用全流水線結(jié)構(gòu)，降低了每一級運算的延遲，實現(xiàn)了JPEG-LS無損/近無損圖像壓縮算法。該算法已在FPGA平臺通過驗證，實現(xiàn)了大吞吐量的無損圖像壓縮，可應(yīng)用于高速圖像傳輸系統(tǒng)中。

[1] 沈洪亮,劉金國.基于JPEG-LS的遙感圖像無損壓縮技術(shù)[J].光電子技術(shù),2009,29(3):206-210.

[2] Marcelo Weinberger, Gadiel Seroussi, Guillermo Sapiro. The LOCO-I lossless image compression algorithm: principles and standardization into JPEG-LS[J].IEEE Transations on Image Proceeding,2000, 9(8):1310-1322.

[3] 唐垚,曹劍中,李變俠,等.基于FPGA的JPEG-LS無損壓縮算法的實現(xiàn)[J].彈箭與制導(dǎo)學(xué)報,2006,26(SA):1219-1222.

[4] 劉嘉晗,趙巖,王宇心,等.高性能全流水線可控參數(shù)JPEG-LS 編碼器實現(xiàn)[J].微電子學(xué)與計算機,2010,27(2):34-37.

[5] BeDi S,Edris E.Improvement to the JPEG-LS pre diction scheme[J].Elsevier on Image Vision Computing,2004,22(1):9-14.

[6] Merlino P, Abramo A.A fully pipeline architecture for the LOCOI compression algorithm[J].IEEE Transactions on Very Large Scale Integration (VLSI),2009,17(7):967-971.

[7] 李曉雯,陳新凱,李國林,等.低功耗全流水線JPEG-LS無損圖像編碼器的VLSI設(shè)計[J].清華大學(xué)學(xué)報:自然科學(xué)版,2007,47(10):1654-1658.

[8] 張毅.碼率可控的JPEG-LS近無損圖像壓縮編碼器硬件實現(xiàn)[D].西安:西安電子科技大學(xué),2014.

[9] 郝勇崢.基于JPEG-LS算法的星載圖像壓縮系統(tǒng)設(shè)計[D].西安:西安電子科技大學(xué),2011.

[10] 徐燕凌,劉蓓.JPEG-LS圖像壓縮動態(tài)碼率控制策略[J].計算機工程,2008,34(7):238-239,271.

[11] 崔倩.JPEG-LS碼率控制算法研究[D].西安:西安電子科技大學(xué),2011.

[12] 張芝賢,王玉周,劉筠筠.基于DSP的圖像采集及JPEG-LS壓縮系統(tǒng)[J].微計算機信息,2009,25(29):139-140,190.

[13] 楊武,董世都,張光建.一種基于小波系數(shù)上下文模型的圖像壓縮方法[J].微電子學(xué)與計算機,2006,23(4):153-155,159.

[14] 劉強,彭玉濤.基于流水線技術(shù)的無損JPEG-LS編碼器實現(xiàn)新方法[J].科技信息,2011(35):120-121,134.

[15] 曹青,吳樂南.靜止圖像無失真編碼的新標(biāo)準(zhǔn)JPEG-LS[J].電子工程師,1999(2):12-14.

[16] 王黎明,趙英亮,韓焱,等.基于JPEG-LS框架的無損壓縮技術(shù)研究[J].電腦開發(fā)與應(yīng)用,2002,15(4):6-7.

Implementation of Lossless Image Compression Algorithm Based on FPGA

FAN Wenjing1, WANG Zhaoli2, WANG Huijuan1, FEI Jufeng2, LI Xiaoxiao1

(1. Room 6, Shanghai Electro-Mechanical Engineering Institute, Shanghai 201109, China;2. Shanghai Wireless Equipment Institute, Shanghai 200090, China)

The traditional hardware implementation of JPEG-LS lossless image compression algorithm suffers poor real-time performance. This paper presents a fully-pipelined structure based on FPGA to achieve the JPEG-LS algorithm. The structure reduces the delay of every step through Multi-stage pipeline to improve maximum throughput as well as the real-time of the compression algorithm, making hardware circuit operating frequencies up to 120 MHz.

fully-pipeline; lossless image compression; high-throughput; FPGA

2016- 01- 23

范文晶(1985-)，男，碩士，工程師。研究方向：數(shù)字信號處理及地面發(fā)射技術(shù)。王召利(1984-)，女，碩士，工程師。研究方向：數(shù)字信號處理技術(shù)。

10.16180/j.cnki.issn1007-7820.2016.11.036

TN919.83；TP

A