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

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.

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科A novel 3D mesh compression using mesh segmentation with multiple principal plane analysis(5)全文阅读和word下载服务。