白 柳， 宋超超

(1. 山西工程職業(yè)技術(shù)學(xué)院機(jī)械系，山西 太原 030009；2. 中國(guó)礦業(yè)大學(xué)(北京)機(jī)電與信息工程學(xué)院，北京 100083)

基于體素構(gòu)造和遺傳算法的三維模型檢索

白 柳1， 宋超超2

(1. 山西工程職業(yè)技術(shù)學(xué)院機(jī)械系，山西 太原 030009；2. 中國(guó)礦業(yè)大學(xué)(北京)機(jī)電與信息工程學(xué)院，北京 100083)

以體素構(gòu)造三維模型原理為基礎(chǔ)，闡述了體素的幾何信息和體素間的拓?fù)潢P(guān)系及基準(zhǔn)問(wèn)題，建立了三維模型特征提取函數(shù)，并對(duì)其旋轉(zhuǎn)、平移和尺寸變化進(jìn)行了經(jīng)典不變矩處理，提出了一種基于體素構(gòu)造和遺傳算法的三維模型檢索方法。該方法通過(guò)對(duì)遺傳信息編碼，以及迭代中的遺傳信息交叉與變異，減小了檢索區(qū)域的收斂速度，提高了檢索準(zhǔn)確率和檢索速度。

體素構(gòu)造；遺傳算法；特征提?。粰z索

隨著計(jì)算機(jī)輔助設(shè)計(jì)技術(shù)的飛速發(fā)展，三維模型應(yīng)用的領(lǐng)域變得越來(lái)越廣泛，其數(shù)量呈幾何式快速增長(zhǎng)。研究表明，約有 80%的模型是在原有模型的基礎(chǔ)上進(jìn)行小范圍的改動(dòng)，甚至是對(duì)原有模型的重用[1]。因此，如何快速、準(zhǔn)確地獲得相似度高的三維模型，是提高設(shè)計(jì)效率、縮短新產(chǎn)品研發(fā)周期的有效手段。三維模型檢索過(guò)程一般可分為：①提取目標(biāo)三維模型的檢索特征；②根據(jù)所提取的檢索特征確立唯一的特征函數(shù)；③與檢索庫(kù)中的三維模型進(jìn)行逐個(gè)比對(duì)；④根據(jù)特征相似度，按照由高到低的順序，排列出檢索到的三維模型。因此，如何有效地提取目標(biāo)三維模型的檢索特征、提高特征函數(shù)的確定性、增強(qiáng)檢索結(jié)果的準(zhǔn)確性、縮短檢索時(shí)間，是三維模型檢索過(guò)程中要解決的關(guān)鍵問(wèn)題?，F(xiàn)有三維模型的特征信息都是由幾何信息和拓?fù)湫畔⒔M成的，其幾何信息和拓?fù)湫畔⒌娜诤掀ヅ錂z索，是一種特征檢索重復(fù)度很低的三維模型檢索方式[2]。本文基于體素構(gòu)造和遺傳算法，提出了一種有別于蟻群算法、形態(tài)分布算法的三維模型檢索方法。與遺傳算法相比，蟻群算法的局部搜索能力較弱，容易出現(xiàn)檢索停滯、局部收斂和收斂速度過(guò)慢等情況，從而產(chǎn)生三維模型的具體細(xì)節(jié)檢索不到位、檢索成本較高等問(wèn)題。與遺傳算法相比，形態(tài)分布算法缺乏具體的數(shù)學(xué)模型，當(dāng)三維模型出現(xiàn)旋轉(zhuǎn)或者尺寸成比例變化時(shí)，其檢索結(jié)果可靠性較低。本文闡述的檢索特點(diǎn)在于描述三維模型的幾何信息和拓?fù)湫畔?，提取三維模型特征，建立特征函數(shù)，并對(duì)特征函數(shù)進(jìn)行不變矩處理，最后利用遺傳算法檢索，匹配到最優(yōu)的三維模型。

1 體素構(gòu)造三維模型

任何一個(gè)復(fù)雜的三維模型都可以看作是由 n個(gè)最為簡(jiǎn)單的基本體，經(jīng)過(guò)有序的布爾運(yùn)算構(gòu)成的，這些最簡(jiǎn)單的基本體稱為體素。體素包括長(zhǎng)方體、圓柱體、球體、楔形體、圓錐體和圓環(huán)體6種基本類型。

在利用計(jì)算機(jī)進(jìn)行輔助設(shè)計(jì)時(shí)，可運(yùn)用體素構(gòu)造三維模型方法提高設(shè)計(jì)的效率。任意一個(gè)復(fù)雜的三維模型，只需要確定其各個(gè)體素形狀的尺寸以及在空間中的相對(duì)位置，再輔以(n-1)個(gè)布爾算子來(lái)表示每一個(gè)體素加入整體三維模型的方式，就可以得到完整的三維模型幾何特征信息和拓?fù)涮卣餍畔3]。

1.1 三維模型幾何信息特征

根據(jù)自身構(gòu)成特點(diǎn)，每一種體素?fù)碛懈髯缘膸缀螀?shù)特征。

(1) 長(zhǎng)方體：長(zhǎng)a1、寬b1、高h(yuǎn)1、基準(zhǔn)為指定的定點(diǎn)位置；

(2) 圓柱體：半徑 r2、高 h2，基準(zhǔn)為一端面圓心；

(3) 球體：半徑r3，基準(zhǔn)為球心；

(4) 楔形體：毗鄰直角的三邊長(zhǎng)(a4、b4、c4)，基準(zhǔn)為其中一個(gè)直角點(diǎn)位置；

(5) 圓錐體：底面半徑r5，高h(yuǎn)5，基準(zhǔn)為底面圓心；

(6) 圓環(huán)體：圓環(huán)體中心圓半徑r6，截面圓半徑r7，基準(zhǔn)為中心圓半徑所在的圓心。

1.2 三維模型拓?fù)湫畔⑻卣?/p>

根據(jù)具體三維模型的結(jié)構(gòu)特點(diǎn)，將孤立的體素進(jìn)行有效地組合，確定體素之間的相對(duì)位置關(guān)系和具體體素?cái)?shù)量。為了有序地組合基本體素，形成有實(shí)際需求的具體三維模型，需要引入布爾運(yùn)算。在建模過(guò)程中，布爾運(yùn)算是通過(guò)對(duì)2個(gè)及2個(gè)以上的體素進(jìn)行并集、差集、交集運(yùn)算，從而得到新的模型。一般采用布爾運(yùn)算的樹狀結(jié)構(gòu)圖來(lái)形象、直觀地表現(xiàn)三維模型各個(gè)體素間的數(shù)量關(guān)系及拓?fù)潢P(guān)系[4]。三維模型樹狀結(jié)構(gòu)示例如圖1所示。

圖1 三維模型樹狀結(jié)構(gòu)

根據(jù)上述體素的布爾運(yùn)算，可得到體素與復(fù)雜三維模型的關(guān)系——體素拓?fù)潢P(guān)系樹其中，Pi為描述基于三維模型樹狀結(jié)構(gòu)圖中第i個(gè)體素和第i-1個(gè)體素的拓?fù)潢P(guān)系子向量。

在確定了體素組合關(guān)系的基礎(chǔ)上，需進(jìn)一步確定各體素基準(zhǔn)點(diǎn)相對(duì)于三維模型的具體位置。體素基準(zhǔn)關(guān)系包含拓?fù)潢P(guān)系特征的各個(gè)體素基準(zhǔn)向量，其表示為

根據(jù)上文所述，體素拓?fù)潢P(guān)系樹 P與體素基準(zhǔn)關(guān)系D共同決定了三維模型拓?fù)湫畔⑻卣鳌?/p>

2 三維模型特征提取

在三維模型特征提取過(guò)程中，定義三維模型的幾何信息特征為X，拓?fù)湫畔⑻卣鳛閅。因此，三維模型的特征信息可以描述為關(guān)于幾何特征信息X和拓?fù)涮卣餍畔的函數(shù)F(X,Y)。

在統(tǒng)計(jì)學(xué)中矩用來(lái)表示隨機(jī)變量的分布情況，而在物理學(xué)中用來(lái)表示物體在三維空間中的分布位置。如果把三維模型看作是體素在三維空間中帶有布爾運(yùn)算的有序分布，那么三維模型的特征就可以用矩來(lái)描述[5]。F(X,Y)的n+m階矩定義為

由此可知，pmn和F(X,Y)存在唯一確定的關(guān)系。F(X,Y)的m+n階中心距定義為

F(X,Y)的 m+n階中心距的中心坐標(biāo)為(X,Y)。F(X,Y)歸一化的中心矩可表示為

其中，u為F(X,Y)的0階中心距；m≥1；n≥1。

在三維模型的檢索過(guò)程中，F(xiàn)(X,Y)歸一化的中心矩主要討論其二階矩和三階矩，即在二維平面(m+n=2)、三維空間(m+n=3)的問(wèn)題[6]。針對(duì)三維模型檢索中出現(xiàn)的旋轉(zhuǎn)、平移和尺寸變化的情況，用以下7個(gè)經(jīng)典不變矩組作處理運(yùn)算[7]

3 遺傳算法在三維模型檢索中的應(yīng)用

在對(duì)三維模型提取的幾何特征信息和拓?fù)涮卣餍畔⒑瘮?shù)進(jìn)行不變矩處理后，可得到如下的一組特征向量

在容量較大的三維模型庫(kù)中，由于平移、旋轉(zhuǎn)和尺度變化等影響因素的存在，能夠檢索出相似度較高的三維模型是非常困難的。因此，本文在體素構(gòu)造三維模型原理的基礎(chǔ)上，提出了利用遺傳算法尋優(yōu)程序檢索最優(yōu)匹配三維模型的方法。遺傳算法尋優(yōu)程序能夠在設(shè)定的搜索范圍內(nèi)自適應(yīng)地搜索出最優(yōu)解，尤其是在這種高維度空間內(nèi)進(jìn)行檢索，能夠有效地改善檢索結(jié)果，縮短檢索時(shí)間[8]。

3.1 遺傳編碼

根據(jù)遺傳算法模擬生物遺傳變異的特點(diǎn)，針對(duì)三維模型幾何特征信息和拓?fù)涮卣餍畔?，選用二進(jìn)制遺傳編碼形式進(jìn)行編碼[9]，具有簡(jiǎn)單、方便、符合最小二進(jìn)制字符集編碼原則的優(yōu)點(diǎn)。幾何特征信息和拓?fù)涮卣餍畔?duì)三維模型的影響，可以用 F(X,Y)歸一化的中心矩 ρmn來(lái)表示。染色體C=(c1,c2,c3,…,cL)，是由ρmn二進(jìn)制轉(zhuǎn)換得到的長(zhǎng)度為L(zhǎng)的向量，其中向量元素c∈{0,1}。

3.2 適應(yīng)度函數(shù)選擇

適應(yīng)度是用來(lái)衡量種群中個(gè)體優(yōu)劣的指標(biāo)。在遺傳算法中，適應(yīng)度函數(shù)是通過(guò)比較排序來(lái)計(jì)算選擇概率的，所以適應(yīng)度函數(shù)值為正值。在檢索三維模型時(shí)，遺傳算法在尋優(yōu)過(guò)程中能夠通過(guò)不斷地自動(dòng)修正其參數(shù)值，得到最優(yōu)選擇，即對(duì)于個(gè)體的優(yōu)劣評(píng)判具有運(yùn)算自適應(yīng)性。其適應(yīng)度函數(shù)g(x)為

根據(jù)本文實(shí)例應(yīng)用中的具體要求，a值取0.5，b值為minF(x)，β值取2，α值取0.5。當(dāng)α等于0.5時(shí)，適應(yīng)度函數(shù)值能夠較為快速地反映出目標(biāo)函數(shù)的變化情況，在算法運(yùn)行后期，可以有效地拉開最優(yōu)解附近點(diǎn)的適應(yīng)度值，防止過(guò)早收斂，便于在較大范圍內(nèi)檢索匹配度最高的三維模型。

3.3 遺傳過(guò)程中的交叉與變異

遺傳過(guò)程中交叉的意義在于產(chǎn)生新的拓?fù)涮卣餍畔ⅲ綔y(cè)檢索區(qū)域里新的匹配三維模型。遺傳過(guò)程中變異能夠恢復(fù)丟失的遺傳信息，產(chǎn)生新的遺傳信息，保持檢索區(qū)域個(gè)體的多樣性，有效地防止算法過(guò)早收斂[9]。

3.4 遺傳算法步驟

利用遺傳算法進(jìn)行三維模型檢索，其具體算法步驟如下：

步驟1.T=0 ( T代表進(jìn)化代數(shù))；

步驟2. 對(duì)三維模型中心距參數(shù)ρmn進(jìn)行編碼；

步驟3. 隨機(jī)選擇初試種群P(T)；

步驟4. 個(gè)體的適應(yīng)度函數(shù)g(x)；

步驟5. 判別遺傳算法的終止條件(終止條件為達(dá)到最大的遺傳代數(shù)或者超過(guò)進(jìn)化要求的偏差)是否滿足，若滿足則直接進(jìn)行最后一步；

步驟6.T=T+1；

步驟7. 應(yīng)用選擇算子在P(T-1)中選擇P(T)；

步驟8. 對(duì)P(T)進(jìn)行交叉、變異操作，獲得新的遺傳信息后轉(zhuǎn)向步驟4；

步驟9. 輸出最優(yōu)的中心矩參數(shù)ρmn，進(jìn)而得到最優(yōu)三維模型幾何信息和拓?fù)湫畔ⅲ缓髮?duì)零件庫(kù)中的三維模型進(jìn)行測(cè)試以獲得最優(yōu)檢索結(jié)果[10]。

4 應(yīng)用實(shí)例與對(duì)比分析

三維模型檢索實(shí)驗(yàn)是在Open CASCADE平臺(tái)下的CAD三維模型庫(kù)中進(jìn)行的，檢索資源涉及到500多個(gè)三維模型。選擇庫(kù)中的一種脹緊聯(lián)接套作為檢索目標(biāo)，遺傳算法檢索參數(shù)設(shè)置如下：染色體種群規(guī)模Spop=300，交叉概率Pcros=0.5，變異概率Pmu=0.1t，最大迭代次數(shù)maxiter=500。

其相似度大于0.1的檢索結(jié)果如圖2所示，在三維模型檢索庫(kù)容量較大的情況下，依然能夠檢索到相似度比較高的三維模型。編號(hào)01的三維模型與目標(biāo)三維模型相比較，都是含有環(huán)狀分布的圓柱、兩個(gè)半徑不同的圓環(huán)體的 3段結(jié)構(gòu)，具有非常高的相似特征和局部結(jié)構(gòu)的重復(fù)度。編號(hào) 12的三維模型在圖中相似度最低，主要是由于在特征提取過(guò)程中，環(huán)狀分布的圓柱布爾運(yùn)算從并集運(yùn)算變異為差集運(yùn)算。

在相同的檢索條件下，查全率分別為 10%、20%、50%、80%、100%時(shí)，遺傳算法、蟻群算法、形態(tài)分布算法分別檢索到的最優(yōu)相似度三維模型如圖3所示[1,11]。從檢索的相似度值分析，在查全率為10%時(shí)，即只在Open CASCADE庫(kù)中檢索50多個(gè)三維模型，3種方法能夠檢索到相同的最優(yōu)三維模型。當(dāng)查全率增高時(shí)，蟻群算法和形態(tài)分布算法檢索到的最優(yōu)模型相似度比遺傳算法低。由此可知，在檢索范圍變大、檢索特征信息干擾因素增多的情況下，遺傳算法相比于其他兩種檢索方法，具有更可靠的特征提取匹配性能。

圖2 遺傳算法檢索結(jié)果

圖3 3種算法檢索結(jié)果比較

為了進(jìn)一步驗(yàn)證遺傳算法在三維模型檢索過(guò)程中的實(shí)用價(jià)值，采用了最為常用的查全率-查準(zhǔn)率、查全率-檢索時(shí)間作為檢索結(jié)果的評(píng)價(jià)依據(jù)，其結(jié)果分別如圖4～5所示。

圖4 查全率-查準(zhǔn)率

圖5 查全率-檢索時(shí)間

由圖 4～5可知，相比于蟻群算法和形態(tài)分布算法，遺傳算法具有更準(zhǔn)確的檢索結(jié)果和更高的檢索效率，但是在查全率較低的范圍內(nèi)，其查準(zhǔn)率與檢索時(shí)間并不具有明顯優(yōu)勢(shì)。

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

本文根據(jù)三維模型的體素構(gòu)造原理和遺傳算法尋優(yōu)程序，提出了一種新的三維模型檢索方法。該方法在體素構(gòu)造原理的基礎(chǔ)上，利用三維模型的幾何特征信息和拓?fù)涮卣餍畔?，提取三維模型的特征函數(shù)，并根據(jù)檢索過(guò)程中出現(xiàn)的模型平移、旋轉(zhuǎn)、尺寸變化等情況，對(duì)特征函數(shù)進(jìn)行不變矩處理，最后利用遺傳算法實(shí)現(xiàn)三維模型的最優(yōu)相似度檢索。實(shí)驗(yàn)結(jié)果表明，在相同的檢索條件下，遺傳算法的查準(zhǔn)率和檢索時(shí)間都優(yōu)于蟻群算法、形態(tài)分布算法等其他檢索算法。因此，在三維模型檢索領(lǐng)域，基于體素構(gòu)造和遺傳算法的三維模型檢索方法具有更高的效率和可靠性能。

[1] 張開興, 張樹生, 李 亮. 基于蟻群算法的三維CAD模型檢索[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2011, 23(4): 633-639.

[2] Stavropoulos G, Moschonas P, Moustakas K, et al. 3-D model search and retrieval from range images using salient features [J]. IEEE Transactions on Multimedia, 2010, 12(7): 692-704.

[3] 張申生. 基于單元分解的實(shí)體構(gòu)造幾何技術(shù)(CDCSG)——一種構(gòu)造試題模型的新方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1990, 1(2): 14-23.

[4] 鄧念東, 侯恩科, 張志華, 等. 三維拓?fù)潢P(guān)系形式化描述及拓?fù)潢P(guān)系模型研究[J]. 西安建筑科技大學(xué)學(xué)報(bào), 2007, 39(6): 873-877.

[5] 邵 紅, 崔文成, 張繼武, 等. 遺傳算法在基于內(nèi)容的圖像檢索中的應(yīng)用[J]. 計(jì)算機(jī)工程, 2003, 29(16): 21-22.

[6] Chen C, Leng B, Xiong Z. A stable viewing strategy for rotation normalization free 3D model retrieval [J]. Procedia Environmental Sciences, 2011, 10(Part A): 613-621.

[7] 何 青, 杜永祚, 宋之平. 一種實(shí)用的不變矩計(jì)算方法[J]. 華北電力大學(xué)學(xué)報(bào), 1998, 25(4): 80-83.

[8] 李 亮, 張樹生, 白曉亮, 等. 基于遺傳算法的三維CAD模型多特征融合和檢索[J]. 制造業(yè)自動(dòng)化, 2013, 35(2): 78-81.

[9] 沈 艷, 郭 兵, 古天祥. 粒子群優(yōu)化算法及其與遺傳算法的比較[J]. 電子科技大學(xué)學(xué)報(bào), 2005, 34(5): 696-699.

[10] Ding B, Zhang Z, Yu X Y, et al. 3D CAD model retrieval based on GA-ACO [C]//Ulaanbaatar. Strategic Technology (IFOST). New York: IEEE Press, 2013: 36-41.

[11] 朱文博, 吳新仁, 甘 屹. 基于形狀拆分的機(jī)械零件三維模型檢索[J]. 圖學(xué)學(xué)報(bào), 2015, 36(1): 35-40.

3D Model Retrieval Based on CGS and Genetic Algorithm

Bai Liu1, Song Chaochao2
(1. Department of Mechanical Engineering, Shanxi Engineering Vocation Technology College, Taiyuan Shanxi 030009, China; 2. College of Mechanical Electrical and Information Engineering, China University of Mining and Technology (Beijing), Beijing 100083, China)

The voxels structure principle of 3D model as the foundation, expounds the voxel geometry information and body elements of topological relations and benchmark problems, establish the 3D model feature extraction function and of its rotation, translation and size changes of classic moment invariant processing, put forward a based on voxel structure and genetic algorithm of 3D model retrieval method. This method reduces the convergence speed of the search area and improves the retrieval accuracy and retrieval speed by the genetic information encoding, the genetic information in the iteration and the variation of the genetic information.

constructice solid geometry; genetic algorithm; feature extraction; retrieval

TH 128；TB 23

10.11996/JG.j.2095-302X.2016060754

A

2095-302X(2016)06-0754-05

2016-01-25；定稿日期：2016-05-24

白 柳(1964?)，女，山西太谷人，副教授，碩士。主要研究方向?yàn)楣こ虉D學(xué)、CAD/CAM 應(yīng)用等。E-mail：sxtybliu@163.com