GIF 格式及LZW算法浅析
前段时间得知一个产品需求,需要在Flash Player中显示gif动画图片。虽然Flash支持gif图像的载入,但无法播放动画。
花了不少时间去了解GIF格式,虽然顺利解决了问题,但是知其然也知其所以然,了解了这些知识,对理解编码/解码的过程和解决问题有非常大的帮助。
GIF概述
Graphics Interchange Format(GIF,图形交换格式)是一种位图的图形文件格式,以8位色(即256种颜色)重现真彩色的图像。它实际上是一种压缩文档,采用LZW压缩算法进行编码,有效地减少了图像文件在网络上传输的时间。是目前广泛应用于网络传输的图像格式之一。
GIF主要分为两个版本,即GIF 87a和GIF 89a:
GIF 87a:是在1987年制定的版本; GIF 89a:是在1989年制定的版本。在这个版本中,为GIF文档扩充了图形控制区块、备注、说明、应用程序接口等四个区块,并提供了对透明色和多帧动画的支持。
GIF格式结构
GIF文件由文件头,描述块,彩色表,数据块,扩展块和结束符构成,GIF87a和GIF89a的区别在于:后者较前者增加了扩展块,从功能上看即提供了对透明色和多帧动画的支持。
结构组成
结构如下表所示:
Header | Header | Header |
Logical Screen Descriptor | Screen Descriptor Block | GIF Data Stream |
Global Color Table | Global Color Table(optional) | |
Application Extension | Extension Blocks(optional, repeated) | |
Graphic Control Extension* | ||
… | ||
Image Descriptor | Image Blocks(repeated) | |
Local Color Table | ||
Table Based Image Data | ||
… | Extension Blocks(optional, repeated) | |
Trailer | Trailer | Trailer |
常见版本结构如下:
GIF87a:
Header | Header |
Logical Screen Descriptor | Screen Descriptor Block |
Global Color Table | Global Color Table(optional) |
Image Descriptor | Image Blocks |
Local Color Table | |
Table Based Image Data | |
Trailer | Trailer |
GIF89a :
Header | Header |
Header | Header |
Logical Screen Descriptor | Screen Descriptor Block |
Global Color Table | Global Color Table(optional) |
Application Extension | Extension Blocks(optional, repeated) |
Graphic Control Extension* | |
… | |
Image Descriptor | Image Blocks(repeated) |
Local Color Table | |
Table Based Image Data | |
… | Extension Blocks(optional, repeated) |
Trailer | Trailer |
Logical Screen Descriptor | Screen Descriptor Block |
Global Color Table | Global Color Table(optional) |
Image Descriptor | Image Blocks |
Local Color Table | |
Table Based Image Data | |
Trailer | Trailer |
*: 如果为多帧图像,则必须要Graphic Control Extension.
结构说明
Header:描述GIF Signature和 Version; Logical Screen Descriptor:包含定义图像显示区域的参数,包括背景颜色信息; Global Color Table:GIF图像是基于颜色表的,存储的数据是该点的颜色对应于颜色表的索引值。全局颜色表作用域为整个数据流,可以用于那些没有局部颜色表的图像。 Image Descriptor:定义图像的属性,包括图像相对于逻辑屏幕边界的偏移量、图像大小以及有无局部颜色列表和颜色列表大小; Local Color Table:和Global的一样,都是可选的颜色表; Table Based Image Data:GIF使用LZW压缩算法,包含LZW编码长度(LZW Minimum Code Size)和图像数据(Image Data)两部分。 Graphic Control Extension:控制跟在它后面的第一个图像(或文本)的渲染方式; Comment Extension:用来说明图形、作者或者其他任何非图形数据和控制信息的文本信息; Plain Text Extension:包含文本数据和描绘文本所需的参数 Application Extension:包含制作该图像文件的应用程序的相关信息; Trailer:表示GIF文件的结尾,它包含一个固定的数值:0x3B。 各部分的数据结构及编码细则可参考 GIF89a Specification,不再赘述。
LZW压缩算法
GIF采用的LZW(Lempel-Ziv-Welch)压缩算法,这是一种基于字典的无损数据压缩算法。1978年Abraham Lempel与Jacob Ziv在发布了LZ78 压缩算法, Terry Welchy 以此作为基础,1984年发布其改进版本—— LZW。
算法说明
LZW压缩算法的基本思想是建立一个编码表(字典),将输入字符串映射成定长的码字输出,通常码长设为12bit。把数字图像当作一个一维的比特串,算法在产生输出串的同时动态地更新编码表,这样码表与串表对应产生压缩图像的特殊性质。串表是动态产生的,编码前先初始化,使其包含所有的单字符串。压缩过程中,串表中不断产生新字符串(串表中没有的字符串),存储新字符串时也保存与新串的前缀相应的子码。
简单地讲,编码过程如下:
- 初始化字典,包含字符串中所有的单个字符;
- 在当前读到的位置,从字典里找到能够匹配的最长字符串ω;
- 返回ω在字典中的索引值,替代ω;
- 把ω+其后一个字符组成一个新的字符串,添加到字典中;
- 回到第2步 。
算法示例
下面借助Wikipedia的示例有助于理解,实际编码规则并非如此:
有这么一段字符串
TOBEORNOTTOBEORTOBEORNOT#
#假定为LZW的结束符,因此字符编码表中需要包含A-Z 和 # 27个项;当字典扩展时,需要增加码字(Code Word)位宽以满足不断增加的新表项 (前缀,Prefix)。25=32,5bit就够存储初始编码表所有数据流。如果码字位宽,每次加1位。初始编码表如下:
Symbol | Binary | Decimal |
# | 00000 | 0 |
A | 00001 | 1 |
B | 00010 | 2 |
C | 00011 | 3 |
D | 00100 | 4 |
E | 00101 | 5 |
F | 00110 | 6 |
G | 00111 | 7 |
H | 01000 | 8 |
I | 01001 | 9 |
J | 01010 | 10 |
K | 01011 | 11 |
L | 01100 | 12 |
M | 01101 | 13 |
N | 01110 | 14 |
O | 01111 | 15 |
P | 10000 | 16 |
Q | 10001 | 17 |
R | 10010 | 18 |
S | 10011 | 19 |
T | 10100 | 20 |
U | 10101 | 21 |
V | 10110 | 22 |
W | 10111 | 23 |
X | 11000 | 24 |
Y | 11001 | 25 |
Z | 11010 | 26 |
编码
Current Sequence | Next Char | Output | Extended Dictionary | Comments | ||
Code | Bits | |||||
NULL | T | |||||
T | O | 20 | 10100 | 27: | TO | 27 = first available code after 0 through 26 |
O | B | 15 | 01111 | 28: | OB | |
B | E | 2 | 00010 | 29: | BE | |
E | O | 5 | 00101 | 30: | EO | |
O | R | 15 | 01111 | 31: | OR | |
R | N | 18 | 10010 | 32: | RN | 32 requires 6 bits, so for next output use 6 bits |
N | O | 14 | 001110 | 33: | NO | |
O | T | 15 | 001111 | 34: | OT | |
T | T | 20 | 010100 | 35: | TT | |
TO | B | 27 | 011011 | 36: | TOB | |
BE | O | 29 | 011101 | 37: | BEO | |
OR | T | 31 | 011111 | 38: | ORT | |
TOB | E | 36 | 100100 | 39: | TOBE | |
EO | R | 30 | 011110 | 40: | EOR | |
RN | O | 32 | 100000 | 41: | RNO | |
OT | # | 34 | 100010 | # stops the algorithm; send the cur seq | ||
0 | 000000 | and the stop code |
编码前长度 : 25 symbols × 5 bits/symbol = 125 bits
编码后长度:(6 codes × 5 bits/code) + (11 codes × 6 bits/code) = 96 bits
使用LZW节省了29 bits, 差不多减少了 22%的数据量,效果明显。
解码
Input | Output Sequence | New Dictionary Entry | Comments | ||||
Bits | Code | Full | Conjecture | ||||
10100 | 20 | T | 27: | T? | |||
01111 | 15 | O | 27: | TO | 28: | O? | |
00010 | 2 | B | 28: | OB | 29: | B? | |
00101 | 5 | E | 29: | BE | 30: | E? | |
01111 | 15 | O | 30: | EO | 31: | O? | |
10010 | 18 | R | 31: | OR | 32: | R? | created code 31 (last to fit in 5 bits) |
001110 | 14 | N | 32: | RN | 33: | N? | so start reading input at 6 bits |
001111 | 15 | O | 33: | NO | 34: | O? | |
010100 | 20 | T | 34: | OT | 35: | T? | |
011011 | 27 | TO | 35: | TT | 36: | TO? | |
011101 | 29 | BE | 36: | TOB | 37: | BE? | 36 = TO + 1st symbol (B) of |
011111 | 31 | OR | 37: | BEO | 38: | OR? | next coded sequence received (BE) |
100100 | 36 | TOB | 38: | ORT | 39: | TOB? | |
011110 | 30 | EO | 39: | TOBE | 40: | EO? | |
100000 | 32 | RN | 40: | EOR | 41: | RN? | |
100010 | 34 | OT | 41: | RNO | 42: | OT? | |
000000 | 0 | # |
总结
简单介绍了GIF文件格式的特点及其内部的结构,并浅析了LZW压缩算法的原理,通过简单的例子演示了LZW编码/解码的过程。相比GIF 87a,GIF 89a增加了很实用的两项功能:透明色支持和多帧动画,也正是因此GIF才会在Internet上如此受欢迎。虽然遭遇了专利风波,但也因此催生了PNG格式,如今LZW的专利都过期了,GIF依然流行。 😉
阅读延伸
GIF89a Specification(W3C) LZMA(Wikipedia)
参考资料
- Graphics Interchange Format(Wikipedia)
- GIF89a Specification
- The Structure of a GIF89a file
- GIF format
- http://www.cnblogs.com/KevinXer1129/archive/2008/10/09/1307251.html
- http://www.chinaai.org/ip/image-processing/gif-struct.html
- LZW(Wikipedia)
- http://www.chinaai.org/ip/image-processing/lzw-gif.html
- Terry Welch, “A Technique for High-Performance Data Compression”, IEEE Computer, June 1984, p. 8–19