Aspecte ale cuantizarii vectoriale folosite in compresia video

Aspecte ale cuantizarii vectoriale folosite in compresia video

In continuare se vor prezenta cateva notiuni de baza referitoare la cuantizarea vectoriala, cuprizand metode de evaluare a performantelor unui cuantizor vectorial si cateva structuri ale unui sistem de cuantizare vectoriala. Toate aceste notiuni se vor trata avand ca model un proces aleator vectorial si un sistem de cuantizare nonadaptiv.

Notiuni preliminare

Un cuantizor vectorial realizeaza corespondenta de la spatiul euclidian, la un set finit de vectori, :

(1)

Setul de vectori , inclus in , poarta numele de set de codare si este compus din vectori de codare,

(2)

De asemenea, se defineste multimea index ca fiind un set de numere naturale

Avand un vector k-dimensional, iesirea cuantizorului vectorial este un alt vector k-dimensional

(3)

Un cuantizor vectorial va partitiona spatiul in N regiuni (celule), , corespunzatoare fiecarui cuvant de cod . Astfel, o regiune este definita sub forma:

. (4)

Din definitiile anterioare rezulta ca:

si pentru . (5)

In concluzie, cuantizorul vectorial este complet definit prin specificarea setului de vectori de cod si a regiunilor corespunzatoare vectorilor din setul . Regiunile ce compun spatiul se pot imparti in doua mari categorii: regiuni (celule) nemarginite, ceea ce inseamna ca volumul acestora in spatiul k-dimensional este infinit si regiuni (celule) marginite, ce au volumul in spatiul k-dimensional finit. Celulele din prima categorie poarta numele de celule supraincarcate, iar celulele din cea de a doua categorie poarta numele de celule granulare. Reuniunea celulelor nemarginite formeaza o regiune nemarginita numita regiune de supraincarcare, iar celulele granulare formeaza asa-numita regiune granulara.

O proprietate importanta a regiunilor este convexitatea: doua puncte din interiorul unei celule din spatiul sunt capetele unui segment continut in respectiva celula. De asemenea, un cuantizor vectorial este regulat daca indeplineste doua conditii: fiecare celula este convexa si .

Evaluarea performantelor unui cuantizor vectorial. Distante utilizate in cuantizarea vectoriala

Eroarea de cuantizare sau distorsiunea este valoarea nenegativa asociata cu vectorul de intrare si cel de iesire . Avand o astfel de masura se pot cuantifica performantele unui sistem de cuantizare vectoriala efectuand media statistica a distorsiunilor . Performantele unui sistem de compresie sunt cu atat mai bune cu cat aceasta distorsiune este mai mica. In practica eroarea (distorsiunea) medie se calculeaza astfel:

(6)

unde este setul de vectori din intrarea sistemului, iar este distorsiunea medie corespunzatoare fiecarei celule . Daca vectorul este o realizare particulara a unui proces stationar si ergodic, atunci limita din (6) exista si ea este egala, cu probabilitate unu, cu .

Fie un vector aleator din cu functia densitate de probabilitate specificata. In acest caz, eroarea (distorsiunea) medie poate fi scrisa ca fiind:

(7)

sau

(8)

unde , iar este functia densitate de probabilitate a lui daca .

Distante in spatiul vectorial. Cea mai utilizata masura de distorsiune intre doi vectori este eroarea patratica sau patratul distantei euclidiene definita astfel:

. (9)

Relatia este valabila atunci cand vectorii si sunt coloana.

O masura generala a distorsiunii se poate exprima sub forma:

(10)

Daca , se obtine distorsiunea absoluta sau norma . Pentru , se obtine, ca in relatia (9), eroarea patratica medie, care este . Norma este definita astfel:

(11)

O alta masura de interes este eroarea patratica ponderata:

, (12)

unde este o matrice simetrica si pozitiv definita, iar si sunt vectori coloana. In unele aplicatii, matricea este selectata in functie de statistica procesului vector de la intrare. De exemplu, distanta Mahalanobis se defineste cu relatia (12) pentru o matrice egala cu matricea de covarianta a vectorului de intrare. Daca componentele vectorului nu sunt corelate, matricea se reduce la o matrice diagonala cu elementele egale cu variantele componentelor vectorului , iar:

. (13)

O alta masura de interes utilizata in special in procesarea imaginilor se defineste cu relatia:

, (14)

unde , iar este matricea unitate. In acest caz distanta intre doi vectori este:

. (15)

3. Structuri ale cuantizorului vectorial

Procesul de codare presupune examinarea fiecarui vector de intrare si identificarea partitiei, din spatiul k-dimensional in care este inclus vectorul . Codorul returneaza in general indexul partitiei, i, iar decodorul genereaza vectorul de cod corespunzator acelui index,.

Se defineste functia de selectie pentru partitia ca fiind:

. (16)

Operatia de cuantizare poate fi scrisa matematic astfel:

. (17)

Se observa ca, pentru un vector de intrare dat, doar un singur termen din suma din (17) este nenul.

Figura 1 reprezinta o structura a unui cuantizor vectorial. Fiecare multiplicator pondereaza un vector de cod cu zero sau unu, astfel incat, la iesirea sumatorului va rezulta vectorul de cod corespunzator. Alternativ, multiplicatorul poate fi vazut ca o locatie de memorie in care este stocat vectorul de cod corespunzator.

Figura 1. Structura primara a unui cuantizor

O celula Voronoi, , este determinata de vectorul de codare si este definita matematic de relatia:

, (18)

unde.

Fie semi-spatiul definit de relatia:

, (19)

si hiperplanul definit de:

, (20)

pentru .

Date fiind definitiile de mai sus, celula Voronoi este intersectia semi-spatiilor:

. (21)

Echivalent, semi-spatiul poate fi exprimat sub forma:

, (22)

unde, iar .

Fie

. (23)

Daca reprezinta functia treapta unitate, atunci:

, (24)

iar

. (25)

Functia de selectie a fost descompusa in operatii elementare . Fiecare functie decide daca vectorul de intrare este continut in semispatiul definit de perechea de vectori de cod . Operatia de codare consta in evaluarea termenilor , , ceea ce presupune evaluari.

In aplicatiile de compresie prin cuantizare vectoriala, o constrangere este rata de codare, definita ca: . Pentru performante bune este necesar ca dimensiunea sa fie cat mai mare, ceea ce presupune si un numar, , de celule mare. Astfel, cuantizorul vectorial va avea un numar mare de celule Voronoi, fiecare avand un numar de fete de dimensiune , mult mai mic decat . Acest lucru inseamna ca multe din semispatiile ce definesc celula sunt redundante si doar un subset de functii , si vor trebui evaluate pentru a se lua decizia daca vectorul este sau nu, continut in celula . De exemplu, in cazul unidimensional, celulele Voronoi sunt intervale si au doar doua fete, astfel incat sunt necesare doar doua comparatii pentru a se determina daca un numar este sau nu, in acel interval. In general, un semispatiu este redundant fata de celula daca , hiperplanul ce defineste, nu contine o fata a celulei. Acest lucru inseamna ca are o dimensiune mai mica decat .

Pentru a caracteriza pe deplin un cuantizor vectorial este necesar sa se identifice fetele tuturor celulelor din spatiul . Astfel, este convenabil a se defini punctele adiacente celulei . este un punct adiacent celulei , daca contine o fata a lui . De asemenea, se defineste numarul de adiacente ca fiind numarul de fete ale celulei si este dat de setul de indici:

, (26)

iar

. (27)

Eliminand in acest mod semispatiile redundante, complexitatea algoritmului de codare poate fi redusa.

In figura 2 se reprezinta structura unei functii de selectie . Numarul de functii ce trebuie evaluate pentru determinarea functiei de selectie este dat de numarul de fete ale celulei , respectiv.

Figura Structura unei functii de selectie S_i

Cuantizarea optimala

Un cuantizor este optim atunci cand oricare alt cuantizor, cu acelasi numar de vectori de cod, prezinta o eroare medie de cuantizare mai mare. Cuantizorul este optim, daca pentru oricare alt cuantizor, cu acelasi numar de vectori de cod, este respectata inegalitatea:

. (28)

In continuare, sunt prezentate doua conditii necesare pentru ca un cuantizor sa fie optim. Cele doua conditii poarta numele de conditia celui mai apropiat vecin (nearest neighbor condition - NNC) si conditia centroidului (centroid condition - CC).

Conditia celui mai apropiat vecin

Avand un set de vectori de codare , conditia celui mai apropiat vecin consta in codarea unui vector de intrare prin cel mai apropiat vector de cod din spatiul . Matematic, partitiile sunt definite astfel:

, (29)

sau

numai daca . (30)

Oricare alta partitionare a spatiului avand setul de vectori de codare dat va produce o distorsiune medie mai mare decat cea care respecta conditia de mai sus.

Conditia centroidului

Avand data o partitie a spatiului, vectorii de cod optimali satisfac conditia:

. (31)

In cazul practic in care avem un set de vectori ce trebuie codati, daca numarul de vectori ce apartin celulei este si daca se utilizeaza distanta euclidiana ca masura a distorsiunii, atunci vectorul de cod va fi:

. (32)

5. Rezultate experimentale

In cele ce urmeaza se urmareste obtinerea regiunilor Voronoi din procesul de clusterizare prin diversi algoritmi aplicati unui semnal de intrare bidimensional, cu distributie normala.

1. Prin folosirea algoritmului LBG (Linde Buzo Gray) pentru semnalul precizat, se obtin regiunile Voronoi din figura 3. Numarul de vectori de cod a rezultat egal cu 64, ceea ce conduce la o rata de codare de     biti/esantion.

Fig. 3 Regiunile Voronoi si vectorii de cod pentru o distributie

Gaussiana bidimensionala

In aceleasi conditii de intrare, se proiecteaza un cuantizor vectorial cu ajutorul algoritmului GLA (algoritmul Loyd generalizat) cu initializare prin despicare. Conform algoritmului Loyd, in figura 4 sunt reprezentati vectorii de cod pentru diverse valori ale lui.

Figura 4 Vectorii de cod si regiunile Voronoi pentru diverse valori ale lui r

3. In acest experimentul se pune in evidenta tendinta celulelor Voronoi de a avea o distributie uniforma. Pentru o dimensiune fixata si un numar de vectori de cod , s-a folosit algoritmul LBG cu un numar de vectori de antrenare. In prima figura din 5 se reprezinta histograma cu numarul de vectori de antrenare din fiecare celula Voronoi . In cea de a doua figura se reprezinta distorsiunea medie introdusa de fiecare partitie Voronoi in distorsiunea medie totala.

Figura 5. Histograma numarului de vectori de antrenare si a distorsiunii medii corespunzatoare fiecarei partitii Voronoi

6. Performantele cuantizarii vectoriale

In aplicatiile practice de cuantizare vectoriala, realizarea urmatoarelor cerinte este esentiala pentru reusita unui sistem de codare a surselor de informatie:

- sa altereze cat mai putin informatia sursei de mesaje sau sa altereze cat mai putin din informatia la care sistemul subiectiv de observatie este sensibil (ex: sistemul vizual uman, sistemul psiho-acustic);

- sa pastreze un raport rata / distorsiune cat mai bun, adica distorsiune mica pentru o rata fixata sau rata cat mai mica pentru o distorsiune fixata ;

- sa se poata implementa printr-un algoritm cat mai rapid de codare si decodare.

Desi in procesarea semnalelor video, eroarea patratica medie este cea mai utilizata masura a distorsiunii pentru evaluarea performantelor algoritmilor de compresie a datelor si de recunoastere a formelor, in unele aplicatii s-a dovedit ca aceasta nu reflecta cel mai bine modelul subiectiv constituit de modelul de observatie uman. In aceasta sectiune, se vor evalua performantele unui cuantizor vectorial din perspectiva functiei de repartitie, a distorsiunii minime pe care o introduce, precum si a geometriei partitiilor .

6.1. Limite ale functiilor de repartitie in cuantizarea vectoriala optimala

Fie vectori ai unui proces aleator vectorial ce are functia de repartitie .

Teorema Glivenko Fie functia empirica de repartitie a unei selectii simple de volum ce provine dintr-o populatie caracterizata de un vector aleator , avand functia de repartitie continua. In aceste conditii:

, (33)

unde

. (34)

Daca este numarul de vectori de antrenare, atunci, conform teoremei lui Glivenko, functia de repartitie empirica a setului de vectori de antrenare tinde, la limita, catre functia de repartitie a procesului .

Urmatoarea teorema face legatura intre statistica setului de antrenare si statistica setului de vectori de cod.

Teorema Smirnov. Fie si doua realizari ale unui proces aleator , caracterizat de functia de repartitie . Fie si functiile de repartitie empirice corespunzatoare celor doua grupe de vectori aleatori, iar si sunt volumele celor doua selectii. Se considera variabilele aleatoare:

(35)

si , functiile de repartitie ale variabilelor si , unde . In conditiile anterioare se poate scrie:

, (36)

. (37)

Se presupune ca . In practica se alege o rata de codare , ceea ce inseamna ca este fixat, iar problema care se pune este cat trebuie ales astfel incat sau sa fie maxima. Se poate scrie ca . In figura 6 este reprezentata functia de repartitie functie de pentru trei valori ale lui .

Figura 6 Functia de repartitie din (36) functie de

Cu cat setul de vectori de antrenare este mai mare, cu atat probabilitatea ca functia de repartitie a setului de antrenare sa fie mai apropiata de functia de repartitie a procesului va fi mai mare. De asemenea, pentru fixat, probabilitatea ca functia de repartitie a setului de vectori de cod sa fie mai apropiata de functia de repartitie a setului de antrenare este mai mare, cu cat raportul de antrenare creste.

Pe de alta parte, daca setul de antrenare are un numar fix de vectori , numarul de vectori de cod poate fi convenabil ales, astfel incat probabilitatea ca cele doua functii de repartitie sa fie cat mai apropiate si, in acelasi timp, rata de codare, dependenta de , sa fie rezonabila. De exemplu, pentru fixat, probabilitatea ca functie de este prezentata in figura 7. Pentru valori mici ale lui , probabilitatea ca cele doua functii sa fie apropiate este mica. Odata cu cresterea lui , probabilitatea de apropiere a functiilor de repartitie creste, astfel ca, pentru valori ale lui mai mari decat 512, aceasta probabilitate se apropie de unu.

Figura 7. Functia de repartitie din (36) functie de

In figura 8 se reprezinta probabilitatea ca cele doua functii de repartitie sa aiba diferenta maxima , functie de . si sunt fixati. Cu cat se impune din proiectare o distorsiune mai mare (distorsiune direct proportionala intr-o mare masura cu sau ), cu atat este mai mare probabilitatea ca cele doua functii de repartitie sa indeplineasca aceasta cerinta.

Figura 8 Functia de repartitie din (36) functie de

Fie functia densitate de probabilitate a unui vector aleator multidimensional dintr-un proces, iar factorul de concentrare, definit ca numarul de vectori de cod dintr-un volum din spatiul. Evident

si . (38)

Ideal ar fi sa se gaseasca un algoritm prin care . Pentru un algoritm ce vizeaza o distorsiune minima, asa cum este algoritmul LBG, la limita:

, (39)

iar pentru o codare ce vizeaza cel mai apropiat vecin (NNC), asa cum sunt hartile de auto-organizare Kohonen, exista relatia:

. (40)

In concluzie, avand un set de vectori de antrenare in spatiul cu o distributie neliniara, algoritmii de cuantizare vectoriala pot selecta un set de vectori de cod (un set de forme) a caror distributie empirica aproximeaza distributia campului din intrare.

7. Limite ale distorsiunii medii in cuantizarea vectoriala

Se pune problema gasirii unei limite teoretice minime a distorsiunii, , fiind date: dimensiunea vectorului, rata de codare si, implicit, numarul de vectori de cod, masura distorsiunii, precum si statistica procesului din care provin vectorii de antrenare.

In cazul in care, ca masura a distorsiunii, se foloseste distanta definita in (10), limita inferioara a distorsiunii unui cuantizor vectorial optim cu rezolutie mare (adica, numar mare de vectori de cod) este:

, (41)

unde:

este numarul de vectori de cod;

dimensiunea vectorilor din intrare si a vectorilor de cod;

este coeficientul de cuantizare.

In cazul in care ca masura a distorsiunii se utilizeaza eroarea medie patratica ():

, (42)

iar pentru un cuantizor de mare rezolutie (cuantizare fina)

, (43)

unde este functia Gamma.

In cazul in care ca masura a distorsiunii se foloseste relatia (14), ceea ce presupune utilizarea unui model de observatie subiectiv, si se face aproximarea , daca , masura distorsiunii va fi:

.

In acest caz se poate scrie:

. (44)

poarta denumirea de matrice de senzitivitate si este determinata de aplicatia particulara in care este utilizata.

In concluzie, odata cu cresterea numarului de vectori de cod, limita minima a distorsiunii medii va scadea. Pentru o rata constanta de codare si fixat, limita distorsiunii medii va fi o functie de statistica procesului. Pentru o distorsiune impusa intr-o aplicatie particulara, rata minima de codare este proportionala cu entropia sursei. Pe de alta parte, pentru o rata de codare fixa, cresterea entropiei sursei din intrare va determina cresterea limitei distorsiunii medii si, implicit, a distorsiunii rezultate din procesul de codare.

8. Geometria partitiilor unui cuantizor optim

O partitie convexa este admisibila daca se poate realiza o partitionare uniforma a spatiului , astfel incat toate partitiile sa fie congruente cu . Pentru cazul bidimensional, poligoanele admisibile sunt triunghiul, patrulaterul si hexagonul regulat.

Se defineste momentul normalizat de inertie al unei partitii ca fiind:

, (45)

unde este volumul -dimensional al partitiei . Coeficientul de cuantizare se defineste ca fiind :

. (46)

O partitie admisibila este optimala in spatiul atunci cand momentul de inertie normalizat al acesteia este minim. Celulele Voronoi au tendinta ca, la limita, sa devina hexagoane regulate. Lucrul acesta se explica prin faptul ca, pentru minimizarea distorsiunii date de relatia (42), coeficientul de cuantizare trebuie minimizat. Pentru ;, hexagonul regulat este partitia admisibila optimala din spatiul

In tabelul 1 sunt date valorile momentului de inertie normalizat ale hiper-sferelor si ale unor partitii din pentru diversi.

Este interesant de determinat numarul maxim de puncte adiacente     ale unui vector de cod intr-o partitionare uniforma a spatiului. este egal cu numarul de fete ale unei partitii admisibile optimale din acelasi spatiu sau, altfel spus, numarul maxim de hiper-sfere de volum unitar ce pot fi tangente la o hiper-sfera de acelasi volum unitar fara a se intersecta intre ele. Numarul este marginit superior si inferior conform relatiei:

, (47)

unde este numarul de asimptote ale dimensiunii . Numarul de adiacente este cunoscut exact doar pentru cateva dimensiuni, dupa cum se prezinta in Tabelul Geometric, situatia este reprezentata in figura 9.

Figura 9 Numarul maxim de sfere de volum unitar din spatiul (a), respectiv (b), care pot fi tangente la o sfera de acelasi volum unitar fara a se intersecta intre ele