5 Úpravy rozložené mapy Obsah Předchozí kapitola Následující kapitola Titulní strana

          Výsledky rozkladu na tiskové barvy nejsou ideální a pro účely rozpoznávání by bylo vhodné jejich kvalitu ještě zlepšit. Ke zlepšení výsledků lze použít v zásadě dva druhy metod: metody snažící se napravit výsledky rozkladu v místech klasifikace s velkou chybou (příklad takových oblastí je na obrázku 4.9) a metody nezávislé na znalosti oblastí klasifikovaných s velkou chybou.

          Úpravy rozložené mapy můžeme chápat jako předzpracování před vlastním rozpoznáváním. Vstupem filtrů je sada bitových map odpovídajících jednotlivým tiskovým barvám a odstínům, výsledkem je sada modifikovaných bitových map, které budou vstupem pro rozpoznávání.


5.1 Kontextový filtr

          Myšlenka kontextového filtru je velice jednoduchá - na základě znalosti výsledku rozkladu (výsledkem rozkladu rozumíme barvu a příznak klasifikace s velkou chybou) ve středovém pixelu a jeho okolí určit výslednou barvu středového pixelu. Tímto způsobem je možné odstraňovat pravidelné chyby rozkladu, šum, přechody apod.


5.1.1 Obecný kontextový filtr

          Vstupem filtru je obraz f, hodnota každého pixelu je podmnožinou tiskových barev a příznaku klasifikace s chybou (tiskové barvy a chybový příznak jsou souhrnně označeny jako MCLE). Výstupem filtru je obraz g stejného typu jako vstup. Dalšími vstupy filtru jsou okolí N, podmínka C a akce A. Okolí N je definováno jako množina dvojic N = {(x1, y1), (x2, y2) ... (xn, yn)}. Výpočet kontextového filtru je definován následujícím způsobem:

          Rovnice 5.1 (5.1)

          V kontextovém filtru je rozhodující podmínka C, kterou zatím nebudu blíže specifikovat. Podstatné je, že na základě barvy středového pixelu a pixelů v okolí vrací logickou hodnotu. Pokud je tato podmínka splněna, barvu ve středovém pixelu modifikuji na základě akce A. Akce A udává, které tiskové barvy se mají odebrat (označeno AR) a které naopak přidat (označeno AA). Pokud podmínka není splněna, je ponechána původní barva pixelu.

          Z definice výpočtu filtru je vidět, že podmínka C ke svému výpočtu může použít barvu středového pixelu fx,y a barvy pixelů v okolí N středového pixelu. Protože C je parametrem kontextového filtru, je nutné specifikovat tvar podmínky tak, aby bylo možné filtr implementovat. Možností zavedení podmínky je mnoho, mnou zvolené řešení umožňuje provádět praktické korekce výsledků rozkladu na tiskové barvy.

          Jako parametr podmínky jsou předávány různé množinové operace (jejichž výsledkem je logická hodnota) pro porovnávání tiskových barev. Z tohoto důvodu jsem zavedl symbol [tečka], který značí jednu z následujících operací:

          Rovnice 5.2 (5.2)

          V dalším textu se budu na první dvě operace odkazovat pomocí množinového znaménka, na další tři pomocí slovního popisu (operace obsahují více znamének). Dále jsem zavedl symbol [trojúhelník] pro označení jedné z následujících operací pro porovnávání počtu prvků množiny (výsledkem operací je opět logická hodnota):

          Rovnice 5.3 (5.3)

          Podmínka C se skládá ze dvou částí - CC (podmínka na barvu středového pixelu) a CN (podmínka na barvy pixelů v okolí N středového pixelu). Část CN může být v podmínce zastoupena několikrát.

          Rovnice 5.4 (5.4)

          Protože zápis v symbolech je sice přesný, ale těžko srozumitelný, pokusím se obsah podmínky vyjádřit slovy. První podmínka je kladena na barvu středového pixelu. V ní je požadováno, aby jeho barva byla ve vztahu definovaném pomocí [tečka] vzhledem k zadané barvě A. Další podmínky požadují, aby v okolí N středového pixelu byl daný počet pixelů (vyjádřeno pomocí [trojúhelník] a n) barvy vyhovující operaci [tečka] vzhledem k A.

          Na závěr ještě uvedu několik praktických příkladů použití filtru. Příklady slouží pouze pro ilustraci možností zadání parametrů filtru, u každého z příkladů existují různé varianty závislé na přesném popisu odstraňovaných chyb.


Příklad 1: Odstranění izolovaných pixelů

          Ve výsledku rozkladu na tiskové barvy se objevily na několika místech ve žlutých plochách černé izolované pixely. Úkolem kontextového filtru je odstranit tyto pixely:

          Rovnice 5.5 (5.5)

          Filtr požaduje pouze 5 pixelů ve čtvercovém okolí s osmi pixely proto, aby k záměně došlo i na okrajích žluté plochy. Naopak k záměně nedojde, pokud je černý pixel součástí nějakého většího černého objektu.


Příklad 2: Zaplnění děr v objektech

          Výskyt drobných děr v objektech je běžným jevem. Tyto díry lze odstranit také morfologickým filtrem (viz dále). Kontextový filtr ale představuje šetrnější řešení, protože obraz nemodifikuje globálně. Uvedený příklad odstraňuje drobné trhliny v plochách černé barvy.

          Rovnice 5.6 (5.6)


Příklad 3: Oprava chybně klasifikovaných barev

          V tomto příkladě se pokusíme napravit chybně klasifikované pixely na horizontálním přechodu mezi barvami BG a BG|BK. Na přechodu se chybně vyskytují barvy BG|?|BL, šířka chybně klasifikované oblasti je maximálně jeden pixel.

          Rovnice 5.7 (5.7)

          Na závěr ještě uvedu výsledky aplikace sady kontextových filtrů na separaci černé barvy převzatou z obrázku 4.8. Byl použit filtr pro odstranění malých objektů (podobné jako odstranění izolovaných pixelů) a filtr pro zaplnění děr v objektech.

Výsledek aplikace sady kontextových filtrů (vstupní obrázek).
vstupní obrázek
Výsledek aplikace sady kontextových filtrů (po aplikaci sady kontextových filtrů).
po aplikaci sady kontextových filtrů

Obrázek 5.1
Výsledek aplikace sady kontextových filtrů.


5.1.2 Speciální kontextové filtry

          Pro zjednodušení korekce barev u pixelů klasifikovaných s velkou chybou je vhodné zavést speciální kontextové filtry. Speciální filtry je možné zadat pomocí několika obecných filtrů, jejich zavedení však představuje zjednodušení zadávání postupu zpracování.

          Speciální kontextové filtry vyhledávají pixel s chybovým příznakem a o korektnosti jednotlivých rozpoznaných barev rozhodují na základě barev okolních pixelů. Okolí N je parametrem speciálního filtru, proto ve formálním zápise není uvedeno.

          Rovnice 5.8 (5.8)

          Slovně řečeno, filtr považuje barvu A v pixelu klasifikovaném s chybou za správnou, pokud v okolí je alespoň a (parametr speciálního filtru) dalších pixelů s touto barvou. Výpočet by bylo možné ještě zdokonalit, pokud bychom uvažovali z okolí pouze pixely klasifikované bez chyby. V tom případě by ale bylo vhodné počet požadovaných pixelů z okolí udávat v procentech (dopředu nevíme, kolik pixelů z okolí bude klasifikovaných bez chyby).

          Kromě odstraňování barev je možné se také pokusit na základě okolních pixelů některé barvy doplnit. Filtr nalezne pixely s chybou klasifikace a pro všechny barvy neobsažené v tomto pixelu zjistí počty těchto barev v okolních pixelech. Pokud počet barvy přesáhne konstantu b, filtr příslušnou barvu do středového pixelu přidá. Přepis takového filtru pomocí obecných kontextových filtrů vypadá následovně:

          Rovnice 5.9 (5.9)

          Pro použití tohoto filtru platí totéž, co v předchozím případě. Také zde je možné výpočet zdokonalit, pokud budeme uvažovat pouze okolní "dobře" klasifikované pixely.

          Posledním velmi jednoduchým filtrem, který je užitečný pro práci s chybovými příznaky, je filtr, který chybové příznaky odstraňuje. Takový filtr je výhodné aplikovat na závěr zpracování rozložené mapy.


5.2 Detekce rastrů

          V případě, že odstíny tiskových barev jsou tvořeny tiskovými rastry (což v běžném případě jsou), je pro účely rozpoznávání nutné plochy tvořené rastry zaměnit odpovídajícím odstínem barvy (např. LtYL). Pokud odstíny nejsou tištěny pomocí rastrů, nebo jsou rastry natolik husté, že se při digitalizaci slijí, není nutné detekci rastrů provádět.

          Touto oblastí zpracování obrazu se zabývá texturální analýza. Protože jsou tiskové rastry poměrně jednoduché, lze pro jejich detekci použít i jednodušší metody - např. průměrování nebo korelační techniky. Jistou možnost detekce představuje i kontextová filtrace. Z těchto jednodušších metod jsem vyzkoušel průměrování a korelaci, na základě korelace jsem vytvořil poměrně úspěšný filtr (jehož výsledky jsou zobrazeny na obrázku 5.5).

          Ještě než uvedu různé metody detekce rastrů, shrnu podmínky, za kterých musí pracovat. Tiskové rastry se vyskytují ve všech tiskových barvách kromě černé. Pro tisk rastrů se používá různá technologie, nejčastější (a v současné době téměř výhradní) způsob používá pravidelnou síť bodů, jejichž průměr závisí na požadovaném odstínu. Středy bodů v této síti bývají vzdáleny zhruba 7 pixelů (při digitalizaci v doporučeném rozlišení 600 x 600 dpi).

          Nyní již přistoupím k popisu vyzkoušených metod detekce rastrů.


5.2.1 Průměrování a kontextové filtry

          Průměrování představuje intuitivní postup podobný vnímání lidského oka nebo digitalizaci rastru velké hustoty. Pro průměrování se používá okno velikosti M x N pixelů (zpravidla čtvercové). Šířku a výšku okna volíme tak, aby byla do okna při jeho libovolné poloze padl stejný počet bodů rastru - to ovšem závisí na vlastnostech rastru.

          Výpočet provádíme následující způsobem: Pro každou polohu okna spočítáme výsledek funkce s(x, y) na základě separace barvy DkX (označeno fDkX). Podle výsledku funkce a zadaných koeficientů a, b (pro případ jednoho odstínu, v případě dvou odstínů je nutné přidat ještě c) určíme, jakému odstínu odpovídá obsah okna (označeno c(x, y)). Nakonec v okně odstraníme sytou tiskovou barvu DkX a celé okno vyplníme barvou odpovídající spočtenému odstínu.

          Rovnice 5.10 (5.10)

          Pro výpočet průměrování není nutné zavádět zvláštní filtr, lze využít sady kontextových filtrů (jejich výsledek ale není přesné průměrování). Výhodou tohoto přístupu je, že kontextové filtry připouští libovolně definované okolí N středového pixelu. Průměrování (pro případ jednoho odstínu) přepíšeme pomocí kontextového filtru následujícím způsobem:

          Rovnice 5.11 (5.11)

          Pokud bychom průměrování pomocí kontextových filtrů použili na tiskovou barvu se dvěma odstíny, bylo by nutné zvolit jiný postup. Protože jeden kontextový filtr neumožní rozlišení obou odstínů a zpracování je sekvenční (následující filtr pracuje nad výsledkem předchozího filtru), doporučuji použít následujícího postupu, který druhému filtru zajistí stejné podmínky, jako měl filtr první:

          Rovnice 5.12 (5.12)

          Průměrování je sice jednoduchá metoda, která dosahuje v detekci rastrů dobrých výsledků, na druhou stranu má ale dva zásadní nedostatky:

          Výsledky této metody a oba druhy chyb ukazuje obrázek 5.2. Na obrázku jsou patrné obě zmíněné chyby, zejména poškození svislých čar znázorňujících podrost. Průměrování lze s úspěchem použít pouze na žlutou tiskovou barvu, ve které se nevyskytují bodové ani liniové symboly. Na ostatní tiskové barvy by ho bylo možné použít pouze v případě, že již byly odstraněny bodové a liniové útvary.

Detekce rastrů průměrováním (vstupní obrázek).
vstupní obrázek
Detekce rastrů průměrováním (průměrování pomocí kontextových filtrů).
průměrování pomocí kontextových filtrů

Obrázek 5.2
Detekce rastrů průměrováním.


5.2.2 Korelační metody

          Korelační metody jsou založeny na porovnávání vzoru a obrazu. Existuje mnoho korelačních technik, v dalším textu budu vycházet ze základní. Pokud chceme nalézt v obraze nějakou pravidelně opakující se výplň plochy (např. tiskový rastr), vezmeme část této plochy jako vzor a budeme jím posouvat po obraze. Pro každou pozici vypočteme míru podobnosti a na základě ní rozhodneme, zda se pod vzorem nachází hledaná výplň či nikoliv.

          Vstupem základní metody je binární obraz f, binární vzor p velikosti M x N pixelů a koeficient a pro porovnávání podobnosti. Výstupem je binární obraz g popisující plochu, na níž byla nalezena hledaná výplň. Pro každou pozici vzoru (x, y) vypočteme míru podobnosti sB(x, y):

          Rovnice 5.13 (5.13)

          Pokud se vzor a obraz na pozici (x, y) liší málo, výsledkem funkce s(x,y) bude hodnota 1. V takovém případě do obdélníkové oblasti obrazu g odpovídající poloze vzoru zapíšeme příznaky, že zde byla nalezena hledaná výplň.

          Tato základní metoda je poměrně úspěšná. Na rozdíl od průměrování při vhodné volbě vzoru nezpůsobuje poškození bodových a liniových útvarů, ale výsledky nejsou tak dobré. Nabízí se několik vylepšení, které nám umožní dosáhnout lepších výsledků. Prvním z nich je rozšíření definice vzoru o pixely, které nemají být při výpočtu míry podobnosti použity. Příklad takového vzoru je na následujícím obrázku (značeno podle konvence použité v aplikaci):

Korelační vzor s nerozhodujícími pixely.

Obrázek 5.3
Korelační vzor s nerozhodujícími pixely.

          Toto vylepšení se odrazí pouze ve výpočtu sB(x, y) tak, že do součtu nebudou zahrnuty "šedé" pixely. Přesnou definici výpočtu uvedu až po následujícím rozšíření. Další možností je zavést váhy jednotlivých pixelů a umožnit požadavek shody. Např. při rozpoznávání bodu rastru je důležitý střed bodu a velké zastoupení prázdných pixelů v okolí bodu. Přechod mezi bodem a okolím již tak důležitý není, protože se body mírně liší tvarem i velikostí. Příkladem rozšíření minulého vzoru o váhy (opět podle konvence použité v aplikaci) může být vzor na obrázku 5.4.

          Aby bylo možné přesně popsat výpočet vylepšeného korelačního filtru, nejprve definuji popis vzoru. Vzor se skládá z bitové masky p popisující požadované pixely (graficky označeny jako černé pixely), bitové masky c popisující kriticky vyžadovanou shodu vzoru s obrazem (graficky značeno jako plné kolečko) a polem w popisujícím váhu pixelů. Pokud na pixelu nezáleží (graficky značen jako šedý pixel), jeho váha je 0, pixely s nízkou vahou (graficky označeny jako kružnice tenkou čarou) mají váhu 1 a pixely s vysokou vahou (graficky označeny jako kružnice tlustou čarou) mají váhu 2. Nesmí nastat situace, kdy ci,j = 1 a současně wi,j ą 0. Na hodnotách pi,j nezáleží, pokud wi,j i ci,j jsou nulové.

Korelační vzor doplněný o váhy pixelů.

Obrázek 5.4
Korelační vzor doplněný o váhy pixelů.

          Nyní již přistoupím k definici výpočtu. Je to v podstatě přepsaný výpočet základní korelační metody, ve kterém se navíc používá kriticky požadovaná shoda sC a váhy jednotlivých pixelů sW. Úspěšné porovnání se provede pouze v případě, pokud je na všech kriticky požadovaných místech shoda.

          Rovnice 5.14 (5.14)

          Pomocí rozšířené korelační metody se mi podařilo dosáhnou výsledků srovnatelných (nebo ještě lepších) jako v případě průměrování, navíc ale bodové a liniové objekty zůstaly nepoškozeny a na okrajích ploch se neobjevily postupné přechody. Na následujícím obrázku jsou zobrazeny výsledky detekce rastrů na separaci zelené barvy z obrázku 4.8.

Detekce rastrů korelační metodou (vstupní obrázek).
vstupní obrázek
Detekce rastrů korelační metodou (výsledek detekce rastrů).
výsledek detekce rastrů

Obrázek 5.5
Detekce rastrů korelační metodou.

          Bylo by možné provést ještě další vylepšení korelační metody, ale pro účely detekce rastrů popsaná verze plně postačuje. Podobnou metodu by pravděpodobně šlo použít i pro vyhledávání bodových útvarů bez možnosti otáčení.


5.3 Morfologický filtr

          Morfologické filtry jsou častým tématem v literatuře zabývající se digitálním zpracováním obrazu a proto se jimi nebudu podrobně zabývat. Z uvedené literatury je možné nalézt je v [2], [3] a [4]. Tyto filtry lze použít ke zkvalitnění výsledků rozkladu, nebo i pro účely rozpoznávání (kostry objektů, zeštíhlování apod.).

          Morfologické filtry jsou založeny na množinových operacích. Je-li f vstupní binární obraz, na jeho základě definujeme množinu A následujícím způsobem:

          Rovnice 5.15 (5.15)

          Množina A je vlastně jiným způsobem zápisu vstupního obrazu. Tuto množinu lze jednoduše převést opět na bitmapu. Kromě množiny A je zaveden ještě strukturní element B - podobně jako A i strukturní element B je množina dvojic B = {(x,y)}. Nakonec ještě definujeme posun A o vektor b = (xb, yb), ten označíme jako (A)b:

          Rovnice 5.16 (5.16)

          Na základě množiny A odpovídající vstupnímu obrazu a strukturního elementu B definujeme čtyři základní morfologické operace:

          Rovnice 5.17 (5.17)

          Pro účely předzpracování budou vhodné zejména closing a opening - tyto morfologické filtry na rozdíl od dilatace a eroze nerozšiřují ani nezužují objekty ve vstupním obraze. Closing se používá k vyhlazení hranic objektů a vyplnění drobných děr. Opening také vyhlazuje hranice objektů, navíc odstraňuje impulsní šum. Grafické znázornění čtyř základních morfologických operací je na obrázku 5.6.

Grafické znázornění morfologických filtrů (vstupní obraz).
vstupní obraz
Grafické znázornění morfologických filtrů (strukt. elem.).
strukt. elem.
Grafické znázornění morfologických filtrů (dilatace).
dilatace
Grafické znázornění morfologických filtrů (eroze).
eroze
Grafické znázornění morfologických filtrů (closing).
closing
Grafické znázornění morfologických filtrů (opening).
opening

Obrázek 5.6
Grafické znázornění morfologických filtrů.

          Morfologické filtry pracují pouze s binárními obrázky, jejich použití je tedy omezeno na jednu tiskovou barvu (či odstín). Při praktické implementaci tedy přibude ještě parametr filtru označující tiskovou barvu, nad kterou bude filtr pracovat.

          Na použití morfologických filtrů je třeba dát pozor v souvislosti s tiskovými rastry pro tisk světlejších odstínů barev. Protože jsou tyto rastry velmi jemné (obvykle jsou složeny z teček velikosti 2 - 3 pixelů), morfologické filtry dokážou narušit jejich strukturu natolik, že již nebude možné je detekovat. Proto by před morfologickou filtrací měla být nejprve provedena detekce tiskových rastrů.

          Praktické výsledky aplikace sady morfologických filtrů jsou zobrazeny na obrázku 5.7. Na výstup detekce filtrů z obrázku 5.5 byly použity pro barvy LtGR a MdGR operace closing a opening s kruhovým strukturním elementem velikosti 7 x 7 pixelů.

Výsledek aplikace sady morfologických filtrů (vstupní obrázek).
vstupní obrázek
Výsledek aplikace sady morfologických filtrů (po aplikaci sady morfologických filtrů).
po aplikaci sady morfologických filtrů

Obrázek 5.7
Výsledek aplikace sady morfologických filtrů.