Podręcznik

5. Metody kompresji sygnałów

5.2. Kwantyzacja wektorowa

Wektor może być wykorzystany do opisu prawie każdego typu wzorca, jak np. segment sygnału mowy czy obrazu, przez proste uformowanie "wektora próbek" z przebiegu sygnału. Kwantyzacja wektorowa (VQ – Vector Quantization) może być widziana jako forma rozpoznawania struktur (wzorów) wejściowych i aproksymowania ich za pomocą jednego z uprzednio określonych wzorców. Zbiór tych wzorców jest określany mianem słownika. Kwantyzacja wektorowa może być również postrzegana jako narzędzie do realizacji wielu skomplikowanych zadań z zakresu przetwarzania sygnałów, włączając klasyfikację i transformacje liniowe. W tego rodzaju zastosowaniach VQ może być traktowane jako technika redukcji złożoności, ponieważ redukcja w zakresie bitów może uprościć następne obliczenia numeryczne, pozwalając czasami na zastąpienie skomplikowanych algorytmów cyfrowego przetwarzania sygnałów prostym przeszukiwaniem tablic. Zatem kwantyzacja wektorowa jest czymś daleko więcej niż formalnym uogólnieniem kwantyzacji skalarnej. W ciągu ostatnich kilku lat stała się ona ważną techniką z dziedziny kompresji oraz klasyfikacji sygnałów, zaś jej przydatność i zastosowania ciągle rosną. Z coraz to większym powodzeniem wykorzystywana jest do „odszumiania” sygnałów.

Kwantyzator wektorowy, odwzorowuje wektory należące do k-wymiarowej przestrzeni euklidesowej Âk w skończony zbiór C zawierający N elementów wyjściowych (odwzorowań) zwanych wektorami kodowymi. Tak więc:

 

  \mathrm{Q:\ }\mathfrak{R}^k \xrightarrow{na} C (5.8)

 

gdzie: C = {c<sub>1</sub>,c<sub>2</sub>,c<sub>3</sub>,...,c<sub>N</sub>}, ciÎRi,  i2, 3...,N].

Zbiór C nazywany jest słownikiem o rozmiarze N zawierającym N różnych elementów będących wektorami z przestrzeni Âk. Rozdzielczość kwantyzatora wektorowego r = (log 2N)/k jest miarą liczby bitów przypadających na wektor kodowy użyty do reprezentowania wektora wejściowego, a także wskaźnikiem możliwej do osiągnięcia dokładności. Przy ustalonej wartości wymiaru kwantyzatora jego rozdzielczość jest jednoznacznie określona rozmiarem słownika N, a nie liczbą bitów użytych do specyfikacji numerycznej wektorów kodowych przechowywanych w słowniku. W typowych rozwiązaniach, słownik stanowi tablicę danych przechowywaną w pamięci komputera, zaś liczba bitów precyzji użytych do zapisu poszczególnych składowych każdego wektora nie ma wpływu na rozdzielczość kwantyzatora, a dotyczy jedynie rozmiaru zajętej pamięci oraz problemu adekwatnej precyzji zapisu słownika.

Z każdym k-wymiarowym kwantyzatorem wektorowym ze słownikiem N-wymiarowym jest związany podział przestrzeni Âk na N, k-wymiarowych obszarów (przedziałów kwantyzacji) Ri, (i=1,2,3,...,N). Każdy przedział jest opisany równaniem:

 

  Ri={<b>x</b></span></span></span><b><span style="font-size:14.0pt"><span style="line-height:115%"><span style="font-family:Symbol">Î</span></span></span></b><sub> </sub><span style="font-size:14.0pt"><span style="line-height:115%"><span style="font-family:Symbol">Â</span></span></span><sup><span style="font-size:14.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif">k</span></span></span></sup><span style="font-size:14.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif">: Q(<b>x</b>)=<b>c</b><sub>i</sub>} (5.9)

 

Z definicji przedziałów kwantyzacji wynika, że:

 

  ÈRi=Âk oraz   Ri Ç  Rj = 0 dla i¹j (5.10)

 

Rozróżnia się przedziały otwarte (brzegowe, znajdujące się na krańcach przestrzeni) i zamknięte (ziarniste), stanowiące zamknięty obszar k-wymiarowy.

Ważną własnością zbioru przedziałów przestrzeni Âk jest wypukłość. Zbiór S należący do tej przestrzeni jest wypukły, jeżeli dla każdych dwu elementów tego zbioru np. A i B zachodzi zależność: aA+(1-a)BÎS dla 0<a<1.

Kolejna własność kwantyzatorów to regularność. Kwantyzator wektorowy nazywamy regularnym jeżeli każdy przedział  Ri stanowi zbiór wypukły oraz ci Î Ri dla każdego i.

Koder kwantyzatora realizuje zadanie wyselekcjonowania spośród skończonego zbioru (słownika) jednego wektora ci , który ma reprezentować bieżący wektor wejściowy x. Indeks i zapisany w postaci binarnej, podobnie jak w przypadku kodera skalarnego, stanowi jedyną informację niezbędną dla dekodera w celu odszukania w słowniku wektora odtworzonego. Dla ułatwienia rozważań analitycznych najwygodniejszy, zdaniem autorów, jest sposób polegający na dekompozycji strukturalnej kwantyzatora wektorowego na dwa bloki składowe: koder i dekoder, tak jak w przypadku skalarnym. 

Koder K odwzorowuje przestrzeń Âk w zbiór I symboli i =1,...,N, zaś dekoder D odwzorowuje zbiór I w zbiór odtworzeniowy {C<sub>i</sub>}. Proces ten można opisać za pomocą zależności:

 

  Q(x)= D[K(x)] (5.11)

 

Właściwie, często wygodnie jest rozpatrywać kwantyzator wektorowy jako układ dostarczający zarówno indeks i jak i skwantowaną wielkość wyjściową Q(x). Rysunek 5.2 ilustruje zasadę kaskadowego połączenia kodera z dekoderem, definiując w ten sposób kwantyzator wektorowy:

Rys. 5.2 Schemat kwantyzatora wektorowego

Zadaniem kodera będzie przydzielenie każdego wektora wejściowego do jednego z przedziałów k-wymiarowej przestrzeni Âk, na zasadzie określenia jego numeru porządkowego i. Zadaniem dekodera, generacja wektora kodowego ci będącego jej reprezentantem.

Bardzo ważną rodzinę kwantyzatorów wektorowych, będącą wręcz synonimem kwantyzacji, stanowią układy wykorzystujące regułę najbliższego sąsiada, znaną z opisu kwantyzacji skalarnej. Cechą znamienną jest tutaj zależność zasady podziału przestrzeni Âk na przedziały, wyłącznie od słownika oraz użytej miary błędu. Nie występuje konieczność geometrycznego opisu przedziałów w sposób jawny.