RLE algoritam: opis, značajke, pravila i primjeri

RLE algoritam je algoritam kompresije podataka koji podržava većina formata datoteka rasterske slike: TIFF, BMP i PCX. RLE je pogodan za komprimiranje bilo koje vrste podataka bez obzira na njegov sadržaj, ali sadržaj podataka utječe na omjer kompresije. Unatoč činjenici da većina RLE algoritama ne može pružiti visoke stope kompresije za složenije metode, ovaj alat je jednostavan za implementaciju i brzo izvršavanje, što ga čini dobrom alternativom.

Na čemu se temelji algoritam kompresije RLE?

RLE djeluje tako da smanjuje fizičku veličinu niza znakova koji se ponavljaju. Ova linija, nazvana izvođenje, obično je kodirana u dva bajta. Prvi bajt predstavlja broj znakova u tijeku i naziva se brojač trčanja. U praksi, kodiranje može uključivati ​​1 do 128 i 256 znakova. Brojač obično sadrži broj znakova minus jedan (vrijednosti u rasponu vrijednosti od 0 do 127 i 255). Drugi bajt je vrijednost simbola u tijeku, koja se nalazi unutar raspona vrijednosti od 0 do 255 i naziva se početna vrijednost.



Bez kompresije, 15-znakovna vožnja bita obično zahtijeva 15 bajtova za pohranu: AAAAAAAAAAAAAAA. U istom retku nakon RLE-kodiranja potrebna su samo dva bajta: 15A. Kodiranje 15A generirano za označavanje niza znakova naziva se RLE paket. U ovom kodu, prvi bajt, 15 je protočni brojač i sadrži potreban broj ponavljanja. Drugi bajt, A, je vrijednost izvođenja i sadrži stvarnu ponavljajuću vrijednost u tijeku.
Novi paket generira se svaki put kada se simbol starta promijeni, ili svaki put kada broj znakova u trci premaši maksimalni broj. Pretpostavimo da niz od 15 znakova prema uvjetima sadrži 4 različita znaka:


AAAAAAbbbXXXXXt Koristeći kodiranje dužine niza, može se sažeti u četiri binarna skupa: 6A3b5X1t Nakon kodiranja duž duljine linije 15-bajtnog niza trebate samo osam bajtova podataka za predstavljanje niza, za razliku od 15 bajtova. U ovom slučaju, kodiranje tijekom trčanja dalo je omjer kompresije od gotovo 2 do 1.

Značajke

Dugačke vožnje su rijetke u nekim tipovima podataka. Na primjer, otvoreni ASCII tekst rijetko sadrži duge staze. U prethodnom primjeru, zadnja kilometraža (koja sadrži simbol t) imala je samo jedan znak. Rad s 1 znakom još uvijek radi. I za račun za pokretanje i za početne vrijednosti potrebno je zabilježiti za svaki niz od 2 znaka. RLE kodiranje zahtijeva informacije koje se sastoje od najmanje dva znaka. U vezi s tim, lansiranje pojedinačnih znakova zapravo zauzima više prostora. Iz istih razloga, podaci koji se u cijelosti sastoje od 2 znaka, ostaju nepromijenjeni nakon RLE kodiranja.
RLE algoritmi kompresije su jednostavnost i visoke performanse, ali njihova izvedba ovisi o vrsti podataka kodiranih slikom. Crno-bijela slika, koja je uglavnom bijela, kao što su stranice knjige, bit će vrlo dobro kodirana zbog velikog brojasusjedni podaci iste boje. Međutim, slike s mnogo boja, kao što je fotografija, također neće biti kodirane. To je zbog činjenice da je složenost slike izražena u obliku velikog broja različitih boja. I zbog te složenosti bit će relativno malo trka iste boje.

Opcije kodiranja dužine

Postoji nekoliko opcija kodiranja tijekom izvršavanja. Ove se slike obično kodiraju u sekvencijalnom procesu koji obrađuje vizualni sadržaj kao 1D tok, a ne kao 2D podatkovnu karticu. Kada se sekvencijalno obradi, rasterska slika se kodira, počevši od gornjeg lijevog kuta, i ide s lijeva na desno na svakoj liniji skeniranja u donjem desnom kutu rasterske slike. Ali alternativni RLE-ovi se također mogu pisati za kodiranje bitmap podataka duž stupaca za kompresiju u 2D-pločicama ili čak za kodiranje piksela dijagonalno na način sličan cik-cak. Odd varijante RLE mogu se koristiti u visoko specijaliziranim aplikacijama, ali se obično javljaju vrlo rijetko.

Algoritam kodiranja s pogreškom kilometraže

Druga rijetka opcija je algoritam RLE kodiranja s pogreškom izvođenja. Ovi alati obično obavljaju kompresiju bez gubitaka, ali odbacivanje podataka tijekom procesa kodiranja, obično resetiranjem jednog ili dva mlađa bitna bitova u svakom pikselu, može povećati omjere kompresije bez negativnog utjecaja na kvalitetu složenih slika. Ovaj RLE algoritam je dobarradi samo sa stvarnom slikom svijeta koja sadrži mnogo finih varijacija vrijednosti piksela.

Cross-Coding

Cross-Coding je kombinacija linija skeniranja koja se javlja kada proces kompresije izgubi razliku između izlaznih linija. Ako se podaci pojedinih linija kombiniraju pomoću RLE algoritma za kodiranje ponavljanja, točka gdje je jedna linija skeniranja zaustavljena, a druga izgubljena, ranjiva je i teško je odrediti.

Ponekad postoji unakrsno kodiranje, što komplicira proces dekodiranja dodavanjem troškova vremenu. Za formate datoteka rasterske slike, ova metoda ima za cilj organizirati rasterske slike duž linija skeniranja. Iako mnoge specifikacije formata datoteke jasno ukazuju na to da bi podatkovne linije trebale biti pojedinačno kodirane, mnoge aplikacije kodiraju te slike kao kontinuirane tokove, ignorirajući granice linija.

Kako kodirati sliku pomoću RLE algoritma?

Pojedinačno kodiranje linija skeniranja ima prednosti u slučajevima kada aplikacija treba koristiti samo dio slike. Pretpostavimo da fotografija sadrži 512 rasponskih linija, a prikazuju se samo linije od 100 do 110. Ako nismo znali gdje su linije skeniranja počele i završile s podacima iz kodirane slike, naša aplikacija bi morala dekodirati linije od 1 do 100 prije pronalaženja deset redaka koje su potrebne. Ako su prijelazi između linija skeniranja obilježeni nekim lako prepoznatljivim oznakom razgraničenja, aplikacija može jednostavno čitati kodirane podatke, brojeći oznake,dok ne dosegne linije koje mu trebaju. Ali ovaj pristup bi bio neučinkovit.

Alternativno

Drugi način određivanja početne točke bilo koje posebne linije skeniranja u bloku kodiranih podataka je konstruirati tablicu za centrifugiranje. Ova tablična struktura obično sadrži jedan element svake linije skeniranja na slici, a svaki element sadrži vrijednost pomaka odgovarajuće linije skeniranja. Da bi se pronašao prvi RLE-paket linije 10 za skeniranje, sve što trebate učiniti s dekodatorom je pronaći vrijednost položaja pomaka spremljenog u deseti element tablice pretraživanja retka skeniranja. Tablica linijskog raspona također može sadržavati broj bajtova koji se koriste za kodiranje svakog retka. Koristeći ovu metodu za pronalaženje prvog RLE-paketa linije 10 za skeniranje, vaš dekoder će kombinirati vrijednosti prvih 9 elemenata tablice proračunske tablice. Prvi paket za liniju 10 skeniranja započet će s tim ofset bajtom od početka slikovnih podataka s RLE kodiranjem.

Jedinice mjerenja

Dijelovi algoritama za kodiranje duljine koji su različiti su odluke koje se donose na temelju tipa podataka koji se dekodiraju (na primjer, dužina izvođenja podataka). RLE dijagrami koji se koriste za komprimiranje rasterske grafike obično su podijeljeni u klase po atomskom tipu (tj. Najosnovniji elementi koje kodiraju. Tri klase koje koristi većina grafičkih formata su bitovi, bajtovi i pikseli RLE.
Brzine bita RLE-sheme kodiraju radovenekoliko bita u liniji skeniranja i zanemaruju granice bajtova i riječi. Samo jednobojni (crno-bijeli), 1-bitne slike sadrže dovoljno bitova kako bi ova klasa RLE-kodiranja bila učinkovita. Tipična RLE bitmapa kodira jedan do 128 bita u jednobajtnom paketu. Sedam mlađih bitnih bitova sadrži brojač izvođenja minus jedan, a stariji bit sadrži vrijednost pokretanja bita jednaku 0 ili 1. Pokret više od 128 piksela podijeljen je u nekoliko RLE-kodiranih paketa.

Isključenje

RLE krugovi na bajtnoj razini kodiraju radnje istih vrijednosti bajtova, ignorirajući neke bitove i granice riječi u liniji skeniranja. Najčešća RLE shema na razini bajta kodira prikaz bajtova u 2-bajtnim paketima. Prvi bajt sadrži brojač od 0 do 255, a drugi sadrži vrijednost početka bajta. Također distribuirane dbcs sheme kodiranja aplikacija s mogućnošću pohranjivanja doslovnih, nezabilježenih bajtova u struji kodiranih podataka. U ovoj shemi, sedam mlađih bitnih bitova prvog bajta sadrži brojač izvođenja minus jedan, a najstariji bit prvog bajta je pokazatelj tipa pokretanja koji slijedi bajt izvođenja brojanja. Ako je stariji bit postavljen na 1, on označava kodirani rad. Kodirani radovi se dekodiraju čitanjem vrijednosti izvođenja i ponovljenim brojem puta, što je označeno brojem ciklusa. Ako je najstariji bit postavljen na 0, prikazuje se doslovno izvođenje, što znači da se bajtovi sljedećeg izvođenja broje doslovno iz podataka kodirane slike. Zatim bajt brojačaIzvršenje sadrži vrijednosti u rasponu od 0 do 127 (brojač izvođenja minus jedan). RLE na razini bajta su dobre za slikovne podatke pohranjene kao jedan bajt po pikselu. Pixel RLE sheme se koriste kada se za pohranu vrijednosti od jednog piksela koriste dva ili više uzastopnih bajtova podataka. Na razini piksela bitovi se ignoriraju, a bajtovi se računaju samo da bi se identificirala svaka vrijednost piksela. Veličina kodiranih paketa ovisi o veličini kodiranih vrijednosti piksela. Broj bitova ili bajtova po pikselu pohranjuje se u zaglavlju slikovne datoteke. Pokretanje slikovnih podataka pohranjenih kao 3-bajtne vrijednosti piksela kodiranih s 4-bajtnim paketom, s jednim bajtnim brojem broja operacija nakon kojeg slijede tri bajta bajtova. Metoda kodiranja ostaje ista kao kod bajta RLE.

Povezane publikacije