JPEGハフマン・テーブル – 解読実践(3)

さてさっき作成したハフマン符号は本当に一意で瞬時解読符号でしょうか? ハフマン木を作成してみます。さっきのハフマン符号は

00
010
011
100
101
110
1110
11110
111110
1111110
11111110
111111110

でした これに基づいて6bitsレベルまで作製したハフマン木は以下の通りです

一意即時解読可能と分かります。

JPEGハフマン・テーブル – 解読実践(2)

それでは前回のDHTを使用してハフマン符号を造りましょう

00 01 05 01 01
01 01 01 01 00
00 00 00 00 00 00

上記の16 bytesがそれぞれのbit数のハフマン符号個数でした。従って、

ハフマン符号bit数 その個数 ハフマン符号
1 0 NA
2 1 00
3 5 010
011
100
101
110
4 1 1110
5 1 11110
6 1 111110
7 1 1111110
8 1 11111110
9 1 111111110
10 0 NA
11 0 NA
12 0 NA
13 0 NA
14 0 NA
15 0 NA
16 0 NA

ということになります。つまりこのDHTを用いて使われるハフマン符号は

00
010
011
100
101
110
1110
11110
111110
1111110
11111110
111111110

の12種類ということになります。この符号が、瞬時復元可能で、しかも一意的に復元可能であることに注目して下さい。

JPEGハフマン・テーブル – 解読実践(1)

実際のDICOM XAをbinary editorである Sterlingで解析しています。JPEG Tagである SOI (Start of Image) = 0xFFD8を探し、そこからDHT = 0xFFC4を探すと以下のバイト列が見つかりました。

FF D8 FF C4 00 1F 00 00 01 05
01 01 01 01 01 01 00 00 00 00
00 00 00 00 01 02 03 04 05 06
07 08 09 0A 0B FF C3

DHTの次に出てきた JPEG Tabは SOF3 = 0xFFC3です。これは、Start of Frame of Loslessというタグです。従って、この0xFFC3に引き続いて実際のシネ画像の一フレーム・データが存在するのです。それではこの実際のXA dataをもとにDHTの解読を実践してみましょう。そのように体と脳にしみこませればプログラムもスイスイ進む筈です。まずは、DHT部分のみ抽出します。

FF C4 00 1F 00 00 01 05 01 01 
01 01 01 01 00 00 00 00 00 00
00 00 01 02 03 04 05 06 07 08
09 0A 0B

ということになります。これを前回のように、意味する部分で色分けしましょう。
FF C4  : DHTタグ
00 1F  : 自分を含めて以降16 + 15 = 31 bytesがDHT
00  : 輝度DC成分の印です

00 01 05 01 01
01 01 01 01 00
00 00 00 00 00 00
: この16 bytesがそれぞれのbit数のハフマン符号個数

00 01 02 03 04 05
06 07 08 09 0A 0B
 : それぞれのハフマン符号に続くデータのビット数
ということになりますね。

JPEG DHTの解析

実際のDICOM XAより取り出したDHT (Define Huffman Table)セグメントを記載しますもちろん、16進数表記であり、1 byteづつ区切っています

FF C4 00 19 00 01 01 01 01 01 01 00 00 00
00 00 00 00 00 00 00 01 00 02 03 04 05

これではその中の意味ある分類ごとに改行しました

FF C4
00 19
00
01 01 01 01 01 01 00 00 00 00 00 00 00 00 00 00
01 00 02 03 04 05

さらに色づけしましょう
FF C4
00 19
00
01 01 01 01 01 01 00 00 00 00 00 00 00 00 00 00
01 00 02 03 04 05
ファイルのバイト列をサーチして、0xFFを探します。0xFFがあれば、その次が0x00であれば、それは0xFFというデータと見なされますが、0x00以外であれば、JPEGのタグと見なされます。
そして、FF C4というバイト列は、それがDHTの開始タグと見なされます。
次の、2 bytesつまり、ここでは00 19ですが、このバイト以降、何バイトがDHTであるかを示します。ここでは 0x0019ですので、16 + 9 = 25 bytesがDHTということになります。これで、01 00 02 03 04 05の最後の05までがDHTということが判明します。
次の 1 byteここでは、00ですが、これにより、このDHTはJPEGの中のDC成分(直流成分)を示し、ハフマンテーブル番号0ということが分かります。特に00というのは、輝度のDC成分という意味になります。まさしく、DICOM XAで用いているのは、輝度のDC成分のみなのです。皆も容易に分かるように、シネ画像は、白黒grey scale画像です。つまり、輝度情報しか持っておらず、DC成分ということは、二次元DCT (Discrete Cosine Transfer: 離散コサイン変換)による画像圧縮がされておらず、エントロピー圧縮しかされていない、つまり圧縮によって画像の情報が失われない lossless圧縮がされている、ということを意味しています。
さて、これからが問題です。
次の16 bytes固定、つまりここでは01 01 01 01 01 01 00 00 00 00 00 00 00 00 00 00ですが、この部分は、この部分の最初から、1bitのハフマン符号が1個、2 bitsのハフマン符号が1個、 3 bitsのハフマン符号が一個 ・・・・ということを表しています。
ということは、このファィルで使われているJPEG圧縮は、以下のハフマン符号を使っている、ということになります

0
10
110
1110
11110
111110
1111110

はいここまで良いですね。
次のバイト列ですが、ここには、先の01 01 01 01 01 01 00 00 00 00 00 00 00 00 00 00部分の合計値個のバイト列が来ます。そして、意味するところは、それぞれのハフマン符号に続いて何ビットがデータ(その符号の意味)を表しているか? それを示します。
ここでは 01 00 02 03 04 05でしたので、
1 bitハフマン符号に続いては 1 bitがデータ、2 bitsのハフマン符号に続いては 0 bitがデータ、3 bitsハフマン符号に続いては、2 bitsがデータ、4 bitsハフマン符号に続いては、3 bitsがデータ、5 bitsハフマン符号に続いては4 bitsがデータ、6 bitsハフマン符号に続いては5 bitsがデータ ということを示しています。
ということは何を意味するのでしょうか? ここから先も理解するのは大変ですよっ
例えば ファイルの頭から読んで、ビット列を得ます。たとえばビット列 1110010011011011があったとします、これはどんな数字の列を表すでしょうか? 頭から順に 1 bitずつ取り出して、先のハフマン符号表と照らし合わせます。そうするとまず
1110 010011011011という風に、最初の4 bitsがヒットします。4 bitsハフマン符号に引き続く 3 bitsがデータでしたので、データ部分は次の緑部分
1110 010 011011011ということになります。このビット列 010を十進数であらわせば、0 x 4 + 0 x 2 + 0 = +2ということになります。従って、ここまでの最初の4 + 3 = 7 bitsで +2を表しました。
次いで、011011011の解析に移ります。再び先のハフマン符号表と照らし合わせますと、0 11011011というように1 bitハフマン符号にヒットしました。この場合、次の1 bitがデータということですから、1 1011011ということで、データは 1ということになります。当然この値は +1ですので、ここまでで十進法表記で、+2, +1と解読されました。
次の1011011部分の解読に移ります。再び先頭ビットからハフマン符号表をサーチします。そうすると、10 11011と2 bitsのビット列10でヒットしました 2 bitsのハフマン符号に引き続く0 bitがデータでしたね。うん? 0 bit? 何じゃそれは? つまり、この部分で 0というデータとなりました。つまりここまでで+2, +1, 0まで解読されましたね。さあ頑張りましょう 残るは11011でした。
これもハフマン符号表でサーチしましょう。そうすると、110 11というように110がヒットしましした。つまり3 bitsのハフマン符号です。この場合、続く2 bitsがデータ、ということになりますので、11つまり、2 + 1 = +3がデータということになります。こうして、数字列 +2, +1, 0, +3というようにこのビット列は解読されました。
ちなみに、それぞれの数字を非圧縮の状態つまり1 byte = 8 bitsで表すとすると8 x 4 = 32 bitsが必要です。しかしながら、我々が用いたデータ列1110010011011011は何と 16 bitsしかありません。従ってこの例では、(32 – 16)/32 = 50%という高い圧縮率が達成できた、ということになります。
難しいですね。僕の頭脳でもここまで理解するのに4年間かかりました。皆様方も頑張って下さいね。