JPEG w trybie progressive, zigzag scan

Mało kto zdaje sobie sprawę, że standard JPEG od dawien dawna przewiduje dwa podstawowe tryby zapisu skompresowanych danych – sekwencyjny i progresywny.

Ten pierwszy jest obecnie powszechniejszy, w rozmaitych aparatach cyfrowych, tych oddzielnych czy tych wbudowanych w urządzenia mobilne tryb sekwencyjny jest szeroko stosowany, za to trudno spotkać urządzenie, które oferowałoby zapis w formie progresywnej. Za to historycznie, tryb progressive miał swój okres świetności w pierwszych latach Internetu.

Po czym można było poznać (wówczas), że obrazek na stronie internetowej był zakodowany progresywnie? Otóż większość użytkowników Internetu łączyło się poprzez modemy telefoniczne o prędkościach nieprzekraczających 30 kbit/s . Wczytywanie obrazków w dużej rozdzielczości bywało wtedy uciążliwe, a sztuczki polegające na wyłączaniu pobierania obrazków w przeglądarce były często stosowane, gdy liczyła się przede wszystkim treść tekstowa.

Przy takich prędkościach nieraz widać było, jak obrazek się wczytuje (zdaje się, że nie było tego widać w Internet Explorerze), po kwadraciku, od górnego lewego rogu w prawo, linia po linii, niczym drukarka. To był tryb sekwencyjny.

1. Zgrubnie –> szczegółowo

Czasem spotykało się strony, na których niemal natychmiast pojawiał się obrazek, jednak całkowicie rozmazany. I z czasem, z sekundy (albo minuty) na sekundę wyostrzał się, żeby stać się zupełnie ostrym po jakimś czasie. I to był właśnie tryb progresywny.

Ilustracja:

lena_progr

To jest akurat animowany gif, nie jest to jpeg zakodowany progresywnie, więc nie obawiajcie się o prędkość łącza. Być może część z Was skojarzy, że na takie zjawisko nadal możemy się natknąć. Ba, część blogów o tworzeniu serwisów internetowych zaleca tryb progressive wobec zdjęć z dość prostej przyczyny – niektórzy użytkownicy urządzeń mobilnych mogą mieć akurat słaby zasięg sieci, wówczas progresywne ładowanie obrazków dobrze wpływa na odbiór, czyli tzw. user experience.

Inżynierowie w Googlu również odkurzyli tryb progressive i stosują go w swoich aplikacjach Google Maps i Street View. Wystarczy spowolnić sobie łącze, na linuxie można na przykład tak:

I wtedy wchodzimy w Street View…

streetview
źródło: Google Street View

W tym przypadku wygląda na to, że obrazki Googla składają się tylko z dwóch skanów, najpierw dostajemy obraz całkowicie rozmazany, a po chwili już zupełnie ostry. Takie przynajmniej odniosłem wrażenie.

Nie zapomnijmy usunąć ograniczenia pasma:

 Tryb progresywny w skrócie polega na stopniowym przesyłaniu współczynników DCT, najpierw te o najmniejszych częstotliwościach, na czele ze składową stałą, później te o częstotliwościach wyższych, odpowiadające za coraz drobniejsze szczegóły.

2. Zigzag scan

Omawialiśmy już transformację DCT oraz to, że ma ona “skłonność” do kumulowania informacji w sąsiedztwie składowej stałej.

Otóż po przeprowadzeniu DCT, a następnie kwantyzacji, macierz współczynników kompresowana jest bezstratnie, w sposób zbliżony do kodowania Huffmana z dodatkowym kodowaniem długości serii. Ponieważ współczynniki leżące na okręgach o środku w postaci składowej stałej często mają zbliżone wartości, dlatego do kompresji bezstratnej kodek nie bierze współczynników od lewa do prawa, z góry na dół tak, jak można by było naiwnie założyć.
Twórcy JPEGa (MPEGa również) zdecydowali, że skwantowane współczynniki DCT wjadą na kodek entropijny po zygzaku:

zigzag
źródło: Wikipedia

Znalazłem nawet przykłady kodu źródłowego, który generuje tablicę z kolejnością odwiedzania komórek w przypadku skanowania zygzakowego. Link >>>>

Zygzak pozwala po pierwsze na takie uszeregowanie współczynników, że te o zbliżonych wartościach będą występowały obok siebie. Po drugie, zera (zerowe współczynniki) będą najczęściej występować seriami, co bardzo ucieszy koder entropijny. Po trzecie, wskutek kwantyzacji często całe prawe dolne pole macierzy DCT to same zera. Koder entropijny w ogóle się po nich nie przebiegnie, tylko postawi znacznik końca bloku wtedy, gdy pozostałe współczynniki wzdłuż zygzaka będą zerowe . Ładnie pokazują to w Wikipedii, gdzie “rozłożono” macierz DCT już po kwantyzacji wzdłuż zygzaka. Link >>>>

O skanowaniu zygzakowym warto wiedzieć, szczególnie gdy mamy przejśc do tego, jak zrealizowane jest kodowanie progresywne.

3. Spectral selection oraz successive approximation

Tryb progressive to w zasadzie dwa oddzielne tryby. W przypadku obu trybów pierwszym skanem umieszczonym w pliku albo przesłanym do klienta będzie skan złożony ze wszystkich składowych stałych wszystkich bloków 8×8, z których złożony jest obraz.

W przypadku spectral selection kolejne skany zawierają kolejne “pasma” współczynników według zygzaka. W poniższej ilustracji wybrałem następujące pasma:

  • składowa stała (DC) (współczynnik pierwszy)
  • współczynniki od 2 do 4
  • wsp. 5 – 8
  • wsp. 9-12
  • wsp 13-20
  • wsp 21-30
  • wsp 31-64

Widać, jak kolejno wraz z uzupełnianiem współczynników DCT obraz się wyostrza:

zigzag_prog

W przypadku successive approximation jest trochę inaczej. Ponieważ współczynniki DCT kodowane są na pojedynczych bajtach, więc każdy współczynnik można zapisać jako

b7 b6 b5 b4 b3 b2 b1 b0

To po przesłaniu składeowej stałej kolejne skany zawierają kolejne przedziały bitów dla wszystkich współczynników, czyli przykładowo:

  • składowa stała (DC) (współczynnik pierwszy, bity b7 b6 b5 b4 b3 b2 b1 b0)
  • składowe AC od 2 do 64, tylko bity b7 b6 b5
  • składowe AC od 2 do 64, tylko bity b4 b3
  • składowe AC od 2 do 64, tylko bit b2
  • składowe AC od 2 do 64, tylko bity b1 b0

Tutaj ilustracji nie ma (jeszcze), niestety z braku czasu.

4. Efektywnośc kompresji w trybie progressive

Tryb progressive w założeniach miał ułatwić prezentację obrazków w czasie ich ładowania. Nie była załóżeniem twórców poprawa efektywności kompresji, w zasadzie przewidywano, że w trybie progressive obrazki będą zajmować więcej niż w trybie sekwencyjnym.

Jednak standard JPEG w pewnym momencie dopuścił możliwość definiowania własnych tablic Huffmana i własnych tablic kwantyzacji. Wraz z rozwojem koderów JPEGa okazało się, że w trybie progresywnym da się osiągnąć kompresję o kilka – kilkanaście procent lepszą niż w trybie sekwencyjnym. I że podobno w trybie progresywnym lepiej kompresują się obrazy zaszumione. Ale wiadomo, nie należy za bardzo wierzyć w to co piszą w Internecie.
Tak czy inaczej, polecam stosowanie trybu progresywnego przy jpegach. Warto wspomnieć, że oprócz sekwencyjnego i progresywnego JPEG posiada jeszcze 2 tryby – bezstratny i hierarchiczny, z czego ten drugi zasługuje na szczególną uwagę. Być może kiedyś sklecę na ten temat notkę

 

Niestety od jakiegoś czasu zaniedbałem bloga. Uprzejmie przepraszam czytelników. Jednocześnie muszę zdradzić, że stworzenie jednej notki zajmuje mi często cały dzień roboczy i to najlepiej jednym ciągiem. Mam zapisane szkice kliku notek ale ciężko mi do nich wrócić po tygodniu, a co do piero po miesiącu. Jeśli chcielibyście mi zasugerować jakiś temat, to proszę o zostawienie komentarza.

 

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

Możesz użyć następujących tagów oraz atrybutów HTML-a: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">