(57)【特許請求の範囲】
【請求項１】
シーンの点群フレームのシーケンスを含む動的点群を受け入れる入力インターフェースと、
現在の点群フレームのブロックをエンコードして、エンコードされたフレームを生成するハードウェアプロセッサであって、前記現在の点群フレームの現在のブロックをエンコードするために、前記ハードウェアプロセッサは、
前記現在のブロックをエンコードするための基準として機能する類似度メトリックに従って、前記現在のブロックに類似した基準ブロックを選択し、
ペアリングされる点の値に基づいて、前記現在のブロック内の各点を、前記基準ブロック内の点とペアリングし、
前記基準ブロックの識別情報及び前記ペアリングされた点の前記値の間の残差の組み合わせに基づいて前記現在のブロックをエンコードし、なお、前記残差は、前記基準ブロック内の前記点の前記値の順序に従って順序付けされ、
前記基準ブロック内の各前記ペアリングされた点が最近傍グラフ内のノードとなるように、前記基準ブロックの前記点を表す前記最近傍グラフを構築し、
前記最近傍グラフの固有値分解を実行して、グラフ変換演算子を生成し、
前記グラフ変換演算子を用いて前記残差を変換して、グラフ変換係数を生成し、
前記グラフ変換係数を量子化及びエントロピー符号化する、ハードウェアプロセッサと、
通信チャネルを通じて、前記エンコードされたフレームを送信する送信機と、
を備える、点群エンコーダ。
【請求項２】
前記ハードウェアプロセッサは、前記現在の点群フレームの前に符号化された点群フレームから前記基準ブロックを選択する、請求項１に記載のエンコーダ。
【請求項３】
前記ハードウェアプロセッサは、前記現在の点群フレームから前記基準ブロックを選択する、請求項１に記載のエンコーダ。
【請求項４】
基準フレームの前記識別情報は、並進モーションのためのモーションベクトル、回転モーションのための回転行列、及び、拡大／縮小モーションのためのスケーリングパラメータのうちの１つ又は組み合わせを含むモーションモデルである、請求項１に記載のエンコーダ。
【請求項５】
前記類似度メトリックは、前記現在のブロック内の点から、前記基準ブロック内の前記点によって形成された表面のモデルまでの距離の総和を含む、請求項１に記載のエンコーダ。
【請求項６】
各前記残差は、各前記残差が３Ｄベクトルとなるように、前記ペアリングされた点の値間の差として求められる、請求項１に記載のエンコーダ。
【請求項７】
各前記残差は、各前記残差がスカラー値となるように、前記現在のブロック内の点から、少なくとも部分的に前記基準ブロック内の前記ペアリングされた点によって形成された表面までの距離として求められる、請求項１に記載のエンコーダ。
【請求項８】
前記表面は、平面として近似される、請求項７に記載のエンコーダ。
【請求項９】
前記ハードウェアプロセッサは、前記固有値分解を実行するものであり、
グラフ隣接行列及びグラフラプラシアン行列のうちの一方又は組み合わせを用いて前記最近傍グラフのグラフ演算子を求め、
前記グラフ演算子に対して前記固有値分解を実行する、
ように構成される、請求項１に記載のエンコーダ。
【請求項１０】
入力インターフェースを介して、シーンの点群フレームのシーケンスを有する動的点群を受け入れることと、
前記入力インターフェースと通信するハードウェアプロセッサを用いて前記点群フレームを分割してブロックにすることであって、
前記現在のブロックをエンコードするための基準として機能する類似度メトリックに従って、前記現在のブロックに類似した基準ブロックを選択することと、
ペアリングされる点の値に基づいて、前記現在のブロック内の各点を、前記基準ブロック内の点とペアリングすることと、
前記基準ブロックの識別情報及び前記ペアリングされた点の前記値の間の残差の組み合わせに基づいて前記現在のブロックをエンコードすることであって、それにより、前記残差は、前記基準ブロック内の前記点の前記値の順序に従って順序付けされることと、
前記基準ブロック内の各ペアリングされた点が最近傍グラフ内のノードとなるように、前記基準ブロックの前記点を表す前記最近傍グラフを構築することと、
前記最近傍グラフの固有値分解を実行して、グラフ変換演算子を生成することと、
前記グラフ変換演算子を用いて前記残差を変換して、グラフ変換係数を生成することと、
前記グラフ変換係数を量子化及びエントロピー符号化することと、
に基づいて、前記ハードウェアプロセッサを用いて前記点群フレームの各ブロックがエンコードされ、エンコードされたフレームを生成することと、
前記ハードウェアプロセッサと通信する送信機を介して、通信チャネルを通じて、前記エンコードされたフレームを送信することと、
を含む、方法。
【請求項１１】
前記符号化された点群フレームから前記基準ブロックを選択することは、前記現在の点群フレームの前に行われる、請求項１０に記載の方法。
【請求項１２】
前記基準ブロックを選択することは、前記現在の点群フレームから行われる、請求項１０に記載の方法。
【請求項１３】
基準フレームを識別することは、並進モーションのためのモーションベクトル、回転モーションのための回転行列、及び、拡大／縮小モーションのためのスケーリングパラメータのうちの１つ又は組み合わせを有するモーションモデルによって行われる、請求項１０に記載の方法。
【請求項１４】
前記類似度メトリックは、前記現在のブロック内の点から、前記基準ブロック内の前記点によって形成された表面のモデルまでの距離の総和を含む、請求項１０に記載の方法。
【請求項１５】
前記プロセッサは、前記固有値分解を実行するために、
グラフ隣接行列及びグラフラプラシアン行列のうちの一方又は組み合わせを用いて前記最近傍グラフのグラフ演算子を求め、
前記グラフ演算子に対して前記固有値分解を実行する、
ように構成される、請求項１０に記載の方法。
【請求項１６】
シーンの点群フレームのシーケンスを含む動的点群を受け入れる入力インターフェースと、
現在の点群フレームのブロックをエンコードして、エンコードされたフレームを生成するハードウェアプロセッサであって、前記現在の点群フレームの現在のブロックをエンコードするために、前記ハードウェアプロセッサは、
前記現在のブロックをエンコードするための基準として機能する類似度メトリックに従って、前記現在のブロックに類似した基準ブロックを選択し、なお、前記類似度メトリックは、前記現在のブロック及び前記基準ブロック内の最も近い点の間の差の総和を含み、
ペアリングされる点の値に基づいて、前記現在のブロック内の各点を、前記基準ブロック内の点とペアリングし、
前記基準ブロックの識別情報及び前記ペアリングされた点の前記値の間の残差の組み合わせに基づいて前記現在のブロックをエンコードし、なお、前記残差は、前記基準ブロック内の前記点の前記値の順序に従って順序付けされ、
前記基準ブロック内の各ペアリングされた点が最近傍グラフ内のノードとなるように、前記基準ブロックの前記点を表す前記最近傍グラフを構築し、
前記最近傍グラフの固有値分解を実行して、グラフ変換演算子を生成し、それにより、前記固有値分解を実行することは、グラフ隣接行列又はグラフラプラシアン行列のうちの一方又は組み合わせを用いて前記最近傍グラフのグラフ演算子を求め、
その後、前記グラフ演算子に対して前記固有値分解を実行し、
前記グラフ変換演算子を用いて前記残差を変換して、グラフ変換係数を生成し、
前記グラフ変換係数を量子化及びエントロピー符号化する、ハードウェアプロセッサと、
通信チャネルを通じて、前記エンコードされたフレームを送信する送信機と、
を備える、点群エンコーダ。
【請求項１７】
前記基準ブロックは、前記現在の点群フレームの前に符号化された点群フレームから選択され、前記基準ブロックを求めて探索するとき、類似度基準は、前記基準ブロック及び前記現在のブロックからの最近傍点間の距離を用いる点対点距離に基づく、請求項１６に記載のエンコーダ。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示の実施形態は、点群信号の解析、補完及び表現に関し、より詳細には、点群処理及び圧縮に関する方法及びエンコーダを含む。
【背景技術】
【０００２】
点群は、多くの場合、同一のシーンについて逐次的に取得され、複数の移動物体を含む。これらの点群は、静止シーン又は静止物体から捕捉された静的点群と比較して、動的点群と呼ばれる。動的点群は、典型的には、複数のフレームに編成され、異なるフレームは、異なる時点において捕捉される。
【発明の概要】
【０００３】
本開示の実施形態は、点群信号の解析、補完及び表現に関し、特に、点群処理及び圧縮に関する方法及びエンコーダを含む。
【０００４】
点群信号は、いくつかの側面において従来のビデオ信号に類似している。なぜならば、点群信号及びビデオ信号はいずれも、サンプリング点のセットから構成されるためである。ビデオ信号では、各サンプリング点は、多くの場合ピクセルと称される一方、点群信号では、各サンプリング点は、３Ｄワールド内の点に対応する。その上、いずれの信号も、同一のシーンから捕捉することができ、したがって、いずれの信号の場合にも、近傍フレーム間に冗長性が存在する。
【０００５】
圧縮タスクに関して、ビデオ圧縮におけるフレーム間予測からの類似の原理を点群圧縮に適用しようとすることから始めることが比較的容易である可能性があるが、しかしながら、これは、以下の事実に起因して簡単ではない（non-trivial）タスクである。
【０００６】
従来のビデオ圧縮では、サンプリング点（ピクセル）は、暗黙的かつ規則的な格子上に配置される。換言すれば、規則格子は、単に、ビデオ信号内でサンプリング点（ピクセル）ロケーションをともに配置することによって得られるものであり、格子内に有用な情報はあまり多くない。したがって、ピクセルロケーションのシグナリングは、比較的容易であり、高レベルシンタックスを介して行うことができる。その代わりに、ビデオ圧縮におけるタスクは、各サンプリング点（ピクセル）に関連付けられた強度情報及び／又は色情報の効率的符号化に焦点を当てている。
【０００７】
一方、点群圧縮の場合、ビデオ圧縮とは異なり、サンプリング点ロケーションを符号化することは難題となる。これは、点群内のサンプリング点がいずれの規則格子上にも存在しないためである。点のロケーションにのみ基づいて点をともに配置することによって、点群信号は、サンプリング点に関連付けられた情報が取り除かれても、シーンの幾何学的特性を表すことができる。このことが、点群内のサンプリング点の幾何学的情報の圧縮を、従来のビデオ圧縮と比較して特異なタスクにしている。当然、圧縮されたサンプリングロケーションに基づいて、いくつかの用途には、シーンの幾何学的情報に加えて、関連付けられた属性に対する圧縮が（利用可能である場合）必要とされる場合がある。属性の圧縮は、この研究における副次的なタスクである。
【０００８】
さらに、ビデオ圧縮では、モーション推定／補償を介した近傍フレーム間の効率的な符号化のためにモーションが利用される。モーション推定／補償の着想を動的点群に適用するとき、点は不規則格子上にサンプリングされるということから、少なくとも１つの主な難題が持ち上がる。点ロケーションのばらつきのある分布が、いくつかの基準点からの幾何学的予測を、簡単ではないタスクにしている。
【０００９】
本開示のいくつかの実施形態は、点群フレームがまず分割されて、符号化単位と呼ばれるブロックにされるブロックベース符号化フレームワークを用いる。このようにして、コーデックは、異なる符号化単位について異なる符号化モード又はパラメータを選択することが可能である。そのような符号化の選択は、レート歪み最適化に基づいて判断される。
【００１０】
次いで、符号化単位ブロックごとに、以前に符号化されたフレームを基準として用いる幾何学的予測符号化手法を提案する。加えて、予測符号化後の残余情報である残差を圧縮するグラフ変換符号化が提案される。
【００１１】
ここに開示されている実施形態は、添付図面を参照して更に説明される。示されている図面は、必ずしも一律の縮尺というわけではなく、その代わり、一般的に、ここに開示されている実施形態の原理を示すことに強調が置かれている。
【図面の簡単な説明】
【００１２】
【図１】本開示の一実施形態による、点群圧縮のためのブロックベース予測符号化の方法を示すブロック図である。
【図２】本開示のいくつかの実施形態による、ブロック予測子内に点予測子を確立する方法のフロー図である。
【図３】本開示のいくつかの実施形態による、基準ブロックに基づくグラフ構築がいかに用いられて、現在のブロックに対してグラフ変換符号化が実行されるのかを示す図である。
【図４】本開示のいくつかの実施形態による、提案される点群のための表面ベースブロック予測のブロック図である。
【図５】本開示のいくつかの実施形態による、残差ブロックのためのサーフェスアウェア（surface-aware：表面を意識した）符号化のブロック図である。
【発明を実施するための形態】
【００１３】
上記で明らかにされた図面は、ここに開示されている実施形態を記載しているが、この論述において言及されるように、他の実施形態も意図されている。この開示は、限定ではなく代表例として例示の実施形態を提示している。ここに開示されている実施形態の原理の範囲及び趣旨に含まれる非常に多くの他の変更及び実施形態を当業者は考案することができる。
【００１４】
概説
本開示のいくつかの実施形態は、ブロックベース符号化フレームワークを含み、ここで、現在の入力点群フレームをエンコード又はデコードすることができ、基準点群フレームは、以前にエンコード又はデコードされている。再構築された点群は、基準点群のためにアクセス可能である。基準フレームは、この実施形態又は他の任意の手法において提案される方法を用いて符号化することができる。
【００１５】
動的点群は、或るバウンディングボックス内に含まれ、これらの点及びその属性は、最大深度を有する八分木構造を用いて編成される。現在の点群フレーム内の点は、動的点群レベルでサイズが指定される、例えば、８×８×８、１６×１６×１６等とすることができる、立方体ブロック（ボクセル）に従った複数の符号化単位に編成される。
【００１６】
したがって、符号化単位ブロックごとに、本開示は、基準点群フレームを用いた幾何学的情報のための予測符号化手法を提案し、基準点群フレームは、時間方向にわたって不変な幾何学表面を仮定する。幾何学表面は、点サンプルによって表される３Ｄ構造体である。
【００１７】
加えて、予測符号化後の残余情報である残差を圧縮するグラフ変換符号化を提案することができる。
【００１８】
ブロックベースフレーム間予測符号化
本開示のいくつかの実施形態は、少なくとも別の点群フレームがより早期の時点において符号化されており、このフレームが基準点群フレームとして利用可能であることを仮定して、現在の点群フレームについての新規な予測符号化手法を提案する。図１は、提案される手法のブロック図を示している。
【００１９】
ステップ１（ブロック１０１）：点群フレームを分割して符号化単位である３Ｄブロックにする。少なくとも１つの例において、分割は、八分木分解を用いて行うことができ、この八分木分解は、点群を、中心位置からｘ方向、ｙ方向及びｚ方向に沿って分割する。本方法の少なくとも１つの側面は、本方法が点群のコンテンツに対して集中解析を必要としないので、低複雑度である。分割パラメータは、八分木分解深度レベル指標及びブロック占有率指標を含むことができる。ここで、占有されたブロックは、実際の符号化単位となる。
【００２０】
第２の分割手法を用いると、分割位置は、物体のエッジ又は平面に沿って適応的に選択される。さらに、分割方向は、ｘ方向、ｙ方向及びｚ方向に限定されず、任意の方向とすることができる。適応的分割を用いると、分割パラメータは、上記の低複雑度分割手法と比較して、分割位置及び分割方向を付加的に含むことになる。本開示の方法の高度な実施形態は、より良好な予測子と、最後に符号化されるより小さな残差とを生成する。点群内の平面／エッジ検出の方法は、この特定の実施形態の範囲外である。
【００２１】
分割が行われた後、分割されたブロックは、１つずつ符号化されることになる（ブロック１１０）。
【００２２】
ステップ２（ブロック１２０）：現在の符号化単位（ブロック１２５）、及び、基準点群フレーム内の所定の探索ウィンドウ（ブロック１３５）を入力として取り込む。基準点群フレーム内の探索ウィンドウから、以降で基準ブロックと呼ばれる点のブロックが識別されることになる。基準点群フレームは、符号化プロセスからのその再構築されたものであることに留意されたい。
【００２３】
このステップからの出力は、モーションベクトル（３Ｄベクトル）及び再サンプリングパラメータを含むことができる照合パラメータのセットとすることができる。
【００２４】
典型的には、基準ブロックは、現在のブロックとは異なる数の点を有することができる。そのため、再サンプリング手順は、基準ブロック内の点の数を現在のブロックに整合させることを必要とする可能性がある。低複雑度の実施態様において、本開示は、基準ブロック内の点をソートし、その後、現在のブロック内と同数の点が存在するように、その先頭のいくつかの点を選び取る。このソート手順は、ブロックのアンカー位置、例えばブロックの前面左上のコーナーまでの点距離に基づいている。
【００２５】
基準ブロックを求めて探索するとき、点対点距離（point-to-point distance：点間距離）に基づいて類似度基準を規定することができ、ここで、基準ブロック及び現在のブロックからの最近傍点間の距離が用いられる。
【００２６】
点群内の表面構造を促進するために、本開示は、類似度基準のために点対平面距離（point-to-plane distance）を用いることを提案し、ここで、点対点誤差は、法線方向に沿って投影される。点対平面距離は、複雑な点対モデル距離（point-to-model distance）に更に置き換わる可能性があり、ここで、３Ｄモデル（又はメッシュ）は、点群のうちの１つから構築され、モデルまでの距離が用いられる。しかしながら、点対モデル距離に伴う高い計算複雑度を考慮すると、１つの実施形態では、点対平面距離を用いることが好まれる。
【００２７】
本開示の別の実施形態では、探索基準は、類似度評価のみではなく、モーションベクトル（モーションモデル）を符号化するコストによっても判断される。重み付けパラメータを用いて、これらの２つの因子が追加されることが提案される。
【００２８】
ステップ３（ブロック１３０）：現在のブロックの予測子として用いられることになる基準ブロックを抽出する。基準ブロック内の点は、予測子として用いることができる。代替的に、点を予測子として用いる前に改変する表面ベース予測は後のセクションにおいて説明する。
【００２９】
ステップ４（ブロック１４０）：ビデオ内の予測符号化の場合、基準フレームから抽出されたブロックを、予測子として直接用いることができる。なぜならば、全てのピクセルが規則格子上でサンプリングされており、基準ブロックと現在のブロックとの間のピクセルをペアリングすることが容易であるためである。しかしながら、３Ｄ点群では、点サンプルは、任意のロケーションにある可能性があるので、現在のブロック内の点を基準ブロック内の点とペアリングして点ロケーション予測を実行することは、簡単ではない。ペアリング手順の詳細は、後に説明する。
【００３０】
ステップ５（ブロック１５０）：基準ブロックと現在のブロックとの間の全ての点ペア間の差を計算する。そのような残差ブロックは、典型的には、３つの方向、すなわち、ｘ方向、ｙ方向及びｚ方向を伴う。最終的に、残差ブロックは、エントロピー符号化器に送信される。残差ブロックに対する高度な符号化手法は、後のセクションで説明する。
【００３１】
ステップ６（ブロック１７０）：残差ブロックに対する変換を実行する。本開示は、基準ブロックに基づいて適応されるグラフベース変換を提案する（以下の記載を参照されたい）。
【００３２】
ステップ７（ブロック１８０）：変換係数に対する量子化を実行し、量子化された係数は、エントロピー符号化される（ブロック１６０）。
【００３３】
上記の手法は、点群フレーム同士の間のインター予測のために設計することができるが、この手法は、適用例に応じて、探索ウィンドウが、現在の点群フレームの既に「符号化された」分割であることを指定することによって、同一の点群フレーム内の予測のために適応させることができる。
【００３４】
単純な動的点群の場合、点群フレーム全体が単一ブロックに分割されている状態で、上記原理を適用することも可能である。
【００３５】
加えて、本明細書において、モーションは、並進モーションからのもののみと仮定される。しかしながら、並進のためのモーションベクトル、回転モーションのための回転行列、及び、拡大／縮小モーションのためのスケーリングパラメータを含む高度なモーションの実施形態の利用が妨げられることはない。
【００３６】
表面ベースブロック予測
本開示は、抽出された基準ブロックを用いて現在のブロックを直接予測すること（ブロック１３０）を既に提案した。この方法の一側面は、点群を取得する際のサンプリング雑音に起因してこの方法が効率的でない場合がある、というものである。他方、基準ブロックによって表される表面構造と現在のブロックによって表される表面構造とは互いに類似することが多い。このことを利用するために、本開示は、図４に示すように、表面ベースブロック予測方法を提案する。
【００３７】
図４を参照すると、ブロックの全ての点のアベレージ位置として、ブロックＢの平均位置ＰＭが定義される。
【数１】
0006732152.tif 000002
ここで、ｐｉ∈Ｒ３は、点ｉのロケーションである。
【００３８】
ブロックのサイズに従って、ブロックＢの中心位置ＰＣが定義される。
【数２】
0006732152.tif 000003
ここで、ｐ０∈Ｒ３は、ブロックの前面左上のコーナーを示し、Ｓ∈Ｒ３は、ブロックのサイズを示し、｛Ｐ０，Ｐ０＋Ｓ｝は、ブロックの立方体空間を示す。
【００３９】
提案される表面ベースブロック予測は、以下のステップから構成される。
【００４０】
引き続き図４を参照すると、ステップ１において、基準ブロックにアクセスする（ブロック４０１）。
【００４１】
ステップ２において、第１のサブセクションで説明されたように、現在のブロック内の点と同数の点が基準ブロック内に存在するように、基準ブロック内の先頭のいくつかの点を選び取る（ブロック４０２）。
【００４２】
ステップ３において、基準ブロックから１つの表面を当てはめる（ブロック４０３）。低複雑度の実施態様において、この表面は、その法線によって表される平面とすることができる。
【００４３】
引き続き図４を参照すると、ステップ４において、基準ブロック内の全ての点を、上記当てはめられた表面に投影する（ブロック４０４）。基準ブロックを、投影された新たな点を用いて更新する。基準ブロックは、ブロックの平均位置が（０，０，０）である状態で、局所座標系において表される。
【００４４】
ステップ５において、基準ブロックの平均を現在のブロックの平均ＰＭに移動させる（ブロック４０５）。このために、アンカー位置ＰＡ、例えば、ブロックの前面左上のコーナーＰ０又はブロックの中心点ＰＣが最初に選択される。アンカー位置の選択は、現在のブロック内の点をデコードする前にアンカー位置が利用可能である必要があるので、現在のブロック内の点に依存しないようにすべきである。エンコーダにおいて、現在のブロックのアンカー位置から平均位置までのオフセットベクトルが計算される。
【数３】
0006732152.tif 000004
【００４５】
以前のステップから得られた予測子点は、アンカー位置ＰＡ及びオフセットベクトルＶｏｆｆｓｅｔを追加することによって更新される。
【００４６】
本開示の一実施形態によれば、３ＤオフセットベクトルＶｏｆｆｓｅｔは、ビットストリームに符号化される。別の実施態様では、このオフセットベクトルは、まず、基準ブロックから当てはめられた平面の法線方向に投影され、その後、投影されたオフセットの量がビットストリームに符号化される。デコーダにおいて、オフセットベクトルは、この量及び法線に基づいて復元される。後者の手法は、ブロック全体を平面に沿ってシフトさせることができる。
【００４７】
基準ブロックと現在のブロックとの間の点のペアリング
基準ブロックを得た後、基準ブロック内の点は、現在のブロック内の点とペアリングされ、それによって、現在のブロック内の各点を基準ブロック内のそのペアリングされた点によって予測することができるようになっている必要がある。ペアリング手順のために、図２に示すように、「未使用最近傍（unused nearest neighbor）」探索が提案される。
【００４８】
まず、基準ブロック内の各点にインデックス番号を割り当てる（ブロック２０１）。エンコーダ及びデコーダの双方で同一のインデックス付け手法が実施されている限り、インデックスの実際の順序は、この手順では重要ではない。
【００４９】
次に、基準ブロック内の全ての点（ブロック２０２、２０５）について、それまで基準ブロック内のいずれの点にもペアリングされていなかった現在のブロック内の最近傍を識別すること（ブロック２０３）を提案する。現在のブロック内の点が識別されると、この点は、基準ブロック内の現在の点とペアリングされ、再度ペアリング／予測されることがないように、ペアリング済みであるとマークされる（ブロック２０４）。探索手順は、エンコーダにのみ必要とされるものであり、デコーダには必要とされないことに留意されたい。
【００５０】
最終的に、多くの適用例の場合、ビットストリーム内での点の出現順序は重要ではなく、副情報が送信される必要はない。しかしながら、適用例によってはこれが当てはまらず、点の出力順序が復元される必要がある場合には、現在のブロック内の点の再順序付けをデコーダにシグナリングすることができる。
【００５１】
ブロックベースグラフ変換符号化
残差ブロックが得られた後、任意選択で、量子化を実行する前に、変換（図１のブロック１７０）、例えば、従来的なＤＣＴ変換を適用することができる。符号化効率を促進するために、エントロピー符号化の前に、残差ブロックに対してグラフ変換を適用することを提案する。
【００５２】
残差ブロック内の点は、３次元空間において出現するので、変換符号化を設計するのは容易ではない。１つの素朴な方法は、点を１Ｄアレイに配置して、このアレイに対して１Ｄ変換を適用することである。しかしながら、この手法は、３Ｄ空間における点の関係を考慮しておらず、性能の観点から最適ではない。
【００５３】
ブロック１４０のプロセスにおいて、基準ブロックと現在のブロックとの間の点のペアが求められる。ここで、この関係を利用して、高度なグラフ変換符号化を設計することを提案する。
【００５４】
詳細には、基準ブロックに基づいたＫ−ＮＮグラフを構築することを提案する。すなわち、基準ブロック内の各点がグラフノードとして処理されることを提案する。基準ブロック内の「Ｋ」最近傍が、グラフエッジに接続される。グラフエッジの重みは、それらのユークリッド距離に基づいて割り当てられる。これは、図３のブロック３０１に示されている。τ−ＮＮグラフを代わりに用いることができ、ここで、半径τ内の点が現在の点に接続される。Ｋ−ＮＮグラフを用いる方が、グラフの疎性を設定することによって変換の複雑度を維持することが容易である一方、τ−ＮＮグラフを用いる方が、点間の物理的関係と整合する。
【００５５】
グラフが構築された後、好ましいグラフ演算子、例えば、グラフ隣接行列、グラフラプラシアン行列を求めることができる。この実施形態では、グラフラプラシアン行列を好ましいグラフ演算子として選択する。
【００５６】
その後、ブロック３１０によって示すように、構築されたグラフを用いて、選択されたグラフ演算子に対する固有値分解を行うことによってグラフフーリエ変換（ＧＦＴ）が導出される。
【００５７】
次に、ブロック３２０の各点上の矢印は、符号化されることになる点属性を表している。例えば、矢印は、ｘロケーション、ｙロケーション又はｚロケーションの値を表すこともできるし、ｒ色チャネル、ｇ色チャネル及びｂ色チャネルからの成分又は符号化されることになる他の任意の属性とすることもできる。矢印は、ブロック３３０のようにベクトル化される。
【００５８】
最終的に、グラフフーリエ変換（ＧＦＴ）が残差ブロックに適用され、これにより、残差ブロック内のエネルギーをコンパクトにすることができる。最後には、ＧＦＴ係数（ブロック３４０）が量子化され、その後、最終ビットストリームを生成するためにエントロピー符号化器に送信される。基準ブロック内の点と現在のブロック内の点とが上述のようにペアリングされるので、基準ブロックから構築されたグラフを、符号化されることになる現在の残差ブロックに対して適用することができるということは、指摘しておく価値がある。
【００５９】
残差ブロックのためのサーフェスアウェア符号化
典型的には、基準点と現在の点との間の残差情報は、各次元がｘ方向、ｙ方向又はｚ方向に対応する３Ｄ残差ベクトルによって表される。多くの場合、全ての点についてそのような３Ｄ残差ベクトルを符号化するのは非効率であることが見出される。ここで、図５に示すように、現在の点のためのサーフェスアウェア符号化方法を提案する。
【００６０】
図５を参照すると、ステップ１において、現在の点とペアリングされた対応する点の近傍に基づいて局所平面を当てはめる（ブロック５０２）。
【００６１】
ステップ２において、１つの次元を法線方向に沿うようにし、残りの２つの次元を当てはめられた平面内に収める状態で、３Ｄ残差ベクトルを更新する（ブロック５０３）。
【００６２】
ステップ３において、任意選択で、更新された３Ｄ残差ベクトルの３つの次元に対して変換を実行し（ブロック５０４）、この３つの次元についての変換係数を得る。
【００６３】
引き続き図５を参照すると、ステップ４において、当てはめられた平面の法線方向に沿った変換係数に対して比較的小さな（精緻な）量子化ステップＱＰ１を適用し（ブロック５０５）、当てはめられた平面内の変換係数の２つの次元に対して比較的大きな（粗大な）量子化ステップＱＰ２＞ＱＰ１を適用する（ブロック５０６）。１つの極端な実施態様では、当てはめられた平面内の成分は、ＱＰ２＝∞を設定することによって破棄することができる。
【００６４】
提案される方法の少なくとも１つの動機は、局所表面から離れた残差オフセットが局所表面内のシフトよりも重要であるということである。すなわち、表面内の点のわずかなシフトは、多くの場合許容可能である一方、表面予測子の法線方向に沿った誤差は、決定的な影響を有する。
【００６５】
本発明の上記で説明した実施形態は、多数の方法のうちの任意のもので実施することができる。例えば、実施形態は、ハードウェア、ソフトウェア又はそれらの組み合わせを用いて実施することができる。ソフトウェアで実施される場合、ソフトウェアコードは、単一のコンピューターに設けられるのか又は複数のコンピューター間に分散されるのかにかかわらず、任意の適したプロセッサ又はプロセッサの集合体において実行することができる。そのようなプロセッサは、１つ以上のプロセッサを集積回路部品に有する集積回路として実装することができる。ただし、プロセッサは、任意の適したフォーマットの回路類を用いて実装することができる。
【００６６】
また、本発明の実施形態は、例が提供された方法として実施することができる。この方法の一部として実行される動作は、任意の適切な方法で順序付けすることができる。したがって、動作が示したものと異なる順序で実行される実施形態を構築することができ、これには、例示の実施形態では一連の動作として示されたにもかかわらず、いくつかの動作を同時に実行することを含めることもできる。
【００６７】
請求項の要素を修飾する、特許請求の範囲における「第１」、「第２」等の序数の使用は、それ自体で、１つの請求項の要素の別の請求項の要素に対する優先順位も、優位性も、順序も暗示するものでもなければ、方法の動作が実行される時間的な順序も暗示するものでもなく、請求項の要素を区別するために、単に、或る特定の名称を有する１つの請求項の要素を、同じ（序数の用語の使用を除く）名称を有する別の要素と区別するラベルとして用いられているにすぎない。
【要約】シーンの点群フレームのシーケンスを含む動的点群を受け入れる入力インターフェースを備える点群エンコーダに関する。プロセッサは、現在の点群フレームのブロックをエンコードして、エンコードされたフレームを生成する。現在の点群フレームの現在のブロックをエンコードするために、現在のブロックをエンコードするための基準として機能する類似度メトリックに従って、現在のブロックに類似した基準ブロックが選択される。ペアリングされる点の値に基づいて、現在のブロック内の各点を、基準ブロック内の点とペアリングする。基準ブロックの識別情報及びペアリングされた点の値の間の残差の組み合わせに基づいて現在のブロックをエンコードする。残差は、基準ブロック内の点の値の順序に従って順序付けされる。送信機は、通信チャネルを通じて、エンコードされたフレームを送信する。【図１】
0006732152.tif 000005
【図２】
0006732152.tif 000006
【図３】
0006732152.tif 000007
【図４】
0006732152.tif 000008
【図５】
0006732152.tif 000009