(57)【要約】  本開示は、木構造化可能なデータ群の解像度を部分的に制御することができるようにする情報処理装置および方法に関する。OctreeパタンのデータであるOctreeパタンデータを符号化し、そのOctreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報を含むビットストリームを生成する。また、ビットストリームを復号し、Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報に基づいて、その最下位レベルと異なるレベルの葉ノードを含むOctreeパタンを構築する。本開示は、例えば、情報処理装置、画像処理装置、電子機器、情報処理方法、またはプログラム等に適用することができる。
2019069711.tif 000002
【特許請求の範囲】
【請求項１】
OctreeパタンのデータであるOctreeパタンデータを符号化し、前記Octreeパタンの、前記Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報を含むビットストリームを生成する符号化部
を備える情報処理装置。
【請求項２】
前記深さ制御情報は、前記Octreeパタンの前記最下位レベルよりも上位のレベルの前記深さ制御情報に対応する特定のノードが葉ノードである、ことを示す所定のビット列である
請求項１に記載の情報処理装置。
【請求項３】
前記所定のビット列は、前記Octreeパタンデータにおいて、前記Octreeパタンの前記最下位レベルよりも上位のレベルのノードに設定されており、前記所定のビット列が設定された前記ノードが葉ノードであることを示すビットパタンを有し、
前記符号化部は、前記Octreeパタンの前記最下位レベルよりも上位のレベルの葉ノードに前記所定のビット列が設定された前記Octreeパタンデータを符号化して前記ビットストリームを生成するように構成される
請求項２に記載の情報処理装置。
【請求項４】
前記Octreeパタンの前記最下位レベルと異なるレベルの所望のノードに前記所定のビット列を設定する設定部をさらに備え、
前記符号化部は、前記設定部が設定した前記所定のビット列を含む前記Octreeパタンデータを符号化して前記ビットストリームを生成するように構成される
請求項３に記載の情報処理装置。
【請求項５】
前記深さ制御情報は、前記ビットストリームにおいて、前記Octreeパタンの前記最下位レベルよりも上位のレベルの前記深さ制御情報に対応する特定のノードが葉ノードであるかを示す所定のフラグ情報である
請求項１に記載の情報処理装置。
【請求項６】
前記符号化部は、前記ビットストリームの、前記Octreeパタンの前記最下位レベルよりも上位のレベルの葉ノードに対応する位置に、前記位置に対応するノードが葉ノードであるかを示す前記所定のフラグ情報を挿入する
請求項５に記載の情報処理装置。
【請求項７】
前記Octreeパタンの前記最下位レベルと異なるレベルにおいて、葉ノードとするノードを特定する特定部をさらに備え、
前記符号化部は、前記ビットストリームの、前記特定部により特定された前記ノードに対応する位置に前記所定のフラグ情報を挿入するように構成される
請求項６に記載の情報処理装置。
【請求項８】
前記深さ制御情報は、前記Octreeパタンの前記最下位レベルの前記深さ制御情報に対応する特定のノードに対する子孫ノードの追加に関する追加情報である
請求項１に記載の情報処理装置。
【請求項９】
前記符号化部は、前記ビットストリームの、前記Octreeパタンの前記最下位レベルの前記子孫ノードを追加するノードに対応する位置に、前記追加情報を挿入する
請求項８に記載の情報処理装置。
【請求項１０】
前記追加情報は、前記ビットストリームの前記追加情報が挿入された前記位置に対応するノードがさらに分割されるかを示す所定のフラグ情報を含む
請求項９に記載の情報処理装置。
【請求項１１】
前記追加情報は、追加する前記子孫ノードの深さに関する情報をさらに含む
請求項１０に記載の情報処理装置。
【請求項１２】
OctreeパタンのデータであるOctreeパタンデータを符号化し、前記Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報を含むビットストリームを生成する
情報処理方法。
【請求項１３】
ビットストリームを復号し、Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報に基づいて、前記最下位レベルと異なるレベルの前記葉ノードを含む前記Octreeパタンを構築する復号部
を備える情報処理装置。
【請求項１４】
前記深さ制御情報は、前記Octreeパタンの前記最下位レベルよりも上位のレベルの前記深さ制御情報に対応する特定のノードが葉ノードである、ことを示す所定のビット列である
請求項１３に記載の情報処理装置。
【請求項１５】
前記所定のビット列は、前記Octreeパタンの前記最下位レベルよりも上位のレベルの葉ノードに設定されており、前記所定のビット列が設定された前記ノードが葉ノードであることを示すビットパタンを有する
請求項１４に記載の情報処理装置。
【請求項１６】
前記深さ制御情報は、前記ビットストリームにおいて、前記Octreeパタンの前記最下位レベルよりも上位のレベルの前記深さ制御情報に対応する特定のノードが、葉ノードであるかを示す所定のフラグ情報である
請求項１３に記載の情報処理装置。
【請求項１７】
前記所定のフラグ情報は、前記ビットストリームの、前記Octreeパタンの前記最下位レベルよりも上位のレベルの葉ノードに対応する位置に挿入されており、前記位置に対応するノードが葉ノードであるかを示す
請求項１６に記載の情報処理装置。
【請求項１８】
前記深さ制御情報は、前記Octreeパタンの前記最下位レベルの前記深さ制御情報に対応する特定のノードに対する子孫ノードの追加に関する追加情報である
請求項１３に記載の情報処理装置。
【請求項１９】
前記追加情報は、前記ビットストリームの、前記Octreeパタンの前記最下位レベルの前記子孫ノードを追加するノードに対応する位置に挿入されている
請求項１８に記載の情報処理装置。
【請求項２０】
ビットストリームを復号し、Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報に基づいて、前記最下位レベルと異なるレベルの前記葉ノードを含む前記Octreeパタンを構築する
情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、情報処理装置および方法に関し、特に、木構造化可能なデータ群の解像度を部分的に制御することができるようにした情報処理装置および方法に関する。
【背景技術】
【０００２】
従来、点群の位置情報や属性情報等により３次元構造を表すポイントクラウドや、頂点、エッジ、面で構成され、多角形表現を使用して３次元形状を定義するメッシュの頂点データの圧縮方法として、例えばOctree等のような、ボクセル（Voxel）を用いた量子化があった（例えば非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】R. Mekuria, Student Member IEEE, K. Blom, P. Cesar., Member, IEEE, "Design, Implementation and Evaluation of a Point Cloud Codec for Tele-Immersive Video",tcsvt_paper_submitted_february.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、Octreeパタンでは、全てのポイントが同一解像度で表現される。そのため、ポイントクラウドにおいて一部の領域のポイントの解像度を他の領域の解像度と異なるものとする場合に、Octree符号化を適用することは困難であった。【０００５】
本開示は、このような状況に鑑みてなされたものであり、木構造化可能なデータ群の解像度を部分的に制御することができるようにするものである。
【課題を解決するための手段】
【０００６】
本技術の一側面の情報処理装置は、OctreeパタンのデータであるOctreeパタンデータを符号化し、前記Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報を含むビットストリームを生成する符号化部備える情報処理装置である。【０００７】
本技術の一側面の情報処理方法は、OctreeパタンのデータであるOctreeパタンデータを符号化し、前記Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報を含むビットストリームを生成する情報処理方法である。【０００８】
本技術の他の側面の情報処理装置は、ビットストリームを復号し、Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報に基づいて、前記最下位レベルと異なるレベルの前記葉ノードを含む前記Octreeパタンを構築する復号部を備える情報処理装置である。【０００９】
本技術の他の側面の情報処理方法は、ビットストリームを復号し、Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報に基づいて、前記最下位レベルと異なるレベルの前記葉ノードを含む前記Octreeパタンを構築する情報処理方法である。【００１０】
本技術の一側面の情報処理装置および方法においては、OctreeパタンのデータであるOctreeパタンデータが符号化され、そのOctreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報を含むビットストリームが生成される。【００１１】
本技術の他の側面の情報処理装置および方法においては、ビットストリームが復号され、Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報に基づいて、その最下位レベルと異なるレベルの葉ノードを含むOctreeパタンが構築される。
【発明の効果】
【００１２】
本開示によれば、情報を処理することができる。特に、木構造化可能なデータ群の解像度を部分的に制御することができる。
【図面の簡単な説明】
【００１３】
【図１】ポイントクラウドの例を説明する図である。
【図２】Octreeパタンの深さ制御の例について説明する図である。
【図３】符号化装置の主な構成例を示すブロック図である。
【図４】符号化の概要の例を説明する図である。
【図５】深さ制御情報の例を説明する図である。
【図６】符号化部の主な構成例を示すブロック図である。
【図７】符号化処理の流れの例を説明するフローチャートである。
【図８】ジオメトリデータ符号化処理の流れの例を説明するフローチャートである。
【図９】符号化部の主な構成例を示すブロック図である。
【図１０】ジオメトリデータ符号化処理の流れの例を説明するフローチャートである。
【図１１】復号装置の主な構成例を示すブロック図である。
【図１２】復号部の主な構成例を示すブロック図である。
【図１３】復号処理の流れの例を説明するフローチャートである。
【図１４】ビットストリーム復号処理の流れの例を説明するフローチャートである。
【図１５】深さ制御情報の例を説明する図である。
【図１６】符号化部の主な構成例を示すブロック図である。
【図１７】ジオメトリデータ符号化処理の流れの例を説明するフローチャートである。
【図１８】ジオメトリデータ符号化処理の流れの例を説明する、図１７に続くフローチャートである。
【図１９】符号化部の主な構成例を示すブロック図である。
【図２０】ジオメトリデータ符号化処理の流れの例を説明するフローチャートである。
【図２１】ジオメトリデータ符号化処理の流れの例を説明する、図２０に続くフローチャートである。
【図２２】復号部の主な構成例を示すブロック図である。
【図２３】ビットストリーム復号処理の流れの例を説明するフローチャートである。
【図２４】深さ制御情報の例を説明する図である。
【図２５】符号化部の主な構成例を示すブロック図である。
【図２６】ジオメトリデータ符号化処理の流れの例を説明するフローチャートである。
【図２７】復号部の主な構成例を示すブロック図である。
【図２８】ビットストリーム復号処理の流れの例を説明するフローチャートである。
【図２９】コンピュータの主な構成例を示すブロック図である。
【発明を実施するための形態】
【００１４】
以下、本開示を実施するための形態（以下実施の形態とする）について説明する。なお、説明は以下の順序で行う。
１．Octreeパタンの部分的な深さ制御
２．第１の実施の形態（終端識別ビットパタン）
３．第２の実施の形態（end_of_node_one_bit）
４．第３の実施の形態（split_voxel_flag）
５．その他
【００１５】
＜１．Octreeパタンの部分的な深さ制御＞
＜ポイントクラウド＞
従来、点群の位置情報や属性情報等により３次元構造を表すポイントクラウドや、頂点、エッジ、面で構成され、多角形表現を使用して３次元形状を定義するメッシュ等のデータが存在した。
【００１６】
例えばポイントクラウドの場合、図１のＡに示されるような立体構造物を、図１のＢに示されるような多数の点（ポイントデータ）の集合（点群）として表現する。つまり、ポイントクラウドのデータ（ポイントクラウドデータとも称する）は、この点群の各点の位置情報や属性情報（例えば色等）により構成される。したがってデータ構造が比較的単純であるとともに、十分に多くの点を用いることにより任意の立体構造を十分な精度で表現することができる。
【００１７】
しかしながら、このようなポイントクラウドやメッシュ等のデータはそのデータ量が比較的大きいので、符号化等によるデータ量の圧縮が求められている。例えば、OctreeやKDtree等といったボクセル（Voxel）を用いた符号化方法が考えられた。ボクセルは、符号化対象の位置情報を量子化するためのデータ構造である。
【００１８】
＜Octree符号化＞
このボクセル構造のデータ（ボクセルデータとも称する）は１階層のデータである。つまり全てのボクセルの大きさは互いに同一である。Octree符号化は、このようなボクセルデータを、ポイントが存在する空間を再帰的に２×２×２分割（x,y,zの各方向に２分割）した最大８分木構造（Octreeパタンとも称する）に変換する。このようにすることにより、ポイントが存在しない空間をまとめる（上位レベル化する）ことができるので、情報量を低減させることができる。
【００１９】
つまり、Octreeパタンでは、ポイントが存在する領域がノードとされる。各ノードには、その領域（空間）を２×２×２分割（８分割）した各領域（空間）についてポイントが存在するか否かを示すビット列が設定される。例えば、その各領域のポイントの存在の有無を１ビットで表現した（値「０」の場合ポイントが存在しないことを示し、値「１」の場合ポイントが存在することを示すようにした）、８ビットのビット列を各ノードに設定するようにする。このビット列の値が「１」のビットに対応する領域についてのみ子ノードが形成される。つまり、最大８分木となる。このような分木が繰り返され、レベルがパラメータセット等に設定された深さ（すなわち最下位レベル）に達すると、分木が終了する。
【００２０】
つまり、Octreeパタンにおいて、子ノードを持たないノード（葉ノード）は、パラメータセット等において設定されるOctreeパタンの深さに対応する最下位レベルにのみ形成される。したがって、このOctreeパタンの深さ（レベル数）は、図２のＡに示される木構造のように、ポイントが存在する領域については全て同一である。換言するに、全てのポイントが同一の解像度で表現される。
【００２１】
ところで、ポイントクラウドのポイントの解像度を部分的に制御する機能が求められている。部分的な制御とは、例えば、一部のポイントの解像度を他の部分のポイントの解像度と異なるものにする等、全ポイントの解像度を統一させないようにすることである。
【００２２】
例えば、ポイントクラウドに注目領域（ROI（Region of Interest））が存在する場合、その注目領域のポイントを他の領域のポイントよりも高解像度化させることが考えられる。このようにすることにより、主観画質を需要に応じて向上させることができる。また、符号化効率を向上させることもできる。
【００２３】
また、例えば、ポイントがボクセルグリッドに一致し、解像度を上げなくても（他のポイントよりも低解像度であっても）そのポイントを表現することができる場合が考えられる。このようにすることにより、Octreeパタンの不要なノードの増大を抑制し、符号化効率の低減を抑制することができる。
【００２４】
さらに、例えば、Octree符号化と、その他の符号化ツールとを組み合わせ、その他の符号化ツールにより一部のノードを高解像度化する場合が考えられる。
【００２５】
しかしながら、上述のように、Octreeパタンでは葉ノードが最下位レベルにのみ形成されるため、このようなポイントの解像度の部分的な制御を表現することができなかった。つまり、木構造化可能なデータ群の解像度を部分的に制御することは困難であった。換言するに、上述のようにポイントクラウドのポイントの解像度を部分的に制御する場合、Octree符号化を適用することが困難になり、符号化効率が低減するおそれがあった。つまり、データ群の解像度を部分的に制御する場合に、そのデータ群の木構造化が困難になり、符号化効率が低減するおそれがあった。
【００２６】
＜深さ制御＞
そこで、OctreeパタンのデータであるOctreeパタンデータを符号化し、そのOctreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに、葉ノードが形成されることを示す『深さ制御情報』を含むビットストリームを生成するようにする。
【００２７】
例えば、情報処理装置において、OctreeパタンのデータであるOctreeパタンデータを符号化し、そのOctreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに、葉ノードが形成されることを示す『深さ制御情報』を含むビットストリームを生成する符号化部を備えるようにする。
【００２８】
このようにすることにより、例えば図２のＢに示される木構造のように、Octreeパタンの深さを部分的に制御することができる。つまり、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる。つまり、木構造化可能なデータ群の解像度を部分的に制御することができる。
【００２９】
また、換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においても、Octree符号化を適用することができ、符号化効率の低減を抑制することができる。つまり、データ群の解像度を部分的に制御する場合にも、そのデータ群の木構造化を実現することができ、符号化効率の低減を抑制することができる。
【００３０】
なお、以下においては、本技術をOctreeパタンデータに適用する場合を例に説明するが、本技術は、例えばKDtree、２分木構造、４分木構造等、任意の木構造を有するデータに適用することができる。また、以下においてはポイントクラウドデータ（を量子化したボクセルデータ）を例に説明するが、データの解像度を部分的に制御することができるものであれば、このデータの内容は任意である。例えば、このデータは、メッシュ（Mesh）等のような３次元構造に関する他の種類のデータであってもよいし、３次元構造以外に関するデータであってもよい。
【００３１】
＜符号化装置＞
図３は、本技術を適用した情報処理装置の一実施の形態である符号化装置の主な構成例を示すブロック図である。図３に示される符号化装置１００は、符号化対象として入力されたポイントクラウドのデータを、ボクセルを用いて符号化し、得られた符号化データ等を出力する。その際、符号化装置１００は、以下に説明するように本技術を適用した方法でこの符号化を行う。
【００３２】
図３に示されるように、符号化装置１００は、制御部１０１、前処理部１１１、バウンディングボックス設定部１１２、ボクセル設定部１１３、および符号化部１１４を有する。
【００３３】
制御部１０１は、符号化装置１００内の各処理部の制御に関する処理を行う。例えば、制御部１０１は、各処理部による処理の実行またはスキップ（省略）を制御する。例えば、制御部１０１は、所定の制御情報に基づいてそのような制御を行う。このようにすることにより、制御部１０１は、不要な処理の実行を抑制することができ、負荷の増大を抑制することができる。
【００３４】
制御部１０１は、どのような構成を有するようにしてもよいが、例えば、CPU（Central Processing Unit）、ROM（Read Only Memory）、RAM（Random Access Memory）等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、処理を行うようにしてもよい。
【００３５】
前処理部１１１は、制御部１０１により制御され、符号化装置１００に入力されるポイントクラウドデータ（符号化対象）に対して、前処理として所定の処理を施し、処理後のデータをバウンディングボックス設定部１１２に供給する。なお、符号化対象となるポイントクラウドは、動画像であってもよいし、静止画像であってもよい。
【００３６】
例えば、制御部１０１は、前処理の実行を許可または禁止する制御情報に従って、前処理の実行が許可されている（禁止されていない）場合に、前処理部１１１に前処理を実行させる。また、例えば、制御部１０１は、前処理の実行の許可または禁止の対象となる符号化対象の範囲を示す制御情報に従って、前処理の実行が許可されている（禁止されていない）符号化対象に対して、前処理部１１１に前処理を実行させる。さらに例えば、制御部１０１は、実行を許可または禁止する処理内容を指定する制御情報に従って、実行が許可されている（禁止されていない）処理を前処理部１１１に実行させる。このようにすることにより、不要な前処理の実行を抑制することができ、負荷の増大を抑制することができる。
【００３７】
なお、前処理の内容は任意である。例えば、前処理部１１１が、前処理として、ノイズを低減させる処理を施すようにしても良いし、解像度（点の数）を変更する処理を行うようにしても良い。また例えば、点群の密度を均等にしたり、所望の偏りを持たせたりするように、各点の配置を更新するようにしてもよい。さらに例えば、奥行き情報を有する画像情報等のようなポイントクラウドでないデータが符号化装置１００に入力されるようにし、前処理部１１１が、前処理として、その入力されたデータをポイントクラウドのデータに変換するようにしてもよい。
【００３８】
前処理部１１１は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、前処理を行うようにしてもよい。
【００３９】
バウンディングボックス設定部１１２は、制御部１０１により制御されて、符号化対象の位置情報を正規化するためのバウンディングボックスの設定に関する処理を行う。
【００４０】
例えば、制御部１０１は、バウンディングボックスの設定の許可または禁止する制御情報に従って、そのバウンディングボックスの設定が許可されている（禁止されていない）場合に、バウンディングボックス設定部１１２にそのバウンディングボックスを設定させる。また、例えば、制御部１０１は、バウンディングボックスの設定の許可または禁止の対象となる符号化対象の範囲を示す制御情報に従って、そのバウンディングボックスの設定が許可されている（禁止されていない）符号化対象に対して、バウンディングボックス設定部１１２にそのバウンディングボックスを設定させる。さらに例えば、制御部１０１は、バウンディングボックスの設定に用いられるパラメータの許可または禁止に関する制御情報に従って、バウンディングボックス設定部１１２に、使用が許可されている（禁止されていない）パラメータを用いてバウンディングボックスを設定させる。このようにすることにより、不要なバウンディングボックスの設定や不要なパラメータの使用を抑制することができ、負荷の増大を抑制することができる。
【００４１】
例えば、バウンディングボックス設定部１１２は、符号化対象の各オブジェクトに対するバウンディングボックスを設定する。例えば、図４のＡに示されるように、ポイントクラウドのデータによりオブジェクト１３１やオブジェクト１３２が表現されている場合、バウンディングボックス設定部１１２は、図４のＢに示されるように、そのオブジェクト１３１やオブジェクト１３２をそれぞれ包含するようにバウンディングボックス１４１やバウンディングボックス１４２を設定する。図３に戻り、バウンディングボックスが設定されると、バウンディングボックス設定部１１２は、そのバウンディングボックスに関する情報をボクセル設定部１１３に供給する。
【００４２】
なお、バウンディングボックス設定部１１２は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、バウンディングボックスの設定に関する処理を行うようにしてもよい。
【００４３】
ボクセル設定部１１３は、制御部１０１により制御されて、符号化対象の位置情報を量子化するためのボクセルの設定に関する処理を行う。
【００４４】
例えば、制御部１０１は、ボクセルの設定の許可または禁止する制御情報に従って、そのボクセルの設定が許可されている（禁止されていない）場合に、ボクセル設定部１１３にそのボクセルを設定させる。また、例えば、制御部１０１は、ボクセルの設定の許可または禁止の対象となる符号化対象の範囲を示す制御情報に従って、そのボクセルの設定が許可されている（禁止されていない）符号化対象に対して、ボクセル設定部１１３にそのボクセルを設定させる。さらに例えば、制御部１０１は、ボクセルの設定に用いられるパラメータの許可または禁止に関する制御情報に従って、ボクセル設定部１１３に、使用が許可されている（禁止されていない）パラメータを用いてボクセルを設定させる。このようにすることにより、不要なボクセルの設定や不要なパラメータの使用を抑制することができ、負荷の増大を抑制することができる。
【００４５】
例えば、ボクセル設定部１１３は、バウンディングボックス設定部１１２により設定されたバウンディングボックス内に、ボクセルを設定する。例えば、ボクセル設定部１１３は、図４のＣに示されるように、バウンディングボックス１４１を分割してボクセル１５１を設定する。つまり、ボクセル設定部１１３は、バウンディングボックス内のポイントクラウドデータをボクセルにより量子化（すなわちボクセル化）する。なお、バウンディングボックスが複数存在する場合、ボクセル設定部１１３は、各バウンディングボックスについてポイントクラウドデータをボクセル化する。つまり、図４のＢの例の場合、ボクセル設定部１１３は、バウンディングボックス１４２に対しても同様の処理を行う。図３に戻り、以上のようにしてボクセルが設定されると、ボクセル設定部１１３は、そのボクセル化されたポイントクラウドデータ（ボクセルデータとも称する）（位置情報の量子化のためのデータ構造に関する情報）や属性情報等を、符号化部１１４に供給する。
【００４６】
なお、ボクセル設定部１１３は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、ボクセルの設定に関する処理を行うようにしてもよい。
【００４７】
符号化部１１４は、制御部１０１により制御され、符号化に関する処理を行う。
【００４８】
例えば、制御部１０１は、符号化を許可または禁止する制御情報に従って、符号化が許可されている（禁止されていない）場合に、符号化部１１４にボクセルデータを符号化させる。また、例えば、制御部１０１は、符号化の許可または禁止の対象となる符号化対象の範囲を示す制御情報に従って、ボクセルデータの、符号化が許可されている（禁止されていない）符号化対象に対して、符号化部１１４に符号化を行わせる。このようにすることにより、不要な符号化を抑制することができ、負荷の増大を抑制することができる。
【００４９】
符号化部１１４は、例えば、ポイントクラウドデータを量子化したボクセルデータ（例えば図４のＣに示されるようなボクセル設定部１１３により生成されたボクセルデータ）を符号化し、符号化データ（ビットストリーム）を生成する。図４のＤは、符号化された信号列の様子の例を示している。
【００５０】
また、符号化部１１４は、適宜、例えば制御情報等の、ポイントクラウドデータ以外の関連情報も符号化し、ヘッダやパラメータセット等に格納する。例えば、符号化部１１４は、Octreeパタンの深さ（レベル数）を指定する情報をヘッダやパラメータセット等に格納する。
【００５１】
符号化部１１４は、上述した各種情報のビットストリームを互いに関連付ける。ここで、「関連付ける」という用語は、例えば、一方のデータを処理する際に他方のデータを利用し得る（リンクさせ得る）ようにすることを意味する。つまり、互いに関連付けられたデータは、１つのデータとしてまとめられてもよいし、それぞれ個別のデータとしてもよい。例えば、符号化データに関連付けられた制御情報は、その符号化データとは別の伝送路上で伝送されるようにしてもよい。また、例えば、符号化データに関連付けられた制御情報は、その符号化データとは別の記録媒体（または同一の記録媒体の別の記録エリア）に記録されるようにしてもよい。なお、この「関連付け」は、データ全体でなく、データの一部であってもよい。例えば、複数フレーム、１フレーム、またはフレーム内の一部分などの任意の単位で互いに関連付けられるようにしてもよい。
【００５２】
符号化部１１４は、このような符号化により得られた符号化データ（ビットストリーム）を符号化装置１００の外部に出力する。この符号化装置１００より出力されたデータ（符号化データや制御情報）は、例えば、図示せぬ後段の処理部により復号され、ポイントクラウドのデータが復元されるようにしてもよいし、図示せぬ通信部により送信され、所定の伝送路を介して復号装置等の他の装置に伝送されるようにしてもよいし、図示せぬ記録媒体に記録されるようにしてもよい。
【００５３】
なお、符号化部１１４は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、符号化に関する処理を行うようにしてもよい。
【００５４】
＜２．第１の実施の形態＞
＜終端識別ビットパタン＞
符号化部１１４は、ボクセル設定部１１３より供給されたボクセルデータをOctree符号化してOctreeパタンのデータ（Octreeパタンデータ）を生成する。また、符号化部１１４は、生成したOctreeパタンデータを可逆符号化し、ビットストリームを生成する。
【００５５】
符号化部１１４は、そのOctree符号化においてOctreeパタンの最下位レベル以外において一部のノードを終端させる（葉ノードとする）場合、本技術を適用し、『そのOctreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに、葉ノードが形成されることを示す深さ制御情報』を含むビットストリームを生成する。
【００５６】
この深さ制御情報は、任意であるが、例えば、『Octreeパタンの最下位レベルよりも上位のレベルの、その深さ制御情報に対応する特定のノードが葉ノードである』ことを示す所定のビット列であるようにしてもよい。
【００５７】
このようにすることにより、復号側において、その「所定のビット列」を検出することにより、容易に「特定のノードが葉ノードである」ことを把握することができる。
【００５８】
例えば、一般的なOctreeパタンにおいては、図５のＡに示されるように、ポイントが存在する領域がノードとして構成され、（最下位レベル以外の）各ノードに対して、その領域を８分割した領域の内のいずれの領域にポイントが存在するかを示す８ビットのビット列（Child mask）が設定される。このビット列は、分割後の８領域の内、値「１」のビットに対応する領域にポイントが存在することを示す（値「０」のビットに対応する領域にポイントが存在しないことを示す）。
【００５９】
一般的なOctreeパタンの場合、図５のＡに示されるように、分木しなくても、最下位レベルまで子孫ノードが形成される。例えば、最下位レベルの１つ上のレベルの右のノードは、子ノードを１つしか持たない（分木はしない）が、ビットパタン「01000000」のビット列が設定され、最下位レベルにおけるポイントの位置が示されている。中央のノードも同様であり、分木はしないがビットパタン「00000001」が設定され、最下位レベルにおけるポイントの位置が示されている。したがって、この場合、全てのポイントの位置（解像度）は、最下位レベルで示される。
【００６０】
これに対して、符号化部１１４は、上述の「深さ制御情報」として、図５のＢに示されるように、最下位レベルより上位のレベルの、終端させるノード（子孫ノードを形成しないノード）に対して、そのノードが葉ノードである（終端である）ことを示すビットパタンのビット列を設定する。そして、符号化部１１４は、そのノードを葉ノードとし、子孫ノードの形成を省略する。そして、符号化部１１４は、その「ビット列（深さ制御情報）」が設定されたノードを含むOctreeパタンデータを可逆符号化し、その「ビット列（深さ制御情報）」を含むビットストリームを生成する。
【００６１】
つまり、この場合の「深さ制御情報」である「所定のビット列」は、Octreeパタンデータにおいて、そのOctreeパタンの最下位レベルよりも上位のレベルのノードに設定されており、その「所定のビット列」が設定されたノードが葉ノードであることを示すビットパタンを有する。そして、符号化部１１４は、そのOctreeパタンの最下位レベルよりも上位のレベルの葉ノードに「所定のビット列」が設定されたOctreeパタンデータを符号化してビットストリームを生成する。
【００６２】
つまり、「ビット列（深さ制御情報）」の位置によって、Octreeパタンの最下位レベルよりも上位のレベルの葉ノードの位置が示される。したがって、復号側においては、ビットストリームを復号してOctreeパタンを再構築する際に、その「ビット列（深さ制御情報）」の位置を確認することにより、Octreeパタンの最下位レベルよりも上位のレベルの葉ノードを検出することができる。つまり、最下位レベルよりも上位のレベルに葉ノードを含むOctreeパタンを正しく復号することができる。
【００６３】
すなわち、このような「ビット列（深さ制御情報）」により、Octreeパタンにおいて、ポイントの解像度の部分的な制御を表現することが可能になる。つまり、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。
【００６４】
換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においても、Octree符号化を適用することができるので（データ群の解像度を部分的に制御する場合にも、そのデータ群の木構造化を実現することができるので）、符号化効率の低減を抑制することができる。
【００６５】
なお、この「所定のビット列」のビットパタン（終端識別ビットパタンとも称する）は、そのOctreeパタンの葉ノードでないノードに設定されるビット列には用いられないビットパタンであるようにしてもよい。例えば、図５のＢの例の場合、最下位レベルの１つ上位のレベルの右のノード（葉ノード）にビットパタン「00000000」（終端識別ビットパタン）のビット列が割り当てられている。ビットパタン「00000000」は、分割後の８領域のいずれにもポイントが存在しないことを示すことになるが、一般的なOctreeパタンにおいては、最下位レベルより上位のレベルにおいて、そのようなノードは存在しない。
【００６６】
このようにすることにより、他のノードに設定されるビット列と同一の仕様のビット列により、最下位レベル以外のレベルの葉ノードを表現することができる。つまり、その葉ノードに対しても他のノードと同一の仕様のビット列を設定することができるので、一般的なOctree符号化からの仕様変更量を低減させることができ、本技術をより容易に実現することができる。
【００６７】
ただし、この終端識別ビットパタンは、「葉ノード」であることを示すことができるものであれば任意であり、上述の例（「00000000」）に限定されない。例えば、葉ノード以外のノードに設定される他のビット列とは、ビット数が異なるようにしてもよい。
【００６８】
なお、終端識別ビットパタンのビット列は、葉ノードとの対応関係が明らかにされているのであれば、対応するノードの位置以外に格納されるようにしてもよい。例えば、終端識別ビットパタンのビット列を、まとめてヘッダやパラメータセット等に格納するようにしてもよい。また、このビット列を、Octreeパタンデータのビットストリームと異なるビットストリームに含めるようにしてもよい。これらの場合、どのビット列がどの葉ノードに対応しているかの情報も必要になる。
【００６９】
＜符号化部＞
図６は、符号化部１１４（図３）の主な構成例を示すブロック図である。図６に示されるように、符号化部１１４は、Octree符号化部２２１、２値化部２２２、および可逆符号化部２２３を有する。
【００７０】
Octree符号化部２２１は、Octree符号化に関する処理を行う。例えば、Octree符号化部２２１は、ボクセル設定部１１３より供給されるボクセルデータのジオメトリデータ（位置情報）をOctree符号化し、Octreeパタンデータを生成する。その際、Octree符号化部２２１は、最下位レベルと異なるレベルの所望のノードを葉ノードとする場合、その所望のノードに対して、上述の「終端識別ビットパタンのビット列」（例えば、ビットパタン「00000000」のビット列）を設定する。
【００７１】
図６に示されるように、Octree符号化部２２１は、Octree深度制御部２３１およびOctree構成部２３２を有する。
【００７２】
Octree深度制御部２３１は、Octreeパタンの深度に関する制御を行う。Octree構成部２３２は、Octreeパタンの構成に関する処理を行う。例えば、Octree構成部２３２は、ジオメトリデータに基づいてOctreeパタンを構築し、そのジオメトリデータに対応するOctreeパタンデータを生成する。Octree深度制御部２３１は、そのOctreeパタンの構築を制御し、Octreeパタンの深さを制御する。
【００７３】
例えば、Octree深度制御部２３１は、Octree構成部２３２がジオメトリデータをOctree符号化してOctreeパタンを生成する際に、そのOctree構成部２３２を制御し、Octreeパタンの最下位レベルよりも上位のレベルの所望のノードを葉ノードとするようにすることができる。つまり、一部のノードがOctreeパタンの最下位レベルよりも上位のレベルにおいて終端する（子孫ノードを形成しない）ようにすることができる。その場合、Octree深度制御部２３１は、Octree構成部２３２を制御し、その所望のノードに対して上述の「終端識別ビットパタンのビット列」を設定するようにしてもよい。
【００７４】
Octree符号化部２２１（Octree構成部２３２）は、その「終端識別ビットパタンのビット列」を含むOctreeパタンデータを２値化部２２２に供給する。
【００７５】
このようにすることにより、符号化部１１４は、Octreeパタンを形成しながら、葉ノードとされるノードに対して「終端識別ビットパタンのビット列」を設定することができる。
【００７６】
なお、Octree符号化部２２１（Octree深度制御部２３１およびOctree構成部２３２のそれぞれ）は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、Octree符号化に関する処理を行うようにしてもよい。
【００７７】
２値化部２２２は、２値化に関する処理を行う。例えば、２値化部２２２は、Octree符号化部２２１から供給されるOctreeパタンデータを２値化して２値データを生成する。２値化部２２２は、生成した２値データを可逆符号化部２２３に供給する。
【００７８】
なお、２値化部２２２は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、２値化に関する処理を行うようにしてもよい。
【００７９】
可逆符号化部２２３は、可逆符号化に関する処理を行う。例えば、可逆符号化部２２３は、２値化部２２２から供給される２値データを可逆符号化し、ビットストリーム（つまり、Octreeパタンデータの符号化データ）を生成する。この可逆符号化の方法は任意である。例えば、CABAC（Context-based Adaptive Binary Arithmetic Code）であってもよい。
【００８０】
また、例えば、可逆符号化部２２３は、OctreeパタンデータのOctreeパタンの深さ（レベル数）を指定する情報を、ヘッダやパラメータセット等に格納し、ビットストリームに含める。
【００８１】
可逆符号化部２２３は、生成したビットストリームを符号化部１１４の外部（すなわち符号化装置１００の外部）に出力する。
【００８２】
なお、可逆符号化部２２３は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、可逆符号化に関する処理を行うようにしてもよい。
【００８３】
上述のように、Octreeパタンの最下位レベルよりも上位のレベルにおいてノードを終端させる場合、Octree符号化部２２１が生成するOctreeパタンデータには、終端識別ビットパタンのビット列が含まれる。つまり、可逆符号化部２２３は、その終端識別ビットパタンのビット列（深さ制御情報）を含むビットストリームを生成する。
【００８４】
したがって、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【００８５】
なお、Octreeパタンデータの符号化方法は任意である。例えば、CAVLC（Context-based Adaptive Variable Length Code）を用いてOctreeパタンデータを符号化するようにしてもよい。その場合、２値化部２２２および可逆符号化部２２３の代わりに、CAVLCを行う可逆符号化部を設けるようにしてもよい。
【００８６】
＜符号化処理の流れ＞
以上のような構成の符号化装置１００により実行される符号化処理の流れの例を図７のフローチャートを参照して説明する。
【００８７】
符号化処理が開始されると、前処理部１１１は、ステップＳ１０１において、入力されたデータに対して前処理を行う。
【００８８】
ステップＳ１０２において、バウンディングボックス設定部１１２は、前処理されたデータに対してバウンディングボックスを設定する。
【００８９】
ステップＳ１０３において、ボクセル設定部１１３は、ステップＳ１０２において設定されたバウンディングボックスにボクセルを設定する。
【００９０】
ステップＳ１０４において、符号化部１１４は、ステップＳ１０３の処理により生成されたボクセルデータのジオメトリデータを符号化する。
【００９１】
ステップＳ１０５において、符号化部１１４は、その符号化により得られたビットストリームを符号化装置１００の外部に出力する。このビットストリームは例えば復号側（復号装置等）に伝送されたり、記録媒体に記録されたりする。
【００９２】
ステップＳ１０５の処理が終了すると、符号化処理が終了する。例えば、符号化対象が動画像である場合、この一連の処理をフレーム毎に行う。
【００９３】
＜ジオメトリデータ符号化処理の流れ＞
次に、図７のステップＳ１０４において実行されるジオメトリデータ符号化処理の流れの例を、図８のフローチャートを参照して説明する。
【００９４】
ジオメトリデータ符号化処理が開始されると、Octree深度制御部２３１は、ステップＳ１２１において、Octreeパタンの処理対象ノードを初期化する。
【００９５】
ステップＳ１２２において、Octree深度制御部２３１は、処理対象ノードのレベルが最下位レベルであるか否かを判定する。処理対象ノードのレベルが最下位レベルでないと判定された場合、処理はステップＳ１２３に進む。
【００９６】
ステップＳ１２３において、Octree深度制御部２３１は、処理対象ノードを終端とするか否かを判定する。処理対象ノードを終端とする、すなわち、処理対象ノードを葉ノードとすると判定された場合、処理はステップＳ１２４に進む。
【００９７】
ステップＳ１２４において、Octree構成部２３２は、終端とする処理対象ノードに対して、終端識別ビットパタン（例えば「00000000」）を生成し、設定する。また、Octree構成部２３２は、その処理対象ノードの子孫ノードを処理対象候補から除外する。つまり、処理対象ノードを葉ノードとし、それに属する子ノードを形成しないようにする。ステップＳ１２４の処理が終了すると、処理はステップＳ１２６に進む。
【００９８】
また、ステップＳ１２３において、処理対象ノードを終端としないと判定された場合、処理はステップＳ１２５に進む。
【００９９】
ステップＳ１２５において、Octree構成部２３２は、終端としない処理対象ノードに対して、ジオメトリデータに基づいて「子ノードのビットパタン」、すなわち、処理対象ノードに対応する領域を８分割（２×２×２分割）した領域のいずれにポイントが存在するかを示すビットパタンのビット列を生成し、そのビット列を処理対象ノードに設定する。ステップＳ１２５の処理が終了すると処理はステップＳ１２６に進む。
【０１００】
また、ステップＳ１２２において、処理対象ノードのレベルが最下位レベルである、すなわち、ジオメトリデータ（のボクセル）と同じ解像度のレベルであると判定された場合、ステップＳ１２３乃至ステップＳ１２５の処理は省略され、処理はステップＳ１２６に進む。つまり、最下位レベルのノードに対しては、ビット列は設定されない。
【０１０１】
ステップＳ１２６において、Octree深度制御部２３１は、全ノードを処理したか否かを判定する。ジオメトリデータに対応するOctreeパタンが構築されておらず、未処理のノードが存在すると判定された場合、処理はステップＳ１２７に進む。
【０１０２】
ステップＳ１２７において、Octree深度制御部２３１は、処理対象ノードを前順の次のノードに設定する。処理対象ノードが更新されると処理はステップＳ１２２に戻る。つまり、ステップＳ１２２乃至ステップＳ１２７の各処理が、ジオメトリデータに対応するOctreeパタンの各ノードに対して行われる。
【０１０３】
そして、ステップＳ１２６において、ジオメトリデータに対応するOctreeパタンが構築され、全ノードを処理したと判定された場合、処理はステップＳ１２８に進む。
【０１０４】
ステップＳ１２８において、２値化部２２２は、上述の処理により生成されたジオメトリデータに対応するOctreeパタンデータを２値化する。
【０１０５】
ステップＳ１２９において、可逆符号化部２２３は、ステップＳ１２８の処理により得られた２値データを可逆符号化し、ビットストリームを生成する。ステップＳ１２４の処理により、Octreeパタンデータには、終端識別ビットパタンのビット列が含まれているので、可逆符号化部２２３は、終端識別ビットパタンのビット列を含むビットストリームを生成する。
【０１０６】
ステップＳ１２９の処理が終了するとジオメトリデータ符号化処理が終了し、処理は図７に戻る。
【０１０７】
以上のように各処理を実行することにより、符号化装置１００は、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０１０８】
なお、以上においてはOctreeパタンの走査順として、前順を例に説明したが、この走査順は任意であり、前順に限定されない。例えば、先行順、前置順、行きがけ順、間順、中間順、通りがけ順、後順、後行順、後置順、帰りがけ順、またはレベル順等であってもよい。
【０１０９】
＜符号化部の他の例＞
なお、Octreeパタンを生成後に編集し、最下位レベルよりも上位のレベルの所望のノードを葉ノード化するようにしてもよい。
【０１１０】
図９は、その場合の符号化部１１４（図３）の主な構成例を示すブロック図である。この場合、図９に示されるように、符号化部１１４は、図６の場合と同様に、Octree符号化部２２１、２値化部２２２、および可逆符号化部２２３を有する。
【０１１１】
ただし、Octree符号化部２２１は、Octree構成部２４１およびOctree深度制御部２４２を有する。Octree構成部２４１は、Octreeパタンの構成に関する処理を行う。例えば、Octree構成部２４１は、一般的なOctree符号化を行い、ジオメトリデータに基づいてOctreeパタンを構築し、ジオメトリデータに対応するOctreeパタンデータを生成する。
【０１１２】
Octree深度制御部２４２は、Octreeパタンの深度に関する制御を行う。例えば、Octree深度制御部２４２は、Octree構成部２４１により構築されたOctreeパタンを編集し、最下位レベルよりも上位のレベルの所望のノードを葉ノード化する。つまり、Octree深度制御部２４２は、Octreeパタンの最下位レベルよりも上位のレベルの所望のノードに属する子孫ノードを削除し、その所望のノードを葉ノード化する。さらに、Octree深度制御部２４２は、その所望のノードに対して、上述の「終端識別ビットパタンのビット列」（例えば、ビットパタン「00000000」のビット列）を設定する。Octree符号化部２２１（Octree深度制御部２４２）は、その「終端識別ビットパタンのビット列」を含むOctreeパタンデータを２値化部２２２に供給する。
【０１１３】
なお、Octree符号化部２２１（Octree構成部２４１およびOctree深度制御部２４２のそれぞれ）は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、Octree符号化に関する処理を行うようにしてもよい。
【０１１４】
２値化部２２２は、そのOctreeパタンデータを２値化して２値データを生成し、可逆符号化部２２３は、その２値データを可逆符号化し、ビットストリームを生成する。
【０１１５】
このようにすることにより、符号化部１１４は、Octreeパタンを形成しながら、葉ノードとされるノードに対して「終端識別ビットパタンのビット列」を設定することができる。
【０１１６】
この場合も、Octreeパタンの最下位レベルよりも上位のレベルにおいてノードを終端させる場合、Octree符号化部２２１が生成するOctreeパタンデータには、終端識別ビットパタンのビット列が含まれる。つまり、可逆符号化部２２３は、この場合も、その終端識別ビットパタンのビット列（深さ制御情報）を含むビットストリームを生成する。
【０１１７】
したがって、符号化部１１４は、この場合も、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０１１８】
＜符号化処理の流れ＞
この場合も、符号化装置１００により実行される符号化処理の流れは、図７のフローチャートを参照して説明した場合と同様であるのでその説明は省略する。
【０１１９】
＜ジオメトリデータ符号化処理の流れ＞
次に、この場合の、図７のステップＳ１０４において実行されるジオメトリデータ符号化処理の流れの例を、図１０のフローチャートを参照して説明する。
【０１２０】
この場合、ジオメトリデータ符号化処理が開始されると、Octree構成部２４１は、ステップＳ１４１において、ジオメトリデータからOctreeパタンを構築し、そのOctreeパタンデータを生成する。
【０１２１】
ステップＳ１４２において、Octree深度制御部２４２は、Octreeパタンの処理対象ノードを初期化する。
【０１２２】
ステップＳ１４３において、Octree深度制御部２４２は、処理対象ノードのレベルが最下位レベルであるか否かを判定する。処理対象ノードのレベルが最下位レベルでないと判定された場合、処理はステップＳ１４４に進む。
【０１２３】
ステップＳ１４４において、Octree深度制御部２４２は、処理対象ノードを終端とするか否かを判定する。処理対象ノードを終端とする、すなわち、処理対象ノードを葉ノードとすると判定された場合、処理はステップＳ１４５に進む。
【０１２４】
ステップＳ１４５において、Octree深度制御部２４２は、終端とする処理対象ノードに設定されたビット列を、終端識別ビットパタン（例えば「00000000」）に置き換える。また、Octree深度制御部２４２は、Octreeパタンに存在した、その処理対象ノードの子孫ノードを削除する。つまり、処理対象ノードを葉ノードとし、それに属する子孫ノードを削除する。ステップＳ１４５の処理が終了すると、処理はステップＳ１４６に進む。
【０１２５】
また、ステップＳ１４４において、処理対象ノードを終端としないと判定された場合、ステップＳ１４５の処理が省略され、処理はステップＳ１４６に進む。つまり、この場合処理対象ノードを編集しない。
【０１２６】
また、ステップＳ１４３において、処理対象ノードのレベルが最下位レベルである、すなわち、ジオメトリデータ（のボクセル）と同じ解像度のレベルであると判定された場合、ステップＳ１４４およびステップＳ１４５の処理は省略され、処理はステップＳ１４６に進む。つまり、最下位レベルのノードに対しては、ビット列は設定されないので編集も行われない。
【０１２７】
ステップＳ１４６において、Octree深度制御部２４２は、ステップＳ１４１において生成されたOctreeパタンの全ノードを処理したか否かを判定する。未処理のノードが存在すると判定された場合、処理はステップＳ１４７に進む。
【０１２８】
ステップＳ１４７において、Octree深度制御部２４２は、処理対象ノードを前順の次のノードに設定する。処理対象ノードが更新されると処理はステップＳ１４３に戻る。つまり、ステップＳ１４３乃至ステップＳ１４７の各処理が、ジオメトリデータに対応するOctreeパタンの各ノードに対して行われる。
【０１２９】
そして、ステップＳ１４６において、全ノードを処理したと判定された場合、処理はステップＳ１４８に進む。
【０１３０】
ステップＳ１４８において、２値化部２２２は、上述の処理により生成されたジオメトリデータに対応するOctreeパタンデータを２値化する。
【０１３１】
ステップＳ１４９において、可逆符号化部２２３は、ステップＳ１４８の処理により得られた２値データを可逆符号化し、ビットストリームを生成する。ステップＳ１４５の処理により、Octreeパタンデータには、終端識別ビットパタンのビット列が含まれているので、可逆符号化部２２３は、終端識別ビットパタンのビット列を含むビットストリームを生成する。
【０１３２】
ステップＳ１４９の処理が終了するとジオメトリデータ符号化処理が終了し、処理は図７に戻る。
【０１３３】
以上のように各処理を実行することにより、符号化装置１００は、この場合も、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０１３４】
なお、以上においてはOctreeパタンの走査順として、前順を例に説明したが、この走査順は任意であり、前順に限定されない。例えば、先行順、前置順、行きがけ順、間順、中間順、通りがけ順、後順、後行順、後置順、帰りがけ順、またはレベル順等であってもよい。
【０１３５】
＜復号装置＞
符号化装置１００が生成したビットストリームを復号する復号装置は、そのビットストリームを復号し、Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報に基づいて、その最下位レベルと異なるレベルの葉ノードを含むOctreeパタンを構築する。したがって、この復号装置は、符号化装置１００が生成したビットストリームを正しく復号することができる。
【０１３６】
図１１は、本技術を適用した情報処理装置の一実施の形態である復号装置の主な構成例を示すブロック図である。図１１に示される復号装置２５０は、図３の符号化装置１００に対応する復号装置であり、例えばこの符号化装置１００により生成されたポイントクラウドの符号化データを復号し、ポイントクラウドのデータを復元する。
【０１３７】
図１１に示されるように、復号装置２５０は、復号部２６１、およびポイントクラウド化処理部２６２を有する。
【０１３８】
復号部２６１は、ビットストリームの復号に関する処理を行う。例えば、復号部２６１は、ビットストリームを符号化部１１４（図３）の符号化方法に対応する復号方法で復号し、Octreeパタンを再構築する。上述したように、符号化装置１００により生成されたビットストリームには、「Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報」が含まれる。復号部２６１は、その「深さ制御情報」に基づいて、最下位レベルと異なるレベルの葉ノードを含むOctreeパタンを構築する。
【０１３９】
したがって、復号部２６１は、符号化部１１４により生成されたビットストリームを正しく復号することができる。したがって、復号装置２５０は、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０１４０】
上述したように、この深さ制御情報は、任意であるが、例えば、『Octreeパタンの最下位レベルよりも上位のレベルの、その深さ制御情報に対応する特定のノードが葉ノードである』ことを示す所定のビット列であるようにしてもよい。
【０１４１】
このようにすることにより、復号部２６１は、その「所定のビット列」を検出することにより、容易に「特定のノードが葉ノードである」ことを把握することができる。
【０１４２】
また、上述したように、この「所定のビット列」は、Octreeパタンの最下位レベルよりも上位のレベルの葉ノードに設定されており、その「所定のビット列」が設定されたノードが葉ノードであることを示すビットパタン（終端識別ビットパタン）を有する。
【０１４３】
つまり、「ビット列（深さ制御情報）」の位置によって、Octreeパタンの最下位レベルよりも上位のレベルの葉ノードの位置が示される。したがって、復号部２６１は、ビットストリームを復号してOctreeパタンを再構築する際に、その「ビット列（深さ制御情報）」の位置を確認することにより、Octreeパタンの最下位レベルよりも上位のレベルの葉ノードを検出することができる。つまり、最下位レベルよりも上位のレベルに葉ノードを含むOctreeパタンを正しく復号することができる。
【０１４４】
なお、上述したように、この「所定のビット列」のビットパタン（終端識別ビットパタン）は、そのOctreeパタンの葉ノードでないノードに設定されるビット列には用いられないビットパタンであるようにしてもよい。例えば、図５のＢの例の場合、最下位レベルの１つ上位のレベルの右のノード（葉ノード）にビットパタン「00000000」（終端識別ビットパタン）のビット列が割り当てられている。
【０１４５】
そして、復号部２６１は、そのOctreeパタン（Octreeパタンデータ）からジオメトリデータ（ボクセルデータ）を再構成する。復号部２６１は、再構成したジオメトリデータ（ボクセルデータ）をポイントクラウド化処理部２６２に供給する。
【０１４６】
なお、復号部２６１は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、復号に関する処理を行うようにしてもよい。
【０１４７】
ポイントクラウド化処理部２６２は、ポイントクラウドデータの復元に関する処理を行う。例えば、ポイントクラウド化処理部２６２は、復号部２６１から供給されたジオメトリデータ（ボクセルデータ）をポイントクラウドデータに変換する（復号ポイントクラウドデータを生成する）。なお、ポイントクラウド化処理部２６２が、その復号ポイントクラウドデータをさらにMeshデータに変換するようにしてもよい。
【０１４８】
ポイントクラウド化処理部２６２は、生成した復号ポイントクラウドデータ（またはMeshデータ）を復号装置２５０の外部に出力する。この出力された復号ポイントクラウドデータ（またはMeshデータ）は、例えば、図示せぬ後段の処理部により画像処理され、画像情報としてモニタ等に表示されるようにしてもよいし、図示せぬ通信部により送信され、所定の伝送路を介して他の装置に伝送されるようにしてもよいし、図示せぬ記録媒体に記録されるようにしてもよい。
【０１４９】
なお、ポイントクラウド化処理部２６２は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、ポイントクラウドデータの復元に関する処理を行うようにしてもよい。
【０１５０】
＜復号部＞
図１２は、復号部２６１の主な構成例を示すブロック図である。図１２に示されるように、復号部２６１は、可逆復号部２７１、終端検出部２７２、多値化部２７３、およびジオメトリ再構成部２７４を有する。
【０１５１】
可逆復号部２７１は、可逆復号に関する処理を行う。例えば、可逆復号部２７１は、符号化装置１００により生成されたビットストリームを、可逆符号化部２２３に対応する方法で可逆復号し、２値データを得る。この可逆復号方法は、可逆符号化部２２３の可逆符号化方法に対応するものであればどのような方法であってもよい。例えば、CABACであってもよい。
【０１５２】
上述したように、このビットストリームには、例えば、Octreeパタンの各ノードのビット列や、最下位レベルより上位のレベルの葉ノードに設定された「深さ制御情報（終端識別ビットパタンのビット列）」等が含まれる。したがって、可逆復号部２７１は、ビットストリームを復号してこれらの情報も抽出し、２値データとして多値化部２７３に供給する。また、このビットストリームに含まれるヘッダやパラメータセットにおいて、「Octreeパタンの深さを指定する情報」が含まれている。可逆復号部２７１は、ビットストリームを復号してこの情報も抽出し、２値データとして多値化部２７３に供給する。
【０１５３】
なお、可逆復号部２７１は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、可逆復号に関する処理を行うようにしてもよい。
【０１５４】
終端検出部２７２は、ノードの終端の検出に関する処理を行う。多値化部２７３は、多値化に関する処理を行う。例えば、多値化部２７３は、可逆復号部２７１から供給される２値データを多値化し、Octreeパタンを再構築して、Octreeパタンデータを生成する。その際、終端検出部２７２は、例えば、多値化部２７３において２値データが多値化されて得られるOctreeパタンに含まれる終端識別ビットパタンのビット列を検出する。また、終端検出部２７２は、その検出結果に応じて多値化部２７３を制御し、Octreeパタンの再構築を制御する。
【０１５５】
例えば、終端検出部２７２は、終端識別ビットパタンのビット列を検出すると、多値化部２７３を制御し、Octreeパタンの再構築において、そのノードを終端（葉ノード）とさせ、そのノードに属する子孫ノードを構築させないようにする。このようにすることにより、多値化部２７３は、「Octreeパタンの深さを指定する情報」により指定されるOctreeパタンの最下位レベルよりも上位のレベルに葉ノードを形成するように、Octreeパタンを再構築することができる。
【０１５６】
多値化部２７３は、このようにして得られたOctreeパタンデータを、ジオメトリ再構成部２７４に供給する。
【０１５７】
なお、終端検出部２７２は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、終端の検出に関する処理を行うようにしてもよい。
【０１５８】
また、多値化部２７３は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、多値化に関する処理を行うようにしてもよい。
【０１５９】
ジオメトリ再構成部２７４は、ジオメトリデータの再構成に関する処理を行う。例えば、ジオメトリ再構成部２７４は、多値化部２７３から供給されるOctreeパタンデータを用いてジオメトリデータを再構成する。ジオメトリ再構成部２７４は、得られたジオメトリデータをポイントクラウド化処理部２６２（図１１）に供給する。
【０１６０】
なお、ジオメトリ再構成部２７４は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、ジオメトリデータの再構成に関する処理を行うようにしてもよい。
【０１６１】
以上のように、可逆復号部２７１乃至多値化部２７３は、ビットストリームを復号し、Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報に基づいて、その最下位レベルと異なるレベルの葉ノードを含むOctreeパタンを構築する。
【０１６２】
したがって、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０１６３】
なお、ビットストリームの復号方法は、その符号化方法に対応するものであれば任意であり、上述の例に限定されない。例えば、CAVLCを用いてビットストリームを復号するようにしてもよい。つまり、この場合、ビットストリームは、CAVLCを用いて符号化されている。その場合、可逆復号部２７１および多値化部２７３の代わりに、CAVLCを行う可逆復号部を設けるようにしてもよい。
【０１６４】
＜復号処理の流れ＞
以上のような構成の復号装置２５０により実行される復号処理の流れの例を図１３のフローチャートを参照して説明する。
【０１６５】
復号処理が開始されると、復号部２６１は、ステップＳ１６１において、供給されたビットストリームを復号して、Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されるOctreeパタンを再構築し、そのOctreeパタンデータに対応するジオメトリデータを再構成する。
【０１６６】
ステップＳ１６２において、ポイントクラウド化処理部２６２は、ステップＳ１６１において得られたジオメトリデータからポイントクラウドデータを復元する。
【０１６７】
ステップＳ１６３において、ポイントクラウド化処理部２６２は、ステップＳ１６２において復元したポイントクラウドデータ（復号ポイントクラウドデータ）を復号装置２５０の外部に出力する。
【０１６８】
ステップＳ１６３の処理が終了すると、復号処理が終了する。
【０１６９】
＜ビットストリーム復号処理の流れ＞
次に、図１３のステップＳ１６１において実行されるビットストリーム復号処理の流れの例を、図１４のフローチャートを参照して説明する。
【０１７０】
ビットストリーム復号処理が開始されると、可逆復号部２７１は、ステップＳ１８１において、ビットストリームを可逆復号し、２値データを生成する。
【０１７１】
ステップＳ１８２において、多値化部２７３は、ステップＳ１８１において得られた２値データを読み込む。
【０１７２】
ステップＳ１８３において、終端検出部２７２は、読み込んだ２値データを多値化部２７３に復号させ、得られたOctreeパタンデータの中に、終端識別ビットパタンのビット列が含まれるか否かを判定する。Octreeパタンデータから終端識別ビットパタンを検出し、終端識別ビットパタンのビット列が含まれると判定された場合、処理はステップＳ１８４に進む。
【０１７３】
ステップＳ１８４において、多値化部２７３は、終端検出部２７２の制御に従って、２値データを多値化し、その終端識別ビットパタンを検出した検出位置（ノード）を終端（葉ノード）とするように、Octreeパタンを再構築する。つまり、深さ制御情報（終端識別ビットパタンのビット列）を、再構築するOctreeパタンに反映させる。
【０１７４】
ステップＳ１８４の処理が終了すると、処理はステップＳ１８６に進む。また、ステップＳ１８３において、終端識別ビットパタンを検出していない（Octreeパタンデータに終端識別ビットパタンのビット列が含まれない）と判定された場合、処理はステップＳ１８５に進む。
【０１７５】
ステップＳ１８５において、多値化部２７３は、２値データを多値化し、一般的なOctreeパタンの場合と同様に、Octreeパタンを再構築する。ステップＳ１８５の処理が終了すると、処理はステップＳ１８６に進む。
【０１７６】
ステップＳ１８６において、多値化部２７３は、２値データを全て処理したか否かを判定する。未処理の２値データが存在する場合、その未処理の２値データを新たな処理対象として、処理をステップＳ１８２に戻す。つまり、全ての２値データに対して、ステップＳ１８２乃至ステップＳ１８６の処理が実行される。そして、ステップＳ１８６において２値データを全て処理したと判定された場合、処理はステップＳ１８７に進む。
【０１７７】
ステップＳ１８７において、ジオメトリ再構成部２７４は、以上の処理により得られたOctreeパタンデータを用いてジオメトリデータを再構成する。
【０１７８】
ステップＳ１８７の処理が終了するとビットストリーム復号処理が終了し、処理は図１３に戻る。
【０１７９】
以上のように各処理を実行することにより、復号装置２５０は、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０１８０】
＜３．第２の実施の形態＞
＜end_of_node_one_bit＞
なお、「深さ制御情報」は、任意の情報であるが、例えば、『ビットストリームにおいて、Octreeパタンの最下位レベルよりも上位のレベルの深さ制御情報に対応する特定のノードが葉ノードであるかを示す所定のフラグ情報』であるようにしてもよい。
【０１８１】
このようにすることにより、復号側において、ビットストリームに含まれる「所定のフラグ情報」に基づいて、容易に「特定のノードが葉ノードである」ことを把握することができる。
【０１８２】
Octreeパタンは、例えば図１５のＡに示されるように、各ノードの情報が所定の走査順（例えば前順）に並べられて順次符号化される。したがって、ビットストリームにおいては、例えば図１５のＢに示されるように、各ノードのビットストリームがその走査順に並ぶ。例えば、図１５のＢに示されるビットストリームは、図１５のＡのOctreeパタンの、斜線模様の範囲に含まれるノード、白地の範囲に含まれるノード、グレー地の範囲に含まれるノードの順に並べられている。
【０１８３】
ここで、図１５のＡのOctreeパタンのグレー地の範囲に含まれるノードが、最下位レベルよりも上位のレベルであるが終端とされる（葉ノードである）とする。この場合、最下位レベルのノードの場合と同様に、そのノードにビット列を設定せず、代わりに、ビットストリームの、そのノードに対応する位置に、終端を示す「深さ制御情報（所定のフラグ情報）」を設定するようにしてもよい。
【０１８４】
つまり、符号化部１１４が、ビットストリームの、Octreeパタンの最下位レベルよりも上位のレベルの葉ノードに対応する位置に、その位置に対応するノードが葉ノードであるかを示す「所定のフラグ情報」を挿入するようにしてもよい。
【０１８５】
この「所定のフラグ情報」の位置によって、Octreeパタンの最下位レベルよりも上位のレベルの葉ノードの位置が示される。したがって、復号側においては、ビットストリームに含まれる「フラグ情報（深さ制御情報）」の位置を確認することにより、Octreeパタンの最下位レベルよりも上位のレベルの葉ノードを検出することができる。つまり、最下位レベルよりも上位のレベルに葉ノードを含むOctreeパタンを正しく復号することができる。
【０１８６】
すなわち、このような「フラグ情報（深さ制御情報）」により、Octreeパタンにおいて、ポイントの解像度の部分的な制御を表現することが可能になる。つまり、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。
【０１８７】
換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においても、Octree符号化を適用することができるので（データ群の解像度を部分的に制御する場合にも、そのデータ群の木構造化を実現することができるので）、符号化効率の低減を抑制することができる。
【０１８８】
例えば、図１５のＢの例のビットストリームの場合、「end_of_node_one_bit」というシンタックス（フラグ情報）が設定され、ビットストリームの、葉ノードであるグレー地の範囲に含まれるノードに対応する位置に、その「end_of_node_one_bit」が挿入されている。したがって、復号側においては、この「end_of_node_one_bit」を検出することにより、その位置に対応するノードが葉ノードであることを容易に検出することができる。
【０１８９】
なお、この「フラグ情報」の名称（シンタックス）は任意であり、「end_of_node_one_bit」以外であってもよい。また、この「フラグ情報（end_of_node_one_bit）」の値は任意である。例えば、「１」であってもよいし、「０」であってもよい。また、この「フラグ情報」が複数ビット（bit）により構成されるようにしてもよい。さらに、この「フラグ情報」が葉ノードであること以外を示す情報が含まれるようにしてもよい。また、この「フラグ情報が」全てのノードに設定され、その値によって葉ノードであるか否かを識別することができるようにしてもよい。
【０１９０】
また、この「フラグ情報」は、葉ノードとの対応関係が明らかにされているのであれば、ビットストリームの、対応するノードの位置以外に挿入されるようにしてもよい。例えば、この「フラグ情報」を、まとめてヘッダやパラメータセット等に格納するようにしてもよい。また、この「フラグ情報」を、Octreeパタンデータのビットストリームと異なるビットストリームに含めるようにしてもよい。これらの場合、どの「フラグ情報」がどの葉ノードに対応しているかを示す情報も必要になる。
【０１９１】
＜符号化部＞
図１６は、この場合の符号化部１１４（図３）の主な構成例を示すブロック図である。図１６に示されるように、この場合の符号化部１１４は、Octree符号化部３２１、２値化部３２２、および可逆符号化部３２３を有する。
【０１９２】
Octree符号化部３２１は、Octree符号化に関する処理を行う。例えば、Octree符号化部３２１は、ボクセル設定部１１３より供給されるボクセルデータのジオメトリデータ（位置情報）をOctree符号化し、Octreeパタンデータを生成する。その際、Octree符号化部３２１は、最下位レベルと異なるレベルの所望のノードを葉ノードとする場合、その所望のノードの位置を特定する。
【０１９３】
図１６に示されるように、Octree符号化部３２１は、Octree深度制御部３３１およびOctree構成部３３２を有する。
【０１９４】
Octree深度制御部３３１は、Octreeパタンの深度に関する制御を行う。Octree構成部３３２は、Octreeパタンの構成に関する処理を行う。例えば、Octree構成部３３２は、ジオメトリデータに基づいてOctreeパタンを構築し、そのジオメトリデータに対応するOctreeパタンデータを生成する。Octree深度制御部３３１は、そのOctreeパタンの構築を制御し、Octreeパタンの深さを制御する。
【０１９５】
例えば、Octree深度制御部３３１は、Octree構成部３３２がジオメトリデータをOctree符号化してOctreeパタンを生成する際に、そのOctree構成部３３２を制御し、Octreeパタンの最下位レベルよりも上位のレベルの所望のノードを葉ノードとするようにすることができる。つまり、一部のノードがOctreeパタンの最下位レベルよりも上位のレベルにおいて終端する（子孫ノードを形成しない）ようにすることができる。さらに、Octree深度制御部３３１は、その所望のノードを葉ノードとするノードとして特定する。
【０１９６】
Octree符号化部３２１（Octree構成部３３２）は、生成したOctreeパタンデータを２値化部３２２に供給する。また、Octree符号化部３２１（Octree深度制御部３３１）は、特定したノードに関する情報を可逆符号化部３２３に供給する。
【０１９７】
このようにすることにより、符号化部１１４は、Octreeパタンを形成しながら、葉ノードとされるノードを特定することができる。
【０１９８】
なお、Octree符号化部３２１（Octree深度制御部３３１およびOctree構成部３３２のそれぞれ）は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、Octree符号化に関する処理を行うようにしてもよい。
【０１９９】
２値化部３２２は、２値化に関する処理を行う。例えば、２値化部３２２は、Octree符号化部３２１から供給されるOctreeパタンデータを２値化して２値データを生成する。２値化部３２２は、生成した２値データを可逆符号化部３２３に供給する。
【０２００】
なお、２値化部３２２は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、２値化に関する処理を行うようにしてもよい。
【０２０１】
可逆符号化部３２３は、可逆符号化に関する処理を行う。例えば、可逆符号化部３２３は、２値化部３２２から供給される２値データを可逆符号化し、ビットストリーム（つまり、Octreeパタンデータの符号化データ）を生成する。この可逆符号化の方法は任意であり、例えば、CABACであってもよい。
【０２０２】
また、可逆符号化部３２３は、Octree深度制御部３３１から供給される情報に基づいて、ビットストリームの、Octree深度制御部３３１により葉ノードとするノードとして特定されたノードに対応する位置に、上述の「所定のフラグ情報（end_of_node_one_bit）」を挿入する。
【０２０３】
また、例えば、可逆符号化部３２３は、OctreeパタンデータのOctreeパタンの深さ（レベル数）を指定する情報を、ヘッダやパラメータセット等に格納し、ビットストリームに含める。
【０２０４】
可逆符号化部３２３は、生成したビットストリームを符号化部１１４の外部（すなわち符号化装置１００の外部）に出力する。
【０２０５】
なお、可逆符号化部３２３は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、可逆符号化に関する処理を行うようにしてもよい。
【０２０６】
上述のように、Octreeパタンの最下位レベルよりも上位のレベルにおいてノードを終端させる場合、可逆符号化部３２３は、ビットストリームの、Octree符号化部２２１により特定されたそのノードに対応する位置に、所定のフラグ情報（深さ制御情報）を挿入する。
【０２０７】
したがって、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０２０８】
なお、Octreeパタンデータの符号化方法は任意である。例えば、CAVLC（Context-based Adaptive Variable Length Code）を用いてOctreeパタンデータを符号化するようにしてもよい。その場合、２値化部２２２および可逆符号化部２２３の代わりに、CAVLCを行う可逆符号化部を設けるようにしてもよい。
【０２０９】
＜符号化処理の流れ＞
この場合も、符号化装置１００により実行される符号化処理の流れは、図７のフローチャートを参照して説明した場合と同様であるのでその説明は省略する。
【０２１０】
＜ジオメトリデータ符号化処理の流れ＞
次に、この場合の、図７のステップＳ１０４において実行されるジオメトリデータ符号化処理の流れの例を、図１７および図１８のフローチャートを参照して説明する。
【０２１１】
ジオメトリデータ符号化処理が開始されると、Octree深度制御部３３１は、図１７のステップＳ２０１において、Octreeパタンの処理対象ノードを初期化する。
【０２１２】
ステップＳ２０２において、Octree深度制御部３３１は、処理対象ノードのレベルが最下位レベルであるか否かを判定する。処理対象ノードのレベルが最下位レベルでないと判定された場合、処理はステップＳ２０３に進む。
【０２１３】
ステップＳ２０３において、Octree深度制御部３３１は、処理対象ノードを終端とするか否かを判定する。処理対象ノードを終端とする、すなわち、処理対象ノードを葉ノードとすると判定された場合、処理はステップＳ２０４に進む。
【０２１４】
ステップＳ２０４において、Octree深度制御部３３１は、処理対象ノードを終端とするノードとして（すなわち終端位置として）記憶する（特定する）。また、Octree構成部３３２は、その処理対象ノードの子孫ノードを処理対象候補から除外する。つまり、処理対象ノードを葉ノードとし、それに属する子ノードを形成しないようにする。ステップＳ２０４の処理が終了すると、処理はステップＳ２０６に進む。つまり、最下位レベルよりも上位のレベルの葉ノードに対しては、ビット列は設定されない。
【０２１５】
また、ステップＳ２０３において、処理対象ノードを終端としないと判定された場合、処理はステップＳ２０５に進む。
【０２１６】
ステップＳ２０５において、Octree構成部３３２は、終端としない処理対象ノードに対して、ジオメトリデータに基づいて「子ノードのビットパタン」、すなわち、処理対象ノードに対応する領域を８分割（２×２×２分割）した領域のいずれにポイントが存在するかを示すビットパタンのビット列を生成し、そのビット列を処理対象ノードに設定する。ステップＳ２０５の処理が終了すると処理はステップＳ２０６に進む。
【０２１７】
また、ステップＳ２０２において、処理対象ノードのレベルが最下位レベルである、すなわち、ジオメトリデータ（のボクセル）と同じ解像度のレベルであると判定された場合、ステップＳ２０３乃至ステップＳ２０５の処理は省略され、処理はステップＳ２０６に進む。つまり、最下位レベルのノードに対しては、ビット列は設定されない。
【０２１８】
ステップＳ２０６において、Octree深度制御部３３１は、全ノードを処理したか否かを判定する。ジオメトリデータに対応するOctreeパタンが構築されておらず、未処理のノードが存在すると判定された場合、処理はステップＳ２０７に進む。
【０２１９】
ステップＳ２０７において、Octree深度制御部３３１は、処理対象ノードを前順の次のノードに設定する。処理対象ノードが更新されると処理はステップＳ２０２に戻る。つまり、ステップＳ２０２乃至ステップＳ２０７の各処理が、ジオメトリデータに対応するOctreeパタンの各ノードに対して行われる。
【０２２０】
そして、ステップＳ２０６において、ジオメトリデータに対応するOctreeパタンが構築され、全ノードを処理したと判定された場合、処理はステップＳ２０８に進む。
【０２２１】
ステップＳ２０８において、２値化部３２２は、上述の処理により生成されたジオメトリデータに対応するOctreeパタンデータを２値化する。ステップＳ２０８の処理が終了すると、処理は、図１８に進む。
【０２２２】
図１８のステップＳ２１１において、可逆符号化部３２３は、処理対象ノードを初期化する。
【０２２３】
ステップＳ２１２において、可逆符号化部３２３は、図１７のステップＳ２０８において生成された処理対象ノードの２値データを読み込む。
【０２２４】
図１８のステップＳ２１３において、可逆符号化部３２３は、処理対象ノードが、図１７のステップＳ２０４において記憶した（特定した）終端位置であるか否かを判定する。処理対象ノードが終端位置であると判定された場合、処理はステップＳ２１４に進む。
【０２２５】
ステップＳ２１４において、可逆符号化部３２３は、ビットストリームの、処理対象ノードに対応する位置（すなわち終端位置）に、所定のフラグ情報（end_of_node_one_bit）を挿入する。ステップＳ２１４の処理が終了すると処理はステップＳ２１６に進む。
【０２２６】
また、ステップＳ２１３において、処理対象ノードが終端位置でないと判定された場合、処理はステップＳ２１５に進む。
【０２２７】
ステップＳ２１５において、可逆符号化部３２３は、処理対象ノードの２値データを可逆符号化する。ステップＳ２１５の処理が終了すると、処理はステップＳ２１６に進む。
【０２２８】
ステップＳ２１６において、可逆符号化部３２３は、全ての２値データを処理したか否かを判定する。未処理の２値データが存在すると判定された場合、処理はステップＳ２１７に進む。
【０２２９】
ステップＳ２１７において、可逆符号化部３２３は、処理対象ノードを前順の次のノードに設定する。処理対象ノードが更新されると処理はステップＳ２１２に戻る。つまり、ステップＳ２１２乃至ステップＳ２１７の各処理が、Octreeパタンの各ノードの２値データに対して行われる。
【０２３０】
そして、ステップＳ２１６において、全ての２値データを処理したと判定された場合、ジオメトリデータ符号化処理が終了し、処理は図７に戻る。
【０２３１】
以上のように各処理を実行することにより、符号化装置１００は、この場合も、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０２３２】
なお、以上においてはOctreeパタンの走査順として、前順を例に説明したが、この走査順は任意であり、前順に限定されない。例えば、先行順、前置順、行きがけ順、間順、中間順、通りがけ順、後順、後行順、後置順、帰りがけ順、またはレベル順等であってもよい。
【０２３３】
＜符号化部の他の例＞
なお、Octreeパタンを生成後に編集し、最下位レベルよりも上位のレベルの所望のノードを葉ノード化し、その所望のノードを葉ノードとするノードとして特定するようにしてもよい。
【０２３４】
図１９は、その場合の符号化部１１４（図３）の主な構成例を示すブロック図である。この場合、図１９に示されるように、符号化部１１４は、図１６の場合と同様に、Octree符号化部３２１、２値化部３２２、および可逆符号化部３２３を有する。
【０２３５】
ただし、Octree符号化部３２１は、Octree構成部３４１およびOctree深度制御部３４２を有する。Octree構成部３４１は、Octreeパタンの構成に関する処理を行う。例えば、Octree構成部３４１は、一般的なOctree符号化を行い、ジオメトリデータに基づいてOctreeパタンを構築し、ジオメトリデータに対応するOctreeパタンデータを生成する。
【０２３６】
Octree深度制御部３４２は、Octreeパタンの深度に関する制御を行う。例えば、Octree深度制御部３４２は、Octree構成部３４１により構築されたOctreeパタンを編集し、最下位レベルよりも上位のレベルの所望のノードを葉ノード化する。つまり、Octree深度制御部３４２は、Octreeパタンの最下位レベルよりも上位のレベルの所望のノードに属する子孫ノードを削除し、その所望のノードを葉ノード化する。さらに、Octree深度制御部３４２は、その所望のノードを、葉ノードとするノードとして特定する（記憶する）。Octree符号化部３２１（Octree深度制御部３４２）は、生成したOctreeパタンデータを２値化部３２２に供給する。また、Octree符号化部３２１（Octree深度制御部３４２）は、特定したノードを示す情報を可逆符号化部３２３に供給する。
【０２３７】
なお、Octree符号化部３２１（Octree構成部３４１およびOctree深度制御部３４２のそれぞれ）は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、Octree符号化に関する処理を行うようにしてもよい。
【０２３８】
２値化部３２２は、図１６の場合と同様に、２値化に関する処理を行う。例えば、２値化部３２２は、Octree符号化部３２１（Octree深度制御部３４２）から供給されるOctreeパタンデータを２値化して２値データを生成する。２値化部３２２は、生成した２値データを可逆符号化部３２３に供給する。
【０２３９】
可逆符号化部３２３は、図１６の場合と同様に、可逆符号化に関する処理を行う。例えば、可逆符号化部３２３は、２値化部３２２から供給される２値データを可逆符号化し、ビットストリーム（つまり、Octreeパタンデータの符号化データ）を生成する。
【０２４０】
また、可逆符号化部３２３は、Octree符号化部３２１（Octree深度制御部３４２）から供給される情報に基づいて、ビットストリームの、Octree深度制御部３４２により葉ノードとするノードとして特定されたノードに対応する位置に、上述の「所定のフラグ情報（end_of_node_one_bit）」を挿入する。
【０２４１】
また、例えば、可逆符号化部３２３は、OctreeパタンデータのOctreeパタンの深さ（レベル数）を指定する情報を、ヘッダやパラメータセット等に格納し、ビットストリームに含める。可逆符号化部３２３は、生成したビットストリームを符号化部１１４の外部（すなわち符号化装置１００の外部）に出力する。
【０２４２】
つまり、可逆符号化部２２３は、この場合も、「所定のフラグ情報（end_of_node_one_bit）」（深さ制御情報）を含むビットストリームを生成する。
【０２４３】
したがって、符号化部１１４は、この場合も、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０２４４】
＜符号化処理の流れ＞
この場合も、符号化装置１００により実行される符号化処理の流れは、図７のフローチャートを参照して説明した場合と同様であるのでその説明は省略する。
【０２４５】
＜ジオメトリデータ符号化処理の流れ＞
次に、この場合の、図７のステップＳ１０４において実行されるジオメトリデータ符号化処理の流れの例を、図２０および図２１のフローチャートを参照して説明する。
【０２４６】
この場合、ジオメトリデータ符号化処理が開始されると、Octree構成部３４１は、図２０のステップＳ２３１において、ジオメトリデータからOctreeパタンを構築し、そのOctreeパタンデータを生成する。
【０２４７】
ステップＳ２３２において、Octree深度制御部３４２は、Octreeパタンの処理対象ノードを初期化する。
【０２４８】
ステップＳ２３３において、Octree深度制御部３４２は、処理対象ノードのレベルが最下位レベルであるか否かを判定する。処理対象ノードのレベルが最下位レベルでないと判定された場合、処理はステップＳ２３４に進む。
【０２４９】
ステップＳ２３４において、Octree深度制御部３４２は、処理対象ノードを終端とするか否かを判定する。処理対象ノードを終端とする、すなわち、処理対象ノードを葉ノードとすると判定された場合、処理はステップＳ２３５に進む。
【０２５０】
ステップＳ２３５において、Octree深度制御部３４２は、処理対象ノードを終端とするノードとして（すなわち終端位置として）記憶する（特定する）。また、Octree構成部３４１は、その処理対象ノードの子孫ノードを削除する。つまり、処理対象ノードを葉ノードとし、それに属する子孫ノードを削除する。ステップＳ２３５の処理が終了すると、処理はステップＳ２３６に進む。
【０２５１】
また、ステップＳ２３４において、処理対象ノードを終端としないと判定された場合、ステップＳ２３５の処理が省略され、処理はステップＳ２３６に進む。つまり、終端としないノードは編集されない（Octree構成部３４１により生成されたままである）。
【０２５２】
また、ステップＳ２３３において、処理対象ノードのレベルが最下位レベルである、すなわち、ジオメトリデータ（のボクセル）と同じ解像度のレベルであると判定された場合、ステップＳ２３４およびステップＳ２３５の処理は省略され、処理はステップＳ２３６に進む。つまり、最下位レベルのノードに対しては、ビット列は設定されないので編集も行われない（Octree構成部３４１により生成されたままである）。
【０２５３】
ステップＳ２３６において、Octree深度制御部３４２は、ステップＳ２３１において生成されたOctreeパタンの全ノードを処理したか否かを判定する。未処理のノードが存在すると判定された場合、処理はステップＳ２３７に進む。
【０２５４】
ステップＳ２３７において、Octree深度制御部３４２は、処理対象ノードを前順の次のノードに設定する。処理対象ノードが更新されると処理はステップＳ２３３に戻る。つまり、ステップＳ２３３乃至ステップＳ２３７の各処理が、ジオメトリデータに対応するOctreeパタンの各ノードに対して行われる。
【０２５５】
そして、ステップＳ２３６において、全ノードを処理したと判定された場合、処理はステップＳ２３８に進む。
【０２５６】
ステップＳ２３８において、２値化部３２２は、上述の処理により生成されたジオメトリデータに対応するOctreeパタンデータを２値化する。ステップＳ２３８の処理が終了すると、処理は、図２１に進む。
【０２５７】
図２１のステップＳ２４１において、可逆符号化部３２３は、処理対象ノードを初期化する。
【０２５８】
ステップＳ２４２において、可逆符号化部３２３は、図２０のステップＳ２３８において生成された処理対象ノードの２値データを読み込む。
【０２５９】
図２１のステップＳ２４３において、可逆符号化部３２３は、処理対象ノードが、図２０のステップＳ２０４において記憶した（特定した）終端位置であるか否かを判定する。処理対象ノードが終端位置であると判定された場合、処理は図２１のステップＳ２４４に進む。
【０２６０】
ステップＳ２４４において、可逆符号化部３２３は、ビットストリームの、処理対象ノードに対応する位置（すなわち終端位置）に、所定のフラグ情報（end_of_node_one_bit）を挿入する。ステップＳ２４４の処理が終了すると処理はステップＳ２４６に進む。
【０２６１】
また、ステップＳ２４３において、処理対象ノードが終端位置でないと判定された場合、処理はステップＳ２４５に進む。
【０２６２】
ステップＳ２４５において、可逆符号化部３２３は、処理対象ノードの２値データを可逆符号化する。ステップＳ２４５の処理が終了すると、処理はステップＳ２４６に進む。
【０２６３】
ステップＳ２４６において、可逆符号化部３２３は、全ての２値データを処理したか否かを判定する。未処理の２値データが存在すると判定された場合、処理はステップＳ２４７に進む。
【０２６４】
ステップＳ２４７において、可逆符号化部３２３は、処理対象ノードを前順の次のノードに設定する。処理対象ノードが更新されると処理はステップＳ２４２に戻る。つまり、ステップＳ２４２乃至ステップＳ２４７の各処理が、Octreeパタンの各ノードの２値データに対して行われる。
【０２６５】
そして、ステップＳ２４６において、全ての２値データを処理したと判定された場合、ジオメトリデータ符号化処理が終了し、処理は図７に戻る。
【０２６６】
以上のように各処理を実行することにより、符号化装置１００は、この場合も、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０２６７】
なお、以上においてはOctreeパタンの走査順として、前順を例に説明したが、この走査順は任意であり、前順に限定されない。例えば、先行順、前置順、行きがけ順、間順、中間順、通りがけ順、後順、後行順、後置順、帰りがけ順、またはレベル順等であってもよい。
【０２６８】
＜復号装置＞
この場合の符号化装置１００が生成したビットストリームを復号する復号装置２５０も、図１１を参照して説明した場合と同様の構成を有する。
【０２６９】
ただし、この場合、深さ制御情報が、例えば、『前記ビットストリームにおいて、前記Octreeパタンの前記最下位レベルよりも上位のレベルの前記深さ制御情報に対応する特定のノードが、葉ノードであるか』を示す所定のフラグ情報（end_of_node_one_bit）であるようにしてもよい。
【０２７０】
このようにすることにより、復号部２６１は、ビットストリームにおいて、その「所定のフラグ情報」を検出することにより、容易に「特定のノードが葉ノードである」ことを把握することができる。
【０２７１】
また、上述したように、この「所定のフラグ情報」は、ビットストリームの、Octreeパタンの最下位レベルよりも上位のレベルの葉ノードに対応する位置に挿入されており、その位置に対応するノードが葉ノードであるかを示す。
【０２７２】
つまり、ビットストリームに挿入される「フラグ情報（深さ制御情報）」の位置によって、Octreeパタンの最下位レベルよりも上位のレベルの葉ノードの位置が示される。したがって、復号部２６１は、ビットストリームを復号してOctreeパタンを再構築する際に、そのビットストリームにおける「フラグ情報（深さ制御情報）」の位置を検出（特定）することにより、Octreeパタンの最下位レベルよりも上位のレベルの葉ノードを形成するように、Octreeパタンを再構築することができる。つまり、最下位レベルよりも上位のレベルに葉ノードを含むOctreeパタンを正しく復号することができる。
【０２７３】
＜復号部＞
図２２は、この場合の復号部２６１の主な構成例を示すブロック図である。図２２に示されるように、復号部２６１は、終端検出部３７１、可逆復号部３７２、多値化部３７３、およびジオメトリ再構成部３７４を有する。
【０２７４】
終端検出部３７１は、ノードの終端の検出に関する処理を行う。例えば、終端検出部３７１は、符号化装置１００により生成されたビットストリームに挿入された「所定のフラグ情報（end_of_node_one_bit）」を検出し、その位置を終端位置として特定する（記憶する）。終端検出部３７１は、その検出結果を可逆復号部３７２および多値化部３７３に供給する。
【０２７５】
なお、終端検出部３７１は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、終端の検出に関する処理を行うようにしてもよい。
【０２７６】
可逆復号部３７２は、可逆復号に関する処理を行う。例えば、可逆復号部３７２は、符号化装置１００により生成されたビットストリームを、可逆符号化部３２３に対応する方法で可逆復号し、２値データを得る。この可逆復号方法は、可逆符号化部３２３の可逆符号化方法に対応するものであればどのような方法であってもよい。例えば、CABACであってもよい。
【０２７７】
また、その際、可逆復号部３７２は、ビットストリームの、終端検出部３７１により検出された終端位置（「所定のフラグ情報（end_of_node_one_bit）」が挿入された位置）から、その「所定のフラグ情報（end_of_node_one_bit）」を削除する。
【０２７８】
可逆復号部３７２は、以上のようにして得た２値データを多値化部３７３に供給する。
【０２７９】
なお、可逆復号部３７２は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、可逆復号に関する処理を行うようにしてもよい。
【０２８０】
多値化部３７３は、多値化に関する処理を行う。例えば、多値化部３７３は、可逆復号部３７２から供給される２値データを多値化し、Octreeパタンを再構築して、Octreeパタンデータを生成する。その際、終端検出部３７１は、終端位置の検出結果に応じて多値化部３７３を制御し、Octreeパタンの再構築を制御する。
【０２８１】
例えば、多値化部３７３は、Octreeパタンの再構築において、終端検出部３７１により検出（特定）されたビットストリームの終端位置に対応するノードを終端（葉ノード）とし、そのノードに属する子孫ノードを構築しないようにする。このようにすることにより、多値化部３７３は、「Octreeパタンの深さを指定する情報」により指定されるOctreeパタンの最下位レベルよりも上位のレベルに葉ノードを形成するように、Octreeパタンを再構築することができる。
【０２８２】
多値化部３７３は、このようにして得られたOctreeパタンデータを、ジオメトリ再構成部３７４に供給する。
【０２８３】
なお、多値化部３７３は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、多値化に関する処理を行うようにしてもよい。
【０２８４】
ジオメトリ再構成部３７４は、ジオメトリデータの再構成に関する処理を行う。例えば、ジオメトリ再構成部３７４は、多値化部３７３から供給されるOctreeパタンデータを用いてジオメトリデータを再構成する。ジオメトリ再構成部３７４は、得られたジオメトリデータをポイントクラウド化処理部２６２（図１１）に供給する。
【０２８５】
なお、ジオメトリ再構成部３７４は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、ジオメトリデータの再構成に関する処理を行うようにしてもよい。
【０２８６】
以上のように、終端検出部３７１乃至多値化部３７３は、ビットストリームを復号し、そのビットストリームに挿入された所定のフラグ情報（深さ制御情報）に基づいて、その最下位レベルと異なるレベルの葉ノードを含むOctreeパタンを構築する。
【０２８７】
したがって、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０２８８】
なお、ビットストリームの復号方法は、その符号化方法に対応するものであれば任意であり、上述の例に限定されない。例えば、CAVLCを用いてビットストリームを復号するようにしてもよい。つまり、この場合、ビットストリームは、CAVLCを用いて符号化されている。その場合、可逆復号部３７２および多値化部３７３の代わりに、CAVLCを行う可逆復号部を設けるようにしてもよい。
【０２８９】
＜復号処理の流れ＞
この場合も、復号装置２５０により実行される復号処理の流れは、図１３のフローチャートを参照して説明した場合と同様であるのでその説明は省略する。
【０２９０】
＜ビットストリーム復号処理の流れ＞
次に、図１３のステップＳ１６１において実行されるビットストリーム復号処理の流れの例を、図２３のフローチャートを参照して説明する。
【０２９１】
ビットストリーム復号処理が開始されると、終端検出部３７１は、ステップＳ２６１において、ビットストリームを読み込む。
【０２９２】
ステップＳ２６２において、終端検出部３７１は、そのビットストリームにおいて、所定のフラグ情報（end_of_node_one_bit）を探索し、検出したか否かを判定する。所定のフラグ情報（end_of_node_one_bit）を検出したと判定された場合、処理は、ステップＳ２６３に進む。
【０２９３】
ステップＳ２６３において、終端検出部３７１は、その所定のフラグ情報（end_of_node_one_bit）を検出した位置を終端位置として記憶する（特定する）。
【０２９４】
ステップＳ２６４において、可逆復号部３７２は、ステップＳ２６１において読み込まれたビットストリームの、ステップＳ２６３において特定された終端位置から、所定のフラグ情報（end_of_node_one_bit）を削除する。
【０２９５】
ステップＳ２６４の処理が終了すると処理はステップＳ２６５に進む。また、ステップＳ２６２において、所定のフラグ情報（end_of_node_one_bit）を検出していないと判定された場合、ステップＳ２６３およびステップＳ２６４の処理が省略され、処理はステップＳ２６５に進む。
【０２９６】
ステップＳ２６５において、可逆復号部３７２は、ステップＳ２６１において読み込まれたビットストリームを可逆復号する。
【０２９７】
ステップＳ２６６において、可逆復号部３７２は、全てのビットストリームを処理したか否かを判定する。未処理のビットストリームが存在すると判定された場合、処理はステップＳ２６１に戻る。ステップＳ２６１乃至ステップＳ２６６の処理が各ビットストリームに対して繰り返し実行され、ステップＳ２６６において、ビットストリームを全て処理したと判定された場合、処理はステップＳ２６７に進む。
【０２９８】
ステップＳ２６７において、多値化部３７３は、ステップＳ２６５の処理により得られた２値データを読み込む。
【０２９９】
ステップＳ２６８において、多値化部３７３は、その２値データに、ステップＳ２６３において特定された終端位置が含まれるか否かを判定する。終端位置が含まれると判定された場合、処理はステップＳ２６９に進む。
【０３００】
ステップＳ２６９において、多値化部３７３は、その終端位置に対応するノードを終端（葉ノード）として２値データを多値化する。つまり、多値化部３７３は、２値データを多値化し、その終端位置に対応するノードを終端（葉ノード）とするように、Octreeパタンを再構築する。つまり、深さ制御情報（終端識別ビットパタンのビット列）を、再構築するOctreeパタンに反映させる。
【０３０１】
ステップＳ２６９の処理が終了すると、処理はステップＳ２７１に進む。また、ステップＳ２６８において、２値データに終端位置が含まれないと判定された場合、処理はステップＳ２７０に進む。
【０３０２】
ステップＳ２７０において、多値化部３７３は、２値データを多値化し、一般的なOctreeパタンの場合と同様に、Octreeパタンを再構築する。ステップＳ２７０の処理が終了すると、処理はステップＳ２７１に進む。
【０３０３】
ステップＳ２７１において、多値化部３７３は、２値データを全て処理したか否かを判定する。未処理の２値データが存在する場合、その未処理の２値データを新たな処理対象として、処理をステップＳ２６７に戻す。つまり、全ての２値データに対して、ステップＳ２６７乃至ステップＳ２７１の処理が実行される。そして、ステップＳ２７１において２値データを全て処理したと判定された場合、処理はステップＳ２７２に進む。
【０３０４】
ステップＳ２７２において、ジオメトリ再構成部３７４は、以上の処理により得られたOctreeパタンデータを用いてジオメトリデータを再構成する。
【０３０５】
ステップＳ２７２の処理が終了するとビットストリーム復号処理が終了し、処理は図１３に戻る。
【０３０６】
以上のように各処理を実行することにより、復号装置２５０は、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０３０７】
＜４．第３の実施の形態＞
＜split_voxel_flag＞
なお、「深さ制御情報」は、任意の情報であるが、例えば、『Octreeパタンの最下位レベルの、その深さ制御情報に対応する特定のノードに対する子孫ノードの追加に関する追加情報』であるようにしてもよい。このようにすることにより、復号側において、ビットストリームに含まれるその「追加情報」に基づいて、特定のノードに対する子孫ノードを追加することができる。
【０３０８】
また、この「追加情報」は、ビットストリームの、Octreeパタンの最下位レベルの子孫ノードを追加するノードに対応する位置に、挿入されるようにしてもよい。このようにすることにより、復号側において、「追加情報」が挿入された位置から、子孫ノードを追加するノード（追加情報に対応するノード）をより容易に特定することができる。
【０３０９】
例えば、図２４に示されるOctreeパタンのように、最下位レベルの一部のノードに対して、「追加情報」を設定する。この「追加情報」には、子孫ノードの追加に関する情報が含まれる。この「追加情報」に含まれる具体的な内容は任意である。例えば、「追加情報」に、ビットストリームのその追加情報が挿入された位置に対応するノードがさらに分割されるかを示す所定のフラグ情報（split_voxel_flag）が含まれるようにしてもよい。また、例えば、「追加情報」に、追加する子孫ノードの深さに関する情報がさらに含まれるようにしてもよい。このようにすることにより、追加情報に基づいてより多様な構成の子孫ノードを追加することができる。
【０３１０】
例えば、図２４の場合、Octreeパタンの、最下位レベルの右から２番目のノードに、追加情報として「所定のフラグ情報（split_voxel_flag）」が設定されている。この情報に基づいて、このノードには、子ノードが追加される。
【０３１１】
すなわち、このような「追加情報（深さ制御情報）」により、Octreeパタンにおいて、ポイントの解像度の部分的な制御を表現することが可能になる。つまり、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。
【０３１２】
換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においても、Octree符号化を適用することができるので（データ群の解像度を部分的に制御する場合にも、そのデータ群の木構造化を実現することができるので）、符号化効率の低減を抑制することができる。
【０３１３】
なお、この「フラグ情報」の名称（シンタックス）は任意であり、「split_voxel_flag」以外であってもよい。また、この「フラグ情報（split_voxel_flag）」の値は任意である。例えば、「１」であってもよいし、「０」であってもよい。また、この「フラグ情報」が複数ビット（bit）により構成されるようにしてもよい。さらに、この「フラグ情報」が葉ノードであること以外を示す情報が含まれるようにしてもよい。また、この「フラグ情報」が全てのノードに設定され、その値によって子孫ノードが追加されるか否かを識別することができるようにしてもよい。なお、この「フラグ情報」が子孫ノードの全ての構成を示す情報を含むようにし、Octreeパタンの最下位レベル（Octreeパタンの深さを指定する情報に基づく最下位レベル）のノードに設定された「フラグ情報」が追加する全ての子孫ノードを表現するようにしてもよい。つまり、例えば複数階層の子孫ノードを追加する場合も、そのOctreeパタンの最下位レベルのノードに設定される１つの「フラグ情報」によってその追加する全ての子孫ノードを表現するようにしてもよい。また、この「フラグ情報」が、設定されたノードの分割に関する情報のみを含むようにしてもよい。つまり、例えば、複数階層の子孫ノードを追加する場合は、その子孫ノードのそれぞれにこの「フラグ情報」を設定することによりその複数階層の子孫ノードを表現するようにしてもよい。
【０３１４】
また、この「フラグ情報」は、葉ノードとの対応関係が明らかにされているのであれば、ビットストリームの、対応するノードの位置以外に挿入されるようにしてもよい。例えば、この「フラグ情報」を、まとめてヘッダやパラメータセット等に格納するようにしてもよい。また、この「フラグ情報」を、Octreeパタンデータのビットストリームと異なるビットストリームに含めるようにしてもよい。これらの場合、どの「フラグ情報」がどの葉ノードに対応しているかを示す情報も必要になる。
【０３１５】
＜符号化部＞
図２５は、この場合の符号化部１１４（図３）の主な構成例を示すブロック図である。図２５に示されるように、この場合の符号化部１１４は、Octree深度制御部４２１、追加情報生成部４２２、Octree符号化部４２３、２値化部４２４、および可逆符号化部４２５を有する。
【０３１６】
Octree深度制御部４２１は、Octreeパタンの深度に関する制御を行う。例えば、Octree深度制御部４２１は、追加情報生成部４２２を制御することにより、追加情報の生成（すなわち、子孫ノードの追加）を制御し、Octreeパタンの深さを制御する。
【０３１７】
なお、Octree深度制御部４２１は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、Octreeの深さ制御に関する処理を行うようにしてもよい。
【０３１８】
追加情報生成部４２２は、Octree深度制御部４２１に指定されたノード（最下位レベルの葉ノード）に対して、追加情報を生成する。追加情報生成部４２２は、生成したその追加情報を可逆符号化部４２５に供給する。
【０３１９】
なお、追加情報生成部４２２は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、追加情報の生成に関する処理を行うようにしてもよい。
【０３２０】
Octree符号化部４２３は、Octree符号化に関する処理を行う。例えば、Octree符号化部４２３は、ボクセル設定部１１３より供給されるボクセルデータのジオメトリデータ（位置情報）をOctree符号化し、Octreeパタンデータを生成する。
【０３２１】
図２５に示されるように、Octree符号化部４２３は、Octree構成部４３１を有する。
【０３２２】
Octree構成部４３１は、Octreeパタンの構成に関する処理を行う。例えば、Octree構成部４３１は、ジオメトリデータに基づいてOctreeパタンを構築し、そのジオメトリデータに対応するOctreeパタンデータを生成する。Octree符号化部４２３（Octree構成部４３１）は、生成したOctreeパタンデータを２値化部４２４に供給する。
【０３２３】
なお、Octree符号化部４２３（Octree構成部４３１）は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、Octree符号化に関する処理を行うようにしてもよい。
【０３２４】
２値化部４２４は、２値化に関する処理を行う。例えば、２値化部４２４は、Octree符号化部４２３から供給されるOctreeパタンデータを２値化して２値データを生成する。２値化部４２４は、生成した２値データを可逆符号化部４２５に供給する。
【０３２５】
なお、２値化部４２４は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、２値化に関する処理を行うようにしてもよい。
【０３２６】
可逆符号化部４２５は、可逆符号化に関する処理を行う。例えば、可逆符号化部４２５は、２値化部４２４から供給される２値データを可逆符号化し、ビットストリーム（つまり、Octreeパタンデータの符号化データ）を生成する。この可逆符号化の方法は任意であり、例えば、CABACであってもよい。
【０３２７】
また、可逆符号化部４２５は、追加情報生成部４２２から供給される追加情報を可逆符号化し、ビットストリームの、子孫ノードを追加する葉ノードに対応する位置に挿入する。さらに、可逆符号化部４２５は、OctreeパタンデータのOctreeパタンの深さ（レベル数）を指定する情報を、ヘッダやパラメータセット等に格納し、ビットストリームに含める。
【０３２８】
可逆符号化部４２５は、生成したビットストリームを符号化部１１４の外部（すなわち符号化装置１００の外部）に出力する。
【０３２９】
なお、可逆符号化部４２５は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、可逆符号化に関する処理を行うようにしてもよい。
【０３３０】
上述のように、Octreeパタンの最下位レベルの葉ノードにさらに子孫ノードを追加する場合、可逆符号化部４２５は、ビットストリームの、そのノードに対応する位置に、追加情報（深さ制御情報）を挿入する。
【０３３１】
したがって、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０３３２】
なお、Octreeパタンデータの符号化方法は任意である。例えば、CAVLC（Context-based Adaptive Variable Length Code）を用いてOctreeパタンデータを符号化するようにしてもよい。その場合、２値化部４２４および可逆符号化部４２５の代わりに、CAVLCを行う可逆符号化部を設けるようにしてもよい。
【０３３３】
＜符号化処理の流れ＞
この場合も、符号化装置１００により実行される符号化処理の流れは、図７のフローチャートを参照して説明した場合と同様であるのでその説明は省略する。
【０３３４】
＜ジオメトリデータ符号化処理の流れ＞
次に、この場合の、図７のステップＳ１０４において実行されるジオメトリデータ符号化処理の流れの例を、図２６のフローチャートを参照して説明する。
【０３３５】
ジオメトリデータ符号化処理が開始されると、Octree深度制御部４２１は、図２６のステップＳ２９１において、Octreeパタンの処理対象ノードを初期化する。
【０３３６】
ステップＳ２９２において、Octree深度制御部４２１は、処理対象ノードのレベルが最下位レベルであるか否かを判定する。処理対象ノードのレベルが最下位レベルでないと判定された場合、処理はステップＳ２９３に進む。
【０３３７】
ステップＳ２９３において、Octree深度制御部４２１は、処理対象ノードにおいてOctreeを深くするか否か、すなわち、子ノードを追加するか否かを判定する。Octreeを深くする（子ノードを追加する）と判定された場合、処理はステップＳ２９４に進む。
【０３３８】
ステップＳ２９４において、追加情報生成部４２２は、処理対象ノードに追加する子孫ノードに関する情報（例えば、split_voxel_flag等）を含む追加情報を生成する。
【０３３９】
ステップＳ２９４の処理が終了すると、処理はステップＳ２９６に進む。また、ステップＳ２９３において、Octreeを深くしない（つまり、処理対象ノードに子ノードを追加しない）と判定された場合、ステップＳ２９４の処理が省略され、処理はステップＳ２９６に進む。
【０３４０】
また、ステップＳ２９２において、処理対象ノードが最下位レベルでないと判定された場合、処理はステップＳ２９５に進む。
【０３４１】
ステップＳ２９５において、Octree符号化部４２３（Octree構成部４３１）は、ジオメトリデータに基づいて、子ノードのビットパタンを有するビット列を生成し、そのビット列を処理対象ノードに設定する。ステップＳ２９５の処理が終了すると、処理はステップＳ２９６に進む。
【０３４２】
ステップＳ２９６において、Octree深度制御部４２１は、全ノードを処理したか否かを判定する。ジオメトリデータに対応するOctreeパタンが構築されておらず、未処理のノードが存在すると判定された場合、処理はステップＳ２９７に進む。
【０３４３】
ステップＳ２９７において、Octree深度制御部４２１は、処理対象ノードを前順の次のノードに設定する。処理対象ノードが更新されると処理はステップＳ２９２に戻る。つまり、ステップＳ２９２乃至ステップＳ２９７の各処理が、ジオメトリデータに対応するOctreeパタンの各ノードに対して行われる。
【０３４４】
そして、ステップＳ２９６において、ジオメトリデータに対応するOctreeパタンが構築され、全ノードを処理したと判定された場合、処理はステップＳ２９８に進む。
【０３４５】
ステップＳ２９８において、２値化部４２４は、上述の処理により生成されたジオメトリデータに対応するOctreeパタンデータを２値化する。
【０３４６】
ステップＳ２９９において、可逆符号化部４２５は、２値データの子孫ノードを追加するノードに対応する位置に、追加情報を付加する。
【０３４７】
ステップＳ３００において、可逆符号化部４２５は、その２値データを可逆符号化し、ビットストリームを生成する。
【０３４８】
ステップＳ３００の処理が終了すると、ジオメトリデータ符号化処理が終了し、処理は図７に戻る。
【０３４９】
以上のように各処理を実行することにより、符号化装置１００は、この場合も、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０３５０】
なお、以上においてはOctreeパタンの走査順として、前順を例に説明したが、この走査順は任意であり、前順に限定されない。例えば、先行順、前置順、行きがけ順、間順、中間順、通りがけ順、後順、後行順、後置順、帰りがけ順、またはレベル順等であってもよい。
【０３５１】
＜復号装置＞
この場合の符号化装置１００が生成したビットストリームを復号する復号装置２５０も、図１１を参照して説明した場合と同様の構成を有する。
【０３５２】
ただし、この場合、深さ制御情報が、例えば、『Octreeパタンの最下位レベルの、深さ制御情報に対応する特定のノードに対する子孫ノードの追加に関する追加情報』であるようにしてもよい。
【０３５３】
このようにすることにより、復号部２６１は、ビットストリームにおいて、その「追加情報」を検出することにより、容易に「特定のノードに追加する子孫ノード」を把握することができる。
【０３５４】
なお、上述したように、この「追加情報」は、ビットストリームの、Octreeパタンの最下位レベルの、子孫ノードを追加するノードに対応する位置に挿入されているようにしてもよい。つまり、ビットストリームに挿入される「追加情報（深さ制御情報）」の位置によって、Octreeパタンの最下位レベルの、子孫ノードを追加するノード（葉ノード）の位置が示されるようにしてもよい。
【０３５５】
また、上述したように、「追加情報」に、ビットストリームのその追加情報が挿入された位置に対応するノードがさらに分割されるかを示す所定のフラグ情報（split_voxel_flag）が含まれるようにしてもよい。また、上述したように、「追加情報」に、追加する子孫ノードの深さに関する情報がさらに含まれるようにしてもよい。このようにすることにより、追加情報に基づいてより多様な構成の子孫ノードを追加することができる。
【０３５６】
このようにすることにより、復号部２６１は、ビットストリームを復号してOctreeパタンを再構築する際に、そのビットストリームにおける「追加情報（深さ制御情報）」の位置を検出（特定）することにより、Octreeパタンの最下位レベルの、追加情報に対応するノードに子孫ノードを追加するように、Octreeパタンを再構築することができる。つまり、最下位レベルの一部の葉ノードに追加された子孫ノードを含むOctreeパタンを正しく復号することができる。
【０３５７】
＜復号部＞
図２７は、この場合の復号部２６１の主な構成例を示すブロック図である。図２７に示されるように、復号部２６１は、可逆復号部４７１、追加情報検出部４７２、多値化部４７３、再構成制御部４７４、およびジオメトリ再構成部４７５を有する。
【０３５８】
可逆復号部４７１は、可逆復号に関する処理を行う。例えば、可逆復号部４７１は、符号化装置１００により生成されたビットストリームを、可逆符号化部４２５に対応する方法で可逆復号し、２値データを得る。この可逆復号方法は、可逆符号化部４２５の可逆符号化方法に対応するものであればどのような方法であってもよい。例えば、CABACであってもよい。
【０３５９】
可逆復号部４７１は、このようにして得た２値データを追加情報検出部４７２および多値化部４７３に供給する。
【０３６０】
なお、可逆復号部４７１は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、可逆復号に関する処理を行うようにしてもよい。
【０３６１】
追加情報検出部４７２は、追加情報の検出に関する処理を行う。例えば、追加情報検出部４７２は、ビットストリームに含まれる追加情報の検出を行う。そして、追加情報検出部４７２は、検出した追加情報を再構成制御部４７４に供給する。
【０３６２】
なお、追加情報検出部４７２は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、追加情報の検出に関する処理を行うようにしてもよい。
【０３６３】
多値化部４７３は、多値化に関する処理を行う。例えば、多値化部４７３は、可逆復号部４７１から供給される２値データを多値化し、Octreeパタンを再構築して、Octreeパタンデータを生成する。多値化部４７３は、このようにして得られたOctreeパタンデータを、ジオメトリ再構成部４７５に供給する。
【０３６４】
なお、多値化部４７３は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、多値化に関する処理を行うようにしてもよい。
【０３６５】
再構成制御部４７４は、再構成の制御に関する処理を行う。例えば、再構成制御部４７４は、追加情報検出部４７２により検出された追加情報に基づいて、ジオメトリ再構成部４７５を制御し、Octreeパタンにおいて、最下位レベルの、追加情報に対応するノードに対して、追加情報に対応する子孫ノードを追加させ、その追加を反映するようにジオメトリデータを再構成させる。
【０３６６】
なお、再構成制御部４７４は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、再構成の制御に関する処理を行うようにしてもよい。
【０３６７】
ジオメトリ再構成部４７５は、ジオメトリデータの再構成に関する処理を行う。例えば、ジオメトリ再構成部４７５は、再構成制御部４７４の制御に従って、多値化部３７３から供給されるOctreeパタンデータを用いてジオメトリデータを再構成する。つまり、ジオメトリ再構成部４７５は、追加情報に対応する子孫ノードを、Octreeパタンの最下位レベルの、追加情報に対応するノードに対して追加し、その追加を反映するようにジオメトリデータを再構成する。
【０３６８】
ジオメトリ再構成部４７５は、得られたジオメトリデータをポイントクラウド化処理部２６２（図１１）に供給する。
【０３６９】
なお、ジオメトリ再構成部４７５は、どのような構成を有するようにしてもよいが、例えば、CPU、ROM、RAM等を有し、CPUがROM等に記憶されているプログラムやデータをRAMにロードして実行することにより、ジオメトリデータの再構成に関する処理を行うようにしてもよい。
【０３７０】
以上のように、可逆復号部４７１乃至ジオメトリ再構成部４７５は、ビットストリームを復号し、そのビットストリームに挿入された所定のフラグ情報（深さ制御情報）に基づいて、その最下位レベルと異なるレベルの葉ノードを含むOctreeパタンを構築し、そのOctreeパタンに基づくジオメトリデータを再構成する。つまり、復号部２６１は、部分的に解像度を制御したOctreeパタンを実現し、そのOctreeパタンに対応するジオメトリデータを得ることができる。
【０３７１】
したがって、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０３７２】
なお、ビットストリームの復号方法は、その符号化方法に対応するものであれば任意であり、上述の例に限定されない。例えば、CAVLCを用いてビットストリームを復号するようにしてもよい。つまり、この場合、ビットストリームは、CAVLCを用いて符号化されている。その場合、可逆復号部４７１および多値化部４７３の代わりに、CAVLCを行う可逆復号部を設けるようにしてもよい。
【０３７３】
＜復号処理の流れ＞
この場合も、復号装置２５０により実行される復号処理の流れは、図１３のフローチャートを参照して説明した場合と同様であるのでその説明は省略する。
【０３７４】
＜ビットストリーム復号処理の流れ＞
次に、図１３のステップＳ１６１において実行されるビットストリーム復号処理の流れの例を、図２８のフローチャートを参照して説明する。
【０３７５】
ビットストリーム復号処理が開始されると、可逆復号部４７１は、ステップＳ３２１において、ビットストリームを可逆復号し、２値データを得る。
【０３７６】
ステップＳ３２２において、追加情報検出部４７２は、ステップＳ３２１において得られた２値データに追加情報が含まれるか否かを判定する。２値データに追加情報が含まれると判定した場合、処理はステップＳ３２３に進む。
【０３７７】
ステップＳ３２３において、多値化部４７３は、その２値データを多値化して最下位レベルまでのOctreeパタンデータを生成する。また、再構成制御部４７４は、検出された追加情報に基づいて、Octreeパタンの最下位レベルの、追加情報に対応するノードに対して、追加情報に対応する子孫ノードを追加させる。ステップＳ３２３の処理が終了すると、処理はステップＳ３２５に進む。
【０３７８】
また、ステップＳ３２２において、２値データに追加情報が含まれないと判定された場合、処理はステップＳ３２４に進む。
【０３７９】
ステップＳ３２４において、多値化部４７３は、その２値データを多値化して最下位レベルまでのOctreeパタンデータを生成する。ステップＳ３２４の処理が終了すると、処理はステップＳ３２５に進む。
【０３８０】
ステップＳ３２５において、ジオメトリ再構成部４７５は、Octreeパタンに対応するジオメトリデータを再構成する。Octreeパタンに子孫ノードが追加された場合、ジオメトリ再構成部４７５は、その追加を反映するようにジオメトリデータを再構成する。
【０３８１】
ステップＳ３２５の処理が終了すると、ビットストリーム復号処理が終了し、処理は図１３に戻る。
【０３８２】
以上のように各処理を実行することにより、復号装置２５０は、Octree符号化を行うポイントクラウドにおいて、ポイントの解像度の部分的な制御を実現することができる（木構造化可能なデータ群の解像度を部分的に制御することができる）。換言するに、ポイントクラウドのポイントの解像度を部分的に制御する場合においてもOctree符号化を適用することができ（データ群の解像度を部分的に制御する場合にもそのデータ群の木構造化を実現することができ）、符号化効率の低減を抑制することができる。
【０３８３】
＜５．その他＞
＜制御情報＞
以上の各実施の形態において説明した本技術に関する制御情報を符号化側から復号側に伝送するようにしてもよい。例えば、上述した本技術を適用することを許可（または禁止）するか否かを制御する制御情報（例えばenabled_flag）を伝送するようにしてもよい。また、例えば、上述した本技術を適用することを許可（または禁止）するブロックサイズの上限若しくは下限、またはその両方を指定する制御情報を伝送するようにしてもよい。
【０３８４】
＜ソフトウエア＞
上述した一連の処理は、ハードウエアにより実行させることもできるし、ソフトウエアにより実行させることもできる。また、一部の処理をハードウエアにより実行させ、他の処理をソフトウエアにより実行させることもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここでコンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータ等が含まれる。
【０３８５】
図２９は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。
【０３８６】
図２９に示されるコンピュータ９００において、CPU（Central Processing Unit）９０１、ROM（Read Only Memory）９０２、RAM（Random Access Memory）９０３は、バス９０４を介して相互に接続されている。
【０３８７】
バス９０４にはまた、入出力インタフェース９１０も接続されている。入出力インタフェース９１０には、入力部９１１、出力部９１２、記憶部９１３、通信部９１４、およびドライブ９１５が接続されている。
【０３８８】
入力部９１１は、例えば、キーボード、マウス、マイクロホン、タッチパネル、入力端子などよりなる。出力部９１２は、例えば、ディスプレイ、スピーカ、出力端子などよりなる。記憶部９１３は、例えば、ハードディスク、RAMディスク、不揮発性のメモリなどよりなる。通信部９１４は、例えば、ネットワークインタフェースよりなる。ドライブ９１５は、磁気ディスク、光ディスク、光磁気ディスク、または半導体メモリなどのリムーバブルメディア９２１を駆動する。
【０３８９】
以上のように構成されるコンピュータでは、CPU９０１が、例えば、記憶部９１３に記憶されているプログラムを、入出力インタフェース９１０およびバス９０４を介して、RAM９０３にロードして実行することにより、上述した一連の処理が行われる。RAM９０３にはまた、CPU９０１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０３９０】
コンピュータ（CPU９０１）が実行するプログラムは、例えば、パッケージメディア等としてのリムーバブルメディア９２１に記録して適用することができる。その場合、プログラムは、リムーバブルメディア９２１をドライブ９１５に装着することにより、入出力インタフェース９１０を介して、記憶部９１３にインストールすることができる。また、このプログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供することもできる。その場合、プログラムは、通信部９１４で受信し、記憶部９１３にインストールすることができる。その他、このプログラムは、ROM９０２や記憶部９１３に、あらかじめインストールしておくこともできる。
【０３９１】
＜補足＞
本技術の実施の形態は、上述した実施の形態に限定されるものではなく、本技術の要旨を逸脱しない範囲において種々の変更が可能である。
【０３９２】
例えば、本技術は、装置またはシステムを構成するあらゆる構成、例えば、システムLSI（Large Scale Integration）等としてのプロセッサ、複数のプロセッサ等を用いるモジュール、複数のモジュール等を用いるユニット、ユニットにさらにその他の機能を付加したセット等（すなわち、装置の一部の構成）として実施することもできる。
【０３９３】
なお、本明細書において、システムとは、複数の構成要素（装置、モジュール（部品）等）の集合を意味し、全ての構成要素が同一筐体中にあるか否かは問わない。したがって、別個の筐体に収納され、ネットワークを介して接続されている複数の装置、および、１つの筐体の中に複数のモジュールが収納されている１つの装置は、いずれも、システムである。
【０３９４】
また、上述した処理部は、その処理部について説明した機能を有するようにすれば、どのような構成により実現するようにしてもよい。例えば、処理部が、任意の回路、LSI、システムLSI、プロセッサ、モジュール、ユニット、セット、デバイス、装置、またはシステム等により構成されるようにしてもよい。また、それらを複数組み合わせるようにしてもよい。例えば、複数の回路、複数のプロセッサ等のように同じ種類の構成を組み合わせるようにしてもよいし、回路とLSI等のように異なる種類の構成を組み合わせるようにしてもよい。
【０３９５】
また、例えば、１つの装置（または処理部）として説明した構成を分割し、複数の装置（または処理部）として構成するようにしてもよい。逆に、以上において複数の装置（または処理部）として説明した構成をまとめて１つの装置（または処理部）として構成されるようにしてもよい。また、各装置（または各処理部）の構成に上述した以外の構成を付加するようにしてももちろんよい。さらに、システム全体としての構成や動作が実質的に同じであれば、ある装置（または処理部）の構成の一部を他の装置（または他の処理部）の構成に含めるようにしてもよい。
【０３９６】
また、例えば、本技術は、１つの機能を、ネットワークを介して複数の装置で分担、共同して処理するクラウドコンピューティングの構成をとることができる。
【０３９７】
また、例えば、上述したプログラムは、任意の装置において実行することができる。その場合、その装置が、必要な機能（機能ブロック等）を有し、必要な情報を得ることができるようにすればよい。
【０３９８】
また、例えば、上述のフローチャートで説明した各ステップは、１つの装置で実行する他、複数の装置で分担して実行することができる。さらに、１つのステップに複数の処理が含まれる場合には、その１つのステップに含まれる複数の処理は、１つの装置で実行する他、複数の装置で分担して実行することができる。換言するに、１つのステップに含まれる複数の処理を、複数のステップの処理として実行することもできる。逆に、複数のステップとして説明した処理を１つのステップとしてまとめて実行することもできる。
【０３９９】
コンピュータが実行するプログラムは、プログラムを記述するステップの処理が、本明細書で説明する順序に沿って時系列に実行されるようにしても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで個別に実行されるようにしても良い。つまり、矛盾が生じない限り、各ステップの処理が上述した順序と異なる順序で実行されるようにしてもよい。さらに、このプログラムを記述するステップの処理が、他のプログラムの処理と並列に実行されるようにしても良いし、他のプログラムの処理と組み合わせて実行されるようにしても良い。
【０４００】
本明細書において複数説明した本技術は、矛盾が生じない限り、それぞれ独立に単体で実施することができる。もちろん、任意の複数の本技術を併用して実施することもできる。例えば、いずれかの実施の形態において説明した本技術の一部または全部を、他の実施の形態において説明した本技術の一部または全部と組み合わせて実施することもできる。また、上述した任意の本技術の一部または全部を、上述していない他の技術と併用して実施することもできる。
【０４０１】
なお、本技術は以下のような構成も取ることができる。
（１）  OctreeパタンのデータであるOctreeパタンデータを符号化し、前記Octreeパタンの、前記Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報を含むビットストリームを生成する符号化部
を備える情報処理装置。
（２）  前記深さ制御情報は、前記Octreeパタンの前記最下位レベルよりも上位のレベルの前記深さ制御情報に対応する特定のノードが葉ノードである、ことを示す所定のビット列である
（１）に記載の情報処理装置。
（３）  前記所定のビット列は、前記Octreeパタンデータにおいて、前記Octreeパタンの前記最下位レベルよりも上位のレベルのノードに設定されており、前記所定のビット列が設定された前記ノードが葉ノードであることを示すビットパタンを有し、
前記符号化部は、前記Octreeパタンの前記最下位レベルよりも上位のレベルの葉ノードに前記所定のビット列が設定された前記Octreeパタンデータを符号化して前記ビットストリームを生成するように構成される
（２）に記載の情報処理装置。
（４）  前記所定のビット列の前記ビットパタンは、前記Octreeパタンの葉ノードでないノードに設定されるビット列には用いられないビットパタンである
（３）に記載の情報処理装置。
（５）  前記ビットパタンは、「00000000」である
（４）に記載の情報処理装置。
（６）  前記Octreeパタンの前記最下位レベルと異なるレベルの所望のノードに前記所定のビット列を設定する設定部をさらに備え、
前記符号化部は、前記設定部が設定した前記所定のビット列を含む前記Octreeパタンデータを符号化して前記ビットストリームを生成するように構成される
（３）乃至（５）のいずれかに記載の情報処理装置。
（７）  前記設定部は、ポイントクラウドデータを量子化したボクセルデータをOctree符号化して前記Octreeパタンを生成する際に、前記Octreeパタンの前記最下位レベルよりも上位のレベルの所望のノードを葉ノードとするようにし、前記ビット列を設定する
（６）に記載の情報処理装置。
（８）  前記設定部は、前記Octreeパタンデータにおいて、前記Octreeパタンの前記最下位レベルよりも上位のレベルの所望のノードを葉ノード化し、前記ビット列を設定する
（６）に記載の情報処理装置。
（９）  前記深さ制御情報は、前記ビットストリームにおいて、前記Octreeパタンの前記最下位レベルよりも上位のレベルの前記深さ制御情報に対応する特定のノードが葉ノードであるかを示す所定のフラグ情報である
（１）乃至（８）のいずれかに記載の情報処理装置。
（１０）  前記符号化部は、前記ビットストリームの、前記Octreeパタンの前記最下位レベルよりも上位のレベルの葉ノードに対応する位置に、前記位置に対応するノードが葉ノードであるかを示す前記所定のフラグ情報を挿入する
（９）に記載の情報処理装置。
（１１）  前記Octreeパタンの前記最下位レベルと異なるレベルにおいて、葉ノードとするノードを特定する特定部をさらに備え、
前記符号化部は、前記ビットストリームの、前記特定部により特定された前記ノードに対応する位置に前記所定のフラグ情報を挿入するように構成される
（１０）に記載の情報処理装置。
（１２）  前記特定部は、ポイントクラウドデータを量子化したボクセルデータをOctree符号化して前記Octreeパタンを生成する際に、前記Octreeパタンの前記最下位レベルよりも上位のレベルの所望のノードを葉ノードとするようにし、前記所望のノードを葉ノードとするノードとして特定する
（１１）に記載の情報処理装置。
（１３）  前記特定部は、前記Octreeパタンデータにおいて、前記Octreeパタンの前記最下位レベルよりも上位のレベルの所望のノードを葉ノード化し、前記所望のノードを葉ノードとするノードとして特定する
（１１）に記載の情報処理装置。
（１４）  前記深さ制御情報は、前記Octreeパタンの前記最下位レベルの前記深さ制御情報に対応する特定のノードに対する子孫ノードの追加に関する追加情報である
（１）乃至（１３）のいずれかに記載の情報処理装置。
（１５）  前記符号化部は、前記ビットストリームの、前記Octreeパタンの前記最下位レベルの前記子孫ノードを追加するノードに対応する位置に、前記追加情報を挿入する
（１４）に記載の情報処理装置。
（１６）  前記追加情報は、前記ビットストリームの前記追加情報が挿入された前記位置に対応するノードがさらに分割されるかを示す所定のフラグ情報を含む
（１５）に記載の情報処理装置。
（１７）  前記追加情報は、追加する前記子孫ノードの深さに関する情報をさらに含む
（１６）に記載の情報処理装置。
（１８）  前記追加情報を生成する生成部をさらに備え、
前記符号化部は、前記生成部により生成された前記追加情報を、前記ビットストリームの、前記Octreeパタンの前記最下位レベルの前記子孫ノードを追加するノードに対応する位置に挿入する
（１４）乃至（１７）のいずれかに記載の情報処理装置。
（１９）  OctreeパタンのデータであるOctreeパタンデータを符号化し、前記Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報を含むビットストリームを生成する
情報処理方法。
【０４０２】
（２１）  ビットストリームを復号し、Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報に基づいて、前記最下位レベルと異なるレベルの前記葉ノードを含む前記Octreeパタンを構築する復号部
を備える情報処理装置。
（２２）  前記深さ制御情報は、前記Octreeパタンの前記最下位レベルよりも上位のレベルの前記深さ制御情報に対応する特定のノードが葉ノードである、ことを示す所定のビット列である
（２１）に記載の情報処理装置。
（２３）  前記所定のビット列は、前記Octreeパタンの前記最下位レベルよりも上位のレベルの葉ノードに設定されており、前記所定のビット列が設定された前記ノードが葉ノードであることを示すビットパタンを有する
（２２）に記載の情報処理装置。
（２４）  前記所定のビット列の前記ビットパタンは、前記Octreeパタンの葉ノードでないノードに設定されるビット列には用いられないビットパタンである
（２３）に記載の情報処理装置。
（２５）  前記ビットパタンは、「00000000」である
（２４）に記載の情報処理装置。
（２６）  前記深さ制御情報は、前記ビットストリームにおいて、前記Octreeパタンの前記最下位レベルよりも上位のレベルの前記深さ制御情報に対応する特定のノードが、葉ノードであるかを示す所定のフラグ情報である
（２１）乃至（２５）のいずれかに記載の情報処理装置。
（２７）  前記所定のフラグ情報は、前記ビットストリームの、前記Octreeパタンの前記最下位レベルよりも上位のレベルの葉ノードに対応する位置に挿入されており、前記位置に対応するノードが葉ノードであるかを示す
（２６）に記載の情報処理装置。
（２８）  前記ビットストリームに含まれる前記所定のフラグ情報を検出する検出部をさらに備え、
前記復号部は、前記検出部により検出された前記所定のフラグ情報に基づいて、前記Octreeパタンを構築するように構成される
（２７）に記載の情報処理装置。
（２９）  前記深さ制御情報は、前記Octreeパタンの前記最下位レベルの前記深さ制御情報に対応する特定のノードに対する子孫ノードの追加に関する追加情報である
（２１）乃至（２８）のいずれかに記載の情報処理装置。
（３０）  前記追加情報は、前記ビットストリームの、前記Octreeパタンの前記最下位レベルの前記子孫ノードを追加するノードに対応する位置に挿入されている
（２９）に記載の情報処理装置。
（３１）  前記追加情報は、前記ビットストリームの前記追加情報が挿入された前記位置に対応するノードがさらに分割されるかを示す所定のフラグ情報を含む
（３０）に記載の情報処理装置。
（３２）  前記追加情報は、追加する前記子孫ノードの深さに関する情報をさらに含む
（３１）に記載の情報処理装置。
（３３）  前記ビットストリームに含まれる前記追加情報を検出する検出部をさらに備え、
前記復号部は、前記検出部により検出された前記追加情報に基づいて、前記Octreeパタンの前記最下位レベルのノードに、前記追加情報に応じた子孫ノードを追加するように構成される
（３０）乃至（３２）のいずれかに記載の情報処理装置。
（３４）  ビットストリームを復号し、Octreeパタンの深さを指定する情報に基づく最下位レベルと異なるレベルに葉ノードが形成されることを示す深さ制御情報に基づいて、前記最下位レベルと異なるレベルの前記葉ノードを含む前記Octreeパタンを構築する
情報処理方法。
【符号の説明】
【０４０３】
１００  符号化装置，  １０１  制御部，  １１１  前処理部，  １１２  バウンディングボックス設定部，  １１３  ボクセル設定部，  １１４  符号化部，  ２２１  Octree符号化部，  ２２２  ２値化部，  ２２３  可逆符号化部，  ２３１  Octree深度制御部，  ２３２  Octree構成部，  ２４１  Octree構成部，  ２４２  Octree深度制御部，  ２５０  復号装置，  ２６１  復号部，  ２６２  ポイントクラウド化処理部，  ２７１  可逆復号部，  ２７２  終端検出部，  ２７３  多値化部，  ２７４  ジオメトリ再構成部，  ３２１  Octree符号化部，  ３２２  ２値化部，  ３２３  可逆符号化部，  ３３１  Octree深度制御部，  ３３２  Octree構成部，  ３４１  Octree構成部，  ３４２  Octree深度制御部，  ３７１  終端検出部，  ３７２  可逆復号部，  ３７３  多値化部，  ３７４  ジオメトリ再構成部，  ４２１  Octree深度制御部，  ４２２  追加情報生成部，  ４２３  Octree符号化部，  ４２４  ２値化部，  ４２５  可逆符号化部，  ４３１  Octree構成部，  ４７１  可逆復号部，  ４７２  追加情報検出部，  ４７３  多値化部，  ４７４  再構成制御部，  ４７５  ジオメトリ再構成部，  ９００  コンピュータ
【図１】
2019069711.tif 000003
【図２】
2019069711.tif 000004
【図３】
2019069711.tif 000005
【図４】
2019069711.tif 000006
【図５】
2019069711.tif 000007
【図６】
2019069711.tif 000008
【図７】
2019069711.tif 000009
【図８】
2019069711.tif 000010
【図９】
2019069711.tif 000011
【図１０】
2019069711.tif 000012
【図１１】
2019069711.tif 000013
【図１２】
2019069711.tif 000014
【図１３】
2019069711.tif 000015
【図１４】
2019069711.tif 000016
【図１５】
2019069711.tif 000017
【図１６】
2019069711.tif 000018
【図１７】
2019069711.tif 000019
【図１８】
2019069711.tif 000020
【図１９】
2019069711.tif 000021
【図２０】
2019069711.tif 000022
【図２１】
2019069711.tif 000023
【図２２】
2019069711.tif 000024
【図２３】
2019069711.tif 000025
【図２４】
2019069711.tif 000026
【図２５】
2019069711.tif 000027
【図２６】
2019069711.tif 000028
【図２７】
2019069711.tif 000029
【図２８】
2019069711.tif 000030
【図２９】
2019069711.tif 000031
【国際調査報告】
2019069711.tif 000032
2019069711.tif 000033
2019069711.tif 000034