郑天翼　黄世震　韦　明

摘 要：讨论PNG图像解码的硬件实现方法，针对PNG文件的图像数据使用的LZ77和Huffman两种无损压缩算法，提出一种补充码表的方法实现快速的硬件解码，并采用较优的软硬件协调机制，在节省功耗的前提下实现PNG硬件解码的加速设计。该设计经Modelsim 6.3仿真测试和Matlab工具比较验证，证明可以完全无失真地恢复PNG图像。

关键词：LZ77；Huffman；软硬件协调；PNG硬件解码

中图分类号：TP391 文献标识码：B 文章编号：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)是流式网络图形格式的简称，是一种位图文件(Bitmap File)存储格式［1］。PNG文件采用压缩率高的LZ77和Huffman两种无损压缩算法，支持网络彩色图像传输，支持Alpha通道、定义透明区域和多重透明，逐步细化地显示图片［2］。

PNG压缩的核心算法是采用Zip压缩算法［3］，该算法的特点就是先利用LZ77算法进行短语式重复的压缩得到未匹配的字节和匹配长度、距离的组合值，然后再根据Huffman算法进行单字节重复的压缩最终得到压缩码流。PNG解码的原理也就是压缩的反过程，那么解码时可根据码表信息和压缩码流还原出原始图像数据。

PNG文件的解码通常由软件完成，软件解码实现方式灵活，但相对硬件解码而言，软件解码速度慢，能量消耗大，不利于移动设备的低功耗设计优化。为此，这里讨论了PNG图像的硬件解码实现方法，其应用对象是手机专用芯片，对低功耗和解码速度都有较高的要求，并解决了PNG解码的快速查表、软硬件协调和硬件加速等实现方法，而硬件加速解码功能的主要作用是减少CPU的负担，极大加快PNG图片显示速度，并在一定程度上减少了功耗，延长了手机的待机时间，具有很大研究与开发的实际价值。

1 PNG图像解码原理的介绍

1.1 LZ77算法介绍

LZ77 算法可以称为“滑动窗口压缩”［4］，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为术语字典；要压缩的字符串若在窗口中出现，则输出匹配长度和距离的组合信息，来替换前面出现的相同字符串,且要求最小匹配的字符串为3个字节，这样可以保证压缩后的数据量小于原始数据。

例如窗口的大小为15个字符，刚刚编码过的15个字符为：byhelloeveryone，即将编码的字符为:hellotoeveryonehi。可以发现有些字符串前面已经出现过，则用()起来的字符串表示滑动窗口中已出现过的匹配串：(hello)to(everyone)hi。

以上这些原始信息，可利用LZ77算法用匹配长度和距离的组合信息来替换有匹配的字符串，若碰到未匹配的字节则直接输出，压缩后的内容为：(5,13)to(8,15)hi。

在LZ77解压缩时，只要维护好滑动窗口，随着压缩信息的不断输入，可根据匹配的组合信息从窗口中找到相应的匹配字符串作为输出，即可还原出原始数据。

1.2 Huffman算法介绍

Huffman算法属于编码式压缩，利用各个单字节所使用频率不一样的特点，使定长编码转变为变长的编码，给频率高的字节更短的编码，使用频率低的字节更长的编码，起到无损压缩的效果。这样，经过 LZ77 压缩后的未匹配的字节和匹配的组合信息可以进一步地进行Huffman压缩，从而得到很高的压缩效率。

例如，对于一组元素的字符值为S={a，b，c，d，e，f},其对应的出现频率为P={10，2，2，2，2，9} 。图1是根据以上信息建立的Huffman树。各元素出现频率和元素值如图1所示，编码后的各个元素长度分别为L={1，3，3，3，3，2}，可见编码后储存这些字符值所需的空间极大地减少了。

这棵Huffman树是根据PNG规范的Deflate原则建立的，具有以下特点：

(1) 左边的叶子编码为0，右边的为1；

(2) 编码必须满足“前缀编码”的要求，即较短的编码不能是较长编码的前缀，这保证了码的惟一性；

(3) 每一层叶子的节点频率按从小到大排列，而同样频率的节点按字符值从小到大排列，这点也是PNG采用的Zip算法对Huffman算法的一种改进。因此，解码时首先要提取出压缩流中的码表信息建立出Huffman树，其中每个叶结点应包含有码长和字符值信息，并把最终生成的码表保存在RAM中供给Huffman解码模块查表还原出图像原始数据。

2 PNG解码的软硬件协调机制

整个PNG硬件解码过程都是由软件来调度的，在硬件解码中若校验到图片数据出错或解码完成时，则PNG硬件模块通过配置专门的寄存器给软件检查做中断处理；当软件检测到这个寄存器信号使能时就产生中断，就能即使关闭PNG硬件解码模块，在数据有误的情况下节省了硬件解码的功耗。

解码前后数据的搬运机制是通过公用的AVI模块(相当于FIFO实现输入输出数据的缓存)实现了PNG数据的搬运：解码前，软件通过调配AVI模块从内存中搬取压缩数据给PNG硬件模块做解码；解码后的数据经过Resize模块缩放后又可以利用AVI搬运给VGA做显示，这种较优的软件调配机制，解决了该设计的软硬件协调问题，可以在节省功耗的前提下实现高效率的解码，具体的软件硬件协调原理如图2所示。

3 PNG解码的总体硬件结构

PNG硬件解码加速的整体结构主要由Bytesshift字符容器、PNG头信息处理模块、Inflate_table建Huffman表模块、Inflate_fast快速解码模块、LZ77寻找匹配串模块、Filter反滤波反交织模块和Resize放大缩小模块7大模块组成。具体PNG解码的硬件流程图如图3所示。

如图3可见，PNG解码的基本流程为：通过AVI模块从总线上搬取压缩数据到Bytesshift字符容器进行缓存,并转换为压缩比特流；通过PNG头信息处理模块保留下文件的头信息，通过控制Inflate_table模块读取码长信息来建立Huffman表，并对压缩数据进行解码；解码后的数据经过Filter模块进行反滤波和反交织等处理，然后发给Resize模块做放大缩小处理后，并通过AVI模块将最终解码后的数据传输出去。其中，解码核心模块和Filter模块通过采用了数据的流水线处理方式，也极大地提高了PNG的解码效率。

4 PNG核心解码模块的硬件结构

由于编码长度可变和编码长度不统一，解码时若按位比较来查找Huffman表会消耗很多时间，且PNG数据流中Huffman编码的最长码长为9。因此，为了实现快速查表解码，本算法中将码长小于9的Huffman树的叶结点作为父结点来扩展到9层，即扩展出来的叶结点信息都同父结点一样，每次用固定的9比特压缩数据作为地址去查表。这样可以保证在每一个时钟内都可以查找到相应的字符值，就可以极大地提高硬件解码的效率。以前面的Huffman树为例子(如图4所示)，简单地将第4层以内的叶结点补充到第4层，即把整个Huffman二叉树补满，则在第4层的子叶结点的长度和字符信息都同父结点一样。

这种扩展Huffman树的方法，可以实现迅速查找Huffman表，得到相应的字符值和匹配的组合信息值，对解出匹配的组合信息值，则根据LZ77原则还原出解码数据作为输出。

该设计中的硬件解码核心模块可参考图5。这种硬件结构的优点是利用扩展码表的方法实现快速解码。核心解码的基本流程为：每次用固定的9 b压缩数据作为地址去查表，查出包含有码长和字符信息的叶结点，并根据码长信息从字符容器模块移出使用过的压缩数据，并等待新进的压缩数据与字符容器剩余的压缩数据组成新的9 b数据作为查表地址。在下一个时钟重复查表的过程，以此方式反复查表直至Huffman解码结束。

5 仿真和综合结果

经Modelsim 6.3仿真提取出解码后数据，在Matlab工具中进行对原图显示与该设计解码后提取出的图像数据进行对比，比较结果完全一致，并且在验证平台上比较其对应的原始图像数据也完全吻合，因此，该硬件设计能够完全不失真的恢复PNG图像数据。

在设计中，使用台积电90 nm的工艺库，在100 MHz的频率下对PNG解码核心模块用DC进行综合，结果如表1所示。(其中面积大小和功耗不包括RAM的面积和读写RAM的功耗)

6 结 语

这里讨论了PNG解码加速的硬件实现方法。其中分析了LZ77和Huffman两种算法的硬件解码原理，以及采用补满Huffman树的机制实现快速查表解码，并运用较优的软硬件协调机制，在节省功耗前的前提下实现PNG硬件解码加速。

参 考 文 献

［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］李章晶,郑国勤.针对无线通信领域的图像压缩的研究.计算机工程与设计,2006,27(23):4 471－4 474.

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

［5］陶钧,王晖,张军,等.三维小波视频编码的可伸缩性研究.小型微型计算机系统,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.

作者简介

郑天翼 男，1983年出生，福建福州人，硕士研究生。主要从事数字信号处理与集成电路设计的研究。

黄世震 男，1968年出生，福建福州人，副教授。福建省ICC副主任，主持省部级重点科研项目多项。主要从事集成电路设计的研究。

韦 明 男，1979年出生，陕西西安人。主要从事数字集成电路设计的研究。