Algorytm RLE: opis, cechy, reguły i przykłady

Algorytm RLE to algorytm kompresji danych obsługiwany przez większość formatów plików obrazów rastrowych: TIFF, BMP i PCX. RLE nadaje się do kompresowania dowolnych danych niezależnie od ich zawartości, ale zawartość danych wpływa na współczynnik kompresji. Pomimo tego, że większość algorytmów RLE nie może zapewnić wysokiego stopnia kompresji dla bardziej złożonych metod, to narzędzie jest łatwe do wdrożenia i wykonania szybko, co czyni je dobrą alternatywą.

Na czym oparty jest algorytm kompresji RLE?

RLE działa poprzez zmniejszanie rozmiaru fizycznego powtarzającego się łańcucha znaków. Linia ta, zwana runem, jest zwykle kodowana w dwóch bajtach. Pierwszy bajt reprezentuje liczbę znaków w przebiegu i jest nazywany licznikiem przebiegu. W praktyce przebieg kodowania może zawierać od 1 do 128 znaków i 256 znaków. Licznik zwykle zawiera liczbę znaków minus jeden (wartości w zakresie wartości od 0 do 127 i 255). Drugi bajt jest wartością symbolu w przebiegu, która jest zawarta w zakresie wartości od 0 do 255 i jest nazywana wartością początkową.



Bez kompresji 15-znakowy przebieg bitowy zwykle wymaga 15 bajtów do przechowywania: AAAAAAAAAAAAAAA. W tej samej linii po kodowaniu RLE potrzebujesz tylko dwóch bajtów: 15A. Kodowanie 15A generowane w celu oznaczenia ciągu znaków nazywa się pakietem RLE. W tym kodzie, pierwszy bajt, 15 jest licznikiem przebiegu i zawiera wymaganą liczbę powtórzeń. Drugi bajt, A, jest wartością przebiegu i zawiera rzeczywistą wartość powtarzania w przebiegu.
Nowy pakiet jest generowany za każdym razem, gdy zmienia się symbol początkowy lub za każdym razem, gdy liczba znaków w przebiegu przekracza maksymalną liczbę. Załóżmy, że w ciągu 15-znakowy na warunkach zawierającego 4 różne symbole


AAAAAAbbbXXXXXt pomocą kodowania długość linii, mogą być skompresowane do czterech pakietów dwubajtowych: 6A3b5X1t Po długości linii kodowania 15 bajtów łańcucha potrzebujesz tylko ośmiu bajtów danych do przedstawienia ciągu, w przeciwieństwie do wyjścia 15 bajtów. W tym przypadku kodowanie podczas biegu daje stopień kompresji prawie 2 do 1.

Funkcje

Długie przebiegi są rzadkie w przypadku niektórych typów danych. Na przykład otwarty tekst ASCII rzadko zawiera długie serie. W poprzednim przykładzie ostatni przebieg (zawierający symbol t) miał tylko jeden znak długości. Bieg 1-znakowy nadal działa. Zarówno konto uruchamiania, jak i wartości startowe muszą być rejestrowane dla każdego przebiegu składającego się z 2 znaków. Kodowanie RLE wymaga informacji składających się z co najmniej dwóch znaków. W związku z tym uruchomienie pojedynczych postaci zajmuje więcej miejsca. Z tych samych powodów dane, które składają się wyłącznie z 2-znakowych przebiegów, pozostają niezmienione po kodowaniu RLE.
Algorytmy kompresji RLE to prostota i wysoka wydajność, ale ich wydajność zależy od typu danych zakodowanych w obrazie. Czarno-biały obraz, który w większości jest biały, taki jak strony książki, będzie bardzo dobrze zakodowany ze względu na dużą liczbęsąsiednie dane o tym samym kolorze. Jednak obrazy o wielu kolorach, takie jak zdjęcia, również nie będą kodowane. Wynika to z faktu, że złożoność obrazu wyraża się w postaci dużej liczby różnych kolorów. A z powodu tej złożoności będzie stosunkowo mało przebiegów tego samego koloru.

Opcje kodowania długości

Istnieje kilka opcji kodowania podczas wykonywania. Obrazy te są zwykle kodowane w sekwencyjnym procesie, który obsługuje treści wizualne jako strumień 1D, a nie jako kartę danych 2D. Podczas sekwencyjnego przetwarzania obraz rastrowy jest kodowany, począwszy od lewego górnego rogu, i przechodzi od lewej do prawej na każdej linii skanowania w prawym dolnym rogu obrazu rastrowego. Ale alternatywne RLE mogą być również zapisane do kodowania danych bitmapowych wzdłuż kolumn dla kompresji w płytkach 2D lub nawet do kodowania pikseli po przekątnej w sposób podobny do zygzaka. Nietypowe warianty RLE mogą być stosowane w wysoce wyspecjalizowanych aplikacjach, ale zwykle występują dość rzadko.

Algorytm kodowania z błędem przebiegu

Inną rzadką opcją jest algorytm kodowania RLE z błędem wykonania. Narzędzia te zazwyczaj wykonują kompresję bezstratną, ale odrzucenie danych podczas procesu kodowania, zwykle poprzez resetowanie jednego lub dwóch młodszych znaczących bitów w każdym pikselu, może zwiększyć współczynniki kompresji bez negatywnego wpływu na jakość złożonych obrazów. Ten program algorytmu RLE jest dobrydziała tylko z obrazem świata rzeczywistego, który zawiera wiele drobnych wariacji wartości pikseli.

Cross-Coding

Cross-Coding to kombinacja linii skanowania, która występuje, gdy proces kompresji traci rozróżnienie między liniami wyjściowymi. Jeżeli dane poszczególnych linii są łączone za pomocą algorytmu kodowania powtórzeń RLE, punkt, w którym jedna linia skanowania jest zatrzymywana, a druga jest tracona, jest wrażliwa i trudna do określenia.

Czasami istnieje cross-kodowanie, które komplikuje proces dekodowania, dodając koszt w czasie. W przypadku formatów plików obrazów rastrowych ta metoda służy do porządkowania obrazów rastrowych wzdłuż linii skanowania. Chociaż wiele specyfikacji formatu pliku wyraźnie wskazuje, że linie danych powinny być indywidualnie kodowane, wiele aplikacji koduje te obrazy jako ciągłe strumienie, ignorując granice linii.

Jak kodować obraz za pomocą algorytmu RLE?

Indywidualne kodowanie linii skanowania ma zalety w przypadkach, gdy aplikacja powinna wykorzystywać tylko część obrazu. Załóżmy, że zdjęcie zawiera 512 linii zakresu i należy wyświetlić tylko linie od 100 do 110. Jeśli nie wiedzieliśmy, gdzie linie skanowania zaczynały się i kończyły danymi z zakodowanego obrazu, nasza aplikacja musiałaby dekodować linie od 1 do 100, zanim znajdzie dziesięć linii, które są potrzebne. Jeśli przejścia między liniami skanowania zostały oznaczone przez jakiś łatwo rozpoznawalny znacznik delimitacji, aplikacja może po prostu odczytać zakodowane dane, licząc markery,dopóki nie osiągnie linii, których potrzebuje. Ale takie podejście byłoby raczej nieskuteczne.

alternatywna

Inną opcją w celu określenia punktu początkowego każdej linii skanowania szczególności kodowanego bloku danych jest budowa linii skanowania tabeli. Ta struktura tabelaryczna zwykle zawiera jeden element każdej linii skanowania na obrazie, a każdy element zawiera wartość odsunięcia odpowiedniej linii skanowania. Aby znaleźć pierwsze RLE-10 linii skanowania pakiet wszystko, czego potrzeba, aby dekoder - znajduje wartość przesunięcia pozycji, która jest przechowywana w dziesiątym punkcie linii skanowania tabeli. Tabela wiersza zakresu może również zawierać liczbę bajtów używanych do kodowania każdej linii. Stosując tę ​​metodę, aby odnaleźć pierwszego pakietu RLE-line skanuje dekodera 10 będą łączyć wartości z pierwszych elementów 9-line skanowania tabeli. Pierwszy pakiet linii skanowania 10 rozpocznie się od bajtu przesunięcia od początku danych obrazu z kodowaniem RLE.

Jednostki

Części algorytmów kodowania długości, które różnią się - decyzję podjętą na podstawie typu danych, który jest dekodowany (np długość danych run). Schematy RLE, używany do kompresji grafiki bitmapowej są zazwyczaj podzielone na klasy w zależności od rodzaju atomowych (czyli najbardziej podstawowych elementów, które one kodują trzy klasy są używane przez większość formatów plików graficznych. - jest bity, bajty i pixel RLE

Jakość kompresji.

Szybkości bitowe Programy RLE kodują przebiegikilka bitów w linii skanowania i zignorować granicę bajtów i słów. Tylko monochromatyczne (czarno-białe) obrazy 1-bitowe zawierają wystarczającą liczbę bitów, aby kodowanie klasy RLE było efektywne. Typowa bitmapa RLE koduje od jednego do 128 bitów w pakiecie jednobajtowym. Siedem młodszych znaczących bitów zawiera licznik przebiegu minus jeden, a starszy bit zawiera wartość przebiegu bitowego równą 0 lub 1. Przebieg powyżej 128 pikseli jest podzielony na kilka pakietów zakodowanych za pomocą RLE.

Wykluczenie

RLE na poziomie bajtów koduje przebiegi o tych samych wartościach bajtowych, ignorując niektóre z bitów i granic słów w linii skanowania. Najpopularniejszy schemat RLE na poziomie bajtów koduje przebieg bajtów w pakietach 2-bajtowych. Pierwszy bajt zawiera licznik od 0 do 255, a drugi zawiera wartość początku bajtu. Również rozproszone schematy kodowania aplikacji dbcs z możliwością przechowywania dosłownych, niezapisanych przebiegów bajtowych w strumieniu zakodowanych danych. W tym schemacie siedem młodszych znaczących bitów pierwszego bajtu zawiera licznik przebiegu minus jeden, a najstarszy bit pierwszego bajtu jest wskaźnikiem typu uruchamiania następującego po bajcie wykonania. Jeśli starszy bit jest ustawiony na 1, oznacza to kodowany przebieg. Zakodowane przebiegi są dekodowane poprzez odczytanie wartości biegu i powtórzenie jej liczby razy, oznaczonej liczbą cykli. Jeśli najstarszy bit jest ustawiony na 0, wyświetlany jest literalny przebieg, co oznacza, że ​​bajty następnego przebiegu są zliczane dosłownie z danych zakodowanego obrazu. Następnie bajt licznikawykonywanie zawiera wartości od 0 do 127 (licznik pracy minus jeden). RLE na poziomie bajtów są dobre dla danych obrazu przechowywanych jako jeden bajt na piksel. Schematy pikseli RLE są używane, gdy dwa lub więcej kolejnych bajtów danych są używane do przechowywania wartości jednego piksela. Na poziomie pikseli bity są ignorowane, a bajty są liczone tylko w celu zidentyfikowania każdej wartości piksela. Rozmiar zakodowanych pakietów zależy od wielkości zakodowanych wartości pikseli. Liczba bitów lub bajtów na piksel jest przechowywana w nagłówku pliku obrazu. Uruchamianie danych obrazu zapisanych jako 3-bajtowe wartości pikseli kodowane przez 4-bajtowy pakiet, z jednym bajtem zliczającym liczbę operacji, po których następują trzy bajty bajtów. Metoda kodowania pozostaje taka sama jak w przypadku bajtu RLE.

Powiązane publikacje