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

さあ大分進みましたね。まあ自分で思っているだけで、分かっている方々から見れば、「なあにやってるの? 未だそんなレベルなの?」でしょうが、いいんだ いいんだ
ここまでのことを纏めましょう。何しろもう一つ配列が必要だと分かりました。この配列もバイト配列で良いでしょう。その個数はハフマン符号語の個数ですから これは動的に確保せねばならない、ということになります。何故ならばハフマン符号語の数は、それぞれのハフマン・テーブルが変化するからです。あるいは大きめの配列を確保してメモリーを無駄遣いしても良いのですが、なんかなあ スマートじゃないなあ 僕の美学に反するなあ
という訳で、BITS[]も動的に確保することにします。これなんかは何時でも16個と決まっているので、それも変な話しですが・・・
という訳で、まずはこれらの作業領域の確保部分です

typedef unsigned char u_char; // これ以降長いので
               // u_charという型を定義した
u_char * BITS = new u_char[16]; // バイト配列16個確保

for (int i=0; i<16; i++) { // データをセット
  BITS[i] = 0x00;
}
BITS[1] = 0x01; BITS[2] = 0x05; BITS[3] = 0x01;
BITS[4] = 0x01; BITS[5] = 0x01; BITS[6] = 0x01; 
BITS[7] = 0x01; BITS[8] = 0x01;

int sum=0;
for (int i=0; i<16; i++) {
  sum += BITS[i]; // これでハフマン符号語の総数を求める
}

u_char * HUFFBITS = new u_char[sum];
         // これでハフマン符号語長を保持する
         // HUFFBITS配列が動的に確保された
int * HUFFCODE = new int[sum];
         // ついでにハフマン符号語を入れる
         // 配列HUFFCODEも動的に確保する

さあこれで良いかな?
何しろ C++使うの2年ぶりなので、すっかり文法を忘れています。まあ、コンパイルすれば誤りは分かるのでまたその時点で修正しましょう。

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

さて実際にコードをコンパイルする前に ハンド・デバッグをしてみます。
まず、外側の走査の最初 つまり i=0の時を見てみます。
さて先ほど確保したBITS[]配列からどのようにしてハフマン符号を導けば良いでしょうか? さっき書いたアルゴリズムをそのままプログラムにすれば良い筈です

int code = 0;  // ハフマン符号初期値は0である
for (int i=0; i<16; i++) { // これでBitS[]配列全体を走査する
  for (int j=0; j<BITS[i]; j++) { 
    code+=1;  // BITS[i]の値だけハフマン符号に1 bit足す
    std::cout << code << std::endl;  // できたハフマン符号を出力する
  }
  code <<= 1;  // 次のビット数のハフマン符号のために、左に1 bitシフトする
}

これでどうでしょうか?
そんなに簡単に行く訳ありませんよね、デバッグするのも大変です。
ですから、内側のループつまり、jをカウンターとするループですが、BITS[i]は0x00でしたので、このループは回りません。従って、code+=1の命令は走りませんので、codeは0のままです。
そして、内側のループを出て、外側のループに入りますので、ここではcodeは 1 bit左シフトしますので、0x00となります。しかし問題は、このハフマン符号が 2 bitsのものだ、ということをどこかに記録せねばなりませんね。そうでないと、integer型の0x00は何ビットzeroが並んでいるのか誰にも分かりません。
そういうことで、このハンド・デバッグで、もう一つ何ビット長のハフマン符号であるかを記録する配列が必要、ということが分かりました。これは重要な進歩です。

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

さて先ほど確保したBITS[]配列からどのようにしてハフマン符号を導けば良いでしょうか? さっき書いたアルゴリズムをそのままプログラムにすれば良い筈です

int code = 0;  // ハフマン符号初期値は0である
for (int i=0; i<16; i++) { // これでBitS[]配列全体を走査する
  for (int j=0; j<BITS[i]; j++) { 
    code+=1;  // BITS[i]の値だけハフマン符号に1 bit足す
    std::cout << code << std::endl;  // できたハフマン符号を出力する
  }
  code <<= 1;  // 次のビット数のハフマン符号のために、左に1 bitシフトする
}

これでどうでしょうか?
そんなに簡単に行く訳ありませんよね、デバッグするのも大変です。

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

それでは前回のアルゴリズムをC++で書きましょう

まずは、何ビットのハフマン符号がいくつあるのか? つまり、例の青い部分の16 bytesを抱えるメモリーが必要ですね これを

unsigned char BITS[16];

で宣言します。そして、さっきの値を代入します

BITS[0] = 0x00; BITS[1] = 0x01; BITS[2] = 0x05; BITS[3] = 0x01;
BITS[4] = 0x01; BITS[5] = 0x01; BITS[6] = 0x01; BITS[7] = 0x01;
BITS[8] = 0x01; BITS[9] = 0x00; BITS[10] = 0x00; BITS[11] = 0x00;
BITS[12] = 0x00; BITS[13] = 0x00; BITS[14] = 0x00; BITS{15] = 0x00;

はい、これで準備整いました。
もちろん、できるだけコンピューターにやらせてしまおうとすれば、少しはプログラムらしく

for (int i=0; i<16; i++) {
  BITS[i] = 0x00;
}
BITS[1] = 0x01; BITS[2] = 0x05; BITS[3] = 0x01;
BITS[4] = 0x01; BITS[5] = 0x01; BITS[6] = 0x01; 
BITS[7] = 0x01; BITS[8] = 0x01; 

としても良いわけですが・・・

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

さてさっきの一意瞬時復号符号であったハフマン符号はどのような規則に則って作成したでしょうか?
それは簡単な規則なのです。

  1. ハフマン符号はビット0から開始する(これは取り決めなので文句言わないでね)
  2. 次のハフマン符号は+1したものとする
  3. ビット数を増加させるハフマン符号になる時には、これまでのハフマン符号に1を足してから、これを左に1 bitシフトして、最後のビットに0を追加する これによって、ビット数が1 bit増加したハフマン符号となる

これを繰り返すのみです。

あっ、もう朝カンファランスの時間

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年間かかりました。皆様方も頑張って下さいね。

bit入力 using C++

#ifndef __READBITSTREAM_H_
#define __READBITSTREAM_H_

#include <memory.h>
typedef unsigned char BYTE;
typedef unsigned int WORD;

class CReadBitStream
{
private:

protected:
	BYTE *mbpRead;			// 読み出しアドレス
	BYTE *mbpEndOfBuf;		// Bufferの終了アドレス
	BYTE mMask;				// bit maskであると同時に現在の読み出しビット位置 (MSB = 7, LSB = 0)
	bool mReadable;			// 1: 読み出し可、 0: 読み出し不可
	void IncBuf(void);		// 読み出しアドレスのインクリメントとアクセス違反のチェック
public:
	CReadBitStream(void);
	CReadBitStream(BYTE *bpBuf, int size);	// 唯一のconstructor
	virtual ~CReadBitStream(void);
	BYTE GetByte(void);		// 1 byte読み出し
	WORD GetWord(void);		// 1 word読み出し
	void CopyBytes(BYTE* bpDest, int n);		// n bytes読みだしてbpDestのアドレス以降にコピーする
	void SkipByte(int n);					// n bytes読み飛ばし
	int GetBit(void);						// 1 bit読みだして返す
	int GetBits(int numOfBits);				// numOfBits数のビットを読みだして返す
	BYTE* GetNextAddress(void);				// 次の読み出しアドレスを戻す
	int ResetBuffer(BYTE* bpBuf, int size);	// bufferを変更する
};

#endif __READBITSTREAM_H_

以前といっても、2010年12月に書いたプログラム探してきました。ビットストリームを扱うために、ファイルから読む込みためのクラスです。