基于體素構造和遺傳算法的三維模型檢索

白 柳， 宋超超

(1. 山西工程職業技術學院機械系，山西 太原 030009；2. 中國礦業大學(北京)機電與信息工程學院，北京 100083)

基于體素構造和遺傳算法的三維模型檢索

白 柳1， 宋超超2

(1. 山西工程職業技術學院機械系，山西 太原 030009；2. 中國礦業大學(北京)機電與信息工程學院，北京 100083)

以體素構造三維模型原理為基礎，闡述了體素的幾何信息和體素間的拓撲關系及基準問題，建立了三維模型特征提取函數，并對其旋轉、平移和尺寸變化進行了經典不變矩處理，提出了一種基于體素構造和遺傳算法的三維模型檢索方法。該方法通過對遺傳信息編碼，以及迭代中的遺傳信息交叉與變異，減小了檢索區域的收斂速度，提高了檢索準確率和檢索速度。

體素構造；遺傳算法；特征提取；檢索

隨著計算機輔助設計技術的飛速發展，三維模型應用的領域變得越來越廣泛，其數量呈幾何式快速增長。研究表明，約有 80%的模型是在原有模型的基礎上進行小范圍的改動，甚至是對原有模型的重用[1]。因此，如何快速、準確地獲得相似度高的三維模型，是提高設計效率、縮短新產品研發周期的有效手段。三維模型檢索過程一般可分為：①提取目標三維模型的檢索特征；②根據所提取的檢索特征確立唯一的特征函數；③與檢索庫中的三維模型進行逐個比對；④根據特征相似度，按照由高到低的順序，排列出檢索到的三維模型。因此，如何有效地提取目標三維模型的檢索特征、提高特征函數的確定性、增強檢索結果的準確性、縮短檢索時間，是三維模型檢索過程中要解決的關鍵問題。現有三維模型的特征信息都是由幾何信息和拓撲信息組成的，其幾何信息和拓撲信息的融合匹配檢索，是一種特征檢索重復度很低的三維模型檢索方式[2]。本文基于體素構造和遺傳算法，提出了一種有別于蟻群算法、形態分布算法的三維模型檢索方法。與遺傳算法相比，蟻群算法的局部搜索能力較弱，容易出現檢索停滯、局部收斂和收斂速度過慢等情況，從而產生三維模型的具體細節檢索不到位、檢索成本較高等問題。與遺傳算法相比，形態分布算法缺乏具體的數學模型，當三維模型出現旋轉或者尺寸成比例變化時，其檢索結果可靠性較低。本文闡述的檢索特點在于描述三維模型的幾何信息和拓撲信息，提取三維模型特征，建立特征函數，并對特征函數進行不變矩處理，最后利用遺傳算法檢索，匹配到最優的三維模型。

1 體素構造三維模型

任何一個復雜的三維模型都可以看作是由 n個最為簡單的基本體，經過有序的布爾運算構成的，這些最簡單的基本體稱為體素。體素包括長方體、圓柱體、球體、楔形體、圓錐體和圓環體6種基本類型。

在利用計算機進行輔助設計時，可運用體素構造三維模型方法提高設計的效率。任意一個復雜的三維模型，只需要確定其各個體素形狀的尺寸以及在空間中的相對位置，再輔以(n-1)個布爾算子來表示每一個體素加入整體三維模型的方式，就可以得到完整的三維模型幾何特征信息和拓撲特征信息[3]。

1.1 三維模型幾何信息特征

根據自身構成特點，每一種體素擁有各自的幾何參數特征。

(1) 長方體：長a1、寬b1、高h1、基準為指定的定點位置；

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

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

(4) 楔形體：毗鄰直角的三邊長(a4、b4、c4)，基準為其中一個直角點位置；

(5) 圓錐體：底面半徑r5，高h5，基準為底面圓心；

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

1.2 三維模型拓撲信息特征

根據具體三維模型的結構特點，將孤立的體素進行有效地組合，確定體素之間的相對位置關系和具體體素數量。為了有序地組合基本體素，形成有實際需求的具體三維模型，需要引入布爾運算。在建模過程中，布爾運算是通過對2個及2個以上的體素進行并集、差集、交集運算，從而得到新的模型。一般采用布爾運算的樹狀結構圖來形象、直觀地表現三維模型各個體素間的數量關系及拓撲關系[4]。三維模型樹狀結構示例如圖1所示。

圖1 三維模型樹狀結構

根據上述體素的布爾運算，可得到體素與復雜三維模型的關系——體素拓撲關系樹其中，Pi為描述基于三維模型樹狀結構圖中第i個體素和第i-1個體素的拓撲關系子向量。

在確定了體素組合關系的基礎上，需進一步確定各體素基準點相對于三維模型的具體位置。體素基準關系包含拓撲關系特征的各個體素基準向量，其表示為

根據上文所述，體素拓撲關系樹 P與體素基準關系D共同決定了三維模型拓撲信息特征。

2 三維模型特征提取

在三維模型特征提取過程中，定義三維模型的幾何信息特征為X，拓撲信息特征為Y。因此，三維模型的特征信息可以描述為關于幾何特征信息X和拓撲特征信息Y的函數F(X,Y)。

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

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

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

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

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

3 遺傳算法在三維模型檢索中的應用

在對三維模型提取的幾何特征信息和拓撲特征信息函數進行不變矩處理后，可得到如下的一組特征向量

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

3.1 遺傳編碼

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

3.2 適應度函數選擇

適應度是用來衡量種群中個體優劣的指標。在遺傳算法中，適應度函數是通過比較排序來計算選擇概率的，所以適應度函數值為正值。在檢索三維模型時，遺傳算法在尋優過程中能夠通過不斷地自動修正其參數值，得到最優選擇，即對于個體的優劣評判具有運算自適應性。其適應度函數g(x)為

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

3.3 遺傳過程中的交叉與變異

遺傳過程中交叉的意義在于產生新的拓撲特征信息，探測檢索區域里新的匹配三維模型。遺傳過程中變異能夠恢復丟失的遺傳信息，產生新的遺傳信息，保持檢索區域個體的多樣性，有效地防止算法過早收斂[9]。

3.4 遺傳算法步驟

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

步驟1.T=0 ( T代表進化代數)；

步驟2. 對三維模型中心距參數ρmn進行編碼；

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

步驟4. 個體的適應度函數g(x)；

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

步驟6.T=T+1；

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

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

步驟9. 輸出最優的中心矩參數ρmn，進而得到最優三維模型幾何信息和拓撲信息，然后對零件庫中的三維模型進行測試以獲得最優檢索結果[10]。

4 應用實例與對比分析

三維模型檢索實驗是在Open CASCADE平臺下的CAD三維模型庫中進行的，檢索資源涉及到500多個三維模型。選擇庫中的一種脹緊聯接套作為檢索目標，遺傳算法檢索參數設置如下：染色體種群規模Spop=300，交叉概率Pcros=0.5，變異概率Pmu=0.1t，最大迭代次數maxiter=500。

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

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

圖2 遺傳算法檢索結果

圖3 3種算法檢索結果比較

為了進一步驗證遺傳算法在三維模型檢索過程中的實用價值，采用了最為常用的查全率-查準率、查全率-檢索時間作為檢索結果的評價依據，其結果分別如圖4～5所示。

圖4 查全率-查準率

圖5 查全率-檢索時間

由圖 4～5可知，相比于蟻群算法和形態分布算法，遺傳算法具有更準確的檢索結果和更高的檢索效率，但是在查全率較低的范圍內，其查準率與檢索時間并不具有明顯優勢。

5 結 束 語

本文根據三維模型的體素構造原理和遺傳算法尋優程序，提出了一種新的三維模型檢索方法。該方法在體素構造原理的基礎上，利用三維模型的幾何特征信息和拓撲特征信息，提取三維模型的特征函數，并根據檢索過程中出現的模型平移、旋轉、尺寸變化等情況，對特征函數進行不變矩處理，最后利用遺傳算法實現三維模型的最優相似度檢索。實驗結果表明，在相同的檢索條件下，遺傳算法的查準率和檢索時間都優于蟻群算法、形態分布算法等其他檢索算法。因此，在三維模型檢索領域，基于體素構造和遺傳算法的三維模型檢索方法具有更高的效率和可靠性能。

[1] 張開興, 張樹生, 李 亮. 基于蟻群算法的三維CAD模型檢索[J]. 計算機輔助設計與圖形學學報, 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] 張申生. 基于單元分解的實體構造幾何技術(CDCSG)——一種構造試題模型的新方法[J]. 計算機輔助設計與圖形學學報, 1990, 1(2): 14-23.

[4] 鄧念東, 侯恩科, 張志華, 等. 三維拓撲關系形式化描述及拓撲關系模型研究[J]. 西安建筑科技大學學報, 2007, 39(6): 873-877.

[5] 邵 紅, 崔文成, 張繼武, 等. 遺傳算法在基于內容的圖像檢索中的應用[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] 何 青, 杜永祚, 宋之平. 一種實用的不變矩計算方法[J]. 華北電力大學學報, 1998, 25(4): 80-83.

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

[9] 沈 艷, 郭 兵, 古天祥. 粒子群優化算法及其與遺傳算法的比較[J]. 電子科技大學學報, 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]. 圖學學報, 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?)，女，山西太谷人，副教授，碩士。主要研究方向為工程圖學、CAD/CAM 應用等。E-mail：sxtybliu@163.com