CZ20017U1

CZ20017U1 - Nelineární obrazový filtr

Info

Publication number: CZ20017U1
Application number: CZ200920871U
Authority: CZ
Inventors: Sekanina@Lukáš; Vašícek@Zdenek
Original assignee: Vysoké ucení technické v Brne,
Priority date: 2009-02-16
Filing date: 2009-02-16
Publication date: 2009-09-07

Description

Oblast techniky

Technické řešení se týká nelineárního obrazového filtru pro potlačení impulzního šumu typu sůl a pepř.

Dosavadní stav techniky

Při přenosu signálu mohou vznikat v důsledku poškozených senzorů, paměťových prvků apod. výpadky, které se v obraze projevuj í jako šum označovaný jako sůl-a-pepř.

Nejčastěji prováděnou operací v oblasti zpracování signálů je filtrace. Cílem filtrace je určitým způsobem vylepšit požadovanou vlastnost vstupního obrazu. Obr. 1 ukazuje obecný princip filtru, který využívá filtrační okno o velikosti 3x3 obrazové body, tj. pixely. Každá hodnota obrazového bodu na pozici [x, yj výstupního obrazu je vypočtena pomocí obrazového bodu na pozici [x, y] vstupního obrazu a jeho osmi sousedů. Stejný filtr je tedy postupně aplikován na všechny body obrazu. Důležité je, že filtr k výpočtu používá pouze lokální informaci, tj . 9 obrazových bodů. Tento koncept je výhodný pro obvodovou realizaci filtrů, kdy je vstupní obraz postupně, tedy sekvenčně, čten z paměti, popřípadě přímo z kamery, filtrován a dále zpracováván. Obvodová realizace má za úkol zajistit urychlení filtrace v porovnání s filtrací prováděnou vhodně vytvořeným programem běžícím na procesoru. Nutnost použiti globální informace, tj. velkého množství obrazových bodů pro výpočet nové hodnoty jednoho obrazového bodu, by výrazně prodražila celý proces filtrace realizovaný přímo na čipu.

Pro různé typy šumů byly navrženy různé typy filtrů, které dělíme na lineární a nelineární. Pro potlačení impulzního šumu se používají nelineární filtry. Lineární filtry vůbec nejsou schopny odstranit tento typ šumu. Hlavní nevýhodou lineárních filtrů je sklon k rozmazávání ostrých přechodů, které jsou v obraze ve většině případů žádoucí, neboť určuji detaily. Navržené řešení spadá do kategorie nelineárních obrazových filtrů pro potlačení impulzního šumu typu sůl a pepř.

Základní variantou nelineárního filtru, který je použitelný pro potlačení impulzního šumu, je mediánový filtr. Mediánový filtr pracuje tak, že vypočte medián z obrazových bodů, které tvoří filtrovací okno, a hodnota tohoto mediánu přímo představuje novou hodnotu obrazového pixelu ve výstupním obrazu. Mediánový filtr je však použitelný pouze pro nízkou intenzitu šumu. Mediánový filtr se v praxi používá nejčastěji, protože jeho implementace zabírá na čipu přiměřené množství logiky viz. Tabulka 1. Vylepšením mediánového filtru vzniká adaptivní mediánový filtr, který je schopen potlačit impulzní šum vysoké intenzity. Jeho nevýhodou je vysoká cena při implementaci na čipu Tabulka 1. Kvalitu filtrace jak u mediánového filtru, tak i u adaptivního mediánového filtru nejvíce ovlivňuje velikost filtrovacího okna. Tyto filtry se používají s filtračními okny 3x3, 5x5, 7x7 nebo 9x9 pixelů. Větší okno většinou znamená vyšší dosažitelnou kvalitu filtrace.

Při obvodové realizaci však zvětšování filtračního okna způsobuje mnoho problémů. Větší filtrační okno znamená, že je filtr složitější, zabírá více místa na čipu a má větší zpoždění. Hlavním problémem je ale skutečnost, že většina v dnešní době dostupných zařízení produkujících video signál generuje obrazová data sériově, postupně bod po bodu, řádek po řádku. Filtry tento přístup musí respektovat a data na jedné straně konzumovat a na straně druhé opět generovat. Do filtru sice vstupují postupně jednotlivé obrazové body, ovšem filtrace se provádí nad hodnotami filtračního okna, které se postupně posouvá po obraze. Posouvající se filtrační jádro je možné realizovat s využitím FIFO pamětí propojených do kaskády, viz obr. 11, kde M je šířka obrázku, v praxi např. 640 pixelů. Počet FIFO pamětí odpovídá počtu řádků filtrovacího okna. Každá paměť FIFO musí mít dostatečné množství položek, aby byla schopna pojmout celý řádek obrazu. Kromě pamětí je zapotřebí automat, který se stará o jejich správné plnění. Čím je filtrační okno větší, tím je potřeba větší paměť FIFO a tím více místa na čipu spotřebuje.

Dále existují i velmi sofistikované filtry, například Chánův filtr, které dosahují kvality filtrace lepší než adaptivní mediánové filtry, ale které je obvodově velmi nevýhodné implementovat a tedy akcelerovat, protože nepoužívají koncept lokálního filtračního okna. Pro výpočet každé hodnoty výstupního obrazu potřebují globální informaci, kterou není možné při rychlém sek5 venčním zpracování pixelů poskytnout. Jinými slovy, tyto filtry jsou vhodné pouze jako softwarové a tedy relativně pomalé řešení. Podrobněji, viz: Raytnond H. Chán. Chung-Wa Ho, and Milá Nikolova: Salt-and-Pepper Noise Removal by Median-type Noise Detectors and Edgepreserving Regularization, IEEE Transactions on Image Processing, 14 (2 005), 1479-1485; Hwang, H., Haddad, R.A. : New algorithms for adaptive medián filters, In: Tzou, K.-H., Koga,

T. (eds.) Proč. SPIE, Visual Communications and Image Processing' 91: Image Processing, vol. 1606, p. 400-407 (1991); Smith, J.L.: Implementing medián filters in XC4000E FPGAs, XCell, vol. 23, no. 1, p. 16,1996.

Podstata technického řešení

Výše uvedené nedostatky jsou do značné míry odstraněny nelineárním obrazovým filtrem pro potlačení impulzního šumu typu sůl a pepř, podle tohoto technického řešení. Jeho podstatou je to, že se skládá z obvodu A prefiltrace pro detekci bodů poškozených impulzem s hodnotou 255 a jejich invertování na hodnotu 0, ke kterému jsou paralelně připojeny čtyři nelineární filtry B1 až B4 propojené se selektorem C, ke kterému je připojen primární výstup filtru, přičemž mezi vstupem obvodu A prefiltrace a selektorem C je umístěn buffer B5.

Obvod A prefiltrace se skládá z osmibitového komparátoru a osmibitového multiplexoru. Jednotlivé filtry jsou v dále popsaném provedení synchronní nebo asynchronní implementace přirozeně vznikne odstraněním synchronizačních prvků a jsou určeny pro odfiltrování určité úrovně šumu. Podstatou řešení je, že každý z filtrů provádí výpočet jiným způsobem. Selektor C sestává z pětivstupové řadicí sítě pro seřazení vstupní hodnoty do stoupající posloupnosti tak, že na výstupu S0 je nejmenší hodnota a na výstupu S4 největší hodnota řazené posloupnosti a z mediánového selektoru.

Jedná se tedy o nelineární filtr vhodný pro aplikace pracující s obrazem kódovaným pomocí 256ti odstínů šedi, popřípadě pro barevný obraz, který má každou složku kódovanou na 8 bitech, ve kterých je kladen důraz na vysokou kvalitu filtrace, rychlost zpracování, nízkou cenu obvodu a nízký příkon obvodu. Navržený filtr vykazuje v porovnání s doposud známými řešeními nejlepší kvalitu filtrace vzhledem k ploše nutné pro jeho realizaci na čipu. Vstupem filtruje devítice obrazových bodů, tj. bod na souřadnici [x, y] a jeho osm okolních bodů, a výstupem je hodnota bodu na souřadnici [x, y], která je vypočtena navrženým obvodem. Hlavní inovace spočívá ve vytvořené obvodové architektuře filtru.

Nelineární obrazový filtr podle tohoto řešení má efektivnější plnění funkce, tj. stejnou nebo srovnatelnou kvalitu a intenzitu funkce tj. filtrovat, jako u adaptivního mediánového filtru při nižších vynaložených zdrojích, jako jsou materiály, energie, menší prostor, čas, práce, cena a podobně.

Jinak řečeno totéž, posuzovaná inovace/invence navrhuje efektivnější plnění funkce - filtrování a výrazně vyšší intenzitu a kvalitu funkce - filtrování vzhledem k mediánovému filtru při mírně vyšších vynaložených zdrojích. Proto má posuzovaný předmět v obou srovnáních vyšší hodnotu hodnota = funkce / (náklady + problémy).

Přehled obrázků na výkresech

Nelineární obrazový filtr pro potlačení impulzního šumu podle tohoto technického řešení bude podrobněji popsán na konkrétních příkladech provedení s pomocí přiložených výkresů, kde na obr. 1 je znázorněn stávající koncept filtrace obrazu s filtračním oknem 3x3 body. Na obr. 2 je znázorněna architektura navrženého filtru. Na obr. 3 je znázorněna architektura bloku prefiltrace. Na obr. 4 je znázorněna struktura filtru Bl. Na obr. 5 je znázorněna struktura filtru B2, Na obr. 6 je znázorněna struktura filtru B3. Na obr. 7 je znázorněna struktura filtru B4. Na obr. 8 je znáCZ 20017 Ul zorněna architektura bloku selekce. Na obr. 9 je znázorněna řadicí síť. Na obr. 10 je znázorněn mediánový selektor. Na obr. 11 je znázorněn princip čtení pixelů z paměti. Na obr. 12 je znázorněna závislost kvality filtrace na intenzitě šumu pro různé přístupy. Na obr. 13 jsou příklady poškozených a vyfiltrovaných obrazů, kde na obr. 13 A) je Q originální obraz. Na obr. 13 Bl) je P20 obraz Q poškozený 20 % šumem. Na obr. 13 B2) je vyfiltrovaný obraz P20 pomocí adapt, med, filtru 5x5. Na obr. 13 B3) je vyfiltrovaný obraz P20 pomocí navrženého řešení. Na obr. 13 B4) je vyfiltrovaný obraz P20 pomocí med, filtru 3x3. Na obr. 13 Cl) je P50 obraz Q poškozený 50 % šumem. Na obr. 13 C2) je vyfiltrovaný obraz P50 pomocí adapt. med. filtru 5x5. Na obr. 13 C3) je vyfiltrovaný obraz P50 pomocí navrženého řešení a na obr. 13 C4) vyfiltrovaný obraz P50 pomocí med. filtru 3x3.

Příklady provedení technického řešení

Příkladný synchronní nelineární obrazový filtr pro potlačení impulzního šumu typu sůl a pepř, se skládá z obvodu A prefiltrace pro detekci bodů poškozených impulzem s hodnotou 255 a jejich invertování na hodnotu 0, ke kterému jsou paralelně připojeny čtyři nelineární filtry Bl až B4 propojené se selektorem C, ke kterému je připojen primární výstup filtru, přičemž mezi vstupem obvodu A prefiltrace a selektorem C je umístěn buffer B5. Obvod A prefiltrace se skládá z osmibitového komparátoru a osmibitového multiplexoru. Jednotlivé filtry jsou synchronní, mají stejný počet stupňů a jsou určeny pro odfiltrování určité úrovně šumu. Selektor C sestává z pětivstupové řadící sítě pro seřazení vstupní hodnoty do stoupající posloupnosti tak, že na výstupu S0 je nejmenší hodnota a na výstupu S4 největší hodnota řazené posloupnosti, a z mediánového selektoru, který vypočte medián hodnot S0 až S4.

Devítice obrazových bodů 10 až 18 získaná z filtrovaného obrazu na souřadnici [x, y] vstupuje do bloku A prefiltrace, jehož úkolem je detekovat body poškozené impulzem s hodnotou 255 a tyto invertovat na hodnotu 0. Tímto způsobem modifikovaných devět bodů paralelně vstupuje do čtyř nelineárních filtrů Bl až B4. Jednotlivé filtry Bl až B4 jsou navrženy tak, aby byly schopny odfiltrovat určitou úroveň šumu a pro různé zašuměni vstupní matice dávaly odlišný výsledek, je-li to možné. Výstupem každého filtru Bl až B4 je jedna hodnota, která je odvozena z devítice IF0 až IF8. Hodnota bodu na souřadnici [x, yj (tj. 00) společně s hodnotami Ol až 04 vypočtenými pomocí sady filtrů vstupuje do selektoru C, který na základě určitého principu vybere z této pětice nejvhodnější hodnotu a předá ji na primární výstup filtru. Tato hodnota je výstupem celého filtru. Úkolem bufferu B5 je vyrovnat zpoždění jednotlivým filtrům tak, aby se hodnota 14 propagovala na vstup bloku selekce ve stejný okamžik jako hodnoty Ol až 04.

Architektura je navržena s ohledem na maximální možnou propustnost systému a lze ji provozovat v tzv. řetězeném provozu, kdy dostáváme v každém taktu synchronizačního signálu jednu hodnotu pro jedno filtrovací okno.

Úkolem bloku A prefiltrace je detekovat body s hodnotou 255 a jejich hodnotu invertovat na 0. Blokové schéma je uvedeno na obr. 3. Hodnota každého bodu filtrovacího okna je zpracována nezávisle pomocí jednoduché logiky, která porovná vstupující hodnotu s hodnotou 255 (OxFF) a v případě shody propustí na vystup hodnotu 0. V ostatních případech je výstupní hodnota rovna vstupní hodnotě. Smyslem tohoto bloku je nahradit dvě chybové hodnoty jedinou, která bude dále filtrována, a umožnit tím zjednodušení dalšího zpracování.

Hardwarová realizace spočívá v implementaci osmibitového komparátoru a osmibitového multiplexoru, pomocí kterého je řízena hodnota na výstupu IFn.

Vstupem filtrů Bl až B4 obr, 4 až 7 je devítice IFO až IF8, kde vstupní hodnota Oje považována za poškozený pixel. Filtry Bl až B4 byly navrženy s využitím optimalizačního algoritmu. Filtry jsou synchronní a mají stejné zpoždění, tj. stejný počet stupňů, což je důležité pro řetězený provoz. Jeden řádek výpočetních elementů filtru pracuje jako jeden stupeň řetězené linky. S každým taktem hodinového signálu se posouvají vypočítané hodnoty jednoho řádku elementů do dalšího řádku elementů. Význam symbolů je následující: + označuje součet dvou hodnot, +'je součet se

CZ 20017 Ul saturací tj. je-li hodnota a+b větší než 255, je výsledek 255, » 1 je bitový posun doprava tj. celočíselné dělení dvěma. SWP je prohození tj. horní čtyři bity výsledku odpovídají spodním čtyřem bitům hodnoty vstupu a, spodní čtyři bity horním čtyřem bitům hodnoty b. Komponenta bez popisu představuje registr nutný pro synchronizaci.

Nej důležitějším blokem z hlediska vlivu na výslednou kvalitu získaného obrazuje blok selekce. Tento blok sestává z pětivstupové řadicí sítě a selektoru pracujícího podle předpisu popsaného dále, který vybere na výstup jednu z svých pěti vstupních hodnot.

Hardwarová realizace řadicí sítě je uvedena na obr. 9. Mediánový selektor je uveden na obr. 10.

Řadicí síť je obvod, který seřadí vstupní hodnoty do neklesající posloupnosti tak, že na výstupu S0 je nejmenší hodnota a na výstupu S4 největší hodnota řazené posloupnosti. Řadicí síť je sestavena běžně známým způsobem. Blok D kopíruje vstupní hodnotu na výstup. Blok E zamění vstupní hodnoty tak, aby na prvním výstupu byla vždy menší ze dvou vstupních hodnot. V případě, že vstupní hodnoty jsou stejné, oba výstupy dávají též stejnou hodnotu.

Mediánový selektor je obvod, jenž má za úkol zvolit na výstup takovou hodnotu, která bude nejlépe aproximovat poškozený pixel. Obvod generuje výstupní hodnoty podle následujícího předpisu:

S,	pokud	*3	= 0
s,	pokud	s₂	= 0
s₃	pokud	S_i	= 0
S₂	pokud	S_o	= 0
Λ	jinak

Hardwarová realizace spočívá v zavedení sady komparátorů na nulovou hodnotu, multiplexoru, který přepíná na výstup jednu ze vstupních hodnot, a jednoduché kombinační logiky (f), která na základě stavu jednotlivých komparátorů generuje řídicí signál pro multiplexor.

Navržený filtr je nelineární a používá malé filtrační okno o velikosti 3x3 pixely. Je založen na použití třístupňové architektury: předzpracování - paralelní filtrace pomocí banku filtrů - výběr výsledku. Hlavní inovace spočívá v konstrukci banky filtrů a výběru výsledku. V bance paralelně pracují čtyři různé filtry navržené každý zvlášť pro odstranění impulzního šumu. Každý z filtrů, pokud by byl použit samostatně, dosahuje přibližně kvality mediánového filtru s filtračním oknem 3x3. Implementační cena jednoho filtruje v porovnání s mediánovým flitrem v průměru o 25 % nižší. Jsou-li však filtry banky spojeny vhodným výběrovým obvodem, je získán výstup srovnatelný s obvodově mnohem složitějším adaptivním mediánovým filtrem. Jedná se tedy o obvod, který by mohl nahradit existující implementace filtrů v čipech. Za relativně malý nárůst plochy na čipu je možné získat podstatně kvalitnější filtraci.

Ověření schopnosti potlačit impulzní šum typu sůl-a-pepř různé intenzity bylo provedeno následovně. Byla použita množina 25 různých testovacích obrazů, přičemž každý z obrazů existuje v 15 verzích, které se liší intenzitou aplikovaného šumu od 5 % do 75 %. Navržený filtr byl použit k potlačení Šumu ve všech verzích všech obrazů. Kvalita filtrace je vypočtena standardním způsobem jako průměrný odstup signálu od šumu (PSNR) pro každou intenzitu šumu. Výsledné hodnoty PSNR jsou uvedeny na obr. 8 - navržený filtr je označen jako banka zelená křivka. Stejným způsobem a na stejné množině testovacích obrazů byla vyhodnocena kvalita filtrace pro mediánový filtr s velikostí filtračního okna 3x3, 5x5 a 7x7 pixelů, adaptivní mediánový filtr s velikostí okna 5x5, 7x7 a 9x9 pixelů a sofistikovaný Chánův filtr. Z obr. 8 je patrné, že navržený filtr dosahuje pro intenzitu šumu do 50 % lepšího odstupu signálu od šumu než mediánový filtr a adaptivní mediánový filtr a to nezávisle na velikosti filtračního okna. Pro intenzitu šumu vyšší než 50 % je navržený filtr nepatrně horší než adaptivní mediánový filtr s velikostí filtračního okna 7x7 nebo 9x9 pixelů. Nejhorší kvalitu filtrace vykazují mediánové filtry. Naopak nejlepší kvalita filtrace vychází pro Chánův filtr. Na obr. 9 ukazuje příklady obrázků z testovací množiny a výsledky filtrace.

Navržený filtr může být implementován buď jako aplikačně specifický integrovaný obvod AS1C nebo v programovatelném hradlovém poli FPGA. Pro ověření bylo zvolena implementace v

FPGA Xilinx Virtex XC2VP50. Tabulka 1 srovnává implementační cenu a maximální pracovní frekvenci pro navržený filtr, mediánový filtr s velikostí filtračního okna 3x3, 5x5 a 7x7 pixelů a adaptivní mediánový filtr s velikostí okna 5x5, 7x7 a 9x9 pixelů. Implementační cena je uvedena obvyklým způsobem, tj. v poctu tzv. slice, což je elementární komponenta FPGA. Nejnižší cenu má mediánový filtr s filtračním oknem 3x3 pixely. Tento filtr však nefiltruje příliš kvalitně viz na ίο obr. 8. Cena navrženého filtruje výrazně nižší než cena dalších filtrů, které dosahují srovnatelné kvality filtrace. Implementační cena je uvedena bez zahrnutí ceny obvodu pro načítání pixelů tj. pamětí FIFO apod. Celková implementační cena filtruje potom dána cenou uvedenou v Tabulka 1 a cenou za implementaci obvodu pro načítaní pixelů. Odhad celkové ceny je proveden v Tabulka 2. V případě implementace obvodu jako ASIC dosáhneme obdobné poměry ploch, které budou zabírat jednotlivé filtry na čipu, jako při provedené implementaci v FPGA.

Tabulka 1: Cena implementace vyjádřená v počtu FPGA slices

parametry	medián	7x7	adaptivní	medián 9x9	banka
3x3	5x5
5x5	7x7
FPGA slices	268	1506	4426	2024	6567	16395	984
max. frekvence
[MHz]	305	305	305	303	298	295	305

Tabulka 2: Cena implementace včetně FIFO (pro obraz o šířce 640 pixelů)

i parametry	medián	adaptivní medián	banka
3x3	5x5	7x7	5x5	7x7 9x9
FPGA slices	2188	4706	8906	5224	11047 \|22155	2904

Průmyslová využitelnost

Nelineární obrazový filtr pro potlačení impulzního šumu podle tohoto technického řešení nalezne uplatnění především při restauraci nebo-li obnovení digitalizovaného obrazu značně poškozeného impulzním šumem, který je v obraze viditelný jako bílé nebo černé tečky typu sůl a pepř.

Claims

NÁROKY NA OCHRANU

25 1. Nelineární obrazový filtr pro potlačení impulzního šumu typu sůl a pepř, vyznačující se tím, že se skládá z obvodu A prefíltrace, za kterým jsou připojeny čtyři paralelně pracující nelineární filtry B1 až B4, jejichž výstup je společně s pixelem umístěným na pozici [x, y] filtrovaného obrazu a vedeným přes buffer B5 následně spojen se selektorem C,
2. Nelineární obrazový filtr podle nároku 1, vyznačující se tím, že je zapojen do

30 synchronního zřetězeného provozu nebo do asynchronního obvodu.

CZ 20017 Ul
3. Nelineární obrazový filtr podle nároku 1 nebo 2, vyznačující se tím, že jednotlivé filtry B1 až B4 jsou opatřeny navzájem různou funkcí pro odfiltrování nastavené úrovně šumu.
4. Nelineární obrazový filtr podle kteréhokoli z uvedených nároků, vyznačující se 5 t í m, že selektor C sestává z pětivstupové řadicí sítě, za kterou je připojen obvod pro výběr výstupní hodnoty.

6 výkresů

CZ 20017 Ul