Opdagelse af nøjagtig og langt mere effektiv algoritme til problemer med registrering af punktsæt

Et problem med registreringsproblemer er en opgave ved hjælp af to former, hver består af et sæt punkter, at estimere forholdet mellem individuelle punkter mellem de to former. Her, en "form" er som en menneskelig krop eller et ansigt, som ligner et andet legeme eller ansigt, men udviser morfologisk mangfoldighed. Tager ansigtet som et eksempel:den midterste position af pupillen i et øje varierer afhængigt af individer, men kan antages at have en korrespondance med en anden persons. En sådan korrespondance kan anslås ved gradvist at deformere den ene form til at være overlejret på den anden. Estimering af korrespondancen mellem et punkt på en figur til et punkt på en anden er det punktsætte registreringsproblem. Da antallet af punkter i en form kan være millioner, estimering af korrespondance beregnes af en computer. Ikke desto mindre, indtil nu, selv når den hurtigste konventionelle metode blev brugt, det tog meget tid til beregning til registrering af ca. 100, 000 point. Dermed, Der er søgt algoritmer, der kunne finde en løsning langt hurtigere uden at påvirke nøjagtigheden. Desuden, foreløbig registrering før automatisk estimering var en forudsætning for den konventionelle beregningsmetode, så algoritmer, der ikke har brug for foreløbig registrering, er ønskelige.

Prof. Osamu Hirose, en ung forsker ved Kanazawa University, har arbejdet på dette problem. I sit studie, der er taget en helt ny tilgang; et punktsætregistreringsproblem defineres som maksimering af posterior sandsynlighed 1) i bayesisk statistik 2) og glattheden af ​​et forskydningsfelt 3) defineres som en tidligere sandsynlighed 4). Som resultat, der er opdaget en ny algoritme, der kan finde en løsning på et typisk punktsætregistreringsproblem, selv uden tilstrækkelig indledende registrering. Ud over, ved at erstatte nogle beregninger af denne algoritme med tilnærmelse, punkt sæt registrering problemer kan løses drastisk hurtigere end konventionelle metoder. For eksempel, for to punktsæt bestående af ca. 100, 000 point hver, anvendelsen af ​​den foreliggende metode lykkedes at gennemføre en meget nøjagtig registrering inden for 2 minutter, mens den hurtigste metode, der var offentligt tilgængelig, tog omkring tre timer. Også, som vist på illustrationen, den foreslåede metode har med succes registreret "drage" datasættet, hvor begge punktsæt var sammensat af 437, 645 point hver. Beregningstiden var cirka 20 minutter. Selvom den nuværende højhastighedsberegning anvender tilnærmelser, registreringsnøjagtigheden ikke reduceres i et mærkbart omfang, som vist ved numeriske eksperimenter.

Ved at bruge algoritmen, nye CG -tegn kan automatisk oprettes, og derved, det kan være en arbejdsbesparende teknik for CG-designere. Den anden illustration viser et eksempel på anvendelse af algoritmen. Kildeform (a) og målform (b) blev hentet fra en offentlig database og brugt som input til algoritmen. Form (c) er resultatet af den første registrering, viser, at kildeformen blev magen til målformen med egenskaber ved kildeformen bevaret. Form (d) er resultatet af den anden registrering, viser kildeformen, der skal deformeres tættere på målformen.

Betydningen af ​​problemer med registrering af punktsæt skyldes deres brede vifte af applikationer inden for computergrafik (CG) og computersyn. Personlig autentificering ved ansigtsgenkendelse, der bruges på smartphones, kan tolkes som en anvendelse af punktsætregistrering. Yderligere, blanding af den tredimensionelle form af visse to personer, kaldet "morphing, "kan udføres gennem punktsætregistrering. Derudover kan der er en velkendt undersøgelse, der muliggjorde restaurering af en tredimensionel ansigtsmodel af afdøde Audrey Hepburn fra et enkelt billede, som brugte en teknik, der kan tolkes som punktsætregistrering. Derfor, da punktsætregistreringer med en lang række applikationer nu kan udføres med en meget høj hastighed med høj nøjagtighed, det forventes, at metoden etableret i denne undersøgelse vil blive brugt som en kerneteknologi inden for dette forskningsområde.

På den anden side, metoden kunne forbedres yderligere. Selvom det er bemærkelsesværdigt hurtigere end den konventionelle metode, beregningshastighed kan blive et problem, når antallet af punkter i et sæt sæt når millioner. Prof. Hirose videreudvikler metoder til at muliggøre beregning af et så stort punktsregistreringsproblem inden for flere minutter. Foreløbige resultater viser et stort løfte om succesfuld videre udvikling.