基于RANSAC算法的三角網(wǎng)格特征曲面提取_圖文

1、2009年1月第37卷第1期機(jī)床與液壓MACH I N E T OOL &HY DRAUL I CSJan 12009Vol 137No 11收稿日期:2007-12-10基金項(xiàng)目:總裝備部預(yù)先研究項(xiàng)目資助(41318111117;航空科學(xué)基金資助項(xiàng)目(2008Z B55001作者簡(jiǎn)介:劉元朋(1976,男,博士,講師,主要研究方向?yàn)榉辞蠊こ?、CAD /CA M 和工業(yè)I CT 成像。電話:135*,E -mail:drag on_ly psina 1co m 1cn ?；赗ANS AC 算法的三角網(wǎng)格特征曲面提取劉元朋,陳良驥,趙輝(鄭州航空工業(yè)管理學(xué)院機(jī)電工程系,河南鄭州4500

2、15摘要:針對(duì)三角網(wǎng)格模型中的二次曲面提取問題,利用隨機(jī)抽樣一致性算法(Random Samp ling Consensus,RANS AC 提出了一種球面、圓柱面和圓錐面等二次特征曲面的提取算法。該算法首先計(jì)算每個(gè)頂點(diǎn)的法向量,然后用帶頂點(diǎn)法向量的三角面片統(tǒng)一表示每類二次曲面的最小子集,最后利用RANS AC 算法進(jìn)行二次曲面提取。實(shí)驗(yàn)結(jié)果分析表明該算法具有良好的穩(wěn)定性和運(yùn)算效率等特點(diǎn)。關(guān)鍵詞:隨機(jī)抽樣一致性算法;三角網(wǎng)格;二次曲面提取中圖分類號(hào):TP391172文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1001-3881(20091-014-3Extracti n g Fea ture Surface f

3、ro m Tr i a ngul ar M eshes Ba sed on RANSAC A lgor ith mL I U Yuanpeng,CHEN L iangji,ZHAO Hui(Depart m ent of Mechanical and Electrical Engineering,ZhengzhouI nstitute of Aer onautical I ndustry Manage ment,Zhengzhou Henan 450015,China Abstract:An aut omatic algorith m was p resented t o detect qua

4、dric fr om triangular mesh .The method is based on random sa m 2p ling consensus algorith m and iteratively detects p lanes,s pheres,cylinders and cones .I n order t o reduce the nu mber of requiredpoints t o define a unique instance of each quadric,the algorith m computes an app r oxi m ate surface

5、 nor mal f or each point firstly,then the m ini m al subset is defined as a triangle with l ocal orientati on t o i m p r ove the r obust of the algorith m.Experi m ental results de mon 2strate that the algorith m is capable t o extract a variety of different types of quadric,while retaining such fa

6、vorable p r operties as high r obustness,effectiveness and generality .Keywords:Random sa mp ling consensus algorith m;Triangular mesh;Quadric surface extracti on0前言隨著激光測(cè)距掃描等三維數(shù)據(jù)采樣技術(shù)的進(jìn)步和硬件設(shè)備性能的提高,三角網(wǎng)格曲面正在逐漸成為計(jì)算機(jī)圖形學(xué)和幾何設(shè)計(jì)領(lǐng)域的新寵。三角網(wǎng)格模型作為一種對(duì)原始模型的線性逼近,被廣泛應(yīng)用于快速原型制造、醫(yī)用圖像、地理地形繪制、計(jì)算機(jī)游戲等許多應(yīng)用領(lǐng)域。但是,這種模型只有一階連續(xù),精度

7、不高,使用三角網(wǎng)格模型表示機(jī)械零件會(huì)損失零件模型的幾何信息和拓?fù)湫畔?使得設(shè)計(jì)者難以對(duì)零件模型進(jìn)行精確快速的分析。A l ons o 全面分析了產(chǎn)品反求建模的方法,并指出產(chǎn)品形面直接用低次參數(shù)曲面片(圓錐面、圓柱面、球面、比用傳統(tǒng)三角網(wǎng)格模型建模精確更高、計(jì)算更有效1。Nourse 指出85%的機(jī)械零件都可以用平面、圓錐面、球面和圓柱面來描述2。因此可靠地提取三角網(wǎng)格模型中的二次曲面是體現(xiàn)零件原始設(shè)計(jì)意圖反求建模的關(guān)鍵環(huán)節(jié)。常見的二次曲面提取方法主要有三類:Hough 變換法3、隨機(jī)抽樣一致性(Random Samp le Consen 2sus,RANS AC 算法4和優(yōu)化算法5。由于Hou

8、gh 變換法的空間需求是其參數(shù)空間的維數(shù)的指數(shù)函數(shù),這意味著該方法在空間上很浪費(fèi),很難用到有兩個(gè)以上參數(shù)的幾何形狀提取,事實(shí)上,Hough 變換法主要用于直線等平面二次曲線的提取。Rabbani 等6利用圓柱面的高斯圖特性,將圓柱面的參數(shù)轉(zhuǎn)化為平面二次曲線參數(shù)的組合,進(jìn)而利用兩個(gè)Hough 變換進(jìn)行圓柱面參數(shù)提取。RANS A 方法的主要優(yōu)點(diǎn)是數(shù)學(xué)上形式化和較低的空間要求,后者同點(diǎn)的數(shù)量呈線性關(guān)系,而不是與參數(shù)數(shù)目成指數(shù)關(guān)系,這是對(duì)Hough 變換方法的顯著改善,使得多個(gè)自由參數(shù)的幾何元素提取變得容易一些。Thomas 等提出了利用RANS A 法進(jìn)行圓柱面提取7。W ahl 等利用RANS

9、A 法從點(diǎn)云數(shù)據(jù)中提取平面8。RANS AC 的困難之處在于它的計(jì)算效率較低,RANS AC 算法的速度主要取決于兩個(gè)因素:要選擇的樣本數(shù),而樣本數(shù)和數(shù)據(jù)的錯(cuò)誤率、置信概率有關(guān)。所以,要提高RANS AC 算法速度的主要辦法是盡量減少樣本數(shù)。優(yōu)化算法是將二次曲面提取問題等同于尋找具有多個(gè)局部極小值的代價(jià)函數(shù)的最優(yōu)解,然后利用遺傳算法9、禁忌搜索10等方法進(jìn)行優(yōu)化求解。優(yōu)化算法的復(fù)雜度高,其運(yùn)算效率比RANS A 法更低。本文作者利用RANS AC 算法提出一種從三角網(wǎng)格模型中提取二次曲面的新方法。1算法基礎(chǔ)111相關(guān)定義在算法描述前,先給出幾個(gè)與算法相關(guān)的定義。三角網(wǎng)格模型M:M是由三維空間中

10、的三角面片通過邊和頂點(diǎn)連接而成的分片線性曲面,用頂點(diǎn)集合V=v1,v2,v m和三角面片集合T=T1,T2,Tn組成的二元組M=(V,T來表示。T(v=T1,T2,Tk表示所有與頂點(diǎn)v相連三角面片的集合。最小子集I:能唯一確定一個(gè)幾何元素所需要的最小點(diǎn)數(shù)的集合,表示為I=v1,v2,v R,R為最小子集中點(diǎn)的數(shù)量。對(duì)于直線而言,兩點(diǎn)即可唯一確定一條直線,所以I=v1,v2。殘差:殘差i 為頂點(diǎn)vi距待評(píng)估幾何元素的距離。最小子集I的代價(jià)函數(shù)g(I:3個(gè)頂點(diǎn)殘差都在一預(yù)定范圍內(nèi)的三角面片的個(gè)數(shù)。112RANS AC算法RANS AC算法的基本思想4:從隨機(jī)抽取的N組樣本中找出最優(yōu)的抽樣,并根據(jù)最

11、優(yōu)抽樣來選擇參與最后計(jì)算的原始數(shù)據(jù)。具體作法是:迭代地在輸入數(shù)據(jù)中采樣所謂的最小點(diǎn)集。并利用每次采樣所得到的最小點(diǎn)集估計(jì)出所要確定的參數(shù),同時(shí)根據(jù)一定的判斷準(zhǔn)則來判別輸入數(shù)據(jù)中哪些是與該參數(shù)相一致的,即內(nèi)點(diǎn),哪些是不一致的,即外點(diǎn)。如此迭代一定次數(shù)后,將對(duì)應(yīng)輸入數(shù)據(jù)中內(nèi)點(diǎn)比例最高的所估計(jì)參數(shù)值以及所篩選出來的內(nèi)點(diǎn)作為RANS AC最后解。將此解作為其它方法的初始值進(jìn)一步優(yōu)化計(jì)算,從而得到最后的估計(jì)參數(shù)值。抽樣次數(shù)N的計(jì)算公式如下:N=ln(1-sln(1-(1-R其中,為預(yù)期的原始數(shù)據(jù)錯(cuò)誤率,s代表至少有一個(gè)最小子集包含所有內(nèi)點(diǎn)的概率。采用隨機(jī)抽樣方法時(shí),使用盡可能少的數(shù)據(jù)來確定一組解是非常重

12、要的。因?yàn)槭褂幂^少的數(shù)據(jù)可以減少錯(cuò)誤數(shù)據(jù)被抽中的概率,同時(shí),所需要的抽樣次數(shù)即計(jì)算量隨所使用的數(shù)據(jù)量的增加成指數(shù)比例增長(zhǎng)。因而達(dá)到相同的估計(jì)精度,使用數(shù)據(jù)量越少算法就越快。2算法描述傳統(tǒng)確定一個(gè)二次曲面至少需要9個(gè)點(diǎn)10。為了較少抽樣次數(shù)N,引入點(diǎn)的法向量信息將最小子集的參數(shù)R統(tǒng)一為3。為了提高抽取的最小子集樣品質(zhì)量,利用三角面片抽樣來取代散亂點(diǎn)的抽樣,利用這種方法同時(shí)也提高了隨機(jī)抽取的效率。211頂點(diǎn)法向量計(jì)算本文中,對(duì)法向量估計(jì)采用文獻(xiàn)11中的公式進(jìn)行計(jì)算,其形式如下:nv=jT(vjAjn jTjT(vjAj其中,j、Aj和n jT分別表示T(v中第j個(gè)三角面片在頂點(diǎn)v處的頂角、面積和單

13、位法向量。212二次曲面識(shí)別本算法中的最小子集I為3個(gè)帶頂點(diǎn)法向量信息的頂點(diǎn)v1,v2,v3,其坐標(biāo)及法向量分別為p1,p2, p3和n1,n2,n3。通過坐標(biāo)和法向量信息可以估計(jì)每個(gè)最小子集所對(duì)應(yīng)的二次曲面類型。其中任一頂點(diǎn)vi與I所確定的二次曲面之間的殘差為i,其法向量ni與頂點(diǎn)pi在I所確定的二次曲面上的向量夾角為i。平面:平面的法向量n可以通過3個(gè)點(diǎn)的坐標(biāo)來確定12,其坐標(biāo)原點(diǎn)到平面的垂直距離參數(shù)取為d= -n Tp,其中p為3個(gè)坐標(biāo)點(diǎn)的平均值。最后通過3個(gè)i是否小于預(yù)定參數(shù)來判定(p,d是否可以作為一平面樣品數(shù)據(jù)。球面:任取兩個(gè)點(diǎn)(p1,n1和(p2,n2。取兩條直線p1+t n1=

14、0和p2+t n2=0間最短線的中點(diǎn)作為球心c,取球半徑為r=p1-c+p2-c2。最后通過3個(gè)i是否小于參數(shù)和3個(gè)i是否小于預(yù)定參數(shù)來判定(c,r是否可以作為一球面樣品數(shù)據(jù)。圓柱面:任取兩個(gè)點(diǎn)(p1,n1和(p2,n2。利用n1和n2確定軸線法向量=n1×n2,然后將兩條參數(shù)化曲線p1+t n1=0和p2+t n2=0分別投影到平面ax=0上,取兩條投影直線的交點(diǎn)作為軸線一點(diǎn)q0。取p1在平面ax=0上投影點(diǎn)與q的距離作為半徑r。最后通過3個(gè)i是否小于參數(shù)和3個(gè)i是否小于預(yù)定參數(shù)來判定(,q,r是否可以作為一圓柱面樣品數(shù)據(jù)。圓錐面:任取3個(gè)點(diǎn)(p1,n1、(p2,n2和(p3,n3

15、。利用3個(gè)點(diǎn)及其法向量確定3個(gè)平面,取3個(gè)平面交點(diǎn)作為頂點(diǎn)坐標(biāo)c。軸線法向量n通過3個(gè)點(diǎn)來確定c+pi-cpi-c3i=1,頂角取為=3i=1arccos(pi-cT/3。最后通過3個(gè)i是否小于參數(shù)和3個(gè)i是否小于預(yù)定參數(shù)來判定(c,n,是否可以作為一圓錐面樣品數(shù)據(jù)。在進(jìn)行二次曲面識(shí)別時(shí),通過圓錐面、圓柱面、球面和平面的順序依次進(jìn)行判斷,從而決定最小子集所屬的二次曲面類型。213內(nèi)點(diǎn)計(jì)算在三角網(wǎng)格模型中,相同類型的三角面片在物理上是連通的,可以形成一個(gè)塊。因此本文作者采用文獻(xiàn)13中所述的邊界擴(kuò)展生長(zhǎng)法來計(jì)算g(I。其51第1期劉元朋等:基于RANS AC算法的三角網(wǎng)格特征曲面提取主要思想為:以

16、最小子集抽取的三角面片為生長(zhǎng)點(diǎn),以三角面片頂點(diǎn)與二次曲面間的殘差為判斷標(biāo)準(zhǔn),進(jìn)行區(qū)域擴(kuò)張;待區(qū)域擴(kuò)張完畢,然后計(jì)算區(qū)域內(nèi)三角形的個(gè)數(shù),取其為g (I 。214算法流程整個(gè)算法的具體步驟如下:步驟1:設(shè)置參數(shù)的初始值N ,和T m in 。步驟2:計(jì)算V 中每個(gè)頂點(diǎn)的法向量。步驟3:隨機(jī)從三角面片集合T 抽取N 組樣本,確定每組樣本的曲面類型,并計(jì)算每個(gè)樣本I 所對(duì)應(yīng)的代價(jià)函數(shù)g (I 。步驟4:獲得最優(yōu)樣本I 對(duì)應(yīng)的內(nèi)點(diǎn)區(qū)域S,對(duì)S中頂點(diǎn)利用最小二乘法14進(jìn)行擬合獲得相應(yīng)特征曲面參數(shù),且從T 中刪除S 中的三角面片。步驟5:如果T 中三角面片的數(shù)量大于預(yù)定閾值T m in ,轉(zhuǎn)步驟3。步驟6:

17、結(jié)束。3驗(yàn)證實(shí)例本文作者提出的算法通過V isual C +和VTK 實(shí)現(xiàn)。為了驗(yàn)證算法的有效性,在Pentium 4210G,內(nèi)存256MB 的計(jì)算機(jī)上,分別對(duì)機(jī)械零件(40k 個(gè)三角面片,見圖1(a ,Fandisk (13k 個(gè)三角面片,見圖2(a 模型進(jìn)行了二次曲面特征提取。對(duì)于機(jī)械零件模型,其初始參數(shù):N =25,=0101mm,=20°,T m in =100,本算法運(yùn)行時(shí)間為317s,結(jié)果見圖1(b ,每一種曲面類型用一種顏色表。Fandisk 模型的參數(shù):N =25,=0101mm,=10°,T m in =50,本算法運(yùn)行時(shí)間為0147s,結(jié)果見圖2(b

18、所示 。4結(jié)論從三角網(wǎng)格模型中提取二次曲面是曲面重建中的重要問題,是解決其它問題的先決條件,例如模式識(shí)別。本文作者使用基于RANS AC 算法提取二次曲面,通過實(shí)例證明該技術(shù)是提取二次曲面的有效方法。該算法具有如下優(yōu)勢(shì):算法原理簡(jiǎn)單;抗噪聲能力強(qiáng);可以提取多個(gè)二次曲面;算法運(yùn)行效率高。參考文獻(xiàn)【1】L A l ons o,F Cuny,S Petitjean,et al .The virtualmesh:a geometric abstracti on for efficiently computing radi osity J .AC M Trans .Graphics,2001,20(3:

19、169-20.【2】B Nourse,D Hakala,R H illyard,et al .Natural quad 2rics in mechanical design J .I n Pr oc .of Aut ofact W est,Anahei m ,1980(1:363-378.【3】V F Leavers .Survey W hich Hough Transf or m J .C V 2GI P:I m age Understanding,1993,58(2:250-264.【4】M A Fischler,R C Bolles .Random sa mp le consensus:

20、aparadig m f or model fitting with app licati ons t o i m age analy 2sis and aut omated cart ography J .AC M Commun,1981,24(6:381-395.【5】R Gerhard,D L M artin .Geometric Pri m itive Extracti onusing a Genetic A lgorith m J .I EEE Transacti ons on Pattern Analysis and Machine I ntelligence,1994,16(9:

21、901-905.【6】T Rabbani .Aut omatic reconstructi on of industrial installa 2ti ons D .Delft University of Technol ogy,2006.【7】C Thomas,G Francois .Extracting Cylinders in Full 3DData using a Random Sa mp ling Method and the Gaussian I m age C .I n:V isi on,Modelling and V isualizati ong,Stuttgart,2001:

22、21-23.【8】R W ahl,M Guthe,R Klein .I dentifying p lanes in point 2cl ouds for efficient hybrid rendering C .I n:The 13thPacific Conference on Computer Graphics and App lica 2ti ons,Macao,2005:12-14.【9】Chen Y H,L iu C Y .Quadric Surface Extracti on usingGenetic A lgorith m s J .Computer A ided Design,

23、1999,(31:101-110.【10】曲學(xué)軍,席平.使用Tabu 搜索技術(shù)提取二次曲面J .中國(guó)機(jī)械工程,2004,15(15:1350-1354.【11】神會(huì)存,周來水.基于離散曲率計(jì)算的三角網(wǎng)格模型優(yōu)化調(diào)整J .航空學(xué)報(bào),2006,27(2:318-324.【12】D Faugeras .Three di m ensi onal computer visi on:a geo 2metric viewpoint M .M I T Press,1993.【13】劉勝蘭,周儒榮,安魯陵.三角網(wǎng)格模型的數(shù)據(jù)分塊算法J .南京航空航天大學(xué)學(xué)報(bào),2003,35(6:653-658.(下轉(zhuǎn)第8頁(yè)根據(jù)

24、本文作者所提出的啟發(fā)式算法對(duì)各項(xiàng)制造任務(wù)進(jìn)行分析,得出滿足資源約束的各項(xiàng)任務(wù)的開始時(shí)間,如表2所示。表2工作開始時(shí)間T 挑選出的工作T =04、2、7T =43T =84T =106T =111根據(jù)各任務(wù)開始時(shí)間情況,對(duì)該中外翼A 墻的制造、裝配過程進(jìn)行搭接網(wǎng)絡(luò)計(jì)劃制定,得出搭接關(guān)系、搭接時(shí)距、相關(guān)時(shí)間參數(shù)。從而繪制出如圖5所示的單代號(hào)網(wǎng)絡(luò)計(jì)劃。 圖5A 墻制造的單代號(hào)網(wǎng)絡(luò)計(jì)劃4結(jié)束語(yǔ)本文作者針對(duì)國(guó)內(nèi)外在搭接網(wǎng)絡(luò)計(jì)劃中搭接關(guān)系和搭接時(shí)距處理上的不足,提出了基于優(yōu)先規(guī)則的啟發(fā)式網(wǎng)絡(luò)計(jì)劃制定方法,在最早開始時(shí)間的計(jì)算中動(dòng)態(tài)處理搭接關(guān)系,解決了資源約束下的制造項(xiàng)目網(wǎng)絡(luò)計(jì)劃制定問題,很好地滿足了實(shí)際需

25、求,為今后制造項(xiàng)目的計(jì)劃編制提供了有效的參考。參考文獻(xiàn)【1】楊冰.搭接網(wǎng)絡(luò)計(jì)劃模型分析J .北方交通大學(xué)學(xué)報(bào),2002,26(5:84-88.【2】M 1G 1S peranz,C 1Vercellis .H ierarchicalmodels for multi 2p r oject p lanning and scheduling J .Eur opean Journal of Operati onal Research,1993,64:312-325.【3】J 1Moder,C 1Philli p s,Davis,et al .Pr ojectM anage mentwith CP M

26、,PERT and Precedence D iagra mm ing,3rded M .B litz,1995.【4】劉永淞,黃明娜.矩陣法計(jì)算搭接施工網(wǎng)絡(luò)計(jì)劃J .基建優(yōu)化,2001,22(4:28-29.【5】楊冰.網(wǎng)絡(luò)計(jì)劃計(jì)算模型的統(tǒng)一J .系統(tǒng)工程理論與實(shí)踐,2002(3:51-55.【6】宇德明.計(jì)算搭接施工計(jì)劃時(shí)間參數(shù)新模型J .鐵道科學(xué)與工程學(xué)報(bào),2005,2(4:77-81.【7】盧向南.項(xiàng)目計(jì)劃與控制M .北京:機(jī)械工業(yè)出版社,2004.(上接第22頁(yè)律,提出了利用在磨削區(qū)內(nèi)磨削冷卻液的體積分?jǐn)?shù)的分布規(guī)律判斷磨削區(qū)冷卻液冷卻效果好壞的一種理論方法。由于冷卻液射流參數(shù)之間的綜

27、合作用決定流場(chǎng)的特性,所以有關(guān)內(nèi)容還需進(jìn)一步的實(shí)驗(yàn)研究?？傊?砂輪轉(zhuǎn)速、冷卻液的射流速度、射流角度及射流位置對(duì)冷卻液的冷卻效果都有一定影響。冷卻效果的好壞是由這些因素綜合作用決定。應(yīng)用氣液兩相流理論研究磨削冷卻液的體積分?jǐn)?shù)的分布規(guī)律,在此基礎(chǔ)上提出了利用在磨削區(qū)內(nèi)磨削冷卻液體積分?jǐn)?shù)的分布規(guī)律來判斷磨削液的冷卻效果好壞的一種理論方法,該方法不僅為準(zhǔn)干式磨削研究中在保證冷卻效果條件下尋找使用最少量的磨削液,提供理論依據(jù),而且可用于高速磨削智能化研究,對(duì)高速磨削過程磨削液冷卻效果的預(yù)測(cè)及高速磨削過程自適應(yīng)控制都具有一定的應(yīng)用價(jià)值。參考文獻(xiàn)【1】蔡光起,趙恒華,高興軍.高速高效磨削加工及其關(guān)鍵技術(shù)J .制造技術(shù)與機(jī)床,2004(11:42-45.【2】葛培琪,程建輝,欒芝云.磨削液磨削加工特性的研究J .潤(rùn)滑與密封,200