(57)【要約】  三次元データ集合の任意の部分に対してサーフェスを生成するシステム及び方法が開示される。本発明による実施形態において、最初にセグメントのサーフェスボクセルの集合を識別する方法を備える。集合内の全てのボクセルに対して、どちら側の隣接要素が内部ボクセルであるかを伝達する情報が得られる。そしてその情報の結果はボクセルを分割するポリゴン状サーフェスの位置及び方向を決定するのに使用される。サーフェスは、全てのポリゴン状サーフェスを連結することで得られる。本発明による実施形態において、ポリゴン状サーフェスは三角形で構築されてもよい。本発明による実施形態において、該サーフェスは、ワイヤフレーム・モードか若しくはソリッド・モードで表示されてもよい。本発明による実施形態において、メッシュリダクションが実施可能である。これにより最終的なサーフェスにおけるポリゴンの数が減少できる。本発明の実施形態において、メッシュサーフェスにより境界が形成されたボリュームが計算される。更に、生成されたメッシュサーフェスが「ホール（穴）」のあるサーフェスである場合、例えば、セグメント化されたオブジェクトがメッシュサーフェス生成前にクロップされる場合には、サーフェスの間のホールがメッシュにより補修された後で、ボリュームが計算される。
2007528529.tif 000002
【特許請求の範囲】
【請求項１】
３次元データ集合で表現されたオブジェクトの任意のセグメンテーション法のためにサーフェスを生成する方法であって、
該方法は、
セグメントのサーフェス・ボクセル集合を識別する段階と
セグメント・サーフェスを生成するために全てのポリゴン状サーフェスを生成する段階とを備え、
前記識別する段階は、集合内の各ボクセルにつき、
ケースごとのベクトルを生成するために、いずれの側面の隣接要素が内部ボクセルであるかを計算する工程と、
ボクセルの分割を行うボクセル中のポリゴン状サーフェスの位置及び方向を決定するためにケースごとのベクトルを使用する工程とを備えることを特徴とする方法。
【請求項２】
任意のボクセルに対して、ケースごとのベクトルが、任意のサーフェス・ボクセルをどの場所を分割するかに関して不明瞭な場合は、ポリゴン状サーフェスを生成する段階の前に後処理が実施されることを特徴とする請求項１記載の方法。
【請求項３】
前記後処理は、不明瞭なボクセルをより小さなサイズのボクセルに細分割する段階と、それぞれのより小さなサイズのボクセルに対してケースごとのベクトルの再計算をする段階と、ポリゴン状サーフェスで前記より小さなサイズのボクセルを分割する段階とを含むことを特徴とする請求項２記載の方法。
【請求項４】
各ポリゴン状サーフェスは三角形から構築されることを特徴とする請求項１記載の方法。
【請求項５】
前記各ポリゴン状サーフェスが２つの三角形から構築されることを特徴とする請求項４記載の方法。
【請求項６】
メッシュ・リダクション法を用いて前記セグメント・サーフェス内のポリゴンの数を減少させる段階を更に備えることを特徴とする請求項１乃至５いずれかに記載の方法。
【請求項７】
密閉されたセグメント・サーフェスを生成するためにセグメント・サーフェス内のホールの充填を行う段階を更に備えることを特徴とする請求項１乃至６いずれかに記載の方法。
【請求項８】
前記密閉されたセグメント・サーフェスの体積は、データ集合内で表示された実際のオブジェクトの体積を測定した値から計算されることを特徴とする請求項７記載の方法。
【請求項９】
ソリッド・モード又はワイヤフレーム・モードで前記セグメント・サーフェスを表示する段階を更に備えることを特徴とする請求項１乃至８いずれかに記載の方法。
【請求項１０】
前記セグメント・サーフェスは、元々生成された全てのポリゴン状サーフェスを使用するか、又はメッシュ・リダクションにより減少されたポリゴン状サーフェスを使用するかのいずれかの方法で表示可能であることを特徴とする請求項９記載の方法。
【請求項１１】
前記ケースごとのベクトルを生成する段階は、サーフェス・ボクセルのいずれの側面の直接的隣接要素が内部ボクセルであるかを決定する段階を備えることを特徴とする請求項１乃至１０いずれかに記載の方法。
【請求項１２】
サーフェス・ボクセルのいずれの辺隣接要素及び角隣接要素が内部ボクセルであるかを決定する段階を備えることを特徴とする請求項１１記載の方法。
【請求項１３】
ポリゴン状サーフェスの位置及び方向は、ケースごとのベクトルの関数であることを特徴とする請求項１２記載の方法。
【請求項１４】
ポリゴン状サーフェスの位置及び方向は、前記サーフェス・ボクセルのどの辺が、ポリゴン状サーフェスと交差するかによって決められることを特徴とする請求項１記載の方法。
【請求項１５】
３次元データ集合で表現されるオブジェクトの任意のセグメンテーション法のためのサーフェスを生成する方法であって、該方法は、
セグメントの内部ボクセルの最外層の集合を識別する段階と、
セグメント・サーフェスを生成するために全てのポリゴン状サーフェスを生成する段階とを備え、
前記識別する段階は、集合内の各ボクセルに対して、
ケースごとのベクトルを生成するために、どちら側の隣接要素が外部ベクトルであるかを計算する工程と、
ボクセルの分割を行うボクセル中のポリゴン状サーフェスの位置及び方向を決定するためにケースごとのベクトルを使用する工程とを備えることを特徴とする方法。
【請求項１６】
３次元データ集合で表現されるオブジェクトの任意のセグメンテーション法のためのサーフェスを生成する方法であって、該セグメンテーション法は閾値に基づいて実行されるとともに、
該セグメンテーションは、
閾値が限定的な設定であるときは請求項１記載の方法を実行する段階と、
閾値が包括的な設定であるときは請求項１５記載の方法を実行する段階とを備えることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３Ｄデータ集合の分析及びディスプレイに関する。より詳しくは、３Ｄデータ集合の任意の部分を囲むサーフェスの生成に関する。
本出願は、以下の出願の優先権を主張している。米国仮特許出願第６０／５２５８２１（２００３年１１月２８日提出）及び米国仮特許出願第 号「３Ｄデータ集合のサーフェスを識別するための方法及びシステム（ボクセル分割）」（発明者、チェン・タオ、２００４年１１月２６日提出）を参照している。出願人は本出願を補正する権利を有し、後者の仮特許出願の出願番号を記載することができる。
【背景技術】
【０００２】
ボリュームビットマップは、ボクセル値の矩形三次元グリッドからなる。ボクセル値は数値であって、通常、観察対象の１又は複数の物理的特性を推測する。観察対象とは、例えば、患者の身体の一領域又は内部構成の観察が望まれる工業製品等である。この数値は各グリッド点において、任意の特性の値を、若しくは各グリッド周辺領域の任意の特性の平均値を示す。任意の特性の値は、ボリューム要素即ちボクセルとして抽象化され、グリッド点の最も近い点の集合である。通常、ボクセル値が任意のボリューム領域に対する平均を示す場合、実際の領域は、その領域内の特性が特定のグリッド点に対するボクセル値に影響を与え、このような領域は、グリッド点に最も近いの点の集合よりも複雑である。しかしこの抽象化は便利な概算法としてよく使用される。３本の長方形の各軸に沿って等しく伸びた３Ｄグリッドは、各グリッド点周囲のボクセルが、グリッド点を立方体の中心に有する立方体の形の一単位のボリュームユニットである。結果的に、本願では「立方体（cube）」という用語は「ボクセル」と同義的に用いられる。
【０００３】
各エッジ上に沿ってグリッド・ステップを備え、各コーナー（角）にグリッド点を備える長方形領域も立方体といえるが、この意味の「立方体（cube）」は従来のマーチング・キューブ法（Marching Cubes algorithm）で使用される。本願では「立方体」をこの意味で使用しない。点の値が、厳密に次のように物理的な位置するわけではないが、物理測定システムにより生成された値をボクセル「内」にある、又は対応するグリッド点「上」にあると表現する。しかしながら、この大よその定義によって、正確な結果を推定することは可能なため、むしろ好都合といえる。更にグリッドにより占有される空間における通常の点を（x, y, z）とし、グリッド点を（i, j, k）とするとき（i，j，kは整数値である）、点（x, y, z）と点(i, j, k)を区別するのに有用である。（x, y, z）の座標は、同一のグリッドステップユニット（これによりボクセルは自動的に立方体となる）内で測定される。尚、整数値以外も測定可能である。
【０００４】
コンピュータ断層撮影法（CT、Computer Tomography）、磁気共鳴（MR、Magnetic Resonance）、超音波（US）、陽電子放出断層撮像法（PET、Positron Emission Tomography）、地震観測法（seismography）などの様々なモダリティにより、ビットマップが生成される。このビットマップにより、Ｘ線又は振動波に対する不透過性、放射性粒子の放出、水素原子核の周辺分子への結合といった特性が示される。同じように、数値でグリッド点（ｉ，ｊ，k）において三次元位置の関数f(x，y，z)の計算結果を示してもよい。この関数で、所望の抽象データを定量的に示したり、若しくは任意の３つの値をもつ数字をx，y，zに関連付けて表示し、これらの数字で空間的な位置又は定量的データ（例えば、反応時間、インベストメント（investment）のリターン等を表すこともできる。単一の数字からなるボクセル値はスキャラーである。二以上の数値からなるボクセル値が、カラーモデルから類推して、各グリッド点に関連付けされる場合、スキャン画像は分光写真とよばれることがある。スキャンの物理的特性は、様々な波長が混合した放射又は反射の集中度が関与している。分光学的データは、赤、緑及び青の濃度を要素ごとに異なる数に対して割り当てることで、ディスプレイのための可視色と関連付けてもよい。しかしスカラー・スキャンを使用すると、カラーは「値が４２を超えれば赤、４２以下なら透明」といった法則に基づいて、要素ごとに割り当てられることが可能である。要素は、どのような信頼度で配列、患者ががんに侵されているとか、石油が含有されるとか、スキャンされるオブジェクト中の対応する点における関心領域であるといったことに関連付けされていて、スキャンの物理的特性が、例えば、定められた閾値以上となると、ユーザは赤で表示されたディスプレイを見て、例えば、腫瘍、石油備蓄、その他の被撮像オブジェクトの物理的なレイアウトについて情報を得ることができる。配色の決定に関してより複雑なテストを使用してもよい。テストの例としては、例えば、付近の要素の平均値より著しく高い数値を有する、特定の数値の組の間にある要素には配色をする。一方で分光学的データをともなうと、あらゆる要素が関与し、法則がより複雑になる。多くの場合において、最終的な結果は、物理的な点における素材が、ユーザの興味のある特性を備える、若しくは備えないという二者択一の結果となる。
【０００５】
ディスプレイが、上記の例のような配色決定の法則を使用している場合、ユーザはオブジェクト（腫瘍など）を認識できるが、赤色の表現は集合体として、ユーザの認知を喚起するに過ぎない。コンピュータは、オブジェクトに帰属する位置の集合に関して明白な表現を有するわけではない。実際、「赤か透明か」の二者択一とは対照的な、連続的な色調変化を表示する規則を備えると、認識された赤色のオブジェクトの輪郭が、くっきりと表示されない可能性がある。するとファジー理論のように、多かれ少なかれ集合内に位置するといった程度の認識にとどまる。これは人間の認知構造にはあっている。しかし多くの用途に対応するには（腫瘍のボリュームを計算する場合など）、輪郭は明確であるべきで、要素がオブジェクト内に含まれるべきか否かを計算可能な決定プロセスであるべきである。このようなプロセスは、スキャン全体の要素とは区別される一又は複数のセグメント（segment、要素の部分集合）を使用して行われ、立体画像のセグメンテーション（segmentation）と呼ばれ、それについての研究文献も多く存在する。セグメンテーション法は、よく知られた手法である。本願において、一部のセグメンテーションは、３Ｄデータ集合の要素を、所望の特定の分類の「内部」にあるか又は「外部」にあるかを標示するために使用される。内部要素の集合を、本願では「セグメント」と呼ぶ。セグメントは適用の実際により様々である。例えば、頭蓋骨、石油備蓄、製造物の空洞部などで、データ元やスキャン・モダリティにより多様である。
【０００６】
セグメント内の要素のリスト化を行うことだけが、最も有用な表現の方法であるとは限らない。具体的には、要素のカウントは、境界サーフェスの位置の推定や、境界サーフェスを含むボリュームの計算よりも、精度は劣る。図１は、２次元で再現された推定の対比である。円（１０１）は、５０個の正方形に相当する面積を有する。しかし、円（１０１）は、外部要素（１０３）から独立した、ユニット化した内部サンプリング要素（１０２）を４５個しか含まない。挿入された曲線状の境界、即ち円（１０１）内部の面積を計算すると、より正確な推定結果が得られる。
【０００７】
明確な境界サーフェスの存在により、その他にも様々な用途が考えられる。例えば、オブジェクトから外部点への距離や、オブジェクト境界からその内部の点への距離を求めたい場合は、オブジェクト内部又は外部それぞれに対して全ての要素を計算する必要はなく、最小限の処理に抑えることができる。サーフェス要素を扱うだけで十分な結果が得られる。サーフェス要素は通常、全ての要素の数から比べると、かなり数が少ない。例えば、各辺（エッジ）につき１００グリッド点を有する立方体では、１００万のグリッド点を有するが、サーフェス点は６万個（各面につき１万個×６面）である。このようにして立方体のサーフェス（即ち６つの面）への距離を求める計算処理の労力が著しく減少される。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
特に、明確にサーフェスを表示しようとすると、オブジェクトを可視的に表示するためのレンダリングの速度を大幅に向上させる必要が生じる。近年の急速な技術進歩にもかかわらず、良質で滑らかな画像、透明度評価などに要求されるインターポーレーションを備えたうえで、要素ごとに、サンプル点が数百万もある立体を直接的にレンダリングすることは、双方向性アプリケーションに対する十分な速度の実現が未だ困難である。オブジェクト周辺の「意味を持たない」要素や、オブジェクトが切断されない限り最終的な画像には映らない内部の要素を求めるプロセスは、時間と労力の無駄である。
【０００９】
コンピュータ環境によって、サーフェスの表現方法を変えて最適なものに適宜変更することも可能である。多くのグラフィック・カードは、三角形の面の集合（即ち、ポリゴン状サーフェスを意味する。ポリゴン状サーフェスは通常、三角形の面からなる。）の高速表示に特に最適化されている。しかしボリュームのレンダリング速度は遅い。一方で、ボリューム重視のコンピューティング環境では、ポリゴンよりも、より好適にサーフェスボクセルが使用できる可能性がある。小規模なポリゴンが数多くあるメッシュサーフェスは、触覚的にも、視覚的にもレンダリングに適さない。なぜなら三角形のサーフェスを一つずつ処理しなければならないためである。しかもこの処理は触覚的ディスプレイでは時間の制約上、不可能である。更に、その視覚的にディスプレイされる画像が一ピクセル以下の幅のポリゴンは、アンチエイリアシングのアルゴリズムに対して実質的に困難を引き起こすことが多い。アンチエイリアシングとは、グラフィック・システムでより滑らかな画像を表示させるための技術である。メッシュリダクション技術は、推定を利用して、数の少ないポリゴンを複数使用したサーフェスに置き換えることができる。これにより、コンピュータ処理時間の削減が図れる。（メッシュリダクション技術については、http://www.matinb.com/contacts/meshreduction.htmか若しくは、Ｐ．Ｓ．Heckbert and M．Garland著，“Survey of Surface Simplification Algorithms”，Technical Report，Computer Science Dept., Carnegie Mellon University，1997年を参照。）
【００１０】
ボクセルデータを三角形メッシュに変換して、セグメンテーションを内部要素と外部要素に分割する有名な手法としては、「マーチング・キューブ法」がある。分割するサーフェスを生成する他の手法として、例えば、H．H．Baker著“Building Surfaces of Evolution： The Weaving Wall”， Int. J Comp Vision 3，51‐71、1989年、及びT．Poston，T‐T Wong， P‐A Heng著“Multiresolution Isosurface Extraction with Adaptive Skeleton Climbing”，Computer Graphics Forum 17：3，1998年9月3日，pp．137‐148がある。しかしながら、これらの手法が強調する点は、数値が関連付けられた要素の分割であって、ボクセル全体の分割ではない。更に従来技術であるマーチングキューブ法やその関連技術を使用して生成されるサーフェスは、完全に閉じたサーフェスを検出するのが難しく、サーフェス中に「ホール（穴）」即ち連結されない部分が生じてしまう。
【００１１】
ボクセルによりサーフェスを表現する単純な手法では、外部ボクセルが隣接する全ての内部ボクセルをリスト化するか、若しくは内部ボクセルが隣接する全ての外部ボクセルをリスト化する。このような構造化されていないリストは、様々な使用法に適用できるが、目的によっては不都合となる可能性もある。
例えば、サーフェスが内部要素と外部要素とを分割する。このため、元の大きなボリュームビットマップ又はセグメンテーションの結果を検索せずにある要素を内部にあるか外部にあるかを特徴付けることが可能である。また使用中のメモリにも負担をかけない。このような特徴付けは、例えば、力覚フィードバック環境中のオブジェクトに触れるときなどに有用である。力覚フィードバックでは、ツールチップが、あるオブジェクトを指すと、力覚情報が得られるシステムである。力覚フィードバックには、１ミリ秒以下の反応時間を要するため、望ましくない長時間のコンピュータ処理が生じる。このような内部／外部の特徴づけは、従う数学的仮定が少ない境界ボクセルの非構造化リストでは難しい。更に、標準的な手法で生成された三角形サーフェスには適合しない。サーフェスの表現を切替えられるようにすれば、両者の利点を活用できる。
【００１２】
2007528529.tif 000003
【課題を解決するための手段】
【００１３】
三次元データ集合の任意の部分に対してサーフェスを生成するシステム及び方法が開示される。本発明による実施形態において、最初にセグメントのサーフェスボクセルの集合を識別する方法を備える。集合内の全てのボクセルに対して、どちら側の隣接要素が内部ボクセルであるかを伝達する情報が得られる。そしてその情報の結果はボクセルを分割するポリゴン状サーフェスの位置及び方向を決定するのに使用される。サーフェスは、全てのポリゴン状サーフェスを連結することで得られる。本発明による実施形態において、ポリゴン状サーフェスは複数の三角形で構築されてもよい。本発明による実施形態において、該サーフェスは、ワイヤフレーム・モードか若しくはソリッド・モードで表示されてもよい。本発明による実施形態において、メッシュリダクションが実施可能である。これにより最終的なサーフェスにおけるポリゴンの数が減少できる。本発明の実施形態において、メッシュサーフェスにより境界が形成されたボリュームが計算される。更に、生成されたメッシュサーフェスが「ホール（穴）」のあるサーフェスである場合、例えば、セグメント化されたオブジェクトがメッシュサーフェス生成前にクロップされる場合には、サーフェスの間のホールがメッシュにより補修された後で、ボリュームが計算される。
【発明を実施するための最良の形態】
【００１４】
本発明は、３Ｄデータ集合の任意のセグメントを完全に囲むボクセルサーフェスを生成するためのシステム及び方法に関する。「ボクセルサーフェス」とは、「サーフェスボクセル」を含む要素の集合であり、更に特定の数学的な仮定を満たすデータもいう意味も含めて用いられる。このボクセルサーフェス生成のデータ構造及びデータ特性により、そのデータから更にメッシュサーフェスを生成することが可能となる。メッシュサーフェスの三角形又は他のポリゴンは、ボクセルサーフェスのボクセル一つ一つの間に密着する（メッシュサーフェスは、内部ボクセルの場合と同様に、ボクセルサーフェスにより囲まれることで区別される）。三角形のカウントは、マーチング・キューブ法で得られた方法と類似している。ボクセルサーフェスの生成には、各ボクセルと連結されるサーフェスの一部を交差させて、単純に連結する。これを行うには、特定のボクセルが分割されるか、若しくは（通常はあまり望ましくないが）充填される（filled in）ことにより、サーフェスではなくセグメントのボクセルを生成する。
【００１５】
このメッシュサーフェスは、ボクセルサーフェスの分割方法と共通の特性を有する。つまり、サーフェスの内部の点をサーフェス外部の点から分割する特性を有する。連続的な軌跡において、点の間、内側、外側はメッシュ内の少なくとも１つの三角形と交わる必要がある。任意の点（ｘ、ｙ、ｚ）について、メッシュサーフェスからの距離、及びボクセルサーフェスからの距離（即ち、任意の点からボクセルサーフェスの一要素であるボクセル中心までの最短距離）が、メッシュサーフェスからの距離（任意の点からメッシュサーフェスの三角形のポイントまでの最短距離）にあるボクセル直径の半分以内となる。ボクセルサーフェスとメッシュサーフェスの２つのサーフェスのモデルは密接に連携し、適宜最適なモデルに変更しながら使用できる。
【００１６】
メッシュサーフェスはレンダリングされ、ユーザに視覚化されるか、当該技術分野ではよく知られた技術である触覚・力覚フィードバックとして使用してもよい。ボクセルサーフェスは、「スプラッティング」等の手段によりレンダリングされる。（参考文献P．Schroeder & J. B. Salem著，“Fast Rotation of Volume Data on Data Parallel Architecture”，Proceedings of Visualization ‘91,サンディエゴ, カリフォルニア州, 50‐57，1991年10月、及びK．Mueller & R．Yagel著，“Fast Perspective Volume Rendering with Splatting by Utilizing a Ray‐Driven Approach”，Proceedings 1996 Symposium on Volume Visualization，サンフランシスコ，カリフォルニア州， 1996年9月，pp．65‐72）コンピュータ処理時間のコストは、ボクセルキャストの数に比例する。この場合は通常、全体のスキャンよりもかなり数が少ない。サーフェスボクセルの数は、通常、対応するサーフェスメッシュの三角形の数の半分以下となる。このため、オブジェクトのより高速なディスプレイが可能となる。
【００１７】
実施例において、高速アルゴリズムによりある点（x，ｙ，ｚ）がボクセルサーフェスの内部か外部にあるかが決定される。例として、ｘ方向のステップがサーフェスのボクセルに交差するまで（条件として三角形の交差をテストするよりも高速）の間を判定する。サーフェス上では、サーフェスのデータ構造が、ステップが内部から来るか外部から来るかについて非常に高速な判断を行う。ボリュームデータを修正するユーザ双方向性（例えば、編集やシミュレート・ドリリング機能）は、ボクセルサーフェスのみに基づいている。このためメモリに要求されるデータも比較的少なく、より高い性能が実現できる。
【００１８】
ボクセルサーフェスは、元のボリュームビットマップからボクセル値を修正するために使用されてもよい。ボリュームビットマップでは、サーフェスがディスプレイ上で異なるパターンで表示されるように、サーフェスに様々なパターンを加える。例えば、画像からのカラー値は、ボリュームビットマップの点上で計画される。これにより内部の情報又は断面の情報（脳又は骨構造など）を明示する同一のボリュームレンダリングによって自然な色調でスキンを表示することができる。このときにメッシュサーフェスを別々に表示するコストをかけずに、処理を行うことができる。ボリュームビットマップによる色調調整が形状の変更と組み合わされる場合は（例えば、美容整形のプランニングなど）、更に質の良い視覚化が実現される。
【００１９】
2007528529.tif 000004
【００２０】
以下の記載における多くの事項は、整数値(ｉ，j)の組で示されるピクセル（画素）の１グリッドが対応する構成の任意の２次元（２Ｄ）において、好適に実施可能である。２Ｄの境界曲線の生成の問題は、３次元（３Ｄ）の境界サーフェスの生成に比べると、はるかに単純であるが、本発明による論法は、何次元でも適用可能である。よって、当業者により４次元以上の「超曲面」の境界の生成に拡張されてもよい。（通常の４次元データ集合の生成は、システムを変更するスキャンを連続的に行うことで実現できる。４次元データ集合は（ｉ，ｊ，ｋ，ｔ）の４つの整数により示され、これらの整数値により位置及び時間の両方が識別される。）従って一般化のために、ピクセル、ボクセル、及びより高い次元における類似体を、次元の数に関わりなく正確な記述として、本願では「要素」と呼ぶ。
【００２１】
2007528529.tif 000005
【００２２】
２．細分割
ボクセルの細分割は、ポリゴン状サーフェスをどの位置に配するかが不明瞭な場合に必要となる。ポリゴン状サーフェスを更に分割して、オブジェクトの境界を推定する形状にする。図２に関して、内部ボクセルの濃いグレイ部分（２３１）の中にグルーブ（groove）構造があるため、グルーブの「内部」にある外部ボクセルをひとつずつ分割するのが難しい。グルーブはポリゴン状サーフェスを使用しているため（非曲線状に分割されたサーフェスとなり）、オブジェクトのサーフェスにインデンテーション（ギザギザ）が残る。これは、以下の記載でより詳細に記載するが、要素の集合（２３０）内部で（２３０）と隣接してグルーブ内部に２つのボクセルが示され、Ｙ方向の各サイドに内部ボクセル隣接要素を備え、不明瞭な結果となっている。この原因は、分割システム中では、オブジェクト境界が、隣接内部ボクセル（２３１）と隣接外部ボクセルの間でボクセルサーフェスを半分に切断するように引かれ、その分割システム中でオブジェクト（２３１）の「グルーブ」内部にあるボクセルサーフェス上のボクセルに対して、オブジェクト境界を引く場所がない。隣接する両側の面のうち、一方の面に内部ボクセルが接し、もう一方の面に外部ボクセルが接するようなボクセルは存在しない。
【００２３】
本発明の実施形態において、上記の課題を解決するために様々な方法が使用される。１つの手段として、ｎ次元の要素を２ｎ個に細分割する（ピクセルならば４分割、ボクセルならば８分割）。ボクセル経路（２４１）はこの技術により可能となる。（このとき「面隣接要素」の定義として、分割されて異なるサイズとなった要素も含むことになる。）ここで、それぞれの新しいボクセルは、内部及び外部隣接要素を持つ。内部隣接要素は濃色のオブジェクト（２３１）の要素であり、外部隣接要素は細分割されたグルーブのボクセルの一部である。境界は各グルーブボクセル（２４１）を横切るように引かれ、オブジェクトの実際の境界が保持される。実際、不明瞭なグルーブボクセルを一つずつ細分割することで、サーフェスボクセル（２３０）の状態を（２２０）の状態へと変形する。
【００２４】
若しくは、不明瞭な要素に対して、例えば「フィリング（充填）」を行って、これにより単純に不明瞭性を除外してもよい。ボクセル経路（２５０）は領域（２３１）の拡大バージョン（２５１）を囲み、容易に分割可能である。ある要素がセグメント内にない場合、その要素は困難を伴い、セグメント内にある隣接要素の集合は、隣り合わない２つの領域の中の要素に接触する（図２の（２３１）のような１ボクセル幅の「グルーブ」や「穴」を持つオブジェクトの場合と同様）。このような不明瞭な要素をセグメント内に移動させると、以前は問題のなかった要素にも上述のような特性の問題が生じてしまう。よってボクセルの充填を繰り返し行うべきである。以下に示される生成では、ボクセル値を使用したインターポーレーションにより、立方体の辺に沿ってサーフェス頂点を配する。インターポーレーションは、全ての内部ボクセルが閾値Ｔ以上の値を持つ場合のみ、正確に機能する。充填したボクセルに新しい値を割り当てるが、その後再度カテゴリー分けを行う必要がある。
【００２５】
2007528529.tif 000006
【００２６】
あるセグメントに充填を行うと、構造の詳細部に対して不適切な損失が引き起こされるため（例えば、１単位の幅を有する要素により被撮像オブジェクト中の液体が流れる管が途切れる）、本発明による実施形態において、細分割が使用されてもよい。２以上の次元では任意の要素集合での隣接要素の集合は、標準的な幾何学的演算手法を使用して容易に生成可能なサーフェスが構成出来ない可能性がある。そのためこれらの修正方法のうち１つ又はその他のものが適用される。
【００２７】
図３に示されるように、細分割を実行する方法は複数ある。スキャンデータが挿入される段階（３０１）と要素が「ＩＮ」又は「ＯＵＴ」のいずれかに分類される段階（３０２）の後、図２に示す（２４１）のような経路を生成するか、（２６０）のようなｎ次元の類似体を生成し、段階（３０３）において、例えば、全ての要素が細分割され、段階（３０４）において、例えば、細分割された新しい要素には、細分割をした要素に応じて「ＩＮ」又は「ＯＵＴ」のいずれかに標示をつける。即ち２次元の場合、新しい（ｉ，ｊ，ｋ）は、古い（ｉ，ｊ，ｋ）を整数で分割（余り切り捨て）した（ｉ／2，ｊ／2，ｋ／2）に対応する。他の次元においても同様である。（３０５）のループ段階でこの論理を完了した後、メッシュサーフェスは下記のように生成される。段階（３０６）は実行してもしなくてもよいが、データオブジェクトとして、オブジェクト内にボクセルサーフェスを明確に生成する。しかしながら、例えば、３次元の細分割では、三角形の数が４倍となるため、要素をより大きな要素に結合させることが有用となり得る。これは本発明における実施形態において、利用してもよい選択肢である。単純な方法の一つとして、段階（３１０）で、拡大した配列構造を崩さずに、結合させて標示をつけて、標示がついた要素のうち、要素の座標値にひとつでも奇数があるものを飛ばし、全てが偶数である座標値を、もとからの座標値として取り扱う。但し、拡大された配列構造は、もとのメモリ量の２ｎ倍のメモリ量を要する。よってメモリ量が限られている場合は、様々な技術を使用して、ポインタにより元の立体と連結される、細分割された要素に対してのみ追加的なメモリが割り当てることができるデータ構造として生成してもよい。
【００２８】
本発明による実施形態において、分割された要素と分割されていない要素の間を区別する代替方法として、要素を統合させる段階（３１０）を省略して、例示されたシステムでは、単純化された要素からなるデータ集合として、２ｎ倍に拡大した配列構造（３次元では８倍の大きさ）を用いて、更に単純に機能させてもよい。３Ｄではこのプロセスにより三角形の数が４倍になるため、段階（３０８）において三角形をもとの要素に結合させることが有用である。また可能性として、段階（３０９）で最終的なサーフェスを出力する前に、上記のメッシュリダクション法を使用して三角形の数を減らすことも一つの方法として考えられる。
【００２９】
３．サーフェス生成
要素集合Ｇを、内部要素（内部ボクセル）集合Ｉとその残りの外部要素集合Ｏ（Ｏ＝Ｇ−Ｉ）にセグメンテーションを行うと、本発明の実施形態において、ボクセルサーフェスΣが生成される。説明の便宜上、最初の完全な細分割のケースに対する方法が、本願において記載されるが、様々なケースでは最適な方法ではない可能性もある。最適に改良を加えたその他の実施形態も、解釈可能である。
【００３０】
本発明の実施形態において、スタック候補Ｃは、例えば、外部要素集合Ｏにある全ての要素を含むように生成される。外部要素集合Ｏにある要素は（面、辺、角など任意の種類の要素で）内部要素集合Ｉにある要素と隣接する。スタック候補Ｃは、単純に（ｉ，ｊ，ｋ）の値のリストとして記憶されるか、若しくは特定の（ｉ，ｊ）で表される各直線において要素のランレングス符号化という圧縮方法を使用して記憶されるか、若しくは当業者に知られた手段により記憶される。
【００３１】
このプロセスを実行する方法は複数ある。例えば、第１の方法はボリュームビットマップ内の（ｉ，ｊ，ｋ）全体にわたって記憶を繰り返し、ボクセル一つずつに対して（ｉ，ｊ，ｋ）がセグメンテーションの外部にあるかどうかを判別して、外部にある場合はスタック候補Ｃとし、更に内部隣接要素があるかどうかを判別する。第２の方法は、スタック候補Ｃに含まれるべき「シード要素」を選択し、シード要素の隣接要素を検査し、その検査した隣接要素をスタック候補Ｃに加え、この加えた隣接要素に隣り合う隣接要素を更に検査し、という工程を繰り返していく。下記のプロセス段階の後、内部にセグメントや空洞部を含む連結したサーフェスが作り出される。空洞部が含まれたり、その空洞部内に連結されない要素が含まれる場合以外は、サーフェスに囲まれるセグメントの部分も連結される。
【００３２】
表１は２次元の場合に使用される変数のリストを示す。変数ｅｉ−，ｅｉ＋，ｅｊ−，ｅｊ＋の意味は表１のとおりである。また表１は隣接ボクセルの情報を集めるスキーマの例を示す。２次元では、隣接するピクセル情報は当然収集されるべきものである。この情報はピクセル境界の形状、方向、位置を決定するために使用され、これによりセグメント化されたピクセル内に含まれると思われる被撮像オブジェクトの境界を推定する。
【００３３】
（表１）
（２次元の隣接情報に関する変数の例）
2007528529.tif 000007
【００３４】
次に、この概念の３次元若しくはそれ以上の次元への適用を記載する。実際のオブジェクトとスキャンデータのセグメンテーションにより得られた内部ボクセル集合の間には差異が生じる。これはスキャンエラーや解像度が空間的に均一でないことが原因である。実際のオブジェクトは、全体がセグメンテーション内に含まれる場合もあるし、そこに含まれない場合もある。これはセグメンテーションの様式が「リベラル（包括的）」であるか「スペアリング（限定的）」であるかによる。「包括的」な設定の場合は、実際のオブジェクトの境界をまたぐボクセルも含む。「限定的」な設定の場合は、実際のオブジェクトの境界の内部のボクセルのみを含む。
【００３５】
但し、内部ボクセル（閾値化やセグメンテーションでの定義による）はオブジェクトの実際の境界は含まないものと仮定する。この仮定では、閾値は限定的に設定され、実際のオブジェクトは内部ボクセル集合の一部又は全体を含み、それ以上は含まないことを意味する。また境界は（挿入される境界か元から存在する境界かに関わらず）、サーフェスボクセル（即ち、セグメンテーションにより外部ボクセルと識別されたもののうち、内部ボクセルと隣接するボクセルの集合）内にあるものとする。一方で、本発明は閾値が包括的に設定される場合も含む。包括的な設定の場合は、内部ボクセルが実際のオブジェクト境界も含み、オブジェクト境界は（挿入されるか元からあるかに関わらず）、内部ボクセルに含まれるものとする。通常、境界は、内部ボクセルの最も外側の層になる。以下の説明において、内部ボクセルが実際に分割されて、外部サーフェスボクセルに対するサーフェスを生成する要素となる場合は、fとＴに代入する値が入れ替えられ、包括的に設定された閾値が適用される。いずれの設定においても、ボクセルを分割し、実際のオブジェクトの実際の境界が、仮想ボクセル環境中のどの場所に存在するかが推定される。
【００３６】
本発明の実施形態において、任意の閾値に関連付けされたサーフェスを生成するために、（１）第１にサーフェスを含むボクセルを特定する。そして（２）ボクセル内のサーフェスの形状が決定される。最後に（３）サーフェスの周縁がどの位置でボクセルの辺及び面と交差するかを計算する。以下の記載はこれらの処理を全て行う。
【００３７】
（１）ボクセルサーフェスの特定
本発明の実施形態において、サーフェスを含むボクセルを特定する方法が２通り存在する。第１の方法として、ボリュームデータのボクセルを一つずつ調べていく。ボクセル値によって、内部ボクセルであるか外部ボクセルであるかが識別される。内部に隣接要素が少なくとも一つ存在する場合は、外部ボクセルはサーフェスボクセルの要素として置かれる（即ち、サーフェスボクセルに含まれる）。このサーフェスボクセルと定義されたボクセルは、サーフェスに行きわたる（即ち、サーフェスに含まれる）ボクセルとする。
【００３８】
第２の方法は、ボクセルサーフェスを抽出するシード点を使用する方法である。サーフェスボクセル点を与え、このサーフェスボクセルの６７６６個の直接的な隣接要素（直接的に隣接する要素）は、１個の内部ボクセル又は、２個の対向しない内部ボクセル又は、３個の内部ボクセル（３個のうち２個が対向していないもの）を含む。全てのサーフェスボクセルに対して、２６の隣接要素の検査が必要となり、これにより新しいサーフェスボクセルが特定される。その新しいサーフェスボクセルそれぞれに対しても、２６個の隣接要素が検査される。このプロセスは、全てのサーフェスボクセルそれぞれに対して２６個の隣接要素が検査し終わるまで続く。
【００３９】
第一の方法では、ボリュームデータ内の全てのオブジェクトのサーフェスを特定することができる。しかしながら、ボリューム全体を処理する時間が増える。第２の方法では、若干処理時間が短縮されるが、オブジェクトの距離がボクセル２単位より大きい場合は、全てのオブジェクトのサーフェスを特定することができないことがある。
上記の説明は３次元の場合である。２次元の場合は、ボクセルをピクセルに、サーフェスを曲線に置き換えれば説明ができる。
【００４０】
（２）サーフェスボクセル一つずつに対して直接的隣接情報を取得。
本発明の実施形態において、サーフェスボクセルの集合が特定されると、サーフェスボクセル一つずつに対して直接的隣接情報が収集される。直接的隣接情報とは、どのサーフェスボクセルの隣接要素がオブジェクト内部にあるか、つまり「内部ボクセル」であるかを伝達する。任意のボクセルの直接的隣接要素とは、任意のボクセルと一つの面全体を共有するボクセルのことである。各ボクセルは６個の直接的隣接ボクセルを持つ。
【００４１】
サーフェスボクセルの直接的隣接情報を記録するために、一時的なブーリーン変数が各サーフェスボクセルに対して割り当てられる。一時的な変数を次の手法で使用して、サーフェスボクセルからなるサーフェスの形状に関する情報を演算する。これにより、全てのサーフェスボクセルに対して、ブーリーン変数が演算可能である。
【００４２】
2007528529.tif 000008
【００４３】
（表３）
（直接的な隣接要素に関する情報、例えば、記憶するための変数の例）
2007528529.tif 000009
【００４４】
説明の便宜上、現在処理中のボクセル（カレントボクセル）をサーフェスボクセルであるボクセル（１４）とする。図４の例に示される如く、ボクセル（１４）は６個の直接的隣接要素を持つ。即ち、ボクセル（１３）、（１５）、（１７）、（１１）、（５）、（２３）である。
【００４５】
一時的なブーリーン変数の計算例は、以下の通りである。
ａ）左側の直接的隣接要素（１３）が内部の場合、ｅｉ−をＴＲＵＥに設定；
ｂ）右側の直接的隣接要素（１５）が内部の場合、ｅｉ＋をＴＲＵＥに設定；
ｃ）下方の直接的隣接要素（１７）が内部の場合、ｅｊ−をＴＲＵＥに設定；
ｄ）上方の直接的隣接要素（１１）が内部の場合、ｅｊ＋をＴＲＵＥに設定；
ｅ）後方の直接的隣接要素（５）が内部の場合、ｅｋ−をＴＲＵＥに設定；
ｆ）前方の直接的隣接要素（２３）が内部の場合、ｅｋ＋をＴＲＵＥに設定；
【００４６】
2007528529.tif 000010
【００４７】
例えば、図５に示されるボクセルのセグメンテーションを使用して、上述した演算を実行した後、ボクセル（４）、（５）、（８）、（１３）、（１４）、（１７）、（２２）、（２３）、（２６）に対して以下の結果が得られる。（これらのボクセルに対してのみ演算結果を示す。３×３のボリューム中の残りの１５個のボクセルは、直接的に隣接する内部ボクセルがないため、取り上げない。）
【００４８】
（表５）
（内部ボクセルが直接的隣接要素である情報、空白部は「ＦＡＬＳＥ」を示す。
2007528529.tif 000011
【００４９】
任意のボクセルに対して考えられる全ての直接的な隣接要素は、下記の表６に示される。表６の内容に対応して、添付資料１で各ケースに対応する図解を提供する。添付資料１ではｅの値及びｅが任意のボクセルの直接的隣接要素の関数として計算されるプロセスを説明している。添付資料１において、内部ボクセルと外部ボクセルは色の濃淡で区別され、内部ボクセルは濃色、外部ボクセルは薄色で示される。
【００５０】
（表６）
（内部ボクセルであるボクセルの直接的な隣接要素に対して考えられる全てのケース）
2007528529.tif 000012
2007528529.tif 000013
2007528529.tif 000014
2007528529.tif 000015
2007528529.tif 000016
【００５１】
表６に関し、６−１のケースでは、明らかに内部ボクセルのことを示しているので、サーフェスボクセル集合の構成要素ではないが、検査項目に含まれている。これは、本発明の実施形態において、実施形態によっては、この６−１のケースを除くよりも処理ループに含めて検査したほうがより効果的であるためである。
【００５２】
（３）サーフェスボクセル内に挿入されたサーフェスの形状に関する情報
直接的隣接要素に関する一時的なブーリーン変数では、十分な結合性を有するサーフェスを生成するために必要な情報は提供されない。例えば、図５において、内部ボクセルはボクセル（１６）のみとする。そのとき、ボクセル（１３）及び（１７）にあるサーフェスの形状情報が判明しているのに対して、ボクセル（１４）については何の情報もない。このため、ボクセル（１３）のサーフェスとボクセル（１７）のサーフェスを結合するのは難しい。これはボクセル（１４）が直接的隣接要素を持たず、ｅ又はｅ値がないためである。しかしながら、ボクセル（１６）がボクセル（１４）の（直接的隣接要素ではないが）隣接要素となるため、サーフェスはボクセル（１４）の左下の角から分割されるのがよい（同様の方法で、図２のサーフェスボクセル（２０１）から境界をどう引くかに関しては、ボクセル（４）の右下の角、（５）の左上の角、（６）の右下の角にわたって境界を引く）。実際には、この場合にボクセル（１４）を分割する正確なサーフェスは、添付書類３のケース３（３ページ目）に説明される。従って、以下に記載するように、サーフェスボクセル付近の境界情報を共有することが必要となる。
【００５３】
よって、例えば、サーフェスボクセル全てについて、変数が新たに定義される。元の隣接要素情報並びにボクセルと隣接ボクセルが共有する情報を記録する。これを表７に示す。本発明の実施形態において、ブーリーン型変数はＦＡＬＳＥに初期設定されてもよく、整数値は０と初期設定されてもよい。
【００５４】
【表７】
2007528529.tif 000017
【００５５】
サーフェスボクセルと内部ボクセルの間の接する面に、サーフェスが生成され、分割を行うことはない。同様に、そのサーフェスボクセルの四つの辺も、サーフェスにより分割されることはない。これは上述の如く、サーフェスボクセルであるならば、オブジェクトの一部がサーフェスボクセル内に含まれるとされるためである。よってサーフェスは、サーフェスボクセルを通って広がるものとされる。（若しくは、包括的な閾値設定では、上述の如く、オブジェクトの境界は、内部ボクセルの最も外側の層にあるものとする。このときオブジェクトの境界は、内部ボクセルを通って広がり、その他のボクセル境界上には接さない。
【００５６】
例えば、図５において、現在処理中のボクセルをサーフェスボクセルであるボクセル（１４）（i，j，k）とする。（ボクセル（１４）は内部隣接要素、即ち辺隣接要素（１６）及び２つの角隣接要素（２５）（７）を持つため）表７に定義される変数は、例えば、ボクセル（１４）に対して以下のように計算される。
【００５７】
2007528529.tif 000018
【００５８】
2007528529.tif 000019
【００５９】
以下に示す４つの条件は、ボクセル（１４）の面隣接要素（５）（i，j，k−1）、（２３）（i，j，k＋1）、（１１）（i，j＋1，k）、（１７）（i，j−1，k）に対応するものである。２つの面隣接要素、即ち（１３）（i−1，j，k）及び（１５）（i＋1，j，k）は、ｅｉ−とｅｉ＋の情報を（１４）と共有しない。（１３）と（１５）が（１４）と隣接する面は、ｉ軸方向と垂直であるため、（１３）と（１５）のｅｉ−及びｅｉ＋情報は、ボクセル（１４）の周囲３×３の隣接要素の外側にあるボクセルに対するものである。以下の４つの条件により、確実に（１４）と隣接する（５）（２３）（１１）（１７）からなるサーフェスが連続して（１４）と連結される。例えば、（５）の前面がサーフェスにより分割されると、以下の第１条件は、この情報を（１４）に伝達する。これにより、ボクセル（１４）の後方面もサーフェスにより分割される。
【００６０】
2007528529.tif 000020
【００６１】
2007528529.tif 000021
【００６２】
更に、次に示す４つの条件は、ボクセル（１４）の辺隣接要素（２）（i，j＋1，k−1）、（８）（i，j−1，k−1）、（２０）（i，j＋1，k＋1）、（２６）（i，j−1，k＋1）である。（１４）と共有する辺は、ｉ軸方向に平行であるためこのような座標値となる。（図１１は、辺に対して以下のように用語を付している。）辺（Ｄ）で（１４）と接する隣接要素（８）は、ｅｉ−値がTRUEの場合、この情報を（１４）のｆｉ−値と共有することが可能である。（８）のｅｊ＋値がTRUEの場合、ボクセル（５）が内部ボクセルであり、（８）の辺（Ｄ）はサーフェスにより分割されない。情報の共有は必要でないため、起こらない。同様に、（８）のｅｋ＋値がTRUEの場合、情報の共有は起こらない。
【００６３】
2007528529.tif 000022
【００６４】
2007528529.tif 000023
【００６５】
else；
上記の条件は、以下の一つの数式に集約することができる。
【００６６】
【数１】
2007528529.tif 000024
【００６７】
2007528529.tif 000025
【００６８】
【数２】
2007528529.tif 000026
【００６９】
【数３】
2007528529.tif 000027
【００７０】
【数４】
2007528529.tif 000028
【００７１】
【数５】
2007528529.tif 000029
【００７２】
【数６】
2007528529.tif 000030
【００７３】
2007528529.tif 000031
【００７４】
2007528529.tif 000032
【００７５】
【表８】
2007528529.tif 000033
【００７６】
後述する後処理が必要なケースを考慮せずに、考えられる全てのケースは下の表９のようにまとめることができる。
【００７７】
【表９】
2007528529.tif 000034
【００７８】
（表９続き）
2007528529.tif 000035
2007528529.tif 000036
2007528529.tif 000037
2007528529.tif 000038
2007528529.tif 000039
2007528529.tif 000040
2007528529.tif 000041
【００７９】
2007528529.tif 000042
【００８０】
2007528529.tif 000043
【００８１】
この技術を実行した結果の例を表１０に示す。
【００８２】
（表１０）
2007528529.tif 000044
2007528529.tif 000045
2007528529.tif 000046
2007528529.tif 000047
2007528529.tif 000048
2007528529.tif 000049
2007528529.tif 000050
2007528529.tif 000051
【００８３】
表１０の最後の列において、ボクセルを分割する各ケースに対応したサーフェス形状が定義される。添付書類２は、表１０に示す全てのケースに対するサーフェスの図解を提供する。
【００８４】
表１０に示す１０パターンのブーリーン変数を使用して、サーフェスボクセルからなるサーフェスの部分が構成される方法が決定される。例えば、図９のケース１−１の場合、εがＴＲＵＥ、fi-がＴＲＵＥのため、ボクセルからなるサーフェスの垂線は、ｉ＋方向要素のみを持つことがわかり、この辺をｉ方向に平行に切断する。図９は、三角形をどのように使用するかに関して解決策を提供する。一つの策は、サーフェスの一部分を三角形化することである。もう一つの策は、表９、図１０のケース２−１の場合、ε、fi-、fｊ-がＴＲＵＥであるため、ボクセルからなるサーフェスの垂線は、ｉ＋方向要素及びj＋方向要素のみを持つことがわかる。内部ボクセルと接する左面及び下面は、分割できない。よって、図１０に示すように、上面及び右面にわたって分割が行われる。
【００８５】
（４．後処理）
サーフェスボクセルに対して、fi−及びfｉ＋がともにＴＲＵＥである場合、若しくはfｊ−及びfｊ＋がともにＴＲＵＥである場合、若しくはfk−及びfｋ＋がともにＴＲＵＥである場合、そのサーフェスボクセルは不明瞭なボクセルと考えられる（図２に関連して上述）。これは、そのボクセルに対して現在利用可能な情報から、サーフェスがボクセルに大してどう形成されるかを決定することが出来ないことを示す。こういったボクセルに対しては、後処理を行えば、問題が解決する。図１２は、後処理が必要なケースを示す。ボクセル（５）、（１４）、（２３）は不明瞭である（これらのボクセルをポリゴン状サーフェスで分割して、一部のボクセルは内部ボクセル、一部は外部ボクセルと分けることはできない。）。両面（左側と右側）とも、サーフェスの「内部」にあると思われ、サーフェスの両側には「内部ボクセル」が隣接している。これは、図２に関連して記載されたグルーブ構造である。
【００８６】
表１１は、１、２、３、４の工程が完了した後の、ブーリーン変数の値の例を示す。このボクセルの例において、５、１４、２３、２、１１、２０は後処理が必要である。
【００８７】
（表１１）
2007528529.tif 000052
【００８８】
本発明の実施形態において、後処理は２つの方法で実施される。第１の方法は、再充填（re-filling）である。再充填により不明瞭なボクセルが内部ボクセルに変更される。図１３は、ボクセル（５）、（１４）、（２３）が内部ボクセルとマークされたときの変化を示す。この時、不明瞭なボクセルは出現しない。通常は、この機能を実施すると、ε値がTRUEである不明瞭なボクセルが再充填される。図１２に示す例では、ただ単にボクセル２、１１、２０を再充填するだけでは、問題は解決されない。ボクセルが再充填されると、再充填されたボクセルの周囲５×５×５の小さなボリュームを再度計算する必要がある。再充填されたボクセルが、隣接する２６の要素の変数の値に影響を及ぼすためである。
【００８９】
第２の方法は、細分割である。この方法は、図２の２Ｄのケースで紹介されている。具体的には、ボクセル（２３０）が細分割されて、ボクセル（２４１）及び（２６１）となる。細分割の基本的な概念としては、不明瞭なボクセルの周囲３×３×３のボリュームの各ボクセルが、８つの部分に等分割される。図１４は、図１２のボクセルの細分割の例を示す。細分割されたボクセルは全て、「親ボクセル」と同様の集中度を持つ。元のボクセルが外部ボクセルの場合、細分割後の８つの「子サブボクセル」は全て「外部サブボクセル」となる。細分割の後、非常に興味深い現象が起こる。図１２における不明瞭なボクセル（１４）は、８つの部分に分割される（図１４に示される如く、１４−１、１４−２、１４−３、１４−４、１４−５、１４−６、１４−７、１４−８となる）。図１４中、新しい６×６×６のボリュームが処理され、ボクセル１４−１に対するε値が計算されるときは、直接的な隣接要素のうち３つのみ（即ち、５−５、１１−３、１３−２）が考慮され、その他の３つ（１４−２、１４−３、１４−５）はその「兄弟関係」と考えられる。更に、ボクセル（１４−１）はｉ＋、ｊ＋、ｋ＋について面隣接要素及び辺隣接要素から共有される情報を得ることはない。これは、例えば、細分割の後、不明瞭なボクセルが現れないことを意味する。
【００９０】
例えば、数式２によると、ボクセル（１４−１）のｆｉ＋は、ｅｉ＋（１４−１）、ｅｉ＋（１４−３）、ｅｉ＋（１４−５）、ｅｉ＋（５−５）、ｅｉ＋（１１−３）、ｅｉ＋（５−７）、ｅｉ＋（２−７）、ｅｉ＋（１１−７）、ｅｉ＋（１４−７）により決定される。上述の数値は全て、常にＦＡＬＳＥである。なぜならその右側の直接的隣接要素は、「兄弟関係」（即ち、同一のボクセルから派生したボクセル）であるため、同じ集中度を持つ。ボクセル（１４−１）のｆｉ＋は、常にＦＡＬＳＥである。
図１４のボクセル（１４）に対する細分割の結果を表１２に示す。細分割されたボクセル（１４）の８個の子ボクセルのうち、不明瞭なものは残っていない。
【００９１】
（表１２）
2007528529.tif 000053
【００９２】
（５．頂点の位置）
幾何学的な点の位置の選択は、様々な方法で行われる。例えば、辺の中央に常に頂点を置いたり、辺に沿って頂点を移動させることにより、最終的なサーフェスの滑らかさが最大限に実現される。実施に利用可能なデータは、「内部」「外部」にセグメンテーションが行われるだけではない。このような分類を行うために使用される要素の値及び閾値レベルは（値及び閾値レベルが分類の根拠となる場合）、本発明の好適な実施形態において、要素値ｆと閾値Ｔによる。要素値ｆは、サンプルのように物理的な量の挿入された値とする。閾値Ｔはそれ以上になると、要素が「内部」と分類される値とする。（以下の説明は、ｆ及びＴの記号に代入される値を入れ替えることにより、全てのケースを網羅する。このとき「内部」とは「閾値以下」であることを意味する）。特に、これらの点は以下に説明するような位置をとる。
【００９３】
図１５に示される如く、サーフェスボクセル（８）の辺Ｄ上の点を選択する必要がある。明らかにボクセル（２）（５）（１１）は、サーフェスボクセルであって、ボクセル（８）と辺を共有する。要素における物理的な値の推定を行うときに、スキャンされた物理量の要素の平均が概算される。ほとんどの物理量の平均値は、Ｆdense＞Ｔの付近、若しくはＦlight＜Ｔの付近である。値が高いほど（平均ではＴより低くても）、Ｔ領域の内部にある要素が多いことを示す。よってサーフェスの分割は、要素が外部に接する面に近い場所で行われることになる。この概念は、辺と接する要素の値に重み付けした影響を与える等式に応用することができる。図１５に、ｉ方向の辺が外部ボクセルと共有のケースに対して式を適用した例が示される。
例示された等式は、データが二値で与えられるという有利な点を持ち（スカラー値から決まるのではなく、インプット時に、各要素につき「内部」か「外部」かの2つに決める）、自然な閾値Ｔは利用できない。更に、以下に等式を示す。
【００９４】
【数７】
2007528529.tif 000054
【００９５】
【数８】
2007528529.tif 000055
【００９６】
【数９】
2007528529.tif 000056
【００９７】
【数１０】
2007528529.tif 000057
【００９８】
【数１１】
2007528529.tif 000058
【００９９】
2007528529.tif 000059
【０１００】
もう一つの挿入値に対する方法として、例えば、閾値Ｔを使用して挿入値を演算する方法がある。それを行う前に、内部に隣接する要素が特定されなければならない。図１５の例において、ボクセル３、６、９、１２は内部ボクセルとし、挿入は以下に示すようになる。
【０１０１】
【数１２】
2007528529.tif 000060
【０１０２】
【数１３】
2007528529.tif 000061
【０１０３】
【数１４】
2007528529.tif 000062
【０１０４】
【数１５】
2007528529.tif 000063
【０１０５】
【数１６】
2007528529.tif 000064
【０１０６】
2007528529.tif 000065
【０１０７】
上述の如く、細分割が実行される際、全ての辺は２つの辺に分割される。ある一つの辺を共有する全てのボクセルが不明瞭なボクセルである場合、その辺上に２つの交差点がある可能性がある。その他のケースでは、常に交差点の数は１つのみである。例えば、図１２において、ボクセル（１１）の辺Ｃ（図１１の辺の定義に準ずる）はサーフェスと交差する点が２つある。細分割の後、図１４において、ボクセル（１１）の辺Ｃは２つの部分に分割されて、ボクセル（１１−７）及び（１１−８）それぞれの辺Ｃとなる。本発明の実施形態において、これら二つの交差点は上述の方法により演算されてもよい。しかし、ボクセル（１１）の辺Ａに対しては、ボクセル（１０）が不明瞭なボクセルではないため、交差点は一つだけである。ボクセル（１０）が処理されると、ボクセル（１０）の辺Ｂ上の一つの交差点が演算される。ボクセル（１１）が処理されると、図１４に示されるように細分割された、ボクセル（１１−７）の辺Ａ上の交差点が演算される。これらの二つの点は同一ではないが、その辺上には交差点は一つだけである。サーフェスが辺を二回交差させると、結果的に多くの穴が現れる。２つの交差点を１つにする処理を使用する方法は幾つかある。第一の方法として、平均の点を演算する。第二に、細分割時の演算のみを続行する。最後に、細分割なしのときの演算を続行する。最後の方法は、本発明の好適な実施形態において実行され、例えば、サーフェスの滑らかさが維持される。図１４の曲線は、最後の方法を実行した結果を示す。
【０１０８】
（サーフェスの例）
図１６乃至４１は本発明の様々な実施形態により生成される様々なサーフェスを示す。
図１６乃至２９はメッシュリダクションを一切実行せずに生成されたサーフェスの例を示す。サーフェスは、３Ｄ双方向データディスプレイシステム内の本発明の実施形態におけるスクリーンショットで示される。ここではRadioDexter（登録商標）ソフトウェアを起動するDextroscope（登録商標）を使用する。両製品とも、シンガポールのVolume Interaction Pte Ltd社の製品である。よって図１６乃至図２９内のサーフェスの左上に表示されたポリゴンの数は、多い。
【０１０９】
図１６は、部分的に拡大したサーフェス（ソリッド・モード）及びその関連ボリュームを示す。図１７は、図１６のサーフェスをワイヤフレーム・モードで部分的に拡大したものである。図１８は、サーフェス全体（ソリッド・モード）及びその関連ボリュームを示す。図１９は、図１７のサーフェスをワイヤフレーム・モードで示したものである。図２０は、図１８のサーフェス全体の後面をソリッド・モードで示したものである。図２１は、図２０のサーフェスをワイヤフレーム・モードで示したものである。図２２は図２０のサーフェスの前面をワイヤフレーム・モード及びフル前面ビューで示したものである。図２３は、図２２をソリッド・モードでレンダリングしたものである。
【０１１０】
図２４は、ワイヤフレーム・モードにおける標準のサーフェス（図２３等で多く確認される）を示す。図２５はソリッド・モードにおける同一のサーフェスを示す。図２６は、関連ボリューム（スキャンデータからセグメント化されたオブジェクト）を備えた同様の標準のサーフェスを示す。図２８は、ワイヤフレーム・モードで表示されたサーフェスのメッシュに、元のインプットボリュームを比較のために重ね合わせた様子を示す。本発明の実施形態において（限定的な閾値設定でも包括的な閾値設定でも）、適切に選択された閾値に対して、また本発明の方法の適切な実施に対して、生成されたメッシュ・サーフェスは、幾何学的にかなり正確である。表１３に関連して記載したように、ボリューム測定に関連して以下に記載される。図２９は、ソリッド・モードにおける同様の比較を示す。
【０１１１】
図３０乃至図３８は、以下に示すように、メッシュリダクションアルゴリズムを用いて生成されたサーフェスを示す。このようにして、ポリゴンの総数は、図の左上に表示されるように、元のメッシュサーフェスのおよそ３分の１から１０分の１に減少される。
図３０は、ソリッド・モード・レンダリングにおける図２２のサーフェスの前頭部を示す。図３１は、図２２と同様の画像であるが、ポリゴン数が大幅に減少されている。図３２は図２２と同様のサーフェスを示し、非常に良く似ているが、ポリゴン数が大幅に減少され、２８２３９６個から２６５７７個へと９割以上も減少されている。図３３は、図３２のサーフェスをソリッド・モードでレンダリングした様子を示す。図３４は、図２４の標準サーフェスのワイヤフレーム・モードでレンダリングした様子を示し、ポリゴン数は６２３５個から１６１１個へと減少している。図３５及び図３６は、元のボリュームデータに並べて表示した標準サーフェスのワイヤフレーム・モード及びソリッドモードでのレンダリングを示す。図３７は、図３４の標準サーフェスをソリッド・モードで示し、図３８は図３７の拡大（即ちズーム）したバージョンである。
【０１１２】
図３９乃至図４１は、細分割を示す。図３９は、ソリッドモードでのサーフェス全体を示し、２つの細分割エリアが示されている。一方の細分割エリアは、髪のライン上若しくはその付近の左目にかけてである（細分割エリア１）。もう一方は左の頬骨の上付近にかけてである（細分割エリア２）。図４０及び図４１はそれぞれ、細分割エリア１及び２の詳細を示したものであって、図２の要素（２４１）の３Ｄ版にあたる。図４０及び図４１は、高倍率で表示されたものであって、メッシュ一つ一つの三角形がはっきりと表示されている。
【０１１３】
図４２は、図２３のサーフェスの別の画像である。
図１６乃至図４１に関連して見られるように、本発明の実施形態により生成されたサーフェスは、ソリッドサーフェスとして表示される。サーフェスを構成する各ポリゴンは、ソリッドな３Ｄサーフェスを生成するように充填される。このサーフェスは、「ワイヤーフレーム」サーフェスとして表示され、サーフェス全体を構成するポリゴン状サーフェスの辺のみが表示される。
【０１１４】
上述のように、複雑性を最小化するために、メッシュリダクションを使用して、サーフェスの表示に要求されるポリゴン数を減少できる。メッシュリダクションは、既知の技術により実施可能である。更に、例えば、メッシュリダクションは、以下の技術を使用して実施可能である。
【０１１５】
（メッシュ・リダクション）
発明者により実施された実験によると、２５６×２５６×２５６のＣＴデータ集合に対して、本発明の手法により生成されたメッシュサーフェスは２０万以上の三角形を有する。従って、このようなメッシュオブジェクトを使用しながら即時的なユーザ・インタラクションを実現することは難しい。なぜなら三角形の数が多く、且つオブジェクトを即時的にレンダリングするのに必要なコンピュータ処理能力が要求されるためである。そこで、本発明の実施形態においては、三角形の数は低いレベルに抑えることが可能である。しかしながら、三角形の数が減少されると、精度が若干失われることがある。よって、メッシュリダクションを実行する際は、精度の劣化を最小限に抑えることが重要となる。本発明の実施形態において、メッシュリダクションは、以下のように実行される。
【０１１６】
（サーフェスの平滑化）
本発明の実施形態により、ボクセル分割により生成されたサーフェスは、サーフェス内に全ての内部ボクセルを含むように試行される。結果的に、サーフェスは輪郭がややギザギザになる。図４２に示される如く、結果はデジタル処理をしたような形状になる。三角形をより減少させるためには、サーフェスの平滑化を行ったほうがよい。
【０１１７】
実施形態において、以下の定義が使用される。
隣接要素：頂点ａ（ｘａ、ｙａ、ｚａ）に対して、頂点ｉ（ｘｉ、ｙｉ、ｚｉ）は頂点ａ（ｘａ、ｙａ、ｚａ）の隣接要素を示す。但し、直線ａｉがサーフェスの一又は複数の三角形の辺である場合に限る。
隣接要素の数、NumOfNei（ｉ）：頂点ｉの隣接要素の数。
隣接する三角形：頂点ａ（ｘａ、ｙａ、ｚａ）が、三角形Tri（ｊ）の頂点の場合、Tri（ｊ）はａの隣接する三角形である。
隣接する三角形の数、NumOfNeiTri（ｉ）：頂点ｉの隣接する三角形の数。
サーフェスボクセル、sv（ｉ）：NumOfNeiTri（ｉ）＝NumOfNei（ｉ）の場合、頂点ｉは、サーフェス頂点として定義される。
境界上の頂点、bv（ｉ）：NumOfNeiTri(ｉ)≠NumOfNei（ｉ）の場合、頂点ｉはサーフェス頂点と定義される。
境界上の頂点の隣接要素、NumOfBNei（ｉ）：境界上の頂点に対しては、隣接要素の中で、境界と隣接する要素の数として定義される。図４８において、頂点ａ、ｂ、ｃは境界上の頂点である。頂点ｂ及びｃは、頂点ａの境界上の頂点の隣接要素である。
【０１１８】
本発明の実施形態において、サーフェスボクセルｓｖ（ａ）の新しい座標（ｘnew、ｙnew、ｚnew）は、元の座標及びその隣接要素の座標により平滑化される。
【０１１９】
2007528529.tif 000066
【０１２０】
同様に、本発明の実施形態により、境界ボクセルbv（ａ）の新しい座標（ｘnew、ｙnew、ｚnew）は、元の座標及びその境界に隣接する要素の座標により平滑化される。
【０１２１】
2007528529.tif 000067
【０１２２】
平滑化プロセスを増やすと、三角形の数が減少される一方で、精度が更に失われる結果を招く。よって、本発明の実施形態において、平滑化プロセスが行われる回数と、維持されるべき精度のバランスが図られる。発明者により実施された実験によると、平滑化プロセスが２回行われたときに、適当な結果が得られる。通常、コンピューティング資源及び要求される精度に応じて、任意の実施形態において行われる平滑化プロセスの数が決定される。
【０１２３】
多くの場合において、この平滑化プロセスは幾つかのサーフェスボクセル内の頂点の位置を変更させるため、それほど精度は失われない。図４３に示される如く、頂点ａはサーフェスボクセル１、２、３、４内を移動する。
【０１２４】
（２）２頂点の結合
図４４は、本発明の実施形態による２頂点の結合を示す。図４４の三角形１乃至５は、３Ｄ空間において共通の垂直ベクトルを持つと仮定する。つまり、５つの三角形は同じ平面にあるとするとき、頂点ａを頂点ｂの場所へ移動させると、５つの三角形が３つの三角形３、４、５に置き換えられる。しかしこれは常に起こるとは限らない。頂点を新しい位置に移動させることは、場合によっては、期待されない結果を引き起こす。例えば、図４５において、頂点ａをｂに移動させた後、三角形５の垂直ベクトルが反転し、三角形５及び三角形４の間にはオーバーレイ（overlay）が形成される。
【０１２５】
通常、頂点の周囲の三角形は、同じ平面上にはない。三角形の平面上のどの性質をもって、頂点移動を行う正当性の指標として、考慮するかを決めることが望ましい。本発明の実施形態において、例えば、三角形により異なる垂直方向ベクトルの差異が、指標として用いられる。垂直方向ベクトルの差異とは、２つの三角形の垂直ベクトルの角度の差で表される。図４４において、三角形１及び２の領域が、三角形３、４、５の領域で占有される様子が示される。よって、三角形３、４、５の垂直ベクトルは、三角形１、２の垂直ベクトルから大幅に逸れていないことが重要である。ここで閾値Ｔangleを定める。垂直ベクトルの角度の差異がＴangleよりも大きい場合、説明した頂点移動は行うべきではない。
【０１２６】
垂直ベクトルの反転が起こらないように、図４５に示すように、実施形態において、角度が変化した垂直ベクトルが計算されると同時に、垂直ベクトルの間の角度及びその付近の三角形も同時に計算される。計算される角度の何れかが、９０°以上である場合、説明した頂点移動は行うべきではない。
【０１２７】
頂点移動のプロセスにおいて、図４６の例に示すような鋭角三角形が生成されるのを避けることが重要である。鋭角三角形はボリュームレンダリング及び変形モデリングに問題を引き起こす可能性がある。本発明の実施形態においては、１０°以下の角度を一つ有する三角形を「鋭角三角形」と定義する。
【０１２８】
図４７に示されたケースに対して、頂点ａがその隣接要素（頂点ｂ）に移動可能であるかを検定するプロセスは以下のステップで実施できる。
（ａ）同一平面テスト
図４７（１）の全ての三角形に対して、垂直ベクトルNormal（ｉ）を計算する。
垂直ベクトルNormal（１）及びNormal（２）の間の角度のAngleBetween（１，２）を計算する。
【０１２９】
2007528529.tif 000068
【０１３０】
2007528529.tif 000069
【０１３１】
（ｂ）鋭角三角形テスト
三角形が鋭角三角形となるのを避けるには、除外されたものを除いて、頂点ａのまわりにある全ての三角形について、検査を行うべきである。頂点ａが頂点ｂに移動されると仮定すると、三角形の３つの頂点のうち１つは、頂点ａから頂点ｂに変更されるため、三角形３、４、５の３つの角度が計算される。角度の何れかが、ユーザに定義された閾値（例えば、１０°）以下であるならば、この移動は行わないほうがよい。
【０１３２】
（ｃ）垂直方向の反転テスト
頂点ａが頂点ｂに移動すると仮定すると、図４７（２）に示される如く、垂直方向の反転テストを行うには、除外されたものを除いて、頂点ａのまわりにある全ての三角形について検査を行うべきである。図４７（２）において、三角形３、４、５が検査されなければならない。三角形３、４、５の中の全ての三角形に対して、三角形及び三角形の辺隣接要素の間の垂直方向のベクトルの角度が計算されなければならない。
三角形（３）に対して、
【０１３３】
2007528529.tif 000070
【０１３４】
2007528529.tif 000071
上述した頂点移動に関して上記のテストを全てクリアした場合、本発明の実施形態において、この頂点は対応する隣接要素に移動可能である。
【０１３５】
（ｄ）境界頂点
境界頂点は、境界頂点の隣接要素に移動可能である。図４８において、頂点ａは境界頂点の隣接要素ｂ又はｃのみに移動可能である。同様に、サーフェス頂点に関係して説明した同一平面テスト、鋭角三角形テスト、及び垂直反転テストを、例えば、境界頂点移動にも適用可能である。また、実施形態において、境界頂点移動に適用されるテストがもう１つある。「辺角度テスト」である。図４８において、頂点ａは頂点ｂに移動されるとする。三角形４の領域は、三角形１、２、３により占有される。頂点ａ、ｂ、ｃが同一線上にあり、三角形１乃至４が同一平面上に配列ば、この頂点移動を実行しても、精度を失うことはない。
【０１３６】
（ｅ）辺角度テスト
２つの境界辺の間の角度を計算する。角度がユーザ定義された閾値を越える場合、この頂点移動は行わないほうが良い。
【０１３７】
（ｆ）細分割により生成された頂点の移動
データに現れるある小規模な特徴（small feature）が、不要なものである可能性もある。これらの小規模な特徴の通常の大きさは、１ボクセル又は複数のボクセル単位分である。通常は、これらの特性はノイズやデジタル処理により引き起こされる。この種類の小規模な特徴は通常、細分割プロセスにより引き起こされる。このような小規模な特徴を取り除くには、細分割後により生成された頂点を除外しなければならない。このプロセスは、メッシュリダクション法の初期に実施可能である。
【０１３８】
本発明の実施形態において、基準値が定義され、例えば、どの特徴を排除するべきであるかが決定される。この段階は、一つのグループ内の細分割後の頂点の数により実施される。細分割された頂点のグループは、細分割による最大可能な数の頂点として定義される。その頂点の隣接要素は、このグループ内にある隣接要素を除けば、サーフェス頂点のみである。図４９及び図５０に、細分割後の頂点の例を示す。図４９は、本発明の実施形態により生成された、患者の頭部の皮膚の一部を示すサーフェスのスクリーン・ショットの一例である。図中の線は、幾つかの細分割後の頂点を含む領域を指す。図に示される如く、この領域に、サーフェスに小規模な特徴が生じる。図５０は、サーフェスの細分割された部分の拡大図を、ワイヤーフレーム・モードで示す。
【０１３９】
本発明の実施形態において、細分割により生成される頂点を取り除くプロセスの例は、以下のように説明される。グループ内の細分割により生成された全ての頂点に対して、隣接要素（サーフェス頂点となる）の中の一要素へ移動を行う。
【０１４０】
上記のプロセスは、グループ内の細分割された全ての頂点が取り除かれるまで、繰り返される。図５１はこのプロセスの一例を示す。頂点ａ、ｂ、ｅ、ｉ、ｋ、ｍは全て細分割により生成された頂点である。ユーザ定義された小規模な特徴の閾値が、例えば６以上である場合、その頂点は取り除かれなければならない。図５２は、頂点をａからｄ（隣接するサーフェス頂点）に移動させるプロセスの第一段階を示す。同様のプロセスは、細分割されたその他の頂点にも適用可能である。図５１に示すように、頂点ｉは元々隣接するサーフェス頂点をもたない。しかし頂点ａが頂点ｄに移動した後は、図５２に示される如く、頂点ｄは頂点ｉの隣接するサーフェス頂点となる。
【０１４１】
（ｇ）特殊ケース
通常、サーフェス頂点は、サーフェスに隣接要素と、２つの異なる隣接頂点を共有する。しかし、それには例外が存在する。図５３には、例えば、頂点ａは、３つの隣接要素（ｇ、ｃ、ｅ）とサーフェス隣接要素ｂを共有する。頂点ａが頂点ｄに移動した場合、幾つかの期待されない結果が生じる。例えば、図５３の下側の図において、頂点ａを頂点ｄに移動した結果が示されている。頂点ｂは５つの隣接する頂点ｃ、ｄ、ｅ、ｆ、ｇを持つ。しかし頂点ｂは周囲に６個の三角形を持つ。三角形１、４、５、６、７、８である。このケースは、サーフェス頂点に対しては起こらない。
【０１４２】
通常は、境界頂点は隣接要素として２つの境界頂点を持つだけである。しかし図５４では例外が示されている。頂点ａは３つの境界上にある頂点隣接要素を持つ。これでは、境界上の頂点に関する上述のアルゴリズムで混乱を引き起こす。
【０１４３】
このような特殊ケースを除くために、本発明の実施形態において、共有する頂点の数の検査は以下のように実施されてもよい。
１．（サーフェス頂点ａをサーフェス頂点ｂに移動させる。サーフェス頂点ａは三角形（２）と２つの頂点をサーフェス頂点ｂと共有しなければならない。
２．境界頂点ａを境界頂点ｂに移動させる。境界頂点ａは三角形（２）と２つの頂点をサーフェス頂点ｂと共有しなければならない。
【０１４４】
（ホール・クロージング及びボリューム測定）
上述の本発明の実施形態の方法では、元のデータにホールがなければ、メッシュサーフェスにもホールは全く形成されない。しかし、時々元のデータがクロップされたとき、クロップ境界上にホールが生じる可能性がある。本発明の実施形態により生成されたサーフェスが元のデータのボリューム測定に使用される場合は、ホールを閉じておくことが必要となる。
【０１４５】
本発明の実施形態により生成された三角形メッシュでホールを閉じるために２つの方法が使用できる。
（１）第１の方法として、クロップボックス周囲のクロップされるデータに６つの空白のスライス画像を加える。本発明の方法を新しいデータ（即ち、クロップされるデータ及びその周囲の６枚の空白のスライス画像）に適用して、メッシュサーフェスを生成し、結果的な三角形メッシュを完全に閉じる。
但し、この方法には幾つか特別な使用法を備えるかもしれない。６つの空白のスライス画像からの三角形は特別な目的のために使用される。例えば、メッシュサーフェスにより囲まれた体積の計算に使用可能である。その三角形を表示させないことも可能である。この三角形を使用して、外側の表面のみを表示させたい場合、メッシュリダクションでは難しい内部構造の消去も可能である。
【０１４６】
（２）第２のアルゴリズムとして、ホールを検出し、検出したホールを閉じる。ホールがクロップ境界によるものである場合、ホールは境界上に位置する。そのホールは２Ｄポリゴンで構成される。２Ｄポリゴンを三角形化し、生成された三角形をメッシュオブジェクトに加えることで、ホールを消去できる。
【０１４７】
図５５は、球の例を示す。この球はＣＴで疑似オブジェクトのスキャンを行い、そのスキャン画像をセグメント化することにより、得られる。スキャンされたオブジェクトは、ポール上に載せられた球であるため、球をセグメント化すると、結果的にポールが球に接している部分が、立体オブジェクトのサーフェスにあるホールにあたる。
【０１４８】
図５６は、本発明の実施形態により生成されたオブジェクトのメッシュサーフェスを示す（クロップ・ボックス内に示される）。三角形メッシュ内にはホールがある。図５７は、上述のホール・クロージングアルゴリズムにより処理された後のメッシュサーフェスをソリッド・モード及び拡大図で示す。
【０１４９】
図５８乃至図６０はそれぞれ、スキャンデータからセグメント化された疑似立方体オブジェクト、及び同一のオブジェクトをソリッド・モードで表示したメッシュサーフェス（底部にホールがある）、及びホール・クロージング処理が行われた後のメッシュサーフェスを示す。（尚、メッシュデータは本発明の方法により生成されたものである。）最後に、同じデータを使用して、図６１乃至図６３はそれぞれ、ＭＲスキャンデータからセグメント化された腫瘍、及び同一のオブジェクトをソリッド・モードで示したメッシュ・サーフェス（底部にホールがある）、及びホール・クロージング処理が行われた後の同一のメッシュ・サーフェスを示す。（尚、メッシュ・サーフェスは本発明の方法により生成されたものである。ホール・クロージングは本発明の方法により実施される）
【０１５０】
ホール・クロージングが適用されると、閉じたメッシュ・サーフェスの体積は、既知の技術を使用して計算可能である。表１３は、このオブジェクトに対して体積計測を行った結果を示したものである。
【０１５１】
（表１３）
2007528529.tif 000072
【０１５２】
表１３に関して、腫瘍については、体積がスキャンデータから計算されたため、実際に計測可能な腫瘍はなかった。表に示すように、スキャンされたオブジェクトから生成された閉じたメッシュ・サーフェスの体積は、単純にセグメント化を行っただけのオブジェクトの体積よりも明らかに精度が高い。これは、限定的な閾値設定のために、セグメント化されたオブジェクトは、実際のオブジェクト並びにセグメント化されたオブジェクトの（本発明の実施形態による）メッシュ・サーフェスよりもサイズが小さいものと思われる。疑似オブジェクトに対する体積計測より、メッシュ・サーフェスは幾何学的に正確であることが示される。これにより図６１乃至図６３の腫瘍のような医療画像からしか識別されない、オブジェクトに対する補修されたメッシュ・サーフェスの体積でも、確実に正確と見なすことができる。
【０１５３】
（擬似コード）
本発明による実施形態による擬似コードでは、指針として以下の擬似コードを使用して実施可能である。それには、コーディング技法、コード言語、及びコンパイラなどを使用する。本発明による実施形態の方法では、３次元及び体積データ集合を記憶、処理、表示できるよう設定されたシステムならば何を使用しても実施できる。該システムの例としては、Volume  Interactions  Pte  Ltd  of  Singapore社によるDextroscope（登録商標）ハードウェア、RadioDexter（登録商標）ソフトウェアなどが挙げられる。
【０１５４】
2007528529.tif 000073
【０１５５】
2007528529.tif 000074
【０１５６】
２．擬似コードの詳細
Ａ．推定及びデータ構造の定義
図６４は、ボリュームオブジェクトに対する推定及び配向の定義を示す。
【０１５７】
2007528529.tif 000075
【０１５８】
2007528529.tif 000076
【０１５９】
Ｂ．アルゴリズムの例
2007528529.tif 000077
【０１６０】
2007528529.tif 000078
【０１６１】
2007528529.tif 000079
【０１６２】
2007528529.tif 000080
【０１６３】
2007528529.tif 000081
【０１６４】
2007528529.tif 000082
【０１６５】
2007528529.tif 000083
【０１６６】
2007528529.tif 000084
【０１６７】
2007528529.tif 000085
【０１６８】
2007528529.tif 000086
【０１６９】
2007528529.tif 000087
【０１７０】
2007528529.tif 000088
【０１７１】
2007528529.tif 000089
【０１７２】
2007528529.tif 000090
【０１７３】
2007528529.tif 000091
【０１７４】
2007528529.tif 000092
【０１７５】
STEP９
ステップ７の結果をグループ化して、オブジェクトのサーフェスを生成する。
【０１７６】
2007528529.tif 000093
【０１７７】
2007528529.tif 000094
【０１７８】
2007528529.tif 000095
【０１７９】
2007528529.tif 000096
【０１８０】
（システムの例）
本発明はデ  ータ・プロセッサのソフトウェア上で、若しくは１又は複数の専用チップ中のハードウェア上で、若しくはそれらの組み合わせで実施可能である。システムの例としては、立体ディスプレイ、データ・プロセッサ、１又は複数のインターフェース（該インターフェースには双方向性ディスプレイ制御コマンド及び機能を備える）、１又は複数のメモリ又は記憶装置、及び画像プロセッサ及び関連システムが挙げられる。例えば、Volume Interactions Pte Ltd of Singapore社製品のDextroscope（登録商標）システム及びDextrobeam（登録商標）システムが挙げられる。これらのシステムは、Radio Dexter software又はその類似品か機能的に同一な３Ｄデータ集合双方向ディスプレイシステムを起動する。またこれらのシステムを使用すれば、本発明の方法が容易に実施できる。
【０１８１】
本発明の実施形態は、適切なデータプロセッサにより実行される命令のモジュラー・ソフトウェア・プログラムとして実施可能である。データプロセッサは本発明の実施形態を好適に実施するための既知のものである。ソフトウェアプログラムを、例えば、ハード・ドライブ、フラッシュ・メモリ、メモリ・スティック、光学記憶メディア、その他の当該技術分野で既知のデータ記憶装置上に格納してもよい。このようなプログラムが適切なデータプロセッサのＣＰＵによりアクセスされて起動すれば、本発明の実施形態における、３Ｄデータディスプレイシステムにおいて、３Ｄコンピュータモデル又は管腔状構造のモデルを表示する上記の手法を実施することができる。
【０１８２】
本発明は、１又は複数の実施形態に関して記載されたものであるが、その記載内容に限定されるものではない。また、本発明に係る請求の範囲は特別な形態や開示した発明の変異のみを含むものではない。また本発明の精神から逸脱しない範囲で当業者により考案された事項も含むものとする。
【０１８３】
本願には３つの付属書類が添付されている。これらの付属書類は、サーフェスボクセルに関して考えられる形態を説明している。これらの付属書類では、必然的に、ボクセルのケースごとに適切な隣接情報ベクトルを図で表している。３つの付属書類はそれぞれ、ボクセルの隣接要素（付属書類１）、ボクセルを分割するポリゴン状サーフェスの形状及び方向（付属書類２）、及び様々なボクセルの隣接要素の形態に対するその両者の組み合わせ（付属書類３）を説明している。図に添えられた文章を同時に参照することで、有用なケース・ベクトルの情報を簡潔に得ることができる。方式的な事項として、付属書類が拒絶されれば、出願人は付属書類の内容を分割して、図面及び文章中に盛り込む権利を有しており、明細書を補正し、新たな図面を出願に含めることができる。新たな図面には添付書類に含まれる説明を備える。またこの図面を明細書の文章中に含めることもできる。しかしながら出願人は、付属書類が最も効率的且つ明確な説明を提供するため、これらが受理されることを望む。
【図面の簡単な説明】
【０１８４】
【図１】円により囲まれた２次元領域の例であって、単純にグリッド点に囲まれた領域をカウントすると、１０％の誤測定が含まれる。
【図２】本発明の実施形態による、２次元サーフェスのインデンテーション（ギザギザ）とボクセルサーフェス付近の細分割を示す。
【図３】本発明の実施形態によるプロセスのフロー図を示す。
【図４Ａ】３Ｄデータ集合の例と１ボクセル周囲の２６個の隣接要素を示す。
【図４Ｂ】図４Ａのボクセルの６つの直接的隣接要素を示す。
【図５】本発明の実施形態による内部ボクセルの例を示す。
【図６】２次元でのポイント集合「内部」の概念を示す。
【図７】本発明の実施形態による２次元でのパターンの例を示す。このパターンに基づいて境界要素の候補は集合の内部及び外部の隣接要素を有してもよい。その隣接要素に対してサーフェスが生成されることになる。
【図８】２次元及び３次元の両方での正方形側面の表記の例を示す。その実施例として、隣接ピクセル又はボクセルの特定パターンに対応する境界を部分的に特定する様子を示す。
【図９】本発明の実施形態による、サーフェスボクセル分割の例を示す。ボクセルの左側の直接的隣接要素がセグメント内部にある様子を示す。
【図１０】本発明の実施形態による、サーフェスボクセル分割の例を示す。ボクセルの左側の直接的隣接要素及び下方の直接的隣接要素はそれぞれ、セグメント内部にあることを示す。
【図１１】本発明の実施形態による、１ボクセルに対する辺の表記を示す。
【図１２】本発明の実施形態による、３Ｄでのボクセルサーフェスの「グルーブ」構造を示す。
【図１３】本発明の実施形態による、図１２の「グルーブ」構造を再充填する様子を示す。
【図１４】本発明の実施形態による、細分割を示す。
【図１５】本発明の実施形態によるインターポーレーションを示す。
【図１６】本発明の実施形態により生成されたサーフェスの例を示す。
【図１７】本発明の実施形態により生成されたサーフェスの例を示す。
【図１８】本発明の実施形態により生成されたサーフェスの例を示す。
【図１９】本発明の実施形態により生成されたサーフェスの例を示す。
【図２０】本発明の実施形態により生成されたサーフェスの例を示す。
【図２１】本発明の実施形態により生成されたサーフェスの例を示す。
【図２２】本発明の実施形態により生成されたサーフェスの例を示す。
【図２３】本発明の実施形態により生成されたサーフェスの例を示す。
【図２４】本発明の実施形態により生成されたサーフェスの例を示す。
【図２５】本発明の実施形態により生成されたサーフェスの例を示す。
【図２６】本発明の実施形態により生成されたサーフェスの例を示す。
【図２７】本発明の実施形態により生成されたサーフェスの例を示す。
【図２８】本発明の実施形態により生成されたサーフェスの例を示す。
【図２９】本発明の実施形態により生成されたサーフェスの例を示す。
【図３０】本発明の実施形態により生成されたサーフェスの例を示す。
【図３１】本発明の実施形態により生成されたサーフェスの例を示す。
【図３２】本発明の実施形態により生成されたサーフェスの例を示す。
【図３３】本発明の実施形態により生成されたサーフェスの例を示す。
【図３４】本発明の実施形態により生成されたサーフェスの例を示す。
【図３５】本発明の実施形態により生成されたサーフェスの例を示す。
【図３６】本発明の実施形態により生成されたサーフェスの例を示す。
【図３７】本発明の実施形態により生成されたサーフェスの例を示す。
【図３８】本発明の実施形態により生成されたサーフェスの例を示す。
【図３９】本発明の実施形態により生成されたサーフェスの例を示す。
【図４０】本発明の実施形態により生成されたサーフェスの例を示す。
【図４１】本発明の実施形態により生成されたサーフェスの例を示す。
【図４２】本発明の実施形態によりメッシュリダクションを行わずに生成されたソリッド・モードで表示したサーフェスを示す。
【図４３】本発明の実施形態によるサーフェスボクセル内の頂点を示す。
【図４４】本発明の実施形態による頂点結合を示す。
【図４５】本発明の実施形態による提案された頂点結合の結果として、三角形に対する垂直ベクトルの反転を示す。
【図４６】本発明の実施形態による「鋭角」三角形を示す。
【図４７】本発明の実施形態による２つの隣接した頂点の結合を示す。
【図４８】本発明の実施形態による境界頂点の例を示す。
【図４９】本発明の実施形態によるサーフェスの細分割された領域を示す。
【図５０】本発明の実施形態によるサーフェスの細分割された領域を示す。
【図５１】本発明の実施形態による細分割により生成された頂点移動を示す。
【図５２】本発明の実施形態による細分割により生成された頂点移動を示す。
【図５３】本発明の実施形態によるメッシュ・リダクションで考えられる特定のケースを示す。
【図５４】本発明の実施形態によるメッシュ・リダクションで考えられる特定のケースを示す。
【図５５】本発明の実施形態によるホール・クロージング及びボリューム測定を示す。
【図５６】本発明の実施形態によるホール・クロージング及びボリューム測定を示す。
【図５７】本発明の実施形態によるホール・クロージング及びボリューム測定を示す。
【図５８】本発明の実施形態によるホール・クロージング及びボリューム測定を示す。
【図５９】本発明の実施形態によるホール・クロージング及びボリューム測定を示す。
【図６０】本発明の実施形態によるホール・クロージング及びボリューム測定を示す。
【図６１】本発明の実施形態によるホール・クロージング及びボリューム測定を示す。
【図６２】本発明の実施形態によるホール・クロージング及びボリューム測定を示す。
【図６３】本発明の実施形態によるホール・クロージング及びボリューム測定を示す。
【図６４】本発明の実施形態による擬似コードの詳細に対する配向の定義を示す。
【図１】
2007528529.tif 000097
【図２】
2007528529.tif 000098
【図３】
2007528529.tif 000099
【図４Ａ】
2007528529.tif 000100
【図４Ｂ】
2007528529.tif 000101
【図５】
2007528529.tif 000102
【図６】
2007528529.tif 000103
【図７】
2007528529.tif 000104
【図８】
2007528529.tif 000105
【図９】
2007528529.tif 000106
【図１０】
2007528529.tif 000107
【図１１】
2007528529.tif 000108
【図１２】
2007528529.tif 000109
【図１３】
2007528529.tif 000110
【図１４】
2007528529.tif 000111
【図１５】
2007528529.tif 000112
【図１６】
2007528529.tif 000113
【図１７】
2007528529.tif 000114
【図１８】
2007528529.tif 000115
【図１９】
2007528529.tif 000116
【図２０】
2007528529.tif 000117
【図２１】
2007528529.tif 000118
【図２２】
2007528529.tif 000119
【図２３】
2007528529.tif 000120
【図２４】
2007528529.tif 000121
【図２５】
2007528529.tif 000122
【図２６】
2007528529.tif 000123
【図２７】
2007528529.tif 000124
【図２８】
2007528529.tif 000125
【図２９】
2007528529.tif 000126
【図３０】
2007528529.tif 000127
【図３１】
2007528529.tif 000128
【図３２】
2007528529.tif 000129
【図３３】
2007528529.tif 000130
【図３４】
2007528529.tif 000131
【図３５】
2007528529.tif 000132
【図３６】
2007528529.tif 000133
【図３７】
2007528529.tif 000134
【図３８】
2007528529.tif 000135
【図３９】
2007528529.tif 000136
【図４０】
2007528529.tif 000137
【図４１】
2007528529.tif 000138
【図４２】
2007528529.tif 000139
【図４３】
2007528529.tif 000140
【図４４】
2007528529.tif 000141
【図４５】
2007528529.tif 000142
【図４６】
2007528529.tif 000143
【図４７】
2007528529.tif 000144
【図４８】
2007528529.tif 000145
【図４９】
2007528529.tif 000146
【図５０】
2007528529.tif 000147
【図５１】
2007528529.tif 000148
【図５２】
2007528529.tif 000149
【図５３】
2007528529.tif 000150
【図５４】
2007528529.tif 000151
【図５５】
2007528529.tif 000152
【図５６】
2007528529.tif 000153
【図５７】
2007528529.tif 000154
【図５８】
2007528529.tif 000155
【図５９】
2007528529.tif 000156
【図６０】
2007528529.tif 000157
【図６１】
2007528529.tif 000158
【図６２】
2007528529.tif 000159
【図６３】
2007528529.tif 000160
【図６４】
2007528529.tif 000161
【国際調査報告】
2007528529.tif 000162
2007528529.tif 000163
2007528529.tif 000164