三維CAD模型檢索方法的優(yōu)化研究*

田 柳，徐賜軍，黃 浩，張紹峰，陳 磊

(1.武漢科技大學 機械自動化學院,湖北 武漢 430081;2.湖北理工學院 機電工程學院,湖北 黃石 435003)

0 引 言

CAD技術(shù)已廣泛地應用于工程設計的各個領域，尤其是在機械行業(yè)，CAD建模已成為機械產(chǎn)品設計、制造等各個環(huán)節(jié)的重要步驟。

隨著企業(yè)的產(chǎn)品更新，企業(yè)擁有CAD模型數(shù)量也在日益增加[1]。三維CAD模型的重用技術(shù)應用滿足了設計人員重新繪圖和建模等需求，提高了產(chǎn)品的設計效率。

徐賜軍等[2]結(jié)合機械結(jié)構(gòu)形態(tài)相關知識，提出了基于機械結(jié)構(gòu)形態(tài)的三維CAD模型檢索方法；XU L等[3]針對復雜的三維模型，基于局部細節(jié)特征的相似性比較來評估CAD模型，提高了三維模型的檢索效率，但是部分模型檢索的準確率有所下降；TASHIRO S等[4]采用具有尺度和旋轉(zhuǎn)不變性的興趣點來提取超向量編碼特征，實現(xiàn)了對三維模型的檢索;SIDDIQU A A等[5]開發(fā)了一種自動編碼器，進行了語義建模以實現(xiàn)三維模型的檢索。

隨著大數(shù)據(jù)應用的發(fā)展，出現(xiàn)了分布式計算、分布式服務器集群、分布式存儲等技術(shù)，大大改善了大數(shù)據(jù)的處理效率，分布式技術(shù)已成為了各研究領域的熱點。LI B等[6]運用分布式檢索技術(shù)，基于Hadoop建造的檢索系統(tǒng)，使用戶可以從海量的信息檢索數(shù)據(jù)中找到所需的答案；郭飛等[7]提出了一種基于HDFS和傳統(tǒng)關系型數(shù)據(jù)庫相結(jié)合的圖像及其特征數(shù)據(jù)的存儲結(jié)構(gòu)設計方法,實現(xiàn)了海量圖像信息的快速存儲和讀取，降低了圖像檢索時間;楊進展[8]部署了一個具有HDFS和MapReduce分布式三維模型管理系統(tǒng)；廖先富[9]基于Hadoop的HDFS文件存儲功能與Django技術(shù)，構(gòu)建了一個云端分布式三維數(shù)據(jù)存儲系統(tǒng)。

隨著模型庫三維CAD模型數(shù)量的增多，單臺計算機算力不足的問題成為檢索的瓶頸。三維CAD模型檢索系統(tǒng)檢索需要的時間越來越多，分布式計算成為優(yōu)化三維CAD模型檢索方法的首選。

針對三維CAD模型檢索效率問題，筆者采用機械結(jié)構(gòu)形態(tài)知識[10]及分布式計算技術(shù)，研究協(xié)同設計環(huán)境下三維CAD模型檢索方法的優(yōu)化。

1 三維模型檢索框架

基于機械結(jié)構(gòu)形態(tài)和分布式計算的三維模型檢索系統(tǒng)以機械結(jié)構(gòu)形態(tài)為主要特征，以分布式計算技術(shù)為主要工具。

基于機械結(jié)構(gòu)形態(tài)和分布式計算的三維CAD模型檢索方法，其框圖如圖1所示。

圖1 三維模型檢索框架

圖1中：

(1)基礎模塊主要功能是通過基本體轉(zhuǎn)換模型實現(xiàn)機械結(jié)構(gòu)三維模型和機械結(jié)構(gòu)形態(tài)的相互轉(zhuǎn)換；

(2)數(shù)據(jù)整理模塊主要是對基礎模塊中的機械結(jié)構(gòu)形態(tài)庫進行處理，以獲取用于后續(xù)分布式計算的數(shù)據(jù)表，主要研究機械結(jié)構(gòu)形態(tài)庫中的模型相似度分組方法，并將模型的分組結(jié)果存儲于數(shù)據(jù)庫中；

(3)優(yōu)化檢索模塊主要是分布式計算技術(shù)在三維模型檢索中的應用，即對數(shù)據(jù)處理模塊產(chǎn)生的數(shù)據(jù)進行處理；

(4)應用模塊主要根據(jù)模型檢索需要選擇合適的指標實現(xiàn)三維模型的檢索。

分布式計算是基于機械結(jié)構(gòu)形態(tài)的三維模型相似度比較方法，結(jié)合MapReduce分布式計算編程模型，將模型相似性比較過程分為Map階段和Reduce階段，并經(jīng)過分布式計算輸出模型ID與相似度的鍵值對，獲取模型ID所對應的機械結(jié)構(gòu)形態(tài)和三維模型。

因此，圖1中的三維模型檢索框架是基于機械結(jié)構(gòu)形態(tài)的三維CAD模型檢索方法，該方法采用數(shù)據(jù)整理模塊和優(yōu)化檢索模塊對其檢索算法進行優(yōu)化。

2 模型相似鏈

基于機械結(jié)構(gòu)形態(tài)的三維CAD模型檢索方法，可大幅度提升模型檢索的效率，但是在三維模型檢索過程中模型庫中的所有模型都需要參與相似度計算，大大增加了計算量。機械結(jié)構(gòu)模型庫往往存在許多只有少許細節(jié)不同的機械結(jié)構(gòu)，若將這一系列的機械結(jié)構(gòu)模型分成一組，構(gòu)成模型相似鏈，則當遇到類似的機械結(jié)構(gòu)進行檢索時，待檢索模型僅與該集合中每個模型進行相似度計算，可大大減少不必要的比較過程和計算。

模型相似鏈是指彼此之間相似度較高的機械結(jié)構(gòu)的模型集合，并以模型編號表示。當待檢測機械結(jié)構(gòu)模型與相似鏈中的某個機械結(jié)構(gòu)模型相似度較高時，說明待檢測機械結(jié)構(gòu)模型與相似鏈中其他機械結(jié)構(gòu)模型相似度高的可能性較大；相反，當待檢測機械結(jié)構(gòu)模型與相似鏈中的某個機械結(jié)構(gòu)模型相似度較低時，說明待檢測機械結(jié)構(gòu)模型與相似鏈中其他機械結(jié)構(gòu)模型相似度低的可能性較大。

因此，只將待檢測機械結(jié)構(gòu)模型與相似度高可能性大的相似鏈中的模型進行比較，不與相似度低可能性大的相似鏈中的模型進行比較，可以大大減少比較次數(shù)。

模型相似鏈基于所有模型的相似性比較矩陣的相似度進行分組，模型相似性比較矩陣即是記錄模型庫中三維模型之間的相似度。

n個機械結(jié)構(gòu)三維模型的相似性比較矩陣如圖2所示。

IDa1……ai……aj……ana11……S1i……S1j……S1n…………1…………………………aiSi1……1……Sij……Sin……………………1………………ajSj1……Sji……1……Sjn………………………………1……anSn1……Sni……Snj……1

本文采用基于機械結(jié)構(gòu)形態(tài)的三維模型相似度計算方法，構(gòu)建三維CAD模型的相似性比較矩陣，以便于模型相似鏈構(gòu)建過程中進行遍歷和篩選數(shù)據(jù)。

若將所有模型ID組成集合A，令A中有n個元素，ID分別為a1、a2、a3…，則數(shù)據(jù)庫模型相似鏈構(gòu)建流程如圖3所示。

圖3 數(shù)據(jù)庫模型相似鏈構(gòu)建過程向下取整，即小于或等于的最大整數(shù)；Bi—第i條相似鏈，Bij—第i條相似鏈的第j個元素;SH—表示模型相似鏈元素構(gòu)建的相似度閾值，一般取表示相似鏈規(guī)模的控制值，其目的是保證相似鏈構(gòu)建效率，能夠有效控制一條相似鏈的長度，如果一條相似鏈過長，會導致在后續(xù)對相似鏈所有元素進行相似度計算時計算量過大

3 分布式計算

分布式系統(tǒng)是多個處理機通過通信線路互聯(lián)而構(gòu)成的松散耦合的系統(tǒng)，通過網(wǎng)絡相互連接傳遞消息與通信后并協(xié)調(diào)行為，且組件之間彼此交互以實現(xiàn)一個共同的目標；把需要進行大量計算的工程數(shù)據(jù)分割成小塊，由多臺計算機分別計算，然后上傳運算結(jié)果，并將結(jié)果統(tǒng)一合并產(chǎn)生數(shù)據(jù)結(jié)論。

分布式計算過程如圖4所示。

圖4 分布式計算過程

該模型將輸入工作劃分為多個小塊，并行計算，并將得出的結(jié)果進行匯總，最終產(chǎn)生計算結(jié)果。其中，map1表示待檢索模型與第一條相似鏈中元素進行相似度計算，計算得出的map(id，score)即為模型id和相對應的相似度。

首先是待檢索模型與每個相似鏈的相似度計算，將每組的運算過程為一個Map階段，每個Map可并行進行計算；然后將Map的運算結(jié)果自動上傳到Reduce，Reduce將所有鍵值對傳入全局變量散列表N中，散列表N是用來記錄鍵值映射關系的數(shù)據(jù)結(jié)構(gòu)，可存儲三維模型ID與相似度的映射關系；最后通過對N中的數(shù)據(jù)進行值排序得到相似度高的三維模型ID，通過ID映射到機械結(jié)構(gòu)形態(tài)庫和三維模型形態(tài)庫，輸出檢索到的三維模型，完成檢索。

Map函數(shù)主要邏輯運行調(diào)用相似度計算方法，經(jīng)過相似度計算后，輸出(id，score)，即(序號，相似度)鍵值對；經(jīng)過MapReduce框架自動將鍵值對數(shù)據(jù)傳入Reduce階段。

令模型數(shù)據(jù)庫共有m個模型相似鏈Bi，且令初始值i=1，j=1，則Map階段運算過程如下。

步驟1：當i≤m時，將待檢索模型與Bi中第j個元素進行相似度計算，即Sij；否則過程終止；

步驟2：若Sij≥SH(SH—相似度上限值，一般取0.6)，則待檢索模型可以與模型相似鏈Bi其他模型進行相似性比較，即該鏈為可用鏈，進行下一步；若Si≤SL(為相似度下限值，一般取0.2)，則待檢索模型不與模型相似鏈Bi中其他模型進行相似性比較，即該鏈為不可用鏈，i=i+1返回步驟1；若SL≤Sij≤SH，則當j<3時j=j+1，返回步驟1；當j>1時i=i+1，j=1，返回步驟1；

步驟3：將可用鏈中所有模型與待檢索模型進行相似度計算，計算出的鍵值對(id，score)上傳至Reduce處理；

步驟4：若i>m，則結(jié)束Map運算，否則返回步驟1。

4 實驗驗證

此處以美國普渡大學開發(fā)的ESB模型庫為基礎數(shù)據(jù)進行實驗驗證。ESB中包含866個STL格式的工程模型，筆者以其中任意1個模型作為輸入，以檢索出模型庫中相似的模型。

實驗采用的PC機參數(shù)為：Intel?Core (TM) i7-7700HQ@2.80 GHz CP，分布式Slave1 內(nèi)存2 GB；Slave2 內(nèi)存2 GB；Master內(nèi)存2 GB。

以ESB模型庫[11]ganter_din6304號模型機械結(jié)構(gòu)形態(tài)為例，其相似度計算結(jié)果如表1所示。

表1 機械結(jié)構(gòu)形態(tài)相似度

表1中，元素值越大說明三維模型之間的相似度越高。

同理，在三維模型數(shù)據(jù)庫構(gòu)建過程中，基于機械結(jié)構(gòu)形態(tài)的三維模型相似度比較算法，獲得的模型庫中三維模型的相似性表矩陣，如圖5所示。

ID12345678110.890.430.360.30.470.490.420.8910.720.360.390.330.020.2630.430.7210.50.760.430.720.7840.360.360.510.430.660.520.6350.30.390.760.4310.390.390.7760.470.330.430.660.3910.630.2670.490.020.720.520.390.6310.2280.40.260.780.630.770.260.221

圖5中，模型1表示ganter_din6304-m20-110-f1，模型2表示ganter_din6304-m8-50-f1。

模型庫相似鏈存儲表如圖6所示。

12345679101129182627364223123578133334973461224338996410112539469811811954474129145164175176

由圖6第1行數(shù)據(jù)可以看出，1號模型與2號模型在同1條相似鏈中。

圖6中行表頭表示相似鏈ID，列表頭表示相似鏈中的元素索引，表中數(shù)據(jù)表示模型id。

圖5模型相似性比較矩陣生成圖6相似鏈的過程如下：第1行中，1為第1條相似鏈的第1個元素，繼續(xù)遍歷得到與1號模型相似度大于0.6的模型ID，分別為2號、9號等模型，故集合[1,2,9,18…]為1條相似鏈；第2行中，1、2均被剔除，故第2條相似鏈從3開始，集合[3,5,7,8…]為1條相似鏈，繼續(xù)生成多條相似鏈。

在進行和模型檢索時，只需根據(jù)流程先和1號、2號模型進行相似度計算，即可確定該相似鏈是否可用。若為可用相似鏈，則與后續(xù)9號、18號等模型繼續(xù)進行相似度計算；若為不可用鏈，則直接跳過該鏈，繼續(xù)判斷下一條相似鏈是否可用。

例如：待檢索模型為1號模型，1號模型與1號相似鏈相似度為1，相似度大于0.6，則1號相似鏈為可用鏈，可與該相似鏈后續(xù)元素繼續(xù)比較。1號模型與2號、3號、4號相似鏈相似度均小于0.6，則這3條相似鏈為不可用鏈，簡化檢索流程，以提高檢索效率。

本文算法與文獻[2]算法查準率與查全率曲線圖如圖7所示。

圖7 查準率-查全率曲線圖

圖7顯示，本文算法的查準率查全率與文獻[2]算法基本一致，說明基于機械結(jié)構(gòu)形態(tài)三維模型檢索的準確率較高。

筆者隨機選取3個模型ganter_din6305-M20、Nozag_bfi_60，以及winkel_ap，分別使用文獻[2]檢索算法和本文算法進行比較，其結(jié)果如表2所示。

表2 檢索算法的結(jié)果比較

由表2可知：本文算法與文獻[2]算法所獲檢索結(jié)果大致相同，但是本算法的檢索時間明顯較短，檢索效率較高。

由此可見，通過模型相似性比較矩陣和相似鏈等技術(shù)的應用，三維模型的檢索效率可以獲得提升。

5 結(jié)束語

三維模型的重用是提升機械產(chǎn)品開發(fā)效率的重要途徑，三維模型檢索是實現(xiàn)三維模型重用的重要方法；但是隨著三維CAD模型庫模型數(shù)量的增加，導致檢索效率大幅度降低。

為了保證檢索效率，本文針對三維模型檢索的需求，分析了基于機械結(jié)構(gòu)形態(tài)的三維CAD模型檢索的特點，提出了模型相似性比較矩陣、相似鏈兩個概念，以簡化模型檢索過程；并給出了模型相似性比較矩陣、相似鏈的計算以及使用方法；結(jié)合分布式系統(tǒng)架構(gòu)提出的分布式計算方法，實現(xiàn)了基于機械結(jié)構(gòu)形態(tài)的三維CAD模型檢索分布式計算系統(tǒng)的搭建；通過簡化模型檢索過程和使用集群代替單機以解決單機算力瓶頸問題的方法，完成了對三維CAD模型檢索方法的優(yōu)化。

實例驗證的結(jié)果表明：該方法能夠在保證檢索精度的條件下，顯著減少三維模型的檢索時間，檢索效率獲得了提升。