(57)【要約】連続する奥行で連続の2Dスライスとしてメモリ(890)に格納された3Dデータセットで表される3Dボリュームを視覚化するシステムである。メモリキャッシュ895は、データセットの一部への高速アクセスを提供する。プロセッサ860は、n1×n2ピクセルの対応の長方形に3Dボリュームを通じてn1×n2の平行光線の束を放つことにより、ボリュームの2D表示を生成する。光線毎にn3のサンプルを順次決定する毎に、それぞれn1×n2×n3のサンプルの束のブロックの連続を施す。束のブロックに寄与するボクセルの3Dのセットを決定するために所定の補間関数が使用される。束のブロックのサイズは、ボクセルの決定されたセットがキャッシュに適合するように選択される。ボクセルのセットは、キャッシュからサンプリングされる。
2006518510.tif 000002
【特許請求の範囲】
【請求項１】
特に医療用途で、３次元(以下3Dという)ボリュームを視覚化するシステムであって、
連続する奥行で２次元(以下2Dという)スライスに構成された前記3Dボリュームのボクセル値を表すデータセットを受信する入力と、
前記データセットを格納し、各スライスがメモリの連続ブロックに格納されるメモリと、
前記メモリに格納された前記データセットの一部を一時的に格納し、キャッシュのデータへの高速アクセスを提供するメモリキャッシュと、
コンピュータプログラムの制御で、
n1×n2ピクセルの対応の長方形に3Dボリュームを通じてn1×n2の平行光線の束を放ち、光線毎にn3の順次のサンプルを順次決定する毎に、それぞれn1×n2×n3のサンプルの束のブロックの連続を施し、n1＞1且つn2＞1且つn3＞1であり、
束のブロック毎に、前記束のブロックに寄与するボクセルの3Dのセットを決定するために所定の補間関数を使用し、n1、n2及びn3は、ボクセルの決定されたセットが前記キャッシュに適合するように選択され、ボクセルの決定されたセットを前記メモリから前記キャッシュにロードし、キャッシュからサンプリングを実行することにより、
前記ボリュームをピクセルの架空の2D投影スクリーンに投影することで、前記ボリュームの2D表示を得るように前記データセットを処理するプロセッサと、
レンダリング用に前記2D表示のピクセル値を提供する出力と
を有するシステム。
【請求項２】
請求項１に記載のシステムであって、
前記キャッシュは、前記プロセッサのレベル１のキャッシュであるシステム。
【請求項３】
請求項１に記載のシステムであって、
前記キャッシュは、レベル２のキャッシュであり、
前記システムは、前記プロセッサのレベル１のキャッシュを更に有し、
前記レベル１のキャッシュは、前記レベル２のキャッシュより高速にデータへのアクセスを提供し、
前記レベル２のキャッシュは、前記レベル１のキャッシュより大きく、
前記プロセッサは、
束のブロック毎に、それぞれm1×m2×m3の前記束のブロック内の下位の束のブロックの連続を決定し、それぞれ連続の下位の束のブロックは、更に前記光線に沿った方向のm3のサンプルであり、1＜m1＜n1且つ1＜m2＜n2且つ1＜m3＜n3であり、
下位の束のブロック毎に、
前記下位の束のブロックに寄与するボクセルの3Dのセットを決定するために、所定の補間関数を使用し、m1、m2及びm3は、ボクセルの決定されたセットが前記レベル１のキャッシュに適合するように選択され、
ボクセルの決定されたセットを前記レベル２のキャッシュから前記レベル１のキャッシュにロードし、
前記レベル１のキャッシュからサンプリングを実行する
ように動作可能であるシステム。
【請求項４】
請求項１に記載のシステムであって、
n1=n2=n3であるシステム。
【請求項５】
請求項１に記載のシステムであって、
前記キャッシュは、それぞれ同じ所定のキャッシュラインのサイズを備えて、複数のキャッシュラインで構成され、
前記スライスは、前記キャッシュラインのサイズの倍数の前記メモリにおいて連続のスライスの間にオフセットを備えて前記メモリに順次格納されるシステム。
【請求項６】
請求項５に記載の方法であって、
前記記憶装置は、スライス毎に前記メモリの前記スライスの開始アドレスを示すメモリアドレスを格納するスライス参照テーブルを有するシステム。
【請求項７】
特に医療用途で、３次元(以下3Dという)ボリュームを視覚化する方法であって、
前記3Dボリュームは連続する奥行で２次元(以下2Dという)スライスに構成されたボクセル値のデータセットで表され、各スライスはメモリの連続ブロックに格納され、前記メモリに格納された前記データセットの一部を一時的に格納してキャッシュのデータへの高速アクセスを提供するメモリキャッシュを通じてアクセス可能であり、
n1×n2ピクセルの対応の長方形に前記ボリュームを通じてn1×n2の平行光線の束を放ち、光線毎にn3の順次のサンプルを順次決定する毎に、それぞれn1×n2×n3のサンプルの束のブロックの連続を施し、n1＞1且つn2＞1且つn3＞1であり、
束のブロック毎に、前記束のブロックに寄与するボクセルの3Dのセットを決定するために所定の補間関数を使用し、n1、n2及びn3は、ボクセルの決定されたセットが前記キャッシュに適合するように選択され、ボクセルの決定されたセットを前記メモリから前記キャッシュにロードし、キャッシュからサンプリングを実行することにより、
前記ボリュームを架空の2D投影スクリーンに投影することで、前記ボリュームの2D表示を得るようにデータセットを処理することを有する方法。
【請求項８】
プロセッサに請求項７に記載のステップを実行させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特に医療用途で、３次元(以下“3D”という)ボリュームを視覚化するシステムに関するものである。本発明はまた、このようなシステムで使用するソフトウェアに関するものである。本発明は、３次元3Dボリュームを視覚化する方法に更に関するものである。
【背景技術】
【０００２】
(専用の事前プログラムのハードウェア又はプログラム可能プロセッサの形式の)デジタル処理ハードウェアの更なる能力で、ボリューム測定データセットから高品質画像を生成する実際のシステムでレンダリング・アルゴリズム(rendering  algorithm)を使用することが可能になってきた。医療用途では、ボリューム測定データセットは、一般的にCT(Computed  Tomography)スキャナ又はMR(Magnetic  Resonance)スキャナのような3Dスキャナを使用して取得される。ボリューム測定データセットは、スカラ値の３次元のセットで構成される。これらの値が得られる位置はボクセルと呼ばれ、ボクセルはボリューム・エレメントの省略である。ボクセルの値は、ボクセル値と呼ばれる。図１は、８のボクセル110で囲まれた立方体100を示している。立方体は、ボクセル立方体又はセルと呼ばれる。
【０００３】
医療用スキャナでは、一般的にデータはスライス毎に構成され、各スライスは２次元である。スライスの値は濃淡値として表すことができる。スライスのスタックは３次元データセットを作る。3Dデータセットの内容を視覚化する既知の比較的簡単な技術は、マルチプラナー・リフォーマッティング(multi-planar  reformatting)と呼ばれる。この技術は、3Dデータセットの隣接したボクセルからの断面でボクセルを‘再サンプリング’することにより、ボリューム測定データを通じて任意の断面を生成するために使用可能である。ほとんどの場合、平面2D断面が使用される。原則として、他の曲線の断面も生成可能である。この技術により、データが取得された方向に無関係に、オペレータが画像を見ることが可能になる。
【０００４】
図２は、全体の不連続データフィールドを入力として受け取り、このデータフィールドを２次元スクリーン210に投影する更に高度なボリューム視覚化アルゴリズムを示している。それぞれの投影は、ユーザにより選択可能でもよく、動的に変更されてもよい(例えばボリュームを通じた仮想ツアーを与える)所定の視点220からのものである。これは、架空の投影スクリーンの各ピクセル(i,j)及びデータフィールドを通じた視点から光線230を放つことにより、実現される。光線に沿った不連続なk個の位置240、242、244、246(薄い灰色で示す)で、データは隣接したボクセルから再サンプルされる。ボリュームの光線の位置に近いボクセルに基づいてピクセル(i,j)のピクセル値を計算する多様な既知のレンダリング・アルゴリズムが知られている。このようなレンダリング・アルゴリズムの例には、ボリューム・レンダリング及びiso-surfaceレンダリングがある。ボリュームの十分に外側の位置からボリュームを観測することにより、図３及び４(簡単にするために2次元の図である)に示すように、放っている光線は、2Dスクリーンに画像を投影する平行光線により表現可能である。一般的に、投影情報の集積は、投影光線に沿って得られるサンプルに適用される関数を通じて実行される。一般的なボリューム視覚化関数には、平均値と、最大値(いわゆる最大値投影法(Maximum  Intensity  Projection)、すなわちMIP)と、最小値と、半透明ブレンド(アルファブレンディングとも呼ばれる)とがある。所要のサンプル位置でボリュームに補間フィルタ関数を適用することで、投影関数で必要なサンプルが作られる。図５は、投影光線に沿って得られるサンプル(点510で示す)を受け取る2D図を示している。長方形はボクセルを示している。得られるサンプルについて、サンプル位置の付近のボクセル値は、ボリュームから取り出されなければならない。必要なボクセル値の数は、補間関数の程度に依存する。一般的に、最も近い８個のボクセルがボクセルに対するサンプルの距離に基づいて重み付けされてサンプルに寄与するトリリニア補間関数(tri-linear  interpolation  function)が使用される。１つの光線のサンプルの線形補間の間にアクセスされるボクセルは、陰付きを使用して示している(図は簡単のため2Dである)。
【０００５】
マルチスライスのCTボリュームデータは、しばしば1000スライスの5122の16ビットボクセルで構成される。これは、合計約500Mバイトのデータになる。従来では、サンプルは光線毎に処理され、光線は行毎及び列毎に走査される。前述のように、各サンプルは、サンプル毎に多数のボクセルの処理を必要とすることがある。全体として、処理システムの処理能力及び記憶帯域に高い需要がかかる。
【０００６】
最新のプロセッサは、大量のメモリへの高速アクセスを提供する中間キャッシュメモリを通じてメモリのデータにアクセスする(キャッシュラインと呼ばれる)。キャッシュラインは、しばしば32又は64バイトのデータである(16ビットのボクセルの場合には、キャッシュラインは16又は32のボクセルを保持する)。単一のボクセルにアクセスするとき、キャッシュラインの残りのボクセルに実際にアクセスするか否かにかかわらず、全体のキャッシュラインがメモリから取り出され、キャッシュに格納される。メモリに格納された順にボクセルにアクセスすることは、次のボクセルがキャッシュラインから取り出されるため、16又は32のボクセル毎に単一のメモリアクセスを生じる。キャッシュは、多様なメモリ位置が同じキャッシュラインにマッピングするという特性を有する。このことは、医療用画像の連続のスライスにおける対応のボクセルの場合に典型的である。
【０００７】
医療用画像では、いわゆる2Dスライスのスタックにボリュームデータを格納することが一般的である。各スライスはボクセルの複数の行及び列で構成される。図６Ａは、スライスのスタックで構成されるこのボリューム測定データの構成を示している(８個のスライス610を示す)。１つのスライスについて、ボクセルの行及び列への構成が図示されている。その例では、８個の列が図示されており、それぞれ８個の列を有する。図６Ｂに示すように、各スライスは、メモリの連続ブロックに配置されている。このようなボリュームデータの配置により、多様な画像処理及びボリューム視覚化アルゴリズムが、ストライド(stride)を用いて３つの直交方向でボクセルにアクセスすることが可能になる。1のストライドでの行のアクセスと、行の長さのストライドでの列のアクセスと、行×列の長さのストライドでのスライスのアクセスである。このように構成されたボリューム測定データにアクセスするときに、メモリアクセス回数にかなりの差が存在する。行方向の連続的なボクセルへのアクセスは、前述のように、16又は32ボクセル毎に単一のメモリアクセスを必要とする。列方向及びスライス方向に連続的なボクセルにアクセスするときに、アクセスされるボクセル毎にメモリアクセスが必要となる。これは、図７に示すように、同時に複数のボクセルにアクセスすることにより、回避可能である。陰付きのボクセルは、単一のキャッシュラインのボクセルを表す。行のアクセスは、常にキャッシュを最適に利用する。同時の列及びスタックのアクセスもまた、キャッシュを最適に利用する。
【０００８】
複数の同時アクセスに対する手法は、ソースのボリュームと一致したアクセス方向にのみ直接適用可能である。任意の投影方向では、この手法は失敗する。更に、複数の光線の同時処理についてのループ制御構造が複雑になり、投影方向に依存する。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ボリューム視覚化を実行する改善アルゴリズムを提供し、特に現在の処理システムの機能をうまく利用することが、本発明の目的である。
【課題を解決するための手段】
【００１０】
本発明の目的を満たすため、特に医療用途で、３次元ボリュームを視覚化するシステムは、
順次に連続する奥行で２次元スライスに構成された3Dボリュームのボクセル値を表すデータセットを受信する入力と、
データセットを格納し、各スライスがメモリの連続ブロックに格納されるメモリと、
メモリに格納されたデータセットの一部を一時的に格納し、キャッシュのデータへの高速アクセスを提供するメモリキャッシュと、
コンピュータプログラムの制御で、
n1×n2ピクセルの対応の長方形に3Dボリュームを通じてn1×n2の平行光線の束を放ち、光線毎にn3の順次のサンプルを順次決定する毎に、それぞれn1×n2×n3のサンプルの束のブロックの連続を施し、n1＞1且つn2＞1且つn3＞1であり、
束のブロック毎に、束のブロックに寄与するボクセルの3Dのセットを決定するために所定の補間関数を使用し、n1、n2及びn3は、ボクセルの決定されたセットがキャッシュに適合するように選択され、ボクセルの決定されたセットをメモリからキャッシュにロードし、キャッシュからサンプリングを実行することにより、
ボリュームをピクセルの架空の2D投影スクリーンに投影することで、ボリュームの2D表示を得るようにデータセットを処理するプロセッサと、
レンダリング用に2D表示のピクセル値を提供する出力と
を有する。
【００１１】
現在のコンピュータシステムでは、メモリ待ち時間は、プロセッサのサイクル時間(＜1ns)に対して大きい(〜50ns)。通常では、キャッシュ待ち時間は数プロセッササイクル(〜5ns)に過ぎない。プロセッサのサイクル時間がメモリのアクセス待ち時間の減少よりかなり早く減少し続けるため、プロセッサのサイクル時間とメモリのアクセス待ち時間との間の相違は増大すると予想される。医療用画像表示に使用されるワークステーションは、約1Gバイトのメモリと、1ns未満のサイクル時間を備えたプロセッサと、約2Mバイトのキャッシュメモリとを有する。一般的なボリューム視覚化技術は、サンプル毎に100サイクルのオーダを必要とする。50nsのメモリ及び1nsのサイクル時間では、サンプル毎に２回より多くメモリにアクセスするときに、プロセッサはメモリの帯域で制限を受ける。トリリニア補間では、ボクセルがキャッシュでまだ利用可能になっていない場合には、サンプル毎に８個のボクセルにアクセスする必要があり、８のメモリアクセスを必要とする。マルチスライスのCTボリュームデータは、しばしば1000スライスの5122の16ビットボクセルで構成される。これは、合計約500Mバイトのデータになり、明らかにキャッシュメモリに完全には入らない。光線毎の従来の処理では、キャッシュにないボクセルに頻繁にアクセスする。一般的に、ロードされたボクセルは、光線に沿った後のサンプルのうちの１つに必要なボクセルで上書きされる。ボクセルは複数の隣接した光線に必要であるため、同じボクセルが繰り返しキャッシュにロードされることがある。本発明によるシステムでは、ブロックのサンプルに寄与する全てのボクセルがキャッシュにロードされるように、光線処理がサンプルの3Dブロックに構成される。ブロックのサイズ及びメモリ内のボクセルのアドレスは、このことが可能であるように選択される。このことにより、キャッシュに同じボクセルを繰り返しロードすることを回避し、それによって、ボリューム視覚化性能をかなり増加させる。
【００１２】
従属項２の方策によれば、ボクセルのセットは、非常に高速に動作するプロセッサのレベル１のキャッシュに適合する。
【００１３】
従属項３の方策によれば、同じ原理が少なくとも２つのレベルに適用される。全体のボクセルのセットは、レベル２のキャッシュに適合する束のブロックに分割される。束のブロックは、プロセッサのレベル１のキャッシュに適合する下位の束のブロックに更に再分割される。このことは、メインメモリへのアクセスに比べて、全体として束のブロックへの高速のアクセスを生じ、実際のサンプリング中の下位の束のボクセルへの高速のアクセスをも生じる。従って、まず束のブロックが決定され、第２レベルのキャッシュにロードされる。次に、下位の束のブロックが決定され、第１レベルのキャッシュにロードされ、下位の束のブロック内のサンプルに対してサンプリングが実行される。下位の束のブロックの処理は、非常に高速になり得る。束のブロックのボクセルは、複数の下位の束のブロックに必要でもよい(例えば、補間の程度のため、下位の束のブロックの端に近いボクセルが、１つより多い下位の束のブロックのサンプリングに使用されてもよい)。第２レベルのキャッシュに既に存在するため、これらのボクセルは、非常に高速に第１レベルのキャッシュにロードされ得る。
【００１４】
従属項４の方策によれば、束のブロックは立方体であり、如何なる視覚方向からでも同じボリューム視覚化速度を提供する(すなわち、視覚化性能は投影方向に無関係である)。
【００１５】
従属項５の方策によれば、3Dデータセットの2Dスライスは、キャッシュラインのサイズの倍数のオフセットを備えてメモリに格納される。束のブロックの処理に必要なボクセルがキャッシュに入るとしても、必要なボクセルを備えたメモリの異なる部分は同じキャッシュラインにマッピングされてもよい。オフセットを導入することにより、連続するスライスのボクセルが同じキャッシュラインにマッピングされないことが確保され、束のブロックをレンダリングするために必要なボクセルの全体集合のキャッシュへの同時ロードを可能にする。
【００１６】
従属項６の方策によれば、スライス参照テーブルが使用される。これは、メモリ内のスライスの格納を制御する効果的な方法である。
【００１７】
本発明の目的を満たすため、特に医療用途で、3Dボリュームを視覚化する方法は、
3Dボリュームは連続する奥行で2Dスライスに構成されたボクセル値のデータセットで表され、各スライスはメモリ(890)の連続ブロックに格納され、メモリに格納されたデータセットの一部を一時的に格納してキャッシュのデータへの高速アクセスを提供するメモリキャッシュ(895)を通じてアクセス可能であり、
n1×n2ピクセルの対応の長方形にボリュームを通じてn1×n2の平行光線の束を放ち、光線毎にn3の順次のサンプルを順次決定する毎に、それぞれn1×n2×n3のサンプルの束のブロックの連続を施し、n1＞1且つn2＞1且つn3＞1であり、
束のブロック毎に、束のブロックに寄与するボクセルの3Dのセットを決定するために所定の補間関数を使用し、n1、n2及びn3は、ボクセルの決定されたセットがキャッシュに適合するように選択され、ボクセルの決定されたセットをメモリからキャッシュにロードし、キャッシュからサンプリングを実行することにより、
ボリュームを架空の2D投影スクリーンに投影することで、ボリュームの2D表示を得るようにデータセットを処理することを有する。
【発明を実施するための最良の形態】
【００１８】
本発明の前記及び他の態様は、以下に記載の実施例を参照して明らかになり、実施例を参照して説明する。
【００１９】
ボリュームを視覚化するシステム及びそれを行う方法について、医療用途について説明する。そのシステム及び方法は、測定結果の処理が対象物のボリューム(の一部)を表す３次元データセット(3D配列の測定)を生じ、各データ要素又はボクセルが対象物の特定の位置に関係し、対象物の１つ以上のローカル特性に関係する値を有する(例えば、有効な時間に容易に開けることができない対象物のX線検査)という事実を特徴とする、他の用途(一般的にシステムで測定可能な全対象物の内部及び構成の検査)にも同様に適用可能であることがわかる。
【００２０】
図８は、本発明によるシステムのブロック図である。そのシステムは、ワークステーションや高性能パーソナルコンピュータのような従来のコンピュータシステムに実装されてもよい。システム800は、3Dボリュームのボクセル値を表すデータの３次元のセットを受信する入力810を有する。データは、Ethernet(登録商標)のような従来のコンピュータネットワークを介して供給されてもよく、有線若しくは無線又はその組み合わせの電気通信ネットワークを介して供給されてもよく、フラッシュメモリのような固体メモリを含み、テープやCDやDVD等のような磁気又は光記録用の一般的な情報担体を読み取るコンピュータ周辺機器を介して供給されてもよい。図８において、画像は、医療用MR又はCTスキャナのような画像収集装置820により取得される。このような収集装置はシステムの一部でもよいが、システムの外部にあってもよい。そのシステムは、データセットを格納する記憶装置830を有する。記憶装置はハードディスクのような永久式であることが好ましい。システムの出力840は、レンダリング用に２次元画像のピクセル値を提供するために使用される。それは、例えば表示用の他のコンピュータシステムへのネットワークを通じたビットマップ式画像として、如何なる適切な形式で画像を供給してもよい。代替として、出力は、適切なディスプレイ850への画像の直接のレンダリング用のグラフィックカード／チップセットを有してもよい。ディスプレイは必ずしもシステムの一部でなくてもよい。システムは、立体表示用に２つの2D画像を同時に提供可能でもよい。その場合には、２つの画像は、観察者のそれぞれの目にそれぞれ対応する２つの異なる視点から作られる。そのシステムは、コンピュータプログラムの制御で、ボリュームの２次元表示を得るようにデータセットを処理するプロセッサ860を更に有する。プログラムは、実行のため、記憶装置830のような永久記憶装置からRAMのようなワーキングメモリ890にロードされてもよい。この例では、実行中に記憶装置830からデータを格納するために、同じメモリ890が使用されてもよい。データセットがメインメモリに完全に格納されるには大きすぎる場合、記憶装置830は仮想メモリとして動作してもよい。プロセッサ860は、2D投影画像のピクセル毎に所定の視点から架空の2D投影スクリーンにボリュームを投影するように動作可能である。
【００２１】
図８のコンピュータシステムの３つの重要な構成要素は、プロセッサと、メモリと、キャッシュメモリである。現在のコンピュータシステムでは、メモリ待ち時間は、プロセッサのサイクル時間(＜1ns)に対して大きい(〜50ns)。通常では、キャッシュ待ち時間は数プロセッササイクル(〜5ns)に過ぎない。プロセッサは、キャッシュメモリを通じてメモリにアクセスし、メモリアクセス待ち時間の影響を低減する。図９は、3D医療用データの高性能レンダリング用の好ましい構成を示している。このシステムでは、3Dデータセットを有する単一のメモリ950への高速アクセスを提供する各キャッシュ(912、922、932及び942で示す)をそれぞれ備えた複数のプロセッサ(910、920、930及び940で示す)を備えた対称型マルチプロセッシング(SMP:Symmetric  Multi-Processing)アーキテクチャが使用されている。一般的にプロセッサに内蔵されてキャッシュのデータへの非常に高速のアクセスを提供する第１レベルのプロセッサキャッシュと、メモリより高速であるが第１レベルのキャッシュより低速である第２レベルのキャッシュとを備えたマルチキャッシュ階層が使用されることが好ましい。このような多層キャッシュは既知であり、更に説明しない。図９の例では、キャッシュ912、922、932及び942が第２レベルのキャッシュであり、キャッシュ914、924、934及び944がそれぞれの第１レベルのキャッシュである。最新式の第１レベルのキャッシュは64Kバイトのオーダである。第２レベルのキャッシュは、0.5Mバイトから数Mバイトのオーダである。プロセッサ及びメモリ技術の進歩とともにキャッシュサイズが増加する。本発明による処理アーキテクチャは、単一のキャッシュのみを備えた単一のプロセッサシステムにも使用可能であることがわかる。プロセッサのサイクル時間がメモリのアクセス待ち時間の減少よりかなり早く減少し続けるため、プロセッサのサイクル時間とメモリのアクセス待ち時間との間の相違は増大すると予想される。医療用画像表示に使用されるワークステーションは、約1Gバイトのメモリと、1ns未満のサイクル時間を備えたプロセッサと、約2Mバイトの第２レベルのキャッシュメモリとを有する。
【００２２】
一般的なボリューム視覚化技術は、サンプル毎に100サイクルのオーダを必要とする。50nsのメモリ及び1nsのサイクル時間では、サンプル毎に２回より多くメモリにアクセスするときに、プロセッサはメモリの帯域で制限を受ける。トリリニア補間では、ボクセルがキャッシュでまだ利用可能になっていない場合には、サンプル毎に８個のボクセルにアクセスする必要があり、８のメモリアクセスを必要とする。マルチスライスのCTボリュームデータは、しばしば1000スライスの5122の16ビットボクセルで構成される。これは、合計約500Mバイトのデータになる。明らかに、このデータ量はキャッシュメモリに完全には入らない。
【００２３】
キャッシュメモリは、大量のメモリへの高速アクセスを提供する。一般的に、キャッシュは、一般的にはそれぞれ32又は64バイトのデータを格納するキャッシュラインに構成される。このようなキャッシュラインは、一般的な2バイトのボクセルについて16又は32のボクセルを保持する。単一のボクセルにアクセスするとき、キャッシュラインの残りのボクセルに実際にアクセスするか否かにかかわらず、全体のキャッシュラインがメモリから取り出され、キャッシュに格納される。メモリに格納された順にボクセルにアクセスすることは、次のボクセルがキャッシュラインから取り出されるため、16又は32のボクセル毎に単一のメモリアクセスを生じる。
【００２４】
結合性は、特定のメモリ位置がマッピングされるキャッシュラインを定めるキャッシュの特性である。直接マッピングのキャッシュでは、キャッシュのサイズを法とするメモリ位置は、同じキャッシュラインにマッピングする。このようなメモリ位置は、同じキャッシュラインに関連付けられる。2-way  set  associativeキャッシュでは、キャッシュの半分サイズを法とするメモリ位置は、同じキャッシュラインの対にマッピングし、それぞれの対は同じ結合性を有する。例えば、2Mバイトの直接マッピングのキャッシュでは、2Mバイトだけ離れたメモリ位置は同じキャッシュラインにマッピングする。5122の16ビットのスライスでは、各スライスは0.5Mバイトのメモリを占有する。連続的に配置されたボリュームでは、３つおきのスライスのボクセルが同じキャッシュラインにマッピングする。キャッシュの結合性の特性は、光線に沿って特定の距離を置いたサンプルが同じキャッシュ位置にマッピングすることを生じる。光線が１つずつ処理される場合、光線がボリュームを通じて進むときにキャッシュ内容が置き換えられるため、このことはキャッシュの最適な使用を生じない。
【００２５】
図１０は、キャッシュにアクセスする例と、キャッシュラインへのメモリ位置のマッピングの例とを示している。この例では、32ビットのメモリアドレスが使用されている。キャッシュラインは、64(=26)バイトを格納する。キャッシュ1030は、1024(=210)のキャッシュラインを構成し、64Kバイトの全体キャッシュサイズを提供する(第１レベルのキャッシュに典型的である)。キャッシュライン毎に、キャッシュラインに現在マッピングされている32バイトの部分の16の最上位アドレスビットを示す16ビットが格納されている。図面において、16ビットアドレスがキャッシュライン1040について数字1020を使用して一度のみ図示されている。メモリにアクセスするため、32ビットのアドレス1010は３つの部分に分割される。6の最小位ビット1012は、キャッシュライン内のバイトを示す。次の10ビット(1014で示す)は、キャッシュラインを示す。新しいメモリアドレスが提供される毎に、10ビット1014を使用してキャッシュラインが決定される。フィールド1020のキャッシュラインについて格納される16ビットは、アドレスの16の最上位ビット1016と比較される。これが一致する場合、要求のデータを含む64バイトのデータ部分は、既にキャッシュラインに存在している。6の最小位ビット1012は、キャッシュラインから所望のデータを取り出すために使用される。一致しない場合、データはキャッシュにまだ存在しない。関連の64バイト部分がメモリから取り出され、対応のキャッシュラインに格納される。
［束のブロック］
本発明によれば、プロセッサは、3×5の光線の束で図１１に示すように、n1×n2ピクセルの長方形にボリュームを通じて平行光線の束を放つようにプログラムされる。束は、投影光線の長方形の集合として定義される。各束は、結果の投影画像(ボリューム視覚化の結果)でのピクセルの長方形の集合を生成する。光線の束を同時に処理することに加えて、各光線に沿った限られた数のサンプルのみが取り込まれる。このことは、サンプルの束のブロックを生じる。全ての光線に沿って、n3の順次のサンプルが決定される。本来、１つの光線に沿ってサンプルを決定する方法は知られている。ここでは、この機構は、n1×n2の光線に沿ってn3のサンプルを決定するために使用される。n1＞1且つn2＞1且つn3＞1であることがわかる。この機構は、それぞれn1×n2×n3のサンプルの束のブロックの連続を生じ、更に光線の束に沿ってn3のサンプルを生じる。束のブロックに寄与するボクセルの3Dのセットを決定するために、所定の補間関数が使用される。従来のトリリニア補間関数を使用して、この3Dのセットは、ブロック内のボクセルにブロック周辺のもう１つのボクセルの奥行のシェルを加えたもので構成される。これが図１２に2Dで図示されている。点はサンプルを示し、灰色の領域はボクセルを示している。陰付きのボクセルは、4×4の束のブロックのサンプルのトリリニア補間に必要なボクセルを示している。一般的な束のブロックは、32×32×32のサンプル点である。この例では、26の明確なボクセルにアクセスするが、16のトリリニア補間には48のボクセルが必要である。
【００２６】
一般的に、n1×n2×n3の所定の束のブロックのサイズと、それぞれz1、z2、z3のズーム因子と、それぞれk1、k2、k3の補間の中心サイズについて、束のブロックをレンダリングするために合計で
(n1/z1+k1)*(n2/z2+k2)*(n3/z3+k3)
のボクセルが必要になる。この式で、ズーム因子は、サンプルの距離とボクセルの距離との間の関係である(例えば、ボクセルの数に対して２倍の数のサンプル)。必要なキャッシュラインの実際の数は、ボクセルのグリッドに対する束のブロックの方向と、キャッシュラインの大きさとに依存する。当業者は、例えば方向に無関係にキャッシュに適合する束のブロックを選択するように、容易に適切な手法を選択することができ、また、所定の方向について最大サイズの束のブロックを計算することができる。
【００２７】
本発明によれば、n1、n2及びn3は、ボクセルの決定されたセットがキャッシュに適合するように選択される。前述の式を使用して、当業者はこのようなブロックを容易に選択することができる。この選択の結果として、ボクセルの決定されたセットは、記憶装置からプロセッサのキャッシュにそのまま全部ロードされ得る。これは、キャッシュからのサンプリングの実行を可能にする。サンプリング自体は既知であり、更にここで説明しない。
【００２８】
束のブロックは立方体(n1=n2=n3)であり、システムの動作を方向に独立にすることが好ましい。
【００２９】
束のブロックは、関連のボクセルのセットが第１レベル又は第２レベルのキャッシュに適合するように選択されてもよい。好ましい実施例では、関連のボクセルがより大きい低速の第２レベルのキャッシュに全て適合する大きい束のブロックになる。大きい束のブロックは、ボクセルの関連のセットが高速の(より小さい)第１レベルのキャッシュに適合する小さい下位の束のブロックに分割される。この再分割は、ボクセルの全体のセットが束のブロックに分割されるものと全く同じ原理に従い、ここでは束のブロックが下位の束のブロックに分割される。再分割を記述する１つの方法は、束のブロック毎に、それぞれm1×m2×m3の下位の束のブロックの連続を決定することである。ただし、1＜m1＜n1且つ1＜m2＜n2且つ1＜m3＜n3である。それぞれの連続の下位の束のブロックは、更に光線に沿った方向のm3のサンプルである。下位の束のブロック毎に、下位の束のブロックに寄与するボクセルの3Dのセットを決定するために、所定の補間が使用される。ボクセルの決定されたセットがレベル２のキャッシュからレベル１のキャッシュにロードされる。m1、m2及びm3は、ボクセルの決定されたセットがレベル１のキャッシュに適合するように選択される。前述のように、ズーム因子を検討してもよい。下位のブロックのレベルでのサンプリングは、レベル１のキャッシュから実行される。
【００３０】
全体のボリュームをサンプリングするために、多数の束のブロック(又は下位の束のブロック)がサンプリングされる必要があることがわかる。ボリュームの端を横断する束のブロックは、ボリュームの境界の外にアクセスすることを回避するために、クリッピングを必要とする。クリッピングは、サンプリング中に更なるオーバーヘッドを取り込むため、クリッピングは、ボリュームの境界を実際に横断するブロックに限定されてもよい。図１３は、陰付きを使用して１つ以上のボクセルのクリッピングを必要とする束のブロックを示している。クリッピングは既知であり、更に説明しない。
【００３１】
束のブロックを用いてボリュームをサンプリングするために必要なループ制御構造は、以下のようになる。
画像の行の全てのブロックに対して{
画像の列の全てのブロックに対して{
光線の束の全てのブロックに対して{
ブロックの行の全てのサンプルに対して{
ブロックの列の全てのサンプルに対して{
ブロックの光線の全てのサンプルに対して{
光線に沿ってサンプリングする
}
}
}
}
}
}
外側の３つのループは、ボリュームの全てのブロックで反復し、内側の３つのループは、ブロックの全てのサンプルで反復する。内側の３つのループは、簡単なサンプリング方式と直接の共通点がある。
［オフセットを備えたスライスの格納］
前述のように、キャッシュの結合性は、ボリュームのスタック方向の列でサンプリングするときに、更なるメモリアクセスを引き起こす可能性がある。この動作を回避するため、方策を行わなければ通常に生じるキャッシュの結合性を回避するように、ボクセルのデータが構成されてもよい。キャッシュの結合性を低減する一般的な原理は、特定の行及び列の位置でのボクセルが連続のスライスに対して同じキャッシュラインにマッピングしないように、ボリュームの連続のスライスを配置することである。これは、各スライスのアドレスにオフセットを導入することで実現可能である。オフセットは、キャッシュラインのサイズ(一般的には32又は64バイト)の倍数になるように選択される。一般的に２つのキャッシュラインで十分である。オフセットは、スライス間のホール(hole)として導入される。この原理を図１４に示す。数字1410で、メモリに連続して格納されるスライスの間にホールが図示されている。典型的な例では、128バイトのホールで、5122の16ビットのスライスアドレスが存在する。この場合、4096のスライスの後にスライス方向にキャッシュの結合性が生じる。
【００３２】
好ましい実施例では、図１５に示すように、スライス参照テーブルが使用される。ボリュームのスライスは、スライス参照テーブルを通じてアクセスされる。スライス参照テーブルは、スライスが配置される実際のアドレスに、スライスへのインデックスをマッピングする。各スライスのデータは、依然としてメモリに連続して格納されるが、連続のスライスは続いて格納される必要がない。有利には、このような知識を必要とするハイレベルのアプリケーションソフトウェアを用いずに、ホールがスライスの間に作られてもよい。このようなメモリ構成の更なる利点は、ボリューム測定データのメモリ配置及びロードが同時に１スライスだけ増加して実行可能であることである。
【００３３】
前述の実施例は、本発明を限定するものではなく、説明するものであり、特許請求の範囲を逸脱することなく、当業者は多数の代替実施例を設計することができる点に留意すべきである。特許請求の範囲において、括弧の間にある如何なる参照符号も、請求項を限定するものとして解釈されるべきではない。“有する”及び“含む”という用語及びその活用の使用は、請求項に記載のもの以外の要素又はステップの存在を除外するものではない。要素の前の先行詞は、そのような要素の複数の存在を除外するものではない。本発明は、複数の明確な要素を有するコンピュータを用いて、及び適切にプログラムされたコンピュータを用いて実装され得る。コンピュータプログラムプロダクトは、光記憶装置のような適切な媒体に格納／配信されてもよく、インターネット又は有線若しくは無線電気通信システムを介して配信されるように、他の形式で配信されてもよい。複数の手段を列挙するシステム／装置／器具の請求項において、これらの手段のうちの複数がハードウェアの同一のアイテムで具現されてもよい。特定の手段が相互に異なる従属項に記載されているという単なる事実は、これらの手段の組み合わせが有利に使用できないことを示しているのではない。
【図面の簡単な説明】
【００３４】
【図１】ボクセルで囲まれたボクセルの立方体である。
【図２】放っている光線とサンプリングである。
【図３】十分に遠くに離れた観測点からの仮想2Dスクリーンへのボリュームの投影である。
【図４】平行投影光線である。
【図５】サンプリングに含まれるボクセルである。
【図６】メモリの3Dセットの構成である。
【図７】キャッシュからの順次格納されたボクセルへのアクセスである。
【図８】本発明によるシステムのブロック図である。
【図９】キャッシュの使用である。
【図１０】キャッシュラインを通じたメモリアクセスである。
【図１１】本発明による光線の束である。
【図１２】束のブロックの周辺のシェルである。
【図１３】束のブロックのクリッピングである。
【図１４】オフセットを備えたスライスの格納である。
【図１５】スライス参照テーブルの使用である。
【図１】
2006518510.tif 000003
【図２】
2006518510.tif 000004
【図３】
2006518510.tif 000005
【図４】
2006518510.tif 000006
【図５】
2006518510.tif 000007
【図６】
2006518510.tif 000008
【図７】
2006518510.tif 000009
【図８】
2006518510.tif 000010
【図９】
2006518510.tif 000011
【図１０】
2006518510.tif 000012
【図１１】
2006518510.tif 000013
【図１２】
2006518510.tif 000014
【図１２】
2006518510.tif 000015
【図１３】
2006518510.tif 000016
【図１４】
2006518510.tif 000017
【図１５】
2006518510.tif 000018
【国際調査報告】
2006518510.tif 000019
2006518510.tif 000020