Zpracování obrazu Studijní text k předmětu UF/0D201 - Snímání obrazu s využitím programovatelných logických polí a multiprocesorových systémů RNDr. Hynek Sekanina, Ing. Jaroslav Zeman, BcA. Bc. Miroslav Zeman Slezská univerzita v Opavě Filozofickou-přírodovědecká fakulta v Opavě Ústav fyziky Snímání a úpravy obrazu Studijní text k předmětu UF/0D201 - Snímání obrazu s využitím programovatelných logických polí a multiprocesorových systémů RNDr. Hynek Sekanina, Ing. Jaroslav Zeman, BcA. Bc. Miroslav Zeman Ústav fyziky Filozofickou-přírodovědecká fakulta v Opavě Slezská univerzita v Opavě Bezručovo náměstí 13, Opava Tato inovace předmětu UF/0D201 - Snímání obrazu s využitím programovatelných logických polí a multiprocesorových systémů je spolufinancována Evropským sociálním fondem a Státním rozpočtem ČR, projekt č. CZ.1.07/2.2.00/28.0014, „Interdisciplinární vzdělávání v ICT s jazykovou kompetencí“. Anotace: Tato publikace je určena studentům, kteří mají zájem snímání a zpracování obrazu za účelem využíti obrazové informace v řídících systémech. Obsahem publikace je studijní text pro předmět „UF/0D201 -Snímání obrazu s využitím programovatelných logických polí a multiprocesorových systémů“. Text podává studentům základní informace z oblasti snímání obrazu a jeho digitálním zpracování, tak aby výstup zpracování obrazu mohl být využit v řídícím či rozhodovacím systému. V studijním textu jsou uvedeny teoretické základy pro zpracování obrazu, tak aby bylo možné navrhnout program či HW komponentu na bázi FPGA, který s obrazem provede všechny potřebné manipulace, přičemž jeho výstupem bude datový údaj použitelný pro účely řízení a rozhodování. Obsah 1 Snímání obrazu.......................................................................................................................1 1.1 CCD snímače...................................................................................................................2 1.2 CMOS snímače................................................................................................................9 1.3 Praktické dopady snímacích prvků na zpracování signálů............................................11 2 Zpracování obrazového signálu............................................................................................12 2.1 Předzpracování..............................................................................................................13 2.2 Předzpracování obrazu..................................................................................................13 2.2.1 Geometrické úpravy obrazu...................................................................................13 2.2.2 Interpolace.............................................................................................................15 2.2.3 Nejbližší soused:....................................................................................................16 2.2.4 Bilineární interpolace:...........................................................................................16 2.2.5 Bikubická interpolace:...........................................................................................16 2.3 Bodové filtry..................................................................................................................17 2.3.1 Barevné modely.....................................................................................................18 2.3.2 Úpravy barevného podání......................................................................................20 2.3.3 Prahování...............................................................................................................21 2.4 Prostorové filtry.............................................................................................................21 2.4.1 Konvoluční filtry...................................................................................................22 2.4.2 Odstranění šumu....................................................................................................23 2.4.3 Filtry pro detekci hran...........................................................................................24 2.4.4 Cannyho detektor hran...........................................................................................26 2.4.5 Zostření obrazu......................................................................................................26 2.4.6 Reliéf.....................................................................................................................26 2.4.7 Hledání přímky......................................................................................................26 2.5 Nelineární filtry.............................................................................................................27 2.6 Rekurzivní filtry............................................................................................................27 2.7 Statistické filtry.............................................................................................................29 2.8 Houghova transformace................................................................................................31 2.9 Filtry využívající FT, WT.............................................................................................32 2.10 Radonova transformace...............................................................................................42 2.11 Filtry využívající matematickou morfologii................................................................46 2.11.1 Hit or Miss filtry..................................................................................................47 i 2.11.2 Kostra segmentu..................................................................................................48 2.11.3 Obrys segmentu...................................................................................................50 2.11.4 Vyplnění ohraničené plochy................................................................................50 2.11.5 Rozšiřování objektů.............................................................................................50 3 Detekce příznaků...................................................................................................................51 3.1 Segmentace....................................................................................................................51 3.1.1 Region growing.....................................................................................................51 3.1.2 Štěpení a spojování oblastí....................................................................................51 3.1.3 Popis segmentů......................................................................................................52 3.1.4 Moment..................................................................................................................53 3.2 Klasifikace.....................................................................................................................54 4 Zpětná stereo-projekce..........................................................................................................56 5 Pár slov na závěr...................................................................................................................59 ii 1 Snímání obrazu 1 Snímání obrazu RYCHLÝ NÁHLED KAPITOLY V této kapitole je ozřejmeno jak je snímán obraz pomocí prvků CCD a CMOS. CÍLE KAPITOLY Po prostudování této kapitoly porozumíme: ● konstrukčnímu uspořádání snímačů, ● technickým rozdílům mezi snímači, které se promítají do zpracování obrazu. KLÍČOVÁ SLOVA KAPITOLY CCD, CMOS, dělení CCD snímačů FT, IT, rastrové filtry, barevné modely Nejběžnějšími komerčně dostupnými snímači pro snímání obrazu jsou technologie na bázi CCD a CMOS technologie. Obě technologie využívají fotoelektrický jev v polovodičích a polovodičových strukturách typu PN, jen různým způsobem, viz dále. Vlastní polovodiče (Si, Ge) jsou upravovány přidáním příměsí (např. P, In) na nevlastní polovodiče typu P a N a pomocí nich jsou vytvářeny struktury zvané PN přechody. Fotony, které nesou obrazovou informaci snímané scény, vždy nesou i energii, a potom, co dopadnou do polovodiče v případě zániku předávají svoji energii atomům v polovodiči. Atom, který absorbuje energii fotonu, při splnění definovaných podmínek, ze svého elektronového obalu uvolní elektron (tento elektron označujeme jako volný a může se volně pohybovat v polovodiči). Volné elektrony pak ovlivňují fyzikální vlastnosti polovodiče, např. vodivost polovodiče1 . V případě struktur PN pak volné elektrony ovlivňují chování této struktury, nejčastěji vodivost. 1 V PN přechodu diody, podle toho v jakém režimu dioda pracuje, buď volné elektrony ovlivňují vodivost a dioda pracuje jako senzor, v tomto případě je na diodu přivedeno závěrné napětí, nebo jsou elektrony odváděny mimo PN přechod, pak dioda pracuje jako fotočlánek. 1 Snímání a úpravy obrazu V zásadě finální snímače CCD a CMOS mohou poskytovat informace o snímaném obraze jak v analogové formě, ale v současnosti zpravidla již v digitální formě, avšak vždy pro součinnost vyžadují vnější řídící obvod, který generuje potřebné řídící signály pro snímač, jde zejména o signály řídící chod pohybu náboje v CCD snímačích a chod A/D převodníků a v neposlední řadě i chod elektronických závěrek CCD snímačů, v případě CMOS snímačů pak chod časování čtení z jednotlivých prvků snímače (řádky, sloupce) včetně nulování a chod A/D převodníku. Samotná zpracování obrazu z hlediska barevného modelu a jeho korekcí včetně komprese již zpravidla probíhá mimo vlastní snímač zpravidla s využitím proprietárních obvodů2 v případě komerčních produktů - fotoaparáty, TV kamery. Existuje i celá řada snímačů, které používají i fotoelektrický jev bez použití polovodičů, např. vidikony, optokony, optické násobiče, ty však jsou používány jen v úzkém specifickém oborovém rozsahu (např. CT) a proto zde nebude uváděná jejich konstrukce. 1.1 CCD snímače V CCD (Charge-Coupled Device) technologii je určující pro zjišťování množství zachycených fotonů ve snímači množství volných elektronů, které tyto fotony uvolní, a toto volné množství elektronů bude prostřednictvím svého náboje na dané ploše snímače určovat intenzitu dopadajícího světla, tzn. náboj bude úměrný intenzitě dopadajícího světla. Svobodnému přemísťování volných elektronů v CCD snímači brání důmyslný systém elektrod a PN přechodů včetně vrstev izolantů mezi těmito strukturami - viz Obr. 1. (výrobní proces zahrnuje řádově 300 operací) ale i správné časování a velikosti napětí přiváděných na jednotlivé elektrody - viz Obr. 2. a Obr. 3. Elektrody (zpravidla z napařeného hliníku nebo 2 Z hlediska výpočetního se jedná zpravidla o upravené procesory, ve kterých je kladen důraz na rychlost výpočtů v oblasti zpracování obrazu, tzn. jsou v něm zpravidla přítomny různé urychlovací komponenty na bázi DES. 2 Obr. 1. Řez strukturou CCD prvku P++ N+ N+ P2 P2 N+ P+ N+ P++ N P+ čočka optická vrstva vyrovnávací vrstva pasivační vrstva elektrodyAl polySi P1 izolace oddělovacíkanál paměťovýregistr čtecíkanál snímač Si otvor 1 Snímání obrazu polykrystalického křemíku - ten se chová jako vodič), jsou na obou stranách snímače (spodní strana je zpravidla celistvá, horní strana je tvořena několika mřížkami). Celkové uspořádání snímače včetně elektronických obvodů řídících chod snímače je na Obr. 5. Obr. 2. Akumulace náboje v CCD prvku a řídící napětí pro pohyb náboje 3 Obr. 3. Příklad 3 fázového řídícího napětí pro pohyb náboje v CCD prvku Snímání a úpravy obrazu Obr. 4. Způsob pohybu náboje na ploše CCD FF čipu CCD snímač pracuje ve třech fázích: 1. fáze mazání – v této fázi je veškerý volný náboj ze snímače odstraněn, to je zajištěno pomocnou elektrodou, která odvede veškeré volné elektrony ze snímače, 2. fáze expozice – v této době necháme na snímač dopadat světlo a akumulujeme volné elektrony ve snímači - náboj, v této fází bývá na jednu z vodivých mřížek přivedeno kladné napětí, přičemž toto napětí způsobí, že záporný náboj elektronů se bude shromažďovat právě pod touto mřížkou, 4 Obr. 5. Celkové uspořádání elektroniky CCD 1 Snímání obrazu 3. fáze snímání – v této fázi postupně na jednotlivé vodivé mřížky přivádíme kladné vícefázové napětí3 _ viz Obr. 2. a Obr. 3, přičemž toto fázování zabezpečí, že volný náboj z plochy snímače budeme postupně posouvat v daném směru, a to ke kraji snímače, kde budeme toto množství volného náboje snímat snímací elektrodou. Ve fázích 1 a 3 je nutno zamezit dopadu světla na snímač, jinak by byl obraz degradován. V kamerách, kde je používána mechanická závěrka, se používají čipy CCD FF – full frame FT - viz 4., zde je snímán obraz z celé plochy čipu (čipy mají vyšší citlivost). Ve spotřební elektronice jsou však mechanické závěrky nahrazeny elektronickými závěrkami, které jsou realizovány přímo na snímači CCD v podobě oddělených oblastí pro snímání (SA – storage area) a expozici (označené IA – image area) označujeme je jako IT - Obr. 6. Proto v konstrukci CCD snímače rozlišujeme snímače na FT nebo IT (frame transfer či interline transfer). V IT ve fázi 2 (expozice) se obraz exponuje v IA, pak je exponovaný obraz rychle přenesen do SA oblasti, odkud je ve fázi 3 (snímání) postupně snímán. S FT a IT snímáním i tak souvisí, jak je načítán náboj z SA či IA, kdy může být načítán jako půl snímku, celé snímky, nebo jako součet z více snímacích prvků – binning - viz Obr. 7., odtud nesou čipy označení jako interlace, grogresive, frame read. 3 Průběh napětí je přesně definován a může se jednat o 2, 3 a 4 fázové posouvání. 5 Obr. 6. Uspořádání a pohyb náboje na CCD IT Snímání a úpravy obrazu Snímací, závěrkové a resetovací elektrody na ploše snímače vytvářejí samostatné oddělené oblasti – jednotlivé pixely, kterými je snímaný obraz v digitální podobě reprezentován. Způsob posunu náboje ve snímači, počet míst, kde se náboj snímá, určuje max. rychlost snímání obrazu ze snímače, resp. kolik snímků za jednotku času ze snímače jsme schopni přenést, proto výrobci snímačů využívají různých technik, aby dobu snímání zkrátili, zpravidla přidávají na počtu snímačů nábojů, tzn. snímač je rozdělen na regiony a každý region má svoji řídící a převodní část. Mřížky, které se nachází na povrchu polovodičové destičky CCD snímače, jsou zpravidla nepropustné pro světlo (zpravidla se jedná o napařený hliník), takže citlivost snímače a množství náboje, který snímáme, je mnohonásobně menší, než by bylo možno získat z čisté plochy snímače, proto výrobci nad těmito mřížkami mohou ve výrobním procesu realizovat miniaturní čočky Obr. 8., které mají za úkol zvýšit efektivitu zachycování fotonů. Jako další alternativou zvýšení citlivosti snímačů se využívá princip průhledných elektrod či velmi tenkých vrstev, nebo je možno světlo přivádět přes zadní plošnou elektrodu snímače. 6 Obr. 7: Pohyb náboje v případě bindigu na CCD čipu 1 Snímání obrazu V případě barevného snímání obrazu, je nutno zajistit oddělené zpracování barev obrazu, přičemž se používá RGB nebo CMY barevný model. Oddělené zpracování barev se realizuje: 1. 3 samostatnými snímači - viz Obr. 9., kdy každý snímač snímá danou barvu odděleně (zpravidla RGB model), tzn. světlo přicházející z objektivu je nutno rozdělit na 3 samostatné barevné složky – toto řešení je dražší z důvodu počtu snímačů, ale může poskytovat vyšší citlivost i vyšší rozlišení, 2. rastrovými filtry přímo realizovanými na ploše snímače - viz Obr. 12. vycházejících z barevných modelů RGB či CYK - viz Obr. 10., kdy výsledný pixel obrazu je tvořen několika samostatnými snímacími prvky, což však se promítá do složitosti výroby samotného snímače, ale i max. dosažitelného rozlišení i celkové citlivosti snímače. 3. jediným snímačem, ale s výměnnými barevnými filtry, které se vřazují do optické cesty mezi snímač a objektiv (toto řešení používají astronomické pozorovací přístroje), přístroj disponuje i vyšší citlivostí než dříve uvedené varianty. 7 Obr. 9. Tříčipové uspořádání kamery pro barevné snímání scény Obr. 8. Realizace čoček nad snímacím prvkem CCD. Snímání a úpravy obrazu V případě použití rastrových filtrů pro vlastní barevnou interpretaci se zpravidla používá pro rekonstrukci barevné informace v daném bodě obrazu Bayerův filtr - viz Obr. 11. Tento filtr vychází z fyziologie lidského oka a jeho maximální citlivost na žluto-zelenou barvu. Tato vlastnost se pak promítá i do fyzické realizace rastrových filtrů tím, že jeden výsledný pixel obrazu je snímán dvěma snímači pro zelenou barvu – mód RGBG - viz Obr. 12. Z hlediska propustnosti filtrů a dosažení max. citlivosti snímače by bylo lépe použít model CMY, avšak výroba fialového filtru je extrémně složitá, proto výrobci používají smíšený model CMYG Obr. 12. V současnosti výrobci snímačů různými technickými úpravami se snaží eliminovat 8 Obr. 10. Barevné modely RGB a CYK. Obr. 13: Uspořádání snímacích prvků na CCD Obr. 12: Příklady barevných rastrů na CCD čipu pro barevné podání obrazu Obr. 11. Realizace Bayerova filtru 1 Snímání obrazu 1.2 CMOS snímače V CMOS snímačích však volné elektrony neshromažďujeme jako v CCD, ale jsou využity pro ovlivňování vodivosti PN přechodu - viz Chyba: zdroj odkazu nenalezen, na který dopadá světlo, měříme přímo tuto vodivost. CMOS snímač se skládá - viz Obr. 15: z fotocitlivé PN či PIN diody, z pomocného obvodu, který resetuje zbytkový náboj snímací diody, z adresovatelného čtecího obvodu, který může být pasivní či aktivní (v aktivním je použit předzesilovač a korektor šumu snímací diody). 9 Obr. 14. Snímací prvek CMOS snímače Snímání a úpravy obrazu Celkové uspořádání snímače je pak zachyceno na Obr. 16. 10 Obr. 16. Celkové uspořádání CMOS snímače s elektronikou Obr. 15: Celkové uspořádání snímacího prvku CMOS snímače s čočkou 1 Snímání obrazu Výhodou CMOS snímačů je oproti CCD: nižší výrobní náklady, jednodušší způsob řízení, adresovatelné čtení kterékoliv snímací diody, vyšší rychlost čtení snímků, možnost korekce šumu již v obvodu snímače, odolnost proti bloomingu. Výhody CCD oproti CMOS: akumulace náboje, tzn. vyšší citlivost v případě velmi dlouhých časů expozice, lineární citlivost oproti logaritmické, nižší šum. 1.3 Praktické dopady snímacích prvků na zpracování signálů Z hlediska reálné konstrukce obrazových snímačů je nutno si uvědomit, že při snímání reálného obrazu scény dochází ke ztrátě rozlišení: v ploše - je daná snímacím rastrem, velikostí snímacích prvků rastru a jejich počtem – rozlišením, dále poměrem aktivní části snímače k ostatním neaktivním plochám4 , v barvě či úrovni - je dána barevnou hloubkou tj. kvantizací úrovně dané barvy v daném obrazovém bodu, tzn. rozsahem hodnot, které můžeme obdržet, v čase - je dáno způsobem, jak je snímán pohyblivý obraz – prokládaně či neprokládaně, ale i počtem snímků za jednotku času. 4 Plošná ztráta zobrazení je největším problémem v medicíně v případě CT, ultrazvukového vyšetření i jiných moderních přístrojů. 11 Snímání a úpravy obrazu Dále dochází k: Ztrátě barevného podání – na ní se podílí konstrukce snímače, optická cesta mezi snímaným obrazem a snímačem, světelné podmínky při snímání obrazu. Rovněž záleží na typu zvoleného barevného modelu pro záznam obrazu a jeho výpočtu z hodnot získaných z reálného snímače. Mnoho výrobců ukládá ve svých zařízeních surový obraz přímo, tak jak byl získán ze snímače, pod označením RAW, pak pro zobrazení obrazu je nutno tato surová data přepočítat do barevného modelu zobrazovače. Přidání šumu k vlastní obrazové informaci – šum je vedlejším produktem každé elektronické součástky, neboť přítomnost volných nosičů nábojů v polovodičích i vodičích souvisí se stochastickým náhodným procesem jejich uvolňování, pohlcování ale i pohybu. Největším zdrojem je samotný termický šum, který lze eliminovat jen jediným způsobem, a to provozem součástek při snížených teplotách. Rozmazání pohybujícího se obrazu vlivem délky expozice5 . Ke všem faktorům je pak nutno přihlížet při dalším zpracování obrazu tak, aby negativní vliv těchto faktorů byl maximálně potlačen. 5 Při některých způsobech snímání lze snímací zařízení synchronizovat s pohybem obrazu, pak lze rozmazání obrazu částečně eliminovat. Existuje i matematický způsob zpětné korekce rozmazaného obrazu vlivem pohybu pomocí FT. 12 2 Zpracování obrazového signálu 2 Zpracování obrazového signálu RYCHLÝ NÁHLED KAPITOLY V této kapitole je ozřejmeny všechny způsoby digitálního zpracování obrazu. CÍLE KAPITOLY Po prostudování této kapitoly porozumíme: - geometrickým transformacím, - bodovým filtracím, - prostorovým filtracím. Dále jsou v této kapitole probrány geometrické transformace, barevné modely a interpolace. KLÍČOVÁ SLOVA KAPITOLY bodová filtrace, prostorová filtrace, konvoluce, FT, WT, interpolace Zpracování digitálního obrazu můžeme rozdělit na: - Předzpracování, - Detekce objektů nebo příznaků v obraze, - Klasifikace objektů či příznaků a reprezentace výsledků. Tento učební text se nezabývá komprimací a dekomprimací obrazu, neboť v případě rozpoznávání či jiném finálním užití dat obrazu je bezpředmětné pracovat během výpočtu s komprimovaným obrazem. Navíc ztrátové komprimace např. JPEG vedou ke ztrátě informací uvnitř obrazu a mohou způsobit nefunkčnost celého systému. 13 Snímání a úpravy obrazu 2.1 Předzpracování Zahrnuje: geometrické transformace - odstranění chyb snímačů a optických soustav, bodové filtrace – které jsou představovány úpravami kontrastu, jasu, gama korekce, odstranění vinětace, ekvalizace (logaritmická či jiná) a prahování, prostorové filtrace – které jsou realizovány pomocí konvolučních masek (lze zajistit filtraci šumu, vyhlazování obrazu, detekci hran) nebo pomocí nelineárních, rekurzivních, statistických filtrů, filtrů využívajících FT a WT či jiných matematických nástrojů, např. Radonova či Houghova transformace či morfologických operací, prostorová transformace - přechod mezi různými matematickými modely scény, např. přechod z 2D do 3D při stereoskopickém snímání scény, nebo pořízením snímků z jiných míst při známém souřadnicovém umístění kamery, či doplnění informací o vzdálenosti jednotlivých objektů k snímanému obrazu (systémy označované jako LIDAR). 2.2 Předzpracování obrazu 2.2.1 Geometrické úpravy obrazu Z hlediska geometrických úprav, se jedná o: posun, zvětšení/zmenšení, rotaci, zkosení, distorzi – válcovou, soudečkovou, kulovou, panoramatickou náklon. Všechny operace jsou snadno implementovatelné, kdy pro každou hodnotu jasu v souřadnicovém sytému původního obrazu vypočteme pomocí transformačních funkcí novou hodnotu souřadnice v novém obraze. Transformace mohou být buď lineární, tzn. geometrické 14 2 Zpracování obrazového signálu prvky v originálním a změněném obraze nemění svůj tvar, tzn. přímka zůstává přímkou, nebo nelineární (často se takováto transformace označuje jako warping či morphing). Některé nelineární transformace např. nemusí být realizovány přímo, ale mohou být složeny z lineárních či jednodušších nelineárních, kdy obraz je rozdělen na více segmentů a transformace probíhá v každém segmentu samostatně. Obecně transformaci zapíšeme: kde: x, y – původní souřadnice, x', y' – nová hodnota souřadnic, f, g – obecná transformační funkce, může být definována pro obě souřadnice, či jen jednu z nich, příklad viz tabulka níže. Některé z lineárních transformací jsou uvedeny v tabulce níže, výhodou těchto transformací je, jdou-li po sobě, mohou být realizovány v jediném kroku, často se k tomu používá maticový tvar výpočtu a systém homogenních souřadnic, přičemž se určí hodnoty jednotlivých koeficientů transformační matice tím, že transformační matice prostě vynásobíme6 . 6 Pozor, ale neplatí zde princip komutativní, tzn. závisí na pořadí 15 ∣ x' y' 1 ∣= ∣ z11 ' z12 tx z21 z22 t y 0 0 1∣= ∣ x y 1∣ x ' = f ( x , y) y' =g(x , y) Snímání a úpravy obrazu Transformace Výpočet translace x '=a+x y'=b+y a,b - koeficienty posunu zoom x '=a⋅x y'=b⋅y a,b - koeficienty zvětšení >1, zmenšeni <1 rotace okolo počátku7 x '=xcos(φ )−y sin(φ) y' =xsin(φ )+y cos(φ ) φ - úhel natočení zrcadlení V : x' =w−x , y '=y H : x'=x , y'=h− y D : x' =y , y' =x w, h - šířka a výška obrázku zkosení V : x' =a+x+by , y' =y H : x'=x , y'=a+y+bx a,b – koeficienty zkosení Při nelineárních transformacích nová souřadnice může být např. vypočtena pomocí polynomu n-tého stupně, kde polynomem aproximujeme požadovaný výsledek: 2.2.2 Interpolace Poněvadž obraz je zpravidla uložen v čtvercové pravoúhlé síti8 , takže jednotlivé body leží vždy na celočíselných násobcích souřadnic (viz Obr. 17. černě označené body se souřadnicemi [0,0], [0,1], [1,0], [1,1]). Při transformacích je třeba řešit, jaký jas má pro danou barevnou složku bod nabýt, nemá-li nová souřadnice hodnotu celého čísla (viz Obr. 17. červeně označený bod se souřadnicemi [x,y]). Proto při určení jasu přistupujeme k interpolaci, která má zohlednit umístění bodu [x,y] mezi body ležící na celočíselných souřadnicích v pravoúhlé síti. Níže jsou uvedeny některé z metod, jak přepočítat jas daného bodu (pro každou z barevných složek samostatně)9 : 7 Požadujeme-li rotaci okolo jiného bodu než počátku, provedeme nejdříve translaci, pak rotaci v počátku, a zpět translaci vůči bodu rotace. 8 Existují i hexagonální interpretace a ukládání obrazových informací. 9 Postup je obrácený, v novém obraze zjišťujeme pro daný bod x', y', kde bude ležet ve starém obraze a ze znalosti hodnot jasu původního obrazu odvodíme hodnotu v transformovaném obrazu. 16 Obr. 17. Interpretace bodů v interpolaci 0,1 1,1 0,0 1,0 x,y x y x '=x+∑ r=0 m ∑ k=0 m ark xr yk y' =y+∑ r=0 m ∑ k =0 m brk x r y k 2 Zpracování obrazového signálu Nejbližší soused kde: round je zaokrouhlovací funkce. Bilineární interpolace: V této interpolaci vycházíme z hodnot 4 okolních bodů, viz Obr. 17. Základní tvar rovnice: kde: x, y - jsou souřadnice bodu uvnitř mřížky x, y = <0, 1> fi,j - jsou hodnoty jasu 4 bodů tvořící rohy mřížky fx,y - je vypočítaná hodnota jasu. Nebo taky pomocí maticového vyjádření: Souřadnice bodu 0,0 také získáme odstraněním desetinné části čísla, x, y je pak desetinná část čísla. Bikubická interpolace: V této interpolaci vycházíme z hodnot jasu 16 okolních bodů v rastru 4x4. Základní rovnice: kde ai,j jsou konstanty vypočítané na základě interpolace. Výpočet lze realizovat i na základě maticové operace: f x , y=∣1 y y2 y3 ∣A ∣ f −1,−1 f 0,−1 f 1,−1 f 2,−1 f −1,0 f 0,0 f 1,0 f 2,0 f −1,1 f 0,1 f 1,1 f 2,1 f −1,2 f 0,2 f 1,2 f 2,2 ∣AT ∣ 1 x x 2 x 3∣ 1331 0363 1632 0060 6 1 A 17 f x , y=(1−x)(1−y) f 0,0+x(1− y) f 1,0+y(1−x) f 0,1+x y f 1,1 f x , y= f round ( x), roudn( y) f x , y=∣1−x x∣ ∣f 0,0 f 0,1 f 1,0 f 1,1 ∣∣1−y y ∣ f x , y=∑ i=0 3 ∑ j=0 3 ai, j xi y j Snímání a úpravy obrazu V odborné literatuře najdeme i bikubickou interpolaci definovanou takto: f x , y=∣g1x g2x g3x g4x∣ ∣ f 0,0 f 0,1 f 0,0 y f 0,1 y f 1,0 f 1,1 f 1,0 y f 1,1 y f 0,0 x f 0,1 x 0 0 f 1,0 x f 1,1 x 0 0 ∣∣ g1y g2y g3y g4y ∣g1q=1−3q 2 +2q 3 g2q=3q 2 −2q 3 g3q=q−2q 2 +q 3 g4q =−q 2 +q 3 q=x ; y f p ,q x = f p+1,q− f p−1,q 2 f p, q y = f p ,q+1− f p ,q−1 2 2.3 Bodové filtry Tyto filtry nevyužívají hodnot vedlejších obrazových bodů, ale jen hodnotu daného bodu obrazu. Poněvadž obraz může nést barevnou informaci nebo jen černo/bílou v různé škále šedi, mohou bodové filtrace pracovat jak s jednotlivými barevnými složkami, tak s celkem, přičemž je nutné brát na zřetel, jak se pohlíží na barevný obraz jako na celek. Dále je nutné mít na zřeteli, že barevný obraz může být uložen v různém barevném modelu, přičemž v každém barevném modelu může konkrétní úprava obrazu poskytovat lepších výsledků než v jiném barevném modelu. 18 Obr. 18. Příklady interpolace (Gimp - nearest, linear, cubic, sinc, původní obraz 16x16 px se 4 barevnými čtverci zvětšený na 100x100 px) 2 Zpracování obrazového signálu 2.3.1 Barevné modely Informace o barvě jednoho bodu v digitálním obraze je uložena zpravidla v některém z těchto barevných modelů10 : RGB či RGBA – (Red Green Blue, Alpha) - model používá aditivní míchání barev a je přirozený např. pro zobrazovací systémy CRT, LED, LCD, ale i mnoho snímacích zařízení, např. kamery, fotoaparáty, skenery11 . V mnoha programových nástrojích je tento model rozšířen o kanál Alpha, což je kanál udávající průhlednost. CMY či CMYK – (Cyan Magenta Ylow, Black) - model používá subtraktivní míchání barev, tento model je přirozený pro tiskárny, CMYK model je jeden z modelů, ve kterém nelze konkrétní barvu z jiného modelu stanovit jednoznačně, HSV či HSB (Hue Saturation Value, Balance) – model se blíží lidskému vnímání barev, HSL (Hue Saturation Lightness) – podobný HSV, ale má odstraněny některé nedostatky HSV, YUV (Luminance Chroma) – model používaný v přenosových TV systémech, např. PAL, vycházející z citlivosti oka. Model vyniká tím, že hlavní složka Y nese převážnou část obrazové informace, zato složky UV jsou v poměru 4:1:1 nebo 4:2:2 vůči složce Y, tzn. nesou menší část informace vůči jasové složce. Vlastnost tohoto modelu je použita v komprimovaném standartu JPEG, MPEG, LAB – matematický model, ve kterém se na ose z vynáší jas, osa nese označení jako "L" (bílá, šedá, černá), na x ose - označení "a" se pracuje s barvou zelenou -a červenou +a, na y ose - označení "b" se pracuje s barvou žlutou +b a modrou -b. Tento model se rovněž přibližuje citlivosti lidského oka. 10 Abstraktní matematický model, který se snaží číselně popsat barvu v digitálním obraze, z hlediska fyzikálního jsme sice schopni barevný prostor změřit absolutně, a to ve fyzikálních jednotkách, ale prakticky jde jen o jisté přiblížení. Barva může mít jen konkrétní jednu vlnovou délku, nebo může být složena z více vlnových délek, nebo může být i směsicí spojitých spekter. Paradoxně v mnohých modelech i při max. počtu bitů, které máme k dispozici, nejsme schopni uložit barevnou informaci, kterou by bylo zdravé oko schopno rozlišit, přesto, že oko rozlišuje cca jen 10 mil. barev. 11 Viz snímací prvky, používá se modifikovaný model sRGB. 19 Snímání a úpravy obrazu Mezi všemi modely existuje matematický přepis12 , který popisuje převod mezi barevnými modely pro normalizované hodnoty, aby v každém modelu byla konkrétní barva subjektivně13 vnímána totožně jak na zobrazovacím14 , tak na snímacím zařízení. Touto problematikou se samostatně zabývá barevná teorie, která zavádí řadu pojmů, např. barevný prostor, barevný režim, teplota barev apod. Nutno si však uvědomit, že převod mezi modely si vždy vyžádá jistou barevnou ztrátu, neboť se často zaokrouhluje, a to finálně na celá čísla. Jak již bylo uvedeno, v konstrukci snímačů se můžeme setkat s tím, že obraz nemusí odpovídat žádnému z uvedených modelů, ale je uložen v surovém RAW tvaru tak, jak byl získán přímo ze snímače. Pak je nutno disponovat přepočítacími koeficienty potřebnými pro přepočet do daného modelu a soustavou přepočtových rovnic, které zpravidla uvádí přímo výrobce snímacího prvku, nebo jsou rovnice stanoveny experimentálně. Samotnou otázkou je, jak v daném modelu ukládat hodnotu dané barevné složky, lze použít procentuální vyjádření 0 až 100% nebo vyjádření v poměru 0 až 1 (používá se pak reálné číslo), ale toto procentuální či číselné vyjádření 0 až 1 nic neříká o barevné hloubce – barevném režimu či gamutu. Neboli jinak - kolik bitů je použito pro úschovu barevné informace v dané složce daného modelu, a může to být od 4 až 32 bitů na jednu složku či 16 až 96 bitů na všechny složky dohromady, přičemž od počtu bitů se odvíjí, kolik barev je schopen model pojmout, např. běžně pro RGB model se používá 24 bitová barevná hloubka, tj. 8 bitů na každou barevnou složku, kdy každá ze složek může nabýt hodnot 0-255, tzn. systém může vytvořit celkem 224 různých barev. V případě digitálních úprav obrazů pro další rozpoznávání či jiné užití však nemusí být žádoucí dodržovat standardizaci v modelech, ale bývají často používány převodní nástroje tak, aby bylo možné v obraze lépe segmentovat jeho jednotlivé části, tzn. např. před vlastním prahováním je vytvořen jen černobílý obraz ve stupních šedi, přičemž můžeme některou z barevných složek zcela potlačit nebo rozlišit v obraze segmenty, které by obdržely stejnou úroveň jasu v daném modelu. Přepočet do škály šedi - viz jednoduchý vzorec níže. Výpočet 12 Z důvodů počtu modelů nejsou zde uvedeny matematické přepisy pro přepočet mezi modely, lze je snadno vyhledat v Internetu. 13 Subjektivní vnímání zde zohledňuje citlivost lidského oka na jednotlivé vlnové délky světla. 14 Zobrazovací zařízení nemusí být jen monitor, ale i tiskárna. Snímací zařízení nemusí být jen fotoaparát, ale i videokamera a skener. 20 2 Zpracování obrazového signálu může zahrnovat celou škálu převodních funkcí f využívající např.: log, sin, tang, vč. aplikace fuzzy logiky. Kde: F , f1,2,3 - jsou obecné funkce jedné až 3 proměnných, g - hodnota šedi15 , RGB - hodnota složek RGB modelu. 2.3.2 Úpravy barevného podání Pro úpravy barvených složek modelu obrazu lze využít obecnou rovnici: f x , y ' =g ( f x , y+ε) λ kde: f'x,y - nová hodnota složky fx,y - původní hodnota složky ε - posun g - obecná lineární či nelineární funkce, bývá odvozena z histogramu λ - exponent. Úpravu můžeme realizovat na jednotlivé složky modelu či na celý model, nebo v případě, že model disponuje výpočtem jasu, tak jen na jasovou složku. Např. inverze složky se realizuje (pro normalizovanou hodnotu 0 až 1): f x , y ' =1− f x , y Pro úpravu složky se často používá Gama korekce16 , která je dána výrazem: f x , y ' =λ f x , y γ kde: γ a λ - jsou kladné reálné konstanty, průběh křivky viz Obr. 27 17 . Gama korekce avšak sama nemění hodnotu nejsvětlejší a nejtmavší části. 15 Nutno brát v potaz, s kolika bity pracujeme a zda používáme normalizovaných hodnot složek a počítáme normalizovanou hodnotu šedi, a to z důvodů podtečení či přetečení hodnoty. 16 Korekce souvisela s úpravou svítivosti pixelů na CRT monitorech a jejich principem fungování, přičemž svítivost závisí exponenciálně na napětí mřížky, i když CRT monitory ustupují, korekce se stále zachovává na straně kamer. 17 Normalizací se myslí, že hodnota λ je stanovena tak, aby výsledná hodnota nabyla vždy max. rozsahu. 21 g=F( f 1(RGB) , f 2(RGB) , f 3(RGB)) Snímání a úpravy obrazu Pro stanovení průběhu funkce g se s výhodou využívá statistické zpracování obrazu v podobě histogramu, tj. podíl počtu obrazových bodů s danou složkou v obraze k celkovému počtu obrazových bodů, kdy můžeme buď histogram vyrovnávat – tj. zajistit rovnoměrné rozložení, nebo zpracovávat jen část obrazové informace, tzn. g funkce může být jakákoliv parametrická funkce či polynom n-tého stupně a existují matematické nástroje, jak určit koeficienty polynomu z histogramu za účelem jeho vyrovnání. 2.3.3 Prahování Prahování převádí obraz zpravidla jen na binární - viz výraz níže - či omezený počet jasových hodnot. V tomto případě na základě např. histogramu či jiným parametrickým nástrojem se určí hodnota prahu/ů p, q18 . Prahovat lze i na libovolnou barevnou hloubku obrazu, pak je nutno stanovit odpovídající počet prahů. f x , y ' = {1 když f x , y
p∧ f x , yb∧b≤c)∨(c>b∧b≤a)∨(c≥b+2) → b=b+1
(a≤b−2)∨(a 0, je algoritmus
25
High, Low, Band pass – horní, dolní propusť, pásmová propusť nebo zádrž.
26
Záměrně zde neuvádím matematický aparát, užitím kterého byl algoritmus odvozen, neboť je velice dobře
zdokumentován v celé škále odborné literatury a není předmětem tohoto kurzu.
33
Obr. 30: Příklady FT
Obr. 31: Pásmový filtr pomocí FT a IFT
Snímání a úpravy obrazu
velice snadný, je též označován jako rychlá Fourierova transformace FFT, lze ho popsat
těmito kroky27
a probíhá dle Obr. 32.:
1. vytvoř vektor komplexních čísel28
o velikosti n, vstupní hodnoty ulož do reálné části
tohoto vektoru, imaginární část ℑ tohoto vektoru nastavíme na hodnotu 0,
2. prvky vstupního vektoru přeuspořádej tak, že nové pořadí prvku je dáno jeho inverzní
bitovou hodnotou jeho indexu (viz tabulka níže pro hodnotu n=8),
Původní
index
Nový
index
Dec. Bin. Dec. Bin.
0 000 0 000
1 001 4 100
2 010 2 010
3 011 6 110
4 100 1 001
5 101 5 101
6 110 3 011
7 111 7 111
přičemž výpočet se bude opírat o motýlkové schéma skládající se ze sekcí, v kterých
se provádí motýlkový výpočet,
3. nastav l = 1, a bod 4. opakuj m krát, kde n=2m
, l můžeme považovat za vzdálenost
mezi motýlky, a tento cyklus vytváří oddíly,
27
Záměrně zde uvádím nerekurzivní algoritmus, který je výrazně efektivnější než algoritmy odvozené z
matematických důkazů.
28
Budeme uvažovat, že číslování prvků vektoru začíná od 0.
34
2 Zpracování obrazového signálu
4. nastav k = l a zvětši hodnotu l = 2 × l a opakuj bod 5. pro: j = 0, 1, …, dokud j < k,
toto můžeme považovat za cyklus vytvářející sekce, kdy k můžeme považovat za
vzdálenost mezi křídly motýlka,
5. posunuj motýlka po i = j, j + 1, ..., n s krokem l a vypočti motýlek na pozici:po
ukončení cyklu z bodu 4., pokračuj v opakování bodu 4. dle počtu v bodu 3.
Algoritmus používá tzv. motýlkové
schéma - viz Obr. 32. po n=8, kde jsou
zobrazeny hodnoty, kterých nabývají
proměnné I1 a I2 a je i znázorněna BK
(bitová konverze). Algoritmus lze použít i
pro inverzní FFT, dále iFFT, postačuje
provést min. úpravy. V případě iFFT
postačuje prohodit sin a cos a zaměnit
znaménko rozdílu při výpočtu imaginární
části pomocného čísla C.
35
A=O [i ]
B=O[i+k]
f =2π j /n
Cℜ=Bℑ⋅sin( f )+Bℜ⋅cos( f )
Cℑ=Bℑ⋅cos( f )−Bℜ⋅sin ( f )
Bℜ=Aℜ−Cℜ
Bℑ=Aℑ−Cℑ
Aℜ=Aℜ+Cℜ
Aℑ=Aℑ+Cℑ
Obr. 32: Motýlkový algoritmus FFT pro n=8
X0
X1
X2
X3
X4
X5
X6
X7
O0
O1
O2
O3
O4
O5
O6
O7
k=1
l=2
k=2
l=4
k=4
l=8BK
0
0
0
0
0
0
2
0
2
2
1
3
0
+
- Operace ± Operace × ωk
Snímání a úpravy obrazu
Výsledný vektor komplexních čísel při přímé transformaci pak obsahuje jednotlivé
frekvenční složky s kmitočtem 0, Δ, 2Δ ,…, přičemž amplitudu a fázi získáme níže uvedeným
vzorcem:
kde f je kmitočet vzorkování.
V případě, že máme n vzorků a n není mocninou základu 2, aplikujeme FFT buď podle
publikovaných zdrojů, kdy např. n = a . b, na průběžné signály aplikujeme FFT pomocí
okénka29
, které vyhovuje definici FFT výše, přičemž opětovně existuje mnoho variant úpravy
okénkového algoritmu FFT (obdélníkové, Hannigovo, Hammigovo, Blackmanovo,
trojúhelníkové, Kairesovo okno) tak, aby byla potlačena nespojitost frekvenční obálky
transformace a zvětšen odstup signálu k šumu po transformaci. Okénko pak po vzorcích
posouváme.
Hodnoty funkcí cos a sin mohou být již předem vypočteny a uloženy ve vektoru, kdy v
algoritmu jen indexujeme správné prvky tohoto vektoru. Rovněž není potřeba používat
komplexní čísla, ale běžné vektory, kdy si uvědomíme, že na sudých prvcích budou ležet
reálné části čísel a na lichých jejich imaginární části.
Zde je část kódu v jazyku C, pro FFT i iFFT:
#define N 1024
int n = N; //počet vzorků
double x[N]; //zde vložit data pro FFT, v případě iFFT, reálná složka
double y[N]; //pro iFFT fáze
int dir = 1; //určuje FFT nebo iFFT, 1 pro přímou FFT
//určíme mocninu
int m = 1;
for(int s=2; s