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

RLE algoritam je algoritam kompresije podataka koji podržava većina rasternih slikovnih formata datoteka: TIFF, BMP i PCX. RLE je pogodan za komprimiranje bilo koje vrste podataka bez obzira na njezin sadržaj informacija, ali sadržaj podataka utječe na omjer kompresije. Unatoč činjenici da većina RLE algoritama ne može osigurati visoke omjere kompresije za složenije metode, ovaj alat je jednostavan za implementaciju i brzo izvedbu, što ga čini dobru alternativu.

Koja je osnova za algoritam kompresije RLE?

RLE djeluje tako što smanjuje fizičku veličinu ponavljajućeg znakovnog niza. Ova linija, nazvana trčanje, obično je kodirana u dva bajta. Prvi bajt predstavlja broj simbola u bijegu i zove se brojač brojača. U praksi, kodirani prikaz može sadržavati od 1 do 128 i 256 znakova. Brojač obično sadrži broj znakova minus jedan (vrijednost u rasponu od 0 do 127 i 255). Drugi bajt je vrijednost simbola u trku koja je sadržana u rasponu vrijednosti od 0 do 255 i naziva se početna vrijednost.

Bez kompresije, simbolični trčanje od 15 znakova obično zahtijeva 15 bajtova za pohranu:

AAAAAAAAAAAAAAA.

U istoj liniji nakon RLE kodiranja potrebno je samo dvije bajta: 15A.

Kodiranje 15A, stvoreno da označi niz znakova, zove se RLE paket. U ovom kodu, prvi bajt, 15, je pokretni brojač i sadrži potrebni broj ponavljanja. Drugi byte, A, je vrijednost za pokretanje i sadrži stvarni ponavljajuću vrijednost u vožnji.

Svaki put kada se početni simbol promijeni, svaki put generiranje novog paketa, ili svaki put kada broj simbola u trajanju premaši maksimalni broj. Pretpostavimo da niz od 15 znakova, prema uvjetima, sadrži 4 različita simbola:

AAAAAAbbbXXXXXt

Koristeći kodiranje s duljinom niza, može se komprimirati u četiri paketa s dva bajta:

6A3b5X1t

Nakon kodiranja duljine linije za niz od 15 bajta, potrebno je samo osam podatkovnih bajtova da predstavljaju niz, za razliku od izvornih 15 bajta. U ovom slučaju, kodno vrijeme kodiranja daje omjer kompresije od gotovo 2 do 1.

Značajke

Dulje staze su rijetke u nekim vrstama podataka. Na primjer, običan ASCII tekst rijetko sadrži dugu vožnju. U prethodnom primjeru posljednja trčanje (koja sadrži simbol t) bila je samo jedan znak u dužini. Rukom od 1 znaka i dalje radi. I početni broj i startna vrijednost moraju biti napisani za svaku vožnju od 2 znaka. Za kodiranje trase korištenjem RLE algoritma potrebni su podaci koji se sastoje od najmanje dva simbola. S tim u vezi pokretanje pojedinačnih znakova zaista traži više prostora. Iz istih razloga, podaci koji se sastoje isključivo od dva simbola, ostaju nepromijenjeni nakon RLE kodiranja.

Sheme algoritma za kompresiju RLE razlikuju se po jednostavnosti i brzoj izvedbi, ali njihova učinkovitost ovisi o vrsti kodiranih podataka. Crno-bijela slika koja je uglavnom bijeloj boji, na primjer stranica knjige, bit će dobro kodirana zbog velikog broja susjednih podataka iste boje. Međutim, slika s mnogo boja, poput fotografije, neće se također kodirati. To je zbog činjenice da se složenost slike izražava u obliku velikog broja različitih boja. I zbog ove složenosti bit će relativno malo staza iste boje.

Opcije kodiranja za duljinu

Postoji nekoliko mogućnosti kodiranja tijekom izvođenja. Slikovni se podaci obično kodiraju u slijednom postupku koji obrađuje vizualni sadržaj kao 1D tok, a ne kao 2D podatkovnu karticu. U sekvencijalnoj obradi, bitmapna slika je kodirana počevši od gornjeg lijevog kuta i usmjerena s lijeva na desno duž linije skeniranja u donjem desnom kutu bitmapa. RLE, ali alternativne sheme također može biti napisan na duljinu podataka kodiranje uz stupcima bitmapa za sažimanje 2D-pločica ili čak za kodiranje piksela dijagonalno cik-cak način. Određene varijante RLE mogu se koristiti u visoko specijaliziranim aplikacijama, ali su obično rijetke.

Algoritam kodiranja s pogreškom u trajanju

Druga rijetka mogućnost je algoritam kodiranja RLE s pogreškom u trajanju. Ovi alati obično obavljaju bez gubitaka kompresije, ali je ispuštanje podataka tijekom procesa kodiranja, obično nulling jedne ili dvije najmanje značajnih bitova u svakom pikselu može povećati omjer kompresije bez štetnog utjecaja na kvalitetu komplicirane slike. Ovaj RLE algoritamski program dobro funkcionira samo sa stvarnim slikama koje sadrže mnoge suptilne varijacije vrijednosti piksela.

Cross-kodiranje

Cross-kodiranje je kombinacija linija skeniranja koja se javlja kada proces kompresije gubi razliku između izvora. Ako su podaci pojedinačnih linija kombinirani s algoritmom kodiranja reprodukcije RLE, točka u kojoj je jedna linija skeniranja zaustavljena, a druga je izgubljena, ranjiva je i teško je otkriti.

Ponekad postoji križni kod koji komplicira proces dekodiranja i dodaje trošak vremena. Za formate slikovnih slikovnih datoteka, ova metoda ima za cilj organizirati bitmap sliku duž linija skeniranja. Iako mnoge specifikacije formata datoteka eksplicitno upućuju na to da se linije podataka moraju pojedinačno kodirati, mnoge aplikacije šifriruju te slike kao kontinuirani tok, ignorirajući granice crte.

Kako kodirati sliku koristeći RLE algoritam?

Kodiranje pojedinačnih linija za skeniranje ima prednosti u slučajevima kada aplikacija treba koristiti samo neke slike. Pretpostavimo da slika sadrži 512 skeniranje linije i linije koji će biti prikazani samo od 100 do 110 Ako ne znamo gdje linija početak i kraj kodiranih slikovnim podacima, naš program će morati dekodirati linijama od 1 do 100 prije pronalaženja deset linija , koji su potrebni. Ako su prijelazi između linija skeniranja uočeni su na neki lako prepoznatljiv biljeg diferencijacije, aplikacija može jednostavno pročitati kodiranih podataka brojanjem žetone dok se ne dostigne željene linije. Ali ovaj pristup bi bio prilično neučinkovit.

Alternativna opcija

Druga mogućnost za određivanje polazne točke bilo koje posebne linije skeniranja u kodiranom podatkovnom bloku jest izgraditi tablicu zamaha. Ova struktura tablice obično sadrži jedan element za svaku liniju skeniranja na slici, a svaki element sadrži vrijednost offset odgovarajuće linije skeniranja. Da biste pronašli prvi RLE paket linije za skeniranje 10, sve što trebate učiniti dekoderu je pronaći vrijednosti položaja pomaka koji su pohranjeni u desetoj stavci tablice za pretraživanje trake. Tablica zamaha može sadržavati i broj bajtova koji se koriste za kodiranje svakog retka. Koristeći ovu metodu za pronalaženje prvog RLE paketa linije za skeniranje 10, dekoder će kombinirati vrijednosti prvih 9 elemenata tablice linije skeniranja. Prvi paket za liniju za skeniranje 10 započinje tom bajtom pomaknutom od početka RLE kodiranih podataka.

Jedinice mjerenja

Dijelovi algoritama za duljinu kodiranja koji su različiti su odluke koje se temelje na vrsti podataka koji se dekodiraju (na primjer, duljinu pokretanja podataka). RLE sheme koje se koriste za komprimiranje rastere grafike obično su podijeljene u klase prema vrsti atomskih (tj. Najosnovnijih) elemenata koje oni kodiraju. Tri klase koje koriste većina grafičkih formata datoteka su bitova, bajtova i piksela RLE.

Kvaliteta kompresije

Bitovi RLE krugovi kodiraju nekoliko bita u liniji skeniranja i ignoriraju granice bajtova i riječi. Samo crno-bijeli (crno-bijeli), 1-bitne slike sadrže dovoljno bitova da bi ovaj RLE-kodiranje klasa djelotvoran. Tipična shema RLE na razini bitova kodira od jednog do 128 bita u paketu od jednog bajta. Sedam najmanje značajnih bitova sadrži početni brojač minus jedan, a bit visokog reda sadrži bitnu vrijednost od 0 ili 1. Duljina trajanja koja je veća od 128 piksela podijeljena je u nekoliko paketnih kodova RLE.

iznimke

RLE sheme kod bajtova kodiranja pokreću istu vrijednost bajtova, ignorirajući neke bitove i granice riječi u liniji skeniranja. Najčešća shema RLE na razini byte koja kodira bajt pokreće se u paketima od 2 bajta. Prvi bajt sadrži brojač od 0 do 255, a drugi sadrži početnu vrijednost bajta. Također je uobičajeno dodati shemu kodiranja od dva bajta s mogućnošću pohrane doslovnih, neizbrisanih bajtova u kodiranom toku podataka.

U takvoj shemi, sedam najmanje značajnih bitova prvog bajta sadrži brojač brojača manje od jednog, a najznačajniji bit prvog bajta je pokazatelj vrste startanja koji prati bajt trčanja broja. Ako je najznačajniji bit postavljen na 1, označava kodiranu vožnju. Kodirane staze se dekodiraju čitanjem vrijednosti kilometraže i ponavljajući broj puta označenih brojem ciklusa. Ako je najznačajniji bit postavljen na 0, prikazuje se doslovni prikaz, što znači da se brojčani bajtovi sljedećeg trčanja čitaju doslovno iz podataka o kodiranoj slici. Brojač byte izvršenja sadrži vrijednost u rasponu od 0 do 127 (početni broj minus jedan). RLE sheme na razini bajta su dobre za slikovne podatke koji su pohranjeni kao jedan bajt po pikselu.

RLE sheme na razini piksela se koriste kada se dva ili više uzastopnih bajtova slikovnih podataka koriste za pohranjivanje vrijednosti jednog piksela. Na razini piksela, bitovi se zanemaruju, a bajtovi se broje samo za prepoznavanje vrijednosti svakog piksela. Veličina kodiranih paketa ovisi o veličini vrijednosti kodiranih piksela. Broj bitova ili bajtova po pikselu pohranjuje se u zaglavlju slikovne datoteke. Prikazani slikovni podaci pohranjeni kao vrijednosti piksela od 3 bajta kodiraju se u paket od 4 bajta, s jednim bajtom koji broji broj operacija, nakon čega slijedi tri bajta s bajtovima. Metoda kodiranja ostaje ista kao kod byte RLE.