Podręcznik

W marcu 1997 rozpoczęto prace nad nowym standardem kompresji obrazów JPEG2000. Obecnie prowadzone są prace (niektóre już zakończono) nad następującymi częściami JPEG2000:

• część 1: podstawowy system kompresji obrazów pojedynczych;
• część 2: rozszerzenia (dodatkowe opcje systemu, m.in. możliwość definiowania własnych transformacji falkowych i kolorów, inny sposób kodowania ROI, nowe algorytmy kwantyzacji itp.);
• część 3: algorytm kompresji sekwencji obrazów (Motion JPEG 2000);
• część 4: testy zgodności (conformance);
• część 5: oprogramowanie referencyjne, tj. biblioteki w Javie (JJ2000) oraz C (JasPer);
• część 6: format pliku dla danych złożonych (obrazowanie dokumentów, artykułów prasowych itp.);
• część 7: (prace nad tą częścią zostały zaniechane);
• część 8: JPSEC, bezpieczeństwo danych;
• część 9: JPIP, interaktywne protokoły transmisji i API;
• 10: JP3D, obrazowanie 3D;
• 11: JPWL, aplikacje bezprzewodowe.

Standard JPEG2000 umożliwia kompresję obrazów o niemal dowolnej reprezentacji oryginalnej, tzn. możliwa jest duża liczba komponentów oraz bitów na próbkę w niemal nieograniczonej przestrzeni obrazu, a także różna orientacja dziedziny obrazu względem układu odniesienia. Liczba komponentów jest ograniczona do 214 (16384); natomiast ich maksymalna szerokość i wysokość to 232-1 próbki (przekracza 4 miliardy próbek). Liczba bitów na próbkę jest ograniczona do 38 bitów (ponad 4 bajty).
    
Nowy paradygmat

Zdolność uzyskiwania możliwie krótkiej reprezentacji danych obrazowych była dotychczas jednym z najważniejszych kryteriów decydujących o przydatności techniki kompresji. Przy obecnym rozwoju nowych technologii multimedialnych równie istotne okazały się nowe cechy funkcjonalne systemów kompresji-dekompresji, powodujące dużą użyteczność algorytmów w znacznie szerszym obszarze zastosowań. Wiele postulatów stawianych przez rosnący krąg potencjalnych użytkowników jest praktycznie nie do zrealizowania za pomocą funkcjonujących dotąd standardów kompresji obrazów, czyli przede wszystkim JPEG-a. Schemat kompresji wynikający z klasycznego paradygmatu definiuje zbiór dostępnych opcji kodera, które pozwalają z jednej strony dopasować algorytm kompresji do własności strumienia wejściowego (dynamiki danych, przestrzeni kolorów itp.), z drugiej zaś - dobrać parametry procesu kompresji (sposób kwantyzacji - np. tablice, szerokość przedziałów, czy kodowania - np. sekwencyjny, progresywny itd.). Po stronie dekodera standard nie dopuszcza żadnych możliwości wyboru sposobu odtwarzania strumienia - obowiązuje ustalony w koderze porządek i sposób rekonstrukcji, a strumień zakodowany jest rekonstruowany w całości. Realizację paradygmatu schematu kompresji ze standardu JPEG przedstawiono na rys. 1.10a).

Koncepcja nowego paradygmatu kompresji (rys. 1.10b)) została sformułowana w okresie intensywnych prac badawczych nad realizacją standardu JPEG2000. W porównaniu z paradygmatem z JPEG-a następuje znaczne rozszerzenie możliwości kształtowania skompresowanego strumienia danych (np. wprowadzanie regionów zainteresowań - ROI, mechanizmu podziału oryginału na części - ang. tile) oraz postaci dekompresowanej reprezentacji oryginału (np. sterowanie rozdzielczością, jakością obrazu, bitowym rozmiarem reprezentacji informacji rekonstruowanej).

Współczesny standard kompresji powinien być tworzony z myślą o szerokiej gamie zastosowań, takich jak Internet, różnorodne aplikacje multimedialne, obrazowanie medyczne, kolorowy fax, drukowanie, skanowanie, cyfrowa fotografia, zdalne sterowanie, przenośna telefonia nowej generacji, biblioteka cyfrowa oraz e-komercja (elektroniczna komercja, głównie z wykorzystaniem Internetu). Nowy system kodowania musi więc być skuteczny w przypadku różnych typów obrazów (binarne, ze skalą szarości, kolorowe, wieloskładnikowe) o odmiennej charakterystyce (obrazy naturalne, medyczne, sztuczne obrazy grafiki komputerowej, naukowe z różnych eksperymentów, z tekstem itd.). Ponadto, powinien zapewniać efektywną współpracę z różnymi technologiami obrazowania (akwizycji/generacji/ wykorzystywania obrazów): z transmisją w czasie rzeczywistym, z archiwizacją, gromadzeniem bazodanowym (np. w cyfrowej bibliotece), w strukturze klient/serwer, z ograniczonym rozmiarem bufora czy limitowaną szerokością pasma itp. Wymagania odnośnie nowego standardu kompresji najlepiej charakteryzują stwierdzenia z 'JPEG2000 call for proposals' z marca 1997 r.: "poszukiwany jest standard dla tych obszarów, gdzie aktualne standardy nie potrafią zagwarantować wysokiej jakości lub wydajności, standard zapewniający nowe możliwości na rynkach, które dotąd nie wykorzystywały technologii kompresji i dający otwarte narzędzia systemowe dla aplikacji obrazowych."

Użyteczność falek w modelowaniu i realizacji Użyteczność analizy falkowej leży głównie w możliwościach skutecznego modelowania przy ich pomocy przestrzenno-częstotliwościowej charakterystyki obrazów naturalnych. Typowa postać obrazu jest mieszaniną obszarów o znacznych rozmiarach z treścią niskoczęstotliwościową (wolno zmieniające się tło sceny naturalnej, np. niebo, ściana w pokoju, czy też jednostajne, lekko zaszumione tło w obrazie medycznym), małych obszarów ze znaczącą treścią wysokoczęstotliwościową (silne krawędzie o dużych gradientach, wyraźne, drobne struktury) oraz obszarów (obiektów) pokrytych teksturami. W bazie falkowej znajdują się elementy o skończonym nośniku, które mają dobrą rozdzielczość częstotliwościową (przy słabszej przestrzennej) w zakresie częstotliwości niskich, czyli dobrze charakteryzują tło i wolnozmienne tekstury, a także elementy z dobrą rozdzielczością przestrzenną (przy słabszej częstotliwościowej) w zakresie częstotliwości wysokich, co daje dobrą lokalizację krawędzi w podpasmach dokładnej skali. Taka korelacja cech bazy z własnościami obrazów naturalnych prowadzi do silnej koncentracji energii sygnału w niewielkiej liczbie współczynników, przy czym większość informacji obrazu znajduje się w niewielkim obszarze podpasma najniższych częstotliwości dziedziny falkowej dekompozycji. Pozostała część informacji zawarta jest w wartościach współczynników rozrzuconych w niewielkich grupach wokół przestrzennej pozycji silnych krawędzi w obrazach uzupełniających różnych skal. Zaś zdecydowana większość współczynników ma wartości bliskie zeru i może być zupełnie pominięta lub silnie kwantowana w procesie stratnej kompresji, bez znaczącego wpływu na jakość rekonstrukcji. Wyższość wielorozdzielczej analizy falkowej w stosunku do STFT (ang. Short Time Fourier Transform) lub blokowej DCT (ang. discrete cosine transform) jest tutaj bezdyskusyjna, ponieważ lepiej, w sposób naturalny opisuje rzeczywisty sygnał.

Rys.1.10  Porównanie paradygmatu schematu kompresji: a) z podstawowej wersji standardu JPEG; b) z nowego standardu JPEG2000 - część I, opartego na falkowej technice kompresji; SNR (ang. Signal to Noise Ratio).

Dodatkową zaletą dekompozycji falkowej jest jej podatność na rozwiązania adaptacyjne, dotyczące zarówno stosowania bazy falkowej o nieskończonej ilości możliwych postaci, jak też samego schematu dekompozycji i podziału na podpasma. Adaptacyjną postać transformacji można lepiej dopasować do własności konkretnego obrazu czy grupy obrazów. Gładkość funkcji bazowych, ich rozmiar, symetryczność, decydują o możliwie najlepszym przybliżeniu lokalnych własności obrazu, a ich właściwy wybór wpływa znacząco na skuteczność kompresji. Zagadnienie doboru optymalnej bazy falkowej w kompresji konkretnego obrazu nie jest właściwie rozwiązywalne w sposób jednoznaczny, ale istnieje cały zbiór przesłanek (w postaci wiedzy a priori) pozwalających dobrać jądro przekształcenia w sposób prawie optymalny.

Klasyczny schemat wielorozdzielczej dekompozycji Mallata ze strukturą logarytmiczną dobrze opisuje wspomniane własności typowych obrazów z wykładniczo opadającym widmem gęstości mocy. Dla obrazów o nieco innej charakterystyce, zawierających dużą ilość informacji w zakresie wysokoczęstotliwościowym (np. rozległe obszary z teksturą prążkową: czarne pasy na białym tle) bardziej efektywną dekompozycję otrzymuje się za pomocą bazy pozwalającej uzyskać dobrą lokalizację w dziedzinie częstotliwości podpasm wysokoczęstotliwościowych (ze względu dobre zróżnicowanie zgromadzonej tam dużej ilości informacji). Konieczne jest do tego narzędzie transformacji falkowej, pozwalające dobrać schemat dekompozycji w zależności od cech obrazu (źródła informacji). Choć teoretycznie można zbudować dowolną liczbę schematów dekompozycji, rozwiązując zagadnienie optymalizacji schematu dekompozycji w każdym konkretnym przypadku, to bardziej praktycznym jest rozwiązanie, gdzie można zbudować skończoną bibliotekę reprezentatywnych transformacji, dobierając z biblioteki, dzięki szybkiemu algorytmowi, optymalną postać transformacji dla konkretnego obrazu. Takim narzędziem jest dekompozycja za pomocą pakietu falek (wavelet packets), zwana też, bardziej algorytmicznie, schematem wyboru najlepszej bazy (best basis). Pakiety falek stanowią dużą bibliotekę transformacji silnie zróżnicowaną pod kątem ich własności dekompozycji przestrzenno-częstotliwościowej, ze zdolnością szybkiego przeszukiwania. Funkcje bazowe pakietu falek mają własności falek klasycznych, przy czym wzbogacone są często o większą liczbę oscylacji. Wykorzystując pakiet falek, można dostosować postać transformacji do praktycznie dowolnego spektrum sygnału - zobacz rys.1.11. Implementacja dekompozycji z pakietem falek wymaga dodatkowych nakładów obliczeniowych, głównie na proces wyszukania optymalnego schematu transformacji dla danego obrazu, a także przesłania niewielkiej informacji dodatkowej do dekodera. Kosztem większego obciążenia obliczeniowego można niemal dowolnie 'blisko' dopasować postać transformacji do sygnału, np. wprowadzając zmienną w czasie segmentację, pozwalając na ewolucję pakietu falek wraz z sygnałem (silnie niestacjonarnym). Z drugiej strony, procedurę takiej transformacji można znacznie uprościć, dobierając ustaloną postać dekompozycji pakietu falek dla danego typu obrazów, jak to ma miejsce np. w standardzie FBI do kompresji obrazów z odciskami palców.

Rys. 1.11 Podział dziedziny czas (przestrzeń)-częstotliwość w różnych schematach dekompozycji: a) dekompozycja równomierna, uzyskana za pomocą pakietu falek lub też STFT, b) klasyczna dekompozycja falkowa Mallata, c) dekompozycja pakietu falek, gdzie szerokość podpasm nie zmienia się ani równomiernie ani logarytmicznie, d) odwrócona dekompozycja falkowa, uzyskana z wykorzystaniem pakietu falek.

Ponadto, atrakcyjną cechą falkowej reprezentacji obrazu, od skal mało dokładnych (tj. skal dużych), z silną koncentracją informacji (energii) na bit danych, do małych skal bardzo dokładnych (z małym przyrostem informacji na bit), jest jej naturalna progresywność. Reprezentacja ta umożliwia sterowanie kolejnością i rodzajem przekazywanej informacji, przy czym niewielkim kosztem można uzyskać strumień danych (prawie) optymalny w sensie R-D.

Kompresja konstruowana na podstawie dekompozycji falkowej jakby naturalnie odpowiada na większość wymagań stawianych w nowym paradygmacie kompresji, pozwalając je realizować w szybkich algorytmach obliczeniowych tak, że praca koderów w systemach czasu rzeczywistego jest możliwa.

Metoda kodowania

Na rys. 1.12 przedstawiono schemat blokowy algorytmu kompresji zaproponowany w standardzie. Dokładniej poszczególne operacje na danych pokazano na rys. 1.13.

Rys. 12  Diagram ogólnego algorytmu kompresji według JPEG2000.

Rys. 1.13  Poglądowy zarys struktur danych wykorzystywanych w kolejnych krokach podstawowego algorytmu kodowania JPEG2000.

Pierwszym etapem kompresji jest formatowanie danych polegające na umiejscowieniu poszczególnych komponentów obrazu na siatce odniesienia (reference grid) oraz podziale ich na części (tile). Zastosowanie siatki umożliwia dokonywanie prostych operacji na obrazie skompresowanym (m.in. obrót o wielokrotność 90 stopni) oraz kompresję obrazów o komponentach o różnej wielkości. Podział obrazu na kafelki ma na celu zmniejszenie zapotrzebowania na pamięć, umożliwia przyspieszenie kodowania (dzięki możliwości równoczesnego kodowania wielu części obrazu) oraz daje dostęp do fragmentów obrazu bez konieczności dekompresji całości (należy zaznaczyć, że taka lokalna dekompresja jest możliwa także w inny sposób). Po podziale obrazu na części każda z nich jest dalej przetwarzane niezależnie.

Po podziale każda część jest poddawany transformacji kolorów. W cz. I standardu zastosowano transformację YCbCr (YCC) w wersji odwracalnej ($YCC_R$) oraz nieodwracalnej ($YCC_I$). Transformacja może być zastosowana tylko w przypadku, kiedy obraz zawiera co najmniej 3 komponenty, przy czym 3 pierwsze muszą mieć taką samą wielkość. Po transformacji kolorów wszystkie komponenty są dalej przetwarzane niezależnie. Cz. II standardu umożliwia dodanie innych (własnych) transformacji przestrzeni kolorów.