Kvantování obrazu. Problém Fourierovy optiky a metody digitálního zpracování obrazu. Vyhlazení barevných přechodů
K metodám schování prostorová oblast lze také považovat za metodu kvantování obrazu, založené na interpixelové závislosti, kterou lze popsat nějakou funkcí. V nejjednodušším případě lze vypočítat rozdíl mezi sousedními pixely; a (nebo a) a nastavte jej jako parametr funkce: 
, kde je diskrétní aproximace rozdílu signálu.
Protože je celé číslo a skutečný rozdíl je reálné číslo, pak dochází k chybám kvantování. U vysoce korelovaných signálů se tato chyba blíží nule: .
Na tato metoda informace jsou skryty úpravou rozdílového signálu. Stegan klíč je tabulka, která přiřazuje konkrétní bit každé možné hodnotě, například:
| -4 | -3 | -2 | -1 | ||||||
| b i |
Pro skrytí i-tého bitu zprávy se vypočítá rozdíl. Pokud v tomto případě b i neodpovídá tajnému bitu, který je třeba skrýt, pak se hodnota nahradí nejbližší hodnotou, pro kterou je taková podmínka splněna. V tomto případě se odpovídajícím způsobem upraví hodnoty intenzity pixelů, mezi kterými byl vypočten rozdíl. Tajná zpráva je extrahována podle hodnoty odpovídající rozdílu.
Uvažujme příklad programu, který implementuje metodu kvantování obrazu
Počáteční údaje jsou standardní.
Krok 2
Prošívaný klíč vypočítáme pomocí modulů (M.28) a (M.29). V tomto případě modul (M.28) vrací všechny možné rozdíly signálu (od -255 do +255) a modul (M 29) vrací hodnoty bitů odpovídající těmto rozdílům.
Hodnoty b i PROTI v tomto případě jsou vypočteny na základě pole červené barevné složky. Navíc pro každý sloupec pole R Součet se vypočítá modulo 2 jeho základních prvků s booleovským přičtením jedné k výsledku součtu u každého třetího prvku. Na konci modulu výsledný vektor b expanduje o délku vektoru. Tedy prvky pole b mají pseudonáhodný charakter. Fragmenty vytvořeného prošívaného klíče jsou znázorněny na Obr. 5.15.
| l- | b= | ||||
| -255 | |||||
| -254 | |||||
| -253 | |||||
| -252 | |||||
| -2 | |||||
| -1 | |||||
Rýže. 6.15. Prošívané fragmenty klíčů
Pojďme nasadit pole kontejnerů S(pole složky modré barvy) do vektoru pomocí modulu (M.16). Nastavíme počáteční index prvku výsledného vektoru, od kterého se budou bity a zprávy vkládat (například ).
Pro výpočet velikosti kroku (pseudonáhodný interval) používáme modul (M.15). Nechte ve stejnou dobu NA := 8.
Krok 4
Algoritmus vkládání je implementován modulem (M.30). Tvorba vektoru binárních dat z řetězce znaků je podobná jako v (M.21) (v tomto případě je však nutné jej nahradit ).
Pro každý bit zprávy se vypočítá index z kontejner vektorový prvek Životopis. Vypočítá se rozdíl mezi sousedními pixely Cvz A C vz-1 Vnitřní smyčka hledá odpovídající rozdílovou hodnotu ve vektoru. Pokud je detekována, je proměnné přiřazena hodnota indexu já, což odpovídá tomuto rozdílu v .
Pokud hodnota neodpovídá aktuálnímu bitu skryté zprávy, pak se provede hledání nejbližšího indexu, na kterém bi rovná se bitu zprávy. Vyhledávání se provádí směrem dolů (L) a nahoru (H) z indexu.
Předběžné přiřazení proměnných na hodnotu ±1000 zajišťuje, že není možné duplikovat předchozí hodnoty, pokud pohyb dolů nebo nahoru nevedl ke splnění nastavené podmínky (druhé je možné, když je index příliš blízko spodní nebo horní hranice vektoru b). Po nalezení hodnot se vybere ta, která je nejblíže počáteční hodnotě.
Intenzita pixelů kontejneru Sv z rovna intenzitě sousedního pixelu zvýšené o hodnotu Sv z -1. Li toto zvýšení vede k tomu, že hodnota intenzity barvy přesahuje rozsah , pak je naopak intenzitě sousedního pixelu Sv z -1 přiřazena hodnota intenzity pixelu Sv z, snížené o částku). Po vložení poslední kousek zpráva, je vnější smyčka přerušena.
Provádíme obrácené skládání vektoru Sv do matice mající rozměr primárního pole S(M.7). Získáme pole S.
Při digitálním zpracování obrazu je spojitý dynamický rozsah hodnot jasu rozdělen do několika diskrétních úrovní. Tento postup se nazývá kvantování. Kvantizér transformuje spojitou proměnnou na diskrétní proměnnou, která nabývá konečného souboru hodnot. Tyto hodnoty se nazývají kvantizační úrovně. V obecný případ transformace je vyjádřena skokovou funkcí (obr. 1.5). Pokud jas obrazového vzorku patří do intervalu (tj. kdy ), pak je původní vzorek nahrazen kvantizační úrovní, kde jsou kvantizační prahy. Předpokládá se, že dynamický rozsah hodnot jasu je omezený a rovný .
1.5 Funkce popisující kvantování
Úkolem sestavení kvantizéru je určit hodnoty prahů a úrovní. Nejjednodušším způsobem, jak tento problém vyřešit, je rozdělení dynamický rozsah ve stejných intervalech. Toto řešení však není nejlepší. Pokud jsou hodnoty jasu většiny obrazových vzorků seskupeny například v „tmavé“ oblasti a počet úrovní je omezený, je vhodné kvantovat nerovnoměrně. V „tmavé“ oblasti byste měli kvantovat častěji a ve „světlé“ oblasti méně často. Tím se sníží kvantizační chyba.
Problém konstrukce kvantizéru lze tedy formulovat jako problém nalezení optimálních hodnot, které splňují nějaké optimalizační kritérium. Obvykle je pro pevný počet úrovní kvantizer optimalizován podle kritéria minimální střední kvadratické chyby
(1.12)
za předpokladu, že je jas náhodná hodnota se známou hustotou pravděpodobnosti.
Střední kvadratická chyba kvantizace (1.12) je rovna
. (1.13)
Diferencováním (1.13) vzhledem k proměnným a přirovnáním derivací k nule získáme nelineární rovnice
.
Je třeba poznamenat, že extrémní prahové hodnoty jsou určeny dynamickým rozsahem jasu. Rovnice (1.14) lze snadno zredukovat do tvaru
.
Z (1.15) vyplývá, že prahy by měly být umístěny uprostřed mezi dvěma sousedními úrovněmi a . Řešení těchto rovnic lze nalézt iterativně. Optimální kvantizér, který splňuje kritérium (1.12), se nazývá Lloyd-Max kvantizér a střední kvadratická chyba pro takový kvantizér je
(1.16)
S rovnoměrným rozložením jasu nelineární rovnice(1.15) lze reprezentovat jako
,
a střední kvadratická chyba je .
V systémech digitální zpracování obrázky mají tendenci snižovat počet úrovní a kvantizačních prahů, protože délka binárního kódového slova, kterým jsou kvantované vzorky reprezentovány v počítači, závisí na jejich počtu. Při relativně malém počtu úrovní se však v kvantovaném obrazu objevují falešné kontury. Vznikají kvůli kroková změna jasu kvantovaného obrazu (obr. 1.6) a jsou patrné zejména v plochých oblastech jeho změny.
Falešné kontury výrazně zhoršují vizuální kvalitu obrazu, protože Lidské vidění je zvláště citlivé na kontury. Při jednotném kvantování typických obrázků je vyžadováno alespoň 64 úrovní. Obrázky 1.7.a a 1.7.b ukazují výsledky jednotné kvantizace obrazu „Portrait“ do 256, respektive 14 kvantizačních úrovní.
Obr.1.6. O mechanismu výskytu falešných obrysů
|
|
|
|
|
Obr.1.7. Jednotné výsledky kvantizace |
||
|
|
|
|
|
Obr.1.8. Výsledek nerovnoměrného kvantování |
Obr.1.9. Histogram portrétního obrázku |
|
V tmavých částech obrázku na obr. 1.7.b jsou patrné falešné obrysy. Použití kvantizéru Lloyd-Max umožňuje výrazně snížit jejich úroveň (viz obr. 1.8, kde je také počet úrovní kvantizace 14). Na Obr. Obrázek 1.9 ukazuje histogram jasu obrazu „Portrait“ při 256 kvantizačních úrovních a označuje prahové hodnoty jako . Z obrázku vyplývá, že ty oblasti dynamického rozsahu, ve kterých jsou seskupeny hodnoty jasu vzorků, jsou častěji kvantovány.
Aby se zabránilo nerovnoměrnému kvantování, které nelze provést pomocí standardního ADC, jsou použity nelineární transformace (obr. 1.10). Vzorek původního obrazu je podroben nelineární transformaci tak, aby hustota rozdělení pravděpodobnosti transformovaných vzorků byla rovnoměrná, tzn. je provedena ekvalizační procedura, která je podrobně popsána v kapitole 2. Poté jsou vzorky kvantovány s jednotným krokem a podrobeny inverzní nelineární transformaci.
Obr.1.10. Kvantování s předběžnou nelineární transformací
Aby se zničily falešné obrysy, Roberts navrhl přidat šum s rovnoměrnou hustotou rozdělení pravděpodobnosti do vzorků jasu před jednotnou kvantizací. Přidaný šum posouvá některé obrazové vzorky na vyšší úroveň a jiné na nižší úroveň. Tím jsou zničeny falešné obrysy. Rozptyl přidaného šumu musí být malý, aby nevedl ke zkreslení obrazu vnímanému jako „sníh“ a zároveň dostatečný ke zničení falešných kontur. Typicky se v intervalu používá rovnoměrně rozložený šum. Výsledky jednotné kvantizace do 14 a 8 úrovní obrazu „Portrait“ s předběžným přidáním šumu jsou uvedeny na obr. 1.11.a a 1.11.b. Při 8 úrovních kvantizace je přidaný šum příliš patrný, ale falešné obrysy jsou téměř úplně zničeny.
|
|
|
|
Obr.1.11. Výsledky rovnoměrného kvantování s předběžným přidáním šumu |
|
Další kvantizační metoda se používá při tisku. Jedná se o metodu generování rastrových binárních (2úrovňových) obrázků z polotónových. Při tisku (například novin nebo časopisů) je obraz tvořen z bílých a černých bodů. K tomu se celý původní snímek rozdělí podle prostorových souřadnic na identické čtvercové bloky. Blok obvykle obsahuje prvky. Ke každému vzorku bloku je přidáno číslo s odpovídajícími souřadnicemi z matice rušivých signálů, jejichž rozměry se rovnají rozměrům bloku. Například čísla se používají jako matice rušivého signálu:
.
Tato operace se opakuje pro všechny bloky. Výsledný obraz je kvantován do dvou úrovní. Na Obr. Obrázek 1.12.a ukazuje polotónový obrázek „Portrait“ s přidaným rušivým signálem. Na Obr. 1.12.b,c ukazují výsledky binární kvantizace obrazu „Portrait“ s přidaným rušivým signálem (obr. 1.12.b) a bez něj (obr. 1.12.c).
|
|
|
|
1.12 Rastrování obrázků |
|
Binární rastrový obrázek poskytuje výrazně lepší vizuální zážitek než běžný binární obrázek. Přenosu jasové stupnice při rastrování je dosaženo změnou geometrických rozměrů bílá skvrna, pozorováno na černém pozadí. Pokud jsou hodnoty „světla“ seskupeny do bloku, pak jsou geometrické rozměry bílé skvrny maximální a rovny se velikosti bloku. S klesajícím jasem se zmenšují i jeho geometrické rozměry. Lidské oko provádí lokální průměrování a vytváří iluzi prohlížení polotónového obrazu. Postup promítání je zvláště účinný při tisku obrázků pomocí vysoké rozlišení, kdy je okem sotva viditelná jediná skvrna.
Definování barevné hloubky
Většina počítačů zobrazuje 8, 16 nebo 24 bitů na pixel. To určuje barevnou hloubku zobrazeného obrázku.
Bez ohledu na to, kolik barev systém zobrazuje, MATLAB dokáže ukládat a zpracovávat obrázky jiné číslo bitů na pixel: 224 barev pro obrázky uint8 RGB, 248 barev pro obrázky uint16 RGB a 2159 barev pro obrázky RGB s dvojnásobnou přesností. Tyto obrazy se nejlépe zobrazují ve 24bitovém systému barev, i když zdroje obrazu nemusí vždy poskytovat tuto barevnou hloubku. Ve většině případů poskytují 16bitové barevné zobrazení.
- Popis určování barevné hloubky systému
- Popis výběru barevné hloubky
Popis barevné hloubky
Následující kód se používá k určení barevné hloubky, kterou může systém zobrazit.
Get(0,"ScreenDepth") ans = 32
MATLAB vrací počet bitů na pixel:
| Význam | Popis |
| 8 | 8bitová reprezentace je zobrazena ve 256 barvách. 8bitové polotónové obrázky jsou nedílná součást 24bitová reprezentace grafické informace. |
| 16 | 16bitová reprezentace obvykle používá 5 bitů na barevnou složku, což se rovná 32 gradacím (tj. 2 5) pro červenou, zelenou a modrou složku. Výsledkem je, že tato reprezentace podporuje 32 768 (tj. 2 15) různé barvy. Některé systémy používají extra bit ke zvýšení počtu zobrazených gradací barev. V našem případě je počet různých barev s 16bitovým zastoupením 64 536 (tedy 2 16). |
| 24 | 24bitové vykreslování využívá 8 bitů pro každou ze tří barevných složek, tzn. 256 (2 8) gradací pro červenou, zelenou a modrá složka. Výsledkem je 16 777 216 (tj. 2 24) různých barev. |
| 32 | 32bitové vykreslování využívá 24 bitů k uložení informací o barvách a dalších 8 bitů k uložení saturace (průhlednosti) dat. Jedná se o takzvaný alfa kanál. |
Popis výběru barevné hloubky
V závislosti na použitém systému můžete nainstalovat různé významy počet bitů na pixel. (To může také souviset s rozlišením grafických objektů. Ve většině případů poskytuje 24bitová reprezentace dobrá vizualizace. Pokud je potřeba použít méně bitů na pixel, lze použít 16bitovou reprezentaci. Při zpracování polotónových obrázků je ve většině případů dostačujících 8 bitů na pixel.
Snížení počtu barev v obrázku
Tato část popisuje způsob snížení počtu barev v indexu resp RGB obrázky X. Uvažujme také metodu difúzního míchání pseudobarvy (dithering). Tato metoda využívá vizuální zvýšení počtu barev v obrázku.
Níže jsou uvedeny stručné popisy funkce pro zmenšení barev v obrázku v aplikaci Obrázek Zpracování Toolbox.
Na systémech s 24bitovým displejem RGB barvy obrázky lze zobrazit v 16 777 216 (tj. 2 24) barvách. Na systémech s menším počtem zobrazovaných barev RGB se obrázky také zobrazí dobře, protože MATLAB automaticky používá aproximaci barev a difúzní míchání pseudo barev.
Indexové obrázky mohou mít problémy s velký počet barvy. V zásadě omezeno na 256 barev. Důvodem jsou následující důvody:
- Na 8bitových zobrazovacích systémech se při vykreslování indexových obrázků, které mají více než 256 barev, používá rozklad, protože ne všechny barvy může systém reprezentovat.
- V některých systémech nemůže mít paleta v zásadě více než 256 pozic.
- Pokud indexový obrázek obsahuje více než 256 barev, MATLAB uloží obrazová data do pole nikoli ve formátu uint8, ale ve formátu s dvojnásobnou přesností. Díky tomu se ukládá více dat, protože každý pixel zabírá 64 bitů.
- Soubory obrázků velké velikosti Je vhodné nahrávat ve formátu, který používá pro vykreslení 256 barev. Pokud při záznamu (pomocí funkce imwrite) ve stejném formátu mají obrázky více než 256 barev, pak jsou v budoucnu možné chyby při vykreslování.
Snížení počtu barev v indexovém obrázku
Pomocí rgb2ind
Funkce rgb2ind převede obrázek RGB na indexový obrázek, čímž se sníží počet zobrazených barev. Při zpracování zdrojového obrazu používá funkce následující metody aproximace barev:
- Kvantování
- Jednotná kvantifikace
- Kvantování nejnižšího rozptylu
- Zobrazení palety
Kvalita výsledného obrázku závisí na zvolené metodě aproximace, barevném rozsahu zdrojového obrázku a použití ditheringu. Všimněte si, že výsledek metod také velmi závisí na konkrétním obrázku.
Kvantování
Kvantování vede ke snížení počtu barev v obraze. Funkce rgb2ind používá kvantizaci jako součást algoritmu redukce barev. Funkce rgb2ind podporuje dvě kvantizační metody: rovnoměrné kvantování a kvantování s nejmenším rozptylem.
Při zvažování této problematiky se používá pojem krychle RGB barvy. Barevná kostka RGB je trojrozměrné pole všech barev, které jsou definovány pro daný typ dat. Protože obrázky v MATLABu mohou být reprezentovány v různé formáty(uint8, uint16 nebo double), pak to ovlivní vzorkování barev v kostce RGB.
Jednotné kvantování. K provedení jednotné kvantizace použijte funkci rgb2ind s příslušnými parametry.
Níže je uveden příklad jednotné kvantizace. Druhý argument ovlivňuje diskrétnost kvantování.
RGB = imread("papriky.png"); = rgb2ind(RGB, 0,1);
Obrázek demonstruje jednotnou kvantizaci obrázku reprezentovaného ve formátu uint8. Pro usnadnění obrázek ukazuje dvourozměrný výsek barevné kostky, kde červená je 0 a rozsah zelené a azurové je .
Kvantování s nejmenším rozptylem. Pro implementaci kvantizace s nejmenší disperzí se používá funkce rgb2ind, udávající maximální počet barev ve výsledném obrázku. Toto číslo určuje počet buněk, do kterých bude barevná kostka RGB rozdělena. Podívejme se na příklad implementace kvantizační metody pro vytvoření indexového obrazu pomocí 185 barev.
RGB = imread("papriky.png"); = rgb2ind(RGB,185);
Kvantizační metoda s nejmenším rozptylem je založena na seskupování pixelů na základě odchylek mezi jejich hodnotami. Tito. vybraný pixel musí mít nejmenší celkovou odchylku od všech pixelů ve skupině.
Snížení počtu barev v indexovém obrázku
Funkce imapprox se také používá ke snížení počtu barev v obrázku. Funkce imapprox využívá některé aproximační techniky. V podstatě funkce imapprox nejprve použije funkci ind2rgb k převodu obrázku do RGB a poté použije funkci rgb2ind k převodu na indexový obrázek s počtem změněných barev.
Příklad.
Podívejme se na příklad generování obrázků, které obsahují 128 a 16 barev pomocí funkcí rgb2ind a imapprox.
L=imread("papriky.png"); obrázek,imshow(L);
Původní obrázek
L=im2double(L); = rgb2ind(L, 128); obrázek,imshow(x,mapa);
Obrázek se 128 barvami
Imapprox(x,mapa,16); obrázek,imshow(Y, nová mapa);
Obrázek s 16 barvami
Kvalita zpracovaného obrazu závisí na použité metodě aproximace, na počtu barev v původním snímku a na tom, zda je použita metoda rozkladu nebo ne. Všimněte si, že různé metody poskytují různé výsledky pro různé obrázky.
Vyhlazování barevné přechody
Metoda difúzního míchání pseudo barev (dithering)
Při použití funkcí rgb2ind nebo imapprox ke snížení počtu barev v obrázku je kvalita výsledného obrázku o něco nižší. Je to způsobeno snížením počtu barev, ve kterých je obrázek zobrazen. Funkce rgb2ind i imapprox používají dithering. To má za následek vizuální zvýšení počtu zobrazených barev. Metoda rozkladu mění barvy sousedních pixelů tak, aby se průměrná barva okolí přibližovala původní barvě RGB.
Podívejme se na příklad toho, jak metoda ditheringu funguje.
- Čtení a vizualizace původního obrázku. rgb=imread("cibule.png"); imshow(rgb);
- Vytvořte indexový obrázek s osmi barvami bez použití rozkladu barev. =rgb2ind(rgb,8,"nodither"); obrázek, imshow(X_no_dither,map);
- Vytvořte osmibarevný indexový obrázek pomocí rozkladu. =rgb2ind(rgb,8,"rozklad"); obrázek, imshow(X_dither,map);
Všimněte si, že zpracování obrazu pomocí metody rozkladu vede k vizuálnímu zvýšení zobrazených barev. Existuje však riziko falešných obrysů.
Provádění převodu barevného prostoru
Převod barevných dat mezi barevnými prostory
Nejběžnější v Image Processing Toolbox pro popis digitální obrázky použitý barevný systém RGB. V tomto případě sloupce palety představují intenzity červené, zelené a modré složky. Paletové obrazy mohou mít libovolnou barevnou hloubku, i když nejrozšířenějšími paletovými obrazy jsou ty s barevnou hloubkou 4 a 8 bitů na pixel.
Existují dva známé přístupy k zobrazování barev z většího barevného prostoru v menším. Jedním z nich je, že barvy, které jsou mimo barevné pole, jsou převedeny na nejbližší barvy uvnitř barevného pole. Tento přístup se nazývá ořezávání. Druhou metodou je metoda komprese. Spočívá v tom, že každá barva na vstupu, bez ohledu na to, zda spadá do barevného pole výstupního zařízení nebo ne, je redukována na jinou barvu než barevný rozsah výstupní zařízení (samozřejmě ne náhodně). Stávající metody převody barevného prostoru se od sebe liší třemi hlavními způsoby: kompresí barevný rozsah, mapování tónů (přinášející dynamický rozsah vstupní zařízení na výstup) a zobrazení bílé tečky.
Převody mezi barevnými prostory závislými na zařízení
Uvažujme dva barevné prostory RGB a CMYK. Jakákoli barva v prostoru RGB je tvořena součtem různá množstvíčervené, zelené a modré komponenty. Když se hodnoty všech složek rovnají nule, vytvoří se černá barva. Pokud všechny komponenty berou maximum možný význam, pak se tvoří bílá barva. Pojem „bílá barva“ je však přibližný. Faktem je, že složky RGB poskytují pouze dobrou aproximaci a skutečnou bílou barvu lze získat pouze sečtením všech jejích spektrálních složek, a nikoli pouze R, G a B. V prostoru CMYK je bílé barvy dosaženo vynulováním všech jejích spektrálních složek. komponenty a azurová (C, azurová), purpurová (M, purpurová) a žlutá (Y, žlutá) slouží k vytvoření dalších barev. Nevýhodou tohoto barevného prostoru je, že zařízení, která jej používají, nemohou zobrazovat jasné a syté barvy.
Barevné prostory RGB a CMYK jsou závislé na zařízení, protože barva v nich je svázána se zařízením, pro které jsou tyto hodnoty nastaveny. „Zařízením“ může být tiskárna, skener, monitor atd. Ve skutečnosti každá tiskárna, skener nebo monitor zobrazí stejný obrázek ve svých vlastních barvách, ačkoli hodnoty RGB, které jim byly dodány, jsou stejné.
Obecně lze barvu popsat souřadnicemi pro tato sada primární barvy nebo chromatické souřadnice a jejich úroveň jasu. Barvu lze popsat pomocí lineární nebo nelineární funkce souřadnic barev nebo souřadnic barevnosti a jasu. Lineární transformace barevné souřadnice představují přechod na novou sadu barev. Stávající systémy barevné souřadnice umožňují kvantitativně popsat barvy a vzorce pro jejich transformaci.
Tabulka ukazuje seznam barevných prostorů závislých na zařízení, které jsou podporovány aplikací pro zpracování obrazu Matlab.
Funkce Účel Účel XYZ Souřadnicový systém pro spektrální primární barvy, který byl vyvinut v roce 1931 CIE (International Commission on Illumination). xyY, uvL, u"v"L a L*a*b* xyY Popis získávání normalizovaných chromatických hodnot. Složka Y, stejně jako v systému XYZ, představuje jas. XYZ uvL Rovnokontrastní souřadnicový systém. L představuje jas a je protějškem Y v XYZ. XYZ u"v"L Evoluce dřívějšího systému k vytvoření barevného prostoru, ve kterém jsou jednotlivé změny barevnosti a jasu vnímány stejně. XYZ Laboratoř* Pokus o zohlednění závislosti vnímání a jasu. L* představuje nelineární škálování L, normalizované s ohledem na některé body. XYZ L*ch V tomto modelu c a h představují sytost a sytost. V polárních souřadnicích se tento systém transformuje Laboratoř*. Laboratoř* sRGB Barevný prostor, který odpovídá barevný gamut průměrný CRT monitor. XYZ a L*a*b* Příklad: Reprezentace obrázků v různých barevných prostorech
Počítáme s obrazem RGB formát do pracovního prostoru MATLABu a převést data barev na barevný prostor XYZ:
Protože myšlenka DPCM je poměrně jednoduchá, pak, jak vyplývá z diagramů na Obr. 4.8 jsou charakteristiky systému redundance redundance obrazu DPCM určeny [pořadí prediktoru P, hodnoty predikčních koeficientů A i , počet kvantizačních úrovní a jejich umístění.
Pořadí prediktoru závisí na statistických charakteristikách obrazu. Typicky, pokud lze sekvenci vzorků modelovat autoregresním Markovovým procesem n-týřádu, pak rozdíly získané pomocí optimálního prediktoru n-týřádu, vytvoří posloupnost nekorelovaných čísel. Obrázky zjevně nejsou Markovovy procesy n-týřádu, ale zkušenosti s kompresí obrazu to ukazují korelační vlastnosti obrazy lze popsat Markovovým procesem třetího řádu, který vede k prediktorům třetího řádu (n=3). Podobně při modelování obrazu bylo zjištěno, že DPCM s prediktory vyššího řádu neposkytuje větší zisky v kvalitě obrazu (jak subjektivní, tak objektivní).
Predikční koeficienty A i lze určit pomocí analýzy střední kvadratické chyby. Nechat G ( k ) - vzorky na skenovací lince, a
( k ) - předpokládané hodnoty těchto vzorků. Je nutné, aby střední kvadratická chyba byla minimální, tzn. Je potřeba najítmin e = E ( g(k) -
}
(4.21)
všude k, i
Toto je známý úkol a pokud proces G ( k ) je stacionární, pak má jeho řešení tvar
,
(4.22)
r (j - i) = E [ g (k - j) g (k -i) ] (4.23)
obvykle nazývaná autokorelační funkce procesu G. Kurzy a i získáme řešením soustavy rovnic (4.22).
Optimální hodnoty predikčních koeficientů závisí na vztazích mezi obrazovými body popsanými autokorelační funkcí. Z definice (4.20) je zřejmé, že v případě stacionárních dat autokorelační funkce se liší od výše uvedené funkce v konstantní hodnotu. U nestacionárních dat funkce r(v rovnici (4.23) závisí na prostorových proměnných a optimální predikční koeficienty by se měly lišit v závislosti na prostorových souřadnicích. To je typické pro obrázky. Naštěstí nestacionární statistické charakteristiky obrazy lze obvykle poměrně dobře aproximovat stacionárními funkcemi, takže neladitelné lineární predikční zařízení poskytuje poměrně dobré výsledky. Při kompresi videoinformace metodou DPCM se chyby obvykle objevují na hranicích zobrazovaných objektů, kde je předpoklad stacionarity splněn v nejmenší míře a v rekonstruovaném obrazu jsou vizuálně vnímány jako abnormálně světlé nebo tmavé body.
Volba počtu kvantizačních úrovní a umístění kvantizačních prahů je částečně kvantitativní a částečně kvalitativní. Umístění kvantizačních prahů lze zjistit pomocí kvantitativních výpočtů. Maxova práce byla první, která uvažovala o nerovnoměrném kvantování, které závisí na distribuční funkci kvantovaného signálu a minimalizuje střední kvadraturu způsobenou omezeným počtem kvantizačních úrovní. Maxův algoritmus nám umožňuje najít optimální umístění přechodové body pro daný počet úrovní kvantizace. Počet úrovní kvantizace se však volí na základě subjektivních kvalitativních úvah.
Minimální počet kvantizačních úrovní jsou dvě (jednociferná čísla) a odpovídá takovému kvantování snímků, ve kterých má rozdíl jasu pevnou (kladnou nebo zápornou) hodnotu. Tato metoda se obvykle nazývá delta modulace, obvod DPCM (obr. 4.8) lze zjednodušit nahrazením kvantizeru omezovačem a prediktorem n čt objednávka na integrátora. Při snižování redundance obrazu pomocí metody delta modulace jsou pozorovány stejné nevýhody jako u delta modulace jiných signálů, jako je řeč, konkrétně prodloužení hran a fragmentační zkreslení. Pokud je však vzorkovací frekvence obrazu zvolena mnohem vyšší než Nyquistova frekvence, pak komprese delta modulace vede k malým (subjektivně znatelným) chybám. Pokud se vzorkovací frekvence blíží Nyquistově frekvenci, pak bude obraz vykazovat větší přetahování okrajů (na okrajích snímků) a drtivé zkreslení (v oblastech s konstantním jasem). Stejně jako u komprese řeči může adaptivní delta modulace snížit tyto chyby. Obecně však platí, že při přenosu obrazu se delta modulace ukázala jako méně účinná než při přenosu řeči.
Kvantování s počtem úrovní větším než dvě umožňuje získat obrazy více Vysoká kvalita. DPCM kompresní systém s 8-úrovňovou (3bitovou) kvantizací at optimální umístění prahy vytváří obrazy, jejichž kvalita je stejná jako v systému PCM s bitovou hloubkou 6 až 8. Výjimkou jsou chyby v blízkosti čar ostrých změn jasu.
Signál z výstupu kvantovacího zařízení musí být samozřejmě zakódován, protože rozdělení pravděpodobnosti kvantovaných rozdílů není rovnoměrné. Úspěšným výběrem kódu (například kód Shannon - Fano nebo Huffman) je možné dále snížit celková rychlost vytváření informací. Pratt poukazuje na to, že při použití Huffmanova kódu je možné snížit rychlost vytváření informace na 2,5 bitů/bod. Toto dodatečné snížení rychlosti musí být zváženo se zvýšenými náklady a složitostí paměti, synchronizátorů a pomocných paměťových registrů potřebných ke spouštění Huffmanových kódů.
Problémy komprese obrazu pomocí DPCM při výběru prvků po řádcích byly diskutovány výše (tj. bodů ležících na aktuální linka skeny). Vzhledem k dvourozměrnému charakteru snímků je možné (a vhodné) rozšířit metodu DPCM tak, aby predikce zohledňovala jas v bodech ležících nejen na aktuálních, ale i na předchozích skenovacích liniích. Schémata komprese DPCM s takovou dvourozměrnou predikcí jsou založena na stejných principech jako schémata pro jednorozměrnou predikci. Vzhledem k tomu, že obrazy jsou charakterizovány přítomností dvourozměrných statistických vztahů, lze doufat, že dvourozměrná predikce poskytne lepší výsledky v kompresi obrazu, protože dekorelace obrazu pomocí operací predikce a odečítání bude prováděna podél dvou souřadnic. Zařízení s prostorovou predikcí totiž poskytují více vysoce kvalitní obrázky. Habibi ukázal, že pomocí dvourozměrného prediktivního zařízení třetího řádu s 8úrovňovou (3bitovou) kvantizací byly získány obrázky, které nebylo možné vizuálně odlišit od originální fotky, zpracované PCM s 11bitovými čísly.
Pro obrazy sestávající ze sekvenčních snímků, jako je televize, lze myšlenky predikce a odčítání spojené s DPCM rozšířit na časovou doménu. V podobné obrázky Jas mnoha bodů se snímek od snímku nemění nebo se mění pomalu. Proto je možné zkonstruovat DPCM kompresní systém, ve kterém je jas dalšího bodu predikován na základě jasu dvourozměrné sady bodů aktuálního snímku a odpovídajících bodů předchozích snímků. V praxi nemůže být pořadí časové predikce vysoké, protože pro každý časový člen je nutné mít paměťové zařízení, kde by byl uložen celý rámec. Simulace s prediktorem třetího řádu, ve kterých byly k predikci použity body nacházející se v aktuálním (a předchozích snímcích vlevo od a nad dotyčným bodem), ukázaly, že velmi pěkné obrázky s průměrnou bitovou hloubkou 1 bit/bod.
4.3.3. Schémata pro snížení redundance obrazu se zpracováním v transformační doméně
Abychom vysvětlili hlavní operace prováděné systémem komprese videa se zpracováním v transformační doméně, přejděme ke kovarianční matici definované vztahem (4.20). matice [ Cg] popisuje korelaci obrazových vzorků v rovině ( x, y), což je souřadnicová rovina obrazu. Důležitá metoda více proměnných Statistická analýza slouží ke studiu pole dat nejen v jejich přirozených souřadnicích, ale také v souřadnicových systémech s výhodnějšími vlastnostmi. Zejména souřadnicové systémy založené na vlastních číslech a vlastních vektorech se ukázaly jako velmi užitečné kovarianční matice
[C g] = [F] [
] [ Ф ] T =
, (4.24)
kde [ F] - matice složená z ortogonálních sloupců vlastních vektorů F i A [ ] - diagonální matice vlastních čísel.
Maticově definovaná transformace souřadnic vlastní vektory [F], má vlastnost, že transformuje dané polečísla v jiném s nekorelovanými prvky a výsledné složky mají klesající rozptyly. Nechť jsou vlastní čísla matice uspořádána v sestupném pořadí a očíslována tak
Přitahuje pozornost
Například starý dobrý formát GIF používá paletu až 256 barev. Pokud chcete uložit sérii svých selfie jako animaci GIF (koho by to zajímalo), pak první věc, kterou byste měli udělat, je přesněji program, který k tomu použijete, budete muset udělat - vytvořit paletku. Můžete použít statickou paletu, například webové bezpečné barvy, kvantizační algoritmus se ukáže jako velmi jednoduchý a rychlý, ale výsledek nebude příliš dobrý. Na základě barev na obrázku můžete vytvořit optimální paletu, která poskytne výsledek vizuálně nejvíce podobný originálu.
Existuje několik algoritmů pro vytvoření optimální palety, z nichž každý má své klady a zápory. Nebudu čtenáře obtěžovat únavnou teorií a vzorci, za prvé jsem líný a za druhé to většinu lidí nezajímá - jednoduše projdou článek a prohlížejí si obrázky.
Dále vás čeká nudný a nepochopitelný příběh o metodě středního řezu, Floyd-Steinbergově algoritmu rozptylu chyb (kvantizační šum) (a nejen), zvláštnostech vnímání barev lidským okem a také trochu kódových sraček. .
Pozadí
Kdysi dávno, když byla Nokia teplá a trh s chytrými telefony dominoval tube a majitelé smartphonů se hrdě nazývali „lidé smartphonů“, v těch dávných dobách jsem psal jednoduché programy v pythonu pro řadu60. Na jednoho z nich jsem narazil onehdy při prohrabávání archivů. GifTool je program pro tvorbu GIF animací ze sady obrázků. V něm jsem implementoval kvantizaci pomocí metody mediánových řezů, kompresního algoritmu LZW, celá struktura souboru byla vytvořena nezávisle a pro zmenšení výsledné velikosti souboru byla použita průhlednost pro pixely, které se na dalším snímku nezměnily. Chtěl jsem si osvěžit paměť a podívat se, jak to funguje. Otevřel jsem kód a... Ten pocit, když nemůžete přijít na svůj posraný kód z doby před deseti lety. Tehdy jsem o PEP8 nevěděl, takže čitelnost kódu byla o něco menší než žádná (v té době jsem měl rád minimalismus, jako mnoho začínajících programátorů). Ukápla jsem pár slz, odplivl jsem si to, předělal jsem to v PyCharm, přišel jsem na to, jak implementovat metodu mediánových sekcí, a rychle jsem vytvořil „špinavý“ skript. Funguje! Paleta je vytvořena, výstupní obrázek je snesitelný. A pak jsem začal přemýšlet, jestli bych toho mohl dosáhnout nejlepší výsledky aby se obraz vizuálně co nejvíce přiblížil originálu.
Takže - metoda středního řezu. Je to pekelně jednoduché. První věc, kterou musíte udělat, je jedinečné barvy obrázky tvoří kostku RGB. Dále jej ořízněte podél nejdelší strany. Náš rozsah červené je například od 7 do 231 (délka 231-7=224), zelený od 32 do 170 (délka 170-32=138), modrý od 12 do 250 (délka 250-12=238), což znamená kostku „rozřízneme“ podél modré strany. Výsledné segmenty také řežeme podél dlouhé strany atd. dokud nezískáme 256 segmentů. Pro každý segment vypočítejte průměrnou barvu - takto získáme paletu.
Pár obrázků je skoro k tématu, pro názornost
Co lze zde zlepšit? První věc, která vás napadne, je vypočítat průměrnou barvu, ne hloupým sečtením všech barev a dělením jejich počtem [ součet(barva) / počet(barva) ], ale zohledněním toho, kolikrát se každá barva objeví. na obrázku. To znamená, že každou barvu vynásobíme počtem jejích výskytů na obrázku, sečteme výsledné hodnoty a výsledek vydělíme počtem výskytů všech barev daného segmentu v obrázku [ součet(barva *celkem)/součet (celkem)]. Díky tomu mají při výpočtu přednost nejčastěji se vyskytující barvy, ale vzácné barvy také provádějí vlastní úpravy, takže paleta vyjde lépe a vizuální odchylka barev je menší. Pro nejlepší výsledky je vhodné vzít v úvahu i gama, ale to jsem si nechal na později. Druhá není tak zřejmá - střední část nebere v úvahu zvláštnosti vnímání barev lidským okem. Odstíny zelené vnímáme mnohem lépe než odstíny modré. Rozhodl jsem se toto nedorozumění napravit a krychli „zploštit“ – délky stran jsem vynásobil koeficienty z . V důsledku toho bylo více úseků na zelené a červené straně a méně na modré. Nikde jinde jsem na takové řešení nenarazil (možná jsem ho nehledal dobře), ale výsledek je zřejmý.
Nyní máme optimální paletu, samozřejmě ne ideální (vím, že se dá ještě vylepšit), ale dost dobrá. Dalším krokem je indexování barev obrázku. Nejjednodušší možností je, ve kterém segmentu se barva nachází, stejně jako index. Rychlé a snadné. Ale je tu jedno ale, a dokonce ani jedno tento krok vrátíme se.
Existuje další způsob, jak zlepšit kvalitu výsledného obrázku - rozptyl chyb. I zde je vše celkem jednoduché - od indexované barvy odečteme odpovídající barvu palety, dostaneme chybu, rozptýlíme ji po sousedních pixelech podle určitého vzorce (šablony), nejznámějšího Floyd-Steinbergova vzorce, který je to, co jsem použil. Když jsou chyby rozptýlené, ostré přechody mezi barvami jsou rozmazané a vizuálně se zdá, že obraz obsahuje více odstínů (barev). Pokud máte zájem, můžete si podrobně a zajímavě přečíst o rozptylu chyb. Také jsem se rozhodl dokončit tento algoritmus, vynásobením chyby stejnými koeficienty, jak se ukázalo, bylo to velmi dobrý nápad– protože v modré oblasti bylo méně sekcí, došlo v ní k výrazné chybě a bez opravy chyby koeficienty rozptyl přinesl mnoho „šumu“.
Nyní se můžete znovu vrátit k indexování. Rozptýlením chyb měníme barvy pixelů a dostáváme ty, které nejsou v naší RGB kostce (připomínám, že je tvořena výhradně barvami obrázků). Nyní se nemůžete jen podívat, ve kterém segmentu se barva nachází, abyste mohli přiřadit index. Řešení bylo nalezeno okamžitě - hledání nejbližší barvy v paletě. V tento vzorec Dosadil jsem stejné koeficienty. Při porovnání výsledků výběru barvy palety na základě indexu segmentu, který obsahuje původní barvu, a výsledků hledání nejbližší barvy jsem jasně viděl, že nejbližší barva často končí v sousedním segmentu. Pokud je zdrojová barva blíže středu segmentu, pak index segmentu odpovídá indexu barvy v paletě, ale čím blíže je zdrojová barva k okrajům segmentu, spíše, že nejbližší barva bude v sousedním segmentu. Obecně jediný správná cesta indexování – vyhledá nejbližší barvu v paletě. Vyhledávání má ale nevýhodu – je pomalé, velmi pomalé. Psát drtič čísel v Pythonu je špatný nápad.
No, chtěl jsem to vysvětlit ve zkratce, ale ukázalo se, že je to celá snůška nesrozumitelného psaní. Doufám, že napíšu lepší kód, než vysvětluji, takže zde je odkaz na github. Kód byl několikrát přepisován, nejprve se vylepšoval algoritmus, až jsem nebyl s výsledkem spokojen, pak se ukázalo, že při zpracování fotografií zabíral příliš mnoho RAM (nejprve jsem to testoval na malých obrázcích), musel jsem přenést kostka RGB, střední sekce a mapa pixelů do databáze (sqlite). Skript pracuje velmi pomalu, ale výsledek je lepší než kvantování pomocí PIL/Pillow a GIMPu (v něm se tato operace nazývá indexování).
Vizuální ukázka:
Originál 
Výsledek kvantizace v GIMPu, optimální paleta 256 barev + Floyd-Stenberg rozmazání barev (normální) 
Výsledek kvantizace PIL/Pillow image.convert(mode="P", dither=PIL.Image.FLOYDSTEINBERG, paleta=PIL.Image.ADAPTIVE, colors=256) 
Výsledek kvantizace mým kódem 
Na co si dát pozor: rozptyl chyb GIMPu je velmi hlučný, PIL/Pillow vytváří nepříliš optimální paletu a prakticky nerozptyluje chyby (ostré přechody mezi barvami).
Pokud nevidíte rozdíl, podívejte se na další příklady na githubu.
P.S.: existuje úžasný program Color Quantizer, který se s tímto úkolem vypořádá lépe a rychleji, takže můj scénář nemá praktický význam, vznikl výhradně ze „sportovního“ zájmu.
UPD: aktualizoval projekt na githubu. Přidán kvantizační algoritmus Octree, oblíbené vzorce rozptylu chyb, hledání nejbližší barvy podle průměrné hodnoty červené.
