一種有效將3D點(diǎn)云分割成平面組件的多分辨率方法

摘要

本文提出了一種有效的多分辨率方法將 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è)大小相等的立方體（稱為八分圓）。對(duì)于它的每個(gè)八分圓，該節(jié)點(diǎn)都包含一個(gè)子節(jié)點(diǎn)，該子節(jié)點(diǎn)本身是一個(gè)分支節(jié)點(diǎn)，或者是樹中的一片葉子。 八叉樹可以用于以與樹的不同深度中節(jié)點(diǎn)的體積大小相對(duì)應(yīng)的采樣分辨率采樣點(diǎn)云。對(duì)于采樣深度 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)。

圖2

在第二階段，我們從平行面元簇中確定共面面元。每個(gè)面元投票決定平面到坐標(biāo)系原點(diǎn)（例如，視點(diǎn)）的距離。與方向直方圖類似，我們將選票分配到具有線性衰減的相鄰箱中。

我們?cè)诰嚯x直方圖的最大值處再次找到共面面元簇。圖 3 顯示了示例場景中此預(yù)分割步驟的結(jié)果。為了使這個(gè)過程高效，我們保持直方圖的粗分辨率，并將模型參數(shù)的準(zhǔn)確估計(jì)推遲到后期處理階段。然而，距離直方圖的分辨率隨著面元的分辨率而增加。

圖3

3、分割成連通域

霍夫變換不考慮面元的空間連通性。因此，我們從共面元組中提取連通分量。圖 4 舉例說明了這一點(diǎn)。我們?cè)趯?duì)應(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ì)只是對(duì)真實(shí)底層平面的粗略估計(jì)。因此，我們將 RANSAC 直接應(yīng)用于面元表示的點(diǎn)。圖 5 顯示了異常值檢測的示例。

圖5 RANSAC 從一組隨機(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ì)的分割

在前面的部分中，我們?cè)敿?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)的單元格被占用。但是，我們保留了前幾層的較粗略的占用決策。請(qǐng)注意，雖然平面段可能會(huì)在此過程中擴(kuò)展，但不會(huì)合并一起增長的段。我們?cè)谧詈蟮奶幚聿襟E中合并共面連接的段。

6、后處理

在處理完所有分辨率后，我們改進(jìn)了最精細(xì)分辨率的分割。首先，我們合并連接的共面平面段。然后我們?cè)诓皇褂梅ň€信息的情況下將節(jié)點(diǎn)分布到平面段上。對(duì)于每個(gè)節(jié)點(diǎn)，我們確定一個(gè)平面段候選列表，這些候選平面段與節(jié)點(diǎn)體積內(nèi)的點(diǎn)的均值距離很小。此外，節(jié)點(diǎn)需要落在連接的組件內(nèi)或每個(gè)候選節(jié)點(diǎn)的邊界。

當(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é)合評(píng)估工具提供了地面實(shí)況分割。表 1 顯示了我們的方法在 SegComp ABW 測試圖像上的結(jié)果，對(duì)于與地面實(shí)況的重疊具有 80% 的容忍度。

表1

雖然我們的方法不是專門為深度圖像設(shè)計(jì)的，但其分割質(zhì)量和平面擬合精度位于該數(shù)據(jù)集結(jié)果的上限范圍內(nèi)。請(qǐng)注意，最好的分割結(jié)果是通過利用圖像結(jié)構(gòu)中編碼的連接信息的方法獲得的。這也將這些方法限制在處理單視圖深度圖像。此外，距離圖像包含深度離散化效應(yīng)形式的強(qiáng)系統(tǒng)噪聲，這對(duì)于僅由少數(shù)點(diǎn)組成的小片段很難處理。

為了評(píng)估我們算法各個(gè)階段的貢獻(xiàn)，我們對(duì)幾個(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ò)誤在很大程度上是由于缺少平面段造成的。對(duì)于高噪聲，某些點(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 等高幀率傳感器的深度圖像。

審核編輯：劉清