障害物のクラスタリングについて

　点群をダウンサンプリングを行った後でも点群の数は多いため，点群のまとまりを一つの障害物として認識して障害物回避を行いたい．

画像処理でのクラスタリング

点群点群画像をOpenCVを使用したラベリングによりクラスタリングを行う場合であれば，全画素を調べて連結した画素をまとまりとして認識できるため，画素数に応じた速度でクラスタリングが可能である．しかし，下図のような点群が位置する場合，左のような場合は連結していない判定で，右のような場合連結している判定となり，最小１ピクセル幅での連結なし，最大√５ピクセル幅での連結ありというように，多少の誤差が生まれてしまう．そのため，障害物間の距離を正確に判断するためには点群の実際のデータからの計算が必要だと考えられる．

Structural Analysis and Shape Descriptors

https://docs.opencv.org/4.2.0/d3/dc0/group__imgproc__shape.html#gaedef8c7340499ca391d459122e51bef5

　全ての点群について正確な計算を行うと時間がかかりすぎてしまうため、回避に重要な範囲を絞り計算を行うべきだろう。そのため、画像による大まかなクラスタリングを行った上でその範囲を探したい．

大まかなクラスタリング

　ここでの大まかなクラスタリングとは，連結している判定がされる最大の距離をロボットの通過可能な幅という大きな幅（ロボットの通過可能な幅の1/√5倍）でピクセルの幅を設定してのクラスタリングである．この方法であれば連結している判定されるのは確実に通過できない点間の距離のときのみである．これより，進行ルートが制限されるため，正確な計算を行う範囲を縮小することが可能だと考えられる．

　また，回避に重要な範囲について，障害物と接触の危険があるロボットの進行方向と目標方向付近だと考えられる．上図での目標方向にある障害物は通行不可能な幅であり，ラベリングによるクラスタリングでは判定できなかったが，目標範囲に絞って点群を利用した計算を行うことで正確な障害物間の距離を計算し，通行可能か判断できるだろう．また，ロボットの進行方向にある障害物は，回避の際に接近する可能性があるため，同じように通行可能かを判定しておく必要があると考えられる．

実装について

　実装について，大まかなクラスタリングの実装については，ピクセルのサイズを決めた後，LiDARの原点を中心にxyz方向にグリッドを配置し，点群の情報を格納，それらのグリッドに対しラベリングのような処理を行うことで大まかなクラスタリングが可能だろう．クラスタリングされた障害物についてはグリッドの座標の重心を求めて記憶しておく．

　次に正確な計算については，重要な範囲に含まれている障害物のグリッド内の点群を使用する．例として上図では目標方向の障害物の赤い枠で表示されているグリッド内の点群を使用する．記憶してある障害物の重心座標から範囲内の障害物の相対的な位置がわかり，それぞれの障害物の重心をつなぐ方向にあるグリッド内の点同士の距離を比較することで正確な障害物の幅が求められるだろう．