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

劉許　宋陽

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

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

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

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

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

1 非封閉孔洞的提取和檢測(cè)

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

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

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

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

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

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

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

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

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

3 孔洞填充點(diǎn)計(jì)算

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

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

3.2 計(jì)算填充點(diǎn)

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

4 實(shí)驗(yàn)及結(jié)果分析

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

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

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

5 結(jié) 語

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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