基于二維典型視圖的三維CAD模型檢索算法

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

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

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

0 引言

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

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

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

1 投影視圖的獲取

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

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

Di=(DFT,DZern,DKraw)

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

圖2 三維CAD模型的投影規則

2 典型視圖的甄選

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

2.1 Apriori 算法

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

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

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

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

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

關聯規則的置信度：一個關聯規則的置信度表示為

它被用來描述該規則的可靠程度。

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

2.2 甄選典型視圖

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

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

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

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

輸入：事務數據庫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 數據庫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來表示。三維模型之間的相似性比較即可轉換為各自典型視圖集之間的比較。由于存在不同模型典型視圖集規模不一致的問題，為了保證相似性計算的有效性，本文采用貪心算法。設模型M和Q對應的典型視圖集分別為CM與CQ，則其相似性計算的具體步驟如下：

表1 事務數據庫D示例

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

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

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

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

3 算法驗證與討論

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

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

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

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

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

表3 檢索實例

4 結論

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