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を続けました。最後にその患者さんが、とても嬉しそうに「ありがとうありがとう」と言って下さったことが良かったな、と思いました。

今 羽田空港国際線

これから CHC (China Heart Conference)という阜外国立循環器病センターが開催している学会に招かれて一泊二日の北京行きです。

本日到着したらばそのまま阜外病院に直行し、慢性完全閉塞のライブデモンストレーション症例を治療します。羽田便は便利になった反面、こんなことが可能となり、余裕が無くなりますね。

積年の謎が溶けかかりつつあります それは Canonical Huffman Code

自分の尊厳というか、誇りをかけて CないしC++を用いて、DICOM XA viewerを自分が死ぬまでに作成したいのです。何回も何回も挑戦しては、挫折の連続でした。

その挫折の原因は分かっているのです、どうしてもそこで使用されている Huffman Codeの decodingアルゴリズムを理解できないのです。

DICOM XAは要するにパラパラ漫画です。一枚の漫画は、JPEG Losslessで格納されているのです。JPEG Losslessという企画はもう何十年も昔に制定された国際規格であり、その企画書も読みました。そこでは、HUFFTABという領域に、Huffman Codeによる圧縮をdecodeするためのキーが書かれているのです。そこまでは掴みました。

しかし、どんなアルゴリズムの解説書を読んでも、ハフマン圧縮されたデータをデコードするためには、ハフマン木のデータが必要としか書いていません。ところが、このHUFFTABにはそんな木構造のデータは無く、表形式のデータしか無いのです。

その謎が、急に溶け始めました。まず、以前購入して難しくて読めなかった、もう廃刊となっている書籍 オーム社刊行の「映像情報符号化」という本です。

昨日この本を読んでいて、あっと思いました。そこには、ハフマン圧縮を行って実際に画像情報を圧縮するためには、いちいちハフマン木を作成しては効率が悪いので、テーブル参照法を用いると書いてありました。どうやらこれが求める回答のようでした。どうしてこんな大切なこと、他のアルゴリズムの数ある書籍には一言も記載が無いのでしょうか。

そして、本日届いた英語の書籍 “Managing Gigabytes” という本をチラチラ見ていたら、ついに見つけました。そのアルゴリズムを Canonical Huffman Codes と呼ぶらしいのです。あー 時間を相当そうですね、かれこれ4年間無駄にしました。最初にこれを知っていれば・・・

もっとも、JPEG Losslessなんて今時デジカメにも使用しないし、 DICOM XAでしか残っていない過去の遺物なので、それに用いる Canonical Huffman Codesなんてものも、世間から忘れ去られているのでしょうね。

ようやく分かった – Unix/Linuxコマンド解説にある()で囲まれた番号の意味

Unix/Linuxのターミナル・コマンドの解説には必ず

$ls(1)

のようにコマンドの後ろにカッコで囲まれた数字がついてきます。これが何なのか? コマンドの解説本にも記載は無いのです。
ずっと疑問に思っていましたが、Linuxのメモリ管理Cライブラリである glib.c について勉強していてようやく分かりました。

セクション#	トピック
1	ユーザに利用可能なコマンド
2	 UnixとCのシステムコール
3	 Cプログラム用のCライブラリルーチン
4	特殊ファイル名
5	のUnixで使用されるフ​​ァイルのファイル形式と規則
6	ゲーム
7	ワープロパッケージ
8	システム管理コマンドと手順

ということらしいのです。要するにUnix/Linuxのオンライン・マニュアルである “man”コマンドで記載されているセクション番号なのです。このセクション番号は上記のように、その役割によって分類されているのです。