Zenn
👌

【読書メモ】詳解 3次元点群処理 Pythonによる基礎アルゴリズムの実装

2022/12/12に公開
機械学習
pointcloud
tech

詳解 3次元点群処理 Pythonによる基礎アルゴリズムの実装を読みました。
点群が中心ですがその他の3次元データ処理についても基礎から丁寧にかつPythonでの扱い方まで解説されており、点群の入りには最適な一冊です。
本記事では中心となるトピックやキーワードを備忘録的にメモしています。

環境構築

本家リポジトリ

https://github.com/3d-point-cloud-processing/3dpcp_book_codes

git clone --recursive https://github.com/3d-point-cloud-processing/3dpcp_book_codes

conda create -n pointcloud python=3.8

pip install open3d==0.16.1  # 最新バージョン使用

各スクリプトの実行が面倒であったため、それらを一つにまとめた勉強用Notebook(sample_notebook_chapter1-5.ipynb)を追加した自前のFolk版
https://github.com/AtsunoriFujita/3dpcp_book_codes

3次元センサ

以下の二つに大別できる。

  • ステレオ法
    • 2つの光学系の視差から奥行きを計算して3次元形状を取得する。カメラの高解像度化に伴って精緻になってきているが、反射条件が理想的であることを仮定した手法が多い（金属部品、凍った地面、霧がかかっている環境などでの計測が苦手）。
      • アクティブステレオ法：プロジェクタ（光源）とカメラを使用。光源とカメラ画素の対応を求める。
      • パッシブステレオ法：2つのカメラを使用。カメラ間の共通視野の画素対応を求める。
      • マルチビューステレオ法：多視点カメラを使用。
      • 照度差ステレオ法：複数位置の光源からの投光とカメラでの計測によって、点光源に対する反射モデルを仮定することで表面の法線方向を推定、奥行きに相当する情報を得る。
  • ToF(Time-of-Flight)
    • 光を照射して返ってくるまでの時間を計測して、光の速さと往復にかかった時間から距離を計算する。ステレオに比べて死角が少ないが、凸形状の奥の部分を計測する際にマルチパスになり、誤差を生むことがある。
    • ToFで利用する電磁波がレーザー光の場合はLiDAR、 ミリ波の場合にRADARと呼ばれたりする。
      • Direct ToF：光を照射して返ってくるまでの時間を純粋に計測する。外乱光に強い傾向。
      • Indirect ToF：時間方向に周期的なパターンで光を照射し、返ってきた光との位相差を求めることでかかった時間を計算する。比較的安価なセンサーが多い。

入出力ファイル

  • PCDフォーマット
    • Point Cloud Library(PCL)で独自に開発されたフォーマット。xyz座標以外にもRGB、法線ベクトル、曲率などの属性も持つことができる。多くの3次元ビューアで開くことができないがopen3dでは入出力関数がある。
  • PLYフォーマット
    • ポリゴンフォーマット。頂点と頂点をつなぐ面のデータで構成される（面の情報がないデータもまれにある）。

サンプリング

2次元画像は点（ピクセル）が格子状に並んでいて、すべての点は輝度やRGB値などを持っているが、3次元点群データは任意個の計測点の3次元座標データの集合となる。
計測器に近い物体の表面上の点と点は距離は小さく、遠い物体になると距離は大きくなる。また、手前の物体に遮蔽された物体の表面は計測できないので穴あきとなる。データは空間に不均一に存在し、点の数が多いからといって解像度が高いとは限らない。
点群データを整列データとして扱う一つの方法としてボクセル化がある。

等間隔サンプリングによるボクセル化

  • 2次元画像のピクセルの概念を3次元に拡張したようなものでxyz軸方向に決まった間隔で点を整列させる。2次元画像のピクセルは密に値を持っているが、計測点が存在しないボクセルは空になる（値を持たない）。
    1. 点群データのxyz座標の最大、最小値を使って直方体（バウンディングボックス）を構成し、1辺の大きさを指定して直方体に分割する（ボクセル）。
    2. 各点をボクセルに割り当てる。
    3. ボクセル内の点の平均値を求め、各ボクセル毎に0 or 1の新しい点を作成して点群データとして出力する。

Farthest Point Sampling(FPS)

等間隔サンプリングによるボクセル化では出力される点群データの点の数は事前にわからない。一方で一定数の点からなる点群を扱いたいケース（例: 深層学習による物体認識など）が存在し、点群データ全体から等間隔に離れたk個の点をサンプリングしたい時に用いられる手法。

FPSでは任意の距離を使用できる。

  1. はじめに1点をランダムに選択する。
  2. この点とすべての点との距離を計算し、最も大きな距離の点を選択する。
  3. 最初と2回目に選ばれた点と最も大きな距離の点を選択する。
  4. この操作をk回繰り返す。

Poisson Disk Sampling(PDS)

FPSは計算コストが高く、オンライン処理では適用できないこともある。高速処理できる手法としてランダムサンプリングがあるが、空間的な均一性が保証されない。PDSはランダムサンプリングに近いが、サンプリングされた2点間距離の最小値をある指定した値以下にならないように制御して空間的均一性の高いサンプリングを行う。

  1. はじめに1点をランダムに選択する。
  2. その次の点もランダムに選択する。
  3. 選択された点を中心とする半径rの球に注目し、球の中にすでにサンプリングされた点があれば、選択された点を削除する。
  4. この操作を点の数がk個になるまで繰り返す。

最新の研究事例で用いられるサブサンプリング

  • Inverse Density Importance Sub-Sampling(IDISS)
  • USIP
  • Modeling Point Clouds with Self-Attention and Gumbel Subset Sampling

など

外れ値除去

計測データにはノイズが含まれることがある。物体の境界部分がうまく計測できなかったり、鏡面反射によって誤った距離が得られることもある。Open3Dには統計的外れ値除去と半径外れ値除去が実装されている。

  • 統計的外れ値除去
    • 各点と近傍点の距離の平均を求める。平均に基づいてしきい値を決めて、近傍点との距離がしきい値以上になる点を外れ値とみなす。パラメータは近傍点の数としきい値。
  • 半径外れ値除去
    • 各点を中心とするある半径の球内の点を近傍点とみなした時に近傍点の数がしきい値未満の点を外れ値とみなす。パラメータは近傍点の数と半径。

法線推定

さまざまな点群処理で法線ベクトルはとても重要な情報になる（物体認識の特徴量に使われたり、点群の位置合わせで面と面を合わせる際に必要になる）。

法線/法線ベクトルは直線、平面に対して定義され、点に対して定義できない。点群の法線を求めるときは暗にその点群がなんらかの物体表面という曲面上に分布していると仮定する。そして各点の法線は、その点における接平面に直行するベクトルとして定義できる。

点群の法線を求める方法

  1. 各点の近傍点を求める。
  2. 近傍点群の3次元座標に対して主成分分析を行う。
  3. 最小固有値の固有ベクトル（近傍点群の分散が最も小さい軸）が法線ベクトルとなる

メッシュデータからの法線推定

面の情報を持つメッシュデータの場合、法線推定は点群の場合よりも簡単になり、面（多くの場合、三角メッシュ）を構成する辺のうち2本の外積を求めれば、それが面の法線ベクトルとなる。そして、点の法線ベクトルは、その点が含まれるすべての面の法線ベクトルの平均値として求められる。

特徴点（キーポイント）抽出

特徴点とは点群の中でも特徴的なパターンを持ち、他の点との区別がつきやすいランドマークになりうる点のこと。点群位置合わせなどで対応点を探す際に重要になる。

Harris3D

2次元画像処理のHarrisコーナー検出の拡張版。窓関数と画素値を使って、その点から全方向に対する画素値の変化が大きい場所（コーナーとなる点）を探す。しきい値を超える点がコーナー点となるが似たような場所で複数の点が抽出されるため、ある範囲の近傍点の中で局所最大となる点を抽出する処理（NMS）を行う。

Intrinsic Shape Signature(ISS)

近傍点集合から共分散行列を計算し、固有値の比を使って点を評価すし、点群の分布に偏りがある点を探す。Harris3Dと同様にある範囲の近傍点の中で局所最大となる点を抽出する処理（NMS）を行う。

大域特徴量

入力データの全体を表す数値列。古典的な物体認識アプローチではこの大域特徴量を機械学習アルゴリズムに入力する。

3D Shape Histgram

3次元データの中心を原点として、物体表面上の点を球上等間隔にサンプリングする。3通りの方法（半径、角度、2つの組み合わせ）で空間を分割して、各領域に含まれる点数のヒストグラムを計算する。

Spherical Harmonics Representation

物体の3次元形状を球面上のある関数と見なし、これを有限個の基底ベクトルの線形結合で近似する。イメージとしては3次元形状のフーリエ変換。回転不変な特徴量が得られる。

LightField Descriptor

物体を（仮想的に配置したカメラにより）多方向から見た2次元画像の集まり（多視点画像）として表現する。仮想カメラは正十二面体の20個の頂点に配置する（最も頂点数の多い正多面体）。仮想的にカメラを動かして、複数の角度から撮影し、シルエットの輪郭を表現する記述子を計算する。2つの物体を比較する際には記述子の類似度を計算する。

局所特徴量

入力データの局所領域を表す数値列。あるデータと別のデータの特徴点の対応付けを行う際に特徴点の周辺領域を記述する際に使われる。

Spin Image

各特徴点の近傍点群で法線ベクトルを求める（基準軸）。特徴点の接平面に対してある近傍点を射影し、αとβの2つの距離を求める。これをすべての近傍点で行い、2次元のヒストグラムを得る。物理空間だけでなく、色空間も分割して色の違いを区別するColor Spin Imageという手法もある。

SHOT

Spin Imageと異なり、基準軸が3軸（半径、方位角、高度）になっている。特徴点の近傍点群の共分散行列を固有値分解する。そのまま固有値分解するとノイズが含まれることが指摘されているため、特徴点と距離が近い点の影響をより強く受けるように改良している。空間を3軸で分割して、各領域の法線ベクトルとその領域内の点の法線ベクトルの内積に関するヒストグラムを計算する。

色付き点群に対応したColor SHOTという手法もある。

Fast Point Feature Histgram(FPFH)

Point Feature Histgramは特徴点を中心とした小球領域に含まれるk個の近傍点からすべての組み合わせの2点間でパラメータ計算されたヒストグラムでこれを高速化したもの。

Open3DにはFPFHのみ実装されている。

点群レジストレーション（位置合わせ）

別々の視点から撮影された2つの点群データの位置合わせには、点群間の距離を測る処理と点群の位置姿勢を変更するための剛体変換の推定で構成される。

近傍探索

点群処理である点に対する（何かしらの距離に基づいた）近傍探索は頻繁に利用される処理のため、毎回すべての点との距離を計算すると効率が悪い。効率の良い近傍点探索手法としてkd-treeがある。

kd-treeはk次元のデータを整理して保存するためのデータ構造。点群の場合は3次元となる。Open3Dのkd-treeには3つの探索基準が用意されている。

  • クエリのk近傍点抽出
  • 指定した半径の値以内の点を抽出
  • 上記2つの基準を満たす点を抽出

ICPアルゴリズム

点群同士の位置合わせ処理に広く用いられるアルゴリズム。ソース点群（位置合わせ元）とターゲット点群（位置合わせ先）を位置合わせするために必要な剛性変換（回転と並進）を推定する。初期値依存のあるアルゴリズムでソースとターゲットが近い位置にないとよい解を得られない。その場合は特徴点マッチングによる位置合わせなどで荒い位置合わせを行った後に実行する。

おおまかな手順は

  1. ソース点群とターゲット点群の対応付け
  2. 剛体変換の推定
  3. 物体の姿勢のアップデート
  4. 収束判定（収束条件を満たさない場合は1. へ）

ICPアルゴリズムの目的関数にはソースとターゲットの点間の距離を評価するPoint-to-Pointとソースの点とターゲットの面の距離を評価するPoint-to-Planeがある。

点群からの物体認識

狭義の物体認識はカテゴリレベルの認識タスクである一般物体認識とデータベースなどから一致するIDを出力するようなインスタンスレベルの認識タスクである特定物体認識とに分けられる。

物体認識のおおまかな手順は

  1. ラベルの付与された3次元データを用意する。
  2. 3次元データから特徴量を抽出する。
  3. 特徴量からラベルを推定する識別器を学習する。
  4. 認識対象物体の3次元データから特徴量を抽出する。
  5. 識別器を使ってラベルを推定する。

同一の物体を計測したデータでも以下に挙げられるような環境や状況に変化が生じるとデータの数値は同じにならない。

  • 照明環境の違いによる色の変化
  • センサから物体までの距離の違いによる解像度の変化
  • センサのノイズ
  • 前傾に存在する障害物による隠れ（オクルージョン）
  • 物体の姿勢変化

一般物体認識ではラベル（カテゴリ）と物体（データ）が一対多の関係になるためカテゴリ内で共通する抽象的な特徴を捉えることが重要になる。

特徴点マッチングによる姿勢推定

目的は入力された2つの点群を貼り合わせる変換行列を求めること。ICPアルゴリズムと目的は一緒だがこちらは2つの点群の初期位置が近いことを仮定しない。

物体の位置姿勢は6自由度（3次元の並進と回転）であるため、探索空間が膨大なため、ソースとターゲットのよく似た部分を見つけて、その情報を基に姿勢を計算する。

手順

  1. 特徴点検出
  2. 特徴量記述
  3. 対応点探索
  4. 姿勢計算

対応点探索には誤りが含まれることがあるので、姿勢計算にはRANSACを使用するなど頑健な推定方法をとる。

一般物体の姿勢推定

特徴点マッチングによる姿勢推定は対象物を別視点から撮影した場合や認識対象物の3次元形状モデルが利用できる場合は使い勝手が良いが利用できない場面も少なくない（3次元形状モデルが公開されていない、使われないで設計されるケースなど）。カテゴリ名が既知で画像中の対象カテゴリの物体の位置姿勢を算出する問題はカテゴリレベル姿勢推定と呼ばれ、2019年頃から研究が活発になっている。

主な研究事例

  • Normalized Object Coordinate Space(NOCS)
  • Active Shape Models(ASM)

プリミティブ検出

平面や球などの単純な図形を検出する処理をプリミティブ検出と呼ぶ。机の上に並べた対象物を検出したい場合、事前に平面を検出して、その部分の点群を削除すれば個々の物体を簡単に検出できるため、シーン理解の強力な前処理として使える。

セグメンテーション

物体を認識するためには認識対象物体の範囲を知る必要があるが多くの場合は取得データの中に複数の物体が写り込んでいる。物体を認識するためにはなんらかのまとまりを持った領域に分割するセグメンテーション処理が必要になる。

物体認識の前にセグメンテーションを行う場合は、認識対象よりも細かいパーツ単位でセグメンテーションを行うオーバーセグメンテーションが有効であることが知られている。オーバーセグメンテーションを行う最も基礎的な手法はDBSCANである（その他の手法はPCLのドキュメントを参照すると良い）。

深層学習による3次元点群処理

3次元点群には1つ1つのデータ要素に順序やグリッド構造がない（任意の2点を入れ替えても形状は変わらない、順不同データとも呼ばれる）。このようなデータを扱う手法としてPointNetとDeepSetがほぼ同時期に提案されている。

PointNet

PointNetでは入力データの順序が変わっても出力が変わらないような関数（Symmetric Function）を導入することで順不同データに対応している。このような関数として、PointNetではチャンネル方向に同一のMLP（Shared MLP）を適用し、(Max-)Poolingで集約することで順序によらない出力を実現している。

そのほかにPointNetではSpatial Transformer Networkのアイデアを基にしたT-Netモジュール（点群の回転を自動的に正規化するモジュール、入力点群に対応する回転行列を計算する）を適用することで、入力点群や特徴量空間から抽出した情報を再度、点群全体や特徴量空間に作用させる設計になっている。

点群の畳み込み

PointNetでは点群全体の特徴を1つのベクトルで構成となっている。3次元点群から局所特徴量を抽出するモチベーションから点群に対する畳み込み手法の提案がされている。

Edge Conv

点群では画像のようなグリッド構造がないため、そのまま畳み込みを適用できない。よって、kNNやredius Neighborによって近傍を設定することが多い。

Edge Convではある点（着目点）の特徴量そのものと着目点の特徴量とその（各）近傍点の特徴量の差分を結合して、Shared MLPで変換し、着目点と各近傍点の点ペアに関する特徴量とする。この特徴量をMax-Poolingすることで着目点の出力特徴量を得る。
そのほかに相対座標からカーネルを計算し、畳み込みは局所点群に関する重み付き和で行う手法（SpiderCNN, FlexConv）などもある。

近年の研究動向

  • 点群畳み込み
    • PointNet++, SpiderCNNは畳み込みの仕組みが簡単で扱いやすい実装も公開されている。
    • 深度センサや車載LiDARなどで取得された点群で地面の方向が既知の場合など、2次元に投影することが自然な点群データの場合、深度画像として処理したり、Bird’s Eye View（BEV）として投影して処理する例もある。この場合は2次元のCNNを利用した特徴抽出ができる。
  • PointNet構造の高速化
    • 高速な推論を実現するためにPointNetの基本構造であるShared MLPをLook Up Tableに置き換えるJustlookupが提案されている。
  • 3次元点群の出力
    • ニューラルネットワークの出力（Auto EncoderやGANなどに使う）として3次元点群を扱う手法も提案されている。
      • Data Driven Upsampling
      • FoldingNet
  • 物体検出
    • 3次元点群中から物体を検出して、場合によってはその姿勢を推定するタスク。
      • VoteNet
      • PointPillars
  • 局所特徴量計算
    • 深層学習を使った3次元点群のレジストレーション用の局所特徴量。
      • PPFNet
      • 3DSmoothNet
  • 点群レジストレーション
    • 深層学習を使った3次元点群のレジストレーション
      • IT-Net
      • PointNetLK
      • DenceFusion

点群以外の3次元データ処理

RGBD画像

RGBに加え、視点から物体表面までの深度の値が入ったデータ。一般に同じセンサを用いる場合、点群データよりも省メモリで高速に処理できるため、ロボットなどのオンライン処理に向いている。

RGBと距離画像を分けてそれぞれのニューラルネットワークへ入力する方法が主流。距離画像はHHA（水平線上の距離、地面からの高さ、重力方向と法線ベクトルのなす角）の3チャンネルにエンコードすることが多い。

ボクセルデータ処理

3次元空間を等間隔のグリッドに分割し、各グリッドが値を持つデータ形式。動画像ファイルのような時系列データやCTスキャンなどによって得られる医用画像などのデータ表現（2次元を3次元へ拡張）に適しているが、3次元センサでとられたデータにも適用できる。

ボクセルデータを入力とした物体認識の研究として以下が挙げられる。

  • 3D ShapeNets
  • VoxNet

メッシュデータ処理

3次元形状を表現する上で非常にコンパクトで可視化に適したデータ形式（CADモデルなどに使われる）。物体認識などの処理を行う上で他の3次元データ形式に比べて使用される機会は多くない。

多視点画像処理

複数視点から3次元物体を撮影して得られる2次元画像群。

多視点画像を入力とした物体認識の研究として以下が挙げられる。

  • Multi-view CNN(MVCNN)
  • RotationNet

Inmlicit Functionを用いた3次元形状表現

関数の等高線によって陰的（メッシュのような直接的な記述ではなく）に表面を表す。滑らかで整合性の取れた3次元形状を表現できる（他の表現は量子化、離散化される）。近年はこの関数をニューラルネットワークで表現する方法が注目されている。学習が難しいというデメリットがあるが今後、一般的な3次元表現形式になることも期待されている。

最後に

点群の入門としてとても素晴らしい一冊でした。紹介されている論文も現在にも影響を与えているものが多いため、少しずつ読み進めていきたい。

Discussion