DHTセグメントの内容解析

ハフマンコードで記述されたデータを元データに復元するには
ハフマンコードの値と元データ値との対応を知る必要がある。
JpegファイルのヘッダにはDHTセグメントと呼ばれる領域があり、
そこにハフマンコードと元データとの対応を表す情報が格納されている。

Jpegヘッダの雛形をGIMPによるJpegファイルをもとに作成した時、
DC用とAC用のDHTセグメントを抜き出して別ファイルに確保した。
これらDHTは実はいわゆるJFIF標準に出来上がっている。

そこでまず、DC用DHTとその意味合いを書き下すとこうなる。



一番左の列は先頭から何Byte目かをあらわし、
次の列はそこの内容を16進数で書き出している。
その次は16進数の意味することをざっくり書いている。

さて、DHTと言うのは「ハフマンテーブル定義」の意味なのだが、
どういうハフマンコードがどんな値に対応するかの
直接的な一覧表にはなっていない。

まず1・2番目のFFC4はコレがDHTであることを意味する「表札」であり、
続く3・4番目の001FでこのDHTセグメントが
「表札の後」に31(=1x16+15)Byte続くことをあらわす。
(この表札2Byteとセグメント長2Byteの記述ルールは
一部を除いてJpegでの基本)

続く5番目は上位4bitと下位4bitそれぞれに別の意味があり、
上位4bitが0ならこのセグメントがDC成分用であることを意味し、
上位4bitが1ならばAC成分用であることを意味しており、
下位4bitはハフマンテーブルに与えた識別番号である。
(ハフマンテーブルはDC/ACで別々に認識するので、
DC/AC間では識別番号が重複可能)

6番目から21番目までは、使用するハフマンコード・セットは
何bit(桁)のものが何種類あるかを記述している。
例えば8番目のところに「5」と言う記述があるが、
これは3bit(3桁)のハフマンコードが5種類あると言う意味であり、
18番目の「00」記述は13bitのハフマンコードは存在しないことを意味する。

この様子をハフマンツリーにするとこうなる。



このハフマンツリーの作り方を説明しておくと、
まずツリーは「0」と「1」の1bit段階に分かれるが、
DHTより1bitコードは0種類･･･つまり採用が無いので、
「0」も「1」も次の2 bit段階へ枝分かれして進む。

DHTより2bitコードは1種類存在するので、1個だけコードを採用する。
採用するのはコードを2進数値として見たときに
値の小さい方からがルールなので「00」を最初のハフマンコードとする。

採用部分からは枝は伸ばさず、
それ以外の3ヶ所から次の3 bit段階へ枝分かれして進む。
3bitコードは5種類存在するので、先と同様に値の小さい方から
010, 011, 100, 101, 110を選定する。

こうして選定したコードを見ると、同じbit段階での選定では左端の2進数値に
「+1加算」しながら指定数だけ選んで行くのだとわかる。

次の4bit段階へは採用されなかった「111」の所だけから枝分かれして進む。
さて、4bit段階の最小値は「1110」なのだが、
この値は「111」を左へビットシフトさせたと見ることが出来る。
つまり算術的には「x2」の処理である。
（111=7で1110=14だから間違いないね？）

以上のようにして上記のツリーが出来上がる。
なお、何故9bitコードの所で1個採用・1個不採用で終わるのかはわからない。
(ただし「終わる」は、それ以上コード採用の無い「実質的な終了」の意味。
採用が無くなっても16 bitコードの段階まで採用数をDHTには記述するのがルール)

そんなんだったら、
8bitコードの所で2個採用で終わって良いのではないかと思うが
どこをぐぐっても理由はわからない。
(ちなみにACのハフマンツリーも右下端に1個不採用のまま終わる)

さて、DHTの6番目から21番目まででハフマンコードセットは決まるが、
それらをどんな値に対応させるかは、まだわからない。
この対応を記述したのが22番目から33番目までである。

22番目から33番目までは、ハフマンコードの小さい方から順に、
ハフマンコードの直後に続くデータ値部分のbit数が記述されており、
(DCの場合。ACはさらにゼロランレングス値の指定が加わる)
コレに従って与えられた値に対応すべきハフマンコードを決める。

･･･良くわからない？･･･
では具体例で行こう。

DC成分のデータ値6(10進数)を先のDHTにより変換記述するとしよう。
10進数の6は8bitの2進数では「00000110」である。
この内、上位の「00000」は8bitにするための帳尻合わせで、
6という数値を表すのに意味を持っている有効な部分は「110」の3bitの部分だ。

そこでDHTの22番目から33番目までの部分から
「03」が記述されている所を探すと25番目の所が「03」になっている。

25番目は22番目から数えると(22,23,24,25)4番目になる。
そこで今度はDHTの6番目から21番目までを参照して作ったハフマンツリーから
4番目に採用されたコード表記を求めて、これが「100」とわかる。
(3bitハフマンコードの3番目だね)

以上により、
Jpegファイルに記述するのは、ハフマンコード「100」と
データの有効部分「110」を連結した6bitの「100110」だ。

ところで･･･先のDHTの表に1ヶ所怪しげな部分がある。
それは22番目で、
ルールどおりに解釈すれば0bitのデータを付加することになる。
で、「0bitのデータ」って何なのよ？･･･ってハナシだ。

理由は一旦保留するが、結論として「0bitのデータ」はゼロのことである。
(モチロン、ゼロを0bitデータと捉えるのはJpeg処理でのローカルルール)
なので、DC成分ではゼロ値を記述する時はハフマンコードの「00」だけを記述し、
データ値記述は行わない。

次にAC用DHTとその意味合いはこうなる。



表の見方は基本的に先のDCのDHTの表と同じ。
6から21番目までを使ってハフマンコードを選定するやり方もDCの時と同じ。
若干の違いがあるのは22番目以降のデータの意味合いである。
(と言っても、コレがハフマンコードの小さい方から順に
対応すべきデータの仕様を指定していることには変わりが無い)

AC用DHTでは22番目から183番目までは上位4bitと下位4bitに分けて
(つまり2桁の16進数として見るなら、上位下位で1個ずつに分けて)
値を読み取り、上位桁の表す数がゼロランレングスの数であり
下位桁の表す数が(DC同様に) 直後に続くデータ値部分のbit数である。

ただし、特殊な意味を持つものが2種類だけ登場する。
それは「00」と記述されるものと「F0」と記述されるものである。
「00」は上の表の25番目に登場しているが、
この場合は、それ以降のAC成分はブロック終端まで全てゼロであることをあらわし、
通常、コレを「EOB」と表記する。

もう一つの「F0」は「ゼロが15個連続し、さらにゼロが後続する」ことを意味し、
通常、コレは「ZRL」と表記したりする。
(上記表では途中省略部分にあり、登場していない)
なぜZRLコードが存在するかというと、
DHT記述の仕様からゼロランレングス数は4bitで表せる範囲の15までだから。
このため、それを超えるゼロ連続は一旦15個で切って、コレをZRLコードに置き換え、
そこから改めてゼロランレングス数をカウントすることになっている。


AC成分が
5, 0, 0, 1, (0が17個連続), 1, ･･･ブロックの最後までゼロ
となっている場合のハフマンコード化の具体例。

まず5は2進数で101で3bitで表現できる数であり、
このAC成分列では5の前にゼロは存在しないので、0RL=0,Data=3bitから
表の24番目を元にハフマンコードの採用3番目で「100」を使用して、
まず「100101」が決まる。

次は2連続のゼロの後の1なので、0RL=2,Data=1bitから
表の30番目を元にハフマンコードの採用9番目で「11100」を使用して
「111001」となる。

次はゼロが17連続してからの1なのだが、ゼロ連続が16個以上なので
一旦15連続ゼロの部分をZRLコードに置き換える。
ZRLコードは「11111111001」である。

するとZRLの後は、ゼロ2連続後の1(0RL=2,Data=1bit)になるので、
先と同じく「111001」となる。
以降、終端までゼロ続きなのでEOBコードである「1010」を記述する。

以上を全て連結して、
100101111001111111110011110011010
ってな具合になる。


ところでデータが正の場合は良いが、
負の数の場合は、その2進数表現が通常のイメージと異なる。

現在のほとんどのコンピュータでは負の数は「2の補数」で表現するが
Jpegのハフマンコード変換では「1の補数」を使用する。

10進数の-1, -2, -3を8bitの2進数で表す場合、
2の補数では11111111, 11111110, 11111101だが、
1の補数では11111110, 11111101, 11111100になる。

ちなみに負の数の1の補数表現は対象数の絶対値を取って
これを2進表現にし、そのビット反転を行うことで得られる。
2の補数表現は、1の補数表現にさらに+1することで得られる。

なお、負の数をハフマンコード変換でデータ記述したり、そのbit数を数える時は、
上位に連続する「1」を取り除いて考える。
つまり、-1, -2, -3は0, 01, 00として考える。
DCハフマンでデータ値0をbit数ゼロ・変換値記述ナシで扱うのは
これをbit数1で変換値0として扱うと、
データ値-1の時のbit数・変換値とカブってしまうからだ。

都度、マトモにやるとハフマン変換はめんどくさいので
工夫しよう。

- つづく -