Podręcznik

Teoria informacji zajmuje się kodowaniem źródłowym i kanałowym bazując na statystycznych właściwościach źródeł informacji, których modele nie uwzględniają  aspektu znaczeniowego ze względu na pominięcie aspektu użyteczności. Można przyjąć, że informacja rozumiana jest wtedy jako wiadomość W, tj. ciąg symboli nad ustalonym alfabetem, z przypisaną wartością semantyczną $\Sigma_{\cdot}(W)$ u nadawcy N zgodną z wartością semantyczną u odbiorcy O:

Przy takiej koncepcji informacja to para $(W,\Sigma_N(W))$, przy możliwej do pominięcia, bo zgodnej, funkcji semantycznej, przy przekazie niezależnym od wymagań odbiorcy. 

Ze względu na postać, w jakiej wyrażona jest informacja, można wyróżnić informację ze zbiorem ziarnistym (zbiór o skończonej liczbie elementów) oraz informację ze zbiorem ciągłym (obok jednej informacji dowolnie blisko można znaleźć inne informacje). W kodowaniu danych cyfrowych użyteczne jest pojęcie informacji ze zbiorem ziarnistym. Można dla niej określić tzw. ciągi informacji, które są ciągiem symboli ze zbioru informacji elementarnych (alfabetu), pojawiających się w określonej kolejności, stanowiącej istotę informacji. Przykładowo, źródło opisane alfabetem $A_S=~\{a,b,c\}$generuje ciąg informacji: ${\textbf s}(A_S)=~(a,a,c,a,b,b,b,c,c,a,c,b,\ldots)$, tj. sekwencję symboli nad alfabetem $A$.

W teorii informacji istnieją dwa zasadnicze cele wykorzystania modeli źródeł informacji: 

•  wyznaczanie fundamentalnych, teoretycznych wartości granicznych wydajności określonej klasy kodów w odniesieniu do ustalonych modeli źródeł informacji,
• opracowanie skutecznych kodów źródeł informacji wiernie przybliżających rzeczywiste strumienie informacji.

Źródło informacji jest matematycznym modelem bytu fizycznego, który w sposób losowy generuje (dostarcza, emituje) sukcesywnie symbole. Przyjmując stochastyczny model źródła informacji dobrze opisujący niepewność zakładamy, iż informacja jest realizacją pewnej zmiennej losowej (procesu losowego czy dokładniej łańcucha (Łańcuchem stochastycznym nazwiemy proces stochastyczny z argumentem ziarnistym) o określonych właściwościach statystycznych. Model informacji, w którym zakładamy, że ma on charakter realizacji zmiennej, łańcucha lub procesu stochastycznego o znanych właściwościach statystycznych (istnieją i są znane rozkłady prawdopodobieństwa informacji), nazywany jest modelem z pełną informacją statystyczną lub krócej - modelem probabilistycznym. 

Ze względów praktycznych szczególnie interesujące są probabilistyczne modele źródeł informacji, a analiza została ograniczona do dyskretnych źródeł informacji. Dla takich modeli obowiązują twierdzenia graniczne, w tym prawa wielkich liczb, z których wynika, że przy dostatecznie dużej liczbie niezależnych obserwacji częstości występowania określonych postaci informacji będą zbliżone do prawdopodobieństw ich występowania. Częstościowe określanie prawdopodobieństw jest tym dokładniejsze, im liczniejsze zbiory są podstawą wyznaczenia prawdopodobieństw.

W kontekście implementacji metod kodowania wygodniej jest mówić o wagach symboli. Jest to liczba wystąpień danego symbolu wogóle lub też w określonym kontekście. Podzielona przez liczbę wystąpień wszystkich symboli jest miarą częstości występowania symbolu, przybliżeniem (estymacją) prawdopodobieństwa.

Proces generacji informacji modelowany za pomocą źródła informacji $S$ polega na dostarczaniu przez źródło sekwencji (ciągu) symboli $\mathbf{s}=(s_1,s_2,\ldots)$) wybranych ze skończonego alfabetu $A_{S}$(czyli $s_{i}\in A_{S}$) według pewnych reguł opisanych zmienną losową o wartościach $s$. Bardziej ogólnie probabilistycznym modelem ciągu informacji elementarnych jest sekwencja zmiennych losowych $(S_1,S_2,\ldots)$  traktowana jako proces stochastyczny (dokładniej łańcuch). Właściwości źródła określone są wtedy przez parametry procesu stochastycznego (prawdopodobieństwa łączne, charakterystyka stacjonarności itd.). Stacjonarność źródła w naszych rozważaniach jest rozumiana w kontekście procesu, którego realizacją jest dana informacja. Rozważmy przestrzeń symboli (dyskretnych próbek) generowanych ze źródła jako zbiór wszystkich możliwych sekwencji symboli wraz z prawdopodobieństwami zdarzeń rozumianych jako występowanie rozmaitych zestawów tych sekwencji. Zdefiniujmy także przesunięcie jako transformację $T$określoną na tej przestrzeni sekwencji źródła, która przekształca daną sekwencję na nową poprzez jej przesunięcie o pojedynczą jednostkę czasu w lewo (jest to modelowanie wpływu czasu na daną sekwencję), czyli  $T(s_{1},s_{2},s_{3},\ldots)=(s_{2},s_{3},s_{4},\ldots)$. Jeśli prawdopodobieństwo dowolnego zdarzenia (zestawu sekwencji) nie ulegnie zmianie poprzez przesunięcie tego zdarzenia, czyli przesunięcie wszystkich sekwencji składających się na to zdarzenie, wtedy transformacja przesunięcia jest zwana niezmienniczą (inwariantną), a proces losowy jest stacjonarny. Teoria stacjonarnych procesów losowych może być więc traktowana jako podzbiór teorii procesów ergodycznych, odnoszącej się do śledzenia zachowania średniej po czasie oraz po próbkach procesów w całej definiowanej przestrzeni.

Warto przypomnieć, że w źródle będącym realizacją procesu ergodycznego każda generowana sekwencja symboli ma te same właściwości statystyczne. Momenty statystyczne procesu, rozkłady prawdopodobieństw itp. wyznaczone z poszczególnych sekwencji zbiegają do określonych postaci granicznych przy zwiększaniu długości sekwencji, niezależnie od wyboru sekwencji. W rzeczywistości nie jest to prawdziwe dla każdej sekwencji procesu ergodycznego, ale zbiór przypadków, dla których jest to fałszywe, występuje z prawdopodobieństwem równym 0. Stąd dla stacjonarnych procesów ergodycznych możliwe jest wyznaczenie parametrów statystycznych (średniej, wariancji, funkcji autokorelacji itp.) na podstawie zarejestrowanej sekwencji danych (symboli, próbek) $\{s_{i}\}_{i=1,2,\ldots}$, co jest wykorzystywane w praktycznych algorytmach kodowania, opartych na przedstawionych poniżej uproszczonych modelach źródeł informacji.

Model bez pamięci - DMS

Najprostszą postacią źródła informacji $S$ jest dyskretne źródło bez pamięci DMS (discrete memoryless source), w którym sukcesywnie emitowane przez źródło symbole są statystycznie niezależne. Źródło DMS jest całkowicie zdefiniowane przez zbiór wszystkich możliwych wartości $s$ zmiennej losowej, tj. zbiór symboli tworzących alfabet $A_{S}=\{a_{1},a_{2},\ldots,a_{n}\}$, oraz zbiór wartości prawdopodobieństw występowania poszczególnych symboli alfabetu: $P_S=\{p_1,p_2,\ldots,p_n\}$, gdzie$\Pr(s=a_{i})=P(a_{i})=p_i$, $p_{i}\geq 0$ i $\sum_{s\in A_S}P(s)=1$.

Można sobie wyobrazić, że źródło o alfabecie $A_{S}$ zamiast pojedynczych symboli generuje bloki $N$ symboli z alfabetu źródła, czyli struktura pojedynczej informacji jest ciągiem $N$ dowolnych symboli źródła. W takim przypadku można zdefiniować nowe źródło $S^{N}$ o $n^{N}$ elementowym alfabecie, zawierającym wszystkie możliwe $N$ - elementowe ciągi symboli. Rozszerzony alfabet takiego źródła jest następujący:$A_{S}^{N}=\underbrace{A_{S}\times A_{S}\times \cdots \times A_{S}}_{N}$, czyli $A_{S}^{N}=\{(a_{i_{1}},a_{i_{2}},\ldots,a_{i_{N}}): \forall_{j\in \{1,\ldots,N\}} a_{i_{j}}\in A_{S}\}=(\mathbf{a}_{1},\mathbf{a}_{2},\ldots,\mathbf{a}_{i},\ldots \mathbf{a}_{n^{N}})$. Prawdopodobieństwo i-tego elementu alfabetu wynosi $P(\mathbf{a}_{i})=P(a_{i_{1}})P(a_{i_{2}})$$\cdots P(a_{i_{N}})$ (mamy do czynienia ze źródłem bez pamięci). Źródło $S^{N}$ jest nazywane rozszerzeniem stopnia $N$ źródła $S$.

Model z pamięcią (warunkowy) - CSM

Jakkolwiek model DMS spełnia założenia prostej, wygodnej w analizie struktury, to jednak w wielu zastosowaniach jest nieprzydatny ze względu na małą zgodność z charakterem opisywanej informacji. Założenie o statystycznej niezależności kolejnych zdarzeń emisji symbolu jest bardzo rzadko spełnione w praktyce. Aby lepiej wyrazić rzeczywistą informację zawartą w zbiorze danych, konstruuje się tzw. model warunkowy źródła - CSM (conditional source model), zwany także modelem z pamięcią w odróżnieniu od modelu DMS. Jest to ogólna postać modelu źródła informacji, którego szczególnym przypadkiem jest DMS, a także często wykorzystywany model źródła Markowa.

Modele źródeł z pamięcią, najczęściej ograniczoną, pozwalają z większą dokładnością przewidzieć pojawienie się poszczególnych symboli alfabetu źródła (strumień danych staje się lepiej określony przez model źródła). Koncepcja pamięci źródła jest realizowana poprzez określenie kontekstu (czasowego), który ma wpływ na prawdopodobieństwo wyemitowania przez źródło konkretnych symboli w danej chwili. W każdej kolejnej chwili czasowej t, po wcześniejszym odebraniu ze źródła sekwencji symboli $\mathbf{s}^{t}=(s_{1},s_{2},\ldots,s_{t})$, można na podstawie \mathbf{s}^{t} (tj. przeszłości) wnioskować o postaci kolejnego oczekiwanego symbolu   poprzez określenie rozkładu prawdopodobieństw warunkowych P(\cdot |\mathbf{s}^{t}).

Zbiór wszystkich dostępnych z przeszłości danych $\mathbf{s}^{t}$ stanowi pełny kontekst wystąpienia symbolu $s_{t+1}$. Kontekst C wykorzystywany w obliczanym rozkładzie $P(\cdot |C)$ do modelowania lokalnych zależności danych dla różnych źródeł informacji stanowi zwykle skończony podzbiór $\mathbf{s}^{t}$. Może być także wynikiem redukcji alfabetu źródła, przekształceń wykonanych na symbolach $\mathbf{s}^{t}$ itp. Reguły określenia C mogą być stałe w całym procesie generacji symboli przez źródło lub też mogą ulegać adaptacyjnym zmianom (np. w zależności od postaci ciągu symboli wcześniej wyemitowanych przez źródło).

Model źródła S z pamięcią jest określony poprzez:

•  alfabet symboli źródła $A_S=\{a_1,a_2,\ldots,a_n\}$,
• zbiór kontekstów C dla źródła S postaci $A_C^S=\{\mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}_{k}\}$,
• prawdopodobieństwa warunkowe $P(a_{i}|\mathbf{b}_{j})$ dla i =1,2,...,n oraz j =1,2,...,k, często wyznaczane metodą częstościową z zależności

gdzie $N(a_{i},\mathbf{b}_{j})$ - liczba łącznych wystąpień symbolu $N(a_{i},\mathbf{b}_{j})$ i kontekstu $\mathbf{b}_{j}, N(\mathbf{b}_{j})$ - liczba wystąpień kontekstu $\mathbf{b}_{j}$, przy czym jeśli $N(\mathbf{b}_{j})=0$ dla pewnych j (taki kontekst wystąpienia symbolu jeszcze się nie pojawił), wtedy można przyjąć każdy dowolny rozkład przy tym kontekście (wykorzystując np. wiedzę a priori do modelowania źródła w takich przypadkach),

• zasadę określania kontekstu C w każdej 'chwili czasowej' t jako funkcję f(\cdot ) symboli wcześniej wyemitowanych przez źródło.

Załóżmy, że źródło emituje sekwencję danych wejściowych \$mathbf{s}^t=(s_1,s_2,\ldots,s_l,\ldots,s_t)$, gdzie $s_{l}\in A_{S}$. Sekwencja kontekstów wystąpienia tych symboli jest określona przez funkcję $f(\cdot )$ oraz $A_{C}^{S}$ i przyjmuje postać: $\textbf{c}^t=(\mathbf{c}_{1},\mathbf{c}_{2},\ldots,\mathbf{c}_{l},\ldots,\mathbf{c}_{t})$, gdzie$\mathbf{c}_l=f(s_1,s_{2},\ldots,s_{l-1})\in A_C^S$ dla $l=2,\ldots,t$ (w przypadku symbolu $s_1$ brak jest symboli wcześniej wyemitowanych przez źródło, można więc przyjąć dowolny kontekst $\mathbf{c}_1)$. W ogólności $f(\cdot )$ wyznaczająca kontekst następnego symbolu $s_{t+1}$ musi być określona jako przekształcenie wszystkich możliwych sekwencji symboli z $A_S$ o długości t lub mniejszej w $A_C^S$. Ponieważ $\mathbf{s}^t$ jest jedyną dostępną sekwencją symboli wygenerowaną przez źródło S prawdopodobieństwa warunkowe określane są na podstawie $\mathbf{s}^t$ według zależności (1.2).

Istotnym parametrem modelu CSM jest rząd kontekstu C, który określa liczbę symboli tworzących kontekst $\mathbf{c}_l$ dla kolejnych symboli emitowanych przez źródło. Rozważmy prosty przykład sekwencji $\mathbf{s}^t$ ze źródła $S$ modelowanego rozkładem $P(a_i|\mathbf{b}_j)$ przy kontekstach kolejnych symboli $\mathbf{c}^l$ rzędu 1. Niech kontekst C stanowi symbol bezpośrednio poprzedzający kodowaną wartość $s_l: \mathbf{c}_l=f(s_1,s_2,\ldots,s_{l-1})=s_{l-1} dla i=2,\ldots,t$ oraz $\mathbf{c}_1=a_r\in A_S$ dla pewnego $1\leq r\leq n$. Wtedy $A_C^S=A_S$, a ten model CSM jest modelem źródła Markowa pierwszego rzędu. Generalnie, model źródła Markowa rzędu m jest bardzo powszechnie stosowaną realizacją CSM (model DMS jest modelem źródła Markowa rzędu 0).

Model źródła Markowa

Źródło Markowa rzędu m jest źródłem, w którym kontekst $C^{(m)}$ wystąpienia kolejnych symboli $s_{l}$ generowanych przez źródło S stanowi skończona liczba m poprzednich symboli $\mathbf{c}_l^{(m)}=(s_{l-1},s_{l-2},\ldots,s_{l-m})$, czyli dla dowolnych wartości l oraz $t\geq m P(s_{l}|s_{l-1},s_{l-2},\ldots,s_{l- t})=P(s_{l}|\mathbf{c}_l^{(m)})$. Zatem prawdopodobieństwo wystąpienia symbolu $a_{i}$ z alfabetu źródła zależy jedynie od m symboli, jakie pojawiły się bezpośrednio przed nim, przy czym określone jest przez zbiór prawdopodobieństw warunkowych (oznaczenia jak przy definicji źródła CSM):

dla wszystkich I oraz$j_{1},j_{2},\ldots,j_{m}=1,2,\ldots,n$.

Często źródło Markowa analizowane jest za pomocą diagramu stanów, jako znajdujące się w pewnym stanie, zależnym od skończonej liczby występujących poprzednio symboli - zobacz rys. 1. Dla źródła Markowa pierwszego rzędu jest n takich stanów, dla źródła rzędu m mamy n^m stanów.

Rys. 1 Diagramy stanów prostych modeli Markowa z alfabetem binarnym: a) ogólny model rzędu 1 z przejściami pomiędzy poszczególnymi stanami, b) model rzędu 2 z przykładowymi wartościami prawdopodobieństw warunkowych. Stany opisane są wszystkimi możliwymi kombinacjami kontekstów, zaś odpowiednie przejścia pomiędzy stanami źródła odzwierciedlają wystąpienie kolejnej danej źródłowej; w kontekście prawy symbol oznacza ten bezpośrednio poprzedzający, zaś lewy - to symbol jeszcze wcześniejszy.

Przy kompresji danych obrazowych efektywny kontekst budowany jest zwykle z najbliższych w przestrzeni obrazu pikseli, przy czym sposób określenia kontekstu może zmieniać się dynamicznie w trakcie procesu kodowania, np. zależnie od lokalnej statystyki. Popularną techniką jest taka kwantyzacja kontekstu (tj. zmniejszanie kontekstu w celu uzyskania bardziej wiarygodnego modelu prawdopodobieństw warunkowych), kiedy to liniowa kombinacja pewnej liczby sąsiednich symboli warunkuje wystąpienie symbolu, dając de facto model warunkowy pierwszego rzędu, zależny jednak od kilku- czy kilkunastoelementowego sąsiedztwa.

\subsection{Miary ilości informacji} \label{Punkt_miary_infor}

Miara ilości informacji dostarczanej (emitowanej) przez probabilistyczne źródło informacji konstruowana jest przy dwóch intuicyjnych założeniach: a) więcej informacji zapewnia pojawienie się mniej prawdopodobnego symbolu, b) informacja związana z wystąpieniem kilku niezależnych zdarzeń jest równa sumie informacji zawartej w każdym ze zdarzeń.

Informacja $I(a_{i})$ związana z wystąpieniem pojedynczego symbolu $a_{i}$ alfabetu źródła $S$ określona jest w zależności od prawdopodobieństwa wystąpienia tego symbolu $p_i=\Pr(s=a_i)$  jako$I(a_i)=\lg(1/p_i), p_{i}\neq 0$. Jest to tzw. informacja własna (self-information).

W przypadku strumienia danych generowanych przez źródło do określenia ilości informacji wykorzystuje się pojęcie entropii. Zasadniczo, dla sekwencji kolejnych symboli $s_{i}$, gdzie $i=1,2,\ldots$, dostarczanych ze źródła informacji $S$ o alfabecie $A_{S}=\{a_{1},a_{2},\ldots,a_{n}\}$ entropia określona jest jako 

gdzie 

$I_m =-\sum_{j_{1}=1}^{n}\sum_{j_{2}=1}^{n}\cdots \sum_{j_{m}=1}^{n}P(a_{j_{1}},a_{j_{2}},\ldots,a_{j_{m}})\lg P(a_{j_{1}},a_{j_{2}},\ldots,a_{j_{m}})=$

$= -\sum_{j_{1},\ldots,j_{m}=1}^{n}\Pr(s_{1}=a_{j_{1}},\ldots,s_{m}=a_{j_{m}}  )\lg \Pr(s_{1}=a_{j_{1}},\ldots,s_{m}=a_{j_{m}})$
oraz $(s_{1},s_{2},\ldots,s_{m})$ jest sekwencją symboli źródła $S$ o długości $m$.

Tak określona entropia nosi nazwę entropii łącznej, gdyż jest wyznaczana za pomocą prawdopodobieństwa łącznego wystąpienia kolejnych symboli z alfabetu źródła informacji. Definicja entropii według zależności (1.4) jest jednak niepraktyczna, gdyż nie sposób wiarygodnie określić prawdopodobieństwa łącznego wystąpienia każdej, możliwej (określonej przez alfabet) kombinacji symboli źródła w rzeczywistym skończonym zbiorze danych. Wymaga to albo dużej wiedzy a priori na temat charakteru zbioru danych, które podlegają kompresji, albo nieskończenie dużej liczby danych do analizy (nieskończenie długiej analizy). Należałoby więc zbudować model źródła informacji określający prawdopodobieństwo łącznego wystąpienia dowolnie długiej i każdej możliwej sekwencji symboli tegoż źródła. Bardziej praktyczne postacie zależności na entropię, aproksymujące wartość entropii łącznej dla danego źródła informacji, wynikają z uproszczonych modeli źródeł.

Entropia modelu źródła może być rozumiana jako średnia ilość informacji przypadająca na generowany symbol źródła, jaką należy koniecznie dostarczyć, aby usunąć wszelką nieokreśloność (niepewność) z sekwencji tych symboli. Podstawa logarytmu używanego w definicjach miar określa jednostki używane do wyrażenia ilości informacji. Jeśli ustala się podstawę równą 2, wtedy entropia według (1.4) wyraża w bitach na symbol średnią ilość informacji zawartą w zbiorze danych (tak przyjęto w rozważaniach o entropii).

Dla poszczególnych modeli źródeł informacji można określić ilość informacji generowanej przez te źródła. Ponieważ modele źródeł tylko naśladują (aproksymują) cechy źródeł rzeczywistych (często niedoskonale), obliczanie entropii dla rzeczywistych zbiorów danych za pomocą tych modeli jest często zbyt dużym uproszczeniem. Należy jednak podkreślić, iż obliczona dla konkretnego źródła ilość informacji tym lepiej będzie przybliżać rzeczywistą informację zawartą w zbiorze danych (wyznaczaną asymptotycznie miarą entropii łącznej), im wierniejszy model źródła informacji został skonstruowany.

Entropia modelu źródła bez pamięci

Zakładając, że kolejne symbole są emitowane przez DMS niezależnie, wyrażenie na entropię tego modelu źródła można wyprowadzić z równania (1.4). Entropia modelu źródła bez pamięci, uzyskana przez uśrednienie ilości informacji własnej po wszystkich symbolach alfabetu źródła wynosi:

gdzie $n$ oznacza liczbę symboli $a_i$ w alfabecie. Dla $P(a_i)=0$ wartość $\mbox{$0\cdot\log_{2}1/0\equiv 0$}$, gdyż $\lim_{\phi \rightarrow 0^+}\phi \log_2 1/\phi=0$. Entropia źródła bez pamięci nazywana jest entropią bezwarunkową (od użytej formy prawdopodobieństwa). W przypadku, gdy źródło DMS nie najlepiej opisuje kodowany zbiór danych entropia obliczona według (1.5) jest wyraźnie większa od entropii łącznej, czyli nie jest w tym przypadku najlepszą miarą informacji. Rzeczywista informacja zawarta w zbiorze danych jest pomniejszona o nieuwzględnioną informację wzajemną, zawartą w kontekście wystąpienia kolejnych symboli.

Zależności pomiędzy danymi w strumieniu zwykle lepiej opisuje model z pamięcią, a wartość entropii tego źródła (tzw. entropii warunkowej) jest bliższa rzeczywistej ilości informacji zawartej w kompresowanym zbiorze danych. Zależność pomiędzy entropią łączną $H(C,S)$ źródła o zdefiniowanym kontekście $C$, warunkową $H(S|C)$ oraz tzw. entropią brzegową (entropią źródła obliczoną dla rozkładu brzegowego) $H(C)$ jest następująca:

Przykładem miary ilości informacji źródeł z pamięcią będzie entropia wyznaczona dla źródeł Markowa, znajdujących bardzo częste zastosowanie w praktyce kompresji.

Entropia modelu źródła Markowa
Aby za pomocą modelu źródła Markowa rzędu $m$ obliczyć ilość informacji (średnio na symbol źródła) zawartą w kodowanym zbiorze danych, wykorzystuje się zbiór prawdopodobieństw warunkowych i określa tzw. entropię warunkową źródła znajdującego się w pewnym stanie $(a_{j_{1}},a_{j_{2}},\ldots,a_{j_{m}})$ jako:

Następnie oblicza się średnią entropię warunkową źródła S jako sumę ważoną entropii warunkowych po kolejnych stanach źródła wynikających ze wszystkich możliwych konfiguracji (stanów) kontekstu $C^{(m)}$:$\quad A_{C^{(m)}}^{S}=\{\mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}_{j},\ldots,\mathbf{b}_{k}\}$, gdzie $\mathbf{b}_{j}=(a_{j_{1}},\ldots,a_{j_{m}})$ oraz $\forall_{l\in \{1,\ldots,m\}}a_{j_{l}}\in A_{S}$, przy czym wagami są prawdopodobieństwa przebywania źródła w danym stanie:

czyli   

$H(S|C^{(m)})=-\sum_{j_{1}=1}^{n}\cdots \sum_{j_{m}=1}^{n}\sum_{i=1}^{n}P(a_{j_{1}},\ldots,a_{j_{m}},a_{i})\log_{2}P(a_{i}|a_{j_{1}},\ldots,a_{j_{m}})$

Tak określona średnia entropia warunkowa modelu źródła Markowa rzędu $m$ jest mniejsza lub równa entropii bezwarunkowej. Jest ona pomniejszona o średnią ilość informacji zawartą w kontekście wystąpienia każdego symbolu strumienia danych. Jednocześnie entropia warunkowa danych przybliżanych źródłem Markowa rzędu $m$ jest niemniejsza niż entropia łączna źródła emitującego tę sekwencję danych (według równania (1.4)). Zależność pomiędzy postaciami entropii związanymi z przedstawionymi modelami źródeł informacji, opisującymi z większym lub mniejszym przybliżeniem informację zawartą w konkretnym zbiorze danych, jest następująca:

Zastosowanie modeli CSM wyższych rzędów zazwyczaj lepiej określa rzeczywistą informację zawartą w zbiorze danych, co pozwala zwiększyć potencjalną efektywność algorytmów kompresji wykorzystujących te modele. W zależności od charakteru kompresowanych danych właściwy dobór kontekstu może wtedy zmniejszyć graniczną długość reprezentacji kodowej. Stosowanie rozbudowanych modeli CSM w konkretnych implementacjach napotyka jednak na szereg trudności, wynikających przede wszystkim z faktu, iż ze wzrostem rzędu kontekstu liczba współczynników opisujących model rośnie wykładniczo. Wiarygodne statystycznie określenie modeli zaczyna być wtedy problemem. Trudniej jest także zrealizować algorytmy adaptacyjne, co w efekcie może zmniejszyć skuteczność kompresji w stosunku do rozwiązań wykorzystujących prostsze modele.

W zagadnieniu kompresji jeszcze silniej wykorzystuje się model informacji, tak probabilistyczne, jak też różne formy modeli uwzględniających w jakimś stopniu funkcje semantyczne danych źródłowych (znaczenie pojedynczych symboli, ciągów danych, relacji pomiędzy danymi, itd.). Zasadnicze jest też odniesienie do reprezentacji rozumianej jako ciąg bitów o możliwie zredukowanej długości - kompresją nazywamy wyznaczanie możliwie oszczędnej reprezentacji sekwencji danych. 

Poniżej przedstawiono bardziej ścisłe próby zdefiniowania pojęcia kompresji - pierwszą w ujęciu bardziej intuicyjnym, drugą - w rozumieniu najnowszych trendów rozumienia i wykorzystywania procesów kompresji danych.

Cele kompresji w zależności od charakteru danych i rodzaju zastosowań mogą być jednak bardziej różnorodne. 

Można wyróżnić dwie zasadnicze kategorie metod kompresji danych: bezstratne i stratne. W kompresji bezstratnej (inaczej odwracalnej, bezstratnej numerycznie) zrekonstruowany po kompresji ciąg danych jest numerycznie identyczny z sekwencją źródłową z dokładnością do pojedynczego bitu. Taki rodzaj kompresji jest wykorzystywany w zastosowaniach wymagających wiernej rekonstrukcji danych oryginalnych, takich jak archiwizacja dokumentów tekstowych, historii operacji finansowych na kontach bankowych, niektórych obrazów medycznych i wielu innych.

Kompresja z selekcją informacji (Inaczej kompresja stratna lub nieodwracalna) nie pozwala odtworzyć (zrekonstruować) z dokładnością do pojedynczego bitu danych źródłowych. W przypadku tzw. stratnej kompresji obrazów wprowadza się czasami pojęcie wizualnej bezstratności, a w przypadku dźwięku -- bezstratności słuchowej (ogólnie chodzi o bezstratność percepcji danych). Uproszczenie strumienia danych prowadzące do efektywniejszej, przede wszystkim krótszej reprezentacji może być niezauważalne dla obserwatora w normalnych warunkach prezentacji. Przykładowo, przy prezentacji obrazów medycznych o dwunastobitowej dynamice za pomocą stacji roboczej z ośmiobitowym przetwornikiem karty graficznej usunięcie (zniekształcenie) treści zapisanej w czterech najmłodszych bitach oryginalnych wartości pikseli nie spowoduje żadnych zmian w obserwowanym obrazie. Definicja percepcyjnej bezstratności jest jednak względna, zależna od zdolności, umiejętności i zamierzeń odbiorcy, co nakazuje  zachowanie ostrożności w konkretnych zastosowaniach. Przykładowo, wystarczy zmiana warunków obserwacji obrazu, np. zmiana okna obserwacji kolejnych map bitowych, użycie danych przetworzonych do rejestracji obrazu na filmie, bądź też poddanie ich dalszemu przetwarzaniu (eliminacja szumów, podkreślenia krawędzi, segmentacja itp.), by wystąpiła zauważalna różnica pomiędzy analizowanym obrazem źródłowym i obrazem ze wstępnie wyzerowanymi najmłodszymi bitami.

Zgodnie z klasycznym paradygmatem kompresji stratnej dane wejściowe transformuje się w nową przestrzeń pośrednią, w której redukowana jest nadmiarowość reprezentacji źródłowej. Wykorzystuje się przy tym ograniczenie zbioru możliwych wartości pośrednich poprzez kwantyzację, co jako proces nieodwracalny powoduje stratność całej metody. Drugim ważnym etapem jest kodowanie reprezentacji pośredniej. Odtworzona sekwencja danych jest jedynie przybliżeniem sekwencji źródłowej zachowującym w założeniu istotne jej właściwości. 

Uproszczenie charakteru danych (związane z redukcją informacji rozumianej syntaktycznie) w procesie kwantyzacji, przeprowadzanej w dziedzinie efektywnej transformaty, pozwala znacznie zwiększyć stopień kompresji w stosunku do metod bezstratnych. Wymaga to jednak rzetelnej kontroli jakości danych rekonstruowanych za pomocą wiarygodnych miar zachowanej ilości informacji. Kontrola ta pozwoli ustalić wartości dopuszczalnych stopni kompresji w określonych zastosowaniach.

Zasadniczym celem selekcji informacji w kompresowanym zbiorze danych jest usunięcie wszystkiego, co nie jest informacją dla odbiorcy, aby uprościć reprezentację danych i zredukować jej długość. Przykładowo, w obrazie może zostać wydzielony obszar zainteresowania (ROI), którego rekonstrukcja ze skompresowanej reprezentacji pozwoli odtworzyć oryginał z dokładnością do pojedynczego bitu, podczas gdy pozostała część obrazu może zostać maksymalnie uproszczona, bez zachowania nawet elementarnej treści. W innym przypadku selekcja może prowadzić do wiernego zachowania jedynie tych właściwości odtwarzanych danych, które są istotne dla odbiorcy. Opis wybranych metod kompresji przedstawiono w dalszej części. 

Efektywność kompresji może być rozumiana zależnie od zastosowania, rodzaju danych kodowanych, sprzętowych możliwości implementacji, parametrów środowiska transmisji|gromadzenia informacji, wymagań użytkownika czy sposobu rozpowszechniania informacji itp. Najbardziej powszechnym rozumieniem tego pojęcia jest efekt minimalizacji rozmiaru  reprezentacji skompresowanej danych oryginalnych. Do liczbowych miar tak rozumianej efektywności należą przede wszystkim: stopień kompresji $CR$ (compression ratio), procent kompresji $CP$ (compression percentage) oraz średnia bitowa $BR$ (bit rate).

Stopień kompresji wyrażany jest stosunkiem liczby bitów reprezentacji oryginalnej do liczby bitów reprezentacji skompresowanej wyrażanej w postaci $n$:1, np. 2:1, 100:1. Procent kompresji (stosowany często w ocenie skuteczności archiwizerów tekstu) określany jest wyrażeniem $CP=(1-\frac{1}{CR})\cdot 100\%$, a średnia bitowa to średnia ilość bitów reprezentacji skompresowanej przypadająca na element źródłowej sekwencji danych. Efektywność (skuteczność, wydajność) kompresji oznacza wtedy uzyskanie możliwie dużych wartości $CR$ i $CP$, czy też możliwie małej średniej bitowej $BR$. Miary  $CR$ i $CP$ są miarami względnymi, przydatnymi np. w ocenie efektywności koderów w zastosowaniach archiwizacji (ich wartość łatwo przekłada się na poziom oszczędności kosztów nośników). Bezwględna wartość $BR$ charakteryzuje rozmiar wyjściowych danych kodera i jest użyteczna w zastosowaniach transmisyjnych (łatwo określić przepustowość sieci np. wymaganą przy transmisji w czasie rzeczywistym).

W innych zastosowaniach efektywność może być związana z minimalizacją czasu kompresji (lub dekompresji), np. przy rejestracji danych pomiarowych w czasie rzeczywistym, wielokrotnym odczytywaniu obrazów zgromadzonych w ogólnodostępnej bazie danych. Kryteriami efektywności mogą być także: minimalny iloczyn: czas $\times$ średnia bitowa, wysoka odporność strumienia danych skompresowanych na błędy transmisji, dobra jakość danych po kompresji/dekompresji w zależności od rodzaju wprowadzonych zniekształceń, możliwość elastycznego  odtwarzania danych źródłowych w szerokim zakresie skal, możliwość kodowania wybranego obszaru (fragmentu) zainteresowań w sposób odmienny od pozostałej części zbioru źródłowego, itp. 

Można przyjąć, że kodowanie jest w pierwszym przybliżeniu synonimem kompresji, niekiedy rozumianym w nieco zawężonym znaczeniu. Podstawą kompresji-kodowania są kody, tj. ustalone reguły tworzenia użytecznej reprezentacji ze zredukowaną nadmiarowością na poziomie bitów. Na bazie kodów podstawowych opracowywane są efektywne metody kompresji danych o różnej specyfice, czemu służą powszechnie przyjęte, sprawdzone wzorce  rozwiązań zweryfikowanych w praktyce, czyli paradygmaty kompresji.

\\Jedną z najprostszych metod kodowania jest zastąpienie serii identycznych symboli liczbą powtórzeń danego symbolu . Niech sekwencja danych wejściowych będzie następująca:$\mathbf{s}_{we}=(5, 5 ,5, 2, 2, 11, 11, 11, 11, 11, 8)$. Jeśli wyznaczymy model opisujący dane źródłowe seriami jednakowych symboli według schematu:  $(\text{liczba powtórzeń}, \text{symbol})$, wówczas opis  $\mathbf{s}_{we}$ źródła za pomocą takiego modelu jest następujący: $\mathcal{M}_{\mathbf{s}_{we}}^{\text{serie}}=\big((3,5),(2,2),(5,11),(1,8)\big)$. Ustalmy, że wynikająca z przyjętego modelu postać opisu jest kodowana binarnie w najprostrzy sposób według zasady, bazującej na przyjętych wstępnie ograniczeniach: 

•  przy założeniu długości serii nie dłuższej niż 8, na pierwszych trzech bitach zapisywana jest dwójkowo liczba  (pomniejszona o jeden) powtórzeń symbolu,
• przy założeniu postaci alfabetu $A_S=\{0,\ldots,15\}$, na  kolejnych czterech bitach kodu dwójkowego reprezentowany jest symbol tej serii.

Binarna postać sekwencji kodowej $\mathbf{s}_{wy}$ wygląda wówczas następująco:  $\mathbf{s}_{wy}=(\texttt{0100101},\ \texttt{0010010},\ \texttt{1001011},\texttt{0001000})$. Uzyskano efekt redukcji długości reprezentacji danych z 44 bitów postaci źródłowej (przyjmując 4 bity na  pojedynczy symbol) do 28 bitów wyjściowych. Efektywność tej metody rośnie, gdy pojawiają się długie serie powtórzeń symboli. 

Inna metoda kodowania wykorzystuje fakt, że niektóre symbole źródłowe pojawiają się częściej, zaś pozostałe rzadziej. Różnicowanie długości słów kodowych poszczególnych symboli polega na przypisaniu krótszych słów symbolom wystepującym częściej. Model opisuje wówczas częstości wystapień symboli za pomocą wag $w(\cdot)$, równych sumie wystąpień poszczególnych symboli alfabetu. W przypadku rozważanej $\mathbf{s}_{wy}$ mamy więc:  $\mathcal{M}_{\mathbf{s}_{we}}^{\text{wagi}}=\{w(5)=3,w(2)=2,w(11)=5$, $w(8)=1\}$. Jeśli na podstawie tych wag zróżnicujemy słowa kodowe w sposób następujący: $\varsigma (5)=\texttt{10},\varsigma (2)=\texttt{110},\varsigma (11)=\texttt{0},\varsigma (8)=\texttt{111}$, wówczas otrzymamy ciąg wyjściowy: $\mathbf{s}_{wy}=(\texttt{10},\texttt{10},\texttt{10},\texttt{110},\texttt{110},\texttt{0},\texttt{0},\texttt{0},\texttt{0},\texttt{0},\texttt{111})$ o długości 20 bitów. Druga forma modelowania okazała się skuteczniejsza, chociaż wymaga jeszcze szereg dookreśleń (w zakresie metody ustalania słów kodowych o zmiennej długości oraz konieczności przekazania w nagłówku pliku skompresowanego parametrów modelu $\mathcal{M}_{\mathbf{s}_{we}}^{\text{wagi}}$.  

Przykładem wstępnej dekompozycji danych w celu uproszczenia modelu jest  wyskorzystanie prostego mechanizmu liczenia różnic pomiędzy wartością kodowaną i wartością bezpośrednio ją poprzedzającą: $\mathcal{D}^{\text{różnice}}=\{r_i:\ r_i=s_i-s_{i-1}, i=1,\ldots,11,\ s_0=0 \}$. Dla rozważanej $\mathbf{s}_{we}$  mamy wtedy $\mathcal{D}_{\mathbf{s}_{we}}^{\text{różnice}}=\{5,0,0,-3,0,9,0,0,0,0,-3\}$. Dalej stosując modelowanie z wagami ustalamy: $\mathcal{M}_{\mathbf{s}_{we}}^{\text{wagi różnic}}=\{w(5)=1,w(0)=7,w(-3)=2,w(9)=1\}$. Przypisując tym symbolom zróżnicowane długością słowa kodowe: $\varsigma (5)=\texttt{110}$, $\varsigma (0)=\texttt{0}$, $\varsigma (-3)=\texttt{10}$, $\varsigma (9)=\texttt{111}$, uzyskamy 18 bitów postaci zakodowanej.

Modelowanie to użycie skutecznych modeli statystycznych i predykcyjnych, oszczędnego opisu lokalnych zależności danych, konstrukcja słownika z najczęściej występującymi frazami (ciągami danych wejściowych), wykorzystanie wiedzy dostępnej a priori na temat kompresowanego zbioru danych, poprzedzone niekiedy przekształceniem (dekompozycją) danych zwiększającą ich podatność na modelowanie, a w konsekwencji - na kodowanie binarne,  itd. Istotne są przy tym kontekstowe zależności danych sąsiednich w sekwencji wejściowej lub też w oryginalnej przestrzeni danych kodowanych, np. pewne metryczne zależności w przestrzeni koloru i w przestrzeni geometrycznej w obrazach.

Na podstawie uzyskanej reprezentacji pośredniej tworzona jest binarna sekwencja wyjściowa (kodowa), poprzez przypisanie ciągów bitów (słów kodowych) poszczególnym danym (pojedynczym symbolom alfabetu źródła informacji), całej sekwencji danych wejściowych lub jej poszczególnym częściom. 

Algorytmy kodowania wykorzystujące opisane wyżej modele źródeł informacji pozwalają tworzyć wyjściową reprezentację kodową, która jest sekwencją bitową o skończonej długości, utworzoną z bitowych słów kodowych charakterystycznych dla danej metody. Realizację algorytmu kodowania, np. w określonym języku programowania lub sprzętową, nazwiemy koderem. Analogicznie realizację algorytmu dekodowania -- dekoderem. Algorytm kodowania realizuje kod, czyli wspomnianą regułę (zasadę, funkcję, przekształcenie) przyporządkowującą ciągowi symboli wejściowych (opisanych modelem źródła informacji o zdefiniowanym alfabecie $A_S$) bitową sekwencję kodową (wyjściową). 

Kodowanie binarne jest metodą wykorzystania określonego kodu do kompresji sekwencji danych wejściowych źródła informacji $A_S$. Kod ten bazuje na określonym modelu źródła informacji, który steruje procesem kodowania binarnego. Podstawowy algorytm kodowania składa się więc z dwóch zasadniczych elementów: modelowania oraz binarnego kodowania.

Kody jednoznacznie dekodowalne

W metodach kompresji, w przeciwieństwie np. do technik szyfrowania, istnieje warunek konieczny, aby reprezentacja kodowa (tj. bitowa sekwencja wyjściowa powstała w wyniku realizacji reguły kodu na strumieniu wejściowym) była jednoznacznie dekodowalna. Oznacza to, iż na podstawie wyjściowej sekwencji bitowej kodera realizującego ustalony kod opisany funkcją kodowania $\mathcal{K}$ można jednoznacznie odtworzyć oryginalny zbiór symboli wejściowych. 

Kodowanie jest więc przekształceniem różnowartościowym 'jeden w jeden', czyli bijekcją. Jeśli dla ciągów symboli wejściowych $s"_{1},s"_{2},\ldots,s"_{t}$ oraz $s""_{1},s""_{2},\ldots,s""_{r}$o wartościach z alfabetu $A_{S}=\{a_{1},\ldots,a_{n}\}$} przyporządkowano bitową sekwencję kodową $z\in Z$ ($Z$ - zbiór wszystkich sekwencji bitowych generowanych przez $\mathcal{K}$):

Oznaczmy przez $A_S^+$  zbiór wszystkich niepustych i skończonych sekwencji symboli alfabetu $A_S$ o $N$ symbolach. Wtedy ogólna postać funkcji kodowania $\mathcal{K}:\ A_S^+ \rightarrow A_{\{0,1\}}^+$ z binarnym alfabetem sekwencji wyjściowych $\{0,1\}$. 

Przykładem kodu jednoznacznie dekodowalnego jest prosty kod dwójkowy stałej długości $B_4$ (zobacz punkt ) z czteroelementowym alfabetem $A_S$. Każdemu z symboli alfabetu przypisano słowo kodowe w postaci binarnego zapisu liczby naturalnej od 0 do 3, będącej indeksem (wskazującej pozycję) danego symbolu w $A_S$ na $k=\log_2 4=2$ bitach. Zbiór słów kodowych jest więc następujący: $A_{B_4}=\{\texttt{00},\texttt{01},\texttt{10},\texttt{11}\}$}, a kod $\mathcal{K}=B_4$ jest odwzorowaniem różnowartościowym (co wynika z unikatowej postaci binarnej reprezentacji indeksu kolejnych symboli $A_S$). 

Kodowanie według $B_4$ polega na przypisaniu kolejnym symbolom sekwencji wejściowej $s_i,\ s_i \in A_S,\ i=1,2\ldots$ odpowiednich binarnych słów kodowych $B_4(s_i)$, takich że $B_4(s_i=a_1)=\texttt{00},\ B_4(s_i=a_2)=\texttt{01},\ B_4(s_i=a_3)=\texttt{10}$ i $B_4(s_i=a_4)=\texttt{11}$, dołączając je do wyjściowej sekwencji bitów (konkatenacja bitów słów kodowych symboli źródła $S$ według porządku ich występowania na wejściu kodera). Praca dekodera tego kodu  polega na odtwarzaniu symboli z $A_S$ według czytanych kolejno 2 bitowych indeksów, co pozwala jednoznacznie zdekodować sekwencję kodową i wiernie zrekonstruować postać źródłowej sekwencji $\mathbf{s}^t$.

Kodowanie według $B_k$ jest przykładem tzw. kodowania przyrostowego:  $\mathcal{K}(s_1,s_2,\ldots,s_{t})=\mathcal{K}(s_1)\mathcal{K}(s_2) \cdots \mathcal{K}(s_t)$, gdzie $s_i \in A_S$, a $\mathcal{K}(s_i) \in A_{\mathcal{K}}=\{\varsigma_1,\varsigma _2,\ldots,\varsigma _n\}$ ($A_{\mathcal{K}}$ nazwiemy alfabetem kodu $\mathcal{K}$). Ogólniej kodowanie przyrostowe polega na kolejnym dołączaniu sekwencji bitowych, przypisywanych czytanym sekwencjom symboli wejściowych według określonej reguły (tj. kodu), tworząc jedną sekwencję kodową. Kod może przypisywać sekwencje kodowe pojedynczym symbolom (jak wyżej) lub całym wieloelementowym grupom (blokom) symboli. 

Dany jest alfabet $A_S=\{a_1,a_2,a_3\}$ oraz zbiór wszystkich niepustych sekwencji nad tym alfabetem $A_S^+$. Trywialnym przykładem kodowania, które po rozszerzeniu nie jest jednoznacznie dekodowalne, jest funkcja $\mathcal{K}_1(a_i)=\beta$, która dowolnemu symbolowi z $A_S$ przypisuje to samo słowo kodowe $\beta \in A_{\{0,1\}}^+$. Dekoder odczytując $\beta$ nie jest w stanie podjąć jednoznacznej decyzji:  $\mathcal{K}_1^{-1}(\beta)=a_1 \ \lor \dots$ $\ldots \ \lor \ \mathcal{K}_1^{-1}(\beta)=a_2 \ \lor \ \mathcal{K}_1^{-1}(\beta)=a_3$.

Innym przykładem kodu niejednoznacznie dekodowalnego przy dwuelementowym alfabecie źródła jest: $\mathcal{K}_2(a_1)=\texttt{0}$ i $\mathcal{K}_2(a_2)=\texttt{00}$, kiedy to sekwencję $\texttt{00}$ można zdekodować jako ciąg symboli $(a_1,a_1)$ lub też jako pojedynczy symbol $a_2$. Przy większym alfabecie źródła, np. $A_S=\{a_1,a_2,a_3,a_4\}$ określmy $\mathcal{K}_3$ jako: $\mathcal{K}_3(a_1)=\texttt{0}$, $\mathcal{K}_3(a_2)=\texttt{1}$, $\mathcal{K}_3(a_3)=\texttt{01}$ i $\mathcal{K}_3(a_4)=\texttt{10}$. Dekodowanie sekwencji bitowych $\beta_1=\texttt{01}$ lub $\beta_2=\texttt{10}$ nie jest jednoznaczne, gdyż $\mathcal{K}_3^{-1}(\beta_1)=a_3$ lub też $\mathcal{K}_3^{-1}(\beta_1)=(a_1,a_2)$, a w przypadku $\beta_2$ mamy $\mathcal{K}_3^{-1}(\beta_2)=a_4=(a_2,a_1)$. 

Koder $\mathcal{K}_4$ przyporządkuje czterem symbolom alfabetu źródła informacji $A_S$ następujące słowa kodowe: $A_{\mathcal{K}_4}=\{\mathcal{K}_4(a_1),\mathcal{K}_4(a_2),\mathcal{K}_4(a_3)\mathcal{K}_4(a_4) \}=$$=\{\varsigma _1^{(\mathcal{K}_4)},\varsigma _2^{(\mathcal{K}_4)},\varsigma _3^{(\mathcal{K}_4)},\varsigma _4^{(\mathcal{K}_4)}\}=\{\texttt{0},\texttt{01},\texttt{001},\texttt{0011}\}$. Rozpatrzmy krótką sekwencję kodową $\beta$ = 00} utworzoną ze słów kodowych alfabetu $A_{\mathcal{K}_4}$, która może być interpretowana jako połączenie słów 0 i 0} ($\varsigma _1\varsigma _2$) lub też 001 (czyli $\varsigma _3$). Kod realizowany przez ten koder również nie jest kodem jednoznacznie dekodowalnym, a można to stwierdzić na podstawie analizy alfabetu postaci (zbioru) słów kodowych danego kodu. Dla koderów wykorzystujących inne zbiory binarnych słów kodowych można w analogiczny sposób stwierdzić, że:

• kod $A_{\mathcal{K}_5}=\{\texttt{1},\texttt{01},\texttt{001},\texttt{0001}\}$ jest jednoznacznie dekodowalny, 
• kod $A_{\mathcal{K}_6}=\{\texttt{0},\texttt{10},\texttt{110},\texttt{111}\}$ jest jednoznacznie dekodowalny,
•  kod $A_{\mathcal{K}_7}=\{\texttt{0},\texttt{10},\texttt{11},\texttt{111}\}$ nie jest jednoznacznie dekodowalny, 
• kod $A_{\mathcal{K}_8}=\{\texttt{0},\texttt{01},\texttt{11}\}$ jest jednoznacznie dekodowalny,
• kod $A_{\mathcal{K}_9}=\{\texttt{001},\texttt{1},\texttt{100}\}$ nie jest jednoznacznie dekodowalny.

Aby kod był jednoznacznie dekodowalny musi mieć $N$ różnych słów kodowych (w przypadku $\mathcal{K}_1$ warunek ten nie jest spełniony). Jeśli w danym kodzie jedno ze słów kodowych jest konkatenacją innych słów, wówczas kod nie jest jednoznacznie dekodowalny (zobacz przypadki kodów  $\mathcal{K}_2$ i $\mathcal{K}_3$). Uogólniając tę zasadę, jeśli połączenie kilku słów kodowych daje taki sam efekt, jak połączenie innych słów z alfabetu kodu, wówczas także mamy do czynienia z brakiem jednoznaczności dekodowania. Tak jest w przypadku kodu $\mathcal{K}_7$, gdzie połączenie słów $\varsigma_3\varsigma_2=\varsigma_4\varsigma_1$, jak również w przypadku kodu $\mathcal{K}_9$, ponieważ $\varsigma_2\varsigma_1=\varsigma_3\varsigma_2$. 

Kody przedrostkowe

W przypadku kodów o liczniejszych alfabetach źródeł informacji trudno jest nieraz zweryfikować kod pod względem jednoznaczności dekodowania. Można jednak zauważyć, że we wszystkich przypadkach przedstawionych powyżej kodów, które nie są jednoznacznie dekodowalne, jedno ze słów kodowych jest przedrostkiem innego. Słowo   $\varsigma_i \in A_{\mathcal{K}}$ jest przedrostkiem słowa $\varsigma_j\in A_{\mathcal{K}},i \neq j$, jeśli $\varsigma_j=\varsigma_i \beta$, gdzie $\beta \in A_{\{0,1\}}^+$. Dla kodów $\mathcal{K}_4, \mathcal{K}_5$ oraz $\mathcal{K}_7$ żadne ze słów nie jest przedrostkiem innego. Są to więc kody przedrostkowe, tj. dla dowolnej pary różnych symboli $a_i ,a_j \in A_S$ zachodzi relacja $\mathcal{K}(a_i) \npreceq \mathcal{K}(a_j)$ (gdzie $\preceq$ oznacza relację początku w sekwencji bitowej). Relacja ta przenosi się na sekwencje symboli źródła $A_S$. Skoro żaden element z $A_{\mathcal{K}}$ nie jest przedrostkiem innego słowa tego zbioru, to sekwencja kodowa $\alpha$ dowolnego ciągu  symboli z $A_S$ także nie może być przedrostkiem sekwencji słów kodowych $\beta$ innego ciągu symboli alfabetu źródła. Efektem wystąpienia choćby jednego różnego symbolu w sekwencji wejściowej jest pojawienie się słowa, który nie jest przedrostkiem innego, co powoduje utratę cechy przedrostkowości sekwencji: $\alpha=\gamma_1\mathcal{K}(a_i)\gamma _2,\beta=\gamma _1\mathcal{K}(a_j)\gamma _2,\ i \neq j,\ \gamma _1,\gamma _2 \in A_{\mathcal{K}}^+ \cup\emptyset \Rightarrow \alpha\npreceq \beta$, ponieważ $\mathcal{K}(a_i)\npreceq \mathcal{K}(a_j)$. Ta właściwość pozwala jednoznacznie zdekodować sekwencję kodową ciagu symboli wejściowych.

Kody przedrostkowe (prefix codes) w literaturze angielskojęzycznej nazywane są także prefix condition codes}, prefix-free codes lub też comma-free code. Wydaje się, że nazwa kody bezprzedrostkowe lepiej oddaje istotę zagadnienia.

Ze względu na możliwość dekodowania od razu kolejnych słów kodowych (od lewej do prawej, co daje prostą budowę kodera), kody przedrostkowe znane są także jako instantaneous codes, czyli kody z natychmiastowym dekodowaniem, bez konieczności odczytywania dalszych bitów w celu poprawnej interpretacji sekwencji bitów. Prosty algorytm dekodera kodu przedrostkowego $\mathcal{K}$ który polega na odczytywaniu kolejnych słów kodowych i dekodowaniu odpowiadających im symboli źródła, jest następujący:

Algorytm 1.3 Dekodowanie sekwencji kodu przedrostkowego 

1. Wyzeruj zmienną $\alpha$ przechowującą wejściową sekwencję bitów;
2. Czytaj do $\alpha$ tyle bitów, ile wynosi minimalna długość słowa kodowego w $A_{\mathcal{K}}$ a wobec braku danych wejściowych zakończ;
3. Porównanie $\alpha$ ze słowami kodu $\mathcal{K}$: dla $i=0,\ldots,n-1$ sprawdź, jeśli $\alpha=\varsigma_i$ (gdzie $\varsigma _i \in A_{\mathcal{K}}$), to emituj na wyjście symbol $a_i=\mathcal{K}^{-1}(\varsigma _i),\ a_i\in A_S$ i kontynuuj krok 1;
4. Czytaj bit z wejścia i dopisz go do $\alpha$, a wobec braku danych wejściowych zakończ;
5. Przejdź do kroku 3.

Kody przedrostkowe mogą być reprezentowane za pomocą struktury binarnych drzew kodowych (są kodami drzew binarnych), gdzie etykietowane gałęzie ustalają kolejne bity słów symboli alfabetu źródła, przypisanych liściom tego drzewa. Przejście od liścia do korzenia ze spisaniem dwójkowych etykiet kolejnych gałęzi daje słowo kodowe danego symbolu (w odwrotnej kolejności, tj. od najmłodszego bitu do nastarszego). Przy dekodowaniu symbolu, odczytywane kolejno bity słowa kodowego (od najstarszego do najmłodszego) prowadzą od korzenia do odpowiedniego liścia. Wykorzystanie struktury drzewa umożliwia wygodną realizację kodera i dekodera danego kodu przedrostkowego.

Przedrostkowość kodu jest warunkiem wystarczającym jego jednoznacznej dekodowalności. Nie jest jednak warunkiem koniecznym, co pokazuje przykład kodu $\mathcal{K}_8$. Kody jednoznacznie dekodowalne, nie będące kodami przedrostkowymi, są jednak trudniejsze w dekodowaniu (komplikuje się nieco budowa dekodera, a interpretacja sekwencji bitów odbywa się z opóźnieniem). Po odczytaniu słowa kodowego wymagają niekiedy odczytania kilku dodatkowych bitów, aby dokonać poprawnej jego interpretacji. Weźmy sekwencję kodową utworzoną według kodu $\mathcal{K}_8$ postaci: $\beta=\texttt{001110}=\varsigma_1\varsigma_2\varsigma_3\varsigma_1$. Zdekodowanie pierwszego symbolu $a_1=\mathcal{K}_8^{-1}(\varsigma _1)$ trójelementowego alfabetu $A_S$ wymaga odczytania dwóch pierwszych bitów (drugi bit sekwencji kodowej równy 0 wskazuje, że pierwsze 0 to $\varsigma_1$ a nie pierwszy bit słowa $\varsigma_2$). Aby poprawnie zdekodować bit drugi i trzeci sekwencji $\beta$(jako $\varsigma_2$) koniecznym jest odczytanie wszystkich pozostałych bitów $\beta$ (tj. czwartego, piątego i szóstego). Bowiem po odczytaniu piątego bitu jeszcze nie wiadomo, czy 0111 (bity od 2 do 5 sekwencji $\beta$) to złączone słowa $\varsigma_2\varsigma_3$, czy też konkatenacja słów $\varsigma_1 \varsigma_3$ z pierwszym bitem kolejnego słowa $\varsigma_3$. Dopiero po odczytaniu ostatniego 0 (szóstego bitu z $\beta$) wszystko się wyjaśnia (gdyby nie był to ostatni bit sekwencji kodowej, nie byłoby wiadomo czy należy dekodować $\varsigma_1$ czy też jest to pierwszy bit $\varsigma_2$).

Kody drzew binarnych

Wykorzystanie struktury drzewa w projektowaniu kodu przedrostkowego pozwala w wygodny sposób realizować założenia dotyczące konstrukcji kodu efektywnego w kompresji danych o określonej charakterystyce. Utworzenie drzewa binarnego dla definiowanego kodu przedrostkowego ułatwia analizę kodu, pozwala wykazać ewentualną jego nadmiarowość, umożliwia prostą jego modyfikację poprzez zmianę sposobu etykietowania drzewa (wpływającego na postać poszczególnych słów) lub dodanie  liści (rozszerzenie alfabetu kodu o nowe słowa).

Właściwości kodu drzewa binarnego są określane na etapie konstruowania struktury drzewa dla założonej liczby liści, przy ustalaniu jego głębokości, poziomu zrównoważenia w skali całego drzewa lub wybranych poddrzew, sposobu rozmieszczenia symboli w liściach oraz zasad etykietowania. Głębokość umieszczenia poszczególnych liści decyduje o długości słów kodowych. Poziom zrównoważenia drzewa wpływa na zróżnicowanie długości słów symboli.
 
Formowanie słów kodowych poszczególnych liści odbywa się poprzez spisywanie etykiet gałęzi przejścia od korzenia do liścia, nigdy w kierunku odwrotnym (wynika to z naturalnego kierunku przejścia od rodzica do dzieci, pozwala rozróżnić potomstwo, choć nieco komplikuje budowę kodera wymuszając konieczność odwrócenia bitów). Idąc od korzenia na kolejnych poziomach formowany jest, w zależności od drogi, przedrostek słów kodowych. Przykładowo, przy ustalaniu słowa liścia z symbolem $b$w drzewie na rys. 1.4a, w węźle wewnętrznym pierwszego poziomu określony jest przedrostek 0, a następnie idąc do prawego syna-liścia otrzymujemy słowo $\varsigma _b=\texttt{01}$ W zależności od wybranego sposobu etykietowania gałęzi, binarne drzewo kodowe (tj. służące do realizacji danego kodu) o określonej strukturze wyznacza wiele kodów o takiej samej długości słów. Słowa te w sposób jednoznaczny opisują drogę przejścia od korzenia do symboli alfabetu $A_S$ przypisanych poszczególnym liściom.

Rys. .4 Etykietowanie drzew binanych: a) drzewo o dwóch wierzchołkach wewnętrznych i trzech liściach z symbolami $a,b,c$ z zaznaczoną relacją rodzic-dzieci oraz ustalonymi słowami kodowymi $\varsigma _a,\varsigma _b,\varsigma _c$; b) trzy inne sposoby etykietowania tego samego drzewa.
 

Przy etykietowaniu drzewa binarnego gałęzie łączące wierzchołek rodzica z dziećmi muszą mieć różne etykiety. Dwa możliwe sposoby etykietowania gałęzi każdego elementarnego poddrzewa (rodzic-dwójka dzieci) to 0 dla połączenia z lewym synem i 1 - z prawym lub odwrotnie (zobacz rys. 1.4a). Skoro istnieją dwie możliwości ustalania przedrostka dzieci każdego wierzchołka wewnętrznego (rodzica), to przy $M$ wierzchołkach wewnętrznych w drzewie mamy $2^M$ różnych sposobów utworzenia słów kodowych. Przykład różnych sposobów etykietowania drzewa o $M=2$ przedstawiono na rys. 1.4. 

W związku z tym, w przypadku budowy drzewa określonego kodu przedrostkowego możliwych jest $2^M$ różnych postaci drzewa binarnego, w zależności od przyjętego sposobu etykietowania. Długość słów poszczególnych symboli alfabetu tego kodu jest określona, czyli odpowiednie liście muszą zawsze znajdować się na tej samej głębokości, chociaż kształt struktury drzewa może być różny.

Długość słowa symbolu danego liścia drzewa jest równa głębokości (numerowi poziomu, licząc od zerowego poziomu korzenia), na jakiej znajduje się liść. Dla drzew z rysunku 1.4 liście $a$i $b$znajdują się na 2 poziomie (na głębokości równej 2), więc mają słowa dwubitowe, zaś liściowi $c$z pierwszego poziomu przypisano słowo jednobitowe. Zmiana sposobu etykietowania nie wpływa na długość poszczególnych słów.

Efektywna postać kodu drzewa binarnego Podstawowy warunek zapewniający efektywność kodu sprowadza się do konstrukcji drzewa, które nie ma zdegenerowanych elementarnych poddrzew, tj. rodzica tylko z jednym dzieckiem. Stąd każdy wierzchołek takiego drzewa, zwanego drzewem lokalnie pełnym, z wyjątkiem korzenia, ma brata. Puste miejsce w zdegenerowanym poddrzewie jest niewykorzystane - brakuje gałęzi z etykietą, dla której zarezerwowano miejsce w drzewie. Zawsze wtedy można zlikwidować wierzchołek rodzica takiego poddrzewa przesuwając na jego miejsce jedyne dziecko (wraz z poddrzewem) i skracając w ten sposób o jeden długość związanego z dzieckiem przedrostka słów liści z jego poddrzewa.

Drzewo lokalnie pełne o zadanej liczbie liści można zbudować, zaczynając np. od struktury z jednym wierzchołkiem, korzeniem, dodając nowe liście zgodnie z poniższą regułą.

Reguła rozbudowy drzewa lokalnie pełnego: wybrany węzeł aktualnej postaci drzewa przenosimy wraz z poddrzewem o jeden poziom niżej, zaś na jego miejsce wstawiamy nowy węzeł wewnętrzny, którego drugim dzieckiem jest nowo dołączany liść.

Drzewo o $N=2$ liściach ma jeden węzeł wewnętrzny, tj. korzeń. Dodanie nowego liścia według tej reguły powoduje, że uzyskujemy drzewo z $N=3$ liśćmi przy dwóch wierzchołkach wewnętrznych. W każdym kolejnym kroku rozbudowy drzewa dochodzi jeden liść i jeden wierzchołek wewnętrzny, a więc liczba wierzchołków wewnętrznych drzewa lokalnie pełnego jest zawsze równa: $M=N-1$. Wszystkich wierzchołków drzewa jest $K=2N-1$. Przykłady drzew przedstawiono na rys.1.5. 

Rys. 1.5 Przykłady drzew: a) lokalnie pełnych; b) nie będących lokalnie pełnymi.

Aby uzyskać postać drzewa, które utraci cechę lokalnej pełności można zmodyfikować opisaną wyżej metodę konstrukcji drzewa lokalnie pełnego w sposób następujący. Wybrany liść przesuwamy poziom niżej, zaś w jego poprzednim miejscu tworzymy wierzchołek wewnętrzny (bez dołączania nowego liścia). W ten sposób powstaje zdegenerowane elementarne poddrzewo, rośnie o jeden liczba węzłów wewnętrznych przy niezmiennej liczbie liści równej $N$. W drzewach  nie będących lokalnie pełnymi o $N$ liściach liczba węzłów wewnętrznych jest więc równa $N$ lub większa, a liczba wszystkich wierzchołków $K>2N-1$.
  
W mniejszym drzewie na rysunku 1.5a liczba wierzchołków $N=2,\ K=3$. Wersja tego drzewa po utracie cechy lokalnej pełności z rys. 1.5b  ma odpowiednio $N=2,\ K=4$ (dwa wierzchołki wewnętrzne plus dwa liście), czyli $K>2N-1$. Nastąpiło wydłużenie długości słowa kodowego symbolu $b$ o jeden bit. Analogicznie większe drzewo z rys. 1.5a ma $N=6,\ K=11$ jego modyfikacja na rys. 1.5b odpowiednio $N=6,\ K=13$ oraz wydłużone słowa symboli $a$i $b$ o jeden bit. 

Każdy wewnętrzny wierzchołek $T$ drzewa lokalnie pełnego o lokalizacji jednoznacznie określonej jego przedrostkiem $\alpha$ ma zawsze dwóch synów: lewego i prawego o przedrostkach $\alpha\texttt{0}$ i $\alpha\texttt{1}$. Przedrostki te muszą pojawić się jako przedrostki słów wszystkich liści występujących w poddrzewie wierzchołka $T$. Stąd w kodzie takiego drzewa każdy przedrostek właściwy $\alpha$ (mający przedłużenie w słowie) dowolnego słowa kodowego $\varsigma _i$ ma przedłużenia $\alpha\texttt{0}$ i $\alpha\texttt{1}$ będące przedrostkami tego słowa oraz innego $\varsigma _j \neq \varsigma _i$. Kod drzewa lokalnie pełnego nazywany jest kodem przedrostkowym pełnym. 

W większym drzewie z rys. 1.5a widać, że dowolny przedrostek związany z wierzchołkiem wewnętrznym ma przedłużenia z dołączonym bitem 0 oraz 1 w przedrostkach dzieci tego wierzchołka, a ostatecznie w słowach liści należących do jego poddrzewa. Z kolei słowa $\varsigma _a = \texttt{0}$ i $\varsigma _b = \texttt{10}$ mniejszego drzewa z rys. 1.5b świadczą o tym, że nie jest on przedrostkowo pełny: przedrostek właściwy $\alpha=\texttt{1}$ słowa $\varsigma _b$ nie ma przedłużenia $\alpha\texttt{1}$ a jedynie przedłużenie $\alpha\texttt{0}$ w słowie symbolu $b$.  

Kody symboli i kody strumieniowe

Kod dwójkowy stałej długości, jak również inne wzmiankowane wyżej przykłady kodów pozwalające lub nie na jednoznaczne dekodowanie tworzonych sekwencji, należą do klasy tzw. kodów symboli (symbol codes). W kodach symboli sekwencja wyjściowa powstaje poprzez przypisanie kolejnym symbolom pojawiającym się na wejściu odpowiednich słów kodowych w schemacie ,,jeden symbol - jedno słowo''. Aby uzyskać efekt kompresji potrzebne jest zróżnicowanie długości poszczególnych słów (w przeciwieństwie do kodu $B_k$, który ustala zwykle oryginalną reprezentację kodowanych danych). Bardziej praktyczne są więc kody o zmiennej długości bitowej słów kodowych (variable-length symbol codes).

Inną, potencjalnie bardziej efektywną grupę metod kodowania stanowią kody strumieniowe (stream codes). W kodach strumieniowych pojedyncze słowo kodowe przypisywane jest ciągowi symboli wejściowych. Może to być ciąg symboli o stałej lub zmiennej długości (np. w koderach słownikowych), a w skrajnym przypadku wszystkim symbolom strumienia wejściowego odpowiada jedno słowo kodowe, będące jednoznacznie dekodowalną reprezentacją danych źródłowych. Takie słowo tworzone jest w koderze arytmetycznym, stanowiącym automat skończony, który w każdym takcie (a więc po wczytaniu kolejnego symbolu wejściowego) wyprowadza (nieraz pustą) sekwencję bitów w zależności od czytanego symbolu i aktualnego stanu automatu.

Jednoznaczna dekodowalność kodów strumieniowych wynika z różnowartościowości przekształcenia sekwencji symboli wejściowych w słowo kodowe (sekwencję kodową). Decydujący wpływ ma tutaj metoda tworzenia słów kodowych, przystosowana do znacznie większego alfabetu możliwych postaci danych wejściowych, zwykle adaptacyjna i bardziej złożona niż w przypadku kodów symboli.

W charakterystyce kodów symboli o zmiennej długości istotną rolę odgrywa także nierówność Krafta-MacMillana. Dotyczy ona kodów jednoznacznie dekodowalnych zawierających $n$słów kodowych o długościach $L_i=|\varsigma _i|$, dla których zachodzi następująca zależność:

Odwrotnie, mając dany zbiór $n$ dodatnich liczb całkowitych $\mbox{\{L_1,..., L_n\}}$ spełniających (1.11) istnieje jednoznacznie dekodowalny kod symboli o długościach kolejnych słów kodowych równych $L_i$.

Nierówność (1.11) jest prawdziwa dla kodów drzew binarnych, co można wykazać na podstawie właściwości struktury drzewa. Dowolną postać drzewa binarnego daje się uzyskać poprzez rozbudowę drzewa najprostszej postaci. Kolejne liście dołączane są w wolnych miejscach istniejącej struktury węzłów lub też poprzez dodanie nowego węzła wewnętrznego. 

Najprostsza (i najbardziej efektywna) postać drzewa z jednym liściem to korzeń z podpiętym bezpośrednio liściem. Mamy wtedy jedno słowo kodowe o długości $L_1=1$ czyli spełniona jest nierówność (1.11). Wstawienie na wolne miejsce (jako drugie dziecko korzenia) drugiego liścia daje dwa słowa kodowe o długościach $L_1=1$i $L_2=1$ wobec czego zachodzi równość $\sum_{i=1}^{2}2^{-L_i}=1$. 

Uzyskaliśmy w ten sposób drzewo lokalnie pełne. Dodanie nowego liścia z zachowaniem lokalnej pełności drzewa może się odbywać według reguły rozbudowy drzewa lokalnie pełnego  stosowanej do dowolnego liścia. Powoduje to następującą zmianę w alfabecie słów kodowych: słowo $\varsigma _i=\alpha$o długości $L_i$ zastępowane jest dwoma słowami postaci $\varsigma _i'=\alpha0$ i $\varsigma _i''=\alpha1$o długości $L_{i+1}$. Odpowiedni składnik sumy z wyrażenia (1.11) się nie zmienia, gdyż $2^{-L_i}=2^{-L_i+1}+2^{-L_i+1}$. Według tej zasady można uzyskać dowolne drzewo lokalnie pełne. Pozwala to stwierdzić, że dla drzew lokalnie pełnych, czyli dla kodu przedrostkowego pełnego zawsze zachodzi równość: $\sum_{i=1}^{n}2^{-L_i}=1$.

Rozbudowa drzewa bez zachowania cechy lokalnej pełności powoduje zmniejszenie efektywności kodu poprzez wydłużenie słów kodowych. Utratę tej cechy powoduje modyfikacja drzewa polegająca na przesunięciu o jeden poziom w dół wierzchołka wraz z całym poddrzewem i ustanowieniu w zwolnionym miejscu nowego węzła wewnętrznego. Operacja ta powoduje wydłużenie długości słów kodowych wszystkich liści tego poddrzewa. Mamy więc $\sum_{i=1}^{n}2^{-L'_i}$ gdzie $L'_i$ to długości słów po modyfikacji. Dla kodu przedrostkowego bez cechy pełności mamy więc zawsze zależność: $\sum_{i=1}^{n}2^{-L_i}$.  

Spełnienie nierówności (1.11) jest warunkiem koniecznym jednoznacznej dekodowalności kodu, nie jest jednak warunkiem wystarczającym (dostatecznym). Potwierdzeniem jest np. kod symboli określony słowami$A_{\mathcal{K}}=\{\texttt{0},\texttt{10},\texttt{110},\texttt{101}\}$ (niewielka modyfikacja kodu $A_{\mathcal{K}_6}$) spełniający(1.11). Przykładowe kody $A_{\mathcal{K}_3}$i $A_{\mathcal{K}_7}$ nie spełniają nierówności (1.11), co dowodzi, że nie są jednoznacznie dekodowalne. Zaś w przypadku kodów $A_{\mathcal{K}_2},A_{\mathcal{K}_4}$i $A_{\mathcal{K}_9}$ zależność ta nie wystarcza do wykazania braku niejednoznacznej dekodowalności.   

Nierówność (1.11) można odnieść do pojęcia informacji własnej związanej z wystąpieniem (z prawdopodobieństwem $p_i$) pojedynczego symbolu kodowanego słowem o długości $L_i$zapisując $L_i=-\log_{2} p_i+\epsilon _i$ gdzie $\epsilon _i$j est nadmiarową|niedomiarową (w stosunku do wartości informacji własnej) długością słowa $L_i$ (wynikającą np. z ograniczenia długości słowa do całkowitej liczby bitów). W wyniku prostych przekształceń $2^{-L_i}=2^{(\log_{2} p_i-\epsilon _i)}=p_i\cdot 2^{-\epsilon _i}$, co pozwala zapisać (1.11) jako $\sum_{i=1}^{n}p_i\cdot 2^{-\epsilon _i}\leq 1$. Jeśli założymy stałą wartość $\epsilon _i=\epsilon$dla wszystkich słów, wtedy $\epsilon \geq 0$. W przypadku, gdy kod dobiera krótsze od informacji własnej słowa kodowe dla wybranych symboli alfabetu, to dla innych symboli słowa muszą być wydłużone (średnio) tak samo lub bardziej. 

Twierdzenia o kodowaniu źródeł

Przy konstruowaniu technik odwracalnej kompresji interesującym jest pytanie o granicę możliwej do uzyskania efektywności kompresji. Intuicyjnie wiadomo, że nie można stworzyć nowej reprezentacji danych o dowolnie małej długości przy zachowaniu pełnej informacji dostarczonej ze źródła. Okazuje się, że entropia łączna $H(S)$ wyznaczona według równań (1.4) dla kodowanego zbioru danych stanowi graniczną (minimalną) wartość średniej bitowej reprezentacji kodowej - jest bowiem miarą ilości informacji pochodzącej ze źródła. Mówią o tym twierdzenia Shannona o kodowaniu źródeł, w tym szczególnie istotne twierdzenie o bezstratnym kodowaniu źródła (tj. z kanałem bezszumnym, z doskonałą rekonstrukcją sekwencji symboli źródła - bez ograniczenia liczby bitów) (noiseless source coding theorem), zwane też pierwszym twierdzeniem Shannona. Według tego twierdzenia, aby zakodować dany proces (sekwencję symboli generowanych przez źródło) o entropii $H(S)$do postaci sekwencji symboli binarnych, na podstawie której możliwe będzie dokładne zdekodowanie (rekonstrukcja) procesu źródłowego, potrzeba co najmniej $H(S)$ symboli binarnych (bitów). Możliwa jest przy tym realizacja schematu kodowania, który pozwoli uzyskać bitową reprezentację informacji z takiego źródła o długości bardzo bliskiej wartości $H(S)$.

Bardziej praktyczna odmiana twierdzenia o bezstratnym kodowaniu źródła dotyczy granicznej efektywności kodowania, osiąganej poprzez kodowanie dużych bloków symboli alfabetu źródła (tj. $N$-tego rozszerzenia źródła, przy zmianie struktury informacji pojedynczej) za pomocą binarnych słów kodowych. Zamiast przypisywania słów kodowych pojedynczym symbolom alfabetu, jak w koderach symboli, koncepcja skuteczniejszego kodera prowadzi w kierunku realizacji kodu strumieniowego, uwzględniając przy tym w możliwie wydajny sposób zależności pomiędzy poszczególnymi symbolami kodowanej sekwencji.

Okazuje się, że zawarta w tym twierdzeniu sugestia o zwiększaniu efektywności kompresji poprzez konstruowanie coraz większych rozszerzeń źródła (rosnące $N$) jest cenną wskazówką, ukazującą kierunek optymalizacji koderów odwracalnych. W dosłownej realizacji tej sugestii występuje jednak problem skutecznego określenia prawdopodobieństw łącznego wystąpienia $N$ symboli źródła na podstawie kodowanego strumienia danych.

Z twierdzenia o bezstratnym kodowaniu źródła jasno wynika, że każde źródło danych może być bezstratnie kodowane przy użyciu kodu jednoznacznie dekodowalnego, którego średnia liczba bitów na symbol źródła jest dowolnie bliska, ale nie mniejsza niż entropia źródła (określona na podstawie prawdopodobieństw występowania poszczególnych symboli i grup symboli źródła) wyrażona w bitach. Jest to naturalne ograniczenie wszystkich metod bezstratnej kompresji odnoszące się do założonych modeli źródeł informacji. Oczywiście użyty model źródła winien jak najlepiej charakteryzować (przybliżać) zbiór danych rzeczywistych. Należy więc podkreślić względność wyznaczanych wartości granicznych wobec przyjętego modelu źródła informacji. Przykładowo, przy konstruowaniu kodera na podstawie modelu źródła bez pamięci, graniczną wartością efektywności tego kodera będzie wartość entropii $H(S_{\mathrm{DMS}})$.

Uzyskanie większej skuteczności kompresji metod bezstratnych jest możliwe poprzez doskonalenie modelu źródła informacji przybliżającego coraz wierniej kompresowany zbiór danych (oryginalnych, współczynników falkowych itp.), nawet kosztem rosnącej złożoności modelu. Potrzeba coraz dokładniej modelować wpływ kontekstu, zarówno za pomocą rozbudowanych, dynamicznych (adaptacyjnych) modeli predykcyjnych, jak też coraz szybciej i pełniej określanych probabilistycznych modeli Markowa nawet wyższych rzędów. Modelowanie musi być skojarzone z efektywnymi rozwiązaniami kodów binarnych (powstających na podstawie tych modeli), pozwalających osiągnąć minimalną długość bitowej sekwencji nowej reprezentacji danych.

Bitowo bezstratna kompresja obrazów oznacza przede wszystkim tworzenie możliwie oszczędnej ich reprezentacji z wykorzystaniem zasad statystycznej teorii informacji do celów archiwizacji. Przez ostatnie ponad 10 lat, od czasu opracowania efektywnych koderów CALIC i według standardu JPEG-LS, nie nastąpił żaden przełom, jakościowy postęp w dziedzinie odwracalnej kompresji obrazów.Wspomniane kodery odwracalne na etapie modelowania źródeł informacji wykorzystują 2W (dwuwymiarową) charakterystykę danych w postaci efektywnych modeli predykcji. 

Obserwuje się natomiast tendencję modelowania źródeł informacji na niższym poziomie bez pośrednich modeli sąsiednich wartości pikseli źródłowych. Uproszczenia prowadza do zamiany: zamiast obiektów piksele, zamiast pikseli - rozkłady map bitowych. Stosuje się modelowanie lokalnych kontekstów wybranych przestrzeni bitowych niekoniecznie skorelowanych z obrazową interpretacją danych, szacowanie zależności danych traktowanych bardziej elementarnie (z uproszczonym alfabetem źródła), a co za tym idzie bardziej uniwersalnie.

W koderach odwracalnych kluczową rolę odgrywają metody modelowania kontekstu przy kodowaniu binarnym (zwykle arytmetycznym). W PPM (prediction with partial string matching) przy modelowaniu prawdopodobieństw warunkowych adaptacyjnego kodera arytmetycznego wykorzystywane są konteksty różnych rozmiarów. Alfabet linii prawdopodobieństw określonego kontekstu rozszerzany jest dynamicznie, tj. niezerowy podprzedział określonego symbolu   pojawia się w linii prawdopodobieństw dopiero wówczas, gdy symbol wystąpi w sekwencji wejściowej poprzedzony tym kontekstem. Ponadto w każdej linii zarezerwowany jest podprzedział symbolu ''PRZEŁĄCZ'', który służy do sygnalizacji zmiany rozmiaru kontekstu (dobierany jest możliwie najdłuższy kontekst zaczynając od kontekstu masymalnego rzędu m). Poszczególne odmiany metody PPM, dostosowane do danych tekstowych, obrazowych, innych, różnią się sposobem określania linii prawdopodobieństw i kontekstów (rozmiarem, kształtem, uproszczeniem statystyki w danym kontekście).

W przypadku, gdy efektywne opisanie jednym kontekstem złożonych lokalnych zależności danych źródłowych nie jest możliwe, stosowane jest niekiedy ważenie kilku modeli prawdopodobieństw bazujących na różnych kontekstach. Jeśli rozkład $P_S^{C_1}$ określono na podstawie kontekstu $C_1$, a $P_S^{C_2}$}  na podstawie $C_2$, wówczas do kodowania można wykorzystać ważony rozkład prawdopodobieństw  $\Big( P_S^{C_1} + P_S^{C_2} \Big)/2$. Metoda ważenia rozkładów prawdopodobieństw z wykorzystaniem struktury drzewa CTW (context-tree weighting) pozwala wykorzystać wszystkie możliwe konteksty i modele kontekstu ograniczone rozmiarem m. CTW bazuje na binarnym alfabecie źródła informacji bez względu na rodzaj kodowanych danych (obraz, dźwięk, tekst itp.). Wymaga to wstępnej konwersji ciągu symboli nad alfabetem $A_S$ w ciąg bitowy (tj. na wstępnej serializacji, jak w standardzie JBIG, czy też w metodzie BKO), kodowany z wykorzystaniem binarnej struktury drzewa określającej konteksty i prawdopodobieństwa modeli źródła z pamięcią i bez do sterowania kodowaniem arytmetycznym.

Do określenia prawdopodobieństw ciągu symboli wykorzystuje się tzw. prawdopodobieństwo blokowe całego bloku bitów, obliczane na podstawie częstości dotychczasowych (w modelu przyczynowym) wystąpień zer i jedynek zakładając model bez pamięci. Zależności pomiędzy danymi uwzględnione zostały w tzw. prawdopodobieństwach ważonych obliczanych w węzłach tworzonego drzewa binarnego.

Inaczej wyznaczane jest też prawdopodobieństwo symboli, tj. według wyrażenia: $P_e(s=a_1)=\frac{n_1+1/2}{n_1+n2+1}$, gdzie alfabet źródła $A_S=\{a_1,a_2\}$ , $n_1$, $n_2$ - liczba wystąpień odpowiednio $a_1$ i $a_2$ w kodowanym dotychczas ciągu źródłowym. $P_e(s=a_2)$ definiowane jest analogicznie.

Coraz większą rolę w praktycznych zastosowaniach odgrywają uniwersalne narzędzia do archiwizacji danych (tzw. archiwizery) wykorzystujące podobne metody statystycznego modelowania źródeł informacji z doborem parametrów zależnie od typu danych. Wykazują one dużą efektywność kompresji skutecznie konkurując z rozwiązaniami dedykowanymi np. kompresji obrazów. Dowodem tego są wyniki licznych eksperymentów, a także przedstawione poniżej rezultaty przeprowadzonych testów własnych (rys. 2.2). 

Rys. 2.2 Porównanie efektywności bezstratnych koderów obrazów. Wykorzystano 29 obrazów testowych w 8 bitowej skali szarości (z prac standaryzacyjnych komitetu JPEG), o nazwach jak na rysunku. Wartości średnich bitowych zbioru wszystkich obrazów testowych dla poszczególnych koderów wynoszą odpowiednio: 4,55 bnp (JPEG\_LS), 4,60 bnp (JPEG2000 VM8.6), 4,75 bnp (JBIG), 4,35 bnp (CALIC), 4,36 (BKO) oraz 4,1 bnp (WinRK v. 2.1.6). Skrót bnp oznacza ''bitów na piksel''.

Uniwersalny archiwizer WinRK (wykorzystujący odmianę metody PPM do modelowania kontekstu) pozwolił w kilku przypadkach na wyraźne zmniejszenie długości zakodowanych danych obrazowych (średnio o blisko 6\%) w stosunku do najefektywniejszego kodera obrazów CALIC. W stosunku do standardów JPEG-LS i JPEG2000 poprawa efektywności sięgnęła odpowiednio 10% i 11%. Nowa wersja WinRK (niestety na obecnym etapie realizacji nieco zbyt złożona obliczeniowo) z algorytmem modelowania PWCM pozwala skrócić skompresowane dane obrazowe o dodatkowe kilka procent.

Dwa uniwersalne kodery map bitowych: według standardu JBIG oraz wykorzystujący nieco bardziej dopasowaną do danych obrazowych metodę serializacji BKO pozwoliły również uzyskać wysoką efektywność kompresji obrazów testowych, przy czym średnia bitowa dla BKO jest na poziomie średniej kodera CALIC. 

Okazuje się, że modele informacji obrazowej wyższego poziomu (obiektowe, predykcyjne, transformacji liniowych) nie usprawniają procesu redukcji nadmiarowości wejściowej reprezentacji danych, są za mało elastyczne w dopasowaniu modeli źródeł do lokalnych (chwilowych) cech sygnału. Są one zaś szczególnie istotne przy porządkowaniu, tworzeniu hierarchii informacji uwzględniając niekiedy przesłanki semantyczne w kompresji selektywnej (więcej o tym w treści wykładu o formowaniu użytecznych reprezentacji w ramach modułu trzeciego.

Opis opracowanej przez D. A. Huffmana w 1952 roku metody kodowania jest najczęściej publikowana publikacją z teorii informacji. Przez lata metodę Huffmana optymalizowano ze względu na rosnący stopień różnych form adaptacji. Wykorzystywano ją także w szeregu standardów dotyczących kodowania faksów (a więc obrazów dwupoziomych) Grupy 3 i Grupy 4, kompresji obrazów wielopoziomych JPEG, czy też sekwencji obrazów MPEG-1 i MPEG-2, wykorzystywanych do dziś.

Algorytm

Kod Huffmana jest optymalny w kategorii kodów symboli realizując podstawową zasadę różnicowania długości słów kodowych symboli ze względu na przewidywana częstość ich występowania w kodowanym strumieniu danych. Konstrukcja słów kodowych realizowana jest za pomocą drzewa binarnego, budowanego od liści do korzenia na podstawie rozkładu wag łączonych kolejno liści.

Inicjalizacja algorytmu zakłada ustalenie zbioru wolnych węzłów zewnętrznych -- liści z przypisanymi im symbolami alfabetu oraz wagami. Początkowo, dwa węzły o najmniejszych wagach łączone są ze sobą w elementarne poddrzewo, z wierzchołkiem rodzica o wadze równej sumie wag węzłów łączonych. Następnie wyszukiwane i łączone ze sobą są kolejne wierzchołki o najniższych wagach (wśród pozostałych liści i wierzchołków poddrzew), tworząc kolejne poziomy drzewa, aż do podłączenia wszystkich wolnych węzłów. Algorytm ten zobrazowano na rys. 2.3. Dwa liście symboli o najmniejszych wagach $w_1$ i $w_2$ połączono tworząc elementarne poddrzewo $T_{1+2}$, ustalając przy tym odpowiednią wagę rodzica, reprezentowanego teraz na liście wolnych węzłów. W kolejnych krokach maleje liczba wolnych węzłów, aż do utworzenia pełnej struktury drzewa.

Rys. 2.4 Przykładowa inicjalizacja metody Huffmana: a) utworzenie elementarnego poddrzewa poprzez łączenie dwóch węzłów o najmniejszych wagach; b)zestaw wolnych węzłów podlegający analizie w kolejnym kroku algorytmu.
 

Taka procedura tworzenia drzewa zapewnia, że:

• liść symbolu o najmniejszej wadze ma najdłuższe słowo, leżąc najgłębiej w drzewie na poziomie $m_{\max}$;
• liść symbolu o drugiej w kolejności najmniejszej wadze należy do tego samego, elementarnego poddrzewa, a więc leży również na poziomie $m_{\max}$, gdyż jedynie drzewo lokalnie pełne jest efektywne w kodowaniu. 

W ten sposób symbole o wagach mniejszych znajdą się na niższych poziomach (lub najwyżej równych) w stosunku do liści symboli o większych wagach. Konsekwencją będą niekrótsze słowa kodowe, co dowodzi optymalności konstruowanego iteracyjnie według powyższej zasady drzewa kodowego. Kryterium optymalizacji określa postać wyrażenia: $\sum_{a_i \in A_S} w_i|\varsigma _i|$  , minimalizowana po wszystkich możliwych postaciach drzewa binarnego z ustalonym alfabetem symboli przypisanych liściom zewnętrznym drzewa. 

Podsumowując, algorytm kodu Huffmana przedstawia się następująco: 

Algorytm 2.1 Kod Huffmana 

1. Określ wagi wszystkich symboli alfabetu (na podstawie liczby wystąpień w wejściowym ciągu danych); symbole te wraz z wagami przypisz liściom konstruowanej struktury drzewa binarnego, stanowiącym początkowy zbiór tzw. wierzchołków wolnych (tj. wierzchołków, które mogą być łączone w elementarne poddrzewa z węzłem rodzica umieszczonym na wyższym poziomie drzewa).
2. Sortuj listę wierzchołków wolnych w porządku nierosnącym wartości ich wag.
3. Odszukaj dwa wolne wierzchołki z najmniejszymi wagami i połącz je z nowotworzonym węzłem rodzica w elementarne poddrzewo; wagę nowego wierzchołka ustal jako sumę wag dzieci.
4. Usuń z listy wierzchołków wolnych dwa węzły o najmniejszych wagach; wpisz na tę listę nowy wierzchołek rodzica.
5. Przypisz gałęziom prowadzącym od rodzica do węzłów-dzieci etykiety: 0 i 1 (np. lewa gałąź - 0, prawa - 1).
6. Powtarzaj kroki 3-5 aż do momentu, gdy na liście wierzchołków wolnych pozostanie tylko jeden węzeł - korzeń drzewa.
7. Odczytaj ze struktury drzewa słowa kodowe kolejnych liści (czyli przypisanych im symboli); słowo stanowią łączone binarne etykiety kolejnych gałęzi odczytane przy przejściu od korzenia do danego liścia (od najbardziej znaczącego bitu gałęzi korzenia do najmniej znaczącego bitu gałęzi dochodzącej do liścia).

Proces dekodowania przebiega jak w metodzie S-F, jedynie w p. 2 budowane jest drzewo według kodu Huffmana (algorytm 2.1)

Algorytm 2.2  Dekodowanie metodą Huffmana

1. Pobierz ze zbioru danych zakodowanych wartości prawdopodobieństw występowania (wagi) poszczególnych symboli alfabetu.
2. Zbuduj drzewo binarne jak w kodzie Huffmana.
3. Dekodowanie kolejnych symboli (prostsza realizacja algorytmu 1.3 dzięki wykorzystaniu struktury drzewa): 
   1. ustaw korzeń drzewa jako aktualny węzeł;
   2. pobierz bit z wejścia: jeśli wczytano 0 to przejdź do lewego syna aktualnego węzła, w przeciwnym razie (wpr) przejdź do jego prawego syna;
   3. jeśli aktualny węzeł to węzeł wewnętrzny -- kontynuuj (b), wpr odczytaj symbol przypisany liściowi, prześlij go na wyjście i powtarzaj od (a) aż do wyczerpania zbioru danych wejściowych. 

Prześledźmy działanie algorytmu Huffmana na następującym przykładzie.

Przyklad 2.1 Kodowanie metodą Huffmana
Dany jest źródłowy ciąg symboli o alfabecie: $A_S=\{A, B, C, D, E\}$, przy czym częstość występowania poszczególnych symboli przedstawia tabela 2.1.

Tab. 2.1 Symbole alfabetu przykładowego zbioru danych wraz z  częstością wystąpień.

Sposób konstrukcji binarnego drzewa kodowego za pomocą algorytmu 2.1 został przedstawiony na rys. 2.4.

Rys_. 2.4 Binarne drzewo kodowe Huffmana z przykładu 2.1. Pochyloną czcionką oznaczono wagi poszczególnych wierzchołków.

//Słowa kodowe przyporządkowane poszczególnym symbolom alfabetu  przedstawiają się następująco: $A\rightarrow \texttt{100},\ B \rightarrow\texttt{0},\ C\rightarrow \texttt{110},\ D\rightarrow \texttt{101},\ E\rightarrow\texttt{111}$. Najczęściej występującemu symbolowi $B$ przypisano jednobitowe słowo kodowe, podczas gdy pozostałym -- trójbitowe. Długości słów kodowych przypisanych poszczególnym symbolom nie oddają w pełni rozkładu ich wag, co jest spowodowane podstawowym ograniczeniem kategorii kodów symboli. Całkowita liczba bitów każdego ze słów zmusza do zaokrągleń wartości entropii własnej, będącej miarą informacji występującej przy pojawieniu się poszczególnych symboli -- zobacz tabelę 2.2. Obliczono w niej efektywność wyznaczonego drzewa  Huffmana. Średnia długość słowa kodowego wynosi $\bar L_\text{Huff}=2,226$, co jest wartością bliską entropii rozważanego źródła informacji, zakładając model bez pamięci:  $H(S_{\textrm{DMS}})=2,176$.  
Tab. 2.2 Efektywność kodu Huffmana dla danych z przykładu 2.1. Zestawiono ilość informacji związaną z wystąpieniem poszczególnych symboli alfabetu z tabeli 2.1 z uzyskaną efektywnością reprezentacji kodowej. W tabeli znajdują się wartości oszacowanych prawdopodobieństw poszczególnych symboli $P(a_i)=N(a_i)/\sum_j N(a_j)$, informacji własnej $I(a_i)$, całkowitej informacji związanej z występowaniem danego symbolu oraz długości słów kodowych i zakodowanej reprezentacji.

Sposób konstrukcji słów kodowych metodą Huffmana według algorytmu 2.1  nie zależy od kolejności wystąpienia symboli w strumieniu wejściowym, gdyż bazuje na posortowanym zbiorze symboli alfabetu. Jeśli symbole  pojawią się seriami: $6 \times A,\ 12 \times B,\ 4\times C,\ 5\times D$ i $4 \times E$, to wystarczy zakodować  liczbę wystąpień kolejnych symboli na czterech bitach, a sam symbol na trzech (zasada RLE), by uzyskać 35 bitową sekwencję kodową jednoznacznie dekodowalną, znacznie krótszą od 69-bitowej reprezentacji Huffmana. Wskazuje to na poważne ograniczenie efektywności kodów symboli budowanych na bazie źródeł bez pamięci, które nie uwzględniają zależności w występujących bezpośrednio po sobie ciągach wartości. Wadę tę częściowo eliminuje np. adaptacyjna metoda Huffmana, jak też stosowanie modeli źródeł z pamięcią i kodów strumieniowych.

Adaptacyjna wersja kodu Huffmana pozwala na bieżące kształtowanie rozkładów prawdopodobieństw występowania symboli, zależnie od lokalnych statystyk w modelu przyczynowym (z uwzględnieniem jedynie danych już zakodowanych). Drzewo  Huffmana jest wtedy stale modyfikowane, zależnie od naliczanych statystyk i aktualizowanych wag poszczególnych symboli, przy czym węzły na poszczególnych poziomach drzewa rozmieszczone są według ustalonego porządku wag (porządek niemalejący od liści do korzenia, zaś na poszczególnych poziomach -- np. od lewej do prawej).  Po zakodowaniu kolejnego symbolu waga odpowiedniego liścia jest inkrementowana, a drzewo korygowane, jeśli zaburzony został przyjęty porządek (tj. gdy węzeł o wyższej wadze znalazł się za węzłem o wadze niższej -- następuje wtedy zamiana). Taka sama procedura adaptacyjnej modyfikacji struktury drzewa Huffmana jest precyzyjnie powtarzana w dekoderze celem wiernej rekonstrukcji sekwencji źródłowej. Adaptacyjna postać algorytmu kodowania jest więc związana z większą złożonością obliczeniową. w typowych implementacjach wzrost ten wynosi 50-100%. 

Kod Golomba należy do szerszej rodziny kodów przedziałowych, które znalazły zastosowanie w standardach multimedialnych, m.in. w JPEG-LS  i H.264. Wyróżnikiem kodów przedziałowych jest potencjalnie nieograniczony alfabet źródła informacji dzielony na przedziały. Słowa kodowe symboli konstruowane są jako  konkatenacja (zlepienie) przedrostka wskazującego na przedział z wyróżnikiem konkretnego elementu danego przedziału. W przypadku kodu Golomba jest to zlepienie odpowiedniego słowa kodu unarnego ze słowem kodu dwójkowego prawie stałej długości. 

Kod dwójkowy prawie stałej długości

Aby uzyskać oszczędniejszą reprezentację kodu dwójkowego (niż za pomocą kodu z p. 1.2.4) przy lic$\lfloor \log_2 n\rfloor$bitów kodu binarnego prawie stałej długości, pozostałym zaś -- $\lceil \log_2 n\rceil$ bitów, zachowując jednoznaczną dekodowalność kodu.

Dokładniej, w kodzie dwójkowym prawie stałej długości $\hat{B}_n$ (dla n-elementowego alfabetu $A_S=\{a_0,\ldots,a_{n-1}\}$pierwszym r symbolom (o indeksie $0\leq i <  r$) przypisywane są słowa $k=\lfloor \log_2 n \rfloor$ bitowe postaci $\hat{B}_n(a_i)=B_k(i)$, a pozostałym - słowa o długości $k+1$ bitów postaci $\hat{B}_n(a_i)=B_{k+1}(r+i)$, gdzie$r=2^{\lceil \log_2 n \rceil}-n$.

Oczywiście, dla źródeł o alfabecie zawierającym $n=2^i,\ i=1,2,\ldots$ symboli, otrzymujemy  $\hat{B}_n=B_{\log_2 n}$, podczas gdy $r=0$. Oznacza to, że kod dwójkowy prawie stałej długości przyjmuje postać kodu stałej długości. 

Przykład 2.2 Kod dwójkowy prawie stałej długości

Ustalmy postać słów kodu  $\hat{B}_n$ dla symboli dwóch alfabetów o odpowiednio $n=3$ oraz $n=5$, sprawdzając jednoznaczną dekodowalność takiego kodu. 
W pierwszym przypadku mamy:  $r=2^{\lceil \log_2 3 \rceil}-3=1$ oraz długość krótszego słowa$k=\lfloor \log_2 3\rfloor=1$. Wtedy  pierwszy symbol alfabetu otrzyma jednobitowe słowo kodowe $\varsigma _0=\hat{B}_3(a_0)=B_1(0)=\texttt{0}$, dwa pozostałe zaś słowa dwubitowe, odpowiednio $\varsigma _1=\hat{B}_3(a_1)=B_2(1+1)=\texttt{10}$ i $\varsigma _2=\hat{B}_3(a_2)=B_2(3)=\texttt{11}$. $\hat{B}_3$ jest  kodem przedrostkowym, jest więc jednoznacznie dekodowalny. Analogicznie, dla $n=5$ otrzymujemy : $r=2^{\lceil \log_2 5 \rceil}-5=3$ oraz $k=\lfloor \log_2 5\rfloor = 2$. Trzy krótsze, dwubitowe słowa kodowe to $\varsigma _0=\hat{B}_5(a_0)=B_2(0)=\texttt{00}$, $\varsigma _1=\hat{B}_5(a_1)=B_2(1)=\texttt{01}$ i $\varsigma _2=\hat{B}_5(a_2)=B_2(2)=\texttt{10}$, a pozostałe: $\varsigma _3=\hat{B}_5(a_3)=B_3(3+3)=\texttt{110}$ i $\varsigma _4=\hat{B}_5(a_4)=B_3(7)=\texttt{111}$. $\hat{B}_5$ jest także kodem przedrostkowym.

W kodzie $\hat{B}_n$ słowa kodowe tworzone są jedynie na podstawie pozycji (indeksu) danego symbolu w alfabecie, bez analizy rozkładu wag poszczególnych symboli. Długość tych słów jest minimalnie zróżnicowana, a więc ich efektywne wykorzystanie w algorytmach kodowania jest możliwe szczególnie w przypadku źródeł o stosunkowo równomiernym (tj. zrównoważonym) rozkładzie prawdopodobieństw symboli. Pokazuje to następujący przykład.

Przyklad 2.3 Efektywność kodu dwójkowego

Wyznaczmy słowa kodu Huffmana dla źródła opisanego zbiorem prawdopodobieństw: $P_S=\{p_0,\ldots,p_5\}=\{1/5,\ 1/5,\ 3/20,\ 3/20,\ 3/20,\ 3/20\}$.
Stosując algorytm 2.1 można skonstruować drzewo Huffmana jak na rys. 2.5. Postać tego drzewa jest \emph{znormalizowana}, tj. liście są uszeregowane w porządku od lewej do prawej według niemalejącej głębokości (każde drzewo Huffmana można znormalizować zamieniając odpowiednio miejscami węzły tego samego poziomu, jeśli relacja maksymalnej głębokości liści ich poddrzew nie jest zgodna z porządkiem uszeregowania -- mechanizm wykorzystywany w algorytmach adaptacyjnych). 
Odczytane z drzewa słowa kodowe kolejnych symboli są następujące: $\varsigma _0=\texttt{00}$, $\varsigma _0=\texttt{01}$, $\varsigma _2=\texttt{100}$, $\varsigma _3=\texttt{101}, \varsigma _4=\texttt{110}$ i $\varsigma _5=\texttt{111}$. Są one identyczne ze słowami kodu $\hat{B}_6$ pod warunkiem uporządkowania symboli alfabetu zgodnie z nierosnącym ich prawdopodobieństwem. Oznacza to, że w tym przypadku kod dwójkowy prawie stałej długości jest równoważny znormalizowanemu kodowi Huffmana, optymalnemu w kategorii kodów symboli.

Rys. 2.5 Znormalizowane drzewo Huffmana konstruowane dla zrównoważonego rozkładu prawdopodobieństwa symboli alfabetu z przykładu 2.3, z typowym etykietowaniem gałęzi; drzewo to daje słowa kodowe jak w kodzie dwójkowym prawie stałej długości.

Okazuje się, że rozkład prawdopodobieństw symboli źródła z przykładu 2.3 jest zrównoważony, tj. suma dwóch najmniejszych prawdopodobieństw rozkładu jest większa od prawdopodobieństwa największego. Dla takich źródeł, po uporządkowaniu symboli alfabetu zgodnie z nierosnącym ich prawdopodobieństwem, kod dwójkowy prawie stałej długości jest optymalnym kodem symboli. 

Kod unarny

Kod unarny wykorzystuje prostą regułę tworzenia kolejnych słów kodowych symboli alfabetu o potencjalnie nieograniczonej długości. Każde ze słów ustalane jest niezależnie, jedynie na podstawie wskazania pozycji symbolu (lub całego przedziału symboli) w hipotetycznym alfabecie.

Według przedrostkowego kodu unarnego, kolejnym symbolom alfabetu przypisywane są słowa postaci: 1, 01, 001, 0001, $\ldots$ lub w logice odwróconej: 0, 10, 110, 1110, $\ldots$. Definicja kodu unarnego $U(i)$ dla dowolnej, całkowitej $i\geq 0$, będącej elementem alfabetu liczb lub indeksem symbolu alfabetu niesprecyzowanej postaci, jest następująca: $U(i)\triangleq \underbrace{\texttt{0\ldots0}}_{i\ \text{razy}}\texttt{1}$ lub $\bar{U}(i)\triangleq \underbrace{\texttt{1\ldots1}}_{i\ \text{razy}}\texttt{0}$.

Za pomocą $U(i)$ można szybko określić słowa dowolnie rozszerzanego alfabetu. Kod ten można wykorzystać do efektywnej kompresji strumienia danych z liczbami naturalnymi (z zerem), przy założeniu: $\forall_i \ i$ jest nie mniej prawdopodobna niż $i-1$. Długość kolejnych słów kodowych $\varsigma _i$ różni się o jeden: $L_i=|\varsigma _i|=L_{i-1}+1$. Ponieważ w kodzie efektywnym długość słowa powinna być równa (proporcjonalna do) informacji własnej danego symbolu $L_i=-\log_2{p_i}$, to kod unarny jest najbardziej efektywny w przypadku, gdy wartości prawdopodobieństw symboli $p_i$ maleją z potęgą dwójki.

Wyobraźmy sobie, że kodowany strumień danych pochodzi ze źródła informacji o alfabecie $A_S=\{0,1,2,\ldots\}$, czyli $a_i=i$, zaś rozkład prawdopodobieństw symboli alfabetu wynosi $P_S=\{\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\ldots\}$, czyli p$p_i=2^{-(i+1)}$. Słowa kodu unarnego przypisane kolejnym symbolom tego źródła mają długości odpowiednio$L_0=1$, $L_1=2$, $L_2=3,\ldots$, czyli $L_i=i+1$. Obliczając średnią bitową takiego kodu mamy:

czyli rozkład długości słów dokładnie odpowiada rozkładowi entropii źródła informacji.
Kod unarny jest więc w tym przypadku kodem optymalnym.

Zależność na  $p_i=2^{-(i+1)},\ i=0,1,2,\ldots$ jest szczególnym przypadkiem rozkładu geometrycznego $p_i=(1-\rho )\rho ^i$ dla $\rho =\frac{1}{2}$. Kod unarny jest optymalny dla wszystkich rozkładów geometrycznych z $\rho \leq \frac{1}{2}$, tj. pozwala uzyskać w tym przypadku rozkład długości słów jak w kodzie Huffmana. Ponieważ przy $\rho$ przyrost informacji własnej kolejnych symboli jest większy od 1 bit/symbol, to zróżnicowane o jeden bit słowa są również optymalne.  Warunkiem koniecznym jest jednak uporządkowanie symboli alfabetu według nierosnących prawdopodobieństw ich występowania.

Jednak dla rozkładów geometrycznych z $\rho >\frac{1}{2}$ informacja własna kolejnych symboli alfabetu narasta wolniej niż 1 bit/symbol, czyli wolniej od wydłużanego o 1 bit słowa kolejnych symboli. Znaczy to, że kod unarny przestaje być wówczas rozwiązaniem optymalnym. Średni przyrost długości słowa kodowego na symbol mniejszy od 1 bita  można uzyskać za pomocą kodu Golomba, łączącego kod unarny (z szybszym przyrostem długości słowa o nieograniczonej precyzji) z kodem dwójkowym prawie stałej długości (o znacznie wolniejszym przyroście długości słowa o ograniczonej precyzji). Okazuje się, że dla rozkładów geometrycznych z $\rho >\frac{1}{2}$ kod Golomba z odpowiednio dobranym parametrem (rzędem) jest optymalnym kodem symboli.

Konstrukcja kodu Golomba 

Rząd kodu Golomba $m \in \mathbb{Z}^+$ określa stały rozmiar przedziału przy podziale potencjalnie nieskończonego alfabetu według zasady:

Słowo kodowe kodu Golomba $G_m(a_i)$ symbolu $a_i \in \pi^{(m)}_u$ składa się z wskaźnika tego przedziału $u=\lfloor i/m \rfloor$, zapisanego w kodzie unarnym, oraz względnego miejsca symbolu w przedziale $k=i\mod m$, $k\in \{0,1,\ldots,m-1\}$. Mamy więc $G_m(a_i)=U(u)\hat{B}_m(a_k)$ lub alternatywnie $\bar{G}_m(a_i)=\bar{U}(u)\hat{B}_m(a_k)$.

Efektywność kodu Golomba warunkowana jest uporządkowaniem realnego alfabetu kodowanych symboli, tak że $p_i \geq p_{i+1}$ oraz właściwym doborem wartość $m$. Ustalenie tego parametru związane jest bezpośrednio z wartością $\rho$, charakteryzującą rozkład geometryczny (zobacz rys. 2.6), możliwie wiernie aproksymujący rozkład prawdopodobieństw uporządkowanego alfabetu źródła. Szybsze opadanie funkcji rozkładu (mniejsze $\rho$) wymaga krótszych przedziałów, wolniejsze - dłuższych. 

Rys. 2.6  Rozkład geometryczny (jednostronny) dla wartości $\rho$: 0,5, 0,7, 0,9.

Wyznaczanie poszczególnych słow kodu Golomba jest proste obliczeniowo. Postać drzew binarnych kodu różnego rzędu ukazuje ich zasadnicze właściwości. Widać to w przykładzie 2.4.

Przyklad 2.4 Kod Golomba
Wyznaczmy słowo kodowe Golomba rzędu m=3 dla i=14. Ustalając wartość $u=\lfloor 14/3 \rfloor=4$ uzyskujemy przedrostek $U(4)=\texttt{00001}$, zaś przy $k=14\mod 3=2$ musimy wyznaczyć słowo kodu dwójkowego $\hat{B}_3(2)$ Obliczmy więc $r=2^{\lceil \log_2 3\rceil}-3=1$, czyli $k\geq r$, stąd $\hat{B}_3(2)=B_{\lceil \log_{2}{3}\rceil}(2+1)=B_2(3)=\texttt{11}$. Poprzez konkatenację otrzymujemy $G_3(a_{13})=U(4)\hat{B}_3(1)=\texttt{00001}\ \texttt{11}$.

Zestawienie słów kodu Golomba dla kolejnych liczb całkowitych nieujemnych przedstawiono w tab. 2.3. Z kolei  binarne drzewa pierwszych słów kodów $G_1, G_2, G_3$ i $G_4$ zamieszczono na rys.2.7. W pierwszym drzewie (dla $m=1$) od ścieżki prawych synów odchodzą tylko liście (jako lewi synowie kolejnych węzłów wewnętrznych). 

Rys. 2.7 Wybrane drzewa Golomba dla kodów rzędu: a) m=1, b) m=2, c) m=3, d) m=4.

W kolejnych węzłach wewnętrznych ścieżki prawych synów podpięte są poddrzewa, początkowo składające się z pojedynczych liści (dla m=1), aż do pełnych poddrzew przy m=4. Przy rosnącym m daje to efekt stopniowego równoważenia drzewa, czyli lepszego dopasowanie do rozkładów geometrycznych o mniejszych nachyleniach (większym $\rho$). 

Tab. 2.3 Przykładowe słowa kodu Golomba różnych rzędów dla kolejnych liczb całkowitych $i\geq 0$; przy m=1 występują tylko słowa kodu unarnego;  | oznacza miejsce sklejenia słowów kodu unarnego oraz dwójkowego prawie stałej długości.

Kod wykładniczy

Przykładem kodu przedziałowego o zmiennym rozmiarze przedziału jest wykładniczy kod Golomba (exp_Golomb), zastosowany w koderze CAVLC (Context based Adaptive Variable Length Coding) standardu H.264. 

Słowa kodowe kodu exp_Golomb konstruowane są według reguły:  

gdzie $$m=\lfloor \log_2 (i+1)\rfloor$. Przykładowe słowa kodu zebrano w tabeli 2.4.

Tab. 2.4 Pierwsze, kolejne słowa wykładniczego kodu przedziałowego.

Charakterystyczną cechą tej wersji kodu Golomba jest wykładniczo rosnąca długość przedziału, równa $2^m$.

Mechanizm kwantyzacji, w najprostszej, skalarnej i równomiernej wersji przedstawiony na rys.2.8 rozumiany jest w algorytmach kompresji jako złożenie dwu odwzorowań: 

• kodera (kwantyzacja prosta): jako odwzorowanie nieskończonego (skończonego dużego) zbioru wartości rzeczywistych dziedziny, określonego i podzielonego na przedziały (na rysunku wzdłuż osi x), na zbiór  indeksów przedziałów kwantyzacji, dzielących dziedzinę  w sposób rozłączny i zupełny; indeksy $d_i \in \{\ldots, -4, -3, -2, -1, 1, 2, 3, 4, \ldots\}$ wskazują przedziały, do których wpadają kolejne dane wejściowe $x_i$; wartości $d_i$  są w dalszej kolejności bezstratnie kodowane;
• dekodera (kwantyzacja odwrotna): jako odwzorowanie zbioru indeksów $d_i$ w zbiór rzeczywistych,  rekonstruowanych wartości  $y_i$ -- reprezentantów przyporządkowanych przedziałów kwantyzacji.

Rys. 2.8 Opis prostych schematów kwantyzacji skalarnej, równomiernej jako odwzorowania  nieskończonego, ciągłego zbioru wartości (reprezentowanego osią x) w skończony zbiór dyskretny (poziomy wzdłuż osi y): a) bez zera, b) z zerem. Poniżej, uproszczony wykres jednej osi x z naniesionymi wartościami rekonstrukcji w kolejnych przedziałach kwantyzacji -- odpowiednio dla schematów bez zera i z zerem: c).

Kwantyzator jest jednoznacznie zdefiniowany przez zbiór przedziałów kwantyzacji (de facto zbiór punktów granicznych, dzielących zakres wartości sygnału wejściowego na te przedziały) oraz zbiór wartości rekonstruowanych. Wartość rekonstrukcji powinna przybliżać zbiór wartości kwantowanych, należących do danego przedziału, w sposób możliwie wiarygodny, tj. minimalizujący zniekształcenie (błąd kwantyzacji) według przyjętej miary. Jeśli operator kwantyzacji (tj. połączonych funkcji kodera i dekodera) oznaczymy przez $Q(\cdot)$, a ciąg $K$ wartości wejściowych przez $X=\{x_i\}_{i=1}^K$, to w wyniku procesu kwantyzacji tych wartości do $M$ poziomów alfabetu rekonstrukcji $Y=\{y_j\}_{j=1}^M$, otrzymujemy ciąg wartości rekonstruowanych $\tilde{X}=\{\tilde{x}_i\}_{i=1}^K$  przybliżający sygnał oryginalny. Kwantyzacja jest więc przekształceniem:

przy czym $\tilde{x}_i=y_j$, jeśli $x_i \in [\beta_{j-1},\beta_j)$, a $\{\beta_j\}_{j=0}^M$  to granice przedziałów kwantyzacji $B_1,B_2,\ldots,B_M$. Jakość tego przybliżenia określa błąd kwantyzacji $D_Q(X,\tilde{X})=D_Q$. Jedną z najczęściej stosowanych miar jest średniokwadratowy błąd kwantyzacji postaci $D_Q=\frac{1}{K}\sum_{i=1}^{K}(x_i=\tilde{x}_i)^2$.

Uśrednienie błędu kwantyzacji po wszystkich próbach wymusza minimalizację tego błędu w skali globalnej. Korzystniej jest, przy założeniu danej liczby przedziałów, zagęścić przedziały kwantyzacji w obszarach skali wartości licznie pokrytych przez dane wejściowe (histogramowe maksima), zapewniając wierniejszą rekonstrukcję danych dominujących.  Uzależnienie schematu kwantyzacji od estymaty funkcji gęstości prawdopodobieństwa zmiennej $X$ prowadzi do kwantyzacji nierównomiernej (ze zróżnicowanym rozmiarem przedziałów kwantyzacji -- zobacz rys. 2.9), realizowany  metodą Lloyda-Maxa. 

Rys. 2.9 Przykłady projektowania schematu kwantyzacji zależnie od postaci estymowanej funkcji gęstości prawdopodobieństwa $p(x)$ zmiennej opisującej  zbiór danych wejściowych: a) kwantyzacja równomierna; b) nierównomierna.R

Można wykazać, że optymalny średniokwadratowo model kwantyzacji spełnia następujące dwa warunki centroidu i najbliższego sąsiada:

• mając dane przedziały kwantyzacji (przypisane do funkcji kodera), najlepszym odwzorowaniem liczb całkowitych indeksów kwantyzacji w zbiór wartości rekonstruowanych (funkcja dekodera) są środki masy (centroidy) tych przedziałów kwantyzacji, obliczane według

• mając dany zbiór poziomów rekonstrukcji (dekoder), najlepszym określeniem przedziałów kwantyzacji jest ustalenie położenia punktów granicznych w środku pomiędzy kolejnymi wartościami rekonstrukcji, według reguły

odpowiada to przypisaniu każdej wartości wejściowej do najbliższej odległościowo wartości rekonstrukcji.

Często wykorzystywanym w kompresji rozwiązaniem jest optymalizacja kwantyzatora z kryterium uwzględniającym entropię strumienia indeksów kwantyzacji. Wymaga ono poruszania się w przestrzeni R-D (Rate-Distortion), ustalając najlepszą relację pomiędzy uzyskiwaną średnią bitową strumienia (jego entropią) a wartością błędu kwantyzacji. Chodzi o równoczesne zmniejszanie obu tych wielkości do pewnej granicy, zależnej przede wszystkim od rodzaju kwantyzacji, właściowości $X$, jak również od sposobu kodowania wartości wyjściowych kwantyzatora. 

Wektorowa kwantyzacja jest uogólnieniem kwantyzacji skalarnej (zobacz p. 2.1.1) na przypadek wielowymiarowych wektorów. Podstawowe zasady konstrukcji kwantyzatora są bardzo podobne, z tym że w miejsce przedziałów kwantyzacji pojawiają się regiony decyzyjne określone w wielowymiarowej przestrzeni wektorów, a zbiór wartości rekonstruowanych zastąpiony jest książką kodów zawierającą wektory rekonstruowane, zwane wektorami kodu. Każdemu wektorowi kodu przyporządkowany jest indeks - kolejne słowo kodowe. Indeksy wskazujące na reprezentantów z książki kodów, przybliżających kolejne wejściowe wektory danych stanowią bitowy strumień nowej, stratnej reprezentacji oryginalnego zbioru danych. Podstawowy schemat metody kompresji bazujący na wektorowej kwantyzacji przedstawiono na rys. 10.

Rys. 2.10 Istota metody kompresji wektorowej kwantyzacji, zamieniającej wektory danych źródłowych na indeksy książki kodów, wskazujące odpowiednie wektory przybliżeń.

Według teorii informacji łączna kwantyzacja sekwencji zmiennych losowych, pomiędzy którymi występuje zależność, jest zawsze lepsza od niezależnej kwantyzacji każdej zmiennej. Tak więc wektorowa kwantyzacja (vector quantization - VQ), eliminująca zależności pomiędzy kolejnymi zmiennymi losowymi, jest skuteczniejsza od kwantyzacji skalarnej (scalar quantization - SQ). Jedynie w przypadku, gdy te zmienne losowe są niezależne (jeśli można je np. opisać wielowymiarowym rozkładem Gaussa), zastosowanie SQ daje wyniki porównywalne z VQ.

W praktyce zastosowanie VQ w algorytmach kompresji napotyka jednak na szereg problemów. Mała wymiarowość wektorów nie daje satysfakcjonującej skuteczności kompresji. Przykładowo, bloki o rozmiarach 2$\times$2 czy 4$\times$4 formowane z obrazów, stanowią wektory odpowiednio 4-ro i 16-to elementowe o ograniczonej podatności na kwantyzację. Jeśli natomiast użyjemy bloków o większych rozmiarach, np. 8$\times$8 czy 16$\times$16, zwiększając wymiarowość wektorów, a co za tym idzie potencjalną skuteczność algorytmu kwantyzacji, wówczas okazuje się, że zbyt duże rozmiary wektorów stają się z kolei mało przydatne w praktycznych aplikacjach VQ ze względu na trudności realizacyjne. Gubione są bowiem szczegóły informacji wejściowej ze względu na zbyt zgrubne przybliżenia wektorami rekonstrukcji. Wynika to z konieczności ograniczenia rozmiarów książki kodowej, a co za tym idzie liczby wektorów kodu. Zbyt duże książki kodowe wymagają bowiem bardzo czasochłonnych algorytmów przeszukiwań oraz olbrzymich pamięci do ich przechowywania. Powodem ograniczenia wymiarowości wektorów w VQ jest także konieczność określenia wielowymiarowej funkcji gęstości prawdopodobieństwa zmiennej losowej, modelującej wartości wektorów w przestrzeni danych, przy konstrukcji optymalnych wektorów kodu. Wiarygodna estymata takiego rozkładu wymaga dużego zbioru treningowego o własnościach zbliżonych do kompresowanych zbiorów danych. Jeśli zwiększamy wymiarowość przestrzeni wektorów, wówczas przy tej samej ilości zbiorów treningowych maleje rzetelność wyznaczanej coraz bardziej złożonej wielowymiarowej funkcji gęstości (zjawisko analogiczne do rozrzedzania kontekstu bezstratnych koderów z modelami statystycznymi wyższych rzędów). Brak jest poza tym praktycznych rozwiązań pozwalających wyznaczyć optymalny zbiór wektorów kodu w skali globalnej całej przestrzeni wektorów danych (uogólniony na wiele wymiarów algorytm Lloyda-Maxa znajduje minima lokalne). Stosowane algorytmy wektorowej kwantyzacji ograniczają więc zazwyczaj wymiarowość kwantowanych wektorów oryginalnego zbioru danych do wartości nie przekraczających 16, do 20.

Dekompozycja danych oryginalnych

Duża złożoność algorytmów wektorowej kwantyzacji, duże koszty obliczeniowe i sprzętowe (konieczność dużej pamięci operacyjnej do realizacji algorytmów) oraz inne ograniczenia realizacyjne powodują problemy z uzyskaniem zadawalającej skuteczności kompresji w dużym obszarze zastosowań. Podejmowano próby wykorzystania różnych schematów wstępnej dekompozycji danych w celu uzyskania możliwe największej redukcji nadmiarowości przed fazą kwantyzacji, przy stosunkowo niewielkich kosztach obliczeniowych i sprzętowych. Do najbardziej popularnych i skutecznych rozwiązań problemu skutecznej dekompozycji danych należy zaliczyć metody wykorzystujące:

• transformaty częstotliwościowe o nieskończonym nośniku,
• przekształcenia fraktalne,
• przekształcenia falkowe,

Bardzo efektywnym rozwiązaniem okazało się wykonanie wstępnej dekompozycji danych przy pomocy różnego typu transformat, a następnie kwantyzacja współczynników tych transformat przy pomocy prostszych rodzajów kwantyzatorów. Dobre metody dekompozycji danych, redukujące znacznie nadmiarowości, w tym przede wszystkim korelacje pomiędzy wartościami współczynników nowej przestrzeni, pozwoliły uzyskać wyższą efektywność całego schematu kompresji przy znacznie mniejszej złożoności i małych kosztach realizacyjnych. Okazuje się, że również w tym przypadku najlepsza postać transformaty w schemacie kodowania transformacyjnego, pozwalająca całkowicie zdekorelować wejściowe źródło danych jest bardzo trudna w praktycznej realizacji ze względu na olbrzymie koszty obliczeniowe. Jądro tego przekształcenia jest bowiem zależne od sygnału transformowanego. Można jednak osiągnąć zbliżone poziom dekorelacji danych przy pomocy prostszej, niezależnej od sygnału transformaty, która pozwala zrealizować bardzo szybkie algorytmy kompresji.

    Nieco inne rozwiązanie, bliższe koncepcji wektorowej kwantyzacji zastosowano w koderach fraktalnych, używanych zasadniczo do stratnej kompresji obrazów. Wykorzystując aparat przekształceń afinicznych do generacji operatorów zwężających z atraktorami w postaci fraktali przybliżających kolejne porcje obrazu, zbudowano algorytm kompresji oparty na idei samopodobieństwa obrazu. Wyznaczanie dużej księgi kodowej na podstawie licznych wektorów treningowych zastępowane jest procesem definiowania słownika na bazie wzajemnego podobieństwa małych fragmentów kompresowanego obrazu - tak jakby obraz był przybliżany na podstawie samego siebie. Po zdefiniowaniu wielu operatorów zwężających opisujących obraz można go następnie wygenerować w kilku lub co najwyżej kilkunastu iteracjach, zaczynając od dowolnej postaci pola obrazu.

    Jeszcze inna koncepcja wywodzi się z teorii aproksymacji. Wiadomo, że dla oszczędniejszego opisu sygnału za pomocą jądra liniowej transformaty potrzeba możliwie dużego podobieństwa sygnału i funkcji bazowych tego przekształcenia. Skoro kompresowane dane reprezentują w zdecydowanej większości przypadków źródła silnie niestacjonarne, należy zastosować dobre narzędzie do opisu sygnałów niestacjonarnych. Transformacja Fouriera lub jej podobne (sinusowa, kosinusowa) wykorzystują funkcje sinusoidalne i kosinusoidalne o nieskończonym nośniku przy założeniach stacjonarności (lub pseudostacjonarności) sygnału, a więc nie są dobrym narzędziem w przypadkach sygnałów niestacjonarnych. Wykorzystano więc narzędzie przekształcenia liniowego falek o funkcjach bazowych określonych na skończonym nośniku, o skończonej energii, świetnie nadające się do analizy sygnałów niestacjonarnych tworząc bardzo oszczędną ich reprezentację.

Kodowanie odwracalne

    Sposób bezstratnego kodowania powstałych po kwantyzacji zbiorów wartości o zredukowanej dynamice (alfabecie) bardzo silnie zależy od realizowanych wcześniej technik dekompozycji i samej kwantyzacji. Trudno więc tutaj mówić o rozwiązaniach optymalnych w każdym przypadku. Zagadnienie to jest analogiczne do rozważanych w pierwszej części tej pozycji problemów bezstratnej kompresji danych. Wyróżnikiem może być jednak duża wiedza a priori o strumieniach danych wchodzących na wejście kodera ze względu na ukształtowanie tego strumienia przez poprzednie etapy schematu kompresji. 

Można wyróżnić dwa podstawowe rodzaje tychże schematów. W pierwszym optymalizuje się maksymalnie funkcje dekorelacyjne w procesach dekompozycji i kwantyzacji, wyrzucając do kodowania zbiory danych prawie zupełnie zdekorelowanych czy wręcz niezależnych, o silnie zróżnicowanym alfabecie danych, zmiennej liczbie bitów, itd. W takich przypadkach rola odwracalnego kodowania jest znikoma lub wręcz żadna. Zadanie redukcji nadmiarowości jest w zadawalającym stopniu wykonywane wcześniej, np. w metodzie kwantyzacji, która jest optymalizowana pod kątem minimalnej entropii danych wyjściowych w relacji do poziomu błędu kwantyzacji, a faza kodowania może być pominięta.

    Innym rozwiązaniem jest zmniejszenie czasochłonności i stopnia złożoności algorytmów kwantyzacji poprzez zastąpienie ich rozwiązaniami znacznie prostszymi, bardziej efektywnymi w stosunku do stopnia złożoności. Dają one co prawda mniejszą redukcję nadmiarowości, ale dodatkowa dekorelacja danych może być wykonana skutecznie w koderze odwracalnym przy znacznie niższych ostatecznych kosztach czasowych. Przykładowo, znając statystyką strumienia danych kwantowanych można zaprojektować efektywny statyczny koder arytmetyczny czy Huffmana o mniej rozbudowanych strukturach i lepszych warunkach początkowych.

    Często spotykaną praktyką jest podział zbioru kodowanego na kilka podzbiorów (strumieni) o wyraźnie różnej statystyce i niezależne kodowanie każdego z nich koderem o innych parametrach modelu źródła informacji czy wręcz 
strukturze, bądź też jednym koderem o modelach przełączanych (rys. 2.11).

Rys. 2.11 Schemat kodera VQ o kilku modelach książek $M_1,M_2,\ldots,M_k$,  przełączanych zależnie od charakterystyki strumienia wejściowego.
 

    Dodatkowo w zależności od zastosowań generowany jest w koderze strumień o cechach kodu sekwencyjnego lub progresywnego, ustalający pewną hierarchię przekazywanej informacji, w niektórych rozwiązaniach również kod zagnieżdżony, kiedy to koder jest zatrzymywany w momencie osiągnięcia założonej długości kodu wyjściowego. Czasami też fazy kwantyzacji i kodowania przeplatają się emitując równolegle ze złożoną procedurą kwantyzacji kolejne partie kwantowanych wartości np. w szybkich zastosowaniach transmisyjnych.

Charakterystyka kolorów treści obrazowej związana jest w pierwszej kolejności z wyborem przestrzeni barw. Chociaż obrazy opisywane są zwykle w przestrzeni RGB (składowe: czerwony, zielony, niebieski), przede wszystkim ze względu na budowę ludzkiego oka (trzy rodzaje czopków o odmiennej charakterystyce widmowej, gdzie maksima przypadają na te trzy kolory) oraz działanie typowych urządzeń służących rejestracji i prezentacji treści obrazowej (kamery, aparaty fotograficzne, monitory, telewizory, skanery), to model percepcji obrazów naturalnych opisujący podobieństwo kolorów wygodniej jest tworzyć w innych przestrzeniach barw. 

Przestrzeń RGB nie pozwala na równomierny opis zdolności percepcji zmian barwowych -- równym odległościom w RGB nie odpowiadają równomierne zmiany obserwowanych kolorów. Ponadto składowe są od siebie silnie zależne, wpływ na ich wartość ma natężenie oświetlenia oraz inne, oprócz barwowych czynniki. Reprezentacja RGB we współrzędnych biegunowych z uwzględnieniem korekcji gamma to przestrzeń barwna  (odcień, nasycenie, jasność). Dobre wyniki w wykorzystaniu RGB lub częściej HSV można osiągnąć jedynie przy opisie obrazów grafiki komputerowej, gdy obrazy są definiowane czy projektowane w tej przestrzeni (np. przy indeksowaniu znaków handlowych) lub też jeśli akwizycja opisywanych obrazów jest dokonywana w ustalonych, stabilnych warunkach (np. w bazie danych obrazowych dotyczących malarskich dzieł sztuki). 

Przy określaniu podobieństwa kolorów użyteczna stała się konwersja RGB do innych, lepiej opisujących ludzkie zdolności percepcji przestrzeni barw. W szczególnie korzystnej reprezentacji kolorów jedna składowa opisuje poziom jasności (sygnał luminancji), a dwie pozostałe dotyczą cech koloru (chrominancja). Warto tu wspomnieć o przestrzeniach takich jak  historyczne XYZ (z 1931 roku, niezależna, pozwalające określać kolory w sposób bezwzględny), YIQ (wykorzystywany w telewizji systemu NTSC), YCrCb (częsty w systemach kompresji obrazów i wideo rodzin JPEG oraz MPEG), YUV (wykorzystywany w telewizji systemu PAL), CIE Luv i CIE Lab (z nieliniowymi modelami dającymi równomierny rozkład percepcji barw, bazując na modelu Munsella) i inne. Różnice barw liczone w tych przestrzeniach lepiej wyrażają obserwowane zróżnicowanie barw, w sposób bardziej niezależny od uwarunkowań procesu akwizycji. Możliwa jest  optymalizacja przestrzeni kolorów wiernie odzwierciedlającej  warunki oświetlenia czy też niezmienniczej względem cieni. Efektem jest identyfikacja barwy teoretycznie zupełnie niezależnie od warunków obserwacji, jednak kosztem  utraty precyzji w szacowaniu wartości barwy, co może mieć wpływ na efektywność wyszukiwania.

Warto też nadmienić, że istniej wiele definicji określających poszczególne przestrzenie barw, np. CIE RGB, Adobe RGB, NTSC RGB, itd., przy czym szczególną pozycję zajmują normy międzynarodowego komitetu CIE (International Commission on Illumination (CIE).

Przykładowo, wzajemne konwersje wybranych przestrzeni barw opisują proste zależności:

• RGB$\rightarrow$YCrCb, według CIE, zakładając $R,G,B,Y \in [0,1],\ Cr,Cb \in [-0.5,0.5]$ 

\begin{equation}
\begin{split}
Y&=0,2989\cdot R + 0,5866\cdot G + 0,1145\cdot B \\
Cr&=0,5 \cdot R - 0,4183\cdot G - 0,0816\cdot B \\
Cb&=-0,1687\cdot R - 0,3312\cdot G + 0,5\cdot B 
\end{split}
\end{equation}

• $RGB\rightarrow XYZ$, według Adobe RGB, zakładając $R,G,B,Y,X,Z \in [0,1]$

\begin{equation}
\begin{split}
Y&=0,2974 \cdot R + 0,6273\cdot G + 0,0753\cdot B \\
X&=0,5767\cdot R + 0,1856\cdot G + 0,1882\cdot B \\
Z&=0,0270\cdot R + 0,0707\cdot G + 0,9911\cdot B 
\end{split}
\end{equation}

Cały zestaw możliwych konwersji przestrzeni kolorów jest dostępny na stronie http://brucelindbloom.com/index.html?Math.html.

Podstawowym deskryptorem koloru jest histogram skwantowanych wartości składowych danej przestrzeni barw, np. HSV. W przypadku obrazów monochromatycznych, deskryptor koloru analogicznie opisuje rozkład poziomów jasności. Liczba przedziałów kwantyzacji histogramu powinna być kompromisem pomiędzy złożonością deskryptora, a jego reprezentatywnością, zależy też silnie od rodzaju obrazów. Jeśli gros informacji zawarta jest w przedziale barw jasnych, wówczas sensowne wydaje się zwiększenie liczby przedziałów kwantyzacji je reprezentujących, kosztem mniej istotnych barw ciemnych.

Niestety, skwantowany histogram nie ma cechy niezmienniczości względem niewielkich przesunięć średniego poziomu jasności obrazu. Takie przesunięcie może zmienić przypisanie wartości pikseli leżących na granicy przedziałów kwantyzacji, wpływając niekiedy znacząco na rozkład histogramu. Wadę tę można ograniczyć poprzez zastosowanie tzw.  histogramu rozmytego. Koncepcja histogramu rozmytego usuwa nieciągłość przypisania wartości pikseli do przedziałów histogramu. Pozwala uprościć histogram za pomocą zachodzących na siebie przedziałów kwantyzacji, rozumianych tutaj jako nośniki zbiorów rozmytych z określoną funkcją przynależności (twórcą teorii zbiorów rozmytych jest Lotfi A. Zadeh).

Rozważmy histogram oraz jego skwantowaną, uproszczoną postać, pozwalającą konstruować deskryptory koloru. Przyjmijmy, że każda z wartości pikseli $f(k)$ (dla uproszczenia ustawionych w ciąg jednowymiarowy) obrazu źródłowego  $\mathbf{f}$ należy do uporządkowanego rosnąco zbioru (alfabetu) wartości możliwych: $f(k) \in A_{\mathbf{f}}=\{a_0,\ldots,a_{M-1}\}$. Histogram, czyli rozkład koloru to zbiór $\{h(m)\}_{m=0}^{M-1}$, gdzie $h(m)=h(a_m)$ oznacza liczbę wystąpień (w punktach $k$ dziedziny obrazu) kolejnych poziomów jasności

Pojęcie histogramu rozmytego nawiązuje do koncepcji kolorów reprezentatywnych, typowych dla obiektów czy tła występujących w danej klasie obrazów. Można go traktować jako alternatywny sposób opisu klasycznego schematu kwantyzacji, definiowanego za pomocą zbioru przedziałów kwantyzacji oraz wartości reprezentujących te przedziały. 
Kwantyzacja histogramu obrazów cyfrowych jest de facto kwantyzacją wtórną, będącą skutkiem redukcji dużego zbioru dyskretnych wartości źródłowych koloru $\mathbf{f}$ do mniejszego zbioru możliwie najlepiej dobranych wartości reprezentatywnych $\tilde{f}$. Kwantyzacja rozkładu kolorów jest skutkiem działania operatora $Q_f: \mathbb{Z}\rightarrow \mathbb{Z}$ przekształcającego $Q_f\Big(f=a(m)\Big)=\Big(\tilde{f}=b(n)\Big)$ z alfabetem kolorów reprezentatywnych $\tilde{f}(k) \in A_{\mathbf{\tilde{f}}}=\{b_0,\ldots,b_n,\ldots,b_{N-1}\}$, $N$ oraz rozkładem kolorów reprezentatywnych 

Tak uproszczony histogram spróbujmy przedstawić w konwencji histogramu rozmytego. Po normalizacji skwantowanego histogramu $p(n) = \tilde{h}(n)/H_{\mathbf{f}}$, gdzie $H_{\mathbf{f}}=\sum_{m=0}^{M-1} h(m)==\sum_{n=0}^{N-1} \tilde{h}(n)$, histogram możemy zinterpretować w kategoriach prawdopodobieństwa, rozumiejąc $p(n)=p(b_n)=Pr(b_n)=Pr(\tilde{f}=b_n)$ jako

gdzie $p(k)=1/N$ jest prawdopodobieństwem, że dowolny piksel wybrany z $\mathbf{f}$ jest pikselem $k$-tym. $p(n|k)$ to  prawdopodobieństwo warunkowe, że wartość piksela z indeksem $k$ przypisana jest przedziałowi skwantowanego koloru $b_n$; w klasycznym histogramie definiowane jest ono binarnie: $p(n|k)=1$ jeśli $k$-ty piksel należy do przedziału koloru $b_n$, zaś w innych przypadkach $p(n|k)=0$. 

W przypadku histogramu rozmytego, nawiązującego do teorii zbiorów rozmytych, warunkowe prawdopodobieństwo przynależności piksela (ze względu na jego wartość) do przedziału danego koloru zastępowane jest funkcją przynależności: $\mu: \mathbb{Z}\rightarrow [0,1]$ określającą relację wartości każdego piksela do wszystkich przedziałów skwantowanych kolorów $b_n$ w sposób mniej jednoznaczny, z możliwą niezerową przynależnością $f_k$ do więcej niż jednego przedziału. Ustalenie wartości $\mu(n,k)=\mu(b_n,f_k)=\mu(b_n,f_k=a_m)=\mu(b_n,a_m)$ może się odbywać na podstawie znormalizowanej odległości realnego koloru piksela $f_k=a_m$ od $b_n$, reprezentującego określony przedział wartości koloru źródłowego $\{a_m|a_m \in [b_{n-1},b_{n+1}]\}$, przy czym najlepiej, jak odległość ta uwzględnia zróżnicowanie ich percepcji, najlepiej w przestrzeni CIE Lab z percepcyjnie równomiernymi przedziałami wartości kolorów. Pozwala to na realizację prostszego obliczeniowo równomiernego rozkładu wartości kolorów reprezentatywnych, tak że $b_n-b_{n-1}=constant$. Głównym zamysłem jest bowiem przypisanie każdemu z pikseli percepcyjnego znaczenia (istotności) jego koloru poprzez odniesienie do wartości reprezentatywnych. Spodziewanym efektem jest rozkład kolorów, który odzwierciedla zróżnicowanie cech percepcji kolorów obrazu, niezależnie od innych czynników (zmian oświetlenia, szum, itd.). 

Przez analogię do zapisu histogramu klasycznego, otrzymujemy

$r(n)$ jest zbiorem rozmytym na przestrzeni wartości pikseli obrazu $\mathbf{f}$, z funkcją przynależności $\mu(n,k)$ do przedziałów kolorów reprezentatywnych $b_n$, o następujących cechach:

• nośnikiem zbioru rozmytego $r(n)$, czyli   $\{f(k)|\mu(n,k)>0\}$, jest zbiór $\{f(k)|f(k) \in [b_{n-1},b_{n+1}]\}$; 
• $\mu(n,k)=1$ dla pikseli, których wartość jest dokładnie równa wartości koloru reprezentatywnego $f(k)=b_n$ (piksele te należą do rdzenia $r(n)$); 
• $mu(n,k)$ jest ciągła, monotonicznie rosnąca na przedziale $[b_{n-1},b_n]$ i malejąca na przedziale $[b_n,b_{n+1}]$, symetryczna względem $b_n$ 
• spełniona jest zależność

Na rysunku 3.1 przedstawiono typową funkcję przynależności w postaci dwóch przesuniętych o połowę okresu funkcji trójkątnych. Analogicznie można skonstruować $\mu$ dla kolejnych przedziałów kolorów reprezentatywnych za pomocą funkcji trygonometrycznych (dwóch kosinusów przesuniętych o $\pi$).

Rys. 3.1 Ilustracja trójkątnej funkcji przynależności wykorzystywanej przy wyznaczaniu rozmytego histogramu obrazu.

Tamura zaproponował zestaw 6 cech teksturowych, korespondujących z percepcją człowieka: skrośność (oarsness) , kontrast (contrast) , kierunkowość (directionality), liniowość(line-likeness), regularność (regularity) i zgrubność(roughness). Przeprowadzone przez samych autorów koncepcji testy wykazały szczególną użyteczność 3 pierwszych miar.

Rys. 3.3 Przykłady właściwości teksturowych według wybranych cech Tamury. a) duża skrośność b) mała skrośność c) duży kontrast d) mały kontrast e) ukierunkowana f) nieukierunkowana. Obrazki zaczerpnięte z literatury.

Cenną zaletą cech teksturowych Tamury jest ich znacząca korelacja z percepcją człowieka. Aspekt tej korelacji był jednym z głównych założeń autorów. Można tam znaleźć także interesujące i rzadko spotykane opisy testów z użytkownikami, oceniającymi korelację miar obliczeniowych z ich subiektywnym wrażeniem. Przykładowe obrazy, pokazujące tekstury o skrajnych wartościach wykorzystanych cech, przedstawiona są na rysunku 3.3. Cechy te definiujemy następująco:

1. Skrośność - daje informacje o wielkości ziarna w teksturze. Im wartości skrośności jest większa, tym większe mamy ziarno. Idea wyznaczania skrośności w mierze Tamury polega na użyciu operatorów o różnym rozmiarze. Dokładnie procedura jej wyznaczania wygląda następująco:

• dla każdego punktu $(n_0, n_1)$ wyznacz średnią wartość w jego sąsiedztwie. Wielkość tego sąsiedztwa to potęgi dwójki, czyli np. $1\times 1, 2\times 2, 4\times 4, \dots, 32\times 32$:

• dla każdego punktu $(n_0, n_1)$ wyznacz różnice pomiędzy nie nachodzącymi na siebie obszarami po przeciwległych stronach punktu w kierunku poziomym i pionowym:

oraz:

• w każdym punkcie $(n_0, n_1)$ wybierz rozmiar sąsiedztwa, który prowadzi do największej wartości różnicy:

•     weź średnią z $2^S$ jako miarę skrośności dla obrazu:

2. Kontrast - w szerszym sensie kontrast stanowi o jakości obrazu. Można wyróżnić 4 czynniki, które mają wpływ na kontrast obrazu w skali szarości:

• dynamika zakresu poziomów jasności,
• polaryzacja rozłożenia czerni i bieli na histogramie poziomów szarości,
• ostrość krawędzi,
• okres powtarzalności wzorców tekstury.

Kontrast obrazu jest wyznaczany jako:

gdzie $\alpha_4=\frac{\mu_4}{\sigma_4}$,$\mu_4=\frac{1}{N_{0}N{1}}\sum_{n_0=1}^{N_0}\sum_{n_1=1}^{N_1}(X(n_0,n_1)-\mu)^4$ jest czwartym momentem średniej $\mu$, $\sigma^2$ jest wariancją poziomów szarości obrazu, a $z$ zostało eksperymentalnie dobrane jako $\frac{1}{4}$.

3. Kierunkowość - kierunkowość jest cechą mówiącą o występowaniu w teksturze kierunku. Nie chodzi tu jednak o to, jaki ten kierunek jest, a jedynie o określenie czy on występuje, tak więc dwie tekstury różniące się jedynie orientacją będą posiadały identyczną kierunkowość.

Do wyznaczenia kierunkowości wyznaczane jest różnicowe przybliżenie pochodnej poziomej $\triangle_H$ i pionowej $\triangle_V$ poprzez splot obrazu $X(n_0, n_1)$ z maskami, odpowiednio (filtr Prewitta):

i wtedy dla każdego punktu $(n_0, n_1)$ wyznaczana jest zależność:

Z tych wartości jest następnie wyznaczany 16--przedziałowy histogram $H_D$, stanowiący opis kierunkowości.

Aby przedstawione powyżej cechy wykorzystać w indeksowaniu obrazów, trzeba je odpowiednio dostosować. W swojej pierwotnej formie każda z cech Tamury daje skalarny wynik dla całego obrazu. W zastosowaniu do indeksowania wskazana byłaby reprezentacja bardziej szczegółowa, w skrajnym przypadku dająca wartość cechy dla każdego piksela w obrazie. Takie podejście pozwala na stworzenie histogramu cechy i jego łatwe porównywanie z histogramami w bazie referencyjnej. W przypadku skrośności, aby otrzymać wartość cechy dla każdego piksela, wykonywane są kroki a) do c) algorytmu, dając w efekcie miarę skrośności dla każdego piksela. Kontrast jest wyznaczany w sąsiedztwie $15\times 15$ dla każdego piksela. Kierunkowość dla każdego piksela wyznaczana jest w ten sposób, że zamiast filtru Prewitta zastosowany jest filtr Sobela, natomiast kierunkowość$\theta$ wyznaczana jest dla każdego piksela, określając kierunkowość w jego sąsiedztwie. W przypadku kierunkowości warto też zwrócić uwagę na fakt, że dla tej miary autorzy pracy Tamury nie opisują dostatecznie jasno sposobu wyznaczenia globalnej miary kierunkowości -- te same problemy mieli zresztą autorzy Deselaers,Faloutsos, którzy w obu przypadkach wspominali o konieczności adaptacji algorytmu wyznaczania skośności.

Mając trzy wartości dla każdego piksela: skośność, kontrast i kierunkowość, można wyznaczyć trójwymiarowy histogram.

Rysunek 3.4 przedstawia przykładowe rysunki obrazujące, odpowiednio, obraz oryginalny (a), skrośność (b), kontrast (c) i kierunkowość (d), oraz wszystkie te trzy wielkości, przedstawione na obrazie barwnym jako składowe RGB (e).

Rys. 3.4 Obraz cech Tamury dla przykładowego obrazu: a) obraz oryginalny, b) obraz skrośności, c) obraz kontrastu, d) obraz kierunkowości, e) obraz skrośności, kontrastu i kierunkowości jako kolorowy obraz RGB

W pracy Terhorst'a ,Deselaers'a opisano deskryptor teksturowy, próbujący opisać całościową charakterystykę teksturową obrazu. Jest to wektor danych, który obejmuje:    

• wymiar fraktalny, jako miara 'chropowatości' tekstury; wymiar fraktalny jest narzędziem matematycznym, wykorzystanym w analizie tekstur;
• cechy wyznaczone na podstawie macierzy powinowactwa; elementami tej macierzy są estymowane prawdopodobieństwa $s(i,j)$ wystąpienia par punktów o jasnościach $i$ oraz $j$, dla określonej odległości pomiędzy punktami i przyjętym kierunku analizy; macierz powinowactwa opisuje więc teksturę poprzez informację o rozkładzie jasności punktów w otoczeniu dla określonej odległości i kierunku;
• entropia, jako miara nieuporządkowania danych obrazowych;
• skrośność, jako wielkość charakteryzująca wielkość ziarna tekstury.

Celem Terhorst'a było opracowanie deskryptora, który w możliwie szerokim zakresie będzie opisywał właściwości tekstury w kontekście ich korelacji z percepcją człowieka. Jest to więc założenie podobne do tego, które postawili autorzy z grupy Tamury i z racji swej potencjalnie dużej użyteczności zostało zaimplementowane i wykorzystane w opracowanym systemie indeksowania.

Tak więc, deskryptor ten stanowi 35--wymiarowy wektor, w skład którego wchodzi 1 wartość na wymiar fraktalny, 1 na entropię, 1 na skrośność i 32 wartości wyznaczone z macierzy powinowactwa. Z macierzy powinowactwa wyznaczana jest średnia jasność, kontrast, drugi moment różnicowy oraz entropia. Każda z tych wielkości wyznaczana jest dla odległości $1$ oraz $2$ oraz dla kątów $0^\circ$, $45^\circ$, $90^\circ$ i $135^\circ$, co w efekcie daje $32$ wartości.

Percepcja dźwięku

W odbiorze dźwięku podstawowe są zróżnicowane wrażenia słuchowe, co do wysokości i głośności. Percepcja dźwięku związana jest z miejscem pobudzenia błony podstawnej, amplitudą odkształcenia i jej powierzchni. Zależy także od liczby impulsów przechodzących przez włókna nerwowe -- głośność dźwięku jest proporcjonalna do liczby impulsów nerwowych powstałych w danej jednostce czasu. Gdy rośnie poziom ciśnienia (do ok. 60 dB) - rośnie liczba impulsów w jednym neuronie, zaś przy  bardzo dużym poziomie pobudzanych jest więcej neuronów. Najmniejsza zmiana poziomu ciśnienia powodująca zmianę wrażenia głośności, tzw. próg różnicy głośności, wynosi około 0,2 dB dla tonu 1000 Hz.

Odczuwanie wysokości przejawia się przy słuchaniu jednoczesnym tonów złożonych, jako zdolność do wyodrębnienia składowych dźwięku (tonów harmonicznych). Ponadto, odczuwana jest także przy słuchaniu kolejnych dźwięków, jako zdolność do rozróżniania zmian częstotliwości. Percepcja wysokości zależy od zarówno od miejsca odkształcenia błony podstawnej, jak i od czasowego rozkładu impulsów w neuronach. Wrażenie wysokości zależy przede wszystkim od częstotliwościowego widma dźwięków, czasu trwania i poziomu ciśnienia.

Głośność i wysokość są cechami wrażeniowymi jednowymiarowymi, natomiast barwa ma charakter wielowymiarowy. Barwa dźwięku zależy głównie od względnych amplitud składowych widmowych i ich zmienności w czasie. Barwa to wrażenie, które pozwala słuchaczowi rozróżnić dwa dźwięki złożone o tej samej głośności i wysokości. 

Warto wspomnieć o kilku efektach, które charakteryzują ludzkie zdolności percepcji dźwięku.  Efekt precedensu polega na tym, że jeśli krótkie dźwięki (impulsy, transjenty) docierają w małym odstępie czasu (1 - 5 ms dla impulsów tonu, do 40 ms dla impulsów mowy lub muzyki) słyszane są jako jeden dźwięk, którego lokalizacja jest zdeterminowana przez kierunek pierwszego. Dźwięk wtórny ma niewielki wpływ na lokalizacje, jeśli dociera z
kierunku bardzo odległego od kierunku dźwięku pierwotnego. Jeśli odstęp czasu miedzy impulsami jest mniejszy od 1 ms, to efekt precedensu nie występuje, a źródło lokalizowane jest pomiędzy kierunkiem dźwięku pierwotnego i wtórnego. Efekt precedensu zanika, gdy poziom dźwięku wtórnego przewyższa poziom pierwotnego o 10-15 dB.

Ważne są też zjawiska maskowania w pasmach krytycznych słuchu i krzywej progowej słyszenia dwuusznego. Ucho ludzkie nie reaguje na dźwięki o natężeniu mniejszym od pewnej wartości zwanej progiem słyszenia dwuusznego. Wartość progowa zależy od częstotliwości dźwięku -- największa czułość słyszenia występuje w zakresie od 2 kHz do 4 kHz (Rys. 4.2). Dźwięki usytuowane na krzywej progowej są ledwie słyszalne. Słuchacz nie odczuwa pogorszenia jakości percepcji sygnału dźwiękowego, jeśli z widma tego sygnału zostaną usunięte składowe, których poziom jest niższy od progu słyszenia. 

Rys. 4.2 Przebieg krzywej progowej słyszenia dwuusznego.

Efekt maskowania jest to zjawisko polegające na podniesieniu progu słyszalności dźwięku maskowanego wskutek obecności dźwięku maskującego (maskera), tzn. dźwięk maskowany może być wtedy słyszany słabo albo wcale. Zjawisko to jest ściśle związane z adaptacją układu słuchowego. Rozróżnia się maskowanie równoczesne i nierównoczesne, związane odpowiednio z właściwościami częstotliwościowymi i czasowymi dźwięków. 

Maskowanie równoczesne polega na tym, że dźwięk maskowany znajduje się w najbliższym czasowo sąsiedztwie (razem -- przy jednoczesnej percepcji) tonu maskującego. Skuteczność maskowania zależy od natężenia dźwięków: maskującego i maskowanego oraz wzajemnej relacji ich widm częstotliwościowych. Zasadniczo najsilniej maskowane są dźwięki o zbliżonych częstotliwościach, a tony o mniejszych częstotliwościach maskują dźwięki o częstotliwościach wyższych -- na rys. 4.3 widoczny jest efekt maskowania pojedynczym tonem 1 kHz. 

W przypadku maskowania niejednoczesnego (rys. 4.3) spada słyszalność dźwięku maskowanego, gdy masker występuje bezpośrednio przed lub bezpośrednio po sygnale maskowanym. Czas maskowania po zaniku tonu maskującego może sięgać do około 200 ms i zależy od natężenia tonu maskującego oraz czasu jego trwania. 

Rys. 4.3 Efekty maskowania: zmiana krzywej progowej wskutek maskowania równoczesnego tonem 1 kHz (góra) oraz efekt maskowania nierównoczesnego (dół).

Wśród metod oceny jakości obrazów przede wszystkim ze względu na ich użyteczność, wymienić należy przede wszystkim specjalistyczne testy użyteczności obrazów -- złożone, dotyczące konkretnej aplikacji testy obserwacyjne bazujące na możliwie wiernej symulacji rzeczywistych warunków pracy z obrazami (detekcji określonych elementów, interpretacji treści), opiniach obserwatorów-specjalistów wyrażanych w formach liczbowych, możliwie wiernie symulujących realia oceny treści obrazów oraz wnikliwej analizie statystycznej odpowiednio opracowanych wyników testów klasyfikacyjnych. 

Przykładem takiej oceny mogą być testy detekcji patologii w medycznych badaniach diagnostycznych z udziałem specjalistów-radiologów. Obrazy medyczne określonej modalności (ultrasonografii, tomografii komputerowej, rentgenowskie itp.) interpretowane są ze względu na obecność określonego rodzaju podejrzanych zmian patologicznych, a efekty podjętych decyzji diagnostycznych poddawane są analizie statystycznej z wykorzystaniem krzywej ROC (Receiver Operating Characteristics). 

Percepcja informacji obrazowej - model HVS

Znane właściwości ludzkiego systemu widzenia (Human Visual System), tj. niedoskonałość ludzkiego wzroku, określone zasady percepcji treści obrazowej, odczuwalne kryteria jakości, subiektywizm i zmienność ocen (po czasie i po różnych realizacjach), a także określony sposób pracy z obrazem wymagają dostosowania metod wizualizacji (inaczej prezentacji) zarejestrowanej informacji obrazowej do charakterystyki odbiorcy.

Czułość kontrastu decyduje o możliwości rozróżniania obiektów poprzez postrzeganie różnic w poziomie jasności obiektu $f_o$ względem jednorodnego tła $f_t$. Próg widoczności $\Delta f=f_o - f_t$ nie jest stały w całym zakresie wartości $f_t$ - czułość spada przy ciemnym i jasnym tle, tak jak to pokazano na rys. 4.4. Okazuje się, że jeszcze trudniej jest dostrzec zróżnicowanie poziomów jasności w obiekcie $\Delta f=f_{o2} - f_{o1}$ przy odmiennej jasności tła - zobacz rys. 4.5.

Rys. 4.4 Określenie czułości kontrastu: a)krzywe Webera uzyskane przy jednorodnym obiekcie wyróżnianym z tła, b)przykładowe obrazki z eksperymentu. Typowa czułość kontrastu JND (Just Noticeable Difference) w środkowym zakresie wartości funkcji jasności wynosi 2\% zarówno w teście ze stałą jasnością obiektu, jak też ze stałą jasnością tła.


Rys_4.5 Określenie czułości kontrastu: a)krzywe Webera uzyskane przy niejednorodnym obiekcie wyróżnianym z tła, b)przykładowe obrazki z eksperymentu. Typowa wartość JND w środkowym zakresie wartości funkcji jasności wynosi 4\% przy jasności tła odmiennej od obiektu oraz 2\% przy równej jasności tła i części obiektu.

Mózg ludzki podczas analizy obrazu uwzględnia otoczenie w jakim występuje dany obiekt. Zależnie od cech kontekstu może pojawić się wrażenie deformacji, zmiany koloru, czy wręcz pojawiania się nowych elementów w obrazie albo znikania drobnych obiektów. Przykładem mogą być dwa odcinki jednakowej długości przedstawione na rys. 4.6a), które są odbierane jako dłuższy i krótszy (efekt rozciągania i ściskania przez groty strzałek). Innym przykładem są dwie równoległe linie (rys. 4.6b)), których wzajemna relacja fałszowana jest poprzez wyraźną preferencję kierunku rozchodzenia się symulowanej fali.

Rys. 4.6 Iluzje wynikające z określonych cech ludzkiego wzroku: a) odcinki o jednakowej długości wydają się różne, b) linie odbierane są jako nierównoległe. 

Nieobiektywność ludzkiego wzroku potwierdzają więc różnego typu iluzje (rys. 4.7) będące przede wszystkim efektem adaptacji zdolności widzenia do zróżnicowanego kontrastu w otoczeniu obiektu czy też odmiennej jasności otaczającego tła. Dodatkowo wzmacniane są niewielkie różnice cech porównywanych obiektów (kolor, kontrast, rozmiar). Symetria widzenia obszarów jasnych i ciemnych powoduje wrażenie występowania obiektów pozornych, które niekiedy w określonych warunkach mogą zakłócić proces poprawnej, tj, odpowiadającej realnym cechom obiektów, interpretacji obrazów.

Rys. 4.7  Iluzje wynikające z określonych cech ludzkiego wzroku: a)pojawiają się pozorne obiekty, b) lewa część każdego z pasków wydaje się jaśniejsza, c) prawy prostokąt (na jaśniejszym tle) jest pozornie bardziej szary.

Kolejny przykład przedstawia okręgi w centralnym punkcie obrazu będące podmiotem obserwacji, otoczone okręgami wyraźnie mniejszymi lub większymi. Przy odbiorze informacji 
obrazowej trudno jest określić czy interesujące okręgi mają jednakowe rozmiary - zobacz rys. 4.8. 

Rys. 4.8 Iluzja Ebbinghausa. Obserwator odnosi wrażenie, że na rys. po lewej stronie środkowy okrąg otoczony mniejszymi okręgami jest większy od okręgu otoczonego okręgami dużymi, natomiast na rys. po prawej oba centralne okręgi wydają się jednakowe. W rzeczywistości na lewym rysunku interesujące obiekty są jednakowych rozmiarów, a na prawym większy jest okrąg otoczony dużymi okręgami.