(57)【要約】本発明は三次元画像を記憶する方法に関する。三次元画像は、画素データのアレイで表される二次元ビデオデータ副集合の積層を有する。画素データの各々のアレイは、メモリのキャッシュラインに多くとも等しい幅を有する画素データの複数の重複した且つ隣接する縦方向のストライプに区分される。画素データの複数の行を有する各々のストライプを記憶するとき、上部の行が最初に記憶され、ストライプの各々の後続する行の最初の画素データが、先行する行の最後の画素データが記憶されるメモリ位置の後にくるメモリ位置に記憶される。
2008510213.tif 000002
【特許請求の範囲】
【請求項１】
三次元オブジェクトに関して情報データサンプルの三次元アレイをメモリに記憶する方法であって：
重複し且つ隣接する縦方向の複数のストライプに前記の情報データサンプルの三次元アレイを区分する段階； 
最上部左のストライプを最初に記憶し、左に隣接するストライプを記憶した後に各々のストライプを記憶する段階；及び
複数の情報データサンプルの行を有する各々のストライプを記憶するとき、上部の行を最初に記憶し、先行する行の最後に記憶されるサンプルが記憶されたメモリ位置に隣接するメモリ位置に各々の後続行の最初のサンプルを記憶する段階；
を有する方法であり、
ストライプは、前記メモリに関連するキャッシュラインに多くとも等しい幅を有する；
ことを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、全ての縦方向の前記ストライプは同じ幅を有する、ことを特徴とする方法。
【請求項３】
請求項１に記載の方法であって、前記ストライプは前記の情報データのアレイと同じ高さを有する、ことを特徴とする方法。
【請求項４】
請求項１に記載の方法であって、各々のサンプル及び下のサンプルは一定のアドレスオフセットを有する前記メモリに記憶される、ことを特徴とする方法。
【請求項５】
請求項１に記載の方法であって、前記ストライプの厚さは１つの情報データサンプルであり、隣接ストライプの並置は前記三次元アレイの二次元副集合を構成する、ことを特徴とする方法。
【請求項６】
請求項５に記載の方法であって、前記二次元副集合の第１副集合における各々の第１データサンプル、及びそれぞれの副集合において同じ位置を有する二次元副集合の第２副集合における各々の第２データサンプルは、一定のアドレスオフセットを有するメモリに記憶される、ことを特徴とする方法。
【請求項７】
請求項１に記載の方法であって、前記ストライプの厚さは少なくとも２つの情報データサンプルである、ことを特徴とする方法。
【請求項８】
請求項１に記載の方法であって、前記情報データサンプルは三次元ピクチャのボクセルに関連する、ことを特徴とする方法。
【請求項９】
メインメモリと既知のキャッシュラインを有する第１レベルキャッシュとを有するメモリ構成；及び
情報データサンプルの三次元アレイの前記メモリ構成への記憶を制御するメモリ制御ユニット；
を有するメモリシステムであって、
前記メモリ制御ユニットは、前記キャッシュラインに少なくとも等しい幅を有するサンプルの重複する且つ隣接する複数の縦方向ストライプに前記の情報データサンプルのアレイを区分し、前記メモリ制御ユニットは、最初に最上部左のストライプを前記メインメモリに記憶し、左に隣接するストライプの後に各々のストライプを記憶し；そして
サンプルの複数の行を有する各々のストライプを記憶するときに、前記メモリ制御ユニットは、最初に上部の行を記憶し、先行する行の最後に記憶されたサンプルが記憶されるメモリ位置に隣接するメモリ位置に各々の後続の行の、最初に記憶されるサンプルを記憶する；
ことを特徴とする方法。
【請求項１０】
三次元オブジェクトに関して情報データサンプルの三次元アレイをメモリに記憶するための命令を実行するコンピュータを有する記録担体であって、記憶段階は：
複数の重複し且つ隣接する縦方向ストライプに前記の情報データサンプルのアレイを区群する副段階；
最上部左のストライプを最初に記憶し、左に隣接するストライプを記憶した後に各々のストライプを記憶する副段階；及び
情報データサンプルの複数の行を有する各々のストライプを記憶するとき、最初に上部の行を記憶し、そして、先行する行の最後に記憶されるサンプルが記憶されたメモリ位置に隣接するメモリ位置に各々の後続の行の最初に記憶されるサンプルを記憶する副段階；
を有し、
ストライプは、前記メモリに関連するキャッシュラインに多くとも等しい幅を有する；
ことを特徴とする記録担体。  
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元（３Ｄ）画像の記憶及びメモリ帯域幅の最適化に関する。
【背景技術】
【０００２】
映像及び表示技術は、診断を行う上で医師を支援するように、今日、医師が利用することが可能である新しいツールに含まれている。医療用画像の性質及びそれらの画像が寄与する目的により、医療分野の特定の制限に対して現在の映像技術を適合させるためには、研究が必要である。医療関係者は、ビデオゲーム又は映画編集のような他の映像アプリケーションに共通であるものと幾らか異なる順序でビデオ技術が提供する特徴を、位置付ける。特に、医療チームにとって最も重要である特徴は、対話性、精度、現実との一貫性及び比率である。ビデオデータは、それ故、新規事項として扱われ、概念化される必要がある。
【０００３】
ゲーミングと共に、医療用アプリケーションは、確かに、三次元画像が最も成功した２つの重要な領域である。しかしながら、三次元画像に伴う主な欠点は、処理器が短時間で処理するデータ集合の規模にある。大きい三次元データ集合を処理することは、適切なデータ可視化に対するまさに障害であり、しばしば、データアクセス、データ転送及びデータ処理を最適化するための解決方法が見出されない場合に、進展を遅延させて、受け入れられない水準に留まってしまう。現在の中央演算処理装置（ＣＰＵ）は、キャッシュ階層を介してメインメモリに記憶されているデータにアクセスする。一般に、２つのキャッシュレベルが存在し、第１レベルのキャッシュは、しばしば、第２レベルのキャッシュよりかなり小さい。データアクセスは、第１レベルキャッシュについては速く、メインメモリについては相対的に遅い。データ転送は、通常、キャッシュラインを介して行われ、そのデータ転送は、２つのメモリエンティティ又はキャッシュエンティティ間で一度転送されたデータ量である。最終世代の処理器は、例えば、最大１２８バイトまでのキャッシュラインを有し、この数は尚も増加している。キャッシュに基づくメモリ組織は、キャッシュラインの幾つかのデータのみを用いるが、大多数のキャッシュラインに影響を与えるアルゴリズムのランタイム中の性能の重大な劣化に繋がる可能性がある。幾つかのアルゴリズムは、一般に、このアーキテクチャのために遅い一方、他のアルゴリズムの性能は、区別可能なパラメータ範囲のために最大１０分の１まで分解される。それ故、転送されるデータの量を減少させる解決方法を求める必要が非常にある。
【０００４】
デジタル画像処理においては、第１解決方法は、データ転送を最適化するように検討されている。米国特許第６，０２８，６１２号明細書においては、メモリからピクチャのアレイ部分を取り出すときに、メモリ帯域幅を減少させるメモリアーキテクチャについて開示されていて、その文献の援用により本発明の説明の一部を代替する。メモリは、行列を有するピクチャを記憶するために複数のワードに副分割される。ピクチャは、所定数の列を各々有する２つ又はそれ以上のストライプに区分される。１つのストライプの１つの行におけるバイト数は、１つのワードにおけるストライプの１つの行にデータを記憶するために、１つのワードにおけるバイト数に等しい。プログレッシブビデオシーケンス又は画像の場合に、メモリはフレーム構造に組織化される。フレームが組織化されたメモリに記憶されるフレームピクチャ又はフィールドが組織化されたメモリに記憶されるフィールドピクチャについて、ストライプの１つの最初の行におけるデータは第１ワードで記憶される。ストライプの各々の後続の行におけるデータは、直接先行する行のデータを記憶するワードに隣接する及び後続するワードアドレスを有するワードで記憶される。上記特許文献で提供している解決方法は、データ処理中の過剰な転送キャッシュライン数の問題を部分的に解決しているのみである。例えば、ストライプ端部の画素の処理は、幾つかの別個のキャッシュラインの取り出しを必要とし、それ故、データ転送を過度に長くする。更に、構造を考慮するために、提案されている実施例には、ワード長に対してストライプの幅を制限するという主な短所がある。
【特許文献１】米国特許第６，０２８，６１２号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００５】
最終的に処理される及び／又は表示されるデータの三次元アレイの記憶を最適化する解決方法を開発する要請が当該産業において存在する。
【課題を解決するための手段】
【０００６】
このために、三次元オブジェクトに関して、情報データサンプルの三次元アレイをメモリに記憶するための方法が提供される。第１段階においては、情報データサンプルのアレイは、複数の重複する且つ隣接する縦方向のストライプに区分される。それらのストライプは、左上のストライプから開始して、メモリに次々と記憶される。左上のストライプが最初に記憶され、各々の後続のストライプが、それらの左側のストライプが記憶された後に記憶される。各々の個々のストライプは複数のサンプルの行を有し、次のように記憶される。即ち、上部の行が先ず、記憶され、上から下に次々と、行が記憶される。即ち、ストライプ（最初のストライプは省く）の各々の行の最初の情報データサンプルは、処理される行の最後の情報データサンプルが記憶されたメモリ位置の後にくるメモリ位置に記憶される。
【０００７】
本発明は、三次元オブジェクトに関連する情報データサンプルのアレイをストライプに区分し、左上角のサンプルから開始して、連続的に次々と、ストライプを記憶することを提供している。本発明の特徴は、ストライプが重複していることである。そのような冗長性は、データ呼び出し中に必要なデータセットの数を減少することが可能である。データがキャッシュラインにおいてアクセスされる実施形態においては、その冗長性は、送信キャッシュラインの総数を減少させることが可能である。例えば、表示アルゴリズムは、しばしば、特定サンプルの周囲にサンプルを必要とし、送信キャッシュライン数は、その周囲のサンプルを別個のキャッシュラインにおいてのみ求めることができる場合に、非常に増加する可能性がある。本発明が提供する方法で処理サンプルの周囲のサンプルについての情報を繰り返すことは、それ故、減少したキャッシュライン数において処理のために必要なデータを集めることが可能である。本発明の１つ又はそれ以上の実施形態の有利点は、メモリの帯域幅を減少させ、それにより、全体的なアルゴリズムの性能を高速化することである。医療分野においては、情報データサンプルは、三次元オブジェクトのボクセルに関連する測定値又は放射線値であることが可能である。
【０００８】
本発明の１つ又はそれ以上の実施形態においては、ストライプは同じ幅を有し、それらのストライプは、メモリに関連するキャッシュラインの一部であることが可能である。メモリが第１キャッシュに結合していて、第２又は第３キャッシュレベルに結合することが可能である実施形態においては、ストライプの幅は、最大で、少なくとも１つ又は２つのキャッシュラインである。それ故、処理されるボクセルの周りのボクセルに関連する情報データサンプルが、処理されるボクセルと同じキャッシュライン内にある可能性が大きい。上記の補間アルゴリズムの実施例においては、所定のサンプルについての補間値の計算は、しばしば、隣接ボクセルに関連する情報データサンプルに基づいている。ストライプの幅がキャッシュラインより小さい場合、隣接ボクセルに関連するサンプルが同じキャッシュライン内にある可能性は大きい。
【０００９】
本発明の上記の及び他の特徴については、以下、説明する実施形態を参照して明らかになり、理解することができるであろう。
【００１０】
本発明について、以下、例示として添付図を参照して、詳述する。
【発明を実施するための最良の形態】
【００１１】
本発明は、視覚化及び処理を最適化する三次元画像を記憶する方法に関する。本発明は、特に、医療分野において有利であるが、本発明の特徴は、何れの種類の映像アプリケーションに適用されることができるように、十分に一般的である。本発明は、三次元画像が二次元スライスの積層として表されるという概念に基づいている。各々の二次元スライスは従来の二次元画像のように扱われ、基本的には、画素データの行列のアレイを有する。画素データは、映像アプリケーション及びデザイナーの選択に応じて、色値、輝度又はクロミナンス値、不透明度又は反射値であることが可能である。各々の二次元画像は、それ故、点の二次元アレイによりグラフィック表示され、各々の点は画素を表す。
【００１２】
図１は、三次元画像１００の二次元スライス１０２、１０４及び１０６を示している。二次元画像１０２は、画素データの６つの行を有する四角形状アレイで描かれて示されている。便宜上、画素データは、左上の角の画素データから開始して、行毎に連続してメモリに記憶される。この実施形態の不利点は、ある画素、その上に隣接する画素及び下に隣接する画素の記憶における不連続性である。実際には、特に縦方向における隣接画素は、間違いなく区別可能であるように及び不連続なメモリ位置に記憶され、異なるキャッシュラインは、それらの画素が検索される必要があるときに要請される。
【００１３】
図２及び図３は本発明の幾つかの基本的な特徴について示している。ピクチャ１０２は、Ｘ方向及びＹ方向において等間隔で位置付けられた画素のアレイ１１４の形で表されている。この例示としての実施形態においては、画素のアレイ１１４は、有限数の縦方向の重複ストライプに区分化される。隣接する第１ストライプ１１６及び第２ストライプ１１８が示されている。図１に示す実施形態と対照的に、画素がストライプ毎にメモリに記憶され、そのことは、所定のストライプの画素全てがメモリ領域に共に記憶されることを意味している。ストライプ１１６は、先ず、左上の角の画素から開始して、記憶され、隣接するストライプ１１８がその後に記憶される。ストライプ１１８の左上の角の画素は、ストライプ１１６の右下の画素（最後に記憶されたストライプ１１６の画素）が記憶されたところに隣接するメモリ位置に記憶されることが可能である。
【００１４】
ストライプ１１６は、次のように記憶される。ストライプ１１６の左上角の画素が、先ず、記憶され、続いて、ストライプ１１６を通して右方向及び下方向に連続して記憶される。ストライプ１１８が、同様に記憶される。この実施形態においては、ストライプ１１６及び１１８は、メモリのキャッシュラインの一部である同じ幅を有する。セグメント１５０及び１５２はメモリに記憶されているキャッシュラインである。
【００１５】
更に、図２に示すように、ストライプ１１６及び１１８は、２つの画素の重複１２０を有し、そのことは、領域１２０における画素データはメモリにおいて冗長であることを意味している。重複画素数の選択は任意であり、実施デザイン及びメモリロードは、最適に適合するように選択されることが可能である。そのことはオーバーヘッドをもたらすが、重複１２０におけるデータは、周囲の画素に関する情報を必要とするアルゴリズムのために有利に用いられる。実際には、もたらされたデータ冗長性は、隣接画素に関する情報が補間結果を計算するために必要であるため、例えば、線形補間及び立方体補間の実行を容易にする。このことについては、図４を参照して更に詳細に説明する。
【００１６】
図４は、ストライプ１１６の第１行の最後の数画素と、ストライプ１１８の第１行の最初の数画素とを示している。米国特許第６，０２８，６１２号明細書に関して上記で説明したように、画素データが非重複ストライプにおいて記憶されている場合、端部における画素の補間は隣接ストライプへのアクセスを必要とし、それ故、異なるキャッシュライン、メモリ領域又は異なるメモリの実体へのアクセスを必要とする。そのような実施は、処理能力を過度に抑制する。ストライプが重複する本発明においては、付加限定が、重複においてどの画素が処理されるべきかに関するアルゴリズムを行うことを可能にする。この実施形態においては、補間アルゴリズムは、重複部分内に位置しているストライプ画素のみを処理するように制限され、そのアルゴリズムは、許容された重複部分の外側に位置する画素を処理せず、それ故、補間しない。例えば、図４を参照するに、ストライプ１１６を処理しているとき、その補間アルゴリズムは、画素１１２についての画素値のみを補間するように設定され、そのアルゴリズムは、画素１２４についての何れの補間値を計算しない。補間アルゴリズムが最近接画素の画素値のみを必要とすることを前提とする場合、そのアルゴリズムは、何れの付加キャッシュラインを必要とすることなく、画素１２２についての結果を容易に計算することができる。同様に、ストライプ１１８を処理しているとき、その補間アルゴリズムは、画素１２４のみの補間結果を計算するように設定されている。各々のストライプ１１６及び１１８の端部画素は、ストライプの処理中には無視され、情報が冗長であるために、同じ端部画素は、非端部画素として隣接ストライプ中に存在し、それ故、それにも拘らず、結局処理されることができる。この実施形態には、データリンクに負担を負わせ、帯域幅を消費するキャッシュラインについての不要な呼び出しを回避する。上記実施形態は、単に例示としての与えられていて、アルゴリズム処理を満足するように、何れの重複の大きさが選択されることが可能である。同様に、ストライプ１１６及び１１８の幅は、ランタイム中のキャッシュラインアクセス数を最適化するように選択される。ストライプ１１６及び１１８は、必要に応じて、異なる幅を有することが可能である。
【００１７】
図５は、メモリアドレスが有効に割り当てられた、本発明の例示としての実施形態を示している。図５は、三次元画像１００を構成する、二次元スライス１０２の左上角の画素１３０及び隣接画素１３２乃至１３６と、次の二次元スライス１０４の左上角の画素１３８とを示している。図５はまた、メモリ１４の内部構成を表すブロック単位を示している。メモリ１４０は、左の列におけるメモリアドレスと右の列におけるデータ画素を有する２列テーブルとして表されている。図に示しているように、画素１３０に関連するデータはメモリアドレス０に、画素１３２に関連するデータはメモリアドレス１に、画素１３４に関連するデータはメモリアドレスＸ０に、画素１３６に関連するデータはメモリアドレス２Ｘ０に、そして画素１３８に関連するデータはメモリアドレスＹ０に記憶される。上記のように、同じ行に位置している画素は連続して目盛り１４０に記憶され、各々の行の最初の画素は、前の行の最後の画素の次にメモリに記憶される。この実施形態においては、一定のアドレスオフセット、即ち、Ｘ０が、二次元スライスにおいて、画素とその画素の下の画素との間に導入される。画素１３０、１３４及び１３６は、それ故、アドレス０、Ｘ０及び２Ｘ０それぞれにおいてメモリに記憶される。画素１３２の下に位置している画素１４２はまた、アドレス１＋Ｘ０においてメモリ１４０に記憶される。同様のアドレスオフセットＹ０が、スライス１０２の画素とスライス１０４の画素との間に導入される。実際には、画素１３０及び１３８は、それぞれのアドレス０及びＹ０においてメモリ１４０に記憶される。導入される一定のオフセットは、隣接画素に関する画素データの迅速な検索を可能にする。
【００１８】
提案しているストライプに基づく記憶方法は、ストライプの幅に対して条件を課すが、ストライプンの厚さ及び高さに可能性を残している。２つの残りの寸法の選択におけるこの自由度は、処理中の高いフレキシビリティ及び仮想ブロック構築を可能にする。図６においては、画像１０２は体の器官の輪郭１４２を有する。輪郭１４２は、器官の外側表面又は外殻の画像１０２の面の断面である。輪郭１４２を形成する画素データを処理するように、全体の輪郭１４２を有する二次元仮想ブロック１４４、１４６及び１４８を計算することが可能である。仮想ブロック１４４、１４６、１４８のＸ方向の寸法はストライプ１１６、１１８の幅のように等しく、Ｙ方向の寸法はデザイナーの選択に任されている。ブロックのＹ方向の寸法は、輪郭及びストライプの共通部分を有するストライプの部分をカバーするように選択されることが可能である。図６に示すように、結果として仮想ブロック１４４乃至１４８が得られる。
【００１９】
三次元仮想ブロックはまた、体の器官の三次元外殻をカバーするように、構築されることが可能である。このために、Ｚ方向の厚さがブロック１４４、１４６及び１４８について計算される。固定された大きさのブロックがメモリに記憶されている、従来のブロックに基づく記憶の実施形態と比べて、本発明は高い自由度を可能にし、処理を高速化している。そのような実施形態は、体の表面又は外殻が処理されて可視化される必要がある医療用アプリケーションに対して、特に適合することができる。
【００２０】
更に、開示されている記憶アーキテクチャはキャッシュラインに基づいているが、他の記憶アーキテクチャがまた、本発明の実施に対して適合されることができる。また、そのことは、キャッシュライン又は他のメモリ転送の実体より広いストライプの幅を修正するメモリアーキテクチャを考慮して、非常に有利である。
【００２１】
本発明においては画素の三次元アレイを二次元アレイへのスライシングは単に例示としての実施形態として与えられ、本発明は、物理データ、放射線データ、ボクセルに関する測定結果を表す情報データサンプルの三次元アレイに先ず、方向付けられることに留意する必要がある。明らかに、ストライプは、１つ又はそれ以上の情報データサンプルの厚さを有することが可能である。
【００２２】
上記は、本発明の原理について、単に例示しているものである。したがって、上記で明示的に記載していない又は図示していないが、本発明の原理を実施し、それ故、同時提出の特許請求の範囲の請求項の範囲内にあり、主旨に沿った種々の構成を考案することができることが理解されるであろう。
【００２３】
それらの請求項を解釈するに、次のことが理解される必要がある。
ａ）用語“を有する”は、所定の請求項に列挙されている要素又は段階以外の要素又は段階の存在を排除するものではない。
ｂ）要素の単数表現はその要素の複数の存在を排除するものではない。
ｃ）幾つかの“手段”は、構成又は機能を実施する同じアイテム、ハードウェア、ソフトウェアにより表されルことが可能である。
ｄ）開示されている要素の各々は、ハードウェア部分（例えば、個別の及び統合された電気回路を有する）、ソフトウェア部分（例えば、コンピュータプログラミング）及び何れのそれらの組み合わせを有することが可能である。
ｅ）ハードウェア部分はアナログ部分、デジタル部分又はそれら両方を有することが可能である。
ｆ）特に記載されていない場合、開示されている装置又は部分の何れは共に組み合わされる、又は更なる部分に分割されることが可能である。
ｇ）特に記載されていない場合、段階の特定のシーケンスは必要とされるように意図されていない。
【図面の簡単な説明】
【００２４】
【図１】三次元画像を記憶するための従来の方法を示す図である。
【図２】本発明の方法を示す図である。
【図３】本発明の方法を示す図である。
【図４】本発明にしたがった隣接ストライプ間の重複に属す画素を示す図である。
【図５】本発明のメモリを示す図である。
【図６】本発明のピクチャを示す図である。
【図１】
2008510213.tif 000003
【図２】
2008510213.tif 000004
【図３】
2008510213.tif 000005
【図４】
2008510213.tif 000006
【図５】
2008510213.tif 000007
【図６】
2008510213.tif 000008
【国際調査報告】
2008510213.tif 000009
2008510213.tif 000010
2008510213.tif 000011