(57)【要約】【課題】三次元モデルにおける空間の認識方法及び装置、並びにその装置を含む画像処理システムを提供する。【解決手段】三次元モデルの空間認識方法は、三次元モデルの輪郭線を介して互いに連結された頂点を同一の集合に分類するように、三次元モデルの頂点を分類するステップと、基準面に含まれる頂点の凸包を決定するステップであって、基準面は三次元モデルにおける、異なる集合に属する頂点を含む平面である、ステップと、条件である（イ）集合が凸包における頂点を含まないこと、及び（ロ）集合において、輪郭線を介して基準面に連結された頂点が基準面に対して三次元モデルの内側に位置することを満たしている集合により限定された空間を認識するステップと、を含む。【選択図】図１
2013175185.tif 000002
【特許請求の範囲】
【請求項１】
三次元モデルにおける空間を認識する方法であって、
前記三次元モデルの輪郭線を介して互いに連結された頂点を同一の集合に分類するように、前記三次元モデルの頂点を分類するステップと、
基準面に含まれる前記頂点の凸包を決定するステップであって、前記基準面は前記三次元モデルにおける、異なる集合に属する頂点を含む平面である、ステップと、
条件である（イ）前記集合が前記凸包における頂点を含まないこと、及び（ロ）前記集合において、輪郭線を介して前記基準面に連結された頂点が前記基準面に対して前記三次元モデルの内側に位置することを満たしている前記集合により限定された空間を認識するステップと、を含む三次元モデルの空間認識方法。
【請求項２】
前記三次元モデルを三角形メッシュで示している場合は、前記輪郭線を決定するステップにおいて、
共同の三角形メッシュ点を有する、前記三次元モデルのうちいずれか２つの平面から、前記共同の三角形メッシュ点の間の重複していない線分を抽出し、
条件である、前記共同の三角形メッシュ点を有する２つの平面はいずれも辺が前記線分と少なくとも一部重なっている三角形メッシュユニットを少なくとも一つ有すること、を満たしている前記線分を前記輪郭線として決定する請求項１に記載の三次元モデルの空間認識方法。
【請求項３】
三次元モデルにおける空間を認識する装置であって、
前記三次元モデルの輪郭線を認識する輪郭線認識手段と、
前記輪郭線を介して互いに連結された頂点を同一の集合に分類するように、前記三次元モデルの頂点を分類する頂点分類手段と、
前記三次元モデルにおける、異なる集合に属する頂点を含む平面を基準面として決定する基準面決定手段と、
前記基準面に含まれる前記頂点の凸包を決定する凸包決定手段と、
条件である（イ）前記集合が前記凸包における頂点を含まないこと、及び（ロ）前記集合において、輪郭線を介して前記基準面に連結された頂点が前記基準面に対して前記三次元モデルの内側に位置することを満たしている前記集合により限定された空間を認識する空間認識手段と、を含む三次元モデルの空間認識装置。
【請求項４】
前記輪郭線認識手段は、
共同の三角形メッシュ点を有する、三角形メッシュで示される前記三次元モデルのうちいずれか２つの平面から、前記共同の三角形メッシュ点の間の重複していない線分を抽出する線分抽出部と、
前記線分と前記共同の三角形メッシュ点を有する２つの平面それぞれの三角形メッシュユニットの辺とをマッチングする線分マッチング部と、を含み、
前記輪郭線認識手段は、前記共同の三角形メッシュ点を有する２つの平面はいずれも辺が前記線分と少なくとも一部重なっている三角形メッシュユニットを少なくとも一つ有する場合、前記線分を前記輪郭線として決定する請求項３に記載の三次元モデルの空間認識装置。
【請求項５】
請求項３又は４に記載の三次元モデルの空間認識装置を含む画像処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理に関し、具体的には、三次元モデルにおける空間の認識方法及び装置、並びにその装置を含む画像処理システムに関する。
【背景技術】
【０００２】
三次元モデルは豊富な情報を含むため、三次元モデルの分割、認識、マッチングなどの技術は広く注目されている。三次元モデルにおける穴（凹空間）は、重要な特徴の一つとして、補助モデル設計、モデルマッチング、モデル検索などの技術に用いられることができる。
【０００３】
従来のモデルにおける穴を認識する方法として、例えばモデルの各部分間の相互包括関係を分析する方法、又は補助線を手動で入力する方法などがある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来の方法は計算複雑度が高い、効率が低い。このため、本発明は、計算複雑度が低く、効率が高い、輪郭図及び平面幾何情報に基づく穴検出方法を提供する。
【課題を解決するための手段】
【０００５】
本発明の一の実施例は、三次元モデルにおける空間を認識する方法であって、前記三次元モデルの輪郭線を介して互いに連結された頂点を同一の集合に分類するように、前記三次元モデルの頂点を分類するステップと、基準面に含まれる前記頂点の凸包を決定するステップであって、前記基準面は前記三次元モデルにおける、異なる集合に属する頂点を含む平面である、ステップと、条件である（イ）前記集合が前記凸包における頂点を含まないこと、及び（ロ）前記集合において、輪郭線を介して前記基準面に連結された頂点が前記基準面に対して前記三次元モデルの内側に位置することを満たしている前記集合により限定された空間を認識するステップと、を含む三次元モデルの空間認識方法を提供する。
【０００６】
本発明の他の実施例は、三次元モデルにおける空間を認識する装置であって、前記三次元モデルの輪郭線を認識する輪郭線認識手段と、前記輪郭線を介して互いに連結された頂点を同一の集合に分類するように、前記三次元モデルの頂点を分類する頂点分類手段と、前記三次元モデルにおける、異なる集合に属する頂点を含む平面を基準面として決定する基準面決定手段と、前記基準面に含まれる前記頂点の凸包を決定する凸包決定手段と、条件である（イ）前記集合が前記凸包における頂点を含まないこと、及び（ロ）前記集合において、輪郭線を介して前記基準面に連結された頂点が前記基準面に対して前記三次元モデルの内側に位置することを満たしている前記集合により限定された空間を認識する空間認識手段と、を含む三次元モデルの空間認識装置を提供する。
【０００７】
本発明の他の実施例は、上記の三次元モデルの空間認識装置を含む画像処理システムを提供する。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施例に係る三次元モデルの空間認識方法の処理プロセスを示すフローチャート。
【図２】処理対象例である三次元モデルを示す図。
【図３】図２の三次元モデルにおける輪郭線を示す図。
【図４】本発明の一の実施例に係る方法により、三角形メッシュで示される三次元モデルの例の輪郭線認識を説明するための図。
【図５】図２の三次元モデルにおける頂点及び本発明の実施例に係る方法により頂点を分類して得られた頂点の集合を示す図。
【図６】図５に示される頂点の集合に基づいて決定された基準面及び該基準面における頂点の凸包を示す図。
【図７】図６に示される凸包における頂点を含まない集合における、基準面に対して三次元モデルの内側に位置する頂点を示す図。
【図８】本発明の実施例に係る三次元モデルの空間認識装置の配置例を示すブロック図。
【図９】本発明の装置及び方法を実施するコンピュータの構成例を示すブロック図。
【発明を実施するための形態】
【０００９】
以下、図面を参照しながら本発明の実施例を説明する。なお、説明の便宜上、図面及び発明詳細な説明には、本発明と関係のない、当業者として既知な部材及び処理について省略とされる。
【００１０】
図１は、本発明の実施例に係る三次元モデルの空間認識方法の処理プロセスを示すフローチャートである。
【００１１】
本発明の実施例に係る三次元モデルの空間認識方法では、ステップＳ１１０において、輪郭線を介して互いに連結された頂点を同一の集合に分類するように、三次元モデルの頂点を分類する。本技術分野における既知の方法で三次元モデルの輪郭線を決定してもよい。ステップＳ１２０において、基準面に含まれる頂点の凸包を決定する。ここで、基準面は三次元モデルにおける、異なる集合に属する頂点を含む平面である。ステップＳ１３０において、以下の条件：（イ）該集合が凸包における頂点を含まないこと、及び（ロ）該集合において、輪郭線を介して基準面に連結された頂点が基準面に対して三次元モデルの内側に位置することを満たしている、集合により限定された空間を認識する。
【００１２】
次に、図２に示される例示的な三次元モデル２００を例として、本発明の実施例に係る方法を説明する。
【００１３】
図２は、処理対象例である三次元モデル２００を示している。三次元モデル２００は、穴に類似する空間２１０を有する。空間２１０のような穴の特徴に対する認識は、三次元モデルの分割、マッチングなどの処理に対して重要である。
【００１４】
図３は、図２の三次元モデルの輪郭線を示しめしている。三次元モデルにおける平面及び輪郭線を認識するための従来技術は多種多様である。
【００１５】
特に、入力された三次元モデルは既知の三角形メッシュにより表示されてもよく、基本データ元素はモデルの頂点と、モデルの表面を構成する三角形とを含む。本発明の一の実施例によれば、三次元モデルを三角形メッシュで示している場合は、三次元モデルの輪郭線を以下の方式で決定してもよい。共同の三角形メッシュ点（即ち、三角形メッシュの頂点）を有する、三次元モデルのうちいずれか２つの平面から、これらの共同の三角形メッシュ点の間の重複していない線分を抽出し、（イ）共同の三角形メッシュ点を有する２つの平面はいずれも三角形メッシュユニットを少なくとも一つ有すること、及び（ロ）該三角形メッシュユニットの辺が線分と少なくとも一部重なっていることという条件を満たしている該線分を輪郭線として決定する。
【００１６】
図４は、本発明の一の実施例に係る方法により、三角形メッシュで示される三次元モデル４００の例の輪郭線認識を説明するための図。図４に示すように、三次元モデル４００の平面は、三角形メッシュユニットに分割されている。交わる一対の平面Ｐ１及びＰ２を例とすると、平面Ｐ１とＰ２は共同の三角形メッシュ点Ａ、Ｂ、Ｃ及びＤを有することと確定される。これらの三角形メッシュ点の間の重複していない線分は、ＡＢ、ＢＣ及びＣＤを含む。線分ＡＢについて、平面Ｐ１には辺が線分ＡＢと重なる三角形メッシュユニットＴ１１が存在し、平面Ｐ２には辺が線分ＡＢと重なる三角形メッシュユニットＴ２１が存在する。線分ＣＤについて、平面Ｐ１には辺が線分ＣＤと重なる三角形メッシュユニットＴ１２が存在し、平面Ｐ２には辺が線分ＣＤと重なる三角形メッシュユニットＴ２２が存在する。従って、線分ＡＢ及びＣＤを輪郭線として決定してもよい。線分ＢＣについて、平面Ｐ１及びＰ２には、辺が線分ＢＣの少なくとも一部と重なる三角形メッシュユニットが存在していないため、線分ＢＣが輪郭線ではないと決定される。このように、他の交わる平面間の輪郭線を決定してもよい。
【００１７】
また、三次元モデルは三角形メッシュの形式を有する場合は、三角形メッシュの表示において、三次元モデルの平面は三角形メッシュにより完全に覆われる必要があるため、三次元モデルの頂点は通常三角形メッシュの頂点に対応する。また、最小の数の三角形で三次元モデルの平面を覆う必要があるため、三次元モデル頂点でない位置には通常三角形メッシュの頂点が存在していない。
【００１８】
従って、三角形メッシュで三次元モデルを表示する場合は、三角形メッシュで表示された三次元モデルに含まれる三角形メッシュ点情報を用いて、三次元モデルの輪郭線及び頂点をより小さい計算複雑度で決定することができる。また、入力された三次元モデルが他の形式、例えばスキャンして生じた点群モデル、各種のモデリングツールで生じたパラメータ化モデル、又は多角形（三角形ではない）メッシュで表示されたモデルの場合は、各種の従来技術でこのような形式で表示された三次元モデルを三角形メッシュの形式に変換してもよい。
【００１９】
次に、図５乃至図７を参照しながら、本発明の実施例に係る方法のステップＳ１１０〜Ｓ１３０を説明する。
【００２０】
図５は、図２の三次元モデル２００における頂点及び本発明の実施例に係る方法（ステップＳ１１０）により三次元モデル２００の頂点を分類して得られた頂点の集合を示している。図５において、「●」により示される第１の頂点集合は輪郭線を介して互いに連結され、「★」により示される第２の頂点集合は輪郭線を介して互いに連結され、第１の集合と第２の集合との頂点間は輪郭線により連結されていない。
【００２１】
図６は、本発明の実施例に係る方法（ステップＳ１２０）により、図５に示される頂点の集合に基づいて決定された基準面及び該基準面における頂点の凸包を示している。該基準面は、第１の集合における頂点Ｍ、Ｎ等を含み、第２の集合における頂点Ｐ、Ｑ等を含む。図６には、基準面上の凸包の頂点を「○」により示している。平面における点の凸包を決定する方法は既知であり、ここに省略とされる。
【００２２】
次に、ステップＳ１３０において、まず凸包上の頂点を含まない集合を決定する。図６に示すように、第１の集合は基準面上の凸包における頂点を含み、第２の集合は凸包における頂点を含まない。ステップＳ１３０において、凸包における頂点を含まない第１の集合について、該集合における輪郭線を介して基準面に連結された頂点が基準面に対して三次元モデルの内側に位置するか否かをさらに決定する。図７に示すように、第２の集合において、輪郭線を介して基準面に連結された頂点（「☆」で示す）は、基準面に対して三次元モデルの内側に位置する。従って、ステップＳ１３０において、上述した２つの条件を満たしている頂点集合（この例では第２の集合）により限定された空間を、三次元モデルにおける穴に類似する空間として認識する。ここに示される例では、第２の集合において、基準面における頂点以外の頂点（「☆」で示される頂点）の全ては、輪郭線を介して基準面に連結される（即ち直接に連結）ことが可能となる。しかし、他の例では、輪郭線及び他の頂点を介して基準面に連結される（即ち間接に連結）頂点が存在する。一つの実施例では、ステップＳ１３０において、基準面に直接に連結された頂点のみが三次元モデルの内側に位置するか否かを判断してもよい。
【００２３】
頂点が基準面に対して三次元モデルの内側に位置するか否かを決定する方法は様々である。例えば、三角形メッシュで三次元モデルを表示する場合は、三角形メッシュの正の方向は三次元モデルの外側に向ける方向に対応してもよい。よって、三角形メッシュにより構成された基準面の正の方向（例えば、図７において、基準面の正の方向を矢印により示している）を決定することができ、三次元モデルの頂点が基準面の負の方向に位置する場合は、これらの頂点が基準面に対して三次元モデルの内側に位置すると決定してもよい。
【００２４】
図８は、本発明の実施例に係る三次元モデルの空間認識装置８００の配置例を示すブロック図である。
【００２５】
三次元モデルの空間認識装置８００は、輪郭線認識装置８１０、頂点分類装置８２０、基準面決定装置８３０、凸包決定装置８４０、及び空間認識装置８５０を含む。
【００２６】
輪郭線認識装置８１０は、三次元モデルの輪郭線を認識する。頂点分類装置８２０は、輪郭線を介して互いに連結された頂点を同一の集合に分類するように、三次元モデルの頂点を分類する。基準面決定装置８３０は、三次元モデルにおける、異なる集合に属する頂点を含む平面を基準面として決定する。凸包決定装置８４０は、基準面に含まれる頂点の凸包を決定する。空間認識装置８５０は、（イ）集合が凸包における頂点を含まないこと、及び（ロ）集合において、輪郭線を介して基準面に連結された頂点が基準面に対して三次元モデルの内側に位置する、という条件を満たしている該集合により限定された空間を認識する。
【００２７】
本発明の一つの実施例によれば、輪郭線認識装置は、線分抽出部と線分マッチング部と（図示せず）を含んでもよい。線分抽出部は、共同の三角形メッシュ点を有する、三角形メッシュで示される三次元モデルのうちいずれか２つの平面から、共同の三角形メッシュ点の間の重複していない線分を抽出する。線分マッチング部は、線分と共同の三角形メッシュ点を有する２つの平面それぞれの三角形メッシュユニットの辺とをマッチングする。輪郭線認識手段は、（イ）共同の三角形メッシュ点を有する２つの平面はいずれも三角形メッシュユニットを少なくとも一つ有し、且つ（ロ）該三角形メッシュユニットの辺が線分と少なくとも一部重なっている場合、線分を輪郭線として決定する。
【００２８】
また、本発明の一つの実施例によれば、三角形メッシュで表示された三次元モデルについて、頂点分類装置８２０は、三角形メッシュ点を三次元モデルの頂点として分類してもよい。
【００２９】
本発明の一の実施例に係る画像処理システムは、上述した三次元モデルの空間認識装置を含む。この画像処理システムは、例えば目標検出システム、局部マッチングシステム、モデル検索システム等であってもよい。
【００３０】
本発明に係る三次元モデルの空間認識方法、装置及び画像処理システムは、三次元モデルにおける平面の情報を利用して、三次元モデルの輪郭抽出及び穴認識を、計算複雑度が低く、効率が高く行うことができる。
【００３１】
なお、本発明は装置、方法又はコンピュータプログラムのプロダクトであってもよいことは、当業者にとって理解される。このため、本発明は以下の具体的な形式で実現されてもよく、例えば、完全なハードウェア、完全なソフトウェア（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、又はソフトウェア部とハードウェア部との組み合わせであってもよい。また、本発明は如何なる有形の表現媒体におけるコンピュータソフトウェアのプロダクトを用いてもよく、該媒体にはコンピュータが使用可能なプログラムコードを含む。
【００３２】
本発明は、一つ又は複数のコンピュータが読取可能な媒体の如何なる組み合わせを用いてもよい。コンピュータ読取可能な媒体は、コンピュータが読取可能な信号媒体又は記憶媒体であってもよく、コンピュータが読取可能な記憶媒体は電気的、磁気的、光学的、電磁的、赤外線の、又は半導体のシステム、装置、機器の部分品、伝播媒体、或いはそれらの適当な組み合わせであってもよいが、ここに例示されるものに限定されない。コンピュータが読取可能な記憶媒体は、より具体的な例として、一つ又は複数の導線間の電気接続、携帯可能なコンピュータディスク、ハードディスク、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去及びプログラム可能読取り専用記憶装置（ＥＰＲＯＭ又はフラッシュメモリ）、光ファイバー、コンパクトディスク（ＣＤ−ＲＯＭ）、光学記憶装置、磁気記憶装置、又はそれらの適当な組みあわせを含む。本明細書では、コンピュータが読取可能な記憶媒体は、指令実行システム、装置若しくは機器に適用される、又は指令実行システム、装置若しくは機器に関するプログラムを含む或いは記憶する、如何なる有形媒体であってもよい。
【００３３】
本発明を実行するための操作のコンピュータプログラムコードは、一つのプログラミング言語又は複数のプログラミング言語の如何なる組み合わせで開発してもよく、プログラミング言語は、例えばＪａｖａ(登録商標)、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋などのオブジェクト指向プログラミング言語を含み、例えば「Ｃ」プログラミング言語又は類似なプログラミング言語などの通常の手続き型プログラミング言語をさらに含む。プログラムコードは完全にユーザのコンピュータで実行してもよいし、部分的にユーザのコンピュータで実行してもよいし、独立のソフトウェアパッケージとして実行してもよいし、一部がユーザのコンピュータで実行し一部がリモートコンピュータで実行してもよいし、完全にリモートコンピュータ又はサーバで実行してもよい。後者の場合は、リモートコンピュータは、例えば地域ネットワーク（ＬＡＮ）又は広域ネットワーク（ＷＡＮ）などの如何なるネットワークを介してユーザのコンピュータに接続されてもよいし、或いは（インターネットのプロバイダによるインターネットを介して）外部コンピュータに接続されてもよい。
【００３４】
図９は、本発明の装置及び方法を実施するコンピュータの構成例を示すブロック図である。
【００３５】
図９において、中央処理ユニット（ＣＰＵ）９０１が、リードオンリーメモリ（ＲＯＭ）９０２に記憶されているプログラム、又は記憶部９０８からランダムアクセスメモリ（ＲＡＭ）９０３にロードされているプログラムに基づいて各種の処理を行う。ＲＡＭ９０３は、必要に応じてＣＰＵ９０１が各種の処理などを実行するときに必要なデータを記憶してもよい。
【００３６】
ＣＰＵ９０１、ＲＯＭ９０２及びＲＡＭ９０３は、バス９０４を介して互いに接続される。また、入力／出力インターフェース９０５もバス９０４に接続される。
【００３７】
入力／出力インターフェース９０５には、入力部９０６（キーボード、マウスなどを含む）、出力部分９０７（例えばＣＲＴなどの表示器、液晶表示装置（ＬＣＤ）、スピーカーなどを含む）、記憶部９０８（ハードディスクなどを含む）、及び通信部９０９（例えばＬＡＮカードなどのネットワーク接続カード、モデムなどを含む）が接続される。通信部９０９は、ネットワーク例えばインターネットを介して通信処理を行う。
【００３８】
駆動装置（ドライブ）９１０は、必要に応じて入力／出力インターフェース９０５に接続されてもよい。また、必要に応じて、例えば磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどの取り外し可能な媒体９１１を駆動装置９１０にセットすることにより、その中から読み出したコンピュータプログラムを記憶部９０８にインストールしてもよい。
【００３９】
ソフトウェアにより上述の一連の処理を実現する場合は、ネットワーク例えばインターネット、又は記憶媒体例えば取り外し可能な媒体９１１から、このソフトウェアを構成するプログラムをインストールしてもよい。
【００４０】
なお、当業者が理解すべきこととしては、このような記憶媒体は、中にプログラムが記憶されており、ユーザにプログラムを提供するよう装置と独立して配られる図９に示すような取り外し可能な媒体９１１に限定されないということである。取り外し可能な媒体９１１の例としては、磁気ディスク（フロッピーディスク（登録商標）を含む）、光ディスク（ＣＤ−ＲＯＭ及びＤＶＤを含む）、光磁気ディスク（ＭＤ（登録商標）を含む）、及び半導体メモリを含む。或いは、記憶媒体はＲＯＭ９０２、記憶部９０８に含まれるハードディスクなどであってもよく、それらにはプログラムが記憶されており、且つそれらを含む装置とともにユーザに配られてもよい。
【００４１】
上記の説明は、本発明の好適な実施例に過ぎず、本発明の実施の範囲がこれらに限定されず、本発明の特許請求の範囲及び明細書の内容に基づいて、当業者によって任意の変更及び変形が可能であり、本発明の保護範囲は特許請求の範囲を基準とする。また、本発明の実施例又は特許請求の範囲は何れも本発明により開示された目的又は利点又は特徴の全てを必ずしも実現する必要はない。さらにまた、本明細書及び特許請求の範囲に言及される「第１の」、「第２の」等の用語は、単なる構成要素を命名する、或いは異なる実施例又は範囲を区別するものであり、構成要素の数の上限又は下限を限定するものではない。
【００４２】
また、上述の各実施例を含む実施形態に関し、更に以下の付記を開示する。
【００４３】
（付記１）
三次元モデルにおける空間を認識する方法であって、
前記三次元モデルの輪郭線を介して互いに連結された頂点を同一の集合に分類するように、前記三次元モデルの頂点を分類するステップと、
基準面に含まれる前記頂点の凸包を決定するステップであって、前記基準面は前記三次元モデルにおける、異なる集合に属する頂点を含む平面である、ステップと、
条件である（イ）前記集合が前記凸包における頂点を含まないこと、及び（ロ）前記集合において、輪郭線を介して前記基準面に連結された頂点が前記基準面に対して前記三次元モデルの内側に位置することを満たしている前記集合により限定された空間を認識するステップと、を含む三次元モデルの空間認識方法。
【００４４】
（付記２）
前記三次元モデルを三角形メッシュで示している場合は、前記輪郭線を決定するステップにおいて、
共同の三角形メッシュ点を有する、前記三次元モデルのうちいずれか２つの平面から、前記共同の三角形メッシュ点の間の重複していない線分を抽出し、
条件である、前記共同の三角形メッシュ点を有する２つの平面はいずれも辺が前記線分と少なくとも一部重なっている三角形メッシュユニットを少なくとも一つ有すること、を満たしている前記線分を前記輪郭線として決定する付記１に記載の三次元モデルの空間認識方法。
【００４５】
（付記３）
三次元モデルにおける空間を認識する装置であって、
前記三次元モデルの輪郭線を認識する輪郭線認識手段と、
前記輪郭線を介して互いに連結された頂点を同一の集合に分類するように、前記三次元モデルの頂点を分類する頂点分類手段と、
前記三次元モデルにおける、異なる集合に属する頂点を含む平面を基準面として決定する基準面決定手段と、
前記基準面に含まれる前記頂点の凸包を決定する凸包決定手段と、
条件である（イ）前記集合が前記凸包における頂点を含まないこと、及び（ロ）前記集合において、輪郭線を介して前記基準面に連結された頂点が前記基準面に対して前記三次元モデルの内側に位置することを満たしている前記集合により限定された空間を認識する空間認識手段と、を含む三次元モデルの空間認識装置。
【００４６】
（付記４）
前記輪郭線認識手段は、
共同の三角形メッシュ点を有する、三角形メッシュで示される前記三次元モデルのうちいずれか２つの平面から、前記共同の三角形メッシュ点の間の重複していない線分を抽出する線分抽出部と、
前記線分と前記共同の三角形メッシュ点を有する２つの平面それぞれの三角形メッシュユニットの辺とをマッチングする線分マッチング部と、を含み、
前記輪郭線認識手段は、前記共同の三角形メッシュ点を有する２つの平面はいずれも辺が前記線分と少なくとも一部重なっている三角形メッシュユニットを少なくとも一つ有する場合、前記線分を前記輪郭線として決定する付記３に記載の三次元モデルの空間認識装置。
【００４７】
（付記５）
付記３又は４に記載の三次元モデルの空間認識装置を含む画像処理システム。
【００４８】
（付記６）
コンピュータに、付記１又は２に記載の各ステップを実行させるためのプログラム。
【００４９】
（付記７）
付記６に記載のプログラムを記憶しているコンピュータ読み出し可能な記憶媒体。
【００５０】
以上、本発明の好ましい実施形態、実施例を説明したが、本発明はこの実施形態、実施例に限定されず、本発明の趣旨を離脱しない限り、本発明に対するあらゆる変更は本発明の技術範囲に属する。
【図１】
2013175185.tif 000003
【図２】
2013175185.tif 000004
【図３】
2013175185.tif 000005
【図４】
2013175185.tif 000006
【図５】
2013175185.tif 000007
【図６】
2013175185.tif 000008
【図７】
2013175185.tif 000009
【図８】
2013175185.tif 000010
【図９】
2013175185.tif 000011