図面 (/)

技術 符号化装置及びその制御方法

出願人 キヤノン株式会社
発明者 松井秀往
出願日 2016年1月14日 (5年3ヶ月経過) 出願番号 2016-005380
公開日 2017年7月20日 (3年9ヶ月経過) 公開番号 2017-126890
状態 特許登録済
技術分野 イメージ処理・作成 TV信号の圧縮,符号化方式
主要キーワード 最上位ブロック 初期ブロック 注視座標 八分木 差分座標 過分割 分割判定 親ブロック
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年7月20日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (15)

課題

次元空間の点群を高い圧縮率で符号化する。

解決手段

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

概要

背景

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

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

概要

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

目的

本発明は、N次元空間の点群を、木構造による符号化を用いながら高い圧縮率で符号化を行う技術を提供する

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

次元座標空間における点群座標情報を符号化する符号化装置であって、基準階層の深さを設定する設定手段と、N次元空間を分割する木構造ブロックを生成する木構造生成手段と、前記木構造のデータを符号化する木構造符号化手段と、前記木構造の着目ブロック内の点の位置を、当該着目ブロック内の空間を単位に符号化するブロック内符号化手段と、前記木構造符号化手段、及び、前記ブロック内符号化手段で生成された符号化データを含む情報を、前記点群の座標情報の符号化データとして出力する出力手段とを有し、前記木構造生成手段で生成される木構造が(1)基準階層より上のブロックは、そのブロック内に3D点が含まれる限り必ず分割されている、(2)基準階層以下のブロックについては分割するか否かが適応的に切り替わっている、ことを特徴とする符号化装置。

請求項2

前記木構造生成手段は、N次元座標空間における符号化対象の点群を内包する初期ブロックを生成する初期ブロック生成手段と、前記初期ブロックを複数のブロックに分割し、分割して得られた分割ブロックそれぞれに対して再帰的に分割を繰り返すことで、前記初期ブロックを最上位層とする木構造のデータを生成する分割手段とを有し、前記分割手段は、(1)着目ブロックが、予め設定された基準階層以上の階層に位置する場合には、前記着目ブロック内に少なくとも1つの点が存在する限り当該着目ブロックの分割を行い、(2)着目ブロックが予め設定された階層より下の階層に位置する場合には、当該着目ブロック内に点が存在しない、あるいは、点が存在しても所定の条件を満たさない場合に、当該着目ブロックの分割を停止し、(3)着目ブロックが予め設定された階層より下の階層に位置する場合で、当該着目ブロックが前記所定の条件を満たす場合に、当該着目ブロックの分割を行うことを特徴とする請求項1に記載の符号化装置。

請求項3

前記木構造生成手段は、着目ブロックの属性として、(1)点を含まない、(2)点を含み、分割されない、(3)点を含み、分割される、のいずれか1つの属性を割り当てることを特徴とする請求項2に記載の符号化装置。

請求項4

前記分割手段は、1つのブロックを、N次元の各軸に沿って2分割することで、2N個のブロックに分割することを特徴とする請求項2または3に記載の符号化装置。

請求項5

前記所定の条件は、着目ブロック内に存在する点の数が予め設定された閾値以上であるとすることを特徴とする請求項2乃至4のいずれか1項に記載の符号化装置。

請求項6

木構造生成手段は、前記基準階層よりも下位層であって、予め設定された階層までの木構造を生成する過分割木構造生成手段と、同じブロックを上位層に持つ複数のブロックが、前記基準階層よりも下位層に位置し、かつ、所定の条件を満たさない場合に、前記複数のブロックを上位層のブロックとして統合する統合手段とを有することを特徴とする請求項1に記載の符号化装置。

請求項7

前記所定の条件は、前記複数のブロックに内包される点の総数が予め設定された閾値以上であることを特徴とする請求項6に記載の符号化装置。

請求項8

前記ブロック内符号化手段は、着目ブロック内に存在する点の数と、各点の座標を当該着目ブロックの予め設定された角からの各点に向かうベクトルを示すデータを符号化データとして生成することを特徴とする請求項1乃至6のいずれか1項に記載の符号化装置。

請求項9

前記出力手段は、基準階層のブロック毎に、当該ブロックの点群に必要な符号化データの所在位置を示す情報を更に出力することを特徴とする請求項1乃至8のいずれか1項に記載の符号化装置。

請求項10

コンピュータが読み込み実行することで、前記コンピュータに、請求項1乃至9のいずれか1項に記載の装置が有する各手段として機能させるためのプログラム

請求項11

請求項10に記載のプログラムを格納したことを特徴とするコンピュータが読み取り可能な記憶媒体

請求項12

N次元座標空間における点群の座標情報を符号化する符号化装置の制御方法であって、設定手段が、基準階層の深さを設定する設定工程と、木構造生成手段が、N次元空間を分割する木構造のブロックを生成する木構造生成工程と、木構造符号化手段が、前記木構造のデータを符号化する木構造符号化工程と、ブロック内符号化手段が、前記木構造の着目ブロック内の点の位置を、当該着目ブロック内の空間を単位に符号化するブロック内符号化工程と、出力手段が、前記木構造符号化工程、及び、前記ブロック内符号化工程で生成された符号化データを含む情報を、前記点群の座標情報の符号化データとして出力する出力工程とを有し、前記木構造生成工程で生成される木構造が(1)基準階層より上のブロックは、そのブロック内に3D点が含まれる限り必ず分割されている。(2)基準階層以下のブロックについては分割するか否かが適応的に切り替わっている。ことを特徴とする符号化装置の制御方法。

技術分野

0001

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

背景技術

0002

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

0003

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

0004

特許第4759291号公報

先行技術

0005

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

発明が解決しようとする課題

0006

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

0007

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

0008

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

課題を解決するための手段

0009

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

発明の効果

0010

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

図面の簡単な説明

0011

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

実施例

0012

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

0013

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

0014

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

0015

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

0016

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

0017

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

0018

木構造符号化部106は、各ブロックの属性を示す木構造のデータを符号化する。各ブロックの属性は、以下の3つのいずれかである。
(1)着目ブロックは3D点を1つも含まず、分割は行われない(点無し)。
(2)着目ブロックは3D点を少なくとも1つ含み、分割は行われない(点有り分割無し)
(3)着目ブロックは3D点を少なくとも1つ含み、分割は行われる(点有り分割有り)。
なお、着目ブロックの属性が「点有り分割無し」の場合、ブロック内座標符号化部105によるブロック内符号化が行われることになる。

0019

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

0020

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

0021

S203にて、切替部103は、着目ブロックが基準階層より上の層に位置するか判定し、基準階層より上の階層に位置する場合には、ブロック分割処理を行うものとして決定する。ブロック分割を行うとして決定されると、分割部104は着目ブロックの分割処理を行う。なお、着目ブロックが3D点を1つも含まない場合には、分割部104はその分割処理をスキップする。つまり、分割部104は、着目ブロックが少なくとも1つの3D点を含む場合に分割処理を行う。図3(c)に、図3(b)のブロックを八分割した例を示す。ここで示すように、ブロック分割は着目ブロックのx、y、z軸の各辺の長さを2分割するように分ける。S203、S204を繰り返すことで、3D点を内包するブロックは、基準階層まで分割される。この後、処理はS205へ進む。なお、以降の説明の分割は、基準階層以下の階層についてのものであることに注意されたい。

0022

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

0023

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

0024

切替部103が、S205にて、着目ブロックを分割すると判定した場合は処理をS206に進め、着目ブロックを分割部104に渡し、着目ブロックを8分割させる。ここで行う分割処理はS204と同様である。つまり、着目ブロックが少なくとも1つの3D点を含むことを条件に、着目ブロックの分割処理を行う。

0025

また、S205にて、切替部103が、着目ブロックを分割しないと判定した場合には、処理をS207に進め、ブロック内座標符号化部105に着目ブロックのブロック内座標符号化を実行させる。ここで、ブロック内座標符号化を説明する。図3(d)は、ブロック内座標符号化を行う対象となった着目ブロックと、その中に含まれる3D点を示している。実施形態では、着目ブロックの代表座標から各3D点の座標の差分を符号化する。換言すれば、着目ブロック内の3D点は、着目ブロックの代表座標を基準とした相対座標として符号化される。本実施形態では、着目ブロックの代表座標は、着目ブロックのx、y、zの座標が最小となる角の座標とする。よって、着目ブロック内の3D点の1つである図示の点P1については、図示の矢印で示されるベクトルエントロピー符号化されることになる。他の3D点も同様に符号化する。なお、着目ブロック内の全3D点の1つを代表座標からのベクトルとして符号化し、残りの3D点は既に符号化した3D点の座標との差分ベクトルとして符号化しても構わない。S205からS207の処理を、S208が全ブロックの分割を終えたと判定するまで繰り返す。そして、全ブロックのブロック内座標符号化を終えると、処理はS209に進み、木構造符号化部106がこれまでの分割処理によって生成された八分木データを符号化する。そして、S210にて、符号化データ出力部107は、八分木データの符号化データ、並びに、ブロック内座標符号化データとを予め設定されたデータ構造に配列し、出力する。

0026

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

0027

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

0028

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

0029

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

0030

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

0031

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

0032

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

0033

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

0034

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

0035

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

0036

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

0037

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

0038

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

0039

外部記憶装置1507は、コンピュータ読み取り/書き込みを行う記憶媒体の一例であり、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置1507には、OS(オペレーティングシステム)や、図1に示した各処理をCPU1501に実現させるためのコンピュータプログラムやデータ等が保存されている。外部記憶装置1507に保存されているコンピュータプログラムやデータは、CPU1501による制御に従って適宜RAM1502にロードされ、CPU1501による処理対象となる。

0040

記憶媒体ドライブ1508は、CD−ROMやDVD−ROMなどの記憶媒体に記録されているコンピュータプログラムやデータを読み出し、読み出したコンピュータプログラムやデータを外部記憶装置1507やRAM1502に出力する。なお、外部記憶装置1507に保存されているものとして説明した情報の一部若しくは全部をこの記憶媒体に記録させておき、この記憶媒体ドライブ1508に読み取らせても良い。I/F1509は、木構造の基準階層等のパラメータ等を入力するインタフェースであり、一例として示すのであればUSB(Universal Serial Bus)である。1510は、上述の各部を繋ぐバスである。

0041

上述構成において、本コンピュータ電源がONになると、CPU1501はROM1503に格納されているブートプログラムに従って、外部記憶装置1507からOSをRAM1502にロードする。この結果、キーボード1504、マウス1505を介した情報入力操作が可能となり、表示装置1506にGUIを表示することが可能となる。ユーザが、キーボード1504やマウス1505を操作し、外部記憶装置1507に格納された、例えばグレー画像量子化用のアプリケーションプログラム起動指示を入力すると、CPU1501はこのプログラムをRAM1502にロードし、実行する。これにより、本コンピュータが符号化装置、あるいは復号装置として機能することになる。

0042

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

0043

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

0044

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

0045

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

0046

図10は、第2の実施形態における復号装置1005のブロック構成図である。この復号装置1005は、符号データを部分復号することが可能な点は第1の実施形態と異なる。図10におけるヘッダ解析部1001、木構造復号部1002、ブロック内点群データ復号部1003、点群変換部1004の基本的な処理は、図6のヘッダ解析部601、木構造復号部602、ブロック内点群データ復号部603、点群変換部604とほぼ同じである。ただし、本第2の実施形態では、部分復号を可能にするために、復号ブロック設定部1007と先頭アドレス読み込み部1008が加わった点、並びに、それに伴い木構造復号部1002とブロック内点群データ復号部1003が部分復号に適した処理をする点が異なる。

0047

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

0048

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

0049

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

0050

[第3の実施形態]
本第3の実施形態では木構造の生成に係る処理が第1の実施形態と異なる例を説明する。本第3の実施形態の装置構成は、図1と同じである。異なる点は、木構造生成部108の処理内容である。

0051

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

0052

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

0053

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

0054

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

0055

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

0056

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

0057

101…設定部、102…初期ブロック生成部、103…切替部、104…分割部、105…ブロック内座標符号化部、106…木構造符号化部、107…符号データ出力部、108…木構造生成部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ