王家樂

浙江工商大學，杭州，310018

?

一種基于法向量分布特征的機械零件模型手繪草圖查詢接口

王家樂

浙江工商大學，杭州，310018

提出一種面向三維機械零件模型檢索的手繪草圖查詢接口。首先，利用模型的法向量最大分布方向來輔助主成分分析(PCA)算法對三維模型的空間姿態(tài)進行旋轉(zhuǎn)歸一，使得模型投影視圖和用戶手繪草圖的視角一致；然后采用一種二維圖像相似性比較算法衡量用戶草圖和模型投影視圖之間的相似性，從而得到與用戶提交的查詢草圖相似的三維零件模型。實驗結(jié)果表明所提出的手繪草圖查詢接口能夠讓用戶快速地表達查詢意圖，且具有較高的檢索準確性。

三維模型檢索；查詢接口；手繪草圖；形狀分析

0　引言

三維輔助設(shè)計軟件的廣泛使用使得機械零件領(lǐng)域中的三維零件模型數(shù)目日益龐大。要有效地管理海量機械零件模型，需要有效的模型形狀相似性檢索方法，從而讓用戶可以快速從零件模型數(shù)據(jù)庫中找到特定形狀的零件模型。

三維形狀的復(fù)雜性令如何讓用戶方便且準確地表達查詢意圖成為三維模型檢索中的一個難點問題。一個實用的三維模型檢索系統(tǒng)，應(yīng)擁有友好的查詢接口和人機交互界面，為用戶提供方便的查詢手段。在機械零件設(shè)計領(lǐng)域，檢索相似零件模型的目的一般是為了設(shè)計重用，復(fù)用已有的零件模型及其設(shè)計方案。在檢索時，用戶很可能沒有現(xiàn)成的零件模型可作為查詢遞交，在這種情況下應(yīng)該支持用戶通過手繪草圖表達待查詢零件的形狀。

本文提出一種適合于三維機械零件模型檢索系統(tǒng)的手繪草圖查詢接口，用戶可通過繪制零件的若干幅二維草圖來表達查詢形狀。

1　相關(guān)研究

三維模型檢索系統(tǒng)的查詢接口一般可分為文字接口、模型接口、手繪草圖接口三類。

文字接口采用基于文本的關(guān)鍵詞檢索方式，將用戶輸入的關(guān)鍵詞同三維模型的文件名或備注信息作文本匹配。這種查詢不屬于形狀特征比較的范疇，因此本文不作討論。

模型接口讓用戶提交一個完整的三維模型作為查詢輸入，檢索系統(tǒng)對此模型提取形狀特征，然后計算其形狀特征向量與數(shù)據(jù)庫中模型的形狀特征向量的距離。模型接口的優(yōu)點是查詢模型十分精確，包含了完整的形狀信息；缺點是查詢時要求用戶擁有一個現(xiàn)成的查詢模型。

手繪草圖接口可讓用戶自主、快速地用手繪方式表達出查詢形狀，從而解決了模型接口需要提供查詢模型的問題。本文對手繪草圖接口展開了重點研究。

文獻[1]基于Teddy手繪建模系統(tǒng)實現(xiàn)了一個面向三維模型檢索的三維草圖接口，用戶在平面上繪制表示三維形體的線條草圖，然后查詢接口根據(jù)二維線條構(gòu)建出三維形體。三維草圖接口對用戶的繪圖水平要求高，操作起來比較復(fù)雜；而且從二維線條圖重構(gòu)三維形體的效果并不理想。二維草圖接口讓用戶手繪若干幅不同角度的模型輪廓圖，檢索系統(tǒng)對三維模型的投影視圖和用戶手繪輪廓圖進行相似性比較。二維草圖接口避開了三維重建的難題，實用性較好，因此得到了較多研究者的關(guān)注[2-3]。

文獻[4]和文獻[5]分別提出了通過繪制三維模型的骨架草圖來構(gòu)建查詢，骨架圖包含了模型的拓撲結(jié)構(gòu)信息，因此可以實現(xiàn)三維模型間的拓撲相似性檢索。但是骨架提取算法易受到模型中噪聲影響，所以檢索準確度受限。

上述各文獻中研究的查詢接口均為非交互式接口，文獻[6]提出一種交互式的三維模型檢索系統(tǒng)查詢接口，用戶可根據(jù)檢索返回的模型投影視圖來修改草圖，然后重新提交草圖進行二次查詢。這種交互式的手繪草圖接口讓用戶能修正查詢形狀，使草圖更加準確地表示用戶的查詢意圖。但交互過程也復(fù)雜化了查詢步驟，非熟練用戶使用該系統(tǒng)是有一定困難的。

文獻[7] 比較了近幾年來的手繪草圖三維形狀查詢研究，其中性能較好的方法均需大量的“視圖采樣”(view sampling)，即從多個視角生成模型的投影視圖(一般為幾十幅至上百幅視圖)。本文研究三維模型姿態(tài)旋轉(zhuǎn)歸一算法，三維模型經(jīng)過旋轉(zhuǎn)歸一后可以只生成和比較特定視角的少數(shù)幾幅視圖，計算量減小但檢索準確度一般次于多角度視圖采樣方法。

針對機械零件模型，文獻[8] 提出利用模型特征拓撲結(jié)構(gòu)的檢索算法，文獻[9] 提出將整個三維模型拆分成若干平面體、回轉(zhuǎn)體和曲面體，根據(jù)形體之間特征數(shù)量和參數(shù)的不同進行形體之間的匹配。以上兩篇文獻所提出的方法充分利用了機械零件模型自身的特點來構(gòu)造有效的檢索算法，但均沒有提供手繪草圖查詢接口，它們不支持手繪草圖查詢。

2　確定投影方向

實現(xiàn)手繪草圖查詢接口的關(guān)鍵步驟有兩個：①確定模型的投影方向，獲得與用戶手繪草圖相同視角的模型投影視圖；②用戶草圖和模型投影視圖間的相似度計算。下面闡述確定模型投影方向的方法。

三維空間中模型可能處在任意的旋轉(zhuǎn)姿態(tài)下，而用戶提交的手繪草圖表示了用戶選定角度下模型某側(cè)面的輪廓圖。因此在生成模型投影視圖之前，需要將模型的空間姿態(tài)進行旋轉(zhuǎn)歸一，以達到如下兩個目的：①不管模型初始旋轉(zhuǎn)姿態(tài)如何，相似的模型在旋轉(zhuǎn)歸一后處在近乎同樣的姿態(tài)下；②在旋轉(zhuǎn)歸一后，能夠得到與用戶習慣視角一致的模型投影方向。

三維模型旋轉(zhuǎn)歸一最常用的方法是PCA旋轉(zhuǎn)歸一算法，它通過計算模型所有頂點坐標協(xié)方差矩陣的特征向量(eigen-vector)得到模型的“主軸”，從而歸一化模型旋轉(zhuǎn)姿態(tài)。PCA算法并不完全適用于基于手繪草圖的三維模型檢索，因為它只能實現(xiàn)上述目的①而不能實現(xiàn)目的②。在一些情況下，盡管PCA算法將相似三維模型的旋轉(zhuǎn)方向歸為一致，但這個方向卻不符合人們的視覺習慣。圖1展示了兩個經(jīng)PCA算法旋轉(zhuǎn)歸一后的椅子模型?？梢钥闯觯@兩個模型旋轉(zhuǎn)歸一后的空間姿態(tài)是一樣的，但PCA確定的投影軸(即圖1中坐標軸)方向不符合人們的視覺習慣，人們通常按圖2中箭頭所示的方向去描繪模型的側(cè)輪廓。用戶一般從一個“正立”面描繪三維物體，例如工程師所用的三視圖是從正前、正側(cè)和正上方來投影物體。

圖1　PCA旋轉(zhuǎn)歸一后的模型姿態(tài)及PCA定義的投影方向

圖2　用戶的視覺習慣方向

PCA算法之所以產(chǎn)生上述問題是因為它僅從模型頂點的分布來考慮模型姿態(tài)，而不涉及模型的面片朝向。機械零件模型的面片朝向一般具有較明顯的規(guī)律性，因此本文通過計算模型面片的法向量最大分布方向來確定模型總體朝向，以此輔助PCA算法更準確地將模型旋轉(zhuǎn)歸一到用戶的習慣觀察角度。

為了計算三維模型的法向量分布，首先獲得模型的擴展高斯圖像(EGI)。EGI把構(gòu)成三維模型的每一個面片映射為單位球面上的一個向量，這個向量的方向與該面片的法向量方向相同，向量的模為該面片的面積率(面片面積/模型總面積)。圖3所示為一個三維模型及其EGI，圖中左邊是一個以面片形式顯示的椅子模型，右邊是該模型的EGI(單位球面上的外指線段表示法向量)。

圖3　三維模型及其EGI

獲得模型的EGI后，建立一個球面坐標系，如圖4所示。在此坐標系中定義一個搜索游標向量I(φ,θ)， 其模r為1。

圖4　球面坐標系

(1)

其中，E為模型的EGI上全部向量的集合，φ∈[0,2π],θ∈[0,π]。然后計算集合U(φ,θ)中所有向量在I(φ,θ)上投影的模長之和：

A(φ,θ)=∑I(φ,θ)·PiPi∈U

(2)

模型的最大法向量分布方向I1即為使得A(φ,θ)值最大的(φ,θ)所定出的方向。

獲得了最大法向量分布方向I1后，再在與I1垂直的平面上搜索法向量分布最大的方向I2。I2的計算過程與I1一樣，只是多了一個約束條件：搜索游標向量I(φ,θ)與I1垂直，即I(φ,θ)·I1=0。求得I1、I2后就可以沿I1、I2以及與它們垂直的方向?qū)δＰ瓦M行投影。

以上算法的計算結(jié)果可以輔助PCA算法對模型進行旋轉(zhuǎn)歸一：把用戶手繪草圖跟用PCA算法旋轉(zhuǎn)歸一后的模型投影圖以及用最大法向量分布算法旋轉(zhuǎn)歸一后的模型投影圖均作比較，取兩次比較中最小的相似性距離作為查詢草圖與模型間的相似性距離。

3　草圖和視圖間的相似度計算

用戶提交的三幅手繪草圖和模型三幅投影視圖之間的對應(yīng)關(guān)系是未知的，需將三幅手繪草圖與模型三幅投影視圖的所有可能排列相匹配，所有排列中最小的相似性距離和為手繪草圖和投影之間的相似性距離。

三維模型的投影視圖有多種：剪影圖像、深度圖像、輪廓圖、外輪廓圖等。其中的輪廓圖屬于線條圖像，適合于作為與用戶手繪草圖匹配的模型視圖。三維模型的輪廓圖是模型表面點的集合，在這些點上模型表面的法向量與視線方向垂直。用數(shù)學語言表達即為：構(gòu)成輪廓線的點滿足ni·(pi-c)=0，其中pi代表模型上的點，ni代表pi的法向量，c代表觀察者視點，pi-c是從視點出發(fā)到pi點的視線。由于三維網(wǎng)格模型由面片組成，其表面法向量方向不連續(xù)，一般情況下不存在法向量正好與視線垂直的面片，所以在網(wǎng)格模型上，把輪廓線定義為前向面片(法向量指向視點的面片)和后向面片(法向量背向視點的面片)的公共邊集合(圖5)，即構(gòu)成輪廓線的邊滿足：[nm·(v-c)][nn·(v-c)]<0，其中nm和nn是共有該邊的兩個面片的法向量，v是該邊上的任意點。

圖5　輪廓線定義

(3)

disImg(·)是一個衡量圖像間相似性的函數(shù)，本文采用文獻[10]提出的線條圖相似性比較算法ARP(angularradialpartitioning)來衡量模型投影視圖和用戶手繪草圖之間的相似性。ARP算法首先需要將線條圖像作平移和縮放歸一化，使得其恰好被一個同心圓和扇形組合的網(wǎng)格覆蓋，這個網(wǎng)格被劃分為M×N個區(qū)域，M是徑向劃分數(shù)目，N是角度劃分數(shù)目，如圖6所示。ARP算法統(tǒng)計每個區(qū)域中圖像像素的數(shù)目，假設(shè)f(k,i)表示第(k,i)個扇形區(qū)域內(nèi)的像素數(shù)(k=0,1,2,…,M-1，i=0,1,2,…,N-1)，對每個給定的k值，對f(k,i)進行一維傅里葉變換：

(4)

傅里葉變換后，取{‖F(xiàn)(k,u)‖}(k=0,1,2,…，M-1;u=0,1,2,…,N-1)作為圖像的特征向量。這個特征向量是具有旋轉(zhuǎn)不變性的。

圖6　圖像劃分網(wǎng)格

4　實驗分析

實驗使用ESB(engineeringshapebenchmark)模型庫[11]來測試算法的檢索性能。ESB模型庫包含了45個機械零件模型分類，共有867個零件模型。本文實驗選用了ESB模型庫中42個模型類，未被選用的3個模型類均為雜類(Miscellaneous類，它們包含類型意義不明顯的零件模型)。實驗對42個類的每一個類進行2～3次查詢。

圖7所示為用戶通過本文所提出的手繪草圖查詢接口進行的一次查詢，圖中上部為用戶提交的三幅手繪草圖，下部為檢索返回的前四個查詢結(jié)果。

圖7　用戶手繪草圖查詢和查詢結(jié)果

本文采用信息檢索領(lǐng)域中常用的查準率-查全率(precision-recall)[12]指標來衡量檢索準確度。查準率是指檢索系統(tǒng)只返回相關(guān)對象的能力(即檢索的準確性)，查全率是指檢索系統(tǒng)返回所有相關(guān)對象的能力(即檢索的全面性)。

圖8展示了單獨使用法向量最大分布算法(MN)、單獨使用PCA算法，以及組合PCA算法和法向量最大分布算法的查準率-查全率曲線?？梢钥闯鼋M合PCA算法和法向量最大分布算法可使得查準率-查全率指標更理想。

圖8　查準率-查全率曲線

表1中列出了基于PCA算法和基于法向量最大分布算法的模型形狀特征提取時間，后者比前者的耗時要多，但由于特征提取可以在用戶進行查詢之前就進行(通常是在數(shù)據(jù)庫建立或有新模型加入到數(shù)據(jù)庫時進行)，因此特征提取時間的長短并不會影響檢索系統(tǒng)對用戶查詢的響應(yīng)速度。表1中最后一行列出了兩種算法的查詢響應(yīng)時間，幾乎沒有差異。

組合PCA算法和法向量最大分布算法雖然會在提升檢索準確度的同時帶來額外的時間開銷，但不影響查詢響應(yīng)速度，只是增加了數(shù)據(jù)庫系統(tǒng)后臺提取模型特征的時間，所以這種方式是有價值的。

表1　計算時間　s

5　結(jié)束語

本文提出了一種面向三維機械零件模型檢索的手繪草圖查詢接口。由于機械零件模型的面片朝向一般具有規(guī)律性，面片法向量通常在某幾個方向上存在顯著的聚集，因此可利用模型的法向量最大分布方向來輔助PCA算法對三維模型的空間姿態(tài)進行旋轉(zhuǎn)歸一，使得模型投影視圖和用戶手繪草圖的視角一致。實驗結(jié)果表明本文提出的手繪草圖查詢接口對用戶友好，具有較高的檢索準確性；雖然特征提取時間有所增加，但并不會影響到檢索系統(tǒng)對用戶查詢的響應(yīng)速度。

[1]Funkhouser T, Min P, Kazhdan M, et al. A Search Engine for 3D Models[J]. ACM Transactions on Graphics, 2003, 22(1): 83-105.

[2]Hou S, Ramani K. Classifer Combination for Sketch-Based 3D Part Retrieval[J]. Computers & Graphics, 2007, 31(4): 598-609.

[3]Eitz M, Richter R, Boubekeur T, et al. Sketch-based Shape Retrieval[J]. ACM Transactions on Graphics, 2012, 31(4): 13-15.

[4]Wang Jiale, He Yuanjun, Tian Haishan, et al. Retrieving 3D CAD Model by Freehand Sketches for Design Reuse[J]. Advanced Engineering Informatics, 2008, 22(3):385-392.

[5]Hou S, Ramani K. Dynamic Query Interface for 3D Shape Search[C]//Proceedings of ASME IDETC/CIE. Salt Lake City, 2004.

[6]Pu J, Ramani K. A 2D Sketch-Based User Interface for 3D CAD Model Retrieval[J]. Journal of Computer Aided Design and Application, 2005, 2(6):717-727.

[7]Li Bo, Lu Yijuan, Li Chunyuan, et al. A Comparison of 3D Shape Retrieval Methods Based on a Large-scale Benchmark Supporting Multimodal Queries[J]. Computer Vision and Image Understanding, 2015, 131(1):1-27.

[8]孫長樂, 寧大勇, 熊偉, 等. 基于特征的工程領(lǐng)域CAD模型檢索技術(shù)[J]. 計算機集成制造系統(tǒng), 2014, 20(4):747-754.

Sun Changle, Ning Dayong, Xiong Wei, et al. Feature-based CAD Model Retrieval Technique in Engineering Field[J]. Computer Integrated Manufacturing Systems, 2014, 20(4):747-754.

[9]朱文博, 吳新仁, 甘屹. 基于形狀拆分的機械零件三維模型檢索[J]. 圖學學報, 2015, 36(1):35-40.

Zhu Wenbo, Wu Xinren, Gan Yi. 3D Model Retrieval of Mechanical Parts Based on Shape Split[J]. Journal of Graphics, 2015, 36(1):35-40.

[10]Chalechale A, Mertins A, Naghdy G. Edge Image Description Using Angular Radial Partitioning[J]. IEE Proceedings—Vision, Image and Signal Processing, 2004, 151(2):28-41.

[11]Jayanti S, Kalyanaraman Y, Iyer N, et al. Developing an Engineering Shape Benchmark for CAD Models[J]. Computer-Aided Design, 2006, 38(9): 939-953.

[12]Singhal A. Modern Information Retrieval: a Brief Overview[J]. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2001, 24(4):35-42.

(編輯盧湘帆)

Free-hand Sketch Query Interface for Retrieving Mechanical Parts Using Normal Vector Distribution Feature

Wang Jiale

Zhejiang Gongshang University,Hangzhou,310018

A sketch query interface was proposed for retrieving 3D models of mechanical parts. The maximum normal distribution of a 3D model was computed to assist the principal component analysis(PCA) to normalize the orientation of the 3D model, and then the projected views of the 3D model could be coordinated with the free-hand sketches submitted by users. To retrieve the 3D models similar with the user sketches, an image similarity assessment algorithm was employed to compare the shape similarity between user sketches and the views of the model. Experiments demonstrate that users can express their query intentions through the proposed query interface rapidly with satisfactory retrieval performance.

3D model retrieval; query interface; free-hand sketch; shape analysis

2015-10-15

國家自然科學基金資助項目(61202200)；浙江省教育廳科研項目(Y201018008)

TP391

10.3969/j.issn.1004-132X.2016.16.002

王家樂，男，1980年生。浙江工商大學計算機與信息工程學院副教授。主要研究方向為信息檢索、人機交互。發(fā)表論文10余篇。