8 Képfeldolgozási alkalmazások 8.1 A képfeldolgozás alapjai A 8.1. ábra egy monokróm, 8bites (256 színű) kép felépítését mutatja meg. A kép 42120 pontból épül fel, 216 sora, 195 oszlopa van. Ha mint jelre tekintünk a képre, egyes elemére 2 indexszel tudunk hivatkozni : a sor- és oszlopindexével. Két módon is hivatkozhatunk a képpontra: [sor, oszlop] index vagy [oszlop, sor] indexszel. A két féle indexelés használatát az adott programnyelv kívánja meg. Általánosan elterjedt, hogy az első index 0-tól kezdődik, így a 8.1. ábrán található kép bal felső és jobb alsó pontjának koordinátái [oszlop, sor] indexelés szerint : (0,0) és (194,215). A képpont értéke attól függ, hány biten tároljuk. A fenti példa esetén a 8 bit 256 különböző színt jelent, amely a nullával kezdődő indexelés miatt 0..256 közötti értéket vehet fel. A képfeldolgozásban általános a 256 színű, szürkeárnyalatos kép: a nyolc biten (1 byte) tárolt képpont adattárolás és feldolgozás szempontjából előnyös, könnyen hozzáférhető. Több szín a feldolgozás szempontjából sokszor csak felesleges információt ad, a 256 színű skála általában elég a feldolgozás szempontjából. Másrészt a túlzott adatmennyiség a feldolgozás idejét drasztikusan megnövelheti. A mintavételezési törvény, a Nyquist kritikus frekvencia a képeknél is igaz. Maga a mintavételezés a képpontokat jelenti egy analóg képből. A rossz mintavételezésből ugyanúgy problémák adódnak (aliasing) : pl. a televízióban a műsorvezető halszálkás öltönyén a csíkok ismétlődési frekvenciája nagyobb a Nyquist féle kritikus frekvenciánál. Az aliasing itt is megjelenik, rossz mintavételezés során fekete-fehér hullámcsíkok szaladgálnak a csíkos öltönyön. Természetesen itt javítani könnyen lehet a problémán, a közelebbi felvétel nagyobb felbontást, mintavételi frekvenciát jelent. A 8.2. ábrán egy homokdomb finom vonulatai láthatóak 170×170 –es felbontásban, és ugyan ez 120×120-as méretben. Figyeljük meg a rosszabb felbontásban a nagyobb frekvenciát tartalmazó részletek (vékonyabb homokcsíkok) eltűnnek, kivehetetlenné vállnak.
{8.1.ábra. Kép és annak nagyított részlete}
{8.2. ábra. 170×170 –es kép és ugyanez 120×120 –as méretben, újramintavételezés után}
8.2 Fényerősség-kontraszt, hisztogram A képek feldolgozásánál fontos szerepet játszik egy statisztikai görbe, az úgynevezett hisztogram. Ezen gyakorisággörbe a kép pontjainak előre definiált változó –tartományaiba eső számát, vagy gyakoriságát adja. Egy-egy hasáb szélessége a hisztogrammon a változó tartományt, magassága a gyakoriságot mutatja. A legegyszerűbb változó tartomány az, ha a 256 db intenzitás értéket 256 tartományra osztjuk. Ekkor –s ez az általánosan használt tartomány- a 256 szürkeárnyalat gyakoriságát mutatja a képben. 10 db változó tartományt definiálva az egyes tartományok 25.6 szélességűek lesznek. Egy kép minőségét befolyásolja a fényerősség, és a kontraszt, a képek alapvető két tulajdonsága. A fényerősségnem más, mint a kép általános fényessége, sötétsége. A kontraszt a fényerősség különbséget jelenti a képben előforduló objektumok között. Például egy fehér háttér előtt álló világos kutya rossz kontrasztú, míg fekete kutya esetén a kontraszt jónak mondható. A 8.3. ábra 4 példát hoz a fényerősség, és a kontraszt hatásairól . Ha a fényerősséget túl kicsire állítjuk a sötét részek (a), ha túl nagyra a világos részek (b) mosódnak egybe, információt vesztünk az eredeti képhez viszonyítva, részletek vesznek el.
(a) fényerősség túl kicsi (b) fényerősség túl nagy
(c) kontraszt túl kicsi (d) kontraszt túl nagy {8.3. ábra. Fényerősség és kontraszt hatása egy ujjlenyomatra.}
A fényerősség növelésével minden képpont értéke megnő, a kontraszt növelésével a világos területek sokkal világosabbak, a fekete területek sokkal sötétebbek lesznek. A kontraszt változtatásánál, ha túl kicsire vesszük, nincsenek igazán különbségek a világos, sötét részek között (c), ha túl nagyra választjuk, szinte csak fehér, vagy fekete pontjaink lesznek, a közbenső árnyalatok eltűnnek (d). A fényerősség, kontraszt személtetéséhez tekintsük a 8.4. (a) ábrát. Ezen találhatunk egy transzformációs görbét, amely minden egyes bemeneti intenzitásértékhez hozzárendel egyetlen kimeneti intenzitásértéket. Ezt a görbétkimeneti transzformációs görbének, vagy elterjedtebb nevén gamma görbének nevezik. Az (a) ábrán a gamma görbe egy 45°-os egyenes, vagyis minden bemeneti intenzitásértékhez önmagát rendeli. Vagyis minden képpont értéke ugyan az marad, a kép nem változik semmit. A hisztogramot megfigyelve látjuk, hogy a kép alulexponált, 180 feletti intenzitásértékek nem is találhatóak rajta, a hisztogram bal oldala hangsúlyos. A (b) és (c) ábrákon láthatjuk a fényerősség változtatásának hatását. Túl nagy fényerősség választásánál (b) minden képpont intenzitásértékéhez konstans adódik. Mivel a maximális intenzitásérték 255, ezt nem lépheti túl a művelet, ezért sok konstanssal megnövelt
intenzitásérték itt "halmozódik". A hisztogram erősen jobbra tolódott, a sötét intenzitással rendelkező pontok száma erősen lecsökkent. A gamma görbe –mivel minden intenzitásértékhez konstans adódik – eltolódik. Látható, hogy a görbe szerint már a nulla intenzitású, fekete pontok is kb. 130-as intenzitásértéket kapnak, vagyis a kapott képen 130 – nál kisebb intenzitású pontok nem is találhatóak. A fényerősség erőteljes lecsökkentésével (c) ellentétes folyamat játszódik le: a hisztogram bal oldala lesz hangsúlyos, a gamma görbe lefelé tolódik, világos képpontok szinte eltűnnek a képről. A kontraszt változtatásának hatását a (d) és (e) ábrákon láthatjuk. Erőteljes növelésével a gamma görbe meredeksége megnő, csökkentésével ezen meredekség lecsökken.
{8.4. ábra. Fényerősség és kontraszt szemléltetése}
8.3 Diszkrét Fourier Transzformáció a képfeldolgozásban A Diszkrét Fourier Transzformáció (DFT) 2 dimenzióban hasonló az 1 dimenziós megvalósításhoz. Az indok, hogy a képfeldolgozásban ez egy kevésbé használatos technika, mint a hangfeldolgozásban az, hogy a kapott spektrum értelmezése nehezebb, ránézésre nem mond annyi hasznos információt a képről. Mivel a kép egy I[x,y] kétváltozós függvénnyel írható le, ezért kétdimenziós DFT-ra van szükségünk. A DFT egy I[x,y] képet egy ugyancsak -es F[u,v] tartományba képzi. A Diszkrét Fourier Transzformáció összefüggése a következő:
Az inverz transzformáció egy -es I[x,y] képbe:
(IDFT)
egy
spektrumból
transzformálja F[u,v]-t
Egyváltozós függvények esetén a spektrum egyetlen eleme egy adott frekvenciájú sinus, cosinus hullám. Kétváltozós DFT esetén az F[u,v] spektrum egyetlen pontja kétváltozós sinus ill. cosinus hullámot takar. Ezek szerint a kép, a kétváltozós függvény változó irányú, és hullámhosszú sinus és cosinus vonulatok összegeként fogható fel. A DFT a képet, mint függvényt térben bontja harmonikus összetevőkre.
A spektrum – hasonlóan az egyváltozós függvények DFT-hez – komplex elemekből áll. Ezek alapján a Fourier energia spektrum a következő:
Azonban kérdéses maradt, milyen frekvencia, illetve hullámhossz tartozik.:
A térharmonikus irányát a következő képen határozható meg:
A frekvencia, vagy ahogy 2 dimenzióban nevezik a térfrekvencia reciproka. Az előbbiek alapján bármely (u,v) indexű DFT elem kiszámítható, és tudjuk, u és v indexek maximuma N. Ezen kívül tudjuk, hogy a Fourier transzformáció periodikus, vagyis:
Ez viszont azt eredményezi, hogy F(u,v) mátrix elemei a síkon minden irányban, ciklikusan ismétlődnek. Elviekben mindegy lenne, melyik transzformáltat nézzük, azonban elterjedt a 0tól való indexelés. Az origóban, az (u,v)=(0,0) találjuk az egyenkomponenst, amely konstans a képeknél az átlagos fényességet adja meg. Az origótól minden irányban távolodva a térfrekvenciák nőnek, u és v index irányában egyaránt –N/2 és N/2 határokig. Mivel az összefüggés alapján a transzformáció indexelése [0..N-1]- ig tart, ezért az így kapott spektrum közepe ( P(N/2,N/2)) a nagy térfrekvenciákat tartalmazza. Ha azt szeretnénk, hogy a spektrum közepe a kis térfrekvenciákat mutassa, ahhoz a 8.5. ábra szerinti kis átalakítást kell elvégezni. Ezek után a spektrum mindig az átalakított, középen kis frekvenciákat tartalmazó mátrixot fogja jelenteni.
{8.5. ábra. 2 dimenziós amplitúdó spektrum átalakítás a frekvenciák jobb szemléltetése végett}
Tekintsük a 8.6. és 8.7. ábrákon látható 2 változós sinus függvények spektrumát! Mivel térbeli sinus hullámokról van szó, ezért a spektrum egyetlen helyen tartalmaz kiemelkedő amplitúdót. Azonban a transzformáció szimmetrikus tulajdonsága miatt P(-u,-v)= P(u,v), illetve a P(0,0)-ban található egyenkomponens miatt 3 pont található a spektrumban. A 8.6. ábrán található P(0,17) ponthoz tartozó sinus hullámhossza:
ebből a térfrekvencia:
A térharmonikus iránya:
Míg a 24. ábrán található, ferdén futó sinushullámnál:
{8.6. ábra 2 változós sinus függvény és spektruma,
{8.7. ábra. 2 változós sinus függvény és spektruma,
}
}
A 8.8. ábrán látható ujjlenyomat energiaspektrumát megvizsgálva a térharmonikusokról kiderül, hogy az origótól mérve kb. ugyan olyan távolságra (50) helyezkednek el a szignifikáns amplitúdójú pontok, vagyis a térfrekvenciájuk hasonló. Amiben különböznek, az az irány. Ha figyelmesebben megnézzük a képet, látható, hogy a barázdák mindig kb. ugyan olyan távolságra vannak, és félkör alakban , kb. 45°-tól +135°-ig húzódnak.
{8.8. ábra. Ujjlenyomat és spektruma}
8.4 Szűrés frekvenciatartományban
A Fourier analízis – 1 dimenziós függvényekéhez hasonlóan – a 2 dimenziós függvényeknél is ugyan úgy működik. Használhatósága azonban kisebb, képek frekvenciatartománybeli spektruma nem olyan egyértelműen hordozza az információt, mint hangok esetében. Zenei jelek esetén a kapott frekvencia spektrum könnyen értelmezhető, adott frekvenciakomponensek keresése, módosítása nem okoz gondot. A 2D DFT esetén azonban a spektrum is kétváltozós függvény, egyes komponensek információtartalma a felhasználó számára nem bír olyan nagy értékkel. Éppen ezért, mint az 5. fejezetben tárgyalt szűrőtervezés, képfeldolgozásban nem létezik. Szűrés azonban létezik frekvenciatartományban, azonban itt nem adott térfrekvenciákról, hanem régiókrólbeszélhetünk. A 8.9. ábra mutatja a szűrők felépítését, a 8.10. ábra a szűrés sematikus ábráját mutatja. A szűrést a konvolúció segítségével lehet elvégezni, vagyis a képet konvolválni kell a szűrővel. Mivel a szűrő frekvenciatartományban lett tervezve, a konvolúciót is ebben a tartományban kell elvégezni, ami itt szorzást jelent a kép spektruma illetve a szűrő között. Aluláteresztő szűrő esetén (ha a 8.5. ábra szerinti spektrumot használjuk) a módosítatlan tartomány a spektrum középső része, ahol a kis frekvenciák találhatóak. Nagy frekvenciák törlése (vagy elnyomása) esetén az inverz transzformáció után kapott eredmény elmosódottabb, életlenebb lesz, de a zajok eltűnnek. Nagy frekvenciák kiemelése esetén a kép élessége javul, viszont a zaj is nő. Sokkal finomabb megoldást jelent, ha a vágandó frekvenciás összetevőket nem töröljük, hanem egy 2D Gauss görbével súlyozzuk az egyes összetevőket. Ebben az esetben a 2D DFT transzformált minden elemét meg kell szorozni a megfelelő csillapítási tényezővel. Mivel a DFT transzformáltat valós számmal szorozzuk meg, így az összetevők fázisa változatlan marad.
(a) aluláteresztő szűrő (b) felüláteresztő szűrő (c) sáváteresztő szűrő {8.9. ábra. Szűrők 2D spektrum esetén.}
{ 8.10. ábra. Szűrés-modell 2D frekvenciatartományban. }
{8.11. ábra. Alul- és felüláteresztő szűrés. (a) eredeti kép (b) aluláteresztő (c) felüláteresztő szűrés esetén.}
A digitális jelfeldolgozás módszerei a képekkel kapcsolatos különböző manipulációk terén is nagyon hatékonynak bizonyulnak. E fejezet a képfeldolgozásban használatos legfontosabb módszerek áttekintését adja, különböző alkalmazási példákon keresztül. 8.5 Alapvető szűrők a képtartományban A képek feldolgozásakor – csakúgy, mint a hangok esetében – az egyik legalapvetőbb feladat a szűrés. A következőkben a 2D konvolúciós szűrésben használatos szűrőkerneleket, valamint az ezekkel végzett konvolúciós szűrés hatását vizsgáljuk. A szükséges alapfogalmak a 4.4 fejezetben a 2D konvolúció elvénél már tárgyalásra kerültek. 8.5.1 Az átlagoló szűrő
A képek simítószűrésére alkalmas, „elkeni” a gyors változásokat, így aluláteresztő szűrőként viselkedik. Az alábbi ábrán egy 3x3-as szűrőkernel és a szűrő frekvenciafüggvénye látható.
(a)
(b)
{8.12 ábra. 2D átlagoló szűrőkernel (a), és frekvenciafüggvénye(b)}
A szűrő – ahogy az nevéből is sejthető – az szűrést oly módon végzi, hogy a környező képpontok súlyozott átlagát képezi, súlyfüggvénye tehát egy olyan mátrix amelyben minden elem a mátrix dimenziói szorzatának reciproka. 8.5.2 Az élkiemelő szűrő Az előző pontban tárgyalt simítószűrő viselkedésével pontosan ellentétes viselkedést megvalósító szűrő. A nagyfrekvenciás komponenseket tartja meg a képből, míg a kisfrekvenciájúakat csillapítja, ezzel felüláteresztő viselkedést valósít meg. A szűrő súlyfüggvénye és frekvenciafüggvénye az alábbi ábrán látható.
(a)
(b)
{8.13 ábra. Élkiemelő szűrőkernel (a), és frekvenciafüggvénye (b)}
8.5.3 A medián szűrő Ez a szűrő alapelvében hasonlít az átlagoló szűrőre, az eltérés csak annyi, hogy a képpontok átlaga helyett a képpontok mediánját használja fel az eredményként keletkező képben. Ezzel a kis változtatással – ahogy azt nemsokára látni fogjuk – bizonyos alkalmazásokban sokkal hatékonyabb lesz, mint az átlagoló szűrő. Egy halmaz elemeinek mediánja , a halmaznak az az eleme, amelynél a halmaz elemeinek fele kisebb vagy egyenlő, az elemek másik fele pedig nagyobb vagy egyenlő. A szűrés tehát ez esetben is egy maszk segítségével történik, de ez a maszk most nem egy konvolúciós kernel, hanem képpontok egy halmazának kiválasztására szolgál. Az eredményként keletkező képben a maszk középpontja alatti pixel új intenzitásértéke, a kiválasztott képponthalmaz intenzitásértékeinek mediánja lesz. A medián szűrés hatására a képben található kiugró intenzitásértékű képpontok fényessége közeledni fog a környezetük fényességéhez, szélsőséges esetben, ha egy homogén képrészletben található egy az átlagfényességnél sötétebb vagy világosabb képpont, az egyszerűen eltűnik a képből. Emiatt a tulajdonsága miatt a medián szűrő nagyon hatékonyan távolítja el az impulzusszerű zajokat. 8.6 Az alapvető szűrők használata A következőkben két egyszerű zajszűrési feladaton mutatjuk be a fentebb tárgyalt szűrők tényleges viselkedését. 8.6.1 Normális eloszlású véletlen zaj eltávolítása Az egyik leggyakoribb zajtípus, amivel a jelfeldolgozási feladatok során találkozunk, az additív normális eloszlású véletlen zaj. Ennek eltávolítása aluláteresztő szűréssel történik, a képtartománybeli aluláteresztő szűrést pedig a simító szűrők (átlagoló, medián) valósítják meg. A következő ábrán a szűrés eredménye látható.
(a)
(b)
(c)
(d)
{8.14 ábra. Simítószűrés a képtartományban. Eredeti kép (a), zajos kép (b), átlagolással szűrt kép (c), medián szűrővel szűrt kép (d)}
Ahogy az ábrán jól látható, az egyszerű átlagoló szűrő és a medián szűrő teljesítménye közel ugyanolyan amennyiben a feladat normális eloszlású véletlen zaj szűrése, egy kevés különbség azért látható a két szűrt kép között. Az átlagoló szűrő, működéséből adódóan egy kicsivel homogénebb képet eredményez, valamint az apró részletek is egy árnyalatnyival jobban megmaradnak, így azt mondhatjuk, hogy e zajtípus eltávolításához az átlagoló szűrő a megfelelő választás. Azt is észrevehetjük, hogy a szűrt képeken bőven maradt zaj, csak a
szemcsézettség csökkent, ahogy az aluláteresztő szűrők „elkenték”, elsimították a gyors átmeneteket. 8.6.2 Impulzusszerű zaj eltávolítása Az impulzusszerű zaj – a normális eloszlású véletlen zajhoz hasonlóan – igen gyakran fordul elő, így az ilyen zajok hatékony eltávolítására alkalmas szűrők nagy jelentősséggel bírnak. E zajtípus szűrésénél szintén simítószűrőt használunk, de ahogy azt látni fogjuk a medián szűrő teljesítménye az impulzusszerű zajok eltávolításában messze meghaladja az átlagoló szűrőét.
(a)
(b)
(c)
(d)
{8.15 ábra. Impulzusszerű zaj eltávolítása. Eredeti kép (a), zajos kép (b), átlagolással szűrt kép (c), medián szűrővel szűrt kép (d)}
Az ábra magáért beszél. Míg a normál véletlen zaj esetében a két simítószűrő közel azonos végeredményt produkál, addig az impulzusszerű zaj eltávolításában a medián szűrő hatékonysága annyival jobb, hogy e területen az átlagoló szűrő nem tud versenyezni vele. 8.7 Mintafelismerés és korreláció Ebben a fejezetben a képfeldolgozás egy olyan területe kerül tárgyalásra, amelyről eddig csak futólag esett szó a jelfeldolgozás alapvető technikáiról szóló fejezetben. A mintafelismerés egy fontos és hasznos képfeldolgozási alkalmazás, melyet széleskörűen lehet alkalmazni a legkülönbözőbb területeken, mint pl. ipari végtermékek minőségellenőrzése, vagy robotok kalibrálása, hogy csak egy párat említsünk a számtalan lehetőség közül. A mintafelismerés fejlettebb, összetettebb alkalmazásai közé tartoznak a különféle biometriai módszerek, mint: ujjlenyomat-felismerés, retina ill. arc azonosítás. E módszerek adekvát megvalósítása olyan összetett algoritmusok működési elvének – ill. ezek implementációjával kapcsolatos problémák – ismeretét feltételezi, melyek túlmutatnak jelen jegyzet keretein. A mintafelismerés egyszerűbb alkalmazásainak megértéséhez és megvalósításához viszont elegendő ismeret áll a rendelkezésünkre, így vizsgálódásaink körét ezekre szűkítjük. 8.7.1 A korreláció mint összehasonlítás A korreláció művelete a 4.fejezetben érintőlegesen már tárgyalásra került, most részletesen megvizsgáljuk ezt a módszert, valamint használhatóságát a minta-felismerés terén. A művelet összehasonlító tulajdonságának megértéséhez képzeljünk el egy vektort a kétdimenziós
térben
,
valamint
tekintsük
a
tér
kanonikus
bázisát . Ha most arra lennénk kíváncsiak, hogy az vektor „mennyire” esik valamelyik bázisvektor irányába, azaz mekkora az adott bázisvektor irányába eső komponense, nem kellene mást tennünk, mint képezni az és a megfelelő bázisvektor skaláris szorzatát az alábbiak szerint.
A fenti összefüggésből azonnal látszik, hogy a skalárszorzat tulajdonképpen nem más, mint az vektor első koordinátája, és hasonlóan, ha a másik bázisvektort használjuk -ben, akkor a vektor második koordinátája lesz az eredmény. Összefoglalva az előbbieket, azt mondhatjuk, hogy a skaláris szorzással tulajdonképpen annyit tettünk, hogy
összehasonlítottuk tetszőlegesen választott vektorunkat (
) valamilyen megadott mintával
( ), és eredményként éppen azt kaptuk, hogy ezek mennyire hasonlítanak egymásra. Természetesen a dolog tetszőleges dimenziószámú vektorra működik (akár végtelen dimenziós vektorok esetében is ld. Wavelet-transzformáció, Fourier-transzformáció), ekkor az általános összefüggés az vektor és az minta korrelációjára:
Ha a fenti elveket át akarjuk ültetni a képfeldolgozásba, csak annyit kell változtatnunk a összefüggésen, hogy a művelet argumentumai vektorok helyett mátrixok legyenek.
Ez az összefüggés pedig maga a kétdimenziós korrelációt definiáló egyenlet egy méretű minta esetére. A vázolt elvek alapján a 2D korreláció olymódon lesz használható mintafelismerésre, hogy az mátrix lesz a keresendő minta, a kép amelyben a mintát keressük, a korreláció eredménye pedig egy olyan mátrix amelynek egy adott helyen található értéke azt mutatja meg, hogy a kép adott helyén található szegmense mennyire esik a minta „irányába”, azaz mennyire hasonlít a mintára. Fontos megemlíteni, hogy árnyalatos képen végezni a korrelációt nem igazán hatékony, sokkal hatékonyabb a kép éleiben a minta éleit keresni. A hatékonyság érdekében tehát célszerű elvégezni valamilyen élkiemelő szűrést a képen, vagy ami még jobb, egy delta-kódolást végezni a képen és a mintán egyaránt a korreláció előtt. 8.7.2 A korreláció megvalósítása A művelet megvalósításának legegyszerűbb módja az, amit a 2D konvolúció működését leíró 4.4 fejezetből már ismerünk, azaz egy konvolúciós maszkot (kernel) végigtolunk a képen úgy, hogy a maszkmátrix középpontja bejárja az összes képpontot az eredeti képen, és minden képpontra elvégezzük a -ban kijelölt műveleteket. Az eredményül kapott mátrixban megkeressük a legnagyobb elemet, és ennek koordinátái mutatják meg, hogy a kép hol hasonlít legjobban a keresett mintára. 8.7.3 A korreláció megvalósítása konvolúció segítségével A korreláció művelete – ahogyan az a 4.3 fejezetből ismert – igen nagy hasonlóságot mutat a konvolúcióval, így a konvolúció felhasználható a korreláció eredményének
kiszámítására. Ehhez mindössze annyit kell tennünk, hogy a keresendő mintát tükrözzük mindkét tengelyére, hisz a 2D konvolúciót definiáló összefüggés mindössze ebben tér el a korrelációt leíró egyenlettől.
Így ahogyan azt az egydimenziós esetnél már láthattuk elvégezhető a korreláció a frekvenciatartományban a konvolúció műveletének segítségével, mely módszer bizonyos esetekben jóval gyorsabb, mint a hagyományos változat. 8.7.4 A korreláció megvalósítása a konvolúció egy gyors implementációjával Ebben a szakaszban egy olyan korrelációs módszert fogunk megvizsgálni, amely már közelebb áll a valódi alkalmazásokhoz. Mind a korreláció, mind pedig a konvolúció nagy hátránya a végrehajtásához szükséges sok számítás, és ezzel természetesen sok idő. Minden kép felfogható olyan mátrixként amely 2D impulzusfüggvényekből áll, azaz minden kép előállítható eltolt és skálázott impulzusok összegeként. Ezen impulzusok amplitúdója az adott helyen lévő pixel intenzitásértéke. Mivel a konvolúció lineáris művelet ezért megoldható, hogy az egyes impulzusokkal külön-külön számoljunk a műveletvégzés során és a végső eredmény ezek összegeként áll elő. Tehát minél kevesebb impulzus van a képen annál rövidebb ideig tart a konvolúció elvégzése. Ha csökkenteni tudnánk az impulzusok számát, akkor időt tudnánk megspórolni a műveletvégzés során. Tekintsük a képet, mint egy kétváltozós diszkrét függvényt a D tartományon, majd osszuk fel a D-t diszjunkt résztartományokra a következőképpen: és . Ezután minden résztartományon számítsuk ki az átlagos intenzitást (F) és a résztartomány minden pontjának adjuk ezt az új intenzitásértéket. Ezzel a képet konstans intenzitású résztartományokra bontottuk, tehát előállítottuk a kép egy közelítését. A közelítés előállításánál természetesen olyan résztartományokat kell választani, ahol az intenzitás már amúgy is „majdnem” konstans. Azt, hogy melyik tartomány felel meg ennek a kritériumnak, akkor tudjuk eldönteni, ha definiálunk egy hibafüggvényt és meghatározzuk, hogy mennyi lehet a maximális hiba egy résztartományon. A hiba alatt itt természetesen azt értjük, hogy a közelítő tartomány mennyiben különbözik az eredeti képtől, így adódik: . Ha a fenti összefüggésben szereplő F konstanst az átlagfényességgel helyettesítjük, a az alábbi formát ölti:
. Ezzel megvan a hibakritérium. Ha egy résztartományon egy előre definiált küszöbértéknél (H) nagyobb a hiba, akkor azt további résztartományokra kell bontani, és újból alá kell vetni a hibakritériummal kapcsolatos vizsgálatnak. A felosztás konkrét megvalósítását többféleképpen el lehet végezni, az egyik legegyszerűbb a kvadrális fa felbontás, ahol egy résztartományt mindig négy egyenlő részre osztunk fel, így a képet alkotó összes résztartomány egy kvadrális fa leveleiben foglal helyet. Ennél egy kicsivel összetettebb, de hatékonyabb módszer, ha a résztartományt csak két további részre osztjuk. Ennél a rekurziónál azonban figyelni kell, hogy váltogassuk a függőleges ill. a vizszintes elosztást, hogy a kialakuló résztartomány-rendszer minél egyenletesebb legyen. A felosztás után, ha mindkét tengely mentén elvégzünk egy delta-kódolást (diszkrét differenciálást), akkor csak a résztartományok sarokpontjain marad nullától különböző értékű impulzus, hiszen a résztartományok belsejében a függvényérték konstans. Ezt szemlélteti az alábbi ábra.
{8.16. ábra. Konstans résztartomány diszkrét differenciálása}
A delta-kódolás után előálló függvényben sokkal kevesebb impulzus van, mint az eredeti képben, így a konvolúció elvégzéséhez szükséges idő jelentősen csökken. A művelet elvégzése után a helyes eredmény előállításához természetesen szükség van egy deltadekódolásra is. A következő ábrán a résztartományokra való felbontás eredményét láthatjuk.
(a) (b)
(c) (d) {8.17. ábra. Résztartományokra osztott kép. Eredeti kép (a), H=10000 küszöbértékkel felosztott kép (b), H=1000 küszöbértékkel felosztott kép (c), a (b) kép résztartomány határvonalak nélkül (d).}
Az ábrán látható, hogy ha a felosztás megfelelően finom, akkor a kép minősége gyakorlatilag nem sokat változik, főleg ami a rajta található jellegzetes mintákat illeti, így ez nem befolyásolja jelentős mértékben a minták felismerésének hatékonyságát. A következőkben megvizsgáljuk a korreláció hatékonyságát a mintafelismerésben. A képünk a következő ábrán látható bohóc, a keresendő minta pedig a bohóc bal szemének egy részlete. A keresés eredményét egy kétváltozós függvény formájában láthatjuk, melynek legnagyobb amplitúdójú értékéhez tartozó koordinátái jelentik a keresett minta pozícióját a képen.
(a)
(b)
(c)
{8.18. ábra. A 2D korreláció. Eredeti kép (a), keresendő minta (b), az eredményfüggvény (c)}
Az ábrán látható, hogy a korreláció eredménye egy jól definiált csúcs némi zajban, így a minta helyét igen pontosan meg tudjuk határozni. Mondhatjuk tehát, hogy egyszerű mintafelismerési alkalmazások esetében a korreláció önmagában is elég jól használható módszer, a hátrányként jelentkező végrehajtási időt pedig csökkenthetjük, ha a konvolúciót hívjuk segítségül a művelet végrehajtásához. 8.8. Dekonvolúciós algoritmusok A 8.19. ábrán látható a lineáris rendszer felépítése. A képfeldolgozás alap problémája, az inverz szűrés, vagyis a zajos, módosított képből az eredetit visszakapni. Ennek megoldására az időtartományban bonyolult algoritmusok adódnak. A megoldás frekvenciatartományban egyszerűnek tűnik. A frekvenciatartománybeli konvolúcióból leszármaztatva:
Azonban a 8.19. ábra rendszermodellből adódóan a zaj, és bizonyos térfrekvenciáknál a 0-val való osztás okoz problémát. A zaj az osztás miatt (mivel általában a zaj kis amplitúdóval jelentkezik) kiemelődik. Ezen problémák miatt az összefüggésben megadott dekonvolúciós modell nem működik megfelelően.
{8.19. ábra. Lineáris rendszer elvi felépítése. b jelenti a rendszer válaszfüggvényét (PSF), jelentse a fellépő véletlen - zajt.}
A probléma tehát a következő : adott egy lineáris rendszeren kimenetén megjelenő kép, illetve a súlyfüggvény (PSF) , amellyel az eredeti képünket módosítottuk - példaként egy aluláteresztő, vagy Gauss–féle konvolúciós szűrővel. A B súlyfüggvény ismert, a legtöbb rendszernél vagy kimenet alapján ismerjük (pl. látható az elmosás a képen, az a priori ismereteink alapján tudjuk, hogy a PSF egy Gauss-féle aluláteresztő szűrő), vagy előállítjuk (az adott lineáris rendszeren impulzus bemenőjelre megkapjuk a kimenetet). Az inverz művelet, a dekonvolúció megoldására számos megoldás, közelítés létezik, azonban általános megoldást nem lehet adni. Minden egyes inverz művelet függ a lineáris rendszer felépítésétől. A következőkben módszerek láthatóak az inverz művelet megvalósítására. 8.8.1. Általános inverz szűrés Az inverz szűrés egy restaurációs technika, amely során pl. Gauss-szűrővel elmosott, zajos képből kell visszaállítani az eredetit. Azonban, az inverz-szűrés rendkívül érzékeny a zajokra. Ha a 8.13-as összefüggés alapján a bemeneti képünket egy alul-áteresztő filterrel konvolváltuk, ebből adódóan inverz műveletként az eredeti kép visszaállításához a kapott kép felül-áteresztő szűrővel való konvolúcióját jelenti. Vagyis :
ahol H komplex függvény jelenti a felül-áteresztő szűrő 2D FFT transzformáltját. Ideális esetben ezen H szűrőt megkapjuk B alul-áteresztő filter transzformált függvényének reciprokaként. Azonban, problémát jelent B nulla, illetve nulla-közeli értékei. Ezek vagy valamely kis amplitúdójú térfrekvencia-összetevőt, vagy valamilyen zajt jelentenek. Ezen összetevők reciproka kimagaslóan nagy értéket jelenthet az amplitúdó-összetevők viszonylatában. B reciproka helyett használjuk ennek nagyon jó közelítését, amely kiküszöböli az előző problémát:
érékének állításával alakíthatjuk (sávkorlátozhatjuk) az inverz-filter értékeit. A másik probléma, a 0-val való osztás megoldásaként B térfrekvenciáihoz tartozó amplitúdóösszetevőket korlátozhatjuk:
ahol n értéke reciproka, vagyis n=1/. A 8.20 . ábrán látható az inverz szűréssel, =10000 értékkel végzett inverz szűrés eredménye. Az eredeti (a) képet zajjal terheltük, illetve Gauss-féle konvolúciós szűrővel elhomályosítottuk. Inverz szűrés eredményeként (c) ábrát kapjuk.
(a)
(b)
(c)
{8.20. ábra. Eredeti (a) , közepes fehér-zajjal telített és Gauss-PSF – el konvolvált (b) kép, illetve általános inverz szűréssel kapott eredménye (c).}
8.8.2. Iteratív eljárás A következő megoldás mögött egy iteratív algoritmus áll, amely során az eredeti f diszkrét függvényt g válaszfüggvény ismeretében lépésenként közelítjük. Az iteráció során F 0 Fourier transzformált kezdőértékeit G, a lineáris rendszer kimenetén kapott frekvenciafüggvény értékei alapján állapítjuk meg, azaz
és ekkor
Ha
az iteráció során jó közelítést ad, akkor
ad. a konvergencia-faktor,
konvolúciója B-vel G-hez közeli értéket
konvergenciáját határozza meg.
A 8.18. összefüggést rekurzívan megoldva:
=
Ha 0 , vagyis k , eredményként F inverz filterrel való konvolúcióját kapjuk. értékének, vagyis a konvergencia-faktornak a következő feltételt kell teljesítenie konvergencia esetén:
és Nagyobb esetén a konvergencia gyorsabb, azonban túl nagy érték esetén a sorozat divergens lehet. Konvergens, illetve divergens értékeket mutat be a 8.21. ábra különböző iterációs lépéseknél .
(a)
(b)
(d) (e)
(c)
(f)
{8.21. ábra. Eredeti kép (a) , zajos+életlen kép (b) , Iteratív inverz szűrés divergens (c) =0.3 , illetve konvergens (=0.03) méréssorozat esetén N=50 (d), 300 (e) ,1000 (f) számú iterációnál. Túl alacsony esetén a túl lassú iteráció eredménytelen, a kép teljesen sötét marad.}
Vizsgáljuk meg a konvergenciát Lambda-MSE tekintetében. a 8.22 . és a 8.23. ábrákon két elmosott kép szempontjából vizsgáltuk meg az inverz szűrés hatékonyságát különböző
konvergencia-faktorok tekintetében. Az iteráció száma minden induló esetén N=1000 volt, s -t minden egyes lefutás után 0,6-szeresére csökkentettük, így [0.3..0.00001] induló konvergencia-faktor tartomány esetén vizsgáltuk a négyzetes eltérés mértékét (MSE) az eredeti, és az elmosott képek között. Túl nagy induló esetén a sorozat divergens lesz, túl kicsi induló faktor esetén pedig nagyon lassan konvergál. Az ábrákról leolvasható, hogy létezik optimális induló-konvergencia faktor, és megállapítható -ra nézve az a tartomány, amely konvergenciát biztosít. Ezen tartományban a sorozat konvergenciája optimális, viszont N=400–as iteráció szám felett az MSE értéke számunkra megfelelő érték alatt marad. Ez esetben viszont létezik minden kép esetén egy [,N] számpár, amely mind az algoritmus lefutási-idejében, mind az iteráció pontosságában optimális. Ezen optimum a 8.22 . és a 8.23. ábrákon található kétváltozós függvények minimum helyének kiszámításával meghatározható. A két ábra összehasonlításával elmondható, hogy -nak biztosan optimuma van [0,1..0,01] értékek között. A 8.23 . ábrán az optimum =0,18, N=15. Azonban ezen induló konvergencia-faktor esetén a sorozat divergens, de N=15 –nél a legjobb közelítést adja.
{8.22. ábra. optimális = 0,00504 optimális N=658 (a harmadik tengelynél =
szerepel) }
{8.23. ábra. optimális =0,18 (a harmadik tengelynél =
optimális N=15 szerepel)}
8.8.3.Wiener-szűrés Ezen szűrés előnye, hogy átmenet az inverz-szűrés, és a zajelnyomás között. Az általános inverz-szűrések nagyon zajérzékenyek, így a zaj felerősödhet a szűrés során. A priori ismeretek alapján a szűrő számításához szükség van az eredeti képre f(n 1,n 2) deltaimpulzusfüggvény válaszfüggvényére b(n 1,n 2), illetve a zajra (n 1,n 2). Ezek alapján általánosan a Wiener szűrő megadható:
, ,ahol B*( 1, 2) – a Gauss-filter (PSF) Fourier transzformáltjának komplex konjugáltja, [1] F – az eredeti kép transzformáltja, a zaj transzformáltja. Ebből F( 1, 2)-vel osztással előáll:
A kifejezés a jel-zajviszony. Ha az eredeti jel nagyon erős a zajhoz képest, akkor a hányados nullához tart, és a Wiener-filter előáll a PSF inverz függvényeként, vagyis:
Ha viszont a zaj nagyon erős a jelhez képest, akkor a hányados végtelenhez tart, és
Additív fehér zaj esetén a kép módosítása nélkül a összefüggés a következő képen alakul:
, ahol
jelenti a variancia-változót.
8.8.4. Teljesítményspektrum-ekvalizáció (PSE) A Wiener-szűrő módosított változata, amely számol :
komplex transzformált amplitúdójával
Egyszerűsíthető a fenti összefüggés, fehér-zajt feltételezve a spektruma konstanssal közelíthető:
(a)
(b)
(c)
(d)
(e)
{8.24. ábra. Eredeti kép (a), és közepes fehér-zajjal telített és Gauss-PSF – el konvolvált képe (b). A többi ábrán Wiener-filterrel (c), PSE szűréssel (d), illetve PSE szűrés a fehér-zaj figyelembevételével (e).}
(a)
(b)
(c)
(d)
(e)
{8.25. ábra. Eredeti kép (a), és viszonylag nagy fehér-zajjal telített és Gauss-PSF – el konvolvált képe (b). A többi ábrán Wiener-filterrel (c), PSE szűréssel (d), illetve PSE szűrés a fehér-zaj figyelembevételével (e).}
A 8.24 -es illetve 8.25-öss ábrasorozatokon látható Wiener-szűréshez kapcsolódó algoritmusok eredményének összehasonlítása. Látható, általában az összes szűrés megszünteti az elmosást, de a zaj mértékében különböznek. A (d) és (e) ábrákon jól látszik, a fehér zaj spektrumának 1( 1, 2) frekvenciafüggvénnyel közelítése nagyon jó közelítést ad, a két kép nem különbözik nagyon egymástól. Kissé módosított Wiener-szűrési eljárás járásnál a zaj spektrumának -val szorzása jobb zajszűrést eredményez.
