Aspecte generale ale compresiei semnalelor video

Aspecte generale ale compresiei semnalelor video

Compresia video poate fi vazuta ca o compresie de imagini, specifica fiecarui cadru, cu o componenta temporala, specifica succesiunii de cadre, deoarece semnalul video este format dintr-o secventa de imagini. Din acest punct de vedere, pe langa tehnicile de compresie a imaginilor, se vor exploata si avantajele corelatiei temporale existente intre cadre. Dintre toate sursele de date, secventa video este caracterizata prin cel mai mare volum de date. Cadrul unei astfel de secvente generate cu formatul CCIR 601 are mai mult de 250.000 pixeli. La o rata de 30 cadre/sec si 16 biti/pixel, rezulta 168 Mbiti/sec.

In tratarea compresiei video ca o compresie de imagini cu o componenta temporala, desi frecvent folosita, exista limitari determinate de modul de percepere a miscarii video, fata de perceperea imaginilor. Pe de o parte, miscarea poate masca artefacte de codare, ce ar putea fi vazute la imagini, iar, pe de alta parte, artefactele care nu ar trebui sa fie vizibile in reconstructia imaginilor pot fi deranjante in reconstructia secventelor video.

Cei mai multi algoritmi de compresie video folosesc corelatia temporala pentru a inlatura redundanta. O metoda larg folosita este codarea diferentiala, in care cadrul curent este reconstruit pe baza celui precedent si a erorii reziduale. In general, algoritmii de codare a semnalelor video tin cont de tipul de imagine din cadre, miscarea obiectelor din cadre, domeniul de aplicatie etc., motiv pentru care nu se poate da o descriere generala a acestora. Cu toate ca s-au facut eforturi de a gasi standarde "generice" algoritmii de codare, cerintele aplicatiei joaca un rol esential in determinarea caracteristicilor ce urmeaza a fi folosite.

Deoarece, in general, algoritmii de compresie sunt proiectati pentru comunicarea bidirectionala, este necesar ca intarzierea introdusa la codare sa fie minima, iar procedurile de compresie si decompresie sa fie de complexitati comparabile. Sistemele asimetrice sunt agreate, de obicei, in aplicatiile de redare de pe medii de stocare sau difuziune, in care exista un singur emitator si mai multi receptori, caz in care codorul poate fi mult mai complicat decat receptorul. In mod analog, in aplicatiile in care secventele video urmeaza a fi decodate pe o statie de lucru, complexitatea decodarii trebuie sa fie scazuta, pentru ca decodorul sa poata decoda un numar suficient de imagini, astfel incat sa existe senzatia de miscare.

Daca semnalul video urmeaza a fi transmis printr-o retea, sub forma de pachete, la proiectarea algoritmilor de compresie trebuie avut in vedere efectul pierderii acestora. Din cele expuse pana acum se desprinde ideea ca fiecare aplicatie prezinta propiile cerinte particulare si necesita o solutie dedicata care sa le rezolve.

In general, compresia video se bazeaza pe doua principii. Primul este redundanta spatiala care exista in fiecare cadru. Cel de-al doilea este acela ca in cea mai mare parte, cadrul video curent difera putin de vecinii lui. Aceasta este numita redundanta temporala. Tehnica tipica pentru compresia video ar putea fi codarea primului cadru utilizand metode de compresie a imaginii nemiscate. Pe baza acesteia s-ar putea apoi coda fiecare cadru succesiv pentru identificarea diferentelor intre un cadru si predecesorul sau si coda apoi aceste diferente. Daca cadrul este foarte diferit de predecesorul sau, acesta ar putea fi codat independent de orice alt cadru. In literatura compresiei video, cadrul care este codat folosind predecesorul sau este numit cadru inter (sau doar inter), in timp ce cadrul care este codat independent este numit cadru intra (sau doar intra).

Compresia video este, de obicei, cu pierderi. Codarea cadrului cu ajutorul predecesorului sau introduce unele distorsiuni. Ca rezultat, codarea cadrului cu ajutorul lui creste distorsiunea. Daca cadrul a pierdut un numar de biti, atunci toate cadrele urmatoare acestuia, pana la urmatorul cadru intra, sunt decodate necorespunzator. Din acest motiv cadrele intra ar putea fi folosite din cand in cand in interiorul unei secvente, nu numai la inceputul sau. Un cadru intra are eticheta I, si un cadru inter are eticheta P.

Un cadru inter poate fi codat pe baza unuia din predecesorii sai si pe unul din succesorii sai. Se stie ca un codor nu ar trebui sa utilizeze nici o informatie care nu este disponibila pentru decodor, dar compresia video manipuleaza cantitati mari de date. In mod normal, trebuie avut in vedere ca la emisie codorul poate sa fie lent, in timp ce, la receptie decodorul trebuie sa fie rapid. Un exemplu tipic este inregistrarea pe banda video pe un hard disk sau DVD, atunci cand se da banda inapoi. Codorului ii poate lua minute sau ore pentru codarea datelor. Decodorul, insa, trebuie sa dea banda inapoi la corectarea ratei de cadru (deci multe cadre pe secunda), asa ca acesta trebuie sa fie foarte rapid. Acesta este motivul pentru care un decodor tipic video lucreaza in paralel. Decodorul are cateva circuite de decodificare ce lucreaza simultan pe cateva cadre.

Se poate imagina situatia in care codorul codeaza cadrul 2 bazandu-se pe cadrele 1 si 3. In acest caz codarea cadrelor in decursul compresiei se efectueaza in ordinea 1,3,2. Decodorul le citeste in aceasta ordine, decodand cadrele 1 si 3 in paralel, furnizeaza la iesire cadrul 1, apoi decodeaza cadrul 2 bazandu-se pe cadrele 1 si 3. Cadrele ar trebui, desigur, sa fie in mod clar etichetate. Un cadru care este codat pe baza cadrului anterior si urmator are eticheta B (bidirectional).

Predictia unui cadru pe baza succesorului sau are sens in cazurile cand miscarea unui obiect in imagine nu acopera treptat o suprafata din fundal. O astfel de suprafata poate fi partial cunoscuta in cadrul curent, dar poate fi cunoscuta mai bine in urmatorul cadru. Astfel, urmatorul cadru este un candidat potrivit pentru predictia acestei suprafete in cadrul curent.

Asadar, intr-o secventa video compresata intervin trei tipuri de cadre I, P si B. Cadrul I este decodat independent de orice cadru. Cadrul P este decodat utilizand cadrul anterior I sau P. Un cadru B este decodat utilizand cadrele I sau P anterior si respectiv, urmator. Figura 1.1a prezinta o secventa de astfel de cadre in ordinea in care ele sunt generate de codor. Figura 1.1b prezinta aceleasi cadre in ordinea in care sunt obtinute la iesirea decodorului si afisate. Cadrul etichetat cu 2 ar trebui sa fie afisat dupa cadrul 5, asa ca fiecare cadru ar trebui sa aiba doua etichete temporale, una care indica timpul de codare si alta, timpul de afisare.

(a)

(b)

Fig. 1.1. a) Ordinea de codare b) Ordinea de afisare

1.2. Reprezentarea semnalului video

Primele eforturi pentru digitizarea semnalului video au fost dedicate esantionarii semnalului compus. In Statele Unite s-a dezvoltat un standard care necesita esantionarea semnalului NTSC la ceva mai mult de 14 milioane de esantioane pe secunda. In Europa eforturile standardizarii vizeaza caracteristicile semnalului PAL. Datorita diferentelor dintre sisteme, rezulta "standarde" diferite. Spre sfarsitul anilor 70, s-a convenit asupra esantionarii componentelor semnalului compus si CCIR a dezvoltat un standard international, numit 601-2, cunoscut ca ITU-R. Acesta propune o familie de frecvente de esantionare pe baza frecventei de 3,725 MHz. Multipli ai acestei frecvente permit generarea unei matrice rectangulare de pixeli, necesare procesarii digitale. Fiecare componenta a semnalulu video (componenta de luminanta Y si componentele de crominanta U si V) poate fi esantionata la multipli intregi de 3,725 MHz, apoi acestea sunt normalizate si digitizate. Datele YUV pot fi aranjate in alte formate, dupa necesitatile impuse de aplicatie. In formatul CIF (Common Interchange Format) folosit pentru videoconferinte, semnalul de luminanta este reprezentat ca o matrice 288 x 352 pixeli, iar cele doua semnale de crominanta sunt reprezentate ca matrice 144 x 176 pixeli. In formatul QCIF se folosesc jumatate din numarul de pixeli pe linii si coloane.

In algoritmul MPEG-1 folosit pentru codarea video la rate de pana la 1,5 MHz se foloseste o subesantionare a formatului CCIR 601 pentru a obtine formatul MPEG-SIF. Plecand de la formatul CCIR 601 cu 480 linii, se foloseste sistemul 4:2:2, in care intai este redusa rezolutia verticala pentru toate componentele semnalului, apoi este redusa cea orizontala prin filtrare (antialias) si subesantionare cu factorul 2, care are ca rezultat o matrice pentru Y de forma 360 x 240pixeli, iar pentru U si V de forma 180 x 240 pixeli.

1.3. Metode de compresie video

Subesantionarea. Codorul selecteaza fiecare al doilea cadru si il scrie in fluxul compresat. Se produce un factor de compresie 2. Decodorul introduce un cadru si il copie pe acesta pentru a se crea doua cadre.

Diferentierea. Cadrul este comparat cu predecesorul sau. Daca diferenta intre cadre este mica, codorul codeaza pixelii care sunt diferiti prin scrierea a trei numere in fluxul compresat pentru fiecare pixel: coordonatele imaginilor sale si diferenta dintre valorile pixelului in cele doua cadre. Daca diferenta intre cele doua cadre este mare, cadrul curent va fi codat in intregime.

Versiunea cu pierderi a acestei metode consta in compararea diferentei dintre intensitatile pixelului din cadrul precedent si cadrul curent cu un anumit prag. Daca diferenta este mai mica decat pragul impus, pixelul nu este considerat diferit.

Diferentierea de bloc. Aceasta metoda este o inbunatatire a metodei precedente. Imaginea este impartita in blocuri de pixeli, si fiecare bloc B din cadrul curent este comparat cu blocul P ce corespunde cadrului anterior. Daca blocurile difera prin mai mult de o anumita cantitate, atunci B este comprimat prin scrierea coordonatelor imaginii sale urmate de valorile tuturor pixelilor sai (ce au fost exprimate ca diferente) in fluxul compresat. Avantajul este ca coordonatele blocului sunt numere mici (mai mici decat a coordonatelor pixelor sai), si aceste coordonate trebuie sa fie scrise o singura data pentru blocul intreg. Aceasta metoda este sensibila la dimensiunea blocului.

Compensarea miscarii Oricine priveste un film stie ca diferenta intre cadrele consecutive este mica deoarece aceasta este rezultatul miscarii scenei, camerei, sau ambelor, intre cadre. Acesta trasatura poate fi, deci, exploatata pentru a se obtine o compresie mai buna. Daca codorul descopera ca o parte P din cadrul anterior are o miscare rigida la o locatie diferita in cadrul curent, atunci P poate fi compresat prin scrierea urmatoarelor trei marimi in fluxul compresat: locatia sa anterioara, locatia sa curenta, si informatia de identificare a limitelor blocului P.

In practica se lucreaza, de obicei, cu blocuri de marime egala (in mod normal patrate dar pot fi de asemenea si dreptunghiuri). Codorul scaneaza cadrul curent, bloc cu bloc. Pentru fiecare bloc B acesta cauta in cadrul anterior un bloc C identic cu acesta (daca compresia este fara pierderi) sau un bloc asemanator cu acesta (daca compresia este cu pierderi). Descoperind un astfel de bloc, codorul scrie diferenta intre locatia prezenta si cea trecuta. Aceasta diferenta este de forma:

, (1.1)

si poarta denumirea de vector de miscare. Figura 1.2a,b prezinta un exemplu simplu unde soarele si copacii sunt miscati in mod rigid spre dreapta (din cauza miscarii camerei), in timp ce copilul se misca la o distanta diferita la stanga (aceasta este miscarea scenei).

Fig. 1.2 Compensarea miscarii

Compensarea miscarii este eficace daca obiectele sunt numai translate, nu scalate sau rotite. Schimbarile drastice de iluminare de la cadru la cadru reduc, de asemenea, eficacitatea acestei metode.

Segmentarea cadrului. Cadrul curent este impartit in blocuri de marimi egale nesuprapuse. Blocurile pot fi patrate sau dreptunghiulare. In cazul al doilea, miscarea este in mare parte orizontala, asa ca blocurile orizontale reduc numarul vectorilor de miscare fara degradarea raportului de compresie. Marimea blocului este importanta, deoarece blocurile mari reduc sansele de gasire a potrivirilor, pe cand blocurile mici conduc la mai multi vectori de miscare. In practica, marimile blocului sunt puteri intregi ale lui 2, (uzual 8 sau 16), deoarece aceasta simplifica soft-ul.

Cautarea blocului. Acesta este un proces indelungat si trebuie sa fie proiectat cu atentie. Daca B este blocul curent in cadrul curent, atunci in cadrul anterior trebuie sa se caute un bloc identic sau foarte asemanator cu B. Cautarea este limitata in mod normal intr-o arie mica (numita arie de cautare), definita prin parametrii deplasarii maxime dx si dy. Acesti parametri specifica distantele maxime pe orizontala si verticala, in pixeli, intre B si oricare bloc potrivit in cadrul anterior. Daca B este un patrat de latura b, aria de cautare va contine pixeli (Fig. 1.3) si se va compune din patrate distincte, care se suprapun. Numarul blocurilor candidate in aceasta arie este deci proportional cu .

Fig. 1.3 Aria de cautare

Pragul de cautare. Fiecare bloc B din cadrul curent este intai comparat cu omologul sau C din cadrul anterior. Daca ele sunt identice, sau diferenta intre ele este mai mica decat pragul curent, codorul consirera ca acel bloc nu a fost miscat.

Marimea distorsiunii. Aceasta este cea mai sensibila parte de codare. Masura distorsiunii selecteaza cea mai buna potrivire pentru blocul B. Aceasta poate sa fie simpla sau complicata, dar trebuie sa fie demna de incredere.

Media diferentei absolute (sau eroarea medie absoluta) calculeaza media diferentelor absolute intre pixelul din B si corespondentul sau din blocul candidat C:

(1.2)

Aceasta implica scaderi si valori absolute, adunari, si o divizare. Aceasta masura este calculata pentru fiecare din cele blocuri candidate distincte, suprapuse, de dimensiune , si este examinata cea mai mica distorsiune (fie aceasta pentru blocul ). Daca aceasta este mai mica decat pragul de cautare, atunci este potrivire pentru B. Altfel, nu exista potrivire pentru B, si B trebuie sa fie codat fara compensarea miscarii.

Diferenta patratica medie este o marime similara, unde patratul diferentei de pixel este calculat cu relatia:

(1.3)

Marimea clasificarii diferentei pixelului numara cat de multe diferente sunt mai mici decat un parametru p.

Marimea proiectiei integrale calculeaza suma unui rand din cadrul B si o scade pe aceasta din suma randului corespunzator din cadrul C. Valoarea absoluta a diferentei este adunata la valoarea absoluta a diferentei sumei coloanelor:

Metode de cautare suboptimale. Aceste metode cauta cateva din blocurile candidate in aria . In felul acesta se accelereaza cautarea pentru descoperirea unei potriviri a blocului astfel incat compresia sa se faca cat mai usor si cat mai repede.

Corectia vectorului de miscare. O data ce un bloc C este selectat ca fiind cel mai potrivit pentru B, vectorul de miscare este calculat ca diferenta intre coltul stang de sus din C si cel corespunzator din B. Indiferent de felul in care a fost determinata potrivirea, vectorul de miscare poate fi eronat din cauza zgomotului, minimelor locale din cadru, sau din cauza algoritmului de potrivire. In incercarea de crestere a potrivirii este posibil a aplica tehnici de netezire pentru vectorii de miscare dupa ce ei au fost calculati. Corelatiile spatiale din imagine sugereaza ca vectorii de miscare sunt de asemenea corelati. Daca anumiti vectori sunt descoperiti ca incalca acest lucru, ei pot fi corectati.

Acest pas este costisitor si poate fi ineficient. O imagine video poate implica miscarea usoara, lina a celor mai multe obiecte, dar, de asemenea, si miscari bruste, rapide ale unor obiecte mici. Corectarea vectorilor de miscare poate interfera cu vectorii de miscare ai acestui tip de obiecte si cauza distorsiuni in cadrele compresate.

Codarea vectorilor de miscare. O parte mare a cadrului curent (poate si pana la o jumatate din el) poate fi convertita in vectori de miscare, prin urmare modul in care acesti vectori sunt codati este decisiv; acest lucru trebuie sa se faca, de asemenea, fara pierderi. Doua proprietati ale vectorilor de miscare ajuta la codarea lor: (1) ei sunt corelati si (2) distributia lor este neuniforma. Pe masura ce se scaneaza cadrul bloc cu bloc, in mod normal, vectorii de miscare ai blocurilor adiacente nu sunt foarte diferiti; ei sunt corelati. De asemenea, ei nu sunt orientati in toate directiile. Exista in mod normal una sau doua directii preferate in care sunt orientati toti sau cei mai multi vectori de miscare; vectorii sunt de asemenea distribuiti neuniform.

Nici o metoda, singura, nu s-a dovedit ideala pentru codarea vectorilor de miscare. Au fost incercate codarea aritmetica, codarea Huffman adaptiva, si diverse codari cu coduri prefix si toate par a avea performante bune. Totusi, doua metode diferite s-au dovedit superioare:

1. Predictia vectorului de miscare pe baza predecesorilor sai din acelasi rand si predecesorii sai din aceeasi coloana ai cadrului curent. Se calculeaza diferenta intre vectorul curent si cel predictat, si rezultatul se codeaza Huffman. Metoda este utilizata in MPEG si alte metode de compresie.

2. Se grupeaza vectorii de miscare in blocuri. Daca toti vectorii dintr-un bloc sunt identici, blocul este codat prin codarea acestui vector. Celelalte blocuri sunt codate ca mai sus. Fiecare bloc codat incepe cu un cod care identifica tipul sau.

Codarea erorii de predictie: Compensarea miscarii este cu pierderi, deoarece un bloc B este in mod normal potrivit cu un bloc oarecum diferit, C. Compresia poate fi imbunatatita prin codarea diferentei intre cadre, bloc cu bloc, si doar pentru blocurile care difera mult. Aceasta se efectueaza de obicei prin codarea prin transformare. Diferenta este scrisa la iesire, urmarind fiecare cadru si este folosita de decodor pentru a imbunatati cadrul dupa ce acesta a fost decodat.

1.4. Metode de cautare suboptimale

Compresia video include mai multi pasi si calcule, asa ca s-au cautat optimizari si algoritmi mai rapizi, in special pentru pasii care implica multe calcule. Un astfel de pas este de cautare a unui bloc C in cadrul anterior care sa se potriveasca cu blocul B din cadrul curent. O cautare exhaustiva este consumatoare de timp, asa ca se foloseste o metoda de cautare suboptimala care cauta numai unele din blocurile candidate suprapuse. Aceste metode nu conduc totdeauna la cea mai buna potrivire, dar pot grabi procesul de compresie, cu pretul unei mici piereri a eficientei compresiei.

Metode bazate pe semnatura. Astfel de metode executa un numar de pasi, limitand numarul de blocuri candidate in fiecare pas. In primul pas, toate blocurile candidate sunt cautate utilizand un criteriu simplu de distorsiune, cum ar fi clasificarea diferentei pixelului. Doar blocurile care se potrivesc cel mai bine cu blocul principal sunt incluse la pasul urmator, unde ei sunt evaluati printr-o masura a distorsiunii mai restrictiva sau prin aceeasi masura, dar cu un parametru mai mic. O metoda pe baza de semnatura poate implica un numar de pasi, utilizand masuri de distorsiune diferite pentru fiecare pas.

Cautarea distantei atenuate. Din experienta se stie ca obiectele cu miscare rapida arata neclare in animatie, chiar daca ele sunt bine delimitate in toate cadrele. Aceasta indica un mod de pierdere a datelor. Se poate impune o potrivire buna a blocului pentru miscarea lenta a obiectelor, si o potrivire mai slaba pentru miscarea rapida a acestora. Rezultatul este un algoritm de potrivire a blocului care cauta toate blocurile apropiate de B, dar din ce in ce mai putine, pe masura ce cautarea se departeaza de B. Figura 1.4 prezinta cum o astfel de metoda poate lucra pentru parametrii de deplasare maxima . Numarul total de blocuri C care sunt cautate se modifica de la la exact 65, adica mai putin de 39%.

Fig. 1.4 Cautarea distantei atenuate pentru

Cautare bazata pe localizare: Aceasta metoda se bazeaza pe presupunerea ca a fost gasita o buna potrivire, chiar daca este posibil a se gasi potriviri mai bune localizate in apropiere. Un algoritm uzual este de a porni cautarea pentru o potrivire intr-un set imprastiat, rar, de blocuri si apoi sa se utilizeze blocul cu cea mai buna potrivire, C, drept centru pentru a doua unda de cautare, dar de aceasta data intr-un set mai dens de blocuri. Figura 1.5 prezinta doua unde de cautare, prima unda considera blocurile departate, selectand cea mai buna potrivire. Cea de-a doua unda cauta fiecare bloc in vecinatatea celei mai bune potriviri.

Fig. 1.5 Cautare locala

Cautarea rectangulara monotona. Aceasta este o varianta a cautarii pe baza localizarii. Ea porneste cu o multime rara de blocuri C care sunt cercetate pentru potrivire. Pentru fiecare bloc se calculeaza marimea distorsiunii si rezultatul este o multime de valori. Marimea acestor distorsiuni creste cu departarea de cea mai buna potrivire. Din examinarea multimii de distorsiuni obtinute in primul pas, in pasul al doilea se poate estima unde este posibil a gasi cea mai buna potrivire. Aceasta metoda este mai putin demna de incredere deoarece directia propusa de multimea valorilor distorsiunilor conduce la cel mai bun bloc local, in timp ce cel mai bun bloc poate fi localizat altundeva.

Algoritmi dependenti. Dupa cum s-a mentionat anterior, miscarea in cadru este rezultatul miscarii camerei sau miscarii obiectului. Daca obiectele din cadru se presupun mai mari decat blocul, este normal sa decidem ca vectorii de miscare a blocurilor adiacente sunt corelati. Algoritmul de cautare poate asadar incepe cu estimarea vectorului de miscare a blocului B din vectorii de miscare care au fost deja gasiti pentru vecinii sai, iar apoi se imbunatateste acest estimat prin compararea lui B cu alte blocuri candidate, C. Aceasta este baza catorva algoritmi dependenti, care pot fi spatiali sau temporali.

Dependenta spatiala. In algoritmul cu dependenta spatiala, vecinii blocului B din cadrul curent sunt utilizati pentru estimarea vectorului de miscare a lui B. Acestia, desigur, trebuie sa fie vecinii ai caror vectori de miscare au fost deja calculati. Cele mai multe blocuri au opt vecini fiecare, dar utilizarea tuturor celor opt poate sa nu fi cea mai buna strategie (de asemenea, exista posibilitatea ca doar unii din vecinii sai sa aiba vectorii lor de miscare deja estimatii). Daca blocurile sunt potrivite in ordinea rastrului, atunci este firesc a folosi unul, doi sau trei vecini potriviti anterior, cum se arata in Fig. 1.6a,b,c. Din cauza simetriei, totusi o strategie mai buna este de a utilizarea patru vecini simetrici, ca in figura 1.6d,e. Acest lucru poate fi efectuat cu o metoda in trei treceri care scaneaza blocurile ca in figura 1.6f. Prima trecere scaneaza toate blocurile de culoare neagra (o patrime a blocurilor din cadru). Vectorii de miscare pentru aceste blocuri sunt calculati prin alte metode. A doua trecere scaneaza blocurile gri (25% din blocuri) si evalueaza vectorul de miscare pentru fiecare, utilizand vectorii de miscare ai vecinilor sai din cele patru colturi. Blocurile albe (cele 50% ramase) sunt scanate la a treia trecere, si vectorul de miscare al fiecaruia este estimat utilizand vectorii de miscare ai vecinilor sai din cele patru parti. Daca vectorii de miscare ai vecinilor sunt foarte diferiti, acestia ar putea sa nu fie utilizati, si vectorul de miscare pentru blocul B sa se calculeze utilizand o alta metoda.

Fig. 1.6. Strategii pentru algoritmii de cautare dependent spatial

Dependenta temporala: Vectorul de miscare al blocului B din cadrul curent poate fi evaluat ca vector de miscare al aceluiasi bloc din cadrul anterior. Acest lucru are sens daca miscarea se presupune uniforma. Dupa ce vectorul de miscare din B este evaluat in acest fel, el ar trebui sa fie imbunatatit si corectat utilizand alte metode.

Cautarea logaritmica bidimensionala. Aceasta metoda multipas reduce aria de cautare in fiecare pas pana cand aceasta se reduce la un singur bloc. Se presupune ca blocul curent B este localizat la pozitia (a,b) in cadrul curent. Aceasta pozitie devine centrul initial de cautare. Algoritmul foloseste un parametru de distanta d care defineste aria de cautare. Aria de cautare consta din blocuri centrate pe blocul curent B.

Pasul 1: Marimea pasului s este calculata cu relatia

(1.5)

si algoritmul compara B cu cele cinci blocuri de la pozitiile , , , , si din cadrul anterior. Aceste cinci blocuri formeaza structura unui semn plus +.

Pasul 2: Este selectata cea mai buna potrivire dintre cele cinci blocuri. Pozitia acestui bloc se noteaza cu . Daca , atunci s este injumatatit (acesta este motivul pentru numele logaritmic). Altfel, s ramane acelasi si centrul de cautare este mutat la.

Pasul 3: Daca s=1, atunci sunt cautate cele noua blocuri in jurul centrului de cautare si cea mai buna potrivire devine rezultatul algoritmului. Altfel, algoritmul trece la pasul 2.

Oricare din blocurile care ar trebui sa fie cautate, dar sunt in exteriorul ariei de cautare sunt ignorate si nu sunt utilizate la cautare. Figura 1.7 prezinta cazul in care . Pentru simplitate, se admite ca blocul curent B are coordonatele cadrului . Cautarea este limitata la aria blocului de centrata pe blocul B. Pasul 1 calculeaza

(1.6)

si cauta cele cinci blocuri (etichetate cu 1) la pozitiile , , , , si . Se presupune ca cea mai buna potrivire din aceste cinci pozitii este , asa ca aceasta pozitie devine noul centru de cautare, si cele trei blocuri (etichetate cu 2) de la pozitiile , , si sunt cautate la pasul al doilea.

Presupunand ca cea mai buna potrivire printre aceste trei blocuri este la pozitia , la pasul urmator se cauta cele doua blocuri etichetate cu 3 la locatiile si , blocul (etichetat 2) de la si blocurile etichetate cu 1 pozitionate la si .

Fig. 1.7 Metoda de cautare logaritmica dublu dimensionala

Cautarea in trei pasi. Aceasta este oarecum similara cautarii logaritmice bidimensionale. In fiecare pas se testeaza opt blocuri, in loc de patru, in jurul centrului de cautare, deci la jumatate din marimea pasului. Daca initial s=3, algoritmul se termina dupa 3 pasi, de unde si denumirea sa.

Cautarea ortogonala. Aceasta este similara cu cautarea logaritmica bidimensionala si cea in trei pasi. Fiecare pas din cautarea ortogonala implica o cautare orizontala si una verticala. Marimea pasului s este initializata la si sunt cercetate blocul din centrul de cautare si alte doua blocuri candidate situate pe fiecare latura a acestuia la distanta s. Cea mai buna din aceste locatii devine centrul de la urmatoarea cautare. Daca marimea pasului s este 1, algoritmul se termina si returneaza cel mai bun bloc gasit la pasul curent. Altfel, s este redus la jumatate, si se executa un alt set de cautari pe orizontala si verticala.

Cautarea la un anumit timp. Si in acest tip de cautare exista doi pasi, unul orizontal si unul vertical. Pasul orizontal cauta toate blocurile in aria de cautare ale caror coordonate y sunt egale cu acelea din blocul B (care sunt pozitionate pe aceeasi axa orizontala ca B). Presupunand ca dintre acestea blocul H are distorsiunea minima, pasul vertical cauta toate blocurile de pe aceeasi axa verticala ca si H si o returneaza pe cea mai buna dintre ele. Procedeul se repeta pe arii de cautare din ce in ce mai mici.

Metode de cautare ierarhice. Metodele ierarhice folosesc avantajul faptului ca potrivirea blocului este sensibila la marimea blocului. O metoda de cautare ierarhica incepe cu blocurile mari si utilizeaza vectorii lor de miscare ca puncte de inceput pentru mai multe cautari cu blocuri mai mici. Blocurile mari sunt mai putin potrivite in determinarea maximelor locale, in timp ce un bloc mic, in general, produce un vector de miscare mai bun. Metoda de cautare ierarhica presupune un mare efort computational si se urmareste cresterea vitezei prin reducerea numarului de operatii. Aceasta metoda se poate realiza in mai multe moduri, dupa cum urmeaza:

In pasii initiali, cand blocurile sunt inca mari, se cauta numai intr-un esantion de blocuri. Vectorii de miscare rezultati nu sunt cei mai buni, dar ei vor fi utilizati ca puncte de inceput pentru altii mai buni.

Cand are loc cautarea in blocuri mari, se sare peste cativa din pixelii blocului. Algoritmul poate, de exemplu, sa utilizeze un sfert din pixelii blocurilor mari, o jumatate din pixelii blocurilor mai mici, si asa mai departe.

Marimile blocului se selecteaza astfel incat blocul utilizat in pasul i sa poata fi divizat intr-un numar de blocuri (obisnuit, patru sau noua) folosite in pasul urmator. In acest mod un singur vector de miscare calculat la pasul i poate fi folosit ca estimat pentru mai multi vectori de miscare mai buni la pasul i+1.

1.5. Metode multidimensionale de cautare a spatiului

Aceste metode sunt mult mai complexe decat cele prezentate anterior. Cautand o potrivire pentru blocul B, o astfel de metoda cauta potrivirile care sunt rotite sau marite, nu numai translate.

O metoda multidimensionala de cautare a spatului poate, de asemenea, gasi un bloc asemanator cu B dar in conditii de iluminare diferite. Acest lucru este utilizat cand un obiect se misca in regiuni care sunt iluminate diferit. Toate metodele prezentate pana acum compara doua blocuri prin compararea valorilor de luminanta a pixelilor corespunzatori. Doua blocuri B si C care contin aceleasi obiecte, dar difera in luminanta, ar putea fi declarate diferite prin astfel de metode.

Cand metoda multidimensionala de cautare a spatiului gaseste blocul C care se aseamana cu B dar are luminanta diferita, se poate declara ca C se potriveste cu B si adauga valoarea luminantei la cadrul compresat B. Aceasta valoare este adaugata de decodor pixelilor cadrului de decompresat, pentru producerea blocului cu valorile originale.

O metoda multidimensionala de cautare a spatului poate, de asemenea, compara un bloc B cu o versiune rotita a blocurilor candidate C. Acest lucru este util daca obiectele din prezentarea video pot fi rotite in plus fata de miscarea existenta. Algoritmul poate, de asemenea, incerca sa potriveasca blocul B cu blocul C care contine o versiune scalata a obiectelor din B. Daca, de exemplu, B are dimensiunea pixeli, algoritmul poate considera blocurile C de marime , micsorand pe fiecare la si comparandu-le pe acestea cu B.

Acest tip de cautare de bloc implica multe operatii si comparatii suplimentare. Marimea spatului de cautare creste semnificativ, de unde si numele de cautare multidimensionala. Acest lucru da impresia ca in prezent nu exista o metoda de cautare multidimensionala care sa ia in considerare scalarea, rotirea si schimbarea iluminarii si care sa fie suficient de rapida pentru utilizarea practica.