JP2017126890A

JP2017126890A - 符号化装置及びその制御方法

Info

Publication number: JP2017126890A
Application number: JP2016005380A
Authority: JP
Inventors: 秀往松井; Hideyuki Matsui
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 2016-01-14
Filing date: 2016-01-14
Publication date: 2017-07-20
Anticipated expiration: 2036-01-14
Also published as: JP6826368B2

Abstract

【課題】Ｎ次元空間の点群を高い圧縮率で符号化する。【解決手段】Ｎ次元座標空間における符号化対象の点群を内包する初期ブロックを設定する設定部と、初期ブロックを複数のブロックに分割し、分割して得られた分割ブロックそれぞれに対して再帰的に分割を繰り返すことで、初期ブロックを最上位層とする木構造のデータを生成する木構造生成部と、木構造のデータを符号化する木構造符号化部と、木構造の着目ブロック内の点の位置を、当該着目ブロック内の空間を単位に符号化するブロック内符号化部と、木構造符号化部、及び、ブロック内符号化部で生成された符号化データを、点群の座標情報の符号化データとして出力する出力部とを有する。【選択図】図１

Description

本発明はＮ次元空間の点群の符号化技術に関するものである。

従来から、八分木を利用した３Ｄ点群の符号化技術が知られている。まず非特許文献１で開示されている３Ｄ点群の位置情報（各点のｘｙｚ座標）を符号化する方法について説明する。非特許文献１では３Ｄ点群を八分木データとブロック内点群データにより符号化する。八分木データの生成ではまず、３Ｄ点群を内包する直方体（以下、ブロック）を定義し、そのブロックのｘ、ｙ、ｚ軸の３辺をそれぞれ２分割して、８つのブロックに分割する。そして、分割後の１つのブロックに着目したとき、その着目ブロック内に点が存在する場合は再帰的に、その着目ブロックをブロック分割を繰り返す。この再帰的なブロック分割は事前に定めた階層で停止する。各ブロックに点があるか無いかを示す八分木データは、バイナリのフラグとして出力する。八分木データにより、点がある領域は最低位（細かい）の階層までブロック分割されており、また、最低位階層の各ブロックに点が存在するか否かの情報が判断できる。そして、ブロック内の点群データとして、各ブロック内の点の数と、ブロック内の各点がブロック内のどこにあるかを示すブロック内座標データを出力する。これにより３Ｄ点群の座標を符号化する。

非特許文献１の方法ではブロック分割は、全てブロック分割を固定階層で打ち切る。これに対し、３次元体積データの符号化において適応的にブロック分割を打ち切る技術を開示している文献として、特許文献１があげられる。この特許文献１では、ブロック分割の打ち切りを適応階層にすることで３次元体積データの圧縮率の向上を達成している。

特許第４７５９２９１号公報

Real-time Compression of Point Cloud Streams, 2012 IEEE International Conference on Robotics and Automation RiverCentre, Saint Paul, Minnesota, USA, May 14-18, 2012

非特許文献１に記載の固定階層ブロック分割は、特許文献１に記載の適応階層ブロック分割に比べて、圧縮率が低いという課題がある。その理由を以下に示す。八分木データとブロック内点群データによる３Ｄ点群の符号化では、ブロック内の点数が多い時はブロック分割を行うと１点当たりのブロック内座標データが小さくなるため、データ量を削減できる。しかし、ブロック内の点数が少ない時はブロック分割の有無を示す八分木データのデータ量の方が大きくなる。従って、圧縮率の観点でみると最適な打ち切り階層はブロック毎に異なるため、固定階層分割では圧縮率が低くなってしまう。

一方、適応階層ブロック分割で出力した３Ｄ点群の場合は、八分木データの上位階層のデータを復号するプログレッシブ復号の際の点の粗密が領域毎に異なってしまうという問題がある。固定階層ブロック分割の八分木データでは、固定階層以上の階層での点が存在するブロックについてはどれも同じ階層のデータを復号できる。従ってプログレッシブ復号時に、点を含むブロックについては１つの代表点（ブロックの中心など）を表示するようなレンダリングを行った場合には、点を等間隔にレンダリングすることができる。一方で、適応階層ブロック分割のプログレッシブ復号では、ブロックサイズが異なるため、大きなブロックでは広い領域に対して１つの代表点が表示され、領域に応じて点の粗密が異なってしまう。

本発明は従来技術がもつ上記の課題を解決することを目的とするものである。そして、本発明は、Ｎ次元空間の点群を、木構造による符号化を用いながら高い圧縮率で符号化を行う技術を提供する。

この課題を解決するため、例えば本発明の符号化装置は以下の構成を備える。すなわち、
Ｎ次元座標空間における点群の座標情報を符号化する符号化装置であって、
基準階層の深さを設定する設定手段と、
Ｎ次元空間を分割する木構造のブロックを生成する木構造生成手段と、
前記木構造のデータを符号化する木構造符号化手段と、
前記木構造の着目ブロック内の点の位置を、当該着目ブロック内の空間を単位に符号化するブロック内符号化手段と、
前記木構造符号化手段、及び、前記ブロック内符号化手段で生成された符号化データを含む情報を、前記点群の座標情報の符号化データとして出力する出力手段とを有し、
前記木構造生成手段で生成される木構造が
（１）基準階層より上のブロックは、そのブロック内に３Ｄ点が含まれる限り必ず分割されている、
（２）基準階層以下のブロックについては分割するか否かが適応的に切り替わっていることを特徴とする。

本発明によれば、Ｎ次元空間の点群を高い圧縮率で符号化することが可能になる。

第１の実施形態の符号データを出力する符号化装置のブロック図。第１の実施形態の符号データを出力する符号化装置のフローチャート。第１の実施形態の処理過程を説明する図。第１の実施形態で出力する符号データの構成を示す図。第１の実施形態で生成する木構造の例を説明する図。第１の実施形態の符号データを復号する復号装置のブロック構成図。第１の実施形態の符号データを復号する復号装置のフローチャート。第２の実施形態で出力する符号データの構成を示す図。第２の実施形態の符号データを出力する符号化装置のフローチャート。第２の実施形態の符号データを復号する復号装置のブロック構成図。第２の実施形態の符号データを復号する復号装置のフローチャート。第３の実施形態の符号データを出力する符号化装置のフローチャート。第３の実施形態の過分割木構造を説明する図。コンピュータのブロック構成図。

以下、添付図面に従って本発明に係る実施形態を詳細に説明する。なお、以下で説明する各実施形態は、本発明を具体的に実施した例を示すもので、特許請求の範囲に記載の構成の具体的な実施形態の１つである。

［第１の実施形態］
第１の実施形態では以下の条件１、条件２を満たす木構造データを生成し、その木構造データを利用した３Ｄ点群の符号化装置を説明する。
条件１：基準階層より上のブロックは、そのブロック内に３Ｄ点が含まれる限り必ず分割されている。
条件２：基準階層以下のブロックについては分割するか否かが適応的に切り替わっている。

上記条件を満たす木構造データを生成する為に、本実施形態では、初期ブロックとして、符号化対象の全ての３Ｄ点群を含む初期ブロックを生成する。次に、着目ブロックに点が含まれる限り、基準階層まで必ずブロック分割を行う。そして、基準階層より下の階層では、ブロック分割を行うか否かを適応的に切り替える。上記処理により、条件１、条件２を満たす、木構造（３Ｄ空間の場合は八分木構造）を生成する。

図１は実施形態における符号化装置のブロック構成図である。以下、同図に従って、本実施形態における装置を構成する各部の処理内容を説明する。符号化装置には３Ｄ点群データを入力する。ここで言う、３Ｄ点群データは、各点がｘ、ｙ、ｚの３座標を持った点の羅列である。各座標は浮動小数点や固定小数点の実数で表現される。また、各点はｘ、ｙ、ｚ座標値以外にも、色情報（ＲＧＢ）や法線ベクトルの情報を付加情報として持っても良い。本実施形態では、説明を単純化するため、各点はｘ、ｙ、ｚの座標値であって、それらは固定小数点で表現されるものとし、尚且つ、座標以外の付加情報は持たないものとして説明する。

設定部１０１は、パラメータとして基準階層を設定する。基準階層は、ユーザが設定しても良いし、一旦設定した場合には特に変更しない限り次回のデフォルト値として利用するために不揮発性メモリ（ＨＤＤ等）に保持するようにしても良い。初期ブロック生成部１０２は、入力された３Ｄ点群の全ての点を内包する立方体を初期ブロック（最上位層のブロック）として生成する。なお、実施形態では、立方体を初期ブロックとする例を説明するが、初期ブロックは直方体であっても構わない。

切替部１０３は、処理対象の着目ブロックについて分割する／しないを判定する。本実施形態では、切替部１０３が、着目ブロック内に少なくとも１つの３Ｄ点が含まれ、かつ、着目ブロックが基準階層より上のブロックである場合には、着目ブロックを必ず分割する。そして、切替部１０３は、着目ブロック内に少なくとも１つの３Ｄ点が含まれ、かつ、着目ブロックが基準階層以下の層に位置する場合には、分割する／しないを適応的に決定していく。なお、切替部１０３は、着目ブロック内に３Ｄ点が含まれない場合には、着目ブロックがどの層に位置しても、その分割は行わない。切替部１０３で着目ブロックについてブロック分割を行うと判定した場合は、分割部１０４は着目ブロックを８分割する。切替部１０３でブロック分割を行わないと判定した場合は、ブロック内座標符号化部１０５により、着目ブロック内にある全ての点に対して、ブロック内の代表座標からの差分座標を計算し、符号化する。

木構造符号化部１０６は、各ブロックの属性を示す木構造のデータを符号化する。各ブロックの属性は、以下の３つのいずれかである。
（１）着目ブロックは３Ｄ点を１つも含まず、分割は行われない（点無し）。
（２）着目ブロックは３Ｄ点を少なくとも１つ含み、分割は行われない（点有り分割無し）
（３）着目ブロックは３Ｄ点を少なくとも１つ含み、分割は行われる（点有り分割有り）。
なお、着目ブロックの属性が「点有り分割無し」の場合、ブロック内座標符号化部１０５によるブロック内符号化が行われることになる。

符号データ出力部１０７では、基準階層の深さ、木構造、ブロック内差分座標を符号化したデータを出力する。ここで、初期ブロック生成部１０２、切替部１０３、分割部１０４は木構造生成部１０８としてまとめることができる。木構造生成部１０８の役割は、設定部１０１で設定した基準階層に基づき、基準階層より上のブロック内に３Ｄ点が１つで含まれる場合、そのブロックを分割し、基準階層以下のブロックについては分割する／しないを適応的に切り替えることである。従って木構造生成部１０８の詳細なブロック構成は、上述の処理ブロック１０２、１０３、１０４以外の構成を取っても構わない。以上で図１の符号化装置の各部の説明を終える。

次に、図２のフローチャートに従って、図１の装置が有する各部の処理の詳細を説明する。なお、以降の「Ｓ」はフローチャートにおけるステップを意味する。まず、符号化装置は、図３（ａ）に示すような、ｘ、ｙ、ｚ座標を持った、符号化対象の点群データを入力する。なお、入力源の種類は問わない。Ｓ２０１にて、設定部１０１は基準階層を設定する。基準階層の設定はパラメータとしてのユーザによる入力に応じて行うものとする。なお、基準階層の設定はそれ以外のどのような方法でも良く、事前にプログラムに固定のパラメータが入っていても良いし、入力された点群の総数を元に基準階層を決めても良い。次いで、Ｓ２０２にて、初期ブロック生成部１０２は、初期ブロックの生成を行う。初期ブロックは図３（ｂ）の例に図示するように、入力された３Ｄ点群を全て内包する立方体のブロックを生成する。符号化効率の観点から、ここで生成する立方体は、全３Ｄ点を内包する最小体積となることが望ましい。

Ｓ２０３にて、切替部１０３は、着目ブロックが基準階層より上の層に位置するか判定し、基準階層より上の階層に位置する場合には、ブロック分割処理を行うものとして決定する。ブロック分割を行うとして決定されると、分割部１０４は着目ブロックの分割処理を行う。なお、着目ブロックが３Ｄ点を１つも含まない場合には、分割部１０４はその分割処理をスキップする。つまり、分割部１０４は、着目ブロックが少なくとも１つの３Ｄ点を含む場合に分割処理を行う。図３（ｃ）に、図３（ｂ）のブロックを八分割した例を示す。ここで示すように、ブロック分割は着目ブロックのｘ、ｙ、ｚ軸の各辺の長さを２分割するように分ける。Ｓ２０３、Ｓ２０４を繰り返すことで、３Ｄ点を内包するブロックは、基準階層まで分割される。この後、処理はＳ２０５へ進む。なお、以降の説明の分割は、基準階層以下の階層についてのものであることに注意されたい。

Ｓ２０５にて、切替部１０３は、着目ブロックを分割するか否かを判定する。切替部１０３は、点群を高圧縮にするという観点に従ってブロック分割をするか否かを判定することが望ましい。既に述べたように、ブロック内の点の数が多い場合は、分割をした方が符号量が小さくなり、点の数が少ない場合は分割をしない方が符号量が小さくなるという特徴がある。そこで、本実施形態では、予め所定の閾値ｎを設定しておき、着目ブロックに含まれる３Ｄ点の数がｎ以上である場合に分割するものとして決定し、ｎ未満の場合には分割しないと判定することとした。

なお、分割する／しないの判定基準は上記に限らない。例えば、着目ブロックを分割した場合としない場合の符号量を推定し、より符号量が小さくなる方を選ぶなどでも構わない。この場合は、３Ｄ点の数で決める場合より高圧縮になることが期待できるが、一方で符号量推定のための演算量が増えることになり、符号化が完了するまでに要する時間が増えてしまうことになる。よって、場合によっては、符号量を優先するか、速度を優先するかをユーザに選択させて、そのいずれかの判定基準に従って分割する／しないを決定しても良い。ここでは、先に説明したように、３Ｄ点の数と閾値との比較で分割判定を行うものとして説明を続ける。

切替部１０３が、Ｓ２０５にて、着目ブロックを分割すると判定した場合は処理をＳ２０６に進め、着目ブロックを分割部１０４に渡し、着目ブロックを８分割させる。ここで行う分割処理はＳ２０４と同様である。つまり、着目ブロックが少なくとも１つの３Ｄ点を含むことを条件に、着目ブロックの分割処理を行う。

また、Ｓ２０５にて、切替部１０３が、着目ブロックを分割しないと判定した場合には、処理をＳ２０７に進め、ブロック内座標符号化部１０５に着目ブロックのブロック内座標符号化を実行させる。ここで、ブロック内座標符号化を説明する。図３（ｄ）は、ブロック内座標符号化を行う対象となった着目ブロックと、その中に含まれる３Ｄ点を示している。実施形態では、着目ブロックの代表座標から各３Ｄ点の座標の差分を符号化する。換言すれば、着目ブロック内の３Ｄ点は、着目ブロックの代表座標を基準とした相対座標として符号化される。本実施形態では、着目ブロックの代表座標は、着目ブロックのｘ、ｙ、ｚの座標が最小となる角の座標とする。よって、着目ブロック内の３Ｄ点の１つである図示の点Ｐ１については、図示の矢印で示されるベクトルがエントロピー符号化されることになる。他の３Ｄ点も同様に符号化する。なお、着目ブロック内の全３Ｄ点の１つを代表座標からのベクトルとして符号化し、残りの３Ｄ点は既に符号化した３Ｄ点の座標との差分ベクトルとして符号化しても構わない。Ｓ２０５からＳ２０７の処理を、Ｓ２０８が全ブロックの分割を終えたと判定するまで繰り返す。そして、全ブロックのブロック内座標符号化を終えると、処理はＳ２０９に進み、木構造符号化部１０６がこれまでの分割処理によって生成された八分木データを符号化する。そして、Ｓ２１０にて、符号化データ出力部１０７は、八分木データの符号化データ、並びに、ブロック内座標符号化データとを予め設定されたデータ構造に配列し、出力する。

このＳ２１０にて出力される符号化データのデータ構造（ファイル構造）の例を示すのが図４である。以下で詳しく説明する。まず先頭のヘッダには、次の情報が含まれる。
（１）初期ブロック（最上位ブロック）の立方体を規定するための情報
（２）八分木データの要素数
（３）基準階層の深さ
ここで、上記（１）の情報は、典型的には、立方体を規定するｘ、ｙ、ｚ軸の各成分の最小の値と、それぞれの最大の値でよい。そして、ヘッダに後続して、基準階層以上の八分木データ、基準階層より下の八分木データ、そしてブロック内点群データが続く。

ここで、八分木データについて図５（ａ）を用いて補足する。図５（ａ）は図２の処理フローにて得た、各ブロックの属性を八分木構造で表したものである。図の凡例にある通り、白丸が「点無し」ブロック、黒丸が「点有り分割有り」ブロック、Ｄと書かれた丸が「点有り分割無し」ブロックである。最上位ブロック（ノード）は、初期ブロックに対応する。そして、最上位ブロックの直下にある８個のブロックは、最上位ブロックを８分割して得られる分割ブロックに相当する。８分割したブロックの並び順は、符号化装置と復号装置との間で共通になっていればよい。

図５（ａ）から、基準階層に達するまでは、点有りのブロックは全て分割されていることが分かる。八分木データは、この各ノードの属性を或る順番に従って羅列したものである。プログレッシブ符号化の観点からは、幅優先順に属性を羅列するのが望ましい。また、各属性には識別可能なコードを割り当てて数値データとして羅列すれば良い。本実施形態では八分木データを可逆のエントロピー符号化して出力する。

八分木データの符号化の一例を図５（ｂ）に基づき説明する。同図は、図５（ａ）の「点無し」ブロックに二進の符号語“０（１ビット）”、「点有り分割有り」ブロックに二進の符号語“１０（２ビット）”、「点有り分割無し」ブロックに二進の符号語“１１（２ビット）”を割り当てた状態を示している。この符号語を、図示の破線で示す幅優先順に並べたデータが、八分木データの符号化データとなる。なお、図示の符号語に、更にバイナリのランレングス符号化や算術符号化を行っても構わない。

最後に、前記八分木データで点有り分割無しになっているブロックに対する、ブロック内の点群データの符号化データが付加される。１つのブロック内の点群データとは、ブロック内にある点の数、及び、Ｓ２０７で符号化したブロック内座標である。ここで、Ｓ２０５で述べた、分割をするか否かを定める閾値ｎについて補足する。本実施形態では高圧縮を達成するためにｎ＝２^N／Ｎで定めるものとする。これは、Ｎ次元の空間を分割した場合に増えるデータ量が２^N個の子ブロック毎に１ビット（もしくは２ビット）であり、また、分割によって減るデータ量は１点当たりブロック内座標がＮビット減るためである。本実施形態ではＮ＝３であるため、ｎ＝３、つまり、ブロック内に３点以上ある場合は分割するものとする。なお、適切なｎの値は各データを圧縮するエントロピー符号化の性能等にも依存するため、上記以外の値をｎに用いても良い。以上で、Ｓ２１０で出力する符号データの説明、及び図２のフローチャートの説明を終える。

次に、図１の符号化装置に対応する復号装置の構成を図６のブロック図を用いて説明する。ここでは図４に示した符号データをプログレッシブ復号可能な復号装置について説明する。ヘッダ解析部６０１では、符号化データファイルのヘッダを解析し、基準階層の深さを含む、ヘッダ情報を読み込む。木構造復号部６０２は、基準階層以上の八分木データ及び、基準階層より下の８分木データの符号化データを読み込む。そして、８分木データをもとに木構造を持つ立方体のブロックを再構築する。ブロック内点群データ復号部６０３は、各ブロック内の点数とブロック内に存在する点の座標を復号し、再構築されたブロックの代表座標に加算することで点群データを復号する。また、点群変換部６０４はプログレッシブ復号する際に用いるブロックであり、木構造復号部６０２で再構築した各ブロックの代表座標を持つ点群に変換する。ここで得られる点群はブロック内点群データ復号部６０３で復号される点群より解像度が低く、点群の大まかな分布を把握するのに使う事が出来る。処理部６０１乃至６０４から構成される復号装置６０５は、低解像度の点群データ、もしくは、点群データが出力され、表示部６０６で表示される。以上で図６の各部の説明を終える。

次に図７を参照して、図６に示した復号装置におけるプログレッシブ復号の処理を説明する。Ｓ７０１にてヘッダ解析部６０１は、符号化データ内のヘッダを解析する。Ｓ７０２では、木構造復号部６０２は、基準階層以上の八分木データの符号化データを読み込んで復号することで、基準階層以上のブロックを再構築する。Ｓ７０３にて、点群変換部６０４は、Ｓ７０２にて得た基準階層かつ、点有りという条件を満たすブロックの代表座標からなる点群を生成する。代表座標は、符号化装置にてブロック内座標を求めるときと同じく、ブロックの中でｘｙｚの各成分が全て最小となる角の座標とする。なお、ブロックの中心座標等の別の点を用いても良い。Ｓ７０４にて、点群変換部６０４は、Ｓ７０３にて生成した低解像度の点群データを表示部６０６に送り、表示する。

Ｓ７０５にて、木構造復号部６０２は、基準階層より下の八分木データの符号化データを復号し、基準階層より下のブロックを構築する。そして、Ｓ７０６にて、ブロック内点群データ復号部６０３は、ブロック内の点数と各点のブロック内座標を復号する。そして、ブロック内点群データ復号部６０３は、Ｓ７０５で復号したブロックの代表座標に、復号して得た各点のブロック内座標を加算することで、点群データを復号する。そして、ブロック内点群データ復号部６０３は、Ｓ７０７にて、その点群を表示部６０６に表示させる。上記フローによりプログレッシブ復号が実現できる。

上記プログレッシブ復号の特徴は、符号化の際に基準階層までブロック分割した符号データを出力することで、プログレッシブ復号で表示する低解像度の点群データの疎密が領域によらず一定になり、見た目が自然な表示が出来る点である。なお、本実施形態では３Ｄ点群を八分木構造を利用して符号化する例を説明したが、図１及び図６で示した符号化装置及び復号装置と同様の構成で、Ｎ次元の点群の２^N分木の符号化／復号にも適用できる。例えば、２Ｄ点群は四分木構造を利用して符号化することも、同様のブロック構成の装置で可能である。

以上で、本実施形態の説明を終える。本実施形態で説明した符号化装置により、プログレッシブ復号時の点の疎密を一定にすることで見た目が自然な表示が可能で、かつ、適応階層で八分木を分割することで高圧縮を達成することができる。以上説明したように本第１の実施形態によれば、プログレッシブ復号時の点の疎密を一定にすることで自然な見た目を保ちながら、３Ｄ点群の座標情報を高い圧縮率で符号化することが可能となる。そして、より一般には、Ｎ次元座標空間の点群を内包するブロックを２^N個のブロックに分割する木構造による符号化において、プログレッシブ復号時の点の疎密を一定にすることで自然な見た目を保ちながら、高い圧縮率で圧縮を行うことが可能になる。

［第１の実施形態の変形例］
図１に示した各部はハードウェアで構成しても良いが、ソフトウェア（コンピュータプログラム）として実装しても良い。この場合、このソフトウェアは、ＰＣ（パーソナルコンピュータ）等、一般のコンピュータのメモリにインストールされることになる。そしてこのコンピュータのＣＰＵがこのインストールされたソフトウェアを実行することで、このコンピュータは、上述の符号化装置の機能を実現することになる。即ち、このコンピュータは、上述の符号化装置に適用することができる。第１の実施形態に係る符号化装置に適用可能なコンピュータのハードウェア構成例について、図１４のブロック図を用いて説明する。

ＣＰＵ１５０１は、ＲＡＭ１５０２やＲＯＭ１５０３に格納されているコンピュータプログラムやデータを用いて、コンピュータ全体の制御を行うと共に、画像処理装置が行うものとして説明した上述の各処理を実行する。ＲＡＭ１５０２は、コンピュータ読み取り可能な記憶媒体の一例である。ＲＡＭ１５０２は、外部記憶装置１５０７や記憶媒体ドライブ１５０５、更にはネットワークインタフェース１５１０からロードされたコンピュータプログラムやデータを一時的に記憶するためのエリアを、有する。更に、ＲＡＭ１５０２は、ＣＰＵ１５０１が各種の処理を実行する際に用いるワークエリアを有する。即ち、ＲＡＭ１５０２は、各種のエリアを適宜提供することができる。ＲＯＭ１５０３は、コンピュータ読み取り可能な記憶媒体の一例であり、コンピュータの設定データや、ブートプログラムなどが格納されている。

キーボード１５０４、マウス１５０５は、コンピュータの操作者が操作することで、各種の指示をＣＰＵ１５０１に対して入力することができる。表示装置１５０６は、ＣＲＴや液晶画面などにより構成されており、ＣＰＵ１５０１による処理結果を画像や文字などでもって表示することができる。

外部記憶装置１５０７は、コンピュータ読み取り／書き込みを行う記憶媒体の一例であり、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置１５０７には、ＯＳ（オペレーティングシステム）や、図１に示した各処理をＣＰＵ１５０１に実現させるためのコンピュータプログラムやデータ等が保存されている。外部記憶装置１５０７に保存されているコンピュータプログラムやデータは、ＣＰＵ１５０１による制御に従って適宜ＲＡＭ１５０２にロードされ、ＣＰＵ１５０１による処理対象となる。

記憶媒体ドライブ１５０８は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されているコンピュータプログラムやデータを読み出し、読み出したコンピュータプログラムやデータを外部記憶装置１５０７やＲＡＭ１５０２に出力する。なお、外部記憶装置１５０７に保存されているものとして説明した情報の一部若しくは全部をこの記憶媒体に記録させておき、この記憶媒体ドライブ１５０８に読み取らせても良い。Ｉ／Ｆ１５０９は、木構造の基準階層等のパラメータ等を入力するインタフェースであり、一例として示すのであればＵＳＢ（Universal Serial Bus）である。１５１０は、上述の各部を繋ぐバスである。

上述構成において、本コンピュータの電源がＯＮになると、ＣＰＵ１５０１はＲＯＭ１５０３に格納されているブートプログラムに従って、外部記憶装置１５０７からＯＳをＲＡＭ１５０２にロードする。この結果、キーボード１５０４、マウス１５０５を介した情報入力操作が可能となり、表示装置１５０６にＧＵＩを表示することが可能となる。ユーザが、キーボード１５０４やマウス１５０５を操作し、外部記憶装置１５０７に格納された、例えばグレー画像量子化用のアプリケーションプログラムの起動指示を入力すると、ＣＰＵ１５０１はこのプログラムをＲＡＭ１５０２にロードし、実行する。これにより、本コンピュータが符号化装置、あるいは復号装置として機能することになる。

なお、ＣＰＵ１５０１が実行する符号化プログラムは、基本的に図１に示す各部に相当する関数を備えることになる。ここで、画像処理結果は外部記憶装置１５０７に保存することになる。また、復号プログラムは図６に示す各部に相当する関数を備えることになる。また、このコンピュータは、以下に説明ずる実施形態に係る符号化装置及び復号装置にも同様に適用可能であることは明らかである。

［第２の実施形態］
本第２の実施形態では、第１の実施形態における、符号データ出力部で出力する符号データの構成を変更し、部分復号可能な符号データを出力する符号化装置を説明する。また、その符号データを部分復号する復号装置についても述べる。

本第２の実施形態における符号化装置は図１に記載の符号化装置と同様の構成を取る。ただし、符号データ出力部１０７が出力するデータの構成が第１の実施形態と異なる。図８を用いて本第２の実施形態で出力する符号データの構成を説明する。図８は第１の実施形態と同じく、図５に示した木構造に分割した３Ｄ点群の符号データのデータ構造（ファイル構造）である。このうち、ヘッダおよび基準階層以上の八分木データは第１の実施形態と同様である。そして、基準階層以上の八分木データに後続するデータ構造が本第２の実施形態の特徴であり、図８に示す様に基準階層にあるブロックを、それぞれ部分ブロックとし、部分ブロック毎に部分復号可能なデータ構成をとる。そのために、各ブロック内のデータを復号するために必要なデータをそれぞれ一か所にまとめ、それらの符号データ内でのアドレスを記述する。これにより、復号時に各部分ブロックの復号に必要なデータのみを読み出して部分復号できるようになる。各部分ブロックを復号するために必要なデータとは、部分ブロック以下の領域の八分木データと、その領域内にある点有り分割無しのブロック対する、ブロック内の点群データ（点の数及びブロック内座標）である。この詳細は既に第１の実施形態にて説明した。

図８に示した符号データを出力するために、本実施形態における符号データ出力部１０７が行う処理手順を図９に示すフローチャートに従って説明する。Ｓ９０１にて、符号データ出力部１０７はヘッダを生成し、出力する。そして、Ｓ９０２にて、符号データ出力部１０７は、基準階層以上の階層の八分木データを出力する。これらの処理はＳ２１０で説明したのと同様である。次にＳ９０３〜Ｓ９０６の処理は部分ブロック毎に行う。まず、Ｓ９０３にて、符号データ出力部１０７は、部分ブロックの先頭アドレスを計算する。図８から分かる様に、最初に符号化する部分ブロックの先頭アドレスは、ヘッダ、基準階層以上の八分木データ、各部分ブロックの符号データ先頭アドレスの羅列の後ろに続くため、それらのデータ量を加算すれば求めることが出来る。ヘッダ、基準階層以上の八分木データのデータ量はＳ９０１、Ｓ９０２で出力済みのため容易に計算できる。各部分ブロックの符号データ先頭アドレスは例えば３２ｂｉｔの自然数で出力すれば良い為、それに部分ブロックの数を掛ければよい。Ｓ９０４にて、符号データ出力部１０７は、部分ブロックデータの所在位置である先頭アドレスを出力する。次のＳ９０５、Ｓ９０６にて、符号データ出力部１０７は、処理対象の部分ブロックを復号する為に必要なデータを出力する。このデータは既に図８の説明で述べた。２つ目の以降の部分ブロックも同様に図８のデータ構成になる様に符号データを出力すれば良い。以上で、図９の説明を終える。ここまでで図８に示す部分復号可能な符号データを出力する符号化装置についての説明を終えた。

図１０は、第２の実施形態における復号装置１００５のブロック構成図である。この復号装置１００５は、符号データを部分復号することが可能な点は第１の実施形態と異なる。図１０におけるヘッダ解析部１００１、木構造復号部１００２、ブロック内点群データ復号部１００３、点群変換部１００４の基本的な処理は、図６のヘッダ解析部６０１、木構造復号部６０２、ブロック内点群データ復号部６０３、点群変換部６０４とほぼ同じである。ただし、本第２の実施形態では、部分復号を可能にするために、復号ブロック設定部１００７と先頭アドレス読み込み部１００８が加わった点、並びに、それに伴い木構造復号部１００２とブロック内点群データ復号部１００３が部分復号に適した処理をする点が異なる。

以下、第２の実施形態の符号化装置の処理手順を、図１１のフローチャートに従って説明する。Ｓ１１０１乃至Ｓ１１０４までは図７のフローチャートの同名の処理と同じである。Ｓ１１０４までが終わった段階で、図８の符号データのうち、ヘッダと基準階層以上の８分木データが読み込まれ、表示部１００６に低解像度点群が表示される。次にＳ１１０５にて、復号ブロック設定部１００７が、基準階層にあるどの部分ブロックを復号するかを設定する。復号対象のブロックは、ユーザが不図示の操作部を操作することで指定するものとする。つまり、表示部１００６から点群を観察するユーザが見たい注視領域を座標として受け取り（以下、注視座標）、注視座標を含む部分ブロックを設定する。注視座標は、例えば表示部が２次元のディスプレイの場合は、ディスプレイの中心に最も近い位置に表示されている低解像度点群データとすれば良い。この他にも注視座標の設定はディスプレイに表示された低解像度点群を見ながらユーザがマウスでクリック指定するといった方法が考えられる。次にＳ１１０６では復号する部分ブロックの符号データの先頭アドレスを受け取り、Ｓ１１０７でその部分ブロックの八分木データを復号し、Ｓ１１０８でその部分ブロックのブロック内点群データの復号をする。そして、Ｓ１１０９では部分ブロックの高解像度の点群データを復号し、Ｓ１１０４で得た低解像度点群と合わせた点群データを表示部に送る。以上で図１０及び図１１の説明を終える。

なお、本第２の実施形態では、図８に示す通り、１つの部分ブロックの復号に必要なデータは、符号データ内の１つの連続した領域にまとめて出力した。しかし、部分ブロックの復号に必要なデータを複数箇所に分けて出力しても良い。ただし、その場合はその部分ブロックの復号に必要なデータの位置を特定可能なアドレスを複数出力する必要がある。

以上で、本第２の実施形態における符号化装置及び復号装置の説明を終える。本第２の実施形態で説明した符号化装置により、第１の実施形態同様、プログレッシブ復号時の点群の粗密が一定な表示が可能で、かつ、適応階層で八分木を分割することで高圧縮を達成する符号データが出力できる。また第１の実施形態にはなかった特徴として、部分ブロックの復号に必要なデータのアドレスを符号データに含めることで、基準階層にある部分ブロック単位で部分復号が可能な符号データの出力及び復号が可能である。

［第３の実施形態］
本第３の実施形態では木構造の生成に係る処理が第１の実施形態と異なる例を説明する。本第３の実施形態の装置構成は、図１と同じである。異なる点は、木構造生成部１０８の処理内容である。

木構造生成部１０８の役割が、第１の実施形態で述べた条件１、条件２を満たす木構造データを生成する点は第１の実施形態と同様である
第１の実施形態における木構造生成部１０８は、再帰的分割によって上記条件１、条件２を満たす木構造を生成する。これに対し、本第３の実施形態の木構造生成部１０８は、再帰的統合によって上記条件１、条件２を満たす木構造を生成する。具体的には以下のステップＡ、Ｂに従って木構造データを生成する。
Ａ：設定部１０１で設定した基準階層よりも下位に位置する、予め設定された下限層まで木構造データを生成する。
Ｂ：同じブロックを上位層に持つ８個のブロックが、基準階層よりも下位層に位置し、かつ、これら８個のブロックに内包される点の総数が予め設定された閾値に満たない場合、これら８個のブロックを上位層の１個のブロックとして統合する。

本第３の実施形態における木構造生成部１０８が行う処理手順を図１２のフローチャートに従って詳細に説明する。Ｓ１２０１、Ｓ１２０６、Ｓ１２０８、Ｓ１２０９で行う処理は、図２の同名の処理と同様である。Ｓ１２０２にて、木構造生成部１０８は木構造の初期状態として、過分割木構造を生成する。過分割木構造とは、図１３に示すように、内部に点を含む全てのブロックが最低位階層（下限層）まで分割されている木構造である。最低位階層は基準階層より深い階層であればどの階層でも良い。最低位階層と基準階層の深さに差が大きいほど、最終的に生成する木構造の自由度が上がるため圧縮率は向上すると考えられるが、その分処理時間は多くかかる。ここでは基準階層より１階層低い位置を最低位階層として設定するものとする。最低位階層の設定方法としては他にも、入力された３Ｄ点群の全点群数に基づき、最低位階層の各ブロックに点が平均して１つ入る様に定める方法などが考えられる。この方法は最低位階層を事前に定めておくのに比べて圧縮対象の３Ｄ点群に適した最低位階層を設定できるため、少ない処理時間の割には高圧縮となる可能性が高い。

Ｓ１２０３乃至Ｓ１２０５は、同一の親ブロックを持つ８つのブロックに対する適応的ブロック統合処理である。Ｓ１２０３ではまず処理対象の基準階層まで統合したかを判定し、基準階層に達した場合はＳ１２０６に進む。達していない場合はＳ１２０４で対象ブロックを統合するかを判定する。判定の基準はブロックを親ブロックに統合した場合に、ブロック内の点数が閾値以下であれば統合するという基準で判定する。第１の実施形態では、注目ブロックに含まれる３Ｄ点の数が閾値以上の場合に分割したが、本第３の実施形態では、この逆である。なお、この統合の基準はそれ以外の基準を用いてもよい。例えば統合する場合としない場合の符号量を比較し、より符号量が小さくなる方を選ぶ方法などが考えられる。

Ｓ１２０５では８つの子ブロックを１つの親ブロックに統合する。Ｓ１２０４で統合しないと判定した場合はＳ１２０６に進む。Ｓ１２０６では図２の同名の処理と同じく、統合しないことが決まったブロックに対して各点のブロック内座標を符号化する。Ｓ１２０７で全ブロックの統合を終えたかを判定し、全て終えた場合はＳ１２０８へ進む。以降は図２の処理フローと同様である。上記の処理を終えると、第１の実施形態と同様、基準階層より上のブロックは必ず分割され、基準階層以下のブロックについては分割するか否かが適応的に切り替わっている木構造を生成することができる。以上で本第３の実施形態の符号化装置の説明を終える。

上記符号化装置で出力される符号データは、第１の実施形態と同様、図６に示す復号装置で復号できる。第１の実施形態では大きな初期ブロックを分割して木構造データを生成したのに対し、本第３の実施形態では、予め設定した小さな過分割ブロックの木構造データを生成し、統合処理を行うことで木構造データを生成した。ただし、分割と統合の両方を組み合わせて行うことも容易に可能である。以上で本第３の実施形態の説明を終える。本第３の実施形態で説明した符号化装置により、第１の実施形態同様、プログレッシブ復号時の点群の粗密が一定な表示が可能で、かつ、木構造の階層が適応的に切り替わることで高圧縮な符号データが得られる。

（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。

１０１…設定部、１０２…初期ブロック生成部、１０３…切替部、１０４…分割部、１０５…ブロック内座標符号化部、１０６…木構造符号化部、１０７…符号データ出力部、１０８…木構造生成部

Claims

Ｎ次元座標空間における点群の座標情報を符号化する符号化装置であって、
基準階層の深さを設定する設定手段と、
Ｎ次元空間を分割する木構造のブロックを生成する木構造生成手段と、
前記木構造のデータを符号化する木構造符号化手段と、
前記木構造の着目ブロック内の点の位置を、当該着目ブロック内の空間を単位に符号化するブロック内符号化手段と、
前記木構造符号化手段、及び、前記ブロック内符号化手段で生成された符号化データを含む情報を、前記点群の座標情報の符号化データとして出力する出力手段とを有し、
前記木構造生成手段で生成される木構造が
（１）基準階層より上のブロックは、そのブロック内に３Ｄ点が含まれる限り必ず分割されている、
（２）基準階層以下のブロックについては分割するか否かが適応的に切り替わっている、
ことを特徴とする符号化装置。
前記木構造生成手段は、
Ｎ次元座標空間における符号化対象の点群を内包する初期ブロックを生成する初期ブロック生成手段と、
前記初期ブロックを複数のブロックに分割し、分割して得られた分割ブロックそれぞれに対して再帰的に分割を繰り返すことで、前記初期ブロックを最上位層とする木構造のデータを生成する分割手段とを有し、
前記分割手段は、
（１）着目ブロックが、予め設定された基準階層以上の階層に位置する場合には、前記着目ブロック内に少なくとも１つの点が存在する限り当該着目ブロックの分割を行い、
（２）着目ブロックが予め設定された階層より下の階層に位置する場合には、当該着目ブロック内に点が存在しない、あるいは、点が存在しても所定の条件を満たさない場合に、当該着目ブロックの分割を停止し、
（３）着目ブロックが予め設定された階層より下の階層に位置する場合で、当該着目ブロックが前記所定の条件を満たす場合に、当該着目ブロックの分割を行う
ことを特徴とする請求項１に記載の符号化装置。
前記木構造生成手段は、
着目ブロックの属性として、
（１）点を含まない、
（２）点を含み、分割されない、
（３）点を含み、分割される、
のいずれか１つの属性を割り当てる
ことを特徴とする請求項２に記載の符号化装置。
前記分割手段は、１つのブロックを、Ｎ次元の各軸に沿って２分割することで、２^N個のブロックに分割することを特徴とする請求項２または３に記載の符号化装置。
前記所定の条件は、
着目ブロック内に存在する点の数が予め設定された閾値以上である
とすることを特徴とする請求項２乃至４のいずれか１項に記載の符号化装置。
木構造生成手段は、
前記基準階層よりも下位層であって、予め設定された階層までの木構造を生成する過分割木構造生成手段と、
同じブロックを上位層に持つ複数のブロックが、前記基準階層よりも下位層に位置し、かつ、所定の条件を満たさない場合に、前記複数のブロックを上位層のブロックとして統合する統合手段とを有する
ことを特徴とする請求項１に記載の符号化装置。
前記所定の条件は、
前記複数のブロックに内包される点の総数が予め設定された閾値以上である
ことを特徴とする請求項６に記載の符号化装置。
前記ブロック内符号化手段は、
着目ブロック内に存在する点の数と、各点の座標を当該着目ブロックの予め設定された角からの各点に向かうベクトルを示すデータを符号化データとして生成する
ことを特徴とする請求項１乃至６のいずれか１項に記載の符号化装置。
前記出力手段は、基準階層のブロック毎に、当該ブロックの点群に必要な符号化データの所在位置を示す情報を更に出力する
ことを特徴とする請求項１乃至８のいずれか１項に記載の符号化装置。
コンピュータが読み込み実行することで、前記コンピュータに、請求項１乃至９のいずれか１項に記載の装置が有する各手段として機能させるためのプログラム。
請求項１０に記載のプログラムを格納したことを特徴とするコンピュータが読み取り可能な記憶媒体。
Ｎ次元座標空間における点群の座標情報を符号化する符号化装置の制御方法であって、
設定手段が、基準階層の深さを設定する設定工程と、
木構造生成手段が、Ｎ次元空間を分割する木構造のブロックを生成する木構造生成工程と、
木構造符号化手段が、前記木構造のデータを符号化する木構造符号化工程と、
ブロック内符号化手段が、前記木構造の着目ブロック内の点の位置を、当該着目ブロック内の空間を単位に符号化するブロック内符号化工程と、
出力手段が、前記木構造符号化工程、及び、前記ブロック内符号化工程で生成された符号化データを含む情報を、前記点群の座標情報の符号化データとして出力する出力工程とを有し、
前記木構造生成工程で生成される木構造が
（１）基準階層より上のブロックは、そのブロック内に３Ｄ点が含まれる限り必ず分割されている。
（２）基準階層以下のブロックについては分割するか否かが適応的に切り替わっている。
ことを特徴とする符号化装置の制御方法。