(57)【要約】【課題】  本発明の目的は、入力ボリュームデータを不連続性を考慮しながら、局所特徴に応じて、適応的な四面体階層構造を構築することである。【解決手段】  本発明では、アダプティブ・グリッドと呼ばれる適応的四面体格子構造を生成するアルゴリズムを示す。連続したボリュームが、視点の変化に関係なく一定の精度で近似されるまで、一次微分や、等値面の曲率のような局所特徴に応じて、グリッドの格子点を新たに生成しながら、四面体を再帰的に分割するというアダプティブ・グリッド生成法の並列アルゴリズムを開発した。また、各格子要素がそれぞれ独立に格子分割を行う過程で発生するクラックの形成を回避し、不連続性を保存する並列アルゴリズムも開発した。【選択図】    図１
2005196505.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
入力された３次元画像ボリュームデータで表されている空間を参照するするために、該空間を初期立方体格子要素の集合に分割設定する初期設定手段、
前記初期設定手段が設定した前記各初期立方体格子要素をそれぞれ６つの同形の四面体格子に分割する初期分割手段、
前記初期分割手段が分割したある四面体格子について、該四面体格子の最長の辺の両端の格子点における局所特徴量の差を検知する局所特徴量検知手段、
前記局所特徴量の差をあらかじめ設定された近似精度と比較して探索する再帰的近傍探索手段、
前記局所特徴量の差が前記近似精度を満たさない場合には、該近似精度を満たすまで、前記四面体格子の最長の辺の中点で該四面体格子を２つの四面体格子に再帰的に２分割してゆく再帰的分割手段、
前記局所特徴量の差が前記近似精度を満たす場合には、近傍からの影響を確認するために、前記四面体格子の各辺を共有して隣接する各四面体格子の内部の局所特徴量の変化の大きさが、前記近似精度を満たすか否かを再帰的に確認する再帰的確認手段、
として機能させ、
前記再帰的近傍探索手段が再帰的に探索した前記局所特徴量の変化に基づいて、
四面体格子内の該局所特徴量の変化量が閾値以下になるまで、
前記再帰的分割手段が前記四面体格子を再帰的に２分割することにより、
前記コンピュータに、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させる、
３次元画像データの適応的かつ階層的な四面体格子構造表現生成プログラム。
【請求項２】
前記再帰的近傍探索手段が前記初期立方体格子要素の局所特徴量の変化を再帰的に探索する領域である影響領域内の境界面と該初期立方体格子要素の表面との距離は、
前記初期分割手段が該初期立方体格子要素から分割した６つの四面体格子を、
前記再帰的分割手段が再帰的に２分割することにより、
該初期立方体格子要素の一辺の長さの距離未満となる、
請求項１に記載の、３次元画像データの適応的かつ階層的な四面体格子構造表現生成プログラム。
【請求項３】
前記再帰的分割手段は、
該再帰的近傍探索手段が前記初期立方体格子要素を各々独立に、該初期立方体格子要素の影響領域内で再帰的に探索した前記局所特徴量の変化に基づいて、
該初期立方体格子要素を各々独立に再帰的に２分割する、
請求項２に記載の、３次元画像データの適応的かつ階層的な四面体格子構造表現生成プログラム。
【請求項４】
入力された３次元画像ボリュームデータで表されている空間を参照するするために、該空間を初期立方体格子要素の集合に分割設定する初期設定手段と、
前記初期設定手段が設定した前記各初期立方体格子要素をそれぞれ６つの同形の四面体格子に分割する初期分割手段と、
前記初期分割手段が分割したある四面体格子について、該四面体格子の最長の辺の両端の格子点における局所特徴量の差を検知する局所特徴量検知手段と、
前記局所特徴量の差をあらかじめ設定された近似精度と比較して探索する再帰的近傍探索手段と、
前記局所特徴量の差が前記近似精度を満たさない場合には、該近似精度を満たすまで、前記四面体格子の最長の辺の中点で該四面体格子を２つの四面体格子に再帰的に２分割してゆく再帰的分割手段と、
前記局所特徴量の差が前記近似精度を満たす場合には、近傍からの影響を確認するために、前記四面体格子の各辺を共有して隣接する各四面体格子の内部の局所特徴量の変化の大きさが、前記近似精度を満たすか否かを再帰的に確認する再帰的確認手段と、
を備え、
前記再帰的近傍探索手段が再帰的に探索した前記局所特徴量の変化に基づいて、
四面体格子内の該局所特徴量の変化量が閾値以下になるまで、
前記再帰的分割手段が前記四面体格子を再帰的に２分割することにより、
前記コンピュータに、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させる、
３次元画像データの適応的かつ階層的な四面体格子構造表現生成装置。
【請求項５】
入力された３次元画像ボリュームデータで表されている空間を参照するするために、該空間を初期立方体格子要素の集合に分割設定する初期設定手段と、
局所特徴量の差をあらかじめ設定された近似精度と比較して探索する再帰的近傍探索手段と、
前記局所特徴量の差が前記近似精度を満たさない場合には、該近似精度を満たすまで、四面体格子の最長の辺の中点で該四面体格子を２つの四面体格子に再帰的に２分割してゆく再帰的分割手段と、
を備えたコンピュータを用いて、
３次元画像ボリュームデータで表されている空間から、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させる方法であって、
入力された３次元画像ボリュームデータで表されている空間を準備するステップと、
入力された３次元画像ボリュームデータで表されている空間を参照するするために、該空間を初期立方体格子要素の集合に分割設定するステップと、
前記初期設定手段が設定した前記各初期立方体格子要素をそれぞれ６つの同形の四面体格子に分割するステップと、
四面体格子の最長の辺の両端の格子点における局所特徴量の差を検知するスッテプと、
前記局所特徴量の差をあらかじめ設定された近似精度と比較して探索するステップと、
前記局所特徴量の差が前記近似精度を満たさない場合には、該近似精度を満たすまで、前記四面体格子の最長の辺の中点で該四面体格子を２つの四面体格子に再帰的に２分割してゆくステップと、
前記局所特徴量の差が前記近似精度を満たす場合には、近傍からの影響を確認するために、前記四面体格子の各辺を共有して隣接する各四面体格子の内部の局所特徴量の変化の大きさが、前記近似精度を満たすか否かを再帰的に確認するステップと、
前記再帰的近傍探索手段が再帰的に探索した前記局所特徴量の変化に基づいて、
四面体格子内の該局所特徴量の変化量が閾値以下になるまで、
前記再帰的分割手段が前記四面体格子を再帰的に２分割することにより、
前記コンピュータに、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させるステップと、
を含む、
３次元画像データの適応的かつ階層的な四面体格子構造表現生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元物体の画像ボリュームデータを適応的かつ階層的に表現、再構成、視覚化する適応的かつ階層的ボリューム・モデルに関する。
【背景技術】
【０００２】
ＣＴやＭＲＩなどの発達により、正確かつ容易に３次元物体のボリュームデータを得ることが可能となった。ＣＧの分野では、そのようなデータを表現・再構成・視覚化する問題が急速に注目を集めるようになってきた（例えば、非特許文献１、２参照。）。
【０００３】
しかし、そのようにして得られたデータは、一般的に膨大であるので効率的に処理を行うには、明確な精度に基づいて効率よくボリュームデータを表現できるボリュームモデルが必要とされる。したがって研究者たちは、さまざまな視覚的な処理の中で、効率的に使用することができる正確さに基づいたボリュームモデルを構築する問題に直面することになる。
【０００４】
過去１０年間、３次元で階層的モデルを構築するために、最も単純で強固なセルである四面体を用いた新しいアプローチが紹介されてきた（例えば、非特許文献６，７，８，９，１０，１１参照。）。階層的四面体構造を構築する上で考えなければならない大きな問題は、各々の四面体が独立に分割される時、近似ボリュームにクラックが生じるかもしれないということである。このことが並列インプリメンテーションをより難しくしている。
【０００５】
クラック問題を解決するために様々なアプローチがとられてきた。Ｍａｕｂａｃｋは、最初に部分的に分割し、その後にメッシュを広げることによってクラックを回避するという手法を考案した（例えば、非特許文献１１参照。）。
【０００６】
Ｂｅｙの方法は、クラックを回避するのに、２タイプの分割のコンビネーションを使っている（例えば、非特許文献８参照。）。
【０００７】
Ｎｉｅｌｓｏｎは、クラックをカバーするＣｏｏｎによるバッチモデルを使うという新しいアプローチを提案した（例えば、非特許文献９参照。）。
【０００８】
これらの新しい四面体を用いたアプローチは確立されているが、並列処理のためのインプリメンテーションや、滑らかなボリュームデータを視点の変化に不変で、任意の精度で近似するのための手法を開発する必要がある。
【０００９】
【特許文献１】特開平６−２１５０７６号公報（段落番号０００９〜００１６、図１）
【非特許文献１】A.E. Kaufman, “State of the Art in Volume Graphics,” VolumeGraphics, pp.3-28, 2001.
【非特許文献２】G.M. Nielson, “Volume Modelling,” Volume Graphics, pp.29-48, 2001.
【非特許文献３】C.H. Chien and J.K.Aggarwal, “VolumeSurface Octrees for the Representation of Three-DimensionalObjects,” Computer Vision Graphics and Image Processing, Vol.36, pp.100-113,1986.
【非特許文献４】Y Zhou and B Chen and A Kaufman, “Multiresolution TetrahedralFramework for Visualising Regular Volume Data,” Proc.IEEE Visiualization ’97,Phoenix, AZ, pp.135-142, 1997.
【非特許文献５】Trotts.I, Hamann.B, Joy.K, Wiley.D, “Simplefication of tetrahedralmeshes with error bounds”, IEEE Transactions of Visualization and ComputerGraphics, 1999.
【非特許文献６】G.M. Nielson, “Tools for triangulaions and tetrahedrizations intScientific Visualization,” IEEE CS, pp.429-525, 1997.
【非特許文献７】M.Mauback, “Local bisection refinement for Nsimplicial gridsgenerated by reflection,” SIAM Journal of Scientific Computing, Vol.16, No1,pp.210-227, 1995.
【非特許文献８】J Bey, “Tetrahedral mesh refinement,” Computing, Vol.55, No13,pp.355-378, 1995.
【非特許文献９】G.M. Nielson and D. Holliday and R.T. Roxborough, “Cracking thecracking problem with Coons patches,” Proc.IEEE Visualization ’99, SanFrancisco, CA, 1999.
【非特許文献１０】B.Gregorski, M.Duchaineau, P.Lindstrom, V.Pascucci, “InteractiveView-Dependent Rendering Of Large Isosurfaces”, IEEE Visualization 2002,pp.475-482, Nov, 2002.
【非特許文献１１】T.Roxborough, G.M.Nielson, “Tetrahedron Based, Least Squares,Progressive Volume Models with Application to Freehand Ultrasound Data”. Ieee2000, pp.93-100, 2000.
【非特許文献１２】H.T Tanaka and F.Kishino, “Adaptive mesh generation for surfacereconstruction: Parallel hierarchical triangulation without cracks,” Proc.IEEE10th International Conference on Pattern Recognition, pp.88-94, 1993.
【非特許文献１３】H.T Tanaka, “Accuracy-BasedSampling and Reconstruction with Adaptive Meshs for Paralle HierarchicalTriangulation,” int.Journal of Computer Vision and Image Understanding, Vol.61,No3, pp.335-350, 1987.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
そこで本発明は、入力ボリュームデータの適応的な四面体格子構造を構築しようとする。本発明の目的は、視点の変化に関係なく一定の精度で近似されるまで一次微分や等値面の曲率のような局所特徴に応じてグリッドの格子点を新たに生成しながら、滑らかに変化するボリュームデータの階層的四面体構造を自動的に構築することである。
【課題を解決するための手段】
【００１１】
本発明に係る３次元画像データの適応的かつ階層的な四面体格子構造表現生成プログラムは、コンピュータを、入力された３次元画像ボリュームデータで表されている空間を参照するするために、該空間を初期立方体格子要素の集合に分割設定する初期設定手段、前記初期設定手段が設定した前記各初期立方体格子要素をそれぞれ６つの同形の四面体格子に分割する初期分割手段、前記初期分割手段が分割したある四面体格子について、該四面体格子の最長の辺の両端の格子点における局所特徴量の差を検知する局所特徴量検知手段、
前記局所特徴量の差をあらかじめ設定された近似精度と比較して探索する再帰的近傍探索手段、前記局所特徴量の差が前記近似精度を満たさない場合には、該近似精度を満たすまで、前記四面体格子の最長の辺の中点で該四面体格子を２つの四面体格子に再帰的に２分割してゆく再帰的分割手段、前記局所特徴量の差が前記近似精度を満たす場合には、近傍からの影響を確認するために、前記四面体格子の各辺を共有して隣接する各四面体格子の内部の局所特徴量の変化の大きさが、前記近似精度を満たすか否かを再帰的に確認する再帰的確認手段、として機能させ、前記再帰的近傍探索手段が再帰的に探索した前記局所特徴量の変化に基づいて、四面体格子内の該局所特徴量の変化量が閾値以下になるまで、前記再帰的分割手段が前記四面体格子を再帰的に２分割することにより、前記コンピュータに、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させる。
【００１２】
上記のように再帰的確認手段は、前記局所特徴量の差が前記近似精度を満たす場合でも、近傍からの影響を確認するために、前記四面体格子の各辺を共有して隣接する各四面体格子の内部の局所特徴量の変化の大きさが、前記近似精度を満たすか否かを再帰的に確認するるため、クラックの発生を回避することができる。
【００１３】
また、上記のような方法で初期立方体格子要素から分割される四面体格子を再帰的に２分割することにより、次のような影響領域を定義することができる。尚、上記入力３次元画像ボリュームデータで表されている空間を参照するするために導入された初期立方体格子要素は、任意の大きさでよい。
【００１４】
本発明に係る３次元画像データの適応的かつ階層的な四面体格子構造表現生成プログラムは、前記再帰的近傍探索手段が前記初期立方体格子要素の局所特徴量の変化を再帰的に探索する領域である影響領域内の境界面と該初期立方体格子要素の表面との距離は、前記初期分割手段が該初期立方体格子要素から分割した６つの四面体格子を、前記再帰的分割手段が再帰的に２分割することにより、該初期立方体格子要素の一辺の長さの距離未満となる。
【００１５】
影響領域内の境界面と該初期立方体格子要素の表面との距離が初期立方体格子要素の一辺の長さの距離未満となるため、初期立方体格子要素を取囲む初期立方体格子要素にクラックがなければ、その他の初期立方体格子要素に発生したクラックの影響が自己に及ばないことが保証される。
【００１６】
本発明に係る３次元画像データの適応的かつ階層的な四面体格子構造表現生成プログラムは、前記再帰的分割手段は、該再帰的近傍探索手段が前記初期立方体格子要素を各々独立に、該初期立方体格子要素の影響領域内で再帰的に探索した前記局所特徴量の変化に基づいて、該初期立方体格子要素を各々独立に再帰的に２分割する。
【００１７】
従って、以上より初期立方体格子要素ごとに並列かつ高速に、クラックの生じない適応的かつ階層的な四面体格子構造表現を生成することができる。
【００１８】
本発明に係る３次元画像データの適応的かつ階層的な四面体格子構造表現生成装置は、入力された３次元画像ボリュームデータで表されている空間を参照するするために、該空間を初期立方体格子要素の集合に分割設定する初期設定手段と、前記初期設定手段が設定した前記各初期立方体格子要素をそれぞれ６つの同形の四面体格子に分割する初期分割手段と、前記初期分割手段が分割したある四面体格子について、該四面体格子の最長の辺の両端の格子点における局所特徴量の差を検知する局所特徴量検知手段と、前記局所特徴量の差をあらかじめ設定された近似精度と比較して探索する再帰的近傍探索手段と、前記局所特徴量の差が前記近似精度を満たさない場合には、該近似精度を満たすまで、前記四面体格子の最長の辺の中点で該四面体格子を２つの四面体格子に再帰的に２分割してゆく再帰的分割手段と、前記局所特徴量の差が前記近似精度を満たす場合には、近傍からの影響を確認するために、前記四面体格子の各辺を共有して隣接する各四面体格子の内部の局所特徴量の変化の大きさが、前記近似精度を満たすか否かを再帰的に確認する再帰的確認手段と、を備え、前記再帰的近傍探索手段が再帰的に探索した前記局所特徴量の変化に基づいて、四面体格子内の該局所特徴量の変化量が閾値以下になるまで、前記再帰的分割手段が前記四面体格子を再帰的に２分割することにより、前記コンピュータに、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させる。
【００１９】
本発明に係る３次元画像データの適応的かつ階層的な四面体格子構造表現生成方法は、入力された３次元画像ボリュームデータで表されている空間を参照するするために、該空間を初期立方体格子要素の集合に分割設定する初期設定手段と、局所特徴量の差をあらかじめ設定された近似精度と比較して探索する再帰的近傍探索手段と、前記局所特徴量の差が前記近似精度を満たさない場合には、該近似精度を満たすまで、四面体格子の最長の辺の中点で該四面体格子を２つの四面体格子に再帰的に２分割してゆく再帰的分割手段と、を備えたコンピュータを用いて、３次元画像ボリュームデータで表されている空間から、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させる方法であって、入力された３次元画像ボリュームデータで表されている空間を準備するステップと、入力された３次元画像ボリュームデータで表されている空間を参照するするために、該空間を初期立方体格子要素の集合に分割設定するステップと、前記初期設定手段が設定した前記各初期立方体格子要素をそれぞれ６つの同形の四面体格子に分割するステップと、四面体格子の最長の辺の両端の格子点における局所特徴量の差を検知するスッテプと、前記局所特徴量の差をあらかじめ設定された近似精度と比較して探索するステップと、前記局所特徴量の差が前記近似精度を満たさない場合には、該近似精度を満たすまで、前記四面体格子の最長の辺の中点で該四面体格子を２つの四面体格子に再帰的に２分割してゆくステップと、前記局所特徴量の差が前記近似精度を満たす場合には、近傍からの影響を確認するために、前記四面体格子の各辺を共有して隣接する各四面体格子の内部の局所特徴量の変化の大きさが、前記近似精度を満たすか否かを再帰的に確認するステップと、前記再帰的近傍探索手段が再帰的に探索した前記局所特徴量の変化に基づいて、
四面体格子内の該局所特徴量の変化量が閾値以下になるまで、前記再帰的分割手段が前記四面体格子を再帰的に２分割することにより、前記コンピュータに、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させるステップと、
を含む。
【００２０】
本明細書において、フィールドデータとは各格子点における局所特徴量と同義であり、一次微分や等値面の曲率のような局所特徴を表す任意の量をいう。以下本明細書において、上記局所特徴量をフィールドデータ又はフィールド値という。
【００２１】
また、以下本明細書において、上記３次元画像ボリュームデータを簡単に入力ボリュームデータと、上記初期立方体格子要素は初期格子という。
【発明の効果】
【００２２】
本発明は、入力ボリュームデータの四面体階層構造を自動的に構築するアダプティブ・グリッドの並列アルゴリズムを提案した。正確かつ効率的なボリュームモデルとして使うことができるこの四面体表現は、指定された任意の精度を必ず満たすという長所を持つ。
【００２３】
また本発明は、ボリューム近似において、クラックの生成を無効化するために、近傍の四面体から、分割するために使う情報を集るという再帰的近傍探索アルゴリズムも提案した。参照される近傍の境界から、本発明は、それぞれの格子要素の参照領域の限界を定義した。
【００２４】
この定義によって、それぞれの格子要素が、独立に再帰的に分割されることが可能となる。このことは、時間的空間的境界の中で、クラックを伴わない四面体階層構造が並列インプリメンテーションにより高速に構築することが可能となる。
【００２５】
更に、本発明の上記手法は、どのようなボリュームデータでも適応的にデータを圧縮するために用いることができる。例えば、上記手法は白黒濃淡画像、カラー画像、ＭＲ画像、距離画像、あるいは赤外線画像といったあらゆる画像データから得られたボリュームデータに対しても適用することができる。
【発明を実施するための最良の形態】
【００２６】
本発明の３次元画像ボリュームデータの適応的かつ階層的な四面体格子構造表現生成方法、プログラム及び装置は、次のアルゴリズムを構成に含む。
【００２７】
即ち、本発明に係るアルゴリズムは、入力された３次元画像ボリュームデータで表されている空間を参照するするために当該空間を初期立方体格子要素の集合に分割設定する初期設定手段と、各初期立方体格子要素をそれぞれ６つの同形の四面体格子に分割する初期分割手段と、四面体格子の最長の辺の両端の格子点における局所特徴量の差を検知する局所特徴量検知手段と、局所特徴量の差をあらかじめ設定された近似精度と比較して探索する再帰的近傍探索手段と、を含む。更に本発明に係るアルゴリズムは、局所特徴量の差が前記近似精度を満たさない場合には、当該近似精度を満たすまで四面体格子の最長の辺の中点で当該四面体格子を２つの四面体格子に再帰的に２分割してゆく再帰的分割手段、及び、局所特徴量の差が前記近似精度を満たす場合には、近傍からの影響を確認するために四面体格子の各辺を共有して隣接する各四面体格子の内部の局所特徴量の変化の大きさが、近似精度を満たすか否かを再帰的に確認する再帰的確認手段、をも含む。
【００２８】
本発明に係るアルゴリズムは、上記再帰的近傍探索手段が再帰的に探索した局所特徴量の変化に基づいて、四面体格子内の当該局所特徴量の変化量が閾値以下になるまで、再帰的分割手段が前記四面体格子を再帰的に２分割することにより、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させるアルゴリズムである。
【００２９】
以下詳説する上記アルゴリズムは、以下本明細書においてアダプティブ・グリッドと呼ばれ、適応的四面体格子構造を生成するアルゴリズムである。アダプティブ・グリッドは、２次元において、入力した距離画像から自由曲面を適応的に再構成する方法を提案したアダプティブ・メッシュを３次元に拡張したものである（例えば、非特許文献１２，１３参照。）。
【００３０】
本実施形態において、連続したボリュームが、視点の変化に関係なく一定の精度で近似されるまで、一次微分や、等値面の曲率のような局所特徴に応じて、グリッドの格子点を新たに生成しながら、四面体を再帰的に分割するというアダプティブ・グリッド生成法の並列アルゴリズムが提供される。また、各格子要素がそれぞれ独立に格子分割を行う過程で発生するクラックの形成を回避し、不連続性を保存する並列アルゴリズムが提供される。
【００３１】
このクラックを回避するアルゴリズムは、不連続性が確認されるまで再帰的に隣接した四面体を拡張しながら、不連続な情報を収集する。この再帰的な拡張によって達した境界は、格子要素のために３次元参照範囲を定義する。
【００３２】
ここで、参照範囲の局所定義は、それぞれの格子要素が独立に分割されることを許している。したがって、クラックのない四面体階層構造の並列化が、時間的空間的に可能となる。
【００３３】
（１）アダプティブ・グリッド
以下に、図１と図２に示すような上記アダプティブ・メッシュを３次元に拡張したアダプティブ・グリッドについて述べる。アダプティブ・メッシュは、視点の変化に不変な局所特徴に基づいて、距離画像から滑らかな自由曲面を再構成するアルゴリズムである。
【００３４】
まず、図１を用いてアダプティブ・メッシュの生成法を説明する（例えば、特許文献１、非特許文献１２，１３参照）。ステップ１：初期格子。図１（ａ）において、黒丸はノードを示す。ラインは、表示平面の相互に直交する（ｘ，ｙ）の座標線と並列関係であることを示している。ステップ２：初期三角形分割。図１（ｂ）において、各ノードで、奥行きｚ、垂線ｎ、主曲率ｋ１、ｋ２,及びその方向ｅ１，ｅ２と共に、表面形状を回復する。四角形でそれぞれ境界づけられた領域を、４つの隣接するノードの２つの三角片により、最初に概算する。ステップ３：再帰的２分割。図（ｃ）、（ｄ）において、両端の曲率に応じて、ラインに沿ってノードを増加し、高曲率の領域を、より細かい三角片で概算する。
【００３５】
次に示すは、Ｍａｕｂａｃｋによっても示された再帰的２分割のアルゴリズムである（非特許文献７参照）。これを用いて、クラックを伴わない並列適応的分割を示す。
【００３６】
（１−１）アルゴリズム
初期設定手段において初期格子は、ボリューム空間を構成するｘ、ｙ、ｚ軸にそってそれぞれInitCubeSize３の大きさの立方体セル要素として、一定の間隔で与えられる。ここでInitCubeSizeは、初期格子である立方体セルの一辺の長さである。各立方体セル要素によって分けられる３次元領域は、初期分割手段により図３に示すように、６つの四面体セルに分けられる。
【００３７】
その後再帰的分割手段により、局所特徴量検知手段が検知する局所特徴に応じて、ルートの四面体は、独立に再帰的に２分割される。この分割のプロセスは、内部のボリュームが、与えられた精度Acc-Threshに近似されるまで繰り返される。
【００３８】
初期格子のサイズは任意のサイズが与えれれる。グリッドの初期化は、最終的にできる四面体のサイズに無関係である。なぜなら、すべての不連続性が、以下に示すクラックを回避するアルゴリズムによって検出され、保存されるからである。
【００３９】
（１−２）再帰的四面体分割
階層表現を構築するアルゴリズムは、初期格子を段階的に分割することを基本としている。親四面体Ｔｐの二分割は、与えられた精度Acc-ThreshがＴｐの６つの辺のいずれかで満たされなかった時に行われる。
【００４０】
親四面体Ｔｐの二つの子四面体ＴｌとＴｒへの分割により、新しい格子点Ｍが生成される。Ｍとは、四面体における最も長い辺＝基辺Ｅ
（式１）
2005196505.tif 000003
の中点である。その後、Acc-Threshが、左右の子四面体ＴｌとＴｒでそれぞれ独立に再帰的に評価されることにより、四面体が再帰的に二分割されることになる。
【００４１】
（１−２−１）四面体の形状
四面体の再帰的二分割において、鏡面対称を含む３つの形状の四面体が登場する。図４に示すように、ＴＹＰＥ−Ｉ、ＴＹＰＥ−ＩＩ、ＴＹＰＥ−ＩＩＩは、それぞれ、レベル３Ｎ、３Ｎ＋１、３Ｎ＋２において、再帰的に生成される。
【００４２】
図５は、親四面体の頂点（Ｐ０、Ｐ１、Ｐ２、Ｐ３）と基辺の中点Ｍを用いて、子四面体ＴＹＰＥ−Ｉ、ＴＹＰＥ−ＩＩ、ＴＹＰＥ−ＩＩＩを一定の法則で再帰的に定義するものである。
【００４３】
図４は、レベル３Ｎの四面体ＴＹＰＥ−Ｉを３回分割した後のレベル３（Ｎ＋１）では、辺の長さが１／２、体積が１／８の同形状の四面体が生成されることを示したものである。
【００４４】
図６は、ＴＹＰＥ−Ｉ、ＴＹＰＥ−ＩＩ、ＴＹＰＥ−ＩＩＩの面の形が、二等辺三角形もしくは、直角三角形であることを示している。最長・最短の辺の比は、ＴＹＰＥ−Ｉは
（式２）、
2005196505.tif 000004
ＴＹＰＥ−ＩＩは
（式３）、
2005196505.tif 000005
ＴＹＰＥ−ＩＩＩは２である。
【００４５】
中点を使うこの四面体２分割は、このように等角度の要求を満たす。もう一つの長所は、与えられたボリューム変化の範囲のために、木がさらに近似のレベルを持っているので、さらに、ボリューム近似の連続したレベルが提供されることである。
【００４６】
（１−２−２）格子点の初期化
立方体セルを６つの四面体に分割する本発明の方法は、２つのオリジナリティーがある。一つは、初期立方体セルの６つの面が、図３（ａ）のように、隣の面と対角線を共有するので、片方の四面体だけ、分割を要求すればよいとうことである。二つ目は、立方体セルを四面体に分割する時に存在する４つの対角線は、どれを選んでも、最終的な四面体分割には影響しないということである。
【００４７】
図１７は、定義された４つの対角線の方向を示したものである。これらの方向は、立方体セル内の６つのルート四面体で共有される対角線の方向によって決まる。しかし、図１７は、４つのことなる最初の四面体分割が、３回分割した後では、同じ四面体分割した結果になるということも示している。
【００４８】
図１８は、初期立方体セルにおいて、４パターンが隣り合うことを示している。１／８のサイズのセルが同じパターンとされるそれぞれの組は対角線上に位置し、４つの組すべてが初期立方体セルの中央で一致する。ゆえに、全方向の影響は、最終的な結果には無関係となる。
【００４９】
（１−２−３）再帰的二分割
四面体の再帰的二分割のためのステップを、下記のコードに示す。
［コード１］
2005196505.tif 000006
【００５０】
それぞれの分割で、すべての四面体のサイズは、１／２になる。ゆえに、最大分割深度ｎｍａｘは、次の式で与えられる。
【数１】
2005196505.tif 000007
【００５１】
ここでInitCubeSizeは、初期格子である立方体セルの一辺の長さである。
【００５２】
（１−３）再帰的近傍探索
以下に、再帰的近傍探索手段及び再帰的確認手段について説明する。適応的分割における大きな問題は、それぞれの四面体が独立に分割された時にクラックが生じてしまうことがあるということである。
【００５３】
初期格子要素の近くに大きなフィールド値の変化がある場合、クラックが格子要素間の境界に沿って形成されることがある。このクラックは、大きくフィールド値が変化している面上で格子要素の一方だけが分割されることによって引き起こされる。
【００５４】
本発明では、隣接する四面体の間でクラックを防ぐために、突然のフィールドデータの変化が確認されるまで、３次元の参照領域を再帰的に拡大することによって、近傍から分割判定の情報をあつめるアルゴリズムを開発した。
【００５５】
再帰的２分割において、全ての四面体は、基辺の中点を用いて分割される。中点を挿入することは、基辺を共有する隣り合う四面体だけの分割に影響を及ぼす。
【００５６】
四面体Ｔｐの基辺Ｅのために、図１６（ａ）に示すように、本明細書においてdiamondとよぶＥを共有する四面体の集合によって、３次元影響領域RI(E)を定義する（例えば、非特許文献１０参照。）。
【００５７】
もしＥがレベル３Ｎで、立方体セル内の対角線ならば、RI(E)は、Ｅを共有する６つの四面体で構成され、形状は立方体セルとなる。与えられたエッジＥの両端点を
（式４）、
2005196505.tif 000008
立方体セルの一辺の長さをＬ，
（式４‘）、
2005196505.tif 000009
とすると、立方体セルの各頂点は次の様に計算できる。
（式４“）、
2005196505.tif 000010
【００５８】
もしＥが、隣り合う四面体セルにより共有される境界面上の対角線ならば、RI(E)は、４つの四面体で構成され、２つは、自身の立方体セルから、他の２つは、隣の立方体セルとなる。この時のdiamondの頂点は、次の様に計算できる。
（式５）、
2005196505.tif 000011
【００５９】
もしＥが、ｘ、ｙ、ｚ軸のいずれかに平行ならば、RI(E)は、Ｅを共有する隣り合う立方体セル内の８つの四面体から構成される。この時のdiamondの頂点は、次の様に計算できる。
（式６）、
2005196505.tif 000012
【００６０】
本発明では、影響領域RI(E)内の四面体Ｔｐで他の分割判定を付け加えた。もし、RI(E)内のどれか一つの四面体が、中点Ｍで分割されれば、他の四面体もまたＭで分割するというものである。このように、もし、与えられた精度が、領域RI(E)内のいずれかの四面体の一辺で満たされなかった場合、四面体Ｔｐは、中点Ｍで左右の四面体ＴｌとＴＲに分割される。
【００６１】
各格子要素Cb(ｉ,j,k)のために、本発明では、独立にルート四面体Rt[i]｜(0≦ｉ≦5)を処理する。最初に、基辺Ｅに沿って精度を評価する。もし、Ｅの精度が与えられた精度に達しなければ、近傍探索をせずに、すぐに四面体RI(E)を分割する。その理由は以下の２つである。
【００６２】
１）影響領域RI(E)内のＥによる拘束から、RI(E)内の全ての四面体は、Ｍにより分割される。これにより、もし、領域RI(E)内の一つの四面体内部にフィールド値の不連続性が確認されても領域RI(E)内には、クラックは発生しない。２）中点Ｍの挿入は、領域RI(E)内の分割にのみ影響する。領域RI(E)外の近傍四面体の分割には全く影響しない。一方で、格子要素Cb(ｉ,ｊ,k)の近傍から集められた分割判定により、分割が間違いないことだと確認できるまで、分割要求は延期される。
【００６３】
次に、影響領域RI(Eｉ)｜(１≦ｉ≦２)において、四面体ＴｌとＴｒのそれぞれの基辺を考える。その後、影響領域RI(E)の精度が、与えられた閾値に達しているかどうかを評価する。この評価の処理は、連続したレベルで四面体ＴｌとＴｒのそれぞれの基辺のために参照領域を再帰的に定義する。図１６（ｂ）は、立方体セルCb(ｉ,ｊ,k)内の６つのルート四面体を３回分割した後の影響領域RI(E)を２次元に平行投影したものである。これは、図１６（ｃ）に示すように立方体セルCb(ｉ,ｊ,k)の参照領域を再帰的に広げることになる。
【００６４】
もし、レベルｎで定義された基辺Ｅ（ｎ）に沿って再帰的近傍探索手段により近傍探索し、領域RI(E)内で精度が達した場合、もしくは、閾値を満たさなかった場合、分割の要求は、レベルｎとなる。その後、探索してきた全ての四面体の分割要求は、立方体セルCb(ｉ,ｊ,k)のルート四面体まで波及することになる。
【００６５】
一方、RR（Cb(ｉ,ｊ,k)）の拡張により許される影響領域RI(E(n))の再帰定義は、RI(E(n))のサイズが、１になるまで続く。この場合、RR（Cb(ｉ,ｊ,k)）によって分けられる近傍の領域内でフィールド値は、一定であるので、Cb(ｉ,ｊ,k)によってわけられた領域は、十分に６つのルート四面体で近似できることになる。RIのボリュームは、３回分割した後、２３の係数で減少する。
【００６６】
このように、参照領域RR（Cb(ｉ,ｊ,k)）は、再帰的に拡張される。図１６（ｄ）は、各レベルにおける影響領域RI(E(n))の再帰定義により拡張された参照領域RR（Cb(ｉ,ｊ,k)）を示したものである。
【００６７】
格子要素Cb(ｉ,ｊ,k)の境界から最も遠い境界RIへの距離ｄは、次式により与えられる。
【数２】
2005196505.tif 000013
【００６８】
数２において、ｋ＝[ｎ／３]であり、InitCubeSizeは、初期格子要素の一辺の長さである。
【００６９】
式（２）は、図１６（ｅ）に示すように、ｄｍａｘが、InitCubeSizeによって制限されることを意味している。したがって、図１６（ｃ）のように、各初期格子要素Cb(ｉ,ｊ,k)から、
（式７）
2005196505.tif 000014
・・・・・（＝１＋６＋８＊（１／６））＊（InitCubeSize）３
であり、ボリュームの参照領域RR（Cb(ｉ,ｊ,k)）を境界として定義することができた。
【００７０】
最大分割レベルｎｍａｘは、次式で与えられる。
【数３】
2005196505.tif 000015
【００７１】
参照領域の境界の定義は、各格子要素が独立に分割できることを可能としている。これは、クラックを生じない再帰的四面体分割の並列計算を時間的空間的に可能にしている。
【００７２】
これらのステップを、下記のコードにまとめる。
（コード２）
2005196505.tif 000016
【００７３】
次に、本発明に係るアルゴリズムにおいて用いられる精度について詳説する。
【００７４】
（２）精度
まず、図１９の様に、ｘ軸がＥｉに沿い、Ｅｉに沿ってフィールド値がｙ軸の方向の高さを表している２Ｄ空間Ｓの中で、四面体の全ての辺Ｅｉに沿って、フィールド値が変化すると考える。図１９では、B-splineという補間技術を用いて、2点Pl及びPｒ間のフィールド値の曲線を、３つのB-splineセグメント（ピンク塗り部分、緑塗り部分、赤塗り部分）とする。紫と黄色で色づけされたB-splineの基準点を、Pl及びPｒで定義された同等の面から算出されるPl及びPｒで定義された接触円と、Acc_threshで定義された角度θにより生成する。接触円の中心Ol及びOｒは、垂線
（式８）
2005196505.tif 000017
と、
（式９）
2005196505.tif 000018
の方向のPl及びPｒにおける曲率
（式１０）
2005196505.tif 000019
に基づき決定する。
【００７５】
Ｅｉに沿った連続したボリュームデータＣ１のフィールド値の変化は、線よりもむしろ曲線で描かれるべきである。多くの手法で簡易に使われる四面体内部のフィールド値の線形補間は、空間Ｓの中の点Ｐｌと点Ｐｒの間の線を同等に描く（例えば、非特許文献１０，１１参照。）。
【００７６】
Ｐｌと点Ｐｒは、空間ＳでＥｉの最後の点とされ、Ｄｉは、Ｐｌと点Ｐｒの間の３次元の距離である。Ｒｉは、Ｅｉに沿ったフィールド値の曲率の逆数である。そのような曲線は、B-splineなどの曲線補間技術により得ることができる。
【００７７】
本発明の実施形態では、曲線は、図１９のように描かれる両端点の等値面の法線と曲率によって定まる円に接触するということを使って計算している。本実施形態の正確な精度は、フィールド値の曲率の変化の比が、その線形近似に変わるものとして与えられ、全ての四面体の全ての辺Ｅｉに適用される。
【００７８】
上記精度は、次式で与えられる。
【数４】
2005196505.tif 000020
【００７９】
数４においてｍは、図７に描かれる単位円のｍ多角形近似と同等の正確さで決められる。ここで図７は、Ｒがアーク長で、Ｄがコード長である単位円のｍ多角形近似を表す。Acc_threshを、単位円のｍ多角形近似として示し、隣接する四面体の勾配ベクトル間の角度を抑制するAcc_thresh=(アーク長)／（コード長）=π／m
sin(π／m)を、同等の面の近似の隣接する三角形（片）間の角度を抑制するθ≦2π／mとして示す。この基準は、隣接した四面体の勾配ベクトル間の角度の抑制と同等である。
【００８０】
この正確な基準により、与えられた四面体Ｔｐの分割判定が次式で行われる。
【数５】
2005196505.tif 000021
【００８１】
本発明による上記階層的ボリューム・モデルは、入力データから得ることが簡単であり、また、任意の精度であらゆるボリュームデータにも近似することができる（例えば、非特許文献３，４，５参照。）。
【００８２】
本発明に係る３次元画像ボリュームデータの適応的かつ階層的な四面体格子構造表現生成方法は、上記アルゴリズムを用いて、３次元画像ボリュームデータで表されている空間から、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させる方法である。
【００８３】
本発明に係る３次元画像ボリュームデータの適応的かつ階層的な四面体格子構造表現生成プログラムは、上記アルゴリズムを用いて、３次元画像ボリュームデータで表されている空間から、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させるプログラムである。
【００８４】
本発明に係る３次元画像ボリュームデータの適応的かつ階層的な四面体格子構造表現生成装置は、上記アルゴリズムを用いて、３次元画像ボリュームデータで表されている空間から、３次元画像ボリュームデータの適応的かつ階層的な多重解像度の四面体格子構造表現を生成させる装置である。
【００８５】
本発明は、入力ボリュームデータの四面体階層構造を自動的に構築するアダプティブ・グリッドの並列アルゴリズムを提案した。正確かつ効率的なボリュームモデルとして使うことができるこの四面体表現は、指定された任意の精度を必ず満たすという長所を持つ。
【００８６】
本発明は、ボリューム近似において、クラックの生成を無効化するために、近傍の四面体から、分割するために使う情報を集るという再帰的近傍探索アルゴリズムもまた提案した。参照される近傍の境界から、本発明は、それぞれの格子要素の参照領域の限界を定義した。
【００８７】
この定義によって、それぞれの格子要素が、独立に再帰的に分割されることが可能となる。このことは、時間的空間的境界の中で、クラックを伴わない四面体階層構造が並列インプリメンテーションにより構築することが可能であるということである。
【００８８】
また本発明において、３次元画像ボリュームデータは画像列であれば特に限定されることはなく、その画像は白黒濃淡画像でも、ＭＲ画像でも、距離画像でも、赤外線画像でも、又はその他の画像でもよい。本発明は、上記何れの３次元画像ボリュームデータからでも、１次微分と２次微分に適応的に３次元画像ボリュームデータを圧縮した階層的、即ち多重解像度の四面体格子構造表現／モデルを自動生成することができる。これは、ボクセル値、即ちある１枚の画像の画素値、の１次微分と２次微分によって適応的に再帰的２分割を行なうため、各画素値が物理的に何を表しているかは問わないからである。従って本発明のアルゴリズムは、汎用的な３次元画像ボリュームデータの圧縮方法ということができる。
【００８９】
その他、本発明は、その主旨を逸脱しない範囲で当業者の知識に基づき種々の改良、修正、変更を加えた態様で実施できるものである。
【００９０】
以下に実施例を示す。実施例では実験環境として、ＣＰＵ−２、８ＧＨｚ、ｍｅｍｏｒｙ−２ＧＢのＰＣを、プラグラム言語にＣ＋＋を、表示にはＶＴＫ(Visualization ToolKit)を使用した。
【実施例１】
【００９１】
本実施例１では、６７×１２９×６７のサイズの椅子のボリュームデータで、上記アルゴリズムの実験を試みた。初期格子サイズは１６Ｖｏｘｅｌである。また、データの最大ボリューム値は２５５である。
【００９２】
実施例１の椅子のデータを図８と、図９に、ｘ−ｙ、ｙ−ｚ平面に平行投影した結果を図１０と、図１１に示す。表１に、レベル３、６、９、１２における圧縮率を示す。
【表１】
2005196505.tif 000022
【実施例２】
【００９３】
本実施例２では、３２０×３２０×３４のサイズのロブスターのボリュームデータで、上記アルゴリズムの実験を試みた。初期格子サイズは３２Ｖｏｘｅｌである。データの最大ボリューム値は、上記実施例１と同様２５５である。
【００９４】
本実施例２で実験したロブスターのデータを図１２に、レベル３、６、９の結果をｘ一ｙ、ｙ−ｚ、ｚ−ｘ平面に平行投影した結果を図１３、図１４、図１５に示す。表２にレベル３、６、９、１２における圧縮率を示す。
【表２】
2005196505.tif 000023
【００９５】
上記の結果が、複雑なボリュームデータの表現が、適応的にサンプリングされたボリュームデータから、効果的に正確に可視化されたことを示している。
【図面の簡単な説明】
【００９６】
【図１】アダプティブ・メッシュの生成法の流れを説明する図。
【図２】（ａ）人間の顔を表すアダプティブ・メッシュを表す図。（ｂ）図２（ａ）の平面投影図。
【図３】立体セルの初期四面体分割の流れを説明する図。
【図４】Ｔｙｐｅ−Ｉ、Ｔｙｐｅ−ＩＩ、Ｔｙｐｅ−ＩＩＩのプリミティブの立方体の再帰的分割の流れを説明する図。
【図５】３つのプリミティブに関するＴｌ及びＴｒの再帰的定義を説明する図。
【図６】３つの四面体プリミティブを表す図。
【図７】Ｒがアーク長で、Ｄがコード長である単位円のｍ多角形近似を説明する図。
【図８】椅子の入力データを表す図。
【図９】椅子の立体描画図。
【図１０】椅子のｘ−ｙ平面図。
【図１１】椅子のｙ−ｚ平面図。
【図１２】ロブスターの入力データを表す図。
【図１３】レベル３のロブスターのｘ−ｙ、ｙ−ｚ及びｚ−ｘ平面図。
【図１４】レベル６のロブスターのｘ−ｙ、ｙ−ｚ及びｚ−ｘ平面図。
【図１５】レベル９のロブスターのｘ−ｙ、ｙ−ｚ及びｚ−ｘ平面図。
【図１６】Cb(i,j,k)の２分割において考察される隣接する領域を表す一連の図。（ａ）基辺Eの影響領域RI(E)を表す図。（ｂ）RI(Cb(I,j,k))の２次元投影図。（ｃ）Cb(i,j,k)の３次元参照領域RRを表す図。（ｄ）各レベルn(=3N+P)を、（N-P）と示す、各再帰レベルでの参照領域RR(Cb(I,j,k))の再帰拡張の２次元投影図。（ｅ）dmax≦InitCubeSizeである上限領域を表す図。
【図１７】対角線の異なる４種類の最初の四面体分割が、３回分割の１サイクル後に、同じ四面体分割した結果になることを説明する流れ図。
【図１８】より細かいレベルで四面体分割されたセルの近接する４パターンを表す図。
【図１９】B-splineという補間技術により、２点Pl及びPｒ間のフィールド値の曲線を、３つのB-splineセグメント（ピンク塗り部分、緑塗り部分、赤塗り部分）に分ける様子を説明する図。
【図１】
2005196505.tif 000024
【図２】
2005196505.tif 000025
【図３】
2005196505.tif 000026
【図４】
2005196505.tif 000027
【図５】
2005196505.tif 000028
【図６】
2005196505.tif 000029
【図７】
2005196505.tif 000030
【図８】
2005196505.tif 000031
【図９】
2005196505.tif 000032
【図１０】
2005196505.tif 000033
【図１１】
2005196505.tif 000034
【図１２】
2005196505.tif 000035
【図１３】
2005196505.tif 000036
【図１４】
2005196505.tif 000037
【図１５】
2005196505.tif 000038
【図１６】
2005196505.tif 000039
【図１７】
2005196505.tif 000040
【図１８】
2005196505.tif 000041
【図１９】
2005196505.tif 000042