基于網(wǎng)格特征臨界點(diǎn)的三維工程模型檢索算法

　　摘要：隨著計(jì)算機(jī)輔助設(shè)計(jì)(Computer Aided Design，CAD)技術(shù)和三維圖形硬件的不斷發(fā)展，專業(yè)化CAD軟件在工業(yè)中得到了廣泛使用。三維工程模型已成為工程分析和生產(chǎn)制造的基礎(chǔ)，是現(xiàn)代工程企業(yè)產(chǎn)品數(shù)據(jù)事實(shí)上的標(biāo)準(zhǔn)，為工程信息的構(gòu)建、分析和重用提供了新的手段，大大提高了設(shè)計(jì)和制造的效率。由于產(chǎn)品結(jié)構(gòu)越來(lái)越復(fù)雜，產(chǎn)品類型不斷增加，需要設(shè)計(jì)的模型越來(lái)越多，造成工程三維模型爆炸式的增長(zhǎng)。統(tǒng)計(jì)顯示，在產(chǎn)品設(shè)計(jì)中只有20%的零部件是需要全新設(shè)計(jì)的，40%可以從現(xiàn)有設(shè)計(jì)中直接得到，剩下的40%可以從現(xiàn)有設(shè)計(jì)中修改得到;75%的新設(shè)計(jì)都需要參考已有的設(shè)計(jì)和知識(shí)口]。

　　現(xiàn)今許多企業(yè)正在建立企業(yè)內(nèi)部的三維工程模型數(shù)據(jù)庫(kù)，方便了產(chǎn)品開發(fā)人員及時(shí)有效地獲得所需的三維模型，加快了產(chǎn)品開發(fā)的步伐。在客戶需求多樣化的今天，有效檢索并重用已有的三維模型及相關(guān)設(shè)計(jì)知識(shí)已成為實(shí)現(xiàn)產(chǎn)品快速研發(fā)、提高企業(yè)競(jìng)爭(zhēng)力的重要手段。

　　傳統(tǒng)的檢索方式是將CAD模型中附帶的文件名、零部件數(shù)量或內(nèi)容等信息作為關(guān)鍵詞進(jìn)行檢索，這種方法相對(duì)簡(jiǎn)單易行，但已不能滿足日益增長(zhǎng)的檢索需求 [z]。許多學(xué)者采用基于圖(graph)的方法對(duì)模型進(jìn)行檢索[3q]，并將其應(yīng)用于基于實(shí)例的產(chǎn)品設(shè)計(jì)中。他們將零件本身的結(jié)構(gòu)特征(如幾何、加工精度特征等)、工藝特征(如外圓、內(nèi)孔、平面、槽等)及其相互間的關(guān)系提取出來(lái)用有向圖表示，進(jìn)而通過(guò)子圖同構(gòu)來(lái)檢索需要的模型。這種方法有效地利用了零件自身的信息，與領(lǐng)域知識(shí)關(guān)聯(lián)緊密。但前提是必須對(duì)模型進(jìn)行特征識(shí)別，才能準(zhǔn)確提取出模型的特征信息。由于不同商業(yè)CAD系統(tǒng)內(nèi)部三維模型表示方法以及建模方式不同，阻礙了CAD系統(tǒng)問(wèn)的產(chǎn)品數(shù)據(jù)交換和模型共享。目前的通用加工特征識(shí)別算法不穩(wěn)定，特征識(shí)別只能針對(duì)某種CAD系統(tǒng)單獨(dú)進(jìn)行二次開發(fā)，工作量大，且缺乏通用性和一般性。況且子圖同構(gòu)算法是NP難問(wèn)題，一旦零件復(fù)雜，對(duì)應(yīng)的有向圖急劇膨脹，檢索效率將大大降低。

　　為此，本文提出一種與CAD系統(tǒng)無(wú)關(guān)的基于網(wǎng)格特征臨界點(diǎn)的三維工程模型檢索算法。該算法以三維模型的網(wǎng)格化表示作為檢索輸入，通過(guò)對(duì)網(wǎng)格模型的分析，找出表征網(wǎng)格形狀的關(guān)鍵點(diǎn)，即特征臨界點(diǎn)，以這些點(diǎn)為基礎(chǔ)計(jì)算三維模型的形狀度量，通過(guò)相似性比較，從模型數(shù)據(jù)庫(kù)中檢索出與輸入模型相似的模型。

　　1、原理與方法

　　1.1 Morse理論和網(wǎng)格特征臨界點(diǎn)

　　1934年，美國(guó)數(shù)學(xué)家M.Morse提出用分析方法研究空間拓?fù)湫再|(zhì)，即Morse理論[5]，成為微分拓?fù)鋵W(xué)的一個(gè)重要分支。空間是幾何研究的對(duì)象，而函數(shù)是分析研究的對(duì)象。因此，定義于空間上的函數(shù)與空間的形狀有著緊密的聯(lián)系。Morse理論正是研究空間上的函數(shù)與空間關(guān)系的，它特別關(guān)注的是函數(shù)的臨界點(diǎn)，并從臨界點(diǎn)的信息中獲取空間形狀的信息，即研究流形上光滑函數(shù)的臨界點(diǎn)與流形本身拓?fù)浣Y(jié)構(gòu)之間的關(guān)系。本文以Morse理論作為理論基礎(chǔ)，將網(wǎng)格模型映射為Morse臨界點(diǎn)的集合。

　　設(shè)MCR“為行維空間下的緊致流形，函數(shù)，：

　　M—R為作用在M上的一個(gè)光滑實(shí)值函數(shù)，在點(diǎn)P(越)∈M處建立局部坐標(biāo)系，“=(U。，?，U。)，則：①如果函數(shù)廠在點(diǎn)P的梯度為零，即 3f/aU。一0，i∈[1，咒]，則P是函數(shù)，的臨界點(diǎn)。②如果P是函數(shù)，的臨界點(diǎn)，且，在P點(diǎn)處的Hessian矩陣日(，)(P;32，越)5(蠢女)非奇異，則P是Morse。$i界-A。

　　本文只考慮M是三角網(wǎng)格、函數(shù)廠是分段線性實(shí)值函數(shù)、且作用在網(wǎng)格M的頂點(diǎn)上的情況，三角面片內(nèi)部的函數(shù)值可由頂點(diǎn)處的函數(shù)值插值得到。

　　假設(shè)對(duì)任意的邊<夕，Pz>∈M，均有廠(P，)≠廠(Pz)，可推知在任意三角面片內(nèi)部，梯度都是恒定的非零實(shí)數(shù)，且I臨界點(diǎn)只出現(xiàn)在網(wǎng)格的頂點(diǎn)上[5]。

　　對(duì)于二維流形，Morse臨界點(diǎn)分為極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)三類。若P為極小值點(diǎn)，則廠在P的/J,lI臺(tái)i域的各個(gè)方向均上升;若P為鞍點(diǎn)，則P 為廠在P的小臨域內(nèi)上升下降轉(zhuǎn)換的過(guò)渡點(diǎn);若P為極大值點(diǎn)，則廠在P的小臨域的各個(gè)方向均下降。圖1表示了網(wǎng)格頂點(diǎn)P的分類情況，其中圓圈表示與P相連的頂點(diǎn)可i，0表示f(v。)>廠(p)，e表示廠(讓)<廠(夕)。

　　1.2網(wǎng)格特征區(qū)域

　　Chang Ha Lee等人于2005年提出了網(wǎng)格特征區(qū)域(mesh saliency)的概念[6]。網(wǎng)格特征區(qū)域是對(duì)網(wǎng)格模型局部區(qū)域重要性的一種度量，即該網(wǎng)格模型局部區(qū)域能否體現(xiàn)網(wǎng)格形狀特點(diǎn)，其基本思想是函數(shù)，將模型表示為采樣點(diǎn)處函數(shù)值的概率分布。

　　計(jì)算網(wǎng)格頂點(diǎn)的平均曲率，并對(duì)其進(jìn)行高斯加權(quán)平該方法易于理解，實(shí)現(xiàn)簡(jiǎn)單，計(jì)算效率高，對(duì)網(wǎng)格退均(Gaussian-weighted average)，然后計(jì)算頂點(diǎn)的化的情況魯棒性好，但存在以下不足：

　　特征因子，以此對(duì)頂點(diǎn)進(jìn)行濾波，找出能體現(xiàn)網(wǎng)格模(1)由于該方法中采樣點(diǎn)的數(shù)量是一定的，不能型外形特點(diǎn)的區(qū)域。根據(jù)模型的形狀與復(fù)雜程度自適應(yīng)地產(chǎn)生采樣點(diǎn)，本文結(jié)合網(wǎng)格特征區(qū)域和Morse理論，找出網(wǎng)特別針對(duì)工程模型，一些很重要的局部幾何特征(如格上表征網(wǎng)格局部形狀的特征臨界點(diǎn)，并以基于這槽、凸臺(tái))很難被充分采樣，而對(duì)于平面特征往往被些臨界點(diǎn)之間的距離和角度值的統(tǒng)計(jì)規(guī)律作為形狀過(guò)采樣，因此采樣點(diǎn)不能很好地體現(xiàn)工程模型的形描述子，對(duì)網(wǎng)格進(jìn)行形狀比較。狀特點(diǎn)。

　　1.3基于形狀分布的圖形檢索算法

　　普林斯頓大學(xué)Robert Osada等人提出的基于形狀分布的方法(D2)E73是圖形檢索領(lǐng)域中十分重要的算法，其基本思想是：首先對(duì)模型進(jìn)行采樣，生成一系列的采樣點(diǎn)，然后通過(guò)作用在模型上的形狀(2)此算法采用單一形狀分布函數(shù)，即任意兩采樣點(diǎn)間的歐氏距離，雖然計(jì)算簡(jiǎn)單，但沒(méi)有充分利用模型的其他幾何信息，如三角面片和網(wǎng)格頂點(diǎn)處的法矢和曲率信息，所以單一的形狀分布函數(shù)很難充分反映出模型的外形特點(diǎn)，檢索結(jié)果差強(qiáng)人意。圖2所示為三個(gè)模型的比較結(jié)果，可以看出，雖然三個(gè)模型的外形差異很大，但通過(guò)此算法得到的形狀分布曲線是相似的。可見該方法并不能很好地區(qū)分這三種模型，此算法有待改進(jìn)和增強(qiáng)。

　　C.Y.IP等人根據(jù)任意兩點(diǎn)的連線與模型的位置關(guān)系，將距離分為In distances，Out distances和Mixed distances，改進(jìn)了D2算法，并用于比較CAD模型[8]，改進(jìn)方法較傳統(tǒng)的形狀分布算法有效，但計(jì)算過(guò)程復(fù)雜，計(jì)算量過(guò)大，實(shí)時(shí)性有待加強(qiáng)，且不能避免傳統(tǒng)形狀分布算法不足對(duì)檢索結(jié)果的影響。

　　2、基于特征臨界點(diǎn)的形狀檢索算法

　　為了克服傳統(tǒng)基于形狀分布檢索算法的不足，本文提出了基于特征臨界點(diǎn)的檢索算法。其基本思想是以三維工程網(wǎng)格模型作為輸入，通過(guò)分析網(wǎng)格頂點(diǎn)的離散法矢和平均曲率，找出表征其結(jié)構(gòu)的特征臨界點(diǎn)，然后計(jì)算臨界點(diǎn)間的形狀函數(shù)值，并對(duì)其進(jìn)行概率統(tǒng)計(jì)，給出形狀分布圖，通過(guò)計(jì)算形狀分布相對(duì)于傳統(tǒng)算法，該算法的優(yōu)勢(shì)在于：

　　(1)用網(wǎng)格模型的特征臨界點(diǎn)代替?zhèn)鹘y(tǒng)的采樣點(diǎn)進(jìn)行形狀函數(shù)計(jì)算，避免了采樣不足對(duì)算法造成的影響。根據(jù)Morse理論，特征臨界點(diǎn)反映了空間模型的拓?fù)鋷缀涡畔�，且其�?duì)模型中有重要工程意義的結(jié)構(gòu)敏感，因此比隨機(jī)生成的采樣點(diǎn)更能體現(xiàn)模型的結(jié)構(gòu)特點(diǎn)，更具針對(duì)性。

　　(2)取網(wǎng)格益面上兩點(diǎn)間近似測(cè)地線距離與兩點(diǎn)處法矢夾角的余弦值作為聯(lián)合形狀函數(shù)，對(duì)函數(shù)值進(jìn)行概率統(tǒng)計(jì)，給出二維形狀函數(shù)分布圖。較之單一的形狀函數(shù)D2，近似測(cè)地距離更能表征模型表面形狀的變化，法矢夾角余弦反映了模型局部區(qū)域內(nèi)形狀的分布，因此聯(lián)合形狀函數(shù)在兩個(gè)方面綜合考慮了模型的結(jié)構(gòu)，更全面地反映出模型的外形特點(diǎn)。

　　(3)不計(jì)算任意兩點(diǎn)間的聯(lián)合形狀函數(shù)值，而是根據(jù)Morse理論，將II缶界點(diǎn)分為極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)，針對(duì)每類臨界點(diǎn)計(jì)算聯(lián)合形狀函數(shù)值，模型的整體描述由三者加權(quán)平均得到。這樣提高了計(jì)算效率，使統(tǒng)計(jì)結(jié)果更具可比性，能夠更合理地描述模型結(jié)構(gòu)。

　　2.1 網(wǎng)格微分量的計(jì)算

　　三角網(wǎng)格模型是一種離散曲面表示形式。法矢和曲率作為重要的微分幾何特性。描述了三角網(wǎng)格模型的局部幾何特征。由于離散形式的曲面是一種分片線性曲面，沒(méi)有連續(xù)的法矢和曲率，通常只考慮頂點(diǎn)處的法矢和曲率，其余各點(diǎn)的幾何特性可通過(guò)對(duì)頂點(diǎn)進(jìn)行線性插值獲得。近幾年來(lái)，眾多學(xué)者提出了一系列估算離散曲面微分量的新方法。浙江大學(xué)方惠蘭等人對(duì)國(guó)際上提出的三角網(wǎng)格曲面上估算平均曲率的七種方法和估算高斯曲率的四種方法進(jìn)行了總結(jié)和比較，指出2002年 Meyer等人提出的Voronoi方法對(duì)高斯曲率和平均曲率估算最優(yōu)砷]，因此本文將該方法擴(kuò)展到頂點(diǎn)法矢的計(jì)算，并用其計(jì)算網(wǎng)格頂點(diǎn)的離散曲率。

　　Voronoi方法的基本思想是把光滑曲面看作是一族網(wǎng)格的極限或者線性逼近，把三角網(wǎng)格每個(gè)頂點(diǎn)的微分量看作是此三角網(wǎng)格在此頂點(diǎn)一個(gè)小鄰域的平均度量。與一般算法等同看待小鄰域內(nèi)所有三角形不同，該算法根據(jù)小鄰域內(nèi)三角形的不同類型(銳角、直角和鈍角三角形)，分別采用不同的面積計(jì)算方法，更好地體現(xiàn)了面片上的微分量對(duì)頂點(diǎn)處微分量的影響。具體過(guò)程可參考文獻(xiàn)[10]。

　　圖4表示按照Voronoi方法計(jì)算得到的三個(gè)工程模型頂點(diǎn)處的離散曲率分布，顏色越深代表此處的曲率越大。2.2網(wǎng)格特征臨界點(diǎn)的計(jì)算根據(jù) Morse理論，筆者首先取作用在網(wǎng)格模型上的實(shí)值函數(shù)廠為網(wǎng)格頂點(diǎn)p處的離散平均曲率H(p)與該點(diǎn)影響因子的代數(shù)和，則函數(shù)，的Morse臨界點(diǎn)體現(xiàn)了網(wǎng)格模型的空間拓?fù)鋷缀谓Y(jié)構(gòu)。

　　Morse臨界點(diǎn)的計(jì)算如下‘11。：

　　步驟1對(duì)每個(gè)頂點(diǎn)戶∈M，采用Voronoi方法計(jì)算其平均曲率H(p)。

　　步驟2計(jì)算頂點(diǎn)P對(duì)局部形狀的影響因子。

　　根據(jù)頂點(diǎn)P的鄰域?qū)�H(戶)進(jìn)行加權(quán)平均，以此將頂點(diǎn)處的曲率與頂點(diǎn)的鄰域聯(lián)系起來(lái)，通過(guò)計(jì)算鄰域頂點(diǎn)間對(duì)局部形狀影響的差異，體現(xiàn)該頂點(diǎn)對(duì)局部形狀的重要性。采用雙向平滑算子(bilateralsmoothing operation)對(duì)H(戶)進(jìn)行鄰域相關(guān)的加權(quán)平均。影響因子的計(jì)算如下：

　　B(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(戶)})]。(1)其中，F(xiàn)(p，盯)為距離頂點(diǎn)戶在盯范圍內(nèi)的頂點(diǎn)的集合;Wc(z)=exp[-一z2/(2口冬)]為標(biāo)準(zhǔn)高斯濾波函數(shù)，W。(z)=exp[一，/(2盯§)]為特征保持加權(quán)函數(shù)。

　　步驟3根據(jù)B(H(p)，盯)更新函數(shù)廠的值。

　　步驟4控制計(jì)算的迭代次數(shù)，控制最終得到的特征臨界點(diǎn)的數(shù)量。迭代次數(shù)越多，生成的特征臨界點(diǎn)的數(shù)量越少。

　　步驟5根據(jù)Morse臨界點(diǎn)的分類，將得到的臨界點(diǎn)分為極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)。

　　上述過(guò)程的偽代碼如下：Procedure SalientCriticalPoints(M，d，iteration)輸入：M為三角網(wǎng)格模型，d為頂點(diǎn)鄰域半徑，iteration為迭代次數(shù)。

　　輸出：Sc為特征臨界點(diǎn)集合。

　　局部變量：N為M中頂點(diǎn)的數(shù)量，Pl為M中的第i個(gè)頂點(diǎn)，f(pi)為頂點(diǎn)pl處的實(shí)值函數(shù)值，a，為頂點(diǎn)Pl的影響因子。

　　Begin集合{P1)=M的所有頂點(diǎn);N一集合{Pl}的勢(shì);for(j=1 to iteration)計(jì)算頂點(diǎn)P，處的平均曲率H(pO，令f(pi)=H(pi)lfor(i一1 to N)計(jì)算頂點(diǎn)pl的影響因子ai(M，f(pi)，d);更新f(Pi)+一8i;endend將得到的實(shí)值函數(shù)值{f(P1)}，利用Morse臨界點(diǎn)的定義判斷Pi的類型，return網(wǎng)格特征臨界點(diǎn)集合Sc，end圖5是對(duì)3個(gè)零件網(wǎng)格模型進(jìn)行臨界點(diǎn)計(jì)算的結(jié)果，其中第一列是模型所有的臨界點(diǎn)，第二列是極大值點(diǎn)，第三列是極小值點(diǎn)，第四列是鞍點(diǎn)，圖片下方的數(shù)字表示此類臨界點(diǎn)的數(shù)量。

　　2.3形狀函數(shù)

　　形狀函數(shù)定義了能夠表征模型形狀的幾何特征，通過(guò)計(jì)算臨界點(diǎn)處的函數(shù)值來(lái)反映模型的結(jié)構(gòu)特點(diǎn)，因此形狀函數(shù)的選擇對(duì)提高算法的性能至關(guān)重要。傳統(tǒng)的 D2距離雖然計(jì)算簡(jiǎn)單，但并不足以反映模型的外形特點(diǎn)，因此檢索結(jié)果不理想。本文采用兩點(diǎn)間近似測(cè)地距離和兩點(diǎn)處法矢夾角余弦作為聯(lián)合形狀函數(shù)，近似測(cè)地距離反映了整個(gè)模型表面形狀的變化，法矢夾角余弦體現(xiàn)了模型局部區(qū)域形狀的分布。

　　(1)近似測(cè)地距離函數(shù)測(cè)地線在微分幾何中有著嚴(yán)格的定義，即曲面上的一條曲線，如果它的每一點(diǎn)處的測(cè)地曲率為零，則稱為測(cè)地線，在工程中可將其直觀理解為曲面上連接兩點(diǎn)的最短路徑。由于精確計(jì)算測(cè)地線算法復(fù)雜、時(shí)間復(fù)雜度較高，本文采用近似測(cè)地線，網(wǎng)格上組成近似測(cè)地線的所有小線段的歐式距離和即為近似測(cè)地距離。

　　本文采用Takashi Kanai等人提出的算法，計(jì)算網(wǎng)格上兩頂點(diǎn)間的近似測(cè)地路徑，其思想是首先將網(wǎng)格的頂點(diǎn)看作圖的節(jié)點(diǎn)，網(wǎng)格頂點(diǎn)間的連接看作圖的邊，采用計(jì)算圖最短路徑的Dijkstra算法獲得初始最短路徑，然后對(duì)此路徑所在的局部鄰域進(jìn)行網(wǎng)格細(xì)分，再對(duì)細(xì)分后的區(qū)域采用Dijkstra算法計(jì)算最短路徑，以此迭代，直至近似最短路徑的長(zhǎng)度變化小于預(yù)先設(shè)定的閾值。具體實(shí)現(xiàn)細(xì)節(jié)可參考文獻(xiàn)[12]。為了更快速地計(jì)算，本文采用最短路徑快速算法(Shortest Path Faster Algorithm，SPFA)代替Dijkstra算法[131。

　　由近似測(cè)地距離的定義可知，此形狀函數(shù)是平移、旋轉(zhuǎn)不變的，但因距離是對(duì)模型大小的一種度量，故是縮放可變的。圖6表示了從模型中某一臨界點(diǎn)到其余同類臨界點(diǎn)間的近似測(cè)地路徑。

　　極大值點(diǎn)極小值點(diǎn)鞍點(diǎn)圖6網(wǎng)格模型l司類臨界點(diǎn)同的近似測(cè)地路徑(2)頂點(diǎn)法矢夾角余弦定義NA為法矢夾角余弦，設(shè)臨界點(diǎn)p;，p，處的單位法矢分別為露，。和n，。，則由向量?jī)?nèi)積可得n以·n聲，==I刀以I×I n戶;I×cosL(力以，n聲，)=》NA=cosL(肛p，np)一np·np。(2)因?yàn)樵趨^(qū)間[o，丌]內(nèi)余弦值是單調(diào)下降的，所以可以用來(lái)唯一度量?jī)墒噶康膴A角。由定義可知此形狀函數(shù)是平移、旋轉(zhuǎn)和縮放不變的。

　　2.4形狀分布矩陣

　　根據(jù)特征臨界點(diǎn)的類型，分別計(jì)算每類臨界點(diǎn)(即極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn))中兩兩頂點(diǎn)之間的聯(lián)合分布函數(shù)。因?yàn)樘卣鼽c(diǎn)的類型不同，其所表征的網(wǎng)格上局部區(qū)域的凸凹性不同，所以分類型計(jì)算聯(lián)合分布函數(shù)使得到的形狀分布矩陣更具可比性，并且把計(jì)算聯(lián)合分布函數(shù)局限到每一類中，比傳統(tǒng)的計(jì)算任意兩點(diǎn)間的形狀函數(shù)的計(jì)算量大大減少，效率更高。這樣做雖然忽略了兩組l臨界點(diǎn)間的拓?fù)潢P(guān)系，但因?yàn)楸緳z索算法本質(zhì)上是基于概率統(tǒng)計(jì)的，并且每類臨界點(diǎn)的分布并沒(méi)有局限到某一區(qū)域，而是在模型整體上分布的，所以只要有足夠的臨界點(diǎn)，足夠的臨界點(diǎn)間形狀函數(shù)值，該模型的形狀特點(diǎn)就能通過(guò)概率統(tǒng)計(jì)反映出來(lái)。絕大多數(shù)情況下不同組內(nèi)的函數(shù)值加權(quán)得到的統(tǒng)計(jì)規(guī)律已能很好地表現(xiàn)出模型的形狀分布規(guī)律。

　　計(jì)算每類臨界點(diǎn)兩兩之間的測(cè)地線距離和法矢夾角余弦值。由于近似測(cè)地線距離函數(shù)是縮放可變的，要對(duì)其進(jìn)行歸一化處理，常用的方法有最大值歸一和平均值歸一。考慮到最大值歸一易受噪聲數(shù)據(jù)影響，故采用平均值歸一化：設(shè)每一類中計(jì)算得到近似測(cè)地距離的最大值為D……，平均值為D……，需要將距離 [o，D……]平均劃分為L(zhǎng)個(gè)單元，則將[o，n。]和[D……，D……]分別等分為L(zhǎng)。/2個(gè)單元，即得到平均值歸一化的分布。NA值域?yàn)閇一 1，1]，設(shè)需要將其平分為L(zhǎng)，個(gè)單元。對(duì)每對(duì)臨界點(diǎn)的聯(lián)合形狀函數(shù)值進(jìn)行統(tǒng)計(jì)，可生成形狀分布矩陣MD=(z州)，×L√z。為近似測(cè)地距離￡屬于單元 i且NA屬于單元�！旱呐R界點(diǎn)對(duì)總數(shù)占所有臨界點(diǎn)對(duì)總數(shù)的比例。將P，NA，l：值分別對(duì)應(yīng)z，Y，z軸，可得到聯(lián)合形狀函數(shù)的二維概率分布圖。

　　分別對(duì)三類臨界點(diǎn)進(jìn)行上述計(jì)算得到三個(gè)矩陣，則一個(gè)網(wǎng)格模型即可抽象為三個(gè)聯(lián)合形狀分布矩陣的線性組合，即M=謝DIn。;+凸 MDmi。+7，MDs“。(3)其中：M為網(wǎng)格模型的形狀分布矩陣;MD加剃MDm"M腑a分別表示與極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)對(duì)應(yīng)的形狀分布矩陣;a，J9，y分別表示三類矩陣的系數(shù)，且滿足歸一化條件口+口+y=1。設(shè)N。，N。t。，N州分別表示模型中極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)的數(shù)量，本文取口5瓦i可吒而N’?盧一—Nma --1-N—minN-。}I_n-N,.a’

　　(4)圖7表示按照本算法得到的歸一化后的模型形狀分布。其中三維柱形圖分別表示了一個(gè)模型總體在極大值點(diǎn)集、極小值點(diǎn)集和鞍點(diǎn)集層次上的形狀分布。從圖中可以看出，分屬不同類別的兩個(gè)模型，其形狀分布具有較大差異，因此本算法具有較好的區(qū)分能力。

　　圖7也比較了統(tǒng)一計(jì)算任意兩臨界點(diǎn)的形狀函數(shù)值和按組計(jì)算形狀函數(shù)值得到的模型形狀分布的差異。前者因用于統(tǒng)計(jì)的函數(shù)值大大增加，統(tǒng)計(jì)結(jié)果較分組計(jì)算的結(jié)果分布稍均勻一些，但最后得出的統(tǒng)計(jì)規(guī)律與分組計(jì)算形狀函數(shù)值并無(wú)本質(zhì)區(qū)別。平面著色圖反映了在一個(gè)柱形圖中單元數(shù)值的分布情況，單元的顏色越亮，數(shù)值越大，可見同一模型的三個(gè)柱形圖內(nèi)部數(shù)值分布規(guī)律并不相同，說(shuō)明了將特征臨界點(diǎn)分為三類分別進(jìn)行計(jì)算的合理性。在工程模型中存在大量的相互之間成直角的面，形狀分布矩陣中的非零值會(huì)集中在表示180。，90。，o。的三行中(Y軸度量的是夾角的余弦值，分別對(duì)應(yīng)Y軸的0，10，20)，針對(duì)該情況筆者進(jìn)行了專門的實(shí)驗(yàn)。圖8說(shuō)明了分布在上述三行中的存在大量互成直角面的模型的形狀分布特點(diǎn)，它與存在其他分布特點(diǎn)的模型并無(wú)本質(zhì)不同。實(shí)驗(yàn)證明，此類模型的形狀函數(shù)值雖然主要分布在這三行中，但每一行的具體分布規(guī)律因模型不同而有所不同，因此本算法也能較好地區(qū)分其間的差別。

　　圖8大量存在互成直角面的模型及其形狀分布2.5形狀比較經(jīng)上述處理，模型的比較轉(zhuǎn)化為形狀分布矩陣的比較。本文仍然采用L。范數(shù)，即歐式距離計(jì)算兩矩陣間的距離。令MA=(m。)I，xL，B=(m6)f。×L。v M分別為模型A，B對(duì)應(yīng)的形狀分布矩陣，則模型A，B間的距離為D(A，B)=D(MA，MB)一

　　3、算法復(fù)雜度分析

　　由算法過(guò)程可知，提取網(wǎng)格特征臨界點(diǎn)和計(jì)算近似測(cè)地距離是時(shí)間復(fù)雜度較高的兩個(gè)步驟。

　　3.1提取網(wǎng)格特征臨界點(diǎn)的時(shí)間復(fù)雜度

　　(1)網(wǎng)格微分量計(jì)算需計(jì)算每個(gè)三角面片的面積，最壞情況下，即每個(gè)三角面片為銳角三角形時(shí)，按照Voroini方法，一個(gè)三角面片的面積需計(jì)算三次(三次面積各不相同)。由于面積計(jì)算僅是單獨(dú)的乘法，與其他步驟相比，可認(rèn)為此步驟的時(shí)間復(fù)雜度為常數(shù)。

　　(2)頂點(diǎn)影響因子計(jì)算最耗時(shí)部分為搜索任意頂點(diǎn)在某鄰域內(nèi)的所有頂點(diǎn)。本文將頂點(diǎn)數(shù)據(jù)存入k-d樹來(lái)加速此過(guò)程。設(shè)網(wǎng)格頂點(diǎn)數(shù)為N，計(jì)算臨界點(diǎn)時(shí)的循環(huán)次數(shù)為艴，文獻(xiàn)[-14]中已證明，在一棵肛d樹中插入和搜索節(jié)點(diǎn)的平均時(shí)間復(fù)雜度為0(109：N)，故此步驟最終的時(shí)間復(fù)雜度為 o(nN·l092N)。

　　3.2計(jì)算近似測(cè)地距離的時(shí)間復(fù)雜度

　　本文采用SPFA算法計(jì)算從任意頂點(diǎn)到其余頂點(diǎn)的近似最短路徑。設(shè)網(wǎng)格模型的邊數(shù)為E，求得的所有臨界點(diǎn)數(shù)量為Nc，文獻(xiàn)E13]已證明，計(jì)算從任意點(diǎn)出發(fā)到所有頂點(diǎn)的近似最短距離的時(shí)間復(fù)雜度為0(E)，故此步驟最終的時(shí)間復(fù)雜度為o(Nc·E)。

　　4、算法驗(yàn)證與討論

　　以Visual C++6.0為集成開發(fā)環(huán)境，結(jié)合Matlab 6.5實(shí)現(xiàn)了本文提出的算法，并在普渡大學(xué)建立的工程標(biāo)準(zhǔn)模型庫(kù)ESB(engineering shapebenchmark)‘153上進(jìn)行了驗(yàn)證。實(shí)驗(yàn)采用PC機(jī)，AMD 2500+CPU，512 M內(nèi)存。

　　ESB中包含866個(gè)STL格式的工程模型，筆者以其中任意一個(gè)模型作為輸入，欲檢索出模型庫(kù)中相似的模型，并與傳統(tǒng)圖形分布算法(D2 shape distribution)和增強(qiáng)圖形分布算法[16](D-IA shape distributionwith simplification)進(jìn)行了對(duì)比。本文描述的算法以模型的STL格式作為檢索輸入，實(shí)驗(yàn)中的參數(shù)為L(zhǎng)，=64，L，=20;根據(jù)實(shí)驗(yàn)結(jié)果，取盯=0.24%￡，￡為網(wǎng)格模型包圍盒對(duì)角線的長(zhǎng)度，并取UC一如一口，iteration一10。圖9列出了前五個(gè)檢索結(jié)果，其中的數(shù)字表示檢索到的模型與輸入模型的距離。從圖中可以看出，基于特征臨界點(diǎn)的算法能夠比另外兩種方法檢索出更多有效的模型，這是因?yàn)樘卣髋R界點(diǎn)本身就是模型的頂點(diǎn)，由 Morse理論可知，臨界點(diǎn)表征了模型的空間拓?fù)浣Y(jié)構(gòu)和幾何結(jié)構(gòu)，因此比基于采樣點(diǎn)的方法更能反映模型自身的特點(diǎn);且本算法采用的近似測(cè)地距離代替?zhèn)鹘y(tǒng)的 D2距離，測(cè)地線本身就是對(duì)模型表面形狀的反映，其長(zhǎng)度亦體現(xiàn)了模型局部形狀的變化，用于做形狀函數(shù)效果較好，但其計(jì)算比D2距離要復(fù)雜。因此，鑒于對(duì)時(shí)間復(fù)雜度的考慮，近似測(cè)地距離是一種較好的折衷。

　　現(xiàn)對(duì)不同檢索輸入的檢索時(shí)間和有效性進(jìn)行統(tǒng)計(jì)，可得到算法的平均性能。針對(duì)ESB庫(kù)中的三大類模型，即薄壁件、棱柱類零件和旋轉(zhuǎn)件分別統(tǒng)計(jì)，將其綜合得到算法在整體ESB庫(kù)上的平均性能，做出查準(zhǔn)率一查全率(Precision—Recall，PR)曲線，并與其他形狀檢索算法(表面積與體積描述 [151、角度分布直方圖[17‘、3D球諧描述子[18]、2D形狀直方圖[1?、光場(chǎng)描述子[20])進(jìn)行了比較，如圖10所示。

　　從PR曲線可以看出，本方法雖然目前還達(dá)不到光場(chǎng)描述子的效果，但它有效提高了傳統(tǒng)D2形狀分布算法的檢索性能，在計(jì)算復(fù)雜度和檢索效果之間找到了一種平衡。

　　對(duì)圖10的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行綜合，表1定量地比較了D2形狀分布、帶網(wǎng)格簡(jiǎn)化的D-IA形狀分布和本文算法的檢索精度和效率，F(xiàn)T，ST，NN的含義見參考文獻(xiàn)E16]。從中可以看出，基于特征臨界點(diǎn)的方法雖然總的檢索時(shí)間有所增加(主要是計(jì)算近似測(cè)地距離需時(shí)較多)，但仍在可接受的范圍內(nèi)，且其檢索結(jié)果要明顯優(yōu)于另外兩種方法。

　　5、結(jié)束語(yǔ)

　　針對(duì)傳統(tǒng)基于形狀分布檢索算法的不足，提出了基于特征臨界點(diǎn)的檢索算法。該算法以三維工程網(wǎng)格模型作為輸入，以Morse臨界點(diǎn)理論為依據(jù)，用網(wǎng)格模型的特征臨界點(diǎn)代替?zhèn)鹘y(tǒng)的采樣點(diǎn)進(jìn)行形狀函數(shù)計(jì)算，避免了采樣不足對(duì)算法造成的影響;取網(wǎng)格曲面上兩臨界點(diǎn)問(wèn)近似測(cè)地線距離與兩點(diǎn)處法矢夾角的余弦值作為聯(lián)合形狀函數(shù)，更好地表征了模型整體表面和局部區(qū)域的變化;分別針對(duì)極大值點(diǎn)、極小值點(diǎn)和鞍點(diǎn)計(jì)算聯(lián)合形狀函數(shù)值，模型的整體描述由三者加權(quán)平均得到。實(shí)驗(yàn)結(jié)果表明，本算法客觀反映了工程模型的相似程度，明顯提高了傳統(tǒng)圖形分布方法檢索的有效性。

　　以下幾項(xiàng)工作在未來(lái)研究中應(yīng)該著重加強(qiáng)：①本文算法的時(shí)間效率雖然可以接受，但還有很大的提升余地來(lái)找到效率更高的近似測(cè)地距離算法。②采用歐拉距離計(jì)算兩矩陣間的距離存在缺點(diǎn)。形狀矩陣中的每一列(行)代表一形狀度量向量，不同度量向量對(duì)于區(qū)分形狀有著不同的重要性，而歐拉距離將矩陣不同列(行)之問(wèn)的差別等同看待，因此最終的距離只反映了平均綜合的結(jié)果，不能表示出某一形狀度最向量對(duì)總體差異的影響。這樣導(dǎo)致了兩矩陣即使距離較近，但其代表的圖形可能并不相似。

　　因此可以嘗試其他的度量方法，從而不僅反映矩陣間的距離，而且能體現(xiàn)矩陣自身的分布。③由于特征臨界點(diǎn)體現(xiàn)了模型局部的形狀信息，可以考慮將其用于局部形狀檢索。

【基于網(wǎng)格特征臨界點(diǎn)的三維工程模型檢索算法】相關(guān)文章：

基于智能優(yōu)化算法的Wiener模型辨識(shí)論文提綱12-05

淺談基于質(zhì)量技術(shù)特征改善率的并行優(yōu)化模型分析論文03-09

基于QBASIC環(huán)境下的數(shù)學(xué)算法教學(xué)11-14

基于滾動(dòng)計(jì)劃的動(dòng)態(tài)企業(yè)資源優(yōu)化模型03-29

探析基于VaR模型的證券投資組合風(fēng)險(xiǎn)12-05

基于勝任力模型的組織生涯管理探析12-12

《基于導(dǎo)納的圖像加密算法的研究》開題報(bào)告12-03

基于教學(xué)知識(shí)點(diǎn)的模型框架與結(jié)構(gòu)分析12-05

淺談基于知識(shí)的網(wǎng)格技術(shù)應(yīng)用研究11-20