(57)【要約】【課題】符号化性能を向上させること。【解決手段】データ符号化方法は、多次元データを複数の一次元データに分割するステップと、前記一次元データを第一の基準に基づきあらかじめ与えられたカテゴリのうち１つと関連付けるステップと、前記カテゴリ毎にデータ圧縮方法を選択するステップと、前記一次元データを前記一次元データが関連付けられたカテゴリに選択されたデータ圧縮方法によってデータ圧縮した圧縮データを得るステップとからなり、前記圧縮データのデータ量の総和は第二の基準を満たす。【選択図】図３
2018078503.tif 000002
【特許請求の範囲】
【請求項１】
多次元データを複数の一次元データに分割するステップと、
前記一次元データを第一の基準に基づきあらかじめ与えられた複数のカテゴリのうちの１つと関連付けるステップと、
前記カテゴリごとにデータ圧縮方法を選択するステップと、
前記一次元データを前記一次元データと関連付けられたカテゴリに対して選択されたデータ圧縮方法によってデータ圧縮した圧縮データを得るステップとからなり、
前記圧縮データに基づいて生成される圧縮後の多次元データ全体のデータ量の総和は第二の基準を満たすことを特徴とする
データ符号化方法。
【請求項２】
前記第二の基準は前記圧縮後の多次元データ全体のデータ量の総和とデータ圧縮後の符号化歪みに基づいて定められる基準であることを特徴とする
請求項１記載のデータ符号化方法。
【請求項３】
前記第一の基準は前記一次元データをデータ圧縮後の符号化歪みの大きさに基づいて定められる基準であることを特徴とする
請求項１記載のデータ符号化方法。
【請求項４】
第一の多次元データを複数の一次元データに分割するステップと、
前記複数の一次元データの順番が前記第一の基準および前記第二の基準とは異なる第三の基準を満たすような順番である一次元データ順を得るステップと、
前記一次元データ順に基づいて並び替えられた前記複数の一次元データからなる第二の多次元データを得るステップと、
前記第二の多次元データをデータ圧縮するステップとからなり、
前記データ圧縮するステップはデータ圧縮する対象のデータと隣接するデータに基づいてデータ圧縮することを特徴とする
請求項１記載のデータ符号化方法。
【請求項５】
前記多次元データは、少なくとも座標情報と色情報とを含み、
前記与えられた複数のカテゴリは第一から第三までの３つのカテゴリからなり、
第一のカテゴリは座標情報が関連付けられ、
第二のカテゴリは色情報が関連付けられ、
第三のカテゴリは前記座標情報でも前記色情報でもない情報が関連付けられることを特徴とする
請求項１から３のうちいずれか一項に記載のデータ符号化方法。
【請求項６】
多次元データを複数の一次元データに分割する分割部と、
前記一次元データを第一の基準に基づきあらかじめ与えられた複数のカテゴリのうちの１つと関連付ける関連付け部と、
前記カテゴリごとにデータ圧縮方法を選択する選択部と、
前記一次元データを前記一次元データと関連付けられたカテゴリに対して選択されたデータ圧縮方法によってデータ圧縮した圧縮データを得る符号化部と、
を備え、
前記圧縮データに基づいて生成される圧縮後の多次元データ全体のデータ量の総和は第二の基準を満たすことを特徴とする
データ符号化装置。
【請求項７】
第一の多次元データを複数の一次元データに分割する分割部と、
前記複数の一次元データの順番が前記第一の基準および前記第二の基準とは異なる第三の基準を満たすような順番である一次元データ順を得る順列決定部と、
前記一次元データ順に基づいて並び替えられた前記複数の一次元データからなる第二の多次元データを得る並び替え部と、
前記第二の多次元データを、データ圧縮する対象のデータと隣接するデータに基づいてデータ圧縮する符号化部と、
を備えることを特徴とする
請求項６記載のデータ符号化装置。
【請求項８】
請求項１から請求項４までのいずれか一項に記載のデータ符号化方法をコンピュータに実行させるためのデータ符号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数次元のデータ群のデータ符号化方法、データ符号化装置及びデータ符号化プログラムに関する。
【背景技術】
【０００２】
近年、デジタル画像を構成する各画素に対して、ＲＧＢ（Red, Green, Blue）成分などの色情報だけでなく、その他の属性情報が付加された、もしくはその他の属性情報が紐づけられたデータ群によって構成される画像データがある。代表的な属性情報は、例えば、画素ごとの奥行き情報を示すデプスマップ（深度マップ）や、３Ｄ（three-Dimensional；３次元）レーザスキャナで測定された点群データなどである。
とくに、後者の点群データは、例えば、物体の位置をＸＹＺ座標などによって表した座標点データ各々に対してＲＧＢ成分の色情報が対応付けられており、それに加えて３Ｄレーザスキャナによる測定時刻やレーザの反射強度などのその他の属性情報も多く付加されている。このように点群データは、多くの情報が付加された点情報の集合体によって構成されているため、付加された情報の次元数（項目数）が多くなることに伴ってデータ量も多くなる。したがって、点群データを蓄積したり、演算したり、または伝送したりするような処理が行われる場面においては、点群データに対して効率的なデータ符号化（データ圧縮）がなされる必要がある。
【０００３】
また、点群データを構成する複数の点情報は、一般性のある配列（例えば、２次元の離散的な格子状の配列など）にしたがって整列した情報ではないことが多いため、測定された点群データをファイル化する場合には、指定した順列にしたがって点情報が格納される必要がある。
従来、データ集合の符号化に関する先行技術として、一次元のデータ要素に対する効率的な符号化を図るための技術がある。例えば、非特許文献１に記載の差分符号化は、データ集合に含まれる複数のデータ間の差分値を符号化することによって、一次元のデータ要素に対する符号化を効率化する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】貴家仁志、吉田俊之、鈴木輝彦、広明敏彦、「映像情報メディア基幹技術シリーズ７  映像情報メディア学会編  画像情報符号化」、コロナ社、２００８年、ｐｐ２０−２１
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１に記載の差分符号化によれば、座標や色などの互いに特性が異なる複数の次元によってデータが構成される場合、各次元に対して個々に符号化がなされることになる。そのため、非特許文献１に記載の差分符号化は、次元毎に効率的な符号化を行うことはできても、複数の次元を横断して効率的な符号化を行うこと、すなわち、複数の次元の間に存在するデータの関係性を利用して効率的な符号化を行うことはできない。
例えば、点群データにおいては、ＸＹＺ座標とＲＧＢ成分などの色情報との間には、データの変動傾向に関する相関がある場合が多いが、非特許文献１に記載の差分符号化では、そのような関係性を利用して効率的に符号化をすることができないため、符号化の効率の面において改善の余地がある。
【０００６】
本発明はこのような事情に鑑みてなされたものであり、符号化性能を向上させる技術の提供を目的としている。
【課題を解決するための手段】
【０００７】
本発明の一態様は、多次元データを複数の一次元データに分割するステップと、前記一次元データを第一の基準に基づきあらかじめ与えられた複数のカテゴリのうちの１つと関連付けるステップと、前記カテゴリごとにデータ圧縮方法を選択するステップと、前記一次元データを前記一次元データと関連付けられたカテゴリに対して選択されたデータ圧縮方法によってデータ圧縮した圧縮データを得るステップとからなり、前記圧縮データに基づいて生成される圧縮後の多次元データ全体のデータ量の総和は第二の基準を満たすことを特徴とするデータ符号化方法である。
【０００８】
本発明の一態様は、上記のデータ符号化方法であって、前記第二の基準は前記圧縮後の多次元データ全体のデータ量の総和とデータ圧縮後の符号化歪みに基づいて定められる基準であることを特徴とする。
【０００９】
本発明の一態様は、上記のデータ符号化方法であって、前記第一の基準は前記一次元データをデータ圧縮後の符号化歪みの大きさに基づいて定められる基準であることを特徴とする。
【００１０】
本発明の一態様は、上記のデータ符号化方法であって、第一の多次元データを複数の一次元データに分割するステップと、前記複数の一次元データの順番が前記第一の基準および前記第二の基準とは異なる第三の基準を満たすような順番である一次元データ順を得るステップと、前記一次元データ順に基づいて並び替えられた前記複数の一次元データからなる第二の多次元データを得るステップと、前記第二の多次元データをデータ圧縮するステップとからなり、前記データ圧縮するステップはデータ圧縮する対象のデータと隣接するデータに基づいてデータ圧縮することを特徴とするデータ符号化方法である。
【００１１】
本発明の一態様は、上記のデータ符号化方法であって、前記多次元データは、少なくとも座標情報と色情報とを含み、前記与えられた複数のカテゴリは第一から第三までの３つのカテゴリからなり、第一のカテゴリは座標情報が関連付けられ、第二のカテゴリは色情報が関連付けられ、第三のカテゴリは前記座標情報でも前記色情報でもない情報が関連付けられることを特徴とする。
【００１２】
本発明の一態様は、多次元データを複数の一次元データに分割する分割部と、前記一次元データを第一の基準に基づきあらかじめ与えられた複数のカテゴリのうちの１つと関連付ける関連付け部と、前記カテゴリごとにデータ圧縮方法を選択する選択部と、前記一次元データを前記一次元データと関連付けられたカテゴリに対して選択されたデータ圧縮方法によってデータ圧縮した圧縮データを得る符号化部と、を備え、前記圧縮データに基づいて生成される圧縮後の多次元データ全体のデータ量の総和は第二の基準を満たすことを特徴とするデータ符号化装置である。
【００１３】
本発明の一態様は、上記のデータ符号化装置であって、第一の多次元データを複数の一次元データに分割する分割部と、前記複数の一次元データの順番が前記第一の基準および前記第二の基準とは異なる第三の基準を満たすような順番である一次元データ順を得る順列決定部と、前記一次元データ順に基づいて並び替えられた前記複数の一次元データからなる第二の多次元データを得る並び替え部と、前記第二の多次元データを、データ圧縮する対象のデータと隣接するデータに基づいてデータ圧縮する符号化部と、を備えることを特徴とするデータ符号化装置である。
【００１４】
本発明の一態様は、上記のデータ符号化方法をコンピュータに実行させるためのデータ符号化プログラムである。
【発明の効果】
【００１５】
本発明により、符号化性能を向上させることができる。
【図面の簡単な説明】
【００１６】
【図１】データ符号化装置に入力される点群データの構成を説明するための図である。
【図２】データ符号化装置の構成を説明するためブロック図である。
【図３】データ符号化装置の動作を説明するためのフローチャートである。
【図４】データ符号化装置の構成を説明するためブロック図である。
【図５】データ符号化装置の動作を説明するためのフローチャートである。
【図６】データ符号化装置の構成を説明するためブロック図である。
【図７】データ符号化装置の動作を説明するためのフローチャートである。
【発明を実施するための形態】
【００１７】
［実施形態］
以下、図面を参照しながら、本発明の実施形態の概要について説明する。
図１は、本発明の実施形態に係るデータ符号化装置に入力される点群データの構成を説明するための図である。
【００１８】
図示するように、本実施形態に係るデータ符号化装置に入力される点群データは、ＸＹＺ座標による位置情報（座標情報）を示すデータ項目である「Ｘ」、「Ｙ」、および「Ｚ」、ＲＧＢ成分による色情報を示すデータ項目である「Ｒ」、「Ｇ」、および「Ｂ」、３Ｄレーザスキャナによるレーザの反射強度を示すデータ項目である「Ｉｎｔｅｎｓｉｔｙ」、および３Ｄレーザスキャナによる測定時刻を示すデータ項目である「Ｔｉｍｅ」の８つの項目の列からなる（８次元の）データである。
【００１９】
本実施形態に係るデータ符号化装置は、Ｎ次元の点群データに含まれるデータ項目を、Ｍ個のカテゴリに分類する。図１に例示した８次元の点群データにおいては、各データ項目が持つ特性（意味）に基づいて、ＸＹＺ座標による位置情報を意味するデータ項目の集合である「カテゴリ１」（第一のカテゴリ）、ＲＧＢ成分による色情報を意味するデータ項目の集合である「カテゴリ２」（第二のカテゴリ）、および、その他（位置情報および色情報以外）の情報を意味するデータ項目である「カテゴリ３」（第三のカテゴリ）、の３つのカテゴリに分類されている。したがって、図１に例示した点群データにおいては、Ｎ＝８、および、Ｍ＝３である。
【００２０】
なお、上記のようなカテゴリを定義する場合の基準について説明する。Ｎ次元の点群データを構成するそれぞれの一次元の点群データには、例えば、符号化歪みを発生させたくない一次元の点群データ（第１の点群データ）と、一定の符号化歪みを許容することができる一次元の点群データ（第２の点群データ）と、オプションのように所定の場合には符号化が不要である一次元の点群データ（第３の点群データ）と、が含まれるものとする。
この場合、例えば、カテゴリＡに分類される点群データに対しては符号化歪みが生じない符号化あるいは符号化歪みが非常に小さい符号化を行い、カテゴリＢに分類される点群データに対しては一定の符号化歪みが生じるがデータ圧縮率がより高い符号化を行い、カテゴリＣに分類される点群データに対しては符号化を行わない、といったように、カテゴリＡ、カテゴリＢ、およびカテゴリＣが予め定義される。
そして、第１の点群データがカテゴリＡに分類され、第２の点群データがカテゴリＢに分類され、第３の点群データがカテゴリＣに分類されることにより、Ｎ次元の点群データに対してそれぞれ適切な符号化がなされる。
【００２１】
このように、データの意味や特性に基づいてデータ毎に符号化歪みの許容度が決定され（なお、データの意味に応じて歪みの許容度は異なることがある）、符号化歪みの許容度に応じてデータがカテゴリ分けされ、カテゴリ毎に適切な符号化方法が選択されることによって、全体としてより適切な符号化条件（符号化方法の組合せ）が決定される。
【００２２】
以下において、カテゴリごとの、非可逆符号化による原データとの差分を示す符号化歪み値Ｄとデータ量Ｒの線形和を、カテゴリごとの「符号化コスト」として定義する。したがって、符号化コストは、Ｄｉ＋λｉ＊Ｒｉ（ｉ＝１，２，３）という数式で表すことができる。ここで、ｉはカテゴリを表す。例えば、カテゴリ１、カテゴリ２、およびカテゴリ３の符号化コストは、それぞれ、Ｄ１＋λ１＊Ｒ１、Ｄ２＋λ２＊Ｒ２、およびＤ３＋λ３＊Ｒ３である。
【００２３】
また、全体の符号化コストＪは、Ｊ＝Σ｛ｗｉ＊（Ｄｉ＋λｉ＊Ｒｉ）｝と示すことができる。本実施形態に係るデータ符号化装置は、この符号化コストＪを最小化するように符号化を行う。
ここで、ｗｉは、カテゴリ間の符号化コストに対して優先付けをするための重み係数である。例えば、ｗｉは、選択された符号化モード（データ圧縮方法）などを示す符号化パラメータ、量子化ステップ幅、または（符号化性能が全体のデータ順列に依存するような場合には）上述した符号化コストＪを最小化するように決定されるデータ順列などを表す重み係数である。この重み係数を掛け合わせることによって、本実施形態に係るデータ符号化装置は、符号化歪みとデータ量のバランスを考慮しつつ、効率的な符号化を行うことができる。
【００２４】
なお、ここでは、「符号化歪み」とは、とは、元データと圧縮データとの差分情報、もしくは圧縮データでは欠損している元データの情報を意味するものとする。
【００２５】
＜第１実施例＞
以下、本発明の実施形態による第１実施例について説明する。
本実施形態の第１実施例に係るデータ符号化装置１ａは、カテゴリごとに、あらかじめ用意された複数の符号化モード（データ圧縮方法）の中から適切な符号化モードを選択し、選択した符号化モードによってカテゴリごとに符号化を行う。
例えば、符号化モード１として、代表的な波形符号化である「ＤＰＣＭ（Differential Pulse-Code Modulation；差分パルス符号変調）」、符号化モード２として「テーブル参照」、の２つの符号化モードがあらかじめ用意されているものとする。
【００２６】
なお、テーブル参照とは、あらかじめ数値セットがテーブルとして準備され、データごとに近しい数値セットのインデックスを特定して、そのインデックスに関する符号を符号化データとして格納する符号化方法である。
【００２７】
本実施形態の第１実施例に係るデータ符号化装置１ａは、上述した符号化コストＪを最小化するように各カテゴリに対する符号化モードの組合せを決定して、カテゴリごとに決定した符号化モードによって符号化を行う。例えば、カテゴリ１およびカテゴリ３を符号化モード１によって、およびカテゴリ２を符号化モード２によって符号化した場合に符号化コストＪが最小となる場合には、データ符号化装置１ａは、このような符号化モードの組合せによって符号化して符号化データを出力する。
【００２８】
（データ符号化装置の機能構成）
以下、データ符号化装置１ａの機能構成について、図面を参照しながら説明する。
図２は、本実施形態の第１実施例に係るデータ符号化装置１ａの機能構成を示すブロック図である。図示するようにデータ符号化装置１ａは、データ入力部１１と、コスト関数入力部１２と、符号化モード候補入力部１３と、符号化モード決定部１４と、符号化部１７ａと、符号化データ出力部１８とから構成される。
【００２９】
データ入力部１１は、符号化対象である、Ｍ個のカテゴリに分類されたＮ次元の点群データを取得する。データ入力部１１は、取得したＮ次元（以下、「多次元」とも言う）の点群データを、後述する符号化モード決定部１４、および後述する符号化部１７ａへ出力する。
コスト関数入力部１２は、符号化コストＪの算出に用いられるコスト関数を構成する情報（例えば、関数形、および関数中の係数値など）を取得する。コスト関数入力部１２は、取得したコスト関数を示す情報を、後述する符号化モード決定部１４へ出力する。
符号化モード候補入力部１３は、各カテゴリの点群データの符号化に用いられる符号化モードの候補（例えば、ＤＰＣＭ、テーブル参照など）を示す情報を取得する。符号化モード候補入力部１３は、符号化モードの候補を示す情報を、後述する符号化モード決定部１４へ出力する。
【００３０】
符号化モード決定部１４は、データ入力部１１から出力された多次元の点群データ、コスト関数入力部１２から出力されたコスト関数を示す情報、および符号化モード候補入力部１３から入力された符号化モードの候補を示す情報を取得する。
符号化モード決定部１４の分割部（図示せず）は、取得した多次元の点群データを複数の一次元の点群データに分割する。
符号化モード決定部１４の関連付け部（図示せず）は、一次元の点群データを、一次元の点群データの項目の特性や意味（第一の基準）に基づき、あらかじめ与えられた複数のカテゴリのうちの１つと関連付ける。
符号化モード決定部１４の選択部（図示せず）は、カテゴリごとに符号化モード（データ圧縮方法）を選択する。ここで、カテゴリごとの符号化モードは、符号化データ（データ圧縮後のデータ）の符号化歪みを所定の値以下とする等の条件の下で、各カテゴリの符号化コストＪが最小化されるように選択される。
符号化モード決定部１４は、カテゴリごとに選択された符号化モードを示す情報、および一次元の点群データとカテゴリとを関連付けた情報を、後述する符号化部１７ａへ出力する。
【００３１】
符号化部１７ａは、データ入力部１１から、多次元の点群データを取得する。また、符号化部１７ａは、符号化モード決定部１４から、カテゴリごとに選択された符号化モードを示す情報、および一次元の点群データとカテゴリとを関連付けた情報を取得する。
符号化部１７ａは、カテゴリごとに、当該カテゴリに関連付けられた一次元の点群データを、当該カテゴリに対して選択された符号化モード（データ圧縮方法）によって符号化（データ圧縮）することにより、カテゴリごとに符号化された符号化データ（圧縮データ）を生成する。
符号化部１７ａは、カテゴリごとに符号化された点群データを、符号化データ出力部１８へ出力する。
【００３２】
符号化データ出力部１８は、符号化部１７ａから取得した、カテゴリごとに符号化された点群データを統合して符号化データを生成し、生成した符号化データを出力する。
【００３３】
（データ符号化装置の動作）
以下、データ符号化装置１ａの動作について、図面を参照しながら説明する。
図３は、本実施形態の第１実施例に係るデータ符号化装置１ａの動作を示すフローチャートである。本フローチャートは、データ符号化装置１ａに対して、符号化対象のデータである点群データ、コスト関数、および符号化モードの候補を示す情報が出力された際に開始する。
【００３４】
（ステップＳ１１）データ入力部１１は、Ｍ個のカテゴリに分類されたＮ次元の点群データをデータ取得する。
（ステップＳ１２）コスト関数入力部１２は、符号化コストＪの算出に用いられるコスト関数を構成する情報（例えば、関数形、および関数中の係数値など）を取得する。
（ステップＳ１３）符号化モード候補入力部１３は、各カテゴリの点群データの符号化に用いられる符号化モードの候補（例えば、ＤＰＣＭ、テーブル参照など）を示す情報を取得する。
（ステップＳ１４）符号化モード決定部１４は、符号化対象の点群データ、符号化コストＪの関数を構成する情報、および符号化モード候補を示す情報に基づいて、符号化コストＪを最小化する符号化モードをカテゴリごとに決定する。
なお、符号化コストＪの最小値の探索方法は、全探索でもよいし、山登り法などの一般的な探索方法を適用してもよい。
（ステップＳ１５）符号化部１７ａは、カテゴリごとに決定された符号化モードに基づいて、カテゴリごとに符号化対象の点群データを符号化する。
（ステップＳ１６）符号化データ出力部１８は、カテゴリごとに符号化された点群データを統合して、符号化データとして出力する。
以上で、本フローチャートの処理が終了する。
【００３５】
＜第２実施例＞
以下、本発明の実施形態による第２実施例について説明する。
本実施形態の第２実施例に係るデータ符号化装置１ｂは、各次元の点群データに対して、適切な量子化ステップ幅を決定して符号化を行う。例えば、データ符号化装置１ｂは、ＤＰＣＭを使って符号化を行うことにした場合、カテゴリごとに適切な量子化ステップ幅を探索し、探索された量子化ステップ幅に基づいて符号化した符号を符号化データとして出力する。
【００３６】
（データ符号化装置の機能構成）
以下、データ符号化装置１ｂの機能構成について、図面を参照しながら説明する。
図４は、本実施形態の第２実施例に係るデータ符号化装置１ｂの機能構成を示すブロック図である。図示するようにデータ符号化装置１ｂは、データ入力部１１と、コスト関数入力部１２と、量子化ステップ幅決定部１５と、符号化部１７ｂと、符号化データ出力部１８とから構成される。
同図において図２の各部に対応する部分には同一の符号を付け、その説明を省略する。
【００３７】
量子化ステップ幅決定部１５は、データ入力部１１から出力された多次元の点群データ、およびコスト関数入力部１２から出力されたコスト関数を示す情報を取得する。
量子化ステップ幅決定部１５の分割部（図示せず）は、取得した多次元の点群データを複数の一次元の点群データに分割する。
量子化ステップ幅決定部１５の関連付け部（図示せず）は、一次元の点群データを、一次元の点群データをデータ圧縮した後の符号化歪みの大きさに基づいて定められる基準（第一の基準）にしたがって、あらかじめ与えられた複数のカテゴリのうちの１つと関連付ける。
量子化ステップ幅決定部１５の選択部（図示せず）は、符号化対象の点群データ、コスト関数に基づいて、符号化コストＪを最小化する量子化ステップ幅をカテゴリごとに選択する。
量子化ステップ幅決定部１５は、カテゴリごとに選択された量子化ステップ幅を示す情報、および一次元の点群データとカテゴリとを関連付けた情報を、後述する符号化部１７ｂへ出力する。
【００３８】
符号化部１７ｂは、データ入力部１１から、多次元の点群データを取得する。また、符号化部１７ｂは、量子化ステップ幅決定部１５から、カテゴリごとに選択されたた量子化ステップ幅を示す情報、および一次元の点群データとカテゴリとを関連付けた情報を取得する。
符号化部１７ｂは、カテゴリごとに、当該カテゴリに関連付けられた一次元の点群データを、当該カテゴリに対して選択された量子化ステップ幅に基づいてデータ圧縮することにより、カテゴリごとに符号化された点群データ（圧縮データ）を生成する。
符号化部１７ｂは、カテゴリごとに符号化された点群データを、符号化データ出力部１８へ出力する。
【００３９】
（データ符号化装置の動作）
以下、データ符号化装置１ｂの動作について、図面を参照しながら説明する。
図５は、本実施形態の第２実施例に係るデータ符号化装置１ｂの動作を示すフローチャートである。本フローチャートは、データ符号化装置１ｂに対して、符号化対象のデータである点群データ、およびコスト関数を示す情報が出力された際に開始する。
【００４０】
（ステップＳ２１）データ入力部１１は、Ｍ個のカテゴリに分類されたＮ次元の点群データを取得する。
（ステップＳ２２）コスト関数入力部１２は、符号化コストＪの算出に用いられるコスト関数を構成する情報（例えば、関数形、および関数中の係数値など）を取得する。
（ステップＳ２３）量子化ステップ幅決定部１５は、符号化対象の点群データ、および符号化コストＪの関数を構成する情報に基づいて、符号化コストＪを最小化する量子化ステップ幅をカテゴリごとに決定する。
なお、第１の実施形態と同様、符号化コストＪの最小値の探索方法は、全探索でもよいし、山登り法などの一般的な探索方法を適用してもよい。
（ステップＳ２４）符号化部１７ｂは、カテゴリごとに決定された量子化ステップ幅に基づいて、カテゴリごとに符号化対象の点群データを符号化する。
（ステップＳ２５）符号化データ出力部１８は、カテゴリごとに符号化された点群データを統合して、符号化データとして出力する。
以上で、本フローチャートの処理が終了する。
【００４１】
＜第３実施例＞
以下、本発明の実施形態による第３実施例について説明する。
本実施形態の第３実施例に係るデータ符号化装置１ｃは、適切なデータ順列を決定して符号化を行う。例えば、ＤＰＣＭを使って符号化が行われる場合、前データとの差分を計算することにより符号化が行われるため、データの順番によって符号化性能が変動する。データ符号化装置１ｃは、全体のデータ順列を変動させ、符号化コストＪを最小化する順列を導き出し、導き出したデータ順列に基づいて符号化した符号を符号化データとして出力する。
【００４２】
（データ符号化装置の機能構成）
以下、データ符号化装置１ｃの機能構成について、図面を参照しながら説明する。
図６は、本実施形態の第３実施例に係る符号化装置１ｃの機能構成を示すブロック図である。図示するように符号化装置１ｃは、データ入力部１１と、コスト関数入力部１２と、データ順列決定部１６と、符号化部１７ｃと、符号化データ出力部１８とから構成される。
同図において図２の各部に対応する部分には同一の符号を付け、その説明を省略する。
【００４３】
データ順列決定部１６は、データ入力部１１から出力された多次元の点群データ、およびコスト関数入力部１２から出力されたコスト関数を示す情報を取得する。
データ順列決定部１６の分割部（図示せず）は、取得した多次元の点群データ（第一の多次元データ）を複数の一次元の点群データに分割する。
【００４４】
データ順列決定部１６の順列決定部（図示せず）は、複数の一次元の点群データの順番が、符号化コストＪを最小化するという基準（第三の基準）を満たす順番である一次元データ順を決定する。
ここで、点群データの順番を入れ替えた場合、あるカテゴリでは符号化コストＪがより小さくなるが、その他のカテゴリでは逆に符号化コストＪがより大きくなってしまう場合がある。例えば、ＲＧＢ成分による色情報を示すデータ項目である「Ｒ」、「Ｇ」、および「Ｂ」に対して符号化コストＪを小さくするように順番の入れ替えを行うと、これに対応して順番が入れ替わるＸＹＺ座標による位置情報（座標情報）を示すデータ項目である「Ｘ」、「Ｙ」、および「Ｚ」では符号化コストＪが大きくなることがある。したがって、データ順列決定部１６の順列決定部（図示せず）は、全体として符号化コストＪが最小化されるように、一次元データ順を決定する。
【００４５】
データ順列決定部１６は、一次元データ順を示す情報、および一次元の点群データとカテゴリとを関連付けた情報を、後述する符号化部１７ｃへ出力する。
【００４６】
符号化部１７ｃは、データ入力部１１から、多次元の点群データを取得する。また、符号化部１７ｃは、データ順列決定部１６から、一次元データ順を示す情報、および一次元の点群データとカテゴリとを関連付けた情報を取得する。
符号化部１７ｃの並び替え部（図示せず）は、一次元データ順を示す情報に基づいて複数の一次元の点群データを並べ替えることによって多次元の点群データ（第二の多次元データ）を生成する。
符号化部１７ｃは、第二の多次元データを、データ圧縮する対象のデータと隣接するデータに基づいて符号化（データ圧縮）する。
符号化部１７ｃは、符号化された点群データを、符号化データ出力部１８へ出力する。
【００４７】
（データ符号化装置の動作）
以下、データ符号化装置１ｃの動作について、図面を参照しながら説明する。
図７は、本実施形態の第２実施例に係る符号化装置１ｃの動作を示すフローチャートである。本フローチャートは、データ符号化装置１ｃに対して、符号化対象のデータである点群データ、およびコスト関数を示す情報が出力された際に開始する。
【００４８】
（ステップＳ３１）データ入力部１１は、Ｍ個のカテゴリに分類されたＮ次元の点群データをデータ取得する。
（ステップＳ３２）コスト関数入力部１２は、符号化コストＪの算出に用いられるコスト関数を構成する情報（例えば、関数形、および関数中の係数値など）を取得する。
（ステップＳ３３）データ順列決定部１６は、符号化対象の点群データ、および符号化コストＪの関数を構成する情報に基づいて、符号化コストＪを最小化する全体のデータ順列を決定する。
なお、第１の実施形態と同様、符号化コストＪの最小値の探索方法は、全探索でもよいし、山登り法などの一般的な探索方法を適用してもよい。
（ステップＳ３４）符号化部１７ｃは、カテゴリごとに決定されたデータ順列によって点群データを並び替えて、カテゴリごとに符号化対象の点群データを符号化する。
（ステップＳ３５）符号化データ出力部１８は、カテゴリごとに符号化された点群データを統合して、符号化データとして出力する。
以上で、本フローチャートの処理が終了する。
【００４９】
以上、説明したように、本発明の実施形態に係るデータ符号化装置１（１ａ、１ｂ、および１ｃ）によれば、２以上の値を持つＮ次元のデータ群がＭ個のカテゴリに分類され、それらＭ個のカテゴリに対して横断的に、適切なパラメータ、例えば、符号化モード、量子化ステップ幅、またはデータ順列などが決定されることにより、効率的な符号化が図られる。なお、Ｍ個のカテゴリは、Ｎ次元のデータに含まれる各次元が持つ特性（意味）、複数の次元の間の相関、およびデータ変動の傾向などを考慮して決定される。これにより、本発明の実施形態に係るデータ符号化装置１（１ａ、１ｂ、および１ｃ）は、符号化性能を向上させることができる。
【００５０】
なお、本実施形態に係る第１乃至第３の実施例に係るデータ符号化装置１（１ａ、１ｂ、および１ｃ）の機能が組み合わされた構成であってもよい。例えば、第１および第２の実施例に係るデータ符号化装置１（１ａ、１ｂ）の機能を組み合わせることにより、適切な符号化モードの選択と量子化ステップ幅とに基づいて効率的な符号化を行うようにしてもよい。また、第２および第３の実施例に係るデータ符号化装置１（１ｂ、１ｃ）の機能を組み合わせることにより、データ順列と量子化ステップ幅とに基づいて効率的な符号化を行うようにしてもよい。
【００５１】
上述した実施形態におけるデータ符号化装置１（１ａ、１ｂ、および１ｃ）をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであってもよく、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＦＰＧＡ（Field Programmable Gate Array）等のプログラマブルロジックデバイスを用いて実現されるものであってもよい。
【００５２】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００５３】
１…データ符号化装置（１ａ、１ｂ、１ｃ）、１１…データ入力部、１２…コスト関数入力部、１３…符号化モード候補入力部、１４…符号化モード決定部、１５…量子化ステップ幅決定部、１６…データ順列決定部、１７…符号化部（１７ａ、１７ｂ、１７ｃ）、１８…符号化データ出力部
【図１】
2018078503.tif 000003
【図２】
2018078503.tif 000004
【図３】
2018078503.tif 000005
【図４】
2018078503.tif 000006
【図５】
2018078503.tif 000007
【図６】
2018078503.tif 000008
【図７】
2018078503.tif 000009