Dissimulation de données par changement de connexité d'un

Publié par

Niveau: Supérieur, Doctorat, Bac+8
Dissimulation de données par changement de connexité d'un maillage 3D Data Hiding Based on Connectivity Modification of 3D Mesh P. Amat 1,2 , W. Puech 1 , S. Druon 1 et J.P. Pedeboy 2 1 Laboratoire LIRMM, UMR CNRS 5506, Université de Montpellier II 161, rue Ada, 34392 MONTPELLIER CEDEX 05, FRANCE, 2 Stratégies S.A., 41-43 rue de Villeneuve, Parc d'a?aires SILIC - BP 80429 94583 Rungis cedex - France Mots clefs Dissimulation de données, Tatouage, Maillage triangulaire 3D, Quadrangle, Parcours de graphe, Arbre couvrant minimum, Analyse en composante principale, Synchronisation des données. Key words Data hiding, Watermarking, 3D mesh, Quadrangle, Graph path, Minimum Spanning Tree, Prin- cipal component analysis, Data synchronization. Abstract Day by day, the amount of digital data has been rapidly increasing on the Internet. The size of 3D objects is very large and these objects need fast transmissions. Moreover, 3D data security becomes increasingly important for many applications, e.g., confidential transmission, video surveillance, military and medical applications. In this paper we present two new approaches of 3D object data hiding without changing the position of vertices in the 3D space.

  • méthode

  • seconde méthode

  • arbre de recouvrement des points

  • connexité des arêtes dans les zones

  • arête

  • maillage

  • parcours

  • insertion des données


Publié le : mercredi 20 juin 2012
Lecture(s) : 62
Source : lirmm.fr
Nombre de pages : 29
Voir plus Voir moins

1,2 1 1 2
1
2
wdeles.connexit?whild'unomaillageselected3DositiDatasurvHidingositionBasedisonhidConnectivitofyblindMojectsdicationpapofdata3Dspace.MeshndPging.eAmatontonhangemenarecare,theW.vPuechighhmedicalparpresen,ofS.cDruonerticesdonn?esideaetmethoJ.Phronize.cPofedebosedoapproacyobdeumulationapproacLabonoratoireters.LIRMM,senseUMRofCNRSv5506,depUnivdataersit?odewhenMonbtptransmission,elliermilitaryIInIw161,trueapproacAobda,withou34392theMONTPELLIERfCEDEXthe05,eFRANCE,theDissimproptheisusedtoedareasemobStrat?giesemS.A.,message.41-43eddinruebdeaVilleneuvconnectivite,inPcomarcquadrangles.d'aairespropSILICof-inBPis80429i94583treeRungisthecedexis-proFsecretrancequadrangleMotsmethoclefinstheDissimnuvlationhanged.detheydonn?es,doTdatouage,ofMaillagentriangulairet3D,hesQuadinra3Dnvgdigitalizedl1e,videoPeillance,arcoursanddeapplications.graphe,thisArbreercouvranettminimwum,newAnalysehesen3Dcompjectosanhidingtetprinhangingcpiopale,vSyncinhronisation3DdesThdonn?es.mainKeyofwtordsoDataosedhiding,dsWtoatermarking,and3Dsyncmesh,particularQuadrangle,ofGraph3Dpath,jectsMinimtoubmtheSpannTheingbTgree,donePrin-ycipalhcompnonenthetyanalysis,edgesDatathesyncareashronization.pAbstractofDaThyrstbosedyhdadataying,3Dthjectsebasedamounmtnimofspanningdigital(MST)dataehassecondbheenbasedrapidlytheincreasingjectiononatheaxisIntheternet.cenTheThesesizedsoflossless3DtheobthatjectspisovserythelargeerticesandunctheseMoreooberjectsareneedandfastnottransmissions.enMoreoofvorderer,the3DidatathesecuritTheseywbapproacecomesareincreasinglyeryimpterestingortanthetobforhamaneyeenapplications,withe.g.,precision.condentialsurR?sum?oDeesnosetjours,cationdesencorevisualisationscesainsifaces,quepdespr?cisiontransfertsdansd'l'?co3Dbjetsjetse3Duson?tretmarquagecourammenlatl'industrieeectu?sobpdeourtransformationsdegnfonctionnalit?soage,msansbreusesdapplicationspallantation,tpardudesjeudevid?osform?soitl'imagerietm?dicaler?aliserenjetpbreusesaosonssspasam?thonnomtouparquel'industrielesmanY,ufacturi?re.desDansaux,cetprotectionarticletransmissionnousl'enricpropvosonsladeuxhronisannouvi?reellestationm?thojetsdesepsommets,ermettancartdedebreusdissimsonulerLesdespdonn?escat?gories,dansdudesdeoblesjets3D3Dlasansmaillagemcacodesdiervlapplositioncetdesd'insertionsommets.neL'id?edicationprincipaleourdestdeux3Dm?thoudesjet,pr?sendet?esl'obestr?sistendeutrouvetertelset2deel?essyncwatermarkinghronitrasernouvdestzonesobparticuli?restdansl'arcl'ob?galemenjett3Djetspdesouvteandesten?trecesutilis?esmaphiqueourLains?rerpluslelesmessage.estL'insertionaildeCettedonn?esos?es'appuieetsurtr?slappmolesdicationgraphdeDelasconnexit?dedesba-ar?tesrepr?sendansdesles2zonesens?lectionn?esencompouos?esendeuquadrangles.r?aliserLaQueldi?rencedomaineendestre'oblestesdeuxtm?thodidessommetspr?senpt?esdesestMolaosimani?red'undeacquiss?lectionneruneetpasdedesynctelshroniserm?dicalcesufacturi?re.zonesnousd'insertion.m?thoAlorsdonnqueh?eslapuienpremi?relam?thosommetsde3Ds'appuiel'insertion.surpundesarbreobcouvranquetl'minimlaumde(AlogoCM),lalajetsecondetexturem?tholui-m?me.dem?thoutilise?un?triaxetellessurleslequelmisessonuniforme.tSTL,proetcjet?shidlesanglais,centtretatouagesanglaisdesszonesvd'insertion.cesCesellesdeuxconcernenm?tholadesdesajetsvduraneugles,laprot?g?esetparhivutilisationmaisdetclefshissemensecr?detes,obr?sistenatec?m?ta-donn?esdesaugmentransformationsrg?om?triquestailletelsobqueetlessyncrotations,ttranslationsm?ta-donn?esouecnhangemenhi?rarct(qualit?d'?cspatiale).hellerepr?senetlaneutilis?esonourtobpas3Dplerturbm?eslagparsurfacique.desrepr?senmocompdicationsdedirectesd'ar?tesdedel'ordreestdesr?panduedonn?essudansort?elestoutesccarteshiersrenduoriginaux.iqCese.appronomcehesm?thotrouvd'insertionendonn?esttuns?esincettet?r?ttation.certainm?thopd'insertionourdonn?esdes,obeuvjetst3Dclass?esdondeuxtspatiallestransomme?,tsfonctionondomainettilis??t?ouracquisl'insertionadonn?es.vqueecleuned'insertion,grandem?thopr?cisiondeetddonjetstexistanlas'appuienmog?n?ralemendicationsurn'estmopasacceptable.de1duIn3Dtroourductionl'insertionAdonn?esvh?es.ecdierl'?vpolutiontiondessommetsr?seauxobinformatiques,3Dleat?l?cechargemengrandetn'estd'obacceptablejetsour3Dnomdevienapplicationstqueuneetransmis-ousionmancouranDanste.articleAnpropddeux'?tredesundeiv?ersellemencactquilisibless'apcestobsurjetsmo3Ddesdoivdesejetsnptr?aliserr?pCesonddesreermetten?d'ins?rerdesm?ta-donn?esnormesunetjetdestelsstandleaderdasteur,indateternationaux.cr?ationM?mel'obsiunnous2Dsouhaitons3D,apcouleurpl'oborteroudlaedenouvjetellesNotonsfonctionnalit?sces?descestobdesjets,g?omilqestesdoncqueimprotations,ortantranslationstlesde?resphelleecter1lesqueformatsPLstandardsX3D1...pDataermettanintendeappmanipuler?galemencesm?thoobdejetsou3D.enDans2ne
tconinitial,tendesucompdedicationscetdearticlobeasel'ordonnan-d?comphierosedededelacesmani?reobsuivdesandanste.?reEndeSectionm?tho2,tnouslapr?sendetonsPunl'algorithme?tatunedesul'artvscat?gorieurinclesdedi?renttestransform?.m?thoetdesod'insertionjetsdedesdonn?esdanscacl'organisationh?esaappliqu?esnauxh?.obsecondejetsL3D.PeNoussurd?criveauons,maillageSectionoriginal,3,r?telescat?gories.deuxdesm?thodesdeslad'insertionlademarquer.donn?esdescacjeth?essecondepropdesos?es.DEnpSection3D,4,ounouss?epr?senoutonsCetteetdoncanalysonsreplesprimitivr?sultatsmodedenos?m?thoendesDansappliqu?esson?nivdesjetobal.jetsde3Ddicationr?els.unEnndenoustriangles,terminons,dieSectionforman5,gparedesseconclusionsetettpdeerspalgorithmeectivbandees.?ta2hoisir,Etatddepartirl'artduSelonenlepremi?retdeyprepel'ordonnancemend'application,eslesoum?thoecdest?deologietato3DucetteagpeoinpteuvoriginalenLts'appuie?tretscoinhoisiesjetensurfong?om?triquecestiobocendomainedeuncer-destainessurconprimitivtrainlates.topLesremconpr?sentrainmtesd'insertionlestpluststandard,desrelativsurementconnectivit?antoptagonistes,jetssonCesttlesencondomainetraincat?gorie,tesd'debas?espdonn?eserceptibilit?,dudetrobustesseIcetadepropcm?thoaputilisalacit?.l'or-Dansandeenompremi?rebreusesdieapplications,l'ordrelesquecondetraindestesoindeles?curit?aoumencoreuderianglecomplexit?Symbenetempsbucdeestcaclologiqueculrsonautmaillage,?galemenroptu?trianglesprendreLaenecompte.?Leslem?thoar?tedes,duquand.?cetteelles,d?partp?euv3endeuxtLa?tredeclass?escat?goriesenm?thofonctiond'insertionduosedomainerd'insertiontcprimitivhoisi.desLejetsssurdeuxconnprincipauxtidomainesid'insertionetsontoptdeslejetsdomaine?spatialDansetpremi?relesladomainesositiontransform?s.pLestsm?thoosandesl'obd'insertion3Dsonestthang?e.?galemenatcat?goriedivis?essursurd?placemenlaspatiauxbasepd'autrestscrit?resl'obcomme3leoufaitld'ad?formationvd'autresoirrimitivbconstituanesoinlesoujetsnonquedesoitlle'obspatialjetdans3DdomaineoriginalM?tho(m?thobadessnonl'ordonnancemenadesveseusurgconnectivit?llaesologieoupaivcat?gorieeugles).teSidesseulemen?thtdesquelquesquiparam?tresosensonsurtcemenn?cessairesdespesourobl'extractionoudulamessage,dilacationm?tholadeouestcaract?ristiquesaologiqueslobo3Drsmarquer.ditemosemi-asonvpriseseugle.compteDesg?n?ralm?tholedesspatial.to-cettetalemendestdesainsertionvteuglessurpdeseuvaueneautcn?cessiterconstituanl'utilil'obsation3D.dhik'unewclefetsecr?te[ICA02]posenourdeuxextrairedesletatouagemessageacacth?.moDansdeceganisationcas,donn?eslad'ins?rerclefmessagsecr?tecacestLaind?pm?thoendanmotedansdulistecondestenalorsulacacm?thoh?momaisl'ordre?galementripletstpdetsl'obtjettriangle.3D'luilm?me.orithUnealgorithmetatodeagtatouageTdoitStrippelingouvoloirquenc?tre(TSPS)coOhnhinal.ubas?deuntouthangemenletopmonde,[OMA97].m?meous'ilins?rerutilil'informationsenivuneduclefcetsecr?te,panoseded?connecterrespneecterdeleduprinciporiginal.epremi?redepKercdekhosconsiste[Ker83].cDansdanscetmaillagearticle,unenousdeprop?partosonstriangledenot?eLeclasserAlesdem?thoadesded'insertionetdemessagedonn?esins?rer,cabandech?ese
e
destdeg?n?r?e.rqu?e.Lefacescdonchlo'obiinitialxleduetitstriangletsuivvansommets.ts'applique?deradejouterdedansmalatbandvessecertainesfait?enonsfonctionmessagederilatrianglesvdomainesaleuruduitsbitindecapacit?message?t?e?duinlas?rertetaugmendug?n?resensdudeect?eparcoursclassecositionhoisiadjouteratntenansLesleetrianglen(horaireetoug?om?triquesanlatiphoraire).lCelaonpmaillageermett?rieuredonacestd'indexerptoutes3lesCettear?tesv?que1triangleouour?les0tenestfonctionincondecetteleursonsenslledelespfaitarctreouusrsplus,dans3ledetriangle.cetteLeses,ar?tesnotersuivtsaoriginalnCetesosenempruntst?es,cesetnedonculesinitialestrianglesxg?n?ranquetfoncettemaisbande,hierssoinitiales,nsttcsurhoisies3Dentatouagefonctionladulamessageencore?Conins?rer.pr?senL'?tapdomaineeeutsuiv3anoirteourdeunel'algorithmeduconsisteLa?m?thod?connecter2cettetriangle,bleasnsondebdethtriangleseutduunemaillageduenedupliquand'uteut-?tretousfois.les?sommetsm?medealainitialbande?es,saufdesceuxtiqueded'insertion.l?nien'ar?terstrianglesdepdesermettanrattadecretroetumarqu?esvblesertriangleleumessage.plusLeconmaillagelatainitial.toupropri?t??desseplusretrouvbezonedoncconclusionarevm?thoecounouvtroula?plapsurfacejetrecouvincertgparendanladesbandededeptrianglestairesconpluparttenandestfragilesletmessage.manipulationL'extractionhierdulesmessagequesedefaitparenccd?vhercSectionhanpartietcal'ar?teermettende?manipudespuistenenlesparcouranttalal'obbanderadedtriangles.desLesmoinconl'obvseconde?niend'algorithmetsbas?emadicationjeursdede3D,cetteositionm?thotsdenormalessondesttquepremi?rel'obquijetdansestcettetrou?cat?gorieetdansqueetdesar?tesomametstsontestar?teramaillagejsiobu4t?s,ge.donccapacit?lacettetaillededudecbhierparaugmensaufte.ourDetriangleplus,dannouslequelpbitsouvtonss?ranoterles.quem?cetteoinsertionpestatr?soirlofortecaled'insertiondansfaitlel'?tapsensdeo?ivisionlenmessagepins?r?r?pnplusieurs'estPpasl'extraction,dius?partirdanslatoutclef,ledeuxmaillager?tesdetrianglel'obsonjet,retrouvetensuitequ'ilparcoursesttrianglesfacileidende?repphase?rerLesdansvletscjeuhierdelesm?thosommesontsquequisommetsonttjout?s,?t?ladupliqu?sietdudonchierdete,retrouvqueerzoneslesonmessagevisiins?r?.duMaoqu'unetmarqu?al.qonattrianglesd?vpeloppcar?tenunedansm?thosurfacedetriangled'insertionDeconsistanlatde?oisinageafacesjoutern'estdesresptrianglesenplordureuslapmaetitsEn?del'inpt?rieurmi?redesdetrianglesdinitiauxndeul'obpjetons3Dque[MSI01].pAdesvoineccomcetteosanal'obp3Dproestchhe,nc?e.hacunpetdesm?thoar?tespropd'unttriraadesnoinglesuppl?meninitialetestadivis?edeenm?thodeuxsonar?testr?sparetler?sistensommetpasd'unlapdetitctriangleconints?r?.donn?esLetelleratiol'inenersiontredeulesligneslongueursexemple.desapprodeuxhesar?tesnousainsieloppfeno3rm?estestdutilis?cettept?gorieourpr?alisertl'insertionr?sisterd'unlablationit.cPconourainitialisertledonn?esprodiusencessus,ledeuxdar?tesnd'untouttrianglejetsonnetjoutencpashoisiese?M?tholbas?es'aidedesd'undicationsGNPdeAjet(G?n?rateCetteucat?gorededeNomestbressurPseudo-Al?atoires).moApr?sdeleg?om?trietaltouagejetdecommelapderni?redesar?teoind'unoutrilesadesnougfaces.ltrairemene,?c'estalecat?gorietrianglet?e,vneoisinque?lecettespatial,ar?te,secsideilpexistes'appliqueretlessispatialiltransform?s.n'aChaquepasd'und?j?doit?t?vtatou?,exactemenquideuxestadjacenparcopuuneruinanaudeetconseuletinc'estuernel'insertionorduredumaillage.mess0
1
pcosi-hial.ets?lectional.maispropmaillageosengrammesth?esdi?renmani?reteslapla-m?thoYindes'informationdellagetatouageetdanssecr?te.lexdomaenipropnehispatial,aucommedianledomaineTm?thoetrpropahededranalysenaldesVsectionolumeparcoursR[Watioes(TVR)caleetjetlelesTLariangletSimilaritycelui-ciQuadruplede(TSQ)jet[OMA97].desLeondelettesTVRdeutiliseunlebas?rappparortutilisedesdevhi?rarcolumesustedetsdeuxdest?tra?dres.m?thoDansaucetteencm?thor?cendelalesestt?tra?dres?utidlis?sins?rersonstlaplaciensform?stparBenedensunedear?tetetleslesnodeuxlatriangleseincidenmarquets.sLevirtuellesparcoursdomaineduosengrapheutilisedeaconnexit?passerrep[OMT02].osedesur?cunins?rearbrededetsrecouvremeosennvtL'algodesositionp3Doinetts.parLespar?tesosandeWl'arbrem?thoconstruit?servunenettt?r?solutiong?n?rertetd'ondelettes.?ror?f?rencerbas?eslestt?tra?dresmenainsiyquepropleurDeuxordredomainede5p[MC03].arczonesouparrs.duConcernand'unetm?tholaWm?thovisededonn?esbas?easulongueursrvlecTSQ,molacourburecongurationl'obg?om?triquepestuneconstitu?etatouagedeenquatreNURBStrianglesdiandonoidstecteursl'unsestpr?servcenglobaletraldeetetsertd'ins?rer?plussignaleralajetpr?sencedesd'information?escacDansh?e.OhL'unal.deunesesuvmoisinsducondetianendomainetfr?quenl'indexledulatriangleKanaiutilis?unepositionourmaillageins?rerenlelebitoidsducomessage.delettesLesal.deux?galemenautresquivdansoisinsondelettesrestanthmets,uneservultir?solutionenl'obteloppalternativoemen[GSS99].tprop?etenregistrerdel'informationins?rerutile.lesL'insertionbassesdesurfacel'inetformtationdeest[WLDB07a].alorsneeectu?eenenromoattaquesdiantatotcapacit?des?paireseauxdemarappmoortsnormedeeciendistancesetdeslescot?sri?t?sdesdetriangles.lesL'algorithmelesVd'?treertex[AMC07].FlouneodededeaBenedenspar[yBen99ade]dansreptoseWsuderbaselaLamodesdicationd'insertiondefaitelaundistanceuniquedesmaillagepl'aideoincleftsLaadmissiblesdeauecenagnertreag00]de?masselesdecacld'obnjet.lesUnerelativsecondedesm?thoecteursdelodeauBenedensenTdianrianglelaoloodedjet.utilisealesroinformationsos?dm?thoedeconnectivit?d'obet3Ddeutilisang?om?triedespetourmog?n?rertunpparcoursetsurvledemaillageeuddedel?'oberjetg?om?trie[Ben99b].[Ben00].Dansm?thocettedm?thoLeedeal.l'insertionosedulamessagenonsedirectemenfdanil'obt3D,endansmoimagesdiand?rivtdela[LCK02].pleositiontransform?,desbucpetoinproptstanm?thod'alt?rerqlaihauteurunedesatricetriangles.cienneLamaillm?thogedel'obprop3Dos?edeparduBorsspatialutilisedomainelatielcongurationDansg?om?triquedomaineloondelettes,calem?thodesdepetoinutilisetsdpompourensdu?etll'informationecmotitobitnpnerfaibledescertainszoneseciend'insertiond'on-[Bor06].[KDK98].Laetzonepropesttrepr?sentt?ealgorithmepartraunaillesommetleetdestous[YPSZ01].lesritrianglesestconsurtigusd?compamvduecdeunjetvd?voisinage?ellipso?dalGuskautourvdeal.ceLasommet.dePos?eourPrauncoal.derl'espaceuneKernelvouraleulrdans?compbutes,fr?quenceslelasommet[PHF99].estangd?plac?al.?osenl'ext?rieurunededesontatouagevhiqueoisinageGr?ceetupd?compourtioncoondelettes,dertatouageunebvauxaleurg?om?triques?unOhuageilhauteestsond?plac?appliqu?s?di?renl'innivt?rieur.deDansdulaim?thoendediandelesCasyrecoettsMacq,Alfacel'insertional.esttfaitepenpprodesjetandesttatouagelesursommehisto-tetd'unutilisentrianangrobusteld?coupageeR?cemsurt,sar?f?rencebasetestsettenpregardanbthmarksi?t?celle-cios?appBennouraDugelarti[BD07].en?tatstl'art?tslalemoiti?compl?tendroitecetteou[RAM07,gaucLDB07b].heG
a b (a,b)
G A
A
trianglesdeuxanalysenouvtanellesim?thoestdesalorsdetdissimconnexit?ulationtonsdecommendonn?esM?thodansledesnousobcjetszones3D.oncernNospremi?rem?tholesdesd'insertionseumbasenttn'existesurunclefmoded?lel'ob3Dderepr?senst?endparpundenfaiteuageillustredelpcommenoinLatstrons,ettrainunehierlisted'und'ar?tescettecorrespdesondant?tunauestmaillageformetriangulaireudealatesurface.laL'id?eleprincipalecaliserdesl'Ad,eerturbudexd?partm?tholadestesttesdeettrouvtroisi?meermessageettdes?lectionn?es.syncg?n?ralhroniserSectiondAemonszoneszonesvparticuli?resdepSectionouvlansoumisestla?tremessageutilis?esArbrepnousourcouplesins?rerSoienlecemessage.coupleL'insertionar?tedeundonn?esdanss'appuiecsurCelamon'estdicationestde6laestcopartirnAnexit?rdcompes(Aar?tesjetdanssecr?desermet,zones?res?lectionn?es.deCespmod?partdicationsDuonAtr?organisationpneourpcons?quencelodepmotdinequeersecr?te.ladoivstructureondredescontriangles?construitsl'Adanslaceszone.zones.eCesl'insertionm?thoCelle-cidesmodeconnexit?dissimlesulationFigurepr?sensctenetde.l'anousvd?nitionanettageconstruction.deSectionnes?lectionnerpasanmohroniserdierleladepcacositiondansinitialeNousdes3.1.4,psoinsontsdesdug?om?triques.mo3.1.5d?leextraire3D.unCetmarqu?.intv:agrapheribleasommetsnunetsectionsursommetslaquiprelation,osios?estiondoncdesupSoitononisansngraphetspasnousreli?pdeermetrespdpropri?t?seunerendre?e,l'insertionplusrobusteuneauxjout?e,transformationsunanesparcourirdegraphetobtenyp?ed'unerotation,secr?te.translationpourticd'unehangemenentosand'?cprincipalehCP)el'obl3D,le.clefLatedi?rencependanstrereplesdedeuxjet,m?tholodeslepr?senoint?edesdeestCM.lafaitmani?recettedeCPs?lectionnuneedurhieretpdeesyncahronilasercalisationlescezonesod'insertion.nAlorsdequequilad?ppremi?redoncm?thodede,clefpr?senLest?ed'insertionSectionen3.1,r?ps'appuie?surlusieursuntrainarbreduescouvranlatdeminimCMum?(Ag?om?trieCM),lalaLaseconde?tapm?thocde,epr?sendut?eelle-m?me.Sectionest3.2,enutilisedianunlaaxedessurdanslequelzonessonLat1prolejet?sh?malesdcencettetresm?thodesEnzones3.1.1d'insertion.d?taillons3.1aInsertiond'unbas?eCMsupr?senrsaunNousarbretrons,couvran3.1.2,ttminimlesumd'insertionDansdecettesyncsectionanousecpr?senmessage.tonsm?thol'approd'insertioncdonn?esheh?esd'insertiond?critedeladonn?es3.1.3.cacmonh?esSectionbas?equesureunzonesarbs?lectionn?esretcouvran?tconminimtesumEnn,(ASectionCM).d?critCettetapprolecdanshecest3Dcomp3.1.1os?ecouvrandeminimtroisD?nition?tapsoites.unLaform?premi?reensem?tapdeedeconsisterepr?sen?tconstruirerelation.untAetCMdeux?departirgraphedessonsommetseninitiauxleduDansmopropd?leest3D.uneLdagrapheseco.n3degraphe?taporieneconnexen?cessitecycle,deceparcouririll'Adoncd?taillonsdequiheminermette?revsommetsurm?meCMpconstruitdeanenirdeces?lectionsommet.nergraphedesectezonesdeuxp:ourSilar?te'insertionenlevdesildonn?es.alorsLeconnexe.pSioinar?tetadecelle-cid?partalorsutilis?cycle.pourG A
G G
G G A
G
G A
G
A G
A s G
A s E s
A F E F
G A
x F E
x F
ar?tecouvranL'algorithmetmounoin.tsIlCMs'agithaqued'unsoitgraphe1partielCMquistiquepplusoss?denedlesSoitmti?mesmsommetseque3Dmoinssyncet?gdpr?senoournPrimtivl'enminimsemfasseblebas?edesiquemerelationsrelationets.statcetteinclustdansermetceluir?organisationdeshierrelationsparticularit?deSectionaua.nousLerco?t?duConstructiongraphepexistedescorrespsonondde?imlasous-graphesommel'ar?tedcalemeneesptoutessolutionlesvidepcondde?raos?tileodenlesestdestousar?teshaquede?ilp.ar?tesSila,Fig.estformerunsommetarbrepcouvranletl'obdC'estedesgraphenousdonantlelaecsomme3D.desyptond?rationscaracdeourseslesar?tesSectionestl'lailplusalgorithmespnetiteCM.vualeurl'algorithmeparetrapp[Kru56].ortP?progcelletdedetoushoisissanlespautreslarbres?couvrane,ttdedele[Pri57].,suralorsunourd'insertionestcommeappdeel?alorsarbrtem?thocl'ensemouvrsommetsantvdeg?n?ralepl'ensemoidssommetsminimumd?partdevide,Ptienetsommetsnot?AAeCM.aDanstellenotresoitm?thominimdetoutesleypsommetoidsosanutilis?l'autrepCeciournecalculercyl'AAinsiCMaestdeslaoindistancedanseuclidienncedeenjettre.lescettepforteoinAtsquedeutilisonsl'ob3.1.2jetde3D.hroniserLamessageparticuvlarit?led'und?leANousCMappuestonsqu'ilalemenestsuunique,cetteilt?riexistepcepinsendanrertdonn?esunet?eam3.1.3.bigu?t?dedansAles:mexiste?thlusieursopdescodestruireconstructiAoLesnconnlorsquesuntsommetdep[Pri57]oss?del'algorithmedeuxKruskalar?tesdedem?merpconstruitoids.ressLemenaunm?thoAdeuncchoisittl'ar?tedequ'elleoidsrenconumtreoentpremiercdans?tapsonenparcours?randesqu'ellesommets.partieSilal'ordonnancemenglobaletAudes?part,sommetsestdansetlesommetcdehierestesthoisimopdi?talorsd?part.l'AestCMunluinaussicomppdeourrait.?trelamobdi?.desPenourapalierec?danscette,anmbbigu?t?desunrestancalculAudeodistancedoncenettreconlestdeuxlessommetsdedes.deuxcar?tes?tapidenunetiestqjout?euPr?senesqueetar?teledecenoidstreudeparmimlesasseadeanCM.unsortl'ensemcomparbretdansestet7dansfa?on.l'ApCMdeestpasbiendeuniqueclquelle.quelesoitll'obdejetbleestetutilis?.ins?r?DecetteE F
A G
A
s
0(s,s) s A
0 0s A (s,s) A
Cep?nopartird?ledudenuneuagesdedansp?oin3Dtsnomilparticuli?reslustr?troisFigureNous2.a.oinlaL'algorithmepr?sendeoKruskalsecconstruitmoprogressivauemendetd'eectueruneudssous-graphezonesPrimeudsdeedequatreendoivtrianntdesd'abmessage.ordzol'ensempbdisple?desclefar?tesmessageselonDleurdepsommetsoidsletobtenensuitehercenCess?lectionnanttquicellest?quideneetformeronhacuntdanspaslesdepcycletrodanshacunl'algorithmeaux[Kru56].trianglesPar?teouruncela,doncleslsod'insertionmmetsutilisesond?tect?est4cservirhoisisGNPundansparobtenund'uneetL'utilisationtri?sappdanssurl'ordredanscroissan?letLselondelaestpbreond?rationledesensl'ensemtubleCMdesdesar?testquialiendetonuncorrespsommetdesdel'Aauxoss?denautres.commeP3.ourtcsommets,haquepar?teautresr?sultatreli?sununetehercpr?senmaillage2.bformetri?etrianglesilzonefautrveuds.?rierssidelaceslistetdesnovzone.oisinsudedoncFigureunedansetLaL'ensemestrepr?sendzonesit?renbitstem?thodetilis?ecelleSectiondetvide.esestsyncdanst,blec.?galemenSisemenceaucunrsommetanvleoisinjn'estestcommuun,partiralorsclefl'ar?ter?te.l'ensemd'unequandnouss'arr?teorteL'algorithmes?curit?.leestins?r?alejout?ed?3dans.Ainsielebrebresenssomlectureest?galplusnomsyst?mdeestdans4moUne3D.queplus.nom(a)de(b)metsFig.grand2leea)prot?g?Nuage.defoispleoindetsecinreitiall'A(453estpu,oinzonests),sonb)recCalculh?esdenl'Al'insertionCMdonn?es.azveecparticuli?resl'ondena?lnogdeorithCMmepdetPrim.ar?tes3.1.2repr?senS?lectionFigureetCessyncsonhronisationform?esdesquatrezonesund'insertioneudLa?resynctroishronisationnodeslsdonn?esccacparh?esar?te.estcobtenhonsueleendrepla?ran3Dtdeuxdesinclusconnexit?slaparticuli?resform?epr?senatescesdansnol'ALesCM.iUnepftsocidestrianglesl'AenCMappartenirconstruit,quatredeuxeudsplahasesDeuxsonatron?cessairestanunedecommsyncdanshroniserzoneleformemessagequadrangle.?bleins?rer.quadranglesLatepremi?relesphaseoconsisteson?ins?r?sd?niresledusensLadedelectureudeetl'At?eCM.3.1.3Endirectemeneet,cesl'arbrenestparticuli?resuniqueetmaishronis?es.leendanparcoursnousdeLacelui-cilefd?peutendtdudesompmetudeund?part.ADansdenotreerserappromessagecl'obheetce8sommet0
1
dier3.1.4ourques'unepaspartiepardebitcespr?senquadranglesdenequatrepdueutFigurepassur?treneutiletis?etpcetteourl'Ar?aliseretl'insertion.desEns?lectionn?eet,zonecertaineseudzonesnnet?r?pdesondenvtdicationpasm?thoammetsuourxecontraintrain9tessondeuemlsandzones?esinparquadranlacomm?thodansdel'insertiond'insertioncompettroisd'autresr?alis?eneunepl'AeuvAuen?tconstruitepassup?trederetenNotonsueslapdeopupr3D.desimpraisetoAnPsimpdequadranglesnnexol'aidenCesinform?esvisiunbilit?pdenol'insertion.cL'Aar?te.CM,tdePparunsadansconstruction,lvexaminonsaunenoustrianglespquadrangle.ermettrepdepr?senr?sisterelleauxd'untransformationsvanesL'insertiontellesd?taillonsqueconstruislesl'ar?terotations,deuxlesinitialetracommen4.bslationstraireoud'unlescommctriangleshangemenfa?onts?tred'?cositionhelles.l'ar?teCeciCMestFigurerendulaplieuossibledugr?cedans?CM.notreem?thodededierd'insertiondesquimonepmounedietepassynclappleosilorstiondudesconsommetsdededesl'obsurjethoisis.3D.cLet?nom?bdereCM.dezoneszonests?lectionn?esded?psommets,endnodudnom?rebretroisdeeudspreli?soinhacuntsunedCeseconstituenl'obdoncjetquadrangles.3D,ourdess?rervbitaleursmessagedesunseuilsgpeournousll'ar?teemsdddeuxi?reninclustesleconUnetrains?lectionn?etesourmaisest?galement?et4.a,duestmaillageos?eglobalnodeal'obecjet.ar?tes.Nousd'unmon?trons,estSectionen4,acomtbiencommdedeszonestrianglesenl'ar?temodeyCMennespr?sensFigureo.ncontps?ll'insertionebitSection,ctil'ar?teounendeuxn?esestendefonction?depastousenceserpparam?tres.aFig.ec3initialel'AExemplecommedet?zones4.c.formanquetmodesaquadranglesdanss?lectionn?esconnexit?pmaillageournonlacellesyncl'AhronisationCettedesddonn?esd'insertioncacermeth?es.ne3.1.3moInsertionladesositiondonn?essoCettedupartied?lepr?senCeteoinlaestphasenotiond'insertionortandespdonnla?eshronisationcacnoush?es.ermetDansreconstruirelam?meSCMecdtil'extractionomessage.nar3.1.2tre,nousm?thoad'insertionvoseonsconpr?sentest?lescommecnMotlalooncaliserilesduzonesd'insertionSc
Sc
Q P ,P ,P ,P1234 1 2 3 4
P P123 4
P P4 123
d P P P4 1 2 3
P P P234 134 124
Sc
Q min(d ) < S .1234 i c
i={1,2,3,4}
d4
derespnormaleecterduetetexpliquonsmaispnormaourquoiestcertainsb)quadranglesAuneunpd?tailloneuvtensurtresppasd?tredeutiligrandes?setit,parourtreins?rer3.1.4lesaudonn?es.aussi3.1.4onConprotrainomm?ndestesplanssurseraleseuilcthoixdesazonesdud'insertionceDansd'insertioncettel'obsectionseuilnousppetr?Soitspedenuntonsaulespconalorstrainmentesdistanceappliqu?esoinauxeauquadranglesCer?sultanlestspdesurl'?tap,e.desisyncesthronisation.tEnueet,s?lectionuneartiepartie(b)deccesd'insertionquadranglesd?trimennvisu'esttrairepasserautilis?elappourseraeectuer3D.l'insertionterm?diairedecodonn?es.estCesleconcapacit?trainrendutesd?leconcernenquadrangletform?latscoplanarit?,surface.lavcon.vtemps,exeid?fautst?calcul?e.etilei-cirecouvremenjet?t.lConsurtrain.tes?parededucoplanacelurit?du:nilaerreurspderempijections?re,conmaillagetrainementenormalesestbitlancoplanarit?0,desquadranglequadrangles.uLeplusfaitdistancesdeamd'uno:dierestlaetconnexit?'undesCMdeuxgraphetriangles)formanFig.tUnundequadrangleapmocit?dieseraaussiaul'angletform?renduenel.treconcesplusdeuxseuiltriangles.pPplusarcapacit?cons?quenserat,etitel'insertionmoinsded?grad?donn?esjetsurPunl'inquadrangledunonncoplanaire,aecter?glageladoncsurfaceossibetendonclaled'insertionrendulevisuelvisueldumomo3D.d?lele3D.lesDeSectionmani?redesid?aleoinilsneNousfaudraitlains?rereaulenimessagevisuelqueDansdanspremierleslaquadrangleslsNtrictemplanendestestcoplanaires.LeCepoendannt,maislaestquanprotit?orthogdeaquadrangleser?ptondanlatNstrictemenLatquiaulacrit?rejectiondepcoplanarit?testdetr?sNliplanmit?e.vAnestd'augmenauter.lacalculcapacit?distanced'insertion,eectu?nouroproudesamenerins?ronseutdansetnotre1.approectivcthelesunauxseuil??d'untessertiontrainIpc)la?d'uLequadrangleneillustr?reten5.ques?lectionn?s.laCegrandeseuilesnouscalcul?espinf?rieureermetud'obtenirbitunpr?alablemencompromisx?enInsertiontrequadrangle,laretencapacit?sid'inseulemensertionsietdlaetqualit?l'Aduissumoded?leP3D.aPlus4ce(c)seuil(1)seraexemplegrand,calculplus(a)ladeourtol?rancecoplanarit?surnlaestcoplanarit?Figuredes10quadrangles

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.