一種基于移動最小二乘法的點云數據孔洞修補算法研究

劉許　宋陽

摘 要： 使用測量儀器獲取點云數據的過程中，由于測量儀器自身缺陷、物體局部遮擋等因素，導致原始點云數據存在孔洞，嚴重影響曲面重建，需要實施孔洞修補，以便獲取完整的模型。采用非封閉孔洞相連的散亂點云的邊界確定孔洞修補范圍，有效提取非封閉的孔洞邊界點及附近模型的邊界點，根據孔洞及其周圍點的信息，基于移動最小二乘法重構一個隱式曲面，并且通過一定步長實施隱式曲面采樣，完成孔洞修補。實驗結果顯示該算法可以修補不同類型的孔洞，并且修補數據與原始點云數據較好的融合在一起，恢復原始模型。

關鍵詞： 移動最小二乘法； 點云數據； 孔洞曲面； 修補數據

中圖分類號： TN98?34 文獻標識碼： A 文章編號： 1004?373X（2017）05?0101?04

Abstract： In the process of acquiring the point cloud data with the measuring instrument， the holes exist in the original point cloud data due to the defect of the measuring instrument itself， object partial occlusion and other factors， which seriously affect on the surface reconstruction， and it is necessary to repair the hole to get a complete model. The scattered point cloud boundary connected with the non?closed hole is used to determine the hole repairing range， and extract the boundary points of the non?closed hole and nearby model. According to the hole and information around it， an implicit surface was reconstructed based on the moving least square method， and sampled with a certain step to repair the hole. The experimental results show this algorithm can repair the holes of different types， and fuse the repaired data with the original point cloud data together to restore the original model.

Keywords： moving least square method； point cloud data； hole surface； repairing data

0 引 言

中國的古代建筑是中國歷史的重要見證，代表中國建筑的繼承與發展，保護這類風格的建筑，也就是保護中國的歷史，是現代人義不容辭的任務[1]。隨著激光測繪、計算機虛擬、圖像處理、三維建模等技術的快速發展，三維激光掃描技術與虛擬現實技術在此基礎上亦得到較大改進，已經在古建筑重建、模具制造、3D打印等領域得到了廣泛的普及和應用，取得了較好的效果[2?5]。三維點云數據采集過程中，由于模型自身損壞、激光掃描視線遮擋等原因，造成點云數據缺失，直接影響建模質量，因此，為了促使建模呈現光滑，需要進行孔洞修復[5?6]。

點云數據孔洞修補算法得到了改進和發展，但是由于測量物體及儀器自身缺陷、測量環境復雜等因素，導致測量的點云數據存在許多的非封閉孔洞。為了能夠更好地實現非封閉孔洞修補，本文提出采用非封閉孔洞相連的散亂點云的邊界確定孔洞修補范圍，采用三次曲線邊界可以擬合模型邊界點，根據孔洞及其周圍點的信息，基于移動最小二乘法重構一個隱式曲面，并且通過一定步長實施隱式曲面采樣，完成孔洞修補，實驗結果表明該算法能夠很好地恢復古建筑容貌[7?9]。

1 非封閉孔洞的提取和檢測

大量的古籍文物在保護和恢復過程中，需要重建其往日容貌，但是拍攝工具及古籍文物自身的缺陷容易導致產生非封閉孔洞，需要尋找一種有效的算法，對其進行優化、修補。因此，準確的提取和檢測非封閉孔洞已經成為孔洞修補的基礎工作，具有重要的作用。如果點[P]的K?鄰近反映有實際曲面的邊界存在，并且點[P]就存在于邊界上，因此點[P]就被稱為邊界特征點。基于K?鄰近點的毗鄰關系可以提取邊界特征點，通過K?鄰近點向其切平面投影可以建立毗鄰關系。連接K?鄰近點的投影點與形心的投影點形成一條線段，以該線段為起始邊，逆時針旋轉，可以計算該線段與其他線段的投影角，并且可以對投影角進行排序，排序完成之后，將投影角按照前后順序相減，可以計算出K?鄰近點的每一個毗鄰角。

為了能夠更好地、全面地修補點云數據孔洞，本文將非封閉孔洞轉化為封閉孔洞，對封閉孔洞進行修補。具體的封閉孔洞轉化步驟為：在非封閉孔洞兩邊各自選取4～6個非噪音點作為三次曲線邊界擬合的控制頂點；針對選取的點實施三次非均勻曲線邊界曲線擬合；重新采樣新得到的曲線邊界曲線，并且提取孔洞邊界的新增采樣點；結合非封閉孔洞的邊界點與新增采樣點，將其連接成封閉的孔洞邊界。

在上述執行步驟中，關鍵點是擬合曲線采樣。擬合曲線采樣首先需要計算型值點的參數間距，并且對其進行排序，選取最小值[Δmin]。引入一個[λ]系數，根據相關經驗，可以設置[λ=2]，如果任意兩個相鄰點[Pi，][Pj]之間的參數間距[Δ>λ×Δmin，]則表示相鄰點[Pi，][Pj]之間需要新增采樣點，其中[Δ=ui-uj，][ui]表示點[Pi]關聯的參數值，[uj]表示點[Pj]關聯的參數值，則：

式中：[n]表示相鄰點[Pi，][Pj]之間需要新增的采樣點個數；[u*i]表示新增采樣點的參數值。使用式（1）和式（2）可以計算擬合曲線上[u*i]參數值上的坐標點，進而可以得到相鄰點[Pi，][Pj]之間的新增采樣點。

2 構建孔洞曲面數學模型

2.1 確定孔洞鄰近域的特征面

為了使點云數據孔洞修補的效果更加光滑，本文使用孔洞及關聯的幾何信息確定孔洞區域隱式曲面。孔洞及其附近的幾何信息通常被稱為孔洞鄰近域，鄰近域的厚度可以確定孔洞附近的點屬于孔洞鄰近域。為了能夠更好地實現點云數據孔洞修補效果，本文將孔洞邊界點的一次K?鄰近點統歸于孔洞鄰近域。假設孔洞所在面上到孔洞鄰近域中的各個點[P1P2…Pn]的平方和最小，則該面表示孔洞鄰域的特征面。特征面可以使用空間點[O]和單位法向量[n]來定義，其中[O]表示孔洞鄰近域[P1P2…Pn]的形心：

假設矩陣[MMT]的最小特征值對應的單位特征向量為[t，]根據主成分分析理論可知[t]垂直于特征面。

2.2 計算局部坐標系

3 孔洞填充點計算

3.1 計算重新采樣點的[u]軸、[v]軸的坐標值

將孔洞多邊形變換到孔洞坐標系下并且可以把孔洞多邊形投影到特征面上，投影面上的多邊形稱為投影孔洞多邊形。求出投影孔洞多邊形在局部坐標系下的包圍框，可以得到該投影孔洞在[u]軸、[v]軸上的[umax，][vmax，][umin，][vmin。]使用一組平行于[u]軸、[v]軸的直線與孔洞多邊形求交，平行線間的間距也就是采樣間隔，采樣間隔的[stepsize]可以表示為：

3.2 計算填充點

在隱含曲面函數方程中代入重新采樣點在[u]軸、[v]軸的值，重新采樣點在[s]軸上的值就可以求解得到，按照上述計算方法迭代執行，求解所有的[s]軸坐標值。確定全部重新采樣點在孔洞坐標系中的位置。

4 實驗及結果分析

為了有效驗證本文算法的有效性，與基于徑向基函數[8]的點云數據孔洞修補算法進行比較。實驗過程中，本文使用RIEGLVZ?4000三維激光掃描儀采集的古建筑生成的點云數據，由于光照、古建筑自身缺損，在圖1中的灰色區域產生了一個非封閉孔洞，在其他區域也產生了一些散亂分布的孔洞，如圖1所示。

為了能夠更好地實現古建筑模型重建，本文采用基于移動最小二乘法的點云數據孔洞修補算法，修補的孔洞使用黃色進行覆蓋，算法運行結果如圖2所示。

為了能夠驗證本文算法執行的有效性，與基于徑向基函數的點云數據孔洞修補算法執行的結果進行對比分析。古建筑模型的原始孔洞點數為452個，徑向基函數修補后孔洞點數剩余76個，孔洞修補率為83.2%；本文算法修補后孔洞點數剩余21個，孔洞修補率為95.4%，孔洞修補成功率明顯高于徑向基函數修補算法。另外，本文算法修補耗費時間為6 143.5 ms，遠小于徑向基函數算法，因此，綜合孔洞修補成功率和耗費的修補時間，本文算法具有較好的效果，詳細數據如表1所示。

5 結 語

隨著古籍文物保護技術的發展，三維重建具有不可替代的作用，為了能夠更加精確地恢復古籍文物的容貌，本文提出了一種針對散亂點云數據非封閉孔洞修補的算法，采用三次曲線邊界可以擬合模型邊界點，并且按照一定的步長進行采樣，形成封閉的孔洞邊界，充分利用孔洞邊界特征面及其領域信息，基于移動最小二乘法構建隱式曲面函數，計算孔洞填充點的坐標值，實現孔洞修補點與原始點的平滑過渡，具有較好的修補效果。

參考文獻

[1] 楊永.古建筑數字化保護關鍵技術研究[D].開封：河南大學，2010：1?10.

[2] 李寶瑞.地面三維激光掃描技術在古建筑測繪中的應用研究[D].西安：長安大學，2012：2?7.

[3] 熊友誼，馮志新，陳穎彪，等.利用點云數據進行三維可視化建模技術研究[J].測繪通報，2012，32（5）：20?23.

[4] 陳飛舟，陳志楊，丁展，等.基于徑向基函數的殘缺點云數據修復[J].計算機輔助設計與圖形學學報，2012，18（9）：1414?1419.

[5] 孫殿柱，朱昌志，李延瑞.散亂點云邊界特征快速提取算法[J].山東大學學報（工學版），2012，34（1）：42?48.

[6] 蔣剛.基于SVM和空間投影的點云空洞修補方法[J].計算機工程，2012，35（12）：269?271.

[7] 田建磊，劉旭敏，關永，等.大規模孔洞點云的快速重建算法研究[J].計算機應用研究，2010，27（4）：1544?1546.

[8] 袁紅星，吳少群，朱仁祥，等.散亂點云數據的高階平滑隱式曲面重建[J].計算機應用研究，2013，30（5）：1593?1595.

[9] 晏海平，吳祿慎，陳華偉.基于徑向基函數的散亂點云孔洞修復算法[J].計算機工程與設計，2014，35（4）：1253?1257.