Algoritmus RLE je algoritmus kompresie údajov podporovaný väčšinou formátov rastrových obrázkových súborov: TIFF, BMP a PCX. Funkcia RLE je vhodná na kompresiu akéhokoľvek typu údajov bez ohľadu na obsah, ale obsah údajov ovplyvňuje kompresný pomer. Napriek tomu, že väčšina algoritmov RLE nedokáže zabezpečiť vysokú mieru kompresie pre zložitejšie metódy, tento nástroj sa dá ľahko implementovať a vykonávať rýchlo, čo z neho robí dobrú alternatívu.

Na čo je založený algoritmus kompresie RLE?

Funkcia RLE funguje znížením fyzickej veľkosti opakujúceho sa reťazca znakov. Tento riadok, nazývaný beh, je zvyčajne zakódovaný v dvoch bajtoch. Prvý bajt predstavuje počet znakov v spustení a nazýva sa počítadlo spustenia. V praxi môže proces kódovania obsahovať 1 až 128 a 256 znakov. Počítadlo zvyčajne obsahuje počet znakov mínus jeden (hodnoty v rozsahu hodnôt od 0 do 127 a 255). Druhý byte je hodnota symbolu v priebehu, ktorá sa nachádza v rozsahu hodnôt od 0 do 255 a nazýva sa začiatočnou hodnotou.


Bez kompresie 15-bitový bežiaci beh obvykle vyžaduje 15 bajtov na uloženie: AAAAAAAAAAAAAAA. V rovnakom riadku po kódovaní RLE potrebujete len dva bajty: 15A. Kódovanie 15A generované na označenie reťazca znakov sa nazýva paket RLE. V tomto kóde prvý bajt, 15 je počítadlo chodu a obsahuje požadovaný počet opakovaní. Druhý bajt A je počiatočná hodnota a obsahuje aktuálnu opakujúcu sa hodnotu v priebehu. Nový balík sa vygeneruje pri každej zmene symbolu štartu alebo pri každom prekročení maximálneho počtu znakov. Predpokladajme, že sa 15-znakový reťazec za podmienok, obsahujúci 4 rôzne symboly:


AAAAAAbbbXXXXXt pomocou kódovania dĺžky trati, to môžu byť komprimované do štyroch dvojbajtové paketu 6A3b5X1t Po dĺžke kódujúce riadku 15 bajtov reťazec potrebujete iba osem bajtov údajov, ktoré reprezentujú reťazec, na rozdiel od výstupu 15 bajtov. V tomto prípade kódovanie počas behu poskytlo kompresný pomer takmer 2 ku 1.

Funkcie

V niektorých typoch údajov sú dlhé série zriedkavé. Napríklad otvorený text ASCII zriedka obsahuje dlhé spúšťanie. V predchádzajúcom príklade posledný najazdený kilometer (obsahujúci symbol t) mal iba jeden znak. 1-znakový chod stále funguje. Hodnoty štartovacieho účtu aj štartovacieho čísla sa musia zaznamenať pre každý beh s 2 znakmi. Kódovanie RLE vyžaduje informácie, ktoré pozostávajú z aspoň dvoch znakov. V súvislosti s tým spustenie jednotlivých znakov skutočne zaberá viac miesta. Z tých istých dôvodov zostanú údaje, ktoré pozostávajú výhradne z dvoch znakových cyklov, nezmenené po kódovaní RLE. Algoritmy kompresie RLE sú jednoduchosť a vysoký výkon, ale ich výkon závisí od typu kódovaných dát. Čiernobiely obraz, ktorý je väčšinou biele, ako sú stránky knihy, bude veľmi dobre kódovaný kvôli veľkému počtupriľahlé údaje majú rovnakú farbu. Obrázky s mnohými farbami, napríklad s fotografiou, však nebudú zakódované. Je to spôsobené tým, že zložitosť obrazu je vyjadrená vo forme veľkého množstva rôznych farieb. A kvôli tejto zložitosti bude relatívne málo behov rovnakej farby.

Možnosti kódovania dĺžky

V priebehu vykonávania je niekoľko možností kódovania. Tieto obrázky sú zvyčajne zakódované v sekvenčnom procese, ktorý spracúva vizuálny obsah ako 1D stream, nie ako 2D dátová karta. Pri sekvenčnom spracovaní je rastrový obraz zakódovaný, začínajúci od ľavého horného rohu, a ide zľava doprava na každú čiaru skenovania v pravom dolnom rohu rastrového obrázka. Ale alternatívne RLE môžu byť tiež napísané na zakódovanie bitmapových dát pozdĺž stĺpcov pre kompresiu v 2D-dlaždiciach alebo dokonca na kódovanie pixlov diagonálne cikcakovitým spôsobom. Nepárne varianty RLE môžu byť použité vo vysoko špecializovaných aplikáciách, ale zvyčajne sa vyskytujú pomerne zriedkavo.

Kódovací algoritmus s chybou najazdených kilometrov

Ďalšou zriedkavou možnosťou je algoritmus kódovania RLE s chybou pri spustení. Tieto nástroje zvyčajne vykonávajú bezstratovú kompresiu, ale zamietnutie údajov počas procesu kódovania, zvyčajne resetovaním jedného alebo dvoch mladších významných bitov v každom pixeli, môže zvýšiť pomery kompresie bez negatívne ovplyvnenia kvality zložitých obrazov. Tento program algoritmu RLE je dobrýpracuje len so skutočným svetovým obrázkom, ktorý obsahuje mnoho jemných variácií hodnôt pixelov.

Cross-kódujúci

Cross-Coding - združenie riadkov, ku ktorému dochádza, keď je kompresný stratí rozdiel medzi výstupnými riadkami. Ak sa dáta jednotlivých liniek v kombinácii opakovaní kódovacieho algoritmu RLE, bod, kde sa zastaví skenovanie línie, a druhá - stratené, je zraniteľný a ťažké definovať.
Niekedy dochádza k krížovému kódovaniu, čo komplikuje proces dekódovania pridaním nákladov na čas. Pre formáty rastrových obrázkových súborov sa táto metóda zameriava na usporiadanie rastrových obrázkov pozdĺž línií skenovania. Hoci mnoho špecifikácia formátu súboru jasne ukazuje, že tieto linky by mali byť individuálne kódovaný, mnoho aplikácií kódujú tieto obrazy ako nepretržitý prúd, ignorovanie čiar ohraničujúcich.

Ako kódovať obrázok pomocou algoritmu RLE?

Jednotlivé kódovanie skenovaných riadkov má výhody v prípadoch, keď by aplikácia mala používať len časť obrazu. Predpokladáme, že obraz obsahuje 512 rozkladovej riadky a mal by zobraziť iba riadky 100 až 110. Ak nevieme, kde začala rozkladovej riadok a skončil kódované obrazové dáta, naše aplikácie dekóduje riadkov 1 až 100, než nájde desať riadkov, ktoré sú potrebné. Ak boli zaznamenané prechody medzi riadkov obrazu v niektorých ľahko rozoznateľné marker rozdielu, aplikácie by potom čítať zakódované dáta, počítanie markerykým nedosiahne linky, ktoré potrebuje. Tento prístup by však bol dosť neúčinný.

Alternatívne

Ďalšou možnosťou pre stanovenie počiatočného bodu akéhokoľvek najmä riadku obrazu kódovaného dátového bloku je vytvoriť tabuľku rozkladovej riadky. Táto štruktúra tabuľky typicky zahŕňa jeden člen každý riadok snímanie obrazu, a každý prvok obsahuje odstupov zodpovedajúcich čítacie linku. Nájsť prvý RLE-10 balíček čítacie linky všetko, čo potrebujete, aby sa dekodér - je nájdená hodnota polohy posunu, ktorý je uložený v desiatom riadku položky vyhľadávacie tabuľka scan. Tabuľka riadku rozpätia môže tiež obsahovať počet bajtov použitých na zakódovanie každého riadku. Pri použití tejto metódy nájsť prvej RLE riadku balík prehľadá váš dekodér 10 bude kombinovať hodnotu prvých 9-line prvkami prehľadanie tabuľky. Prvý paket pre čiaru na skenovanie 10 začne týmto posunutým bajtom od začiatku obrazových dát s kódovaním RLE.

jednotky

Časti kódovacích algoritmov, ktoré sa líšia dĺžkou - rozhodnutie vykonané na základe typu dát, ktorá sa dekóduje (napr dĺžky behu dáta). Schémy RLE, ktorý sa používa na kompresiu bitmapovej grafiky sú zvyčajne rozdelené do tried podľa typu atómových (tj najzákladnejších prvkov, ktoré kódujú tri triedy sú používané väčšinou formátov súborov. - je bitov, bytov a pixel RLE

Quality Compression.

Bitové rýchlosti kódovania schém RLEniekoľko bitov v riadku skenovania a ignoruje okraj bajtov a slov. Iba monochromatické (čierne a biele), 1-bitové obrázky obsahujú dostatočné množstvo bitov, ktoré umožňujú efektívne kódovanie tejto triedy RLE. Typický rastrový RLE kóduje jeden až 128 bitov v jednom bajtovom pakte. Sedem mladších významných bitov obsahuje počítadlo spustenia mínus jedno a starší bit obsahuje bitovú hodnotu rovnajúcu sa 0 alebo 1. Prekročenie viac ako 128 pixelov je rozdelené na niekoľko paketov kódovaných RLE.

Vylúčenie

Cirkulácie na úrovni bajtu RLE zakódujú behy s rovnakými hodnotami bajtov, ignorujúc niektoré bity a hranice slov v riadku skenovania. Najbežnejšia schéma RLE na úrovni bajtov zakóduje chod bajtov v 2-bajtových paketoch. Prvý bajt obsahuje počítadlo od 0 do 255 a druhý obsahuje hodnotu začiatku bajtu. Tiež distribuované schémy kódovania aplikácií dbcs so schopnosťou ukladať doslova nerekordované bajty beží v toku kódovaných dát. V tejto schéme sedem mladších významných bitov prvého bajtu obsahuje počítadlo run-down minus jeden a najstarší bit prvého bajtu je indikátorom typu spustenia, ktorý nasleduje po byte run-time. Ak je starší bit nastavený na hodnotu 1, označuje kódovaný beh. Kódované série sa dekódujú čítaním hodnoty priebehu a opakovaním jej počtu, čo je počet cyklov. Ak je najstarší bit nastavený na hodnotu 0, zobrazí sa doslovné zobrazenie, čo znamená, že bajty nasledujúceho počítania sa počítajú doslovne z údajov kódovaného obrázka. Potom bajt počítadlaspúšťanie obsahuje hodnoty v rozmedzí od 0 do 127 (bežiaci počítadlo mínus jeden). RLE na úrovni bajtov sú dobré pre obrazové dáta uložené ako jeden bajt na pixel. Schémy pixelov RLE sa používajú, keď sa na ukladanie hodnôt jedného pixelu použijú dva alebo viac po sebe nasledujúcich bajtov. Na úrovni pixelov sa bity ignorujú a bajty sa počítajú len na identifikáciu každej hodnoty pixelov. Veľkosť kódovaných paketov závisí od veľkosti kódovaných hodnôt pixelov. Počet bitov alebo bajtov na pixel je uložený v hlavičke súboru obrázka. Spúšťanie obrazových dát uložených v hodnotách trojbajtových pixelov kódovaných 4-bajtovým paketom s jedným bajtom počítajúcim počet operácií, za ktorými nasledujú tri bajty bajtov. Metóda kódovania zostáva rovnaká ako v prípade bajtu RLE.