Comprimarea video: Ce este transformarea discretă a cosinusului?

Am implementat o tehnică de transformare imagine / video numită transformare discretă a cosinusului. Această tehnică este utilizată în codarea video MPEG. Am bazat algoritmul meu pe ideile prezentate la următoarea adresă URL:

http://vsr.informatik.tu-chemnitz.de/~jan/MPEG/HTML/mpeg_tech.html

Acum pot transforma o secțiune de 8x8 dintr-o imagine alb-negru, cum ar fi:

0140  0124  0124  0132  0130  0139  0102  0088  
0140  0123  0126  0132  0134  0134  0088  0117  
0143  0126  0126  0133  0134  0138  0081  0082  
0148  0126  0128  0136  0137  0134  0079  0130  
0147  0128  0126  0137  0138  0145  0132  0144  
0147  0131  0123  0138  0137  0140  0145  0137  
0142  0135  0122  0137  0140  0138  0143  0112  
0140  0138  0125  0137  0140  0140  0148  0143 

Într-o imagine cu toate informațiile importante din partea dreaptă sus. Blocul transformat arată astfel:

1041  0039  -023  0044  0027  0000  0021  -019  
-050  0044  -029  0000  0009  -014  0032  -010  
0000  0000  0000  0000  -018  0010  -017  0000  
0014  -019  0010  0000  0000  0016  -012  0000  
0010  -010  0000  0000  0000  0000  0000  0000  
-016  0021  -014  0010  0000  0000  0000  0000  
0000  0000  0000  0000  0000  0000  0000  0000  
0000  0000  -010  0013  -014  0010  0000  0000  

Acum, trebuie să știu cum pot profita de această transformare? Aș dori să detectez alte blocuri de 8x8 în aceeași imagine (sau altă imagine) care reprezintă o potrivire bună.

De asemenea, ce îmi dă această transformare? De ce sunt importante informațiile stocate în partea din dreapta sus a imaginii convertite?

0
fr hi bn

6 răspunsuri

Rezultatul unui DCT este o transformare a sursei originale în domeniul frecvenței. Intrarea din stânga sus stochează "amplitudinea" frecvența "de bază" și frecvența crește atât de-a lungul axelor orizontale și verticale. Rezultatul DCT este de obicei o colecție de amplitudini la frecvențele mai joase mai obișnuite (cvadrantul din stânga sus) și mai puține intrări la frecvențele mai mari. După cum a menționat lassevk, este obișnuit să se elimine doar aceste frecvențe mai mari, deoarece în mod obișnuit constituie părți foarte mici ale sursei. Cu toate acestea, acest lucru duce la pierderea informațiilor. Pentru a finaliza comprimarea este obișnuită utilizarea unei comprimări fără pierderi peste sursa DCT'd. Aici intră compresia, pe măsură ce toate nivelele de zerouri se împachetează până aproape de nimic.

Un avantaj posibil al utilizării DCT pentru a găsi regiuni similare este acela că puteți face o primă trecere la valori de joasă frecvență (colțul din stânga sus). Acest lucru reduce numărul de valori pe care trebuie să le potriviți. Dacă găsiți potriviri cu valori de frecvență joasă, puteți crește la compararea frecvențelor mai mari.

Sper că acest lucru vă ajută

0
adăugat

Dacă îmi amintesc corect, această matrice vă permite să salvați datele într-un fișier cu compresie.

Dacă citiți mai jos, veți găsi modelul zig-zag de date pentru a citi din matricea finală. Datele cele mai importante sunt în colțul din stânga sus și cel mai puțin important în colțul din dreapta jos. Ca atare, dacă opriți scrierea la un moment dat și considerați restul ca 0, chiar dacă nu sunt, veți obține o aproximare a pierderii imaginii.

Numărul de valori pe care le aruncați scade comprimarea la costul fidelității imaginii.

Dar sunt sigur că altcineva îți poate da o explicație mai bună.

0
adăugat

Răspunsul lui Anthony Cramp mi-a arătat bine. Pe măsură ce menționează că DCT transformă datele în domeniul de frecvență. DCT este puternic utilizat în compresia video, deoarece sistemul vizual vizual este mai puțin sensibil la schimbările de frecvență înaltă, prin urmare, reducerea valorilor frecvenței superioare duce la obținerea unui fișier mai mic, cu un efect redus asupra percepției umane asupra calității video.

În ceea ce privește utilizarea DCT pentru a compara imaginile, cred că singurul beneficiu real este dacă eliminați datele de frecvență mai ridicate și, prin urmare, aveți un set mai mic de date pentru căutare / potrivire. Ceva ca wavelet-urile Harr pot da rezultate mai bune pentru potrivirea imaginilor.

0
adăugat

Am învățat tot ce știu despre DCT din Cartea de comprimare a datelor . Pe lângă faptul că este o introducere excelentă în domeniul comprimării datelor, acesta are un capitol aproape de capăt pe compresia imaginilor pierdute, care introduce JPEG și DCT.

0
adăugat

Aș recomanda iau o copie a de compresie video digitală - este o foarte bună imagine de ansamblu a algoritmilor de compresie pentru imagini și video.

0
adăugat

Conceptele care stau la baza acestor tipuri de transformări sunt mai ușor de văzut prin analizarea mai întâi a unui caz unidimensional. Imaginea aici arată o undă pătrată împreună cu câțiva dintre primii termeni ai o serie infinită. Privind la aceasta, rețineți că dacă funcțiile pentru termeni sunt adăugate împreună, ele încep să aproximeze forma valului pătrat. Cu cât adăugați mai mulți termeni, cu atât este mai bine aproximarea. Dar, pentru a obține de la o aproximare la semnalul exact, trebuie să însumați un număr infinit de termeni. Motivul pentru aceasta este că valul pătrat este discontinuu. Dacă vă gândiți la un val pătrat în funcție de timp, acesta merge de la -1 la 1 în timp zero. Pentru a reprezenta un astfel de lucru este nevoie de o serie infinită. Aruncă o privire mai departe la complotul termenilor seriei. Primul este roșu, cel de-al doilea galben. Termenii succesivi au mai multe tranziții "în sus și în jos". Acestea provin din frecvența crescândă a fiecărui termen. Lipirea cu valul pătrat în funcție de timp și fiecare termen de serie funcție de frecvență există două reprezentări echivalente: o funcție de timp și o funcție de frecvență (1 / timp).

În lumea reală, nu există valuri pătrate. Nimic nu se întâmplă în momentul zero. Semnalele audio, de exemplu, ocupă domeniul 20Hz până la 20KHz, unde Hz este 1 / o dată. Astfel de lucruri pot fi reprezentate cu serii finite ".

Pentru imagini, matematica este aceeași, dar două lucruri sunt diferite. În primul rând, este de două dimensiuni. În al doilea rând, noțiunea de timp nu are sens. În sensul 1D, valul pătrat este doar o funcție care oferă o valoare numerică pentru un argument pe care am spus că a fost timpul. O imagine (statică) este o funcție care oferă o valoare numerică pentru fiecare pereche de indici de rând, de coloană. Cu alte cuvinte, imaginea este o funcție a unui spațiu 2D, care este o regiune dreptunghiulară. O funcție asemănătoare poate fi reprezentată în funcție de frecvența sa spațială. Pentru a înțelege ce este frecvența spațială, ia în considerare o imagine de nivel de 8 biți și o pereche de pixeli adiacenți. Tranziția cea mai abruptă care poate apărea în imagine este trecerea de la 0 (să zicem negru) la 255 (să zicem alb) peste distanța de 1 pixel. Aceasta corespunde direct cu cea mai mare frecvență (ultimul) termen de reprezentare a seriei.

O transformare Fourier (sau Cosine) bidimensională a imaginii are ca rezultat o serie de valori de aceeași dimensiune ca imaginea, reprezentând aceeași informație nu ca o funcție a spațiului, ci o funcție de 1 / spațiu. Informația este ordonată de la cea mai joasă la cea mai înaltă frecvență de-a lungul diagonalei de la rândul de început cel mai înalt și de la indicele coloanei. Un exemplu este aici .

Pentru compresia imaginilor, poți transforma o imagine, poți renunța la un anumit număr de termeni de frecvență mai înaltă și transformă invers restul celor din urmă înapoi la o imagine, care are mai puține detalii decât originalul. Deși se transformă într-o imagine de aceeași dimensiune (cu termeni eliminați înlocuiți cu zero), în domeniul frecvențelor, ocupă mai puțin spațiu.

Un alt mod de a privi la aceasta este reducerea unei imagini la o dimensiune mai mică. Dacă, de exemplu, încercați să reduceți dimensiunea unei imagini aruncând trei din patru pixeli la rând și trei din fiecare patru rânduri, veți avea o matrice de 1/4 dimensiune, dar imaginea va arăta groaznică. În cele mai multe cazuri, acest lucru se realizează cu un interpolator 2D, care produce pixeli noi prin media grupurilor rectangulare ale pixelilor imaginii mari. Procedând astfel, interpolarea are un efect similar aruncând termenii seriei în domeniul frecvenței, dar este mult mai rapid de calculat.

Pentru a face mai multe lucruri, mă voi referi la o transformare Fourier ca exemplu. Orice discuție bună a subiectului va ilustra modul în care sunt corelate transformările Fourier și Cosine. Transformarea Fourier a unei imagini nu poate fi privită ca atare, deoarece este făcută din numere complexe. Este deja separat în două tipuri de informații, părți reale și imaginare ale numerelor. De obicei, veți vedea imagini sau parcele din acestea. Dar este mai semnificativ (de obicei) separarea numerelor complexe în magnitudinea lor și în unghiul de fază. Acest lucru este pur și simplu luând un număr complex pe planul complex și trecerea la coordonate polare.

Pentru semnalul audio, gândiți-vă la funcțiile combinate de păcat și cosinus, luând o cantitate attițională în argumentele lor, pentru a transfera funcția înainte și înapoi (ca parte a reprezentării semnalului). Pentru o imagine, informația despre fază descrie modul în care fiecare termen al seriei este schimbat în raport cu ceilalți termeni din spațiul de frecvență. În imagini, marginile (sperăm) sunt atât de distincte încât sunt bine caracterizate de termenii de frecvență mai mici în domeniul frecvențelor. Acest lucru nu se întâmplă deoarece acestea sunt tranziții abrupte, ci pentru că au, de ex. o mulțime de zonă neagră adiacentă la o mulțime de zonă mai ușoară. Luați în considerare o felie unică de margine. Nivelul de gri este zero, apoi trece în sus și rămâne acolo. Vizualizați undă sinusoidală care va fi primul termen de aproximație în care va trece punctul de mijloc al tranziției semnalului la păcat (0). Unghiul de fază al acestui termen corespunde unei deplasări în spațiul imaginii. O mare ilustrație a acestui lucru este disponibilă aici . Dacă încercați să găsiți forme și puteți face o formă de referință, aceasta este o modalitate de a le recunoaște.

0
adăugat