A novel 3D mesh compression using mesh segmentation with multiple principal plane analysis

PatternRecognition43(2010)267--

279

ContentslistsavailableatScienceDirect

PatternRecognition

journalhomepage:/locate/p

r

Anovel3Dmeshcompressionusingmeshsegmentationwithmultipleprincipalplaneanalysis

Shyi-ChyiChenga, ,Chen-TsungKuob,c,Da-ChunWub

a

DepartmentofComputerScienceandEngineering,NationalTaiwanOceanUniversity,2Pei-NingRoad,Keelung202,Taiwan

InstituteofEngineeringScienceandTechnology,NationalKaohsiungFirstUniversityofScienceandTechnology,1UniversityRoad,Yenchao,Kaohsiung824,Taiwanc

DepartmentofInformationManagement,LongcyuanVeteransHospital,VAC,ExecutiveYuan,1AnpingLane1JhaoshengRoad,Pingtung912,Taiwan

b

ARTICLEINFOABSTRACT

Articlehistory:

Received24July2007

Receivedinrevisedform20May2009Accepted26May2009Keywords:3DmeshCompressionSegmentation

Principleplaneanalysisk-meansclustering

Thispaperproposesanovelschemefor3Dmodelcompressionbasedonmeshsegmentationusingmul-tipleprincipalplaneanalysis.Thisalgorithmfirstperformsameshsegmentationscheme,basedonfusionofthewell-knownk-meansclusteringandtheproposedprincipalplaneanalysistoseparatetheinput3Dmeshintoasetofdisjointedpolygonalregions.Theboundaryindexingschemeforthewholeobjectiscreatedbyassemblinglocalregions.Finally,thecurrentworkproposesatriangletraversalschemetoencodetheconnectivityandgeometryinformationsimultaneouslyforeverypatchundertheguidanceoftheboundaryindexingscheme.Simulationresultsdemonstratethattheproposedalgorithmobtainsgoodperformanceintermsofcompressionrateandreconstructionquality.

©2009ElsevierLtd.Allrightsreserved.

1.Introduction

Inrecentyears,three-dimensional(3D)meshmodelshavebeenwidelyusedingeographicaldatabases,manufacturingassemblies,virtualrealityforentertainmentapplications,orotherinteractiveapplications.Thesemodelsareoftenrepresentedascomplextrian-gularmeshes,whichmayhavethousandsorevenmillionsofver-ticesandpolygons.Alloftheseapplicationsrequirelargestorage,computerpowerandaccessoverbandwidth-limitedlinks.Thus,itisessentialtocompressthe3Dmodelsefficiently.SinceDeering[1]firstintroducedtheconceptofgeneralizedtriangularmeshcompres-sion,manyalgorithmscategorizedaslosslessorlossy,single-rateorprogressive,andsingleresolutionormulti-resolution,havebeenproposedtocompress3Dmeshes[1–18].Agoodreviewon3Dmeshcompressiontechnologycanbefoundin[12,13].

Comparedwiththelossy3Dmeshcoding,alosslesstechniquere-constructsmeshdataidenticaltotheoriginal.Manyapplicationsuselosslessdatacompression,suchasinexecutablecode,wordprocess-ingfiles,etc.Tocomparesingle-ratecodingwithprogressivecoding,single-ratecodingfocusesonsavingthebandwidthbetweenCPUandthegraphiccard;however,progressivecompressionof3Dmeshesprovidesmultipleresolutionsfortransmittingcomplexmeshesovernetworkswithlimitedbandwidth.Earlyresearchconducted

Correspondingauthor.

E-mailaddresses:csc@mail.ntou.edu.tw(S.-C.Cheng),dcwu@ccms.nkfust.edu.tw(C.-T.Kuo),jmskuo@mail.vhlc.gov.tw(D.-C.Wu).

0031-3203/$-seefrontmatter©2009ElsevierLtd.Allrightsreserved.doi:10.1016/j.patcog.2009.05.016

single-ratecodingon3Dmeshcompression.Chow[2]presentedanalgorithmtoefficientlyproducegeneralizedtrianglemeshes.HismeshifyingalgorithmsandvariablecompressionmethodachievedcompressionratioshigherthanDeering'smethod[1].Toumaetal.[3]proposedthevalence-drivenapproachthatrecordsthedegreeofeachvertexalongaspiralingvertextree.Progressivemeshcom-pressionhasbeenalsointensivelyresearched,sinceitenablesthedecodertoreconstruct3Dmodelscontinuouslyfromcoarsetofinelevels-of-details(LODs)[4–8].TheEdgebreakermethodproposedbyRossignac[9]canhandlemanifoldmesheswithmultipleboundaryloopsandhandles.Gumholdetal.[10]improvedthisconnectivityupperboundto3.522bpv.

Trianglemeshcompressionhasbeenthefocusofmuchstudy.Thisrepresentationcontainstwokindsofinformation:geometryandconnectivity.Geometrycodingdescribesvertexcoordinatesinthe3Dspace,andconnectivitycodingdescribeshowtoconnecttheseposi-tions.Theconnectivitycompressionproblemhasbeenwellstudied,withmanyexistingmethods[12,13]achievingbit-ratesoflessthantwobitspertrianglefortheconnectivityportionofamesh[11].Lessefforthasgoneintogeometrycompression,oftensimplyperformedbypredictioncodingandquantization[14].Recently,researchershaveproposedothergeometrycompressiontechniques,includingwavelettransform[15],spectralcompression[16],andk–dtreeoroctreedecomposition[17].Althoughtheperformanceofthese3Dmeshcompressiontechniquesachievingbit-ratesbetween1and2bytespervertexisgood,theoutputbitstreamremainslargeforcomplexobjectswithhighnumbersofverticesandtriangles.Thus,developingeffectivecompressiontechniquesforthevertexdatato

268S.-C.Chengetal./PatternRecognition43(2010)267--279

transmit3Dmeshmodelsinabandwidth-limitednetworkisimpor-tant.Simetal.[18]proposedanalgorithmtoencodeconnectivitydataandgeometrydatausingatrianglefanstructure.Mostprevi-ousworkstypicallydiscussconnectivitycompressionandgeometrycompressionissuesindividually.Thisworkproposesasegmentation-based3Dmeshcompressionmethodthatsimultaneouslyconsidersconnectivityandgeometrycompressionproblems.

Meshsegmentationisthefirststeptowardsregion-based3Dmeshcompression[19].Segmentationismorecommonintheimageprocessingarea,andhasbeenrecentlyintroducedintothe3Dmesharea[20–25].Amongexistingalgorithms,thewatershed-basedap-proachhasreceivedmoreattention.Thisapproachusesdiscretecurvatureateachmeshvertexastheheightfieldthatdriveswa-tershedsegmentation.Thecurvatureestimationfor3Dmeshesiscomputationallyexpensive[20–22],asitismathematicallydefinedforasmoothsurfaceonly.Featuresensitivemeshsegmentationthatmaintainssalientfeaturesisimportantformanycomputergraphicsandgeometricmodelingapplications[23].Chengetal.[24]proposedapatch-growingapproachusingashortest-pathlabelingtechniquetosegmentthemodelintomultipleregions.Zhang[25]proposedasimplesegmentationalgorithmusingGaussiancurva-tureanalysis,efficientforcertain3Dmodels.However,similartootherexistingmethods,thisalgorithmisdefectivewhenprocessingahigh-resolution3Dmodel,asthegeometriccharacteristicsofad-jacentpolygonsinsuchamodelaretooclosetobedifferentiated.Therefore,anefficientandrobustalgorithmisneededfor3Dmeshsegmentation.

Thecurrentworkproposesanefficientsegmentation-based3Dmeshcompressionsystem,whichprovidesprogressivetransmissionfor3Dmodelsoverabandwidth-limitednetwork.Thisalgorithmfirstperformsameshsegmentationscheme,basedonfusionofthewell-knownk-meansclusteringandtheproposedmultipleprinci-palplaneanalysistoseparatetheinput3Dmeshintoasetofdis-jointedpolygonalregions.Theboundaryindexingschemeforthewholeobjectiscreatedbyassemblinglocalregions.Finally,apro-posedtriangletraversalschemeencodesconnectivityandgeome-tryinformationsimultaneouslyforeveryregionundertheguidanceofboundaryindexing.Atthedecoder,basedonboundaryindexing,thisworkobtainseachindividualregionandreconstructsthewholeobjectusingconnectivityandgeometrycodinginformation.Simula-tionresultsdemonstratethattheproposedalgorithmobtainsgoodcompressionperformance.

Theremainderofthispaperisorganizedasfollows.Section2presentsthemethodtoseparatetheinputtrianglemeshintomul-tipleuniformregionsusingak-meansclusteringwiththeprincipalplaneanalysistechnique.Thecurrentapproachto3DmeshmodelcompressionisdescribedindetailinSection3.Section4presentsexperimentalresultsobtainedfromapplyingtheproposedmethodtotest3Dmodels.Section5outlinesabriefconclusion.2.Clustering-based3Dmeshsegmentation

Thissectionpresentsaclustering-based3Dmeshsegmentationmethodbasedonk-meansclustering[25–27]withtheproposedprincipalplaneanalysis[28].Toclearlyintroducetheproposedseg-mentationscheme,thek-meansmethodandprincipalplaneanalysisarefirstdescribed.2.1.k-meansclustering

In1967,MacQueenproposedthek-means[26]algorithmasoneofthesimplestunregulatedlearningalgorithmstosolvetheclus-teringproblem.Theprocedurefollowsasimpleandeasymethodtoclassifyagivendatasetintokofgroups.Themainideaistodefinekcentroids,oneforeachgroup.Thesecentroidsshouldbeproperly

placedbecausedifferentlocationscausedifferentresults.Choosingthemasfarawayaspossiblefromeachotheristhebetterchoice.Thenextsteptakeseachpointbelongingtoagivendatasetandassociatesittothenearestcentroid.Whennopointispending,thefirststepisaccomplishedwithanearlygrouping.Atthisstage,knewcentroidsofgroupsresultingfromthepreviousstepneedre-calculating.Afterobtainingknewcentroids,anewbindingmusttakeplacebetweenapointinthesamedatasetandthenearestnewcentroid,generatingaloop.Thisloopmaycausekcentroidstochangetheirlocationstepbystepuntilnomorechangesareaccom-plished.Inotherwords,centroidsdonotchangeanymore.Finally,thisalgorithmaimsatminimizinganobjectivefunction,inthiscaseasquarederrorfunction.TheobjectivefunctionJ k=

n x(j)

i uj 2

(1)

j=1i=1

where x(j)

(j)

i uj 2isachosendistancemeasurebetweenadatapointxiandthegroupcentroiduj,isanindicatorofthedistanceofndatapointsfromtheirrespectivegroupcenters.

Thealgorithmiscomposedofthefollowingsteps:(1)Datapointsareassignedatrandomtothekgroups.Thecentroid

iscomputedforeachgroup.

(2)Eachpointisassignedtothegroupwiththeclosestcentroid.(3)Whenallpointshavebeenassigned,recalculatethepositionsof

thekcentroids.

(4)RepeatSteps(2)and(3)untilcentroidsstopchanging.Thispro-ducesaseparationofthepointsintokgroupsfromwhichthemetrictobeminimizedcanbecalculated.k-meansisasimplealgorithmthathasbeenadaptedtomanyproblemdomains.Asthefollowingshows,itisagoodcandidateforextendingworkwith3Dmeshsegmentation.2.2.Principalplaneanalysisfor3Dmodels

In[29],thisworkproposesa3Dmodelretrievalmethodusingprincipalplaneanalysisthatdefinestheprincipleplaneasaskele-tonrepresentationcorrespondingtothesymmetricsurfacefora3Dobject.

Theprincipalplanecanbeconvenientlyrepresentedintermsofmoments.Inthecaseof3DfeaturespaceS3,theprincipalplaneHcanberepresentedasAx+By+Cz=D

(2)

whereA,B,andCarethedirectionalnumbersofHthatsatisfythefollowingrelationship:A2+B2+C2=1.

(3)

Thedistancefroma3Dvector c=(x,y,z)toHisgivenbyf(x,y,z)=Ax+By+Cz D.

(4)

Letthecentroid¯c

ofthe3Dspacebedefinedas N

(¯x,y¯,z¯)= 1 1 N1

NNxi,yi,zi

(5)

i=1

Ni=1

N

i=1

wherexi,yi,andziarethetri-stimulusvaluesoftheithvector.

Obviously,thedistancefromtheorigin(0,0,0)ofS3toHisD.Forprocessingconvenience,wesubtractthecentroidfromallthe3Dpointsinordertotranslatetheoriginofthe3Dspacetothecentroid.Inthiscase,thevalueofDin(2)iszero.

S.-C.Chengetal./PatternRecognition43(2010)267--279269

Tofindthedirectionnumbersofthe3DprincipalplaneH,taketheoriginatthecentroid;thentheinertiamomentofthepointsinS3abouttheplaneHis

I(A,B,C)=

(Ax+By+Cz)2.(6)

(x,y,z)∈S3

DifferentiateswithrespecttoA,BandC,andequatingtozerogives2

x(Ax+By+Cz)=0(x,y,z)∈S3

2

y(Ax+By+Cz)=0(x,y,z)∈S3

2

z(Ax+By+Cz)=0.

(x,y,z)∈S3

Hence,

m2,0,0A+m0,1,1B+m1,0,1C=0m1,1,0A+m0,2,0B+m0,1,1C=0m1,0,1A+m0,1,1B+m0,0,2C=0(7)

wherems,t,uisa3Dmomentgivenby

m

s,t,u=xsytzu.

(8)

(x,y,z)inS3

Tosolvethesetoflinearsystemin(6),wegetAm0,2,0m1,0,1 m1,1,0m0,1,1

B=

m(9)

2,0,0m0,1,11,1,0m1,0,1=k1Cm0,2,0m1,0,1 m0,1,1m1,1,0

B=

m=k2.(10)

0,0,2m1,1,00,1,1m1,0,1

Thevaluesofk1andk2canbeobtaineddirectlyfromthevaluesof3Dmomentswhichcanbecomputedinadvanceaccordingto(8).CombiningEqs.(3),(9),and(10),itissimpletoobtain

(A,B,C)= k1

,1k2 .1+k21+k2,21+k21+k2(11)21+k21+k22OncetheprincipalplaneHisobtained,foreach3Dvector c

=(x,y,z)wecancomputethedepthfrom ctoHbydH( c

)=Ax+By+Cz.(12)

3.Theproposed3Dmeshsegmentation

Clustering-basedsegmentationusesiterativeclusteringasatool

toseparatetheinputmeshintomultipleregionsaccordingtolocalpropertiesofvertices.Forexample,Shlafmanetal.[30]usedk-meansclusteringtoprovideameaningfulsegmentation.However,thepro-ducedregionshavejaggedboundaries,showninFig.1(a).Theprob-lemswithapplyingk-meansclusteringtosegment3Dmeshmodelsarethreefold:(1)k-meansclusteringdoesnotguaranteegeneratingcontiguousclustersandthusmightresultinseveralsmalluniformregions.(2)Themethodselectsanumberofseedverticesandthenassignseachtriangletotheclusterofthenearestseedvertex.Theresultingregionsaredependentontheinitialsetofseedvertices.Moreover,itisnotadaptivetotheshapesofmeshsurfaces.(3)Thenumberofclusters,i.e.,thevalueofkisingenerallyunknown.Thisworkpresentsasegmentationframeworkincorporatingk-meansclusteringandprincipalplaneanalysistosolvetheaboveproblems.Fig.1(b)showsasegmentationexampleusingtheproposedmethod.

Thispaperintroducesamultispacegeneralizationofthemulti-pleprincipalplaneanalysis(whichwecallMPPA),wheremoresub-spacesarecreatedtoapproximatethedifferentuniformregionsof

theinputmeshmodel.TheMPPAcanbeusedtogenerateacompactrepresentationoftheoriginalmeshmodelbymappingeachvertexonlyintothebest-suitedsubspace,showninFig.2.Then,allthesubspacesaresimultaneouslyusedtoencodeeachconnectivityandvertex,thusprovidingmultiplepointsofviewtotheinputmesh.

LetV={ v

i∈R3|i=1,...,n}beasetofn3DverticesofaninputmeshM,thenforagivenpartition ={P1,P2,...,P

k}ofVsuchthatPi=V,Pi∩Pj= i,i,j=1...k,i ji=1...k

theMPPAsegmentationisdefinedbythesetofsubspacesS={SSc¯i,Hi,i=1,...,k},where¯c1/|S

i|Si=

i=i|v ∈Pi v

isthecentroidcoordinateofSiandHiistheprincipalplaneofSidefinedin(2).Eachsubspacedeterminesaprincipalplane,andthesetofprincipalplanesprovidesacompactrepresentationoftheoriginalmeshmodel.

AhugenumberofMPPAsegmentationsmaybederivedfromthesameinputmeshmodelbyvaryingkand .Theapproachtoobtainbetterkand aimsatminimizingthemean-squareaveragerecon-structionerroron ,definedasaweightedsumofreconstructionerrorsrelatedtothesubspaceSiapproximatedbyHi

k(k, )=1

n

mi|dHi( v

)|(13)

i=1

v

∈Piwherem )isthedepthvaluev

HiisthecardinalityofPianddHi(v

from toidefinedin(12). (k, )isthenacostfunctionrepresentingtheinputmeshmodelMandusedasameritfunctionforchoosingkand .

Obviously,thelargervalueofkleadstoasmallervalueof (k, )usingtheunconstrainedminimizationprocess.Alimitcaseiswheneachtriangleconstructsaregionandenablesazero-errorsolution,i.e., (k, )=0.Ontheotherhand,employingafewelementsforcreatingaregionwouldnotachievehighcompressionrate.Thus,thisworkproposesapracticalstrategytodetermineanoptimalMPPAsegmentationusingk-meansclustering.Let maxbethemaximumerrorchosenfor (k, ).Thealgorithmproceedsbyincreasingkuntilfindingasolution(k, )suchthat (k, ) maxorthemaximum

allowednumberofregionskmaxisreached.Let betheoptimalsegmentationforapartition k

k.TheMPPAsegmentationalgorithmisseparatedintothreemainsteps:

MPPA(V, max,kmax){k=1;

=∞;//setstheoptimalreconstructionerrorfoundingtobeaverylargenumberdo{

k=k+1;

k = Generate(k,V);//generatesinitialsegmentationfork= Optimize(k, k);//ifk

optimizesthepartition k( > (k, )){= (k, k

k);//updatestheoptimalreconstructionerrorfound-ing

t=k;// tisthebestsegmentationfounding}

}while( > max∧k<kmax)return(t, t);}

Obviously,requiringsmallreconstructionerrors,i.e.,smallvaluesof max,allowstheregionstobetterfittheinputmeshmodel,butatthesametime,determinesthecreationofalargernumberofregions.Thefollowingdiscussestheoptimizationprocedure( -Optimize)andtheinitializationprocedure( -Generate)indetail.

270S.-C.Chengetal./PatternRecognition43(2010)267--279

k-means

0-20-40

-60-40

-60-40-20

0-20-40

-20

k-means with principal plane analysis

20

-60-40

-20

40

6080

2040

60

80

-60-40-20

Fig.1.Segmentationresultsusing(a)k-meansclusteringand(b)k-meansclusteringwithmultipleprincipalplaneanalysis.

3.1. -Optimize

Theprocedure -Optimizeiterativelyfinetuneaninitialpar-tition ksuchthatthevalueof (k, k)decreases.Theoptimiza-tioniscarriedoutbyrearranging fromtheircorrespondingprincipalktominimizethedistancesofverticesplanes,thusminimizingreconstructionerrors.Ateachstep,principalplanesarederivedtoapproximatetheshapesofcorrespondingsubspacesandeachver-texisreassignedtothenearestsubspaceaccordingtothedepthin-formation.Fig.3showsanexampleofseparatingtheinputmeshmodelintotworegions,eachapproximatedbyitsprincipalplane.The -Optimizeprocedureissummarizedasfollows:

-Optimize(k, ={P1,P2,...,Pk}){

t=0;//tistheiterationcounterrepeat{

i=1,...,kHi=PPA(Pi);//PPAcomputestheprincipalplaneHiforP i

Pold= ;

1 =P2=···=Pv

∈V{k= ;z=argmini=1,...,k(|dHi( v

)|);//dHi(v )isthedepthfromv toHidefinedin(12)

Pz=Pz∪{ v

};}

t=t+1;

}until( = old∨t=tmax);return( )}

3.2. -Generate

Analogoustothek-meansalgorithm,theinitialclusterscanberandomlygenerated.However,badinitialconditionsoftenresultinabadpartitionforthek-meanslikealgorithms.Thecurrentworkusesamoreeffectiveapproachtogeneratebetterinitialsolutions.

Thismethodisbasedonaclusterseparatingschemebysplittingaclusterwithalargereconstructionerrorintotwosets.Initially,alltheverticesintheinputmeshareplacedinthesetP1.Inthefirsttimecallofthe -Generateprocedure,theprincipalplaneH1ofP1isobtainedbyperformingthePAAtransformation.Foreachvertex

v

inP1,wecomputeitsdepthvaluedH1( v)using(12).Then,P1isseparatedintotwosetsaccordingtothedepthvaluesofvertices

v∈P11,if(dH1( v) d¯H1

)P,otherwise,d¯H1

=1 dH1( v).(14)121 v

∈P1

Ifitisthekthtimetousethe -Generateprocedure,theopti-mizationpartition obtainedfromthe -Optimizeprocedureinthepreviousiterationk 1

oftheMPPAsegmentationalgorithmis

used

Fig.2.AnMPPAsegmentationwherethree3Dsubspacesarecreatedandeach

subspaceisusedtorepresentasubsetofverticeshavingsimilarcharacteristics.

togeneratethecandidatepartition kforfurtheroptimizationpro-cessing.Thek 1vertexsets,i.e.,P1,P2,...,Pk 1,in ,andtheirprincipalplanesaregiven.ForeachvertexsetPin k 1reconstructionerrorasfollows:

k 1,wefirst

calculateitsweighted (P)=

m

n

|dH( v

)|(15)

v

∈PwheremandnarethenumbersofverticesbelongingtoPand respectively.Accordingly,thevertexsetwithlargersizeandrecon-k 1

,structionerrorhasalargervalueof ().Thesetwiththelargestvalue

of ()isselectedfrom toprovideanadditionalk forsplittingusingtheruledefinedin(13)vertex1

setfor issummarizedasfollows:

k.The -Generateprocedure -Generate(k,V){

if(k=2){//ThefirsttimeusingtheprocedureP1=V;

H1=PPA(P1);//PPAP2={ v|dH1(v )>d¯computestheprincipalplaneH1forP1

H1&v ∈P1};//d¯H1

istheaveragedepthvalueofP1

S.-C.Chengetal./PatternRecognition43(2010)267--279

271

Fig.3.Anexampleofrearrangingverticesintheinputmeshtothenearestneighborregionsusingmultipleprincipleplaneanalysis.

P1=P1 P2;}else{

foreachvertexsetPin ,computes (P)using(14);z=argmaxk 1

i=1,...,k 1( (Pi));//choosethesetwiththelargestreconstructionerror

Pk={ v|d¯&vPHZ(v )>dHZ

∈Pz};//splitPzintotwosetsPz=z Pk;}

return( k={P1,P2,...,Pk});}

4.Segmentation-based3Dmeshmodelcompression

Performingthesegmentationalgorithmmentionedabove,theinput3Dmeshmodelisseparatedintomultiplemeaningfulre-gions,whicharethenseparatelycompressedandtransmittedtothedecoder.Foreachregion,wehavetwocompressionjobstodo:geometrycodingandconnectivitycoding,oftentreatedastwoin-dependentcompressionphasesinexistingresearches[12,13].How-ever,theconnectivityandgeometryinformationfora3Dmeshshouldhavehighcorrelation.Thus,combininggeometrycodingandconnectivitycodingisessentialtoachievehighrate3Dmeshcom-pression.Fig.4showstheblockdiagramoftheproposed3Dmeshcompressionsystem.Basically,theproposedregion-based3Dmeshcompressionconsistsoftwophases:boundarycodingandinter-nalconnectivity–geometrycoding.Thishierarchicalrepresentationschemeprovidesaflexiblewaytoimplementaprogressive3Dmesh:intheformerstage,theboundariesofeachregioncorrespondingtothecompactshapeapproximationoftheinputmesharetransmit-ted.Then,theinternalconnectivityandgeometryinformationforeachregionistransmittedtofinetunethetopologystructureoftheregion.

4.1.Boundarycoding

Supposethattworegionsshareajointboundary.Atthedecoderside,regionswithjointboundariesshouldbezippedproperlytoreconstructtheoriginalmesh,showninFig.5.Eachedgeoftheinputmeshiseithersharedbytworegions,calledaboundaryedge,orbelongstoasingleregion,calledaninterioredge.Theshapeofaregionisdefinedbyaclosedloopformedbylinkingupitsboundaryedges.Tworegionsareadjacentregionsiftheyshareanedge.

Fig.4.Blockdiagramoftheproposed3Dmeshcompressionsystem.

Fig.5.Zippingtworegionstogetherbasedonthejointboundary:(a)regionsbeforezippingand(b)zippingresultof(a).

A3Dmeshcanberepresentedasoneormoreconnectedcompo-nents,eachconsistingofasetofregionswitheverypairofregionsreachablewitheachother.GivenaconnectedcomponentC,wecon-structagraphG=(N,E)tomodel,whereNisthesetofregionsinCandEisthesetofedges,eachofthemlinkseverypairofadja-centregions.ConstructingaspanningtreefromGiseasy,andthemeshregionsencodeonebyonebyfollowingthetreeedgesusingaspecifictreetraversalalgorithm.

Rememberthataprincipalplaneisusedtoapproximatearegion

mesh.Let v theverticesi

,i=1,...,mbeasetofverticescollectedfromprojecting v

i,i=1,...,mofaregionPontoitsprincipalplaneH.Thecoordinatesof v i,showninFig.6(a),canbeobtainedfrom v i= vi dH( v) nH,

i=1,...,m

(16)

where n

HistheunitnormalvectoroftheprincipalplaneH.Alltheprojectedvertices v ,i=1,...,mofPareonthecommonplaneH,showninFig.6(b).

i

TheproposedboundarycodingalgorithmstartsencodingtheboundaryBofaregionbyprojectingtheregionontoitsprincipalplaneH.TheprojectedboundaryB oftheregionformsaclosedlooponHbylinkinguptheprojectedboundaryedges.Theboundarymayhaveanorientation,inwhichcase,everyboundaryedgeisadirected

edge,withastartandendvertex.Let vibeavertexofB,and v i

be

272S.-C.Chengetal./PatternRecognition43(2010)267--279

→

1

Fig.6.ProjectingverticesofaregionPontoitsprincipalplaneH:(a)therelation-shipbetweentheoriginalvertices v

i,i=1,...,mandtheircorrespondingvertices v

i,i=1,...,monH;(b)Histhecommonplanefortheprojectedvertices v i,i=1,...,m.

v1′

v0

′Boundary

Fig.7.Boundarydescription.

thecorrespondingvertexofB

.Thevertex v

icanbereconstructedusing v

i)n H.Sincetheprincipalplaneisobtainedbyminimiz-ingthei+dH(vsumofabsolutedepthvaluesoftheverticeswithinaregion,

theabsolutevalueofdv H( v

i)isoftensmall.Thus,thecoordinatesof i

shouldbeeffectivelyencodedtoachievehighcompressionrate.Consideringthecentroid¯c

HofHasthereferencepoint,thebound-arycodingalgorithmstartsscanningtheprojectedboundaryB byarbitrarilychoosingavertexofB toformtheinitialvector.Acircle

centeredat¯c

HisformedtovisiteveryvertexinB inthecounterclockwisefashion.Duringthisscan,boundarycodingrecordsthefol-lowingboundarydescriptioncodeforB : u

0 VertexChainCode (17)

where u0=( v 0 ¯cH)isthestartingreferencevectorandVertexChain-Code(VCC)[31]isthesequenceofpolarcoordinates r

i , i foreach

boundaryvertex v iwith ui 1=(v i 1

¯cH)asthereferencevector,showninFig.7.Moreconcisely,thevaluesofr

i and ifor v i

aredefinedas r

i

= v i ¯cH 1( v ¯cH)·(v ¯cH)(18)

i=cosi 1i

.HHTheVCCtoencodetheprojectedboundaryB canbefurthertrans-formedintotheDifferentialVertexChainCode(DVCC)bysubtracting

thepolarcoordinatesof v removeredundantVCCinformation.ifromthoseofitspreviousvertex v toInthiscase,theboundaryi 1

de-scriptioncodeforB ischangedinto

u

0 r

1, 1 DVCCB (19)

whereDVCCB isdefinedasDVCCB ={ r

i , i | ri =ri ri 1,

i= i i 1,i=2,...,|B |}.

Thevaluesof r

i and inDVCCB arerelativelysmallcompared

withr

i andiinVCC,andthusrepresentingB intermsofDVCCB hasbettercompressionresult.ThisworkencodesDVCCforeachprojectedboundaryusingthewell-knownvariablelengtharithmeticcoding[32]tofurtherimprovecompressionrate.

Tocompletethediscussionoftheproposedboundarycoding,foreachregion,thetotalinformationtorecordincludes(1)thenormal

vector n

Hoftheprincipalplane,(2)thedepthvaluesequenceforeachvertex,(3)andtheboundarydescriptioncodedefinedin(19).Inordertozipthejointboundaries,thesharededgesandverticesareindexedatboththeencoderanddecoderends.Aboundarysep-aratingtworegionsisalsoencodedtwice.Thecurrentworkrecon-structsthejointboundaryusingthesamerule,sothatthedecoderzipsthetworegionsseamlesslywithoutadditionalinformation.4.2.Internalconnectivity–geometrycoding

Foreachregion,theinternalconnectivity–geometrycodedescribesthetopologystructurewithintheregionindetail.Theproceduretoencodetheinternalconnectivityandgeometryinfor-mationsimultaneouslyforaregionissimilartothatusedtoencodetheboundary.Onceagain,theprincipalplaneofeachregioncanbeusedtoprojecteveryvertexoftheregionontothesameplane.Thevertexscanningtechniquementionedabovecanbeappliedtovisitandencodealltheinternalverticesandedges.

ThisresearchchoosesthesimpletrianglemeshofFig.8toillus-tratehowtheproposedinternalconnectivity–geometryalgorithmspansthemeshwithsuccessivecirclescanning.ThemeshshowninFig.8istheversionofprojectingverticesaswellastheiredgesontheprincipalplaneofaregion.Thisworkconductstheencodingschemeonthisplane.

Initially,thealgorithmsupposesallmeshboundaryvertices(1–13)areencodedintheboundaryencodingstage(cf.Fig.8(a)).Toconductthecircularcanningprocedureforencodinginternalconnectivityandgeometryinformation,weneedtoselectanin-ternalvertexasthestartingreferencevectorconsistingoftwovertices—oneofwhichisinternal.Letvertices(15,13)constitutethestartingreferencevertices(c.f.Fig.8(b)).Startingwiththisrefer-encevector,theinternalconnectivity–geometrycodingalgorithmthenrecursivelyandcircularlyvisitstheinternalvertices.Theseedvertex15visitsthevertices(13,19,17,16,14)inclockwisedirec-tion(Fig.8(b)).Afterthisstep,thealgorithmoutputstheinternalconnectivity–geometrydescriptioncode

v15 v13 T, r19 1519 15

17 1517 15

13 15, 13 15 T, r19 15, 19 15 T, r16 1516 15

14 15

14 15

17 15, 17 15 T, r16 15, 16 15

(20)

S.-C.Chengetal./PatternRecognition43(2010)267--279

273

15

5

5

1011

5

1

1

Fig.8.Encodingtheinternalconnectivity–geometryinformationofasimplemeshusingtheproposedcircularscanning

algorithm.

5

555555

Fig.9.Reconstructingthestructureofasimplemeshusingtheinternalconnectivity–geometrydescriptioncodes.

s iisthecoordinateofvertexi, rji i v s v j v s wherev= vs

s,v j v s,and j s= i visthenormdifferencebetweenvectorsv

i v s)·(v j v s))/ v i v s v j v s istheanglebetweencos 1((v

i v sandv j v s,andT=0indicatesthattheaccompanyingvectorsv

informationforeachbracedpartisusedforreconstructingthevertex

coordinates.Notethateveryvisitedvertexihasanedgeconnecting

i s

totheseedvertexsandeverypairofconsecutivevisitedverticeshasanedge.ThisstudymaintainsavertexorderedsetSconsistingofinternalverticesvisitedinthepreviouscircularscanningprocesses.Afterthefirstrun,S=(13,19,17,16,14).ThevertexinSisoneoftheseedvertexcandidatestostartacircularscan.

Next,weselectthefirstinternalvertexvisitedbythepreviousscanprocessasthenextseedvertex.Inthiscase,13willbetheseed

274S.-C.Chengetal./PatternRecognition43(2010)267--279

vertexforthenextruntoscanunvisitedvertices.InS,vertex13hastwoneighboringvertices14and19.Again,wescanthevertices(4,3,2,1)fromtheedgebetween14and13totheedgebetween19and13(Fig.8(c))andoutputtheinternalconnectivity–geometrydescriptioncode T,4 T,3 T,2 T,1

whereT=1indicatesthattheaccompanyinginformationforeachbracedpartisavertexindexwhosecoordinateshavebeencoded.Inthiscase,(4,3,2,1)areboundaryverticescodedintheaboveboundarycodingprocedure.Afterthestep,vertex13willberemovedfromSandvertex14isthenextseed.FurtherstepsintheconquestareshowninFig.8(d)–(i).

Toreconstructtheinputmesh,thereconstructionalgorithmini-tiallyrestorestheboundary(0–12)usingtheboundarydescriptioncode(Fig.9(a)).Nowfromthefirstinternalconnectivity–geometrydescriptioncodedefinedin(19),thealgorithmrestorestheinternalnodes(13,19,16,17,14)(Fig.9(b)),resultinginsettingthevertex13asthenewseednodeandtheedgesfrom14to13andfrom19to13formthetwosidesofthenextrestorationrun.Thesuccessive

reconstructionoffanscontinuesuntiltheentiremeshisrecon-structedasshowninFig.9(c)–(i).

Theinternalconnectivity–geometrycodingalgorithmvisitstheinputregionverticesonitsprincipalplane.Foreachvertex,thedepthvalueshouldbeaddedintothecodingstreamtorestoreitsoriginalcoordinates.Theprojectedregionisona2DspaceifwerotatetheregionbyaligningtheaxiszwiththenormalvectoroftheprincipalplaneasshowninFig.10.5.Experimentalresults

Toevaluatetheeffectivenessoftheproposedsegmentation-basedcompression,thecurrentstudyimplementsa3Dmeshmodelcompressionsystemforgeometricandconnectiveencod-ing/reconstructionofmeshesonaPCwithPentiumIV1.8GHzCPUrunningtheWindowsXPoperatingsystem.Theexperimentsusedasetof3Dmeshmodels(Fig.11)forperformancemeasurementsthatarefreelyavailableontheInternet.

Thisinvestigationfirsttestedeffectivenessoftheproposedmeshsegmentationalgorithmusingthehybridofk-meansclusteringandthemultipleprincipalplanesanalysis.Fig.12showsthesegmenta-tionresultofthisapproachappliedtoanoisysimple“triceratops”modelwith90%verticesmovedalongthesurfacenormals.GiventhesegmentationresultoftheoriginalmeshmodelMasthegroundtruth,wemightderiveasimplecriterionSPtoverifyrobustnessoftheproposedmeshsegmentationalgorithm.SPisdefinedas

k1 i||Ri∩RSP=H

z

y

10

9

81718

71615

6

51413

34

i=1

11

19

12

1

2

Z’H

y’

x’

Fig.10.Theprojectedregionisonatwo-dimensionalspacebyrotatingtheregion

Hoftheprincipalplanewiththeaxisz:(a)thewithaligningthenormalvectorn

H)originalmeshinthex–y–zspace

and(b)theprojectedmeshinthex –y –z (n

space.

i|isthenum-where|M|isthenumberofverticesinMand|Ri∩R

berofverticeswhicharebothwithinthesegmentedregionRifor

iforthenoise-addedmeshmodel.ThevaluetheoriginalmeshandR

ofSPishighwhenthesegmentedregionsofanoise-addedmesharealmostthesameasthoseoftheoriginalmesh.InthecaseofFig.12,thevalueofSPachieves99%.Thus,theproposedsegmenta-tionalgorithmisrobustinresistingnoise.

Thecurrentsegmentationprocedureproducesthecorrectseg-mentationofthemodel.Thenumberofregionssegmentedfromacomplexmeshmodelaffectsprecisecompactrepresentation.Fig.13showsthatvaryingthenumberofsegments(kmax)usedintheseg-mentationprocedureleadstoadaptivemeshsmoothingwithsimul-taneoussharpeningofsurfacecreasesatdifferentgeometricscales.Fig.14showsdistributingreconstructionerrorsofFig.13(a)usingsegmentedregionstoapproximatetheoriginalinputmesh.Accord-ingly,theproposedmeshsegmentationprocedureprovidesaccuratecompactrepresentationtoapproximatetheinputmesh.Accordingto(15),wecancalculatethereconstructionerrorforaninputmesh.Fig.15showsothersegmentationresultsfordifferentmeshmodels,andTable1listsreconstructionerrorsusingthesegmentedregionstoapproximatetheinputmodels.

Fig.11.Examplesof3Dtriangularmodelsusedformeasurements:(a)“nefertiti”;(b)“body”;(c)“tiger”;(d)“bunny”;(e)“triceratops.”

S.-C.Chengetal./PatternRecognition43(2010)267--279

275

Fig.12.Segmentationresultsofasimplemodelusingtheproposedmethod:(a)original“triceratops”model;(b)and(c)arethesegmentationsof(a)withwireframeandflatshaded,respectively.(d)Noisy“triceratops”modelwith90%verticesmovedalongthesurfacenormals;(e)and(f)arethesegmentationsof(d)withwireframeandflatshaded,

respectively.

Fig.13.SegmentationresultsfortheStanfordbunnyusingtheproposedsegmentationprocedurewithdifferentnumbersofregions:(a)theoriginalmodel;(b)thesegmentationresultwith10regions;(c)thesegmentationresultwith50regions,and(d)thesegmentationresultwith100

regions.

0.110.10.09Reconstruction Error

0.080.070.060.050.040.030.02

2

4

6

8

10

12

14

16

18

Number of Segments

Fig.14.ThereconstructionerrorofFig.13(a)usingsegmentedregionstoapproxi-matetheoriginalmodelunderdifferentgeometryscales.

Second,wecompresstheinputmeshmodelsbyencodingthesegmentedregionsonebyonewiththeproposedcompressional-gorithm.Fig.16showsthecompressionresultsconsistingofase-riesofregionencodingstepsfor“Nefertiti”,andFig.17showsthecorrespondingreconstructionsteps.Fig.18showsasimulationoftheprogressiveregion-by-regiontransmission.Theusercanchoosetoresumeaparticularlyinterestedregion(Fig.18(a))orrestorethewholeobjectusinganinteractiveloopuntilreconstructingthewholeobject(Fig.18(b)).Theproposedcompressionschemeusesvariablelengtharithmeticcodingforfurthercompressingthegeometrycodesandboththelossyandlosslessgeometrycodingmodesareofferedinthesystem.TherelativedemonstrationsareshowninFig.19.

Finally,inordertofurtherverityeffectivenessoftheproposedmethod,thisworkalsosimulatestheDualParallelogramPrediction(DPP)method[18]andAsymptoticClosedLoopVectorQuantiza-tion(ACLVQ)scheme[14]forperformancecomparison.Eitheronefocusesonthedesignofgeometrycodingof3Dmeshes.Table2liststheresultsofcompressionrateandrunningtimeduringcodinganddecodingforeachtestmodelusingdifferentmethods.ThebpvslistedinTable2encodesboththeconnectivityandgeometryinfor-mationfortheproposedmethod,butthebpvsfortheDPPmethodandtheACLVQmethodincludeonlygeometryinformationwithver-texpositionsbeingpre-quantizedwith10bitspercoordinate(bpc).Theconnectivityinformationcontributesanadditional1–2bpvsto

276S.-C.Chengetal./PatternRecognition43(2010)267--

279

Fig.15.Thesegmentationexamples:(a)“body”segmentedintotworegions;(b)“nefertiti”segmentedintothreeregions;(c)“triceratops”segmentedintofiveregions;(d)“tiger”segmentedintosixregions.

Table1

Reconstructionerrorsusingthesegmentedregionstoapproximatetheinputmodels.Models

kmax

Constructionerrors0.13200.09680.01790.02280.2148

NefertitiBodyTigerBunny

Triceratops4413199

Fig.16.Region-by-regionencodingstagesofthe“nefertiti”model:(a)–(c)areaseriesofcircularscanprocessestoencodethefirstregionand(d)–(h)aretheconnectivity–geometryencodingsteptocompressregions2and3.

compressionratesoftheDPPmethodandtheACLVQmethodifweusestate-of-the-artconnectivitycoding[11].Accordingly,thepro-posedmethodoutperformsthecomparedmethods.Fig.20showscompressionperformancecomparisonfordifferentmethodsusingthetestmodelsintermsofcompressionrateanddistortioner-ror.Fig.21showsreconstructionqualitycomparisonforthe“Tiger”modelusingdifferentmethodswithnearlythesamecompressionrate.

TheproposedcircularscanningprocessforvisitingverticesissimilartothefanscanningprocessintheAdvancingFan-Front(AFF)methodproposedbyMuduretal.[11].TheAFFtraversesthefansofatrianglemeshusingaboundaryvertexandtwoboundaryedgesas

S.-C.Chengetal./PatternRecognition43(2010)267--279

277

Fig.17.Region-by-regionreconstructionstageofthe“nefertiti”model:(a)–(c)arethereconstructionstepstorestoreregion1and(d)–(h)arethereconstructionstepstorestoreregions2and

3.

Fig.18.Simulationoftheprogressiveregion-by-regiontransmission:(a)particularlyinterestingregionselectedbyuserand(b)wholeobjectstepby

step.

Fig.19.Demonstrationoflossyandlosslessgeometrycoding:(a)originalmodel;(b)losslesscodingand(c)–(e)lossycodingunder16,12,8bitspervertex.

theinitialseedandstartinggates,respectively.Theproposedschemechoosesaninteriorvertexastheinitialseedfortraversingthefansofthetrianglemesh.Theinteriorvertexastheinitialseedreducesthenumberoffansinboththeencodingandreconstructionstages.Theproposedalgorithmalsoencodesboththeconnectiveandge-ometryinformationsimultaneouslycomparedwithAFFwhichonly

278S.-C.Chengetal./PatternRecognition43(2010)267--279

Table2

PerformancecomparisonformeshcompressionusingtheproposedmethodA,DPPmethodB[18],andACLVQmethodC[14].Model

Vertices

Faces

No.FansinA

MethodAGC+IC

NefertitiBodyTigerBunny

Triceratops

2997115169348343124

562179610061694515660

1453542223160981254

15.0412.227.787.2310.56

T0.0320.0530.4523.3210.245

MethodBGC15.6113.129.237.4711.32

T0.0200.0640.5542.2310.292

MethodCGC15.2313.868.327.1111.62

T0.0430.1020.7245.0210.422

GCisthegeometrycodingintermofbitspervertex(bpv),ICistheconnectivitycoding,andTistheaverageexecutiontimeinsecondstocodinganddecodingamodel.

161514Bits Per Ve

rtex (bpv)

Mean Square Error

13121110987

Nefertiti

Venus

TigerModels

BunnyTriceratops

ProposedDPPACL VQ

10-5

ProposedDPPACL VQ

10-6

10-7

10-8

NefertitiVenusTigerModels

BunnyTriceratops

pressionperformancecomparisonfordifferentmethodsusingthetestmodelsintermsof(a)compressionrateand(b)distortionerror.

parisonofreconstructionqualityforthe“Tiger”modelusingdifferentmethodswithnearlythesamecompressionrate:(a)theoriginalmodel;(b),(c),and(d)arethereconstructionresultsof(a)usingtheproposedmethod,theDPP,andtheACLVQ,respectively.

focusesonencodingtheconnectivityinformationofamesh.Simula-tionresultsshowthattheproposedalgorithmprovidesapromisingencoding/decodingtechniquefor3Dmeshes.6.Conclusion

Thispaperproposesasegmentation-based3Dmeshcompres-sion.Ourcontributionslieinthreeaspects.Firstly,fusingthewell-knownk-meansclusteringandtheproposedprincipalplaneanalysistoseparatetheinput3Dmeshintoasetofdisjointedpolygonalregionsisefficientandrobust.Secondly,wecompressthemeshobjectintoindependentregionsandaboundary,sothedecoderobtainseachindividualpartandrestorestheoriginalobject.ThisisespeciallyusefulinsomeinteractiveapplicationssuchasInternetgamingandremotetraininginavirtualenviron-ment.Theusercanrestoretheparticularlyinterestedpart(s)orthewholeobjectstepbystep.Finally,theproposedcircularscanningprocedureprovidesanewmethodtoencodeconnectivityandge-ometryinformationoftheinputmeshsimultaneously.Traditionalmethodsbelongingtoeitherconnectivitycodingorgeometrycod-ingdonotofferatotalsolutiontotheproblemof3Dmeshcom-pression.

Experimentalresultsshowthatourschemeprovidesbettercom-pressionthanearlierknowntechniques.Ourfuturestudywillfocusoncontent-based3Dmodelretrievalinthecompressiondomainanderrorresilienceduringtriangularmeshreconstruction.

S.-C.Chengetal./PatternRecognition43(2010)267--279279

References

[1]M.Deering,Geometrycompression,in:ProceedingsoftheACMSIGGRAPH,

1995,pp.13–20.

[2]M.-M.Chow,Optimizedgeometrycompressionforreal-timerendering,in:

ProceedingsoftheEighthConferenceonVisualization'97(IEEEVisualization'97),SanFrancisco,CA,1997,pp.347–354.

[3]C.Touma,C.Gotsman,Trianglemeshcompression,in:Proceedingsofthe

GraphicsInterfaces'98,1998,pp.26–34.

[4]H.Hoppe,Progressivemeshes,in:ProceedingsoftheACMSIGGRAPH'96,1996,

pp.99–108.

[5]R.Pajarola,J.Rossignac,Compressedprogressivemeshes,IEEETransactionson

VisualizationandComputerGraphics6(1)(2000)79–93.

[6]S.-B.Park,C.-S.Kim,S.-U.Lee,Progressivemeshcompressionusingcosine

indexpredictorand2-stagegeometrypredictor,in:ProceedingsoftheIEEEICIP2002,vol.2,2002,pp.233–236.

[7]P.Alliez,M.Desbrun,Progressivecompressionforlosslesstransmissionof

trianglemeshes,in:ProceedingsoftheACMSIGGRAPH2001,2001,pp.195–202.[8]P.-M.Gandoin,O.Devillers,Progressivelosslesscompressionofarbitrary

simplicialcomplexes,ACMTransactionsonGraphics21(3)(2002)372–379.

[9]J.Rossignac,Edgebreaker:connectivitycompressionfortrianglemeshes,IEEE

TransactionsonVisualizationandComputerGraphics5(1)(1999)47–61.[10]S.Gumhold,W.Strasser,Realtimecompressionoftrianglemeshconnectivity,

ACMSIGGRAPH(1998)133–140.

[11]S.P.Mudur,S.V.Babji,D.Shikhare,Advancingfan-front:3Dtrianglemesh

compressionusingfanbasedtraversal,ImageandVisionComputing22(2004)1165–1173.

[12]J.Peng,C.-S.Kim,C.-C.J.Kuo,Technologiesfor3Dmeshcompression:asurvey,

JournalofVisualCommunicationandImageRepresentation16(2005)688–733.[13]P.Alliez,C.Gotsman,Recentadvancesincompressionof3Dmeshes,in:

N.A.Dodgson,M.S.Floater,M.A.Sabin(Eds.),AdvancesinMultiresolutionforGeometricModelling,Springer,Berlin,2004,pp.3–26.

[14]P.H.Chou,T.H.Meng,Vertexdatacompressionthroughvectorquantization,

IEEETransactionsonVisualizationandGraphics8(4)(2002)373–382.

[15]S.Valette,R.Prost,Awavelet-basedprogressivecompressionschemefor

trianglemeshes:wavemesh,IEEETransactionsonVisualizationandGraphics10(2)(2004)123–129.

[16]Z.Karni,C.Gotsman,Spectralcompressionofmeshgeometry,in:Proceedings

oftheACMSiggraphConference,2000,pp.279–286.

[17]J.Peng,C.-C.J.Kuo,Geometry-guidedprogressivelossless3Dmeshcodingwith

octree(OT)decomposition,ACMTransactionsonGraphics(2005)609–616.[18]J.-Y.Sim,C.-S.Kim,S.-U.Lee,3Dmeshcompressionusingtrianglefanstructure,

IEEEInternationalSymposiumonCircuitsandSystems2(2002)257–260.[19]S.-B.Park,C.-S.Kim,S.-U.Lee,Errorresilient3-Dmeshcompression,IEEE

TransactionsonMultimedia8(5)(2006)885–895.

[20]L.Chevalier,F.Jaillet,A.Baskurt,Segmentationandsuperquadricmodelingof

3Dobjects,JournalofWSCG11(1)(2003).

[21]A.Mangan,R.Whitaker,Partitioning3Dsurfacemeshesusingwatershed

segmentation,IEEETransactionsonVisualizationandComputerGraphics5(4)(1999)308–321.

[22]S.Pulla,A.Razdan,G.Farin,Improvedcurvatureestimationforwatershed

segmentationof3-Dimensionalmeshes,TechnicalReport,Tempe,AZ:ArizonaStateUniversity,2001.

[23]A.Razdan,M.Bae,Ahybridapproachtofeaturesegmentationoftriangle

meshes,Computer-AidedDesign35(9)(2003)783–789.

[24]S.-C.Cheng,C.-T.Kuo,i,Apatch-growingapproachto3Dmodel

segmentationusingtriangleinequality,JournalofChineseInstituteofEngineers30(4)(2007)675–687.

[25]Y.Zhang,J.K.Paik,A.Koschan,M.A.Abidi,D.Gorsich,Asimpleandefficient

algorithmforpartdecompositionof3Dtriangulatedmodelsbasedoncurvatureanalysis,ProceedingsoftheInternationalConferenceonImageProcessing,vol.3,Rochester,NewYork,2002,pp.273–276.

[26]J.B.MacQueen,Somemethodsforclassificationandanalysisofmultivariate

observations,in:ProceedingsofFifthBerkeleySymposiumonMathematicalStatisticsandProbability,vol.1,UniversityofCaliforniaPress,Berkeley,1967,pp.281–297.

[27]T.Kanungo,D.M.Mount,anyahu,C.Piatko,R.Silverman,A.Y.Wu,

Anefficientk-meansclusteringalgorithm:analysisandimplementation,IEEETransactionsonPatternAnalysisandMachineIntelligence24(2002)881–892.[28]T.Kanungo,D.M.Mount,anyahu,C.Piatko,R.Silverman,A.Y.Wu,A

localsearchapproximationalgorithmfork-meansclustering,ComputationalGeometry:TheoryandApplications28(2004)89–112.

[29]C.-T.Kuo,S.-C.Cheng,3Dmodelretrievalusingprincipalplaneanalysisand

dynamicprogramming,PatternRecognition40(2)(2007)742–755.

[30]S.Shlafman,A.Tal,S.Katz,Metamorphosisofpolyhedralsurfacesusing

decomposition,ComputerGraphicsForum21(3)(2002)219–228.

[31]E.Bribiesca,Anewchaincode,PatternRecognition32(2)(1999)235–251.[32]K.Sayood,IntroductiontoDataCompression,MorganKaufmannPublishers,

Inc.,LosAltos,CA,1996.

AbouttheAuthor—SHYI-CHYICHENGreceivedtheB.S.degreefromNationalTsingHuaUniversity,Hsinchu,Taiwanin1986,andtheM.S.andPh.D.degreesinElectronicsEngineeringandComputerScienceandInformationEngineeringin1988and1992,respectively,bothfromNationalChiaoTungUniversity,Hsinchu,Taiwan.From1992to1998,hewasaTechnicalStaffattheChunghwaTelecomLaboratories,Taoyuan,Taiwan.HejoinedthefacultyofDepartmentofComputerandCommunicationEngineering,NationalKaohsiungFirstUniversityofScienceandTechnology,Kaohsiung,Taiwanfrom1999to2005.HeiscurrentlyaProfessorwiththeDepartmentofComputerScienceandEngineering,NationalTaiwanOceanUniversity,Keelung,Taiwan.Hisresearchinterestsincludemultimediadatabases,image/videocompressionandcommunications,andintelligentmultimediasystems.

AbouttheAuthor—CHEN-TSUNGKUOreceivedthePh.D.degreeinComputerandCommunicationEngineeringfromNationalKaohsiungFirstUniversityofScienceandTechnology,Taiwanin2007.Since1995,hehasservedasaStaffattheComputerCenteroftheLongchuanVeteransHospital,Pingtung,Taiwan.Hisresearchinterestsincludeimageprocessing,computergraphics,datamininganddecisionsupportsystem.

AbouttheAuthor—DA-CHUNWUreceivedthePh.D.degreeinComputerSciencefromNationalChiaoTungUniversity,Taiwanin1996.HeiscurrentlyanAssociateProfessorwiththeDepartmentofComputerandCommunicationEngineering,NationalKaohsiungFirstUniversity,Kaohsiung,Taiwan.Hisresearchinterestsincludemultimediadatabases,image/videowatermarking,anddigitalrightmanagementsystems.

本文来源：https://www.bwwdw.com/article/xrej.html