1）摘要

????????3D 點云中的實時平面提取對于許多機器人應用至關重要。作者提出了一種新穎的算法，用于在從 Kinect 傳感器等設備獲得的有組織的點云中實時可靠地檢測多個平面。通過在圖像空間中將這樣的點云均勻地劃分為不重疊的點組，我們首先構建了一個圖，其節點和邊分別代表一組點及其鄰域。然后，在此圖上執行凝聚分層聚類，以系統地合并屬于同一平面的節點，直到平面擬合均方誤差超過閾值。最后，使用像素級區域增長來優化提取的平面。實驗表明，所提出的算法可以可靠地以超過 35Hz 的幀速檢測場景中的所有主要平面，對于 640×480 個點云，比最先進的算法要快得多。

2）創新點

①提出了一種基于組織點云的凝聚聚類的高效平面提取算法。

②分析了聚類算法的復雜性，并表明它在初始節點的數量上是對數線性的。

③展示了實時性能，其準確性可與最先進的算法相媲美。

3）算法結構

3.1）快速平面粗提取

????????快速平面提取算法包括三個主要步驟，如上圖所示：該算法首先初始化一個圖形，然后執行 AHC 以提取粗平面，最后進行細化。如果應用程序只需要對平面區域進行粗略分割，例如，檢測點云中的對象，則可以跳過最后的優化步驟，這可能會將 640 × 480 個點的幀速率增加到 50Hz 以上。

????????首先，我們澄清我們的符號。F 表示由 M 行和 N 列組成的有序點云的完整幀。B、C 分別表示粗細分割，即 B/C 的每個元素 Bk/Cl 都是一個段——一組 3D 點 pi，j 。同時 Π、Π0 分別是對應于 B、C 的平面方程組。另請注意，圖 G 的每個節點 v 都是一組 3D 點，每個無向邊 uv 表示圖像空間中線段 u、v 的鄰域。

A 圖初始化

????????我們的算法需要非重疊節點初始化，如算法 2 的第 3 行到第 5 行所示。此步驟在圖像空間中將點云均勻劃分為一組大小為 H × W 的初始節點。這個要求導致我們的算法失去了自動檢測平面邊界的優勢。為了在此限制下使用 AHC 正確分割平面，我們從圖中刪除以下類型的節點和相應的邊緣，如下圖中的示例所示：

????????1）具有高 MSE 的節點：非平面區域會導致高平面擬合 MSE，我們只需將其刪除即可。

????????2）包含缺失數據的節點：由于傳感器的限制，可能無法正確感知場景的某些區域，從而導致數據丟失（例如，百葉窗后面的玻璃窗）。

????????3）包含深度不連續性的節點：這些節點包含兩組點，它們位于兩個表面上，這兩個表面在 3D 中并不接近，但在圖像空間中很接近（通常一個表面部分遮擋了另一個表面，例如，顯示器遮擋了后面的墻壁）。如果在屬于該節點的點上執行主成分分析 （PCA） 以進行平面擬合，則擬合平面將幾乎平行于視線方向，因此仍然具有較小的 MSE。將此“異常值”節點與其相鄰節點合并將對平面擬合結果產生不良影響，因為在最小二乘法中存在眾所周知的過度加權異常值的問題。

????????4）兩個平面之間邊界處的節點：這些節點包含兩組在 3D 中彼此靠近但位于兩個不同平面上的點（例如，房間的角落），如果它們合并到其中一個平面，將降低平面擬合精度。

算法 2 中的函數 REJECTNODE 和 REJECTEDGE 旨在減少這四種不良初始節點的影響。REJECTNODE 函數從圖形中刪除前三種類型的壞節點（以及其中的點），而 REJECTEDGE 函數用于減輕第四種壞節點的影響。有趣的是，這種不重疊的 “劣勢 ”的好處是避免了每點的正常估計。我們的初始化步驟可以看作是將節點內的所有點視為具有公共平面法線。與其他最先進的方法相比，這是我們速度提高的一個重要原因，這些方法通常花費大量時間對每個點進行正常估計。

B Agglomerative Hierarchical Clustering

????????如算法 3 所示，我們算法中的 AHC 與線回歸中的 AHC 幾乎相同，只是它是在圖而不是雙鏈表上做的。我們首先構建一個最小堆數據結構，以有效地找到具有最小平面擬合 MSE 的節點。然后，我們重復查找一個節點 v，該節點當前在圖中的所有節點中具有最小平面擬合 MSE，并將其與它的一個相鄰節點 u_best 合并，從而產生最小合并 MSE（回想一下，圖中的每個節點都是一組點;因此合并的 MSE 是兩組 umerge 的并集的平面擬合 MSE）。如果此最小合并 MSE 超過某個預定義的閾值 TMSE（不一定是固定參數），則找到一個平面段 v 并從圖中提取;否則，合并后的節點 umerge 將通過 v 和 ubest 之間的邊收縮添加回圖中。

3.2）平面分割結果細化

????????對于許多應用程序，在上一節中獲得的粗平面分割可能還不夠，特別是如果應用程序使用平面的邊界或需要更高精度的估計平面方程。因此，我們對粗略分割 B 執行細化。

????????粗略分割中預計會出現三種類型的偽影，如上圖所示：

????????? 鋸齒波：通常位于兩個連接平面之間的邊界處。

????????? 未使用的數據點：通常位于遮擋或缺失數據節點的邊界處。

????????? Over-Segmentation：通常在兩個對象的遮擋邊界之間

????????鋸齒偽影會導致估計中包含少量異常值，而未使用的數據點和過度分段會導致使用的異常值較少。所有偽影都會產生不準確的平面邊界，并略微降低估計平面方程的精度。

????????我們對它們的解決方案在算法 4 中進行了描述。由于鋸齒偽影幾乎總是在 B 的邊界區域觀察到，因此每個段邊界區域的侵蝕可以有效地消除它們（第 5 行至第 13 行）。然后，從所有新的邊界點開始像素級區域增長，將所有未使用的數據點分配給之前提取的最近平面（第 14 行到第 27 行）。在區域增長期間，將為每個段 Bk 發現 4 個連接的鄰域，從而形成一個新的圖形 G0 。最后，在這個非常小的圖形（通常少于 30 個節點）上再次應用 AHC 可以修復過度分割偽影（第 28 行）。

4）實驗

A 仿真數據

????????在模擬深度圖上測試了算法的魯棒性，該深度圖具有 20 個不同級別的均勻分布噪聲，幅度為 E = 10l、l = 0、. . . 、20（噪聲單位：mm;真實深度范圍為 1396mm 至 3704mm）。將噪聲添加到深度圖后，我們將其轉換為有組織的點云并輸入到我們的算法中 （W = H = 20，TMSE = 502 ）。如下圖所示，我們的算法可以可靠地檢測 l = 0， . . . ， 14 的所有 4 個平面，并在此之后開始過度分割。然而，即使 E = 200 毫米，我們的算法也能夠檢測到場景中的主要平面。

B Kinect采集的實際數據

????????為了測量算法的處理速度，在室內場景中收集了 2102 幀 640 × 480 像素的真實 Kinect 數據，部分如上圖所示。然后使用 12 種不同的初始節點大小（TNUM = 800，α = 0.02，e= 8mm，TANG 從 z = 500mm 的 15? 線性增加到 z = 4000mm 的 90?）。如下圖所示，初始節點大小為 10 × 10，即使經過細化，我們的算法平均只需 27.3 ± 6.9 毫秒即可處理一幀 640×480 像素的 Kinect 數據，實現了超過 35Hz 的幀速率。據我們所知，這比其他最先進的算法要快得多。

C 分割數據集

????????使用 SegComp 數據集評估了算法的準確性。對平面場景的 ABW （W = H = 4，TMSE = 1，TANG = 60? ，TNUM = 160， α = 0.1） 和感知器 （W = H = 8，TMSE = 2.1，TANG = 45? ，TNUM = 240， α = 0.03） 數據集進行了實驗。ABW 和 PERCEPTRON 測試數據集的典型分割結果如上圖所示。使用 SegComp 提供的評估工具的詳細基準測試結果如下表所示。可以看出，該算法在分割精度和平面方向估計方面的性能與最先進的算法相當，特別是考慮到幀速率要高得多。

5）結論

????????作者提出了一種新穎的有序點云快速平面提取算法，在 640 × 480 個點云上實現了超過 35Hz 的幀速率，同時提供了準確的分割。將來，希望將該算法擴展到無組織的點云以及球體和圓柱體等其他基元的快速提取。