PNG:時雨エノキオプト:トップページへ
しとしと.時雨エノキオプトはここにある
「絵」でつづるワロタロの日々の記録である
天まで届け心の樹


GIFデコーダサンプルプログラム解説 ver1.11
since 2008/01/28
update 2009/06/26

GIFデコーダサンプルプログラム解説

概要
 ワロタロは先日,GIF画像ファイルの自前読み込みに挑戦してみた.そして一応読み込みに成功したので, GIFデコーダサンプルプログラムを作ってここで公開する. 同じように自作しようとする人の助けになれば良いと思う. ただ,ワロタロの勝手な解釈も多く含まれているので,ヒント程度に思っていただきたい.

 サンプルプログラムGIFDecConは,GIFファイルを読み込んでコンソールで表示するプログラムである. GIFファイルの中身をファイル先頭から順に表示してくだけのものである. 理解が一番面倒であるLZW解凍以外の部分は,簡単のため大胆に(?)省略してあるため, 必要に応じて機能追加して使っていただきたい.

GIFのバージョンはGIF89a,開発環境はVC++6.0なのだ.

[ サンプルプログラム GIFDecCon ダウンロード ] Ver1.1


 プログラムマップ
 LZW解凍アルゴリズム
 GIFの読み込みの雑多なヒント
 参考文献
 おわりに

GIFデコーダーサンプルプログラム解説

プログラムマップ
 一般的にこういうことはしないようにも思うが,ソースコード GIFDecCon.cpp の中身をぱっと見できるように図を用意した.矢印は,矢印元が矢印先を呼び出すことを意味している.

JPG:GIFDecConの内容
図1 GIFDecCon.cppの内容

 「GIF読み込み開始関数」は readGIF(char*) 関数である.この関数にファイル名を渡すと, コンソールにGIFファイルの内容が表示される.

 「GIFブロック読み込み関数」は, readGIF_Block(FILE*) 関数である.この関数はreadGIF関数 から呼び出され,順次読み込んだGIFブロックの種類に応じてさらに読み込み関数を呼び出す. 「GIF拡張ブロック読み込み関数群」と「GIFイメージブロック読み込み関数」 を切り替えるだけの関数である.

 「GIF拡張ブロック読み込み関数群」は readGIF_Block_Ext(FILE*) をはじめとする関数群で,各種拡張ブロックに 応じて細かい読み込み関数を呼び出して拡張ブロックを表示する.

 「GIFイメージブロック読み込み関数」は readGIF_Block_Image(FILE*) 関数である.画像データを 1ラインずつ読み込んで表示していく.画像データはLZWで圧縮されているので,LZWデコーダの各関数を使う.

 「GIFのLZWデコーダ」はLZWDec_InitDecStat(GifDecodeState *dec , int lzw_min)関数をはじめとする, GIFの仕様のもとLZW圧縮されたデータを読み込む関数群である.



GIFデコーダサンプルプログラム解説

LZW解凍アルゴリズム
 GIFではLZW圧縮が使われている. GIF特有な処理を含むLZW圧縮なので,まずは単なるLZW圧縮解凍について説明し, それを踏まえてGIF特有な処理について説明する.その後,ワロタロ的な解凍アルゴリズムも紹介する. GIF圧縮についてはここでは細かく述べない.

 LZW圧縮では,辞書を作成しながらコードを生成していく.解凍でも,ファイルからコードを 読み込みながら辞書を作成していく.必然的に,LZW解凍プログラムは ,「コード読込部」と「辞書作成部」の2部構成となる(とワロタロは考えている).


 まず,LZW圧縮アルゴリズムを説明する.

LZW圧縮アルゴリズム
1. 文字が1文字だけの語を全て登録した辞書を用意する.
    最初の1文字を読込んでそれを変数wに入れる.

2.1 1文字読込んで,変数kに入れる.
    圧縮すべきデータがもう無い場合,3へ.
2.2 変数wの直後に変数kが続いている文字列を変数wkに入れる.すなわちwk=w+kとなる.
2.3 変数wkが辞書に登録されているかを調べる.
2.4 wkが登録されている場合:
    2.1に戻る.
2.5 wkが登録されていない場合:
    wkを辞書に登録する.
    wを辞書の登録番号で符号化する.
    kをwに入れ,2.1に戻る.

3. 最後にwに語が残っている場合:
   wに残っている語を符号化する.
   この時点で,wに入っている語は辞書に登録されているはずなので,辞書の登録番号で符号化できる.

 このアルゴリズムは, しらぎくさいと実験室「LZW圧縮アルゴリズムの概要」 を参考にさせていただいた.ほとんどそのままである.
 つまり,未登録のデータ列となるまで手持ちバッファにデータを読み込んでいき,バッファの内容が未登録の データ列となったら,その直前までは登録済みであるから辞書の登録番号で登録する, これを繰り返す,というアルゴリズムである. このアルゴリズムは辞書の登録番号だけが符号化されるので,符号化された文字列は,もとより文字数が少なくなる.

 例として,0〜255の値をとる文字を扱う例を図2に示す.例では,辞書の0〜255の登録番号には,1文字の語が 既に登録されていることとして,1 255 1 255 1 255 というデータを圧縮している.

JPG:LZW圧縮の例
図2 LZW圧縮の例

 ちなみに,完成した辞書をとっておかないと解凍時に解凍できないように思えるが, 辞書を作りながら解凍していけば可能である.


 LZW解凍について説明する. 次に示すアルゴリズムにおいて,2は前に述べた「コード読込部」,3は「辞書作成部」に当たる. 「コード読込部」は入力から辞書番号を読み込み,「辞書作成部」は,圧縮の際に行った辞書作成と同じ方法で辞書を作成する.

LZW解凍アルゴリズム(ワロタロが自作した時の場合)
1. 文字が1文字だけの語を全て登録した辞書を用意する.

2.1 1文字読込んで,変数kに入れる.
    解凍すべきデータがもう無い場合,4.2へ.
2.2 登録番号kの語が単語登録されているかを調べる.
    単語登録されている場合:辞書から単語を読み出し,出力バッファに追加する.
    単語登録されていない場合:後述の「単語推定」により単語を推定し,出力バッファに追加する.

3. 出力バッファから辞書作成を行う.
    出力バッファを圧縮前データと考えれば,圧縮と同じ方法で辞書を作成していくことができる.
    出力バッファ中のデータの最後まで辞書作成を行う.

4.1 出力バッファの内容を出力する.
    2.1へ戻る.
4.2 出力バッファの内容を出力する.
    もうデータが無いので終了する.

 例として,0〜255の値をとる文字を扱う例を図3に示す. 入力データ(圧縮済データ)は1 255 256 で,解凍後は1 255 1 255 となる. ただしここでは,上記の解凍アルゴリズム中にある「単語推定」が運良く必要無い.

JPG:LZW解凍の例
図3 LZW解凍の例

 ここで,解凍アルゴリズム中にある「単語推定」について説明する. アルゴリズムでは,単語登録されていない場合「単語推定」するとあるが,普通に考えると, 単語が作成されていない辞書番号が解凍中に出てきてはいけないように思えるだろう. しかしこれはLZWでは特殊な場合ではなく,その場合「単語推定」して解決する.

  ※「単語推定」はワロタロの勝手な解釈であってスタンダードなものではないので注意

 ここでは説明のために,0〜255の値をとる文字を扱う場合を考える. 例えば1 255 1 255 1 255 1 255という元データを圧縮すると,1 255 256 258 255 という圧縮結果になる. この場合,解凍時に258を読み込んだ時点で,258番の辞書が登録されておらず問題になる.

JPG:未登録の辞書番号の出現
図4 未登録の辞書番号の出現(@〜Eは実行される順)

 しかし下図のように「コード読込部」と「辞書作成部」を並べると,258番の辞書が出力されようとしている 部分と辞書(258)に登録されようとしている部分に重複があることがわかる.重複部分は,辞書(258)に登録 されようとしている部分の最初の部分と同一であり,内容が確定している. そのためこの部分は「推定」できるのである.

JPG:LZW解凍で登録されていない辞書の番号が現れた場合の重複の様子
図5 LZW解凍で登録されていない辞書の番号が現れた場合の重複の様子
辞書(258)はまだ完成していないが,その時
点で258が現れても重複部分から推定できる



GIFデコーダーサンプルプログラム解説

GIFの読み込みの雑多なヒント
 GIFファイルの仕様は,GIF仕様書で決まっている. 仕様書は英語で書かれていたりするが,図を見ればなんとかならなくもないレベルである. ワロタロのプログラムを使うよりも,仕様書を見ながら自作した方が良いだろうと思う. そのため体系的な説明はせず,以降はGIF読み込みを自作する際に引っかかりそうな部分を説明というか紹介する.

 ・GIFのファイル構造は,ブロックという単位で構成されている.
 ・画像ブロック中のLZWデータは255バイト以下の塊ごとになっており,
  1文字はビット単位で符号化してある.
 ・GIFでは特殊な文字として「クリアコード」,「終了コード」が存在する.
 ・辞書は文字の値とその前の文字への参照による連結リストで実装されている場合が多い.
 ・「辞書が満杯になった」場合も考慮する必要がある.


GIFファイルのおおまかな構造
 GIFファイルの構造はブロックの集まりであり,こんなものである(図6). 拡張ブロックにはディレイタイム(GIFアニメで1画像を表示している時間)やコメントなどが記録される.

JPG:GIFファイルの中身
図6 GIFファイルの中身

 ブロックの中身の読み込みは簡単なファイル操作であり,データの意味も仕様書を読めば分かるため説明は省略する. あるいはこのページの上の方で公開しているプログラムを見れば参考になると思う.


画像ブロックのビットデータについて
 画像ブロックでのLZWデータ読み込みついて述べる.画像ブロックは図7のような内容である. LZWデータは,256バイト以下の塊ごとにまとめられていて,データの長さ(バイト数)とデータ本体の組の繰り返しになっている. ただし,長さが0のものは終端を意味し,そこで一枚の画像のデータは終了である. 各データ間はビットが繋がっている点には注意しなければならない.

JPG:画像ブロック
図7 画像ブロック

 LZW最小ビット長というのは,図6の「デーーータ」の部分を読み進んでいくビット長である. それと同時に,最初に用意する辞書のサイズやクリアコード等を決める重要なものでもある. LZW最小ビット長は,例えば256色の場合,9ビットになる.

JPG:ビット読み込み
図8 LZWデータ内のビット読み込み

 LZWデータは最初はLZW最小ビット長ずつ読み進む.読んだデータはコードと呼ばれる. コードは辞書の登録番号のことである. このビット単位での読み込みが意外と面倒くさかったりもするが,仕方が無い. 後に述べるが,辞書は拡張されることがあり,その際に読み込み長が1ビットずつ増える.

 実際にネット上で使われているGIFを見て見ると,ほとんとはLZW最小ビット長が9ビットである. 「GIFといえば256色」なので,文字コード(0〜255)と辞書コード等(256〜)を保存するために9ビット必要なのだ.


GIF独自なコードについて
 GIFでは辞書をうまく扱うために独自に「クリアコード」,「終了コード」というものを導入している. 分類すると次の四つがあるようである. (仕様で4つと決まっているわけではなく,ワロタロ流の分類である)

文字コード
 圧縮されていない,つまり読み込んだ値がそのままデータとなるデータのこと. GIF画像の多くは256色のため,多くの場合0〜255の値をとる. これらは初期状態から辞書に登録されているとみなされる.

クリアコード
 解凍中にクリアコードが出現した場合,辞書を初期化する. また,読み込みビット長も初期に戻す. 辞書中で、文字コードの最後+1に初期状態から登録されていることとする.多くの場合,256の値をとる.

終了コード
 終了コードが出現した場合,圧縮済みデータはそこで終了となる. 辞書中で、クリアコード+1に初期状態から登録されていることとする.多くの場合,257の値をとる.

辞書コード
 圧縮されているデータ(つまり辞書に登録されている)のこと.文字に直して出力する. 多くの場合,辞書拡張前で258〜511(9ビット),辞書拡張していくと最大で4095(12ビット) の値をとる.


辞書構造の注意点
 ネット上で公開されているプログラムでは,

   文字の値とその前の文字への参照による連結リスト

の構造で辞書を表現する場合が多いようである.確かにこの構造であれば,単語の前の方が共通している 場合に,単語の末尾を参照するだけで新しい単語を登録できるという利点は想像がつく. ただしポインタとクラス等を使って本格的な連結リストにするほどではなく,値の配列と参照の配列を 用意するだけでよいようである.

JPG:辞書の構造と参照の様子を示した図
図9 辞書の構造と参照の様子を示した図
この場合辞書259の内容は(254,2,12)、辞書260の内容は(254,2,12,3)となる


辞書の拡張時の注意点
 辞書が満杯になった時点で,辞書の大きさを2倍に拡張する. それまで作成されていた辞書の内容はそのままでよい.読み込みビット長は1増える. 辞書の拡張はそれだけで完了である. ただ,GIFの仕様で読み込みビット長は12より大きくしないことになっている. GIFファイルが正しく作成されていれば,ビット長が13になる前にクリアコードが出現して ビット長が9に戻るはずである. 例外処理はしておくべきだが13になっても読み込む方が悪いわけではないかもしれない



GIFデコーダサンプルプログラム解説

参考文献
しらぎくさいと実験室「LZW圧縮アルゴリズムの概要」
 今回デコードのアルゴリズムを参考にしたページです.

とほほのWWW入門 GIFフォーマットの詳細
 杜甫々さんのサイトの一部で,GIFファイルのデータ構造について述べられています. また,別のページでは過去の特許問題について述べられており勉強になります.



GIFデコーダサンプルプログラム解説

おわりに
 以上でGIF読み込みの説明は終了である. 多分に自己満足的な内容ではあったが,この文書が誰かの何かの役に立つことを期待する.
GIF:スマイルGIF←GIFファイル


過去ver


top

↓fade out