基于斐波那契采樣的三維線云模型平面提取算法

武 凱 周佳新 程章林

1(中國科學院深圳先進技術研究院 深圳 518055)

2(中國科學院大學計算機科學與技術學院 北京 100049)

1 引 言

近年來，隨著虛擬現(xiàn)實和圖形學的發(fā)展，三維場景模型在智慧城市、三維地圖導航和文娛生活等場景中都具有廣泛的應用，因而吸引了大量學者對其進行研究[1-4]。在城市場景三維重建中，由于平面是構成最終多面體幾何模型中十分重要的元素，因此平面提取是解決城市場景三維重建的重要環(huán)節(jié)之一。

平面提取是從已采集的三維數(shù)據(jù)中提取可能存在的平面。其中，傳統(tǒng)的方法(主要對點云模型進行處理)主要包括基于隨機抽樣一致(Random Sample Consensus，RANSAC)的平面擬合算法[5-6]、基于數(shù)據(jù)之間相似性的區(qū)域增長算法[7-8]以及基于霍夫變換[9-10]的平面擬合算法。由于點云具有數(shù)據(jù)量龐大、噪聲繁雜等特性，基于點云的平面提取算法往往耗時較長，且精準性較差。目前，城市場景三維重建中的研究對象主要是一些規(guī)則的物體[11]，如城市中的建筑物通常是由規(guī)則的邊線構成，通過觀察分析這些邊線就能推斷整個建筑物的整體形狀。線云的概念和點云類似，是由若干線段構成的集合。相較于使用點云數(shù)據(jù)，三維線段是比點更高一級的幾何圖元數(shù)據(jù)，不僅包含位置信息，還含有三維點所不能表示的方向信息。此外，同等場景下線云數(shù)據(jù)的量級比點云數(shù)據(jù)小。因此，合理地利用線段信息能夠減少平面提取的難度，提高平面提取的效率和精度。

鑒于線云具有數(shù)據(jù)量小、蘊含信息量大等優(yōu)勢，近年來，研究人員逐漸將研究重點轉向獲取三維線云數(shù)據(jù)[12-15]，并開始研究基于線云數(shù)據(jù)的三維重建算法[16-17]。然而，目前基于三維線云進行平面提取的方法較少。雖然可以類比點云的平面提取算法進行實現(xiàn)，但是這些方法都具有一定的局限性。例如，與基于區(qū)域增長的算法依賴初始種子的選取以及需要相對稠密的數(shù)據(jù)相反，基于 RANSAC 的平面提取方法適合使用稀疏數(shù)據(jù)。但因該方法使用隨機采樣，較為依賴采樣次數(shù)且隨機性較大導致結果的精度不夠。基于霍夫變換的方法先將原始數(shù)據(jù)投影到霍夫空間，使真實空間中的一個平面映射至霍夫空間中的一個點，然后利用投票機制確定平面的參數(shù)。由于每個平面的參數(shù)有較大差異，難以確定該方法的參數(shù)空間的范圍且網(wǎng)格劃分也比較困難。以極坐標表示的霍夫空間，雖然能有效縮減范圍，但仍難以均勻劃分空間。

針對以上基于三維線云的平面提取算法存在的問題，本文提出一種新的基于線云數(shù)據(jù)的平面提取算法。主要步驟包括：首先，將輸入線云的每條線段映射成高斯球面上的一個點；其次，使用螺旋曲線斐波那契采樣對高斯球表面空間做近似均勻采樣，并對過球心的平面進行擬合；然后，根據(jù)平面方程的截距信息分離出平行的平面并使用奇異值分解修正采樣造成的誤差；最終，迭代擬合出所有可能存在的平面。該方法具有兩個創(chuàng)新點：(1)將線云提取平面的問題轉換為高斯球表面空間的采樣問題，簡化了問題的復雜性；(2)在高斯球表面使用螺旋曲線斐波那契采樣，使采樣空間分布更加均勻，提高了最終平面提取的質(zhì)量。

2 相關工作

根據(jù)三維數(shù)據(jù)的輸入源分類，平面擬合的算法可以分為基于點云模型的平面提取算法和基于線云模型的平面提取算法。

2.1 基于點云模型的平面提取算法

基于 RANSAC 的平面提取算法首先隨機采樣可以構成平面的點；然后計算其余點到該平面的距離，統(tǒng)計距離小于一定閾值的點并將這些點歸類于該平面，隨后計算最終平面上點的數(shù)量。經(jīng)過多次迭代，選出具有點數(shù)最多的平面作為新擬合的平面。之后，繼續(xù)在剩余的數(shù)據(jù)中迭代擬合其他平面，直至達到終止條件。該方法在選擇合適的參數(shù)下能夠得到較好的結果，但其因隨機采樣和依賴參數(shù)控制，得到的結果可能并非實際的最優(yōu)解。Li 等[18]提出一種利用法線方向和鄰近信息從點云中提取所有的子結構，進而在子結構上進行平面信息提取的方法。該方法作為基于 RANSAC 的方法的變種，在重建結果的精度上有很大的提升，但其缺點是難以確定子結構的大小。Yue 等[19]提出一種基于法線聚類和帶約束初始點的 RANSAC 分割方法，該方法首先使用 Mean Shift 的方法求解點云法線，然后基于法線的初始約束執(zhí)行 RANSAC 的方法完成平面分割?；趨^(qū)域增長的方法首先選取種子點，然后設定增長條件和中止條件，算法將自動搜尋所有構成平面的點。然而，選取種子點缺乏統(tǒng)一的標準，這限制了區(qū)域增長算法的精確性和魯棒性[20-21]。目前，許多高效的初始點選擇方法已被提出，其中，最為經(jīng)典的方法是將點云中具有最小曲率的點作為初始點進行區(qū)域增長[22-23]。區(qū)域增長算法實現(xiàn)簡單，但是對噪聲十分敏感，當不同區(qū)域之間過度平滑時，系統(tǒng)難以將平面結構區(qū)分開[24]。Li 等[25]采用分層聚類的方式解決初始點選擇困難的問題，完成了對屋頂平面分割的任務?；诨舴蜃儞Q的方法——利用投票機制將原始數(shù)據(jù)投影到霍夫空間來確定具體的參數(shù)，常用于二維直線和圓的檢測。對三維平面而言，霍夫空間中的每一個點都與真實空間中的一個平面對應，通過離散采樣并統(tǒng)計霍夫空間中的峰值可以確定三維空間中平面的參數(shù)。此類方法雖然對噪聲不敏感，但是存在參數(shù)空間分布不一致的現(xiàn)象。對此，也有學者提出解決方法，如章大勇等[10]采用一種基于對偶空間分割的三維霍夫變換方法將球面采樣區(qū)域劃分為多個對稱的區(qū)域，然后在這些區(qū)域中借助不同的參數(shù)進行采樣，一定程度上消除了變換帶來的采樣區(qū)域不一致。此外，Tian 等[26]使用 GPU 并行加速基于霍夫變換的平面提取算法，實現(xiàn)了對三維激光雷達點云的快速平面檢測。

2.2 基于線云模型的平面提取算法

相較于從點云數(shù)據(jù)中提取平面，目前對利用線段等輪廓信息進行平面提取的方法研究較少。Wu 等[27]提出先從點云中獲取交叉線段結構，再進一步提取平面信息的方法。Zhang 等[28]利用局部信息，通過計算線段之間的距離并進行譜聚類，以實現(xiàn)平面結構的提取。由于該方法需要計算局部信息，而現(xiàn)實中的建筑物在不同平面上線段的分布密度很可能不同，因而參數(shù)范圍的設定存在較大困難。Cabo 等[29]使用激光掃描數(shù)據(jù)，并利用 3D 線段檢測平面，但是它使用了激光雷達采集數(shù)據(jù)的強大特性，即采集的數(shù)據(jù)是相互平行而且密集的線云。

綜上所述，大多數(shù)平面提取算法是基于點云模型或分析點云模型中的線段信息來進行平面擬合，系統(tǒng)仍然需要處理繁多的點云數(shù)據(jù)。直接以線云模型作為輸入提取平面的相關研究較少，且現(xiàn)有的基于線云模型平面提取算法的普適性較差，通常對輸入的線云有較高的要求，如需要密度分布均勻的線云信息[28]或是相互平行且密集的線云[29]。

3 基于斐波那契采樣的三維線云模型平面提取算法

本文提出一種新的基于斐波那契采樣的三維線云模型平面提取算法，算法流程主要包括數(shù)據(jù)獲取和預處理、球面近似均勻采樣、統(tǒng)計采樣點以及平面擬合等 4 個步驟。其中，統(tǒng)計采樣點和平面擬合步驟是迭代過程，流程如圖 1 所示。

圖1 方法流程圖Fig.1 Method flow

3.1 數(shù)據(jù)獲取和預處理

3.1.1 數(shù)據(jù)獲取

圖2 數(shù)據(jù)獲取Fig.2 Data collection

3.1.2 數(shù)據(jù)預處理

圖3 數(shù)據(jù)預處理Fig.3 Data preprocessing

理論上，空間中一組共面的線段對應于高斯球上一個過球心的平面。由此，基于三維線段的平面提取問題可轉換為高斯球上過球心平面的檢測問題。同時，對于每個經(jīng)過高斯球球心的圓面，其用單位向量表示的法線也恰好對應高斯球面上的一個點。于是，過球心平面的確定也可以轉化為高斯球面上點的確定。這樣的處理不僅簡化了三維線段的表達，降低了數(shù)據(jù)處理的難度，同時，也將復雜的平面擬合問題轉換為高斯球面上點的采樣問題。

值得注意的是，高斯球面上的點，僅表示三維線段的方向，而丟失了垂直于其方向的位置信息。因此，檢測得到過高斯球球心的圓面之后，圓面上共面的點集對應原始三維線云模型中的線段集合并不一定全部共面，需要在后續(xù)過程中，結合原始的三維線段信息作進一步處理。但總體而言，將復雜的平面擬合問題轉換為高斯球面上點的采樣問題，極大地簡化了問題。

3.2 球面近似均勻采樣

盡管數(shù)據(jù)經(jīng)過預處理后得到了簡化，但基于點的平面檢測由于噪聲的存在，不宜直接通過 RANSAC 實現(xiàn)。而基于霍夫變換的方法，難以劃分均勻的網(wǎng)格，仍然存在采樣空間分布不均的現(xiàn)象。受霍夫變換投票機制的啟發(fā)，本文使用螺旋曲線斐波那契采樣方法對高斯球面上的點進行近似均勻采樣，以得到可能存在的平面法線，從而確定過高斯球球心的平面。采用斐波那契螺旋曲線在球面上生成均勻分布的點有著出色的效果，有研究表明，與用經(jīng)緯網(wǎng)格測量球面上不規(guī)則圖形的面積相比，使用斐波那契網(wǎng)格測量球面上不規(guī)則圖形的面積，加權誤差可以減小40%[30]。

圖4 采樣點示意圖Fig.4 Schematic diagram of sampling points

3.3 統(tǒng)計采樣點

3.4 平面擬合

通過統(tǒng)計采樣點過程能夠獲得待擬合平面的線段集合Lm。然而，由于將三維線段映射到高斯球面上時，損失了直線的截距信息，因此統(tǒng)計采樣點過程獲得的線段集合Lm可能表示一個平面或者多個平行的平面。即在高斯球上共面的線段集合對應的真實空間中三維線段集合有可能位于多個平行平面上。鑒于這些平面具有相同的法線且僅具有不同的截距，依據(jù)截距的差異便可分離出多個平行平面。

為了提取精確的單個平面，本文使用平面的截距信息對線段集合進行劃分，并選擇劃分后具有最多數(shù)量的線段集合作為此次迭代提取的平面，一次平面擬合的過程如下：(1)給定統(tǒng)計采樣點過程中得到的線段集合Lm以及采樣點tm對應的單位方向向量u。

(4)當線段集合C中線段的數(shù)量小于指定閾值λ時，表示集合C中線段無法構成平面，平面提取算法結束。

每次平面擬合迭代過程結束之后，需要刪除已經(jīng)用于構建平面的線段集合C，以及集合C中線段對應在高斯球面上的點，更新原始線段集合L以及高斯球面上的點集S。隨后進行下一輪的統(tǒng)計采樣點和平面擬合過程，直至算法達到運行結束條件。

此外，在完成平面擬合迭代過程之后，由于離散采樣法線存在一定誤差，可能存在提取的兩個或多個平面非常相近, 如圖 5 所示，圖 5(a)和圖 5(b)兩個平面對應原始模型中同一個平面。因此，在完成平面提取后需要進行一個后處理：將在角度誤差閾值 之內(nèi)相互平行且截距之差在距離誤差閾值 之內(nèi)的平面合并，并使用奇異值分解修正最終的平面參數(shù)。本文方法中 取2，后處理結果如圖 5(c)所示。需要說明的是，得到多個相似平面是所有平面擬合算法都會存在的問題，因此在本文實驗中，對所有平面擬合方法均進行相同的后處理操作。

圖5 重復表達的兩個平面Fig.5 Two planes of repeated expression

4 結果與討論

與其他傳統(tǒng)的方法相比，本文提出的平面提取算法的特點是：直接以線云作為算法輸入，提取平面的完整性和質(zhì)量都很高。其中，提取平面的完整性高說明算法提取平面的能力強。為了驗證本文算法的有效性，從兩個方面分析實驗結果：(1)提取平面的完整性和效率；(2)提取平面的質(zhì)量。同時，本文在多個數(shù)據(jù)樣本下進行了實驗，并與傳統(tǒng)方法的實驗結果進行對比。

4.1 實驗設置

對于不同方法的實驗參數(shù)盡可能選擇保持一致，本實驗中采用的參數(shù)如表 1 所示。

表1 不同算法的參數(shù)Table 1 Parameters of different algorithms

除了以上共同的參數(shù)之外，每種方法均需要設置額外的不同參數(shù)。在基于 RANSAC 的方法中，需要額外指定隨機采樣的次數(shù)，本文設置隨機采樣次數(shù)為 10 000。在霍夫變換方法中，需要指定采樣步長為霍夫空間中采樣點之間的角度差，實驗中設置采樣步長為 18 °。經(jīng)試驗，在步長為 18 ° 時，霍夫空間中需要采樣 10 000 次。此外，本文方法需要額外指定近似均勻采樣中需要的采樣點個數(shù)，為保證與基于霍夫變換的方法和基于 RANSAC 的方法的采樣次數(shù)一致，本文方法設置采樣點個數(shù)為 10 000。

4.2 完整性

衡量平面提取算法的一個標準是提取平面的完整性，即能從線云中提取更多的符合原始線云模型的平面。本文在 4 個線云模型實例上進行實驗，并與傳統(tǒng)方法的實驗結果進行對比。不同方法提取線段的結果如圖 6 所示，圖 6(a)為輸入的4 個線云模型，圖 6(b～d)分別為基于 RANSAC的方法、基于霍夫變換的方法和本文方法對線云模型提取平面的結果。其中，提取的不同平面分別以不同的顏色標注。結果表明，本文方法提取的平面更加完整，缺失的線段數(shù)量最少。

圖6 平面提取結果對比Fig.6 Comparison of plane extraction results

平面提取算法的完整性越高，從線云中提取符合原始線云模型的平面越多。為了定量地評估算法提取平面的完整性，本文統(tǒng)計了平面擬合算法提取的平面?zhèn)€數(shù)以及有效平面占比。一般來說，提取平面的個數(shù)越多越能體現(xiàn)平面擬合算法對原始數(shù)據(jù)的表達能力。然而，并不是所有提取的平面都符合原始數(shù)據(jù)，即算法提取的平面與原始線云數(shù)據(jù)中對應的平面有較大差異，該平面無法對原始數(shù)據(jù)進行有效表達。因此，本文另外統(tǒng)計了平面擬合算法的有效平面占比，進一步衡量平面擬合算法對原始線云模型數(shù)據(jù)的表達能力。

本文使用不同平面提取方法對 4 個線云模型實例進行實驗的數(shù)據(jù)統(tǒng)計結果如表 2 所示，表中數(shù)據(jù)均為算法運行 10 次的平均結果。其中，模型一和模型二是較為干凈的線云數(shù)據(jù)，模型三和模型四是噪聲較大的線云數(shù)據(jù)，且模型四的場景更加復雜。

從表 2 統(tǒng)計數(shù)據(jù)可以看出，在以上 4 個模型實例中，本文方法提取的有效平面?zhèn)€數(shù)最多且有效平面占比最高，說明本文方法提取的平面更完整。基于 RANSAC 的方法的提取結果同樣十分優(yōu)秀，但是因為隨機采樣可能產(chǎn)生非最優(yōu)的結果，最終可能提取一些不合理的平面。圖 7 展示了提取有效平面和無效平面的結果對比，圖 7(a)呈現(xiàn)了預期提取的平面區(qū)域，圖 7(b)是本文算法提取的平面，圖 7(c)為基于 RANSAC 的方法提取的平面。結果表明，本文方法提取的平面能夠較好地對應原始線云，記為一個有效平面。然而，基于 RANSAC 的方法因為離群噪聲線段的影響，干擾了平面提取的過程，使得提取的平面相較于原始線云有較大偏差，這里記為無效的提取平面?；诨舴蜃儞Q的方法由于采樣空間不均勻，提取較多不合理的平面，導致有效平面占比較低，平面提取的完整性較差。如表 2 中模型三和模型四的結果所示，當線云數(shù)據(jù)中含有較大噪聲時，基于 RANSAC 的方法和基于霍夫變換的方法提取的有效平面占比顯著下降，這是因為離群的噪聲線段對 RANSAC 的隨機采樣過程造成了較大干擾，基于霍夫變化的方法對噪聲比較敏感。相較于其他兩種算法，本文方法對于具有較大噪聲和較復雜場景的線云數(shù)據(jù)仍表現(xiàn)十分穩(wěn)定。

圖7 有效平面和無效平面的對比Fig.7 Comparison of effective plane and invalid plane

表2 不同平面提取方法的結果比較Table 2 Comparison of the results of plane extraction by different methods

在運行時間方面，基于霍夫變換的方法有最好的時間復雜度，這是因為霍夫變換利用對偶信息計算每條線段經(jīng)過了哪些采樣點，而不用遍歷每個采樣點。基于 RANSAC 的方法和本文方法略慢于基于霍夫變換的方法。當場景數(shù)據(jù)含有較大噪聲且場景較復雜時，由于基于霍夫變換的方法提取了許多不合理的平面，導致該方法的效率有所下降。

4.3 提取平面的質(zhì)量

衡量平面提取算法效果的另一個標準是提取平面的質(zhì)量，由于難以對平面提取的質(zhì)量進行定量評估，本文分別對比了使用不同方法提取相同平面的實驗結果，并對這些結果進行定性分析。圖 8 展示了不同方法提取相同平面的結果，自上而下共展示了 4 個平面擬合的結果，圖 8(a)中紅色方框的區(qū)域為提取的單個平面對應在原始圖像和線云的區(qū)域，圖 8(b～d)分別為基于 RANSAC的方法、基于霍夫變換的方法和本文方法提取的單個平面。由于缺失所提取平面的真實平面參數(shù)，難以量化提取平面是否準確。然而，通過觀察所提取平面中線段集合的構成能直觀感知所提取平面的質(zhì)量。當平面上線段集合與原始線云和參考圖像更契合時，可以認為對該平面的提取更準確。

圖8 不同方法提取相同平面的結果對比Fig.8 Comparison of the results of different methods extracting the same plane

從圖 8 可以看出，本文方法提取的平面中線段集合的構成能更準確地對應原始線云模型以及圖像中的平面結構，且較少包含其他平面上的線段信息。這很大程度反映了本文算法所提取平面參數(shù)的準確性更高。這主要是因為本文采用螺旋曲線斐波那契的方法進行了近似均勻采樣，使空間的劃分更均勻，因而提取的擬合平面的線段集更精確，效果更好。相較于其他兩種方法，基于 RANSAC 的方法提取平面的質(zhì)量綜合結果最差，這是因為該方法隨機采樣構造初始平面，導致提取平面參數(shù)的穩(wěn)定性較差。

5 結 論

本文提出一種基于線云模型的平面提取方法，并采用螺旋曲線斐波那契的方法對采樣空間進行近似均勻劃分以提高平面擬合的結果。實驗結果表明，與基于 RANSAC 的方法和基于霍夫變換的方法相比，本文方法在提取平面的完整性以及提取平面的質(zhì)量方面具有更高的優(yōu)越性。但是本文方法仍存在一定的局限性——運行效率較慢。在未來的工作中，將深入研究在保證現(xiàn)有的平面提取效果的同時，進一步提高算法的效率。