Clustering
檢測點雲數據中的圓形圖案
對於我正在研究的一些體積重建算法，我需要在 3d 點數據（來自激光雷達設備）中檢測任意數量的圓形圖案。圖案可以在空間中任意定向，並假設位於（雖然不完美）薄二維平面中。這是一個在同一平面上有兩個圓圈的示例（儘管請記住這是一個 3d 空間）：
我嘗試了很多方法.. 最簡單的（但迄今為止效果最好的一種）是基於最近鄰圖的不相交集的聚類。當圖案相距很遠時，這工作得相當好，但對於像示例中的圓圈這樣的圓圈來說，這樣的圓圈非常接近。
我嘗試了 K-means，但效果不佳：我懷疑圓形點排列可能不太適合它。另外，我還有一個額外的問題是事先不知道 K 的值。
我嘗試了更複雜的方法，基於最近鄰圖中的循環檢測，但我得到的要么太脆弱，要么計算成本高。
我還閱讀了很多相關主題（霍夫變換等），但似乎沒有什麼能完美適用於這個特定的上下文。任何想法或靈感將不勝感激。
廣義霍夫變換正是您想要的。困難在於有效地做到這一點，因為 3D 中的圓空間有六個維度（三個用於中心，兩個用於定向平面，一個用於半徑）。這似乎排除了直接計算。
一種可能性是通過一系列更簡單的霍夫變換來偷偷摸摸得到結果。例如，您可以從（通常的）霍夫變換開始檢測平面子集：這些只需要 3D 網格進行計算。對於檢測到的每個平面子集，沿該平面對原始點進行切片並執行廣義霍夫變換以進行圓檢測。如果原始圖像沒有很多共麵點（圓圈形成的點除外）可能會淹沒圓圈產生的信號，這應該可以很好地工作。
如果圓的大小有一個預定的上限，您可能會節省大量計算：您可以專注於每個點的有界鄰域內的點對或三元組，而不是查看原始圖像中的所有點對或三元組。