RLE algoritm: descriere, caracteristici, reguli și exemple

Algoritmul RLE este un algoritm de comprimare a datelor care este susținut de cele mai multe formate de fișiere de imagini raster: TIFF, BMP și PCX. RLE este potrivit pentru comprimarea oricărui tip de date, indiferent de conținutul său de informații, dar conținutul datelor afectează raportul de compresie. În ciuda faptului că majoritatea algoritmilor RLE nu pot oferi rapoarte de compresie ridicate pentru metode mai complexe, acest instrument este ușor de implementat și performat rapid, ceea ce o face o bună alternativă.

Care este baza algoritmului de compresie RLE?

RLE funcționează prin scăderea dimensiunii fizice a unui șir de caractere repetat. Această linie, numită alergare, este de obicei codată în două octeți. Primul octet reprezintă numărul de simboluri din execuție și se numește contorul de run. În practică, rularea codată poate include de la 1 la 128 și 256 de caractere. Contorul conține de obicei numărul de caractere minus unul (valoare cuprinsă între 0 și 127 și 255). Cel de-al doilea octet este valoarea simbolului din run, care este cuprins în intervalul de valori de la 0 la 255 și este denumit valoarea de start.

Fără compresie, o rulare simbolică de 15 caractere necesită de obicei 15 octeți pentru a stoca:

AAAAAAAAAAAAAAA.

În aceeași linie după codarea RLE, sunt necesare doar două octeți: 15A.

Codificarea 15A, generată pentru a denumi un șir de caractere, se numește pachet RLE. În acest cod, primul octet, 15, este contorul de alergare și conține numărul necesar de repetări. Cel de-al doilea octet, A, este valoarea de execuție și conține valoarea efectivă de repetare în execuție.

Un nou pachet este generat de fiecare dată când se schimbă simbolul de pornire sau de fiecare dată când numărul de simboluri din run este mai mare decât numărul maxim. Să presupunem că un șir de 15 caractere, conform condițiilor, conține 4 simboluri diferite:

AAAAAAbbbXXXXXt

Folosind o codare cu o lungime de șir, ea poate fi comprimată în patru pachete cu două octeți:

6A3b5X1t

După codarea lungimii liniei pentru un șir de 15 octeți, este nevoie de doar opt octeți de date pentru a reprezenta șirul, spre deosebire de cei 15 octeți originali. În acest caz, codificarea timpului de execuție a dat un raport de compresie de aproape 2 la 1.

caracteristici

Runurile lungi sunt rare în anumite tipuri de date. De exemplu, textul simplu ASCII conține rareori runde lungi. În exemplul anterior, ultima rulare (care conținea simbolul t) a avut doar un caracter în lungime. O rulare de 1 caractere încă funcționează. Atât numãrul de început cât și valoarea de început trebuie scrise pentru fiecare rulaj de 2 caractere. Pentru codarea rulajului folosind algoritmul RLE, sunt necesare informații constând din cel puțin două simboluri. În acest sens, lansarea de caractere unice necesită mai mult spațiu. Din aceleași motive, datele care se compun în întregime de două simboluri rulează, rămân neschimbate după codarea RLE.

Schemele algoritmului de compresie RLE diferă în ceea ce privește simplitatea și viteza de execuție ridicată, dar eficacitatea acestora depinde de tipul de date de imagine codificate. O imagine alb-negru, cea mai mare parte albă, de culoare, de exemplu o pagină de carte, va fi foarte bine codificată datorită numărului mare de date adiacente având aceeași culoare. Cu toate acestea, o imagine cu multe culori, cum ar fi o fotografie, nu va fi codată, de asemenea. Acest lucru se datorează faptului că complexitatea imaginii este exprimată sub forma unui număr mare de culori diferite. Și din cauza acestei complexități vor exista relativ puține runde de aceeași culoare.

Opțiuni de codare pentru lungime

Există mai multe opțiuni de codare în timpul rulării. Datele de imagine sunt, de obicei, codificate într-un proces secvențial care procesează conținutul vizual ca un flux 1D, mai degrabă decât ca o cartelă de date 2D. În procesarea secvențială, imaginea bitmap este codificată pornind de la colțul din stânga sus și direcționată de la stânga la dreapta de-a lungul fiecărei linii de scanare în colțul din dreapta jos al bitmap-ului. scheme RLE dar alternative pot fi scrise codificarea de lungime de date de-a lungul coloane bitmap pentru a comprima un 2D-țiglă sau chiar pentru codarea pixelilor zigzag pe diagonală mod. Variantele rare RLE pot fi utilizate în aplicații foarte specializate, dar sunt de obicei rare.

Algoritmul de codare cu eroare de lungime în execuție

O altă opțiune rară este algoritmul de codare RLE cu o eroare de lungime în execuție. Aceste instrumente de obicei efectua compresie fără pierderi, dar renunțarea datelor în timpul procesului de codificare, de obicei, prin nulling unuia sau a doi biți mai puțin semnificativi din fiecare pixel poate crește rapoarte de compresie fără a afecta în mod negativ calitatea imaginilor complicate. Acest program de algoritm RLE funcționează bine numai cu imagini din lumea reală care conțin multe variații subtile ale valorilor pixelilor.

Cross-codificare

Codificarea încrucișată este combinația de linii de scanare care apare atunci când procesul de compresie pierde diferența dintre liniile sursă. Dacă datele liniilor individuale sunt combinate cu algoritmul de codificare a repetiției RLE, punctul în care o linie de scanare este oprită și cealaltă este pierdută este vulnerabilă și dificil de detectat.

Uneori există o codificare încrucișată care complică procesul de decodificare, adăugând costul timpului. Pentru formatele de fișiere imagine raster, această metodă vizează organizarea unei imagini bitmap de-a lungul liniilor de scanare. Deși multe specificații privind formatul de fișier indică în mod explicit că liniile de date trebuie să fie codificate individual, multe aplicații codifică aceste imagini ca un flux continuu, ignorând limitele liniei.

Cum se codifică o imagine utilizând algoritmul RLE?

codificare individuală a liniilor de scanare are avantaje, în acele cazuri în care cererea trebuie să utilizeze numai o anumită parte a imaginii. Să presupunem că imaginea cuprinde 512 linii de scanare și linii pentru a fi afișate numai de la 100 la 110. Dacă noi nu știm unde începe liniile de scanare și finisare a datelor de imagine codificate, aplicația noastră ar trebui să decodeze liniile 1-100 înainte de a găsi zece linii , care sunt necesare. În cazul în care au fost observate tranziția între liniile de scanare într-un marker de ușor de recunoscut de diferențiere, o aplicație poate citi pur și simplu datele codificate prin numărarea jetoanele până când ajunge la liniile dorite. Dar această abordare ar fi destul de ineficientă.

O opțiune alternativă

O altă opțiune pentru determinarea punctului de pornire al oricărei linii de scanare specifice în blocul de date codificat este construirea unei tabele de maturare. Această structură de tabelă conține de obicei un element pentru fiecare linie de scanare din imagine și fiecare element conține valoarea de offset a liniei de scanare corespunzătoare. Pentru a găsi linia de scanare prima RLE-pachet de 10, tot ceea ce este necesar pentru a face decodor - este de a găsi valoarea poziției de compensare stocată în linia de scanare tabel de element de a zecea. Masa de maturare poate conține și numărul de octeți folosiți pentru a codifica fiecare linie. Folosind această metodă pentru a găsi primul pachet RLE de linie de scanare 10, decodorul dvs. va combina valorile primelor 9 elemente ale liniei de scanare. Primul pachet pentru linia de scanare 10 va începe cu această decalaj de octeți de la începutul datelor de imagine codate RLE.

Unități de măsură

Părți ale algoritmilor de codificare a lungimii care sunt diferiți sunt deciziile care se fac pe baza tipului de date care este decodificat (de exemplu, durata de rulare a datelor). Schemele RLE utilizate pentru a comprima graficele raster sunt, de obicei, împărțite în clase după tipul de elemente atomice (adică cele mai fundamentale) pe care le codifică. Cele trei clase utilizate de cele mai multe formate de fișiere grafice sunt biți, octeți și pixeli RLE.

Calitatea compresiei

Circuitele RLE cu nivel de biți codifică mai multe biți în linia de scanare și ignoră limitele octeților și cuvintelor. Numai imaginile pe un bit monocrom (alb-negru) conțin un număr suficient de biți pentru a face această clasă de codare RLE eficientă. O schemă tipică RLE la nivelul biților codifică de la unu la 128 de biți într-un pachet de un singur octet. Cele șapte biți mai puțin semnificativi cuprind un start-up un contor minus și conține cea mai mare valoare de biți a alerga bit, egal cu 0 sau 1. lungime mai mare de 128 de pixeli Run este împărțit în mai multe pachete RLE-codificate.

excepții

Schemele RLE la nivel de cod octeți rulează aceleași valori octete, ignorând unele biți și limite de cuvinte în linia de scanare. Cea mai comună schemă RLE la nivelul octetului codifică octetul se execută în pachete de 2 octeți. Primul octet conține un numărător de la 0 la 255, iar al doilea conține valoarea inițială a octetului. De asemenea, este comun să se adauge o schemă de codare de două octeți cu capacitatea de a stoca rute de octeți literale, ne-scrise, în fluxul de date codificat.

Într-o astfel de schemă, cei șapte biți cei mai puțin semnificativi ai primului octet conțin un număr de run-minus unul, iar cel mai semnificativ bit al primului octet este un indicator al tipului de pornire care urmează după octetul numărului de execuții. Dacă bitul cel mai semnificativ este setat la 1, acesta indică o rulare codată. Testele codificate sunt decodate prin citirea valorii kilometrajului și repetarea numărului de ori indicat de numărul de cicluri. Dacă bitul cel mai semnificativ este setat la 0, este afișată o execuție literală, ceea ce înseamnă că octeții de numărare din următoarea execuție sunt citiți literalmente din datele de imagine codificate. Contorul de execuție de execuție conține apoi o valoare cuprinsă între 0 și 127 (numărul de început minus unul). Schemele RLE la nivel de octet sunt bune pentru datele de imagine, care sunt stocate ca un octet per pixel.

Schemele RLE la nivelul pixelilor sunt utilizate atunci când doi sau mai mulți octeți consecutivi de date de imagine sunt utilizați pentru a stoca valorile unui pixel. La nivelul pixelilor, biții sunt ignorați, iar octeții sunt numărați numai pentru a identifica fiecare valoare a pixelilor. Dimensiunea pachetelor codate depinde de dimensiunea valorilor pixelilor codificate. Numărul de biți sau octeți per pixel este stocat în antetul fișierului imagine. Rularea datelor de imagine stocate în valori 3 octeți ale pixelilor este codificată în pachete de 4 octeți, cu operațiuni conta un singur octet, urmat de trei octeți de octet. Metoda de codare rămâne aceeași ca și cu octetul RLE.