(57)【要約】  立体３次元画像データを３次元表面データに変換する方法は、まず、表面変換の前に、立体画像の主表面に付着した無関係のボクセルと、主画像の周囲の無関係のボクセルとを除去する（２１０）ことにより、立体画像の表面を平滑化する。立体画像が表面画像に変換されると、方法は、周囲のトポグラフィに関して考慮した場合に不適当に見える、あらゆる著しく急な山型の構造を除去する（８４０）ことにより、表面をクリーニングする。表面画像をレンダリングするために必要なデータの量は、周囲のトポグラフィの平面閾値内にある表面小面を除去する（１３０）ことによって低減される。トポグラフィはまた、局所エリアにおいて中間レベルに向かうように圧縮される。方法はさらに、この時閾値限界内にある可能性のあるさらなる表面小面を低減するように繰り返してもよい（１４０）。
2009508583.tif 000002
【特許請求の範囲】
【請求項１】
ボクセルからなる立体３次元画像を３次元表面レンダリングに変換する方法であって、
該立体３次元画像の表面のボクセルを第１所定閾値に収縮させるステップと、
任意の非収縮表面ボクセルの周囲の該表面にボクセルを追加することにより、該立体３次元画像の該表面を第２所定閾値に膨張させるステップと、
数が第３所定閾値を下回る連続ボクセルのグループを除去するステップと、
すべての表面ボクセルを識別するデータを、複数の相関三角プレートを表すデータに変換することにより、初期３次元表面画像をレンダリングするステップと、
該立体３次元画像を形成する該ボクセルのすべてを識別するデータを破棄するステップと、
該複数の三角プレートのグループによって形成される多面体構造を除去することにより、該初期３次元表面画像をクリーニングするステップと、
該初期３次元表面画像を形成する該複数の三角プレートの数を低減することにより、該初期３次元表面画像をデシメートするステップと、
該複数の三角プレートのグループによって形成される多面体構造のピーク頂点の、局所平面からの初期距離を低減することにより、該初期３次元表面レンダリングを平滑化するステップと、
を含む、方法。
【請求項２】
前記クリーニングするステップが、
前記三角プレートのグループによって形成される任意の多面体構造のピーク頂点および対応するエッジであって、局所平面からの該ピーク頂点の距離が第４所定閾値を上回る、該ピーク頂点および対応するエッジを除去するステップ
をさらに含む、請求項１に記載の方法。
【請求項３】
前記多面体構造の前記ピーク頂点および対応するエッジの前記除去によって形成されるベース多角形エリアを三角形分割するステップをさらに含む、請求項２に記載の方法。
【請求項４】
前記デシメートするステップが、
前記三角プレートのグループによって形成される任意の多面体構造のピーク頂点および対応するエッジであって、該ピーク頂点の局所平面からの距離が第５所定閾値を下回る、該ピーク頂点および対応するエッジを除去するステップ
をさらに含む、請求項１に記載の方法。
【請求項５】
前記多面体構造の前記ピーク頂点および対応するエッジの前記除去によって形成されるベース多角形エリアを三角形分割するステップをさらに含む、請求項４に記載の方法。
【請求項６】
前記デシメートするステップが、
前記三角プレートのグループによって形成される任意の多面体構造のピーク頂点および対応するエッジであって、該多面体構造の該対応するエッジのうちの少なくとも１つの多面角が第６所定閾値を上回る、該ピーク頂点および対応するエッジを除去するステップ
をさらに含む、請求項１に記載の方法。
【請求項７】
前記多面体構造の前記ピーク頂点および対応するエッジの前記除去によって形成されるベース多角形エリアを三角形分割するステップをさらに含む、請求項６に記載の方法。
【請求項８】
前記平滑化するステップが、
前記初期距離を変換するステップと、
該波形に対しフーリエ変換を適用することにより振幅領域波形を形成するステップと、
該振幅領域波形をフィルタリングすることにより、前記ピーク頂点と前記局所平面との間の前記距離の低い範囲および高い範囲のうちの少なくとも一方を減衰させるステップと、
逆フーリエ変換を適用することにより、該減衰した振幅領域波形を第２波形に変換するステップと、
該第２波形を、該ピーク頂点と該局所平面との間の低減した第１波形の距離に変換するステップと、
をさらに含む、請求項１に記載の方法。
【請求項９】
残っている三角プレートの第７所定閾値に達するまで、前記デシメートするステップおよび前記平滑化するステップを繰り返すステップをさらに含む、請求項１に記載の方法。
【請求項１０】
前記第７所定閾値を満たすことができないとき、残っている三角プレートの該第７所定閾値に達するまで、第１変更閾値、第２変更閾値および／または第３変更閾値で請求項１および請求項１１のステップを繰り返すステップをさらに含む、請求項９に記載の方法。
【請求項１１】
残っている三角プレートの第７所定閾値に達するまで、前記クリーニングするステップ、前記デシメートするステップおよび前記平滑化するステップを繰り返すステップをさらに含む、請求項１に記載の方法。
【請求項１２】
前記第７所定閾値を満たすことができないとき、残っている三角プレートの該第７所定閾値に達するまで、第１変更所定閾値、第２変更所定閾値および／または第３変更所定閾値で請求項１および請求項１１のステップを繰り返すステップをさらに含む、請求項１１に記載の方法。
【請求項１３】
前記３次元表面画像を形成する各三角形小面に対し小面法線を計算するステップをさらに含む、請求項１に記載の方法。
【請求項１４】
前記小面法線を計算するステップが、
小面の各頂点に対し、該頂点に共通の各三角プレートの該小面法線を平均化することにより、頂点法線値を計算するステップと、
特定の小面の各頂点の頂点法線値の平均を計算するステップと、
該三角プレートの各々の該小面法線を、該頂点法線値の該平均に置き換えるステップと、
をさらに含む、請求項１３に記載の方法。
【請求項１５】
立体３次元画像の表面のボクセルを第１所定閾値に収縮させるステップと、
任意の非収縮表面ボクセルの周囲の該表面にボクセルを追加することにより、該立体３次元画像の該表面を第２所定閾値に膨張させるステップと、
数が第３所定閾値を下回る連続ボクセルのグループを除去するステップと、
すべての表面ボクセルを識別するデータを、複数の相関三角プレートを表すデータに変換することにより、初期３次元表面画像をレンダリングするステップと、
該立体３次元画像を形成する該ボクセルのすべてを識別するデータを破棄するステップと、
該複数の三角プレートのグループによって形成される多面体構造を除去することにより、該初期３次元表面画像をクリーニングするステップと、
該初期３次元表面画像を形成する該複数の三角プレートの数を低減することにより、該初期３次元表面画像をデシメートするステップと、
該複数の三角プレートのグループによって形成される多面体構造のピーク頂点の、局所平面からの初期距離を低減することにより、該初期３次元表面レンダリングを平滑化するステップと、
を含むステップを実行するコンピュータ実行可能命令を有するコンピュータ可読媒体。
【請求項１６】
前記クリーニングするステップを実行する前記コンピュータ実行可能命令が、
前記三角プレートのグループによって形成される任意の多面体構造のピーク頂点および対応するエッジであって、局所平面からの該ピーク頂点の距離が第４所定閾値を上回る、該ピーク頂点および対応するエッジを除去するステップ
をさらに含む、請求項１５に記載のコンピュータ読取可能媒体。
【請求項１７】
前記デシメートするステップを実行する前記コンピュータ実行可能命令が、
前記三角プレートのグループによって形成される任意の多面体構造のピーク頂点および対応するエッジであって、局所平面からの該ピーク頂点の距離が第５所定閾値を下回る、該ピーク頂点および対応するエッジを除去するステップ
をさらに含む、請求項１５に記載のコンピュータ読取可能媒体。
【請求項１８】
前記デシメートするステップを実行する前記コンピュータ実行可能命令が、
前記三角プレートのグループによって形成される任意の多面体構造のピーク頂点および対応するエッジであって、該多面体構造の該対応するエッジのうちの少なくとも１つの多面角が第６所定閾値を上回る、該ピーク頂点および対応するエッジを除去するステップ
をさらに含む、請求項１５に記載のコンピュータ読取可能媒体。
【請求項１９】
前記平滑化するステップを実行する前記コンピュータ実行可能命令が、
前記初期距離を変換するステップと、
該波形に対しフーリエ変換を適用することにより振幅領域波形を形成するステップと、
該振幅領域波形をフィルタリングすることにより、前記ピーク頂点と前記局所平面との間の前記距離の低い範囲および高い範囲のうちの少なくとも一方を減衰させるステップと、
逆フーリエ変換を適用することにより、該減衰した振幅領域波形を第２波形に変換するステップと、
該第２波形を、該ピーク頂点と該局所平面との間の低減した第１波形の距離に変換するステップと、
をさらに含む、請求項１５に記載のコンピュータ読取可能媒体。
【請求項２０】
前記デシメートするステップを実行する前記コンピュータ実行可能命令が、残っている三角プレートの第７所定閾値に達するまで、前記デシメートするステップおよび前記平滑化するステップを繰り返すステップをさらに含む、請求項１５に記載のコンピュータ読取可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本発明は、２００５年９月１５日に出願された米国特許出願第１１／２２７，００５号明細書（「’００５出願」）に対する利益を主張する。’００５出願は、本明細書において完全に説明されているかのように参照により本明細書に援用される。
【０００２】
本発明は、立体グラフィカル画像ファイルを単に立体画像の表面を表すデータに変換する方法に関する。
【背景技術】
【０００３】
従来のＸ線システムでは、骨および軟組織の異なるＸ線吸収特性に基づいて２次元影画像が作成される。診断ツールとしての従来のＸ線システムに対する顕著な改善は、コンピュータ断層撮影（ＣＴ）システムまたはコンピュータ体軸断層撮影（ＣＡＴ）システムの開発によって提供された。これらＣＴシステムまたはＣＡＴシステムは、Ｘ線ベースであり、当初、検査されている身体、物体または患者の横方向スライスを示す単一の２次元ビューを生成するために使用された。その後、複数の連続スライスに対するデータを生成し、放射線専門医の推断能力を使用することによって、ＣＴスキャンデータから３次元情報を組み立てることにより、さまざまな内部器官に対する３次元表現が提案された。影付きかつ立体的な３次元画像は、かかる連続ＣＴスキャンのシーケンスによって生成されるデータの３次元アレイからのスライス間の補間によって生成することができる。同様に、より新しい磁気共鳴画像化（ＭＲＩ）技術も、また、内部身体器官の物理特性を表すデータの３次元アレイを生成することができる。ＭＲＩシステムは、骨および軟組織だけでなくさまざまな組織タイプをよりよく識別する機能を提供できる点において、ＣＴシステムに対し有利である。ＭＲＩ撮像システムはまた、単なる画像データではなく生理学的データを生成することもできる。この場合もまた、ＣＴシステムの場合のように、ＭＲＩデータは、スライスのシーケンスとしてのみ入手可能であり、３次元画像をレンダリングするためにはスライス間の補間が必要である。
【０００４】
近年、患者の心臓のＣＴ画像およびＭＲＩ画像は、心臓専門医および他の臨床医が、不整脈を診断し治療するための電気生理学研究または心臓アブレーション治療を行うのを支援するために使用されてきた。心臓の３次元画像は、臨床医が、心臓内のカテーテル電極の位置を視覚化して患者の状態をマップし治療するのに役立つ。しかしながら、一般に、心臓内の空洞の表面のレンダリングのみが必要でありまたは望ましい。したがって、ＭＲＩ画像データまたはＣＴ画像データからの立体３次元情報を表面データのみに変換する方法が開発された。表面データのみを操作することにより、必要な処理能力がはるかに低減し、より高速なレンダリング速度が達成される。
【０００５】
以前から、立体３次元画像データを単なる表面データに変換するいくつかのオプションが開発されたが、各々には利点と欠点とがある。かかる肯定的態様および否定的態様は、一般に、相対処理速度、表面レンダリングの精度、および無関係な情報を識別し破棄する能力に現れる。
【０００６】
本明細書のこの背景技術部分に含まれる、本明細書で列挙するあらゆる参考文献およびそのあらゆる説明または論考を含む情報は、技術的な参照の目的のみのために含まれるものであり、本発明の範囲が束縛されるべき主題であるとみなされるべきではない。
【発明の開示】
【課題を解決するための手段】
【０００７】
本発明は、立体３次元画像データを３次元表面データに変換する新たな方法を提供する。変換の一部として、本方法は、表面変換の前に、立体画像の主表面に付着したボクセルと主画像の周囲の無関係のボクセルとを含む無関係なボクセルを除去することにより、立体画像の表面を平滑化する。立体画像が表面画像に変換されると、本方法は、再び、周囲のトポグラフィに関して考慮した場合に不適当に見える、あらゆる著しく急な山型のピーク状構造を除去することにより、表面をクリーニングする。本方法はさらに、周囲のトポグラフィの平面閾値内にある表面小面（ｓｕｒｆａｃｅ ｆａｃｅｔｓ）を除去することにより、表面画像をレンダリングするために必要なデータの量を低減する。本方法はさらに、局所エリアにおけるトポグラフィを圧縮して中間レベルに向かうようにする。トポグラフィカルエリアを圧縮した後、方法はさらに、この時閾値限界内にある可能性のある追加の表面小面を低減するように繰り返してもよい。データ低減の標的レベルに達すると、３次元表面画像は完成したとみなされ、使用のために保存される。この方法に対する例示的な適用は、電気生理学研究およびアブレーション治療とともに使用されるためにＭＲＩ画像データまたはＣＴ画像データを３次元表面のみのデータに変換することにある。しかしながら、本発明は、あらゆる立体３次元立体画像データを３次元表面画像に変換するために使用され得る。
【０００８】
本発明の他の特徴、詳細、有用性および利点は、添付図面にさらに示されておりかつ添付の特許請求の範囲において定義されるような本発明のさまざまな実施形態の以下のより特定の書面による説明から明らかとなろう。
【発明を実施するための最良の形態】
【０００９】
本発明は、立体３次元グラフィック画像モデルを、その３次元グラフィックモデルの外面を密に近似する表面レンダリングに変換する方法に関する。３次元立体モデルである画像モデルを扱っているが、ユーザにはモデルの外面に関連する情報のみが重要である場合、かかる変換は、非常に望ましい可能性がある。かかる場合、３次元情報のすべてを操作しようと試みることは、コンピュータ処理能力の無駄であり、さらに、画像をレンダリングするために追加のかつ不要な処理時間がかかる。たとえば、ＭＲＩまたはＣＴ等の医療用撮像プロセスでは、立体画像モデルは、かかるスキャンからもたらされるスライス画像を積み重ねることによってレンダリングされる。この立体３次元情報は、一般に、診断用医療画像をレンダリングするために組織密度またはタイプの変化を示す大量のグレースケールボクセルデータを含む。望まれる情報が、特定の器官または組織構造、たとえば心室の表面のレンダリングのみである場合、関心のある表面領域の内部および外部のボクセルデータは不必要である。
【００１０】
図１は、立体３次元グラフィックモデルを、その３次元グラフィックモデルの外面に密に近似する表面レンダリングに変換するために、本発明に従って行われる一連のステップを示す高レベルフローチャート１００を示す。ステップ１０５において、解剖学的スキャンファイルのセグメント化モデルであってもよい、３次元グラフィックモデル、たとえばＭＲＩ画像またはＣＴ画像がアクセスされ開かれる。セグメント化モデルは、３次元画像の小領域が、より大きい３次元画像からデジタル処理によって分離されたことを示し、たとえば心臓の他の部分から分離された右心房の画像である。例示的なセグメンテーションアプリケーションには、アナライズ（ＡＮＡＬＹＺＥ）（ミネソタ州ミネアポリスのメイヨー（Ｍａｙｏ（Ｍｉｎｎｅａｐｏｌｉｓ，ＭＮ））、ヴェリスモ（Ｖｅｒｉｓｍｏ）（ミネソタ州セントポールのセント・ジュード・メディカル（Ｓｔ．Ｊｕｄｅ  Ｍｅｄｉｃａｌ，Ｉｎｃ．（Ｓｔ．Ｐａｕｌ，ＭＮ））およびＣａｒｄＥＰ（ウィスコンシン州ミルウォーキーのジェネラル・エレクトリック・メディカル・システムズ（Ｇｅｎｅｒａｌ  Ｅｌｅｃｔｒｉｃ  Ｍｅｄｉｃａｌ  Ｓｙｓｔｅｍｓ（Ｍｉｌｗａｕｋｅｅ，ＷＩ））がある。一般にかかる画像ファイルは、３次元画像点情報からなる。各画像点は、一般にボクセルと呼ばれ、それは、画素、すなわち２次元表示環境におけるグラフィック情報の共通単位の３次元バージョンである。したがって、各ボクセルは、３次元グラフィック画像をレンダリングするために必要な情報、特に位置情報、色情報および陰影情報を含む。
【００１１】
３次元グラフィックファイルがアクセスされると、立体画像の表面上のボクセルには、収縮（ｅｒｏｓｉｏｎ）および膨張（ｄｉｌａｔｉｏｎ）プロセスが施される（ステップ１１０）。これについて、図２および図３Ａ〜図３Ｄに関してより詳細に説明する。図２の収縮および膨張プロセス２００は、３次元モデルを簡略化するために実行される。収縮および膨張プロセス２００は、所望の３次元画像に対して無関係である可能性があるか、または他の方法で３次元画像を不必要に複雑にするようなブリッジまたは他の狭いボクセル構造を除去することを目的とする。ステップ２１０において、立体モデルの表面のボクセルの１つまたは複数の層が収縮または除去される。除去される層の数は、閾値変数として設定され、ユーザが所望の結果に応じて変更することができるものである。狭いボクセル列は所望の表面画像の一部でない可能性が高いという仮定から動作して、幅が一定数未満であるボクセルのグループを除去するように閾値を設定することにより、かかるグループまたはチェーンが除去または収縮される。
【００１２】
図３Ａ〜図３Ｃは、収縮ステップ２１０の効果を概略的に示す。図３Ａに示すように、Ａ〜Ｌが付されたボクセルのグループに対して収縮プロセスが施される。図３ＡにおけるボクセルＡ〜Ｌのグループは、提示を容易にするために２次元形式で表されているが、実際には、プロセスは立体グラフィックモデルの表面の３次元ボクセルに対して動作していることに留意されたい。たとえば、閾値収縮値が１に設定されているとき、収縮プロセス２１０は、ＤおよびＥを除くすべてのボクセルを除去する。図３Ｂにおいて、収縮が施されるボクセルＡ、Ｂ、Ｃ、Ｆ、Ｇ、Ｈ、Ｉ、Ｊ、Ｋ、Ｌが、十字によって消されている。これは、ボクセルＤおよびＥのみが、すべての辺において隣接ボクセルによって包囲されているため、明らかである。
【００１３】
立体グラフィックモデルの表面に収縮が施されると（ステップ２１０）、プロセスは次に、膨張または再構築ステップ２２０を実行する。このステップでは、収縮された表面にボクセルの１つまたは複数の層が再び追加される。図３Ｃに示すように、元の画像表面のボクセルＤおよびＥのみが残されている。しかしながら、膨張ステップ２２０が実行されると、ボクセルＤおよびＥは新たなボクセルＡ’、Ｂ’、Ｃ’、Ｆ’、Ｉ’およびＪ’によって包囲される。これらボクセルＡ’、Ｂ’、Ｃ’、Ｆ’、Ｉ’およびＪ’内の円は、それらが膨張プロセスの結果として新たに形成されていることを示す。図３Ｄから明らかであるように、ボクセルＧおよびＨの薄いブリッジはもはや立体グラフィック表面の一部ではない。同様に、元のボクセルＫおよびＬは除去されており、このため、結果としての表面は「より平滑」である。膨張ステップ２２０が実行されると、膨張立体画像グラフィックは、本発明のさらなるステップに従ってさらに処理されるために保存される（ステップ２３０）。
【００１４】
図１に戻ると、収縮および膨張プロセスが実行された後（ステップ１１０）、次に、立体グラフィック画像に対しクラッタ除去が施される（ステップ１１５）。図４および図５Ａ〜図５Ｃに、クラッタ除去４００のプロセスをより詳細に示す。クラッタ除去プロセス４００の目的は、ユーザが設定した閾値のサイズ限界を満たさないあらゆる小さいかまたは分離したボクセルクラスタを除去することである。ボクセルの独立したグループにおけるボクセルの数が閾値を下回るとき、そのグループは「クラッタ」として削除される。したがって、第１ステップは、画像の一部として維持されるクラスタまたはグループにおけるボクセルの数に対する最小閾値を確定することである（ステップ４１０）。次のステップは、連結ボクセルの個々の島またはクラスタ各々を識別することである（ステップ４２０）。たとえば、図５Ａでは、ボクセル５００、５０２、５０４、５０６という４つの別個のクラスタが識別されている。第１クラスタ５００は６つのボクセルを有するものとして示されており、第２クラスタ５０２は単一ボクセルとして示されており、第３クラスタ５０４は２つのボクセルを有するものとして示されており、第４クラスタ５０６は５つのボクセルのグループとして示されている。
【００１５】
クラッタ除去プロセス４００は、個々の島またはクラスタ各々におけるボクセルの数をカウントすることによって続行する（ステップ４３０）。検査のために第１島またはクラスタが選択される（ステップ４４０）。そして、その特定の島またはクラスタにおけるボクセルの数が、先に設定された閾値を下回るか否かの判断がなされる（ステップ４５０）。ボクセルの特定のクラスタが閾値を上回る数を有するとき、かかるクラスタは、立体画像ファイルの一部であり続ける。ボクセルの数が閾値を下回るとき、ボクセルのその特定の島またはクラスタは、３次元グラフィック画像から破棄される（ステップ４６０）。たとえば、図５Ｂに示すように、閾値が２ボクセルに設定されているとき、第２クラスタ５０２および第３クラスタ５０４は、画像ファイル全体から削除される。クラスタが除去された後（ステップ４６０）、またはクラスタにおけるボクセルの数が閾値を上回るとき（ステップ４５０）、プロセス４００は続けて、さらなる島またはクラスタが検査される必要があるか否かを判断する（ステップ４７０）。さらなるボクセルクラスタが検査される必要のないとき、プロセス４００は、操作すべき新たなクラスタを選択する（ステップ４８０）。ボクセルの追加のクラスタに検査が必要であるとき、プロセス４００はステップ４５０に戻り、各クラスタにおけるボクセルを閾値と比較する。このため、図５Ｃに示すように、第２クラスタ５０２および第３クラスタ５０４は除去されるが、各々閾値量より多くのボクセルを有する第１クラスタ５００および第４クラスタ５０６は、グラフィック画像ファイルの一部として残る。クラッタ除去プロセスは、閾値を超える残りのボクセルクラスタを含む立体画像を保存することによって終了する（ステップ４９０）。
【００１６】
クラッタ除去のステップ１１５に続き、図１に示すように、次に高密度タイリング手続き１２０を実施してもよい。高密度タイリングステップ１２０の主な目的は、立体グラフィック画像を単なる立体画像の外面のレンダリングに変換することである。表面レンダリングを作成することにより、著しい量のデータおよび情報を破棄することができ、そのため、画像のより高速な処理および操作が可能となる。例示的な高密度タイリングプロセスを、図６により詳細に示す。この例示的なプロセスは、参照により開示内容がすべて本明細書に援用される、米国特許第４，７１０，８７６号明細書において詳細に説明されている。
【００１７】
本論考の目的のために、図６および図７Ａ〜図７Ｂに関連して、高密度タイリングプロセス６００の高レベルな概観を提示する。最初に、立体画像の表面ボクセルが識別される（ステップ６１０）。次に、各表面ボクセルに関して、各露出頂点がさらに識別される（ステップ６２０）。たとえば、図７Ａに、Ｖ１〜Ｖ８が付された８つの頂点を有する単一ボクセルを示す。本論考の目的のために、頂点Ｖ１が唯一の外部頂点として識別される。実際には、これは、他の頂点の各々が別のボクセルの頂点に隣接していることを意味する。各ボクセルを、さらに、頂点Ｖ１〜Ｖ８の各々の間に延在する１２のエッジを有するものとして見ることができる。図７Ａにおいて、エッジの各々にはＥ１〜Ｅ１２が付されている。頂点Ｖ１およびＶ４、Ｖ３およびＶ４ならびにＶ４およびＶ８を連結する破線を除くと、図７Ａの破線は、エッジの各々の中点を連結し、概してボクセルを４つの象限に分割する。
【００１８】
この背景により、高密度タイリングプロセス６００の次のステップは、外部または露出頂点に対して垂直な三角プレートを構築することである（ステップ６３０）。この概念を図７Ｂに示す。図７Ｂに示すように、三角プレートは、外部頂点Ｖ１に共通するエッジＥ１、Ｅ４およびＥ５の各々の中点の間に構築される。図７Ｂにおいて分かるように、この三角プレートは頂点Ｖ１に対して垂直である。ボクセルの２つ以上の頂点が外部頂点である場合、この三角プレート構築の概念は、外部頂点の各々に対して垂直な三角プレートの集まりを構築するように推定される。表面ボクセルの外部頂点の各々に対して三角プレートが構築されると、ボクセルの夫々のエッジ中点によって識別される三角プレートの各々の頂点は、２値表面画像情報に変換される（ステップ６４０）。三角プレートが２値形式で表されると、立体画像の表面ボクセルと内部ボクセルとの両方に対する３次元ボクセル情報が破棄される（ステップ６５０）。そして、元の立体画像の表面に対応する三角プレートの集まりの２値表面情報が保存される（ステップ６６０）。
【００１９】
図１に示すような高密度タイリングステップ１２０を介して、立体グラフィック画像が表面モデルに変換されると、プロセスにおける次のステップは表面をクリーニングすることである（ステップ１２５）。表面をクリーニングする目的は、周囲の表面と実質的に同一平面にないあらゆるオブジェクトを探索し除去することである。表面をクリーニングするプロセスについては、図８および図９Ａ〜図９Ｂに関してより詳細に説明する。三角プレートによって形成される表面画像は、隣接エリアの上方に延在する多面体構造によって埋められる相対的に平面なエリアを有する表面「メッシュ」として視覚化されてもよい。
【００２０】
表面クリーニングプロセス８００は、ピーク頂点がベース頂点の上方にありかつエッジに沿ってそれに連結される任意の多面体の、ベース頂点の平均面を確定すること（ステップ８１０）によって開始する。そして、各ピーク頂点からステップ８１０において先に確定された平均面までの距離が計算される（ステップ８２０）。そして、平均ベースからのピーク頂点の距離が閾値より大きいか否かについて判断される（ステップ８３０）。概して、この閾値は、本来平滑な表面構成のエリアから突出している実質的な収差を識別するように、ユーザによって選択される。ピーク頂点の分離距離が閾値を上回るとき、ピーク頂点と、ピーク頂点をベース頂点に連結するすべてのエッジと、が、表面メッシュから除去される（ステップ８４０）。ピーク頂点が除去されると、ピーク頂点の除去後に残っているあらゆる多角形ベースエリアが三角部分に変換される（ステップ８５０）。ピーク頂点から局所平面までの距離が閾値を下回るとき、表面クリーニングプロセス８００はステップ８３０からステップ８６０までスキップする。プロセス８００は、すべての頂点が検査されたか否かを問い合わせる（ステップ８６０）。そうでないとき、プロセス８００は検査するために新たな頂点を選択し（ステップ８７０）、ステップ８１０に戻って、新たな頂点の周りの平均平面を計算し、プロセス８００における他のステップを完了する。最終ベースエリアが三角形分割された（ｔｒｉａｎｇｕｌａｔｅｄ）後、クリーンな表面モデルがさらなる処理ステップで使用されるために保存される（ステップ８８０）。
【００２１】
図９Ａおよび図９Ｂは、表面クリーニングプロセス８００の例示的な描写である。図９Ａにおいて、ベース９０４を有する鋭利な多面体９０２が、本来略平面の表面エリア９００の上方に延在している。表面クリーニングプロセス８００に従い、多面体９０２のピーク頂点Ｖが、ピーク頂点Ｖをベース９０４の頂点に連結するエッジと同様に除去される。図９Ｂにおいて、ピーク頂点Ｖと、それをベース９０４と連結するエッジとが除去されている。図９Ｂにおいて、ベース９０４のみが、平面エリア９００における穴または空きエリアとして残る。しかしながら、ベース９０４は非三角形の多角形であり、３次元表面を表すために望まれる２値データセットに適合しない。したがって、先の多面体９０２のベース９０４は、図９Ｂに示すように、２つの三角形部分９０６、９０８に適切に三角形分割される。
【００２２】
図１に戻ると、ステップ１２５において表面がクリーニングされた後、多角形表面モデルがデシメートされる（ステップ１３０）。デシメーションの主な目的は、３次元表面を記述するために使用される情報の量を低減することである。ステップ１２０の高密度タイリングアルゴリズムにより、１００，０００以上の三角形からなる表面が作成される。かかる大量の表面三角形の位置を特定し方向付けることに関するデータにより、表面モデルを操作するコンピュータシステムの処理能力に対し要求が高くなる。したがって、画像の表面を形成する著しい数の三角形を除去しようと試みることが望ましい。通常、画像表面を表すおよそ１５，０００の三角形まで低減することにより、対応するデータが管理可能な量まで低減する。
【００２３】
図１０は、多角形モデルのデシメーションプロセス１０００に含まれるステップをより詳細に示す。図１１Ａおよび図１１Ｂは、かかるプロセスが表面画像に対して与える影響のグラフィック表現を提供する。デシメーションプロセス１０００は、実際には、いくつかの点において、図８に関して上述した表面クリーニングプロセス８００に類似する。上述したように、多面体ピーク頂点の周囲の局所平均面が確定される（ステップ１０１０）。そして、局所面からのこのピーク頂点の距離が測定される（ステップ１０２０）。そして、プロセスは、局所面からのピーク頂点の距離が閾値距離を下回るか否かを問い合わせる（ステップ１０３０）。ピーク頂点が閾値距離を下回らないとき、プロセスは続けて、同様の計算を行う新たなピーク頂点を選択する（ステップ１０８０）。ピーク頂点分離距離が閾値を下回るとき、プロセスはさらに、ピーク頂点によって形成される多角形の二面角が閾値より大きいか否かを問い合わせる。二面角が大きいほど、ピーク頂点によって形成される多面体は平坦になる。これは、ピーク頂点によって形成される多面体が、周囲の局所平面に対して非常に低く、そのため、多面体がデシメーションに対し適当な候補であることを示す。二面角が閾値を上回らないとき、プロセスは続けて同様の計算を行う新たなピーク頂点を選択する（ステップ１０８０）。
【００２４】
ステップ１０３０およびステップ１０４０における条件が満たされると、ピーク頂点と付着されたエッジとが表面モデルから除去される（ステップ１０５０）。デシメーションプロセス８００において上述したように、いかなる奇数多角形形状エリアも三角形の集まりに変換するために、残っている多角形ベースが三角形分割される（ステップ１０６０）。そして、デシメーションプロセス１０００は、表面モデルのすべてのあり得るピーク頂点が検査されたか否かを問い合わせる（ステップ１０７０）。そうでないとき、デシメーションプロセス１０００は、続けてすべてのピーク頂点を検査するように繰り返し、それらがデシメーションの基準を満たすか否かを判断する。デシメーションプロセス１０００が表面モデルのすべてのピーク頂点を検査すると、デシメートされた表面モデルがさらなる処理のために保存される（ステップ１０９０）。
【００２５】
デシメーションプロセス１０００の結果を、図１１Ａおよび図１１Ｂの比較を通して見る。図１１Ａにおいて、ピーク頂点Ｖを有する多面体は、Ａ〜Ｅが付された５つの小面（ｆａｃｅｔｓ）から構成される。この例では、ピーク頂点の高さｄは、閾値限界を下回り、二面角φは閾値限界を超え、したがって多面体にデシメーションが施される。図１１Ｂにおいて、ピーク頂点Ｖおよび隣接エッジが除去されており、残っている多角形フットプリントが、５つの三角形Ａ〜Ｅからなる先の多面体表面の代りに、３つの三角形Ａ’、Ｂ’およびＣ’からなる表面をもたらすように三角形分割されている。このように、デシメーションプロセス１０００を遂行することにより、表面モデルを記述するために必要なデータの量が低減することが明らかとなる。
【００２６】
再び図１に戻ると、デシメーションステップが実行された後（ステップ１３０）、表面画像モデルは、関連する平滑化プロセスを介して平滑化されてもよい（ステップ１３５）。図１２に、例示的な平滑化プロセス１２００をより詳細に提示する。平滑化プロセス１２００は、デシメーションプロセス１０００と同様に開始する。各三角形の頂点の周りの局所平面が確定され（ステップ１２１０）、夫々の局所平面からの表面モデル上の頂点の距離が計算される（ステップ１２２０）。しかしながら、平滑化プロセス１２００では、完全に異なる方法が実行される。平滑化プロセス１２００では、頂点の、それらの夫々の局所平面からの距離が、波形に変換される（ステップ１２３０）。例示的な波形を図１３Ａに示す。図１３Ａにおける波形のピークは、周囲のベース頂点からの隣接するピーク頂点の相対距離を表す。
【００２７】
平滑化プロセス１２００の次のステップでは、波形に対してフーリエ変換が実行され（ステップ１２４０）、それにより、波形の領域が振幅領域に変更される。振幅領域を、図１３Ｂにおいて、局所平面からの夫々の高さまたは距離に対してプロットされたピーク頂点の数を表す曲線として示す。たとえば図１３Ａでは、ピーク頂点の大部分が、中間高さ内にある分離距離を有する可能性がある。平滑化プロセス１２００の次のステップでは、変換に対してフィルタが適用されることにより、ユーザによって設定された保持すべき振幅値の範囲またはパーセンテージ閾値に基づき、低い値および高い値が除去される（ステップ１２５０）。このフィルタリングを、図１３Ｂにおいて、高および低とマークされた値から中間値を分離する垂直線によって表す。ステップ１２５０においてフィルタが適用されると、振幅領域波形における減衰値に対し逆フーリエ変換が実行される（ステップ１２６０）。それにより、高さの高い頂点の減衰によって局所平面からのピーク頂点の分離距離が低減する（ステップ１２７０）。さらに、減衰はまた、あらゆる低い頂点にも影響を与え、それにより、それらエリアにおける局所平面が上昇する。頂点の相対的な上昇および低下を、図１３Ａにおいて矢印によって表す。平滑化プロセス１２００からもたらされる最終表面を図１３Ｃに表す。図３においては、ピーク頂点と局所平面との間の分離距離が短くなっている。図１３Ａと図１３Ｃとの間で共通する頂点のうちのいくつかにつき、図１３Ａと図１３Ｂとの間に及ぶ例示的な破線によって示す。平滑化プロセス１２００は、平滑表面モデルを保存することによって終了する（ステップ１２８０）。
【００２８】
表面レンダリングプロセスの次のステップを、再び図１に提示する。本プロセスの目的が表面モデルを表すために必要なデータの量を低減することであることを想起し、プロセスは、デシメーションステップ１３０および平滑化ステップ１３５を介して三角形割当量（ｂｕｄｇｅｔ）が満たされたか否かを問い合わせる（ステップ１４０）。上述したように、表面モデルから三角形小面を低減するための例示的な目標は、表面画像モデルを表すために、１００，０００を超える三角形を、１５，０００を下回る三角形まで低減することであってもよい。所望の低減レベルが満たされていないとき、プロセスはステップ１４０に戻り、ステップ１４０の三角形割当量が最終的に満たされるまで、ステップ１３０においてデシメーションプロセスを実行し、さらにステップ１３５において平滑化プロセスを実行する。ステップ１３５の平滑化プロセスを実行することにより、表面モデルから突出している多面体の任意のピーク頂点とそれらの局所平面との間の分離距離は一様に低減されることが留意されるべきである。この分離距離を低減することにより、ここでより多くのピーク頂点の分離距離が閾値距離を下回ることになるため、より多くのピーク頂点が、図１０のステップ１０３０に従うデシメーションに対する対象となる。したがって、デシメーションステップ１３０および平滑化ステップ１３５を繰り返し実行することにより、ステップ１３５の三角形割当量を最終的に満たすことができる。さらに、デシメーションステップ１３０および平滑化ステップ１３５を実行する順序は重要でなく、逆にしてもよい、ということも留意されるべきである。
【００２９】
ステップ１４０の三角形割当量が達成されると、プロセスは、表面モデルを形成する残りの三角形の各々に対して、小面法線（すなわち、三角プレートの面に対して垂直な方向を示す単位ベクトル）を計算する（ステップ１４５）。小面法線を計算することに関与するステップを、図１４により詳細に示す。小面法線計算プロセス１４００は、表面画像レンダリングを作成する際の比較的標準的なプロセスである。小面法線データは、グラフィックレンダリングプログラムにより、人工光源の相対位置に基づいて特定の小面に対する適当な陰影を示すために使用される。小面法線は、３次元表面モデルを形成する各三角プレートの各頂点に対し頂点法線をさらに計算するために使用される。頂点法線情報は、後のグラフィックレンダリングのために表面画像情報とともに保存される。まず、表面画像における各小面または三角プレートに対する法線が計算される（ステップ１４１０）。次に、特定の頂点を包囲する小面の小面法線が平均化される（ステップ１４２０）。特定の頂点を包囲する小面法線の平均は、特定の頂点に割り当てられるか特定の頂点によって識別され（ステップ１４３０）、表面モデル情報とともに保存される（ステップ１４４０）。
【００３０】
プロセス１００の目的に対し、小面法線プロセス１４００はステップ１４４０で完了する。しかしながら、例示的なグラフィックレンダリングプログラムによって後に実行される一般的なステップのいくつかの論考は、頂点法線情報を作成し格納するための根本理由を理解するのに役立つ。表面画像に対しグレースケールまたは色を適用するための陰影を確定する場合、多くのグラフィックレンダリングプログラムは頂点法線情報を得ようとする。表面画像の各三角形小面に対し、小面を包囲する３つの頂点に対する法線値の平均が計算され（ステップ１４５０）、次いで、頂点法線に対するこの平均値が、夫々の小面に小面法線として再割当てされる（ステップ１４６０）。これらステップに対するボックスを図１４では想像線で示す。なぜなら、技術的にそれらは表面画像レンダリングプロセス１００の一部ではないためである。法線ベクトル情報を２度平均化することにより、特に点光源下で表面に適用されるグレースケールまたは色陰影に関し、大幅により一様な表面画像が達成可能である。
【００３１】
このプロセスの利点を、図１５Ａおよび図１５Ｂに示す。図１５Ａにおいて、ピーク頂点を有する多面体は、矢印で示すような完全に異なる方向でグラフィック表面レンダリングプログラムにおいて光源から光を反射するいくつかの小面を有する。このように反射方向が異なることにより、多面体の小面に適用されるグレースケールは非一様となり、さらに、周囲のより平滑な表面エリアとは完全に異なる方向に光源を反射する可能性が高くなる。しかしながら、頂点法線（図１５Ｂ参照）を計算し、その後、各三角形小面に対して頂点法線を平均化することにより、いかなるグレースケール適用に対する反射方向も、多面体の表面に亙ってより一貫することになる。小面法線および頂点法線が計算されると、図１において概説したプロセスは、計算された３次元表面モデルを後に使用されるためのフォーマットで保存することにより終了する（ステップ１５０）。
【００３２】
本発明のさまざまな実施形態を、ある程度詳細に、もしくは１つまたは複数の個々の実施形態に関連して上述したが、当業者は、本発明の精神または範囲から逸脱することなく開示した実施形態に対し多数の変更を行うことができる。すべての方向に関する言及（たとえば、近位の、遠位の、上位の、下位の、上方へ、下方へ、左の、右の、横方向の、正面の、背面の、頂部の、底部の、上方の、下方の、垂直の、水平の、右回りのおよび左回りの）は、単に、読者による本発明の理解を助けるための識別目的のためにのみ使用されており、特に本発明の位置、向きまたは使用に関して限定をもたらすものではない。接続に関する言及（たとえば、付着された、結合された、連結されたおよび接合された）は、広く解釈されるべきであり、特に示さない限り、要素の集まりの間の中間部材と要素間の相対移動とを含んでもよい。したがって、接続に関する言及は、必ずしも、２つの要素が直接接続されかつ互いに固定関係にあることを暗示するとは限らない。上記説明に含まれるかまたは添付図面に示されるすべての事柄が、限定するものとしてではなく単に例示的なものとして解釈されるように意図されている。以下の特許請求の範囲において定義されるような本発明の基本要素から逸脱することなく、細部または構造の変更を行ってもよい。
【図面の簡単な説明】
【００３３】
【図１】本発明による、立体３次元画像を３次元表面画像に変換するプロセスのフローチャートである。
【図２】図１の収縮／膨張ステップのプロセスを詳述するフローチャートである。
【図３Ａ】さまざまなサイズのボクセルグループに対する図２の収縮／膨張プロセスの動作を表す概略図である。
【図３Ｂ】さまざまなサイズのボクセルグループに対する図２の収縮／膨張プロセスの動作を表す概略図である。
【図３Ｃ】さまざまなサイズのボクセルグループに対する図２の収縮／膨張プロセスの動作を表す概略図である。
【図３Ｄ】さまざまなサイズのボクセルグループに対する図２の収縮／膨張プロセスの動作を表す概略図である。
【図４】図１のクラッタ除去ステップのプロセスを詳述するフローチャートである。
【図５Ａ】さまざまなサイズのボクセルグループに対する図４のクラッタ除去プロセスの動作を表す概略図である。
【図５Ｂ】さまざまなサイズのボクセルグループに対する図４のクラッタ除去プロセスの動作を表す概略図である。
【図５Ｃ】さまざまなサイズのボクセルグループに対する図４のクラッタ除去プロセスの動作を表す概略図である。
【図６】図１の高密度タイリングステップのプロセスを詳述するフローチャートである。
【図７Ａ】ボクセルを平面三角プレートに変換して３次元表面画像を形成する際の図６の高密度タイリングプロセスの効果を表す概略図である。
【図７Ｂ】ボクセルを平面三角プレートに変換して３次元表面画像を形成する際の図６の高密度タイリングプロセスの効果を表す概略図である。
【図８】図１の表面クリーニングステップのプロセスを詳述するフローチャートである。
【図９Ａ】３次元表面画像に対する図８の表面クリーニングプロセスの効果を表す概略図である。
【図９Ｂ】３次元表面画像に対する図８の表面クリーニングプロセスの効果を表す概略図である。
【図１０】図１のデシメーションステップのプロセスを詳述するフローチャートである。
【図１１Ａ】３次元表面画像に対する図１０のデシメーションプロセスの効果を表す概略図である。
【図１１Ｂ】３次元表面画像に対する図１０のデシメーションプロセスの効果を表す概略図である。
【図１２】図１の表面平滑化ステップのプロセスを詳述するフローチャートである。
【図１３Ａ】３次元表面画像に対する図１２の平滑化プロセスの動作および効果を表す概略図である。
【図１３Ｂ】３次元表面画像に対する図１２の平滑化プロセスの動作および効果を表す概略図である。
【図１３Ｃ】３次元表面画像に対する図１２の平滑化プロセスの動作および効果を表す概略図である。
【図１４】図１の小面法線計算ステップのプロセスを詳述するフローチャートである。
【図１５Ａ】３次元表面画像に対する図１４の小面法線計算プロセスの効果を表す概略図である。
【図１５Ｂ】３次元表面画像に対する図１４の小面法線計算プロセスの効果を表す概略図である。
【図１】
2009508583.tif 000003
【図２】
2009508583.tif 000004
【図３Ａ】
2009508583.tif 000005
【図３Ｂ】
2009508583.tif 000006
【図３Ｃ】
2009508583.tif 000007
【図３Ｄ】
2009508583.tif 000008
【図４】
2009508583.tif 000009
【図５Ａ】
2009508583.tif 000010
【図５Ｂ】
2009508583.tif 000011
【図５Ｃ】
2009508583.tif 000012
【図６】
2009508583.tif 000013
【図７Ａ】
2009508583.tif 000014
【図７Ｂ】
2009508583.tif 000015
【図８】
2009508583.tif 000016
【図９Ａ】
2009508583.tif 000017
【図９Ｂ】
2009508583.tif 000018
【図１０】
2009508583.tif 000019
【図１１Ａ】
2009508583.tif 000020
【図１１Ｂ】
2009508583.tif 000021
【図１２】
2009508583.tif 000022
【図１３Ａ】
2009508583.tif 000023
【図１３Ｂ】
2009508583.tif 000024
【図１３Ｃ】
2009508583.tif 000025
【図１４】
2009508583.tif 000026
【図１５Ａ】
2009508583.tif 000027
【図１５Ｂ】
2009508583.tif 000028
【国際調査報告】
2009508583.tif 000029
2009508583.tif 000030