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 jen pro přestavu o složitosti snímače, čočka a vše pod ní tvoří 1 pixel snímače 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. barevný 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 Domnívám se, že pro účely našeho předmětu nejsou v následujícím důležité žádné detaily, jde jen o to, abychom si uvědomili, že "surové" informace o obrazu získané přímo ze snímače, zdaleka nejsou přímo vhodné k tomu, abychom "vykreslili" hledaný obraz. Proto po sejmutí RAW obrazu dochází k náročnému počítačovému zpracování získaných digitálních hodnot (tj. čísel), což znamená, že nastupuje řada výpočtů, které můžeme členit jak je dále uvedeno. Jen pro představu si projděme, jaké typy výpočtů se provádějí. 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 FT a WT jsou velmi často používanými transformacemi obecně, proto jsem je zde zaškrtl. Podívejme se, co například umí s obrazem udělat. 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> 1; int j = i2; int md = n-1; for (int i=1; i <= i2; i++) { 29 V okénku využíváme již definovaný DFFT algoritmus a okénko postupně posouváme nad vzorky. 36 Δ= f /n Ai=√Aℜi 2 +Aℑi 2 φ=atan( Aℑi Aℜi ) 2 Zpracování obrazového signálu if (i < j) { int tx = x[i]; x[i] = x[j]; x[j] = tx; tx = y[i]; y[i] = y[j]; y[j] = tx; if (i2 > j) //zrcadlení bitů přes negaci { int nj = md-j; int ni = md-i; int tx = x[ni]; x[ni] = x[nj]; x[nj] = tx; tx = y[ni]; y[ni] = y[nj]; y[nj] = tx; } } int k = i2; while (k <= j) { j -= k; k >>= 1; } j += k; } //vlastní FFT double c1 = -1.0; //nahrazuje výpočet sin, cos double c2 = 0.0; //nahrazuje výpočet sin, cos int l = 1; for (int o=0;o> 1; x[k+s2] -= x[k]; x[k] += x[k+s2] / 2; } } void iwt(double *x, int n) { for (int s = n; s >=2 ; s >>= 1) for (int k = 0; k < n; k += s) { int s2 = s >> 1; x[k] -= x[k+s2] / 2; x[k+s2] += x[k]; } } 35 Nezapomeňme, jak je definováno počítání, a to od 1. Znak % je zbytek po dělení. 40 2 Zpracování obrazového signálu Poznámky ke kódu:  Hodnota n musí být n=2m , kde m>1.  Výsledek je vždy uložen v tomtéž vektoru.  Koeficienty jsou uloženy „na přeskáčku“, tzn. v pořadí dělení intervalu 2, tj. pro n=8: jx [0] 3 jx [1] 0 jx[2] 1 jx[3] 0 jx[4] 3 jx[5] 0 jx [6] 1 jx[7] 0 .  Tato transformace není zrovna ideální pro odstraňování šumu. V případě 2D WT a iWT opětovně postupujeme nejprve po řádcích a pak po sloupcích. Tak jako v FT, výsledek transformací je uložen po kvadrantech obdobně jako u FT. Samotná WT a iWT umí výrazně pomocí potlačit šum36 v obraze, ale lze provádět i morfologické analýzy obrazu, např. lze sledovat změnu zemského povrchu z dlouhodobého hlediska. WT našla v současnosti uplatnění jako nová metoda JPEG2000 komprimace obrazu, kdy WT nahradila FT (resp. její kosinovou verzi) a je označována jako fraktální komprese obrazu. FT a WT 2D transformace či konvoluce s jádrem odvozené z FT či WT v různém pořadí a při současné transformaci souřadnic mezi kartézskými a polárními mohou sloužit pro úpravu obrazu před vlastním rozpoznáváním či hledání shody se vzory. Např. polární transformace, FT, konvoluce s WT jádrem, iFT slouží jako nástroj pro úpravu obrazu před autentifikací osob pomocí tváře. Rovněž FT může sloužit pro určení posunu, otočení a zoom obrazu. Postup vychází z matematického aparátu FT, kdy použijeme FT na obrazy, z transformovaných obrazů určíme podíl, na který použijeme iFT, kdy ve výsledném obraze získáme max. hodnotu v místě, které udává posun. (Pro rotaci pracujeme v polárních souřadnicích, pro zoom použijeme polární souřadnice v logaritmickém měřítku – problém se přenese do oblasti posunu). Existují i metody, jak provádět tyto výpočty v případě, že obraz obsahuje šumovou složku. 36 V tomto případě je více jak vhodné provést nejdříve analýzu z hlediska jaký základ WT zvolit, tzn. jaký by měla mít tvar konvoluční matice g a h, neboť správnou volbou lze eliminovat šum, ale při min. kvadratické chybě upraveného signálu a původního signálu. 41 Snímání a úpravy obrazu 2.10 Radonova transformace Radonova transformace37 nepřímo souvisí s Houghovou transformací. Přímá transformace Radonova se opírá o integrál obrazové funkce38 počítaný po přímce vedené v obrazové rovině. Přímka vystupuje ve vzorci v normálovém tvaru, tzn. její určující parametry jsou φ a r tak, jak se používají v Houghove transformaci. Integrál obrazové funkce pak provedeme pro všechny hodnoty φ (0 až π) a r (leží v R) a hodnoty integrálu opětovně vynášíme do transformované spektrální roviny s parametry φ a r zvané sinogram. V rovině sinogramu pak funkční hodnota integrálu obrazové funkce je vlastně úměrná součtu funkčních obrazových funkcí v jednotlivých bodech přímky. K přímé Radonově transformaci existují matematické nástroje pro inverzní Radonovu transformaci, tzn. ze spektrální roviny sinogramu lze zpět zrekonstruovat původní hodnoty obrazové funkce v rovině x, y. Matematický aparát inverzní Radonovy transformace je odvozen od dvourozměrné Fourierovy transformace skrze definici Laplaciánu39 , přičemž mezi Radonovou a Fourierovou tranformací existují matematické vztahy z hlediska řezu, které pro odvození zpětné transformace jsou použity. Složitý matematický aparát je dnes nahrazen numerickým výpočtem využívající filtrovanou zpětnou projekci - FBP (Filtered Back Projection). Výpočet bez FBP lze zrealizovat takto: 37 Odvodil ji matematik Radon narozený v Čechách. 38 Funkce popisuje analyticky jas obrazového objektu v x, y rovině, tj. obrazové rovině. 39 Laplacián je obecná definice druhé derivace obecné vícerozměrné funkce. 42 Obr. 34. Integrace po přímce obrazové funkce x y obrazová funkce f(x,y) r=xcos(φ )+ysin (φ) r φ L Fig. 33. Integrace po přímce L skrz obrazovou funkci f(x,y) x y obrazová funkce f(x,y) r=xcos(φ )+ ysin (φ ) r φ L 2 Zpracování obrazového signálu 1. Data sinogramu uložíme do matice, kde v každém sloupci leží hodnota útlumu pro daný úhel φ. 2. Provedeme jednorozměrnou FFT nad každým sloupcem, výsledky uložíme do matice. 3. Nově vypočtenou matici transformujeme z polárních souřadnic do kartézských souřadnic pomocí zvolené sady interpolací, teď jsme vlastně získali Fourierovo dvourozměrné spektrum obrazu. 4. Provedeme dvourozměrnou inverzní FFT nad interpolovanou kartézskou soustavou souřadnic. Přeneseme-li matematický popis Radonovy transformace do reálného světa počítačové tomografie40 , pak integrál obrazové funkce je nahrazen útlumem rentgenového záření procházejícího skrze snímanou část objektu41 , v CT je obecný objekt nahrazen lidským tělem. Výsledkem jedné části transformace pro daný úhel φ je běžný rentgenový snímek42 , který zachytí dané útlumy tkání43 . Samotný tomograf pořizuje 50 až 500 snímků s různými úhly φ, tzn. rentgenové snímky se pořizují pod různými úhly, kdy zdroj záření a snímač se pootočí o určitý úhel. Z takto pořízených snímků se vytvoří spektrum – sinogram - snímaného obrazu, tj. ve výsledku lidského těla. Na takto pořízené spektrum – sinogram - se aplikuje inverzní Radonova transformace, čímž získáme informace o původním obrazu a jeho řezu. Nutno si uvědomit, že sinogram z CT je zašuměn, pracuje se s digitalizovanými daty a dochází k zaokrouhlování během výpočtu, takže získaný obraz obsahuje spoustu artefaktů, které v originálním obrazu neexistují. Z těchto důvodů se hledají různá řešení, ať na úrovni matematického aparátu nebo na úrovni algoritmů FBP (Filtered back projection), jak šum a artefakty odstranit (zpravidla data získaná v bodu 3. před projekcí jsou filtrována za použití RAMP či Ramakrishan-Lakshiminarayanan (Ram-Lak) filtrů44 a uživatelských filtrů, např. Hann, Hamming, Butterworth45 ). 40 CT se používá v lékařství při zpracování rentgenových snímků pořízených na tomografech, mezi laickou veřejností označovanou jako počítačová tomografie pod zkratkou CT (Computing Tomograph). 41 V CT se bere v úvahu, že útlum rentgenového záření není lineární, ale je exponenciálně závislý I =I0 e −μ s , kde μ je koeficient útlumu a s dráha, I0 je intenzita před vstupem do prostředí. 42 Snímky se nesnímají na fotografický materiál, ale snímají se již elektronickým detektorem. 43 Hodnotě r pak odpovídá snímaná rovina. 44 Jde o filtr typu horní propust. 45 Jde o filtry typu dolní propust. 43 Snímání a úpravy obrazu Iterativní rekonstrukce se opírají o to, že již máme nějakým způsobem zrekonstruovaný obraz (např. pomocí výše matematicky popsaného způsobu), pak provedeme nad takto získaným obrazem přímou transformaci a porovnáme ji s originálním pořízeným sinogramem. Pak v každé iteraci upravíme hodnotu pixelu zrekonstruovaného obrazu o rozdíl46 mezi vypočteným sinogramem a originálním získaným sinogramem. Iterace zastavíme v okamžiku, kdy dosáhneme požadovanou shodu mezi originálním a vypočteným sinogramem nebo po požadovaném počtu kroků. Nevýhodou tohoto postupu je, že nemusí konvergovat vlivem šumu, ale i nedostatečným počtem projekcí. Existuje i možnost zpětné transformace bez použití FT a FBP, kdy obraz budeme postupně iterativně upřesňovat. Výpočet lze charakterizovat takto: 1. Všechny body rekonstruovaného obrazu nastav na hodnotu 0. Pokračuj bodem 2. 2. Zpracovávej postupně všechny sloupce sinogramu podle bodu 3.47 3. Pro vybraný sloupec sinogramu (tj. parametr φ) opakuj bod 3. 4. Pro každou hodnotu jasu ve sloupci, která určuje hodnotu r, urči polohu přímky v rekonstruovaném obraze (známe tak r a φ), a na této přímce spočítej průměrnou hodnotu jasu, tuto hodnotu odečti od hodnoty jasu sinogramu a získej tak rozdíl. Rozdíl pak rovnoměrně rozděl všem bodům na přímce tak, aby průměrný jas na přímce odpovídal hodnotě jasu v sinogramu. 5. Po zpracování celého sinogramu lze pokračovat dále již zpřesňujícím iterativním výpočtem uvedeným v předchozím odstavci. 46 Hodnotu rozdílu nelze aplikovat přímo, ale je nutný k tomu jistý matematický aparát, který lze nalézt v odborné literatuře, zpravidla se jedná o systém řešení nelineárních diferenciálních rovnic, nebo též aparát zvaný EM - Expecation Maximizaton a ML - maximum likelihood. 47 Na pořadí zpracování nezáleží, ale s výhodou lze využít fakt, že hodnotám úhlů φ=0° a 90° odpovídají přímky jdoucí po řádcích a sloupcích v rekonstruované matici, nebo správnou volbou pořadí volby úhlů (0°, 90°, pak 45°, 135° a pak vždy polovina předchozího) zlepšuje finální odhad obrazu. 44 2 Zpracování obrazového signálu Samotná Radonova transformace v případě použití pro účely filtrace může být použita pro odstranění malých objektů z obrazu či zvýraznění čárových prvků (např. používá se při zpracování fotografií nebeských těles a detekci meteoritů, kdy úspěšnost detekce lze zvýšit až 90%). 45 Obr. 37. Sinogram barevného testovacího obrazu Obr. 35. Sinogram čb. fotografie Obr. 36. Sinogram z CT a rekonstrukce řezu lidské lebky Snímání a úpravy obrazu 2.11 Filtry využívající matematickou morfologii Jedná se o binární dilataci, erozi, otevření a uzavření. Filtry lze úspěšně aplikovat jak na binární obrazy, tak i obrazy ve stupních šedi. Filtry využívají faktu, že na obraz je možno pohlížet jako na množinu, přičemž mezi jednotlivými množinami můžeme realizovat součet či rozdíl ale i průnik. Dilatace je pak definována jako součet dvou množin dvou obrazů nebo téhož obrazu, který je posunut o daný vektor. Zpravidla je volena velikost vektoru rovna hodnotě 1, tj. právě o jeden zobrazovací bod. Vzhledem ke kartézské soustavě, používané pro vyjádření informace o obrazu, však může vektor nabýt i při hodnotě velikosti 1 až 8 směrů, přičemž výsledek operace je právě závislý na tomto směru. Eroze je definována jako množinový rozdíl, opět téhož obrazu posunutého o daný vektor, je to operace duální k operaci dilatace. Otevření je definováno jako eroze následovaná dilatací a uzavření jako dilatace následovaná erozí. Jednotlivé operace se používají k vyplnění děr, ztenčení objektů, odstranění malých objektů, nalezení hranice mezi texturami48 , zjištění zastoupení textury dané velikosti. V případě nebinárních obrázků lze morfologické operace realizovat taktéž, ale nutno mít na zřeteli, že budeme hledat maxima jasu nebo maxima jasu v rámci doplňku. Operaci otevření a uzavření lze snadno realizovat pomocí valící se kružnice po hraně segmentu s identickým jasem49 viz Chyba: zdroj odkazu nenalezen. Morfologické operace pak můžeme použít např. pro určení gradientu v obrázku. 48 V textuře musí být rozdíl ve velikosti, pak menší texturu odstraníme uzavřením skrze masku odpovídající velikosti menší textuře, větší texturu otevřeme skrze masku, která je přibližně tak velká jako vzdálenost mezi prvky textury, nakonec upravíme hranici. 49 Rozdíl mezi otevřením a uzavřením je, kterou stranu hranice použijeme pro valení kružnice, v příkladu na Chyba: zdroj odkazu nenalezen tedy horní nebo spodní strana původní hranice. 46 Obr. 38. Příklady operací eroze a dilatace 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 zdrojový obrázek eroze (pro posun vlevo) dilatace (pro posun vlevo) 2 Zpracování obrazového signálu Dále morfologické operace využívají následující známé algoritmy. Všechny algoritmy lze matematicky popsat pomocí základních morfologických operátorů a množinové algebry. 2.11.1 Hit or Miss filtry Jde o jednoduchý algoritmus, který spadá mezi morfologické filtry, využívající práci s maskou n × n bitů, zpravidla 3 × 3 (jako konvoluční maska), realizující logické i množinové operace mezi maskou a binárním obrazem. Masku posouváme po celém obrazu jako konvoluční masku. Operaci lze zapsat následovně: Princip algoritmu: Maskou projdi celý obrázek, tam, kde se shodují hodnoty pozadí a popředí dle masky nastav v místě řídícího bodu hodnotu 1, jinak 0. Řídící bod je uvnitř masky, zpravidla střed. Maska je tvořena hodnotami pozadí: 0 = B1, hodnotami popředí: 1 = B2 tam, kde v masce není určena hodnota, na hodnotě v obrázku nezávisí. Algoritmus umí na základě vhodných masek - viz Obr. 40. - najít:  samostatně ležící bod – maska a  rohový bod – maska b - nutno rotovat po 90°  koncový bod úsečky – maska c - nutno rotovat po 90°  křížení či větvení – masky d, e - nutno rotovat po 45°  či jiné oblasti, masky mohou mít i sudý rozměr. 47 Obr. 39. Otevření/uzavření nebinárních obrázků pomocí valící se kružnice původní hranice nová hranice po otevření/uzavření A=A−B1∩A c −B2 Snímání a úpravy obrazu Existuje celá řada heuristických algoritmů, které používají v základu Hit or Miss filtr, kdy se používají dále dilatace, eroze, negace původního obrazu, k nim různé dodatkové operace jako je průnik, rozdíl, sjednocení ale i logický součet a součin. Některé algoritmy jsou uvedeny níže, ale kromě nich lze hledat i doplňky k segmentům obrazu, hledat min. rozměr segmentu, aby byl konvexní, a jiné operace. 2.11.2 Kostra segmentu Algoritmem využívajícím masky lze vytvořit kostru segmentu, tzn. zúžit na 1 bod. Algoritmus probíhá iterativně: Najdi všechny body (nalezený bod se určuje vůči centru masky), které vyhovují maskám - viz Obr. 41., které rotuj o 90°, nalezené body odečti od původního obrázku, úpravy ukonči, když již nebyl nalezen v obrázku žádný bod nalezený pomocí masek. 48 Obr. 41. Masky pro nalezení kostry obrazu 0 0 0 1 1 1 1 0 0 011 1 Obr. 40. Příklady základních masek Hit or Miss a výsledných operací (zleva a, b, c, d, e) 0 0 01 0 0 00 0 0 1 0 0 1 1 01 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 zdrojový obrázek příklad nalezených bodů 1 samostatný bod 1 rohový bod 1 koncový bod dle masek a, b, c 2 Zpracování obrazového signálu Nevýhodou tohoto algoritmu je, že ve složitějších obrázcích vytváří parazitní větvení pahýly. Tyto pahýly lze eliminovat aplikací níže uvedených vzorů dle. Obr. 43., vzory je nutno rotovat o 90°, ale použití těchto vzorů je omezené, neboť by mohli odstranit celou kostru. Obr. 43. Vzor odstraňující pahýly V případě, že segment vytváří uzavřenou oblast, lze odstranit všechny pahýly bez obav, že by kostra objektu byla odstraněna úplně. Existují i další alternativy, jak eliminovat parazitní pahýly u segmentů, které nevytváří uzavřené struktury, např. tím, že nejdříve označíme konce segmentu, nalezneme kostru a tu pomocí dilatace budeme přičítat k nalezeným koncům. Hledání kostry obrázku má i alternativní matematický algoritmus, který je však výpočetně náročný, kdy algoritmus hledá v obrázku místa, kde může vepsat kružnici o max. poloměru, přičemž si uschovává informaci o středu kružnice. 49 Obr. 42. Ukázka algoritmu hledání kostry segmentu 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 zdrojový obrázek po aplikaci všech 8 masek výsledek červeně označeny body které budou odstraněny Obr. 44. Příklad kostry určené nejmenšími vepsanými kružnicemi 0 0 0 1 0 0 01 0 0 0 0 0 0 00 Snímání a úpravy obrazu 2.11.3 Obrys segmentu Zjištění obrysu vyplněného segmentu v obrázku pomocí eroze lze tímto algoritmem: Uschovej původní verzi obrázku, originální obrázek projdi erozní maskou, viz Obr. 45., tvořenou 3 × 3 body, resp. proveď operaci logického součinu z obrázku na obvodu masky do jejího centrálního řídícího bodu, výsledek odečti od uchovaného obrázku - viz Obr. 46., neboli: X =A−(A⊖B) 2.11.4 Vyplnění ohraničené plochy Vyplnění ohraničené plochy lze rovněž zajistit pomocí algoritmu využívajícího dilataci: Uschovej původní obrázek, původní obrázek procházej dilatační maskou od inicializačního bodu, původní obrázek sečti s výsledkem. Dilatační maska je z 3 × 3 bodů s centrálním bodem ve středu. Existují i jiné algoritmy, např. semínkový50 . 50 Samotný semínkový algoritmus lze snadno popsat a vyhledat na Internetu, nutno však předeslat, že při bezmyšlenkovém přístupu k realizaci tohoto algoritmu, algoritmus v poměru test/změna barvy, pracuje velice neefektivně a provádí některé testy téhož bodu až 4x. Rovněž na Internetu jsou algoritmy, které nebudou pracovat bezchybně. 50 Obr. 45. Erozní maska 11 1 1 1 111 1 Obr. 47. Dilatační maska 1 111 1 Obr. 46. Příklad fungování hledání obrysu 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 zdrojový obrázek eroze obrázku výsledek 2 Zpracování obrazového signálu 2.11.5 Rozšiřování objektů Objekty, které mají malou kompaktnost, můžeme rozšířit tak, aby jejich kompaktnost narostla pomocí masek s dilatací - viz Obr. 49. Masky je nutno rotovat o 90°. 51 Obr. 48. Masky pro rozšíření 1 1 0 1 0 0 1 1 1 1 1 1 1 0 Snímání a úpravy obrazu 3 Detekce příznaků RYCHLÝ NÁHLED KAPITOLY Kapitola nastiňuje problémy jak předzpracovaný obraz dále zpracovat, tak aby obrazovou informaci bylo možno využít pro řídící algoritmy či jiné rozhodovací procesy. CÍLE KAPITOLY Po prostudování této kapitoly nahlédneme do problematiky: ● vyhledávání vzorů v obraze, ● identifikace vzorů a přiřazení vzorům jednoznačné klasifikátory. KLÍČOVÁ SLOVA KAPITOLY segmentace, parametrizace, moment, pravidlové systémy Zpracování digitálního obrazu můžeme rozdělit na: Úkolem je najít relevantní údaje v obraze a přiřadit jim příznaky. Je důležité, aby příznaky byly:  spolehlivé - tzn. pro stejnou třídu objektů musí být příznak totožný,  diskriminovatelné – tzn. pro každou třídu musí být příznak odlišný,  nezávislé - tzn. mezi příznaky nejsou vazby. Obecně detekce příznaků je zpravidla netriviální úloha vyžadující hlubší rozbor celého problému a k vlastní detekci se používají dále uvedené postupy. Přesto, že této problematice se věnuje velká pozornost, informací použitelných v obecných rovinách je poskrovnu. 3.1 Segmentace Segmentace má za úkol rozdělit obraz do oblastí, jež můžeme označit za stejnorodé, např. oddělení pozadí od zájmových částí. Převážná část algoritmů používá prahování s použitím 52 3 Detekce příznaků histogramu a různé metody testování shodnosti okolí vůči testovanému obrazovému bodu nebo různé heuristické algoritmy. 3.1.1 Region growing Algoritmus předpokládá, že obdrží již binárně zpracovaný obraz, který postupně procházíme a na základě odbarvovacích masek postupně obarvíme jednotlivé objekty. 3.1.2 Štěpení a spojování oblastí Obraz je nejdříve rozdělen do skupin, potom na základě testování jasu mohou nastat dva případy:  je-li jas v oblasti různorodý, tak obraz rozštěpíme,  jsou-li ve dvou sousedících oblastech jasy shodné, oblasti sloučíme. 3.1.3 Popis segmentů  Pro popis segmentů je možno použít:  velikost plochy – problém lze vyřešit jednoduchým sečtením počtu obrazových bodů patřících do segmentu,  směr - určíme tak, že kolem objektu se snažíme opsat co nejmenší obdélník tak, aby objekt byl obsažen v obdélníku, jeho delší strana pak určuje směr,  popis pomocí průběhu obvodu a jeho délky - řetězcový kód je složen z čísel, kterými jsou očíslovány úsečky - viz Obr. 47., které reprezentují směr, ve kterém se nachází následující obrazový bod patřící do obvodu segmentu. Pro uvedený obrazec - viz Obr. 47. , je řetězcový kód od výchozího bodu: 1207676544322. Někdy se tento kód ještě diferencuje tak, že zkoumáme, kolikrát musíme před dalším krokem obrázkem otočit po chodu hodinových ručiček, aby následující chod byl ve směru 0, tzn. pro uvedený obrázek je: 1167717770770, čili 53 Obr. 49. Příklad číslování směrů pro určení řetězcového kódu (vlevo) a příklad segmentu pro ukázku řetězcového kódu (vpravo) 1 02 3 2 0 4 6 1 3 5 7 Snímání a úpravy obrazu pro výpočet i-té pozice: xi=(n+xi−xi−1)mod n , kde: n = 4 pro 4 směrový, 8 pro osmi-směrový chod, x0=0. Počet chodů nám dává délku obvodu,  kompaktnost – určuje se jako poměr obvodu segmentu (její druhé mocniny) k jeho ploše, kruh má toto číslo nejmenší,  výstřednost, podloudnost, pravoúhlost - můžeme ji určit buď z poměru stran opsaného obdélníku s co nejmenším obsahem, nebo jako měření nejdelších na sobě kolmých tětiv. U pravoúhlosti jde o poměr mezi plochou zkoumaného objektu a velikostí obsahu opsaného obdélníka,  Eulerovo číslo, tj. počet děr v segmentu,  vzdálenost bodů od hrany či její průměrná hodnota - viz Obr. 51. Výpočet lze zrealizovat pomocí eroze, ale existuje i efektivní algoritmus popsaný např. Rosenfeldem a Pfaltzem. 3.1.4 Moment Moment je definovaný jednoduchým matematickým vztahem: kde: p, q - jsou celočíselné konstanty větší jak 0 a udávající stupeň, řád momentu, fx, y - hodnota jasu v bodu x, y, 54 Obr. 50. Vzdálenost bodů od hrany 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 2 2 2 1 0 0 0 1 1 1 1 1 0 0 0 1 2 3 2 1 0 0 0 1 1 1 1 1 0 0 0 1 2 2 2 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 zdrojový obrázek výpočet vzdálenosti m p, q =∑Ω ∑Ω x p y q f x , y mc p, q =∑Ω ∑Ω (x−xc ) p ( y−yc ) q f x , y xc= m 1,0 m 0,0 yc= m 0,1 m 0,0 ms p, q = m p ,q m 0,0ε ε= p+q 2 +1 3 Detekce příznaků Ω - je množina bodů spadající do daného klasifikovaného segmentu. Moment je citlivý na posun, velikost i rotaci segmentu, což lze korigovat již při výpočtu momentu, kdy moment budeme počítat k těžišti (centrum) objektu mc, a zavedeme normalizaci na velikost (size) segmentu ms, do výpočtu můžeme zahrnout i natočení segmentu. Z hodnot momentů můžeme určit jak podlouhlost, tak i úhel natočení objektu i integrální jas objektu. 3.2 Klasifikace Výstupem klasifikátoru je jednoznačný popis - numerický či syntaktický zkoumaného obrazu s možností realizovat na základě tohoto popisu regulační smyčku či realizovat řídící algoritmus nebo též poskytnout již potřebná finální data pro nějaký vyšší rozhodovací algoritmus či systém. Nelze obecně definovat způsob klasifikace, neboť záleží na faktoru, co má být v obraze klasifikováno, např. o zcela jiný způsob půjde v případě, že výstupem klasifikátoru budou informace typu, které získáme při OCR - optickém rozpoznávání písma nebo rozpoznávání objektů, u kterých předem známe tvar, např. značky, vodící čáry či jinak vymezující značení, nebo obecných objektů (úsečky, kružnice, rohy a jiné geometrické útvary), ze kterých dále vyvozujeme další závěry nebo provádíme další výpočty, např. vytvoření 3D - viz zpětná stereo-projekce. Samostatnou kapitolou jsou nástroje pro klasifikaci v medicínské oblasti, kdy chceme nalézt objekty, které signalizují anatomické změny – výdutě, nádory, zúžení či slepá ramena. Samotnou klasifikaci je možné provádět pomocí různých klasifikátorů, např.:  statistických, např. pomocí shlukové analýzy nebo analýzy SVM (Support Vector Machines)51 , tzn. s předpokladem, že segmenty v n rozměrném prostoru vytvářejí shluky či jsou od sebe odděleny (každému segmentu náleží jeden prostor), přičemž pro právě hledanou klasifikaci buď vypočteme Eulerovou vzdálenost od již předem klasifikovaných obrazů a vybereme pak ten klasifikátor, který má min. vzdálenost, nebo v n rozměrném prostoru se snažíme oddělit jednotlivé hodnoty klasifikátorů pomocí přímky či jiné funkce (polynomické, sigmoid, Gauss), 51 Pracuje podobně jako neuronová síť, ale lze snadněji spočítat průběh dělící funkce. 55 Snímání a úpravy obrazu  pravidlových, syntaktických či fuzzy-logic, kdy předpokládáme, že v obraze jsme již provedli segmentaci a známe popis segmentů a na základě těchto hodnot zkoušíme pomocí pravidel nebo syntaxí určit hodnotu klasifikátoru,  neuronových,  transformačních či korelačních – např. pro triviální klasifikaci přímek se nabízí právě Houghova tranformace, nebo obrazy porovnat na základě výpočtu korelace. Neuronové sítě jsou popsány v učebním textu: Autonomní systémy, ty mohou být použity jako filtr a obraz upravit (např. síť typu BAM), např. odstraněním chyb v obraze nebo též stanovit přímou hodnotu klasifikátoru (např. neuronové sítě lze s výhodou použít pro učící se systém OCR). Zde je příklad pravidlového systému, který má za úkol rozpoznat konkrétní tvar, systém může pracovat např. takto: 1. V pravidlovém systému máme uloženo n morfologických prvků a před vlastní klasifikací máme uloženo v bázi znalostí řetězec či strom, ve kterém máme uložen výskyt jednotlivých morfologických prvků v každém klasifikovaném tvaru. 2. Po předložení klasifikovaného tvaru začneme v něm hledat jednotlivé morfologické prvky, vždy od většího k menšímu. 3. V případě, že morfologický prvek nalezneme, tuto část z klasifikovaného tvaru vyjmeme a vytváříme řetězec (strom), do kterého vkládáme informaci o nalezeném morfologickém prvku52 , v případě, že ještě v klasifikovaném tvaru zbývá nezpracovaná část, postupujeme znovu bodem 2, jinak pokračujeme bodem 4. 4. Z báze znalostí pak porovnáme získaný řetězec s řetězcem v bázi znalostí nebo hledáme danou větev ve stromu, při nalezení shody v řetězcích či nalezení větve ve stromu jsme nalezli i daný klasifikovaný tvar. 52 Sytém může obsahovat i morfologické prvky, které do syntaxe nebudou zahrnuty – např. okraje okolo prohledávaného tvaru či jiné údaje, rovněž ve stromu může a nemusí být uložena informace o pozici, kde morfologický prvek byl nalezen. 56 4 Zpětná stereo-projekce 4 Zpětná stereo-projekce RYCHLÝ NÁHLED KAPITOLY V této kapitole je ozřejmeny postupy pomocích kterých můžeme pomocí 2D obrazů vymodelovat 3D snímanou scénu. CÍLE KAPITOLY Po prostudování této kapitoly porozumíme základním matematickým postupům zpětné stereo-projekce. KLÍČOVÁ SLOVA KAPITOLY stero-projekce, kamerový systém, souřadnicový systém Zpětná stereo-projekce nám umožňuje na základě dvou pořízených obrazů téže scény vytvořit 3D model scény nebo např. určit vzdálenost určitého vybraného bodu P od kamerové osy. Nejjednodušší je situace v případě, kdy použijeme dvě totožné kamery se stejnými ohniskovými vzdálenostmi f, které mají rovnoběžné osy snímání a jsou umístěny v téže snímací rovině - viz Obr. 43., a počátek souřadného systému O položíme na střed mezi kamerami. 57 Obr. 51. Zobrazení zpětné stereoprojekce // // P(x,y,z) O O2 O1 z y xf f b/2 b/2u1 u2 v2 v1 X1 X2 Snímání a úpravy obrazu Pak z podobnosti příslušných trojúhelníků můžeme pro bod P velice rychle odvodit: Výpočet lze zrealizovat, i když dříve uvedený předpoklad nesplníme, tzn. osy kamer nemusí být rovnoběžné, kamery jsou na různých souřadnicích a mají různou ohniskovou vzdálenost, je však nutno k problému přistoupit skrze homogenní souřadnice, vyjádřit pomocí nich vlastnosti kamer a zavést transformace souřadnicových systémů kamer do souřadnicového systému O. Potom: Matice Pi má rozměr 3x4 prvky a popisuje transformaci bodu P do zobrazovacích rovin kamer. Její hodnoty pak určíme kalibrací kamerového systému, min. počet kalibračních bodů je 6 pro každou kameru. Poněvadž systém rovnic je předeterminován, měření souřadnic u, v je zatíženo chybami, máme však možnost systém řešit metodou nejmenších čtverců a chyby minimalizovat. Pro normované souřadnice a kameru bez zkreslení perspektivy můžeme pro bod x' 53 na zobrazovací ploše kamery a obecný bod x v prostoru zapsat: z ∣ x1 y1 1 ∣= ∣ f 0 0 0 f 0 0 0 1∣∣ 1 0 0 0 0 1 0 0 0 0 1 0∣∣ x y z 1 ∣ pro: xR2 ' = ∣ x1 y1 1 ∣; K f = ∣ f 0 0 0 f 0 0 0 1∣;Π0= ∣ 1 0 0 0 0 1 0 0 0 0 1 0∣ λ x1R2 =K f Π 0 X R3 po přidání translace souřadnic kamery: λ ∣ x1 y1 1 ∣= ∣ fsx fsθ ox 0 fsy oy 0 0 1 ∣Π 0 ∣ x y z 1 ∣λ x1R2 =K Π 0 X R3 kde: K je transformační matice kamerového systému a zahrnuje transformaci středu objektivu vůči souřadnicovému systému umístěnému v levém horním rohu, zachování poměru stran x/y, zkosení roviny a ohniskovou vzdálenost. 53 R2 - dvourozměrné, R3 - třírozměrné vyjádření. 58 z= bf u1−u2 x= b(u1+u2) 2(u1−u2) y= b(v1+v2) 2(u1−u2) ui=Pi⋅x , x=(x , y , z ,1) , ui=(qui ,qvi ,q) , q≠0 4 Zpětná stereo-projekce Pro 2 kamery a totožný bod na dvou obrázcích platí: λ1 x1=Rλ2 x2+T kde λ, R, T jsou neznámé hodnoty a parametry představují: R - otočení kamery 2 vůči kameře 1, T - posun kamery 2 vůči kameře 1, λ - obecný koeficient, zahrnující hloubku. Pak hledáme řešení výše uvedené rovnice, kterou formalizujeme. Máme několik matematických možností, jak systém vyřešit: pro lineární řešení je nutné mít min. 8 párů bodů, pak však máme více rovnic než je neznámých (můžeme zahrnout i více než 8 bodů) a z důvodů chyb při odečtu kamerových souřadnic používáme přibližné řešení metodou nejmenších čtverců. Pro nelineární řešení postačuje již 5 párů bodů, avšak obdržíme až 10 řešení. Známe-li z rektifikace parametry kamer, a jsou-li kamery paralelně, můžeme na základě disparity bodů v obraze určit hloubku bodu v obrazu. Není třeba zdůrazňovat, že chceme-li, aby systém sám vytvářel 3D model zcela automaticky, neobejdeme se bez předchozích nástrojů jako je odstraňování šumu, detekce hran a rohů, nástrojů pro ztotožňování téhož prvku ve dvou různých obrazech (morfologické prohledávání) a až posléze můžeme přistoupit ke konstrukci 3D modelu. 59 Snímání a úpravy obrazu 5 Pár slov na závěr Tento dokument nemohl obsáhnout velice široký rozsah problematiky týkající se digitálního zpracování obrazu54 , ale je jen jistým vodítkem, aby bylo možno již v této chvíli přistoupit k fyzické realizaci jednotlivých výše probraných postupů při digitálním zpracování obrazu na úrovni FPGA a porovnat toto řešení (v oblasti rychlosti, spotřeby energie, rychlosti vývoje) s běžnými postupy využívající běžné procesory na úrovni jazyků C a Assembler. Materiály, které se dotýkají programové části, neuronových sítí, speciálních matematických postupů (např. stimulované žíhání) a FPGA jsou uvedeny v dokumentu: Autonomní řídící systémy. 54 Dokument bude dále doplňován tak, aby dále pokryl mnohé postupy, na kterých se teprve pracuje (např. morfologické hledání hran) nebo nebyly zmíněny z důvodů časové náročnosti zpracování této problematiky, aby ji bylo možno prezentovat ve zhuštěné formě. 60