RLE algoritmus: popis, funkce, pravidla a příklady

Algoritmus RLE je algoritmus komprese dat, který je podporován většinou formátů rastrových obrazových souborů: TIFF, BMP a PCX. RLE je vhodný pro kompresi libovolného typu dat bez ohledu na jeho informační obsah, ale obsah dat ovlivňuje kompresní poměr. Navzdory skutečnosti, že většina algoritmů RLE nemůže poskytnout vysoké kompresní poměry pro složitější metody, je tento nástroj snadno implementovatelný a výkonný rychle, což z něj dělá dobrou alternativu.

Jaký je základ algoritmu komprese RLE?

Funkce RLE funguje zmenšením fyzické velikosti opakujícího se znakového řetězce. Tato řádek, nazvaný běh, je obvykle kódován ve dvou bajtech. První bajt představuje počet symbolů v běhu a nazývá se počítadlo běhu. V praxi může kódovaný běh obsahovat 1 až 128 a 256 znaků. Počítadlo obvykle obsahuje počet znaků mínus jeden (hodnota v rozsahu hodnot od 0 do 127 a 255). Druhý byte je hodnota symbolu v běhu, která je obsažena v rozsahu hodnot od 0 do 255 a je označována jako počáteční hodnota.

Bez komprese symbolické 15znakové běh obvykle vyžaduje 15 bajtů pro uložení:

AAAAAAAAAAAAAAA.

Ve stejném řádku po kódování RLE jsou vyžadovány pouze dva bajty: 15A.

Kódování 15A, generované pro označení řetězce znaků, se nazývá paket RLE. V tomto kódu je první bajt, 15, počítadlo běhu a obsahuje požadovaný počet opakování. Druhý byte, A, je hodnota běhu a obsahuje aktuální opakující se hodnotu v běhu.

Nový paket se generuje pokaždé, když se změní symbol startu, nebo pokaždé, když počet symbolů v běhu překročí maximální počet. Předpokládejme, že 15-ti znakový řetězec podle podmínek obsahuje 4 různé symboly:

AAAAAAbbbXXXXXt

Pomocí kódování s délkou řetězce lze jej komprimovat do čtyř dvoubajtových paketů:

6A3b5X1t

Po kódování délky řádku pro řetězec s 15 bajty trvá na reprezentaci řetězce pouze osm datových bajtů, na rozdíl od původních 15 bajtů. V tomto případě kódování při běhu poskytlo kompresní poměr téměř 2 na 1.

Vlastnosti

Dlouhé běhy jsou u některých typů dat vzácné. Například jednoduchý text ASCII zřídka obsahuje dlouhé spouštění. V předchozím příkladu byl poslední běh (obsahující symbol t) dlouhý pouze jeden znak. Jeden znakový běh stále funguje. Počáteční počet a počáteční hodnota musí být zapsány pro každý cyklus se dvěma znaky. Pro kódování běhu pomocí algoritmu RLE jsou vyžadovány informace sestávající z alespoň dvou symbolů. V této souvislosti spouštění jednotlivých znaků skutečně trvá více prostoru. Ze stejných důvodů se data, která se skládají výlučně z 2-symboly, nezmění po kódování RLE.

Schémata kompresního algoritmu RLE se liší v jednoduchosti a vysoké rychlosti provádění, ale jejich účinnost závisí na typu kódovaných obrazových dat. Černobílý obrázek, který je převážně bílý, například kniha, bude velmi dobře kódován kvůli velkému počtu sousedních dat, které mají stejnou barvu. Však obraz s mnoha barvami, například fotografii, nebude kódován také. To je způsobeno skutečností, že složitost obrazu je vyjádřena ve formě velkého množství různých barev. A vzhledem k této složitosti bude relativně málo běhů stejné barvy.

Možnosti kódování délky

Existuje několik možností pro kódování při běhu. Obrazová data jsou obvykle kódován v následném procesu, který zpracovává jak vizuálního obsahu 1D-stream, nikoli jako 2D mapových podkladů. V sériovém zpracování bitmapy zakódován, počínaje v levém horním rohu a jde zleva doprava každého skenovacího řádku v pravém dolním rohu bitmapy. RLE, ale alternativní systém může být také zapsána do kódování délkou dat po sloupcích bitmapu kompresi 2D-dlaždice nebo dokonce pro kódování pixelů diagonálně cik-cak. Liché RLE varianty mohou být použity ve specializovaných aplikacích, ale to je obvykle poměrně vzácné.

Kódovací algoritmus s chybou délky běhu

Další možností je zřídka setkal RLE kódování algoritmus s délkou chybové cesty. Tyto nástroje obvykle provádět bezeztrátovou kompresi, ale klesá dat během kódovacího procesu, obvykle nulling jednoho nebo dvou nejméně významných bitů v každém pixelu se mohou zvýšit kompresního poměru, aniž by to ovlivnilo kvalitu složitých obrazů. Tento program RLE algoritmus pracuje dobře pouze s obrazy reálného světa, které obsahují mnoho jemných variací hodnot pixelů.

Křížové kódování

Křížové kódování je kombinace řádků skenování, ke kterým dochází, když proces komprese ztrácí rozdíl mezi zdrojovými linkami. Pokud jsou data jednotlivých linií kombinována s algoritmem kódování opakování RLE, je zranitelná a obtížně rozpoznatelná skutečnost, kdy je jeden řádek skenování zastaven a druhý je ztracen.

Někdy dochází ke křížovému kódování, které komplikuje proces dekódování a zvyšuje čas. Pro formáty rastrových obrazových souborů se tato metoda zaměřuje na uspořádání bitmapového obrazu podél čáry skenování. Přestože mnoho specifikací formátu souboru výslovně naznačuje, že datové linky musí být jednotlivě kódovány, mnohé aplikace zakódují tyto obrazy jako nepřetržitý proud, ignorující hranice čáry.

Jak kódovat obrázek pomocí algoritmu RLE?

Individuální kódování řádků má výhody v těch případech, kdy musí aplikace použít pouze určitou část obrazu. Předpokládejme, že obraz obsahuje 512 skenovacích linek a linek, které mají být zobrazeny pouze v rozmezí od 100 do 110. Pokud nevíte, kde začít řádky obrazu a úprava kódovaných obrazových dat, naše aplikace bude muset dekódovat řádků 1 až 100, než najde deset řádků požadováno. Pokud byly pozorovány přechody mezi řádků obrazu v některých snadno rozpoznatelným markeru diferenciace, aplikace by se jednoduše čtení kódovaných dat počítáním žetonů, dokud se nedosáhne požadované linie. Ale tento přístup by bylo dost neefektivní.

Alternativa

Další možností pro určení počátečního bodu libovolného řádku pro skenování v kódovaném datovém bloku je vytvoření tabulky zametání. Tato struktura tabulky obvykle obsahuje jeden prvek pro každý řádek skenování v obraze a každý prvek obsahuje hodnotu posunutí příslušné řádky pro skenování. Chcete-li najít první paket RLE linky 10 pro skenování, stačí k dekodéru pouze najít hodnoty posunuté pozice uložené v desáté položce vyhledávací tabulky skenovacího řetězce. Tabulka zametání může také obsahovat počet bajtů použitých pro kódování každého řádku. Pomocí této metody můžete najít první balíček RLE linky 10 pro skenování, dekodér kombinuje hodnoty prvních 9 prvků tabulky řádků skenování. První paket pro linku 10 pro skenování začne tímto posunutím bajtů od počátku obrazových dat zakódovaných v RLE.

Jednotky měření

Části algoritmů kódování délky, které se liší, jsou rozhodnutí, která se provádějí na základě typu dat, který se dekóduje (například délka spouštění dat). Schémata RLE používaná pro kompresi rastrové grafiky jsou obvykle rozdělena do tříd podle typu atomových (tj. Nejzákladnějších) prvků, které zakódují. Tři třídy používané většinou grafických formátů souborů jsou bity, bajty a pixelové RLE.

Kvalita komprese

schémata RLE úrovni bitové kódování běhy několik bitů v čtecí linky a ignorovat hranice bytů a slov. Pouze monochromatické (černá a bílá), 1-bitové obrazy obsahují dostatečný počet bitů, aby se tato třída RLE kódující efektivní. Typický schéma RLE na úrovni bitů kóduje jeden až 128 bitů v jednom bajtu. Sedm nejméně významných bitů obsahovat čítač minus jeden startovací a obsahuje nejvyšší hodnotu bitu bitového běhu, rovnající se 0 nebo 1. délky běhu větší než 128 pixelů je rozdělen do několika RLE-kódovaných paketů.

Výjimky

Schémata RLE v úrovni kódování byte spouští stejné hodnoty bytu, přičemž ignoruje některé hranice bitů a slov v řádku prohledávání. Nejběžnější schéma RLE na úrovni bytu kóduje bajt běží do dvoubajtových paketů. První byte obsahuje čítač od 0 do 255 a druhý obsahuje počáteční hodnotu bytu. Také je běžné přidat dvoubajtovou schéma kódování se schopností ukládat doslovné běžné bajty v kódovaném datovém toku.

V takovém schématu obsahují sedm nejméně významných bitů prvního bajtu čítač běhu minus jeden a nejvýznamnější bit prvního bajtu je indikátorem typu startu, který následuje po bajtu počátku běhu. Pokud je nejvýznamnější bit nastaven na hodnotu 1, označuje kódovaný provoz. Kódované běhy jsou dekódovány čtením hodnoty počtu kilometrů a opakováním počtu udávaných počtem cyklů. Pokud je nejvýznamnější bit nastaven na hodnotu 0, zobrazí se doslovné spuštění, což znamená, že počet bajtů dalšího spuštění se přečte doslovně z kódovaných obrazových dat. Bajt paketu provedení obsahuje hodnotu v rozmezí 0 až 127 (počáteční počet mínus jeden). Schémata RLE na úrovni bajtů jsou dobré pro obrazová data, která jsou uložena jako jeden bajt na pixel.

Schémata RLE na úrovni pixelů se používají, když se pro ukládání hodnot jednoho pixelu použijí dva nebo více po sobě jdoucích bajtů obrazových dat. Na úrovni pixelů jsou bity ignorovány a bajty jsou počítány pouze pro identifikaci každé hodnoty pixelu. Velikost kódovaných paketů závisí na velikosti kódovaných hodnot pixelů. Počet bitů nebo bajtů na pixel je uložen v záhlaví obrazového souboru. Běžící obrazová data uložená v hodnotě 3 bajtů jsou zakódována do paketu o velikosti 4 bajtů, přičemž jeden počet počítá počet operací, po němž následují tři bajty s bajty. Metoda kódování zůstává stejná jako u byte RLE.