基于網(wǎng)格特征臨界點(diǎn)的三維工程模型檢索算法
摘要：隨著(zhù)計算機輔助設計(Computer Aided Design，CAD)技術(shù)和三維圖形硬件的不斷發(fā)展，專(zhuān)業(yè)化CAD軟件在工業(yè)中得到了廣泛使用。三維工程模型已成為工程分析和生產(chǎn)制造的基礎，是現代工程企業(yè)產(chǎn)品數據事實(shí)上的標準，為工程信息的構建、分析和重用提供了新的手段，大大提高了設計和制造的效率。由于產(chǎn)品結構越來(lái)越復雜，產(chǎn)品類(lèi)型不斷增加，需要設計的模型越來(lái)越多，造成工程三維模型爆炸式的增長(cháng)。統計顯示，在產(chǎn)品設計中只有20%的零部件是需要全新設計的，40%可以從現有設計中直接得到，剩下的40%可以從現有設計中修改得到;75%的新設計都需要參考已有的設計和知識口]。
現今許多企業(yè)正在建立企業(yè)內部的三維工程模型數據庫，方便了產(chǎn)品開(kāi)發(fā)人員及時(shí)有效地獲得所需的三維模型，加快了產(chǎn)品開(kāi)發(fā)的步伐。在客戶(hù)需求多樣化的今天，有效檢索并重用已有的三維模型及相關(guān)設計知識已成為實(shí)現產(chǎn)品快速研發(fā)、提高企業(yè)競爭力的重要手段。
傳統的檢索方式是將CAD模型中附帶的文件名、零部件數量或內容等信息作為關(guān)鍵詞進(jìn)行檢索，這種方法相對簡(jiǎn)單易行，但已不能滿(mǎn)足日益增長(cháng)的檢索需求 [z]。許多學(xué)者采用基于圖(graph)的方法對模型進(jìn)行檢索[3q]，并將其應用于基于實(shí)例的產(chǎn)品設計中。他們將零件本身的結構特征(如幾何、加工精度特征等)、工藝特征(如外圓、內孔、平面、槽等)及其相互間的關(guān)系提取出來(lái)用有向圖表示，進(jìn)而通過(guò)子圖同構來(lái)檢索需要的模型。這種方法有效地利用了零件自身的信息，與領(lǐng)域知識關(guān)聯(lián)緊密。但前提是必須對模型進(jìn)行特征識別，才能準確提取出模型的特征信息。由于不同商業(yè)CAD系統內部三維模型表示方法以及建模方式不同，阻礙了CAD系統問(wèn)的產(chǎn)品數據交換和模型共享。目前的通用加工特征識別算法不穩定，特征識別只能針對某種CAD系統單獨進(jìn)行二次開(kāi)發(fā)，工作量大，且缺乏通用性和一般性。況且子圖同構算法是NP難問(wèn)題，一旦零件復雜，對應的有向圖急劇膨脹，檢索效率將大大降低。
為此，本文提出一種與CAD系統無(wú)關(guān)的基于網(wǎng)格特征臨界點(diǎn)的三維工程模型檢索算法。該算法以三維模型的網(wǎng)格化表示作為檢索輸入，通過(guò)對網(wǎng)格模型的分析，找出表征網(wǎng)格形狀的關(guān)鍵點(diǎn)，即特征臨界點(diǎn)，以這些點(diǎn)為基礎計算三維模型的形狀度量，通過(guò)相似性比較，從模型數據庫中檢索出與輸入模型相似的模型。
1、原理與方法
1.1 Morse理論和網(wǎng)格特征臨界點(diǎn)
1934年，美國數學(xué)家M.Morse提出用分析方法研究空間拓撲性質(zhì)，即Morse理論[5]，成為微分拓撲學(xué)的一個(gè)重要分支�？臻g是幾何研究的對象，而函數是分析研究的對象。因此，定義于空間上的函數與空間的形狀有著(zhù)緊密的聯(lián)系。Morse理論正是研究空間上的函數與空間關(guān)系的，它特別關(guān)注的是函數的臨界點(diǎn)，并從臨界點(diǎn)的信息中獲取空間形狀的信息，即研究流形上光滑函數的臨界點(diǎn)與流形本身拓撲結構之間的關(guān)系。本文以Morse理論作為理論基礎，將網(wǎng)格模型映射為Morse臨界點(diǎn)的集合。
設MCR“為行維空間下的緊致流形，函數，：
M—R為作用在M上的一個(gè)光滑實(shí)值函數，在點(diǎn)P(越)∈M處建立局部坐標系，“=(U。，?，U。)，則：①如果函數廠(chǎng)在點(diǎn)P的梯度為零，即 3f/aU。一0，i∈[1，咒]，則P是函數，的臨界點(diǎn)。②如果P是函數，的臨界點(diǎn)，且，在P點(diǎn)處的Hessian矩陣日(，)(P;32，越)5(蠢女)非奇異，則P是Morse。$i界-A。
本文只考慮M是三角網(wǎng)格、函數廠(chǎng)是分段線(xiàn)性實(shí)值函數、且作用在網(wǎng)格M的頂點(diǎn)上的情況，三角面片內部的函數值可由頂點(diǎn)處的函數值插值得到。
假設對任意的邊<夕，Pz>∈M，均有廠(chǎng)(P，)≠廠(chǎng)(Pz)，可推知在任意三角面片內部，梯度都是恒定的非零實(shí)數，且I臨界點(diǎn)只出現在網(wǎng)格的頂點(diǎn)上[5]。
對于二維流形，Morse臨界點(diǎn)分為極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)三類(lèi)。若P為極小值點(diǎn)，則廠(chǎng)在P的/J,lI臺i域的各個(gè)方向均上升;若P為鞍點(diǎn)，則P 為廠(chǎng)在P的小臨域內上升下降轉換的過(guò)渡點(diǎn);若P為極大值點(diǎn)，則廠(chǎng)在P的小臨域的各個(gè)方向均下降。圖1表示了網(wǎng)格頂點(diǎn)P的分類(lèi)情況，其中圓圈表示與P相連的頂點(diǎn)可i，0表示f(v。)>廠(chǎng)(p)，e表示廠(chǎng)(讓)<廠(chǎng)(夕)。
1.2網(wǎng)格特征區域
Chang Ha Lee等人于2005年提出了網(wǎng)格特征區域(mesh saliency)的概念[6]。網(wǎng)格特征區域是對網(wǎng)格模型局部區域重要性的一種度量，即該網(wǎng)格模型局部區域能否體現網(wǎng)格形狀特點(diǎn)，其基本思想是函數，將模型表示為采樣點(diǎn)處函數值的概率分布。
計算網(wǎng)格頂點(diǎn)的平均曲率，并對其進(jìn)行高斯加權平該方法易于理解，實(shí)現簡(jiǎn)單，計算效率高，對網(wǎng)格退均(Gaussian-weighted average)，然后計算頂點(diǎn)的化的情況魯棒性好，但存在以下不足：
特征因子，以此對頂點(diǎn)進(jìn)行濾波，找出能體現網(wǎng)格模(1)由于該方法中采樣點(diǎn)的數量是一定的，不能型外形特點(diǎn)的區域。根據模型的形狀與復雜程度自適應地產(chǎn)生采樣點(diǎn)，本文結合網(wǎng)格特征區域和Morse理論，找出網(wǎng)特別針對工程模型，一些很重要的局部幾何特征(如格上表征網(wǎng)格局部形狀的特征臨界點(diǎn)，并以基于這槽、凸臺)很難被充分采樣，而對于平面特征往往被些臨界點(diǎn)之間的距離和角度值的統計規律作為形狀過(guò)采樣，因此采樣點(diǎn)不能很好地體現工程模型的形描述子，對網(wǎng)格進(jìn)行形狀比較。狀特點(diǎn)。
1.3基于形狀分布的圖形檢索算法
普林斯頓大學(xué)Robert Osada等人提出的基于形狀分布的方法(D2)E73是圖形檢索領(lǐng)域中十分重要的算法，其基本思想是：首先對模型進(jìn)行采樣，生成一系列的采樣點(diǎn)，然后通過(guò)作用在模型上的形狀(2)此算法采用單一形狀分布函數，即任意兩采樣點(diǎn)間的歐氏距離，雖然計算簡(jiǎn)單，但沒(méi)有充分利用模型的其他幾何信息，如三角面片和網(wǎng)格頂點(diǎn)處的法矢和曲率信息，所以單一的形狀分布函數很難充分反映出模型的外形特點(diǎn)，檢索結果差強人意。圖2所示為三個(gè)模型的比較結果，可以看出，雖然三個(gè)模型的外形差異很大，但通過(guò)此算法得到的形狀分布曲線(xiàn)是相似的�？梢�(jiàn)該方法并不能很好地區分這三種模型，此算法有待改進(jìn)和增強。
C.Y.IP等人根據任意兩點(diǎn)的連線(xiàn)與模型的位置關(guān)系，將距離分為In distances，Out distances和Mixed distances，改進(jìn)了D2算法，并用于比較CAD模型[8]，改進(jìn)方法較傳統的形狀分布算法有效，但計算過(guò)程復雜，計算量過(guò)大，實(shí)時(shí)性有待加強，且不能避免傳統形狀分布算法不足對檢索結果的影響。
2、基于特征臨界點(diǎn)的形狀檢索算法
為了克服傳統基于形狀分布檢索算法的不足，本文提出了基于特征臨界點(diǎn)的檢索算法。其基本思想是以三維工程網(wǎng)格模型作為輸入，通過(guò)分析網(wǎng)格頂點(diǎn)的離散法矢和平均曲率，找出表征其結構的特征臨界點(diǎn)，然后計算臨界點(diǎn)間的形狀函數值，并對其進(jìn)行概率統計，給出形狀分布圖，通過(guò)計算形狀分布相對于傳統算法，該算法的優(yōu)勢在于：
(1)用網(wǎng)格模型的特征臨界點(diǎn)代替傳統的采樣點(diǎn)進(jìn)行形狀函數計算，避免了采樣不足對算法造成的影響。根據Morse理論，特征臨界點(diǎn)反映了空間模型的拓撲幾何信息，且其對模型中有重要工程意義的結構敏感，因此比隨機生成的采樣點(diǎn)更能體現模型的結構特點(diǎn)，更具針對性。
(2)取網(wǎng)格益面上兩點(diǎn)間近似測地線(xiàn)距離與兩點(diǎn)處法矢夾角的余弦值作為聯(lián)合形狀函數，對函數值進(jìn)行概率統計，給出二維形狀函數分布圖。較之單一的形狀函數D2，近似測地距離更能表征模型表面形狀的變化，法矢夾角余弦反映了模型局部區域內形狀的分布，因此聯(lián)合形狀函數在兩個(gè)方面綜合考慮了模型的結構，更全面地反映出模型的外形特點(diǎn)。
(3)不計算任意兩點(diǎn)間的聯(lián)合形狀函數值，而是根據Morse理論，將II缶界點(diǎn)分為極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)，針對每類(lèi)臨界點(diǎn)計算聯(lián)合形狀函數值，模型的整體描述由三者加權平均得到。這樣提高了計算效率，使統計結果更具可比性，能夠更合理地描述模型結構。
2.1 網(wǎng)格微分量的計算
三角網(wǎng)格模型是一種離散曲面表示形式。法矢和曲率作為重要的微分幾何特性。描述了三角網(wǎng)格模型的局部幾何特征。由于離散形式的曲面是一種分片線(xiàn)性曲面，沒(méi)有連續的法矢和曲率，通常只考慮頂點(diǎn)處的法矢和曲率，其余各點(diǎn)的幾何特性可通過(guò)對頂點(diǎn)進(jìn)行線(xiàn)性插值獲得。近幾年來(lái)，眾多學(xué)者提出了一系列估算離散曲面微分量的新方法。浙江大學(xué)方惠蘭等人對國際上提出的三角網(wǎng)格曲面上估算平均曲率的七種方法和估算高斯曲率的四種方法進(jìn)行了總結和比較，指出2002年 Meyer等人提出的Voronoi方法對高斯曲率和平均曲率估算最優(yōu)砷]，因此本文將該方法擴展到頂點(diǎn)法矢的計算，并用其計算網(wǎng)格頂點(diǎn)的離散曲率。
Voronoi方法的基本思想是把光滑曲面看作是一族網(wǎng)格的極限或者線(xiàn)性逼近，把三角網(wǎng)格每個(gè)頂點(diǎn)的微分量看作是此三角網(wǎng)格在此頂點(diǎn)一個(gè)小鄰域的平均度量。與一般算法等同看待小鄰域內所有三角形不同，該算法根據小鄰域內三角形的不同類(lèi)型(銳角、直角和鈍角三角形)，分別采用不同的面積計算方法，更好地體現了面片上的微分量對頂點(diǎn)處微分量的影響。具體過(guò)程可參考文獻[10]。
圖4表示按照Voronoi方法計算得到的三個(gè)工程模型頂點(diǎn)處的離散曲率分布，顏色越深代表此處的曲率越大。2.2網(wǎng)格特征臨界點(diǎn)的計算根據 Morse理論，筆者首先取作用在網(wǎng)格模型上的實(shí)值函數廠(chǎng)為網(wǎng)格頂點(diǎn)p處的離散平均曲率H(p)與該點(diǎn)影響因子的代數和，則函數，的Morse臨界點(diǎn)體現了網(wǎng)格模型的空間拓撲幾何結構。
Morse臨界點(diǎn)的計算如下‘11。：
步驟1對每個(gè)頂點(diǎn)戶(hù)∈M，采用Voronoi方法計算其平均曲率H(p)。
步驟2計算頂點(diǎn)P對局部形狀的影響因子。
根據頂點(diǎn)P的鄰域對H(戶(hù))進(jìn)行加權平均，以此將頂點(diǎn)處的曲率與頂點(diǎn)的鄰域聯(lián)系起來(lái)，通過(guò)計算鄰域頂點(diǎn)間對局部形狀影響的差異，體現該頂點(diǎn)對局部形狀的重要性。采用雙向平滑算子(bilateralsmoothing operation)對H(戶(hù))進(jìn)行鄰域相關(guān)的加權平均。影響因子的計算如下：
B(H(戶(hù))，口)一[Σ(H(z)一H(夕))J∈F‘p·2a)W。(fI z—p J)w。(I H(z)一H(夕)1)]/[Σz∈F(p·2a)Wc(1l z—P 11)Ws(1 H(z)一H(戶(hù))})]。(1)其中，F(p，盯)為距離頂點(diǎn)戶(hù)在盯范圍內的頂點(diǎn)的集合;Wc(z)=exp[-一z2/(2口冬)]為標準高斯濾波函數，W。(z)=exp[一，/(2盯§)]為特征保持加權函數。
步驟3根據B(H(p)，盯)更新函數廠(chǎng)的值。
步驟4控制計算的迭代次數，控制最終得到的特征臨界點(diǎn)的數量。迭代次數越多，生成的特征臨界點(diǎn)的數量越少。
步驟5根據Morse臨界點(diǎn)的分類(lèi)，將得到的臨界點(diǎn)分為極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)。
上述過(guò)程的偽代碼如下：Procedure SalientCriticalPoints(M，d，iteration)輸入：M為三角網(wǎng)格模型，d為頂點(diǎn)鄰域半徑，iteration為迭代次數。
輸出：Sc為特征臨界點(diǎn)集合。
局部變量：N為M中頂點(diǎn)的數量，Pl為M中的第i個(gè)頂點(diǎn)，f(pi)為頂點(diǎn)pl處的實(shí)值函數值，a，為頂點(diǎn)Pl的影響因子。
Begin集合{P1)=M的所有頂點(diǎn);N一集合{Pl}的勢;for(j=1 to iteration)計算頂點(diǎn)P，處的平均曲率H(pO，令f(pi)=H(pi)lfor(i一1 to N)計算頂點(diǎn)pl的影響因子ai(M，f(pi)，d);更新f(Pi)+一8i;endend將得到的實(shí)值函數值{f(P1)}，利用Morse臨界點(diǎn)的定義判斷Pi的類(lèi)型，return網(wǎng)格特征臨界點(diǎn)集合Sc，end圖5是對3個(gè)零件網(wǎng)格模型進(jìn)行臨界點(diǎn)計算的結果，其中第一列是模型所有的臨界點(diǎn)，第二列是極大值點(diǎn)，第三列是極小值點(diǎn)，第四列是鞍點(diǎn)，圖片下方的數字表示此類(lèi)臨界點(diǎn)的數量。
2.3形狀函數
形狀函數定義了能夠表征模型形狀的幾何特征，通過(guò)計算臨界點(diǎn)處的函數值來(lái)反映模型的結構特點(diǎn)，因此形狀函數的選擇對提高算法的性能至關(guān)重要。傳統的 D2距離雖然計算簡(jiǎn)單，但并不足以反映模型的外形特點(diǎn)，因此檢索結果不理想。本文采用兩點(diǎn)間近似測地距離和兩點(diǎn)處法矢夾角余弦作為聯(lián)合形狀函數，近似測地距離反映了整個(gè)模型表面形狀的變化，法矢夾角余弦體現了模型局部區域形狀的分布。
(1)近似測地距離函數測地線(xiàn)在微分幾何中有著(zhù)嚴格的定義，即曲面上的一條曲線(xiàn)，如果它的每一點(diǎn)處的測地曲率為零，則稱(chēng)為測地線(xiàn)，在工程中可將其直觀(guān)理解為曲面上連接兩點(diǎn)的最短路徑。由于精確計算測地線(xiàn)算法復雜、時(shí)間復雜度較高，本文采用近似測地線(xiàn)，網(wǎng)格上組成近似測地線(xiàn)的所有小線(xiàn)段的歐式距離和即為近似測地距離。
本文采用Takashi Kanai等人提出的算法，計算網(wǎng)格上兩頂點(diǎn)間的近似測地路徑，其思想是首先將網(wǎng)格的頂點(diǎn)看作圖的節點(diǎn)，網(wǎng)格頂點(diǎn)間的連接看作圖的邊，采用計算圖最短路徑的Dijkstra算法獲得初始最短路徑，然后對此路徑所在的局部鄰域進(jìn)行網(wǎng)格細分，再對細分后的區域采用Dijkstra算法計算最短路徑，以此迭代，直至近似最短路徑的長(cháng)度變化小于預先設定的閾值。具體實(shí)現細節可參考文獻[12]。為了更快速地計算，本文采用最短路徑快速算法(Shortest Path Faster Algorithm，SPFA)代替Dijkstra算法[131。
由近似測地距離的定義可知，此形狀函數是平移、旋轉不變的，但因距離是對模型大小的一種度量，故是縮放可變的。圖6表示了從模型中某一臨界點(diǎn)到其余同類(lèi)臨界點(diǎn)間的近似測地路徑。
極大值點(diǎn)極小值點(diǎn)鞍點(diǎn)圖6網(wǎng)格模型l司類(lèi)臨界點(diǎn)同的近似測地路徑(2)頂點(diǎn)法矢夾角余弦定義NA為法矢夾角余弦，設臨界點(diǎn)p;，p，處的單位法矢分別為露，。和n，。，則由向量?jì)确e可得n以·n聲，==I刀以I×I n戶(hù);I×cosL(力以，n聲，)=》NA=cosL(肛p，np)一np·np。(2)因為在區間[o，丌]內余弦值是單調下降的，所以可以用來(lái)唯一度量?jì)墒噶康膴A角。由定義可知此形狀函數是平移、旋轉和縮放不變的。
2.4形狀分布矩陣
根據特征臨界點(diǎn)的類(lèi)型，分別計算每類(lèi)臨界點(diǎn)(即極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn))中兩兩頂點(diǎn)之間的聯(lián)合分布函數。因為特征點(diǎn)的類(lèi)型不同，其所表征的網(wǎng)格上局部區域的凸凹性不同，所以分類(lèi)型計算聯(lián)合分布函數使得到的形狀分布矩陣更具可比性，并且把計算聯(lián)合分布函數局限到每一類(lèi)中，比傳統的計算任意兩點(diǎn)間的形狀函數的計算量大大減少，效率更高。這樣做雖然忽略了兩組l臨界點(diǎn)間的拓撲關(guān)系，但因為本檢索算法本質(zhì)上是基于概率統計的，并且每類(lèi)臨界點(diǎn)的分布并沒(méi)有局限到某一區域，而是在模型整體上分布的，所以只要有足夠的臨界點(diǎn)，足夠的臨界點(diǎn)間形狀函數值，該模型的形狀特點(diǎn)就能通過(guò)概率統計反映出來(lái)。絕大多數情況下不同組內的函數值加權得到的統計規律已能很好地表現出模型的形狀分布規律。
計算每類(lèi)臨界點(diǎn)兩兩之間的測地線(xiàn)距離和法矢夾角余弦值。由于近似測地線(xiàn)距離函數是縮放可變的，要對其進(jìn)行歸一化處理，常用的方法有最大值歸一和平均值歸一�？紤]到最大值歸一易受噪聲數據影響，故采用平均值歸一化：設每一類(lèi)中計算得到近似測地距離的最大值為D……，平均值為D……，需要將距離 [o，D……]平均劃分為L(cháng)個(gè)單元，則將[o，n。]和[D……，D……]分別等分為L(cháng)。/2個(gè)單元，即得到平均值歸一化的分布。NA值域為[一 1，1]，設需要將其平分為L(cháng)，個(gè)單元。對每對臨界點(diǎn)的聯(lián)合形狀函數值進(jìn)行統計，可生成形狀分布矩陣MD=(z州)，×L√z。為近似測地距離￡屬于單元 i且NA屬于單元�！旱呐R界點(diǎn)對總數占所有臨界點(diǎn)對總數的比例。將P，NA，l：值分別對應z，Y，z軸，可得到聯(lián)合形狀函數的二維概率分布圖。
分別對三類(lèi)臨界點(diǎn)進(jìn)行上述計算得到三個(gè)矩陣，則一個(gè)網(wǎng)格模型即可抽象為三個(gè)聯(lián)合形狀分布矩陣的線(xiàn)性組合，即M=謝DIn。;+凸 MDmi。+7，MDs“。(3)其中：M為網(wǎng)格模型的形狀分布矩陣;MD加剃MDm"M腑a分別表示與極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)對應的形狀分布矩陣;a，J9，y分別表示三類(lèi)矩陣的系數，且滿(mǎn)足歸一化條件口+口+y=1。設N。，N。t。，N州分別表示模型中極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)的數量，本文取口5瓦i可吒而N’?盧一—Nma --1-N—minN-。}I_n-N,.a’
(4)圖7表示按照本算法得到的歸一化后的模型形狀分布。其中三維柱形圖分別表示了一個(gè)模型總體在極大值點(diǎn)集、極小值點(diǎn)集和鞍點(diǎn)集層次上的形狀分布。從圖中可以看出，分屬不同類(lèi)別的兩個(gè)模型，其形狀分布具有較大差異，因此本算法具有較好的區分能力。
圖7也比較了統一計算任意兩臨界點(diǎn)的形狀函數值和按組計算形狀函數值得到的模型形狀分布的差異。前者因用于統計的函數值大大增加，統計結果較分組計算的結果分布稍均勻一些，但最后得出的統計規律與分組計算形狀函數值并無(wú)本質(zhì)區別。平面著(zhù)色圖反映了在一個(gè)柱形圖中單元數值的分布情況，單元的顏色越亮，數值越大，可見(jiàn)同一模型的三個(gè)柱形圖內部數值分布規律并不相同，說(shuō)明了將特征臨界點(diǎn)分為三類(lèi)分別進(jìn)行計算的合理性。在工程模型中存在大量的相互之間成直角的面，形狀分布矩陣中的非零值會(huì )集中在表示180。，90。，o。的三行中(Y軸度量的是夾角的余弦值，分別對應Y軸的0，10，20)，針對該情況筆者進(jìn)行了專(zhuān)門(mén)的實(shí)驗。圖8說(shuō)明了分布在上述三行中的存在大量互成直角面的模型的形狀分布特點(diǎn)，它與存在其他分布特點(diǎn)的模型并無(wú)本質(zhì)不同。實(shí)驗證明，此類(lèi)模型的形狀函數值雖然主要分布在這三行中，但每一行的具體分布規律因模型不同而有所不同，因此本算法也能較好地區分其間的差別。
圖8大量存在互成直角面的模型及其形狀分布2.5形狀比較經(jīng)上述處理，模型的比較轉化為形狀分布矩陣的比較。本文仍然采用L。范數，即歐式距離計算兩矩陣間的距離。令MA=(m。)I，xL，B=(m6)f。×L。v M分別為模型A，B對應的形狀分布矩陣，則模型A，B間的距離為D(A，B)=D(MA，MB)一
3、算法復雜度分析
由算法過(guò)程可知，提取網(wǎng)格特征臨界點(diǎn)和計算近似測地距離是時(shí)間復雜度較高的兩個(gè)步驟。
3.1提取網(wǎng)格特征臨界點(diǎn)的時(shí)間復雜度
(1)網(wǎng)格微分量計算需計算每個(gè)三角面片的面積，最壞情況下，即每個(gè)三角面片為銳角三角形時(shí)，按照Voroini方法，一個(gè)三角面片的面積需計算三次(三次面積各不相同)。由于面積計算僅是單獨的乘法，與其他步驟相比，可認為此步驟的時(shí)間復雜度為常數。
(2)頂點(diǎn)影響因子計算最耗時(shí)部分為搜索任意頂點(diǎn)在某鄰域內的所有頂點(diǎn)。本文將頂點(diǎn)數據存入k-d樹(shù)來(lái)加速此過(guò)程。設網(wǎng)格頂點(diǎn)數為N，計算臨界點(diǎn)時(shí)的循環(huán)次數為艴，文獻[-14]中已證明，在一棵肛d樹(shù)中插入和搜索節點(diǎn)的平均時(shí)間復雜度為0(109：N)，故此步驟最終的時(shí)間復雜度為 o(nN·l092N)。
3.2計算近似測地距離的時(shí)間復雜度
本文采用SPFA算法計算從任意頂點(diǎn)到其余頂點(diǎn)的近似最短路徑。設網(wǎng)格模型的邊數為E，求得的所有臨界點(diǎn)數量為Nc，文獻E13]已證明，計算從任意點(diǎn)出發(fā)到所有頂點(diǎn)的近似最短距離的時(shí)間復雜度為0(E)，故此步驟最終的時(shí)間復雜度為o(Nc·E)。
4、算法驗證與討論
以Visual C++6.0為集成開(kāi)發(fā)環(huán)境，結合Matlab 6.5實(shí)現了本文提出的算法，并在普渡大學(xué)建立的工程標準模型庫ESB(engineering shapebenchmark)‘153上進(jìn)行了驗證。實(shí)驗采用PC機，AMD 2500+CPU，512 M內存。
ESB中包含866個(gè)STL格式的工程模型，筆者以其中任意一個(gè)模型作為輸入，欲檢索出模型庫中相似的模型，并與傳統圖形分布算法(D2 shape distribution)和增強圖形分布算法[16](D-IA shape distributionwith simplification)進(jìn)行了對比。本文描述的算法以模型的STL格式作為檢索輸入，實(shí)驗中的參數為L(cháng)，=64，L，=20;根據實(shí)驗結果，取盯=0.24%￡，￡為網(wǎng)格模型包圍盒對角線(xiàn)的長(cháng)度，并取UC一如一口，iteration一10。圖9列出了前五個(gè)檢索結果，其中的數字表示檢索到的模型與輸入模型的距離。從圖中可以看出，基于特征臨界點(diǎn)的算法能夠比另外兩種方法檢索出更多有效的模型，這是因為特征臨界點(diǎn)本身就是模型的頂點(diǎn)，由 Morse理論可知，臨界點(diǎn)表征了模型的空間拓撲結構和幾何結構，因此比基于采樣點(diǎn)的方法更能反映模型自身的特點(diǎn);且本算法采用的近似測地距離代替傳統的 D2距離，測地線(xiàn)本身就是對模型表面形狀的反映，其長(cháng)度亦體現了模型局部形狀的變化，用于做形狀函數效果較好，但其計算比D2距離要復雜。因此，鑒于對時(shí)間復雜度的考慮，近似測地距離是一種較好的折衷。
現對不同檢索輸入的檢索時(shí)間和有效性進(jìn)行統計，可得到算法的平均性能。針對ESB庫中的三大類(lèi)模型，即薄壁件、棱柱類(lèi)零件和旋轉件分別統計，將其綜合得到算法在整體ESB庫上的平均性能，做出查準率一查全率(Precision—Recall，PR)曲線(xiàn)，并與其他形狀檢索算法(表面積與體積描述 [151、角度分布直方圖[17‘、3D球諧描述子[18]、2D形狀直方圖[1?、光場(chǎng)描述子[20])進(jìn)行了比較，如圖10所示。
從PR曲線(xiàn)可以看出，本方法雖然目前還達不到光場(chǎng)描述子的效果，但它有效提高了傳統D2形狀分布算法的檢索性能，在計算復雜度和檢索效果之間找到了一種平衡。
對圖10的實(shí)驗數據進(jìn)行綜合，表1定量地比較了D2形狀分布、帶網(wǎng)格簡(jiǎn)化的D-IA形狀分布和本文算法的檢索精度和效率，FT，ST，NN的含義見(jiàn)參考文獻E16]。從中可以看出，基于特征臨界點(diǎn)的方法雖然總的檢索時(shí)間有所增加(主要是計算近似測地距離需時(shí)較多)，但仍在可接受的范圍內，且其檢索結果要明顯優(yōu)于另外兩種方法。
5、結束語(yǔ)
針對傳統基于形狀分布檢索算法的不足，提出了基于特征臨界點(diǎn)的檢索算法。該算法以三維工程網(wǎng)格模型作為輸入，以Morse臨界點(diǎn)理論為依據，用網(wǎng)格模型的特征臨界點(diǎn)代替傳統的采樣點(diǎn)進(jìn)行形狀函數計算，避免了采樣不足對算法造成的影響;取網(wǎng)格曲面上兩臨界點(diǎn)問(wèn)近似測地線(xiàn)距離與兩點(diǎn)處法矢夾角的余弦值作為聯(lián)合形狀函數，更好地表征了模型整體表面和局部區域的變化;分別針對極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)計算聯(lián)合形狀函數值，模型的整體描述由三者加權平均得到。實(shí)驗結果表明，本算法客觀(guān)反映了工程模型的相似程度，明顯提高了傳統圖形分布方法檢索的有效性。
以下幾項工作在未來(lái)研究中應該著(zhù)重加強：①本文算法的時(shí)間效率雖然可以接受，但還有很大的提升余地來(lái)找到效率更高的近似測地距離算法。②采用歐拉距離計算兩矩陣間的距離存在缺點(diǎn)。形狀矩陣中的每一列(行)代表一形狀度量向量，不同度量向量對于區分形狀有著(zhù)不同的重要性，而歐拉距離將矩陣不同列(行)之問(wèn)的差別等同看待，因此最終的距離只反映了平均綜合的結果，不能表示出某一形狀度最向量對總體差異的影響。這樣導致了兩矩陣即使距離較近，但其代表的圖形可能并不相似。
因此可以嘗試其他的度量方法，從而不僅反映矩陣間的距離，而且能體現矩陣自身的分布。③由于特征臨界點(diǎn)體現了模型局部的形狀信息，可以考慮將其用于局部形狀檢索。
【基于網(wǎng)格特征臨界點(diǎn)的三維工程模型檢索算法】相關(guān)文章：
基于智能優(yōu)化算法的Wiener模型辨識論文提綱12-05
淺談基于質(zhì)量技術(shù)特征改善率的并行優(yōu)化模型分析論文03-09
基于QBASIC環(huán)境下的數學(xué)算法教學(xué)11-14
基于滾動(dòng)計劃的動(dòng)態(tài)企業(yè)資源優(yōu)化模型03-29
基于勝任力模型的組織生涯管理探析12-12
《基于導納的圖像加密算法的研究》開(kāi)題報告12-03
基于教學(xué)知識點(diǎn)的模型框架與結構分析12-05
淺談基于知識的網(wǎng)格技術(shù)應用研究11-20
- 相關(guān)推薦