Główna zawartość
Kurs: Podstawy informatyki - program rozszerzony > Rozdział 1
Lekcja 6: Bezstratna kompresja danychBezstratna kompresja obrazu
Obrazy są wokół nas, od ikon aplikacji po animowane GIFy i zdjęcia. Pliki graficzne mogą zajmować wiele miejsca, więc komputery używają szeregu algorytmów, aby kompresować te pliki.
Dla najprostszych obrazów, komputery mogą używać algorytmu kompresji zwanego run-length encoding (RLE).
Mapy bitowe
Zanim poznamy kompresję obrazów, zobaczmy jak możemy reprezentować bitowo obraz bez żadnej kompresji.
Oto prosty obraz, 16x16 ikona serca:
Przyliżmy i nałóżmy na wierzch siatkę, tak aby można było dokładnie zobaczyć, które piksele są czerwone, a które białe:
Ikona serca składa się tylko z dwóch kolorów, czerwonego i białego, więc komputer może przedstawiać w binarnym odwzorowaniu czerwone piksele jako
Używając tej metody, ikona serca byłaby przedstawiona tak:
0001100000110000
0011110001111000
0111111011111100
1111111111111110
1111111111111110
1111111111111110
1111111111111110
1111111111111110
0111111111111100
0011111111111000
0001111111110000
0000111111100000
0000011111000000
0000001110000000
0000000100000000Wyobraźmy sobie, że musisz przeczytać powyższe bity komuś, kto je zapisuje. Po pewnym czasie możesz powiedzieć "pięć zer" zamiast "zero zero zero zero zero". Cóż, komputer może zrobić to samo...
Algorytm kompresji RLE
W kodowaniu RLE, komputer zastępuje każdy wiersz cyframi wskazującymi, ile kolejnych pikseli jest tego samego koloru, zawsze zaczynając od liczby białych pikseli.
Na przykład, pierwszy wiersz zawiera 3 białe piksele, 2 czerwone piksele, 5 białych pikseli, 2 czerwone piksele, następnie 4 białe piksele:
1 100 000 110 000Byłoby to zapisane w następujący sposób:
3,2,5,2,4Czwarty wiersz jest ciekawy, ponieważ zaczyna się od piksela czerwonego. Kodowanie RLE rozpoczyna zapis od ilości białych pikseli, więc zapis będzie tak wyglądał:
0,15,1Dekompresja RLE
Gdy komputer używa kodowania RLE, powinien także być w stanie odtworzyć idealnie obraz ze skompresowanej reprezentacji - powinniśmy postępować zgodnie ze strategią komputera.
Spróbujmy. Oto przedstawienie czarno-białej ikony przy użyciu RLE:
4, 9, 3
4, 7, 2, 1, 2
4, 7, 2, 1, 2
4, 9, 3
4, 7, 5
4, 7, 5
5, 5, 6
0, 15, 1
1, 13, 2Pierwszy wiersz ma 4 białe piksele, a następnie 9 czarnych pikseli, a następnie 3 białe piksele. Wygląda to tak:
Kolejny wiersz ma 4 białe piksele, następnie 7 czarnych, 2 białe, 1 czarny i 2 białe piksele. Wygląda to tak:
Gdy w ten sposób zapiszemy kolejne wiersze, okaże się, że ikona to filiżanka i spodek:
Współczynnik kompresji
Stwierdziliśmy, że kodowanie RLE może zaoszczędzić miejsce w czasie przechowywanie prostych obrazów - ale ile miejsca?
Aby się tego dowiedzieć, napisałem program do kodowanie czarno-białej mapy bitowej metodą RLE. Niniejsza tabela przedstawia wyniki dla trzech ikon serca rosnącego rozmiaru:
| Obraz | Wymiary | Nieskompresowane | po RLE | Oszczędność miejsca |
|---|---|---|---|---|
| 16x16 | 256 | 228 | 10.9% | |
| 32x32 | 1024 | 532 | 48.0% | |
| 128x128 | 16384 | 2898 | 82.3% |
Spójrz na kolumnę końcową, oszczędność miejsca. Zauważyłeś zależność? Zaoszczędziliśmy znacznie więcej miejsca, ponieważ rozmiar wzrasta z powodu znacznie dłuższego powtarzającego się kolor (przebiegu).
A co z obrazami o tym samym rozmiarze? Ta tabela podsumowuje wyniki kompresji trzech dużych ikon za pomocą RLE:
| Obraz | Wymiary | Nieskompresowane | po RLE | Oszczędność miejsca |
|---|---|---|---|---|
| 128x128 | 16384 | 2898 | 82.3% | |
| 128x128 | 16384 | 8298 | 49.4% | |
| 128x128 | 16384 | 8730 | 46.7% |
Teraz widzisz, dlaczego wybrałem ikonę serca jako mój przykład: bardzo dobrze się kompresuje, dzięki wielu seriom czarnego lub białego koloru. Kompresja RLE nadal zmniejsza o połowę rozmiar innych ikon, ale nie oszczędza aż tyle miejsca.
W niektórych przypadkach RLE nie może w ogóle zaoszczędzić miejsca...
Limity RLE
A co z tą ikoną 16x16?
Powiększmy, abyśmy mogli zobaczyć każdy piksel:
Każdy piksel tej ikony jest innego koloru, nie da się tego skrócić.
Kodowanie RLE nie potrafi skompresować takiego obrazka. Ten przykład stworzyłem specjalnie do tego artykułu (wygenerowany przez ten program), wydaję się więc nie być to takie powszechne.
Jak się okazuje, zdjęcia są podobne do tej ikony - prawdziwy świat jest wypełniony detalami nie dającymi się tak skrócić.
Strona drużyny Khan Academy zawiera to piękne zdjęcie psa patrzącego na ekran komputera:
Przy normalnej rozdzielczości wygląda na to, że istnieją bloki o podobnym kolorze, jak na futrze psa lub szary kolor na ekranie komputera.
Przybliżmy widok do pikseli:
Teraz widzisz, że nawet pozornie prosty ekran komputerowy jest rozległym zestawem podobnych kolorów. Kodowanie pikseli RLE nie zrobi zbyt wiele, aby zmniejszyć rozmiar pliku.
Zastosowanie dla RLE
Kompresja RLE była bardzo popularną techniką, kiedy większość obrazów komputerowych była ikonami z ograniczoną paletą kolorów.
W dzisiejszych czasach nasze obrazy są bardziej złożone i nie zawierają tyle obszaru tego samego koloru.
Gdzie jest obecnie używany RLE? Faksy nadal używają RLE do kompresji wysyłanych dokumentów, ponieważ muszą one zapisywać tylko czarno-białe litery. Obrazy JPEG używają RLE na końcowym etapie kompresji, ale najpierw używają bardziej złożonego algorytmu do kompresji danych fotograficznych. Poznamy to wkrótce.
🙋🏽🙋🏻♀️🙋🏿♂️Masz pytania związane z tym zagadnieniem? Możesz zadać swoje pytanie poniżej!
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji