一種基于局部特征的三維模型檢索算法

屠 宏,耿國華

(西北大學信息科學與技術(shù)學院,西安710127)

一種基于局部特征的三維模型檢索算法

屠 宏,耿國華

(西北大學信息科學與技術(shù)學院,西安710127)

在基于內(nèi)容的三維模型檢索系統(tǒng)中,特征提取技術(shù)是三維模型檢索的關(guān)鍵。為此,提出基于局部特征的三維模型檢索算法。定義一種新的局部特征描述符:曲度,將其作為三維模型檢索時的特征。曲度作為對平均曲率與高斯曲率的校正,在不增加額外計算量的前提下,可同時克服平均曲率對平滑模型的不敏感性和高斯曲率分布較均勻的缺點,更真實地反映三維模型的局部彎曲程度。實驗結(jié)果表明,以曲度作為特征進行檢索,可明顯提高檢索的查準率,配合全局特征檢索時則可在保證查全率的基礎(chǔ)上,大幅提高檢索的準確性。

三維模型檢索;曲度;高斯曲率;平均曲率;特征提取

1 概述

隨著三維數(shù)據(jù)獲取技術(shù)、三維建模以及計算機軟硬件技術(shù)的快速發(fā)展,三維模型的獲取和產(chǎn)生已經(jīng)越來越容易,全世界每天都產(chǎn)生大量的三維模型,并且其應(yīng)用的范圍也越來越廣泛,如工業(yè)設(shè)計、虛擬現(xiàn)實、游戲動漫等。如何在各種模型數(shù)據(jù)庫和互聯(lián)網(wǎng)上快速、準確地找到自己所需的三維模型,已成為多媒體信息檢索中的一個重要課題。

三維模型檢索系統(tǒng)一般包括模型的特征提取、特征庫建立、特征向量的相似性匹配、查詢及反饋接口等部分,其中,三維模型的特征提取是其首要的和關(guān)鍵的一步。三維模型特征向量的質(zhì)量決定了三維模型檢索的質(zhì)量。文獻［1-3］利用模型頂點的曲率的特性作為描述符進行模型檢索。對于嵌入在歐幾里得空間R3中的二維平面,有2種曲率存在:平均曲率(mean curvature)和高斯曲率(Gauss curvature)。平均曲率H=κ1+κ2和曲面面積的第一變分密切相關(guān),平均曲率依賴于嵌入方式,例如,一個圓柱和一個平面是局部等距的,但是平面的平均曲率為0,而圓柱的平均曲率為非零。高斯曲率K=κ1·κ2實際上是曲面的內(nèi)在屬性,也就是高斯曲率不依賴于曲面的特定嵌入。

本文提出一種基于局部特征的三維模型檢索算法,定義曲度D=κ21+κ22作為三維模型的特征描述符,利用其同時包含高斯曲率和平均曲率信息的特點,克服平均曲率對平滑模型的不敏感性,以及高斯曲率分布較均勻的缺點,更真實地反映三維模型的

局部彎曲程度,提高三維模型檢索的查準率。

2 基于內(nèi)容的三維模型檢索

基于內(nèi)容的三維模型檢索首先從三維模型中自動計算并提取其特征向量也稱為形狀描述符,如形狀、空間關(guān)系、材質(zhì)的顏色及紋理等特征,建立三維模型的多維特征信息索引,然后在多維特征空間中計算待查詢模型與目標模型之間的相似程度并進行排序,實現(xiàn)對三維模型數(shù)據(jù)庫的瀏覽和檢索［4］。其核心技術(shù)是三維模型的特征向量或是形狀描述符的提取,圖1是一個典型的基于內(nèi)容的三維模型檢索系統(tǒng)的框架。離線部分是對模型庫中的模型進行特征提取并建立特征庫的過程,每一個模型都由唯一的一個或一組特征向量表示。在線部分是對待檢索的模型進行特征提取,然后在模型特征庫中進行相似性比較,并進行排序得到最終的檢索結(jié)果。在整個檢索系統(tǒng)中,三維模型的特征提取是其核心,因此,國內(nèi)外對三維模型特征提取算法的研究也比較多。

圖1 三維模型檢索系統(tǒng)框架

三維模型的檢索算法可以分為基于全局特征的檢索和基于局部特征的檢索。全局特征描述了三維模型的整體形狀特征,這些特征包括模型的各種統(tǒng)計矩、模型的體積和面積、傅里葉變換等。文獻［5］利用高斯核函數(shù)描述模型投影輪廓特征的分布作為特征,進行模型檢索。文獻［6］提取了三維模型投影輪廓的邊界點為描述符進行檢索。文獻［7］用W-系統(tǒng)矩融合volume descriptors不變特征用于模型檢索。文獻［8］推廣了高斯映射,將模型表面點到原點的法向距離也存儲在高斯映射中,高斯映射和推廣的高斯映射都需要將模型歸一化。文獻［9］將模型映射到以模型中心為對稱中心的12個平面上,通過對比二維映射圖來確定模型間的相似度。近些年,很多學者不再直接比較三維模型全局特征的相似度,而是通過比較全局特征分布的相似度來確定三維模型的相似度,文獻［10］將模型表面任意點的距離、角度、面積和體積的分布作為特征描述符進行三維模型的相似性匹配,通過他們的對比實驗結(jié)果顯示,模型表面任意點之間的距離分布圖作為特征的效果最好。全局特征描述符適合對模型進行粗分類,對模型之間細微的不同不敏感,對同類模型間的檢索效果不是很好。

基于局部特征的三維模型描述符主要考慮的是模型表面上的點和其鄰近點之間的關(guān)系,文獻［11］用球坐標系將模型表面曲率映射到了一個單位球上,比較兩個模型的曲率分布來確定模型的相似性,它要求模型必須是封閉的,不能有“洞”。Zaharia and Preteux描述用三維形狀譜描述符作為特征,形狀索引被定義為模型表面2個主曲率的函數(shù),這種方法需要復(fù)雜的計算,要求模型表面有良好的拓撲結(jié)構(gòu)。文獻［12］通過一點的鄰域內(nèi)的三維曲線的性質(zhì)描述這點附近曲面的性質(zhì),以此為三維模型的局部特征進行檢索,這種方法計算量大,很難應(yīng)用到三維模型檢索算法中去。

三維模型的全局特征描述符體現(xiàn)的是三維模型整體的特征,基于全局特征的檢索算法對模型的粗分類比較有效,對于同類型的不同模型的敏感度較低,大多數(shù)全局特征描述符的計算較簡單。三維模型的局部特征描述符體現(xiàn)的是三維模型局部的特性,基于局部特征的檢索算法可以區(qū)分模型之間細微的差別,適合模型的精確檢索,特征描述符的計算較復(fù)雜,對模型的要求較高。

3 平均曲率、高斯曲率和曲度

曲線的曲率描繪的是曲線的彎曲程度,曲面的曲率描繪了曲面的彎曲程度,曲面上任一點的曲率是由過這點的曲線的曲率來刻畫的,對于曲面上任意一點,平均曲率H和高斯曲率K常被用來刻畫曲面的彎曲特性。在三維模型檢索算法中,平均曲率和高斯曲率常被用作三維模型的局部特征描述符進行三維模型的檢索。

設(shè)曲面S的方程為r=r(u,v),則曲面上的點的平均曲率H、高斯曲率K可以由下面的公式給出:

其中:

高斯曲率和平均曲率都是曲面的內(nèi)在幾何不變量,能很好地描繪曲面上某點的彎曲程度,但是也有

各自的缺陷。高斯曲率K=κ1·κ2是2個主曲率的乘積,圓柱形曲面上的任意一點,它的最小曲率都為0,因此,圓柱曲面上的任意一點的高斯曲率也為0,也就是說,以高斯曲率作為特征來看,圓柱曲面和平面是局部同構(gòu)的,但從實際情況和視覺效果上看,它們是不同的。因此,以高斯曲率作為特征描述符進行模型檢索,對此類曲面不敏感,會降低模型的查準率。平均曲率K=κ1+κ2/2是2個主曲率的和,當曲面上某點為鞍點時,其平均曲率為0,以平均曲率作為特征來看,曲面上的鞍點和平面的點是局部同構(gòu)的,但從實際情況和視覺效果上看,它們是不同的。因此,以平均曲率作為特征描述符進行模型檢索,對此類曲面不敏感,會降低模型的查準率。

曲度公式可以寫成高斯曲率K和平均曲率H的和的形式。對于圓柱曲面,當高斯曲率為0時,平均曲率不為0;對于曲面上的鞍點,平均曲率為0時,高斯曲率不為0。因此,曲度克服了平均曲率和高斯曲率固有的缺點,能準確區(qū)分圓柱形表面上的點、鞍點和平面上的點,曲度作為特征描述符能提高模型檢索的精確度。

對于表面較光滑的三維模型,平均曲率較小,以平均曲率作為特征描述符對此類模型并不敏感,相對而言,高斯曲率對此類模型具有較高的敏感性,曲度是平均曲率的平方和高斯曲率的和,當平均曲率較小時,其平方后的值會更小,這時曲度就近似等于高斯曲率,它克服了平均曲率作為特征對光滑模型不敏感的缺點。同時,曲度作為平局曲率和高斯曲率的和,在高斯曲率的值上又加上了平均曲率的值,克服了高斯曲率分布較均勻的缺點。從以上數(shù)值角度的分析來看,曲度作為特征描述符能提高模型檢索的精確度。

4 曲度的計算

三維模型的表示方法有很多種,其中三角網(wǎng)格形式是三維模型常用的表示方法之一,本文以三角網(wǎng)格模型作為研究對象。經(jīng)典的微分幾何研究的是連續(xù)的曲線和曲面的微分特性,對于網(wǎng)格模型這種離散形式的曲面并不適用,因此需要借助離散微分幾何的一些方法來計算高斯曲率和平均曲率。

三角網(wǎng)格上曲率計算的方法有多種,平均曲率的估計本文采用文獻［13］的方法,引入Laplace-Beltrami算子Δ=2Hn(Δ為梯度算子,H為采樣點的平均曲率,n為采樣點的法向量)。對拉普拉斯算子Δ在三角網(wǎng)格曲面上進行離散,對網(wǎng)格曲面上的頂點pi,其 1-鄰域點集為{pi,j∈N(i)},則Δ是其加權(quán)和:

圖2 αij,βij示意圖

圖3 Spi面積示意圖

點S是三角形的外心(三角形的三邊的垂直平分線交于一點。該點叫做三角形的外心)

當Ti為銳角三角形時:

5 實驗結(jié)果與分析

本文實驗的計算機配置為Intel CPU主頻3.2 GHz,內(nèi)存16 GB,測試平臺是Windows 7操作系統(tǒng),代碼由Matlab 2012b編寫,本文從普林斯頓基準數(shù)據(jù)庫中抽取了4類125個模型建立了實驗數(shù)據(jù)庫,包括31個人、37個手、27個四足動物、30條魚。采用相同的模型數(shù)據(jù)集,分別用平均曲率、高斯曲率和本文提出的算法進行對照實驗,采用查準率(Precision)和查全率(Recall)評價3種算法的檢索性能,部分檢索結(jié)果如圖4所示。

圖4 部分檢索結(jié)果

對于光滑模型,平均曲率不敏感,在第1組實驗中,以平均曲率為特征的檢索結(jié)果中有2個錯誤匹配的模型,高斯曲率的檢索結(jié)果較平均曲率略好,有一個錯誤匹配的模型,以曲度為特征的檢索效果最好,沒出現(xiàn)錯誤匹配的模型,其查全率-查準率曲線如圖5所示。

圖5 查全率-查準率曲線(曲率均勻模型)

對于不光滑模型的檢索,高斯曲率分布較均勻,對模型的變化并不是太敏感,平均曲率的檢索效果較高斯曲率略好,只有一個錯誤匹配的模型,本文提出的特征提取方法檢索效果最好,其查全率-查準率曲線如圖6所示。

圖6 查全率-查準率曲線(曲率不均勻模型)

6 結(jié)束語

本文定義了三維模型的曲度作為特征用于檢索,將曲度表示為平均曲率和高斯曲率的和,包含了平均曲率和高斯曲率的信息,能較全面地反映模型表面的總體特征,其檢索性能要優(yōu)于單純使用平均曲率或是高斯曲率的檢索性能。但是,由于曲度的計算依賴于離散網(wǎng)格曲面曲率的計算,而離散網(wǎng)格上曲率的計算易受噪聲的影響且計算量大,因此,更魯棒、簡單的曲率計算是下一步的改進方向。

［1]Torkhani F,Wang K,Chassery J M.A Curvature-tensorbased PerceptualQuality Metric for 3DTriangular Meshes［J］.Machine Graphics&Vision,2013,32(16): 1-25.

［2]Liu Yujie,Zhang Xiaodong,Li Zongmin,et al.Extended Cone-curvature Based Salient Points Detection and 3D ModelRetrieval［J］.MultimediaToolsand Applications,2013,64(3):671-693.

［3]Cho J W,ProstR,JungHY.AnOblivious Watermarkingfor3-DPolygonalMeshesUsing Distribution of Vertex Norms［J］.IEEE Transactions on Signal Processing,2007,55(1):142-155.

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

［5]唐 祺,楊 新.基于高斯核密度函數(shù)和輪廓的三維模型檢索［J］.計算機工程,2013,39(10):172-180.

［6]姜 陽,呂學強,付成睿,等.基于邊界點描述符的三維模型檢索研究［J］.微電子學與計算機,2013, 30(10):71-74.

［7]馬自萍,康寶生,馬金林.W-系統(tǒng)矩和Fourier變換下Volume Descriptors不變特征的三維模型檢索［J］.計算機輔助設(shè)計與圖形學報,2014,26(4):519-616.

［8]Kang S B,Ikeuchi K.Determining 3-D Object Pose Using the Complex Extended Gaussian Image［C］// ProceedingsofComputerVisionandPattern Recognition.Lahaina,USA:IEEE Computer Society, 1991:580-585.

［9]Kazhdan M,Chazelle B,Dobkin D,et al.A Reflective Symmetry Descriptor for 3D Models［J］.Algorithmica, 2004,38(1):201-25.

［10]Osada R,FunkhouserT,ChazelleB,etal.Shape Distributions［J］.ACM Transactions on Graphics,2002, 21(4):807-832.

［11]Shum H Y,HebertM,IkeuchiK.On3DShape Similarity［C］//Proceedings of Computer Vision and Pattern Recognition.Ottawa,Canada:IEEE Computer Society,1996:526-531.

［12]Chua C S,JarvisR.PointSignatures:ANew Representation for 3D Object Recognition［J］.International Journal of Computer Vision,1997,25(1):63-85.

［13]Xu Guoliang.DiscreteLaplace——BeltramiOperators and Their Convergence［J］.Computer Aided Geometric Design 2004,21(8):767-784.

［14]Dyn N,Hormann K,Kim S J,et al.Optimizing 3D Triangulations Using Discrete Curvature Analysis［J］.Mathematical Methods for Curves and Surfaces,2001, 38(8):135-146.

編輯 金胡考

A 3D Model Retrieval Algorithm Based on Local Feature

TU Hong,GENG Guohua
(School of Information Science and Technology,Northwest University,Xi’an 710127,China)

Feature extraction is the most important technology in content-based 3D model retrieval.This paper proposes an algorithm for feature extraction based on curvature features of 3D triangle model.The curvature of 3D model can become the sum of Gaussian curvature and mean curvature.So it is a blend of the Gaussian curvature and mean curvature.It can estimate the curvature of 3D model’s vertices through the discrete differential geometry,and build a feature vector of 3D model.Experimental results show that the algorithm of this paper is better than the average curvature or Gaussian curvature as the feature vector.

3D model retrieval;camber;Gaussian curvature;mean curvature;feature extraction

屠 宏,耿國華.一種基于局部特征的三維模型檢索算法［J］.計算機工程,2015,41(3):218-222.

英文引用格式:Tu Hong,Geng Guohua.A 3D Model Retrieval Algorithm Based on Local Feature［J］.Computer Engineering,2015,41(3):218-222.

1000-3428(2015)03-0218-05

:A

:TP18

10.3969/j.issn.1000-3428.2015.03.041

國家自然科學基金資助項目(60873094)。

屠 宏(1979-),女,博士研究生,主研方向:圖形圖形處理,機器學習;耿國華,教授、博士生導(dǎo)師。

2014-03-24

:2014-05-06E-mail:tuhong7903@gmail.com