If you're seeing this message, it means we're having trouble loading external resources on our website.

Pokud používáš webový filtr, ujisti se, že domény: *.kastatic.org and *.kasandbox.org jsou vyloučeny z filtrování.

Hlavní obsah

Kurz: Informatika – Počítače a internet > Kapitola 1

Lekce 3: Komprese dat
Počítačové vědy
Informatika – Počítače a internet
Digitální informace
Komprese dat
© 2024 Khan AcademyPodmínky poskytování služebZásady ochrany osobních údajůZásady používání souborů cookie

Jednoduchá komprese obrázku

Učebna Google
Obrázky jsou všude kolem nás, od ikon aplikací až po animované GIFy a fotografie. Obrazové soubory mohou zabrat spoustu místa, takže počítače používají řadu algoritmů pro jejich kompresi.
Pro ty nejjednodušší obrázky používají počítače obvykle kompresní algoritmus s názvem kódování délkou běhu (RLE).

Bitové mapy

Než prozkoumáme kompresi obrázku, podívejme se, jak lze obrázek reprezentovat v binární soustavě bez jakékoliv komprese.
Zde je jednoduchý obrázek, 16x16 ikona srdce:
Ikona červeného srdce s bílým pozadím
Pojďme si to prohlédnout z blízka s použitím mřížky, aby bylo jasně vidět, které pixely jsou červené a které pixely jsou bílé:
Mřížka 16 x 16 pixelů s ikonou srdce. Srdce je vyrobeno z červených pixelů a pozadí tvoří bílé pixely.
Ikona srdce se skládá pouze ze dvou barev, červené a bílé, takže ji počítač může reprezentovat v binární soustavě mapováním červených pixelů na 1 a bílých pixelů na 0. Nazývá se to bitová mapa, protože dochází k mapování pixelů na bity.
Pomocí této metody bude zobrazená ikona reprezentována následovně (nuly na začátku každého řádku jsou vynechané):
0001100000110000
0011110001111000
0111111011111100
1111111111111110
1111111111111110
1111111111111110
1111111111111110
1111111111111110
0111111111111100
0011111111111000
0001111111110000
0000111111100000
0000011111000000
0000001110000000
0000000100000000
Představ si, že výše uvedené bity čteš někomu, kdo si je zapisuje. Po chvilce by bylo jednodušší říkat "pět nul" namísto "nula nula nula nula nula". Počítač to tak může taky dělat...

RLE kompresní algoritmus

Při kódování délkou běhu počítač nahradí každý řádek číslicemi, které říkají, kolik po sobě jdoucích pixelů má stejnou barvu, počínaje vždy počtem bílých pixelů.
Například první řádek obsahuje 3 bílé pixely, 2 červené pixely, 5 bílých pixelů, 2 červené pixely, a 4 bílé pixely:
1 100 000 110 000
Bylo by to reprezentováno následovně:
3,2,5,2,4
Čtvrtý řádek je zajímavý, protože začíná červeným pixelem. Kódování délky běhu začína počtem bílých pixelů, takže budou zastoupeny následovně:
0,15,1
Zkontroluj si, že tomu rozumíš
Zde je druhý řádek bitmapy pro ikonu srdce:
11 110 001 111 000
Jak by byl tento řádek reprezentován v RLE?
Vyber 1 odpověď:

RLE dekomprese

Když počítač používá kódování délkou běhu, měl by být schopen z komprimované reprezentace dokonale znovuvytvořit obrázek, a pokud budeme postupovat podle jeho instrukcí, měli bychom to být schopni udělat také.
Pojďme to zkusit. Tady je zobrazena černobílá ikona pomocí RLE:
4, 9, 3
4, 7, 2, 1, 2
4, 7, 2, 1, 2
4, 9, 3
4, 7, 5
4, 7, 5
5, 5, 6
0, 15, 1
1, 13, 2
První řádek má 4 bílé pixely, pak 9 černých pixelů, a pak 3 bílé pixely. Vypadá následovně:
Další řádek obsahuje 4 bílé pixely, pak 7 černých, 2 bílé, 1 černý a 2 bílé. Vypadá následovně:
Když budeme pokračovat, výsledným obrázkem bude šálek s podšálkem:
Zkontroluj si, že tomu rozumíš
Následující je RLE reprezentace komprimované 6x6 černobílé ikony:
2,2,2
2,2,2
0,6
0,6
2,2,2
2,2,2
Jaký matematický symbol ti tato ikona připomíná?
Vyber 1 odpověď:

Limity RLE

RLE komprese funguje nejlépe na obrázcích, které mají mnoho opakovaných běhů (delší, lepší) a na obrázcích s menším počtem barev.
A co tato 16x16 ikona?
Ikona vyrobená z náhodných barev pro každý pixel.
Pojďme se na to podívat zblízka, ať si můžeme představit každý pixel:
Mřížka o velikosti 16 x 16 pixelů. Každý pixel je náhodné barvy.
Každý pixel této ikony je jiné barvy a nejsou zde proto žádné sekvence.
Kódování délkou běhu nemůže takovýto obrázek zkomprimovat. Jedná se o příklad, který jsem vytvořil právě pro tento článek (vygenerovaný tímto programem), takže se může zdát, že se nejedná až o tak běžnou záležitost.
Jak se ale ukazuje, fotografické obrázky se podobají této ikoně — skutečný svět je plný detailů, které přerušují nepřerušované sekvence.
Stránka týmu Khan Academy obsahuje tuto nádhernou fotografii psa, který se dívá na obrazovku počítače:
Fotografie psa dívajícího se na obrazovku počítače.
Při normálním rozlišení se zdá, že existují bloky se sekvencemi stejné barvy, jako například v kožichu psa nebo šedá barva na obrazovce počítače.
Pojďme se na pixely podívat zblízka:
Pixelová mřížka přiblížená na psí čenich, který se dívá na obrazovku počítače. Pixely jsou modré a oranžové, ale zahrnují velký počet odstínů modré a oranžové.
Nyní lze vidět, že i zdánlivě jednoduchá počítačová obrazovka je tvořena obrovskou řada víceméně podobných barev. Kódování pixelů délkou běhu zde příliš velikost souboru nezmenší.

Použití pro RLE

RLE komprese byla velmi populární technikou, když byla většina počítačových obrázků ikonami s omezeným barevným rozpětím.
V současné době jsou naše obrázky složitější a neobsahují tolik sekvencí stejné barvy.
Kde se používá RLE dnes? Faxové stroje stále používají RLE pro komprimaci faxových dokumentů, protože reprezentují pouze černobílá písmena. JPEG obrázky používají RLE v závěrečné fázi komprese, ale nejprve používají složitější algoritmus ke zkomprimování fotografických detailů. Brzy to prozkoumáme víc.

Chceš se zapojit do diskuze?

Přihlášení
Zatím žádné příspěvky.
Umíš anglicky? Kliknutím zobrazíš diskuzi anglické verze Khan Academy.