鄭天翼　黃世震　韋　明

摘 要：討論P(yáng)NG圖像解碼的硬件實(shí)現(xiàn)方法，針對(duì)PNG文件的圖像數(shù)據(jù)使用的LZ77和Huffman兩種無(wú)損壓縮算法，提出一種補(bǔ)充碼表的方法實(shí)現(xiàn)快速的硬件解碼，并采用較優(yōu)的軟硬件協(xié)調(diào)機(jī)制，在節(jié)省功耗的前提下實(shí)現(xiàn)PNG硬件解碼的加速設(shè)計(jì)。該設(shè)計(jì)經(jīng)Modelsim 6.3仿真測(cè)試和Matlab工具比較驗(yàn)證，證明可以完全無(wú)失真地恢復(fù)PNG圖像。

關(guān)鍵詞：LZ77；Huffman；軟硬件協(xié)調(diào)；PNG硬件解碼

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1004－373X(2009)04－182－03

Hardware Design for Accelerating PNG Decode

ZHENG Tianyi,HUANG Shizhen,WEI Ming

(Fujian Key Laboratory of Microelectronic & Integrated Circuit,College of Physics and Information Engineering,Fuzhou University,Fuzhou,350002,China)

Abstract：This paper discusses a hardware accelerated implementation for PNG image decoding within LZ77 and Huffman compression algorithm without any distortion,this design adopts complete patch－tree table to achieve fast hardware decode,cooperate hardware and software to accelerate hardware decode with less power consume under the test of Modelsim 6.3 and Matlab tools,the results show this design can recover PNG image without any distortion.

Keywords：LZ77;Huffman;cooperating of software and hardware;PNG hardware decode

0 引 言

PNG(Portable Network Graphic Format)是流式網(wǎng)絡(luò)圖形格式的簡(jiǎn)稱，是一種位圖文件(Bitmap File)存儲(chǔ)格式［1］。PNG文件采用壓縮率高的LZ77和Huffman兩種無(wú)損壓縮算法，支持網(wǎng)絡(luò)彩色圖像傳輸，支持Alpha通道、定義透明區(qū)域和多重透明，逐步細(xì)化地顯示圖片［2］。

PNG壓縮的核心算法是采用Zip壓縮算法［3］，該算法的特點(diǎn)就是先利用LZ77算法進(jìn)行短語(yǔ)式重復(fù)的壓縮得到未匹配的字節(jié)和匹配長(zhǎng)度、距離的組合值，然后再根據(jù)Huffman算法進(jìn)行單字節(jié)重復(fù)的壓縮最終得到壓縮碼流。PNG解碼的原理也就是壓縮的反過(guò)程，那么解碼時(shí)可根據(jù)碼表信息和壓縮碼流還原出原始圖像數(shù)據(jù)。

PNG文件的解碼通常由軟件完成，軟件解碼實(shí)現(xiàn)方式靈活，但相對(duì)硬件解碼而言，軟件解碼速度慢，能量消耗大，不利于移動(dòng)設(shè)備的低功耗設(shè)計(jì)優(yōu)化。為此，這里討論了PNG圖像的硬件解碼實(shí)現(xiàn)方法，其應(yīng)用對(duì)象是手機(jī)專用芯片，對(duì)低功耗和解碼速度都有較高的要求，并解決了PNG解碼的快速查表、軟硬件協(xié)調(diào)和硬件加速等實(shí)現(xiàn)方法，而硬件加速解碼功能的主要作用是減少CPU的負(fù)擔(dān)，極大加快PNG圖片顯示速度，并在一定程度上減少了功耗，延長(zhǎng)了手機(jī)的待機(jī)時(shí)間，具有很大研究與開(kāi)發(fā)的實(shí)際價(jià)值。

1 PNG圖像解碼原理的介紹

1.1 LZ77算法介紹

LZ77 算法可以稱為“滑動(dòng)窗口壓縮”［4］，該算法將一個(gè)虛擬的，可以跟隨壓縮進(jìn)程滑動(dòng)的窗口作為術(shù)語(yǔ)字典；要壓縮的字符串若在窗口中出現(xiàn)，則輸出匹配長(zhǎng)度和距離的組合信息，來(lái)替換前面出現(xiàn)的相同字符串,且要求最小匹配的字符串為3個(gè)字節(jié)，這樣可以保證壓縮后的數(shù)據(jù)量小于原始數(shù)據(jù)。

例如窗口的大小為15個(gè)字符，剛剛編碼過(guò)的15個(gè)字符為：byhelloeveryone，即將編碼的字符為:hellotoeveryonehi。可以發(fā)現(xiàn)有些字符串前面已經(jīng)出現(xiàn)過(guò)，則用()起來(lái)的字符串表示滑動(dòng)窗口中已出現(xiàn)過(guò)的匹配串：(hello)to(everyone)hi。

以上這些原始信息，可利用LZ77算法用匹配長(zhǎng)度和距離的組合信息來(lái)替換有匹配的字符串，若碰到未匹配的字節(jié)則直接輸出，壓縮后的內(nèi)容為：(5,13)to(8,15)hi。

在LZ77解壓縮時(shí)，只要維護(hù)好滑動(dòng)窗口，隨著壓縮信息的不斷輸入，可根據(jù)匹配的組合信息從窗口中找到相應(yīng)的匹配字符串作為輸出，即可還原出原始數(shù)據(jù)。

1.2 Huffman算法介紹

Huffman算法屬于編碼式壓縮，利用各個(gè)單字節(jié)所使用頻率不一樣的特點(diǎn)，使定長(zhǎng)編碼轉(zhuǎn)變?yōu)樽冮L(zhǎng)的編碼，給頻率高的字節(jié)更短的編碼，使用頻率低的字節(jié)更長(zhǎng)的編碼，起到無(wú)損壓縮的效果。這樣，經(jīng)過(guò) LZ77 壓縮后的未匹配的字節(jié)和匹配的組合信息可以進(jìn)一步地進(jìn)行Huffman壓縮，從而得到很高的壓縮效率。

例如，對(duì)于一組元素的字符值為S={a，b，c，d，e，f},其對(duì)應(yīng)的出現(xiàn)頻率為P={10，2，2，2，2，9} 。圖1是根據(jù)以上信息建立的Huffman樹(shù)。各元素出現(xiàn)頻率和元素值如圖1所示，編碼后的各個(gè)元素長(zhǎng)度分別為L(zhǎng)={1，3，3，3，3，2}，可見(jiàn)編碼后儲(chǔ)存這些字符值所需的空間極大地減少了。

這棵Huffman樹(shù)是根據(jù)PNG規(guī)范的Deflate原則建立的，具有以下特點(diǎn)：

(1) 左邊的葉子編碼為0，右邊的為1；

(2) 編碼必須滿足“前綴編碼”的要求，即較短的編碼不能是較長(zhǎng)編碼的前綴，這保證了碼的惟一性；

(3) 每一層葉子的節(jié)點(diǎn)頻率按從小到大排列，而同樣頻率的節(jié)點(diǎn)按字符值從小到大排列，這點(diǎn)也是PNG采用的Zip算法對(duì)Huffman算法的一種改進(jìn)。因此，解碼時(shí)首先要提取出壓縮流中的碼表信息建立出Huffman樹(shù)，其中每個(gè)葉結(jié)點(diǎn)應(yīng)包含有碼長(zhǎng)和字符值信息，并把最終生成的碼表保存在RAM中供給Huffman解碼模塊查表還原出圖像原始數(shù)據(jù)。

2 PNG解碼的軟硬件協(xié)調(diào)機(jī)制

整個(gè)PNG硬件解碼過(guò)程都是由軟件來(lái)調(diào)度的，在硬件解碼中若校驗(yàn)到圖片數(shù)據(jù)出錯(cuò)或解碼完成時(shí)，則PNG硬件模塊通過(guò)配置專門的寄存器給軟件檢查做中斷處理；當(dāng)軟件檢測(cè)到這個(gè)寄存器信號(hào)使能時(shí)就產(chǎn)生中斷，就能即使關(guān)閉PNG硬件解碼模塊，在數(shù)據(jù)有誤的情況下節(jié)省了硬件解碼的功耗。

解碼前后數(shù)據(jù)的搬運(yùn)機(jī)制是通過(guò)公用的AVI模塊(相當(dāng)于FIFO實(shí)現(xiàn)輸入輸出數(shù)據(jù)的緩存)實(shí)現(xiàn)了PNG數(shù)據(jù)的搬運(yùn)：解碼前，軟件通過(guò)調(diào)配AVI模塊從內(nèi)存中搬取壓縮數(shù)據(jù)給PNG硬件模塊做解碼；解碼后的數(shù)據(jù)經(jīng)過(guò)Resize模塊縮放后又可以利用AVI搬運(yùn)給VGA做顯示，這種較優(yōu)的軟件調(diào)配機(jī)制，解決了該設(shè)計(jì)的軟硬件協(xié)調(diào)問(wèn)題，可以在節(jié)省功耗的前提下實(shí)現(xiàn)高效率的解碼，具體的軟件硬件協(xié)調(diào)原理如圖2所示。

3 PNG解碼的總體硬件結(jié)構(gòu)

PNG硬件解碼加速的整體結(jié)構(gòu)主要由Bytesshift字符容器、PNG頭信息處理模塊、Inflate_table建Huffman表模塊、Inflate_fast快速解碼模塊、LZ77尋找匹配串模塊、Filter反濾波反交織模塊和Resize放大縮小模塊7大模塊組成。具體PNG解碼的硬件流程圖如圖3所示。

如圖3可見(jiàn)，PNG解碼的基本流程為：通過(guò)AVI模塊從總線上搬取壓縮數(shù)據(jù)到Bytesshift字符容器進(jìn)行緩存,并轉(zhuǎn)換為壓縮比特流；通過(guò)PNG頭信息處理模塊保留下文件的頭信息，通過(guò)控制Inflate_table模塊讀取碼長(zhǎng)信息來(lái)建立Huffman表，并對(duì)壓縮數(shù)據(jù)進(jìn)行解碼；解碼后的數(shù)據(jù)經(jīng)過(guò)Filter模塊進(jìn)行反濾波和反交織等處理，然后發(fā)給Resize模塊做放大縮小處理后，并通過(guò)AVI模塊將最終解碼后的數(shù)據(jù)傳輸出去。其中，解碼核心模塊和Filter模塊通過(guò)采用了數(shù)據(jù)的流水線處理方式，也極大地提高了PNG的解碼效率。

4 PNG核心解碼模塊的硬件結(jié)構(gòu)

由于編碼長(zhǎng)度可變和編碼長(zhǎng)度不統(tǒng)一，解碼時(shí)若按位比較來(lái)查找Huffman表會(huì)消耗很多時(shí)間，且PNG數(shù)據(jù)流中Huffman編碼的最長(zhǎng)碼長(zhǎng)為9。因此，為了實(shí)現(xiàn)快速查表解碼，本算法中將碼長(zhǎng)小于9的Huffman樹(shù)的葉結(jié)點(diǎn)作為父結(jié)點(diǎn)來(lái)擴(kuò)展到9層，即擴(kuò)展出來(lái)的葉結(jié)點(diǎn)信息都同父結(jié)點(diǎn)一樣，每次用固定的9比特壓縮數(shù)據(jù)作為地址去查表。這樣可以保證在每一個(gè)時(shí)鐘內(nèi)都可以查找到相應(yīng)的字符值，就可以極大地提高硬件解碼的效率。以前面的Huffman樹(shù)為例子(如圖4所示)，簡(jiǎn)單地將第4層以內(nèi)的葉結(jié)點(diǎn)補(bǔ)充到第4層，即把整個(gè)Huffman二叉樹(shù)補(bǔ)滿，則在第4層的子葉結(jié)點(diǎn)的長(zhǎng)度和字符信息都同父結(jié)點(diǎn)一樣。

這種擴(kuò)展Huffman樹(shù)的方法，可以實(shí)現(xiàn)迅速查找Huffman表，得到相應(yīng)的字符值和匹配的組合信息值，對(duì)解出匹配的組合信息值，則根據(jù)LZ77原則還原出解碼數(shù)據(jù)作為輸出。

該設(shè)計(jì)中的硬件解碼核心模塊可參考圖5。這種硬件結(jié)構(gòu)的優(yōu)點(diǎn)是利用擴(kuò)展碼表的方法實(shí)現(xiàn)快速解碼。核心解碼的基本流程為：每次用固定的9 b壓縮數(shù)據(jù)作為地址去查表，查出包含有碼長(zhǎng)和字符信息的葉結(jié)點(diǎn)，并根據(jù)碼長(zhǎng)信息從字符容器模塊移出使用過(guò)的壓縮數(shù)據(jù)，并等待新進(jìn)的壓縮數(shù)據(jù)與字符容器剩余的壓縮數(shù)據(jù)組成新的9 b數(shù)據(jù)作為查表地址。在下一個(gè)時(shí)鐘重復(fù)查表的過(guò)程，以此方式反復(fù)查表直至Huffman解碼結(jié)束。

5 仿真和綜合結(jié)果

經(jīng)Modelsim 6.3仿真提取出解碼后數(shù)據(jù)，在Matlab工具中進(jìn)行對(duì)原圖顯示與該設(shè)計(jì)解碼后提取出的圖像數(shù)據(jù)進(jìn)行對(duì)比，比較結(jié)果完全一致，并且在驗(yàn)證平臺(tái)上比較其對(duì)應(yīng)的原始圖像數(shù)據(jù)也完全吻合，因此，該硬件設(shè)計(jì)能夠完全不失真的恢復(fù)PNG圖像數(shù)據(jù)。

在設(shè)計(jì)中，使用臺(tái)積電90 nm的工藝庫(kù)，在100 MHz的頻率下對(duì)PNG解碼核心模塊用DC進(jìn)行綜合，結(jié)果如表1所示。(其中面積大小和功耗不包括RAM的面積和讀寫RAM的功耗)

6 結(jié) 語(yǔ)

這里討論了PNG解碼加速的硬件實(shí)現(xiàn)方法。其中分析了LZ77和Huffman兩種算法的硬件解碼原理，以及采用補(bǔ)滿Huffman樹(shù)的機(jī)制實(shí)現(xiàn)快速查表解碼，并運(yùn)用較優(yōu)的軟硬件協(xié)調(diào)機(jī)制，在節(jié)省功耗前的前提下實(shí)現(xiàn)PNG硬件解碼加速。

參 考 文 獻(xiàn)

［1］Brown C W,Shepherd B J.Graphic File Formats Reference and Guide.Manning Publications Co.,1995.

［2］Roelofs G.News and History of the Png Development Group.http://www.cdrom.com/pub/png/pngnews.html.

［3］李章晶,鄭國(guó)勤.針對(duì)無(wú)線通信領(lǐng)域的圖像壓縮的研究.計(jì)算機(jī)工程與設(shè)計(jì),2006,27(23):4 471－4 474.

［4］Scott N R.Computer Number Systems and Arithmetic.New Jersey:Prentice Hall,Englewood Cliffs,1985.

［5］陶鈞,王暉,張軍,等.三維小波視頻編碼的可伸縮性研究.小型微型計(jì)算機(jī)系統(tǒng),2005,26(2):285－288.

［6］Kakadiaris C.A Convex Penalty Method for Optical Human Motion Tracking.International Multimedia Conference.New York:ACM,2003:1－10.

［7］Zhang Z M.Independent Motion Detection Directly from Compressed Surveillance Video.International Multimedia Conference.New York:ACM,2003.

［8］Peleg A,Weiser U.MMX Technology Extension to the Intel Architecture.IEEE Micro.,1996,16(4):42－50.

［9］Deutch P,Gailly J －L,Adler M.GZip.http://www.gzip.org,2008.

作者簡(jiǎn)介

鄭天翼 男，1983年出生，福建福州人，碩士研究生。主要從事數(shù)字信號(hào)處理與集成電路設(shè)計(jì)的研究。

黃世震 男，1968年出生，福建福州人，副教授。福建省ICC副主任，主持省部級(jí)重點(diǎn)科研項(xiàng)目多項(xiàng)。主要從事集成電路設(shè)計(jì)的研究。

韋 明 男，1979年出生，陜西西安人。主要從事數(shù)字集成電路設(shè)計(jì)的研究。