李 瑞,劉 磊,盛 蘊(yùn),張桂戌

(華東師范大學(xué) 計(jì)算機(jī)科學(xué)與軟件工程學(xué)院,上海 200062)

一種改進(jìn)的三維網(wǎng)格凸度衡量方法

李 瑞,劉 磊,盛 蘊(yùn),張桂戌

(華東師范大學(xué) 計(jì)算機(jī)科學(xué)與軟件工程學(xué)院,上海 200062)

針對現(xiàn)有方法需要不斷地調(diào)整投影方向、時(shí)間消耗大的缺點(diǎn),提出了一種改進(jìn)的三維網(wǎng)格凸度衡量方法,該方法只需在物體主方向投影一次,減少了時(shí)間消耗.該方法首先采用主成分分析(Principal Component Analysis,PCA)計(jì)算網(wǎng)格模型的主方向,然后計(jì)算模型在主方向上的投影面積和網(wǎng)格模型中每個(gè)面片在主方向上的投影面積之和,將它們的比值作為凸度值的初始估計(jì),最后在主方向上對模型進(jìn)行切片處理,計(jì)算所有切片的二維凸度值的加權(quán)平均,并將其作為凸度值的修正.實(shí)驗(yàn)結(jié)果證明,這種改進(jìn)的凸度衡量方法在計(jì)算速度上比現(xiàn)有方法更快,而且更加符合人類的視覺感知.

形狀分析; 凸度衡量; 主成分分析

0 引 言

形狀分析是計(jì)算機(jī)視覺、模式識別和計(jì)算機(jī)圖形學(xué)中的基礎(chǔ)性問題.形狀的幾何特征提取是形狀分析的一個(gè)子方向,常用的幾何特征有凸度[1-2]、線性度[3-5]、緊密度[6]、橢圓度[7]和對稱度[8]等.其中,凸度在形狀分解[9]、分類[10]和檢索[11-12]等領(lǐng)域得到了廣泛的研究,在人類的視覺感知中扮演著重要角色[13-14].凸的物體具有顯著的視覺特征和簡單的幾何特性[13,15],所以基于視覺顯著性的模型分解往往把模型的凸度值作為分解的依據(jù)[9,16-18],這種基于凸度值的分解比單純的基于嚴(yán)格凸模型的分解具有更好的魯棒性,而且可以把凸度值設(shè)為分解的閾值,控制分解的細(xì)致程度[9].

在三維空間中,只有當(dāng)網(wǎng)格模型內(nèi)任意兩點(diǎn)之間的連線都在這個(gè)模型的內(nèi)部時(shí),這個(gè)模型才是一個(gè)完全凸的模型.一般來說,三維網(wǎng)格模型的凸度衡量方法需要滿足以下4個(gè)基本條件[1,19].

(1)任意網(wǎng)格模型的凸度值都是一個(gè)實(shí)數(shù),并且在0到1之間.

(2)只有當(dāng)網(wǎng)格模型是完全凸的時(shí)候,其凸度值才為1.

(3)一定存在這樣的網(wǎng)格模型,它的凸度值無限接近于0.

(4)凸度衡量方法對于給定的網(wǎng)格模型必須滿足相似變換不變性.

1 相關(guān)工作

本文將回顧幾種常用的二維和三維凸度衡量方法.為了能區(qū)別二維和三維的凸度衡量方法,我們用小寫字母c表示二維凸度衡量方法,用大寫字母C表示三維凸度衡量方法.

1.1 二維形狀的凸度衡量方法

二維凸度的衡量方法已經(jīng)得到了廣泛的研究,其中最常用的是將形狀本身的面積與其凸包的面積的比值作為凸度值[1].

定義1 給定一個(gè)二維形狀s,其凸包為CH(s),則它的凸度c1(s)為

公式(1)中,c1是一種簡單而高效的衡量方法,具有較強(qiáng)的抗噪性,但它對邊界的變化不敏感,比如對細(xì)長的凹陷反映不敏感[1].基于周長的凸度衡量方法解決了這個(gè)問題.在基于周長的凸度衡量方法中,對于任意一個(gè)二維形狀s,它的周長和凸包的周長一定存在著

這樣的關(guān)系,當(dāng)s為完全凸的時(shí)候,公式(2)兩邊才相等.因此,s的凸包周長與其本身周長的比值可用作凸度值的衡量.

定義2 給定一個(gè)二維形狀s,其凸包表示為CH(s),則它的凸度c2(s)為

因?yàn)閏2是一種基于周長的凸度衡量方法,它對邊界的變化較為敏感,所以抗噪性比c1要差.

還有一些與凸包無關(guān)的凸度衡量方法,如ˇZuni′c等人[1]提出了一種基于邊界投影的方法,這種方法需要不斷旋轉(zhuǎn)圖形來尋找一個(gè)使凸度值最小的外接矩形;Rosin等人[20]提出了一種具有對稱性的凸度衡量方法,與基于凸包的方法不同,這種方法通過一個(gè)凸多邊形去逼近原始多邊形,以這個(gè)凸多邊形與原多邊形的面積的比值作為凸度值;在此方法的基礎(chǔ)上,Kolensnikov等人[21]提出了一種基于動態(tài)規(guī)劃的優(yōu)化算法來計(jì)算最優(yōu)擬合多邊形;Rahtu等人[22]提出了一種基于概率的凸度衡量方法,這種方法通過計(jì)算圖形內(nèi)任意兩點(diǎn)連線上的某一點(diǎn)屬于圖形內(nèi)部的概率來計(jì)算凸度.

1.2 三維網(wǎng)格的凸度衡量方法

相比于二維凸度衡量方法,三維網(wǎng)格的凸度衡量方法并沒有得到廣泛的研究.一些二維的凸度衡量方法可直接擴(kuò)展到三維空間,與定義1中的二維凸度衡量方法類似,一種常用的基于體積的三維網(wǎng)格凸度衡量方法為網(wǎng)格自身體積與其凸包的體積之比.

定義3 給定一個(gè)三維網(wǎng)格M,其凸包為CH(M),則它的凸度C1(M)為

值得注意的是,本文所提及的三維網(wǎng)格都是三維封閉網(wǎng)格.與c1類似,C1同樣對于細(xì)長的凹陷不敏感[2],而且對于具有相同體積和凸包體積的網(wǎng)格模型,根據(jù)C1的計(jì)算方法會得到相同的凸度值,而這在很多情況下是不合理的,如圖1所示.

而一些二維的凸度衡量方法不能直接擴(kuò)展到三維空間,如果我們把基于邊界的二維凸度衡量方法c2直接擴(kuò)展到三維空間,則二維空間中形狀的邊界可以看作是三維空間中網(wǎng)格的表面積.在二維空間中,一定存在不等式(2),但在三維空間中,卻不存在關(guān)于網(wǎng)格模型表面積與其凸包的表面積的不等式.這是因?yàn)閷τ谝恍╊愃朴趫D2的網(wǎng)格模型,存在

不等關(guān)系;而對于一些類似于中空立方體的網(wǎng)絡(luò)模型(見圖8),卻存在相反的不等關(guān)系

因此,不能直接將二維的c2擴(kuò)展到三維空間.

圖1 具有相同的體積與凸包體積的網(wǎng)格模型Fig.1 Different meshes with identical mesh and convex hull volumes

圖2 一個(gè)具有很多空洞的立方體模型Fig.2 A cube with many holes

為了解決方法C1對細(xì)長凹陷不敏感的問題,Lian等人[2]提出了一種基于投影的三維網(wǎng)格凸度衡量方法,該方法是由文獻(xiàn)[1]擴(kuò)展而來.

定義4 給定一個(gè)三維網(wǎng)格模型M,它的凸度值可以定義為

公式(7)中,Pface(M,α,β,γ)和Pview(M,α,β,γ)是網(wǎng)格模型分別繞x,y和z軸旋轉(zhuǎn)α,β和γ角度后的Pface和Pview,其中,Pface是網(wǎng)格上所有面片分別在坐標(biāo)平面XOY,Y OZ和ZOX上的投影面積之和,即

Pview是網(wǎng)格模型在平行于坐標(biāo)平面的外包立方體上的投影面積之和,因?yàn)橥獍⒎襟w有6個(gè)面,所以Pview可以表示為

圖3(a)表示網(wǎng)格模型中的一個(gè)三角面片在坐標(biāo)平面上的投影.圖3(b)表示網(wǎng)格模型在三個(gè)坐標(biāo)平面的投影,即Pviewx,Pviewy和Pviewz.對于所有的網(wǎng)格模型都存在不等關(guān)系

只有當(dāng)網(wǎng)格模型為完全凸的時(shí)候等號才成立.而不斷的旋轉(zhuǎn)模型,是為了找到一個(gè)最小的凸度值作為模型最終的凸度值.

由于最小化C2(M)的計(jì)算是一個(gè)非線性的優(yōu)化問題,傳統(tǒng)的優(yōu)化方法不能解決,因此Lian提出了用遺傳算法進(jìn)行求解.在計(jì)算Pview時(shí),需要將網(wǎng)格模型在3個(gè)坐標(biāo)平面上進(jìn)行透視投影,然后提取出緩沖區(qū)中的投影圖,借此來估算投影面積.而遺傳算法需要多次迭代,每次迭代又需要多次計(jì)算每個(gè)個(gè)體的值,導(dǎo)致該方法運(yùn)行耗時(shí),不方便使用,因此需要設(shè)計(jì)一種快速的凸度衡量方法.

基于以上問題,本文提出了一種改進(jìn)的三維網(wǎng)格模型的凸度衡量方法.該方法同樣是一種基于投影的方法,是對Lian的方法的一種改進(jìn).Lian的方法計(jì)算速度過慢的原因在于遺傳算法需要多次計(jì)算投影面積,而本文的思想是只在特定方向上投影一次,再對在此方向上計(jì)算的投影比值進(jìn)行修正,以最后的修正值作為網(wǎng)格的凸度值.因?yàn)檫@種新方法結(jié)合了基于體積的方法和基于表面積的方法,因此其具有基于體積的方法的抗噪性,又能對細(xì)長的凹陷較為敏感,而且相對于C2,新方法大大縮短了計(jì)算時(shí)間.

圖3 Pface與Pview的示意圖Fig.3 Illustration of Pface and Pview

2 改進(jìn)的三維網(wǎng)格模型的凸度衡量

本文提出了一種改進(jìn)的三維模型凸度衡量方法,通過旋轉(zhuǎn)模型至某一固定方向,并對3個(gè)坐標(biāo)平面進(jìn)行投影來估計(jì)凸度的初始值;然后平行于每個(gè)坐標(biāo)平面方向?qū)δＰ瓦M(jìn)行切片,通過計(jì)算切片的凸度值對初始估值進(jìn)行修正,從而得到最終的凸度值.該方法用公式表達(dá)為

其中,R是將網(wǎng)格旋轉(zhuǎn)至特定方向的旋轉(zhuǎn)矩陣,Corr()是對初始估值的修正函數(shù).

2.1 主方向上的初始估值

如上所述,我們希望通過旋轉(zhuǎn)矩陣R把網(wǎng)格模型旋轉(zhuǎn)至某一特定方向,通過這一方式來替代Lian的方法中耗時(shí)的遺傳算法.從定義4可知,通過旋轉(zhuǎn)模型至某一個(gè)特定方向,C2最終會達(dá)到一個(gè)最小值.一般來說,只有當(dāng)模型的所有面片在三個(gè)坐標(biāo)平面投影具有最大重合時(shí),C2才會達(dá)到最小值.因此,我們的目標(biāo)就是不通過優(yōu)化算法,只旋轉(zhuǎn)一次就讓投影重疊的面積接近于最大值.

這里我們采用了主成分分析(PCA)來對旋轉(zhuǎn)方向進(jìn)行估計(jì),這主要是基于以下兩點(diǎn)原因.首先,PCA是一種常用的降維方法,通過對數(shù)據(jù)集協(xié)方差矩陣進(jìn)行特征分解,得到數(shù)據(jù)集的主方向及其權(quán)值,數(shù)據(jù)集在主方向上具有最大的方差.因此PCA可以保證面片在坐標(biāo)平面上的投影具有相對較大的重疊面積,從而獲得一個(gè)相對較小的初始估值.其次,在接下來的修正過程中,垂直于主方向?qū)δＰ瓦M(jìn)行切片比其他方向更能表示出模型的幾何特征.

假設(shè)E為網(wǎng)格頂點(diǎn)的特征向量所組成的協(xié)方差矩陣,把公式(11)中的參數(shù)R用E代替,則在主方向上的凸度的初始估值Ce可以表示為

圖4顯示了4個(gè)三維網(wǎng)格模型的主方向,以及模型在坐標(biāo)平面上的投影.從圖中可以看出,初始估值Ce(M)與經(jīng)過遺傳算法優(yōu)化后的值C2(M)比較接近.

圖4 模型在主方向坐標(biāo)系下的投影以及C2和Ce的值Fig.4 Mesh silhouettes along the principal axes with the mesh convexity values calculated by C2and Ce

但在主方向上的估計(jì)也有一定的局限性.在Pview與Pface比值最小的方向上,網(wǎng)格表面投影重疊最多,而主方向只能反映網(wǎng)格頂點(diǎn)在此方向上的方差最大.對于不是完全凸的網(wǎng)格,在主方向上可能沒有投影重疊的表面,即在主方向上比值為1.如圖5所示,圖中的網(wǎng)格是一個(gè)工程部件的模型,可以計(jì)算出在主方向上的投影面積比為1,但是它并不是完全凸的.通過以上的例子可以看出,若直接用主方向上的比值代替最小比值作為網(wǎng)格的凸度值,不能滿足凸度衡量方法的條件2,因此需要對主方向上的初始估值進(jìn)行修正.

圖5 一個(gè)用PCA會產(chǎn)生錯(cuò)誤估計(jì)的模型Fig.5 An example whose convexity is overestimated by PCA

2.2 初始估值的修正

缺少合理高效的三維網(wǎng)格凸度衡量方法的一個(gè)重要原因是三維模型比二維形狀的復(fù)雜度高.若能將三維網(wǎng)格的凸度問題轉(zhuǎn)化為二維形狀的凸度問題,那么借助于常用的二維凸度衡量方法,三維網(wǎng)格的凸度也能方便的計(jì)算出來.在二維凸度計(jì)算中,c1和c2是最基本的凸度衡量方法,我們把模型沿著主方向坐標(biāo)軸進(jìn)行切片,通過對切片進(jìn)行二維凸度值測量來對初始估值進(jìn)行修正.

類似于醫(yī)學(xué)上斷層掃描的思想,我們也可以在三個(gè)方向?qū)W(wǎng)格模型進(jìn)行“切片”.如圖6所示,圖中只顯示了沿一個(gè)方向的切片,此方向上的切片都是凸的,但是在另外兩個(gè)正交方向上存在凹切片.通過切片處理,一個(gè)網(wǎng)格模型被轉(zhuǎn)換為一系列的二維形狀,而這些二維形狀的凸度則反映了原始網(wǎng)格的凸度值.因此,我們使用這些二維形狀的凸度值來計(jì)算每個(gè)主方向的修正系數(shù).

圖6 三維網(wǎng)格切片示意圖Fig.6 An illustration of mesh slicing

本文通過計(jì)算切平面與網(wǎng)格的交點(diǎn)得到切片,由于網(wǎng)格模型的表面一般凹凸不平,如圖7所示,以上方法所得切片的邊界常呈鋸齒狀,而基于邊界的方法c2對邊界的變化非常敏感,若采用c2進(jìn)行凸度計(jì)算,則會產(chǎn)生較大誤差.因此我們采用基于面積的方法c1來消除邊界噪聲產(chǎn)生的影響.

圖7 三維網(wǎng)格表面Fig.7 The surface of 3d mesh

假設(shè)我們在某一方向上把三維網(wǎng)格模型切成N+1份,每個(gè)切片之間是等距的,則修正系數(shù)可以表示為

其中,Area(si)是第i個(gè)切片的面積,Area(CH(si))是第i個(gè)切片對應(yīng)的凸包的面積.實(shí)際上,計(jì)算Area(si)是比較復(fù)雜的,通過改變公式(13),將其分子分母同時(shí)乘以切片的間距l(xiāng)step,則可變?yōu)?/p>

在N足夠大的時(shí)候,分子可約等于模型的體積.

為了使切片數(shù)量根據(jù)網(wǎng)格模型的精度自適應(yīng)調(diào)整,保留更多的幾何特征,我們提出平均網(wǎng)格邊長的概念.網(wǎng)格模型中所有邊長的平均值即為平均網(wǎng)格邊長l,我們把平均網(wǎng)格邊長的一半作為切片的步長,即

假設(shè)模型在某一主方向上最大的投影長度為L,那么總的切片數(shù)量為N=L/lstep.為了控制切片數(shù)量,我們設(shè)置了一個(gè)最大閾值Nmax,當(dāng)N等于或超過這個(gè)閾值時(shí),則用最大閾值作為切片數(shù)量,即

針對本文中用到的模型,我們將Nmax默認(rèn)設(shè)置為200.如果Nmax設(shè)置的較小,則會影響凸度計(jì)算的精度,如果Nmax設(shè)置的較大,則會增加凸度的計(jì)算時(shí)間,綜上,三個(gè)方向的修正項(xiàng)最終可以表示為

定義5 對于一個(gè)給定的三維網(wǎng)格M,它的凸度值C3(M)為

其中,

為了證明C3的可行性,我們需要驗(yàn)證它是否滿足凸度衡量方法的4個(gè)基本條件.

證 明:如果網(wǎng)格模型M是完全凸的,則每一個(gè)二維的切片都是凸的,那么rx=ry=rz=1.另一方面,在任意方向上Pview(ME)=Pface(ME),所以C3(M)=1恒成立,條件2得證.當(dāng)M不是完全凸的時(shí)候,必定存在某些切片是非凸的,則rx,ry,rz∈(0,1],而任意一個(gè)模型在主方向上Pview≤Pface一定成立,根據(jù)公式(18)和公式(19),我們可以得出C3(M)≤1,條件1得證.由于主方向的計(jì)算與網(wǎng)格初始的狀態(tài)和網(wǎng)格的位置無關(guān),而修正項(xiàng)是在主方向的基礎(chǔ)上進(jìn)行的計(jì)算,因此最后計(jì)算出的凸度值具有平移旋轉(zhuǎn)不變性.又因C3(M)是基于比值的計(jì)算,因此具有縮放不變性,條件4得證.

為了證明條件3,我們構(gòu)造出一個(gè)中空的立方體,如圖8所示.假設(shè)立方體的外邊長為a,內(nèi)邊長為b,則

當(dāng)不斷增大b,使其無限接近于a時(shí),

條件3得證.至此,我們已經(jīng)證明了定義C3滿足凸度衡量的基本條件.

圖8 中空立方體Fig.8 The hollow cube

此外,如果采用Lian的方法計(jì)算中空立方體的凸度,則

如果不斷減少b,直到b=0,則C2(M)=1;而如果不斷增加b,使其無限接近于a,由C2計(jì)算的凸度值為

本文認(rèn)為這是一種不合理的情況.

3 實(shí)驗(yàn)結(jié)果對比與分析

本節(jié)我們對一些來自公共數(shù)據(jù)庫里的模型進(jìn)行定量分析.第3.1節(jié)與其他三維網(wǎng)格凸度衡量方法進(jìn)行對比;第3.2節(jié)與Lian的方法進(jìn)行計(jì)算時(shí)間的對比.

3.1 實(shí)驗(yàn)分析

為了證明本文方法的有效性,我們采用McGill Articulated 3D Shape Benchmark和Princeton Benchmark[23]數(shù)據(jù)庫中的網(wǎng)格模型進(jìn)行實(shí)驗(yàn).在實(shí)驗(yàn)之前,我們先對網(wǎng)格模型進(jìn)行預(yù)處理,將網(wǎng)格模型的重心設(shè)為坐標(biāo)系原點(diǎn).

圖9 不同凸度衡量方法的對比Fig.9 The comparison of different convexity measures

圖9顯示的是用不同凸度衡量方法計(jì)算出的凸度值,網(wǎng)格模型按照C3的值進(jìn)行排序.通過結(jié)果可以看出,本文方法對模型1,3,6,7和8計(jì)算的凸度值較低,相反,C2的值較大.從模型18我們可以看出,單純基于體積的方法C1對于細(xì)長的凹陷并不敏感,而C2和C3卻能夠給出合理的結(jié)果.由于公式(14)是一個(gè)近似計(jì)算,對于球形模型會產(chǎn)生一個(gè)較大的誤差,所以模型23計(jì)算出的值并不是完全凸的.

為了更好的表明C2與C3的區(qū)別,我們?nèi)藶樵O(shè)計(jì)了4個(gè)模型,如圖10所示,當(dāng)內(nèi)邊界b分別等于0,0.2a,0.5a和0.8a時(shí),C2與C3的凸度值不斷地減少,這符合我們的視覺感知.

圖11顯示的是一個(gè)具有較深凹槽的立方體,當(dāng)凹槽的寬度n趨近于0的時(shí)候,凹槽的體積趨近于0,則此時(shí)C1(M)為

圖10 不斷增大b時(shí)的凸度值Fig.10 The hollow cubes with broadening b

圖11 一個(gè)具有深凹的立方體模型Fig.11 A cube with a deep dent

然而這個(gè)值不能反映出凹槽的存在,而C3卻可以探測到這個(gè)凹槽的存在,

對于圖1的兩個(gè)模型,C3計(jì)算出的凸度值分別為0.6756和0.7483,即凹陷深的模型,凸度值較低.而C1只受到凹陷的體積的影響,沒有考慮到凹陷是在模型的邊緣區(qū)域還是內(nèi)部區(qū)域.

圖12顯示的是同一手模型在不同姿勢下的凸度.從圖中可以看出,5個(gè)手指完全張開時(shí),凸度值最大.而當(dāng)手指彎曲的程度越高或彎曲手指越多時(shí),其凸度值越小,這與人們心理上對凸度的衡量是一致的.

圖12 不同手勢的凸度值Fig.12 Hand gestures calculated by C3

本文從MPI-FAUST、McGill Articulated 3D Shape Benchmark和Princeton Benchmark數(shù)據(jù)庫中提取了80個(gè)網(wǎng)格模型,共分為5個(gè)類別,圖13顯示的是其中的一些樣本.我們把模型的凸度作為特征進(jìn)行了分類實(shí)驗(yàn),實(shí)驗(yàn)采用的k近鄰分類算法,由于樣本集較小,我們采用了留一法交叉驗(yàn)證(Leave-one-out Cross Validation).當(dāng)采用C2作為特征進(jìn)行分類時(shí),分類的準(zhǔn)確率為81.25%,而當(dāng)采用C3作為特征進(jìn)行分類時(shí),分類的準(zhǔn)確率提升到了85.00%.由于此處采用的是單一全局特征作為分類的特征,不能達(dá)到較高的分類準(zhǔn)確率,當(dāng)把C2和C3作為特征進(jìn)行分類時(shí),分類的準(zhǔn)確率達(dá)到了92.50%.

圖13 5類模型的樣本Fig.13 Samples of 5 types of meshes

3.2 算法的時(shí)間復(fù)雜度分析

Lian在算法中使用的參數(shù)為50個(gè)個(gè)體,進(jìn)行200次迭代.當(dāng)網(wǎng)格模型的頂點(diǎn)非常多的時(shí)候,此算法的執(zhí)行速度較慢.與Lian的方法不同,本文的方法避免使用遺傳算法多次從幀緩存中讀取圖像,而只需計(jì)算一次投影面積.表1顯示了在計(jì)算網(wǎng)格模型的凸度時(shí),本文方法與Lian的方法在時(shí)間消耗上的對比.本文使用的實(shí)驗(yàn)環(huán)境是:CPU為Intel CORE i5;內(nèi)存為6GB;編程環(huán)境為 Microsoft Visual Studio 2010.Lian的方法時(shí)耗的計(jì)算以從緩沖區(qū)讀取圖像的時(shí)間為基準(zhǔn),再將此時(shí)間乘以迭代次數(shù)得到運(yùn)行總時(shí)間(實(shí)際運(yùn)行時(shí)間比表中顯示的時(shí)間更長).從表中可以看出,本文方法與Lian的方法相比,大大減少了時(shí)耗.

4 結(jié) 論

為了解決現(xiàn)有三維網(wǎng)格模型凸度衡量方法的缺點(diǎn),本文提出了一種根據(jù)Lian的方法C2進(jìn)行改進(jìn)的方法C3.與C1相比,C3可以探測到細(xì)長的凹陷,而且對于具有相同體積和相同凸包體積的模型,C3能夠根據(jù)凹陷的深淺進(jìn)行凸度計(jì)算,而不是單純的計(jì)算體積比,這更加符合人類的視覺感知.與C2相比,C3通過引入基于面積的二維形狀的凸度計(jì)算,使該方法具有了基于體積的方法與基于投影的方法的特點(diǎn).通過先確定主方向再進(jìn)行投影,C3極大的縮短了C2的計(jì)算時(shí)間,這使其更能適用于實(shí)際應(yīng)用.

表 1 時(shí)間消耗對比Tab.1 Comparison of time consumptions

[1]ˇZUNI′C J,ROSIN P L.A new convexity measure for polygons[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(7):923-934.

[2] LIAN Z,GODIL A,ROSIN P L,et al.A new convexity measurement for 3D meshes[C]//Computer Vision and Pattern Recognition(CVPR),2012 IEEE Conference on.IEEE,2012:119-126.

[3]ˇZUNI′C J,ROSIN P L.A rectilinearity measurement for polygons[C]//European Conference on Computer Vision.Berlin:Springer,2002:746-758.

[4] LIAN Z,ROSIN P L,SUN X.Rectilinearity of 3D meshes[J].International Journal of Computer Vision,2010,89(2/3):130-151.

[5] ROSIN P L.A two-component rectilinearity measure[J].Computer Vision and Image Understanding,2008,109(2):176-185.

[6]ˇZUNI′C J,HIROTA K,MARTINEZ-ORTIZ C.Compactness measure for 3D shapes[C]//Informatics,Electronicsamp;Vision(ICIEV),2012 International Conference on.IEEE,2012:1180-1184.

[7] ROSIN P L.Measuring shape:Ellipticity,rectangularity,and triangularity[J].Machine Vision and Applications,2003,14(3):172-184.

[8] LEOU J J,TSAI W H.Automatic rotational symmetry determination for shape analysis[J].Pattern Recognition,1987,20(6):571-582.

[9] REN Z,YUAN J,LIU W.Minimum near-convex shape decomposition.[J].IEEE Transactions on Pattern Analysisamp;Machine Intelligence,2013,35(10):2546-2552.

[10] ROSIN P L.Classification of pathological shapes using convexity measures[J].Pattern Recognition Letters,2009,30(5):570-578.

[11] SARFRAZ M,RIDHA A.Content-based image retrieval using multiple shape descriptors[C]//Ieee/acs International Conference on Computer Systems and Applications.2007:730-737.

[12] YANG Y B,LIN H,ZHU Q.Content-based 3D model retrieval:A survey[J].Chinese Journal of Computers,2004,27(10):1297-1310.

[13] BIEDERMAN I.Recognition-by-components:A theory of human image understanding[J].Psychological Review,1987,94(2):115.

[14] SIDDIQI K,KIMIA B B.Parts of visual form:Computational aspects[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17(3):239-251.

[15] SINGH M,HOFFMAN D D.13-part-based representations of visual shape and implications for visual cognition[J].Advances in Psychology,2001,130:401-459.

[16] LIU H,LIU W,LATECKI L J.Convex shape decomposition[C]//Computer Vision and Pattern Recognition(CVPR),2010 IEEE Conference on.IEEE,2010:97-104.

[17] GHOSH M,AMATO N M,LU Y,et al.Fast approximate convex decomposition using relative concavity[J].Computer-Aided Design,2013,45(2):494-504.

[18] ASAFI S,GOREN A,COHEN-OR D.Weak convex decomposition by lines-of-sight[J].Computer Graphics Forum,2013,32(5):23-31.

[19] 劉磊.三維網(wǎng)格特征提取與分割[D].上海:華東師范大學(xué),2015.

[20]ROSIN P L,MUMFORD C L.A symmetric convexity measure[J].Computer Visionamp;Image Understanding,2004,103(2):101-111.

[21] KOLESNIKOV A,FRANTI P.Optimal algorithm for convexity measure calculation[C]//IEEE International Conference on Image Processing.2005:353-356.

[22] RAHTU E,SALO M,HEIKKILA J.A new convexity measure based on a probabilistic interpretation of images[J].IEEE Transactions on Pattern Analysisamp;Machine Intelligence,2006,28(9):1501-1512.

[23]CHEN X,GOLOVINSKIY A,FUNKHOUSER T.A benchmark for 3D mesh segmentation[J].ACM Transactions on Graphics,2009,28(3):341-352.

(責(zé)任編輯:李 藝)

An improved convexity measure for 3D meshes

LI Rui,LIU Lei,SHENG Yun,ZHANG Gui-xu
(School of Computer Science and Software Engineering,East China Normal University,Shanghai200062,China)

In this paper we proposed an improved 3D mesh convexity measure by projecting only once a given 3D mesh onto the orthogonal 2D planes along its principal directions.Unlike the previous work which was time-consuming and required constant adaptations of the projection direction,we used the calculated result along the principal directions as an initial estimate of mesh convexity,followed by a correction process.In the initial estimation,our measure computed only once the summed area ratio of mesh silhouette images to mesh faces,along the principal directions of the mesh.Then,the mesh was sliced into a number of 2D cross sections along its principal directions.Finally,a 2D convexity measure for the 2D sliced cross sections was employed to correct the convexity overestimated by the initial estimation.Experimental results had demonstrated the effectiveness and effciency of the improved convexity measure against the existing ones.

shape analysis;convexity measure;principal component analysis

TP391.4

A

10.3969/j.issn.1000-5641.2017.06.006

1000-5641(2017)06-0063-13

2016-08-16

國家自然科學(xué)基金(61202291)

李 瑞,男,碩士研究生,研究方向?yàn)橛?jì)算機(jī)圖形學(xué).E-mail:15201802836@163.com.

盛 蘊(yùn),男,副教授,碩士生導(dǎo)師,研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、計(jì)算機(jī)視覺等.

E-mail:ysheng@cs.ecnu.edu.cn.