(57)【特許請求の範囲】
【請求項１】
3Dメッシュモデルにおいて反復構造を検出する方法であり、3Dメッシュモデルにおいて反復構造を検出する装置により実行される方法であって、
サンプリング手段により、現在のサンプリングステップサイズを使用して前記3Dメッシュモデルをサンプリングするステップと、
検出手段により、前記3Dメッシュモデル内で１つ以上の反復構造及び前記モデルの残りの部分を検出するステップ、並びに、判定手段により、前記１つ以上の反復構造のそれぞれについて標本を判定するステップと、
前記検出するステップが前記現在のサンプリングステップサイズを使用して１つ以上の反復構造を生じる限り、
低減手段により、前記現在のサンプリングステップサイズを低減し、低減されたサンプリングステップサイズを取得するステップと、
検出された反復構造のそれぞれの検出された標本及び前記モデルの前記残りの部分について、前記低減手段と前記サンプリング手段と前記検出手段と前記判定手段により実行されるステップを繰り返すステップと
を有し、
前記低減されたサンプリングステップサイズが前記現在のサンプリングステップサイズとして使用される方法。
【請求項２】
それぞれの検出するステップは、
それぞれの現在のサンプリングステップサイズに基づいてサンプリングポイント毎に曲率記述子を計算するステップと、
曲率記述子に従って前記サンプリングポイントをクラスタ化するステップであり、１つ以上のサンプリングポイントのクラスタが取得されるステップと、
共通のサンプリングポイントのクラスタに属するサンプリングポイントの対の間で変換を計算するステップと、
変換空間において前記計算された変換をクラスタ化するステップであり、１つ以上の変換クラスタが取得されるステップと、
前記変換空間における前記１つ以上の変換クラスタのそれぞれに従って、反復構造及びその標本を判定するステップであり、変換が前記変換空間において共通のクラスタに属するサンプリングポイントの対は、反復構造の２つのインスタンスとして定義されるステップと
を有する、請求項１に記載の方法。
【請求項３】
前記曲率記述子は、平均曲率H(vi)と、ガウス曲率K(vi)と、主曲率とを有する、請求項２に記載の方法。
【請求項４】
前記クラスタ化するステップは、平均値シフトアルゴリズムを使用する、請求項２又は３に記載の方法。
【請求項５】
前記変換を計算するステップは、複数の可能な変換を有する変換空間を計算することを有する、請求項２ないし４のうちいずれか１項に記載の方法。
【請求項６】
前記3Dモデルを符号化するステップを更に有し、
前記反復構造の参照モデルは１回のみ符号化され、前記反復構造のインスタンスは、前記符号化された参照モデルを参照することにより符号化される、請求項１ないし５のうちいずれか１項に記載の方法。
【請求項７】
前記方法は、前記検出するステップがもはや反復構造を生じない場合、終了する、請求項１ないし６のうちいずれか１項に記載の方法。
【請求項８】
前記方法は、サンプリングステップサイズが所定の閾値に到達した場合、終了する、請求項１ないし７のうちいずれか１項に記載の方法。
【請求項９】
前記サンプリングステップサイズを計算する初期ステップを更に有し、
前記サンプリングステップサイズは、前記3Dメッシュモデルのパラメータから計算される、請求項８に記載の方法。
【請求項１０】
前記3Dメッシュモデルの周辺のバウンディングボックスが構成され、
前記バウンディングボックスの対角の長さが計算され、前記サンプリングステップサイズは、前記対角の長さの一部として設定される、請求項９に記載の方法。
【請求項１１】
処理実行時間を測定するステップを更に有し、
前記方法は、前記処理実行時間が所定のタイムアウト値に到達した場合、終了する、請求項１ないし１０のうちいずれか１項に記載の方法。
【請求項１２】
3Dメッシュモデルにおいて反復構造を検出する装置であって、
現在のサンプリングステップサイズを使用して前記3Dメッシュモデルをサンプリングするサンプリング手段と、
前記3Dメッシュモデル内で１つ以上の反復構造及び前記モデルの残りの部分を検出する検出手段と、
前記１つ以上の反復構造のそれぞれについて標本を判定する判定手段と、
前記現在のサンプリングステップサイズを低減し、低減されたサンプリングステップサイズを取得する低減手段と、
前記検出手段が前記現在のサンプリングステップサイズに基づいて１つ以上の反復構造を検出する限り、検出された反復構造のそれぞれの検出された標本及び前記モデルの前記残りの部分について前記低減手段、前記サンプリング手段、前記検出手段及び前記判定手段の繰り返しの動作を制御する制御手段と
を有し、
前記低減されたサンプリングステップサイズが前記現在のサンプリングステップサイズとして使用される装置。
【請求項１３】
前記検出手段は、
それぞれの現在のサンプリングステップサイズに基づいてサンプリングポイント毎に曲率記述子を計算する曲率計算手段と、
曲率記述子に従って前記サンプリングポイントをクラスタ化するサンプリングポインクラスタ化手段であり、１つ以上のサンプリングポイントのクラスタが取得されるサンプリングポイントクラスタ化手段と、
共通のサンプリングポイントのクラスタに属するサンプリングポイントの対の間で変換を計算する変換計算手段と、
変換空間において前記計算された変換をクラスタ化する変換クラスタ化手段であり、１つ以上の変換クラスタが取得される変換クラスタ化手段と、
前記変換空間における前記１つ以上の変換クラスタのそれぞれに従って、標本の反復構造を判定する反復構造判定手段であり、変換が前記変換空間において共通のクラスタに属するサンプリングポイントの対は、反復構造の２つのインスタンスとして定義される反復構造判定手段と
を有する、請求項１２に記載の装置。
【請求項１４】
前記3Dモデルを符号化するエンコーダを更に有し、
前記反復構造の参照モデルは１回のみ符号化され、前記反復構造のインスタンスは、前記符号化された参照モデルを参照することにより符号化される、請求項１２又は１３に記載の装置。
【請求項１５】
前記低減されたサンプリングステップサイズと所定の最小サンプリングステップサイズとを比較する比較手段を更に有し、
前記制御手段は、最小サンプリングステップサイズに到達した場合、前記装置の動作を終了させる、請求項１２ないし１４のうちいずれか１項に記載の装置。
【請求項１６】
処理実行時間を測定する時間測定ユニットを更に有し、
前記処理実行時間が所定のタイムアウト値に到達した場合、方法が終了する、請求項１２ないし１５のうちいずれか１項に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、3Dメッシュモデルにおいて反復構造を検出する方法に関する。
【背景技術】
【０００２】
反復構造（repetitive  structure）は、自然（例えば、生物学及び物理学）において遍在するだけでなく、他の分野（エンジニアリング及び芸術）においても遍在する。反復構造は、人工の物体で非常に一般的であり、例えば建築のほとんど全ての設計様式の基本になっている。従って、全ての一般的な種類の3Dメッシュモデルは、一般的に反復構造を有する。このようなモデルの増加する複雑性のため、これらを符号化するために必要なデータ量を最小化することが望まれる。反復構造を含む対称性は、複雑性を低減するために使用され得る一種の冗長性であることが分かる。反復構造は、一回のみ符号化される必要があり、複数回呼び出される又は“インスタンス化（instantiate）”されることができる。この冗長性から利益を受けるために、既存の3Dメッシュモデルで反復構造を検出することが必要になる。通常の方法は、ユーザが反復要素を手動で識別することに依存する周期的な構造をセグメント化する技術を使用している。明らかに、このようなユーザの支援は好ましくない。
【０００３】
反復構造の各インスタンスは、変換（transformation）（回転、平行移動、鏡映及び均等変倍等）により個々に変更されることができる。（部分的）対称性検出のための既知の方法（非特許文献１）は、異なる縮尺であっても、“変換投票（transformation  voting）”と呼ばれる手法を使用する。これは、変換空間（transformation  space）を構成し、可能な変換をクラスタ化し、変換クラスタ（transformation  cluster）により対称性を判定することを有する。例えば、Mitra（非特許文献１）は、第１のステップにおいて、局所形状記述子（local  shape  descriptor）を計算する。局所形状記述子は、対称性候補動作のもとで、相互にマッピングされ得るポイントを対にするために使用される。一式の可能な変換候補は、変換空間と呼ばれる。類似する変換を有する対は、変換空間においてクラスタを形成し、クラスタは、対応する対称関係の証拠を提供する。第２のステップにおいて、変換がクラスタに分類されたポイントの対は、空間整合性（spatial  consistency）について検査される。対称的な表面パッチ（surface  patch）を検出して抽出するときにサンプリング候補の小さいセットのみが考慮される必要があるように、確率論的クラスタ化（stochastic  clustering）は、表面対応関係（surface  correspondence）を提供する。曲率記述子（curvature  descriptor）は、サンプリングポイントを対にするために使用される。曲率記述子が異なりすぎる場合、ポイントの対の候補は破棄される。同様に、曲率記述子に従ってサンプリングポイントを“類似セット”にグループ化することが知られている（非特許文献２）。一般的に、曲率は、幾何学物体が平坦から逸脱する量である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】"Partial  and  Approximate  Symmetry  Detection  for  3D  Geometry",  2006  by  N.Mitra,  L.Guibas,  M.Pauly,  ACM  Trans.  Gr.  25,  3,  560.568
【非特許文献２】"Discovering  Structural  Regularity  in  3D  Geometry",  M.Pauly,  N.Mitra,  J.Wallner,  H.Pottmann,  L.Guibas,  2008,  ACM  Trans.  Gr.  27,  3
【非特許文献３】"Discrete  differential  geometry  operators  for  triangulated  2-manifolds",  Meyer  M,  Desbrun  M,  Schroder  P,  Barr  A,  in:  Visualization  and  Mathematics,  Berlin,  2002,  52-58
【非特許文献４】"Mean  shift:  A  robust  approach  toward  feature  space  analysis",  Comaniciu  D.,  Meer  P.;  2002  IEEE  Trans.  PAMI  24,  5,  603-619
【非特許文献５】"Efficient  variants  of  the  ICP  algorithm",  RUSINKIE  ICZ  ,  S.  and  LEVOY,  M.,  2001,  in  3DIM,  145-152
【発明の概要】
【発明が解決しようとする課題】
【０００５】
クラスタ化を使用する１つの理由は、比較されるデータの量が非常に大きいことにある。サンプリングポイントの数（従って、データ量）は、サンプリングステップサイズにかなり依存する。小さいサンプリングステップは、多くのデータを生じ、クラスタ化ステップの効率を低くする。しかし、大きいサンプリングステップは、小縮尺の構造の省略を生じる。
【０００６】
本発明は、既知の3D圧縮方法（特に、変換投票法）に対する改善を提供する。通常では、後者は、クラスタ化を変換し、候補を比較することにより、対称性の候補を見つけるステップを有する。これらは、3D圧縮又は他の用途で使用されることがある。
【課題を解決するための手段】
【０００７】
本発明により提供される改善は、少なくともサンプリングステップサイズに関係する。特に、本発明は、減少するサンプリングステップサイズを用いて、繰り返しの均等サンプリング（iterative  uniform  sampling）方法を使用する。所与の3Dメッシュモデルは、比較的大きい初期サンプリングステップサイズで均等にサンプリングされる。次に、サンプリングポイントは、曲率に従ってクラスタ化され、同じクラスタに属するサンプリングポイントの間で変換が判定される。これらは、いわゆる変換候補（candidate  transformation）である。従って、変換候補は、双方のポイントが類似する曲線を有するサンプリングポイントの対についてのみ判定されればよい。このようなクラスタ化ステップは、アルゴリズムの効率を改善するだけでなく、アルゴリズムの精度を向上させる。以前に計算された全ての変換により構築された変換空間は、サンプリングステップサイズが小さい場合に比べて、少ない雑音要素を含む。従って、次のクラスタ化ステップは、全ての反復構造を発見する可能性が高くなる。モデルが反復構造を有する場合、このようなクラスタ化の通常の結果は、１つ以上の明確なクラスタが現れることになる。次のステップにおいて、（最も関係のある）クラスタが選択され、対応する変換及びサンプリングポイントの対が、反復構造を示すものとして想定される。最も関係のあるクラスタは、最も有意で明白なものである。クラスタに属さない他の変換は破棄される。
【０００８】
この手順は、減少するサンプリングステップサイズを用いて繰り返し実行される。それぞれの繰り返しは反復を省略し、モデルの残りの部分及び前の繰り返しで検出された代表的な構造の標本（representative）のみを処理する。従って、3Dモデルの多重スケール反復構造（multi-scale  repetitive  structure）が発見され得る。反復構造の数が安定的である場合又は所定の最小サンプリングステップサイズに到達した場合、繰り返し処理が終了する。タイムアウトを定義し、処理の実行時間を測定し、実行時間がタイムアウトを超過したときに処理を終了させることも可能である。
【０００９】
更なるクラスタ化及び繰り返しステップは、調査されるべき可能な変換の量を低減し、従って、必要な処理能力を低減する。
【００１０】
本発明の一実施例によれば、3Dメッシュモデルにおいて反復構造を検出する方法は、現在の（均等な）サンプリングステップサイズを使用して3Dメッシュモデルをサンプリングするステップと、3Dメッシュモデル内で１つ以上の反復構造及びモデルの残りの部分を検出し、１つ以上の反復構造のそれぞれについて標本を判定するステップと、検出するステップが現在のサンプリングステップサイズを使用して１つ以上の反復構造を生じる限り、現在のサンプリングステップサイズを低減し、低減されたサンプリングステップサイズを取得するステップと、検出された反復構造のそれぞれの検出された標本及びモデルの残りの部分についてサンプリングするステップ及び検出するステップを繰り返すステップとを有し、低減されたサンプリングステップサイズが現在のサンプリングステップサイズとして使用される。検出された多重スケール反復構造は、ツリー構造に記録される。検出するステップがもはや反復構造を生じない場合、又は所定の最小サンプリングステップサイズ若しくはタイムアウトに到達した場合、反復構造を検出する方法は終了する。
【００１１】
一実施例では、それぞれの検出するステップは、それぞれの現在のサンプリングステップサイズに基づいてサンプリングポイント毎に曲率記述子を計算するステップと、曲率記述子に従ってサンプリングポイントをクラスタ化するステップであり、１つ以上のサンプリングポイントのクラスタが取得されるステップと、共通のサンプリングポイントのクラスタに属するサンプリングポイントの対の間で変換を計算するステップと、変換空間において計算された変換をクラスタ化するステップであり、１つ以上の変換クラスタが取得されるステップと、変換空間における１つ以上の変換クラスタのそれぞれに従って、反復構造及びその標本を判定するステップであり、変換が変換空間において共通のクラスタに属するサンプリングポイントの対は、反復構造の２つのインスタンスとして定義されるステップとを有する。
【００１２】
本発明の一実施例によれば、3Dメッシュモデルにおいて反復構造を検出する装置は、現在の（均等な）サンプリングステップサイズを使用して3Dメッシュモデルをサンプリングするサンプリング手段と、3Dメッシュモデル内で１つ以上の反復構造及びモデルの残りの部分を検出する検出手段と、１つ以上の反復構造のそれぞれについて標本を判定する判定手段と、現在のサンプリングステップサイズを低減し、低減されたサンプリングステップサイズを取得する低減手段と、検出手段が現在のサンプリングステップサイズを使用して１つ以上の反復構造を検出する限り、検出された反復構造のそれぞれの検出された標本及びモデルの残りの部分についてサンプリング手段及び検出手段を制御する制御手段とを有し、低減されたサンプリングステップサイズが現在のサンプリングステップサイズとして使用される。検出手段がもはや反復構造を検出しない場合、又は所定の最小サンプリングステップサイズ若しくはタイムアウトに到達した場合、反復構造を検出する装置は中断する。
【００１３】
本発明の有利な実施例は従属項、以下の説明及び図面に記載されている。
【図面の簡単な説明】
【００１４】
【図１】3Dモデルにおいて反復構造を発見する方法のブロック図
【図２】対称性検出の原理
【図３】検出された多重スケール反復構造を記録するツリー構造
【図４】反復構造を発見する装置のブロック図
【図５】反復構造を検出する検出手段のブロック図
【図６】例示的な3Dメッシュモデル及びその対応するデータセット
【図７】ポイントの対のポイントの間の変換
【発明を実施するための形態】
【００１５】
本発明の例示的な実施例について、添付図面を参照して説明する。
【００１６】
図１は、3Dモデルにおける反復構造を発見する方法のブロック図を示している。入力モデルについて、サンプリングポイントが計算される100。ここでは、比較的大きいサンプリングステップサイズが使用される。次のステップ200において、サンプリングポイント毎に曲率記述子が計算される。サンプリングポイントは、曲率記述子に従ってクラスタ化される300。すなわち、類似する曲率記述子を備えたサンプリングポイントが同じクラスタに入れられる。クラスタ内のサンプリングポイントの中で、反復構造が検出（すなわち、計算）され400、検証される500。検出された反復構造から、各反復構造が下位分岐（sub-branch）により表されるツリーが構成される。最後に、反復数が前のステップで増加したか否かが検査される700。（ほとんどのモデルと同様に）反復構造を含む入力モデルについて、このことが最初に常に当てはまる。この場合、サンプリングステップサイズが減少し、サンプリングポイントがクラスタの下位構造について再計算される。
【００１７】
3Dモデルにおいて反復構造を検出する効率的な方法が開示され、この方法は、いずれかの小さい縮尺の反復構造と、多重スケール反復構造とを自動的に発見することができる。主な概念は、曲率に基づいて全てのサンプリングポイントをクラスタ化し、減少するステップサイズでモデルを繰り返し処理することを含む。この方法のブロック図が図１に示されている。このアルゴリズムでは、設定される入力データは、ポイントセットでもよく、メッシュに基づくモデルでもよい。
【００１８】
この方法により検出された多重スケール反復構造を記録するために、ツリー構造が使用される。ツリーの各ノードは、１つの反復構造を記録する。始めに、ツリーは、入力モデルに対応するルートのみを有する。サンプリングステップHは、最初に比較的大きい数である。
【００１９】
サンプリングブロック100は、表面を均等にサンプリングする。この図では、現在のサンプリングステップはHとして示されている。
【００２０】
曲率記述子計算ブロック200は、各サンプリングポイントの曲率記述子を計算する。サンプリングポイントpiについて、その平均曲率H(pi)と、ガウス曲率K(pi)と、主曲率Ki1、Ki2と、主方向Ci1、Ci2とを計算する。曲率記述子を計算するために如何なる方法が使用されてもよい。例えば、Meyer他  2002（非特許文献３）のセクション3-5に記載の方法が使用されてもよい。piの曲率記述子は、以下のようになる。
cd(pi)=H(pi)2/K(pi)      (1)
Ki1、Ki2、Ci1及びCi2は以下に記載する次の計算で有用になる。曲率記述子についての更なる詳細は以下に提供される。
【００２１】
ブロック300は、曲率記述子に従ってサンプリングポイントをクラスタ化する。ここでは、クラスタ演算子として、平均値シフト（mean-shift）アルゴリズムを使用する（これは一般的に知られており、例えばComaniciu他（非特許文献４）に記載されている）。密度関数は以下のように定義される。
ρ(H(v)2/K(v))=Σi(H(v)2/K(v)-H(vi)2/K(vi))/h      (1a)
ただし、hはComaniciu他（非特許文献４）に示されたものである。
【００２２】
ブロック300は、不要なサンプルの対を切り捨てることにより、次の分析ステップの効率及びロバスト性を改善する。この理由は、同じ反復構造が類似する曲率を有するポイントを構成するからである。
【００２３】
ブロック400は、現在のレベルの反復構造を計算する。これは、各サンプリングポイントのクラスタを別々に扱う。Φkを現在処理されているクラスタとして示す。
【００２４】
ブロック410は、例えばMitra他  2006（非特許文献１）に記載の方法により、Φkの変換空間Γkを計算する。変換Ti,j∈Γkは、ポイントpi∈Φkを他のポイントpj∈Φkに変換する。ブロック200は、１つのサンプリングポイントpiの主曲率Ki1、Ki2と主方向Ci1、Ci2とを既に計算している。
【００２５】
Ci1及びCi2は、piの局所フレーム(Ci1,Ci2,ni)を定め、ni=Ci1×Ci2である。２つの連続した回転演算R1ij及びR2ijが存在する。R1ijは、niをnjに並列にする。R2ijは、Ci1をCj1に並列にする。倍率si,jは以下により計算される。
si,j=(Ki1/Kj1+Ki2/Kj2)/2      (2)
平行移動（translation）ti,jは以下により計算される。
ti,j=pj-si,jRi,jpi      (3)
従って、以下の７次元のTi,jを得る。
Ti,j=(si,j,Rxi,j,Ryi,j,Rzi,j,txi,j,tyi,j,tzi,j)      (4)
Rxi,j、Ryi,j、Rzi,jはオイラー角であり、回転R2を表し、ti,j=[txi,j,tyi,j,tzi,j]Tは平行移動を表す。
【００２６】
ブロック420は、Γkの全ての変換をクラスタ化する。既存のアルゴリズムと同様に、このステップのクラスタ化演算として、平均値シフトを選択する。同じクラスタの変換は、通常では同じ反復構造を表す。
【００２７】
ブロック430は、反復構造に対応する表面パッチ（曲面片）を計算する。サイズの減少順に、ブロック420で計算されたクラスタを扱う。Ckが処理されている変換クラスタを示すものとする。Mitra他  2006（非特許文献１）と同様に、徐々に増えるパッチ増加処理により表面パッチを計算する。これは、CkのランダムなポイントTi,jから始まる。Ti,jは、サンプリングポイント(pi,pj)の対に対応する。pi1がpiの１リング周辺の１つの表面の頂点であり、pi1=TijSijR2ijR1ijpi1であると仮定する。Dis_surは、pi1とpjの周辺の表面との間の距離であり、Dis_Ptはpi1とpjとの間の距離である。
Dis=u1*Dis_Sur+u2*Dis_Pt,  u1+u2=1      (5)
u1及びu2は何らかの定数である（u1=0.8、u2=0.2と設定する）。Disが閾値より小さい場合、pi1はpiから始まる表面パッチに追加される。表面パッチは、その現在の境界から、それ以上のポイントが追加できなくなるまで増加し続ける。piから始まる表面パッチが終了した後に、pjから始まる表面パッチを計算する。このような２つの表面パッチがそれぞれ２つのパッチのセット{Pati}及び{Patj}に追加される。パッチ増加処理の間に、全ての訪問したサンプリングポイント及びこれらに関与する変換に印を付ける。いずれかの印の付いていない変換がCkに存在する場合には、新たなパッチが構築される。最終的に、クラスタ毎に２つのパッチのセットが計算され、同じ反復構造のインスタンスになる。一方のパッチのセットは、標本として選択され、他方は、対応する反復構造のインスタンスとしてみなされる。
【００２８】
ブロック500は、ブロック400で発見された反復構造を検証するために、例えばRUSINKIEWICZ他  2001（非特許文献５）から知られているようなICP（Iterated  Closest  Point）アルゴリズムを使用する。まず、インスタンス構造が、ICPにより対応する反復に正確に一致し得るか否かを検査する。このテストを通過できない反復構造は、破棄される。次に、ICPにより残った標本のそれぞれの対を一致させることを試みる。正確に一致した２つの標本について、対応する反復構造が組み合わされる。
【００２９】
ブロック600は、図３に示すように、検出された多重スケール反復構造を記録するツリー構造を更新する。ちょうど検出された反復構造は、対応するノードのリーフ（葉）として追加される。反復構造を含まない表面の一部に対応する特別のリーフノードが追加される。アルゴリズムの次の繰り返しで検出される小さい縮尺の反復構造が存在してもよい。
【００３０】
次の繰り返しでは、サンプリングステップは、元のサイズの半分になる。アルゴリズムは、全てのリーフノードを別々に扱う。一実施例では、アルゴリズムは、サンプリングステップが閾値より小さくなったときに中断する。
【００３１】
一実施例では、アルゴリズムを中断するサンプリングステップの閾値は、入力モデルに依存し、特に、入力モデルのバウンディングボックス（bounding-box）の直径に依存する。すなわち、（例えば、x、y、z軸に沿ったデカルト直径システムにおいて）バウンディングボックスは、完全なモデルの周囲に構成され、(xmin,ymin,zmin)から(xmax,ymax,zmax)への対角の長さが計算され、サンプリングステップサイズの閾値は、その一部（分数）（例えば、0.5%（diagonal_length/200）以下）になるように設定される。
【００３２】
図２は、3Dモデルの例を示している。ａ）では、いずれか特定のステップサイズを示すサンプリングポイントが示されており、ｂ）は、従来技術で構成される可能な変換を示している。サンプリングポイント毎に、互いのサンプリングポイントへの変換が計算される。しかし、本発明では、このような計算は、201、210、220のように、類似する曲率を有するポイントの対についてのみ計算される。クラスタ化の後に、実際の対称性に関係するこれらの変換が特定可能になる。この理由は、これらは非常に類似しているため、共通の変換クラスタになるからである。図２ｃ）において、この例示的なモデルの判定された対称性（対称軸230の鏡映）が示されている。
【００３３】
ここで、従来技術（Mitra  2006（非特許文献１））は、２つのサンプリングポイントが類似するシグニチャ（signature）を有するサンプリングポイントの対のみを扱う点に留意すべきである。この方法は以下のようになる。piを１つのサンプリングポイントであると仮定し、Pをサンプリングポイントのセットであると仮定する。ki1/ki2はpiのシグニチャであり、ki1及びki2はpiの主曲率である。全てのサンプリングポイントは、シグニチャ空間Ωにマッピングされる。Ωにおいて近いポイントの対のみが、後の分析処理の適切な候補として考えられる。従来技術は、まず、ランダムなサブセットP*⊂Pを選択する。後の分析でのポイントの対の候補は、(p*,p)であり、p*∈P*且つp∈Pである。所与のサンプリングポイントpi∈P*では、従来技術は、Ωにおいて範囲クエリを実行することにより、全ての適切なパートナー（仲間）を判定する。従来技術は、piの全ての適切なパートナーを見つけるために、標準的な空間近接データ構造kd-treeを使用する。この方法により、従来技術は、二次数（quadratic  number）のポイントの対の網羅的な計算を回避することができる。本発明では、曲率記述子に従って全てのサンプリングポイントをクラスタ化することにより、同じ目的を実現する。従来技術により使用されるサンプリングポイントのサブセットをランダムに選択する方法と比べて、本発明は更に正確であり、いずれかの縮尺で全ての反復構造を検出することを保証することができる。従来技術ではこれは不可能である。
【００３４】
対称性は、本発明の重要な概念であるため、ここで、一式の変換（回転、平行移動、鏡映及び均等変倍等）のもとで不変を意味することを明確にする。
【００３５】
更に、曲率及び曲率記述子は明確な数学的概念であり、その構成は従来技術において周知である（例えば、Pauly（非特許文献２））。viの平均曲率H(vi)は、使用される座標システムとは独立である。ガウス曲率K(vi)は、3D座標システムに依存し、以下により定義される。
【００３６】
【数１】
0005583848.tif 000002
ただし、ki1及びki2はviの２つの主曲率である。微分幾何学（Differential  Geometry）によれば、ガウス曲率K(vi)及び平均曲率H(vi)は以下の２つの主曲率により表されてもよい。
K(vi)=ki1*ki2      (7)
H(vi)=ki1+ki2      (8)
従って、主曲率を以下のように定義することができる。
【００３７】
【数２】
0005583848.tif 000003
式(9)及び(10)から、以下の曲率記述子を取得することができる。
【００３８】
【数３】
0005583848.tif 000004
従って、H(vi)2/K(vi)は、変倍、回転及び平行移動の変換のもとで不変である。従って、H(vi)2/K(vi)を形状記述子として使用し、H(vi)2/K(vi)に従ってクラスタサンプルポイントを使用する。同じ曲率記述子は、Pauly他  2008（非特許文献２）で使用されているが、異なる目的で使用されている。
【００３９】
図４は、本発明の一実施例に従って3Dメッシュモデルにおいて反復構造を検出する装置を示している。これは、入力で提供された3Dメッシュモデルをサンプリングするサンプリング手段SM（すなわち、サンプリングユニット）を有する。これは、以下に説明するように、他のユニットから受信した現在の均等なサンプリングステップサイズsssを使用する。
【００４０】
サンプリングユニットSMは、サンプリングされたデータを検出手段DM1に提供する。検出手段DM1は、サンプリングされた3Dメッシュモデル内で１つ以上の反復構造を検出し、反復構造ではないモデルの残りの部分を識別する。各反復構造rsは、判定手段Dm2に提供される。判定手段DM2は、１つ以上の反復構造のそれぞれについて標本repを判定する。標本（すなわち、そのデータ）は、検出手段DM1に戻される。DM1は、これをその（更なる）反復を識別するために使用する。
【００４１】
反復構造のサンプリング及び制御データと、前述の残りのデータ部分rsrdは、出力として、例えばエンコーダEに提供される。これらのデータrsrdは、サンプリングされたサンプリングステップサイズを有する、各反復構造の標本及びそれぞれの残りの部分のサンプリングデータを有する。データrsrdはまた、反復構造の反復を定義するデータを有する。例は以下に提供される。
【００４２】
更に、装置は、検出手段が現在のサンプリングステップサイズを使用して１つ以上の反復構造を検出する限り、装置の繰り返しの動作を制御する制御手段CMを有する。すなわち、検出手段DM1がモデルにおけるその動作を終了し、少なくとも１つの反復構造を識別したことを制御手段CMに伝えた場合、制御手段CMは、サンプリングステップサイズ低減手段SRMを制御し、サンプリングステップサイズを低減する。更に、制御手段CMは、サンプリング手段SM、検出手段DM1及び判定手段DM2を制御し、低減されたサンプリングステップサイズを使用して、検出された反復構造のそれぞれ検出された標本及びモデルの残りの部分についてその動作を反復する。
【００４３】
サンプリングステップサイズは、初めに所定の値isssであり、所与の係数fによって連続的に低減される。一実施例では、この係数は一定の整数である。一実施例では、この係数は“2”である。すなわち、第１の繰り返しでは、サンプリングステップサイズは所定の値isssであるが、第２の繰り返しではisss/2になり、第３の繰り返しではisss/4になり、以下同様である。第２及び更なる繰り返しは、反復構造の標本及び残りのものについてのみ実行される点に留意すべきである。
【００４４】
DM1がもはや反復構造を検出しない場合、又は所定の最小サンプリングステップサイズsmin若しくはタイムアウトに到達した場合、反復構造を検出する装置は中断する。この目的で、一実施例では、装置は、タイムアウト測定ユニットTMUを有し、一実施例では、サンプリングステップサイズ比較ユニットCMPを有する。
【００４５】
一実施例では、検出された多重スケール反復構造は、メモリ装置にツリー構造として記録される。
【００４６】
図５は、検出手段DM1の一実施例の詳細を示している。これは、それぞれの現在のサンプリングステップサイズに基づいて、サンプリングポイント毎に曲率記述子を計算する曲率計算手段CUCMを有する。曲率記述子は、前述の通りである。サンプリングポイントクラスタ化手段SPCMは、曲率記述子に従ってサンプリングポイントをクラスタ化する。ここで、１つ以上のサンプリングポイントのクラスタが提供される。変換計算手段TCAMは、共通のサンプリングポイントのクラスタに属するサンプリングポイントの対の間の変換を計算するために使用され、変換クラスタ化手段TCLMは、計算された変換をクラスタ化するために使用される。これは、変換空間において行われ、１つ以上の変換クラスタtcが提供されることを生じる。最後に、検出手段DM1は、変換空間における１つ以上の変換クラスタのそれぞれに従って反復構造rsを判定する反復構造判定手段RSDMを有する。ここで、変換が変換空間において共通のクラスタに属するサンプリングポイントの対が、反復構造の２つのインスタンスとして定義される。反復構造rsは、前述の判定手段DM2に提供され、判定手段DM2は、反復構造の標本repを判定（すなわち、識別）する。これは、いずれかの任意の方法で生じてもよい。例えば、反復構造の最初に判定されたインスタンスが標本として選択され、全ての更なるインスタンスが反復として選択される。反復構造判定手段RSDMは、まず、以下に説明するように、全体モデルを定義する第１のデータrsrdを出力し、少なくとも１つの反復構造が見つかったか否かを示す第２のデータrsdを出力する。後者のデータrsdは、制御ブロックCMに提供される。制御ブロックCMは、他の繰り返しを開始することを判定してもよい。
【００４７】
図６は、例示的な3Dメッシュモデルの反復構造及び残りのデータ部分を定義するデータの例を示している。ここでは、これは、一実施例の基本原理を説明するための簡単な例である点に留意すべきである。
【００４８】
図６は、複数回使用される１つの反復構造と、反復構造ではない残りのものとを有する3Dメッシュモデルを示している。この例では、反復構造は三角形であり、残りのものrmは円である。また、図６に示すように、前述のデータrsrdは、反復構造の標本rrのサンプリングデータrrd1と、その個々の反復を示す反復データr1,r2,...と、各反復の位置、縮尺等を定義するそれぞれの変換tr1(rrd1)、tr2(rrd2)、...とを有する。更に、データrsrdは、残りのものを定義するサンプリングデータrmd1を有する。この例では、残りのものは、１つのみの単一の構造であるが、２つ以上の個々の下位構造でもよい。
【００４９】
図７は、ポイントの対のポイントの間の変換を示している。(pi,pj)はCkのポイントの対であり、Ti,jはこれらの間の変換である。p’iはpiの１リング周辺である。Ti,jによるp’iの変換は、p’jを得ることができる。すなわち、変換の後のp’iが実際のp’jに近い場合（例えば、閾値の円の中にある場合）、変換Ti,jは好適な候補である。変換Ti,jが複数のポイントの好適な候補である場合、これは対称性を判定するために使用される。
【００５０】
3Dモデルにおいて反復構造を発見することは、困難なタスクであるが、その結果は多くの側面で有用である。記載の方法及び装置は、例えば、3Dモデル圧縮、3Dモデル修復、幾何学合成等に使用されてもよい。
【００５１】
3Dモデルのコンパクトな標本は、反復構造を検出した結果に基づいて生成されてもよい。このような標本は、以下のものを含む。
・反復構造の数を示すいくつかのビット
・反復構造の標本毎に、圧縮された幾何学パターンを示すいくつかのビット
・反復構造のインスタンスの数を示すいくつかのビット
・インスタンス毎に、その変換を示すいくつかのビット及び標本のIDを示すいくつかのビット
本発明は、反復構造の検出のための既知のアルゴリズムに対して以下の利点を少なくとも有する。まず、全ての種類のモデルについて、反復構造が迅速に検出可能になる。この理由は、まず、全てのサンプリングポイントが曲率に従ってクラスタ化され、サンプリングポイントの各クラスタが別々に扱われるためである。
【００５２】
次に、本発明は、モデルにおける全ての反復構造を検出するのに適しているが、既知の方法はそうではない。例えば、小さい縮尺の構造を含むモデルを処理するときに、既知の方法は、全ての反復構造を検出するために大きい数のサンプリングポイントを必要とし、例えば、サンプリングポイントの数が大きくなり過ぎると、クラスタ化が失敗する。
【００５３】
第３に、多重スケール反復構造を備えたモデルでは、本発明は、全てのレベルの反復構造を検出することができるが、現在の方法はできない。この理由は、減少するサンプリングステップを使用して反復構造を繰り返し検出するからである。
【００５４】
本発明の好ましい実施例に適用される本発明の基本的な新規の特徴について図示、説明及び指摘したが、記載の装置及び方法において、記載の装置の形式及び詳細並びにその動作での様々な省略、置換及び変形が、本発明の要旨を逸脱することなく、当業者により行われてもよいことが分かる。同じ結果を実現するために基本的に同じ機能で基本的に同じ方法で実行する要素の全ての組み合わせは、本発明の範囲内であることを明確に意図する。１つの記載の要素から他のものへの要素の置換も十分に意図及び検討される。
【００５５】
本発明について、単なる例によって説明したが、本発明の範囲を逸脱することなく、詳細の変更が行われてもよいことが分かる。（必要に応じて）詳細な説明及び特許請求の範囲に記載のそれぞれの特徴は、独立して提供されてもよく、如何なる適切な組み合わせで提供されてもよい。必要に応じて、特徴はハードウェア、ソフトウェア又は２つの組み合わせで実装されてもよい。特許請求の範囲に現れる参照符号は単なる例示であり、特許請求の範囲に限定的な影響を有さない。
【図１】
0005583848.tif 000005
【図２ａ）】
0005583848.tif 000006
【図２ｂ）】
0005583848.tif 000007
【図２ｃ）】
0005583848.tif 000008
【図３】
0005583848.tif 000009
【図４】
0005583848.tif 000010
【図５】
0005583848.tif 000011
【図６】
0005583848.tif 000012
【図７】
0005583848.tif 000013