單曲率特征自由曲面的相似性比較算法

王洪申, 汪雨蓉, 趙紅紅, 閆金堂

(蘭州理工大學(xué) 機(jī)電工程學(xué)院, 甘肅 蘭州 730050)

隨著CAD/CAM技術(shù)的發(fā)展和在工程中的普及,三維CAD模型在設(shè)計(jì)和加工中的重用問(wèn)題日顯突出,三維模型的相似性評(píng)價(jià)是模型檢索和重用的核心技術(shù),受到廣泛關(guān)注,學(xué)者們對(duì)三維CAD模型的相似性比較方法進(jìn)行了較深入的研究,如Hilaga等[1]提出基于Reeb圖的三維網(wǎng)格模型拓?fù)淦ヅ浞椒?Bespalov等[2]對(duì)網(wǎng)格化處理的CAD模型進(jìn)行形狀檢索,發(fā)現(xiàn)機(jī)械零件拓?fù)浣Y(jié)構(gòu)的微小變化會(huì)引起相似度的巨大差異;Bespalov等[3]提出基于尺度空間分解的層次特征分割方法,用于三維CAD模型的局部相似性比較。由于工程特性或美觀的需要,自由曲面在工業(yè)產(chǎn)品中應(yīng)用越來(lái)越多,自由曲面造型復(fù)雜、加工困難,重用自由曲面設(shè)計(jì)模型和數(shù)控加工規(guī)劃具有更好的工程意義,這使得評(píng)價(jià)自由曲面相似性顯得尤為迫切。You等[4]構(gòu)建拓?fù)鋱D,通過(guò)檢測(cè)獨(dú)立最大團(tuán)方法,計(jì)算汽車覆蓋件曲面模型的相似性;王洪申等[5]采用區(qū)域生長(zhǎng)法對(duì)STL格式的自由曲面進(jìn)行分割構(gòu)建拓?fù)浣Y(jié)構(gòu),利用賦權(quán)二分圖最優(yōu)匹配算法進(jìn)行相似性比較;Fu等[6]研究鼠標(biāo)、相機(jī)等自由曲面模型的相似性,提出基于高斯曲率積分的相似性比較方法;王洪申等[7]提出距離-曲率形狀分布的方法,以距離-曲率矩陣的相似度得到曲面模型的相似性描述;張開(kāi)興等[8]從曲率云圖中提取特征點(diǎn)的類Sift算子,通過(guò)比較局部特征的相似性實(shí)現(xiàn)2個(gè)曲面相似性的評(píng)價(jià)。Li等[9-10]運(yùn)用層次分割圖(HPG)表達(dá)注塑模具,并基于HPG圖運(yùn)用子圖同構(gòu)算法計(jì)算模具間的相似性。Huang等[11]提出一種以加工重用為目的的自由曲面相似性評(píng)價(jià)與檢索方法。首先對(duì)曲面進(jìn)行內(nèi)容編碼,初步過(guò)濾掉不匹配的對(duì)象,然后用D2算法[12]和子圖同構(gòu)算法評(píng)價(jià)自由曲面的相似性。已有研究都是通過(guò)設(shè)計(jì)抽象的幾何描述子來(lái)表達(dá)自由曲面的幾何特征,而在將自由曲面表達(dá)成幾何描述子的過(guò)程中,不可避免地丟失了部分自由曲面的幾何特征,從而限制了對(duì)曲面的幾何形態(tài)描述能力。為了能以更細(xì)的粒度描述自由曲面的幾何特征,又能滿足檢索對(duì)計(jì)算速度的需要,本文依據(jù)曲面曲率,提出適用于單曲率特征自由曲面相似性比較算法。該算法首先調(diào)整三維曲面的姿態(tài),使相比較的曲面的Z軸方向一致,然后將待比較曲面做切片處理提取曲面上的截交線,以截交線上一系列點(diǎn)的曲率為依據(jù)判別相應(yīng)曲線的相似性,將2個(gè)曲面的相似性度量轉(zhuǎn)換為2簇平面曲線的相似性比較,以降維思想簡(jiǎn)化曲面相似性評(píng)價(jià)問(wèn)題。

1 單曲率特征自由曲面的含義

曲面上點(diǎn)的曲率信息是曲面形狀描述中極其重要的一個(gè)屬性,能夠可靠地反應(yīng)曲面的形狀特征。由微分幾何知,曲面上某點(diǎn)處的2個(gè)主曲率為k1,k2,它們的乘積稱為曲面該點(diǎn)處的高斯曲率,常以K表示,它們的平均數(shù)稱為曲面該點(diǎn)的平均曲率,常以H表示。根據(jù)曲面上點(diǎn)的高斯曲率和平均曲率將自由曲面的特征定義為如下A,B,C 3類(如圖1所示),本文研究的“單曲率特征的自由曲面”定義為:曲率特征單一,只有凸特征或凹特征或鞍型特征的簡(jiǎn)單自由曲面。

A類:K>0,H<0的曲面稱為單一凸自由曲面,如圖1a)所示;

B類:K>0,H>0的曲面稱為單一凹自由曲面, 如圖1b)所示;

C類:K≤0的曲面稱為單一鞍型自由曲面,又叫雙曲拋物面, 如圖1c)所示。

本文約定:類型相同單特征自由曲面才有評(píng)價(jià)相似性意義,如果曲面類型不同則認(rèn)為不具有相似性。

圖1 單曲率特征的自由曲面分類

2 單曲率特征自由曲面的相似性比較算法

本文研究的是B樣條表達(dá)的自由曲面的相似性評(píng)價(jià)算法,所設(shè)計(jì)算法的總體思路如圖2所示,將一個(gè)自由曲面描述為一簇平面曲線的集合,2個(gè)自由曲面之間的相似性可以通過(guò)曲面上對(duì)應(yīng)的2簇曲線的相似性來(lái)衡量。曲面上點(diǎn)的曲率信息能形象地描述曲面形狀,本文設(shè)計(jì)的算法以點(diǎn)的曲率為核心參數(shù),計(jì)算2個(gè)曲面上已提取的對(duì)應(yīng)曲線的相似值,用所有相似值的平均值來(lái)評(píng)估2個(gè)單曲率特征自由曲面的相似性。

圖2 本文算法思路

2.1 曲面做Z軸對(duì)齊處理

調(diào)整曲面模型在歐氏空間的擺放位置,將曲面的Z軸對(duì)齊。如圖3a)所示,兩凸曲面在空間的擺放位置不統(tǒng)一,2個(gè)面上各點(diǎn)法矢矢量和分別為N1,N2,由于曲面的位置不一致,可能無(wú)法得到正確相似性比較結(jié)果；通過(guò)對(duì)齊處理，如圖3b)所示,使兩曲面的法矢矢量之和的方向一致,均指向Z坐標(biāo)軸的方向,即兩曲面的Z軸對(duì)齊,此時(shí)曲面做截切處理,一一對(duì)應(yīng)的截交線更能反映曲面的真實(shí)相似度,提高算法的精度。具體實(shí)現(xiàn)過(guò)程如下:

圖3 凸面對(duì)齊處理

1) 設(shè)S={S1,S2}表示待比較相似性的同類單曲率特征的一個(gè)自由曲面集,首先依據(jù)曲面點(diǎn)的曲率值大小(不考慮正負(fù)號(hào),只考慮數(shù)值的大小),分別在曲面S1和S2上遍歷取點(diǎn)Pi(i=1,2,…,n)。曲率值大反映曲面的彎曲程度大,取分布較密集的點(diǎn)才能更準(zhǔn)確地表達(dá)曲面的真實(shí)形狀;曲率值小反映曲面的彎曲程度小,可以取分布較稀疏的點(diǎn)。遍歷取點(diǎn)的步驟如下:

步驟2選定一個(gè)搜索起點(diǎn)P1(本文設(shè)起點(diǎn)為u=0,v=0處的點(diǎn));

1) 依據(jù)前面所述,曲面上分布點(diǎn)的曲率較大時(shí)，所取的點(diǎn)比較密集，反之則所取的點(diǎn)比較稀疏,因此當(dāng)k≠0時(shí),設(shè)

(1)

式中，a1,a2,b1,b2是設(shè)定的計(jì)算參數(shù)，且a1≠0,a2≠0,b1≠0;

(2)

(3)

(4)

由公式(2)～(4)解得

(5)

公式(5)中,在給定范圍內(nèi)先確定參數(shù)a1,a2的取值,再由a1,a2確定參數(shù)b1,b2的取值。將a1,a2,b1,b2值帶入到公式(1)中即可確定每次取點(diǎn)的Δv的值；

2) 當(dāng)k=0時(shí),取Δv=b1,此處b1與1)中的意義相同，且b1≠0;

步驟4固定起點(diǎn)的v參數(shù),在參數(shù)曲線v=0上以同樣方法計(jì)算參數(shù)距離Δu尋找下一個(gè)v參數(shù)線的起點(diǎn),再重復(fù)步驟3，找到該v參數(shù)線上相應(yīng)的曲面點(diǎn);

步驟5重復(fù)步驟4,直到u參數(shù)線方向的數(shù)值越界，即可按曲率大小搜索到整個(gè)曲面上的點(diǎn)。

本文輸入圖4所示的凸曲面,計(jì)算公式(5),取a1=10-4,b1=0.03,a2=0.02,b2=0.002,4個(gè)參數(shù)值帶入公式(1)找到曲面上的所有點(diǎn)(圖4中的黑色十字交叉點(diǎn))。

圖4 凸曲面上取點(diǎn)

2.2 調(diào)整曲面大小

在工程中,有時(shí)討論自由曲面的相似性并不考慮曲面的大小,為了消除曲面尺度對(duì)相似性評(píng)價(jià)的影響,此時(shí)需要對(duì)曲面進(jìn)行比例縮放。曲面滿足Z方向的對(duì)齊后,對(duì)其中一個(gè)單曲率特征的自由曲面(本文選曲面S2)做比例縮放變換以調(diào)整大小,使兩曲面在Z坐標(biāo)軸的方向具有相同的曲面高度,用相同數(shù)目的等距平面分別截切2個(gè)曲面,處理結(jié)果如圖5所示(XOZ面內(nèi)的實(shí)體投影圖,其中黑色線條是截切處理后生成的截交線)。圖5a)的2個(gè)凸特征自由曲面S1和S2的形狀相似、大小差異明顯,工程應(yīng)用中需要考慮曲面大小尺度對(duì)相似性評(píng)價(jià)的影響時(shí),曲面不縮放,直接對(duì)其進(jìn)行截切處理,計(jì)算曲面的相似度量值(相似值為0.491),用于評(píng)價(jià)考慮曲面大小時(shí)的相似性;若將曲面縮放,消除兩曲面的大小差異,如圖5b)所示,使兩曲面在Z方向具有相同的高度范圍,相應(yīng)的相似度量值為0.126,符合人的感官判斷,這種情況適用于工程應(yīng)用中不考慮曲面大小時(shí)的相似性評(píng)價(jià)。

圖5 凸曲面的縮放變換

2.3 曲面做截切處理

三維自由曲面模型的表面形狀較復(fù)雜,微小變化會(huì)引起曲面的不同,直接比較其相似性有一定的難度。而曲面做平面截切處理可將三維空間曲面形狀的描述問(wèn)題轉(zhuǎn)換為二維平面曲線的形狀描述問(wèn)題,簡(jiǎn)化曲面相似性的比較。因此以降維的思想,用垂直于Z軸的相同數(shù)量(設(shè)為m)的等距平行平面T={Ti}(i=1,2,…,m)分別截切曲面S1和S2,在曲面S1和S2上生成各自的等高線,得到一一對(duì)應(yīng)的平面曲線(如圖5所示)。設(shè)M1,M2分別是曲面S1和S2上分布的截交線集合,則:

M1={Curvei|Curvei?S1}(i=1,2,…,m)

2.4 計(jì)算曲線的相似性

通過(guò)對(duì)曲面的截切處理,得到能反映單曲率自由曲面特性的一系列平面曲線,為了準(zhǔn)確描述曲線特征、合理表征曲線的相似性,以曲率為變量,用兩曲線曲率的Earth Mover′s Distance(EMD)值描述其相似性。EMD,也叫推土機(jī)距離,是一種距離度量的定義,能通過(guò)一次線性規(guī)劃計(jì)算出2個(gè)大小不同(或相同)的幾何或向量的距離。對(duì)于2條曲線,其形狀大小越相近,EMD值越小,相似度越高;反之,則表示其差別越大;形狀大小完全相同時(shí),EMD恒為0。

1) 曲線相似性評(píng)價(jià)

(6)

公式(6)的Ei代表第i對(duì)曲線相似的度量值。

2) 曲線相似性算法驗(yàn)證

為了驗(yàn)證2條平面曲線的相似性評(píng)價(jià)算法,設(shè)定2組曲線:Ellip1、Ellip2、Ellip3和Curve1、Curve2、Curve3、Curve4,同組曲線中,第一組為橢圓曲線,第二組為B樣條曲線(包括開(kāi)曲線和閉合曲線),其中Curve1、Curve4是形狀大小相同、位置不同的B樣條閉合曲線,如圖6～圖9所示。

圖6 3條橢圓曲線及其對(duì)應(yīng)的曲率線

圖7 3條相比較的B樣條開(kāi)曲線及其曲率線

圖8 3條相比較的B樣條閉曲線及其曲率線

圖9 形狀相同位置不同的B樣條曲線及其曲率線

分別在每條曲線上沿曲線方向等弧長(zhǎng)取相同數(shù)量(設(shè)為n)的點(diǎn),并計(jì)算各點(diǎn)的曲率(相對(duì)曲率),作為EMD度量的參數(shù),依次計(jì)算兩兩曲線的EMD值,為直觀反映曲率大小的變化,在平面坐標(biāo)系中繪制曲率分布線。由于不同曲線之間存在長(zhǎng)度上的大小差異,因此需要對(duì)曲率分布線的尺度進(jìn)行歸一化,本文實(shí)例以曲線上等弧長(zhǎng)的長(zhǎng)度作為曲率線橫坐標(biāo)的間隔,其中橫坐標(biāo)代表所取點(diǎn)的數(shù)量(坐標(biāo)原點(diǎn)是第一個(gè)點(diǎn)),縱坐標(biāo)代表點(diǎn)的曲率值。

曲線的類型、相關(guān)數(shù)據(jù)及圖形、對(duì)應(yīng)的曲率線如圖所示,圖中取點(diǎn)數(shù)量n=100時(shí)曲線所對(duì)應(yīng)的曲率線,曲線發(fā)生微小變化,則曲率線產(chǎn)生局部差異。計(jì)算同一曲線類型中兩兩對(duì)應(yīng)曲線的EMD值度量其相似性,結(jié)果如表1所示。曲線圖形是形狀有微小差異的平面曲線,根據(jù)人的直觀視覺(jué)判斷,圖6中橢圓曲線Ellip1、Ellip2的形狀大小最相近,Ellip2、Ellip3次之,Ellip1、Ellip3的形狀相差最大,計(jì)算結(jié)果，兩兩曲線的相似程度Eij滿足關(guān)系:E12(Ellip1,Ellip2)>E23(Ellip2,Ellip3)>E13(Ellip1,Ellip3)，結(jié)論與人的感知相同。圖7和圖8中B樣條曲線相似程度Eij也滿足如上關(guān)系式，結(jié)論與人的感知相同。圖9所示的閉合曲線，Curve1、Curve4的形狀大小完全相同，但位置不同，評(píng)價(jià)的相似值恒為0，評(píng)價(jià)結(jié)果與實(shí)際相符，表明選用EMD距離描述平面曲線相似性時(shí)，無(wú)需考慮曲線在平面內(nèi)的方位。表1數(shù)據(jù)顯示：無(wú)論描述橢圓曲線還是B樣條曲線，兩兩曲線的相似度量值隨著形狀差異的增大呈遞增趨勢(shì)，符合人的感官判斷，滿足各曲線間實(shí)際的相似關(guān)系，所以在應(yīng)用中，EMD距離適用于平面曲線的相似性比較。

表1 曲線圖形的EMD度量值的比較

2.5 計(jì)算曲面的相似度量值

三維曲面的表面形狀映射為一組二維曲線,2個(gè)相比較的三維曲面的相似性度量轉(zhuǎn)化為對(duì)應(yīng)的2組平面曲線的相似性度量。用2.4節(jié)公式(6)計(jì)算對(duì)應(yīng)曲線的相似值并求和即為兩曲面的相似值。由于曲面做平面截切處理時(shí),截切平面的數(shù)目變化會(huì)影響截交線相似性的總和,為了避免該問(wèn)題,對(duì)曲線相似度量值的總和求平均值,以該平均值作為曲面的相似性評(píng)價(jià)指標(biāo),記作:

(7)

3 實(shí)驗(yàn)與討論

基于OCC(Open CASCADE)開(kāi)源3D建模庫(kù),以Microsoft Visual Studio 2010為集成開(kāi)發(fā)環(huán)境,分別用第一節(jié)中定義的A,B,C 3類單曲率特征自由曲面驗(yàn)證本文相似性評(píng)價(jià)算法。主要驗(yàn)證以下屬性:(1)自由曲面繞Z軸任意旋轉(zhuǎn)對(duì)相似性評(píng)價(jià)結(jié)果的影響;(2)曲面的縮放操作對(duì)相似性評(píng)價(jià)結(jié)果的影響;(3)截交線的數(shù)量對(duì)相似性評(píng)價(jià)的影響。根據(jù)以上實(shí)驗(yàn)?zāi)康?對(duì)每類(A,B,C類)單曲率自由曲面構(gòu)造2個(gè)B樣條曲面,并分別設(shè)計(jì)3組實(shí)驗(yàn),組號(hào)分別記為X-Ⅰ、X-Ⅱ、X-Ⅲ(X取A,B,C)。實(shí)驗(yàn)方法:X-Ⅰ組在曲面相似性比較中,不對(duì)曲面進(jìn)行縮放操作,相比較的曲面位置是對(duì)齊的;X-Ⅱ組曲面不縮放,同時(shí)曲面S2繞Z坐標(biāo)軸做旋轉(zhuǎn)變換;X-Ⅲ組對(duì)曲面進(jìn)行縮放。對(duì)每組實(shí)驗(yàn)分別用10種截切間距截切曲面,由公式(7)計(jì)算兩曲面的相似度量值,在實(shí)驗(yàn)中,曲面的每條截交線上參與計(jì)算的點(diǎn)均取100個(gè)。

3.1 曲面的相似性評(píng)價(jià)實(shí)驗(yàn)數(shù)據(jù)

圖10～圖12為單曲率特征自由曲面的3種基本類型曲面實(shí)驗(yàn)圖例,表2～表4是實(shí)驗(yàn)所得的數(shù)據(jù)。

圖10 凸特征自由曲面的實(shí)驗(yàn)(A組實(shí)驗(yàn)表2) 圖11 凹特征自由曲面的實(shí)驗(yàn)(B組實(shí)驗(yàn)表3) 圖12 鞍型特征自由面的實(shí)驗(yàn)(C組實(shí)驗(yàn)表4)

表2 凸特征自由曲面的相似性比較

圖13 凸曲面不同截面數(shù)目的EMD分布線圖

表3 凹特征自由曲面相似性比較

圖14 凹曲面不同截面數(shù)目的EMD分布線圖

表4 型特征的自由曲面相似性比較

圖15 鞍型面不同截面數(shù)目的EMD分布線圖

3.2 相似性評(píng)價(jià)實(shí)驗(yàn)分析與討論

4 結(jié) 論

曲率是曲面的重要微分幾何特性,其大小與自由曲面模型在歐氏空間的擺放位置無(wú)關(guān),本文利用曲率的這種屬性設(shè)計(jì)了單曲率自由曲面相似性評(píng)價(jià)算法。首先運(yùn)用降維思想,用垂直于Z軸的平面對(duì)單曲率特征的B樣條曲面做截切處理,得到曲面與截面的交線信息,將三維空間模型轉(zhuǎn)換為較簡(jiǎn)單的二維平面圖形的集合,然后以EMD距離度量平面曲線的相似性,由此反映自由曲面的相似性,方法可靠,便于計(jì)算,對(duì)考慮曲面大小和不考慮曲面大小的情況都適用。通過(guò)大量的實(shí)驗(yàn)驗(yàn)證,設(shè)計(jì)的算法簡(jiǎn)單可行,并具有如下屬性:(1)對(duì)相比較的2個(gè)自由曲面僅需對(duì)齊一個(gè)坐標(biāo)軸;(2)算法既適用于考慮大小的曲面相似性評(píng)價(jià),也適用于不考慮大小的曲面相似性評(píng)價(jià);(3)相似性評(píng)價(jià)指標(biāo)收斂。