Kompresja PNG | Teleinf Edu

Powstanie PNG i ograniczenia GIF

Na początku rozwoju World Wide Web format GIF pozwalał ograniczać rozmiar prostych grafik używanych na stronach i obsługiwał animację. Miał jednak dwa ograniczenia, które doprowadziły do opracowania innego formatu. Paleta GIF obejmowała najwyżej 256 kolorów, więc format nie nadawał się do wiernego zapisu fotografii. Używany w nim algorytm kompresji LZW był objęty patentami, a żądania opłat licencyjnych zwiększały niepewność prawną producentów oprogramowania.

W odpowiedzi grupa programistów opracowała otwarty standard przeznaczony jako wolny od patentów zamiennik GIF. Otrzymał nazwę PNG, rozwijaną jako . Projekt obejmował bezstratną kompresję, obrazy truecolor, progresywne wyświetlanie oraz pełny kanał alfa. Format ma strukturę strumieniową opartą na blokach danych zwanych chunkami. Chunk IHDR opisuje parametry obrazu, kolejne chunki IDAT przenoszą fragmenty jednego strumienia danych, a IEND oznacza koniec datastreamu. Dekoder może przetwarzać chunki po kolei bez wczytywania całego obrazu do pamięci, a CRC pozwala wykryć uszkodzenie zawartości bloku. Dzięki tym właściwościom PNG dobrze nadaje się do grafik z ostrymi krawędziami, tekstem i przezroczystością.

DEFLATE w strukturze PNG

JPEG może stosować stratną kwantyzację w wieloetapowym procesie, natomiast PNG przechowuje dane obrazu bez utraty informacji. Po filtrowaniu scanline'ów PNG zapisuje je w strumieniu zlib, który używa formatu DEFLATE. W PNG metoda kompresji ma numer 0 i korzysta ze strumienia zlib oraz okna DEFLATE o rozmiarze do 32 KiB. Bloki IDAT zawierają kolejne fragmenty jednego strumienia, a opakowanie zlib ma własne dane kontrolne, w tym sumę Adler-32. DEFLATE łączy wyszukiwanie powtórzeń metodą LZ77 z kodowaniem Huffmana. Ten sam format danych występuje między innymi w kontenerach ZIP i GZIP, które mają własne struktury opakowania.

Część 1: Odwołania LZ77 do powtórzeń

Pierwszy etap DEFLATE wykorzystuje , czyli metodę wyszukiwania powtórzeń w ostatnich danych wejściowych. W DEFLATE odwołanie zawiera długość dopasowania i odległość od jego wcześniejszego wystąpienia. Właściwy strumień zapisuje te wartości jako kody długości i odległości, dlatego opis dwóch liczb jest uproszczeniem modelu działania. Przykład znakowy poniżej służy do pokazania zasady, lecz nie opisuje pełnego zapisu bitowego DEFLATE.

Koder czyta dane obrazu bajt po bajcie i utrzymuje "przesuwne okno" ostatnio przetworzonych danych. To okno pełni funkcję słownika. Dla nowych bajtów koder sprawdza, czy taka sama sekwencja znajduje się już w oknie, którego rozmiar w DEFLATE może wynosić do 32 KiB. Odległość nie może wykraczać poza dostępne okno, a dopasowanie może kopiować bajty z obszaru właśnie odtwarzanego.

Jeśli sekwencja jest nowa, koder zapisuje ją jako "literał" i przesuwa okno o zapisane bajty.
Jeśli sekwencja wystąpiła wcześniej, koder zapisuje odwołanie zamiast kolejnych kopii bajtów. Odwołanie zawiera dwie liczby:
1. Odległość: Liczba bajtów między bieżącą pozycją a początkiem dopasowania w oknie.
2. Długość: Liczba bajtów kopiowanych z dopasowania.

Na przykład rozważmy zdanie: "W Szczebrzeszynie chrząszcz brzmi w trzcinie, co Szczebrzeszyn z tego słynie." W tym modelu znakowym przy dopasowaniu drugiego fragmentu "Szczebrzeszyn" odwołanie może mieć postać (odległość: 47, długość: 13), gdy odległość liczy się w znakach od początku bieżącego dopasowania do początku wcześniejszego.

Początkową część zdania zapisuje jako literały i umieszcza ją w oknie.
Przy drugim wystąpieniu "Szczebrzeszyn" znajduje wcześniejsze dopasowanie i zapisuje odwołanie zamiast 13 znaków.
Następny fragment " z tego słynie." zapisuje jako literały.

Ta technika dobrze sprawdza się w grafice generowanej komputerowo, która często zawiera duże obszary jednolitego koloru lub powtarzające się wzory.

Część 2: Kodowanie Huffmana strumienia wynikowego

Wynikiem etapu LZ77 jest strumień literałów oraz odwołań długość/odległość. Drugi etap DEFLATE koduje te symbole za pomocą .

Kodowanie Huffmana jest kodowaniem entropijnym. Koder analizuje częstość symboli, czyli literałów oraz kodów długości i odległości, a następnie buduje książkę kodową, w której:

Symbole występujące często otrzymują krótsze kody binarne.
Symbole występujące rzadko otrzymują dłuższe kody binarne.

Krótsze kody dla częstych symboli zmniejszają rozmiar strumienia. DEFLATE może używać tablic Huffmana ustalonych dla bloku albo tablic zapisanych w samym bloku. Połączenie odwołań LZ77 i kodowania Huffmana tworzy bezstratny etap kompresji używany przez PNG.

Filtrowanie wierszy obrazu przed kompresją

DEFLATE korzysta z powtórzeń w danych. Naturalne obrazy mogą zawierać szum i gradienty, które przerywają długie ciągi identycznych bajtów. PNG stosuje więc odwracalne filtrowanie, które przygotowuje dane obrazu do kompresji.

Koder PNG przetwarza obraz w poziomych wierszach pikseli, czyli wierszach skanowania. Przed kompresją może przekształcić każdy wiersz za pomocą filtru. Jest to odwracalna transformacja matematyczna, która zastępuje bajty wartościami różnicowymi. Sąsiednie piksele często mają podobne wartości, więc różnice zawierają więcej powtórzeń i lepiej pasują do DEFLATE. Filtry działają na bajtach wiersza skanowania, niezależnie od głębi bitowej i typu koloru.

Dla każdego wiersza skanowania koder może wybrać jeden z pięciu typów filtrów. Sposób wyboru należy do kodera, a typ filtru jest zapisywany przed przefiltrowanymi bajtami, aby dekoder mógł odtworzyć dane. Typy filtrów to:

Typ 0: None: Brak filtrowania. Surowe bajty wiersza trafiają do kompresora.
Typ 1: Sub: Każdy bajt jest zastępowany różnicą między nim a bajtem odpowiadającym poprzedniemu pikselowi w tym samym wierszu. Filtr pasuje do łagodnych gradientów poziomych.
Typ 2: Up: Każdy bajt jest zastępowany różnicą między nim a bajtem z poprzedniego wiersza. Filtr pasuje do wzorów powtarzających się pionowo.
Typ 3: Average: Każdy bajt jest zastępowany różnicą między nim a zaokrągloną w dół średnią bajtów z lewej strony i z poprzedniego wiersza. Filtr może pomagać przy gradientach ukośnych.
Typ 4: Paeth: Filtr oblicza predykcję z trzech bajtów, z lewej strony, z poprzedniego wiersza oraz z pozycji lewego górnego sąsiada. Następnie wybiera sąsiada najbliższego predykcji i zapisuje różnicę. Może pomagać przy złożonych wzorach dwuwymiarowych.

Filtrowanie nie zmniejsza samo w sobie liczby bajtów. Przygotowuje wiersze skanowania tak, aby DEFLATE mógł lepiej wykorzystać powtórzenia. Dla filtru Sub oznaczenie poprzedniego elementu uwzględnia liczbę bajtów na piksel, a przy pierwszym pikselu brakujący sąsiad ma wartość zero. Po odwróceniu filtru dekoder otrzymuje pierwotne bajty obrazu. Skuteczność zależy od zawartości obrazu.

Tryby kolorów i przezroczystość w PNG

PNG obsługuje kilka typów obrazów oraz dwa sposoby zapisu informacji o przezroczystości. Typ koloru i głębia bitowa określają układ próbek w każdym pikselu. Standard rozróżnia między innymi skalę szarości, truecolor, indeksowanie oraz warianty z dodatkową próbką alfa.

Tryby kolorów

PNG definiuje tryby przeznaczone dla różnych rodzajów obrazów:

Skala szarości: Jeden kanał jasności może mieć głębię od 1 do 16 bitów na próbkę. Dozwolone są wartości 1, 2, 4, 8 i 16 bitów.
Kolor indeksowany: Piksel przechowuje indeks palety o głębi 1, 2, 4 lub 8 bitów. Paleta może zawierać do 256 wpisów, więc tryb pasuje do obrazów z ograniczoną liczbą kolorów.
Truecolor: Piksel zawiera próbki czerwonego, zielonego i niebieskiego kanału. Przy 8 bitach na próbkę daje to 24 bity na piksel i około 16,7 miliona kombinacji koloru. PNG dopuszcza także 16 bitów na próbkę, czyli 48 bitów na piksel RGB. Dla obrazu truecolor z alfa dochodzi czwarta próbka o tej samej głębi.

Kanał alfa i przezroczystość

PNG obsługuje pełny . W GIF przezroczystość jest związana z jednym kolorem palety, natomiast PNG może przechowywać pośrednie poziomy krycia dla próbek 8- i 16-bitowych. W trybie indeksowanym prostą przezroczystość można opisać dodatkową tablicą tRNS, bez pełnego kanału alfa.

Gdy kanał alfa występuje w trybie skali szarości lub truecolor, każdy piksel otrzymuje dodatkową próbkę o głębi 8 albo 16 bitów. Próbka opisuje stopień krycia. W wersji 8-bitowej wartość 0 oznacza pełną przezroczystość, a 255 pełne krycie. W wersji 16-bitowej zakres wynosi od 0 do 65535. Ten zapis pozwala odwzorować wygładzone krawędzie, cienie i obiekty nakładane na różne tła.