LZW圧縮アルゴリズム[実践的なGIFファイルの作成]

LZWで画像を圧縮してGIFファイルを作成する方法をご紹介します。

目次

1. LZWのアルゴリズム
2. GIFファイルのフォーマット
3. LZWを使用してGIFファイルを作成する

はじめに

LZWの圧縮アルゴリズムは難しくはありません。困難と思われる箇所はGIFファイルの生成におけるビット操作です。このビット操作には「ビット長の変化」(3bitから12bitまで可変)や「ビットの右詰」や「ビットからバイト単位に変換」がありますので、その時のビットの確認作業が大変です。

1. LZWのアルゴリズム

1-1. 辞書の初期化

LZWの辞書サイズは3bit(8種類)から12bit(4096種類)までの可変長です。

LZW圧縮をする前には必ず「辞書を初期化」します。辞書を初期化するには最初に「辞書のサイズ」を決めます。圧縮対象の文字列(数字)が0-3の2bitの範囲(01230123...など)だと「2bit」に「+1bit」を加算して3bitの辞書サイズになります。

辞書のサイズが確定したら、次に圧縮対象の文字列の全ての種類を辞書に登録します。0-3の2bitの範囲だと辞書の0ページ目は「0」、1ページ目には「1」、2ページ目には「2」、3ページ目には「3」となります。4ページはクリアコードの「4」、5ページにエンドコードの「5」、6/7ページ目は未登録です。最終的に3bitの辞書は0-7の範囲となり8ページとなります。

[3bitの辞書] - 文字列が2bitの範囲(0-3) 2色/4色

この辞書にLZW圧縮で発見された文字列を「エンドコード」の次のページ以降にどんどん追加していきます。そして、辞書のサイズが満タンになったら、1bit分の辞書のサイズを大きくします。最大で12bitとなります。

クリアコードとエンドコードは、LZW圧縮の開始に「クリアコード」を出力して圧縮の終わりに「エンドコード」を出力する為に必要なコードとなります。

また、辞書が12bitで満タンになった場合に「辞書を初期化」(最初の状態にクリア)します。その初期化の際にもクリアコードを出力します。※クリアコードはクリア符号と翻訳される場合もあります。

次は「4bitの辞書」と「5bitの辞書」、「9bitの辞書」のサンプルとなります。

[4bitの辞書] - 文字列が3bitの範囲(0-7) 8色

[5bitの辞書] - 文字列が4bitの範囲(0-15) 16色

[9bitの辞書] - 文字列が8bitの範囲(0-255) 256色

1-2. 圧縮アルゴリズムの流れ

いきなりプログラムみたいな文章になりましたね。このような文章だとプログラムのコードを提示した方が早いですが、この記事を見てる方は自力で圧縮をしたい方だと思いますので今回はコードは提示しませんのでご了承ください。

2017/3/4 追記：オープンソースでGIF.jsを公開しました。

1-3. サンプル 1

10010010 を圧縮すると「4, 1, 0, 0, 6, 8, 0, 5」となります。

[解説]

[辞書]

1-4. サンプル 2

010101010 を圧縮すると「4, 0, 1, 6, 8, 7, 5」となります。

[解説]

[辞書]

1-5. サンプル 3

00001110000 を圧縮すると「4, 0, 6, 0, 1, 9, 7, 0, 5」となります。

[解説]

[辞書]

1-6. ビット長

LZWには圧縮した値のビットの長さがあります。ビット長は辞書の登録数と連動して3bitから12bitまで自動的に増加していきます。ビット長が増えるタイミングは辞書が登録されて満タンになった「次のコード」から1bit増えます。

次は3つのサンプルのビット長になります。

1-7. 圧縮データの保存

LZWの圧縮データはビット長のサイズを元に全てbit単位にします。次にbyte単位にするのですが、そのときはbitを「右詰」で埋めていきます。

1-8. 画像ファイルの変換

画像ファイルをGIFファイルに変換する際には画像をあらかじめ256色以下に減色して、その画像の左から右、上から下の1ピクセル毎のパレットインデックスを取得してそのデータをLZWで圧縮します。

2. GIFファイルのフォーマット

GIFファイルの色数は「2色/4色/8色/16色/32色/64色/128色/256色」でサイズは「1x1」から「65535x65335」となります。

※名称や用語は私の独自の名前になってる箇所があります。

2-1. 全体図

2-2. GIF Header(13byte)

「共通パレット」「1画素のビット数」「共通パレットのソートフラグ」「共通パレットのパレット数」はこの順番で左詰にして1byteにします。

「1画素のビット数」の値が3の場合は「+1」されて実際は4bitとなります。「共通パレットのパレット数」の値が3の場合は「+1」されて4bitとなり、「2^4」で16色となります。また、「1画素のビット数」と「共通パレットのパレット数」は同じ値になる事が多いです。

2-3. 共通パレット

GIF Headerの「共通パレット」が「1」の場合に存在する。

色はRGB順に並び「2^(共通パレットのパレット数 + 1)」個格納される。「共通パレットのパレット数」が0の場合は2色で「RGBRGB」の6byteのパレットが書き込まれます。

2-4. Block

Blockには「画像ブロック」と「拡張ブロック」がありますが、今回はシンプルなGIFファイルを作成しますので画像ブロックのみを解説します。

[画像ブロック]
・Image Data (0x2c)

[拡張ブロック]
・Graphic Control Extension (0x21,0xf9) 透過色など
・Comment Extension (0x21,0xfe) 画像のコメントを設定
・Plain Text Extension (0x21,0x01) テキストデータの設定(未使用に近い)
・Application Extension (0x21,0xff) アプリ独自の情報を設定

<Image Data(0x2c)の全体図>

<Image Data Header (10byte)>

ビットの扱いなどはGIF Headerと同様です。

<固有パレット>
共有パレットと同様

<LZW最小コードサイズ>
最初の辞書サイズの事で「LZW圧縮の最小ビット数」と呼ばれます。(2-8)

基本的にGIF Headerの「1画素のビット数」に「+1」を加算した値と同じになる。また、LZWのアルゴリズムの仕様上、2色の場合は「1」ではなく値を 「2」と設定する。

実際のbit数はGIF Headerの「1画素のビット数」や「共通パレットのパレット数」のようにこの値に「+1」を加算したbit数となる。

なので、2色の場合は3bit(2)の辞書となる。2色の場合が2bit(1)だと「0、1、クリアコード、エンドコード」の4種類になっていきなり辞書が満タンになるので、それを回避する為です。

<Blocks>

LZWで圧縮したデータを全て書き込む為には繰り返し出力します。

<Block Terminator>
常に0

2-5. Trailer

ファイルの終端で常に「0x3b」となる。

3. LZWを使用してGIFファイルを作成する

いよいよ、GIFファイルの生成に突入します。

LZWとGIFファイルのフォーマットはもう解説済みですので、サンプルを提示したいと思います。このサンプルデータがあるとなしでは、作業効率が全然違うと思います。

3-1. 3x3 2色 白黒

3x3で2色の白黒のGIFファイルです。

種類	画像	備考
3x3		ダウンロードはこちら
拡大		3x3のGIFファイルをペイントで拡大したものです

GIFファイルをバイナリエディタで開くとこうなります。

元のピクセルデータ(パレットインデックス)

圧縮後のデータ

圧縮データのビット長

後は圧縮データをビットに変換して右詰にして出力するだけです。

3-2. 3 2色 カラフル

3x3で2色のカラフルのGIFファイルです。

種類	画像	備考
3x3		ダウンロードはこちら
拡大		3x3のGIFファイルをペイントで拡大したものです

GIFファイルをバイナリエディタで開くとこうなります。

元のピクセルデータ(パレットインデックス)

圧縮後のデータ

圧縮データのビット長

3-3. メモ

以上となります。長時間、お疲れ様でした。

仕様書

GIF87a仕様書 (英語)
GIF89a仕様書 (英語)
GIF89a仕様書 (日本語) ※リンク切れ

参考リンク

GIFフォーマットの詳細
LZW 圧縮アルゴリズムの概要
LZW 圧縮アルゴリズム
画像データの圧縮（LZWについて）

• Twitter
• Facebook
• はてブ

• Pocket
• LINE

関連記事