見出し画像

【機械学習（11/10更新）】３次元点群処理について（クオータニオン、ボクセル化、局所特徴量の抽出など）（随時更新）

Yusuke

最近、点群処理を業務で行うことが多くなったので「詳解　3次元点群処理」を読んで点群の扱い方を勉強している。

非常に良書だが、難しい内容が多く、すべて理解してnoteにまとめるとかなりの時間がかかると思うので、特に業務に直結する「クオータニオン」や「ボクセル化」について、（ChatGPTとのやり取りを）自分の備忘として記述した。
この本のこと以外にも、自身で気づいた点群の処理方法についてなども記述していこうと思う。


そもそも点群とは

そもそも点群とは何なのか。点群とは、x,y,zの3次元で表される点の集まりのこと。点一つ一つがそれぞれx,y,z座標を持っており、それらをまとめることで、一つの大きなものを表示することが可能になる。

参考として、静岡県が出しているグラウンドデータを使おうと思う。

そのほかにも、能登半島の地震が発災する前の点群データをG空間情報センターというところが無料で提供してたり、長崎県が「オープンナガサキ」と称して点群データを提供していたり、様々な地理情報が、点群データをとして存在している。

静岡県のデータをダウンロードしてみた。

静岡県のデータ取得画面

Cloud Compareというオープンソースソフトウェアを使って静岡県のグラウンドデータや能登東部の点群データを移すとこのようになる。


静岡の点群データ
能登半島の点群データ

点群で地形の情報をビジュアライズできるので、土地の管理業務などに非常に有益なデータである一方、その使い方についてはまだまだ開発途上なところが現状である。

最近は、オープンソースとして無料でダウンロードできる点群データも増えてきている。下記に例として複数リンクを添付したので、もし気になる人は要チェックです。

1-1．点群の回転・スケール変換

まず、２次元の回転を極座標表示（直交座標と異なり、点の位置を角度と距離で表す表示方法）を使って考えることから始める。（下記リンクを参考にしました）

noteでの数式の上手な書き方分からず、自分が覚えなおすために書いているので、綺麗なものを見たい方は是非本書を！（すいません）

(x1, y1) = (r cos α, r sin α)
とすると
(x2, y2) = (r cos (α + θ), r sin(α + θ))
となる。

加法定理より次式が成り立つ。

これらの式を行列で表すと、

となる。

この

を回転行列という。

さらに、並進という、点群の平行移動を考える。

点（x1, y1）を角度θで回転させた後、x軸方向にtx、y軸方向にtyの平行移動を加えた場合、次式で表せる。

式１

を並進ベクトルという。
式１を行列を用いて表すと、

X2 = RX1 + t が成立する。

これは、次式の通り、掛け算のみの形で書くことができる。

実際に行列を計算してみると合っていることがわかる。


1-2．オイラー角

下記リンクを参考にしました。中学生が書いた記事とのこと。すごいなと思います。（ちょっとPCで数式を書くのが面倒なので、いつかお金がたまって新しいノートPCが買えたら（来年４月ごろ予定）、記述したものを載せようと思います。。）

1-3．クオータニオン

下記リンクを参考にしました。

角度θの２次元回転は複素数を使ってcosθ + i sinθ で表すことができる。（オイラーの公式）

３次元の回転は、四元数qは３つの虚数単位i, j, kを用いて次式のようにあらわす。

本書では数式で解説されているのだが、要約するとこうだ

四次元数で回転を定義すると、自由度の関係からオイラー角よりも簡潔にきれいに回転を表すことができる

その利用しやすさから、3Dコンピューターグラフィックスやゲーム開発など様々なところで使用されている。

2-1．サンプリング（ボクセル化、PDSについて）

３次元データのサンプリングは、２次元データとは大きく異なるが、考え方はその延長線上にある。

ボクセル化

最もよく使われるサンプリング方法として「ボクセル」が挙げられる。これは「ボックス」と「ピクセル」が混ざった造語で、３次元点群データをx,y,z座標に任意の大きさのボックスを並べる。そして、ボックス内に点がない場合を0とし、ある場合を１とすることで点群をピクセル化するのである。


ボクセル化イメージ図

pythonではOpen3Dにあるpcd.voxel_down_sample関数を使うことで容易にボクセル化することが可能である。

Poisson Disk Sampling（PDS）

点群処理におけるPoisson Disk Samplingは、3D点群データからサンプル点を均等に間隔をあけて抽出する方法です。主に、点群データのダウンサンプリングやリサンプリングのために使用され、密集度が高い箇所から不要な点を減らし、全体のデータ量を軽減しつつ情報を損なわないようにします。

特徴と利点

  1. 均等な間隔のサンプリング：
    Poisson Disk Samplingは、指定した最小距離を確保しながら点を選択するため、密度に偏りが少なく、均等な分布でサンプリング点が抽出されます。これは、例えばランダムサンプリングと異なり、点が密集しすぎたり、逆にスカスカになる箇所が生じにくいというメリットがあります。

  2. データの圧縮と計算コストの削減：
    点群データのデータ量を削減することで、データを扱う際の計算コストやメモリ使用量を抑えます。これにより、3Dモデルのレンダリングや機械学習、物体検出などの処理が効率化されます。

点群処理での用途例

  • 3Dスキャンデータの軽量化：高密度のスキャンデータからPoisson Disk Samplingを用いて重要な点のみを残し、データサイズを軽量化。

  • 点群データのノイズ除去：ノイズの多いデータからノイズ成分を抑え、信頼性のあるサンプル点だけを保持。

  • リサンプリング：データを均等に分布させることで、3Dモデルの解析やシミュレーションの精度向上。

アルゴリズム概要

Poisson Disk Samplingの基本アルゴリズムは、次のような手順で進められます：

  1. 初期点の配置：最初に空間内にランダムな点を配置します。

  2. 近傍探索と新規点の追加：各点の周囲に最小距離を保ちながら、新しい点を追加します。

  3. 条件を満たさない点の排除：サンプル点が既存の点から指定の最小距離を超えていない場合は、その点を排除します。

  4. 全点の配置完了：最小距離条件を満たしつつ、全サンプル点が配置されるまで繰り返します。

このようにして、3D空間上で効率的かつ均等な分布を持つ点群を抽出できるため、Poisson Disk Samplingは点群データ処理において非常に有効なサンプリング手法とされています。

2-2．法線推定

点群の法線ベクトルとは、平面や曲面の点に対して垂直なベクトルのことである。
各点の局所的な面の向きがわかるため、とても重要な特徴量である。

算出方法

  • 最近傍点の使用： 各点の近傍にある点の集合（k近傍や半径内の点など）を用いて、局所的な面を推定します。

  • 主成分分析（PCA）： 近傍点群を使って主成分分析を行い、局所的な面に対する法線ベクトルを推定します。

    • 最近傍点集合の分布の中で、最小の分散を持つ方向が法線方向として推定されます。

    • 計算手順：

      1. 点 ppp に対して、近傍の点を収集します。

      2. 収集した点の共分散行列を計算します。

      3. 共分散行列の固有ベクトルと固有値を求め、最小の固有値に対応する固有ベクトルを法線ベクトルとします。

  • 方向の一貫性の確認： 点群全体で法線ベクトルの向きを統一するために、各点の法線ベクトルが隣接する点群と同じ方向を向くように調整する必要があります。これには、反転したベクトルを検出し、一貫した向きに揃えるアルゴリズムが用いられます（例: MSTに基づいた手法）。

PythonのOpen３Dライブラリを用いると簡単に推定ができる

import open3d as o3d

# 点群データを読み込む
point_cloud = o3d.io.read_point_cloud("point_cloud_data.ply")

# 法線ベクトルの推定
point_cloud.estimate_normals(
    search_param=o3d.geometry.KDTreeSearchParamHybrid(radius=0.1, max_nn=30)
)

# 法線ベクトルの方向を調整（隣接点と一致するように）
point_cloud.orient_normals_consistent_tangent_plane(k=10)

# 法線ベクトルを可視化
o3d.visualization.draw_geometries([point_cloud], point_show_normal=True)

2-3．局所特徴量

本書では点群の局所特徴量としてよく使用されるSpin Imageが紹介されている。

特徴量とは、ある特徴点ｐ（∈R^3）まわりの点を表す特徴量である。


3-1．位置合わせ（kd-tree）

# x,y座標の点の近傍点を求めるプログラムの例
points_nb = []

coords = df_nearby[['x', 'y']].values
kdtree = KDTree(coords)

for _, row in df_nearby.iterrows():
    if row['index'] > 0:
        rowid = row['index']
        center_x = row['x']
        center_y = row['y']
        radius = row['Re']        
        indices_within_radius = kdtree.query_ball_point([center_x, center_y], radius)        
        points_within_circle = df_nearby.iloc[indices_within_radius].copy()        
        points_within_circle['id'] = rowid
        points_nb.append(points_within_circle)

いいなと思ったら応援しよう！