適応最大強度投影レイキャスティングの方法及びシステム
【課題】適応データ表現、レイキャスティング、及びデータ補間技術を用いてボリュームデータセットをレンダリングする方法及びシステムを提供する。
【解決手段】適応MIPレイキャスティングシステムは、最初に3Dデータセットを複数のサブボリュームにフラグメント化してオクトリデータ構造を構成し、各サブボリュームは、オクトリデータ構造の1つのノードに付随している。システムは、次に2D画像平面を確立し、各々がサブボリュームの部分集合と適応して相互作用する複数のレイを3Dデータセットに向けて選択的に放出し、レイ経路に沿う最大データ値を識別する。最大データ値は、次に2D画像平面上でピクセル値に変換する。最後に、システムは、ピクセル値がレイキャスティングによって発生されなかった位置のピクセル値を補間し、それによって3Dデータセットの2D画像を発生させる。
【解決手段】適応MIPレイキャスティングシステムは、最初に3Dデータセットを複数のサブボリュームにフラグメント化してオクトリデータ構造を構成し、各サブボリュームは、オクトリデータ構造の1つのノードに付随している。システムは、次に2D画像平面を確立し、各々がサブボリュームの部分集合と適応して相互作用する複数のレイを3Dデータセットに向けて選択的に放出し、レイ経路に沿う最大データ値を識別する。最大データ値は、次に2D画像平面上でピクセル値に変換する。最後に、システムは、ピクセル値がレイキャスティングによって発生されなかった位置のピクセル値を補間し、それによって3Dデータセットの2D画像を発生させる。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、一般的に、ボリュームデータレンダリングの分野に関するものであり、より詳細には、適応データ表現、レイキャスティング、及びデータ補間技術を用いてボリュームデータセットをレンダリングする方法及びシステムに関する。
【背景技術】
【0002】
3Dオブジェクト及び2D画像の内部構造の可視化は、コンピュータグラフィックの分野内の重要な話題であり、医学、地球科学、製造、及び薬物発見を含む多くの産業に応用されている。
【0003】
例えば、CTスキャナは、異なる器官、例えば心臓を含む患者の身体の数百又は数千の平行2D画像スライスを生成することができ、各スライスは、データ値の2Dアレイを含み、各データ値は、特定の部位での身体のスカラー属性、例えば密度を表している。全てのスライスを互いに積み重ねて、心臓が埋め込まれた患者の身体の画像ボリューム又はボリュームデータセットを形成する。心臓の3D構造特性を示す2D画像は、心血管疾患の診断における重要な助けになる。
【0004】
別の例として、石油業界では、地震学的撮像技術を用いて地球内の3D領域の3D画像ボリュームを作り出している。断層又は岩塩ドームのような一部の重要な地質構造は、その領域内に埋め込まれている場合があり、必ずしも領域の表面上とは限らない。同様に、これらの構造の3D特性を完全に示す2D画像は、石油生産を増す上で極めて重要である。
【0005】
最大強度投影(MIP)レイキャスティングは、3D画像ボリュームによって表された中実領域の内部を2D画像平面上、例えばコンピュータモニタ上に可視化するために開発された技術である。一般的に、複数のレイが2D放射面から画像ボリューム内に投射され、各レイキャスティングは、それぞれのレイ経路に沿った画像ボリューム内のボクセルでの最大データ値(例えば、強度)を識別し、それを所定の画面転送機能を通じて2D画像平面上のピクセルでの画像値の中に転送することを担っている。画像値は、レイ経路が遭遇した画像ボリューム内に埋め込まれたオブジェクトの3D特性、例えばそれらの形状及び向きを示している。2D画像平面上のピクセルに付随する画像値は、コンピュータモニタ上でレンダリングすることができる画像を形成する。
【0006】
上述のCTの例に戻ると、医師がいずれかの方向に画像ボリュームを遮ることによって心臓の2D画像スライスを任意に作り出すことができるとしても、どの単一の画像スライスも心臓の表面全体を可視化することはできない。これとは対照的に、CT画像ボリュームのMIPレイキャスティングを通じて作り出した2D画像は、心臓の3D特性を容易に示すことができ、これは、多くの種類の心血管疾患診断において非常に重要である。同様に、石油探査においては、3D地震データのMIPレイキャスティングは、石油技術者が潜在的な油田である領域の地下地質構造の3D特性をより正確に判断して石油生産を大幅に増すことを助けることができる。
【0007】
MIPレイキャスティングは、多くの重要な分野で重要な役割を果たすとしても、MIPレイキャスティング技術の幅広い展開を保証するために克服する必要があるいくつかの技術的課題が存在する。第1に、MIPレイキャスティングは、計算的に高価な処理である。3Dターゲットの3D特性を捕捉することができる高品質2D画像を生成するためには、MIPレイキャスティングでは、大きな3Dデータセットを処理する必要があり、これは、通常は多数の計算を意味する。例えば、5123ボクセルの一般的な3Dデータセットに対して、従来のMIPレイキャスティングアルゴリズムを用いて5122ピクセルの2D画像を生成するのに少なくとも1億4000万回の計算が必要である。
【0008】
更に、多くの用途では、各2D画像が異なる視角又は可視化パラグラフを有する3Dデータセットの連続2D画像をユーザが大きな遅延なく見ることができるように、3DデータセットのMIPレイキャスティングは、リアルタイムで作動することが要求される。医療用撮像においては、毎秒少なくとも6フレームの連続2D画像レンダリングがリアルタイム対話式フィードバックに対する必要性を満たすことが一般的に受け入れられている。これは、毎秒ほほ10億回の計算と同等である。
【0009】
最新コンピュータの限定された計算能力に鑑みて、MIPレイキャスティングの計算コストを低減するためにより効率的なアルゴリズムが開発されてきた。しかし、これらのアルゴリズムの多くは、作り出された2D画像の品質を犠牲にしてその効率を達成している。例えば、連続オブジェクトの個別の表現に関する一般的な問題は、ジッター効果であり、これは、ユーザが連続オブジェクトの更に詳細を見るために拡大した時に最も明白である。ジッター効果が慎重に制御されなかった場合、それは、MIPレイキャスティングアルゴリズムによって作り出された画像の品質を大幅に損なう場合がある。
【0010】
従って、レンダリング効率を増し、同時に画質品質に及ぼす影響がより小さいか又は好ましくは感知できない新しいMIPレイキャスティング方法及びシステムを開発することが望ましいと考えられる。
【発明の開示】
【0011】
本発明の好ましい実施形態は、適応データ表現技術、MIPレイキャスティング技術、及びデータ補間技術を用いて3Dデータセットに埋め込まれた3Dオブジェクトの高品質2D画像を発生させる適応MIPレイキャスティング方法及びシステムである。
【0012】
本方法及びシステムは、最初に、3Dデータセットを異なるサイズの複数のサブボリュームにフラグメント化してデータ構造、例えばオクトリを構成し、オクトリのノードをデータセットの異なるサブボリュームに関連付け、各サブボリュームはまた、サブボリューム内のデータ値分布を特徴付ける一組のデータ値パラメータを有する。特に、データセット全体は、オクトリのルートノードと関連している。
【0013】
本方法及びシステムは、次に、複数のレイを2D放射面から3Dデータセットに向けて投射する。一般的に平行投影と称する一実施形態では、複数のレイは、互いに平行であり、各レイは、2D放射面上に固有のレイ原点を有する。一般的に透視投影と称する別の実施形態では、複数のレイは、全てが同じレイ原点から放出され、各レイは、3Dデータセットに対して固有の放出角を有する。
【0014】
ある一定の断面又はレイ厚み及び所定の現在のデータ値記録を有する各レイは、そのレイ経路に沿って3Dデータセットの一連のサブボリュームと相互作用し、それがレイ経路に沿ってより高いデータ値を識別した時には常に現在のデータ値記録を更新する。具体的には、レイとサブボリュームの間の各相互作用の間に、現在のデータ値記録とサブボリュームに付随する一組のデータ値パラメータとの間で1つ又はそれよりも多くの比較が行われる。現在のデータ値記録がレイ経路上のサブボリュームのボクセルでの、例えばサブボリューム内のレイ経路の中間点でのデータ値よりも小さい場合には、ボクセルでのデータ値は、古い記録と入れ替わって新しい現在のデータ値記録になることになる。この処理は、レイが3Dデータセットを出るか、又はいくつかの所定のレイキャスティング終了条件が満たされてレイ経路上の3Dデータセットの最大データ値記録を識別するまで続けられる。最大データ値記録は、所定の画面転送関数に従って2D画像平面上のピクセル値に変換される。複数のレイに付随する2D画像平面上のピクセル値は、3Dデータセットに埋め込まれた3D内部構造を示す2D画像を構成する。
【0015】
レイと相互作用する適切なサブボリュームの選択に対して2つの競合する要件が存在する。一方では、大きなサブボリュームは、レイキャスティングの計算経費を大きく低減することができて本方法及びシステムがより効率的になり、他方では、小さなサブボリュームは、3D内部構造をより正確に特徴付けることができ、より高い品質の画像が作り出される。本方法及びシステムは、いくつかの所定の条件、例えば、サブボリュームの最大及び最小データ値間の差が所定の閾値よりも小さいことを満足するサブボリュームを選択することにより、これらの2つの競合するゴール間の均衡を取る必要がある。一実施形態では、オクトリのルートノードに付随するデータセット全体が、レイと相互作用するように最初に選択される。しかし、ルートノードに付随するデータ値パラメータの組が、3Dデータセットに埋め込まれた3D内部構造を十分に捕捉するのは稀であるから、データセットをより小さなサブボリュームに更にフラグメント化すべきであることが多く、レイ経路に沿ってレイ原点に最も近い、ルートノードの子ノードに付随するより小さなサブボリュームの1つが次に検査され、それが所定の条件を満足するかが判断される。このフラグメント化及び検査処理は、望ましいサイズのサブボリュームが識別されるまで再帰的に繰り返される。
【0016】
レイと相互作用するサブボリュームを最終的に選択した状態で、本方法及びシステムは、レイ経路上にあるサブボリューム内の特定の位置にあるデータ値を、その特定の位置を取り囲む既知データ値のトリリニア補間を通じて推定する。推定データ値がレイの現在のデータ値記録よりも大きい場合、推定データ値をその新しい現在のデータ値記録としてレイに割り当てる。そうでなければ、レイの現在のデータ値記録はそのままである。それに続いて、レイがまだ3Dデータセット内にある場合、本方法及びシステムは、選択したものの次に適切なサイズでレイ経路に沿って更に遠い別のサブボリュームを識別し、新しい推定最大データ値が判断されて推定が続行される。
【0017】
MIPレイキャスティングアルゴリズムの計算経費及び画像解像度は、主として、2D放射面から投射されるレイの数及び密度によって判断される。最新のコンピュータハードウエアで妥当な期間内に処理することができる限定された数のレイに鑑みて、本方法及びシステムは、2D放射面上のレイ原点の位置を、2D画像平面上のそれらのレイに付随するピクセル値が3Dデータセットに埋め込まれた3D内部構造の特性を有効に捕捉することができるように最適化する。
【0018】
一実施形態では、4つのレイが、最初に2D放射面の4つのコーナから放出される。2D画像平面の4つのコーナでの4つピクセル値を取得した後に、本方法及びシステムは、所定の画像化誤差閾値に照らしてそれらの値の変動を検査する。変動が閾値を超える場合、更に1つのレイを放射面の中心から放出し、それによって2D画像平面を4つのサブ平面に分割する。各サブ平面内のピクセル値の変動は、所定の画像化誤差閾値に照らして更に検査される。変動が閾値を超えるあらゆるサブ平面は、どのサブ平面の変動も閾値よりも小さくなるまで更に再帰的に分割される。
【0019】
最後に、本方法及びシステムは、2D画像平面上の周囲ピクセル値に基づいて、レイに付随しない2D画像平面上の各ピクセルにおける値を推定する。一実施形態では、これらのピクセル値は、所定の画像化誤差閾値を満足した最小サブ平面の4つのコーナにあるピクセル値のバイリニア補間の結果である。
【0020】
本発明の以上の特徴及び利点、並びにその付加的な特徴及び利点は、図面と共に本発明の好ましい実施形態の詳細説明の結果として以下においてより明確に理解されるであろう。
【発明を実施するための最良の形態】
【0021】
図1A及び図1Bは、本発明の2つの実施形態、つまり、平行投影及び透視投影をそれぞれ概略的に示している。直交座標(x、y、z)によって表された3Dドメインにおいては、1つ又はそれよりも多くの3Dオブジェクトを含む画像ボリューム106がある。MIPレイキャスティングでは、複数のレイ104を画像ボリューム106に投射し、2D画像上の3Dオブジェクトの3D特性を可視化するように各レイ経路に沿って最大データ値を識別することによって2D画像を発生させる。尚、本発明の状況におけるレイの形状は1D線ではなく、以下で説明する特定のレイ構成に依存するが3Dチューブ又はコーンである。
【0022】
図1Aに示す実施形態では、複数のレイ104を放射面102上の異なる位置から放出すると、各レイは、他のレイに平行に画像ボリューム106に向けて進む。レイの形状は、レイ厚みとも呼ばれる一定のサイズの断面を有するチューブ103である。異なるレイは、2D画像平面101上の異なるピクセルに対応し、各ピクセル値は、対応するレイ経路上で識別された画像ボリュームの最大データ値によって判断される。このようなMIPレイキャスティング構成は「平行投影」と呼ばれる。平行投影の場合、画像平面101は、レイ経路に沿ってどこにでも位置することができる。説明上、画像平面101は、図1Aに示すように放射面102と一致するものとすることができる。
【0023】
図1Bに示す実施形態では、複数のレイ104を放射面102上の同一レイ原点107から放出し、各レイは、画像ボリューム106に対して固有の透視角を有する。その結果、各個々のレイの形状は、視角108及びレイ原点107と画像ボリューム106との間の距離の両方の関数である可変サイズの断面を有するコーン105である。同様に、異なるレイは、2D画像平面101上の異なるピクセルに対応し、各ピクセル値は、対応するレイ経路上で識別された画像ボリュームの最大データ値で判断される。このようなMIPレイキャスティング構成は「透視投影」と呼ばれる。透視投影の場合、画像平面101は、レイ原点107と画像ボリューム106との間でレイ経路に沿ってどこにでも位置することができる。説明上、画像平面101は、図1Bに示すように放射面102と一致するものとすることができる。
【0024】
一般的に、上述の2つのMIPレイキャスティング構成の一方によって発生した2D画像の画像解像度は、単位面積当たりのピクセル数に依存する。実際には、画像当たりのピクセル総数は、定数、例えば5122であることが多く、これは、コンピュータモニタ上のピクセル数に依存する。従って、レイチューブ103の断面積を小さくすることによって単位面積当たりのピクセル数を多くすることにより、より高い画像解像度が達成され、放射面をレイ経路に沿って画像ボリューム106から離したり又は近づけたりしても画像解像度には影響はない。これとは対照的に、視角108又は距離109又はその両方を小さくすることにより、透視投影においてより高い解像度が達成される。
【0025】
図1Cは、画像解像度がレイ厚みとして変化する様子を示している。簡素化を期すために、各画像は、102=100ピクセルを有し、グリッド110−1、112−1、及び114−1のレイ厚みは、それぞれ、S、4S、及び16Sである。その結果、グリッド114−2上に発生した画像114−2は、最低の解像度を有し、一方、グリッド110−1上に発生した画像110−2は、最高の解像度を有する。平行投影では、放射面のサイズを小さくして放射面上のレイ原点の密度を大きくすることによってこのような拡大効果を達成し、また、透視投影では、放射面を画像ボリューム内の3Dオブジェクトの中心に近づけることによって同じ効果を達成する。
【0026】
画像ボリューム106は、通常、図1Dに示すように3Dデータセット116によって表される。3Dデータセットの各ボクセルは、特定の位置での3Dオブジェクトの物理的属性を示すスカラーデータ値を有する。図1Dに示すように、3Dデータセット116は、3つの直交座標x、y、及びzを有する。各座標に沿って、データセットは、その座標に垂直な2Dデータスライスのスタックを含む。各データスライスは、他の2つの座標に沿って規則的グリッド上のデータ値の2Dアレイを含む。例えば、3つの直交データスライス116−1、116−2、及び116−3は、それぞれ、z、x、及びyの方向で画像ボリューム106の異なる(ただし限定された)遠近感をもたらす。
【0027】
アルゴリズムの概要
本発明の一実施形態によるMIPレイキャスティングは、図2に示すような3つの大きな段階を含む。段階201では、本方法は、画像ボリュームを異なるサイズの複数のサブボリュームにフラグメント化し、一組のデータパラメータに付随する各サブボリュームは、サブボリュームのデータ値分布を特徴付ける。本方法に関する詳細は、図3A、図3B、及び図4に関連して以下に説明する。
【0028】
段階203では、本方法は、画像ボリュームの中心からある一定の距離を隔てて位置し、かつ画像ボリュームに対してある一定の方向に向けられた放射面から画像ボリュームに対して複数回のレイキャスティングを行う。放射面から投射されたレイは、レイ経路に沿って位置する一連のサブボリュームと選択的に相互作用する。レイ経路上の最大データ値を画像平面内のピクセル値に変換する。この処理の更なる詳細は、図5から図7に関連して以下に説明する。
【0029】
段階205では、本方法は、段階203で発生したピクセル値を用いて画像平面内のいずれかの他の位置のピクセル値を推定し、画像ボリュームに埋め込まれた3Dオブジェクトの2D図を呈示する。段階203及び段階205を数回繰返し、より多くのピクセル値を推定することができる。更に、段階203及び段階205を繰返して、放射面の位置又は方向が変わったか又は異なる可視化パラメータが適用された時に一連の新しい画像を発生させることができる。この処理の更なる詳細を図8から図10に関連して以下に説明する。
【0030】
画像ボリュームのフラグメント化
本発明の一実施形態によれば、画像ボリュームをまず一組のサブボリュームにフラグメント化し、各サブボリュームをより小さなサブボリュームに更にフラグメント化する。このような再帰的フラグメント化は、最小サブボリュームが所定のサイズ限界に達するまで続けられる。画像ボリューム全体を含む全てのサブボリュームを階層データ構造に関連付け、これによって元の画像ボリュームの新しい表現が得られる。
【0031】
図3Aは、複数のサブボリューム(例えば、585個のサブボリューム)にフラグメント化された後の3Dデータセット302を示している。これらのサブボリュームは、4つのフラグメント化レベルI、II、III、及びIVに属する。説明上、異なるサイズのサブボリューム、例えば、II−2、III−2、及びIV−2は、より小さなサイズの他のサブボリュームを露出させるために図3Aから除外されている。サイズに基づいて、サブボリュームの各々をオクトリデータ構造304の1つのノードに関連付ける。尚、説明を簡素化するために、サブボリュームの小さな部分集合のみをオクトリ304に示している。
【0032】
フラグメント化レベルIから始まって、データセット302全体は、単一のサブボリュームI−1として処理され、オクトリ304のルートノードに関連する。フラグメント化レベルIIでは、データセット302は、仕切られて同じサイズの8つのサブボリュームにされ、各サブボリューム、例えば、II−6をオクトリ304のレベルIIの1つの中間ノードに関連する。フラグメント化レベルIIIでは、サブボリュームII−6のような各サブボリュームは、更に8つのより小さなサブボリュームIII−1、III−2、...、及びIII−8に分割され、同様に、各サブボリューム、例えばIII−6は、レベルIIIの中間ノードに関連する。フラグメント化レベルIVでは、サブボリュームIII−6のような各サブボリュームは、仕切られて8つのサブボリューム(サブボリュームIV−6を含む)にされ、レベルIVの各サブボリュームは、オクトリ304の葉ノードに関連する。レベルIには80個のサブボリュームがあり、レベルIIには81個のサブボリュームがあり、レベルIIIには82個のサブボリュームがあり、レベルIVには83個のサブボリュームがあることから、データセット302を4つの異なるフラグメント化レベルで合計で、
80+81+82+83=1+8+64+512=585
個のサブボリュームにフラグメント化する。
【0033】
サブボリュームは、サブボリューム内のデータ値分布を特徴付ける複数の組のデータパラメータを有する。一実施形態では、その組のパラメータには、少なくとも3つの要素が含まれる:
・サブボリューム内のデータ値の最小値を表すVmin、
・サブボリューム内のデータ値の平均を表すVavg、及び
・サブボリューム内のデータ値の最大値を表すVmax
【0034】
図3Aに示すように、画像ボリュームフラグメント化は再帰的手順である。この手順は、最小サブボリュームが指定のサイズ限界に達するまで終わらない。一実施形態では、この指定のサイズ限界又はオクトリ葉ノードに付随する最小サブボリュームは、画像ボリュームの2×2×2セル又はボクセルを有するサブボリュームである。セル又はボクセルは、付随のデータ値を有する画像ボリュームの最小単位である。例えば、画像ボリュームがMIPレイキャスティングでは一般的である5123個のセルを有し、かつ最小サブボリュームが2×2×2セルを有する場合、画像ボリュームフラグメント化処理は、フラグメント化レベルIVまで続くと、最小サブボリュームの数が2563である。
【0035】
図3Bは、2つのセル又はボクセルが3つの直交方向の各々に互いに隣り合う8つのセル又はボクセルを有するサブボリューム306を示している。ボクセル308は、1つの採取データ値、例えばV0に中心がある立方体である。ボクセル内のデータ値は、一定であると仮定し、ボクセルの境界に沿ってデータ値の不連続があるとすることができる。これとは対照的に、セル310は、立方体の各コーナに1つがある8つの採取データ値V1からV8を有する同じサイズの立方体である。一実施形態によれば、セルのあらゆる点のデータ値は、トリリニア補間によって推定し、セルの境界に沿ってはデータ値の不連続はない。尚、本発明は、いずれのフォーマット、セル、又はボクセルにおいて表される画像ボリュームにも等しく適用される。簡素化を期すために、以下で説明する内容は、一例としてセル表示に焦点を当てるものである。
【0036】
再び図3Bを参照すると、原点がセル310の中心にある3D直交座標があり、セルの3つの直交する縁部の長さは、それぞれ、Dx、Dy、及びDzである。セル310のいずれかの点V(x、y、z)でのデータ値は、以下のように、セル310の8つのコーナでのデータ値V1からV8の関数としてトリリニア補間によって表すことができる。
【0037】
【数1】
【0038】
図4は、上述の画像ボリュームフラグメント化並びオクトリ構造のコンピュータプログラムを要約した流れ図である。段階401では、コンピュータプログラムは、3Dデータセットを受け取り、3Dデータセットをオクトリのルートノードと関連付けることにより、オクトリデータ構造を初期化する。段階403では、データセットを8つのサブボリュームにフラグメント化し、各サブボリュームが8つの子ノードに関連付けられるように、8つの子ノードをルートノードで発生させる。
【0039】
段階405から始まって、最小サブボリュームが指定のサイズ限界に達するまで、各サブボリュームをより小さなサブボリュームに再帰的にフラグメント化する。段階405では、コンピュータプログラムは、最初に、サブボリュームのサイズが指定のサイズ限界、例えば、2×2×2セルのサブボリュームに達したかを検査する。達していない場合、段階407では、サブボリュームを8つのより小さなサブボリュームにフラグメント化する。8つのより小さなサブボリュームの1つを拾うと、再帰的フラグメント化が段階405で再び始まる。
【0040】
サブボリュームのサイズが指定のサイズ限界、例えば、2×2×2セルに達した場合、コンピュータプログラムは、段階409でこのサブボリュームをフラグメント化するのを止め、サブボリュームに付随するオクトリのノードは、オクトリの葉ノードの1つである。段階411では、コンピュータプログラムは、2×2×2セルまでフラグメント化されていない他のサブボリュームがあるかを検査する。ある場合には、上述のサブボリュームの1つを選択して、再帰的フラグメント化が段階405で続けられる。ない場合には、画像ボリュームフラグメント化を終了する。
【0041】
上述のように、各サブボリュームは、2D放射面上のピクセル値を推定するための(Vmin、Vavg、Vmax)のような一組のデータパラメータに関連付けられる。一実施形態では、3Dデータセットをフラグメント化してオクトリを構成した後に、コンピュータは、オクトリの葉ノードレベルから始まり、図3AのサブボリュームIV−6のような葉ノードに付随するサブボリュームの対応する(Vmin、Vavg、Vmax)を計算する。葉ノードに付随するサブボリュームは、8つのセルのみを含み、かつ、各セルは、大半は2つ又はそれよりも多くのセルによって共有される8つのデータ値を有することから、コンピュータプログラムは、記憶装置、例えば、ハードディスクから27個のデータ値を検索し、サブボリュームの(Vmin、Vavg、Vmax)を計算する必要があるだけである。
【0042】
葉ノードレベルの全てのサブボリュームを処理した後に、コンピュータプログラムは、オクトリ304上でレベルを1つ上げ、中間ノードに付随するIII−6のようなサブボリュームの対応するパラメータを計算する。この処理は、ルートノードに達するまで続けられる。各中間ノードは、8つの子ノードを有し、各子ノードは、付随のデータパラメータが既に前に求められているサブボリュームに付随するものであることから、この中間ノードの各データ値パラメータを8つの子ノードに付随する8つのパラメータの関数として表すことができる。
・Vmin=Min(Vmin_1,Vmin_2,...,Vmin_8)、
・Vavg=(Vavg_1+Vavg_2+...+Vavg_8)/8、及び
・Vmax=Max(Vmax_1,Vmax_2,...,Vmax_8)
【0043】
以下で明らかになるように、データ値パラメータのこの発生は、図3Aに示すように上から下にルートノードレベルで始まるオクトリ構造と反対の方向に進む。データパラメータ発生のこの下から上の手法は、オクトリのより低いレベルにある計算結果を最大に再利用することから最も効率的である。
【0044】
段階201では、元の画像ボリュームの新しい表現がMIPレイキャスティングの段階203に利用可能である。この表現は、オクトリ及び異なるサイズの複数のサブボリュームを含み、オクトリの1つのノードに付随し、かつ一組のデータパラメータを有する各サブボリュームは、サブボリューム内のデータ値分布を特徴付ける。
【0045】
3D適応MIPレイキャスティング
MIPレイキャスティングは、画像ボリュームに埋め込まれた内部3D構造を示す2D画像を発生させるアルゴリズムであり、ピクセルからのレイを画像ボリュームに投射し、レイ経路に沿った最大データ値を識別し、所定の画面転送関数に従って最大データ値をピクセル値に変換することによって2D画像の各ピクセル値を推定する。本発明の一実施形態によれば、効率的な3D適応MIPレイキャスティングアルゴリズムは、以下の3つの段階を含む。
・段階1:アルゴリズムは、所定の現在のデータ値記録及びある一定の断面を有するレイの数学的モデルを構成して3Dオブジェクトを個別の3Dデータセットとして表し、データセットの各データ値は、オブジェクトの特定の位置でのこのような物理特性を表す。
・段階2:アルゴリズムは、レイ経路に沿った一連のデータ値を一度に1つレイの現在のデータ値記録と比較し、より高いデータ値が識別された場合は現在のデータ値記録を入れ替える。
・段階3:アルゴリズムは、所定の画面転送関数に従ってレイ経路に沿った最高データ値でもあるレイの最終データ値を2D画像上のピクセル値に変換する。
【0046】
画面転送関数は、一般的に、3Dデータセットに埋め込まれた内部構造の異なる態様を解明するために任意に選択された単調関数である。図5は、MIPレイキャスティングで使用することができる画面転送関数である。垂直軸は、2D画像上のピクセル値の大きさを示し、水平軸は、3Dデータセットのデータ値のマグニチュードを示している。画面転送関数を3つの部分に分割することができる。Vlowよりも小さい一切のデータ値は、一定のピクセル値Plowに対応し、Vhighよりも大きな一切のデータ値は、一定のピクセル値Phighに対応し、VlowとVhighの間の一切のデータ値は、PlowとPhighの間にあるピクセル値Piに対応する。
【0047】
図6は、コンピュータプログラムが本発明の一実施形態に従って特定のレイ経路に沿った画像ボリュームの最高データ値を識別する方法を示す流れ図である。画像ボリュームは、既に図3Aに示すようにオクトリに付随する複数のサブボリュームにフラグメント化されており、一組のデータパラメータ(Vmin、Vavg、Vmax)を有する各サブボリュームは、データ値分布を特徴付けることから、コンピュータプログラムは、効率を目的として、オクトリのルートノードに付随する画像ボリューム全体に対して識別処理を開始する。
【0048】
段階601では、コンピュータプログラムは、2D放射面から放出した複数のレイからレイを選択し、そのレイは、2D放射面上の原点と、画像ボリュームに対する特定の向きと、初期の現在のデータ値記録Vrecとを有する。一実施形態では、Vlowよりも低い一切のデータ値は、2D画像上の同じピクセル値Plowに対応することから、図5に示すように、画面転送関数のVlowになるように初期の現在のデータ値記録を設定する。図7に関連して以下で説明するように、この手法は、オクトリデータ構造に適用した時に、かなりの量の画像ボリュームを識別処理から排除することができ、識別処理がより効率的になる。
【0049】
段階603では、コンピュータプログラムは、オクトリデータ構造からレイに初めて遭遇する最大サブボリュームを選択し、このサブボリューム内のレイ経路がレイの現在のデータ値記録Vrecよりも高いデータ値を有する点を含むかを検査する。デフォルトにより、段階603で選択される第1のサブボリュームは、常に付随の組のデータ値(Vmin、Vavg、Vmax)を有する画像ボリューム全体である。しかし、図6に示すように、コンピュータプログラムは、一部の条件が満たされた場合は、段階608又は609を完了した後に段階603に再度行くことができる。この場合、コンピュータプログラムは、オクトリデータ構造に付随する少なくとも1つのサブボリュームを検査済みであるはずであり、段階603で選択したサブボリュームは、画像ボリューム全体ではなく、レイが出たばかりのサブボリュームの空間的に隣接するサブボリュームになる。
【0050】
上述のように、コンピュータプログラムのゴールは、画像ボリューム内でレイ経路上にある最高データ値を識別することである。しかし、画像化誤差を低減するために、並びに識別処理を促進させるために、段階603で選択したサブボリュームは、Vrecよりも高い少なくとも1つのデータ値、例えば、Vrec<Vmaxを有することだけの理由により、レイの現在のデータ値記録のより高い値との入れ替えは行わない。むしろ、サブボリュームは、レイの現在のデータ値記録を入れ替えるために以下の3つの判断基準を満足すべきである。
・サブボリューム最大データ値Vmaxは、レイの現在のデータ値記録Vrecよりも高くなければならない(段階605)、
・サブボリューム内の最大画面値差(MSVD)は、所定の閾値を下回らなければならない(段階609)、及び
・サブボリューム内のレイ経路上の所定の位置、例えば、サブボリューム内のレイ経路の中点のデータ値Vestは、レイの現在のデータ値記録Vrecよりも高くなければならない(段階615)。
【0051】
段階605では、コンピュータプログラムは、レイの現在のデータ値記録Vrecを段階603で選択したサブボリュームのサブボリューム最大データ値Vmaxと比較する。Vrec>Vmaxの場合、レイの現在のデータ値記録が更新される機会はない。従って、コンピュータプログラムは、このサブボリュームを排除し、レイは、サブボリュームを出た時の現在のデータ値記録を維持する。尚、レイは、サブボリュームを出た直後に画像ボリューム全体を通過したと考えられる。従って、コンピュータプログラムは、段階608では、これがレイ経路上の最終サブボリュームであるかを検査する。そうである場合、コンピュータプログラムは、レイキャスティングを止め、レイの現在のデータ値記録Vrecをレイ経路に沿った最高データ値と処理することになり、次に、この最高データ値を2D放射面上の対応するピクセル値を推定するのに使用する。そうでなければ又はVrec<Vmaxの場合には、値がレイの現在のデータ値記録よりも高い少なくとも1つの位置がサブボリューム内にある。しかし、このボクセルをVrecを更新するのに使用することができるか否かを判断するためには、コンピュータプログラムによって取られるいくつかの更に別の段階が必要である。
【0052】
段階607では、コンピュータプログラムは、所定の画面転送関数(STF)を用いてサブボリュームの最大画面値差(MSVD)を推定する。サブボリュームのMSVDは、2D放射面上のピクセル値変動に及ぼすサブボリューム内のデータ値変動の影響を示している。一実施形態では、サブボリュームの付随のデータパラメータVmin、Vavg、Vmax、及び現在のデータ値記録Vrecのマグニチュードにより、サブボリュームのMSVDは、以下のように若干異なる定義を有する場合がある。
・Vrec<Vminの場合、MSVD=MAX(STF(Vmax)−STF(Vavg),STF(Vavg)−STF(Vmin))、
・Vmin<Vrec<Vavgの場合、MSVD=MAX(STF(Vmax)−STF(Vavg),STF(Vavg)−STF(Vrec))、又は
・Vavg<Vrec<Vmaxの場合、MSVD=STF(Vmax)−STF(Vrec)
【0053】
識別処理の目的は、画像ボリューム内のレイ経路上の最高データ値を識別することであることから、値が現在のデータ値記録Vrecよりも小さいサブボリュームのあらゆるボクセルは、サブボリュームのMSVDの推定には関係がないはずである。一方、Vavgは、サブボリューム内のデータ値分布全体を特徴付けるという点においてVmax及びVminよりも正確であり、Vavg並びVmax及びVminを伴うMSVD定義では、Vmax及びVminを伴うだけのMSVD定義よりも正確な画像を生成することができる。一部の代替的実施形態では、平均データ値Vavgは、中央データ値Vmedで入れ替えることができる。中央データ値は、サブボリュームデータ値の一方の半分よりも高く、サブボリュームのデータ値の他方の半分よりも低いデータ値である。
【0054】
段階609では、コンピュータプログラムは、推定MSVDを所定の閾値と比較する。推定MSVDが閾値を超える場合、コンピュータプログラムは、オクトリデータ構造に沿って現在サブボリュームに付随するノードから段階的に下り、子ノードの1つに付随するより小さなサブボリュームを選択する(段階611)。子ノードに付随する複数のより小さなサブボリュームの中で、コンピュータプログラムは、他の全てのサブボリュームの先にあるレイに遭遇するものを選択し、次に、段階605に戻って新たに選択したサブボリュームが段階609での試験に合格するのに十分に小さいか否かを判断する。尚、新たに選択したサブボリュームは、固有の組のデータパラメータ(V’min、V’avg、V’max)を有し、特に、最大データ値V’maxは、親ノードの最大データ値Vmaxよりも小さいとすることができる。V’max<Vrecの場合、コンピュータプログラムは、このより小さなサブボリュームを飛び越して、上述のように段階608に移動することになる。
【0055】
段階605から段階611を含むループ後に、コンピュータプログラムは、例えば2×2×2セルを有する最小サブボリュームに付随するオクトリデータ構造の葉ノードに到達することができる。最小サブボリュームがまだ段階609で試験に合格しない場合、コンピュータプログラムは、8つのセルの1つを選択するか又はセルを8つのサブセルにフラグメント化し、次に、段階609で試験に合格するようにサブセルの1つを検査することができる。図3Bに示すように、例えば、トリリニア補間を通じて8つのコーナでの8つのデータ値を用いてセル又はサブセル内のいずれかの点でのあらゆるデータ値を推定することができる。他方、レイは、一部の実施形態によれば、ある一定の断面を有するチューブ又はコーンであると見なされる。従って、セル内のフラグメント化は、ある一定の段階では、例えば、サブセルのサイズが断面内のレイの断面よりも小さい場合は停止すべきである。これが発生すると、コンピュータプログラムは、段階609での試験が満足されたと仮定して自動的に段階613に進むことができる。
【0056】
段階609での試験が満足されたか又はサブボリューム(又はセル又はサブセル)のMSVDが所定の閾値よりも小さいと仮定して、コンピュータプログラムは、次に、現在のデータ値記録Vrecをサブボリューム内のレイ経路上の1つの地点にある推定データ値Vestと比較し、VrecをVestで更新すべきか否かを判断する。一部の実施形態では、サブボリューム内のレイ経路の中心点をこの比較のために選択し、一部の他の実施形態では、コンピュータは、レイがサブボリュームに入る/出る位置のような位置を選択することができる。選択した位置が正確にはセルの1つのコーナではないことが多いことから、コンピュータプログラムは、指定の位置にあるデータ値Vestを補間すべきである。これを行うために、コンピュータプログラムは、段階613では、最初にどのセルが選択した位置を含むか否かを判断し、次に、コンピュータメモリ又はハードディスクからセルの8つのコーナにあるデータ値を検索し、例えば、トリリニア補間を通じてセルの位置にあるデータ値Vestを推定する。
【0057】
Vrec>Vest(段階615で「ノー」)の場合、レイは、現在のサブボリュームを出ると同時に現在のデータ値記録を維持する。尚、レイがサブボリュームを出る時には常に、コンピュータプログラムは、段階608でレイも画像ボリューム全体を出たかを検査すべきである。Vrec<Vest(段階615で「イエス」)の場合、コンピュータプログラムは、段階617で現在のデータ値記録VrecをVestと入れ替え、Vestは、レイの現在のデータ値記録になる。次に、コンピュータプログラムは、図5に示すように、Vhighを超えるデータ値記録が対応するピクセル値Phighに影響を与えないために、段階619でレイの現在のデータ値記録を画面転送関数のVhighと比較する。Vrec>Vhighの場合、レイキャスティングを続ける必要がないので、コンピュータプログラムは、この特定のレイに対してレイキャスティングを直ちに終了する。そうでなければ、レイキャスティングが続行される。しかし、レイはサブボリュームを出たばかりであることから、コンピュータプログラムは、段階603でレイキャスティングを再開する前に、最初にレイが画像ボリューム全体の外側にあるか否かを判断する。
【0058】
図6に示す適応MIPレイキャスティングアルゴリズムは、本質的には、レイ経路に沿ったサブボリュームのシーケンスを選択し、レイ経路に沿った最高データ値を有するサブボリュームの1つにおける1つの位置を識別する手順である。異なるサブボリュームがオクトリデータ構造の異なるノードに付随し、かつ異なる組のデータパラメータ(Vmin、Vavg、Vmax)によって特徴付けられることから、アルゴリズムは、MIPレイキャスティング(例えば、段階605で)のゴールに関連のないサブボリュームを適切に排除して計算経費を大幅に低減することができる。
【0059】
図7は、任意に分布させたデータ値のグループ間で最高値を有するボクセルを図6に示す実施形態に従って識別する際にアルゴリズムが作業する方法を示す1D実施例を示すものである。尚、1Dにおけるゴールは、アルゴリズムの2D又は3Dバージョンが、異なるサブボリューム内のレイ経路の異なる部分上のデータ値のシーケンスを推定してその間で最高値を識別する必要があるために、2D又は3Dにおけるゴールよりも達成しやすい。これとは対照的に、最高データ値は、アルゴリズムの1Dバージョンには既知のものであり、未知のものはこの最高値の位置であり、一方、レイ経路上の最高値の位置は、2D又は3Dバージョンのアルゴリズムの関心事ではない(たとえ容易に入手可能であっても)。
【0060】
この例においては、水平軸に沿って16個のデータサンプル、AからPがある。例えば、サンプルAは100、サンプルJは221、サンプルNは83であるなどである。直観的な手法は、最初に現在のデータ値記録に任意の値(例えば、108)を割り当て、次に、16個全てのデータサンプルと1つずつ比較することである。サンプルがより高い値を有する場合、現在のデータ値記録は、より高い値と入れ替えられる。この処理は、最終サンプルPが検査されて最高値を有するサンプルがサンプルI(227)であると識別されるまで続けられる。
【0061】
明らかに、この直観的手法の計算経費はO(N)であり、Nは、データサンプル数である。M2グループのデータサンプル(2D画像を発生させるのに必要とされるM2レイキャスティングと類似)がある場合、総計算経費は、O(NM2)になる。Nが非常に小さい数字である場合、この手法は、成功するであろう。しかし、現実の用途、例えばCTスキャン画像ボリュームにおいては、Nは、大きな数字(例えば、数百又は千を超えさえもする)であることが多く、O(NM2)は、ほとんどのコンピュータシステムでは処理できないほど大きなものになる。
【0062】
代わりに、16個のデータサンプルの各々が二進ツリー700の16個の葉ノードの1つに関連するように、5レベル二進ツリー700を構成する。ルートノード740を含む二進ツリー700の全ての非葉ノードは、この非葉ノードの子孫である葉ノードでの最小データ値、平均データ値、及び最大データ値を示す一組のデータパラメータ(Vmin、Vavg、Vmax)と関連する。例えば、ノード720は、付随の値がそれぞれ100及び125である2つの葉ノードのみを有することから、一組のデータパラメータ(100、112、125)を有し、ルートノード740は、16個全ての葉ノードが子孫であり、16個の葉ノードの中で葉ノードIが最高値227を有し、葉ノードL及びMが最低値58を有するので、一組のデータパラメータ(58、138、227)を有する。
【0063】
初期データ値記録は、それぞれ、Vrec=180、Vlow=180、Vhigh=220であると仮定すると、所定の閾値TMSVD=10であり、画面転送関数STF(V)=V<Vlowであれば180、又はVlow<V<VhighであればV、又はVhigh<Vであれば220である。段階603に従ってルートノードを選択してVrecと比較する。Vrec(180)がルートノードのVmax(227)よりも小さいことから、180よりも高い付随値を有する16個のサンプルの少なくとも1つがある。従って、ルートノードのMSVDを段階607に従って(STF(Vmax)−STF(Vrec))=227−180=47のように推定する。これは、Vrec(180)がルートノードのVavg(138)よりも大きいからである。MSVD(47)は、TMSVD(10)よりも大きいことから、コンピュータプログラムは、段階611に従って1つレベルを下げて子ノードの1つに行くことにより、葉ノードのサブグループを検査すべきである。子ノード760のVmaxは、現在のデータ値記録Vrec(180)よりも小さい171のみであることから、段階605に従って子ノード760の子孫である8つの葉ノードのいずれも考察する必要はない。代わりに、子ノード780が選択されるが、その理由は、それが子ノード760の隣にあり、かつそのVmax(227)がVrec(180)よりも大きいからである。この処理は、上述の3つ全ての判断基準を満足するノード784が識別され、かつ現在のデータ値記録(180)と入れ替えるために葉ノードIでの値(227)が選択されるまで続けられる。尚、検査していない葉ノードがまだ6つ(KからP)あっても、現在のデータ値記録Vrec(227)がVhigh(220)よりも高く、かつ、より高い値があっても得られるピクセル値には影響を与えないので、これ以上の検査の必要はない。従って、コンピュータプログラムは、段階619に従ってこの処理を適切に終了することができる。
【0064】
数学的には、上述の二進ツリーによる手法の計算経費は、データサンプルの分布が不規則である場合はO(log2N)のみであり、直観的手法O(N)の計算経費よりも大幅に低い。上述のように、3Dデータセットを複数のサブボリュームにフラグメント化して各サブボリュームをオクトリデータ構造のノードに関連付けることによってアルゴリズムを3Dまで拡張した時に、計算経費は、大幅に落ちる可能性がある。
【0065】
段階609で適応MIPレイキャスティングに使用した所定の閾値は、アルゴリズムの効率及び精度に影響を与えるパラメータである。所定の画面転送関数が与えられると、閾値は、試験に合格することができるサブボリュームを見つけるまで段階609で検査するのにコンピュータプログラムがいくつのサブボリュームを必要とするかを決めるものである。すなわち、閾値が大きいほど、アルゴリズムは効率的になる。一方、段階613でのアルゴリズムは、任意に選択した位置、例えば、サブボリューム内のレイ経路の中心点でのデータ値を推定し、この推定値をサブボリューム内のレイ経路上の最大データ値として処理して段階615で現在のデータ値記録と比較する。しかし、この任意に選択した位置は、データ値がサブボリューム内のレイ経路上のピークに到達する正確な位置ではない可能性がある。より小さな閾値は、段階609での試験に合格することができるより小さなサブボリュームに変換され、従って、任意に選択した位置と正確な位置との間の誤差が小さくなる。実際には、コンピュータプログラムは、適切な閾値を選択することにより、これらの2つの競合するゴール、又は効率と精度を両立させなければならない。
【0066】
一実施形態によれば、段階609で使用した閾値は、静的な値ではなく、妥当な経費で最適な結果を発生させるために画像間で変わる動的な値である。E0をユーザが定める初期閾値であると仮定して、カスタマイズされた閾値を以下のように定める。
・平行投影の場合、Pzoomを画像の物理的サイズを示すズーム因子とすると、E(E0,Pzoom)=E0/Sqrt(Pzoom)、及び
・透視投影の場合、Pdistanceをレイ原点と画像ボリュームの中心との間の距離とすると、E(E0,Pdistance)=E0*Log2(Pdistance)
【0067】
平行投影の場合にズーム因子Pzoomを大きくすると、閾値が小さくなり、コンピュータプログラムは、レイ経路に沿った最大データ値を識別する前により多くのサブボリュームを試験する必要があり、解像度が高く、かつジッター効果が小さくなった画像が作り出される。これとは対照的に、透視投影の場合にレイ原点と画像ボリュームとの間の距離Pdistanceを大きくすると、画質に逆効果を与える。
【0068】
画質以外に、使い易さは、適応MIPレイキャスティングアルゴリズムを評価する時の別の要素である。例えば、放射面を画像ボリュームに対して位置決めする時間と画像をコンピュータモニタ上でレンダリングする時間との間のいかなる時間間隔も、心血管疾患診断のような動的画像化用途において望ましくないものである。このような時間遅延を小さくし、ユーザに対して診断処理中により多くの制御を与えるために、一実施形態では、以下のように、望ましいフレーム/秒(DFPS)と実際のフレーム/秒(AFPS)との間の比率によって所定の閾値を調節することができる。
・平行投影の場合、E(E0,Pzoom,DFPS,AFPS)=E(E0,Pzoom)*DFPS/AFPS、及び
・透視投影の場合、E(E0,Pdistance,DFPS,AFPS)=E(E0,Pdistance)*DFPS/AFPS
【0069】
その名称が示すように、DFPSは、ユーザが好む画像レンダリング速度であり、一方、AFPSは、コンピュータハードウエア、放射面上のピクセル数、及び処理される画像ボリュームのような画像化システムの設定値によって限定される画像レンダリング速度である。好ましい画像レンダリング速度がシステムによって提供される画像レンダリング速度よりも大きい場合、閾値は、相応に大きくなるべきである。その結果、閾値を大きくすると、画質に妥協して処理することにより、ユーザが好む画像レンダリング速度が達成される。他方、好ましい画像レンダリング速度がシステムが与えることができる画像レンダリング速度よりも小さい場合、システムは、閾値を小さくして、ユーザが許容可能な速度におけるより高品質な画像を発生させるための付加的な機能を有することができる。
【0070】
2D画像の推定
3DMIPレイキャスティングでは、画像ボリューム内のレイ経路に沿った最大データ値を識別し、次に、所定の画面転送関数に従ってそれを2D画像平面上の特定の位置のピクセル値に変換する。3DMIP適応レイキャスティングは、計算上高価な作動であることから、アルゴリズムの効率は、実質的にレイキャスティングを通じて発生させなければならない画像平面上のピクセル値の数に依存する。図8は、コンピュータプログラムが画像平面上のどのピクセル値を適応MIPレイキャスティング方法を通じて発生させる必要があるかを適応して判断する方法、及びどのピクセル値を発生したピクセル値を用いて画質に対して感知不能でないならば無視可能な影響で推定することができるかを示す流れ図である。
【0071】
段階801では、コンピュータプログラムは、図1A及び図1Bに示すように、画像ボリュームから隔てたある一定の距離であり、かつ画像ボリュームに対してある一定の方向に向けられた2D画像平面を構成する。画像平面は、通常、M×M(例えば、512×512)要素を含むコンピュータメモリ内の2Dアレイによって表され、2Dアレイの各要素は、画像平面上の対応する位置の1つのピクセル値を格納する。
【0072】
段階803では、コンピュータプログラムは、画像平面を同じサイズの複数のミニ平面に細分化し、各ミニ平面は、2Dアレイの一部分に対応し、かつP×P(例えば、16×16)ピクセルを含む。一実施形態では、ミニ平面は、四分木データ構造のルートノードに関連する。
【0073】
段階805では、段階803で作成した各ミニ平面に対して、コンピュータプログラムは、4回の別々の適応MIPレイキャスティングを行い、ミニ平面の4つのコーナにある4つのピクセル値を推定する。
【0074】
段階807から始めて、コンピュータプログラムは、この再帰的処理が終わると画像ボリュームの2D画像が2Dアレイ内に形成されるように、2Dアレイの全ての要素をピクセル値で再帰的に満たす。一実施形態では、コンピュータプログラムは、各々が四分木データ構造の1つの子ノードに付随する複数のより小さなサブ平面にミニ平面を細分化し、適応MIPレイキャスティング又は補間法を通じてサブ平面の各ピクセルにピクセル値を割り当てる。より詳細には、コンピュータプログラムは、最初に、段階807で処理されていないミニ平面があるか否か、すなわち、ピクセル値なしに少なくとも1つのピクセルを含むミニ平面があるかを検査する。ない場合には、画像平面の全てのピクセルには、ピクセル値が既に割り当てられており、コンピュータプログラムは終了する。ある場合には、コンピュータプログラムは、段階809で処理されていないサブ平面がないかに関して、段階807で識別したミニ平面に関連する四分木データ構造を検査する。
【0075】
四分木データ構造に関連する全てのサブ平面が処理された場合、コンピュータプログラムは、段階807に戻って次のミニ平面を処理する。そうでない場合、コンピュータプログラムは、段階811でサブ平面を識別し、このサブ平面が2×2ピクセルのみを含むかを検査する。2×2ピクセルのみを有するサブ平面は、サブ平面を細分化することができる最小サブ平面である。一実施形態では、コンピュータプログラムは、段階813で適応MIPレイキャスティングを通じて、段階811で識別したサブ平面上のあらゆるピクセルに対してピクセル値を推定する。段階811で識別したサブ平面が2×2ピクセルよりも大きい場合、コンピュータプログラムは、更に別の実験を実施してサブ平面をピクセル値で埋める方法を決めるべきである。
【0076】
段階815では、コンピュータプログラムは、最初にこのサブ平面の最大ピクセル値差(MPVD)を推定する。名称が示すように、MPVDは、サブ平面内のピクセル値分布を測るものである。一実施形態では、MPVDは、以下のように定められる。
MPVD=MAX(|Pavg−P1|,|Pavg−P2|,|Pavg−P3|,|Pavg−P4|)/S
ただし、Sは、サブ平面内のピクセル総数であり、P1からP4は、サブ平面のコーナのピクセル値であり、Pavgは、以下のようにP1からP4の平均である。
Pavg=(1/4)(P1+P2+P3+P4)
【0077】
一部の他の実施形態では、平均ピクセル値Pavgは、MPVDを推定するためにサブ平面の中央ピクセル値Pmedと入れ替わることができる。関連のピクセル値を有していないサブ平面内の残りのピクセルを満たす方法を判断するために、MPVDを所定の画像化誤差閾値と比較する。
【0078】
一般的に、補間は、適応MIPレイキャスティングよりも効率的な代案であり、従って可能な限り使用すべきである。他方、適応MIPレイキャスティングを通じて発生したピクセル値は、補間を通じて発生したものよりも正確である。2D画像の異なる部分は、画像ボリューム内の異なる3D構造を捕捉して異なるレベルの画像解像度を必要とする可能性があることから、2D画像に沿った汎用画像化誤差閾値は、最も好ましい選択肢ではない。
【0079】
代わりに、段階817では、コンピュータプログラムは、画像ボリュームの異なる部分を処理する時に閾値を選択的に調節する。例えば、コンピュータプログラムは、ある一定の3D内部構造、例えば医療画像化における骨の縁部に対応する場合がある2D画像の部分をレンダリングする時により小さな所定の画像化誤差閾値を選択すべきであり、これは、その後、強制的にサブ平面をより小さなサブ平面にフラグメント化させ、その結果、補間ではなく適応MIPレイキャスティングを通じてサブ平面内により多くのピクセル値を発生させる必要がある。所定の画像化誤差閾値修正のカスタマイズ化に関する更なる詳細は、図10に関連して以下に与えられている。
【0080】
段階819では、コンピュータプログラムは、サブ平面のMPVDがカスタマイズされた画像化誤差閾値を超えるかを検査する。超えない場合、コンピュータプログラムは、最初に、適応MIPレイキャスティングを通じてサブ平面の中心にあるピクセル値を推定し、次に、段階823で各々が四分木データ構造の子ノードに付随する複数のより小さなサブ平面にサブ平面を細分化する。MPVDがカスタマイズされた画像化誤差閾値よりも高い場合、コンピュータプログラムは、段階821で既存のピクセル値の補間を通じてあらゆる満たされていないピクセルに値を割り当てる。一実施形態では、サブ平面のコーナにある4つのピクセル値のバイリニア補間によってサブ平面内のピクセル値分布を推定する。図9に示すように、いずれかの位置(x,y)のピクセル値P(x,y)は、以下のようにバイリニア補間することができる。
【0081】
【数2】
【0082】
段階821又は823後に、コンピュータプログラムは、段階809に戻って次のサブ平面があれば処理する。この処理は、2Dアレイの全ての要素に、3D適合レイキャスティング又はバイリニア補間によって作り出された画像平面上の1つの位置に対応するピクセル値が割り当てられるまで続けられる。その結果、コンピュータモニタのようなグラフィック表示装置上でレンダリングすることができる画像ボリュームの2D画像が形成される。
【0083】
一般的に、人間の目の方が、オブジェクト、例えば2D画像の高周波成分に敏感である。しかし、バイリニア補間(図9)は、本質的にローパスフィルタであるために画像の高周波成分を不鮮明にする傾向がある。従って、高周波成分を捕捉して総計算経費を抑えるために、コンピュータプログラムは、いくつかの部分でより高価な適応MIPレイキャスティングを通じてより多くのピクセル値を発生させ、同時に画像平面の他の部分でバイリニア補間を通じてピクセル値の大部分を推定することができる。
【0084】
上述のように、画像解像度及び画像レンダリング速度を制御するために所定の画像化誤差閾値を調節することができる。例えば、サブ平面が複雑な内部構造又はオブジェクトの縁部のような高周波成分に対応していない場合、所定の画像化誤差閾値は高い値に上げられ、この逆も可能である。しかし、この目的を達成するために、コンピュータプログラムは、処理されるサブ平面が高周波成分を含むか否かを予測すべきである。
【0085】
一部の実施形態によれば、2つの方法を用いて所定の画像化誤差閾値を調節し、画質と画像レンダリング速度を両立させることができる。図8の段階817に示すように、その方法は以下の通りである。
・バイリニア補間誤差分析、及び
・オクトリ横縁部検出
【0086】
図10Aに示すように、サブ平面1000は、適応MIPレイキャスティングが発生させる4つのコーナにある4つの既知のピクセル値P1からP4を有する。従って、サブ平面1000の中心にあるバイリニア補間したピクセル値P5'は、以下の通りである。
P5'=(1/4)(P1+P2+P3+P4)
【0087】
一方、コンピュータプログラムはまた、サブ平面1000が4つのより小さなサブ平面に細分化された時に、サブ平面1000の中心での適応MIPレイキャスティングを通じてピクセル値P5を発生させる。2つのピクセル値間の絶対差|P5−P5'|は、バイリニア補間の結果がこのサブ平面1000内でいかに正確であるかを示している。例えば、より高い絶対差は、サブ平面が更に細分化する必要があることを意味するばかりでなく、サブ平面内には高周波成分がある可能性があることを示唆している。従って、コンピュータプログラムは、画像化誤差閾値を実質的に下げ、サブ平面内の内部構造の3D特性を完全に捕捉することができる。他方、より小さな絶対差は、サブ平面内の画像が滑らかであり、かつ所定の画像化誤差閾値を相応に大きくして大幅に画像解像度を落とすことなく計算経費を低減することができることを示唆している。
【0088】
オクトリ横縁部検出は、最大データ値を含む識別されたサブボリューム又はセル又はサブセルと、より小さな3Dオブジェクト又は画像ボリュームに埋め込まれた3Dオブジェクトの鋭い縁部を捕捉するための画像平面との間のサイズ差を検査することによって画像化誤差閾値を調節する方法である。
【0089】
簡素化を期すために、図10Bは、少なくとも2つのオブジェクト1140及び1160を含む2Dデータセット1100を示し、2Dデータセットは、N×Nピクセルを含む。データセットの内側には、Lピクセルを含む画像線1120がある。レイ経路1130に沿って、図6に示すような判断基準の少なくとも1つを満足した異なるサイズの一連のサブ平面がある(それぞれ、段階605、609、及び615)。拡大図1180は、コンピュータプログラムがレイ経路1130に沿った最大データ値1190を識別するサブ平面を取り囲む2Dデータセットの詳細を示している。最大データ値を含むサブ平面のフラグメント化レベルがQであると仮定して、小さいオブジェクト又はレイ経路近くのオブジェクトの鋭い縁部の存在を示す因子Zは、以下のように定められる。
【0090】
【数3】
【0091】
Qの値が高くなると(すなわち、より小さなサブ平面)、結果的にZ因子が高くなり、レイ経路1130に沿って一部の小さなオブジェクトがある可能性があることを示唆しており、レイ経路に沿った小さなオブジェクト又は鋭い縁部を見失わないように、相応に所定の画像化誤差閾値を下げるべきである。他方、Qの値が低くなると(すなわち、より大きなサブ平面)、Z因子が低くなり、レイ経路に沿った小さなオブジェクトを識別する可能性が小さいことを示しており、画像線1120上の有意な詳細を失うことなく、所定の画像化誤差閾値を大きくすることができる。尚、Z因子は、レイがデータセットの内側で早期に終了されることなくデータセットを出る時に、所定の画像化誤差閾値を調節する際に有用である。
【0092】
最後に、望ましいフレーム/秒と実際のフレーム/秒との比率に従って所定の画像化誤差閾値を調節することもできる。前者が後者よりも大きい場合は、画像化誤差閾値は、所定の画像解像度の僅かな損失でシステムのデフォルト能力よりも多くの画像フレームをレンダリングすることができるように増大させることができ、そうでなければ、所定の画像化誤差閾値は、前者が後者よりも小さい場合は減少させることができる。
【0093】
コンピュータシステム
上述の適応MIPレイキャスティング方法は、通常のコンピュータシステム内で実施することができ、特別なハードウエアサポートは不要である。図11は、本発明の一部の実施形態によるこのようなシステム1100を示している。適応MIPレイキャスティングシステム1100は、一般的に1つ又はそれよりも多くの中央演算処理装置(CPU)1120と、メモリ1114と、システム1100の様々な構成要素を相互に接続する1つ又はそれよりも多くの通信バス1112とを含む。適応MIPレイキャスティングシステム1100はまた、例えば、3Dデータセットの2D画像を表示する表示装置1106とユーザの画像レンダリング要求を受け取るキーボード1108とを含むユーザインタフェース1104を含む。システム1100は、任意的に、遠隔操作記憶装置からの3Dデータベースを検索するか又はレンダリング結果を遠隔地のクライアントに送出するネットワーク又は他の通信インタフェースを含むことができる。
【0094】
メモリ1114は、高速ランダムアクセスメモリを含み、また、1つ又はそれよりも多くの磁気ディスク記憶装置(図示せず)のような不揮発性メモリを含むこともできる。また、メモリ1114は、中央演算処理装置1102から遠隔に位置する大容量記憶装置を含むことができる。メモリ1114は、以下を格納することが好ましい。
・様々な基本的システムサービスを処理し、かつハードウエア依存のタスクを実行するための手順を含むオペレーティングシステム1116、
・「インターネット」、他の広域ネットワーク、ローカルエリアネットワーク、及びメトロポリタンエリアネットワークなどのような1つ又はそれよりも多くの通信ネットワーク(有線又は無線)を通じて、システム1100を様々なセキュリティ装置又はクライアントコンピュータ(図示せず)及び場合によっては他のサーバ又はコンピュータに接続するのに使用されるネットワーク通信モジュール1118、
・システム1100の作動に必要とされるメモリ1114に記憶された他のモジュール及びデータ構造を初期化するシステム初期化モジュール1120、
・3Dデータセットの2D画像を発生させて表示装置1106上でレンダリングする適応MIPレイキャスティングエンジン、
・3Dデータセット、及びフラグメント化した3Dデータセットを表す対応するオクトリデータ構造、
・2D画像データセット、及びフラグメント化された2D画像を表す複数の対応する四分木データ構造、及び
・3Dデータセットのデータ値を2D画像データセットのピクセル値に変換する画面転送関数表。
【0095】
MIPレイキャスティングエンジン1122は、実行可能な手順、副手順、及び以下のような画像発生手順をサポートする他のデータ構造を含む。
・3Dデータセットを複数のサブボリュームにフラグメント化し、各サブボリュームに対して一組のデータ値パラメータを推定してオクトリデータ構造を構成し、サブボリュームをオクトリデータ構造上の様々なノードに関連付ける3Dデータセットフラグメント化モジュール1124、
・一組の所定の判断基準に基づいてレイと相互作用する一連のサブボリュームを選択し、次にレイ経路に沿った最大データ値を識別する3D適応MIPレイキャスティングモジュール1126、及び
・各々が四分木データ構造に付随する複数のミニ平面に2D画像平面を細分化し、選択的に3D適応レイキャスティングモジュール1126を呼び出して3Dデータセットの2D画像を構成する2D画像レンダリングモジュール1128。
【0096】
図8に示すように、2D画像構成中に、システム1100は、最初に画像平面を複数のミニ平面に細分化し、次に各ミニ平面を再帰的に処理し、バイリニア補間又は必要であれば適応MIPレイキャスティングを通じて画像平面内の全てのピクセルをピクセル値に関連付ける。最後に、単一の2D画像がメモリ1114内に形成される。1つのミニ平面の画像化結果は、別のミニ平面から独立していることから、適応MIPレイキャスティングアルゴリズムは、実際にはパラレルコンピュータ又はコンピュータのクラスター上で実施することができるパラレルアルゴリズムである。
【0097】
図12は、コンピュータクラスター1200を使用する本発明の一実施形態を示している。クラスター1100は、以下を含む。
・1つ又はそれよりも多くの画像ボリュームを格納するデータ記憶装置1210、例えばハードディスク、
・好ましくは1つ又はそれよりも多くのCPUと、MIPレイキャスティングソフトウエアを格納する独自のメモリとを各々が有する複数のコンピュータサーバ1230、
・コンピュータクラスターによって発生した画像を表示するコンピュータモニタ1250、
・指令及びレンダリングパラメータをユーザから受け取るためのキーボード1270及びマウス1290、及び
・様々な構成要素を接続する通信バス1220。
【0098】
説明上、コンピュータクラスター1200内には4つのサーバがあり、各サーバは、部分画像1240で示すような最終画像の1/4の発生を担っている。各サーバ内では、タスクは、サーバ毎に複数のCPUがある場合には異なるCPU間で更に仕切ることができる。全ての部分画像1240が発生した後に、サーバの1つは、部分画像1240を合併して完全な画像にし、モニタ1250上でレンダリングする。
【実施例】
【0099】
図13A及び図13Bは、本発明の一実施形態による適応MIPレイキャスティングを用いて3DのCTスキャンデータセットから発生させた2つの画像の実施例を与えている。2つの画像は、図13Aのピクセル値が所定の画面転送関数に従ってレイ経路に沿って識別したそれぞれの最大データ値に依存するだけであり、一方、図13Bのピクセル値が画像平面と画像ボリューム内の最大データ値の位置との間の距離によって更に重み付け処理されることを除き、実質的には同じものである。その結果、画像ボリュームの異なる部分で識別した同じ最大データ値は、図13Bの画像上で異なるピクセル値を引き起こす可能性があり、見る者に対してある一定の3D透視を提供する。例えば、図13Aの大腿骨の2つの画像部分1320及び1340は、事実上同じ輝度を有し、一方、図13Bの同じ2つの部分1360及び1380は、異なる輝度を有する。特に、部分1360は、部分1380よりも見る者から離れた位置にあることから、部分1380と比較すると若干暗く見える。
【0100】
以上の説明は、説明を目的として特定的な実施形態を参照して行ったものである。しかし、上述の例示的な説明は、網羅的であること又は開示した正確な形態に本発明を限定することを意図していない。多くの修正及び変形が以上の教示の見地から可能である。実施形態は、本発明の原理及びその実際的な用途を最も良く説明し、それによって当業者が予想される特定の使用に適するような様々な修正を用いて本発明及び様々な実施形態を最も良く利用することができるように選んで説明したものである。
【図面の簡単な説明】
【0101】
【図1A】本発明の実施形態の平行投影の概略図である。
【図1B】本発明の実施形態の透視投影の概略図である。
【図1C】異なる画像解像度での3Dオブジェクトの3つの2D画像を示す図である。
【図1D】3Dデータセットによって採取された3Dオブジェクトを示す図である。
【図2】本発明の一実施形態によるMIPレイキャスティングアルゴリズムを示す流れ図である。
【図3A】3Dデータセットフラグメント化の一実施形態を示す図である。
【図3B】8つのセル又はボクセルを含むサブボリュームとボクセル又はセル内のスカラーデータ値分布とを示す図である。
【図4】3Dデータセットフラグメント化のコンピュータ実装を示す流れ図である。
【図5】レイと3Dデータセットのサブボリュームの間の一連の相互作用を概略的に示す図である。
【図6】本発明の実施形態によりレイ経路に沿って最大データ値を識別するためのコンピュータプログラムを示す流れ図である。
【図7】本発明の一実施形態による適応MIPレイキャスティングを示す1D実施例を表す図である。
【図8】コンピュータプログラムが本発明の一部の実施形態に従って2D画像を適応して発生させる方法を示す流れ図である。
【図9】ピクセル値のバイリニア補間の例を示す図である。
【図10A】所定の画像化誤差閾値を調節する2つの方法の一方を示す図である。
【図10B】所定の画像化誤差閾値を調節する2つの方法の他方を示す図である。
【図11】本発明の一実施形態による適応MIPレイキャスティングシステムのブロック図である。
【図12】本発明の一実施形態によりコンピュータクラスターに実装された適応MIPレイキャスティングレンダリングシステムのブロック図である。
【図13】本発明の一実施形態による適応MIPレイキャスティングアルゴリズムの異なるバージョンを通じた人体の2つの画像を示す図である。
【符号の説明】
【0102】
101 2D画像平面
102 放射面
104 レイ
106 画像ボリューム
【技術分野】
【0001】
本発明は、一般的に、ボリュームデータレンダリングの分野に関するものであり、より詳細には、適応データ表現、レイキャスティング、及びデータ補間技術を用いてボリュームデータセットをレンダリングする方法及びシステムに関する。
【背景技術】
【0002】
3Dオブジェクト及び2D画像の内部構造の可視化は、コンピュータグラフィックの分野内の重要な話題であり、医学、地球科学、製造、及び薬物発見を含む多くの産業に応用されている。
【0003】
例えば、CTスキャナは、異なる器官、例えば心臓を含む患者の身体の数百又は数千の平行2D画像スライスを生成することができ、各スライスは、データ値の2Dアレイを含み、各データ値は、特定の部位での身体のスカラー属性、例えば密度を表している。全てのスライスを互いに積み重ねて、心臓が埋め込まれた患者の身体の画像ボリューム又はボリュームデータセットを形成する。心臓の3D構造特性を示す2D画像は、心血管疾患の診断における重要な助けになる。
【0004】
別の例として、石油業界では、地震学的撮像技術を用いて地球内の3D領域の3D画像ボリュームを作り出している。断層又は岩塩ドームのような一部の重要な地質構造は、その領域内に埋め込まれている場合があり、必ずしも領域の表面上とは限らない。同様に、これらの構造の3D特性を完全に示す2D画像は、石油生産を増す上で極めて重要である。
【0005】
最大強度投影(MIP)レイキャスティングは、3D画像ボリュームによって表された中実領域の内部を2D画像平面上、例えばコンピュータモニタ上に可視化するために開発された技術である。一般的に、複数のレイが2D放射面から画像ボリューム内に投射され、各レイキャスティングは、それぞれのレイ経路に沿った画像ボリューム内のボクセルでの最大データ値(例えば、強度)を識別し、それを所定の画面転送機能を通じて2D画像平面上のピクセルでの画像値の中に転送することを担っている。画像値は、レイ経路が遭遇した画像ボリューム内に埋め込まれたオブジェクトの3D特性、例えばそれらの形状及び向きを示している。2D画像平面上のピクセルに付随する画像値は、コンピュータモニタ上でレンダリングすることができる画像を形成する。
【0006】
上述のCTの例に戻ると、医師がいずれかの方向に画像ボリュームを遮ることによって心臓の2D画像スライスを任意に作り出すことができるとしても、どの単一の画像スライスも心臓の表面全体を可視化することはできない。これとは対照的に、CT画像ボリュームのMIPレイキャスティングを通じて作り出した2D画像は、心臓の3D特性を容易に示すことができ、これは、多くの種類の心血管疾患診断において非常に重要である。同様に、石油探査においては、3D地震データのMIPレイキャスティングは、石油技術者が潜在的な油田である領域の地下地質構造の3D特性をより正確に判断して石油生産を大幅に増すことを助けることができる。
【0007】
MIPレイキャスティングは、多くの重要な分野で重要な役割を果たすとしても、MIPレイキャスティング技術の幅広い展開を保証するために克服する必要があるいくつかの技術的課題が存在する。第1に、MIPレイキャスティングは、計算的に高価な処理である。3Dターゲットの3D特性を捕捉することができる高品質2D画像を生成するためには、MIPレイキャスティングでは、大きな3Dデータセットを処理する必要があり、これは、通常は多数の計算を意味する。例えば、5123ボクセルの一般的な3Dデータセットに対して、従来のMIPレイキャスティングアルゴリズムを用いて5122ピクセルの2D画像を生成するのに少なくとも1億4000万回の計算が必要である。
【0008】
更に、多くの用途では、各2D画像が異なる視角又は可視化パラグラフを有する3Dデータセットの連続2D画像をユーザが大きな遅延なく見ることができるように、3DデータセットのMIPレイキャスティングは、リアルタイムで作動することが要求される。医療用撮像においては、毎秒少なくとも6フレームの連続2D画像レンダリングがリアルタイム対話式フィードバックに対する必要性を満たすことが一般的に受け入れられている。これは、毎秒ほほ10億回の計算と同等である。
【0009】
最新コンピュータの限定された計算能力に鑑みて、MIPレイキャスティングの計算コストを低減するためにより効率的なアルゴリズムが開発されてきた。しかし、これらのアルゴリズムの多くは、作り出された2D画像の品質を犠牲にしてその効率を達成している。例えば、連続オブジェクトの個別の表現に関する一般的な問題は、ジッター効果であり、これは、ユーザが連続オブジェクトの更に詳細を見るために拡大した時に最も明白である。ジッター効果が慎重に制御されなかった場合、それは、MIPレイキャスティングアルゴリズムによって作り出された画像の品質を大幅に損なう場合がある。
【0010】
従って、レンダリング効率を増し、同時に画質品質に及ぼす影響がより小さいか又は好ましくは感知できない新しいMIPレイキャスティング方法及びシステムを開発することが望ましいと考えられる。
【発明の開示】
【0011】
本発明の好ましい実施形態は、適応データ表現技術、MIPレイキャスティング技術、及びデータ補間技術を用いて3Dデータセットに埋め込まれた3Dオブジェクトの高品質2D画像を発生させる適応MIPレイキャスティング方法及びシステムである。
【0012】
本方法及びシステムは、最初に、3Dデータセットを異なるサイズの複数のサブボリュームにフラグメント化してデータ構造、例えばオクトリを構成し、オクトリのノードをデータセットの異なるサブボリュームに関連付け、各サブボリュームはまた、サブボリューム内のデータ値分布を特徴付ける一組のデータ値パラメータを有する。特に、データセット全体は、オクトリのルートノードと関連している。
【0013】
本方法及びシステムは、次に、複数のレイを2D放射面から3Dデータセットに向けて投射する。一般的に平行投影と称する一実施形態では、複数のレイは、互いに平行であり、各レイは、2D放射面上に固有のレイ原点を有する。一般的に透視投影と称する別の実施形態では、複数のレイは、全てが同じレイ原点から放出され、各レイは、3Dデータセットに対して固有の放出角を有する。
【0014】
ある一定の断面又はレイ厚み及び所定の現在のデータ値記録を有する各レイは、そのレイ経路に沿って3Dデータセットの一連のサブボリュームと相互作用し、それがレイ経路に沿ってより高いデータ値を識別した時には常に現在のデータ値記録を更新する。具体的には、レイとサブボリュームの間の各相互作用の間に、現在のデータ値記録とサブボリュームに付随する一組のデータ値パラメータとの間で1つ又はそれよりも多くの比較が行われる。現在のデータ値記録がレイ経路上のサブボリュームのボクセルでの、例えばサブボリューム内のレイ経路の中間点でのデータ値よりも小さい場合には、ボクセルでのデータ値は、古い記録と入れ替わって新しい現在のデータ値記録になることになる。この処理は、レイが3Dデータセットを出るか、又はいくつかの所定のレイキャスティング終了条件が満たされてレイ経路上の3Dデータセットの最大データ値記録を識別するまで続けられる。最大データ値記録は、所定の画面転送関数に従って2D画像平面上のピクセル値に変換される。複数のレイに付随する2D画像平面上のピクセル値は、3Dデータセットに埋め込まれた3D内部構造を示す2D画像を構成する。
【0015】
レイと相互作用する適切なサブボリュームの選択に対して2つの競合する要件が存在する。一方では、大きなサブボリュームは、レイキャスティングの計算経費を大きく低減することができて本方法及びシステムがより効率的になり、他方では、小さなサブボリュームは、3D内部構造をより正確に特徴付けることができ、より高い品質の画像が作り出される。本方法及びシステムは、いくつかの所定の条件、例えば、サブボリュームの最大及び最小データ値間の差が所定の閾値よりも小さいことを満足するサブボリュームを選択することにより、これらの2つの競合するゴール間の均衡を取る必要がある。一実施形態では、オクトリのルートノードに付随するデータセット全体が、レイと相互作用するように最初に選択される。しかし、ルートノードに付随するデータ値パラメータの組が、3Dデータセットに埋め込まれた3D内部構造を十分に捕捉するのは稀であるから、データセットをより小さなサブボリュームに更にフラグメント化すべきであることが多く、レイ経路に沿ってレイ原点に最も近い、ルートノードの子ノードに付随するより小さなサブボリュームの1つが次に検査され、それが所定の条件を満足するかが判断される。このフラグメント化及び検査処理は、望ましいサイズのサブボリュームが識別されるまで再帰的に繰り返される。
【0016】
レイと相互作用するサブボリュームを最終的に選択した状態で、本方法及びシステムは、レイ経路上にあるサブボリューム内の特定の位置にあるデータ値を、その特定の位置を取り囲む既知データ値のトリリニア補間を通じて推定する。推定データ値がレイの現在のデータ値記録よりも大きい場合、推定データ値をその新しい現在のデータ値記録としてレイに割り当てる。そうでなければ、レイの現在のデータ値記録はそのままである。それに続いて、レイがまだ3Dデータセット内にある場合、本方法及びシステムは、選択したものの次に適切なサイズでレイ経路に沿って更に遠い別のサブボリュームを識別し、新しい推定最大データ値が判断されて推定が続行される。
【0017】
MIPレイキャスティングアルゴリズムの計算経費及び画像解像度は、主として、2D放射面から投射されるレイの数及び密度によって判断される。最新のコンピュータハードウエアで妥当な期間内に処理することができる限定された数のレイに鑑みて、本方法及びシステムは、2D放射面上のレイ原点の位置を、2D画像平面上のそれらのレイに付随するピクセル値が3Dデータセットに埋め込まれた3D内部構造の特性を有効に捕捉することができるように最適化する。
【0018】
一実施形態では、4つのレイが、最初に2D放射面の4つのコーナから放出される。2D画像平面の4つのコーナでの4つピクセル値を取得した後に、本方法及びシステムは、所定の画像化誤差閾値に照らしてそれらの値の変動を検査する。変動が閾値を超える場合、更に1つのレイを放射面の中心から放出し、それによって2D画像平面を4つのサブ平面に分割する。各サブ平面内のピクセル値の変動は、所定の画像化誤差閾値に照らして更に検査される。変動が閾値を超えるあらゆるサブ平面は、どのサブ平面の変動も閾値よりも小さくなるまで更に再帰的に分割される。
【0019】
最後に、本方法及びシステムは、2D画像平面上の周囲ピクセル値に基づいて、レイに付随しない2D画像平面上の各ピクセルにおける値を推定する。一実施形態では、これらのピクセル値は、所定の画像化誤差閾値を満足した最小サブ平面の4つのコーナにあるピクセル値のバイリニア補間の結果である。
【0020】
本発明の以上の特徴及び利点、並びにその付加的な特徴及び利点は、図面と共に本発明の好ましい実施形態の詳細説明の結果として以下においてより明確に理解されるであろう。
【発明を実施するための最良の形態】
【0021】
図1A及び図1Bは、本発明の2つの実施形態、つまり、平行投影及び透視投影をそれぞれ概略的に示している。直交座標(x、y、z)によって表された3Dドメインにおいては、1つ又はそれよりも多くの3Dオブジェクトを含む画像ボリューム106がある。MIPレイキャスティングでは、複数のレイ104を画像ボリューム106に投射し、2D画像上の3Dオブジェクトの3D特性を可視化するように各レイ経路に沿って最大データ値を識別することによって2D画像を発生させる。尚、本発明の状況におけるレイの形状は1D線ではなく、以下で説明する特定のレイ構成に依存するが3Dチューブ又はコーンである。
【0022】
図1Aに示す実施形態では、複数のレイ104を放射面102上の異なる位置から放出すると、各レイは、他のレイに平行に画像ボリューム106に向けて進む。レイの形状は、レイ厚みとも呼ばれる一定のサイズの断面を有するチューブ103である。異なるレイは、2D画像平面101上の異なるピクセルに対応し、各ピクセル値は、対応するレイ経路上で識別された画像ボリュームの最大データ値によって判断される。このようなMIPレイキャスティング構成は「平行投影」と呼ばれる。平行投影の場合、画像平面101は、レイ経路に沿ってどこにでも位置することができる。説明上、画像平面101は、図1Aに示すように放射面102と一致するものとすることができる。
【0023】
図1Bに示す実施形態では、複数のレイ104を放射面102上の同一レイ原点107から放出し、各レイは、画像ボリューム106に対して固有の透視角を有する。その結果、各個々のレイの形状は、視角108及びレイ原点107と画像ボリューム106との間の距離の両方の関数である可変サイズの断面を有するコーン105である。同様に、異なるレイは、2D画像平面101上の異なるピクセルに対応し、各ピクセル値は、対応するレイ経路上で識別された画像ボリュームの最大データ値で判断される。このようなMIPレイキャスティング構成は「透視投影」と呼ばれる。透視投影の場合、画像平面101は、レイ原点107と画像ボリューム106との間でレイ経路に沿ってどこにでも位置することができる。説明上、画像平面101は、図1Bに示すように放射面102と一致するものとすることができる。
【0024】
一般的に、上述の2つのMIPレイキャスティング構成の一方によって発生した2D画像の画像解像度は、単位面積当たりのピクセル数に依存する。実際には、画像当たりのピクセル総数は、定数、例えば5122であることが多く、これは、コンピュータモニタ上のピクセル数に依存する。従って、レイチューブ103の断面積を小さくすることによって単位面積当たりのピクセル数を多くすることにより、より高い画像解像度が達成され、放射面をレイ経路に沿って画像ボリューム106から離したり又は近づけたりしても画像解像度には影響はない。これとは対照的に、視角108又は距離109又はその両方を小さくすることにより、透視投影においてより高い解像度が達成される。
【0025】
図1Cは、画像解像度がレイ厚みとして変化する様子を示している。簡素化を期すために、各画像は、102=100ピクセルを有し、グリッド110−1、112−1、及び114−1のレイ厚みは、それぞれ、S、4S、及び16Sである。その結果、グリッド114−2上に発生した画像114−2は、最低の解像度を有し、一方、グリッド110−1上に発生した画像110−2は、最高の解像度を有する。平行投影では、放射面のサイズを小さくして放射面上のレイ原点の密度を大きくすることによってこのような拡大効果を達成し、また、透視投影では、放射面を画像ボリューム内の3Dオブジェクトの中心に近づけることによって同じ効果を達成する。
【0026】
画像ボリューム106は、通常、図1Dに示すように3Dデータセット116によって表される。3Dデータセットの各ボクセルは、特定の位置での3Dオブジェクトの物理的属性を示すスカラーデータ値を有する。図1Dに示すように、3Dデータセット116は、3つの直交座標x、y、及びzを有する。各座標に沿って、データセットは、その座標に垂直な2Dデータスライスのスタックを含む。各データスライスは、他の2つの座標に沿って規則的グリッド上のデータ値の2Dアレイを含む。例えば、3つの直交データスライス116−1、116−2、及び116−3は、それぞれ、z、x、及びyの方向で画像ボリューム106の異なる(ただし限定された)遠近感をもたらす。
【0027】
アルゴリズムの概要
本発明の一実施形態によるMIPレイキャスティングは、図2に示すような3つの大きな段階を含む。段階201では、本方法は、画像ボリュームを異なるサイズの複数のサブボリュームにフラグメント化し、一組のデータパラメータに付随する各サブボリュームは、サブボリュームのデータ値分布を特徴付ける。本方法に関する詳細は、図3A、図3B、及び図4に関連して以下に説明する。
【0028】
段階203では、本方法は、画像ボリュームの中心からある一定の距離を隔てて位置し、かつ画像ボリュームに対してある一定の方向に向けられた放射面から画像ボリュームに対して複数回のレイキャスティングを行う。放射面から投射されたレイは、レイ経路に沿って位置する一連のサブボリュームと選択的に相互作用する。レイ経路上の最大データ値を画像平面内のピクセル値に変換する。この処理の更なる詳細は、図5から図7に関連して以下に説明する。
【0029】
段階205では、本方法は、段階203で発生したピクセル値を用いて画像平面内のいずれかの他の位置のピクセル値を推定し、画像ボリュームに埋め込まれた3Dオブジェクトの2D図を呈示する。段階203及び段階205を数回繰返し、より多くのピクセル値を推定することができる。更に、段階203及び段階205を繰返して、放射面の位置又は方向が変わったか又は異なる可視化パラメータが適用された時に一連の新しい画像を発生させることができる。この処理の更なる詳細を図8から図10に関連して以下に説明する。
【0030】
画像ボリュームのフラグメント化
本発明の一実施形態によれば、画像ボリュームをまず一組のサブボリュームにフラグメント化し、各サブボリュームをより小さなサブボリュームに更にフラグメント化する。このような再帰的フラグメント化は、最小サブボリュームが所定のサイズ限界に達するまで続けられる。画像ボリューム全体を含む全てのサブボリュームを階層データ構造に関連付け、これによって元の画像ボリュームの新しい表現が得られる。
【0031】
図3Aは、複数のサブボリューム(例えば、585個のサブボリューム)にフラグメント化された後の3Dデータセット302を示している。これらのサブボリュームは、4つのフラグメント化レベルI、II、III、及びIVに属する。説明上、異なるサイズのサブボリューム、例えば、II−2、III−2、及びIV−2は、より小さなサイズの他のサブボリュームを露出させるために図3Aから除外されている。サイズに基づいて、サブボリュームの各々をオクトリデータ構造304の1つのノードに関連付ける。尚、説明を簡素化するために、サブボリュームの小さな部分集合のみをオクトリ304に示している。
【0032】
フラグメント化レベルIから始まって、データセット302全体は、単一のサブボリュームI−1として処理され、オクトリ304のルートノードに関連する。フラグメント化レベルIIでは、データセット302は、仕切られて同じサイズの8つのサブボリュームにされ、各サブボリューム、例えば、II−6をオクトリ304のレベルIIの1つの中間ノードに関連する。フラグメント化レベルIIIでは、サブボリュームII−6のような各サブボリュームは、更に8つのより小さなサブボリュームIII−1、III−2、...、及びIII−8に分割され、同様に、各サブボリューム、例えばIII−6は、レベルIIIの中間ノードに関連する。フラグメント化レベルIVでは、サブボリュームIII−6のような各サブボリュームは、仕切られて8つのサブボリューム(サブボリュームIV−6を含む)にされ、レベルIVの各サブボリュームは、オクトリ304の葉ノードに関連する。レベルIには80個のサブボリュームがあり、レベルIIには81個のサブボリュームがあり、レベルIIIには82個のサブボリュームがあり、レベルIVには83個のサブボリュームがあることから、データセット302を4つの異なるフラグメント化レベルで合計で、
80+81+82+83=1+8+64+512=585
個のサブボリュームにフラグメント化する。
【0033】
サブボリュームは、サブボリューム内のデータ値分布を特徴付ける複数の組のデータパラメータを有する。一実施形態では、その組のパラメータには、少なくとも3つの要素が含まれる:
・サブボリューム内のデータ値の最小値を表すVmin、
・サブボリューム内のデータ値の平均を表すVavg、及び
・サブボリューム内のデータ値の最大値を表すVmax
【0034】
図3Aに示すように、画像ボリュームフラグメント化は再帰的手順である。この手順は、最小サブボリュームが指定のサイズ限界に達するまで終わらない。一実施形態では、この指定のサイズ限界又はオクトリ葉ノードに付随する最小サブボリュームは、画像ボリュームの2×2×2セル又はボクセルを有するサブボリュームである。セル又はボクセルは、付随のデータ値を有する画像ボリュームの最小単位である。例えば、画像ボリュームがMIPレイキャスティングでは一般的である5123個のセルを有し、かつ最小サブボリュームが2×2×2セルを有する場合、画像ボリュームフラグメント化処理は、フラグメント化レベルIVまで続くと、最小サブボリュームの数が2563である。
【0035】
図3Bは、2つのセル又はボクセルが3つの直交方向の各々に互いに隣り合う8つのセル又はボクセルを有するサブボリューム306を示している。ボクセル308は、1つの採取データ値、例えばV0に中心がある立方体である。ボクセル内のデータ値は、一定であると仮定し、ボクセルの境界に沿ってデータ値の不連続があるとすることができる。これとは対照的に、セル310は、立方体の各コーナに1つがある8つの採取データ値V1からV8を有する同じサイズの立方体である。一実施形態によれば、セルのあらゆる点のデータ値は、トリリニア補間によって推定し、セルの境界に沿ってはデータ値の不連続はない。尚、本発明は、いずれのフォーマット、セル、又はボクセルにおいて表される画像ボリュームにも等しく適用される。簡素化を期すために、以下で説明する内容は、一例としてセル表示に焦点を当てるものである。
【0036】
再び図3Bを参照すると、原点がセル310の中心にある3D直交座標があり、セルの3つの直交する縁部の長さは、それぞれ、Dx、Dy、及びDzである。セル310のいずれかの点V(x、y、z)でのデータ値は、以下のように、セル310の8つのコーナでのデータ値V1からV8の関数としてトリリニア補間によって表すことができる。
【0037】
【数1】
【0038】
図4は、上述の画像ボリュームフラグメント化並びオクトリ構造のコンピュータプログラムを要約した流れ図である。段階401では、コンピュータプログラムは、3Dデータセットを受け取り、3Dデータセットをオクトリのルートノードと関連付けることにより、オクトリデータ構造を初期化する。段階403では、データセットを8つのサブボリュームにフラグメント化し、各サブボリュームが8つの子ノードに関連付けられるように、8つの子ノードをルートノードで発生させる。
【0039】
段階405から始まって、最小サブボリュームが指定のサイズ限界に達するまで、各サブボリュームをより小さなサブボリュームに再帰的にフラグメント化する。段階405では、コンピュータプログラムは、最初に、サブボリュームのサイズが指定のサイズ限界、例えば、2×2×2セルのサブボリュームに達したかを検査する。達していない場合、段階407では、サブボリュームを8つのより小さなサブボリュームにフラグメント化する。8つのより小さなサブボリュームの1つを拾うと、再帰的フラグメント化が段階405で再び始まる。
【0040】
サブボリュームのサイズが指定のサイズ限界、例えば、2×2×2セルに達した場合、コンピュータプログラムは、段階409でこのサブボリュームをフラグメント化するのを止め、サブボリュームに付随するオクトリのノードは、オクトリの葉ノードの1つである。段階411では、コンピュータプログラムは、2×2×2セルまでフラグメント化されていない他のサブボリュームがあるかを検査する。ある場合には、上述のサブボリュームの1つを選択して、再帰的フラグメント化が段階405で続けられる。ない場合には、画像ボリュームフラグメント化を終了する。
【0041】
上述のように、各サブボリュームは、2D放射面上のピクセル値を推定するための(Vmin、Vavg、Vmax)のような一組のデータパラメータに関連付けられる。一実施形態では、3Dデータセットをフラグメント化してオクトリを構成した後に、コンピュータは、オクトリの葉ノードレベルから始まり、図3AのサブボリュームIV−6のような葉ノードに付随するサブボリュームの対応する(Vmin、Vavg、Vmax)を計算する。葉ノードに付随するサブボリュームは、8つのセルのみを含み、かつ、各セルは、大半は2つ又はそれよりも多くのセルによって共有される8つのデータ値を有することから、コンピュータプログラムは、記憶装置、例えば、ハードディスクから27個のデータ値を検索し、サブボリュームの(Vmin、Vavg、Vmax)を計算する必要があるだけである。
【0042】
葉ノードレベルの全てのサブボリュームを処理した後に、コンピュータプログラムは、オクトリ304上でレベルを1つ上げ、中間ノードに付随するIII−6のようなサブボリュームの対応するパラメータを計算する。この処理は、ルートノードに達するまで続けられる。各中間ノードは、8つの子ノードを有し、各子ノードは、付随のデータパラメータが既に前に求められているサブボリュームに付随するものであることから、この中間ノードの各データ値パラメータを8つの子ノードに付随する8つのパラメータの関数として表すことができる。
・Vmin=Min(Vmin_1,Vmin_2,...,Vmin_8)、
・Vavg=(Vavg_1+Vavg_2+...+Vavg_8)/8、及び
・Vmax=Max(Vmax_1,Vmax_2,...,Vmax_8)
【0043】
以下で明らかになるように、データ値パラメータのこの発生は、図3Aに示すように上から下にルートノードレベルで始まるオクトリ構造と反対の方向に進む。データパラメータ発生のこの下から上の手法は、オクトリのより低いレベルにある計算結果を最大に再利用することから最も効率的である。
【0044】
段階201では、元の画像ボリュームの新しい表現がMIPレイキャスティングの段階203に利用可能である。この表現は、オクトリ及び異なるサイズの複数のサブボリュームを含み、オクトリの1つのノードに付随し、かつ一組のデータパラメータを有する各サブボリュームは、サブボリューム内のデータ値分布を特徴付ける。
【0045】
3D適応MIPレイキャスティング
MIPレイキャスティングは、画像ボリュームに埋め込まれた内部3D構造を示す2D画像を発生させるアルゴリズムであり、ピクセルからのレイを画像ボリュームに投射し、レイ経路に沿った最大データ値を識別し、所定の画面転送関数に従って最大データ値をピクセル値に変換することによって2D画像の各ピクセル値を推定する。本発明の一実施形態によれば、効率的な3D適応MIPレイキャスティングアルゴリズムは、以下の3つの段階を含む。
・段階1:アルゴリズムは、所定の現在のデータ値記録及びある一定の断面を有するレイの数学的モデルを構成して3Dオブジェクトを個別の3Dデータセットとして表し、データセットの各データ値は、オブジェクトの特定の位置でのこのような物理特性を表す。
・段階2:アルゴリズムは、レイ経路に沿った一連のデータ値を一度に1つレイの現在のデータ値記録と比較し、より高いデータ値が識別された場合は現在のデータ値記録を入れ替える。
・段階3:アルゴリズムは、所定の画面転送関数に従ってレイ経路に沿った最高データ値でもあるレイの最終データ値を2D画像上のピクセル値に変換する。
【0046】
画面転送関数は、一般的に、3Dデータセットに埋め込まれた内部構造の異なる態様を解明するために任意に選択された単調関数である。図5は、MIPレイキャスティングで使用することができる画面転送関数である。垂直軸は、2D画像上のピクセル値の大きさを示し、水平軸は、3Dデータセットのデータ値のマグニチュードを示している。画面転送関数を3つの部分に分割することができる。Vlowよりも小さい一切のデータ値は、一定のピクセル値Plowに対応し、Vhighよりも大きな一切のデータ値は、一定のピクセル値Phighに対応し、VlowとVhighの間の一切のデータ値は、PlowとPhighの間にあるピクセル値Piに対応する。
【0047】
図6は、コンピュータプログラムが本発明の一実施形態に従って特定のレイ経路に沿った画像ボリュームの最高データ値を識別する方法を示す流れ図である。画像ボリュームは、既に図3Aに示すようにオクトリに付随する複数のサブボリュームにフラグメント化されており、一組のデータパラメータ(Vmin、Vavg、Vmax)を有する各サブボリュームは、データ値分布を特徴付けることから、コンピュータプログラムは、効率を目的として、オクトリのルートノードに付随する画像ボリューム全体に対して識別処理を開始する。
【0048】
段階601では、コンピュータプログラムは、2D放射面から放出した複数のレイからレイを選択し、そのレイは、2D放射面上の原点と、画像ボリュームに対する特定の向きと、初期の現在のデータ値記録Vrecとを有する。一実施形態では、Vlowよりも低い一切のデータ値は、2D画像上の同じピクセル値Plowに対応することから、図5に示すように、画面転送関数のVlowになるように初期の現在のデータ値記録を設定する。図7に関連して以下で説明するように、この手法は、オクトリデータ構造に適用した時に、かなりの量の画像ボリュームを識別処理から排除することができ、識別処理がより効率的になる。
【0049】
段階603では、コンピュータプログラムは、オクトリデータ構造からレイに初めて遭遇する最大サブボリュームを選択し、このサブボリューム内のレイ経路がレイの現在のデータ値記録Vrecよりも高いデータ値を有する点を含むかを検査する。デフォルトにより、段階603で選択される第1のサブボリュームは、常に付随の組のデータ値(Vmin、Vavg、Vmax)を有する画像ボリューム全体である。しかし、図6に示すように、コンピュータプログラムは、一部の条件が満たされた場合は、段階608又は609を完了した後に段階603に再度行くことができる。この場合、コンピュータプログラムは、オクトリデータ構造に付随する少なくとも1つのサブボリュームを検査済みであるはずであり、段階603で選択したサブボリュームは、画像ボリューム全体ではなく、レイが出たばかりのサブボリュームの空間的に隣接するサブボリュームになる。
【0050】
上述のように、コンピュータプログラムのゴールは、画像ボリューム内でレイ経路上にある最高データ値を識別することである。しかし、画像化誤差を低減するために、並びに識別処理を促進させるために、段階603で選択したサブボリュームは、Vrecよりも高い少なくとも1つのデータ値、例えば、Vrec<Vmaxを有することだけの理由により、レイの現在のデータ値記録のより高い値との入れ替えは行わない。むしろ、サブボリュームは、レイの現在のデータ値記録を入れ替えるために以下の3つの判断基準を満足すべきである。
・サブボリューム最大データ値Vmaxは、レイの現在のデータ値記録Vrecよりも高くなければならない(段階605)、
・サブボリューム内の最大画面値差(MSVD)は、所定の閾値を下回らなければならない(段階609)、及び
・サブボリューム内のレイ経路上の所定の位置、例えば、サブボリューム内のレイ経路の中点のデータ値Vestは、レイの現在のデータ値記録Vrecよりも高くなければならない(段階615)。
【0051】
段階605では、コンピュータプログラムは、レイの現在のデータ値記録Vrecを段階603で選択したサブボリュームのサブボリューム最大データ値Vmaxと比較する。Vrec>Vmaxの場合、レイの現在のデータ値記録が更新される機会はない。従って、コンピュータプログラムは、このサブボリュームを排除し、レイは、サブボリュームを出た時の現在のデータ値記録を維持する。尚、レイは、サブボリュームを出た直後に画像ボリューム全体を通過したと考えられる。従って、コンピュータプログラムは、段階608では、これがレイ経路上の最終サブボリュームであるかを検査する。そうである場合、コンピュータプログラムは、レイキャスティングを止め、レイの現在のデータ値記録Vrecをレイ経路に沿った最高データ値と処理することになり、次に、この最高データ値を2D放射面上の対応するピクセル値を推定するのに使用する。そうでなければ又はVrec<Vmaxの場合には、値がレイの現在のデータ値記録よりも高い少なくとも1つの位置がサブボリューム内にある。しかし、このボクセルをVrecを更新するのに使用することができるか否かを判断するためには、コンピュータプログラムによって取られるいくつかの更に別の段階が必要である。
【0052】
段階607では、コンピュータプログラムは、所定の画面転送関数(STF)を用いてサブボリュームの最大画面値差(MSVD)を推定する。サブボリュームのMSVDは、2D放射面上のピクセル値変動に及ぼすサブボリューム内のデータ値変動の影響を示している。一実施形態では、サブボリュームの付随のデータパラメータVmin、Vavg、Vmax、及び現在のデータ値記録Vrecのマグニチュードにより、サブボリュームのMSVDは、以下のように若干異なる定義を有する場合がある。
・Vrec<Vminの場合、MSVD=MAX(STF(Vmax)−STF(Vavg),STF(Vavg)−STF(Vmin))、
・Vmin<Vrec<Vavgの場合、MSVD=MAX(STF(Vmax)−STF(Vavg),STF(Vavg)−STF(Vrec))、又は
・Vavg<Vrec<Vmaxの場合、MSVD=STF(Vmax)−STF(Vrec)
【0053】
識別処理の目的は、画像ボリューム内のレイ経路上の最高データ値を識別することであることから、値が現在のデータ値記録Vrecよりも小さいサブボリュームのあらゆるボクセルは、サブボリュームのMSVDの推定には関係がないはずである。一方、Vavgは、サブボリューム内のデータ値分布全体を特徴付けるという点においてVmax及びVminよりも正確であり、Vavg並びVmax及びVminを伴うMSVD定義では、Vmax及びVminを伴うだけのMSVD定義よりも正確な画像を生成することができる。一部の代替的実施形態では、平均データ値Vavgは、中央データ値Vmedで入れ替えることができる。中央データ値は、サブボリュームデータ値の一方の半分よりも高く、サブボリュームのデータ値の他方の半分よりも低いデータ値である。
【0054】
段階609では、コンピュータプログラムは、推定MSVDを所定の閾値と比較する。推定MSVDが閾値を超える場合、コンピュータプログラムは、オクトリデータ構造に沿って現在サブボリュームに付随するノードから段階的に下り、子ノードの1つに付随するより小さなサブボリュームを選択する(段階611)。子ノードに付随する複数のより小さなサブボリュームの中で、コンピュータプログラムは、他の全てのサブボリュームの先にあるレイに遭遇するものを選択し、次に、段階605に戻って新たに選択したサブボリュームが段階609での試験に合格するのに十分に小さいか否かを判断する。尚、新たに選択したサブボリュームは、固有の組のデータパラメータ(V’min、V’avg、V’max)を有し、特に、最大データ値V’maxは、親ノードの最大データ値Vmaxよりも小さいとすることができる。V’max<Vrecの場合、コンピュータプログラムは、このより小さなサブボリュームを飛び越して、上述のように段階608に移動することになる。
【0055】
段階605から段階611を含むループ後に、コンピュータプログラムは、例えば2×2×2セルを有する最小サブボリュームに付随するオクトリデータ構造の葉ノードに到達することができる。最小サブボリュームがまだ段階609で試験に合格しない場合、コンピュータプログラムは、8つのセルの1つを選択するか又はセルを8つのサブセルにフラグメント化し、次に、段階609で試験に合格するようにサブセルの1つを検査することができる。図3Bに示すように、例えば、トリリニア補間を通じて8つのコーナでの8つのデータ値を用いてセル又はサブセル内のいずれかの点でのあらゆるデータ値を推定することができる。他方、レイは、一部の実施形態によれば、ある一定の断面を有するチューブ又はコーンであると見なされる。従って、セル内のフラグメント化は、ある一定の段階では、例えば、サブセルのサイズが断面内のレイの断面よりも小さい場合は停止すべきである。これが発生すると、コンピュータプログラムは、段階609での試験が満足されたと仮定して自動的に段階613に進むことができる。
【0056】
段階609での試験が満足されたか又はサブボリューム(又はセル又はサブセル)のMSVDが所定の閾値よりも小さいと仮定して、コンピュータプログラムは、次に、現在のデータ値記録Vrecをサブボリューム内のレイ経路上の1つの地点にある推定データ値Vestと比較し、VrecをVestで更新すべきか否かを判断する。一部の実施形態では、サブボリューム内のレイ経路の中心点をこの比較のために選択し、一部の他の実施形態では、コンピュータは、レイがサブボリュームに入る/出る位置のような位置を選択することができる。選択した位置が正確にはセルの1つのコーナではないことが多いことから、コンピュータプログラムは、指定の位置にあるデータ値Vestを補間すべきである。これを行うために、コンピュータプログラムは、段階613では、最初にどのセルが選択した位置を含むか否かを判断し、次に、コンピュータメモリ又はハードディスクからセルの8つのコーナにあるデータ値を検索し、例えば、トリリニア補間を通じてセルの位置にあるデータ値Vestを推定する。
【0057】
Vrec>Vest(段階615で「ノー」)の場合、レイは、現在のサブボリュームを出ると同時に現在のデータ値記録を維持する。尚、レイがサブボリュームを出る時には常に、コンピュータプログラムは、段階608でレイも画像ボリューム全体を出たかを検査すべきである。Vrec<Vest(段階615で「イエス」)の場合、コンピュータプログラムは、段階617で現在のデータ値記録VrecをVestと入れ替え、Vestは、レイの現在のデータ値記録になる。次に、コンピュータプログラムは、図5に示すように、Vhighを超えるデータ値記録が対応するピクセル値Phighに影響を与えないために、段階619でレイの現在のデータ値記録を画面転送関数のVhighと比較する。Vrec>Vhighの場合、レイキャスティングを続ける必要がないので、コンピュータプログラムは、この特定のレイに対してレイキャスティングを直ちに終了する。そうでなければ、レイキャスティングが続行される。しかし、レイはサブボリュームを出たばかりであることから、コンピュータプログラムは、段階603でレイキャスティングを再開する前に、最初にレイが画像ボリューム全体の外側にあるか否かを判断する。
【0058】
図6に示す適応MIPレイキャスティングアルゴリズムは、本質的には、レイ経路に沿ったサブボリュームのシーケンスを選択し、レイ経路に沿った最高データ値を有するサブボリュームの1つにおける1つの位置を識別する手順である。異なるサブボリュームがオクトリデータ構造の異なるノードに付随し、かつ異なる組のデータパラメータ(Vmin、Vavg、Vmax)によって特徴付けられることから、アルゴリズムは、MIPレイキャスティング(例えば、段階605で)のゴールに関連のないサブボリュームを適切に排除して計算経費を大幅に低減することができる。
【0059】
図7は、任意に分布させたデータ値のグループ間で最高値を有するボクセルを図6に示す実施形態に従って識別する際にアルゴリズムが作業する方法を示す1D実施例を示すものである。尚、1Dにおけるゴールは、アルゴリズムの2D又は3Dバージョンが、異なるサブボリューム内のレイ経路の異なる部分上のデータ値のシーケンスを推定してその間で最高値を識別する必要があるために、2D又は3Dにおけるゴールよりも達成しやすい。これとは対照的に、最高データ値は、アルゴリズムの1Dバージョンには既知のものであり、未知のものはこの最高値の位置であり、一方、レイ経路上の最高値の位置は、2D又は3Dバージョンのアルゴリズムの関心事ではない(たとえ容易に入手可能であっても)。
【0060】
この例においては、水平軸に沿って16個のデータサンプル、AからPがある。例えば、サンプルAは100、サンプルJは221、サンプルNは83であるなどである。直観的な手法は、最初に現在のデータ値記録に任意の値(例えば、108)を割り当て、次に、16個全てのデータサンプルと1つずつ比較することである。サンプルがより高い値を有する場合、現在のデータ値記録は、より高い値と入れ替えられる。この処理は、最終サンプルPが検査されて最高値を有するサンプルがサンプルI(227)であると識別されるまで続けられる。
【0061】
明らかに、この直観的手法の計算経費はO(N)であり、Nは、データサンプル数である。M2グループのデータサンプル(2D画像を発生させるのに必要とされるM2レイキャスティングと類似)がある場合、総計算経費は、O(NM2)になる。Nが非常に小さい数字である場合、この手法は、成功するであろう。しかし、現実の用途、例えばCTスキャン画像ボリュームにおいては、Nは、大きな数字(例えば、数百又は千を超えさえもする)であることが多く、O(NM2)は、ほとんどのコンピュータシステムでは処理できないほど大きなものになる。
【0062】
代わりに、16個のデータサンプルの各々が二進ツリー700の16個の葉ノードの1つに関連するように、5レベル二進ツリー700を構成する。ルートノード740を含む二進ツリー700の全ての非葉ノードは、この非葉ノードの子孫である葉ノードでの最小データ値、平均データ値、及び最大データ値を示す一組のデータパラメータ(Vmin、Vavg、Vmax)と関連する。例えば、ノード720は、付随の値がそれぞれ100及び125である2つの葉ノードのみを有することから、一組のデータパラメータ(100、112、125)を有し、ルートノード740は、16個全ての葉ノードが子孫であり、16個の葉ノードの中で葉ノードIが最高値227を有し、葉ノードL及びMが最低値58を有するので、一組のデータパラメータ(58、138、227)を有する。
【0063】
初期データ値記録は、それぞれ、Vrec=180、Vlow=180、Vhigh=220であると仮定すると、所定の閾値TMSVD=10であり、画面転送関数STF(V)=V<Vlowであれば180、又はVlow<V<VhighであればV、又はVhigh<Vであれば220である。段階603に従ってルートノードを選択してVrecと比較する。Vrec(180)がルートノードのVmax(227)よりも小さいことから、180よりも高い付随値を有する16個のサンプルの少なくとも1つがある。従って、ルートノードのMSVDを段階607に従って(STF(Vmax)−STF(Vrec))=227−180=47のように推定する。これは、Vrec(180)がルートノードのVavg(138)よりも大きいからである。MSVD(47)は、TMSVD(10)よりも大きいことから、コンピュータプログラムは、段階611に従って1つレベルを下げて子ノードの1つに行くことにより、葉ノードのサブグループを検査すべきである。子ノード760のVmaxは、現在のデータ値記録Vrec(180)よりも小さい171のみであることから、段階605に従って子ノード760の子孫である8つの葉ノードのいずれも考察する必要はない。代わりに、子ノード780が選択されるが、その理由は、それが子ノード760の隣にあり、かつそのVmax(227)がVrec(180)よりも大きいからである。この処理は、上述の3つ全ての判断基準を満足するノード784が識別され、かつ現在のデータ値記録(180)と入れ替えるために葉ノードIでの値(227)が選択されるまで続けられる。尚、検査していない葉ノードがまだ6つ(KからP)あっても、現在のデータ値記録Vrec(227)がVhigh(220)よりも高く、かつ、より高い値があっても得られるピクセル値には影響を与えないので、これ以上の検査の必要はない。従って、コンピュータプログラムは、段階619に従ってこの処理を適切に終了することができる。
【0064】
数学的には、上述の二進ツリーによる手法の計算経費は、データサンプルの分布が不規則である場合はO(log2N)のみであり、直観的手法O(N)の計算経費よりも大幅に低い。上述のように、3Dデータセットを複数のサブボリュームにフラグメント化して各サブボリュームをオクトリデータ構造のノードに関連付けることによってアルゴリズムを3Dまで拡張した時に、計算経費は、大幅に落ちる可能性がある。
【0065】
段階609で適応MIPレイキャスティングに使用した所定の閾値は、アルゴリズムの効率及び精度に影響を与えるパラメータである。所定の画面転送関数が与えられると、閾値は、試験に合格することができるサブボリュームを見つけるまで段階609で検査するのにコンピュータプログラムがいくつのサブボリュームを必要とするかを決めるものである。すなわち、閾値が大きいほど、アルゴリズムは効率的になる。一方、段階613でのアルゴリズムは、任意に選択した位置、例えば、サブボリューム内のレイ経路の中心点でのデータ値を推定し、この推定値をサブボリューム内のレイ経路上の最大データ値として処理して段階615で現在のデータ値記録と比較する。しかし、この任意に選択した位置は、データ値がサブボリューム内のレイ経路上のピークに到達する正確な位置ではない可能性がある。より小さな閾値は、段階609での試験に合格することができるより小さなサブボリュームに変換され、従って、任意に選択した位置と正確な位置との間の誤差が小さくなる。実際には、コンピュータプログラムは、適切な閾値を選択することにより、これらの2つの競合するゴール、又は効率と精度を両立させなければならない。
【0066】
一実施形態によれば、段階609で使用した閾値は、静的な値ではなく、妥当な経費で最適な結果を発生させるために画像間で変わる動的な値である。E0をユーザが定める初期閾値であると仮定して、カスタマイズされた閾値を以下のように定める。
・平行投影の場合、Pzoomを画像の物理的サイズを示すズーム因子とすると、E(E0,Pzoom)=E0/Sqrt(Pzoom)、及び
・透視投影の場合、Pdistanceをレイ原点と画像ボリュームの中心との間の距離とすると、E(E0,Pdistance)=E0*Log2(Pdistance)
【0067】
平行投影の場合にズーム因子Pzoomを大きくすると、閾値が小さくなり、コンピュータプログラムは、レイ経路に沿った最大データ値を識別する前により多くのサブボリュームを試験する必要があり、解像度が高く、かつジッター効果が小さくなった画像が作り出される。これとは対照的に、透視投影の場合にレイ原点と画像ボリュームとの間の距離Pdistanceを大きくすると、画質に逆効果を与える。
【0068】
画質以外に、使い易さは、適応MIPレイキャスティングアルゴリズムを評価する時の別の要素である。例えば、放射面を画像ボリュームに対して位置決めする時間と画像をコンピュータモニタ上でレンダリングする時間との間のいかなる時間間隔も、心血管疾患診断のような動的画像化用途において望ましくないものである。このような時間遅延を小さくし、ユーザに対して診断処理中により多くの制御を与えるために、一実施形態では、以下のように、望ましいフレーム/秒(DFPS)と実際のフレーム/秒(AFPS)との間の比率によって所定の閾値を調節することができる。
・平行投影の場合、E(E0,Pzoom,DFPS,AFPS)=E(E0,Pzoom)*DFPS/AFPS、及び
・透視投影の場合、E(E0,Pdistance,DFPS,AFPS)=E(E0,Pdistance)*DFPS/AFPS
【0069】
その名称が示すように、DFPSは、ユーザが好む画像レンダリング速度であり、一方、AFPSは、コンピュータハードウエア、放射面上のピクセル数、及び処理される画像ボリュームのような画像化システムの設定値によって限定される画像レンダリング速度である。好ましい画像レンダリング速度がシステムによって提供される画像レンダリング速度よりも大きい場合、閾値は、相応に大きくなるべきである。その結果、閾値を大きくすると、画質に妥協して処理することにより、ユーザが好む画像レンダリング速度が達成される。他方、好ましい画像レンダリング速度がシステムが与えることができる画像レンダリング速度よりも小さい場合、システムは、閾値を小さくして、ユーザが許容可能な速度におけるより高品質な画像を発生させるための付加的な機能を有することができる。
【0070】
2D画像の推定
3DMIPレイキャスティングでは、画像ボリューム内のレイ経路に沿った最大データ値を識別し、次に、所定の画面転送関数に従ってそれを2D画像平面上の特定の位置のピクセル値に変換する。3DMIP適応レイキャスティングは、計算上高価な作動であることから、アルゴリズムの効率は、実質的にレイキャスティングを通じて発生させなければならない画像平面上のピクセル値の数に依存する。図8は、コンピュータプログラムが画像平面上のどのピクセル値を適応MIPレイキャスティング方法を通じて発生させる必要があるかを適応して判断する方法、及びどのピクセル値を発生したピクセル値を用いて画質に対して感知不能でないならば無視可能な影響で推定することができるかを示す流れ図である。
【0071】
段階801では、コンピュータプログラムは、図1A及び図1Bに示すように、画像ボリュームから隔てたある一定の距離であり、かつ画像ボリュームに対してある一定の方向に向けられた2D画像平面を構成する。画像平面は、通常、M×M(例えば、512×512)要素を含むコンピュータメモリ内の2Dアレイによって表され、2Dアレイの各要素は、画像平面上の対応する位置の1つのピクセル値を格納する。
【0072】
段階803では、コンピュータプログラムは、画像平面を同じサイズの複数のミニ平面に細分化し、各ミニ平面は、2Dアレイの一部分に対応し、かつP×P(例えば、16×16)ピクセルを含む。一実施形態では、ミニ平面は、四分木データ構造のルートノードに関連する。
【0073】
段階805では、段階803で作成した各ミニ平面に対して、コンピュータプログラムは、4回の別々の適応MIPレイキャスティングを行い、ミニ平面の4つのコーナにある4つのピクセル値を推定する。
【0074】
段階807から始めて、コンピュータプログラムは、この再帰的処理が終わると画像ボリュームの2D画像が2Dアレイ内に形成されるように、2Dアレイの全ての要素をピクセル値で再帰的に満たす。一実施形態では、コンピュータプログラムは、各々が四分木データ構造の1つの子ノードに付随する複数のより小さなサブ平面にミニ平面を細分化し、適応MIPレイキャスティング又は補間法を通じてサブ平面の各ピクセルにピクセル値を割り当てる。より詳細には、コンピュータプログラムは、最初に、段階807で処理されていないミニ平面があるか否か、すなわち、ピクセル値なしに少なくとも1つのピクセルを含むミニ平面があるかを検査する。ない場合には、画像平面の全てのピクセルには、ピクセル値が既に割り当てられており、コンピュータプログラムは終了する。ある場合には、コンピュータプログラムは、段階809で処理されていないサブ平面がないかに関して、段階807で識別したミニ平面に関連する四分木データ構造を検査する。
【0075】
四分木データ構造に関連する全てのサブ平面が処理された場合、コンピュータプログラムは、段階807に戻って次のミニ平面を処理する。そうでない場合、コンピュータプログラムは、段階811でサブ平面を識別し、このサブ平面が2×2ピクセルのみを含むかを検査する。2×2ピクセルのみを有するサブ平面は、サブ平面を細分化することができる最小サブ平面である。一実施形態では、コンピュータプログラムは、段階813で適応MIPレイキャスティングを通じて、段階811で識別したサブ平面上のあらゆるピクセルに対してピクセル値を推定する。段階811で識別したサブ平面が2×2ピクセルよりも大きい場合、コンピュータプログラムは、更に別の実験を実施してサブ平面をピクセル値で埋める方法を決めるべきである。
【0076】
段階815では、コンピュータプログラムは、最初にこのサブ平面の最大ピクセル値差(MPVD)を推定する。名称が示すように、MPVDは、サブ平面内のピクセル値分布を測るものである。一実施形態では、MPVDは、以下のように定められる。
MPVD=MAX(|Pavg−P1|,|Pavg−P2|,|Pavg−P3|,|Pavg−P4|)/S
ただし、Sは、サブ平面内のピクセル総数であり、P1からP4は、サブ平面のコーナのピクセル値であり、Pavgは、以下のようにP1からP4の平均である。
Pavg=(1/4)(P1+P2+P3+P4)
【0077】
一部の他の実施形態では、平均ピクセル値Pavgは、MPVDを推定するためにサブ平面の中央ピクセル値Pmedと入れ替わることができる。関連のピクセル値を有していないサブ平面内の残りのピクセルを満たす方法を判断するために、MPVDを所定の画像化誤差閾値と比較する。
【0078】
一般的に、補間は、適応MIPレイキャスティングよりも効率的な代案であり、従って可能な限り使用すべきである。他方、適応MIPレイキャスティングを通じて発生したピクセル値は、補間を通じて発生したものよりも正確である。2D画像の異なる部分は、画像ボリューム内の異なる3D構造を捕捉して異なるレベルの画像解像度を必要とする可能性があることから、2D画像に沿った汎用画像化誤差閾値は、最も好ましい選択肢ではない。
【0079】
代わりに、段階817では、コンピュータプログラムは、画像ボリュームの異なる部分を処理する時に閾値を選択的に調節する。例えば、コンピュータプログラムは、ある一定の3D内部構造、例えば医療画像化における骨の縁部に対応する場合がある2D画像の部分をレンダリングする時により小さな所定の画像化誤差閾値を選択すべきであり、これは、その後、強制的にサブ平面をより小さなサブ平面にフラグメント化させ、その結果、補間ではなく適応MIPレイキャスティングを通じてサブ平面内により多くのピクセル値を発生させる必要がある。所定の画像化誤差閾値修正のカスタマイズ化に関する更なる詳細は、図10に関連して以下に与えられている。
【0080】
段階819では、コンピュータプログラムは、サブ平面のMPVDがカスタマイズされた画像化誤差閾値を超えるかを検査する。超えない場合、コンピュータプログラムは、最初に、適応MIPレイキャスティングを通じてサブ平面の中心にあるピクセル値を推定し、次に、段階823で各々が四分木データ構造の子ノードに付随する複数のより小さなサブ平面にサブ平面を細分化する。MPVDがカスタマイズされた画像化誤差閾値よりも高い場合、コンピュータプログラムは、段階821で既存のピクセル値の補間を通じてあらゆる満たされていないピクセルに値を割り当てる。一実施形態では、サブ平面のコーナにある4つのピクセル値のバイリニア補間によってサブ平面内のピクセル値分布を推定する。図9に示すように、いずれかの位置(x,y)のピクセル値P(x,y)は、以下のようにバイリニア補間することができる。
【0081】
【数2】
【0082】
段階821又は823後に、コンピュータプログラムは、段階809に戻って次のサブ平面があれば処理する。この処理は、2Dアレイの全ての要素に、3D適合レイキャスティング又はバイリニア補間によって作り出された画像平面上の1つの位置に対応するピクセル値が割り当てられるまで続けられる。その結果、コンピュータモニタのようなグラフィック表示装置上でレンダリングすることができる画像ボリュームの2D画像が形成される。
【0083】
一般的に、人間の目の方が、オブジェクト、例えば2D画像の高周波成分に敏感である。しかし、バイリニア補間(図9)は、本質的にローパスフィルタであるために画像の高周波成分を不鮮明にする傾向がある。従って、高周波成分を捕捉して総計算経費を抑えるために、コンピュータプログラムは、いくつかの部分でより高価な適応MIPレイキャスティングを通じてより多くのピクセル値を発生させ、同時に画像平面の他の部分でバイリニア補間を通じてピクセル値の大部分を推定することができる。
【0084】
上述のように、画像解像度及び画像レンダリング速度を制御するために所定の画像化誤差閾値を調節することができる。例えば、サブ平面が複雑な内部構造又はオブジェクトの縁部のような高周波成分に対応していない場合、所定の画像化誤差閾値は高い値に上げられ、この逆も可能である。しかし、この目的を達成するために、コンピュータプログラムは、処理されるサブ平面が高周波成分を含むか否かを予測すべきである。
【0085】
一部の実施形態によれば、2つの方法を用いて所定の画像化誤差閾値を調節し、画質と画像レンダリング速度を両立させることができる。図8の段階817に示すように、その方法は以下の通りである。
・バイリニア補間誤差分析、及び
・オクトリ横縁部検出
【0086】
図10Aに示すように、サブ平面1000は、適応MIPレイキャスティングが発生させる4つのコーナにある4つの既知のピクセル値P1からP4を有する。従って、サブ平面1000の中心にあるバイリニア補間したピクセル値P5'は、以下の通りである。
P5'=(1/4)(P1+P2+P3+P4)
【0087】
一方、コンピュータプログラムはまた、サブ平面1000が4つのより小さなサブ平面に細分化された時に、サブ平面1000の中心での適応MIPレイキャスティングを通じてピクセル値P5を発生させる。2つのピクセル値間の絶対差|P5−P5'|は、バイリニア補間の結果がこのサブ平面1000内でいかに正確であるかを示している。例えば、より高い絶対差は、サブ平面が更に細分化する必要があることを意味するばかりでなく、サブ平面内には高周波成分がある可能性があることを示唆している。従って、コンピュータプログラムは、画像化誤差閾値を実質的に下げ、サブ平面内の内部構造の3D特性を完全に捕捉することができる。他方、より小さな絶対差は、サブ平面内の画像が滑らかであり、かつ所定の画像化誤差閾値を相応に大きくして大幅に画像解像度を落とすことなく計算経費を低減することができることを示唆している。
【0088】
オクトリ横縁部検出は、最大データ値を含む識別されたサブボリューム又はセル又はサブセルと、より小さな3Dオブジェクト又は画像ボリュームに埋め込まれた3Dオブジェクトの鋭い縁部を捕捉するための画像平面との間のサイズ差を検査することによって画像化誤差閾値を調節する方法である。
【0089】
簡素化を期すために、図10Bは、少なくとも2つのオブジェクト1140及び1160を含む2Dデータセット1100を示し、2Dデータセットは、N×Nピクセルを含む。データセットの内側には、Lピクセルを含む画像線1120がある。レイ経路1130に沿って、図6に示すような判断基準の少なくとも1つを満足した異なるサイズの一連のサブ平面がある(それぞれ、段階605、609、及び615)。拡大図1180は、コンピュータプログラムがレイ経路1130に沿った最大データ値1190を識別するサブ平面を取り囲む2Dデータセットの詳細を示している。最大データ値を含むサブ平面のフラグメント化レベルがQであると仮定して、小さいオブジェクト又はレイ経路近くのオブジェクトの鋭い縁部の存在を示す因子Zは、以下のように定められる。
【0090】
【数3】
【0091】
Qの値が高くなると(すなわち、より小さなサブ平面)、結果的にZ因子が高くなり、レイ経路1130に沿って一部の小さなオブジェクトがある可能性があることを示唆しており、レイ経路に沿った小さなオブジェクト又は鋭い縁部を見失わないように、相応に所定の画像化誤差閾値を下げるべきである。他方、Qの値が低くなると(すなわち、より大きなサブ平面)、Z因子が低くなり、レイ経路に沿った小さなオブジェクトを識別する可能性が小さいことを示しており、画像線1120上の有意な詳細を失うことなく、所定の画像化誤差閾値を大きくすることができる。尚、Z因子は、レイがデータセットの内側で早期に終了されることなくデータセットを出る時に、所定の画像化誤差閾値を調節する際に有用である。
【0092】
最後に、望ましいフレーム/秒と実際のフレーム/秒との比率に従って所定の画像化誤差閾値を調節することもできる。前者が後者よりも大きい場合は、画像化誤差閾値は、所定の画像解像度の僅かな損失でシステムのデフォルト能力よりも多くの画像フレームをレンダリングすることができるように増大させることができ、そうでなければ、所定の画像化誤差閾値は、前者が後者よりも小さい場合は減少させることができる。
【0093】
コンピュータシステム
上述の適応MIPレイキャスティング方法は、通常のコンピュータシステム内で実施することができ、特別なハードウエアサポートは不要である。図11は、本発明の一部の実施形態によるこのようなシステム1100を示している。適応MIPレイキャスティングシステム1100は、一般的に1つ又はそれよりも多くの中央演算処理装置(CPU)1120と、メモリ1114と、システム1100の様々な構成要素を相互に接続する1つ又はそれよりも多くの通信バス1112とを含む。適応MIPレイキャスティングシステム1100はまた、例えば、3Dデータセットの2D画像を表示する表示装置1106とユーザの画像レンダリング要求を受け取るキーボード1108とを含むユーザインタフェース1104を含む。システム1100は、任意的に、遠隔操作記憶装置からの3Dデータベースを検索するか又はレンダリング結果を遠隔地のクライアントに送出するネットワーク又は他の通信インタフェースを含むことができる。
【0094】
メモリ1114は、高速ランダムアクセスメモリを含み、また、1つ又はそれよりも多くの磁気ディスク記憶装置(図示せず)のような不揮発性メモリを含むこともできる。また、メモリ1114は、中央演算処理装置1102から遠隔に位置する大容量記憶装置を含むことができる。メモリ1114は、以下を格納することが好ましい。
・様々な基本的システムサービスを処理し、かつハードウエア依存のタスクを実行するための手順を含むオペレーティングシステム1116、
・「インターネット」、他の広域ネットワーク、ローカルエリアネットワーク、及びメトロポリタンエリアネットワークなどのような1つ又はそれよりも多くの通信ネットワーク(有線又は無線)を通じて、システム1100を様々なセキュリティ装置又はクライアントコンピュータ(図示せず)及び場合によっては他のサーバ又はコンピュータに接続するのに使用されるネットワーク通信モジュール1118、
・システム1100の作動に必要とされるメモリ1114に記憶された他のモジュール及びデータ構造を初期化するシステム初期化モジュール1120、
・3Dデータセットの2D画像を発生させて表示装置1106上でレンダリングする適応MIPレイキャスティングエンジン、
・3Dデータセット、及びフラグメント化した3Dデータセットを表す対応するオクトリデータ構造、
・2D画像データセット、及びフラグメント化された2D画像を表す複数の対応する四分木データ構造、及び
・3Dデータセットのデータ値を2D画像データセットのピクセル値に変換する画面転送関数表。
【0095】
MIPレイキャスティングエンジン1122は、実行可能な手順、副手順、及び以下のような画像発生手順をサポートする他のデータ構造を含む。
・3Dデータセットを複数のサブボリュームにフラグメント化し、各サブボリュームに対して一組のデータ値パラメータを推定してオクトリデータ構造を構成し、サブボリュームをオクトリデータ構造上の様々なノードに関連付ける3Dデータセットフラグメント化モジュール1124、
・一組の所定の判断基準に基づいてレイと相互作用する一連のサブボリュームを選択し、次にレイ経路に沿った最大データ値を識別する3D適応MIPレイキャスティングモジュール1126、及び
・各々が四分木データ構造に付随する複数のミニ平面に2D画像平面を細分化し、選択的に3D適応レイキャスティングモジュール1126を呼び出して3Dデータセットの2D画像を構成する2D画像レンダリングモジュール1128。
【0096】
図8に示すように、2D画像構成中に、システム1100は、最初に画像平面を複数のミニ平面に細分化し、次に各ミニ平面を再帰的に処理し、バイリニア補間又は必要であれば適応MIPレイキャスティングを通じて画像平面内の全てのピクセルをピクセル値に関連付ける。最後に、単一の2D画像がメモリ1114内に形成される。1つのミニ平面の画像化結果は、別のミニ平面から独立していることから、適応MIPレイキャスティングアルゴリズムは、実際にはパラレルコンピュータ又はコンピュータのクラスター上で実施することができるパラレルアルゴリズムである。
【0097】
図12は、コンピュータクラスター1200を使用する本発明の一実施形態を示している。クラスター1100は、以下を含む。
・1つ又はそれよりも多くの画像ボリュームを格納するデータ記憶装置1210、例えばハードディスク、
・好ましくは1つ又はそれよりも多くのCPUと、MIPレイキャスティングソフトウエアを格納する独自のメモリとを各々が有する複数のコンピュータサーバ1230、
・コンピュータクラスターによって発生した画像を表示するコンピュータモニタ1250、
・指令及びレンダリングパラメータをユーザから受け取るためのキーボード1270及びマウス1290、及び
・様々な構成要素を接続する通信バス1220。
【0098】
説明上、コンピュータクラスター1200内には4つのサーバがあり、各サーバは、部分画像1240で示すような最終画像の1/4の発生を担っている。各サーバ内では、タスクは、サーバ毎に複数のCPUがある場合には異なるCPU間で更に仕切ることができる。全ての部分画像1240が発生した後に、サーバの1つは、部分画像1240を合併して完全な画像にし、モニタ1250上でレンダリングする。
【実施例】
【0099】
図13A及び図13Bは、本発明の一実施形態による適応MIPレイキャスティングを用いて3DのCTスキャンデータセットから発生させた2つの画像の実施例を与えている。2つの画像は、図13Aのピクセル値が所定の画面転送関数に従ってレイ経路に沿って識別したそれぞれの最大データ値に依存するだけであり、一方、図13Bのピクセル値が画像平面と画像ボリューム内の最大データ値の位置との間の距離によって更に重み付け処理されることを除き、実質的には同じものである。その結果、画像ボリュームの異なる部分で識別した同じ最大データ値は、図13Bの画像上で異なるピクセル値を引き起こす可能性があり、見る者に対してある一定の3D透視を提供する。例えば、図13Aの大腿骨の2つの画像部分1320及び1340は、事実上同じ輝度を有し、一方、図13Bの同じ2つの部分1360及び1380は、異なる輝度を有する。特に、部分1360は、部分1380よりも見る者から離れた位置にあることから、部分1380と比較すると若干暗く見える。
【0100】
以上の説明は、説明を目的として特定的な実施形態を参照して行ったものである。しかし、上述の例示的な説明は、網羅的であること又は開示した正確な形態に本発明を限定することを意図していない。多くの修正及び変形が以上の教示の見地から可能である。実施形態は、本発明の原理及びその実際的な用途を最も良く説明し、それによって当業者が予想される特定の使用に適するような様々な修正を用いて本発明及び様々な実施形態を最も良く利用することができるように選んで説明したものである。
【図面の簡単な説明】
【0101】
【図1A】本発明の実施形態の平行投影の概略図である。
【図1B】本発明の実施形態の透視投影の概略図である。
【図1C】異なる画像解像度での3Dオブジェクトの3つの2D画像を示す図である。
【図1D】3Dデータセットによって採取された3Dオブジェクトを示す図である。
【図2】本発明の一実施形態によるMIPレイキャスティングアルゴリズムを示す流れ図である。
【図3A】3Dデータセットフラグメント化の一実施形態を示す図である。
【図3B】8つのセル又はボクセルを含むサブボリュームとボクセル又はセル内のスカラーデータ値分布とを示す図である。
【図4】3Dデータセットフラグメント化のコンピュータ実装を示す流れ図である。
【図5】レイと3Dデータセットのサブボリュームの間の一連の相互作用を概略的に示す図である。
【図6】本発明の実施形態によりレイ経路に沿って最大データ値を識別するためのコンピュータプログラムを示す流れ図である。
【図7】本発明の一実施形態による適応MIPレイキャスティングを示す1D実施例を表す図である。
【図8】コンピュータプログラムが本発明の一部の実施形態に従って2D画像を適応して発生させる方法を示す流れ図である。
【図9】ピクセル値のバイリニア補間の例を示す図である。
【図10A】所定の画像化誤差閾値を調節する2つの方法の一方を示す図である。
【図10B】所定の画像化誤差閾値を調節する2つの方法の他方を示す図である。
【図11】本発明の一実施形態による適応MIPレイキャスティングシステムのブロック図である。
【図12】本発明の一実施形態によりコンピュータクラスターに実装された適応MIPレイキャスティングレンダリングシステムのブロック図である。
【図13】本発明の一実施形態による適応MIPレイキャスティングアルゴリズムの異なるバージョンを通じた人体の2つの画像を示す図である。
【符号の説明】
【0102】
101 2D画像平面
102 放射面
104 レイ
106 画像ボリューム
【特許請求の範囲】
【請求項1】
適応最大強度投影レイキャスティングの方法であって、
採取したスカラー場の3Dデータセットを異なるサイズの複数のサブボリュームにフラグメント化し、一組のデータ値パラメータに付随する各サブボリュームが、該サブボリューム内の該スカラー場のデータ値分布を特徴付ける段階と、
前記スカラー場のデータ値に依存する画面転送関数を定義する段階と、
各々が初期データ値記録と断面とを有する複数のレイを前記採取データセットに向けて選択的に投射する段階と、
を含み、
各レイに対しては、
前記レイの経路に沿って位置する前記複数のサブボリュームの部分集合を選択する段階と、
前記選択された部分集合内にある前記レイ経路上の最大データ値を識別する段階と、
前記画面転送関数に従って前記最大データ値を2D画像平面内のピクセル値に変換する段階と、
を含み、
前記投射レイに対して判断された前記ピクセル値を用いて、前記2D画像平面内の他の位置の他のピクセル値を推定する段階、
を更に含むことを特徴とする方法。
【請求項2】
前記採取3Dデータセットをフラグメント化する段階は、
前記採取データセットを8つのサブボリュームにフラグメント化する段階と、
各サブボリュームに対して、それを最小のサブボリュームのサイズが所定のサイズ限界に到達するまで8つのより小さなサブボリュームに再帰的にフラグメント化する段階と、
を含むことを特徴とする請求項1に記載の方法。
【請求項3】
前記所定のサイズ限界は、2×2×2の3Dセルを含むサブボリュームであり、前記スカラー場のデータ値は、各セルの各コーナに付随していることを特徴とする請求項2に記載の方法。
【請求項4】
各セルは、8つのコーナを有し、該セル内にある位置の前記データ値は、該セルの該8つのコーナでの前記データ値を用いてトリリニア補間されることを特徴とする請求項3に記載の方法。
【請求項5】
サブボリュームに付随する前記データ値パラメータの組は、該サブボリューム内の前記スカラー場の最大、平均、及び最小データ値を含むことを特徴とする請求項1に記載の方法。
【請求項6】
ルートノードと複数の中間ノードと複数の葉ノードとを有するオクトリデータ構造を構成する段階と、
前記ルートノードを前記採取3Dデータセットに関連付ける段階と、
前記複数の葉ノードの各々を前記最小サブボリュームの1つに関連付ける段階と、
前記複数の中間ノードの各々を前記最小サブボリュームよりも大きい前記サブボリュームの1つに関連付ける段階と、
を更に含むことを特徴とする請求項1に記載の方法。
【請求項7】
前記複数のレイを採取データセットに向けて選択的に投射する段階は、
前記2D画像平面を複数のミニ平面に細分化する段階、
を含み、
前記複数のミニ平面の各々に対しては、
前記ミニ平面の前記4つのコーナでの4つのピクセル値を推定する段階と、
前記ミニ平面を複数のサブ平面に再帰的に細分化する段階と、
を含み、
各サブ平面の最大ピクセル値差が所定の画像化誤差閾値よりも小さくなるまでレイを前記採取データセットに向けて投射することにより、前記サブ平面の中心のピクセル値を推定する段階、
を更に含む、
ことを特徴とする請求項1に記載の方法。
【請求項8】
サブ平面の前記最大ピクセル値差は、該サブ平面の前記4つのコーナでのピクセル値の該サブ平面の平均ピクセル値からの最大偏差として定義されることを特徴とする請求項7に記載の方法。
【請求項9】
前記所定の画像化誤差閾値は、ユーザによって提供された画像レンダリング速度、前記3Dデータセットに埋め込まれたオブジェクトの縁部までの距離、及び適応MIPレイキャスティングから推定されたピクセル値とバイリニア補間から推定されたピクセル値との間の差によって調節されることを特徴とする請求項7に記載の方法。
【請求項10】
前記レイ経路に沿って位置する複数のサブボリュームの部分集合を選択する段階は、
前記レイ経路に沿って前記レイに初めて遭遇する最大のサブボリュームと、それに付随するデータ値パラメータの組とを識別する段階と、
前記レイの現在のデータ値記録と前記サブボリュームの付随するデータ値パラメータの組とを用いて、該サブボリュームの最大画面値差を推定する段階と、
前記サブボリュームに包含されたより小さなサブボリュームを、該より小さなサブボリュームの前記推定最大画面値差が所定の閾値よりも小さくなるまで再帰的に選択する段階と、
を含むことを特徴とする請求項1に記載の方法。
【請求項11】
前記所定の閾値は、ユーザによって指定された画像レンダリング速度と、平行投影の場合ではズーム因子と、又は透視投影の場合では透視角及び前記画像平面と前記採取データセットの間の透視距離とによって調整されることを特徴とする請求項10に記載の方法。
【請求項12】
前記複数のサブボリュームの部分集合の1つ内にあるレイ経路上の最大データ値を識別する段階は、
サブボリュームの所定の位置でのデータ値を推定する段階と、
前記推定データ値が前記現在のデータ値記録よりも高い場合に、前記レイの現在のデータ値記録を更新する段階と、
前記レイが前記採取データセットを出るまで、前記部分集合の全ての残っているサブボリュームに対して前記推定及び更新する段階を繰り返す段階と、
を含むことを特徴とする請求項1に記載の方法。
【請求項13】
前記サブボリュームは、2×2×2セル又は少なくとも前記レイの前記断面を超える寸法を有するセル又はサブセルを含む最小サブボリュームであることを特徴とする請求項12に記載の方法。
【請求項14】
前記投射レイに対して判断されたピクセル値を用いて他の位置の他のピクセル値を推定する段階は、
前記他の位置の各々に対して、
前記位置を取り囲みかつ4つの投射レイに関連する4つピクセル値を選択する段階と、
前記4つのピクセル値を用いて前記位置でのピクセル値をバイリニア補間する段階と、
を含むことを特徴とする請求項1に記載の方法。
【請求項15】
適応最大強度投影(MIP)レイキャスティングシステムであって、
プログラムを実行する1つ又はそれよりも多くの中央演算処理装置と、
複数のMIPレイキャスティングパラメータを受け取るためのユーザインタフェースと、
前記1つ又はそれよりも多くの中央演算処理装置によって実行可能な適応MIPレイキャスティングエンジンモジュールと、
を含み、
前記モジュールは、
スカラー場の採取3Dデータセットを異なるサイズの複数のサブボリュームにフラグメント化し、一組のデータ値パラメータに付随する各サブボリュームが、該サブボリューム内の該スカラー場のデータ値分布を特徴付けるような命令と、
前記スカラー場のデータ値に依存する画面転送関数を定義するための命令と、
各々が初期現在データ値記録と断面とを有する複数のレイを前記採取データセットに向けて選択的に投射するための命令と、
レイ経路上に位置する前記複数のサブボリュームの部分集合を選択するための命令と、
前記選択された部分集合内にある前記レイ経路上の最大データ値を識別するための命令と、
前記画面転送関数に従って前記最大データ値を2D画像平面内のピクセル値に変換するための命令と、
前記投射レイに対して判断された前記ピクセル値を用いて、前記2D画像平面内の他の位置の他のピクセル値を推定するための命令と、
を含む、
ことを特徴とするシステム。
【請求項16】
前記採取3Dデータセットをフラグメント化するための命令は、
前記3Dデータセットを8つのサブボリュームにフラグメント化する段階と、
各サブボリュームに対して、それを最小サブボリュームのサイズが所定のサイズ限界に到達するまで8つのより小さなサブボリュームに再帰的にフラグメント化する段階と、
を含むことを特徴とする請求項15に記載のシステム。
【請求項17】
前記所定のサイズ限界は、2×2×2の3Dセルを含むサブボリュームであり、前記スカラー場のデータ値は、各セルの各コーナに付随していることを特徴とする請求項16に記載のシステム。
【請求項18】
各セルは、8つのコーナを有し、該セル内のどの位置の前記データ値も、該セルの該8つのコーナでの前記データ値を用いてトリリニア補間されることを特徴とする請求項17に記載のシステム。
【請求項19】
前記データ値パラメータの組は、前記サブボリューム内の前記スカラー場の最大、平均、及び最小データ値を含むことを特徴とする請求項15に記載のシステム。
【請求項20】
ルートノードと複数の中間ノードと複数の葉ノードとを含むオクトリデータ構造を構成するための命令と、
前記ルートノードを前記3Dデータセットと関連付けるための命令と、
前記複数の葉ノードの各々を前記複数のサブボリュームからの最小サブボリュームと関連付けるための命令と、
前記複数の中間ノードの各々を前記最小サブボリュームよりも大きな前記複数のサブボリュームからのサブボリュームと関連付けるための命令と、
を更に含むことを特徴とする請求項15に記載のシステム。
【請求項21】
前記採取データセットに向けて複数のレイを選択的に投射するための命令は、
前記2D画像平面を複数のミニ平面に細分化する、
ための命令を含み、
前記複数のミニ平面の各々に対しては、
前記ミニ平面の前記4つのコーナでの4つのピクセル値を推定し、
前記ミニ平面を複数のサブ平面に再帰的に細分化する、
ための命令を含み、
各サブ平面の最大ピクセル値差が所定の画像化誤差閾値よりも小さくなるまでレイを前記採取データセットに向けて投射することにより、該サブ平面の中心でのピクセル値を推定する、
ための命令を更に含むことを特徴とする請求項15に記載のシステム。
【請求項22】
サブ平面内の前記最大ピクセル値差は、該サブ平面の前記4つのコーナでのピクセル値の該サブ平面の平均ピクセル値からの最大偏差として定義されることを特徴とする請求項21に記載のシステム。
【請求項23】
前記所定の画像化誤差閾値は、ユーザによって提供された画像レンダリング速度、前記3Dデータセットに埋め込まれたオブジェクトの縁部までの距離、適応MIPレイキャスティングから推定されたピクセル値とバイリニア補間から推定されたピクセル値との間の差によって調整されることを特徴とする請求項21に記載のシステム。
【請求項24】
前記レイ経路に沿って位置する複数のサブボリュームの部分集合を選択するための命令は、
前記レイ経路に沿って前記レイに初めて遭遇する最大のサブボリュームとそれに付随するデータ値パラメータの組とを識別し、
前記レイの現在のデータ値記録と前記サブボリュームの付随するデータ値パラメータの組とを用いて該サブボリュームの最大画面値差を推定し、
前記サブボリュームに包含されたより小さなサブボリュームを、該より小さなサブボリュームの前記推定最大画面値差が所定の閾値よりも小さくなるまで再帰的に選択する、
ための命令を含むことを特徴とする請求項15に記載のシステム。
【請求項25】
前記複数のサブボリュームの部分集合の1つ内にあるレイ経路上の最大データ値を識別するための命令は、
サブボリュームの所定の位置でのデータ値を推定し、
前記推定データ値が前記現在のデータ値記録よりも高い場合に、前記レイの現在のデータ値記録を更新し、
前記レイが前記採取データセットを出るまで、前記部分集合の全ての残っているサブボリュームに対して前記推定及び更新する段階を繰り返す、
ための命令を含むことを特徴とする請求項15に記載のシステム。
【請求項26】
前記サブボリュームは、2×2×2セル又は少なくとも前記レイの前記断面を超える寸法を有するセル又はサブセルを含む最小サブボリュームであることを特徴とする請求項25に記載のシステム。
【請求項27】
前記投射レイに対して判断されたピクセル値を用いて2D画像平面内の他の位置の他のピクセル値を推定するための命令は、
各位置を取り囲みかつ4つの投射レイに関連する4つピクセル値を選択し、
前記4つのピクセル値を用いて前記位置でのピクセル値をバイリニア補間する、
ための命令を含むことを特徴とする請求項15に記載のシステム。
【請求項28】
コンピュータ可読記憶媒体とそこに組み込まれたコンピュータプログラム機構とを含む、コンピュータシステムと共に使用するためのコンピュータプログラム製品であって、
前記コンピュータプログラム機構は、
スカラー場の採取3Dデータセットを異なるサイズの複数のサブボリュームにフラグメント化し、一組のデータ値パラメータに付随する各サブボリュームが、該サブボリューム内の該スカラー場のデータ値分布を特徴付けるような命令と、
前記スカラー場のデータ値に依存する画面転送関数を定義するための命令と、
各々が初期現在データ値記録と断面とを有する複数のレイを前記採取データセットに向けて選択的に投射するための命令と、
レイ経路上に位置する前記複数のサブボリュームの部分集合を選択するための命令と、
前記複数のサブボリュームの前記部分集合の1つ内にある前記レイ経路上の最大データ値を識別するための命令と、
前記画面転送関数に従って前記最大データ値を2D画像平面内のピクセル値に変換するための命令と、
前記投射レイに対して判断された前記ピクセル値を用いて、前記2D画像平面内の他の位置の他のピクセル値を推定するための命令と、
を含む、
ことを特徴とする製品。
【請求項29】
前記採取3Dデータセットをフラグメント化するための命令は、
前記3Dデータセットを8つのサブボリュームにフラグメント化する段階と、
各サブボリュームに対して、それを最小サブボリュームのサイズが所定のサイズ限界に到達するまで8つのより小さなサブボリュームに再帰的にフラグメント化する段階と、
を含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項30】
前記所定のサイズ限界は、2×2×2の3Dセルを含むサブボリュームであり、前記スカラー場のデータ値は、各セルの各コーナに付随していることを特徴とする請求項29に記載のコンピュータプログラム製品。
【請求項31】
各セルは、8つのコーナを有し、該セル内のどの位置の前記データ値も、該セルの該8つのコーナでの前記データ値を用いてトリリニア補間されることを特徴とする請求項30に記載のコンピュータプログラム製品。
【請求項32】
前記データ値パラメータの組は、前記サブボリューム内の前記スカラー場の最大、平均、及び最小データ値を含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項33】
ルートノードと複数の中間ノードと複数の葉ノードとを含むオクトリデータ構造を構成するための命令と、
前記ルートノードを前記3Dデータセットと関連付けるための命令と、
前記複数の葉ノードの各々を前記複数のサブボリュームからの最小サブボリュームと関連付けるための命令と、
前記複数の中間ノードの各々を前記最小サブボリュームよりも大きな前記複数のサブボリュームからのサブボリュームと関連付けるための命令と、
を更に含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項34】
前記採取データセットに向けて複数のレイを選択的に投射するための命令は、
前記2D画像平面を複数のミニ平面に細分化する、
ための命令を含み、
前記複数のミニ平面の各々に対しては、
前記ミニ平面の前記4つのコーナでの4つのピクセル値を推定し、
前記ミニ平面を複数のサブ平面に再帰的に細分化する、
ための命令を含み、
各サブ平面の最大ピクセル値差が所定の画像化誤差閾値よりも小さくなるまでレイを前記採取データセットに向けて投射することにより、該サブ平面の中心でのピクセル値を推定する、
ための命令を更に含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項35】
サブ平面内の前記最大ピクセル値差は、該サブ平面の前記4つのコーナでのピクセル値の該サブ平面の平均ピクセル値からの最大偏差として定義されることを特徴とする請求項34に記載のコンピュータプログラム製品。
【請求項36】
前記所定の画像化誤差閾値は、ユーザによって提供された画像レンダリング速度、前記3Dデータセットに埋め込まれたオブジェクトの縁部までの距離、適応MIPレイキャスティングから推定されたピクセル値とバイリニア補間から推定されたピクセル値との間の差によって調整されることを特徴とする請求項34に記載のコンピュータプログラム製品。
【請求項37】
前記レイ経路に沿って位置する複数のサブボリュームの部分集合を選択するための命令は、
前記レイ経路に沿って前記レイに初めて遭遇する最大のサブボリュームとそれに付随するデータ値パラメータの組とを識別し、
前記レイの現在のデータ値記録と前記サブボリュームの付随するデータ値パラメータの組とを用いて該サブボリュームの最大画面値差を推定し、
前記サブボリュームに包含されたより小さなサブボリュームを、該より小さなサブボリュームの前記推定最大画面値差が所定の閾値よりも小さくなるまで再帰的に選択する、
ための命令を含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項38】
前記複数のサブボリュームの部分集合の1つ内にあるレイ経路上の最大データ値を識別するための命令は、
サブボリュームの所定の位置でのデータ値を推定し、
前記推定データ値が前記現在のデータ値記録よりも高い場合に、前記レイの現在のデータ値記録を更新し、
前記レイが前記採取データセットを出るまで、前記部分集合の全ての残っているサブボリュームに対して前記推定及び更新する段階を繰り返す、
ための命令を含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項39】
前記サブボリュームは、2×2×2セル又は少なくとも前記レイの前記断面を超える寸法を有するセル又はサブセルを含む最小サブボリュームであることを特徴とする請求項38に記載のコンピュータプログラム製品。
【請求項40】
前記2D画像平面上の他の位置のピクセル値を推定するための命令は、
各位置を取り囲みかつ4つの投射レイに関連する4つピクセル値を選択し、
前記4つのピクセル値を用いて前記位置でのピクセル値をバイリニア補間する、
ための命令を含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項41】
採取された3Dデータセットによって表された3Dオブジェクトの2D画像を発生させる方法であって、
採取された3Dデータセットを異なるサイズの複数のサブボリュームにフラグメント化し、一組のデータ値パラメータに付随する各サブボリュームが、該サブボリューム内のデータ値分布を特徴付ける段階と、
2D放射面から前記複数のサブボリュームに向けて、各々が初期データ値記録及び断面を有して該2D放射面に対して所定の方向に放出される複数のレイを選択的に投射する段階と、
前記2D放射面上の複数の位置で、各々が前記複数のレイ経路の1つに沿った最大データ値を特徴付ける複数のピクセル値を選択的に発生させる段階と、
前記2D放射面上の前記複数の位置での前記複数のピクセル値の部分集合を用いて、該2D放射面上の他の位置のピクセル値を推定する段階と、
を含むことを特徴とする方法。
【請求項42】
初期データ値のレイがそのレイ経路に沿って3Dデータセットと相互作用する時の最大データ値を識別する方法であって、
各サブボリュームがサブボリューム内の最大、平均、及び最小データ値を含む一組のデータ値パラメータに関連する異なるサイズの複数のサブボリュームに3Dデータセットをフラグメント化する段階と、
前記3Dデータセットのデータ値に依存する単調画面転送関数を定義する段階と、
前記レイ経路に沿って、どの選択したサブボリュームの最大データ値も該レイの現在のデータ値記録よりも高く、かつ該選択したサブボリュームの最大画面転送差が所定の閾値よりも低いような一組のサブボリュームを選択する段階と、
前記選択された組の各サブボリュームに対して、該サブボリューム内の所定の位置でのデータ値を推定し、該推定データ値が前記レイの現在のデータ値記録よりも高い場合には、該推定データ値で該レイの現在のデータ値記録を更新する段階と、
を含むことを特徴とする方法。
【請求項43】
前記所定の位置は、選択されたサブボリューム内の前記レイ経路の中心であることを特徴とする請求項42に記載の方法。
【請求項44】
多次元データセットの部分集合内のデータ値を識別する方法であって、
各々が関連するデータ値パラメータの組を有する異なるサイズの複数のサブデータセットにデータセットをフラグメント化する段階と、
各ノードが前記サブデータセットの1つに関連する複数のノードを有する階層データ構造を構成する段階と、
前記部分集合の一意的な部分を網羅するサブデータセットを識別する段階と、
前記部分集合の前記一意的な部分が前記データ値を含むかを検査する段階と、
前記部分集合を完全に網羅する一連のサブデータセットが識別されるまで前記識別する段階及び検査する段階を繰り返す段階と、
を含むことを特徴とする方法。
【請求項45】
初期データ値が、前記部分集合に割り当てられ、該初期データ値は、前記一意的な部分内の現在のデータ値が所定の条件を満足する場合には該現在のデータ値と入れ替えられることを特徴とする請求項44に記載の方法。
【請求項46】
前記所定の条件は、前記現在のデータ値が前記初期データ値よりも高く、かつ前記得られたデータ値が前記部分集合の最大データ値であることを含むことを特徴とする請求項45に記載の方法。
【請求項47】
前記所定の条件は、前記現在のデータ値が前記初期データ値よりも低く、かつ前記得られたデータ値が前記部分集合の最小データ値であることを含むことを特徴とする請求項45に記載の方法。
【請求項48】
前記部分集合は、前記多次元データセット内の所定の多次元領域内に位置するデータ値を含むことを特徴とする請求項44に記載の方法。
【請求項49】
前記所定の多次元領域は、前記多次元データセット内の線上又は線の近くに位置するデータ値を含むことを特徴とする請求項48に記載の方法。
【請求項50】
前記所定の多次元領域は、前記多次元データセット内の曲線上又は曲線の近くに位置するデータ値を含むことを特徴とする請求項48に記載の方法。
【請求項51】
前記所定の多次元領域は、前記多次元データセット内の平面上又は平面の近くに位置するデータ値を含むことを特徴とする請求項48に記載の方法。
【請求項52】
前記所定の多次元領域は、前記多次元データセット内の曲面上又は曲面の近くに位置するデータ値を含むことを特徴とする請求項48に記載の方法。
【請求項53】
前記一連のサブデータセット内の最大サイズのサブデータセットが、最初に識別されて検査されることを特徴とする請求項44に記載の方法。
【請求項1】
適応最大強度投影レイキャスティングの方法であって、
採取したスカラー場の3Dデータセットを異なるサイズの複数のサブボリュームにフラグメント化し、一組のデータ値パラメータに付随する各サブボリュームが、該サブボリューム内の該スカラー場のデータ値分布を特徴付ける段階と、
前記スカラー場のデータ値に依存する画面転送関数を定義する段階と、
各々が初期データ値記録と断面とを有する複数のレイを前記採取データセットに向けて選択的に投射する段階と、
を含み、
各レイに対しては、
前記レイの経路に沿って位置する前記複数のサブボリュームの部分集合を選択する段階と、
前記選択された部分集合内にある前記レイ経路上の最大データ値を識別する段階と、
前記画面転送関数に従って前記最大データ値を2D画像平面内のピクセル値に変換する段階と、
を含み、
前記投射レイに対して判断された前記ピクセル値を用いて、前記2D画像平面内の他の位置の他のピクセル値を推定する段階、
を更に含むことを特徴とする方法。
【請求項2】
前記採取3Dデータセットをフラグメント化する段階は、
前記採取データセットを8つのサブボリュームにフラグメント化する段階と、
各サブボリュームに対して、それを最小のサブボリュームのサイズが所定のサイズ限界に到達するまで8つのより小さなサブボリュームに再帰的にフラグメント化する段階と、
を含むことを特徴とする請求項1に記載の方法。
【請求項3】
前記所定のサイズ限界は、2×2×2の3Dセルを含むサブボリュームであり、前記スカラー場のデータ値は、各セルの各コーナに付随していることを特徴とする請求項2に記載の方法。
【請求項4】
各セルは、8つのコーナを有し、該セル内にある位置の前記データ値は、該セルの該8つのコーナでの前記データ値を用いてトリリニア補間されることを特徴とする請求項3に記載の方法。
【請求項5】
サブボリュームに付随する前記データ値パラメータの組は、該サブボリューム内の前記スカラー場の最大、平均、及び最小データ値を含むことを特徴とする請求項1に記載の方法。
【請求項6】
ルートノードと複数の中間ノードと複数の葉ノードとを有するオクトリデータ構造を構成する段階と、
前記ルートノードを前記採取3Dデータセットに関連付ける段階と、
前記複数の葉ノードの各々を前記最小サブボリュームの1つに関連付ける段階と、
前記複数の中間ノードの各々を前記最小サブボリュームよりも大きい前記サブボリュームの1つに関連付ける段階と、
を更に含むことを特徴とする請求項1に記載の方法。
【請求項7】
前記複数のレイを採取データセットに向けて選択的に投射する段階は、
前記2D画像平面を複数のミニ平面に細分化する段階、
を含み、
前記複数のミニ平面の各々に対しては、
前記ミニ平面の前記4つのコーナでの4つのピクセル値を推定する段階と、
前記ミニ平面を複数のサブ平面に再帰的に細分化する段階と、
を含み、
各サブ平面の最大ピクセル値差が所定の画像化誤差閾値よりも小さくなるまでレイを前記採取データセットに向けて投射することにより、前記サブ平面の中心のピクセル値を推定する段階、
を更に含む、
ことを特徴とする請求項1に記載の方法。
【請求項8】
サブ平面の前記最大ピクセル値差は、該サブ平面の前記4つのコーナでのピクセル値の該サブ平面の平均ピクセル値からの最大偏差として定義されることを特徴とする請求項7に記載の方法。
【請求項9】
前記所定の画像化誤差閾値は、ユーザによって提供された画像レンダリング速度、前記3Dデータセットに埋め込まれたオブジェクトの縁部までの距離、及び適応MIPレイキャスティングから推定されたピクセル値とバイリニア補間から推定されたピクセル値との間の差によって調節されることを特徴とする請求項7に記載の方法。
【請求項10】
前記レイ経路に沿って位置する複数のサブボリュームの部分集合を選択する段階は、
前記レイ経路に沿って前記レイに初めて遭遇する最大のサブボリュームと、それに付随するデータ値パラメータの組とを識別する段階と、
前記レイの現在のデータ値記録と前記サブボリュームの付随するデータ値パラメータの組とを用いて、該サブボリュームの最大画面値差を推定する段階と、
前記サブボリュームに包含されたより小さなサブボリュームを、該より小さなサブボリュームの前記推定最大画面値差が所定の閾値よりも小さくなるまで再帰的に選択する段階と、
を含むことを特徴とする請求項1に記載の方法。
【請求項11】
前記所定の閾値は、ユーザによって指定された画像レンダリング速度と、平行投影の場合ではズーム因子と、又は透視投影の場合では透視角及び前記画像平面と前記採取データセットの間の透視距離とによって調整されることを特徴とする請求項10に記載の方法。
【請求項12】
前記複数のサブボリュームの部分集合の1つ内にあるレイ経路上の最大データ値を識別する段階は、
サブボリュームの所定の位置でのデータ値を推定する段階と、
前記推定データ値が前記現在のデータ値記録よりも高い場合に、前記レイの現在のデータ値記録を更新する段階と、
前記レイが前記採取データセットを出るまで、前記部分集合の全ての残っているサブボリュームに対して前記推定及び更新する段階を繰り返す段階と、
を含むことを特徴とする請求項1に記載の方法。
【請求項13】
前記サブボリュームは、2×2×2セル又は少なくとも前記レイの前記断面を超える寸法を有するセル又はサブセルを含む最小サブボリュームであることを特徴とする請求項12に記載の方法。
【請求項14】
前記投射レイに対して判断されたピクセル値を用いて他の位置の他のピクセル値を推定する段階は、
前記他の位置の各々に対して、
前記位置を取り囲みかつ4つの投射レイに関連する4つピクセル値を選択する段階と、
前記4つのピクセル値を用いて前記位置でのピクセル値をバイリニア補間する段階と、
を含むことを特徴とする請求項1に記載の方法。
【請求項15】
適応最大強度投影(MIP)レイキャスティングシステムであって、
プログラムを実行する1つ又はそれよりも多くの中央演算処理装置と、
複数のMIPレイキャスティングパラメータを受け取るためのユーザインタフェースと、
前記1つ又はそれよりも多くの中央演算処理装置によって実行可能な適応MIPレイキャスティングエンジンモジュールと、
を含み、
前記モジュールは、
スカラー場の採取3Dデータセットを異なるサイズの複数のサブボリュームにフラグメント化し、一組のデータ値パラメータに付随する各サブボリュームが、該サブボリューム内の該スカラー場のデータ値分布を特徴付けるような命令と、
前記スカラー場のデータ値に依存する画面転送関数を定義するための命令と、
各々が初期現在データ値記録と断面とを有する複数のレイを前記採取データセットに向けて選択的に投射するための命令と、
レイ経路上に位置する前記複数のサブボリュームの部分集合を選択するための命令と、
前記選択された部分集合内にある前記レイ経路上の最大データ値を識別するための命令と、
前記画面転送関数に従って前記最大データ値を2D画像平面内のピクセル値に変換するための命令と、
前記投射レイに対して判断された前記ピクセル値を用いて、前記2D画像平面内の他の位置の他のピクセル値を推定するための命令と、
を含む、
ことを特徴とするシステム。
【請求項16】
前記採取3Dデータセットをフラグメント化するための命令は、
前記3Dデータセットを8つのサブボリュームにフラグメント化する段階と、
各サブボリュームに対して、それを最小サブボリュームのサイズが所定のサイズ限界に到達するまで8つのより小さなサブボリュームに再帰的にフラグメント化する段階と、
を含むことを特徴とする請求項15に記載のシステム。
【請求項17】
前記所定のサイズ限界は、2×2×2の3Dセルを含むサブボリュームであり、前記スカラー場のデータ値は、各セルの各コーナに付随していることを特徴とする請求項16に記載のシステム。
【請求項18】
各セルは、8つのコーナを有し、該セル内のどの位置の前記データ値も、該セルの該8つのコーナでの前記データ値を用いてトリリニア補間されることを特徴とする請求項17に記載のシステム。
【請求項19】
前記データ値パラメータの組は、前記サブボリューム内の前記スカラー場の最大、平均、及び最小データ値を含むことを特徴とする請求項15に記載のシステム。
【請求項20】
ルートノードと複数の中間ノードと複数の葉ノードとを含むオクトリデータ構造を構成するための命令と、
前記ルートノードを前記3Dデータセットと関連付けるための命令と、
前記複数の葉ノードの各々を前記複数のサブボリュームからの最小サブボリュームと関連付けるための命令と、
前記複数の中間ノードの各々を前記最小サブボリュームよりも大きな前記複数のサブボリュームからのサブボリュームと関連付けるための命令と、
を更に含むことを特徴とする請求項15に記載のシステム。
【請求項21】
前記採取データセットに向けて複数のレイを選択的に投射するための命令は、
前記2D画像平面を複数のミニ平面に細分化する、
ための命令を含み、
前記複数のミニ平面の各々に対しては、
前記ミニ平面の前記4つのコーナでの4つのピクセル値を推定し、
前記ミニ平面を複数のサブ平面に再帰的に細分化する、
ための命令を含み、
各サブ平面の最大ピクセル値差が所定の画像化誤差閾値よりも小さくなるまでレイを前記採取データセットに向けて投射することにより、該サブ平面の中心でのピクセル値を推定する、
ための命令を更に含むことを特徴とする請求項15に記載のシステム。
【請求項22】
サブ平面内の前記最大ピクセル値差は、該サブ平面の前記4つのコーナでのピクセル値の該サブ平面の平均ピクセル値からの最大偏差として定義されることを特徴とする請求項21に記載のシステム。
【請求項23】
前記所定の画像化誤差閾値は、ユーザによって提供された画像レンダリング速度、前記3Dデータセットに埋め込まれたオブジェクトの縁部までの距離、適応MIPレイキャスティングから推定されたピクセル値とバイリニア補間から推定されたピクセル値との間の差によって調整されることを特徴とする請求項21に記載のシステム。
【請求項24】
前記レイ経路に沿って位置する複数のサブボリュームの部分集合を選択するための命令は、
前記レイ経路に沿って前記レイに初めて遭遇する最大のサブボリュームとそれに付随するデータ値パラメータの組とを識別し、
前記レイの現在のデータ値記録と前記サブボリュームの付随するデータ値パラメータの組とを用いて該サブボリュームの最大画面値差を推定し、
前記サブボリュームに包含されたより小さなサブボリュームを、該より小さなサブボリュームの前記推定最大画面値差が所定の閾値よりも小さくなるまで再帰的に選択する、
ための命令を含むことを特徴とする請求項15に記載のシステム。
【請求項25】
前記複数のサブボリュームの部分集合の1つ内にあるレイ経路上の最大データ値を識別するための命令は、
サブボリュームの所定の位置でのデータ値を推定し、
前記推定データ値が前記現在のデータ値記録よりも高い場合に、前記レイの現在のデータ値記録を更新し、
前記レイが前記採取データセットを出るまで、前記部分集合の全ての残っているサブボリュームに対して前記推定及び更新する段階を繰り返す、
ための命令を含むことを特徴とする請求項15に記載のシステム。
【請求項26】
前記サブボリュームは、2×2×2セル又は少なくとも前記レイの前記断面を超える寸法を有するセル又はサブセルを含む最小サブボリュームであることを特徴とする請求項25に記載のシステム。
【請求項27】
前記投射レイに対して判断されたピクセル値を用いて2D画像平面内の他の位置の他のピクセル値を推定するための命令は、
各位置を取り囲みかつ4つの投射レイに関連する4つピクセル値を選択し、
前記4つのピクセル値を用いて前記位置でのピクセル値をバイリニア補間する、
ための命令を含むことを特徴とする請求項15に記載のシステム。
【請求項28】
コンピュータ可読記憶媒体とそこに組み込まれたコンピュータプログラム機構とを含む、コンピュータシステムと共に使用するためのコンピュータプログラム製品であって、
前記コンピュータプログラム機構は、
スカラー場の採取3Dデータセットを異なるサイズの複数のサブボリュームにフラグメント化し、一組のデータ値パラメータに付随する各サブボリュームが、該サブボリューム内の該スカラー場のデータ値分布を特徴付けるような命令と、
前記スカラー場のデータ値に依存する画面転送関数を定義するための命令と、
各々が初期現在データ値記録と断面とを有する複数のレイを前記採取データセットに向けて選択的に投射するための命令と、
レイ経路上に位置する前記複数のサブボリュームの部分集合を選択するための命令と、
前記複数のサブボリュームの前記部分集合の1つ内にある前記レイ経路上の最大データ値を識別するための命令と、
前記画面転送関数に従って前記最大データ値を2D画像平面内のピクセル値に変換するための命令と、
前記投射レイに対して判断された前記ピクセル値を用いて、前記2D画像平面内の他の位置の他のピクセル値を推定するための命令と、
を含む、
ことを特徴とする製品。
【請求項29】
前記採取3Dデータセットをフラグメント化するための命令は、
前記3Dデータセットを8つのサブボリュームにフラグメント化する段階と、
各サブボリュームに対して、それを最小サブボリュームのサイズが所定のサイズ限界に到達するまで8つのより小さなサブボリュームに再帰的にフラグメント化する段階と、
を含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項30】
前記所定のサイズ限界は、2×2×2の3Dセルを含むサブボリュームであり、前記スカラー場のデータ値は、各セルの各コーナに付随していることを特徴とする請求項29に記載のコンピュータプログラム製品。
【請求項31】
各セルは、8つのコーナを有し、該セル内のどの位置の前記データ値も、該セルの該8つのコーナでの前記データ値を用いてトリリニア補間されることを特徴とする請求項30に記載のコンピュータプログラム製品。
【請求項32】
前記データ値パラメータの組は、前記サブボリューム内の前記スカラー場の最大、平均、及び最小データ値を含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項33】
ルートノードと複数の中間ノードと複数の葉ノードとを含むオクトリデータ構造を構成するための命令と、
前記ルートノードを前記3Dデータセットと関連付けるための命令と、
前記複数の葉ノードの各々を前記複数のサブボリュームからの最小サブボリュームと関連付けるための命令と、
前記複数の中間ノードの各々を前記最小サブボリュームよりも大きな前記複数のサブボリュームからのサブボリュームと関連付けるための命令と、
を更に含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項34】
前記採取データセットに向けて複数のレイを選択的に投射するための命令は、
前記2D画像平面を複数のミニ平面に細分化する、
ための命令を含み、
前記複数のミニ平面の各々に対しては、
前記ミニ平面の前記4つのコーナでの4つのピクセル値を推定し、
前記ミニ平面を複数のサブ平面に再帰的に細分化する、
ための命令を含み、
各サブ平面の最大ピクセル値差が所定の画像化誤差閾値よりも小さくなるまでレイを前記採取データセットに向けて投射することにより、該サブ平面の中心でのピクセル値を推定する、
ための命令を更に含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項35】
サブ平面内の前記最大ピクセル値差は、該サブ平面の前記4つのコーナでのピクセル値の該サブ平面の平均ピクセル値からの最大偏差として定義されることを特徴とする請求項34に記載のコンピュータプログラム製品。
【請求項36】
前記所定の画像化誤差閾値は、ユーザによって提供された画像レンダリング速度、前記3Dデータセットに埋め込まれたオブジェクトの縁部までの距離、適応MIPレイキャスティングから推定されたピクセル値とバイリニア補間から推定されたピクセル値との間の差によって調整されることを特徴とする請求項34に記載のコンピュータプログラム製品。
【請求項37】
前記レイ経路に沿って位置する複数のサブボリュームの部分集合を選択するための命令は、
前記レイ経路に沿って前記レイに初めて遭遇する最大のサブボリュームとそれに付随するデータ値パラメータの組とを識別し、
前記レイの現在のデータ値記録と前記サブボリュームの付随するデータ値パラメータの組とを用いて該サブボリュームの最大画面値差を推定し、
前記サブボリュームに包含されたより小さなサブボリュームを、該より小さなサブボリュームの前記推定最大画面値差が所定の閾値よりも小さくなるまで再帰的に選択する、
ための命令を含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項38】
前記複数のサブボリュームの部分集合の1つ内にあるレイ経路上の最大データ値を識別するための命令は、
サブボリュームの所定の位置でのデータ値を推定し、
前記推定データ値が前記現在のデータ値記録よりも高い場合に、前記レイの現在のデータ値記録を更新し、
前記レイが前記採取データセットを出るまで、前記部分集合の全ての残っているサブボリュームに対して前記推定及び更新する段階を繰り返す、
ための命令を含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項39】
前記サブボリュームは、2×2×2セル又は少なくとも前記レイの前記断面を超える寸法を有するセル又はサブセルを含む最小サブボリュームであることを特徴とする請求項38に記載のコンピュータプログラム製品。
【請求項40】
前記2D画像平面上の他の位置のピクセル値を推定するための命令は、
各位置を取り囲みかつ4つの投射レイに関連する4つピクセル値を選択し、
前記4つのピクセル値を用いて前記位置でのピクセル値をバイリニア補間する、
ための命令を含むことを特徴とする請求項28に記載のコンピュータプログラム製品。
【請求項41】
採取された3Dデータセットによって表された3Dオブジェクトの2D画像を発生させる方法であって、
採取された3Dデータセットを異なるサイズの複数のサブボリュームにフラグメント化し、一組のデータ値パラメータに付随する各サブボリュームが、該サブボリューム内のデータ値分布を特徴付ける段階と、
2D放射面から前記複数のサブボリュームに向けて、各々が初期データ値記録及び断面を有して該2D放射面に対して所定の方向に放出される複数のレイを選択的に投射する段階と、
前記2D放射面上の複数の位置で、各々が前記複数のレイ経路の1つに沿った最大データ値を特徴付ける複数のピクセル値を選択的に発生させる段階と、
前記2D放射面上の前記複数の位置での前記複数のピクセル値の部分集合を用いて、該2D放射面上の他の位置のピクセル値を推定する段階と、
を含むことを特徴とする方法。
【請求項42】
初期データ値のレイがそのレイ経路に沿って3Dデータセットと相互作用する時の最大データ値を識別する方法であって、
各サブボリュームがサブボリューム内の最大、平均、及び最小データ値を含む一組のデータ値パラメータに関連する異なるサイズの複数のサブボリュームに3Dデータセットをフラグメント化する段階と、
前記3Dデータセットのデータ値に依存する単調画面転送関数を定義する段階と、
前記レイ経路に沿って、どの選択したサブボリュームの最大データ値も該レイの現在のデータ値記録よりも高く、かつ該選択したサブボリュームの最大画面転送差が所定の閾値よりも低いような一組のサブボリュームを選択する段階と、
前記選択された組の各サブボリュームに対して、該サブボリューム内の所定の位置でのデータ値を推定し、該推定データ値が前記レイの現在のデータ値記録よりも高い場合には、該推定データ値で該レイの現在のデータ値記録を更新する段階と、
を含むことを特徴とする方法。
【請求項43】
前記所定の位置は、選択されたサブボリューム内の前記レイ経路の中心であることを特徴とする請求項42に記載の方法。
【請求項44】
多次元データセットの部分集合内のデータ値を識別する方法であって、
各々が関連するデータ値パラメータの組を有する異なるサイズの複数のサブデータセットにデータセットをフラグメント化する段階と、
各ノードが前記サブデータセットの1つに関連する複数のノードを有する階層データ構造を構成する段階と、
前記部分集合の一意的な部分を網羅するサブデータセットを識別する段階と、
前記部分集合の前記一意的な部分が前記データ値を含むかを検査する段階と、
前記部分集合を完全に網羅する一連のサブデータセットが識別されるまで前記識別する段階及び検査する段階を繰り返す段階と、
を含むことを特徴とする方法。
【請求項45】
初期データ値が、前記部分集合に割り当てられ、該初期データ値は、前記一意的な部分内の現在のデータ値が所定の条件を満足する場合には該現在のデータ値と入れ替えられることを特徴とする請求項44に記載の方法。
【請求項46】
前記所定の条件は、前記現在のデータ値が前記初期データ値よりも高く、かつ前記得られたデータ値が前記部分集合の最大データ値であることを含むことを特徴とする請求項45に記載の方法。
【請求項47】
前記所定の条件は、前記現在のデータ値が前記初期データ値よりも低く、かつ前記得られたデータ値が前記部分集合の最小データ値であることを含むことを特徴とする請求項45に記載の方法。
【請求項48】
前記部分集合は、前記多次元データセット内の所定の多次元領域内に位置するデータ値を含むことを特徴とする請求項44に記載の方法。
【請求項49】
前記所定の多次元領域は、前記多次元データセット内の線上又は線の近くに位置するデータ値を含むことを特徴とする請求項48に記載の方法。
【請求項50】
前記所定の多次元領域は、前記多次元データセット内の曲線上又は曲線の近くに位置するデータ値を含むことを特徴とする請求項48に記載の方法。
【請求項51】
前記所定の多次元領域は、前記多次元データセット内の平面上又は平面の近くに位置するデータ値を含むことを特徴とする請求項48に記載の方法。
【請求項52】
前記所定の多次元領域は、前記多次元データセット内の曲面上又は曲面の近くに位置するデータ値を含むことを特徴とする請求項48に記載の方法。
【請求項53】
前記一連のサブデータセット内の最大サイズのサブデータセットが、最初に識別されて検査されることを特徴とする請求項44に記載の方法。
【図1A】
【図1B】
【図1C】
【図1D】
【図2】
【図3A】
【図3B】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10A】
【図10B】
【図11】
【図12】
【図13A】
【図13B】
【図1B】
【図1C】
【図1D】
【図2】
【図3A】
【図3B】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10A】
【図10B】
【図11】
【図12】
【図13A】
【図13B】
【公表番号】特表2007−503061(P2007−503061A)
【公表日】平成19年2月15日(2007.2.15)
【国際特許分類】
【出願番号】特願2006−524013(P2006−524013)
【出願日】平成16年8月18日(2004.8.18)
【国際出願番号】PCT/US2004/026819
【国際公開番号】WO2005/020142
【国際公開日】平成17年3月3日(2005.3.3)
【出願人】(505375676)フォヴィア インコーポレイテッド (2)
【氏名又は名称原語表記】Fovia,Inc
【住所又は居所原語表記】555 Bryant Street, No.242 Palo Alto,California 94301,U.S.A.
【Fターム(参考)】
【公表日】平成19年2月15日(2007.2.15)
【国際特許分類】
【出願日】平成16年8月18日(2004.8.18)
【国際出願番号】PCT/US2004/026819
【国際公開番号】WO2005/020142
【国際公開日】平成17年3月3日(2005.3.3)
【出願人】(505375676)フォヴィア インコーポレイテッド (2)
【氏名又は名称原語表記】Fovia,Inc
【住所又は居所原語表記】555 Bryant Street, No.242 Palo Alto,California 94301,U.S.A.
【Fターム(参考)】
[ Back to top ]