三角網(wǎng)格模型特征線提取方法

上官寧,劉斌

(華僑大學機電及自動化學院,福建泉州362021)

三角網(wǎng)格模型特征線提取方法

上官寧,劉斌

(華僑大學機電及自動化學院,福建泉州362021)

提出一種三角網(wǎng)格模型的特征線提取方法.在三角網(wǎng)格模型特征點提取的基礎上,人工交互地指定初始特征點.由初始特征點開始,應用主成分分析法分析特定范圍內(nèi)特征點集的主方向,尋找主方向上距離質(zhì)心最遠的特征點,并作為特征方向上的后繼特征點;依次迭代,順序記錄特征點序列,直至尋找的后繼特征點落回到初始特征域內(nèi)才結束.最終,用3次非均勻B樣條曲線,將得到的特征點集合擬合生成光滑特征線.

三角網(wǎng)格模型;特征線;提取;主成分分析;主曲率

在反求工程、計算機動畫、計算機可視化等領域,對網(wǎng)格模型進行CAD模型重建、網(wǎng)格簡化、網(wǎng)格光順、網(wǎng)格變形及網(wǎng)格編輯等處理過程中,通常希望能夠保留模型的特征.更為實際的是,三角網(wǎng)格模型被廣泛地應用于表達任意形狀和拓撲的三維幾何模型.現(xiàn)有的網(wǎng)格模型特征線提取方法,一般是先找出網(wǎng)格上曲率突變點作為特征點,然后,將這些離散的特征點連接成線,也就是特征線.典型的代表有M ilroy等[1]在OCS(Orthogonal Cross Section)模型的基礎上,估算出模型上各點處的法矢,利用法矢和鄰點信息擬合一張二次曲面,計算該二次曲面的主曲率和主方向,主曲率在主方向的極值點被確定為特征點;然后,用能量最小化原則將特征點連成樣條線.Yang等[2]通過建立局部參數(shù)二次曲面來計算主曲率和主方向,實現(xiàn)了對密集數(shù)據(jù)點云的特征線提取.該方法對有誤差影響的點云或稀疏點云不適用.劉勝蘭等[3]提出,根據(jù)相鄰三角片的法矢夾角和各點主曲率是否為極值,分兩次提取特征點,利用三角頂點加權和均勻化等方法,減少狹長三角片對特征點提取的計算誤差影響;然后,將特征點分組連接成B樣條曲線,實現(xiàn)了三角網(wǎng)格模型的特征線提取.郭延文等[4]提出半自動化特征線提取技術,根據(jù)用戶指定的點集,考慮兩點間的距離和方向及曲率信息,提取出初始特征區(qū)域后,再將特征區(qū)域映射至二維平面.最后,運用Snake算法精煉后映射回三維空間,得出平滑特征線.這些方法對于離散的網(wǎng)格模型的特征點提取已很成熟,然而,將這些特征點連接生成特征線的過程都存在弊端,因此并不能很好地將特征點分組連接.為此,本文著重研究三角網(wǎng)格模型的特征線提取.

1 特征點提取

三角網(wǎng)格模型的特征線生成算法是,采用主曲率極值法來判斷提取出模型的特征頂點.

1.1 離散網(wǎng)格頂點法矢計算

三角網(wǎng)格模型是離散的,不同于連續(xù)表面.采用文[5]從力學角度提出的單位法矢加權疊加公式,計算模型中網(wǎng)格頂點法矢.如圖1所示,對于三角網(wǎng)格模型中的任一點Vi,設Vi的m個相關三角形為Tk(1≤k≤m).相應地,Vi有m個相鄰頂點Pk(1≤k≤m),Ni為頂點Vi處的法矢,nk為Tk向外的單位法矢,di,k為Vi與Pk的距離.則有

1.2 主曲率和主方向的計算

由曲面論可知,零件的棱線、脊線、曲面交線等處曲面的曲率較大.為計算每一頂點的曲率,可在頂點P處建立曲面S(u,v)=(u,v,h(u,v)),如圖2所示.其中:h(u,v)=au2+buv+cv2局部坐標系(Phuv)由絕對坐標(Oxyz)經(jīng)變換可得,即經(jīng)O平移至P,再旋轉(zhuǎn)使得z軸與h軸重合,此時u,v可取x,y軸.

建立的曲面在P點處存在無數(shù)條主法矢和曲面的法矢N重合的曲線,該曲線族的曲率k是曲面在P點的法曲率.法曲率中的極小值k1和極大值k2稱為主曲率,k1,k2對應的曲線的切線方向分別為m1, m2,稱為主方向,兩者總是互相垂直.

由式(1)可以求出任一點Vi的法矢Ni,然后,在Vi處建立二次曲面S(u,v),且Vi點的鄰接點Vj(1≤j≤m)在局部坐標系(Phuv)下的坐標值為(uj,vj,hj).由m個鄰點得到的線性方程組為

圖1 Vi點的法矢Fig.1 No rmal vector of vertex Vi

圖2 P點的局部坐標系Fig.2 Local coo rdinate system of point P

用最小二乘法解此方程組,即可求得曲面S(u,v).方程的最小二乘解就是使得各個鄰點到曲面距離的平方和最小時的解.由曲面的第一、第二基本公式,可得到曲面上Vi處的法曲率k,即

其中:λ=d u/d v;d k(λ)/dλ=0的根為λ1,λ2.此時,法曲率k就達到它的極值k1,k2,對應的主方向為(1, λ1),(1,λ2);或者為(-λ1,1),(-λ2,1).對于曲面S(u,v),k1,k2值分別為

圖3 極值點判斷示意圖Fig.3 Schematic of determination of extremum point

1.3 主曲率極值判斷

在計算出各頂點的主曲率后,可通過對主曲率的極值判斷得出特征點集.具體方法如圖3所示.

對任意頂點Vi,在m1方向及其反向的延長線與三角形的交點為A,B (實際空間上并不相交,是延長線在三角面上的垂直投影與三角形的交點).當Vi點主曲率k1的絕對值大于A,B兩點在m1方向上的k值的絕對值時,則Vi點就是在m1方向上的曲率極值點,標示為特征點.A,B點的k值可由Vj,Vj+1在m1方向上的k1值線性組合求得.該方法同樣適用于k2,可判斷Pi在方向m2是否為特征點.

需要說明的是,由于存在曲率計算誤差,直接根據(jù)上述極值判斷的特征點遠遠多于實際所需.引入文[3]中的辦法,加入局部和整體誤差消除因子.

(1)加入局部誤差消除因子Ierr.在比較極值時,用(1-Ierr)×k1來代替k1,用(1-Ierr)×k2來代替k2,即Vi點主曲率極值比A,B點的k值大到一定程度時,才認為該點是特征點.Ierr可使特征點密集的區(qū)域稀疏化,可根據(jù)實際情況取值.為了增強大曲率區(qū)域的影響,給每一極值點賦一個曲率權值.權值等于主曲率極值的絕對值,若主曲率在兩個方向上均為極值,則取極值的絕對值之和.

(2)加入整體誤差閾值gerr.對于每一個曲率極值點,當某一點曲率權值與最大曲率權值的比值小于閾值gerr時,則將這一點從特征點序列中去掉,即利用gerr可以去掉曲率平坦區(qū)域的雜點.

圖4 鞋楦模型及其特征點提取Fig.4 Shoe lastmodel and the extraction of its feature points

對鞋楦三角網(wǎng)格模型進行特征點提取,如圖4所示.圖4中:網(wǎng)格頂點數(shù)為18 064;提取的特征點數(shù)為3 824;Ierr取0.008;gerr取所有主曲率極值的絕對平均值的0.05%.

2 特征線生成

把已提取出的所有特征點看作一個特征點集F,集合中特征點的排列是無序的,且存在某些雜點或不是主要關注的特征點.如圖4中鞋楦模型的特征點中,主要關注的是統(tǒng)口線和楦底板線這兩條特征線的識別.提出一種基于主成分分析技術(PCA),將無序的特征點集有針對性的分組連接,由用戶指定需要提取的初始特征位置的特征線生成算法.

2.1 主特征方向識別

特征線生成的第1步,是要將無序的特征點集有序化,形成一串沿特征方向行進的特征點序列,而其首要任務就是識別主特征方向.

對于特征點P∈F,P點在其δ鄰域內(nèi)的特征點集合為N(P)={pi∈F||pi-P|≤δ},i=1,…,k.然后,應用PCA方法,對N(p)進行主成分分析.讓集合N(P)中的任一點pi減去集合中所有點的平均坐標ˉp(即質(zhì)心坐標),計算協(xié)方差矩陣C(3,3)為

對協(xié)方差矩陣進行特征分解,求解特征方程

則最大特征值λ0所對應的最大特征向量x0為特征點集合的第一主方向,即是所求的主特征方向.

圖5 不同δ鄰域的主特征方向識別Fig.5 Identification of p rimary feature direction in differentδneighbo rhoods

特別需要注意的是,δ鄰域大小的選取會影響主特征方向識別的準確性,尤其是特征點在局部分布不均勻的情況下.在δ鄰域選取不同大小時,對主特征方向識別的比較,如圖5所示.圖5中:虛線圓圈表示選取的δ大小;直線段為識別的主特征方向.

文[6]中提出了一種自適應地選取δ大小的方法,逐步遞增δ值來計算主方向.即將鄰域內(nèi)的點投影至主方向上,得到二維點集,其X坐標與Y坐標集合對應兩個隨機變量,并計算相關系數(shù)ρ(X,Y).根據(jù)線性相關性,直至|ρ|≥0.7時,選取的δ為較好的值.

2.2 特征線生成

由用戶指定初始特征點后,就可由初始特征點開始進行特征點排序.

首先,以初始特征點為中心,進行主特征方向識別.應用PCA方法提取初始特征域內(nèi)的主特征方向線后,將初始特征域內(nèi)的所有特征點投影至主特征方向線上,取出距離質(zhì)心最遠的特征點,作為后繼特征點加入特征點序列,且記錄初始特征點至該后繼特征點的方向為特征線的行進方向.

其次,再以剛求出的后繼特征點為中心,進入下一輪的主特征方向提取.

重復以上步驟,尋找又一后繼特征點.如此迭代,直至尋找的后繼特征點落回到初始特征域內(nèi)才結束.最終,可得到一串有序的特征點集合,用3次非均勻B樣條曲線擬合生成光滑特征線.

所提算法已用Visual C++語言和OpenGL技術在微機上編程實現(xiàn).鞋楦統(tǒng)口特征線提取的步驟示例,如圖6所示.

圖6 鞋楦模型統(tǒng)口特征線生成Fig.6 Feature line generation of mouth system of shoe lastmodel

3 結束語

在特征點提取的基礎上,提出應用主成分分析的方法識別主特征方向.沿特征點生長方向搜尋后繼特征點,達到將無序特征點有序化的目的,進而實現(xiàn)了網(wǎng)格模型的特征線提取.通過用戶交互式的選取初始特征點,可更針對性地進行有用特征線的提取,比自動提取方法更具實用價值.

[1] M ILROY M J,BRADLEY C,V ICKERS GW.Segmentation of a w raparound model using an active contour[J]. Computer Aided Design,1997,29(4):299-320.

[2] YANGM,LEE E.Segmentation of measured point data using a parametric quadric surface app roximation[J].Computer Aided Design,1999,31(7):449-457.

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

[4] GUO Yan-wen,PENGQun-sheng,HU Guo-fei,et al.Smooth feature line detection fo r meshes[J].Journal of Zhejiang University:Science(A),2005,6(5):460-468.

[5] 柯映林.離散數(shù)據(jù)的幾何造型技術及其應用研究[D].南京:南京航空航天大學,1992.

[6] DAN IELSJⅡ,HA L K,OCHOTTA T,et al.Robust smoo th feature extraction from point clouds[C]∥Proceedings of the IEEE International Conference on Shape Modeling and App lications.Washington D C:IEEE Computer Society,2007:123-136.

SHANG-GUAN Ning,L IU Bin
(College of Mechanical Engineering and Automation,Huaqiao University,Quanzhou 362021,China)

A method of feature line extraction from triangular mesh model is p resented.Initial feature point ismanually specified based on feature points extraction from triangularmesh model.From the beginning of initial feature point,method of p rincip le component analysis(PCA)is used to analyze p rimary direction of feature points in a special region and to search the feature pointw hich is farthest from the center ofmass in the p rimary direction and w ill be chosen as subsequent feature point.Iteratively,the sequence of the feature points is reco rded in order until the sought subsequent feature points are among the initial feature region.Finally,third-o rder non-uniform rational B-spline curve is used and that obtained set of feature points is fit into a smooth feature line.

triangular mesh model;feature line;extraction;p rincipal component analysis;p rincip le curvature

Investigation of Feature L ine Extraction from Triangular Mesh M odel

TP 391.41

A

(責任編輯:陳志賢 英文審校:鄭亞青)

1000-5013(2010)05-0487-04

2009-07-04

劉斌(1972-),男,副教授,主要從事材料成型數(shù)值模擬的研究.E-mail:mold_bin@hqu.edu.cn.

福建省科技計劃重點項目(2006H0029);福建省自然科學基金資助項目(E0710017,E0810040)