Képszurés ˝ II Digitális képelemzés alapveto˝ algoritmusai 1
Laplace-szur ˝ o˝
2
Gauss- és Laplace-képpiramis
3
˝ Gyors szur ˝ ok ˝ Szeparábilis szur ˝ ok ˝ Futószur ˝ ok
4
Adaptív zajszurés ˝
Csetverikov Dmitrij Eötvös Lóránd Egyetem, Budapest
[email protected] http://vision.sztaki.hu
Informatikai Kar
Laplace-operátor és approximációja A folytonos Laplace-operátor definíciója: ∂2 ∂2f ∂2 . ∂2f + = + f ∆f (x, y ) = ∂x 2 ∂y 2 ∂x 2 ∂y 2 Egyszeru˝ 3 × 3-as maszk Laplace-operátorra a deriváltakat különbségekkel approximáljuk ∂f ∂x −→
−1 1 0
∂2f −→ ∂x 2
−1 1 0 − 0 −1 1 = −1 2 −1
0 0 0 0 −1 0 0 −1 0 ∆f −→ −1 2 −1 + 0 2 0 = −1 4 −1 0 0 0 0 −1 0 0 −1 0
Laplace-szur ˝ o˝ és átlagolás ˝ Normalizálás után az alábbi approximált wL Laplace-szur ˝ ot kapjuk: ∆f (x, y ) ≈ f (x, y ) − Av (x, y ) = f (x, y ) ∗ wL , ahol Av a szomszédos képelemek átlaga: h i . 1 f (x − 1, y ) + f (x, y − 1) + f (x + 1, y ) + f (x, y + 1) Av (x, y ) = 4 0 −1 0 1 4 −1 4 −1 0 −1 0 4 szomszéd
−1 −1 −1 1 8 −1 8 −1 −1 −1 −1 8 szomszéd
Egyszeru˝ maszkok Laplace-szurésre ˝
Laplace-szur ˝ o˝ tulajdonságai 1/2
Laplace-szur ˝ o˝ tulajdonságai 2/2
Az eredmény közel áll az eredeti és a simított kép különbségéhez. a lassú képváltozásokat levonjuk, a gyorsak megmaradnak ha nincs változás, nulla az eredmény (válasz, response)
Az output kép értéktartománya elvileg [−255, 255]. egy pixel és a szomszédai különbsége gyakran kicsi ⇒ a gyakorlatban az értéktartomány lényegesen szukebb ˝ ⇒ jobb nem kerekíteni
A Laplace-szur ˝ o˝ kiemel intenzitás-változásokat és finom részleteket.
Laplace-szurés ˝ példái 1/3
Laplace abszolút
˝ alkalmazhatunk elötte, hogy a Egy simítószur ˝ ot képfüggvény deriválható legyen. Laplacian-of-Gaussian (LoG): a Laplace és a Gauss szur ˝ o˝ konbinációja wLoG = wG ∗ wL wG alkalmazása után a képfüggvény simább, deriválhatóbb lesz wLoG kevésbé zajérzékeny, mint wL a LoG nulla-átmenetei élpontok ˝ nulla-átmenetek: elojel-váltások, zero-crossings
kontúrokat, foltokat, vékony vonalakat
bemenet
Zaj-érzékeny, mert magasrendu˝ deriváltakat tartalmaz.
Laplace-szurés ˝ példái 2/3
Laplace eltolt
Az eredményt kétféleképpen mutatjuk be: abszolútérték leképezés: −127 → 127, 127 → 127 eltoltérték leképezés: −127 → 0, 127 → 254
˝ fugg ˝ A leképezéstol ˝ oen más és más részletek látszanak.
bemenet
Laplace abszolút
Laplace eltolt
A kontúrok ki vannak emelve. A fokozatos képváltozások el vannak nyomva.
Laplace-szurés ˝ példái 3/3
Képpiramis 1/2
Csökkeno˝ felbontású képmásolatok sorozata a piramis alja (bottom): maximális (eredeti) felbontás a piramis csúcsa (top): minimális felbontás
A felbontás-csökkentés tipikus menete: 1 2
bemenet
Laplace abszolút
Laplace eltolt 3
A Laplace-szur ˝ o˝ zaj-érzékeny. A só-és-borsó zajt tartalmazó képen kevés a kontraszt rész. ⇒ a Laplace-szurés ˝ eredménye zaj jellegu˝
Képpiramis 2/2
˝ képszurés, ˝ pl. kisméretu˝ Gauss- vagy Laplace-szur ˝ ovel decimálás (decimation): minden második sor és oszlop törlése iteráció: a két muvelet ˝ megismétlése
A Gauss-piramis legalsó szintje (alja) az eredeti kép. A Laplace-piramis alja a Laplace-szurt ˝ eredeti kép.
Gauss-képpiramis példája
˝ A szur ˝ otípus választása milyen képi tulajdonságokat, sajátságokat akarunk ˝ megorizni a csökkeno˝ felbontású képen? ⇒ ha az élekre koncentrálunk, akkor Laplace ⇒ ha minimális információ-vesztességet akarunk, akkor Gauss
Másféle, bonyolultabb képpiramisok is léteznek. A képpiramis szorosan kapcsolódik a scale-space-hez. képpiramis: rögzitett arányú felbontás-csökkenés (tipikusan, a felére) scale-space: szabályozható arányú részletesség-csökkenés (elméletileg, folytonos)
A képet elsimítjuk, a felbontás a felére csökken. A finom részletek fokozatosan eltunnek. ˝ ˝ ⇒ lehetoség változó részletességu˝ képelemzésre
Laplace-képpiramis példája
Sejtdetektálás Laplace-piramis segítségével 1/3
eredeti sejtkép (vizelet) A finom részletek megmaradnak. A lassú képváltozások eltunnek. ˝ ˝ ⇒ lehetoség lassan változo˝ háttér eltuntetésére ˝
Sejtdetektálás Laplace-piramis segítségével 2/3
Laplace-piramis 2.szintje, kinagyítva A piramis kiemeli a sur ˝ u˝ képváltozású régiókat. Az objektumok láthatók az alacsony kontraszt és a változó háttér ellenére.
Különbözo˝ méretu, ˝ alakú és textúrajú sejtek láthatók. egyes sejtek kontrasztja igen alacsony
A cél a sejtrégiók kiemelése.
Sejtdetektálás Laplace-piramis segítségével 3/3
a detektált objektumok Minden sejtet detektáltunk és nincs hamis detektálás (false positive)
Az alacsony kontraszt ellenére a határok elég pontosak.
˝ 1/3 Szeparábilis szur ˝ ok
˝ 2/3 Szeparábilis szur ˝ ok
˝ bontható: Egy 2D-s szeparábilis szur ˝ o˝ két 1D-s szur ˝ ore w(y , x) = v (y ) · u T (x)
Egy DW × DW -s ablakra a muveletigény ˝ minden pontban
˝ a szur ˝ omátrix (maszk) minden eleme a két 1D-s szur ˝ o˝ megfelelo˝ elemeinek a szorzata u T (x) a transzponált (horizontális) vektor
1 2 1 1 2 4 2 = 2 · 1 2 1 1 2 1 1
1 2 1
1 1 2 1
2 2 4 2
1 1 2 1
2 ˝ O(DW eredeti szur ˝ o: ) ˝ 2 · O(DW ) szeparábilis szur ˝ o:
˝ Hogyan bontsunk egy 2D-s szur ˝ omátrixot több 1D-s szur ˝ o˝ lineáris konbinációára? használjuk a Szinguláris Érték Dekompozíciót, az SVD-t nem biztos, hogy gyorsabb lesz ˝ számától ⇒ függ az 1D-s szur ˝ ok
Szeparábilis szur ˝ o˝ példája
˝ 3/3 Szeparábilis szur ˝ ok
Futószurés ˝ fogalma 1/2 Amikor az ablak a következu˝ pozícióba lép,
A Gauss-szur ˝ o˝ szeparábilis wG (x, y ) = wG (x) · wG (y ) wG (x) = C · e
−
nem számítjuk ki az új értéket az eredeti definíció szerint ˝ o˝ pozícióban kapott értéket és hanem felhasználjuk az eloz módosítjuk azt (felfrissítjük, update) hiszen az ablak tartalma csak kismértékben változik egy oszlop kilép egy oszlop belép
x2 2σ 2
A dobozszur ˝ o˝ is szeparábilis egy dobozszur ˝ o˝ mátrix két 1D-s egységvektor szorzata ˝ ˝ a dobozszur ˝ o futószur ˝ o-implementációja még gyorsabb
˝ Futószur ˝ o˝ megoldások különbözo˝ szur ˝ okre léteznek. dobozszur ˝ o˝ mediánszur ˝ o˝
Angolul: futószurés: ˝ run filtering ˝ running filter futószur ˝ o:
A futó dobozszur ˝ o˝ 1/2
Futószurés ˝ fogalma 2/2
A módszer hatékonysága az eredmény kiszámítási módjától függ.
Adatstruktúra: az S[x] tömb, hossza N
egy addítiv mennyiség, pl. az átlag könnyen módosítható egy nemlineáris mennyiség, pl. a medián nehezebben módosítható
képméret: M sor, N oszlop ablakméret: DW × DW
DW
y
a kezdo˝ pozícióra kiszámítjuk az SW ablakösszeget
A futó dobozszur ˝ o˝ 2/2
A futó dobozszur ˝ o˝ számításigénye
Lépés soron belül (Next Position)
S[1]
az aktuális SW frissítése:
S[3]
S[x]
Kép- és ablakméret
x INIT
DW
NP
az összes S[x] frissítése:
INIT: S[x] inicializálása ˝ (emlékezteto)
x
Inicializálás minden sor elején
a Gyors Fourier Transzformációra (FFT) a Szinguláris Érték Dekompozícióra (SVD)
minusz kilépo˝ pixel plusz belépo˝ pixel
S[x]
a kezdo˝ sorra kiszámítjuk az S[x] oszlopösszegeket
Az ötletet más, bonyolultabb matematikai muveletekre ˝ is ki lehet terjeszteni egy fútóablakban (data window)
Sor végén ugrás a következo˝ sor elejére (Next Row)
S[3]
Az adatstruktúra inicializálása
˝ A futószurés ˝ kiterjesztheto˝ tetszoleges alakú ablakra.
minusz kilépo˝ S plusz belépo˝ S
S[1]
y
NR
képméret: M sor, N oszlop ablakméret: DW × DW
Ha M ≫ DW , a muveletigény ˝ az S[x] inicializálása erejeig ˝ nem függ az ablakmérettol. a gyakorlatban a 25 × 25-ös futó dobozszur ˝ o˝ ugyanolyan gyors, mint az 5 × 5-ös
Ha N ≫ M, transzponáljuk a képmátrixot, a szurés ˝ után pedig állítsuk vissza! ⇒ így talán gyorsabb lesz
Az adaptívitás szüksége
˝ Eddig kizárolag a nemadaptív szur ˝ okkel foglalkoztunk: rögzített a környezet-kiválasztás, pl. fix méretu˝ ablak rögzített a környezeten definiált operátor, pl. a medián
˝ Az adaptívitás a lokális kontextus felhasználása, amitol az eredmény javulását várjuk. ˝ elkerüljük az átlagszur ˝ okre jellemzo˝ élelmosódást ˝ elkerüljük az mediánszur ˝ okre jellemzo˝ sarok-lekerekítést
Mi ezen nemkívánatos hatások oka? nem vesszük észre, hogy az ablak az objektum és a háttér határán van ⇒ összekeverjük a két különbözo˝ intenzitás-osztályhoz tartozó értékeket
Képelem-kiválasztás egy n × n-es ablakban
Standard környezet az összes n2 pixel
k legközelebbi szomszéd (k -nearest neighbours, k -NN) a k pixel, amely intenzitás szerint legközelebb van a c középpixelhez a k egyik lehetséges beállítása: k = n × n2 + (n − 1) például, ha n = 3, akkor k = 5
Szigma-legközelebbi szomszédok az i pixelt akkor választjuk, ha |I(i) − I(c)| < k · σzaj gyakran k = 2 σzaj a zaj szórása ⇒ σzaj becslésére felhasználhatjuk a kép háttér részeit
Adaptív környezet-kiválasztás
Megpróbáljuk elválasztani ˝ az objektum-képelemeket a háttér-képelemektol a releváns értékeket a zajtól
Adaptív környezet-kiválasztás: csak a releváns pixeleket fogjuk felhasználni. eddig a környezet a teljes ablak volt most az ablakban csak bizonyos képelemeket veszünk figyelembe
A kiválasztott környezeten definiált operátor viszont fix marad. eddig is fix függvényt, pl. átlagot használtunk most is ez lesz
Szimmetrikus legközelebbi szomszédok az i pixelt akkor választjuk, ha |I(i) − I(c)| < |I(is ) − I(c)| {i, is } a közép-szimmetrikus képelemek egyik párja
Lokális kontextus: pixelek intenzitása és elrendezése Hasznos az élek esetén az él ugyanazon oldálán levo˝ képelemeket választja elkerüli "az élen keresztüli átlagolást" ⇒ elkerüli az élelmosódást
i c
is
szimmetrikus pixelpár
választás kontúron
˝ össehasonlítása Standard és adaptív 5 × 5-ös szur ˝ ok
input kép
doboz
medián
A szigma-szur ˝ o˝ nem tünteti el a só-és-borsó zajt
szigma átlag 5 × 5
szigma med. 5 × 5
szigma med. 9 × 9
Egy zajos pixelre az Izajos ± 2σzaj intervallum nem tartalmaz zajmentes pixeleket |Izajos − Izajmentes | > 2σzaj
Emiatt a szúro˝ a Izajos zajos értéket választja k -NN átlag
szimm. átlag
szimm. medián
⇒ a zajt nem távolítja el
