JP7580489B2 - ビデオベースの点群コーディングのための高速リカラー - Google Patents

Description

関連出願の相互参照
本出願は、2021年6月4日に出願された米国仮特許出願第63/197,184号および2021年10月13日に出願された米国特許出願第17/500,345号の優先権を主張し、これらの開示はその全体が参照により本明細書に組み込まれる。

本開示は、一連の高度なビデオコーディング技術、より具体的には、高速リカラー色転写を含むビデオベースの点群（ポイントクラウド）圧縮に関する。

世界の高度な三次元（3D）表現によって、より没入型のインタラクションおよび通信が可能になっている。これにより、機械がわれわれの住む世界を理解し、解釈し、ナビゲートすることも可能になっている。点群は、世界の3D表現として広く使用されている。例えば、それらは、地図作成のための地理情報システム（GIS）、および文化的伝統のオブジェクトおよびコレクションなどを視覚化およびアーカイブするための文化的伝統において、物体検出および位置特定のための自動運転車両で使用され得る。点群データに関連するいくつかのユースケースが識別されており、点群の表現および圧縮のためのいくつかの対応する要件が開発されている。

点群は、例えば3次元（3D）などの高次元点の集合を含み、それぞれが3D位置情報および色、反射率などの追加の属性を含む。それらは、複数のカメラおよび深度センサ、または様々な設定のLidarを使用してキャプチャされることができ、元のシーンを現実的に表現するために数千から数十億の点で構成され得る。

より高速な伝送、またはストレージの低減を目的として、点群を表すために要するデータ量を削減するために、圧縮技術が必要とされている。ISO／IEC MPEG（JTC 1／SC 29／WG 11）は、静的または動的クラウドのための圧縮技術を標準化するためのアドホックグループ（MPEG-PCC）を創設した。

実施形態によれば、少なくとも1つのプロセッサによって実行される、ビデオ点群コーディングを使用してビデオストリームを符号化する方法は、ソース点群を取得するステップと、幾何学的に再構築された点群を取得するステップであって、幾何学的に再構築された点群はロッシーコーディングを使用して再構築される、ステップと、幾何学的に再構築された点群に含まれる目標点を取得するステップと、目標点の最近傍であるソース点群のうちの第1の複数の点を決定するための順方向K次元（KD）ツリー探索と、目標点が最近傍であるソース点群のうちの第2の複数の点を決定するための逆方向KDツリー探索とのうちの少なくとも一方を実行するステップと、第1の複数の点の第1の平均色値と第2の複数の点の第2の平均色値とのうちの少なくとも一方に基づいて平均色値を決定するステップと、平均色値に基づいて目標点の色値を選択するステップと、選択された色値に基づいて符号化されたビデオストリームを生成するステップと、を含む。

実施形態によれば、ビデオ点群コーディングを使用してビデオストリームを符号化するための装置は、プログラムコードを格納するように構成された少なくとも1つのメモリと、プログラムコードを読み取り、プログラムコードによって命令されたとおりに動作するように構成された少なくとも1つのプロセッサと、を含み、プログラムコードは、少なくとも1つのプロセッサに、ソース点群を取得させるように構成された第1の取得コードと、少なくとも1つのプロセッサに、幾何学的に再構築された点群を取得させるように構成された第2の取得コードであって、幾何学的に再構築された点群はロッシーコーディングを使用して再構築される、第2の取得コードと、少なくとも1つのプロセッサに、幾何学的に再構築された点群に含まれる目標点を取得させるように構成された第3の取得コードと、少なくとも1つのプロセッサに、目標点の最近傍であるソース点群のうちの第1の複数の点を決定するための順方向K次元（KD）ツリー探索と、目標点が最近傍であるソース点群のうちの第2の複数の点を決定するための逆方向KDツリー探索とのうちの少なくとも一方を実行させるように構成された実行コードと、少なくとも1つのプロセッサに、第1の複数の点の第1の平均色値と第2の複数の点の第2の平均色値とのうちの少なくとも一方に基づいて平均色値を決定させるように構成された決定コードと、少なくとも1つのプロセッサに、平均色値に基づいて目標点の色値を選択させるように構成された選択コードと、少なくとも1つのプロセッサに、選択された色値に基づいて符号化されたビデオストリームを生成させるように構成された生成コードと、を含む。

実施形態によれば、ビデオ点群コーディングを使用してビデオストリームを符号化するためのコンピュータ命令を格納した非一時的コンピュータ可読媒体が提供され、コンピュータ命令は、少なくとも1つのプロセッサによって実行されると、少なくとも1つのプロセッサに、ソース点群を取得することと、幾何学的に再構築された点群を取得することであって、幾何学的に再構築された点群はロッシーコーディングを使用して再構築される、ことと、幾何学的に再構築された点群に含まれる目標点を取得することと、目標点の最近傍であるソース点群のうちの第1の複数の点を決定するための順方向K次元（KD）ツリー探索と、目標点が最近傍であるソース点群のうちの第2の複数の点を決定するための逆方向KDツリー探索とのうちの少なくとも一方を実行することと、第1の複数の点の第1の平均色値と第2の複数の点の第2の平均色値とのうちの少なくとも一方に基づいて平均色値を決定することと、平均色値に基づいて目標点の色値を選択することと、選択された色値に基づいて符号化されたビデオストリームを生成することと、を行わせる。

本開示の主題のさらなる特徴、性質、および様々な利点は、以下の詳細な説明、および添付の図面でより明らかになる。

一実施形態による通信システムの簡略化されたブロック図の概略図である。 一実施形態によるストリーミングシステムの簡略化されたブロック図の概略図である。 一実施形態によるビデオエンコーダの簡略化されたブロック図の概略図である。 一実施形態によるビデオデコーダの簡略化されたブロック図の概略図である。 一実施形態による、ソース点群と再構築された点群との間の順方向探索の一例を示す図である。 一実施形態による、ソース点群と再構築された点群との間の逆方向探索の一例を示す図である。 一実施形態によって実行されるプロセスを示すフロー図である。 一実施形態によるデバイスを示す図である。 実施形態を実施するのに適したコンピュータシステムの図である。

ビデオベースの点群圧縮（video-based point cloud compression、V-PCC）の考え方の背景にあるのは、既存のビデオコーデックを利用して、動的点群の形状、占有、およびテクスチャを3つの個別のビデオシーケンスとして圧縮することである。3つのビデオシーケンスの解釈に必要な余分なメタデータは、個別に圧縮されてもよい。ビットストリーム全体の小部分がメタデータであり、ソフトウェア実装を使用してこれを効率的に符号化／復号することができる。ビデオコーデックによって、大量の情報が処理されてもよい。

本開示の実施形態は、反復平滑化フレームワークにおける過剰平滑化を回避するためのアニーリング反復幾何形状平滑化に関する。本開示の実施形態は、純粋な中央値を使用する計算の複雑さを低減することを目的として、平均統計値と中央値統計値との組み合わせを使用して基準点を導出することに関する。

図1～図4を参照すると、本開示の符号化および復号の構造を実施するための、本開示の実施形態が説明されている。本開示の符号化および復号の構造は、上述したV-PCCの態様を実施してもよい。

図1は、本開示の一実施形態による通信システム100の簡略ブロック図を示す。システム100は、ネットワーク150を介して相互接続された少なくとも2つの端末110、120を含み得る。データの単方向伝送の場合、第1の端末110は、ネットワーク150を介して他の端末120に伝送するために、ローカルロケーションでビデオデータをコード化し得る。第2の端末120は、ネットワーク150から他方の端末のコード化ビデオデータを受信し、コード化データを復号し、復元されたビデオデータを表示し得る。単方向データ伝送は、メディアサービング用途などで一般的であり得る。

図1は、例えば、ビデオ会議中に行われ得るコード化ビデオの双方向伝送をサポートするために設けられた第2の端末対130、140を示している。データの双方向伝送の場合、各端末130、140は、ネットワーク150を介して他の端末に伝送するために、ローカルロケーションでキャプチャされたビデオデータをコード化し得る。各端末130、140は、もう一方の端末によって伝送されたコード化ビデオデータを受信してもよく、コード化データを復号してもよく、かつ復元されたビデオデータをローカルディスプレイデバイスに表示してもよい。

図1では、端末110～140は、例えば、サーバ、パーソナルコンピュータ、およびスマートフォン、ならびに／または任意の他のタイプの端末であってもよい。例えば、端末（110～140）は、ラップトップコンピュータ、タブレットコンピュータ、メディアプレーヤ、および／または専用ビデオ会議機器であり得る。ネットワーク150は、例えば、有線および／または無線通信ネットワークを含む、端末110～140間でコード化ビデオデータを伝達する任意の数のネットワークを表す。通信ネットワーク150は、回線交換および／またはパケット交換チャネルでデータを交換し得る。代表的なネットワークは、電気通信ネットワーク、ローカルエリアネットワーク、ワイドエリアネットワーク、および／またはインターネットを含む。本考察の目的のために、ネットワーク150のアーキテクチャおよびトポロジは、以下で説明されない限り、本開示の運用には無関係な場合がある。

図2は、開示された主題の用途の一例として、ストリーミング環境でのビデオエンコーダおよびデコーダの配置を示している。開示された主題は、例えば、ビデオ会議、デジタルTV、CD、DVD、メモリスティックなどを含むデジタルメディアへの圧縮ビデオの格納を含む、他のビデオ対応アプリケーションで使用され得る。

図2に示すように、ストリーミングシステム200は、ビデオソース201およびエンコーダ203を含むキャプチャサブシステム213を含み得る。ストリーミングシステム200は、少なくとも1つのストリーミングサーバ205および／または少なくとも1つのストリーミングクライアント206をさらに含んでもよい。

ビデオソース201は、例えば、3Dビデオに対応する3D点群を含むストリーム202を生成することができる。ビデオソース201は、例えば、3Dセンサ（例えば、深度センサ）、または3D撮像技術（例えば、（1つまたは複数の）デジタルカメラ）、および3Dセンサまたは3D撮像技術から受信したデータを使用して3D点群を生成するように構成されたコンピュータデバイスを含んでもよい。符号化ビデオビットストリームと比較してデータ量が大きくてもよいサンプルストリーム202を、ビデオソース201に接続されたエンコーダ203によって処理することができる。以下でより詳細に説明するように、エンコーダ203は、開示される主題の態様を可能にする、または実施するために、ハードウェア、ソフトウェア、またはこれらの組み合わせを含むことができる。エンコーダ203は、符号化ビデオビットストリーム204をさらに生成してもよい。圧縮されていないストリーム202と比較して、データ量が小さくてもよい符号化ビデオビットストリーム204を、後で使用するためにストリーミングサーバ205に格納することができる。1つまたは複数のストリーミングクライアント206は、符号化ビデオビットストリーム204のコピーであってもよいビデオビットストリーム209を検索するために、ストリーミングサーバ205にアクセスすることができる。

ストリーミングクライアント206は、ビデオデコーダ210およびディスプレイ212を含むことができる。ビデオデコーダ210は、例えば、符号化ビデオビットストリーム204の着信コピーである、ビデオビットストリーム209を復号し、ディスプレイ212または別のレンダリングデバイス（図示せず）上にレンダリングされ得る発信ビデオサンプルストリーム211を生成することができる。一部のストリーミングシステムでは、ビデオビットストリーム204、209を、特定のビデオコーディング／圧縮規格に従って符号化することができる。このような規格の例は、これに限定されないが、ITU-T勧告H.265、汎用ビデオコーディング（Versatile Video Coding、VVC）、およびMPEG／V-PCCを含む。

図3および図4を参照しながら、本開示の実施形態によって実行され得るV-PCCのいくつかの態様について、以下で説明する。

図3は、本開示の実施形態による、ビデオエンコーダ203の例示的な機能ブロック図を示す。

図3に示すように、ビデオエンコーダ203は、（1つまたは複数の）点群フレーム350を受信して、点群フレーム350に基づいて、形状画像352、テクスチャ画像356、および占有マップ334を生成してもよい。ビデオエンコーダ203は、形状画像352を圧縮して圧縮された形状画像362にし、テクスチャ画像356を圧縮して圧縮されたテクスチャ画像364にし、占有マップ334を圧縮して圧縮された占有マップ372にしてもよい。ビデオエンコーダ203のマルチプレクサ328は、圧縮された形状画像362、圧縮されたテクスチャ画像364、および圧縮された占有マップ372を含む、圧縮されたビットストリーム374を形成してもよい。

より詳細には、実施形態では、ビデオエンコーダ203は、点群フレーム350をパッチに分割する、パッチ生成モジュール302を含んでもよい。パッチはV-PCCの有用なエンティティである。パッチ生成プロセスは、点群フレーム350を分解して、平滑な境界を有する最小の数のパッチにすることを含み、その一方で、再構築誤差を最小にすることをさらに含む。本開示のエンコーダは、このような分解を生じさせるために、様々な方法を実施し得る。

ビデオエンコーダ203は、パッキングプロセスを実行するパッチパッキングモジュール304を含んでもよい。パッキングのプロセスは、未使用の空間を最小にしながら、抽出したパッチを2Dグリッドにマッピングすること、およびグリッドのM×M（例えば、16×16）のブロックがいずれも、一意のパッチに関連付けられるように保証することを含む。効率的なパッチパッキングは、未使用の空間を最小化することによって、あるいは時間的整合性を確保することによって、圧縮効率に直接的な影響を及ぼす。パッチパッキングモジュール304は、占有マップ334を生成し得る。

ビデオエンコーダ203は、形状画像生成モジュール306、およびテクスチャ画像生成モジュール308を含んでもよい。同一サンプルに複数の点が投影される事例に対処するために、各パッチをレイヤと呼ばれる2つの画像に投影してもよい。例えば、形状画像生成モジュール306およびテクスチャ画像生成モジュール308は、点群の形状およびテクスチャを画像（レイヤとも呼ばれる）として格納するために、パッチパッキングモジュール304のパッキングプロセス中に計算された、3Dから2Dへのマッピングを利用してもよい。生成された画像／レイヤは、（1つまたは複数の）ビデオフレームとして格納され、パラメータとして提供される構成に従って、ビデオコーデック（例えば、HMビデオコーデック）を使用して圧縮されてもよい。

実施形態では、入力点群フレーム350および占有マップ334に基づいて、形状画像生成モジュール306は形状画像352を生成し、テクスチャ画像生成モジュール308はテクスチャ画像356を生成する。一実施形態では、形状画像352はYUV420-8ビット形式で、W×Hの単色フレームで表されてもよい。一実施形態では、占有マップ334画像は、グリッドの各セルが空の空間に属するか、それとも点群に属するかを示すバイナリマップからなるテクスチャ画像356を生成するために、テクスチャ画像生成モジュール308は、再サンプリングされた点に関連付けられる色を計算する目的で、再構築された／平滑化された形状358を利用してもよい。

ビデオエンコーダ203はまた、パディングされた形状画像354およびパディングされたテクスチャ画像360を形成するために、形状画像352をパディングするための画像パディングモジュール314、およびテクスチャ画像356をパディングするための画像パディングモジュール316をそれぞれ含んでもよい。画像パディング（背景の充填とも呼ばれる）とは単に、画像の未使用の空間を冗長情報で埋める。良好な背景の充填とは、パッチ境界の周囲に著しいコーディング歪みを導入しないようにしながら、ビットレートの増加を最小化するものである。画像パディングモジュール314および画像パディングモジュール316は、パディングされた形状画像354、およびパディングされたテクスチャ画像360をそれぞれ形成するために、占有マップ334を使用してもよい。一実施形態では、ビデオエンコーダ203は、パディングされたテクスチャ画像360を形成するために、グループ拡大モジュール320を含んでもよい。

ビデオエンコーダ203は、パディングされた形状画像354を圧縮して圧縮された形状画像362にするビデオ圧縮モジュール322、およびパディングされたテクスチャ画像360を圧縮して圧縮されたテクスチャ画像364にするビデオ圧縮モジュール324をそれぞれ含んでもよい。

ビデオエンコーダ203は、占有マップ334のロスレス符号化366用のエントロピー圧縮モジュール318、および占有マップ334のロッシー符号化368用のビデオ圧縮モジュール326を含んでもよい。

実施形態では、ビデオエンコーダ203は、ビデオ圧縮モジュール322によって提供される再構築された形状画像365と、パッチ情報332とを使用して、平滑化された形状358を生成するための平滑化モジュール310を含んでもよい。平滑化モジュール310の平滑化手順は、圧縮アーティファクトによってパッチ境界に生じ得る、潜在的な不連続性を緩和することを目的としてもよい。平滑化された形状358は、テクスチャ画像356を生成するために、テクスチャ画像生成モジュール308によって使用されてもよい。

ビデオエンコーダ203は、圧縮された補助パッチ情報370を形成するための補助パッチ情報圧縮モジュール312をさらに含んでもよく、圧縮された補助パッチ情報370は、マルチプレクサ328によって圧縮されたビットストリーム374として提供される。

図4は、本開示の実施形態による、ビデオデコーダ210の例示的な機能ブロック図である。

図4に示すように、ビデオデコーダ210は、ビデオエンコーダ203からコード化ビットストリーム374を受信して、圧縮されたテクスチャ画像362、圧縮された形状画像364、圧縮された占有マップ372、および圧縮された補助パッチ情報370を取得してもよい。ビデオデコーダ210は、圧縮されたテクスチャ画像362、圧縮された形状画像364、圧縮された占有マップ372、および圧縮された補助パッチ情報370を復号して、復元されたテクスチャ画像460、復元された形状画像462、復元された占有マップ464、および復元された補助パッチ情報466をそれぞれ取得してもよい。続いて、ビデオデコーダ210は、復元されたテクスチャ画像460、復元された形状画像462、復元された占有マップ464、および復元された補助パッチ情報466に基づいて、再構築された点群474を生成してもよい。

実施形態では、ビデオデコーダ210は、受信した圧縮されたビットストリーム374の、圧縮されたテクスチャ画像362、圧縮された形状画像364、圧縮された占有マップ372、および圧縮された補助パッチ情報370を分配する、デマルチプレクサ402を含んでもよい。

ビデオデコーダ210は、圧縮されたテクスチャ画像362を復号するビデオ復元モジュール404、圧縮された形状画像364を復号するビデオ復元モジュール406、圧縮された占有マップ372を復号する占有マップ復元モジュール408、および圧縮された補助パッチ情報370を復号する補助パッチ情報復元モジュール410をそれぞれ含んでもよい。

ビデオデコーダ210は、復元された形状画像462、復元された占有マップ464、および復元された補助パッチ情報466に基づいて再構築された（三次元の）形状468を取得する、形状再構築モジュール412を含んでもよい。

ビデオデコーダ210は、再構築された形状468を平滑化して平滑化された形状470を取得する、平滑化モジュール414を含んでもよい。平滑化手順は、圧縮アーティファクトによってパッチ境界に生じ得る、潜在的な不連続性を緩和することを目的とし得る。

ビデオデコーダ210は、復元されたテクスチャ画像460および平滑化された形状470に基づいて、再構築されたテクスチャ472を取得するためのテクスチャ再構築モジュール416を含んでもよい。

ビデオデコーダ210は、再構築されたテクスチャ472の色を平滑化して再構築された点群474を取得する、色平滑化モジュール418を含んでもよい。3D空間内で隣接していないパッチが、2Dビデオ内で互いに隣接してパッキングされることがしばしばある。これは、隣接していないパッチの画素値が、ブロックベースのビデオコーデックによって混合する場合があることを意味する。色平滑化モジュール418の色平滑化は、パッチ境界に現れる、目に見えるアーティファクトを削減することを目的としてもよい。

ビデオベースの点群圧縮（V-PCC）におけるリカラーリング
V-PCCに対応し得るMPEG PCCテストモデルカテゴリ2（TMC2）モデルでは、形状が不可逆的にコード化され、複製された位置がマージされるとき、色転写（color transferring）と呼ばれることがあるリカラーリングプロセスがエンコーダ側で適用され得る。図5および図6を参照して、リカラーリングアルゴリズムの一例を以下に示す。

ソース点群502、属性、および再構築された点群504に含まれる目標点p_rが与えられると、色転写手順、すなわちリカラーリングプロセスは、属性の歪みを最小限に抑える再構築された点群の属性値を決定し得る。この手法は、以下のように実施することができる。

各目標点p_rについて：
1．ソース点群502内のp_rに最も近いN₁（1＜N₁）個の近傍点を見つけ、Ψ₁によって示される点の集合を作成する。これは、図5に示すような順方向探索に対応し得る。
2．p_rが再構築された点群504内のそれらのN₂個の最近傍点の集合に属するように、ソース点群502内の点の集合を見つける。この点の集合をΨ₂で表す。これは、図6に示すような順方向探索に対応し得る。
3．Ψ₁およびΨ₂の点の距離加重平均を以下によって計算する。

ここで、Δ（a，b）は点aと点bとの間のユークリッド距離を示し、c（q）は点qの色を示す。
4．

の平均（または各集合の点の数を重みとする加重平均）を計算し、それを重心色として使用する。
5．いくつかの実施形態では、重心色に対するそれらの絶対差が閾値th_cよりも大きい場合、重心点からの逆方向探索を使用して点を除外してもよい。
6．いくつかの実施形態では、

の平均（または各集合の点の数を重みとする加重平均）を更新し、p_rに変換することができる。

TMC2の現在の設計では、K次元（KD）ツリーデータ構造が最近傍探索で利用され、リカラーリング動作が再構築された点群内のすべての点に適用されるため、リカラーリングプロセスはかなり複雑であり得る。以下に説明する実施形態は、リカラーリングアルゴリズムの複雑さを低減し得る。

本明細書に開示される実施形態は、別々に使用されてもよく、任意の順序で組み合わされてもよい。さらに、各実施形態、例えばエンコーダおよびデコーダは、処理回路（例えば、1つもしくは複数のプロセッサまたは1つもしくは複数の集積回路）によって実装されてもよい。一例では、1つまたは複数のプロセッサは、非一時的コンピュータ可読媒体に格納されたプログラムを実行する。

実施形態によるいくつかの高速リカラーリングアルゴリズムを以下に提案する。実施形態では、これらの高速リカラーリングアルゴリズムの任意の組み合わせ、またはこれらの高速リカラーリングアルゴリズムの一部を使用または適用することができる。

単方向探索
高速リカラーリングの現在の設計では、2つのKDツリーが構築され、1つはソース点群用であり、もう1つは再構築された点群用である。ソース点群のKDツリーは順方向探索で使用され、再構築された点群のKDツリーは逆方向探索で使用される。

実施形態では、逆方向探索のみが適用され、したがって、再構築された点群のKDツリーのみが構築される。そのような簡略化されたリカラーリングアルゴリズムの例は、以下の通りであり得る。

各目標点p_rについて：
1．p_rがN₂個の最近傍の集合に属するソース点の集合を見つける。この点の集合をΨ₂で表す。それは、図1に示すような逆方向探索である。
2．Ψ₂の点の距離加重平均を以下によって計算する。

ここで、Δ（a，b）は点aと点bとの間のユークリッド距離を示し、c（q）は点qの色を示す。
3．目標点p_rの色を

に設定する。

実施形態では、順方向探索のみが適用され、したがって、ソース点群のKDツリーのみが構築される。簡略化されたリカラーリングアルゴリズムは、以下の通りであり得る。

各目標点p_rについて
1．ソース内のp_rに最も近いN₁（1＜N₁）個の近傍を見つけ、Ψ₁によって示される点の集合を作成する。
2．Ψ₁の点の距離加重平均を以下によって計算する。

ここで、Δ（a，b）は点aと点bとの間のユークリッド距離を示し、c（q）は点qの色を示す。
3．目標点p_rの色を

に設定する。

簡略化された加重平均
実施形態では、加重平均戦略を、多くの態様で単純化することができる。本明細書に開示された実施形態の任意の部分は、任意の順序で組み合わされてもよいことに留意されたい。

例えば、実施形態では、

におけるΔ（a，b）の距離計算について、
任意の座標系（例えば、デカルト座標および球面座標）において任意の距離メトリック（例えば、l₁およびl₂の距離）が使用されてもよい。

実施形態では、最近傍は、予測子として直接使用されてもよい。

実施形態では、近傍の平均値は、以下のように予測子として計算されてもよい。

これは、すべての重み付けを一定の値、すなわちΔ（q，p_r）＝Kに設定することと等価であり得る。

実施形態では、重みを計算する際に浮動小数点演算の代わりに整数乗算、例えば除算が使用されてもよい。例えば、

とし、式中、MおよびNは整数定数であり、例えば、M＝32、N＝Δ（a，b）＞＞1であり、

は整数変換を示し、これはフロアまたはシーリングまたはラウンド演算であり得る。そして、以下のようにして加重平均を導出することができる。

この実施形態では、上記の式の分母が0に等しい場合、すなわちΣ_q∈ΨkQ（q，p_r）＝0である場合、この特殊なケースに対処するために他の方法を使用することができる。例えば、近傍の平均を単純に計算するか、または最近傍を予測子として採用することができる。

この実施形態では、すべてのq∈Ψ_kに対するQ（q，p_r）の最大数が2^Lよりも小さいことを保証するために、別の整数パラメータLを定義することができる。2^L以上のQ（q，p_r）がある場合、すべてのQ（q，p_r）は、最大Q（q，p_r）が2^Lより小さくなるまで、例えばビット単位の右シフトによってダウンスケールされ得る。

実施形態では、距離ベースの重み付けモデルを、任意の変換モデル、例えば線形モデル、二次モデル、および他の非線形モデルによって修正することができる。例えば、重み付けは以下のようにすることができる。

式中、A＞0およびB＞0は正の定数である。この新しいモデルに基づいて、整数変換が適用される場合、変換式はそれに応じて以下のように変更することができる。

実施形態では、整数変換が適用される場合、ルックアップテーブルを使用して整数乗算演算を置き換えてもよい。この場合、ルックアップテーブルは、c・Q（a，b）のすべての可能な組み合わせの事前計算結果を格納するように構築されてもよく、すなわち、

次いで、平均化された重み付けを以下のように変更することができる。

ボクセル化された空間のKDツリーでの探索
実施形態では、元の座標の点群からKDツリーを構築する代わりに、3D空間をより小さい立方体に分割することによって、点群を最初にボクセル化することができ、同じ立方体内の点は単一の点としてマージされる。複数の点を1つにマージすることは、それらの幾何学的形状および属性値を平均化する際に行うことができ、距離ベースの平均化などの任意の重み付け戦略を適用することができる。次に、順方向および逆方向の探索プロセスは、ボクセル化された点群のKDツリーで行うことができる。

図7は、ビデオ点群コーディングを使用してビデオストリームを符号化する方法700のフローチャートである。いくつかの実施態様では、図7の1つまたは複数のプロセスブロックは、エンコーダ203によって実行され得る。いくつかの実施態様では、図7の1つまたは複数のプロセスブロックは、エンコーダ203とは別個のまたはエンコーダ203を含む、デコーダ210などの別のデバイスまたはデバイスのグループによって実行され得る。

図7に示すように、動作710において、方法700は、ソース点群を取得するステップを含み得る。実施形態では、ソース点群は、上述したソース点群502に対応し得る。

動作720において、方法700は、幾何学的に再構築された点群を取得するステップを含み得、幾何学的に再構築された点群は、ロッシーコーディングを使用して再構築される。実施形態では、幾何学的に再構築された点群は、上述した再構築された点群504に対応し得る。

動作730において、方法700は、幾何学的に再構築された点群に含まれる目標点を取得するステップを含み得る。実施形態では、目標点は、上述の目標点p_rに対応し得る。

動作740において、方法700は、目標点の最近傍であるソース点群のうちの第1の複数の点を決定するための順方向K次元（KD）ツリー探索と、目標点が最近傍であるソース点群のうちの第2の複数の点を決定するための逆方向KDツリー探索とのうちの少なくとも一方を実行するステップを含み得る。実施形態では、第1の平均色値は、上述の

に対応してもよく、第2の平均色値は、上述の

に対応してもよい。

動作750において、方法700は、第1の複数の点の第1の平均色値と第2の複数の点の第2の平均色値とのうちの少なくとも一方に基づいて平均色値を決定するステップを含み得る。

動作760において、方法700は、平均色値に基づいて目標点の色値を選択するステップを含み得る。

動作770において、方法700は、選択された色値に基づいて符号化ビデオストリームを生成するステップを含み得る。

実施形態では、平均色値は、第1の平均色値を使用せずに第2の平均色値に基づいて決定されてもよい。

実施形態では、平均色値は、第2の平均色値を使用せずに第1の平均色値に基づいて決定されてもよい。

実施形態では、第1の平均色値および第2の平均色値の少なくとも一方は、整数変換を使用して決定されてもよい。

実施形態では、第1の平均色値および第2の平均色値の少なくとも一方は、線形モデル、二次モデル、または非線形モデルのうちの少なくとも1つを使用して決定されてもよい。

実施形態では、第1の平均色値と第2の平均色値とのうちの少なくとも一方は、ボクセル化されたソース点群およびボクセル化された幾何学的に再構築された点群のうちの少なくとも1つに基づいて決定されてもよい。

図7は方法700の例示的なブロックを示しているが、いくつかの実装形態では、方法700は、図7に示されたものとは異なる追加のブロック、より少ないブロック、異なるブロック、または異なる配置のブロックを含んでもよい。追加的または代替的に、方法700のブロックのうちの2つ以上が並行して実行されてもよい。

図8は、実施形態による、ビデオ点群コーディングを使用して符号化されたビデオストリームを復号する装置800の図である。図8に示すように、装置800は、第1の取得コード810と、第2の取得コード820と、第3の取得コード830と、実行コード840と、決定コード850と、選択コード860と、生成コード870とを含む。

第1の取得コード810は、少なくとも1つのプロセッサにソース点群を取得させるように構成されてもよい。

第2の取得コード820は、少なくとも1つのプロセッサに幾何学的に再構築された点群を取得させるように構成されてもよく、幾何学的に再構築された点群はロッシーコーディングを使用して再構築される。

第3の取得コード830は、少なくとも一つのプロセッサに、幾何学的に再構築された点群に含まれる目標点を取得させるように構成されてもよい。

実行コード840は、少なくとも1つのプロセッサに、目標点の最近傍であるソース点群のうちの第1の複数の点を決定するための順方向K次元（KD）ツリー探索と、目標点が最近傍であるソース点群のうちの第2の複数の点を決定するための逆方向KDツリー探索とのうちの少なくとも一方を実行させるように構成されてもよい。

決定コード850は、少なくとも1つのプロセッサに、第1の平均色値および第2の平均色値の少なくとも一方に基づいて平均色値を判定させるように構成されてもよい。

選択コード860は、少なくとも1つのプロセッサに、平均色値に基づいて目標点の色値を選択させるように構成されてもよい。

生成コード870は、少なくとも1つのプロセッサに、選択された色値に基づいて符号化ビデオストリームを生成させるように構成されてもよい。

上述した技術は、コンピュータ可読命令を使用し、1つまたは複数のコンピュータ可読媒体に物理的に格納されたコンピュータソフトウェアとして実装され得る。例えば、図9は、開示の特定の実施形態を実装するのに適したコンピュータシステム900を示している。

コンピュータソフトウェアは、コンピュータ中央処理装置（CPU）、グラフィックス処理装置（GPU）などによって、直接、または解釈、マイクロコードの実行などを通して実行することができる命令を含むコードを作成するために、アセンブリ、コンパイル、リンクなどの機構の適用を受け得る、任意の適切な機械コードまたはコンピュータ言語を使用してコード化され得る。

命令は、例えばパーソナルコンピュータ、タブレットコンピュータ、サーバ、スマートフォン、ゲーミングデバイス、およびモノのインターネットデバイスなどを含む様々なタイプのコンピュータまたはその構成要素上で実行され得る。

コンピュータシステム900について図9に示される構成要素は、例であり、本開示の実施形態を実装するコンピュータソフトウェアの使用範囲または機能に関する制限を示唆することを意図するものではない。構成要素の構成は、コンピュータシステム900の非限定的な実施形態に示されている構成要素のいずれか1つ、または構成要素の組み合わせに関して、依存性を有するものとも要件を有するものとも解釈されてはならない。

コンピュータシステム900は、特定のヒューマンインターフェース入力デバイスを含み得る。そのようなヒューマンインターフェース入力デバイスは、例えば、触覚入力（キーストローク、スワイプ、データグローブの動きなど）、オーディオ入力（音声、拍手など）、視覚入力（ジェスチャーなど）、嗅覚入力（図示せず）を介して、1人または複数の人間ユーザによる入力に応答し得る。ヒューマンインターフェースデバイスは、オーディオ（スピーチ、音楽、環境音など）、画像（走査画像、静止画像カメラから取得された写真画像など）、ビデオ（2次元ビデオ、立体ビデオを含む3次元ビデオなど）などの、必ずしも人間による意識的な入力に直接関連しない特定の媒体をキャプチャするためにも使用され得る。

入力ヒューマンインターフェースデバイスは、キーボード901、マウス902、トラックパッド903、タッチスクリーン910、データグローブ、ジョイスティック905、マイク906、スキャナ907、カメラ908のうちの1つまたは複数（それぞれの1つのみを図示）を含み得る。

コンピュータシステム900は、特定のヒューマンインターフェース出力デバイスも含み得る。そのようなヒューマンインターフェース出力デバイスは、例えば、触覚出力、音、光、および嗅覚／味覚を通して、1人または複数の人間のユーザの感覚を刺激し得る。そのようなヒューマンインターフェース出力デバイスは、触覚出力デバイス（例えば、タッチスクリーン910、データグローブ、またはジョイスティック905による触覚フィードバックであるが、入力デバイスとして機能しない触覚フィードバックデバイスも存在し得る）を含み得る。例えば、そのようなデバイスは、オーディオ出力デバイス（スピーカ909、ヘッドホン（図示せず）など）、視覚出力デバイス（CRTスクリーン、LCDスクリーン、プラズマスクリーン、OLEDスクリーンを含むスクリーン910など、それぞれタッチスクリーン入力機能の有無にかかわらず、それぞれ触覚フィードバック機能の有無にかかわらず、そのいくつかはステレオグラフィック出力などの手段を通して、2次元視覚出力または3次元を超える出力を出力できるものもある、仮想現実ガラス（図示せず）、ホログラフィックディスプレイ、およびスモークタンク（図示せず））、およびプリンタ（図示せず）であり得る。

コンピュータシステム900は、人間がアクセス可能なストレージデバイスおよびそれらに関連する媒体、例えば、CD／DVDなどの媒体921を伴うCD／DVD ROM／RW 920を含む光学媒体、サムドライブ922、リムーバブルハードドライブまたはソリッドステートドライブ923、テープやフロッピーディスク（図示せず）などのレガシー磁気媒体、セキュリティドングル（図示せず）などの特殊なROM／ASIC／PLDベースのデバイスなどを含み得る。

また、当業者は、本開示の主題に関連して使用される「コンピュータ可読媒体」という用語が伝送媒体、搬送波、または他の一時的信号を包含しないことを理解すべきである。

コンピュータシステム900は、1つまたは複数の通信ネットワークへのインターフェースを含むこともできる。ネットワークは、例えば、無線、有線、光とすることができる。ネットワークはさらに、ローカル、広域、メトロポリタン、車両および産業用、リアルタイム、遅延耐性などとすることができる。ネットワークの例は、イーサネットなどのローカルエリアネットワーク、無線LAN、GSM、3G、4G、5G、LTEなどを含むセルラーネットワーク、ケーブルTV、衛星TV、地上波放送TVを含むTV有線または無線ワイドエリアデジタルネットワーク、およびCANBusを含む車両および産業用などを含む。特定のネットワークは一般に、特定の汎用データポートまたは周辺バス949に接続された外部ネットワークインターフェースアダプタを必要とする（例えば、コンピュータシステム900のUSBポートなど）、他のものは一般に、以下に説明するようにシステムバスへの接続によってコンピュータシステム900のコアに統合される（例えば、PCコンピュータシステムへのイーサネットインターフェースまたはスマートフォンコンピュータシステムへのセルラーネットワークインターフェース）。これらのネットワークのいずれかを使用して、コンピュータシステム900は他のエンティティと通信することができる。このような通信は、単方向、受信のみ（例えば、TVの放送）、単方向の送信のみ（例えば、特定のCANbusデバイスへのCANbus）、または双方向、例えば、ローカルまたはワイドエリアデジタルネットワークを使用する他のコンピュータシステム向けであり得る。そのような通信は、クラウドコンピューティング環境955への通信を含むことができる。特定のプロトコルおよびプロトコルスタックは、上記で説明されたように、それらのネットワークおよびネットワークインターフェースの各々で使用され得る。

前述のヒューマンインターフェースデバイス、ヒューマンアクセス可能なストレージデバイス、およびネットワークインターフェース954は、コンピュータシステム900のコア940に接続され得る。

コア940は、1つまたは複数の中央処理装置（CPU）941、グラフィックス処理装置（GPU）942、フィールドプログラマブルゲートアレイ（FPGA）943の形式の特殊なプログラム可能な処理装置、特定のタスクのためのハードウェアアクセラレータ944などを含み得る。これらのデバイスは、読み取り専用メモリ（ROM）945、ランダムアクセスメモリ（RAM）946、ユーザがアクセスできない内部ハードドライブ、SSDなどの内部大容量ストレージ947と共に、システムバス948を通して接続され得る。いくつかのコンピュータシステムでは、システムバス948は、1つまたは複数の物理プラグの形でアクセス可能であり、追加のCPU、GPUなどによる拡張を可能にすることができる。周辺デバイスは、コアのシステムバス948に直接接続されることも、周辺バス949を介して接続されることもできる。周辺バスのアーキテクチャは、PCI、USBなどを含む。グラフィックスアダプタ950は、コア940に含まれてもよい。

CPU941、GPU942、FPGA943、およびアクセラレータ944は、組み合わせて、前述のコンピュータコードを構成することができる特定の命令を実行することができる。そのコンピュータコードは、ROM945またはRAM946に格納され得る。移行データはまた、RAM946に格納され得るが、永久データは、例えば、内部大容量ストレージ947に格納され得る。1つまたは複数のCPU941、GPU942、大容量ストレージ947、ROM945、RAM946などと密接に関連付けられ得るキャッシュメモリを使用することにより、任意のメモリデバイスへの高速ストレージおよび検索が有効にされ得る。

コンピュータ可読媒体は、様々なコンピュータ実施動作を行うためのコンピュータコードを有することができる。媒体およびコンピュータコードは、本開示の目的のために特別に設計および構築されたものであり得るし、またはそれらは、コンピュータソフトウェア技術の当業者に周知の利用可能な種類のものであり得る。

一例として、限定としてではなく、アーキテクチャ、具体的にはコア940を有するコンピュータシステム900は、1つまたは複数の有形のコンピュータ可読媒体で具体化されたソフトウェアを実行する（1つまたは複数の）プロセッサ（CPU、GPU、FPGA、アクセラレータなどを含む）の結果として機能を提供することができる。そのようなコンピュータ可読媒体は、上記で紹介したようにユーザがアクセス可能な大容量ストレージのほか、コア内部大容量ストレージ947またはROM945などの非一時的性質のコア940の特定のストレージにも関連する媒体であり得る。本開示の様々な実施形態を実装するソフトウェアは、そのようなデバイスに格納され、コア940によって実行され得る。コンピュータ可読媒体は、特定の必要性に応じて、1つまたは複数のメモリデバイスまたはチップを含むことができる。ソフトウェアは、コア940、特にその中のプロセッサ（CPU、GPU、FPGAなどを含む）に、RAM946に格納されたデータ構造の定義およびソフトウェアによって定義されたプロセスによる、そのようなデータ構造の変更を含む、本明細書に記載の特定のプロセスまたは特定のプロセスの特定の部分を実行させることができる。加えて、または代替として、コンピュータシステムは、本明細書に記載の特定のプロセスまたは特定のプロセスの特定の部分を実行するためにソフトウェアの代わりにまたは一緒に動作することができる回路（例えば、アクセラレータ944）に配線されたまたはそうでなければ具体化されたロジックの結果として機能を提供することができる。ソフトウェアへの参照にはロジックを含めることができ、必要に応じてその逆も可能である。必要に応じて、コンピュータ可読媒体への言及は、実行のためのソフトウェアを格納する回路（集積回路（IC）など）、実行のためのロジックを具体化する回路、またはこれらの両方を包含することができる。本開示は、ハードウェアとソフトウェアの任意の適切な組み合わせを包含する。

本開示は、いくつかの非限定的な実施形態を説明しているが、本開示の範囲内にある変更、順列、および様々な代替の同等物が存在する。したがって、当業者は、本明細書に明示的に示されていないかまたは記載されていないが、本開示の原理を具体化し、したがってその趣旨および範囲内にある多数のシステムおよび方法を考案することができることが理解されよう。

100 通信システム
110，120，130，140 端末
150 通信ネットワーク
200 ストリーミングシステム
201 ビデオソース
202 ストリーム
203 ビデオエンコーダ
204 符号化ビデオビットストリーム
205 ストリーミングサーバ
206 ストリーミングクライアント
209 ビデオビットストリーム
210 ビデオデコーダ
211 発信ビデオサンプルストリーム
212 ディスプレイ
213 キャプチャサブシステム
302 パッチ生成モジュール
304 パッチパッキングモジュール
306 形状画像生成モジュール
308 テクスチャ画像生成モジュール
310 平滑化モジュール
312 補助パッチ情報圧縮モジュール
314，316 画像パディングモジュール
318 エントロピー圧縮モジュール
320 グループ拡大モジュール
322，324，326 ビデオ圧縮モジュール
328 マルチプレクサ
332 パッチ情報
334 占有マップ
350 点群フレーム
352 形状画像
354 パディングされた形状画像
356 テクスチャ画像
358 平滑化された形状
360 パディングされたテクスチャ画像
362 圧縮された形状画像
364 圧縮されたテクスチャ画像
365 再構築された形状画像
366 ロスレス符号化
368 ロッシー符号化
370 圧縮された補助パッチ情報
372 圧縮された占有マップ
374 圧縮されたビットストリーム、コード化ビットストリーム
402 デマルチプレクサ
404，406 ビデオ復元モジュール
408 占有マップ復元モジュール
410 補助パッチ情報復元モジュール
412 形状再構築モジュール
414 平滑化モジュール
416 テクスチャ再構築モジュール
418 色平滑化モジュール
460 復元されたテクスチャ画像
462 復元された形状画像
464 復元された占有マップ
466 復元された補助パッチ情報
468 再構築された形状
470 平滑化された形状
472 再構築されたテクスチャ
474 再構築された点群
502 ソース点群
504 再構築された点群
800 装置
810 第1の取得コード
820 第2の取得コード
830 第3の取得コード
840 実行コード
850 決定コード
860 選択コード
870 生成コード
900 コンピュータシステム
901 キーボード
902 マウス
903 トラックパッド
905 ジョイスティック
906 マイク
907 スキャナ
908 カメラ
909 スピーカ
910 タッチスクリーン
920 CD／DVD ROM／RW
921 媒体
922 サムドライブ
923 リムーバブルハードドライブまたはソリッドステートドライブ
940 コア
941 中央処理装置（CPU）
942 グラフィックス処理装置（GPU）
943 フィールドプログラマブルゲートアレイ（FPGA）
944 アクセラレータ
945 読み取り専用メモリ（ROM）
946 ランダムアクセスメモリ（RAM）
947 コア内部大容量ストレージ
948 システムバス
949 周辺バス
950 グラフィックスアダプタ
954 ネットワークインターフェース
955 クラウドコンピューティング環境

Claims (14)

1. ビデオ点群コーディングを使用してビデオストリームを符号化する方法であって、前記方法は、少なくとも1つのプロセッサによって実行され、
   ソース点群を取得するステップと、
   幾何学的に再構築された点群を取得するステップであって、前記幾何学的に再構築された点群はロッシーコーディングを使用して再構築される、ステップと、
   前記幾何学的に再構築された点群に含まれる目標点を取得するステップと、
   前記目標点の最近傍である前記ソース点群のうちの第1の複数の点を決定するために、順方向K次元（KD）ツリー探索が行われるが逆方向KDツリー探索が行われないか、または前記目標点が最近傍である前記ソース点群のうちの第2の複数の点を決定するために、前記逆方向KDツリー探索が行われるが前記順方向K次元ツリー探索が行われない、単方向探索を実行するステップと、
   前記順方向K次元ツリー探索が行われたことに応じて前記第1の複数の点の第1の平均色値に基づいて、または前記逆方向K次元ツリー探索が行われたことに応じて前記第2の複数の点の第2の平均色値に基づいて、平均色値を決定するステップと、
   前記平均色値に基づいて前記目標点の色値を選択するステップと、
   選択された前記色値に基づいて符号化されたビデオストリームを生成するステップと
   を含む、方法。
2. 前記平均色値が、前記第1の平均色値を使用せずに前記第2の平均色値に基づいて決定される、請求項1に記載の方法。
3. 前記第2の平均色値が、以下の式に従って決定され、
   Ψ₂は前記第2の複数の点を表し、
   は前記第2の平均色値を表し、c（q）は前記第2の複数の点に含まれる点qの色を表し、Δ（q，p_r）はqとp_rとの間のユークリッド距離を表す、請求項2に記載の方法。
4. 前記第2の平均色値は、線形モデル、二次モデル、または非線形モデルのうちの少なくとも1つによって修正される、請求項3に記載の方法。
5. 前記第2の平均色値は、整数変換を使用して決定される、請求項4に記載の方法。
6. 前記点qの色と前記整数変換の変換式のすべての可能な組み合わせ事前計算結果を格納するよう構築されたルックアップテーブルを使用して整数乗算演算を置き換える、請求項5に記載の方法。
7. 前記平均色値が、前記第2の平均色値を使用せずに前記第1の平均色値に基づいて決定される、請求項1に記載の方法。
8. 前記第1の平均色値が、以下の式に従って決定され、
   Ψ₁は前記第1の複数の点を表し、
   は前記第1の平均色値を表し、c（q）は前記第1の複数の点に含まれる点qの色を表し、Δ（q，p_r）はqとp_rとの間のユークリッド距離を表す、請求項7に記載の方法。
9. 前記第1の平均色値は、線形モデル、二次モデル、または非線形モデルのうちの少なくとも1つによって修正される、請求項8に記載の方法。
10. 前記第1の平均色値は、整数変換を使用して決定される、請求項9に記載の方法。
11. 前記点qの色と前記整数変換の変換式のすべての可能な組み合わせ事前計算結果を格納するよう構築されたルックアップテーブルを使用して整数乗算演算を置き換える、請求項10に記載の方法。
12. 前記第1の平均色値と前記第2の平均色値とのうちの前記少なくとも一方が、ボクセル化されたソース点群と、ボクセル化された幾何学的に再構築された点群とのうちの少なくとも一方に基づいて決定される、請求項1に記載の方法。
13. ビデオ点群コーディングを使用してビデオストリームを符号化するための装置であって、前記装置は、
    プログラムコードを格納するように構成された少なくとも1つのメモリと、
    前記プログラムコードを読み取り、前記プログラムコードによって命令されたとおりに動作するように構成された少なくとも1つのプロセッサと
    を備え、前記プログラムコードは、前記少なくとも1つのプロセッサに、請求項1から12のいずれか一項に記載の方法を行わせる、装置。
14. コンピュータに、請求項1から12のいずれか一項に記載の方法を行わせる、コンピュータプログラム。

Images