Popis nástroja Image Processing Toolbox. Prechod od spojitých signálov a transformácií k diskrétnym

Pri digitálnom zobrazovaní je nepretržitý dynamický rozsah hodnôt jasu rozdelený do niekoľkých samostatných úrovní. Tento postup sa nazýva kvantovanie. Kvantizér transformuje spojitú premennú na diskrétnu premennú, ktorá nadobúda konečnú množinu hodnôt. Tieto hodnoty sa nazývajú kvantizačné úrovne. AT všeobecný prípad transformácia je vyjadrená skokovou funkciou (obr. 1.5). Ak jas obrazovej vzorky patrí do intervalu (tj keď ), potom je pôvodná vzorka nahradená kvantizačnou úrovňou , kde sú kvantizačné prahy. Predpokladá sa, že dynamický rozsah hodnôt jasu je obmedzený a rovný .

1.5 Funkcia popisujúca kvantovanie

Úlohou konštrukcie kvantizátora je určiť hodnoty prahov a úrovní. Najjednoduchší spôsob Riešením tohto problému je rozdelenie dynamický rozsah v rovnakých intervaloch. Toto riešenie však nie je najlepšie. Ak sú hodnoty jasu väčšiny vzoriek obrázkov zoskupené napríklad v „tmavej“ oblasti a počet úrovní je obmedzený, potom je vhodné kvantovať nerovnomerne. V "tmavej" oblasti by ste mali kvantovať častejšie a menej často v "svetlej". Tým sa zníži kvantizačná chyba.

Problém konštrukcie kvantizátora teda možno formulovať ako problém nájsť optimálne hodnoty a splniť nejaké optimalizačné kritérium. Zvyčajne je kvantizér pre pevný počet úrovní optimalizovaný podľa kritéria minimálnej strednej štvorcovej chyby

(1.12)

za predpokladu, že je jas náhodná hodnota so známou hustotou pravdepodobnosti.

Chyba kvantovania rms (1.12) sa rovná

. (1.13)

Diferencovaním (1.13) vzhľadom na premenné a prirovnaním derivácií k nule dostaneme nelineárne rovnice

.

Treba poznamenať, že extrémne prahové hodnoty sú určené dynamickým rozsahom jasu. Rovnice (1.14) sa dajú jednoducho zredukovať do tvaru

.

Z (1.15) vyplýva, že prahy by mali byť umiestnené v strede medzi dvoma susednými úrovňami a . Riešenie týchto rovníc možno nájsť iteračne. Optimálny kvantizér, ktorý spĺňa kritérium (1.12), sa nazýva Lloyd-Max kvantizér a stredná kvadratická chyba pre takýto kvantizér je

(1.16)

Pri rovnomernom rozložení jasu možno nelineárne rovnice (1.15) znázorniť ako

,

a stredná kvadratická chyba je .

V systémoch digitálne spracovanie obrázky majú tendenciu znižovať počet úrovní a kvantizačných prahov, pretože dĺžka binárneho kódového slova, ktoré predstavuje kvantované hodnoty v počítači, závisí od ich počtu. Avšak s relatívne malý početúrovne sa na kvantovanom obrázku objavia falošné kontúry. Vznikajú v dôsledku prudká zmena jasu kvantovaného obrazu (obr. 1.6) a sú badateľné najmä v jemných oblastiach jeho zmeny.

Falošné kontúry výrazne zhoršujú vizuálnu kvalitu obrazu, pretože. ľudské videnie je obzvlášť citlivé na kontúry. Pre jednotné kvantovanie typických obrázkov je potrebných aspoň 64 úrovní. Obrázky 1.7.a a 1.7.b znázorňujú výsledky rovnomernej kvantizácie obrazu „Portrait“ do 256 a 14 úrovní kvantovania.

Obr.1.6. K mechanizmu výskytu falošných kontúr

Obr.1.7. Jednotné výsledky kvantizácie
Obr.1.8. Výsledok nerovnomerného kvantovania	Obr.1.9. Histogram snímky „Portrét“.

V tmavých častiach obrazu na obr. 1.7.b, sú badateľné falošné kontúry. Použitím kvantizéra Lloyd-Max je možné výrazne znížiť ich úroveň (viď obr. 1.8, kde je aj počet úrovní kvantovania 14). Na obr. 1.9 ukazuje histogram jasu snímky „Portrét“ pri 256 kvantizačných úrovniach a prahy označené ako . Z obrázku vyplýva, že tie oblasti dynamického rozsahu, v ktorých sú zoskupené hodnoty jasu vzoriek, sú kvantované častejšie.

Aby sa predišlo nerovnomernému kvantovaniu, ktoré nie je možné vykonať pomocou štandardného ADC, používajú sa nelineárne transformácie (obr. 1.10). Vzorka pôvodného obrazu je podrobená nelineárnej transformácii tak, aby hustota rozdelenia pravdepodobnosti transformovaných vzoriek bola rovnomerná, t.j. vykoná sa ekvalizačný postup, ktorý je podrobne popísaný v kapitole 2. Potom sa vzorky kvantujú s jednotným krokom a podrobia sa inverznej nelineárnej transformácii.

Obr.1.10. Kvantovanie s nelineárnou predtransformáciou

Aby sa zničili falošné obrysy, Roberts navrhol pridanie šumu s jednotnou hustotou pravdepodobnosti k hodnotám jasu pred jednotnou kvantizáciou. Pridaný šum posúva niektoré vzorky obrazu o jednu úroveň vyššie a iné o úroveň nižšie. Tak sa zničia falošné kontúry. Rozptyl pridaného šumu by mal byť malý, aby neviedol k deformáciám vnímaným ako „sneh“ v obraze a zároveň dostatočný na zničenie falošných kontúr. Zvyčajne sa používa rovnomerne rozložený šum na intervale . Výsledky rovnomernej kvantizácie do 14 a 8 úrovní obrazu "Portrét" s predbežným pridaním šumu sú na obr. 1.11.a a 1.11.b. Pri 8 úrovniach kvantizácie sa pridaný šum stáva príliš viditeľným, ale falošné obrysy sú takmer úplne zničené.

Obr.1.11. Rovnomerné výsledky kvantovania s predbežným pridaním šumu

Ďalšia kvantizačná metóda sa používa pri tlači. Toto je metóda na generovanie rastrových binárnych (2-úrovňových) obrázkov z poltónových obrázkov. Pri tlači (napríklad novín alebo časopisov) je obraz tvorený bielymi a čiernymi bodkami. Za týmto účelom je celý pôvodný obrázok rozdelený priestorovými súradnicami na identické štvorcové bloky. Blok zvyčajne obsahuje prvky. Ku každej vzorke bloku sa pridá číslo s príslušnými súradnicami z matice rušivého signálu, ktorého rozmery sa rovnajú rozmerom bloku. Napríklad nasledujúce čísla sa používajú ako matica rušivých signálov:

.

Táto operácia sa opakuje pre všetky bloky. Výsledný obraz je kvantovaný do dvoch úrovní. Na obr. 1.12.a ukazuje obrázok v odtieňoch šedej „Portrét“ s pridaným rušivým signálom. Na obr. 1.12.b, c sú zobrazené výsledky binárnej kvantizácie obrazu „Portrét“ s pridaným rušivým signálom (obr. 1.12.b) a bez neho (obr. 1.12.c).

1.12 Rasterizácia obrázkov

Binárna bitmapa poskytuje oveľa lepší vizuálny zážitok ako bežný binárny obrázok. Prenos šedej stupnice pri skríningu sa dosiahne zmenou geometrických rozmerov biela škvrna pozorované na čiernom pozadí. Ak sú hodnoty „svetla“ zoskupené do bloku, potom sú geometrické rozmery bieleho bodu maximálne a rovnajú sa veľkosti bloku. So znižovaním jasu sa zmenšujú aj jeho geometrické rozmery. Ľudské oko vykonáva lokálne spriemerovanie, čím vytvára ilúziu pozorovania obrazu v odtieňoch šedej. Screening je obzvlášť účinný pri tlači obrázkov pomocou s vysokým rozlíšením keď je okom sotva viditeľná jediná škvrna.

Stanovenie farebnej hĺbky

Väčšina počítačov používa na zobrazenie 8, 16 alebo 24 bitov na pixel. To určuje farebnú hĺbku zobrazeného obrazu.

Bez ohľadu na to, koľko farieb systém zobrazuje, MATLAB dokáže ukladať a spracovávať obrázky iné číslo bitov na pixel: 224 farieb pre obrázky uint8 RGB, 248 farieb pre obrázky uint16 RGB a 2159 farieb pre obrázky RGB s dvojnásobnou presnosťou. Tieto obrázky sa najlepšie zobrazujú v 24-bitovom systéme farieb, aj keď zdroje obrazu nemusia vždy poskytovať túto farebnú hĺbku. Vo väčšine prípadov poskytujú 16-bitové zobrazenie farieb.

• Popis určovania farebnej hĺbky systému
• Popis výberu farebnej hĺbky

Popis farebnej hĺbky

Nasledujúci kód sa používa na určenie farebnej hĺbky, ktorú môže systém zobraziť.

Get(0,"ScreenDepth") ans = 32

MATLAB vráti počet bitov na pixel:

Význam	Popis
8	8-bitové zobrazenie je zobrazené v 256 farbách. 8-bitové obrázky v odtieňoch šedej sú neoddeliteľnou súčasťou 24-bitové znázornenie grafických informácií.
16	16-bitová reprezentácia zvyčajne používa 5 bitov na farebnú zložku, čo sa rovná 32 gradáciám (t. j. 25) pre červenú, zelenú a modrú zložku. Výsledkom je, že táto reprezentácia podporuje 32 768 (tj 2 15) rôznych farieb. Niektoré systémy používajú kúsok navyše na zvýšenie počtu gradácií v zobrazenej farbe. V našom prípade je počet odlišných farieb v 16-bitovej reprezentácii 64,536 (t.j. 2 16).
24	24-bitové vykresľovanie využíva 8 bitov pre každú z troch farebných zložiek, t.j. 256 (2 8) gradácií na červenú, zelenú a modrú zložku. Výsledkom je 16 777 216 (t.j. 2 24) rôznych farieb.
32	32-bitové vykresľovanie využíva 24 bitov na uloženie informácie o farbe a ďalších 8 bitov sa používa na uloženie sýtosti (priehľadnosti) údajov. Toto je takzvaný alfa kanál.

Popis výberu farebnej hĺbky

V závislosti od systému, ktorý používate, môžete nainštalovať rôzne významy počet bitov na pixel. (Môže to súvisieť aj s povolením grafické objekty. Vo väčšine prípadov poskytuje 24-bitová reprezentácia dobrú vizualizáciu. Ak je potrebné použiť menej bitov na pixel, možno použiť 16-bitovú reprezentáciu. Pri spracovaní poltónových obrázkov vo väčšine prípadov postačuje 8 bitov na pixel.

Zníženie počtu farieb na obrázku

Táto klauzula popisuje metódu zníženia počtu farieb v indexe resp RGB obrázky X. Zvážte aj metódu difúzneho pseudomiešania farieb (dithering). Táto metóda využíva vizuálne zvýšenie počtu farieb na obrázku.

Nižšie sú uvedené krátke popisy funkcie na zníženie farieb na obrázku v aplikácii spracovanie obrazu nástrojov.

Na systémoch s 24-bitovým displejom RGB farby obrázky je možné zobraziť v 16 777 216 (t.j. 2 24) farbách. Na systémoch s menším počtom farieb RGB na zobrazenie sa obrázky budú zobrazovať dobre, pretože MATLAB automaticky používa aproximáciu farieb a difúzne rozklady farieb.

Indexové obrázky môžu mať problémy s veľkým počtom farieb. V podstate obmedzené na 256 farieb. Je to spôsobené nasledujúcimi dôvodmi:

• V systémoch s 8-bitovým zobrazením sa pri vykresľovaní indexových obrázkov, ktoré majú viac ako 256 farieb, používa difúzna metóda pseudofarebného rozkladu, pretože nie všetky farby môže systém reprezentovať.
• V niektorých systémoch nemôže mať paleta v zásade viac ako 256 pozícií.
• Ak indexový obrázok obsahuje viac ako 256 farieb, MATLAB uloží obrazové dáta do poľa nie vo formáte uint8, ale vo formáte s dvojnásobnou presnosťou. To vedie k zvýšeniu množstva uložených údajov, pretože každý pixel zaberá 64 bitov.
• Súbory obrázkov veľké veľkosti je žiaduce nahrávať vo formáte, ktorý pri vykresľovaní používa 256 farieb. Ak pri nahrávaní (pomocou funkcie imwrite) v rovnakom formáte majú obrázky viac ako 256 farieb, v budúcnosti sú možné chyby vykresľovania.

Zníženie počtu farieb v indexovom obrázku

Pomocou rgb2ind

Funkcia rgb2ind konvertuje obrázok RGB na indexový obrázok, čím sa zníži počet zobrazených farieb. Pri spracovaní pôvodného obrázka funkcia používa nasledujúce metódy aproximácie farieb:

• Kvantovanie
  • Rovnomerné kvantovanie
  • Kvantizácia najmenšej disperzie
• Paletový displej

Kvalita výsledného obrázku závisí od zvolenej metódy priblíženia, rozsahu farieb pôvodného obrázku a použitia metódy difúzneho rozkladu. Všimnite si, že výsledok metód tiež veľmi závisí od konkrétneho obrázka.

Kvantovanie

Kvantovanie znižuje počet farieb na obrázku. Funkcia rgb2ind využíva kvantizáciu ako súčasť algoritmu redukcie farieb. Funkcia rgb2ind podporuje dve metódy kvantovania: rovnomerné kvantovanie a kvantovanie s najmenším rozptylom.

Pri zvažovaní tejto problematiky sa uplatňuje pojem kocky. RGB farby. Farebná kocka RGB je 3D pole všetky farby, ktoré sú definované pre tento typ údajov. Pretože obrázky v MATLABE môžu byť reprezentované v rôznych formátov(uint8, uint16 alebo double), potom to ovplyvní vzorkovanie farieb v kocke RGB.

Rovnomerné kvantovanie. Ak chcete vykonať jednotné kvantovanie, použite funkciu rgb2ind s príslušnými parametrami.

Nižšie je uvedený príklad rovnomerného kvantovania. Druhý argument ovplyvňuje diskrétnosť kvantovania.

RGB = imread("papriky.png"); = rgb2ind(RGB, 0,1);

Obrázok demonštruje rovnomerné kvantovanie obrázka reprezentovaného vo formáte uint8. Pre pohodlie je na obrázku znázornený 2D výrez farebnej kocky, kde červená je 0 a rozsah zelenej a azúrovej je .

Kvantovanie s najmenšou disperziou. Na implementáciu kvantizácie s najmenšou disperziou sa používa funkcia rgb2ind označujúca maximálny počet farieb vo výslednom obrázku. Toto číslo určuje počet buniek, na ktoré sa rozdelí farebná kocka RGB. Uvažujme o príklade implementácie kvantizačnej metódy na vytvorenie indexového obrazu pomocou 185 farieb.

RGB = imread("papriky.png"); = rgb2ind(RGB,185);

Metóda kvantovania s najmenším rozptylom je založená na kombinovaní pixelov do skupín na základe odchýlok medzi ich hodnotami. Tie. vybraný pixel by mal mať najmenšiu celkovú odchýlku od všetkých pixelov v skupine.

Zníženie počtu farieb v indexovom obrázku

Funkcia imapprox sa používa aj na zníženie počtu farieb na obrázku. Funkcia imapprox používa niektoré aproximačné metódy. V podstate funkcia imapprox najprv skonvertuje obrázok do RGB pomocou funkcie ind2rgb a potom ho pomocou funkcie rgb2ind prevedie na indexový obrázok s počtom zmenených farieb.

Príklad.
Uvažujme o príklade generovania obrázkov, ktoré obsahujú 128 a 16 farieb pomocou funkcií rgb2ind a imapprox.

L=imread("papriky.png"); postava,imshow(L);

pôvodný obrázok

L=im2double(L); = rgb2ind(L, 128); obrázok,imshow(x,mapa);

Obrázok so 128 farbami

Imapprox(x, mapa, 16); figure,imshow(Y, newmap);

Obrázok so 16 farbami

Kvalita spracovaného obrazu závisí od použitej metódy priblíženia, od počtu zapnutých farieb pôvodný obrázokči sa používa metóda difúzneho pseudomiešania farieb (dithering) alebo nie. Poznač si to rôzne metódy dať rôzne výsledky pre rôzne obrázky.

Vyhladenie farebných prechodov

Spôsob difúzneho pseudomiešania farieb (dithering)

Pri použití funkcií rgb2ind alebo imapprox na zníženie počtu farieb v obrázku je kvalita výsledného obrázku o niečo nižšia. Je to spôsobené znížením počtu farieb, s ktorými sa obrázok zobrazuje. Obe funkcie – rgb2ind a imapprox – využívajú metódu difúzneho rozkladu. To vedie k vizuálne zväčšenie počet zobrazených farieb. Metóda rozkladu mení farby susedných pixelov tak, aby sa priemerná farba okolia približovala pôvodnej farbe RGB.

Uvažujme o príklade práce metódy difúzneho pseudomiešania farieb (dithering).

1. Čítanie a vizualizácia pôvodného obrazu. rgb=imread("cibuľa.png"); imshow(rgb);

   

2. Vytvorenie indexového obrázka s ôsmimi farbami bez použitia metódy difúzneho rozkladu. =rgb2ind(rgb,8,"nodither"); postava, imshow(X_no_dither, mapa);

   

3. Vytvorenie indexového obrazu s ôsmimi farbami pomocou metódy difúzneho rozkladu. =rgb2ind(rgb,8,"rozklad"); postava, imshow(X_dither,map);

   

   Všimnite si, že spracovanie obrazu metódou difúzneho pseudomiešania farieb (dithering) vedie k vizuálnemu zvýšeniu zobrazovaných farieb. Existuje však riziko falošných kontúr.

   Vykonanie konverzie farebného priestoru

   Prevod farebných údajov medzi farebnými priestormi

   Najčastejšie v Image Processing Toolbox pre popis digitálne zobrazovanie použité farebný systém RGB. V tomto prípade stĺpce palety predstavujú intenzity červenej, zelenej a modrej zložky. Paletové obrázky môžu mať ľubovoľnú farebnú hĺbku, hoci paletované obrázky sú najpoužívanejšie, s farebnou hĺbkou 4 a 8 bitov na pixel.

   Existujú dva prístupy k zobrazovaniu farieb z väčšieho farebného priestoru do menšieho. Jedným z nich je, že farby, ktoré sa nachádzajú mimo farebného poľa, sa prevedú na farby najbližšie v tóne vo vnútri farebného poľa. Tento prístup sa nazýva orezávanie. Druhá metóda je metóda kompresie. Spočíva v tom, že každá farba na vstupe, bez ohľadu na to, či spadá do farebného poľa výstupného zariadenia alebo nie, sa redukuje na inú farbu z farebná škála výstupné zariadenie (samozrejme, ďaleko od náhodne). Existujúce metódy prevody farebného priestoru sa od seba líšia v troch hlavných vlastnostiach: kompresia farebného gamutu, mapovanie tónov (prenesenie dynamického rozsahu vstupného zariadenia na výstupné zariadenie) a zobrazenie bieleho bodu.

   Prevody medzi farebnými priestormi závislými od zariadenia

   Zvážte dva farebné priestory RGB a CMYK. Akákoľvek farba v priestore RGB je vytvorená ako súčet rôzne množstváčervené, zelené a modré komponenty. Keď sa hodnoty všetkých komponentov rovnajú nule, vytvorí sa čierna. Ak všetky zložky nadobudnú maximálnu možnú hodnotu, vytvorí sa biela farba. Pojem "biela farba" je však približný. Faktom je, že komponenty RGB poskytujú len dobrú aproximáciu a skutočnú bielu farbu je možné získať iba pridaním všetkých jej spektrálnych zložiek, a nielen R, G a B. V priestore CMYK sa biela farba dosiahne vynulovaním všetkých jej zložiek, a azúrová (C, Cyan), Magenta (M, Magenta) a Yellow (Y, Yellow) sa v nej používajú na vytvorenie ďalších farieb. Nevýhodou tohto farebného priestoru je, že zariadenia, ktoré ho používajú, nedokážu zobraziť jasné a sýte farby.

   Farebné priestory RGB a CMYK sú závislé od zariadenia, pretože farba v nich je viazaná na konkrétne zariadenie, pre ktoré sú tieto hodnoty nastavené. „Zariadením“ môže byť tlačiareň, skener, monitor atď. V skutočnosti každá tlačiareň, skener alebo monitor zobrazí rovnaký obrázok vo svojich vlastných farbách, hoci RGB hodnoty sú podávané rovnako.

   Vo všeobecnosti možno farbu opísať súradnicami pre túto sadu primárne farby alebo chromatické súradnice a úroveň ich jasu. Farbu možno opísať pomocou lineárnej alebo nelineárnej funkcie farebných súradníc alebo súradníc farbonosnosti a jasu. Lineárne transformácie farebné súradnice predstavujú prechod na novú sadu farieb. Existujúce systémy Farebné súradnice vám umožňujú kvantifikovať farby a ich prevodné vzorce.

   V tabuľke sú uvedené farebné priestory závislé od zariadenia, ktoré sú podporované zobrazovacou aplikáciou Matlab.

   Funkcia	Účel	Účel
   XYZ	Súradnicový systém spektrálnych základných farieb, ktorý v roku 1931 vyvinula CIE (International Commission on Illumination).	xyY, uvL, u "v" L a L * a * b *
   xyY	Popis získania normalizovaných chromatických hodnôt. Zložka Y, rovnako ako v systéme XYZ, predstavuje jas.	XYZ
   uvL	Súradnicový systém s rovnakým kontrastom. L predstavuje jas a je analogický s Y v XYZ.	XYZ
   u"v"L	rozvoj starý systém s cieľom získať farebný priestor, v ktorom sú jednotlivé zmeny vo sýtosti a jase vnímané rovnako.	XYZ
   L*a*b*	Pokus o zohľadnenie závislosti vnímania a jasu. L* je nelineárne škálovanie L, normalizované vzhľadom na niektoré body.	XYZ
   L*ch	V tomto modeli c a h predstavujú sýtosť a sýtosť. AT polárne súradnice tento systém je prevedený na L*a*b*.	L*a*b*
   sRGB	Farebný priestor, ktorý zodpovedá farebnému gamutu priemerného CRT monitora.	XYZ a L*a*b*

   Príklad: Znázorňovanie obrázkov v rôznych farebných priestoroch

   Obrázok považujeme za v RGB formát v pracovnom priestore MATLAB a konvertovať farebné dáta do farebný priestor XYZ:

   

Priťahuje pozornosť

Napríklad starý dobrý vo formáte gif používa paletu s maximálne 256 farbami. Ak si chcete uložiť sériu svojich selfie ako gif-animáciu (kto by to potreboval), tak prvá vec, ktorú si, alebo skôr program, ktorý na to použijete, bude musieť vytvoriť paletu. Môžete použiť statickú paletu, napríklad farby bezpečné pre web, kvantizačný algoritmus sa ukáže ako veľmi jednoduchý a rýchly, ale výsledok nebude veľmi dobrý. Na základe farieb na obrázku môžete vytvoriť optimálnu paletu, ktorá vám poskytne vizuálne najpodobnejší výsledok ako originál.

Existuje niekoľko algoritmov na vytvorenie optimálnej palety, z ktorých každý má svoje výhody a nevýhody. Nebudem obťažovať čitateľa únavnou teóriou a vzorcami, po prvé som príliš lenivý, po druhé, väčšina o to nemá záujem - jednoducho si prelistujú článok, prezerajú si obrázky.

Ďalej tu nájdete nudný a nepochopiteľný príbeh o metóde mediánového rezu, algoritme rozptylu chýb (kvantizačný šum) podľa Floyda-Steinberga (nielen), vlastnostiach vnímania farieb ľudského oka, ako aj niektorých posraný kód.

pozadie

Kedysi dávno, keď bola Nokia teplá a na trhu smartfónov dominovala lampa a majitelia smartfónov sa hrdo nazývali „výrobcovia smartfónov“, v tých starých časoch som písal jednoduché pythonové programy pre series60. Na jeden z nich som natrafil pri prehrabávaní sa v archívoch. GifTool je program na vytváranie gif animácií zo sady obrázkov. V ňom som implementoval kvantizáciu metódou mediánovej sekcie, kompresným algoritmom LZW, celá štruktúra súboru bola vytvorená samostatne, pre pixely, ktoré sa na ďalšej snímke nezmenili, bola použitá priehľadnosť na zmenšenie výslednej veľkosti súboru. Chcel som si osviežiť pamäť, vidieť, ako to funguje. Otvoril som kód a... Ten pocit, keď nevieš rozlúštiť svoj desať rokov starý kód. Vtedy som o PEP8 nevedel, takže čitateľnosť kódu bola o niečo menšia ako žiadna (potom sa mi páčil minimalizmus, ako mnohým začínajúcim programátorom). Uronil som slzu, odpľul, prerobil som v PyCharm, prišiel som na to, ako implementovať metódu strednej sekcie, rýchlo som nahodil „špinavý“ skript. Tvorba! Paleta je vytvorená, výstupný obrázok je znesiteľný. A potom som sa uhryzol - môžem dosiahnuť najlepšie výsledky aby sa obraz vizuálne čo najviac priblížil originálu.

Takže - metóda strednej časti. Je to jednoduché až na hanbu. Prvým krokom je vytvorenie kocky RGB zo všetkých jedinečných farieb obrázka. Potom ho odrežte pozdĺž najdlhšej strany. Napríklad máme rozsah červenej od 7 do 231 (dĺžka 231-7=224), zelenej od 32 do 170 (dĺžka 170-32=138), modrej od 12 do 250 (dĺžka 250-12=238), tak kocku "prekrojíme" po modrej strane. Výsledné segmenty sú tiež rezané pozdĺž dlhej strany atď. kým nezískame 256 segmentov. Pre každý segment vypočítajte priemernú farbu - takto získame paletu.

Pár obrázkov takmer k téme, kvôli prehľadnosti

Čo sa tu dá zlepšiť? Prvá vec, ktorá vás napadne, je vypočítať priemernú farbu nie hlúpym sčítaním všetkých farieb a delením ich počtom [ suma(farba) / počet(farba) ], ale s prihliadnutím na to, koľkokrát sa každá farba vyskytuje na obrázku. . To znamená, že každú farbu vynásobíme počtom jej výskytov na obrázku, získané hodnoty sčítame, výsledok vydelíme počtom výskytov na obrázku všetkých farieb tohto segmentu [ súčet(farba * súčet) / súčet(celkom )]. Výsledkom je, že pri výpočte majú prednosť najčastejšie sa vyskytujúce farby, ale vzácne farby si robia aj vlastné úpravy, takže paleta je lepšia, vizuálna odchýlka farieb je menšia. Pre najlepšie výsledky je žiaduce brať do úvahy aj gama, ale to som si nechal na neskôr. Druhá nie je taká zrejmá - stredná časť vôbec nezohľadňuje zvláštnosti vnímania farieb. ľudské oko. Oveľa lepšie vnímame odtiene zelenej ako odtiene modrej. Toto nedorozumenie som sa rozhodol napraviť a kocku som „sploštil“ – dĺžky strán som vynásobil koeficientmi z tohto článku. Výsledkom je, že na zelenej a červenej strane je viac sekcií a na modrej menej. Nikde inde som také riešenie nevidel (možno som zle hľadal), ale výsledok je zrejmý.

Teraz máme optimálnu paletu, samozrejme nie ideálnu (viem, že sa dá ešte vylepšiť), ale dosť dobrá. Ďalší krok– indexovanie farieb obrazu. Najjednoduchšou možnosťou je, v ktorom segmente sa farba nachádza, toto je index. Rýchle a jednoduché. Existuje však jedno ale, a dokonca ani jedno tento krok budeme späť.

Existuje ďalší spôsob, ako zlepšiť kvalitu výsledného obrazu - rozptyl chýb. Aj tu je všetko celkom jednoduché - od indexovanej farby odčítame zodpovedajúcu farbu palety, dostaneme chybu, rozptýlime ju po susedných pixeloch podľa určitého vzorca (šablóny), najznámejšieho Floyd-Steinbergovho vzorca , použil som to. Pri rozptýlení chýb sú ostré prechody medzi farbami rozmazané a vizuálne sa zdá, že obrázok obsahuje viac odtieňov (farby). Ak máte záujem, môžete si prečítať o rozptyle chýb podrobne a zaujímavo. Tiež som sa rozhodol dokončiť tento algoritmus vynásobením chyby všetkými rovnakými koeficientmi, ako sa ukázalo, bolo to veľmi dobrý nápad- keďže v modrom rozsahu bolo menej prierezov, získala sa v ňom významná chyba a bez korekcie chyby koeficientmi rozptyl priniesol veľa „šumu“.

Teraz sa môžete znova vrátiť k indexovaniu. Rozhadzovaním chýb meníme farby pixelov a získavame tie, ktoré nie sú v našej kocke RGB (pripomeňme, že je tvorená výlučne farbami obrázka). Teraz sa pri priraďovaní indexu nemôžete len pozrieť na to, v ktorom segmente sa farba nachádza. Riešenie sa našlo okamžite – hľadanie najbližšej farby v palete. AT tento vzorec Dosadil som všetky rovnaké koeficienty. Pri porovnaní výsledkov výberu farby palety podľa indexu segmentu, ktorý obsahuje pôvodnú farbu a výsledkov vyhľadávania najbližšej farby, som jasne videl, že najbližšia farba často končí v susednom segmente. Ak je zdrojová farba bližšie k stredu segmentu, potom index segmentu zodpovedá indexu farieb v palete, ale čím bližšie je zdrojová farba k okrajom segmentu, tým je pravdepodobnejšie, že najbližšia farba bude byť v susednom segmente. Vo všeobecnosti jediné správna cesta indexovanie - hľadanie najbližšej farby v palete. Ale vyhľadávanie má mínus - je pomalé, veľmi pomalé. Písať drvič čísel v pythone je zlý nápad.

No, chcel som to v skratke vysvetliť, ale ukázalo sa, že je to celá kopa nezrozumiteľných spisov. Dúfam, že kódujem lepšie, ako vysvetľujem, takže tu je odkaz na github. Kód sa niekoľkokrát prepisoval, najskôr sa vylepšoval algoritmus, kým mi výsledok nevyhovoval, potom sa ukázalo, že pri spracovaní fotografií žerie príliš veľa RAM (najskôr som to testoval na malých obrázkoch), musel som preniesť RGB kocka, stredná sekcia a mapa pixelov do databázy ( sqlite). Skript je veľmi pomalý, ale výsledok je lepší ako kvantovanie pomocou PIL / Pillow a GIMP (v ňom sa táto operácia nazýva indexovanie).

Vizuálna ukážka:

Originál

Výsledok kvantovania v GIMPe, optimálna paleta pre 256 farieb + farebný rozklad podľa Floyda-Stenberga (normálne)

Výsledok kvantizácie PIL/Vankúš image.convert(mode="P", dither=PIL.Image.FLOYDSTEINBERG, paleta=PIL.Image.ADAPTIVE, colors=256)

Výsledok kvantizácie podľa môjho kódu

Na čo si dať pozor: rozptyl chýb GIMPu je veľmi „hlučný“, PIL/Vankúš vytvára neoptimálnu paletu a takmer žiadne rozptýlenie chýb (ostré prechody medzi farbami).
Ak nevidíte rozdiel, pozrite si ďalšie príklady na github.

P.S.: existuje úžasný program Color Quantizer, ktorý sa s touto úlohou vyrovná lepšie a rýchlejšie, takže môj scenár nemá praktický význam, je vyrobený výlučne zo "športového" záujmu.
UPD: aktualizoval projekt na github. Pridaný kvantizačný algoritmus Octree (octree), populárne vzorce rozptylu chýb, hľadanie najbližšej farby podľa priemernej hodnoty červenej.

Anotácia: Úvod. Algoritmus pre jednotné rozdelenie farebného priestoru. Algoritmus rozdelenia frekvencie: myšlienka algoritmu, metóda rozdelenia farebných kociek - lokálne triedené vyhľadávanie. Algoritmus strednej časti. Klastrovacie metódy na kvantovanie obrazu: metóda K-means, metóda grafovej konektivity, hierarchická metóda, zovšeobecnená metóda K-means alebo metóda dynamického zahusťovania. Záver.

12.1. Úvod

Proces konverzie analógový signál v digitálna forma pozostáva z troch etáp: diskretizácia ("Diskretizácia. Antialiasing. Geometrické transformácie rastrových obrázkov"), kvantizácia a kódovanie. Táto prednáška sa zameriava na druhú fázu. Kvantovanie- ide o nahradenie referenčnej hodnoty najbližšou hodnotou zo súboru pevných hodnôt. Pre obrázky to znamená zníženie počtu hodnôt atribútov pre každý pixel alebo jednoduchšie zníženie počtu farieb v obrázku. To si vyžaduje, aby sa kvalita obrazu zhoršovala čo najmenej. Operácia kvantovania sa aplikuje aj na už digitalizovaný materiál.

Kvantovanie je potrebné pre:

• šetrenie pamäte;
• zlepšenie vlastností sekvencií pre kompresiu;
• príprava na ďalšie spracovanie;
• pridávanie efektov.

Vyjadrime sa k týmto bodom podrobnejšie vo vzťahu k obrázkom.

Úspora pamäte sa samozrejme dosahuje znížením nákladov na ukladanie hodnôt atribútov. Mnohé formáty na ukladanie obrázkov 1 , ako napríklad PNG, GIF, namiesto ukladania hodnôt atribútov ukladajú referenčné čísla pre reťazce paliet. Paleta je tabuľka, ktorej riadky obsahujú pevnú hodnotu atribútu. Predtým sa mechanizmus palety používal na vytváranie a zobrazovanie obrázkov na displeji vzhľadom na skutočnosť, že množstvo videopamäte pred rokom 1995 v obvyklom stolný počítač nepresiahla jeden megabajt.

Zlepšenie vlastností sekvencií pre kompresiu sa dosiahne znížením počtu možných hodnôt, a teda zvýšením počtu opakovaní.

Ryža. 12.1.

Príprava na ďalšie spracovanie je potrebná pre niektoré algoritmy, ktorých zložitosť výrazne závisí od počtu možných hodnôt atribútov. V tomto prípade sa často výsledok algoritmu nelíši alebo sa mierne líši.

Kvantizáciu obrazu možno použiť na pridanie umeleckých efektov a zvýraznenie okrajov.

Táto kapitola predpokladá, že hodnoty atribútov obrazových pixelov sú vo farebnom priestore RGB ("Základné pojmy. Farebná reprezentácia v počítačovej grafike"). Pseudokódy algoritmov pre jednoduchosť prezentácie sú uvedené pre 8-bitový obrázok v odtieňoch sivej (256 odtieňov) (pozri obr. 12.1), prevod sa vykonáva na 4-bitový obrázok (16 odtieňov).

Ryža. 12.2.

12.2. Algoritmus pre jednotné rozdelenie farebného priestoru

Zvážte najjednoduchší kvantizačný algoritmus - algoritmus jednotného rozdeľovania farebného priestoru, tiež nazývaný lineárne kvantovanie. Rozdeľme si farebný priestor na rovnaké časti v každom z hlavných smerov (pre RGB existujú tri takéto smery – podľa počtu komponentov). Napríklad v smere modrej alebo zelenej osi (pozri obr. 1.5) rozdelíme kocku na 8 častí a v smere červenej na 4. Do tabuľky sa zadá množina hodnôt, ktoré sa tvoria na priesečníku oddielov. V našom príklade dostaneme 256 hodnôt rovnomerne rozložených v kocke RGB. Transformácia obrazu je ďalej zredukovaná na hľadanie zodpovedajúceho čísla v tabuľke, takže vzdialenosť medzi skutočnou farbou a náhradnou farbou je minimálna. To sa dá rýchlo urobiť pomocou zaokrúhľovania.

// z 256 odtieňov sivej vyrobíme 16 // I(pixel) - atribút pixel // Inew(pixel) nový atribút - referenčné číslo v palete // Paleta - paleta // počet odtieňov v pôvodnom obrázku NOldColors = 256; // počet prvkov v palete NNewColors = 16; // 1. Vyplňte paletu for(i = 0; i< NNewColors; i++) { Palette[i] = i * (NOldColors / NNewColors); } // 2. Вычиcляем новые значения атрибутов foreach(pixel in I) // для каждого пикселя { // округляем, отбрасывая zlomková časť Inew(pixel) = I(pixel) / (NOldColors / NNewColors); ) Výpis 12.1. Algoritmus pre jednotné rozdelenie farebného priestoru

V dôsledku práce tento algoritmus (pozri obr. 12.2) na obrázku sa často objavujú príliš jasné hranice a naopak, detaily sú vymazané. Hlavnými výhodami tohto algoritmu sú však jednoduchosť a vysoká rýchlosť.

Signály vstupujú do systému spracovania informácií spravidla v spojitá forma. Na počítačové spracovanie nepretržité signály je potrebné ich v prvom rade previesť na digitálne. Na tento účel sa vykonávajú operácie diskretizácie a kvantizácie.

Vzorkovanie obrázkov

Vzorkovanie- ide o transformáciu spojitého signálu na postupnosť čísel (počty), teda zobrazenie tohto signálu podľa nejakej konečnej dimenzie. Táto reprezentácia spočíva v premietnutí signálu na daný základ.

Najpohodlnejšie z hľadiska organizácie spracovania a prirodzeného spôsobu diskretizácie je znázornenie signálov vo forme vzorky ich hodnôt (vzoriek) v samostatných, pravidelne rozmiestnených bodoch. Táto metóda sa nazýva skríning a poradie uzlov, v ktorých sa odoberajú vzorky - raster. Interval, počas ktorého sa zaznamenávajú hodnoty spojitého signálu, sa nazýva vzorkovací krok. Recipročný krok sa nazýva vzorkovacia frekvencia,

Základná otázka, ktorá sa vynára v priebehu vzorkovania, je: s akou frekvenciou by sa mali odoberať vzorky signálu, aby sa dal z týchto vzoriek inverzne rekonštruovať? Je zrejmé, že ak sa vzorky odoberajú príliš zriedka, potom nebudú obsahovať informácie o rýchlo sa meniacom signáli. Rýchlosť zmeny signálu je charakterizovaná hornou frekvenciou jeho spektra. Minimálna povolená šírka vzorkovacieho intervalu teda súvisí s najvyššou frekvenciou spektra signálu (k nej nepriamo úmernou).

V prípade jednotnej diskretizácie, Kotelnikovova veta, uverejnenom v roku 1933 v diele „Na šírku pásmaéter a drôt v telekomunikáciách“. Hovorí: ak má spojitý signál spektrum obmedzené frekvenciou , potom ho možno úplne a jednoznačne zrekonštruovať z jeho diskrétnych vzoriek odobratých s periódou , t.j. s frekvenciou.

Obnova signálu sa vykonáva pomocou funkcie . Kotelnikov dokázal, že kontinuálny signál, ktorý spĺňa vyššie uvedené kritériá, môže byť reprezentovaný ako séria:

.

Táto veta sa tiež nazýva vzorkovacia veta. Funkcia je tiež tzv počítacia funkcia alebo Kotelnikov, hoci sériu interpolácií tohto druhu študoval Whitaker v roku 1915. Funkcia počítania má nekonečnú dĺžku a dosahuje svoju maximálnu hodnotu, rovný jednej, v bode, okolo ktorého je symetrický.

Každá z týchto funkcií môže byť považovaná za odpoveď ideálu filter nízke frekvencie (LPF) na delta impulz, ktorý prišiel v čase . Aby sa teda obnovil spojitý signál z jeho diskrétnych vzoriek, musia prejsť cez príslušný dolnopriepustný filter. Treba poznamenať, že takýto filter je nekauzálny a fyzicky nerealizovateľný.

Daný pomer znamená možnosť presná obnova signály s obmedzeným spektrom postupnosťou ich odčítaní. Signály s obmedzeným spektrom sú signály, ktorých Fourierovo spektrum je nenulové iba v obmedzenej oblasti domény definície. Možno im pripísať optické signály, pretože. Fourierovo spektrum obrázkov získaných v optické systémy, je obmedzený z dôvodu obmedzenej veľkosti ich prvkov. Frekvencia je tzv Nyquistova frekvencia. Toto je medzná frekvencia, nad ktorou by vo vstupnom signáli nemali byť žiadne spektrálne zložky.

Kvantovanie obrazu

Pri digitálnom zobrazovaní je nepretržitý dynamický rozsah hodnôt jasu rozdelený do niekoľkých samostatných úrovní. Tento postup sa nazýva kvantovanie. Jeho podstata spočíva v transformácii spojitej premennej na diskrétnu premennú, ktorá nadobúda konečný súbor hodnôt. Tieto hodnoty sa nazývajú kvantizačné úrovne. Vo všeobecnom prípade je transformácia vyjadrená skokovou funkciou (obr. 1). Ak intenzita obrazovej vzorky patrí do intervalu (t.j. kedy ), potom sa pôvodná vzorka nahradí kvantizačnou úrovňou , kde – kvantizačné prahy. Predpokladá sa, že dynamický rozsah hodnôt jasu je obmedzený a rovný .

Ryža. 1. Funkcia popisujúca kvantovanie

Hlavnou úlohou v tomto prípade je určiť hodnoty prahov a kvantizačných úrovní. Najjednoduchším spôsobom riešenia tohto problému je rozdelenie dynamického rozsahu na rovnaké intervaly. Toto riešenie však nie je najlepšie. Ak sú hodnoty intenzity väčšiny vzoriek obrázkov zoskupené napríklad v „tmavej“ oblasti a počet úrovní je obmedzený, potom je vhodné kvantovať nerovnomerne. V "tmavej" oblasti by mala byť kvantovaná častejšie a menej často v "svetlej" oblasti. Tým sa zníži kvantizačná chyba.

V systémoch na digitálne spracovanie obrazu majú tendenciu znižovať počet úrovní a prahov kvantizácie, pretože množstvo informácií potrebných na kódovanie obrazu závisí od ich počtu. Pri relatívne malom počte úrovní sa však v kvantovanom obraze môžu objaviť falošné kontúry. Vznikajú v dôsledku prudkej zmeny jasu kvantovaného obrazu a sú badateľné najmä v plochých oblastiach jeho zmeny. Falošné obrysy výrazne zhoršujú vizuálnu kvalitu obrazu, pretože ľudské videnie je obzvlášť citlivé na obrysy. Pre jednotné kvantovanie typických obrázkov je potrebných aspoň 64 úrovní.