はじめに

動作環境
Ubuntu 22.04
ROS2 humble

SLAMTEC RPLiDAR A1 M8

方法：DBSCANによるクラスタリング

DBSCANは密度ベースのクラスタリングアルゴリズムであり、以下の手順でLiDARから取得した点群をグルーピングすることができる⁽¹⁾ 。

1.　データ点pの近傍を調べる

ある点pから半径ε以内にあるデータ点を「ε-近傍点」とする。
$$
N_{\epsilon}(p) = \{ q \mid q \in P, d_{p,q} \leq \epsilon \}
$$

2.　コア点の判定

ε-近傍点の数がMinPts以上であれば、点pを「コア点（クラスタの中心となる点」とする。
$$
|N_{\epsilon}(p)| \geq MinPts
$$

3.　クラスタの拡張

コア点同士が互いのε-近傍点に含まれる場合それらは同じクラスタに属する。つまり、あるコア点のε-近傍点に別のコア点が含まれていればそれらは同じクラスタとしてグループ化される。コア点ではないがコア点のε-近傍にある点（ボーダー点）は、そのコア点の属するクラスタに含める。

4.　外れ値（ノイズ点）の判定

どのクラスタにも属さない点は「ノイズ点」として分類する。

5.　クラスタリングの完了

すべてのデータ点に対して上記の処理を行い、クラスタの構成が決定する。

結果：2D LiDARから得た点群のクラスタリング

先述した手法を利用し、2D LiDARから得た点群をDBSCANによってクラスタリングした。Pythonで実装されていたDBSCANアルゴリズム⁽¹⁾ をC++に書き換えて動作させた。図にクラスタリングの結果を示す（$ε$=0.1, $MinPts$=10とした）。クラスタリング前の点群は壁・ボトル・人間・PC画面の辺であった。それらをクラスタリングし色分けすると壁を緑・ボトルを青・人間を赤に表示されていることがわかる。PC画面の辺は点の数が少なく、ノイズと判定された。

応用：大きさの推定

ここでは、各クラスタの大きさ（広がり具合）を簡易的に推定する方法を提案する。

1.　クラスタの平均座標（重心）求める

クラスタに含まれるすべての点のx座標とy座標の平均を計算することでクラスタの平均座標（重心）を求める。
$$
C_x = \frac{1}{N} \sum_{i=1}^{N} x_i
,　C_y = \frac{1}{N} \sum_{i=1}^{N} y_i
$$

2.　クラスタの外周円を描く

クラスタの平均座標から最も遠い点までの距離rを算出し、（$C_x$, $C_y$）を中心とした半径rの円を描く。
$$
r = \max \left( \sqrt{(x_i - C_x)^2 + (y_i - C_y)^2} \right)
$$

図のように、各クラスタの大まかなスケールを簡易的に推定することが出来た。今回は単に円を描くことで大きさの推定を行ったが、描く図形をクラスタの特徴に合わせて変えることでさらに精度を向上させることが出来る（今後の展望）。

参考文献

[1] Kota_Yukawa（湯川皓太）, ”pythonでDBSCANアルゴリズムを実装”, Qiita, (2021)

ソースコード

今回実装したコードはGitHubにあります（Branch：feature/cluster_size）。LiDARの動作方法は以下の記事を参考にしてください。動作について質問があればいつでもお答えします。

謝辞

この取り組みは株式会社GxP(グロースエクスパートナーズ)様のサポートを受けて実施しています。貴重なアドバイスやロボットに必要な機材の支援をいただきました。心より感謝申し上げます。