学报社科类稿件投稿模板

更新时间:2023-12-30 作者:用户投稿原创标记本站原创 点赞:5509 浏览:20252

3DModelRetrievalMethodBasedonAffinityPropagationClustering

(题目中实词首字母大写,四号粗体)

LinLin*,XiaolongXie,andFangyuChen

(名前姓后,两个名字之间用连字符连接,小四号斜体)

(SchoolofMechatronicsEngineering,HarbinInstituteofTechnology,Harbin150001,China)

(单位采用小单位前,大单位后,若有多个单位需要编号,作者姓名右上角加上相应的编号,六号正体)

Abstract:Inordertoimprovetheaccuracyandefficiencyof3Dmodelretrieval,themethodbasedonaffinitypropagationclusteringalgorithmisproposed.Firstly,projectionray-basedmethodisproposedtoimprovethefeatureextractionefficiencyof3Dmodels.Basedontherelationshipbetweenmodelanditsprojection,theintersectionin3Dspaceistranormedintointersectionin2Dspace,whichreducesthenumberofintersectionandimprovestheefficiencyoftheextractionalgorithm.Infeatureextraction,multi-layersphereethodisanalyzed.Thetwo-layersphereethodmakesthefeaturevectormoreaccurateandimprovesretrievalprecision.Secondly,Semi-supervisedAffinityPropagation(S-AP)clusteringisutilizedbecauseitcanbeappliedtodifferentclusterstructures.TheS-APalgorithmisadoptedtofindthecentermodelsandthenthecentermodelcollectionisbuilt.Duringretrievalprocess,thecollectionisutilizedtoclassifythequerymodelintocorrespondingmodelbaseandthenthemostsimilarmodelisretrievedinthemodelbase.Finally,75samplemodelromPrincetonlibraryareselectedtodotheexperimentandthen36modelsareusedforretrievaltest.Theresultsvalidatethattheproposedmethodoutperformstheoriginalmethodandtheretrievalprecisionandrecallratiosareimprovedeffectively.

(摘 要四要素:目的,过程和方法,结果,结论,小五号)

Keywords:featureextraction,projectray-basedmethod,affinitypropagationclustering,3Dmodelretrieval

(关 键 词3~8个,小五号)

CLCNumber:TP391.7(中图分类号必须有,小五号)

Introduction(一级标题从引言部分开始编号,以下以此类推,四号粗体)

WiththedevelopmentandwideapplicationofCAD/CAMtechnology,thenumberof3Dmodelsgrowsgreatly.Howtoretrievethedesired3Dmodelfromthemasodelbaseefficientlyandtousethemforre-designbeesanurgentdemand.Whendesigning3Dmodelforanewproduct,thedesignersoftenneedtoretrievesimilarmodelsandrevisethemandthiswillimprovethedesignefficiency.Ifthenumberof3Dmodelisall,itiseasytofindthesuitable3Dmodel,butifthenumberof3Dmodelsislarge,itisdifficulttofindthedesiredmodelonlybythedesigner'emoryinashorttime.Sotheputerisrequiredtospeedupthedesignprocess.Inaddition,inotherareaswhichneedtoprocessalargenumberof3Dgeometryinformation,3Dretrievaltechnologyalsohasthewideapplication.

Featureextractionof3Dmodelisthemostimportantpartofretrievaltechnology.Featureextractionisextractingthecharacteristicdescriptorromthe3Dmodelandformingafeaturevector,whichcanbeutilizedtodistinguish3Dmodels.Thesimilaritybetweentwomodelscanbecalculatedbasedonthefeaturevectors,andthenthemostsimilar3Dmodelisretrievedfromthemodelbases.Thealgorithmsof3Dmodelfeatureextractioncanbedividedintothefollowingcategories[1-3]:thealgorithmsbasedonthegeometricinformation,thealgorithmsbasedonthesummomentofthespatialandfrequencydomainandthealgorithmsbasedontopologicalrelationships.Theray-basedmethod[4]belongingtothegeometryinformationmethodhasbeenwidelyusedandmanyfeatureextractionalgorithmsarederivedfromit.However,duetothelowefficiencyofthealgorithmanditsapplicationlimitationsonthesomeissues,itshouldbeimprovedinpractice.Inordertoimprovetheefficiencyofray-basedmethod,theprojectionray-basedmethodisproposedinthispaper,whichreducestheintersectioncalculationoftriangularfacetsandrays.

Theprocessof3Dmodelretrievaliscalculatingandparingthesimilaritybetweenthefeaturevectorsof3Dmodels.Supposingthereareafeaturevectorspaceandtwofeaturevectorsand,thesimilaritycanbecalculatedbyusingthefollowingmethods:

1)statisticaldistance:

(1)

Minkowski-formdistance():

(2)

If,theabsolutedistanceis:

(3)

If,theEuclideandistanceis:

(4)

Accordingtotheaboveexpressions,thelarge-scalemodelbaseandhighdimensionoffeaturevectorwillleadtoahighputationalplexityof3Dretrieval.Inordertolimittheretrievalscopeandimprovetheefficiency,theclusteralgorithmisappliedinthepapertofindtherepresentativemodelromthemodelbaseandtheyareusedtoclassifythequerymodelintothecorrectcluster.Thentheretrievalisexecutedonlyincluster,soitcanimprovetheefficiency.

K-meansclustering[5-6]isthemostwidelyappliedmethod,anditcandealwithlarge-scaledatawithfastiterationspeed.ButK-meansalgorithmissensitivetoinitialclustercentersandeasytofallintothelocalminimum.Thereforeitisrequiredtorunmanytimeswiththedifferentinitializationtofindthebestclusteringresults.However,thisstrategyiseffectiveonlywithaallnumberofclustersandthebetterinitialization.

Supportvectormachinetechnology[7](SVM)haswideapplicationinthefieldofdataclassificationanditoverestheproblemsofhighdimensionandlocalminimum.However,SVMisasupervisedlearningalgorithmandalarge-scalequadraticprogramming.Astoamulti-classificationproblem,althoughvarioussolutionsareproposed,thelargeputationisnotsolved.

Therecentproposedaffinitypropagationclustering(AP)algorithm[8-11]andK-meansalgorithmbothbelongtotheKcentersclusteringmethod.However,itoverestheshortingsofK-meansanditdoesnotneedtoselecttheinitialclustercenters.APcontinuallysearcheortherightclustercenterduringtheiterativeprocess,andfinallymakesthefitnesunction(objectivefunction)ofclusteringmaximizes.Itoidstheproblemsofselectinginitialvaluesandithaastrunspeedonlarge-scaledata.Therefore,itisverysuitableforhighdimensionalandlarge-scaleclassificationissue.

Inthispaper,APisadoptedtoobtaintherepresentativemodelromeachmodelbase,andthenthequerymodelisdeterminedwhichthemostpossiblemodelbaseitbelongstobyparingwiththerepresentativemodels.Then,theabovesimilarityEqs.(1)-(4)areusedforthemostsimilarmodelretrievalfromthemodelbase.Itlimitstheretrievalscopeandimprovesretrievalspeedandaccuracy.

PrincipleandStepsofRay-BasedMethod(一级标题实词的首字母大写,四号粗体)

Thebasicideaoftheray-basedmethodisthat:thesamplingraysareemittedtosomedirectionromthecenterof3Dmodel.Iftheraysintersectthetriangularfacetswhichposethemodelsurface,themaximumdistancefromtheintersectionstothecenterisusedasafeatureof3Dmodel(asshowninFig.1.)

Fig.1Principleofray-basedmethod

(图和表格标题第一个单词首字母大写,小五粗体)

Thefeatureextractionprocessincludesthefollowingsteps:

1)Thepretreatmentofthe3Dmodel:themodel'scenteriovedtotheorigin,andthenthemodelisscaledtotheunitsize,andallthemodelsareputinthesamedirection,

2)Supposingthemodelissurroundedbytheunitballwhosecenteristheorigin,theraysareemittedarounduniformly,andthenthecoordinatesoftheintersectionpointarecalculated.

Aseriesofsamplingraysthroughtheorigininsphericalcoordinatescanbeexpressedas:

whereisthedirectionofray,isthelengthofray,andareshowninFig.2.

Fig.2Diagramofsphericalcoordinates

Thecoordinatesofapointonatriangularfacetcanbeexpressedas:

where,andaretheverticesofthetriangular.

If,theparametersu,vandtcanbecalculatedby:

If,thecorrespondingparametersandtaresed.

3)Takingthemaximumdistancefromtheintersectionstotheoriginasafeatureofthemodel,andthenextractingtheallfeaturevectorrom3Dmodel.

ProjectRay-BasedMethod

3.1ProjectRelationshipAnalysisofBall-SectionandTriangularFacets(二级标题实词首字母大写,四号粗体,若还有标题,第一个单词首字母大写,其他小写,五号斜体)

Therayswithafixedandvariousposeaballcross-section,andthentheballcross-sectionisprojectedtothesectionthroughtheoriginandperpendiculartotheballcross-section.Theprojectionisalinewhoseequationis:

Thelocationsoftheballcross-sectionandtriangularfacetsareshowninFig.3.

Fig.3Relationsofcross-sectionandtriangularfacets

Becausethemodelislimitedintheunitball,theintersectionoftheballcross-sectionandthetriangularfacetscanbejudgedaccordingtowhethertheprojectlineofballcross-sectionintersectstheprojectionsofthetriangularfacets.TherelationshipisshowninFig.4.

Fig.4Projectionrelationshipofballcross-sectionandtriangularfacets

Figs.3and4describethelocationrelationshipbetweentheballcross-sectionandthespatialtrianglefacetsandthecorrespondingprojectionrelationship.Accordingtotheaboveanalysis,thelocationrelationshipbetweenthelineandthetriangleinthesameplanecanbeusedtodeterminewhetherthetriangleintersectstheballsection.Thentwojudgmentmethodsare:

1)Themethodbasedondistance.Ifatleastonevertexoftriangleisonthelineorontheothersideoftheline,thetriangleintersectstheline.ThedistanceequationfromapointP(x,y)toalinethroughtheoriginis,wherethesignofax+bycanbeusedtodeterminethelocationrelationshipbetweenthepointsandlines.Thenbyusingtherelationshipsbetweenallthepointsoftriangleandtheline,whethertheballcross-sectionandintersectthetriangularfacetcanbedetermined.Forexample,P1andP2areendpointsofasideL1oftriangle,D1andD2arethedistanceromP1andP2toL2.If,L1intersectsL2,otherwise,theydonotintersect.ThelocationrelationshipisshowninFig.5.

Fig.5Locationrelationbetweentwolines

2)Methodbasedonintersectionangle.Astoatriangle,ifoneofthefollowingEq.(5)holds,itmeansthatthelineisthroughanysideofthetriangle,thenthelineandtriangleintersect.TheprocessisshowninFig.6.

(5)

whereistheanglebetweenthevectorsOAandOC,whichcanbegotbythecosineformula.

Fig.6Diagramofanglerelationship

3.2StepsofProjectRay-BasedAlgorithm

Animportantwaytoimprovetheefficiencyofray-basedmethodistoreducethenumberofunnecessaryintersection.Theideaisthat:1)gettingNplaneswithafixed,differentintheball,2)usingthemethodinSection3.1torecordthetriangularfacetsintersectingtheplanes.Becauseaplane(aballcross-section)includesaseriesofrays,iftriangularfacetsdonotintersecttheballcross-section,itdefinitelydoesnotintersecttheraysintheballcross-section.3)removingtherayswhichdonotintersectthetriangularfacets.Thestepsofprojectray-basedmethodareaollows:

Thegraticulevariableslandwareinitializedas0.

If,thecorrespondingiscalculated,andtheballcross-sectionwithangleisdeterminatewhetheritintersectstriangularfacets.Theintersectedtriangleacetsareputintothecollections..if,thealgorithmisend.

If,thecorrespondingiscalculated..if,itgoestostep2,

Iftheindexnumber(isthemaximumnumberoftriangularfacets),thecorrespondinariablesu,vandtarecalculatedbyusingthemethodproposedinSection2..if,andthealgorithmreturnstostep3.

Ifthevariablesu,vandtdonotmeettheintersectionconditionsThenisafeaturevectorof3Dmodel.

ThealgorithmflowisshowninFig.7.Thevariablesl,wandkrepresenttheindexnumbersofgraticuleandtriangularfacetswhileandrepresentthemaximumnumbersofgraticuleandtriangularfacets.Thevariabletisthedistancefromtheintersectiontooriginwhileisthemaximumdistance.

Fig.7Flowofprojectionray-basedalgorithm


Supposingthenumberofraysis,thenumberofthetriangularfacetsthatposethesurfaceofa3Dmodelis,theverticesnumberoftriangleacetsisandthefinalnumberofthetriangularfacetsneededtobecalculatedfortheintersectionis.

Becausetheputationofremovingtheno-intersectiontriangulariuchallerthanintersectioncalculationbetweentheraysandtrianglefacets,itcanbeignored.Theiterationtimesinray-basedmethodis,theiterationtimesintheimprovedprojectray-basedmethodis.Thus,theratioofputingworkis.Thelargermeansthatthemethodioreeffective.Thenumberofremovedno-intersectiontriangularfacetsisbymethodbasedondistanceandbymethodbasedonintersectionangle.Theputationofmethodbasedondistanceis,whichislessthanthatofmethodbasedonintersectionangle.FromEq.(5),itcanbeconcludedthatintersectionjudgmentbymethodbasedonintersectionangleioreplexitythanthatbymethodbasedondistance.Therefore,themethodbasedondistanceisbetter.

Theaboveapproachusessingle-layerspheretoextractfeatures.However,thisapproachignorestheinnerinformationofthemodel,soitisonlysuitableforconvexmodel.Inordertousetheinnerinformationofmodelswhentheapproachisutilizedindealingwithmodelswithothertopologicalstructures,multi-layerspheresapproachisproposed.Thestepsare:(i)limitingthemodelinaball,(ii)dividingtheballintoNlayerseragely,(iii)emittingtherayromcentertosamplingpointsoneachsphere,andcalculatingtheintersectionpointsofraysandthemodel.Ifthereisnosamplingpointbetweenthe(n-1)-thsphereandnthsphere,thenthissamplingpointiseliminatedasthefeaturesofnthlayer,where.

Nowtheexamplesarepresentedtovalidatetheeffectivenessoftheproposedapproach.Thesingle-layersphereisutilizedfirstly,andtheprojectray-basedalgorithmisutilizedtoextractfeatures.ThentheEuclideandistanceisutilizedtoparethesimilaritybetweenmodels,andtheresultsareusedtodrawthePrecision-Recalldiagramtoevaluatetheprecisionoftheretrieval.

ThePrecisionandRecallrepresenttheprecisionratioandrecallratiorespectively,andtheycanbeutilizedtoevaluatetheretrievalresults.Precisionratioistheratioofcorrectmodelsinallretrievedmodels,anditisutilizedtoevaluatetheprecisionofretrievedresults.Precisionratioiscalculatedasthenumberofcorrectmodelsdividedbythenumberofretrievedmodels.Recallratioistheratioofcorrectretrievedmodelsinallmodels,anditisutilizedtoevaluatetheabilitytoretrievethecorrectmodels.Recallratioiscalculatedasthenumberofcorrectretrievedmodelsdividedbythenumberofallmodels.SointhePrecision-Recalldiagram,thecurvewhichisclosertoupper-rigeanstheretrievedresultsarebetter.

Themodelsofbottleandboxareutilizedastestdata,andthenumberofraysis1,024.Intheexperiments,theresultsofdifferentmodelsaredifferent,asshowninFig.8.AccordingtotheresultsinFig.8,thepreciseofboxmodelsislowerthanthatofbottlemodels,andthereasonisthatthetopologicalstructureofboxmodelsioreplicatedthanthatofbottlemodels.Thereisplentyinnerinformationinboxmodels,sothesingle-layerspherecannotdescribethesemodelsaccurately.

Fig.8Resultsofbottleandboxmodels

Theresultsofboxmodelsarenotverygoodwhenusingsingle-layersphere,sotwo-layerspheresareused,andtheprecisionisimproved.TheresultsareshowninFig.9.

Fig.9Resultsofboxmodels

Accordingtotheexperiments,themulti-layerspheresprojectray-basedapproachcanextractthefeaturesofmodelswiththeplicatedtopologicalstructureeffectively.

TheGearmodels,LflangemodelsandSflangemodelsarealsotakenastestingmodels.Intheexperiments,theraynumbersaresetas1024,andthenthenumbersofspheresareincreasedfrom1to3.Theresultsshowthatretrievedprecisionoftwo-layersphereethodiuchbetterthanone-layerspheremethod,whiletheretrievedprecisionofthree-layersphereethodisonlylittlebetterthanone-layerspheremethod.Thus,thenumberofspheresshouldbesetareasonablevalue.Theexperimentalsoevaluatesthenumberofrays.Theraynumbersaresetas64,256and1024,andtheresultsshowthattheprecisionincreasesastheincreaseofraynumbers,whiletheimprovementisnotveryobvious.Thus,generally,theraynumberissetas1024,andthetwo-layerspheremethodisutilized.Inthisway,thefeaturevectorof3Dmodelscontainoreinformation.Ituseine-grainedfeaturestodescribe3Dmodels,soitioreaccurateanditcanimprovetheretrievalprecision.

AffinityPropagationClusteringMethod

Affinitypropagationclustering(AP)isanewclusteringalgorithmanditsrunspeediastevenformulti-classificationproblem.BeforetheiterationprocessofAP,thesimilaritymatrix:consistingofthesimilaritybetweendatapointsiedasinput.Thealgorithmfirsttakesallthedatapointsasthepotentialclustercentersandsupposesthattherearemessagesenergyandbetweenanytwodatapointsiandk.Theisvaluemessagesentfrompointtothecandidateclustercenterpoint,whichisusedtoevaluatewhetherthepointisofsuitabilityastheclustercenterforthepoint,isthevaluemessagesentfromcandidateclustercenterstopoint,whichisusedtoevaluatewhetherthepointisreadytoselectthepointastheclustercenters.Thestrongertheinformationenergyandare,themorepossiblethepointisastheclusteringcenter,whilethepointiorepossibletobelongtotheclasswiththecenterpoint.Theexpressionsofandareshowninthefollowingequations.

(6)

(7)

Inordertooidvibrationsduringtheiterationprocess,thedampingfactorisintroducedinthealgorithm,andthemessageenergyintheiterationis:

(8)

(9)

ThediagonalvaluesinSmatrixareusedastheevaluationcriteriaforapointbeingaclustercenter,whichiscalledthebiasparameter.Generally,themedianofallnon-diagonalelementsisadoptedasthevalueof.TheparameterisusedinEq.(10).

(10)

Alargerleadstolargerand,whichmeansthepointiorepossibletobethefinalclustercenter.Whenislarger,morepointstendtobethefinalclustercenters.Therefore,enlargingornotcanincreaseordecreaseclusternumbersproducedbyAP.

ThestepsofAPalgorithmareaollows:

(1)InitializingtheelementsofsimilaritymatrixS,attractionmatrixRandtheattributionmatrixAas0,andthedampingfactor,thenumberofiterations,themaintainnumberofclusterinformationCcount等于0.AssigningthemaximumiterationnumbertmaxandthemaximuminformationmaintainnumberCcountmaxandthemediansofallS-diagonalelementstop(k),

(2)Thenewattractionandnewattributions,initerationarecalculatedbyEqs.(6)to(7),

(3)Thefinalattractionandfinalattributions,initerationtarecalculatedbyEqs.(8)to(9),

(4)Findingtherepresentativepointsbytheequation,

(5)Repeatingsteps(2)-(4)untiltherepresentativepointskeepconsistentduringmanytimesiterationor.

AccordingtoAPalgorithm,itassumesthatalltheclustersinfeaturespacearepact.InAP,theenergyfunctionisthesumofsimilaritiesbetweensamplesandclustercenters,whichis.SupposingthatthenumberofclustersisJ,andAPminimizes.Thus,iftheclusterstructureispact,itiseasytoguaranteethateachisall,andthenisall,soAPcanachievegoodresultsinthiscondition.Butiftheclusterstructureisloose,thatistosay,theclustersarenotveryclear,APalgorithmtendstoproducemoreclusterstomakeeveryandminimize,soAPwouldproducetoomanyclusters,andtheresultsarenotaccurate.

InordertoimprovetheaccuracyofAPalgorithmandmakethealgorithmeffectivewhenthescaleofmodelsetchangesortheplexdegreeofmodelschanges,thesemi-supervisedAPclusteringalgorithm(S-AP)inRef.[12]isutilizedtocluster3Dmodels.

InS-APalgorithm,theclusteringcentersarealsodeterminedaccordingtoaller,buttheobjectivefunctionisnotminimizing,whileitusesvalidityindextosupervisetheclustering.TheSilhouetteindex[13]isusedasthevalidityindex.

Supposingthatistheeragedissimilarityordistancebetweensampletinclusterandalltheothersamplesinthiscluster,whileistheeragedissimilarityordistancebetweensampletandsamplesinanothercluster,and.ThentheSilhouetteindexofsampletis.

Theerageofvaluesofallthesamplesindatasetcanrepresentthequalityoftheclusteringresults.ThelargererageSilhouetteindexis,thebetterthequalityofclusteringis,sotheclusterresultsofthemaximumindexisthebestresultofclustering.InAP,thenumberofclustersincreasesanddecreaseswiththeincreaseanddecreaseofthevalueofp.InS-AP,theinitialvalueofpisthemedianofattractiondegree,anditsvaluedecreasesdynamicallytoobtainallernumberofclusters.Thenthemaximumanditsclusteringresultsareobtained.Theincrementofpis,whereistheminimumofattractiondegree.TheflowofS-APalgorithmisshowninFig.10.

Fig.10FlowofS-AP

APalgorithmisanunsupervisedmethod,butsearchingrepresentativemodelsasclustercentersin3Dmodelsisaclassificationproblemwhichisasupervisedproblem.InordertoenhancetheeffectivenessofAPalgorithm,thesimilaritymatrixSwhichisinputintothealgorithmiodified.

Inthisstudy,thesimilaritybetweentwosamplesinoneclustermultipliesaweighttoincreasetheinformationenergybetweensamplesinoneclusteranddecreasetheinformationenergybetweensamplesindifferentclusters.Thiodificationcanmaketheclustercentermodelmorerepresentativebecauseasamplemodelwhichisontheedgeoftwoclustersisnotlikelytobeaclustercenter.Supposingthatthesetofclustercentersis,andthenumberofmodelsinkthclusteris.Theputationalplexityis,whiletheputationalplexityoforiginalapproachis.

SimulationandResultAnalysis

Inordertoverifytheeffectivenessoftheproposedmethodproposed,6typesof3DmodelsareselectedfromthePrincetonlibrary[14].Theprojectionray-basedmethodisusedtogetthe256featurevectorsbyemitting1616rays,wherearetheindexnumberofgraticuleandisthemaximumdistancefromtheintersectionstoorigin.The3Dmodelsincludebottle,flange,gear,gun,helicopterandhumanbodymodel.ThepartsofthesamplemodelsareshowninFig.11.

Fig.11Partsofthesamplemodels

First,APalgorithmisadoptedtoclassifythe78modelsin6modelbasesinordertofindthecentermodelsofeachbasewhicharerepresentativeanddistinctive.ThetestenvironmentisWindowsXP.MATLAB7.1Softwareisusedforsimulation.Theclusteringerroriscalculatedaollows:

(11)

whereisthecentermodelsofclassK(thereareseveralcentermodels),istheclusterK.

TheclusteringresultsareshowninTable2.

Table2Clusteringresults

ModelBottleFlangeGearGunHelicopterHumanbodyError(%)0022.037.538.95.0Theclusteringerrorsofgunandhelicoptermodelsarelarger.Thereasonisthatthegunandhelicoptermodelshealotofdetailedcharacteristic.Aentionedabove,araymayintersectseveralfacets,butonlythemaximumdistancefromtheintersectionstooriginisadoptedasthefeaturevector.Sothefeaturesextractedfromgunandhelicoptermodelscannotdescribethemodelsexactly.However,fortheconvexmodels,suchasthehumanbody,flangeandbottlemodels,theclusteringresultsarebetter.Thereforetheray-basedmethodsarenotsuitableforthe3Dmodelswithmoredetailcharacteristics.Theextractionmethodwithhigherprecisioncanbeusedinthissituation:suchasweletmoments[15],3DZernikmoments[16],Fourieranalysis[17],andsphericalharmonicanalysiethod[18-20]andother3Dmodelfeatureextractionmethods.

(1)Theanalysisofputationplexity.First,theEuclideandistancebetweentheretrievedmodelandthecentermodelsisutilizedtojudgewhichmodelbaseitmaybelongto.

,

Then,theretrievalalgorithmsearchesinthecorrespondingmodelbaseforthemostsimilar3Dmodel.Thetotalputationalplexityis:

whereisthemodelsinclusterK

However,ifretrievalfromallofthemodelbasesbytheoriginalmethod,thecalculationis.Dueto,therefore,thecalculationofthemethodiuchallerthanthatoforiginalmethod.

(2)Theanalysisofprecision.39bottle,bodyandflangemodelsareselectedfrom75sampleortesting.AfterclusteringbyEq.(11),theclusteringerroris0.Thieansthattheall39modelsareclassifiedtothecorrectmodelbase.Themostsimilarmodelandtheentiresimilarmodelswillberetrievedfromthecorrectmodelbase.Thereforetherecallandprecisionratesare100%.Ontheotherhand,the3Dretrievalsystemdevelopedbythepaperisusedtoretrievethesimilarmodelfromallthemodelbases.Withthe256featurevectorsextractedbytheprojectray-basedmethod,theretrievalprocessofthe3bottle,3humanbodyand3flangemodelsaredone(asshowninFigs.11-13).Theretrievalresultsarelistedindescendingorderofthesimilarity,andthefirst10retrievedmodelsaretakentocalculatetheprecisionratewhichisshowninTable3.

Fig.12InterfaceofbottleretrievalFig.13Interfaceofflangeretrieval

Fig.14Interfaceofhumanbodyretrieval

Table3Resultsofmodelretrieval

ModelBottleFlangeHumanbodyNamePrecision(%)NamePrecision(%)NamePrecision(%)Model1M48230Gb9113_120Humanm21960Model2M48330Gb9113_2100Humanm22160Model3M48460Gb9113_390Humanm23760

FromTable3,theretrievalprecisionsof3typesofmodelsarelow.Thereasonsarethatleseaturevectorsareextracted,andmoreover,thelimitationofray-basedmethoditself.Itisinaccuratethatonlythemaximumdistanceisextractedasthefeaturevectorfor3Dmodel.However,eveninthecaseoffewerfeatures,themethodproposedbythepapercanachievethehigherretrievalprecision,whichshowsthatthemethodisofthepracticabilityandeffectiveness.

Conclusions

Theprojectray-basedmethodwhichreducestheputationalplexityandimprovestheextractionefficiencyisproposedforfeatureextractionof3Dmodelsinthispaper.Infeatureextraction,multi-layersphereethodisproposedandthechoiceofraynumberandspherenumberarediscussed.Thetwo-layersphereethodisutilizedanditcanmakethefeaturevectormoreaccurateandimproveretrievalprecision.Semi-supervisedAffinityPropagation(S-AP)Clusteringisutilizedbecauseitcanbeappliedtodifferentclusterstructures.S-APalgorithmisadoptedtoclusterandfindthecentermodelswhichcanrepresentthemodellibrary.Thequerymodeliirstlyclassifiedtocorrespondingmodelbase,andthen,themostsimilarmodelisretrievedinthemodelbase.TheS-APclusteringalgorithmisefficientanditsclusteringresultsaremoreaccurate.Infeatureextraction,themulti-layersphereethodcanextractaccuratefeaturesevenforplicated3Dmodels,andinmodelretrieval,theapplicationofS-APimprovestheretrievalefficiency.

References(格式要求见文档最后)

[1]CuiChenyang,ShiJiaoying.Analysisoffeatureextractionin3Dmodelretrieval.JournalofComputer-aidedDesign&,ComputerGraphics,2004,16(7):882-889(inChinese)

[2]YangYubin,LinHui,ZhuQing.Content-based3Dmodelretrieval:asurvey.ChineseJournalofComputers,2004,27(10):1297-1310.(inChinese)

[3]ZhengBochuan,PengWei.Asurveyon3Dmodelretrievaltechniques.JournalofComputer-aidedDesign&,ComputerGraphics,2004,16(7):873-881.(inChinese)

[4]VranicDV,SaupeD.3Dmodelretrieval.ProceedingsofSpringConferenceonComputerGraphics.Budmerice,Slovakia,2000.89-93.

[5]ChangChihtang,LaiJimZC,JengMuder.AfuzzyK-meansclusteringlgorithmusingclustercenterdisplacement.JournalofInformationScienceandEngineering,2016,27(3):995-1009.

[6]AhmadAmir,DeyLipika.Ak-meanstypeclusteringalgorithmforsubspaceclusteringofmixednumericandcategoricaldatasets.PatternRecognition,2016,32(7):1062-1069.

[7]CortesC,VapnikV.Support-vectorworks.MachineLearning,1995,20(3):273-297.

[8]FreyBJ,DueekD.Clusteringbypassingmessagesbetweendatapoints.Science,2007,315(5814):972-976.

[9]GuanRenchu,ShiXiaohu,MarcheseMaurizio.Textclusteringwithseedsaffinitypropagation.IEEETransactionsonKnowledgeandDataEngineering,2016,23(4):627-637.

[10]GuoKun,ZhangQishan.Affinitypropagationclusteringbasedongreyrelationalanalysis,JournalofGreySystem,2016,22(2):147-156.

[11]KellyK.Affinityprogramslashesputingtimes.news.utoronto.ca/bin6/070215-2952.asp,2007-10-25.

[12]WangKaijun,LiJian,ZhangJunying,etal.Semi-supervisedaffinitypropagationclustering.ComputerEngineering.2007,33(23):197-201.(inChinese)

[13]DudoitS,FridlyandJ.Aprediction-basedresamplingmethodforestimatingthenumberofclustersinadataset.GenomeBiology,2002,3(7):0036.1-0036.21

[14]DobkinD.Princetonshaperetrievalandanalysisgroup.shape.cs.princeton.edu/search..2001-11.

[15]CuiLi.ThetheoriesofN-Dgeneralizedquasi-realwelets&,weletmomentsandtheirapplications.JilinUniversityDoctorThesis,2004.33-86.

[16]NovitniM,KleinR.3DZernikdescriptororcontentbasedshapedretrieval.ProceedingsOfACMSymposiumonSolidModelingandApplications.Washington,DC.2003.216-225.

[17]OsadaR,FunkhouserT,ChazelleB,etal.Shapedistributions.ACMTransactiononGraphics,2002,21(4):807-823.

[18]VranicDV,SaupeD.3Dmodelretrievalwithsphericalharmonicsandmoments.ProceedingsoftheDAGM2001.Munich.2001.392-397.

[19]VranicDV,SaupeD,RichterJ.Toolor3D-objectretrieval:Karhuner-Loevetranormandsphericalharmonics.ProceedingsofIEEEWorkshoponMultimediaSignalProcessing.Cannes.2001.293-296.

[20]VranicDV,SaupeD.Animprovementofrotationinvariant3D-shapedescriptor.ProceedingsoftheIEEEInternationalConferenceonImageProcessing.Barcelona.2003.757-760.