JP2015504545A

JP2015504545A - 予測位置符号化

Info

Publication number: JP2015504545A
Application number: JP2014539208A
Authority: JP
Inventors: チャン，ウェンフェイ; カイ，カンイン; マ，テン
Original assignee: Thomson Licensing SAS
Current assignee: Thomson Licensing SAS
Priority date: 2011-11-07
Filing date: 2011-11-07
Publication date: 2015-02-12
Also published as: WO2013067674A1; US20140376827A1; KR20140086998A; US9111333B2; EP2777018A4; EP2777018A1; CN103918009A

Abstract

３次元メッシュモデルの位置符号化をする方法と装置を記載する。該方法は、空でない子セルＣｌ，ｋのシンボル確率を推定する、Ｃｌ，ｋはレイヤｌにあるｋ番目のセルを示すステップであって、前記シンボル確率はフィッティングされた平面Ｐの正確性に基づき推定されるステップと、前記空でない子セルが二以上の頂点を有するとき、前記空でない子セルを分割してサブセルを生成するステップと、レイヤｌに、未処理の空でない子セルがまだあるか判断するステップと、レイヤｌにまだ処理されていない空でない子セルがなければ、レイヤｌのすべての空でない子セルが頂点を１つだけ有し、サブセルの中心とそのサブセル内の点との間の距離が第１の閾値以下であるか判断するステップと、レイヤｌのすべての空でない子セルが頂点を１つだけ有し、サブセルの中心とそのサブセル内の点との間の距離が第１の閾値以下であるとき、前記空でない子セルの位置を表すシンボルをエントロピー符号化するステップと、を有する。

Description

本発明は、３次元モデルに関し、より具体的には、３次元メッシュデータモデルの圧縮と送信及び圧縮された３次元データの受信と復号に関する。

建築設計、化学プラント、機械コンピュータ支援設計（ＣＡＤ）設計などの大規模３次元エンジニアリングモデルが、セカンドライフ（登録商標）やグーグルアース（登録商標）などの様々な仮想世界アプリケーション中にますます多く展開されている。ほとんどのエンジニアリングモデルには、サイズが小さいまたは中くらいの接続されたコンポーネントが多数あり、それぞれが平均して多ければ数百のポリゴンを有している。さらに、これらのタイプのモデルは、様々な位置、スケール、及び方向で繰り返される多数の幾何学的特徴（geometric features）を有する。コンピュータゲーム及びビデオゲームは、動画（映画）産業のように３次元モデルを用いる。映画産業は、アニメ及び現実の動画においてキャラクタ及びオブジェクトとして、３次元モデルを用いる。３次元モデルは医療及び建築でも用いられる。

１９９０年代初頭から３次元メッシュを効率的に圧縮する様々なアルゴリズムが提案されている。しかし、初期の業績はほとんどのものが、なめらかな表面と小さい三角形を有するシングル連結３次元モデルの圧縮に集中していた。大規模３次元エンジニアリングモデルなどのマルチ連結３次元モデルの場合、コンポーネントは別々に圧縮される。これは比較的効率の悪い圧縮となる。実際、圧縮性能は、異なる連結コンポーネント間の冗長性を除去することにより、大きく向上することができる。３次元モデルの圧縮は、動画産業では、消費者へのブロードバンドによる３次元動画の送信及び映画館への送信で非常に重要である。３次元メッシュモデル（例えば、映画、動画）は非常に大量の帯域幅を消費する。

大規模３次元エンジニアリングモデルにおいて繰り返される幾何学的特徴を自動的に発見する方法が非特許文献１で提案されている。しかし、３次元エンジニアリングモデルの圧縮をより効率化する余地は大きい。例えば、繰り返されるインスタンスの変形情報は、原モデルを再生するのに必要であるが、これをカバーする圧縮ソリューションは提供されていない。３次元エンジニアリングモデルが通常有するサイズが大きい連結コンポーネントを考えると、この種の情報も大容量の記憶を消費する。さらに、コンポーネントの頂点位置の主成分分析（ＰＣＡ）を使う場合、ジオメトリが同じだが接続性が異なるコンポーネントは、平均が同じであり、方向軸が同じである。このように、技術水準は、様々なスケールにおける繰り返しパターンの検出には適していない。スケール（すなわち、サイズ）のみが異なる２つのコンポーネントは、同じ等価クラスの繰り返される特徴としては認識されない。さらに、非特許文献１に記載されたものより高い圧縮率を達成することが望ましい。

非特許文献２は、メッシュモデルのすべての連結コンポーネントの平均をエンコードするＫＤツリーベースの圧縮アルゴリズムを記載している。このアルゴリズムは、各繰り返しにおいて、１つのセルを２つの子セルに分割し、頂点の数を２つの子セルの一方にエンコードする。親セルがｐ個の頂点を含む場合、子セルの一方の頂点数は、算術符号化器でｌｏｇ_２（ｐ＋１）ビットを用いてエンコードできる。空でない各セルが十分小さくなり１つだけの頂点を含み、頂点位置を十分正確に再構成できるようになるまで、この分割が反復的に適用される。非特許文献２には、このアルゴリズムは非一様分布の場合に最も効率的であり、規則的分布がワーストケースである。

シンボルがアルファベットのセットまたはシンボルのセットから選択された場合、一連のシンボルは、エントロピー符号化で圧縮できる。エントロピー符号化エンジンは、統計モデル、すなわちシンボルの確率分布に基づいてシンボルにコードワードを割り当てる。一般的に、頻繁に使われるシンボルほど少ないビットでエントロピー符号化され、頻繁に使われないシンボルほど多くのビットでエントロピー符号化される。

エントロピー符号化は数十年にわたり研究されている。エントロピー符号化方には基本的に３つのタイプがある：ハフマン符号化などの可変長符号化（ＶＬＣ）と、算術符号化と、Ｌｅｍｐｅｌ−Ｚｉｖ（ＬＺ）圧縮やＬｅｍｐｅｌ−Ｚｉｖ−Ｗｅｌｃｈ（ＬＺＷ）圧縮などの辞書ベース圧縮とがある。

ＶＬＣコードは、各シンボルを表すのに整数個のビットを用いる。ハフマン符号化が最も広く使われているＶＬＣ法である。ハフマン符号化は、確率がより大きいシンボルに対してより少ないビットを割り当て、確率がより小さいシンボルに対してはより大きなビットを割り当てる。ハフマン符号化は、各シンボルの確率が１／２の整数乗の場合に最適である。算術符号化は、各シンボルに分数個のビットを割り当てることができ、エントロピーにより近くアプローチできる。ハフマン符号化と算術符号化は、ＪＰＥＧ、ＭＰＥＧ−２、Ｈ．２６４／ＡＶＣなどの既存の（ビデオ）圧縮標準で広く使われている。ＬＺとＬＺＷは、繰り返されるデータストリングをテーブルのエントリーで置き換えるテーブルベース圧縮モデルを利用する。ほとんどのＬＺ法では、テーブルはそれ以前の入力データから動的に生成される。例えば、ＧＩＦ、Ｚｉｐ、ＰＮＧなどの標準では、辞書ベースアルゴリズムが利用されている。

密閉３次元モデルのランダムポイント位置及び頂点位置などのジオメトリデータの圧縮には、空間的ツリーベースアプローチを利用できる。密閉３次元モデル（watertight ３D model）は、頂点が均一かつ密に分布したモデルである。空間的ツリーベースアプローチは、八分木またはＫＤツリーにより入力された空間点を組織化する。ツリーをトラバースし、ツリーの再生に必要な情報を記憶する。

最初、３次元モデルのすべての点の周りに境界ボックスを構成する。すべての３次元点の境界ボックスは、最初、１つのセルと見なされる。空間的ツリーを構成するため、空でない各セルが十分小さくなり１つだけの頂点を含み、頂点位置を十分正確に再構成できるようになるまで、セルは反復的に分割される。頂点位置は対応セルの中心座標から再生できるので、空間的ツリーベースアルゴリズムは、シングル解像度圧縮アルゴリズムと同じ圧縮比でマルチ解像度圧縮を実現できる。

図１は、２次元の場合のＫＤツリー符号化の原理を示す。２次元モデルを境界ボックス１０で囲む。これを親セルと呼ぶ。７つの頂点が親セル中に位置している。ＫＤツリー符号化アルゴリズムは、所定数のビットを用いて頂点の総数を符号化し、その後、セルを再帰的に分割する。このアルゴリズムは、１つの親セルを２つの子セルに分割するたびに、頂点の数を２つの子セルの一方にエンコードする。習慣的に、これは（垂直スプリット後の）左の子セルか、または（水平スプリット後の）上の子セルとする。親セルがｐ個の頂点を含む場合、子セルの一方の頂点数は、算術符号化器でｌｏｇ_２（ｐ＋１）ビットを用いてエンコードできる。空でない各セルが十分小さくなり１つだけの頂点を含み、頂点位置を十分正確に再構成できるようになるまで、この分割を反復的に適用する。すべての繰り返しインスタンスの位置を圧縮する場合、すべての位置の境界ボックス１０全体は、始め、親セルと見なされる。図１の例では、頂点の総数（７つ）は３２ビットを用いてエンコードされる。次に垂直スプリットを適用し、左の子セルＶ１と右の子セルＶ２が得られる。次のコーディングステップにおいて、左の子セルＶ１中の頂点数は、４であるが、これがエンコードされる。エンコードに用いられるビット数は、親セル中の頂点数により決まる：この例では、ｌｏｇ_２（７＋１）＝３ビットである。右の子セルＶ２中の頂点数は、親セル中の頂点数と左の子セルＶ１中の頂点数から求められるので、エンコードする必要はない。

次のステップにおいて、水平スプリットを適用する。左の子セルＶ１は、ここで親セルＶ１となるが、上の子セルＶ１Ｈ１と下の子セルＶ１Ｈ２にスプリットされる。右の子セルＶ２は、ここで親セルＶ２となるが、上の子セルＶ２Ｈ１と下の子セルＶ２Ｈ２にスプリットされる。符号化を、上の左子セルＶ１Ｈ１に続ける。これは２つの頂点を有する。そこで、次に数２がエンコードされ、算術コーダでｌｏｇ_２（４＋１）＝２．３ビットを用いる。上記の通り、下の左子セルＶ１Ｈ２中の頂点数はエンコードする必要がない。左セルＶ１中の頂点数と上の左子セルＶ１Ｈ１中の頂点数から求められるからである。次に、同じ手順を右セルＶ２に適用し、２ビットを用いてゼロをエンコードする結果となる。図１に示したように、各頂点が別々のセルに入るまでには、もう２回のスプリットステップが必要であり、各頂点がそのセル中に十分ローカライズされるまでには、より多くのステップが必要である。各ステップは、ますます多くの１または０をエンコードする必要がある。必要な精度に応じて、追加ステップ数は多くなり得る。

他方、八分木ベースアプローチは、各繰り返しにおいて、空でないセルを８つの子セルに分割する。説明を容易にするため、四分木を説明する２次元の例を図２及び図３に示す。トラバースの順序（traversal orders）を矢印で示す。エンコードするため、現在の親セルを４つの子セルにスプリットし、所定順序でトラバース（travers）し、１子セルにつき１ビットがその子セル中に点があるか否かを示す。例えば、図２において、２つの親セル１と２の子セルが矢印で示したようにトラバースされる。空でない子セルは灰色になっている。第１の親セル１の子セル２１０，２１１，２１２及び２１３は、第１のシーケンス「１０１０」で表される。トラバースした第１と第３の子セル２１０と２１２は空でない（すなわち、一以上の点を含む）ので、「１」で示されている。第２と第４の子セル２１１と２１３は空である（すなわち、点を含まない）ので、「０」で示されている。図３は、同じセルであるが、用いるトラバースが異なり、結果として得られるシーケンスも異なることを示している。

図４は八分木の親セル及び子セルを示す。八分木方式では、親セルは８つの子セル４０、・・・、４６にスプリットされる（下の左セル４２の後ろの子セルは隠れており、図示されていない）。可能性のある一トラバース順序は、左右、上下、及び前後であり、その結果、トラバース順序は、セル４０−４１−４２−４３−４４−４５−（下の左セル４２の後の隠れているセル）−４６となる。それに応じて、八分木の場合には、空でない子セル構成が８ビットの二進数により示され、空の及びからでない子セルの可能性のある２５５通りの組み合わせをカバーする。空でない子セルの数を別にエンコードする必要はない。表１はシーケンスの一例である。

シーケンス例

留意点として、親セルにおける子セルの具体的なトラバース順序は、本実施形態にはあまり関係がない。原理的に、本実施形態ではどのトラバース順序（traversal order）を用いることもできる。以下、子セル構成を表すのに使われるビットストリングをシンボルとして示す。表１の例では、各シンボルに８ビットを用いる。他の実施形態では、シンボル中のビット数は可変であってもよい。例えば、４ビットストリングを用いて四分木の子セル構成を表すので、図２の例のシンボルのビット数は４である。

図５は、八分木構造の例を示す。各ノードはシンボルに関連し、各レイヤはツリー表現のある精度に対応している。最初のセルは８つのセルに分割される。子セル１，２，５，６及び７はより多くの頂点を含み、子セル３，４及び８は空であり、その結果、８ビットシンボル１１００１１１０（５１０）がレイヤ０の子セル構成を表す。空でない各子セルは、さらに、分割され、対応する子セル構成がレイヤ１に表される。分割は、空でない各セルが１つの頂点のみを含むようになるまで続けられる。

確率分布例

八分木の幅優先トラバースを用いて、３次元メッシュの頂点位置を一連のシンボルに整理できる。図５の例では、一連のシンボルは、１１００１１１０、１１００００００、１００１０１００、００１００１１０、００００１０００、及び００００１０００になる。

複雑な３次元モデルにおいて最も頻出するシンボルの確率分布を、確率の降順で表２に示す。表２から分かるように、バイナリ表現において「１」を１つだけ含むシンボルが、最も支配的な確率（＞９３％）で発生する。幾何学的に説明すれば、何回か分割すると、複数の頂点が同じセルに入ることはほとんど無いということである。すなわち、八分木の下位レイヤでは、「１」を１つだけ有するシンボルが支配的であり、上位レイヤでは、そうでないシンボルがより多い。

本実施形態では、２つのシンボルセットを定義する：可能性のあるすべてのシンボルを含むユニバーサルシンボルセットＳ０＝｛１，２，３，・・・，２５５｝と、「１」を１つだけ含むシンボル、すなわち最頻出のシンボルのみを含むシンボルセットＳ１＝｛１，２，４，８，１６，３２，６４，１２８｝。表現を容易にするため、８ビットバイナリストリングを１０進数として記した。シンボルは、シンボルセットS１に属するとき、S１シンボルと呼び、そうでなければ非S１シンボルと呼ぶ。

八分木の統計的特性を利用するため、特許文献１は、八分木で表されたシーケンスをS０またはS１で適応的に符号化された複数のサブシーケンスにパーティショニングすることを提案している。サブシーケンス境界のインデックスは補助情報として符号化される。補助情報のオーバーヘッド（例えば、各インデックスに対して２バイト）が必要なため、概して、S１シンボルが連続するサブシーケンスはシンボルセットS１で符号化される。

シーケンスの一部にS１シンボルと非S１シンボルが両方ともあり、S１シンボルの確率がより大きいとき、かかる部分を複数のサブシーケンスに分割することは、オーバーヘッドの点から効率的ではない。他方、かかる部分をシンボルセットS０で符号化することも、非S１シンボルの確率が低いので、効率的ではない。

３次元メッシュ符号化では、ジオメトリデータは、普通は、空間的ツリー分解ベースアプローチ、例えば非特許文献２に記載されたＫＤツリーベースアプローチ、または非特許文献３及び非特許文献４に記載された八分木ベースアプローチにより圧縮される。非特許文献２、３及び４に記載された方法は、プログレッシブコーディングをサポートしている他に、大きな圧縮利得も達成している。これらのコーダは、３次元モデルの座標軸に平行な最小境界ボックスを、ＫＤツリーデータ構造または八分木データ構造のそれぞれ２つまたは８つの子に繰り返し分割する。空でない各セルが十分小さくなり１つだけの頂点を含み、頂点位置を十分正確に再構成できるようになるまで、セルを繰り返し分割する。各セル分割に対して、各子セルが空であるか否か、シンボルにより示す。ＫＤツリーまたは八分木を記述するシンボルシーケンスは、ここではトラバースシンボルシーケンス（traversal symbol sequences）と呼ぶが、八分木を幅優先トラバースして、出会ったノードの分割を表すシンボルを集めて生成される。次に、エントロピーコーダ・デコーダ（コーデック）を用いてそのシンボルシーケンスを圧縮する。シンボルシーケンスのエントロピーを減らして、符号化効率を高めるために、非特許文献３、４は両方とも、いくつかの近傍ベースプレディクタに基づき、子セル再配列（child-cell reordering）を実行する。

各セル分割において、非特許文献３では、空でない子セルの数Ｔ（１≦Ｔ≦８）と、可能なすべての組み合わせ中の空でない子セル構成のインデックスとをエンコードする。ジオメトリ情報は、空でない子セルの表現中に考慮され、圧縮率は良くなるが、複雑性が高くなってしまう。

特許文献２及び３は、空でない子セルの数Ｔを捨てることを提案している。その場合、空でない子セルの構成は、２５５通りすべての組み合わせをカバーしている８ビットのバイナリ数により示される。これらの８ビット二進数はエントロピー符号化により圧縮される。

特許文献２と特許文献３で提案されている統計ベースアプローチによれば、非特許文献２と非特許文献３よりも、ランダム分布した位置の符号化において、計算の複雑性がずっと低くなりロバスト性が良くなる。密閉３次元モデルの頂点圧縮は、この逆である。その理由は、特許文献２と特許文献３では、ジオメトリ冗長性を除去せず、これがビット的な大きなコストになるからである。

PCT出願第PCT/CN２０１１/０７７２７９号（発明の名称「A Model- Adaptive Entropy Coding Method for Octree Compression」 PCT/CN2011/077279 PCT/CN2011/078936

D. Shikare, S. Bhakar and S. P. Mudur, "Compression of Large 3D Engineering models Using Automatic Discovery of repeating geometric Features", 6th International Fall Workshop on Vision, Modeling and Visualization (VMV2001), November 21 - 23, 2001, Stuttgart, Germany O. Devillers, P. Gandoin, "Geometric Compression for Interactive transmission", in IEEE Visualization, 2000, pp. 319 - 326 J. L. Peng, C. C. Jay Kuo, "Geometry Guided Progressive Lossless 3D Mesh Coding with Octree Decomposition", ACM SIGGRAPH (ACM Transactions on Graphics 24 (3)), pp 609 - 616, 2005 Y. Huang, J. Peng, C. C. J. Kuo, and M. Gopi, "A Generic Scheme for Progressive Point Cloud Coding", IEEE Transactions on Visualization and Computer Graphicsl4, pp 440 - 453, 2008

本発明は、位置符号化ための確率予測をインプリメントする。統計的符号化では、重み付き３次元モデルの頂点位置における冗長性を効果的に取り除くことができない。本発明は、位置符号化の差異のジオメトリ上の特徴を利用する。３次元モデルの八分木を構成するとき、空でない子セル構成の確率を、３次元モデルの表面のなめらかさに基づき、各セルについて予測する。エントロピーコーデックが、頻繁に生じるコード値（例えば、０１００）に対して短いコードワードを割り当て、及びその逆である。例えば、０１００の確率が５０％であるとき、短いコードワード（約−ｌｏｇ_２（０．５）＝１ビット）を割り当てる。０１１０の確率が１２．５％であるとき、長いコードワード（約−ｌｏｇ_２（０．１２５）＝３ビット）を割り当てる。このように、入来コード値が確率が高いシンボルとして予測される場合、対応するコードワードは通常は短い。確率が幾何学的相関に基づくので、ジオメトリ的冗長性が実際に取り除かれる。このように、空間的冗長性を効率的に取り除き、高い圧縮率を実現する。

３次元メッシュモデルの位置符号化をする方法と装置を記載する。該方法は、空でない子セルＣ_ｌ，ｋのシンボル確率を推定する、Ｃ_ｌ，ｋはレイヤｌにあるｋ番目のセルを示すステップであって、前記シンボル確率はフィッティングされた平面Ｐの正確性に基づき推定されるステップと、前記空でない子セルが二以上の頂点を有するとき、前記空でない子セルを分割してサブセルを生成するステップと、レイヤｌに、未処理の空でない子セルがまだあるか判断するステップと、レイヤｌにまだ処理されていない空でない子セルがなければ、レイヤｌのすべての空でない子セルが頂点を１つだけ有し、サブセルの中心とそのサブセル内の点との間の距離が第１の閾値以下であるか判断するステップと、レイヤｌのすべての空でない子セルが頂点を１つだけ有し、サブセルの中心とそのサブセル内の点との間の距離が第１の閾値以下であるとき、前記空でない子セルの位置を表すシンボルをエントロピー符号化するステップと、を有する。

添付した図面を参照して以下の詳細な説明を読めば、本発明を最もよく理解することができる。図面には以下に簡単に説明する図が含まれている：
２次元の場合におけるＫＤツリーベースのジオメトリコーディングを示す図である。２次元の場合の四分木ベースのジオメトリコーディングを示す図である。２次元の場合の四分木ベースのジオメトリコーディングを示す図である。セルパーティショニングを示す図である。八分木の一例を示す図である。四分木構成で用いられるトラバース順序を示す図である。四分木構成の場合の２次元空間の階層的分割を示す図である。四分木構成の場合の、図６Ｂに示した階層的２次元分割から得られる四分木シンボルを示す図である。連結情報がある場合の、２次元位置予測の一例を示す図である。連結情報がない場合の、２次元位置予測の一例を示す図である。本発明の原理による実施形態の予測位置符号化方法の一実施形態を示すフローチャートである。図８のステップ８０５を示す拡大図である。本発明の原理による本発明の予測位置復号方法の一実施形態を示すフローチャートである。図９のステップ９０５を示す拡大図である。本発明の原理による予測位置符号化を含むデバイスの一実施形態を示すブロック図である。本発明の原理による予測位置復号を含むデバイスの一実施形態を示すブロック図である。

例示を目的として、四分木を構成するプロセスを図６Ａないし図６Ｃに示す。図６Ａは、四分木構成で用いられるトラバース順序を示す図である。図６Ｂは、四分木構成の場合の２次元空間の階層的分割を示す図である。小さい黒い四角形は符号化する点を示す。図６Ｂの一番左の四分木では、平面をサイズが等しい４つのサブセルに分割している。各サブセルは少なくとも１つの点を含むので、空でない、対応する子セル構成は１１１１である。図６Ｂの真ん中の四分木では、各サブセルをさらに４つのサブセルに分割し、空でない子セル構成を符号化しており、例えば、図６Ｂ中、サブセル「ＴＬ」の右下の子セルのみが点を含む。よって、対応する空でない子セル構成は００１０である。続いて図６Ｂの一番右の四分木では、セルは繰り返し分割され、空でない子セル構成がエンコードされる。図６Ｃは、四分木構成の場合の、図６Ｂに示した階層的２次元分割から得られる四分木シンボルを示す図である。四分木は図６Ｃに示したように構成される。各レイヤは繰り返される１回の分割に対応する。

本発明は、規則的に分布した頂点の位置を効率的に圧縮する。本発明には４つのキーポイントがある：
１．空でない子セル構成のシンボル確率を、各子セルの中心と、隣接するセルの中心点をフィッティングして求めた平面との間の距離を用いて計算する。
２．空でない子セル構成のシンボル確率を、幾つかの子セルの中心点と、隣接するセルの中心点とにより形成される凸形状ハル（convex hull）の表面積の値である距離尺度で計算する。
３．コーデックは、セルに平面をフィッティングするため、連結情報が利用できれば、少なくとも１つの頂点が現在のセル中の複数の頂点のうちの一頂点と接続されているセルの中心点を用いる。
４．コーデックは、セルに平面をフィッティングするため、連結情報が利用できないとき、少なくとも１つの頂点を含む複数の隣接セルの中心点を用いる。
５．予測した確率を、フィッティング平面の正確性に基づいて調整する。例えば、フィッティングエラーが小さければ、確率を、予測値として厳密に設定する。そうでなければ、確率を、一様分布に近く設定する。フィッティングエラーの閾値を、設定パラメータとして設定してもよい。閾値を設定した場合、その閾値を用いて、フィッティングエラーが大きいかまたは小さいか、それゆえシンボル確率を調整するか、判断する。

説明を容易にするため、本発明の位置予測方法を２次元の例を用いて説明する。２次元の場合、平面フィッティングはラインフィッティングになる。図７Ａと図７Ｂは、２次元空間中の凸分布の一例を示す。図７Ａは、連結情報がある場合の、２次元位置予測の一例を示す図である。図７Ｂは、連結情報がない場合の、２次元位置予測の一例を示す図である。

Ａ：
既知の連結情報で、簡単な方法で隣接セルを求めることができる。子セルは、フィッティング平面に近ければ近いほど、空でない確率が高い。この尺度から分かることは、子がフィッティング平面に近ければ近いほど、現在の子セルの中心点と、すべての隣接セルの中心点とにより形成される凸形状ハルの表面積は小さい。この凸形状ハルは、複雑性がｏ（ｎｌｏｇｎ）である標準的アルゴリズム（グラハムスキャンなど）により計算できる。このハルを取得すると、予備的な幾何学的方法により、表面積を容易に計算できる。子セルｐ，ｑ，ｒ及びｓについて、この面積尺度はｄｉｓｔ_ｋにより表される。ここで、ｋ＝ｐ，ｑ，ｒ，ｓである。

Ｂ：
図７Ａでは、連結情報が利用できる。頂点の連結の仕方が分かれば、各レイヤにおけるサブセルの連結を計算できる。図７Ａに示したように、頂点はセルＣ（ｉ，ｊ）の子セルｑにあり、すなわち、四分木シンボルは図６Ａのトラバース順序を用いると、０１００である。セルＣ（ｉ，ｊ）は、セルＣ（ｉ−２，ｊ−１），Ｃ（ｉ＋２，ｊ），Ｃ（ｉ＋２，ｊ＋１）と連結していることが分かっている。これらのセルを含むセルセットＳｃを定義する。Ｓｃ中のセルの中心座標に基づき、セルセットＳｃ中の点に直線をフィットさせ、ラインＬを得る。このラインを記述する関数はａｘ＋ｂｙ＋ｃ＝０と表せる。

図７Ｂでは、連結情報が利用できない。図７Ｂに示したように、頂点はセルＣ（ｉ，ｊ）の子セルｑにあり、すなわち、四分木シンボルは図６Ａのトラバース順序を用いると、再び０１００である。曲線は実際の縁を表す。セルＣ（ｉ−１，ｊ−１），Ｃ（ｉ，ｊ−１），Ｃ（ｉ＋１，ｊ），Ｃ（ｉ＋１，ｊ＋１）及びＣ（ｉ，ｊ）に頂点があることが分かる。これらのセルはセルセットＳｃに含まれ、セルセットＳｃ中の点の中心座標に基づき直線がフィッティングされ、ラインＬが得られる。このラインを記述する関数はａｘ＋ｂｙ＋ｃ＝０と表せる。

以前提案された方法は、空でない子セル構成シンボル（０００１，００１０，０１００，１０００）に等しい確率を割り当てた。本発明は、フィッティングされたラインと子セルｐ，ｑ，ｒ及びｓの中心点との間の距離に基づき、適応的に、等しくない確率を割り当てる。子セルの中心点をｋ（ｘ_ｋ，ｙ_ｋ）とし、フィッティングしたラインへのその距離をｄｉｓｔ_ｋｋ＝ｐ，ｑ，ｒ，ｓ，とすると、

ここで、ｓｉｚｅは分割するセルの幅である。
式（１ａ）または（１ｂ）で求めたｄｉｓｔ_ｋの値に基づき、確率は次式で計算できる：

ｐｒｏｂ_ｋは子セルｋに頂点がある確率であり、ｕは後で説明するパラメータである。

図７Ａと図７Ｂから分かるように、ラインＬと子セルｑの中心座標との間の距離は、すべての子セルの中で最小であり、シンボル０１００の確率は最大値に設定される。その結果、この分割（０１００）のシンボルのビットコストを小さくする。

空でない子セル構成シンボルは０００１，００１０，０１００及び１０００だけではない。セル構成シンボル０００１，００１０，０１００及び１０００は、空でない子セルに１つの頂点だけの場合である。複数の頂点がセルにある場合の確率はどうだろう？例えば、シンボル０１１１を考えると、これは子セルｑ、ｒ及びｓにそれぞれ３つの頂点があることを意味する。この場合の重みをｗｅｉｇｈｔ_ｑｒｓとすると、

このような場合はほとんど起こらず、ｗｅｉｇｈｔ_ｑｒｓはまだ大きすぎるので、重みをスケールし直す。コーデックは、現在のレイヤ中の単一頂点シンボル（０００１，００１０，０１００及び１０００）と複数頂点シンボルの確率を推定する。各シンボルの重みに、対応する推定確率をかける。最終的に、対応する重みを規格化して、式（２）のように、各シンボルの確率を求める。

フィッティングの正確性をチェックするため、フィッティングしたラインＬと、Ｓｃ中のセルの中心点との間の距離を計算する。Ｓｃ中のセルがｃ_ｋ（ｘ_ｋ、ｙ_ｋ）ｋ＝１〜ｎとすると、

ｕはフィッティングの正確性を表す。ｕの値が大きいことは、フィッティングエラーが小さいことを示す。式（３）で計算される確率は信頼性がより高い。ｕの値が小さいことは、フィッティングエラーが大きいことを示す。そうすると、式（３）で計算される確率は信頼性がより低い。式（２）でｕの値を考慮すると、ｕが大きくなるにつれ、確率関数は一様分布に近づく。フィッティングエラーの閾値を、設定パラメータとして設定してもよい。閾値を設定した場合、その閾値を用いて、フィッティングエラーが大きいかまたは小さいか、それゆえシンボル確率を調整するか、判断する。

３次元では、本発明の予測位置符号化に、例示したラインフィッティングではなく、プレーンフィッティングを用いる。頂点の３次元位置を表すため、コーデックは八分木を構成して、サブセルの占有状態（occupancy）を示す。各分割に対して、問題となる頂点に隣接する子セルの頂点と平面をフィッティングする。３次元の場合、点の位置（問題となる頂点）をｃ（ｉ，ｊ，ｋ）の形式で示し、フィッティングした平面の関数をａｘ＋ｂｙ＋ｃｚ＋ｗ＝０の形式で示す。正確性の次に、フィッティングした平面をチェックして、パラメータｕを求める。式（５）は次式に拡張される、

最後に、空でない子セル構成の異なる複数のシンボルの確率を設定する。求めた確率モデルを、実際の空でない子セル構成のエントロピー符号化に適用する。

図８は、本発明の原理による実施形態の予測位置符号化方法の一実施形態を示すフローチャートである。セルカウンタを初期化する。ステップ８０５において、Ｃ_ｌ，ｋの空でない子セル構成の予測を計算する。ここで、Ｃ_ｌ，ｋはレイヤｌにあるｋ番目のセルを示す。ステップ８１０において、セルを再度分割する。ステップ８１５において、セルカウンタ（ｋ）をインクリメントする。ステップ８２０において、現在のレイヤにまだ処理されていないセルがあるか判断するテストを行う。まだ処理されていないセルがあれば、処理はステップ８０５に進む。処理されていないセルがもう無ければ、ステップ８２５において、エントロピーエンコーダにより、最深レイヤの空でないすべての子セルが多くても１つの点（頂点）を含むか、及びサブセルの中心とサブセルｖ_ｌ，ｋ内の点との間の距離が最大許容エラー以下であるか判断するテストを行う。ここで、最大許容エラーはｔｈであり、ｃ_ｌ，ｋはＣ_ｌ，ｋの中心点である。最深レイヤにあるすべてのセルが多くても１つの点（頂点）を含み、サブセルの中心と、そのサブセルｖ_ｌ，ｋ中の点との間の距離が許容最大エラー以下であれば、ステップ８３０において、空でない子セルシンボルを符号化する。最深レイヤにあるすべてのセルが、多くとも１つの点（頂点）を含まないか、サブセルの中心と、そのサブセルｖ_ｌ，ｋ中の点との間の距離が、最大許容エラーより大きい場合、ステップ８３５において、セルカウンタ（ｋ）を再初期化し、レイヤカウンタ（ｌ）をインクリメントする。処理はステップ８０５に進む。ステップ８０５，８１０，８１５，８２０及び８３５は、基本的に、上記の平面フィッティングである。ステップ８２５は、上記の平面フィッティングの正確性であり、ステップ８３０は、確率を設定するステップと、求めた確率にエントロピー符号化を適用するステップとを含む。

図８Ａは、図８のステップ８０５を示す拡大図である。ステップ８４０において、レイヤｌに１つの「１」のみを有する空でない子セルの確率を、確率ｐｒｏｂ１とする。ステップ８４５において、連結情報が得られるか判断するテストを行う。連結情報が得られる場合、ステップ８５０において、現在のセルに連結された複数のセルの中心座標を用いて、平面Ｐをフィッティングする。ステップ８５５において、空でない子セルのシンボル確率を、サブセルの中心座標と、フィッティングした平面との間の距離に基づき、予測する。「１」を１つだけ有する空でない子セル（例えば、１０００００００，０１００００００．．．）の確率にｐｒｏｂ１をかける。「１」を複数有する空でない子セル（例えば、１１００００００，０１０００１００．．．）の確率に（１−ｐｒｏｂ１）をかける。ステップ８６０において、フィッティングの正確性をチェックし、推定確率を適宜調整する。フィッティングエラーが小さい（正確性が高い）とき、予測したシンボル確率は調整しない。フィッティングエラーが大きい（正確性が低い）とき、予測したシンボル確率を一様分布に近く設定する。連結情報が得られない場合には、ステップ８６５において、隣接する空でないセルの中心座標を用いて平面Ｐをフィッティングする。

復号プロセスは基本的に符号化プロセスの逆である。符号化されたシンボルは、シアターまたは消費者デバイスで受け取られ、すべてのシンボルが復号されるまで、予測された確率に基づき、レイヤごとに、一つずつ復号される。符号化されたシンボルは、処理の前または後に、記憶手段に記憶されてもよい。シンボルが復号されると、消費者デバイスにおいてまたはシアターでレンダリングするため、３次元メッシュモデルが再生される。再生された３次元メッシュモデルは、レンダリング前に記憶手段に記憶されてもよい。

図９は、本発明の原理による本発明の予測位置復号方法の一実施形態を示すフローチャートである。セルカウンタを初期化する。ステップ９０５において、受信デバイスにおいて、符号化されたシンボルが予測される。符号化されたシンボルは、処理の前または後に、記憶手段に記憶されてもよい。受け取った（符号化された）空でない子セル構成のシンボルは、ステップ９１０において、予測された確率に基づき復号される。ステップ９１５において、セルＣ_ｌ，ｋは、復号された構成により分割される。ステップ９２０において、セルカウンタ（ｋ）をインクリメントする。ステップ９２５において、このレイヤにまだ処理されていないセルがあるか判断するテストを行う。このレイヤにまだ処理されていないセルがあれば、処理はステップ９０５に進む。このレイヤにまだ処理されていないセルがあれば、ステップ９３０において、最低、八分木を受け取ったか判断するテストを行う。最低、八分木が受け取られていれば、ステップ９３５において、レンダリングするため、３次元メッシュモデルを再生する。再生された３次元メッシュモデルは、レンダリング前に記憶手段に記憶されてもよい。最低、八分木が受け取られていなければ、ステップ９４０において、レイヤカウンタ（ｌ）をインクリメントし、セルカウンタ（ｋ）を再初期化する。処理はステップ９０５に進む。

図９Ａは、図９のステップ９０５を示す拡大図である。ステップ９４０において、レイヤｌに１つの「１」のみを有する空でない子セルの確率を、確率ｐｒｏｂ１とする。ステップ９４５において、連結情報が得られるか判断するテストを行う。連結情報が得られる場合、ステップ９５０において、現在のセルに連結された複数のセルの中心座標を用いて、平面Ｐをフィッティングする。ステップ９５５において、空でない子セルのシンボル確率を、サブセルの中心座標と、フィッティングした平面との間の距離に基づき、予測する。「１」を１つだけ有する空でない子セル（例えば、１０００００００，０１００００００．．．）の確率にｐｒｏｂ１をかける。「１」を複数有する空でない子セル（例えば、１１００００００，０１０００１００．．．）の確率に（１−ｐｒｏｂ１）をかける。ステップ９６０において、フィッティングの正確性をチェックし、推定確率を適宜調整する。フィッティングエラーが小さい（正確性が高い）とき、予測したシンボル確率は調整しない。フィッティングエラーが大きい（正確性が低い）とき、予測したシンボル確率を一様分布に近く設定する。連結情報が得られない場合には、ステップ９６５において、隣接する空でないセルの中心座標を用いて平面Ｐをフィッティングする。

図１０は、本発明の原理による予測位置符号化を含むデバイスの一実施形態を示すブロック図である。ここで図１０を参照して、データ送信システムまたは装置１０００を示す。これに対して上記の特徴及び原理を適用できる。データ送信システムまたは装置１０００は、例えば、衛星、ケーブル、電話線、または地上波放送などの様々な媒体を用いて信号を送信するヘッドエンドまたは送信システムであり得る。データ送信システムまたは装置１０００を用いて、例えば、記憶する信号を提供する。送信はインターネットまたはその他のネットワークにより提供できる。データ送信システムまたは装置１０００は、例えば、ビデオコンテンツ、及び例えば３次元メッシュモデルなどその他のコンテンツを生成及び配信できる。

データ送信システムまたは装置１０００は、プロセッサ１００５から、処理されたデータ及びその他の情報を受け取る。一実装では、プロセッサ１００５は、３次元メッシュモデルのジオメトリデータを処理して、一連のシンボルを生成する。プロセッサ１００５は、例えば、八分木のツリーデータ構造をいかにパーツ及びその他の情報に分割するか示すメタデータを装置１０００に提供する。

データ送信システムまたは装置１０００は、符号化した信号を送信するエンコーダ１０１０及びトランスミッタ１０１５を含む。エンコーダ１０１０は、プロセッサ１００５からデータ情報を受け取る。エンコーダ１０１０は、符号化された信号を生成する。エンコーダ１０１０のエントロピー符号化エンジンは、例えば、算術コーダまたはハフマンコーダである。

エンコーダ１０１０は、サブモジュールを含み、これには例えば様々な情報を受け取り、記憶や送信のために構造化されたフォーマットにアセンブルするアセンブリユニットが含まれる。様々な情報には、例えば、符号化されたまたはされていないビデオ、符号化されたまたはされていないサブストリーム長さインジケータやシンタックスエレメントなどの要素が含まれる。幾つかの実装では、エンコーダ１０１０は、プロセッサ１００５を含み、それゆえプロセッサ１００５の動作を実行する。エンコーダ１０１０は、図８及び図８Ａを参照して上で説明した原理により動作する。

トランスミッタ１０１５は、エンコーダ１０１０から符号化された信号を受け取り、その符号化された信号を一以上の出力信号で送信する。トランスミッタ１０１５は、例えば、符号化された画像を表す一以上のビットストリーム及び／またはそれに関する情報を有するプログラム信号を送信するように構成されている。典型的なトランスミッタは、例えば、エラー補正コーディングの提供、信号中のデータのインターリーブ、信号中のエネルギーのランダム化、モジュレータ１０２０を用いた信号の一以上のキャリアへの変調などのうち一以上の機能を実行する。トランスミッタ１０１５は、アンテナ（図示せず）を含み、またはアンテナとインタフェースする。さらに、トランスミッタ１０１５の実装はモジュレータ１０２０に限定されてもよい。

また、データ送信システムまたは装置１０００は、ストレージユニット１０２５に通信可能に結合している。一実装では、ストレージユニット１０２５は、エンコーダ１０１０に結合し、エンコーダ１０１０からの符号化されたビットストリームを記憶する。他の一実装では、ストレージユニット１０２５は、トランスミッタ１０１５に結合し、トランスミッタ１０１５からのビットストリームを記憶する。トランスミッタ１０１５からのビットストリームは、例えば、一以上の符号化され、トランスミッタ１０１５によりさらに処理されたビットストリームを含み得る。別の実装においては、ストレージユニット１０２５は、標準的ＤＶＤ、ブルーレイディスク、ハードドライブ、その他の等価なストレージデバイスのうちの一以上である。

図１１は、本発明の原理による予測位置復号を含むデバイスの一実施形態を示すブロック図である。ここで図１１を参照して、データ受信システムまたは装置１１００を示す。これに対して上記の特徴及び原理を適用できる。データ受信システムまたは装置１１００は、例えば、ストレージデバイス、衛星、ケーブル、電話線、地上波放送などの様々なメディアにより信号を受信するように構成されている。信号はインターネットまたはその他のネットワークにより受信できる。

データ受信システムまたは装置１１００は、例えば、セルラー電話、コンピュータ、セットトップボックス、テレビジョン、またはその他のデバイスであって符号化ビデオを受信し、例えば復号されたビデオ信号を表示（ユーザへの表示など）、処理、または記憶のために提供するものであり得る。データ受信装置１１００は、シアターの機器であって、シアターの観客に対してレンダリングする信号を受信するものであってもよい。このように、データ受信システムまたは装置１１００は、その出力を、例えば、テレビジョン、コンピュータモニタ、（記憶、処理または表示用の）コンピュータ、その他の等価な記憶、処理または表示デバイスのスクリーンに供給する。

データ受信システムまたは装置１１００は、データ情報が例えば３次元メッシュモデルを含む場合、そのデータ情報を受信して処理できる。データ受信システムまたは装置１１００は、例えば、本願の実施形態で説明した信号などの符号化された信号を受信するレシーバ１１０５を含む。レシーバ１１０５は、例えば、３次元メッシュモデル及び／またはテクスチャ画像のうちの一以上、または図１０のデータ送信システムからの信号出力を受信できる。

レシーバ１１０５は、例えば、符号化された画像を表す複数のビットストリームを有するプログラム信号を受信するように構成されている。典型的なレシーバは、例えば、符号化され変調されたデータ信号の受信、デモジュレータ１１１０を用いた一以上のキャリアからのデータ信号の復調、信号中のエネルギーのデ・ランダム化、信号中のデータのデ・インターリーブ、及び信号のエラー訂正復号のうちの一以上の機能を実行する。レシーバ１１０５は、アンテナ（図示せず）を含み、またはアンテナとインタフェースする。レシーバ１１０５の実装はデモジュレータ１１１０に限定されてもよい。

データ受信システムまたは装置１１００は、デコーダ１１１５を含む。レシーバ１１０５は、受信した信号をデコーダ１１１５に供給する。レシーバ１１０５によりデコーダ１１１５に供給される信号は、一以上の符号化ビットストリームを含む。デコーダ１１１５は、例えば、ビデオ情報を含む復号ビデオ信号などの復号信号を出力する。デコーダ１１１５は、図９及び図９Ａを参照して上で説明した原理により動作する。

また、データ受信システムまたは装置１１００は、ストレージユニット１１２０に通信可能に結合している。一実施形態では、ストレージユニット１０２０はレシーバ１１０５に結合され、レシーバ１１０５はストレージユニット１１２０からのビットストリームにアクセスする。他の一実施形態では、ストレージユニット１０２０はデコーダ１１１５に結合され、デコーダ１１１５はストレージユニット１１２０からのビットストリームにアクセスする。ストレージユニット１０２０からアクセスされるビットストリームは、別の実施形態では、一以上の符号化されたビットストリームを含む。別の実装においては、ストレージユニット１１２０は、標準的ＤＶＤ、ブルーレイディスク、ハードドライブ、その他の等価なストレージデバイスのうちの一以上である。

デコーダ１１１５からの出力データは、一実施形態では、プロセッサ１１２５に供給される。プロセッサ１１２５は、一実施形態では、３次元メッシュモデル再構成を行うように構成されたプロセッサである。幾つかの実装では、デコーダ１１１５は、プロセッサ１１２５を含み、それゆえプロセッサ１１２５の動作を実行する。他の実施形態では、プロセッサ１１２５は、ダウンストリームデバイスの一部であり、例えば、セットトップボックス、テレビジョン、または映画館におけるその他の機器（デバイス、装置）などである。

特定の機能と態様を有する一以上の実装を提供する。具体的に、エントロピー符号化及び復号に関する複数の実施形態を提供する。予測位置エントロピー符号化及び復号は、様々なアプリケーションに適用できる。例えば、３次元メッシュのジオメトリデータの圧縮、ランダムな２次元座標、及び統計的に可変なデータソースなどに適用できる。しかし、これらの実施形態のバリエーション及び追加的アプリケーションを想定でき、本願の範囲ないであり、説明した実施形態の特徴と態様は他の実施形態に合わせることができる。

本願で説明した実施形態と特徴の一部は、ＭＰＥＧ３ＤＧＣ標準及びその拡張版のコンテキストで用いることができる。また、これらの実施形態や特徴は、（既存または将来の）他の標準のコンテキストで用いてもよいし、標準化を伴わないコンテキストで用いられてもよい。

また、本願とその特許請求の範囲において、様々な情報を「判断（determining）」する旨を記載した。情報の判断には、例えば、その情報の推定、その情報の計算、その情報の予測、またはその情報のメモリからの読み出しのうちの一以上が含まれ得る。

また、多くの実施形態は、エンコーダ（例えば、エンコーダ１０１０）、デコーダ（例えば、デコーダ１１１５）、デコーダからの出力を処理するポストプロセッサ（例えば、プロセッサ１１２５）、またはエンコーダに入力を提供するプリプロセッサ（例えば、プロセッサ１００５）のうちの一以上で実施できる。さらに、本開示では、他の実施形態を想定している。

言うまでもなく、本発明は、ハードウェア、ソフトウェア、ファームウェア、特殊用途プロセッサ、またはこれらの組み合わせなどのいろいろな形体で実施することができる。好ましくはハードウェアとソフトウェアを組み合わせて本発明を実施する。また、プログラム記録装置に有体的に化体されたアプリケーションプログラムとしてソフトウェアを実施してもよい。そのアプリケーションプログラムは、好適なアーキテクチャを有する機械にアップロードされ、実行される。好ましくは、機械は、中央処理装置（ＣＰＵ）、ランダムアクセスメモリ（ＲＡＭ）、及び入出力（Ｉ／Ｏ）インターフェイス等のハードウェアを有するコンピュータプラットフォームで実施される。コンピュータプラットフォームはオペレーティングシステムとマイクロコードも含んでもよい。ここに説明した様々なプロセスや機能は、オペレーティングシステムにより実行できる、マイクロ命令コードの一部やアプリケーションプログラムの一部（またはこれらの組み合わせ）であってもよい。また、追加的データ記憶装置や印刷装置等その他の様々な周辺装置をコンピュータプラットフォームに接続してもよい。
さらに言うまでもなく、添付した図面に示したシステム構成要素や方法ステップの一部はソフトウェアで実施されてもよいので、システム構成要素（または方法ステップ）間の実際的な結合は本発明をプログラムするそのプログラム方法に応じて異なる。ここに開示された本発明の教示を受けて、関連技術分野の当業者は、本発明の同様な実施形態や構成を考えることができるであろう。

Claims

３次元メッシュの位置符号化の方法であって、
空でない子セルＣ_ｌ，ｋのシンボル確率を推定する、Ｃ_ｌ，ｋはレイヤｌにあるｋ番目のセルを示すステップであって、前記シンボル確率はフィッティングされた平面Ｐの正確性に基づき推定されるステップと、
前記空でない子セルが二以上の頂点を有するとき、前記空でない子セルを分割してサブセルを生成するステップと、
レイヤｌに、未処理の空でない子セルがまだあるか判断するステップと、
レイヤｌにまだ処理されていない空でない子セルがなければ、レイヤｌのすべての空でない子セルが頂点を１つだけ有し、サブセルの中心とそのサブセル内の点との間の距離が第１の閾値以下であるか判断するステップと、
レイヤｌのすべての空でない子セルが頂点を１つだけ有し、サブセルの中心とそのサブセル内の点との間の距離が第１の閾値以下であるとき、前記空でない子セルの位置を表すシンボルをエントロピー符号化するステップと、
を有する方法。
前記第１の閾値は最大エラーである、請求項１に記載の方法。
あるレイヤのサブセルが次に深いレイヤのセルになる、請求項１に記載の方法。
レイヤｌの、「１」を１つだけ有する空でない子セルのシンボル確率を推定する、前記「１」を１つだけとは、前記空でない子セルが少なくとも１つの頂点を含むことを示す、請求項１に記載の方法。
現在の空でない子セルの中心座標と、現在の空でない子セルに連結したセルの中心座標とにより形成される凸形状ハルの表面積に応じて、前記空でない子セルのシンボル確率を予測するステップをさらに有する、請求項４に記載の方法。
現在の空でない子セルの中心座標と、現在の空でない子セルに連結したセルの中心座標とにより形成される凸形状ハルの表面積に応じて、前記空でない子セルのシンボル確率を予測するステップをさらに有する、請求項３に記載の方法。
連結情報を得られるとき、前記フィッティングされた平面Ｐに、現在の空でない子セルに連結されたセルの中心座標を用いる、請求項４に記載の方法。
サブセルの中心座標と前記フィッティングされた平面Ｐとの間の距離に応じて、前記空でない子セルのシンボル確率を予測するステップと、
前記フィッティングされた平面Ｐのフィッティングエラーをチェックするステップと、
前記推定されたシンボル確率を調整するステップと
をさらに有する、請求項７に記載の方法。
前記フィッティングエラーが第２の閾値より小さいとき、前記予測されたシンボル確率を調整しない、請求項８に記載の方法。
前記フィッティングエラーが第２の閾値より大きいとき、前記予測されたシンボル確率を一様分布に近く設定する、請求項８に記載の方法。
空でない子セル構成のシンボル確率を計算する関数のパラメータとして前記フィッティングエラーを用い、前記パラメータが大きくなると、空でない子セルの推定されたシンボル確率が一様分布に近づくようにする、請求項８に記載の方法。
連結情報が得られないとき、隣接する空でないセルの中心座標を、前記フィッティングされた平面Ｐに用いる、請求項４に記載の方法。
サブセルの中心座標と前記フィッティングされた平面Ｐとの間の距離に応じて、前記空でない子セルのシンボル確率を予測するステップと、
前記フィッティングされた平面Ｐのフィッティングエラーをチェックするステップと、
前記推定されたシンボル確率を調整するステップと
をさらに有する、請求項１２に記載の方法。
前記フィッティングエラーが第２の閾値より小さいとき、前記予測されたシンボル確率を調整しない、請求項１３に記載の方法。
前記フィッティングエラーが第２の閾値より大きいとき、前記予測されたシンボル確率を一様分布に近く設定する、請求項１３に記載の方法。
空でない子セル構成のシンボル確率を計算する関数のパラメータとして前記フィッティングエラーを用い、前記パラメータが大きくなると、空でない子セルの推定されたシンボル確率が一様分布に近づくようにする、請求項１２に記載の方法。
レイヤｌの、「１」を複数有する空でない子セルのシンボル確率を推定する、
請求項１に記載の方法。
各頂点に重みを割り当て、前記重みが大きすぎるとき、前記重みをリスケールし、推定された確率を対応する重みで規格化する、請求項１７に記載の方法。
３次元メッシュの位置符号化するエンコーダであって、
データを受け取り、符号化された信号を生成するエンコーダであって、
空でない子セルＣ_ｌ，ｋのシンボル確率を推定する、Ｃ_ｌ，ｋはレイヤｌにあるｋ番目のセルを示すステップであって、前記シンボル確率はフィッティングされた平面Ｐの正確性に基づき推定されるステップと、
前記空でない子セルが二以上の頂点を有するとき、前記空でない子セルを分割してサブセルを生成するステップと、
レイヤｌに、未処理の空でない子セルがまだあるか判断するステップと、
レイヤｌにまだ処理されていない空でない子セルがなければ、レイヤｌのすべての空でない子セルが頂点を１つだけ有し、サブセルの中心とそのサブセル内の点との間の距離が閾値以下であるか判断するステップと、
レイヤｌのすべての空でない子セルが頂点を１つだけ有し、サブセルの中心とそのサブセル内の点との間の距離が閾値以下であるとき、前記空でない子セルの位置を表すシンボルをエントロピー符号化するステップと、を実行するエンコーダ。
レイヤｌの、「１」を１つだけ有する空でない子セルのシンボル確率を推定し、前記「１」を１つだけとは、前記空でない子セルが少なくとも１つの頂点を含むことを示し、連結情報を得られるとき、前記フィッティングされた平面Ｐに、現在の空でない子セルに連結されたセルの中心座標を用いる、
前記エンコーダは、さらに、
サブセルの中心座標と前記フィッティングされた平面Ｐとの間の距離に応じて、前記空でない子セルのシンボル確率を予測するステップと、
前記フィッティングされた平面Ｐのフィッティングエラーをチェックするステップと、
前記推定されたシンボル確率を調整するステップと
を実行する、請求項１９に記載のエンコーダ。
レイヤｌの、「１」を１つだけ有する空でない子セルのシンボル確率を推定し、連結情報が得られないとき、隣接する空でないセルの中心座標を、前記フィッティングされた平面Ｐに用いる、
前記エンコーダは、さらに、
サブセルの中心座標と前記フィッティングされた平面Ｐとの間の距離に応じて、前記空でない子セルのシンボル確率を予測するステップと、
前記フィッティングされた平面Ｐのフィッティングエラーをチェックするステップと、
前記推定されたシンボル確率を調整するステップと
を実行する、請求項１９に記載のエンコーダ。
レイヤｌの、「１」を複数有する空でない子セルのシンボル確率を推定する、各頂点に重みを割り当て、前記重みが大きすぎるとき、前記重みをリスケールし、推定された確率を対応する重みで規格化する、請求項１９に記載のエンコーダ。