王欽瑞 張應(yīng)中 羅曉芳

(大連理工大學(xué)機械工程學(xué)院 遼寧 大連 116024)

綜合平均曲率與網(wǎng)格邊的特征線提取方法

王欽瑞 張應(yīng)中 羅曉芳

(大連理工大學(xué)機械工程學(xué)院 遼寧 大連 116024)

隨著數(shù)字幾何獲取技術(shù)的發(fā)展，大量的復(fù)雜形體采用網(wǎng)格模型表示。而網(wǎng)格模型的特征線或特征邊緣的識別和提取是后續(xù)開展幾何和特征識別的基礎(chǔ)工作，為此提出一種綜合平均曲率與網(wǎng)格邊的三角網(wǎng)格模型特征線提取方法。分兩次提?。菏紫壤萌敲嫫ㄊ笂A角大小對模型中的尖銳邊進行初次提取特征點；然后綜合平均曲率與網(wǎng)格邊的關(guān)系對特征點進行二次提取；最后用兩次提取邊的頂點作為特征點，進行分類分組處理擬合成特征線。經(jīng)過實例驗證，該算法可以快速地提取尖銳邊和過渡邊等，具有很好的提取效果。

特征線提取 三角網(wǎng)格模型 曲率估計 逆向工程

0 引 言

隨著數(shù)字幾何獲取技術(shù)的發(fā)展，大量的復(fù)雜形體采用三角網(wǎng)格表示。三角網(wǎng)格可以表達(dá)任意形狀和拓?fù)涞娜S幾何模型，但是對采樣獲取的三角網(wǎng)格模型還需要開展很多后續(xù)幾何處理工作，例如幾何特征提取、網(wǎng)格分割以及模型重構(gòu)等。網(wǎng)格模型的特征線或特征邊緣的識別和提取是后續(xù)幾何和特征識別的基礎(chǔ)。經(jīng)過多年的發(fā)展，很多學(xué)者對如何從三角網(wǎng)格模型中提取特征線的問題提出了很多方法，主要分為兩大類，即基于面和基于邊的方法。此外還有一些學(xué)者將兩種方法結(jié)合起來，如Razdan等[1]。

基于面的方法主要是對三角網(wǎng)格數(shù)據(jù)模型中的點根據(jù)某種屬性(例如法矢、主曲率以及特征值等) 進行標(biāo)識。然后選取一組“種子點”，從這些“種子點”開始進行K-階鄰域的區(qū)域增長，找出具有相同標(biāo)識的點歸為同一數(shù)據(jù)塊，直到K-階鄰域沒有與標(biāo)識一樣的點才停止區(qū)域增長。整個網(wǎng)格數(shù)據(jù)模型的點都被劃分為不同數(shù)據(jù)塊，而不同數(shù)據(jù)塊之間的邊界就構(gòu)成了網(wǎng)格模型的特征線。例如，Wang等[2]先根據(jù)曲率將頂點分類，再利用統(tǒng)計學(xué)方法和高斯映射進行區(qū)域增長，從而確定模型的特征線；韓麗等[3]的基于離散曲率的網(wǎng)格分割方法，采用曲率作為點的標(biāo)識，進行區(qū)域增長；Kim等[4]的基于張量投票理論的特征線提取方法，采用張量投票矩陣特征值作為點的標(biāo)識，依據(jù)特征值分布與點的幾何特征之間關(guān)系對頂點進行分類，張慧娟等[5]對其方法進行了優(yōu)化處理。這種方法對二次曲面效果較好，對自由曲面則效果不佳。

基于邊的三角網(wǎng)格數(shù)據(jù)模型特征線提取的方法一般先對網(wǎng)格離散頂點進行曲率估計，找出那些曲率突變點，并將其作為特征點，最后將這些特征點有序地擬合成線，即特征線。典型的有Milroy等[6]在OCS(Orthogonal Cross Section) 模型上，估算三角網(wǎng)格模型上各點的法矢，利用法矢和K-階鄰域的點的信息擬合成一張二次曲面，從而計算出主曲率與主方向。若主曲率在主方向上取得極值，則該點被確定為特征點，然后利用能量最小化原則將特征點連接成線，即為特征線。劉勝蘭等[7]根據(jù)一條邊上兩個相鄰三角面片法矢的夾角和每個頂點的主曲率是否在主方向上為極值，分兩次提取，再將這些點連成線。這些方法對特征點的判斷計算量大，降低了提取效率。

本文在深入分析以前算法的基礎(chǔ)上提出一種新的對三角網(wǎng)格模型中的特征線提取算法。該算法是在三角網(wǎng)格數(shù)據(jù)模型的基礎(chǔ)上采用綜合平均曲率與網(wǎng)格邊的方法來實現(xiàn)的，省略了對特征點的直接判斷，而是通過網(wǎng)格模型三角形邊是否為特征邊間接地判斷該特征邊的兩個端點是否為特征點，提高了效率。

1 Taubin曲率估計算法分析及改進

曲率估計算法一般分為兩大類算法：一是K-階鄰域曲面擬合法[8]，二是頂點離散估計[9]。K-階鄰域曲面擬合法是將一點與周圍K-階鄰域頂點進行局部擬合成一個曲面，利用擬合曲面的方程計算該點的曲率。K值越大，擬合區(qū)域越大，估算曲率也就越精確，抗噪性越好，但計算量就會越大。頂點離散估計法相對于擬合法減少了計算量，提高了估算效率。Taubin利用特征向量方法估算了頂點主曲率與主方向，該方法在網(wǎng)格分布均勻時因估算準(zhǔn)確，計算量小而得到廣泛使用。

1.1 網(wǎng)格頂點法矢估計

Taubin曲率估計算法[9]首先是對頂點法矢的估算，頂點法矢的估算尤為重要，直接影響后面對稱矩陣的構(gòu)造以及曲率的精確度。在三角網(wǎng)格拓?fù)渲亟ㄟ^程中保存了點、線、面的鄰接關(guān)系以及面的法矢，從圖1可以看出，點vi的一環(huán)鄰域中的點、線、面的關(guān)系。Taubin頂點法矢是以面積為權(quán)值的相鄰三角面片的法矢的矢量和，具體估算為：

(1)

其中，fk為三角面片的面積，F(xiàn)i為頂點相鄰的所有三角形，Nfk為三角面片的法矢量。

圖1 法矢估計模型

然而，網(wǎng)格頂點法矢不僅受到相鄰三角形大小的影響，還受到三角形的形狀以及相鄰三角形分布密度的影響。而Taubin曲率估計算法中，使用面積加權(quán)法對網(wǎng)格頂點法矢的計算只考慮了頂點相鄰三角形的大小，忽略了三角形形狀和密度的影響。目前有很多學(xué)者都提出改進的方法，如神會存等[10]在權(quán)值中加入三角面片頂點處內(nèi)角。本文在Taubin的基礎(chǔ)上提出一種新的加權(quán)方法，其表達(dá)式為：

(2)

其中，Lk為三角形周長，dj,j+1為頂點相鄰三角形與頂點相對的邊長，dk為三角形質(zhì)心到頂點的距離。

|fk|/Lk不僅將三角形面積考慮在內(nèi)，還將三角形分布密度作為影響因素包含在內(nèi)，在頂點一側(cè)區(qū)域面積一定的情況下，三角形密度越大，單個三角形面積越小，其對應(yīng)的三角形周長反而相對增大，|fk|/Lk變小，這樣就減小了緊密一側(cè)三角形對頂點法矢的影響；對于狹長三角形，dj,j+1比較小，而dk比較大，這樣dj,j+1/dk就會很小，從而降低了狹長三角形對法矢的影響。圖2是權(quán)值改變前后，對某一網(wǎng)格模型局部的法矢計算結(jié)果對比，可以看出權(quán)值改變后法矢方向明顯垂直于網(wǎng)格表面。

圖2 權(quán)值改進前后結(jié)果對比

1.2 Householder矩陣及Givens變換

Householder矩陣的構(gòu)造直接影響頂點主方向的計算。Taubin曲率算法一個關(guān)鍵步驟是將構(gòu)造矩陣轉(zhuǎn)化為對角陣，先后經(jīng)過Householder變換和Givens變換，在Householder矩陣構(gòu)造時，Taubin選取的Wvi陣構(gòu)造方法，使得Qvi的第一列向量與頂點法矢Nvi成一個小的夾角，從而導(dǎo)致主方向所在平面也發(fā)生了旋轉(zhuǎn)。此時的Qvi無法滿足式(3)，即無法使式(4)右邊矩陣的首行首列為0，降低了主方向的計算精度。

(3)

(4)

為了提高計算精度，本文利用了Nvi是構(gòu)造矩陣Mvi的特征向量和其對應(yīng)的特征值為0，并依據(jù)Householder矩陣的性質(zhì)，采用一種新的Wvi構(gòu)造方法，如下：

(5)

(6)

這樣就保證了Qvi的第一列向量與頂點法矢Nvi相等向量，滿足式(3)，完成對角化第一步得到式(4)。

圖3為Householder矩陣改進前后對螺旋掃描體網(wǎng)格某型的同一局部的主方向計算結(jié)果對比。由圖可以看出Householder矩陣改進后，在螺旋掃描體上兩個主方向相互垂直，分別位于兩個相切方向上，較符合理論實際情況，使該曲率估計精度得到了提高。

圖3 Householder改進前后結(jié)果對比

在曲率估計算法中，主方向與Householder變換后的方向成一個夾角θ，需要經(jīng)過Givens變換求出θ，進而獲得主方向。則Givens變換為：

(7)

其中主對角線的值為：

(8)

(9)

由Givens變換副對角線值為零可以得到cosθ和sinθ值，可以獲得主方向：

(10)

同樣可以獲得主曲率：

(11)

高斯曲率和平均曲率為：

(12)

2 特征線提取算法

本文算法利用網(wǎng)格模型中的三角形邊分兩次間接地對特征點進行提取，然后再根據(jù)提取方法的不同分類，將這些特征點分組提取為特征線，由STL文件到提取特征線過程如圖4所示。

圖4 提取算法流程圖

主要分為三個模塊：1) 三角網(wǎng)格模型拓?fù)潢P(guān)系重建，主要利用已有的數(shù)據(jù)結(jié)構(gòu)[11-12]進行點線面關(guān)系重構(gòu)；2) 特征點提取，分兩次對尖銳邊與平滑過渡邊進行提取，通過法矢夾角運算與曲率計算識別特征邊，進一步獲得特征點；3) 點擬合成線，由兩次得到的特征點按提取方法不同分類，各類特征點分組擬合成線。

2.1 特征邊初次提取

在采樣獲取的三維網(wǎng)格模型中，只要幾何特征還存在于模型中，就會留下痕跡，即凹凸邊線。網(wǎng)格模型雖然弱化了一些特征，但對尖銳凹凸線還是會保留的，并且其三角形的邊與特征線方向基本上保持一致。

在三角網(wǎng)格模型中，尖銳邊相鄰的兩個三角面片夾角比較小，隨著尖銳特征減緩，其夾角也逐漸增大；當(dāng)夾角小于預(yù)設(shè)定的閾值時，則將該邊標(biāo)識為特征邊，反之則不作標(biāo)識，一般閾值設(shè)置為120。兩個三角面片的夾角與其法矢夾角成互補關(guān)系，所以可以用法矢夾角大小來識別特征邊；此時的閾值也與三角面片的閾值成互補關(guān)系，即法矢夾角大于此時的閾值(60)時識別為特征邊，夾角越大，則邊越尖銳，這樣可以方便地提取網(wǎng)格模型中的尖銳邊。

該方法計算簡單，運行速度快，減少了耗費時間的曲率計算，對一些簡單零件模型可以直接滿足要求。但對于零件中的平緩過渡的特征邊無法處理，還需要采用曲率與凹凸性關(guān)系的方法來識別三角面片之間的平滑過渡特征線。

2.2 二次提取特征邊

平緩過渡特征邊通常連接兩個沒有明顯分界的曲面，該類特征邊特征不明顯，提取比較困難。文獻(xiàn)[7,13]利用曲率判斷該邊上的點是否為極值點的方法來處理這種特征邊，這種方法計算量大，處理時間長。本文利用平均曲率與凹凸性的關(guān)系來處理這種特征邊，避免了對極值的判斷，降低了計算量。

Besl等[14]根據(jù)高斯曲率與平均曲率的正負(fù)將點的局部曲面分為了9類，任意復(fù)雜曲面都可以由這些曲面組合而成，而平緩過渡特征邊通常就是這些曲面的分界邊，表1僅給出了平均曲率與曲面凹凸性的關(guān)系。

表1 平均曲率與曲面凹凸性關(guān)系

如圖5所示，兩個相鄰三角形存在一個公共邊ei,j，其兩個端點分別為vi和vj，vi+1和vj+1稱為該邊相對的兩個頂點。由表1可知，判斷ei,j是否為特征邊只需要比較該邊相對的兩頂點vi+1和vj+1的平均曲率與0的大小。本文采用區(qū)間(-0.01, 0.01)代替0值，這樣能夠形成三個區(qū)間，若兩點的平均曲率值分別屬于兩個不同的區(qū)間，則將該邊進行標(biāo)識。

圖5 邊與相對點模型

尖銳邊上的頂點，即初次提取的特征邊上的頂點，這些頂點的曲率都是由差別很大曲面甚至尖銳邊上的頂點估計出來的，可能會導(dǎo)致了這些點的曲率估計誤差較大。若vi+1和vj+1取到這些點，可能會對邊的判斷產(chǎn)生較大的誤差，本文如果采用出現(xiàn)這種情況，則直接放棄對該邊的標(biāo)記。

經(jīng)過上述過程，一些因為網(wǎng)格化而形成的凸凹特征邊也會被提取出來，里面存在一些偽特征邊，需要將其分離出來以得到真正的特征邊，因此除去偽特征邊是必不可少的一步。通常判斷一個點是否為特征點, 就是判斷該點的曲率在主方向上是否為極值點[13]。本文基于這種思想定義了邊的主方向，并利用邊的主方向與邊的夾角關(guān)系來除去偽特征邊。

邊的主方向：在網(wǎng)格模型中，邊是由兩個頂點連接而成，用這兩個頂點主方向的矢量和作為該邊的主方向，如下式：

PD=PD1+PD2

(13)

其中PD為邊的主方向，PD1和PD2為邊兩個端點的主方向，矢量和示意如圖6所示，這樣定義邊的主方向既減小了以單個頂點作為邊的主方向所引起的誤差又可以將邊的變化趨勢合理反應(yīng)出來。

圖6 邊主方向計算示意圖

當(dāng)邊的方向與邊的主方向中的其中一個一致時，就將該邊標(biāo)識為特征邊。在三角網(wǎng)格模型中，邊與邊主方向不可能完全一致，會成一個夾角關(guān)系,因此，本文設(shè)置了一個區(qū)間(0, 30)，當(dāng)夾角在這個區(qū)間范圍內(nèi)時，就判定該邊為特征邊，否則就去除該邊。

2.3 獲取特征線

以上得到的特征邊都是由三角形邊組成的，這些邊的頂點通過去除冗余點后就組成了特征點集合。文獻(xiàn)[7]將這些特征點排序后分組擬合成B樣條，由于B樣條擬合會消除尖角處特征，那么兩條特征線的夾角處特征就有可能被消除，如圖7所示。

圖7 尖角特征被消除

本文根據(jù)兩次提取方法不同將特征點分成兩類，一類是由尖銳邊得到特征點，另一類是由平緩過渡邊得到的特征點。對第一類特征點做分組有序連接線處理；另一類采用了劉勝蘭等[7]的方法分組擬合成B樣條曲線。

2.4 算法實現(xiàn)描述

本文整體提取算法步驟如下：

輸入： STL文件格式數(shù)據(jù)。

輸出： 三角網(wǎng)格模型特征線。

Step1 讀入STL文件格式數(shù)據(jù)，并建立點、邊、面之間的拓?fù)潢P(guān)系，分別儲存于點表、邊表和面表中。

Step2 提取尖銳特征邊。邊e兩鄰面法向量n1和n2，夾角φ= ，閾值θ，若φ>θ，標(biāo)識該邊為特征邊，存在邊數(shù)組EArray1中。

Step3 提取平緩過渡特征邊。

Step3.1 利用改進后的Taubin曲率估算法估算頂點曲率。

Step3.2 根據(jù)平均曲率與凹凸性的關(guān)系，并以尖銳特征邊頂點作為限制條件提取初始特征邊。

Step3.3 去除偽特征邊，并將特征邊保存在邊數(shù)組EArray2中。

Step4 將EArray1和EArray2中邊的頂點分別保存在特征點數(shù)組Array1和Array2中，并分類分組處理擬合成線。

在Step2中的尖銳邊不包括邊界邊，邊界邊可由一條邊的相鄰三角形個數(shù)進行判斷[15]，這里不再贅述。

3 實 例

為了驗證本算法的有效性，本文算法通過Visual C++ 2008和OpenGL開發(fā)平臺編程實現(xiàn)，實驗環(huán)境是Windows XP操作系統(tǒng)，主頻2.6 GHz，內(nèi)存為2.0 GB，為了更能說明本文算法提取結(jié)果的有效性，采用的文獻(xiàn)[7]的算法進行對比分析。

表2給出兩種模型基本信息和文獻(xiàn)[7]算法與本文算法分別耗用的時間。圖8、圖9分別給出了利用文獻(xiàn)[7]算法和本文算法對表1中的齒輪模型與大象模型分別提取特征線后的結(jié)果對比圖。

表2 模型特征線提取算法時間耗費

圖8 齒輪模型兩種算法對比圖

圖9 大象模型兩種算法對比圖

經(jīng)過對兩種算法的對比分析，本文算法與文獻(xiàn)[7]算法識別的模型輪廓基本一致，有力地說明了本文算法的有效性。此外本文算法還可以有效地識別一些不易被識別出的平滑過渡線，如齒輪齒根處的過渡線，大象鼻子處的輪廓線；在光順性方面，本文算法識別效果也比較突出，整體光順性比文獻(xiàn)[7]的有所提高。

在整個計算過程中，兩種算法都進行了曲率估計，文獻(xiàn)[7]運用曲面擬合，計算量大，本文使用離散估計，大大地減少了計算量。此外，相對于文獻(xiàn)[7]中的算法，本文并沒有直接對特征點進行判斷，而是通過特征邊間接地得到特征點，在此方面也減少了計算量，提高了算法效率。

4 結(jié) 語

本文對Taubin曲率算法做出了一些改進，并在此基礎(chǔ)上提出了一種新的特征線提取算法。該算法充分利用了三角形法矢以及平均曲率與凹凸性的關(guān)系，分兩次提取特征點，最后對特征點進行擬合成線處理。實驗表明，該算法對網(wǎng)格模型特征線提取效果較好，尤其是對機械零件的特征線提取，直接跳過了對頂點的判斷，減少了計算量。但是對含有大量噪聲的模型或自然網(wǎng)格模型等網(wǎng)格模型提取結(jié)果連續(xù)性較差，有待進一步提高，下一步重點對此進行研究。

[1] Razdan A, Bae M. A hybrid approach to feature segmentation of triangle meshes[J]. Computer-Aided Design, 2003, 35(9):783-789.

[2] Wang J, Yu Z. Surface feature based mesh segmentation[J]. Computers & Graphics, 2011, 35(3):661-667.

[3] 韓麗, 高小山, 楚秉智. 離散曲率約束的三角網(wǎng)格模型拓?fù)浞指钏惴╗J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2009, 21(6):831-835.

[4]KimHS,ChoiHK,LeeKH.Featuredetectionoftriangularmeshesbasedontensorvotingtheory[J].Computer-AidedDesign, 2009, 41(1):47-58.

[5] 張慧娟, 耿博, 汪國平. 采用張量投票理論的三角網(wǎng)格特征邊提取算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2011, 23(1):62-70.

[6]MilroyMJ,BradleyC,VickersGW.Segmentationofawrap-aroundmodelusinganactivecontour[J].Computer-AidedDesign, 1997, 29(4):299-320.

[7] 劉勝蘭, 周儒榮, 張麗艷. 三角網(wǎng)格模型的特征線提取[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2003, 15(4):444-448,453.

[8]RazdanA,BaeM.CurvatureestimationschemefortrianglemeshesusingbiquadraticBézierpatches[J].Computer-AidedDesign，2005, 37(14):1481-1491.

[9]TaubinG.Estimatingthetensorofcurvatureofasurfacefromapolyhedralapproximation[C]//Proceedingsofthe5thInternationalConferenceonComputerVision, 1995:902-907.

[10] 神會存, 李建華, 周來水. 三角網(wǎng)格模型頂點法矢與離散曲率計算[J]. 計算機工程與應(yīng)用, 2005(26):12-15.

[11]SiegerD,BotschM.Design,implementation,andevaluationofthesurfacemeshdatastructure[C]//Proceedingsofthe20thInternationalMeshingRoundtable.Heidelberg:Springer, 2011:533-550.

[12]GurungT,LuffelM,LindstromP,etal.Zipper:Acompactconnectivitydatastructurefortrianglemeshes[J].Computer-AidedDesign, 2013, 45(2): 262-269.

[13]YangM,LeeE.Segmentationofmeasuredpointdatausingaparametricquadricsurfaceapproximation[J].Computer-AidedDesign, 1999, 31(7):449-457.

[14]BeslPJ,JainRC.Segmentationthroughvariable-ordersurfacefitting[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 1988, 10(2):167-192.

[15]JunY.Apiecewiseholefillingalgorithminreverseengineering[J].Computer-AidedDesign, 2005, 37(2):263-270.

A FEATURE LINE EXTRACTION METHOD COMBINING MEANCURVATURE WITH MESH EDGES

Wang Qinrui Zhang Yingzhong Luo Xiaofang

(SchoolofMechanicalEngineering,DalianUniversityofTechnology,Dalian116024,Liaoning,China)

With the development of digital geometry technology, a large number of complex shapes are represented by the mesh model. It is the basic work for follow-up geometry and feature recognition to identify and extract feature lines. Thus, a feature line extraction method combining mean curvature with mesh edges is presented. Firstly, the angle between the normal of adjacent triangles is used for the initial extraction of sharp edges. Then the feature edges are extracted according to the relationships between concave-convex properties and mean curvature of the surface. Finally the vertices of the extracted feature edges are classified and linked into feature lines. The case study verifies that the proposed algorithm can extract sharp edges and transition feature edges efficiently and effectively.

Feature line extraction Triangular mesh model Curvature estimation Reverse engineering

2015-11-11。國家自然科學(xué)基金項目(51375069)。王欽瑞，碩士生，主研領(lǐng)域：數(shù)字網(wǎng)格分割及特征重構(gòu)。張應(yīng)中，副教授。羅曉芳，副教授。

TP391.41

A

10.3969/j.issn.1000-386x.2017.01.043