Registrace množiny bodů - Point set registration - Wikipedia

Registrace sady bodů je proces sladění dvou sad bodů. Tady je modrá ryba registrována na červenou rybu.

v počítačové vidění, rozpoznávání vzorů, a robotika, registrace sady bodů, také známý jako registrace mračen bodů nebo skenování shoda, je proces hledání prostorového proměna (např., škálování, otáčení a překlad ), který zarovná dva mračna bodů. Účel nalezení takové transformace zahrnuje sloučení více datových sad do globálně konzistentního modelu (nebo souřadnicového rámce) a mapování nového měření na známou datovou sadu k identifikaci prvků nebo k odhadnout jeho pózu. Surová 3D cloudová data bodů se obvykle získávají z Lidars a RGB-D kamery. Mraky 3D bodů lze také generovat z algoritmů počítačového vidění, jako jsou triangulace, úprava svazku a v poslední době použití odhadu hloubky monokulárního obrazu hluboké učení. Pro 2D registraci sady bodů používanou při zpracování obrazu a na základě funkcí registrace obrázku, množina bodů může být 2D pixelové souřadnice získané pomocí extrakce funkcí například z obrázku detekce rohů. Registrace cloudu bodů má v aplikaci rozsáhlé aplikace autonomní jízda,^[1] odhad pohybu a 3D rekonstrukce,^[2] detekce objektu a odhad pozice,^[3][4] robotická manipulace,^[5] simultánní lokalizace a mapování (SLAM),^[6][7] panorama šití,^[8] virtuální a rozšířená realita,^[9] a lékařské zobrazování.^[10]

Jako zvláštní případ lze zaznamenat registraci dvou sad bodů, které se liší pouze 3D rotací (tj., neexistuje škálování a překlad), se nazývá Wahba problém a také související s ortogonální problém.

Přehled problému

Data ze dvou 3D skenů stejného prostředí je třeba srovnat pomocí registrace sady bodů.

Data shora, úspěšně zaregistrovaná pomocí varianty iterativního nejbližšího bodu.

Problém lze shrnout takto:^[11]Nechat ${ displaystyle lbrace { mathcal {M}}, { mathcal {S}} rbrace}$ být dvě množiny bodů konečné velikosti v konečný trojrozměrný skutečný vektorový prostor ${ displaystyle mathbb {R} ^ {d}}$, které obsahují ${ displaystyle M}$ a ${ displaystyle N}$ bodů (např., ${ displaystyle d = 3}$ obnoví typický případ kdy ${ displaystyle { mathcal {M}}}$ a ${ displaystyle { mathcal {S}}}$ jsou 3D sady bodů). Problémem je najít transformaci, která se použije na pohyblivou množinu bodů „modelu“ ${ displaystyle { mathcal {M}}}$ takový, že rozdíl (obvykle definován ve smyslu bodově Euklidovská vzdálenost ) mezi ${ displaystyle { mathcal {M}}}$ a statická "scéna" nastavena ${ displaystyle { mathcal {S}}}$ je minimalizován. Jinými slovy, mapování z ${ displaystyle mathbb {R} ^ {d}}$ na ${ displaystyle mathbb {R} ^ {d}}$ je požadováno, čímž se získá nejlepší vyrovnání mezi transformovanou sadou „modelu“ a sadou „scény“. Mapování může sestávat z rigidní nebo netuhé transformace. Transformační model lze zapsat jako ${ displaystyle T}$, pomocí kterého je transformovaná registrovaná modelová sada bodů:

${ displaystyle T ({ mathcal {M}})}$

(1)

Výstupem algoritmu registrace bodové sady je tedy optimální transformace ${ displaystyle T ^ { star}}$ takhle ${ displaystyle { mathcal {M}}}$ je nejlépe sladit s ${ displaystyle { mathcal {S}}}$, podle nějakého definovaného pojmu funkce vzdálenosti ${ displaystyle operatorname {dist} ( cdot, cdot)}$:

${ displaystyle T ^ { star} = arg min _ {T v { mathcal {T}}} { text {dist}} (T ({ mathcal {M}}), { mathcal { S}})}$

(2)

kde ${ displaystyle { mathcal {T}}}$ se používá k označení množiny všech možných transformací, které se optimalizace pokusí vyhledat. Nejoblíbenější volbou funkce vzdálenosti je vzít druhou mocninu Euklidovská vzdálenost za každou dvojici bodů:

${ displaystyle operatorname {dist} (T ({ mathcal {M}}), { mathcal {S}}) = součet _ {m v T ({ mathcal {M}})} Vert m -s_ {m} Vert _ {2} ^ {2}, quad s_ {m} = arg min _ {s in { mathcal {S}}} Vert sm Vert _ {2} ^ {2}}$

(3)

kde ${ displaystyle | cdot | _ {2}}$ označuje vektor 2-norm, ${ displaystyle s_ {m}}$ je odpovídající bod v sadě ${ displaystyle { mathcal {S}}}$ který dosáhne nejkratší vzdálenost do daného bodu ${ displaystyle m}$ v sadě ${ displaystyle { mathcal {M}}}$. Minimalizace takové funkce v rigidní registraci je ekvivalentní řešení a nejmenší čtverce problém. Když korespondence (tj., ${ displaystyle s_ {m} leftrightarrow m}$) jsou uvedeny před optimalizací, například pomocí technik párování funkcí, pak optimalizaci stačí odhadnout transformaci. Tento typ registrace se nazývá korespondenční registrace. Na druhou stranu, pokud jsou korespondence neznámé, je nutná optimalizace, aby se společně zjistily korespondence a transformace. Tento typ registrace se nazývá Simultánní registrace pozice a korespondence.

Tuhá registrace

Vzhledem ke dvěma bodovým sadám přináší tuhá registrace a rigidní transformace který mapuje jeden bod nastavený na druhý. Tuhá transformace je definována jako transformace, která nemění vzdálenost mezi dvěma body. Taková transformace se obvykle skládá z překlad a otáčení.^[12] Ve výjimečných případech může být sada bodů také zrcadlována. V robotice a počítačovém vidění má nejvíce aplikací rigidní registrace.

Non-rigid registrace

Registrovaný mračno bodů z a lidar namontován na jedoucím autě.

Vzhledem k tomu, že dvě sady bodů, nepružná registrace vede k nepružné transformaci, která mapuje jednu bodovou sadu na druhou. Mezi netuhé transformace patří afinní transformace jako škálování a smykové mapování. V kontextu registrace množiny bodů však netuhá registrace obvykle zahrnuje nelineární transformaci. Pokud vlastní variační režimy z množiny bodů jsou známy, nelineární transformace může být parametrizována vlastními hodnotami.^[13] Nelineární transformaci lze také parametrizovat jako a tenká deska spline.^[14][13]

Algoritmy registrace množiny bodů

Některé přístupy k registraci množiny bodů používají algoritmy, které řeší obecnější shoda grafu problém.^[11] Výpočtová složitost takových metod však bývá vysoká a omezují se na rigidní registrace. Algoritmy specifické pro problém registrace sady bodů jsou popsány v následujících částech PCL (Point Cloud Library) je open-source framework pro n-dimenzionální mračno bodů a zpracování 3D geometrie. Zahrnuje několik algoritmů registrace bodů.^[15]

V této části budeme uvažovat pouze o algoritmech pro rigidní registraci, kde se předpokládá, že transformace obsahuje 3D rotace a překlady (případně také včetně jednotného měřítka).

Metody založené na korespondenci

Metody založené na korespondenci předpokládají domnělou korespondenci ${ displaystyle m leftrightarrow s_ {m}}$ jsou uvedeny za každý bod ${ displaystyle m in { mathcal {M}}}$. Proto jsme dospěli k nastavení, kde oba bodové soubory ${ displaystyle { mathcal {M}}}$ a ${ displaystyle { mathcal {S}}}$ mít ${ displaystyle N}$ body a korespondence ${ displaystyle m_ {i} leftrightarrow s_ {i}, i = 1, tečky, N}$jsou uvedeny.

Registrace bez odlehlých hodnot

V nejjednodušším případě lze předpokládat, že všechny korespondence jsou správné, což znamená, že body ${ displaystyle m_ {i}, s_ {i} in mathbb {R} ^ {3}}$ jsou generovány následovně:

${ displaystyle s_ {i} = lRm_ {i} + t + epsilon _ {i}, i = 1, tečky, N}$

(cb.1)

kde ${ displaystyle l> 0}$ je jednotný faktor měřítka (v mnoha případech ${ displaystyle l = 1}$ předpokládá se), ${ displaystyle R v { textu {SO}} (3)}$ je správná 3D rotační matice (${ displaystyle { text {SO}} (d)}$ je speciální ortogonální skupina stupně ${ displaystyle d}$), ${ displaystyle t in mathbb {R} ^ {3}}$ je 3D překladový vektor a ${ displaystyle epsilon _ {i} in mathbb {R} ^ {3}}$ modeluje neznámý aditivní šum (např., Gaussovský hluk ). Konkrétně, pokud je hluk ${ displaystyle epsilon _ {i}}$ Předpokládá se, že sleduje izotropní Gaussovo rozdělení s nulovou střední hodnotou se směrodatnou odchylkou ${ displaystyle sigma _ {i}}$, tj., ${ displaystyle epsilon _ {i} sim { mathcal {N}} (0, sigma _ {i} ^ {2} I_ {3})}$, pak lze ukázat následující optimalizaci, která poskytne odhad maximální věrohodnosti pro neznámé měřítko, rotaci a překlad:

${ displaystyle l ^ { star}, R ^ { star}, t ^ { star} = arg min _ {l> 0, R v { textu {SO}} (3), t v mathbb {R} ^ {3}} sum _ {i = 1} ^ {N} { frac {1} { sigma _ {i} ^ {2}}} left Vert s_ {i} -lRm_ {i} -t doprava Vert _ {2} ^ {2}}$

(cb.2)

Všimněte si, že když je faktor měřítka 1 a vektor translace je nula, optimalizace obnoví formulaci Wahba problém. Navzdory nekonvexnost optimalizace (cb.2) kvůli nekonvexnosti sady ${ displaystyle { text {SO}} (3)}$, klíčová práce od Berthold K.P. Roh ukázal, že (cb.2) ve skutečnosti připouští řešení uzavřené formy oddělením odhadu měřítka, rotace a překladu.^[16] Podobné výsledky objevil Arun et al.^[17] Kromě toho za účelem nalezení jedinečné transformace ${ displaystyle (l, R, t)}$, alespoň ${ displaystyle N = 3}$ jsou vyžadovány nekolineární body v každé množině bodů.

V poslední době Briales a Gonzalez-Jimenez vyvinuli a semidefinitní relaxace použitím Lagrangeova dualita, pro případ, kdy je model nastaven ${ displaystyle { mathcal {M}}}$ obsahuje různá 3D primitiva, jako jsou body, čáry a roviny (což je případ modelu ${ displaystyle { mathcal {M}}}$ je 3D síť).^[18] Je zajímavé, že semidefinitní relaxace je empiricky těsná, tj., prokazatelně globálně optimální roztok lze extrahovat z řešení semidefinitní relaxace.

Robustní registrace

The nejmenší čtverce formulace (cb.2) je známo, že za své činnosti působí svévolně špatně odlehlé hodnoty. Odlehlá korespondence je dvojice měření ${ displaystyle s_ {i} leftrightarrow m_ {i}}$ který se odchyluje od generativního modelu (cb.1). V tomto případě lze uvažovat o jiném generativním modelu takto:^[19]

${ displaystyle s_ {i} = { begin {cases} lRm_ {i} + t + epsilon _ {i} & { text {if}} i - { text {th pair is an inlier}} o_ {i} & { text {if}} i - { text {ta dvojice je odlehlá}} end {případy}}}$

(cb.3)

kde pokud ${ displaystyle i-}$th pár ${ displaystyle s_ {i} leftrightarrow m_ {i}}$ je inlier, pak se řídí modelem bez odlehlých hodnot (cb.1), tj., ${ displaystyle s_ {i}}$ se získává z ${ displaystyle m_ {i}}$ prostorovou transformací plus malým hlukem; pokud však ${ displaystyle i-}$th pár ${ displaystyle s_ {i} leftrightarrow m_ {i}}$ je tedy odlehlá ${ displaystyle s_ {i}}$ může být libovolný vektor ${ displaystyle o_ {i}}$. Jelikož předem nevíte, které korespondence jsou odlehlé hodnoty, proveďte robustní registraci podle generativního modelu (cb.3) má zásadní význam pro počítačové vidění a robotiku nasazenou v reálném světě, protože současné techniky porovnávání funkcí mají tendenci vydávat vysoce poškozené korespondence, kde přes ${ displaystyle 95 \%}$ z korespondence mohou být odlehlé hodnoty.^[20]

Dále popíšeme několik běžných paradigmat pro robustní registraci.

Maximální shoda

Maximální shoda usiluje o nalezení největší sady korespondencí, které jsou v souladu s generativním modelem (cb.1) pro nějakou volbu prostorové transformace ${ displaystyle (l, R, t)}$. Formálně vzato maximální konsenzus řeší následující optimalizaci:

${ displaystyle max _ {l> 0, R in { text {SO}} (3), t in mathbb {R} ^ {3}, { mathcal {I}}} vert { mathcal {I}} vert, quad { text {předmět}} { frac {1} { sigma _ {i} ^ {2}}} Vert s_ {i} -lRm_ {i} -t Vert _ {2} ^ {2} leq xi, forall i in { mathcal {I}}}$

(cb.4)

kde ${ displaystyle vert { mathcal {I}} vert}$ označuje mohutnost sady ${ displaystyle { mathcal {I}}}$. Omezení v (cb.4) vynucuje, aby každá dvojice měření v sadě inlier ${ displaystyle { mathcal {I}}}$ musí mít zbytky menší než předem definovaná prahová hodnota ${ displaystyle xi}$. Bohužel nedávné analýzy ukázaly, že problém globálního řešení (cb.4) je NP-tvrdý a globální algoritmy se obvykle musí uchýlit rozvětvené a vázané (BnB) techniky, které v nejhorším případě vyžadují exponenciální časovou složitost.^{[21][22][23][24][25]}

Přestože je řešení maximalizace konsensu přesné, je těžké, existují účinné heuristiky, které v praxi fungují docela dobře. Jednou z nejpopulárnějších heuristik je Konsensus náhodných vzorků (RANSAC) systém.^[26] RANSAC je iterační metoda hypotézy a věrohodnosti. Při každé iteraci metoda nejprve náhodně vzorkuje 3 z celkového počtu ${ displaystyle N}$ korespondence a počítá hypotézu ${ displaystyle (l, R, t)}$ pomocí Hornovy metody,^[16] pak metoda vyhodnotí omezení v (cb.4) spočítat, kolik korespondencí ve skutečnosti souhlasí s takovou hypotézou (tj. počítá zbytek ${ displaystyle Vert s_ {i} -lRm_ {i} -t Vert _ {2} ^ {2} / sigma _ {i} ^ {2}}$ a porovná to s prahovou hodnotou ${ displaystyle xi}$ pro každou dvojici měření). Algoritmus končí buď poté, co našel konsensuální sadu, která má dostatek korespondence, nebo poté, co dosáhl celkového počtu povolených iterací. RANSAC je vysoce efektivní, protože hlavní výpočet každé iterace provádí řešení v uzavřené formě metodou Horn. RANSAC je však nedeterministický a funguje dobře pouze v režimu s nízkým odlehlým poměrem (např., níže ${ displaystyle 50 \%}$), protože jeho runtime roste exponenciálně vzhledem k odlehlému poměru.^[20]

Abychom vyplnili mezeru mezi rychlým, ale nepřesným schématem RANSAC a přesnou, ale vyčerpávající optimalizací BnB, vyvinuli nedávné výzkumy deterministické přibližné metody k řešení maximalizace konsensu.^{[21][22][27][23]}

Odlehlé odstranění

Metody odlehlého odstraňování se snaží před zpracováním prostorové transformace předem zpracovat sadu vysoce poškozených korespondencí. Motivací odstranění odlehlých hodnot je výrazně snížit počet odlehlých korespondencí při zachování inlierových korespondencí, aby se optimalizace přes transformaci stala snazší a efektivnější (např., RANSAC funguje špatně, když je odlehlý poměr vyšší ${ displaystyle 95 \%}$ ale funguje docela dobře, když je odlehlý poměr nižší ${ displaystyle 50 \%}$).

Parra et al. navrhli metodu nazvanou Zaručené odstranění odlehlých míst (GORE), která používá geometrická omezení k prořezávání odlehlých korespondencí a zároveň zaručuje zachování inlierových korespondencí.^[20] Ukázalo se, že GORE je schopen drasticky snížit odlehlý poměr, což může významně zvýšit výkon maximalizace konsensu pomocí RANSAC nebo BnB. Yang a Carlone navrhli vytvořit párová měření invariantní translace a rotace (TRIM) z původní sady měření a vložit TRIM jako okraje graf jejichž uzly jsou 3D body. Vzhledem k tomu, že inliery jsou párově konzistentní, pokud jde o měřítko, musí tvořit a klika v grafu. Proto za použití efektivních algoritmů pro výpočet maximální klika grafu může najít inliers a efektivně prořezat outliers.^[4] Je také prokázáno, že metoda odstraňování odlehlých hodnot založená na klikach je docela užitečná při problémech s registrací bodů v reálném světě.^[19] Podobné nápady na odstranění odlehlých míst navrhla také Parra et al..^[28]

M-odhad

M-odhad nahrazuje objektivní funkci nejmenších čtverců v (cb.2) s robustní nákladovou funkcí, která je méně citlivá na odlehlé hodnoty. Formálně se M-odhad snaží vyřešit následující problém:

${ displaystyle l ^ { star}, R ^ { star}, t ^ { star} = arg min _ {l> 0, R v { textu {SO}} (3), t v mathbb {R} ^ {3}} sum _ {i = 1} ^ {N} rho left ({ frac {1} { sigma _ {i}}} left Vert s_ {i } -lRm_ {i} -t doprava Vert _ {2} doprava)}$

(cb.5)

kde ${ displaystyle rho ( cdot)}$ představuje volbu robustní nákladové funkce. Všimněte si, že výběr ${ displaystyle rho (x) = x ^ {2}}$ obnoví odhad nejmenších čtverců v (cb.2). Mezi oblíbené robustní nákladové funkce patří ${ displaystyle ell _ {1}}$-normální ztráta, Huberova ztráta,^[29] Geman-McClure ztráta^[30] a zkrácená ztráta nejmenších čtverců.^[19][8][4] M-odhad byl jedním z nejpopulárnějších paradigmat pro robustní odhad v robotice a počítačovém vidění.^[31][32] Protože robustní objektivní funkce jsou obvykle nekonvexní (např., ztráta zkrácených nejmenších čtverců v.s. ztráta nejmenších čtverců), algoritmy pro řešení nekonvexního M-odhadu jsou obvykle založeny na lokální optimalizace, kde je nejprve poskytnut počáteční odhad, následovaný iterativními vylepšeními transformace, aby se snižovala objektivní funkce. Místní optimalizace má tendenci fungovat dobře, když se počáteční odhad blíží globálnímu minimu, ale je také náchylný k uvíznutí v místních minimech, pokud je k dispozici špatná inicializace.

Odstupňovaná nekonvexnost

Odstupňovaná nekonvexita (GNC) je univerzální rámec pro řešení nekonvexních optimalizačních problémů bez inicializace. Dosáhla úspěchu v aplikacích raného vidění a strojového učení.^[33][34] Klíčovou myšlenkou GNC je vyřešit těžký nekonvexní problém vycházejícím ze snadného konvexního problému. Konkrétně pro danou robustní nákladovou funkci ${ displaystyle rho ( cdot)}$, lze sestavit náhradní funkci ${ displaystyle rho _ { mu} ( cdot)}$ s hyperparametrem ${ displaystyle mu}$, ladění, které může postupně zvyšovat nekonvexnost náhradní funkce ${ displaystyle rho _ { mu} ( cdot)}$ dokud konverguje k cílové funkci ${ displaystyle rho ( cdot)}$.^[34][35] Proto na každé úrovni hyperparametru ${ displaystyle mu}$, je vyřešena následující optimalizace:

${ displaystyle l _ { mu} ^ { star}, R _ { mu} ^ { star}, t _ { mu} ^ { star} = arg min _ {l> 0, R v { text {SO}} (3), t in mathbb {R} ^ {3}} sum _ {i = 1} ^ {N} rho _ { mu} left ({ frac {1 } { sigma _ {i}}} left Vert s_ {i} -lRm_ {i} -t right Vert _ {2} right)}$

(cb.6)

Black a Rangarajan dokázali, že objektivní funkce každé optimalizace (cb.6) lze rozdělit na částku vážené nejmenší čtverce a takzvaná funkce odlehlého procesu na vahách, které určují spolehlivost optimalizace v každé dvojici měření.^[33] Pomocí duality Black-Rangarajan a GNC šité na míru pro funkci Geman-McClure, Zhou et al. vyvinul rychlý globální registrační algoritmus, který je robustní proti ${ displaystyle 80 \%}$ odlehlé hodnoty v korespondenci.^[30] Více nedávno, Yang et al. ukázalo, že společné použití GNC (přizpůsobené funkci Geman-McClure a funkce zkrácených nejmenších čtverců) a dualita Black-Rangarajan může vést k řešení univerzálních problémů pro robustní problémy s registrací, včetně mračen bodů a registrace sítě.^[35]

Ověřitelně robustní registrace

Téměř žádný z výše uvedených robustních registračních algoritmů (kromě algoritmu BnB, který běží v nejhorším případě v exponenciálním čase) nemá záruky výkonu, což znamená, že tyto algoritmy mohou bez upozornění vrátit zcela nesprávné odhady. Proto jsou tyto algoritmy pro bezpečnostní aplikace, jako je autonomní řízení, nežádoucí.

Velmi nedávno, Yang et al. vyvinula první certifikovatelný robustní registrační algoritmus s názvem Odhad zkrácených nejmenších čtverců A SEmidefinite relaxace (TEASER).^[19] U registrace mračna bodů TEASER nejen vydává odhad transformace, ale také kvantifikuje optimálnost daného odhadu. TEASER přijímá následující odhad zkrácených nejmenších čtverců (TLS):

${ displaystyle l ^ { star}, R ^ { star}, t ^ { star} = arg min _ {l> 0, R v { textu {SO}} (3), t in mathbb {R} ^ {3}} sum _ {i = 1} ^ {N} min left ({ frac {1} { sigma _ {i} ^ {2}}} left Vert s_ {i} -lRm_ {i} -t right Vert _ {2} ^ {2}, { bar {c}} ^ {2} right)}$

(cb.7)

který se získá výběrem robustní nákladové funkce TLS ${ displaystyle rho (x) = min (x ^ {2}, { bar {c}} ^ {2})}$, kde ${ displaystyle { bar {c}} ^ {2}}$je předdefinovaná konstanta, která určuje maximální povolené zbytky považované za inliery. Objektivní funkce TLS má vlastnost, že pro inlier korespondence (${ displaystyle Vert s_ {i} -lRm_ {i} -t Vert _ {2} ^ {2} / sigma _ {i} ^ {2} <{ bar {c}} ^ {2}}$), je uplatněn obvyklý trest nejmenších čtverců; zatímco u odlehlých korespondencí (${ displaystyle Vert s_ {i} -lRm_ {i} -t Vert _ {2} ^ {2} / sigma _ {i} ^ {2}> { bar {c}} ^ {2}}$), není uplatněna žádná pokuta a odlehlé hodnoty jsou zahozeny. Pokud je optimalizace TLS (cb.7) je vyřešen na globální optimálnost, pak je ekvivalentní spuštění Hornovy metody pouze na inlierových korespondencích.

Řešení (cb.7) je poměrně náročný díky své kombinatorické povaze. TEASER řeší (cb.7) takto: (i) Vytváří invariantní měření tak, aby bylo možné odhadnout měřítko, rotaci a translaci oddělit a vyřešit samostatně, což je strategie inspirovaná původní Hornovou metodou; (ii) Stejný odhad TLS se použije pro každý ze tří dílčích problémů, kde lze problém škálového TLS vyřešit přesně pomocí algoritmu zvaného adaptivní hlasování, problém rotace TLS lze uvolnit na semidefinitní program (SDP), kde je relaxace v praxi přesná,^[8] i při velkém počtu odlehlých hodnot; problém překladu TLS lze vyřešit pomocí adaptivního hlasování po jednotlivých komponentách. Rychlá implementace využívající GNC je otevřený zdroj zde. V praxi může TEASER tolerovat více než ${ displaystyle 99 \%}$ extrémní korespondence a běží v milisekundách.

Kromě vývoje TEASER, Yang et al. také dokázat, že za určitých mírných podmínek na datech mračen bodů odhadovaná transformace TEASER omezila chyby z transformace země-pravda.^[19]

Metody simultánní pozice a korespondence

Iterativní nejbližší bod

The iterativní nejbližší bod Algoritmus (ICP) představili Besl a McKay.^[36]Algoritmus provádí rigidní registraci iterativním způsobem střídáním (i) dané transformace, nálezu nejbližší bod v ${ displaystyle { mathcal {S}}}$ za každý bod ${ displaystyle { mathcal {M}}}$; a (ii) vzhledem k korespondenci nalezení nejlepší rigidní transformace řešením nejmenší čtverce problém (cb.2). Jako takový, to funguje nejlépe, když počáteční póza ${ displaystyle { mathcal {M}}}$ je dostatečně blízko ${ displaystyle { mathcal {S}}}$. v pseudo kód, základní algoritmus je implementován následovně:

algoritmus ICP(${ displaystyle { mathcal {M}}, { mathcal {S}}}$)    ${ displaystyle  theta: =  theta _ {0}}$    zatímco ne registrovaný: X := ∅        pro ${ displaystyle m_ {i}  v T ({ mathcal {M}},  theta)}$:            ${ displaystyle { hat {s}} _ {j}: = { text {nejbližší bod}} { mathcal {S}} { text {to}} m_ {i}}$            ${ displaystyle X: = X +  langle m_ {i}, { hat {s}} _ {j}  rangle}$        θ := nejmenší čtverce (X)    vrátit se θ

Tady funkce nejmenší čtverce provádí nejmenší čtverce optimalizace k minimalizaci vzdálenosti v každém z ${ displaystyle langle m_ {i}, { hat {s}} _ {j} rangle}$ páry pomocí řešení uzavřené formy Horn^[16] a Arun.^[17]

Protože nákladová funkce registrace závisí na nalezení nejbližšího bodu v ${ displaystyle { mathcal {S}}}$ do každého bodu ${ displaystyle { mathcal {M}}}$, může se změnit, jak běží algoritmus. Proto je obtížné dokázat, že ICP bude ve skutečnosti konvergovat přesně k místnímu optimu.^[37] Empiricky ve skutečnosti ICP a EM-ICP nesbližujte se s místním minimem nákladové funkce.^[37] Protože ICP je intuitivní a snadno implementovatelný, zůstává nejčastěji používaným algoritmem registrace bodů.^[37] Bylo navrženo mnoho variant ICP, které ovlivňují všechny fáze algoritmu od výběru a shody bodů až po minimalizační strategii.^[13][38]Například maximalizace očekávání Algoritmus se aplikuje na algoritmus ICP k vytvoření metody EM-ICP a Algoritmus Levenberg-Marquardt se aplikuje na algoritmus ICP k vytvoření LM-ICP metoda.^[12]

Robustní přizpůsobení bodů

Robustní porovnávání bodů (RPM) představili Gold et al.^[39] Metoda provádí registraci pomocí deterministické žíhání a měkké přiřazování korespondencí mezi množinami bodů. Zatímco v ICP je korespondence generovaná heuristikou nejbližšího souseda binární, RPM používá a měkký korespondence, kde korespondence mezi libovolnými dvěma body může být kdekoli od 0 do 1, i když nakonec konverguje k 0 nebo 1. Korespondence nalezená v RPM je vždy jedna k jedné, což není vždy případ ICP.^[14] Nechat ${ displaystyle m_ {i}}$ být ${ displaystyle i}$Třetí bod ${ displaystyle { mathcal {M}}}$ a ${ displaystyle s_ {j}}$ být ${ displaystyle j}$Třetí bod ${ displaystyle { mathcal {S}}}$. The matice shody ${ displaystyle mathbf { mu}}$ je definován jako takový:

${ displaystyle mu _ {ij} = left lbrace { begin {matrix} 1 & { text {if point}} m_ {i} { text {odpovídá point}} s_ {j} 0 & { text {jinak}} end {matrix}} vpravo.}$

(ot./min)

Problém je pak definován jako: Vzhledem ke dvěma bodovým sadám ${ displaystyle { mathcal {M}}}$ a ${ displaystyle { mathcal {S}}}$ najít Afinní transformace ${ displaystyle T}$ a matice shody ${ displaystyle mathbf { mu}}$ to je nejlépe souvisí.^[39] Znalost optimální transformace usnadňuje určení matice shody a naopak. Algoritmus RPM však určuje obojí současně. Transformaci lze rozložit na překladový vektor a transformační matici:

${ displaystyle T (m) = mathbf {A} m + mathbf {t}}$

Matice ${ displaystyle mathbf {A}}$ ve 2D se skládá ze čtyř samostatných parametrů ${ displaystyle lbrace a, theta, b, c rbrace}$, což jsou měřítko, rotace a vertikální a horizontální smykové komponenty. Funkce nákladů je pak:

${ displaystyle operatorname {cost} = součet _ {j = 1} ^ {N} součet _ {i = 1} ^ {M} mu _ {ij} lVert s_ {j} - mathbf {t } - mathbf {A} m_ {i} rVert ^ {2} + g ( mathbf {A}) - alpha sum _ {j = 1} ^ {N} sum _ {i = 1} ^ {M} mu _ {ij}}$

(ot / min. 2)

podléhá ${ displaystyle forall j ~ sum _ {i = 1} ^ {M} mu _ {ij} leq 1}$, ${ displaystyle forall i ~ sum _ {j = 1} ^ {N} mu _ {ij} leq 1}$, ${ displaystyle forall ij ~ mu _ {ij} v lbrace 0,1 rbrace}$. The ${ displaystyle alpha}$ termín ovlivňuje cíl směrem k silnější korelaci snížením nákladů, pokud má matice shody více. Funkce ${ displaystyle g ( mathbf {A})}$ slouží k regularizaci afinní transformace penalizací velkých hodnot komponent měřítka a smyku:

${ displaystyle g ( mathbf {A} (a, theta, b, c)) = gamma (a ^ {2} + b ^ {2} + c ^ {2})}$

pro nějaký parametr regularizace ${ displaystyle gamma}$.

Metoda RPM optimalizuje nákladovou funkci pomocí Softassign algoritmus. Zde bude odvozen případ 1D. Vzhledem k souboru proměnných ${ displaystyle lbrace Q_ {j} rbrace}$ kde ${ displaystyle Q_ {j} v mathbb {R} ^ {1}}$. Proměnná ${ displaystyle mu _ {j}}$ je spojen s každým ${ displaystyle Q_ {j}}$ takhle ${ displaystyle sum _ {j = 1} ^ {J} mu _ {j} = 1}$. Cílem je najít ${ displaystyle mathbf { mu}}$ který maximalizuje ${ displaystyle sum _ {j = 1} ^ {J} mu _ {j} Q_ {j}}$. To lze formulovat jako trvalý problém zavedením kontrolního parametru ${ displaystyle beta> 0}$. V deterministické žíhání metoda, kontrolní parametr ${ displaystyle beta}$ jak se algoritmus spouští, se pomalu zvyšuje. Nechat ${ displaystyle mathbf { mu}}$ být:

${ displaystyle mu _ { hat {j}} = { frac { exp {( beta Q _ { hat {j}})}}} { sum _ {j = 1} ^ {J} exp {( beta Q_ {j})}}}}$

(ot / min. 3.)

toto je známé jako funkce softmax. Tak jako ${ displaystyle beta}$ zvyšuje, přibližuje se k binární hodnotě podle potřeby v rovnici (ot./min). Problém lze nyní zobecnit na 2D případ, kdy místo maximalizace ${ displaystyle sum _ {j = 1} ^ {J} mu _ {j} Q_ {j}}$, je maximalizováno následující:

${ displaystyle E ( mu) = součet _ {j = 1} ^ {N} součet _ {i = 0} ^ {M} mu _ {ij} Q_ {ij}}$

(4 / min)

kde

${ displaystyle Q_ {ij} = - ( lVert s_ {j} - mathbf {t} - mathbf {A} m_ {i} rVert ^ {2} - alpha) = - { frac { částečný operatorname {cost}} { částečné mu _ {ij}}}}$

To je jednoduché, až na to, že nyní platí omezení ${ displaystyle mu}$ jsou dvojnásobně stochastická matice omezení: ${ displaystyle forall j ~ sum _ {i = 1} ^ {M} mu _ {ij} = 1}$ a ${ displaystyle forall i ~ sum _ {j = 1} ^ {N} mu _ {ij} = 1}$. Jako takový jmenovatel z rovnice (ot / min. 3.) nelze pro 2D případ vyjádřit jednoduše. K uspokojení omezení je možné použít výsledek kvůli Sinkhornovi,^[39] který uvádí, že dvojnásobná stochastická matice se získá z libovolné čtvercové matice se všemi pozitivními položkami iteračním procesem střídání normalizací řádků a sloupců. Algoritmus je tedy napsán jako takový:^[39]

algoritmus RPM2D${ displaystyle ({ mathcal {M}}, { mathcal {S}})}$    t := 0    ${ displaystyle a,  theta, b, c: = 0}$    ${ displaystyle  beta: =  beta _ {0}}$    ${ displaystyle { hat { mu}} _ {ij}: = 1+  epsilon}$    zatímco ${ displaystyle  beta < beta _ {f}}$:        zatímco μ nekonverguje: // aktualizuje parametry korespondence pomocí softassign            ${ displaystyle Q_ {ij}: = - { frac { částečné  operatorname {náklady}} { částečné  mu _ {ij}}}}$            ${ displaystyle  mu _ {ij} ^ {0}: =  exp ( beta Q_ {ij})}$            // použít Sinkhornovu metodu            zatímco ${ displaystyle { hat { mu}}}$ nekonverguje:                // Aktualizace ${ displaystyle { hat { mu}}}$ normalizací ve všech řádcích:                ${ displaystyle { hat { mu}} _ {ij} ^ {1}: = { frac {{ hat { mu}} _ {ij} ^ {0}} { sum _ {i = 1 } ^ {M + 1} { hat { mu}} _ {ij} ^ {0}}}}$                // Aktualizace ${ displaystyle { hat { mu}}}$ normalizací ve všech sloupcích:                ${ displaystyle { hat { mu}} _ {ij} ^ {0}: = { frac {{ hat { mu}} _ {ij} ^ {1}} { sum _ {j = 1 } ^ {N + 1} { hat { mu}} _ {ij} ^ {1}}}}$            // aktualizovat parametry pozice sestupem souřadnic            Aktualizace θ pomocí aktualizace analytického řešení t pomocí aktualizace analytického řešení a, b, c použitím Newtonova metoda        ${ displaystyle  beta: =  beta _ {r}  beta}$        ${ displaystyle  gamma: = { frac { gamma} { beta _ {r}}}}$    vrátit se a, b, c, θ a t

kde deterministický kontrolní parametr žíhání ${ displaystyle beta}$ je původně nastaven na ${ displaystyle beta _ {0}}$ a zvyšuje se faktorem ${ displaystyle beta _ {r}}$ dokud nedosáhne maximální hodnoty ${ displaystyle beta _ {f}}$. Souhrny v normalizačních krocích jsou součtem ${ displaystyle M + 1}$ a ${ displaystyle N + 1}$ místo jen ${ displaystyle M}$ a ${ displaystyle N}$ protože omezení na ${ displaystyle mu}$ jsou nerovnosti. Jako takový ${ displaystyle M + 1}$th a ${ displaystyle N + 1}$th prvky jsou uvolněné proměnné.

Algoritmus lze také rozšířit pro množiny bodů ve 3D nebo vyšších rozměrech. Omezení na korespondenční matici ${ displaystyle mathbf { mu}}$ jsou stejné v případě 3D jako v případě 2D. Struktura algoritmu proto zůstává nezměněna, přičemž hlavní rozdíl spočívá v tom, jak jsou řešeny rotační a překladové matice.^[39]

Tenká deska spline robustní spojování bodů

Animace 2D netuhé registrace sady zelených bodů ${ displaystyle { mathcal {M}}}$ do sady purpurových bodů ${ displaystyle { mathcal {S}}}$ poškozené hlučnými odlehlými hodnotami. Velikost modrých kruhů nepřímo souvisí s kontrolním parametrem ${ displaystyle beta}$. Žluté čáry označují korespondenci.

Algoritmus ChPS a Rangarajan s algoritmem TPS-RPM (thin point spline robust point matching) rozšiřuje metodu RPM o nepružnou registraci parametrizací transformace jako tenká deska spline.^[14]Protože však parametrizace spline tenké desky existuje pouze ve třech rozměrech, nelze metodu rozšířit na problémy zahrnující čtyři nebo více dimenzí.

Korelační jádro

Přístup jádrové korelace (KC) registrace sady bodů zavedli Tsin a Kanade.^[37]Ve srovnání s ICP je algoritmus KC odolnější vůči hlučným datům. Na rozdíl od ICP, kde je pro každý bod modelu uvažován pouze nejbližší bod scény, zde každý bod scény ovlivňuje každý bod modelu.^[37] Jako takový se jedná o vícekrát propojený registrační algoritmus. Pro některé funkce jádra ${ displaystyle K}$, korelace jádra ${ displaystyle KC}$ dvou bodů ${ displaystyle x_ {i}, x_ {j}}$ je definována takto:^[37]

${ displaystyle KC (x_ {i}, x_ {j}) = int K (x, x_ {i}) cdot K (x, x_ {j}) dx}$

(kc.1)

The funkce jádra ${ displaystyle K}$ vybrané pro registraci množiny bodů je obvykle symetrické a nezáporné jádro, podobné těm, které se používají v Okno Parzen odhad hustoty. The Gaussovo jádro se obvykle používá pro svou jednoduchost, i když jiné jako Jádro Epanechnikov a jádro tricube může být nahrazeno.^[37] Korelační korelace celé množiny bodů ${ displaystyle { mathcal { chi}}}$ je definován jako součet korelací jádra každého bodu v sadě s každým dalším bodem v sadě:^[37]

${ displaystyle KC ({ mathcal {X}}) = součet _ {i neq j} KC (x_ {i}, x_ {j}) = 2 součet _ {i$

(kc.2)

Logaritmus KC množiny bodů je proporcionální v rámci konstantního faktoru k informační entropie. Všimněte si, že KC je měřítkem „kompaktnosti“ množiny bodů - triviálně, pokud by všechny body v množině bodů byly na stejném místě, vyhodnotila by KC velkou hodnotu. The nákladová funkce algoritmu registrace množiny bodů pro některý transformační parametr ${ displaystyle theta}$ je definována takto:

${ displaystyle operatorname {cost} ({ mathcal {S}}, { mathcal {M}}, theta) = - sum _ {m in { mathcal {M}}} sum _ {s in { mathcal {S}}} KC (s, T (m, theta))}$

(kc.3)

Některé algebraické manipulace přinášejí:

${ displaystyle KC ({ mathcal {S}} pohár T ({ mathcal {M}}, theta)) = KC ({ mathcal {S}}) + KC (T ({ mathcal {M} }, theta)) - 2 operatorname {cost} ({ mathcal {S}}, { mathcal {M}}, theta)}$

(kc.4)

Výraz je zjednodušen pozorováním ${ displaystyle KC ({ mathcal {S}})}$ je nezávislý na ${ displaystyle theta}$. Dále, za předpokladu rigidní registrace, ${ displaystyle KC (T ({ mathcal {M}}, theta))}$ je neměnný, když ${ displaystyle theta}$ se změní, protože euklidovská vzdálenost mezi každou dvojicí bodů zůstává stejná pod rigidní transformace. Výše uvedená rovnice může být tedy přepsána jako:

${ displaystyle KC ({ mathcal {S}} cup T ({ mathcal {M}}, theta)) = C-2 operatorname {cost} ({ mathcal {S}}, { mathcal { M}}, theta)}$

(kc.5)

The odhady hustoty jádra jsou definovány jako:

${ displaystyle P _ { mathcal {M}} (x, theta) = { frac {1} {M}} součet _ {m in { mathcal {M}}} K (x, T (m , theta))}$

${ displaystyle P _ { mathcal {S}} (x) = { frac {1} {N}} součet _ {s v { mathcal {S}}} K (x, s)}$

Funkci nákladů lze poté ukázat jako korelaci dvou odhadů hustoty jádra:

${ displaystyle operatorname {cost} ({ mathcal {S}}, { mathcal {M}}, theta) = - N ^ {2} int _ {x} P _ { mathcal {M}} cdot P _ { mathcal {S}} ~ dx}$

(kc.6)

Po založení nákladová funkce, algoritmus jednoduše používá klesání najít optimální transformaci. Výpočet nákladové funkce od nuly při každé iteraci je výpočetně nákladný, takže diskrétní verze nákladové funkce Rovnice (kc.6) se používá. Odhady hustoty jádra ${ displaystyle P _ { mathcal {M}}, P _ { mathcal {S}}}$ lze vyhodnotit v bodech mřížky a uložit do a vyhledávací tabulka. Na rozdíl od ICP a souvisejících metod není nutné hledat nejbližšího souseda, což umožňuje implementaci poměrně jednoduchého algoritmu KC.

Ve srovnání s ICP a EM-ICP pro hlučné 2D a 3D sady bodů je algoritmus KC méně citlivý na šum a častěji vede ke správné registraci.^[37]

Gaussův model směsi

Odhady hustoty jádra jsou součty Gaussianů, a proto je lze reprezentovat jako Gaussovy modely směsí (GMM).^[40] Jian a Vemuri používají verzi GMM registračního algoritmu KC k provedení netuhé registrace parametrizované tenké dlahy.

Koherentní posun bodu

Pevné (s přidáním měřítka) registrace sady modrých bodů ${ displaystyle { mathcal {M}}}$ to the red point set ${ displaystyle { mathcal {S}}}$ using the Coherent Point Drift algorithm. Both point sets have been corrupted with removed points and random spurious outlier points.

Affine registration of a blue point set ${ displaystyle { mathcal {M}}}$ to the red point set ${ displaystyle { mathcal {S}}}$ using the Coherent Point Drift algorithm.

Non-rigid registration of a blue point set ${ displaystyle { mathcal {M}}}$ to the red point set ${ displaystyle { mathcal {S}}}$ using the Coherent Point Drift algorithm. Both point sets have been corrupted with removed points and random spurious outlier points.

Coherent point drift (CPD) was introduced by Myronenko and Song.^[13][41]The algorithm takes a probabilistic approach to aligning point sets, similar to the GMM KC method. Unlike earlier approaches to non-rigid registration which assume a thin plate spline transformation model, CPD is agnostic with regard to the transformation model used. The point set ${ displaystyle { mathcal {M}}}$ představuje Gaussian mixture model (GMM) centroids. When the two point sets are optimally aligned, the correspondence is the maximum of the GMM posterior probability for a given data point. To preserve the topological structure of the point sets, the GMM centroids are forced to move coherently as a group. The maximalizace očekávání algorithm is used to optimize the cost function.^[13]

Ať tam bude M body v ${ displaystyle { mathcal {M}}}$ a N body v ${ displaystyle { mathcal {S}}}$. The GMM funkce hustoty pravděpodobnosti pro bod s je:

${displaystyle p(s)=sum _{i=1}^{M+1}P(i)p(s|i)}$

(cpd.1)

kde v D rozměry, ${displaystyle p(s|i)}$ je Gaussovo rozdělení centered on point ${displaystyle m_{i}in {mathcal {M}}}$.

${displaystyle p(s|i)={frac {1}{(2pi sigma ^{2})^{D/2}}}exp {left(-{frac {lVert s-m_{i} Vert ^{2}}{2sigma ^{2}}} ight)}}$

The membership probabilities ${displaystyle P(i)={frac {1}{M}}}$ is equal for all GMM components. The weight of the uniform distribution is denoted as ${displaystyle win [0,1]}$. The mixture model is then:

${displaystyle p(s)=w{frac {1}{N}}+(1-w)sum _{i=1}^{M}{frac {1}{M}}p(s|i)}$

(cpd.2)

The GMM centroids are re-parametrized by a set of parameters ${ displaystyle theta}$ estimated by maximizing the likelihood. This is equivalent to minimizing the negative funkce log-likelihood:

${displaystyle E( heta ,sigma ^{2})=-sum _{j=1}^{N}log sum _{i=1}^{M+1}P(i)p(s|i)}$

(cpd.3)

where it is assumed that the data is nezávislé a identicky distribuované. The correspondence probability between two points ${ displaystyle m_ {i}}$ a ${ displaystyle s_ {j}}$ je definován jako posterior probability of the GMM centroid given the data point:

${displaystyle P(i|s_{j})={frac {P(i)p(s_{j}|i)}{p(s_{j})}}}$

The maximalizace očekávání (EM) algorithm is used to find ${ displaystyle theta}$ a ${ displaystyle sigma ^ {2}}$. The EM algorithm consists of two steps. First, in the E-step or odhad step, it guesses the values of parameters ("old" parameter values) and then uses Bayesova věta to compute the posterior probability distributions ${displaystyle P^{ ext{old}}(i,s_{j})}$ of mixture components. Second, in the M-step or maximization step, the "new" parameter values are then found by minimizing the expectation of the complete negative log-likelihood function, i.e. the cost function:

${displaystyle operatorname {cost} =-sum _{j=1}^{N}sum _{i=1}^{M+1}P^{ ext{old}}(i|s_{j})log(P^{ ext{new}}(i)p^{ ext{new}}(s_{j}|i))}$

(cpd.4)

Ignoring constants independent of ${ displaystyle theta}$ a ${ displaystyle sigma}$, Rovnice (cpd.4) can be expressed thus:

${displaystyle operatorname {cost} ( heta ,sigma ^{2})={frac {1}{2sigma ^{2}}}sum _{j=1}^{N}sum _{i=1}^{M+1}P^{ ext{old}}(i|s_{j})lVert s_{j}-T(m_{i}, heta ) Vert ^{2}+{frac {N_{mathbf {P} }D}{2}}log {sigma ^{2}}}$

(cpd.5)

kde

${displaystyle N_{mathbf {P} }=sum _{j=0}^{N}sum _{i=0}^{M}P^{ ext{old}}(i|s_{j})leq N}$

s ${displaystyle N=N_{mathbf {P} }}$ jen když ${ displaystyle w = 0}$. The posterior probabilities of GMM components computed using previous parameter values ${displaystyle P^{ ext{old}}}$ je:

${displaystyle P^{ ext{old}}(i|s_{j})={frac {exp left(-{frac {1}{2sigma ^{{ ext{old}}2}}}lVert s_{j}-T(m_{i}, heta ^{ ext{old}}) Vert ^{2} ight)}{sum _{k=1}^{M}exp left(-{frac {1}{2sigma ^{{ ext{old}}2}}}lVert s_{j}-T(m_{k}, heta ^{ ext{old}}) Vert ^{2} ight)+(2pi sigma ^{2})^{frac {D}{2}}{frac {w}{1-w}}{frac {M}{N}}}}}$

(cpd.6)

Minimizing the cost function in Equation (cpd.5) necessarily decreases the negative log-likelihood function E in Equation (cpd.3) unless it is already at a local minimum.^[13] Thus, the algorithm can be expressed using the following pseudocode, where the point sets ${ displaystyle { mathcal {M}}}$ a ${ displaystyle { mathcal {S}}}$ are represented as ${displaystyle M imes D}$ a ${displaystyle N imes D}$ matice ${displaystyle mathbf {M} }$ a ${displaystyle mathbf {S} }$ respektive:^[13]

algorithm CPD${displaystyle ({mathcal {M}},{mathcal {S}})}$    ${displaystyle 	heta :=	heta _{0}}$    inicializovat ${displaystyle 0leq wleq 1}$    ${displaystyle sigma ^{2}:={frac {1}{DNM}}sum _{j=1}^{N}sum _{i=1}^{M}lVert s_{j}-m_{i}
Vert ^{2}}$    zatímco not registered:        // E-step, compute P        pro ${displaystyle iin [1,M]}$ a ${displaystyle jin [1,N]}$:            ${displaystyle p_{ij}:={frac {exp left(-{frac {1}{2sigma ^{2}}}lVert s_{j}-T(m_{i},	heta )
Vert ^{2}
ight)}{sum _{k=1}^{M}exp left(-{frac {1}{2sigma ^{2}}}lVert s_{j}-T(m_{k},	heta )
Vert ^{2}
ight)+(2pi sigma ^{2})^{frac {D}{2}}{frac {w}{1-w}}{frac {M}{N}}}}}$        // M-step, solve for optimal transformation        ${displaystyle lbrace 	heta ,sigma ^{2}
brace :=mathbf {solve} (mathbf {S} ,mathbf {M} ,mathbf {P} )}$    vrátit se θ

kde vektor ${ displaystyle mathbf {1}}$ is a column vector of ones. The řešit function differs by the type of registration performed. For example, in rigid registration, the output is a scale A, a rotation matrix ${ displaystyle mathbf {R}}$, and a translation vector ${displaystyle mathbf {t} }$. Parametr ${ displaystyle theta}$ can be written as a tuple of these:

${displaystyle heta =lbrace a,mathbf {R} ,mathbf {t} brace }$

which is initialized to one, the matice identity, and a column vector of zeroes:

${displaystyle heta _{0}=lbrace 1,mathbf {I} ,mathbf {0} brace }$

The aligned point set is:

${displaystyle T(mathbf {M} )=amathbf {M} mathbf {R} ^{T}+mathbf {1} mathbf {t} ^{T}}$

The solve_rigid function for rigid registration can then be written as follows, with derivation of the algebra explained in Myronenko's 2010 paper.^[13]

solve_rigid${displaystyle (mathbf {S} ,mathbf {M} ,mathbf {P} )}$    ${displaystyle N_{mathbf {P} }:=mathbf {1} ^{T}mathbf {P} mathbf {1} }$    ${displaystyle mu _{s}:={frac {1}{N_{mathbf {P} }}}mathbf {S} ^{T}mathbf {P} ^{T}mathbf {1} }$    ${displaystyle mu _{m}:={frac {1}{N_{mathbf {P} }}}mathbf {M} ^{T}mathbf {P} mathbf {1} }$    ${displaystyle {hat {mathbf {S} }}:=mathbf {S} -mathbf {1} mu _{s}^{T}}$    ${displaystyle {hat {mathbf {M} }}:=mathbf {M} -mathbf {1} mu _{m}^{T}}$    ${displaystyle mathbf {A} :={hat {mathbf {S} ^{T}}}mathbf {P} ^{T}{hat {mathbf {M} }}}$    ${displaystyle mathbf {U} ,mathbf {V} :=mathbf {svd} (mathbf {A} )}$ // the singular value decomposition z ${displaystyle mathbf {A} =mathbf {U} Sigma mathbf {V} ^{T}}$    ${displaystyle mathbf {C} :=operatorname {diag} (1,...,1,det(mathbf {UV} ^{T}))}$ // diag(ξ) je diagonální matice formed from vector ξ    ${displaystyle mathbf {R} :=mathbf {UCV} ^{T}}$    ${displaystyle a:={frac {operatorname {tr} (mathbf {A} ^{T}mathbf {R} )}{operatorname {tr} (mathbf {{hat {mathbf {M} }}^{T}operatorname {diag} (mathbf {P} mathbf {1} ){hat {mathbf {M} }}} )}}}$ // tr je stopa matice    ${displaystyle mathbf {t} :=mu _{s}-amathbf {R} mu _{m}}$    ${displaystyle sigma ^{2}:={frac {1}{N_{mathbf {P} }D}}(operatorname {tr} (mathbf {{hat {mathbf {S} }}^{T}operatorname {diag} (mathbf {P} ^{T}mathbf {1} ){hat {mathbf {S} }}} )-aoperatorname {tr} (mathbf {A} ^{T}mathbf {R} ))}$    vrátit se ${displaystyle lbrace a,mathbf {R} ,mathbf {t} 
brace ,sigma ^{2}}$

For affine registration, where the goal is to find an afinní transformace instead of a rigid one, the output is an affine transformation matrix ${ displaystyle mathbf {B}}$ and a translation ${displaystyle mathbf {t} }$ such that the aligned point set is:

${displaystyle T(mathbf {M} )=mathbf {M} mathbf {B} ^{T}+mathbf {1} mathbf {t} ^{T}}$

The solve_affine function for rigid registration can then be written as follows, with derivation of the algebra explained in Myronenko's 2010 paper.^[13]

solve_affine${displaystyle (mathbf {S} ,mathbf {M} ,mathbf {P} )}$    ${displaystyle N_{mathbf {P} }:=mathbf {1} ^{T}mathbf {P} mathbf {1} }$    ${displaystyle mu _{s}:={frac {1}{N_{mathbf {P} }}}mathbf {S} ^{T}mathbf {P} ^{T}mathbf {1} }$    ${displaystyle mu _{m}:={frac {1}{N_{mathbf {P} }}}mathbf {M} ^{T}mathbf {P} mathbf {1} }$    ${displaystyle {hat {mathbf {S} }}:=mathbf {S} -mathbf {1} mu _{s}^{T}}$    ${displaystyle {hat {mathbf {M} }}:=mathbf {M} -mathbf {1} mu _{s}^{T}}$    ${displaystyle mathbf {B} :=({hat {mathbf {S} ^{T}}}mathbf {P} ^{T}{hat {mathbf {M} }})({hat {mathbf {M} ^{T}}}operatorname {diag} (mathbf {P} mathbf {1} ){hat {mathbf {M} }})^{-1}}$    ${displaystyle mathbf {t} :=mu _{s}-mathbf {B} mu _{m}}$    ${displaystyle sigma ^{2}:={frac {1}{N_{mathbf {P} }D}}(operatorname {tr} ({hat {mathbf {S} ^{T}}}operatorname {diag} (mathbf {P} ^{T}mathbf {1} ){hat {mathbf {S} }})-operatorname {tr} ({hat {mathbf {S} ^{T}}}mathbf {P} ^{T}{hat {mathbf {M} }}mathbf {B} ^{T}))}$    vrátit se ${displaystyle {mathbf {B} ,mathbf {t} },sigma ^{2}}$

It is also possible to use CPD with non-rigid registration using a parametrization derived using variační počet.^[13]

Sums of Gaussian distributions can be computed in lineární čas za použití fast Gauss transform (FGT).^[13] V důsledku toho časová složitost of CPD is ${displaystyle O(M+N)}$, which is asymptotically much faster than ${displaystyle O(MN)}$ metody.^[13]

Sorting the Correspondence Space (SCS)

This algorithm was introduced in 2013 by H. Assalih to accommodate sonar image registration.^[42] These types of images tend to have high amounts of noise, so it is expected to have many outliers in the point sets to match. SCS delivers high robustness against outliers and can surpass ICP and CPD performance in the presence of outliers. SCS doesn't use iterative optimization in high dimensional space and is neither probabilistic nor spectral. SCS can match rigid and non-rigid transformations, and performs best when the target transformation is between three and six stupně svobody.

Bayesian coherent point drift (BCPD)

A variant of coherent point drift, called Bayesian coherent point drift (BCPD), was derived through a Bayesian formulation of point set registration.^[43]BCPD has several advantages over CPD, e.g., (1) nonrigid and rigid registrations can be performed in a single algorithm, (2) the algorithm can be accelerated regardless of the Gaussianity of a Gram matrix to define motion coherence, (3) the algorithm is more robust against outliers because of a more reasonable definition of an outlier distribution. Additionally, in the Bayesian formulation, motion coherence was introduced through a prior distribution of displacement vectors, providing a clear difference between tuning parameters that control motion coherence.

Viz také

• Point feature matching

Reference