Podręcznik

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.