CZ200989A3

CZ200989A3 - Nelineární obrazový filtr

Info

Publication number: CZ200989A3
Application number: CZ20090089A
Authority: CZ
Inventors: Sekanina@Lukáš; Vašícek@Zdenek
Original assignee: Vysoké ucení technické v Brne, Fakulta informacních technologií
Priority date: 2009-02-16
Filing date: 2009-02-16
Publication date: 2010-08-25
Also published as: CZ304181B6

Abstract

Vynález se týká nelineárního obrazového filtru pro potlacení impulsního šumu typu sul a pepr, který se skládá z obvodu (A) prefiltrace, za kterým jsou pripojeny ctyri paralelne pracující nelineární filtry (B1, B2, B3), jejichž výstup je spolecne s pixelem umísteným na pozici [x, y] filtrovaného obrazu a vedeným pres buffer (B5) následne spojen se selektorem (C).

Description

Nelineární obrazový filtr.

Oblast techniky

Vznález se týká nelineárního obrazového filtru pro potlačení impulsní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 operaci 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,y] výstupního obrazu je vypočtena pomoci obrazového hodu 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 filtraci 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é selíme r.a lineární a nelineární. Pro potlačení impulsní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 filrrů je sklon k rozmazávání ostrých přechodů, které jsou v obraze ve většině případů žádoucí, neboť určují detaily. Navržené řešení spadá do kategorie nelineárních obrazových filtrů pro potlačení impulsního šumu typu sůl a pepř.

Základní variantou nelineárního filtru, který je použitelný pro potlačeni impulsního šumu, je mediánový filtr. Mediánový filtr pracuje tak, že vypočte medián z obrazových bodů, které tvoři 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 impulsní šum vysoké intenzity. Jeho nevýhodou je vysoká cena při implementaci na čmpu Tabulka 1. Kvalitu filtrace jak u mediánového filtru, tak i a adaptivního mediánového filtru nejvíce ovlivňuje velikost filtrovacího okna. Tyto filtry se používají s filtračními okny 3x1, 5x5, 7x/ nebo 9x9 pixelů. Větší okno většinou znamená vyšší dosažitelnou kvalitu filtrace.

Při obvodové realizaci však zvětšováni 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í. Hjavnim problémem je ale skutečnost, že většina v dnešní době dostupných zařízeni produkujících video signál generuje obrazová data sériově, postupně bod po bodu, řádek po řádku. Filtry tento

μ.ř 1 .¾f.up musí respektovat a data na jedné straně konzumovat a na straně druhé opět generovat. Do filtru sice vstupuji 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ěni. Čí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 sekvenčním zpracování pixelů poskytnout. Jinými slovy, tyto filtry jsou vhodné pouze jako softwarové a sedy relativně pomalé řešení. Podrobněji, viz: Raymond H. Chán, Chung-Wa Ho, and Milá Nikolova: Salt-and-Pepper Noise Removal by Median-type Noise Detectors and Edge-preserving Regularization, IEEE Trangactions on Image Processing, 14 (2005), 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 vynálezu

Výše uvedené nedostatky jsou do značné míry odstraněny nelineárním obrazovým filtrem pro potlačení impulsního šumu typu „aul 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 impulsem 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 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šeni 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 filtru je 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í impulsní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. 1 je znázorněna struktura filtru B2. Na obr. 2 je znázorněná struktura filtru B3 . Na obr. 3 je znázorněna struktura filtru B4. Na obr. 4 je znázorněna architektura bloku selekce. Na obr. 5 je znázorněna řadicí síť. Na obr,6 je znázoir.ěn mediánový selektor. Na obr. 7 je znázorněn princip -''erii pixelů z paměti. Na obr. 8 je znázorněna závislost kvality filtrace na intenzitě šumu pro různé přístupy. Na obr. 9 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 pomoci 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 pomoci navrženého řešeni a na obr. 13 C4) vyfiltrovaný obraz P50 pomocí med, filtru 3x3.

Příklady provedeni technického řešeni

Příkladný synchronní nelineární obrazový filtr pro potlačení impulsního šumu typu „sůl a pepř, se skládá z obvodu A prefiltrace pro detekci bodů poškozených impulsem s hodnotou 255 a jejich invertováni 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áni 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 Ξ4 největší hodnota řazené posloupnosti, a z mediánového selektoru, který vypočte medián hodnot SO až S4.

Devítice obrazových bodů 10 až 18 získaná z filtrovaného uín-azu na souřadnici [x,y] vstupuje do bloku A prefiltrace, jehož úkolem je detekovat body poškozené impulsem s hodnotou 255 a tyuO invertovat na hodnotu 0. Tímto způsobem modifikovaných devět bodů paralelně vstupuje do čtyř nelineárních filtrů Bl až • · * * · * ϊ « « ·« v··· · r I · · «· ♦ · · I a a · a«a a ···♦· « «·· «« aa ··««a «·

B4 . Jednotlivé filtry BI až B4 jsou navrženy tak, aby byly schopny odfiltrovat určitou úroveň šumu a pro různé zašumění vstupní matice dávaly odlišný výsledek, je-li to možné. Výstupem každého filtru BI až B4 je jedna hodnota, která je odvozena z devítice IPO až IF8. Hodnota bodu na souřadici [x,y] (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 01 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 výstup hodnotu 0. V ostatních případech je výstupní hodnota C'.vna 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.

-8Vstupem filtrů BI až B4 obr. 4 až 7 je devítice IFO až IF8, kde vstupní hodnota 0 je považována za poškozený pixel. Filtry Dl 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 saturací tj. je-li hodnota a+b vetší než 255, je výsledek 255, >> 1 je bitový posun doprava tj . celočíselné děleni 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.

Nejdůležitějším blokem z hlediska vlivu na výslednou kvalitu získaného obrazu je 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ěli vstupních hodnot.

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

Řadicí siť 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.

-9Mediá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:

	pokud	= 0
	pokud	S₂ = 0
⁵ 3	pokud	5₍ = 0
	pokud	s₀ = o
A	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 pomoci banku filtrů - výběr výsledku. Hlavní inovace spočívá v konstrukci oanky filtrů a výběru výsledku. V bance paralelně pracují čtyři ruzne filtry navržené každý zvlášť pro odstranění impulsní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 filtru je v porovnání s mediánovým filtrem 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 impulsní šum typu „sůl-a-pepř různé intenzity bylo provedeno následovně.

Byla použita množina

• ·

Ž5 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 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 Na 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ši kvalitu filtrace vykazují mediánové filtry. Naopak nej lepší kvalita filtrace vychází pro Chánův filtr. Na obr. 9 ukazuje pízklady 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 ASIC nebo v programovatelném hradlovém poli FPGA. Pro ověřeni 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 velikosti okna 5x5, 7x7 a 9x9 pixelů. Implementační cena je uvedena obvyklým způsobem, tj. v počtu 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 filtru je výrazně nižší než cena dalších filtrů, «

které dosahuji srovnatelné kvality filtrace. Implementační cena je uvedena bez zahrnuti ceny onvodu pro načítání pixelů t j . pamětí FIFO apod. Celková implementační cena filtru je 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	adaptivní	medián 9x9	banka
5x5	7x7
3x3	5x5	7x7
FPGA slices max. frekvence	268	1506	4426	2024	6567	16395	984
[MHz]	305	305	305	303	298	295	305

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

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čeni impulsního šumu podle tohoto technického řešeni nalezne uplatněni především při restauraci nebo-li obnovení digitalizovaného obrazu značně poškozeného impulsním šumem, který je v obraze viditelný jako bilé nebo černé tečky typu sůl a pepř.

Claims

PATENTOVÉ NÁROKY

1. Nelineární obrazový filtr pro potlačeni impulsního šumu typu sůl a pepř, vyznačující se tím, že se skládá z obvodu A prefiltrace, 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 zapojen do synchronního zřetězeného provozu nebo do asynchronního obvodu.
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 různou funkcí pro odfiltrování určité úrovně šumu.
4. Nelineární obrazový filtr podle kteréhokoli z uvedených nároků, vyznačující se 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.