(57)【要約】  ３Ｄメッシュは通常、３種のデータにより表現される。すなわち連結性のデータ、幾何学的データ、物性データである。符号化された３Ｄメッシュモデルは、ビットストリームとして表現され、伝送され及び／または記憶することができる。ビットストリームがすべての変換データを組み込むが、一方でこれは効果的で、複数の適用分野を扱うことができる。この場合、ビットストリームのサイズまたは復号効率または誤り耐性のいずれかが最も重要になることがある。よって、一つのインスタンスの変換データ、即ちその位置、方向、倍率をビットストリーム中にどのように配置するかについて、２つのモードのオプションが開示されている。第１のモードでは、一つのインスタンスの位置、方向、可能な倍率が共にビットストリームに共にパッケージ化される。第２のモードでは、変換データのタイプ、例えばすべてのインスタンスの位置、方向、可能な倍率が共に、データのタイプによりビットストリームにより、共にパッケージ化される。
2014518421.tif 000002
【特許請求の範囲】
【請求項１】
３Ｄモデルを表現するビットストリームを符号化又は復号する方法であって、
３Ｄモデルに関連付けられた複数のインスタンス情報にアクセスするステップであって、各インスタンスは対応するパターン及び変換データに関連付けられている前記ステップと、
第１または第２のモードでビットストリーム中の送信のための複数のパターン情報を符号化又は復号するステップと、を含み、
第１のモードでは、各々異なるインスタンスに関連付けられた変換情報は、インスタンス単位で各インスタンスを有するビットストリームにグループ化され、第２のモードでは、変換情報は変換情報タイプ単位でビットストリームにグループ化される、前記方法。
【請求項２】
前記インスタンス情報は、第１のモードでグループ化されるか、第２のモードでグループ化されるかを決定するために、インディケータビットを使用するステップを更に含む、請求項１に記載の方法。
【請求項３】
変換データのタイプは、位置、方向、倍率データの１つ以上を含む、請求項２に記載の方法。
【請求項４】
前記インスタンス情報に続く３Ｄモデルの一意的部分に関連するデータを符号化又は復号するステップを更に含む、請求項３に記載の方法。
【請求項５】
ビットストリームは、第１および第２のモードの適応的組合せを使用して符号化または復号され、前記インスタンス情報のうち選択されたものは、第１のモードを使用して符号化または復号され、前記インスタンス情報のうち他の選択されたものは、第２のモードを使用して符号化または復号される、請求項３に記載の方法。
【請求項６】
３Ｄモデルを表現するビットストリームを符号化するエンコーダであって、
パターン、及び繰り返し構造及び変換データに関連付けられたインスタンスを含む３Ｄモデルに繰り返し構造を発見するモジュールと、
第１及び第２のモードのうち一つのモードで、ビットストリーム中のインスタンス情報を符号化するモジュールと、を備え、第１のモードでは、各々異なるインスタンスに関連付けられた変換情報は、インスタンス単位で各インスタンスを有するビットストリームにグループ化され、第２のモードでは、変換情報は変換情報タイプ単位でビットストリームにグループ化される、前記エンコーダ。
【請求項７】
前記符号化するモジュールは、前記インスタンス情報が、第１のモードでグループ化されるか、第２のモードでグループ化されるかを決定するために、インディケータビットを含む、請求項６に記載の方法。
【請求項８】
前記変換データのタイプは、位置、方向、倍率データの１つ以上を含む、請求項７に記載の方法。
【請求項９】
前記符号化するモジュールは、前記インスタンス情報に続く３Ｄモデルの一意的部分に関連するデータを更に含む、請求項８に記載の方法。
【請求項１０】
前記符号化するモジュールは、第１および第２のモードの適応的組合せを使用してビットストリームを符号化し、前記インスタンス情報のうち選択されたものは、第１のモードを使用して符号化または復号され、前記インスタンス情報のうち他の選択されたものは、第２のモードを使用して符号化または復号される、請求項８に記載の方法。
【請求項１１】
３Ｄモデルを表現するビットストリームを復号するデコーダであって、
対応するパターン及び変換データに関連付けられたインスタンス情報を含むビットストリームにアクセスするためのモジュールと、
第１および第２のモードのうち一つのモードでビットストリーム中のインスタンス情報を復号するモジュールと、を備え、第１のモードでは、各々異なるインスタンスに関連付けられた変換情報は、インスタンス単位で各インスタンスを有するビットストリームにグループ化され、第２のモードでは、変換情報は変換情報タイプ単位でビットストリームにグループ化される、前記デコーダ。
【請求項１２】
前記復号するモジュールは、前記インスタンス情報が、第１のモードでグループ化されるか、第２のモードでグループ化されるかをインディケータビットに基づいて決定する、請求項１１に記載の前記方法。
【請求項１３】
前記変換データのタイプは、位置、方向、倍率データを含む、請求項１２に記載の前記方法。
【請求項１４】
前記復号するモジュールは、前記インスタンス情報に続く３Ｄモデルの一意的部分に関連するデータを更に復号する、請求項１３に記載の前記方法。
【請求項１５】
前記復号するモジュールは、第１および第２のモードの適応的組合せを使用してビットストリームを復号し、前記インスタンス情報のうち選択されたものは、第１のモードを使用して符号化または復号され、前記インスタンス情報のうち他の選択されたものは、第２のモードを使用して符号化または復号される、請求項１３に記載の方法。
【請求項１６】
有形媒体に記憶された３Ｄモデルを表現するビットストリームであって、
対応するパターン及び変換データに関連付けられているインスタンス情報を備え、
前記インスタンス情報は、第１および第２のモードのうち一つのモードで前記ビットストリームに添付されており、第１のモードでは、各々異なるインスタンスに関連付けられた変換情報は、インスタンス単位で各インスタンスを有するビットストリームにグループ化され、第２のモードでは、変換情報は変換情報タイプ単位でビットストリームにグループ化される、前記ビットストリーム。
【請求項１７】
前記ビットストリームは、前記インスタンス情報が、第１のモードでグループ化されるか、第２のモードでグループ化されるかを示すインディケータビットを含む、請求項１６に記載の方法。
【請求項１８】
前記変換データのタイプは、位置、方向、倍率データを含む、請求項１７に記載の方法。
【請求項１９】
前記ビットストリームは、前記インスタンス情報に続く３Ｄモデルの一意的部分に関連するデータを更に含む、請求項１８に記載の方法。
【請求項２０】
前記ビットストリームは、第１および第２のモードの適応的組合せを含み、前記インスタンス情報のうち選択されたものは、第１のモードを使用して符号化または復号化され、前記インスタンス情報のうち他の選択されたものは、第２のモードを使用して符号化または復号化される、請求項１８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、繰り返し構造発見をベースとした３Ｄモデル圧縮アルゴリズムのビットストリームシンタック及びセマンティックス、これらを符号化する方法及び装置、これらを復号する方法及び装置に関する。
【背景技術】
【０００２】
実際の適用では、多くの３Ｄモデルは、多数の連結した成分から成る。そしてこれらの多数連結した３Ｄモデルは通常、図１に示すように、種々の変換に多くの繰り返し構造を含んでいる。この種の３Ｄモデルの効果的な圧縮方法は、繰り返し構造に存在する冗長性を抜き出せることが必要である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】国際公開第２０１０／１４９４９２号   [ＰＡ０９００３９]Ｋａｎｇｙｉｎｇ  Ｃａｉ，Ｊ．Ｙｕ及びＺ．Ｂ．Ｃｈｅｎ「大規模な３Ｄの工学モデルのための効率的な圧縮方式」（国際特許出願ＰＣＴ／ＥＰ２０１０／０５８０４８，ＷＯ２０１０／１４９４９２号Ａ１として出願公開（内部参照番号ＰＱ０９００３９）
【非特許文献１】[ＣＡＩ２００９]Ｋａｎｇｙｉｎｇ  Ｃａｉ，Ｗｅｎｃｈｅｎｇ  Ｗａｎｇ，Ｚｈｉｂｏ  Ｃｈｅｎ，Ｑｕｑｉｎｇ  Ｃｈｅｎ及びＪｕｎ  Ｔｅｎｇ，「大規模モデルの効果的圧縮のための繰り返しパターンの開発」（ＶＲＣＡＩ２００９）
【非特許文献２】[ｗ１１４５５]ＩＳＯ／ＩＥＣ（国際標準化機構）１４４９６−１６  第４版、ＭＰＥＧ−３ＤＧＣ，第９３回ＭＰＥＧ会議の最終テキスト
【発明の概要】
【０００４】
入力モデルに繰り返し構造を発見することを利用する、多数連結された３Ｄモデルに対する効果的な圧縮アルゴリズムは、２０１０年６月９日に出願され、トムソン  ライセンシングに譲渡されたＷＯ２０１０／１４９４９２号「大規模な３Ｄの工学モデルのための効率的な圧縮方式」に提案されており、その教示は本明細書に参照により組み込まれている。これは種々の位置、方向、倍率で繰り返されている構造を発見する。そして３Ｄモデルは、「パターンのインスタンス」表現に構造化されている。パターンは対応する繰り返し構造を代表する幾何学である。繰り返し構造に属する連結成分は、対応するパターンのインスタンスと呼ばれ、その変換、すなわちパターンに関する位置、方向、可能な倍率により表現される。インスタンスの方向は、デカルト座標系の（ｘ０，ｙ０，ｚ０）及び（ｘ１，ｙ１，ｚ１）または球座標系（α，β，γ）により表現される２つの直交軸により表現される。
【０００５】
繰り返し構造の発見をベースとした圧縮アルゴリズムに関する、圧縮ビットストリームのシンタックス及びセマンティックスが開示されており、これはＭＰＥＧ−３ＤＧＣにより提供される静的３Ｄモデル圧縮アルゴリズムより効果的であることが証明されている。本願の繰り返し構造の発見をベースとした圧縮アルゴリズムの開示された圧縮ビットストリームのシンタックス及びセマンティックスは、例えばＭＰＥＧに適用可能である。
【０００６】
本発明は、圧縮ビットストリームのシンタックス及びセマンティックスに関する。
【０００７】
本発明は更に、繰り返し構造を有する３Ｄモデルに対するビットストリームを符号化し、復号するシステム及び方法を提供する。
【０００８】
当該方法を利用する装置は以下に示されている。
【０００９】
本発明は更に、繰り返し構造を有する３Ｄモデルに対するビットストリームを符号化し、あるいは復号する対応するステップを有する方法をコンピュータに実行させるための実行可能な命令を有するコンピュータ可読媒体を提供する。
【図面の簡単な説明】
【００１０】
【図１】多数の連結成分及び繰り返し構造を有する例示的３Ｄモデルを示す。
【図２】本発明による３ＤＭＣ圧縮ビットストリームの構造を処理する方法を示す。
【図３】本発明の原理による３Ｄモデルの例示的エンコーダを示す。
【図４】本発明の原理による３Ｄモデルの例示的デコーダを示す。
【発明を実施するための形態】
【００１１】
３次元（３Ｄ）メッシュは、ビデオゲーム、工学的設計、ｅコマース、ヴァーチャル・リアリティ、構造上および科学技術上の視覚化等３Ｄオブジェクトを表現する様々な適用分野で広く使用される。その未処理の表現は通常、膨大なデータを必要とする。しかしほとんどの適用分野は、記憶または伝送のためのコンパクトな３Ｄメッシュ表現を好む。３Ｄメッシュは通常、３種のデータにより表現される。すなわち連結性のデータ、幾何学的データ、物性データである。連結性のデータは、頂点間の隣接関係を記述し、幾何学的データは頂点の配置を特定し、物性データは法線ベクトル、材料の反射率、テクスチャ座標系等の属性を特定する。ほとんどの３Ｄ圧縮アルゴリズムは、連結性データ、幾何学的データを別個に備えている。幾何学的データの符号化順序は、基礎となる連結性の符号化により決定される。幾何学的データは通常、量子化、予測、統計的符号化という３つの主なステップにより圧縮される。３Ｄメッシュの物性データは通常、同様の手法で圧縮される。
【００１２】
本発明は、大規模な３Ｄ光学モデルの効果的な圧縮方法に関する。当該モデルはしばしば、いわゆる「連結成分」という複数の区画から構成される。幾何学的特徴のパターンを繰り返す表現における冗長性は、一つの幾何学的なパターンのインスタンスとして、（例えば、位置、サイズの正規化後の）等価である連結成分をすべて考慮することにより削減できる。等価な成分はクラスタリングが可能である。クラスタは、３Ｄモデルの一部のみか、あるいはすべての成分を指すことができる。次に、それぞれの連結成分は、対応する幾何学的なパターン（またはクラスタリングの種類）の英数字識別子等の識別子と、幾何学的なパターンから成分を再構成できる変換情報とによって表現することができる。この変換情報は、例としては、倍率、平均値（または中央値）、方向軸（または／及び回転の情報）またはシフトの情報の一つ以上であってもよい。原則として、他の情報も可能である。
【００１３】
符号化されたモデルは、ビットストリームとして表現され、伝送され及び／または記憶することができる。
【００１４】
本願はビットストリームがすべての変換データを組み込むことを所望するが、一方で本願はこれが効果的で、複数の適用分野を扱うことも所望し、この場合、ビットストリームのサイズまたは復号効率または誤り耐性のいずれかが最も重要となることがある。
【００１５】
よって、一つのインスタンスの変換データ、すなわちその位置、方向及び倍率をビットストリーム中にどのように配置するかについて、２つのオプションが開示されている。双方のオプションには独自の効果がある。双方の適応的組合せは、特に効果的である。
【００１６】
オプション（Ａ）は、グループ化されたインスタンス変換モードと呼ばれる。このモードを利用して、一つのインスタンスの位置、方向、及び可能な倍率がビットストリームに共にパッケージ化される。
【００１７】
オプション（Ａ）の効果は以下の通りである。
・これは誤り耐性である。デコーダは、幾つかのインスタンスの変換の喪失から復元可能である。
・オンライン復号。これは、圧縮ビットストリームを読み込む過程において、インスタンスを一つ一つ復号できることを意味する。圧縮ビットストリーム全体の読み込みの完了を待つ必要はない。
・より高いコーデック速度
・コーデックはバッファを必要としない（またはごく一部しか必要としない）。
【００１８】
オプション（Ｂ）は別個のインスタンス変換モードと呼ばれる。すべてのインスタンスの位置、方向あるいは可能な倍率は、ビットストリームに共にパッケージ化される。換言すれば、一つのインスタンスの位置、方向、及び可能な倍率がビットストリームに別個にパッケージ化される。
【００１９】
オプション（Ｂ）の効果は以下の通りである。
・オプション（Ａ）に対して小さい圧縮された３Ｄモデルのサイズ
【００２０】
オプション（Ｂ）を使用するデコーダは、以下の特徴も備えている。
・デコーダは誤り耐性ではない。
・オフライン復号。これは、デコーダが圧縮ビットストリーム全体を読み込んで初めて復号を開始できることを意味する。
・より低いコーデック速度
・バッファが必要である。
【００２１】
本願のビットストリームの定義には、上記２つのオプション（Ａ）及び（Ｂ）の双方が含まれる。そしてユーザまたは自動制御手段は、一つ以上の適用分野に適合するものを選択することができる。
【００２２】
本願の繰り返し構造発見をベースとした圧縮アルゴリズムである、Ａ３ＤＭＣの圧縮ビットストリームの全体構造は図２に示す通りである。
【００２３】
ビットストリームはヘッダバッファ（Ａ３ＤＭＣ＿ｓｔｒｅａｍ＿ｈｅａｄｅｒ）から開始し、これには圧縮ストリームを復号するのに必要なすべての情報が含まれる。すなわち、当初のモデル、必要に応じてパターンおよび他の部分を圧縮するのに使用される３Ｄモデル圧縮方法には何らかの繰り返し構造が存在するか、このビットストリームにおいては、「グループ化されたインスタンス変換モード」と「別個のインスタンス変換モード」のいずれが使用されているか、いずれの繰り返し構造にも含まれない当初のモデルの何らかの部分（一意的部分）があるか等である。
【００２４】
当初のモデルに繰り返し部分がない場合（ｒｅｐｅａｔ＿ｓｔｒｕｃ＿ｂｉｔ！＝１）、ビットストリームの左部分（例えば先頭）は、Ａ３ＤＭＣ＿ｓｔｒｅａｍ＿ｈｅａｄｅｒに表示される３Ｄモデル圧縮方法を利用する圧縮された入力３Ｄモデルである。そうでない場合は、ビットストリームの次の部分は、すべてのパターンの圧縮された結果である。このビットストリームにおいていずれのインスタンス変換パッキングモードが選択されたかにより、ｃｏｍｐｒ＿ｉｎｓｔａ＿ｇｒｏｕｐｅｄ＿ｄａｔａまたはｃｏｍｐｒ＿ｉｎｓｔａ＿ｓｅｐａｒａｔｅ＿ｄａｔａのいずれかがビットストリームにおいて次の部分となる。当初の３Ｄモデルにおいて一意的部分が存在する場合、ｃｏｍｐｒ＿ｕｎｉ＿ｐａｒｔ＿ｄａｔａが添付される。そうでない場合は、ビットストリームは終了する。
【００２５】
Ａ３ＤＭＣの圧縮ビットストリームのシンタックス及びセマンティックスを、以下のように詳細に説明する。
【００２６】
ビットストリームのシンタックスおよびセマンティックス
【００２７】
シンタックス機能、カテゴリおよび記述子の仕様
ｆ（ｎ）：（左から右に）記載されたｎビットを使用した固定パターンビット文字列。ｎは、各シンボルのコード長に左右される。
ｅｃ（ｖ）：構成シンボルを含む場合もある、エントロピー符号化された（例えば、算術符号化された）シンタックスエレメント。
【００２８】
Ａ３ＤＭＣ＿ｓｔｒｅａｍ ｃｌａｓｓ
【表１】
2014518421.tif 000003
【００２９】
Ａ３ＤＭＣ＿ｓｔｒｅａｍ＿ｈｅａｄｅｒ：ヘッダバッファを含んでいる。
Ａ３ＤＭＣ＿ｓｔｒｅａｍ＿ｄａｔａ：データバッファを含んでいる。
【００３０】
Ａ３ＤＭＣ＿ｓｔｒｅａｍ＿ｈｅａｄｅｒ  ｃｌａｓｓ
【表２】
2014518421.tif 000004
【００３１】
ｒｅｐｅａｔ＿ｓｔｒｕｃ＿ｂｉｔ：３Ｄモデルに繰り返し構造があるか否かを示す１ビット符号なし整数である。０は繰り返し構造がないことを意味し、１は繰り返し構造を意味する。
３ｄ＿ｍｏｄｅｌ＿ｃｏｍｐｒ＿ｍｏｄｅ：繰り返し構造を含んでいない場合に、パターン、一意的部分、当初の３Ｄモデル自体を圧縮するのに使用される３Ｄモデル圧縮方法を示す、２ビット符号なし整数。
【００３２】
【表３】
2014518421.tif 000005
【００３３】
ＱＰ：量子化パタメータを示す５ビットの符号なし整数。例えばＱＰの最小値は３であり、最高値は３１である。
ｐａｔｔｅｒｎ＿ｎｕｍ：２５５未満の場合のすべてのパターン数を示す８ビット符号なし整数。ｐａｔｔｅｒｎ＿ｎｕｍの最小値は１である。
ｐａｔｔｅｒｎ＿ｎｕｍ＿２：２５５以上の場合のすべてのパターン数を示す１６ビットの符号なし整数。この場合、パターン総数は、（ｐａｔｔｅｒｎ＿ｎｕｍ＿２＋２５５）である。
ｉｎｓｔａｎｃｅ＿ｎｕｍ：６５５３５未満の場合のすべてのインスタンスの数を示す１６ビット符号なし整数。ｉｎｓｔａｎｃｅ＿ｎｕｍの最小値は１である。
ｉｎｓｔａｎｃｅ＿ｎｕｍ＿２：６５５３５以上の場合のすべてのインスタンスの数を示す３２ビットの符号なし整数。この場合、インスタンス総数は、（ｉｎｓｔａｎｃｅ＿ｎｕｍ＿２＋６５５３５）である。
ｉｎｓｔａ＿ｔｒａｎｓ＿ｇｒｏｕｐ＿ｂｉｔ：「グループ化されたインスタンス変換モード」と「別個のインスタンス変換モード」が本ビットストリームで使用されているか否かを示す１ビット符号なし整数。０は「別個のインスタンス変換モード」を表し、１は「グループ化されたインスタンス変換モード」を表す。
ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｍｏｄｅ＿ｂｉｔ：インスタンス方向の符号化モードを示す１ビット符号なし整数。０は球モードを意味し、１はデカルトモードを意味する。
ｕｓｅ＿ｓｃａｌｉｎｇ＿ｂｉｔ：インスタンス変換が倍率を含むか否かを示す１ビット符号なし整数。０は倍率がインスタンス変換に含まれることを表し、１は含まれないことを表す。
ｕｎｉ＿ｐａｒｔ＿ｂｉｔ：１ビット符号なし整数は、当初の３Ｄモデルには一意的部分があるか否かを示す。０は一意的部分がないことを意味し、１は一意的部分があることを意味する。
ｒｅｓｅｒｖｅｄ＿ｂｉｔｓ：常に００００であり、バイトアライメントに使用される４ビット符号なし整数。
【００３４】
Ａ３ＤＭＣ＿ｓｔｒｅａｍ＿ｄａｔａ  ｃｌａｓｓ
【表４】
2014518421.tif 000006
【００３５】
ｃｏｍｐｒ＿ｒｅｐｅａｔ＿ｓｔｒｕｃ＿ｄａｔａ：繰り返し構造を含む圧縮された３Ｄモデルを含む。
ｃｏｍｐｒ＿３ｄ＿ｍｏｄｅｌ＿ｄａｔａ：繰り返し構造を有さず、３ｄ＿ｍｏｄｅｌ＿ｃｏｍｐｒ＿ｍｏｄｅにより表示される圧縮方法により符号化される、圧縮された３Ｄモデルを含む。
【００３６】
ｃｏｍｐｒ＿ｒｅｐｅａｔ＿ｓｔｒｕｃ＿ｄａｔａ  ｃｌａｓｓ
【表５】
2014518421.tif 000007
【００３７】
ｃｏｍｐｒ＿ｐａｔｔｅｒｎ＿ｄａｔａ：すべてのパターンの圧縮されたパターンデータを含んでおり、これは３ｄ＿ｍｏｄｅｌ＿ｃｏｍｐｒ＿ｍｏｄｅにより表示される圧縮方法により符号化される。
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｇｒｏｕｐｅｄ＿ｄａｔａ：「グループ化されたインスタンス変換モード」を使用する圧縮されたインスタンス変換データを含んでいる。
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｓｅｐａｒａｔｅ＿ｄａｔａ：「別個のインスタンス変換モード」を使用する圧縮されたインスタンス変換データを含んでいる。
ｃｏｍｐｒ＿ｕｎｉ＿ｐａｒｔ＿ｄａｔａ：圧縮された一意的部分のデータを含んでおり、これは３ｄ＿ｍｏｄｅｌ＿ｃｏｍｐｒ＿ｍｏｄｅにより表示される圧縮方法により符号化される。
【００３８】
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｇｒｏｕｐｅｄ＿ｄａｔａ  ｃｌａｓｓ
【表６】
2014518421.tif 000008
【００３９】
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｐａｔｔｅｒｎＩＤ：ｉ番目のインスタンスの圧縮されたパターンＩＤを含んでいる。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｐｏｓｉｔｉｏｎ：インスタンスの圧縮された位置を含んでいる
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｃａｒｔｅｓｉａｎ：デカルトモードにおけるｉ番目のインスタンスの圧縮された方向を含んでいる。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｓｐｈｅｒｉｃａｌ：球モードにおけるｉ番目のインスタンスの圧縮された方向を含んでいる。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｓｃａｌｉｎｇ：ｉ番目のインスタンスの圧縮された倍率を含んでいる。
ｂｉｔ＿ｎｕｍ＿ｉｎｓｔａ＿ｐｏｓｉｔｉｏｎ（）：ＱＰに基づいて各インスタンスの位置の値につき、ビット数を算定する。
【００４０】
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｃａｒｔｅｓｉａｎ  ｃｌａｓｓ
【表７】
2014518421.tif 000009
【００４１】
デカルトモードにおけるｉ番目のインスタンスの方向は、２つの直交軸（ｘ０，ｙ０，ｚ０）および（ｘ１，ｙ１，ｚ１）により表現される。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｘ０：ｉ番目のインスタンスの方向の圧縮されたｘ０を含んでいる。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｙ０：ｉ番目のインスタンスの方向の圧縮されたｙ０を含んでいる。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｚ０＿ｓｇｎ：ｘ０及びｙ０を使用してｚ０を算定するのに必要なｚ０の符号を表示する１ビット符号なし整数。０は“-”を表し、１は“＋”を表している。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｚ０＿ｒｅｓ：（ｚ０―ｃｏｍｐｕｔｅｒ＿ｚ０（））により算定されるｚ０の圧縮された残差を含んでいる。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｚ１：ｉ番目のインスタンスの方向の圧縮されたｚ１を含んでいる。
ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｘ１＿ｓｇｎ：ｘ０，ｙ０を使用してｘ１を算定するのに必要なｘ１の符号を表示する１ビット符号なし整数。０は“-”を表し、１は“＋”を表している。
ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｙ１＿ｓｇｎ：ｘ０，ｙ０を使用してｙ１を算定するのに必要なｙ１の符号を表示する１ビット符号なし整数。０は“-”を表し、１は“＋”を表している。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｘ１：ｉ番目のインスタンスの方向の圧縮されたｘ１を含んでいる。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｙ１：ｉ番目のインスタンスの方向の圧縮されたｙ１を含んでいる。
ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｄｅｌｔａ＿ｓｇｎ：ｘ０，ｙ０，ｚ０を使用してｘ１またはｙ１を算定するのに必要な符号を表示する１ビット符号なし整数。０は“-”を表し、１は“＋”を表している。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｚ１＿ｒｅｓ：（ｚ１―ｃｏｍｐｕｔｅｒ＿ｚ１（））により算定されるｚ１の圧縮された残差を含んでいる。
しきい値：圧縮分野で広く受け入れられているしきい値。
ｃｏｍｐｕｔｅ＿ｚ０（）：ｘ０，ｙ０，ｚ０符号を使用して、ｉ番目のインスタンスのｚ０を算定する。
ｂｉｔ＿ｎｕｍ＿ｏｒｉｅｎｔ＿ｃａｒｔｅｓｉａｎ（）：ＱＰに基づいてデカルト座標系において、各方向の値につき、ビット数を算定する。
ｂｉｔ＿ｎｕｍ＿ｏｒｉｅｎｔ＿ｒｅｓ＿ｃａｒｔｅｓｉａｎ（）：ＱＰに基づいてデカルト座標系において、各方向の残差値につき、ビット数を算定する。
ｃｏｍｐｕｔｅ＿ｚ１（）：ｘ０，ｙ０，ｚ０，ｘ１，ｙ１を使用して、ｉ番目のインスタンスのｚ１を算定する。
【００４２】
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｓｐｈｅｒｉｃａｌ  ｃｌａｓｓ
【表８】
2014518421.tif 000010
【００４３】
球モードにおけるｉ番目のインスタンスの方向は、３つの角度α，β，γにより表現される。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ａｌｐｈａ：ｉ番目のインスタンスの方向の圧縮されたαを含んでいる。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｂｅｔａ：ｉ番目のインスタンスの方向の圧縮されたβを含んでいる。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｇａｍｍａ：ｉ番目のインスタンスの方向の圧縮されたγを含んでいる。
ｃｏｍｐｒ＿ｉｔｈ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｒｅｓ：ｉ番目のインスタンスの方向のデカルト座標系における圧縮された残差を含んでいる。
ｂｉｔ＿ｎｕｍ＿ｏｒｉｅｎｔ＿ａｌｐｈａ（）：ＱＰに基づいて各アルファ値につき、ビット数を算定する。
ｂｉｔ＿ｎｕｍ＿ｏｒｉｅｎｔ＿ｂｅｔａ（）：ＱＰに基づいて各ベータ値につき、ビット数を算定する。
ｂｉｔ＿ｎｕｍ＿ｏｒｉｅｎｔ＿ｇａｍｍａ（）：ＱＰに基づいて各ガンマ値につき、ビット数を算定する。
ｎｅｅｄ＿ｃｏｒｒｅｃｔｉｏｎ（）：方向をチェックし、大誤差を生じさせる可能性のあるエッジ条件である場合は、真を返し、そうでない場合は、偽を返す。
【００４４】
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｓｅｐａｒａｔｅ＿ｄａｔａ  ｃｌａｓｓ
【表９】
2014518421.tif 000011
【００４５】
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｐａｔｔｅｒｎＩＤ＿ｌｅｎｇｔｈ：すべてのインスタンスの圧縮されたパターンＩＤの長さを表示する３２ビット符号なし整数を含んでいる。
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｐａｔｔｅｒｎＩＤ＿ｄａｔａ：すべてのインスタンスの圧縮されたパターンＩＤを含んでいる。
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｐｏｓｉｔｉｏｎ＿ｌｅｎｇｔｈ：すべてのインスタンスの圧縮された位置の長さを表示する３２ビット符号なし整数を含んでいる。
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｐｏｓｉｔｉｏｎ＿ｄａｔａ：すべてのインスタンスの圧縮された位置を含んでいる。
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｌｅｎｇｔｈ：すべてのインスタンスの圧縮された方向の長さを表示する３２ビット符号なし整数を含んでいる。
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｄａｔａ：すべてのインスタンスの圧縮された方向を含んでいる。
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｓｃａｌｉｎｇ＿ｌｅｎｇｔｈ：すべてのインスタンスの圧縮された倍率の長さを表示する３２ビット符号なし整数を含んでいる。
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｓｃａｌｉｎｇ＿ｄａｔａ：すべてのインスタンスの圧縮された倍率を含んでいる。
【００４６】
ｃｏｍｐｒ＿ｉｎｓ＿ｐｏｓｉｔｉｏｎ＿ｄａｔａ  ｃｌａｓｓ
【表１０】
2014518421.tif 000012
【００４７】
ｉｎｓｔａ＿ｐｏｓｉｔｉｏｎ＿ｂｂｏｘ：すべてのインスタンスの位置の境界ボックスを含んでいる。
ｃｏｎｆｉｇ＿ｎ０＿ｓｙｍｂｏｌｓ：ｎ０の通常の八分木構成シンボルを含んでいる。
ｃｏｎｆｉｇ＿ｎ１＿ｓｙｍｂｏｌｓ：ｎ１の通常の八分木構成シンボルを含んでいる。
ｃｏｎｆｉｇ＿ｎ２＿ｓｙｍｂｏｌｓ：ｎ２の通常の八分木構成シンボルを含んでいる。
【００４８】
ｃｏｍｐｒ＿ｉｎｓｔａ＿ｏｒｉｅｎｔ＿ｄａｔａ  ｃｌａｓｓ
【表１１】
2014518421.tif 000013
【００４９】
更に上記ビットストリームは、ＭＰＥＧ−３ＤＧＣ［ｗ１１４５５］により定義されたＳＣ３ＤＭＣビットストリーム等他のビットビットストリームに埋め込まれていてもよい。ここには当該解決手段の可能な実施形態がある。
【００５０】
本願は、ＳＣ３ＤＭＣストリームヘッダの符号化モードのＩＳＯの予約済み値３を以下のように使用する（[ｗ１１４５５]の原表５３参照）。
【００５１】
表１―ＳＣ３ＤＭＣ符号化モード
【表１２】
2014518421.tif 000014
【００５２】
本願は、[ｗ１１４５５]で定義されたＳＣ３ＤＭＣストリームを以下のように修正する。
【００５３】
【表１３】
2014518421.tif 000015
【００５４】
Ａ３ＤＭＣ＿ｓｔｒｅａｍ＿ｈｅａｄｅｒ＿ＳＣ３ＤＭＣ  ｃｌａｓｓ
【表１４】
2014518421.tif 000016
【００５５】
ｒｅｓｅｒｖｅｄ＿ｂｉｔｓ＿ｆｉｒｓｔ：常に０である１ビット符号なし整数。これはバイトアライメント用である。
【００５６】
特に、本発明は、
１．本願の繰り返し構造発見をベースとした圧縮アルゴリズムの圧縮ビットストリームシンタック及びセマンティックス
２．別個のインスタンスまたはグループ化されたインスタンス変換データのオプションであって、双方ともビットストリームで可能なものを有するための解決手段
３．既存のＳＣ３ＤＭＣビットストリームにおける本願の現在のビットストリーム提案の可能な実施形態
【００５７】
図３は、例示的３Ｄモデルエンコーダ３００のブロック図を示している。装置３００の入力は、３Ｄモデル、３Ｄモデルおよび他のメタデータを符号化するための品質パラメータを含んでいてもよい。３Ｄモデルは最初に繰り返し構造発見モジュール３１０を通過し、これはパターン、インスタンスおよび一意的コンポーネントの観点から３Ｄモデルを出力する。パターンエンコーダ３２０は、パターンを圧縮するために用いられ、一意的コンポーネントエンコーダ３５０は、一意的コンポーネントを符号化するために用いられる。インスタンスについては、インスタンスコンポーネント情報は、ユーザ選択モードに基づき符号化される。インスタンス情報グループモードが選択される場合、インスタンス情報はグループ化されたインスタンス情報エンコーダ３４０を使用して符号化され、選択されない場合は、基本的インスタンス情報エンコーダ３３０を使用して符号化される。符号化されたコンポーネントは、更に繰り返し構造検証器３６０で検証される。符号化されたコンポーネントが品質要求に適合しない場合、これは一意的コンポーネントエンコーダ３５０を使用して符号化されることになる。パターン、インスタンス、一意的コンポーネントのためのビットストリームは、ビットストリーム・アセンブラ３７０で組み立てられる。
【００５８】
図４は、例示的３Ｄモデルデコーダ４００のブロック図を示す。装置４００の入力は３Ｄモデルのビットストリーム、例えばエンコーダ３００により生成されるビットストリームであってもよい。圧縮ビットストリームにおけるパターンに関する情報は、パターンデコーダ４２０により復号される。一意的コンポーネントに関する情報は、一意的コンポーネントデコーダ４５０により復号される。インスタンス情報の復号もユーザ選択モードに依存する。インスタンス情報グループモードが選択される場合、インスタンス情報はグループ化されたインスタンス情報デコーダ４４０を使用して復号され、選択されない場合は、基本的インスタンス情報デコーダ４３０を使用して復号される。復号されたパターン、インスタンス情報及び一意的コンポーネントは、モデル再構成モジュール４６０で出力３Ｄモデルを生成するために再構成される。
【００５９】
本明細書で記載される実装は、例えば方法、プロセス、装置、ソフトウエアプログラム、データストリーム、信号において実装されもよい。信号形式の実装の関連でのみ考察される場合（例えば方法としてのみ考察される場合）であっても、考察される特徴の実装は、他の形式（例えば、装置またはプログラム）で実装されてもよい。装置は、例えば適切なハードウエア、ソフトウエア、ファームウエアにおいて実装されてもよい。当該方法は例えば、一般にはコンピュータ、マイクロプロセッサ、集積回路、プログラム可能論理装置を含む処理装置を指すプロセッサ等の装置において実装されてもよい。プロセッサは更に、例えばコンピュータ、携帯電話、携帯情報端末（ＰＤＡ；Ｐｏｒｔａｂｌｅ／Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）、その他エンドユーザ間の情報の通信を円滑にする他のデバイス等の通信装置であってもよい。
【００６０】
本発明の原理の「一つの実施形態」または「実施形態」または「一つの実装」または「実装」並びにこれらの他の変形に対する参照は、実施形態との関連で記載された特定の特性、構造、特徴等は、本発明の原理の少なくとも一つの実施形態に含まれることを意味する。よって「一つの実施形態において」または「実施形態において」または「一つの実装において」または「実装において」フレーズが現れること、並びに明細書を通して様々な箇所に現れる他のいずれかの変形は、必ずしもすべてが同一の実施形態に言及しているとは限らない。
【００６１】
当業者に明らかなように、実装することにより、例えば記憶または送信できる情報を伝送するためにフォーマットされた種々の信号を生成することができる。情報には例えば、方法を実行するための指令、記述された実装の一つにより生成されるデータがある。例えば信号は、記述された実施形態のビットストリームを伝送するためにフォーマットされてもよい。かかる信号は、例えば、電磁波（例えばスペクトルの無線周波数部分を用いて）またはベースバンド信号としてフォーマットされてもよい。フォーマットすることには例えば、データストリームを符号化し、符号化されたデータストリームでキャリアを変調することであってもよい。信号が伝達する情報は例えば、アナログまたはデジタル情報であってもよい。信号は、既知の種々の異なる有線または無線リンクを介して送信されてもよい。信号はプロセッサ可読媒体に記憶されてもよい。
【００６２】
原則として、開示された発明は、他のデータ圧縮領域にも適用可能である。本発明は、一意的ビットストリームフォーマットを生じさせる。
【００６３】
ビットストリームがすべての変換データを組み込むが、一方でこれは効果的で、複数の適用分野を扱うことができる。この場合、ビットストリームのサイズまたは復号効率または誤り耐性のいずれかが最も重要になることがある。よって、一つのインスタンスの変換データ、即ちその位置、方向、倍率をビットストリーム中にどのように配置するかについて、２つのモードのオプションが開示されている。第１のモード（オプションＡ）では、一つのインスタンスの位置、方向、可能な倍率がビットストリームに共にパッケージ化される。第２のモード（オプションＢ）では、すべてのインスタンスの位置、方向、可能な倍率が共にビットストリームにパッケージ化される。
【００６４】
本発明は単に一つの例として記載されているに過ぎず、細部の改変は本発明の範囲から逸脱しない限り行うことができることが理解されるだろう。
【００６５】
明細書に開示された各特徴及び（該当する場合は）特許請求の範囲及び図面は、個々に、あるいはいずれかの適切な組合せで提供してもよい。特徴は該当する場合、ハードウエア、ソフトウエアまたはその２つの組合せで実装されてもよい。接続は該当する場合は、無線接続または無線接続として実装されてもよく、必ずしも直接または専用接続として実装される必要はない。特許請求の範囲に現れる参照番号は、図示の目的のみであり、特許請求の範囲を限定する効果を有しない。
【図１】
2014518421.tif 000017
【図２】
2014518421.tif 000018
【図３】
2014518421.tif 000019
【図４】
2014518421.tif 000020
【国際調査報告】
2014518421.tif 000021
2014518421.tif 000022
2014518421.tif 000023