Point-set registrering

Punktuppsättningsregistrering är processen för att anpassa två punktuppsättningar. Här registreras den blå fisken till den röda fisken.

Inom datorseende , mönsterigenkänning och robotik är punktuppsättningsregistrering , även känd som punkt-molnregistrering eller skanningsmatchning , processen att hitta en rumslig transformation ( t.ex. skalning , rotation och translation ) som riktar två punktmoln . Syftet med att hitta en sådan transformation inkluderar att slå samman flera datamängder till en globalt konsistent modell (eller koordinatram), och att kartlägga en ny mätning till en känd datamängd för att identifiera funktioner eller för att uppskatta dess ställning . Rå 3D-punktmolndata erhålls vanligtvis från Lidars och RGB-D-kameror . 3D-punktmoln kan också genereras från datorseendealgoritmer som triangulering , buntjustering och på senare tid, monokulär bilddjupuppskattning med hjälp av djupinlärning . För 2D-punktuppsättningsregistrering som används i bildbehandling och funktionsbaserad bildregistrering kan en punktuppsättning vara 2D-pixelkoordinater erhållna genom funktionsextraktion från en bild, till exempel hörndetektering . Punktmolnregistrering har omfattande tillämpningar inom autonom körning , rörelseuppskattning och 3D-rekonstruktion , objektdetektering och poseringsuppskattning , robotmanipulation , simultan lokalisering och kartläggning (SLAM), panoramasömmar , virtuell och förstärkt verklighet och medicinsk bildbehandling .

Som ett specialfall kallas registrering av två punktuppsättningar som endast skiljer sig åt genom en 3D-rotation ( dvs. det finns ingen skalning och translation), Wahba-problemet och även relaterat till problemet med ortogonala procrustes .

Formulering

Data från två 3D-skanningar av samma miljö måste justeras med hjälp av punktuppsättningsregistrering.

Data från ovan, registrerade framgångsrikt med en variant av iterativ närmaste punkt.

Problemet kan sammanfattas enligt följande: Låt $\lbrace {\mathcal {M}},{\mathcal {S}}\rbrace$ vara två ändliga storlekspunkter i en ändlig dimensionell reell vektor mellanslag $\mathbb {R} ^{d}$ , som innehåller $M$ respektive $N$ punkter ( t.ex. $d=3$ återställer den typiska fallet när ${\mathcal {M}}$ och ${\mathcal {S}}$ är 3D-punktuppsättningar). Problemet är att hitta en transformation som ska tillämpas på den rörliga "modell"-punktuppsättningen ${\mathcal {M}}$ så att skillnaden (typiskt definierad i betydelsen punktvis euklidiskt avstånd ) mellan ${ \displaystyle {\mathcal {M}}}$ och den statiska "scenen"-uppsättningen ${\mathcal {S}}$ minimeras. Med andra ord önskas en mappning från $\mathbb {R} ^{d}$ till ${\displaystyle \mathbb {R} ^{d}} som ger den bästa anpassningen mellan den transformerade "modellen$ " set och "scenen" set. Kartläggningen kan bestå av en stel eller icke-styv transformation. Transformationsmodellen kan skrivas som $T$ , med hjälp av vilken den transformerade, registrerade modellpunktuppsättningen är:

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

 

 

 

 

()

Utdata från en punktuppsättningsregistreringsalgoritm är därför den optimala transformationen $T^{\star }$ så att ${\mathcal {M}}$ bäst anpassas till ${\mathcal {S}}$ , enligt någon definierad uppfattning om avståndsfunktion $\operatorname {dist} (\cdot ,\cdot )$ :

$T^{\star }=\arg \min _{T\in {\mathcal {T}}}{\text{avstånd }}(T({\mathcal {M}}),{\mathcal {S}})$

 

 

 

 

()

där ${\mathcal {T}}$ används för att beteckna mängden av alla möjliga transformationer som optimeringen försöker söka efter. Det mest populära valet av avståndsfunktionen är att ta kvadraten på det euklidiska avståndet för varje par av punkter:

$\operatornamn {dist } (T({\mathcal {M}}),{\mathcal {S}})=\summa _{m\in T({\mathcal {M}})}\Vert m-s_{m}\Vert _{2}^{2},\quad s_{m}=\arg \min _{s\in {\mathcal {S}}}\Vert sm\Vert _{2}^{2}$

 

 

 

 

()

där $\|\cdot \|_{2}$ anger vektorn 2-norm , $s_{m}$ är motsvarande punkt i mängden ${\mathcal { S}}$ som når det kortaste avståndet till en given punkt $m$ i mängden ${\mathcal {M}}$ efter transformation. Att minimera en sådan funktion i rigid registrering är ekvivalent med att lösa ett minsta kvadratproblem .

Typer av algoritmer

När överensstämmelserna ( dvs $s_{m}\leftrightarrow m$ ) ges före optimeringen, till exempel med hjälp av funktionsmatchningstekniker , behöver optimeringen bara uppskatta transformationen. Denna typ av registrering kallas korrespondensbaserad registrering . Å andra sidan, om korrespondenserna är okända, krävs optimering för att gemensamt ta reda på korrespondenserna och transformationen tillsammans. Denna typ av registrering kallas simultan pose- och korrespondensregistrering .

Styv registrering

Givet två punktuppsättningar ger stel registrering en stel transformation som mappar en punktuppsättning till den andra. En stel transformation definieras som en transformation som inte ändrar avståndet mellan två punkter. Typiskt består en sådan transformation av translation och rotation . I sällsynta fall kan punktuppsättningen också speglas. Inom robotteknik och datorseende har rigid registrering flest tillämpningar.

Ej rigid registrering

Registrerat punktmoln från en lidar monterad på en bil i rörelse.

Givet två punktuppsättningar ger icke-rigid registrering en icke-rigid transformation som mappar en punktuppsättning till den andra. Icke-styva transformationer inkluderar affina transformationer som skalning och skjuvmappning . I samband med punktuppsättningsregistrering innebär emellertid icke-stel registrering typiskt icke-linjär transformation. Om egenmoden för variation av punktmängden är kända, kan den olinjära transformationen parametriseras av egenvärdena. En olinjär transformation kan också parametriseras som en tunn plattspline .

Andra typer

Vissa metoder för registrering av punktuppsättningar använder algoritmer som löser det mer allmänna grafmatchningsproblemet . Beräkningskomplexiteten hos sådana metoder tenderar dock att vara hög och de är begränsade till stela registreringar. I den här artikeln kommer vi endast att beakta algoritmer för rigid registrering, där transformationen antas innehålla 3D-rotationer och translationer (eventuellt även inklusive en enhetlig skalning).

PCL (Point Cloud Library) är ett ramverk med öppen källkod för n-dimensionellt punktmoln och 3D-geometribehandling. Den innehåller flera punktregistreringsalgoritmer.

Korrespondensbaserad registrering

Korrespondensbaserade metoder antar att de förmodade korrespondenserna $m\leftrightarrow s_{m}$ ges för varje punkt $m\in {\mathcal {M}}$ . Därför kommer vi fram till en inställning där båda punktmängderna ${\mathcal {M}}$ och ${\mathcal {S}}$ har $N$ punkter och överensstämmelserna $m_{i}\leftrightarrow s_{i},i=1,\dots ,N$ ges.

Outlier-fri registrering

I det enklaste fallet kan man anta att alla överensstämmelser är korrekta, vilket innebär att punkterna $m_{i},s_{i}\in \mathbb {R} ^{3}$ genereras enligt följande:

$s_{i}=lRm_{i}+t+\epsilon _{i},i=1,\dots ,N$

 

 

 

 

()

där $l>0$ är en enhetlig skalningsfaktor (i många fall antas ${\displaystyle l=1} ),$$R\in {\text{SO }}(3)$ är en riktig 3D-rotationsmatris ( ${\text{SO}}(d)$ är den speciella ortogonala gruppen av grad $d$ ), $t\in \mathbb {R} ^{3}$ är en 3D-översättningsvektor och $\epsilon _{i}\in \mathbb {R} ^{3}$ modellerar okänt additivt brus ( t.ex. Gaussiskt brus ). Specifikt, om bruset $\epsilon _{i}$ antas följa en nollmedelvärde isotrop Gauss-fördelning med standardavvikelse $\sigma _{i}$ , dvs. ${\displaystyle \epsilon _{i}\sim {\mathcal {N}}(0,\sigma _{i}^{2}I_{3})} ,$ sedan följande optimering kan visas för att ge maximal sannolikhetsuppskattning för den okända skalan, rotationen och translationen:

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

 

 

 

 

()

Observera att när skalningsfaktorn är 1 och translationsvektorn är noll, så återställer optimeringen formuleringen av Wahba-problemet . Trots att optimeringen ( cb.2 ) inte är konvex på grund av att mängden ${\displaystyle {\text{SO}}(3)} inte är konvex,$ visade det framträdande arbetet av Berthold KP Horn att ( cb .2 ) tillåter faktiskt en lösning i sluten form genom att frikoppla uppskattningen av skala, rotation och translation. Liknande resultat upptäcktes av Arun et al . Dessutom, för att hitta en unik transformation $(l,R,t)$ , är minst $N=3$ icke-kollinjära punkter i varje punktuppsättning nödvändig.

På senare tid har Briales och Gonzalez-Jimenez utvecklat en semidefinitiv relaxation med hjälp av lagrangisk dualitet , för det fall där modelluppsättningen ${\mathcal {M}}$ innehåller olika 3D-primitiver som punkter, linjer och plan (vilket är fallet när modellen ${\mathcal {M}}$ är ett 3D-nät). Intressant nog är den semidefinita relaxationen empiriskt tight, dvs en certifierat globalt optimal lösning kan extraheras från lösningen av den semidefinita relaxationen.

Robust registrering

Minsta kvadraters formulering ( cb.2 ) är känd för att fungera godtyckligt dåligt i närvaro av extremvärden . En outlier-överensstämmelse är ett par mått $s_{i}\leftrightarrow m_{i}$ som avviker från den generativa modellen ( cb.1 ). I det här fallet kan man överväga en annan generativ modell enligt följande:

$s_{i}={\begin{cases}lRm_{i}+ t+\epsilon _{i}&{\text{if }}i-{\text{th paret är ett inlier}}\\o_{i}&{\text{if }}i-{\text{th paret är en outlier}}\end{cases}}$

 

 

 

 

()

där om ${\displaystyle i-}:$ te paret $s_{i}\leftrightarrow m_{i}$ är en inlier, så följer den den extrema modellen ( cb.1 ), dvs. $s_{i}$ erhålls från $m_{i}$ genom en rumslig transformation plus litet brus; men om ${\displaystyle i-}:$ te paret $s_{i}\leftrightarrow m_{i}$ är en extremvärde, då kan ${\displaystyle s_{i}} vara$ någon godtycklig vektor $o_{i}$ . Eftersom man inte på förhand vet vilka motsvarigheter som är extremvärden, är robust registrering under den generativa modellen ( cb.3 ) av största vikt för datorseende och robotik som används i den verkliga världen, eftersom nuvarande funktionsmatchningstekniker tenderar att producera mycket korrupta korrespondenser där över $95\%$ av överensstämmelserna kan vara extremvärden.

Därefter beskriver vi flera vanliga paradigm för robust registrering.

Maximal konsensus

Maximal konsensus försöker hitta den största uppsättningen av överensstämmelser som överensstämmer med den generativa modellen ( cb.1 ) för något val av rumslig transformation $(l,R,t)$ . Formellt sett löser maximal konsensus följande optimering:

$\max _{l>0,R\in {\text{SO}}(3 ),t\in \mathbb {R} ^{3},{\mathcal {I}}}\vert {\mathcal {I}}\vert ,\quad {\text{med förbehåll för }}{\frac {1 }{\sigma _{i}^{2}}}\Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}\leq \xi ,\forall i\in {\mathcal {I}}$

 

 

 

 

()

där $\vert {\mathcal {I}}\vert$ anger kardinaliteten av mängden ${\mathcal {I}}$ . Restriktionen i ( cb.4 ) tvingar fram att varje par av mätningar i inliermängden ${\mathcal {I}}$ måste ha rester som är mindre än ett fördefinierat tröskelvärde $\xi$ . Tyvärr har nya analyser visat att globalt lösa problem (cb.4) är NP-Hard , och globala algoritmer måste vanligtvis tillgripa branch-and-bound (BnB)-tekniker som tar exponentiell tidskomplexitet i värsta fall.

Även om det är svårt att lösa konsensusmaximering exakt, finns det effektiva heuristiker som fungerar ganska bra i praktiken. En av de mest populära heuristikerna är schemat Random Sample Consensus (RANSAC) . RANSAC är en iterativ hypotes-och-verifieringsmetod. Vid varje iteration samplar metoden först slumpmässigt 3 av det totala antalet $N$ -överensstämmelser och beräknar en hypotes $(l,R,t)$ med Horns metod, sedan metoden utvärderar begränsningarna i ( cb.4 ) för att räkna hur många överensstämmelser som faktiskt överensstämmer med en sådan hypotes (dvs. den beräknar den resterande $\ Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}$ och jämför det med tröskelvärdet $\xi$ för varje par av mätningar). Algoritmen avslutas antingen efter att den har hittat en konsensusuppsättning som har tillräckligt med överensstämmelse, eller efter att den har nått det totala antalet tillåtna iterationer. RANSAC är mycket effektiv eftersom huvudberäkningen av varje iteration utför den slutna lösningen i Horns metod. RANSAC är dock icke-deterministisk och fungerar bara bra i regimen med lågt extremvärde ( t.ex. under $50\%$ ), eftersom dess körtid växer exponentiellt i förhållande till extremförhållandet.

För att fylla gapet mellan det snabba men inexakta RANSAC-schemat och den exakta men uttömmande BnB-optimeringen har nyare forskning utvecklat deterministiska ungefärliga metoder för att lösa konsensusmaximering.

Avvikande borttagning

Metoder för borttagning av extrema objekt försöker förbearbeta uppsättningen av mycket korrupta korrespondenser innan man uppskattar den rumsliga transformationen. Motivationen för borttagning av extremvärden är att avsevärt minska antalet avvikande överensstämmelser, samtidigt som inre överensstämmelser bibehålls, så att optimering över omvandlingen blir enklare och mer effektiv (t.ex. RANSAC fungerar dåligt när avvikande förhållandet är över $95\$ men presterar ganska bra när avvikande förhållande är under ${\displaystyle 50\%} )$ .

Parra et al. har föreslagit en metod som heter Guaranteed Outlier Removal (GORE) som använder geometriska begränsningar för att beskära outlier-överensstämmelser samtidigt som man garanterar att inre överensstämmelser bevaras. GORE har visat sig kunna drastiskt minska outlier-kvoten, vilket avsevärt kan öka prestandan för konsensusmaximering med RANSAC eller BnB. Yang och Carlone har föreslagit att bygga parvisa translations- och rotationsinvarianta mätningar (TRIM) från den ursprungliga uppsättningen av mätningar och bädda in TRIMs som kanterna på en graf vars noder är 3D-punkterna. Eftersom inliers är parvis konsekventa vad gäller skalan, måste de bilda en klick i grafen. Genom att använda effektiva algoritmer för att beräkna den maximala klicken i en graf kan man därför hitta inliers och effektivt beskära extremerna. Den maximala klickbaserade metoden för borttagning av extremvärden har också visat sig vara ganska användbar i verkliga problem med registrering av punktuppsättningar. Liknande idéer om avlägsnande av extremvärden föreslogs också av Parra et al. .

M-uppskattning

M-uppskattning ersätter minsta kvadratens objektiva funktion i ( cb.2 ) med en robust kostnadsfunktion som är mindre känslig för extremvärden. Formellt försöker M-estimation lösa följande problem:

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

 

 

 

 

()

där $\rho (\cdot )$ representerar valet av den robusta kostnadsfunktionen. Observera att om du väljer $\rho (x)=x^{2}$ återställs minsta kvadratuppskattningen i ( cb.2 ). Populära robusta kostnadsfunktioner inkluderar $\ell _{1}$ -normförlust, Huberförlust , Geman-McClure-förlust och trunkerad minsta kvadratförlust . M-uppskattning har varit ett av de mest populära paradigmen för robust uppskattning inom robotik och datorseende. Eftersom robusta objektivfunktioner vanligtvis är icke-konvexa ( t.ex. den trunkerade minsta kvadratförlusten kontra minsta kvadratförlusten), baseras algoritmer för att lösa den icke-konvexa M-uppskattningen typiskt på lokal optimering , där först en första gissning ges, efter genom iterativa förbättringar av transformationen för att fortsätta att minska den objektiva funktionen. Lokal optimering tenderar att fungera bra när den initiala gissningen är nära det globala minimum, men den är också benägen att fastna i lokala minima om den förses med dålig initiering.

Graderad icke-konvexitet

Graduated non-convexity (GNC) är ett generellt ramverk för att lösa icke-konvexa optimeringsproblem utan initiering. Den har nått framgång i applikationer för tidig vision och maskininlärning. Nyckelidén bakom GNC är att lösa det svåra icke-konvexa problemet genom att utgå från ett lätt konvext problem. Specifikt, för en given robust kostnadsfunktion ${\displaystyle \rho (\cdot )} ,$ kan man konstruera en surrogatfunktion $\rho _{\mu }(\cdot )$ med en hyperparameter $\mu$ , inställning som gradvis kan öka icke-konvexiteten för surrogatfunktionen $\rho _{\mu }(\cdot )$ tills den konvergerar till målfunktion $\rho (\cdot )$ . Därför, på varje nivå av hyperparametern $\mu$ , löses följande optimering:

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

 

 

 

 

()

Black och Rangarajan bevisade att den objektiva funktionen för varje optimering ( cb.6 ​​) kan dualiseras till en summa av viktade minsta kvadrater och en så kallad outlierprocessfunktion på de vikter som bestämmer tillförlitligheten för optimeringen i varje par av mått. Genom att använda Black-Rangarajan-dualitet och GNC skräddarsydd för Geman-McClure-funktionen, Zhou et al. utvecklat den snabba globala registreringsalgoritmen som är robust mot cirka $80\%$ extremvärden i korrespondenserna. På senare tid har Yang et al. visade att gemensam användning av GNC (skräddarsydd för Geman-McClure-funktionen och den trunkerade minsta kvadratfunktionen) och Black-Rangarajan-dualitet kan leda till en generell lösning för robusta registreringsproblem, inklusive punktmoln och mesh-registrering.

Säkert robust registrering

Nästan ingen av de robusta registreringsalgoritmerna som nämns ovan (förutom BnB-algoritmen som körs i exponentiell tid i värsta fall) kommer med prestandagarantier , vilket innebär att dessa algoritmer kan returnera helt felaktiga uppskattningar utan förvarning. Därför är dessa algoritmer oönskade för säkerhetskritiska tillämpningar som autonom körning.

Mycket nyligen har Yang et al. har utvecklat den första certifierbart robusta registreringsalgoritmen, som heter Truncated least squares Estimation And SEmidefinite Relaxation (TEASER). För punktmolnregistrering matar TEASER inte bara ut en uppskattning av transformationen, utan kvantifierar också optimaliteten för den givna uppskattningen. TEASER använder följande uppskattning av trunkerade minsta kvadrater (TLS):

$l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{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)$

 

 

 

 

()

som erhålls genom att välja TLS robust kostnadsfunktion $\rho (x)=\min(x^{2},{\bar {c}}^ {2})$ , där ${\bar {c}}^{2}$ är en fördefinierad konstant som bestämmer de maximalt tillåtna residualerna som ska betraktas som inliers. TLS-objektivfunktionen har egenskapen att för inlier överensstämmelser ( $\Vert s_{i}-lRm_{i}-t\ Vert _{2}^{2}/\sigma _{i}^{2}<{\bar {c}}^{2}$ ), det vanliga minsta kvadratstraffet tillämpas; medan för outlier-överensstämmelser ( $\Vert s_{i}-lRm_{i}-t\Vert _{2}^{ 2}/\sigma _{i}^{2}>{\bar {c}}^{2}$ ), ingen påföljd tillämpas och extremvärdena kasseras. Om TLS-optimeringen ( cb.7 ) löses till global optimalitet, är det likvärdigt med att köra Horns metod på endast de inre överensstämmelserna.

Men att lösa ( cb.7 ) är ganska utmanande på grund av dess kombinatoriska karaktär. TEASER löser ( cb.7 ) enligt följande: (i) Den bygger invarianta mätningar så att uppskattningen av skala, rotation och translation kan kopplas bort och lösas separat, en strategi som är inspirerad av den ursprungliga Horns metod; (ii) Samma TLS-uppskattning tillämpas för vart och ett av de tre delproblemen, där TLS-problemet i skalan kan lösas exakt med hjälp av en algoritm som kallas adaptiv röstning, rotations-TLS-problemet kan avslappnas till ett semidefinite program (SDP) där relaxationen är exakt i praktiken, även med stora mängder extremvärden; översättnings-TLS-problemet kan lösas med hjälp av komponentvis adaptiv röstning. En snabb implementering som utnyttjar GNC är öppen källkod här . I praktiken kan TEASER tolerera mer än $99\%$ outlier-överensstämmelser och körningar på millisekunder.

Förutom att utveckla TEASER har Yang et al. bevisar också att, under vissa milda förhållanden på punktmolnsdata, har TEASERs uppskattade transformation begränsat fel från grund-sanningstransformationen.

Samtidig posering och korrespondensregistrering

Iterativ närmaste punkt

Huvudartikel: Iterativ närmaste punkt

Den iterativa närmaste punkt -algoritmen (ICP) introducerades av Besl och McKay. Algoritmen utför stel registrering på ett iterativt sätt genom att alternera i (i) givet transformationen, hitta den närmaste punkten i ${\mathcal {S}}$ för varje punkt i ${\mathcal {M} }$ ; och (ii) givet överensstämmelserna, hitta den bästa stela transformationen genom att lösa problemet med minsta kvadrater ( cb.2 ). Som sådan fungerar det bäst om den initiala ställningen för ${\mathcal {M}}$ är tillräckligt nära ${\mathcal {S}}$ . I pseudokod implementeras den grundläggande algoritmen enligt följande:

 
    0
    
        
            
            
          algoritm  ICP(  M  ,  S  )  θ  :=  θ  medan den inte  är registrerad:  X  := ∅   för  m  i  ∊  T  (  M  ,  θ  ):  ŝ  j  := närmaste punkt i  S  till  m  i  X  :=  X  + ⟨  m  i  ,  ŝ  j  ⟩  θ  := minsta_kvadrat(  X  )  returnerar  θ 

utför funktionen minsta kvadrater optimering för att minimera avståndet i vart och ett av paren $\langle m_{i},{\hat {s}}_{j}\rangle$ , med hjälp av lösningarna i sluten form av Horn och Arun.

Eftersom kostnadsfunktionen för registrering beror på att hitta den närmaste punkten i ${\mathcal {S}}$ till varje punkt i ${\displaystyle {\mathcal {M}}} ,$ kan den ändras när algoritmen körs . Som sådan är det svårt att bevisa att ICP faktiskt kommer att konvergera exakt till det lokala optimum. I själva verket, empiriskt, konvergerar inte ICP och EM-ICP till kostnadsfunktionens lokala minimum. Icke desto mindre, eftersom ICP är intuitivt att förstå och enkelt att implementera, förblir det den mest använda punktuppsättningsregistreringsalgoritmen. Många varianter av ICP har föreslagits, som påverkar alla faser av algoritmen från urval och matchning av punkter till minimeringsstrategin. Till exempel tillämpas förväntningsmaximeringsalgoritmen på ICP-algoritmen för att bilda EM-ICP-metoden, och Levenberg -Marquardt-algoritmen tillämpas på ICP-algoritmen för att bilda LM-ICP-metoden.

Robust punktmatchning

Robust point matching (RPM) introducerades av Gold et al. Metoden utför registrering med användning av deterministisk glödgning och mjuk tilldelning av överensstämmelse mellan punktuppsättningar. Medan i ICP den överensstämmelse som genereras av den närmaste granne-heuristiken är binär, använder RPM en mjuk överensstämmelse där överensstämmelsen mellan två valfria punkter kan vara allt från 0 till 1, även om den i slutändan konvergerar till antingen 0 eller 1. Överensstämmelserna som finns i RPM är alltid en-till-en, vilket inte alltid är fallet i ICP. Låt $m_{i}$ vara ${\displaystyle i}:$ te punkten i ${\mathcal {M}}$ och $s_{j}$ vara ${\ displaystyle j}$ :te punkten i ${\mathcal {S}}$ . Matchningsmatrisen $mathbf {\mu } }$ \ definieras som sådan:

$motsvarar {\displaystyle \mu _{ij}={\begin{cases}1&{\text{om punkt }}m_{i}{\text{ att peka }}s_{j}\\0&{\text{annars}}\end{case}}}$

 

 

 

 

()

Problemet definieras då som: Med tanke på två punktuppsättningar ${\mathcal {M}}$ och ${\mathcal {S}}$ hitta den affina transformationen $T$ och matchningsmatrisen $\mathbf {\mu }$ som bäst relaterar dem. Att känna till den optimala transformationen gör det enkelt att bestämma matchningsmatrisen och vice versa. RPM-algoritmen bestämmer dock båda samtidigt. Transformationen kan delas upp i en translationsvektor och en transformationsmatris:

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

Matrisen $\mathbf {A}$ i 2D är sammansatt av fyra separata parametrar ${\displaystyle \lbrace a,\theta ,b,c\rbrace } ,$ som är skala, rotation och de vertikala respektive horisontella skjuvkomponenterna. Kostnadsfunktionen är då:

$\ operatornamn {kostnad} =\summa _{j=1}^{N}\summa _{i=1}^{M}\mu _{ij}\lVert s_{j}-\mathbf {t} -\mathbf {A} m_{i}\rVert ^{2}+g(\mathbf {A} )-\alpha \sum _{j=1}^{N}\summa _{i=1}^{M}\ mu _{ij}$

 

 

 

 

()

föremål för ${\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}\leq 1}$ , ${\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}\leq 1} , ∀$ i $textstyle \forall ij~\mu _{ij}\in \lbrace 0,1\rbrace }$ . Termen $\alpha$ riktar målet mot starkare korrelation genom att minska kostnaden om matchningsmatrisen har fler i sig. Funktionen $g(\mathbf {A} )$ tjänar till att reglera den affina transformationen genom att straffa stora värden på skalan och skjuvningskomponenterna:

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

för någon regulariseringsparameter $\gamma$ .

RPM-metoden optimerar kostnadsfunktionen med hjälp av Softassign-algoritmen. 1D-fallet kommer att härledas här. Givet en uppsättning variabler $\lbrace Q_{j}\rbrace$ där $Q_{j}\in \mathbb {R} ^{1}$ . En variabel $\mu _{j}$ är associerad med varje $Q_{j}$ så att ${\textstyle \sum _{j=1} ^{J}\mu _{j}=1}$ . Målet är att hitta $\mathbf {\mu }$ som maximerar ${\textstyle \sum _{j=1}^{J}\mu _{j}Q_{ j}}$ . Detta kan formuleras som ett kontinuerligt problem genom att införa en kontrollparameter $\beta >0$ . I den deterministiska glödgningsmetoden ökas kontrollparametern ${\displaystyle \beta } långsamt när algoritmen körs.$ Låt $\mathbf {\mu }$ vara:

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

 

 

 

 

()

detta kallas softmax-funktionen . När $\beta$ ökar, närmar det sig ett binärt värde som önskat i ekvation ( rpm.1 ). Problemet kan nu generaliseras till 2D-fallet, där istället för att maximera ${\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}$ , är följande maximerat:

$E(\mu )=\summa _{j=1}^{N}\summa _{i=0}^ {M}\mu _{ij}Q_{ij}$

 

 

 

 

()

var

$Q_{ij}=-(\lVert s_{j}-\mathbf {t} -\mathbf {A} m_{i}\rVert ^{2}-\alpha )=-{\frac {\partial \operatörsnamn {kostnad} }{\partial \mu _{ij}}}$

är begränsningarna på $\mu$ dubbelt stokastiska matrisbegränsningar : ${\textstyle \forall j~\summa _{i=1} ^{M}\mu _{ij}=1}$ och ${\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij }=1}$ . Som sådan kan nämnaren från ekvation ( rpm.3 ) inte enkelt uttryckas för 2D-fallet. För att tillfredsställa begränsningarna är det möjligt att använda ett resultat på grund av Sinkhorn, som säger att en dubbelstokastisk matris erhålls från vilken kvadratisk matris som helst med alla positiva poster genom den iterativa processen med alternerande rad- och kolumnnormaliseringar. Algoritmen är alltså skriven som sådan:

    
    
    
    
    
         
            
            
            
            
                
                
                
                
            
        
        
      algoritm RPM2D $({\mathcal {M}},{\mathcal {S}})$ t  := 0   a  ,  θ  b  ,  c  := 0  β  :=  β 0${\hat {\mu }}_{ij}:=1+\epsilon$  medan  β  <  β  f  :  medan  μ  inte har konvergerat:  // uppdatera korrespondensparametrar genom softassign ${\displaystyle Q_{ij}:=-{\frac {\partial \operatörsnamn {kostnad} }{\partial \mu _{ij}}}} μ$${\displaystyle \mu _{ij}^{0}:=\exp(\beta Q_{ij})} //$ tillämpa Sinkhorns metod   medan ${\hat {\mu }}$ har inte konvergerat:  // uppdatera ${\hat {\mu }}$ genom att normalisera över alla rader: ${ \displaystyle {\hat {\mu }}_{ij}^{1}:={\frac {{\hat {\mu }}_{ij}^{0}}{\sum _{i=1} ^{M+1}{\hat {\mu }}_{ij}^{0}}}}$ // uppdatera ${\hat {\mu }}$ genom att normalisera över alla kolumner: ${\displaystyle {\hat {\mu }}_{ij}^{0}:={\frac {{\hat { \mu }}_{ij}^{1}}{\sum _{j=1}^{N+1}{\hat {\mu }}_{ij}^{1}}}} //$ uppdatering poseringsparametrar genom koordinatnedstigningsuppdatering  θ  med  hjälp av analytisk lösningsuppdatering  t  med hjälp av analytisk lösningsuppdatering  a, b, c  med  Newtons metod $\beta :=\beta _{r}\beta$$\gamma :={\frac {\gamma }{\beta _{r}}}$ returnerar  a, b, c, θ  och  t 

där den deterministiska glödgningskontrollparametern $\beta$ initialt sätts till $\beta _{0}$ och ökar med faktorn $\beta _{r}$ tills den når maxvärdet $\beta _{f}$ . Summeringarna i normaliseringsstegen summerar till $M+1$ och $N+1$ istället för bara $M$ och $N$ eftersom begränsningarna på $\mu$ är ojämlikheter. Som sådana är ${\displaystyle M+1}:$ te och $N+1$ :e elementen slackvariabler .

Algoritmen kan även utökas för punktuppsättningar i 3D eller högre dimensioner. Begränsningarna på korrespondensmatrisen $\mathbf {\mu }$ är desamma i 3D-fallet som i 2D-fallet. Därför förblir strukturen på algoritmen oförändrad, med den största skillnaden är hur rotations- och translationsmatriserna löses.

Tunn platta spline robust spetsmatchning

Animation av 2D icke-styv registrering av den gröna punktuppsättningen ${\mathcal {M}}$ till den magentafärgade punktuppsättningen ${\mathcal {S}}$ skadad med bullriga extremvärden. Storleken på de blå cirklarna är omvänt relaterad till kontrollparametern $\beta$ . De gula linjerna indikerar korrespondens.

Algoritmen för robust punktmatchning (TPS-RPM) för tunn platt spline från Chui och Rangarajan utökar RPM-metoden för att utföra icke-rigid registrering genom att parametrisera transformationen som en tunn plattspline . Eftersom parametriseringen av tunnplåtspline endast existerar i tre dimensioner, kan emellertid metoden inte utvidgas till problem som involverar fyra eller flera dimensioner.

Kärnkorrelation

Kärnkorrelationsmetoden (KC) för punktuppsättningsregistrering introducerades av Tsin och Kanade. Jämfört med ICP är KC-algoritmen mer robust mot bullriga data. Till skillnad från ICP, där, för varje modellpunkt, endast den närmaste scenpunkten beaktas, här påverkar varje scenpunkt varje modellpunkt. Som sådan är detta en multipellänkad registreringsalgoritm. För vissa kärnfunktioner $K$ definieras kärnkorrelationen $KC$ av två punkter ${\displaystyle x_{i},x_{j}} så här:$

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

 

 

 

 

()

Kärnfunktionen $K$ som väljs för punktuppsättningsregistrering är vanligtvis symmetrisk och icke-negativ kärna, liknande de som används i Parzen- fönsterdensitetsuppskattningen . Gausskärnan används vanligtvis för sin enkelhet, även om andra som Epanechnikov-kärnan och tricube-kärnan kan ersättas . Kärnkorrelationen för en hel punktmängd ${\mathcal {\chi }}$ definieras som summan av kärnkorrelationerna för varje punkt i mängden till varannan punkt i mängden:

$KC({\mathcal {X}})=\summa _{i\neq j}KC(x_{i},x_{j})=2\summa _{i<j}KC(x_{i},x_{j})$

 

 

 

 

()

Logaritmen för KC för en punktmängd är proportionell, inom en konstant faktor, till informationsentropin . Observera att KC är ett mått på en "kompakthet" av punktuppsättningen - trivialt, om alla punkter i punktuppsättningen var på samma plats, skulle KC utvärderas till ett stort värde. Kostnadsfunktionen för punktuppsättningsregistreringsalgoritmen för någon transformationsparameter $\displaystyle \theta }$ { definieras så här:

$\operatörsnamn {kostnad} ({\mathcal {S}},{\ mathcal {M}},\theta )=-\summa _{m\in {\mathcal {M}}}\summa _{s\in {\mathcal {S}}}KC(s,T(m,\ theta ))$

 

 

 

 

()

Vissa algebraiska manipulationer ger:

$KC({\mathcal {S }}\cup T({\mathcal {M}},\theta ))=KC({\mathcal {S}})+KC(T({\mathcal {M}},\theta ))-2\operatörsnamn {kostnad} ({\mathcal {S}},{\mathcal {M}},\theta )$

 

 

 

 

()

Uttrycket förenklas genom att observera att $KC({\mathcal {S}})$ är oberoende av $\theta$ . Vidare, om man antar rigid registrering, $KC(T({\mathcal {M}},\theta ))$ invariant när $\theta$ ändras eftersom Euklidiskt avstånd mellan varje par av punkter förblir detsamma under stel transformation . Så ovanstående ekvation kan skrivas om som:

$KC({\mathcal {S}}\cup T({\mathcal {M}},\ theta ))=C-2\operatörsnamn {kostnad} ({\mathcal {S}},{\mathcal {M}},\theta )$

 

 

 

 

()

Uppskattningarna av kärndensitet är definierade som:

$P_{\mathcal {M}}(x,\theta )={\frac {1}{ M}}\summa _{m\in {\mathcal {M}}}K(x,T(m,\theta ))$

${ \displaystyle P_{\mathcal {S}}(x)={\frac {1}{N}}\summa _{s\in {\mathcal {S}}}K(x,s)}$

Kostnadsfunktionen kan sedan visas vara korrelationen mellan de två kärndensitetsuppskattningarna:

${\displaystyle \operatörsnamn {kostnad} ({\mathcal {S}},{\mathcal {M}},\theta$

 

 

 

 

()

Efter att ha etablerat kostnadsfunktionen använder algoritmen helt enkelt gradientnedstigning för att hitta den optimala transformationen. Det är beräkningsmässigt dyrt att beräkna kostnadsfunktionen från början vid varje iteration, så en diskret version av kostnadsfunktionen Ekvation ( kc.6 ) används. Kärndensitetsuppskattningarna $P_{\mathcal {M}}, P_{\mathcal {S}}$ utvärderas vid rutnätspunkter och lagras i en uppslagstabell . Till skillnad från ICP och relaterade metoder är det inte nödvändigt att hitta närmaste granne, vilket gör att KC-algoritmen är jämförelsevis enkel att implementera.

Jämfört med ICP och EM-ICP för bullriga 2D- och 3D-punktuppsättningar är KC-algoritmen mindre känslig för brus och resulterar i korrekt registrering oftare.

Gaussisk blandningsmodell

Kärndensitetsuppskattningarna är summor av Gausser och kan därför representeras som Gaussiska blandningsmodeller ( GMM). Jian och Vemuri använder GMM-versionen av KC-registreringsalgoritmen för att utföra icke-rigid registrering parametriserad av tunna plattsplines .

Sammanhängande punktdrift

Stel (med tillägg av skalning) registrering av en blå punktuppsättning ${\mathcal {M}}$ till den röda punktuppsättningen ${\mathcal {S}}$ med hjälp av Coherent Point Drift-algoritmen. Båda poänguppsättningarna har skadats med borttagna punkter och slumpmässiga falska avvikande punkter.

Affin registrering av en blå punktuppsättning ${\mathcal {M}}$ till den röda punktuppsättningen ${\mathcal {S}}$ med hjälp av Coherent Point Drift-algoritmen.

Icke-rigid registrering av en blå punktuppsättning ${\mathcal {M}}$ till den röda punktuppsättningen ${\mathcal {S}}$ med hjälp av Coherent Point Drift-algoritmen. Båda poänguppsättningarna har skadats med borttagna punkter och slumpmässiga falska avvikande punkter.

Coherent point drift (CPD) introducerades av Myronenko och Song. Algoritmen tar ett probabilistiskt tillvägagångssätt för att justera punktuppsättningar, liknande GMM KC-metoden. Till skillnad från tidigare tillvägagångssätt för icke-styv registrering som antar en med tunn plattspline, är CPD agnostisk med avseende på den använda transformationsmodellen. Punktuppsättningen ${\mathcal {M}}$ representerar centroider för Gaussisk blandningsmodell (GMM). När de två punktuppsättningarna är optimalt inriktade, är överensstämmelsen det maximala för GMM:s posteriora sannolikhet för en given datapunkt. För att bevara den topologiska strukturen av punktuppsättningarna, tvingas GMM-centroiderna att röra sig koherent som en grupp. för förväntningsmaximering används för att optimera kostnadsfunktionen.

Låt det finnas M punkter i ${\mathcal {M}}$ och N punkter i ${\mathcal {S}}$ . GMM- sannolikhetstäthetsfunktionen för en punkt s är:

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

 

 

 

 

()

där, i D- dimensioner, $p(s|i)$ är den Gaussiska fördelningen centrerad på punkten $m_{i}\in {\mathcal {M}}$ .

$p(s|i)={\frac {1}{( 2\pi \sigma ^{2})^{D/2}}}\exp {\left(-{\frac {\lVert s-m_{i}\rVert ^{2}}{2\sigma ^{ 2}}}\right)}$

Medlemskapssannolikheterna $P(i)={\frac {1}{M}}$ är lika för alla GMM-komponenter. Vikten av den enhetliga fördelningen anges som $w\in [0,1]$ . Blandningsmodellen är då:

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

 

 

 

 

()

GMM-centroiderna omparametriseras av en uppsättning parametrar $\theta$ uppskattade genom att maximera sannolikheten. Detta motsvarar att minimera den negativa log-likelihood-funktionen :

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

 

 

 

 

()

där det antas att uppgifterna är oberoende och identiskt distribuerade . Överensstämmelsesannolikheten mellan två punkter $m_{i}$ och $s_{j}$ definieras som den bakre sannolikheten för GMM-centroiden givet datapunkten:

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

för förväntningsmaximering ( EM) används för att hitta $\theta$ och $\sigma ^{2}$ . EM-algoritmen består av två steg. Först, i E-steget eller uppskattningssteget , gissar den parametrarnas värden ("gamla" parametervärden) och använder sedan Bayes sats för att beräkna de bakre sannolikhetsfördelningarna $P^{ \text{old}}(i,s_{j})$ av blandningskomponenter. För det andra, i M-steget eller maximeringssteget , hittas sedan de "nya" parametervärdena genom att minimera förväntan på den fullständiga negativa log-sannolikhetsfunktionen, dvs kostnadsfunktionen:

$\operatörsnamn {kostnad} =- \sum _{j=1}^{N}\summa _{i=1}^{M+1}P^{\text{gammal}}(i|s_{j})\log(P^{\ text{new}}(i)p^{\text{new}}(s_{j}|i))$

 

 

 

 

()

Om man ignorerar konstanter oberoende av $\theta$ och $\sigma$ , kan ekvation ( cpd.4 ) uttryckas så här:

$\operatörsnamn {kostnad} (\theta ,\sigma ^{2})={\frac {1}{2\sigma ^{2}}}\summa _{j=1}^ {N}\summa _{i=1}^{M+1}P^{\text{gammal}}(i|s_{j})\lVert s_{j}-T(m_{i},\theta )\rVert ^{2}+{\frac {N_{\mathbf {P} }D}{2}}\log {\sigma ^{2}}$

 

 

 

 

()

var

$N_{\mathbf {P} }=\summa _{j=0}^{N}\summa _{i =0}^{M}P^{\text{gammal}}(i|s_{j})\leq N$

med $N=N_{\mathbf {P} }$ endast om $w=0$ . De bakre sannolikheterna för GMM-komponenter beräknade med tidigare parametervärden $P^{\text{old}}$ är:

$P^{\text{old}}(i|s_{j})={\ frac {\exp \left(-{\frac {1}{2\sigma ^{{\text{gammal}}2}}}\lVert s_{j}-T(m_{i},\theta ^{\ text{gammal}})\rVert ^{2}\right)}{\sum _{k=1}^{M}\exp \left(-{\frac {1}{2\sigma ^{{\text {gammal}}2}}}\lVert s_{j}-T(m_{k},\theta ^{\text{gammal}})\rVert ^{2}\right)+(2\pi \sigma ^ {2})^{\frac {D}{2}}{\frac {w}{1-w}}{\frac {M}{N}}}}$

 

 

 

 

()

Att minimera kostnadsfunktionen i ekvation ( cpd.5 ) minskar nödvändigtvis den negativa log-likelihood-funktionen E i ekvation ( cpd.3 ) om den inte redan är på ett lokalt minimum. Algoritmen kan alltså uttryckas med hjälp av följande pseudokod, där punktmängderna ${\mathcal {M}}$ och ${\mathcal {S}}$ representeras som $M\times D$ och $N\times D$ matriser $\mathbf {M}$ respektive $\mathbf {S}$ :

    
    
    
    
        
            
        
        
      algoritm CPD $({\mathcal {M}},{\mathcal {S}})$ θ  :=  θ 0 initiera 0 ≤  w  ≤ 1 $\sigma ^{2}:={\frac {1}{DNM}}\summa _{j=1}^{N}\summa _ {i=1}^{M}\lVert s_{j}-m_{i}\rVert ^{2}$ medan det  inte är registrerat:  // E-steg, beräkna  P   för  i  ∊ [1,  M  ] och  j  ∊ [1,  N  ]: ${\displaystyle p_{ij}:={\frac {\exp \left(-{\frac {1} {2\sigma ^{2}}}\lVert s_{j}-T(m_{i},\theta )\rVert ^{2}\right)}{\sum _{k=1}^{M} \exp \left(-{\frac {1}{2\sigma ^{2}}}\lVert s_{j}-T(m_{k},\theta )\rVert ^{2}\right)+( 2\pi \sigma ^{2})^{\frac {D}{2}}{\frac {w}{1-w}}{\frac {M}{N}}}}} //$ M- steg, lös för optimal transformation  {  θ  ,  σ  2  } :=  lös  (  S  ,  M  ,  P  )  return  θ 

där vektorn $\mathbf {1}$ är en kolumnvektor av ettor. Lösningsfunktionen skiljer sig åt beroende på vilken typ av registrering som utförs . Till exempel, i rigid registrering är utdata en skala a , en rotationsmatris $\mathbf {R}$ och en translationsvektor $\mathbf {t}$ . Parametern $\theta$ kan skrivas som en tuppel av dessa:

$\theta =\lbrace a,\mathbf {R} ,\mathbf {t} \rbrace$

som initieras till ett, identitetsmatrisen och en kolumnvektor med nollor:

$\theta _{0}=\lbrace 1,\mathbf {I} ,\mathbf {0} \rbrace$

Den justerade punktuppsättningen är:

$T(\mathbf {M} )=a\mathbf {M} \mathbf {R} ^{T}+\mathbf {1} \mathbf {t } ^{T}$

solve_rigid - funktionen för rigid registrering kan sedan skrivas på följande sätt, med härledning av algebra förklarad i Myronenkos 2010-uppsats.

    
    
    
    
    
    
     
     
    
       
    
    
     solve_rigid  (  S  ,  M  ,  P  )  N  P  :=  1  T  P1 $\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} } S ^$$\ displaystyle {\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}} M ^ :=$${ \hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}} A := S T ^$${ A} :={\hat {\mathbf {S} ^{T}}}\mathbf {P} ^{T}{\hat {\mathbf {M} }}} U$ ,  V  :  =  svd  (  A  )   / /  singularvärdesuppdelningen  av  A  =  UΣV  T  C  := diag(1, …, 1, det(  UV  T  ))  //  diag(  ξ  )  är den  diagonala matrisen  som bildas av vektorn ξ  R  :=  UCV  T $a:={\frac {\operatörsnamn {tr} (\mathbf {A} ^{T}\mathbf {R } )}{\operatörsnamn {tr} (\mathbf {{\hat {\mathbf {M} }}^{T}\operatörsnamn {diag} (\mathbf {P} \mathbf {1} ){\hat {\ mathbf {M} }}} )}}$ //  tr  är  spåret  av en matris  t  :=  μ  s  −  a  R  μ  m $\sigma ^{2}:={\frac {1}{N_{\mathbf {P} }D}}(\operatörsnamn {tr} (\mathbf {{\hat {\mathbf {S} }}^{T}\operatörsnamn {diag} (\mathbf {P} ^{T}\mathbf {1} ){\hat {\mathbf {S} } }} )-a\operatörsnamn {tr} (\mathbf {A} ^{T}\mathbf {R} ))$ returnera  {  a  ,  R  ,  t  },  σ  2 

För affin registrering, där målet är att hitta en affin transformation istället för en stel, är utdata en affin transformationsmatris $\mathbf {B}$ och en översättning $\mathbf {t}$ såsom att den justerade punktuppsättningen är:

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

Funktionen solve_affine för stel registrering kan sedan skrivas på följande sätt, med härledning av algebra förklarad i Myronenkos 2010-uppsats.

    
    
    
    
    
    
    
    
     solve_affine  (  S  ,  M  ,  P  )  N  P  :=  1  T  P1 $\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} } S ^$$\ displaystyle {\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}} M ^ :=$${ \hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}} B$$\mathbf {B} :=({\hat {\mathbf {S} }}^{T}\mathbf {P} ^{T}{\hat { \mathbf {M} }})({\hat {\mathbf {M} }}^{T}\operatörsnamn {diag} (\mathbf {P} \mathbf {1} ){\hat {\mathbf {M} }})^{-1}$ t  :=  μ  s  −  B  μ  m $\sigma ^{2}:={\frac {1}{N_{\mathbf {P} }D}}(\operatörsnamn {tr} ({\hat {\mathbf {S} }}^{T}\operatörsnamn {diag} (\mathbf {P} ^{T}\mathbf {1} ){\hat {\mathbf {S} }})-\operatörsnamn {tr} ({ \hat {\mathbf {S} }}^{T}\mathbf {P} ^{T}{\hat {\mathbf {M} }}\mathbf {B} ^{T}))$ returnera  {  B  ,  t  },  σ  2 

Det är också möjligt att använda CPD med icke-rigid registrering med hjälp av en parametrisering härledd med hjälp av variationskalkyl .

Summor av Gauss-fördelningar kan beräknas i linjär tid med hjälp av den snabba Gauss-transformen (FGT). Följaktligen tidskomplexiteten för CPD ${\displaystyle O(M+N)} , vilket är asymptotiskt mycket$$) {\displaystyle O(MN)}$ än metoder.

Bayesian coherent point drift (BCPD)

En variant av koherent punktdrift, kallad Bayesian coherent point drift (BCPD), härleddes genom en Bayesiansk formulering av punktuppsättningsregistrering. BCPD har flera fördelar jämfört med CPD, t.ex. (1) icke-rigida och stela registreringar kan utföras i en enda algoritm, (2) algoritmen kan accelereras oavsett Gaussianiteten hos en Gram-matris för att definiera rörelsekoherens, (3) algoritmen är mer robust mot extremvärden på grund av en mer rimlig definition av en extremfördelning. Dessutom, i den Bayesianska formuleringen, introducerades rörelsekoherens genom en tidigare fördelning av förskjutningsvektorer, vilket ger en tydlig skillnad mellan avstämningsparametrar som styr rörelsekoherens. BCPD accelererades ytterligare av en metod som kallas BCPD++, som är en trestegsprocedur som består av (1) nedsampling av punktuppsättningar, (2) registrering av nedsamplade punktuppsättningar och (3) interpolering av ett deformationsfält. Metoden kan registrera punktuppsättningar som består av mer än 10 miljoner punkter samtidigt som dess registreringsnoggrannhet bibehålls.

Koherent punktdrift med lokal ytgeometri (LSG-CPD)

En variant av koherent punktdrift kallad CPD with Local Surface Geometry (LSG-CPD) för rigid punktmolnregistrering. Metoden lägger adaptivt till olika nivåer av punkt-till-plan-bestraffning ovanpå punkt-till-punkt-bestraffningen baserat på den lokala ytans planhet. Detta resulterar i GMM-komponenter med anisotropa kovarianser, istället för de isotropa kovarianserna i den ursprungliga CPD. Den anisotropa kovariansmatrisen modelleras som:

$\Sigma _{m}^{-1}={\frac {1}{\sigma ^{2}}}\ vänster(\alpha _{m}\mathbf {n} _{m}\mathbf {n} _{m}^{T}+\mathbf {I} \right)$

 

 

 

 

()

var

$\alpha _{m}={\frac {1 -\exp \left(\lambda \left(3-{\frac {1}{\kappa _{m}}}\right)\right)}{1+\exp \left(\lambda \left(3- {\frac {1}{\kappa _{m}}}\right)\right)}}\alpha _{max}$

 

 

 

 

()

$\Sigma _{m}$ är den anisotropiska kovariansmatrisen för den m:te punkten i måluppsättningen; $\mathbf {n} _{m}$ är normalvektorn som motsvarar samma punkt; $\mathbf {I}$ är en identitetsmatris, som fungerar som en regularizer, som drar bort problemet från illa ställda. $\alpha _{m}$ är penaliseringskoefficient (en modifierad sigmoidfunktion), som ställs in adaptivt för att lägga till olika nivåer av punkt-till-plan penalisering beroende på hur platt den lokala ytan är. Detta realiseras genom att utvärdera ytvariationen $\kappa _{m}$ i närheten av den m:te målpunkten. $\alpha _{max}$ är den övre gränsen för bestraffningen.

Punktmolnregistreringen är formulerad som ett problem med maximal sannolikhetsuppskattning (MLE) och lös det med algoritmen Expectation-Maximization (EM). I E-steget omarbetas korrespondensberäkningen till enkla matrismanipulationer och beräknas effektivt på en GPU. I M-steget är en obegränsad optimering på en matris Lie-grupp utformad för att effektivt uppdatera den stela transformationen av registreringen. Genom att dra fördel av de lokala geometriska kovarianserna visar metoden en överlägsen prestanda i noggrannhet och robusthet mot brus och extremvärden, jämfört med baslinjens CPD. En förbättrad körtidsprestanda förväntas tack vare den accelererade GPU-korrespondensberäkningen. En implementering av LSG-CPD är öppen källkod här .

Sortera korrespondensutrymmet (SCS)

Denna algoritm introducerades 2013 av H. Assalih för att tillgodose registrering av ekolodsbilder. Dessa typer av bilder tenderar att ha höga mängder brus, så det förväntas ha många extremvärden i punktuppsättningarna för att matcha. SCS ger hög robusthet mot extremvärden och kan överträffa ICP- och CPD-prestanda i närvaro av extremvärden. SCS använder inte iterativ optimering i högdimensionellt utrymme och är varken probabilistisk eller spektral. SCS kan matcha stela och icke-styva transformationer och presterar bäst när måltransformationen är mellan tre och sex frihetsgrader .

Se även

• Punktfunktionsmatchning
• Point-set triangulering
• Normalfördelningar transformeras

externa länkar

• Referensimplementering av tunn platta spline robust punktmatchning
• Referensimplementering av registrering av kärnkorrelationspunktuppsättning
• Referensimplementering av koherent punktdrift
• Referensimplementering av ICP-varianter
• Referensimplementering av Bayesiansk koherent punktdrift
• Referensimplementering av LSG-CPD