następny punkt »


1. Kompresja obrazów

Gotowe obrazy są pamiętane w postaci map bitowych. Przy obecnie stosowanych rozdzielczościach obrazów 800 ´ 600, 1024 x 768 czy 1280 ´ 1024 i 24 bitach na piksel ilość miejsca w pamięci potrzebna na zapisanie pojedynczego obrazu jest znaczna (odpowiednio w przybliżeniu 1,44 MB, 2,36 MB, 3,93 MB). Dodatkowy problem pojawia się przy przesyłaniu obrazów - czas transmisji jest odpowiednio długi. Stąd pojawia się potrzeba stosowania kompresji obrazów, a więc zapisywania ich w takiej postaci, żeby możliwie maksymalnie zmniejszyć ilość pamięci potrzebnej do zapamiętania obrazu.

W kompresji obrazów wyróżnia się dwa podejścia. W jednym z nich zakłada się, że kompresja ma być bezstratna. Oznacza to, że obraz poddany kompresji, a następnie dekompresji będzie wyglądał dokładnie tak samo jak obraz pierwotny - w czasie procesu kompresja-dekompresja nie jest tracona żadna informacja. Założenie to istotnie ogranicza możliwość uzyskania wysokiej kompresji. W praktyce, metody bezstratne pozwalają uzyskiwać stopnie kompresji (stosunek wymaganej pojemności pamięci przed kompresją do wymaganej pojemności po kompresji) rzędu kilku.

W drugim podejściu do kompresji dopuszcza się pewną utratę informacji w procesie kompresja-dekompresja obrazu. Mówi się wtedy o kompresji stratnej. W tym przypadku można uzyskiwać wysokie stopnie kompresji rzędu kilkudziesięciu. W metodach realizujących kompresję stratną z reguły dąży się do usuwania informacji mających stosunkowo małe znaczenie dla interpretacji całego obrazu, a więc dąży się do usuwania mało istotnych szczegółów.

Dalej omówimy przykładowe metody kompresji bezstratnej i stratnej.

Bodaj najprostszą metodą kompresji bezstratnej jest metoda kodowania ciągów znana pod nazwą metoda RLE. Istota tej metody polega na wyszukiwaniu ciągów identycznych elementów i zapamiętywaniu wartości tych elementów i liczby ich powtórzeń. Załóżmy, że piksele w obrazie monochromatycznym (z odcieniami szarości) są reprezentowane za pomocą bajtów i że pewien ciąg pikseli w obrazie jest jak na rysunku XV.1a. Ten ciąg można zapisać krócej, zgodnie z podaną zasadą, tak jak na Rys. XV.1b. W każdej parze liczb pierwsza oznacza liczbę powtórzeń a druga wartość piksela. Oczywiście mając skompresowany ciąg i pamiętając zasadę kompresji można łatwo dokonać dekompresji i odtworzyć dokładnie pierwotny ciąg pikseli.

Rys. XV.1. Przykład kompresji metodą RLE. a) Informacja przed kompresją, b) informacja po kompresji

Można zauważyć, że skuteczność kompresji jest duża wtedy, gdy występują długie ciągi takich samych wartości. Jeżeli jednak pojawiają się pojedyncze wartości, to zamiast zysku może wystąpić strata. (W niektórych implementacjach stosuje się rozwiązania zwiększające efektywność w takich przypadkach.) Najczęściej, w konkretnych implementacjach, kompresji RLE poddawane są poszczególne wiersze obrazu. Nie jest to jednak regułą. Można spotkać rozwiązania, w których kodowane są kolumny obrazu albo ciągi pikseli wybieranych metodą ZigZag (por. Rys. XV.4).

Zwróćmy uwagę na pewien problem związany z kodowaniem obrazów barwnych. Jeżeli każdy piksel jest reprezentowany za pomocą trzech składowych RGB, to obraz może być zapisany jako ciąg trójek RGB reprezentujących kolejne piksele albo za pomocą trzech ciągów zawierających odpowiednio tylko składowe R albo tylko składowe B albo tylko składowe C kolejnych pikseli (por. rysunek XV.2). Można zauważyć, że w tym drugim przypadku efektywność kompresji może być większa, co wynika stąd, że szansa na pojawianie się dłuższych ciągów identycznych wartości jest większa w obrębie ciągu tych samych składowych (tworzących tak zwane płaszczyzny odpowiednio R, G i B).

Rys. XV.2. Wpływ uporządkowania danych na efektywność kompresji. a) Uporządkowanie pikselowe, b) uporządkowanie według składowych barwy

Ogólnie metoda kompresji RLE pozwala uzyskiwać stopnie kompresji na poziomie 2 : 1, 3 : 1. Oczywiście stopień kompresji zależy od konkretnego obrazu - dla jednych obrazów można uzyskać większy stopień kompresji, dla innych mniejszy. Dodajmy, że jest to cecha charakterystyczna każdej metody kompresji.

Spośród innych metod kompresji bezstratnych często stosowanych w praktyce należy wymienić metodę Huffmana oraz metodę LZW. Istotą metody Huffmana jest to, że stosuje się kody o zmiennej długości. Pikselom, które występują częściej w danym obrazie przyporządkowuje się krótsze kody. Z kolei metoda LZW jest metodą słownikową. Istota metody polega na tym, żeby możliwie najdłuższym ciągom powtarzających się wartości pikseli przypisywać odpowiednie kody. Metoda LZW jest objęta patentem (natomiast wcześniejsza wersja metody LZ77 nie jest objęta patentem).

Jedną z najczęściej stosowanych metod kompresji stratnych jest metoda JPEG. Ze względu na złożoność metody ograniczymy się do przedstawienia ogólnej koncepcji tej metody. Na początku obraz dzielony jest na podobrazy (bloki) o rozmiarach 8x8 pikseli. Procesowi kompresji jest poddawany każdy blok niezależnie. Proces ten obejmuje cztery kroki pokazane na rysunku XV.3.

Rys. XV.3. Schemat blokowy metody kompresji JPEG

W pierwszym kroku wykonuje się konwersję z modelu RGB do modelu YCrCb. Występuje tu pierwsza kompresja, bowiem o ile w modelu RGB przeznacza się 24 bity na piksel, to w modelu YCrCb tylko 16 (8 bitów na składową luminancji Y i po 4 bity na składowe niosące informację o barwie - wykorzystuje się tu fakt, iż oko człowieka jest bardziej czułe na zmiany jasności niż na zmiany barwy). Dalsze kroki są realizowane niezależnie dla składowych Y,Cr,Cb.

Tablica wartości Y o rozmiarze 8´ 8 poddawana jest transformacie kosinusowej i w efekcie uzyskuje się nowy zestaw 64 liczb - współczynników z rozwinięcia kosinusowego. Wykorzystuje się tu następującą zależność

,

gdzie syx są to oryginalne dane z tablicy o współrzędnych yx a suv są to współczynniki uzyskane w wyniku transformacji kosinusowej, zapisywane w tablicy o współrzędnych uv. Współczynniki Cu i Cv s¹ równe ½ gdy u,v = 0 i równe 1 w przeciwnym przypadku.

W kolejnym kroku wykonywana jest tak zwana kwantyzacja. Jej celem jest zamienienie możliwie dużej liczby współczynników transformaty na zera. Generalnie chodzi o to, że wśród współczynników transformaty są takie, które niosą dużą ilość informacji o obrazie i takie, które niosą niewielką ilość informacji o obrazie. Te ostatnie można wyeliminować bez większej straty dla ogólnej jakości obrazu - ich wpływ jest na tyle mały, że obserwator może nie zauważyć zmian w obrazie związanych z ich usunięciem.

Kwantyzację realizuje się w następujący sposób. Korzystamy z pomocniczej tablicy 8´ 8, zawierającej odpowiednio dobrane wartości. Kolejno dzieli się przez siebie współczynniki z tablicy uzyskanej w wyniku transformacji przez odpowiednie współczynniki z pomocniczej tablicy (to znaczy pierwszy element tablicy współczynników transformacji dzielimy przez pierwszy element pomocniczej tablicy, potem to samo wykonujemy w stosunku do drugich współczynników itd.) i wyniki zaokrągla się w dół. Elementy pomocniczej tablicy są tak dobrane, żeby w wynikowej tablicy pojawiała się duża liczba zer. Są one z reguły zgrupowane w prawej dolnej części wynikowej tablicy. Dzięki operacji kwantyzacji uzyskuje się kompresję informacji, przy czym jest to operacja nieodwracalna.

Tablica uzyskana w wyniku kwantyzacji jest w ostatnim kroku poddawana kodowaniu metodą RLE i następnie metodą Huffmana. Kodowaniu metodą RLE poddawany jest ciąg wartości z wynikowej tablicy przeglądany w porządku ZigZag jak na rysunku XV.4. Taki porządek jest przyjęty ze względu na to, że pozwala uzyskać długi ciąg zer zgrupowanych w prawej dolnej części tablicy. Zauważmy, że do ciągu nie wchodzi element z lewego górnego rogu oznaczony jako DC. Jest on kodowany wspólnie z odpowiednimi elementami dla innych bloków obrazu 8x8, z których składa się cały obraz poddawany kompresji.

Rys. XV.4. Przeglądanie elementów tablicy w porządku ZigZag

Przy dekompresji obrazu postępuje się w odwrotnej kolejności jak przy kompresji. Najpierw ma miejsce odkodowanie ciągu właściwe dla metody Huffmana, a potem dla metody RLE. Odtworzona tablica jest poddawana odwrotnej operacji jak przy kwantyzacji (z wykorzystaniem tej samej pomocniczej tablicy), z tym, że oczywiście nie można odtworzyć wyzerowanych współczynników. Z kolei odzyskana tablica współczynników transformaty kosinusowej jest poddawana odwrotnej transformacji kosinusowej. Na końcu następuje konwersja z modelu YCrCb do modelu RGB.

Kompresja metodą JPEG pozwala uzyskiwać stopnie kompresji 20:1 - 30:1 przy praktycznie niezauważalnych zniekształceniach obrazu odzyskiwanego po dekompresji. Przy większych stopniach kompresji zmiany takie są już zauważalne.

Na zakończenie dodajmy, że omówione wyżej metody kompresji są stosowane do kompresji pojedynczych obrazów. Przy kompresji sekwencji obrazów są stosowane inne metody, na przykład takie jak w standardach MPEG.


 następny punkt »