PNG图像格式的压缩算法

admin管理员组

文章数量:1533889

2024年3月30日发(作者：)

PNG图像格式的压缩算法

便携式网络图形（Portable Network Graphics）简称为PNG，它是一种无损压缩的位

图图形格式，其含有以下几种特性：

1、 支持256色调色板技术以产生小体积文件

2、 支持最高48位真彩色图像以及16位灰度图像

3、 支持阿尔法通道（Alpha Channel，表示图片的透明度和半透明度）的透明/半透明

性

4、 支持图像亮度的伽马校正（Gamma校准，用来针对影片或是影像系统里对于光线的

辉度 (luminance) 或是三色刺激值 (tristimulus values)所进行非线性的运算或

反运算）信息

5、 使用了无损压缩的算法

6、 使用了循环冗余校验（CRC，用来检测或校验数据传输或者保存后可能出现的错误）

防止文件出错

一、 PNG格式的文件结构

PNG定义了两种类型的数据块：一种是PNG文件必须包含、读写软件也都必须要支持的

关键块（critical chunk）；另一种叫做辅助块（ancillary chunks），PNG允许软件忽略它

不认识的附加块。这种基于数据块的设计，允许PNG格式在扩展时仍能保持与旧版本兼容。

关键数据块中有4个标准数据块：

1、文件头数据块IHDR(header chunk)：包含有图像基本信息，作为第一个数据块出现

并只出现一次。

2、调色板数据块PLTE(palette chunk)：必须放在图像数据块之前。

3、图像数据块IDAT(image data chunk)：存储实际图像数据。PNG数据允许包含多个

连续的图像数据块。

4、图像结束数据IEND(image trailer chunk)：放在文件尾部，表示PNG数据流结束

二、PNG格式文件的压缩算法

PNG格式文件采用的是从LZ77派生的一个称为DEFLATE的非专利无失真式压缩算法，

这个算法对图像里的直线进行预测然后存储颜色差值，这使得PNG经常能获得比原始图像更

大的压缩率。

PNG算法的压缩过程一般有以下几个步骤：

1、图像信息由数据过滤器（delta filtering）进行处理， delta filtering是一

个无损的数据过滤算法，它不会改变图像信息的大小，但是会让图像信息具有更高的可压缩

性。

2、被处理过的数据将会用Ziv-Lempel（LZ77）算法进行处理，处理后的数据被Huffman

算法压缩，得到最后的PNG格式的图像数据，过程可用下图表示。

（1） LZ77压缩算法原理

为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语：

1.输入数据流(input stream)：要被压缩的字符序列。

2.字符(character)：输入数据流中的基本单元。

3.编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲存

储器中的开始字符。

4.前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列

的存储器。

5.窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处

理的字符数。

6.指针(pointer)：指向窗口中的匹配串且含长度的指针。

LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体

执行步骤如下：

1.把编码位置设置到输入数据流的开始位置。

2.查找窗口中最长的匹配串。

3.以“(Pointer, Length) Characters”的格式输出，其中Pointer是指向窗口中匹配

串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配

的第1个字符。

4.如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后

返回到步骤2

（2） 使用LZ77算法进行压缩

如果当前处理开始字节的串在窗口中有匹配串，就先输出一个标志位，表明下面是一个

（之间的距离，匹配长度）对，然后输出（之间的距离，匹配长度）对，再从刚才处理完的

串之后的下一个字节继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就先输出

一个标志位，表明下面是一个没有改动的字节，然后不做改动的输出当前处理字节，再继续

处理下一个字节。

伪代码如下：

压缩一段字节流，src - 源数据区，srclen - 源数据区字节长度，dest - 压缩数据区，

返回值 > 0 压缩数据长度，返回值 = 0 数据无法压缩，返回值 < 0 压缩中异常错误

int CCompressLZ77::Compress(BYTE* src, int srclen, BYTE* dest)

{

CurByte <- 0

CurBit <- 0

pWnd <- src;

_InitSortTable()

初始化索引表，释放上次压缩用的空间

for i <- 0 to srclen

do if CurByte >= srclen

return 0;

do if _SeekPhase(src, srclen, i, &off, &len)

_SeekPhase(BYTE* src, int srclen, int nSeekStart, int* offset, int* len)

在滑动窗口中查找术语, nSeekStart - 从何处开始匹配, offset, len - 用

于接收结果，表示在滑动窗口内的偏移和长度, 返回值- 是否查到长度为2

或2以上的匹配字节串

_OutCode(dest, 1, 1, FALSE)

_OutCode(dest, len, 0, TRUE)

在窗口不满64k大小时，不需要16位存储偏移

_OutCode(dest, off, UpperLog2(nWndSize), FALSE)

_ScrollWindow(len)

将窗口向右滑动n个字节

i <- i+len-1;

else

_OutCode(dest, 0, 1, FALSE);

_OutCode(dest, (DWORD)(src[i]), 8, FALSE);

_ScrollWindow(1);

destlen <- CurByte + ((CurBit) ? 1 : 0);

if destlen >= srclen

return 0;

return destlen;

}

(3) LZ77算法解压算法

对于LZ77压缩文本的解压很简单。解压算法必须保存解压输出的最后N个字符。当碰到

编码字符串时，解压算法使用<指针>，和<长度>，字段将编码替换成实际的正文字符串。

三、 LZ77算法优劣以及应用

（1）LZ77算法优劣

Ziv-Lempel（LZ77） 算法假设需要压缩的数据中连续的序列重复的出现，如果正在处

理的序列与历史滑动窗口中的一条或者朵小序列相匹配，则将该序列处理为一个LZ77 对，

LZ77 对包含(距离，长度) 这两个数据，指向最近的一个匹配的序列。如果在一定范围(例

如长度在3~258 之间)内无法找到相应的匹配对，则LZ77 算法会采取一种“贪婪”策略来

处理该序列。这种“贪婪”策略在压缩文本或者很多二进制文件时效果很好，然而它在处理

过滤后的数据时效果不太理想。过滤后数据主要由很小的随机分布的数据组成，在这种情况

下，即使使用“贪婪”策略也不一定能得到很好的效果。

（2）LZ77算法应用

如今除了PNG图像格式压缩使用了LZ77算法，还有GZIP(GNU自由软件的文件压缩程)

以及ZLIB（提供数据压缩用的函式库）均采用了LZ77算法进行压缩。

本文标签： 数据算法图像压缩匹配