基于模型分割的子區(qū)域局部匹配算法

李 芳，莫 蓉

（西北工業(yè)大學(xué) 機(jī)電學(xué)院，陜西 西安 710072）

0 引言

隨著數(shù)字化設(shè)計(jì)技術(shù)的深入發(fā)展，產(chǎn)品的三維模型越來(lái)越多地應(yīng)用于企業(yè)中，成為可以利用的有效資源，如何快速準(zhǔn)確地從模型庫(kù)中找到所需的零件模型成為應(yīng)用的一個(gè)難點(diǎn)。在機(jī)械工程領(lǐng)域，CAD模型的相似性檢索具有重要的應(yīng)用價(jià)值[1-2]。人們往往將已有的模型作為設(shè)計(jì)參考或重用，而模型的細(xì)節(jié)結(jié)構(gòu)成為結(jié)構(gòu)細(xì)分的重要因素，因此，在模型庫(kù)中進(jìn)行三維模型的局部檢索在工程界具有重要的應(yīng)用價(jià)值。近年來(lái)，基于內(nèi)容的檢索技術(shù)研究成為熱點(diǎn)，它可以直接利用三維模型的特征來(lái)建立索引和完成檢索，其關(guān)鍵是使提取的結(jié)果能夠描述模型形狀特征[3]。Zhang和Chen[4]在幾何結(jié)構(gòu)上通過(guò)三角網(wǎng)格描述模型的表面輪廓，但由于數(shù)據(jù)多計(jì)算效率較低，效果不理想；Osada[5]提取模型表面采樣點(diǎn)，計(jì)算點(diǎn)與點(diǎn)之間諸如角度距離、面積和體積作為幾何度量的形狀函數(shù)，其形狀函數(shù)值的概率分布作為模型的特征向量，但分布函數(shù)會(huì)丟失細(xì)節(jié)信息。Cyr和Kimia[6]將圖片進(jìn)行聚類(lèi)并最終根據(jù)圖片之間的關(guān)系將它們組織成 shock圖結(jié)構(gòu)，采用shock圖匹配算法計(jì)算物體的圖片之間的相似度。

為了更好地實(shí)現(xiàn)局部檢索時(shí)準(zhǔn)確性與效率的雙重結(jié)合，本文提出了一種基于模型分割的子區(qū)域局部匹配算法。提取CAD模型的B-rep信息，交互或預(yù)定義方式獲取預(yù)檢索的局部區(qū)域，將局部區(qū)域和CAD模型分別用屬性鄰接圖表示，并對(duì)兩者按照模型凸凹性區(qū)域分割算法進(jìn)行區(qū)域分割，再在凹凸性基礎(chǔ)上實(shí)現(xiàn)CAD模型的局部匹配。

1 基于模型子區(qū)域局部匹配算法

1.1 CAD模型的B-rep表示

模型的B-rep表示可以直接反映形體元素的幾何信息與拓?fù)湫畔ⅲ鋬?yōu)點(diǎn)是可直接表示點(diǎn)、邊、面等幾何元素及其之間的關(guān)系[7]。屬性鄰接圖（Attributed Adjacency Graph，AAG）是一種用圖來(lái)表示實(shí)體的B-rep結(jié)構(gòu)的方法，其表達(dá)式為G=（V，E，A）。其中，G表示CAD模型；V表示圖的節(jié)點(diǎn)集合，代表模型的幾何曲面，每個(gè)面fi都有唯一一個(gè)節(jié)點(diǎn)vi與之對(duì)應(yīng)；E表示圖的邊集合，對(duì)于模型的每?jī)蓚€(gè)相鄰面fi，fj都有唯一的弧ei與之對(duì)應(yīng)；A表示面集合和邊集合的相關(guān)屬性，面的屬性包括其所屬類(lèi)別以及指向，其中，類(lèi)別包括平面、柱面、雙曲面、球面等。面的指向則根據(jù)其曲率正負(fù)分為凸曲面、凹曲面、平面[7]。邊作為兩面的相交部分，其屬性可以按照兩曲面外夾角分為凸邊、凸切邊、凹邊、凹切邊[9]。考慮到工程應(yīng)用中大部分三維模型由相對(duì)簡(jiǎn)單的幾何面構(gòu)成，本文的研究對(duì)象均為由簡(jiǎn)單幾何面如平面、柱面構(gòu)成的CAD模型。

定義一：凸子圖。（1）圖 g=（v，e，a）是圖 G=（V，E，A）的導(dǎo)出子圖；（2）g中的任意節(jié)點(diǎn)表示的面的屬性為凸曲面或平面；（3）g中節(jié)點(diǎn)之間的連接邊均為凸邊。則稱(chēng)g為凸子圖。凸子圖所代表的曲面組成的區(qū)域?yàn)橥箙^(qū)域。

定義二：凹子圖。（1）圖 g=（v，e，a）是圖 G=（V，E，A）的導(dǎo)出子圖；（2）g中的任意節(jié)點(diǎn)表示的面的屬性為凹曲面或平面；（3）g中節(jié)點(diǎn)之間的連接邊均為凹邊。則稱(chēng)g為凹子圖。凹子圖所代表的曲面組成的區(qū)域?yàn)榘紖^(qū)域。

定義三：凸節(jié)點(diǎn)。圖 g=（v，e，a）中，節(jié)點(diǎn) vi表示面為凸曲面或平面；并且它的連接邊中無(wú)凹邊，則稱(chēng)這類(lèi)節(jié)點(diǎn)為凸節(jié)點(diǎn)。

定義四：凹節(jié)點(diǎn)。圖 g=（v，e，a）中，節(jié)點(diǎn) vi表示的面為凹面或平面；并且它的連接邊中無(wú)凸邊，則稱(chēng)這類(lèi)節(jié)點(diǎn)為凹節(jié)點(diǎn)。

定義五：混合節(jié)點(diǎn)。圖 g=（v，e，a）中，節(jié)點(diǎn) vi表示凸（凹）曲面，并且連接邊中存在凹（凸）邊；或者vi節(jié)點(diǎn)表示平面，并且它的連接邊中同時(shí)存在凸邊和凹邊。

顯然凸（凹）區(qū)域中的節(jié)點(diǎn)一定是凸（凹）節(jié)點(diǎn)，如果可以繼續(xù)分離子圖，則分離后的子圖凸凹類(lèi)型不變。對(duì)于混合節(jié)點(diǎn)，其凸凹性比較模糊，視分割情況而定。

1.2 模型區(qū)域分割

將模型表面按照凸凹類(lèi)型分成凸區(qū)域、凹區(qū)域，AAG中與之對(duì)應(yīng)的即凸子圖、凹子圖，因此三維模型中凸凹區(qū)域的分割等價(jià)于對(duì)應(yīng)的屬性鄰接圖的分割。我們可以將模型區(qū)域分割定義如下：

圖 G=（V，E，A），存在一組子圖 g1，g2，…，gi，gn（i=1，2，…，n），其中 gi=（v，e，a）是凸子圖或凹子圖，且滿足 GV=g1V∪g2V∪∪gnV；且 giV∩gjV=?（i≠j）；則稱(chēng)圖g1，g2，…，gi，…，gn（i=1，2，…，n）是圖G的一組分割。

在分割中，我們希望實(shí)現(xiàn)凸區(qū)域和凹區(qū)域的合理劃分，其中凸凹子圖中節(jié)點(diǎn)和邊的凸凹性質(zhì)與其子圖本身一致。在劃分中，凸節(jié)點(diǎn)劃分到凸子圖，凹節(jié)點(diǎn)劃分到凹子圖，而混合節(jié)點(diǎn)中既有相連的凸邊又有相連的凹邊，劃分起來(lái)比較麻煩，因此需要重新確定混合節(jié)點(diǎn)的凸凹性質(zhì)。鑒于先識(shí)別凸子圖或者先識(shí)別凹子圖會(huì)得到不同的效果但又不會(huì)影響區(qū)域凸凹區(qū)域特征的表現(xiàn)，我們規(guī)定在分割時(shí)先識(shí)別并分離凸子圖，后識(shí)別并分離凹子圖[10]。

一種最直接最簡(jiǎn)單的分割即是將圖的每個(gè)節(jié)點(diǎn)作為一個(gè)子圖，顯然，這種分割沒(méi)有意義。我們希望分割后的區(qū)域數(shù)量越少越好，并且能夠明顯的描述模型表面凸凹特點(diǎn)。因此提出下列分割方法：

（1）根據(jù)節(jié)點(diǎn)凸凹性，通過(guò)圖的遍歷識(shí)別出G中所有混合節(jié)點(diǎn)，若無(wú)，則圖G中節(jié)點(diǎn)的凸凹性質(zhì)一致，本身G就是一凸子圖或者凹子圖，將圖G=（V，E，A），輸出到區(qū)域H中；若存在混合節(jié)點(diǎn)，轉(zhuǎn)到步驟（2）；

（2）由步驟（1）識(shí)別出了混合節(jié)點(diǎn)后，刪除混合節(jié)點(diǎn)的所有凹邊，將G分割成子圖集M={g1，g2，…，gm}；

（3）在剩余的子圖集中肯定存在凸子圖，可能存在凹子圖，因?yàn)楸旧砘旌瞎?jié)點(diǎn)就連接著凸邊和凹邊，刪除了與其連接的凹邊，必然剩下凸邊，否則與混合節(jié)點(diǎn)的定義相違背。將子圖集M輸出到H中；

（4）將分割后的凸子圖輸出到H后，在剩余的圖中恢復(fù)刪除的凹邊，并重新確定子圖gi（i=m+1，…，n）中混合節(jié)點(diǎn)的凸凹類(lèi)型。若不存在混合節(jié)點(diǎn)，則將它輸出到區(qū)域R中；否則，將以gi作為輸入，重復(fù)步驟（2）；

（5）輸出分割結(jié)果H。

1.3 子區(qū)域局部匹配算法的實(shí)現(xiàn)

傳統(tǒng)的模型匹配算法大多按照CAD模型以及預(yù)匹配模型的B-rep信息，在大圖中搜索與小圖的拓?fù)渑c幾何相同的子圖。由于屬性鄰接圖中包含了模型每個(gè)面和邊的屬性信息，算法實(shí)現(xiàn)起來(lái)信息量大，效率不是很理想，區(qū)別能力有限。因此我們?cè)贑AD模型B-rep表示的基礎(chǔ)上，構(gòu)建模型的屬性鄰接圖，提出模型表面區(qū)域分割的思想，經(jīng)過(guò)分割后，模型被分解為凸凹子圖的集合 G={g1，g2，…，gu}，設(shè)預(yù)匹配子圖為 Q={q1，q2，…，qs}，下文中我們稱(chēng)圖 G為大圖，預(yù)匹配子圖為小圖，分三種情況進(jìn)行匹配，具體的匹配過(guò)程如下：

情況一：小圖均為凸子圖（或凹子圖）

（1）小圖Q由凸節(jié)點(diǎn)組成，即本身為一凸子圖，則只需在大圖G中的凸子圖中進(jìn)行匹配搜索，設(shè)G的一個(gè)凸子圖gi，ηi∈E，i=1，2，…，t（ηi為凸子圖的邊，t為此凸子圖的邊數(shù)）vj∈e，j=1，2，…，s（vj為小圖的邊，s為小圖的邊數(shù)）若t≥s，則繼續(xù)匹配，轉(zhuǎn)到步驟（2）；反之，此凸子圖中無(wú)法與已知子圖匹配；如此過(guò)程遍歷Q中的所有凸子圖；

（2）分別在凸子圖gi中尋找與邊vj屬性相同的所有邊，如果存在則存入集合，Si，j，i=1，2，…，z，j=1，2，…，s（z為凸子圖個(gè)數(shù)，s為集合元素的個(gè)數(shù)，與小圖中邊的個(gè)數(shù)相同）；若凸子圖gi中無(wú)與邊vj屬性相同的邊，則該凸子圖中不含有預(yù)匹配的局部結(jié)構(gòu)。

（3）在 Si，j中任取一條邊，并按照邊的順序提取出各邊相鄰的面，去除重復(fù)的面，形成面的集合Vy。若Vy中面的個(gè)數(shù)與小圖的面的個(gè)數(shù)相同，則轉(zhuǎn)到步驟4，否則進(jìn)行下一個(gè)組合。

（4）將Vy組成的局部結(jié)構(gòu)從CAD模型中分離出來(lái)并表示出其鄰接矩陣，如果新結(jié)構(gòu)的鄰接矩陣與小圖的鄰接矩陣相等，則該凸子圖中含有預(yù)匹配的局部結(jié)構(gòu)；反之，返回步驟（3），繼續(xù)下一組合。

（5）若小圖Q由凹節(jié)點(diǎn)組成，即本身為一凹子圖，匹配過(guò)程類(lèi)似凸子圖，過(guò)程如步驟（1）到（4）。

情況二：小圖為混合子圖

若小圖Q由凸節(jié)點(diǎn)和凹節(jié)點(diǎn)組成，設(shè)分割后的小圖表示為 Q={q1…ql，ql+1…qh}，其中{q1…ql}表示小圖的凸子圖集合，{ql+1…qh}表示小圖的凹子圖的集合；分割后的大圖表示為 G={g1…gm，gm+1…gs}；其中{g1…gm}表示大圖的凸子圖集合，{gm+1…gs}表示大圖的凹子圖集合。

（1）通過(guò)圖的深度優(yōu)先算法或?qū)挾葍?yōu)先算法遍歷大圖G的各節(jié)點(diǎn)，判斷大圖是否也由凸凹節(jié)點(diǎn)組成，如果是，轉(zhuǎn)向步驟（2），反之，大圖中無(wú)匹配區(qū)域；

（2）從小圖的一個(gè)凸子圖中任取一個(gè)邊wj，并在大圖的各凸子圖中搜索與該邊屬性相同的邊，設(shè)為vi；

（3）將搜索到的大圖中邊所在的凸子圖存入集合 M={g1…gt}；

（4）任取M中的一個(gè)凸子圖，從vi開(kāi)始遍歷與其相連的各邊，看是否與wj所連的相應(yīng)的邊的屬性相同，若相同，則此凸子圖匹配成功，繼而重復(fù)步驟（2），進(jìn)行下一小圖中的凸子圖的匹配；若在遍歷過(guò)程中，有屬性不一致的邊，則停止此次搜索，由于大圖中可能存在不止一個(gè)凸子圖中有與邊wj相同屬性的邊，因此，還需繼續(xù)重復(fù)步驟（2），直到與wj屬性相同的邊所在的凸子圖都遍歷完成，還無(wú)可匹配子圖，則結(jié)束匹配；

（5）小圖中凹子圖的搜索及匹配與凸子圖類(lèi)似，步驟如上，這里就不再贅述。

（6）由于小圖是由凸凹子圖組成，只有其凸凹子圖同時(shí)在大圖中找到相匹配的部分才能說(shuō)明大圖中存在與小圖匹配的子結(jié)構(gòu)。

2 實(shí)驗(yàn)與分析

本節(jié)給出了采用本文方法得到的部分實(shí)驗(yàn)結(jié)果：一個(gè)是根據(jù)凸凹性質(zhì)的模型表面區(qū)域劃分；另外一個(gè)是基于凸凹子區(qū)域的局部匹配得到的檢索結(jié)果。

2.1 模型的凸凹區(qū)域分割

利用本文的方法，選取典型零件對(duì)其區(qū)域分割。圖1a所示為一個(gè)CAD模型經(jīng)過(guò)表面區(qū)域分割后的結(jié)果，我們將同一區(qū)域的部分標(biāo)記為同種顏色。該模型經(jīng)過(guò)分割后共有五個(gè)區(qū)域，其中四個(gè)凹區(qū)域，一個(gè)凸區(qū)域；為了更好的顯示，圖1b中給出了該模型的拓?fù)溥B接圖，其中“+”表示面與面的連接邊為凸邊，“-”則為凹邊。工程中的正特征和負(fù)特征對(duì)于模型的特征表述以及制造加工具有重要的意義，而我們的凸區(qū)域和凹區(qū)域也和這兩種特征有一定的聯(lián)系。實(shí)驗(yàn)可以看出，利用該方法能較好的實(shí)現(xiàn)CAD模型的區(qū)域分割，并且對(duì)于得到的分割區(qū)域具有一定的工程意義，為模型分析及下文的子區(qū)域匹配奠定了良好的基礎(chǔ)。

圖1 模型凸凹區(qū)域分割

2.2 基于凸凹子區(qū)域的局部匹配

圖2 典型結(jié)構(gòu)

圖3 典型結(jié)構(gòu)搜索結(jié)果

為了驗(yàn)證基于子區(qū)域局部匹配算法的有效性，我們選擇了上述區(qū)域分割的盤(pán)類(lèi)結(jié)構(gòu)作為典型結(jié)構(gòu)（圖2），并在50個(gè)包含了軸類(lèi)、齒輪類(lèi)、盤(pán)類(lèi)的典型結(jié)構(gòu)作為三維CAD模型庫(kù)中進(jìn)行匹配。其中三維CAD模型庫(kù)中有11個(gè)模型被準(zhǔn)確檢索到，這里選取6個(gè)具有代表性的模型進(jìn)行顯示如圖3。本文算法較之以往的按照相似性模糊匹配方法具有明顯的優(yōu)勢(shì)，由于在匹配之前對(duì)模型進(jìn)行凸凹區(qū)域分割處理，相匹配的結(jié)構(gòu)必然與預(yù)匹配模型具有相同拓?fù)浣Y(jié)構(gòu)的凸區(qū)域和凹區(qū)域，因此能更好的保證匹配精度。而且按照凸凹區(qū)域來(lái)匹配不需要逐邊逐面的按照屬性來(lái)搜索，可以大大降低搜索空間，通過(guò)與文獻(xiàn)[3]對(duì)比，可以發(fā)現(xiàn)本文的算法在效率上能大約提高15%到25%。

3 小結(jié)

局部結(jié)構(gòu)的檢索在工程上具有一定的意義，也是模型檢索中一個(gè)難點(diǎn)問(wèn)題[11]。幾何模型的數(shù)據(jù)結(jié)構(gòu)只能表達(dá)產(chǎn)品的幾何拓?fù)潢P(guān)系，不能表達(dá)產(chǎn)品的非幾何信息，因而缺乏產(chǎn)品開(kāi)發(fā)過(guò)程中所要求的工程語(yǔ)義信息[12]。本文在屬性鄰接圖的基礎(chǔ)上，提出一種基于凸凹子區(qū)域的局部匹配算法。首先按照模型的面和邊的屬性，經(jīng)過(guò)一系列的處理將CAD模型分割成凸凹區(qū)域，也就相當(dāng)于將其屬性鄰接圖分割成若干個(gè)凸凹子圖。在匹配過(guò)程中，將大圖與小圖中凸子圖與凸子圖，凹子圖與凹子圖分別匹配。通過(guò)判斷子區(qū)域是否相應(yīng)匹配看大圖中是否含有預(yù)匹配的結(jié)構(gòu)。本文算法不需逐邊逐面的采用子圖匹配算法來(lái)進(jìn)行檢索。由于考慮模型的邊和面的幾何信息，更有利于模型結(jié)構(gòu)的檢索[13]。但是屬性鄰接圖的構(gòu)造是從模型的B-rep信息入手，這種采用單一特征描述方法喪失了空間分布信息，因此存在不完整性。如何將幾何和拓?fù)湫畔⒏玫膩?lái)進(jìn)行特征描述，并用于三維模型檢索，仍是今后需要研究的內(nèi)容。

[1]Cardone A，Gupta S K，Karnik M·A survey of shape similarity assessmentalgorithmsforproductdesign and manufacturing applications[J].Journal of Computing and Information Science in Engineering，2003，3（6）：109-118.

[2]王 玉，馬浩軍，何 瑋，等.機(jī)械三維CAD模型的聚類(lèi)和檢索[J].計(jì)算機(jī)集成制造系統(tǒng)，2006，12（6）：924-928.

[3]胡琪波，何衛(wèi)平，董 蓉，等.可重用MES模板檢索技術(shù)研究[J].鍛壓裝備與制造技術(shù)，2010，45（3）.

[4]Zhang和chen C.Zhang and T.Chen.Indexing and Retrieval of 3D Models Aided by Active Learning.In ACM Multimedia，2001：615-616.

[5]Osada R.Osada，T.Funkhouser，B.Chazelle，and D.Dobkin.shape Dis tributions.Acm Transactions On Graphics，2002.21（4）：807-832.

[6]Cyr和Kimia C.M.Cyr and B.Kimia.3D Object Recognition Using Shape Similiarity-Based Aspect Graph.In ICCV01，2001：254-261.

[7]王 飛，張樹(shù)生，白曉亮，等.基于子圖同構(gòu)的三維CAD模型局部匹配 [J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2008，（8）：1078-1084.

[8]Sonthi R，Kunjur G，Gadh R.Shape feature determination using the curvature region representation[C]//Proceedings of the 4thSymposium on Solid Modeling and Applications，Atlanta，1997：285-296.

[9]Fu M W，Ong S K，Lu W F，etal.An approach to identify design and manufacturing features from a data exchanged part model[J].Computer-Aided Desegn，2003，35（11）：979-993.

[10]馬露杰，黃正東，梁 良，等.CAD模型表面區(qū)域分割方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2009.

[11]白 靜.面向設(shè)計(jì)重用的三維CAD模型檢索[D].浙江：浙江大學(xué)，2009.

[12]杜繼濤，齊從謙，甘 屹.基于集成技術(shù)的汽車(chē)覆蓋件產(chǎn)品模型.鍛壓裝備與制造技術(shù)，2005，40（2）.

[13]徐 勝.三維物體識(shí)別研究[D].成都：電子科技大學(xué)，2009.