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月に書いたプログラム探してきました。ビットストリームを扱うために、ファイルから読む込みためのクラスです。

JPEG DC成分のハフマン圧縮

再び挑み、ようやく目の前が開けてきました。今 3:30AMです。

そもそもの間違いは、JPEG losslessのDC成分に関するハフマン符号化圧縮についての大きな誤解でした。アルゴリズムの書籍などで紹介されているハフマン符号化では、ハフマン木を用いて符号化します。これによって、効率的に一意瞬時符号化・復号化が可能となるビット列を得ることができます。しかし、これらの書籍で紹介されているものは、その符号に対応するデータが1:1で対応付けられているのです。従って、最終的にはハフマン符号と対応データの対応付けの表が出来上がることになります。

しかし、JPEG Lossless DCではこれをしないのです。そこでのデータ格納形式は、ハフマン符号が表しているものは、データではないのです。データでなく、データを表現するビット数なのです。JPEG規格書では、この「データを表すビット数」のことを、「カテゴリー」と呼んでいます。日本語訳では、「分類」と訳されています。

これは一体何を表すのでしょうか? よく、が出てきます。これを理解できませんでした。しかし、ついに本日理解しました。このビット数、つまりカテゴリーで表されるビット数のデータをビット・ストリームから取り出すのです。例えば

カテゴリ3に属するハフマン符号が “10” だとします そうすると次のビット列は

10110111110100

はどうなるでしょぅか?
これは 1010111110100 という風に判断されます。

つまり、赤字部分がハフマン符号であり、この部分がカテゴリ3に属するものと判断されます。従って、引き続く 3 bitsつまり青字部分がデータということになります。

101を二進数と考えられば、その値は 2x2x1 + 2×0 + 1 = 5ということになり、結果的に10101の 5 bitsで5という数字を表すことができました。もともと5という数字は 通常 8 bitsで表現されますので、この操作によって、 8 -> 5 というように 3 bits節約されたことになります。つまり、(8-5)/8 = 37.5%の圧縮率が達成されたことになります。

ここで、ピクセルのビット数、つまりレベルを8 bitsとします。これは通常用いられているもので、そもそも人間の眼が識別できる濃度差の限界とも言えるものです。もちろん、DICOM XAでも 8 bitsの濃度差しか使用していません。濃度差が 8 bitsということは、0から255までの値が当てはまります。

さっきの方法で圧縮しようとしても、例えば255というデータを表すためには 8 bits必要ですから、8 bitsのデータビットの前に、8 という数字を表すハフマン符号がつけたされることになります。そうすると、今度は逆に余計なビットが付加されることになり、圧縮どころかデータ量の拡大が起こってしまいます。しかしながら、実際の画像ではここで一工夫することにより、データがゼロの周囲に収束するようにしています。それは、ピクセル毎の差分値を用いるのです。自然画像では、濃淡はほとんどの場合滑らかに変化します。ということは、差分を取れば祖値は小さい、ということになります。JPEG輝度DC成分では自然画像のこの性質をうまく利用します。

実際にJPEG 輝度DC成分では、ここでのデータは、隣のピクセルとの差分値を当てることになっていますので、その大部分は一桁の値に集積することになります。さらに、工夫してあり、差分は、左右に隣のピクセルと行うのではなく、ジグザグに隣り合うピクセルとの間で差分を取るのです。

ここまで理解すれば、いかにアルゴリズム本の「ハフマン符号化」とは異なるかが分かります。そして、この違いが JPEGに対する理解を妨げているのです。そもそも何故、このようなややこしいことをしているのか? これは実際にもっと理解を進め、プログラムを書いてテストしなければなりませんが、現段階で言える僕の推測は・・・


JPEG規格制定当時、コンピューターで表される画像のサイズは比較的小さく、せいぜい1,024 x 1,024ぐらいしか無かった。従って、8 bitsの濃度を表す1:1のハフマン符号:データ の対応付け表を画像データの中に持てば、そのハフマン符号表部分が冗長なデータとしてサイズが巨大になってしまった。
結果的に、上で述べた方法、つまり、データとの直接変換表は持たずに、画像データそのものの中に埋め込んだ

このように理解しています。

ついについに近づいた

ここ数年がかりの自分のプロジェクト 言わずと知れた DICOM XA Viewerの作成です。その前提として、XA fileの中のDHT (Define Huffman Table)の解析が必要です。それに悩み、この難解なテーブルにどれだけの時間を注いできたことでしょう?

もちろん分からないのは僕が馬鹿だからなのです。でも、馬鹿といっても、そんなにひどい馬鹿ではないのです。この問題に悩んでいる人は世の中たくさんいる筈なのです。そして、ついに同じ悩みで苦しみ、そして万民のためにその秘密を解き明かしているページにヒットしたのです。これまで発見できなかった筈です、何故ならば比較的新しいページだからです。しかも、日本語でなく英語のページです。いやいやここで糠喜びは禁物です。もっと読み解き、理解する必要があります。しかし、ついについに近づいてきた、そんな予感がします。

昨日のバンケット (Banquet)

昨日症例を 2時間ぐらい終えて、Welcome Dinner Party (Banquet)の会場に急ぎました。会場はオリンピック競技場のすぐ近くに作られた国家会議中心の4階でした。僕は、事前にその席上で挨拶のスピーチをするように言われていましたが、それがそんなに大きなパーティーだとは予想だにしていなかったのです。

昨日のパーティーは、僕が今まで経験したどんなパーティーよりも大きなものでした。丸テーブルが何と 130卓あり、それぞれに 10名超の参加者が着席したのです。そして、前列には大きな長方形のテーブルがあり、僕は Goa Runlin先生と、Hu Dayi先生に挟まれ、真ん中に正面を向いて座らされたのです。その長方形のテーブルには、アメリカ、ヨーロッパなどから著名な心臓外科の先生が、そして、世界麻酔学会会長とか、日本からは東京医科歯科大学教授が、世界心電図学会会長として参列しています。このテーブルには総勢60名ぐらいか座りました。

そして、挨拶は最初に中国心臓病学会会長が、次にいきなり僕が指名されたのです。もう全くのぶっつけ本番です。インターベンションを代表し、しかもアジアを代表して話をしました。昨日のライブ症例を例に挙げ、ヨーロッパやアメリカとは異なる現状、だからこそ互いの友好と交流が必要であることをはなししました。その中では、漫然たる心臓外科に大して批判的なことも話しました。

いやー 汗が出ましたね。こんな大きな会でいきなりスピーチできる日本人ってそんなにいないですよね。何しろ日本人は本番に極端に弱いのです。精神力というか胆力が足らないです。甘えた日本人ばかりです。

本日午前中にあった TRI Compititionは中国、台湾、香港の先生方が発表されました。全てTRIによるCTOばかりで、食傷気味でした。そしていま、BCIA (Beijing Capital International Airport)にいます。これから暫くして羽田行きの便で帰国します。

本日の予定

本日はもうかれこれ5年以上この中国で継続している TRI Competitionというのを開催し、その主催者として座長をずっと午前中します。

中国では僕が1997年頃TRIを導入してから、現在では全症例の 80%近くが行われているのです。大病院のみならず小病院でも行われており、そこでの優秀な医師を発掘する試みとして行ってきました。基本的に自分で行ったTRI症例の中で優れたものを呈示して頂き、それを複数の審査員が採点して集計し、トップを毎年選ぶ、というものです。事前にインターネットで一次審査がされています。

その後は、DRAGON Trialの最終打ち合わせを行い、そして羽田に戻ります。北京で困るのは、インターネット接続が制限される場合がある、ということです。時には Google検索そのものがブロックされたりします。今朝もそのために必要なページにアクセスできない状況です。帰国してからアクセスするしかありません。

昨日のライブデモンストレーション

昨日は一例慢性完全閉塞の治療をライブデモンストレーションで行いました。

症例は75歳くらいの男性で、CCS class 2の労作性狭心症患者さんでした。これまで、心筋梗塞の既往や、PCIあるいはCABGの既往はありませんでした。診断造影では、左主幹部遠位三分岐の病変+左冠動脈前下行枝入口部からの石灰化した慢性完全閉塞でした。

通常であれば、CABGに決まっていますが、患者さんが手術を拒否された、という理由でPCIになりました。

そのような状況ですので、順行性に行くにはあまりにも危険ですし、もちろん慢性完全閉塞部分はつるつるであり、何のとっかかりもありません。右冠動脈から良好な副血行が、conus branchを介して前下行枝心尖部に行っているのですが、これは蛇行がひどくとても使えません。PCIの時に造影して良く見ると中隔枝が使えそうです。一番遠位の中隔枝が比較的太いのですが、右冠動脈から分かれてすぐにhair-pin curveがありました。まずはそれから試みたのですが、案の定このヘアピンを越えません。その一つ手前の中隔枝を狙いました。ワイヤーは途中心室性期外収縮を出しながら何とか前下行枝近くまで行くのですが、前下行枝の中に入りません。そこでCorsairを進めるのですが、右冠動脈から中隔枝に入ったところで全く進みません。延長して、Finecrossに置換したのですが、同様に進みません。1.25mm balloonに交換しましたが同様でした。そうこうする内にワイヤーは中隔枝から抜けてしまいます。慌てずワイヤーをplastic-jacket hydrophilic wireに交換し、再度その中隔枝通過を狙いますが、今度は途中で行きません。そこで、先端造影して、ぐちゃぐちゃに既になっている中隔枝を造影で確認し、再度狙って今度はワイヤーを通過させました。しかし、そうは言っても同様にCorsiarなどが通過できないことは目に見えていたので、今度はワイヤー交換の時に思い切って7Fr guiding catheterの中に5Fr 子カテを入れて臨んだのです。もちろんこの時の予想される問題点は、Corsaiの長さが足りるか? というものですよね。可能な限り右冠動脈の中に子カテを進め、Corsairを押しこんだところ、今度は通過できなかった部分を越えていきました。しかし、もうCorsairがお尻にきいてます。そこで、メインの7Fr GCを右冠動脈内に深く挿入し、5Fr子カテも#4PD入口部まで進めました。もちろん患者さんは胸痛を訴え、ST II, III, aVFは上昇しました。それでも続けざるを得ませんでしたので、Corsairを押しこんでようやくCorsiarは前下行枝に抜けました。それから子カテをぎりぎりまで引いて虚血を解除し、Miracle 3により慢性完全閉塞部分の遠位から左主幹部への穿通をこ試みました。案の定慢性完全閉塞は固かったのですが、一か所通りやすい部分があり、その部分を通過して、左主幹部そして大動脈に抜けました。

問題はそれからです、順行性ガイディング・カテーテルからIVUSを入れて、逆行性ワイヤー (Miracle 3)が真腔を通過して大動脈に抜けていることを確認したのですが、何しろ長さが足りず、Corsairで慢性完全閉塞部分を通過することができないのです。従って、やわらかいワイヤーに置換して、順行性ガイディング・カテーテル内への逆行性ワイヤー挿入を試みるのは危険です。色々考えた末、順行性ガイディング・カテーテルから鈍角枝にワイヤーを挿入し、そのワイヤーを深く押しこんで順行性ガイディング・カテーテルを左主幹部で浮かし気味にして、ガイディング・カテーテルの向きを調整しながら逆行性Miracle 3を何とか順行性ガイディング・カテーテル内に回収しました。こうなればしめたものです。順行性ガイディング・カテーテル内で3.0mm balloonを拡張することによって traction anchoringを行い無理やりCorsairを順行性ガイディング・カテーテル内に引き込みました。それからは、300CMワイヤーを用いて型の通り行い、左主幹部から前下行枝にかけて Xience-Vを三本植え込み最終的には綺麗な仕上がりで終了しました。

みんな大喜びで、助手の先生からは、その時メインの助手と、それ以外に2名の助手、合計3名の中国人医師が助手について下さったのですが、「またファンが増えました」と、言われました。

僕の手技が放映される前に日本人のある医師が講演していました。術者として当然マイクとイヤフォンをつけているので、その内容が聞こえます。最初は慢性完全閉塞に対するTRIの効用について、続けて慢性完全閉塞に対する逆行性アプローチについての講演だったようです。内容は問題ありません。しかし、その医師の普段の診療に対する姿勢を伝え聞いていましたのでとても評価できませんでした。そんなことを思いながら黙々とPCIを続けました。最後にその患者さんが、とても嬉しそうに「ありがとうありがとう」と言って下さったことが良かったな、と思いました。