Farthest Point Sampling

又稱: FPS, furthest point sampling
類別: Sensing › Perception outputs
標籤: point-cloud, sampling, 3d-perception, preprocessing, deep-learning

一種從點雲中挑選固定數量的點、讓它們均勻分布在形狀上的貪婪方法，做法是反覆選擇離已選點最遠的點。

定義

最遠點取樣（Farthest point sampling，FPS）從 N 個點的集合中選出 M 個點組成的子集。它從一個點開始（隨機選取或固定），每一步加入一個點，這個點到離它最近的已選點的距離為最大。實作時，會為每個輸入點記錄它到最近已選點的距離，並在每次加入新點後更新這個值，因此運算量隨 N 乘以 M 成長。不論原始取樣的密度如何，結果都能均勻涵蓋整個形狀。同樣的貪婪規則，也是 Gonzalez 於 1985 年提出、k 中心分群問題的經典 2 倍近似演算法。

在點雲深度學習中，FPS 因 PointNet++ 而廣為人知：PointNet++ 在每一層用它選擇局部鄰域的中心，後來許多網路也在推論前用它把輸入點雲降取樣到固定大小。隨機取樣會跟著輸入的密度走，可能漏掉細薄或觀測稀疏的部分；相較之下，FPS 能維持對整個物體的涵蓋。與體素網格降取樣相比，它回傳的點數是精確的，這正是輸入大小固定的網路所需要的。

FPS 有它的取捨。它會刻意偏好離群點：孤立的雜訊點離其他所有點都很遠，會很早就被選中，因此點雲通常要先經過濾波。這個程序是循序執行的，在非常大的點雲上會很慢；GPU 實作會在每一步之內平行化距離更新，近似變體則在空間分割上運作。輸出取決於起始點；在網格上，測地線變體沿著表面、而非沿直線量測距離。

為何重要

點雲網路需要固定大小的輸入，而深度感測器產生的點遠多於網路能處理的數量。均勻的涵蓋代表把手、邊緣與壺嘴這些雖小但重要的部分能在降取樣後保留下來，這對抓取與可供性預測很重要。

主要應用

為神經網路把點雲前處理成固定大小
在階層式點網路中選擇鄰域中心
在計算 Chamfer 距離或推土機距離（Earth mover's distance）之前將點雲降取樣
選出分散的候選抓取點或接觸點
為涵蓋挑選多樣的關鍵點或樣本

實際應用

工作台上方的一台深度攝影機，每個影格產生數十萬個點。處理流程先裁切出工作範圍，去除統計離群點，以體素降取樣減少工作量，再執行 FPS，取得與網路訓練時完全相同數量的點，例如 2048 個。團隊在訓練時與機器人上使用相同的取樣程序，因為以 FPS 取樣點雲訓練的網路，與以隨機樣本訓練的網路，看到的點分布並不相同。

常見誤解

FPS 產生的是均勻隨機樣本 — 起始點一旦固定，它就是確定性的，而且是在空間中均勻分散點，而不是隨機取樣
FPS 對雜訊很穩健 — 離群點離其他所有點都很遠，會很早被選中，因此點雲通常要先經過濾波
FPS 保留了掃描的密度資訊 — 它刻意把密度拉平，這有助於涵蓋，卻也去除了感測器在哪裡看到較多點的線索

誰需要了解

3D 感知工程師
研究點雲網路的機器學習研究人員
使用點雲策略的操作工程師

維基百科

最远优先遍历

Open Source Robotics