基于特征數據分塊自適應切片的空洞修補

何桂珍

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

基于特征數據分塊自適應切片的空洞修補

何桂珍

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

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

空洞修補；自適應切片；特征數據分塊；散亂點云；虛擬修復

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

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

從以上算法分析可知，都是將空洞看成是一種曲面區域，當空洞所在的區域為幾種曲面區域時或者多個數據分塊區域，上述方法就會失效。本文正是針對以上缺點提出的，所設計的修補方法適用于多種曲面的修補?？朔卣餍畔⑷笔А⑺迯颓娌还忭樀炔蛔?，這些優勢可將該方法很好地應用于修復破損的雕像、雕刻或者復雜的破損零件。

1 算法概述

為了能夠使修補的虛擬點云數據保持特征信息，就要實現自適應切片能夠過特征點，即保持小特征，所以首先必須實現散亂點云特征提取，然后在保留特征的情況下進行自適應切片，具體算法如下：

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

2）基于特征的自適應切片修補空洞：利用米形進行自適應切片，將所有切片通過特征性的區域擬合求交，對過空洞的切片進行曲線擬合，利用權值在曲線上取點，獲得空洞區域填充的虛擬點云。

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

圖1 空洞修補流程圖Fig.1 Flowchart of patching hole

1.1 基于特征的數據分塊

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

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

1.2 基于特征的自適應切片修補空洞

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

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

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

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

4）所有切片通過特征線的區域擬合求交，而不是在該區域通過散亂點求交獲得切片數據點；切片通過平面數據分塊區域時，數據點通過平面求交獲得。

5）對過空洞的切片進行曲線擬合，根據曲線類型定義不同的權值，利用權值在曲線上取點，獲得空洞區域填充的虛擬點云，如圖2所示，為水平方向的切片填充的虛擬點，其他方向的切片也作相同的處理。

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

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

1.3 填充點云的曲面網格重構

為了提高修補效率，有時只需對所修補的虛擬點云進行曲面網格重構，而虛擬修復就是利用填充的虛擬點云重構曲面模型作為一個應用模塊來替換或修補已損壞部分。在完成空洞邊界提取和空洞填充的基礎上，在已有的空洞邊界約束下利用射線法將填充的缺失點云進行逐層地表面重建，以利于表面特征信息的保留。該方法主要思想是利用層剝法理論［11］。

1）計算自適應切片填充的虛擬點云的最小包圍盒，然后利用八叉樹數據結構進行組織，建立拓撲關系。

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

3）判斷該射線是否通過了全局法向映射測試：如果法向射線和八叉樹中一個包含點的葉節點相交，該點沿著測試法向與其他表面片相交，認為該點q沒有通過全局法向映射測試；相反，如果點p沿著法向n的射線和八叉樹相交的節點均為空節點，則認為點p通過測試，如圖3所示。

圖3 全局法向映射測試Fig.3 Global normalmapping test

4）將最外層通過全局法向映射測試的散亂點作為同一投影平面內的二維點，以p為三角中心構建種子三角片，依據逐層生長法通過種子三角片構建三角網格模型。

5）完成最外層表面重建之后，再循環執行以上步驟，直到層層表面重建之后完成填充曲面模型重構完畢。

2 試驗結果

為了驗證本文方法的穩健性和可靠性，作者進行了實驗驗證。實驗曲面包含多種曲面類型，不能用一種簡單曲面進行處理，根據數據分塊的方法，將空洞曲面類型分類，圖中空洞區域有三種不同的曲面類型，分別用不同的顏色進行了表示，對每一同曲面進行修復，最終實現整個空洞修復。實驗結果表明，該修復方法能夠很好地保留不同曲面類型。

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

為了評價本文方法的穩健性和適用性，從所修復曲面模型、修復誤差和修復效率等方面橫向比較該方法的優越性。比較效果如圖5所示。

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

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

不但定性地比較各方法，還要從定量的角度實現精度評價，本實例應用修復后的曲面模型利用點到距離評價方法進行誤差評定，為了從多角度比較各方法的優越性，增加時效性這一參數，計算結果如表1所示。

表1 復雜曲面修復分析結果Tab.1 Analysis of surface repair results

對表中的數據進行歸納分析，可得出以下結論：①對于這類具有復雜多類型的空洞應采用本文方法，修復精度高，最大修復誤差都不超過1mm，平均誤差很??；②文獻方法由于沒有考慮多種曲面類型和特征，所以造成曲面修復誤差較大，最大誤差達到2mm。由于本文方法在修復時考慮了特征信息，所以曲面上的復雜信息能很好地保留。

通過直觀的曲面修復效果、修復誤差、修復效率等三方面的分析歸納，可得出以下結論：本文方法適應性強，能夠保留復雜曲面的特征信息，在修復雕像、古建筑等復雜物體時，優勢較大。

3 結束語

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

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

[2]龔志遠,付偉.利用三坐標測量"點云"的曲面反求設計[J].華東交通大學學報,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]邱澤陽.離散數據中的孔洞修補[J].工程圖學學報,2004(4):85-89.

[7]蔡利棟.關于KH和KJ符號圖的一些注解[J].中國圖像圖形學報,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]范德營,蔣先剛,丘赟立,等.車載紅外視頻圖像快速彩色化技術研究[J].華東交通大學學報,2013,30(2):71-77.

[10]程效軍,何桂珍.適用于多值曲面修復的空洞邊界提取方法[J].測繪學報,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

江西省青年科學基金項目（20142BAB217032）

何桂珍（1983—），女，講師，博士，研究方向為近景攝影測量與三維建模。

1005-0523（2014）04-0095-05