Podręcznik

2.2. Krótka historia rozwoju

Pierwowzory współczesnych metod kodowania można dostrzec już w podejmowanych od wieków próbach kształtowania różnych form oszczędnego opisu bogatych w formie treści (pojęć). W każdej społeczności podejmowano próby  przekazania informacji, ostrzegając np. przed zagrożeniem za pomocą sygnałów dymnych czy dźwiękowych.  Aby wyrazić emocje, utrwalić doświadczenia posługiwano się malowidłami, rysowano znaki na ciele, nacinano skórę. Wymyślono języki, by łatwiej się porozumieć. Słowom przypisano określone znaczenie, intensywnie gestykulowano, powstały różne formy mowy niewerbalnej, itp. 

Dopiero jednak datowane na przełom lat czterdziestych i pięćdziesiątych prace Claude Shannona, jednego z największych naukowców XX wieku według m.in. Sloane'a, zawierały sformalizowaną podstawę służącą opracowaniu metod kompresji, dając początek intelektualnej dyscyplinie kompresji. Stanowią one swego rodzaju akt założycielski w rozwoju współczesnych metod kompresji.

Sformułowane przez Shannona podstawy teorii informacji to kanał transmisji, probabilistyczne rozumienie informacji (zmienna losowa i łańcuch losowy opisujące źródło z pełną informacją statystyczną), entropia jako miara informacji, przyczyny nadmiarowości (redundancji), modele źródeł informacji, teoria zniekształceń źródeł informacji itd. Shannon przyczynił się także do powstania efektywnego algorytmu kodowania wykorzystującego analizę statystyczną sekwencji danych kompresowanych, znanego obecnie jako metoda Shannona-Fano.

Kolejnym istotnym wydarzeniem było opracowanie przez D.A. Huffmana optymalnej metody kodowania ciągu danych poprzez przyporządkowanie każdemu symbolowi alfabetu źródła modelującego dane wejściowe oddzielnego słowa kodowego o zmiennej długości (opublikowanie w 1952r.). Długość słów (w bitach) jest w przybliżeniu odwrotnie proporcjonalna do prawdopodobieństwa wystąpienia danego symbolu na wejściu kodera. Metoda jest wykorzystywana przez dziesiątki lat w różnych wersjach i odmianach jako uzupełnienie wstępnej dekompozycji oraz modelowania pośredniej reprezentacji danych (jak np. w standardzie JPEG). 

W latach sześćdziesiątych i siedemdziesiątych opracowano wiele algorytmów kompresji stratnej polegających na wyznaczeniu i zachowaniu właściwości danych, które są decydujące w ich interpretacji i wykorzystaniu (np. tekstur i konturów w obrazach). Zwiększenie efektywności kompresji uzyskuje się kosztem znaczącej redukcji tła nie mającego wartości użytkowych. Metody te zwane ekstrakcyjnymi były stosowane głównie do kompresji obrazów medycznych. Określano w obrazie wszelką informację istotną diagnostycznie kodując odpowiednie regiony zainteresowań w sposób bezstratny, zaś pozostałe obszary, nieistotne w opinii specjalistów, kompresowano stratnie z dużym poziomem zniekształceń. 

W latach 1977 i 1978 zostały opublikowane przez Lempela i Ziva dwa algorytmy bezstratnej kompresji, które stały się podstawą nowej grupy metod tzw. kodowania słownikowego. Metody te charakteryzuje faza modelowania dyskretnego (bazującego na identyczności ciągów symboli, bez modeli probabilistycznych), polegająca na wyznaczaniu słownika fraz powtarzających się  ciągów danych. Słownik jest wtedy podstawową strukturą wykorzystywaną w procesie tworzenia reprezentacji kodowej. Jest ona konkatenacją  kolejnych wskaźników pozycji słownika, które odpowiadają sukcesywnie kodowanym ciągom danych wejściowych. Od pierwszych liter nazwisk autorów oraz daty publikacji algorytmy te nazwano odpowiednio LZ77 i  LZ78. Modyfikacje tych algorytmów, m.in. LZSS i LZW uzyskały duży walor użytkowy i znalazły zastosowanie w licznych archiwizerach, m.in w: Unix_Compress, ARC, PKZIP, LHA (LHarc), ARJ, RAR, 7-Zip, WinZip, PKArc, w formatach obrazów GIF i PNG, w metodzie Deflate.

W latach osiemdziesiątych XX wieku nastąpił intensywny rozwój technik kompresji. Na uwagę zasługują prace nad coraz doskonalszymi modelami adaptacyjnymi, a także rozwój metod kodowania transformacyjnego. Podejmowano próby wykorzystania różnych transformacji, np. Fouriera, Walsha-Hadamarda, sinusowej, Karhunena-Loevego, do upakowania energii sygnału w zredukowanej dziedzinie przekształcenia. Najlepsze rezultaty uzyskano dla dyskretnej transformaty kosinusowej DCT (discrete cosine transform), co znalazło odbicie w opracowanych na początku lat dziewięćdziesiątych standardach kompresji obrazów cyfrowych wielopoziomowych -- JPEG i MPEG. Na rys. 2.1 przedstawiono schematyczne porównanie funkcji bazowych DCT i transformacji Fouriera, które ukazuje zaletę ciągłości kosinusowych funkcji bazowych przy granicach przedziału określoności, co zapewnia wyższą jakość rekonstruowanego po kwantyzacji sygnału rozwiniętego w przedziałach przyległych.  

Rys. 2.1 Porównanie baz przekształceń DCT i Fouriera w przypadku przedziałowego liczenia transformacji. Ciągłość funkcji DCT na granicach przedziałów (widoczna na rysunkach powyżej) powoduje dokładniejszą rekonstrukcję sygnału w przedziale (rysunki poniżej).

Ponadto opracowano wydajne implementacje kodowania arytmetycznego, najefektywniejszego z kodów binarnych (stale optymalizowane szczególnie w zakresie modelowania, np. w ramach standardów JPEG2000, MPEG-4, JBIG-2. Kodery arytmetyczne wykorzystują kontekstowe modele zależności danych ograniczone niekiedy do alfabetu binarnego, uproszczone koncepcje obliczeń znacznie zmniejszające złożoność obliczeniową.   

Przełom lat osiemdziesiątych i początek lat dziewięćdziesiątych to doskonalenie dwóch nowatorskich metod kompresji obrazów, bazujących na dość złożonym aparacie matematycznym. Pierwsza to metoda wykorzystująca przekształcenia fraktalne, pozwalająca uzyskać dużą skuteczność kompresji szczególnie dla obrazów naturalnych o niebogatej treści. Istotne zasługi w rozwoju tej techniki położyli między innymi Barnsley, Jacquin, Hurd. Drugą metodą, z którą związane są takie nazwiska jak: Mallat, Daubechies, Villasenor, Vetterli, Strang i wiele innych, jest kompresja na bazie wieloskalowych przekształceń falkowych (wavelet transform). Kompresja falkowa rozszerza znaną wcześniej koncepcję kodowania pasmowego (subband coding). Kodowanie falkowe, realizowane także w wersji bezstratnej za pomocą transformacji całkowitoliczbowych, zapewnia dużą efektywność kompresji sygnałów niestacjonarnych, w tym obrazów. Ma szereg zalet, takich jak: naturalnie uzyskiwany hierarchiczny opis informacji w przestrzeni wielorozdzielczej, możliwość łatwej i szybkiej adaptacji metody kodowania do lokalnej charakterystyki danych w różnej skali, z zachowaniem zależności z przestrzeni oryginalnej. Pozwala to zwiększyć efektywność kompresji obrazów do wartości często niemożliwych do uzyskania za pomocą innych metod.

W drugiej połowie lat dziewięćdziesiątych rośnie znaczenie metod kompresji obrazów statycznych (pojedynczych), które wykorzystują przekształcenia falkowe do dekompozycji danych źródłowych w różnych zastosowaniach. Przełomowa okazała się tutaj praca J.M. Shapiro dotycząca algorytmu EZW (embedded zerotree wavelet), ukazująca efektywny sposób kodowania współczynników falkowych, znacznie zwiększający wydajność kompresji w stosunku do metod bazujących na DCT. W setkach publikacji przedstawiono coraz doskonalsze metody dekompozycji, kwantyzacji i kodowania współczynników falkowych, których efektem było opracowanie nowego standardu kompresji obrazów JPEG2000. Standard ten wykorzystuje koncepcję falkowej dekompozycji obrazów, elastyczny sposób kształtowania strumienia danych kodowanych w zależności od potrzeb użytkownika, dokładną kontrolę długości tego strumienia i optymalizację stopnia zniekształceń, metodę kompresji stratnej-do-bezstratnej (lossy-to-lossless) umożliwiającą efektywną kompresję stratną, sukcesywnie przechodzącą w bezstratną po dołączeniu wszystkich informacji do sekwencji wyjściowej kodera i wiele innych. Koder według JPEG2000 pozwala w wielu przypadkach zwiększyć blisko dwukrotnie  efektywność kompresji w stosunku do kodera standardu JPEG. Kolejne części standardu JPEG2000 dotyczą różnych obszarów zastosowań (m.in. transmisji bezprzewodowej, interaktywnych protokołów wymiany informacji obrazowej, zabezpieczeń praw własności w strumieniu kodowym, kina domowego i telewizji cyfrowej, indeksowania i opisu za pomocą deskryptorów obrazów).

Zastosowanie metod falkowych do kompresji wideo napotyka na pewne ograniczenia. Stosowane obecnie kodeki wykorzystują najczęściej transformację DCT z blokową estymacją i kompensacją ruchu. Do tej grupy należą   doskonalone od początku lat dziewięćdziesiątych standardy multimedialne: H.261, MPEG-1, MPEG-2, H.263, H.263+, aż po H.264 (MPEG-4, część 10). Ponadto, prace nad algorytmami kompresji drugiej generacji (z obiektową analizą scen i bardziej elastyczną kompensacją ruchu) doprowadziły do opracowania nowego kodeka wideo w ramach MPEG-4, część II. W kolejnych przedstawicielach rodziny standardów MPEG skoncentrowano się bardziej na zagadnieniu indeksowania danych multimedialnych, opracowaniu deskryptorów opisujących treść i formę danych (MPEG-7). W roku 2000 rozpoczęto prace nad standardem MPEG-21, który jest ''wielkim obrazem'' ogromnej infrastruktury wymiany i konsumpcji treści multimedialnych, uwzględniającym mnogość istniejących już i rozwijanych narzędzi  reprezentowania danych, określając ich wzajemne relacje i porządkując całą przestrzeń multimediów. Aktualny stan prac nad standardami JPEG i MPEG można śledzić na stronach odpowiednio http://www.jpeg.org/ i http://www.mpeg.org/.