(57)【特許請求の範囲】
【請求項１】
３Ｄモデルを表すビットストリームを生成する方法であって、
構造に関連付けられたパターンのインスタンスに関する情報にアクセスするステップであって、前記情報は前記パターンに関連付けられたパターン識別子及びパターン変換情報を含む、アクセスするステップと、
前記インスタンスを表すビットストリームを生成し、前記パターン識別子及び前記パターン変換情報が第１のフォーマット及び第２のフォーマットのうちの一方で前記ビットストリーム中に配設されることを含む、生成するステップと、
を含み、
複数のパターン及びパターン情報を含み、
前記第１のフォーマットは、前記パターン識別子の各々及び関連する変換情報を前記ビットストリーム中に共にパックすることを含み、前記第２のフォーマットは、複数のパターン識別子を前記ビットストリーム中に共にパックし、情報タイプに従って前記変換情報を前記ビットストリーム中に共にパックすることを含む、
方法。
【請求項２】
前記パターンの各々に関連する特性情報にアクセスするステップをさらに有し、
前記第１のフォーマットは、各パターン識別子をその変換情報及び特性情報と前記ビットストリーム中に共にパックすることを含み、前記第２のフォーマットは、複数のパターン識別子を前記ビットストリーム中に共にパックし、情報タイプに従って前記変換情報及び特性情報を前記ビットストリーム中に共にパックすることを含む、請求項１に記載の方法。
【請求項３】
３Ｄモデルを表すビットストリームを生成する装置であって、
構造に関連付けられたパターンのインスタンスに関する情報にアクセスする手段であって、前記情報は前記パターンに関連付けられたパターン識別子及びパターン変換情報を含む、アクセスする手段と、
前記インスタンスを表すビットストリームを生成し、前記パターン識別子及び前記パターン変換情報が第１のフォーマット及び第２のフォーマットのうちの一方で前記ビットストリーム内に配設されることを含む、生成する手段と、
を含み、
複数のパターン及びパターン情報を含み、
前記第１のフォーマットは、前記パターン識別子の各々及び関連する変換情報を前記ビットストリーム中に共にパックすることを含み、前記第２のフォーマットは、複数のパターン識別子を前記ビットストリーム中に共にパックし、情報タイプに従って前記変換情報を前記ビットストリーム中に共にパックすることを含む、
装置。
【請求項４】
前記アクセスする手段は前記パターンの各々に関連する特性情報にアクセスし、
前記第１のフォーマットは、各パターン識別子をその変換情報及び特性情報と前記ビットストリーム中に共にパックすることを含み、前記第２のフォーマットは、複数のパターン識別子を前記ビットストリーム中に共にパックし、情報タイプに従って前記変換情報及び特性情報を前記ビットストリーム中に共にパックすることを含む、請求項３に記載の装置。
【請求項５】
３Ｄモデルを表すビットストリームを処理する方法であって、
前記ビットストリームが構造に関連付けられたパターンに関する情報を含むかどうかを判定するステップであって、前記情報は、第１のフォーマット又は第２のフォーマットの、前記パターンに関連付けられたパターン識別子及び変換情報を含む、判定するステップと、
前記判定に応じて、前記パターンに関連付けられた前記パターン識別子及び前記変換情報にアクセスするステップと、
前記パターン識別子及び前記変換情報を復号して３Ｄモデル・データを生成するステップと、
を含み、
前記ビットストリームは複数のパターンに関する情報を含み、
前記第１のフォーマットは、前記パターン識別子の各々及び関連する変換情報を前記ビットストリーム中に共にパックすることを含み、前記第２のフォーマットは、複数のパターン識別子を前記ビットストリーム中に共にパックし、情報タイプに従って前記変換情報を前記ビットストリーム中に共にパックすることを含む、
方法。
【請求項６】
前記パターンの各々に関連する特性情報にアクセスするステップをさらに有し、
前記第１のフォーマットは、前記パターン識別子の各々及び関連する変換情報及び特性情報を前記ビットストリーム中に共にパックすることを含み、前記第２のフォーマットは、複数のパターン識別子を前記ビットストリーム中に共にパックし、情報タイプに従って前記変換情報及び特性情報を前記ビットストリーム中に共にパックすることを含む、請求項５に記載の方法。
【請求項７】
３Ｄモデルを表すビットストリームを処理する装置であって、
前記ビットストリームが構造に関連付けられたパターンに関する情報を含むかどうかを判定する手段であって、前記情報は、第１のフォーマット又は第２のフォーマットの、前記パターンに関連付けられたパターン識別子及び変換情報を含む、判定する手段と、
前記判定に応じて、前記パターンに関連付けられた前記パターン識別子及び前記変換情報にアクセスする手段と、
前記パターン識別子及び前記変換情報を復号して３Ｄモデル・データを生成する手段と、
を含み、
前記ビットストリームは複数のパターンに関する情報を含み、
前記第１のフォーマットは、前記パターン識別子の各々及び関連する変換情報を前記ビットストリーム中に共にパックすることを含み、前記第２のフォーマットは、複数のパターン識別子を前記ビットストリーム中に共にパックし、情報タイプに従って前記変換情報を前記ビットストリーム中に共にパックすることを含む、
装置。
【請求項８】
前記アクセスする手段は前記パターンの各々に関連する特性情報にアクセスし、
前記第１のフォーマットは、前記パターン識別子の各々及び関連する変換情報及び特性情報を前記ビットストリーム中に共にパックすることを含み、前記第２のフォーマットは、複数のパターン識別子を前記ビットストリーム中に共にパックし、情報タイプに従って前記変換情報及び特性情報を前記ビットストリーム中に共にパックすることを含む、請求項７に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３Ｄモデル圧縮アルゴリズムに基づく反復構造発見のビットストリーム・シンタックス及びセマンティクス、３Ｄモデルを表すビットストリームを生成する方法及び装置、並びにこれを処理する方法及び装置に関する。
【背景技術】
【０００２】
実際の適用例では、多くの３Ｄモデルは多数の接続された構成要素からなる。さらにこれらの多接続３Ｄモデルは、図に示されるように、通常、様々な変換における多くの反復構造を含む。この種の３Ｄモデルのための効率的な圧縮方法は、反復構造内に存在する冗長性を抽出できるものでなければならない。
【０００３】
本発明の所有者は、K.Cai、Y.JIN、及びA.Chenによる「Efficient  Compression  Schime  for  Large  3D  Engineering  Models」という名称のＰＣＴ出願（WO2010149492）も共有しており、かかる出願は、多くの小型から中型サイズの接続された構成要素からなり、様々な位置、スケール、及び向きで反復する形状特徴を有する、３Ｄモデルのための圧縮方法を教示している。その教示は参照により本明細書に具体的に組み込まれている。この方法は、様々な位置、向き、及びスケーリング係数で反復する構造を発見する。その後３Ｄモデルは「パターン・インスタンス」表現に編成される。パターンとは、対応する反復構造を表現する形状である。反復構造に属する接続された構成要素は、対応するパターンのインスタンスと呼ばれ、それらの変換、すなわち、パターンに関係する位置、向き、及び可能スケーリング係数によって表される。インスタンスの向きは、デカルト座標系における（ｘ０，ｙ０，ｚ０）及び（ｘ１，ｙ１，ｚ１）、又は球面座標系における（アルファ，ベータ，ガンマ）によって表される、２本の直交軸によって表される。
【０００４】
本発明の所有者は、圧縮インスタンス変換データに関する２つのモードを教示する、K.Cai、W.Jiang、及びJ.Tianによる「Bitstream  Syntax  and  Semantics  of  Repetitive  Structure  Discovery  Based  3D  Model  Compression  Algorithm」という名称のＰＣＴ出願（PCT/CN2011/076991）も共有している。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、法線（normal）、カラー、及びテクスチャ座標などの３Ｄモデル・プロパティを扱うことが可能であり、その変換が反転変換（reflection  transformation）を含むインスタンスを圧縮することが可能な方法及び装置を提供することが求められている。
【課題を解決するための手段】
【０００６】
したがって本原理は、通常のカラー及びテクスチャ座標などの３Ｄモデル・プロパティを圧縮するため、並びに、その変換が反転変換を含むインスタンスを圧縮し、この情報を含むビットストリームを生成するために使用可能な、方法及び装置を提供する。
【０００７】
本原理は、いくつかの構造に関連付けられたパターンのインスタンスに関する情報にアクセスすることであり、情報はそれぞれのパターンに関連付けられたパターン識別子及び変換情報を含む、アクセスすること、並びに、以下で説明するように、第１のフォーマット及び第２のフォーマットのうちの１つのビットストリーム内に配設された、パターン識別子及びパターン変換データを含む、インスタンスを表すビットストリームを生成することを含む、３Ｄモデルを表すビットストリームを生成するための方法を提供する。本原理は、これらのステップを実行するための装置も提供する。ビットストリームは、複数のパターンに関連付けられた情報と、第１のフォーマット及び第２のフォーマットのうちの１つの複数のパターンに関連付けられたそれぞれの情報とを含むことも可能である。
【０００８】
本原理は、ビットストリームが構造に関連付けられたパターンのインスタンスに関する情報を含むかどうかを判定することであって、情報は、以下で説明するように第１のフォーマット又は第２のフォーマットの、パターンに関連付けられたパターン識別子及び変換情報を含む、判定すること、判定ステップに応答して、パターンに関連付けられたパターン識別子及び変換情報にアクセスすること、及び、３Ｄモデル・データを生成するためにパターン識別子及び変換情報を復号することを含む、３Ｄモデルを表すビットストリームを処理するための方法も提供する。本原理は、前記ステップを実行するための装置も提供する。ビットストリームは、複数のパターンに関連付けられた情報と、第１のフォーマット及び第２のフォーマットのうちの１つの複数のパターンに関連付けられたそれぞれの情報とを含むことも可能である。
【０００９】
本原理は、前述の方法に従ってビットストリームを生成又は処理するための命令を記憶した、コンピュータ読み取り可能記憶媒体も提供する。
【００１０】
本原理は、前述の方法に従って生成されたビットストリームを記憶した、コンピュータ読み取り可能記憶媒体も提供する。
【図面の簡単な説明】
【００１１】
【図１】多数の接続された構成要素及び反復構造を伴う例示の３Ｄモデルを示す図である。
【図２】反復構造発見ベースの圧縮アルゴリズムＡ３ＤＭＣに基づいて、ビットストリームの構造を決定するためのステップを含む、例示のプロセスを示す図である。
【図３】本原理に関する例示のエンコーダを示す図である。
【図４】本原理に関する例示のデコーダを示す図である。
【発明を実施するための形態】
【００１２】
反復構造の発見時には、形状のみがチェックされる。１インスタンスは、プロパティ・データを対応するパターンと共有するか、又はそれ自体のプロパティ・データを有することが可能である。インスタンスのプロパティは、パターンとプロパティを共有しない場合、別々に圧縮されることになる。
【００１３】
インスタンス変換は、反転部分、回転部分、並進（translation）部分、及び可能スケーリング部分の、４つの部分に分割することができる。４つの部分は別々に圧縮される。
【００１４】
すべてのパターンは、より多くのビットレート節約を達成するために、まとめて圧縮される。復号時、パターンは、インスタンスの復元前に互いに分離される必要がある。
【００１５】
図３及び図４は、本原理の態様を実装するのに適した例示のエンコーダ及びデコーダを示す。エンコーダ及びデコーダの詳細は、出願人の共有するＰＣＴ出願WO2010149492及びPCT/CN2011/076991で提供されており、その説明は、参照により本明細書に明示的に組み込まれている。当業者であれば理解されるように、こうした３Ｄレンダリングが必要とされる様々な実施形態に柔軟性を提供するために、コーデックはハードウェア、ソフトウェア、又はファームウェア、或いはこれらのモダリティの組み合わせで実装可能である。特定用途向け集積回路（ＡＳＩＣ）、プログラマブル・アレイ論理回路、ディスクリート半導体回路、及びプログラマブル・デジタル信号処理回路、とりわけ、一時的又は持続的なコンピュータ読み取り可能媒体は、すべて、本発明を実装するために使用可能である。これらはすべて、本発明の可能な実装の非限定的な例であり、当業者であれば、他の実施形態が実現可能であることを理解されよう。
【００１６】
２インスタンス圧縮モード
ビットストリームがすべてのインスタンス・データを埋め込むことを望む一方で、効率的であり、時にはビットストリーム・サイズ又は復号効率又は誤り耐性のいずれかが最も重要ないくつかの適用例に対処することも望む。
【００１７】
したがって本発明者等は、パターンの１インスタンスのデータ、すなわちそのパターンＩＤ（たとえば、第１のパターンには１、第２のパターンには２、というように、パターン圧縮データ・ストリーム内のパターンの実際の位置であるＩＤ）、その反転変換部分（Ｆ）、その並進変換部分（Ｔ）、その回転変換部分（Ｒ）、及びそのスケーリング変換部分（Ｓ）を、いかにしてビットストリーム内に入れるかについて、２つのオプションを提案する。どちらもそれら独自の長所及び短所を有する。
【００１８】
オプション（Ａ）基本インスタンス・データ・モード（ＩＤ、Ｆ、Ｔ、Ｒ、Ｓ、ＩＤ、Ｆ、Ｔ、Ｒ、Ｓ・・・）：このモードを使用すると、１インスタンスのパターンＩＤ、反転変換部分、並進変換部分、回転変換部分、及びスケーリング変換部分は、ビットストリーム内にまとめてパックされる。
長所：
・誤り耐性がある。デコーダは、いくつかのインスタンスの変換失敗から回復可能である。
【００１９】
・オンライン復号。これは、圧縮ビットストリームの実際の読み取り時に、インスタンスが１つずつ復号可能であることを意味する。圧縮ビットストリーム全体の読み取り完了を待つ必要はない。
【００２０】
・コーデック速度が速い。
【００２１】
・コーデックはバッファを必要としない。
短所：
・圧縮済みの３Ｄモデル・サイズが相対的に大きい。
【００２２】
オプション（Ｂ）グループ化インスタンス・データ・モード（ＩＤ、ＩＤ、Ｆ、Ｆ、Ｔ、Ｔ、Ｒ、Ｒ、Ｓ、Ｓ）：このモードを使用すると、情報は、情報タイプに基づいてグループ化される。すなわち、１インスタンスのパターンＩＤ、反転変換部分、並進変換部分、回転変換部分、及びスケーリング変換部分は、ビットストリーム内にまとめてパックされる。
長所：
・圧縮済みの３Ｄモデル・サイズが相対的に小さい。
短所：
・デコーダは、もはや誤り耐性がない。
【００２３】
・オフライン復号・これは、デコーダが、圧縮されたビットストリーム全体の読み取り後にのみ、復号を開始できることを意味する。
【００２４】
・コーデック速度が遅い。
【００２５】
・バッファが必要である。
【００２６】
現行のビットストリーム定義は、上記２つのオプションの両方を含むことになる。その後ユーザは、彼らのアプリケーションにより良く適合する方を選択することができる。特定の実装は、２つのインスタンス・データ・モードのうちの１つを実装することのみを選択することができる。その場合、ビットストリーム定義は適宜変更されるものとする。詳細については「ビットストリームのシンタックス及びセマンティクス」の項を参照されたい。
【００２７】
インスタンスは、オリジナルの構成要素と、パターン及びインスタンス変換から復元された構成要素との間の距離として定義される、より大きな復号誤りを有する可能性があるため、ビットストリームのいくつかのデータ・フィールドは、復号された３Ｄモデル品質を保証するために、圧縮されたインスタンス復号誤りを示すように定義される。インスタンスの復号誤りを圧縮するか否かは、たとえば品質要件に基づいている。
【００２８】
インスタンス変換の圧縮
以下に示されるように、インスタンス変換は、反転部分（Refle）、回転部分（Rotat）、並進部分（Transl）、及び可能スケーリング部分の、４つの部分に分割可能である。
【００２９】
【表１】
0005933742.tif 000002
反転部分は、W.Jiang、K.Cai、及びT.Luoによる「Method  and  Apparatus  for  Reflective  Symmetry  Based  3D  Model  Compression」という名称のＰＣＴ出願（出願番号を記入）に記載されるように、たとえば１ビット・フラグによって表すことが可能である。
【００３０】
回転部分は３×３マトリクスである。３列（又は行）の回転部分は単位直交ベクトルである。時には復号効率又は復号誤りのいずれかが最も重要である、いくつかの適用例に対処するために、本発明者等は、回転部分をいかにして圧縮するかについて２つのオプションを提案する。どちらもそれら独自の長所及び短所を有する。
【００３１】
オプション（Ａ）デカルト・モード。デカルト座標系において、W.Jiang、K.Cai、及びJ.Tianによる「Conditional  Error  Correction  in  Orientation  AX’sEncoding」という名称のＰＣＴ出願（PCT/CN2011/077277）に記載されるように、たとえば、回転部分は２本の直交軸（ｘ０，ｙ０，ｚ０）及び（ｘ１，ｙ１，ｚ１）によって表され、圧縮されることが可能である。
長所：
・コーデック速度が速い。
短所：
・復号済みの３Ｄモデルの精度が相対的に低い。
【００３２】
オプション（Ｂ）球面モード。このモードを使用すると、回転部分は、たとえば「Computing  Euler  Angles  from  a  Rotation  Matrix」Greg  Slaubaugh,1999,Reportsによって、オイラー角（アルファ，ベータ，ガンマ）に変換され、W.Jiang、K.Cai、及びJ.Tianによる「Orientation  Encoding」という名称のＰＣＴ出願（PCT/CN2011/077271）に記載されるように、圧縮されることが可能である。
長所：
・復号済みの３Ｄモデルがより正確である。
短所：
コーデック速度が相対的に遅い。
【００３３】
現行のビットストリーム定義は、上記２つのオプションの両方を含むことになる。その後ユーザは、彼らのアプリケーションにより良く適合する方を選択することができる。特定の実装は、２つのインスタンス回転圧縮モードのうちの１つを実装することのみを選択することができる。その場合、ビットストリーム定義は適宜変更されるものとする。詳細については「ビットストリームのシンタックス及びセマンティクス」の項を参照されたい。
【００３４】
並進部分は、ベクトル（ｘ，ｙ，ｚ）（擬似並進ベクトル）によって表される。グループ化インスタンス変換モードを使用すると、すべての擬似インスタンス並進ベクトルは、
たとえば、W.Jiang、K.Cai、及びZ.Chenによる「A  Model  Adaptive  Entropy  Coding  for  Octree  Compression」という名称のＰＣＴ出願（PCT/CN2011/077279）に記載された、オクトリー・データ構造内のすべての擬似インスタンス並進ベクトルの境界ボックスを再帰的に細分する方法を使用して、オクトリー（octree）（ＯＴ）分解（decomposition）ベースの圧縮アルゴリズムによって圧縮される。本発明者等は、各オクトリー・ノード細分を、１ビット・フラグを使用して子ノードが非空であるかどうかを示す、８ビット長の占有コードによって表す。オクトリーを記述する占有コード・シーケンスは、オクトリーの幅優先トラバース（breadth  first  traversing）によって生成される。本発明者等は、占有コード・シーケンスをいくつかの間隔に分割し、それらを異なる確率モデルで圧縮することによって、占有コード・シーケンスを圧縮する。インスタンスは、重複並進ベクトルと呼ばれる極端に近い擬似並進ベクトルを有する可能性があるため、ビットストリームのいくつかのデータ・フィールドは、重複並進ベクトルを示すために定義される。
【００３５】
スケーリング部分は、たとえばM.Isenburg等による「Lossless  Compression  of  Predicted  Floating-Point  Geometry」、Computer-Aided  Design,Volume  37,Issue  8、８６９〜８７７ページ、２００５年７月によって、インスタンスの均一スケーリングＳによって表され、浮動小数点数について無損失圧縮アルゴリズムによって圧縮される。
【００３６】
インスタンス・プロパティの圧縮
実際の適用例では、形状に加えて、３Ｄモードは通常、法線、カラー、及びテクスチャ座標などの様々なプロパティを有する。インスタンスが同じパターンのプロパティを有することを必要とすることで、反復構造が発見され得る回数を制限し、Ａ３ＤＭＣの圧縮率を下げることになる。したがって本発明者等は、反復構造の発見時に形状のみをチェックし、インスタンスは、対応するパターンのプロパティによって異なるプロパティを有することができる。
【００３７】
基本インスタンス・データ・モードが使用される場合、いかにしてビットストリームからインスタンスのプロパティを取得するかを示すために、１つのデータ・フィールドが定義される。
【００３８】
・ケースＡ：インスタンスはパターン・プロパティ・データを共有し、データ・フィールドはそのプロパティを表す必要がない。
【００３９】
・ケースＢ：インスタンスはそれ独自のプロパティを有し、そのプロパティをビットストリーム内に表すために別々のデータ・フィールドが必要である。
【００４０】
１インスタンスのプロパティ・データ（Ｐ）は、インスタンスの他のデータに従い、すなわち（ＩＤ、Ｆ、Ｔ、Ｒ、Ｓ、Ｐ、ＩＤ、Ｆ、Ｔ、Ｒ、Ｓ、Ｐ・・・）である。グループ化インスタンス・データ・モードが使用される場合、すべてのインスタンスは、パターン・プロパティ・データを共有するか、それら独自のプロパティ・データを有するものとする。ビットストリームのインスタンス・データ部分は（ＩＤ、ＩＤ、Ｆ、Ｆ、Ｔ、Ｔ、Ｒ、Ｒ、Ｓ、Ｓ、Ｐ、Ｐ）のようになる。本発明者等は、ISO/IEC  14496-16の同じ３Ｄモデル・プロパティ・データ・フィールド定義を使用する。
【００４１】
圧縮済みビットストリームの一般構造
本発明者らの反復構造発見ベース圧縮アルゴリズム、Ａ３ＤＭＣの圧縮済みビットストリームの一般構造の分解は、図２に示された通りである。ビットストリームは、ヘッダ・バッファ（A3DMC_stream_header）で始まり、オリジナル・モデル内に少なくとも１つの反復構造が存在するか否かの情報、形状を圧縮するために使用される３Ｄモデル圧縮方法、すべての３Ｄオブジェクト（パターン及び必要であれば他の部分）の接続性及びプロパティ、このビットストリーム内で「グループ化インスタンス変換モード」又は「基本インスタンス変換モード」が使用されるか否かの情報、反復的でないオリジナル・モデルの何らかの部分（ユニーク部分と呼ぶ）が存在するか否かの情報、インスタンス復号誤りが補償されるかどうかの情報、インスタンスが有し得るプロパティのタイプの情報など、圧縮済みストリームを復号するためのすべての必要な情報を含む。
【００４２】
オリジナル・モデル内に反復構造（repeat_struc_bit!=1）を含まない場合、ビットストリームの左部分は、A3DMC_stream_header内に示された３Ｄモデル圧縮方法を使用する圧縮済み入力３Ｄモデルである。含む場合、ビットストリーム内の次の部分は、すべてのパターンの圧縮済み結果である。このビットストリーム内でいずれのインスタンス変換パッキング・モードが選択されるかに応じて、compr_insta_grouped_data又はcompr_insta_elementary_dataのいずれかが、ビットストリーム内の次の部分である。オリジナル３Ｄモデル内にユニーク部分が存在する場合、compr_uni_part_dataが付属される。存在しない場合、ビットストリームは終了する。
【００４３】
ビットストリーム・シンタックス及びセマンティクス
ＳＣ３ＤＭＣ仕様ですでに使用されているシンタックス関数、カテゴリ、及び記述子に加えて、本発明者等は、以下の２つも使用することになる。
【００４４】
ｆ（ｎ）：各シンボルについて（左から右へ記載された）ｎ個のビットを用いる、固定長符号化ビット。ｎは各シンボルの符号長さに依存する。
【００４５】
ｅｃ（ｖ）：場合によっては構成シンボルを含む、エントロピー符号化（たとえば算術符号化）シンタックス要素。
【００４６】
ビットストリーム・シンタックス及びセマンティクス
A3DMC_streamクラス
シンタックス
【表２】
0005933742.tif 000003
セマンティクス
A3DMC_stream_header：ヘッダ・バッファを含む。
【００４７】
A3DMC_steam_data：データ・バッファを含む。
【００４８】
A3DMC_stream_headerクラス
シンタックス
【表３】
0005933742.tif 000004
セマンティクス
repeat_struc_bit：３Ｄモデル内に一定量を上回る反復構造が存在するか否かを示す、１ビットの符号なし整数。０は反復構造なし、１は反復構造。
【００４９】
3d_model_compr_mode：パターン、ユニーク部分、及び、反復構造を含まない場合のオリジナル３Ｄモデル自体を圧縮するために使用される、３Ｄモデル圧縮方法を示す、２ビットの符号なし整数。
【表４】
0005933742.tif 000005
ＱＰ：品質パラメータを示す５ビットの符号なし整数。ＱＰの最小値は３であり最大値は３１である。
【００５０】
pattern_num：２５５未満の場合のすべてのパターンの数を示す、８ビットの符号なし整数。pattern_numの最小値は１である。
【００５１】
pattern_num_2：２５５以上の場合のすべてのパターンの数を示す、１６ビットの符号なし整数。この場合、合計パターン数は（pattern_num_2+255）である。
【００５２】
instance_num：６５５３５未満の場合のすべてのインスタンスの数を示す、１６ビットの符号なし整数。instance_numの最小値は１である。
【００５３】
instance_num_2：６５５３５以上の場合のすべてのインスタンスの数を示す、３２ビットの符号なし整数。この場合、合計インスタンス数は（instance_num_2+65535）である。
【００５４】
insta_trans_elem_bit：ビットストリーム内で「グループ化インスタンス変換モード」又は「基本インスタンス変換モード」のいずれが使用されるかを示す、１ビットの符号なし整数。０は「グループ化インスタンス変換モード」、１は「基本インスタンス変換モード」。
【００５５】
insta_rotat_mode_bit：インスタンス回転変換の符号化モードを示す、１ビットの符号なし整数。０は球面モード、１はデカルト・モード。
【００５６】
use_scaling_bit：インスタンス変換がスケーリング係数を含むかどうかを示す１ビットの符号なし整数。１はインスタンス変換にスケーリング係数が含まれ、０は含まれない。ほとんどのインスタンスのスケーリング係数が１．０に等しい場合、インスタンス変換はスケーリング係数を含まない。そこで、すべてのインスタンスは対応するパターンと同じサイズを有さなければならない。
【００５７】
uni_part_bit：オリジナル３Ｄモデル内にユニーク部分が存在するかどうかを示す、１ビットの符号なし整数。０はユニーク部分が存在しないことを意味し、１はユニーク部分が存在することを示す。uni_part_bitが０に等しい場合、パターン・インスタンス圧縮データ後にビットストリームの端部が右に達していることも意味する。
【００５８】
error_compensate_enable_bit：ビットストリーム内の何らかのインスタンスに関する圧縮済み復号誤りのデータ・フィールドが存在するかどうかを示す、１ビットの符号なし整数。０はビットストリーム内のインスタンスの圧縮済み復号誤りのデータ・フィールドが存在しないことを意味し、１はビットストリーム内の何らかのインスタンスの圧縮済み復号誤りのデータ・フィールドが存在することを意味する。
【００５９】
property_enable_bits：各ビットが、対応するプロパティ（たとえば法線、カラー、テクスチャ座標）が符号化されるかどうかを示す、４ビット・フラグ。０は対応するプロパティが符号化されないことを意味し、１は符号化されることを意味する。ビットとプロパティとの間の関係は、以下の表に示される。
【００６０】
【表５】
0005933742.tif 000006
A3DMC_stream_dataクラス
シンタックス
【表６】
0005933742.tif 000007
セマンティクス
compr_repeat_struc_data：反復構造を含む圧縮済み３Ｄモデルを含む。
【００６１】
compr_3d_model_data：反復構造を含まず、3d_model_compr_modeによって示される圧縮方法によって符号化された、圧縮済み３Ｄモデルを含む。
【００６２】
compr_repeat_struc_dataクラス
シンタックス
【表７】
0005933742.tif 000008
セマンティクス
compr_pattern_data：3d_model_compr_modeによって示される圧縮方法によって符号化された、すべてのパターンの圧縮済み形状、接続性、及びプロパティを含む。
【００６３】
compr_insta_elementary_data：「基本インスタンス変換モード」を使用するすべてのパターン・インスタンスについての、圧縮済みインスタンス変換データを含む。バイトが位置合わせされるように圧縮される。
【００６４】
compr_insta_grouped_data：「グループ化インスタンス変換モード」を使用するすべてのパターン・インスタンスについての、圧縮済みインスタンス変換データを含む。バイトが位置合わせされるように圧縮される。
【００６５】
compr_uni_part_data：3d_model_compr_modeによって示される圧縮方法によって符号化された、圧縮済みユニーク部分データを含む。
【００６６】
compr_insta_elementary_dataクラス
シンタックス
【表８】
0005933742.tif 000009
【表９】
0005933742.tif 000010
セマンティクス
insta_tranl_bbox：インスタンス並進情報を圧縮する場合に量子化が使用できるような、並進ベクトル・データの最小値及び最大値を含む。
【００６７】
compr_elem_insta_patternID：ｉ番目インスタンスの圧縮済みパターンＩＤを含む。
【００６８】
elem_insta_share_pattern_property_bit：ｉ番目インスタンスが対応するパターンとプロパティを共有するか否かを示す、１ビットの符号なし整数。０は、ｉ番目インスタンスが対応するパターンとプロパティを共有せず、そのプロパティを圧縮する必要があることを意味する。１は、ｉ番目インスタンスが対応するパターンとプロパティを共有することを意味する。
【００６９】
elem_insta_reflection_flag：ｉ番目インスタンスの変換が反転を含むかどうかを示す、１ビットの符号なし整数。０はｉ番目インスタンスの変換が反転を含まないことを意味し、１はｉ番目インスタンスの変換が反転を含むことを意味する。
【００７０】
compr_elem_insta_transl：ｉ番目インスタンスの圧縮済み並進ベクトルを含む。
【００７１】
compr_elem_insta_rotat_cartesian：デカルト・モードでｉ番目インスタンスの圧縮済み回転変換を含む。
【００７２】
compr_elem_insta_rotat_spherical：球面モードでｉ番目インスタンスの圧縮済み回転変換を含む。
【００７３】
compr_elem_insta_scaling：ｉ番目インスタンスの圧縮済みスケーリング係数を含む。
【００７４】
compr_elem_insta_normal_header：ｉ番目インスタンスの圧縮済み法線のヘッダを含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【００７５】
compr_elem_insta_normal_data：ｉ番目インスタンスの圧縮済み法線を含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【００７６】
compr_elem_insta_color_header：ｉ番目インスタンスの圧縮済みカラーのヘッダを含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【００７７】
compr_elem_insta_color_data：ｉ番目インスタンスの圧縮済みカラーを含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【００７８】
compr_elem_insta_texcoord_header：ｉ番目インスタンスの圧縮済みテクスチャ座標のヘッダを含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【００７９】
compr_elem_insta_texcoord_data：ｉ番目インスタンスの圧縮済みテクスチャ座標を含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【００８０】
elem_insta_error_compensate_flag：ビットストリームの次の部分がｉ番目インスタンスの圧縮済み復号誤りであるかどうかを示す、１ビットの符号なし整数。０は、ビットストリームの次の部分がｉ番目インスタンスの圧縮済み復号誤りでないことを意味し、１は、ビットストリームの次の部分がｉ番目インスタンスの圧縮済み復号誤りであることを意味する。
【００８１】
compr_elem_insta_error_compen_header：ｉ番目インスタンスの圧縮済み復号誤りのヘッダを含む。
【００８２】
compr_elem_insta_error_compen_data：ｉ番目インスタンスの圧縮済み復号誤りを含む。
【００８３】
bit_num_insta_transl()：ＱＰに基づき、各擬似インスタンス並進ベクトルについてビット数を計算する。
【００８４】
compr_elem_insta_rotat_cartesianクラス
シンタックス
【表１０】
0005933742.tif 000011
セマンティクス
デカルト・モードのｉ番目インスタンスの回転変換は、２本の直交軸（ｘ０，ｙ０，ｚ０）及び（ｘ１，ｙ１，ｚ１）によって表される。
【００８５】
compr_elem_insta_rotat_x0：ｉ番目インスタンスの回転の圧縮済みｘ０を含む。
【００８６】
compr_elem_insta_rotat_y0：ｉ番目インスタンスの回転の圧縮済みｙ０を含む。
【００８７】
elem_insta_rotat_z0_sgn：ｘ０及びｙ０を使用してｚ０を計算するために必要なｚ０の符号を示す、１ビットの符号なし整数。０は「−」、１は「＋」である。
【００８８】
compr_ith_insta_orient_z0_res：不正確な可能性が高い計算済みｚ０の圧縮済み剰余を含む。
【００８９】
compr_elem_insta_rotat_w：ｘ０及びｙ０に依存して、ｘ１、ｙ１、又はｚ１であり得る、ｉ番目インスタンスの回転の圧縮済み第３座標ｗを含む。
【００９０】
elem_insta_rotat_sgn_v：ｘ０、ｙ０、ｚ０、及びｗを使用してｖを計算するために必要な、ｗに依存してｘ１又はｙ１であり得る、第５座標ｖの符号を示す、１ビットの符号なし整数。０は「−」、１は「＋」である。
【００９１】
compr_elem_insta_rotat_z1_res：不正確な可能性が高い計算済みｚ１の圧縮済み剰余を含む。
【００９２】
need_compensate_z0()：ｉ番目インスタンスの回転の計算済みｚ０が補償される必要があるか否かを判定する。ｉ番目インスタンスの回転の計算済みｚ０が補償される必要がある場合はtrueを、ｉ番目インスタンスの回転の計算済みｚ０が補償される必要がない場合はfalseを戻す。
【００９３】
need_compensate_z1()：ｉ番目インスタンスの回転の計算済みｚ１が補償される必要があるか否かを判定する。ｗがｚ１でなく、ｉ番目インスタンスの回転の計算済みｚ１が補償される必要がある場合は、trueを戻す。ｗがｚ１であるか、又は、ｉ番目インスタンスの回転の計算済みｚ１が補償される必要がない場合は、falseを戻す。
【００９４】
bit_num_rotat_cartesian()：ＱＰに基づき、デカルト座標系における各回転値についてビット数を計算する。
【００９５】
bit_num_rotat_res_cartesian()：ＱＰに基づき、デカルト座標系における各回転剰余値についてビット数を計算する。
【００９６】
compr_elem_insta_rotat_sphericalクラス
シンタックス
【表１１】
0005933742.tif 000012
セマンティクス
球面モードのｉ番目インスタンスの回転は、３つの角度、アルファ、ベータ、及びガンマで表される。
【００９７】
compr_elem_insta_rotat_alpha：ｉ番目インスタンスの回転の圧縮済みアルファを含む。
【００９８】
compr_elem_insta_rotat_beta：ｉ番目インスタンスの回転の圧縮済みベータを含む。
【００９９】
compr_elem_insta_rotat_gamma：ｉ番目インスタンスの回転の圧縮済みガンマを含む。
【０１００】
bit_num_rotat_alpha()：ＱＰに基づき、各アルファ値についてビット数を計算する。
【０１０１】
bit_num_rotat_beta()：ＱＰに基づき、各ベータ値についてビット数を計算する。
【０１０２】
bit_num_rotat_gamma()：ＱＰに基づき、各ガンマ値についてビット数を計算する。
【０１０３】
compr_insta_grouped_dataクラス
シンタックス
【表１２】
0005933742.tif 000013
セマンティクス
compr_insta_patternID_header：すべてのインスタンスの圧縮済みパターンＩＤについての、１６ビット・ヘッダ。patternID_dataを自動的に符号化するための圧縮済みビットストリーム長さを決定することが可能な、固定長コーデック又はエントロピー・コーデックを使用する場合、このデータ・フィールドは未使用である。
【０１０４】
compr_insta_patternID_data：すべてのインスタンスの圧縮済みパターンＩＤを含む。
【０１０５】
insta_reflection_flag_data：すべてのインスタンスの反転フラグを含む。バイトが位置合わせされるように圧縮される。
【０１０６】
compr_insta_transl_header：すべてのインスタンスの圧縮済み並進ベクトルについての、１６ビット・ヘッダ。transl_dataを自動的に符号化するための圧縮済みビットストリーム長さを決定することが可能な、固定長コーデック又はエントロピー・コーデックを使用する場合、このデータ・フィールドは未使用である。
【０１０７】
compr_insta_transl_data：すべてのインスタンスの圧縮済み擬似並進ベクトルを含む。完全な説明は４．９を参照のこと。
【０１０８】
compr_insta_rotat_header：すべてのインスタンスの圧縮済み回転変換部分についての、１６ビット・ヘッダ。rotat_dataを自動的に符号化するための圧縮済みビットストリーム長さを決定することが可能な、固定長コーデック又はエントロピー・コーデックを使用する場合、このデータ・フィールドは未使用である。
【０１０９】
compr_insta_rotat_data：すべてのインスタンスの圧縮済み回転変換部分を含む。バイトが位置合わせされるように圧縮される。完全な説明は４．１０を参照のこと。
【０１１０】
compr_insta_scaling_header：すべてのインスタンスの圧縮済みスケーリング係数についての、１６ビット・ヘッダ。scaling_dataを自動的に符号化するための圧縮済みビットストリーム長さを決定することが可能な、エントロピー・コーデックを使用する場合、このデータ・フィールドは未使用である。
【０１１１】
compr_insta_scaling_data：すべてのインスタンスの圧縮済みスケーリング係数を含む。
【０１１２】
insta_share_pattern_property_bit：１ビットの符号なし整数が、すべてのインスタンスがパターンとプロパティを共有するかどうかを示す。０は、すべてのインスタンスがパターンとプロパティを共有せず、それらのプロパティが圧縮されることを意味する。１は、すべてのインスタンスがパターンとプロパティを共有することを意味する。
【０１１３】
compr_insta_normal_header：すべてのインスタンスの圧縮済み法線のヘッダを含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【０１１４】
compr_insta_norma_datal：すべてのインスタンスの圧縮済み法線を含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【０１１５】
compr_insta_color_header：すべてのインスタンスの圧縮済みカラーのヘッダを含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【０１１６】
compr_insta_color_data：すべてのインスタンスの圧縮済みカラーを含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【０１１７】
compr_insta_texcoord_header：すべてのインスタンスの圧縮済みテクスチャ座標のヘッダを含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【０１１８】
compr_insta_texcoord_data：すべてのインスタンスの圧縮済みテクスチャ座標を含む。詳細な定義については、ISO/IEC  14496-16  5.2.1.3を参照のこと。
【０１１９】
insta_error_compen_flag_data：すべてのインスタンスのelem_insta_error_compensate_flagを含む。
【０１２０】
compr_elem_insta_error_compen_header：ｉ番目インスタンスの圧縮済み復号誤りのヘッダを含む。
【０１２１】
compr_elem_insta_error_compen_data：ｉ番目インスタンスの圧縮済み復号誤りを含む。
【０１２２】
compr_insta_transl_dataクラス
シンタックス
【表１３】
0005933742.tif 000014
セマンティクス
num_node：オクトリー・ノードの数を示す、１６ビットの符号なし整数。
【０１２３】
num_dupli_leaf：重複リーフ・ノードと呼ばれる、重複インスタンス並進ベクトルを含むオクトリー・リーフ・ノードの数を示す、８ビットの符号なし整数。
【０１２４】
dupli_leaf_id：オクトリーの幅優先トラバース・シーケンスにおける、ｉ番目の重複リーフ・ノードのインデックスを含む。
【０１２５】
num_dupli_insta_transl：ｉ番目の重複オクトリー・リーフ・ノード内に入る重複インスタンス並進ベクトルの数を示す、４ビットの符号なし整数。
【０１２６】
num_interval_bound：オクトリー占有コード・シーケンス全体の間隔境界の数を示す、８ビットの符号なし整数。
【０１２７】
reserved_bits：バイト位置合わせ目的のいくつかのＩＳＯ予約済みビットを含む。
【０１２８】
interval_bound_id：ｉ番目の間隔境界のインデックスを含む。
【０１２９】
occup_p0_symbols：アルファベットの汎用セットで圧縮されたオクトリー・ノードの占有コードを含む。
【０１３０】
occup_p1_symbols：アルファベットのサブセットで圧縮されたオクトリー・ノードの占有コードを含む。
【０１３１】
compr_insta_rotat_dataクラス
シンタックス
【表１４】
0005933742.tif 000015
実装は、２つのインスタンス・データ・パッキング・モードのうちの１つのみを実装するように選択する可能性がある。その場合、A3DMC_stream_headerにおけるinsta_trans_elem_bitがビットストリーム定義から除去されるべきである。実装によって基本インスタンス・データ・モードが選択された場合、compr_insta_grouped_dataがビットストリーム定義から除去されるべきである。実装によってグループ化インスタンス変換モードが選択された場合、compr_insta_elementary_dataがビットストリーム定義から除去されるべきである。
【０１３２】
実装は、２つのインスタンス回転圧縮モードのうちの１つのみを実装するように選択する可能性がある。その場合、A3DMC_stream_headerにおけるinsta_rotat_mode_bitがビットストリーム定義から除去されるべきである。実装によって圧縮インスタンス回転に対してデカルト・モードが選択された場合、compr_elem_insta_rotat_sphericalがビットストリーム定義から除去されるべきである。実装によって球面モードが選択された場合、compr_elem_insta_rotat_cartesianがビットストリーム定義から除去されるべきである。
【０１３３】
実装は、すべてのインスタンスの圧縮済みパターンＩＤ、並進変換部分、回転変換部分、及びスケーリング係数について、ビットストリーム内にヘッダを含めないように選択する可能性がある。その場合、compr_insta_patternID_header、compr_insta_transl_header、compr_insta_rotat_header、及びcompr_insta_scaling_headerが、ビットストリーム定義から除去されるべきである。
【０１３４】
したがって、本原理に従い、３Ｄモデルが反復構造発見を使用して表され、前述のシンタックスに従ってビットストリームが生成され、法線、カラー、及びテクスチャ座標などの３Ｄモデル・プロパティに対処するため、及び、その変換が反転変換を含むインスタンスを圧縮するために、符号化される。モデル・データがアクセスされ、パターンＩＤ及び変換情報、及びプロパティ情報が決定される。パターンＩＤ、変換情報、及びプロパティ情報は、３Ｄモデルのビットストリーム表現を生成するために、前述のフォーマットのうちの１つに従って、まとめてグループ化される。
【０１３５】
とりわけ本原理は、以下の特徴及び利点を提供する。
【０１３６】
１．本発明者等の反復構造発見ベースの圧縮アルゴリズムの、圧縮済みビットストリームのシンタックス及びセマンティクス。
【０１３７】
２．どちらもビットストリーム内で可能な、基本インスタンス又はグループ化インスタンスのデータ・オプションを有するためのソリューション。
【０１３８】
３．対応するパターン・プロパティ・データ又は対応するデータ・フィールドのいずれかから、インスタンス・プロパティ・データを取得するように適合された、デコーダ。
【０１３９】
４．品質要件に従ってインスタンスの復号誤りを圧縮するように適合された、エンコーダ。
【０１４０】
５．復号されたパターン及び復号されたインスタンス変換から復元された構成要素に、圧縮解除された復号誤りを追加することによって、最終インスタンス構成要素を取得するように適合された、デコーダ。
【０１４１】
６．すべてのパターンをまとめて圧縮するように適合されたエンコーダ。
【０１４２】
７．インスタンスを復元する前にパターンを分離するように適合されたデコーダ。
【０１４３】
８．インスタンス変換の４つの部分、すなわち反転、回転、並進、及び可能スケーリングの部分を、別々に圧縮するように適合された、エンコーダ。
【０１４４】
９．２本の直交軸又はオイラー角としての、１インスタンス変換の回転部分の圧縮。
【０１４５】
図４に示されたように、対応する復号された反転、並進、回転、及び可能スケーリングの部分から、インスタンスの変換マトリクスを復元するように適合された、デコーダ。
【０１４６】
本明細書で説明される実装は、たとえば、方法又はプロセス、装置、ソフトウェア・プログラム、データ・ストリーム、或いは信号内に実装可能である。単一形式の実装との関連においてのみ考察される（たとえば、方法としてのみ考察される）場合であっても、考察される特徴の実装は、他の形（たとえば装置又はプログラム）内でも実装可能である。装置は、たとえば適切なハードウェア、ソフトウェア、及びファームウェア内で実装可能である。方法は、たとえばコンピュータ、マイクロプロセッサ、集積回路、又はプログラマブル論理デバイスを含む、たとえば一般に処理デバイスと呼ばれるプロセッサなどの、装置内で実装可能である。プロセッサは、たとえばコンピュータ、携帯電話、携帯情報端末（「ＰＤＡ」）、及び、エンドユーザ間での情報の通信を容易にする他のデバイスなどの、通信デバイスも含む。
【０１４７】
本原理の「一実施形態」又は「実施形態」又は「一実装」又は「実装」という言い方、並びにそれらの様々な他の変形は、実施形態に関連して説明される特定の機能、構造、特徴などが、本原理の少なくとも１つの実施形態に含まれることを意味する。したがって、
本明細書全体を通じて様々な箇所に現れる、「一実施形態において」又は「実施形態において」又は「一実装において」又は「実装において」という表現、並びに任意の他の変形の出現は、必ずしもすべてが同じ実施形態を指しているわけではない。
【０１４８】
加えて、本明細書又はその特許請求の範囲は、様々な情報片の「決定」を言い表すことができる。情報の決定は、たとえば情報の推定、情報の計算、情報の予測、又はメモリからの情報の取り出しのうちの、１つ又は複数を含むことができる。
【０１４９】
さらに、本明細書又はその特許請求の範囲は、様々な情報片への「アクセス」を言い表すことができる。情報へのアクセスは、たとえば情報の受信、情報の取り出し（たとえばメモリ）、情報の記憶、情報の処理、情報の送信、情報の移動、情報のコピー、情報の消去、情報の計算、情報の決定、情報の予測、又は情報の推定のうちの、１つ又は複数を含むことができる。
【０１５０】
加えて、本明細書又はその特許請求の範囲は、様々な情報片の「受信」を言い表すことができる。「アクセス」と同様に「受信」は、広義な用語であることが意図される。情報の受信は、たとえば情報へのアクセス、又は（たとえばメモリからの）情報の受信のうちの、１つ又は複数を含むことができる。さらに「受信」は、通常、色々な点で、たとえば情報の記憶、情報の処理、情報の送信、情報の移動、情報のコピー、情報の消去、情報の計算、情報の決定、情報の予測、又は情報の推定などの、動作時に関連している。
【０１５１】
当業者には明白であるように、実装は、たとえば記憶又は伝送され得る情報を搬送するようにフォーマット化された様々な信号を生成することができる。情報は、たとえば、方法を実行するための命令、又は説明された実装のうちの１つによって生成されるデータを、含むことができる。たとえば信号は、説明された実施形態のシンタックスを書き込む又は読み取るための規則を、データとして搬送するように、或いは、説明された実施形態によって作成された実際のシンタックス値を、データとして搬送するように、フォーマット化され得る。こうした信号は、たとえば電磁波として（又はスペクトルの無線周波数部分を使用して）、又はベースバンド信号として、フォーマット化することができる。フォーマット化は、たとえばデータ・ストリームの符号化、及び符号化されたデータ・ストリームによる搬送波の変調を含むことができる。信号が搬送する情報は、たとえばアナログ又はデジタルの情報とすることができる。信号は、知られているように、様々な異なる有線又は無線リンクを介して伝送可能である。信号は、プロセッサ読み取り可能媒体上に記憶することが可能である。
【図１】
0005933742.tif 000016
【図２】
0005933742.tif 000017
【図３】
0005933742.tif 000018
【図４】
0005933742.tif 000019