Kabsch algoritm

Kabsch algoritmi kutsutakse ka partial Procrustes superimposition. Algoritm leiab näiteks kahe punktide hulga vahel joonduse, mis on arvutigraafikas vajalik, kuid on ka muid kasutusalasid. Paistab lahe algoritm, seega kirjutan üles. Esialgu tundub väga teoreetiline algoritm, sest kasutab sellist asja nagu covariance matrix, mis teadagi on see maatriks, mida tegelikult üldse kasutada ei saa. Lisaks veel singular value decomposition, mis on ju põhimõtteliselt eigenvaluede leidmine, mis on samuti kirves.

Algoritmi jaoks on alguses kaks hulka vektoreid, mis mõlemad on maatriksi kujul(P ja Q). Iga rida maatriksis on üks vektor(või punkt vms.).  Kusjuures igal vektoril on paariline, st. et on teada millist vektorit millisega võrreldakse.

Esiteks tuleb nende vektorite koordinaatidest nende centroid lahutada, koordinaatsüsteemiga joondamiseks.

Teiseks tuleb covariance maatriks leida, see on maatriks kujul A = PTQ .

Kolmandaks tuleb maatriksi A SVD leida. A = VSWT . A on sümmeetriline, seega on võimalusi palju. Näiteks Jacobi meetod, mis annab kohe kõik eigenvalued ja vektorid. Hea on, et mingit inverse‘i ei pea leidma, sest lihtsalt transpositsioonist piisab.

Neljandaks saab leida rotatsiooni maatriksi U, mis joondab P ja Q. U = WDV T , kus D on NxN identity maatriks. N on vektori suurus.

Ma leidsin sellise kirjelduse wikist. Võibolla on midagi paremat olemas.

UPDATE:

Kirjutasin veits koodi selle algoritmi testimiseks, koodi on palju, ei hakka postitama. Algoritm on väga täpne, mida ma esialgu ei uskunud, olles lugenud SVD jm. kasutatava kama täpsuse kohta. Ma arvan, et seda tänu heale SVD funktsioonile, mille sain mingist LAPACK-i klooni moodi teegist. Lisaks veel häid linke(otsisin midagi selle algoritmi kohta, leidsin enda saidi):

http://nghiaho.com/?page_id=671

Põhimõtteliselt võib seda algoritmi muuta, jättes mõne sammu vahele kui vaja vms. Ma ei tea veel kuidas paremini skaleeruvaks teha see algoritm, võibolla ei saagi midagi eriti teha. Olen lugenud, et hajusate maatriksite jaoks on hajusam SVD,  mida võiks proovida. SVD-d kasutatakse umbes PCA moodi , põhimõtteliselt jätad ainult suuremad numbrid ja vastavad vektorid alles. Selleks on jälle vaja eigenvalue-d leida..SVD peaks küll olema läbinisti uuritud ala, igasuguste variantidega, vaevalt et hätta jääb. Maatriksite korrutamine on ka üks asi, mida veits kiiremaks saab. Tõsiselt handycapped, kui oleks vaja midagi suuremat reaalajas liigutada. Õnneks kolmnurga liigutamiseks on kolme punkti ainult vaja.

 

Advertisements