(57)【要約】  この方法は、属性によって定められる複数の点を含む点群（ＰＣ）にアクセスすること（２）であって、前述の属性は３Ｄ空間内の点の空間位置及び点の少なくとも１つの特徴を含む、アクセスすること（２）、点の属性に基づいて点群を点の１つ又は複数のクラスタ（Ｃｉ）へと区分化すること（２）、並びに少なくとも１つのクラスタ（Ｃｉ）について、複数の頂点及び少なくとも１つの辺を有する類似度グラフを構築すること（４）であって、類似度グラフは属性に関してクラスタ（Ｃｉ）の隣接点間の類似度を表し、複数の頂点はクラスタ（Ｃｉ）の点に対応する頂点Ｐｉ及びＰｊを含む、構築すること（４）、グラフの頂点ＰｉとＰｊとを接続する１つ又は複数の辺に１つ又は複数の重みｗｉ，ｊを割り当てること、１つ又は複数の割り当てた重みを使用して変換を計算すること（６）であって、前述の変換は係数によって特徴付けられる、計算すること（６）、及び変換係数を量子化し（８）符号化する（１０）ことを含む。
2020521359.tif 000002
【特許請求の範囲】
【請求項１】
属性によって定められる複数の点を含む点群（ＰＣ）にアクセスすることであって、前記属性は３Ｄ空間内の点の空間位置及び前記点の少なくとも１つの特徴を含む、アクセスすること、
前記点の前記属性に基づいて前記点群（ＰＣ）を点の１つ又は複数のクラスタ（Ｃｉ）へと区分化すること（２）、
並びに少なくとも１つのクラスタ（Ｃｉ）について、
複数の頂点及び少なくとも１つの辺を有する類似度グラフを構築すること（４）であって、前記類似度グラフは前記属性に関して前記クラスタ（Ｃｉ）の隣接点間の類似度を表し、前記複数の頂点は前記クラスタ（Ｃｉ）の点に対応する頂点Ｐｉ及びＰｊを含む、構築すること（４）、
前記グラフの頂点ＰｉとＰｊとを接続する１つ又は複数の辺に１つ又は複数の重みｗｉ，ｊを割り当てること、
前記１つ又は複数の割り当てた重みを使用して変換を計算すること（６）であって、前記変換は係数によって特徴付けられる、計算すること（６）、及び
前記変換係数を量子化し（８）符号化する（１０）こと
を含む、方法。
【請求項２】
点群（ＰＣ）を符号化するための装置（３０）であって、
属性によって定められる複数の点を含む前記点群であって、前記属性は３Ｄ空間内の点の空間位置及び前記点の少なくとも１つの特徴を含む、前記点群を前記点の前記属性に基づいて点の１つ又は複数のクラスタへと区分化するように構成される区分化モジュール（３４）と、
少なくとも１つのクラスタ（Ｃｉ）について、複数の頂点及び少なくとも１つの辺を有する類似度グラフを構築することであって、前記類似度グラフは前記属性に関して前記クラスタ（Ｃｉ）の隣接点間の類似度を表し、前記複数の頂点は前記クラスタ（Ｃｉ）の点に対応する頂点Ｐｉ及びＰｊを含む、構築すること、及び前記グラフの頂点ＰｉとＰｊとを接続する１つ又は複数の辺に１つ又は複数の重みｗｉ，ｊを割り当てることを行うように構成される構築モジュール（３６）と、
少なくとも１つのクラスタについて、前記１つ又は複数の割り当てられた重みを使用して変換を計算するように構成される計算モジュール（３８）であって、前記変換は係数によって特徴付けられる、計算モジュール（３８）と、
前記変換係数を量子化し符号化するように構成される符号化モジュール（４０）と
を含む、装置（３０）。
【請求項３】
少なくとも１つのクラスタ（Ｃｉ）について、前記符号化済みの変換係数並びに前記クラスタ（Ｃｉ）の識別情報及び前記計算済みの変換の識別情報を復号器（５０）に伝送するステップ（１２）を前記方法が含み、又は伝送するための手段（４２）を前記装置が含む、請求項１に記載の方法又は請求項２に記載の装置。
【請求項４】
前記変換係数の前記符号化がエントロピ符号化である、請求項１若しくは３に記載の方法又は請求項２若しくは３に記載の装置。
【請求項５】
前記重みｗｉ，ｊが閾値を下回る場合は前記重みを０に設定し、頂点Ｐｉ及びＰｊの接続を解除する、請求項１若しくは３〜４の何れか一項に記載の方法又は請求項２〜４の何れか一項に記載の装置。
【請求項６】
前記変換がグラフフーリエ変換、ＧＦＴである、請求項１若しくは３〜５の何れか一項に記載の方法又は請求項２〜５の何れか一項に記載の装置。
【請求項７】
前記少なくとも１つの特徴が色情報を含む、請求項１若しくは３〜６の何れか一項に記載の方法又は請求項２〜６の何れか一項に記載の装置。
【請求項８】
属性によって定められる複数の点を含む点群（ＰＣ）の１つ又は複数のクラスタのインデックスに関連する変換係数を含むデータを受信することであって、前記属性は３Ｄ空間内の点の空間位置及び前記点の少なくとも１つの特徴を含む、受信すること、
前記受信したデータを復号すること（２０）、及び
受信したクラスタインデックスによって識別される少なくとも１つのクラスタについて逆変換を実行すること（２４）によって前記点群の前記１つ又は複数のクラスタ（Ｃｉ）を再構築すること
を含む、方法。
【請求項９】
点群を再構築するための装置（５０）であって、
属性によって定められる複数の点を含む前記点群の１つ又は複数のクラスタのインデックスに関連する変換係数を含むデータを受信するように構成される受信機（５４）であって、前記属性は３Ｄ空間内の点の空間位置及び前記点の少なくとも１つの特徴を含む、受信機（５４）と、
前記受信されたデータを復号するように構成される復号モジュール（５６）と、
受信されたクラスタインデックスによって識別される少なくとも１つのクラスタについて逆変換を実行することによって前記点群の前記１つ又は複数のクラスタを再構築するように構成される再構築モジュール（５８）と
を含む、装置（５０）。
【請求項１０】
前記復号がエントロピ復号を含む、請求項８に記載の方法又は請求項９に記載の装置。
【請求項１１】
前記変換がグラフフーリエ変換、ＧＦＴである、請求項８若しくは１０に記載の方法又は請求項９若しくは１０に記載の装置。
【請求項１２】
請求項１又は３〜７の何れか一項に記載の符号化方法をコンピュータが実行できるようにするためのコンピュータ実行可能命令を含む、コンピュータ可読プログラム。
【請求項１３】
請求項８又は１０又は１１の何れか一項に記載の再構築方法をコンピュータが実行できるようにするためのコンピュータ実行可能命令を含む、コンピュータ可読プログラム。
【請求項１４】
請求項１若しくは３〜７の何れか一項に記載の方法に従って又は請求項２〜７の何れか一項に記載の装置によって生成されるデータコンテンツを含む、非一時的コンピュータ可読媒体。
【請求項１５】
請求項１若しくは３〜７の何れか一項に記載の方法に従って又は請求項２〜７の何れか一項に記載の装置によって生成されるデータを含む、信号。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
本開示は、一般に点群データ源の分野に関する。より詳細には、本発明は点群圧縮（ＰＣＣ）を扱う。従って、本開示は点群を符号化するための方法及び対応する符号器に関する。本開示は、点群を再構築するための方法及び対応する復号器にも関する。本開示は、本発明の符号化方法及び再構築方法を実装するコンピュータプログラムに更に関する。
【背景技術】
【０００２】
発明の背景
この節に記載する手法は遂行可能だが、過去に考案され又は遂行されている手法では必ずしもない。従って本明細書で別段の定めがない限り、この節に記載の手法は本願の特許請求の範囲に対する従来技術ではなく、この節に含まれることによって従来技術として認めることもない。
【０００３】
点群は１組の点で構成される。各点はその空間位置（ｘ，ｙ，ｚ）、即ち幾何学的配置情報、及び（Ｒ，Ｇ，Ｂ）又は（Ｙ，Ｕ，Ｖ）又は他の任意の色座標系内の色情報を概して含む様々な属性によって定められる。幾何学的配置は属性データの１つと見なすことができる。本開示の残りの部分では、幾何学的配置データ及び他の属性データの両方を点の属性と見なす。
【０００４】
点群データ源は多くの応用において見つかる。大規模な点群データ源に依拠する重要な応用は地理情報システム、ロボット工学、医療断層撮影、及び科学的可視化において見つけることができる。
【０００５】
より工業的であり且つ科学指向であるこれらの応用の他に、飛行時間又は他の奥行検知技術に基づく安価な３Ｄスキャナの人気の高まり、モバイル装置上での３Ｄ捕捉、及びクラウドベースの３Ｄ印刷の台頭が、大規模な相互運用可能な圧縮３Ｄ点群の記憶及び伝送データ形式の大きい需要を消費者市場内で作り出している。
【０００６】
走査される３Ｄ点群はしばしば何千もの点を有し、大量の記憶空間を占有する。加えて、それらの点群は３Ｄスキャナからライブで捕捉されるとき高速で生成することができ、データ転送速度を一層高める。従って、点群圧縮はネットワーク化された効率的な配信及び記憶に不可欠である。
【０００７】
３Ｄグラフィックス及びロボット工学の分野で点群圧縮のかなりの取り組みがなされてきたが、それらの取り組みは効率的な相互運用可能且つ完全な終端間３Ｄマルチメディアシステムを構築するための要件の一部に概して対処しない。
【０００８】
例えば高品質レンダリングに重要な色及び他の属性値の符号化はしばしば無視され、又は例えば色の単純な単方向の予測符号化を行うことによって非効率的に処理される。更に、経時変化する点群、即ち或る期間にわたって高速で捕捉される一連の群の圧縮は限られている。更に、ハードウェア／帯域幅限界が該当するシステム又は低遅延が極めて重要であるシステムでは、複雑度が低く非可逆的な符号化を伴う方法が興味を引く。これらの課題に対処するために点群圧縮の研究を引き続き行う必要がある。
【０００９】
従来技術では、点群の様々な符号化方法が提案されてきた。
【００１０】
第１の符号化手法は８分木に基づく点群表現に基づく。これは例えばJ. Peng及びC.-C. Jay Kuo, “Geometry-guided progressive lossless 3D mesh coding with octree (OT) decomposition,” ACM Trans. Graph, vol. 21, no. 2, pp. 609-616, July 2005、並びにYan Huang, Jingliang Peng, C.-C. Jay Kuo及びM. Gopi, “A Generic Scheme for Progressive Point Cloud Coding,” IEEE Transactions on Visualization and Computer Graphics, vol.14, no.2, pp.440-453, 2008の中で記載されている。
【００１１】
８分木とは、全ての分岐ノードが空間内の特定の立方体の又は立方形の境界ボリュームを表すツリーデータ構造である。根から始まり、全ての分岐はノードの境界ボックスのサブオクタントごとに１つの最大８個の子を有する。
【００１２】
一例を図１及び図２の左側に示す。
【００１３】
圧縮のために、単一のビットを使用して分岐ノードの全ての子が空かどうかを印付けし、８個のオクタントの幾らかの一貫した順序付けを仮定し、その分岐ノード構成は単一のバイトによって効率的に表すことができる。木を幅優先順に横断し、遭遇する全ての子ノード構成バイトを出力することによって空間内の点分布を効率的に符号化することができる。符号化済みのバイトストリームを読み取ると、最初のバイト内で設定されるビットの数が、直接の子である連続バイトの数を復号器に知らせる。ビットの位置は、そのビットが占有する８分木内のボクセル／子を指定する。図２の右側は、左側に示す８分木に関するこのバイトストリーム表現を示す。
【００１４】
その階層的性質により、８分木表現は点群のスパース性を活用する際に非常に効率的である。従って、８分木分解に基づく戦略はスパースな点群を圧縮するのに非常に効率的である。しかし、８分木に基づく表現は隙のない密な点群を表現し圧縮するには非効率的である。更に、既存の８分木に基づく点群表現の殆どは点の幾何学的配置及び他の属性を独立に表す。
【００１５】
第２の符号化手法は、区分化に基づく点群表現に基づく。これは例えばProc. Eurographics Symp. on Point-Based Graphics, 2004内のT. Ochotta及びD. Saupe, “Compression of point-based 3d models by shape-adaptive wavelet coding of multi-heightfields”、及びJ. Digne, R. Chaine, S. Valette, et al, “Self-similarity for accurate compression of point sampled surfaces,” Computer Graphics Forum, vol. 33, p.155-164, 2014の中で記載されている。
【００１６】
区分化に基づく点群表現は、面様の分解、面の投影、及び符号化という３つのステップを含む。最初のステップにおいて、点群データを面様のパッチに区分化する。次いで、その結果生じるパッチを１つ又は幾つかの面上に投影する。最後のステップにおいて、投影像を圧縮する。投影像を圧縮するために、効率的な画像／映像圧縮技法を使用することができる。
【００１７】
面様の区分化に基づくＰＣＣは、おおよその区分線形面を表す密な点群を符号化するのに非常に効率的であることが分かっている。しかし、区分化に基づくＰＣＣには幾つかの不利点がある。実際、この方法は規則的な格子上への再サンプリングを必要とし、かかる再サンプリングは近似誤差を引き起こす。更に、複雑な形状のために大量のパッチを生成する必要があり、そのことは複雑なテクスチャのための高い計算複雑さを含意する。更に、この方法は幾何学的配置及び他の特性を独立に処理する。
【００１８】
Robotics and Automation (ICRA), 2012 IEEE International Conference on , pp.778,785, 14-18 May, 2012内のJ. K. N. Blodow, R. Rusu, S. Gedikli、及びE. S. M Beetz, “Real-time compression of point cloud streams”等、上記の２つの点群表現の利点を組み合わせようとする取り組みがある。
【００１９】
それらの取り組みでは、８分木の分解のやり方で入力点群をまず分解する。それぞれの立方形分割操作の後、新たに生成される同じ葉の立方形に含まれる点が面によって近似され得るかどうかを確認する。近似され得る場合、対応する立方体の分割を停止し、対応する面上に投影することによって関連する点を符号化する。すると面様のパッチの位置が８分木の方法によって効率的に表現され圧縮され得る。
【００２０】
しかしこれらの全ての既知の方法は、点群の属性データの効率的な表現及び符号化を提供しない。
【００２１】
Collet et al. “High-quality streamable free-viewpoint video”, ACM Transactions on Graphics, vol.34, no.4, 2015の文献では点群が３Ｄメッシュに変換され、その後、点群を符号化するために最先端の３Ｄメッシュ圧縮技法が使用される。しかし、点群をメッシュに変換する必要があるこの方法は通常計算コストが高く、３Ｄメッシュの接続性を符号化するために余分なビットが必要になる。
【００２２】
最近では点群を符号化するためのグラフに基づく方法が提案されている。点群の属性はZhang et al.: “Point cloud attribute compression with graph transform”, IEEE International Conference on Image Processing, Paris, 2014内のグラフ変換を使用して圧縮される。属性はグラフ上の信号として扱われ、信号の相関をおおよそ失わせるためにグラフ変換が使用される。しかし、８分木構造に基づいてグラフを構築することにより、点群表現は依然として８分木表現に基づく。更に、幾何学的配置を除く属性の圧縮だけがこの文献では検討されている。
【００２３】
３Ｄ点群シーケンスを圧縮する問題は、グラフに基づく方法と共にイントラ符号化に重点を置いてThanou et al.: “Graph-based compression of dynamic 3D point cloud sequences,” IEEE Transactions on Image Processing, vol.25, n°4, pages 1765-1778, 2016の中で述べられている。それでもなお、この手法は８分木表現を依然として採用する。Queiroz et al. “Compression of 3D point clouds using a region-adaptive hierarchical transform”, IEEE Transactions on Image Processing, Volume: 25, Issue: 8, Aug. 2016では、階層変換に基づいて点群内の色を圧縮するための方法が設計されている。その一方で、点群の幾何学的配置はここでも８分木表現を使用して符号化される。
【００２４】
上記の取り組みは全て８分木表現に基づき、幾何学的配置及び他の属性を別々に検討する。符号化効率を得るための点群の区分線形性の活用が８分木表現によって限定されるのでかかる形態は不利である。更に、幾何学的配置と属性との間の冗長性が考慮されておらず、そのことは符号化性能の更なる改善をなくす。
【発明の概要】
【００２５】
発明の概要
本開示はこの状況を改善するための解決策を提案する。
【００２６】
従って本開示は、請求項１に記載の点群を符号化するための方法、及び請求項２に記載の対応する符号器に関する。本開示は、請求項８に記載の点群を再構築するための方法、及び請求項９に記載の対応する復号器にも関する。本開示は、本発明の符号化方法及び再構築方法を実装するコンピュータプログラムに更に関する。本開示は請求項１５に記載の信号にも関する。
【００２７】
従って本開示は、複数の点を含む点群を符号化するための方法を提供し、各点は属性によって定められ、属性は３Ｄ空間内の点の空間位置及び点の少なくとも１つの特徴を含み、この方法は、
−点の属性に基づいて点群を点のクラスタへと区分化すること、
並びにクラスタごとに
−属性に関してクラスタの隣接点間の類似度を表す類似度グラフを構築すること、
−構築した類似度グラフに基づいてグラフフーリエ変換、ＧＦＴを計算することであって、ＧＦＴはその係数によって特徴付けられる、計算すること、及び
−ＧＦＴ係数を量子化し符号化すること
を含む。
【００２８】
従って本発明の符号化方法は、幾何学的配置、即ち３Ｄ空間内の点の空間位置及び少なくとも１つの他の属性、即ち色又はテクスチャ等の特徴を含む属性を一緒に圧縮し、ＧＦＴに基づいてそれらの間の冗長性を活用する。
【００２９】
点群をクラスタに区分化することによって各クラスタ内でグラフ変換操作が行われ、従って処理時間の意味でより効率的である。
【００３０】
有利にはこの方法は、クラスタごとに、符号化済みのＧＦＴ係数並びにクラスタの識別情報及び計算済みのＧＦＴの識別情報を復号器に伝送することを含む。
【００３１】
どのＧＦＴがどのクラスタに使用されるのかを復号器に示し、それにより点群の最終的な再構築に復号器が正しい逆変換を行うことができるように、これらの識別情報はクラスタインデックス及びＧＦＴインデックスで構成され得る。
【００３２】
好ましい実施形態によれば、ＧＦＴ係数の符号化がエントロピ符号化である。
【００３３】
有利には、点群のクラスタへの区分化が正規化カット技法を使用する。
【００３４】
この技法は、例えばIEEE Trans. Pattern Anal. Mach. Intell., Vol.22, No.8, pages 888-905, 2000内のMalik et al.: “Normalized cuts and image segmentation”の文献の中で記載されている。
【００３５】
好ましくは、構築される類似度グラフの頂点が対応するクラスタの点で構成され、この方法がグラフの任意の頂点Ｐｉ及びＰｊ間に重みｗｉ，ｊを割り当てることを含む。
【００３６】
有利には、前述の重みが閾値を下回る場合は頂点Ｐｉ及びＰｊ間の重みｗｉ，ｊを０に設定する。
【００３７】
このようにして、小さな重みは対応する接続された頂点が或る程度異なることを意味するので、符号化の質を落とすことなしに全体的な符号化ビットを低減するために小さな重みは符号化しない。
【００３８】
有利には、類似度グラフを構築することは、重みｗｉ，ｊが閾値以上の場合に頂点Ｐｉ及びＰｊ間に辺ｅｉ，ｊを追加することを含む。
【００３９】
本開示は、複数の点を含む点群を符号化するための符号器も提供し、各点は属性によって定められ、属性は３Ｄ空間内の点の空間位置及び点の少なくとも１つの特徴を含み、この符号器は、
−点の属性に基づいて点群を点のクラスタへと区分化するように構成される区分化モジュールと、
−属性に関してクラスタの隣接点間の類似度を表す類似度グラフをクラスタごとに構築するように構成される構築モジュールと、
−構築された類似度グラフに基づいてグラフフーリエ変換、ＧＦＴをクラスタごとに計算するように構成される計算モジュールであって、ＧＦＴはその係数によって特徴付けられる、計算モジュールと、
−ＧＦＴ係数を符号化するように構成される符号化モジュールと
を含む。
【００４０】
有利にはこの符号器は、符号化済みのＧＦＴ係数並びにクラスタの識別情報及び計算済みのＧＦＴの識別情報を復号器に伝送するように構成される送信機を含む。
【００４１】
本開示は、複数の点を含む点群を再構築するための方法も提供し、各点は属性によって定められ、属性は３Ｄ空間内の点の空間位置及び点の少なくとも１つの特徴を含み、この方法は、
−クラスタインデックス及びＧＦＴインデックスに関連するＧＦＴ係数を含むデータを受信すること、
−受信したデータを復号すること、及び
−受信したクラスタインデックスによって識別されるクラスタごとに逆ＧＦＴを実行することによってクラスタを再構築すること
を含む。
【００４２】
有利には復号がエントロピ復号を含む。
【００４３】
本開示は、複数の点を含む点群を再構築するための復号器も提供し、各点は属性によって定められ、属性は３Ｄ空間内の点の空間位置及び点の少なくとも１つの特徴を含み、この復号器は、
−クラスタインデックス及びＧＦＴインデックスに関連するＧＦＴ係数を含む符号化済みのデータを受信するように構成される受信機と、
−受信されたデータを復号するように構成される復号モジュールと、
−受信されたクラスタインデックスによって識別されるクラスタごとに逆ＧＦＴを実行することによってクラスタを再構築するように構成される再構築モジュールと
を含む。
【００４４】
本開示による方法はプログラム可能機器上のソフトウェアによって実装することができる。これらの方法はハードウェア若しくはソフトウェアだけによって、又はそれらの組み合わせによって実装することができる。
【００４５】
これらの方法はソフトウェアによって実装可能なので、これらの方法は任意の適切なキャリア媒体上でプログラム可能機器に与えるためのコンピュータ可読コードとして具体化することができる。キャリア媒体は、フロッピディスク、ＣＤ−ＲＯＭ、ハードディスクドライブ、磁気テープ装置、又はソリッドステートメモリ装置等の記憶媒体を含み得る。
【００４６】
従って本開示は、本発明の符号化方法をコンピュータが実行できるようにするためのコンピュータ実行可能命令を含むコンピュータ可読プログラムを提供する。
【００４７】
図３の図面は、かかるコンピュータプログラムのための全般的なアルゴリズムの一例を示す。
【００４８】
本開示は、本発明の再構築方法をコンピュータが実行できるようにするためのコンピュータ実行可能命令を含むコンピュータ可読プログラムも提供する。
【００４９】
図４の図面は、かかるコンピュータプログラムのための全般的なアルゴリズムの一例を示す。
【００５０】
図面の簡単な説明
本発明を添付図面の図中に限定ではなく例として示し、図中、同様の参照番号は同様の要素を指す。
【図面の簡単な説明】
【００５１】
【図１】既に説明しており、従来技術による８分木に基づく点群表現を示す概略図である。
【図２】既に説明しており、８分木データ構造の全体像を示す概略図である。
【図３】本発明の一実施形態による、点群を符号化するステップを示す流れ図である。
【図４】本発明の一実施形態による、点群を再構築するステップを示す流れ図である。
【図５】本発明の一実施形態による符号器を示す概略図である。
【図６】本発明の一実施形態による復号器を示す概略図である。
【発明を実施するための形態】
【００５２】
好ましい実施形態の詳細な説明
本発明の一実施形態による、点群を符号化する方法を図３の流れ図に示す。
【００５３】
点群ＰＣの点は、幾何学的配置、即ち各点の空間位置及び例えば色等の点の少なくとも別の属性を含むその属性によって特徴付けられる。以下の説明では点群の各点が、３Ｄ空間内の幾何学的配置ｇ及びＲＧＢ空間内の色ｃという２つの属性を有すると仮定する。
【００５４】
ステップ２で、点群データを幾つかのクラスタに分類する。殆どの点群データが区分線形挙動を有することが概して認められているので、このクラスタリングの結果、各クラスタ内の点群データが線形関数によって近似され得る。
【００５５】
このクラスタリングは従来技術による任意のクラスタリング方法によって実行することができる。
【００５６】
有利には、このクラスタリングは、点群の点の全ての属性間の類似度を考慮するために本実施形態に従って修正される正規化カット技法を使用して実行される。
【００５７】
従ってクラスタリングを実行するとき、多面的な関係が考慮される。つまり、区分線形特性を最適な方法で活用するクラスタリング結果を実現するために、幾何学的配置及び色等の他の属性の両方の類似度を考慮して点群を区分化する。
【００５８】
ステップ２の終わりにおいて、点群ＰＣは対応するインデックスによって識別される複数のクラスタＣｉへとクラスタリングされており、１≦ｉ≦Ｎであり、Ｎは得られたクラスタの数である。クラスタのインデックスは、クラスタごとに一意のインデックスが割り当てられることを確実にしながら無作為に割り当てられる。
【００５９】
次いでステップ４で、クラスタごとに類似度グラフを構築する。この類似度グラフはクラスタの隣接する頂点、即ち点間の類似度を表し、クラスタのコンパクト表現を取得することを可能にする。
【００６０】
グラフＧ＝｛Ｖ，Ｅ，Ｗ｝は、濃度｜Ｖ｜＝Ｎを有する１組の有限の頂点Ｖ、頂点を接続する１組の辺Ｅ、及び重み付き隣接行列Ｗで構成される。ＷはＮｘＮの実行列であり、ｗｉ，ｊは頂点Ｐｉ及びＰｊを接続する辺（ｉ，ｊ）に割り当てられる重みである。ここでは対称重み付き隣接行列、即ちｗｉ，ｊ＝ｗｊ，ｉに対応する無向グラフだけを検討する。重みは非負、即ちｗｉ，ｊ≧０だと仮定する。
【００６１】
ステップ４で構築した類似度グラフにおいて、頂点Ｐｉ及び頂点Ｐｊ間の重みｗｉ，ｊは
【数１】
2020521359.tif 000003
として割り当てられ、ｇｉ及びｇｊはそれぞれ座標ベクトル、即ちｇｉ＝（ｘｉ，ｙｉ，ｚｉ）Ｔ及びｇｊ＝（ｘｊ，ｙｊ，ｚｊ）Ｔであり、ｃｉ及びｃｊはそれぞれ色ベクトル、即ちｃｉ＝（ｒｉ，ｇｉ，ｂｉ）Ｔ及びｃｊ＝（ｒｊ，ｇｊ，ｂｊ）Ｔである。この公式では｜｜ｇｉ−ｇｊ｜｜２は幾何学的配置の類似度を示し、｜｜ｃｉ−ｃｊ｜｜２は色の類似度を示す。
【００６２】
σは重みの値を制御するために使用されるパラメータであり、しばしば経験的に設定される。
【００６３】
このようにして、構築されるグラフにおいて幾何学的配置情報及び色情報の両方が考慮され、これは１つの属性の類似度しか考慮しない辺の重みの通常の定義と異なる。
【００６４】
好ましい実施形態によれば、及びスパース表現に関する接続された頂点の数を減らすために、閾値ｔを使用して小さな重みを以下のように０に設定する：
ｗｉ，ｊ＜ｔが成立する場合、ｗｉ，ｊ＝０  （２）
【００６５】
このようにして、符号化ビットを節約するために小さな重みは符号化しない。更に、これらの重みは小さく、接続された頂点が或る程度異なることを意味するので、これらの重みを０に設定することは符号化の質を殆ど落とさない。
【００６６】
従ってグラフは以下のように構築される。
【００６７】
クラスタの点Ｐｉごとに、点Ｐｉ及びクラスタ内の他の任意の点Ｐｊ間のあり得る辺の重みを方程式（１）に従って計算している。ｗｉ，ｊ＞＝ｔが成立する場合、Ｐｉ及びＰｊ間の辺ｅｉ，ｊを追加し、計算済みの重みｗｉ，ｊをその辺に付加し、さもなければ小さな重みはそれらの点の間に大きな相違があることを意味するのでＰｉとＰｊとの接続を解除する。
【００６８】
次いでステップ６で、構築した類似度グラフに基づいてクラスタごとにＧＦＴを計算する。このステップにおいて、グラフの重みから重み付き隣接行列が得られる。
【００６９】
次いでグラフのラプラシアン行列を計算する。
【００７０】
ラプラシアン行列の様々な改変形態が存在する。
【００７１】
一実施形態では、Ｌ：＝Ｄ−Ｗとして定められる非正規化組合せグラフラプラシアンを使用し、Ｄはそのｉ番目の対角成分がＷのｉ番目の行内の全ての成分の和、即ち
【数２】
2020521359.tif 000004
である対角行列として定められる次数行列である。ラプラシアン行列は実対称行列なので、ラプラシアン行列は、１組の完全な正規直交固有ベクトル｛Ψｌ｝ｌ＝０，１，．．．，Ｎ−１と共に１組の実固有値｛λｌ｝ｌ＝０，１，．．．，Ｎ−１を認め、即ちｌ＝０，１，．．．，Ｎ−１ではＬΨｌ＝λｌΨｌである。
【００７２】
一実施形態では、このラプラシアン行列を２つの理由で採用する。
【００７３】
まず、Ｌの各行内の成分の和は構造によって０になるので、対応する固有ベクトルとしての［１．．．１］Ｔと共に０が固有値であることが保証される。このことはＧＦＴの周波数解釈を可能にし、固有値λｌはグラフ周波数であり常にＤＣ成分を有し、これは多くの平滑領域で構成される点群データを圧縮するのに有益である。類似する点を接続し異なる点の接続を解除することによって高周波係数（high-frequency coefficient）が低減され、そのことはＧＦＴ領域内の点群のコンパクト表現につながる。
【００７４】
第２に、全ての辺の重みが１に等しい状態で、（１Ｄ  ＤＣＴに対応する）線グラフ又は４接続グラフ（２Ｄ  ＤＣＴ）について定められる場合、ＧＦＴはデフォルトで良く知られているＤＣＴとなる。つまり、このように重みを選択した場合、ＧＦＴはスパース信号表現において少なくともＤＣＴと同程度優れている。上記の２つの所望の特性により、以下の段落の中で説明するように、ＧＦＴを定義するために非正規化ラプラシアン行列を使用する。
【００７５】
ＧＦＴを定義するために、ラプラシアン行列の固有ベクトル｛Ψｌ｝ｌ＝０，１，．．．，Ｎ−１を使用する。形式的に、Ｇの頂点上にある任意の信号ｘ∈ＲＮについて、その
【数３】
2020521359.tif 000005
は次式
【数４】
2020521359.tif 000006
として定められ、
【数５】
2020521359.tif 000007
はｌ番目のＧＦＴ係数であり、ここでｘ（ｎ）は点群の点ｎの属性を指す。
【００７６】
クラスタごとに、得られるＧＦＴがＧＦＴインデックスによって識別される。
【００７７】
従って、ステップ６はＧＦＴ係数及びＧＦＴインデックスをもたらす。
【００７８】
次いでステップ８で、ＧＦＴ係数を量子化する。
【００７９】
ステップ１０で、例えばMarpe: “Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard”, IEEE Trans. Cir. and Sys. For Video Technol., vol.13, no.7, pages 620-636, 2003の中で記載されているＣＡＢＡＣ法を使用することにより、量子化済みのＧＦＴ係数をエントロピ符号化する。
【００８０】
更にステップ１０で、クラスタインデックス及びＧＦＴインデックスによって構成されるオーバヘッドをエントロピ符号化してどのＧＦＴがどのクラスタに使用されるのかを示す。次いでステップ１２で、符号化済みのＧＦＴ係数、クラスタインデックス、及びＧＦＴインデックスを復号器に伝送する。
【００８１】
図４は、本開示の一実施形態による点群を再構築するステップ、即ち符号化済みのＧＦＴ係数、クラスタインデックス、及びＧＦＴインデックスを受信した後で復号器によって実施される復号ステップを示す。
【００８２】
ステップ２０で、受信したＧＦＴ係数、クラスタインデックス、及びＧＦＴインデックスをエントロピ復号する。
【００８３】
次いでステップ２２で、復号したＧＦＴ係数を逆量子化する。
【００８４】
ステップ２４で、逆量子化したＧＦＴ係数及び復号したＧＦＴインデックス（適用済みのＧＦＴを示す）を使用して逆ＧＦＴを実行する。
【００８５】
逆ＧＦＴは
【数６】
2020521359.tif 000008
によって得られ、但しｘは各クラスタの点群データを表す回復済みの信号である。
【００８６】
一実施形態によれば、グラフフーリエ変換は以下のように計算し、点群内の各点はグラフ内の頂点として扱う。
【００８７】
まず、各点をその近傍にそれらが類似する限り接続する。各点と近傍との間に大きな相違がある場合は２点の接続を解除する。
【００８８】
第２に、接続グラフを所与として隣接行列Ｗを定め、頂点ｉ及びｊが接続される場合はｗｉ，ｊ＝ｗｊ，ｉ＝１であり、さもなければ０である。次いで次数行列Ｄを計算する。
【００８９】
第３のステップで、計算済みの行列Ｗ及びＤを使用し、Ｌ＝Ｄ−Ｗとしてグラフラプラシアン行列を計算する。Ｌの固有ベクトルＵはＧＦＴの基底ベクトルである。最後に点群の点の属性を列ベクトル内にスタックし、方程式３及び４に従ってＧＦＴ及び逆ＧＦＴを計算する。
【００９０】
類似する点を接続し異なる点の接続を解除することによって高周波係数が低減され、そのためＧＦＴ領域内の点群のコンパクト表現につながる。
【００９１】
図５は、本開示の符号化方法を実装する符号器３０の例示的実施形態のブロック図である。
【００９２】
有利には、符号器３０は１つ又は複数のプロセッサ及びメモリ３２を含む。
【００９３】
符号器３０は、
−点の属性に基づいて点群を点のクラスタへと区分化するように構成される区分化モジュール３４と、
−属性に関してクラスタの隣接点間の類似度を表す類似度グラフをクラスタごとに構築するように構成される構築モジュール３６と、
−構築された類似度グラフに基づいてグラフフーリエ変換、ＧＦＴをクラスタごとに計算するように構成される計算モジュール３８であって、ＧＦＴはその係数によって特徴付けられる、計算モジュール３８と、
−ＧＦＴ係数を符号化するように構成される符号化モジュール４０と
を含む。
【００９４】
符号器３０は、符号化済みのＧＦＴ係数並びにクラスタの識別情報及び計算済みのＧＦＴの識別情報を復号器に伝送するように構成される送信機４２も含む。
【００９５】
記載の実施形態によれば、バス４４が符号器３０の様々な要素間の通信経路を提供する。他の２点間相互接続の選択肢（例えば非バスアーキテクチャ）も可能である。
【００９６】
図６は、本開示の再構築方法を実装する復号器５０の例示的実施形態のブロック図である。
【００９７】
有利には、復号器５０は１つ又は複数のプロセッサ及びメモリ５２を含む。
【００９８】
復号器５０は、
−クラスタインデックス及びＧＦＴインデックスに関連するＧＦＴ係数を含む符号化済みのデータを受信するように構成される受信機５４と、
−受信されたデータを復号するように構成される復号モジュール６６と、
−クラスタごとに逆ＧＦＴを実行することによってクラスタを再構築するように構成される再構築モジュール５８と
を含む。
【００９９】
記載の実施形態によれば、バス６０が復号器５０の様々な要素間の通信経路を提供する。他の２点間相互接続の選択肢（例えば非バスアーキテクチャ）も可能である。
【０１００】
本発明の好ましい実施形態だと現在考えられる内容を図示し説明してきたが、本発明の真の範囲から逸脱することなしに他の様々な修正を加えることができ、等価物を置換できることを当業者なら理解されよう。加えて、本明細書に記載した本発明の主要概念から逸脱することなしに、本発明の教示に特定の状況を適合させるために多くの修正を加えることができる。更に、本発明の実施形態は上記の特徴の全てを含まなくてもよい。従って、開示した特定の実施形態に本発明を限定することは意図せず、本発明は添付の特許請求の範囲に含まれる全ての実施形態を含むことを意図する。
【０１０１】
「含む（comprise）」、「含む（include）」、「組み込む（incorporate）」、「含有する（contain）」、「である（is）」、及び「有する（have）」等の表現は、この説明及び関連する特許請求の範囲を解釈するとき非排他的方法で解釈すべきであり、つまり更に存在することが明確に定められていない他のアイテム又は構成要素を認めるように解釈すべきである。単数形の言及は複数形の言及とも解釈すべきであり、その逆も同様である。
【０１０２】
本発明の範囲から逸脱することなしに、本明細書で開示した様々なパラメータを修正できること、並びに開示し及び／又は特許請求の範囲に記載した様々な実施形態を組み合わせることができることを当業者なら容易に理解されよう。
【０１０３】
例えば、記載したグラフ変換がＧＦＴでも、例えばElsevier: Applied and Computational Harmonic Analysis, vol.30, April 2010, pp.129-150内のD. Hammond, P. Vandergheynst、及びR. Gribonval, “Wavelets on graphs via spectral graph theory”に記載されているwavelets on graphs、及びPh.D. dissertation, University of Southern California, 2010内のG. Shen, “Lifting transforms on graphs: Theory and applications”に記載されているlifting transforms on graphs等の他のグラフ変換を使用することもできる。
【図１】
2020521359.tif 000009
【図２】
2020521359.tif 000010
【図３】
2020521359.tif 000011
【図４】
2020521359.tif 000012
【図５】
2020521359.tif 000013
【図６】
2020521359.tif 000014
【国際調査報告】
2020521359.tif 000015
2020521359.tif 000016
2020521359.tif 000017