基于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基金項目:總裝備部預(yù)先研究項目資助(41318111117;航空科學(xué)基金資助項目(2008Z B55001作者簡介:劉元朋(1976,男,博士,講師,主要研究方向為反求工程、CAD /CA M 和工業(yè)I CT 成像。電話:135*,E -mail:drag on_ly psina 1co m 1cn 。基于RANS AC 算法的三角網(wǎng)格特征曲面提取劉元朋,陳良驥,趙輝(鄭州航空工業(yè)管理學(xué)院機(jī)電工程系,河南鄭州4500

2、15摘要:針對三角網(wǎng)格模型中的二次曲面提取問題,利用隨機(jī)抽樣一致性算法(Random Samp ling Consensus,RANS AC 提出了一種球面、圓柱面和圓錐面等二次特征曲面的提取算法。該算法首先計算每個頂點的法向量,然后用帶頂點法向量的三角面片統(tǒng)一表示每類二次曲面的最小子集,最后利用RANS AC 算法進(jìn)行二次曲面提取。實驗結(jié)果分析表明該算法具有良好的穩(wěn)定性和運算效率等特點。關(guān)鍵詞:隨機(jī)抽樣一致性算法;三角網(wǎng)格;二次曲面提取中圖分類號:TP391172文獻(xiàn)標(biāo)識碼:A 文章編號: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前言隨著激光測距掃描等三維數(shù)據(jù)采樣技術(shù)的進(jìn)步和硬件設(shè)備性能的提高,三角網(wǎng)格曲面正在逐漸成為計算機(jī)圖形學(xué)和幾何設(shè)計領(lǐng)域的新寵。三角網(wǎng)格模型作為一種對原始模型的線性逼近,被廣泛應(yīng)用于快速原型制造、醫(yī)用圖像、地理地形繪制、計算機(jī)游戲等許多應(yīng)用領(lǐng)域。但是,這種模型只有一階連續(xù),精度

7、不高,使用三角網(wǎng)格模型表示機(jī)械零件會損失零件模型的幾何信息和拓?fù)湫畔?使得設(shè)計者難以對零件模型進(jìn)行精確快速的分析。A l ons o 全面分析了產(chǎn)品反求建模的方法,并指出產(chǎn)品形面直接用低次參數(shù)曲面片(圓錐面、圓柱面、球面、比用傳統(tǒng)三角網(wǎng)格模型建模精確更高、計算更有效1。Nourse 指出85%的機(jī)械零件都可以用平面、圓錐面、球面和圓柱面來描述2。因此可靠地提取三角網(wǎng)格模型中的二次曲面是體現(xiàn)零件原始設(shè)計意圖反求建模的關(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ù),這意味著該方法在空間上很浪費,很難用到有兩個以上參數(shù)的幾何形狀提取,事實上,Hough 變換法主要用于直線等平面二次曲線的提取。Rabbani 等6利用圓柱面的高斯圖特性,將圓柱面的參數(shù)轉(zhuǎn)化為平面二次曲線參數(shù)的組合,進(jìn)而利用兩個Hough 變換進(jìn)行圓柱面參數(shù)提取。RANS A 方法的主要優(yōu)點是數(shù)學(xué)上形式化和較低的空間要求,后者同點的數(shù)量呈線性關(guān)系,而不是與參數(shù)數(shù)目成指數(shù)關(guān)系,這是對Hough 變換方法的顯著改善,使得多個自由參數(shù)的幾何元素提取變得容易一些。Thomas 等提出了利用RANS A 法進(jìn)行圓柱面提取7。W ahl 等利用RANS

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

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

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

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

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

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

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

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

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

18、所示 。4結(jié)論從三角網(wǎng)格模型中提取二次曲面是曲面重建中的重要問題,是解決其它問題的先決條件,例如模式識別。本文作者使用基于RANS AC 算法提取二次曲面,通過實例證明該技術(shù)是提取二次曲面的有效方法。該算法具有如下優(yōu)勢:算法原理簡單;抗噪聲能力強(qiáng);可以提取多個二次曲面;算法運行效率高。參考文獻(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 .中國機(jī)械工程,2004,15(15:1350-1354.【11】神會存,周來水.基于離散曲率計算的三角網(wǎng)格模型優(yōu)化調(diào)整J .航空學(xué)報,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é)報,2003,35(6:653-658.(下轉(zhuǎn)第8頁根據(jù)

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

25、求,為今后制造項目的計劃編制提供了有效的參考。參考文獻(xiàn)【1】楊冰.搭接網(wǎng)絡(luò)計劃模型分析J .北方交通大學(xué)學(xué)報,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】劉永淞,黃明娜.矩陣法計算搭接施工網(wǎng)絡(luò)計劃J .基建優(yōu)化,2001,22(4:28-29.【5】楊冰.網(wǎng)絡(luò)計劃計算模型的統(tǒng)一J .系統(tǒng)工程理論與實踐,2002(3:51-55.【6】宇德明.計算搭接施工計劃時間參數(shù)新模型J .鐵道科學(xué)與工程學(xué)報,2005,2(4:77-81.【7】盧向南.項目計劃與控制M .北京:機(jī)械工業(yè)出版社,2004.(上接第22頁律,提出了利用在磨削區(qū)內(nèi)磨削冷卻液的體積分?jǐn)?shù)的分布規(guī)律判斷磨削區(qū)冷卻液冷卻效果好壞的一種理論方法。由于冷卻液射流參數(shù)之間的綜

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