(57)【要約】  3Dモデルは、“パターン・インスタンス”表現を使用してモデル化されてもよい。頂点及び三角形を記述するために、インスタンスの特性（例えば、テクスチャ、色及び法線）は、パターンの順序に対応するように調整される。インスタンスのテクスチャは、対応するパターンのテクスチャとの類似性に依存して符号化される。インスタンスのテクスチャがパターンのテクスチャと同一又はほぼ同一である場合、インスタンスのテクスチャは符号化されず、パターンのテクスチャはインスタンスのテクスチャを再現するために使用される。インスタンスのテクスチャがパターンのテクスチャと類似する場合、インスタンスのテクスチャは、パターンのテクスチャから予測的に符号化される。すなわち、インスタンスのテクスチャとパターンのテクスチャとの間の差分が符号化され、インスタンスのテクスチャは、パターンのテクスチャと差分との組み合わせとして判断される。
2015512072.tif 000002
【特許請求の範囲】
【請求項１】
3Dモデルを表すビットストリームを復号化する方法であって、
パターンのインスタンスが前記パターンの特性を使用するか否かを前記ビットストリームから判断するステップであり、前記パターンは前記3Dモデルの構造に関連し、前記インスタンスは前記パターンの変換として表されるステップと、
前記パターンの前記特性に応じて前記インスタンスの特性を判断するステップであり、前記インスタンスの前記特性は、テクスチャ、テクスチャ座標、色及び法線のうち１つに対応するステップと
を有する方法。
【請求項２】
前記インスタンスの前記特性と前記パターンの前記特性との間の差分を前記ビットストリームから判断するステップを更に有し、
前記インスタンスの前記特性を判断するステップは、前記インスタンスの前記特性と前記パターンの前記特性との間の前記判断された差分に更に応じる、請求項１に記載の方法。
【請求項３】
3Dモデルを表すビットストリームを生成する方法であって、
パターンのインスタンスにアクセスするステップであり、前記パターンは前記3Dモデルの構造に関連し、前記インスタンスは前記パターンの変換として表されるステップと、
前記インスタンスの特性が前記パターンの特性を使用して符号化されたか否かを前記ビットストリームにおいて示すステップであり、前記インスタンスの前記特性は、テクスチャ、テクスチャ座標、色及び法線のうち１つに対応するステップと
を有する方法。
【請求項４】
前記インスタンスの前記特性と前記パターンの前記特性との間の差分を判断するステップと、
前記インスタンスの前記特性と前記パターンの前記特性との間の差分を前記ビットストリームにおいて示すステップと
を更に有する、請求項３に記載の方法。
【請求項５】
前記インスタンスの前記特性は前記テクスチャに対応し、
前記インスタンスのテクスチャのパッチと、前記パターンの対応するテクスチャのパッチとの相関を判断するステップと、
前記インスタンスの前記テクスチャのパッチが前記パターンの対応するテクスチャのパッチを使用して符号化されるか否かを判断するステップと
を更に有する、請求項３に記載の方法。
【請求項６】
前記インスタンスの前記テクスチャのパッチが前記パターンの対応するテクスチャのパッチと同一又はほぼ同一であると判断された場合、前記インスタンスの前記テクスチャのパッチは、テクスチャ画像から除去される、請求項５に記載の方法。
【請求項７】
前記インスタンスの前記テクスチャのパッチが前記パターンの対応するテクスチャのパッチと同一又はほぼ同一であると判断された場合、前記インスタンスの前記テクスチャのパッチの内容は空になる、請求項５に記載の方法。
【請求項８】
前記インスタンスの前記テクスチャのパッチは、前記3Dモデルの一式の隣接する三角形に対応するテクスチャ画像の領域である、請求項５に記載の方法。
【請求項９】
3Dモデルを表すビットストリームを生成する方法であって、
構造に関連するパターンにおける第１の面の頂点の順序を判断するステップと、
複数の特性セットにアクセスするステップであり、前記複数の特性セットの各特性セットは、前記パターンのインスタンスにおける第２の面の対応する頂点に関連するステップと、
前記判断された順序に応じて前記複数の特性セットを並び替えるステップと
を有する方法。
【請求項１０】
前記パターンにおける前記第１の面に対応する前記インスタンスにおける前記第２の面を判断するステップを更に有する、請求項９に記載の方法。
【請求項１１】
前記第１の複数の特性セットの各特性セットは、テクスチャ座標、テクスチャ画像、色及び法線のうち少なくとも１つを含む、請求項９に記載の方法。
【請求項１２】
請求項１ないし１１のうちいずれか１項に記載の方法に従ってビットストリームを生成又は復号化する手段を含む装置。
【請求項１３】
請求項１ないし１１のうちいずれか１項に記載の方法に従ってビットストリームを生成又は復号化する命令を格納したコンピュータ読み取り可能記憶媒体。
【請求項１４】
請求項３ないし１１のうちいずれか１項に記載の方法に従って生成されたビットストリームを格納したコンピュータ読み取り可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この出願は、2012年1月21に出願された中国PCT特許出願第PCT/CN2012/070703号及び2012年4月19日に出願された中国PCT特許出願第PCT/CN2012/074356号の優先権を主張し、これらの全内容を援用する。
【０００２】
本発明は、3Dモデルを表すビットストリームを生成する方法及び装置に関し、これを復号化する方法及び装置に関する。
【背景技術】
【０００３】
実際の用途では、多くの3Dモデルは多数の接続されたコンポーネントで構成される。これらの複数コンポーネントの3Dモデルは、図１に示すように、通常では様々な変換の多くの反復構造を含む。
【０００４】
入力モデルにおける反復構造を利用した複数コンポーネントの3Dモデルの圧縮アルゴリズムが知られている。3Dモデルの反復構造は、様々な位置、方向及び倍率で発見される。3Dモデルは、“パターン・インスタンス（pattern-instance）”表現に構成される。パターンは、対応する反復構造の代表的な幾何学的形状を示すために使用される。反復構造に属するコンポーネントは、対応するパターンのインスタンスとして示され、パターンID及び変換情報（例えば、パターンに関する反射（鏡映）、平行移動、回転及び起こりえる拡大縮小）により表されてもよい。インスタンスの変換情報は、例えば、反射部、平行移動部、回転部、起こりえる拡大縮小部に構成されてもよい。反復的でない3モデルのいくつかのコンポーネントが存在する場合があり、これは特有コンポーネント（unique  component）と呼ばれる。
【０００５】
K.  Cai,  Y.  Jin及びZ.  Chenによる“Efficient  compression  scheme  for  large  3D  engineering  models”という題の同一出願人によるPCT出願（PCT/EP10/058048、代理人管理番号PA090039）は、様々な位置、縮尺及び方向に繰り返す幾何学的特徴を有する3Dモデルの圧縮方法を開示しており、この教示を援用する。
【０００６】
K.  Cai,  W.  Jiang及びJ.  Tianによる“Bitstream  syntax  and  semantics  of  repetitive  structure  discovery  based  3D  model  compression  algorithm”という題の他の同一出願人によるPCT出願（PCT/CN2011/076991、代理人管理番号PA110044）は、インスタンス変換情報を圧縮する２つのモードを開示しており、この教示を援用する。
【０００７】
K.  Cai,  W.  Jiang及びJ.  Tianによる“Method  and  apparatus  for  generating  a  bitstream  of  repetitive  structure  discovery  based  3D  model  compression”という題の他の同一出願人によるPCT出願（PCT/CN2011/082942、代理人管理番号PA110067）は、２つのインスタンス圧縮モード（すなわち、基本インスタンスデータモード及びグループ化インスタンスデータモード）を開示しており、この教示を援用する。
【０００８】
K.  Cai,  W.  Jiang及びT.  Luoによる“System  and  method  for  error  controllable  repetitive  structure  discovery  based  compression”という題の同一出願人によるPCT出願（PCT/CN2012/070877、代理人管理番号PA120001）は、インスタンスのコンポーネント間での冗長性を低減するため、従って圧縮効率を改善するため、3Dモデルにおいて反復構造を識別する方法及び装置を開示しており、この教示を援用する。
【発明の概要】
【課題を解決するための手段】
【０００９】
本発明の原理は、3Dモデルを表すビットストリームを復号化する方法を提供し、以下に説明するように、パターンのインスタンスがパターンの特性を使用するか否かをビットストリームから判断するステップであり、パターンは3Dモデルの構造に関連し、インスタンスはパターンの変換として表されるステップと、パターンの特性に応じてインスタンスの特性を判断するステップであり、インスタンスの特性は、テクスチャ、テクスチャ座標、色及び法線のうち１つに対応するステップとを有する。本発明の原理はまた、これらのステップを実行する装置も提供する。
【００１０】
本発明の原理はまた、3Dモデルを表すビットストリームを生成する方法を提供し、以下に説明するように、パターンのインスタンスにアクセスするステップであり、パターンは3Dモデルの構造に関連し、インスタンスはパターンの変換として表されるステップと、インスタンスの特性がパターンの特性を使用して符号化されたか否かをビットストリームにおいて示すステップであり、インスタンスの特性は、テクスチャ、テクスチャ座標、色及び法線のうち１つに対応するステップとを有する。本発明の原理はまた、これらのステップを実行する装置も提供する。
【００１１】
本発明の原理はまた、3Dモデルを表すビットストリームを生成する方法を提供し、以下に説明するように、構造に関連するパターンにおける第１の面の頂点の順序を判断するステップと、複数の特性セットにアクセスするステップであり、複数の特性セットの各特性セットは、パターンのインスタンスにおける第２の面の対応する頂点に関連するステップと、判断された順序に応じて複数の特性セットを並び替えるステップとを有する。本発明の原理はまた、これらのステップを実行する装置も提供する。
【００１２】
本発明の原理はまた、前述の方法に従ってビットストリームを生成又は復号化する命令を格納したコンピュータ読み取り可能記憶媒体も提供する。
【００１３】
本発明の原理はまた、前述の方法に従って生成されたビットストリームを格納したコンピュータ読み取り可能記憶媒体も提供する。
【図面の簡単な説明】
【００１４】
【図１】多数のコンポーネント及び反復構造を有する例示的な3Dモデルを示す図
【図２Ａ】パターン及びインスタンスを示す図の例
【図２Ｂ】パターン及びインスタンスのテクスチャ画像を示す図の例
【図３Ａ】インスタンスの三角形とパターンの三角形との間の１対１の対応なしに、インスタンスの頂点とパターンの頂点との間の１対１の対応を示す図の例
【図３Ｂ】インスタンスがパターンに対して反転することを示す図の例
【図４】本発明の原理の実施例に従って3Dモデルを符号化する例を示すフローチャート
【図５Ａ】パターン及びインスタンスを示す他の図の例
【図５Ｂ】調整前のインスタンスのテクスチャ座標のリスト
【図５Ｃ】本発明の原理の実施例による調整後のインスタンスのテクスチャ座標のリスト
【図６Ａ】3Dモデルのテクスチャ画像の部分を示す図の例
【図６Ｂ】3Dモデルのテクスチャ画像の部分を示す図の例
【図７】本発明の原理の実施例に従ってパターンの対応するテクスチャのパッチとインスタンスのテクスチャのパッチとの類似性を判断する例を示すフローチャート
【図８】本発明の原理の実施例に従ってテクスチャ符号化モードを判断する例を示すフローチャート
【図９】本発明の原理の実施例に従ってテクスチャ画像を復号化する例を示すフローチャート
【図１０Ａ】テクスチャ画像を示す図の例
【図１０Ｂ】本発明の原理の実施例に従って処理されたテクスチャ画像を示す図の例
【図１０Ｃ】本発明の原理の実施例に従って処理されたテクスチャ画像を示す図の例
【図１１】本発明の原理の１つ以上の実装で使用され得る符号化器の例を示すブロック図
【図１２】本発明の原理の１つ以上の実装で使用され得る復号化器の例を示すブロック図
【図１３】本発明の原理の１つ以上の実装で使用され得るデータ処理システムの例を示すブロック図
【図１４】本発明の原理の１つ以上の実装で使用され得るデータ処理システムの他の例を示すブロック図
【発明を実施するための形態】
【００１５】
図１に示すように、3Dモデルには多くの反復構造が存在することがある。3Dモデルを効率的に符号化するために、反復構造は、パターン及びインスタンスに構成されてもよい。インスタンスは、例えば、対応するパターンのパターンIDと、平行移動、回転及び拡大縮小についての情報を含む変換行列とを使用して、対応するパターンの変換として表される。
【００１６】
インスタンスがパターンIDと変換行列とにより表される場合、パターンID及び変換行列は、インスタンスを圧縮するときに圧縮される。従って、インスタンスは、パターンIDと復号化された変換行列を通じて再現され得る。すなわち、インスタンスは、パターンIDによりインデックス付けされた復号化されたパターンの変換（復号化された変換行列からのもの）として再現されてもよい。
【００１７】
テクスチャ付きの3Dモデルを表すために、１つ以上のテクスチャ画像は、幾何学的形状と共に送信されてもよい。3Dモデルのそれぞれの面は、テクスチャ画像の特定の領域に対応する。頂点毎のテクスチャ画像の対応する座標は、マッピング関係を表すように符号化される。
【００１８】
テクスチャの符号化は、通常では幾何学的形状及び3Dモデルの接続性の符号化より多くのビットを使用するため、テクスチャ情報を効率的に圧縮させることが好ましい。本発明の原理は、反復のテクスチャの間の冗長性を利用することにより、3Dモデルのテクスチャ情報を効率的に圧縮する方法及び装置を提供する。
【００１９】
図２Ａは、例示的なパターン201及び例示的なインスタンス202を示している。各頂点又は面はインデックスにより示される。例えば、パターンの面240はインデックスT6により示され、その３つの頂点はインデックスV13、V12及びV14により示される。インスタンスの対応する面245はインデックスT20により示され、その３つの頂点はインデックスV12、V8及びV3により示される。パターン及びインスタンスが整列されているときに互いに実質的に重複している場合、パターンの面又は頂点はインスタンスの面又は頂点に対応し、その逆も同様であることが示される。対応する面又は頂点のインデックスはパターン及びインスタンスで異なる点に留意すべきである。図２Ｂは、それぞれパターン201及びインスタンス202の例示的なテクスチャ画像203及び204を示している。
【００２０】
3Dモデルは、全ての頂点の座標で構成される頂点テーブル（V0,V1,V2,...）と、頂点テーブルの全ての三角形の頂点のインデックスで構成される三角形テーブル（T0,T1,T2,...）とにより表されてもよい。更にそれぞれの頂点及び三角形は、法線（normal）、色及びテクスチャ座標のような１つ以上の特性を有してもよい。これらの頂点の特性及び三角形の特性は、対応するテーブルの頂点及び三角形に添付されてもよく、頂点／三角形テーブルの同じ頂点／三角形の順序に従って更なる頂点／三角形特性テーブルに格納されてもよい。
【００２１】
表１は、頂点、テクスチャ座標、法線及び面の定義を含む例示的な3Dメッシュファイルを示している。
【００２２】
【表１】
2015512072.tif 000003
表１に示すように、テクスチャ座標のインデックスは、面を定義する際にテクスチャ座標を指定するために使用されてもよい。面の定義のブロックにおいて、フォーマットは、頂点のインデックス／テクスチャ座標のインデックス／法線のインデックスである。面を表すために三角形が使用される場合、それぞれの面は３組のテクスチャ座標のインデックスを有する。全てのこれらの組がリストを形成する。
【００２３】
パターンとインスタンスとの間の対応は、KDツリー（KD-tree）検索のような最近傍検索アルゴリズムにより構築され得る１対１の頂点の対応に基づいてもよい。三角形及びインスタンスの頂点の特性も反復構造に基づいて圧縮される場合、三角形の間の対応も考慮されるべきである。
【００２４】
図３Ａに示す一例では、インスタンスの頂点とパターンの頂点との間に１対１の対応が存在する（VpiはViiに対応する）。しかし、インスタンスの三角形とパターンの三角形との間に１対１の対応は存在しない。三角形の間の対応がなければ、パターンの特性に基づいてインスタンスの三角形の特性を圧縮することは困難になる可能性がある。
【００２５】
従って、インスタンスと対応するパターンとの間での１対１の頂点の対応の他に、１つのインスタンスは、１対１の頂点の対応に一致する対応するパターンと１対１の三角形の対応を有するべきである。１つのインスタンスの全ての三角形は、パターンがインスタンスのコンポーネントに整列された後に、対応するパターンと反対の法線を有してもよい。これは、インスタンス及びパターンが互いに反転していることを意味する。図３Ｂに示すように、三角形TpiはTiiに対応するが、Tpi及びTiiは異なる方向（すなわち、反対の法線）を有する。
【００２６】
パターン及びインスタンスが反復構造に対応するため、インスタンスの幾何学的情報を符号化するために、パターンの幾何学的形状を再利用することが可能になり得る。この例では、他の特性（例えば、非限定的にテクスチャ及び法線）の間の類似性を更に調査する。パターンとインスタンスとの間の冗長性を除去するために、インスタンスを符号化する前にインスタンスの表現を前処理してもよい。
【００２７】
図４は、3Dモデルを符号化する例示的な方法400を示している。方法400において、ステップ410にて3Dモデルのデータ（例えば、幾何学的形状、テクスチャ座標及びテクスチャ画像）が入力される。ステップ420において、3Dモデル内のコンポーネントがパターン及びインスタンスに構成される。ステップ425において、パターンとインスタンスとの間の頂点及び三角形の対応を構築し、インスタンスのコンポーネントの表現を前処理する。次にステップ430において、3Dモデルが符号化される。特に、パターンの特性がインスタンスを符号化するために再利用されてもよい。
【００２８】
以下では、前処理ステップ（430）及び符号化ステップ（440）について更に詳細に説明する。
【００２９】
＜前処理＞
【表２】
2015512072.tif 000004
表２は、共に図２Ａに示すパターン201とインスタンス202との間の頂点及び三角形の間の対応を示している。すなわち、パターン及びインスタンスが同様の構造に対応する場合であっても、3Dメッシュファイルにおけるこれらの表現は異なる。
【００３０】
インスタンスのテクスチャを符号化するために、一実施例では、パターンの幾何学的形状に基づいて、インスタンスの初期のテクスチャ画像における対応する三角形を再配置することにより、新たなテクスチャ画像が生成されてもよい。この再配置の間に、パターンのテクスチャ座標が使用される。すなわち、インスタンスのテクスチャ座標からパターンのテクスチャ座標への変換からマッピングが導かれる。従って、インスタンスは、テクスチャ画像を除きパターンからのテクスチャに関連するデータを使用することが可能になってもよい。
【００３１】
他の実施例では、新たなテクスチャ画像を生成することなく、テクスチャ座標及びインデックスを処理する。まず、テクスチャ座標は、パターンの頂点及び三角形の順序に従って並び替えられてもよい。純粋に幾何学的な情報に基づく反復構造が識別された場合、この情報は、テクスチャデータを処理するために使用されてもよい。
【００３２】
並び替えの例が図５Ａ〜５Ｃに示されいている。まず、例えば最近傍検索により、パターンとインスタンスとの間の頂点の対応が識別されてもよい。頂点の対応を認識すると、三角形の対応が取得されてもよい。次に、この手順を全ての頂点及び三角形について実行し、表２に示す対応テーブルを取得する。頂点の対応及び三角形の対応は１対１になる必要がある点に留意すべきである。例えば、パターン201の頂点201（頂点のインデックスV13）は、インスタンス202の頂点215（頂点のインデックスV12）に対応し、パターンの面／三角形240（面のインデックスT6）は、インスタンスの面／頂点245（面のインデックスT20）に対応する。１つの例示的な実施例では、パターンの面T6はT6:V12/TEX_12  V13/TEX_13  V14/TEX_14と記述され、インスタンスの面T20はT20:V3/TEX_3  V8/TEX_8  V12/TEX_12と記述される。インデックス／テクスチャ座標のインデックスは、ここでは面を表すために使用される点に留意すべきである（すなわち、法線のインデックスは示されていない）。
【００３３】
図５Ｂ及び５Ｃは、それぞれ調整前後の例示的なテクスチャ座標を示している。調整前では、インスタンスの面の定義は、インスタンスの頂点のインデックス及び三角形のインデックスに基づく。調整後では、インスタンスは、対応するパターンの頂点のインデックス及び三角形の順序を使用する。従って、T20:V3/TEX_3  V8/TEX_8  V12/TEX_12はT6:V12/TEX_8  V13/TEX_12  V14/TEX_3に変更される。従って、インスタンスにおける面245のテクスチャ座標は、TEX_3,TEX_8,TEX_12（図５Ｂに示す）からTEX_8,TEX_12,TEX_3（図５Ｃに示す）になる。色及び法線のような他の特性が考慮される場合、これらも同様に並び替えられる必要がある。
【００３４】
＜符号化＞
前処理の後に、パターンの特性（例えば、テクスチャ、法線）は、インスタンスの特性を効率的に符号化するために使用されてもよい。一実施例では、本発明の原理は、パターン及びインスタンスのテクスチャの間の類似性を検査する。パターン及びインスタンスのテクスチャ座標が同一である場合、すなわち、インスタンスがパターンと同じテクスチャを使用する場合、そのインスタンスについてテクスチャは符号化されない。むしろ、インスタンスを再現するときにパターンのテクスチャをコピーすることを復号化器に通知するために、フラグがビットストリームに書き込まれる。パターン及びインスタンスのテクスチャ座標が異なる場合、テクスチャ画像の対応する領域の内容がパターンとインスタンスとの間で比較される。内容が異なる場合、インスタンスのテクスチャ座標が符号化される。内容が同一又はほぼ同一である場合、インスタンスに対応する領域はテクスチャ画像から除去され、復号化器は、インスタンスを再現するときにパターンのテクスチャをコピーする。
【００３５】
内容が或る程度類似している場合、パターンとインスタンスとの間の差分画像が生成され、テクスチャ画像のインスタンスに対応する領域は、差分画像と置換され、差分画像をインスタンスのテクスチャに追加することによりインスタンスのテクスチャを生成することを復号化器に通知するために、フラグがビットストリームに書き込まれる。従って、インスタンスのテクスチャは、テクスチャ画像の冗長性を利用するようにパターンのテクスチャから予測的に符号化される。
【００３６】
テクスチャの特性に加えて、他の特性（例えば、非限定的にインスタンスの法線及び色）も、対応するパターンの特性と同一でも又は類似してもよい。テクスチャと同様に、インスタンスのこれらの特性は、パターンの特性から予測可能であり、特性の代わりに予測誤差が符号化される。以下では、インスタンスを符号化するときにパターンとインスタンスとの間の類似性をどのように使用することができるかを示す例として、テクスチャを使用する。
【００３７】
テクスチャの特性を効率的に符号化するために、テクスチャの表現について４つのテクスチャ符号化モードが規定される。
【００３８】
モード1：パターン及びインスタンスのテクスチャ座標は同一である。このモードでは、インスタンスのテクスチャ内容及びテクスチャ座標は符号化されない。
【００３９】
モード2：パターン及びインスタンスのテクスチャ座標は異なり、テクスチャの内容は同一又はほぼ同一である。このモードでは、インスタンスのテクスチャ座標は符号化されるが、テクスチャ内容はスキップされる。
【００４０】
モード3：パターン及びインスタンスのテクスチャ座標は異なり、テクスチャの内容は類似する。このモードでは、インスタンスのテクスチャ座標は符号化され、パターンとインスタンスとの間のテクスチャの差分が符号化される。従って、パターンのテクスチャからインスタンスのテクスチャを予測することから圧縮の恩恵がある。
【００４１】
モード4：パターン及びインスタンスのテクスチャ座標並びにテクスチャの内容は異なる。このモードでは、インスタンスのテクスチャ内容及びテクスチャ座標は通常通り符号化される。
【００４２】
図６Ａ及び６Ｂは、ウサギの目に対応する3Dモデルのテクスチャ画像の部分を示している。図６Ａの目は図６Ｂの目に非常に似ており、一方の目を使用して他方を表すことは可能である。例示目的で、これらの２つの目が２つのコンポーネントA及びBに属することを仮定する。コンポーネントBはパターンAのインスタンスであり、問題は、BのテクスチャがAのテクスチャにより表されることが可能であるか否かを判断することである。
【００４３】
BのテクスチャがAのテクスチャにより表されることが可能であるか否か及びどのように表されることが可能であるかを判断するために、コンポーネントの表面の全てのテクスチャを比較する代わりに、パッチの単位でテクスチャを比較する。パッチは、3Dモデルにおいて隣接する三角形のセットに対応するテクスチャ画像である。これはコンポーネントの１つ以上の三角形を含んでもよい。正確にいくつの三角形がパッチに存在するかは、入力3Dモデルに依存し得る。
【００４４】
図７は、パターンの対応するテクスチャのパッチとインスタンスのテクスチャのパッチとの類似性を判断する例示的な方法700を示している。方法700は、初期化ステップ705で始まる。初期化ステップは、テクスチャ画像を複数のパッチに分割してもよい。各パッチは、１つ以上のコンポーネントの一部に対応し、１つ以上のコンポーネントのIDは記録されてもよい。方法700において、パッチが全てのインスタンスについてパターンと同一又はほぼ同一であることを示すために、“除去”フラグを使用し、パッチがパターンと類似していることを示すために、“置換”フラグを使用する。初期化ステップにおいて、“除去”及び“置換”の双方のフラグは0に設定される。
【００４５】
ステップ710において、パッチがパターン又は特有コンポーネントの部分のテクスチャを表すか否かを検査する。そうである場合、制御は終了ステップ799に渡される。そうでない場合、方法700は、テクスチャのパッチの検査に進み、テクスチャがパッチにより（部分的に）表される各インスタンスを検査する。
【００４６】
ステップ720において、特定のマッチング基準（例えば、平均二乗誤差（MSE：mean  square  error））を使用して、テクスチャのパッチと、そのパターンにより使用される対応するパッチとを比較する。ステップ730において、インスタンスのテクスチャとパターンのテクスチャとの間の相関を検査する。テクスチャがかなり相関している場合（例えば、MSE＜閾値0）、インスタンスのテクスチャは、パターンのテクスチャと同一又はほぼ同一と考えられ、これはパターンのテクスチャにより表されてもよい。この場合、ステップ750において、“除去”フラグが1に設定され（すなわち、パッチは除去されるものとしてタグ付けされる）、例えば、インスタンスのテクスチャとパターンのテクスチャとの間の相対位置に従ってインスタンスのテクスチャ座標を平行移動することにより、テクスチャ座標が更新されてもよい。テクスチャが中程度に相関している場合（例えば、閾値0≦MSE＜閾値1）、ステップ740において、インスタンスが１つのみのパッチを有するか否かを検査する。そうでない場合、ステップ770に進む。そうでない場合、ステップ745において、“置換”フラグが1であるか否か（すなわち、パッチが置換されるものとしてタグ付けされているか否か）を検査する。そうである場合、ステップ770に進む。そうでない場合、“置換”フラグを1に設定し、“除去”フラグを-1に設定する。テクスチャの間の相関が低い場合（例えば、閾値1＜MSE）、ステップ770に進む。
【００４７】
ステップ775において、テクスチャのパッチに対応する更なるインスタンスが存在するか否かを検査する。そうである場合、制御はステップ720に戻される。そうでない場合、パッチを使用した全てのインスタンスが終了した場合、ステップ780において、“置換”フラグが1にであるか否かを検査する。そうである場合、パッチは、パターンのテクスチャとインスタンスのテクスチャとの間の差分で置換される（785）。そうでない場合、制御は終了ステップ799に渡される。
【００４８】
除去されるとしてタグ付けされたパッチについて２つの別の動作が存在し得る。
【００４９】
(1)テクスチャのパッチはテクスチャ画像から物理的に除去され、テクスチャ座標が更新される。従って、小さいテクスチャ画像を生じる。テクスチャ画像からいくつかの領域を除去することにより、テクスチャ画像のサイズが低減可能になるため、テクスチャ画像は効率的に圧縮可能になる。
【００５０】
(2)テクスチャのパッチの内容が空になる。例えば、パッチの各画素が特定の色の値（例えば、黒又は灰色）に設定される。
【００５１】
個々のパッチが処理された後に、例えば、図８に示す方法800のように、インスタンスのテクスチャが符号化される必要があるか否かを判断することができる。パッチが除去又は置換された場合、対応するテクスチャ座標は、パターンのテクスチャのパッチの値に更新される。
【００５２】
インスタンスの全てのテクスチャ座標がパターンと同一である場合（810）、ステップ840において、モードフラグを‘00’（モード1）に設定し、パターンとインスタンスとがテクスチャを共有することを示す。いくつかのパッチが差分と置換された場合（820）、ステップ830において、モードフラグを‘10’（モード3）に設定する。そうでない場合、ステップ835において、モードフラグを‘01’（モード2及び4）に設定する。ステップ850において、全てのインスタンスが処理されたか否かを検査する。ステップ860において、いずれかのパッチが1に設定された“除去”フラグを有するか否かを検査する。そうである場合、パッチはテクスチャ画像において再配置され、全体の3Dモデルのテクスチャ座標が更新される（870）。モードフラグは、ビットストリームで伝達され、テクスチャ座標は、モードフラグが‘00’でない場合に送信される（880）。モードを表すために異なるビット列が使用されてもよい点に留意すべきである。
【００５３】
図９は、インスタンスのテクスチャを復号化する例示的な方法900を示している。インスタンス毎に、ステップ910においてモードフラグを復号化する。この方法900は、モードフラグに従って進む（920）。
【００５４】
モードフラグが‘00’である場合、全体のインスタンスについてパターンのテクスチャを使用する（940）。
【００５５】
モードフラグが‘01’である場合、ステップ930においてテクスチャ座標を復号化し、ステップ935において、復号化されたテクスチャ座標に従ってテクスチャのパッチを見つける。
【００５６】
モードフラグが‘10’である場合、ステップ950においてテクスチャ座標を復号化し、ステップ955において、テクスチャ座標に従ってテクスチャ画像をコピーする。そして、ステップ960において、パターンからのテクスチャ画像を追加することにより、インスタンスのテクスチャを更新する。方法900はステップ999で終了する。
【００５７】
図１０Ａは、入力として使用される例示的なテクスチャ画像であり、図１０Ｂ及び１０Ｃは、例えば方法700及び800を使用して処理した後の例示的なテクスチャ画像である。図１０Ｂにおいて、除去されるものとしてタグ付けされたパッチは、灰色のブロックと置換される。図１０Ｃにおいて、除去されるものとしてタグ付けされたパッチは、テクスチャ画像から物理的に除去される。図１０Ｂから分かるように、除去されたテクスチャのパッチに対応する多くの灰色の領域がテクスチャ画像に存在する。図１０Ｃでは、パッチは再配置されており、すなわち、灰色のパッチが除去され、残りのテクスチャのパッチがまとめられ、かなり小さいテクスチャ画像を生じている。双方の場合に、圧縮される情報が少なくなり、従って、テクスチャ画像の圧縮効率を改善し得る。
【００５８】
表３には、本発明の原理について例示的なシンタックス及び意味が示されている。インスタンス毎に、そのテクスチャの圧縮モードと、必要な場合にはテクスチャ座標データとを示す。
【００５９】
【表３】
2015512072.tif 000005
compr_elem_insta_texture_headerはモードフラグである。この特有の意味は表４に示されている。“共有”モードは図９のモード‘00’に対応し、“no_pred”モードは図９のモード‘01’に対応し、“texture_residual”は図９のモード‘10’に対応する。
【００６０】
【表４】
2015512072.tif 000006
compr_elem_insta_texcoord_dataは、モードが“no_pred”又は“texture_residual”である場合に全ての頂点のテクスチャ座標を含む。モードが“共有”である場合には、これはヌルになるべきである。
【００６１】
図１１は、例示的な3Dモデル符号化器1100のブロック図を示している。一実施例では、方法700及び800は、符号化器1100で使用されてもよい。装置1100の入力は、3Dモデルと、3Dモードを符号化する品質パラメータと、他のメタデータとを含んでもよい。3Dモデルは、まず反復構造発見モジュール1100を通過する。反復構造発見モジュール1100は、パターン、インスタンス及び特有コンポーネントに関して3Dモデルを出力する。パターン符号化器1120は、パターンを圧縮するために使用され、特有コンポーネント符号化器1150は特有コンポーネントを符号化するために使用される。インスタンスについて、インスタンスのコンポーネント情報は、ユーザにより選択されたモードに基づいて符号化される。インスタンス情報グループモードが選択された場合、インスタンス情報は、グループ化インスタンス情報符号化器1140を使用して符号化される。そうでない場合、基本インスタンス情報符号化器1130を使用して符号化される。符号化されたコンポーネントは、反復構造検証器1160で更に検証される。符号化されたコンポーネントがその品質要件を満たさない場合、特有コンポーネント符号化器1150を使用して符号化される。パターン、インスタンス及び特有コンポーネントのビットストリームは、ビットストリーム組み立て器1170において組み立てられる。
【００６２】
図１２は、例示的な3Dモデル復号化器1200のブロック図を示している。一実施例では、方法900は、復号化器1200で使用されてもよい。装置1200の入力は、3Dモデルのビットストリーム（例えば、方法700及び800により生成されたビットストリーム）を含んでもよい。圧縮されたビットストリームにおけるパターンに関する情報は、パターン復号化器1220により復号化される。特有コンポーネントに関する情報は、特有コンポーネント復号化器1250により復号化される。インスタンス情報の復号化も、ユーザにより選択されたモードに依存する。インスタンス情報グループモードが選択された場合、インスタンス情報は、グループ化インスタンス情報復号化器1240を使用して復号化される。そうでない場合、基本インスタンス情報復号化器1230を使用して復号化される。復号化されたパターン、インスタンス情報及び特有コンポーネントは、モデル再現モジュール1260において出力の復号化された3Dモデルを生成するために再現される。
【００６３】
次に図１３を参照すると、前述の特徴及び原理が適用され得るデータ送信システム又は装置1300が示されている。例えば、データ送信システム又は装置1300は、様々な媒体（例えば、衛星、ケーブル、電話回線又は地上波放送等）のうちいずれかを使用して信号を送信するヘッドエンド又は送信システムでもよい。更に又は或いは、データ送信システム又は装置1300は、例えば記憶するための信号を提供するために使用されてもよい。送信は、インターネット又は他のネットワークで提供されてもよい。データ送信システム又は装置1300は、例えばビデオコンテンツ又は他のコンテンツ（例えば、3Dモデル等）を生成して配信することができる。
【００６４】
データ送信システム又は装置1300は、プロセッサ1301から処理されたデータ及び他の情報を受信する。１つの実装では、プロセッサ1301は、“パターン・インスタンス（pattern-instance）”の表現を生成するために、3Dモデルの幾何学的データを処理する。プロセッサ1301はまた、例えばパターンID及び変換を示すメタデータを1300に提供してもよい。
【００６５】
データ送信システム又は装置1300は、符号化器1302と、符号化された信号を送信可能な送信機1304とを含む。符号化器1302は、プロセッサ1301からデータ情報を受信する。符号化器1302は、符号化された信号を生成する。
【００６６】
符号化器1302は、例えば、記憶又は送信のために、様々な情報を受信し、構造化されたフォーマットに組み立てるアセンブリユニットを含むサブモジュールを含んでもよい。例えば、様々な情報は、符号化されたビデオ又は符号化されていないビデオと、符号化された要素又は符号化されていない要素（例えば、サブストリーム長のインジケータ及びシンタックス要素等）を含んでもよい。或る実装では、符号化器1302は、プロセッサ1031を含み、従ってプロセッサ1301の動作を実行する。
【００６７】
送信機1304は、符号化器1302から符号化された信号を受信し、符号化された信号を１つ以上の出力信号で送信する。例えば、送信機1304は、符号化された画像及び／又はそれに関する情報を表す１つ以上のビットストリームを有する番組信号を送信するように適合されてもよい。典型的な送信機は、例えば、誤り訂正符号化の提供、信号におけるデータのインターリーブ、信号のエネルギーのランダム化、及び変調器1306を使用した１つ以上のキャリアへの信号の変調のうち１つ以上のような機能を実行する。送信機1304は、アンテナ（図示せず）を含んでもよく、インタフェース接続してもよい。更に、送信機1034の実装は、変調器1306に限定されなくてもよい。
【００６８】
データ送信システム又は装置1300は、記憶ユニット1308に通信可能に結合される。１つの実装では、記憶ユニット1308は、符号化器1302に結合され、符号化器1302からの符号化されたビットストリームを格納する。他の実装では、記憶ユニット1308は、送信機1304に結合され、送信機1304からのビットストリームを格納する。送信機1304からのビットストリームは、例えば、送信機1304により更に処理された１つ以上の符号化されたビットストリームを含んでもよい。異なる実装では、記憶ユニット1308は、標準のDVD、Blu-Rayディスク、ハードドライブ、又は他の記憶デバイスのうち１つ以上である。
【００６９】
次に図１４を参照すると、前述の特徴及び原理が適用され得るデータ受信システム又は装置1400が示されている。データ受信システム又は装置1400は、様々な媒体（例えば、記憶デバイス、衛星、ケーブル、電話回線又は地上波放送等）で信号を受信するように構成されてもよい。信号は、インターネット又は他のネットワークで受信されてもよい。
【００７０】
データ受信システム又は装置1400は、例えば、携帯電話、コンピュータ、セットトップボックス、テレビ、又は符号化されたビデオを受信し、例えば、表示（例えば、ユーザへの表示）、処理若しくは記憶のために、復号化されたビデオ信号を提供する他のデバイスでもよい。従って、データ受信システム又は装置1400は、例えば、テレビの画面、コンピュータモニタ、コンピュータ（記憶、処理又は表示のため）又は他の記憶、処理若しくは表示デバイスにその出力を提供してもよい。
【００７１】
データ受信システム又は装置1400は、データ情報を受信して処理可能である。データ情報は、例えば3Dモデルを含んでもよい。データ受信システム又は装置1400は、符号化された信号（例えば、この出願の実装で説明した信号等）を受信する受信機1402を含む。受信機1402は、例えば、3Dモデル及び／又はテクスチャ画像のうち１つ以上を提供する信号、又は図１２のデータ送信システム1200から出力された信号を受信してもよい。
【００７２】
受信機1402は、例えば、符号化された画像を表す複数のビットストリームを有する番組信号を受信するように適合されてもよい。典型的な受信機は、例えば、変調及び符号化されたデータ信号の受信、復調器1404を使用した１つ以上のキャリアからのデータ信号の復調、信号のエネルギーの逆ランダム化、信号におけるデータのデインターリーブ、信号の誤り訂正復号化のうち１つ以上のような機能を実行する。受信機1402は、アンテナ（図示せず）を含んでもよく、インタフェース接続してもよい。受信機1402の実装は復調器1404に限定されない。
【００７３】
データ受信システム又は装置1400は、復号化器1406を含む。受信機1402は、受信信号を復号化器1406に提供する。受信機1402により復号化器1406に提供された信号は、１つ以上の符号化されたビットストリームを含んでもよい。復号化器1406は、復号化された信号（例えば、ビデオ情報を含む復号化されたビデオ信号等）を出力する。復号化器1406は、例えば図１２で説明した復号化器1200でもよい。
【００７４】
データ受信システム又は装置1400はまた、記憶ユニット1407に通信可能に結合される。１つの実装では、記憶ユニット1407は、受信機1402に結合され、受信機1042は記憶ユニット1407からビットストリームにアクセスする。他の実装では、記憶ユニット1407は、復号化器1406に結合され、復号化器1406は記憶ユニット1407からビットストリームにアクセスする。異なる実装では、記憶ユニット1407からアクセスされるビットストリームは、１つ以上の符号化されたビットストリームを含む。異なる実装では、記憶ユニット1407は、標準のDVD、Blue-Rayディスク、ハードドライブ又は他の記憶デバイスのうち１つ以上である。
【００７５】
１つの実装では、復号化器1406からの出力データは、プロセッサ1408に提供される。１つの実装では、プロセッサ1408は、3Dモデルの再現を実行するように構成されたプロセッサである。或る実装では、復号化器1406は、プロセッサ1408を含み、従って、プロセッサ1408の動作を実行する。他の実装では、プロセッサ1408は、例えばセットトップボックス又はテレビのような下流のデバイスの一部である。
【００７６】
従って、特定の特徴及び態様を有する１つ以上の実装を提供する。特に、3Dモデルの符号化及び復号化に関する複数の実装を提供する。3Dモデルの符号化及び復号化は、例えば、ビデオゲーム、仮想現実及び科学的可視化のような様々なアプリケーションを可能にし得る。しかし、これらの実装及び更なるアプリケーションの変更も考えられ、この開示の範囲内である。記載の実装の特徴及び態様は、他の実装に適合されてもよい。
【００７７】
この出願に記載の実装及び特徴のいくつかは、MPEG  3DGC標準及びその拡張に関して使用されてもよい。更に、これらの実装及び特徴は、他の標準（既存のもの又は将来的なもの）に関して使用されてもよく、標準に関与しない状況で使用されてもよい。
【００７８】
ここに記載の実装は、例えば、方法若しくは処理、装置、ソフトウェアプログラム、データストリーム又は信号で実装されてもよい。単一の実装形式に関してのみ説明していたとしても（例えば、方法のみとして説明していたとしても）、説明した特徴の実装は、他の形式（例えば、装置又はプログラム）にも実装されてもよい。装置は、例えば、適切なハードウェア、ソフトウェア及びファームウェアに実装されてもよい。方法は、例えば、プロセッサのような装置に実装されてもよい。プロセッサは、例えば、コンピュータ、マイクロプロセッサ、集積回路又はプログラム可能論理デバイスを含む処理デバイスを一般的に示す。プロセッサはまた、例えば、コンピュータ、携帯電話、ポータブル／パーソナルデジタルアシスタント（PDA）及びエンドユーザ間の情報の通信を容易にする他のデバイスのような通信デバイスを含む。
【００７９】
本発明の原理の“一実施例”若しくは“実施例”又は“１つの実装”又は“実装”とその変形への言及は、実施例に関して説明した特定の機能、構造、特徴等が本発明の原理の少なくとも１つの実施例に含まれることを意味する。従って、“一実施例では”若しくは“実施例では”又は“１つの実装では”若しくは“実装では”という用語と他の変形が現れることは、必ずしも同じ実施例を示しているとは限らない。
【００８０】
更に、この出願又は特許請求の範囲は、様々な情報の“判断”を示すことがある。情報の判断は、例えば、情報の推定、情報の計算、情報の予測、又はメモリからの情報の取得のうち１つ以上を含んでもよい。
【００８１】
更に、この出願又は特許請求の範囲は、様々な情報への“アクセス”を示すことがある。情報のアクセスは、例えば、情報の受信、（例えばメモリからの）情報の取得、情報の格納、情報の処理、情報の送信、情報の移動、情報のコピー、情報の削除、情報の計算、情報の判断、情報の予測、又は情報の推定のうち１つ以上を含んでもよい。
【００８２】
更に、この出願又は特許請求の範囲は、様々な情報の“受信”を示すことがある。受信は、“アクセス”と同様に、広い意味になることを意図する。情報の受信は、例えば、情報のアクセス又は（例えばメモリからの）情報の取得のうち１つ以上を含んでもよい。更に、“受信”は、典型的には、例えば、情報の格納、情報の処理、情報の送信、情報の移動、情報のコピー、情報の削除、情報の計算、情報の判断、情報の予測、又は情報の推定のような動作中に何らかの方法で関与する。
【００８３】
当業者に明らかになるように、実装は、例えば格納又は送信され得る情報を伝達するようにフォーマットされた様々な信号を生成してもよい。情報は、例えば、方法を実行する命令又は記載の実装のうち１つにより生成されたデータを含んでもよい。例えば、信号は、記載の実施例のビットストリームを伝達するようにフォーマットされてもよい。このような信号は、例えば、電磁波（例えば、スペクトルの無線周波数部分を使用するもの）又はベースバンド信号としてフォーマットされてもよい。フォーマットは、例えば、データストリームを符号化し、符号化されたデータストリームでキャリアを変調することを含んでもよい。信号が伝達する情報は、例えば、アナログ又はデジタル情報でもよい。信号は、既知のように、様々な異なる有線又は無線回線で送信されてもよい。信号は、プロセッサ読み取り可能媒体に格納されてもよい。
【図１】
2015512072.tif 000007
【図２Ａ】
2015512072.tif 000008
【図２Ｂ】
2015512072.tif 000009
【図３Ａ】
2015512072.tif 000010
【図３Ｂ】
2015512072.tif 000011
【図４】
2015512072.tif 000012
【図５Ａ】
2015512072.tif 000013
【図５Ｂ】
2015512072.tif 000014
【図５Ｃ】
2015512072.tif 000015
【図６Ａ】
2015512072.tif 000016
【図６Ｂ】
2015512072.tif 000017
【図７】
2015512072.tif 000018
【図８】
2015512072.tif 000019
【図９】
2015512072.tif 000020
【図１０Ａ】
2015512072.tif 000021
【図１０Ｂ】
2015512072.tif 000022
【図１０Ｃ】
2015512072.tif 000023
【図１１】
2015512072.tif 000024
【図１２】
2015512072.tif 000025
【図１３】
2015512072.tif 000026
【図１４】
2015512072.tif 000027
【国際調査報告】
2015512072.tif 000028
2015512072.tif 000029