JP7573052B2 - 符号化及び復号方法、エンコーダ、デコーダ及びソフトウェア - Google Patents

Description

本発明は、点群圧縮に関し、特に点群のエントロピー符号化を改善するための符号化及び復号方法並びにエンコーダ及びデコーダに関する。

近年、３次元メディア情報の表現方法として、３次元メッシュに代わる３次元点群が注目されている。点群データに関連するユースケースは非常に多岐にわたり、
映画制作における３Ｄ資産（ａｓｓｅｔ）、
リアルタイム３Ｄ没入型テレプレゼンス、又は仮想現実（ＶＲ）アプリケーションのための３Ｄ資産、
３Ｄ自由視点映像（例えば、スポーツ観戦のために用いられる）、
地理情報システム（地図作成）、
文化遺産（壊れやすい資産のデジタル形式での保存）、
自動運転（大規模な環境の３Ｄマッピング）などを含む。
点群とは、３Ｄ空間内の点の集合であり、各点は色や材料特性などの関連する属性を持つ。点群を使って、オブジェクトやシーンをこれらの点の集合として再構成することができる。異なる設定の複数のカメラと深度センサを使用して点群を取得することができ、再構成されたシーンをリアルに再現するために、点群は、数千から数十億の点で構成されることもある。

点群の各点には、その位置（通常は３２ビット又は６４ビットの浮動小数点として符号化されたＸ、Ｙ、Ｚ情報）とその属性（通常は少なくとも２４ビットで符号化されたＲＧＢカラー）を格納する必要がある。点群に含まれる点は数十億個に及ぶこともあるため、点群の生データは数ギガバイトに及ぶことが容易に理解できる。従って、点群を表現するために必要なデータ量を削減するための圧縮技術が強く求められている。

点群の圧縮には、２つの異なる方法が開発された。

まず、ビデオベース点群圧縮（Ｖｉｄｅｏ ｂａｓｅｄ Ｐｏｉｎｔ Ｃｌｏｕｄ Ｃｏｍｐｒｅｓｓｉｏｎ、ＶＰＣＣ）方法では、点群を３つの異なる軸Ｘ、Ｙ、Ｚと異なる深さに複数回投影してすべての点を１つの投影画像に存在させる。次に、投影して得られた複数の投影画像を複数の部分（ｐａｔｃｈ）に処理することで冗長性を除去し、再配列して最終的な画像を得、当該最終的な画像に付加されたメタデータは画素位置を空間上の点位置に変換するために用いられる。その後、従来の画像／動画用ＭＰＥＧエンコーダで圧縮を行う。この方法の利点は、既存のエンコーダを再利用し、動的な点群を自然にサポートする（ビデオエンコーダを使用）ことであるが、この方法は疎な点群にはほとんど適用できず、点群専用の方法でより高い圧縮利得が得られると予想される。

第二に、ジオメトリベース点群圧縮（Ｇｅｏｍｅｔｒｙ ｂａｓｅｄ Ｐｏｉｎｔ Ｃｌｏｕｄ Ｃｏｍｐｒｅｓｓｉｏｎ、ＧＰＣＣ）方法では、点位置（通常ジオメトリと呼ばれる）と点の属性（色、透明度など）が別々に符号化される。ジオメトリを符号化するために、八分木構造が使用される。点群全体は１つの立方体に収められ、当該立方体を８つのサブ立方体に分割し続け、各サブ立方体に１つの点しか含まれないようにする。従って、点の位置は、木の各ノードの占有情報に置き換えられる。各立方体は８個のサブ立方体のみを有するため、占有を符号化するのに３ビットが十分であり、従って深さＤの木に対して、１つの点の位置を符号化するのに３^Ｄビットが必要である。このような変換だけでは、圧縮利得を高めることが十分ではないが、木構造であるため、多くの点が同じノード値を共有し、また、エントロピーエンコーダが使用されるため、情報量を大幅に低減できることに留意する必要がある。

多くの点群は表面を含むことを考慮し、従来のＧＰＣＣ設計において、平面符号化方式を導入して八分木に適用するノードをより効果的に符号化する。

そこで、占有子ノードが同一水平面に属するか否かを示すフラグｉｓＰｌａｎａｒを導入した。ｉｓＰｌａｎａｒがｔｒｕｅであれば、その平面が下平面であるか上平面であるかを示すために、追加ビットでＰｌａｎｅＰｏｓｉｔｉｏｎをシグナリングする。

バイナリ算術エンコーダを利用してｉｓＰｌａｎａｒフラグを符号化し、８（即ち、２×２×２）ビットのコンテキスト情報を平面コンテキスト情報とする。また、ノードが平面である場合、バイナリ算術エンコーダを用いて平面位置情報を符号化し、２４（即ち、２×３×２×２）ビットのコンテキスト情報を平面位置コンテキスト情報とする。

なお、角度符号化方式を導入することにより、疎な点群データに対する角度コンテキストを用いて平面符号化方式を強化し、ただし、大多数の場合、疎な点群データにおける隣接占有は０（すなわち、空）に近づく。より具体的には、削減されたコンテキスト情報でｐｌａｎｅＰｏｓｉｔｉｏｎを符号化する際に、角度符号化方式は、コンテキスト情報を置き換え、依然として平面符号化方式と同じコンテキストモデルを用いてＩｓＰｌａｎａｒフラグを算術的に符号化する。しかしながら、点群を符号化及び復号するための従来の方法において、隣接ノードの情報は考慮されていない。

それを鑑みて、本発明の目的は、点群のデータ圧縮の速度及び正確度を改善するための符号化及び復号方法、エンコーダ及びデコーダを提供することである。

本発明の１態様において、点群を符号化して圧縮点群データのビットストリームを生成するための符号化方法を提供し、前記点群のジオメトリは八分木ベース構造によって表現され、前記八分木ベース構造は、前記点群を含むボリューム空間をサブボリュームに再帰的に分割することにより、親子関係を有する複数のノードを含み、各前記サブボリュームは前記八分木ベース構造のノードに関連し、前記方法は、
符号化方式を決定するステップであって、前記符号化方式は平面符号化方式と角度符号化方式とを含むステップと、
現在の子ノードの符号化コンテキスト情報を取得するステップであって、
前記符号化方式が前記平面符号化方式であれば、符号化コンテキスト情報は平面コンテキスト情報を含み、前記現在の子ノードの平面コンテキスト情報は現在の親ノードの占有パターンと、前記現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンとに基づいて決定され、
前記符号化方式が前記角度符号化方式であれば、前記現在の子ノードの符号化コンテキスト情報は前記現在の親ノードの平面情報と、前記現在の親ノードに隣接する垂直隣接親ノードの占有とを含むステップと、
決定された符号化コンテキスト情報に基づいて、前記現在の子ノードの占有をエントロピー符号化して前記ビットストリームの符号化データを生成するステップとを含む。

従って、まず符号化方式を決定し、符号化方式に基づいてコンテキスト情報を決定し、当該コンテキスト情報は二種類の異なるコンテキスト情報を含み、それにより効果的なエントロピー符号化を行う。

平面符号化方式の場合、現在の親ノードと隣接親ノードは木の同じ深さＤにある。現在の親ノードと隣接親ノードとは、位置によって共通表面を共有している。現在の子ノードは、木の深さＤ＋１における、現在の親ノードの直接子ノードであり、平面コンテキスト情報は、現在の親ノードと少なくとも１つの隣接親ノードの占有パターンに依存して決定される。占有パターンは、各親ノード内の占有子ノードの分布を含む。平面コンテキスト情報は、現在の子ノードを通過する、点群によって表現される可能性のある平面又は表面に関する情報を含む。従って、現在の親ノードの少なくとも１つの直接隣接ノードの占有パターンの情報はエントロピー符号化のためのコンテキスト情報として考慮される。

角度符号化方式の場合、代わりに、より効率的な平面コンテキスト方式が実現される。平面符号化方式の平面コンテキスト情報と比べ、疎なクラウドデータでアクセス可能な情報のみが考慮される。

その結果、現在の子ノードの占有の予測をより確実に行うことができ、予測結果はエントロピーエンコーダに利用され、データ量をさらに低減させることができる。このようにして、各ノードの占有を決定するために木が完全にトラバースされ、エントロピーエンコーダに十分なコンテキスト情報を提供する。

好ましくは、隣接親ノードは現在の子ノードに直接隣接するノードであり、現在の子ノードと１つの表面を共有する。

好ましくは、平面符号化方式の場合、符号化コンテキスト情報は平面コンテキスト情報を含み、前記現在の子ノードの唯一の平面コンテキスト情報は現在の親ノードの占有パターン及び前記現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンに基づいて決定される。

好ましくは、角度符号化方式の場合、現在の子ノードの符号化コンテキスト情報は現在の親ノードの平面情報及び現在の親ノードに隣接する垂直隣接親ノードの占有を含む。

好ましくは、符号化方式が平面符号化方式であれば、符号化コンテキスト情報は平面位置コンテキスト情報を含み、平面位置コンテキスト情報は、
現在の子ノードと、前記八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードとの間の距離ｄと、
前記八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードの平面位置と、
前記現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンに基づいて決定された前記現在の子ノードの平面位置と
のうちの１つ又は複数を含む。

特に、距離ｄは、「近い」、「あまり遠くない」、「遠い」の値に離散化される。同じ深さＤの同じ座標での符号化されたノードが存在すれば、平面位置の「高」又は「低」も平面位置コンテキスト情報に含まれてもよい。子ノードの座標は対応する親ノード内の相対位置である。また、平面位置は、現在の親ノードに隣接する少なくとも１つの隣接親ノードの占有パターンに基づいて決定された平面位置コンテキスト情報に含まれてもよい。特に、平面位置コンテキスト情報は１つ以上又はすべての上記情報を含む。特に、平面符号化方式において、平面位置コンテキスト情報は上記情報を含み得る。

好ましくは、八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードが存在しなければ、平面位置コンテキスト情報は、現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンに基づいて決定された現在の子ノードの平面位置のみを含む。従って、この場合、隣接ノードから収集された情報のみに基づいて平面位置コンテキスト情報を決定する。これ以上の情報は取得できないため、利用することもできない。しかし、隣接ノードからの情報が含まれるため、このような場合でも効率的な圧縮が実現可能となる。特に、従来のＧＰＣＣ仕様で提出された、ｐｌａｎｅＰｏｓｉｔｉｏｎを符号化するための平面に垂直な軸を識別するａｘｉｓＩｄｘ文は、隣接ノードの占有に基づいて決定されたコンテキスト情報に置き換えられる。

好ましくは、符号化方式が角度符号化方式であり、現在の子ノードに角度符号化方式が適用しない場合、符号化コンテキスト情報は、平面位置コンテキスト情報を含み、平面位置コンテキスト情報は、
現在の子ノードと、八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードとの間の距離ｄと、
八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードの平面位置と、
現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンに基づいて決定された前記現在の子ノードの平面位置と
のうちの１つ又は複数を含む。
従って、この場合、平面位置コンテキスト情報は、平面符号化方式における平面位置情報と同じであってもよい。特に、平面位置コンテキスト情報は１つ以上又はすべての上記情報を含む。特に、角度符号化方式において、現在の子ノードに角度符号化方式が適用しない場合、平面位置コンテキスト情報は、上記情報を含み得る。

好ましくは、少なくとも１つの隣接ノードの占有パターンに基づいて平面コンテキスト情報及び平面位置コンテキスト情報を決定するために、現在の親ノードに対する現在の子ノードの平面位置が決定され、現在の平面位置は、高平面位置及び低平面位置を含む。ここで、考慮されるある幾何軸について、親ノードを通過する軸に沿って、現在の親ノード内に当該軸に垂直である、現在の子ノードを含む子ノードの平面が存在すれば、現在の平面位置は低平面位置である。現在の親ノードに当該軸に垂直である、現在の子ノードを含まない子ノードの平面が存在すれば、現在の平面位置は高平面位置である。このように、平面符号化方式では平面コンテキスト情報として、平面符号化方式と角度符号化方式では平面位置コンテキスト情報の一部として用いるために、現在の平面位置が決定される。

好ましくは、現在の平面位置が低平面位置であれば、平面コンテキスト情報及び平面位置コンテキスト情報は、隣接親ノードの現在の親ノードに直接隣接する第１グループの４つの子ノードの占有と、現在の親ノードの前記第１グループに正対する第２グループの４つの子ノードの占有とに基づいて決定される。換言すれば、隣接親ノードの第１グループの４つの子ノードは現在の親ノードと隣接親ノードとの共通表面に直接隣接し、第２グループは現在の親ノード内で現在の親ノードの反対側に直接隣接して配置される。各グループは、好ましくは、４つの子ノードによって１つの平面を定義し、各平面は考慮される幾何軸に垂直であり、評価すべき現在の子ノードに直接隣接する。それにより、十分な情報が取得でき、現在の子ノードにおける平面の可能性とその位置の可能性を確実に予測することができる。

好ましくは、現在の平面位置が低平面位置であれば、第１グループの少なくとも１つの子ノードが占有されており、第２グループが占有されていない場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。

好ましくは、現在の平面位置が低平面位置であれば、第１グループが占有されておらず、第２グループの少なくとも１つの子ノードが占有されている場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。

好ましくは、現在の平面位置が低平面位置であれば、第１グループが占有されておらず、第２グループが占有されていない場合、平面コンテキスト情報は平面の可能性を含み、ただし、隣接親ノードにおいて第１グループに属しない少なくとも１つ又は複数の子ノードが占有されている場合、平面位置コンテキスト情報は低平面の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ」である。

好ましくは、現在の平面位置が低平面位置であれば、第１グループの少なくとも１つの子ノードが占有されており、第２グループの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＞＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、低平面位置の可能性を含み、ただし、＃ＦｉｒｓｔＧｒｏｕｐは第１グループの占有ノードの数を示し、＃ＳｅｃｏｎｄＧｒｏｕｐは第２グループの占有ノードの数を示す。

好ましくは、現在の平面位置が低平面位置であれば、第１グループの少なくとも１つの子ノードが占有されており、第２グループの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＜＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、高平面位置の可能性を含み、ただし、＃ＦｉｒｓｔＧｒｏｕｐは第１グループの占有ノードの数を示し、＃ＳｅｃｏｎｄＧｒｏｕｐは第２グループの占有ノードの数を示す。

好ましくは、現在の平面位置が高平面位置であれば、平面コンテキスト情報及び平面位置コンテキスト情報は、考慮される軸に沿った前記現在の親ノードの直後の隣接親ノードの占有パターン、及び考慮される軸に垂直な平面にあり、前記現在の子ノードに直接隣接する、前記現在の親ノードの４つの子ノードのグループの占有に基づいて決定される。換言すれば、現在の親ノードの共通表面に直接隣接する（すなわち、当該共通表面の後に位置する）隣接親ノードの子ノードの占有は、復号順によって不明である。従って、現在の子ノードと１つの共通表面を共有する隣接親ノード自身の占有は、現在の親ノード内の現在の子ノードの反対側に直接隣接して配置される、すなわち隣接親ノードに対向する（すなわち、符号化／復号順の前）グループと共に使用される。従って、子ノードグループには、符号化すべき現在の子ノードが含まれない。各グループは、好ましくは４つの子ノードによって１つの平面を定義し、各平面は考慮される幾何軸に垂直であり、評価すべき現在の子ノードに直接隣接する。それにより、十分な情報が取得でき、現在の子ノードにおける平面の可能性とその位置の可能性を確実に予測することができる。

好ましくは、現在の平面位置が高平面位置であれば、当該グループの少なくとも１つの子ノードが占有されており、隣接親ノードが占有されていない場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。

好ましくは、現在の平面位置が高平面位置であれば、当該グループが占有されておらず、隣接親ノードが占有されている場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。

好ましくは、現在の平面位置が高平面位置であれば、当該グループが占有されておらず、隣接親ノードが占有されていない場合、平面コンテキスト情報は平面の可能性を含み、ただし、考慮される軸に沿った現在の親ノードの直前の隣接親ノードにおける少なくとも１つ又は複数の子ノードが占有されている場合、平面位置コンテキスト情報は低平面の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ」である。

好ましくは、現在の平面位置が高平面位置であれば、当該グループの少なくとも１つの子ノードが占有されており、隣接親ノードが占有されており、＃Ｇｒｏｕｐ＞２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含み、＃Ｇｒｏｕｐは、当該グループにおける占有ノードの数を示す。ただし、隣接親ノードのうち、統計的に１つの子ノードが占有されていると仮定する。

好ましくは、現在の平面位置が高平面位置であれば、当該グループの少なくとも１つの子ノードが占有されており、隣接親ノードが占有されており、＃Ｇｒｏｕｐ＜２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含み、＃Ｇｒｏｕｐは、当該グループにおける占有ノードの数を示す。

好ましくは、現在の平面位置が高平面位置であれば、当該グループの少なくとも１つの子ノードが占有されており、隣接親ノードが占有されており、＃Ｇｒｏｕｐ＝２である場合、平面コンテキスト情報は平面が存在しない可能性を含み、平面位置は未知と推定され、＃Ｇｒｏｕｐは、当該グループにおける占有ノードの数を示す。

好ましくは、隣接親ノードは、幾何軸の１つに沿って配置される。幾何軸（Ｘ、Ｙ、Ｚ）のいずれかに沿って平面コンテキスト情報を評価する場合、隣接親ノードは、当該特定の軸に沿った当該親ノードの直前又は直後に位置する。

好ましくは、平面コンテキスト情報は、３つの幾何軸のすべてに沿って決定される。このようにして、点群の各点によって表される平面又は表面は各軸に沿って評価される。

好ましくは、現在の親ノードは、復号順に従って隣接親ノードと相対的に配置される。復号する際には、八分木ベース構造のノードが順次評価される。従って、復号順において現在の親ノードの前にある占有パターンの情報は、既にアクセス可能であり、それにより、復号のための平面コンテキスト情報の決定に用いられことができる。特に、復号順は、符号化順と完全に逆である。ただし、符号化する際に、点群における各点の確実な位置は既知である。

本発明の１態様において、圧縮点群データのビットストリームを復号して再構成点群を生成するための方法を提供し、点群のジオメトリは八分木ベース構造によって表現され、前記八分木ベース構造は、前記点群を含むボリューム空間をサブボリュームに再帰的に分割することにより、親子関係を有する複数のノードを含み、各前記サブボリュームは前記八分木ベース構造のノードに関連し、前記方法は、
符号化方式を決定するステップであって、前記符号化方式は平面符号化方式と角度符号化方式とを含むステップと、
現在の子ノードの符号化コンテキスト情報を取得するステップであって、
前記符号化方式が前記平面符号化方式であれば、符号化コンテキスト情報は平面コンテキスト情報を含み、前記現在の子ノードの平面コンテキスト情報は現在の親ノードの占有パターンと、前記現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンとに基づいて決定され、
前記符号化方式が前記角度符号化方式であれば、前記現在の子ノードの符号化コンテキスト情報は前記現在の親ノードの平面情報と、前記現在の親ノードに隣接する垂直隣接親ノードの占有とを含むステップと、
前記現在の子ノードの符号化コンテキスト情報に基づいて、前記ビットストリームをエントロピー復号して前記点群を再構成する。

平面符号化方式の場合、現在の親ノードと隣接親ノードは木の同じ深さＤにある。現在の親ノードと隣接親ノードとは、位置によって共通表面を共有している。現在の子ノードは、木の深さＤ＋１における、現在の親ノードの直接子ノードであり、平面コンテキスト情報は、現在の親ノードと少なくとも１つの隣接親ノードの占有パターンに依存して決定される。平面コンテキスト情報は、現在の子ノードを通過する、点群によって表現される可能性のある平面又は表面に関する情報を含む。従って、現在の親ノードの少なくとも１つの直接隣接ノードの占有に関する情報はエントロピー復号のためのコンテキスト情報として考慮される。

角度符号化方式の場合、代わりに、より効率的な平面コンテキスト方式が実現される。平面符号化方式の平面コンテキスト情報と比べ、疎なクラウドデータでアクセス可能な情報のみが考慮されている。

その結果、現在の子ノードの占有の予測をより確実に行うことができ、予測結果はエントロピーデコーダに利用され、データ量をさらに低減させることができる。このようにして、各ノードの占有を決定するために木が完全にトラバースされ、エントロピーデコーダに十分なコンテキスト情報を提供する。

好ましくは、復号方法は、さらに、上述した符号化方法に関する特徴に従って構成される。これらの特徴は、復号方法と自由に組み合わせることができる。

本発明の１態様において、点群を符号化して圧縮点群データのビットストリームを生成するためのエンコーダを提供し、前記点群のジオメトリは八分木ベース構造によって表現され、前記八分木ベース構造は、前記点群を含むボリューム空間をサブボリュームに再帰的に分割することにより、親子関係を有する複数のノードを含み、各前記サブボリュームは前記八分木ベース構造のノードに関連し、
プロセッサ、及び、メモリ記憶デバイスを含み、前記メモリ記憶デバイスには前記プロセッサにより実行可能な命令が記憶されており、前記命令が実行されると、前記プロセッサに上記符号化方法を実行させる。

本発明の１態様において、圧縮点群データのビットストリームを復号して再構成点群を生成するためのデコーダを提供し、点群のジオメトリは八分木ベース構造によって表現され、前記八分木ベース構造は、前記点群を含むボリューム空間をサブボリュームに再帰的に分割することにより、親子関係を有する複数のノードを含み、各前記サブボリュームは前記八分木ベース構造のノードに関連し、
プロセッサ、及び、メモリ記憶デバイスを含み、前記メモリ記憶デバイスには前記プロセッサにより実行可能な命令が記憶されており、前記命令が実行されると、前記プロセッサに上記復号方法を実行させる。

本発明の１態様において、非一時的なコンピュータ可読記憶媒体を提供し、該媒体にはプロセッサが実行する命令が記憶されており、前記命令が実行されると、前記プロセッサに上記符号化及び／又は復号方法を実行させる。

ここで例示の形式で図面を参照し、図面は本願の例示的な実施例を示す。
点群エンコーダの全体図を示すブロック図である。 点群デコーダの全体図を示すブロック図である。 図３は八分木データ構造の概略図である。 各ノードにおける８つの子ノードの番号付けである。 既知の占有情報を有するノードの隣接ノードを示す図である。 コンテキスト情報を示す図である。 本発明の具体的な実施例を示す図である。 本発明の具体的な実施例を示す図である。 本発明の具体的な実施例を示す図である。 本発明の第１実施例及び第２実施例のステップを示すフローチャートである。 エンコーダの概略図である。 デコーダの概略図である。

本発明は点群を符号化及び復号するための方法及び点群を符号化及び復号するためのエンコーダ及びデコーダを説明する。サブボリュームに関連する現在の親ノードはさらに、複数のサブボリュームに分割され、各サブボリュームは現在の親ノードの子ノードに対応し、そしてエンコーダで、子ノードの占有状況に基づいて、現在の親ノードの占有パターンを決定する。現在の親ノードの占有パターンと、現在の親ノードに直接隣接する隣接親ノードの占有パターンとに基づいて平面コンテキスト情報（ｐｌａｎａｒ ｃｏｎｔｅｘｔ ｉｎｆｏｒｍａｔｉｏｎ）を決定する。エントロピーエンコーダは、決定された平面コンテキスト情報に基づいて占有パターンを符号化することにより、ビットストリームの符号化データを生成する。デコーダは、同一の平面コンテキスト情報を決定し、ビットストリームをエントロピー復号することにより、占有パターンを再構築する。

当業者であれば、添付の図面と併せて以下の実施例の説明を検討すると、本発明の他の態様及び特徴を理解することができる。

以下の説明では、時として、「ノード」と「サブボリューム（ｓｕｂ－ｖｏｌｕｍｅ）」という用語が互換的に使用されることがある。ノードがサブボリュームに関連していることは理解されるべきである。ノードは、木の上の特定の点であり、内部ノード又は葉ノードであってもよい。サブボリュームは、ノードが表現する境界あり物理的空間である。「ボリューム（ｖｏｌｕｍｅ）」という用語は、定義された、点群を含む最大の境界あり空間を意味するために使用されてもよい。ボリュームは、点群データを符号化するための相互接続されたノードの木構造を構築するために、サブボリュームに再帰的に分割される。

点群とは、３次元座標系における点の集合である。これらの点は、通常、１つ又は複数の物体の外面を表現することを意図している。各点は、３次元座標系における位置（ポジション）がある。当該位置は、デカルト座標系又は他の任意の座標系における３つの座標（Ｘ、Ｙ、Ｚ）で表されてもよい。これらの点には、色などの他の関連属性を有してもよく、場合によっては、Ｒ、Ｇ、Ｂ、又はＹ、Ｃｂ、Ｃｒなどの３成分の値であってもよい。他の関連属性は、所望の点群データの用途に応じて、透明度、反射率、法線ベクトルなどを含み得る。

点群は、静的なものであっても、動的なものであってもよい。例えば、物体や地形の詳細なスキャンやマッピングは、静的な点群データであってもよい。マシンビジョン目的の環境のＬｉＤＡＲベースのスキャンは、点群が（少なくとも潜在的に）時間の経過とともに（例えばボリュームの連続したスキャンごとに）変化するため、動的であってもよい。従って、動的な点群は、時間順に並んだ点群のシーケンスである。

点群データは、保存（歴史的・文化的な物体のスキャン）、地図作成、マシンビジョン（自動運転・半自動運転車など）、仮想現実システムなど、様々な用途で利用され得る。マシンビジョンなどの用途で使われる動的な点群データは、保存用の静的な点群データとはかなり異なってもよい。例えば、車載ビジョンは、通常、解像度が比較的低く、無色で、高度に動的な点群に係り、前記点群は、高い収集頻度を持つＬｉＤＡＲ（又は類似のもの）センサによって取得される。このような点群の目的は、人間が使用したり見たりするためではなく、決定プロセスにおける機械オブジェクト検出／分類のためである。例えば、一般的なＬｉＤＡＲフレーム（ｆｒａｍｅ）には数万点が含まれるが、高品質の仮想現実アプリケーションでは数百万点が必要となる。計算速度の向上や新しいアプリケーションの開発に伴い、時間の経過とともに、より高解像度のデータが求められるようになることが予想される。

点群データは有用であるが、効率的かつ効率的な圧縮、すなわち符号化及び復号処理がないため、採用や配置に支障をきたす可能性がある。

点群データを符号化するための一般的なメカニズムの１つは、木ベース構造を使用することである。木ベース構造では、点群の境界あり三次元ボリュームはサブボリュームに再帰的に分割される。木のノードはサブボリュームに対応する。サブボリュームをさらに分割するか否かの判断は、木の解像度及び／又はサブボリュームに含まれる点の有無に基づいて行ってもよい。葉ノードは、その関連するサブボリュームが点を含むか否かを示す占有フラグを有してもよい。分割フラグは、ノードがサブノードを有するか否か（すなわち、現在のボリュームがさらにサブボリュームに分割されているか否か）を示してもよい。これらのフラグは、場合によってはエントロピー符号化され、場合によっては予測符号化が使用されてもよい。

一般的な木構造は、八分木である。この構造におけるボリューム／サブボリュームはすべて立方体（ｃｕｂｅ）であり、サブボリュームが分割されるごとに、さらに８つのサブボリューム／サブ立方体が生成される。このような木構造の例示は、図３に示され、完全の点群を含むボリュームを表現するノード３０を有する。当該ボリュームは８つのサブボリューム３２に分割され、各サブボリュームは図３の八分木における１つのノードに関連する。点を含むノードは、点群の少なくとも１つの点３５を含む占有ノード３４を表し、空ノード３６は、点群の点を含まないサブボリュームを表す。図３に示すように、占有ノードは８つのサブボリュームにさらに分割されてもよく、この８つのサブボリュームは特定の親ノード４０の各子ノード３８に関連し、それにより親ノード４０の占有パターンを決定する。図３に示すように、例示された親ノード４０の占有パターンは、バイナリ形式で「００１０００００」として表され得、占有されている第３子ノード３８を指示する。いくつかの実施形態において、この占有パターンをバイナリエントロピーエンコーダで符号化し、それにより点群データのビットストリームが生成される。

図１には、本発明の１形態に係る点群エンコーダ１０の簡略化されたブロック図を示す。点群エンコーダ１０は、点群データ１２を受信し、八分木を生成するための木構築モジュールを備えてもよく、八分木は点群を含むボリューム空間のジオメトリを表現し、点群の点の当該ジオメトリにおけるポジション又は位置を指示する。

点群を符号化するための八分木の基本的な作成方法は、以下を含み得る。
１．座標系の点群を含むバウンディングボリューム（立方体）から開始する。
２．当該バウンディングボリュームを８つのサブボリューム（８つのサブ立方体）に分割する。
３．各サブボリュームに対して、サブボリュームが空の場合は０でマーキングし、サブボリュームが少なくとも１つの点がある場合は１でマーキングする。
４．１でマーキングされたすべてのサブボリュームに対して、最大の分割の深さになるまで、上記の２を繰り返し、サブボリュームを分割する。
５．最大の深さのすべての葉サブボリューム（サブ立方体）に対して、葉立方体が空でない場合は１でマーキングし、そうでない場合は０でマーキングする。

木を所定の順序で（分割して得られた各サブボリュームにおいて、幅優先又は深さ優先で、スキャンパターン／順序に従って）トラバースし、各ノードの占有パターンを表すビットシーケンスを生成してもよい。

そして、エントロピーエンコーダ１６を用いて当該ビットシーケンスを符号化し、圧縮ビットストリーム１４を生成する。エントロピーエンコーダ１６はコンテキストモデル１８を用いてビットシーケンスを符号化してもよく、当該コンテキストモデル１８は、エントロピーエンコーダ１６がコンテキストに基づいてビットを符号化するための確率を決定するということを規定する。各ビット又は定義されたビットの集合を符号化した後、コンテキストモデル１８は適応的に更新されてもよい。

ビデオ符号化又は画像符号化と同様に、点群符号化には予測操作を含み得、これらの操作において、サブボリュームのパターンの予測に努めており、パターンそのものではなく、予測によって得られた残差を符号化する。予測は、空間的（同一点群内の事前符号化されたサブボリュームに依存）であってもよいし、時間的（時間順に並んだ点群シーケンスにおける、事前符号化された点群に依存）であってもよい。

図２に、エンコーダ１０に対応する点群デコーダ２０の一例のブロック図を示す。点群デコーダ２０はエントロピーデコーダ２２を備え、エントロピーデコーダ２２はエンコーダ１０と同じコンテキストモデル２４を用いる。エントロピーデコーダ２２は、圧縮データの入力ビットストリーム２６を受信し、当該データをエントロピー復号することにより、展開されたビットの出力シーケンスが生成される。そして、当該シーケンスは、木再構築装置により、再構成された点群データに変換される。木再構築装置は、展開されたデータと、木データを二値化するスキャン順序の知識とに基づいて、木構造２８を再構築する。これにより、木再構成装置は、点群における点の位置を再構成することができる。

図４に示すように、親ノード１１２が８つの子ノード１１０に分割され、この８つの子ノード１１０は２×２×２個の立方体であり、ただし、各立方体は同じサイズであり、辺の長さが親ノード１１２に関連する立方体の辺の長さの半分である。また、図４は、親ノード１１２内の子ノード１１０の番号を示している。以下、図４に示す番号付けシステムを用いて説明する。図４には、示された親ノード１１２の、幾何軸Ｘ、Ｙ、Ｚで表される３次元空間における、空間的な向きも示されている。

特定ノード内の点が表面に属しているため、占有パターンは、当該ノードが占有されているか否かの確率に関する平面情報を含んでもよい。通常、現実世界は閉じた表面に支配されている。特に室内の部屋だけではなく、都会の屋外シーンでも同様である。エントロピーエンコーダ及びデコーダは、そういう事実を利用している。点群によって表現される表面を検出できれば、その表面上の点の分布を予測することができ、それによりその表面に属する特定ノードの占有確率を決定することができる。それは、コンテキスト情報を定義することにより実現されることができ、当該コンテキスト情報は、ｉｓＰｌａｎａｒフラグを用いてビットストリームを符号化・復号するために用いられる。平面コンテキスト情報は、通常、バイナリ値であり、特定ノードの設定されたｉｓＰｌａｎａｒフラグ（ｉｓＰｌａｎａｒ＝１）は、そのノードが特定表面に属している可能性が高いと解釈される。なお、ノード内に表面が存在する事実以外、他の平面情報を考慮してもよく、例えば、ｐｌａｎｅＰｏｓｉｔｉｏｎフラグで実現された平面位置情報であってもよく、ｐｌａｎｅＰｏｓｉｔｉｏｎフラグは平面の現在の子ノード内の位置を指示する。また、ｐｌａｎｅＰｏｓｉｔｉｏｎフラグは、バイナリ値であってもよく、対応する位置を示す値である「高」及び「低」を有する。エントロピーエンコーダ／デコーダは平面コンテキスト情報を用いて、当該平面情報をビットストリームに符号化し、それによりビットストリームのデータを低減させる。

また、異なるコンテキスト情報を用いて異なるタイプの点群に適用される他の符号化方式も存在する。従って、平面符号化方式と角度符号化方式が定義されている。好ましくは、角度符号化方式は、疎な点群に適用され、角度コンテキスト情報をエントロピーエンコーダ／デコーダに提供することが意図されている。符号化方式はビットストリームのメタデータにおいて指示されてもよい。

従って、本発明によれば、平面符号化方式の場合、コンテキスト情報は上記したような平面コンテキスト情報及び平面位置コンテキスト情報を含む。平面コンテキスト情報は、後に詳述するように、符号化すべき現在の子ノードの現在の親ノードの占有パターンと、隣接ノードにおける少なくとも１つのノードの占有パターンとに基づいて決定される。また、図６は平面位置コンテキスト情報を示す。平面位置コンテキスト情報は、
ａ）現在の子ノード１２０と、八分木構造の深さＤでの、同じ座標での最も近い符号化されたノード１２１との間の距離ｄであって、「近い」と「あまり遠くない」と「遠い」との３つの値に離散化される距離ｄと、
ｂ）同じ深さ（低又は高）及び同じ座標での、最も近い符号化されたノード１２１の平面位置（それがある場合）と、
ｃ）後に詳述するような、少なくとも１つの隣接親ノードの占有パターンに基づく現在の子ノードの平面位置とを含む。

平面コンテキスト情報は１ビット（平面又は非平面）、平面位置コンテキスト情報は３×２×２ビットの情報である。

なお、本発明によれば、角度符号化方式の場合、コンテキスト情報は上記したような平面コンテキスト情報及び平面位置コンテキスト情報を含む。前記平面コンテキスト情報は、
ａ）現在の親ノードのｉｓＰｌａｎａｒフラグであって、すなわち現在の親ノードに平面が存在するか否かを示すｉｓＰｌａｎａｒフラグと、
ｂ）現在の親ノードに垂直方向に隣接する垂直隣接親ノード１２４の占有とを含む。

また、角度符号化方式に用いられる平面位置コンテキスト情報は、
ａ）既に利用可能なノードと現在の子ノードとの間の角度に基づいて識別された、既に利用可能なノードの平面位置ｐｌａｎｅＰｏｓｉｔｉｏｎを含む。

図５を参照して、２つの子ノード１０２、１０３を有する現在の親ノード１００を示し、２つの子ノード１０２、１０３は占有ノードとして例示され、すなわち２つの子ノードのサブボリュームは、それぞれ点群の少なくとも１つの点を含む。また、図５に示されているのは、隣接親ノード１０４、１０６、１０８であり、それぞれ少なくとも１つの占有子ノードを含む。特定の八分木レベルに位置する子ノード１０２、１０３の平面コンテキスト情報を予測する前に、当該八分木における、現在の親ノード１００と同じレベルＤでの３つの隣接親ノード１０４、１０６、１０８の占有情報は、デコーダ側で既知である。復号順は既定されたため、現在の親ノード１００の子ノード１０２、１０３を評価する際に、隣接親ノード１０４、１０８、１０６の情報は、復号器側で既知であり、コンテキスト情報の決定に用いられることができる。これら３つの隣接親ノード１０４、１０６、１０８は、現在の子ノード１０２、１０３に近傍しているため、これら隣接親ノード１０４、１０６、１０８の占有パターンと符号化すべき現在の子ノード１０２、１０３の占有パターンとの間には関連性が存在する。ここで、占有パターンは、各親ノードの子ノードの占有である。この情報は取得しやすいが、従来の符号化方法や復号方法ではまだ使用されていない。例えば、Ｘ軸に沿って現在の子ノード１０２のコンテキスト情報を評価する場合、Ｘ軸に沿った現在の親ノード１００に直接隣接する隣接親ノード１０４を考慮に入れてもよい。また、上述したように、直接隣接する親ノードが考慮され、当該親ノードは復号順において現在の親ノードの前にある。このように、復号期間において、先行ノードの占有パターンはデコーダにとっては既知であり、コンテキスト情報の決定に用いられることができる。Ｙ軸に沿ってコンテキスト情報を評価する場合、Ｙ軸に沿った現在の親ノード１００に隣接する隣接親ノード１０６を考慮に入れてもよい。当該情報も、デコーダにとっては既知であり、現在の子ノード１０２の信頼性の高い平面コンテキスト情報を取得するために利用しやすい。

ただし、現在の子ノードの占有と少なくとも１つの隣接親ノードの占有パターンとの関連性を考慮する場合、符号化すべき現在の子ノードの位置を考慮しなければならない。従って、現在の子ノードの現在の平面位置を決定する必要がある。現在の平面位置は、現在の親ノード内の現在の子ノードの考慮される軸に沿った平面と、当該幾何軸に垂直な平面とを示す。例えば、Ｘ軸に沿って、第１低平面は子ノード０、１、２、３によって定義され、高平面は子ノード４、５、６、７によって定義される。Ｙ軸に沿って、低平面は子ノード０、１、４、５によって定義され、高平面は子ノード２、３、６、７によって定義される。Ｚ軸に沿って、低平面は子ノード０、２、４、６によって定義され、高平面は子ノード１、３、５、７によって定義される。従って、図５の例では、子ノード１０２のＸ軸に沿った現在の平面位置は低平面位置であり、子ノード１０３のＸ軸に沿った現在の平面位置は高平面位置である。

図７を参照し、図７は、いかに現在の子ノードの隣接ノードの占有に基づいて平面コンテキスト情報及び平面位置コンテキスト情報を決定するかの構成を示し、前記情報は、点群データを圧縮するためにエントロピー符号化において用いられる。この点について、本発明の目的の１つは、現在の子ノード１２０の隣接親ノードの占有パターンを考慮し、平面情報を符号化するときに、そのような情報をコンテキスト情報に組み込むことである。ここで、図７は、符号化すべき現在の子ノードが現在の親ノードの低位置にある状況を示す。

図７（ａ）は、Ｘ軸に沿った平面コンテキスト情報の決定を示す。現在の子ノード１２０の平面コンテキスト情報は評価されるべきである。従って、現在の親ノード１２２と、現在の親ノード１２２に直接隣接する隣接親ノード１２４の占有パターンを評価する。評価すべき隣接親ノード１２４は、Ｘ軸に沿って配置される。また、隣接親ノード１２４は、復号順において現在の親ノード１２２の前に配置される。従って、現在の親ノード１２２を復号する際には、隣接親ノード１２４に関するすべての情報は、既に利用可能となる。また、点群の位置及び占有パターンはエンコーダにとって完全に既知であるため、現在の子ノード１２０の情報を符号化する際に、隣接親ノード１２４の占有情報も既知である。

特に、現在の子ノード１２０のコンテキスト情報を決定するためには、隣接親ノード１２４の子ノードである第１グループ１２６の子ノードと、現在の親ノード１２２の子ノードである第２グループ１２８の子ノードとを考慮する。隣接親ノード１２４の第１グループ１２６の４つの子ノードは、現在の親ノード１２２に直接隣接する。これにより、第１グループ１２６の各子ノードは、現在の親ノード１２２と共通表面を共有する。現在の親ノード１２２の第２グループ１２８の４つの子ノードは、第１グループと正対している。従って、第２グループ１２８の４つの子ノードで現在の親ノード１２２の側面を形成し、当該側面は、隣接親ノード１２４と現在の親ノード１２２との間の共通面である側面と正対している。換言すれば、第１グループ１２６の子ノードと第２グループ１２８の子ノードとにより、現在の子ノード１２０の両側にあり、考慮される軸に垂直な平面が定義される。従って、この２つの平面により、コンテキスト情報の確実な決定を提供することができる。点群における、現在の子ノード１２０を通過する表面は、第１グループ１２６又は第２グループ１２８により定義された平面のいずれかを通過する可能性が高いため、現在の子ノード１２０のコンテキスト情報は、第１グループ１２６の占有及び／又は第２グループ１２８の占有に大きく依存する。

一般的に、現在の平面位置が低平面位置であれば、第１グループの少なくとも１つの子ノードが占有されており、第２グループが占有されていない場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。第１グループが占有されておらず、第２グループの少なくとも１つの子ノードが占有されている場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。第１グループが占有されておらず、第２グループも占有されていない場合、平面コンテキスト情報は平面の可能性を含み、ただし、隣接親ノードにおいて第１グループに属しない少なくとも１つ又は複数の子ノードが占有されている場合、平面位置コンテキスト情報は低平面の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ（未知）」である。第１グループの少なくとも１つの子ノードが占有されており、第２グループの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＞＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、低平面位置の可能性を含む。第１グループの少なくとも１つの子ノードが占有されており、第２グループの少なくとも１つの子ノードも占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＜＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、高平面位置の可能性を含む。ただし、＃ＦｉｒｓｔＧｒｏｕｐは第１グループの占有ノードの数を示し、＃ＳｅｃｏｎｄＧｒｏｕｐは第２グループの占有ノードの数を示す。

より具体的には、Ｘ軸に沿った評価及び図４に示す番号付けシステムについては以下となる。
・第１グループの子ノード４～７のうちの少なくとも１つの子ノードが占有されており、第２グループの子ノード４～７が占有されていない場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、低平面位置の可能性を含む。
・第１グループの子ノード４～７が占有されておらず、第２グループの子ノード４～７のうちの少なくとも１つの子ノードが占有されている場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、高平面位置の可能性を含む。
・第１グループの子ノード４～７が占有されておらず、第２グループの子ノード４～７が占有されていない場合、平面コンテキスト情報は、平面の可能性を含み、ただし、隣接親ノードにおける少なくとも１つ又は複数の子ノード０～３は占有されている場合、平面位置コンテキスト情報は、低平面の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ」である。
・第１グループの子ノード４～７のうちの少なくとも１つの子ノードが占有されており、第２グループの子ノード４～７のうちの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＞＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、低平面位置の可能性を含む。
・第１グループの子ノード４～７のうちの少なくとも１つの子ノードが占有されており、第２グループの子ノード４～７のうちの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＜＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、高平面位置の可能性を含む。

従って、符号化について、低位置である現在の平面位置に対してエントロピー符号化を実行する場合、現在の子ノードにＸ軸に垂直な平面が存在するか又は存在しない確率はコンテキスト情報と見なされる。ただし、当該情報は平面符号化方式と角度符号化方式における平面コンテキスト情報として用いられてもよく、平面符号化方式における平面位置コンテキスト情報として含まれてもよい。

現在の子ノード１２０の平面コンテキスト情報を決定するために、図７（ｂ）に基づいてＹ軸に沿って評価することは、以下のように設定される。
・第１グループの子ノード２、３、６、７のうちの少なくとも１つの子ノードが占有されており、第２グループの子ノード２、３、６、７が占有されていない場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、低平面位置の可能性を含む。
・第１グループの子ノード２、３、６、７が占有されておらず、第２グループの子ノード２、３、６、７のうちの少なくとも１つの子ノードが占有されている場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、高平面位置の可能性を含む。
・第１グループの子ノード２、３、６、７が占有されておらず、第２グループの子ノード２、３、６、７が占有されていない場合、平面コンテキスト情報は、平面の可能性を含み、ただし、隣接親ノードにおける少なくとも１つ又は複数の子ノード０、１、４、５が占有されている場合、平面位置コンテキスト情報は、低平面の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ」である。
・第１グループの子ノード２、３、６、７のうちの少なくとも１つの子ノードが占有されており、第２グループの子ノード２、３、６、７のうちの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＞＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、低平面位置の可能性を含む。
・第１グループの子ノード２、３、６、７のうちの少なくとも１つの子ノードが占有されており、第２グループの子ノード２、３、６、７のうちの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＜＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、高平面位置の可能性を含む。

従って、符号化について、低位置である現在の平面位置に対してエントロピー符号化を実行する場合、現在の子ノードにＹ軸に垂直な平面が存在するか又は存在しない確率はコンテキスト情報と見なされる。ただし、当該情報は平面符号化方式と角度符号化方式における平面コンテキスト情報として用いられてもよく、平面符号化方式における平面位置コンテキスト情報として含まれてもよい。

現在の子ノード１２０の平面コンテキスト情報を決定するために、図７（ｃ）に基づいてＺ軸に沿って評価することは、以下のように設定される。
・第１グループの子ノード１、３、５、７のうちの少なくとも１つの子ノードが占有されており、第２グループの子ノード１、３、５、７が占有されていない場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、低平面位置の可能性を含む。
・第１グループの子ノード１、３、５、７が占有されておらず、第２グループの子ノード１、３、５、７のうちの少なくとも１つの子ノードが占有されている場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、高平面位置の可能性を含む。
・第１グループの子ノード１、３、５、７が占有されておらず、第２グループの子ノード１、３、５、７が占有されていない場合、平面コンテキスト情報は、平面の可能性を含み、ただし、隣接親ノードにおける少なくとも１つ又は複数の子ノード０、２、４、６は占有されている場合、平面位置コンテキスト情報は、低平面位置の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ」である。
・第１グループの子ノード１、３、５、７のうちの少なくとも１つの子ノードが占有されており、第２グループの子ノード１、３、５、７のうちの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＞＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、低平面位置の可能性を含む。
・第１グループの子ノード１、３、５、７のうちの少なくとも１つの子ノードが占有されており、第２グループの子ノード１、３、５、７のうちの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＜＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、高平面位置の可能性を含む。

従って、符号化について、低位置である現在の平面位置に対してエントロピー符号化を実行する場合、現在の子ノードにＺ軸に垂直な平面が存在するか又は存在しない確率はコンテキスト情報と見なされる。ただし、当該情報は平面符号化方式と角度符号化方式における平面コンテキスト情報として用いられてもよく、平面符号化方式における平面位置コンテキスト情報として含まれてもよい。

以上に示すように、符号化すべき現在の子ノードの現在の平面位置が高平面位置であれば、状況が異なる。そして、現在の子ノードに隣接する隣接親ノードは、符号化順において現在の親ノードの後にある。この場合、隣接親ノードの子ノードの占有は未知であり、隣接親ノード自身の占有のみを使用してコンテキスト情報を決定してもよい。

特に、現在の平面位置が高平面位置であれば、平面コンテキスト情報及び平面位置コンテキスト情報は、考慮される軸に沿った現在の親ノードの直後の隣接親ノードの占有、及び考慮される軸に垂直な平面にあり、現在の子ノードに直接隣接する、現在の親ノードの４つの子ノードのグループの占有に基づいて決定される。換言すれば、現在の親ノードの共通表面に直接隣接する隣接親ノードの子ノードの占有は、復号順によって通常不明である。従って、現在の子ノードと共通表面を共有する隣接親ノード自身の占有は、現在の親ノード１２２内の、現在の親ノード１２２の反対側に直接隣接して配置される（すなわち、隣接親ノード１３０に対向する）グループ１３２と共に使用される。好ましくは、当該グループ１３２は、４つの子ノードによって１つの平面が定義され、当該平面は、考慮される幾何軸に垂直であり、現在の親ノード内の評価すべき現在の子ノードに直接隣接する。

一般的に、現在の平面位置が高平面位置であれば、当該グループ１３２の少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されていない場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。当該グループ１３２が占有されておらず、隣接親ノード１３０が占有されている場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。当該グループ１３２が占有されておらず、隣接親ノード１３０が占有されていない場合、平面コンテキスト情報は平面の可能性を含み、ただし、考慮される軸に沿った現在の親ノード１２２の直前の隣接親ノード１３４における少なくとも１つ又は複数の子ノード１３６が占有されている場合、平面位置コンテキスト情報は低平面の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ」である。当該グループ１３２の少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、＃Ｇｒｏｕｐ＞２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。当該グループ１３２の少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、＃Ｇｒｏｕｐ＜２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。当該グループ１３２の少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、＃Ｇｒｏｕｐ＝２である場合、平面コンテキスト情報は平面が存在しない可能性を含み、それにより平面位置が未知である。＃Ｇｒｏｕｐは該グループ１３２における占有子ノードの数を示す。

より具体的には、図８（ａ）を参照してＸ軸に沿って評価することは以下となる。
・当該グループ１３２の子ノード０～３のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されていない場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。
・当該グループ１３２の子ノード０～３が占有されておらず、隣接親ノード１３０が占有されている場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。
・当該グループ１３２の子ノード０～３が占有されておらず、隣接親ノード１３０が占有されていない場合、平面コンテキスト情報は平面の可能性を含み、ただし、考慮される軸に沿った現在の親ノード１２２の直前の隣接親ノード１３４における少なくとも１つ又は複数の子ノード４～７が（図９（ａ）に示されたように）占有されている場合、平面位置コンテキスト情報は低平面の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ」である。
・当該グループ１３２の子ノード０～３のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、かつ＃Ｇｒｏｕｐ＞２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。
・当該グループ１３２の子ノード０～３のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、＃Ｇｒｏｕｐ＜２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。
・当該グループ１３２の子ノード０～３のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、＃Ｇｒｏｕｐ＝２である場合、平面コンテキスト情報は平面が存在しない可能性を含み、それにより平面位置が未知と推定される。＃Ｇｒｏｕｐは該グループにおける占有子ノードの数を示す。

従って、符号化について、高位置である現在の平面位置に対してエントロピー符号化を実行する場合、現在の子ノード１２０にＸ軸に垂直な平面が存在するか又は存在しない確率はコンテキスト情報と見なされる。ただし、当該情報は平面符号化方式と角度符号化方式における平面コンテキスト情報として用いられてもよく、平面符号化方式における平面位置コンテキスト情報として含まれてもよい。

現在の子ノード１２０の平面コンテキスト情報を決定するために、図８（ｂ）に基づいてＹ軸に沿って評価することは、以下のように設定される。
・当該グループ１３２の子ノード０、１、４、５のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されていない場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。
・当該グループ１３２の子ノード０、１、４、５が占有されておらず、隣接親ノード１３０が占有されている場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。
・当該グループ１３２の子ノード０、１、４、５が占有されておらず、隣接親ノード１３０が占有されていない場合、平面コンテキスト情報は平面の可能性を含み、ただし、考慮される軸に沿った現在の親ノード１２２の直前の隣接親ノード１３４における少なくとも１つ又は複数の子ノード２、３、６、７が（図９（ｂ）に示されたように）占有されている場合、平面位置コンテキスト情報は低平面の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ」である。
・当該グループ１３２の子ノード０、１、４、５のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、＃Ｇｒｏｕｐ＞２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。
・当該グループ１３２の子ノード０、１、４、５のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、＃Ｇｒｏｕｐ＜２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。
・当該グループ１３２の子ノード０、１、４、５のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、かつ＃Ｇｒｏｕｐ＝２である場合、平面コンテキスト情報は平面が存在しない可能性を含み、それにより平面位置が未知と推定される。＃Ｇｒｏｕｐは当該グループにおける占有子ノードの数を示す。

従って、符号化について、高位置である現在の平面位置に対してエントロピー符号化を実行する場合、現在の子ノード１２０にＹ軸に垂直な平面が存在するか又は存在しない確率はコンテキスト情報と見なされる。ただし、当該情報は平面符号化方式と角度符号化方式における平面コンテキスト情報として用いられてもよく、平面符号化方式における平面位置コンテキスト情報として含まれてもよい。

現在の子ノード１２０の平面コンテキスト情報を決定するために、図８（ｃ）に基づいてＺ軸に沿って評価することは、以下のように設定される。
・当該グループ１３２の子ノード０、２、４、６のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されていない場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。
・当該グループ１３２の子ノード０、２、４、６が占有されておらず、隣接親ノード１３０が占有されている場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。
・当該グループ１３２の子ノード０、２、４、６が占有されておらず、隣接親ノード１３０が占有されていない場合、平面コンテキスト情報は平面の可能性を含み、ただし、考慮される軸に沿った現在の親ノード１２２の直前の隣接親ノード１３４における少なくとも１つ又は複数の子ノード１、３、５、７が（図９（ｃ）に示されたように）占有されている場合、平面位置コンテキスト情報は低平面の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ」である。
・当該グループ１３２の子ノード０、２、４、６のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、＃Ｇｒｏｕｐ＞２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。
・当該グループ１３２の子ノード０、２、４、６のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、＃Ｇｒｏｕｐ＜２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。
・当該グループ１３２の子ノード０、２、４、６のうちの少なくとも１つの子ノードが占有されており、隣接親ノード１３０が占有されており、＃Ｇｒｏｕｐ＝２である場合、平面コンテキスト情報は平面が存在しない可能性を含み、それにより平面位置が未知と推定される。＃Ｇｒｏｕｐは当該グループにおける占有子ノードの数を示す。

従って、符号化について、高位置である現在の平面位置に対してエントロピー符号化を実行する場合、現在の子ノード１２０にＺ軸に垂直な平面が存在するか又は存在しない確率はコンテキスト情報と見なされる。ただし、当該情報は平面符号化方式と角度符号化方式における平面コンテキスト情報として用いられてもよく、平面符号化方式における平面位置コンテキスト情報として含まれてもよい。

要するに、すべての場合において、いずれもエントロピー符号化に用いることができる信頼性の高い平面コンテキスト情報モデルが構築され、それにより各ノードにおける表面又は平面の発生を考慮し、この知識を利用して、エントロピーエンコーダ／デコーダによるデータ圧縮のために、ノードの占有を有効に予測する。

いくつかの場合において、上記したコンテキスト情報のセットの実現は不可能又は無意味である。従って、平面符号化方式における平面位置コンテキスト情報について、同一座標、同一深さで最も近い符号化されたノードが平面でないか、又は存在しない場合、現在のＧＰＣＣ仕様では、特定のコンテキストモデルを用いることを提案し、当該モデルはａｘｉｓＩｄｘ文（値＝０、１、２）を利用してｐｌａｎｅＰｏｓｉｔｉｏｎを符号化するための平面に垂直な軸を識別する。しかし、この方法には、隣接ノードの占有による情報が無視された。本発明によれば、依然として現在の子ノードと同一の親ノード内にあり、考慮される軸に垂直な同一平面内における隣接子ノードの占有に基づいて推定を行うことができる。例えば、Ｘ軸を考慮し、現在の子ノードが座標２にある場合、現在の親ノード内にあり、Ｘ軸に垂直な同一垂直面内における子ノード０、１の情報は既知であり、平面位置コンテキスト情報の決定に用いることができ、例えば、これらのノードのうちの１つ又はこれらのノードの大多数の平面位置コンテキスト情報を、符号化すべき現在の子ノードの平面位置コンテキスト情報として用いる。例えば、Ｘ軸を考慮し、現在の子ノードが座標７にある場合、現在の親ノード内にあり、Ｘ軸に垂直な同一垂直面内における子ノード４～６の情報が既知であり、平面位置コンテキスト情報の決定に用いることができる。従って、同一座標かつ同一深さＤで最も近い符号化されたノードが存在しない場合、平面位置コンテキスト情報は、提出されたａｘｉｓＩｄｘ文を置き換えることができ、より効率的なエントロピー符号化のために改善されたコンテキスト情報を提供する。従って、以上に提出された平面符号化方式での平面位置コンテキスト情報に用いられるコンテキストモデルは、以下に置き換えられる。
ａ）少なくとも１つの隣接ノードの占有に基づく現在の子ノードの平面位置。

また、角度符号化方式について、すなわち点群は角度符号化方式により符号化されることが指示されたとしても、当該点群の１つ又は複数のノードが当該符号化方式に適合しない可能性がある。この場合、角度符号化方式の平面位置コンテキスト情報は、上述したように、平面方式に基づく平面位置コンテキスト情報に置き換えられる。

図１０（ａ）を参照し、点群を符号化する方法が示され、当該方法は、
符号化方式を決定するステップであって、符号化方式は平面符号化方式と角度符号化方式とを含むステップ（ステップ１０）と、
現在の子ノードの符号化コンテキスト情報を取得するステップ（ステップ１１）であって、
符号化方式が平面符号化方式であれば、符号化コンテキスト情報は平面コンテキスト情報を含み、現在の子ノードの平面コンテキスト情報は現在の親ノードの占有と、現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有とに基づいて決定され（ステップ１１１）、
符号化方式が角度符号化方式であれば、現在の子ノードの符号化コンテキスト情報は現在の親ノードの平面情報と、現在の親ノードに隣接する垂直隣接親ノードの占有とを含む（ステップ１１２）ステップと、
決定された符号化コンテキスト情報に基づいて、現在の子ノードをエントロピー符号化してビットストリームの符号化データを生成するステップ（ステップ１２）とを含む。

図１０（ｂ）を参照し、点群を復号する方法が示され、当該方法は、
符号化方式を決定するステップであって、符号化方式は平面符号化方式と角度符号化方式とを含むステップ（ステップ２０）と、
現在の子ノードの符号化コンテキスト情報を取得するステップ（ステップ２１）であって、
符号化方式が平面符号化方式であれば、符号化コンテキスト情報は平面コンテキスト情報を含み、現在の子ノードの平面コンテキスト情報は現在の親ノードの占有と、現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有とに基づいて決定され（ステップ２１１）、
符号化方式が角度符号化方式であれば、現在の子ノードの符号化コンテキスト情報は現在の親ノードの平面情報と、現在の親ノードに隣接する垂直隣接親ノードの占有とを含む（ステップ２１２）ステップと、
現在の子ノードのコンテキスト情報に基づいてビットストリームをエントロピー復号して点群を再構築するステップ（ステップ２２）と、を含む。

従って、本発明によれば、隣接ノードに関する情報を使用、評価することでコンテキスト情報モデルを取得し、それにより現在の子ノード内の表面の発生をより確実に予測する。当該情報は、圧縮点群データのデータ量を低減するために用いられることができ、同じコンテキスト情報モデルはデコーダにも用いられ、それにより提供されたビットストリームを高効率かつ高精度に、確実に復号することができる。従って、従来の符号化方法及び現在のＧＰＣＣ仕様に比べ、少なくとも１％の大幅なデータ削減を達成することができる。しかし、この値は点の密度に依存しており、特にＬｉＤＡＲ点群のような屋内の点群については、密な点群とみなすことができると仮定される。

符号化又は復号方法の実施例において、符号化方式は平面符号化方式であれば、符号化コンテキスト情報は平面コンテキスト情報を含み、平面コンテキスト情報は、現在の親ノードの占有パターンと現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンとに基づく平面の存在を含む。

符号化方法又は復号方法の実施例において、符号化方式は平面符号化方式であれば、符号化コンテキスト情報は平面位置コンテキストを含み、平面位置コンテキスト情報は、
現在の子ノードと、八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードとの間の距離ｄと、
八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードの平面位置と、
現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンに基づいて決定された現在の子ノードの平面位置と
のうちの１つ又は複数を含む。

符号化方法又は復号方法の実施例において、八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードが存在しなければ、平面位置コンテキスト情報は、現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンに基づいて決定された前記現在の子ノードの平面位置のみを含む。

符号化方法又は復号方法の実施例において、符号化方式は角度符号化方式であれば、符号化コンテキスト情報は平面コンテキストを含み、平面コンテキスト情報は、
現在の親ノードのｉｓＰｌａｎａｒフラグと、
現在の親ノードに直接隣接する垂直隣接親ノード（すなわち、考慮される軸に垂直で、復号順において現在の親ノードの直前にある）の占有と、のうちの１つ又は複数を含む。

符号化方法又は復号方法の実施例において、符号化方式が角度符号化方式であり、現在の子ノードに角度符号化方式が適用しない場合、符号化コンテキスト情報は、平面位置コンテキスト情報を含み、平面位置コンテキスト情報は、
現在の子ノードと、八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードとの間の距離ｄと、
八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードの平面位置と、
現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンに基づいて決定された現在の子ノードの平面位置と
のうちの１つ又は複数を含む。

符号化方法又は復号方法の実施例において、少なくとも１つの隣接親ノードの占有パターンに基づいて平面コンテキスト情報及び平面位置コンテキスト情報を決定するために、現在の親ノードに対する現在の子ノードの平面位置が決定され、現在の平面位置は、高平面位置及び低平面位置を含む。

符号化方法又は復号方法の実施例において、現在の平面位置が低平面位置であれば、平面コンテキスト情報及び平面位置コンテキスト情報は、隣接親ノードの現在の親ノードに直接隣接する第１グループの４つの子ノードの占有と、現在の親ノードの第１グループに正対する第２グループの４つの子ノードの占有とに基づいて決定される。

符号化方法又は復号方法の実施例において、現在の平面位置が低平面位置であれば、第１グループの少なくとも１つの子ノードが占有されており、第２グループが占有されていない場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。

符号化方法又は復号方法の実施例において、現在の平面位置が低平面位置であれば、第１グループが占有されておらず、第２グループの少なくとも１つの子ノードが占有されている場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。

符号化方法又は復号方法の実施例において、現在の平面位置が低平面位置であれば、第１グループが占有されておらず、第２グループが占有されていない場合、平面コンテキスト情報は平面の可能性を含み、ただし、隣接親ノードにおいて第１グループに属しない少なくとも１つ又は複数の子ノードが占有されている場合、平面位置コンテキスト情報は低平面の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ」である。

符号化方法又は復号方法の実施例において、現在の平面位置が低平面位置であれば、第１グループの少なくとも１つの子ノードが占有されており、第２グループの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＞＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、低平面位置の可能性を含み、ただし、＃ＦｉｒｓｔＧｒｏｕｐは第１グループの占有ノードの数を示し、＃ＳｅｃｏｎｄＧｒｏｕｐは第２グループの占有ノードの数を示す。

符号化方法又は復号方法の実施例において、現在の平面位置が低平面位置であれば、第１グループの少なくとも１つの子ノードが占有されており、第２グループの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＜＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、平面コンテキスト情報は、平面の可能性を含み、平面位置コンテキスト情報は、高平面位置の可能性を含み、ただし、＃ＦｉｒｓｔＧｒｏｕｐは第１グループの占有ノードの数を示し、＃ＳｅｃｏｎｄＧｒｏｕｐは第２グループの占有ノードの数を示す。

符号化方法又は復号方法の実施例において、現在の平面位置が高平面位置であれば、平面コンテキスト情報及び平面位置コンテキスト情報は、考慮される軸に沿った前記現在の親ノードの直後の前記隣接親ノードの占有率、及び考慮される軸に垂直な平面にあり、前記現在の子ノードに直接隣接する、前記現在の親ノードの４つの子ノードのグループの占有に基づいて決定される。

符号化方法又は復号方法の実施例において、現在の平面位置が高平面位置であれば、当該グループの少なくとも１つの子ノードが占有されており、隣接親ノードが占有されていない場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含む。

符号化方法又は復号方法の実施例において、現在の平面位置が高平面位置であれば、当該グループが占有されておらず、隣接親ノードが占有されている場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含む。

符号化方法又は復号方法の実施例において、現在の平面位置が高平面位置であれば、当該グループが占有されておらず、隣接親ノードが占有されていない場合、平面コンテキスト情報は平面の可能性を含み、ただし、考慮される軸に沿った現在の親ノードの直前の隣接親ノードにおける少なくとも１つ又は複数の子ノードが占有されている場合、平面位置コンテキスト情報は低平面の可能性を含み、そうでなければ、「ＵＮＫＮＯＷＮ」である。

符号化方法又は復号方法の実施例において、現在の平面位置が高平面位置であれば、当該グループの少なくとも１つの子ノードが占有されており、隣接親ノードが占有されており、＃Ｇｒｏｕｐ＞２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は低平面位置の可能性を含み、＃Ｇｒｏｕｐは、当該グループにおける占有ノードの数を示す。

符号化方法又は復号方法の実施例において、現在の平面位置が高平面位置であれば、当該グループの少なくとも１つの子ノードが占有されており、隣接親ノードが占有されており、＃Ｇｒｏｕｐ＜２である場合、平面コンテキスト情報は平面の可能性を含み、平面位置コンテキスト情報は高平面位置の可能性を含み、＃Ｇｒｏｕｐは、当該グループにおける占有ノードの数を示す。

符号化方法又は復号方法の実施例において、現在の平面位置が高平面位置であれば、当該グループの少なくとも１つの子ノードが占有されており、隣接親ノードが占有されており、＃Ｇｒｏｕｐ＝２である場合、平面コンテキスト情報は平面が存在しない可能性を含み、平面位置は未知と推定され、＃Ｇｒｏｕｐは、当該グループにおける占有ノードの数を示す。

符号化方法又は復号方法の実施例において、隣接親ノードは幾何軸の１つに沿って配置される。

符号化方法又は復号方法の実施例において、３つの幾何軸のすべてに沿って平面コンテキスト情報を決定する。

符号化方法又は復号方法の実施例において、現在の親ノードは、復号順に従って隣接親ノードと相対的に配置される。

好ましい実施例において、点群を符号化／復号することにより圧縮点群データのビットストリームを生成する方法は、ＬＩＤＡＲ（光検出及び測距）デバイスで実現される。ＬＩＤＡＲデバイスは光伝送モジュールとセンサモジュールとを備える。光伝送モジュールは、レーザ光で環境をスキャンするように設定され、環境内のオブジェクトによって反射されたレーザ光のエコー（ｅｃｈｏ）は、センサモジュールのセンサで測定される。また、ＬＩＤＡＲデバイスは評価モジュールを備え、当該評価モジュールは、好ましくはレーザ光の戻り時間及び／又は反射されたレーザ光の波長の差異により環境の点群における３Ｄ表現を決定する。従って、エコーはオブジェクト又は環境の数百万個の位置情報点を含み得、それにより大型の点群になり、当該点群をさらに処理したり評価したりするための計算デバイスへの要求が高くなる。例えば自動運転の特定のアプリケーションにおいて、安全のため、ＬＩＤＡＲ点群の処理はほぼリアルタイムでなければならない。従って、点群データを効果的かつ正確に圧縮することは必要である。従って、ＬＩＤＡＲデバイスはエンコーダを備えてもよく、当該エンコーダはプロセッサ及びメモリ記憶デバイスを備える。メモリ記憶デバイスは、命令を含むコンピュータプログラム又はアプリケーションを記憶してもよく、該命令が実行されると、プロセッサに本明細書に記載のような操作を実行させる。例えば、命令は本発明に記載の方法に基づいて符号化し、符号化されたビットストリームを出力してもよい。追加的又は代替的に、ＬＩＤＡＲデバイスはデコーダを備えてもよく、該デコーダはプロセッサ及びメモリ記憶デバイスを備える。メモリ記憶デバイスは命令を含むコンピュータプログラム又はアプリケーションを記憶してもよく、該命令が実行されると、プロセッサに本明細書に記載のような操作を実行させる。従って、エンコーダ／デコーダにより、点群データを効果的かつ正確に圧縮することができ、それにより取得した点群データをより効果的に、好ましくはリアルタイムで処理する確率を提供する。好ましくは、エンコーダのプロセッサとデコーダのプロセッサは同じである。好ましくは、エンコーダのメモリ記憶デバイスとデコーダのメモリ記憶デバイスは同じである。好ましくは、エンコーダ及び／又はデコーダのプロセッサは点群をさらに処理するか又は評価するように設定され、さらに、好ましくは、点群をリアルタイムで処理するか又は評価するように設定される。特に、自動運転の例について、点群の評価は運転方向における障害物の判定を含んでもよい。

図１１を参照し、エンコーダ１１００の例示的な実施例の簡略化ブロック図を示す。エンコーダ１１００は、プロセッサ１１０２と、メモリ記憶デバイス１１０４とを備える。メモリ記憶デバイス１１０４は命令を含むコンピュータプログラム又はアプリケーションを記憶してもよく、該命令が実行されると、プロセッサ１１０２に本明細書に記載のような操作を実行させる。例えば、命令は本発明に記載の方法に基づいて符号化し、符号化されたビットストリームを出力してもよい。理解すべきことは、命令が非一時的なコンピュータ可読媒体に記憶されてもよく、例えばコンパクトディスク、フラッシュメモリデバイス、ランダムアクセスメモリ、ハードディスクドライブなどであってもよい。命令が実行されると、プロセッサ１１０２は、命令に指定された操作及び機能を実行し、それにより、上記処理を実現する専用プロセッサとして用いられる。いくつかの例示において、このようなプロセッサは「プロセッサ電気回路」又は「プロセッサ回路」と呼ばれてもよい。

図１２を参照し、デコーダ１２００の例示的な実施例の簡略化ブロック図を示す。デコーダ１２００は、プロセッサ１２０２と、メモリ記憶デバイス１２０４とを備える。メモリ記憶デバイス１２０４は命令を含むコンピュータプログラム又はアプリケーションを記憶してもよく、該命令が実行されると、プロセッサ１２０２に本明細書に記載のような操作を実行させる。理解すべきことは、命令が非一時的なコンピュータ可読媒体に記憶されてもよく、例えばコンパクトディスク、フラッシュメモリデバイス、ランダムアクセスメモリ、ハードディスクドライブなどであってもよい。命令が実行されると、プロセッサ１２０２は、命令に指定された操作及び機能を実行し、それにより、上記処理を実現する専用プロセッサとして用いられる。いくつかの例示において、このようなプロセッサは「プロセッサ電気回路」又は「プロセッサ回路」と呼ばれてもよい。

理解すべきことは、本発明に係るエンコーダ及び／又はデコーダは複数の計算デバイスにおいて実現されてもよく、サーバ、適切にプログラミングされた汎用コンピュータ、マシンビジョンシステム及び移動デバイスを含むがこれらに限定されない。エンコーダ又はデコーダは、本発明に記載された機能を実行するための、１つ又は複数のプロセッサを設定するための命令を含むソフトウェアによって実現されてもよい。ソフトウェア命令は任意の適切な非一時的なコンピュータ可読メモリに記憶されてもよく、ＣＤ、ＲＡＭ、ＲＯＭ、フラッシュメモリ等を含む。

理解すべきことは、本発明に記述されたエンコーダ及び／又はデコーダと、記述されたエンコーダ又はデコーダを設定するための方法／処理を実現するモジュール、ルーチン、処理、スレッド又は他のソフトウェアコンポーネントは標準的なコンピュータプログラミング技術及び言語を使用して実現されてもよい。本発明は特定のプロセッサ、コンピュータ言語、コンピュータプログラミングプロトコル、データ構造、他のこのような実現の詳細に限定されない。当業者であれば理解されるように、説明された処理は揮発性又は不揮発性メモリに記憶されたコンピュータ実行可能なコードの一部、専用集積チップ（ＡＳＩＣ）の一部等として実現されてもよい。

また、本発明は、本発明に係る符号化処理の適用により生成されたデータを符号化するコンピュータ可読信号を提供する。

本発明の１態様において、点群を符号化して圧縮点群データのビットストリームを生成するための符号化方法を提供し、前記点群のジオメトリは八分木ベース構造によって表現され、前記八分木ベース構造は、前記点群を含むボリューム空間をサブボリュームに再帰的に分割することにより、親子関係を有する複数のノードを含み、各前記サブボリュームは前記八分木ベース構造のノードに関連し、前記方法は、
符号化方式を決定するステップと、
現在の子ノードの符号化コンテキスト情報を取得するステップと、
決定された符号化コンテキスト情報に基づいて、前記現在の子ノードの占有をエントロピー符号化して前記ビットストリームの符号化データを生成するステップとを含む。

好ましくは、符号化方式は平面符号化方式と角度符号化方式とを含む。

好ましくは、符号化方式が平面符号化方式であれば、符号化コンテキスト情報は平面コンテキスト情報を含む。

好ましくは、現在の子ノードの平面コンテキスト情報は、現在の親ノードの占有パターンと、現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンとに基づいて決定される。

好ましくは、符号化方式が角度符号化方式であれば、現在の子ノードの符号化コンテキスト情報は現在の親ノードの平面情報と、現在の親ノードに隣接する垂直隣接親ノードの占有とを含む。

本発明の１態様において、圧縮点群データのビットストリームを復号して再構成点群を生成するための方法を提供し、点群のジオメトリは八分木ベース構造によって表現され、前記八分木ベース構造は、前記点群を含むボリューム空間をサブボリュームに再帰的に分割することにより、親子関係を有する複数のノードを含み、各前記サブボリュームは前記八分木ベース構造のノードに関連し、前記方法は、
符号化方式を決定するステップと、
現在の子ノードの符号化コンテキスト情報を取得するステップと、
現在の子ノードの符号化コンテキスト情報に基づいて、ビットストリームをエントロピー復号して点群を再構成するステップとを含む。

好ましくは、符号化方式は平面符号化方式と角度符号化方式とを含む。

好ましくは、符号化方式が平面符号化方式であれば、符号化コンテキスト情報は平面コンテキスト情報を含む。

好ましくは、現在の子ノードの平面コンテキスト情報は、現在の親ノードの占有パターンと、現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンとに基づいて決定される。

好ましくは、符号化方式が角度符号化方式であれば、現在の子ノードの符号化コンテキスト情報は現在の親ノードの平面情報と、現在の親ノードに隣接する垂直隣接親ノードの占有とを含む。

記述された実施例に対していくつかの調整及び修正を行ってもよい。従って、以上に説明された実施例は例示的であり、限定的ではないと考えられる。特に、実施例は互いに自由に組み合わせることができる。

Claims (15)

1. 点群を符号化して圧縮点群データのビットストリームを生成するための符号化方法であって、
   前記点群のジオメトリは八分木ベース構造によって表現され、前記八分木ベース構造は、前記点群を含むボリューム空間をサブボリュームに再帰的に分割することにより、親子関係を有する複数のノードを含み、各前記サブボリュームは前記八分木ベース構造のノードに関連し、
   符号化方式を決定するステップであって、前記符号化方式は平面符号化方式と角度符号化方式とを含むステップと、
   現在の子ノードの符号化コンテキスト情報を取得するステップであって、
   前記符号化方式が前記平面符号化方式であれば、前記現在の子ノードの符号化コンテキスト情報は平面コンテキスト情報を含み、前記現在の子ノードの平面コンテキスト情報は現在の親ノードの占有パターンと、前記現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンとに基づいて決定され、
   前記符号化方式が前記角度符号化方式であれば、前記現在の子ノードの符号化コンテキスト情報は前記現在の親ノードの平面情報と、前記現在の親ノードに隣接する垂直隣接親ノードの占有とを含むステップと、
   決定された符号化コンテキスト情報に基づいて、前記現在の子ノードをエントロピー符号化して前記ビットストリームの符号化データを生成するステップと、を含むことを特徴とする符号化方法。
2. 圧縮点群データのビットストリームを復号して再構成点群を生成するための復号方法であって、
   点群のジオメトリは八分木ベース構造によって表現され、前記八分木ベース構造は、前記点群を含むボリューム空間をサブボリュームに再帰的に分割することにより、親子関係を有する複数のノードを含み、各前記サブボリュームは前記八分木ベース構造のノードに関連し、
   符号化方式を決定するステップであって、前記符号化方式は平面符号化方式と角度符号化方式とを含むステップと、
   現在の子ノードの符号化コンテキスト情報を取得するステップであって、
   前記符号化方式が前記平面符号化方式であれば、前記現在の子ノードの符号化コンテキスト情報は平面コンテキスト情報を含み、前記現在の子ノードの平面コンテキスト情報は現在の親ノードの占有パターンと、前記現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンとに基づいて決定され、
   前記符号化方式が前記角度符号化方式であれば、前記現在の子ノードの符号化コンテキスト情報は前記現在の親ノードの平面情報と、前記現在の親ノードに隣接する垂直隣接親ノードの占有とを含むステップと、
   前記現在の子ノードの符号化コンテキスト情報に基づいて、前記ビットストリームをエントロピー復号して前記点群を再構成するステップと、を含むことを特徴とする復号方法。
3. 前記符号化方式が前記平面符号化方式であれば、前記符号化コンテキスト情報は平面位置コンテキスト情報を含み、
   前記平面位置コンテキスト情報は、
   前記現在の子ノードと、前記八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードとの間の距離ｄと、
   前記八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードの平面位置と、
   前記現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンに基づいて決定された前記現在の子ノードの平面位置と
   のうちの１つ又は複数を含むことを特徴とする請求項１に記載の方法。
4. 前記八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードが存在しなければ、前記平面位置コンテキスト情報は、前記現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンに基づいて決定された前記現在の子ノードの平面位置のみを含むことを特徴とする請求項３に記載の方法。
5. 前記符号化方式が前記角度符号化方式であり、前記現在の子ノードに前記角度符号化方式が適用しない場合、前記符号化コンテキスト情報は前記平面位置コンテキスト情報を含み、
   前記平面位置コンテキスト情報は、
   前記現在の子ノードと、前記八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードとの間の距離ｄと、
   前記八分木ベース構造における同じ深さＤでの、対応する親ノードにおける同じ座標での最も近い符号化されたノードの平面位置と、
   前記現在の親ノードに直接隣接する少なくとも１つの隣接親ノードの占有パターンに基づいて決定された前記現在の子ノードの平面位置と
   のうちの１つ又は複数を含むことを特徴とする請求項３又は４に記載の方法。
6. 前記少なくとも１つの隣接親ノードの占有パターンに基づいて、前記平面コンテキスト情報及び前記平面位置コンテキスト情報を決定するために、前記現在の親ノードに対する前記現在の子ノードの現在の平面位置が決定され、前記現在の平面位置は高平面位置と低平面位置とを含むことを特徴とする請求項３又は４に記載の方法。
7. 前記現在の平面位置が低平面位置であれば、
   前記平面コンテキスト情報及び前記平面位置コンテキスト情報は、
   前記隣接親ノードの前記現在の親ノードに直接隣接する第１グループの４つの子ノードの占有と、
   前記現在の親ノードの前記第１グループに正対する第２グループの４つの子ノードの占有とに基づいて決定されることを特徴とする請求項６に記載の方法。
8. 前記第１グループの少なくとも１つの子ノードが占有されており、前記第２グループが占有されていない場合、前記平面コンテキスト情報は平面の可能性を含み、前記平面位置コンテキスト情報は低平面位置の可能性を含み、又は
   前記第１グループが占有されておらず、前記第２グループの少なくとも１つの子ノードが占有されている場合、前記平面コンテキスト情報は平面の可能性を含み、前記平面位置コンテキスト情報は高平面位置の可能性を含み、又は
   前記第１グループが占有されておらず、前記第２グループが占有されていない場合、前記平面コンテキスト情報は平面の可能性を含み、ただし、前記隣接親ノードにおいて前記第１グループに属しない少なくとも１つ又は複数の子ノードが占有されている場合、前記平面位置コンテキスト情報は低平面の可能性を含み、又は、
   前記第１グループの少なくとも１つの子ノードが占有されており、前記第２グループの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＞＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、前記平面コンテキスト情報は平面の可能性を含み、前記平面位置コンテキスト情報は低平面位置の可能性を含み、又は
   前記第１グループの少なくとも１つの子ノードが占有されており、前記第２グループの少なくとも１つの子ノードが占有されており、＃ＦｉｒｓｔＧｒｏｕｐ＜＃ＳｅｃｏｎｄＧｒｏｕｐ＋１である場合、前記平面コンテキスト情報は平面の可能性を含み、前記平面位置コンテキスト情報は高平面位置の可能性を含み、
   ＃ＦｉｒｓｔＧｒｏｕｐは前記第１グループ内の占有子ノードの数を示し、＃ＳｅｃｏｎｄＧｒｏｕｐは前記第２グループ内の占有子ノードの数を示すことを特徴とする請求項７に記載の方法。
9. 前記現在の平面位置が高平面位置であれば、
   前記平面コンテキスト情報及び前記平面位置コンテキスト情報は、
   考慮される軸に沿った前記現在の親ノードの直後の前記隣接親ノードの占有と、
   考慮される軸に垂直な平面にあり、前記現在の子ノードに直接隣接する、前記現在の親ノードの４つの子ノードのグループの占有とに基づいて決定されることを特徴とする請求項６に記載の方法。
10. 前記グループの少なくとも１つの子ノードが占有されており、前記隣接親ノードが占有されていない場合、前記平面コンテキスト情報は平面の可能性を含み、前記平面位置コンテキスト情報は低平面位置の可能性を含み、又は
    前記グループが占有されておらず、前記隣接親ノードが占有されている場合、前記平面コンテキスト情報は平面の可能性を含み、前記平面位置コンテキスト情報は高平面位置の可能性を含み、又は
    前記グループが占有されておらず、前記隣接親ノードが占有されていない場合、前記平面コンテキスト情報は平面の可能性を含み、ただし、考慮される軸に沿った前記現在の親ノードの直前の隣接親ノードにおける少なくとも１つ又は複数の子ノードが占有されている場合、前記平面位置コンテキスト情報は低平面の可能性を含み、又は
    前記グループの少なくとも１つの子ノードが占有されており、前記隣接親ノードが占有されており、＃Ｇｒｏｕｐ＞２である場合、前記平面コンテキスト情報は平面の可能性を含み、前記平面位置コンテキスト情報は低平面位置の可能性を含み、又は
    前記グループの少なくとも１つの子ノードが占有されており、前記隣接親ノードが占有されており、＃Ｇｒｏｕｐ＜２である場合、前記平面コンテキスト情報は平面の可能性を含み、前記平面位置コンテキスト情報は高平面位置の可能性を含み、又は
    前記グループの少なくとも１つの子ノードが占有されており、前記隣接親ノードが占有されており、＃Ｇｒｏｕｐ＝２である場合、前記平面コンテキスト情報は平面が存在しない可能性を含み、前記平面位置が未知であると推定され、
    ＃Ｇｒｏｕｐはグループにおける占有ノードの数を示すことを特徴とする請求項９に記載の方法。
11. 前記隣接親ノードは、考慮される軸のうちの１つの幾何軸に沿って配置されることを特徴とする請求項１、３又は４に記載の方法。
12. 前記平面コンテキスト情報は３つの幾何軸のすべてに沿って決定されることを特徴とする請求項１、３又は４に記載の方法。
13. 点群を符号化して圧縮点群データのビットストリームを生成するためのエンコーダであって、
    前記点群のジオメトリは八分木ベース構造によって表現され、前記八分木ベース構造は、前記点群を含むボリューム空間をサブボリュームに再帰的に分割することにより、親子関係を有する複数のノードを含み、各前記サブボリュームは前記八分木ベース構造のノードに関連し、
    プロセッサ、及び
    メモリ記憶デバイスを含み、前記メモリ記憶デバイスには前記プロセッサにより実行可能な命令が記憶されており、前記命令が実行されると、前記プロセッサが請求項１及び請求項３～１２のいずれか一項に記載の方法を実行することを特徴とするエンコーダ。
14. 圧縮点群データのビットストリームを復号して再構成点群を生成するためのデコーダであって、
    点群のジオメトリは八分木ベース構造によって表現され、前記八分木ベース構造は、前記点群を含むボリューム空間をサブボリュームに再帰的に分割することにより、親子関係を有する複数のノードを含み、各前記サブボリュームは前記八分木ベース構造のノードに関連し、
    プロセッサ、及び、
    メモリ記憶デバイスを含み、前記メモリ記憶デバイスには前記プロセッサにより実行可能な命令が記憶されており、前記命令が実行されると、前記プロセッサが請求項２に記載の方法を実行することを特徴とするデコーダ。
15. 非一時的なコンピュータ可読記憶媒体であって、
    プロセッサが実行する命令を記憶しており、前記命令がプロセッサにより実行されると、前記プロセッサが請求項１～１２のいずれか一項に記載の方法を実行することを特徴とする記憶媒体。