孟慶年，鄭德華，張崇軍

（1.河海大學(xué) 地球科學(xué)與工程學(xué)院，江蘇 南京 210098 ）

基于總體最小二乘切片的孔洞修補方法研究

孟慶年1，鄭德華1，張崇軍1

（1.河海大學(xué) 地球科學(xué)與工程學(xué)院，江蘇 南京 210098 ）

對點云孔洞的修補進行研究是點云數(shù)據(jù)處理的重要部分。對常用的孔洞修補方法進行了介紹，并詳細(xì)介紹了基于切片的孔洞修補方法。通過引入總體最小二乘方法對基于切片的孔洞修補方法進行改進，使修補的精度得到提高。通過對比常用的修補方法在復(fù)雜孔洞修補中的應(yīng)用，基于總體最小二乘的切片方法的修補效果更優(yōu)。

孔洞修補；復(fù)雜孔洞；切片方法；總體最小二乘方法

近些年來，隨著三維激光掃描技術(shù)及其相關(guān)技術(shù)的快速發(fā)展，三維激光掃描技術(shù)已廣泛應(yīng)用于各個領(lǐng)域[1]。但在使用三維激光掃描儀時，往往會因為掃描對象的自身部位遮擋、外物遮擋或者點云數(shù)據(jù)預(yù)處理等原因造成數(shù)據(jù)缺失，從而在掃描點云上形成孔洞[2]。而這些數(shù)據(jù)缺失的存在不僅會對建模的質(zhì)量造成嚴(yán)重影響[3]，而且對于模型的有限元分析以及模型快速制造等后續(xù)操作也有很大的影響[4]。因此，對于點云的孔洞修補方法進行研究是十分必要的。目前，常用的是基于網(wǎng)格的孔洞修補方法，對于一般的孔洞修復(fù)效果良好，但是對于孔洞區(qū)域含有多種曲面的情況，往往修復(fù)效果不佳或失效。而基于切片的孔洞修補方法不僅能夠修復(fù)常見的簡單孔洞，還能夠修復(fù)各種復(fù)雜的孔洞。目前對基于切片的修補方法研究較少，而且都是基于簡單的最小二乘方法。本文通過引入總體最小二乘方法對系數(shù)矩陣和觀測向量進行修正，從而提高切片方法擬合修補的精度[5]。

1 孔洞邊界的檢測提取

根據(jù)孔洞的形狀，大致可將孔洞分為簡單孔洞、復(fù)雜孔洞以及環(huán)形孔洞。本文以簡單孔洞為例，對孔洞的邊界進行提取?？锥吹倪吔鐧z測提取大致包括K鄰點數(shù)據(jù)的拓?fù)渌阉鳌Ⅻc云數(shù)據(jù)的法矢計算、邊界點的確定以及內(nèi)邊界提取[6]。

1）K鄰點數(shù)據(jù)的拓?fù)渌阉?。常用的K鄰點搜索方法有空間格網(wǎng)方法、K-d tree方法以及八叉樹等方法，本文使用空間柵格方法對點云數(shù)據(jù)建立拓?fù)潢P(guān)系，通過計算以及調(diào)整求得空間格網(wǎng)的最終邊長，通過劃分建立網(wǎng)格之間的拓?fù)潢P(guān)系。

2）點云數(shù)據(jù)的法矢計算。根據(jù)已經(jīng)確定好的數(shù)據(jù)點的K鄰域構(gòu)成一個平面，使用最小二乘方法進行擬合，這個平面的法矢即為數(shù)據(jù)點的法矢，對法矢的方向進行檢測，確保指向一致。

3）邊界點的確定以及內(nèi)邊界提取。將數(shù)據(jù)點的K個鄰點按計算出的法矢投影到數(shù)據(jù)點的平面上，計算數(shù)據(jù)點與鄰點連線之間的夾角，根據(jù)夾角的最大值判斷是否為邊界點。將邊界點進行連接，通過一定的判別準(zhǔn)則，將內(nèi)邊界提取出來。

2 基于三角剖分的孔洞修補方法研究

孔洞的修補方法大致可分為3類：基于體數(shù)據(jù)的孔洞修補方法、基于網(wǎng)格的孔洞修補方法以及基于切片的孔洞修補方法。目前最為常用的是基于網(wǎng)格的孔洞修補方法，本文以三角剖分方法為例，詳細(xì)介紹修補的過程。

以得到的孔洞邊界為基礎(chǔ)，對孔洞區(qū)域進行修補，三角剖分方法的主要思想是局部擴張并填充，假設(shè)兩邊界邊的夾角為α，填充過程如下[7]：

1）當(dāng)邊界邊夾角α≤0.5π時，將邊界端點進行連接形成一條新的邊界邊，生成一個新的三角面片。

2）當(dāng)0.5π＜α≤ π時，平分邊界邊夾角α增加一個端點，記錄新生成的端點，形成兩條新的邊界邊，并生成兩個三角面片。

3）當(dāng)π＜α≤1.5π時，三等分邊界邊夾角α新增兩個端點，記錄新生成的端點，形成三條新的邊界邊，并生成3個三角面片。

4）當(dāng)1.5π＜α≤2π時，四等分邊界邊夾角α新增3個端點，記錄新生成的端點，形成4條新的邊界邊，生成4個三角面片。

通過對邊界邊夾角的遍歷，使空洞區(qū)域逐步填充，對新生成的點進行保存，從而達到孔洞填充的目的。孔洞填充完畢后，還需對最后生成的三角片進行合法性檢測即可得到修補的點云數(shù)據(jù)。

3 基于切片的點云孔洞修補方法研究

基于切片的修補方法不僅能夠修補普通的孔洞，而且還能夠修補各種復(fù)雜的孔洞，尤其是孔洞區(qū)域含有多種曲面的復(fù)雜孔洞。基于切片的修補方法主要包含兩個步驟：切片寬度的確定和切片的投影擬合。

3.1 切片寬度的確定

切片寬度的確定常用的方法是密度法，本文介紹兩種密度法。

1）基于空間格網(wǎng)劃分的密度法。

式中，Vt為所有的空間網(wǎng)格的個數(shù)；Ve為所有空的空間網(wǎng)格的個數(shù)；n為鄰近點的個數(shù)；N為所有的數(shù)據(jù)點個數(shù)。

式中，δ為切片寬度；ρ1為柵格法求得的點云密度；k1一般取值4～8。

2）基于鄰近點搜索的密度法[8]。

式中，n為點的個數(shù)；m為搜索的最鄰近點個數(shù)；D為數(shù)據(jù)點到m個鄰近點距離之和。

式中，δ為切片寬度；ρ2為最鄰近點法求得的點云密度；k2一般取值1～4。

3.2 基于最小二乘的切片投影擬合方法

根據(jù)計算所得的切片寬度，首先需要對切片進行劃分，然后對切片進行投影擬合。

1）切片劃分。以單向切片為例進行研究，首先確定切片方向。以X方向為主方向?qū)c云進行切片處理，則可以得到間距一定的多條切片。

2）切片投影擬合。對獲得的點云切片逐條處理，首先對切片進行投影，可以得到二維的散亂點。對二維的散亂點進行擬合，目前常用的方法是最小二乘擬合方法。設(shè)曲線的函數(shù)為：

設(shè)點云的個數(shù)為n，φ0(x)=1，φ1(x)=x，φ2(x)=x2，令每個點的權(quán)重ωi相同，且都為1。由式（6）可以求解出a、b、c，從而得到擬合函數(shù)。

3.3 基于總體最小二乘的切片投影擬合方法

在數(shù)據(jù)采集過程中，假設(shè)每個點的采集誤差相等，并且每個點的三個維度的坐標(biāo)也是等誤差的，數(shù)據(jù)點是必然含有誤差的。在進行數(shù)據(jù)處理的過程中，對切片進行擬合時，因為其系數(shù)矩陣和觀測向量是以原始數(shù)據(jù)為依據(jù)的，所以必然含有誤差，如果直接使用將會對擬合修補結(jié)果造成影響。

總體最小二乘的基本思想是在觀測方程中，不僅觀測向量中存在誤差，同時系數(shù)矩陣中也含有誤差。所以，由式（6）中的觀測方程[9]：

可以表示為：

總體最小二乘表達式為：

本文使用SVD奇異值分解方法對總體最小二乘進行求解。

1）對構(gòu)造的增廣矩陣[A Y]進行分解得：

2）判斷V22是否為奇異矩陣，若V22非奇異，則：

3）總體最小二乘方法計算得到的殘差矩陣為：

對于切片投影的擬合圖如圖1，通過對系數(shù)矩陣誤差的考慮，基于總體最小二乘的擬合方法的效果明顯優(yōu)于最小二乘方法的擬合效果。

圖1 切片投影擬合圖

4 實驗案例

使用Trimble GX三維激光掃描儀對某石質(zhì)雕塑進行掃描，得到三維掃描數(shù)據(jù)在表面起伏復(fù)雜部位人為制作孔洞（如圖2），方便后續(xù)的實驗對比。

圖2 三維激光掃描點云及孔洞附近點云示意圖

首先，對孔洞的內(nèi)邊界進行提取得到內(nèi)邊界（如圖3）。使用三角剖分的方法進行孔洞修補（如圖4），從修補的結(jié)果可以看出，修補的孔洞部分的點位分布不均勻且與周邊數(shù)據(jù)的連接不光滑。使用切片方法進行孔洞修補（如圖5），從修補的結(jié)果可以看出，修補的孔洞部分的點位分布均勻且與周邊數(shù)據(jù)的連接較為光滑。

圖3 孔洞內(nèi)邊界示意圖

圖4 三角剖分方法修補示意圖

圖5 切片方法修補示意圖

對孔洞的點云數(shù)據(jù)分別使用基于三角剖分的孔洞修補方法、基于神經(jīng)網(wǎng)絡(luò)的孔洞修補方法、基于最小二乘切片的孔洞修補方法以及基于總體最小二乘切片的孔洞修補方法對點云孔洞數(shù)據(jù)進行修補，修補結(jié)果如表1。從修補的效果上看，基于切片的修補方法的效果明顯優(yōu)于三角剖分方法和神經(jīng)網(wǎng)絡(luò)方法，而基于總體最小二乘的切片方法考慮到系數(shù)矩陣的誤差，使得擬合的效果更優(yōu)。

表1 不同孔洞修補方法的修補效果對比

5 結(jié) 語

傳統(tǒng)的修補方法對于復(fù)雜度較高的多值曲面的孔洞修補往往是失效的或修補效果不理想，本文詳細(xì)地介紹了基于切片的孔洞修補方法，并引入總體最小二乘方法對切片的擬合修補進行改進，相對于傳統(tǒng)算法具有如下優(yōu)點：

1）切片修補方法不僅能夠很好地修補簡單孔洞，而且還適用于復(fù)雜度較高的多值曲面孔洞，生成的修補數(shù)據(jù)分布均勻且與邊界數(shù)據(jù)平滑過渡。

2）引入總體最小二乘方法對切片的擬合修補進行改進，使得孔洞修補的效果更優(yōu)、精度更高。

3）算法相對簡單，易于實現(xiàn)，適應(yīng)于大規(guī)模數(shù)據(jù)處理。

綜合以上優(yōu)點，基于總體最小二乘切片的孔洞修補方法具有較高的實際應(yīng)用價值。

[1] 習(xí)曉環(huán),駱社周,王方建,等．地面三維激光掃描系統(tǒng)現(xiàn)狀及發(fā)展評述[J]．地理空間信息,2012,10(6)：13-15

[2] 陸旻豐,吳杭彬,劉春,等．地面三維激光掃描數(shù)據(jù)缺失分類及成因分析[J]．遙感信息,2013,28(6)：82-86

[3] 顧園園．散亂點云孔洞修補技術(shù)的研究與實現(xiàn)[D]．蘇州大學(xué), 2008

[4] 何桂珍．基于特征數(shù)據(jù)分塊自適應(yīng)切片的空洞修補[J]．華東交通大學(xué)學(xué)報,2014,31(4)：95-99

[5] 袁豹,岳東杰．關(guān)于總體最小二乘方法適應(yīng)性實驗研究[J]．測繪工程,2012,21(6)：22-26

[6] 禚永盛．散亂點云模型孔洞邊界提取算法的研究與實現(xiàn)[D]．南京師范大學(xué),2012

[7] 張麗艷,周儒榮,周來水．三角網(wǎng)格模型孔洞修補算法研究[J]．應(yīng)用科學(xué)報,2002,20(3)：221-224

[8] 張?zhí)鹛铮诜指铧c云的NURBS曲面三維重構(gòu)方法研究[D]．北京建筑大學(xué),2013

[9] 孟慶年,鄭德華,曾廣建．基于補償最小二乘的AR(p)模型在變形監(jiān)測中的應(yīng)用[J]．勘察科學(xué)技術(shù),2015(2)：46-48

P207.2

B文章編號：1672-4623（2017）06-0047-04

10.3969/j.issn.1672-4623.2017.06.014

2015-07-16。

孟慶年，碩士研究生，研究方向為測量平差與數(shù)據(jù)處理。