Kompresja PNG

Bezstratna kompresja obrazów z obsługą przezroczystości używająca algorytmu DEFLATE.

W Poszukiwaniu Lepszego Formatu Obrazu: Narodziny PNG

We wczesnych dniach sieci World Wide Web format GIF był królem. Pozwalał na małe rozmiary plików dla prostych grafik używanych na stronach internetowych i dał światu radość prostych animacji. Jednak GIF miał dwie znaczące wady, które skłoniły społeczność internetową do poszukiwania lepszej alternatywy. Po pierwsze, był ograniczony do palety zaledwie 256 kolorów, co czyniło go nieodpowiednim dla wysokiej jakości obrazów fotograficznych. Po drugie, używany przez niego algorytm kompresji LZW był opatentowany, a właściciel patentu zaczął domagać się opłat licencyjnych, tworząc niepewność prawną dla twórców oprogramowania.

W odpowiedzi na to, grupa programistów stworzyła nowy, otwarty standard, zaprojektowany jako lepszy, wolny od patentów zamiennik dla GIF. Nazwali go PNG, co oficjalnie oznacza . PNG został zaprojektowany od podstaw, aby był wszechstronny, potężny i, co najważniejsze, całkowicie bezstratny. Od tego czasu stał się najszerzej stosowanym formatem kompresji bezstratnej w Internecie, cenionym za zdolność do obsługi grafik z ostrymi krawędziami, tekstem i przezroczystością z doskonałą wiernością.

Serce PNG: Algorytm DEFLATE

W przeciwieństwie do JPEG, który używa złożonego, wieloetapowego, stratnego potoku, moc kompresji PNG pochodzi z jednego, genialnego i całkowicie algorytmu znanego jako DEFLATE. Algorytm DEFLATE to nie jedna technika, ale sprytne połączenie dwóch dobrze ugruntowanych metod kompresji stosowanych sekwencyjnie. Jest to ten sam podstawowy algorytm, który jest używany w popularnych formatach archiwizacji plików, takich jak ZIP i GZIP, co świadczy o jego wszechstronności i skuteczności.

Część 1: LZ77 - Znajdowanie Powtarzających się Wzorców

Pierwszy etap DEFLATE wykorzystuje , potężną technikę kompresji opartą na słowniku. Działa on, szukając powtarzających się sekwencji danych w obrazie.

Wyobraź sobie algorytm czytający dane pikseli twojego obrazu bajt po bajcie. Utrzymuje on "przesuwne okno" ostatnio widzianych danych, które działa jak dynamiczny słownik. Czytając nowe dane, ciągle sprawdza swój słownik, aby zobaczyć, czy obecna sekwencja bajtów pojawiła się już wcześniej w oknie.

  • Jeśli sekwencja jest nowa, algorytm po prostu wyprowadza ją jako "literał" i dodaje do swojego słownika.
  • Jeśli sekwencja była już widziana, algorytm robi coś sprytnego. Zamiast wyprowadzać sekwencję bajtów ponownie, wyprowadza znacznie krótsze odwołanie, czyli wskaźnik. Taki wskaźnik zazwyczaj składa się z dwóch liczb:
    1. Odległość: Jak daleko wstecz w słowniku należy spojrzeć, aby znaleźć początek pasującej sekwencji.
    2. Długość: Ile bajtów należy skopiować z tego miejsca początkowego.

Na przykład rozważmy zdanie: "W Szczebrzeszynie chrząszcz brzmi w trzcinie, co Szczebrzeszyn z tego słynie." Algorytm LZ77 przetworzyłby to następująco:

  1. Wyprowadziłby "W Szczebrzeszynie chrząszcz brzmi w trzcinie, co " jako literały.
  2. Gdy dotrze do drugiego "Szczebrzeszyn", znajduje dopasowanie w swoim słowniku. Zamiast pisać te 12 znaków ponownie, wyprowadza wskaźnik, np. (odległość: 38, długość: 12), który jest znacznie krótszy.
  3. Następnie wyprowadza " z tego słynie." jako literały.

Ta technika jest niezwykle skuteczna w przypadku grafiki generowanej komputerowo, która często zawiera duże obszary identycznego koloru lub powtarzające się wzory.

Część 2: Kodowanie Huffmana - Efektywne Kodowanie Wyniku

Wynikiem etapu LZ77 jest mieszanka literałów (dla nowych danych) i wskaźników odległość/długość (dla powtarzających się danych). Drugi etap DEFLATE bierze ten mieszany strumień i kompresuje go dalej, używając .

Kodowanie Huffmana to forma kodowania entropijnego. Działa poprzez analizę częstotliwości każdego symbolu (czy to literału, czy określonego typu wskaźnika) w strumieniu danych. Następnie buduje niestandardową książkę kodową, w której:

  • Symbole, które pojawiają się bardzo często, otrzymują bardzo krótkie kody binarne (np. zaledwie kilka bitów).
  • Symbole, które pojawiają się rzadko, otrzymują dłuższe kody binarne.

Używając mniej bitów dla najczęstszych elementów, ogólny rozmiar strumienia danych jest znacznie zmniejszony. Połączenie zdolności LZ77 do znajdowania wzorców i wydajności statystycznej kodowania Huffmana sprawia, że algorytm DEFLATE jest niezwykle potężny i wszechstronny, stanowiąc bezstratny rdzeń formatu PNG.

Tajna Broń PNG: Filtrowanie Przed Kompresją

Chociaż algorytm DEFLATE jest potężny, działa najlepiej na danych z dużą ilością powtórzeń. Naturalne obrazy, nawet te z dużymi obszarami pozornie jednolitego koloru, często mają subtelny szum lub gradienty, które przerywają długie, idealne ciągi identycznych bajtów. Aby dane obrazu stały się bardziej "kompresowalne" dla silnika DEFLATE, PNG stosuje kluczowy krok wstępny zwany filtrowaniem.

Koder PNG przetwarza obraz po jednej poziomej linii pikseli na raz (tzw. "scanline"). Zanim linia zostanie skompresowana, może zostać "przefiltrowana". Nie oznacza to stosowania efektu wizualnego, jak rozmycie. Jest to odwracalna transformacja matematyczna, która zastępuje rzeczywiste wartości pikseli mniejszymi, bardziej powtarzalnymi wartościami różnicowymi. Chodzi o to, by zakodować *zmianę* z jednego piksela na drugi, a nie absolutną wartość samego piksela. Ponieważ sąsiednie piksele w obrazie są często bardzo podobne, te różnice są często małymi liczbami lub zerami, które są znacznie łatwiejsze do skompresowania przez algorytm DEFLATE.

Dla każdej linii skanowania koder PNG może wybrać jeden z pięciu typów filtrów, wybierając ten, który według jego przewidywań da najbardziej kompresowalny wynik dla tej konkretnej linii. Typ użytego filtru jest następnie zapisywany razem z przefiltrowanymi danymi, aby dekoder wiedział, jak odwrócić ten proces. Typy filtrów to:

  • Typ 0: None - Brak filtrowania. Surowe dane pikseli linii są przekazywane bezpośrednio do kompresora.
  • Typ 1: Sub - Wartość każdego piksela jest zastępowana różnicą między nim a wartością piksela bezpośrednio po jego lewej stronie. Jest to bardzo skuteczne dla obrazów z łagodnymi gradientami poziomymi.
  • Typ 2: Up - Wartość każdego piksela jest zastępowana różnicą między nim a wartością piksela bezpośrednio nad nim w poprzedniej linii skanowania. Działa dobrze dla obrazów z wzorami pionowymi.
  • Typ 3: Average - Wartość każdego piksela jest zastępowana różnicą między nim a średnią wartości pikseli po jego lewej stronie i bezpośrednio nad nim. Jest to dobry filtr ogólnego przeznaczenia, który dobrze radzi sobie z gradientami ukośnymi.
  • Typ 4: Paeth - To najbardziej złożony filtr. Przewiduje wartość bieżącego piksela na podstawie trzech najbliższych sąsiadów (lewy, górny i lewy-górny), a następnie wybiera tego sąsiada, który jest najbliższy przewidywanej wartości. Piksel jest następnie zastępowany różnicą między jego rzeczywistą wartością a wartością wybranego sąsiada. Doskonale radzi sobie ze złożonymi, dwuwymiarowymi wzorami.

Ten inteligentny krok filtrowania jest głównym powodem, dla którego PNG jest często znacznie bardziej wydajny w kompresji grafik i diagramów niż starsze formaty, takie jak GIF, które nie posiadają tego zaawansowanego etapu wstępnego przetwarzania.

Wszechstronność PNG: Tryby Kolorów i Przezroczystość

PNG został zaprojektowany, aby być wysoce elastycznym, zdolnym do obsługi szerokiej gamy typów obrazów. Osiąga to dzięki obsłudze wielu trybów kolorów i rewolucyjnemu podejściu do przezroczystości.

Obsługa Kolorów

PNG nie jest ograniczony do jednej reprezentacji kolorów. Obsługuje kilka trybów w celu wydajnego przechowywania różnych rodzajów obrazów:

  • Skala Szarości: Dla obrazów czarno-białych. Może używać do 16 bitów na piksel dla ogromnego zakresu odcieni szarości.
  • Kolor Indeksowany: Ten tryb jest podobny do GIF. Używa palety do 256 kolorów. Jest idealny dla obrazów z ograniczoną liczbą kolorów, aby osiągnąć mniejszy rozmiar pliku niż tryby pełnokolorowe.
  • Truecolor: Jest to najczęstszy tryb dla obrazów wysokiej jakości. Przechowuje pełną informację o kolorze RGB, zazwyczaj używając 24 bitów na każdy z Czerwonego, Zielonego i Niebieskiego), co pozwala na ponad 16.7 miliona różnych kolorów.

Rewolucyjna Przezroczystość: Kanał Alfa

Być może najważniejszą zaletą PNG nad GIF jest obsługa pełnego . Podczas gdy GIF oferuje tylko binarną przezroczystość (piksel jest albo w pełni widoczny, albo w pełni niewidoczny), PNG pozwala na zmienne poziomy przezroczystości.

Gdy obecny jest kanał alfa (w trybach Skali Szarości lub Truecolor), dla każdego piksela przechowywane jest dodatkowe 8 lub 16 bitów danych. Dane te nie reprezentują koloru, lecz poziom nieprzezroczystości piksela, na skali od 0 (całkowicie przezroczysty) do 255 (całkowicie nieprzezroczysty). Pozwala to na zaawansowane efekty, takie jak gładkie, antyaliasingowe krawędzie, cienie wtapiające się w tło oraz szkliste, przezroczyste obiekty. Ta cecha uczyniła PNG standardowym formatem dla grafik internetowych, logo i ikon, które muszą być płynnie nakładane na różne tła.