gif格式图片的解析

GIF(Graphics Interchange Format，图形交换格式)文件是由 CompuServe公司开发的图形文件格式，版权所有，任何商业目的使用均须 CompuServe公司授权。

GIF文件内部是按块划分的，包括控制块（ Control Block ）和数据块（Data Sub-blocks）两种。控制块是控制数据块行为的，根据不同的控制块包含一些不同的控制参数；数据块只包含一些8-bit的字符流，由它前面的控制块来决定它的功能，每个数据块大小从0到255个字节，数据块的第一个字节指出这个数据块大小（字节数），计算数据块的大小时不包括这个字节，所以一个空的数据块有一个字节，那就是数据块的大小0x00。

一个GIF文件的结构可分为文件头(File Header)、GIF数据流(GIF Data Stream)和文件终结器(Trailer)三个部分。文件头包含GIF文件署名(Signature)和版本号(Version)；GIF数据流由控制标识符、图象块(Image Block)和其他的一些扩展块组成；文件终结器只有一个值为0x3B的字符（';'）表示文件结束。下表显示了一个GIF文件的组成结构：

GIF署名用来确认一个文件是否是GIF格式的文件，这一部分由三个字符组成："GIF";文件版本号也是由三个字节组成,可以为"87a"或"89a".具体描述见下表:

逻辑屏幕标识符(Logical Screen Descriptor)

背景颜色索引  -  为 背景 颜 色指向全局色表。背景 颜 色是指那些没有被 图 像覆盖的 视 屏部分的 颜 色。若全局色表 标 志位置 为 0 ， 则该 字段也被赋值 0 ，并且被忽略。

象素高宽比  -  用于 计 算原 图 像中像素的近似高 宽 比。如果 该 字段的 值为 非 0 ， 则 象素的高 宽 比由下面的公式 计 算 ：

高 宽 比  = ( 象素高 宽 比  + 15) / 64

该 字段的取 值 范 围 从最 宽 的比 值 4 ： 1 到最高的比 值 1 ： 4 ， 递 增的 步 幅 为 1/64 。 取 值 ：  0 -  没有比 值 ， 1 ～ 255 -  用于 计 算的 值 。

全局色表标志  -  指示有没有全局色表，如果 该标 志位置 1 ， 则 全局色表会 紧接在该块之后出现 。 该 位也用于解 释 是否 选 用背景 颜 色索引字段。若 该 位置 1 ， 则 背景 颜 色索引字段的 值 将指向背景 颜 色表。

色彩方案  -  提供 给 原始 图 像的 每 个 颜 色的位数减 1 。 这 个 值 代表 图 像中所使用的整个 调 色板的大小，而不是 图 像中所使用的 颜 色的数量。例如，若 该 字段的 值为 3 ， 则图 像中所使用的 调 色板的 每 个色 值 占 4 位。

短标志  -  表明全局色表是否被排序。如果 该 位置 1 ， 则 全局色表按照重要性 递 减的原 则进 行了排序。典型地，是按照 颜 色的使用 频 度 进 行 递 减排序，使用 频 度最高的 颜 色排在色表的最前面。 这样 便可帮助解 码 器 选择 最好的 颜 色子集来成象。

全局色表的尺寸  -  如果全局色表 标 志位置 1 ， 则该 字段的 值记录 全局色表中所占用的字 节 数。

全局颜色列表(Global Color Table)必须紧跟在逻辑屏幕标识符后面，每个颜色列表索引条目由三个字节组成，按R、G、B的顺序排列。

图象标识符(Image Descriptor)包含处理一个基于图像的表的必要参数，它是一幅图所必需的，图象标识符以0x2C(',')字符开始。一幅图像对应一个图象标识符，图象标识符后面跟着对应的图像数据。

局部颜色列表(Local Color Table)

如果上面的局部颜色列表标志置位的话，则需要在这里（紧跟在图象标识符之后）定义一个局部颜色列表以供紧接着它的图象使用，注意使用前应线保存原来的颜色列表，使用结束之后回复原来保存的全局颜色列表。如果一个GIF文件即没有提供全局颜色列表，也没有提供局部颜色列表，可以自己创建一个颜色列表，或使用系统的颜色列表。局部颜色列表的排列方式和全局颜色列表一样：RGBRGB......

图形控制扩展(Graphic Control Extension)

这一部分是可选的（需要89a版本），可以放在一个图象块(图象标识符)或文本扩展块的前面，用来控制跟在它后面的第一个图象（或文本）的渲染(Render)形式，组成结构如下：

扩充引入  -  用于 识别 一个 扩 充 块 的 开 始， 该 字段 为 固定 值 0x21 。

图像控制标号  -  识别 当前 块 是否 为图 形控制 扩 充。 该 字段 为 固定 值  0xF9 。

块尺寸  -  块 中所包含的字 节 数。从 块 尺寸字段 开 始到快 结 束符（不含 结 束符）。 该 字段包含固定 值 4 。

配置方法  -  指示 图 像 显 示后的 处 理方法。 值 :

0 -  无指定的配置，解 码 器不需要做任何 处 理。

1 -  不做配 值 。 图 像将被留在原位置。

2 -  恢 复 背景 颜 色。 图 像所占的区域必 须备 恢 复为 背景 颜 色。

3 -  恢 复 以前的 颜 色。解 码 器需要将 图 像区域恢 复为 原来成象的 颜 色。

4-7 -  未定 义 。

用户输入标志  -  说 明在 继续处 理之前是否需要用 户输 入。可以和 输 入延 时 一起使用。

透明标志  -  表明在透明索引字段是否 给 定透明索引。

延时  -  如果不 为 0,  该 字段指定以 1/100 秒 为单 位的 时 延数。

透明索引  -  如果遇到透明索引， 则显 示 设备 的相 关 象素不被改 变 ， 继续处 理下一个象素。

块终止符  -  这 个 0 长 度字段 标 志着 图 像控制 扩 充得 结 束。

基于颜色列表的图象数据(Table-Based Image Data)，由两部分组成：LZW编码长度(LZW Minimum Code Size)和图象数据(Image Data)。

GIF图象数据使用了LZW压缩算法（详细介绍请看后面的『LZW算法和GIF数据压缩』），大大减小了图象数据的大小。图象数据在压缩前有两种排列格式：（由图象标识符的交织标志控制)。连续方式按从左到右、从上到下的顺序排列图象的光栅数据；交织图象按下面的方法处理光栅数据：

创建四个通道(pass)保存数据，每个通道提取不同行的数据：
第一通道(Pass 1)提取从第0行开始每隔8行的数据；
第二通道(Pass 2)提取从第4行开始每隔8行的数据；
第三通道(Pass 3)提取从第2行开始每隔4行的数据；
第四通道(Pass 4)提取从第1行开始每隔2行的数据；

LZW for GIF 算法原理

LZW是一个字典式压缩算法，他在压缩原始数据时，对每一个新出现的原始数据串赋一个数值作为标号，那么下次又出现了这个串后，就可以用这个值来代替了。比如：

原始数据：  ABCCAABCDDAACCDB      ，

ABCD可以用0～3的数来表示。那么注意这个字符串中出现了好几个重复的字串：

AB CCA ABCDDAACCDB

那么就可以用 4来代表 AB，5来代表 CC 等等，原来的字符串就变为

压缩后的数据： 45 A 4 CDDAA5DB ,

变短了一点点。实际上上面这个字符串号可以进一步的压缩，等会再谈。

为了区别代表串的值和原来的单个的数 据值，需要使它们的数值域不重合，比如说原来的数我们是以8位为单位来处理的（就算实际上不是8位的，我们也可以看作是8位的，反正是一个0101的数据 流），那么就认为原始的数的范围是0～255，压缩程序生成的标号的范围就不能为0～255，可以从256开始，但是这样一来就超过了8位的表示范围了， 所以 LZW 算法必须要扩展数据的位数，至少要扩一位，这样看起来不是反而是增加了数据流的体积了吗？不过如果能用一个数据代表一个原始数据串，那么还是划得来的。从这个原理也可以看出LZW算法的适用范围， 那就是原始数据串最好是有大量的子串多次重复出现，重复的越多，压缩效果越好。反之则越差，可能真的不减反增了。

LZW算法在处理数据时，随着新的串的不断发现，标号的值也就不断增加，增加到一定的程度，出与查找效率和标号集（也就是字典）所需存储空间的考虑，就不能再让它增加了，那么怎么办呢？干脆就从头开始，在这里做一个标记（ 清除标志 CLEAR），表示从这里我 重新开始构造字典字典了，以前的所有标记作废，开始使用新的标记。这个标号集的大小多少比较合适呢？据说理论上是越大压缩率越高（我个人感觉太大了也不见得就好），不过处理的开销也呈指数增长， 一般都是根据处理速度和内存空间选定一个大小，GIF规范规定的是12位，超过12位的表达范围就推倒重来，并且GIF为了提高压缩率，采用的是变长的字 长。比如说原始数据是8位，那么一开始，先加上一位再说，开始的字长就成了9位，然后开始加标号，当标号加到512时，也就是超过9为所能表达的最大数据 时，也就意味着后面的标号要用10位字长才能表示了，那么从这里开始，后面的字长就是10位了。依此类推，到了2^12也就是4096时，在这里插一个清 除标志，从后面开始，从9位再来。

GIF规定的清除标志 CLEAR 的数值是原始数据字长表示的最大值加 1，如果原始数据字长是8清除标志就是256，如果原始数据字长为4那么就是16。另外GIF还规定了一个 结束标志 END ，它的值是清除标志 CLEAR 再加 1。由于GIF规定的位数有1位（单色图），4位（16色）和8位（256色），而1位的情况下如果只扩展1位，只能表示4种状态，那么加上一个清除标志和结束标志就用完了，所以1位的情况下就必须扩充到3位。其它两种情况初始的字长就为5位和9位。

好了，现在开始谈谈LZW的具体算法。前面已经说了，LZW是基于字典的压缩方法，那么这个字典是怎么来的呢？难道先编一本“大百科字典”，随压缩包免费奉送？这显然是不可能的。LZW算法的优点就是可以 动态生成字典，并且这个字典的信息已经包含在压缩后的数据流中了，不必再另外储存字典信息了。下面以一个压缩过程为例来说明一下。这个例子是Bob Montgomery给出的，非常的经典，我这里充当一个翻译的工作，并稍微加一点我的解释。

比如有一个字符串，是由A、B、C、D四个字符构成的，那么就可以用0 1 2 3 来表示，两位就够了。

A B A B A B A B B B A B A B A A C D A C D A D C A B A A A B A B .....

首先要扩充一位，变成3位，定义 Clear＝4，End＝5。那么以后的标号就从6开始。

第一步，取第一个字符，是A，A已经在我们的定义中了，也就是说，我们已经（认识）他了，就不做处理了。

下一步，取第二个字符，现在的取到的字符串为 （ A ， B ），注意，这里引入一个 前缀（ prefix ）和 后缀（ suffix ）的概念，一个字符串可以用一个前缀加一个后缀来表示即 （前缀，后缀）前缀是一个标号，可以是原始的字符，也可以是一个代表字符串的标号，后缀则是一个字符。那么这里取到了（ A ， A ），以前没见过，不认识，好，现在 用 6 代表（ A ， B ）， 下次就认识了。因为有不认识的了，所以把前缀  A  放入到输出流中，只保留后缀  B  ，让它变成前缀。

第三步，取下一个字符，是  A ，现在的字符串是（ B ， A ），还是不认得，用一个新标号来表示他， 7 ＝（ B ， A ）。把前缀  B  放入到输出流， A  变成前缀。

第四步，取下一个字符，是  B  ，那么取道的是（ A ， B ），哈，这次认得了，不就是老 6 么。好，把字符串规约到  6 ，以 6 来作为前缀。

第五步，取下一个，是 A  ，即为（ 6 ， A ），又不认得了，就令 8 ＝（ 6 ， A ），把前缀  6 放到 输出流。现在的前缀变成  A 了。 注意 ，到这里标号已经超过 3 位能够表示的最大范围了，所以接下来必须要 扩展数据位 ，那么接下来的数据就是以 4 位字长来表示了。接下来的过程以此类推。

编码器伪代码
Initialize String Table;
[.c.] = Empty;
[.c.]k = First Character in CharStream;
while ([.c.]k != EOF )
{
　　if ( [.c.]k is in the StringTable)
　　{
　　　　[.c.] = [.c.]k;
　　}
　　else
　　{
　　　　add [.c.]k to the StringTable;
　　　　Output the Index of [.c.] in the StringTable to the CodeStream;
　　　　[.c.] = k;
　　}
　　[.c.]k = Next Character in CharStream;
}
Output the Index of [.c.] in the StringTable to the CodeStream;

LZW的解压

LZW 的解压过程就是一个查字典的过程。那么这个字典是从哪里来的呢？这就是 LZW 的最大优点之一，那的字典信息是完全包含在压缩后的数据中的，解压程序可以动态的从压缩过的数据中构造出来，因此解压过程也非常类似于压缩过程。

以上面的例子压缩结果为例，它的输出就是我们的输入，为：

待解压的数据流为: A B 6 8 B 10 9 A A C D 14 16 D C 8 ....

解压的过程是以一对一对数据来处理的。首先我们要知道原始数据的位数，这一点是要在处理压缩数据以前就知道的。在 GIF 文件中，可以从。我们来一步步分析这个过程：

第一步，取第一个和第二个数据，是（ A ， B ），不认得，令 6 ＝（ A ， B ），把前缀 A 放入输出流中，后缀 B 变成前缀；

第二步，取第三个数据，现在变为（ B ， 6 ）。不认得， 那么令 7 ＝（ B ， 6 ）吗？ …… NO ！ 请先回过头去看压缩过程，我们定义一个新的标志，前缀可以是一个代表子串的标号，但是后缀都是一个单个的数据的，所以这里我们也不能让后缀是一个字串标号。那么后缀是什么呢？让我们把 6 展开， 6 是 A B ，那么这里原来的字串就是 B A B ……，现在知道了把，其实 7 ＝（ B ， A ）， 那么7的后缀就是6 代表的字符串的第一个字符 。现在我们把 B 放入输出流。

第三步，取第四个数据。第四个数据是……………？？？？怎么，不就是 8 吗。那是，明摆着写着呢。如果我不这样写，写成 0001100001011001 …………你还认得是 8 吗？由于 GIF 是变位长的，所以我们一定要清楚在这里到地取几位。先回过头来看上一步，由于上一步我们已经把标号排到 7 了， 7 是 3 位的最大数值，所以从这一步以后，就应该把 字长加一位 ，所以这里我们要取 4 位，就是 1000 ，也就是 8 了。好了，现在得到的是（ 6 ， 8 ）。不认得，那么令 8 ＝（ 6 ，……………………………………… 8 ？？）。 8 我们还不知道呢，怎么能用它来定义自己呢？回顾一下上一步我们定义 7 的时候，取的后缀是 6 的第一个字符，那么这里我 8 的后缀也应该是 8 的第一个字符，我们知道 8 的前缀是 6 ，那么 8 的第一个字符也就是 6 的第一个字符。也就是  A 。所以 8 ＝（ 6 ， A ），现在把 6 代表的字符串 AB 放入输出流，让前缀变为 8 ；

第四步，取第五个数，现在是（ 8 ， B ），让 9 ＝（ 8 ， B ），把 8 ＝ 6A ＝ AB A 放入输出流，前缀为 B 。

第五步，取第六个，（ B ， 10 ），同第三步，令 10 ＝（ B ， 10 的第一个字符）＝（ B ， B ），把 B 放入输出流

解码器伪代码 Initialize String Table;
[code] = First Code in the CodeStream;
Output the String for [code] to the CharStream;
[old] = [code];
[code] = Next Code in the CodeStream;
while ([code] != EOF )
{
　　if ( [code] is in the StringTable)
　　{
　　　　Output the String for [code] to the CharStream; // 输出[code]所对应的字符串
　　　　[...] = translation for [old]; // [old]所对应的字符串
　　　　k = first character of translation for [code]; // [code]所对应的字符串的第一个字符
　　　　add [...]k to the StringTable;
　　　　[old] = [code]; 
　　}
　　else
　　{
　　　　[...] = translation for [old]; 
　　　　k = first character of [...]; 
　　　　Output [...]k to CharStream;
　　　　add [...]k to the StringTable;
　　　　[old] = [code]; 
　　}
　　[code] = Next Code in the CodeStream;
}

实际上解压算法要简单得多，因为他每次都是按照读入的标记来查找的，所以采用（前缀。后缀）的格式存储成一个结构数组就可以了，可以根据标记直接找到它的位置，再根据它的前缀依次往前找，每次把后缀压入一个栈，到头后弹出到输出流就可以了。