science >> Wetenschap >  >> Elektronica

Ontdekking van een nauwkeurig en veel efficiënter algoritme voor problemen met de registratie van puntenverzamelingen

Deze animatie toont de evolutie van vormvervorming, als gevolg van de toepassing van het algoritme op de drakendataset. Wat betreft de gordeldierdataset, de rode vorm vóór optimalisatie werd gecreëerd door niet-lineaire vervorming van de blauwe vorm. Beide puntensets zijn samengesteld uit 437, 645 punten elk. Krediet:Kanazawa University

Een puntverzamelingsregistratieprobleem is een taak met twee vormen, elk bestaande uit een reeks punten, om de relatie van individuele punten tussen de twee vormen te schatten. Hier, een "vorm" is als een menselijk lichaam of gezicht, dat lijkt op een ander lichaam of gezicht, maar morfologische diversiteit vertoont. Als we het gezicht als voorbeeld nemen:de centrale positie van de pupil van een oog verschilt per persoon, maar er kan worden aangenomen dat deze overeenkomt met die van een andere persoon. Een dergelijke overeenkomst kan worden geschat door de ene vorm geleidelijk te vervormen zodat deze op de andere kan worden geplaatst. Het schatten van de overeenstemming van een punt op de ene vorm met een punt op een andere is het puntverzamelingsregistratieprobleem. Aangezien het aantal punten van één vorm miljoenen kan zijn, schatting van correspondentie wordt berekend door een computer. Niettemin, tot nu toe, zelfs wanneer de snelste conventionele methode werd gebruikt, het kostte veel tijd voor de berekening voor de registratie van ca. 100, 000 punten. Dus, Er is gezocht naar algoritmen die veel sneller een oplossing zouden kunnen vinden zonder de nauwkeurigheid aan te tasten. Verder, voorafgaande registratie voordat geautomatiseerde schatting een voorwaarde was voor de conventionele rekenmethode, dus algoritmen die geen voorafgaande registratie nodig hebben, zijn wenselijk.

Prof. Osamu Hirose, een jonge wetenschapper aan de Kanazawa University, heeft aan dit probleem gewerkt. In zijn studeerkamer er is gekozen voor een geheel nieuwe aanpak; een puntverzamelingsregistratieprobleem wordt gedefinieerd als maximalisatie van de posterieure kans 1) in Bayesiaanse statistiek 2) en de gladheid van een verplaatsingsveld 3) wordt gedefinieerd als een voorafgaande kans 4). Als resultaat, er is een nieuw algoritme ontdekt dat een oplossing kan vinden voor een typisch probleem met de registratie van puntenverzamelingen, zelfs zonder voldoende voorafgaande registratie. In aanvulling, door sommige berekeningen van dit algoritme te vervangen door benadering, puntsetregistratieproblemen kunnen drastisch sneller worden opgelost dan conventionele methoden. Bijvoorbeeld, voor tweepuntsets bestaande uit ca. 100, 000 punten elk, toepassing van de huidige methode was succesvol in het voltooien van zeer nauwkeurige registratie binnen 2 minuten, terwijl de snelste methode die publiekelijk beschikbaar was ongeveer drie uur duurde. Ook, zoals weergegeven in de afbeelding, de voorgestelde methode heeft met succes de "dragon" -dataset geregistreerd, waar beide puntenreeksen waren samengesteld uit 437, 645 punten elk. De rekentijd was ongeveer 20 minuten. Hoewel de huidige snelle berekening gebruik maakt van benaderingen, de nauwkeurigheid van de registratie wordt niet merkbaar verminderd, zoals aangetoond door numerieke experimenten.

Door het algoritme te gebruiken, nieuwe CG-tekens kunnen automatisch worden gemaakt, en daarbij, het kan een arbeidsbesparende techniek zijn voor CG-ontwerpers. De tweede afbeelding toont een voorbeeldtoepassing van het algoritme. Bronvorm (a) en doelvorm (b) werden verkregen uit een openbare database en gebruikt als invoer voor het algoritme. Vorm (c) is het resultaat van de eerste registratie, waaruit blijkt dat de bronvorm vergelijkbaar werd met de doelvorm, waarbij de kenmerken van de bronvorm behouden bleven. Vorm (d) is het resultaat van de tweede registratie, waarbij de te vervormen bronvorm dichter bij de doelvorm wordt weergegeven.

  • (a) Bronvorm. (b) Doelvorm van registratie van puntenreeksen. (c) Vorm na de eerste registratie. (d) Vorm na de tweede registratie. Krediet:Kanazawa University

  • De rode vorm wordt gemaakt door een niet-rigide vervorming van de blauwe vorm; de twee vormen kunnen niet op elkaar worden gelegd door vormrotatie. De meest linkse vorm vertegenwoordigt de initiële plaatsing, waaruit blijkt dat de voorlopige registratie van puntensets niet is uitgevoerd vóór de geautomatiseerde registratie. Het optimalisatieproces wordt van links naar rechts weergegeven. Krediet:Kanazawa University

Het belang van registratieproblemen van puntenverzamelingen is te wijten aan hun brede scala aan toepassingen op het gebied van computer graphics (CG) en computer vision. Persoonlijke authenticatie door gezichtsherkenning die op smartphones wordt gebruikt, kan worden geïnterpreteerd als een toepassing van puntensetregistratie. Verder, het mengen van de driedimensionale vorm van bepaalde twee personen, genaamd "morphing, " kan worden uitgevoerd via de registratie van puntenreeksen. er is een bekende studie die de restauratie van een driedimensionaal gezichtsmodel van wijlen Audrey Hepburn op basis van een enkele foto mogelijk maakte, die een techniek gebruikte die kan worden geïnterpreteerd als registratie van puntenverzamelingen. Daarom, omdat puntverzamelingregistraties met een grote verscheidenheid aan toepassingen nu met een zeer hoge snelheid en een hoge nauwkeurigheid kunnen worden uitgevoerd, de verwachting is dat de in dit onderzoek ontwikkelde methode als kerntechnologie in dit onderzoeksveld zal worden gebruikt.

Anderzijds, de methode zou nog verbeterd kunnen worden. Hoewel het opmerkelijk sneller is dan de conventionele methode, rekensnelheid kan een probleem worden wanneer het aantal punten in een puntenset miljoenen bereikt. Prof. Hirose ontwikkelt methoden om zo'n groot puntenverzamelingsregistratieprobleem binnen enkele minuten te kunnen berekenen. Voorlopige resultaten zijn veelbelovend voor succesvolle verdere ontwikkelingen.