En effektiv algoritm för isometry-invariant matchning av ytor presenteras. Nyckelidén är att beräkna minimi-förvrängning kartläggning mellan två ytor. För detta ändamål introducerar vi den generaliserade flerdimensionella skalningen, en beräkningseffektiv kontinuerlig optimeringsalgoritm för att hitta den minsta distorsion som inbäddar en yta i en annan. Den generaliserade flerdimensionella skalningsalgoritmen möjliggör både fullständig och partiell ytmatchning. Till exempel tillämpas det på problemet med uttrycksinvarianta tredimensionella ansiktsigenkänning. Gromov-Hausdorff avstånd  och isometrisk inbäddning Iterative-cloestpoint  och delvis inbäddning T han problemet med jämförelse mellan deformerbara ytor har nyligen fått en hel del intresse för mönsterigenkänning, särskilt inom områdena tredimensionell (3D) dataanalys och syntes. Det uppstår till exempel i medicinsk avbildning och 3D-ansiktsigenkänning (1). Den grundläggande frågan är hur man effektivt men exakt kan kvantifiera likheten mellan en given referensyta ("modell") och någon annan yta ("sond"), vanligtvis en böjd version av modellen. Vi skulle vilja fånga distinktionen av modellen och sonden inneboende egenskaper i samband med den metriska strukturen av ytan, samtidigt som ignorera de extrinsiska egenskaper som beskriver hur ytan är nedsänkt i det omgivande utrymmet och som ofta förändras medan ytan böjer. En deformation som bevarar ytans inre struktur kallas en 'isometri'. Vårt mål är därför att definiera en beräkningsbar isometry-invariant mått på likhet mellan ytor. Ofta är problemet ännu mer komplicerat, när sonden endast delvis är tillgänglig (se bild. 1 )............................................................................................................... Vi hänvisar till den senare inställningen som ''partiell yta matchning'' och till det fall där hela sonden är tillgänglig som ''full yta matchning''. Ett av de tidigaste försöken med isometry-invariant ytmatchning är den klassiska ''iterativa närmaste punkten'' (ICP) algoritm (2). Den tar upp ett särskilt fall av det partiella matchningsproblemet där endast stela (Euklidiska) isometrier är tillåtna. En effektiv metod för konstruktion av nästan isometri-invarianta representationer av ytor [kallade ''kanoniska former'' (CFs)] baserade på Euclidean inbäddningar presenterades i ref. 3, som en generalisering av ref. 4. Vad är det som händer? Detta tillvägagångssätt använde en flerdimensionell skalningsalgoritm (MDS) (5). MDS är nära relaterat till dimensionalitetsreduktion (6, 7) och kan utföras på ett beräkningseffektivt sätt. Euclidean inbäddningar används i teoretisk datavetenskap för att representera metriska utrymmen som vanligtvis uppstår från geometri av grafer (8). Nyligen använde Mémoli och Sapiro (9) en diskret probabilistisk approximation av Gromov-Hausdorff (GH) avstånd (10) för att jämföra ytor upp till isomerer. Deras metod är baserad på att utvärdera alla permutationer mellan två uppsättningar av ytprover, som är beräknings dyrt. Dessutom är GH-avståndet olämpligt för partiell matchning. Ett av de viktigaste bidragen till detta arbete är det 'partiella inbäddningsavståndet (PE)' som motiveras av Gromovs teori. För effektiv beräkning introducerar vi en förlängning av MDS, som vi kallar generaliserad MDS (GMDS). Nyckelidén är att mäta minsta möjliga förvrängning när man försöker inbädda en yta i en annan. Genom att använda GMDS kan vi hantera såväl fullständig som partiell ytmatchning; denna förmåga är en fördel jämfört med en enkel användning av GH avstånd. Tidningen innehåller sex avsnitt. Teoretiska stiftelser granskar den teoretiska bakgrunden av isometri-invariant ytmatchning. Vi definierar vårt PE-avstånd och visar dess relation till GH-avståndet. Nästa avsnitt, GMDS, introducerar GMDS och tar upp implementation och optimering överväganden. Följande avsnitt fokuserar på partiell matchning av ytor. I Resultat visar vi några experimentella resultat. Slutligen sammanfattar vi de viktigaste resultaten i slutsatserna. Låt S vara en jämn ansluten och kompakt Riemannian yta (2-manifold) med minimal geodesik C* S (s, s på) mellan två punkter s, s på S. Vi definierar den geodesiska avståndsfunktionen d S : S  på S 3  på samma sätt som d S (s, s på)  på längden{C* S (s, s på)}. För enkelhetens skull säger vi ''ytare S''' som antyder det underliggande metriska utrymmet (S, d S ) som induceras av den Riemannska geometrin av S. I vårt sammanhang uppfattas ytor från en synvinkel av metrisk snarare än Riemannian geometri; med andra ord, vi anser inte den Riemannska metriska tensor, men de geodesiska avstånd som det inducerar. I praktiken arbetar vi med provytor som representeras av finita metriska utrymmen. Vi använder följande definitioner: en delmängd S r  på S kallas en 'r-covering' (eller ''r-net'') av S om S  och Sr B S (s, r), där B S (s 0, r) {s S : d S (s, s 0 ) r} är en boll av radier r runt s 0 i S. En ändlig r-covering av S som består av N-punkter betecknas av S N r. Måttet på S N r antas vara den begränsade metriska d S N r (s, s på) d S (s, s på) för alla s, s på S N r. Vi hänvisar till r som '' sampling radie.''' En godtycklig finit provtagning av S som består av N-punkter betecknas med S N, där S kallas ''kontinuerlig'' yta och S N en ''diskrete'' en.
Bronstein m.fl. bädda in den inneboende geometrin av S i ytan Q med hjälp av generaliserade MDS REF.
Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching
{'venue': 'Proceedings of the National Academy of Sciences', 'journal': 'Proceedings of the National Academy of Sciences', 'mag_field_of_study': ['Computer Science', 'Medicine']}