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

石 民，張樹(shù)生，李 亮，白曉亮

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

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

0 引言

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

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

本文提出一種基于二維典型視圖的三維CAD模型檢索算法，該算法通過(guò)從CAD模型二維投影視圖集中甄選出其中具有代表性（即信息含量高）的視圖， 將三維模型間的比較轉(zhuǎn)化為各自典型視圖間的相似性匹配。首先對(duì)一個(gè)三維CAD模型沿固定視角進(jìn)行投影，獲得相應(yīng)的二維投影視圖集；然后采用Apriori算法從中挖掘出具有代表性的視圖作為該模型的典型視圖； 最后通過(guò)比較模型各自對(duì)應(yīng)的典型視圖來(lái)獲得三維模型間的相似性評(píng)價(jià)。

1 投影視圖的獲取

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

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

Di=(DFT,DZern,DKraw)

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

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

2 典型視圖的甄選

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

2.1 Apriori 算法

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

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

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

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

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

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

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

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

2.2 甄選典型視圖

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

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

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

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

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

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

1）L1= 1項(xiàng)頻繁項(xiàng)目集

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

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

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

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

6）for all Cant中的候選項(xiàng)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)：計(jì)算置信度，提取典型視圖

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

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

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

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

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

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

3 算法驗(yàn)證與討論

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

圖3 三種算法的平均查全率-查準(zhǔn)率曲線比較

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

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

表2 三種算法的E測(cè)度指標(biāo)比較

表3 檢索實(shí)例

4 結(jié)論

本文提出了一種基于二維典型視圖的三維CAD模型檢索算法。通過(guò)對(duì)CAD模型進(jìn)行二維投影并甄選出其中的典型視圖， 將模型表示為其對(duì)應(yīng)的二維典型視圖的集合。三維模型間的相似性評(píng)價(jià)通過(guò)比較各自對(duì)應(yīng)的二維典型視圖來(lái)獲得。實(shí)驗(yàn)結(jié)果表明本文算法的檢索性能優(yōu)于其他幾種算法，能夠更好地勝任對(duì)三維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.