Képfeldolgozási eljárások BSc szakdolgozat
írta: témavezet®:
Kiss Martin Károly Keszthelyi Gabriella
Eötvös Loránd Tudományegyetem Természettudományi Kar Budapest, 2015
Tartalomjegyzék
1. Bevezetés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2. Lineáris sz¶r®k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Konvolúció . . . . Simítás . . . . . . . A kép szélein . . . Néhány nemlineáris Zaj . . . . . . . . .
. . . . . . . . . . . . . . . módszer . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. 3 . 5 . 8 . 10 . 12
3. Éldetektálás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Gradiens alapú élkeresés . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 LoG élkeresés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Canny élkeresés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4. Harris sarokdetektálás . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Alkalmazás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5. Matlab implementációk . . . . . . . . . . . . . . . . . . . . . . . . . . 32
i
Köszönetnyilvánítás
Ezúton szeretnék köszönetet mondani témavezet®mnek, Keszthelyi Gabriellának, hogy tanácsaival és útmutatásával segítette munkámat. Hálás vagyok, amiért segített összeszedni a szükséges szakirodalmat és segítette annak megértését. Valamint köszönöm családomnak és barátaimnak, akik kitartóan támogattak az egyetemi évek alatt. Külön szeretném megköszönni édesanyámnak a támogatását és segítségét ezen id®szak alatt.
1
1. Bevezetés Jól csak a szívével lát az ember. Ami igazán lényeges, az a szemnek láthatatlan." Antoine de Saint-Exupéry, A kis herceg
Már a kis herceg óta tudjuk, hogy jól csak a szívünkkel látunk, manapság mégis a számítógépeinkt®l várjuk el ugyanezt. Felmerül a kérdés, valóban képesek a számítógépek látni? Egyáltalán, mi az a számítógépes látás? Egy ilyen sokoldalú tudományágnak nagyon nehezen lehet olyan de níciót adni, amely vitathatatlan, ezért inkább azt érdemes megnézni, mivel foglalkozik. A számítógépes látás kapcsolatban áll, de nem ekvivalens, a fotogrammetriával, a képfeldolgozással és a mesterséges intelligenciával. Valamint, a számítógépes látás témaköre igen tág és sok ponton kapcsolódik egyéb tudományterületekkel. Továbbá, számos hasznos alkalmazással rendelkezik, néhány példa: orvosi képfeldolgozás, ipari min®ségellen®rzés, robotika, katonai alkalmazások, mozgás rekonstrukciója és keresés képeket tartalmazó adatbázisokban, stb. . . Több ezer oldalnyi szakirodalom található a témában érdekl®d®k számára.
1. ábra. Egy virág képének részlete, valamint ez függvényként ábrázolva. Mi a továbbiakban képfeldolgozással, azon belül is él- és sarokkereséssel foglalkozunk. Az ember látása folyamatos, egybefügg®en látjuk a körölöttünk lév® világot, viszont a számítógép a fényképeket (videókat) nem tudja ily módon tárolni. Így létrehozták a digitális kép fogalmát, amely lényegében egy "táblázat" (vagy "mátrix"), melynek minden eleme egy-egy színt tartalmaz, amelyet egy egész számnak, vagy egészekb®l álló számhármasnak feleltetnek meg. A táblázat egy elemét pixelnek nevezik. Ha számhármasokról beszélünk, például az RGB (red, green, blue, azaz piros, zöld, kék) kódolás esetén, és megszámozzuk a táblázat sorait és 2
oszlopait, akkor ez felfogható, mint egy f : N × N → R3 függvény, vagyis a sorok és oszlopok megfelel® elemeihez hozzárendelünk egy számhármast, amely megadja, hogy az adott pont színe mennyi pirosat, mennyi zöldet és mennyi kéket "tartalmaz" (például ha mindhárom érték minimális, vagyis 0, akkor fekete szín¶ a pixel, vagy ha a kék érték minimális és a piros és a zöld érték maximális, ami általában 1 vagy 255, akkor sárga szín¶ a pixel). Nekünk az objektumok határainak megválasztásához általában nincs szükségünk színekre, csak egy szürke árnyaltra, azaz elég egy g : N × N → R függvény, amely felvett értékei a szürkének egy árnyalatát jelölik (példa: 1. ábra). Például 8 bitet használva le tudunk kódolni egy színt, itt az értékek egészek és 0-tól 255-ig mennek, ahol 0 a fekete és 255 a fehér színt jelöli, ezzel 256 árnyalatát adva a szürke színnek, matematikai számolásokhoz viszont egyszer¶bb egy olyan modellt alkalmazni, ami folytonos és 0 jelöli a fekete és 1 jelöli a fehér színt. S®t a legtöbb probléma esetén, folytonos értelmezési tartományt használva vezetjük be a megfelel® függvényeket, majd ezután diszkretizáljuk.
2. Lineáris sz¶r®k
A képfeldolgozás során, általában nem egymástól függetlenül vizsgáljuk meg a pixelek tulajdonságait, hanem valamilyen küls® megjelenés alapján, a pixelek egy csoportját gyeljük meg. Egy egyszer¶ módszer, ha a pixel értékek súlyozott összegét használjuk. Különböz® súlyokat használva a különböz® célok elérésére. Például ennek segítségével tudjuk élesíteni a képünket, vagy eltávolítani a zajt, vagy kiemelni az éleket. A következ® egyszer¶ modellt fogjuk használni. Egy új mátrixot csinálunk, ugyanakkora méret¶t, mint az eredeti kép. Ezek után minden helyre, ebben az új mátrixban, egy súlyozott összegét írjuk a kép megfelel® pixelét körülvev® pixeleknek. Minden pixel esetén ugyanazt a súlyozást használva. Ezt az eljárást lineáris sz¶résnek nevezik (linear ltering ). A mintát, ami alapján a súlyozott összeget vesszük, pedig kernelnek nevezik. Azt a folyamatot amikor egy képre alkalmazzák a kernelt, azt pedig konvolúciónak (convolution ).
Konvolúció Formálisan, a konvolúció ZZ g(i, j) =
f (i − u, j − v)h(u, v)dudv
3
a folytonos esetben és g(i, j) =
X
f (k, l)h(i − k, j − l) =
X
k,l
f (i − k, j − l)h(k, l)
k,l
a diszkrét esetben (ezt az esetet használjuk a gyakorlati alkalmazás miatt), ahol g a kapott új mátrix (kép), f az eredeti kép és h a kernel (természetesen a konvolúció m¶veletét bármely két tesz®leges függvényen el lehet végezni). A szumma esetén, k és l értékét szándékosan nem választottuk meg, feltételezzük, hogy akkora a terjedelem, hogy minden nemnulla érték számításba kerül. Hasonlóan de niálhatjuk az 1 dimenziós esetre is. Ekkor Z f (i − u)h(u)du
g(i) =
a folytonos és g(i) =
X
f (i − k)h(k)
k
a diszkrét esetben. Egyszer¶bb jelölés: g = f ∗ h.
A következ® sorokban f , g és h egy-egy mátrixot jelöl, a pedig egy konstansot, ahol nincs külön jelölve, ott pontonként értelmezend® a m¶velet. A konvolúció tulajdonságai közé tartozik, hogy kommutatív f ∗ g = g ∗ f,
asszociatív (f ∗ g) ∗ h = f ∗ (g ∗ h),
LSI operátor, azaz lineáris h ∗ (f + g) = h ∗ f + h ∗ g a(h ∗ f ) = h ∗ (af )
és eltolás-invariáns g(i, j) = f (i + k, j + l)
⇐⇒
(h ∗ g)(i, j) = (h ∗ f )(i + k, j + l).
4
Simítás A képeknek többnyire megvan az a tulajdonsága, hogy a pixelek hasonlóak a szomszédaikhoz. Azonban, ha a kép zajos volt, ez a tulajdonság elveszik. Zajnak tekinthetünk minden olyan dolgot, amellyel nem tudunk vagy nem akarunk dolgozni. Például a fényképez®gép, amellyel dolgozunk pár helyen "halott" pixeleket rögzít, azaz a képt®l függetlenül, ezeken a helyeken mindig fekete a kép. Ilyen esetekben természetes, ha megpróbáljuk a pixeleket az ®ket körülvev® pixelek súlyozott átlagával helyettesíteni. Azt szeretnénk elérni, hogy a kapott kép egy defókuszált fényképre hasonlítson. Ezt a folyamatatot hívják simításnak (smoothing ) vagy elmosásnak (blurring ).
2. ábra. Egy kép konvolúciója az átlag sz¶r®vel, balról jobbra haladva el®ször az eredeti kép látható, majd a kép konvolúciója az átlag sz¶r®vel, el®ször 3 × 3, majd 5 × 5 és végül 10 × 10 méret¶ kernelt használva. El®ször nézzük az átlag sz¶rést, vagyis azt az esetet, ha az ®t körülvev® pixelek mindegyikét azonos súllyal vesszük. Azaz, mondjuk (2k +1)×(2k +1)-es blokkokat átlagolunk (ahol k = 1, 2, . . . ). Ez azt eredményezi, hogy az inputként kapott f képb®l, a következ® j+k i+k X X 1 f (u, v) g(i, j) = (2k + 1)2 u=i−k v=j−k
output keletkezik. Ez pontosan azt jelenti, mintha a képnek és annak a kernelnek vennénk a konvolúcióját, mely (2k + 1) × (2k + 1) méret¶ és minden eleme egyenl® 1-gyel (és ezt megszorozzuk a megfel® konstanssal). Például 3 × 3 esetben: 1 1 1 1 1 1 1 9 1 1 1
5
Ez a módszer azonban nem túl hatásos, nem a várt eredményt hozza. Vegyünk egy olyan képet, amely közepén egy darab 1-es van és minden más eleme 0. Ha ezt simítjuk az el®z® módszerrel, akkor egy négyzetet kapunk középen, melynek minden eleme ugyanakkora. Ez azonban nem az, amit a defókuszált fényképez®gépek csinálnak. Egy olyan simítási eljárást akarunk, amely egy kis kört ad meg középen, mely a középpontól kifelé folyamatosan halványul és az árnyalatát csak a középponttól való távolság határozza meg. (3. ábra)
3. ábra. Forrás: [1]. Ezt jól modellezi a szimmetrikus Gauss-kernel Gσ (x, y) =
1 − x2 +y2 2 e 2σ . 2πσ 2
(1)
σ -t szórásnak (standard deviation ) szokták nevezni. Ez a kernel egy olyan súlyozott
összeget eredményez, mely sokkal nagyobb súlyt fektet a középen lév® pixelekre, mint a határon lév® pixelekre. A simítás elnyomja a zajt úgy, hogy minden pixel a szomszédjára "hasonlít", viszont a mivel a távolabbi szomszédokat kisebb súllyal vettük, ezzel eleget tettünk annak, hogy a távoli szomszédok kevésbé befolyásolják ezt. A σ -t okosan kell megválasztani. Ha a szórás kicsi (kisebb, mint 1), akkor a simításnak kis hatása lesz, mert nagyon kevés súlyt fektet az ®t körülvev® pixelekre. Ennél nagyobbra választjuk a σ -t, akkor az átlag kiegyensúlyozottan a szomszédokra fókuszál. Ez egy jó közelítés lesz, a zaj nagyrésze el fog t¶nni, cserébe a kép egy kicsivel homályosabb lesz. Végül, ha túl nagyra választjuk az értéket, a kép részletei, amiket vizsgálni szerettünk volna, elt¶nnek a zajjal együtt. A gyakorlatban általában diszkrét kernelt használunk. Ez a következ®képpen néz ki: 2 2 h(i, j) =
1 − (i−k−1) +(j−k−1) 2σ 2 e , 2πσ 2
6
4. ábra. A (1) helyen de niált Gauss függvény ábrázolva, σ = 1 esetén. ahol h egy (2k + 1) × (2k + 1) méret¶ kernel (k = 1, 2, . . . ), ebben a formában még az elemek összege nem biztos, hogy 1 lesz, így viszont lehet, hogy világosabb vagy sötétebb lesz a kép, tehát még leosztunk minden elemet, az összes elem összegével, így biztosan 1 lesz az összeg. E m¶velet során ügyesen kell megválasztani σ értékét. Ha a σ túl kicsi, akkor csak egy elemnek lesz nemnulla (vagy nagyon kicsi) értéke. Ha a σ nagy, akkor pedig k-nak is nagyobbnak kell lennie, különben a súlyozásból kimaradnának olyan elemek is, amelyek jelent®sen szerepeltek volna. A Gauss sz¶r®nek jó tulajdonságai közé tartozik, hogy ha egy sz¶r®nek vesszük a konvolúcióját egy másik sz¶r®vel, akkor szintén Gauss sz¶r®t kapunk: Gσ1 ∗ Gσ2 = G√σ2 +σ2 1
2
ez hasznos lehet, ha el®ször nem voltunk elégedettek a simítás eredményével, mert egy nagyobb szórású simításra lenne szükségünk, akkor elég csak még egyszer simítani egy kisebbel, mert a paraméterek a fent leírt módon viselkednek, tehát nem kell az eredeti képhez visszatérnünk és azt simítani. A számítógépes felhasználás során elképzelhet® az is, hogy egy nagyobb simítást, inkább több, kisebb szórású simítás eredményeként szeretnénk elérni, a jobb futásid® érdekében. A konvolúció m¶velet elvégzéséhez K 2 m¶veletre (összeadás, szorzás) van szükség pixelenként, ahol K a mérete a kernelnek (szélessége vagy magassága). Ez 7
felgyorsítható azzal, ha a 2 dimenziós konvolúció helyett, egy 1 dimenziós konvolúciót végzünk el vízszintesen, utána pedig egy 1 dimenziós konvolúciót függ®legesen, ehhez összesen 2K m¶veletre van szükség. Azokat a kerneleket, amelyekre ez megoldható szétválaszthatónak (separable ) nevezzük. Például az átlag kernel szétválasztható: 1 1 1 1 1 1 1 1 1 1 ∗ 1 1 1 1 = 9 3 3 1 1 1 1
Most vizsgáljuk meg a Gauss kernelt. Szorzatra bontható a következ®képpen: 1 − x2 +y2 2 Gσ (x, y) = e 2σ = 2πσ 2
x2 1 √ e− 2σ2 2πσ
y2 1 √ e− 2σ2 2πσ
Tehát felbontottuk egy olyan szorzatra melynek els® tényez®je csak x-t®l, a második csak y -tól függ. Azon kernelek, amelyek ilyen módon szorzatra bonthatóak, szétválaszthatóak. 1 dimenzióban ez is lesz a sz¶r®nk, azaz 1 dimenzióban: x2 1 Gσ (x) = √ e− 2σ2 2πσ
lesz a konvolúciós függvény. A 2 dimenziós Gauss sz¶rés tehát helyettesíthet® két, 1 dimenziós sz¶r® alkalmazásával, el®ször vízszintesen, majd függ®legesen, minden pixelre. Általánosságban vannak numerikus módszerek annak eldöntésére egy kernelr®l, hogy az szétválasztható-e vagy sem. Az egyik ilyen módszer a szinguláris felbontás.
2.1. Tétel (Szinguláris felbontás). Legyen A ∈ Rm×n ekkor létezik U ∈ Rm×m ,
S ∈ Rm×n , V ∈ Rn×n , melyekre A = U SV T , ahol U és V ortogonális mátrix, S pedig diagonális mátrix, nemnegatív számokkal a f®átlóban, S f®átlójában lév® si értékeket hívják A szinguláris értékeinek. A szinguláris értékeket csökken® sorrendben szokás megadni, ez esetben az S mátrix egyértelm¶en meghatározható az A mátrixból.
Tekintsük a kernelt, mint egy mátrixot és annak vegyük a szinguláris felbontását. Ha csak 1 szinguláris érték nemnulla, akkor a kernel szétválasztható és ezt a szétválasztást meg is kapjuk a felbontásból. (B®vebben a [2] könyvben megtalálható.)
A kép szélein A képek, amikkel foglalkozunk, sajnos nem végtelen hosszúak és szélesek. Így amikor végrehajtjuk a konvolúciót a kép széleihez tartozó pixelek esetén olyan pixelekkel is vennünk kellene a súlyozást, amelyek nem léteznek. Többféleképpen is 8
megoldhatjuk ezt a problémát. Az egyik megoldás az, hogy olyan helyen nem végezzük el a konvolúciót, ahol a számítás során olyan pixelt használnánk, ami nem létezik. Azaz a kép széleit elhagyjuk, így viszont az output egy kisebb méret¶ kép lesz. Többszöri konvolúció után a képméret jelent®sen kisebb lesz, ami nem túl optimális. Másik megoldás, ha nem akarjuk, hogy a kép mérete kisebb legyen, akkor a kép körül, mint egy keret, új értékekkel töltjük fel a mátrixot. Annyival, hogy elvégezhet® legyen a konvolúció a kép minden pixelére. Ezen folyamat végrehajtására többféle opciónk van, a következ®kben az alábbi mátrixot fogjuk használni, minden esetben 2 széles keretet adunk neki: 1 2 3 4 5 6 7 8 9 • Az egyik az, hogy minden extra értéket 0-nak választunk (zero-padding ). Ez
az egyik legegyszer¶bb módszer, lényegében egy fekete keretet ad a képnek (2. ábra), így konvolúció után az eredeti kép a széleken sötétebb lehet. 0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 1 4 7 0 0
0 0 2 5 8 0 0
0 0 3 6 9 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
• Az el®z®höz hasonló módszer, ha minden értéket egy konstans értéknek vá-
lasztunk. Ez pedig olyan mintha egy szürkeárnyalatot választanánk a kép keretének.
• Lehet az is, hogy minden hozzávett pixel értéke annyi, mint a hozzá legkö-
zelebb es® eredeti pixel értéke. 1 1 1 4 7 7 7
1 1 1 4 7 7 7
1 1 1 4 7 7 7
9
2 2 2 5 8 8 8
3 3 3 6 9 9 9
3 3 3 6 9 9 9
3 3 3 6 9 9 9
• További módszer, hogy az eredeti kép értékeit letükrözzük a kép széleire. 5 2 2 5 8 8 5
4 1 1 4 7 7 4
4 1 1 4 7 7 4
5 2 2 5 8 8 5
6 3 3 6 9 9 6
6 3 3 6 9 9 6
5 2 2 5 8 8 5
• Az utolsó bemutatott módszert összeragasztásnak (wraparound ) nevezik. Ez
azt csinálja, hogy mikor elérünk a kép jobb széléhez, a bal szélén lév® értékt®l kezdve másoljuk le a jobb szélre az értéket, ha pedig a bal széléhez, akkor a jobb szélét®l kezdve másoljuk le az értékeket. Hasonlóan a fels®- és alsó határon, illetve a sarkoknál. Így egy tóruszhoz hasonló szerkezetet kapunk. 5 8 2 5 8 2 5
6 9 3 6 9 3 6
4 7 1 4 7 1 4
5 8 2 5 8 2 5
6 9 3 6 9 3 6
4 7 1 4 7 1 4
5 8 2 5 8 2 5
Bár még többféle lehet®ség is van, a dolgozat keretein belül ezeket nem ismertetem. A két megoldás közül szabadon eldönthetjük melyiket használjuk. A második el®nye, hogy az eredeti mátrix méretével megegyez® mátrixot kapunk, viszont ekkor olyan súlyokat használtuk a kép szélein lév® pixelek kiszámításánál, amelyeket mi adtunk meg, így lényegében egy kicsit csaltunk.
Néhány nemlineáris módszer Az összes eddig bemutatott simítási módszer lineáris volt, azaz a pixeleket valamilyen formában az ®ket körülvev® pixelekkel súlyoztuk, minden esetben ugyanakkora súlyokkal. Vannak esetek, mikor nemlineáris sz¶rök használata célszer¶bb. Például ha van egy kép, amely valamelyik része majdnem teljesen egy árnyalatú (ég, tenger, f¶, fekete- vagy fehér háttér), de sajnos rögzítés során erre a részre egy teljesen más árnyalatú pixelek kerültek. Ekkor, ha valamilyen lineáris módszerrel 10
simítjuk, akkor is marad egy kis folt, azokon a helyeken, ahol a hibás pixelek voltak, csak az árnyalati különbség halványul. Vegyük a medián sz¶r®t, amely kiválasztja a pixel adott környezetéb®l a mediánt (rendezett sorban, páratlan számú elem esetén a középs®, páros számú elem esetén a középs® két elem átlaga) és azt írja a pixel helyére. Mivel ez csak pixel helyére egy másikat ír, vannak zajok, például a Gauss-zaj (amit a következ® részben tárgyalunk), amelyeknél a lineáris sz¶r®k használata jobb eredményre vezet. S®t a medián sz¶r®t költségesebb számolni is, mint a lineáris sz¶r®ket. Jobb választás lehet az α-rendezett átlag, mely kiszámolja a környez® pixelek átlagát kihagyva azon α százalékát, ahol a legkisebb illetve, a legnagyobb értékek vannak. Vehetünk még ezen kívül súlyozott mediánt is, amely el®ször megsúlyozza a környez® pixeleket a távolság szerint, majd így veszi a mediánt. A legnagyobb probléma (a nagyobb futásid® mellett) az, hogy mindhárom sz¶r® hajlamos lekerekíteni az éleket és sarkokat. A lineárisnál szintén öszetettebb sz¶r® a bilaterális sz¶r® (bilateral lter ). Az alapötlet az, hogy ahelyett, hogy egy pixel számolásánál a környez® pixelek x százalékát hagynánk el, ahelyett azokat hagyjuk el, amelyek nagyon különböznek a középs® elemt®l. Ekkor a létrejöv® új kép pixelének értéke a súlyozott átlaga lesz a szomszédjainak, a következ® módon: P g(i, j) =
f (k, l)w(i, j, k, l) P , k,l w(i, j, k, l)
k,l
ahol a w(i, j, k, l) súlyozási együttható. A w(i, j, k, l) esetén az (i, j) azt a pixelt jelöli, melyet éppen ki szeretnénk számolni, a (k, l) pedig az egyik szomszédja. Ennek az értéke két tényez®b®l áll össze. Az els® a koordináták különbségéb®l adódik 2 2 d(i, j, k, l) = e
−
(i−k) +(j−l) 2σ 2 d
,
ahol σd paraméter, a második pedig a pixelértékek különbségéb®l −
r(i, j, k, l) = e
kf (i,j)−f (k,l)k2 2 2σr
,
ahol σr paraméter és a norma a vektortávolság (a normás jelölésnek a színes képek sz¶résénél van nagyobb jelent®sége). E kett® szorzatából a következ® súlyozási együtthatót kapjuk: w(i, j, k, l) = e
−
(i−k)2 +(j−l)2 kf (i,j)−f (k,l)k2 − 2 2σ 2 2σr d
.
A módszer nagy el®nye, hogy meg®rzi az éleket, azonban hosszabb futási ideje van, mint az el®z®knek. 11
5. ábra. Bilaterális sz¶rés: (a) zajos lépcs® él input, (b) a koordináták különbségéb®l képzett sz¶r® (domain ), (c) a pixelértékek különbségéb®l képzett sz¶r® (range ), (d) bilaterális sz¶r®, (e) output, (f) 3D távolság a pixelértékek között; forrás: [2].
Zaj A zajról már írtam az el®z® részben, most kicsit b®vebben ismertetem. A zajnak (noise ) valamilyen modelljét szeretnénk megadni. Képfeldolgozásban zaj alatt a kép olyan adatait értjük, amelyb®l nem tudunk információt kinyerni, vagy amelyb®l nem akarunk információt kinyerni. Minden más adatot jelnek (signal ) nevezünk. A következ®kben két zaj modellt ismertetek. Az additív stacionárius Gauss zaj modellben minden pixel értékéhez egy értéket adunk hozzá, amelyet egymástól függetlenül ugyanazon a Gauss eloszlásból választjuk ki úgy, hogy a várható érték 0 legyen. A modell paramétere az eloszláshoz tartozó szórás. Ez a modell a fényképez®gépek által okozott termál zajt kívánja modellezni. A zaj szintjét simítással szeretnénk csökkenteni, ha erre alkalmazzuk az átlag sz¶rést, akkor egy m × m-es kernelt használva, a zaj szórása m-ed részére csökken. Ugyanis nézzük meg általánosságban, ha m2 elemet átlagolunk mi történik, Ii -vel (i = 1, 2, . . . m2 ) jelöljük azon elemek halmazát amelyeket átlagoltunk és ekkor minden elem Ii = si + ni alakban áll el®, ahol si legyen a
12
tényleges érték és ni pedig a zaj. Ekkor legyen 2
m 1 X Ii A= 2 m i=1
feltéve, hogy ni i.i.d. és G(0, σ 2 ) eloszlású, ahol σ 2 a szórásnégyzetet jelöli, ebb®l következik, hogy: 2
m 1 X si E(A) = 2 m i=1 2
m 1 X ni A − E(A) = 2 m i=1 !2 !2 m2 m2 X X 1 1 D2 (A) = E[(A − E(A))2 ] = E 4 ni = 4 E ni m m i=1 i=1
(2)
most vizsgáljuk meg a zajösszeg szórásnégyzetét: 2
2
D
m X
2
! ni
=
i=1
m X
2
X
2
D (ni ) + 2
Cov(ni , nj ) =
1≤i<j≤m2
i=1
m X
D2 (ni ) = m2 σ 2
i=1
mivel a változók függetlenek, ezért a tagok páronként vett kovarianciája 0, másrészr®l: 2
D2
m X i=1
! ni
= E
2
m X
!!2
2
m X
ni − E
i=1
ni
i=1
= E
!2
2
m X
ni
i=1
mivel minden ni várható értéke 0. Ezekb®l azt kaptuk meg, hogy E
!2
2
m X
ni
= m2 σ 2
i=1
ezt behelyettesítve (2)-ba kapjuk, hogy: D2 (A) =
σ2 1 2 2 m σ = m4 m2
Mivel a szórásnégyzet m12 -szeresére változott, ezért a szórás m1 -szeresre fog. Tehát a zaj nem sz¶nt meg teljesen, csak tompult. Természetesen a Gauss sz¶rést is 13
szokták alkalmazni, de a medián sz¶r®t nem, hiszen minden értékben van valamilyen elváltozás, így ezt nem csökkenti a medián sz¶r®. A só és bors (salt and pepper ) zaj modellezi azokat a fényképez®gépeket, amelyek bizonyos helyeken hibás pixeleket rögzítenek. Véletlenszer¶en kiválasztunk pixeleket és ezeket vagy a minimális, vagy a maximális értékre állítjuk be (azaz fehérre vagy feketére). Az eredmény úgy néz ki, mintha a képet "megszórtuk" volna sóval és borssal, innen kapta az elnevezését. Formálisan is de niálhatjuk: Isp (h, k) =
I(h, k) imin + y(imax − imin )
ha x < l ha x ≥ l
ahol Isp a zajjal szennyezett kép, I az eredeti kép, x ∈ [0, 1] közé es® véletlen szám (ez pixelenként eltér®), l az a paraméter amely meghatározza, hogy mennyire zajos a kép, és y pedig véletlenszer¶en választva 0 vagy 1 (P (y = 0) = P (y = 1) = 21 ). Ezt a zajt általában medián sz¶r®vel szokták simítani.
6. ábra. Egy só és bors zajjal szennyezett kép, els® esetben Gauss sz¶r®t alkalmazva, második esetben pedig medián sz¶r®t.
3. Éldetektálás
A következ® fejezetben az élekkel (edge ) és az éldetektálással (edge detection ) fogunk megismerkedni. Az élek egyenes vonalak, vagy görbék, amelyek mentén éles árnyalatváltozás van. Ez többféleképpen el®fordulhat (7. ábra): • Egy képen egy tárgy és a háttér mentén. (1) • Felületi változások esetén, például egy szoba fényképénél a sarkoknál. (2)
14
• Egy tárgynak vagy felületnek a mintája változik. Például egy tetkó, vagy
zebrák csíkjai. (3)
• Egy tárgynak (embernek) az árnyéka. (4)
7. ábra. A különböz® éltípusok; forrás: [3]. Az éleket a kialakulások szerint is rendezhetjük (1 dimenziós metszettel ábrázolva): • Lépcs® (step ) él két (közel azonos) árnyalatú régió közötti kontúr. A változás
hirtelen, egyik pixelr®l a másikra megy végbe. Ez a leggyakoribb élfajta.
8. ábra • Rámpa (ramp ) él hasonló a lépcs®höz, csak a változás nem hirtelen, hanem
folyamatosan pár pixel alatt megy végbe.
15
9. ábra • Gerinc (ridge ) él olyan, ahol az árnyalat hirtelen változik, de vissza is tér
rövid id®n belül az eredetihez. Leginkább vékony vonalak okozzák ezeket. A szélesebb gerinc éleket lehet két lépcs® éllel modellezni.
10. ábra • Tet® (roof ) él hasonló a gerinchez, csak itt a változás lassan megy végbe
és egyb®l vissza is fordul. Ez a legritkább fajta, általában csak az el®z® felsorolásban említett felületi változás során megy végbe.
11. ábra Továbbá a következ® fogalmak jól jellemzik az éleket: • Él normális (edge normal ): (egység)vektor abba az irányba, amelybe a leg-
nagyobb az intenzitásváltozás, mer®leges az élre.
• Él irány (edge direction ): (egység)vektor amely mer®leges az élnormálra, így
érint®je annak a kontúrnak, amely az él része.
• Él pozíció (edge position vagy center ): azok a pozíciók a képen, ahol az él
van. Többnyire ez egy bináris kép (0, 1 érték¶, azaz 0 ahol nincs és 1 ahol van). 16
12. ábra • Él er®sség (edge strenght vagy magnitude ): lokálisan a kép kontrasztja a nor-
mális mentén. (Azaz a legnagyobb intenzitásváltozás mértéke helyenként.)
Szeretnénk az árnyalatváltozásokat valamilyen értelemmel és jelent®séggel felruházni. Sajnos ezt nehezen lehet de niálni, például egy tájképen, a fák levelei és a háttér között húzódó él, hogyan számít a fa határának? Az az eset is el®fordulhat, mikor egy él semmilyen jelent®séggel nem bír az adott kérdésben, például csak a kép rosszabb min®sége miatt van éles változás. Azt sem tudjuk de niálni, hogy mekkora árnyalatváltozás esetében beszélhetünk élr®l. A továbbiakban olyan élekre fókuszálunk, amelyeknél a árnyalatváltozás nagy, azaz a nagy gradiens er®ssége (gradient magnitude ) a szürkeérték függvényünknek. Mivel 2 dimenzióban van a kép, amivel dolgozunk, ezért a 2 dimenziós gradienst de niáljuk:
3.1. De níció (Gradiens). Vegyünk egy f : R2 → R függvényt. Ennek a függvénynek a gradiense az a vektormez®, mely ∇f : R2 → R2 , hogy ∇f =
∂f ∂f , ∂x ∂y
.
3.2. De níció (Gradiens er®ssége (magnitude )). Az el®z®ekben de niált gradiens q
er®ssége: |∇f | =
( ∂f )2 + ( ∂f )2 . ∂x ∂y
3.3. De níció (Gradiens iránya (orientation )). Az el®z®ekben de niált gradiens , ∂f ). iránya: θ = atan2( ∂f ∂y ∂x Itt az atan2 függvény az arctan általánosítása 2 dimenzióra, a számítógépes nyelvekben használatos, alkalmas arra, hogy egy síkvektor y és x koordinátáiból (ügyelve a szokásoshoz képest fordított sorrendre) kiszámítsuk a vektor irányszögét (azaz, az X -tengellyel bezárt szögét), −π és π (kis változtatással 0 és 2π ) között:
3.4. De níció. Az atan2 : R2 → R függvény amelyhez a standard arctan függvényt használjuk, melynek az értékkészlete (− π2 , π2 ), a következ®: 17
arctan( xy ) arctan( xy ) + π arctan( xy ) − π atan2(y, x) = π2 −π 2
nem de niált
ha x > 0 ha y ≥ 0, x < 0 ha y < 0, x < 0 ha y > 0, x = 0 ha y < 0, x = 0 ha y = 0, x = 0
A következ®kben valamilyen közelítést szeretnénk adni a parciális deriváltakra. Mivel mi a deriválás problémáját diszkrét pixeleken szeretnénk megoldani, ezért természetes a közelítés. A közelítést valamilyen véges különbségként ( nite dierence ) szeretnénk felírni. Vegyük az f : R → R függvénynek a Taylor-sorát az x helyen felírva a következ®t kapjuk, ha az következ® helyen nézzük: 1 1 f (x + h) = f (x) + hf 0 (x) + h2 f 00 (x) + h3 f 000 (x) + . . . 2 3!
(3)
Itt természetesen h(> 0) értékét minél kisebbre szeretnénk választani.Ezt átalakítva kapjuk a véges "el®re" különbséget ( nite forward dierence ): f (x + h) − f (x) = f 0 (x) + O(h) h
Most pedig nézzük a következ® helyen: 1 1 f (x − h) = f (x) − hf 0 (x) + h2 f 00 (x) − h3 f 000 (x) + . . . 2 3!
(4)
Ezt átalakítva pedig megkapjuk a véges "hátra" különbséget ( nite backward difference ): f (x) − f (x − h) = f 0 (x) + O(h) h
Mindkét kapott kifejezés a deriváltat közelíti. Most vonjuk ki az (3) egyenletb®l a (4) egyenletet. Ekkor a következ®t kapjuk átalakítás után: f (x + h) − f (x − h) = 2hf 0 (x) +
2 3 000 h f (x) + . . . 3!
f (x + h) − f (x − h) = f 0 (x) + O(h2 ) 2h
Ezt véges centrális különbségnek ( nite central dierence ) nevezik. A legfontosabb, hogy ez egy jobb közelítés, mint az el®z® kett®, mert itt a hibatag csak h2 nagyságrend¶. Ezek alapján az x szerinti parciális deriváltra egy megfelel® közelítés lenne, 18
ha ezt az el®z® különbséget vennénk úgy, hogy a h értékét 1-nek választanánk, hiszen ekkor egy elég jó közelítést adtunk, amelynél a pixel szomszédait használjuk (h most a képet jelöli): hx (i, j) =
h(i + 1, j) − h(i − 1, j) ∂h (i, j) ≈ . ∂x 2
Ez pontosan azt jelenti, hogy a képnek és a következ® kernelnek vettük a konvolúcióját: 1 1 0 −1 2 Hasonló gondolatmenettel jön ki, hogy az y parciális deriváltat jól közelíti: hy (i, j) =
∂h h(i, j + 1) − h(i, j − 1) (i, j) ≈ . ∂y 2
Ezt pedig a következ® kernellel való konvolúcióval kapjuk meg:
1 1 0 2 −1
Az ilyen kerneleket, amelyekkel deriválást közelítünk, derivált sz¶r®knek nevezzük.
13. ábra. A zaj hatása az élkeresésre, el®ször az eredeti, majd Gauss zajjal szennyezett képre alkalmazzuk a Canny élkeresést. Vegyük észre azt, hogy ekkor az eredeti pixelek értékeit mindkét esetben valahogyan teljesen a szomszédaival helyettesítettük. Az a veszély áll fent, hogy ekkor a zaj nagyon befolyásolja majd az eredményt. Ha a rögzít® készülékünk "halott" pixeleket is rögzít, akkor itt mindig feketék lesznek a pixelek és ez általában nagy változást eredményez, tehát a deriváltak is reagálni fognak rá. Ezért el®ször valamilyen simítási módszerrel el kell simítanunk a zajt és csak utána végezhetünk 19
további m¶veleteket. Mivel azt szeretnénk, hogy a kapott élek az irányítástól ne függjenek, ezért célszer¶ olyan simítási eljárást alkalmazni, amelynél a sz¶r® értékeit, csak a középponttól való távolság határozza meg, azaz radiálisan szimmetrikus a középpontra (circularly symmetric ). Ilyen sz¶r® a Gauss sz¶r®, mivel rengeteg el®nye is van (szétválasztható, helyettesíthet® több kisebb szórású sz¶r® egymás utána alkalmazásával, stb. . . ) ezért általában ezt szokták alkalmazni.
Gradiens alapú élkeresés A következ®kben egy egyszer¶ élkeresési módszert mutatok be, amely a gradiens er®sségét használja. A következ® lépésekb®l áll: 1. Kiszámoljuk a gradiens vektort minden pixelre úgy, hogy vesszük a konvolúciót a vízszintes és függ®leges derivált sz¶r®kkel (simítást is végzünk, ha kell). 2. A gradiens er®sséget kiszámoljuk minden pixelre. 3. Ha a gradiens er®sség egy bizonyos általunk megadott küszöbértéknél nagyobb, akkor ott (lehetséges) él pont van. Tehát az els® lépésben, ha simított képpel rendelkezünk, akkor veszünk egy derivált sz¶r®t vízszintesen és függ®legesen, ezután pedig továbblépünk a második pontra. Ha viszont simítást is szeretnénk végezni és utána meghatározni a deriváltat, akkor D ∗ (S ∗ I) = (D ∗ S) ∗ I,
ahol D jelölje a (vízszintes vagy függ®leges irányú) derivált sz¶r®t, S a simítást végz® sz¶r®t és I az eredeti képet, a konvolúció asszociativitása miatt, el®ször elvégezhetjük a simítósz¶r® deriválását, majd utána ennek az egy kernelnek vesszük a konvolúcióját az eredeti képpel. Gauss sz¶r®vel való simítás esetén a Gauss függvény (jelölje f (x, y)) parciális deriváltjai: f (x, y) = ∂f x − x2 +y2 2 (x, y) = − e 2σ ∂x 2πσ 4
1 − x2 +y2 2 e 2σ 2πσ 2
és
∂f y − x2 +y2 2 (x, y) = − e 2σ . ∂y 2πσ 4
Majd ezekb®l képezzük a kernelt, amellyel a konvolúciót végezzük, ahhoz hasonlóan, ahogyan az eredeti Gauss függvényt is diszkretizáltuk.
20
14. ábra. A Gauss függvény parciális deriváltjai ábrázolva, el®bb az x szerinti, majd az y szerinti derivált. Természetesen más kernelt is használhatunk, amellyel a simítást és a deriválást közelítjük. Egyik ilyen a Prewitt operátor, a vízszintes és függ®leges derivált közelítést jelölje Gx és Gy , az eredeti képet jelölje I . Ekkor: −1 0 1 Gx = −1 0 1 ∗ I −1 0 1
és
−1 −1 −1 0 0 ∗I Gy = 0 1 1 1
a konvolúciós kernelek szétválaszthatóak, a következ®képpen:
−1 0 1 1 −1 0 1 = −1 0 1 ∗ 1 −1 0 1 1
−1 −1 −1 −1 0 0 0 = 0 ∗ 1 1 1 1 1 1 1
Mindkét esetben a szétválasztásban szerepl® els® sz¶r® a deriváltat közelíti, a második pedig az átlagsz¶r®t. Természetesen konstansokban eltér azoktól a sz¶r®kt®l amiket eddig bevezettünk, de ez számunkra nem baj, hiszen (mivel minden pixel ugyanannyira tér el) ezt a küszöbválasztásnál tudjuk korrigálni. Egy másik példa a Sobel operátor, az el®z® jelölésekkel élve: −1 0 1 Gx = −2 0 2 ∗ I −1 0 1
és 21
−1 −2 −1 0 0 ∗I Gy = 0 1 2 1
a konvolúciós kernelek szintén szétválaszthatóak: −1 0 1 1 −2 0 2 = −1 0 1 ∗ 2 −1 0 1 1 −1 −2 −1 −1 0 0 0 = 0 ∗ 1 2 1 1 2 1 1
Itt a szétválasztásokban szerepl® els® sz¶r®k a deriváltat, míg a másodikak a Gauss sz¶r®t közelítik. Ha az els® lépést valamilyen módon elvégeztük, utána kiszámoljuk minden pixelre a gradiens er®sséget, vagyis az (i, j) pixelhez tartozó gradienser®sség: G(i, j) =
q G2x (i, j) + G2y (i, j)
A harmadik lépéshez pedig vegyünk egy bináris képet (B ), a t küszöbérték szerint (ahol t egy konstans érték), azaz B(i, j) =
ha G(i, j) > t ha G(i, j) ≤ t
1 0
Ez egy egyszer¶ módja az élkeresésnek, hátránya az, hogy a küszöbérték választása nagyban befolyásolja a kimenetet. Továbbá, hogy ez a módszer vastag éleket talál meg, azonban mi jobban szeretnénk egy pixel széles egymáshoz kapcsolódó kontúrokat. Ennek megoldása kés®bb következik.
LoG élkeresés Éles változások a szürkeérték függvényünkben az els® deriváltak maximum-, illetve minimumhelyein jelentkeznek. Ez annak felel meg, mintha a második deriváltaknak keresnénk a nullátmeneteit. Ehhez 2 dimenziós esetben a Laplace operátort használjuk:
3.5. De níció. Vegyünk egy f : R2 → R függvényt. Ehhez a függvényhez2 tartozó 2 2 dimenziós Laplace operátor az a ∆f : R2 → R függvény, amelyre ∆f =
∂ f ∂x2
+ ∂∂yf2 .
Szükségünk van a második deriváltak közelítésére, ezt szintén a Taylor-sorok segítségével közelítjük: 1 1 f (x + h) = f (x) + hf 0 (x) + h2 f 00 (x) + h3 f 000 (x) + O(h4 ) 2 3!
22
1 1 f (x − h) = f (x) − hf 0 (x) + h2 f 00 (x) − h3 f 000 (x) + O(h4 ) 2 3!
Az el®z® 2 egyenletet összeadva kapjuk:
f (x + h) + f (x − h) = 2f (x) + h2 f 00 (x) + O(h4 ) f (x + h) − 2f (x) + f (x − h) = f 00 (x) + O(h2 ) h2 Ezekb®l azt kaptuk meg, hogy az x szerinti második deriváltak közelíti az, hogy
ha a képnek a következ® kernellel vesszük a konvolúcióját: 1 −2 1
az y szerinti második deriváltat pedig, a következ® kernellel való konvolúcióval kapjuk meg: 1 −2 1
A Laplace operátor ezek összegét használja, azaz (I az eredeti kép):
1 1 0 1 0 1 −2 1 ∗ I + −2 ∗ I = 1 −2 1 + −2 ∗ I = 1 −4 1 ∗ I 1 1 0 1 0
Olyan helyeket keresünk, ahol ezt a m¶veletet elvégezve (közel) 0 értékeket kapunk. Viszont azokban a régiókban, ahol a kép egy konstans értéket vesz fel szintén 0-t fog visszaadni ez a m¶velet, tehát csak azokat a helyeket választjuk, ahol a gradiens er®sség is megfelel® nagyságú volt. Mivel a második parciális deriváltakat használtuk, ezért a kép érzékeny a zajra, tehát érdemes simítani a képet el®ször. Nagyon sok számítási munkát megspórolhatunk, ha a két m¶veletet egyszerre hajtjuk végre oly módon, hogy el®bb képezzük a Gauss sz¶r® Laplace operátorát, majd ezzel a módosított sz¶r®vel végezzük el a konvolúciót. Ezt a sz¶r®t hívják LoG (Laplacian of Gaussian ) sz¶r®nek (vagy LoG operátornak). Kiszámításához, vegyük a Gauss függvény parciális második deriváltjait: f (x, y) = ∂ 2f x2 − σ 2 − x2 +y2 2 (x, y) = e 2σ ∂x2 2πσ 6
1 − x2 +y2 2 e 2σ 2πσ 2 ∂ 2f y 2 − σ 2 − x2 +y2 2 és (x, y) = e 2σ . ∂y 2 2πσ 6
Ezek összege adja a LoG operátort: x2 + y 2 − 2σ 2 − x2 +y2 2 ∆Gσ (x, y) = e 2σ . 2πσ 6
23
Diszkretizálás után kapjuk a kívánt kernelt. Ezt a függvényt lehet két Gaussfüggvény különbségeként közelíteni, ezt DoG-nek (Dierence of Gaussians, megjegyzés: néhány helyen a DoG rövidítést a Derivative of Gaussian esetén használják, azaz a Gauss deriváltjára vonatkozik) szokták nevezni: ∆Gσ = Gσ1 − Gσ2
a szétválaszthatóság a DoG esetén is fenáll, így ez a LoG egy hatékony implementációja a gyakorlatban. (15. ábra)
15. ábra. LoG (σ = 1 esetén), valamint ennek DoG közelítése (σ1 = σ2 = √12 ).
√
2 és
Canny élkeresés A következ®kben a Canny élkeres®t mutatom be, valószín¶leg ez a leggyakrabban használt élkeres®. Ha feltételezzük, hogy a kép Gauss zajjal szennyezett, és lépcs® éleket keresünk, akkor vegyük a következ® elvárásokat az élkereséssel kapcsolatban: • jó detekció: a lehet® legtöbb élet találja meg, • jó lokalizáció: a megtalált él pontjai az él közepén helyezkedjenek el, • kevés hamis találat: egy élet csak egyszer jelezzen és a megtalált élek között
ne legyenek a zaj által okozott élek.
John Canny talált egy folytonos, lineáris sz¶r®t, amely maximalizálja ezeket a kritériumokat, sajnos nincs zárt alakja ennek az optimális sz¶r®nek. Viszont jól közelíti a Gauss deriváltja, ennek segítségével megkeressük az x és y szerinti deriváltakat, majd kiszámoljuk a gradiens er®sségét és irányát. Ezután megkeressük az élek középpontjait és a többi pontot elhagyjuk, ezzel megvékonyítva a kapott 24
éleket, majd kizárjuk a hamis találatokat hiszterézis küszöböléssel. A nem-maximumok elhagyásának (non-maximum suppression ) gondolata onnan ered, hogy élek ott vannak, ahol a gradiensnek lokális maximuma van, azonban különböz® éleknél eltér® lehet az az árnyalatváltozás, amelynek az él megjelenése köszönhet®, így szükségünk lesz egy módszerre, ami ezen segít. A fentebb már ismertetett gradiens alapú élkeres® sajnos nem tud olyan küszöböt találni, amely megtartja az éleket és a legnagyobb kontrasztú él mentén is csak az élközepeket találja meg, így a küszöbölés után olyan pontokat is megtartott az él mentén, amelyek nem az él közepén helyezkedtek el, ezzel megvastagítva az éleket. A módszer lényege az, hogy minden pixelre közelítjük a kiszámolt gradiens irányát 4 irány, vízszintes, függ®leges és a két diagonális valamelyikével. Ezután az ez iránymenti két szomszédjával összehasonlítjuk a gradiens er®sségeket, ezután, ha nem volt maximum, akkor nem ® lesz az él közepe, tehát elvetjük, ha ® volt a maximum, akkor megtartjuk. Ennek a módszernek másik megközelítése, ha nem a kiszámolt irányt közelítjük, hanem a képet folytonosnak tekintve interpoláció segítségével állapítjuk meg milyen értékekkel kell az összehasonlítást végezni (16. ábra, b®vebben [1] forrásban megtalálható).
16. ábra. A pontok a pixeleket jelölik, most éppen a q -ról szeretnénk eldönteni, hogy az él közepén helyezkedik-e el, sajnos a gradiens iránya nem megy át semelyik szomszédos pixelen sem, ezért interpoláció segítségével szeretnénk meghatározni a p és r helyen a gradiens er®sséget, tipikusan, ezek az értékek lineáris interpolációval, esetünkben p és r bal és jobb oldali szomszédja segítségével, számolható, ezek után, ha a q -nál lév® gradiens er®sség nagyobb, mint p és r gradiens er®ssége, akkor q élpont lesz; forrás: [1]. Ezután már csak a hiszterézis küszöbölés (hysteresis thresholding ) van hátra. Az optimális küszöbérték megtalálása (a gradiens alapú élkeresésnél is) mindig 25
problémát okozott, ha túl nagy a küszöb, rengeteg élet elveszthetünk, vagy szakadásokat okozhatunk, ha túl kicsi értéket választunk küszöbnek, akkor pedig sok olyan élet is találhatunk, amely eredetileg nem is volt él. Ezt a problémát próbálja orvosolni a hiszterézis küszöbölés azzal, hogy két küszöböt is megadunk, egy nagyobb és egy kisebb értéket, jelölje ezeket rendre H és L. Minden pont mely esetén a gradiens er®sség kisebb, mint L, azt elvetjük, és minden pont melyre a gradiens er®sség nagyobb, mint H , azt megtartjuk, ezeket nevezzük el er®s élpontoknak. Azon pontokat, amely a kett® közé esnek, nevezzük gyenge élpontoknak. Végeredményben azokat a pontokat tartjuk meg amelyek vagy er®s élpontok voltak, vagy olyan gyenge élpontok, hogy valamilyen úton (szomszédos gyenge élpontok sorozatán) el tudunk jutni egy er®s élpontba (ez természetesen nem jelentheti azt, hogy vastagodott egy él, mert ezt már a nem-maximumok elhagyása után alkalmaztuk).
17. ábra. Egy képen alkalmazva a különböz® élkereséses algoritmusok. El®ször Prewitt operátor segítségével, majd LoG és végül Canny élkereséssel. Nem cél a különböz® módszerek egymással történ® összehasonlítása, mert a kimenetet nagyban befolyásolja a különböz® küszöbérték választások.
4. Harris sarokdetektálás
A sarkokat (corner ) de niálhatjuk két él metszeteként, így azt gondolnánk, hogy az élkeres® algoritmusok segítségével tudunk könnyen sarokpontokat is találni, azonban, mint láthattuk (18. ábra), az élkeres® algoritmusok nem mindig m¶ködnek jól a sarkok körül. A sarokpontok megkereséséhez egy csúszóablakot fogunk használni, ezt vizsgálva ott lesz sarokpont, ahol az ablakot mozgatva bármely irányba, nagy változás tapasztalható a képfüggvény értékeinkben. Az ablakon belül nézve, három esetet különböztethetünk meg (19. ábra): 26
18. ábra. Látható, hogy az élkeres® algoritmusok a sarkok körül nem mindig viselkednek úgy, ahogy elvárnánk (Canny). • "sima" régió: nincs (vagy kevés) változás minden irányban, • "él": nincs változás az él mentén, • "sarok": jelent®s változás minden irányban.
19. ábra. "Sima" régió, "él" és "sarok"; forrás: [6]. A Harris sarokkeres® egy matematikai megközelítést ad arra, hogy melyik eset áll fent. Az ablak változása egy [u, v] eltolás hatására: E(u, v) =
X
w(x, y)[I(x + u, y + v) − I(x, y)]2 ,
(5)
x,y
ahol w(x, y) ablak (súly)függvény, például az ablakon belül 1, azon kívül 0 értéket vesz fel. Most írjuk fel a kétváltozós függvények Taylor-sorát az alábbi helyen: ∂f ∂f f (x + u, y + v) = f (x, y) + u (x, y) + v (x, y)+ ∂x ∂y 2 2 1 ∂ 2f 2∂ f 2∂ f + u (x, y) + uv (x, y) + v (x, y) + . . . 2 ∂x2 ∂x∂y ∂y 2
27
Ez alapján egy els®rend¶ közelítés: f (x + u, y + v) ≈ f (x, y) + u
∂f ∂f (x, y) + v (x, y) ∂x ∂y
ezt alkalmazzuk az (5) egyenletbe (jelölje Ix és Iy a parciális deriváltakat): E(u, v) =
X
≈
X
≈
X
w(x, y)[I(x + u, y + v) − I(x, y)]2
x,y
w(x, y)[I(x, y) + uIx (x, y) + vIy (x, y) − I(x, y)]2
x,y
w(x, y)(u2 Ix2 (x, y) + 2uvIx (x, y)Iy (x, y) + v 2 Iy2 (x, y))
x,y
Ha ezt átírjuk mátrix egyenletté, akkor azt kapjuk, hogy u E(u, v) ≈ u v M , v
ahol M egy (2 × 2) mátrix: M=
X x,y
Ix2 (x, y) Ix (x, y)Iy (x, y) w(x, y) . Ix (x, y)Iy (x, y) Iy2 (x, y)
A továbbiakban a kapott M mátrixot vizsgáljuk meg. Nézzük meg a különböz® minták felett (ezek a minták az "ablakok"), mit kapunk, ha kiszámoljuk a deriváltakat, és ezután ábrázoljuk a kapott értékek eloszlását. Ezeket az eloszlásokat jól tudjuk a kapott értékekre illesztett ellipszisek méretével és alakjával jellemezni. Kapcsolat van az M mátrix sajátértékei és a kapott ellipszisek között, mégpedig észrevehetjük, hogy ott lesz "sarok", ahol mindkét sajátérték értéke nagy.
28
20. ábra. Él, sima és sarok; forrás: [6].
21. ábra. A deriváltak, mint 2 dimenziós pontok ábrázolása, majd ellipszis illesztése; forrás: [6].
22. ábra. M sajátértékei alapján osztályozás; forrás: [7].
29
Ezek szerint, M sajátértékeivel jól jellemezhetjük a problémát. Azonban a sajátérték számítás a gyakorlatban költséges m¶velet, ezért Harris és Stephens a következ® sarkosságot jellemz® függvényt adta meg: R = det(M ) − k(trace(M ))2 = λ1 λ2 − k(λ1 + λ2 )2
itt k konstans, értéke k = 0.06. Itt determinánst és trace-t kell számolnunk, 2 × 2 esetben könnyen számolható, det(A) = a11 a22 − a12 a21 és trace(A) = a11 + a22 , ha A az alábbi mátrix: A=
a11 a12 a21 a22
A kapott függvény értékeire fogunk megfelel® küszöbölést alkalmazni. Ha (pozitív) nagy R értéke ott sarok lesz, ha negatív és a gradiens er®sség is megfelel®en nagy, akkor élet találtunk, ha pedig |R| kicsi, akkor ott sem él, sem sarok nem lehet. (Megjegyzés: tehát ezt élek keresésére is használhatjuk!) Ezután még nemmaximum elhagyást is alkalmazunk.
23. ábra. Sarokkeresés. A Harris sarokdetektáló algoritmus összefoglalható a következ® lépésekben: 1. Számítsuk ki az M mátrixot minden egyes képpont feletti ablakban és ebb®l megkapjuk az R sarkossági jellemz®t. 2. Keressük meg azokat a pontokat, amelyekre a sarkossági érték elegend®en nagy (R > t, ahol t küszöbérték). 3. Tartsuk meg ezekb®l a lokális maximumokat (vagyis nyomjuk el a nemmaximumokat). 30
Alkalmazás A képfeldolgozásban, valamint a számítógépes látás számos területén felmerül® probléma egy látványról készült képpár közötti pont megfeleltetések megkeresése. Ehhez megbízható jellemz®ket (feature ), tipikusan sarokpontokat nyerünk ki a képekb®l és ezeket megfeleltetjük egymásnak. Ennek a módszernek számos alkalmazása van, például: képek illesztése, 3D rekonstrukció, mozgáskövetés, objektumok azonosítása, stb. . . Egyik alkalmazása a panorámaképek készítése (24. ábra). Ezt a következ® lépések segítségével tudjuk elkészíteni (két kép esetén): 1. Jellemz®pontok keresése mindkét képen. 2. Kapott pontok megfeleltetése. 3. Megfeleltetések alapján a képpár összeillesztése.
24. ábra. Egy panorámakép készítése; forrás: [7]. 31
5. Matlab implementációk
A gyakorlatban sok programmal tudunk képfeldolgozást végezni. A szakdolgozatomban szerepl® képeket Matlab segítségével csináltam. A Matlab környezetben egyszer¶ parancsokkal elvégezhetjük a szükséges m¶veleteket. imread () függvénnyel beolvashatjuk a megfelel® formátumú (például .jpg vagy .tif ) képet, ezután az rgb2gray () függvénnyel tehetjük szürkeárnyalatú képpé, az egyszer¶bb kezelés érdekében, a képet érdemes az alapértelmezett uint8 típusról, double típusra átállítani az im2double () segítségével. A konvolúció m¶veletét az im lter () függvény segítségével tudjuk megvalósítani (vigyázat: a függvény alapméretezett beállítása a korreláció m¶veletet végzi, így külön be kell állítani paraméterként a konvolúciót), éleket az edge (), sarkokat pedig a corner () függvény segítségével kereshetünk, itt paraméterek segítségével kiválaszthatjuk a nekünk tetsz® eljárásokat. A (módosított) képet pedig, az imshow () függvénnyel tudjuk megnézni. A következ®kben három implementációt mutatok be: • Gauss kernel, ahol a szigmát választhatjuk meg, a kernel mérete ennek függ-
vényében változik:
f u n c t i o n k=Gaussk ( l ) szigma=l ; s z e l f=f l o o r (3 ∗ szigma ) ; [ x , y]= meshgrid(− s z e l f : s z e l f , − s z e l f : s z e l f ) ; t=exp ( − (1/(2 ∗ szigma ^2)) ∗ ( x .^2 + y . ^ 2 ) ) ; k=t /sum(sum( t ) ) ; • Só és bors zaj alkalmazása képekre (az intenzitást választhatjuk meg):
f u n c t i o n k=s a l t a n d p e p p e r ( img , l ) k=img ; f o r i =1: s i z e ( k , 1 ) f o r j =1: s i z e ( k , 2 ) r=rand ; i f r>=l e=r a n d i ( [ 0 , 1 ] ) ; k ( i , j )=e ; end end end 32
• Gradiens alapú élkeresés implementációja Prewitt operátor segítségével, a küszöbérték tetsz®legesen megadható (megjegyzés:a t mátrix kihagyható lett volna és elég lett volna egyb®l a k mátrixot számolni, ám néha jól jön, ha
megvan határozva az a részlet, amely a gradiens er®sséget számolja ki, mert máshol is felhasználható): f u n c t i o n k=P r e w i t t o ( img , t h r e s h ) x=[−1 0 1 ; −1 0 1 ; −1 0 1 ] ; y=[−1 −1 − 1; 0 0 0 ; 1 1 1 ] ; imgx=i m f i l t e r ( img , x , ' conv ' ) ; imgy=i m f i l t e r ( img , y , ' conv ' ) ; t=z e r o s ( s i z e ( img , 1 ) , s i z e ( img , 2 ) ) ; f o r i =1: s i z e ( t , 1 ) f o r j =1: s i z e ( t , 2 ) t ( i , j )= s q r t ( imgx ( i , j )^2+imgy ( i , j ) ^ 2 ) ; end end k=z e r o s ( s i z e ( img , 1 ) , s i z e ( img , 2 ) ) ; f o r i =1: s i z e ( t , 1 ) f o r j =1: s i z e ( t , 2 ) i f t ( i , j )> t h r e s h k ( i , j )=1; end end end
33
Irodalomjegyzék
[1] David A. Forsyth and Jean Ponce, Computer Vision: A Modern Approach, Prentice Hall 2002. [2] Richard Szeliski, Computer Vision: Algorithms and Applications, Electronic Draft 2010 (http://szeliski.org/Book/). [3] Stuart Russell and Peter Norvig, Arti cial Intelligence A Modern Approach, Second Edition, Prentice Hall 2003. [4] Emanuele Trucco and Alessandro Verri, Introductory Techniques for 3D Computer Vision, Prentice Hall 1998. [5] Chris Harris and Mike Stephens, A combined corner and edge detector, Plessey Company plc. 1988. [6] Robert Collins, Introduction to Computer Vision Lecture Notes Fall 2007 (http://www.cse.psu.edu/~rcollins/CSE486/). [7] Kató Zoltán, Digitális képfeldolgozás El®adásjegyzet 2014 (http://www.inf.u-szeged.hu/~kato/teaching/DigitalisKepfeldolgozasTG/).
34
