論文鏈接：https://www.researchgate.net/profile/Sven-Behnke-2/publication/221104985_Efficient_Multi-resolution_Plane_Segmentation_of_3D_Point_Clouds/links/0912f5012c7339e394000000/Efficient-Multi-resolution-Plane-Segmentation-of-3D-Point-Clouds.pdf

來源：公眾號(hào)「3D視覺工坊」?

摘要

本文提出了一種有效的多分辨率方法將 3D 點(diǎn)云分割成平面組件。為了提高效率，本文從粗到精的 3D 分辨率中迭代處理大點(diǎn)云，在每個(gè)分辨率下，快速提取表面法線來描述表面元素（面元），將無法與來自較粗分辨率的平面關(guān)聯(lián)的面元分組為具有霍夫變換的共面簇。然后提取這些集群上的連接組件，并通過 RANSAC 確定最佳平面擬合。最后，合并平面片段并在最佳分辨率上細(xì)化分割。在實(shí)驗(yàn)中，展示了該方法的效率和質(zhì)量，并將其與其他最先進(jìn)的方法進(jìn)行了比較。

簡介

我們將 Hough 變換與 RANSAC 相結(jié)合以穩(wěn)健地提取來自 3D 點(diǎn)云的平面片段（圖 1）。為了提高效率，我們采用由粗到細(xì)的策略：以多種分辨率提取局部表面法線來描述表面元素（面元）。我們使用八叉樹實(shí)現(xiàn)了一種高效的多分辨率法線方法估計(jì)。在每個(gè)分辨率下，我們確定哪些面元可以用較粗分辨率上擬合的平面來解釋。在剩余的面元上，我們應(yīng)用霍夫變換將場景預(yù)分割為共面面元。為了提高準(zhǔn)確性和魯棒性，我們使用 RANSAC 擬合平面段。在最佳分辨率下，我們合并共面連接的平面段并分配剩余的點(diǎn)。

圖1

1、通過多種分辨率進(jìn)行有效的法線估計(jì)

我們用八叉樹表示點(diǎn)云。八叉樹由分支節(jié)點(diǎn)和葉節(jié)點(diǎn)組成，每個(gè)分支節(jié)點(diǎn)和葉節(jié)點(diǎn)都覆蓋一個(gè) 3D 體積。樹的根跨越感興趣的完整 3D 體積。每個(gè)分支節(jié)點(diǎn)在其中心位置將其體積分成八個(gè)大小相等的立方體（稱為八分圓）。對于它的每個(gè)八分圓，該節(jié)點(diǎn)都包含一個(gè)子節(jié)點(diǎn)，該子節(jié)點(diǎn)本身是一個(gè)分支節(jié)點(diǎn)，或者是樹中的一片葉子。八叉樹可以用于以與樹的不同深度中節(jié)點(diǎn)的體積大小相對應(yīng)的采樣分辨率采樣點(diǎn)云。對于采樣深度 d，我們確定采樣深度的所有節(jié)點(diǎn)或較粗分辨率的所有葉節(jié)點(diǎn)。此外，八叉樹允許有效地計(jì)算 節(jié)點(diǎn)體積中的積分值：在每個(gè)節(jié)點(diǎn)中，我們維護(hù)位于節(jié)點(diǎn)體積內(nèi)的點(diǎn)值的積分。在樹的構(gòu)建過程中，我們將一個(gè)點(diǎn)的值分配給該點(diǎn)訪問的所有節(jié)點(diǎn)，同時(shí)將它從根遞歸傳遞到它的最終葉節(jié)點(diǎn)。利用這個(gè)屬性，我們可以有效的計(jì)算每個(gè)節(jié)點(diǎn)中點(diǎn)的均值和協(xié)方差。均值：μ；協(xié)方差：

一旦構(gòu)建了八叉樹，我們就可以通過找到樣本協(xié)方差的最小特征值?λ?的特征向量來估計(jì)每個(gè)分辨率上的表面法線。圖 2 展示了本方法在兩個(gè)分辨率上提取的法線示例。

? 圖2我們需要用最少數(shù)量的點(diǎn)來支持法線估計(jì)。通過考慮協(xié)方差矩陣的特征值進(jìn)一步評估法線的質(zhì)量。當(dāng)點(diǎn)主要分布在一個(gè)平面內(nèi)時(shí)， 曲率：γλλλλ?（1）很小；當(dāng)點(diǎn)在平面的兩側(cè)均勻分布時(shí)，λλ的比值接近于1。對這些指標(biāo)進(jìn)行閾值化會(huì)影響平面邊界的法線估計(jì)，最終，我們要求最大特征值?λ?相對于節(jié)點(diǎn)的體積長度而言較大，以便這些點(diǎn)完全分布在整個(gè)體積中。

2、霍夫空間的預(yù)分割

我們使用 Hough 變換在單一分辨率上找到共面面元簇，使用快速的兩階段方法。在第一階段，每個(gè)面元在方向直方圖中為具有相應(yīng)法線的平面投票。按照 Rabbani 的方法，我們將方向直方圖離散化為近似等距的傾斜角和方位角。公式（1）中的曲率方程提供了法線估計(jì)中不確定性的度量。我們使用此曲率將面元??和權(quán)重?的的法線方向分布到直方圖中具有相似方向的范圍中，比如：

其中，是面元中點(diǎn)數(shù)的個(gè)數(shù)，γ是法線曲率的閾值，?和?分別是面元和直方圖的法線， 特別的，α是法線的角度影響范圍。我們檢測局部最大值方向直方圖，以便找到平行面元的簇。在第二階段，我們從平行面元簇中確定共面面元。每個(gè)面元投票決定平面到坐標(biāo)系原點(diǎn)（例如，視點(diǎn)）的距離。與方向直方圖類似，我們將選票分配到具有線性衰減的相鄰箱中。我們在距離直方圖的最大值處再次找到共面面元簇。圖 3 顯示了示例場景中此預(yù)分割步驟的結(jié)果。為了使這個(gè)過程高效，我們保持直方圖的粗分辨率，并將模型參數(shù)的準(zhǔn)確估計(jì)推遲到后期處理階段。然而，距離直方圖的分辨率隨著面元的分辨率而增加。

圖3

3、分割成連通域

霍夫變換不考慮面元的空間連通性。因此，我們從共面元組中提取連通分量。圖 4 舉例說明了這一點(diǎn)。我們在對應(yīng)于面元的霍夫空間最大值的平面上覆蓋一個(gè)網(wǎng)格。網(wǎng)格的分辨率是根據(jù)面元的分辨率來選擇的。我們將每個(gè)面元位置投射到網(wǎng)格中并標(biāo)記占用的網(wǎng)格單元。區(qū)域增長產(chǎn)生連接的組件，當(dāng)組件不受最小數(shù)量的面元（在我們的實(shí)現(xiàn)中設(shè)置為 3）支持時(shí)，我們將丟棄這些組件。

圖4

4、通過 RANSAC 進(jìn)行精確分割

我們進(jìn)一步改進(jìn)了與共面面元的連接組件的平面擬合。由于方向和距離直方圖的粗分辨率，霍夫變換的平面估計(jì)只是對真實(shí)底層平面的粗略估計(jì)。因此，我們將 RANSAC 直接應(yīng)用于面元表示的點(diǎn)。圖 5 顯示了異常值檢測的示例。

? 圖5RANSAC 從一組隨機(jī)的三點(diǎn)樣本中估計(jì)平面參數(shù)。在固定的迭代次數(shù)內(nèi)，我們確定面元的所有點(diǎn)支持的最好的平面估計(jì)。當(dāng)點(diǎn)到平面的距離低于某個(gè)閾值時(shí)，點(diǎn)被接受為平面擬合的內(nèi)點(diǎn)。我們根據(jù)面元的分辨率調(diào)整此閾值。我們只接受大部分面元點(diǎn)支持的平面擬合。我們還要求提取的平面與霍夫變換確定的初始擬合相似。當(dāng)平面擬合被接受時(shí)，我們重新確定線段的連通分量。

5、由粗到細(xì)的分割

在前面的部分中，我們詳細(xì)介紹了如何在單一分辨率上分割平面。然而，我們建議使用由粗到細(xì)的策略來分割場景。通過這種方式，可以僅從幾個(gè)面元中有效地檢測到大平面段。此外，我們的方法固有地適應(yīng)場景中平面的范圍。它使用盡可能多的上下文來決定共面性。我們從粗分辨率到精細(xì)分辨率處理場景。當(dāng)在分辨率上找不到更多的平面段時(shí)，我們過渡到下一個(gè)更精細(xì)的分辨率。為了改進(jìn)已經(jīng)找到的平面片段的分割，我們將更精細(xì)分辨率的面元重新分配到片段上。我們測試面元方向和位置是否適合每個(gè)平面段，以及它是否位于其連接組件的邊界內(nèi)或邊界處。最終，我們還調(diào)整了連接的組件。為此，我們根據(jù)新的分辨率增加了占用圖的采樣率。我們將面元投影到平面段中并標(biāo)記相應(yīng)的單元格被占用。但是，我們保留了前幾層的較粗略的占用決策。請注意，雖然平面段可能會(huì)在此過程中擴(kuò)展，但不會(huì)合并一起增長的段。我們在最后的處理步驟中合并共面連接的段。

6、后處理

在處理完所有分辨率后，我們改進(jìn)了最精細(xì)分辨率的分割。首先，我們合并連接的共面平面段。然后我們在不使用法線信息的情況下將節(jié)點(diǎn)分布到平面段上。對于每個(gè)節(jié)點(diǎn)，我們確定一個(gè)平面段候選列表，這些候選平面段與節(jié)點(diǎn)體積內(nèi)的點(diǎn)的均值距離很小。此外，節(jié)點(diǎn)需要落在連接的組件內(nèi)或每個(gè)候選節(jié)點(diǎn)的邊界。我們進(jìn)一步檢查無法唯一分配給平面段的節(jié)點(diǎn)，并單獨(dú)分布節(jié)點(diǎn)體積中的點(diǎn)。我們根據(jù)距離選擇最好的兩個(gè)候選平面?和?，計(jì)算通過?和?的交線與法線方向的等距平面：

當(dāng)平面段的重心位于該平面的不同側(cè)時(shí)，我們相應(yīng)地將點(diǎn)分布在等距平面的兩側(cè)。否則，我們只是將這些點(diǎn)關(guān)聯(lián)到最近的平面。

實(shí)驗(yàn)結(jié)果

30 幅 ABW 測試圖像的分辨率為 512× 512 像素。該數(shù)據(jù)集還結(jié)合評估工具提供了地面實(shí)況分割。表 1 顯示了我們的方法在 SegComp ABW 測試圖像上的結(jié)果，對于與地面實(shí)況的重疊具有 80% 的容忍度。

? 表1雖然我們的方法不是專門為深度圖像設(shè)計(jì)的，但其分割質(zhì)量和平面擬合精度位于該數(shù)據(jù)集結(jié)果的上限范圍內(nèi)。請注意，最好的分割結(jié)果是通過利用圖像結(jié)構(gòu)中編碼的連接信息的方法獲得的。這也將這些方法限制在處理單視圖深度圖像。此外，距離圖像包含深度離散化效應(yīng)形式的強(qiáng)系統(tǒng)噪聲，這對于僅由少數(shù)點(diǎn)組成的小片段很難處理。為了評估我們算法各個(gè)階段的貢獻(xiàn)，我們對幾個(gè)變體進(jìn)行了測試。RansacOnly 方法使用貪心法來檢測平面（使用點(diǎn)云庫 PCL 實(shí)現(xiàn)）。它在不使用法線信息的情況下迭代地找到適合尚未歸因的點(diǎn)的最佳支持平面。它只能達(dá)到平均性能，其運(yùn)行時(shí)間在很大程度上取決于場景的復(fù)雜性。HoughOnly 基于我們的多分辨率方法，但不執(zhí)行 RANSAC 來改進(jìn)初始 Hough 分割。且與我們的方法相比，HoughOnly 方法分割場景的準(zhǔn)確性較低。圖 6展示了我們的方法在不同重疊公差 SegComp ABW 測試圖像上的結(jié)果?？梢钥闯?，我們的方法中的錯(cuò)誤在很大程度上是由于缺少平面段造成的。對于高噪聲，某些點(diǎn)可能未分配給平面或邊界可能無法正確解析。由于我們的方法不考慮圖像鄰域，因此很難達(dá)到 90% 的重疊。圖 5展示了 ABW 數(shù)據(jù)集的兩個(gè)示例性分割。在左圖中，我們的算法遺漏了多個(gè)平面片段。我們將一些未命中歸因于八叉樹的離散化。這個(gè)問題可以通過在不同的離散化中重新處理未分段的部分來解決。

圖6

總結(jié)與展望

本文，我們提出了一種從 3D 點(diǎn)云中提取平面的有效方法。我們將 Hough 變換與RANSAC 相結(jié)合，以在多種分辨率下擬合平面。通過使用由粗到精的策略，我們可以有效地利用可用數(shù)據(jù)。它允許考慮最大可能的上下文來做出共面性的決定。這也使我們的方法數(shù)據(jù)高效。在實(shí)驗(yàn)中，將改方法與使用 SegComp 數(shù)據(jù)庫的最先進(jìn)方法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，我們以高幀率和高質(zhì)量處理 3D 激光和深度傳感器（例如 Kinect）的 3D 點(diǎn)云。在未來的工作中，我們將提取更多類型的幾何形狀圖元，例如圓柱體和球體。我們還計(jì)劃調(diào)整我們的方法來順序處理來自 Kinect 等高幀率傳感器的深度圖像。

本文僅做學(xué)術(shù)分享，如有侵權(quán)，請聯(lián)系刪文。

3D視覺工坊精品課程官網(wǎng)：3dcver.com

1.面向自動(dòng)駕駛領(lǐng)域的3D點(diǎn)云目標(biāo)檢測全棧學(xué)習(xí)路線！(單模態(tài)+多模態(tài)/數(shù)據(jù)+代碼)

2.徹底搞透視覺三維重建：原理剖析、代碼講解、及優(yōu)化改進(jìn)

3.國內(nèi)首個(gè)面向工業(yè)級實(shí)戰(zhàn)的點(diǎn)云處理課程

4.激光-視覺-IMU-GPS融合SLAM算法梳理和代碼講解

5.徹底搞懂視覺-慣性SLAM：基于VINS-Fusion正式開課啦

6.徹底搞懂基于LOAM框架的3D激光SLAM: 源碼剖析到算法優(yōu)化

7.徹底剖析室內(nèi)、室外激光SLAM關(guān)鍵算法原理、代碼和實(shí)戰(zhàn)(cartographer+LOAM +LIO-SAM)

8.從零搭建一套結(jié)構(gòu)光3D重建系統(tǒng)[理論+源碼+實(shí)踐]

9.單目深度估計(jì)方法：算法梳理與代碼實(shí)現(xiàn)

10.自動(dòng)駕駛中的深度學(xué)習(xí)模型部署實(shí)戰(zhàn)

11.相機(jī)模型與標(biāo)定(單目+雙目+魚眼）

12.重磅！四旋翼飛行器：算法與實(shí)戰(zhàn)

13.ROS2從入門到精通：理論與實(shí)戰(zhàn)

14.國內(nèi)首個(gè)3D缺陷檢測教程：理論、源碼與實(shí)戰(zhàn)

15.基于Open3D的點(diǎn)云處理入門與實(shí)戰(zhàn)教程

16.透徹理解視覺ORB-SLAM3：理論基礎(chǔ)+代碼解析+算法改進(jìn)

17.不斷更新中......

重磅！粉絲學(xué)習(xí)交流群已成立

交流群主要有3D視覺、CV&深度學(xué)習(xí)、SLAM、三維重建、點(diǎn)云后處理、自動(dòng)駕駛、多傳感器融合、CV入門、三維測量、VR/AR、3D人臉識(shí)別、醫(yī)療影像、缺陷檢測、行人重識(shí)別、目標(biāo)跟蹤、視覺產(chǎn)品落地、視覺競賽、車牌識(shí)別、硬件選型、ORB-SLAM系列源碼交流、深度估計(jì)、TOF、求職交流等方向。

添加小助理微信（dddvisiona）,一定要備注：研究方向+學(xué)校/公司+昵稱，例如：”3D視覺 + 上海交大 + 靜靜“。請按照格式備注，可快速被通過且邀請進(jìn)群。原創(chuàng)投稿也請聯(lián)系。?