Voxel(3D Data)を、高速多値ラベリング処理

ラベリング処理は比較的コスト(リソースを消費する)のかかる重い処理です。2次元や、3次元のデータは、通常
連続したデータの集まりとして表されます。2次元の画像は、画素が縦横に連続して並んだデータとして扱われ、
3次元の立体は、ボクセルが縦横高さ方向に連続して並んだデータとして扱われます。
データが並んでいる事は、ある画素やボクセルと接している画素やボクセルがある事を意味します。それぞれの
基本要素（画素やボクセル）は、固有の値（色や輝度）を保持しています。　連続する基本要素同士が同じ値を
持っている場合は、画像や立体の中で特徴のある領域を構成している要素であると判断できます。
となると、同じ特徴量を持った基本要素同士が接続している部分を識別したくなるのが人の常です。
この同じ特徴量を持った基本要素が構成する塊（接続している）毎に、識別出来るようにユニークな番号を割り
当てるのが、ラベリング処理です。
ところで、基本要素同士の接続とは何でしょうか？
基本要素、画素（pixel）やボクセル（voxel）は、正方形或いは立方体として表されます。　正方形のケースでは、
規則正しく並んでいると、画素同士は辺を介して接している場合と頂点を介して接している場合に分けられます。
辺を介して接している場合を４連結と言い、辺或いは頂点を介して接している場合を８連結と言います。
立方体の場合は、面を介して接する場合いと、面と辺を介して接する場合と、面と辺と頂点を介して接する場合
があり、それぞれ ６連結と１８連結と２６連結と言います。

基準点と近傍点	４連結 (■部)	８連結 (■部)
画像（pixel）データの連結性

Stanford のデータアーカイブから CTデータをダウンロードして使用します
本文中の画像は座標系の違いにより、リンク先の画像と上下が反転していますが意図的な処理です。

頭部の頭頂部から、喉に向かって aspect has converted 1:1:1.

Information on original data See also: The Stanford volume data archive Description: CT study of a cadaver head Dimensions: 113 slices of 256 x 256 pixels, voxel grid is rectangular, and X:Y:Z aspect ratio of each voxel is 1:1:2 Files: 113 binary files, one file per slice File format: 16-bit integers (Mac byte ordering), file contains no header Data source: acquired on a General Electric CT Scanner and provided courtesy of North Carolina Memorial Hospital

１、The Stanford volume data archive からgzipped tar file (7.3 MB) をダウンロードし、解凍します。
　　　CThead ディレクトリが作成され、CThead.1 ～ CThead.113 までのファイルが生成されます。

２、CThead2voxel を使って、スライスデータから３次元の voxel データを生成します。
　　　興味のある方が、ボクセルデータを生成する時の参考に、プログラム（CThead2voxel.c）を公開します。
　　　・プログラムの起動時に、ダウンロードし展開したファイルのあるディレクトリを指定します。
　　　　書き出すボクセルファイル名の指定も可能です。ボクセルファイルの仕様は、補足情報を参照して下さい。
　　　・各層毎のファイルを読み込み、ビッグエンディアンのデータをリトルエンディアンに変更します。
　　　・アスペクトを １：１：１ する、補完処理を行います。
　　　・符号なし16ビットデータ中の有効データ範囲（0x000～0xFFF）から、今回の処理では上位の 5ビットをデータ
　　　　として使用するので、CTデータと 0x0F80 で and を取り 8ビットの範囲に収める為に4ビットシフトします。
　　　　{ ( (unsigned short)(CT_Data) & 0x0F80 ) >> 4 }
　　　・ボクセルのヘッダー情報(補足情報を参照)とコメント(任意)に続け、ボクセルデータの本体を書き出す。
　　　　コメントは、XML 又は HTML 形式で記述する事で拡張性を保持します。カラーマップ情報を記録したい
　　　　場合など容易に記述できます。（後方の互換性は保障されません。知らない定義は無視されます）

３、ボクセルファイルの情報は、showVoxelHeader を使って確認できます。
　　　ボクセルデータの処理ソフトを作成する時の参考に、プログラム（showVoxelHeader.c）を公開します。
　　　・以下の利用が出来ます。 （windows 環境で利用可能なバイナリーファイルも同胞）
　　　　ボクセルデータの情報のみを表示させる。
　　　　　showVoxelHeader.exe CThead.vxl >nul
　　　　ボクセルデータのコメントのみを表示させる。
　　　　　showVoxelHeader.exe CThead.vxl 2>nul
　　　　　出力をリダイレクトしてファイルに書き出し、ブラウザー(一例)で確認する
　　　　　showVoxelHeader.exe CThead.vxl > voxel_comm.html 2>nul
　　　　　"C:\Program Files\Mozilla Firefox\firefox.exe" voxel_comm.html

興味のある方は、voxel を扱うプログラムを作成されては如何でしょうか。
補足情報
DICOM 形式のデータを読み込む場合には、ファイル名から推察される位置情報と、実際の位置が異なる
場合があります。 DICOM タグの グループ 0x0020 画像属性の エレメント 0x0013 インスタンス番号等を
参照する事で対処が可能です。

上記手順で作成したボクセルデータに、多値データに対応したラベリング処理を行った結果です。
(画像のラベリングで領域の面積が分かるように、領域の体積や重心が容易にもとまります)
本手法ではシーケンシャルスキャン（ラスタースキャン相当）方式を採用しており、１回のスキャン
で全多値ボリュームデータの連結解析を完了するので、非常に高速なラベリングが可能です。
また、処理時間は処理する連結性に依存し、６連結＜１８連結＜２６連結の順で長くなります。

	２次元の CTデータから生成した Voxel データを多値データとして、 ６連結のラベリング処理した結果 ラベルデータ(自然数)を強制的に 画像に見立てて表示 上記処理手順により作成した 連結部を強調する為に諧調を 下げた Voxel データを使用し ている事に注意してください
	Voxelのラベリングデータを擬似カラー 表示した例 同じ色の部分は、同一のラベル番号が 付与されている ３次元の連続性が、正しく処理されて いる事が確認できる。
	擬似カラー表示方向を変更した例 顔の前面方向から、後方にかけての画像

18連結ラベリングと26連結ラベリング
18連結ラベリング(擬似カラー表示)	26連結ラベリング(擬似カラー表示)

ラベリングデータから特定の部位を抽出
ボクセルデータは、既にラベリング済みなので、任意の領域（ラベル番号）を
指定（選択）できます。　　６連結ラベリングデータからの抽出結果

ラベル番号 #723 を抽出	ラベル番号 #3932 を抽出

　移動する画素は、１層毎に移動範囲が、１ピクセル以内に制限 (同じ場所には留まらない)
　　拡大画像を表示するには、対象画像をクリックして下さい。

6連結（移動体は全て別）	18連結（移動体は部分連結）	26連結（移動体は連続体）

無償の３次元データ多値ラベリング処理 プログラムの開発評価にともない期間限定で、３次元データの多値ラベリング処理を無料で行います。 (2011年3月31日まで) サービス利用条件： １、既に３次元データを所有している方。 　　・データの大きさの１辺が 1,000 ボクセル以下。（最大1Gボクセル： 1K x 1K x 1K） 　　・１ボクセルが、1、2、4 Byte の何れかで構成されている事（符号なし整数として処理）。 ２、6,18,26連結中の希望する何れかの連結解析による多値ラベリング処理。 ３、処理データに不具合が見つかった場合に障害報告の提出可能な方。（報告の書式は問いません） ４、処理結果を利用した事による如何なる損害に対して、一切の保障を行わない事に同意できる方。 質問及びリクエストは、メールにてお願い致します。（メールはこちらから）

ボリュームデータの解析で、多値ラベリングを用いた事例

The Stanford volume data archive terra-cotta bunny を使用した性能テスト 使用環境：　Core 2 Duo E7200 @2.53GHz Mem 4G Windows XP SP3 VOXEL:　512 x 512 x 360 ( 94,371,840 Voxel、符号なし16ビット) 処理方法：　26連結の多値データ対応のラベリング処理 （15.6 sec） シャビーなCPU環境でも、94,371,840 voxel の多値ラベリング処理を 15.6sec で完了した。 本ラベリング処理の時間は、ボクセル数にほぼ線形比例します ので、1Kx1Kx1K のデータでも、処理は３分以内での完了が期待できます。

ラベリング処理で使用する元のボクセルデータ
CTデータの変換で使用したプログラム（WindowsバイナリーとCソース）
ボクセルファイルの仕様

ボクセルデータは非常に大きなエリアを使用しますので、各種の処理を施す場合には処理時間が
非常に重要な要素（問題）となります。　ラベリング等の重い処理ではなおさらです。
コストを無視できる軍事用の装置（表面化しないので知る由も無いが）であれば潤沢な資金を利用
してハイスペックなコンピュータや、処理装置を利用できますので容易に実現出来るでしょうが、
汎用のましては、１世代以上前の事務用ＣＰＵを使用して実現するにはノウハウが必要となります。
1K x 1K x 1K (1G) 程度のサイズのボクセルであれば、数（２～３）分でラベリングが完了するので、
民生技術の中では性能的にトップクラスの部類だと考えています。医療やGISの世界ではニーズが
高いと理解していますので、今後の、この分野での発展に期待しています。
ここに記載の情報が、少しでも皆様のお役に立てば幸いです。　Are you following me?