石 民，張樹生，李 亮，白曉亮

SHI Min, ZHANG Shu-sheng, LI Liang, BAI Xiao-liang

（西北工業(yè)大學 現(xiàn)代設計與集成制造技術教育部重點實驗室，西安 710072）

0 引言

在目前的機械設計制造領域，基于三維模型的產(chǎn)品設計與制造已經(jīng)成為當前的主流模式，被廣泛應用在產(chǎn)品開發(fā)的各個環(huán)節(jié)（CAD、CAE、CAPP、CAM等）。統(tǒng)計數(shù)據(jù)表明，在新產(chǎn)品的研發(fā)過程中有超過75%的設計活動都是對已有的設計進行重用或微小修改[1]?；趦?nèi)容的三維CAD模型檢索技術能夠幫助企業(yè)對已有的產(chǎn)品設計成果進行管理和重用，進而提高設計效率，縮短研發(fā)周期，并最終有效地提升企業(yè)的核心競爭力。

對于基于內(nèi)容的三維模型CAD檢索技術，它的關鍵問題之一是如何有效描述CAD模型的形狀特征，其對于檢索結果的精度和準度有著直接影響[2]。目前，基于視覺相似的三維模型檢索算法被認為是檢索效果最好的一類算法[3,4]，該類算法仿效了人類視覺對物體的認知過程，將三維模型表示為所對應的二維投影視圖的集合。這樣一來，兩個三維模型之間的比較就轉化為各自投影集合中所對應的二維投影視圖之間的比較。如果所對應的二維投影視圖都相似，則認為這兩個模型相似。該類算法中最著名的為Chen等提出的光場算法[5]。然而，在使用投影視圖對三維模型進行相似性匹配時，光場算法只是籠統(tǒng)地對視圖集中的每一幅視圖都同等看待，卻忽視了不同視圖在匹配過程中其實具有不同的重要性。相較于其它視圖，模型的某些投影視圖包含更多的信息，因而更能影響模型間的相似性匹配。從圖1可以很明顯地看出，螺絲刀的主視圖相較于它的俯視圖含有更多的信息，對于模型來說更具有代表性。因此，區(qū)別對待每個視圖在模型相似性匹配過程中的重要程度是十分必要的。Li[6]等提出了一種基于二維投影視圖最優(yōu)權重的三維模型檢索算法。該算法通過使用拉格朗日乘數(shù)子和支持向量機為視圖配置權重，以達到區(qū)分不同視圖重要性的目的。

本文提出一種基于二維典型視圖的三維CAD模型檢索算法，該算法通過從CAD模型二維投影視圖集中甄選出其中具有代表性（即信息含量高）的視圖， 將三維模型間的比較轉化為各自典型視圖間的相似性匹配。首先對一個三維CAD模型沿固定視角進行投影，獲得相應的二維投影視圖集；然后采用Apriori算法從中挖掘出具有代表性的視圖作為該模型的典型視圖； 最后通過比較模型各自對應的典型視圖來獲得三維模型間的相似性評價。

1 投影視圖的獲取

和其他基于視覺相似的檢索算法一樣， 在本文中，對三維模型的投影視角來自于平均分布在該模型球形包圍盒工的頂點，為了能夠獲得足夠多數(shù)量的投影視圖作為典型視圖的候選樣本，同時又不會造成過大的計算負擔，本文選用正八十面體的42個頂點作為投影視角。這樣一來，一個三維模型將被表示為二維投影視圖集合I ={i1, i2,...i42}。

對于一幅投影視圖i，使用二維極半徑傅立葉變換，二維Zernike矩[5]，二維Krawtchouk矩[7]描述它的特征

Di=(DFT,DZern,DKraw)

式中：Di是由分別來自于二維基半徑傅立葉變化、二維Zernike矩，二維Krawtchouk矩的特征向量DFT、DZern和DKraw串聯(lián)組成的投影視圖特征描述子。

圖2 三維CAD模型的投影規(guī)則

2 典型視圖的甄選

獲得二維投影視圖集合之后，接下來將甄選其中的典型視圖。在本文中，典型視圖被定義為在一個投影視圖集合中與其他若干視圖相似, 可以代表這些視圖的一類視圖。對于一幅視圖，若集合中與其相似的視圖越多，則認為該視圖越具有典型性。例如，球體的正投影視圖可以用來代表其他所有的視圖。由于在內(nèi)容中體現(xiàn)了與其相似的若干視圖的共同特點，因此典型視圖相較其它視圖含有更高的信息量。本文將通過Apriori算法挖掘出二維投影視圖集中的典型視圖，將三維模型進一步表示為由典型視圖所組成的二維典型視圖集合。

2.1 Apriori 算法

Apriori算法作為關聯(lián)規(guī)則的挖掘技術已經(jīng)在計算機信息與數(shù)據(jù)挖掘領域得到了廣泛應用[8]。下面介紹關于它的一些基本概念：

事務：事務是數(shù)據(jù)集ITEM=item item item的一個子集，不同事務的全體構成了事務數(shù)據(jù)庫DATA。

關聯(lián)規(guī)則：關聯(lián)規(guī)則指如果項集X在某一事物中出現(xiàn)，則必然會導致項目集Y在同一事務中出現(xiàn)的一種規(guī)則，即X?Y ，其中X?ITEM ，Y?ITEM ，X∩Y≠Φ。

數(shù)據(jù)項的支持度和頻繁集：設X?ITEM為數(shù)據(jù)項集的一個子集，B為全體事務集DATA中包含X的事務的數(shù)量，A為DATA中包含的所有事務的數(shù)量，則項集X的支持度為：

它描述了數(shù)據(jù)項集X的重要性。支持度大于最小支持度的數(shù)據(jù)集為頻繁集。

關聯(lián)規(guī)則的置信度：一個關聯(lián)規(guī)則的置信度表示為

它被用來描述該規(guī)則的可靠程度。

Apriori算法的核心思想是通過對事務數(shù)據(jù)庫的多輪掃描來發(fā)現(xiàn)所有的頻繁集。首先找出所有支持度大于最小支持度的項集，即頻繁項集；然后基于這些頻繁項集產(chǎn)生新的關聯(lián)規(guī)則往復掃描。此過程不斷重復直到不再有新的頻繁項集產(chǎn)生為止。

2.2 甄選典型視圖

在使用Apriori算法挖掘典型視圖之前，需要構建一個事務數(shù)據(jù)庫DATA。首先，將二維投影視圖間的相似性度量定義為

式中： dis()為視圖i和i’對應特征描述子Di和Di’的L-2距離，它被歸一化在區(qū)間[0,1]。若度量結果大于規(guī)定的最小相似度min_ImgSim，則認為i和i’相似。然后，對于投影視圖集合I的每一幅視圖i，統(tǒng)計該集合中所有與其相似的視圖（包括其自身）。最后，將統(tǒng)計后的項目作為一條事務存入事務數(shù)據(jù)庫DATA。DATA由對應著視圖集規(guī)模的42條事務組成，如表1所示。

對二維典型視圖的挖掘從對事務數(shù)據(jù)庫DATA的第一輪掃描開始。首先，對于項集中的每一個數(shù)據(jù)項（即投影視圖）計算其所對應的支持度，篩選出大于最小支持度min_support的頻繁1-項集組成頻繁項目集L1；然后，以L1作為輸入構建候選集，掃描數(shù)據(jù)庫并從中找出大于最小支持度的2-項頻繁項目集L2；接下來繼續(xù)用L2作為輸入去尋找L3。此過程不斷重復直到?jīng)]有新的頻繁集產(chǎn)生為止。典型視圖即為每個頻繁項目集中對應關聯(lián)規(guī)則置信度最小的數(shù)據(jù)項。算法1 給出了整個典型視圖甄選的流程。

算法1：典型視圖甄選算法

輸入：事務數(shù)據(jù)庫DATA，最小支持度閾值min_support

輸出：三維模型的典型視圖集C

1）L1= 1項頻繁項目集

2）for（k=2；Lk-1；k++） do

3）CankApriori_gen(Lk-1，min_support)：構建候選集

4）for all 數(shù)據(jù)庫DATA中的事務t do

5）Cant Subset(Cank，t)：提取包含在事務t中的候選集

6）for all Cant中的候選項Can’ do

7）Can’.Count++

8）end for

9）Lk= {Can’∈CankCan’.Count ≥ min_support}

10）end for

11）L = ∪kLk

12）end for

13）C SeekMinConf(L)：計算置信度，提取典型視圖

完成典型視圖的甄選之后，三維模型將由其對應的二維典型視圖集C來表示。三維模型之間的相似性比較即可轉換為各自典型視圖集之間的比較。由于存在不同模型典型視圖集規(guī)模不一致的問題，為了保證相似性計算的有效性，本文采用貪心算法。設模型M和Q對應的典型視圖集分別為CM與CQ，則其相似性計算的具體步驟如下：

表1 事務數(shù)據(jù)庫D示例

步驟1 取模型M的1幅典型視圖ci∈C，遍歷CQ中的每一幅視圖crQ，找出與其最相似的視圖cj。ci與cu之間的距離函數(shù)定義為

式中：r為模型Q典型視圖集的規(guī)模；Dci于MDcQr分別是cMi和cQu對應的特征描述子。其值越小，表示視圖越相似。

步驟2 重復步驟1，直至任一視圖集合中所有的視圖都成功匹配。在此過程中，視圖集CM與CQ內(nèi)已經(jīng)匹配成功的視圖不參與重復計算。則2個模型M和Q之間的相似性度量可表示為

式中：N =min(s, r )，s和r分別為模型M和Q所對應的典型視圖集的規(guī)模。D為匹配成功的視圖對之間的L-2距離。

3 算法驗證與討論

本文以OpenCASCADE[9]為幾何造型平臺，Microsoft Visual Studio 2008為集成開發(fā)環(huán)境，構建了一個三維CAD模型測試庫。庫中的模型主要來自于普渡大學建立的工程標準模型庫ESB，包含了齒輪類、盤類、軸類等400多個CAD模型。在實驗中，為了確保在對模型投影的過程中，從每一視角投影的唯一性，本文利用實驗平臺OPENCASCADE和改進PCA法對模型的姿態(tài)分別對模型進行位置尺度和旋轉的歸一化處理。投影視圖的尺寸規(guī)定為256×256。衡量投影視圖相似性的最小相似度min_ImgSim與典型視圖甄選時

圖3 三種算法的平均查全率-查準率曲線比較

甄選時的最小支持度min_support分別設定為70%與50%。

為了驗證本文算法在三維CAD模型檢索中的有效性，本文使用查全率-查準率曲線（P-R Curve）和E測度（E-Measures）作為檢索結果的評價指標，將本文算法與光場算法（LFD）[5]及文獻[6]中的算法（OWD）進行比較。綜合圖3、表2及表3的實驗結果，可以看出本文算法的檢索性能優(yōu)于其他兩種算法，檢索結果更加符合人的相似性感知。

表2 三種算法的E測度指標比較

表3 檢索實例

4 結論

本文提出了一種基于二維典型視圖的三維CAD模型檢索算法。通過對CAD模型進行二維投影并甄選出其中的典型視圖， 將模型表示為其對應的二維典型視圖的集合。三維模型間的相似性評價通過比較各自對應的二維典型視圖來獲得。實驗結果表明本文算法的檢索性能優(yōu)于其他幾種算法，能夠更好地勝任對三維CAD模型的檢索。

[1] Ulman D G.The mechanical design process,second ed.New York:McGraw-Hill,1997.

[2] Tangelder J W H,Veltkamp R C.A survey of content based 3D shape retrieval methods.Multimedia Tools and Applications,2007,39(3):441-471.

[3] Shilane P,Min P,Kazhdan M,et al.The Princeton Shape Benchmark.In Proc.Shape Modeling Applications,Genoa,Italy,2004.

[4] Jayanti S,Kalyanaraman Y,Iyer N et al. Developing an engineering shape benchmark for CAD models.Computer Aided Design,2006,28(9):939-953.

[5] Chen D Y,Tian X P,Shen Y T. On visual similarity based 3D model retrieval.Computer Graphics Forum,2003,22(3):223-232.

[6] Li L,Wang H Z,Chin T J.Retrieving 3D CAD models using 2D images with optimized weights. In Proc.International Congress on Image and Signal Processing,Yantai,China,2010.

[7] Yap P T,Paramesran R,Ong S H.Image analysis by Krawtchouk moments.IEEE Transactions on Image Processing,2003,12(11):1367-1377.

[8] Wu X D,Kumar V,Quinlan J R et al. Top 10 algorithms in data mining.Knowledge and information systems,2007,14(1):1-137.

[9] OpenCASCADE Technology www.opencascade.org.