GIF格式文件解码

时间:2024-03-10 08:35:56

找资料,看文档,动手验证,忙活了将近1个多月,图片处理的工作也算是小有收获。趁着目前掌握的知识还没有遗忘,且还有很大的兴趣来做一个分析总结,就是写作本文的动力了,也可以给以后做一个参考。
GIF-即为Graphics Interchange Format的缩写,它是基于LZW编码方式的图片存储格式,图片像素的颜色最高支持256色。
首先分析GIF格式图片的数据结构:
1、总体上,GIF文件的结构可分为:文件头(file header),GIF数据流(gif data stream)和文件终结器(trailer)三个部分。
i)文件头包含GIF标识和版本号,固定格式如下:

typedef struct gifheader

{

         BYTE bySignature[3]; //固定识别码”GIF”

         BYTE byVersion[3];  //版本号,可能为87a或89a

}GIFHEADER;

 

7 6 5 4 3 2 1 0        Field Name                    Type

     +---------------+

   0 |               |       Signature                     3 Bytes

     +-             -+

   1 |               |

     +-             -+

   2 |               |

     +---------------+

   3 |               |       Version                       3 Bytes

     +-             -+

   4 |               |

     +-             -+

   5 |               |

     +---------------+

ii)紧接着文件头的是逻辑屏幕标识信息(logical screen descriptor),由7字节组成,固定格式如下:

 

typedef struct gifscrdesc

{

         WORD wWidth;     //屏幕宽度像素

         WORD wHeight;   //屏幕高度像素

         //小字节序模式,大字节序的话则为 |m|cr |s|pixel|(1:3:1:3)排列。

         struct globalflag

         {

                   BYTE PalBits : 3;  //调色板的大小;

                   BYTE SortFlag : 1;    //调色板中RGB的值是否排序过

                   BYTE ColorRes : 3;   //原色图像的色彩分辨率

                   BYTE GlobalPal : 1;  //是否存在全局调色板

         }GlobalFlag;

         BYTE bybackground;      //背景颜色索引号

         BYTE byAspectRatio;     //纵横比

}GIFSCRDESC;

 

      7 6 5 4 3 2 1 0        Field Name                    Type

     +---------------+

  0  |               |       Logical Screen Width          Unsigned

     +-             -+

  1  |               |

     +---------------+

  2  |               |       Logical Screen Height         Unsigned

     +-             -+

  3  |               |

     +---------------+

  4  | |     | |     |       <Packed Fields>               See below

     +---------------+

  5  |               |       Background Color Index        Byte

     +---------------+

  6  |               |       Pixel Aspect Ratio            Byte

 

<Packed Fields>  =      Global Color Table Flag       1 Bit

                             Color Resolution              3 Bits

                             Sort Flag                     1 Bit

                             Size of Global Color Table    3 Bits

这部分结构中,GlobalPal标志决定文件是否提供全局调色板,如果为1存在的话,则调色板支持的颜色系列数由PalBits确定,即为
nSize = 3× 2××(PalBits+1)。cr标识的作用暂时没发现。

iii)如果存在全局调色板,则紧接着逻辑屏幕标识的就是全局调色板信息;如果没有指定,则该部分可以不存在。
全局调色板结构如下:

typedef struct gifRGB

{

         BYTE red;

         BYTE green;

         BYTE blue;

}GIFRGB;

即为红,绿,蓝的系列数组,图片各像素按照索引值获取对应的颜色值。

 7 6 5 4 3 2 1 0        Field Name                    Type

     +===============+

  0  |               |       Red 0                         Byte

     +-             -+

  1  |               |       Green 0                       Byte

     +-             -+

  2  |               |       Blue 0                        Byte

     +-             -+

  3  |               |       Red 1                         Byte

     +-             -+

     |               |       Green 1                       Byte

     +-             -+

 up  |               |

     +-   . . . .   -+       ...



iv)以上为固定格式信息,之后可以跟着以0X21标识的扩展数据块,也可以跟着以0X2C标识的图像数据块。
图像数据块以 0X2C起始,前部是图像描述符信息,结构如下:

typedef struct gifimage

{

         WORD wLeft;  //图像相对于逻辑屏幕左上角的X坐标

         WORD wTop;  //图像相对于逻辑屏幕左上角的Y坐标

         WORD wWith; //图像宽度

         WORD wHeight; //图像高度

     //以小字节序排列,如果大字节序,则为(1:1:1:2:3)格式。

         struct localflag

         {

                   BYTE PalBits : 3;  //局部调色板的大小

                   BYTE Reseved : 2; //固定置0

                   BYTE SortFlag : 1;  //局部调色板数据是否排过序

                   BYTE Interlace : 1;  //图象是否以交错方式存储

                   BYTE LocalPal : 1;  //是否存在局部调色板

         }LocalFlag;

}GIFIMAGE;

此处 LocalPal标识指定是否存在局部调色板,而PalBites则在存在局部调色板的场景下,为局部调色板的支持的颜色系列数,即为
nLocalSize = 3× 2××(PalBits + 1)。
而interlace标识指定紧跟着的图像是否以交织方式存储;

 7 6 5 4 3 2 1 0        Field Name                    Type

     +---------------+

  0  |               |       Image Separator               Byte

     +---------------+

  1  |               |       Image Left Position           Unsigned

     +-             -+

  2  |               |

     +---------------+

  3  |               |       Image Top Position            Unsigned

     +-             -+

  4  |               |

     +---------------+

  5  |               |       Image Width                   Unsigned

     +-             -+

  6  |               |

     +---------------+

  7  |               |       Image Height                  Unsigned

     +-             -+

  8  |               |

     +---------------+

  9  | | | |   |     |       <Packed Fields>               See below

     +---------------+

 

     <Packed Fields>  =      Local Color Table Flag        1 Bit

                             Interlace Flag                1 Bit

                             Sort Flag                     1 Bit

                             Reserved                      2 Bits

                             Size of Local Color Table     3 Bits



v)如果存在局部调色板,则紧跟着图像描述符,格式等同全局调色板,大小由nLocalSize确定;如果没有指定,则可以不存在。当存在局部调色板时,则后续紧跟着的一幅图像使用局部调色板;如果没有局部调色板,则图像使用全局调色板;如果全局调色板也不存在,则使用该系统自定义的调色板。

vi)局部调色板之后紧跟着图像压缩数据,格式为:
BYTE LZW_MinCodeLen;
Data  SubBlock0;
Data  SubBlock1;
...
Data  SubBlockEnd;
块结束标识SubBlockEnd固定为0X00.
Data格式为
BYTE DataLen;
BYTE Data[DataLen];
由于此处是用一个字节来指定子块长度,因此一个子块的最大长度不会超过255字节。数据块较大的话,需要隔分为许多子块。数据块以0X00结束,即指长度为0的子块。

 7 6 5 4 3 2 1 0        Field Name                    Type

     +---------------+

     |               |       LZW Minimum Code Size         Byte

     +---------------+

 

     +===============+

     |               |

     /               /       Image Data                    Data Sub-blocks

     |               |

     +===============+


关于图像数据块的组织方式,后续再详细介绍。

vii)图像扩展块均以0X21为起始标识,以一字节的扩展标签区分,也是以0X00为块结束标识。一般GIF包括的扩展块有:图形控制扩展(Graphic Control Extension, 0XF9),注释扩展(Comment extension, 0XFE),原始文本扩展(Plain text Extension, 0X01),应用程序扩展(Application Extension, 0XFF)。

2、gif格式存储图片的另一个优点,就是一个文件可以存储多幅图像,而图形控制扩展块可以用来控制图像显示的方式。

从上面的分析中,我们获得的每幅图像的数据流,实际上并非是原始图像数据,而是经过了LZW压缩,gif编码格式转换之后的规范数据流。如何反编码还原原始的图像数据呢?
首先,既然GIF是基于LZW压缩方式存储的,有必要清楚LZW编码,解码的基本原理,虽然gif文件在lzw编解码时又有其独特之处。
LZW压缩方式有三个重要的对象:输入数据流(CharStream),输出编码流(CodeStream),编译表(String table)。
i)LZW编码原理:
第一步,初始化编译表,录入所有可能出现的元字符。初始化前缀字符串pre_Stream,当前字符cur_Char为空。
第二步,从CharStream读入一个字符cur_Char=(next char in CharStream),用pre_Stream[cur_Char]作为一个新串,此时因为pre_Stream为空,所以其为元字符,必可以匹配到编译表中的某项;置换pre_Stream=cur_Char。
第三步,重新读入字符cur_Char=(next char in CharStream)。若cur_Char=EOF,转第十步;否则,转第四步。
第四步,用pre_Stream[cur_Char]作为一个新串,检查是否匹配编译表中的表项。
第五步,如果找不到匹配项,则输出pre_Stream在编译表(string table)中对应的索引值到CodeStream,把pre_Stream[cur_Char]作为新的项添加到string table,然后设置pre_Stream=cur_Char。重复到第三步。
第六步,如果找到了匹配项,则设置pre_Stream=pre_Stream[cur_Char]。重复到第三步。
第十步,输出pre_Stream在编译表(string table)中对应的索引值到CodeStream,结束编码。
用伪码表示如下:
--------------------------------------------
Init string table
pre_stream=empty
cur_char=empty

cur_char=read next char
while  cur_char != EOF
{
    if pre_stream[cur_char] is in stream table
    {
        pre_stream = pre_stream[cur_char]
     }
     else
     {
        output the index of pre_stream to code_stream
        append pre_stream[cur_char] to string table
        pre_stream = cur_char
     }
     cur_char = read next char
}
output the index of pre_stream to code_stream.
---------------------------------------------

ii)LZW解码原理:
第一步,初始化编译表;初始化code=empty, old_code=empty。
第二步,从编码流读入一个数据code;由于第一个数据必定为元项,可以找到对应的字符元[code]。输出该元字符[code]到char_stream,设置old_code=code。
第三步,重新从编码流读入一个数据code;如果code=EOF,则结束解码;否则转第四步。
第四步,检查该数据值是否在编译表中有对应索引。
第五步,如果有对应索引,则输出该索引对应的字符串[code]到char_stream;令k表示[code]字符串的首字符,则同时添加[old_code]k到编译表(string table)中;设置old_code=code;重复转第三步。
第六步,如果没有对应索引,则该数值必须是编译表(string table).size() + 1。此时,令k表示[old_code]字符串的首字符,输出[old_code]k到char_stream,同时添加[old_code]k到编译表中。设置old_code=code;重复转第三步。

用伪码表示如下:
--------------------------
init string table
code=empty
old_code=empty

code=read next code stream
output [code] to char stream
old_code = code
code=read next code stream

while EOF != code
{
     if code is less than size of string table
     {
          output [code] to char stream
          k = the first char of [code]
          append [old_code]k to string table
          old_code = code
     }
     else
     {
          k = the first char of [old_code]
          output [old_code]k to char stream
          append [old_code]k to string table
          old_code = code
     }
}
-----------------------------------
按照以上原理,LZW编码/解码的实现,相对是比较简单的。从个人的实践经验看,至少解码是很容易的;使用STL模板库的vector对象作为编译表的容器,每次添加新的表项到尾部,而查找索引时就可以直接随机下标定位。关于编码,因为涉及到一个查找匹配的问题,如何设计好编译表的组织结构对算法的效率影响较大;其它部分则难度不打。
总之,LZW编码时,就是以待编码的字符串在容器中查找匹配项,输出索引值。而解码时,则是根据索引值从容器中输出索引对应的字符串。
以上就是关于LZW压缩方式的详细解说。不过,要解码GIF文件,完全按照如上的方式是不行的,因为GIF文件的LZW压缩,是一种变长的,且会限制编译表最大容量的LZW压缩算法。

在了解LZW压缩原理的基础上,我们就可以继续深入分析GIF文件是如何实现图像解码的。
在GIF文件的格式中,图像数据部分会保存 LZW code size字段的信息,以及编码数据流。
1、LZW code size是指定初始化编译表时,用于说明编译表的大小可用几位bit位表示;例如,若其值为8,则表示初始化编译表大小为 2××8=256。另外,由于GIF图片最多会使用256种颜色,所以LZW code size的值不会超过8;而当图片颜色最小为二值黑白图时,该值不能为1,而是最小为2。

2、在GIF文件压缩中,编译表在初始化时,0-2××(LZW code size) -1为原始项;表项值2××(LZW code size)是清除编译表标识,即clear code,缩写为<CC>;遇到该值,解码程序需要重置string table,重置字长bit位为初始值(LZW code size)。而表项值 2××(LZW code size) + 1 是结束标识,即end-of-information,缩写<EOI>;遇到该值,停止解码。因此,用户自定义的编译表项,实际上是从 2××(LZW code size) + 2 开始的。也就是说,在实现解码的程序中,你在初始化string table时需要设置2××(LZW code size)+2个初始项。

3、GIF的LZW压缩是采用变长数据流,单次数据流的位长,最小为 LZW code size + 1位,最长不超过12位。也就是初始化完成后,string table的大小为 2 ×× (LZW code size) + 2;而从编码流中获取的第一个数据的bit位长 cur_bits = LZW code size + 1;在解码过程中string table的容量按1累次递增,当其大小 size() == (2 **cur_bits - 1)时,则需要把当前数据位长 cur_bits加一,下一次读取的数据位数为新的cur_bits值。当cur_bits == 12时,即使size() == (2**12 -1),此时也不再增加cur_bits值。一般而言,在此场景下,在编码阶段用户应该立即输出<CC>提示解码时从这里开始重置;而解码时读入此标识,则立即进行解码初始化,重置string table,且使cur_bits=LZW code size + 1的值。

4、关于gif的解码相比于LZW算法独特之处,上面几点已经做了详细说明。下面讲述的,是如何读取变长的编码流,用于数据解码。
GIF数据的提取是按照从 左->右,由上->下的顺序扫描图像形成的,经过LZW编码后形成变长数据流,然后按照8bit一组的方式划分为字节,最后按照字节分成许多数据子块存储。前面从GIF数据组织结构也可以看到,gif图像数据块都是以字节为单位,以一定数目的字节组合成子块,而一幅图像的数据一般由多个子块的数据形成。因此在解码的时候,需要把输入的字节流数据按照指定的变长位长截取,截断的数据才是真实有效的待解码数据。举例如下

高位       7654 3210
byte#0   abcd  efgh
byte#1   ijkl     mnop
...

则如果指定位长为5,依次提取的数据应该为    defgh,  opabc, jklmn, ...,即规则是,依次获取每个字节的从低位到高位的bit位,直到读入所有数据。

至此,关于gif格式图片的数据解码提取基本上就介绍完了。如果要有实体的印象,最好的做法就是用二进制方式打开一个gif格式文件,首先根据前面的格式说明对号入座;在解码时,确定最终是否解码成功,可以把解码出来的像素点个数,与图像说明中的图像宽,高的乘积比较,一致的话应该就是解码成功的。

注:注意解码时,初始数据位长为LZW code size+1,然后是在 size() == 2**cur_bits - 1时,再把cur_bits加一,下次读入的数据位长也就变长一位。另外,当cur_bits == 12时,此时即使string table的大小 size() == 2**cur_bits - 1,也不能再累加cur_bits了,而是保持12不变。此时,一般下一个读入的12位数据值应该是 2××(LZW code size),指示重新初始化。如此循环,直到解码结束。这些也是个人在实践验证的时候,理解并解决的问题。

另外,关于图像设置了interlace交织模式下数据的组织方式,暂没有动手研究验证。不过从原理上看,交织模式的信息介绍如下:
交织模式是为了在网络传输不理想的情况下,可以以渐变至清晰的方式显示较大图像的一种存储方式。它把原始图像分为4通道存储,每个通道的数据按照如下方式获取:
Group 1 :     Every 8th. row, starting with row 0.     (Pass 1)
Group 2 :     Every 8th. row, starting with row 4.     (Pass 2)
Group 3 :     Every 4th. row, starting with row 2.     (Pass 3)
Group 4 :     Every 2nd. row, starting with row 1.     (Pass 4)