Semi-global matchning

Semi-global matchning ( SGM ) är en datorseende algoritm för uppskattning av en tät olikhetskarta från ett likriktat stereobildspar , introducerad 2005 av Heiko Hirschmüller när han arbetade på German Aerospace Center . Med tanke på dess förutsägbara körtid, dess gynnsamma avvägning mellan kvalitet på resultaten och beräkningstid, och dess lämplighet för snabb parallell implementering i ASIC eller FPGA , har den stött på bred användning i realtids stereovision-applikationer som robotik och avancerad drivrutin assistanssystem .

Problem

Pixelvis stereomatchning gör det möjligt att utföra realtidsberäkning av disparitetskartor genom att mäta likheten mellan varje pixel i en stereobild och varje pixel inom en delmängd i den andra stereobilden. Givet ett likriktat stereobildspar, för en pixel med koordinater $(x,y)$ väljs uppsättningen pixlar i den andra bilden vanligtvis som $\{({\hat {x}},y)|{\hat {x}}\geq x,{\hat {x}}\leq x +D\}$ , där $D$ är en maximal tillåten disparitetsförskjutning.

En enkel sökning efter den bäst matchande pixeln ger många falska matchningar, och detta problem kan mildras med tillägget av en regleringsterm som straffar hopp i olikhet mellan intilliggande pixlar, med en kostnadsfunktion i formen

$E({\boldsymbol {d}})=\summa _ {p}D(p,d_{p})+\summa _{p,q\in {\mathcal {N}}}R(p,d_{p},q,d_{q})$

där $D(p,d_{p})$ är den pixelmässiga skillnadskostnaden vid pixel $p$ med disparitet $d_{p}$ , och $R(p,d_{p},q,d_{q})$ är regulariseringskostnaden mellan pixlar $p$ och $q$ med dispariteter $d_{p}$ respektive $d_{q}$ , för alla par av närliggande pixlar ${\mathcal {N}}$ . Sådana restriktioner kan effektivt upprätthållas på en per-scanline-basis genom att använda dynamisk programmering (t.ex. Viterbi-algoritmen ), men en sådan begränsning kan fortfarande introducera streckartefakter i djupkartan, eftersom liten eller ingen regularisering utförs över skanningslinjer.

En möjlig lösning är att utföra global optimering i 2D, vilket dock är ett NP-komplett problem i det allmänna fallet. För vissa familjer av kostnadsfunktioner (t.ex. submodulära funktioner ) kan en lösning med starka optimalitetsegenskaper hittas i polynomtid med användning av grafsnittsoptimering , men sådana globala metoder är i allmänhet för dyra för realtidsbearbetning.

Algoritm

Illustration av kostnadsackumuleringsmönstret vid beräkning av två-pass SGM med åtta riktningar.

Tanken bakom SGM är att utföra linjeoptimering längs flera riktningar och beräkna en aggregerad kostnad $S(p,d)$ genom att summera kostnaderna för att nå pixel $p$ med disparitet ${ \displaystyle d}$ från varje riktning. Antalet riktningar påverkar körtiden för algoritmen, och medan 16 riktningar vanligtvis säkerställer god kvalitet, kan ett lägre antal användas för att uppnå snabbare exekvering. En typisk 8-riktningsimplementering av algoritmen kan beräkna kostnaden i två omgångar, ett framåtpass som ackumulerar kostnaden från vänster, uppe-vänster, topp och uppe-höger, och ett bakåtpass som ackumulerar kostnaden från höger, botten- höger, botten och botten-vänster. En enkelpassagealgoritm kan implementeras med endast fem riktningar.

Kostnaden är sammansatt av en matchande term $D(p,d)$ och en binär regulariseringsterm $R(d_{p},d_{q })$ . Den förra kan i princip vara vilken lokal bildskillnad som helst, och vanliga funktioner är absolut eller kvadratisk intensitetsskillnad (vanligtvis summerad över ett fönster runt pixeln och efter att ha applicerat ett högpassfilter på bilderna för att få en viss belysningsinvarians ) . Birchfield–Tomasi olikhet , Hamming-avstånd för censustransformen , Pearson-korrelation ( normaliserad korskorrelation) . Även ömsesidig information kan approximeras som en summa över pixlarna och därmed användas som ett lokalt likhetsmått. Regleringstermen har formen

$R(d_{p},d_{q})={\begin{cases}0\quad &d_{p}=d_{q}\\P_{1}&|d_{p}-d_ {q}|=1\\P_{2}&|d_{p}-d_{q}|>1\end{fall}}$

där $P_{1}$ och $P_{2}$ är två konstanta parametrar, med $P_{1}<P_{2}$ . Trevägsjämförelsen gör det möjligt att tilldela ett mindre straff för enhetliga förändringar i disparitet, vilket möjliggör mjuka övergångar motsvarande t.ex. lutande ytor, och straffar större hopp samtidigt som diskontinuiteter bevaras på grund av den konstanta strafftiden. För att ytterligare bevara diskontinuiteter kan gradienten av intensiteten användas för att anpassa strafftermen, eftersom diskontinuiteter i djupet vanligtvis motsvarar en diskontinuitet i bildintensitet I {\ $I}$ , genom att ställa in

$P_{2}=\max \left\{P_{1},{\frac {{\hat {P}}_{2}}{|I(p)-I(q)|}} \höger\}$

för varje pixelpar $p$ och $q$ .

Den ackumulerade kostnaden $S(p,d)=\summa _{r}L_{r}(p,d)$ är summan av alla kostar $L_{r}(p,d)$ för att nå pixel $p$ med disparitet $d$ längs riktningen $r$ . Varje term kan uttryckas rekursivt som

$L_{r}(p,d)=D(p ,d)+\min \left\{L_{r}(pr,d),L_{r}(pr,d-1)+P_{1},L_{r}(pr,d+1)+P_ {1},\min _{i}L_{r}(pr,i)+P_{2}\right\}-\min _{k}L_{r}(pr,k)$

där minimikostnaden vid föregående pixel $\min _{k}L_{r}(pr,k)$ subtraheras för numerisk stabilitet, eftersom den är konstant för alla skillnader vid den aktuella pixeln och därför påverkar det inte optimeringen.

Värdet på skillnaden vid varje pixel ges av $d^{*}(p)=\operatörsnamn {argmin} _{d}S(p, d)$ , och subpixelnoggrannhet kan uppnås genom att anpassa en kurva i $d^{*}(p)$ och dess närliggande kostnader och ta minimum längs kurvan. Eftersom de två bilderna i stereoparet inte behandlas symmetriskt i beräkningarna, kan en konsistenskontroll utföras genom att beräkna dispariteten en andra gång i motsatt riktning, byta roll för vänster och höger bild och ogiltigförklara resultatet för pixlar där resultatet skiljer sig mellan de två beräkningarna. Ytterligare efterbehandlingstekniker för förfining av disparitetsbilden inkluderar morfologisk filtrering för att ta bort extremvärden, intensitetskonsistenskontroller för att förfina texturlösa regioner och interpolering för att fylla i pixlar som ogiltigförklarats av konsistenskontroller.

Kostnadsvolymen $C(p,d)$ för alla värden på $p=(x,y)$ och $d$ kan vara förberäknad och i en implementering av den fullständiga algoritmen, med användning av $D$ möjliga disparitetsförskjutningar och $R$ -riktningar, besöks varje pixel därefter $R$ gånger, därför är algoritmens beräkningskomplexitet för en bild med storleken $W\times H$ är $O(WHD)$ .

Minneseffektiv variant

Den största nackdelen med SGM är dess minnesförbrukning. En implementering av två-pass 8-riktningar versionen av algoritmen kräver att lagra $W\ gånger H\ gånger D+3\ gånger W\ gånger D+D$ element, eftersom den ackumulerade kostnadsvolymen har storleken $W\times H\times D$ och för att beräkna kostnaden för en pixel under varje pass är det nödvändigt att hålla reda på ${\ displaystyle D}$ -vägkostnader för dess vänstra eller högra granne längs en riktning och för $W\times D$ -vägkostnaderna för pixlarna i raden ovanför eller under längs 3 riktningar. En lösning för att minska minnesförbrukningen är att beräkna SGM på delvis överlappande bildrutor och interpolera värdena över de överlappande regionerna. Denna metod gör det också möjligt att tillämpa SGM på mycket stora bilder, som inte skulle passa i minnet i första hand.

En minneseffektiv approximation av SGM lagrar för varje pixel endast kostnaderna för de disparitetsvärden som representerar ett minimum längs någon riktning, istället för alla möjliga disparitetsvärden. Det sanna minimumet kommer med stor sannolikhet att förutsägas av minima längs de åtta riktningarna, vilket ger liknande kvalitet på resultaten. Algoritmen använder åtta riktningar och tre pass, och under den första passagen lagrar den för varje pixel kostnaden för den optimala skillnaden längs de fyra top-down-riktningarna, plus de två närmaste lägre och högre värdena (för sub-pixel interpolation). Eftersom kostnadsvolymen lagras på ett sparsamt sätt måste de fyra värdena för optimal olikhet också lagras. I det andra passet beräknas de andra fyra nedifrån-och-upp-riktningarna, vilket slutför beräkningarna för de fyra disparitetsvärdena valda i det första passet, som nu har utvärderats längs alla åtta riktningarna. Ett mellanvärde av kostnad och disparitet beräknas från utsignalen från det första passet och lagras, och minnet för de fyra utsignalerna från det första passet ersätts med de fyra optimala disparitetsvärdena och deras kostnader från riktningarna i det andra passet. En tredje passage går igen längs samma riktningar som användes i den första passagen, och slutför beräkningarna för skillnadsvärdena från den andra passagen. Det slutliga resultatet väljs sedan bland de fyra minima från det tredje passet och det mellanliggande resultatet beräknas under det andra passet.

I varje pass lagras fyra disparitetsvärden, tillsammans med tre kostnadsvärden vardera (minsta och dess två närmaste angränsande kostnader), plus skillnaden och kostnadsvärdena för det mellanliggande resultatet, för totalt arton värden för varje pixel, vilket gör den totala minnesförbrukning lika med ${\displaystyle 18\ gånger W\ gånger H+3\ gånger W\ gånger D+D} ,$ till kostnaden i tid för en extra pass över bild.

Se även

• 3D-rekonstruktion
• Dator stereo vision
• Struktur från rörelse

• Hirschmüller, Heiko (2005). "Exakt och effektiv stereobehandling genom halvglobal matchning och ömsesidig information". IEEE-konferens om datorseende och mönsterigenkänning . s. 807–814.
•   Hirschmuller, Heiko (2007). "Stereobehandling genom semiglobal matchning och ömsesidig information". IEEE-transaktioner på mönsteranalys och maskinintelligens . IEEE. 30 (2): 328–341. doi : 10.1109/TPAMI.2007.1166 . PMID 18084062 .
• Hirschmüller, Heiko (2011). "Halvglobal matchning-motivation, utvecklingar och tillämpningar". Fotogrammetrisk vecka . Vol. 11. s. 173–184.
• Hirschmüller, Heiko; Buder, Maximilian; Ernst, Ines (2012). "Minneseffektiv semi-global matchning" . ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences . 3 : 371-376. Bibcode : 2012ISPAn..I3..371H . doi : 10.5194/isprsannals-I-3-371-2012 .
• Kim, Junhwan; Kolmogorov, Vladimir; Zabih, Ramin (2003). "Visuell korrespondens med energiminimering och ömsesidig information". Proceedings of the Ninth IEEE International Conference on Computer Vision . s. 1033–1040.
• Spangenberg, Robert; Langner, Tobias; Rojas, Raúl (2013). "Viktad semi-global matchning och centrumsymmetrisk folkräkningstransformering för robust förarassistans". Internationell konferens om datoranalys av bilder och mönster . s. 34–41.

externa länkar

• "Stereovision" . Arkiverad från originalet 2019-01-01.