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

李 芳，莫 蓉

（西北工業大學 機電學院，陜西 西安 710072）

0 引言

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

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

1 基于模型子區域局部匹配算法

1.1 CAD模型的B-rep表示

模型的B-rep表示可以直接反映形體元素的幾何信息與拓撲信息，其優點是可直接表示點、邊、面等幾何元素及其之間的關系[7]。屬性鄰接圖（Attributed Adjacency Graph，AAG）是一種用圖來表示實體的B-rep結構的方法，其表達式為G=（V，E，A）。其中，G表示CAD模型；V表示圖的節點集合，代表模型的幾何曲面，每個面fi都有唯一一個節點vi與之對應；E表示圖的邊集合，對于模型的每兩個相鄰面fi，fj都有唯一的弧ei與之對應；A表示面集合和邊集合的相關屬性，面的屬性包括其所屬類別以及指向，其中，類別包括平面、柱面、雙曲面、球面等。面的指向則根據其曲率正負分為凸曲面、凹曲面、平面[7]。邊作為兩面的相交部分，其屬性可以按照兩曲面外夾角分為凸邊、凸切邊、凹邊、凹切邊[9]。考慮到工程應用中大部分三維模型由相對簡單的幾何面構成，本文的研究對象均為由簡單幾何面如平面、柱面構成的CAD模型。

定義一：凸子圖。（1）圖 g=（v，e，a）是圖 G=（V，E，A）的導出子圖；（2）g中的任意節點表示的面的屬性為凸曲面或平面；（3）g中節點之間的連接邊均為凸邊。則稱g為凸子圖。凸子圖所代表的曲面組成的區域為凸區域。

定義二：凹子圖。（1）圖 g=（v，e，a）是圖 G=（V，E，A）的導出子圖；（2）g中的任意節點表示的面的屬性為凹曲面或平面；（3）g中節點之間的連接邊均為凹邊。則稱g為凹子圖。凹子圖所代表的曲面組成的區域為凹區域。

定義三：凸節點。圖 g=（v，e，a）中，節點 vi表示面為凸曲面或平面；并且它的連接邊中無凹邊，則稱這類節點為凸節點。

定義四：凹節點。圖 g=（v，e，a）中，節點 vi表示的面為凹面或平面；并且它的連接邊中無凸邊，則稱這類節點為凹節點。

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

顯然凸（凹）區域中的節點一定是凸（凹）節點，如果可以繼續分離子圖，則分離后的子圖凸凹類型不變。對于混合節點，其凸凹性比較模糊，視分割情況而定。

1.2 模型區域分割

將模型表面按照凸凹類型分成凸區域、凹區域，AAG中與之對應的即凸子圖、凹子圖，因此三維模型中凸凹區域的分割等價于對應的屬性鄰接圖的分割。我們可以將模型區域分割定義如下：

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

在分割中，我們希望實現凸區域和凹區域的合理劃分，其中凸凹子圖中節點和邊的凸凹性質與其子圖本身一致。在劃分中，凸節點劃分到凸子圖，凹節點劃分到凹子圖，而混合節點中既有相連的凸邊又有相連的凹邊，劃分起來比較麻煩，因此需要重新確定混合節點的凸凹性質。鑒于先識別凸子圖或者先識別凹子圖會得到不同的效果但又不會影響區域凸凹區域特征的表現，我們規定在分割時先識別并分離凸子圖，后識別并分離凹子圖[10]。

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

（1）根據節點凸凹性，通過圖的遍歷識別出G中所有混合節點，若無，則圖G中節點的凸凹性質一致，本身G就是一凸子圖或者凹子圖，將圖G=（V，E，A），輸出到區域H中；若存在混合節點，轉到步驟（2）；

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

（3）在剩余的子圖集中肯定存在凸子圖，可能存在凹子圖，因為本身混合節點就連接著凸邊和凹邊，刪除了與其連接的凹邊，必然剩下凸邊，否則與混合節點的定義相違背。將子圖集M輸出到H中；

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

（5）輸出分割結果H。

1.3 子區域局部匹配算法的實現

傳統的模型匹配算法大多按照CAD模型以及預匹配模型的B-rep信息，在大圖中搜索與小圖的拓撲與幾何相同的子圖。由于屬性鄰接圖中包含了模型每個面和邊的屬性信息，算法實現起來信息量大，效率不是很理想，區別能力有限。因此我們在CAD模型B-rep表示的基礎上，構建模型的屬性鄰接圖，提出模型表面區域分割的思想，經過分割后，模型被分解為凸凹子圖的集合 G={g1，g2，…，gu}，設預匹配子圖為 Q={q1，q2，…，qs}，下文中我們稱圖 G為大圖，預匹配子圖為小圖，分三種情況進行匹配，具體的匹配過程如下：

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

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

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

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

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

（5）若小圖Q由凹節點組成，即本身為一凹子圖，匹配過程類似凸子圖，過程如步驟（1）到（4）。

情況二：小圖為混合子圖

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

（1）通過圖的深度優先算法或寬度優先算法遍歷大圖G的各節點，判斷大圖是否也由凸凹節點組成，如果是，轉向步驟（2），反之，大圖中無匹配區域；

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

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

（4）任取M中的一個凸子圖，從vi開始遍歷與其相連的各邊，看是否與wj所連的相應的邊的屬性相同，若相同，則此凸子圖匹配成功，繼而重復步驟（2），進行下一小圖中的凸子圖的匹配；若在遍歷過程中，有屬性不一致的邊，則停止此次搜索，由于大圖中可能存在不止一個凸子圖中有與邊wj相同屬性的邊，因此，還需繼續重復步驟（2），直到與wj屬性相同的邊所在的凸子圖都遍歷完成，還無可匹配子圖，則結束匹配；

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

（6）由于小圖是由凸凹子圖組成，只有其凸凹子圖同時在大圖中找到相匹配的部分才能說明大圖中存在與小圖匹配的子結構。

2 實驗與分析

本節給出了采用本文方法得到的部分實驗結果：一個是根據凸凹性質的模型表面區域劃分；另外一個是基于凸凹子區域的局部匹配得到的檢索結果。

2.1 模型的凸凹區域分割

利用本文的方法，選取典型零件對其區域分割。圖1a所示為一個CAD模型經過表面區域分割后的結果，我們將同一區域的部分標記為同種顏色。該模型經過分割后共有五個區域，其中四個凹區域，一個凸區域；為了更好的顯示，圖1b中給出了該模型的拓撲連接圖，其中“+”表示面與面的連接邊為凸邊，“-”則為凹邊。工程中的正特征和負特征對于模型的特征表述以及制造加工具有重要的意義，而我們的凸區域和凹區域也和這兩種特征有一定的聯系。實驗可以看出，利用該方法能較好的實現CAD模型的區域分割，并且對于得到的分割區域具有一定的工程意義，為模型分析及下文的子區域匹配奠定了良好的基礎。

圖1 模型凸凹區域分割

2.2 基于凸凹子區域的局部匹配

圖2 典型結構

圖3 典型結構搜索結果

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

3 小結

局部結構的檢索在工程上具有一定的意義，也是模型檢索中一個難點問題[11]。幾何模型的數據結構只能表達產品的幾何拓撲關系，不能表達產品的非幾何信息，因而缺乏產品開發過程中所要求的工程語義信息[12]。本文在屬性鄰接圖的基礎上，提出一種基于凸凹子區域的局部匹配算法。首先按照模型的面和邊的屬性，經過一系列的處理將CAD模型分割成凸凹區域，也就相當于將其屬性鄰接圖分割成若干個凸凹子圖。在匹配過程中，將大圖與小圖中凸子圖與凸子圖，凹子圖與凹子圖分別匹配。通過判斷子區域是否相應匹配看大圖中是否含有預匹配的結構。本文算法不需逐邊逐面的采用子圖匹配算法來進行檢索。由于考慮模型的邊和面的幾何信息，更有利于模型結構的檢索[13]。但是屬性鄰接圖的構造是從模型的B-rep信息入手，這種采用單一特征描述方法喪失了空間分布信息，因此存在不完整性。如何將幾何和拓撲信息更好的來進行特征描述，并用于三維模型檢索，仍是今后需要研究的內容。

[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]王 玉，馬浩軍，何 瑋，等.機械三維CAD模型的聚類和檢索[J].計算機集成制造系統，2006，12（6）：924-928.

[3]胡琪波，何衛平，董 蓉，等.可重用MES模板檢索技術研究[J].鍛壓裝備與制造技術，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]王 飛，張樹生，白曉亮，等.基于子圖同構的三維CAD模型局部匹配 [J].計算機輔助設計與圖形學學報，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模型表面區域分割方法[J].計算機輔助設計與圖形學學報,2009.

[11]白 靜.面向設計重用的三維CAD模型檢索[D].浙江：浙江大學，2009.

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

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