Ścisnąć tyle, ile się tylko da

Komputery coraz bardziej integrują się z obrazem. Aplikacje multimedialne, przesyłanie obrazów, wideokonferencje, cyfrowe wideo definitywnie przestają być domeną futurologów. Coraz bardziej stajemy się cywilizacją obrazu. Obraz, zwłaszcza kolorowy, zajmuje całkiem sporo miejsca. Coraz powszechniejsze staje się wołanie o jego kompresję - dobrą i szybką.

Komputery coraz bardziej integrują się z obrazem. Aplikacje multimedialne, przesyłanie obrazów, wideokonferencje, cyfrowe wideo definitywnie przestają być domeną futurologów. Coraz bardziej stajemy się cywilizacją obrazu. Obraz, zwłaszcza kolorowy, zajmuje całkiem sporo miejsca. Coraz powszechniejsze staje się wołanie o jego kompresję - dobrą i szybką.

Komputery są coraz szybsze, lepsze i mają więcej pamięci. Cóż z tego, skoro apetyty i potrzeby użytkowników rosną zawsze cokolwiek szybciej. By im sprostać komputery powinny być jeszcze lepsze, jeszcze szybsze i tak bez końca. Już niewiele czasu potrzeba, by multimedia naprawdę "trafiły pod strzechy". Multimedia to hasło-wytrych, coś z czym będziemy się stykać coraz częściej, czyli połączenie siły różnych mediów i sposobów przekazu w programie komputerowym. Są one przede wszystkim ogromnie pamięciochłonne. A multimedia czy film wideo, to już całkiem horrendalne rozmiary plików. Jedynie kompresja obrazu może zminimalizować ilość miejsca potrzebnego na jego przechowanie. Opracowano wiele technik kompresji i stworzono wiele algorytmów; niektóre z nich zastosowano już w sprzęcie.

Wszystkie algorytmy kompresji danych, ograniczają redundancję (nadmiarowość) informacji. Jednak większość z nich nie jest odpowiednia do upakowania obrazów graficznych (stosując metody ogólne nie osiągnie się w praktyce lepszego współczynnika kompresji niż 1:3). O ile strata jednego bitu dla kodu źródłowego może oznaczać katastrofę, o tyle w przypadku grafiki będzie praktycznie niezauważalna. Stąd łatwo wysnuć wniosek, że istnieją algorytmy specjalnie stworzone do graficznych. Kompresja polega tutaj na takim odrzuceniu części informacji opisującej obraz, by oko ludzkie nie było w stanie tego spostrzec lub by pogorszenie jakości obrazu było możliwie małe i zależne od żądanego stopnia kompresji (który może być nawet jak 1:100). Takie algorytmy kompresji obrazu określa się mianem: lossy (bo tracimy część informacji), w przeciwieństwie do tradycyjnych metod typu loseless, gdzie obrazek będzie mógł być odpakowany dokładnie do wejściowej postaci.

Algorytm JPEG i pokrewne

Właściwości piksela określają dwa parametry: chrominancja (opisująca barwę) i luminancja (poziom jasności). Człowiek odbiera znacznie silniej bodźce wzrokowe związane z jasnością, a słabiej z barwą (co sprawia, że powinniśmy przede wszystkim szukać oszczędności redukując ilość informacji potrzebnych do opisania chrominancji).

Najbardziej popularne algorytmy kompresji obrazów związane są z metodami przetwarzania sygnałów cyfrowych (a więc traktowania obrazu jako mapy bitowej). W obecnej chwili standardem de facto staje się algorytm JPEG (skrót od: Joint Pictures Expert Group), bazujący na dyskretnej transformacie kosinusowej (Discrete Cosine Transform).

Standard JPEG został już uznany przez CCITT (International Telegraph and Telephone Consultative Committete - organizację, która m.in. opracowała standard przesyłania faksów), a wkrótce ma stać się normą ISO. Na tym algorytmie bazuje większość dostępnych kart realizujących sprzętową kompresję obrazu.

Zasadniczy proces kompresji przebiega następująco: obraz zostaje podzielony na bloki 8x8 pikseli; pojedynczy blok traktuje się nie jako wzorzec bitowy, ale sygnał o zmiennej wartości, który może być aproksymowany zbiorem 64 funkcji typu kosinus (o różnych częstotliwościach). Z każdą taką funkcją związany jest współczynnik określający wartość jej amplitudy. Kompresja polega na zaniedbaniu funkcji, których współczynniki są stosunkowo małe, mniej dokładnym reprezentowaniu współczynników dla funkcji o wyższych częstotliwościach oraz kwantyzacji otrzymanych wartości w odpowiedni zakres wartości (którego rozpiętość jest określona stopniem kompresji obrazka). Otrzymany w ten sposób ciąg danych zostaje uporządkowany i dodatkowo spakowany za pomocą kodowania arytmetycznego lub kodów Huffmana.

Proces dekompresji jest analogiczny (przy zachowaniu odwrotnej kolejności działań - tyle, że oczywiście nie możemy przeprowadzić "dekwantyzacji", ta część informacji zostaje stracona). Próbuje się ulepszać działanie algorytmu, stosując inne, bardziej złożone funkcje bazowe zamiast kosinusów, ale efekty są tutaj bardzo niejednoznaczne (tj. nie można mówić o ogólnym usprawnieniu).

Podstawowa implementacja algorytmu JPEG jest dostępna za darmo (jako kod źródłowy).

Algorytm JPEG ma poważne wady, wynikające bezpośrednio ze sposobu w jaki jest on realizowany. Skutkiem dzielenia pierwotnego obrazu na bloki pikseli poddane później obróbce, obraz po dekompresji może wyglądać tak, jakby składał się z dużych kwadracików (b. widoczne staje się zmniejszenie rozdzielczości obrazka). Dokuczliwy może być też tzw. efekt Gibbsa, czyli dodanie zbędnych linii (zmarszczek) przy kontrastowych krawędziach przedmiotów (np. pniach drzew na tle nieba).

Problem kompresji staje się o wiele bardziej skomplikowany, gdy mamy do czynienia z kompresją obrazków ruchomych (a żyjemy już w czasach gdy cyfrowe wideo na stacjach roboczych przestaje być czymś niezwykłym). Korzystając z tego, że film nie jest niczym innym tylko sekwencją kolejnych nieruchomych klatek można kodować je jedna po drugiej, ale byłoby to niezwykle rozrzutne rozwiązanie. Poszczególne klatki są na ogół do siebie bardzo podobne i dobry algorytm kompresji powinien to uwzględniać. Podstawowy algorytm MPEG (od Moving Pictures Experts Group) jest ciągle jeszcze niedostatecznie opracowany, by mógł stać się światowym standardem.

W praktyce istotne są trzy rodzaje klatek (ramek - frames):

- osobne klatki z całym obrazem (intraframe)

- klatki których wygląd da się przewidzieć za pomocą wektorów przemieszczenia (motion vectors)

- zrekonstruowane z klatek sąsiednich (interpolowane).

Przy obecnych mocach obliczeniowych stacji roboczych konieczne jest sprzętowe wspomaganie kompresji ruchomych obrazów. Wiele firm konstruuje procesory sygnałowe (DSP), realizujące mutacje algorytmu MPEG. Z pomocą takich układów powstały technologie VDI Intela (z procesorem i750) i CD-I Philipsa.

Obecnie można uzyskać (za rozsądną cenę) kompresję/dekompresję obrazu 30 klatek/s. dla trybu true color (24 bity/piksel) przy rozdzielczości 640x480 pikseli (np. z pomocą urządzenia zwanego MediaSpace, skonstruowanego w wyniku współpracy znanego angielskiego producenta sprzętu multimedialnego, firmy VideoLogic oraz , tej od Postscriptu). Przewiduje się, że do końca bieżącej dekady powinny powstać systemy dokonujące w czasie rzeczywistym kompresji i dekompresji obrazu telewizyjnego o jakości studyjnej.

Zainteresowanych bardziej dokładnym poznaniem szczegółów technicznych algorytmów JPEG i MPEG odsyłam do poświęconego tej tematyce numeru pisma "Communications of the ACM" z kwietnia 1991 r.

Można inaczej

Jednak niedoskonałość i nieadekwatność technik kompresji, bazujących na cyfrowym przetwarzaniu sygnałów, zwróciła uwagę naukowców w stronę rozwiązań alternatywnych. Przełomu dokonał dr Michael Barnsley, opracowując technologię i algorytmy kompresji fraktalnej. W latach osiemdziesiątych założył firmę Iterated Systems Inc, by swoje idee przemienić w produkt rynkowy.Efekty przerosły najśmielsze oczekiwania - opracowana technika kompresji obrazu była na tyle nowatorska i rewolucyjna, ze początkowo pokpiwano sobie z jej twórców, oskarżając ich o blefowanie ("to nie ma prawa działać...").

Fraktal można zdefiniować sobie jako obrazek, który powiększony dowolną liczbę razy, zawsze będzie miał jeszcze niewidoczne szczegóły, a do jego narysowania wystarczy użyć małego zbioru instrukcji i danych - np. można to zrobić za pomocą programu komputerowego (to trochę mało ścisła definicja, ale wystarczająca jak na potrzeby tego artykułu). Najważniejszą obserwacją B. Mendelbrota, odkrywcy i pierwszego badacza fraktali, jest spostrzeżenie, że właśnie z ich pomocą można najlepiej opisać obiekty naturalne, takie jak drzewa, góry, itd. Co więcej, obraz naturalny wydaje się być w dużym stopniu "samopodobny" (np. jak drzewa w lesie), a właśnie samopodobieństwo jest podstawową właściwością fraktali. Co więcej kawałki tego samego obrazka wydają się być do siebie o wiele bardziej podobne niż do kawałków innych obrazków (to tzw. redundancja afiniczna). Najważniejszą implikacją tego faktu, jest możliwość opisania skomplikowanych obrazów za pomocą niewielkiej liczby danych - jako współczynników przekształceń afinicznych (p. ramka). Ideą M. Barnsley'a było takie zautomatyzowanie procesu znajdowania parametrów odpowiednich przekształceń, by mogło się to odbywać całkowicie bez ingerencji człowieka. W roku 1991 Iterated Systems opatentował tę technologię, zastrzegając ją pod nazwą Fractal Transform.

Proces kompresji polega zasadniczo na podziale obrazu wejściowego na pewną liczbę odpowiednich kawałków (podzbiorów, których kształt zależy od konkretnego obrazu) i znalezieniu odpowiednich przekształceń afinicznych (p. ramka), odwzorowujących jeden z kawałków na drugi (tak by po przekształceniu były do siebie podobne). Istotną informacją, na podstawie której można odtworzyć obraz, są współczynniki tych przekształceń i sposób jego podziału.

Proces dekompresji przebiega inaczej: jest to realizacja algorytmu tworzenia obrazu dla funkcji iterowanych (Iterated Function System).

JPEG a Fractal Transform

Istotną przewagą algorytmu kompresji fraktalnej nad tradycyjnymi metodami, takimi jak algorytm JPEG, jest niezależność od wejściowej rozdzielczości - obrazek może być zdekodowany w dowolnej wielkości (ponieważ ważna jest tylko informacja o przekształceniach, a nie liczba pikseli jaka była na początku, co sprawia, że spakowany obrazek jest w pełni skalowalny). Ma to dzisiaj, w dobie wielości standardów oraz trybów kart i drukarek graficznych, ogromne znaczenie.

Upakowane pliki są zapisywane w formacie Fractal Image Format (w skrócie: FIF). Może to trochę wyglądać na paradoks, ale obraz po przekształceniu go w plik *.FIF jest w pewnym sensie opisany w sposób bardziej naturalny (tzn. człowiek patrzy na rzeczy całościowo, tak jak dzieje się to w algorytmie kompresji fraktalnej, a nie piksel po pikselu, czyli kawałeczek po kawałeczku).

Algorytm kompresji fraktalnej, w przeciwieństwie do kompresji JPEG, jest asymetryczny. Czas potrzebny na dokonanie kompresji obrazu może być dłuższy nawet kilkaset razy niż w przypadku dekompresji. Ekstremalnie dekompresja może być nawet tak szybka, że sumaryczny czas potrzebny na ściągnięcie pliku *.FIF z dysku twardego i jego dekompresję na mapę bitową w pamięci, będzie krótszy niż czas oczekiwania na wgranie z dysku pliku z obrazkiem nieskompresowanym(!). Zwykle jest to na typowym Pececie kilka sekund (w porównaniu do ok. 1 min. w wypadku algorytmu JPEG). Ta cecha algorytmu kompresji fraktalnej sprawia, że jest to idealne rozwiązanie dla gotowych aplikacji multimedialnych (np. na CD-ROM-ach). Zauważył to już Microsoft, wybierając algorytm kompresji fraktalnej z Iterated Systems do swojej multimedialnej encyklopedii Encarta. Stosowanie algorytmu JPEG jest zalecane w aplikacjach, w których musimy często przeprowadzać kompresję obrazów (np. przy interakcyjnej pracy z obrazem wideo).

Nie bez znaczenia jest daleko wyższa (średnia) efektywność techniki kompresji fraktalnej nad algorytmem JPEG, gdzie dla porównywalnej jakości obrazu, stopień upakowania na ogół będzie daleko większy przy zastosowaniu pierwszej metody.

W wersji handlowej oprogramowanie realizujące algorytm kompresji fraktalnej jest dostępne jako pakiety POEM ColorBox, POEM Hi-Res i POEM VideoBox. Dają one do ręki programiście gotowe narzędzie, które może zastosować w programach (np. w postaci bibliotek DLL, za ok. 1000 USD dostaje się prawo do 20 tzw. run time licenses).

Warto zauważyć, że komercyjne implementacje algorytmu kompresji fraktalnej pojawiły się niedawno i jeszcze nie zdążyły zadomowić się na rynku. Znaczenie tej techniki będzie niewątpliwie rosło. Iterated Systems pracuje obecnie nad zastosowaniem tych algorytmów do kompresji cyfrowych obrazów telewizyjnych (głównie HDTV) i być może telewizja następnej generacji będzie miała właśnie wiele wspólnego z geometrią fraktali.

Przekształcenie afiniczne: zmienia położenie przedmiotu, może go obracać i skalować, a co więcej zmieniać proporcje między jego długością i szerokością. W algorytmie kompresji fraktalnej przekształcenia te operują w przestrzeni trójwymiarowej, gdzie trzecim wymiarem jest kolor i jasność piksela.

Podstawowe skróty:

JPEG - międzynarodowy standard określający metodę kompresji obrazków nieruchomych (kolorowych i z odcieniami szarości).

JBIG - mutacja algorytmu JPEG dla obrazków biało-czarnych (bi-level czyli dwupoziomowych), np. do przesyłania faksem

MPEG - ciągle rozwijany algorytm kompresji obrazów sekwencyjnych, mający wiele wspólnego z algorytmem JPEG

*p64 - algorytm kodowania obrazu wideo z przeznaczeniem do stosowania w sieciach ISDN

CD-I - marka handlowa Philipsa, sprzęt oparty na CD służący do zabawy multimediami na "domowy użytek", a także określenie algorytmów kompresji obrazu wideo opracowanego przez Philipsa na użytek CD-I

Znane algorytmy kompresji obrazu charakteryzują się dość znacznym stosunkiem upakowania (typowa wartość to 1:25). Klasyczny algorytm JPEG, bazujący na dyskretnej transformacie kosinusowej, staje się powoli światowym standardem. Jednocześnie rozwijane są metody i algorytmy kompresji obrazów ruchomych. Wielkie nadzieje wiąże się z nową techniką, w której używa się fraktali do kompresji obrazu. Celem kompresji fraktalnej jest "matematyczne modelowanie" wejściowego obrazka z pomocą właściwego fraktala, tak dokładnie, jak to jest tylko możliwe.


TOP 200