Podręcznik

Specyfikacja normy standardu JPEG zawiera:

• opis procesu przetwarzania źródłowych danych obrazowych w dane obrazowe skompresowane;
• opis procesu przetwarzania skompresowanych danych obrazowych w zrekonstruowane dane obrazu;
• wskazania dotyczące praktycznych implementacji standardu;
• opis zakodowanej reprezentacji skompresowanych danych obrazowych.

Specyfikacja nie opisuje kompletnej zakodowanej reprezentacji obrazu, może ona zawierać pewne parametry zależne od aplikacji. W normie wyszczególniono cztery procedury (tryby) kompresji, a mianowicie: 

• podstawowa (baseline process);
• rozszerzona na bazie DCT(extended DCT- based process);
• bezstratna (lossless process);
• hierarchiczna (hierarchical process);

Początkowo źródłowe obrazy kolorowe z przestrzeni barw RGB, zwykle stosowanej przy rejestracji obrazów, są konwertowane do przestrzeni barw YCrCb w celu efektywniejszej kompresji, zgodnie z zależnością:

Wydziela się w ten sposób składową luminancji (Y), na którą przede wszystkim wrażliwe jest ludzkie oko podczas percepcji treści obrazowej. Dalej każdy komponent kodowany jest niezależnie, przy uwzględnieniu pewnych różnic związanych z mniejszej czułością percepcji składowych chrominancji. 

Kodowanie każdego składnika obrazu (luminancja, składowe chrominancji) przebiega analogicznie. W podstawowym procesie kodowania dane wejściowe są ośmiobitowe, w rozszerzonym - 12 bitowe. Obraz jest dzielony na bloki $8\times 8$ i każdy blok jest transformowany za pomocą DCT (discrete cosine transform), przy czym kodowanie obrazu przebiega sekwencyjnie, tzn. z lewej strony na prawą zaczynając od góry obrazu i przemieszczając się na dół.

W standardzie JPEG wykorzystano zbiór funkcji bazowych transformacji DCT - 2W dyskretna transformacja kosinusowa funkcji obrazu $f(x,y)$ w bloku o rozmiarach $N\times N$ zdefiniowana jest w sposób następujący: 

jako przekształcenie proste, a odwrotne:

gdzie $k(u,v)$ są wartościami współczynników w dziedzinie DCT, $C(u),C(v)=\frac{1}{\sqrt{2}}$ dla $u,v=0$ oraz $C(u),C(v)=1$ w p.p.

W JPEG przyjęto blokową postać DCT, dla $N=8$, ze względu na redukcję efektów Gibbsa (pierścieniowe zniekształcenia powodowane obcinaniem górnej części pasma) oraz dostosowanie do lokalnej charakterystyki widmowej obrazu. Istotną okazała się także możliwość przyspieszenia procesu transformacji -- przy podziale blokowym redukowana jest liczba obliczeń w stosunku do wersji pełnokadrowej, można opracować szybkie algorytmy ze stablicowanymi wartościami kosinusów, możliwe jest też zrównoleglenie obliczeń niezależnych przekształceń w blokach. Dwuwymiarowe funkcje bazowe przedstawiono na rys.1.1.   

Rys. 1.1  Baza 64 dwuwymiarowych funkcji kosinusowych zastosowana w JPEG; według ogólnie przyjętej konwencji w lewym górnym rogu bloku ustalana jest wartość średnia pikseli w bloku, która odpowiada współczynnikowi określonemu przez splot danych z funkcją stałą); kolejne wartości współczynników DCT są efektem splotu danych z kolejnymi harmonicznymi bazy funkcji kosinusowych. 

Norma określa $N=8$, a obliczone 64 współczynniki DCT z każdego bloku podlegają \textbf{kwantyzacji} skalarnej z przedziałem kwantyzacji dobranym dla każdej harmonicznej. Kolejne wartości $k(u,v)$ są dzielone przez odpowiadające im wartości w tablicy kwantyzacji $\mathbf{Z}=\Biggl[ \begin{smallmatrix} z(0,0) & \cdots & z(7,0)\\ \vdots & \vdots & \vdots \\ z(0,7) & \cdots & z(7,7) \end{smallmatrix} \Biggr]$  
i zaokrąglone do najbliższej liczby całkowitej: $\hat k(u,v)=\Big [ \frac{k(u,v)}{z{(u,v)}} \Big]$. Tablicę tę można dobrać w zależności od aplikacji, przykładowe postacie oddzielnych tablic dla luminancji i chrominancji pokazano na rys. 1.2. 

Rys. 1.2  Charakterystyka procesu kwantyzacji w JPEG: u góry -- tablice kwantyzacji dla luminancji (po lewej) i chrominancji, optymalizujące jakość rekonstruowanych obrazów pod kątem oceny psychowizualnej (rekomendowane w normie JPEG, jednak nie obligatoryjne); u dołu -- krzywa równomiernej kwantyzacji skalarnej z przedziałem zerowym. 

Uzyskano schemat kwantyzacji równomiernej (ze stałym przedziałem) z zerem, jak na rys. 1.2. Dla przykładowej wartości $z(u,v)=c$  wartość $\hat k(u,v)=p$ wtedy i tylko wtedy, jeśli $c(p - \frac{1}{2}) \leq k(u,v) < c(p + \frac{1}{2})$. Dla $|k(u,v)| < \frac{c}{2}$ mamy $p=0$, czyli następuje wyzerowanie współczynnika, tj. usunięcie odpowiedniej harmonicznej z widma sygnału odtwarzanego w procesie dekompresji według  (1.3).  

Powyższe rozwiązanie pozwala przy stosunkowo niewielkim błędzie kwantyzacji zachować współczynniki o wartościach powyżej progu $\frac{c}{2}$. Poprzez dobranie odpowiednich wartości tablicy kwantyzacji $z(u,v)$, zgodnie z wagą percepcji ustalonej dla poszczególnych współczynników-harmonicznych można zachować wysoką psychowizualną jakość obrazu w subiektywnej ocenie obserwatora. Standard JPEG dopuszcza dowolną postać tablicy kwantyzacji, jednak w normie podano rekomendowane postacie tablic kwantyzacji dla luminancji i chrominancji (rys. 1.2). Tablice te zawierają doświadczalnie dobrane wartości, które odzwierciedlają subiektywne wrażenie odbioru poszczególnych składowych harmonicznych obrazów. Są one efektem kilkuletnich badań nad psychowizualnym odbiorem obrazów naturalnych.

Silniejsza kwantyzacja współczynników w blokach powoduje charakterystyczny dla JPEG efekt blokowy, który jest konsekwencją uzyskanej nieciągłości funkcji jasności obrazu na granicach bloków - rys. 1.3.

Rys. 1.3 Efekt blokowy uzyskany dla kompresji JPEG w stopniu 43:1 (para obrazów u góry -- z lewej oryginał Lena) oraz 75:1 (dolna para obrazów Barbara).

Kolejnym etapem schematu kompresji jest kodowanie kwantowanych współczynników DCT. Wartości współczynników każdego bloku są ustawiane w jednowymiarowy ciąg danych według sekwencji zygzak, a następnie kodowane z wykorzystaniem metody Huffmana, kodu binarnego oraz RLE. Charakterystyczny rozkład wartości współczynników to  składowa stała oraz dominujące zwykle, co do wartości bezwzględnej, wartości współczynników niskich harmonicznych, malejące przy przechodzeniu do składowych o wyższej częstotliwości, z dużą liczbą zer. Ustalenie ciągu kodowanych danych według porządku zygzak pozwala na ustawienie w najbliższym sąsiedztwie danych o zbliżonych wartościach. Uzyskuje się w ten sposób jednowymiarowy ciąg wartości zakończony dużą ilością zer, podatny na efektywne kodowanie - zobacz rys. 1.4. Składową stałą bloku koduje się różnicowo, tzn. koduje się jedynie różnicę pomiędzy wartością składowej stałej obecnego bloku i poprzedniego. Do kodowania kategorii wartości współczynnika używa się kodu Huffmana, przy czym rekomendowana tablica słów kodowych nie jest obligatoryjna. Doprecyzowanie wartości współczynnika wewnątrz kategorii odbywa się za pomocą kodu dwójkowego. W przypadku składowej stałej (DC) ustalono słowa Huffmana dla 12 takich kategorii (rys. 1.5), zaś dla składowych zmiennych (AC) utworzonych zostało 10 kategorii wartości (z wykluczeniem wartości 0), przy czym każda z kategorii otrzymała różne słowa kodowe w zależności od liczby zer poprzedzających wartość niezerową - rys. 1.5. Norma w wersji rozszerzonej dopuszcza także stosowanie kodera arytmetycznego.

Rys. 1.4  Przykład przekształceń w procesie kodowania JPEG: kolejno przykładowy blok obrazu z wartościami funkcji jasności, obliczone współczynniki DCT, te same współczynniki po kwantyzacji z użyciem tablic luminancji z rys. 1.2 oraz ustalenie kolejności kodowania skwantowanych współczynników według porządku zygzak.

Rys. 1.5 Tablice kodowania rekomendowane normą JPEG, choć nieobligatoryjne: dla składowej stałej DC (po lewej u góry) oraz składowych zmiennych AC - tablica z podziałem na kategorie wartości oraz tablica słów kodowych poszczególnych kategorii poprzedzonych określoną liczbą współczynników zerowych.

Proces dekompresji przebiega dokładnie odwrotnie, przy czym dekoder musi posługiwać się dokładnie tymi samymi tablicami specyfikacji (tablica kwantyzacji, Huffmana). Umożliwia to format zapisu (JFIF), w którym tablice specyfikacji poprzedzone odpowiednimi markerami umieszczone są w pliku razem z danymi skompresowanymi. 

Ogólny schemat algorytmu przedstawiono na rys. 1.6. 

Rys. 1.6  Ogólny schemat blokowy algorytmu kompresji ze standardu JPEG, bazujący na blokowej DCT.

Tryb rozszerzony i hierarchiczny

Rozszerzony proces kompresji umożliwia kompresję zarówno 8- mio jak i 12- to bitowych danych, przy czym kodowanie może być nie tylko sekwencyjne, ale i progresywne. W modzie progresywnym poszczególne bloki współczynników przeglądane są w tej samej kolejności, jednak wartości ich współczynników kodowane są częściowo w wielu skanach, zgodnie z podziałem na poszczególne podpasma lub mapy bitowe. Rozwiązanie to wymaga jednak zapewnienia dodatkowego bufora pamięci do przechowania skwantowanych wartości współczynników całego obrazu, odpowiednio porządkowanych na etapie ich finalnego kodowania oraz formowania strumienia wyjściowego. 

W normie występują dwa rodzaje procedur progresywnego kodowania. Pierwsza, nazywana selekcją widma, dzieli współczynniki ustawione według sekwencji zygzak na kolejne pasma, które zawierają poszczególne części częstotliwościowego spektrum każdego z bloków. Druga procedura związana jest z precyzją, z jaką kodowane są współczynniki w każdym z pasm i nazywana jest sukcesywną aproksymacją. Najpierw kodowana jest pewna liczba bardziej znaczących bitów wartości tych współczynników, a następnie mniej znaczące bity. Można progresywnie kodować współczynniki jedynie przy pomocy procedury selekcji widma, jak też z wykorzystaniem obu procedur. Wówczas mamy do czynienia z tzw. pełną progresją. Ze stwierdzeń zawartych w opisie normy wynika, że zastosowanie selekcji widmowej, jakkolwiek wygodne dla wielu zastosowań, daje porównywalne bądź nieco gorsze wyniki kompresji niż sekwencyjna metoda kodowania, podczas gdy przy pełnej progresji skuteczność kompresji może się okazać nieco większa.
 
W rozszerzonym procesie kodowania możliwe jest także arytmetyczne kodowanie, a tablica warunkowych zależności danych (conditioning table) jest wówczas zapamiętywana jako tablica specyfikacji.

Hierarchiczny proces kodowania macierzy obrazu polega na tworzeniu jego reprezentacji w postaci sekwencji kadrów  o różnej rozdzielczości za pomocą rozszerzonego procesu kodowania (wykorzystującego DCT) lub metody bezstratnej (bazującej na predykcji). Można także połączyć te dwie metody i w schemacie kodowania z DCT zastosować kodowanie bezstratne współczynników jedynie zaokrąglonych do najbliższej liczby całkowitej (a więc bez opisanej wyżej metody kwantyzacji z wyspecyfikowaną tablicą), co daje efekt kompresji prawie bezstratnej (zmiany źródłowych wartości pikseli poprzez błędy przybliżeń są praktycznie niezauważalne). 

Tworzone są zrekonstruowane składniki odniesienia obrazu różnej rozdzielczości i koduje się różnice pomiędzy obrazem oryginalnym a tymi składnikami odniesienia. Stosowanie filtrów próbkujących obraz oryginalny z różną rozdzielczością tworzy charakterystyczną piramidę przestrzennej rozdzielczości.

Tryb hierarchiczny może być stosowany alternatywnie, aby zwiększyć jakość rekonstruowanych składników obrazu o danej rozdzielczości w stosunku do procedury z progresją z trybu rozszerzonego, bardziej kontrolując poszczególne poziomy rozdzielczości. W tej procedurze kodowania możliwe jest porządkowanie treści przekazu według ustalonej progresji skali, co jest szczególnie użyteczne w systemach posługujących się wielorozdzielczymi wersjami danych obrazów (zależnymi np. od parametrów urządzeń do wizualizacji, drukarek czy też wymagań do przetwarzania obrazów).

Bezstratny JPEG

Standard opisujący odwracalny algorytm kodowania obrazów wykorzystuje predykcyjne kodowanie wartości pikseli z kilkoma wariantowymi modelami o różnych kontekstach. Można wybrać najbliższe sąsiedztwo piksela rzędu 1, 2 lub 3 jak na rys. 1.7a). Dostępnych jest kilka najprostszych podstawień lub liniowych predykcji ponumerowanych od 1 do 7 jak w tabeli na rys. 1.7b). Opcja 0 oznacza rezygnację z jakiejkolwiek formy predykcji, co jest szczególnie przydatne w różnicowym kodowaniu według trybu hierarchicznego.

Rys. 1.7 Modele predykcji w bezstratnym JPEG: a) przestrzenny kontekst sąsiednich pikseli $(f_w,f_{gl},f_g)$ wykorzystywanych przy kodowaniu $f$; b) równania określające wartość przewidywaną $\hat f$ w poszczególnych trybach kodowania predykcyjnego. 

Opcje 1,2 i 3 to najprostsze predykcje rzędu 1 dobierane ze względu na dominujący kierunek ułożenia informacji w obrazie. Predykcja z numerem 7 wykorzystuje dwóch najbliższych sąsiadów w pionie i w poziomie, podczas gdy opcje 4-6 są najbardziej złożonymi modelami rzędu o bardzo uproszczonym rozkładzie wartości wag. 

Proces kodowania bezstratnego ujęty w standardzie zamiast koncepcji kodowania transformacyjnego z DCT realizowaną w kwadratowych blokach $8\times 8$ pikseli, proponuje liniową predykcję kodowanych wartości dobieraną dla danego skanu. Różnica pomiędzy wartością przewidywaną $\hat f$, a źródłową wartością piksela $f$  kodowana jest dostosowaną metodą Huffmana lub arytmetycznie. W metodzie Huffmana stosuje się 17 kategorii różnicowych wartości błędu predykcji, a w kodowaniu arytmetycznym konstruowany jest dwuwymiarowy model statystyczny.

Odwracalny koder JPEG cechuje stosunkowo mała efektywność kompresji obrazów ze względu na zbyt proste w wielu zastosowaniach modele predykcji oraz wykorzystanie metod entropijnych o ograniczonej efektywności (statyczny koder Huffmana) bądź stosowalności (ze względu na ograniczenia powszechnego dostępu do binarnego kodera arytmetycznego QM). Zaletą jest jednak to, że według specyfikacji JPEG metodą tą  można odwracalnie kodować obrazy o dynamice od 2 do 16 bitów, co oznacza potencjalnie bardzo szeroki zakres zastosowań. W przypadku medycznych danych obrazowych, gdzie często stosowane są wyłącznie bezstratne metody kompresji, szczególnie cenna jest możliwość kodowania danych obrazowych dwubajtowych (wartość funkcji jasności piksela zapisana jest na 2 bajtach). Taka sytuacja występuje np. w tomografii komputerowej, tomografii rezonansu megnetycznego czy w radiografii cyfrowej i mammografii. 

Przykładowo, bezstratną procedurę JPEG wykorzystano na Uniwersytecie Południowej Florydy do archiwizacji znaczącego zestawu obrazów mammograficznych DDSM. Baza ta zawiera wiele referencyjnych, zweryfikowanych diagnostycznie rezultatów badań, które są wykorzystywane  przez naukowców na całym świecie od wielu lat. Te ogólnodostępne zasoby są przydatne w porównawczej ocenie radiologicznej, jak też w testowaniu nowych metod przetwarzania, analizy i poprawy jakości obrazów, wykorzystywanych w komputerowym wspomaganiu diagnostyki, a także w optymalizacji metod kompresji obrazów. 
 

Ograniczenia efektywności bezstratnego JPEG doprowadziły do opracowania i przyjęcia w 1996 roku nowego standardu kompresji obrazów rodziny JPEG -- JPEG-LS (lossless and near lossless). 

Główne etapy bezstratnej/prawie bezstratnej kompresji obrazów według standardu JPEG-LS, tj. modelowanie kontekstu, predykcja, kodowanie błędu predykcji oraz alternatywny mod sekwencji podobnej (w szczególnym przypadku kompresji bezstratnej - identycznej), przedstawiono na rys. 1.8.

Rys. 1.8 Schemat blokowy kodera JPEG-LS.

Modelowanie kontekstu polega na w pierwszej kolejności na ustaleniu rozmiaru i kształtu najbliższego sąsiedztwa każdego z kodowanych pikseli. Na podstawie rozkładu wartości pikseli sąsiedztwa: a) wybierany jest tryb kodowania; b) obliczana jest przewidywana wartość piksela, c) konstruowany jest statystyczny model błędów predykcji (tj. różnicy pomiędzy wartością piksela i wartością przewidywaną). Lokalny kontekst z JPEG-LS pokazano na rys. 1.9. 

Rys. 1.9  Lokalny, przyczynowy kontekst wystąpienia kodowanego piksela $f$ w przestrzeni obrazu, wykorzystany w standardzie JPEG-LS do wyboru trybu kodowania, w nieliniowej predykcji oraz przy modelowaniu błędu predykcji na etapie binarnego kodowania; sąsiednie piksele o wskaźnikach pozycji $a,b,c$ stanowią elementy kontekstu predykcji rzędu 3, natomiast poszerzony zbiór pikseli $f_a,f_b,f_c,f_d$ został użyty w ocenie lokalnych zależności danych do selekcji trybu kodowania oraz zwiększenia efektywność modelu źródła stosowanego w kodowaniu binarnym.

Kontekst określony na podstawie czterech danych o położeniu $a$, $b$, $c$ i $d$ pozwala po pierwsze określić, czy informacja zawarta w wartości $f$ ma być kodowana w trybie regularnym czy w trybie sekwencji próbek identycznych:

• tryb sekwencji pikseli podobnych jest wybierany wówczas, gdy estymacja na podstawie kontekstu wskazuje, że wartości sąsiednich pikseli z dużym prawdopodobieństwem są prawie identyczne, z tolerancją dopuszczalną w kodowaniu prawie bezstratnym (identyczne w kodowaniu bezstratnym);
• tryb regularny jest wybierany wówczas, gdy z estymacji kontekstowej wynika, że nie istnieje duże prawdopodobieństwo wystąpienia kolejnych pikseli prawie identycznych, z tolerancją dopuszczalną w kodowaniu prawie bezstratnym (identycznych w bezstratnym); wówczas stosowana jest predykcja wartości kodowanego piksela na podstawie kontekstu jego wystąpienia.

Kodowanie sekwencji próbek podobnych

Charakter kontekstu ustalany jest za pomocą prostej estymacji gradientów lokalnych pikseli sąsiednich według zależności: $d_1=f_d-f_b$, $d_2=f_b-f_c$, \\ $d_3=f_c-f_a$. Warunek kontekstu pikseli podobnych w przypadku kompresji odwracalnej  wygląda następująco: $d_1=d_2=d_3=0$, co oczywiście oznacza identyczność pikseli sąsiedztwa: $f_a=f_b=f_c=f_d$. Dopuszczając stratność procesu kompresji, redefiniowany jest warunek kontekstu pikseli podobnych (z dokładnością $\sigma$) w sposób następujący: $\forall_{i \in \{1,2,3\}} |d_i| \leq \sigma$. Przy spełnieniu powyższych warunków wartość piksela kodowana jest w trybie sekwencji próbek podobnych. 

Oczekiwana jest wtedy seria kolejnych próbek o wartościach identycznych z $f_a$ zakończona pojawieniem się piksela o innej wartości lub końcem aktualnego wiersza. Długość serii jest kodowana z wykorzystaniem adaptacyjnej wersji kodu Golomba $EG_m$ (kod elementarny z ograniczeniem wartości rzędu $m$ do potęgi dwójki). W przypadku przerwania serii pikseli podobnych kodowana jest różnica pomiędzy $f$ i $f_b$ (modulo rozmiar skończonego alfabetu wartości pikseli). 

Nieliniowa predykcja trybu regularnego

W przypadku nie spełnienia warunku podobieństwa (identyczności) przez wartości pikseli sąsiedztwa  kodowanego piksela stosowany jest bardziej złożony tryb regularny (dominujący w przypadku obrazów naturalnych), wykorzystujący nieliniową predykcję z trójelementowego kontekstu oraz statystyczne modelowanie kontekstu i adaptacyjny kod Golomba do kodowania błędu predykcji.

W standardzie kompresji bezstratnej JPEG-LS wykorzystano prosty kontekst predykcji trzeciego rzędu składający się z elementów o położeniu $a$, $b$ i $c$ jak na rys.1.9. Model predykcji MED/MAP  jest nieliniowy, określony dla wartości $f$ następująco:

gdzie wartość przewidywana $\hat f$ ustalana jest adaptacyjnie na okoliczność znajdującej się w najbliższym sąsiedztwie krawędzi obiektu (gdy $f_c$ nie jest medianą pikseli sąsiedztwa), bądź też na okoliczność obszaru łagodnego ($f_c\) jest medianą).

Dodatkowo, błąd predykcji $\epsilon =f-\hat f$ jest korygowany za pomocą składnika zależnego od kontekstu, aby skompensować systematyczny błąd odchylenia w predykcji. Obciążenie operatora predykcji jest możliwe wskutek wykorzystania predykcji medianowej oraz przybliżeń $\hat f$ do wartości całkowitej (w skończonym zbiorze punktów).

Po predykcji według (1.4) wartość $\hat f$ jest korygowana zależnie od odchylenia błędu predykcji przy danym konteście. Założono dwustronny geometryczny, symetryczny rozkład błędów predykcji ze środkiem (wartością średnią) w przedziale . Celem jest utrzymanie środka rozkładu błędów w tym przedziale. Procedura wykorzystuje sumaryczną wartość błędów próbek zanotowanych przy tym samym kontekście kodowania.

Zmienna odchylenia błędu B[Q] pozwala na aktualizację wartości korekcji predykcji C[Q] najwyżej o jeden w każdej iteracji. WartośćC[Q] obliczana jest zgodnie z procedurą jak niżej, podobnie jak aktualna postać B[Q]:

Przykład 1.1. Oprogramowanie: korekcja błędu predykcji związana z obciążeniem operatora predykcji w JPEG-LS

/* Aktualizacja zmiennych B[Q] i C[Q]; zmienna C[Q] zawiera wartość korekcji wartości przewidywanej Px; SIGN równe jeden oznacza kontekst 'dodatni' */
B[Q] = B[Q] + E; /* suma błędów predykcji E */
N[Q] = N[Q] + 1; /* liczba wystąpień Q od inicjalizacji */ 

if (B[Q] <= -N[Q]) {<br />    B[Q] = B[Q] + N[Q]; C[Q] = C[Q] - 1;<br />    if (B[Q] <= -N[Q])  B[Q] = -N[Q] + 1;<br /> } else if (B[Q] > 0) {<br />    B[Q] = B[Q] - N[Q]; C[Q] = C[Q] + 1;<br />    if (B[Q] > 0) B[Q] = 0;<br /> }
....
if (SIGN == +1)  /* korekcja przewidywań */
   Px = Px + C[Q];
else Px = Px - C[Q];

Skorygowany błąd predykcji jest następnie kodowany z wykorzystaniem adaptacyjnego kodu Golomba, którego podstawowy parametr (tj. rząd) dobierany jest na podstawie rozkładu wartości błędu predykcji przy danym kontekście.

Modelowanie kontekstu

Chcąc objąć modelem statystycznym entropijnego kodowania szerszy niż w predykcji obszar potencjalnych zależności danych zdefiniowano najbliższe sąsiedztwo 4 pikseli $a$, $b$, $c$, $d$,  jak na rys. \ref{Rys_jpegls}. Na jego podstawie określono wykorzystany w kodowaniu binarnym, skwantowany kontekst  rzędu~4 składający się z następujących różnic:

gdzie wartości błędów predykcji $\epsilon=f-\hat f$ obliczane są według modelu predykcji (1.4). Wykorzystując kontekst (1.5) do estymacji prawdopodobieństw warunkowych konstruowany jest model $P(\epsilon |\Delta \epsilon _1,\Delta \epsilon _2,\Delta \epsilon _3)$. 

Alfabet każdego z trzech elementów kontekstu $C^{(4)}=(\Delta \epsilon _1,\Delta \epsilon _2,\Delta \epsilon _3)$ zmniejszono za pomocą operatora kwantyzacji $Q(\cdot )$ o $2T+1$ regionach indeksowanych: $\{-T,-T+1,\ldots,-1,0,1,\ldots,T\}$, co daje $(2T+1)^3$ różnych kontekstów. Przykładowo, dla $T=4$ mamy indeksy regionów: $\{-4,-3,\ldots, 3, 4\}$, co daje $9^3=729$ stanów modelu kontekstu. Kwantyzacja $Q(\cdot )$ nie musi być równomierna (o stałej szerokości przedziału kwantyzacji). W JPEG-LS dopuszczono kwantyzację nierównomierną, np. według następujących przedziałów domyślnych (zakładając $T=4$): $\{0\},\pm \{1,2\},\pm \{3,4,5,6\},\pm \{7,8,\ldots,20\},\pm \{\Delta \epsilon >20\}$. Procedurę kwantyzacji alfabetu kontekstu przedstawia poniższy fragment kodu:

Przykład 1.2. Oprogramowanie: kwantyzacja alfabetu kontekstu przy kodowaniu błędów predykcji w JPEG-LS

/* Różnica błędów predykcji E w punkcie i jest kwantowana do wartości QEi; T1,T2,T3 to dobierane granice przedziałów*/
if (Ei <= -T3) QEi = -4;
else if (Ei <= -T2) QEi = -3;
else if (Ei <= -T1) QEi = -2;
else if (Ei < 0) QEi = -1;
else if (Ei == 0) QEi = 0;
else if (Ei < T1) QEi = 1;
else if (Ei < T2) QEi = 2;
else if (Ei < T3) QEi = 3;
else Ei = 4;

Domyślnie T1=3, T2=7, T3=27. Okazuje się, że dla mniejszych zbiorów danych, np. obrazów o rozmiarach 64$\times$64, lepiej jest użyć jeszcze silniejszej kwantyzacji kontekstów, np. do 63 stanów trójelementowego kontekstu z alfabetem składającym się z pięciu symboli zamiast dziewięciu. Daje to poprawę efektywności kompresji, ponieważ model o mniejszej liczbie stanów może być bardziej wiarygodny.

Aby dodatkowo zmniejszyć liczbę stanów modelu z pamięcią ustala się znak kontekstu kodowanej wartości. Kontekst ''ujemny'' zamieniany jest na ''dodatni'', a model konstruowany jest wyłącznie na podstawie  kontekstów ''dodatnich''. Adaptacyjnie modyfikowany model w chwili $t$ (używany do kodowania $\epsilon _{t+1}$) określa prawdopodobieństwo wystąpienia określonej wartości $\epsilon _{t+1}$ zależnie od kontekstu $C_{\mathbf{t}}=C_t^{(3)}=\mathbf{c}=(g_1,g_2,g_3)$ (określony w każdej chwili jak na rys. 1.9). Jeśli pierwszy niezerowy element kontekstu zaczynając od $g_1=Q(\Delta \epsilon _1)$ jest ujemny, odwracane są znaki wszystkich elementów niezerowych. ''Dodatni'' kontekst $-\mathbf{c}$ warunkuje wtedy prawdopodobieństwo symbolu w kodzie binarnym. Założono w tym przypadku symetryczność rozkładu:

gdzie $\varepsilon \in A_{\mathcal{E}}$. Takie rozwiązanie zakłada kodowanie wartości $-\epsilon _{t+1}$ dla kontekstów ''ujemnych'', co należy uwzględnić podczas dekodowania. 

Uzyskano zmniejszenie liczby stanów do $((2T+1)^3+1)/2=365$.

Binarne kodowanie błędu predykcji

Na etapie rozwoju standardu JPEG-LS jako kod binarny stosowano metodę Huffmana z modelem z pamięcią, a także optymalizowany algorytm adaptacyjny kodu Golomba. Pozwoliło to uzyskać bardzo szybką metodę kompresji obrazów o dużej efektywności. Dodatkowy wzrost efektywności kosztem większej złożoności obliczeniowej można uzyskać wykorzystując kodowanie arytmetyczne (proponowane rozszerzenie JPEG-LS) \cite{LOCOA}. Używany jest tutaj analogiczny sposób kwantyzacji kontekstu i alfabetu na podstawie sąsiedztwa 5 pikseli. 

W finalnej wersji standardu wykorzystano szybki kod Rice'a $R_k$ rzędu $k$, gdzie $k$ jest dobierane zależnie od kontekstu i zmieniane adaptacyjnie. Wartość $k$ dla danego kontekstu jest uaktualniana za każdym razem, gdy kodowana jest próbka poprzedzona tym kontekstem. Metoda modyfikacji $k$ wykorzystuje skumulowaną sumę modułów błędów predykcji wartości pikseli występujących przy danym kontekście jak niżej:

Przyklad 1.3. Oprogramowanie: dynamiczne ustalanie optymalnego rzędu kodu Rice'a JPEG-LS

/* Zmienna A[0..364] zawiera sumę modułów błędów predykcji kontektu Q;  w N[0..364] liczone są przypadki wystąpień Q od inicjalizacji; A[Q]  i N[Q] są aktualizowane zgodnie z aktualnym błędem predykcji E*/
A[Q] = A[Q] + abs(E); /* aktualizacja zmiennych */
N[Q] = N[Q] + 1;
...
for(k=0; (N[Q]<<k)<A[Q]; k++); /* wyznaczenie rzędu k */

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

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

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

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

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

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

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

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

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

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

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

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

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

Metoda kodowania

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

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

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

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

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

Zmiana koncepcji kodowania wideo jest chyba największym wyróżnikiem kolejnej normy - MPEG-4. Zrealizowano w niej koncepcję kodowania obiektowego, z definicją obszaru obiektu o dowolnym kształcie, zgodnie z paradygmatem metod kompresji tzw. drugiej generacji. Obok kompresji sekwencji ramek typowych (definiowanych w prostokątnej dziedzinie pikseli) dopuszczono kompresję sekwencji regionów dowolnych kształtów (obszarów o kształtach zadanych  mapą binarną). W normie dodano także możliwość syntetycznego kodowania  obrazu i dźwięku. W porównaniu z MPEG-2 udoskonalono możliwości skalowalności strumienia kodowanego oraz dodano mechanizm odporności na błędy (error resilience).

Obok mechanizmów śledzenia obiektów o naturalnych kształtach w sekwencji czasowej, w normie zaproponowano nowatorskie narzędzie do kompresji obrazów pojedynczych - kodowanie wizualnej tekstury VTC (Visual Texture Coding), przewidziane dla scen multimedialnych zawierających obrazy statyczne. W algorytmie VTC wykorzystano falkową dekompozycję obrazu, realizując kodowanie w nieco uproszczonej wersji niż w JPEG2000.

Możliwe jest także kodowanie obrazów syntetycznych. W zależności od rodzaju syntezy obrazu sztucznego zaproponowano: kodowanie siatek dwuwymiarowych, kodowanie siatek wielokątnych trójwymiarowych, animację sztucznej twarzy i sztucznego ciała. Zdefiniowano trzy typy modelowania wizualnego: modele geometryczne opisujące kształt i wygląd prezentowanych obiektów, modele kinematyczne określające przemieszczenia i zniekształcenia obiektów oraz modele dynamiczne (w tym biomechaniczne), definiujące siły działające na obiekty i naprężenia wewnątrz tych obiektów.

Norma wzbogaca część systemową o narzędzia kompozycji i interakcji z mediami cyfrowymi. Ochrona praw autorskich znajduje odbicie w dwóch protokołach IPMP (Intelectual Property Management and Protection): IPMP-H (odpowiednik MPEG-2) oraz IPMP-X z nowymi funkcjonalnościami. Odpowiednikiem protokołu interakcji i sygnalizacji z MPEG-2 (DSM-CC) jest w przypadku MPEG-4 DMIF (Delivery Multimedia Integration Framework). DMIF jest protokołem sesji kontrolującej strumieniowanie mediów cyfrowych za pośrednictwem technik transportowych w sieci.

MPEG-4 określa mechanizmy budowy scen multimedialnych złożonych z równoczesnych prezentacji wideo, audio, obrazów statycznych, animacji, efektów grafiki komputerowej. Kluczowym narzędziem temu służącym jest binarny format strumieniowania BIFS (BInary Format for Streaming), w którym opisano  hierarchiczną strukturę sceny, z mechanizmem zmiany konfiguracji sceny i jej animacji. Tekstowy opis sceny określono w rozszerzalnym tekstowym formacie XMT (eXtensible MPEG-4 Textual format), który w postaci XMT-A jest tekstową wersją BIFS. Cennym rozwiązaniem zamieszczonym w  MPEG-4 jest mechanizm interakcji wielu użytkowników współdzielących tę samą scenę multimedialną, zgodnie z mechanizmem ''światów wielu użytkowników'' (MUW - multi-user worlds).

W normie zdefiniowano składnię formatu plikowego MP4 - dla kodowanej reprezentacji treści multimedialnych oraz metadanych wspomagających strumieniowanie, edycję, lokalne odtwarzanie i wymianę treści. Wprowadzono także pojęcie informacji o multimedialnej treści obiektów (OCI - Object Content Information).

W obszarze audio zaproponowano w MPEG-4 trzy nowe techniki kompresji dźwięku z przepływnościami bitowymi w zakresie od 2 kbit/s do 64 kbit/s. Ponadto, określono dwa narzędzia reprezentacji danych wspierających tworzenie dźwięku syntetycznego: interfejs systemu ''tekst w mowę'' (text to speech interface) oraz interfejs systemów dźwięku strukturalnego. Pierwszy z nich jest wykorzystywany do zapisu parametrów dźwiękowych (takich jak czas trwania głoski), które równolegle z tekstem są wprowadzane na wejście syntetyzera dźwięku. Określa też parametry umożliwiające synchronizację dźwięku z animowaną twarzą, dopuszcza różne języki w tekście i międzynarodowe symbole dla głosek, przy czym informacja jest wprowadzana do oryginalnego tekstu techniką specjalnych znaczników. W systemie dźwięku strukturalnego zdefiniowano język orkiestry (Structured Audio Orchestra Language), który umożliwia konfigurowanie sztucznej orkiestry złożonej z ''instrumentów'' reprezentowanych przez dynamicznie ładowane strumienie. Ponadto, język definiowania nut (Structured Audio Score Language)  reprezentuje nie tylko zapis nutowy, ale umożliwia określanie nowych dźwięków i modyfikację dźwięków istniejących.

Obok części 2 standardu, opisującej obiektowe kodowanie wideo, w okresie późniejszym opracowano zupełnie inną koncepcję kodowania wideo, wracając do schematu blokowego i transformacji DCT, jednak na zupełnie innych warunkach adaptacji przyjętych schematów do realiów treści obrazowej. Część 10 zawiera specyfikację metody, w ramach innej ścieżki standaryzacyjnej zwaną H.264, która pozwala wyraźnie zwiększyć efektywność kodowania kosztem wyraźnego wzrostu złożoności obliczeniowej algorytmów. Co warto podkreślić, tak wysoką wydajność kodeka H.264 uzyskano metodą wielu drobnych modyfikacji, powodujących uelastycznienie modelu ruchu obiektów i wynikających z tego, konsekwentnych zmian w zakresie realizacji poszczególnych przekształceń, aż do formowania strumienia zakodowanych danych. Wprowadzono m.in. takie mechanizmy jak:

• predykcja wewnątrzramkowa INTRA, realizowana w blokach $4\times 4$ (dla szczegółów) lub $16\times 16$ (dla płaskich, łagodnych obszarów); nie jest to opcja obligatoryjna; 
• wykorzystanie nadpróbkowania, sięgającego nawet 1/8 piksela do estymacji ruchu;  
• wykorzystanie w estymacji i kompensacji ruchu bloków o różnej wielkości: $16\times 16,\ 16\times 8,\  8\times 16,\   8\times 8,\   8\times 4,\  4\times 8,\  4\times 4$;
• stosowanie wielu obrazów referencyjnych do kompensacji ruchu, z możliwością ustalenia dowolnych wag, przy czym kierunek ruchu nieistotny, a klatki typu B mogą być referencyjne;
• całkowitoliczbowa wersja transformacji DCT liczona w bloku $4\times 4$, z możliwością rozszerzeń na dziedzinę $8\times 8$ lub $16\times 16$ poprzez wykorzystanie transformacji Hadamarda; 
• adaptacyjny filtr redukcji efektów blokowych.

Standard MPEG-7 nie definiuje algorytmów kompresji audio i wideo (czy raczej dekompresji, jak poprzednie normy), ale normuje metadane multimedialne, a więc opisy danych  cyfrowych lub też zawartej w nich treści. Opisy te są wykorzystywane do efektywnej charakterystyki, selekcji, doboru czy wyszukania określonych materiałów multimedialnych lub ich fragmentów. 

Dokument systemowy określa narzędzia definiowania składni metadanych w języku XML oraz techniki kompresji postaci XML-owej do postaci binarnej BiM (Binary Format for MPEG-7). Informacja zawarta w schemacie XML, określającym składnię danego typu opisów, wykorzystywana jest do redukcji strukturalnej nadmiarowości informacji (nazwa elementu, nazwa atrybutu, itp.), natomiast dedykowane techniki kodowania służą do kompresji wartości elementów i atrybutów w dokumencie XML (IEEE 754 dla liczb zmiennoprzecinkowych, UTF8 dla kodu UNICODE, kodowanie listy wartości, itp.)

Metadane

W MPEG-7 zaproponowano wiele mechanizmów definiowania metadanych, ustalono przede wszystkim bogaty język definicji opisów treści multimedialnej DDL (Description Definition Language). Język DDL jest nieznacznym rozszerzeniem  XML Schema, który w MPEG-7 wykorzystywany jest w definiowaniu normowanych typów metadanych dla poszczególnych mediów cyfrowych. Aplikacja generująca metadane, przypisane określonemu strumieniowi danych musi generować opisy według składni zdefiniowanej w typach metadanych normy, a więc zgodnych z odpowiednimi schematami XML.

Główne atrybuty informacji o treści przypisanej obiektom (OCI) to: klasyfikatory treści, słowa kluczowe, opis w języku naturalnym, język strumienia audio, informacja o kontekście wytwórczym danego medium, kategoria przyzwolenia odbioru (np. ocena dopuszczalnego wieku widza danego programu). Metadane mogą być włączane do opisu obiektu audio-wizualnego (AV), do strumienia elementarnego lub też same mogą tworzyć strumień elementarny. W strumieniu OCI mogą się znajdować opisy wielu obiektów AV.

Typy metadanych zostały podzielone na następujące kategorie:

• typy sygnałowe, odnoszące się do informacji zawartej w danych zarejestrowanego sygnału cyfrowego, np. tekstura czy kształt konturu obiektów obrazu, struktura kolorów, linia melodyczna audio; metadane tego typu są generowane automatycznie na podstawie zarejestrowanego sygnału określonego rodzaju;
• typy semantyczne, dotyczące znaczenia obiektów, relacji między nimi i zrozumiałych zdarzeń świata rzeczywistego (naturalnego) zapisanych w sygnale;
• typy strukturalne, normujące organizację metadanych w struktury danych i ich kolekcje;
• typy kontrolne, nawiązujące do informacji niezbędnych w zarządzaniu i udostępnianiu medium cyfrowego, takich jak:  kontekst techniczny (typ nośnika, typ kompresji, format i rozmiar pliku), kontekst wytwórczy (autor, producent, typ narzędzia wytwórczego, klasyfikacja produktu, np. muzyka filmowa), kontekst dystrybucyjny (dystrybutor, prawa własności, koszty).

 Szereg technik automatycznej ekstrakcji cech z obrazów, ich sekwencji oraz z materiału dźwiękowego określono w dokumentach wideo i audio tego standardu.

Deskryptory wizualne

Wśród deskryptorów wizualnych można wyróżnić kilka zasadniczych grup:

• opis struktur podstawowych
  • rozmieszczenie siatki (Grid Layout) -- kompozycja deskryptorów wizualnych obliczanych niezależnie w siatce bloków pokrywających dany obraz,
  • widok złożony w 2W-3W (2D-3D Multiple View) -- kompozycja deskryptorów wizualnych obliczanych niezależnie dla wielu obrazów 2W lub 3W tej samej sceny,
• deskryptory koloru
  • dominujące kolory (Dominant Colors) -- informacje o dominujących kolorach, ekstrahowane z obiektu wizualnego (ramka, region ramki, sekwencja ramek, obszar czasowy),   
  • skalowalny kolor (Scalable Color) -- informacja o histogramie kolorów skalowalna ze względu na liczbę poziomów kwantyzacji koloru w przestrzeni HSV (Hue, Saturation, Value),
  • rozmieszczenie koloru (Color Layout) -- informacja o współczynnikach DCT w blokach ramki dla składowych Y (luminancja) oraz Cb i Cr (chrominancja),
  • struktura koloru (Color Structure) -- informacja o strukturalnym histogramie kolorów w przestrzeni kolorów HMMD (Hue, Min, Max, Difference),
• deskryptory tekstury
  • jednolitość tekstury (Homogenous Texture) -- informacja o teksturze jednorodnej bazująca na analizie spektrum transformacji Radona z wykorzystaniem zestawu filtrów Gabora,
  • przegląd tekstury (Texture Browsing) -- zwarta informacja o teksturze na podstawie analizy kierunków dominujących w amplitudowym spektrum transformaty Gabora  obrazu oryginalnego,
  • histogram krawędzi (Edge Histogram) -- histogram dla elementarnych typów krawędzi liczonych w różnych konfiguracjach bloków,
• deskryptory kształtu
  • kształt regionu (Region Shape) -- informacja o kształcie obszaru na podstawie momentów Zernicke (transformacja ART),
  • kształt konturu (Contour Shape) -- informacja o kształcie konturu na podstawie analizy CSS (transformacja do skalowalnej przestrzeni krzywizny),
  • trójwymiarowe widmo kształtu (3D Shape Spectrum),
• deskryptory ruchu:
  • ruch kamery (Camera Motion) -- informacja o parametrach ruchomej kamery,
  • tor ruchu (Motion Trajectory) -- informacja o trajektorii ruchu obiektu interpolowanej funkcją kawałkami wielomianową, co najwyżej stopnia drugiego,
  • aktywność ruchu (Motion Activity) -- aktywność ruchu mierzona na podstawie estymacji ruchu w makroblokach $16\times 16$.

Warto zwrócić uwagę przede wszystkim na trzy zdefiniowane w MPEG-7 deskryptory tekstury obiektów wizyjnych:

• Homogeneous Texture Descriptor – HTD, który służy do opisu jednorodnych tekstur obiektów wizyjnych,
• Texture Browsing Descriptor – TBD, który opisuje percepcyjne właściwości postrzegania tekstur,
• Edge Histogram Descriptor – EHD, który nie opisuje regionów o danych teksturach, lecz rozkład i kierunkowość krawędzi pomiędzy regionami o różnych teksturach w obrazie.

Edge Histogram Description

Rys. 1.14 Pięc typów krawędzi ekstrahowanych w EHD

Histogram krawędzi opisuje rozkład przestrzenny obrazu za pomocą pięciu typów krawędzi pokazanych na rysunku (1.14): czterech kierunkowych i jednym bezkierunkowym. Ostatni typ krawędzi nie jest określony a priori w żaden sposób i jest częścią obrazu. Zostaje on z niego wydzielony za pomocą procedury pokazanej na rysunku 1.15. Obraz wejściowy jest dzielony na bloki, a następnie podbloki, w obrębie których wykonywana jest operacja detekcji krawędzi.

Rys. 1.15 Zasada składania bloków i definiowanie pod--bloków w EHD.

Krawędzie odgrywają ważną rolę w postrzeganiu obrazów, szczególnie obrazów naturalnych, dlatego też powyższy deskryptor uważany jest za najważniejszy przy porównywaniu grup obrazów za pomocą wzorca.

Homogeneous Texture Descriptor
Deskryptor homogennych tekstur służy do opisu jednorodnych tekstur obiektów wizyjnych. Metoda wykorzystywana do ekstrakcji tego deskryptora została zaproponowana w Manjunath'a i polega na wyznaczeniu parametrów statystycznych każdego z kanałów dwuwymiarowego widma obrazu statycznego. Podział widma na rozłączne podpasma odbywa się przy użyciu zastawu filtrów zamodelowanych funkcją Gabora:

gdzie $s$, $r$ to indeksy podpasm, $\omega, \theta$ to argumenty pulsacji i kąta, natomiast $\sigma, \tau$ to odchylenie standardowe pulsacji i kąta.

Deskryptor HTD dzieli widmo obrazu na $30$ kanałów o sześciu kierunkach orientacji i pięciu zakresach częstotliwości, tak jak pokazano na rysunku 1.16. Dla każdego z kanałów wyznaczana jest średnia energia składników widma oraz ich wariancja. Składnia deskryptora HTD jest następująca (MPEG75}:

gdzie $[f_{DC}$ to jednorodnie skwantowana wartość średniej luminancji obrazu, $f_{SD}$ to jednorodnie skwantowana wartość odchylenia standardowego luminancji punktów obrazu od średniej, $e_i$ to średnia wartość energii $i$--tego kanału, natomiast $d_i$ to wartość dewiacji energii $i$--tego kanału.

Rys. 1. 16 Podział widma na kanały dla obliczeń deskryptora HTD. Rysunek zaczerpnięto z literatury.

Texture Browsing Descriptor 
Percepcyjny deskryptor tekstury opisuje tekstury obiektów wizyjnych poprzez wyznaczenie parametrów odpowiadających ludzkiemu sposobowi postrzegania. Składnia opisu deskryptora TBD jest następująca:

gdzie $v_1$ to parametr regularności bądź struktury tekstury (regularity), $v_2, v_3$ to parametry opisujące kierunkowość tekstury (directionality), natomiast $v_4, v_5$ to parametry opisujące ziarnistość tekstury (coarseness).

Algorytm ekstrakcji cech TBD został przedstawiony w i także opiera się na filtracji widma z użyciem funkcji Gabora (1.7). 

Deskryptor TBD ma na celu wyznaczenie opisu, który bardziej odpowiada percepcyjnym właściwościom postrzegania człowieka. Nie gwarantuje to jednak uzyskiwania zadowalających rezultatów wyszukiwania. Liczba parametrów deskryptora jest ograniczona do pięciu (1.9). Dodatkowo wartości poszczególnych parametrów są silnie kwantowane, co zapewnia bardzo ograniczoną objętość bitową deskryptora, co niekorzystnie wpływa na precyzję wyszukiwania z użyciem TBD i ogranicza zakres jego zastosowań. Dodatkowo, deskryptor TBD charakteryzuje się bardzo dużą złożonością obliczeniowa ekstrakcji opisu, co dyskwalifikuje zastosowanie tego deskryptora w aplikacjach działających w czasie rzeczywistym.

Deskryptory rozpoznawania twarzy

Zdefiniowano także specyficzne, bardziej zaawansowane deskryptory, m.in. rozpoznawania twarzy:

• deskryptor rozpoznawania twarzy (Face Recognition) - informacja o obrazie twarzy uzyskana na podstawie skwantowanych do 5 bitów pierwszych 48 współczynników transformaty KLT,
• zaawansowany deskryptor rozpoznawania twarzy (Advanced Face Recognition) -- informacja o obrazie twarzy uzyskana w wyniku hierarchicznej liniowej analizy dyskryminacyjnej LDA, dokonanej na informacji spektralnej globalnej i lokalnej w blokach, z opcjonalną wstępną normalizacją twarzy do pozy frontalnej.

Deskryptory wizualne oprócz formatu XML mają także zdefiniowaną formę binarną, bardziej upakowaną niż binarna postać BiM -- w oprogramowaniu referencyjnym zamieszczono kodeki postaci XML na postać binarną (rys. 1.17).

Rys. 1.17 Schemat blokowy kodeków deskryptorów wizualnych MPEG-7, zaczerpnięty z literatury.
 

Deskryptory audio

Wśród deskryptorów opisujących dźwięk i mowę warto wymienić przede wszystkim:

• sygnatura audio (Audio Signature) - skalowalna informacja o lokalnych statystykach widma dźwięku,
• deskryptory brzmienia instrumentów (Musical Instrument Timbre) -- szereg deskryptorów charakteryzujących brzmienie instrumentu w terminach bazowych charakterystyk widmowych, takich jak centroid widma harmonicznego, jego rozproszenie, itp.
• deskryptor melodii (Melody) -- złożony deskryptor zawierający między innymi sygnaturę czasową i linię melodyczną w postaci ciągu zmian melodycznych.
• deskryptory rozpoznawania i indeksowania dźwięku (General Sound Recognition and Indexing) -- szereg deskryptorów pozwalających dokonać rozróżnienia dźwięków na poziomie ogólnym, np. pomiędzy muzyką, mową, a szumem, lub bardziej szczegółowym, np. między głosem mężczyzny, kobiety i dziecka (podstawowym modelem jest ukryty łańcuch Markowa).

Sztuczna inteligencja kojarzona jest z maszyną myślącą, czyli są to metody, algorytmy, urządzenia  posiadające (skutecznie naśladujące) funkcje ludzkiego umysłu. Inaczej, sztuczna inteligencja jest nauką o maszynach wykonujących zadania, które wymagają inteligencji, gdy są rozwiązywane przez człowieka.

Sztuczna inteligencja (artificial intelligence -- AI) to dział informatyki, którego przedmiotem jest badanie reguł rządzących inteligentnymi zachowaniami człowieka, tworzenie formalnych modeli tych zachowań i — w konsekwencji — realizacja narzędzi komputerowych (za pomocą algorytmów, procedur, oprogramowania, rozwiązań sprzętowych) symulujących, naśladujących lub wspomagających te zachowania. 

SI ma powiązania z psychologią, medycyną, fizjologią, bioniką, cybernetyką, teorią gier, modelowaniem matematycznym i in., czerpiąc pojęcia, metody i rezultaty oraz ubogacając poprzez oferowanie własnych pojęć i aparatu badawczego, metod obiektywizacji i formalizacji wiedzy. Przykładowe, wykorzystywane metody i narzędzia to -- w warstwie konceptualnej -- języki programowania (głównie Lisp i Prolog), języki systemów eksperckich (CLIPS, jego rozszerzenia -- np. Jess, Flops,  OPS5, Smalltalk), środowiskowe programy ułatwiające implementacje systemów (Pro Genesis, KEE,  Loops,  Level  5 Object, Aion  Execution System), systemy szkieletowe (ExSys, DecisionPro, PC-Shell, G2, XpertRule), zintegrowany pakiet oprogramowania narzędziowego (np. SPHINX), algorytmy wyszukiwania informacji, poszukiwania rozwiązań problemów złożonych, dopasowywania wzorców i in., systemy wspomagania rozpoznania, decyzji, schematy i procedury działań zaradczych, przewidywania, ostrzegania, planowania, sterowania, zaś w warstwie materialnej -- komputery o specjalnej architekturze, urządzenia komunikowania się z komputerem (interfejsy, różne technologie interakcji), inteligentne roboty itp.
 
Komputerowe realizacje SI wykorzystuje  się konkretniej do rozpoznawania kształtów (np. pisma, elementów obrazów), dźwięków (np. mowy), do gry (np. w szachy, strategicznych), dowodzenia twierdzeń, wyszukiwania informacji, analizy wyników eksperymentalnych, w celu komponowania muzyki, tłumaczenia testów, formułowania ekspertyz (ocen, opinii), sterowania, monitorowania, śledzenia obiektów, robotów i procesów technologicznych, do sugerowania prostych diagnoz lekarskich, w koncepcji inteligentnego domu, zarządzania sprzętem, aktualizacji informacji i zasobów wiedzy,  klasyfikacji zagadnień, problemów itp. 

Jednoznaczna definicja systemów SI jest trudna, a granice płynne. Ogólnie są to systemy bazujące na wiedzy i doświadczeniu, wykorzystujące bardziej jakościową wiedzę niż modele matematyczne, charakteryzujące się symbolicznym wnioskowaniem, chociaż z biegiem lat w coraz większym stopniu wykorzystujące metody numeryczne. Algorytmy odwołują się coraz częściej do sprawdzonych heurystyk, poszukując wręcz najbardziej korzystnych uproszczeń w sytuacji zastanej. Tworzone systemy  informacyjne (maszyny) mają zdolność uczenia się, pozyskiwania wiedzy, głębokiej adaptacyjności oraz autonomiczności. 

Wśród fundamentalnych obszarów SI wyróżnia się przede wszystkim reprezentację wiedzy, systemy ekspertowe, sieci neuronowe, algorytmy genetyczne, szerzej -- ewolucyjne, kognitywistykę, teorię gier, przetwarzanie języka, rozumienie mowy, widzenie komputerowe, uczenie maszyn, logikę rozmytą, programowanie automatyczne i robotykę.

Zasadniczy podział zagadnień sztucznej inteligencji ogranicza się do:

• silnej SI, dotyczącej systemów myślących, odwołującej się do osiągnięć kognitywistyki (tj. nauki zajmującej się badaniem, wyjaśnianiem i modelowaniem umysłu oraz procesów poznawczych, w tym percepcją, reprezentacją, emocjami, świadomością, pamięcią, rozumowaniem, mową, komunikacją itp.); 
• słabej SI, nazywanej inteligencją obliczeniową, soft computing, zajmującej się problemami szczegółowymi, o jasno zdefiniowanym celu oraz kryteriach wykorzystując logikę, teorie zbiorów, teorię automatów, probabilistykę i statystykę itp.; podstawowe metody to automatyczne wnioskowanie, transmutacje wiedzy, stosowanie heurystyk, algorytmy mrówkowe, maszynowe uczenie się (z nadzorem, bez nadzoru, odkrywanie asocjacji i wzorców sekwencji, boty (tj. narzędzia do przeszukiwania  i  pozyskiwania  wiedzy, z mechanizmem decyzyjnym na bazie wcześniej  zdobytej wiedzy) itd.

Aproksymacja i optymalizacja

Zadania rozwiązywane w ramach SI można przyporządkować dwóm postawowym kategoriom: zadania aproksymacji oraz zadania optymalizacji.

Aproksymacją nazywamy znajdowanie ciągłego modelu zjawiska, cechy czy sygnału za pomocą funkcji czy krzywej przechodzącej w pobliżu zadanego, ziarnistego (dyskretnego) zbioru punktów. Zwykle aproksymację rozumie się więc w kontekście funkcjonalnego opisu danej dziedziny. Jest to problem dobrania nieznanej funkcji (zespołu funkcji określonej klasy, kawałków funkcji, krzywej itp.) na podstawie  ograniczonych informacji o danym procesie, tj. skończonej liczby wartości (często zmierzonych, a więc obarczonych błędem pomiaru) danej dziedziny. Inaczej, mamy więc do czynienia z zagadnieniem przybliżania (dopasowywania) danych data fitting). 

Zadania aproksymacji (inaczej ekstrapolacji, rozpoznania) obejmują przede wszystkim

• znajdowanie ukrytych zależności pomiędzy danymi,
• przewidywanie (predykcja) zachowań obiektów, przebiegu zdarzeń, wyników własnych działań, prognozowanie trendów;
• uogólnienia wiedzy (''skoro wszyscy sportowcy -- biegacze trenują przynajmniej pięć dni w tygodniu, to brak takiego treningu może oznaczać niebycie biegaczem''); 
• uzupełnianie fragmentów zniszczonych zdjęć, zwiększanie rozdzielczości obrazów cyfrowych w celu wyświetlenia na wysokiej jakości monitorze; 
• rozpoznanie (efekt klasyfikacji) nieznanych obiektów na podstawie znanych przykładów, np. rozpoznawanie obrazów, mowy, OCR;
• sterowanie obiektami, modelowanie zachowań, naśladowanie, animacja.

Podstawowy schemat postępowania obejmuje wybór uzasadnionej klasy funkcji dobrze aproksymujących właściwości opisywanego zjawiska (jest to zasadniczy przedmiot rozważań teorii aproksymacji), a następnie procedurę (algorytm) dobierania konkretnej postaci funkcji odpowiadającej pomierzonym wartościom (to przede wszystkim obszar analizy i metod numerycznych). Użyteczna klasa funkcji aproksymujących to przede wszystkim funkcje względnie gładkie (gładkość to cecha sygnałów naturalnych), stanowiące zbiór możliwie zupełny (tj. kompletny, obejmujący opisem wszystkie możliwe przypadki) względem rozważanej grupy problemów. Korzystne jest przy tym, gdy są to funkcje łatwe w komputerowej obróbce (liczenie wartości, określanie pochodnych i całek itp.). Przykładem stosowanych klas aproksymacji opisów naturalnych zjawisk są funkcje wielomianowe, przedziałami wielomianowe, funkcje sklejane.

Formalnie, mając dane niektóre wartości nieznanej funkcji $f$ na $X$, tj. ciąg przykładów (próbek) -- zbioru treningowego $(x_1, y_1), \ldots, (x_n, y_n)$, chcemy zgadnąć wartości $f: X \rightarrow Y$ w innych punktach dziedziny, tj. w dowolnym $x_0 \in X$. Szukana $f$, dająca zgadywane $y_0=f(x_0)$, wyznaczana jest przy określonych ograniczeniach, wynikających z przyjętego  kryterium aproksymacji $f$ jest możliwie wiarygodnym uogólnieniem charakteryzującym dany problem, rodzajem modelu określonej cechy dziedziny. 

Kryterium aproksymacji może mieć różną postać, zwykle jedną z poniższych

gdzie $\epsilon$ jest maksymalnym dopuszczalnym błędem w punkcie 

gdzie $f$ rozumiana jest jako zmienna losowa, proces losowy lub pole losowe. 

W przypadku obrazów, obok dwuwymiarowych funkcji przybliżających rozkład wartości jasności danej grupy pikseli, stosowany jest też opis konturów obiektów za pomocą krzywych $S$ konstruowanych w płaszczyźnie obrazów. Do najbardziej użytecznych klas krzywych aproksymujących należy zaliczyć parametryczne krzywe wielomianowe typu Beziera, Hermite'a czy też krzywe sklejane. W kryteriach aproksymacji, występuje euklidesowa metryka $\|S - (x_i,y_i)\|$. 

Znajdowanie optymalnych rozwiązań dla bardziej złożonych zagadnień aproksymacji, a takimi niewątpliwie jest większość przybliżeń realnych obiektów i cech obrazowych, nie jest zadaniem prostym. Wydaje się, że do dziś aktualne jest ogólne stwierdzenie P.J. Daviesa z 1965 roku, że jednym z najbardziej zaskakujących faktów teorii aproksymacji jest nieskuteczność najprostszych i najbardziej naturalnych rozwiązań. Nierzadko w użytecznych realiach ocieramy się o problemy NP-trudne.

Optymalizacja jest metodą  poszukiwania wśród wielu alternatyw rozwiązania najlepszego (optymalnego), ocenianego według wiarygodnego, liczbowego kryterium jakości. Przykładowo, są to problemy minimalizacji funkcji kosztu poszukiwań, minimalizacji funkcji błędu względem rozwiązania wzorcowego, maksymalizacja wygranej (w grach logicznych) itp. W złożonych problemach często nie wystarcza jedno kryterium -- mówimy wtedy o optymalizacji wielokryterialnej, np. odwieczny problem maksymalizacji zysków przy minimalizacji kosztów czy też maksymalizacji jakości kompresowanego stratnie obrazu przy minimalizacji średniej bitowej jego reprezentacji. Dobór metody przetwarzania obrazów źródłowych, kiedy chcemy jednocześnie zredukować szum, wyostrzyć krawędzie i zachować oryginalne cechy tekstury jest też dobrym przykładem takiego zagadnienia. 

Przez $X$ oznaczmy dowolny, skończony zbiór  wszystkich możliwych rozwiązań problemu (tzw. przestrzeń stanów). Do oceny rozwiązań -- stanów wykorzystajmy rzeczywistą funkcję celu $f:\ X\rightarrow R$. Zadaniem jest znaleźć takie $x_0 \in X$ według jednego z kryteriów

• maksimum

• minimum

Klasycznym przykładem zadań optymalizacji jest sortowanie, poszukiwanie wyjścia z labiryntu, poszukiwanie najkrótszej drogi dojścia do celu (np. problem komiwojażera), posunięcia giełdowe maksymalizujące zysk, zarządzanie pamięcią operacyjną czy dostępem do zasobów itp. 

Realne problemy optymalizacji mają zwykle olbrzymią przestrzeń stanów, niepozwalającą zastosować trywialnych metod typu brute force jako praktycznego rozwiązania. W takich przypadkach poszukiwane są skuteczne heurystyki, pozwalające przeglądać przestrzeń stanów w rozsądnych wymiarach czasowych. Jeśli problem da się opisać analitycznie, co nie jest częste w realnych zjawiskach, zadanie optymalizacji sprowadza się do policzenia odpowiedniego ekstremum zadanej funkcji celu (lub funkcjonału). Wykorzystuje się wtedy zwykle układ równań uzyskany poprzez przyrównanie składowych gradientu funkcji celu do zera. Można też poszukiwać lokalnych ekstremów kierując się kierunkiem gradientu. Stosowany jest też losowy wybór rozwiązań według określonego scenariusza, np. w algorytmach ewolucyjnych. 

Łatwo zauważyć, że zadanie optymalizacji może znaleźć zastosowanie w problemie aproksymacji, np. do wyszukania ze skończonego zbioru funkcji danej klasy rozwiązania dającego minimalny błąd przybliżenia danych według kryterium. Odwrotnie, aproksymację uproszczonych rozwiązań, jako pewnego rodzaju redukcję przestrzeni stanów można wykorzystać do rozwiązania problemu optymalizacji (np. w metodzie Newtona).