DCT - mono-dimensionala

Transformata cosinus discreta pentru o lista de n numere reale (esantioanele semnalului), s(i), i=0,1, . , n-1 este o alta lista de numere de lungime n, calculate prin relatiile

, k = 0,1, . , n (1)

unde 

(2)

Fiecare element al listei transformate S(k) este produsul scalar intre lista de intrare s(i) si un vector de baza. Factorul constant este ales astfel incat vectorii baza sa fie ortogonali si normalizati. Cei opt vectori baza pentru n=8 sunt prezentati in figura 1.

Figura 1 - Vectorii de baza ai transformatei cosinus, n=8

In scriere matriciala, transformarea este

unde

unde

Fiecare vector de baza, a_k, (coloanele matricii A) corespunde unei sinusoide de o anumita frecventa, asa cum se poate observa in figura 1. Lista initiala poate fi refacuta din S, prin aplicarea transformatei cosinus discrete inverse (IDCT), dupa relatiile:

, i= 0, . ., n-1

unde

Ecuatia exprima pe s ca o combinatie liniara a vectorilor baza. Coeficientii sunt elementele transformarii S, care pot fi priviti ca reflectand cantitatea din fiecare frecventa prezenta in intrarea s.   Transformata mono-dimensionala DCT este utila in procesarea semnalelor, cum ar fi vorbirea.

Transformata DCT bi-dimensionala

Transformata bi-dimensionala DCT este utila la compresia imaginilor. Pentru o matrice s de dimensiune nxn, DCT 2D se calculeaza simplu: DCT 1D se aplica pentru fiecare linie a lui s apoi fiecarei coloane a rezultatului. Relatiile de calcul sunt

,

,

In notatie matriciala:

DCT 2D poate fi calculata prin aplicarea transforamarilor 1D separate pe linii si coloane, si se spune ca DCT 2D este separabila in doua dimensiuni.

Refacerea informatiei originale inseamna

Ca si in cazul uni-dimensional, fiecare element S(u,v) al transformarii este produsul intern intre intrare si functia baza, unde - in acest caz - functiile de baza sunt matrici de dimensiune nxn. Fiecare matrice de baza este produsul a doi vectori de baza. Fiecare matrice de baza poate fi considerata ca o imagine. In figura 2 se prezinta cele 64 de matrici de baza. (Se recomanda scalarea matricilor de baza pentru folosirea intregului domeniu de variatie al nivelului de gri [0 255] pentru [min max], la reprezentarea pe 8 biti a valorii unui pixel).

Figura 2 - Matricele de baza ai transformatei cosinus bidimensionale, n=8

Fiecare matrice de baza este caracterizata de o frecventa spatiala, orizontala si verticala. Matricile din figura sunt aranjate de la stanga la dreapta si de sus in jos in ordinea crescatoare a frecventelor.

Fiecare pixel din imaginea DCT descrie ponderea fiecarei matrici de baza in semnalul (imagine) de la intrare. Pixelii sunt aranjati, in ordinea crescatoare a frecentelor de la stanga la dreapta si de sus in jos. Cel mai stralucitor pixel din coltul din dreapta sus este cunoscut ca termenul de current continuu, sau componenta medie, cu frecventa . El este media pixelilor de la intarre, si este - tipic - cel mai mare coefficient in DCT al imaginilor naturale.

Compresia cu DCT

Compresia bazata pe DCT se bazeaza pe doua tehnici in reducerea darelor pentru reprezentarea unei imagini. Prima este cuantizarea coeficientilor transformarii; a doua este codarea entropica a coeficientilor cuantizati.

O cuantizare fina, ce permite considerarea mai multor valori si pierderi mai mici de informatie, foloseste coeficienti de normare: Numarul de cuantizat este impartit la factorul de ponderare, inainte de rotunjire, adica inainte de cuantificarea propriu-zisa. Decuantizarea inseamna inmultirea valorii cuantizate cu ponderea folosita la cuantizare.

In standardul de compresie JPEG, fiecare DCT coefficient este cuantizat utilizand o pondere ce depinde de frecventa coeficientului considerat. Coeficientii pentru fiecare bloc de 8x8 sunt impartiti la o matrice de cuantizare de 8x8, si rezultatul este rotunjit la cel mai aproape intreg.

In general, frecventele spatiale de ordin mare sunt mai putin vizibile ochiului uman in comparatie cu frecventele joase. Astfel, factorii de cunatizare sunt alesi ca fiind mai mari pentru frecvente mari. Urmatoarea matrice de cuantizare este folosita intens pentru imaginile moco-crome si pentru componenta de luminanta a imaginiii color. Ea se folosteste in compresia JPEG.

Vizualizand matricea pe o scara a nivelelor de gri se vede dependenta factorilor de cuantizare de frecventa.

 

La efectuarea compresiei, se transforma matricea in blocuri si se cuantizeaza fiecare bloc. La de-compresie se inmulteste fiecare bloc cu matricea de cuantizare si se obtine imaginea reconstruita.

Exemplu: Se considera problema compresiei unei imagini, ce reprezinta litera A, ca in figura 3. In partea dreapta a figurii 3, se prezinta coeficientii DCT pe o scara de gri de la 0 la 255, cu scalarea corespunzatoare a matricii S.

Figura 3 - Litera A (8x8 pixel) si coeficientii DCT

In figura 4, se prezinta litera A reconstituita folosind numai o parte din coeficienti, si anume pentru n = 5, 6, 7, si 8. Selectarea numarului de coeficienti se bazeaza pe faptul ca cele mai mari valori se gasesc in jurul frecventelor joase (cel putin pentru imagini naturale).

In figura 5 se prezinta un criteriu de selectie bazat pe selectia coeficientilor dupa valorile acestora. Se observa ca se obtine un raport de compresie destul de mare, in jur de 20. De altfel, 90 % din coeficientii transformarii au valori foarte mici.

Programele folosite la generarea figurilor acetui document sunt prezentate in Anexa, la sfarsitul documentului.

Figura 4 - Litera A, pentru n = 5,6,7 si 8 coeficienti

Figura 5 - Compresia unei imagini prin DCT; raportul de compresie este 20

Referinte

Andrew B. Watson, Image Compression Using the Discrete Cosine Transform, Mathematica Journal, 4(1), 1994, p. 81-88

Anexa 1 - Codul sursa Matlab pentru acest capitol

% functie DCT monodimensionala;

% numele = f_dct_1D

clc; clear; clf;

n=8;

fs=1000;

ts=1/fs;

t = (0:n-1)*ts;

f1 = 100;

f2 = 0;

s = sin(6.28 * t * f1) + cos(6.28 * t * f2);

for k=1:n,

sum = 0;

for i=1:n,

sum = sum + s(i) * cos(( 2*i-1)* (k-1) * 3.14 / 2 / n);

end;

if k==1, C(k)= 1/sqrt(2); else C(k) = 1; end;

S(k) = sqrt(2/n)*C(k)* sum;

end;

st=s'; % vector coloana;

% calculul matricii transformarii:

for i=1:n,  % indicele de linie

for k=1:n,

if k==1, C(k)= 1/sqrt(2); else C(k) = 1; end;

A(k,i) = sqrt(2/n)* C(k) * cos(( 2*i-1)* (k-1) * 3.14 / 2 / n);

end;

end; 

St = A * st;

%coloanele matricii A definesc vectorii baza;

% reprezentarea vectorilor baza

if(1),

for i=1:8,

subplot(4,2,i), plot([0:n-1], A(:,i));

ylabel(strcat('i=', num2str(i)));

end;

end;

pause;

% se reface semnalul initial cu mai putini coeficienti:

nr = 20;

Sr = [St(1:nr)' zeros(1,n-nr)]';

sr = inv(A)* Sr;

subplot(311), plot(t,st);

subplot(312), plot(t,sr);

subplot(313), plot(t, (st-sr).^2);

crt = sumsqr(st-sr)/n

= = = = = = = = = = = = ==

% functie DCT bi-dimensionala;

% numele = f_dct_2D

% 0 = black; 255 = white;

clc; clear; clf;

n=8;

s = ones(n,n);

s = [0 0 0 1 1 0 0 0;

0 0 1 0 0 1 0 0;

0 0 1 0 0 1 0 0;

0 0 1 0 0 1 0 0;

0 1 1 0 0 1 1 0;

0 1 1 1 1 1 1 0;

1 0 0 0 0 0 0 1;

1 0 0 0 0 0 0 1];

s=~s;

s = s * 255;

% calculul matricii transformarii:

for i=1:n, 

for k=1:n,

if k==1, C(k)= 1/sqrt(2); else C(k) = 1; end;

A(k,i) = sqrt(2/n)* C(k)*cos((2*i-1)* (k-1) * 3.14 / 2 / n);

end;

end; 

Am=dctmtx(8);  % matricea transformarii data de Matlab;

S = A * s * A';

sr = A' * S * A;;

%coloanele matricii A definesc vectorii baza;

% reprezentarea vectorilor baza

subplot(221), imshow(s, [0 255]);

subplot(222), imshow(S, [0 255]);

pause;

clf;

%compress..

for nc= [5 6 7 8];

Sc=zeros(n,n);

for i=1:nc,

for j=1:nc,

Sc(i,j) = S(i,j);

end;

end;

src = A' * Sc * A;

subplot(2,2, nc-4), imshow(src,[0 255]);

end;

if (0),

% se calculeaza matricele de baza

% se definesc vectorii de baza din liniile matricii A:

BM = []; % BM = basis matrix;

for i=1:n,

a = A(i,:);

for j=1:n,

b = A(j,:);

x = a' * b

BM = [BM x];

subplot(8,8,(i-1)*8 +j), imshow(x, [min(min(x)) max(max(x))]);

pause;

end;

end;

end;

= = = = = = = = = = = = =

clc; clear; clf;

im = 'cameraman.tif';

subplot(221), imshow(im); ylabel('size = 65240 Bytes');

I = imread(im);

J = dct2(I);

subplot(222), plot(log(abs(J))); title('log(abs(DCT))');

J1=J; J2=J;

J1(abs(J) < 200) = 0; K1 = idct2(J1);

subplot(223), imshow(K1,[0 255]); title('abs(S) < 200 -> 63342 / 65536');

ylabel('size = 2716 Bytes');

J2(abs(J) < 80) = 0; K2 = idct2(J2);

subplot(224), imshow(K2,[0 255]);title('abs(S) < 80 - > 64669 / 65536');

IMWRITE(K1,'cameraman_c1.tif','tif');

IMWRITE(K1,'cameraman_c2.tif','tif');

n1=0; n2 = 0;

for i=1:256,

for j=1:256,

if J(i,j) < 200, n1 = n1+1; end;

if J(i,j) < 80, n2 = n2+1; end;

end;

end;

= = = = = = = = = = = = = ==