Implementering av skalutrymme - Scale space implementation

Inom områdena datorsyn , bildanalys och signalbehandling används begreppet skala-rymdrepresentation för att bearbeta mätdata i flera skalor, och specifikt förbättra eller undertrycka bildfunktioner över olika skalområden (se artikeln om skalutrymme ) . En särskild typ av skala-rymdrepresentation tillhandahålls av det gaussiska skalrummet, där bilddata i N- dimensioner utsätts för utjämning av Gauss- konvolvering . Det mesta av teorin för Gaussskala rymden handlar om kontinuerliga bilder, medan en vid implementering av denna teori måste möta det faktum att de flesta mätdata är diskreta. Därför uppstår det teoretiska problemet om hur man diskretiserar den kontinuerliga teorin samtidigt som man antingen bevarar eller väl närmar sig de önskvärda teoretiska egenskaperna som leder till valet av den gaussiska kärnan (se artikeln om axiom för skalutrymme ). Denna artikel beskriver grundläggande tillvägagångssätt för detta som har utvecklats i litteraturen.

Redogörelse av problemet

Den Gaussisk skala-space representation av en N dimensionell kontinuerlig signal,

${\ displaystyle f_ {C} \ vänster (x_ {1}, \ cdots, x_ {N}, t \ höger),}$

erhålls genom att konvegera f _C med en N -dimensionell Gaussisk kärna :

${\ displaystyle g_ {N} \ vänster (x_ {1}, \ cdots, x_ {N}, t \ höger).}$

Med andra ord:

${\ displaystyle L \ left (x_ {1}, \ cdots, x_ {N}, t \ right) = \ int _ {u_ {1} =-\ infty}^{\ infty} \ cdots \ int _ {u_ {N} =-\ infty}^{\ infty} f_ {C} \ vänster (x_ {1} -u_ {1}, \ cdots, x_ {N} -u_ {N}, t \ höger) \ cdot g_ {N} \ vänster (u_ {1}, \ cdots, u_ {N}, t \ höger) \, du_ {1} \ cdots du_ {N}.}$

För implementering är denna definition dock opraktisk, eftersom den är kontinuerlig. När man applicerar skalutrymme -konceptet på en diskret signal f _D kan olika tillvägagångssätt tas. Denna artikel är en kort sammanfattning av några av de mest använda metoderna.

Separerbarhet

Använda separationsegenskapen för den gaussiska kärnan

${\ displaystyle g_ {N} \ left (x_ {1}, \ dots, x_ {N}, t \ right) = G \ left (x_ {1}, t \ right) \ cdots G \ left (x_ {N }, t \ höger)}$

den N -dimensionella faltning drift kan delas upp i en uppsättning av separerbara utjämningssteg med en endimensionell Gausskärna G längs varje dimension

${\ displaystyle L (x_ {1}, \ cdots, x_ {N}, t) = \ int _ {u_ {1} =-\ infty}^{\ infty} \ cdots \ int _ {u_ {N} = -\ infty}^{\ infty} f_ {C} (x_ {1} -u_ {1}, \ cdots, x_ {N} -u_ {N}, t) G (u_ {1}, t) \, du_ {1} \ cdots G (u_ {N}, t) \, du_ {N},}$

var

${\ displaystyle G (x, t) = {\ frac {1} {\ sqrt {2 \ pi t}}} e^{-{\ frac {x^{2}} {2t}}}}$

och standardavvikelsen för den gaussiska σ är relaterad till skalparametern t enligt t = σ ² .

Avskiljbarhet kommer att antas i allt som följer, även när kärnan inte är exakt Gaussisk, eftersom separering av dimensionerna är det mest praktiska sättet att genomföra flerdimensionell utjämning, särskilt i större skalor. Därför fokuserar resten av artikeln på det endimensionella fallet.

Den provtagna Gauss -kärnan

Vid genomförandet av det endimensionella utjämningssteget i praktiken är det förmodligen enklaste tillvägagångssättet att förena den diskreta signalen f _D med en samplad Gaussisk kärna :

${\ displaystyle L (x, t) = \ sum _ {n =-\ infty}^{\ infty} f (xn) \, G (n, t)}$

var

${\ displaystyle G (n, t) = {\ frac {1} {\ sqrt {2 \ pi t}}} e^{-{\ frac {n^{2}} {2t}}}}$

(med t = σ ² ) som i sin tur avkortas i ändarna för att ge ett filter med ändligt impulssvar

${\ displaystyle L (x, t) = \ sum _ {n = -M}^{M} f (xn) \, G (n, t)}$

för M valt tillräckligt stort (se felfunktion ) så att

${\ displaystyle 2 \ int _ {M}^{\ infty} G (u, t) \, du = 2 \ int _ {\ frac {M} {\ sqrt {t}}}^{\ infty} G ( v, 1) \, dv <\ varepsilon.}$

Ett vanligt val är att ställa in M till en konstant C gånger standardavvikelsen för den gaussiska kärnan

${\ displaystyle M = C \ sigma +1 = C {\ sqrt {t}} +1}$

där C ofta väljs någonstans mellan 3 och 6.

Att använda den samplade Gauss-kärnan kan emellertid leda till implementeringsproblem, i synnerhet vid beräkning av derivat av högre ordning i finare skala genom att tillämpa samplade derivat av Gaussiska kärnor. När noggrannhet och robusthet är primära konstruktionskriterier, bör därför alternativa implementeringsmetoder övervägas.

För små värden på ε (10 ⁻⁶ till 10 ⁻⁸ ) är de fel som introduceras genom att stympa Gaussian vanligtvis försumbara. För större värden på ε finns det dock många bättre alternativ till en rektangulär fönsterfunktion . Till exempel, för ett visst antal poäng kommer ett Hamming -fönster , Blackman -fönster eller Kaiser -fönster att göra mindre skada på Gaussers spektrala och andra egenskaper än en enkel avkortning. Trots detta, eftersom den gaussiska kärnan minskar snabbt i svansen, är huvudrekommendationen fortfarande att använda ett tillräckligt litet värde av ε så att trunkeringseffekterna inte längre är viktiga.

Den diskreta gaussiska kärnan

Den idealiska diskreta Gauss -kärnan (solid) jämfört med den vanliga Gaussian (streckad), för skalor t = [0,5, 1, 2, 4]

Ett mer förfinat tillvägagångssätt är att förena den ursprungliga signalen med den diskreta gaussiska kärnan T ( n , t )

${\ displaystyle L (x, t) = \ sum _ {n =-\ infty}^{\ infty} f (xn) \, T (n, t)}$

var

${\ displaystyle T (n, t) = e^{-t} I_ {n} (t)}$

och betecknar de modifierade Bessel -funktionerna för heltalsordning, n . Detta är den diskreta motsvarigheten till den kontinuerliga Gaussian genom att den är lösningen på den diskreta diffusionsekvationen (diskret utrymme, kontinuerlig tid), precis som den kontinuerliga Gaussian är lösningen på ekvationen för kontinuerlig diffusion. ${\ displaystyle I_ {n} (t)}$

Detta filter kan avkortas i den rumsliga domänen som för den provtagna Gaussian

${\ displaystyle L (x, t) = \ sum _ {n = -M}^{M} f (xn) \, T (n, t)}$

eller kan implementeras i Fourier-domänen med hjälp av ett slutet uttryck för dess diskreta Fourier-transform :

${\ displaystyle {\ widehat {T}} (\ theta, t) = \ sum _ {n =-\ infty}^{\ infty} T (n, t) \, e^{-i \ theta n} = e^{t (\ cos \ theta -1)}.}$

Med detta frekvensdomän-tillvägagångssätt överförs skalutrymmeegenskaperna exakt till den diskreta domänen, eller med utmärkt approximation med användning av periodisk förlängning och en lämpligt lång diskret Fourier-transform för att approximera diskret-tid-Fourier-transformen för signalen som utjämnas. Dessutom kan derivat-approximationer av högre ordning beräknas på ett enkelt sätt (och bevara skalutrymmeegenskaper) genom att tillämpa små supportcentralskillnadsoperatorer på den diskreta skalutrymmet .

Som med den provtagna Gaussian kommer en vanlig avkortning av det oändliga impulssvaret i de flesta fall att vara en tillräcklig approximation för små värden på ε, medan för större värden på ε är det bättre att använda antingen en sönderdelning av den diskreta gaussian till en kaskad av generaliserade binomfilter eller alternativt för att konstruera en begränsad ungefärlig kärna genom att multiplicera med en fönsterfunktion . Om ε har valts för stort så att effekterna av trunkeringsfelet börjar dyka upp (till exempel som falska extrema eller falska svar på derivatoperatörer av högre ordning), är alternativen att minska värdet på ε så att en större ändlig kärna används, med avstängning där stödet är mycket litet, eller för att använda ett avsmalnande fönster.

Rekursiva filter

Kärnor med skalutrymme. Idealisk diskret gaussisk baserad på besselfunktioner (röd) och tvåpoliga par framåt/bakåt rekursiva utjämningsfilter (blå) med poler som beskrivs i texten. Överst visar enskilda kärnor, och botten är deras kumulativa sammankoppling med varandra; t = [0,5, 1, 2, 4].

Eftersom beräkningseffektiviteten ofta är viktig, används lågordnade rekursiva filter ofta för utjämning av skalutrymme. Till exempel använder Young och van Vliet ett rekursivt filter av tredje ordningen med en riktig pol och ett par komplexa poler, applicerade framåt och bakåt för att göra en sjätte ordningens symmetriska approximation till Gauss med låg beräkningskomplexitet för vilken utjämningsskala som helst.

Genom att slappna av några av axiomen drog Lindeberg slutsatsen att bra utjämningsfilter skulle vara "normaliserade Pólya -frekvenssekvenser", en familj av diskreta kärnor som inkluderar alla filter med riktiga poler vid 0 < Z <1 och/eller Z > 1, liksom som med riktiga nollor vid Z <0. För symmetri, vilket leder till ungefärlig riktad homogenitet, måste dessa filter begränsas ytterligare till par poler och nollor som leder till nollfasfilter.

För att matcha överföringsfunktionens krökning vid nollfrekvens för den diskreta Gaussian, vilket säkerställer en ungefärlig halvgruppsegenskap av additiv t , två poler vid

${\ displaystyle Z = 1+{\ frac {2} {t}}-{\ sqrt {\ vänster (1+{\ frac {2} {t}} \ höger)^{2} -1}}}$

kan appliceras framåt och bakåt, för symmetri och stabilitet. Det här filtret är den enklaste implementeringen av en normaliserad Pólya -frekvenssekvenskärna som fungerar för alla utjämningsskalor, men det är inte en lika bra approximation till Gaussian som Young och van Vliets filter, som inte är normaliserad Pólya -frekvenssekvens på grund av dess komplexa stolpar.

Överföringsfunktionen, H ₁ , av en symmetrisk pol-par rekursivt filter är nära besläktad med den tidsdiskreta Fouriertransformen av den diskreta Gausskärna via första ordningens approximation av den exponentiella:

${\ displaystyle {\ widehat {T}} (\ theta, t) = {\ frac {1} {e^{t (1- \ cos \ theta)}}} \ approx {\ frac {1} {1+ t (1- \ cos \ theta)}} = H_ {1} (\ theta, t),}$

där t -parametern här är relaterad till den stabila polpositionen Z = p via:

${\ displaystyle t = {\ frac {2p} {(1-p)^{2}}}.}$

Dessutom är sådana filter med N -poler, som de två polpar som illustreras i detta avsnitt, en ännu bättre approximation till den exponentiella:

${\ displaystyle {\ frac {1} {\ left (1+{\ frac {t} {N}} (1- \ cos \ theta) \ right)^{N}}} = H_ {N} (\ theta , t),}$

där de stabila polpositionerna justeras genom att lösa:

${\ displaystyle {\ frac {t} {N}} = {\ frac {2p} {(1-p)^{2}}}.}$

Impulssvaret för dessa filter är inte särskilt nära gaussiska om inte mer än två polpar används. Men även med endast ett eller två polpar per skala kommer en signal som successivt utjämnas vid ökande skalor att vara mycket nära en gaussisk utjämnad signal. Halvgruppsegenskapen är dåligt approximerad när för få polpar används.

Axiom för skalutrymme som fortfarande uppfylls av dessa filter är:

• linjäritet
• skiftinvarians (heltalskift)
• icke-skapande av lokalt extrema (nollkorsningar) i en dimension
• icke-förbättring av lokalt extrema i valfritt antal dimensioner
• positivitet
• normalisering

Följande är endast tillfredsställande, approximationen är bättre för större antal polpar:

• förekomsten av en oändlig generator A (den oändliga generatorn för den diskreta Gaussian, eller ett filter som närmar sig den, kartlägger ungefär ett rekursivt filtersvar till en av oändligt större t )
• den semi-gruppstruktur med tillhörande kaskaden utjämning egenskapen (denna egenskap approximeras genom att betrakta kärnor vara likvärdiga när de har samma t värde, även om de inte är helt lika)
• rotationssymmetri
• skalavvikelse

Denna rekursiva filtermetod och variationer för att beräkna både den gaussiska utjämningen såväl som Gaussiska derivat har beskrivits av flera författare. Tan et al. har analyserat och jämfört några av dessa tillvägagångssätt och har påpekat att filtren Young och van Vliet är en kaskad (multiplikation) av filter framåt och bakåt, medan Deriche och Jin et al. filter är summor av filter framåt och bakåt.

Vid fina skalor garanterar inte den rekursiva filtreringsmetoden såväl som andra separerbara tillvägagångssätt bästa möjliga approximation till rotationssymmetri, så icke-separerbara implementeringar för 2D-bilder kan övervägas som ett alternativ.

Vid beräkning av flera derivat i N-jet samtidigt kan diskret skalautrymmeutjämning med den gaussiska kärnans diskreta analog eller med en rekursiv filter-approximation följt av små supportdifferensoperatörer vara både snabbare och mer exakt än att beräkna rekursiva approximationer för varje derivatoperatör.

Finite-impulse-response (FIR) -utjämnare

För små skalor kan ett FIR-filter med låg ordning vara ett bättre utjämningsfilter än ett rekursivt filter. Den symmetriska 3-kärnan [ t /2, 1- t , t /2] , för t  ≤ 0,5 utjämnar till en skala av t med ett par riktiga nollor vid Z  <0, och närmar sig den diskreta gaussian i gränsen för små t . Faktum är att med oändlig t kan antingen detta två-nollfilter eller tvåpoliga filtret med polerna vid Z  = t / 2 och Z  = 2 / t användas som den oändliga generatorn för de diskreta gaussiska kärnor som beskrivs ovan.

FIR-filterets nollor kan kombineras med det rekursiva filterets stolpar för att skapa ett generellt utjämningsfilter av hög kvalitet. Till exempel, om utjämningsprocessen alltid ska applicera ett bikadratiskt (tvåpoligt, två-noll) filter framåt och bakåt på varje datarad (och på varje kolumn i 2D-fallet), kan polerna och nollorna göra var och en del av utjämningen. Nollorna begränsas vid t = 0,5 per par (nollor på Z = –1), så för stora skalor gör polerna det mesta av arbetet. På finare skalor gör kombinationen en utmärkt approximation till den diskreta Gauss om polerna och nollorna gör ungefär hälften av utjämningen. De t -värdena för varje del av utjämning (poler, nollor, framåt och bakåt flera program, etc.) är additiva, i enlighet med den ungefärliga halv grupp egenskap.

Z -planplatser med fyra poler (X) och fyra nollor (cirklar) för ett utjämningsfilter med hjälp av framåt/bakåt biquad för att jämna till en skala t = 2, med hälften av utjämningen från polerna och hälften från nollorna. Nollorna är alla på Z = –1; polerna är vid Z = 0,172 och Z = 5,83. Polerna utanför enhetscirkeln implementeras genom att filtrera bakåt med de stabila polerna.

FIR -filteröverföringsfunktionen är nära besläktad med den diskreta Gaussians DTFT, precis som det rekursiva filtret. För ett par nollor är överföringsfunktionen

${\ displaystyle {\ widehat {T}} (\ theta, t) = e^{-t (1- \ cos \ theta)} \ approx {1-t (1- \ cos \ theta)} = F_ {1 } (\ theta, t),}$

där t -parametern här är relaterad till nollägena Z = z via:

${\ displaystyle t =-{\ frac {2z} {(1-z)^{2}}},}$

och vi kräver t  ≤ 0,5 för att hålla överföringsfunktionen icke-negativ.

Dessutom är sådana filter med N par nollor en ännu bättre approximation till exponentialen och sträcker sig till högre värden av t  :

${\ displaystyle \ left (1-{\ frac {t} {N}} (1- \ cos \ theta) \ right)^{N} = F_ {N} (\ theta, t),}$

där de stabila nollägena justeras genom att lösa:

${\ displaystyle {\ frac {t} {N}} =-{\ frac {2z} {(1-z)^{2}}}.}$

Dessa FIR- och pol-nollfilter är giltiga skalutrymskärnor som uppfyller samma axiom som de helpoliga rekursiva filtren.

Realtidsimplementering inom pyramider och diskret approximation av skalanormaliserade derivat

När det gäller ämnet automatiskt skalval baserat på normaliserade derivat används ofta pyramid-approximationer för att få prestanda i realtid. Lämpligheten av att approximera skala-rymdoperationer inom en pyramid härstammar från det faktum att upprepad kaskadutjämning med generaliserade binomiala kärnor leder till likvärdiga utjämningskärnor som under rimliga förhållanden närmar sig Gaussian. Dessutom kan de binomiala kärnorna (eller mer allmänt klassen av generaliserade binomiala kärnor) visa sig utgöra den unika klassen av begränsade stödkärnor som garanterar att lokala extrema eller nollkorsningar inte skapas med ökande skala (se artikeln om multi -skaliga tillvägagångssätt för detaljer). Särskild försiktighet kan dock behöva vidtas för att undvika diskretiseringsartefakter.

Andra mångsidiga tillvägagångssätt

För endimensionella kärnor finns en välutvecklad teori om mångskaliga tillvägagångssätt , angående filter som inte skapar nya lokala extrema eller nya nollkorsningar med ökande skalor. För kontinuerliga signaler är filter med riktiga poler i s -planet inom denna klass, medan för diskreta signaler uppfyller ovan beskrivna rekursiva och FIR -filter dessa kriterier. I kombination med det strikta kravet på en kontinuerlig halvgruppsstruktur utgör den kontinuerliga Gaussian och den diskreta Gaussian det unika valet för kontinuerliga och diskreta signaler.

Det finns många andra multi-skala signalbehandling, bildbehandling och datakomprimeringstekniker som använder vågor och en mängd andra kärnor, som inte utnyttjar eller kräver samma krav som skalutrymme beskrivningar gör; det vill säga, de är inte beroende av att en grövre skala inte genererar ett nytt extremum som inte var närvarande i en finare skala (i 1D) eller icke-förbättring av lokalt extrema mellan angränsande skalnivåer (i valfritt antal dimensioner).

Se även

• Skala utrymme
• Pyramid (bildbehandling)
• Flerskala tillvägagångssätt
• Gaussiskt filter

Referenser