様式 C-19	 科学研究費補助金研究成果報告書	 平成２３年６月１０日現在機関番号：３２２０１	 研究種目：若手研究（Ｂ）	 研究期間：２００９	  〜	  ２０１０	 課題番号：２０７０００９６	 研究課題名（和文）	  点群による複数ボリュームデータの可視化のためのモンテカルロ法に	 	  	  	  	  	  	  	  	  	  	  基づく並列点群生成	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	 研究課題名（英文）	  A	 Parallel	 Point	 Generation	 Using	 Monte	 Carlo	 Methods	 for	 Point	 	  	  	  	  	  	  	  	  	  	 	 Based	 Visualization	 of	 Multiple	 Volume	 Data	 研究代表者	 
	  木村	  彰徳	  （KIMURA	 AKINORI）	 
	  足利工業大学・工学部・准教授
	  研究者番号：６０３７３０９９	 研究成果の概要（和文）：	  近年のマルチコアプロセッサやコンピュータクラスタリングによる並列処理技術の発展によって，より大規模で高速な計算が可能になっている．このような計算で得られる大規模な結果の評価には可視化が重要な役割をしている．そこで，シミュレーションで得られた複数のボリュームデータを融合して可視化を行うための手法として，点群を用いた可視化技術に関する研究を行う．特に，ボリュームデータのフィールド値に対しモンテカルロ法によって点群を生成するための並列点群生成の研究である．
研究成果の概要（英文）： The evolving technologies of multicore processors or a PCclustering system enable a large scale and a fast calculations with parallel processingtechniques. In such calculations, computer visualization plays the role in evaluations ofcomplex and a lot of results. We have researched and developed a method to fuse andvisualize multiple volume data based on a point-based rendering. Especially, that visualization algorithm utilizes a Monte Carlo method for the parallel point generation.

交付決定額	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  （金額単位：円）
直接経費間接経費合	
  計２００８年度1,000,000	 300,000	 1,300,000	 ２００９年度500,000	 150,000	 650,000	 ２０１０年度600,000	 180,000	 780,000	 総	  計2,100,000	 630,000	 2,730,000	 研究分野：	  総合領域科研費の分科・細目：	  情報学・メディア情報学・データベースキーワード：	  可視化、並列処理、ボリュームデータ１．研究開始当初の背景情報技術の発展によって低価格で高性能なコンピュータを入手できるようになっている．特に，科学分野での利用において，マルチコアプロセッサやコンピュータクラスタリングによる並列処理が，より大規模な計算を可能にしている．しかしながら，このような並列処理システムで効率の良い計算を行うためには，並列処理アルゴリズムが必要である．それゆえに，既存のアルゴリズムで逐次処理の多いものは，今後，計算速度を飛躍的に上げることは困難になると推測できる．このように，今後のアルゴリズムに関する研究では，並列処理を可能にするものでなければ，コンピュータのリソースを効率良く用いることは不可能である．
パーソナルコンピュータによる計算システムの発展によって，様々な分野でコンピュータシミュレーションが活用されるようになっている．特に，大規模シミュレーションでは，大規模なモデルに対して高精度かつ高速に結果を得るための研究が進んでいる．そのため，今後もさらに，より大規模なモデルで，より高精度かつ高速な処理が要求されて行くと考えている．
シミュレーションの場合だけでなく，測定機器の高精度化によって，取得できるデータも大規模化している．例えば，現在の CT スキャナ装置では，物体を３次元的に 0.5mm程の間隔で，物体内の密度を測定できるようになっている．例えば，170cm の人体の全身のスキャンデータを取得した場合には，ボリュームデータのサイズが 512 512 3400 ボクセルにもなる．このデータをパーソナルコンピュータで，ストレス無くリアルタイムに加工や可視化することは非常に難しい．それが，倍の精度になるだけで，ボリュームデータのサイズは 8 倍にもなることを考えると，今後さらに大規模データの可視化を可能にするアルゴリズムの重要性は高くなる．
２．研究の目的可視化技術の役割として，大量の計算結果から単にデータを可視化するだけではなく，新たな発見や隠れた情報を見つけ出すことが要求される．そのため，シミュレーションで得た高精度の結果を可視化するアルゴリズムにも，大規模データを効率良く，正確に処理することが要求されるようになる．
今後，より大規模で高精度なボリュームデータの可視化が要求されることが予想される．そのために，ボリュームデータのグリッド構築に必要な接続情報が必要なく，グリッドのサイズや精度にほとんど依存しない点群によるボリュームグラフィックスは，より大規模なボリュームデータに対して効率的な処理を可能にする有用な手法であると考えられる．また，現在のボリュームレンダリングでは，高速化のために，グラフィックスハードウェア（GPU）を用いたレンダリングが主流になっている．しかしながら，高精度な可視化が必要な場合には，従来のレイキャスティング法などのダイレクトボリュームレンダリングによる可視化を行っている．GPU にはオンボードメモリ容量の制限があるために，大規模なボリュームデータの可視化は，可視化精度を落とすかデータ量を減らすことで対応している．
そのような大規模データを高精度で取り扱うのはほとんどが科学計算で，グラフィックスボードのメーカーが一般向けの商品で対応することは難しい．また，PC クラスタや GRID コンピューティングなどを用いた大規模計算では，それらの CPU リソースを用いた効率の良い処理が効果的である．
本研究では，複数のボリュームデータを融合して可視化を行うための手法として，点群を用いた（ポイントベース）の可視化技術に関する研究を行う．特に，ボリュームデータのフィールド値に対しモンテカルロ法によって点群を生成するための並列点群生成の研究である．また，開発した手法を用いた応用ソフトウェア又はソフトウェアライブラリを開発し，オープンソフトウェアとして公開することも目的としている．
３．研究の方法本研究で開発するボリュームデータに対する点群の並列生成法は，大規模かつ多様なデータに対応するために，ほとんどの処理をマルチコア及び PC クラスターシステムで実行可能な並列アルゴリズムとする．そして，複数の構造又は非構造格子のボリュームデータの融合を可能にする．
アルゴリズムの実装のために，PC クラスタ し ス テ ム に よ る 実 行 を 想 定 し ， MPI（Message Passing Interface）を利用し，C++言語で並列処理プログラムを開発する．また，１台のコンピュータでのマルチコアによる実行ではマルチスレッドや OpenMP を利用することが考えられるが，これは開発コストが高いため MPI による実装の評価を行った後に検討することにした．
開発した点群の並列生成法のアルゴリズムを実装した応用ソフトウェア又はソフトウェアライブラリは，オープンソースソフトウェアとして公開することを目標とすることで，利用されるアルゴリズムの開発を目指す．
４．研究成果	 (1)	 データ構造の検討	 ボリュームデータの可視化の一つとして，等値面表示がある．例えば，人体の臓器の形状を見たい場合である．このときに，必要となる点の数も数百から数千万点になることから，大規模点群から必要な点を効率良く検索するためのデータ構造を検討した．
領域分割データ構造として，多くの点群処理のアルゴリズムでも利用されているkd-tree データ構造がある．しかしながら，近傍領域の点群探索を改善するために次のようなデータ構造を検討した．
点群が広がるデータ空間を 3 階層に分割し木構造を構築する固定長の領域分割データ構造及び適応的な領域分割データ構造である．図１のように，固定長の領域分割データ構造は各領域を添字で直接参照でき、各領域の近傍領域の効率的な点群探索を可能にしている．一方，図 2 のような適応的な領域分割を行うデータ構造では、各軸方向の分割数を適応的に変更することで，固定長の領域分割データ構造での各領域に含まれる点群数の不均衡を改善することが期待できる．
図 3 に点群データを格納する適応的な領域図 1	 	 データ空間の固定長の領域分割	 図 4	 複数ボリュームデータの 2D 表示	 図 2	 	 データ空間の適応的な領域分割	 図 5	 複数ボリュームデータの 3D 表示	
 NZ 軸方向に分割Y 軸方向に分割X 軸方向に分割Point dataPoint dataPoint dataPoint dataPoint dataPoint data図 3	  適応的な領域分割データ構造の木構造分割データ構造の木構造の概略を示す．三次元空間に広がる点群を含む直方体のボリュームを考え，点群の数によって分割数を変更えることによって，各領域の保有する点群の数を揃える方法である．まず，Z 軸方向に領域の分割を行い，次に，その各領域に対してY 軸方向に領域の分割を行う．さらに，X 軸方向の領域においても同様に分割を行うことで，図 3 に示すような木構造を作成する．
分割された各領域にある点群は，葉ノードが持つことになる．どちらのデータ構造も一長一短があり，取り扱うデータによっても性能が変化することから，現段階では選択的にデータ構造を利用することを考えている．
(2) ボリュームデータの重ね合わせ表示の検討ここでは，がん治療法の一つである放射線治療で利用されるシミュレータの結果を想定したデータをもとに，複数のボリュームデータの重ね合わせ表示について検討する．
放射線治療シミュレータでは，がんを死滅させるために必要な，照射線量（放射線を人体に照射する量）が各臓器や部位にどの程度の影響を与えるかを見積もる必要があり，そのために放射線シミュレーションが行われている．放射線治療の計画を策定する放射線治療計画装置では，CT スキャナで取得した患者のデータを元に放射線シミュレーションによって適切な照射線量を見積る．そして，医師が指定した治療の重要箇所である関心領域に対して照射線量が適切に分布しているかを評価する．
図 4 は患者の CT データの画像にシミュレーションで得られた照射線量を重ね合わせて表示し，さらに医師が入力した関心領域を線で表示した結果である．図 5 は患者の CTデータの画像にシミュレーションで得られた照射線量及び照射された放射線の軌跡を重ね合わせて表示した結果である．
これらの結果のように複数ボリュームデータを表示することができた．しかしながら，生成された点群の状態の検証を進めるなかで，ボリュームデータを局所的に特徴が複雑な部分（フィールド値の変化が多様な部分など）でのサンプリングができていないことがわかった．その原因の一つは，そのようなボリュームデータに対するポテンシャルの設定が不適格なためにサンプリングができていないと考え研究を進めてきたが解決には至らなかった．
今後，本研究の一つの課題であった高精度な結果を得るため問題の解決しアルゴリズムを完成させ，応用ソフトウェア又はソフトウェアライブラリを公開することを考えている．
５．主な発表論文等	 （研究代表者、研究分担者及び連携研究者には下線）	 〔雑誌論文〕（計２件）①	  木村彰徳, 八田拓也, 市村智和, 仲田晋,田中覚, "複雑な陰関数曲面モデルの確率過程的並列サンプリング", 電子情報通信学会論文誌, 査読有, Vol.J92-D, No.3,pp.439-442, 2009.3.
②	  木村彰徳, 山添悠, 田中覚, 田中弘美, "ボリュームデータの局所特徴に基づく並列三次元領域抽出", 画像電子学会論文誌, 査読有, Vol.38, No.4, pp.471-480,2009.7.
	 〔学会発表〕（計３件）①	  北條雄也, 木村彰徳, "三次元形状計測装置で取得した点群データのための編集ソフトウェアの開発", 平成 22 年電気学会全国大会, 2010.3，東京都.
②	  A. Kimura, T. Yamashita, T.Akagi, T.
Sasaki, Y. Tatsumi, K. Hasegawa, S.
Tanaka "DICOM-RT Extension Support of Visualization Tool for Radiotherapy Simulation", IEEE NuclearScience Symposium Conference 2010,2010.11, Knoxville, USA.
③	  周東諒, 木村彰徳, "放射線治療シミュレーションのための可視化ツールの開発,"第１回電気学会栃木・群馬支所合同研究発表会, 2011.3，栃木県.
④	  A. Kimura, S. Tanaka, K. Hasegawa, T.
Sasaki, "gMocren: A volume visualization application for Geant4- based radiotherapy simulation", PTCOG50,2011.5, Philadelphia, USA.
	 
６．研究組織	 (1)研究代表者	 
	  木村	 彰徳（KIMURA	 AKINORI）	 足利工業大学・工学部・准教授	 
	  研究者番号：６０３７３０９９