Znovuobjavenie JPEG. Aký je najsvetlejší pomer strán. Algoritmy kompresie obrazu

21.07.2019

Návod

Z nadpisu ste správne pochopili, že nejde o úplne obyčajný popis JPEG algoritmu (formát súboru som podrobne opísal v článku „Dekódovanie JPEG pre figuríny“). V prvom rade zvolený spôsob prezentácie materiálu predpokladá, že nevieme nič nielen o JPEG, ale ani o Fourierovej transformácii a Huffmanovom kódovaní. A vôbec, z prednášok si toho veľa nepamätáme. Len sa odfotili a začali rozmýšľať, ako sa to dá skomprimovať. Preto som sa snažil prístupným spôsobom vyjadriť len podstatu, v ktorej si však čitateľ vyvinie dostatočne hlboké a hlavne intuitívne pochopenie algoritmu. Vzorce a matematické výpočty - prinajmenšom len tie, ktoré sú dôležité pre pochopenie toho, čo sa deje.

Znalosť algoritmu JPEG je veľmi užitočná pre viac než len kompresiu obrázkov. Využíva teóriu z oblasti digitálneho spracovania signálov, matematickej analýzy, lineárnej algebry, teórie informácie, najmä Fourierovej transformácie, bezstratového kódovania atď. Získané poznatky preto môžu byť užitočné kdekoľvek.

Ak existuje túžba, navrhujem paralelne s článkom prejsť rovnakými krokmi. Skontrolujte, či je vyššie uvedené zdôvodnenie vhodné pre rôzne obrázky, skúste vykonať vlastné úpravy algoritmu. To je veľmi zaujímavé. Ako nástroj môžem odporučiť skvelú kombináciu Python + NumPy + Matplotlib + PIL (Pillow). Takmer všetka moja práca (vrátane grafiky a animácie) bola vykonaná pomocou nich.

Pozor, premávka! Veľa ilustrácií, grafiky a animácií (~ 10Mb). Je iróniou, že v článku o JPEG sú len 2 obrázky s týmto formátom z päťdesiatich.

Nech už je algoritmus kompresie informácií akýkoľvek, jeho princíp bude vždy rovnaký – nájdenie a popis vzorcov. Čím viac vzorov, tým väčšia redundancia, tým menej informácií. Archivátory a kódovače sú zvyčajne „nabrúsené“ na konkrétny typ informácií a vedia, kde ich nájsť. V niektorých prípadoch je vzor okamžite viditeľný, napríklad vzor modrej oblohy. Každý riadok jeho digitálneho znázornenia sa dá celkom presne opísať rovnou čiarou.

Budeme cvičiť na mývalových mačkách. Sivý obrázok vyššie slúži ako príklad. Dobre kombinuje homogénne aj kontrastné oblasti. A ak sa naučíme komprimovať šedú, potom nebudú žiadne problémy s farbou.

Vektorové znázornenie

Najprv sa pozrime, ako sú závislé dva susedné pixely. Je logické predpokladať, že s najväčšou pravdepodobnosťou budú veľmi podobné. Skontrolujeme to pri všetkých pároch obrázka. Označme ich na súradnicovej rovine bodkami tak, aby hodnota bodu pozdĺž osi X bola hodnota prvého pixelu, pozdĺž osi Y - druhého. Pre náš obrázok s rozmermi 256 x 256 dostaneme 256 * 256/2 bodov:

Dá sa predvídať, že väčšina bodov je na alebo blízko priamky y = x (a je ich ešte viac, ako vidíte na obrázku, pretože sú opakovane na sebe navrstvené a navyše sú priesvitné) . Ak áno, bolo by jednoduchšie pracovať s ich otočením o 45 °. Aby ste to dosiahli, musíte ich vyjadriť v inom súradnicovom systéme.

Základné vektory nového systému sú samozrejme nasledovné:. Nútené deliť odmocninou z dvoch, aby sme dostali ortonormálny systém (dĺžky základných vektorov sú rovné jednej). Tu je ukázané, že nejaký bod p = (x, y) v novom systéme bude reprezentovaný ako bod (a 0, a 1). Keď poznáme nové koeficienty, môžeme ľahko získať staré spätnou rotáciou. Je zrejmé, že prvá (nová) súradnica je priemer a druhá je rozdiel medzi x a y (ale delený odmocninou z 2). Predstavte si, že ste vyzvaní, aby ste ponechali iba jednu z hodnôt: buď 0, alebo 1 (to znamená, že druhú hodnotu prirovnáte k nule). Je lepšie zvoliť 0, pretože hodnota 1 bude pravdepodobne aj tak blízko nule. Toto sa stane, ak obnovíme obrázok iba o 0:

4x zväčšenie:

Úprimne povedané, tento druh kompresie nie je veľmi pôsobivý. Je lepšie rozdeliť obrázok na tri pixely rovnakým spôsobom a znázorniť ich v trojrozmernom priestore.

Sú to rovnaké grafy, ale z rôznych uhlov pohľadu. Červené čiary sú osi, ktoré sa navrhli. Zodpovedajú vektorom:. Dovoľte mi pripomenúť, že musíte deliť nejakými konštantami, aby sa dĺžky vektorov rovnali jednej. Rozšírením na takomto základe teda dostaneme 3 hodnoty a 0, 1, a 2 a 0 je dôležitejšie ako 1 a 1 je dôležitejšie ako 2. Ak vyhodíme 2, tak sa graf „sploští“ v smere vektora e 2. Tento už dosť tenký trojrozmerný plech sa stane plochým. Nepríde o toľko, no zbavíme sa tretiny hodnôt. Porovnajme obrazy zrekonštruované trojicami: (a 0, 0, 0), (a 1, a 2, 0) a (a 0, a 1, a 2). V minulej verzii sme nič nevyhodili, takže dostaneme originál.

4x zväčšenie:

Druhá kresba je už dobrá. Ostré miesta sa trochu vyhladili, ale celkovo je obraz zachovaný veľmi dobre. A teraz sa rovnakým spôsobom rozdeľme na štyri a vizuálne definujme základ v štvorrozmernom priestore ... Ach, áno. Môžete však hádať, aký bude jeden zo základných vektorov: (1,1,1,1) / 2. Preto sa môžete pozrieť na projekciu štvorrozmerného priestoru na priestor kolmý na vektor (1,1,1,1), aby ste identifikovali ďalšie. Ale toto nie je najlepší spôsob.
Naším cieľom je naučiť sa previesť (x 0, x 1, ..., x n-1) na (a 0, a 1, ..., a n-1), aby každá hodnota ai bola menej dôležitá ako tie predchádzajúce.... Ak to dokážeme, potom možno posledné hodnoty sekvencie možno úplne vyhodiť. Vyššie uvedené skúsenosti naznačujú, že je to možné. Ale bez matematického aparátu sa človek nezaobíde.
Takže musíte previesť body na nový základ. Najprv však musíte nájsť vhodný základ. Vráťme sa k prvému párovaciemu experimentu. Budeme uvažovať vo všeobecných podmienkach. Definovali sme základné vektory:

Vyjadrený cez ne vektor p:

alebo v súradniciach:

Ak chcete nájsť 0 a 1, musíte projektovať p na e 0 a e 1 resp. A na to musíte nájsť bodkový produkt

podobne:

V súradniciach:

Často je vhodnejšie vykonať transformáciu v maticovej forme.

Potom A = EX a X = E T A. Toto je krásna a pohodlná forma. Matica E sa nazýva transformačná matica a je ortogonálna, stretneme sa s ňou neskôr.

Prechod od vektorov k funkciám.

Je vhodné pracovať s vektormi malých rozmerov. Chceme však nájsť vzory vo veľkých blokoch, preto je namiesto N-rozmerných vektorov pohodlnejšie pracovať so sekvenciami, ktoré reprezentujú obrázok. Takéto postupnosti budem nazývať diskrétnymi funkciami, pretože nasledujúca úvaha platí pre spojité funkcie.
Ak sa vrátime k nášmu príkladu, predstavme si takú funkciu f (i), ktorá je definovaná len v dvoch bodoch: f (0) = x a f (1) = y. Podobne definujeme bázové funkcie e 0 (i) a e 1 (i) na základe báz e 0 a e 1. Dostaneme:

Toto je veľmi dôležitý záver. Teraz vo fráze "rozklad vektora na ortonormálne vektory" môžeme nahradiť slovo "vektor" slovom "funkcia" a dostaneme úplne správny výraz "rozklad funkcie na ortonormálne funkcie". Nezáleží na tom, že sme dostali takú skromnú funkciu, pretože rovnaké uvažovanie funguje pre N-rozmerný vektor, ktorý môže byť reprezentovaný ako diskrétna funkcia s N hodnotami. A práca s funkciami je prehľadnejšia ako s N-rozmernými vektormi. Prípadne môžete takúto funkciu reprezentovať ako vektor. Navyše, obyčajná spojitá funkcia môže byť reprezentovaná nekonečne-rozmerným vektorom, aj keď už nie v euklidovskom, ale v Hilbertovom priestore. Tam ale nepôjdeme, budú nás zaujímať iba diskrétne funkcie.
A naša úloha nájsť základ sa mení na úlohu nájsť vhodný systém ortonormálnych funkcií. V nasledujúcej úvahe sa predpokladá, že sme už nejakým spôsobom definovali množinu základných funkcií, podľa ktorých budeme rozširovať.
Povedzme, že máme nejakú funkciu (reprezentovanú napríklad hodnotami), ktorú chceme reprezentovať ako súčet ostatných. Tento proces môžete reprezentovať vo vektorovej forme. Ak chcete funkciu rozložiť, musíte ju postupne „premietnuť“ do základných funkcií. Vo vektorovom zmysle poskytuje výpočet projekcie minimálne priblíženie pôvodného vektora k inému na vzdialenosť. Berúc do úvahy, že vzdialenosť sa počíta pomocou Pytagorovej vety, potom podobná reprezentácia vo forme funkcií poskytuje najlepšiu strednú štvorcovú aproximáciu funkcie k inej. Každý koeficient (k) teda určuje „tesnosť“ funkcie. Formálnejšie, k * e (x) je najlepšia aproximácia efektívnej hodnoty k f (x) spomedzi l * e (x).
Nasledujúci príklad ukazuje proces aproximácie funkcie pomocou iba dvoch bodov. Na pravej strane je vektorová reprezentácia.

S ohľadom na náš experiment rozdelenia do párov môžeme povedať, že tieto dva body (0 a 1 na vodorovnej osi) sú párom susediacich pixelov (x, y).
To isté, ale s animáciou:

Ak vezmeme 3 body, potom musíme zvážiť trojrozmerné vektory, ale aproximácia bude presnejšia. A pre diskrétnu funkciu s N hodnotami je potrebné zvážiť N-rozmerné vektory.
So množinou získaných koeficientov je možné ľahko získať pôvodnú funkciu sčítaním základných funkcií s príslušnými koeficientmi. Analýza týchto koeficientov môže poskytnúť množstvo užitočných informácií (v závislosti od základu). Špeciálnym prípadom týchto úvah je princíp rozšírenia Fourierovho radu. Koniec koncov, naša úvaha je použiteľná na akýkoľvek základ a pri rozširovaní vo Fourierovom rade sa berie úplne špecifický.

Diskrétne Fourierove transformácie (DFT)

V predchádzajúcej časti sme prišli na to, že by bolo fajn funkciu rozložiť na zložené. Začiatkom 19. storočia sa nad tým zamýšľal aj Fourier. Pravda, nemal obrázok s mývalom, a tak musel skúmať rozloženie tepla po kovovom prstenci. Potom zistil, že je veľmi vhodné vyjadriť teplotu (a jej zmenu) v každom bode prstenca ako súčet sínusoidov s rôznymi periódami. "Fourier zistil (odporúčam prečítať, je to zaujímavé), že druhá harmonická sa rozpadá 4-krát rýchlejšie ako prvá a harmonické vyšších rádov sa rozpadajú ešte väčšou rýchlosťou."
Vo všeobecnosti sa čoskoro ukázalo, že periodické funkcie sú pozoruhodne rozložené na súčet sínusoidov. A keďže v prírode existuje veľa objektov a procesov, ktoré sú popísané periodickými funkciami, objavil sa silný nástroj na ich analýzu.
Možno jedným z najviditeľnejších periodických procesov je zvuk.

1. graf - čistý tón pri 2500 hertzoch.
2. - biely šum. Teda šum s rovnomerne rozloženými frekvenciami v celom rozsahu.
3. - súčet prvých dvoch.

Ak by mi dali hodnoty poslednej funkcie v čase, keď som nevedel o Fourierovom rade, a požiadali o ich analýzu, určite by som bol v strate a nemohol by som povedať nič hodnotné. No áno, nejaká funkcia, ale ako pochopiť, že je tam niečo objednané? Ale ak by som hádal počúvať poslednú funkciu, ucho by medzi hlukom zachytilo jasný tón. Aj keď nie veľmi dobre, keďže som pri generovaní špeciálne volil také parametre, aby sa signál na súhrnnom grafe vizuálne rozpustil v šume. Pokiaľ tomu dobre rozumiem, stále nie je jasné, ako to načúvací prístroj robí. Nedávno sa však ukázalo, že zvuk nerozkladá na sínusoidy. Možno jedného dňa pochopíme, ako sa to stane, a objavia sa pokročilejšie algoritmy. No, stále sme v staromódnom štýle.
Prečo neskúsiť vziať sinusoidy ako základ? V skutočnosti sme to už urobili. Pripomeňme si náš rozklad na 3 základné vektory a znázornime ich na grafe:

Áno, áno, viem, že to vyzerá ako fit, ale s tromi vektormi je ťažké očakávať viac. Teraz je však jasné, ako získať napríklad 8 základných vektorov:

Jednoduchá kontrola ukazuje, že tieto vektory sú párovo kolmé, teda ortogonálne. To znamená, že môžu byť použité ako základ. Transformácia na takomto základe je všeobecne známa a nazýva sa diskrétna kosínusová transformácia (DCT). Myslím, že z uvedených grafov je jasné, ako sa získa vzorec transformácie DCT:

Je to stále rovnaký vzorec: A = EX so substituovaným základom. Základné vektory špecifikovaného DCT (sú to tiež riadkové vektory matice E) sú ortogonálne, ale nie ortonormálne. Na to treba pamätať pri inverznej transformácii (nebudem sa tým zaoberať, ale koho to zaujíma - v inverznej DCT sa objavuje výraz 0,5 * a 0, keďže vektor nulovej bázy je väčší ako ostatné).
Nasledujúci príklad ukazuje proces aproximácie priebežných súčtov na pôvodné hodnoty. Pri každej iterácii sa ďalší základ vynásobí nasledujúcim koeficientom a pripočíta sa k priebežnému súčtu (teda rovnako ako v prvých experimentoch na mývali – jedna tretina hodnôt, dve tretiny).

Napriek niektorým argumentom o vhodnosti výberu takéhoto základu však zatiaľ neexistujú žiadne skutočné argumenty. Skutočne, na rozdiel od zvuku, účelnosť rozkladu obrazu na periodické funkcie je oveľa menej zrejmá. Obraz však môže byť naozaj príliš nepredvídateľný aj na malej ploche. Preto je obrázok rozdelený na dostatočne malé časti, ale nie celkom malé, aby rozklad dával zmysel. V JPEG je obrázok „rozrezaný“ na 8 x 8 štvorcov. V rámci takéhoto diela sú fotografie zvyčajne veľmi jednotné: pozadie plus mierne výkyvy. Takéto oblasti sú inteligentne aproximované sínusoidmi.
No povedzme, že tento fakt je viac-menej intuitívny. Z ostrých farebných prechodov je ale zlý pocit, pretože pomaly sa meniace funkcie nás nezachránia. Musíme pridať rôzne vysokofrekvenčné funkcie, ktoré robia svoju prácu, ale vedľa seba na jednotnom pozadí. Nasnímajte obrázok 256 x 256 s dvoma kontrastnými oblasťami:

Rozložme každý riadok pomocou DCT, čím získame 256 koeficientov na riadok.
Potom ponecháme iba prvých n koeficientov a zvyšok prirovnáme k nule, a preto bude obraz prezentovaný ako súčet iba prvých harmonických:

Číslo na obrázku je počet zostávajúcich kurzov. Na prvom obrázku zostal len priemer. K druhej už pribudla jedna nízkofrekvenčná sínusoida atď.. Mimochodom, pozor na hranicu - napriek všetkému lepšiemu priblíženiu sú vedľa uhlopriečky dobre viditeľné 2 pruhy, jeden je svetlejší, druhý je tmavší. Časť posledného obrázka zväčšená 4-krát:

A vo všeobecnosti, ak ďaleko od hranice vidíme počiatočné jednotné pozadie, potom keď sa k nemu priblížime, amplitúda začne rásť, nakoniec dosiahne minimálnu hodnotu a potom sa prudko stane maximálnou. Tento jav je známy ako Gibbsov efekt.

Výška týchto hrbolčekov, ktoré sa objavujú v blízkosti diskontinuít funkcie, sa neznižuje s nárastom počtu členov vo funkciách. Pri diskrétnej transformácii zaniká len vtedy, ak sú zachované takmer všetky koeficienty. Presnejšie povedané, stane sa neviditeľným.
Nasledujúci príklad je úplne podobný vyššie uvedenému rozkladu trojuholníkov, ale na skutočnom mývali:

Pri štúdiu DCT môžete nadobudnúť mylný dojem, že vždy stačí len niekoľko prvých (nízkofrekvenčných) koeficientov. To platí pre mnohé fotografie, ktorých hodnoty sa dramaticky nemenia. Na hranici kontrastných oblastí však budú hodnoty svižne „skákať“ a aj posledné koeficienty budú veľké. Preto, keď počujete o vlastnostiach DCT na zachovanie energie, vezmite do úvahy skutočnosť, že sa vzťahuje na mnohé typy signálov, s ktorými sa stretávate, ale nie na všetky. Zamyslite sa napríklad nad tým, ako bude vyzerať diskrétna funkcia, ktorej koeficienty expanzie sa rovnajú nule, s výnimkou posledného. Pomôcka: zamyslite sa nad rozkladom vo vektorovej forme.
Napriek nedostatkom je zvolený základ jeden z najlepších na reálnych fotografiách. O niečo neskôr sa dočkáme malého porovnania s ostatnými.

DCT vs všetko ostatné

Keď som študoval problematiku ortogonálnych transformácií, pravdu povediac, veľmi ma nepresvedčili argumenty, že všetko okolo je súčet harmonických kmitov, preto je potrebné obrázky rozložiť na sínusoidy. Alebo možno niektoré krokové funkcie sú lepšie? Preto som hľadal výsledky štúdií o optimálnosti DCT na reálnych snímkach. Všade sa píše, že „v praktických aplikáciách sa najčastejšie vyskytuje DCT kvôli vlastnosti „zahusťovania energie“. Táto vlastnosť znamená, že maximálne množstvo informácií je obsiahnuté v prvých koeficientoch. A prečo? Nie je ťažké vykonať výskum: vyzbrojíme sa množstvom rôznych obrázkov, rôznych známych základov a začneme počítať štandardnú odchýlku od skutočného obrázka pre iný počet koeficientov. Našiel som malý prieskum v článku (použité obrázky) o tejto technike. Zobrazuje grafy závislosti akumulovanej energie od počtu prvých expanzných koeficientov v rôznych bázach. Ak ste sa pozreli na grafy, ste presvedčení, že DCT trvalo zastáva čestné ... ehm ... 3. miesto. Ako to? Čo je KLT transformácia? Chválil som DCT, ale tu...

KLT

Všetky transformácie okrem KLT sú transformácie s konštantnou bázou. A v KLT (Karunen-Loeveova transformácia) je vypočítaný najoptimálnejší základ pre niekoľko vektorov. Vypočítava sa tak, že prvé koeficienty dávajú najmenšiu strednú kvadratúru chybu celkovo pre všetky vektory. Podobnú prácu sme urobili skôr ručne, pričom sme vizuálne definovali základ. Na prvý pohľad to vyzerá ako rozumný nápad. Mohli by sme napríklad rozdeliť obrázok na malé časti a pre každú vypočítať iný základ. Objavuje sa však nielen starosť o uloženie tohto základu, ale aj jeho výpočet je dosť namáhavý. A DCT stráca len málo a okrem toho má DCT rýchle konverzné algoritmy.

DFT

DFT (Discrete Fourier Transform) - Diskrétna Fourierova transformácia. Tento názov niekedy označuje nielen konkrétnu transformáciu, ale aj celú triedu diskrétnych transformácií (DCT, DST ...). Pozrime sa na vzorec DFT:

Ako asi tušíte, ide o ortogonálnu transformáciu s nejakým zložitým základom. Keďže sa takáto zložitá forma vyskytuje o niečo častejšie ako vždy, má zmysel študovať jej záver.
Niekto by mohol nadobudnúť dojem, že akýkoľvek čistý harmonický signál (s celočíselnou frekvenciou) pri rozklade DCT poskytne iba jeden nenulový koeficient zodpovedajúci tejto harmonickej. Nie je to tak, keďže okrem frekvencie je dôležitá aj fáza tohto signálu. Napríklad expanzia sínusu v kosíne (podobne ako diskrétna expanzia) bude nasledovná:

Toľko k čistej harmonike. Splodila kopu ďalších. Animácia zobrazuje DCT koeficienty sínusoidy v rôznych fázach.

Ak sa vám zdalo, že sa stĺpy otáčajú okolo osi, tak sa vám to nezdalo.
Takže teraz funkciu rozložíme na súčet sínusoidov nielen rôznych frekvencií, ale aj posunutých v nejakej fáze. Bude vhodnejšie zvážiť fázový posun pomocou príkladu kosínusu:

Jednoduchá trigonometrická identita dáva dôležitý výsledok: fázový posun je nahradený súčtom sínusov a kosínusov, počítaných s koeficientmi cos (b) a sin (b). To znamená, že funkcie môžete rozložiť na súčet sínusov a kosínusov (bez akýchkoľvek fáz). Toto je bežný trigonometrický tvar. Oveľa častejšie sa však používa komplex. Na jeho získanie je potrebné použiť Eulerov vzorec. Stačí nahradiť deriváty vzorca za sínus a kosínus, dostaneme:

Teraz malá náhrada. Podčiarkovník je konjugované číslo.

Dostaneme konečnú rovnosť:

c je komplexný koeficient, ktorého skutočná časť sa rovná kosínusovému koeficientu a imaginárna časť sa rovná sínusovému koeficientu. A množina bodov (cos (b), sin (b)) je kruh. V takomto zázname každá harmonická vstupuje do rozkladu s kladnými aj zápornými frekvenciami. Preto v rôznych vzorcoch Fourierovej analýzy dochádza k súčtu alebo integrácii zvyčajne od mínus do plus nekonečna. Často je pohodlnejšie vykonávať výpočty v tejto zložitej forme.
Transformácia rozloží signál na harmonické s frekvenciami od jednej do N kmitov na ploche signálu. Ale vzorkovacia frekvencia je N v oblasti signálu. A podľa Kotelnikovovej vety (aka Nyquist - Shannonova veta) musí byť vzorkovacia frekvencia aspoň dvojnásobkom frekvencie signálu. Ak tomu tak nie je, potom sa získa efekt objavenia sa signálu s falošnou frekvenciou:

Prerušovaná čiara zobrazuje nesprávne zrekonštruovaný signál. S takýmto javom ste sa v živote stretli často. Napríklad vtipný pohyb kolies auta vo videu, alebo moaré efekt.
Vďaka tomu sa zdá, že druhá polovica N komplexných amplitúd pozostáva z iných frekvencií. Tieto falošné harmonické druhej polovice sú zrkadlovým obrazom prvej a nenesú žiadne ďalšie informácie. Zostáva nám teda N / 2 kosínusov a N / 2 sínusov (tvoriacich ortogonálny základ).
Dobre, existuje základ. Jeho zložkami sú harmonické s celočíselným počtom kmitov v oblasti signálu, čo znamená, že krajné hodnoty harmonických sú rovnaké. Presnejšie povedané, sú takmer rovnaké, pretože posledná hodnota je prevzatá nie úplne od okraja. Navyše, každá harmonická je takmer zrkadlovo symetrická okolo svojho stredu. Všetky tieto javy sú obzvlášť silné pri nízkych frekvenciách, ktoré sú pre nás dôležité pri kódovaní. To je tiež zlé, pretože hranice bloku budú v komprimovanom obrázku viditeľné. Základ DFT ilustrujem s N = 8. Prvé 2 riadky sú kosínusové zložky, posledné sú sínusové:

Venujte pozornosť vzhľadu duplikátov komponentov so zvyšujúcou sa frekvenciou.

V duchu môžete premýšľať o tom, ako by sa dal rozložiť signál, ktorého hodnoty plynule klesajú z maximálnej hodnoty na začiatku na minimálnu hodnotu na konci. Iba harmonické bližšie ku koncu by mohli urobiť viac-menej adekvátnu aproximáciu, čo nie je pre nás veľmi dobré. Obrázok vľavo je aproximáciou signálu s jedným koncom. Vpravo - symetricky:

S tým prvým sú veci extrémne zlé.
Dá sa to teda urobiť ako v DCT - znížiť frekvencie 2- alebo iný počet krát, takže počet niektorých kmitov je zlomkový a hranice sú v rôznych fázach? Potom komponenty nebudú ortogonálne. A nedá sa s tým nič robiť.

DST

Čo ak sa v DCT použijú sínusy namiesto kosínusov? Získame diskrétnu sínusovú transformáciu (DST). Ale pre náš problém nie sú všetky zaujímavé, keďže celé aj polovice periód sínusov sú na hraniciach blízke nule. To znamená, že dostaneme približne rovnaký nevhodný rozklad ako v DFT.

Návrat k DCT

Ako sa mu darí na hraniciach? Dobre. Existujú protifázy a žiadne nuly.

Všetko ostatné

Non-Fourierove transformácie. nebudem opisovať.
WHT - Matica pozostáva iba zo stupňovitých komponentov s hodnotami -1 a 1.
Haar je tiež ortogonálna vlnková transformácia.
Sú horšie ako DCT, ale ľahšie sa počítajú.

Takže máte nápad prísť s vlastnou transformáciou. Zapamätaj si to:

Základ musí byť ortogonálny.
S pevnou základnou líniou nemôžete poraziť KLT v kvalite kompresie. Medzitým je na skutočných fotografiách DCT takmer taká dobrá, ako je.
S DFT a DST ako príklad, musíte pamätať na hranice.
A pamätajte, že DCT má ďalšiu dobrú výhodu - blízko hraníc ich zložiek sa ich deriváty rovnajú nule, čo znamená, že prechod medzi susednými blokmi bude celkom hladký.
Fourierove transformácie majú rýchle algoritmy so zložitosťou O (N * logN), na rozdiel od priameho výpočtu: O (N 2).

Nebude to ľahké, však? Pre niektoré typy obrázkov si však môžete vybrať lepší základ ako DCT.

Dvojrozmerné transformácie

Teraz sa pokúsme vykonať takýto experiment. Vezmite si napríklad výrez z obrázka.

Jeho 3D graf:

Poďme cez DCT (N = 32) pre každý riadok:

Teraz chcem, aby ste si očami prebehli každý stĺpec získaných koeficientov, teda zhora nadol. Pamätajte, že naším cieľom je udržať hodnoty čo najmenšie a zároveň odstrániť tie nepodstatné. Pravdepodobne ste uhádli, že hodnoty každého stĺpca získaných koeficientov možno rozložiť rovnakým spôsobom ako hodnoty pôvodného obrázka. Nikto nás neobmedzuje pri výbere ortogonálnej transformačnej matice, ale urobíme to znova s DCT (N = 8):

Koeficient (0,0) sa ukázal byť príliš veľký, preto je na grafe znížený 4-krát.
Takže, čo sa stalo?
V ľavom hornom rohu sú najvýznamnejšie koeficienty rozšírenia z najvýznamnejších koeficientov.
V ľavom dolnom rohu sú najvýznamnejšie koeficienty rozťažnosti z najvýznamnejších koeficientov.
V pravom hornom rohu sú najvýznamnejšie koeficienty rozťažnosti z najvýznamnejších koeficientov.
V pravom dolnom rohu sú najnevýznamnejšie koeficienty rozťažnosti z najvýznamnejších koeficientov.
Je jasné, že význam koeficientov klesá, ak sa pohybujete diagonálne z ľavého horného rohu do pravého dolného. Čo je dôležitejšie: (0, 7) alebo (7, 0)? Čo vôbec znamenajú?
Najprv po riadkoch: A 0 = (EX T) T = XE T (transponované, pretože vzorec A = EX je pre stĺpce), potom po stĺpcoch: A = EA 0 = EXE T. Ak to dôkladne vypočítate, dostanete vzorec:

Ak sa teda vektor rozloží na sínusoidy, potom maticu na funkcie v tvare cos (ax) * cos (by). Každý blok 8x8 v JPEG je reprezentovaný ako súčet 64 funkcií formulára:

Wikipedia a ďalšie zdroje poskytujú takéto funkcie vo vhodnejšej forme:

Preto sú koeficienty (0, 7) alebo (7, 0) rovnako užitočné.
V skutočnosti však ide o obvyklý jednorozmerný rozklad na 64 64-rozmerných báz. Všetko vyššie uvedené platí nielen pre DCT, ale aj pre akýkoľvek ortogonálny rozklad. Analogicky vo všeobecnom prípade získame N-rozmernú ortogonálnu transformáciu.
A tu je 2-rozmerná transformácia mývala (DCT 256x256). Opäť s vynulovanými hodnotami. Čísla - počet nenulových koeficientov všetkých (najvýznamnejšie hodnoty zostali umiestnené v trojuholníkovej oblasti v ľavom hornom rohu).

Pamätajte, že koeficient (0, 0) sa nazýva jednosmerný, ostatných 63 sa nazýva AC.

Výber veľkosti bloku

Priateľ sa pýta: prečo sa v JPEG používa delenie 8x8. Z uverejnenej odpovede:

DCT zaobchádza s blokom, ako keby bol periodický a musí rekonštruovať výsledný skok na hraniciach. Ak vezmete bloky 64 x 64, "s najväčšou pravdepodobnosťou budete mať obrovský skok na hraniciach a budete" potrebovať veľa vysokofrekvenčných komponentov, aby ste to zrekonštruovali na uspokojivú presnosť.

Hovorí sa, že DCT funguje dobre iba na periodických funkciách, a ak vezmete veľkú veľkosť, s najväčšou pravdepodobnosťou dostanete obrovský skok na hraniciach bloku a na jeho pokrytie budete potrebovať veľa vysokofrekvenčných komponentov. To nie je pravda! Toto vysvetlenie je veľmi podobné DFT, ale nie DCT, keďže takéto skoky dokonale pokrýva už pri prvých komponentoch.
Tá istá stránka poskytuje odpoveď z MPEG FAQ s hlavnými argumentmi proti veľkým blokom:

Malý zisk pri rozdelení na veľké bloky.
Zvýšená výpočtová zložitosť.
V jednom bloku je vysoká pravdepodobnosť veľkého počtu ostrých hrán, ktoré spôsobia Gibbsov efekt.

Navrhujem, aby ste to preskúmali sami. Začnime s prvý.

Vodorovná os je zlomkom prvých nenulových koeficientov. Vertikálne – štandardná odchýlka pixelov od originálu. Maximálna možná odchýlka sa berie ako jednotka. Samozrejme, jeden obrázok na verdikt zjavne nestačí. Navyše nekonám celkom správne, iba nulujem. V skutočnom JPEG sa v závislosti od kvantizačnej matice vynulujú iba malé hodnoty vysokofrekvenčných zložiek. Preto nasledujúce experimenty a závery majú za cieľ povrchne odhaliť princípy a zákonitosti.
Môžete porovnať rozdelenie do rôznych blokov so zvyšnými 25 percentami koeficientov (zľava doprava, potom sprava doľava):

Veľké bloky nie sú zobrazené, pretože sú vizuálne takmer na nerozoznanie od rozmerov 32x32. Teraz sa pozrime na absolútny rozdiel s pôvodným obrázkom (zosilnený 2-krát, inak nie je naozaj nič vidieť):

8x8 dáva lepšie výsledky ako 4x4. Ďalšie zvýšenie veľkosti už neposkytuje jasne viditeľnú výhodu. Hoci by som vážne uvažoval o 16x16, namiesto 8x8: zvýšenie obtiažnosti o 33% (o obtiažnosti v ďalšom odseku), dáva malé, ale stále viditeľné zlepšenie pri rovnakom počte koeficientov. Výber 8x8 však vyzerá dostatočne rozumne a možno je to zlatá stredná cesta. JPEG bol vydaný v roku 1991. Myslím si, že tento druh kompresie bol pre vtedajšie procesory veľmi náročný.

Po druhé argument. Pamätajte, že zvýšenie veľkosti bloku bude vyžadovať viac výpočtov. Odhadnime koľko. Zložitosť prevodu na čelo, ako už celkom vieme: O (N 2), keďže každý koeficient pozostáva z N členov. V praxi sa však používa efektívny algoritmus rýchlej Fourierovej transformácie (FFT). Jeho popis presahuje rámec tohto článku. Jeho zložitosť: O (N * logN). Pre dvojrozmerný rozklad ho musíte použiť dvakrát N-krát. Takže zložitosť 2D DCT je O (N 2 logN). Teraz porovnajme zložitosť výpočtu obrázka s jedným blokom a niekoľkými malými:

Jeden blok (kN) x (kN): O ((kN) 2 log (kN)) = O (k 2 N 2 log (kN))
k * k blokov N * N: O (k 2 N 2 logN)

To znamená, že napríklad oblasť 64x64 je dvakrát náročnejšia na výpočet ako oblasť 8x8.

Po tretie argument. Ak máme na obrázku ostré ohraničenie farieb, tak to ovplyvní celý blok. Možno je lepšie, že tento blok bude dostatočne malý, pretože v mnohých susedných blokoch už takáto hranica pravdepodobne nebude. Miznutie z hraníc je však dostatočne rýchle. Navyše samotný okraj bude vyzerať lepšie. Overme si to na príklade s veľkým počtom kontrastných prechodov, opäť len so štvrtinou koeficientov:

Hoci skreslenie 16x16 blokov siaha ďalej ako 8x8, písmo je hladšie. Preto ma presvedčili len prvé dva argumenty. Ale viac sa mi páči rozdelenie 16x16.

Kvantovanie

V tejto fáze máme veľa matíc 8x8 s koeficientmi kosínusovej transformácie. Je čas zbaviť sa bezvýznamných koeficientov. Existuje elegantnejšie riešenie ako len vynulovanie posledného kurzu, ako sme to urobili vyššie. S touto metódou nie sme spokojní, pretože nenulové hodnoty sa ukladajú s nadmernou presnosťou a medzi tými, ktorí nemajú šťastie, môžu byť dosť dôležité. Východiskom je použitie kvantizačnej matice. Straty sa vyskytujú práve v tejto fáze. Každý Fourierov koeficient sa vydelí zodpovedajúcim číslom v kvantizačnej matici. Pozrime sa na príklad. Vezmeme prvý blok z nášho mývala a kvantifikujeme ho. Špecifikácia JPEG poskytuje štandardnú maticu:

Štandardná matica je 50% kvalita v FastStone a IrfanView. Táto tabuľka bola zvolená z hľadiska vyváženosti kvality a kompresného pomeru. Myslím si, že hodnota pre DC koeficient je väčšia ako susedné z dôvodu, že DCT nie je normalizovaný a prvá hodnota je väčšia ako by mala byť. Vysokofrekvenčné koeficienty sú drsnejšie, pretože sú menej dôležité. Myslím si, že teraz sa takéto matrice používajú zriedka, pretože zhoršenie kvality je jasne viditeľné. Nikto nezakazuje používať svoju tabuľku (s hodnotami od 1 do 255)
Počas dekódovania nastáva opačný proces - kvantované koeficienty sa násobia po členoch hodnotami kvantizačnej matice. Ale keďže sme hodnoty zaokrúhlili, nebudeme môcť presne rekonštruovať pôvodné Fourierove koeficienty. Čím väčšie je kvantizačné číslo, tým väčšia je chyba. Rekonštruovaný koeficient je teda len najbližší násobok.
Ďalší príklad:

A ako dezert zvážte 5% kvalitu (pri kódovaní vo Fast Stone).

Pri obnove tohto bloku dostaneme len priemernú hodnotu plus vertikálny gradient (kvôli zachovanej hodnote -1). Ukladajú sa však iba dve hodnoty: 7 a -1. S ostatnými blokmi nie je situácia o nič lepšia, tu je zrekonštruovaný obrázok:

Mimochodom, asi 100% kvalita. Ako môžete hádať, v tomto prípade kvantizačná matica pozostáva výlučne z jednotiek, to znamená, že nedochádza k žiadnej kvantizácii. Kvôli zaokrúhľovaniu koeficientov na celé číslo však nedokážeme presne obnoviť pôvodný obrázok. Napríklad mýval zachoval presnosť 96 % pixelov a 4 % sa líšili o 1/256. Samozrejme, takéto „skreslenia“ nie je možné vidieť vizuálne.
A môžete vidieť kvantizačné matice rôznych kamier.

Kódovanie

Predtým, ako budeme pokračovať, musíme pomocou jednoduchších príkladov pochopiť, ako možno získané hodnoty komprimovať.

Príklad 0(na zahriatie)
Predstavte si situáciu, že váš priateľ zabudol u vás doma papier so zoznamom a teraz vás požiada, aby ste mu ho nadiktovali cez telefón (iné spôsoby komunikácie neexistujú).
zoznam:

d9rg3
wfr43gt
wfr43gt
d9rg3
d9rg3
d9rg3
wfr43gt
d9rg3

Ako by ste si uľahčili svoju úlohu? Nemáte žiadnu osobitnú túžbu bolestne diktovať všetky tieto slová. Ale sú len dve a opakujú sa. Preto len nejako nadiktujete prvé dve slová a dohodnete sa, že ďalšie „d9rg3“ sa bude volať prvé slovo a „wfr43gt“ - druhé. Potom bude stačiť nadiktovať: 1, 2, 2, 1, 1, 1, 2, 1.

Takéto slová označíme ako A, B, C ... a nazveme ich symbolmi. Navyše pod symbolom sa môže skrývať čokoľvek: písmeno abecedy, slovo alebo hroch v zoo. Hlavná vec je, že rovnaké pojmy zodpovedajú rovnakým symbolom a iné zodpovedajú rôznym. Keďže našou úlohou je efektívne kódovanie (kompresia), budeme pracovať s bitmi, keďže ide o najmenšie jednotky reprezentácie informácie. Preto budeme zoznam písať ako ABBAAABA. Namiesto „prvého slova“ a „druhého slova je možné použiť bity 0 a 1.“ Potom sa ABBAAABA kóduje ako 01100010 (8 bitov = 1 bajt).

Príklad 1
Kódovať ABC.
3 rôzne znaky (A, B, C) sa nemôžu žiadnym spôsobom zhodovať s 2 možnými bitovými hodnotami (0 a 1). A ak áno, potom môžete použiť 2 bity na znak. Napríklad:

A: 00
B: 01
C: 10

Postupnosť bitov spojených so symbolom sa bude nazývať kód. ABC bude zakódované takto: 000110.

Príklad 2
Kódovať AAAAAABC.
Použitie 2 bitov na znak A sa zdá byť trochu zbytočné. Čo keby ste to skúsili takto:

C: 00

Kódovaná sekvencia: 000000100.
Je zrejmé, že táto možnosť nie je vhodná, pretože nie je jasné, ako dekódovať prvé dva bity tejto sekvencie: ako AA alebo ako C? Je veľmi nehospodárne používať nejaký oddeľovač medzi kódmi, zamyslíme sa nad tým, ako túto prekážku obísť inak. Takže zlyhanie bolo spôsobené tým, že kód C začína kódom A. Sme však odhodlaní kódovať A jedným bitom, aj keď B a C sú dva. Na základe tohto želania dáme A kód 0. Potom kódy B a C nemôžu začínať 0. Ale môžu začínať 1:

B: 10
C: 11

Sekvencia je zakódovaná takto: 0000001011. Skúste ju mentálne dekódovať. Môžete to urobiť iba jedným spôsobom.
Vyvinuli sme dve požiadavky na kódovanie:

Čím väčšia je váha znaku, tým kratší by mal byť jeho kód. A naopak.
Pre jednoznačné dekódovanie nemôže znakový kód začínať žiadnym iným znakovým kódom.

Je zrejmé, že poradie symbolov nie je dôležité, zaujíma nás len frekvencia ich výskytu. Preto je s každým symbolom spojené určité číslo, nazývané váha. Váha znaku môže byť buď relatívna hodnota, ktorá odráža podiel jeho výskytu, alebo absolútna hodnota, ktorá sa rovná počtu znakov. Hlavná vec je, že váhy sú úmerné výskytu symbolov.

Príklad 3
Zoberme si všeobecný prípad pre 4 symboly s ľubovoľnou váhou.

A: pa
B: pb
C: pc
D: pd

Bez straty všeobecnosti uvádzame pa ≥ pb ≥ pc ≥ pd. Existujú iba dva varianty kódov, ktoré sa zásadne líšia v dĺžke:

Ktorý z nich je výhodnejší? Aby ste to dosiahli, musíte vypočítať dĺžku prijatých kódovaných správ:
W1 = 2 * pa + 2 * pb + 2 * ks + 2 * pd
W2 = pa + 2 * pb + 3 * ks + 3 * pd
Ak je W1 menšie ako W2 (W1-W2<0), то лучше использовать первый вариант:
W1-W2 = pa - (pc + pd)< 0 =>pa< pc+pd.
Ak sa C a D vyskytujú spolu častejšie ako ostatné, potom ich spoločný vrchol dostane najkratší kód jedného bitu. V opačnom prípade jeden bit pripadne na symbol A. To znamená, že spojenie symbolov sa správa ako nezávislý symbol a má váhu rovnajúcu sa súčtu prichádzajúcich symbolov.
Vo všeobecnosti, ak p je váha znaku reprezentovaná zlomkom jeho výskytu (od 0 do 1), potom najlepšia dĺžka kódu je s = -log 2 p.
Uvažujme o tom pre jednoduchý prípad (je ľahké ho znázorniť vo forme stromu). Takže musíte zakódovať 2 s znaky s rovnakou váhou (1/2 s). Kvôli rovnosti váh budú dĺžky kódov rovnaké. Každá postava potrebuje s bitov. Ak je teda váha symbolu 1/2 s, jeho dĺžka je s. Ak váhu nahradíme p, tak dostaneme dĺžku kódu s = -log 2 p. To znamená, že ak sa jeden znak vyskytuje dvakrát menej často ako druhý, potom bude dĺžka jeho kódu o jeden bit dlhšia. Tento záver je však ľahké vyvodiť, ak si pamätáte, že pridanie jedného bitu vám umožňuje zdvojnásobiť počet možných možností.
A ešte jeden postreh - dva symboly s najmenšou váhou majú vždy najväčšiu, ale rovnakú dĺžku kódu. Navyše, ich bity, s výnimkou posledného, sú rovnaké. Ak by to nebola pravda, potom by sa aspoň jeden kód mohol skrátiť o 1 bit bez porušenia predpony. To znamená, že dva znaky s najnižšou váhou v kódovom strome majú spoločného rodiča na vyššej úrovni. Môžete to vidieť v príklade C a D vyššie.

Príklad 4
Skúsme vyriešiť nasledujúci príklad na základe záverov získaných v predchádzajúcom príklade.

Všetky symboly sú zoradené v zostupnom poradí podľa hmotnosti.
Posledné dva znaky sú spojené do skupiny. Tejto skupine je priradená váha rovnajúca sa súčtu váh týchto prvkov. Táto skupina sa podieľa na algoritme spolu so symbolmi a inými skupinami.

Kroky sa opakujú, kým nezostane iba jedna skupina. V rámci každej skupiny je jednému symbolu (alebo podskupine) priradený bit 0 a druhému bit 1.
Tento algoritmus sa nazýva Huffmanovo kódovanie.
Obrázok ukazuje príklad s 5 znakmi (A: 8, B: 6, C: 5, D: 4, E: 3). Hmotnosť symbolu (alebo skupiny) je uvedená vpravo.

Koeficienty kódujeme

Vrátime sa. Teraz máme veľa blokov so 64 koeficientmi v každom, ktoré treba nejako uložiť. Najjednoduchším riešením je použiť pevný počet bitov na faktor - samozrejme nešťastné. Zostavme si histogram všetkých získaných hodnôt (t.j. závislosť počtu koeficientov od ich hodnoty):

Venujte pozornosť - mierka je logaritmická! Môžete vysvetliť dôvod akumulácie hodnôt presahujúcich 200? Toto sú DC koeficienty. Keďže sú veľmi odlišné od ostatných, nie je prekvapujúce, že sú kódované oddelene. Tu je len DC:

Všimnite si, že tvar grafu pripomína tvar grafov z veľmi raných experimentov s delením do párov a trojíc pixelov.
Vo všeobecnosti sa hodnoty DC koeficientov môžu meniť od 0 do 2047 (presnejšie od -1024 do 1023, pretože v JPEG sa 128 odpočítava od všetkých pôvodných hodnôt, čo zodpovedá odčítaniu 1024 od DC) a spravodlivo rozdelené. rovnomerne s malými vrcholmi. Huffmanovo kódovanie tu teda veľmi nepomôže. Predstavte si tiež, aký veľký bude strom kódovania! A počas dekódovania v ňom budete musieť hľadať hodnoty. Toto je veľmi drahé. Myslíme ďalej.
Jednosmerný faktor je priemerná hodnota bloku 8x8. Predstavte si prechodový prechod (aj keď nie dokonalý), ktorý sa často nachádza na fotografiách. Samotné hodnoty DC sa budú líšiť, ale budú predstavovať aritmetický postup. To znamená, že ich rozdiel bude viac-menej konštantný. Zostavme si histogram rozdielov:

To je lepšie, pretože hodnoty sú vo všeobecnosti sústredené okolo nuly (ale Huffmanov algoritmus opäť poskytne príliš veľký strom). Malé hodnoty (v absolútnej hodnote) sú bežné, veľké sú zriedkavé. A keďže malé hodnoty zaberajú niekoľko bitov (ak odstránite úvodné nuly), jedno z pravidiel kompresie sa riadi dobre: priraďte krátke kódy znakom s veľkou váhou (a naopak). Stále nás obmedzuje nedodržanie ďalšieho pravidla: nemožnosť jednoznačného dekódovania. Vo všeobecnosti možno tento problém vyriešiť nasledujúcimi spôsobmi: zameniť s kódom oddeľovača, určiť dĺžku kódu, použiť predponové kódy (už ich poznáte – to je prípad, keď žiadny kód nezačína iným). Poďme podľa jednoduchej druhej možnosti, to znamená, že každý koeficient (presnejšie rozdiel medzi susednými) sa zapíše takto: (dĺžka) (hodnota), podľa nasledujúcej tabuľky:

To znamená, že kladné hodnoty sú priamo zakódované vo svojej binárnej reprezentácii a záporné hodnoty sú zakódované rovnakým spôsobom, ale s počiatočnou 1 nahradenou 0. Zostáva rozhodnúť, ako zakódovať dĺžky. Keďže existuje 12 možných hodnôt, na uloženie dĺžky je možné použiť 4 bity. Ale práve tu je lepšie použiť Huffmanovo kódovanie.

Hodnoty s dĺžkami 4 a 6 sú najviac, takže dostali najkratšie kódy (00 a 01).

Môže vzniknúť otázka: prečo má napríklad hodnota 9 kód 1111110 a nie 1111111? Koniec koncov, môžete pokojne zvýšiť "9" na vyššiu úroveň vedľa "0"? Faktom je, že v JPEG nemôžete použiť kód pozostávajúci iba z jednotiek - tento kód je vyhradený.
Je tu ešte jedna funkcia. Kódy získané opísaným Huffmanovým algoritmom sa nemusia v bitoch zhodovať s kódmi v JPEG, hoci ich dĺžky budú rovnaké. Pomocou Huffmanovho algoritmu sa získajú dĺžky kódov a vygenerujú sa samotné kódy (algoritmus je jednoduchý - začínajú krátkymi kódmi a pridávajú ich jeden po druhom do stromu čo najviac doľava, pričom sa zachováva prefix nehnuteľnosť). Napríklad pre strom vyššie je uložený zoznam: 0,2,3,1,1,1,1,1. A samozrejme je uložený zoznam hodnôt: 4,6,3,5,7,2,8,1,0,9. Pri dekódovaní sa kódy generujú rovnakým spôsobom.

Teraz je to poriadok. Zistili sme, ako sa ukladajú DC:
[Huffmanov kód pre dĺžku DC rozdielu (v bitoch)]
kde DC diff = DC prúd - DC predchádzajúci

Sledovanie AC:

Keďže graf je veľmi podobný grafu pre DC rozdiely, princíp je rovnaký: [Huffmanov kód pre AC dĺžku (v bitoch)]. Ale nie naozaj! Keďže mierka na grafe je logaritmická, nie je okamžite zrejmé, že nulové hodnoty sú asi 10-krát vyššie ako hodnoty 2 - ďalšie vo frekvencii. Je to pochopiteľné – nie každý prežil kvantovanie. Vráťme sa k matici hodnôt získaných vo fáze kvantovania (pomocou kvantizačnej matice FastStone, 90%).

Keďže existuje veľa skupín po sebe idúcich núl, objavuje sa myšlienka – zaznamenať len počet núl v skupine. Tento kompresný algoritmus sa nazýva RLE (Run-length encoding). Zostáva zistiť smer obchvatu "následnej chôdze" - kto je za kým? Písanie zľava doprava a zhora nadol nie je príliš efektívne, pretože nenulové koeficienty sú sústredené blízko ľavého horného rohu a čím bližšie k pravému dolnému rohu, tým viac núl.

Preto JPEG používa poradie nazývané „cik-cak“, ako je znázornené na obrázku vľavo. Táto metóda dobre rozlišuje skupiny núl. Pravý obrázok ukazuje alternatívnu metódu premostenia, ktorá nesúvisí s JPEG, ale má kuriózny názov (dôkaz). Dá sa použiť v MPEG pri kompresii prekladaného videa. Výber algoritmu premostenia neovplyvňuje kvalitu obrazu, ale môže zvýšiť počet kódovaných skupín núl, čo môže v konečnom dôsledku ovplyvniť veľkosť súboru.
Upravme náš záznam. Pre každý nenulový koeficient AC:
[Počet núl pred AC] [Huffmanov kód pre dĺžku AC (v bitoch)]
Myslím, že je to hneď poznať – aj počet núl je Huffmanom perfektne zakódovaný! Toto je veľmi blízka a dobrá odpoveď. Môžete však trochu optimalizovať. Predstavte si, že máme určitý koeficient AC, pred ktorým bolo 7 núl (samozrejme, ak to vypíšeme v cikcaku). Tieto nuly sú duchom hodnôt, ktoré neprežili kvantovanie. S najväčšou pravdepodobnosťou bol náš koeficient tiež zle zbitý a stal sa malým, čo znamená, že jeho dĺžka je krátka. Počet núl pred AC a dĺžka AC sú teda závislé veličiny. Preto to píšu takto:
[Huffmanov kód pre (počet núl pred AC, dĺžka AC (v bitoch)]
Algoritmus kódovania zostáva rovnaký: tie dvojice (počet núl pred AC, dĺžka AC), ktoré sa vyskytujú často, dostanú krátke kódy a naopak.

Zostavíme histogram závislosti veličiny pre tieto páry a Huffmanov strom.

Dlhé „pohorie“ potvrdzuje náš predpoklad.

Vlastnosti implementácie v JPEG:
Takýto pár zaberá 1 bajt: 4 bity pre počet núl a 4 bity pre dĺžku AC. 4 bity sú hodnoty od 0 do 15. Na dĺžku AC je toho viac než dosť, ale môže tam byť viac ako 15 núl? Potom sa použije viac párov. Napríklad pre 20 núl: (15, 0) (5, AC). To znamená, že 16. nula je zakódovaná ako nenulový koeficient. Keďže bližšie ku koncu bloku je vždy plno núl, potom za posledným nenulovým koeficientom sa použije dvojica (0,0). Ak sa vyskytne počas dekódovania, zostávajúce hodnoty sa rovnajú 0.

Zistené, že každý blok je zakódovaný, je uložený v súbore, ako je tento:
[Huffmanov kód pre dĺžku DC rozdielu]
[Huffmanov kód pre (počet núl pred AC 1, dĺžka AC 1]
…
[Huffmanov kód pre (počet núl pred AC n, dĺžka AC n]
Kde AC i - nenulové AC koeficienty.

Farebný obrázok

Spôsob, akým je farebný obrázok prezentovaný, závisí od zvoleného farebného modelu. Jednoduchým riešením je použiť RGB a zakódovať každý farebný kanál obrazu samostatne. Potom sa kódovanie nebude líšiť od kódovania šedého obrázka, iba práca je 3-krát viac. Ale kompresiu obrazu je možné zvýšiť, ak si uvedomíte, že oko je citlivejšie na zmeny jasu ako farby. To znamená, že farbu možno uložiť s väčšou stratou ako jas. RGB nemá samostatný kanál jasu. Závisí to od súčtu hodnôt každého kanála. Preto sa na uhlopriečku jednoducho „položí“ RGB kocka (toto je znázornenie všetkých možných hodnôt) – čím vyššie, tým svetlejšie. Nie je to však obmedzené na - kocka je mierne stlačená zo strán a ukazuje sa skôr ako rovnobežnosten, ale to len preto, aby sa zohľadnili zvláštnosti oka. Napríklad je náchylnejší na zelenú ako modrú. Takto sa objavil model YCbCr.

(Obrázok cez Intel.com)
Y je jasová zložka, Cb a Cr sú modrá a červená zložka farebného rozdielu. Preto, ak chcú viac komprimovať obraz, potom sa RGB skonvertuje na YCbCr a kanály Cb a Cr sa zdecimujú. To znamená, že sú rozdelené do malých blokov, napríklad 2x2, 4x2, 1x2, a všetky hodnoty jedného bloku sú spriemerované. Alebo inými slovami, znížte veľkosť obrazu pre tento kanál 2- až 4-krát vertikálne a/alebo horizontálne.

Každý blok 8x8 je zakódovaný (DCT + Huffman) a zakódované sekvencie sa zapíšu v tomto poradí:

Je zvláštne, že špecifikácia JPEG neobmedzuje výber modelu, to znamená, že implementácia kódovača môže ľubovoľne rozdeliť obrázok na farebné zložky (kanály) a každá bude uložená samostatne. Som si vedomý toho, že používam odtiene sivej (1 kanál), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4). Prvé tri podporuje takmer každý, no s poslednými 4-kanálovými sú problémy. FastStone, GIMP ich podporujú správne a štandardné programy pre Windows, paint.net správne extrahuje všetky informácie, ale potom vyhodí 4 čierny kanál, takže (Antelle povedal, že ho nevyhadzujú, prečítajte si jeho komentáre) zobrazia svetlejší obraz. Vľavo - klasický YCbCr JPEG, vpravo CMYK JPEG:

Ak sa líšia farbou alebo je viditeľný iba jeden obrázok, potom s najväčšou pravdepodobnosťou máte IE (akúkoľvek verziu) (UPD. V komentároch je uvedené „alebo Safari“). Môžete skúsiť otvoriť článok v rôznych prehliadačoch.

A ešte niečo

Stručne povedané, o ďalších funkciách.

Progresívny režim

Rozložme získané tabuľky DCT koeficientov na súčet tabuliek (približne takto (DC, -19, -22, 2, 1) = (DC, 0, 0, 0, 0) + (0, -20, -20, 0, 0) + (0, 1, -2, 2, 1)). Najprv zakódujeme všetky prvé výrazy (ako sme sa už naučili: Huffman a cik-cak bypass), potom druhý atď. hrubý obrázok s 8x8 „pixelmi“. Potom zaokrúhlite AC koeficienty na spresnenie čísla. Potom k nim hrubé opravy, potom presnejšie. A tak ďalej. Koeficienty sú zaokrúhlené, pretože v počiatočných fázach načítania nie je presnosť taká dôležitá, ale zaokrúhľovanie má pozitívny vplyv na dĺžku kódov, pretože každá fáza používa svoju vlastnú Huffmanovu tabuľku.

Bezstratový režim

Bezstratová kompresia. DCT č. Používa sa predpoveď 4. bodu od troch susedov. Chyby predpovedí kóduje Huffman. Podľa mňa sa používa trochu častejšie ako nikdy.

Hierarický režim

Z obrázka sa vytvorí niekoľko vrstiev s rôznym rozlíšením. Prvá hrubá vrstva je zakódovaná ako obvykle a potom už len rozdiel (spresnenie obrazu) medzi vrstvami (predstiera, že ide o Haarovu vlnku). Na kódovanie sa používa DCT alebo Lossless. Podľa mňa sa používa trochu menej často ako nikdy.

Aritmetické kódovanie

Huffmanov algoritmus generuje optimálne kódy pre váhu znakov, ale to platí len pre pevnú zhodu znakov s kódmi. Aritmetika nemá takú tuhú väzbu, čo umožňuje používať kódy, ako keby, s zlomkovým počtom bitov. Tvrdí sa, že znižuje veľkosť súboru v priemere o 10% v porovnaní s Huffmanom. Nie je bežné kvôli patentovým problémom, nie je podporované všetkými.

Dúfam, že teraz rozumiete algoritmu JPEG intuitívne. Vďaka za prečítanie!

UPD
vanwin ponúkol, že uvedie použitý softvér. S potešením oznamujem, že všetko je dostupné a zadarmo:

Python + NumPy + Matplotlib + PIL (vankúš)... Hlavný nástroj. Nájdené vydaním „bezplatnej alternatívy Matlabu“. Odporúčame! Aj keď nepoznáte Python, za pár hodín sa naučíte robiť výpočty a vytvárať krásne grafy.
JpegSnoop... Zobrazuje podrobné informácie o súbore jpeg.
yEd... Editor grafov.
Inkscape... Urobil v ňom ilustrácie, napríklad príklad Huffmanovho algoritmu. Prečítal som si niekoľko lekcií, ukázalo sa, že je to veľmi cool.
Daumov editor rovníc... Hľadal som editor vizuálnych vzorcov, pretože nie som veľmi priateľský s Latexom. Daum Equation - plugin pre Chrome, zistil som, že je to veľmi pohodlné. Okrem vyberania myšou môžete Latex upravovať.
FastStone... Myslím, že ho predstavovať netreba.
Picpick... Bezplatná alternatíva k SnagIt. Sedí v podnose, robí snímky obrazovky, čo hovoria, kde hovoria. Plus všelijaké vychytávky, ako pravítko, pipeta, uhlomer atď.

Štítky: Pridať štítky

Problémy so stratovými archivačnými algoritmami

Na archiváciu obrázkov sa prvýkrát použili známe algoritmy. Tie, ktoré sa používali a používajú v zálohovacích systémoch, pri vytváraní distribúcií atď. Tieto algoritmy archivovali informácie nezmenené. Hlavným trendom posledných rokov je však používanie nových tried obrázkov. Staré algoritmy už nespĺňajú požiadavky na archiváciu. Mnohé obrázky neboli prakticky komprimované, hoci „na prvý pohľad“ mali zjavnú nadbytočnosť. To viedlo k vytvoreniu nového typu algoritmov – stratových kompresných algoritmov. Spravidla sa v nich dá nastaviť pomer archivácie a tým aj miera straty kvality. Ide o kompromis medzi veľkosťou a kvalitou obrazu.

Jedným z vážnych problémov počítačovej grafiky je, že ešte nebolo nájdené adekvátne kritérium na posúdenie straty kvality obrazu. A neustále sa stráca – pri digitalizácii, pri prenose na obmedzenú paletu farieb, pri prenose do iného systému farebného znázornenia pre tlač a, čo je pre nás obzvlášť dôležité, pri archivácii so stratami. Môže byť uvedený príklad jednoduchého kritéria: štandardná odchýlka hodnôt pixelov (L 2 miera alebo odmocnina - RMS):

Podľa nej sa obraz vážne poškodí, keď sa jas zníži len o 5 % (oko to nepostrehne – nastavenie jasu sa pri rôznych monitoroch líši oveľa viac). Zároveň sa obrázky so „snežením“ - ostrá zmena farby jednotlivých bodov, slabé pruhy alebo „moaré“ budú považovať za „takmer nezmenené“ (Vysvetlite prečo?). Iné kritériá majú aj svoje nepríjemné stránky.

Zvážte napríklad maximálnu odchýlku:

Toto opatrenie, ako by ste mohli hádať, je mimoriadne citlivé na rytmus jednotlivých pixelov. Tie. v celom obraze sa môže výrazne zmeniť len hodnota jedného pixelu (čo je okom takmer nepostrehnuteľné), podľa tohto opatrenia však dôjde k vážnemu poškodeniu obrazu.

Miera, ktorá sa teraz používa v praxi, sa nazýva odstup signálu od špičky k šumu (PSNR).

Toto opatrenie je v skutočnosti podobné štandardnej odchýlke, ale je o niečo pohodlnejšie ho použiť kvôli logaritmickej škále stupnice. Má rovnaké nevýhody ako štandardná odchýlka.

Stratu kvality obrazu najlepšie vyhodnotia naše oči. Za výbornú sa považuje archivácia, pri ktorej nie je možné okom rozlíšiť pôvodné a rozbalené obrázky. Dobré – keď zistíte, ktorý z obrázkov bol archivovaný, môžete porovnať iba dva susediace obrázky. S ďalším zvýšením kompresného pomeru sa spravidla prejavia vedľajšie účinky charakteristické pre tento algoritmus. V praxi je možné aj pri výbornom zachovaní kvality v obraze vykonávať pravidelné, špecifické zmeny. Stratové archivačné algoritmy sa preto neodporúčajú na kompresiu obrázkov, ktoré sa neskôr vytlačia vo vysokej kvalite alebo spracujú programami na rozpoznávanie obrázkov. Nepríjemné efekty u takýchto obrázkov, ako sme už povedali, môžu nastať aj pri jednoduchom zmenšovaní obrázkov. Algoritmus JPEG

JPEG je jedným z najnovších a najvýkonnejších algoritmov. V praxi je to de facto štandard pre plnofarebné obrázky. Algoritmus pracuje s oblasťami 8x8, kde sa jas a farba menia pomerne hladko. Výsledkom je, že keď sa matica takejto oblasti rozšíri v dvojitom rade v kosínusoch (pozri vzorce nižšie), významné sú len prvé koeficienty. Kompresia v JPEG sa teda uskutočňuje na úkor plynulých zmien farieb v obraze.

Algoritmus vyvinutý skupinou fotografických expertov špeciálne na kompresiu 24-bitových obrázkov. JPEG – Joint Photographic Expert Group je divízia v rámci ISO – Medzinárodnej organizácie pre normalizáciu. Názov algoritmu znie ["jei" peg]. Vo všeobecnosti je algoritmus založený na diskrétnej kosínusovej transformácii (ďalej DCT) aplikovanej na maticu obrazu, aby sa získala nejaká nová matica koeficientov. Na získanie pôvodného obrázka sa použije inverzná transformácia.

DCT rozkladá obraz na amplitúdy určitých frekvencií. Pri transformácii teda dostaneme maticu, v ktorej je veľa koeficientov buď blízkych alebo rovných nule. Navyše, vďaka nedokonalosti ľudského videnia je možné koeficienty aproximovať hrubšie bez citeľnej straty kvality obrazu.

Na tento účel sa používa kvantovanie. V najjednoduchšom prípade ide o aritmetický bitový posun doprava. Touto transformáciou sa niektoré informácie stratia, ale možno dosiahnuť veľké kompresné pomery.

Ako funguje algoritmus

Poďme sa teda bližšie pozrieť na algoritmus. Povedzme, že komprimujeme 24-bitový obrázok.

Krok 1.

Obrázok z farebného priestoru RGB so zložkami zodpovednými za červenú (červenú), zelenú (zelenú) a modrú (modrú) zložku farby bodu preložíme do farebného priestoru YCrCb (niekedy nazývaného YUV).

V ňom je Y jasová zložka a Cr, Cb sú zložky zodpovedné za farbu (chromatická červená a chromatická modrá). Vzhľadom na skutočnosť, že ľudské oko je menej citlivé na farbu ako na jas, je možné archivovať polia pre zložky Cr a Cb s vysokými stratami, a teda vysokými kompresnými pomermi. Táto transformácia sa v televízii používa už dlho. Signálom zodpovedným za farbu je pridelené užšie frekvenčné pásmo.

Zjednodušený preklad z farebného priestoru RGB do farebného priestoru YCrCb možno znázorniť pomocou prechodovej matice:

Inverzná transformácia sa vykoná vynásobením YUV vektora inverznou maticou.

Krok 2.

Rozdeľte pôvodný obrázok na matice 8x8. Z každej vytvoríme tri pracovné matice DCT - 8 bitov samostatne pre každý komponent. Pri vyšších kompresných pomeroch môže byť tento krok trochu náročnejší. Obrázok je rozdelený zložkou Y - ako v prvom prípade a pre zložky Cr a Cb sa matice typujú cez čiaru a cez stĺpec. Tie. z pôvodnej matice 16x16 sa získa iba jedna pracovná matica DCT. Zároveň, ako je dobre vidieť, strácame 3/4 užitočných informácií o farebných zložkách obrázka a dostávame dvojnásobnú kompresiu naraz. Môžeme to urobiť prácou v priestore YCrCb. Ako ukázala prax, na výsledný RGB obraz to má malý vplyv.

Krok 3

Na každú pracovnú maticu aplikujeme DCT. V tomto prípade dostaneme maticu, v ktorej koeficienty v ľavom hornom rohu zodpovedajú nízkofrekvenčnej zložke obrazu av pravom dolnom rohu - vysokofrekvenčnej.

V zjednodušenej forme možno túto transformáciu znázorniť takto:

Krok 4

Kvantujeme. V podstate ide len o delenie pracovnej matice kvantizačnou maticou prvok po prvku. Pre každý komponent (Y, U a V), vo všeobecnom prípade je špecifikovaná vlastná kvantizačná matica q (ďalej MK). V tomto kroku sa riadi kompresný pomer a dochádza k najväčšej strate. Je jasné, že zadaním MK s veľkými koeficientmi získame viac núl a teda väčší kompresný pomer.

Kvantovanie je tiež spojené so špecifickými účinkami algoritmu. Pri veľkých hodnotách koeficientu gama môže byť strata na nízkych frekvenciách taká veľká, že sa obraz rozpadne na štvorce 8x8. Straty vo vysokých frekvenciách sa môžu prejaviť takzvaným „Gibbsovým efektom“, kedy sa okolo obrysov vytvára akési „halo“ s ostrým farebným prechodom.

Krok 5.

Maticu 8x8 preložíme na 64-prvkový vektor pomocou skenovania „cik-cak“, t.j. berieme prvky s indexmi (0,0), (0,1), (1,0), (2,0) ...

Na začiatku vektora teda dostaneme maticové koeficienty zodpovedajúce nízkym frekvenciám a na konci vysoké frekvencie.

Krok 6.

Konvolúcia vektora pomocou algoritmu skupinového kódovania. V tomto prípade dostaneme dvojice typu (preskočiť, číslo), kde „preskočiť“ je počítadlo preskočených núl a „číslo“ je hodnota, ktorú je potrebné vložiť do ďalšej bunky. Takže vektor 42 3 0 0 0 -2 0 0 0 0 1 ... bude zložený do párov (0,42) (0,3) (3, -2) (4,1) ....

Krok 7.

Konvoluujte výsledné páry pomocou Huffmanovho kódovania s pevnou tabuľkou.

Proces obnovy obrazu v tomto algoritme je úplne symetrický. Metóda vám umožňuje komprimovať niektoré obrázky 10-15 krát bez vážnej straty.

Operačný kanál používaný v algoritme JPEG.

Významné pozitívne aspekty algoritmu sú:

Kompresný pomer je nastavený.
Víkend farebný obrázok môže mať 24 bitov na bod.

Nevýhody algoritmu sú tieto:

Keď sa kompresný pomer zvýši, obrázok sa rozdelí na samostatné štvorce (8x8). Je to spôsobené tým, že pri nízkych frekvenciách počas kvantovania dochádza k veľkým stratám a nie je možné obnoviť pôvodné dáta.
Prejavuje sa Gibbsov efekt - haló pozdĺž hraníc ostrých farebných prechodov.

Ako už bolo spomenuté, JPEG bol štandardizovaný relatívne nedávno - v roku 1991. Ale aj vtedy existovali algoritmy, ktoré komprimovali silnejšie s menšou stratou kvality. Faktom je, že akcie vývojárov štandardu boli obmedzené silou technológie, ktorá v tom čase existovala. To znamená, že aj na osobnom počítači musel algoritmus pracovať menej ako minútu na priemernom obrázku a jeho hardvérová implementácia musela byť relatívne jednoduchá a lacná. Algoritmus musel byť symetrický (čas dekompresie je približne rovnaký ako čas archivácie).

Posledná uvedená požiadavka umožnila hračkám, akými sú digitálne fotoaparáty – zariadenia s veľkosťou malej videokamery, robiť 24-bitové fotografie na 10-20 MB flash kartu s rozhraním PCMCIA. Potom sa táto karta vloží do slotu na vašom notebooku a príslušný program vám umožní čítať obrázky. Nie je pravda, že ak by bol algoritmus asymetrický, bolo by nepríjemné dlho čakať, kým sa zariadenie „dobije“ – skomprimuje obraz.

Nie veľmi príjemnou vlastnosťou JPEG je aj fakt, že často sú horizontálne a vertikálne pruhy na displeji úplne neviditeľné a môžu sa objaviť až pri tlači vo forme moaré. Vyskytuje sa vtedy, keď sa na vodorovné a zvislé pruhy obrázka prekryje šikmá tlačová mriežka. Kvôli týmto prekvapeniam sa JPEG neodporúča aktívne používať pri tlači, pretože má vysoké koeficienty. Pri archivácii záberov určených na prezeranie človekom je však v súčasnosti nenahraditeľný.

Široké používanie JPEG bolo dlho obmedzené, možno len tým, že pracuje s 24-bitovými obrázkami. Preto, aby bolo možné zobraziť obraz v prijateľnej kvalite na bežnom monitore v 256-farebnej palete, bolo potrebné použiť vhodné algoritmy, a teda aj určitý čas. V aplikáciách zameraných na náročných používateľov, ako sú hry, sú takéto oneskorenia neprijateľné. Okrem toho, ak sú obrázky, povedzme, konvertované v 8-bitovom formáte GIF na 24-bitový JPEG a potom späť na GIF na prezeranie, potom dôjde k strate kvality dvakrát pri oboch prevodoch. Napriek tomu je nárast veľkosti archívov často taký veľký (3-20 krát!) A strata kvality je taká malá, že ukladanie obrázkov vo formáte JPEG je veľmi efektívne.

Je potrebné povedať niekoľko slov o modifikáciách tohto algoritmu. Hoci JPEG je štandard ISO, jeho formát súboru nebol opravený. Výrobcovia využívajú túto výhodu a vytvárajú svoje vlastné nekompatibilné formáty, a preto môžu zmeniť algoritmus. Interné tabuľky algoritmu odporúčaného ISO sú nimi nahradené vlastnými. Okrem toho je trochu zmätok pri špecifikácii straty. Napríklad pri testovaní sa ukázalo, že „výborná“ kvalita, „100 %“ a „10 bodov“ poskytujú výrazne odlišné obrázky. Mimochodom, „100%“ kvalita neznamená bezstratovú kompresiu. Existujú aj možnosti JPEG pre konkrétne aplikácie.

Ako norma ISO sa JPEG stále viac používa pri výmene obrázkov cez počítačové siete. Algoritmus JPEG je podporovaný vo formátoch Quick Time, PostScript Level 2, Tiff 6.0 a v súčasnosti zaujíma popredné miesto v multimediálnych systémoch.

Charakteristika algoritmu JPEG:

Trieda obrázka: Plnofarebné 24-bitové obrázky alebo obrázky v odtieňoch sivej bez ostrých farebných prechodov (fotografie).

symetria: 1

Charakteristika: V niektorých prípadoch algoritmus vytvára „halo“ okolo ostrých horizontálnych a vertikálnych okrajov v obraze (Gibbsov efekt). Navyše, keď je kompresný pomer vysoký, obraz sa rozdelí na bloky 8x8 pixelov.

Fraktálny algoritmus

Myšlienka metódy

Archivácia fraktálov je založená na tom, že obraz zobrazujeme v kompaktnejšej podobe – pomocou koeficientov Iterated Function System (ďalej len IFS). Skôr než sa pozrieme na samotný proces archivácie, pozrime sa na to, ako IFS buduje imidž, t.j. dekompresný proces.

Presne povedané, IFS je súbor trojrozmerných afinných transformácií, v našom prípade transformujúcich jeden obrázok na druhý. Body v trojrozmernom priestore sú transformované (súradnica x, súradnica y, jas).

Tento proces najjasnejšie demonštroval Barnsley vo svojej knihe „Fractal Image Compression“. Tam bol predstavený koncept kopírky, ktorý pozostáva z obrazovky, na ktorej je zobrazený pôvodný obrázok, a zo systému šošoviek premietajúcich obraz na inú obrazovku:

Šošovky môžu premietať časť obrazu voľný tvar kdekoľvek inde na novom obrázku.
Oblasti v ktorom obrázky sa premietajú nepretínajú sa.
Objektív môže zmeniť jas a znížiť kontrast.
Objektív môže zrkadliť a otáčať fragment vášho obrázka.
Objektív by mal do mierky(zmenšiť) svoj fragment obrázka.

Umiestnením šošoviek a zmenou ich charakteristík môžeme kontrolovať výsledný obraz. Jedna iterácia práce stroja spočíva v tom, že sa z pôvodného obrazu vytvorí nový pomocou dizajnu, po ktorom sa nový berie ako počiatočný. Tvrdí sa, že v procese iterácie získame obraz, ktorý sa prestane meniť. Bude to závisieť iba od umiestnenia a vlastností šošoviek a nebude to závisieť od pôvodného obrázka. Tento obrázok sa nazýva „ pevný bod"alebo atraktor tohto IFS. Zodpovedajúca teória zaručuje, že pre každý IFS existuje presne jeden pevný bod.

Keďže mapovanie šošoviek je kompresné, každá šošovka výslovne špecifikuje sebepodobný oblasti na našom obrázku. Vďaka vlastnej podobnosti získame komplexnú štruktúru obrazu pri akomkoľvek zväčšení. Je teda intuitívne jasné, že systém iterovateľných funkcií definuje fraktál(voľne - sebepodobný matematický objekt).

Najznámejšie sú dva obrázky IFS: Sierpinski Triangle a Barnsley Fern. „Sierpinského trojuholník“ je definovaný tromi a „Barnsleyova papraď“ štyrmi afinnými transformáciami (alebo v našej terminológii „šošovkami“). Každá transformácia je zakódovaná doslova čítanými bajtmi, pričom s ich pomocou vytvorený obraz môže zaberať niekoľko megabajtov.

Aktivita: Nakreslite na obrázok 4 oblasti, ktoré by sa spojili, aby pokryli celý obrázok, pričom každá z nich by bola podobná celému obrázku (nezabudnite na stonku papradia).

Z vyššie uvedeného je zrejmé, ako archivátor funguje a prečo to trvá tak dlho. V skutočnosti je fraktálna kompresia hľadaním sebepodobných oblastí v obraze a definovaním parametrov afinných transformácií pre ne.

=>
V najhoršom prípade, ak sa nepoužije optimalizačný algoritmus, bude potrebné spočítať a porovnať všetky možné fragmenty obrazu rôznych veľkostí. Dokonca aj pre malé obrázky, ak vezmeme do úvahy diskrétnosť, dostaneme astronomické množstvo možností, ktoré je potrebné hľadať. Navyše ani prudké zúženie transformačných tried, napríklad v dôsledku škálovania iba o určitý počet krát, neprináša znateľný zisk v čase. Navyše sa stráca kvalita obrazu. Prevažná väčšina výskumov v oblasti fraktálnej kompresie je teraz zameraná na skrátenie doby archivácie potrebnej na získanie vysokokvalitného obrazu.

Definícia.

kde A b c d e f reálne čísla a volá sa dvojrozmerná afinná transformácia.

Definícia. Transformácia reprezentovaná ako

kde a, b, c, d, e, f, p, q, r, s, t, u sú reálne čísla a nazýva sa trojrozmerná afinná transformácia.

Definícia. Nech je transformácia v priestore X. Ide o to, čo sa nazýva pevný bod(atraktor) premena.

Definícia. Transformácia v metrickom priestore (X, d) sa nazýva kontrahovanie, ak existuje číslo s:, taký, že

komentár: Formálne môžeme na fraktálnu kompresiu použiť akékoľvek mapovanie kontrakcií, ale v skutočnosti sa používajú iba trojrozmerné afinné transformácie s dosť silnými obmedzeniami na koeficienty.

Veta. (O zmluvnej transformácii)

Nechajte vložiť úplný metrický priestor (X, d). Potom existuje presne jeden pevný bod tejto transformácie a pre každý bod postupnosť konverguje k.

Všeobecnejšia formulácia tejto vety zaručuje konvergenciu.

Definícia. Obrázok je funkcia S definovaná na jednotkovej štvorci a nadobúdajúca hodnoty od 0 do 1 resp

Nechajte trojrozmernú afinnú transformáciu zapísať vo forme

a je definovaný na kompaktnej podmnožine karteziánskeho štvorca x. Potom prenesie časť povrchu S do oblasti nachádzajúcej sa s posunom (e, f) a rotácia daná maticou

Navyše, ak budeme interpretovať hodnotu S ako sa jas zodpovedajúcich bodov zníži v pčasov (transformácia musí byť kompresná) a zmena na posun q.

Definícia. Konečná populácia W kontrahovanie trojrozmerných afinných transformácií definovaných na doménach tak, že sa volá systém iterovateľných funkcií ( IFS).

Systém iterovaných funkcií je jednoznačne spojený s pevným bodom – obrázkom. Proces kompresie má teda nájsť systémové koeficienty a proces dekompresie má za úlohu opakovať systém, kým sa získaný obraz nestabilizuje (pevný bod IFS). V praxi stačí 7-16 iterácií. Oblasti budú ďalej označované ako zoradené a oblasti - doména.

Konštrukcia algoritmu

Ako už bolo zrejmé z vyššie uvedeného, hlavnou úlohou pri kompresii fraktálneho algoritmu je nájsť zodpovedajúce afinné transformácie. V najvšeobecnejšom prípade vieme preložiť obrazové oblasti ľubovoľnej veľkosti a tvaru, no v tomto prípade dostaneme astronomický počet iterovaných verzií rôznych fragmentov, ktoré nie je možné momentálne spracovať ani na superpočítači.

V cvičná verzia algoritmu nižšie platia nasledujúce obmedzenia oblasti:

Všetky oblasti sú štvorce so stranami rovnobežnými so stranami obrázka. Toto obmedzenie je dosť prísne. V skutočnosti ideme aproximovať celú škálu geometrických tvarov iba pomocou štvorcov.
Pri preklade doménovej domény do hodnotenej domény sa vykoná zmenšenie veľkosti presne dvakrát... To značne zjednodušuje kompresor aj dekompresor úloha škálovania malých plôch nie je triviálna.
Všetky bloky domény sú štvorce a majú pevná veľkosť... Obrázok je rozdelený jednotnou mriežkou na sadu doménových blokov.
Zaberajú sa rozsahy domén „Cez bod“ pozdĺž X a Y, čo okamžite zníži vyhľadávanie 4-krát.
Pri preklade domény domény na rotáciu poradia kocky je to možné len na 0 0, 90 0, 180 0 alebo 270 0... Povolený je aj zrkadlový odraz. Celkový počet možných transformácií (počítajúc prázdne) je 8.
Vykonáva sa vertikálne škálovanie (stlačenie) (jas). pevne stanovený počet krát- 0,75.

Tieto obmedzenia vám umožňujú:

Zostavte algoritmus, ktorý vyžaduje relatívne malý počet operácií aj na pomerne veľkých obrázkoch.
Je veľmi kompaktný na reprezentáciu údajov pre zápis do súboru. Pre každú afinnú transformáciu v IFS potrebujeme:

dve čísla na nastavenie posunu bloku domény. Ak obmedzíme vstupné obrázky na 512x512, tak bude stačiť 8 bitov na každé číslo.
tri bity na nastavenie transformácie symetrie pri preklade bloku domény na blok poradia.
7-9 bitov, aby ste nastavili posun jasu počas prekladu.

Informácie o veľkosti bloku môžu byť uložené v hlavičke súboru. Na jednu afinnú transformáciu sme teda minuli menej ako 4 bajty. V závislosti od veľkosti bloku môžete vypočítať, koľko blokov bude na obrázku. Takto môžeme získať odhad stupňa kompresie.

Napríklad pre súbor v odtieňoch sivej s 256 farbami 512 x 512 pixelov s veľkosťou bloku 8 pixelov budú afinné transformácie 4 096 (512 / 8 x 512 / 8). Každý bude vyžadovať 3,5 bajtu. Ak teda pôvodný súbor mal 262144 (512x512) bajtov (bez zohľadnenia hlavičky), súbor s koeficientmi zaberie 14336 bajtov. Pomer archivácie je 18-násobný. Zároveň neberieme do úvahy, že súbor s koeficientmi môže mať aj redundanciu a archivovať ho bezstratovou metódou archivácie, napríklad LZW.

Nevýhody navrhovaných obmedzení:

Keďže všetky oblasti sú štvorce, nie je možné využiť podobnosť objektov, ktoré sú ďaleko od štvorcov (ktoré sú na skutočných obrázkoch celkom bežné.)
Podobne nebudeme môcť použiť podobnosť objektov na obrázku, pričom koeficient podobnosti medzi nimi je veľmi odlišný od 2.
Algoritmus nebude môcť využiť podobnosť objektov na obrázku, uhol medzi nimi nie je násobkom 90 0.

Toto je poplatok za rýchlosť kompresie a pre jednoduchosť zabaľovania koeficientov do súboru.

Samotný baliaci algoritmus je zredukovaný na vymenovanie všetkých blokov domény a výber pre každý zodpovedajúci blok poradia. Nižšie je uvedený diagram tohto algoritmu.

pre (všetky bloky rozsahu) (
min_distance = MaximumDistance;
R ij= obrázok-> CopyBlock (i, j);
for (všetky bloky domény) (// S otáčkami a neg.
prúd = Súradnice prúdu. transformácie;
D = obrázok-> CopyBlock (aktuálny);
aktuálna_vzdialenosť = R ij.L2vzdialenost (D);
if (aktuálna_vzdialenosť< min_distance) {
// Ak sú najlepšie šance horšie:
min_distance = aktuálna_vzdialenosť;
najlepší = aktuálny;
}
) // Ďalší rozsah
Save_Coefficients_to_file (najlepšie);
) // Ďalšia doména

Ako je zrejmé z vyššie uvedeného algoritmu, pre každý blok poradia ho skontrolujeme so všetkými možnými blokmi domény (vrátane tých, ktoré prešli transformáciou symetrie), nájdeme možnosť s najmenšou mierou L 2 (najmenšia smerodajná odchýlka) a uložte koeficienty tejto transformácie do súboru. Koeficienty sú (1) súradnice nájdeného bloku, (2) číslo od 0 do 7, ktoré charakterizuje transformáciu symetrie (rotácia, odraz bloku) a (3) posun jasu pre túto dvojicu blokov. Posun jasu sa vypočíta takto:

kde r ij- hodnoty pixelov bloku poradia ( R), a d ij- hodnoty pixelov bloku domény ( D). V tomto prípade sa opatrenie považuje za:

Nepočítame druhú odmocninu L 2 opatrenia a nerozdeľujte ho na n, keďže tieto transformácie sú monotónne a nezabránia nám nájsť extrém, budeme však môcť pre každý blok vykonať o dve operácie menej.

Vypočítajme počet operácií potrebných na kompresiu obrázka v odtieňoch šedej 256 farieb 512 x 512 pixelov s veľkosťou bloku 8 pixelov:

Podarilo sa nám teda zredukovať počet operácií kompresného algoritmu na celkom vyčísliteľné (aj keď za pár hodín) hodnoty.

Schéma algoritmu dekompresie obrazu

Dekompresia algoritmu fraktálnej kompresie je extrémne jednoduchá. Je potrebné vykonať niekoľko iterácií trojrozmerných afinných transformácií, ktorých koeficienty boli získané v štádiu kompresie.

Ako počiatočný môže byť braný úplne akýkoľvek obrázok (napríklad úplne čierny), keďže príslušný matematický aparát nám zaručuje konvergenciu sekvencie obrázkov získaných pri IFS iteráciách k statickému obrázku (blízkeho pôvodnému). Zvyčajne na to stačí 16 iterácií.

Prečítajte si koeficienty všetkých blokov zo súboru;
Vytvorte čierny obrázok požadovanej veľkosti;
Kým (obrázok sa nepohne) (
Pre (každý rozsah (R)) (
D = obrázok-> CopyBlock (D_coord_for_R);
Pre (každý pixel ( i, j) v bloku (
R ij = 0,75 D ij + o R;
) // Ďalší pixel
) // Ďalší blok
) // Až do konca

Keďže sme si zapísali koeficienty pre bloky R ij(čo, ako sme už diskutovali, sú v našom konkrétnom prípade štvorce rovnakej veľkosti) dôsledne, ukáže sa, že obrázok postupne vyplníme štvorcami mriežky rozdelenia pomocou afinnej transformácie.

Ako môžete vypočítať, počet operácií na jeden pixel obrázka v odtieňoch sivej počas obnovy je nezvyčajne malý (N operácií „+“, 1 operácií „*“, kde N je počet opakovaní, tj 7-16). Vďaka tomu je dekompresia obrázkov pre fraktálny algoritmus rýchlejšia ako dekompresia, napríklad pre algoritmus JPEG, v ktorom je 64 „+“ operácií a 64 „? “(Okrem krokov RLE a Huffmanovho kódovania!). V tomto prípade pre fraktálny algoritmus dochádza k násobeniu racionálnym číslom, jedným pre každý blok. To znamená, že môžeme najprv použiť celočíselnú racionálnu aritmetiku, ktorá je výrazne rýchlejšia ako aritmetika s pohyblivou rádovou čiarkou. Po druhé, násobenie vektora číslom je jednoduchšia a rýchlejšia operácia, často zakomponovaná do architektúry procesora (procesory SGI, Intel MMX ...), ako bodový súčin dvoch vektorov, ktorý je nevyhnutný v prípade JPEG. Pri plnofarebnom obrázku sa situácia kvalitatívne nemení, keďže oba algoritmy využívajú preklad do iného farebného priestoru.

Odhad strát a spôsoby ich regulácie

V súhrne zjednodušenej verzie algoritmu bolo vynechaných veľa dôležitých otázok. Napríklad, čo robiť, ak algoritmus nemôže nájsť podobný pre žiadny fragment obrázka? Jednoznačným riešením je rozdeliť tento fragment na menšie a pokúsiť sa ich vyhľadať. Zároveň je jasné, že tento postup nemožno opakovať donekonečna, inak sa počet potrebných transformácií zvýši natoľko, že algoritmus prestane byť kompresným algoritmom. Preto počítame so stratou v niektorej časti obrazu.

Pre algoritmus fraktálnej kompresie, ako aj pre iné stratové kompresné algoritmy, sú veľmi dôležité mechanizmy, ktorými bude možné upraviť kompresný pomer a stratový pomer. K dnešnému dňu bol vyvinutý pomerne veľký súbor takýchto metód. Po prvé, je možné obmedziť počet afinných transformácií, pričom sa vedome zabezpečí, že kompresný pomer nie je nižší ako pevná hodnota. Po druhé, je možné požadovať, aby v situácii, keď je rozdiel medzi spracovaným fragmentom a jeho najlepšou aproximáciou vyšší ako určitá prahová hodnota, bol tento fragment rozdrvený (na to je potrebných niekoľko „šošoviek“). Po tretie, môžete zakázať delenie fragmentov menších ako napríklad štyri body. Zmenou prahových hodnôt a priority týchto podmienok budeme veľmi flexibilne ovládať kompresný pomer obrázka v rozsahu od bitmapy po akýkoľvek kompresný pomer. Upozorňujeme, že táto flexibilita bude oveľa vyššia ako flexibilita najbližšieho rivala, algoritmu JPEG.

Charakteristika fraktálového algoritmu :

Kompresné pomery: 2-2000 (definované používateľom).

Trieda obrázka: Plnofarebné 24-bitové obrázky alebo obrázky v odtieňoch sivej bez ostrých farebných prechodov (fotografie). Je žiaduce, aby oblasti s väčšou dôležitosťou (pre vnímanie) boli kontrastnejšie a ostrejšie a oblasti s menšou dôležitosťou - s nízkym kontrastom a rozmazané.

symetria: 100-100000

Charakteristika: Môže ľubovoľne meniť mierku obrazu pri rozopínaní, zväčšovať ho 2-4 krát bez toho, aby sa objavil „efekt schodiska“. So zvyšujúcim sa stupňom kompresie sa na hraniciach blokov v obraze objaví „blokový“ efekt.

Rekurzívny (vlnový) algoritmus

Anglický názov pre rekurzívnu kompresiu je wavelet. Do ruštiny sa prekladá ako kompresia vĺn a kompresia pomocou impulzov. Tento typ archivácie je známy už dlho a priamo vychádza z myšlienky využitia koherencie oblastí. Algoritmus je zameraný na farebné a čiernobiele obrázky s plynulými prechodmi. Ideálne pre snímky, ako sú röntgenové snímky. Kompresný pomer je nastavený a pohybuje sa od 5-100. Keď sa pokúsite nastaviť vyšší koeficient na ostrých hranách, najmä tých, ktoré prechádzajú pozdĺž uhlopriečky, objaví sa „efekt schodiska“ - kroky rôzneho jasu, veľkosť niekoľkých pixelov.

Myšlienkou algoritmu je, že rozdiel uložíme do súboru - číslo medzi priemernými hodnotami susedných blokov na obrázku, ktoré zvyčajne nadobúda hodnoty blízke 0.

Takže dve čísla a 2i a a 2i +1 môže byť vždy reprezentovaný ako b 1 i=(a 2i +a 2i +1 ) / 2 a b 2 i=(a 2i -a 2i +1 ) / 2. Podobne aj postupnosť a imôžu byť párovo preložené do sekvencie b 1,2 i.

Pozrime sa na konkrétny príklad: komprimujme reťazec hodnôt jasu 8 pixelov ( a i): (220, 211, 212, 218, 217, 214, 210, 202). Získame nasledujúce sekvencie b 1 i a b 2 i: (215,5, 215, 215,5, 206) a (4,5, -3, 1,5, 4). Všimnite si, že hodnoty b 2 isú dostatočne blízke 0. Operáciu zopakujeme, berúc do úvahy b 1 i ako a i... Táto akcia sa vykonáva ako keby rekurzívne, odtiaľ názov algoritmu. Získame z (215,5, 215, 215,5, 206): (215,25, 210,75) (0,25, 4,75). Získané koeficienty, zaokrúhlené na celé čísla a komprimované napríklad pomocou Huffmanovho algoritmu s pevnými tabuľkami, môžeme vložiť do súboru.

Všimnite si, že našu transformáciu sme použili na reťaz len dvakrát. V skutočnosti si môžeme dovoliť aplikovať vlnkovú transformáciu 4-6 krát. Okrem toho je možné získať dodatočnú kompresiu pomocou nejednotných Huffmanových tabuliek krokov (t. j. musíme uložiť Huffmanov kód pre najbližšiu hodnotu v tabuľke). Tieto techniky vám umožňujú dosiahnuť výrazné kompresné pomery.

Cvičenie: Obnovili sme reťaz (215, 211) (0, 5) (5, -3, 2, 4) zo súboru (pozri príklad). Zostavte reťazec ôsmich hodnôt jasu pixelov, ktoré znovu vytvorí algoritmus kompresie vĺn.

Algoritmus pre 2D dáta je implementovaný podobným spôsobom. Ak máme štvorec 4 bodov s jasom a 2 i, 2 j,a 2 i + 1, 2 j,a 2 i, 2 j +1 a a 2 i + 1, 2 j + 1, potom

Pôvodné		B 1	B 2
obrázok		B 3	B 4

Pomocou týchto vzorcov pre obrázok s rozmermi 512 x 512 pixelov po prvej transformácii získame 4 matice 256 x 256 prvkov:

-- Prvý, ako možno uhádnete, uloží zmenšenú kópiu obrázka. V druhom prípade sú spriemerované rozdiely párov hodnôt pixelov horizontálne. Po tretie, spriemerované rozdiely párov hodnôt pixelov pozdĺž vertikály. Štvrtý obsahuje spriemerované rozdiely v hodnotách pixelov pozdĺž uhlopriečky. Analogicky s dvojrozmerným prípadom môžeme našu transformáciu zopakovať a namiesto prvej matice dostaneme 4 matice veľkosti 128x128. Opakovaním našej transformácie tretíkrát dostaneme výsledok: 4 matice 64x64, 3 matice 128x128 a 3 matice 256x256. V praxi sa pri zápise do súboru hodnoty získané v poslednom riadku () zvyčajne zanedbávajú (okamžite získajú asi tretinu veľkosti súboru - 1 - 1/4 - 1/16 - 1/64 ... ).

Výhody tohto algoritmu možno pripísať skutočnosti, že veľmi ľahko umožňuje realizovať možnosť postupného „vývoja“ obrazu pri prenose obrazu cez sieť. Okrem toho, keďže v skutočnosti ukladáme kópiu miniatúry na začiatok obrázka, uľahčuje to zobrazenie „hrubého“ obrázka podľa názvu.

Na rozdiel od JPEG a fraktálneho algoritmu táto metóda nefunguje v blokoch, napríklad 8x8 pixelov. Presnejšie, operujeme s blokmi 2x2, 4x4, 8x8 atď. Tým, že si koeficienty pre tieto bloky ukladáme samostatne, sa však pomerne ľahko vyhneme rozdeleniu obrázku na „mozaikové“ štvorčeky.

Charakteristika vlnového algoritmu:

Kompresné pomery: 2-200 (definované používateľom).

Trieda obrázka: Ako fraktál a JPEG.

symetria: ~1.5

Charakteristika: Navyše, keď je kompresný pomer vysoký, obraz sa rozdelí na samostatné bloky.

Záver

Na záver zvážte tabuľky, ktoré spájajú parametre rôznych vyššie uvedených algoritmov kompresie obrazu.

Algoritmus	Vlastnosti obrazu, vďaka ktorým dochádza ku kompresii
RLE	Po sebe idúce identické farby: 2 2 2 2 2 2 15 15 15
LZW	Identické reťazce: 2 3 15 40 2 3 15 40
Huffman	Rozdielna frekvencia farieb: 2 2 3 2 2 4 3 2 2 2 4
CCITT-3	V obraze prevláda biela, veľké plochy vyplnené jednou farbou
Rekurzívne	Hladké farebné prechody a žiadne ostré hrany
Jpeg	Nedostatok ostrých hraníc
Fraktál	Podobnosť medzi prvkami obrázka

Algoritmus	Kompresná súprava	Časová symetria	Prečo orientovaný	Straty	Rozmer
RLE	32, 2, 0.5	1	3,4 bit	nie	1D
LZW	1000, 4, 5/7	1.2-3	1-8 bit	nie	1D
Huffman	8, 1.5, 1	1-1.5	8 bit	nie	1D
CCITT-3	213(3), 5, 0.25	~1	1-bitový	nie	1D
JBIG	2-30 krát	~1	1-bitový	nie	2D
Bezstratový JPEG	2 krát	~1	24-bitová, šedá	nie	2D
Jpeg	2-20 krát	~1	24-bitová, šedá	Áno	2D
Rekurzívna kompresia	2-200 krát	1.5	24-bitová, šedá	Áno	2D
Fraktál	2-2000 krát	1000-10000	24-bitová, šedá	Áno	2,5D

Ak chcete efektívne komprimovať údaje, musíte najskôr vyhodnotiť povahu obrázka. JPEG komprimuje grafické údaje na základe toho, čo vidí ľudské oko. Preto, aby som vám pomohol pochopiť, ako a čo robí JPEG, by som vám rád poskytol prehľad ľudského vizuálneho vnímania.

Kompresia JPEG prebieha v niekoľkých fázach. Cieľom je transformovať grafické dáta takým spôsobom, aby sa bezvýznamné vizuálne informácie dali ľahko identifikovať a zahodiť. Táto „stratová“ kompresia sa líši od väčšiny ostatných prístupov používaných pri grafických formátoch, ktoré sa snažia zachovať každý kúsok obrazu nedotknutý.

Farebný model

Prvým krokom v JPEG je výber vhodného spôsobu znázornenia farieb. Farby sú zvyčajne špecifikované v 3D súradnicovom systéme. Systém, ktorý väčšina programátorov dobre pozná, popisuje farbu ako kombináciu červenej, zelenej a modrej (RGB). Bohužiaľ, z hľadiska stlačiteľnosti to nie je najlepší spôsob, ako opísať farbu. Problém je v tom, že všetky tri zložky – červená, zelená a modrá – sú rovnaké. Prechod na iný farebný systém však umožňuje zvýrazniť niektoré dôležitejšie informácie.

Profesionáli používajú dva farebné modely: HSL (Hue-Saturation-Lightness) a HSV (Hue-Saturation-Value). Je intuitívne jasné, že zložka Svetlosti modelu HSL a zložka jasu (Value) modelu HSV určujú pomer svetla a tieňa svojim vlastným spôsobom. Sýtosť definuje úroveň „čistej“ farby. Desaturované farby sú často neformálne označované ako „sivé“. Odtieň je to, čo vnímame ako farbu objektu, napríklad červenú alebo sivozelenú. Tu je dôležité poznamenať úžasný fakt: ľudské videnie je citlivejšie na zmeny v osvetlení, a nie na farbu ako takú!

Rôzne implementácie kompresného algoritmu JPEG používajú rôzne systémy farieb. Systém podania farieb YCbCr používaný spoločnosťou JFIF je veľmi podobný systému vyvinutému pred mnohými rokmi pre farebnú televíziu.

Preriedenie

Hlavným dôvodom prevodu jedného farebného modelu na iný je potreba identifikovať informácie, ktoré sú menej podstatné pre zobrazenie obrázku. JPEG znižuje množstvo farebných informácií. Kým zložka luma sa prenáša v plnom rozlíšení, zložky farebného rozdielu využívajú polovičný rozsah hodnôt. V dôsledku tohto jednoduchého kroku sa objem dát zníži o jednu tretinu.

Subsampling upravuje farby farebného TV obrazu. Čiernobiele obrázky a farebné informácie sa zvyčajne prenášajú do televízie oddelene. Informácie o farbe sa navyše prenášajú v menej prísnej forme ako informácie o jase obrazu.

Diskrétna kosínusová transformácia (DCT)

Každá farebná zložka je spracovaná samostatne, ako keby nešlo o jednofarebné, ale o tri obrázky v odtieňoch šedej. Ak sa pozriete na detailný obrázok z veľkej vzdialenosti, môžete rozlíšiť iba všeobecný tón obrázka. Napríklad „väčšinou modrá“ alebo „väčšinou červená“. Čím bližšie k obrázku, tým viac detailov môžete vidieť. Na napodobnenie tohto efektu používa JPEG jeden matematický trik s názvom Discrete Cosine Transform (DCT). DCT konvertuje informácie o pixeloch na informácie o zmene pixelov. Prvá vec, ktorú môže DCT poskytnúť, je priemerná farba oblasti. Potom čoraz viac dolaďuje detaily.

Rovnako ako pri vzdialenom obrázku je priemerná hodnota farby veľmi dôležitou informáciou o ploche obrázka. Vaše oko je menej citlivé na rýchlosť zmeny farby, takže to nie je také dôležité. Transformáciou farebných informácií týmto spôsobom zvýrazníme informácie, ktoré je možné darovať.

Predpokladá sa, že straty sú spôsobené touto fázou. Ak zakódujete obrázok pomocou DCT a potom použijete inverznú funkciu DCT na jeho rekonštrukciu, nezískate presne rovnakú sadu bitov. Táto chyba je však chybou zaokrúhľovania. Vyskytuje sa pri vykonávaní aritmetických operácií a zvyčajne nie je príliš veľký. Preto radšej považujem fázu DCT za „väčšinou bezstratovú“ akciu.

V prípade veľkých obrázkov je výpočet DCT a reverzného DCT veľmi časovo náročný proces. Aby sa skrátil čas výpočtu, JPEG rozdelí obrázok na mozaiku s rozmermi 8 x 8 pixelov. Každá z mozaík je spracovaná samostatne, čo výrazne skracuje výpočtový čas potrebný pre DCT. Problém, ktorý vzniká pri tomto prístupe je, že po kvantovaní (o ktorej sa bude diskutovať v ďalšej časti) sa hranice týchto štvorcov nemusia zhodovať, a preto sa stanú viditeľnými, keď je parameter kvality nastavený na nízku hodnotu.

Kvantovanie

Vývojári JPEG sa primárne zaujímali o fotografické obrázky so súvislými tónmi. Tieto obrázky v odtieňoch sivej sa zvyčajne vyznačujú jemnými prechodmi z jednej farby do druhej. Pre takéto obrázky je nízkofrekvenčná (pomaly sa meniaca) zložka DCT dôležitejšia ako vysokofrekvenčná (rýchlo sa meniaca) zložka.

Termín kvantizácia jednoducho znamená zaokrúhľovanie. JPEG zahodí niektoré grafické informácie zaokrúhlením každého člena DCT s rôznymi váhami na základe rôznych faktorov. Vysokofrekvenčná zložka je zaoblená silnejšie ako nízkofrekvenčná zložka. Napríklad nízkofrekvenčná zložka, v ktorej je uložená priemerná hodnota jasu, môže byť zaokrúhlená na násobky troch, kým vysokofrekvenčná zložka môže byť zaokrúhlená na násobky sto!

Operácia kvantovania vysvetľuje, prečo kompresia JPEG vedie k „chveniu“ čiar v prípade ostrých obrysov. Obrysy sú definované vysokofrekvenčnou (rýchlo sa meniacou) priestorovou zložkou. (Na prvý pohľad sa môže zdať, že by ste mali mať rozmazaný obrys, ale nezabudnite, že C v DCT znamená kosínus.)

Typicky sú farebné roviny kvantované oveľa hrubšie ako luma roviny. Tu výber správneho farebného modelu pomáha odhaliť informácie, ktoré možno zahodiť.

Kompresia

Až doteraz, s výnimkou vzorkovacej frekvencie dvoch farebných kanálov, nedošlo k žiadnej kompresii. Všetky vyššie uvedené kroky – konverzia farebného modelu, DCT a kvantizácia – ponechali veľkosť údajov nezmenenú. Nakoniec sa dostávame k poslednému kroku, počas ktorého sa dáta skutočne zmenšia pomocou štandardných techník bezstratovej kompresie.

Údaje uložené v predchádzajúcich krokoch je možné komprimovať efektívnejšie ako surový surový materiál, ktorým sú grafické údaje RGB. Navyše žiadny z prijatých krokov nebol nadbytočný, každá zmena v údajoch bola zameraná na efektívnejšiu kompresiu finálnej verzie.

Zmena farebného modelu umožnila stenčovanie informácií o kanáli a ich energickejšie kvantovanie.

DCT umožnilo izolovať vysokofrekvenčnú priestorovú zložku. Vysokofrekvenčná zložka je zvyčajne malá, výsledkom čoho je neúmerne veľký výstup DCT, ktorý uľahčuje proces kompresie.

Počas procesu kvantovania sa väčšina vysokofrekvenčnej zložky vynuluje a zvyšok nadobudne konkrétne hodnoty. Zníženie počtu odlišných hodnôt tiež uľahčuje proces kompresie údajov.

Štandard JPEG poskytuje dve rôzne metódy bezstratovej kompresie, ktoré možno použiť v poslednom kroku. Huffmanova kompresia (Huffmanova kompresia je dlhotrvajúci nepatentovaný, ľahko programovateľný algoritmus. Naproti tomu novší aritmetický kódovací algoritmus je predmetom mnohých patentov. (Nie je teda žiadnym prekvapením, že mnohé programy na kompresiu JPEG podporujú iba Huffmanovu kompresiu.)

Pri dekódovaní obrázkov JPEG postupujte podľa týchto krokov v opačnom poradí. Dátový tok je najprv dekomprimovaný, potom je každý blok 8-8 podrobený inverznej DCT a nakoniec je obraz konvertovaný na zodpovedajúci farebný model (zvyčajne RGB). Všimnite si, že informácie, ktoré boli zámerne vyradené decimáciou a kvantizáciou, sa nikdy neobnovia. Ak však bolo všetko urobené správne, strata informácií nespôsobí žiadne viditeľné znehodnotenie obrazu.

JPEG je jedným z najnovších a najvýkonnejších algoritmov. V praxi je to de facto štandard pre plnofarebné obrázky. Algoritmus pracuje s oblasťami 8x8, kde sa jas a farba menia pomerne hladko. Výsledkom je, že keď sa matica takejto oblasti rozšíri v dvojitom rade v kosínoch (vzorce nižšie), významné sú iba prvé koeficienty. Kompresia v JPFG sa teda uskutočňuje na úkor plynulých zmien farieb v obraze.

Algoritmus bol vyvinutý skupinou fotografických expertov špeciálne pre kompresiu 24-bitových JPEG obrázkov – Joint Photographic Expert Group – divízia v rámci ISO – Medzinárodnej organizácie pre normalizáciu. Vo všeobecnosti je algoritmus založený na diskrétnej kosínusovej transformácii (ďalej len DCT), aplikovanej na maticu obrazu, aby sa získala nejaká nová matica koeficientov. Na získanie pôvodného obrázka sa použije inverzná transformácia

DCT rozkladá obraz na amplitúdy niektorých frekvencií, čím pri transformácii dostaneme maticu, v ktorej je veľa koeficientov buď blízkych alebo rovných nule. Okrem toho je ľudský systém vnímania farieb slabý v rozpoznávaní určitých frekvencií. Preto je možné niektoré koeficienty aproximovať na hrubšie bez výraznej straty kvality obrazu.

Operácia algoritmu.

Poďme komprimovať 24-bitový obrázok.

Krok I.

V ňom je Y zložka jasu a Cg, Cb sú zložky zodpovedné za farbu (chromatická červená a chromatická modrá). Vzhľadom na skutočnosť, že ľudské oko je menej citlivé na farbu ako na jas, je možné archivovať polia pre zložky Cg a Cb s vysokými stratami, a teda vysokými kompresnými pomermi. Táto transformácia sa v televízii používa už dlho. Signálom zodpovedným za farbu je pridelené užšie frekvenčné pásmo.

Zjednodušený preklad z farebného priestoru RGB do farebného priestoru YCrCb možno znázorniť takto:

Inverzná transformácia sa vykonáva vynásobením vektora YUV inverznou maticou:

Krok 2.

Rozdeľte pôvodný obrázok na matice 8x8. Z každej vytvoríme tri pracovné matice DCT - 8 bitov samostatne pre každý komponent. Pri vyšších kompresných pomeroch môže byť tento krok trochu náročnejší. Obrázok je rozdelený zložkou Y - ako v prvom prípade a pre zložky Cr a Cb sa matice typujú cez čiaru a cez stĺpec. Tie. z pôvodnej matice 16x16 sa získa iba jedna pracovná matica DCT. Navyše, ako je dobre vidieť, prídeme o 3/4 užitočných informácií o farebných zložkách obrázka a okamžite dostaneme dvojnásobnú kompresiu. Môžeme to urobiť prácou v priestore YCrCb. Ako ukázala prax, výsledný RGB obraz to výrazne neovplyvňuje.

Krok 3

V zjednodušenej forme možno túto transformáciu znázorniť takto:

Krok 4

Vykonávame kvantovanie. V princípe ide o jednoduché delenie pracovnej matice kvantizačnou maticou prvok po prvku. Pre každú zložku (Y, U a V) je vo všeobecnom prípade určená jej vlastná kvantizačná matica (ďalej MK).

V tomto kroku sa riadi kompresný pomer a dochádza k najväčšej strate. Je jasné, že zadaním MK s veľkými koeficientmi získame viac núl a teda väčší kompresný pomer.

Kvantovanie je tiež spojené so špecifickými účinkami algoritmu. Pri veľkých hodnotách koeficientu gama , - strata v nízkych frekvenciách môže byť taká veľká, že sa obraz rozdelí na štvorce 8x8. Straty vo vysokých frekvenciách sa môžu prejaviť takzvaným „Gibbsovým efektom“, kedy sa okolo obrysov vytvorí akési „halo“ s ostrým farebným prechodom.

Krok 5.

Maticu 8x8 preložíme na 64-prvkový vektor pomocou cik-cak skenu, t.j. vyberte prvky s indexmi (0,0). (0,1). (1,0). (2.0) ...

Na začiatku vektora teda dostaneme maticové koeficienty zodpovedajúce nízkym frekvenciám a na konci vysoké frekvencie.

Krok 6.

Takže vektor bude zložený do párov (0, 42) (0, 3) (3, -2) (4, 1)

Krok 7.

Zbalíme naučené páry pomocou Huffmanovho kódovania s pevnou tabuľkou.

Proces obnovy obrazu v tomto algoritme je úplne symetrický. Metóda vám umožňuje komprimovať niektoré obrázky 10-15 krát bez vážnej straty.

Operačný kanál používaný v algoritme JPEG.

Významné pozitívne aspekty algoritmu sú:

1) Kompresný pomer je nastavený
2) Výstupný farebný obrázok môže mať 24 bitov na bod.

Nevýhody algoritmu sú tieto:

1) Keď sa kompresný pomer zvýši, obrázok sa rozdelí na samostatné štvorce (8x8). Je to spôsobené tým, že počas kvantovania dochádza pri nízkych frekvenciách k veľkým stratám a nie je možné obnoviť pôvodné dáta.
2) Objaví sa Gibbsov efekt – haló pozdĺž hraníc ostrých farebných prechodov.

JPEG bol štandardizovaný relatívne nedávno - v roku 1991. Ale aj vtedy existovali algoritmy, ktoré komprimovali silnejšie s menšou stratou kvality. Faktom je, že akcie vývojárov štandardu boli obmedzené silou technológie, ktorá v tom čase existovala. To znamená, že aj na osobnom počítači musel algoritmus pracovať menej ako minútu na priemernom obrázku a jeho hardvérová implementácia musela byť relatívne jednoduchá a lacná. Algoritmus musel byť symetrický (čas dekompresie je približne rovnaký ako čas archivácie).

Posledná požiadavka umožnila vznik digitálnych fotoaparátov - zariadení veľkosti malej videokamery, ktoré zachytávajú 24-bitové fotografie na 10-20 MB flash kartu s rozhraním PCMCIA. Potom sa karta vloží do slotu na notebooku a príslušný program vám umožní čítať obrázky. Ak by bol algoritmus asymetrický, bolo by nepríjemné dlho čakať, kým sa zariadenie „dobije“ – skomprimuje obraz.

Nie veľmi príjemnou vlastnosťou JPEG je aj fakt, že často sú horizontálne a vertikálne pruhy na displeji úplne neviditeľné a môžu sa objaviť až pri tlači vo forme moaré. Vyskytuje sa vtedy, keď sa na vodorovné a zvislé pruhy obrázka prekryje šikmá tlačová mriežka. Kvôli týmto prekvapeniam sa JPEG neodporúča aktívne používať pri tlači, pretože má vysoké koeficienty. Pri archivácii a záberoch určených na prezeranie človekom je však v súčasnosti nenahraditeľný.

Je potrebné povedať niekoľko slov o modifikáciách tohto algoritmu. Hoci JPEG je štandard ISO, jeho formát súboru nebol opravený. Výrobcovia využívajú túto výhodu a používajú svoje vlastné nekompatibilné formáty, a preto môžu zmeniť algoritmus. Takže interné tabuľky algoritmu odporúčané ISO. sú nimi nahradené vlastnými Kronami, navyše je mierny zmätok pri nastavovaní miery strát. Napríklad pri testovaní sa ukázalo, že „výborná“ kvalita, „100 %“ a „10 bodov“ poskytujú výrazne odlišné obrázky. Navyše, mimochodom, "100%" kvalita neznamená bezstratovú kompresiu. Existujú aj možnosti JPEG pre konkrétne aplikácie.

Charakteristika algoritmu JPFG:

Kompresné pomery: 2-200 (definované používateľom).

Trieda obrázka: Plnofarebné 24-bitové obrázky alebo obrázky v odtieňoch šedej bez náhlych farebných prechodov (fotografie).

symetria: 1.

Špeciálne funkcie: V niektorých prípadoch algoritmus vytvára „halo“ okolo orezaných horizontálnych a vertikálnych okrajov v obraze (Gibbsov efekt). Navyše, keď je kompresný pomer vysoký, obraz sa rozdelí na bloky 8x8 pixelov.

JPEG je jedným z nových a dostatočne výkonných algoritmov. V praxi je to de facto štandard pre plnofarebné obrázky. Algoritmus pracuje s oblasťami 8x8, kde sa jas a farba menia pomerne hladko. Výsledkom je, že pri rozklade takejto matice sa plocha v dvojitom riadku v kosínusoch (pozri vzorce nižšie) považuje za významnú iba prvými koeficientmi. Kompresia v JPEG sa teda uskutočňuje kvôli plynulosti farebných zmien v obrázok.

Algoritmus vyvinutý skupinou fotografických expertov špeciálne na kompresiu 24-bitových obrázkov. JPEG – Joint Photographic Expert Group je divízia v rámci ISO – Medzinárodnej organizácie pre normalizáciu. Názov algoritmu znie ["jei" peg]. Vo všeobecnosti je algoritmus založený na diskrétnej kosínusovej transformácii (ďalej len DCT), ktorá sa aplikuje na maticu obrazu, aby sa získala nejaká nová matica koeficientov. Na získanie pôvodného obrázka sa použije inverzná transformácia.

DCT rozkladá obraz na amplitúdy určitých frekvencií. Pri transformácii teda dostaneme maticu, v ktorej je veľa koeficientov buď blízkych alebo rovných nule. Navyše v dôsledku nedokonalosti ľudského videnia je možné koeficienty aproximovať hrubšie bez výraznej straty kvality obrazu.

Na tento účel sa používa kvantovanie. V najjednoduchšom prípade ide o aritmetický bitový posun doprava. Touto transformáciou sa niektoré informácie stratia, ale dá sa dosiahnuť veľký kompresný pomer.

Ako funguje algoritmus

Pozrime sa teda na algoritmus podrobnejšie (obr. 2.1). Povedzme, že komprimujeme 24-bitový obrázok.

Krok 1. Obrázok z farebného priestoru RGB so zložkami zodpovednými za červenú (červenú), zelenú (zelenú) a modrú (modrú) zložku farby bodu preložíme do farebného priestoru YCrCb (niekedy nazývaného YUV).

V ňom je Y zložka jasu a Cr, Co sú zložky zodpovedné za farbu (chromatická červená a chromatická modrá). Vzhľadom na to, že ľudské oko je menej citlivé na farbu ako na jas, je možné archivovať polia pre Cr a Co komponenty s veľkými stratami a tým aj s veľkými kompresnými pomermi.Takáto transformácia sa už dlho používa v televízii. Signálom zodpovedným za farbu je pridelené užšie frekvenčné pásmo. Zjednodušený preklad z farebného priestoru RGB do farebného priestoru YCrCb možno znázorniť pomocou prechodovej matice:

Krok 2. Rozdeľte pôvodný obrázok na matice 8x8. Z každej vytvoríme 3 pracovné matice DCT - 8 bitov samostatne pre každý komponent. Pri vyšších kompresných pomeroch môže byť tento krok trochu náročnejší. Obrázok je rozdelený zložkou Y ako v prvom prípade a pre zložky Cr a Cb sa matice typujú cez čiaru a cez stĺpec. To znamená, že z pôvodnej matice 16x16 sa získa iba jedna pracovná matica DCT. Zároveň, ako je dobre vidieť, prídeme o 3/4 užitočných informácií o farebných zložkách obrazu a hneď dostaneme 2-násobnú kompresiu. Môžeme to urobiť prácou v priestore YCrCb. Ako ukázala prax, na výsledný RGB obraz to má malý vplyv.

Krok 3 V zjednodušenej forme možno DCT pre n = 8 znázorniť takto:

nu, v] = ^ Hc (i, u) xC (j, v) y

r Y)

Yq= Celé číslo

V tomto kroku sa riadi kompresný pomer a dochádza k najväčšej strate. Je jasné, že zadaním MK s veľkými koeficientmi získame viac núl a teda väčší kompresný pomer.

Kvantovanie je tiež spojené so špecifickými účinkami algoritmu. Pri vysokých hodnotách gama môže byť strata na nízkych frekvenciách taká veľká, že sa obraz rozdelí na štvorce 8x8. Straty vo vysokých frekvenciách sa môžu prejaviť tzv Gibbsov efekt, keď sa okolo kontúr s ostrým farebným prechodom vytvorí akési „haló“.

Krok 5. Maticu 8x8 preložíme na 64-prvkový vektor pomocou "cik-cak" -scanningu, to znamená, že vezmeme prvky s indexmi (0,0), (0,1), (1,0), ( 2,0)...

Na začiatku vektora teda dostaneme maticové koeficienty zodpovedajúce nízkym frekvenciám a na konci vysoké frekvencie.

Krok 6. Konvolúcia vektora pomocou algoritmu skupinového kódovania. V tomto prípade získame dvojice typu<пропустить, число>kde "skip" je počet núl, ktoré sa majú preskočiť, a "number" je hodnota, ktorá sa má vložiť do ďalšej bunky. Takže vektor 42 3000-2 00001 ... bude zložený do párov (0,42) (0,3) (3, -2) (4,1) ....

Krok 7. Konvoluujte výsledné dvojice pomocou Huffmanovho kódovania s pevnou tabuľkou.

Proces obnovy obrazu v tomto algoritme je úplne symetrický. Metóda vám umožňuje komprimovať niektoré obrázky 10-15 krát bez vážnej straty.

Významné pozitívne aspekty algoritmu sú:

■ je nastavený stupeň kompresie;

■ výstupný farebný obrázok môže mať 24 bitov na bod.

Nevýhody algoritmu sú tieto:

■ Zvýšením kompresného pomeru sa obrázok rozdelí na samostatné štvorce (8x8). Je to spôsobené tým, že počas kvantovania dochádza pri nízkych frekvenciách k veľkým stratám a nie je možné obnoviť pôvodné dáta.

■ Objaví sa Gibbsov efekt – haló pozdĺž okrajov ostrých farebných prechodov.

Ako už bolo spomenuté, JPEG bol štandardizovaný relatívne nedávno - v roku 1991. Ale aj vtedy existovali algoritmy, ktoré komprimovali silnejšie s menšou stratou kvality. Faktom je, že akcie vývojárov štandardu boli obmedzené silou technológie, ktorá v tom čase existovala. To znamená, že aj na PC musel algoritmus pracovať menej ako minútu na priemernom obrázku a jeho hardvérová implementácia musela byť relatívne jednoduchá a lacná. Algoritmus musel byť symetrický (čas dekompresie je približne rovnaký ako čas archivácie).

Splnenie poslednej požiadavky umožnilo vznik zariadení, ako sú digitálne fotoaparáty, ktoré snímajú 24-bitové fotografie na 8-256 MB flash kartu. obrázky. Nie je to pravda. nya, ak by bol algoritmus asymetrický, bolo by nepríjemné dlho čakať, kým sa zariadenie „dobije“ – stlačí sa obraz.

Nie veľmi pekná vlastnosť JPEG je tiež potom,že často horizontálne a vertikálne pruhy na displeji sú úplne neviditeľné a môžu sa objaviť len pri tlači vo forme moaré vzoru. Vyskytuje sa vtedy, keď sa na vodorovné a zvislé pruhy obrázka prekryje šikmá tlačová mriežka. Kvôli týmto prekvapeniam nie sú JPEG odporúča aktívne použitie v tlači, nastavenie vysokých koeficientov kvantizačnej matice. Pri archivácii záberov určených na prezeranie človekom je však v súčasnosti nenahraditeľný.

Široký Použitie JPEG bolo dlho obmedzované snáď len tým, že pracuje s 24-bitovými obrázkami. Preto, aby bolo možné zobraziť obraz v prijateľnej kvalite na bežnom monitore v 256-farebnej palete, bolo potrebné použiť vhodné algoritmy, a teda aj určitý čas. V aplikáciách zameraných na náročných používateľov, ako sú hry, sú takéto oneskorenia neprijateľné. Okrem toho, ak sú obrázky, ktoré máte, napríklad konvertované v 8-bitovom formáte GIF na 24-bitový JPEG a potom späť na GIF na prezeranie, strata kvality nastane pri oboch prevodoch dvakrát. Napriek tomu je nárast veľkosti archívov často taký veľký (3-20 krát) a strata kvality je taká malá, že ukladanie obrázkov vo formáte JPEG sa ukazuje ako veľmi efektívne.

Je potrebné povedať niekoľko slov o modifikáciách tohto algoritmu. Hoci JPEG je štandard ISO, jeho formát súboru nebol opravený. Pomocou toho výrobcovia vytvárajú svoje vlastné nekompatibilné formáty, a preto môžu meniť algoritmus. Interné tabuľky algoritmu odporúčaného ISO sú nimi nahradené vlastnými. Okrem toho je trochu zmätok pri špecifikácii straty. Napríklad pri testovaní sa ukázalo, že „výborná“ kvalita, „100 %“ a „10 bodov“ poskytujú výrazne odlišné obrázky. Zároveň, mimochodom, „100 %“ kvalita neznamená bezstratovú kompresiu. Existujú aj možnosti JPEG pre konkrétne aplikácie.

Ako norma ISO sa JPEG stále viac používa pri výmene obrázkov cez počítačové siete. Algoritmus JPEG je podporovaný v Quick Time, PostScript Level 2, Tiff 6.0 a v súčasnosti zaujíma popredné miesto v multimediálnych systémoch.

Charakteristika algoritmu JPEG: o! NS. ,. Pomer kompresie: 2-200 (definované používateľom). , c,: _ ,. ... Trieda obrázka: plnofarebné 2jj bitové obrázky alebo izo- | obrázky v odtieňoch sivej bez náhlych farebných prechodov (fotografie).

symetria: 1.

Charakteristika: v niektorých prípadoch algoritmus vytvára! „halo“ okolo ostrých horizontálnych a vertikálnych okrajov v obraze (Gibbsov efekt). Navyše s vysokým kompresným pomerom iso-! Odraz je rozdelený do blokov 8x8 pixelov.

Súvisiace články

Ako sa dostať do servisnej ponuky na LG G2

Firmvér Samsung Galaxy Gio S5660

Zobrazovanie položiek podľa štítku: firmvér samsung galaxy a8

Sony Ericsson Xperia Arc Smartphone Arc užívateľská príručka

Pomer strán 1440 x 900

Rozlíšenia obrazovky monitora

Najnovšie články

2021-11-16 12:29:16
Kedy potrebujem aktualizovať firmvér

2021-11-11 12:38:28
Ako premeniť smartfón s Androidom na bezpečnostnú kameru

2021-11-11 12:38:28
Ako vyzerá čínska klávesnica (história a fotografie)

Populárne články

Hodnota avatarov v psychológii

Hodnota avatarov v psychológii

Ako zdôrazniť písmeno v MS Word

Čo to znamená, ak je avatar osoby

Ako si vytvoriť svoj vlastný Twitter moment

Voľba redaktora

2021-11-11 12:38:28

Čo môže povedať avatar na sociálnej sieti o svojom majiteľovi
Viac podrobností! 1. Farba. Farba je dôležitý detail na obrázku a často si avatara vyberáme práve pre jeho farebnú schému, ktorá je pre nás najvhodnejšia ...

2021-11-11 12:38:28

Ako si vytvoriť svoj vlastný Twitter moment
Navigácia Sociálne siete dnes zohrávajú dôležitú úlohu v živote používateľov internetu. Vďaka takýmto zdrojom majú ľudia možnosť komunikovať s ...

2021-11-06 10:20:40

Skenovací mikroskop s atómovou silou Laboratórna správa by mala obsahovať
Mikroskop atómovej sily vytvorili v roku 1982 Gerd Binnig, Calvin Quait a Christopher Gerber v USA ako modifikáciu predtým vynájdeného ...

2021-11-06 10:20:40

Výber nosných stojanov kontaktnej siete
Metodická príručka K realizácii praktického vyučovania v disciplíne „Kontaktná sieť“. 1. Výber dielov a materiálov pre kontaktné zostavy ...

2021-11-06 10:20:40

Návrh a výpočet AC trolejového vedenia
VYSVETLIVKA. Metodické pokyny sú určené pre študentov denného a externého štúdia Vysokej školy železničnej Saratov ...