Wprowadzenie do kompresji obrazów
Obrazy cyfrowe są używane w fotografii, dokumentach i stronach internetowych. Surowe, nieskompresowane dane obrazu mogą zajmować dużo miejsca. Pojedyncza fotografia o wysokiej rozdzielczości może zajmować dziesiątki megabajtów. Przechowywanie tysięcy takich zdjęć szybko zapełniłoby dysk, a wysłanie jednego przez wolne łącze internetowe mogłoby zająć kilka minut.
Kompresja obrazów zmniejsza rozmiar pliku za pomocą algorytmów, które usuwają lub wydajniej zapisują powtarzalne i mniej istotne informacje. pozwala przechowywać więcej obrazów i szybciej je udostępniać. W danych obrazu może wynikać z powtarzających się wzorów, dużych obszarów jednego koloru lub szczegółów pomijanych przez percepcję. Stosowane techniki obejmują dwa rodzaje kompresji: bezstratną i stratną.
Podział: kompresja bezstratna i stratna
Wybór między kompresją bezstratną a stratną określa kompromis między rozmiarem pliku i zgodnością z oryginałem. Każde podejście służy innym zastosowaniom i typom obrazów.
Kompresja bezstratna: dokładna rekonstrukcja
zmniejsza rozmiar pliku bez odrzucania informacji. Po dekompresji otrzymujemy dokładnie te same dane co przed kompresją, bit po bicie. Zapis wynikowy można odtworzyć bez utraty informacji.
Osiąga się to poprzez znajdowanie statystycznej redundancji w danych. Na przykład, zamiast przechowywać "niebieski, niebieski, niebieski, niebieski, niebieski", algorytm bezstratny może zapisać "(niebieski, 5 razy)". Inna technika polega na tworzeniu słownika wspólnych wzorców i zastępowaniu ich krótszymi kodami. Rozważmy fragment wiersza:
Jakżeż ja się uspokoję,
Pełne strachu oczy moje,
Pełne grozy myśli moje,
Algorytm bezstratny może wykryć powtarzające się frazy "Pełne" oraz "moje" i zastąpić kolejne wystąpienia krótkim wskaźnikiem do wcześniejszego słowa. Oszczędza to miejsce bez zmiany danych. Stopień kompresji zależy od zawartości. Dane powtarzalne kompresują się dobrze, a dane losowe zwykle słabo.
Kiedy używać: Kompresja bezstratna jest wymagana, gdy dane muszą zostać odtworzone bez zmian. Dotyczy to plików tekstowych, programów, obrazów medycznych, takich jak skany MRI, oraz diagramów technicznych. PNG jest bezstratnym formatem obrazu, a GIF stosuje bezstratne LZW po zapisaniu indeksowanej palety.
PNG stosuje odwracalne filtrowanie wierszy obrazu przed kompresją Deflate. Filtr zmienia sposób zapisu sąsiednich próbek, lecz dekoder może odtworzyć pierwotne bajty. Format obsługuje między innymi obrazy indeksowane, w skali szarości, truecolor oraz kanał alfa. Każdy blok (chunk) PNG ma także sumę kontrolną CRC, która pomaga wykrywać uszkodzenia danych. Sam filtr nie usuwa bajtów. Przygotowuje dane do skuteczniejszego kodowania Deflate. Przezroczystość PNG może być przechowywana jako kanał alfa, co odróżnia ją od pojedynczego przezroczystego indeksu GIF. Filtrowanie PNG jest odwracalne i niezależne od kwantyzacji palety.
Kompresja stratna: przybliżenie obrazu
trwale usuwa część danych, aby uzyskać mniejszy plik. Usuwane informacje są wybierane według modelu danych i przewidywanej wrażliwości percepcji.
Metoda ta opiera się na , które opisują wrażliwość ludzkiego wzroku. Wzrok zwykle silniej reaguje na zmiany jasności niż na drobne zmiany koloru, dlatego koder może przechowywać luminancję dokładniej niż chrominancję. Wynik jest przybliżeniem oryginału i przy określonych warunkach oglądania może wyglądać jak obraz bezstratny. Ustawienie "jakości" dobiera kompromis między rozmiarem pliku i wiernością wizualną.
Kiedy używać: Kompresja stratna jest często stosowana do fotografii, wideo i audio, gdy dokładność bit po bicie nie jest wymagana. Niewielka utrata jakości może wtedy uzasadniać zmniejszenie pliku. JPEG jest przykładem stratnego formatu obrazu.
Format GIF: paleta kolorów
GIF, czyli Graphics Interchange Format, jest rastrowym formatem z indeksowaną paletą kolorów. Specyfikacja GIF89a opisuje między innymi animację, przezroczystość i przeplot. Jeśli obraz ma więcej niż 256 kolorów, zapis wymaga redukcji palety, po której indeksy są kompresowane bezstratnym algorytmem LZW.
Krok 1: indeksowana paleta kolorów
Plik GIF używa indeksowanej palety kolorów. Zamiast przechowywać pełną wartość koloru, zwykle 24 bity reprezentujące ponad 16 milionów kolorów, zapisuje tablicę kolorów oraz indeks dla każdego piksela. Paleta GIF może zawierać maksymalnie 256 kolorów.
Jeśli oryginalny obraz zawiera tysiące lub miliony kolorów, jak fotografia, koder GIF wykonuje . Wybiera do 256 kolorów i mapuje pozostałe barwy do najbliższych wpisów palety. Tracone są wtedy subtelne gradienty i odcienie. Dla obrazu, który od początku ma niewiele kolorów, na przykład logo lub diagramu, redukcja palety może zachować wszystkie dane.
Po ustaleniu palety, każdy piksel w obrazie nie jest już reprezentowany przez pełną wartość koloru, ale przez prostą 8-bitową liczbę (), która służy jako indeks do jego koloru w palecie.
Krok 2: kompresja LZW
Po zamianie obrazu na strumień indeksów kolorów stosowany jest bezstratny algorytm Lempel-Ziv-Welch (LZW). LZW buduje słownik powtarzających się sekwencji. Gdy znajdzie znaną sekwencję, zapisuje kod wskazujący jej wpis zamiast całej sekwencji. Jest to skuteczne dla obrazów z dużymi obszarami jednolitego koloru, ponieważ długi ciąg identycznych indeksów może zostać zapisany za pomocą kilku kodów.
W danych GIF kody mają rozmiar zależny od słownika i są poprzedzone minimalnym rozmiarem kodu. Strumień zawiera również kody czyszczenia słownika oraz zakończenia danych. Po dekompresji otrzymuje się dokładnie ten sam strumień indeksów, który zapisano po redukcji palety.
Cechy specjalne i zastosowania
- Animacja: GIF może przechowywać wiele klatek w jednym pliku wraz z informacją o czasie ich wyświetlania, co pozwala tworzyć proste animacje zapętlone.
- Przezroczystość: GIF obsługuje binarną przezroczystość. Jeden kolor palety można oznaczyć jako przezroczysty, lecz format nie przechowuje częściowej przezroczystości kanału alfa.
- Przeplot: GIF z przeplotem jest wyświetlany w kilku przebiegach. Wstępny obraz pojawia się przed pobraniem wszystkich danych, a kolejne przebiegi go uzupełniają.
Format JPEG: kompresja fotografii
JPEG (nazwa pochodzi od grupy Joint Photographic Experts Group) jest formatem przeznaczonym między innymi do stratnej kompresji obrazów o ciągłych tonach, takich jak fotografie. Wykorzystuje właściwości percepcji wzrokowej, lecz uzyskany rozmiar i jakość zależą od parametrów kodowania.
ITU-T T.81 opisuje między innymi bazowy sekwencyjny proces DCT, procesy rozszerzone i progresywne oraz procesy bezstratne. Konkretny plik JPEG może więc używać innego profilu i innych tablic niż przykład bazowy.
Proces kompresji JPEG obejmuje kilka etapów:
- Transformacja przestrzeni kolorów:
Obraz jest zazwyczaj konwertowany z przestrzeni RGB (czerwony, zielony, niebieski) do przestrzeni luminancji i chrominancji YCbCr. Rozdziela to jasność (Y, luma) od koloru (Cb i Cr, chrominancja). Wzrok jest zwykle bardziej czuły na drobne szczegóły jasności niż na szczegóły koloru.
- Podpróbkowanie chrominancji:
Składowe chrominancji mogą być zapisywane z mniejszą rozdzielczością niż luminancja. W schemacie blok pikseli współdzieli próbki Cb i Cr, podczas gdy każdy piksel zachowuje własną próbkę Y. Zmniejsza to liczbę próbek koloru, lecz wpływ zależy od obrazu i parametrów kodera.
Inne schematy, takie jak i , zachowują odpowiednio więcej próbek chrominancji. Podpróbkowanie nie jest wymagane w każdym kodowaniu JPEG.
- Dyskretna transformata kosinusowa (DCT):
Obraz jest dzielony na bloki pikseli . Każdy blok jest przetwarzany przez . Transformacja przedstawia blok za pomocą 64 współczynników częstotliwości. Pierwszy współczynnik, współczynnik DC, opisuje składową stałą, a pozostałe 63 współczynniki AC opisują zmiany i szczegóły obrazu.
Sama transformata zmienia reprezentację współczynników. Odrzucanie informacji następuje w kolejnym etapie kwantyzacji, nie podczas obliczania DCT.
- Kwantyzacja:
To główny stratny etap JPEG. Każdy z 64 współczynników DCT jest dzielony przez odpowiednią wartość z 64-elementowej , a wynik jest zaokrąglany do liczby całkowitej. Większe wartości tablicy silniej zmniejszają współczynniki, szczególnie dla wysokich częstotliwości, więc wiele z nich staje się zerami. Ustawienie "jakości" w koderze zwykle skaluje tablice kwantyzacji lub wybiera ich wariant, lecz szczegóły zależą od implementacji.
- Kodowanie entropijne:
W ostatnim etapie skwantyzowane współczynniki są odczytywane w porządku zygzakowatym, który grupuje zera. Sekwencje zer są zapisywane za pomocą (RLE). W profilu baseline JPEG symbole są następnie kodowane bezstratnie za pomocą tablic Huffmana. T.81 definiuje także alternatywne kodowanie arytmetyczne.
Warto odróżnić utratę związaną z kwantyzacją od końcowego kodowania entropijnego. RLE i kodowanie Huffmana nie usuwają informacji z już skwantyzowanych współczynników. T.81 opisuje również procesy bezstratne i predykcyjne, dlatego określenie JPEG nie oznacza jednego obowiązkowego przebiegu.
W typowym kodowaniu baseline współczynnik DC jest kodowany różnicowo względem poprzedniego bloku, a współczynniki AC opisują długość serii zer i rozmiar wartości. Tablice Huffmana są częścią strumienia JPEG. Ich dobór wpływa na długość końcowego bitstreamu, a ustawienie jakości zmienia przede wszystkim kwantyzację.