(57)【要約】本発明によれば、３次元データベースの関心のある領域を通じて中心線を決定する方法を提供する（図１）。この方法は、関心のある領域の境界の識別及び関心のある領域の終了ポイントの識別を有する。境界内のこれらポイントに対して、境界に対するポイントの近傍の関数であるペナルティ値が決定される。中心線は、最小のペナルティ付き距離を有する終了ポイントを接続する経路によって識別され、ペナルティ付きの距離は、実際に蓄積された経路長及び経路に沿ったポイントに関連したペナルティを反映する（図９Ａ）。中心線から、完全な組織の分岐を、分岐の終了ポイントを決定するとともに各終了ポイント、中心線又は他の交差分岐からの最小のペナルティ付き距離を見つけることによって確立する（図９Ｂ）。
2004518186.tif 000002
【特許請求の範囲】
【請求項１】
３次元画像データセットの関心のある領域を通じた中心線を決定する方法であって、
関心のある領域の境界を識別し、
関心のある領域の終了ポイントを識別し、
前記境界内のこれらポイントに対して、境界に対する前記ポイントの近傍の関数であるペナルティ値を決定し、
最小のペナルティ付き距離を有する終了ポイントを接続する経路を決定し、そのペナルティ付き距離が、実際に蓄積された経路長及び前記経路に沿ったポイントに関連したペナルティを反映することを特徴とする方法。
【請求項２】
前記関心のある領域のポイントの各々における境界領域からの距離を演算することを特徴とする請求項１記載の方法。
【請求項３】
前記オブジェクトの中心線付近のポイントを識別し、前記ペナルティ値を決定するステップ及び前記中心線付近のポイント上のみの経路を決定するステップを行うことを特徴とする請求項２記載の方法。
【請求項４】
前記中心線付近のポイントを識別する動作が、
前記関心のある領域の各ポイントに対する勾配領域を決定し、
一様でない勾配を有するポイントの領域を識別し、
一様でない勾配を有する領域を接続することを特徴とする請求項３記載の方法。
【請求項５】
前記終了ポイントを接続する経路を円滑化することを特徴とする請求項１記載の方法。
【請求項６】
終了ポイントの少なくとも一つを、前記オブジェクトの既に知られていることに基づいて選択することを特徴とする請求項１記載の方法。
【請求項７】
前記中心線から分岐の終了ポイントを識別し、
識別された終了ポイントの各々に対して、最小のペナルティ付き距離を有する他の分岐に対する終了ポイントを接続する分岐経路を決定し、そのペナルティ付き距離が、実際に蓄積された経路長及び前記分岐経路に沿ったポイントに関連したペナルティを反映することを特徴とする請求項１記載の方法。
【請求項８】
前記分岐経路のポイントの各々に対する境界領域からの距離を演算することを特徴とする請求項７記載の方法。
【請求項９】
各分岐に対して、前記分岐の中心線付近のポイントを識別し、ペナルティ地を決定するステップ及び前記中心線付近のポイント上のみの経路を決定するステップを行うことを特徴とする請求項７記載の方法。
【請求項１０】
前記分岐の中心線付近のポイントを識別する動作が、
前記関心のある領域の各ポイントに対する勾配領域を決定し、
一様でない勾配を有するポイントの領域を識別し、
一様でない勾配を有する領域を接続することを特徴とする請求項９記載の方法。
【請求項１１】
各分岐の中心線を円滑化することを特徴とする請求項１０記載の方法。
【請求項１２】
仮想的なオブジェクトを通じる中心線を発生する方法であって、
その仮想的なオブジェクトの３次元画像データセットを取得し、その画像データセットが、複数のボクセルを具え、
前記３次元画像データセットの関心のある領域の境界を識別し、
その関心のある領域のボクセルの各々に対する境界領域からの距離を演算し、
前記関心のある領域のボクセルの各々に対する勾配ボクセル領域を決定し、
一様でない勾配を有するボクセルの領域を識別し、
その一様でない勾配の領域を接続し、
接続された領域からルートボクセルを識別し、
接続されたボクセルから、前記ルートボクセルからのペナルティ付き距離を計算し、
前記ルートボクセルから、そのルートボクセルに対して最も遠いボクセルまでの最小のペナルティ付き距離を決定することを特徴とする方法。
【請求項１３】
前記最小のペナルティ付き距離によって規定された経路を円滑化することを特徴とする請求項１２記載の方法。
【請求項１４】
前記分岐の終了ポイントを決定し、
分岐終了ポイントの各々に対して、最小のペナルティ付き距離を有する他の分岐に対する終了ポイントを接続する分岐経路を決定し、そのペナルティ付き距離が、実際に蓄積された経路長及び前記分岐経路に沿ったポイントに関連したペナルティを反映することを特徴とする請求項１２記載の方法。
【請求項１５】
仮想的なオブジェクトのナビゲーションを行う方法であって、
関心のある領域の境界を識別し、
境界内のポイントに対して、境界に対するポイントの近傍に比例するペナルティ値を決定し、
現在のカメラ位置のペナルティ値に従って仮想的なカメラの速度及び方向のうちの少なくとも一方を制御することを特徴とする方法。
【請求項１６】
ペナルティ領域を、境界領域からの距離とすることを特徴とする請求項１５記載の方法。
【請求項１７】
仮想的なオブジェクトの中心線に沿ってナビゲーションを行う方法であって、
前記中心線に沿った最初のナビゲーション方向を決定し、
ナビゲーションを前記最初のナビゲーション方向に沿って行う際に、前記中心線に第１の印を付け、
ナビゲーションを前記最初のナビゲーション方向とほぼ反対方向に沿って行う際に、前記中心線に第２の印をつけることを特徴とする方法。
【請求項１８】
前記第１の印を、第１のカラーとし、前記第２の印を、前記第１のカラーと異なる第２のカラーとしたことを特徴とする請求項１７記載の方法。
【請求項１９】
前記最初のナビゲーション方向を、前記中心線の約±７０°の範囲内の方向として規定することを特徴とする請求項１７記載の方法。
【請求項２０】
前記オブジェクトを結腸とし、前記最初のナビゲーション方向を、直腸から盲腸までとすることを特徴とする請求項１９記載の方法。
【請求項２１】
前記オブジェクトを結腸とし、前記最初のナビゲーション方向を、盲腸から結腸までとすることを特徴とする請求項１９記載の方法。
【発明の詳細な説明】
【０００１】
この出願の課題は、国立保健研究所の契約番号ＣＡ７９１８０及び海軍調査研究所の米国オフィスの譲渡番号Ｎ０００１４９７１０４０２によって一部資金が提供されている。これらの譲与から、米国政府は、本発明について所定の権利を有する。
【０００２】
発明の分野
本発明は、一般にコンピュータに基づく３次元視覚化に関し、更に詳しくは構造発生を含む仮想ナビゲーションの向上した方法に関する。
【０００３】
発明の背景
複数のコンピュータに基づく視覚化システムにおいて、観察されるオブジェクトを通じた構造又は中心線を規定できるようにすることが所望されている。そのような構造は、仮想的な結腸検査のような仮想的なナビゲーションに対する基準経路を提供する。同様に、大動脈のような他の器官を通じた正確な長さ測定及びナビゲーションもオブジェクト構造を必要とする。当然、正確な中心線又はツリーを規定する必要は、医療的なイメージングに制限されない。仮想エンジニアリング及びアーキテクチャのような他の分野も、ツリー状オブジェクトの構造を規定するとともに種々の視覚化アプリケーションの線形オブジェクトの中心線を発生する正確な方法によって有益なものとなる。
【０００４】
視覚化されたオブジェクトに対する中心線を発生する種々の技術が知られている。例えば、結腸のような器官の仮想的な検査において、中心線は、ＣＴ，ＭＲＩ又は超音波データのような画像データを再び観察する間に放射線技師によって手動でマークされる。しかしながら、この技術に伴う高レベルの手動が介在するために、それは高価なものとなり、一般的には好適でない。
【０００５】
中心線を自動的に発生する方法は、位相ティニング（ｔｏｐｏｌｏｇｉｃａｌ ｔｈｉｎｎｉｎｇ）又は「オニオンピーリング」（ｏｎｉｏｎ ｐｅｅｌｉｎｇ）と称される。この技術の複数の既知の変形があるのに対して、関心のある領域からの容量単位（ボクセル）は、残りのものが１個のボクセルのように予め設定された厚さの接続されたラインとなるまで、層間で境界から除去される。この技術が一般に結腸のようなオブジェクトの中心線の決定の際に有効であることがわかったのに対して、それは、演算的にコストが高くなるという不都合を有する。さらに、所定の幾何学的構造によって、位相ティニングによって決定される中心線は、常に直感的に消耗される中心線ではない。
【０００６】
仮想的なオブジェクトを通じた中心線を発生する他の技術は、Ｄｉｊｋｓｔｒａアルゴリズムのようなオブジェクトを通じた最短経路の決定を試みるアルゴリズムの使用を有し、それは、参照することによってここに完全に組み込んだ論文”Ａ Ｎｏｔｅ ｏｎ Ｔｗｏ Ｐｒｏｂｌｅｍｓ ｉｎ Ｃｏｎｎｅｘｉｏｎ ｗｉｔｈ Ｇｒａｐｈｓ”， Ｄｉｊｋｓｔｒａ， Ｎｕｍｅｒｉｓｈｅ Ｍａｔｅｍｅｔｉｃ， ｖｏｌ． １， ｐｐ ２６９−２７１， １９５９に開示されている。Ｄｉｊｋｓｔｒａアルゴリズムは、負でない重みを有する重み付けされたグラフの全体的な最小重み付け経路を見つける。このアルゴリズムは、一般に２段階を有する。第１段階において、ソース領域（ＤＳＦ）からの距離が、単一のソースから全てのグラフ頂点までの最短距離を有するこれら頂点にラベリングすることによって形成される。第２段階において、最も遠いノードからソースノードに戻って追跡することによって最短経路が決定される。したがって、このアルゴリズムの使用は、画像データからグラフ形態への写像を必要とする。そのような写像の一例を図８ａに示す。Ｄｉｊｋｓｔｒａアルゴリズムは、オブジェクトに鋭いターンが生じる場合に不都合を有する。そのような場合、最短経路を探求するアルゴリズムは、「コーナの近くを通る」傾向にあり、中心線が中心から境界に向かってシフトする。
【０００７】
仮想的なオブジェクトの組織は、複数の所望の特性の関係において規定される。ここで使用されるように、組織を、ツリー形状にするとともに分岐を通じた単一のボクセル経路から構成する必要がある。したがって、組織は、２次元的な多岐管ではなく３次元スペースの１次元曲線を表す。組織は、関心のある領域の境界内に存在したままである必要があり、好適には、形状の「中心」に存在したままである必要がある。任意の形態のオブジェクトに対して、中心の概念は、関心のある領域の境界の全てからの距離の最大化と中心線が曲がりくねった経路をとる程度の最小化との間のバランスを取ることを要求する。このようにバランスをとると、組織を取得する際の最短経路の形態又は最短経路の統合を行うことが所望される。
【０００８】
オブジェクトの組織を発生する複数の技術が知られているが、既知の技術の各々は、固有の不都合を有する。したがって、仮想的なオブジェクト内の中心線、組織及び／又はナビゲーション経路を発生する向上した技術が必要とされる。
中心線は、仮想的なオブジェクトを通じてナビゲーションする主要経路としてしばしば用いられる。例えば、仮想的な結腸検査の場合、ユーザは、一般に結腸の中心線のいずれかの方向に沿ってナビゲーションするのを許容され、関心のある領域を調べるために中心線から外れてナビゲーションを行うことができる。したがって、仮想的な結腸検査によって、観察者は、通常の光学的な結腸検査の場合に比べて結腸の管腔内面を更に柔軟に観察することができる。このことは、仮想現実及びコンピュータグラフィックスによって仮想的なカメラが任意の視点から任意の観察方向で観察を行うことができるという事実によって達成され、同時に、（光学的なカメラが移動が制約された状態でプローブの端部に配置されているために、）光学的な結腸検査が、結腸に沿った１方向の経路に制限される。しかしながら、仮想的な検査によって生じる柔軟性によって、新たな試みが行われている。特に、同一方向の配置の困難さが変化する。結腸は、非常に曲がりくねっており、その結果、３次元の結腸に沿って同一方向を維持する際には、ユーザは方向を見失う。このようなおそれは、ユーザが中心線から外れて向きを変えるとともに結腸壁に近接する構造を検査するときに特に顕著になる。しばしば、中心線から戻る際には、ユーザは、以前に来た方向に戻るおそれがある。観察者が逆方向から来るので、通常、逆方向の脱出が容易でない。したがって、仮想環境で達成しうる所望の柔軟性を減少することなく、仮想的なオブジェクトを通じてナビゲーションする間に観察者が方向を見失うおそれを減少する方法を提供することが好ましい。
【０００９】
発明の要約
本発明の目的は、仮想的なオブジェクトの中心線及び適応しうる組織を発生する向上した方法を提供する。
【００１０】
本発明によれば、３次元画像データセットの関心のある領域を通じて中心線を決定する方法を提供する。本発明は、関心のある領域の境界を識別し、関心のある領域の終了ポイントを識別する。境界内のこれらポイントに対して、境界に対するポイントの近傍に比例するペナルティ値が決定される。中心線は、最小のペナルティ付き距離を有する終了ポイントを接続する最長のユークリッド経路によって識別され、ペナルティ付きの距離は、実際に蓄積された経路長と、経路に沿ったポイントに関連したペナルティとを反映する。
【００１１】
方法は、好適には、最初にオブジェクトの中心線付近のポイントを識別するステップを有する。この場合、ペナルティ値を決定するステップ及び既に説明した経路を決定するステップを、中心線付近のポイント上でのみ実行することができる。これによって、処理すべきデータセットが減少し、処理コスト及び速度が向上する。
【００１２】
中心線付近のポイントを識別する動作を、関心のある領域のポイントの各々に対する境界領域からの距離（ＤＢＦ）を演算し、関心のある領域の各ポイントに対する勾配領域を決定し、一様でない勾配を有するポイントの領域を識別し、一様でない勾配を有する領域を接続することによって行う。
【００１３】
単一の中心線に加えて、分岐したオブジェクトの完全な組織を決定する方法に拡張するのも望ましい。これを、中心線から延在する分岐の終了ポイントを識別し、識別された終了ポイントの各々に対して、最小のペナルティ付き距離を有する他の分岐に終了ポイントを接続する分岐経路を決定することによって行う。また、各分岐からのペナルティ付きの距離は、分岐の実際に蓄積された経路長と、分岐経路に沿ったポイントに関連したペナルティとを反映する。
【００１４】
図面中、特に説明しない限り、同一の参照番号及び符号を、図示した実施の形態の同様な形態、素子、構成要素又は部分を示すのに使用する。さらに、本発明を、図面を参照して詳細に説明する間、本発明は、図示した実施の形態に関連して実施される。添付した特許請求の範囲によって規定されたような本発明の範囲及びその精神から逸脱することなく、記載された実施の形態を変更及び変形することができる。
【００１５】
発明を実施するための最良の形態
本発明は、管腔の中心線又は更に複雑なオブジェクトの組織を自動的に発生する向上した演算的に有効な方法を提供する。この方法は、Ｄｉｊｋｓｔｒａの最短経路のような既知の最短経路アルゴリズムを拡大するペナルティ付き距離の領域（ｐｅｎａｌｉｚｅｄ ｄｉｓｔａｎｃｅ ｆｉｅｌｄｓ）の概念を用いる。言及した例は、一般に、仮想結腸検査のような医療検査に関連するが、仮想ナビゲーションに基づくコンピュータの任意のアプリケーションに適用可能である。
【００１６】
既に説明したように、既知のＤｉｊｋｓｔｒａの最短経路のアルゴリズムの問題は、オブジェクトを通じた経路が急に向きを変えるときに明らかになる。そのような場合、一部を変更又は変形しない場合、Ｄｉｊｋｓｔｒａの最短経路は、コーナに接するとともに、オブジェクトの中心から逸脱する傾向にある。本発明による方法によれば、これは、ペナルティ付き領域の概念を用いることによって補正される。図８Ａは、従来のＤｉｊｋｓｔｒａアルゴリズムによるボクセルに接続する距離領域を示す。図８Ｂを参照すると、本発明による方法は、オブジェクト境界に近接するボクセルに対する増大した重み付けすなわちペナルティを提供するよう重み付けされた「ペナルティエッジ」を付加することによって、Ｄｉｊｋｓｔｒａアルゴリズムの隣接エッジを補足する。図８Ｂに示すように、２７個の頂点：１個の中央の頂点及び２６個のペナルティ頂点が存在し、その各々は、中央の頂点をペナルティエッジと共有する。ペナルティエッジは、経路中に含まれるボクセルに関連するペナルティの半分に等しい重みを有する。この場合、隣接エッジは、ペナルティ頂点に接続する。この結果、グラフは、単一の構成要素に接続され、この場合、エッジは、Ｄｉｊｋｓｔｒａアルゴリズムが全体的に最小の経路を見つけることができる正の重みを有する。経路に関連したコストは、経路に関連したペナルティの全ての和を加えた経路の蓄積された安定したユークリッド距離となる。中心線は、ペナルティ付きの距離領域を通じた最小コストの経路として規定される。
【００１７】
図１は、仮想オブジェクトの組織を決定する方法を示すフローチャートである。この方法は、ＣＴ又はＭＲＩデータのようなオブジェクトの画像データが取得され、かつ、このデータが３次元ボリューム領域に変換されるとともにセグメント化されると仮定する。ＣＴ，ＭＲＩ、超音波等の２次元画像データの取得することと、２次元データを、複数のボクセルを有する３次元表示への変換することとは、そのような３次元データのセグメント化に対する種々の技術のように従来周知である。したがって、データは、ボリュームと称される３次元の直線的なグリッドとして表現され、この場合、容量測定に関するサンプルポイントは、ボクセルと称される。
【００１８】
中心線を決定するために、セグメント化された画像データは、オブジェクト境界の輪郭を描くとともに境界のボリューム内のボクセルに「内側」ボクセルのラベルを付す２値マスクを当てる（ステップ１０２）。参照することによってここに組み込まれた２００１年２月２日に出願された米国特許出願番号０９／７７７，１２０号の発明の名称が”Ｓｙｓｔｅｍ ａｎｄ Ｍｅｔｈｏｄ ｆｏｒ Ｐｅｒｆｏｒｍｉｎｇ ａ Ｔｈｒｅｅ−Ｄｉｍｅｎｓｉｏｎａｌ Ｖｉｒｔｕａｌ Ｅｘａｍｉｎａｔｉｏｎ ｏｆ Ｏｂｊｅｃｔ， Ｓｕｃｈ ａｓ Ｉｎｔｅｒｎａｌ Ｏｒｇａｎｓ”の電子結腸洗浄に開示されたセグメンテーション技術を、これに関連して用いることができる。２値マスクによって規定された２値によって、関心のある領域を、「内側」とタグを付けたボクセルを包囲する境界ボックスを用いて切り取ることができる（ステップ１０４）。ステップ１０４におけるデータの切取りによる本発明の実施に十分でない間、データセットが著しく減少し、次のステップが更に有効に行われる。例えば、医療イメージング走査の場合、ボリュームサイズが３０〜５０％のオーダに減少する。
【００１９】
切取りに続いて、「内側」とフラグが立てられた各ボクセル間のユークリッド距離が決定され及び記録される（ステップ１０６）。この結果、図２に示すように、境界フィールドからの距離（ＤＢＦ）からの写像が行われる。ユークリッド距離を決定する方法の一つは、Ｔ． ＳａｉｔｏらによるＰａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， ｖｏｌ． ２７， ｎｏ． １１， ｐｐ．１５５１−１５６５の論文”Ｎｅｗ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ Ｅｕｃｌｉｄｉａｎ Ｄｉｓｔａｎｃｅ Ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｏｆ ａｎ ｎ−Ｄｉｍｅｎｓｉｏｎａｌ Ｄｉｇｉｔｉｚｅｄ Ｐｉｃｔｕｒｅ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ”に開示された４経路アルゴリズムである。しかしながら、各ボクセルから境界までの距離を演算する他のアルゴリズムを用いることもできる。
【００２０】
好適には、関心のある領域の境界内の各ボクセルに対して、中央の互いに相違する勾配が、境界領域からの距離（ＤＢＦ）の勾配ベクトル領域（ＧＶＦ）を規定するために計算される（ステップ１０８）。これを、各ボクセルを隣接する６個のボクセルのみと比較することによって行うことができる。ポイント（ｘ，ｙ，ｚ）におけるＧＶＦは、Ｇｘｙｚ（Ｇｘ，Ｇｙ，Ｇｚ）によって見つけられ、この場合、Ｇｘ＝Ｖｘ＋１，ｙ，ｚ−Ｖｘ−１，ｙ，ｚ，Ｇｙ＝Ｖｘ，ｙ＋１，ｚ−Ｖｘ，ｙ−１，ｚ，Ｇｚ＝Ｖｘ，ｙ，ｚ＋１−Ｖｘ，ｙ，ｚ−１である。更に多くの隣接するボクセルを、２６ボクセルの隣接するソベルフィルタ（Ｓｏｂｅｌ ｆｉｌｔｅｒ）を用いることによってこの計算に用いることができるが、ボクセルの個数が増大すると、結果的に得られる中心線を向上することなく計算が低速になる傾向にある。図３の図形的な表示は、図２のＤＢＦの表示に対するＧＶＦを示す。図３において、各ボクセルに関連した各勾配領域ベクトルを、ボクセル位置の原点とともに矢印３００として示す。
【００２１】
ＧＶＦが確立された後、勾配領域ベクトルが、勾配領域ベクトル内の局所的な隣接部の特性を決定するために分析される。隣接部を、２×２×２ボクセルセルとして規定することができる。図４を参照すると、隣接部は、６分類：中心線４０２の付近の極大部、中心線４０４付近の極小部、中心線４１０付近の一様な区域、中心線４１２を外れた一様な区域、中心線４０６を外れた極大部及び中心線４０８を外れた極小部で特徴付けられる。
【００２２】
中心線４０２上又は中心線４０２付近の極大部は、８個の隣接ポイントの勾配領域ベクトルの全てが中心線に向かう方向にあるオブジェクトの中心線付近の領域として規定される。したがって、極大部４１４及び４１６によって示したように、勾配領域ベクトルは、互いに相違するが収束した方向を指示する。
【００２３】
中心線４０４上の極大部は隣接部として規定され、この場合、そのような極大部を包囲する勾配視野ベクトルの全ては、このポイントから方向が離れるとともに、隣接する極大部の方向を向く。ベクトルは、互いに相違する方向を向く少なくとも２グループのベクトル中に存在する。管腔を通る中心線の場合、各極小部は、いずれかの側の極大部によって規定される。
【００２４】
中心線４０６から外れた極大部は、一般に、中心線４０２上又は中心線４０２付近に配置された極大部と同一の特徴を有する。そのような極大部との唯一の差は、中心線から離間して配置されている点である。このことは、極大部４１８で示すように、主要な中心線を外れた分岐又は歪みに生じる。同様に、極小部４２０のような中心線を外れた極小部は、中心線に対する位置を除いて、極小部４２２のような中心線上の極小部と区別がつかない。
【００２５】
極大部及び極小部に加えて、中心線４１０の上及び中心線４２４から外れた位置にある一様な勾配領域ベクトルの領域も存在する。一様なＧＶＦは、８ボクセルセルのような隣接部のＧＶＦベクトルが平均方向から９０°未満で変化する方向のものとして規定される。オブジェクト境界に近接する領域において、局所隣接部のベクトルは、一般に、境界に垂直な同一方向を指示する。オブジェクトが急速に広がる中心線に沿った領域も存在しうる。その結果、そのような領域の中心線に隣接するＧＶＦベクトルは、一様にこの領域の中心に向かって指示する。したがって、全ての一様でない勾配領域ベクトルの領域をラベリングする方法は、中心線のこの部分を取得しない。
【００２６】
８ボクセルキューブ又はセルのような隣接部のＧＶＦベクトルが平均方向から９０°未満で変化する方向のものとして、一様なＧＶＦが規定されると、図５に示すプロセルを用いて、局所的に一様なＧＶＦベクトル及び局所的に一様でないＧＶＦベクトルにラベル付けが行われる。ステップ５０５において、規格化された平均勾配領域ベクトルが、各ボクセル位置に対して２×２×２セルのベクトルのように規定された隣接部の各々に対して算出される。次いで、２×２×２ＧＶＦベクトルの各々と関連の平均ベクトルとの間の内積を決定し及び検査する（ステップ５１０）。正の内積は、一様なＧＶＦを表し、それに対して、零又は負の内積は、一様でないＧＶＦを表す。したがって、一様でない隣接部を識別するために、正でない内積を有するセルにラベルが付される（ステップ５１５）。
【００２７】
各ボクセル位置の隣接部における少数例えば８個のボクセルを用いることによって、迅速な実行時間が許容され、その結果、境界の内側の少ない割合のボクセルのみが、中心線付近にあり得るものとしてフラグが立てられる。
【００２８】
フラグ立てプロセスの結果、複数の切り離された群のフラグが立てられたボクセルが生じる。次のステップにおいて、フラグが立てられたボクセルの接続を中心線に沿って行う（図１、ステップ１１０）。一様でないＧＶＦのフラグが立てられたボクセルの接続手順の大要を、図６及び７に示す。先ず、極大部７０５のようにフラグが立てられたボクセル位置を、開始ポイントとして選択する（ステップ６０５）。フラグが立てられたボクセルの各ベクトルは、中心線に沿って指示する成分と、中心線に向かって指示する成分とを有する。したがって、ボクセル間の経路は、次にフラグが立てられたボクセルに到達する（ステップ６１５）まで、最初にフラグが立てられらボクセルからＧＶＦベクトルの方向に沿って横切られる（ステップ６１０）。図７を参照すると、フラグが立てられたボクセル７１０から開始して、ＧＶＦベクトルがボクセル７１２に向けられる。このプロセスは、極大部７１６のフラグが立てられたボクセル７１４に到達するまで繰り返される。ＧＶＦベクトルが中心線に向かって指示する傾向にあるので、ボクセルを横切るプロセスは、自己補正プロセスとなる。例えば、ボクセル７１０は、中心線の右となり、選択された次のボクセル７１２は、中心線の左となる。７１２のＧＶＦベクトルが中心線に向かうので、選択された次のベクトルは、少なくとも中心線に近接し、場合によっては中心線の右となる。ステップ６０５〜６１５のプロセスは、フラグが立てられた一様でない隣接部の各群に対して繰り返される。
【００２９】
図１に戻ると、オブジェクト内の開始ポイントのボクセルが選択され、そのボクセルから最も離れた少なくとも一つのボクセルが、ソース領域からの距離（ＤＳＦ）を演算することによって決定される。そのような任意のボクセルから最も離れたボクセルは、中心線の終点を表し、中心線又は組織に対するルートボクセルとして選択される。開始ポイントの選択を、領域の知識によって向上させる。結腸検査の場合、直腸が検査を開始するのに最適なポイントであり、その結果、直腸付近のポイントの選択が所望される。このポイントのロケーションの評価は、データセットの中央底部に最も密接した最も近い「内側」ポイントを見つけることによって決定される。これを、結腸の「内側」であると決定されたボクセルを見つけるまで、増大する半径の被覆部の中央底部のデータセットボクセルに近接したボクセルを通じた探査を実行することによって見つけることができる。
【００３０】
ステップ１１６において、ルートボクセル領域からのペナルティ付きの距離（ＰＤＲＦ）が決定される。ＰＤＲＦの計算は、提案された経路の各ボクセルにペナルティを割り当てることを伴う。ボクセルνのペナルティｐは、ステップ１０６で計算されたボクセルのＤＢＦ値及び全てのＤＢＦ値Ｍ（Ｍ＞ｍａｘ（ＤＢＦ））の全体的な上限に基づいて割り当てられる。ペナルティｐを、
ｐ（ν）＝５０００・［１−ＤＢＦ（ν）／Ｍ］１６
によって計算する。
【００３１】
項［１−ＤＢＦ（ν）／Ｍ］は常に、オブジェクトの境界付近のボクセルに対して発生する最大値とともに［０，１］の範囲にある。発見的に選択された項５０００は、直線経路の任意の距離平均を克服するよう結果的に得られるペナルティが十分に大きくなることを保証するために十分大きくなるよう選択される。５０００の値によって、組織のセグメントを、浮動小数点精度を超えることなく３０００ボクセル長まで許容することができる。同様の特性を有する他の関数（例えば、中央に向かって小さくなるとともに境界に向かって大きくなるペナルティ）を選択することができる。
【００３２】
フラグが立てられたボクセルの各々にペナルティを割り当てた後、最小コスト経路を決定する（ステップ１１８）。経路に沿って各ボクセルで累積されたコストは、
コスト（νｋ）＝コスト（νｋ−１）＋距離（νｋ， νｋ−１）＋ペナルティ（νｋ）
蓄積されたコストに加えて、所定のボクセルＤａ（ν）の蓄積された距離は、
Ｄａ（νｋ）＝Ｄａ（νｋ−１）＋距離（νｋ， νｋ−１）
として表現される。このように蓄積された距離を用いて、ＰＤＲＦの最も遠いボクセルを識別することができ、それは、中心線の逆の端部を表す。
最も遠いボクセルから、ソースボクセルに戻る最小コスト経路が決定される。これは、エンドボクセルからルートボクセルに戻る分離した中心線を追跡することによってＤｉｊｋｓｔｒａアルゴリズムと同様に行われる。境界付近のボクセルに対して更に高いペナルティを含むために、最小コスト経路は、オブジェクトの中央にプッシュされる傾向にある。この最小コスト経路は、オブジェクトの分離した中心線となる。ツリー状構造の場合、この分離した中心線は、分離した構造ツリーの主分岐となる。
【００３３】
分離したセンターラインは、あるボクセルからあるボクセルまでの複数の接続された短いラインセグメントから構成される。そのように分離した「段階ステップ」表示は、仮想ナビゲーションのような複数のアプリケーションにおいて所望の中心線ではない。そのような場合、階段ステップは、仮想カメラのジッタとしてそれ自体が出現するおそれがある。したがって、複数の場合において、分離した中心線を円滑化するのが望ましい（ステップ１２０）。曲線を円滑化する好適な方法の一つは、適合化された許容誤差によるスプラインアルゴリズムの近似を用いることである。オブジェクトの狭い範囲において、誤差値を小さくする必要があり、それに対して、広い領域において、分離された中心線からの更なる逸脱が許容される。このような許容誤差を、境界からの距離の割合として表現することができる。５０％未満の割合によって、中心線は、境界より中心線に近接した状態となり、したがって、境界内にあることが保証される。最初のボクセル及び最後のボクセルを補間するとともにそれらの間で近似を行う周知のＢスプライン曲線を、一様でない間隔で中心線ボクセルに近接して配置された制御ポイントとともに用いることができる。複数の発見を用いて、特定の精度を達成するのに要求される制御ポイントの数を最小にすることができる。例えば、３５％の許容誤差は、制御ポイントとして、分離した中心線ボクセルの１７％を必要とし、それに対して、５０％の許容誤差は、制御ポイントとして、分離した中心線ボクセルの１３％しか必要としない。
【００３４】
単一の中心線のみが所望される結腸のような管腔形状のオブジェクトの場合、円滑化走査は、中心線発生プロセスで完了する。肺や大動脈のような更に複雑な分岐構造の場合、最初の中心線は、オブジェクトの完了したツリー構造組織の主分岐としての役割を果たす。
複雑なオブジェクトに対する組織の分岐の残りの決定は、組織の各分岐に対して繰り返されるステップ１２２〜１３０で決定される。
【００３５】
組織の規定を完了するための中心線の延長プロセスは、組織ボクセルまでの「適合した球の転がし」の概念から開始する。この結果、後に説明するように、組織の分岐の中心線の付近にあるボクセルのラベリングが行われる（ステップ１３０）。適合化された球は、境界に対する近接、スケーリング係数に適合したユーザ及び定数を規定したユーザに関連して、組織に沿って各ボクセルで規定される。これは、
半径（ν）＝境界からの距離（ν）・スケール＋定数
として数式で表現される。適合した球の半径内にあるこれらボクセルは、処理されたボクセルとしてラベルが付される。項「スケール」及び「定数」の組合せは、組織分岐を決定するのに用いられる最小形態サイズを決定する。例えば、結腸のような管腔構造において、３のスケーリング係数及び５０の定数にした結果、最初の中心線が結腸ボクセルにラベルを付し、したがって、オブジェクトを通じた中心線のみとなる。大動脈のような分岐されたオブジェクトに対して、１．１のスケーリング係数及び１０の定数が見つかると、組織の分岐として全ての重大な血管が示される。
【００３６】
中心線に沿って分岐を識別するために、ルート領域からの新たにペナルティ付きの距離（ＰＤＲＦ）が、ステップ１２２で処理されたボクセルとしてラベルが付されたボクセルの各々に対して計算される（ステップ１２４）。ＰＤＲＦは、ステップ１１６に関連して既に説明したのと同様に求められる。ＰＤＲＦ計算から最も遠いボクセルとして識別されたボクセルは、次の主要な分岐の先端として用いられる。
【００３７】
現在の分岐の先端ボクセルから、現存する組織ボクセルに到達する、すなわち、分岐が併合するまで、現在の分岐に対するＰＤＲＦに沿って経路が決定される（ステップ１２６）。ステップ１１８に対して既に説明したように、これは、分岐ボクセルのＰＤＲＦを通じた最小コスト経路の識別を伴う。
【００３８】
分離した最小コスト経路を現在の分岐に対して決定した後、分岐の中心線が円滑化される（ステップ１２８）。円滑化操作を、ステップ１２０に関連して説明したプロセス又は既知である他の任意の数の曲線円滑化技術を用いて行うことができる。適合すべき一つの追加の制約の結果、組織の二つの分岐を併合するポイントが不連続とならないようにする必要がある。
【００３９】
分岐に対する中心線が円滑化された後、分岐中心線のボクセルが、組織の分岐のデータセットに追加される（ステップ１３０）。ステップ１２２〜１３０は、関心のあるオブジェクトのセグメント化されたボリューム全体が分析されるまで繰り返される。
【００４０】
図９Ａは、大動脈の画像データのセット上でステップ１０２〜１２０を実行した結果を示す。大動脈はほぼ透明に描写され、大動脈の主要な分岐の中心線９０２がハイライトされる。図９Ｂにおいて、ステップ１２０〜１３０は、全ての分岐の血管がそれを貫く中心線を有する大動脈の全体のツリー組織まで中心線９０２が拡張するよう反復的に繰り返される。
【００４１】
任意のセグメントに対する両終点の決定を向上する他の任意の方法を用いることもできる。この方法では、近似された開始ポイントからＰＤＦを演算し、近似された開始ポイントから最長距離ポイントを見つける。最長距離ポイントは、正しい終点と考えられる。他のＰＤＦは、正しい終点から演算され、最長距離ポイントが正しき開始ポイントと考えられる。
【００４２】
結腸の一部として自動的に識別される一つより多くの接続された構成要素（すなわちセグメント）が存在する。これらセグメントの一部又は全ては、実際に結腸の一部となり得る。二つより多いセグメントが存在する場合、第１のセグメントの端部に対する最も近い新たなセグメントを見つけることによって、第２のセグメントを選択することができる。このポイントを、新たなセグメントの新たなＰＤＲＦに対する開始ポイントとして用いることができる。
【００４３】
二つ以上のセグメントがシステムによって自動的に識別されるとともに、観察者が、割り当てられた順序に同意しない場合、セグメントの一部又は全てを選択する機会がユーザに与えられる（その理由は、一部が関心のない他の器官のエアポケットであるおそれがあるからである。）。所望の順序で横切る各セグメントをクリックすることのによって選択を行うことができる。例えば、結腸検査において、医師は、通常、結腸のセグメントを先ずクリックし、盲腸のセグメントを最後にクリックする。さらに、ユーザは、全ての中心線の接続が一つの連続的な経路として出現するように、各セグメント内の好適な進行方向を反転することができる。さらに、セグメントの順の選択及び各セグメント内の方向の選択を、一方又は他方のセグメント端部の単一の選択によって行うことができる。システムは、どの端部をユーザが選択したかを自動的に決定し、必要な場合には中心線の方向を反転する。
【００４４】
組織全体を通じて案内されたナビゲーションを容易にするために、ユーザは、図形的なユーザインタフェースを用いて構造上の開始ポイント及び終了ポイントを選択することによってナビゲーション用の開始ポイント及び終了ポイントを規定する。開始又は終了ポイントが中心線又は分岐の終了ポイント付近にある場合、選択したポイントを、分岐先端の終了ポイントに対してスナップすることができるので、選択に精度を必要としない。所望の場合には、新たなナビゲーション領域を、この新たに規定された経路に対して計算することができ、新たな中心線を、選択したポイント間で発生して、分岐接合部の任意の遷移を減少することができる。
【００４５】
組織の中心線が仮想オブジェクトを通じて決定された後、そのような中心線はしばしば、オブジェクトを通じたナビゲーションに対する主要経路として使用される。既に説明したように、一般的に、中心線に沿った両方向にナビゲーションを行う機会がユーザに提供され、ユーザは、関心のある領域を調査する中心線のナビゲーションを解除することもできる。しかしながら、このようなナビゲーションの柔軟性によって、ユーザが方向を見失うおそれが生じる。
【００４６】
インタラクティブモードでナビゲーションする間に方向を見失うおそれを最小にするために、本発明による方法は、進行方向を表示するために中心線を着色するとともに既に調査された領域をマークする技術を採用する。中心線は、ユーザが現在の検査方向と同一方向（すなわち、直腸→盲腸又は盲腸→直腸）に沿って進行するか否かに従って着色される。図１０に示すように、（緑色のような）通常の色は、視点が１３５°の最も近接した中心線方向内にあることを示す。（赤色のような）正反対の色は、視点が４５°の最も近接した中心線方向の逆方向にあることを示す。好適には、この着色の決定を、中心線が２色間でフラッシュしないようにヒステリシスのレベルを追加する予め設定されたしきい値によってフィルタ処理する（図１）。現在の観察方向と最も近接する中心線方向との間の角度は、単に２方向の内積の交差として算出される。ナビゲーション中の最も近接した中心線位置を容易に決定するために、仮想的な視点に対する全ての有効な位置は、好適には迅速なルックアップに対する連続的な表示ではなく分離したポイントによって規定される最も近接したポイントに対するポインタを格納する。
【００４７】
ＰＤＦは、中心線の形成以外に重要な使用を有する。セグメント中心線終了ポイントに向かうセグメントの各々を通じてユーザの視点を変換するために、ＰＤＦファイルを用いることができる。ＰＤＦ領域は、各ポイントにおいて勾配が境界から離間するとともにセグメント中心線終了ポイントに向かって同時に指定を行う特性を有する。視点が全体的な最小値に到達するまで単に勾配方向に沿って視点を変換することによって、視点は、中心方向に向かうとともに中心線に沿って円滑に描写される。これによって、ユーザは、消失なく有効に結腸を容易に横切ることができる。さらに、ユーザが進行位置を観察するために、観察方向を進行方向に向かって回転することができる。現在の観察方向から新たな進行観察方向までの遷移を円滑に行うために、観察方向を、各時間ステップで付加される重み付けベクトルを有する新たな進行観察方向に組み合わせる。自動的なナビゲーションに加えて、ユーザは、中心線から離間したオブジェクトの境界内の自由なナビゲーションを許可される。ＤＦＰの値は、オブジェクトの境界に対する仮想カメラの近傍の測定を行う。視点が、境界から所定のしきい値距離内にある場合、境界「から離間した」視点を円滑にプッシュする力が行使される。「離間した」方向は、ＤＦＰの勾配を用いて評価される。この勾配は、境界から離間して指示する最もあり得る方向を生じる。力の大きさは、境界に最も近接するとともに境界から離間して減少する関数によって決定される。中心線の発生に関連して既に説明したオブジェクトの境界の近傍に比例するペナルティを用いるコスト領域の演算を、オブジェクトを通じて案内されるナビゲーションで用いることもできる。したがって、選択されたナビゲーション経路のコストを、選択された経路の蓄積されたユークリッド距離に経路の蓄積されたペナルティコストとすることができる。案内されたナビゲーションの開始ポイントにもかかわらず、ペナルティ領域は、中心線に向かってナビゲーションをプッシュするとともに選択されたシードポイントに向かう中心線に対してナビゲーションを円滑にダウンするよう指導する傾向にあり、そのシードポイントは、典型的にはオブジェクトの終了ポイントとして選択される。
【００４８】
本発明による方法は、任意の数の演算処理プラットホームで実行される。その技術によって効率が増大することによってパーソナルコンピュータが非常に適切に使用されることが予測される。例えば、Ｗｉｎｄｏｗｓ２０００オペレーティングシステムの下で動作するとともに単一の１ＧＨｚ  ＣＰＵを有するＩＢＭコンパチブルＷｉｎｔｅｌ  ＰＣによって、結腸の中心線を２分未満で発生したり図９Ｂの大動脈組織を３６秒で発生させるように、非常に理想的な処理時間となる。
【００４９】
本発明は、上記実施の形態に限定されるものではなく、幾多の変更及び変形が可能である。
【図面の簡単な説明】
【図１】本発明による仮想オブジェクトの組織を発生する好適な方法を示すフローチャートである。
【図２】内側ボクセルの各々とオブジェクト境界との間のユークリッド距離又は境界領域からの距離（ＤＢＦ）の数値表示に沿った関心のある領域の大要の図形表示である。
【図３】関心のある領域の勾配領域ベクトル（ｇｒａｄｉｅｎｔ ｆｉｅｌｄ ｖｅｃｔｏｒ）の図形的な表示である。
【図４】図３からの一様でない勾配隣接部のフラグ立てを示す図形表示である。
【図５】一様でない勾配領域ベクトルをラベリングする方法を示すフローチャートである。
【図６】中心線のフラグが立てられたボクセルを接続するフローチャートである。
【図７】勾配領域ベクトルに沿ったフラグが立てられたボクセルの接続を示す図形表示である。
【図８】図８Ａ及び８Ｂは、Ｄｉｊｋｓｔｒａアルゴリズムを適用することができる指導されないグラフに対するボクセルグリッド及び隣接部関係の写像を示す図であり、図８Ａは、通常の最短距離ソース領域を表し、図８Ｂは、本発明によって用いられるソース領域からのペナルティ付き距離を示す。
【図９Ａ】大動脈を通じた中心線の発生を示す。
【図９Ｂ】図１の方法による大動脈を通じた完全なツリー組織の発生を示す。
【図１０】中心線を沿った進行方向を確立する、中心線及びパラメータを有する関心のある領域の断面である。
【図１】
2004518186.tif 000003
【図３】
2004518186.tif 000004
【図４】
2004518186.tif 000005
【図５】
2004518186.tif 000006
【図６】
2004518186.tif 000007
【図７】
2004518186.tif 000008
【図８】
2004518186.tif 000009
【図１０】
2004518186.tif 000010
【国際公開パンフレット】
2004518186.tif 000011
2004518186.tif 000012
2004518186.tif 000013
2004518186.tif 000014
2004518186.tif 000015
2004518186.tif 000016
2004518186.tif 000017
2004518186.tif 000018
2004518186.tif 000019
2004518186.tif 000020
2004518186.tif 000021
2004518186.tif 000022
2004518186.tif 000023
2004518186.tif 000024
2004518186.tif 000025
2004518186.tif 000026
2004518186.tif 000027
2004518186.tif 000028
2004518186.tif 000029
2004518186.tif 000030
2004518186.tif 000031
2004518186.tif 000032
2004518186.tif 000033
2004518186.tif 000034
2004518186.tif 000035
2004518186.tif 000036
2004518186.tif 000037
2004518186.tif 000038
2004518186.tif 000039
2004518186.tif 000040
【国際公開パンフレット（コレクトバージョン）】
2004518186.tif 000041
2004518186.tif 000042
【国際調査報告】
2004518186.tif 000043