Podręcznik

2. Kompresja i porządkowanie danych

2.10. Kwantyzacja

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:

$Q: \mathbb{R}\rightarrow \mathbb{R},\ \text{ tak że } Q(x_i)=\tilde{x}_i$

(2.3)

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

$y_j=\dfrac{\int_{\beta_{j-1}}^{\beta_j}x p(x) dx}{\int_{\beta_{j-1}}^{\beta_j}p(x) dx}$

(2.4)

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

$\beta_j=\dfrac{y_j+y_{j+1}}{2}$

(2.5)

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.