Lineární filtrování obrazu. Grafické filtry založené na twist matrix. Filtrování pomocí funkce imfilter

Přenos informací v systémech řízení informací lze provádět pomocí spojitých i diskrétních signálů. Použití diskrétních signálů se v některých případech ukazuje jako výhodnější, protože diskrétní signály jsou méně náchylné ke zkreslení během přenosu a tato zkreslení se snáze detekují.

A co je nejdůležitější, diskrétní signály jsou pohodlnější pro použití a zpracování digitálními zařízeními. Na druhou stranu většina primárních signálů přijímaných ze senzorů je spojitých, což vyvolává problém efektivní konverze spojitých signálů na diskrétní a naopak. Proces (procedura) převodu spojité fyzikální veličiny na diskrétní se nazývá kvantování.

Typy kvantování

Kvantování podle úrovně – v tomto případě je jím nahrazena spojitá funkce popisující primární signál samostatné hodnoty, oddělené od sebe určitým konečným intervalem (úrovní). V souladu s tím je okamžitá hodnota funkce nahrazena jejími nejbližšími diskrétními hodnotami a je volána kvantizační úroveň. Interval mezi dvěma sousedními úrovněmi se nazývá krok kvantování.

Krok kvantování může být buď konstantní ( jednotné kvantování ) a proměnné ( nerovnoměrné kvantování ).

Přesnost převodu spojitého signálu na diskrétní závisí na velikosti kvantizačního kroku. Tato přesnost se posuzuje nesouladem mezi skutečnou hodnotou funkce a kvantovanou hodnotou. Velikost této nesrovnalosti se nazývá kvantizační chyba neboli „šum“.

Při přenosu signálu přes komunikační kanál může být tento signál ovlivněn určitým druhem rušení, které tento primární signál zkresluje. Pokud je známa maximální hodnota tohoto rušení (), můžete zvolit kvantovací krok q, který překračuje , tedy q>, a poté znovu kvantovat signál na přijímací straně, pak můžete přijímaný signál zbavit rušení.

Re-kvantizace tedy umožňuje obnovit signál zkreslený rušením a eliminovat hromadění vlivu rušení.

Kvantování času (vzorkování) – v tomto případě je spojitá funkce x(t) nahrazena jejími jednotlivými hodnotami získanými v pevně stanovených časech.

Vzorky hodnot primárního signálu se provádějí v pevných bodech v čase - kvantizační krok nebo krok vzorkování. Čím menší je zvolený interval, tím přesněji lze funkci vnímat na přijímacím konci. Na druhou stranu, pokud je krok vzorkování příliš malý, rychlost přenosu dat klesá a požadavky na šířku pásma komunikačního kanálu se také zvyšují:

Pokud je krok vzorkování příliš velký, sníží se přesnost reprodukce funkce při příjmu.

Přednáška č. 5

V některých případech se ukazuje jako vhodné použít smíšený typ kvantování, tedy kvantování podle úrovně a času. V tomto případě je signál předem kvantován podle úrovně a výsledné kvantované hodnoty jsou vzorkovány v určených časových intervalech. V tomto případě je chyba takového kvantování určena geometrickou střední hodnotou kvantování podle úrovně a kvantování podle času

V některých případech se používají složitější typy kvantování:

Většinu zpracování obrazu lze provést bez opakování statistické analýzy popsané v předchozí části pro každý nový snímek. Omezené množství apriorních informací se ukazuje jako zcela dostačující. Řekněme, že známe matici společných výskytů pro „ideální“ obrázek a chceme zlepšit kvalitu zašuměné verze tohoto obrázku. Li největší prvky matice jsou umístěny na hlavní diagonále nebo v její blízkosti, to znamená, že většina pixelů má stejnou barvu jako sousední pixely. Pokud chceme histogram takového snímku vyrovnat, pak, jak je uvedeno v kap. 3.2, je vhodné použít pravidlo 3. Pokud je potřeba eliminovat šum, pak nahrazením hodnoty každého pixelu zašuměného obrázku nějakým váženým součtem hodnot sousedních pixelů snížíte variabilitu hodnot sousedních pixelů a získáme obrázek bližší originálu (viz příklad 3.5). Dostáváme se tedy ke vztahu charakterizujícímu vztah mezi původním obrázkem a filtrovaným obrázkem:

Proces, který provádí tuto operaci, se nazývá lineární filtr, konkrétně filtr klouzavého průměru, protože nahrazuje hodnotu každého pixelu nějakým průměrem hodnot sousedních prvků. Pokud se váhová funkce v rámci obrázku nemění a nezávisí na souřadnicích x, y, pak lze rovnici (3.2) přepsat jako následující formulář:

Tento proces se nazývá prostorově invariantní filtr. Tyto filtry jsou široce používány při zpracování časových signálů, ale vhodnost jejich použití při zpracování obrazu není zřejmá. Rovnice (3.3) je zjednodušena při zápisu pomocí Fourierovy transformace. Může být zobrazen (viz kap.

Výsledkem použití takového filtru je potlačení některých frekvencí a posílení jiných v závislosti na H(i,

Příklad 3.5. Pokud potřebujete vyčistit obraz od vysokofrekvenčního šumu, pak k provedení takového vyhlazení můžete použít následující typ funkce

Výsledek použití filtru lze posoudit porovnáním rozdílů v hodnotách sousedních pixelů před a po filtraci, ukazují to zejména nejjednodušší výpočty

Označíme-li maximem absolutního rozdílu hodnot sousedních pixelů původního obrázku a odpovídajícím rozdílem pixelů filtrovaného obrázku, pak z rovnice (36) vyplývá

těch. Je zřejmé, že tento rozdíl nemůže narůstat pouze v případech, kdy maximální rozdíl hodnot pixelů je několikanásobně větší než maximální rozdíl hodnot pro dvojici pixelů, tzn. když je nějaká lineární funkce jeho argumentů V opačném případě se zadaný rozdíl sníží a oblasti obrazu získají homogennější charakter Protože se obvykle použití takového jednoduchého filtru ukáže jako nedostatečné k odstranění šumu uchýlit se k použití filtru vyššího řádu Jednou z možných implementací takového filtru je nuda jednoduchý filtr a jeho opakovanou aplikací na obraz Obr. 39 a 310 ukazují výsledky filtrování na Obr. 3.10a ukazuje původní obrázek získaný z obrázku zobrazeného na obr. 3 9, superponováním gaussovského bílého šumu na druhý, na obr. Obrázek 3.10 b ukazuje výsledky osminásobné aplikace filtru specifikovaného rovnicí (3 5). Není těžké vidět, že tento proces vede nejen k odstranění vysokofrekvenčního šumu, ale také způsobuje rozmazání hran. obraz

Rýže. 3.9 (viz sken) Původní obrázek použitý pro...

Pokud totiž aplikujeme rovnici (3.6) na jasně definovaný okraj obrázku

ukazuje se, že

Jinými slovy, rozdíl v hodnotách sousedních pixelů byl poloviční a to přirozeně vedlo ke snížení kontrastu obrazu

Výsledky použití tohoto filtru lze také posoudit uvažováním Fourierovy transformace funkce

Použijeme rovnici (34)

Tento výraz lze zjednodušit pomocí identity

a poté provedením nejjednodušších goniometrických transformací má výraz (3 8) ve výsledku následující podobu

DIGITÁLNÍ ZPRACOVÁNÍ SIGNÁLY

Téma 17. ZPRACOVÁNÍ OBRÁZKU

Není nic, na co by se lidská představivost odvážila.

Titus Lucretius. římský filozof a básník. Já století př.n.l E.

Představivost je dobrá věc. Ale vytáhnout bezdomovce ze sklepa, umýt ho, udělat z něj Apollo, zabalit do krabičky od sirek a poslat kamarádovi e-mail dobrý grafický program udělá lépe.

Anatoly Pyshmintsev, novosibirský geofyzik Uralské školy. XX století

Zavedení.

1. Základní pojmy. Grafické znázornění obrázky. Reprezentace barev v počítačové grafice. Barva RGB model. Barevný systém CIE XYZ.

2. Geometrické transformace rastrových obrázků. Oblasti a fáze transformace. Odběr vzorků. Interpolační řada pro rekonstrukci dvourozměrného signálu. Frekvenční zkreslení obrázky a jejich odstranění. Převzorkování obrázků.

3. Filtrování obrazu. Lineární filtry. Anti-aliasingové filtry. Filtry pro zvýšení kontrastu. Rozdílové filtry. Dvourozměrná cyklická konvoluce. Nelineární filtry. Prahová filtrace. Střední filtrování. Extrémní filtry.

4. Komprese obrazu. Algoritmy kódování délky opakování (RLE). Slovníkové algoritmy. Statistické kódovací algoritmy. Ztrátová komprese obrazu. Odhad ztráty v obrazech. Fourierova transformace. Vlnková transformace.

ZAVEDENÍ

Rozsah výzkumu v oblasti digitálního zobrazování rychle roste. To je dáno tím, že zpracování obrazu je zpracováním vícerozměrných signálů a většina signálů v reálném světě je vícerozměrných.

Obraz v matematickém vyjádření je dvourozměrný signál, který nese obrovské množství informací. Barevný obrázek 500 × 500 prvků je pole několika stovek tisíc bajtů. Takové informace lze zpracovat pouze racionální organizací výpočtů. Pro specifické úlohy zpracování obrazu můžete použít efektivní způsoby zpracování s ohledem na vlastnosti a omezení tohoto konkrétní úkol. Ale pokud mluvíme o zpracování obrazu k vyřešení široké třídy problémů, pak je nutné vyzdvihnout sadu standardní operace, ze kterého můžete sestavit algoritmy pro řešení libovolných problémů. Patří mezi ně lineární transformace, dvourozměrná konvoluce a dvourozměrné diskrétní Fourierovy transformace.

Ale nelineární transformace jsou také široce používány při zpracování obrazu. Zvláštností obrázků je, že jednotlivé prvky obrázku jsou v určitém spojení se sousedními prvky. Většina algoritmů konverze obrazu je proto lokální povahy, tj. zpracovávají obrazy skupinami prvků nacházejících se v blízkosti daného. Lineární transformace splňují vlastnost lokality a umožňují konstrukci algoritmů výpočetní náročnost což málo závisí na velikosti okolní oblasti. Stejné vlastnosti jsou vyžadovány pro nelineární transformace obrazu. Třída takových transformací zahrnuje algoritmy nazývané algoritmy filtrování hodnocení založené na výpočtu lokální statistiky hodnocení obrázků. Při výpočtu statistik pořadí a jejich odvozenin jsou možná zjednodušení kvůli informační redundanci obrázků. Většina slavný algoritmus tato třída je algoritmus střední filtrování. Mezi další příklady algoritmů hodnocení patří algoritmy extrémního filtrování, které nahrazují analyzovaný prvek obrazu maximem nebo minimem v okolí. Další vlastností rank algoritmů je lokální přizpůsobení charakteristikám zpracovávaného obrazu a možnost jejich využití nejen pro vyhlazování a odstranění šumu, ale také pro zvýraznění prvků v automatickém rozpoznávání obrazu.

Při zpracování obrazu se široce používají metody pro zpracování jednorozměrných signálů, pokud je lze zobecnit na vícerozměrné signály. Zároveň je nutné vzít v úvahu, že matematické metody pro popis vícerozměrných systémů nejsou úplné. Vícerozměrné systémy mít velký počet stupně volnosti a jejich design získává flexibilitu, která není vlastní jednorozměrným systémům. Současně nelze vícerozměrné polynomy rozložit na prvočinitele, což komplikuje analýzu a syntézu vícerozměrných systémů.

17.1. Základní pojmy

Grafické znázornění obrázků. Pro prezentaci grafických informací na dvourozměrné rovině (obrazovce monitoru) se používají dva přístupy: rastrový a vektorový.

U vektorového přístupu je grafická informace popisována jako soubor abstraktních geometrických objektů - přímky, segmenty, křivky, obdélníky atd. Vektorový popis předpokládá apriorní znalost struktury obrazu.

Rastrová grafika pracuje s libovolnými obrázky ve formě rastrů. Rastr je popis obrázku v rovině jeho rozdělením (vzorkováním) na identické prvky na pravidelné mřížce a přiřazením každému prvku vlastní barvu a případné další atributy. Nejjednodušší rastr je obdélníkový, nejekonomičtější z hlediska počtu vzorků pro přenos obrázků je šestiúhelníkový. Z matematického hlediska je rastr po částech konstantní aproximace v rovině kontinuální funkce obrázky.

Prvek rastru se nazývá pixel. Standardní identifikace pixelů:

f(i, j) = (A(i, j), C(i, j)), (17.1.1)

kde A(i, j) Ì R2 je plocha pixelu, C(i, j) Î C je atribut pixelu (obvykle barva). Nejčastěji se používají dva typy atributů:

C(i, j) = I(i, j) - intenzita pixelu (jas);

C(i, j) = (R(i, j), G(i, j), B(i, j)) - atributy barev v barevném modelu RGB.

V matricové formě:

Mij ​​​​= (Aij, Cij).

Při odběru vzorků nepřetržité obrazy hodnoty Aij lze definovat dvěma způsoby, buď jako hodnoty bodů Aij = (i, j), pro které jsou definovány atributy Cij, nebo jako hodnoty čtverců Aij = ( i, i+1) × (j, j+1) nebo jakýkoli jiný tvar, s určením Cij na základě průměrných hodnot v rámci tohoto tvaru (obr. 17.1.1).

V praxi jsou zpravidla X a Y omezené množiny nezáporných celých čísel čtvercového nebo obdélníkového rastru s poměrem šířky rastru k výšce, který se zapisuje ve tvaru např. "4:3" .

Reprezentace barev v počítačové grafice. Pojem barvy je založen na vnímání elektromagnetických vln lidskýma očima určitý rozsah frekvence Denní světlo, které vnímáme, má vlnové délky λ od 400 nm (fialová) do 700 nm (červená). Popis světelný tok může sloužit jako jeho spektrální funkce I(λ). Světlo se nazývá monochromatické, pokud má jeho spektrum pouze jednu konkrétní vlnovou délku.

Na sítnici oka jsou dva typy receptorů: tyčinky a čípky. Spektrální citlivost tyčinek (obr. 17.1.2) je přímo úměrná jasu dopadajícího světla. Čípky jsou rozděleny do tří typů, z nichž každý má určitou citlivost v omezených rozsazích s maximy v červené, zelené a modré barvě a ve tmě svou citlivost prudce ztrácí. Oční náchylnost k modrá barva výrazně nižší než ostatní dva. Důležitá vlastnost Lidské vnímání světla je lineární při přidávání barev s různými vlnovými délkami.

RGB barevný model (Red, Green, Blue - červená, zelená, modrá) v počítačové grafice je v současnosti nejrozšířenější. V tomto modelu je spektrální funkce reprezentována jako součet křivek citlivosti pro každý typ kužele s nezápornými váhovými koeficienty (normalizovanými od 0 do 1), které jsou označeny R, G a B. Model je charakterizován vlastností aditiv pro získání nových barev. Například kódování spektrálních funkcí:

Černá: fčerná = 0, (R, G, B) = (0,0,0);

Fialová barva ffialová = fred + fblue, (R, G, B) = (1,0,1);

Bílá fbílá = fred + fgreen + fblue, (R, G, B) = (1,1,1).

Trojrozměrný barevný prostor modelu RGB je znázorněn na Obr. 17.1.3. Vzhledem ke zvláštnostem vnímání světla receptory ne všechny barvy viditelné pro lidi, jsou v tomto modelu reprezentativní. Podíl barev, které jsou reprodukovány, je však výrazně větší než podíl, který není v tomto modelu zastoupen.

Barevný systém CIE XYZ. Mezinárodní standard reprezentace barev CIE (CIE - Commission Internationale de l'Eclairage) byl přijat v roce 1931 Mezinárodní komisí pro osvětlení základní funkceρX(λ), ρY(λ), ρZ(λ), v závislosti na vlnové délce, jejichž lineární kombinace s nezápornými koeficienty (X, Y a Z) umožňují získat všechny barvy viditelné pro člověka. Tyto funkce berou v úvahu relativní vnímání intenzity světla očními receptory. V trojrozměrném prostoru tvoří barevný systém CIE kužel v prvním kvadrantu a používá se k zobrazení vysoce kvalitních barevných obrázků.

17.2. Geometrické transformace rastrových obrázků

Oblasti a fáze transformace. Obrázky lze rozdělit na texturu a detaily. V obrázcích textur nesou všechny vzorky (prvky) informaci (obrázek na televizní obrazovce). Detailní obrázek je takový, ve kterém můžete identifikovat rušivé objekty, pozadí a užitečné objekty.

Existují tři hlavní skupiny algoritmů pro zpracování obrazu na počítačích:

1. Primární (předběžné) zpracování snímků za účelem restaurování, čištění náhodný hluk, zlepšení kvality, korekce geometrického zkreslení optické systémy(rozostření, aberace atd.).

2. Popis obrázků, rozpoznávání vzorů. Provádí se pro stanovení parametrů detailů obrazu a zahrnuje: nalezení oblastí obrazu, které jsou jednotné v úrovni osvětlení a barvy, identifikaci znaků tvaru obrazů, určení souřadnic speciálních bodů objektů atd.

3. Efektivní kódování pro snížení objemu přenosu a úložiště.

Většina metod předběžného zpracování je založena na použití lineárních prostorově invariantních (SPI) filtrů. Lineární algoritmy jsou prováděny pomocí dvourozměrných analogů jednorozměrných FIR a IIR filtrů. Lze je využít například při implementaci filtrů pro snížení šumu v obrazech.

FIR filtry jsou implementovány pomocí konvoluční metody. Výhody 2D FIR filtrů jsou přehlednost, jednoduchost a absolutní robustnost. IIR filtry jsou implementovány pomocí diferenčních rovnic a z-transformací. Jsou rychlejší než filtry FIR, ale mohou být nestabilní. Syntéza dvourozměrných IIR filtrů se liší od syntézy jednorozměrných, protože pro dvourozměrná funkce Není možné jednoznačně identifikovat póly.

K obnově obrázků a zlepšení jejich kvality mohou být také vyžadovány nelineární metody. Například pro potlačení šumu a zároveň zachování obrysové části snímků je nutné použít nelineární nebo lineární prostorově neinvariantní (SPNI) filtry, které jsou implementovány rank algoritmy. Všechny rank nelineární filtry jsou založeny na rychlých algoritmech pro výpočet lokálních histogramů.

Jednou z takových metod je mediánové filtrování. Použití středních filtrů je účinné pro potlačení určitých typů šumu a periodického rušení bez současného zkreslení signálu, například pro potlačení shluků šumu, včetně vynechaných linek. Metodu lze také použít k řešení problémů souvisejících s rozpoznáváním, například k identifikaci tenkých čar a malých izolovaných objektů.

Algoritmy pro popis obrazu a rozpoznávání vzorů jsou obvykle nelineární a heuristické povahy. Vlastnosti objektů jsou obvykle plocha obrazu předmětu, obvod obrysu obrazu, poměr plochy ke čtverci obvodu obrazu. Tvar předmětu lze charakterizovat poloměrem kružnice vepsané do obrazu nebo popsaného kolem obrazu předmětu, délkou vektoru minimálního a maximálního poloměru od „těžiště“ obrazu.

Odběr vzorků. Transformace obrazu v počítači a ukládání zpracovávaných dat jsou prováděny v diskrétní podobě. Přijímat diskrétní reprezentace Vzorkování je aplikováno ze spojitých analogových obrazů reálného světa. V praxi se provádí vstupními zařízeními (digitální fotoaparát, skener nebo jiná). Pro vizuální vnímání zpracovaných obrazů na výstupních zařízeních (displej, plotr atd.) je analogový obraz rekonstruován z jeho vzorkované reprezentace.

V nejjednodušším případě černobílé obrázky máme dvourozměrné pole sa(x, y). Pro barevné obrázky v modelu RGB, s přihlédnutím k vlastnosti aditivity při přidávání barev, lze každou vrstvu R, G a B také považovat a zpracovat jako dvourozměrné pole s následným sečtením výsledků.

Ze způsobů, jak zobecnit jednorozměrnou periodickou diskretizaci na dvourozměrný případ, je nejjednodušší periodická diskretizace v pravoúhlých souřadnicích:

s(n, m) = sa(nDx, mDy),

kde Dx a Dy jsou horizontální a vertikální intervaly vzorkování dvourozměrného spojitého signálu sa(x, y) se spojitými souřadnicemi x a y. Níže jsou hodnoty Dx a Dy, jako v jednorozměrném případě, brány rovny 1.

Vzorkování dvourozměrného signálu také vede k periodizaci jeho spektra a naopak. Podmínka informační ekvivalence souřadnicových a frekvenčních reprezentací diskrétního signálu je rovněž zachována při stejném počtu vzorkovacích bodů v hlavních rozsazích signálu. Pro obdélníkové vzorkování jsou dopředné a inverzní Fourierovy transformace dány vztahem:

S(k, l) =s(n, m) exp(-jn2pk/N-jm2pl/M), (17.2.1)

S(k, l) =exp(-jn2pk/N) s(n, m) exp(-jm2pl/M), (17.2.1")

s(n, m) =S(k, l) exp(-jn2pk/N-jm2pl/M). (17.2.2)

s(n, m) =exp(-jn2pk/N) S(k, l) exp(-jm2pl/M). (17,2,2")

Rýže. 17.2.1. Periodizace spektra.

Tyto výrazy ukazují, že dvourozměrný DFT z pravoúhlého vzorkovacího rastru dat lze vypočítat pomocí jednorozměrných sekvenčních DFT. Druhé součty výrazů (17.2.1") a (17.2.2") jsou jednorozměrné DFT úseků funkcí s(n, m) a S(k, l) podél čar n a k, resp. první z nich jsou jednorozměrné DFT vypočítaných funkcí v řezech po ma l. Jinými slovy, počáteční matice hodnot s(n, m) a S(k, l) jsou nejprve přepočteny na střední matice s DFT v řádcích (nebo ve sloupcích) a mezilehlé matice na konečné matice s DFT ve sloupcích. (resp. v řádcích).

Aby se periodické opakování spektra (obr. 17.2.1) způsobené vzorkováním analogový signál s frekvencí Fx=1/Dx a Fy=1/Dy, nemění spektrum v hlavním frekvenčním rozsahu (vzhledem ke spektru původního analogového signálu), je nutné a dostatečné, aby maximální frekvenční složky fmax ve spektru byly analogového signálu jak ve vedení, tak podél sloupců, nepřekročil Nyquistův kmitočet (fmax. x £ fN = Fx/2, fmax. y £ fM = Fy/2). To znamená, že vzorkovací frekvence signálu musí být alespoň dvakrát vyšší než maximální frekvenční složka ve spektru signálu:

Fx ³ 2fmax. x, Fy ³ 2fmax. y, (17.2.3)

což zajišťuje, že spektrální funkce dosahují nulových hodnot na koncích hlavního rozsahu spektra.

Interpolační řada pro rekonstrukci dvourozměrného signálu. Pokud je spojitý signál sa(x, y) signálem s omezeným spektrem a periody vzorkování jsou zvoleny dostatečně malé, aby se spektra sousedních period nepřekrývala:

Sa(Wx, Wy) = 0 pro |Wx|p/Dx, |Wy|p/Dx,

pak, jako v jednorozměrném případě, signál sa(x, y) může být rekonstruován z diskrétního signálu pomocí dvourozměrného analogu řady Kotelnikov-Shannon:

sa(x, y) = Sn Sm s(n, m) . (17.2.4)

Frekvenční zkreslení obrazu a jejich eliminace. Lze také vzorkovat signál s neomezeným spektrem, ale v tomto případě dochází k aliasingu spekter v sousedních periodách a vysoké frekvence vyšší než Nyquistova frekvence budou „maskovány“, jako v jednorozměrném případě, pod nízkými frekvencemi. hlavního období. Efekt „odrazu“ od hranic období dává ještě komplexnější obraz díky interferenci frekvencí odrážených podél různých souřadnic. Podobný efekt, známý jako aliasing, bude také pozorován, když je vzorkovací frekvence obrazu nedostatečná. Tento efekt lze pozorovat zvláště zřetelně u ostrých kontrastních změn jasu.

K boji proti takovým jevům se používá předfiltrování (antialiasing) - předběžná konvoluce analogového obrazu s funkcí váhového filtru, která odřízne vysokofrekvenční složky, které mohou vést k aliasingu. Ve dvourozměrném případě je filtrování popsáno následovně:

z(x, y) = h(x", y") ③③ s(x-x", y-y"). (17.2.5)

Je třeba poznamenat, že analogové obrázky existují pouze v optické oblasti, například ve formě světelného displeje na obrazovce, fotografickém papíru nebo filmu, ale nemohou existovat v paměti počítače. Fyzická implementace předfiltrace je tedy možná pouze při registraci obrazu jeho rozostřením, které se zpravidla nepoužívá. Primární informace by měly být vždy zaznamenány s maximální úplností a přesností a očištění primárních informací od zbytečných detailů a redundance je záležitostí následného zpracování dat. Proto ve vztahu k rovnici 17.2.5 může dvourozměrná předfiltrace ve své praktické implementaci představovat pouze filtrování obrazů vzorkovaných s velkou rezervou v hlavním frekvenční rozsah(s nadměrným rozlišením) a obvykle se používá při převzorkování na větší krok, například při kompresi obrázků. Předfiltrování lze také zabudovat do algoritmů pro konstrukci obrazu.

Na Obr. 17.2.3 a níže, Tabulka 17.2.1 ukazuje příklady nejběžnějších jednorozměrných filtrů pro vyhlazování. Mohou být také implementovány ve formě analogových filtrů a použity například při přenosu televizních obrazových řádků v analogové formě přes rádiové kanály (horizontální antialiasing). V zásadě lze podobnou operaci provést napříč sloupci (double - image) a po sečtení snímku se provede kompletní antialiasingová operace, tato metoda však patří spíše do oblasti speciálního vědeckého výzkumu.

Tabulka 17.2.1.

Základní váhové funkce

Časové okno	Funkce váhy	Fourierův obraz
přírodní (P)	P(t) = 1, |t|£t; П(t) = 0, |t|>t	П(w) = 2t sinc
Bartlett (D)		B(w) = tsinc2(hmotn./2).
Henninga, Ganna	p(t) = 0,5	0,5P(š)+0,25P(š+p/t)+0,25P(š-p/t)
Lemování	p(t) = 0,54+0,46 cos(pt/t)	0,54P(š)+0,23P(š+p/t)+0,23P(š-p/t)
Carre (2. okno)	p(t) = b(t) sinc(pt/t)	t·B(w)*П(w), П(w) = 1 pro |w|
Laplaceova-Gaussova	p(t) = exp[-b2(t/t)2/2]	[(t/b) exp(-t2w2/(2b2))] ③ П(w)

Dvourozměrné analogy jednorozměrných filtrů f1(x) jsou konstruovány ve dvou variantách symetrie: nebo jako funkce poloměru:

f2(x, y) = f1(),

nebo jako dílo:

f2(x, y) = f1(x) × f1(y).

První možnost je správnější, ale druhá má vlastnost separability, tj. dvourozměrnou konvoluci lze provést dvěma jednorozměrnými konvolucemi postupně podél řádků s f1(x) a podél sloupců s f1(y).

Převzorkování obrázku nebo převzorkování je změna vzorkovací frekvence digitálního signálu. Při použití na digitální obrázky to znamená změnu velikosti obrázku.

Existují různé algoritmy pro převzorkování obrázků. Chcete-li například zvětšit obrázek 2krát pomocí metody bilineární interpolace, mezilehlé sloupce a řádky se získají lineární interpolací hodnot sousedních sloupců a řádků. Každý bod nového snímku lze získat jako vážený součet většího počtu bodů v původním snímku (bikubická a jiné typy interpolace). Převzorkování nejvyšší kvality je dosaženo při použití algoritmů, které berou v úvahu nejen časovou oblast, ale také frekvenční oblast signálu.

Uvažujme převzorkovací algoritmus s maximálním zachováním informace o frekvenci obrazu. Budeme zvažovat fungování algoritmu na jednorozměrných signálech, protože dvourozměrný obraz lze nejprve roztáhnout nebo zkomprimovat vodorovně (podél řádků) a poté svisle (podél sloupců), a redukovat převzorkování dvourozměrného obrázku na převzorkování. jednorozměrných signálů.

Řekněme, že máme jednorozměrný signál (obr. 17.2.4), specifikovaný na intervalu 0-T a vzorkovaný s krokem Dt=1 (N intervalů). Signál je nutné „natáhnout“ mkrát. Spektrum signálu znázorněné na obrázku je vypočteno rychlou Fourierovou transformací (FFT, počet vzorků spektra se rovná počtu vzorků signálu) a je udáno v hlavním rozsahu FFT (0-2p, Nyquistova frekvence wN = p/Dt = p, nebo 0,5N podle číslování vzorků spektra s krokem podél spektra Df = 1/T nebo Dw = 2p/T). Provedení protažení má 2 kroky.

Prvním krokem je nulová interpolace, která prodlouží délku signálu m krát. (obr. 17.2.5). Musíte vynásobit všechny vzorky původního signálu hodnotou ma pak vložit nulovou hodnotu m-1 za každý vzorek signálu. Interval 0-T, jehož hodnota zůstává nezměněna, nyní obsahuje m-krát více vzorkovacích intervalů (mN) a nový vzorkovací krok bude roven Dx=Dt/m. V souladu s tím je nová Nyquistova frekvence pro tento signál mp/Dt = mp. Fyzická hodnota kroku podél spektra ve frekvenčních jednotkách je však převrácenou hodnotou fyzické hodnoty intervalu nastavení signálu (Df = 1/T), a proto FFT z mN bodů signálu vypočítá mN bodů spektrum v hlavním FFT rozsahu 0-14pm s krokem spektra původního signálu, ve kterém bude obsahovat m-periody spektra původního signálu (jedna hlavní a m-1 strana).

Druhým krokem je odfiltrování postranních pásem spektra pomocí dolnopropustného filtru buď v časové nebo spektrální doméně. Na Obr. 17.2.6 bylo spektrum vyčištěno a byla provedena inverzní Fourierova transformace, výsledkem byl signál mkrát delší než původní s plným zachováním všech frekvenčních informací.

Na podobném principu lze zkonstruovat algoritmus pro kompresi (decimaci) signálu nkrát s obráceným pořadím kroků. Při kompresi signálu se zvýší krok vzorkování signálu a v souladu s tím se sníží Nyquistova frekvence, zatímco ořezové vysoké frekvence (šum a nevýznamné vysokofrekvenční části spektra signálu) se budou odrážet od hranice hlavního rozsahu. a sečteno s hlavními informacemi, což vytváří zkreslení. Pro eliminaci tohoto jevu je signál nejprve filtrován dolní propustí s mezní frekvencí rovnou nové Nyquistově frekvenci (antialiasing) a teprve poté je signál zdecimován decimací.

Když se převzorkování provádí pouze v časové oblasti, jsou algoritmy roztahování a komprese zpravidla kombinovány do jednoho sekvenčního procesu zadáním změny v kroku vzorkování ve formě poměru m/n, který umožňuje specifikovat celočíselné hodnoty ma n pro zlomkové hodnoty změny kroku vzorkování. To výrazně zjednodušuje algoritmy a zvyšuje efektivitu a kvalitu jejich práce. Například při roztažení signálu 1,5krát při m/n = 3/2 se signál nejprve roztáhne 3krát (jednoduché a rovnoměrné přidání nul ke všem vzorkům, poté se provede filtrace dolní propustí, načež signál je zeslaben faktorem dva Antialiasingový filtr není vyžadován, protože jeho mezní frekvence je překryta frekvencí první dolní propusti (například m/n = 2 /3), pouze antialiasingový filtr se používá stejným způsobem.

17.3. filtrování obrazu

Filtrování obrázků je operace, jejímž výsledkem je obrázek stejné velikosti, získaný z původního podle určitých pravidel. Typicky je intenzita (barva) každého pixelu ve výsledném obrázku určena intenzitou (barvami) pixelů umístěných v nějakém jeho sousedství v původním obrázku.

Pravidla filtrování mohou být velmi různorodá. Filtrování obrazu je jednou z nejzákladnějších operací počítačového vidění, rozpoznávání vzorů a zpracování obrazu. Práce velké většiny metod zpracování obrazu začíná tím či oním filtrováním zdrojových obrázků.

Lineární filtry mají velmi jednoduchý matematický popis. Budeme předpokládat, že je dán původní polotónový obraz A, a intenzity jeho pixelů označíme jako A(x, y). Lineární filtr je definován funkcí reálné hodnoty h (jádro filtru) definovanou na rastru. Samotné filtrování se provádí pomocí operace diskrétní konvoluce (vážená sumace):

B(x, y) = h(i, j) ③③A(x, y) = h(i, j) A(x-i, y-j). (17.3.1)

Výsledkem je obrázek B. Typicky je jádro filtru nenulové pouze v nějakém okolí N bodu (0, 0). Mimo toto okolí se h(i, j) rovná nule nebo je jí velmi blízké a lze je zanedbat. Sčítání se provádí přes (i, j) О N a hodnota každého pixelu B(x, y) je určena pixely obrázku A, které leží v okně N se středem v bodě (x, y) (označeném množinou N(x, y) ). Jádro filtru definované na pravoúhlém sousedství N lze vidět jako matici m x n, kde délky stran jsou lichá čísla. Když zadáváte jádro jako matici, mělo by být vystředěno. Pokud se pixel (x, y) nachází v blízkosti okrajů obrazu, pak souřadnice A(x-i, y-j) pro určité (i, j) mohou odpovídat neexistujícím pixelům A mimo obraz. Tento problém lze vyřešit několika způsoby.

Vyhněte se filtrování těchto pixelů oříznutím okrajů obrázku B nebo použitím původních hodnot obrázku A na jejich hodnoty.

Nezahrnujte chybějící pixel do součtu, rozdělte jeho váhu h(i, j) rovnoměrně mezi ostatní pixely v okolí N(x, y).

Určete hodnoty pixelů mimo hranice obrázku pomocí extrapolace.

Definujte hodnoty pixelů za hranicemi obrázku pomocí zrcadlového pokračování obrázku.

Výběr metody se provádí s ohledem na specifické vlastnosti filtru a obrazu.

Anti-aliasingové filtry. Nejjednodušší obdélníkový vyhlazovací filtr o poloměru r je specifikován pomocí matice velikosti (2r+1) × (2r+1), jejíž všechny hodnoty se rovnají 1/(2r+1)2 a součtu hodnota se rovná jedné. Jedná se o dvourozměrný analog nízkoprůchodového jednorozměrného filtru ve tvaru U s klouzavým průměrem. Při filtrování s takovým jádrem je hodnota pixelu nahrazena průměrnou hodnotou pixelů ve čtverci se stranou 2r+1 kolem. Příklad masky filtru 3×3:

.

Jedním z použití filtrů je redukce šumu. Šum se liší pixel od pixelu nezávisle a za předpokladu, že matematické očekávání hodnoty šumu je nula, šum sousedních pixelů se při sečtení vzájemně vyruší. Čím větší je okno filtrování, tím nižší bude průměrná intenzita šumu, dojde však také k odpovídajícímu rozmazání výrazných detailů obrazu. Obraz bílého bodu na černém pozadí během filtrace (reakce na jeden impuls) bude stejnoměrně šedý čtverec.

Redukce šumu pomocí obdélníkového filtru má značnou nevýhodu: všechny pixely v masce filtru v jakékoli vzdálenosti od zpracovávaného mají na výsledek stejný vliv. O něco lepšího výsledku dosáhnete úpravou filtru zvýšením hmotnosti centrálního bodu:

.

Účinnější redukce šumu lze dosáhnout, pokud se s rostoucí vzdáleností od zpracovávaného snižuje vliv pixelů na výsledek. Gaussův filtr s jádrem má tuto vlastnost: h(i, j) = (1/2ps2) exp(-(i2+j2)/2s2). Gaussův filtr má nenulové jádro nekonečné velikosti. Hodnoty jádra filtru však velmi rychle klesají na n), a proto se v praxi lze omezit na konvoluci s oknem malé velikosti kolem (0, 0), například s poloměrem okna rovným 3σ .

Gaussovské filtrování je také vyhlazování. Na rozdíl od obdélníkového filtru však bude obraz bodu s Gaussovým filtrováním symetrickým rozmazaným bodem, s jasem klesajícím od středu k okrajům. Míra rozmazání obrazu je určena parametrem σ.

Filtry pro zvýšení kontrastu . Zatímco antialiasingové filtry snižují místní kontrast obrazu jeho rozmazáním, filtry zvyšující kontrast mají opačný účinek a jsou v podstatě filtry s vysokou prostorovou frekvencí. Jádro kontrastního filtru v bodě (0, 0) má hodnotu větší než 1, s celkovým součtem hodnot rovným 1. Například filtry zvyšující kontrast jsou filtry s jádrem definovaným maticemi :

. .

Příklad použití filtru je na Obr. 17.3.1. Efektu zvýšení kontrastu je dosaženo díky skutečnosti, že filtr zvýrazňuje rozdíl mezi intenzitami sousedních pixelů a tyto intenzity od sebe oddaluje. Tento efekt bude tím silnější, čím větší bude hodnota centrálního členu jádra. Charakteristickým artefaktem lineárního filtrování zvyšujícího kontrast je patrné světlo a méně nápadné tmavé halo kolem hranic.

Rozdílové filtry – jedná se o lineární filtry specifikované diskrétními aproximacemi diferenciálních operátorů (metodou konečných diferencí). Tyto filtry hrají zásadní roli v mnoha aplikacích, například při hledání hran v obraze.

Nejjednodušší diferenciální operátor je derivace vzhledem k x-ové souřadnici d/dx, která je definována pro spojité funkce. Obvyklými variantami podobných operátorů pro diskrétní obrázky jsou filtry Prewitt a Sobel:

. .

Filtry, které aproximují derivační operátor d/dy na souřadnici y, se získají transpozicí matic.

Nejjednodušší algoritmus pro výpočet normy gradientu ze tří sousedních bodů:

G(x, y) = .

Používá se také zjednodušený výpočetní vzorec:

Výpočet normy gradientu přes čtyři sousední body (operátor Roberts):

Sobelův algoritmus používá osm vzorků jasu v blízkosti centrálního bodu:

G(x, y) = , G(x, y) @ ,

Gxx, y = - ,

Gyx, y = -.

Spolu s přesnějším určením gradientové normy Sobelův algoritmus také umožňuje určit směr gradientového vektoru v rovině analýzy obrazu ve tvaru úhlu j mezi gradientovým vektorem a směrem maticových řad. :

j(x, y) = argtg(Gyx, y/Gxx, y).

Na rozdíl od vyhlazovacích a kontrastních filtrů, které nemění průměrnou intenzitu obrazu, výsledkem aplikace rozdílových operátorů je obvykle obraz s průměrnou hodnotou pixelu blízkou nule. Vertikální rozdíly (ohraničení) původního obrázku odpovídají pixelům s velkými hodnotami modulu ve výsledném obrázku. Rozdílové filtry se proto také nazývají filtry výběru hranic objektu.

Podobně jako výše uvedené filtry lze filtry pro jiné diferenciální operátory konstruovat pomocí metody konečných rozdílů. Zejména diferenciální Laplaceův operátor (Laplacián) D= 𝝏2/𝝏x2 + 𝝏2/𝝏y2, který je důležitý pro mnoho aplikací, lze aproximovat pro diskrétní obrázky pomocí filtru s maticí (jedna z možností):

.

Jak je vidět na Obr. 17.3.2, v důsledku použití diskrétního Laplacianu, velké absolutní hodnoty odpovídají jak vertikálním, tak horizontálním rozdílům jasu. Filtr je tedy filtr, který najde hranice libovolné orientace. Nalezení hranic v obrázku lze provést použitím tohoto filtru a odebráním všech pixelů, jejichž absolutní hodnota přesahuje určitou prahovou hodnotu.

Takový algoritmus má však značné nevýhody. Tou hlavní je nejistota při volbě prahové hodnoty. Pro různé části obrazu se obvykle získá přijatelný výsledek s výrazně odlišnými prahovými hodnotami. Rozdílové filtry jsou navíc velmi citlivé na obrazový šum.

Dvourozměrná cyklická konvoluce. Stejně jako u jednorozměrných signálů lze dvourozměrnou konvoluci provádět v prostorové frekvenční doméně pomocí rychlých algoritmů Fourierovy transformace a násobení dvourozměrných spekter obrazu a jádra filtru. Je také cyklický a obvykle se provádí v posuvné verzi. Vezmeme-li v úvahu cykličnost, pro výpočet konstantního vzoru spektra jádra se rozměry masky filtru jádra zdvojnásobí podél os a vyplní se nulami a stejné rozměry masky se použijí pro výběr okna klouzajícího po obrázku, ve kterém FFT se provádí. Implementace FIR filtru pomocí FFT je zvláště účinná, pokud má filtr velkou referenční plochu.

Nelineární filtry . V digitálním zpracování obrazu se k obnově obrazů poškozených různými modely šumu široce používají nelineární algoritmy založené na statistikách pořadí. Umožňují vyhnout se dodatečnému zkreslení obrazu při odstraňování šumu a také výrazně zlepšují výsledky filtrů na snímcích s vysokou mírou šumu.

Představme si koncept M-okolí obrazového prvku A(x, y), který je pro toto okolí centrální. V nejjednodušším případě M-okolí obsahuje N-pixelů - bodů spadajících do masky filtru, včetně (nebo nezahrnuje) centrální. Hodnoty těchto N-prvků mohou být uspořádány do variační řady V(r), řazeny vzestupně (nebo sestupně) a určité momenty této řady lze vypočítat, například průměrná hodnota jasu mN a rozptyl dN. Výstupní hodnota filtru, který nahrazuje centrální vzorek, se vypočítá pomocí vzorce:

B(x, y) = aA(x, y) + (1-a) mN. (17.3.2)

Hodnota koeficientu a = je spojena určitou závislostí se statistikou vzorků v okně filtru, např.:

a = dN /(dN + k dS), (17.3.3)

kde dS je rozptyl šumu nad obrazem jako celkem nebo přes S-okolí pro S > M a MÎS, k je konstanta spolehlivosti pro rozptyl S-okolí. Jak vyplývá z tohoto vzorce, pro k = 1 a dN » dS platí a » 0,5 a hodnota B(x, y) = (A(x, y) + mN)/2, tj. sčítají se rovnoměrně na hodnot centrálního vzorku a průměrné hodnoty pixelů jeho M-okolí. S rostoucími hodnotami dN se zvyšuje příspěvek centrální referenční hodnoty k výsledku, a když se hodnoty dN snižují, zvyšuje se hodnota mN. Váhu příspěvku průměrných hodnot v M-okolí lze měnit hodnotou koeficientu k.

Volba statistické funkce a povaha závislosti koeficientu a na ní může být značně různorodá (například podle rozptylu rozdílů ve vzorcích v M-okolí s centrálním vzorkem), a závisí jednak na velikosti na cloně filtru a na povaze snímků a šumu. V podstatě by hodnota koeficientu a měla specifikovat stupeň poškození centrálního vzorku a tím i výpůjční funkci pro jeho korekci vzorků z M sousedství.

Nejjednodušší a nejběžnější typy nelineárních filtrů pro zpracování obrazu jsou prahové a střední filtry.

Prahová filtrace se uvádí například takto:

B(x, y) =

Velikost p je prahová hodnota filtrování. Pokud hodnota centrálního bodu filtru překročí průměrnou hodnotu vzorků mN v jeho M-okolí o prahovou hodnotu, pak je nahrazena průměrnou hodnotou. Prahová hodnota může být buď konstantní nebo funkčně závislá na hodnotě centrálního bodu.

Mediánové filtrování je definován takto:

B(x, y) = med (M(x, y)),

tj. výsledkem filtrování je střední hodnota pixelů okolí, jejichž tvar je určen maskou filtru. Mediánové filtrování může účinně odstranit šum z obrazu, který nezávisle ovlivňuje jednotlivé pixely. Takovým rušením jsou například „rozbité“ pixely při digitálním snímání, „sněžný“ šum, když jsou některé pixely nahrazeny pixely s maximální intenzitou atd. Výhodou středního filtrování je, že „horký“ pixel na tmavém pozadí být nahrazeny tmavými a nikoli „rozmazanými“ po celé oblasti.

Mediánové filtrování má výraznou selektivitu s ohledem na prvky pole, které jsou nemonotónní složkou sekvence čísel v otvoru filtru. Mediánový filtr zároveň ponechává monotónní složku sekvence beze změny. Díky této funkci mediánové filtry s optimálně zvolenou clonou zachovávají ostré hranice objektů bez zkreslení, potlačují nekorelovaný nebo slabě korelovaný šum a malé detaily.

Extrémní filtry se určují podle pravidel:

Bmin(x, y) = min (M(x, y)),

Bmax(x, y) = max (M(x, y)),

tj. výsledek filtrování je minimální a maximální hodnota pixelů v masce filtru. Takové filtry se obvykle používají pro binární obrázky.

17.4. KOMPRESE OBRAZU

Typický obrázek s rozlišením asi 3000x2000 při 24 bitech na pixel pro přenos barev má objem 17 megabajtů. Pro profesionální zařízení velikost výsledného rastru obrázku může být výrazně větší, barevná hloubka až 48 bitů na pixel a velikost jednoho obrázku může být i více než 200 megabajtů. Algoritmy komprese obrazu jsou proto velmi důležité pro snížení množství dat představujících obraz.

Existují dvě hlavní třídy algoritmů:

1. Bezeztrátová komprese A (bezeztrátová komprese), pokud existuje inverzní algoritmus A-1 takový, že pro libovolné h - obraz A[h] = h1 máme A-1 = h. Bezeztrátová komprese se používá u takových grafických obrazových formátů jako: GIF, PCX, PNG, TGA, TIFF a používá se při zpracování zvláště cenných primárních informací (lékařské snímky, letecké a kosmické fotografie atd.), kdy i sebemenší zkreslení nežádoucí

2. Ztrátová komprese, pokud neposkytuje možnost přesné obnovy původního obrazu. Přibližný algoritmus obnovy obrazu spárovaný s A bude označen jako A*. Dvojice (A, A*) je vybrána tak, aby poskytovala vysoký kompresní poměr při zachování vizuální kvality. Ztrátová komprese se používá u obrazových formátů: JPEG, JPEG2000 atd.

Všechny algoritmy a příkazy platí jak pro obrázky, tak pro libovolné sekvence, jejichž prvky mohou nabývat konečného počtu hodnot. Je třeba mít na paměti, že neexistují žádné ideální algoritmy, které by dokázaly komprimovat jakýkoli soubor dat bez ztráty.

Algoritmy kódování délky opakování (RLE). jsou založeny na jednoduchý princip: nahrazení opakujících se skupin prvků původní sekvence dvojicí (množství, prvek) nebo pouze množstvím.

Bitová úroveň. Zdrojová data budeme uvažovat například na úrovni posloupnosti bitů, které reprezentují černobílý obrázek. Obvykle je v řadě několik 0 nebo 1 a můžete zakódovat počet stejných číslic v řadě. Ale počet opakování musí být také zakódován v bitech. Můžeme uvažovat, že každé číslo opakování se mění od 0 do 7 (3bitový kód), přičemž se střídá sekvence kódů jedniček a nul. Posloupnosti lze například porovnat s čísly 7 0 4, tedy 7 jedniček, 0 nul, 4 jedniček a máme nový rok - Čím delší je délka posloupností identických bitů, tím větší efekt. Posloupnost 21 jedniček, 21 nul, 3 jedniček a 7 nul tedy bude zakódována následovně: tj. z původní sekvence dlouhé 51 bitů máme sekvenci dlouhou 36 bitů.

Úroveň bajtů. Předpokládejme, že vstupem je polotónový obrázek, kde je pro hodnotu intenzity pixelu alokován 1 bajt a výrazně se sníží očekávání dlouhého řetězce identických bitů.

Vstupní stream rozdělíme na bajty (kód od 0 do 255) a opakující se bajty zakódujeme dvojicí (množství, písmeno). Jeden bajt lze ponechat beze změny. Zakódujeme tedy bajty AABBBCDAA (2A) (3B) (C) (D) (2A).

Úpravy tohoto algoritmu se však samy o sobě používají jen zřídka (například ve formátu PCX), protože podtřída sekvencí, na které je algoritmus účinný, je poměrně úzká. Častěji se používají jako jeden ze stupňů kompresního potrubí.

Slovníkové algoritmy Namísto kódování pouze jednoho prvku příchozí sekvence je zakódován řetězec prvků. V tomto případě se ke kódování nových používá slovník řetězců (vytvořený ze vstupní sekvence).

Algoritmus LZ77 byl jedním z prvních, který používal slovník. Posledních N již zakódovaných prvků sekvence je použito jako slovník. Během procesu komprese se podsekvenční slovník „souvá“ po vstupní sekvenci. Řetězec prvků na výstupu je zakódován následovně: pozice odpovídající části zpracovávaného řetězce prvků ve slovníku - offset (vzhledem k aktuální pozici), délka, první prvek následující za spárovanou částí řetězce. Délka párovacího řetězce je výše omezena číslem n. Úkolem je tedy najít největší řetězec ze slovníku, který odpovídá zpracovávané sekvenci. Pokud nejsou žádné shody, zaznamená se nulový posun, délka jednotky a první prvek nekódované sekvence.

Výše popsané schéma kódování vede ke koncepci posuvného okna, které se skládá ze dvou částí:

Subsekvence již zakódovaných prvků délky N-dictionary - search buffer;

Dílčí posloupnost délky n z řetězce prvků, pro které bude proveden pokus o nalezení shody - vyrovnávací paměť náhled(předběžný buffer).

Dekódování komprimované sekvence je dekódování zaznamenaných kódů: každý záznam je porovnán s řetězcem ze slovníku a explicitně zapsaným prvkem, po kterém je slovník posunut. Slovník je znovu vytvořen, jak běží dekódovací algoritmus.

Tento algoritmus je zakladatelem celé rodiny algoritmů. Mezi jeho přednosti patří slušný stupeň komprese na docela velkých sekvencích a rychlá dekomprese. Mezi nevýhody patří nízká rychlost komprese a nižší kompresní poměr než u alternativních algoritmů.

Algoritmus LZW. Slovník v tento algoritmus je tabulka, která se při běhu algoritmu plní řetězci prvků. Během procesu komprese je nalezen nejdelší řetězec již zaznamenaný ve slovníku. Pokaždé, když není ve slovníku nalezen nový řetězec prvků, je přidán do slovníku a je zaznamenán kód řetězce. Teoreticky neexistují žádná omezení velikosti tabulky, ale omezení velikosti vám umožňuje zlepšit kompresní poměr, protože se hromadí zbytečné (nevyskytující se) řetězce. Čím více položek tabulka obsahuje, tím více informací musí být přiděleny kódům obchodů.

Dekódování spočívá v přímém dešifrování kódů, tj. ve vytvoření slovníku a výstupu odpovídajících řetězců. Slovník se inicializuje stejným způsobem jako v kodéru. Mezi výhody algoritmu patří vysoký a dostatečný stupeň komprese vysoká rychlost komprese i dekódování.

Statistické kódovací algoritmy ke každému prvku sekvence přiřaďte kód tak, aby jeho délka odpovídala pravděpodobnosti výskytu prvku. Komprese probíhá nahrazením prvků původní sekvence, které mají stejnou délku (každý prvek zabírá stejný počet bitů) prvky různé délky, úměrné zápornému logaritmu pravděpodobnosti, tj. prvky, které se vyskytují častěji než jiné, mají kód kratší délky.

Používá Huffmanův algoritmus prefixový kód proměnná délka, mající speciální vlastnost: less krátké kódy neodpovídají prefixu (počáteční části) delších. Tento kód umožňuje kódování jedna ku jedné. Proces komprese zahrnuje nahrazení každého prvku vstupní sekvence jeho kódem. Konstrukce sady kódů se obvykle provádí pomocí tzv kódové stromy.

Huffmanův algoritmus je dvouprůchodový algoritmus. První průchod obrazem vytvoří tabulku hmotností prvků a při druhém dojde ke kódování. Existují implementace algoritmu s pevnou tabulkou. Často se stává, že apriorní rozdělení pravděpodobnosti prvků abecedy je neznámé, protože není k dispozici celá sekvence najednou a používají se adaptivní modifikace Huffmanova algoritmu.

Ztrátová komprese obrazu. Množství informací potřebných k uložení obrázků je obvykle velké. Klasické algoritmy, bytí algoritmy obecný účel, neberou v úvahu, že komprimovanou informací je obrázek - dvourozměrný objekt, a neposkytují dostatečný stupeň komprese.

Ztrátová komprese vychází z vlastností lidského vnímání obrazu: největší citlivost v určitém rozsahu barevných vln, schopnost vnímat obraz jako celek bez povšimnutí drobných zkreslení. Hlavní třídou obrázků, na které jsou zaměřeny algoritmy ztrátové komprese, jsou fotografie a obrázky s hladkými barevnými přechody.

Odhad ztráty v obrazech. Existuje mnoho měřítek pro posouzení ztrát v obrazech po jejich obnovení (dekódování) z komprimovaných, ale pro všechny je možné vybrat dva obrazy tak, že jejich míra rozdílu bude poměrně velká, ale rozdíly budou téměř neviditelné do oka. A naopak – můžete vybrat obrázky, které se na pohled velmi liší, ale liší se jen nepatrně.

Standardní numerickou mírou ztráty je obvykle standardní odchylka (RMS) hodnot pixelů rekonstruovaného obrázku od původního. Nejdůležitějším „měřítkem“ hodnocení ztráty je však názor pozorovatele. Čím méně rozdílů (nebo ještě lépe, žádné rozdíly) pozorovatel detekuje, tím vyšší je kvalita kompresního algoritmu. Algoritmy ztrátové komprese často dávají uživateli možnost vybrat si množství „ztracených“ dat, tedy právo vybrat si mezi kvalitou a velikostí komprimovaný obrázek. Přirozeně, čím lepší vizuální kvalita při vyšším kompresním poměru, tím lepší je algoritmus.

Fourierova transformace. V obecný případ obrázek lze vidět jako funkci dvou proměnných definovaných v bodech výsledného rastru. Množina takových funkcí v bodech pevného konečného rastru tvoří konečnorozměrný euklidovský prostor a lze na ně aplikovat diskrétní Fourierovu transformaci, tedy spektrální reprezentaci obrazu. Poskytuje:

Nekorelované a nezávislé koeficienty spektra, tj. přesnost zobrazení jednoho koeficientu nezávisí na žádném jiném.

- Energetické zhutnění. Transformace ukládá základní informace v malém počtu koeficientů. Tato vlastnost Tento efekt je nejvýraznější u fotorealistických snímků.

Koeficienty spektrálního zobrazení jsou amplitudy prostorových frekvencí obrazu. V případě obrázků s hladké přechody Většina informací je obsažena v nízkofrekvenčním spektru.

Použitý kompresní algoritmus formát JPEG, je postaven na použití diskrétní kosinové Fourierovy transformace. Kompresní schéma v algoritmu je potrubí, kde tato transformace je pouze jednou z fází, ale jednou z hlavních. Algoritmus obsahuje následující hlavní operace:

1. Přenést na barevný prostor YCbCr. Zde Y je složka jasu, Cb a Cr jsou chrominanční složky. Lidské oko je citlivější na jas než na barvu. Proto je důležitější zachovat větší přesnost při přenosu Y než při přenosu Cb a Cr.

2. Diskrétní kosinová transformace (DCT). Obraz je rozdělen do 8 × 8 bloků Na každý blok je aplikována diskrétní kosinusová transformace (samostatně pro složky Y, Cb a Cr).

3. Redukce vysokofrekvenčních složek v maticích DCT. Lidské oko stěží zaznamená změny ve vysokofrekvenčních složkách, proto lze koeficienty odpovědné za vysoké frekvence uložit s menší přesností.

4. Cikcak řazení matic. Toto je speciální maticový průchod pro získání jednorozměrné sekvence. Nejprve přijde prvek T00, pak T01, T10, T1 Navíc pro typické fotorealistické obrázky budou nejprve nenulové koeficienty odpovídající nízkofrekvenčním složkám a pak množina nul (vysokofrekvenční složky).

5. Komprese nejprve metodou RLE a poté Huffmanovou metodou.

Algoritmus obnovy obrazu pracuje v opačném pořadí. Kompresní poměr je od 5 do 100krát nebo více. Vizuální kvalita většiny fotorealistických snímků přitom zůstává zachována dobrá úroveň při stlačení až 15krát. Algoritmus a formát jsou nejběžnější pro přenos a ukládání plnobarevných obrázků.

Vlnková transformace signály jsou zobecněním klasické Fourierovy transformace. Termín "vlnka" přeložený z angličtiny znamená "malá (krátká) vlna." Vlnky jsou obecný název pro rodiny matematické funkce určitou formu, která je lokální v čase a frekvenci a ve které jsou všechny funkce získávány z jedné základní pomocí jejích posunů a protažení podél časové osy.

Ve ztrátových kompresních algoritmech jsou zpravidla zachovány všechny operace kompresního potrubí a diskrétní Fourierova transformace je nahrazena diskrétní vlnkovou transformací. Vlnkové transformace mají velmi dobrou frekvenčně-prostorovou lokalizaci av tomto ohledu jsou lepší než tradiční Fourierovy transformace. V tomto případě je možné použít silnější kvantizaci, čímž se zlepší vlastnosti sekvence pro následnou kompresi. Algoritmy komprese obrazu založené na této transformaci vykazují lepší výsledky při zachování kvality obrazu při stejném kompresním poměru.

literatura

46. ​​​​a další Rychlé algoritmy v digitálním zpracování obrazu. – M.: Radio and Communications, 1984. – 224 s.

47. Zpracování obrazu Soifer. Část 2. Metody a algoritmy. – Sorosův vzdělávací časopis č. 3, 1996.

48. , Šum kazety z obrázků založených na nelineárních algoritmech využívajících statistiku pořadí. - Yaroslavl State University, 2007.

49. Andreev televizní sledovací systémy. Část II. aritmetika - logické základy a algoritmy. Konzultace. - Petrohrad: Petrohrad, GUITMO, 2005. – 88 s.

51. Lukin A. Úvod do číslicového zpracování signálů (matematické základy) - M.: Moskevská státní univerzita, Laboratoř počítačové grafiky a multimédií, 2002. - http://pv. *****/dsp/dspcourse. pdf, http://dsp-book. *****/dspkurz. djvu, http://geogin. *****/archiv/dsp/dsp4.pdf.

1i. atd. Základy algoritmu rastrová grafika. – Internetová univerzita informačních technologií. – http://www. *****/goto/kurz/rastrgraph/

2i. Lukin -elektronické systémy: Poznámky k přednášce. ITMO, 2004. - Petrohrad, MFF ITMO, 2004. - http://iff. *****/kons/oes/KL. htm

O zaznamenaných chybách a návrzích na doplnění: *****@***ru.

Copyright©2008DavydovA.PROTI.

Rozmanitost přístupů ke zlepšení obrazu spadá do dvou kategorií: metody zpracování prostorové domény (prostorové metody) a metody zpracování prostorové domény. frekvenční oblasti(frekvenční metody). Prostorová doména se týká souboru pixelů, které tvoří obraz. Funkce předběžného zpracování prostorové domény je zapsána jako

Kde F(x, y) – vstupní obrázek,

G(x, y) – výstupní (zpracovaný) obrázek,

h– operátor funkce F, definovaný v nějaké doméně ( x, y).

Operace tohoto typu patří do obecné třídy operace na sousedních prvcích. Tyto operace jsou hlavními nástroji pro nízkoúrovňové zpracování obrazu nebo zpracování obrazu v prostorové doméně.

Hlavní přístup k určení okolí bodu ( x, y) je použití čtvercové nebo obdélníkové oblasti části obrazu se středem v bodě ( x, y). Střed této části obrázku se pohybuje od pixelu k pixelu, počínaje například zleva horní roh. Zároveň získat G(x, y) operátor se používá pro každou pozici ( x, y). Ačkoli se někdy používají jiné tvary sousedství (jako je kruh), upřednostňují se čtvercové tvary kvůli jejich snadné implementaci.

Jedna z nejpoužívanějších metod prostorové domény je založena na použití filtrů (konvoluční masky, šablony, okna). Typicky je maska ​​filtru malý (například rozměr 3*3) dvourozměrný systém, jehož koeficienty jsou voleny tak, aby detekovaly danou vlastnost obrazu (obr. 1.5, a).

Rýže. 1.5: a – filtrační maska; b – koeficienty masky filtru

Pokud hodnoty w 1 ,w 2 ,…,w 9 představuje koeficienty, masky pixelů ( x, y) a jeho osmi sousedů (obr. 1.5, b), pak lze algoritmus reprezentovat jako provádění následující operace na okolí 3*3 bodů (x, y) :

Úlohou filtrování obrazu se v širokém smyslu rozumí jakákoli procedura zpracování obrazu, ve které je vstup do procedury rastrový obrázek a výstupem je rastrový obrázek. Častěji se však „filtrováním“ rozumí tzv rušení filtrování. Hlavním cílem filtrování šumu je zpracovat snímky tak, aby výsledek byl vhodnější z pohledu konkrétní aplikace. Obecně můžeme rozlišovat lineární filtry(vyhlazovací filtry, filtry zvyšující kontrast, rozdílové filtry) a nelineární filtry(střední filtr).

Zde je stručný popis nejběžnějších metod filtrování.

Nízkopropustný filtr– zeslabuje vysokofrekvenční složky a posiluje úlohu nízkofrekvenčních. Frekvence při aplikaci na obrázky odráží množství detailů přítomných v obrázku. Náhlé změny jasu, interference a šum jsou příklady vysokofrekvenčních prvků v obraze. Vyhlazení obrazu je implementováno pomocí následujících jader:

,

,

.

Vysokopropustný filtr– zeslabuje nízkofrekvenční složky v obraze a posiluje roli vysokofrekvenčních. High-pass filtry se používají ke zvýraznění detailů, jako jsou obrysy, okraje, nebo k doostření obrazu. Každý skok v jasu a každý obrys představuje intenzivní detail spojený se zvýšenými frekvencemi. Izolace vysokofrekvenčních komponent se provádí pomocí následujících jader:

,

,

.

Robertsův kameraman. Robertsův operátor je příkladem nelineárního filtru. Transformace každého pixelu pomocí Robertsova křížového operátoru může zobrazit derivaci obrázku podél nenulové úhlopříčky a kombinaci těchto transformovaných obrázků lze také chápat jako gradient od dvou horních pixelů ke dvěma spodním. Robertsův operátor se používá pro výpočetní rychlost, ale je horší než alternativy kvůli značnému problému citlivosti na hluk. Vytváří jemnější čáry než jiné metody zvýraznění okrajů.

Na zpracování se podílejí čtyři pixely umístěné následovně (obr. 1.6).

Rýže. 1.6. Pixely zapojené do zpracování operátorem Roberts

Odpověď operátora Robertse:

Konvoluční jádra v v tomto případě bude vypadat takto:

,

.

Konvoluce pro každé jádro se vypočítá samostatně. Odezvou tohoto filtru je hodnota

, (1.17)

Kde P A Q– odezva jader H 1 a H 2 .

Někdy množství
.

Sobelův operátor. Sobelův operátor se používá v algoritmech detekce hran. Jedná se o diskrétní diferenciální operátor, který vypočítává přibližnou hodnotu gradientu jasu obrazu. Výsledkem aplikace Sobelova operátoru v každém bodě obrázku je buď vektor gradientu jasu v tomto bodě, nebo jeho norma. Metoda zvýraznění hran využívající Sobelův operátor uvažuje dvě různá konvoluční jádra:

Na základě těchto konvolucí se vypočítá velikost a směr hran. Konvoluce pro každé jádro se vypočítá samostatně. Odezvou tohoto filtru je hodnota

, (1.19)

Kde P A Q– odezva jader H 1 a H 2 .

Někdy množství
.

Prewittův kameraman. Operátor Prewitt funguje podobně jako operátor Sobel. Prewittův detektor hran je vhodným způsobem odhadnout velikost a orientaci hranice. Zatímco diferenciální gradientní detektor vyžaduje časově náročný výpočet odhadů orientace z veličin ve vertikálním a horizontálním směru, Prewittův hranový detektor udává směr přímo od jádra s maximálním výsledkem. Metoda zvýraznění hran pomocí Prewittova operátoru bere v úvahu dvě různá konvoluční jádra:

Výsledek operátora Prewitt je

, (1.21)

Kde P A Q– odezva jader H 1 a H 2 .

Laplaceův operátor. Diskrétní Laplaceův operátor se často používá při zpracování obrazu, jako je extrakce hran nebo aplikace odhadu pohybu. Diskrétní Laplacián je definován jako součet druhých derivací a je vypočítán jako součet rozdílů v sousedech centrálního pixelu. Laplaceova metoda vylepšení hran bere v úvahu řadu různých konvolučních jader. Zde jsou některé z nich:

Jak vidíte, součet prvků matice je nulový, takže odezva filtru může být záporná. V tomto případě se odezva bere modulo. V důsledku zpracování se oblasti s konstantní nebo lineárně rostoucí intenzitou zčernají a oblasti s rychle se měnícími hodnotami intenzity jsou jasně zvýrazněny.

Níže jsou uvedeny některé prostorové procesy, které nespadají do kategorie konvoluce a lze je použít k eliminaci různé typy hluk.

Harmonický střední filtr. Harmonický průměr řady
vypočítané podle vzorce

. (1.23)

Během procesu filtrování je hodnota aktuálního obrazového bodu nahrazena hodnotou
sady hodnot pro devět pixelů, včetně aktuálních a sousedních.

Min– filtr. Během procesu filtrování je hodnota aktuálního pixelu nahrazena minimální hodnotou sousedních pixelů. Takže například pro jádro dimenze 3 budeme mít:

Max– filtr. Během procesu filtrování je hodnota aktuálního pixelu nahrazena maximální hodnotou sousedních pixelů (podobně jako u předchozího filtru).

Min- Max-filtr. Během procesu filtrování je hodnota aktuálního pixelu v obrázku nejprve nahrazena minimální hodnotou sousedních pixelů a při dalším průchodu maximální hodnotou.

Mediánový filtr. Filtrování průměru používá hodnoty prvků obsažených v přilehlé oblasti k určení nové hodnoty. Filtr uspořádá prvky sousední oblasti v seřazeném pořadí a vybere průměrnou hodnotu. Takže například pro jádro dimenze 3 bude střední hodnota pátá:

Pomocí metod zpracování prostorového obrazu můžete získat řadu zajímavé efekty. Pojďme si některé z nich uvést.

Embossovací efekt. Pomocí operace konvoluce můžete implementovat transformaci, která dodá obrazu efekt embosování.

(1.24)

Binární „pseudo-půltónový“ obrázek. Původní obrázek je zpracován pomocí masky D2 nebo D4: pokud je hodnota pixelu menší než proporcionální hodnota odpovídajícího prvku masky, pak je nastavena na nulu, jinak je mu přiřazeno 255. Maska je aplikována na obrázek bez překrývání . Masky D2 a D4:

,

.

Při použití prostorových procesů mohou vyvstat následující otázky související se zvláštnostmi zpracování pixelů:

Eliminace okrajových efektů;

Hodnota odezvy je mimo limity.

U první otázky jsou možná následující řešení:

Vyloučit pixely ohraničení obrázku z převodu

v tomto případě bude mít výstupní obrázek menší velikosti, nebo namalujte hraniční pixely například černou barvou;

Nezahrnujte odpovídající pixel do součtu, rovnoměrně rozložte jeho váhu mezi ostatní pixely v okolí;

Doplňte (dokončete) původní obrázek přidáním požadovaného počtu pixelů podél okraje. Počet sloupců, které mají být přidány, obvykle závisí na velikosti jádra. Zde jsou dvě možnosti:

• Určete hodnoty pixelů mimo hranice obrázku pomocí extrapolace.

  Uvažujme například hodnotu intenzity blízko hraniční konstanty nebo uvažujme gradient intenzity v blízkosti hraniční konstanty;

Definujte hodnoty pixelů mimo hranice obrazu pomocí zrcadlení.

Škálujte získané hodnoty pro pozitivní odezvy filtru;

Pokud je odezva filtru negativní, vezměte kterýkoli z nich absolutní hodnota(modulo) nebo vést k nule.

Také v této části stojí za to uvést možnou „klasifikaci“ šumu na obrázku:

Šum soli a pepře - náhodné bílé a černé pixely;

Impulzní šum – náhodné bílé pixely;

Gaussův šum je kolísání intenzity rozložené podle normálního zákona.