3D Point Cloud Compression (3次元点群圧縮) とは？

この記事について

• この記事では、点群圧縮に関連する技術、すなわち変換、量子化、エントロピー符号化などに注目して個人的に整理した内容をまとめています。
• 点群圧縮の手法の中でもDeep Learningに基づく方法については本記事の範囲外とし、後日別の記事を作成します。

Introduction : 3D点群データ圧縮技術の概要と重要性

3D点群データは、建築、ロボティクス、医療、地理情報システム（GIS）など、幅広い分野で活用される重要な情報源です。これらのデータは高精度な3次元空間情報を提供する一方で、その膨大なデータ量が通信、処理、保存における大きな課題となっています。この課題に対処するため、効率的な点群データ圧縮技術の開発が急務とされています。

点群圧縮技術は、データの空間的・時間的冗長性を削減し、情報の精度を保ちながらデータサイズを劇的に削減することを目指します。これにより、ストレージ容量の節約やネットワーク伝送効率の向上が可能となり、リアルタイムアプリケーションやリソース制約のある環境での利用が現実的になります。

Ford Media Center

多様な分野における3Dデータの有効活用を支える基盤として、今後さらに重要性を増す当該技術について、本記事を通じて、その技術的な全体像と可能性について（私自身が勉強したことをアウトプットする場として活用しつつ、）解説していきたいと思います。

なお、本記事は、以下の論文を参考に作成されています。記事内で理解しきれなかった、詳細が気になる箇所があれば、ぜひ元の論文を読んでみてください。

参考文献

1. Quach, M., Pang, J., Tian, D., Valenzise, G., & Dufaux, F. (2022). Survey on Deep Learning-Based Point Cloud Compression. Frontiers in Signal Processing, 2.
2. Point Cloud Compression: Technologies and Standardization, 英語版 Ge Li (著), Wei Gao (著), Wen Gao (著)

1. 点群データとは？

• 点群(Point Cloud)は、x, y, z座標と色、法線、反射率などの 属性(attributes) を持つ点の集合です。点群データは、各点の位置を示すジオメトリ部分と、各点に付随する追加情報である属性部分の2つの要素に分割できます。また、時間的次元を持つ点群は 「dynamic point cloud(動的点群)」 、時間的次元を持たない点群は 「static point cloud(静的点群)」 と呼ばれます。

  
  出典：参考文献1(図1)

• 点群には無秩序性や不規則性といった2D画像データには無い特性があり、点群圧縮技術の開発において大きな課題をもたらしています。空間的に分布する点群データには、画像のピクセルに相当するような規則的な単位が存在せず、点群の空間的な相関関係を活用するのが難しいため、冗長性を取り除いて圧縮することが困難です。
• 点群の無秩序性（順序性がないこと）は、 順列不変性（Permutation Invariance） とも呼ばれます。つまり、点群内の点の順序が変わっても、データの表現には影響を与えません。これは、ピクセルが固定された順序で配置される2D画像データとは本質的に異なります。

• 無秩序性や不規則性に加え、点群には変換不変性、局所的相関性、および高い計算複雑性という特性もあります。

  • 変換不変性：点群が表現する対象物は、剛体変換（平行移動や回転を含む）によって変化しません。
  • 局所的相関性：3D空間内の点の位置情報とその周辺の点に関する情報は意味を持ち、点群の形状を特徴付けるために使用できます。
  • 高い計算複雑性 ：
    • 点群は高次元データであり、各点は3次元以上の情報を持っています。
    • 実用的な観点では、点群内の膨大な点の数が、点群の圧縮や処理手法に高い複雑性をもたらします。

2.情報理論のお話 (スキップ可)

情報理論は、点群圧縮に限らず、情報圧縮を語る上で重要な基礎知識です。本記事では、詳細は割愛しますが、気になる方は調べてください。
キーワード : 情報量 · 符号化 · エントロピー

ちなみに私は、下記の書籍で学習しました。

情報量

• 情報量とは、不確実性の低減度合いを表す尺度です。情報量 $ I(x) $ は、ある事象 $ x $ の発生確率 $P(x)$ を用いて次のように定義されます：

  I(x) = -\log_2 P(x)
  

• 発生確率が低いほど、得られる情報量は大きくなります。

エントロピー（平均情報量）

• エントロピー $ H(X) $ は、ランダム変数 $ X $ の不確実性の平均的な度合いを示します。離散的な確率分布を持つ $ X $ に対して、次のように定義されます：

  H(X) = -\sum_{x \in X} P(x) \log_2 P(x)
  

• エントロピーは、情報源が生成するデータの平均情報量（情報量の期待値）を表し、その単位は ビット (bit) です。

• 【補足】ランダム変数$X$とは、確率空間において各事象（結果）に対して数値を対応付ける関数です。例えば、サイコロを振る場合、ランダム変数 $X$ を「出た目」とすると、値の集合は$ \lbrace1,2,3,4,5,6\rbrace$になります。

平均符号長

• 符号化アルゴリズムで使用される符号語の平均長さ $ L $ を示します。これは、各シンボル(=記号)の発生確率 $ P(x) $ と対応する符号語の長さ $ l(x) $ を用いて次のように計算されます：

  L = \sum_{x \in X} P(x) l(x)
  

• 効率的な符号化では、この平均符号長がエントロピーに近づきます。

情報源符号化定理

• 情報源符号化定理は、ランダム変数 $ X $ を符号化する際に必要な平均符号長 $ L $ の下限を示します。この定理によれば、次が成り立ちます：

  H(X) \leq L < H(X) + 1
  

• この定理は、理想的な符号化ではエントロピーに非常に近い平均符号長が実現可能であることを意味します。

この定理から， 「記号列を忠実に復元できるようにビット列で表現する際に， 情 報源出力 1記号あたりに用いるビット数をどこまで小さくできるか」 という工学 的な問題に対する答えが， エントロピーという， 符号化とは無関係に定義される 情報理論的な量で与えられることがわかる．
(楫勇一. OHM大学テキスト　情報・符号理論 (p.104). Kindle 版. )

3. 点群圧縮技術(PCC)について

• 点群データの特性に基づき、点群圧縮はジオメトリ(geometric)圧縮と属性(attribute)圧縮に分けられます。通常、ジオメトリ座標がまず符号化され、次にジオメトリ座標が再構築された後に属性情報が符号化されます。

  
  出典：参考文献2（図2.2, 2.3）

• 上図のように、点群ジオメトリ圧縮のパイプラインは、従来の画像や動画の符号化パイプラインとは異なります。具体的には、点群ジオメトリを最初に量子化し、ジオメトリデータに対して変換を適用しない点が特徴です。一方、点群属性圧縮のパイプラインは、予測、変換、量子化、エントロピー符号化といったモジュールを含む点で、従来の画像や動画の符号化パイプラインに類似しています。

• 様々な手法を用いて、下記のようなデータ間の冗長性を削減することが、点群データの圧縮効率を向上させる鍵となります。

  • 空間的冗長性（Spatial Redundancy）：隣接する点が似た情報を持つことで生じる冗長性。
  • 時間的冗長性（Temporal Redundancy）：動的な点群データにおいて、フレーム間でデータが重複することで生じる冗長性。
  • 情報エントロピー冗長性（Information Entropy Redundancy）:データ内で特定の情報が頻繁に出現することで生じる冗長性。

3.0.1. 3D点群圧縮の国際標準方式について

国際標準化団体MPEG（Moving Picture Experts Group） は、効率的な3D点群圧縮技術への需要に対応すべく、点群データの圧縮における標準方式を策定しました。

1. G-PCC (Geometry-based Point Cloud Compression)
   ジオメトリデータ（形状情報）を中心に圧縮する方式。
   静的点群の圧縮に適しており、高いジオメトリ精度を実現。
2. V-PCC (Video-based Point Cloud Compression)
   点群データを2D画像に変換して圧縮する方式。
   動的点群の圧縮に適しており、既存のビデオ圧縮技術を活用可能。

KDDI総合研究所

3.0.2. 点群データの表現について

点群データは、その特性に応じて1~4次元までの構造で表現・圧縮されます。それぞれの次元表現は、異なる処理方法や応用が可能であり、特定の要件に応じて適切に選択されます。

2次元構造（2D Structure）

• 点群を画像形式に投影して表現する方法。特にビデオベースの点群圧縮（V-PCC）で広く使用されます。占有画像、ジオメトリ画像、属性画像などの2Dデータを生成します。

• まず、点群(a)を小さな3Dパッチ(3D点群データを小さな領域（部分集合）に分割したもの)に分割するします。その後、パッチを2D平面に投影し、以下のような画像を生成します。
  
  出典：参考文献2(図2.8,(Copyright © 1988–2024, www.mpeg.org))

  • (b)占有画像（occupancy image）：パッチ位置を記録。0と1でピクセルの占有状態を表す。
  • (c)ジオメトリ画像（geometry image）：表面点から投影平面までの深さを記録。
  • (d)属性画像（attribute image）：色や反射率などの属性情報を記録。

3次元構造（3D Structure）

• 点群のジオメトリ情報を占有コード（occupancy code）として効率的に表現する方法。オクツリー（octree）、クアッドツリー（quadtree）、バイナリツリー（binary tree）などの木構造が用いられます。

• オクツリー（Octree）
  
  TraumaBot - 3D body reconstruction & recognition: Octree based point cloud stream compression in PCL

  • ノードを再帰的に8つのサブノードに分割。すべてのリーフノードが1点のみを含む状態になるまで処理。

  • 占有コードを使用して各ノードの状態（占有・非占有）を記録。

  • 特徴

    • 空間構造の提供により、近傍探索や空間分割が容易。
    • 階層構造により、異なるレベルでの特性を取得可能。
    • 分割を特定のレベルで停止することで、異なる精度の表現が可能。

2次元構造は従来の画像圧縮技術との親和性が高く、応用範囲が広いのに対して、3次元構造は空間の正確な表現と効率的な探索を可能にし、高精度な解析に適しているという特徴があります。また、1次元構造および4次元構造は、それぞれ簡易的な圧縮処理と(時間の概念を導入した)動的データの処理に特化しています。

ここからは、3. 点群圧縮技術(PCC)についてにて引用した図(Fig.2.2& 2.3 -> [Quantization]やら[Prediction]やら書いてあるやつ)に対応するPCCを構成する要素について解説します。

3.1. 予測符号化（Predective Coding）

• 予測符号化とは、前段までで符号化した情報を用いて、現在符号化する情報を推定することを指します。
• 一般的に、予測プロセスでは現在の信号の値から予測値を差し引き、残差を得ます。予測後、残差は元の信号よりも小さくなり、符号化すべき情報量を削減することで圧縮の目的（=データ量の削減）を達成します。
• ジオメトリー及び、属性の予測において、前節で記載したデータ表現に対応して、異なる方法がとられます。
  • 1次元予測ツリー(one-dimensional predictive tree)
    • データをツリー構造で管理し、親や祖先の情報を使って予測します。簡単で処理が軽いのが特徴です。
  • 2次元マッピング画像(two-dimensional mapped
    images )
    • 点群を画像形式に変換し、画像や動画圧縮技術（例えば、動き予測や角度予測）を使って圧縮します。
  • 3次元構造オクツリー(three-dimensional octree)

    • 隣接ノード(点)を用いて、符号化対象ノードが占有されているかどうかを予測したり、占有コードのエントロピー符号化（後述）を最適化します。

    • 3次元構造に基づく属性予測は通常、以下のステップで行われます：

      1. 予測順序を構築し、ソートされた各点が近傍の点と類似した属性を持つようにする。
      2. 幾何学的に最も近い点を探索して参照点を見つける。
      3. 各種戦略に基づき、属性予測値を計算する。

• 静的な点群には空間的な相関が存在し、動的な点群では隣接するフレーム間に時間的な相関が存在します(下図)。また、予測(符号化)は、その適用範囲に基づいて、イントラ予測（intra-prediction） と インタ予測（inter-prediction） に分類されます。イントラ予測は、単一(フレーム)の点群内の近隣情報の類似性を利用して空間的冗長性を除去します。一方、インタ予測は、連続した点群のシーケンスにおける連続性を活用して時間的冗長性を削減します。(冗長性については上述)

  
  出典：参考文献2（図3.1, (Copyright © 1988–2024, www.mpeg.org ))

• 効率的な予測技術は、点群の冗長性を削減し、変換符号化、量子化、エントロピー符号化といった後続プロセスのための優れたデータ基盤を提供します

3.1.1 Intra Prediction

◾️ ジオメトリ情報の予測 (ex. オクツリー)

(ここではオクツリーに限定して記述しますが、1次元予測ツリーにもイントラ予測は適用できます。(点群データの表現については上述))

• 3D点群を圧縮する際、オクツリー構造を使って空間を分割し、その中のノードが点を含むかどうかを 占有コード で表します（1 は占有、0 は非占有）。これを効率的に符号化するために 予測(本節) と エントロピー符号化(3.4節) を用います。

• 符号化済みノードの占有状態を利用して、符号化対象ノードの占有コードを予測します。

  • 例えば、符号化済みの近くのノードがすべて占有されている（1）場合、符号化対象ノードも占有されている可能性が高いと予測できます。
  • 同じ点群内の隣接ノードや親ノードとその子ノードの間には高い相関性が存在します

  
  TraumaBot - 3D body reconstruction & recognition: Octree based point cloud stream compression in PCL

占有コードの予測の基本的な流れ

1. 符号化済みの近隣ノード の占有状態（パターン）を集め、それを分類します。
   • 例えば、近くに占有されているノードが2つある場合と3つある場合では、符号化対象ノードの予測方法(アルゴリズム)が異なるかもしれません。
2. これらの分類に基づいて、符号化を最適化するための ルール（コンテキストモデル） を設計します。
3. 占有コードを符号化するときに、予測された結果と実際の符号化対象ノードの状態との差（予測残差）を使います。
4. この差を利用して、エントロピー符号化をより効率的に行い、圧縮率を向上させます。

【※補足】コンテキストモデル

• コンテキストモデル は、データのコンテキスト情報（周辺の文脈や状況）を考慮して符号化効率を向上させるためのアルゴリズムやルールの集合です。
• この場合、符号化対象ノードの周りにある近隣ノードの占有状態がコンテキストになります。
• 近隣ノードの占有パターンを分類し、その分類に基づいて符号化方法を最適化します。
• また、近年はDeep Learningを用いて圧縮を行う技術の研究が多く行われており（別で記事を作成します）、占有パターンを明示的に分類し、それに基づいて符号化方法を決定する（ルールベース）のではなく、モデルが占有パターンを自動的に学習し、分類と符号化方法の最適化をエンドツーエンドで実行する場合もあります。
• Deep Learningでは、占有状態だけでなく、点群の幾何的な特徴 （距離、方向、密度など） を含めた多次元のコンテキスト情報を学習に利用できます。ルールベースの手法よりも柔軟に複雑なパターンを捉えることが可能です。

◾️ 属性情報の予測

• 属性イントラ予測は、点群データ内の属性（例：色や強度）の空間的な類似性を利用して冗長性を減らす方法です。
• 属性情報の予測はジオメトリ情報に依存します。
• 再構築されたジオメトリ情報を基に空間内で最も近い点を見つけ出します。

1. 予測順序の生成

   • 点群は不規則に分布しているため、空間的に近い点が予測順序でも隣接するように並べ直します。代表的な手法には、空間充填曲線（Hilbert順序やMorton順序）や詳細レベル（LoD）構造を利用する方法があります。

2. 近隣点の選定

   • 予測は順序に従って1点ずつ行います。現在の点に最も近い符号化済みの点を近隣点として選びます。距離の測定にはマンハッタン距離やユークリッド距離を使用します。

3. 予測値の計算

   • 最も簡単な方法は、直前の点の再構築された属性値を予測値として使用することです。
   • より高度な方法では、最も近い1点または複数の近隣点（k近傍点）を利用し、これらの属性値を加重平均して予測値を計算します。
   • この際、近隣点との距離を重みに利用し、より正確な予測を行います。

4. 誤差（残差）の計算と符号化

   • 予測値と元の属性値との差（残差）を計算し、この残差を量子化して冗長性をさらに削減します。残差は復号時に元の属性値を再構築するために使用されます。

5. レート・歪み最適化（RDO, Rate Distortion Optimization)

   • 最適な予測モードを選択するために、残差と符号化ビット数を考慮したスコアを計算し、スコアが最小となるモードを採用します。

【コメント】　Attribute Compression の論文はあまり読んだことがないので、最近の論文を読みたい

3.1.2 Inter Prediction (インタ予測)

• 連続した点群シーケンスにおいて、インタ予測は参照フレームを使用して現在のフレームとの時間的相関を利用します。この予測は、現在のフレームと既に符号化されたフレーム間での 動き推定（Motion Estimation, ME） と 動き補償（Motion Compensation, MC） に基づいて行われます。

• 動的点群の隣接フレームは、通常、平行移動、回転、拡大縮小などの複雑な3D変形を伴います。例えば、2つのオクツリーを同時に分割しても、対応するノードが必ずしも同じ物体部分を表すとは限りません。この場合、参照フレームは有効な参照を提供できません。

• 動き推定（Motion Estimation）

  • 動き推定は、2つのフレーム間の動き情報を特定するために使用されます。この動き情報は、通常動きベクトルとして記述されます。

• 動き補償（Motion Compensation）

  • 動き補償では、動きベクトルを参照フレームに適用し、現在のフレームにより近い補償フレームを生成します。
  • ここでいう「補償」とは、点群データや映像データにおいて、参照フレームに対して現在のフレームがどのように動いたかを考慮し、参照フレームを現在のフレームにできるだけ近づけるように補正する技術です。

◾️ ジオメトリ情報の予測 (ex. オクツリー)

• XOR(排他的論理和)を使う手法
  • 各ノードの占有状態（占有コード）を比較し、同じなら0、異なれば1を出力するアルゴリズムです。
    • 例: 占有コードが両方とも1なら0、片方が1で片方が0なら1。
  • 動きが連続的で類似しているフレーム間では、XORの結果に0が多くなるため、データ量を減らせます。
• 参照フレームをマッピングする手法
  • 現在のノードを参照フレームにマッピングし、近くのノードの占有状態を確認します。
  • これに基づいて、現在のノードの占有コードをより正確に予測するためのモデル（コンテキストモデル）を構築します。

◾️ 属性情報の予測

• イントラ予測は同じフレーム内の符号化済み点のみを使用していたのに対し、インタ予測は、他のフレーム（参照フレーム）にある符号化済み点も利用できます。
• まず、符号化対象の現在の点を参照フレームにマッピングします。これにより、参照フレーム内で符号化済みの点に対応付けられます。
• その後、現在の点の近くにある符号化済みの点を探索します。この探索では、計算コストを抑えるために探索範囲が制限されており、距離の計算にはユークリッド距離やマンハッタン距離が使用されます。
• 次に、探索で見つかった近隣点の属性値をもとに予測値を計算します。
• 最後に、この属性残差を符号化してデータ量をさらに削減します。

3.2. 変換符号化（Transform Coding）

• 変換符号化は、離散コサイン変換(DCT)等を用いて、信号を空間領域から周波数領域へ変換する技術です。これにより、信号の表現がよりコンパクトになり、信号内の相関を削減できます(周波数領域での値の大小は、空間領域における信号の変化の速さや複雑さによって決まります)。周波数領域の特徴 として、点群データの中には、滑らかなテクスチャやゆっくりと変化する領域が多くあります(自然界や人工物の多くは連続的で滑らかな表面を持っているため（例：地面、建物の壁、車のボディなど）)。周波数領域ではエネルギーが主に低周波数に集中するため、高周波数成分を減らすことで効率的な圧縮が可能です。

• 上記のような変換手法の他にも、いくつか主要な変換手法が存在します。例えばリフティング変換 は、MPEGによるジオメトリベースの点群圧縮標準に採用されている方法で、以下の3ステップで行います：

  • 分割（Split）
  • 予測（Prediction）
  • 更新（Update）

  従来の変換手法（例：DCTやウェーブレット変換）と比較して、リフティング変換は単純な加算や減算操作のみを含むため、計算効率が高いことが特徴です。また、

• グラフフーリエ変換（GFT） は、不規則なデータ（点群など）の解析に適した変換方法です。グラフラプラシアン行列を用いて、空間領域から周波数領域へ変換し、よりコンパクトなデータ表現を得られます。

3.3. 量子化(Quantization)

• 量子化は、連続的な実数データ（属性値）を有限個の離散的な値に変換するプロセスで、データ量を削減するための手法です。量子化レベルが高く（量子化ステップサイズが大きい）なるほど、圧縮率は向上しますが、歪みも大きくなります。そのため、圧縮率(compression rate) と 歪み(distortion) のバランスを取ることが重要です。

• ジオメトリを量子化する場合は、点群の座標を小さい範囲にマッピングすることで、データ量を削減します（正規化等の前処理を必要とする場合もあります）。

  とっても単純な例

      (before)
          点1: (1.23, 2.47, 3.89)
          点2: (4.56, 5.34, 6.78)
          点3: (7.89, 8.12, 9.45)
                     ||||
                     VVVV
      (after)
          点1: (1, 2, 4)
          点2: (5, 5, 7)
          点3: (8, 8, 9)
  

  • データ量の削減：
    元の座標は浮動小数点数（例えば32ビット）で表現されていますが、量子化後は整数値（例えば16ビット以下）で表現可能です。
    これにより、ストレージの使用量が減少します。
  • 歪みの発生：
    元の座標と量子化後の座標との間に誤差が生じます。
    例えば、点1のZ座標は元々3.89でしたが、量子化後は4に丸められています。この誤差（0.11）は歪みとして現れます。

• 属性を量子化するばあいは、RGBや反射強度などの属性値を一定の範囲ごとに分けて近似的な値に置き換えることで、データ量を削減します。例えば、RGBカラー情報を持つ点群の場合、256段階（0～255）で表現される色の値を、より少ない段階（例えば16段階）に丸め込むことで、データの容量を減らします。

3.4. エントロピー符号化(Entropy Coding)

【コメント】 手法が多岐に渡り、理解するのに理解するのに苦労しました。しかし、基本的なアイデアを抑えることで、様々なアプローチを俯瞰できるようになりました。（情報理論大事）

下記の記事では、エントロピー符号化の概要をわかりやすくまとめてくださっているので、ぜひご一読ください。

もっと詳細に知りたい方向けの記事(英語)

ただ、今回の記事は著者の知識を整理する目的を大いに含んでいるので、私なりにもまとめてみたいと思います。

【本題】

• エントロピー符号化とは、入力シンボルの列を損失なく圧縮してビットストリームに変換する技術のことです。シンボルあたりの平均ビット数を可能な限り小さくすることをモチベーションとしています。
• 情報理論のお話を思い出すと、シンボルを符号化するには、平均して少なくともエントロピー$H(X)$ビットが必要になります。しかし、これはあくまで理論的な限界を示すものであり、これを満たす具体的な符号化手法は設計されていません。

基本的なアイデア

下記にいくつかの具体例を示しますが、様々な符号化手法が提案されていますが、エントロピー符号化の基本的なアイデアは、頻繁に現れる文字には短い符号語を割り当て、逆に、あまり出現しない記号に長い符号語を割り当てることです。これにより、全体の平均符号語長が短くなります。

--具体例を眺めてみます--

ハフマン符号化

• 各シンボルの出現頻度に基づいて符号語を割り当てる圧縮方法です。頻繁に出現するシンボルには短い符号語が割り当てられます。
• 例：データ「AABBBBCC」で、A=2回, B=4回, C=2回の場合、A=10, B=0, C=11のように符号化できます。
• 効率的な符号化が可能ですが、符号語表（ハフマン木）を保存する必要があり、大規模なデータには不向きです。

算術符号化

• 入力シンボル列全体を1つの数値区間にマッピングし、より効率的に圧縮する方法です。
• 出現確率に応じて符号語の長さを動的に調整し、平均符号語長をエントロピーに非常に近づけます。
• 例：データ列「ABBB」は、A=0.2, B=0.8の確率を考慮して、小数点の区間「0.2~0.36」のように符号化されます。
• 高い圧縮率を実現しますが、計算コストが高いのが課題です。

【余談】ハフマン符号かと算術符号化について実用的な面での話

• ハフマン符号化はその仕組み上、任意の情報源に対して平均符号語長を最小とすることができるという特徴があります(証明は，韓太舜，小林欣吾：情報と符号化の数理，培風館（1999） などを参照のこと)が、実用上の問題点として、以下のようなものが挙げられます。(参考)

  1. 記号と符号語の対応表が必要
     情報源の記号数が多い場合、大量の記憶容量が必要になる。

  2. 情報源の確率分布が必要
     符号化器・復号器の構築に際し、情報源の確率分布が事前に必要。

  3. 拡大情報源への応用
     1記号ずつ符号化するのではなく、複数記号をまとめて符号化（拡大情報源(=元の情報源から出力される記号をまとめたものを新しい情報源とみなしたもの)の符号化）した方が効率的ですが、記号数が指数的に増加するため、拡大次数(=複数の記号をまとめて符号化する際に、まとめる記号の数)が大きい場合は現実的ではありません。

• これに対して、算術符号は以下の利点を持ちます：

  1. 逐次的な演算により符号語を生成し、記号列全体の符号語を事前に計算・保持する必要がない。
  2. 記号列の長さを十分に大きくすることで、平均符号語長を情報源のエントロピーに近づけることが可能。
  3. 符号化・復号が効率的に行えるアルゴリズムが提案されている。

ランレングス符号化

• 同じ値が連続して繰り返されるデータを効率的に圧縮する方法です。
• 例：データ列「AAAABBBCC」があれば、「4A3B2C」といった形式に変換します。
• 点群圧縮では、データをバイナリ形式に変換する際に使用されることがあります。

CABAC（コンテキスト適応型バイナリ算術符号化）

• 算術符号化の一種で、データの文脈（コンテキスト）を考慮して圧縮率を高める方法です。
• データの局所的な特徴に基づき、それぞれのシンボルが出現する確率を動的に推定し、高効率な圧縮を実現します。
• MPEGやAVSで採用されており、特に動画や点群の圧縮で重要な役割を果たします。

ANS（非対称数体系符号化）

• 算術符号化に似た手法ですが、計算コストが低く、実装が簡単なのが特徴です。
• 高い圧縮率を保ちながら、処理速度を向上させることができ、リアルタイムのデータ圧縮に向いています。
• 比較的新しい技術で、動画や点群データの圧縮で注目されています。

4. まとめ

• 本記事では、点群データ圧縮における基礎的な技術から最新の国際標準規格、さらに具体的な符号化手法までを解説しました。点群データの無秩序性や高次元性といった特性が、圧縮技術の開発において大きな挑戦であるからこそ、挑戦する価値がある分野であると思いました。

• 個人的には、やろうやろうと思ってこれまでできていなかった、変換、量子化、エントロピー符号化などの基本要素について体系的に整理したことで、点群圧縮の全体像が把握できたかと思っています。

• 本記事が、点群圧縮技術の理解を深める一助となれば幸いです。