1 引言

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

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

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

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

　　采樣問題，簡化了問題的復雜性;(2) 在高斯球表面使用螺旋曲線斐波那契采樣，使采樣空間分布更加均勻，提高了最終平面提取的質量。

　　2 相關工作

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

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

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

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

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

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

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

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

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

　　3.1.1 數(shù)據獲取

　　本文算法的輸入是三維線云。為了更方便地獲取數(shù)據，本方法使用 Hofer 等提出的 Line3D 從多副圖像中獲得場景的三維線云。與三維點重建類似，利用圖像中的直線結構重建三維線段。Hofer 等采用 Structure-from-Motion 提供的相機姿態(tài)解決不同圖像之間線段匹配的問題，從而構建出三維線云。本文算法首先使用消費級相機采集若干場景圖像，然后將圖像序列輸入 Line3D 中重構出原始線云作為本文算法的輸入。獲取的三維線云用集合 表示，其中，k 表示線云模型中線段的總數(shù)量;li 表示位于集合 L 中 第個線段。從圖像序列中提取線云的一個實例如圖 2 所示。

　　圖 1 方法流程圖

　　圖 2 數(shù)據獲取

　　3.1.2 數(shù)據預處理

　　原始輸入的三維線云模型，線段之間非常雜亂。不同的線云模型也具有不同的空間范圍，數(shù)據處理比較困難。由于判斷一條線段是否位于特定平面，取決于該線段的方向，以及二者是否存在交點，而與線段的長度無關。據此，本文將線云模型中的每條線段映射到半徑為 1 的高斯球面上，如圖 3 所示。具體操作是：先將每條三維線段的長度單位化;然后平移每條線段，使得線段的一個端點位于坐標原點，則另一個端點位于半徑為 1 的高斯球面上。將三維線云模型 L 映射到高斯球上得到一個新的點集，其中，k 表示集合中線段的總數(shù)量;si 表示位于集合 S 中第 個點。集合L 與集合 S 中的元素一一對應。

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

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

　　3.2 球面近似均勻采樣

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

　　采樣點構成的集合用 表示，其中，n 表示集合中采樣點的總數(shù)量;ti 表示位于集合 T 中第 個采樣點。圖 4 展示了使用螺旋曲線斐波那契采樣對高斯球面采樣的示意圖。　　

　　圖 3 數(shù)據預處理

　　圖 4 采樣點示意圖

　　3.3 統(tǒng)計采樣點

　　區(qū)別于霍夫變換中的統(tǒng)計方式，在近似均勻采樣過程中每個采樣點代表對應平面的法向量。因此，近似均勻采樣過程之后， 需要統(tǒng)計以該采樣點作為法向量確定的過高斯球球心的圓面上所有點的數(shù)量。當點的數(shù)量大于指定閾值，說明圓面上的這些點可以擬合出該圓面，即對應原始三維線云中的線段集合可能存在待擬合的平面。統(tǒng)計采樣點的具體過程包括：對于每個采樣點，計算高斯球球心 o 和高斯球面上每個點構成的向量os_j與采樣點t_i方向之間的夾角，當 處于 范圍時，認為該高斯球面上的屬于 t_i采樣點。由于線云模型的獲取過程存在誤差，不能準確地獲得每條直線在三維空間中的方向。因此， 本文設定一個角度誤差閾值 ，若兩個向量之間的夾角處于誤差范圍內，便認為兩向量垂直。對每個采樣點，統(tǒng)計過高斯球球心的圓面上所有點的數(shù)量，找出具有最多數(shù)量的點集 S_m  以及 S_m  對應的原始線段集合中的子集合 L_m ，同時記錄對應的采樣點t_m。線段集合  L_m  和采樣點t_m將作為平面擬合的依據。

　　3.4 平面擬合

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

　　為了提取精確的單個平面，本文使用平面的截距信息對線段集合進行劃分，并選擇劃分后具有最多數(shù)量的線段集合作為此次迭代提取的平面，一次平面擬合的過程如下：

　　(1) 給定統(tǒng)計采樣點過程中得到的線段集合 L_m  以及采樣點t_m 對應的單位方向向量 u。

　　(2) 對每條原始的線段以其中點作為代表，計算在向量 u 方向上的投影 d_i。

　　(3)計算以向量 u 作為法線的平面 P 的截距 d_p，使得截距在    范圍的線段集合 C 中的數(shù)量最多，其中 為距離誤差閾值。隨后對該平面線段集采用奇異值分解修正由范圍采樣造成的誤差，以確定最終的平面參數(shù)。

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

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

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

　　4 結果與討論

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

　　4.1 實驗設置

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

　　其中，距離誤差閾值 表示當直線與平行平面之間的距離在  范圍內時，認為直線位于平行平面上，本文實驗中   取 0.1 m。角度誤差閾值表示當兩條直線之間的夾角在范圍時，認為兩條直線垂直，本文實驗中 取1.5 ?。由于在霍夫變換中，采樣空間按經緯度進行劃分， 所以霍夫變換中的角度閾值與實際采樣的大小有關，在霍夫變換的方法中不設置角度誤差閾值  。λ 表示可以構成平面的最少線段數(shù)目，在這 3 種方法中均設定為 15。

　　表 1 不同算法的參數(shù)

　　圖 5 重復表達的兩個平面

　　圖 6 平面提取結果對比

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

　　4.2 完整性

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

　　圖 7 有效平面和無效平面的對比

　　表 2 不同平面提取方法的結果比較

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

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

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

　　圖 8 不同方法提取相同平面的結果對比

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

　　4.3 提取平面的質量

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

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

　　5 結論

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

   作者：武 凱 1,2 周佳新 1,2 程章林 1*

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

　　      2 中國科學院大學計算機科學與技術學院

　      　轉載自《集成技術》