大規模ボリューム処理に関する研究 第3報-大規模距離場生成のためのコンパクトなデータ構造

摘要

ボリュームデータから距離場を生成する距離変換[1] は，高精細化するCT 画像の形状処理（中立面抽出[2] など）において重要な技術である．第1 報において，out-of-core 法を用いた距離変換(OoCDT)を提案した．OoCDT は，ボリュームデータを小領域のクラスタに分割した後，それぞれのクラスタに対して距離変換を行うことで，低メモリで大規模データの距離変換を可能にした．しかし，中間データが非常に大きいため，ディスクを圧迫するだけでなくファイルI/O の多さが問題として残っていた．本報では，out-of-core 距離変換のデータ構造を改良した疎格子距離変換(sparse grid distance transform: SGDT) を提案する．本手法は，クラスタの距離場を前景背景を表す2 値画像で持つ．これは，クラスタの境界部の距離場と2 値画像があれば，各クラスタに対する1 回の距離変換で完全な距離場を復元できるという観察に基づいている(図1)．クラスタの中間データは2 値情報になるため，データ量だけでなくファイルI/O も大幅に削減できるだけでなく，計算時間も高速になる．