6790847367

B. Jackowski: Grafika dyskretna 17

4a. Kompresja RLE

Najprostszy pomysł zasadza się na zauważeniu, że jeżeli dane nie są całkiem chaotyczne, to jest spora szansa, że piksel danego koloru będzie się powtarzał wiele razy pod rząd.

Wystarczy zatem powstawiać w ciąg pikseli co jakiś czas dwa rodzaje znaczników: jeden mówiący, że najbliższy piksel jest powtórzony ileś tam razy, drugi zaś informujący, że kolejne ileś tam pikseli należy traktować dosłownie.

Ten sposób kompresji nosi nazwę RLE, z angielskiego run length enco-ding), co można by tłumaczyć jako kodowanie bieżących długości.

Znaczniki to oczywiście zwykłe liczby, na ogół z takiego samego zakresu jak kolory, czyli [0,255]. Należy się jedynie umówić, że na przykład liczby z zakresu 0 < z < 127 oznaczają powtórzenie z + 1 razy piksela następującego po znaczniku, a liczby z zakresu 128 < 2 < 255 oznaczają, że kolejne 2 — 127 pikseli nie zostało zakodowanych. Umówmy się jeszcze, że pierwszym elementem ciągu wynikowego jest znacznik. To wystarcza do jednoznacznej interpretacji zakodowanego ciągu.

Załóżmy dla przykładu, że mamy cieniowaną mapę bitową i że wejściowy ciąg pikseli ma następującą postać:

0,0,0,0,255,255,255,0,63,0,127,127,127,127,127,127,127

Możemy go zakodować w następujący sposób (znaczniki dla czytelności zostały podkreślone):

3,0,2,255,130,0,63,0,6,127

Pierwszy znacznik informuje, że wartość 0 ma zostać 4 razy powtórzona (tzn. 3 + 1), drugi - że wartość 255 należy powtórzyć 3 razy, trzeci - że kolejne 3 piksele nie są kodowane, wreszcie czwarty - że wartość 127 ma być 7 razy powtórzona. W ten sposób długość ciągu została zredukowana o 7 bajtów. Jeśli piksele się powtarzają długimi fragmentami, to można osiągnąć prawie 64-krotną redukcję, gdyż w najlepszym razie zamiast 128 bajtów wstawiamy 2 - znacznik oraz wartość.

Współczynnik redukcji można by poprawić, gdyby znaczniki przechowywane były w dwóch bajtach. Wówczas maksymalna wartość znacznika