Techniki kompresji

W Google stale pracujemy nad sposobami przyspieszania wczytywania stron internetowych. Można to na przykład zrobić, zmniejszając obrazy z internetu. Obrazy zajmują do 60–65% bajtów na większości stron internetowych, a rozmiar strony to główny czynnik wpływający na łączny czas renderowania. Rozmiar strony jest szczególnie ważny na urządzeniach mobilnych, gdzie mniejsze obrazy oszczędzają zarówno przepustowość, jak i żywotność baterii.

WebP to nowy format obrazu opracowany przez Google i obsługiwany w Chrome, Opera i Androidzie. Został on zoptymalizowany pod kątem szybszego i mniejszych obrazów w internecie. Obrazy WebP są o około 30% mniejsze niż obrazy w formacie PNG i JPEG o tej samej jakości wizualnej. Poza tym format obrazu WebP ma swoje właściwości z innymi formatami. Obsługuje:

  • Kompresja stratna: kompresja stratna jest oparta na kodowaniu klatek kluczowych VP8. VP8 to format kompresji filmów utworzony przez firmę On2 Technologies jako następca formatów VP6 i VP7.

  • Kompresja bezstratna: format kompresji bezstratnej został opracowany przez zespół WebP.

  • Przezroczystość: 8-bitowy kanał alfa przydaje się w przypadku obrazów. Kanału alfa można używać razem z funkcją stratnego RGB, która nie jest obecnie dostępna w przypadku żadnego innego formatu.

  • Animacja: obsługuje animowane obrazy w kolorach.

  • Metadane: może zawierać metadane EXIF i XMP (używane np. przez kamery).

  • Profil kolorów: w profilu może być umieszczony profil ICC.

Dzięki lepszej kompresji obrazów i obsłudze wszystkich tych funkcji WebP może doskonale zamiennikować większość formatów obrazów: PNG, JPEG i GIF. Co więcej, czy wiecie, że WebP zapewnia nowe możliwości optymalizacji obrazów, np. obsługę obrazów stratnych z przejrzystością? Tak! WebP to szwajcarski nóż w formatach graficznych.

Jak to się robi? Podwińmy rękawy i przyjrzymy się bliżej.

Strata WebP

Kompresja stratna WebP korzysta z tej samej metodologii co VP8 do prognozowania klatek (wideo). VP8 opiera się na prognozowaniu bloków i jak każdy inny kodek blokowy, VP8 dzieli ramkę na mniejsze segmenty nazywane makroblokami.

W ramach każdego makrobloku koder może przewidzieć nadmiarowe informacje o ruchu i kolorze na podstawie przetworzonych wcześniej bloków. Ramka obrazu jest „kluczowa” w tym sensie, że wykorzystuje tylko piksele zdekodowane w najbliższej okolicy przestrzennej każdego z makr-bloków i stara się wypełnić nieznaną ich część. Jest to tzw. kodowanie prognozujące (patrz kodowanie wewnątrzklatkowe filmów VP8).

Nadmiarowe dane mogą być następnie odejmowane od bloku, co zapewnia bardziej wydajną kompresję. Pozostała nam jedynie niewielka różnica, zwana reszta, która dotyczy przesyłania w postaci skompresowanej.

Po poddaniu matematycznej odwracalnej przekształcenia (słynnej DCT, czyli dyskretnej transformacji cosinusowej), wyniki zazwyczaj zawierają wiele wartości zerowych, które można skompresować znacznie efektywniej. Wynik jest następnie poddany kwantyzacji i kodowaniu entropii. Co ciekawe, na etapie kwantyzacji tylko straty są odrzucane (na diagramie poniżej wyszukaj dzielenie przez QPj). Pozostałe kroki można odwrócić i bezstratnie.

Poniższy diagram przedstawia kroki związane z kompresją stratną WebP. Cechy wyróżniające w porównaniu z plikami JPEG są oznaczone na czerwono.

WebP stosuje kwantyzację bloków i adaptuje do siebie bity między różnymi segmentami obrazu: mniej bitów dla segmentów o niskiej entropii i większych bitów dla segmentów o większej entropii. WebP korzysta z kodowania entropii arytmetycznej, uzyskując lepszą kompresję w porównaniu do kodowania Huffmana używanego w JPEG.

Tryby przewidywania wewnętrznego VP8

Tryby prognozowania wewnętrznego VP8 są używane z 3 typami makr bloków:

  • 4x4 luma
  • 16x16 luma
  • Kolor 8 x 8

Te makrobloki mają 4 często używane tryby prognozowania wewnętrznego:

  • H_PRED (prognoza pozioma). Wypełnia każdą kolumnę bloku kopią z lewej kolumny – L.

  • V_PRED (prognoza pionowa). Wypełnia każdy wiersz bloku kopią z powyższego wiersza (A.

  • DC_PRED (prognoza DC). Wypełnia blok pojedynczą wartością, używając średniej liczby pikseli z wiersza powyżej A i kolumny po lewej stronie od wartości L.

  • TM_PRED (przewidywanie TrueMotion). Tryb, którego nazwa pochodzi od metody kompresji opracowanej przez On2 Technologies. Oprócz wiersza A i kolumny L TM_PRED używa piksela P powyżej i po lewej stronie bloku. Różnice poziome między pikselami w A (zaczynając od P) są przekazywane przy użyciu pikseli od L do początku każdego wiersza.

Na diagramie poniżej widać różne tryby prognozowania używane przy kompresji stratnej WebP.

W przypadku bloków 4 x 4 luma dostępnych jest 6 dodatkowych trybów wewnątrz, podobnych do V_PRED i H_PRED, ale odpowiadają one przewidywaniu pikseli w różnych kierunkach. Więcej informacji na temat tych trybów znajdziesz w przewodniku po strumieniach bitowych VP8.

Kwantyzacja bloków adaptacyjnych

Aby poprawić jakość obrazu, jest on podzielony na obszary o widocznie podobnych cechach. Dla każdego z tych segmentów parametry kompresji (kroki kwantyzacji, natężenie filtrowania itd.) są dostosowywane niezależnie. Pozwala to uzyskać skuteczną kompresję przez redystrybucję bitów tam, gdzie są najbardziej przydatne. VP8 zezwala na maksymalnie 4 segmenty (ograniczenie strumienia bitowego VP8).

Dlaczego format WebP (strata) jest lepszy niż JPEG

Kodowanie z wyprzedzeniem to główny powód, dla którego WebP wygrywa nad JPEG. Blokowanie kwantyzacji adaptacyjnej też ma duże znaczenie. Filtrowanie pomaga przy średniej i niskiej szybkości transmisji bitów. Kodowanie arytmetyczne logicznego zapewnia o 5–10% większą kompresję w porównaniu z kodowaniem Huffmana.

Bezstratny WebP

Kodowanie bezstratne WebP polega na przekształceniu obrazu za pomocą kilku różnych technik. Następnie kodowanie entropii jest wykonywane na parametrach przekształcenia i danych obrazu po przekształceniu. Przekształcenia zastosowane do obrazu obejmują prognozowanie przestrzenne pikseli, przekształcenie przestrzeni kolorów, użycie lokalnie nowych palet, umieszczenie wielu pikseli w jednym pikselu oraz zastąpienie ich w wersji alfa. Do kodowania entropii używamy wariantu kodowania LZ77-Huffmana, który wykorzystuje kodowanie 2D wartości odległości i kompaktowych wartości rozproszonych.

Przekształcenie prognozujące (przestrzenne)

Przewidywanie przestrzenne służy do ograniczania entropii, wykorzystując fakt, że sąsiednie piksele są często skorelowane. W przekształceniu prognostycznego prognozowana jest bieżąca wartość pikseli, które zostały już zdekodowane (w kolejności linii skanowania), a kodowana jest tylko wartość rezydualna (rzeczywista – prognozowana). Tryb prognozowania określa typ prognozy. Obraz jest podzielony na wiele kwadratowych obszarów, a wszystkie piksele w jednym kwadracie korzystają z tego samego trybu prognozowania.

Dostępnych jest 13 różnych trybów prognozowania. Najczęściej są to piksele lewe, u góry, w lewym górnym rogu i w prawym górnym rogu. Pozostałe to kombinacje (średnie) wartości lewo, góra, lewy górny róg i prawy górny róg.

Przekształcenie koloru (dekorelacji)

Celem przekształcenia kolorów jest dekorowanie wartości R, G i B każdego piksela. Przekształcenie koloru zachowuje wartość zielonego (G) bez zmian, przekształca czerwony (R) na zielony i przekształca niebieski (B) na zielony, a następnie kolor czerwony.

Tak jak w przypadku przekształcenia prognostycznego, najpierw obraz jest dzielony na bloki i ten sam tryb przekształcania jest stosowany do wszystkich pikseli w bloku. W każdym bloku są 3 rodzaje elementów przekształcenia kolorów: zielony_na_czerwony, zielony_na_niebieski i czerwony_na_niebieski.

Odejmij zielone przekształcenie

Funkcja „Odejmij zielone przekształcenie” odejmuje wartości zielone od wartości czerwonego i niebieskiego każdego piksela. Gdy istnieje to przekształcenie, dekoder musi dodać wartość zielonej do niebieskiej i czerwonej. Jest to szczególny przypadek ogólnej przekształcenia dekoracji kolorów powyżej. Jest to dość częste, by można było je przyciąć.

Przekształcenie indeksowania kolorów (palety)

Jeśli nie ma wielu unikalnych wartości pikseli, lepiej utworzyć tablicę indeksów kolorów i zastąpić wartości pikseli indeksami tablicy. Jest to możliwe dzięki przekształceniu indeksowania kolorów. Przekształcenie indeksowania kolorów sprawdza liczbę niepowtarzalnych wartości ARGB na zdjęciu. Jeśli liczba ta nie przekracza progu 256, tworzy tablicę wartości ARGB, która zastępuje wartości w pikselach odpowiednim indeksem.

Kodowanie z pamięci podręcznej kolorów

Bezstratna kompresja WebP wykorzystuje już widoczne fragmenty obrazu do zrekonstruowania nowych pikseli. Jeśli nie znaleziono interesującego dopasowania, można też użyć palety lokalnej. Ta paleta jest stale aktualizowana, aby można było ponownie używać ostatnich kolorów. Na poniższym zdjęciu widać, jak lokalna pamięć podręczna kolorów jest stopniowo aktualizowana o 32 ostatnio używane kolory w miarę skanowania.

LZ77 wsteczne odwołanie

Odwołania wsteczne to kropki o długości i kodzie odległości. Długość wskazuje, ile pikseli w kolejności wiersza skanowania ma zostać skopiowanych. Kod odległości to liczba wskazująca pozycję wcześniej widocznego piksela, z którego mają zostać skopiowane piksele. Wartości długości i odległości są przechowywane z użyciem prefiksu LZ77.

Kodowanie za pomocą prefiksu LZ77 dzieli duże wartości całkowite na 2 części: kod prefiksu i dodatkowe bity. Kod prefiksu jest przechowywany za pomocą kodu entropii, a dodatkowe bity są przechowywane w niezmienionej postaci (bez kodu entropii).

Na diagramie poniżej widać model LZ77 (wersja 2D) z dopasowaniem słów (zamiast pikseli).

Lossy WebP z alfa

Oprócz stratnego kodowania WebP (kolorów RGB) i bezstratnego WebP (bezstratnego RGB z alfa) dostępny jest inny tryb WebP, który umożliwia stratne kodowanie kanałów RGB i bezstratne kodowanie w kanale alfa. Taka możliwość (stratna RGB i bezstratna alfa) nie jest obecnie dostępna w przypadku żadnego z istniejących formatów obrazów. Obecnie webmasterzy, którzy potrzebują przejrzystości, muszą kodować obrazy bezstratnie w formacie PNG, co prowadzi do znacznego wzmożonego rozmiaru. WebP alfa koduje obrazy z mniejszą liczbą bitów na piksel i stanowi skuteczny sposób zmniejszenia rozmiaru takich obrazów. Bezstratna kompresja kanału alfa powoduje dodanie tylko 22% bajtów do stratnego kodowania WebP (o jakości 90).

Ogólnie zmiana przezroczystego pliku PNG na stratną wartość WebP + alfa pozwala zmniejszyć rozmiar o średnio 60–70%. Potwierdzono, że ta funkcja jest bardzo atrakcyjna w przypadku witryn z dużą liczbą ikon (np. everything.me).