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

孟慶年，鄭德華，張崇軍

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

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

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

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

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

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

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

1 孔洞邊界的檢測(cè)提取

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

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

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

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

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

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

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

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

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

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

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

通過對(duì)邊界邊夾角的遍歷，使空洞區(qū)域逐步填充，對(duì)新生成的點(diǎn)進(jìn)行保存，從而達(dá)到孔洞填充的目的?？锥刺畛渫戤吅?，還需對(duì)最后生成的三角片進(jìn)行合法性檢測(cè)即可得到修補(bǔ)的點(diǎn)云數(shù)據(jù)。

3 基于切片的點(diǎn)云孔洞修補(bǔ)方法研究

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

3.1 切片寬度的確定

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

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

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

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

2）基于鄰近點(diǎn)搜索的密度法[8]。

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

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

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

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

1）切片劃分。以單向切片為例進(jìn)行研究，首先確定切片方向。以X方向?yàn)橹鞣较驅(qū)c(diǎn)云進(jìn)行切片處理，則可以得到間距一定的多條切片。

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

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

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

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

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

可以表示為：

總體最小二乘表達(dá)式為：

本文使用SVD奇異值分解方法對(duì)總體最小二乘進(jìn)行求解。

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

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

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

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

圖1 切片投影擬合圖

4 實(shí)驗(yàn)案例

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

圖2 三維激光掃描點(diǎn)云及孔洞附近點(diǎn)云示意圖

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

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

圖4 三角剖分方法修補(bǔ)示意圖

圖5 切片方法修補(bǔ)示意圖

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

表1 不同孔洞修補(bǔ)方法的修補(bǔ)效果對(duì)比

5 結(jié) 語

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P207.2

B文章編號(hào)：1672-4623（2017）06-0047-04

10.3969/j.issn.1672-4623.2017.06.014

2015-07-16。

孟慶年，碩士研究生，研究方向?yàn)闇y(cè)量平差與數(shù)據(jù)處理。