(57)【特許請求の範囲】
【請求項１】
モデルの形状記述子としてｎ次元ベクトルを生成する方法であって、
前記ベクトルのｎ個のエレメントのうちの１つであり、前記モデルの基本形状を記述する前記ベクトルのタイプエレメントを決定するステップと、
前記タイプエレメント以外の前記ベクトルのｎ−１個のエレメントであるメトリックエレメントを計算するステップと
を有し、
前記メトリックエレメントの夫々は、前記タイプエレメントの関数として分けられる前記モデルのｎ−１個のレイヤのいずれか１つに関連し、該関連するレイヤに前記モデルの全ての特徴のうちの幾つが入るかを示す前記モデルの特徴の構成比を表す、方法。
【請求項２】
前記モデルは、３Ｄモデルである、
請求項１に記載の方法。
【請求項３】
前記特徴は、前記３Ｄモデルの頂点、三角形、又はエッジを有する、
請求項２に記載の方法。
【請求項４】
前記３Ｄモデルの基本形状は、立方体、球、及び円柱を有する、
請求項２に記載の方法。
【請求項５】
前記基本形状は、平面、開放円柱、円柱、楕円、及び球を有する、
請求項２に記載の方法。
【請求項６】
前記タイプエレメントは、前記３Ｄモデルの共分散行列の３つの固有値の関数として計算される、
請求項４に記載の方法。
【請求項７】
前記タイプエレメントは、整数である、
請求項１乃至６のうちいずれか一項に記載の方法。
【請求項８】
前記３Ｄモデルの境界ボックスは、前記タイプエレメントに従って決定されるｎ−１個の埋め込み形状によって分けられる、
請求項３に記載の方法。
【請求項９】
前記メトリックエレメントは全て、浮動小数である、
請求項１に記載の方法。
【請求項１０】
前記メトリックエレメントのうちの１つは、ｎ−１個のレイヤのうちの１つに入る前記３Ｄモデルの特徴の構成比の正規化によって計算される、
請求項８に記載の方法。
【請求項１１】
モデルの形状記述子としてｎ次元ベクトルを生成する装置であって、
前記ベクトルのｎ個のエレメントのうちの１つであり、前記モデルの基本形状を記述する前記ベクトルのタイプエレメントを決定する手段と、
前記タイプエレメント以外の前記ベクトルのｎ−１個のエレメントであるメトリックエレメントを計算する手段と
を有し、
前記メトリックエレメントの夫々は、前記タイプエレメントの関数として分けられる前記モデルのｎ−１個のレイヤのいずれか１つに関連し、該関連するレイヤに前記モデルの全ての特徴のうちの幾つが入るかを示す前記モデルの特徴の構成比を表す、装置。
【請求項１２】
モデルの形状記述子としてｎ次元ベクトルを生成する装置であって、
前記ベクトルのｎ個のエレメントのうちの１つであり、前記モデルの基本形状を記述する前記ベクトルのタイプエレメントを決定し、
前記タイプエレメント以外の前記ベクトルのｎ−１個のエレメントであるメトリックエレメントを計算する
よう構成されるプロセッサを有し、
前記メトリックエレメントの夫々は、前記タイプエレメントの関数として分けられる前記モデルのｎ−１個のレイヤのいずれか１つに関連し、該関連するレイヤに前記モデルの全ての特徴のうちの幾つが入るかを示す前記モデルの特徴の構成比を表す、装置。
【請求項１３】
前記モデルは、３Ｄモデルである、
請求項１２に記載の装置。
【請求項１４】
前記特徴は、前記３Ｄモデルの頂点、三角形、又はエッジを有する、
請求項１３に記載の装置。
【請求項１５】
前記３Ｄモデルの基本形状は、立方体、球、及び円柱を有する、
請求項１３に記載の装置。
【請求項１６】
前記基本形状は、平面、開放円柱、円柱、楕円、及び球を有する、
請求項１３に記載の装置。
【請求項１７】
前記タイプエレメントは、前記３Ｄモデルの共分散行列の３つの固有値の関数として計算される、
請求項１５に記載の装置。
【請求項１８】
前記タイプエレメントは、整数である、
請求項１２乃至１７のうちいずれか一項に記載の装置。
【請求項１９】
前記３Ｄモデルの境界ボックスは、前記タイプエレメントに従って決定されるｎ−１個の埋め込み形状によって分けられる、
請求項１４に記載の装置。
【請求項２０】
前記メトリックエレメントは全て、浮動小数である、
請求項１２に記載の装置。
【請求項２１】
前記メトリックエレメントのうちの１つは、ｎ−１個のレイヤのうちの１つに入る前記３Ｄモデルの特徴の構成比の正規化によって計算される、
請求項１９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、コンピュータグラフィクスに係る。特に、本発明は、モデルの形状記述子を生成する方法及び装置に係る。
【背景技術】
【０００２】
３Ｄ形状記述子は、通常、完全な３Ｄモデル又は３Ｄモデルの一部分の特徴を定義するｎ次元ベクトルであり、コンピュータグラフィクス技術における基本ツールの１つである。３Ｄ形状記述子は、検索、対称性の発見、及びモデリングのような、多くの３Ｄモデルプロセッシングタスクにおいて幅広く使用されている。
【０００３】
MITRA,  N.  J.，GUIBAS,  L.  J.，及びPAULY,  M.，“Partial  and  approximate  symmetry  detection  for  3D  geometry”，ACM  Trans.  Gr.  25，3，560.568，2006年（非特許文献１）は、サンプル点の形状記述子として同じ点にある曲率テンソルの比を使用することを提案している。
【０００４】
弁別性能を改善するよう、多数の形状記述子が提案されてきた。以下の文献は、既知の３Ｄ形状記述子の幾つかの例について論じている：
（１）３Ｄ形状コンテクスト（M.  Kortgen，G.-J.  Park，M.  Novotni，及びR.  Klein，“3D  Shape  Matching  with  3D  Shape  Contexts”，the  7th  Central  European  Seminar  on  Computer  Graphics，2003年（非特許文献２））；
（２）スピンイメージ（A.  E.  Johnson及びM.  Herbert，“Using  Spin  Images  for  Efficient  Object  Recognition  in  Cluttered  3D  Scenes”，IEEE  Trans.  on  PAMI，21(5)，pp.433-449，1999年（非特許文献３））；
（３）形状分布（R.  Osada，T.  Funkhouser，B.  Chazelle，及びD.  Dobkin，“Shape  Distributions”，ACM  Trans.  on  Graphics，21(4)，pp.807-832，2002年（非特許文献４））。
【０００５】
上記の文献（１）で記載されている形状コンテクストは、３Ｄ形状の検索及び照合のために、S.  Belongie，J.  Malik及びJ.  Puzicha，“Shape  Matching  and  Object  Recognition  Using  Shape  Contexts”，IEEE  Trans.  on  PAMI，24(4)，pp.509-522，2002年（非特許文献５）において提案されている２Ｄ形状コンテクストが自然に発展したものに当たり、基準点でそれに対する残りの点の分布を捕捉して定義される。上記の文献（２）で記載されるスピンイメージは、２Ｄヒストグラムとして表されるデータレベルの形状記述子である。文献（１）及び（２）のそれら２つのアプローチは、局所的なポイントサンプルジオメトリの統計値に基づき、メッシュ、ポリゴンスープ、及び向きを持ったポイントクラウドのような、様々な形状表現のためのアプローチである。
【０００６】
上記の文献（３）で記載されている形状分布は、代表的な大域的形状記述子であり、オブジェクトのシグニチャが、オブジェクトの大域的な幾何学的特性を測定する形状関数からサンプリングされる形状分布として表される。形状弁別関数を如何にして選択すべきかと、それらをサンプリングする有効な方法を如何にして開発すべきかとに関して、このアプローチには課題が存在する。J.  W.  H.  Tangelder，R.  C.  Veltkamp，“A  Survey  of  Content  Based  3D  Shape  Retrieval  Methods”，Shape  Modeling  International，pp.145-156，2004年（非特許文献６）では、様々な大域的／局所的な形状記述子が３Ｄモデル検索のタスクのために精査されている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】MITRA,  N.  J.，GUIBAS,  L.  J.，及びPAULY,  M.，“Partial  and  approximate  symmetry  detection  for  3D  geometry”，ACM  Trans.  Gr.  25，3，560.568，2006年
【非特許文献２】M.  Kortgen，G.-J.  Park，M.  Novotni，及びR.  Klein，“3D  Shape  Matching  with  3D  Shape  Contexts”，the  7th  Central  European  Seminar  on  Computer  Graphics，2003年
【非特許文献３】A.  E.  Johnson及びM.  Herbert，“Using  Spin  Images  for  Efficient  Object  Recognition  in  Cluttered  3D  Scenes”，IEEE  Trans.  on  PAMI，21(5)，pp.433-449，1999年
【非特許文献４】R.  Osada，T.  Funkhouser，B.  Chazelle，及びD.  Dobkin，“Shape  Distributions”，ACM  Trans.  on  Graphics，21(4)，pp.807-832，2002年
【非特許文献５】S.  Belongie，J.  Malik及びJ.  Puzicha，“Shape  Matching  and  Object  Recognition  Using  Shape  Contexts”，IEEE  Trans.  on  PAMI，24(4)，pp.509-522，2002年
【非特許文献６】J.  W.  H.  Tangelder，R.  C.  Veltkamp，“A  Survey  of  Content  Based  3D  Shape  Retrieval  Methods”，Shape  Modeling  International，pp.145-156，2004年
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、３Ｄ形状記述子を計算する現在のアルゴリズムの大部分は、完璧な（watertight）３Ｄモデル、すなわち、滑らかな表面及び密な頂点分布を備えた３Ｄモデル、のために設計されている。完璧でない（non-watertight）３Ｄモデルの例が図１に示されている。前述のアルゴリズムは、完璧でない３Ｄモデル、例えば、建築及び機械ＣＡＤモデルのような、鋭角な造作及び粗な頂点分布を備えた３Ｄモデル、に適さない。そして、実時間３Ｄモデル検索のような幾つかのアプリケーションは、３Ｄ形状記述子を計算するための高速なアルゴリズムを必要とする。
【０００９】
従って、完璧でない３Ｄモデルに有効である、３Ｄモデルの形状記述子を生成する方法及び装置の必要性が存在する。
【課題を解決するための手段】
【００１０】
本発明の一態様に従って、モデルの形状記述子としてｎ次元ベクトルを生成する方法が提供される。方法は、前記モデルの基本形状を記述する前記ベクトルのタイプエレメントを決定するステップと、前記ベクトルのｎ−１個のメトリックエレメントを計算するステップとを有し、前記メトリックエレメントの夫々は、前記タイプエレメントの関数として分けられるｎ−１個のレイヤのうちの１つに入る前記モデルの特徴の構成比を表す。
【００１１】
本発明の他の態様に従って、モデルの形状記述子としてｎ次元ベクトルを生成する装置が提供される。装置は、前記モデルの基本形状を記述する前記ベクトルのタイプエレメントを決定する手段と、前記ベクトルのｎ−１個のメトリックエレメントを計算する手段とを有し、前記メトリックエレメントの夫々は、前記タイプエレメントの関数として分けられるｎ−１個のレイヤのうちの１つに入る前記モデルの特徴の構成比を表す。
【００１２】
本発明の他の態様に従って、ｎ次元ベクトルであるモデルの形状記述子が提供される。形状記述子は、前記モデルの基本形状を記述するタイプエレメントと、前記ベクトルのｎ−１個のメトリックエレメントとを有し、前記メトリックエレメントの夫々は、前記タイプエレメントの関数として分けられるｎ−１個のレイヤのうちの１つに入る前記モデルの特徴の構成比を表す。
【００１３】
本発明の更なる態様及び利点は、本発明の以下の詳細な説明において知られることが理解されるべきである。
【図面の簡単な説明】
【００１４】
【図１】完璧でない３Ｄモデルの例を示す図である。
【図２】タイプエレメントに従う３Ｄモデルの境界ボックスの分割を示す図である。
【図３】２Ｄ形状のメトリックベクトルエレメントの計算のためのプロセスを示す図である。
【図４】本発明の実施形態に従って計算される３Ｄ形状記述子により３Ｄモデルを構成する方法のフローチャートを示すブロック図である。
【図５】本発明の実施形態に従って計算される３Ｄ形状記述子により入力マルチコンポーネント３Ｄモデルの接続されたコンポーネントの中で反復構造を見つける方法のフローチャートを示すブロック図である。
【発明を実施するための形態】
【００１５】
添付の図面は、本発明の実施形態の原理を説明するのに役立つ記載とともに実施形態の更なる理解を提供するよう包含される。本発明は、実施形態に制限されない。
【００１６】
本発明の実施形態が、これから、図面に関連して詳細に記載される。以下の記載において、既知の機能及び構成の幾つかの詳細な記載は、簡潔さのために省略されることがある。
【００１７】
本発明の実施形態に従って、複雑でない３Ｄモデルの形状記述子を生成する方法が提供される。この方法はロバストであり、完璧でない３Ｄモデルを有効に処理することができる。本発明の実施形態は、３Ｄモデリング及び対称性発見メッシュの単純化のために使用可能であり、このとき、入力メッシュで検出されるマルチスケールの反復構造は、程度が異なる詳細さで保たれ得る。
【００１８】
本発明の実施形態に従う方法において、ｎ次元ベクトルが、３Ｄモデルの形状を定義するよう形状記述子として生成された。本発明の実施形態では、１１次元ベクトルが記載される。すなわち、３Ｄ形状記述子のベクトルは、１１のエレメントを含む。なお、当業者は、ｎが如何なる整数値であってよいと十分に理解することができる。更なる精度は、形状記述子の目的で、より大きい次元を有するベクトルについて期待される。
【００１９】
本発明の実施形態に従って、ベクトルの１１のエレメントのうちの１つは、３Ｄモデルの基本形状を記述するよう決定され、タイプエレメントと呼ばれ得る。３Ｄモデルの基本形状セットは当該技術で知られており、本発明の状況に応じて設定され得る。一例において、基本形状セットは、立方体、球、及び円柱を有する。他の例では、基本形状セットは、平面、開放円柱（底面及び天面がない円柱）、円柱、楕円、及び球を有することができる。
【００２０】
タイプエレメントは整数であることができ、例えば、立方体について０、球について１、及び円柱について２、あるいは、平面について０、開放円柱について１、円柱について２、楕円について３、及び球について４をとる。
【００２１】
３Ｄモデルのタイプエレメントは、３Ｄモデルの共分散行列の３つの固有値に従って計算され得る。例えば、立方体、球、及び円柱を有する基本形状セットに関し、タイプエレメントは次のように計算され得る：
３つの固有値が明らかな差を有する、すなわち、２番目に大きい値が最も大きい値の９５％より小さく且つ最も小さい値が２番目に小さい値の９５％よりも小さい場合、タイプエレメントは０、すなわち、立方体に設定される。
【００２２】
２つの値のみが十分に近い、すなわち、一方が他方の９５％内にある場合、タイプエレメントは１、すなわち、円柱に設定される。
【００２３】
他の場合に関し、３つの値は十分に近く、タイプエレメントは２、すなわち、球に設定される。
【００２４】
次に、ベクトルの残り１０のエレメントは、タイプエレメントに従って分割される異なるレイヤに入る３Ｄモデルの境界ボックス上の特徴の構成比を表すよう決定され、それらの夫々は、メトリックベクトルエレメントと呼ばれる。３Ｄモデルの特徴は、３Ｄモデルの頂点、三角形、又はエッジであることができる。
【００２５】
メトリックベクトルエレメントは全て浮動小数であることができ、次のように計算され得る。
【００２６】
次に、３Ｄモデルの境界ボックス上の全ての頂点によりベクトルのメトリックベクトルエレメントを決定する例が、詳細に説明される。
【００２７】
モデル正規化の後、３Ｄモデルの境界ボックスは、タイプエレメントに従って、１０のレイヤに分割され得る。図２は、タイプエレメントに従う３Ｄモデルの境界ボックスの分割を示す図である。
【００２８】
（ｉ）立方体に関し、１０の埋め込まれた立方体が、３Ｄモデル境界ボックスを分割するために使用される。全ての立方体は同じ中心、すなわち、３Ｄモデル中心を有する。立方体の長さは、０．１，０．２，・・・，１であり、これは、１つが他に含まれることを意味する。
【００２９】
（ｉｉ）円柱に関し、１０の埋め込まれた円柱が、３Ｄモデル境界ボックスを分割するために使用される。円柱の高さは、０．１，０．２，・・・，１であり、底面の半径は、０．０５×√２，０．１×√２，０．１５×√２，・・・，０．５×√２である。全ての円柱は同じ中心、すなわち、３Ｄモデル中心を有する。
【００３０】
（ｉｉｉ）球に関し、１０の埋め込まれた球が、３Ｄモデル境界ボックスを分割するために使用される。球の半径は、０．０５×√２，０．１×√２，０．１５×√２，・・・，０．５×√２である。全ての球は同じ中心、すなわち、３Ｄモデル中心を有する。
【００３１】
３Ｄモデル境界ボックスの分割の後、異なるレイヤに入る頂点が数えられ、初期メトリックベクトルエレメントが計算される。最終のメトリックベクトルは正規化によって求められる。
【００３２】
図３は、２Ｄ形状のメトリックベクトルエレメントの計算のためのプロセスを示す図である。
【００３３】
ハート様の形状が図３には示されている。境界ボックスは長方形状である。その形状のためのタイプエレメントは、例えば、（長方形についての）１に設定され得る。５次元ベクトルが２Ｄ形状の形状記述子として使用されるとする。すなわち、４つのメトリックベクトルエレメントが必要とされ、その場合に、境界ボックスは、図３に示されるように、同じ中心を有し且つ段々と小さくなる４つの長方形によって分割される。図３に示されるように、ハート様形状の境界ボックス上には、全部で１９の頂点が存在する（黒点で示される。）。そして、４つのレイヤの夫々には、１２（６３．２％）、５（２６．３％）、２（１０．５％）、０個の頂点が入る。よって、ハート様形状のベクトル形状記述子は（１，０．６３２，０．２６３，０．１０５，０．０）である。
【００３４】
メトリックベクトルエレメントの計算は、例示のために、２Ｄ形状に関して記載される。３Ｄモデルのためのプロセスは、同様であることが当業者によって認識される。
【００３５】
２つのモデルの間の類似度は、次のように定量的に計算され得る：
（１）２つの形状エレメントが等しくない場合、２つの３Ｄモデルの間の類似度は０である。
【００３６】
（２）形状エレメントが等しい場合、２つのメトリックベクトルのユークリッド距離は計算される。距離がｄであるとすると、その場合、２つの３Ｄモデルの間の類似度は１／ｄである。
【００３７】
本発明の他の実施形態は、３Ｄモデルの形状記述子としてｎ次元ベクトルを生成する対応する装置を提供する。装置は、３Ｄモデルの基本形状を記述するベクトルのタイプエレメントを決定する手段と、ベクトルのｎ−１個のメトリックエレメントを計算する手段とを有し、メトリックエレメントの夫々は、タイプエレメントの関数として分けられるｎ−１個のレイヤのうちの１つに入る３Ｄモデルの特徴の構成比を表す。
【００３８】
本発明の更なる実施形態は、３Ｄモデルの対応する形状記述子を提供する。形状記述子は、ｎ次元ベクトルであり、３Ｄモデルの基本形状を記述するタイプエレメントと、ベクトルのｎ−１個のメトリックエレメントとを有し、メトリックエレメントの夫々は、タイプエレメントの関数として分けられるｎ−１個のレイヤのうちの１つに入る３Ｄモデルの特徴の構成比を表す。
【００３９】
次に、本発明の実施形態の方法に従って計算される３Ｄ形状記述子の適用が、３Ｄモデリング及び反復構造の発見に関連して記載される。
【００４０】
複雑な３Ｄモデルを構成することは、複雑であり且つ時間がかかる。既存の３Ｄモデルの対称性発見結果に基づき、幾つかのパターンが、新しい３Ｄモデルを生成するために置換され得る。なお、パターン置換は、生成されるモデルを妥当なものとするためにモデルの全ての反復部分を直す必要があるので、面倒である。次に、本発明の実施形態に従って計算される３Ｄ形状記述子を用いて３Ｄモデルを構成する方法が、記載される。
【００４１】
３Ｄモデルを構成する方法に従って、既存のモデルの構造を解析することによって、３Ｄモデルの全ての反復構造が求められ、適切なモデルが、新しい３Ｄモデルを生成するよう幾つかのパターンを置換するためにライブラリから選択される。
【００４２】
図４は、本発明の実施形態に従って計算される３Ｄ形状記述子により３Ｄモデルを構成する方法のフローチャートを示すブロック図である。
【００４３】
ブロック４０１で、原モデルのマルチスケール反復構造（ＲＳ；Repetitive  Structures）が検出される。
【００４４】
原モデルのマルチスケール反復構造の検出のために、国際特許出願第ＰＣＴ／ＣＮ２０１０／０００９８４号（Kangying  Cai等、“Method  and  apparatus  for  detecting  repetitive  structures  in  3D  mesh  models”）に記載されている方法が使用されてよい。この特許文献によれば、有効な且つマルチスケールの方法が３Ｄモデルにおいて反復構造を検出するために提案されており、逓減的なサンプリングステップサイズによる繰り返し均等サンプリング方法が使用される。所与の３Ｄメッシュモデルは、相対的に大きい初期サンプリングステップサイズにより均等にサンプリングされる。次いで、サンプリング点がそれらの曲率に従ってクラスタ化され、次いで、同じクラスタに属するサンプリング点の間で変換が決定される。それらは、いわゆる候補変換（candidate  transformations）である。よって、候補変換は、両方の点が同様の曲率を有するようなサンプリング点の対についてのみ決定される必要がある。そのようなクラスタ化ステップは、アルゴリズム効率を改善するのみならず、アルゴリズム精度も高める。予め計算された全ての変換によって構成される変換空間は、サンプリングステップサイズがより小さい場合よりもノイズ成分が少ない。よって、続くクラスタ化ステップは、全ての反復構造を発見する可能性がより高い。モデルが反復構造を有する場合は、そのようなクラスタ化の有用な結果は、１又はそれ以上の個別的なクラスタが現れることである。次のステップで、（最も関連がある）クラスタが選択され、対応する変換及びサンプリング点の対は、反復構造を示すと考えられる。最も関連があるクラスタは、最も重要且つ明白であるクラスタである。クラスタに属さない他の変換は不要である。このプロシージャは、逓減的なステップサイズにより繰り返し実行される。夫々の繰り返しは反復をスキップし、モデルの残りの部分及び前の繰り返しにおいて検出された反復構造の代表のみを処理する。このように、３Ｄモデルにおけるマルチスケール反復構造も発見され得る。繰り返しプロセスは、反復構造の数が安定する場合に、又は所定の最小サンプリングステップサイズが到達される場合に、停止する。また、タイムアウトを定義し、プロセスのランタイムを測定し、ランタイムがタイムアウトを超える場合にプロセスを終了することも可能である。以上に基づき、入力モデルメッシュモデルＭのマルチスケール反復構造の検出は、上記の特許文献によって達成され得る。この結果は、本発明の実施形態において使用され得る。
【００４５】
図４のブロック４０１に示されるように、原モデルのマルチスケール反復構造１，２，・・・，ｎが検出される。原モデルにおいて検出された反復構造に基づき、局所的な反復部分は、図３の右側に示されるように、新しいモデルを生成するよう同様のオブジェクトにより置換され得る。
【００４６】
ブロック４０３で、パターンｉのベクトル３Ｄ形状記述子が計算される。最初に、パターンｉの向きが世界座標系と整列され、次いで、単位立方体へとスケーリングされる。次いで、整列されたパターンＩのベクトル３Ｄ形状記述子が計算される。
【００４７】
ブロック４０５で、３Ｄデータベースが、新しいパターンｉを見つけるために検索される。３Ｄモデルに加えて、３Ｄモデルのベクトル３Ｄ形状記述子はまた、３Ｄデータベースでも利用可能である。ベクトル３Ｄ形状記述子を比較することによって、古いパターンと最も類似する３Ｄデータベース内の新しいパターンが見つけられ得る。
【００４８】
ブロック４０７で、新しいインスタンスコンポーネントが計算される。新しいパターンは最初に、ブロック４０１によって計算された対応する古いパターンの同じ位置、向き及びスケーリング係数を有するよう変換される。次いで、新しいインスタンスは、変換後の新しいパターンと、原のインスタンス変換とから計算される。
【００４９】
図５は、本発明の実施形態に従って計算される３Ｄ形状記述子により入力マルチコンポーネント３Ｄモデルの接続されたコンポーネントの中で反復構造を見つける方法のフローチャートを示すブロック図である。
【００５０】
図５に示されるように、ブロック５０１で、全てのンポーネントは、それらの主曲率に従ってクラスタ化される。当該技術における既知のクラスタ化方法がこのステップで使用され得る。
【００５１】
ブロック５０３で、ブロック４０１の１つの結果として起こるコンポーネントクラスタ内のコンポーネントは更に、それらの形状記述子に従ってクラスタ化される。当該技術における既知のクラスタ化方法がこのステップで使用され得る。
【００５２】
ブロック５０５で、ブロック５０３の結果として起こるコンポーネントクラスタは結合される。２つのコンポーネントクラスタの代表的なコンポーネントが同じ反復構造に属する場合は、それら２つのコンポーネントクラスタは結合される。詳細なアルゴリズムは次のとおりであることができる：
void  Combine_Component_Cluster(void)
{
全ての代表的なコンポーネント対の距離を計算；
距離に応じて昇順に全ての代表的なコンポーネント対をソート；
For(ソートされた代表的なコンポーネント対ごと)
{
２つの代表的なコンポーネントを整列；
２つの代表的なコンポーネントの間の距離を計算；
If(代表的なコンポーネント距離<閾値)
対応する２つのコンポーネントクラスタを結合；
else
中止；
}
｝
２つのコンポーネントの間の距離は次のように計算される。
Component_Distance=a*component_principle_curvature_distance+
b*component_shape_descriptor_distance
ここで、a及びbはユーザ固有の定数である。
【００５３】
ブロック５０７で、夫々のコンポーネントクラスタ内の反復構造が発見される。夫々のコンポーネントは、それらが同じ反復構造に属するかどうかを決定するために、当該クラスタが属するコンポーネントクラスタの反復構造と比較される。詳細なアルゴリズムは次のとおりであることができる：
void  Discover_Repetitive_Structure_Inside_Component_Cluster(void)
{
For(コンポーネントクラスタCluster_iごと)
{
For(Cluster_iに属するコンポーネントcごと)
{
cとCluster_iの代表的なコンポーネントであるRepre_iとを整列；
cとCluster_iの代表的なコンポーネントとの間の距離を計算；
If(コンポーネント距離<閾値)
反復構造Repre_iに属するようcを付加；
else
新しい反復構造を追加し、その新しい反復構造にcを付加；
}
}
}
ブロック５０９で、ブロック５０１の結果として起こる反復構造が結合される。２つのコンポーネントクラスタの代表的なコンポーネントが同じようである場合は、それら２つのコンポーネントクラスタは結合される。
【００５４】
本発明は３Ｄモデルに関して記載されているが、当業者は、本発明が２Ｄ形状にも適用され得ることを十分に理解することができる。  
上記の実施形態に加えて、以下の付記を開示する。
（付記１）
モデルの形状記述子としてｎ次元ベクトルを生成する方法であって、
前記モデルの基本形状を記述する前記ベクトルのタイプエレメントを決定するステップと、
前記ベクトルのｎ−１個のメトリックエレメントを計算するステップと
を有し、
前記メトリックエレメントの夫々は、前記タイプエレメントの関数として分けられるｎ−１個のレイヤのうちの１つに入る前記モデルの特徴の構成比を表す、方法。
（付記２）
前記モデルは、３Ｄモデルである、
付記１に記載の方法。
（付記３）
前記特徴は、前記３Ｄモデルの頂点、三角形、又はエッジを有する、
付記２に記載の方法。
（付記４）
前記３Ｄモデルの基本形状は、立方体、球、及び円柱を有する、
付記２に記載の方法。
（付記５）
前記基本形状は、平面、開放円柱、円柱、楕円、及び球を有する、
付記２に記載の方法。
（付記６）
前記タイプエレメントは、前記３Ｄモデルの共分散行列の３つの固有値の関数として計算される、
付記４に記載の方法。
（付記７）
前記タイプエレメントは、整数である、
付記１乃至６のうちいずれか一つに記載の方法。
（付記８）
前記３Ｄモデルの境界ボックスは、前記タイプエレメントに従って決定されるｎ−１個の埋め込み形状によって分けられる、
付記３に記載の方法。
（付記９）
前記メトリックエレメントは全て、浮動小数である、
付記１に記載の方法。
（付記１０）
前記メトリックエレメントのうちの１つは、ｎ−１個のレイヤのうちの１つに入る前記３Ｄモデルの特徴の構成比の正規化によって計算される、
付記８に記載の方法。
（付記１１）
モデルの形状記述子としてｎ次元ベクトルを生成する装置であって、
前記モデルの基本形状を記述する前記ベクトルのタイプエレメントを決定する手段と、
前記ベクトルのｎ−１個のメトリックエレメントを計算する手段と
を有し、
前記メトリックエレメントの夫々は、前記タイプエレメントの関数として分けられるｎ−１個のレイヤのうちの１つに入る前記モデルの特徴の構成比を表す、装置。
（付記１２）
ｎ次元ベクトルであるモデルの形状記述子であって、
前記モデルの基本形状を記述するタイプエレメントと、
前記ベクトルのｎ−１個のメトリックエレメントと
を有し、
前記メトリックエレメントの夫々は、前記タイプエレメントの関数として分けられるｎ−１個のレイヤのうちの１つに入る前記モデルの特徴の構成比を表す、形状記述子。
【図１】
0005986681.tif 000002
【図２（ａ）】
0005986681.tif 000003
【図２（ｂ）】
0005986681.tif 000004
【図２（ｃ）】
0005986681.tif 000005
【図３】
0005986681.tif 000006
【図４】
0005986681.tif 000007
【図５】
0005986681.tif 000008