(57)【要約】  3Dモデルは、少数の大きな三角形と共に、しばしば任意の接続と共に、小型ないし中型のサイズの接続要素を多数有する。多数のマルチコンポーネント3Dモデルのコンパクト表現の効率又は機能は、たとえ要素が厳密には等しくなかったとしても要素間の類似性を検出及び表現することで改善できる。本発明は、クラスタリング及びクラスタ代表表面に基づいて、2つ以上の異なってはいるが類似する幾何学的パターンを別々にエンコードする変位マップを利用する。複数の幾何学的パターンをエンコードする方法は、幾何学的パターンが一致している複製物を検出及びエンコードし(100)、類似する幾何学的パターンを検出及びクラスタリングし(200)、部分的な類似度を検出する(300)。部分的な類似度を検出する際に、クラスタ代表表面を生成し、少なくとも1つのクラスタリングされた幾何学的パターンについて変位マップを生成し、共通する表面及び変位マップをエンコードする。
2013539125.tif 000002
【特許請求の範囲】
【請求項１】
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをエンコードする方法であって、
類似する幾何学的パターンを検出するステップと、
検出された類似する幾何学的パターンを共通するクラスタに分類するステップと、
クラスタ代表表面を生成するステップと、
クラスタに分類された少なくとも２つの幾何学的パターンについて各自の変位マップを生成するステップであって、前記各自の変位マップの各々は、前記クラスタ代表表面に属する頂点と、クラスタに分類された幾何学的パターンに属する頂点との間の変分を規定する、ステップと、
前記クラスタ代表表面及び前記変位マップをエンコードすることで前記複数の幾何学的パターンをエンコードするステップと
を有する方法。
【請求項２】
類似する幾何学的パターンを検出する前記ステップにおいて、前記接続要素を正規化し、正規化された要素を互いに比較し、該正規化された要素は、位置、方向及びサイズを示す、請求項１に記載の方法。
【請求項３】
元々の要素各々の位置情報、方向情報及び/又はサイズ情報に変位マップが関連付けられる、又は元々の要素各々の位置情報、方向情報及び/又はサイズ情報が変位マップに含まれる、請求項２に記載の方法。
【請求項４】
クラスタについて前記クラスタ代表表面を生成するステップにおいて、該クラスタに属するように分類された幾何学的パターンを平均化する、請求項１−３の何れか１項に記載の方法。
【請求項５】
前記類似する幾何学的パターンを検出する前記ステップにおいて、正規化の後に等しい少なくとも２つの幾何学的パターンを検出し、該検出したものを幾何学的パターンの代表を表わすものとして表現する初期ステップを行い、
クラスタに分類する前記ステップ及び以後のステップにおいて、前記幾何学的パターンの代表が個々の等しい幾何学的パターンの代わりに使用され、何れの幾何学的パターンの代表が参照されているかを示す通知情報が、少なくとも２つの幾何学的パターンと共にエンコードされる、請求項１−４の何れか１項に記載の方法。
【請求項６】
前記変位マップが、垂直方向における前記クラスタ代表表面の少なくとも１つの頂点の変位を規定する、請求項１−５の何れか１項に記載の方法。
【請求項７】
クラスタに分類された前記少なくとも２つの幾何学的パターンについて各自の変位マップを生成するステップにおいて、エネルギ関数を最小化する、請求項１−６の何れか１項に記載の方法。
【請求項８】
前記エネルギ関数は反復的に最小化され、前記エネルギ関数は、頂点の位置の合致性を示す第１の項と、垂直方向の合致性を示す第２の項と、反復ステップサイズを示す第３の項とを含む、請求項７に記載の方法。
【請求項９】
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをデコードする方法であって、
第１のデータをデコードし、クラスタ代表表面を求めるステップと、
第２のデータ及び第３のデータをデコードし、少なくとも２つの変位マップを求めるステップと、
前記クラスタ代表表面を設定するステップと、
前記少なくとも２つの変位マップのうちの第１の変位マップを前記クラスタ代表表面に適用することで、第１の幾何学的パターンを再構築するステップと、
前記少なくとも２つの変位マップのうちの第２の変位マップを前記クラスタ代表表面に適用することで、第２の幾何学的パターンを再構築するステップと
を有する方法。
【請求項１０】
前記第２又は第３のデータから取得された第４のデータをデコードし、前記第１及び/又は第２の幾何学的パターンの位置、方向及びスケールのデータを求めるステップを更に有する請求項９に記載の方法。
【請求項１１】
少なくとも第１及び第２の再構築された幾何学的パターンを３Ｄメッシュモデルに形成するステップを更に有する請求項９又は１０に記載の方法。
【請求項１２】
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをエンコードする装置であって、
類似する幾何学的パターンを検出する検出手段と、
検出された類似する幾何学的パターンを共通するクラスタに分類するクラスタリング手段と、
クラスタ代表表面を生成する演算手段と、
クラスタに分類された少なくとも２つの幾何学的パターンについて各自の変位マップを生成する変位マップ生成手段であって、前記各自の変位マップの各々は、前記クラスタ代表表面に属する頂点と、クラスタに分類された幾何学的パターンに属する頂点との間の変分を規定する、変位マップ生成手段と、
前記クラスタ代表表面及び前記変位マップをエンコードすることで前記複数の幾何学的パターンをエンコードするエンコード手段と
を有する装置。
【請求項１３】
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをデコードする装置であって、
第１のデータをデコードし、クラスタ代表表面を求める第１のデコーダと、
第２のデータをデコードし、少なくとも２つの変位マップを求める第２のデコーダと、
前記クラスタ代表表面を設定する第１の構築手段と、
前記少なくとも２つの変位マップのうちの第１の変位マップを前記クラスタ代表表面に適用することで、第１の幾何学的パターンを再構築する第２の構築手段と、
前記少なくとも２つの変位マップのうちの第２の変位マップを前記クラスタ代表表面に適用することで、第２の幾何学的パターンを再構築する第３の構築手段と
を有する装置。
【請求項１４】
少なくとも第１及び第２の再構築された幾何学的パターンを３Ｄメッシュモデルに合成する合成手段と、同一群の代表である幾何学的パターンから少なくとも２つの等しい要素を再構築する第４の再構築手段とを更に含み、前記２つの等しい要素は、異なる位置、方向及びサイズの関連情報を有している、請求項１３に記載の方法。
【請求項１５】
少なくとも２つの異なる幾何学的パターンについて共通する表現を示す要素のデータと、
前記共通する表現及び少なくとも２つの幾何学的パターンに関する少なくとも２つの異なる変位マップと
を有する３Ｄメッシュモデルを表現するデータ構造又はデータストリームを用いてエンコード及びデコードを行う方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチコンポーネント3Dメッシュモデルのような類似する幾何学的パターンを効率的にエンコードすること等に関する。
【背景技術】
【０００２】
この欄は、以下に説明される及び/又は特許請求の範囲に記載される本発明の様々な形態に関連する様々な技術を読者に紹介するように意図されている。この欄の説明は、読者に背景技術を示し、本発明の様々な形態を十分に理解することを促すことに役立つものと思われる。従ってここでの説明はその観点から読まれるべきであり、従来技術であると認めたわけではない。
【０００３】
様々な分野で広く使用されている3Dモデルには、小型ないし中型の大きさの接続された要素又はコンポーネントが多数存在し、それらの要素の各々は平均的に数百個に及ぶポリゴンを有する。この種のモデルはマルチ接続又はマルチコンポーネント3Dモデル(multi−connected  or  multi−component  3D  model)と呼ばれている。これは、生物学、物理学、工学等の様々な分野で重要な役割を演じる。この種のモデルは、例えば機械CAD設計、アーキテクチャ設計及び化学プラント等に使用され、様々な仮想世界アプリケーションで益々発展している。
【０００４】
メモリ削減及び伝送効率等の観点からは、コンパクト表現(compact  representation)が重要事項の1つになる。3Dモデルは、通常、座標配列(coordinate  array)及び面配列(face  array)から成る「インデックスフェース群(indexed  face  set)」により表現される。座標配列は全ての頂点の座標をリスト化(列挙)し、面配列はその座標配列の中の3つの頂点を指定することで面の各々をリスト化(列挙)する。インデックスフェース群に含まれているものは圧縮されていない。「トライアングルストリップ(triangle  strip)」(非特許文献1)は、ほとんどのグラフィックカードで適切に使用可能な(サポートされている)幅広く使用されている3Dモデルのコンパクト表現である。トライアングルストリップ法は、図1に示すように、3Dメッシュを三角形の細長い片に分割し、これらの片又はストリップをエンコードする。図1の場合、頂点v0，．．．v7は、3Dメッシュモデルの一部をなす一群の三角形の片又はストリップを規定する。
【０００５】
多くの既存の3D圧縮アルゴリズムは、圧縮率を向上させるために3Dモデルの各自自身のコンパクト表現を使用している。これらのコンパクト表現は、小さな三角形の密集したメッシュの滑らかな表面に対して適切に機能する。しかしながら、大きなマルチ接続3Dモデルは、大きな三角形が小数しかない多数の接続要素(しばしば任意の接続を含んでいる)を有する。構造建築CADモデルは、一般的には、滑らかでない表面を多数含むので、その方法は適切でない。更に、既存の方法の多くは、各々が別々に接続された要素を取り扱っている。従って、そのような3Dモデルの表現は、大きなマルチコンポーネント3Dモデルには適切に機能しない。
【０００６】
近年、大きなマルチコンポーネント3Dモデルに特化して設計された幾つかのコンパクト表現が提案されている。非特許文献2及び非特許文献3は、大きなマルチコンポーネント3Dモデルのためのコンパクト表現を提案し、回転、並進及び/又はスケーリングによらず、反復的な要素を検出できる。更に、非特許文献4では、3Dメッシュモデルの表面の詳細を規定するための変位マップが説明されている。そのような詳細は、(対象の形状を規定するマクロ構造の反対として)メソ構造(meso−structures)と言及され、組織、構造、テクスチャ又は光の影響を示す高周波幾何学詳細(high  frequency  geometric  details)を含む。従ってそれらは表面上のバンプ(bumps)のように比較的小さいけれども目に見える。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】J.L.  Peng,  C.−S.  Kim  and  C.−C.  Jay  Kuo.  Technologies  for  3D  mesh  compression  :  A  survey.  ELSEVIER  Journal  of  Visual  Communication  and  Image  Representation  16(6),  688−733,  2005
【非特許文献２】Kangying  Cai,  Yu  Jin,  Wencheng  Wang,  Quqing  Chen,  Zhibo  Chen,  Jun  Teng:  Compression  of  massive  models  by  efficiently  exploiting  repeated  patterns.  VRST  2009:  229−230
【非特許文献３】Kangying  Cai,  Wencheng  Wang,  Zhibo  Chen,  Quqing  Chen,  Jun    Teng:  Exploiting  repeated  patterns  for  efficient  compression  of  massive  models.  VRCAI  2009:  145−150
【非特許文献４】L.Szirmay−Kalos,  T.Umenhoffer:“Displacement  Mapping  on  the  GPU  −  State  of  the  Art”;  in  Computer  Graphics  Forum  (CGF),  Volume  25  (2006),  Number  3,  pp.1−24
【非特許文献５】SORKINE,  O.,  LIPMAN,  Y.,  COHEN−OR,  D.,  ALEXA,  M.  RoSSL,  C.,  AND  SEIDEL,  H.−P.2004.  Laplacian  surface  editing.  In  Proc.  of  Symp.  of  Geometry  Processing,  179−188
【非特許文献６】N.  Aspert,  D.  Santa−Cruz  and  T.  Ebrahimi,  MESH:  Measuring  Error  between  Surfaces  using  the  Hausdorff  distance,  in  Proceedings  of  the  IEEE  International  Conference  on  Multimedia  and  Expo  2002  (ICME),  vol.I,  pp.705−70
【発明の概要】
【発明が解決しようとする課題】
【０００８】
開示される発明の課題は、構造をエンコード又はデコードする改善された方法及び装置等を提供することである。
【課題を解決するための手段】
【０００９】
開示される発明による方法は、
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをエンコードする方法であって、
類似する幾何学的パターンを検出するステップと、
検出された類似する幾何学的パターンを共通するクラスタに分類するステップと、
クラスタ代表表面を生成するステップと、
クラスタに分類された少なくとも２つの幾何学的パターンについて各自の変位マップを生成するステップであって、前記各自の変位マップの各々は、前記クラスタ代表表面に属する頂点と、クラスタに分類された幾何学的パターンに属する頂点との間の変分を規定する、ステップと、
前記クラスタ代表表面及び前記変位マップをエンコードすることで前記複数の幾何学的パターンをエンコードするステップと
を有する方法である。
【図面の簡単な説明】
【００１０】
【図１】3Dメッシュモデル符号化のためのトライアングルストリップを示す図。
【図２】一実施形態によるエンコード方法のフローチャート。
【図３】変位マッピングの原理を示す図。
【図４】クラスタ代表表面を生成し、対象クラスタのメンバをエンコードする様子を示す図。
【図５】クラスタ代表表面のパターンに基づいて対象クラスタのメンバをデコードする様子を示す図。
【図６】頂点、頂点に至る半径のなす角度及び垂直方向を示す図。
【図７】部分的類否検出方法の簡略化された方法を示すフローチャート。
【図８】変位マップの計算例を説明するための図。
【図９】エンコーダの原理的な構造例を示す図。
【図１０】デコーダの原理的な構造例を示す図。
【図１１】エンコード方法及びデコード方法のフローチャートを示す図。
【発明を実施するための形態】
【００１１】
＜発明の概要＞
反復的なパターンを検出することによる恩恵を受ける上記のコンパクト表現方法は、所定の変換形式(すなわち、回転、並進及びスケーリング)の観点から厳密に一致する反復的なパターンのみを検出していることに、発明者等は着目した。しかしながら、実際の適用例では、少数の3Dモデルのみがそのような要素を含んでいるに過ぎない。
【００１２】
大きなマルチコンポーネント3Dモデルのコンパクト表現の効率は、厳密には等しく要素同士の類似度を検出及び表現することで大幅に改善できる、という認識に本発明は基づいている。概してそのような要素は幾何学的パターンである。
【００１３】
新規な本発明の形態は、単独のベースモデルに基づいて、2つ以上の異なってはいるが類似している幾何学的パターンを差分符号化するために変位マップを利用する。
【００１４】
本発明の一形態によれば、複数の幾何学的パターンをエンコードする方法は、類似する幾何学的パターンを検出してクラスタリングするステップと、(例えば、クラスタ化された全ての幾何学的パターンを平均化することで)クラスタ表現表面又はクラスタ代表表面(cluster  representative  surface)を生成するステップと、少なくともクラスタリングされた幾何学的パターンについて変位マップを生成するステップと、共通する表面及び変位マップをエンコードするステップとを有する。幾何学的パターンの類似性又は類似度(similarity)は正規化ステップの後に決定されてもよい。
【００１５】
（Ａ）本発明の一形態による方法は、
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをエンコードする方法であって、
類似する幾何学的パターンを検出するステップと、
検出された類似する幾何学的パターンを共通するクラスタに分類するステップと、
クラスタ代表表面を生成するステップと、
クラスタに分類された少なくとも２つの幾何学的パターンについて各自の変位マップを生成するステップであって、前記各自の変位マップの各々は、前記クラスタ代表表面に属する頂点と、クラスタに分類された幾何学的パターンに属する頂点との間の変分を規定する、ステップと、
前記クラスタ代表表面及び前記変位マップをエンコードすることで前記複数の幾何学的パターンをエンコードするステップと
を有する方法である。変位マップのエンコード又は符号化の際に、尺度又はスケーリング、位置、向き又は方向、及び/又はコピー情報が指定してもよい。
【００１６】
（Ｂ）本発明の別の形態による方法は、
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをデコードする方法であって、
第１のデータをデコードし、クラスタ代表表面を求めるステップと、
第２のデータ及び第３のデータをデコードし、少なくとも２つの変位マップを求めるステップと、
前記クラスタ代表表面を設定するステップと、
前記少なくとも２つの変位マップのうちの第１の変位マップを前記クラスタ代表表面に適用することで、第１の幾何学的パターンを再構築するステップと、
前記少なくとも２つの変位マップのうちの第２の変位マップを前記クラスタ代表表面に適用することで、第２の幾何学的パターンを再構築するステップと
を有する方法である。
【００１７】
本方法は、第４のデータをデコードし、前記第１及び/又は第２の幾何学的パターンの位置、向き及びスケールのデータを求めるステップを更に有してもよい。第４のデータは、前記第２又は第３のデータに付随していてもよいし或いは前記第２又は第３のデータから取得されてもよい。
【００１８】
（Ｃ）本発明の更に別の形態による装置は、
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをエンコードする装置であって、
類似する幾何学的パターンを検出する検出手段と、
検出された類似する幾何学的パターンを共通するクラスタに分類するクラスタリング手段と、
クラスタ代表表面を生成する演算手段と、
クラスタに分類された少なくとも２つの幾何学的パターンについて各自の変位マップを生成する変位マップ生成手段であって、前記各自の変位マップの各々は、前記クラスタ代表表面に属する頂点と、クラスタに分類された幾何学的パターンに属する頂点との間の変分を規定する、変位マップ生成手段と、
前記クラスタ代表表面及び前記変位マップをエンコードすることで前記複数の幾何学的パターンをエンコードするエンコード手段と
を有する装置である。
【００１９】
（Ｄ）本発明の他の更に別の形態による装置は、
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをデコードする装置であって、
第１のデータをデコードし、クラスタ代表表面を求める第１のデコーダと、
第２のデータをデコードし、少なくとも２つの変位マップを求める第２のデコーダと、
前記クラスタ代表表面を設定する第１の構築手段と、
前記少なくとも２つの変位マップのうちの第１の変位マップを前記クラスタ代表表面に適用することで、第１の幾何学的パターンを再構築する第２の構築手段と、
前記少なくとも２つの変位マップのうちの第２の変位マップを前記クラスタ代表表面に適用することで、第２の幾何学的パターンを再構築する第３の構築手段と
を有する装置である。
【００２０】
本発明に関する更なる目的、対象、特徴、構成、効果、利点等は、添付図面を参照しながら行われる以下の説明及び特許請求の範囲を考慮することで更に明らかになるであろう。
【００２１】
＜詳細な説明＞
以下、本発明の実施の形態を添付図面を参照しながら説明する。
【００２２】
図2は3Dメッシュモデルの処理を例示的なフローチャートで示す。入力メッシュは複数の幾何学的パターンに分割、分離又は区分けされる(100)。分割等の際に、大きさ、寸法、サイズ、位置、向き、方向等の観点から幾何学的パターンの正規化が行われてもよい。正規化データ(サイズ因子、位置及び方向のデータ)は、幾何学的パターン各々に関連付けられ、或いはリスト等に保存されてもよい。これらは、元のメッシュモデルを再構築する際に使用されることになる。選択的なステップとして、反復的な又は繰り返しの幾何学的パターンが検出される。すなわち、この選択的なステップは、(モデルの空間分解能、モデルの量子化等により決定される制限の範囲内で)厳密に一致する幾何学的パターンを検出する。そのような幾何学的パターンは、本願では「同一群、複製群、コピー群(copy  set)」と言及される。検出された同一のパターンは、本願において「同一群の代表(copy  set  representative)」と言及される1つの代表的なパターンにより表現される。
【００２３】
他の幾何学的パターンは、同一群の代表と共に、それらの類似度に応じてクラスタ化され(200)、類似するパターンは同じクラスタに指定される。クラスタリングステップ200において、幾何学的パターンは互いに比較され、類似するパターンが判定されかつそれらには各自のクラスタが指定される。一実施形態では、幾何学的パターン各々について形状記述子が算出され、形状記述子が互いに比較され、形状記述子の比較結果に基づいてクラスタリングが行われる。更なる詳細については後述する。一実施形態では、クラスタリングステップ200が終わると、入力メッシュの部分各々に1つの幾何学的パターンクラスタが指定されている。別の実施形態では、類似する部分を表現する幾何学的パターンが一切検出されなかった場合、或いは検出された幾何学的パターンの類似度が十分に良い値でなかった場合、入力メッシュの1つ以上の部分にはクラスタが指定されない。これは、例えば、後述の相対的エンコード方法が従来のエンコード方法よりも多いビットを必要とするような場合である。概して、後述のエンコード方法は、より効果的又は効率的であり、クラスタ毎に属する幾何学的パターンが多いほど、クラスタ中の幾何学的パターンは、より類似するようになる。
【００２４】
「部分的類似度検出」のステップ300において、クラスタのエレメントに共通する代表(common  representative)が決定される。それは、「クラスタ代表表面(cluster  representative  surface：CRS)」又は「初期共通面」と言及される。なぜなら、それは全てのクラスタエレメントを表現する際に使用される面だからである。概して、クラスタ代表表面は、そのクラスタが指定されている全ての幾何学的パターンに可能な限り類似している幾何学的パターンである。CRSを取得するために差分法を使用することができる。一実施形態では、そのクラスタに属するように指定されている全ての幾何学的パターンを平均化することで、CRSが取得される。別の実施形態では、クラスタに属する全ての幾何学的パターンに規則定なグリッド又は格子を当てはめ、ボクセル(voxel)の外側の可視的な抽出することで、CRSが取得されてもよい。ボクセルは体積領域のピクセルであり、3D空間内の規則的なグリッドにおける値を表現する体積要素である。パターンクラスタのボクセル形状は、クラスタに属する全てのパターンモデルの内部にある全てのグリッドボクセル群として定義される。一実施形態において、平均化された幾何学的パターン又はボクセル形状は、(解析的又は数値的な)最適化関数により更に最適化されてもよい。
【００２５】
クラスタに属するように指定されている(全ての又はほとんど全ての)個々の幾何学的パターンは、CRSと相違するので、その相違は、以下において詳細に説明するように、クラスタのCRSと個々の幾何学的パターン各々とを比較することで判定される。そして、変位マップ(displacement  map)を用いて幾何学的パターン各々について別々に相違がエンコード又は符号化される。図3(a)は変位マップの一般的な利用法を示す。微小で可視的でない表面の影響、例えば表面の構造、組成、テクスチャ、光及び影等の影響を考慮するための変位マップが従来使用されているが、本発明は、幾何学的パターンを差分符号化するため、すなわち実際の幾何学的パターンとCRSとの間の相違を表現するために変位マップを使用している。これは、2つ以上の類似する幾何学的パターンが1つのCRSを共有できるという利点をもたらす。変位マップは、完全な幾何学的パターンよりもはるかに少ないビット数しか符号化に必要としないので、顕著なデータ量の削減効果(すなわち、冗長性の排除)を発揮できる。共通するクラスタに属するように指定される類似する幾何学的パターンが多いほど、効率的に符号化できる。
【００２６】
一実施形態において、変位マップはCRSの頂点に対する空間的な変位、変分又は偏移を規定する。空間的な変位は空間内での並進運動である。一実施形態において、並進運動の方向は頂点の各々についてそれぞれ規定されてよい。一実施形態において、並進運動の方向は、3Dメッシュモデルについて知られている頂点法線(normal  of  vertex)の方向であるように規定される。すなわち、幾何学的パターンの変位マップは、実際の幾何学的パターンの頂点に合わせる場合に、クラスタ代表表面内の頂点各々を各自の頂点法線の方向に動かさなければならない量を規定する。一実施形態では、CRSは実際の幾何学的パターンよりも多い数の頂点を有する場合、変位マップは、例えばゼロである変位量を指定することで、CRSの1つ以上の頂点が飛び越えられる又はスキップされるようにしてもよい。一実施形態では、CRSは実際の幾何学的パターンよりも少ない数の頂点を有する場合、変位マップはCRSの1つ以上の頂点を2回(又はそれ以上)使用してもよい。一実施形態において、変位マップは異なる変位方向を規定してもよい。変位マップは、単なる一連の数として実現されてもよく、その場合、各々の数が頂点の変位を表し、例えば頂点は図1に示されているストリップのように明示的又は黙示的であってもよい。CRSの頂点の数が変更される実施形態の場合、位置、スケール又は向きのデータについて追加的なセクションがリストに含められてもよい。このリストは任意の圧縮方法により更に圧縮されてもよい。
【００２７】
図3(b)に示す例の場合、変位マップはCRSであるSrepの頂点v2に2つの変位ベクトルdv20，dv21を指定し、実際の幾何学的パターンSactの頂点の数を増やしている。この処理は、1つ以上の頂点に対して、或いは全ての頂点に対してさえ実行されてよい。2つ以上の変位ベクトルdv20，dv21は、必須ではないが、異なる方向を向いていてもよい。
【００２８】
図4はエンコード又は符号化の一例を示す。この例では、3Dメッシュモデルが(同時に目視できる)4つの個別的な要素301−304を有する。図4では、要素301−304は既に分離間は分割され、正規化又は規格化されていることが仮定されている。反復的なパターン検査ブロック100では、2つの要素303、304のパターンが厳密に一致していることが検出される。これらは、1つの同一群の代表313と要素303、304の詳細を示す同一群情報(例えば、リスト)とにより表現できる。303、304のような要素は、同一群の代表313、又は変位マップ及びCRSをそれぞれ指すリファレンス、個々の位置、向き、及び寸法(スケール)303a、304aによりエンコード又は符号化される。簡明化のため、要素は図4の輪郭図321−323で描かれている。クラスタリングブロック200では、要素321−323が類似していることが判定され、部分的な類似度検出ブロック300ではCRS320が生成される。例えば、CRS320は、全ての幾何学的パターン321−323に含まれる一群のボクセルである(図4(b)に示されているように、類否判断は規格化又は正規化の後に行われる)。この例の場合、1つのパターンは同一群の代表313である。同一群に属する各々についての情報303a、304aは、同一群の代表のデータから分離されてもよいし、それに付随していてもよい。
【００２９】
要素の各々は、各自が関連する特定のクラスタ(例えば、クラスタID又はCRSのID)及びそのクラスタのCRS320により表現され、個々の変位マップ341−343はCRSからの各自の変位又は変分を規定する。更に、要素は、要素の寸法又はスケール、位置及び方向を規定する関連データ301a−304aを有し、及び/又は同一群の代表313として例示的に示されているような個々の同一物を規定する別の関連データを有していてもよい。そして、CRS及び変位マップはエントロピ符号化される。これらは既存の任意のエントロピ符号化方法を用いて別々に又は一緒にエントロピ符号化されてよい。
【００３０】
図5は一実施形態における例示的なデコード方法又は復号化方法を示す。スケール、大きさ、寸法、位置、向き、方向及び(必要に応じて)コピーデータ403a等のような関連する量と共にCRS400及び個々の変位マップ401−403により表現されているように、複数のエンコードされた要素はエントロピーデコード又はエントロピ復号化される。元々の要素411、412、413は、変位マップをCRS400に適用することで再構築される(400)。要素413のような同一群の表現の場合、個々のコピー423、424の各々は、コピー群情報403aに従って同一群の代表を複製することで再構築できる。そして、元々の要素は、スケール、寸法、位置、向きの情報を個々の要素各々に適用することで再構築される。上述したようにブロック200では、ブロック100により生成された幾何学的パターンを分類又はクラスタリングしている。クラスタリングは、図6に示されているような半径角度(radius  angle)と呼ばれる形状記述子に基づいている。パターンメッシュPの半径角度A(P)は、次のようにして計算される。
【００３１】
【数１】
2013539125.tif 000003
半径角度A(P)は正規化の後に要素をクラスタに分類するために使用されてもよい。通常、3Dメッシュモデルは、複数のクラスタに分類される多数の要素を有する。上述したように、ブロック300では、共通するパターンクラスタに属する幾何学的パターンの中で、部分的な類似度(similarity)が計算される。ブロック300の具体的な詳細については図7に示されている。処理は、クラスタのパターンモデル全てに属する初期表面を設定することから始まる。反復的なローカル微調整プロセスにより共通表面が計算される。初期化ブロック310では、全ての幾何学パターンを規則的なグリッドに組み込むことで初期共通表面が算出される。パターンクラスタのボクセル外殻(voxel  hull)はパターンモデル全ての内側にある一群の全てのグリッドボクセルである。次に、ボクセル外殻の可視的な外部表面が、初期共通表面、すなわちCRSとして抽出される。
【００３２】
反復的な適合ブロック320は、共通表面を反復的に適合し、パターンモデルをできるだけ多く表現するようにする。反復処理の各々は、照合ブロック321における照合の処理、及び変形ブロック322における変形(deformation)の処理から成る。共通表面が安定化した場合、又は反復の最大回数に達した場合に、この処理は終了する。
【００３３】
照合ブロック321では、共通表面上の頂点の各々と、現在のパターンモデルクラスタに属するパターンモデルの各々における最も近い位置とを照合する。viが共通表面上の1つの頂点であり、wijがviに最も近いパターンモデルPjの頂点であったとする。微調整ブロック322では、(viをパラメータとして)以下の数式(eq．2)を最適化することで新たな共通表面を計算し、CRSを出力する。微調整はCRS及び変位を最適化する。
【００３４】
【数２】
2013539125.tif 000004
ここで、viは共通表面の頂点の新たな位置であり、vi’は共通表面の頂点の現在の位置であり、‖x，y，z‖はベクトル(x，y，z)の長さを示す。
【００３５】
数式(Eq．2)はエネルギ関数(原則として冗長性又は重複性(redundancy)に対応する)を表す項を示す。最適化はエネルギを最小化することを意味する。数式Eq．2の場合、c1、c2及びc3により重み付けされている様々な項は、以下の意味を有する：c1により重み付けされている第1の項は、変位させたCRS頂点と実際の頂点との間の距離(すなわち、合致性)を表す。c2により重み付けされている第2の項は、変位させたCRS頂点の法線と実際の頂点での法線との間の距離(すなわち、法線の合致性)を表す。c3により重み付けされている第3の項は反復ステップサイズを表す。言い換えれば、第1の項は、復元されたメッシュを元のメッシュの方に引き付け、第2の項は元々のメッシュのローカルな詳細事項(法線方向)を維持し、第3の項は共通表面を以前の反復に合う位置の方に引き付ける(すなわち、前回の反復内容と比較している)。c1、c2、c3はパラメータであり、例えばユーザが規定する閾値である。簡明化のため、初期状態でc1＝c2＝c3＝1と設定し、以後数式に従って修正されてゆくものとする。数式Eq．4のliはいわゆるラプラシアンベクトル(非特許文献5)であり、局所的な法線を近似するために使用できる。
【００３６】
確認ブロック330は、パターンメッシュ各々の変位マップを算出し、共通表面及び変位マップがパターンメッシュを表現しているか否かを確認する。パターンメッシュPの場合、その変位マップは図8に示されているようにして計算され、ここで、Pはパターンメッシュであり、Sはその対応する共通表面である。ラプラシアンベクトルは次式に従って計算できる。
【００３７】
【数３】
2013539125.tif 000005
変位マップは次式に従って計算できる。
【００３８】
【数４】
2013539125.tif 000006
復元されたパターンメッシュはP’＝P＋hp(・)である。P’及びPの間の距離が、あるユーザにより決定された閾値よりも小さかった場合、Pは対応する共通表面S及び変位マップh()により表現できる。P’及びPの間の距離は、いわゆるハウスドルフ距離(Husdorff  distance)であってもよい。2つのメッシュ間のこの距離を計算する方法の1つは非特許文献6に記載されている。上記のユーザが規定する閾値は現在における必要性に合わせられていてもよく、圧縮は損失を伴ってもよいし(ロスあり)又は(少なくとも可視的には)伴わなくてもよい(ロスレス)。
【００３９】
出力のコンパクト表現に関し、ブロック300で計算された共通表面も幾何学的パターンと言及される。
【００４０】
一実施形態において、マルチ接続3Dメッシュモデルのコンパクト表現は、以下のものを含む：
＿幾何学的パターンの数を示す何らかのビット。CRSも幾何学的パターンとして表現される。
＿幾何学的パターンの各々についての、圧縮された幾何学パターンを表現するためのビット。
＿インスタンス(instance)の数を表現する何らかのビット。
＿インスタンスの各々についての、位置を示すビット、スケーリング又は寸法を示すビット、向き又は方向の軸を示すビット、幾何学的パターン識別子を示すビット、変位マップが必要であるか否かを示す1ビットフラグ、及び(1ビットフラグが1であった場合)個々の変位マップを示すビット。
【００４１】
図9は、(必須ではないが)1つ以上の3Dメッシュモデルの接続要素である複数の幾何学的パターンeiをエンコード又は符号化する装置の一形態を示す。装置は、類維持する幾何学的パターンを検出する検出手段92と、検出された類似する幾何学的パターンを同じくラスタに分類する(クラスタリングする)クラスタリング手段93と、クラスタ代表表面を生成する演算手段94と、少なくとも2つのクラスタリングされた幾何学的パターン各々の変位マップを生成する変位マップ生成手段95a、95bと、クラスタ代表表面及び変位マップにより複数の幾何学的パターンをエンコードするエンコーダ96とを有し、変位マップの各々はクラスタ代表表面の頂点とクラスタリングされた幾何学パターンの頂点との間の変位を規定している。エンコーダはエンコードされたデータストリームe0を出力する。本装置は1つ以上の変位マップ生成手段95a、95bを備えていてもよい。一実施形態において、検出手段92は、検出された幾何学的パターンを正規化又は規格化し、検出された幾何学的パターンに関する位置、方向及び寸法を提供する正規化部91a(例えば、演算手段)を有する。全部又は一部のモジュールが共通ストレージ手段97にアクセスしてもよい。
【００４２】
一実施形態において、類似する幾何学的パターンを検出する検出手段92は、(正規化の後に)一致する少なくとも2つの幾何学的パターンを始めに検出し、それらを同一群代表幾何学的パターンの例として表現する同一物検出手段又はコピー検出手段91bを有する。この場合、以後のモジュール(クラスタリング手段93、CRS演算手段94、変位マップ生成手段95a、95b及びエンコーダ96)は、個々の同一の幾何学的パターンではなく同一群の表現を使用し、エンコーダ96は、同一群の表現を指すリファレンスや、個々の位置、方向及び寸法の情報を、少なくとも2つの対象とする幾何学的パターンと共にエンコードする。
【００４３】
図10は、(必須ではないが)1つ以上の3Dメッシュモデルの接続要素である複数の幾何学的パターンを入力データストリームからデコード又は復号化する装置の一例を示す。本装置は、クラスタ表現表面111を取得するための第1のデータをデコードする第1のデコーダ101(すなわち、CRSデコーダ101)と、少なくとも2つの変位マップ112a、112bを取得するための第2のデータをデコードするための第2のデコーダ102と、クラスタ表現表面113を再構築する第1の再構築手段103(すなわち、CRS再構築手段103)と、少なくとも2つの変位マップのうち第1の変位マップ112aをクラスタ代表表面に適用することで、第1の幾何学的パターン114aを再構築する第2の再構築手段(すなわち、幾何学的パターン再構築部104a)と、少なくとも2つの変位マップのうち第2の変位マップ112bをクラスタ代表表面113に適用することで、第2の幾何学的パターン114bを再構築する第2の再構築手段104bとを有する。第2及び第3の再構築手段104a、104bは同一であってもよく、すなわち1つの幾何学的パターン再構築手段104であってもよい。或いは、同時に処理を行う場合に有利であるように多数の幾何学的パターン再構築手段が存在していてもよい。
【００４４】
一実施形態において、デコードを行う装置は、入力データストリーム110から第3のデータをデコードし、第1及び/又は第2の及び/又は別の幾何学的パターンの位置、方向及びスケールのデータ115を取得する第3のデコーダ105を更に有し、そのデータは、以後、個々の幾何学的パターンを再構築するために使用される。一実施形態において、合成手段106(例えば、レンダリング装置)は、少なくとも第1及び第2の再構築された幾何学的パターン114a、114b、及び選択的な別の幾何学的パターン114xを、出力される3Dメッシュモデル116に合成する。
【００４５】
一実施形態では、デコーダは、(要素413のような)同一群の代表である幾何学的パターンから少なくとも2つの同じ要素を再構築する第4の再構築手段107を更に有し、その2つの同一の要素は、異なる位置、向き及び/又はサイズの付随情報を有している。コピー群の情報403aに従って又は要素を表現するデータ群に関連する個々の要素情報に従って同一群表現を複製又はコピーすることで、個々のコピー423、424の各々が再構築されてもよい。
【００４６】
一実施形態では、図11(a)に示されているように、複数の幾何学的パターンをエンコードする方法において、複数の幾何学的パターンは(必須ではないが)1つ以上の3Dメッシュモデルの接続要素であり、当該方法は、類似する幾何学的パターン301、302、303、304を検出するステップ201と、検出された類似する幾何学的パターンを共通するクラスタに分類するステップ203と、CRS320を生成又は算出するステップ204と、クラスタに分類された少なくとも2つの幾何学的パターンについて各自の変位マップを生成するステップ205であって、前記各自の変位マップの各々は、前記CRS320に属する頂点と、クラスタに分類された幾何学的パターンに属する頂点との間の変分を規定する、ステップ205と、前記CRS及び前記変位マップをエンコードすることで前記複数の幾何学的パターンをエンコードするステップとを有する。
【００４７】
一実施形態では、類似する幾何学的パターンを検出するステップ201において、前記接続要素を正規化し201a、類似度を判定するために正規化された要素を互いに比較してもよい。正規化の際に、サイズ(すなわち、寸法、スケーリング)、方向(すなわち、向き、回転)及び/又は位置(すなわち、並進運動)等の幾何学的パターンに対する量を正規化する。
【００４８】
一実施形態において、クラスタのCRSを生成又は計算するステップ204において、クラスタに分類された幾何学的パターンを平均化してもよい。
【００４９】
一実施形態において、前記類似する幾何学的パターンを検出する前記ステップにおいて、(一実施形態では正規化の後に)等しい少なくとも２つの幾何学的パターンを検出し202、該検出したものを幾何学的パターンの代表を表わすものとして表現する313初期ステップを行い、クラスタに分類する前記ステップ203及び以後のステップにおいて、前記幾何学的パターンの代表313が個々の等しい幾何学的パターン303、304の代わりに使用される。一実施形態では、何れの幾何学的パターンの代表が参照されているかを示す通知情報又はインジケータが、幾何学的パターン又はその変位マップと共にエンコードされる。それは変換情報を示してもよく、すなわち位置、方向及びスケールの内の1つ以上を示してもよい。一実施形態では、等しい幾何学的パターン303、304が、それらの共通表現320(又はその識別子)、単独の変位マップ及び異なる各自の変換情報データ群によりエンコードされたデータストリームの中で表現される。
【００５０】
一実施形態では、クラスタに属する少なくとも2つの幾何学的パターンについて変位マップを生成するステップ95において、(上記の数式Eq．2)エネルギ関数を最小化する。一実施形態では、エネルギ関数は反復的に最小化される。一実施形態では、エネルギ関数は、頂点の位置が合致していることを示す第1の部分と、垂直方向が合致していることを示す第2の部分とを有する。エネルギ関数が反復的に最小化される場合、そのエネルギ関数は反復ステップサイズを表現する第3の部分を含んでいてもよい。
【００５１】
一実施形態において、変位マップは、各自の垂線方向におけるクラスタ代表表面の頂点各々の変位を規定する。一実施形態において、変位マップは、頂点の変位方向を追加的に規定していてもよい。変位方向は、例えば、頂点の垂線方向からの変位量、のように差分符号化されてもよい。
【００５２】
一実施形態において、初期の共通する表面を算出するステップ204は、反復の各々において、照合するステップ(すなわち、共通の表面の頂点各々を、現在のパターンモデルクラスタのパターンモデル各々における最も近い位置に合わせる処理)と変形するステップ(すなわち、位置のずれ及び垂直方向のずれを最小化する処理)とを含んだ処理を反復することを含む。一実施形態において、数式Eq．5によるラプラシアンベクトルが垂直方向を近似するために使用されてもよい。
【００５３】
一実施形態において、CRSを計算するステップ204において、クラスタに属する全ての幾何学的パターンを規則的なグリッドに組み込み、ボクセル外殻の可視的な外側表面を初期共通表面として抽出する。パターンクラスタのボクセル外殻は、全てのパターンモデルの内側にある一群の全てのグリッドボクセルである。
【００５４】
一実施形態において、CRS初期共通表面を計算するステップ204は、数式Eq．2による最適化を行ってもよい。
【００５５】
一実施形態において、本方法は、クラスタの代表表面及び変位マップを保存及び/又は送信するステップ有してもよい。
【００５６】
一実施形態において、図11(b)に示されているように、１つ以上の3Dメッシュモデルの接続要素である複数の幾何学的パターンをデコードする方法は、第1のデータをデコードし、クラスタ代表表面420を求めるステップ501と、第2のデータをデコードし、少なくとも2つの変位マップを求めるステップ502と、CRS420を設定するステップ503と、前記少なくとも2つの変位マップのうちの第1の変位マップをCRS420に適用することで、第1の幾何学的パターンを再構築するステップ504と、前記少なくとも2つの変位マップのうちの第2の変位マップをCRS420に適用することで、第2の幾何学的パターンを再構築するステップ505とを有する方法である。
【００５７】
デコード方法の一形態では、第3のデータをデコードし、第1の幾何学的パターン421及び第2の幾何学的パターン422の位置、方向及びスケールのデータを取得するステップを更に有する。
【００５８】
上記の実施の形態では、クラスタについて共通する代表(common  representatives)がボクセルの最小共通サブセット(a  least  common  subset)であったが、クラスタについて他のタイプの代表が構築されてもよく、このことは当業者にとって明らかであり、何れについても全て本発明の精神及び範囲に包含されることに、留意すべきである。
【００５９】
以上、好ましい実施の形態に適用される本発明の基礎的な新規な特徴が示され、説明され、提示されてきたが、説明された装置及び方法等において様々な省略、置換及び変更が、開示された装置の形態及び詳細において並びに動作例において、本発明の範囲から逸脱せずに当業者によってなされてもよいことが、理解されるであろう。本発明は回転対称な要素の観点から説明されてきたが、当業者は本方法及び本装置等は任意のタイプの要素に適用されてよいことを認めるであろう。1つ以上の3Dメッシュモデルの考察する要素として複数の幾何学的パターンが説明されてきたが、複数の幾何学的パターンは、原則として、一緒に符号化又はエンコードされる任意の一群の幾何学的パターンを含んでもよく、特に幾何学的パターンの冗長性がエンコード又は符号化される。実質的に同じ方法で同じ結果に至る実質的に同じ機能を実行する要素の全ての組み合わせが、本発明の範囲内に属することが、明示的に意図されている。説明された或る実子の形態の要素を別の実施の形態に置換することも当然に想定されており、本願で意図されている。簡明化のために幾何学的モデルを示すために付されている参照番号又は参照符号は、それら幾何学的モデルを表現するデータを参照しているに過ぎないことが理解されるべきである。
【００６０】
本発明は単なる一例として説明されており、様々な具体的詳細の変形は本発明の範囲から逸脱することなく可能であることが、理解されるべきである。明細書、特許請求の範囲及び(存在する場合の)添付図面に記載されている事項は独立に又は適切な任意の組み合わせにより与えられてよい。特徴は、ハードウェア、ソフトウェア又はそれらの組み合わせにより実現されてよい。特許請求の範囲における参照番号(存在する場合)は、単なる例示であるに過ぎず、特許請求の範囲を限定する如何なる効果も有しない。
【図１】
2013539125.tif 000007
【図２】
2013539125.tif 000008
【図３】
2013539125.tif 000009
【図４ａ）】
2013539125.tif 000010
【図４ｂ）】
2013539125.tif 000011
【図５】
2013539125.tif 000012
【図６】
2013539125.tif 000013
【図７】
2013539125.tif 000014
【図８ａ）】
2013539125.tif 000015
【図８ｂ）】
2013539125.tif 000016
【図９】
2013539125.tif 000017
【図１０】
2013539125.tif 000018
【図１１ａ）】
2013539125.tif 000019
【図１１ｂ）】
2013539125.tif 000020
【手続補正書】
【提出日】平成25年8月28日(2013.8.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをエンコードする方法であって、
類似する幾何学的パターンを検出するステップと、
検出された類似する幾何学的パターンを共通するクラスタに分類するステップと、
クラスタ代表表面を生成するステップと、
クラスタに分類された少なくとも２つの幾何学的パターンについて各自の変位マップを生成するステップであって、前記各自の変位マップの各々は、前記クラスタ代表表面に属する頂点と、クラスタに分類された幾何学的パターンに属する頂点との間の変分を規定する、ステップと、
前記クラスタ代表表面及び前記変位マップをエンコードすることで前記複数の幾何学的パターンをエンコードするステップと
を有する方法。
【請求項２】
類似する幾何学的パターンを検出する前記ステップにおいて、前記接続要素を正規化し、正規化された要素を互いに比較し、該正規化された要素は、位置、方向及びサイズを示す、請求項１に記載の方法。
【請求項３】
元々の要素各々の位置情報、方向情報及び/又はサイズ情報に変位マップが関連付けられる、又は元々の要素各々の位置情報、方向情報及び/又はサイズ情報が変位マップに含まれる、請求項２に記載の方法。
【請求項４】
クラスタについて前記クラスタ代表表面を生成するステップにおいて、該クラスタに属するように分類された幾何学的パターンを平均化する、請求項１−３の何れか１項に記載の方法。
【請求項５】
前記類似する幾何学的パターンを検出する前記ステップにおいて、正規化の後に等しい少なくとも２つの幾何学的パターンを検出し、該検出したものを幾何学的パターンの代表を表わすものとして表現する初期ステップを行い、
クラスタに分類する前記ステップ及び以後のステップにおいて、前記幾何学的パターンの代表が個々の等しい幾何学的パターンの代わりに使用され、何れの幾何学的パターンの代表が参照されているかを示す通知情報が、少なくとも２つの幾何学的パターンと共にエンコードされる、請求項１−４の何れか１項に記載の方法。
【請求項６】
前記変位マップが、垂直方向における前記クラスタ代表表面の少なくとも１つの頂点の変位を規定する、請求項１−５の何れか１項に記載の方法。
【請求項７】
クラスタに分類された前記少なくとも２つの幾何学的パターンについて各自の変位マップを生成するステップにおいて、エネルギ関数を最小化する、請求項１−６の何れか１項に記載の方法。
【請求項８】
前記エネルギ関数は反復的に最小化され、前記エネルギ関数は、頂点の位置の合致性を示す第１の項と、垂直方向の合致性を示す第２の項と、反復ステップサイズを示す第３の項とを含む、請求項７に記載の方法。
【請求項９】
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをデコードする方法であって、
第１のデータをデコードし、クラスタ代表表面を求めるステップと、
第２のデータ及び第３のデータをデコードし、少なくとも２つの変位マップを求めるステップと、
前記クラスタ代表表面を設定するステップと、
前記少なくとも２つの変位マップのうちの第１の変位マップを前記クラスタ代表表面に適用することで、第１の幾何学的パターンを再構築するステップと、
前記少なくとも２つの変位マップのうちの第２の変位マップを前記クラスタ代表表面に適用することで、第２の幾何学的パターンを再構築するステップと
を有する方法。
【請求項１０】
前記第２又は第３のデータから取得された第４のデータをデコードし、前記第１及び/又は第２の幾何学的パターンの位置、方向及びスケールのデータを求めるステップを更に有する請求項９に記載の方法。
【請求項１１】
少なくとも第１及び第２の再構築された幾何学的パターンを３Ｄメッシュモデルに形成するステップを更に有する請求項９又は１０に記載の方法。
【請求項１２】
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをエンコードする装置であって、
類似する幾何学的パターンを検出する検出手段と、
検出された類似する幾何学的パターンを共通するクラスタに分類するクラスタリング手段と、
クラスタ代表表面を生成する演算手段と、
クラスタに分類された少なくとも２つの幾何学的パターンについて各自の変位マップを生成する変位マップ生成手段であって、前記各自の変位マップの各々は、前記クラスタ代表表面に属する頂点と、クラスタに分類された幾何学的パターンに属する頂点との間の変分を規定する、変位マップ生成手段と、
前記クラスタ代表表面及び前記変位マップをエンコードすることで前記複数の幾何学的パターンをエンコードするエンコード手段と
を有する装置。
【請求項１３】
１つ以上の３Ｄメッシュモデルの接続要素である複数の幾何学的パターンをデコードする装置であって、
第１のデータをデコードし、クラスタ代表表面を求める第１のデコーダと、
第２のデータをデコードし、少なくとも２つの変位マップを求める第２のデコーダと、
前記クラスタ代表表面を設定する第１の構築手段と、
前記少なくとも２つの変位マップのうちの第１の変位マップを前記クラスタ代表表面に適用することで、第１の幾何学的パターンを再構築する第２の構築手段と、
前記少なくとも２つの変位マップのうちの第２の変位マップを前記クラスタ代表表面に適用することで、第２の幾何学的パターンを再構築する第３の構築手段と
を有する装置。
【請求項１４】
少なくとも第１及び第２の再構築された幾何学的パターンを３Ｄメッシュモデルに合成する合成手段と、同一群の代表である幾何学的パターンから少なくとも２つの等しい要素を再構築する第４の再構築手段とを更に含み、前記２つの等しい要素は、異なる位置、方向及びサイズの関連情報を有している、請求項１３に記載の装置。
【請求項１５】
少なくとも２つの異なる幾何学的パターンについて共通する表現を示す要素のデータと、
前記共通する表現及び少なくとも２つの幾何学的パターンに関する少なくとも２つの異なる変位マップと
を有する３Ｄメッシュモデルを表現するデータ構造又はデータストリームを用いてエンコード及びデコードを行う方法。
【国際調査報告】
2013539125.tif 000021
2013539125.tif 000022
2013539125.tif 000023