基于特征數(shù)據(jù)分塊自適應(yīng)切片的空洞修補(bǔ)

何桂珍

（華東交通大學(xué)土木建筑學(xué)院，江西南昌330013）

基于特征數(shù)據(jù)分塊自適應(yīng)切片的空洞修補(bǔ)

何桂珍

（華東交通大學(xué)土木建筑學(xué)院，江西南昌330013）

針對(duì)常用的空洞修補(bǔ)方法在修復(fù)具有多種曲面類型的空洞時(shí)失效和所修復(fù)的曲面不光順等缺點(diǎn)，提出基于特征數(shù)據(jù)分塊自適應(yīng)切片的空洞修補(bǔ)。首先，在考慮特征信息的情況下基于聚類對(duì)散亂點(diǎn)云進(jìn)行分塊；然后利用特征進(jìn)行自適應(yīng)切片，獲得曲線并進(jìn)行擬合；最后，在線上取點(diǎn)填充缺失的點(diǎn)云，最終對(duì)完整的點(diǎn)云模型進(jìn)行曲面重構(gòu)建立實(shí)體模型。試驗(yàn)結(jié)果表明，采用自適應(yīng)切片法修補(bǔ)空洞能夠保留特征，所填充的點(diǎn)云數(shù)據(jù)精度較高，能夠滿足后續(xù)建模的需要。此外對(duì)該方法填充的點(diǎn)云進(jìn)行了曲面重構(gòu)及光順，結(jié)果令人滿意。

空洞修補(bǔ)；自適應(yīng)切片；特征數(shù)據(jù)分塊；散亂點(diǎn)云；虛擬修復(fù)

研究三維激光掃描技術(shù)逐步成為測(cè)繪界的一個(gè)熱點(diǎn)，利用三維激光掃描儀采集數(shù)據(jù)過(guò)程中，由于環(huán)境影響或物件本身的損壞，使獲得的樣件表面數(shù)據(jù)存在一些不希望有的“空洞”［1］。這些空洞影響模型的重建及零件加工等后續(xù)處理，因此必須對(duì)這些數(shù)據(jù)空洞進(jìn)行修補(bǔ)?？斩葱扪a(bǔ)在航空、航天、船舶、汽車和模具等制造業(yè)得到了廣泛的應(yīng)用，也可應(yīng)用于修復(fù)破損的藝術(shù)品或者被損零件［2］，例如修復(fù)破損的雕像、雕刻；修復(fù)由于常年使用造成的船舶破損；修繕古建筑等。此時(shí)并不需要對(duì)整個(gè)原型進(jìn)行復(fù)制，而只需借助于逆向工程技術(shù)提取需要修復(fù)的零部件以實(shí)現(xiàn)缺損空洞的定位和逆向建模，仿真缺損物體的修理工藝，實(shí)現(xiàn)修復(fù)技術(shù)的現(xiàn)代化。在研究修復(fù)過(guò)程中，需要對(duì)三維激光掃描測(cè)量技術(shù)獲取的點(diǎn)云數(shù)據(jù)進(jìn)行空洞修復(fù)研究。

目前，比較常用的空洞修補(bǔ)方法是根據(jù)空洞周圍的局部離散點(diǎn)來(lái)建立一張曲面片，然后采用面上取點(diǎn)的策略補(bǔ)出空洞部位所缺的點(diǎn)［3-5］。國(guó)內(nèi)代表性的研究者邱澤陽(yáng)提出的空洞識(shí)別算法首先通過(guò)人工交互的手段在空洞附近提取不共線的3個(gè)點(diǎn)，構(gòu)成一個(gè)三角形，然后將局部測(cè)試點(diǎn)向該三角片所在平面投影，構(gòu)造初始三角Bezier曲面片，并進(jìn)行迭代求解，最后在滿足條件的三角曲面片中取點(diǎn)，完成空洞修補(bǔ)；通過(guò)確定空洞鄰近域的特征面和以特征面為基礎(chǔ)的局部坐標(biāo)系后，建立基于移動(dòng)最小二乘法的隱式曲面，將空洞多邊形變換到空洞局部坐標(biāo)系下，并將空洞多邊形投影到特征面上，然后對(duì)投影空洞多邊形重新采樣，最后將重新采樣點(diǎn)的u，v坐標(biāo)值代入計(jì)算出的隱式曲面函數(shù)方程，得到空洞填充點(diǎn)［6］。

從以上算法分析可知，都是將空洞看成是一種曲面區(qū)域，當(dāng)空洞所在的區(qū)域?yàn)閹追N曲面區(qū)域時(shí)或者多個(gè)數(shù)據(jù)分塊區(qū)域，上述方法就會(huì)失效。本文正是針對(duì)以上缺點(diǎn)提出的，所設(shè)計(jì)的修補(bǔ)方法適用于多種曲面的修補(bǔ)?？朔卣餍畔⑷笔?、所修復(fù)曲面不光順等不足，這些優(yōu)勢(shì)可將該方法很好地應(yīng)用于修復(fù)破損的雕像、雕刻或者復(fù)雜的破損零件。

1 算法概述

為了能夠使修補(bǔ)的虛擬點(diǎn)云數(shù)據(jù)保持特征信息，就要實(shí)現(xiàn)自適應(yīng)切片能夠過(guò)特征點(diǎn)，即保持小特征，所以首先必須實(shí)現(xiàn)散亂點(diǎn)云特征提取，然后在保留特征的情況下進(jìn)行自適應(yīng)切片，具體算法如下：

1）基于特征的數(shù)據(jù)分塊：首先用基于平均曲率的特征權(quán)值方法提取特征點(diǎn)，并用最小生成樹(shù)連接成特征線［7］，然后通過(guò)聚類方法依據(jù)8種基本曲面類型將散亂數(shù)據(jù)點(diǎn)進(jìn)行粗略劃分，在所求的特征線約束下對(duì)曲面進(jìn)行精確分塊。

2）基于特征的自適應(yīng)切片修補(bǔ)空洞：利用米形進(jìn)行自適應(yīng)切片，將所有切片通過(guò)特征性的區(qū)域擬合求交，對(duì)過(guò)空洞的切片進(jìn)行曲線擬合，利用權(quán)值在曲線上取點(diǎn)，獲得空洞區(qū)域填充的虛擬點(diǎn)云。

3）填充點(diǎn)云的曲面網(wǎng)格重構(gòu)：在已有的空洞邊界約束下利用射線法將填充的缺失點(diǎn)云進(jìn)行逐層的表面重建，以利于表面特征信息的保留。具體修補(bǔ)流程如圖1所示。

圖1 空洞修補(bǔ)流程圖Fig.1 Flowchart of patching hole

1.1 基于特征的數(shù)據(jù)分塊

特征點(diǎn)提取階段的主要任務(wù)是為點(diǎn)云中的每個(gè)采樣點(diǎn)設(shè)置一個(gè)權(quán)值，使之與該點(diǎn)隸屬于特征點(diǎn)的可能性大小成正比關(guān)系，稱為特征權(quán)重。本文采用基于平均曲率的特征權(quán)值［8］。本文研究對(duì)象為散亂點(diǎn)云，采用局部曲面擬合的方法估算曲率，曲率越大，表示曲線或者曲面的彎曲程度越大。首先用該方法提取特征點(diǎn)，并用最小生成樹(shù)連接成特征線，然后通過(guò)聚類方法依據(jù)8種基本曲面類型將散亂數(shù)據(jù)點(diǎn)進(jìn)行粗略劃分，在所求的特征線約束下對(duì)曲面進(jìn)行精確分塊。

利用計(jì)算出的高斯曲率和平均曲率根據(jù)Besl［9］提出的8種基本曲面類型將曲面初步分塊。如果把相同類型的點(diǎn)組成一個(gè)曲面，就可得到8種基本曲面，任意復(fù)雜曲面可以由這8種基本曲面塊組成。任意兩曲面的接觸邊界散亂數(shù)據(jù)點(diǎn)，利用最小生成樹(shù)連接形成特征線，在特征線的約束下，從一“種子點(diǎn)”開(kāi)始，該點(diǎn)的類型就是塊的類型，進(jìn)行“區(qū)域生長(zhǎng)”，找出具有相似特征的一組點(diǎn)構(gòu)成一曲面片，直至周圍鄰域沒(méi)有特征一致的點(diǎn)，且特征點(diǎn)的個(gè)數(shù)大于某一閾值，否則認(rèn)為該特征點(diǎn)為噪音點(diǎn)而刪除，獲得精確曲面分塊。

1.2 基于特征的自適應(yīng)切片修補(bǔ)空洞

點(diǎn)云切片的實(shí)質(zhì)是用某平面和點(diǎn)云進(jìn)行求交得到的切片曲線，在實(shí)際應(yīng)用中，由于點(diǎn)云密度總是有限的，不可能構(gòu)造一條完整的截面曲線，所以可通過(guò)給定一個(gè)合適的帶寬，這一帶寬稱為切片厚度δ，δ是一個(gè)比較難以確定的參數(shù)，以往研究者都使用了同一個(gè)切片厚度，但由于切片層有一定厚度，所以就會(huì)出現(xiàn)切片層范圍內(nèi)小特征遺失現(xiàn)象。針對(duì)此類問(wèn)題，本文提出了一種基于特征的自適應(yīng)切片方法，具體實(shí)現(xiàn)步驟如下：

1）隨機(jī)計(jì)算n個(gè)點(diǎn)的k近鄰點(diǎn)，n個(gè)點(diǎn)與其近鄰點(diǎn)的平均距離表示點(diǎn)云密度，將密度值乘以層厚系數(shù)得切片厚度，通過(guò)鄰域數(shù)據(jù)點(diǎn)配對(duì)連線并與切片求交獲取切片數(shù)據(jù)點(diǎn)。該方法依據(jù)點(diǎn)云密度確定層厚，利用相同切片層厚進(jìn)行初切片。

2）根據(jù)所提取的物體外邊界線［10］，計(jì)算關(guān)聯(lián)邊界點(diǎn)的數(shù)據(jù)塊Ft（t=0，1，2，…，k-1），擬合求特征交線，利用通過(guò)特征點(diǎn)位置增加切片，當(dāng)確定切片平面位置時(shí)，需要自適應(yīng)的根據(jù)與切片相垂直的散亂點(diǎn)云平面的曲率變化情況確定切片厚度。

3）計(jì)算散亂點(diǎn)云的質(zhì)心，然后過(guò)質(zhì)心做與切片平面相垂直的平面（設(shè)為m個(gè)，每個(gè)平面的旋轉(zhuǎn)角360/m），則利用前述切片平面技術(shù)，獲得m條截面曲線。根據(jù)曲率值變化，自適應(yīng)地確定切片層厚度；依據(jù)橫向水平層的點(diǎn)形成的曲線曲率變化程度給數(shù)據(jù)點(diǎn)分別賦予不同權(quán)值，然后對(duì)橫向水平層依次旋轉(zhuǎn)45度角，形成米字形切片層。

4）所有切片通過(guò)特征線的區(qū)域擬合求交，而不是在該區(qū)域通過(guò)散亂點(diǎn)求交獲得切片數(shù)據(jù)點(diǎn)；切片通過(guò)平面數(shù)據(jù)分塊區(qū)域時(shí)，數(shù)據(jù)點(diǎn)通過(guò)平面求交獲得。

5）對(duì)過(guò)空洞的切片進(jìn)行曲線擬合，根據(jù)曲線類型定義不同的權(quán)值，利用權(quán)值在曲線上取點(diǎn)，獲得空洞區(qū)域填充的虛擬點(diǎn)云，如圖2所示，為水平方向的切片填充的虛擬點(diǎn)，其他方向的切片也作相同的處理。

圖2 基于自適應(yīng)切片填充空洞Fig.2 Patching hole based on adaptive slicing

用本方法填充的虛擬點(diǎn)云，不僅與周圍點(diǎn)之間光滑連續(xù)，同時(shí)，考慮空洞包含有不同曲面類型，填充的點(diǎn)云能夠保持特征信息且分布也比較均勻，非常適合后續(xù)曲面構(gòu)造的需要。

1.3 填充點(diǎn)云的曲面網(wǎng)格重構(gòu)

為了提高修補(bǔ)效率，有時(shí)只需對(duì)所修補(bǔ)的虛擬點(diǎn)云進(jìn)行曲面網(wǎng)格重構(gòu)，而虛擬修復(fù)就是利用填充的虛擬點(diǎn)云重構(gòu)曲面模型作為一個(gè)應(yīng)用模塊來(lái)替換或修補(bǔ)已損壞部分。在完成空洞邊界提取和空洞填充的基礎(chǔ)上，在已有的空洞邊界約束下利用射線法將填充的缺失點(diǎn)云進(jìn)行逐層地表面重建，以利于表面特征信息的保留。該方法主要思想是利用層剝法理論［11］。

1）計(jì)算自適應(yīng)切片填充的虛擬點(diǎn)云的最小包圍盒，然后利用八叉樹(shù)數(shù)據(jù)結(jié)構(gòu)進(jìn)行組織，建立拓?fù)潢P(guān)系。

2）對(duì)于包圍盒中的任一輸入點(diǎn)p，根據(jù)上節(jié)介紹的方法計(jì)算該點(diǎn)的k近鄰域并估計(jì)其法矢方向n，然后沿著n或者n的反方向確定一條射線。

3）判斷該射線是否通過(guò)了全局法向映射測(cè)試：如果法向射線和八叉樹(shù)中一個(gè)包含點(diǎn)的葉節(jié)點(diǎn)相交，該點(diǎn)沿著測(cè)試法向與其他表面片相交，認(rèn)為該點(diǎn)q沒(méi)有通過(guò)全局法向映射測(cè)試；相反，如果點(diǎn)p沿著法向n的射線和八叉樹(shù)相交的節(jié)點(diǎn)均為空節(jié)點(diǎn)，則認(rèn)為點(diǎn)p通過(guò)測(cè)試，如圖3所示。

圖3 全局法向映射測(cè)試Fig.3 Global normalmapping test

4）將最外層通過(guò)全局法向映射測(cè)試的散亂點(diǎn)作為同一投影平面內(nèi)的二維點(diǎn)，以p為三角中心構(gòu)建種子三角片，依據(jù)逐層生長(zhǎng)法通過(guò)種子三角片構(gòu)建三角網(wǎng)格模型。

5）完成最外層表面重建之后，再循環(huán)執(zhí)行以上步驟，直到層層表面重建之后完成填充曲面模型重構(gòu)完畢。

2 試驗(yàn)結(jié)果

為了驗(yàn)證本文方法的穩(wěn)健性和可靠性，作者進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)曲面包含多種曲面類型，不能用一種簡(jiǎn)單曲面進(jìn)行處理，根據(jù)數(shù)據(jù)分塊的方法，將空洞曲面類型分類，圖中空洞區(qū)域有三種不同的曲面類型，分別用不同的顏色進(jìn)行了表示，對(duì)每一同曲面進(jìn)行修復(fù)，最終實(shí)現(xiàn)整個(gè)空洞修復(fù)。實(shí)驗(yàn)結(jié)果表明，該修復(fù)方法能夠很好地保留不同曲面類型。

圖4 空洞區(qū)域具有多種曲面類型的曲面修復(fù)Fig.4 Surface repair for hole area with a variety of surface types

為了評(píng)價(jià)本文方法的穩(wěn)健性和適用性，從所修復(fù)曲面模型、修復(fù)誤差和修復(fù)效率等方面橫向比較該方法的優(yōu)越性。比較效果如圖5所示。

圖5 兩種方法修復(fù)曲面效果圖Fig.5 Repaired surface by two ways

從圖比較可知，本文提出的方法可以很好地保留模型的特征信息，文獻(xiàn)［6］對(duì)于這種復(fù)雜曲面只能識(shí)別出存在一條空洞邊界線，進(jìn)行曲面修復(fù)后反面模型仍然存在空洞，而且模型的特征信息沒(méi)有很好地被保留，所以從效果圖可以直觀地判斷出本文方法更優(yōu)越。

不但定性地比較各方法，還要從定量的角度實(shí)現(xiàn)精度評(píng)價(jià)，本實(shí)例應(yīng)用修復(fù)后的曲面模型利用點(diǎn)到距離評(píng)價(jià)方法進(jìn)行誤差評(píng)定，為了從多角度比較各方法的優(yōu)越性，增加時(shí)效性這一參數(shù)，計(jì)算結(jié)果如表1所示。

表1 復(fù)雜曲面修復(fù)分析結(jié)果Tab.1 Analysis of surface repair results

對(duì)表中的數(shù)據(jù)進(jìn)行歸納分析，可得出以下結(jié)論：①對(duì)于這類具有復(fù)雜多類型的空洞應(yīng)采用本文方法，修復(fù)精度高，最大修復(fù)誤差都不超過(guò)1mm，平均誤差很?。虎谖墨I(xiàn)方法由于沒(méi)有考慮多種曲面類型和特征，所以造成曲面修復(fù)誤差較大，最大誤差達(dá)到2mm。由于本文方法在修復(fù)時(shí)考慮了特征信息，所以曲面上的復(fù)雜信息能很好地保留。

通過(guò)直觀的曲面修復(fù)效果、修復(fù)誤差、修復(fù)效率等三方面的分析歸納，可得出以下結(jié)論：本文方法適應(yīng)性強(qiáng)，能夠保留復(fù)雜曲面的特征信息，在修復(fù)雕像、古建筑等復(fù)雜物體時(shí)，優(yōu)勢(shì)較大。

3 結(jié)束語(yǔ)

針對(duì)曲面虛擬修復(fù)中的空洞修補(bǔ)問(wèn)題，提出了一種保留特征的空洞修補(bǔ)方法，該方法通過(guò)計(jì)算曲數(shù)據(jù)進(jìn)行粗略分塊，在所求的特征線約束下對(duì)數(shù)據(jù)進(jìn)行精細(xì)分塊；基于特征數(shù)據(jù)塊利用米形進(jìn)行自適應(yīng)切片，獲得切片曲線并進(jìn)行擬合，在線上取點(diǎn)填充缺失的點(diǎn)云，最終對(duì)完整的點(diǎn)云模型進(jìn)行曲面重構(gòu)建立實(shí)體模型。通過(guò)實(shí)驗(yàn)驗(yàn)證，本文提出的方法有較強(qiáng)的穩(wěn)健性和適應(yīng)性，不僅具有特征保留作用，而且不需要求“單類型”曲面，可很好地避免多種曲面類型修復(fù)不能保留特征和光順等問(wèn)題，能適應(yīng)多種復(fù)雜曲面。

[1]姜振宇.逆向工程中點(diǎn)云孔洞填充算法的研究[J].機(jī)械制造,2005(43):43-45.

[2]龔志遠(yuǎn),付偉.利用三坐標(biāo)測(cè)量"點(diǎn)云"的曲面反求設(shè)計(jì)[J].華東交通大學(xué)學(xué)報(bào),2004,21(5):116-118.

[3]PAVEL C,BERT J.Filling holes in point clouds[C]//Lecture Notes in Computer Science,2003:196-212.

[4]LIEPA P.Filling holes inmeshes[C]//Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 2003:200-205.

[5]DAVIS J,MARSCHNE S R,GARR M,et al.Filling holes in complex surfaces using volumetric diffusion[C]//First International Symposium on 3D Data Processing,2002:428-861.

[6]邱澤陽(yáng).離散數(shù)據(jù)中的孔洞修補(bǔ)[J].工程圖學(xué)學(xué)報(bào),2004(4):85-89.

[7]蔡利棟.關(guān)于KH和KJ符號(hào)圖的一些注解[J].中國(guó)圖像圖形學(xué)報(bào),1998,7(3):562-564.

[8]BESL P J,JAIN R C.Segmentation through variable-order surface fitting[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,1988,10(2):167-192.

[9]范德?tīng)I(yíng),蔣先剛,丘赟立,等.車載紅外視頻圖像快速彩色化技術(shù)研究[J].華東交通大學(xué)學(xué)報(bào),2013,30(2):71-77.

[10]程效軍,何桂珍.適用于多值曲面修復(fù)的空洞邊界提取方法[J].測(cè)繪學(xué)報(bào),2012(4):85-89.

[11]LIM C W,TAN T S.Surface reconstruction by layer peeling[J].The Visual Computer,2006,229(11):593-603.

Hole Patching of Adaptive Slicing Based on Feature-data Segmentation

He Guizhen
(School of Civil Engineering and Architecture,East China Jiaotong University,Nanchang 330013,China)

Since common hole patchingmethods have some shortcomings,such as failure in repairing a variety of surfaces or repaired surfaces being not smooth,a new hole patchingmethod is presented which uses adaptive slic?ing based on the feature data segmentation.Firstly,scattered point cloud is segmented based on cluster under the consideration of feature information;then adaptive slicing generates curves to be fitted with the features.Finally, virtual points are chosen from the curves to fill themissing parts of the point cloud.The surface of the complete point cloud is reconstructed to establish a physicalmodel.Test results show that the adaptive slicingmethod can keep patching hole feature and have high accuracy of filled point cloud,which canmeet the needs of the subse?quentmodeling.In addition,the results of surface reconstruction and smoothing obtained are satisfactory.

hole-patching;adaptive slicing;feature data segmentation;scattered point cloud;virtual repair

P234

A

2014-04-03

江西省青年科學(xué)基金項(xiàng)目（20142BAB217032）

何桂珍（1983—），女，講師，博士，研究方向?yàn)榻皵z影測(cè)量與三維建模。

1005-0523（2014）04-0095-05