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

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

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

?

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

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

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

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

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

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

1 無損壓縮算法

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

圖1 JPEG-LS編碼器模型

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

圖2 JPEG-LS 壓縮算法框圖

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

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

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

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

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

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

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

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

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

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

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

然而在JPEG-LS標準中并沒有規(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標準，以這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)化降低了算法復雜度，提高了效率。在計算得到預測值,根據(jù)預測值通過量化后得到誤差值以及量化誤差值的過程如下

if(Errval)>0

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

else

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

(2)

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

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

圖3 變量更新結構圖

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

2.2 算法流水線結構

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

圖4 JPEG-LS流水線硬件結構圖

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

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

階段2 局部梯度值量化；

階段3 查詢變量Q地址；

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

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

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

階段9 以及預測誤差值計算；

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

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

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

3 實驗及結果

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

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

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

4 結束語

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

[1] 沈洪亮,劉金國.基于JPEG-LS的遙感圖像無損壓縮技術[J].光電子技術,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].彈箭與制導學報,2006,26(SA):1219-1222.

[4] 劉嘉晗,趙巖,王宇心,等.高性能全流水線可控參數(shù)JPEG-LS 編碼器實現(xiàn)[J].微電子學與計算機,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設計[J].清華大學學報:自然科學版,2007,47(10):1654-1658.

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

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

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

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

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

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

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

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

[16] 王黎明,趙英亮,韓焱,等.基于JPEG-LS框架的無損壓縮技術研究[J].電腦開發(fā)與應用,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ā)射技術。王召利(1984-)，女，碩士，工程師。研究方向：數(shù)字信號處理技術。

10.16180/j.cnki.issn1007-7820.2016.11.036

TN919.83；TP

A