PNG图像的压缩算法
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 数据无法压缩,返回值
int CCompressLZ77::Compress(BYTE* src, intsrclen, BYTE* dest)
{
CurByte
CurBit
pWnd
_InitSortTable()
初始化索引表,释放上次压缩用的空间
fori
do if CurByte>= srclen
return 0;
do if _SeekPhase(src, srclen, i, &off, &len)
_SeekPhase(BYTE* src, intsrclen, intnSeekStart, 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
else
_OutCode(dest, 0, 1, FALSE);
_OutCode(dest, (DWORD)(src[i]), 8, FALSE);
_ScrollWindow(1);
destlen
ifdestlen>= srclen
return 0;
returndestlen;
}
(3) LZ77算法解压算法
对于LZ77压缩文本的解压很简单。解压算法必须保存解压输出的最后N 个字符。当碰到编码字符串时,解压算法使用,和,字段将编码替换成实际的正文字符串。
三、 LZ77算法优劣以及应用
(1)LZ77算法优劣
Ziv-Lempel (LZ77) 算法假设需要压缩的数据中连续的序列重复的出现,如果正在处理的序列与历史滑动窗口中的一条或者朵小序列相匹配,则将该序列处理为一个LZ77 对,LZ77 对包含(距离,长度) 这两个数据,指向最近的一个匹配的序列。如果在一定范围(例如长度在3~258 之间) 内无法找到相应的匹配对,则LZ77 算法会采取一种“贪婪”策略来处理该序列。这种“贪婪”策略在压缩文本或者很多二进制文件时效果很好,然而它在处理
过滤后的数据时效果不太理想。过滤后数据主要由很小的随机分布的数据组成,在这种情况下,即使使用“贪婪”策略也不一定能得到很好的效果。
(2)LZ77算法应用
如今除了PNG 图像格式压缩使用了LZ77算法,还有GZIP(GNU自由软件的文件压缩程) 以及ZLIB (提供数据压缩用的函式库)均采用了LZ77算法进行压缩。