三维模型形状描述子研究

UniversityofScienceandTechnologyAdissertationforbachelor’sStudyOnShapeDescriptorsfor3DModelsAuthor’sName: ChaoTang Prof.LigangLiuFinishedTime: May,2016第一章绪 引 课题研究的意 相关工 本文的工 本文的结 第二章ShapeDistribution Shape 实验结果与分 第三章LightField LightField 3D网格投影成二维图 图像描述 Fourier Zernike Fourier联合 实验结果和讨 联合Mini 第四章Shape Bagof Bagof Spatially-SensitiveBagof BoF&SS- 方法比 第五章总结与展 研究内容总 展 索技术如识图谷歌识图技术，检索技术扎根于生活的方方面面，更影响CEO科再奇提到：2015年将是另外一个猛，数量级直图像，因而对于3D模型的检索技术的研究势在必行。3D模型检索的一大方向是通过将模型简化成相应的形状描述子，从而将对于3D模型的比较转化为对于形状描述子的比较。DataDataResultS12Feature;(这一步在有些情况可以不需要SDD(ShapeDistributionDescriptor)采用了统计的方法，通过将模型简化成概率分布并比较相应的概率分布图达到对于模型的比较；LFD(LightFieldDe-scriptor)采用的是二维图像比较的方法，通过对于模型不同视角的采样得到一矩，从而达到对于三维模型的比较；Shape方法采用了基于HK(HeatKer-nel)/HKS(HeatKernelSignature)Feature以及文本检索和图像检索的常用的BOF(BagOfFeature)/SS-BOF(SpatiallySensitiveBagofFeature)得到相应的描述模型之间的相似性比较方法很多。和熟知的多数据检索一样，模型的检索同样可以有基于文本和基于内容两种不同的方法。的3DWare-HouseTag，基于Tag的语义信息自然也可以得到模型的相似程度。然而，这样得到的结果往往不符合预期，达不到在文本检索中的体验。此时基于内容的模型匹配可以得到更加符合认知的结果。本：三维网格描述子光场描述子热核热核签名BagofFeatureSpatillaySensitiveBagOfFeature形状描述子Shape非刚性变换AlongwiththeamazingdevelopmentofIntetechnique,thedemandforre-trievaltechnologyisgrowingmuchquickly.Fromsimpletextretrieval,likesearchengine,toone-dimensionalsoundretrievalandtwo-dimensionalimageretrieval,re-trievaltechniqueischainseparablepartinpeople’sdailylife.Moreover,retrievaltechniqueisalwayschangingourworkstyleandimprovingworkefficiency.Atthesametime,theCEOofInhasmentionedthatyear2015isawatershed,asitwitnessedtheevolutionfrom2Dtechniquesto3Dtechniques.Recently,theamountof3Dmod-elsgrowssofastthathasbeennearlyclosetotheamoutof2Dimages.Therefore,theresearchof3DModelsretrievaltechniqueisnecessary.Animportantmethodof3Dretrievaltechniqueistosimplifythe3dmodelstoshapedescriptors.Inthisway,the3dmodelscanbecomparedbycomparingtheshapedescriptorsinstead.DataData:modelResult:Thedescriptorcorrespondtomodel12calculatemodel’sfeaturebymodel;(Thisstepisnot3calculatedescriptorby0.2:TheStepofcalculatingInthispaper,wefocusonthreekindofdescriptorswhicharebasedondifferentSDD(ShapeDistributionDescriptor)isbasedonstatisticaltheory,bywhichev-ery3DmodelissimplifiedasaPDF(probabilitiesdistributionfunction).ThereforethesimilaritybetweentwomodelscanbemeasuredbythesimilarityofthetwocorrespondPDFs.LFD(LightFieldDescriptor)isbasedon2-dimensionalimages’method.Bypro-jectinginto2-dimensionalspace,3Dmodelisconvertedtoasetofimage.So,fortheilaritybetweentwo3Dmodel.Themethod–Shape,whichcombiningHK(HeatKernel)/HKS(HeatKernelSignature)andBOF(BagofFeature)/SS-BOF(SpatiallySen-sitiveBagofFeature)whichiscommonintextretrieval,obtainsarobustresultonnon-rigidmodels.Therearemanykindsofmethodoncomparingthesimiliaritybetweenmodels.Likethemuti-mediadataretrieval,whichiswellknowntous,themethodofretrievalcanbedividedintotwodirections:oneisbasedontext,anotherisbasedoncontent.Theavailablityoflargedatasetsof3Dmodelswithtagssuchas3DWarehousemeetourexpectationsandthesameexperienceontextsearching.Now,themethodbasedoncontentcanprovideabetterresultandthethreemethodmentioninthispaperareallbasedoncontent.KeyWords:3DMesh,Descriptor,LightFieldDescriptor,HeatKernel,HeatKernelSignature,BagofFeature,Spatially-SensitiveBagofFeature,Shape,ShapeDe-scriptor,Non-rigid第一 绪一方面随着三维数据生成和的能力的提升，另一方面得益于人们对于三据的能力需求自然非常急切。而决定三维模型的相似性是模型的识别，检索，但是如何建立一个这样的度量呢？如何找到可以表征模型的本息的属供了强大的技术积累。借鉴这些思想，总能从中举一反三，得到应用于三维模型的合适的方法。相关示例可见图1.1图 2D到3D的一些平推结随着科技的发展，33维数据的操控们均是该方向杰出的思想，可以给一些启发和指引。 采用统计的，通过获取物体/事物的统计信息作为该物体/事物的属性，借助于这些可以做很多应用。近年来，无论是人工智能，还是机器 在进入形状检索之前，先讨论相对成图像检索技术，并从图像检索技术中获取启发，可以发展出一系列平行于2D3D形状检索技术。上世纪70年代出现的早期图像检索技术是基于文本的检索方法（text-basedimageretrieval，这种方法是对每幅图像进行人工标注，从而将图像检索转换为快速膨胀，基于人工标注的耗时、昂贵；另一方面，人工标注具有歧义性，为后来检索应用的普及造成极大的不便。为了解决上述两个问题，90者又提出新的基于内容的图像检索（ContentBasedImageRetrieval,CBIR）方法，对于基于形状的图像检索过程，2D图像的基于特征的构造分为：特征提取Scale[1]]，MSER方法通过提取图像中最小变化区域来生成图进行分析。2008年，[2]也提出了选取图像中的128维的基于点周围图像梯度方向柱状图向量化方法，并拥有旋转不变的特改善了由[5]通过特征表示获取的向量表示子进行建立vocabulary。即便如此，仍然会有一些不变的情况，比如两篇文章中，“a”,”the”等词汇的频率很忽略的.Amores提出了基于空间关联的方法克服了这一问题。 文本描述子首推BagofWord(词袋法)，通过统计的得到文本的统计信 表 评价方Local3D模型检索大致可以分为三个类型：3D2D的图像检索有着极其类似的地方，似乎就是在对于2D图像形状检索的一个平推，但实际上的是非常之大的。在这个过程中，涌现出了很多杰出的思想.1.2是各类检索方法的分表 检索类图 形状检索的各类分支[9]LightFieldDescriptor模型间的相似性比较。最后一种通过计算模型每个点的Feature，将模型转化为FeatureBagOfFeature和Spatially-SensitiveBagOfFeature对于模型的相似性进行计算。参考了[10]和[11].第二章至第四章分别介绍SDD描述子，LFD描述子以及Shape描述第二 ShapeDistributionShape可以定义一个模型上的Shape函数，比如，随机一点和一固定点之间的D1D2A3.如果两个模型很相似，并且采样的数目足够大，对于shape函数做统计，他们的分布会尽可能的一致。（当然，这个过程是不可逆的，不能断言：即便一采样的数目足够大，他可以唯一对应一个模型。但是只要可以把相似的模型找出来，这个ShapeDistribution2.(AiBi)i=12随机点对的过程如下：事实上只要有产生一个随机点的过程即可。如果直接对于模型顶点随机选取，测试的结果证明这样选的并不好。这里采用A,B,C通过函数 (1 r1)A r1(1−r2)B r1r2013.scale不变性，将距离除去随机点对距离的最大值。对所得的距离做频率统计，统计的横坐标为区间段。得到了一组V维的向量SD，V是所分区间的个数。4.DA,B=||SDA− 图 几类对比结图 测试数据SD之间的对比以及模型之间的对比，SOCR.obj球体出现了八个点决定的正方体网格，因而出现了两个奇异的第三 LightFieldLightField2D表示3D2D图像检索技术的成熟性。然而由于无法直接建立一个好的旋转使得两个模型发生旋转重合。此时体每个顶点的投影图像。这就是LightFieldDescriptor的主要思想。，分别对模型A，B进行投影操作得到两组投影图像集合，其中图像的序号与投影点的序号。模型A，B之间的距离可以定义为：像距离会在后面提到。用数学语言表达如(5.1)式所示DA,B= ,k,IB,k),i=1, i 证明正十二面体的旋转对称变换可以分成以下几类：一是绕着六条对面|Sd(D)|60=|A5||Sd(D)|=60=|A5|,245-3-循环，152型置换1Sd(D 定N个观测角度(给十二面N个随机的旋转)，可以得到N×N个(A,B)的组合对，而其中在对角线上的N个组合对是相同的（A,B在世界坐标系下的位置不变，从相同方向对于物体进行观测投射到平面的结果也相同）(N(N1)1)种组合 断言可以和大程度上近球面，若采用N=10， 的角度误差，如(5.2)式所示x

×x

= 高，可以适当提高N的大小。nDA,B=minDA,B(Lj,Lk),j,k=1, 图 多视角组合结Pixel得到二维图像。图 投影示意图 FourierDescriptor(ContourShapeDescriptor).RegionShape描述子在意的是Shape的特征而忽略边界，ContourShapeDescriptor关注的是Shape的轮廓，而忽 FourierFourierSignatureFourier变换得到的。常用的shapesignature有complexcoordinate，curvaturefunction，cumulativeangularfunctioncentroidfunctionZhang2008centroidfunction比其记shape的边界坐标为(x(t)y(t))t=02..N1N√r(t) (x(t)−xc)2+(y(t)− xcyccentroidxc=N

ycr(t)Fourier

1N

1N1anN

,n=0,1,..N− 由于centrioddistance的平移不变性，可知道an具有平移不变性。为了使得 )f=(|a1|,|a1|,|a2| )

|a0| 的Fourier算子shape而言，在文章（ZhangandLu@AnIntegratedApproachtoShapeBasedImageRetrieval）60FourierDescriptor已经可以充分代表这个模型了。因而采用12面体已经足够精细。ZernikeVnm(ρ,θ)= m<=n

(ρ)

(n− (n− 对于一张图像函数f(x, 在做投影的时候是放在单位球中投影的，n+1∫

f(x,y)[Vnm(x, πxπ f(r,θ)≈N∑Zn,mVn,m(r, n=0图 Zernike重N取得越近的效果越好，下面一个例子:图(a)是原图，(b)(f)分别N=5，15，25，35，45Fourier现在有了F=(f1,f2,..fn)Z=z1,z2,..zm，只需要取联合的描述子d=(αf1,αf2,αfn,βz1,βz2,...βzm),α,β的大小可以适当改善结果。具体可以参考Zhang2008最后两张图像的相似性可以用下列式子来衡量dIA,IB=||dA−Mini图 小数据库示是对于一组6个模型的实验结果,见图3.6从结果来看，LFD对于模型的相似度识别十分准确，实验的结果十分符合图 数据库的缩略图 基于LFD的实现的一些检索结图 检索程序示意注：基于QT平台实现的三维模型检索程序，提供了一些基本的读文件， 图 结果展时间在5s左右第四 ShapeDistributionDescriptorShapeFunction同时,ShapeDisctributionLFD都是global的方法。很难对于一个模型局部性变换鲁棒。原文可以参考[10]和[11]以及[13].Shape-是较早将Lace—Beltrami算子作为模型的不变量，HKS的思想或多或少受到了Shape 启发，因而可以事先查看有关Shape 的相关工作[14]

∆U= 熟悉的Rn空间，热传导方程的基本解有如下形式n/2n/2

Φ(x,t)

4t (x∈Rn,t>

(x∈Rn,t<∆MU= f(x)为t=0时刻热量在流形上的分布，Ht(f为t时刻热量的分布。此时Ht称为热算子。不难证明Ht和∆M存在以下的关系Ht= 证明Ht(fii∑H(f)t

ii∆H(f)=∑ ii∂Ht(f)=∑ Ht(f)=∂Ht(f

)∂Kt(x,y)=∆K(tx,y),∀t>0,x,y∈ limδx(y)x, ∂Kt(x,y)=∆K(x,y),∀t>0,x,y∈ δx(yDirac1(x=δx(y)0(x̸=

Kt(x,y)

Mϕ= ∂Mϕn不难证明∆−1为且自伴算子，由定理：Hibert- idt定理可0<λ1<λ2<λ3<...,λnlim

较好的鲁棒性。然而Kt(x,y)需要的空间巨大，不适宜对一般大量的模型的定理 当Lace—BeltramiOperators的特征值不重复出现时，有T: ↕ kM(x,y)=kN(T(x),T(y))∀x,y∈M,t> ↕ kM(x,x)=kN(T(x),T(x))∀x∈M,t> 这里定义热核签名：HKSt(x)=Kt(x,HKSHeatkernelHKS需要的数据量却从二维下降到了一维，从O(n2)降到了O(n).HKSt(x,x)的物理意义转化成了，在点x给定单位热量，经过时间t的该点散发的热量。图 模型的HKS可视HKS的值明显越大，同时也可以作为模型的特征点。（∆U=∂U联系起来，热传导方程的右边表示的即是热量的速度，左边的Lace算子可以可以离散为该点和周围点的平均HKS的值第一组狼的模型由于是保距离的非刚性变换，HKS的值得分布几乎趋于HKS和其他两组BagofHKS(x,x)T*1维的向量。基可以把所有点的HKS联系起来，就可以得到整个模型的形状了。文本匹配的典型方法是BagofWords，也就是 Bagof对于模型，现在对于每个模型的每个点有了一个THKS，不p(x)T为时间段的数量，可以类比成文本中的“单词”。对于所有的”单词表”p1p2p3...pV。此时再统计每个模型在“单词表”上出现的全相同出现的概率几乎为0.因而简单的统计出现的频数是没有意义的。这里22θi(x)= ,i=1,2,3, 记θ(x)=(θ1(x),θ2(x),θ3(x),..θV(x))，参数c(x)使得||θ(x)||=1.根据θi(x) 不难观察出p(x)与pi(x)越接近，那么θi(x)的值越大。换言之，们可以这么认为，θi(x)即为点x的HKS属于第i类的概率。||θ(x)||=1是为了使得让x点处的HKS在“单词表”上出现的概率之和为1.如果 使得σ对于一个顶点数目为n的模型X每个点“单词表”上的出现的概率值i，此f(X)

n

f(X)为一个V*1维的向量，他的第i个分量”单词表“上的第i个单词在模 通过定义f(X)上的度量，即可确定模

dBoF(X,Y)=||f(X)−f(Y 采用了两组非刚性变换的模型进行了一些测试，测试模型为图4.2,图 测试模注：a,b,c为一组-非刚性变换的海马系列；d,e,f为一组-Spatially-SensitiveBagofSpatially-SensitiveBagofVVF(X)F(i,j)图 海马系列的BoF结图 狼狼系列的BoF结 果，这里使用的模型和上述一致（海马和狼系列4.5BoF&SS-图 SS-BoF的结cSDD，LFD而言，优点在于计算迅速，对于scale，旋转，平移都具有SDD缺点在于过于粗糙，对于不同物体很难做出细致的区分。对LFDretrieval的方法中应用最广也是最为鲁棒的。但是两种方法的的缺点在于对于非刚性变换束手无策。基于HKS的Shape方法HKS的过程涉及到大型矩阵的分解，因而是速度上仍然有所欠缺。同时对于非刚性变换的物体，不能简单通过将模型两点间的最大第五 了方法之间的优劣性。SDD是对于快速分类具有较快的速度，LFD对于刚性变SDD方法的理论基础不够完善，无法准确的给出相应的证明：两个模LFDFourier算联合Zernikemoment，基于HKS的Shape方法虽然对于旋转，非刚性，平移等具有鲁棒性，但却没有scale不变性。最近有学者Bronstein提出了scale不变的HKS方法，后LoweDG.Disttiveimagefeaturesfromscale-invariantkeypoints[J].Interna-tionalJournalofComputerVision.2004,60(60):91–110.TolaE,LepetitV,FuaP.Afastlocaldescriptorfordensematching[M].[S.l.]:[s.n.],2010:1-8.byHBay,TuyaarsT,GoolL.Surf:Speededuprobustfeatures.1:404–417[C].Proc.ofECCV.[S.l.],2013.ChumO,PhilbinJ,SivicJ,etal.Totalrecall:Automaticqueryexpansionwithagenerativefeaturemodelforobjectretrieval[C].IEEEInternationalConferenceonComputerVision.[S.l.],2007:1-8.BrownM,LoweDG.Automaticpanoramicimagestitchingusinginvariantfea-tures[J].InternationalJournalofComputerVision.2007,74(1):59–73.TangelderJWH,VeltkampRC.Asurveyofcontentbased3dshaperetrievalmethods[C].ProceedingsoftheShapeModelingInternational2004.[S.l.],2010:ZhangH,VanKaickO,DyerR.Spectralmeshprocessing[C].InternationalCon-ferenceonComputerGraphicsandInctiveTechniques,SIGGRAPHASIA2009,Yokohama,Japan,December16-19,2009,CoursesProceedings.[S.l.],2009:1865-OsadaR,FunkhouserT,ChazelleB,etal.Shapedistributions[J].AcmTransac-tionsonGraphics.2002,21(4):807–832.ChenD,TianX,ShenY,etal.Onvisualsimilaritybased3dmodelretrieval[C].ComputerGraphicsForum.[S.l.],2003:223-232.OvsjanikovM,BronsteinAM,GuibasLJ,etal.Shape:acomputervi-sionapproachtoinvariantshaperetrieval[C].IEEEInternationalConferenceonComputerVisionWorkshops.[S.l.],2009:320-327.SunJ,OvsjanikovM,GuibasL.Aconciseandprovablyinformativemulti-scalesignaturebasedonheatdiffusion[M]:volume28.[S.l.]:[s.n.],2009:1383–1392.TeagueMR.Imageysisviathegeneraltheoryofmoments*[J].JournaloftheOpticalSocietyofAmerica.1980,69(8):920–930.BronsteinAM,BronsteinMM,GuibasLJ,etal.Shape:Geometricwordsandexpressionsforinvariantshaperetrieval[J].AcmTransactionsonGraphics.2011,30(1):623–636.ReuterM,WolterFE,PeineckeN.Lace–beltramispectraas‘shape-’ofsurfacesandsolids[J].CompuidedDesign.2006,38(4):342–366.BelkinM,SunJ,WangY.Discreaceoperatoronmeshedsurfaces[C].ACMSymposiumonComputationalGeometry,CollegePark,Md,Usa,June.[S.l.],2008:278-287.LoweDG.Disttiveimagefeaturesfromscale-invariantkeypoints[J].Interna-tionalJournalofComputerVision.2004,60(60):91–110.TolaE,LepetitV,FuaP.Afastlocaldescriptorfordensematching[M].[S.l.]:[s.n.],2010:1-8.byHBay,TuyaarsT,GoolL.Surf:Speededuprobustfeatures.1:404–417[C].Proc.ofECCV.[S.l.],2013.ChumO,PhilbinJ,SivicJ,etal.Totalrecall:Automaticqueryexpansionwithagenerativefeaturemodelforobjectretrieval[C].IEEEInternationalConferenceonComputerVision.[S.l.],2007:1-8.BrownM,LoweDG.Automaticpanoramicimagestitchingusinginvariantfea-tures[J].InternationalJournalofComputerVision.2007,74(1):59–73.TangelderJWH,VeltkampRC.Asurveyofcontentbased3dshaperetrievalmethods[C].ProceedingsoftheShapeModelingInternational2004.[S.l.],2010:ZhangH,VanKaickO,DyerR.