RLE

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Run-Length Encoding (RLE, kodowanie długości serii) – prosta metoda bezstratnej kompresji danych, której działanie polega na opisywaniu ciągów tych samych liter (bitów, bajtów, symboli, pikseli itp.) za pomocą licznika powtórzeń (długości serii), a dokładniej przez pary: licznik_powtórzeń_litery, litera.

Telefaks (potocznie faks) – współczesna nazwa usługi symilograficznej dla abonentów, polegająca na przesyłaniu wiadomości w postaci obrazów nieruchomych pomiędzy aparatami symilograficznymi, realizowana za pośrednictwem łączy telefonicznych z komutacją automatyczną. Początki rozwoju telefaksu przypadają na koniec lat 70. Istnieje kilka norm komunikacji pomiędzy telefaksami. Najczęściej jest używana norma analogowa G3 (14400 bit/s), jest też cyfrowa G4 (64000 bit/s) dla ISDN.BMP – format pliku z grafiką bitmapową. Opracowany pierwotnie dla systemu OS/2, wykorzystywany później także w interfejsach systemów z rodziny Microsoft Windows™, jednak jako wolny od patentów jest dostępny i – mimo dużych rozmiarów – popularny jako format przechowywania danych również na wszystkich pozostałych platformach. Zawiera w sobie prostą kompresję bezstratną RLE (która nie musi być użyta), informację o użytych kolorach. Obsługuje tryby RGB oraz RGBA.

Na przykład w ciągu:

wwwwwiiiikkkkkkkiiippppppeeeeeddddiia

litera w powtarza się 5 razy, co jest zapisywane jako 5w (ciąg pięciu liter w), dalej i występuje 4 razy – 4i, itd. aż ostatecznie uzyskuje się ciąg:

5w4i7k3i6p5e4d2i1a

składający się z 18 znaków, podczas gdy kodowany ciąg składał się z 37 znaków.

Dane, które charakteryzują się takim rozkładem liter to głównie obrazy bitmapowe, np. pomiędzy wierszami tekstu występują długie ciągi pikseli w kolorze tła jak w dokumentach faksowych, w których dominuje białe tło. Dlatego kompresja RLE jest stosowana m.in. w faksach, w różnych formatach zapisu obrazu, takich jak PCX, BMP, TGA, również jako jeden z filtrów w dokumentach PostScript i PDF.

Transformata Burrowsa-Wheelera to algorytm użyteczny przy bezstratnej kompresji danych. Dane po przetworzeniu tą transformacją dają się znacznie lepiej skompresować za pomocą klasycznych algorytmów kompresji. Operuje ona na blokach, przy czym jest tym efektywniejsza im bloki te są większe. Zazwyczaj używa się bloków o rozmiarach kilkuset kilobajtów.PDF (ang. Portable Document Format, przenośny format dokumentu) – format plików służący do prezentacji, przenoszenia i drukowania treści tekstowo-graficznych, stworzony i promowany przez firmę Adobe Systems. Język opisu pliku PDF jest okrojoną wersją języka programowania PostScript wzbogaconą o elementy hipertekstowe.

Kodowanie RLE jest także stosowane jako jeden z końcowych etapów kompresji, który poprzedzają transformaty mające na celu utworzenie ciągów znaków dobrze kompresowanych przez RLE; takie transformaty, to np. Burrowsa-Wheelera i MTF lub w przypadku kompresji dźwięku – jeden ze sposóbów predykcji.

Piksel (ang. pixel – wyraz utworzony ze zbitki dwóch angielskich słów: picture+element) jest to najmniejszy jednolity (przedstawiający konkretny kolor, patrz subpiksel) element obrazu wyświetlanego na ekranie (monitora komputerowego, telewizora itp.), drukowanego (dotyczy technologii druku punktowego) lub uzyskiwanego za pomocą urządzeń przetwarzania obrazu (aparat cyfrowy, skaner).TGA (znany także jako TARGA) – rastrowy format plików graficznych oryginalnie opracowany przez firmę Truevison (teraz Avid). Oryginalnie używany był w kartach graficznych TARGA oraz VISTA, które były pierwszymi procesorami graficznymi obsługującymi standardy high color/true color dla komputerów IBM PC i kompatybilnych.

W niektórych praktycznych implementacjach (np. w filtrach PostScript i PDF, w formacie TGA) zapobiega się kodowaniu serii 1-elementowych, a więc powstawaniu ciągów postaci 1a1b1c1a. W takich przypadkach koder wysyła specjalny kod, który informuje dekoder, że następne n symboli należy wprost skopiować, a nie powielać – dla przykładowych danych będzie to ciąg (4)abca, czyli 5 symboli, zamiast 8.

PostScript – uniwersalny język opisu strony opracowany przez firmę Adobe Systems, będący obecnie standardem w zastosowaniach poligraficznych.Pixmapa, mapa pikseli – plik wykorzystujący rastrowy sposób reprezentacji komputerowej grafiki dwuwymiarowej polegający na określeniu położenia każdego piksela obrazu, oraz przypisaniu mu wartości określającej kolor w danym trybie koloru.

RLE 2D[ | edytuj kod]

W kompresji obrazów bitmapowych można stosować również rozszerzenie metody, w której sprawdza się czy w bieżącym wierszu obrazu powtarzają się piksele z wiersza wcześniejszego, wykorzystując w ten sposób ewentualne przestrzenne zależności.

Może sprawdzać, czy zachodzi równość ciągu pikseli i dla pewnego zakresu jak również na skos, tj. porównywać z ciągami pikseli z poprzedniego wiersza przesuniętymi o jedną pozycję w lewo lub prawo ( lub ). Jeśli zostanie znaleziony taki ciąg, wówczas zapisywana jest jego długość oraz kierunek porównania (tj. powyżej, powyżej na skos w lewo lub prawo). Rzecz jasna prócz tego stosowana jest zwykła metoda RLE.

Move To Front (MTF) – prosta transformacja strumienia danych, używana jako część niektórych procesów kompresji, której zastosowanie może spowodować zmniejszenie entropii. Co za tym idzie, algorytmy kompresji zależne od tej własności (kodowanie Shannona, Shannona-Fano, Huffmana, arytmetyczne) dadzą lepsze wyniki; może także wyprodukować sekwencje lepiej kompresowane metodą RLE.

Przykład[ | edytuj kod]

Fragment obrazu:

y – 1 a b c d a a a b c przetworzony wiersz obrazu
    y b c d a a c c b c przetwarzany wiersz

Wiersz może zostać zakodowany 6 symbolami: (na skos w prawo)5, 2c, (powyżej)2; udało się znaleźć w przetwarzanym wierszu dwa ciągi występujące w poprzednim, oprócz tego powtarza się litera c.

Dla porównania po zastosowaniu wyłącznie kodowania długości serii: 1b1c1d2a2c1b1c (14 symboli), zaś po eliminacji ciągów 1-elementowych: (3)bcd2a2c(2)bc (11 symboli).

Bibliografia[ | edytuj kod]

  • Artur Przelaskowski: Kompresja danych: podstawy, metody bezstratne, kodery obrazów. Warszawa: BTC, 2005. ISBN 83-60233-05-5.
  • Khalid Sayood: Kompresja danych. Wprowadzenie. Warszawa: RM, 2002. ISBN 83-7243-094-2.




  • Reklama