(57)【特許請求の範囲】
【請求項１】
点群からブロックのセットにおける各ブロックを復号して、復号された点群を取得する復号用プロセッサを備える点群復号器であって、各ブロックは点のセットを含み、各ブロックについて、前記復号用プロセッサは、
圧縮されたビットストリームから予測残差のセットを復号し、
前記ブロックにおける所定のロケーションを使用し、
前記予測残差のセットにおける各予測残差について、前記予測残差を前記所定のロケーションに加算することにより点の位置を計算して、前記ブロックについて復号された点のセットを取得し、
前記ブロックのセットにおける前記ブロックについて復号された点は、前記復号された点群を表し、
前記圧縮されたビットストリームは、点群符号器によって生成され、前記点群符号器は、点群から点のブロックを符号化して、符号化された点群を取得し、前記点群は前記ブロックのセットを含み、前記ブロックは前記点のセットを含み、前記ブロックにおける所定のロケーションを使用し、各点について、前記点の位置と前記所定のロケーションとの差を計算して、前記ブロックにおける前記点のセットに対して前記予測残差のセットを取得する、符号化用プロセッサと、
前記圧縮されたビットストリームを介して前記予測残差のセットを送信する送信機と、
を備え、
前記符号化用プロセッサにおいて、
前記点のセットの各点を組織グリッドにおける位置要素にマッピングすることにより、前記点群を組織化し、
前記点のセットは、角度及び半径に従ってスキャンされ、その結果、前記点のセットにおける各点は２次元（２Ｄ）グリッドにマッピングされ、
前記２Ｄグリッドの第１の次元は前記角度に従い、その結果、前記角度が増大するに従い、前記第１の次元に沿った前記グリッドの位置も増大し、
前記２Ｄグリッドの第２の次元は前記半径に従い、その結果、前記半径が増大するに従い、前記第２の次元に沿った前記グリッドにおける位置も増大する、点群復号器。
【請求項２】
点群からブロックのセットにおける各ブロックを復号して、復号された点群を取得する復号用プロセッサを備える点群復号器であって、各ブロックは点のセットを含み、各ブロックについて、前記復号用プロセッサは、
圧縮されたビットストリームから予測残差のセットを復号し、
前記ブロックにおける所定のロケーションを使用し、
前記予測残差のセットにおける各予測残差について、前記予測残差を前記所定のロケーションに加算することにより点の位置を計算して、前記ブロックについて復号された点のセットを取得し、
前記ブロックのセットにおける前記ブロックについて復号された点は、前記復号された点群を表し、
前記圧縮されたビットストリームは、点群符号器によって生成され、前記点群符号器は、点群から点のブロックを符号化して、符号化された点群を取得し、前記点群は前記ブロックのセットを含み、前記ブロックは前記点のセットを含み、前記ブロックにおける所定のロケーションを使用し、各点について、前記点の位置と前記所定のロケーションとの差を計算して、前記ブロックにおける前記点のセットに対して前記予測残差のセットを取得する、符号化用プロセッサと、
前記圧縮されたビットストリームを介して前記予測残差のセットを送信する送信機と、
を備え、
前記符号化用プロセッサにおいて、
前記点のセットを有する領域のデータ依存不均一区画化を実行し、その結果、前記領域の少なくとも１つの次元にわたる前記区画化のロケーションが各点の位置および属性に従って区画を求めるスコア関数によって求められ、
前記スコア関数に対する入力が、探索領域内の点のサブセットであり、前記スコア関数の出力が最大化される場所に対応する前記点のロケーションは、前記次元にわたる前記領域の前記区画化のロケーションに対応する、点群復号器。
【請求項３】
前記符号化用プロセッサにおいて、
不連続性を示す前記点群の領域に関連付けられた点のサブセットを入力として有する前記スコア関数の出力は、不連続性を示さない前記点群の領域に関連付けられた点のサブセットを入力として有する前記スコア関数の出力より高いスコア値である、請求項２に記載の点群復号器。
【請求項４】
点群からブロックのセットにおける各ブロックを復号して、復号された点群を取得する復号用プロセッサを備える点群復号器であって、各ブロックは点のセットを含み、各ブロックについて、前記復号用プロセッサは、
圧縮されたビットストリームから予測残差のセットを復号し、
前記ブロックにおける所定のロケーションを使用し、
前記予測残差のセットにおける各予測残差について、前記予測残差を前記所定のロケーションに加算することにより点の位置を計算して、前記ブロックについて復号された点のセットを取得し、
前記ブロックのセットにおける前記ブロックについて復号された点は、前記復号された点群を表し、
前記圧縮されたビットストリームは、点群符号器によって生成され、前記点群符号器は、点群から点のブロックを符号化して、符号化された点群を取得し、前記点群は前記ブロックのセットを含み、前記ブロックは前記点のセットを含み、前記ブロックにおける所定のロケーションを使用し、各点について、前記点の位置と前記所定のロケーションとの差を計算して、前記ブロックにおける前記点のセットに対して前記予測残差のセットを取得する、符号化用プロセッサと、
前記圧縮されたビットストリームを介して前記予測残差のセットを送信する送信機と、
を備え、
前記符号化用プロセッサにおいて、
前記点のブロックにおける前記点のリサンプリングを実行し、前記リサンプリングは、前記ブロックの前記点のセットにおける点の数を点のサブセットまで低減させることであり、かつ、各点の位置および属性に従って区画を求めるスコア関数のスコアと所定の閾値に基づき、前記点のサブセットを識別し、その結果、前記スコア関数の出力が前記所定の閾値より高い場合、前記点を前記サブセットに含ませるように実行する、点群復号器。
【請求項５】
前記符号化用プロセッサにおいて、
前記各ブロックにおける前記点は、前記点がセンサによって取得された順序に従って処理される、請求項１から４までのいずれか１項に記載の点群復号器。
【請求項６】
前記符号化用プロセッサにおいて、
点の前記符号化は、前記点が、先行して符号化された点と同一であるか又は前記先行して符号化された点の所定の閾値距離内にある場合に、スキップされる、請求項１から４までのいずれか１項に記載の点群復号器。
【請求項７】
前記符号化用プロセッサにおいて、
点の前記符号化は、復号されたときの前記点が、先行して復号された点と同一であるか又は前記先行して復号された点の所定の閾値距離内にある場合に、スキップされる、請求項１から４までのいずれか１項に記載の点群復号器。
【請求項８】
前記所定のロケーションは前記ブロックの中心である、請求項１から４までのいずれか１項に記載の点群復号器。
【請求項９】
点群を復号する方法であって、
メモリに接続された復号用プロセッサを使用して、点群からブロックのセットにおける各ブロックを復号して、復号された点群を取得することであって、各ブロックは点のセットを含み、各ブロックについて、前記復号用プロセッサは、
圧縮されたビットストリームから予測残差のセットを復号し、
前記ブロックにおける所定のロケーションを使用し、
前記予測残差のセットにおける各予測残差について、前記予測残差を前記所定のロケーションに加算することにより点の位置を計算して、前記ブロックに対する復号された点のセットを取得する、
ことを含み、
前記ブロックのセットにおける前記ブロックについての前記復号された点は、前記復号された点群を表し、
前記圧縮されたビットストリームは、符号化用プロセッサを使用して生成され、前記符号化用プロセッサは、
点群から点のブロックを符号化して、符号化された点群を取得し、前記点群は前記ブロックのセットを含み、前記ブロックは前記点のセットを含み、前記ブロックにおける所定のロケーションを使用し、各点について、前記点の位置と前記所定のロケーションとの差を計算して、前記ブロックにおける前記点のセットに対して前記予測残差のセットを取得し、
前記圧縮されたビットストリームを介して前記予測残差のセットを送信機で送信し、
前記点のセットの各点を組織グリッドにおける位置要素にマッピングすることにより、前記点群を組織化し、
前記点のセットは、角度及び半径に従ってスキャンされ、その結果、前記点のセットにおける各点は２次元（２Ｄ）グリッドにマッピングされ、
前記２Ｄグリッドの第１の次元は前記角度に従い、その結果、前記角度が増大するに従い、前記第１の次元に沿った前記グリッドの位置も増大し、
前記２Ｄグリッドの第２の次元は前記半径に従い、その結果、前記半径が増大するに従い、前記第２の次元に沿った前記グリッドにおける位置も増大する、
ことを含む、方法。
【請求項１０】
点群を復号する方法であって、
メモリに接続された復号用プロセッサを使用して、点群からブロックのセットにおける各ブロックを復号して、復号された点群を取得することであって、各ブロックは点のセットを含み、各ブロックについて、前記復号用プロセッサは、
圧縮されたビットストリームから予測残差のセットを復号し、
前記ブロックにおける所定のロケーションを使用し、
前記予測残差のセットにおける各予測残差について、前記予測残差を前記所定のロケーションに加算することにより点の位置を計算して、前記ブロックに対する復号された点のセットを取得する、
ことを含み、
前記ブロックのセットにおける前記ブロックについての前記復号された点は、前記復号された点群を表し、
前記圧縮されたビットストリームは、符号化用プロセッサを使用して生成され、前記符号化用プロセッサは、
点群から点のブロックを符号化して、符号化された点群を取得し、前記点群は前記ブロックのセットを含み、前記ブロックは前記点のセットを含み、前記ブロックにおける所定のロケーションを使用し、各点について、前記点の位置と前記所定のロケーションとの差を計算して、前記ブロックにおける前記点のセットに対して前記予測残差のセットを取得し、
前記圧縮されたビットストリームを介して前記予測残差のセットを送信機で送信し、
前記点のセットを有する領域のデータ依存不均一区画化を実行し、その結果、前記領域の少なくとも１つの次元にわたる前記区画化のロケーションを各点の位置および属性に従って区画を求めるスコア関数によって求め、
前記スコア関数に対する入力が、探索領域内の点のサブセットであり、前記スコア関数の出力が最大化される場所に対応する前記点のロケーションは、前記次元にわたる前記領域の前記区画化のロケーションに対応する、
ことを含む、方法。
【請求項１１】
点群を復号する方法であって、
メモリに接続された復号用プロセッサを使用して、点群からブロックのセットにおける各ブロックを復号して、復号された点群を取得することであって、各ブロックは点のセットを含み、各ブロックについて、前記復号用プロセッサは、
圧縮されたビットストリームから予測残差のセットを復号し、
前記ブロックにおける所定のロケーションを使用し、
前記予測残差のセットにおける各予測残差について、前記予測残差を前記所定のロケーションに加算することにより点の位置を計算して、前記ブロックに対する復号された点のセットを取得する、
ことを含み、
前記ブロックのセットにおける前記ブロックについての前記復号された点は、前記復号された点群を表し、
前記圧縮されたビットストリームは、符号化用プロセッサを使用して生成され、前記符号化用プロセッサは、
点群から点のブロックを符号化して、符号化された点群を取得し、前記点群は前記ブロックのセットを含み、前記ブロックは前記点のセットを含み、前記ブロックにおける所定のロケーションを使用し、各点について、前記点の位置と前記所定のロケーションとの差を計算して、前記ブロックにおける前記点のセットに対して前記予測残差のセットを取得し、
前記圧縮されたビットストリームを介して前記予測残差のセットを送信機で送信し、
前記点のブロックにおける前記点のリサンプリングを実行し、前記リサンプリングは、前記ブロックの前記点のセットにおける点の数を点のサブセットまで低減させることであり、かつ、各点の位置および属性に従って区画を求めるスコア関数のスコアと所定の閾値に基づき、前記点のサブセットを識別し、その結果、前記スコア関数の出力が前記所定の閾値より高い場合、前記点を前記サブセットに含ませる、
ことを含む、方法。
【請求項１２】
点群復号器であって、
先行して復号された点を含むデータが記憶されたメモリと、
圧縮されたビットストリームから点のシーケンスを復号して復号された点群を取得する復号用プロセッサであって、
前記圧縮されたビットストリームから予測残差のシーケンスを復号し、
前記予測残差のシーケンスにおける各予測残差について、前記予測残差を前記メモリに記憶された先行して復号された点の位置に加算することにより、点の位置を計算して、復号された点のシーケンスを取得する、
ものと、
を備え、
前記復号された点のシーケンスは、前記復号された点群を表し、
前記圧縮されたビットストリームは、点群符号器によって生成され、前記点群符号器は、点群の点のシーケンスを符号化して符号化された点群を取得する符号化用プロセッサであって、各点について、前記点の位置と前記メモリに記憶された先行して復号された点との差を計算して、前記点のシーケンスについて予測残差のシーケンスを取得するものと、圧縮されたビットストリームを介して前記予測残差のシーケンスを送信する送信機とを備え、
前記点群の点のシーケンスにおける前記点を並び替えて、連続した点の間の距離が並び替える前の前記点群の距離より小さくなるようにする、点群復号器。
【請求項１３】
点群復号器であって、
先行して復号された点を含むデータが記憶されたメモリと、
圧縮されたビットストリームから点のシーケンスを復号して復号された点群を取得する復号用プロセッサであって、
前記圧縮されたビットストリームから予測残差のシーケンスを復号し、
前記予測残差のシーケンスにおける各予測残差について、前記予測残差を前記メモリに記憶された先行して復号された点の位置に加算することにより、点の位置を計算して、復号された点のシーケンスを取得する、
ものと、
を備え、
前記復号された点のシーケンスは、前記復号された点群を表し、
前記圧縮されたビットストリームは、点群符号器によって生成され、前記点群符号器は、点群の点のシーケンスを符号化して符号化された点群を取得する符号化用プロセッサであって、各点について、前記点の位置と前記メモリに記憶された先行して復号された点との差を計算して、前記点のシーケンスについて予測残差のシーケンスを取得するものと、圧縮されたビットストリームを介して前記予測残差のシーケンスを送信する送信機とを備え、
前記シーケンスにおける前記点群の点を並び替えて、前記点の間の同一の差の発生の頻度が、前記並び替える前の点の間の同一の差の発生の頻度より高くなるようにする、点群復号器。
【請求項１４】
前記先行して復号された点は、前記シーケンスにおける前記点の直前に復号された前記点のシーケンスにおける点に対応する、請求項１２または１３に記載の点群復号器。
【請求項１５】
前記先行して復号された点は、復号された、前記点のシーケンスにおける第１の点に対応する、請求項１２または１３に記載の点群復号器。
【請求項１６】
復号された点は、前記復号された点が、前記復号された点群を表す前記復号された点のシーケンスにおける先行して復号された点と同一であるか、又は前記先行して復号された点から所定の閾値距離内にある場合、前記復号された点群を表す前記復号された点のシーケンスから排除される、請求項１２または１３に記載の点群復号器。
【請求項１７】
前記予測残差のシーケンスにおける第１の予測残差について、３次元（３Ｄ）空間における所定の位置に前記第１の予測残差を加算することにより、前記復号された点のシーケンスのうちの第１の復号された点の位置を計算して、前記復号された点のシーケンスのうちの前記第１の復号された点を取得する、請求項１２または１３に記載の点群復号器。
【請求項１８】
前記３Ｄ空間の代わりにＮ次元空間とする、請求項１７に記載の点群復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、包括的には、点群信号を表現する方法、符号器及び復号器に関し、より詳細には、点群を圧縮し、表現し、処理することに関する。
【背景技術】
【０００２】
点群は、一般に、３次元（３Ｄ）空間に位置する点のセットによって特徴付けられる。点群における各点について、色等の属性又は他のデータをそれらの点に関連付けることができる。点群におけるデータの量が極めて大きくなる可能性があることを前提とすると、ディスクドライブ等の記憶媒体にデータを記憶するために、又は、ネットワーク対応サーバからクライアントデバイスにストリーミングするためにビットストリームにデータをシグナリングする等、データを伝送するために、圧縮が必要とされる。画像を圧縮する方法は十分に確立されているが、３Ｄ点群を圧縮するためには異なる方法が必要であり、その理由は、画素又はピクセルの均一なグリッドを含む画像とは異なり、点群における点は３Ｄ空間の任意の場所に位置する可能性があるためである。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
したがって、点群を圧縮し、表現し、処理する方法、符号器及び復号器が必要とされている。
【課題を解決するための手段】
【０００４】
本開示の実施形態は、点群信号を表現する方法、符号器及び復号器に関し、より詳細には、点群を圧縮し、表現し、処理することに関する。点群は、３次元空間に位置する点のセットによって特徴付けることができ、そこでは、各点に属性又は他のデータを関連付けることができる。本開示の態様は、点群を圧縮することを含み、その理由は、点群におけるデータの量は大きい可能性があり、その結果、記憶媒体にデータを記憶するために、又は、ネットワーク対応サーバからクライアントデバイスにストリーミングするためにビットストリームにデータをシグナリングするため等、データを伝送するために、圧縮が必要となるためである。
【０００５】
点予測に関して、いくつかの実施形態は、点群における各点の所定のロケーションに対する座標を、点位置と所定のロケーションとの間の差を計算しそれをシグナリングすることにより、シグナリングすることを含む。この差は、予測残差とすることができる。所定のロケーションは、処理すべき点を含むブロックの中心とすることができる。所定のロケーションはまた、先行して復号された点のロケーション、例えば、第１の復号された点とすることもできる。
【０００６】
いくつかの実施形態は、点位置と所定のロケーションとの間の差を復号することを含み、この差は、予測残差とすることができる。
【０００７】
いくつかの実施形態は、点群における先行して復号された点に対する各点の座標をシグナリングすることを含む。例えば、点のシーケンスにおける１つの点を所与とすると、その点のロケーションと、連続した順序でその点の直前に処理され又は符号化され又は復号された点のロケーションとの差を、計算することができる。この差は予測残差とすることができる。
【０００８】
いくつかの実施形態は、或る点の点位置と先行して復号された点の位置との間の差を復号することを含む。この差は予測残差とすることができる。先行して復号された点は、その点の前に連続的に復号された点とすることができる。
【０００９】
点の並べ替え及びスキップに関して、いくつかの実施形態は、後続する点の間の距離が最小化されるように点のシーケンスを並べ替えることを含む。更に他の実施形態は、後続する点の間の異なる距離の数が最小化されるように点のシーケンスを並べ替えることを含むことができる。
【００１０】
いくつかの実施形態は、或る点が、先行してシグナリングされた点と同じ場所にあるか又は先行してシグナリングされた点からの閾値距離内にある場合、その点のシグナリングをスキップすることを含む。さらに、所与の復号された点が、先行してシグナリングされた点と同じ場所にあるか又は先行してシグナリングされた点からの閾値距離内にある場合、その点の再構成をスキップすることができる。バウンディングボックス又は座標下限及び上限の外側にある点又は復号された点のシグナリング又は再構成も、スキップすることができる。
【００１１】
データ依存区画化に関して、いくつかの実施形態は、空間の少なくとも１つの次元にわたる区画化のロケーションを求めるスコア関数に基づいて、空間のデータ依存不均一区画化を実行することを含む。そこでは、空間のデータ依存不均一区画化は、オブジェクトを表すデータの測定又は計算とともに、最小又は最大ブロックサイズ等、現区画化構造に関する情報に基づくことができ、関数、すなわちスコア関数は、処理されている現ブロック又はサブブロックを分割すべき方法又は場所を指定することができる。
【００１２】
不規則点群を組織化することに関して、いくつかの実施形態は、不規則点群を、各点を組織グリッド内の位置にマッピングすることによって組織化することを含む。マッピングプロセスは、スキャンプロセスとともに実施することができ、スキャンプロセスでは、点群における点は、スキャン原点に対するそれらの位置に基づき、かつスキャン方向又は角度に基づく順序で、仮想的にスキャンすることができる。
【００１３】
点群をリサンプリング及び再位置合わせすることに関して、いくつかの実施形態は、点群における点のサブセットを識別するためにスコア関数を使用することを含み、点群の後続する処理は点のサブセットに適用される。
【００１４】
いくつかの実施形態は、点群における点をグリッド等の所定のロケーションのサブセットにリサンプリングするか又は位置合わせすることを含む。点ロケーションをシグナリングすることができ、又は、その点が位置合せされた場所を示すインデックスをシグナリングすることができる。
【００１５】
本開示の一実施形態によれば、点群からブロックのセットにおける各ブロックを復号して、復号された点群を取得するプロセッサを備える点群復号器が開示される。そこでは、各ブロックは点のセットを含み、各ブロックについて、プロセッサは、圧縮されたビットストリームから予測残差のセットを復号する。ブロックにおける所定のロケーションを使用し、予測残差の組における各予測残差について、所定のロケーションにその予測残差を加算することにより点の位置を計算して、そのブロックに対する復号された点のセットを取得する。そこでは、ブロックの組におけるブロックについての復号された点は、復号された点群を表す。
【００１６】
本開示の別の実施形態によれば、メモリに接続されたプロセッサを使用して、点群からブロックのセットにおける各ブロックを復号して、復号された点群を取得することを含む、点群を復号する方法が開示される。そこでは、各ブロックは点のセットを含み、各ブロックについて、プロセッサは、圧縮されたビットストリームから予測残差のセットを復号する。この方法は、ブロックにおける所定のロケーションを使用すること、及び予測残差のセットにおける各予測残差について、予測残差を所定のロケーションに加算することにより点の位置を計算して、ブロックについての復号された点のセットを取得することを含む。そこでは、ブロックのセットにおけるブロックについての復号された点は、復号された点群を表す。
【００１７】
本開示の別の実施形態によれば、先行して復号された点を含む、データが記憶されたメモリを備える点群復号器が開示される。点群復号器は、圧縮されたビットストリームから点のシーケンスを復号して復号された点群を取得するプロセッサを備える。プロセッサは、圧縮されたビットストリームから予測残差のシーケンスを復号する。プロセッサは、予測残差のシーケンスにおける各予測残差について、予測残差をメモリに記憶された先行して復号された点の位置に加算することにより、点の位置を計算して、復号された点のシーケンスを取得する。そこでは、復号された点のシーケンスは、復号された点群を表す。
【００１８】
本明細書に開示する実施形態について、添付図面を参照して更に説明する。図示する図面は、必ずしも正確な縮尺ではなく、代わりに、概して、本明細書に開示する実施形態の原理を例示することに重きが置かれている。
【図面の簡単な説明】
【００１９】
【図１Ａ】本開示の実施形態による、第１の点予測方法のステップを示すブロック図である。
【図１Ｂ】本開示の実施形態による、本開示の方法を実施するいくつかの構成要素を示すブロック図である。
【図２Ａ】本開示の実施形態による、データ依存不均一区画化方法を示す概略図である。
【図２Ｂ】従来技術による区画化方法を示す概略図である。
【図３Ａ】本開示の実施形態による、データ依存不均一分割を実行すべき場所を計算するために線に沿ったデータを使用するプロセスを示す概略図であり、データのブロック又はパッチを所与とすると、垂直中間分割位置に沿ったデータがデータ点のスライディングウィンドウによって水平にスキャンされ、そのスライディングウィンドウを使用して、現ブロックを水平に、すなわち垂直線により、例えば、２Ｄグリッドを区画化する場合は左サブブロック及び右サブブロックに分割すべき場所が求められる。
【図３Ｂ】本開示の実施形態による、データ依存不均一分割を実行すべき場所を計算するために線に沿ったデータを使用するプロセスを示す概略図であり、ブロック又はパッチを所与とすると、水平分割位置に沿った又は垂直分割位置に対して直交する線に沿ったデータがデータ点のスライディングウィンドウによって垂直にスキャンされ、そのスライディングウィンドウを使用して、現ブロックを垂直に、すなわち水平線により、例えば、２Ｄグリッドを分割する場合は下サブブロック及び上サブブロックに分割すべき場所が求められる。
【図４Ａ】本開示の実施形態による、データ依存不均一分割を実行すべき場所を計算するためにデータ点の多次元スライディングウィンドウを使用するプロセスを示す概略図であり、データは、水平分割位置に沿って向けられた領域、例えば垂直矩形である。
【図４Ｂ】本開示の実施形態による、データ依存不均一分割を実行すべき場所を計算するためにデータ点の多次元スライディングウィンドウを使用するプロセスを示す概略図であり、データは、垂直分割位置に沿って向けられた領域、例えば水平矩形である。
【図５Ａ】本開示の実施形態による、３Ｄ点群を示す概略図である。
【図５Ｂ】本開示の実施形態による、各点の平面からの距離を表すレンジマップ若しくは深度マップを示す概略図であり、又は、各点の高度若しくは深度は、スコア関数に対するデータ入力として使用される。
【図５Ｃ】本開示の実施形態による、点群又はレンジマップに適用されたスコア関数の出力を示す概略図であり、そこでは、高いスコア値ほど明るい色で示されている。
【図５Ｄ】従来技術による均一分割の一例を示す概略図である。
【図５Ｅ】本開示の実施形態による、データ依存不均一分割方法を示す概略図である。
【図５Ｆ】本開示の実施形態による、データ依存不均一分割方法を示す概略図である。
【図６】本開示の実施形態による、分割プロセスを実施するいくつかのステップのリストを示すフロー図である。
【図７】本開示の実施形態による、データ依存不均一分割が使用される場合に、ビットストリームからデータを復号するいくつかのステップを示すブロック図である。
【図８Ａ】本開示の実施形態による、不規則点群を組織化する方法を示す概略図である。
【図８Ｂ】本開示の実施形態による、例えば２Ｄ空間における組織グリッド又はマトリックスを示す概略図であり、グリッドにおける各位置はインデックスを有する。
【図８Ｃ】本開示の実施形態による、不規則点群を組織化する方法のスキャンプロセスを示す概略図である。
【図８Ｄ】本開示の実施形態による、不規則点群を組織化する方法のマッピングプロセスを示す概略図である。
【発明を実施するための形態】
【００２０】
上記図面は、本明細書に開示する実施形態を示すが、考察において留意するように、他の実施形態も企図される。本開示は、例示的な実施形態を限定としてではなく代表として提示する。当業者であれば、本明細書に開示する実施形態の原理の範囲及び趣旨内にある他の多くの変更形態及び実施形態を考案することができる。
【００２１】
ブロックにおける中心又は所定のロケーションから予測する
図１Ａは、本開示の実施形態による、第１の点予測方法１００Ａのステップを示すブロック図である。例えば、領域の原点又はコーナーに対する各点の座標をシグナリングする代わりに、各点とブロックにおける所定のロケーションとの間の成分毎の差をシグナリングすることができる。例えば、点位置が（ｘ，ｙ，ｚ）であり、ブロックにおける所定のロケーションがブロックの中心（ｘｃ，ｙｃ，ｚｃ）として定義される場合、（ｘ−ｘｃ，ｙ−ｙｃ，ｚ−ｚｃ）がビットストリームにシグナリングされる。
【００２２】
図１Ａのステップ１１０は、メモリに接続されたプロセッサを使用して、点群からブロックのセットにおける各ブロックを復号するように点群を復号して、復号された点群を取得することを含み、各ブロックは点のセットを含む。
【００２３】
図１Ａのステップ１１５は、プロセッサにより、各ブロックについて、圧縮されたビットストリームから予測残差のセットを復号することを含む。
【００２４】
図１Ａのステップ１２０は、そのブロックにおける所定のロケーションを使用することを含む。
【００２５】
図１Ａのステップ１２５は、予測残差の組における各予測残差について、点の位置を、所定のロケーションに予測残差を加算することにより計算して、そのブロックについて復号された点のセットを取得することを含み、ブロックの組におけるブロックについての復号された点は、復号された点群を表す。
【００２６】
図１Ｂは、本開示の実施形態による、本開示の方法を実施するいくつかの構成要素を示すブロック図１００Ｂである。例えば、プロセッサ１２は、方法のために、メモリ１０に接続されている、本開示の符号器又は復号器とすることができる。プロセッサ１２は、クライアントデバイス１６に接続されているネットワーク対応サーバ１４に接続することができる。
【００２７】
先行して復号された点から点のチェーン又はシーケンスを予測する
本開示によれば、別の方法は、第２の点予測方法を含むことができる。第２の方法は、点ロケーション（ｘｎ，ｙｎ，ｚｎ）、ｎ＝１，２，．．．，Ｎのセットを所与とすると、ビットストリームに点ロケーション（ｘｎ，ｙｎ，ｚｎ）をシグナリングすることができることを開示する。ブロックの中心又は所定のロケーションから予測する場合、各点ロケーション（ｘｎ，ｙｎ，ｚｎ）について、ビットストリームに予測残差（ｘｎ−ｘｃ，ｙｎ−ｙｃ，ｚｎ−ｚｃ）がシグナリングされる。点のグループが互いの近くでクラスタリングされている場合等、場合によっては、先行して復号された点を、目下復号される点のための予測子として使用することにより、予測残差を低減させることができる。例えば、第１の点ｎ＝１は、（ｘｎ，ｙｎ，ｚｎ）又は（ｘｎ−ｘｃ，ｙｎ−ｙｃ，ｚｎ−ｚｃ）としてシグナリングすることができる。第２の点ｎ＝２は、（ｘ２−ｘ１，ｙ２−ｙ１，ｚ２−ｚ１）としてシグナリングすることができる。第３の点は、（ｘ３−ｘ２，ｙ３−ｙ２，ｚ３−ｚ２）としてシグナリングすることができ、全てのｎについて以下同様である。
【００２８】
例えば、第２の方法は、点群を復号するために、メモリに接続されたプロセッサを使用して、点群からブロックのセットにおける各ブロックを復号して、復号された点群を取得することを含むことができる。そこでは、各ブロックは点のセットを含み、各ブロックについて、プロセッサは、圧縮されたビットストリームから予測残差のセットを復号する。ブロックにおける所定のロケーションを使用し、予測残差の組における各予測残差について、所定のロケーションに予測残差を加算することにより点の位置を計算して、そのブロックに対する復号された点のセットを取得する。そこでは、ブロックの組におけるブロックについての復号された点は、復号された点群を表す。
【００２９】
本開示によれば、別の方法は、第３の点予測方法を含むことができる。第３の方法は、後続する点を予測するために第１の復号された点（ｘ１，ｙ１，ｚ１）を使用することができ、そのため、点ｎ＝２についてシグナリングされた予測残差は（ｘ２−ｘ１，ｙ２−ｙ１，ｚ２−ｚ１）であり、点ｎ＝３については（ｘ３−ｘ１，ｙ３−ｙ１，ｚ３−ｚ１）であり、全てのｎについて以下同様であることを開示する。
【００３０】
例えば、第３の方法は、先行して復号された点を含むデータが記憶されたメモリを含む、点群復号器を含む。点群復号器は、圧縮されたビットストリームから点のシーケンスを復号して復号された点群を取得するプロセッサを備える。プロセッサは、圧縮されたビットストリームから予測残差のシーケンスを復号する。プロセッサは、予測残差のシーケンスにおける各予測残差について、メモリに記憶された先行して復号された点の位置に予測残差を加算することにより、点の位置を計算して、復号された点のシーケンスを取得する。そこでは、復号された点のシーケンスは復号された点群を表す。
【００３１】
予測残差における大きさ又はエネルギーを低減させる、点又は点のシーケンスの並べ替え
ブロック又は領域における点（ｘｎ，ｙｎ，ｚｎ）、ｎ＝１，２，．．．，Ｎのシーケンスを所与とすると、後続する点の間の距離が最小化されるように、点を並べ替えることができる。そうすることにより、点のチェーン又はシーケンスがシグナリングされる場合に、シグナリングされる予測残差の大きさ又はエネルギーが低減する。
【００３２】
同一の残差の発生の頻度を増大させる、点の並べ替え
ブロック又は領域における点（ｘｎ，ｙｎ，ｚｎ）、ｎ＝１，２，．．．，Ｎのシーケンスを所与とすると、後続する点の間の異なる距離の数が最小化されるように、点を並べ替えることができる。例えば、１つの座標について、５つの連続した点の間の差のシーケンスが、１、４、４、１であるが、連続する点の間の差が３、３、３、３となるように点を並べ替えることができる場合、並べ替えた後の差の合計は並べ替える前の合計より大きくなるが、異なる距離の数は低減する。したがって、これらの差又は予測残差をシグナリングするために、エントロピー符号器等の符号器が使用される場合、点を並べ替えた後に生成された残差は、低減したエントロピーを有することができ、したがって、ビットストリームにシグナリングする必要があるビットの数が低減する。
【００３３】
点が既に復号された点と同一であるか又はそうした点から閾値距離内にある場合、その点の符号化及び／又は復号をスキップする
点のセットを符号化し、それらをビットストリームにシグナリングする場合、所与の点が先行してシグナリングされた点と同じ場所にあるか又は先行してシグナリングされた点から閾値距離内にあるとき、その点はビットストリームにシグナリングされない。
【００３４】
別の実施形態では、所与の復号された点が、先行してシグナリングされた点と同じ場所にあるか又は先行してシグナリングされた点から閾値距離内にある場合、その点は再構成されず、すなわち、再構成された点群に含まれない。したがって、復号された点群における再構成された点の総数を低減させることができ、したがって、メモリ又は記憶要件が低減し、レンダリングする必要のある点の数が低減するためレンダリング速度が改善する。
【００３５】
別の実施形態では、所与の点がバウンディングボックス又は座標下限及び上限外にある場合、その点はビットストリームにシグナリングされない。
【００３６】
別の実施形態では、所与の復号された点がバウンディングボックス又は座標下限及び上限外にある場合、その点は再構成された点群に含まれない。
【００３７】
データ依存不均一区画化
図２Ａを参照すると、本開示の実施形態による、データ依存不均一区画化２０２を実行することができる。データ依存不均一区画化２０２は、最小又は最大ブロックサイズ等、現区画化構造に関する情報とともに、オブジェクトを表すデータに基づく測定又は計算に基づくことができ、関数は、処理されている現ブロック又はサブブロックを分割すべき方法又は場所を指定することができる。例えば、図２Ｂの従来技術による方法２０１に示すように、中間位置で分割し、異なるブロック間でオブジェクトをばらばらにする代わりに、図２Ａの２０２において、本開示によれば、第１の分割は、４つのサブブロック又はサブ区画を生成するが、それらのうちの１つのみ、すなわち右下のみが、オブジェクトデータによって占有される（図２Ａを参照）。同様に、図２Ａは、本開示による、第２の分割が、異なるサブブロックの間でオブジェクトデータを分割することなく、右下ブロックを４つのサブブロックに区画化することを示す。
【００３８】
３Ｄ空間における各点が、２Ｄグリッド上の位置にマッピング又はインデックス付けされる場合、このデータ依存不均一区画化方法はインデックスの２Ｄグリッドに適用することができる。
【００３９】
図２Ｂは、八分木におけるように３Ｄ空間を区画化する従来技術による区画化方法を示す概略図である。特に、図２Ｂは、２０１に示すような四分木による、２Ｄ空間における区画化を示す。２０１における外側境界は、空間の初期ブロック又は区画化を示す。星は、ブロックにおけるデータによって表されるオブジェクトの一例である。判断プロセスを用いて、初期ブロックを２Ｎ個のブロック又は区画（Ｎは空間の次元（２Ｄ空間の場合はＮ＝２、３Ｄ空間の場合はＮ＝３））に分割するか否かが判断される。各区画は、垂直に半分かつ水平に半分にするようにして、２Ｎ個のブロックに分割される。この分割プロセスは、所望の停止基準が満たされるまで、各サブブロック又はサブ区画について繰り返される。
【００４０】
図３Ａは、本開示の実施形態による、データ依存不均一分割を実行すべき場所を計算するために線に沿ったデータを使用するプロセスを例示する概略図であり、そこでは、ブロック又はパッチ３０３を所与とすると、垂直中間分割位置３０５に沿ったデータが、データ点のスライディングウィンドウ３０７によって水平にスキャンされ、これは、現ブロックを水平に、すなわち垂直線３１１により、例えば、２Ｄグリッドを区画化する場合は左サブブロック及び右サブブロックに分割することを意味する。スキップ領域３１３は、スコア関数への入力として使用される探索領域３０７の一方の側にあり、スキップ領域３１５は、探索領域３０７の他方の側にあり、その結果、スキップ領域の幅３１７は、対象のパッチの幅の１／３に設定することができる。
【００４１】
図３Ｂは、本開示の実施形態による、データ依存不均一分割を実行すべき場所を計算するために線に沿ったデータを使用するプロセスを例示する概略図であり、ブロック又はパッチ３２３を所与とすると、水平分割位置３２５に沿ったデータが、データ点のスライディングウィンドウ３２７によって垂直にスキャンされ、これは、現ブロックを垂直に、すなわち水平線３３１により、例えば、２Ｄグリッドを区画化する場合は下サブブロック及び上サブブロックに分割することを意味する。
【００４２】
図３Ａ及び図３Ｂは、データ依存不均一分割を実行すべき場所を計算するために線に沿ったデータを使用する少なくとも１つのプロセスの概略図又は図である。例えば、図３Ａは、垂直中間分割位置３０５に沿ったデータが、データ点のスライディングウィンドウ３０７によって水平にスキャンされる、ブロック又はパッチ３０３を示す。これらのデータ点は、平面からの距離又は深度等、点群における点の位置に関連するデータとすることができ、又は、点は、輝度若しくは色等、データにおける属性に関連付けることができる。スライディングウィンドウはＭ個の点を含み、垂直中間位置にわたるデータが水平にスキャンされ（図３Ａ）、すなわち、スコア関数等の関数への入力として、Ｍ個の点が選択され使用される。ブロックが細くなりすぎるのを防止するために、最小境界距離又はスキップ領域３１５及び３１３を画定することができ（例えば、３１７）、そこでは、スキップ領域の幅はパッチの幅の１／３に設定することができ、それにより最小ブロックサイズが確保される。スライディングウィンドウは、一度に１つのデータ点位置をスライドすることができ、又は、計算を簡略化するために、複数の点、例えば、１つおきの点をスキップすることができる。スコアが計算される各ウィンドウについて、最良スコア、通常は最大又は最小スコアの位置が特定され、その最良スコアに対応する位置３０９は、現ブロックを水平に、すなわち垂直線３１１によって、例えば、２Ｄグリッドを区画化する場合は左サブブロック及び右サブブロックに分割するための分割位置であるものとして、示される。
【００４３】
図３Ｂを参照すると、同じブロックを他の方向に、例えば垂直に分割したい場合、最初の方向に対して直交する方向にこのプロセスを繰り返すことができる。これにより、単数又は複数の上ブロック及び単数又は複数の下ブロックへの垂直分割、すなわち、水平線３３１による分割がもたらされる。このプロセスの出力は、各分割の位置、例えば、スコア関数からもたらされる最大スコアのロケーション３２９、又は、各分割の位置、例えば、パッチのコーナーに対する分割線３３１の位置にマッピングすることができるインデックスである。２Ｄブロックが水平にかつ垂直に分割される場合、ブロックは４つのサブブロックに区画化される。水平区画化のみ又は垂直区画化のみが行われる場合、ブロックは２つのサブブロックに区画化される。ブロックが細くなりすぎるのを防止するために、最小境界距離又はスキップ領域３３３及び３３５を画定することができ（例えば、３３７）、そこでは、スキップ領域の高さはパッチの高さの１／３に設定することができ、それにより最小ブロックサイズが確保される。スライディングウィンドウは、一度に１つのデータ点位置をスライドすることができ、又は、計算を簡略化するために、複数の点、例えば、１つおきの点をスキップすることができる。スコアが計算される各ウィンドウについて、最良スコア、通常は最大又は最小スコアの位置が特定され、その最良スコアに対応する位置３２９は、現ブロックを垂直に、すなわち水平線３３１によって、例えば、２Ｄグリッドを区画化する場合は最上サブブロック及び最下サブブロックに分割するための分割位置であるものとして、示される。
【００４４】
図４Ａは、本開示の実施形態による、ブロック又はパッチ４０３に対してデータ依存不均一分割を実行すべき場所を計算するためにデータ点の多次元スライディングウィンドウを使用するプロセスを示す概略図であり、そこでは、データは、水平分割位置４１１に沿って向けられた領域、例えば垂直矩形４１９である。
【００４５】
図４Ｂは、本開示の実施形態による、ブロック又はパッチ４２３に対してデータ依存不均一分割を実行すべき場所を計算するためにデータ点の多次元スライディングウィンドウを使用するプロセスを示す概略図であり、そこでは、データは、垂直分割位置４３１に沿って向けられた領域、例えば水平矩形４３９である。
【００４６】
図４Ａ及び図４Ｂは、データ依存不均一分割を実行すべき場所を計算するために多次元データを使用する少なくとも１つのプロセスの図である。図３Ａ及び図３Ｂに示すようにスコア関数への入力としてデータの１次元スライディングウィンドウを使用する代わりに、図４Ａ及び図４Ｂでは、入力として、多次元領域、例えば、２Ｄ領域４１９又は４３９のデータを使用することができる。
【００４７】
図４Ａに関して、ブロックが薄くなりすぎるのを防止するために、最小境界距離又はスキップ領域４１５及び４１３を画定することができ（例えば、４１７）、そこでは、スキップ領域の幅はパッチの幅の１／３に設定することができ、それにより最小ブロックサイズが確保される。スライディングウィンドウは、一度に１つのデータ点位置をスライドすることができ、又は、計算を簡略化するために、複数の点、例えば、１つおきの点をスキップすることができる。スコアが計算される各ウィンドウについて、最良スコア、通常は最大又は最小スコアの位置が特定され、その最良スコアに対応する位置４０９は、現ブロックを水平に、すなわち垂直線４１１によって、例えば、２Ｄグリッドを区画化する場合は左サブブロック及び右サブブロックに分割するための分割位置であるものとして、示される。
【００４８】
図４Ｂに関して、同様にブロックが薄くなりすぎるのを防止するために、最小境界距離又はスキップ領域４３３及び４３５を画定することができ（例えば、４３７）、そこでは、スキップ領域の高さはパッチの高さの１／３に設定することができ、それにより最小ブロックサイズが確保される。スライディングウィンドウは、一度に１つのデータ点位置をスライドすることができ、又は、計算を簡略化するために、複数の点、例えば、１つおきの点をスキップすることができる。スコアが計算される各ウィンドウについて、最良スコア、通常は最大又は最小スコアの位置が特定され、その最良スコアに対応する位置４２９は、現ブロックを垂直に、すなわち水平線４３１によって、例えば、２Ｄグリッドを区画化する場合は最上サブブロック及び最下サブブロックに分割するための分割位置であるものとして、示される。
【００４９】
図５Ａは、本開示の実施形態による、３Ｄ点群５１０を示す概略図である。
【００５０】
図５Ｂは、本開示の実施形態による、各点の平面からの距離を表すレンジマップ又は深度マップ５２０を示す概略図であり、又は、各点の高度若しくは深度は、スコア関数に対するデータ入力として使用される。
【００５１】
図５Ｃは、本開示の実施形態による、スコア関数の出力、例えば、グラフ信号処理（ＧＳＰ）スコアマップ５３０を示す概略図であり、そこでは、高いスコア値５３１ほど明るい色を用いて示されている。例えば、このスコア関数は、２Ｄ又は３Ｄ空間に表されるオブジェクトのエッジに沿ったものである場合である可能性があるような不連続を示すパッチ、グリッド又は点群の領域に相対的に高いスコア値を割り当てることができる。
【００５２】
リサンプリング
更に図５Ｃを参照すると、リサンプリング（ブロックにおける点の数を低減させるため）に関して、Ｐ１個の点を含む領域又はブロックを所与とすると、スコア関数５３０を使用して、スコアが閾値より小さいか又は大きいＰ２個の点のサブセットを識別することができる。そして、領域、ブロック又は区画の後続する処理は、Ｐ１個の点の代わりにＰ２個の点を使用して継続する。Ｐ２＜Ｐ１である場合、システムの計算複雑度、又はビットストリームにシグナリングされるデータの量を低減させることができる。
【００５３】
図５Ｄは、５２でのパッチの数を有する従来技術による均一分割方法５４０を示す概略図である。
【００５４】
図５Ｅ及び図５Ｆは、本開示の実施形態による、図５Ｅのデータ依存不均一分割５５０及び図５Ｆのデータ依存不均一分割５６０の方法を示す概略図である。ここで、図５Ｅは、３１個のパッチをもたらす、図３Ａの最大スコア点３０９及び図３Ｂの最大スコア点３２９を計算する場合に、データの線に沿って図３Ａのスライディングウィンドウ３０７及び図３Ｂのスライディングウィンドウ３２７を使用するときの、不均一分割のロケーションを示す。図５Ｆは、３６個のパッチをもたらす、図４Ａの最大スコア点４０９及び図４Ｂの最大スコア点４２９を計算する場合に、データの領域又は矩形に沿って図４Ａのスライディングウィンドウ４０７及び図４Ｂのスライディングウィンドウ４２７を使用するときの、不均一分割のロケーションを示す。具体的には、本開示の実施形態による、図５Ｅのデータ依存不均一分割５５０及び図５Ｆのデータ依存不均一分割５６０は、図５Ｄの従来技術による方法５４０のパッチ、すなわち５２個のパッチより少ないパッチ、それぞれ、図５Ｅの５５０では３１個のパッチ、図５Ｆの５６０では３６個のパッチを示す。
【００５５】
図５Ｂを参照すると、レンジマップ若しくは深度マップ５２０は各点の平面からの距離を表し、又は、各点の高度若しくは深度はスコア関数に対するデータ入力として使用される。スコアマップ５３０において、点群５１０に対応する点ロケーション、又は点群５１０に対応する若しくはレンジマップ５２０に対応するインデックスは、スコア関数が最良であった、例えば最大であった場所において相対的に明るい色で強調表示又は示される。この場合、グラフ信号処理（ＧＳＰ）方法を使用して、スコアを計算することができる。この例で最良スコアが発生するロケーションは、点群５１０又はレンジマップ５２０におけるエッジ又は不連続性に対応する傾向がある。
【００５６】
図５Ｅ及び図５Ｆを参照すると、図３Ａ及び図３Ｂの方法が使用される場合における、図５Ｅの最適な水平及び垂直分割ロケーション５５０が示されている。また、図４Ａ及び図４Ｂの方法が使用される場合における、図５Ｆの最適な水平及び垂直分割ロケーション５６０が示されている。グラフ信号処理（ＧＳＰ）方法は、高速なリサンプリング方法になり得る。例えば、点群における各点の幾何学的情報に対して特定のグラフフィルターが適用される場合、図５Ｃのフィルタリング結果又は出力５３０は、幾何学的特性に関して、フィルターに入力される点又は点の組の重要性を反映するスコアとしての役割を果たすことができる。重要性評価において他の任意の属性が対象である場合、それらに対して同じグラフフィルターを適用することができ、最終的なフィルタリングスコアは、それらの点に関連する幾何学的位置及び属性に対するフィルタリング結果全ての重み付き和とすることができる。
【００５７】
図６は、本開示の実施形態による、分割プロセス６００を実施するいくつかのステップのリストを示すフロー図である。分割プロセスを実施するいくつかのステップは、幅及び高さ等の初期寸法を有する、入力としてブロック、区画又はパッチｒを有する、分割関数、すなわち「関数Ｓｐｌｉｔ（ｒ）」を示すステップ６１０を含むことができる。
【００５８】
ステップ６１５、６２０及び６２５を参照すると、図６のステップ６１５は、高さが幅より大きい場合、これは、「パッチの高さ＞パッチの幅であるか」として表すことができることを示す。そして、ステップ６２０は、高さが幅より大きい場合、分割方向を水平に設定することができ、そうでない場合、ステップ６２５に示すように、分割方向を垂直に設定することができ、すなわち、「分割方向を選択→水平、そうでない場合、分割方向→垂直」であることを示す。
【００５９】
図６のステップ６３０は、その後、スコア関数、例えば、グラフ信号処理スコア関数ＧＳＰｓｃｏｒｅＳｃａｎ（ｃｏｎｖ．ｗｉｄｔｈ）が計算されることを示し、ここで、ｃｏｎｖ．ｗｉｄｔｈは、探索領域のサイズ、又はサイズ及び寸法を示す。また、ｃｏｎｖ．ｗｉｄｔｈは、スキップ領域のサイズ等、他の情報を含むことができる。スコア関数は、ｍａｘ＿ｓｃｏｒｅ＿ｌｏｃａｔｉｏｎを返し、これは、ロケーション、例えば、スコアが最適であるロケーションの水平又は垂直位置又はオフセットであり、すなわち、「ｍａｘ＿ｓｃｏｒｅ＿ｌｏｃａｔｉｏｎ＝ＧＳＰｓｃｏｒｅＳｃａｎ（ｃｏｎｖ．ｗｉｄｔｈ)」である。ブロック、区画又はパッチ又は領域ｒは、２つの領域ｒ１（ステップ６３５）及びｒ２（ステップ６４０）に分割することができる。
【００６０】
図６のステップ６３５は、ブロック、区画又はパッチ又は領域（ｒ）を領域１（ｒ１）に分割することができることを示し、そこでは、ｒ１は、領域における位置が分割ロケーションの一方の側にある場合に対応し、すなわち、ｒ１＝分割方向に対する位置がｍａｘ＿ｓｃｏｒｅ＿ｌｏｃａｔｉｏｎ未満である（＜）、パッチにおける点の組である。
【００６１】
図６のステップ６４０は、領域２（ｒ２）に分割することができるブロック、区画又はパッチ又は領域（ｒ）を示し、そこでは、ｒ２は、位置が分割ロケーションの他方の側にある場合に対応し、すなわち、ｒ２＝分割方向に対する位置がｍａｘ＿ｓｃｏｒｅ＿ｌｏｃａｔｉｏｎ以上である（≧）、パッチにおける点の組である。
【００６２】
図６のステップ６４５は、サブ区画ｒ１に対して、例えば、サブ区画が、最小サイズ又は寸法等の所定基準を満足させる、すなわち、ｒ１の寸法＞指定された単数又は複数の寸法である場合に、この分割プロセスを繰り返すことができることを示す。
【００６３】
図６のステップ６５０は、サブ区画が、ｒ１が指定された寸法より大きいという基準を満足させる場合、関数Ｓｐｌｉｔ（ｒ１）を呼び出すことを示し、すなわち、ｒ１の寸法が指定された単数又は複数の寸法より大きい（＞）場合、関数Ｓｐｌｉｔ（ｒ１）を呼び出す。
【００６４】
図６のステップ６５５は、サブ区画が基準を満足させない場合、ｒ１分割プロセスが終了したことを示し、すなわち、ｒ１の分割を終了する。
【００６５】
図６のステップ６６０は、サブ区画ｒ２に対して、例えば、サブ区画が、最小サイズ又は寸法等の所定基準を満足させる、すなわち、ｒ２の寸法＞指定された単数又は複数の寸法である場合に、この分割プロセスを繰り返すことができることを示す。
【００６６】
図６のステップ６６５は、サブ区画が、ｒ２が指定された寸法より大きいという基準を満足させる場合、関数Ｓｐｌｉｔ（ｒ２）を呼び出すことを示し、すなわち、ｒ２の寸法が指定された単数又は複数の寸法より大きい（＞）場合、関数Ｓｐｌｉｔ（ｒ２）を呼び出す。
【００６７】
図６のステップ６７０は、サブ区画が基準を満足させない場合、ｒ２分割プロセスが終了したことを示し、すなわち、ｒ２の分割を終了する。
【００６８】
図７は、本開示の実施形態による、データ依存不均一分割が使用される場合に、ビットストリームからデータを復号するいくつかのステップを示すブロック図である。例えば、図７は、データ依存不均一分割が使用される場合に、データを復号するために使用されるビットストリームについてのシンタックスを列挙する。初期パッチ、領域又はブロックのサイズ、例えば高さ及び幅が復号される（７０１）。その領域についての分割フラグが復号される（７０２）。分割の存在は、分割フラグが真（ｙｅｓ）であるか又は偽（ｎｏ）であるかを判断する（７０５）ことによって判断される。例えば、１のフラグ値は分割の存在を示すことができ、０のフラグ値は、分割が存在しないことを示すことができる。分割フラグが真（ｙｅｓ）、例えば１である場合、その領域はサブ領域に分割される。分割フラグが偽（ｎｏ）、例えば０である場合、その領域はそれ以上分割されない。分割フラグが１である場合、各サブ領域を画定する分割ロケーション又は分割インデックスが復号される（７０３）。分割ロケーションは、オフセット、絶対ロケーション若しくは座標、領域のコーナー等、現領域における事前指定位置からのオフセットを指定する整数、水平、垂直、若しくは水平及び垂直オフセット、又は、各インデックスを水平、垂直、若しくは水平及び垂直オフセットにマッピングするルックアップテーブルへのインデックスとすることができる。分割フラグの組は、区画又はサブ区画の組全体についての階層的な分割を画定する分割木の指定とみなすことができる。分割フラグが偽（ｎｏ）、例えば０である場合、その領域はそれ以上分割されず、その領域に関連するデータが復号され（７０４）、その後、方法は、領域又はサブ領域についての復号シンタックスを終了する（７０９）。このデータは、パッチを適合するための制御点、量子化された予測残差、点ロケーションデータ又は属性データを含むことができる。分割フラグが真（ｙｅｓ）、例えば１であり、したがって、サブ領域が画定される場合、７０３によって出力された各サブ領域について、シンタックスは、７０２から開始して各サブ領域について繰り返される。７０１に戻って幅及び高さを指定する必要はなく、その理由は、復号器は、分割ロケーションに基づいて各サブ領域の幅及び高さを推測することができるためである。
【００６９】
更に図７を参照すると、分割インデックスは、限定されないが、
（１）現ブロック又はグリッドにおける事前指定位置からのオフセットを指定する整数、
（２）水平、垂直、又は水平及び垂直オフセット、
（３）各インデックスを水平、垂直、又は水平及び垂直オフセットにマッピングするルックアップテーブルに対するインデックス、
を含むことが留意される。
【００７０】
グリッドに対する位置合せ／リサンプリング
任意に配置された点を含む領域、ブロック又は区画を所与とすると、それらの点は、ロケーションの所定のサブセットにリサンプリング又は位置合せされる。例えば、各点の座標は、０．０〜１．０の浮動小数点数を含む場合、全ての座標が０．１の倍数であるように、量子化又は再位置決めプロセス等を通して位置合わせすることができる。したがって、この例では、点は、０．１分解能のグリッドに位置合せされる。したがって、この位置合せ又はリサンプリングにより、各点についてのあり得る座標の数が低減し、それにより、ビットストリームにシグナリングする必要がある座標についてのあり得る異なる値の数が低減する。
【００７１】
別の実施形態では、座標は、直接シグナリングされず、インデックスがシグナリングされる。例えば、各点の座標が０．０以上でありかつ１．０未満である場合、かつ、グリッド分解能が０．５である場合、その領域における点座標は、０．０又は０．５に再位置合わせされる。その場合、１ビットフラグを用いて、座標が０．０又は０．５に位置合わせされたか否かを示すことができる。グリッド分解能が１．０である場合、再位置合わせされた点座標は、領域の原点又はコーナーとともに位置合わせされるため、それらの点座標を示すために何もシグナリングする必要はない。
【００７２】
不規則点群を組織化する方法
図８Ａは、本開示の実施形態による、不規則点群を組織化する方法を示す概略図である。
【００７３】
図８Ｂは、本開示の実施形態による、例えば２Ｄ空間における組織グリッド又はマトリックスを示す概略図であり、グリッドにおける各位置はインデックスを有する。
【００７４】
図８Ｃは、本開示の実施形態による、不規則点群を組織化する方法のスキャンプロセスを示す概略図である。
【００７５】
図８Ｄは、本開示の実施形態による、不規則点群を組織化する方法のマッピングプロセスを示す概略図である。
【００７６】
例えば、図８Ａの点群８０１は、座標（ｘｎ，ｙｎ，ｚｎ）、ｎ＝１，２，．．．，ＮにおいてＮ個の任意に配置された点を有することができ、不規則点群であるものとして示されている。この例では、各点に文字Ａ〜Ｇが付されている。図８Ｂの組織グリッド８０２は、例えば２Ｄ空間におけるマトリックス又はグリッドとして定義され、グリッドの各位置はインデックスを有する。２Ｄグリッドの場合、図８Ｂの水平インデックスｕ  ８０３及び垂直インデックスｖ  ８０４がある。図８Ａの点群８０１における各点が、図８Ｂの組織グリッド８０２における位置にマッピングされ、したがって組織化される。したがって、点群における各点は、（ｕ，ｖ）を介してインデックス付けすることができる。したがって、（ｕ，ｖ）空間８０２の後続する区画化は、点群８０１を、（ｕ，ｖ）空間の所与の区画における各要素が点群８０１における点のサブセットに対応する点のサブグループに区画化する。
【００７７】
１つの実施形態では、点群８０１における各点の、図８Ｂの組織グリッド８０２における位置へのマッピングは、点群が符号化される前に事前に確定されるか又は既知である。
【００７８】
別の実施形態では、プロセスは、図８Ａの点群８０１の各点を、図８Ｂの組織グリッド８０２における位置にマッピングする。このプロセスは、図８Ｃのスキャンプロセス８１０とすることができる。３Ｄ空間における固定位置等の位置が、図８Ｃのスキャン原点８１１として指定される。図８Ａの点群８０１における点は、図８Ｃのスキャン方向８１２に基づく順序で、スキャン原点に対するそれらの点の位置に基づいて仮想的にスキャンされる。スキャン方向は、例えば、固定方向に対する角度θによって指定することができる。Ｊ回のスキャンがあり、各スキャンは、図８Ｃに示す、スキャン原点からの半径又は距離ｒｊ、ｊ＝１，２，．．．，Ｊ８１３を有する。図８Ｄのマッピング例８２０では、点群は、それぞれ半径ｒ１、ｒ２、ｒ３でスキャンされる（８３０、８３２、８３４）。この場合、半径の数Ｊは、組織グリッドのｖ方向における図８Ｂの要素Ｖ  ８０４の数に対応する。スキャンから所与の閾値距離内の点群における全ての点は、そのスキャンに関連付けられ、その後、後続するスキャンに対する後の考慮から除去される。スキャンが動作する角度の範囲は、Ｕ個の等しい区画に分割され、そこで、Ｕは、組織グリッドのｕ方向における図８Ｂの要素８０３の数である。スキャン半径ｒｊを所与とすると、その半径に関連する図８Ｄのスキャン８２０は、Ｕ個の区画に分割することができる。これらの区画は、スキャン方向８２０に関して等しく間隔を空けて配置することができる。スキャンｒｊに関連付けられた点群における全ての点について、それらの点の各々は、スキャンの区画に対応する組織グリッドに対するインデックス位置ｕに割り当てられる。Ｕの値が大きいほど、より長いスキャン、又はより小さい区画を有するスキャン、例えば、より分解能の高いスキャンのいずれかに対応する。８２０において、点Ｂ及びＤは、第１のスキャンに関連付けられ、組織グリッドの対応する列ｖ＝１に配置される。点Ａ及びＣは第２のスキャンに関連付けられ、点Ｅ、Ｆ及びＧは第３のスキャンに関連付けられる。点群における各点の組織グリッドに対する図８Ｄの最終的なマッピング８２１により、３Ｄ点群における各点を、組織グリッドにおけるロケーション（ｕ，ｖ）によってインデックス付けすることができる。組織グリッドにおける空位置は、点群における点にマッピングされない。このようにマッピングすることにより、３Ｄ空間において互いに隣接する点は、組織グリッドにおいて互いに隣接する可能性が高い。したがって、組織グリッドにおける領域又は点のグループを選択することは、３Ｄ空間においての関連する点グループを選択する可能性が高い。
【００７９】
別の実施形態では、Ｕ及びＶは十分に大きいため、点群における全ての点が、組織グリッドにおける一意の位置にマッピングされる。
【００８０】
別の実施形態では、組織グリッドにおける同じ位置に２つ以上の点をマッピングすることができる。この場合、組織グリッドにおける所与の位置にマッピングされる点の組は、点位置の平均又は点位置の他の何らかの関数等、単一点によって表すことができる。
【００８１】
別の実施形態では、組織グリッドは、疎であり、すなわち多くの空位置を有する可能性がある。この場合、空位置の数を低減させるように、組織グリッドをリサンプリング又はダウンサンプリングすることができる。これを達成する１つの方法例は、組織グリッドの１つのエッジに向かって非空位置をシフトさせるか又は圧縮することによる。別の方法は、点が排除された行又は列を、除去されていない行又は列のうちの対応する行又は列にグループ化することによって、組織グリッドにおける行又は列の数を低減させることができる。複数の点を含む組織グリッドの除去されていない要素を、上述したような単一点に置き換えることができる。
【００８２】
メモリと通信するプロセッサを含む符号器及び復号器を使用してシーンを表現する点群を符号化及び復号する方法は、データ依存不均一区画化を実行するステップと、ブロックにおける点の数を低減させるようにリサンプリングするステップと、点をグリッドに位置合わせ及びリサンプリングするステップと、ブロックにおける中心又は所定のロケーションから点を予測するステップと、先行して復号された点から点のチェーン又はシーケンスを予測するステップと、連続した点の間の距離が最小化されるように点群の点のシーケンスにおける点を並べ替えるステップと、点の間の同一の差の発生の頻度が最大化されるようにシーケンスにおける点群の点を並べ替えるステップと、点が、既に復号された点と同一であるか又はそうした点から指定された閾値距離内にある場合、その点の符号化又は復号をスキップするステップと、各点又は点のグループを組織グリッドにおける位置要素にマッピングすることにより、不規則点群を組織化するステップとを含む。
【図１Ａ】
0006949197.tif 000002
【図１Ｂ】
0006949197.tif 000003
【図２Ａ】
0006949197.tif 000004
【図２Ｂ】
0006949197.tif 000005
【図３Ａ】
0006949197.tif 000006
【図３Ｂ】
0006949197.tif 000007
【図４Ａ】
0006949197.tif 000008
【図４Ｂ】
0006949197.tif 000009
【図５Ａ】
0006949197.tif 000010
【図５Ｂ】
0006949197.tif 000011
【図５Ｃ】
0006949197.tif 000012
【図５Ｄ】
0006949197.tif 000013
【図５Ｅ】
0006949197.tif 000014
【図５Ｆ】
0006949197.tif 000015
【図６】
0006949197.tif 000016
【図７】
0006949197.tif 000017
【図８Ａ】
0006949197.tif 000018
【図８Ｂ】
0006949197.tif 000019
【図８Ｃ】
0006949197.tif 000020
【図８Ｄ】
0006949197.tif 000021