読者です 読者をやめる 読者になる 読者になる

プログラムdeタマゴ

nodamushiの著作物は、文章、画像、プログラムにかかわらず全てUnlicenseです

GIFフォーマット講座3〜画像データの展開

今日は画像データの展開の仕方について。デコードです。

画像をデコードする際は基本的にエンコードの逆をたどればいいのです。

  1. LZW Minimum Code Sizeを読み込んで保存しておく。
  2. ブロックサイズを読み取る。
  3. 1で読み取ったサイズまでをデコードする。
  4. 2,3の繰り返し。
  5. ブロックサイズが0だったら終わり。




ただし、今回はブロックサイズを読み込む過程は無視して解説します。
(単純にいったんエンコードした物を255byte以下の小ブロックに分割しただけで、元は全体で一つなので、解説する上では必要ない。実際にデコードする際は、以下に述べる方法に、Nbyte読み込む事にブロックサイズがちょくちょく割り込んでいると思えば良いだけである。)



さて、前々回で10010010を圧縮すると100240になりました。
逆に100240を10010010に戻してみましょう。

手順は大まかにこんな感じです。
a.最初の数を出力数に、次の数を待機数に読み込みます。辞書を初期化します。
b.辞書の出力数のページの値と辞書の待機数のページにある値の最初の文字を並べた数を辞書の新しいページに書き込みます。
c.辞書の出力数のページに書かれている値を書き出します。
d.待機数を出力数に、新しく一つ読み込んで待機数に入れます。
e.以下、b〜dの繰り返し

まぁ、やってみましょう。例の汚い手描きですよ。
今回は0.1からなる数列ですので、辞書に0,1を登録しておきます。(ここではまだ、クリアコードとか考えていないので、この二つだけです)
B:出力数。K:待機数




ちゃんと元の10010010に戻りましたね。
ただ、これだけではうまくいかないこともあります。

0,1からなる数列111を圧縮してみて下さい。12になります。
では、この12を展開してみましょう。
まず、1を出力数に、2を待機数にセットします。
次に辞書登録を行います。

辞書の1P目の「1」と辞書の2P目にかかれている最初の値……って、辞書はまだ1P目までしか登録されていません。2P目は今回登録するのにいったいどうしろと言うのでしょう。

では、仮に2P目の最初の値をxと仮定します
そうすると、2P目に登録される数は「1x」となりますね。
おや?
xは2P目の最初の数、という条件がありますから「1x」の最初の数、つまり、1ということが決まります。

よって、x=1となり、2Pに登録する数は11となります。


一般化して言えば、今回登録するページが待機数に出た場合、辞書に登録する値は「出力数のページの値とその値の最初の数を並べた物」が辞書に登録されます。



基本的にはこれで終わりです。

後は、クリアコード、終了コードは出力しない、辞書に登録している個数が、2^nになったときは読み込みビット長を1増やす、クリアコードが出たら辞書の初期化、ビットは右から詰まっていることなど、エンコード時と同じ事に注意すれば問題なくデコードできるかと思います。

ただ、byte単位から必要bit分だけ読み出すのは中々面倒くさいです。