HDBSCAN + kNN による MVS 点群の階層的なフィルタリング

Researcher の尾川です。今回は MVS の後処理の高速化についてご紹介します。

背景

MVS によって得られた生の 3D 点群には一定のノイズが含まれます。当社の主なターゲットであるドローン測量分野では、撮影中に動くもののほか、撮影位置に依存して被写体の光の強さが変わるもの（水面を含む光沢面）や、実質的に無限遠にあるもの（空など）が入力画像に内在するノイズの原因として挙げられます。さらにその後の処理において、誤検出に由来するノイズなどが追加される場合があります。

たとえば、このようなノイズが最終的な高さデータ (DSM) まで残ってしまうとそのノイズ点の高さが地形表面の高さとして表現されてしまったり、メッシュの頂点になってしまうとテクスチャメッシュとして不適切なものが生成されてしまったりします。したがって、MVS の実行直後にこのようなノイズをできる限り除去することが重要です。

問題の整理と提案手法

このノイズを除去するフィルタリングは、問題として次のように整理できます。これらを考慮するとクラスタリングが基本的な戦略であり、入力点の大半を含むクラスター（通常1個）に含まれる点が結果として得られる点です。

• 対象の点数：数百万から数億（3次元）
• 点の分布に関する先験情報：基本的には被写体の表面に集中している、誤検出であってもその表面に集中している、光沢面や空などはランダムノイズになりやすい

しかし、3D 点群に対して直接クラスタリングを実行すると規模の観点から品質と処理時間（並列処理の可否を含む）の両立が難しいことが課題となっていました。従来の実装では品質面の限界も感じていたため、次のような手順を検討し、改善を試みることにしました。

1. ボクセルダウンサンプリングにより、空間内の点を約10万点にサンプリングする。
2. 手順1の点に対して HDBSCAN を適用し、サンプリング点に対するクラスタリング結果を得る。
3. 手順1の点と手順2の結果を使って kNN モデルを学習する。
4. もとの点群に対して手順3の kNN モデルで推定し、もとの点群に対するクラスタリング結果を得る。

サンプリング

点は偏在しているため、points[::1000] のような単純なサンプリングでは空間を正しく代表できません。一方で遍在している状況も考えづらいため、ボクセルダウンサンプリングを採用することにしました。

ボクセルダウンサンプリングではあらかじめボクセルサイズを設定する必要がありますが、分布の偏在により、その値における結果点数は予測できません。この小さな課題については、制御理論のような考え方でボクセルサイズを調整しながら反復処理することで対応しました。端的に言えば、ボクセルサイズを1/2にしたとき、サンプリング点数はもとの8倍以下であり、この倍率はサイズの縮小とともに小さくなる性質を利用しています。

HDBSCAN

手法そのものについては以前の記事をご覧ください。 サンプリングの目標点数としている10万点は公式にすぐ処理できると案内されている規模で、実際、すぐ終わりました。いくつか調整できるパラメータがありますが、点群の特性やサンプリングの適切性が前述の想定と一致している限りはあまり変える必要はないのかなと考えています。

kNN

並列に高速に分類したいので kNN を選択しました。

推定手法の評価

開発環境のマシンでは100万点あたり1秒が相場で、従来手法の約10倍でした。 図に示すデータセット（約420万点）では、主に水面に由来する点を適切に除去できていることを確認できます。

フルカラーがフィルタリング結果（出力）、黄枠の青い点がノイズのクラスター、赤い点がノイズ

この図に対応するクラスターごとの概要は次のとおりです。density = (kNN points) / (HDBSCAN points)

Cluster 0: 127 points in HDBSCAN, 246 points in kNN, density 1.9, 0.01%
Cluster 1: 310 points in HDBSCAN, 584 points in kNN, density 1.9, 0.01%
Cluster 2: 118 points in HDBSCAN, 351 points in kNN, density 3.0, 0.01%
Cluster 3: 198 points in HDBSCAN, 1166 points in kNN, density 5.9, 0.03%
Cluster 4: 180 points in HDBSCAN, 554 points in kNN, density 3.1, 0.01%
Cluster 5: 228 points in HDBSCAN, 668 points in kNN, density 2.9, 0.02%
Cluster 6: 288 points in HDBSCAN, 1926 points in kNN, density 6.7, 0.05%
Cluster 7: 117 points in HDBSCAN, 2526 points in kNN, density 21.6, 0.06%
Cluster 8: 106 points in HDBSCAN, 341 points in kNN, density 3.2, 0.01%
Cluster 9: 92369 points in HDBSCAN, 4166609 points in kNN, density 45.1, 99.40%
Noise: 6469 points in HDBSCAN, 16591 points in kNN

まとめ

適切なサンプリングに基づいて機械学習の手法を組み合わせることで、品質と速度を両立できる可能性について紹介しました。なお、このアルゴリズムは6/5以降の「くみき」等において実際に適用されています。

動くものや物体の境界に由来するノイズはクラスタリング手法に基づく除去は難しいため、MVS の深度推定結果から妥当性を評価するようなフィルタリングも行っています。これについてはまた機会があればご紹介します。

202304_skymatix_engineer from skymatixHR

www.slideshare.net