一種基于移動最小二乘法的點云數(shù)據(jù)孔洞修補(bǔ)算法研究

劉許　宋陽

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

關(guān)鍵詞： 移動最小二乘法； 點云數(shù)據(jù)； 孔洞曲面； 修補(bǔ)數(shù)據(jù)

中圖分類號： TN98?34 文獻(xiàn)標(biāo)識碼： 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 引 言

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

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

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

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

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

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

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

2 構(gòu)建孔洞曲面數(shù)學(xué)模型

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

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

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

2.2 計算局部坐標(biāo)系

3 孔洞填充點計算

3.1 計算重新采樣點的[u]軸、[v]軸的坐標(biāo)值

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

3.2 計算填充點

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

4 實驗及結(jié)果分析

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

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

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

5 結(jié) 語

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

參考文獻(xiàn)

[1] 楊永.古建筑數(shù)字化保護(hù)關(guān)鍵技術(shù)研究[D].開封：河南大學(xué)，2010：1?10.

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

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

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

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

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

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

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

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