(57)【要約】【課題】インデックス付けを伴うボリュームデータの等値面生成において、インデックス付けに画像合成処理技術を用いて一気にインデックス付けを行うことで、インデックス付けにかかる処理時間を大幅に減少させる等値面生成方法を提供する。【解決手段】各単位格子に対するインデックス付けは、単位格子を挟んで隣り合うスライス画像を２枚用意し、スライス画像から単位格子に対するインデックス付けに必要な枚数の閾値判定用画像を生成し、閾値判定用画像の各ピクセルの値を閾値と比較し、比較結果値を各ピクセルに与えた比較結果画像を合成することで行われる。生成された合成画像の各ピクセルの値は、それぞれ単位格子のインデックスとして利用でき、これを用いて等値面が生成される。【選択図】図３
2005038182.tif 000002
【特許請求の範囲】
【請求項１】
インデックス付けを伴うボリュームデータの等値面生成方法において、各単位格子に対するインデックス付けには、
前記単位格子の少なくとも一部が含まれる、隣り合うスライス画像を少なくとも２枚用意する過程と、
前記２枚のスライス画像から、インデックス付けに必要な枚数の閾値判定用画像を生成する過程と、
それぞれの前記閾値判定用画像の各ピクセルの値を所定の閾値と比較する過程と、
前記比較する過程により得られる比較結果値を対応する各ピクセルに与えたそれぞれの比較結果画像を生成する過程と、
前記比較結果画像を画像合成し、生成された合成画像の各ピクセルの値をそれぞれ各単位格子のインデックスとする１枚の合成画像を生成する過程と、
が含まれることを特徴とするボリュームデータの等値面生成方法。
【請求項２】
インデックス付けを伴うボリュームデータの等値面生成方法において、各単位格子に対するインデックス付けには、
前記単位格子の少なくとも一部が含まれる、隣り合うスライス画像を少なくとも２枚用意する過程と、
それぞれの前記スライス画像の各ピクセルの値を所定の閾値と比較する過程と、
前記比較する過程により得られる比較結果値を対応する各ピクセルに与えたそれぞれの比較結果画像を生成する過程と、
前記比較結果画像から、インデックス付けに必要な枚数のインデックス付け用画像を生成する過程と、
前記インデックス付け用画像を画像合成し、生成された合成画像の各ピクセルの値をそれぞれ各単位格子のインデックスとする１枚の合成画像を生成する過程と、
が含まれることを特徴とするボリュームデータの等値面生成方法。
【請求項３】
請求項１又は請求項２に記載の等値面生成方法において、前記比較結果値は、前記所定の閾値よりも小さければゼロを、大きければ所定値を与えることで生成されることを特徴とするボリュームデータの等値面生成方法。
【請求項４】
請求項１に記載の等値面生成方法において、前記インデックス付けに必要な枚数の閾値判定用画像を生成する過程は、前記スライス画像のピクセルの参照方法を変化させることにより行われることを特徴とするボリュームデータの等値面生成方法。
【請求項５】
請求項１に記載の等値面生成方法において、前記単位格子は、８個の頂点からなる立方格子からなり、前記閾値判定用画像は、前記スライス画像をＸ軸方向、Ｙ軸方向、ＸＹ軸方向に単位格子分それぞれ移動させることで、８枚生成されることを特徴とするボリュームデータの等値面生成方法。
【請求項６】
請求項５に記載の等値面生成方法において、
前記単位格子は、ｖ１〜ｖ８の８個の頂点からなる立方格子からなり、前記隣り合うスライス画像は、頂点ｖ１〜ｖ４が含まれる第１スライス画像と、頂点ｖ５〜ｖ８が含まれる第２スライス画像とからなり、
前記閾値判定用画像を生成する過程は、頂点ｖ１の位置に頂点ｖ２が、頂点ｖ１の位置に頂点ｖ３が、頂点ｖ１の位置に頂点ｖ４がそれぞれ来るように前記第１スライス画像を移動することで、前記第１スライス画像から４枚の閾値判定用画像を生成すると共に、頂点ｖ５の位置に頂点ｖ６が、頂点ｖ５の位置に頂点ｖ７が、頂点ｖ５の位置に頂点ｖ８がそれぞれ来るように前記第２スライス画像を移動することで、前記第２スライス画像から４枚の閾値判定用画像を生成する過程からなることを特徴とするボリュームデータの等値面生成方法。
【請求項７】
請求項１乃至請求項６の何れかに記載の等値面生成方法において、前記インデックス付けを伴う等値面生成方法には、マーチングキューブ法を用いた等値面生成方法が含まれることを特徴とするボリュームデータの等値面生成方法。
【請求項８】
請求項１乃至請求項７の何れかに記載の等値面生成方法において、前記所定の閾値との比較は、アルファテストにより行うことを特徴とするボリュームデータの等値面生成方法。
【請求項９】
請求項１乃至請求項７の何れかに記載の等値面生成方法において、前記所定の閾値との比較は、フラグメントプログラムにより行われることを特徴とするボリュームデータの等値面生成方法。
【請求項１０】
請求項１乃至請求項９の何れかに記載の等値面生成方法において、前記スライス画像が３枚以上用意され、前記生成される合成画像が３次元画像であることを特徴とするボリュームデータの等値面生成方法。
【請求項１１】
請求項１乃至請求項１０の何れかに記載の等値面生成方法において、前記閾値判定用画像は、仮想的に作成されることを特徴とするボリュームデータの等値面生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はインデックス付けを伴うボリュームデータの等値面生成方法に関し、特に、インデックス付けを、画像合成処理技術を用いてまとめて行う等値面生成方法に関する。
【背景技術】
【０００２】
ＣＴ画像や各種物理量分布のシミュレーション結果等で得られるボリュームデータからの物体再構成の手法は数多く提案されている。その中には、単位格子にインデックスを付し、そのインデックスに対応する三角形面等のポリゴンを用いて等値面を生成する手法がある。代表的なインデックス付けを伴う等値面生成方法には、マーチングキューブ法が挙げられる。マーチングキューブ法は、８個の頂点を有する単位立方格子ごとに等値面を構成するポリゴンを生成し、シェーディング手法を用いて可視化するというものである。マーチングキューブ法に関しては、下記の非特許文献１に詳細に説明されているが、本明細書でも図１及び図２を用いて簡単に説明する。
【０００３】
図１は、マーチングキューブ法で用いる８個の頂点ｖ１〜ｖ８を有する単位立方格子を示すものである。等値面は、頂点と閾値とを比べることによって与えられる、２つの領域を隔てる境界面として求めることができる。まず、所定の閾値とすべての頂点の値（色値、輝度値等）とを比較して、閾値よりも大きいものと閾値よりも小さいものに分けてインデックス付けを行う。例えば図１に示すように、頂点ｖ１〜ｖ８の各頂点において、ボクセル値が閾値よりも大きい場合には１を、小さい場合には０を付し、これをｖ８が最上位ビットとなるように、ｖ８，ｖ７，ｖ６，ｖ５，ｖ４，ｖ３，ｖ２，ｖ１という順番に並べることで、インデックスを生成する。即ち、インデックスを８ｂｉｔで表わす。
【０００４】
単位立方格子内に閾値よりも大きい頂点と小さい頂点の両方が存在すると、その立方格子は等値面と交差すると判定される。等値面を構成するポリゴンの頂点は格子上に存在し、色情報等のボクセルの値を用いた線形補間によって求められる。そして、このようにポリゴンを決定して等値面を生成していくが、８個の頂点の組み合わせは２５６通りあるため、立方格子ごとに２５６通りのうちのどのパターンに当てはまるかを判別するのは大変である。したがって、マーチングキューブ法では、パターンを減らしていくことを考える。即ち、白黒反転させても生成されるポリゴンは同じであることや、あるパターンを他のパターンの組み合わせで代用すること等を考えて、最終的に図２に示す１５のパターンに減らすことができる。このように、マーチングキューブ法は、それぞれの単位立方格子にインデックスを付して、予め求めておいたポリゴンの生成パターンに当てはめて等値面を生成し、すべてのポリゴンを組み合わせて最終的なボリュームデータの等値面を生成するものである。
【０００５】
なお、マーチングキューブ法を応用した種々の手法が提案されており、単位立方格子を５個や６個の四面体に分割するもの等も存在する。さらに、三角柱状格子を１単位としてインデックス付けに用いるものも等も考え得る。
【０００６】
【非特許文献１】Ｗｉｌｌｉａｍ  Ｅ．  Ｌｏｒｅｎｓｅｎ及びＨａｒｖｅｙ  Ｅ．  Ｃｌｉｎｅ著，  「ＭＡＲＣＨＩＮＧ  ＣＵＢＥＳ：Ａ  ＨＩＧＨ  ＲＥＳＯＬＵＴＩＯＮ  ３Ｄ  ＳＵＲＦＡＣＥ  ＣＯＮＳＴＲＵＣＴＩＯＮ  ＡＬＧＯＲＩＴＨＭ」，  Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ，  Ｖｏｌｕｍｅ  ２１，  Ｎｕｍｂｅｒ  ４，  １９８７年７月，  ｐ．ｐ．１６３−１６９
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述のようなマーチングキューブ法等のインデックス付けを伴う等値面生成方法では、単位格子ごとにインデックスを１つずつ付していかなければならないため、処理時間が非常にかかるものであった。具体的には、１つの単位格子に対して、各頂点のボクセル値を順番に所定の閾値と比較し、その大小によってインデックスを生成していくことを、すべての単位格子に対して順番に１つずつ行っていかなければならなかったため、ＣＰＵ等で行う計算処理工程が非常に多くなってしまっており、処理時間がかかっていた。このように、インデックス付けを伴う等値面生成方法においては、インデックス付けの工程が最も処理時間がかかる部分であり、処理時間を短縮する上でボトルネックとなる部分であった。
【０００８】
本発明は、斯かる実情に鑑み、インデックス付けを伴うボリュームデータの等値面生成に関し、インデックス付けに画像合成処理技術を用いて、一度に複数のインデックス付けを一気に行うことで、インデックス付けにかかる処理時間を大幅に減少させた等値面生成方法を提供しようとするものである。
【課題を解決するための手段】
【０００９】
上述した本発明の目的を達成するために、本発明によるインデックス付けを伴うボリュームデータの等値面生成方法における各単位格子に対するインデックス付けには、前記単位格子の少なくとも一部が含まれる、隣り合うスライス画像を少なくとも２枚用意する過程と、前記２枚のスライス画像から、インデックス付けに必要な枚数の閾値判定用画像を生成する過程と、それぞれの前記閾値判定用画像の各ピクセルの値を所定の閾値と比較する過程と、前記比較する過程により得られる比較結果値を対応する各ピクセルに与えたそれぞれの比較結果画像を生成する過程と、前記比較結果画像を画像合成し、生成された合成画像の各ピクセルの値をそれぞれ各単位格子のインデックスとする１枚の合成画像を生成する過程とが含まれる。
【００１０】
また、先にそれぞれの前記スライス画像の各ピクセルの値を所定の閾値と比較する過程を行った後に、前記比較する過程により得られる比較結果値を対応する各ピクセルに与えたそれぞれの比較結果画像を生成する過程と、前記比較結果画像から、インデックス付けに必要な枚数のインデックス付け用画像を生成する過程と、前記インデックス付け用画像を画像合成し、生成された合成画像の各ピクセルの値をそれぞれ各単位格子のインデックスとする１枚の合成画像を生成する過程とを行っても良い。
【００１１】
ここで、比較結果値は、前記所定の閾値よりも小さければゼロを、大きければ所定値を与えることで生成されれば良い。
【００１２】
また、インデックス付けに必要な枚数の閾値判定用画像を生成する過程は、前記スライス画像のピクセルの参照方法を変化させることにより行われても良い。
【００１３】
また、単位格子は、８個の頂点からなる立方格子からなり、前記閾値判定用画像は、前記スライス画像をＸ軸方向、Ｙ軸方向、ＸＹ軸方向に単位格子分それぞれ移動させることで、８枚生成されても良い。
【００１４】
さらに、単位格子は、ｖ１〜ｖ８の８個の頂点からなる立方格子からなり、前記隣り合うスライス画像は、頂点ｖ１〜ｖ４が含まれる第１スライス画像と、頂点ｖ５〜ｖ８が含まれる第２スライス画像とからなり、前記閾値判定用画像を生成する過程は、頂点ｖ１の位置に頂点ｖ２が、頂点ｖ１の位置に頂点ｖ３が、頂点ｖ１の位置に頂点ｖ４がそれぞれ来るように前記第１スライス画像を移動することで、前記第１スライス画像から４枚の閾値判定用画像を生成すると共に、頂点ｖ５の位置に頂点ｖ６が、頂点ｖ５の位置に頂点ｖ７が、頂点ｖ５の位置に頂点ｖ８がそれぞれ来るように前記第２スライス画像を移動することで、前記第２スライス画像から４枚の閾値判定用画像を生成する過程からなるものでも良い。
【００１５】
ここで、インデックス付けを伴う等値面生成方法には、マーチングキューブ法を用いた等値面生成方法が含まれても良い。
【００１６】
また、所定の閾値との比較は、アルファテストやフラグメントプログラムにより行われれば良い。
【００１７】
さらに、スライス画像が３枚以上用意され、前記生成される合成画像が３次元画像であっても良い。
【００１８】
また、閾値判定用画像は、仮想的に作成されても良い。
【発明の効果】
【００１９】
本発明のインデックス付けを伴うボリュームデータの等値面生成方法によれば、処理時間を短くする上でボトルネックとなっていたインデックス付けの工程を一度に処理できるので、非常に高速に処理可能となるため、高速に等値面が生成可能となるという効果が得られる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明を実施するための最良の形態を図示例と共に説明する。なお、以下ではマーチングキューブ法を基に、単位格子としては基本的な構成である８個の頂点を持つ単位立方格子に対するインデックス付けについて主に説明するが、本発明はこれに限定されず、インデックス付けを伴う等値面生成方法であれば、マーチングキューブ法によるインデックス付けに限らず、また、頂点の数も８個に限らず、種々の形態が考えられる。即ち、本発明は単位格子の頂点の数を画像入力数として、画像合成処理により合成可能なものであれば良い。
【００２１】
本発明による等値面生成方法におけるインデックス付けでは、１つ１つの単位格子に対して１個ずつインデックスを生成していくのではなく、その処理を画像合成処理に置き換えて、一度にインデックスを生成するようにしている。具体的には、例えばマーチングキューブ法において、ある１つの単位立方格子を考えた場合、その立方格子の８個の頂点に対しては８個の値が関連付けられており、これらを加算することによりインデックスを生成している。これは、１ピクセルに対して８つの色入力がある場合の混色と状況が同じである。即ち、８枚の画像をブレンドし１枚の画像を得る画像処理に置き換えることができる。したがって、合成された１枚の画像の各ピクセルの値を、各単位格子のインデックスとすることが可能となる。このように処理することにより、インデックス付けは単位格子ごとに行われるのではなく、単位格子が複数含まれる一対のスライス画像単位で行うことが可能となる。なお、ここで言うスライス画像とは、ＣＴ画像や各種物理量分布のシミュレーション結果等で得られる、物体の断面画像を言う。したがって、スライス画像に含まれる単位格子すべてのインデックスが一気に生成可能となるのである。以下により具体的にその過程を説明する。
【００２２】
図３は、本発明による等値面生成方法におけるインデックス付けの工程を説明するためのフローチャートである。先ず、ボリュームデータに対して、スライス画像を用意する（ステップ３０１）。このステップでは、具体的には、図４に示すように、単位格子１を挟むように隣り合う２枚のスライス画像２，３を用意する。第１スライス画像２には、単位立方格子１の頂点ｖ１〜ｖ４で構成される面が含まれ、第２スライス画像３には、単位立方格子１の頂点ｖ５〜ｖ８で構成される面が含まれる。
【００２３】
次に、閾値判定用画像を生成する（ステップ３０２）。１枚のスライス画像から４枚の閾値判定用画像が生成されることを、図５を用いて説明する。このステップでは、具体的には、スライス画像をＸ軸方向、Ｙ軸方向、ＸＹ軸方向に単位格子分それぞれ移動させることで、４枚の閾値判定用画像を生成する。これを第１スライス画像２、第２スライス画像３それぞれに対して行うことで、合計８枚の閾値判定用画像が生成される。具体的には、頂点ｖ１の位置に頂点ｖ２が、頂点ｖ１の位置に頂点ｖ３が、頂点ｖ１の位置に頂点ｖ４がそれぞれ来るように第１スライス画像２を移動することで、第１スライス画像から４枚の閾値判定用画像を生成すると共に、頂点ｖ５の位置に頂点ｖ６が、頂点ｖ５の位置に頂点ｖ７が、頂点ｖ５の位置に頂点ｖ８がそれぞれ来るように第２スライス画像を移動することで、第２スライス画像から４枚の閾値判定用画像を生成する。なお、閾値判定用画像の生成は、上述の例には限定されず、例えばスライス画像のピクセルの参照方法を変化させることで、複数の必要な枚数の閾値判定用画像を生成するようにしても良い。なお、これらの閾値判定用画像は、実際にフレームバッファ上等に生成されず、内部で仮想的に作成されても勿論構わない。
【００２４】
そして、生成されるこれらの閾値判定用画像の各ピクセルの値を、所定の閾値と比較し、比較結果画像を生成する（ステップ３０３）。各ピクセルの値を所定の閾値と比較し、例えば各頂点に対して２ビットでインデックス付けを行う場合には、所定の閾値よりも大きい値のピクセルには「１」を、小さい値のピクセルには「０」というような比較結果値を与えた比較結果画像を生成する。これを、各閾値判定用画像の各ピクセルに対して行う。具体的には、アルファテストを用いて比較を行えば良い。これは、フラグメントプラグラム等で実行しても勿論構わない。なお、ここで言うアルファテストとは、物体の不透明の度合を検査するものである。
【００２５】
なお、先にスライス画像に対してその各ピクセルの値を所定の閾値と比較し、比較結果値を求めた後にその値を与えた比較結果画像を生成し、それを移動させて８枚の画像（ここではインデックス付け用画像）を生成するようにしても良い。
【００２６】
その後、このようにして生成した比較結果画像を画像合成する（ステップ３０４）。合成画像の、あるピクセルに対応する単位格子の頂点ｖ１〜ｖ８の比較結果が、例えばｖ１が「０」、ｖ２が「１」、ｖ３が「０」、ｖ４が「１」、ｖ５が「１」、ｖ６が「１」、ｖ７が「０」、ｖ８が「０」であった場合、合成後の画像の対応する位置のピクセルの値はｖ８を最上位ビットとして、「００１１１０１０」という８ビットデータが生成される。
【００２７】
なお、例えば１６ビットでインデックス付けを行う場合、閾値よりも高いときに、ｖ１には「０ｘ１」を、ｖ２には「０ｘ２」を、ｖ３には「０ｘ４」を、ｖ４には「０ｘ８」を、ｖ５には「０ｘ１０」を、ｖ６には「０ｘ２０」を、ｖ７には「０ｘ４０」を、ｖ８には「０ｘ８０」を、それぞれ与えるようにすれば良い。この場合、上記の例と同様に、ｖ２，ｖ４，ｖ５，ｖ６が閾値よりも高いときには、合成後の画像の対応する位置のピクセルの値は、「０ｘ３Ａ」となる。
【００２８】
このように、８枚の閾値判定用画像から、生成された比較結果値が与えられた画像の合成画像が生成されることで、結果的にスライス画像に含まれるすべての単位格子に対するインデックス付けが終了する（ステップ３０５）。生成された１枚の合成画像の各ピクセルの値は、それぞれ各単位格子のインデックスに対応する。このように、一対のスライス画像単位で、１枚の合成画像をすべてのボリュームデータに対して生成していくことで、すべての単位格子に対するインデックス付けが完了する。
【００２９】
本発明の等値面生成方法によれば、単位格子に対するインデックス付けを、画像合成処理手順を用いて行うことが可能となる。したがって、本発明では、１つの命令で複数のデータを扱う処理方式であるＳＩＭＤプロセッサ等を用いることで、スライス画像単位で一度に多くのインデックスを生成可能となる。
【００３０】
本発明は、ＳＩＭＤプロセッサとして、例えばＤｉｒｅｃｔＸ８世代のＮＶＩＤＩＡ社のＧｅＦｏｒｃｅ３／４（ＧｅＦｏｒｃｅはＮＶＩＤＩＡ社の登録商標）やＡＴＩ社のＲａｄｅｏｎ等のＧＰＵが利用可能である。このようなＧＰＵを用いることで、単位格子ごとに個々にインデックス付けを行っていた工程が、画像としてスライス画像単位で一気に効率良く行えるようになる。
【００３１】
なお、上記の例では隣り合うスライス画像を２枚用意する例を説明したが、本発明はこれに限定されず、より多くのスライス画像を一度に用いるようにすることも可能である。即ち、上述の例では、一対のスライス画像を用いて、その間に挟まれる単位格子のインデックスを、１枚に合成された２次元画像で表わすようにしたが、これを、３枚以上の複数のスライス画像を用いて、閾値判定用画像を３次元画像で作成するようにし、合成画像も３次元画像で生成するようにする。これにより、最終的に生成される３次元の合成画像の各ボクセルの値が、各単位格子のインデックスに対応することになる。したがって、スライス画像単位ではなく、ボリュームデータに対して一気にすべてのインデックスを生成することも可能となる。
【００３２】
なお、本発明のインデックス付けを伴うボリュームデータの等値面生成方法は、上述の図示例にのみ限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加え得ることは勿論である。
【図面の簡単な説明】
【００３３】
【図１】図１は、マーチングキューブ法で用いる８個の頂点ｖ１〜ｖ８を有する単位立方格子を説明するための図である。
【図２】図２は、マーチングキューブ法による１５のパターンのポリゴンを説明するための図である。
【図３】図３は、本発明の等値面生成方法におけるインデックス付けの工程を説明するための図である。
【図４】図４は、本発明の等値面生成方法で用いられる、単位格子１を挟むように隣り合う２枚のスライス画像を説明するための概念図である。
【図５】図５は、本発明の等値面生成方法で用いられる閾値判定用画像を複数生成する方法を説明するための概念図である。
【符号の説明】
【００３４】
１    単位格子
２，３    スライス画像
【図１】
2005038182.tif 000003
【図２】
2005038182.tif 000004
【図３】
2005038182.tif 000005
【図４】
2005038182.tif 000006
【図５】
2005038182.tif 000007