Podręcznik

Kwantyzator skalarny przetwarza każdą próbkę sygnału dźwiękowego (lub każdy piksel obrazu) osobno, z tego względu nie może wykorzystać związków łączących sąsiednie próbki lub piksele. Cechę tę posiada kwantyzator wektorowy (VQ – vector quantizer), przetwarzający N-wymiarowe wektory złożone z sąsiednich próbek (lub blisko siebie leżących pikseli). Na rys. 22 pokazano sposób tworzenia 2-wymiarowych wektorów z próbek sygnału audio. 

Rysunek 22 Tworzenie wektorów N=2-wymiarowych z próbek sygnału audio

Mając zbiór wektorów pobranych np. z frazy sygnału mowy  możemy je przedstawić jako mgławicę w przestrzeni N-wymiarowej - rys.23.

Rysunek 23 Mgławica wektorów 2-wymiarowych, wektory słownika i komórki Voronoy'a

Kwantyzacja wektorowa polega na zaokrągleniu wektora z mgławicy do najbliższego wektora ze słownika $\mathbf{F}={f_1,\ f_2,\ \ldots,f_L}$, pełniącego rolę zbioru poziomów kwantyzacji. Na rys.23 wektory słownika są czarnymi punktami. Zbiór wszystkich wektorów z mgławicy, dla których wektor $f_k$ jest najbliższym wektorem słownika, tworzy k-tą komórkę Voronoy’a $P(f_k)$ (od nazwiska ukraińskiego matematyka, profesora Uniwersytetu Warszawskiego). Komórki Voronoy’a są wielowymiarowymi przedziałami kwantyzacji. 
Jeśli przeznaczamy b bitów na zakodowanie jednej próbki sygnału, wówczas mamy $bN$ bitów na wektor, co oznacza, że liczba wektorów w słowniku (zwanym też książką kodową) wynosi 

Na rys.24 pokazano koder i dekoder kwantyzacji wektorowej. Dla N-wymiarowego wektora próbek x poszukujemy najbliższego wektora w słowniku F, po czym, wykorzystując $bN$ bitów, przesyłamy jego numer (j) do dekodera. Tym numerem adresujemy wektor $f_j$ w identycznym słowniku w dekoderze i wyprowadzamy N próbek skwantowanego sygnału. 

Rysunek 24 Kodowanie (a) i odtwarzanie (b) sygnału w kwantyzacji wektorowej

Jeżeli podstawimy wymiar wektora N=1, wówczas wrócimy do kwantyzatora skalarnego. Słownik stanie się zbiorem poziomów kwantyzacji, a komórki Voronoy’a – przedziałami kwantyzacji. 
Jak zaprojektować słownik kwantyzatora wektorowego? Rys.23 sugeruje, że granice komórek powinny przebiegać w równej odległości od najbliższych wektorów słownika, a wektor słownika powinien dobrze reprezentować wektory należące do jego komórki. Oznacza to, że wektor słownika winien być równy wartości średniej (centroidowi) wektorów z komórki. Te dwa warunki trudno jest spełnić od razu, ale można skonstruować algorytm iteracyjny, na przemian obliczając komórki i wektory słownika. Mając zbiór wektorów słownika, przeprowadzamy kwantyzację przydzielając każdy wektor z mgławicy do jednej z komórek Voronoy’a. Następnie obliczamy wartość średnią wektorów w każdej komórce otrzymując wektor nowego słownika. Taki algorytm nazywa się algorytmem Lloyda lub algorytmem K średnich. W istocie mamy tu problem klasteryzacji zbioru wektorów tworzących mgławicę. Sieć działań pokazano na rys.25. 

Rysunek 25 Algorytm Lloyda obliczania słownika kwantyzatora wektorowego

Działania algorytmu kończą się z chwilą osiągnięcia punktu stałego: w dwóch kolejnych iteracjach pojawia się ten sam słownik. 
Słownik początkowy może być otrzymany metodą losowania L wektorów z mgławicy. Algorytm Lloyda nie gwarantuje otrzymania najlepszego z możliwych słowników, ale w każdej iteracji następuje zmniejszenie energii błędu kwantyzacji wektorów z mgławicy. 
Wariantem algorytmu Lloyda jest algorytm  LBG (od nazwisk jego twórców: Linde, Buzo, Gray). Polega on na uruchamianiu algorytmu Lloyda kolejno dla 1, 2, 4, 8, … wektorów.  W pierwszym uruchomieniu otrzymujemy wartość średnią wszystkich wektorów z mgławicy (bazy danych uczących). Otrzymany wektor rozszczepiamy na dwa blisko siebie leżące i uruchamiamy algorytm Lloyda dla dwóch wektorów. Po osiągnięciu zbieżności, rozszczepiamy każdy wektor i uruchamiamy algorytm dla 4 wektorów, itd. aż do otrzymania słownika liczącego L wektorów. 
W Module 4 opisany jest symulator kwantyzacji wektorowej. Zainteresowanych zachęcam uruchomienia procedury Lloyda i LBG – można obserwować ewolucję wektorów słownika i komórki Voronoy’a. Interesujące jest porównanie kwantyzatora wektorowego i skalarnego (ten ostatni otrzymujemy podstawiając wymiar wektora N=1).  Porównanie należy przeprowadzić przy tej samej przepływności, tzn. tej samej liczbie b bitów na próbkę. Przy stałej wartości b bit/próbkę możemy zmieniać wymiar wektorów (N) jednocześnie zmieniając ich liczbę L wg wzoru (33). Przykładowe wyniki pokazano na rys.26. Jakość skwantowanego sygnału rośnie skutkiem zwiększania wymiaru wektora. Ten wzrost jest jednak ograniczony, gdyż nie można zmniejszyć szumu kwantyzacji poniżej wartości  opisanej funkcją RDF (rys.1). Przy zwiększaniu wymiaru wektora N szum kwantyzacji kwantyzatora wektorowego dąży do wartości RDF (pokazano to na rys.1). Oznacza to, że kwantyzator wektorowy jest asymptotycznie optymalnym koderem sygnału.

Rysunek 26 SNR w procesie kwantyzacji skalarnej i wektorowej sygnału mowy

Przewaga kwantyzatora wektorowego nad kwantyzatorem skalarnym wynika z:

• wykorzystania korelacji między kolejnymi N próbkami
• wykorzystania właściwości wielowymiarowej gęstości prawdopodobieństwa próbek

Przy braku korelacji mgławica przybiera kształt okrągły, jednak i w tym przypadku można uzyskać niewielką poprawę SNR w porównaniu z kwantyzacją skalarną. 
Poważnym problemem w implementacji kwantyzacji wektorowej jest złożoność obliczeniowa. Wynika to z eksponencjalnego wzrostu liczby wektorów słownika przy wzroście wymiaru wektorów (wzór 33). Każdy kwantowany wektor należy porównać ze wszystkimi wektorami słownika, co pochłania LN operacji arytmetycznych. W procesie kwantowania sygnału audio mamy $\frac{f_s}{N}$wektorów na sekundę  ( f_s– częstotliwość próbkowania). W ciągu sekundy należy zatem wykonać  $\frac{f_s}{N}LN=f_sL=f_s2^{bN}$ operacji. Już dla wektorów o wymiarze rzędu kilkunastu jest to liczba wykluczająca implementację w czasie rzeczywistym – rys.27.
 

Rysunek 27 Liczba operacji arytmetycznych na sekundę w kwantyzacji wektorowej sygnału audio (częstotliwość próbkowania 8 kHz)

Aby obniżyć złożoność obliczeniową, stosuje się m.in. kwantyzator wektorowy typu kształt – wzmocnienie (SGVQ - shape - gain vector quantizer). Tu wektor próbek x jest reprezentowany jako iloczyn wektora kształtu i skalarnego wzmocnienia:

W ten sposób ten sam słownik kształtów $\mathbf{F}=\{f_j\}$. zawierający L_s wektorów, może być wykorzystany w procesie kwantyzacji sygnałów o różnej mocy. Schemat kodera i dekodera SGVQ pokazano na rys.28. Oprócz słownika kształtów wykorzystuje się słownik wzmocnień  $\mathbf{G}=\{g_m\}$, czyli zbiór L_g poziomów kwantyzacji dla wzmocnienia.

Rysunek 28 Kodowanie (a) i odtwarzanie (b) sygnału w kwantyzatorze wektorowym kształt-wzmocnienie

Wektor x* można utworzyć na L_s L_g sposobów,  ale nie testujemy wszystkich kombinacji $g_mf_j$  .Najczęściej wpierw wybiera się kształt (L_s porównań wektora x z wektorami kształtu ze słownika F), a potem, dla wybranego kształtu, szuka się wzmocnienia (L_g prób). Pokazano to na rys.29. Kształt wybieramy na minimum kąta, jaki tworzy on z kwantowanym wektorem x. Równoważnym podejściem jest szukanie maksimum kosinusa kąta:

Następnie dla wybranego kształtu $f_j$ szukamy optymalnego wzmocnienia gopt tak, aby wektor gopt $f_j$ był rzutem ortogonalnym x na $f_j$:  $x-g_{opt}f_j\bot f_j$. Ortogonalność oznacza zerowanie się iloczynu skalarnego wektorów: $x^Tf_j-g_{opt}f_j^Tf_j=0$. Ostatecznie otrzymujemy

W końcu kwantujemy $g_{opt}$, wybierając ze słownika wzmocnień G wartość gm, najbliższą $g_{opt}$.

Rysunek 29 Wybór kształtu i wzmocnienia w SGVQ

W Module 4 opisano symulator kwantyzatora wektorowego, w tym kwantyzatora kształt- wzmocnienie. Zainteresowany czytelnik może przekonać się, że przy tej samej przepływności SGVQ nie zapewnia tak dobrej jakości sygnału jak klasyczny kwantyzator wektorowy. Zaletą SGVQ jest znacznie mniejsza liczba operacji arytmetycznych, umożliwiająca implementację kodera w czasie rzeczywistym.