Compromisul complexitate-distorsiune in potrivirea vectoriala pe baza tehnicilor probabilistice de distanta partiala

Compromisul complexitate-distorsiune in potrivirea vectoriala pe baza tehnicilor probabilistice de distanta partiala

Multe aplicatii de compresie cu pierderi solicita codorului sa efectueze potrivirea vectoriala. Un exemplu clasic este cuantizarea vectoriala in care se urmareste a se determina pentru fiecare vector de intrare cea mai buna potrivire dintre toti vectorii unui dictionar (set de vectori). Complexitatea cautarii depinde atat de dimensiunea vectorilor cat si de marimea dictionarului. Un alt exemplu de potrivire vectoriala il reprezinta estimarea miscarii in codarea video. In acest caz se urmareste a se gasi pentru fiecare bloc-imagine din cadrul video curent cea mai buna potrivire cu blocurile-imagine dintr-o regiune de cautare prestabilita din cadrul anterior. Informatia despre cea mai buna potrivire este trimisa catre decodor sub forma unui vector de miscare.

Atat in cuantizarea vectoriala cat si in estimarea miscarii, potrivirea unui bloc-imagine (vector) cu unul existent intr-un dictionar (set de vectori) se realizeaza prin calcularea unei distante (metrice) dintre blocul din intrare si toate blocurile (vectorii) din setul de cod sau toate blocurile posibile dintr-o regiune prestabilita a cadrului video.

In cazul cuantizarii vectoriale metrica (distanta) folosita in majoritatea aplicatiilor este distanta euclidiana dintre vectorul de intrare si vectorul de cod:

(1)

unde este vectorul de dimensiune ce urmeaza a fi cuantizat, iar este vectorul de cod continut in setul de vectori de cod . Astfel, este vectorul de cod a lui daca:

(2)

In cazul estimarii miscarii, datorita efortului computational redus pentru calculul acesteia, s-a impus o metrica denumita suma diferentelor absolute (SDA). SDA pentru un vector de miscare se defineste ca fiind:

(3)

unde este nivelul de intensitate a pixelului din cadrul , este setul de pixeli din blocul ce urmeaza a fi codat iar , unde este domeniul prestabilit in care poate varia vectorul de miscare. De exemplu, o valoare tipica pentru poate fi regiunea definita de intervalul . Daca SDA este normalizat cu cardinalul unui bloc-imagine, , noua valoare poarta numele de media diferentelor absolute (MDA).

Complexitatea calculului metricei determina complexitatea algoritmului. In principiu, pentru a realiza cea mai buna potrivire, un sistem de codare trebuie sa calculeze toate distantele intre un vector (bloc) de intrare si toti vectorii de cod (in cazul cuantizarii vectoriale) sau toate blocurile posibile (vectorilor de miscare) in cazul estimarii miscarii. Complexitatea algoritmului va depinde de trei factori:

i)            numarul de vectori de cod din setul de vectori de cod, respectiv, numarul de blocuri-imagine ce trebuie testati pentru a gasi cea mai buna potrivire;

ii)           metrica folosita, distanta euclidiana sau SDA;

iii)         dimensiunea a vectorului, respectiv, a blocului.

Astfel, evaluarea si proiectarea unei tehnici de potrivire atat pentru cuantizarea vectoriala cat si pentru estimarea miscarii necesita evaluarea si reducerea complexitatii algoritmului utilizat.

Complexitatea algoritmului poate fi redusa prin:

i)            reducerea numarului de vectori de cod, respectiv a vectorilor de miscare ce trebuie comparati cu vectorul de intrare;

ii)           reducerea numarului de operatii elementare (multiplicari-M, adunari-A si comparatii-C) necesare calcularii distantei dintre doi vectori sau doua blocuri. Se mentioneaza ca numarul de operatii elementare depinde de metrica adoptata precum si de dimensiunea vectorilor, respectiv, a blocurilor imagine implicate.

Ansamblul de tehnici care se ocupa de cuantizarea vectoriala formeaza tehnicile de cautare rapida (CR), iar grupul de tehnici care se ocupa de cautarea celui mai apropiat bloc-imagine pentru un bloc dat poarta numele de tehnici de potrivire rapida (PR). Cele doua tehnici pot fi proiectate astfel incat sa genereze acelasi rezultat ca si cautarea exhaustiva sau, ca alternativa, sa genereze un rezultat suboptimal (ceea ce inseamna ca tehnica adoptata sa genereze un vector de cod sau un bloc care nu este cel mai apropiat in spatiul k-dimensional, dar care se gaseste cu o probabilitate mare intr-o zona restransa din jurul vectorului din intrare). Cea de a doua solutie introduce un factor suplimentar de distorsiune, dar poate cauza o reducere a complexitatii algoritmului de cautare. Tehnicile care gasesc potrivirea perfecta, adica vectorul cu distanta minima fata de vectorul de intrare, se numesc tehnici optimale.

Algoritmii de cautare rapida (CR) se bazeaza pe cautarea a mai putine puncte in interiorul regiunii de cautare prin impunerea unei strategii de cautare. Restrangerea domeniului de cautare se face prin eliminarea, prin operatii cat mai putine, a acelor vectori de cod care nu pot fi in apropierea vectorului de intrare. Un vector de cod se considera a nu fi apropiat de vectorul de intrare daca distanta dintre vectorul de intrare si acel vector de cod este mai mare decat o distanta deja calculata intre vectorul de intrare si un alt vector de cod. Mai mult, un algoritm de cautare bun este un algoritm pentru care rutina de cautare incepe de la un vector de cod cat mai apropiat de vectorul de intrare. Cautarea poate fi oprita atunci cand a fost gasit un candidat destul de bun pentru potrivire. Majoritatea tehnicilor de cautare pentru estimarea miscarii sunt suboptimale, ceea ce inseamna ca nu gasesc cea mai buna potrivire pentru blocul-imagine de referinta. Printr-o usoara crestere a distorsiunii introduse de sistemul de codare, se poate reduce substantial efortul de calcul necesar cautarii si, in consecinta, a timpului mediu de codare a unei secvente video. In literatura din ultimii ani exista numeroase exemple de algoritmi de cautare rapida pentru estimarea miscarii.

In cazul cuantizarii vectoriale, in tehnicile de cautare rapida optimale, vectorii de cod care nu sunt apropiati de vectorul din intrare sunt eliminati primii, apoi se efectueaza cautarea exhaustiva asupra celor ramasi. O alta posibilitate este aceea de a construi un dictionar cu o structura care sa permita cautarea rapida. Un criteriu determinist se defineste ca fiind un criteriu dupa care, cu probabilitate unu, vectorul de cod corespunzator distantei minime nu se afla in setul de vectori eliminati. O alta metoda care reduce substantial cautarea se bazeaza pe algoritmii de cautare intr-o structura sub forma de arbore. Dezavantajul acesteia este acela ca proiectarea setului de vectori de cod poate fi complicata si suboptimala din perspectiva distorsiunii medii.

Desi metodele de cautare rapida sunt vast tratate in literatura, mai putina atentie a fost acordata tehnicilor de potrivire rapida a vectorilor de miscare.

Pentru compensarea miscarii se poate utiliza un algoritm de cautare dupa distanta partiala ce utilizeaza ca metrica suma diferentelor absolute (SDA). Spre deosebire de cuantizarea vectoriala, unde se utilizeaza distanta euclidiana, aceasta metrica poate reduce si mai mult timpul de cautare cu o usoara degradare a performantelor codarii din perspectiva fidelitatii secventelor video. De altfel, aceasta metrica a fost implementata cu succes in multe sisteme video de codare prin soft. Alte tehnici de cautare ce utilizeaza SDA se bazeaza pe reducerea numarului de pixeli folositi pentru a calcula SDA prin decimarea pixelilor din macrobloc.

2. Metode deterministe de cautare rapida pentru estimarea miscarii

Ideea de baza este aceea de a compara un calcul incomplet al distantei cu "cea mai buna distanta gasita pana acum", in timp ce procesul de calcul inca nu s-a terminat. Pe baza monotoniei distantei, (distanta totala creste cu dimensiunea), calculul se poate termina daca distanta partiala este deja mai mare decat "cea mai buna distanta gasita pana in acum". Astfel, cuvantul de cod curent nu poate fi solutia optima si se trece la evaluarea urmatorului cuvant de cod. Aplicarea tehnicii bazate pe distanta partiala pentru cuantizarea vectoriala si estimarea miscarii se formuleaza dupa cum urmeaza. Se defineste distanta partiala intre intrarea si cuvintul de cod cu relatia , adica suma patratelor diferentelor pana la dintre vectorul si cuvantul de cod . Este evident ca pentru .

In continuare, se defineste cuvantul de cod "cel mai bun pana in prezent" pentru vectorul de intrare cu distantele corespunzatoare ca fiind . este submultimea cuvintelor de cod din dictionarul , a caror distanta fata de a fost testata.

Similar, in cazul estimarii miscarii, calculul SDA partiale poate fi definit prin impartirea multimii in k submultimi , unde pentru si . Prin urmare, SDA partiala calculata in iteratia pentru blocul cu vectorul de miscare este si .

"Cel mai bun pana in prezent" vector de miscare pentru blocul este .

Suma distantelor absolute corespunzatoare, , se defineste similar. Multimea este analoga multimii , adica include blocurile ce au fost testate pana in acel moment.

In continuare se prezinta algoritmul distantei partiale pentru estimarea miscarii. Algoritmul pentru cuantizarea vectoriala este similar.

Algoritm de cautare dupa distanta partiala

Pas 1: La inceputul rutinei de cautare, pentru un bloc-imagine dat in intrare, se initializeaza cu o valoare mare, iar vectorul de miscare optim .

Pas 2: Se trece la urmatorul vector de miscare din regiunea de cautare. . Daca numarul vectorilor din regiunea de cautare ce au ramas de evaluat este zero, se returneaza vectorul de miscare optim .

Pas 3: Se calculeaza .

Pas 4: Daca se trece la Pas 5, altfel se trece la Pas 3.

Pas 5: Daca se trece la Pas 2, altfel si se trece la Pas 3.

Pas 6: Daca , si , se trece la Pas 2.

Reducerea complexitatii algoritmului de cautare expus se datoreaza pasului 5 unde se opreste calculul distantei in momentul in care distanta partiala calculata depaseste "cea mai buna distanta pana in prezent". Aceasta reducere a complexitatii este dependenta de statistica vectorilor din intrare si de statistica vectorilor din regiunea in care se face cautarea. De asemenea aceasta tehnica de cautare este dependenta de modul in care se aleg vectorii de miscare la Pas 2 si de valoarea initiala a lui . Performantele algoritmului pot fi imbunatatite daca se utilizeaza in prealabil o proiectie pe componentele principale si daca vectorii de cod sunt aranjati in ordinea descrescatoare a probabilitatii lor de aparitie. In general, cu cat o tehnica de cautare rapida este mai eficienta, cu atat timpul de codare obtinut prin gasirea cu testare determinista a celui mai potrivit bloc va fi mai mic.

3. Potrivirea rapida prin testarea ipotezelor

Un dezavantaj al potrivirii rapide prin testare determinista este acela ca nu prezinta accesibilitate computationala, adica nu permite obtinerea unei solutii rapide cu pretul unei oarecare reduceri a calitatii. In continuare se investigheaza algoritmi care prezinta accesibilitate computationala, adica reducerea graduala a complexitatii se face cu pretul reducerii corespunzatoare a potrivirii calitatii. Acesti algoritmi se bazeaza pe metoda potrivirii rapide prin testarea ipotezelor care utilizeaza ipoteze de test pentru a decide cand se termina cautarea la pasul 5 din algoritmul anterior. Ideea de baza este de a estima intai metrica distanta din distanta partiala calculata la iteratia . Diferenta dintre distanta actuala si cea estimata poate fi modelata ca o variabila aleatoare cu o anumita functie densitate de probabilitate. Suplimentar testarii distantelor partiale se poate adauga o regula de decizie pentru a determina daca estimatul bazat pe distanta partiala permite luarea deciziei ca distanta finala totala este mai mare decat distanta "cea mai buna pana in prezent". Aceasta decizie se ia tinand cont de faptul ca estimatul este demn de incredere, asa cum s-a determinat din modelul de probabilitate. Daca estimatul prezinta suficienta incredere, cautarea se termina. In caz contrar, se continua calculul metricei la iteratia urmatoare (cea include o crestere a dimensiunii vectorilor). In acest fel potrivirea rapida prin testarea ipotezelor combina testul distantei partiale si testul ipotezelor.

In continuare se prezinta doua aplicatii de potrivire rapida prin testarea ipotezelor la estimarea miscarii si cuantizarea vectoriala.

Rezultate experimentale

1. Estimarea miscarii

In cele ce urmeaza, se considera media diferentelor absolute (MDA) drept metrica. Astfel "cea mai buna pana in prezent" MDA si MDA partiala corespunzatoare iteratiei se definesc cu relatiile si, respectiv, , unde reprezinta cardinalul multimii. Se pleaca de la exprimarea estimatului mediei diferentelor absolute din media partiala a diferentelor absolute. Considerand distanta si distantele partiale ca procese aleatoare, cea mai buna estimare in sensul mediei patratice este valoarea medie a distantei in functie de distanta partiala, adica . Din observatiile experimentale poate fi aproximat de , cu eroarea de estimare devenind din ce in ce mai mica cu cresterea lui , dupa cum se vede in figura 1. Aceasta figura arata histogramele dintr-o secventa tipica de erori de estimare la diverse valori ale lui unde a fost partitionat in 16 submultimi . este multimea pixelilor din primele i randuri ale macroblocului.

Figura 1. Histogramele erorii de estimare folosind ca un estimat pentru in 16 iteratii parcurse de la stanga la dreapta si de sus in jos

Intuitiv, ar putea fi evident ca, asa cum confirma experimentele, cu cat se folosesc mai multi pixeli cu atat acuratetea estimarii este mai buna, in medie, pentru estimarea cu SDA. Prin urmare se va obtine cel mai bun vector de miscare daca se foloseste numai SDA partiala. Mai mult, histogramele rezultate pot fi vazute ca estimati ai functiei densitate de probabilitate ai erorii de estimare. Pentru estimarea miscarii, in cele mai multe cazuri, functia densitate de probabilitate poate fi bine aproximata de distributia laplaciana.

In continuare se prezinta o procedura de proiectare a regulii de decizie pentru testarea ipotezelor. Date fiind si se doreste a se decide intre doua ipoteze:

i)            exista o mare probabilitate ca final sa fie mai mare decat curent si sa se opreasca calculul sau

ii)           nu se dispune de un estimat suficient de demn de incredere si se calculeaza , adica se trece la iteratia pentru metrica si se testeaza din nou.

Dat fiind ipotezele sunt:

Parametrul care determina performanta regulii de decizie este probabilitatea alarmei false, . Prin urmare se pune problema gasirii regulii optime de decizie astfel incat unde este probabilitatea limita aleasa pentru alarma falsa.

Conditia poate fi scrisa astfel:

si regula de decizie optimala este :

(1)

Deoarece membrul stang al relatiei (1) poate fi scris sub forma . Membrul drept este .

Regula de decizie devine

(2)

unde este pragul.

Aceasta situatie este redata in figura 2.

Figura 2. Histograma erorii de estimare obtinuta din datele de antrenare (cu linie continua) si modelarea parametrica (cu linie intrerupta)

Relatia (2) este adaugata testului de distanta partiala din sectiunea precedenta. Folosind modelul distributiei Laplace , unde este parametrul laplacian pentru iteratia , pragul poate fi scris sub forma

(3)

In general, ipotezele de test se pot proiecta diferit pentru fiecare iteratie, adica poate sa fie diferit pentru fiecare iteratie. Pentru simplitate, insa, se impune constant pentru toate iteratiile experimentului. Chiar pentru acelasi , variaza in functie de de la fiecare iteratie. In experimentele noastre se foloseste o aproximare rapida a parametrilor care estimeaza adaptiv pentru fiecare 15 cadre.

Metoda potrivirii rapide prin testarea ipotezelor a fost aplicata la cautarea exhaustiva, cautarea logaritmica 2-D si cautarea spatio-temporala corelata (ST1). Rezultatele obtinute din aplicarea potrivirii rapide prin testarea ipotezelor sunt prezentate in figurile 3 si 4, unde distorsiunea este energia blocurilor reziduale, iar complexitatea se masoara atat in numarul de comparatii intre pixeli cat si prin numarul de cicluri masina consumati in simulare. Drept secvente de test au fost considerate secventele "calendarul mobil" si "fotbal". Reprezentarea curbei complexitate - distorsiune se face in functie de parametrul care ia valori intre 0.01 si 0.2.

Fig. 3 Reprezentarea complexitate - distorsiune a 150 cadre pentru secventa "calendar mobil". Linie punctata - cicluri masina; linie continua - numarul de pixeli comparati

Fig. 4 Reprezentarea complexitate - distorsiune a 150 cadre pentru secventa "fotbal". Linie punctata - cicluri masina; linie continua - numarul de pixeli comparati

2. Cuantizarea vectoriala

Ca si in cazul estimarii miscarii, intai se adopta metrica respectiv . Primul obiectiv este estimarea lui din . Apoi se determina functia densitate de probabilitate a erorii de estimare si aceasta se modeleaza astfel incat sa se poata proiecta regula de decizie pe baza testarii ipotezelor care sa respecte probabilitatea impusa pentru alarma falsa. Ca si in cazul estimarii miscarii, se ajunge la concluzia ca poate fi bine aproximat de . Pentru simplitate, se poate aproxima, de asemenea, functia densitate de probabilitate a erorii de estimare folosind functia de distributie laplaciana, ca in cazul estimarii miscarii, si sa se proiecteze regula de decizie pe baza acestei presupuneri. Parametrul laplacian in cazul cuantizarii vectoriale se obtine din vectorii de antrenare. Rezultatul complexitate-distorsiune obtinut cu ajutorul potrivirii rapide prin testarea ipotezelor este aratat in figura 5, care prezinta rezultatul potrivirii rapide prin testare determinista la diferite marime ale setului de vectori de cod ca si graficele corespunzatoare potrivirii rapide prin testarea ipotezelor pentru o dimensiune a dictionarului (setului de vectori) cu variind in domeniu 0.05-0.055. In figura 5 sursa este gaussiana cu vectorii generati independenti si identic distribuiti (i.i.d.), de dispersie unitara.

Fig. 5. Reprezentarea complexitate-distorsiune a cuantizarii vectoriale cu potrivirea rapida prin testarea ipotezelor pentru marimea vectorului egala cu 8 pentru o sursa i.i.d.

Se observa ca, spre deosebire de cazul estimarii miscarii in care marimea echivalenta a dictionarului este fixata prin regiunea de cautare, in cazul cautarii vectoriale, marimea dictionarului poate fi aleasa sa respecte cerintele complexitate-distorsiune. Se observa ca pentru a opera in modul computational accesibil, in cazul potrivirii rapide cu testare determinista marimea dictionarului trebuie sa fie modificata in timp ce accesibilitatea se obtine cu o marime constanta a dictionarului pentru cazul potrivirii rapide cu testarea ipotezelor. In figura 5 performantele complexitate-distorsiune obtinute cu potrivirea rapida prin testarea ipotezelor este aproximativ aceeasi cu cea obtinuta cu potrivirea rapida prin testare determinista, folosind marimi diferite ale dictionarului in cadrul unei anumite iteratii. Aceasta se datoreaza urmatorilor factori:

i)            viteza obtinuta cu metoda potrivirii rapide cu testare determinista este deja mare, adica metoda este de trei patru ori mai rapida decat metoda traditionala MSE. Mai mult de 90% din calculele distantei sunt finalizate mai repede de algoritmul potrivirii rapide prin testare determinista si cele mai multe finalizari se produc in primele iteratii.

ii)           metoda potrivirii rapide prin testarea ipotezelor introduce un cost suplimentar pentru testarea ipotezelor in timpul primelor iteratii. Oricum, numarul de terminari la primele iteratii este relativ mic in comparatie cu castigul general atins prin metoda testarii deterministe.

iii)         dimensiunea vectorului in cazul estimarii vectoriale este de departe mai mica decat in cazul estimarii miscarii (1616).