Algoritem RLE: opis, funkcije, pravila in primeri

Algoritem RLE je algoritem stiskanja podatkov, ki ga podpira večina formatov rastrskih slikovnih datotek: TIFF, BMP in PCX. RLE je primeren za stiskanje vseh vrst podatkov, ne glede na njegovo informacijsko vsebino, vendar vsebina podatkov vpliva na stopnjo stiskanja. Kljub dejstvu, da večina algoritmov RLE ne more zagotoviti visokih razmerij stiskanja za bolj zapletene metode, je to orodje enostavno implementirati in opraviti hitro, kar je dobra alternativa.

Kakšna je osnova za algoritem za stiskanje RLE?

RLE deluje tako, da zmanjša fizično velikost nizov ponavljajočih znakov. Ta vrstica, imenovana run, je običajno kodirana v dveh bajtih. Prvi bajt predstavlja število simbolov v teku in se imenuje števec za vožnjo. V praksi lahko kodirani pretok vključuje od 1 do 128 in 256 znakov. Števec ponavadi vsebuje število znakov, minus ena (vrednost v območju od 0 do 127 in 255). Drugi bajt je vrednost simbola v teku, ki je v območju vrednosti od 0 do 255 in se imenuje začetna vrednost.

Brez stiskanja simbolni trdi disk s 15 znaki običajno zahteva 15 bajtov za shranjevanje:

AAAAAAAAAAAAAAA.

V isti vrstici po kodiranju z RLE je potrebnih le dva bajta: 15A.

Kodiranje 15A, ustvarjeno za označevanje znakovnega niza, se imenuje paket RLE. V tej kodi je prvi bajt, 15, števec za vožnjo in vsebuje zahtevano število ponovitev. Drugi bajt, A, je run vrednost in vsebuje dejansko ponavljajočo se vrednost v zagonu.

Vsakič, ko se spremeni simbol za začetek, se generira nov paket ali vsakič, ko število simbolov v zagonu presega največje število. Predpostavimo, da 15-vrstični niz v skladu s pogoji vsebuje 4 različne simbole:

AAAAAAbbbXXXXXt

Z uporabo kodiranja z dolžino niza lahko stisnemo v štiri dvobajtne pakete:

6A3b5X1t

Po kodiranju dolžine črte za 15-bajtni niz potrebuje samo osem podatkovnih bajtov, ki predstavljajo niz, v nasprotju s prvotnimi 15 bajti. V tem primeru je kodiranje v časovnem obdobju dalo razmerje stiskanja skoraj 2 na 1.

Značilnosti

Dolgi poteki so redki pri nekaterih vrstah podatkov. Na primer, navadno besedilo ASCII redko vsebuje dolge programe. V prejšnjem primeru je bil zadnji zagon (ki vsebuje simbol t) le en znak v dolžini. 1-mestni zagon še vedno deluje. Za začetek 2 znakov je treba zapisati začetno število in začetno vrednost. Za kodiranje teče z uporabo algoritma RLE je potrebno informacije, sestavljene iz vsaj dveh simbolov. V zvezi s tem lansiranje posameznih znakov dejansko traja več prostora. Iz istih razlogov podatki, ki so sestavljeni izključno iz dveh simbolov, ostanejo nespremenjeni po kodiranju RLE.

Sheme algoritma za stiskanje RLE se razlikujejo po preprostosti in visoki hitrosti izvajanja, vendar je njihova učinkovitost odvisna od vrste kodiranih slikovnih podatkov. Črno-bela slika, ki je večinoma bela barva, na primer knjiga, bo zelo dobro kodirana zaradi velikega števila sosednjih podatkov z enako barvo. Vendar pa tudi slika z veliko barvami, kot je fotografija, ne bo kodirana. To je posledica dejstva, da je kompleksnost slike izražena v obliki velikega števila različnih barv. Zaradi te kompleksnosti bo relativno malo poteka iste barve.

Možnosti kodiranja za dolžino

Ob zagonu je več možnosti kodiranja. Podatki o slikah so običajno kodirani v zaporednem procesu, ki obdeluje vizualno vsebino kot 1D tok, ne pa kot 2D podatkovno kartico. Pri sekvenčni obdelavi se bitna slika kodira od zgornjega levega kota in usmerjena od leve proti desni vzdolž vsake linije skeniranja v spodnji desni kot bitne slike. Toda alternativne sheme RLE se prav tako lahko zapisujejo za kodiranje podatkov vzdolž dolžine bitne slike vzdolž stebrov za stiskanje v 2D ploščice ali celo za kodiranje pikslov diagonalno na cikcak način. Različice neželenih RLE se lahko uporabljajo v zelo specializiranih aplikacijah, vendar so ponavadi redke.

Algoritem kodiranja z napako v dolžini izvajanja

Druga redka možnost je algoritem kodiranja RLE z napako v dolžini izvajanja. Ta orodja običajno izvajajo kompresijo brez izgube, vendar pa pri padanju podatkov med procesom kodiranja običajno z ničliranjem enega ali dveh najmanj pomembnih bitov v vsakem pikslu lahko poveča razmerja stiskanja, ne da bi to vplivalo na kakovost zapletenih slik. Ta program RLE algoritma dobro deluje le s slikami v realnem svetu, ki vsebujejo veliko subtilnih sprememb vrednosti pikslov.

Cross-kodiranje

Cross-kodiranje je kombinacija linij skeniranja, ki se pojavijo, ko proces stiskanja izgubi razliko med izvornimi črtami. Če so podatki posameznih vrstic združeni z algoritmom kodiranja ponavljanja RLE, se točka, pri kateri je ena linija skeniranja zaustavljena in druga je izgubljena, je ranljiva in težko zazna.

Včasih gre za navzkrižno kodiranje, ki otežuje proces dekodiranja in dodaja stroške časa. Za oblike zapisa z rastrskimi slikovnimi datotekami želi ta metoda organizirati bitno sliko vzdolž optičnih črt. Čeprav številne specifikacije datotečnega formata izrecno kažejo, da morajo biti podatkovne črte individu- allno kodirane, mnoge aplikacije kodirajo te slike kot neprekinjen tok, pri čemer ignorirajo meje vrstic.

Kako kodirati sliko z algoritmom RLE?

Kodiranje posameznih skenirnih linij ima prednosti v primerih, ko mora aplikacija uporabiti le nekaj slik. Recimo, da ima fotografija 512 vrstic za optično branje in prikazati je treba samo linije od 100 do 110. Če ne bi vedeli, kje se vrstice za skeniranje začnejo in končajo s kodiranimi slikovnimi podatki, bi morala naša aplikacija dekodirati vrstice od 1 do 100, preden najde deset vrstic , ki so potrebni. Če so bili prehodi med skenirnimi črtami označeni z nekaj prepoznavljivim označevalnim markerjem, je aplikacija lahko preprosto prebrala kodirane podatke in štela markerje, dokler ne doseže potrebnih črt. Toda ta pristop bi bil precej neučinkovit.

Alternativa

Druga možnost za določitev izhodiščne točke katere koli posamezne linije skeniranja v kodiranem podatkovnem bloku je izdelava tabele pometanja. Ta struktura tabele ponavadi vsebuje en element za vsako linijo skeniranja na sliki in vsak element vsebuje odmaknjeno vrednost ustrezne linije skeniranja. Če želite najti prvi RLE paket skenirane linije 10, morate vse, kar morate storiti dekoderju, najti vrednosti položaja offset, shranjene v deseti točki tabele iskalnih nizov. Tabela pometanj lahko vsebuje tudi število bajtov, uporabljenih za kodiranje vsake vrstice. Z uporabo te metode za iskanje prvega RLE paketa skenirane linije 10 bo vaš dekoder združil vrednosti prvih 9 elementov tabele vrstic skeniranja. Prvi paket za skenirno vrstico 10 se bo začel s tem byte offsetom od začetka RLE kodiranih slikovnih podatkov.

Merske enote

Deli algoritmov za kodiranje dolżin, ki so drugaćni, so odloćitve, ki se sprejemajo na podlagi vrste podatkov, ki se dekodirajo (na primer, trajanje podatkovnega vodenja). Sheme RLE, ki se uporabljajo za stiskanje rastrske grafike, so običajno razdeljene v razrede po vrsti atomskih (t.j., najbolj osnovnih) elementov, ki jih kodirajo. Trije razredi, ki jih uporablja večina grafičnih formatov, so bitov, bajtov in RLE-jev pikslov.

Kakovost stiskanja

RLE vezja na ravni bitov kodirajo poteke več bitov v liniji skeniranja in ignorirajo meje bajtov in besed. Samo enobarvne (črno-bele), 1-bitne slike vsebujejo dovolj bitov, da bi ta razred za kodiranje RLE učinkoviti. Tipična RLE shema na ravni bitov kodira od ene do 128 bitov v enobajtnem paketu. Sedem najmanj pomembnih bitov vsebuje začetni števec minus ena in bit velikega reda vsebuje bitno vrednost 0 ali 1. Dolžina izvajanja, večja od 128 slikovnih pik, je razdeljena na več kodiranih paketov RLE.

Izjeme

Sheme RLE na ravni bajtov kodirajo teče iste vrednosti bajtov, pri čemer ignorirajo nekaj bitov in omejitve besed v vrstici skeniranja. Najpogostejša shema RLE na ravni bajtov kodiranja šifrira v 2-bajtne pakete. Prvi bajt vsebuje števec od 0 do 255, drugi pa vsebuje začetno vrednost bajtov. Prav tako je običajno dodati dvobajtno kodirno shemo z možnostjo shranjevanja dobesednih, ne-napisanih bajtov v toku kodiranega prenosa podatkov.

V takšni shemi sedem najmanj pomembnih bitov prvega bajta vsebujeta števec za vožnjo minus ena, najpomembnejši bit prvega bajt pa je indikator začetnega tipa, ki sledi bajtu števila voženj. Če je najpomembnejši bit nastavljen na 1, označuje kodiran zagon. Kodirane programe se dekodirajo z branjem vrednosti kilometrine in ponovitvijo števila krat, ki jih označuje število ciklov. Če je najpomembnejši bit nastavljen na 0, se prikaže dobesedni zagon, kar pomeni, da se štetje bajtov naslednjega bita dobesedno bere iz podatkov kodirane slike. Bajt izvajalnega bita nato vsebuje vrednost v razponu od 0 do 127 (začetek števila minus ena). Sheme RLE na ravni bajtov so dobre za podatke o sliki, ki so shranjeni kot en bajt na slikovno piko.

Sheme RLE na ravni slikovnih pik se uporabljajo, če se za shranjevanje vrednosti enega piksla uporabita dva ali več zaporednih bajtov slikovnih podatkov. Na ravni slikovnih pik se izbori ne upoštevajo, bajt pa se šteje le za določitev vrednosti vsakega piksla. Velikost kodiranih paketov je odvisna od velikosti kodiranih vrednosti slikovnih pik. Število bitov ali bajtov na slikovno piko je shranjeno v glavi slikovne datoteke. Delovanje slikovnih podatkov, shranjenih kot vrednosti 3-bajtnega piksla, se kodira v 4-bajtni paket, pri čemer en bajt šteje število operacij, ki mu sledijo trije bajti z bajti. Metoda kodiranja ostaja enaka kot pri bajtu RLE.