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