カテゴリ : プログラミング
キーワード (keywords) : lzw,gif,作成,アルゴリズム,フォーマット,サンプル,圧縮
説明 (description) : LZ78を改良した辞書式圧縮である「LZW圧縮アルゴリズム」の解説です。主にLZWを使用して画像を圧縮してGIFファイルを作成する方法をご紹介します。
登録日時: 2020-08-05 07:01:30
更新日時: 2020-08-05 07:33:42
LZWで画像を圧縮してGIFファイルを作成する方法をご紹介します。
1. LZWのアルゴリズム
2. GIFファイルのフォーマット
3. LZWを使用してGIFファイルを作成する
LZWの圧縮アルゴリズムは難しくはありません。困難と思われる箇所はGIFファイルの生成におけるビット操作です。このビット操作には「ビット長の変化」(3bitから12bitまで可変)や「ビットの右詰」や「ビットからバイト単位に変換」がありますので、その時のビットの確認作業が大変です。
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色
辞書番号 | 辞書内容 | 備考 |
---|---|---|
0ページ | 0 | |
1ページ | 1 | |
2ページ | 2 | |
3ページ | 3 | |
4ページ | 4 | クリアコード |
5ページ | 5 | エンドコード |
6ページ | 未登録 | |
7ページ | 未登録 |
この辞書にLZW圧縮で発見された文字列を「エンドコード」の次のページ以降にどんどん追加していきます。そして、辞書のサイズが満タンになったら、1bit分の辞書のサイズを大きくします。最大で12bitとなります。
クリアコードとエンドコードは、LZW圧縮の開始に「クリアコード」を出力して圧縮の終わりに「エンドコード」を出力する為に必要なコードとなります。
また、辞書が12bitで満タンになった場合に「辞書を初期化」(最初の状態にクリア)します。その初期化の際にもクリアコードを出力します。※クリアコードはクリア符号と翻訳される場合もあります。
次は「4bitの辞書」と「5bitの辞書」、「9bitの辞書」のサンプルとなります。
[4bitの辞書] - 文字列が3bitの範囲(0-7) 8色
辞書番号 | 辞書内容 | 備考 |
---|---|---|
0ページ | 0 | |
1ページ | 1 | |
2ページ | 2 | |
3ページ | 3 | |
4ページ | 4 | |
5ページ | 5 | |
6ページ | 6 | |
7ページ | 7 | |
8ページ | 8 | クリアコード |
9ページ | 9 | エンドコード |
10ページ | 未登録 | |
11ページ | 未登録 | |
12ページ | 未登録 | |
13ページ | 未登録 | |
14ページ | 未登録 | |
15ページ | 未登録 |
[5bitの辞書] - 文字列が4bitの範囲(0-15) 16色
辞書番号 | 辞書内容 | 備考 |
---|---|---|
0ページ | 0 | |
1ページ | 1 | |
2ページ | 2 | |
... 省略 ... | ||
14ページ | 14 | |
15ページ | 15 | |
16ページ | 16 | クリアコード |
17ページ | 17 | エンドコード |
18ページ | 18 | 未登録 |
19ページ | 19 | 未登録 |
... 省略 ... | ||
30ページ | 未登録 | |
31ページ | 未登録 |
[9bitの辞書] - 文字列が8bitの範囲(0-255) 256色
辞書番号 | 辞書内容 | 備考 |
---|---|---|
0ページ | 0 | |
1ページ | 1 | |
2ページ | 2 | |
... 省略 ... | ||
254ページ | 254 | |
255ページ | 255 | |
256ページ | 256 | クリアコード |
257ページ | 257 | エンドコード |
258ページ | 未登録 | |
259ページ | 未登録 | |
... 省略 ... | ||
510ページ | 未登録 | |
511ページ | 未登録 |
順序 | 内容 |
---|---|
1 | クリアコードの出力 |
2 | 圧縮対象の文字列(数字)から一文字を読み込みprefix変数に格納する |
3 | 次の一文字を読み込んでsuffix変数に格納する |
4 | prefix変数 + suffix変数を連結した文字列をcom1変数に格納する。次にcom1の内容が辞書に登録されているかを確認をする |
[登録済] | |
5 | 次の一文字をsuffixに格納する。com1 + suffixを連結した文字列を com2変数に格納する。次にcom2が辞書に登録されているかを確認をする |
[登録済] | |
6 | com2をcom1に格納して5に戻る |
[未登録] | |
7 | com2を辞書に登録する。com1の辞書番号を出力する。 prefixにsuffixを格納して3に戻る |
[未登録] | |
com1を辞書に登録して、prefixの辞書番号を出力する。 suffixをprefixに格納して3に戻る | |
8 | 全ての文字列を圧縮した後にエンドコードを出力する |
いきなりプログラムみたいな文章になりましたね。このような文章だとプログラムのコードを提示した方が早いですが、この記事を見てる方は自力で圧縮をしたい方だと思いますので今回はコードは提示しませんのでご了承ください。
2017/3/4 追記:オープンソースでGIF.jsを公開しました。
10010010 を圧縮すると「4, 1, 0, 0, 6, 8, 0, 5」となります。
[解説]
順序 | 内容 |
---|---|
1 | 文字列が0と1しかありませんので「3bitの辞書」で初期化する。 |
2 | クリアコードの「4」を出力する。 |
3 | 1と0を連結した文字列「10」が辞書に登録されていないので6ページ目の辞書に登録する。「1」を出力する。 |
4 | 0と0を連結した文字列「00」が辞書に登録されていないので7ページ目の辞書に登録する。「0」を出力する。 |
5 | 0と1を連結した文字列「01」が辞書に登録されていないので8ページ目の辞書に登録する。「0」を出力する。 |
6 | 1と0を連結した文字列「10」が辞書に登録されているので、10と0を連結して100とする。 この100は辞書に登録されていないので9ページ目の辞書に登録する。10の辞書番号の「6」を出力する。 |
7 | 0と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。 この010は辞書に登録されていないので10ページ目の辞書に登録する。01の辞書番号の「8」を出力する。 |
8 | 文字列の終端の0の辞書番号の「0」を出力する。 |
9 | エンドコードの「5」を出力する |
[辞書]
辞書番号 | 辞書内容 | 備考 |
---|---|---|
0ページ | 0 | |
1ページ | 1 | |
2ページ | 2 | |
3ページ | 3 | |
4ページ | 4 | クリアコード |
5ページ | 5 | エンドコード |
6ページ | 10 | LZWで登録されたページ |
7ページ | 00 | LZWで登録されたページ |
8ページ | 01 | LZWで登録されたページ |
9ページ | 100 | LZWで登録されたページ |
10ページ | 010 | LZWで登録されたページ |
010101010 を圧縮すると「4, 0, 1, 6, 8, 7, 5」となります。
[解説]
順序 | 内容 |
---|---|
1 | 文字列が0と1しかありませんので「3bitの辞書」で初期化する。 |
2 | クリアコードの「4」を出力する。 |
3 | 0と1を連結した文字列「01」が辞書に登録されていないので6ページ目の辞書に登録する。「0」を出力する。 |
4 | 1と0を連結した文字列「10」が辞書に登録されていないので7ページ目の辞書に登録する。「1」を出力する。 |
5 | 0と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。 この010は辞書に登録されていないので8ページ目の辞書に登録する。01の辞書番号の「6」を出力する。 |
6 | 0と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。 この010は辞書に登録されているので、010と0を連結して0101とする。 この0101は辞書に登録されていないので9ページ目の辞書に登録する。010の辞書番号の「8」を出力する。 |
7 | 1と0を連結した文字列「10」が辞書に登録されているので、10の辞書番号の「7」を出力する。 |
8 | エンドコードの「5」を出力する |
[辞書]
辞書番号 | 辞書内容 | 備考 |
---|---|---|
0ページ | 0 | |
1ページ | 1 | |
2ページ | 2 | |
3ページ | 3 | |
4ページ | 4 | クリアコード |
5ページ | 5 | エンドコード |
6ページ | 01 | LZWで登録されたページ |
7ページ | 10 | LZWで登録されたページ |
8ページ | 010 | LZWで登録されたページ |
9ページ | 0101 | LZWで登録されたページ |
00001110000 を圧縮すると「4, 0, 6, 0, 1, 9, 7, 0, 5」となります。
[解説]
順序 | 内容 |
---|---|
1 | 文字列が0と1しかありませんので「3bitの辞書」で初期化する。 |
2 | クリアコードの「4」を出力する。 |
3 | 0と0を連結した文字列「00」が辞書に登録されていないので6ページ目の辞書に登録する。「0」を出力する。 |
4 | 0と0を連結した文字列「00」が辞書に登録されているので、00と0を連結して000とする。 この000は辞書に登録されていないので7ページ目の辞書に登録する。00の辞書番号の「6」を出力する。 |
5 | 0と1を連結した文字列「01」が辞書に登録されていないので8ページ目の辞書に登録する。「0」を出力する。 |
6 | 1と1を連結した文字列「11」が辞書に登録されていないので9ページ目の辞書に登録する。「1」を出力する。 |
7 | 1と1を連結した文字列「11」が辞書に登録されているので、11と0を連結して110とする。 この110は辞書に登録されていないので10ページ目の辞書に登録する。11の辞書番号の「9」を出力する。 |
8 | 0と0を連結した文字列「00」が辞書に登録されているので、00と0を連結して000とする。 この000は辞書に登録されているので、000と0を連結して0000とする。 この0000は辞書に登録されていないので11ページ目の辞書に登録する。000の辞書番号の「7」を出力する。 |
9 | 文字列の終端の0の辞書番号の「0」を出力する。 |
10 | エンドコードの「5」を出力する |
[辞書]
辞書番号 | 辞書内容 | 備考 |
---|---|---|
0ページ | 0 | |
1ページ | 1 | |
2ページ | 2 | |
3ページ | 3 | |
4ページ | 4 | クリアコード |
5ページ | 5 | エンドコード |
6ページ | 00 | LZWで登録されたページ |
7ページ | 000 | LZWで登録されたページ |
8ページ | 01 | LZWで登録されたページ |
9ページ | 11 | LZWで登録されたページ |
10ページ | 110 | LZWで登録されたページ |
11ページ | 0000 | LZWで登録されたページ |
LZWには圧縮した値のビットの長さがあります。ビット長は辞書の登録数と連動して3bitから12bitまで自動的に増加していきます。ビット長が増えるタイミングは辞書が登録されて満タンになった「次のコード」から1bit増えます。
次は3つのサンプルのビット長になります。
元の文字列 | LZW圧縮 | ビット長 |
---|---|---|
10010010 | 4, 1, 0, 0, 6, 8, 0, 5 | 3, 3, 3, 3, 4, 4, 4, 4 |
010101010 | 4, 0, 1, 6, 8, 7, 5 | 3, 3, 3, 3, 4, 4, 4 |
00001110000 | 4, 0, 6, 0, 1, 9, 7, 0, 5 | 3, 3, 3, 3, 4, 4, 4, 4, 4 |
LZWの圧縮データはビット長のサイズを元に全てbit単位にします。次にbyte単位にするのですが、そのときはbitを「右詰」で埋めていきます。
画像ファイルをGIFファイルに変換する際には画像をあらかじめ256色以下に減色して、その画像の左から右、上から下の1ピクセル毎のパレットインデックスを取得してそのデータをLZWで圧縮します。
GIFファイルの色数は「2色/4色/8色/16色/32色/64色/128色/256色」でサイズは「1x1」から「65535x65335」となります。
※名称や用語は私の独自の名前になってる箇所があります。
名称 | バイト数 | 備考 |
---|---|---|
GIF Header | 13byte | |
(共通パレット) | 可変 | 省略可能 |
Block | 可変 | 複数のBlockを設定可能 |
Trailer | 1byte |
名称 | バイト数 | 内容 |
---|---|---|
シグネチャ | 3byte | GIF(0x47 0x49 0x46) |
バージョン | 3byte | GIF87a : 0x38 0x37 0x61 アニメサポート GIF89a : 0x38 0x39 0x61 アニメ/透過色サポート |
画像の横幅 | 2byte | |
画像の縦幅 | 2byte | |
共通パレット | 1bit | 0:存在しない 1:存在する |
1画素のビット数 | 3bit | 値:0-7 共通パレットのパレット数と同じ値が多い。 ※ここの値はあまり重要ではない。常に0(000)や7(111)の場合がある。仕様書には「この値はオリジナル・パレットの豊富さを表すように設定されるべきです。」と記載されている。 |
共通パレットのソートフラグ | 1bit | 0:未ソート 1:ソート済み(色の重要度順に整列) |
共通パレットのパレット数 | 3bit | 0-7 0:2色/1:4色/2:8色/3:16色/4:32色/5:64色/6:128色/7:256色 |
背景色の共通パレットインデックス | 1byte | 今回は0で良い。 ここの背景色はGIF Headerで定義されているイメージサイズとImage Dataブロックで定義されているイメージサイズが異なる場合のみ有効となります。(背景色は余白の色) |
ピクセルの縦横比 | 1byte | 0:比率情報なし 1-255:この値をNとして(N+15)/64と縦横比が算出される。 ※常に0で良い |
「共通パレット」「1画素のビット数」「共通パレットのソートフラグ」「共通パレットのパレット数」はこの順番で左詰にして1byteにします。
「1画素のビット数」の値が3の場合は「+1」されて実際は4bitとなります。「共通パレットのパレット数」の値が3の場合は「+1」されて4bitとなり、「2^4」で16色となります。また、「1画素のビット数」と「共通パレットのパレット数」は同じ値になる事が多いです。
GIF Headerの「共通パレット」が「1」の場合に存在する。
色はRGB順に並び「2^(共通パレットのパレット数 + 1)」個格納される。「共通パレットのパレット数」が0の場合は2色で「RGBRGB」の6byteのパレットが書き込まれます。
Blockには「画像ブロック」と「拡張ブロック」がありますが、今回はシンプルなGIFファイルを作成しますので画像ブロックのみを解説します。