Descomposició SVD: Aplicació a la Compressió d'Imatges

Donada una matriu mxn, la descomposició SVD (Singular Value Decomposition) dona un canvi de base en el qual la matriu original diagonalitza. Les bases del canvi son ortonormals i els valors de la diagonal (valors singulars) donen informació sobre la matriu original.
En molt casos s'utilitza la SVD en el contexte de resoldre sistemes d'equacions lineals de la forma Ax=b

SVD dins Matlab

La funció de Matlab que permet obtenir la descomposició SVD és svd
A=ones(3,4)+10*eye(3,4) %fem una matriu NO quadrada per poder veure les diferents dimensions
A = 3×4
11 1 1 1 1 11 1 1 1 1 11 1
[U,D,V]=svd(A)
U = 3×3
5.7735e-01 0 8.1650e-01 5.7735e-01 7.0711e-01 -4.0825e-01 5.7735e-01 -7.0711e-01 -4.0825e-01
D = 3×4
1.3115e+01 0 0 0 0 1.0000e+01 0 0 0 0 1.0000e+01 0
V = 4×4
5.7229e-01 5.3578e-17 8.1650e-01 -7.6249e-02 5.7229e-01 7.0711e-01 -4.0825e-01 -7.6249e-02 5.7229e-01 -7.0711e-01 -4.0825e-01 -7.6249e-02 1.3207e-01 -1.0271e-17 4.8266e-17 9.9124e-01
A-U*D*V' %noteu que la matriu V s'ha de trasposar (és la inversa!) per fer el canvi de base.
ans = 3×4
0 0 -4.4409e-16 0 -2.6645e-15 5.3291e-15 8.8818e-16 0 -3.1086e-15 1.1102e-15 1.7764e-15 2.2204e-16
S=diag(D) %Valors singulars
S = 3×1
1.3115e+01 1.0000e+01 1.0000e+01
Veiem que les matrius U i V son ortogonals
U*U' %el producte entre si de tots els vectors U
ans = 3×3
1.0000e+00 -4.0287e-17 -5.1491e-18 -4.0287e-17 1.0000e+00 -9.8261e-17 -5.1491e-18 -9.8261e-17 1.0000e+00
V*V' %el producte entre si de tots els vectors U
ans = 4×4
1.0000e+00 2.0123e-16 1.3618e-16 4.1633e-17 2.0123e-16 1.0000e+00 -1.6653e-16 -4.1633e-17 1.3618e-16 -1.6653e-16 1.0000e+00 -1.3878e-17 4.1633e-17 -4.1633e-17 -1.3878e-17 1.0000e+00
El rang de la matriu és el nombre de valors singulars diferent de zero
ind=find(S > 0); %només cal els > 0, ja que tots els valors singulars son positius
rang=length(ind); %la longitud del vector dona el número total
% comparem amb la funció de Matlab que dona el rang d'una matriu (rank(A))
[rang, rang-rank(A)] %mostrem el valor i la comprovació
ans = 1×2
3 0

Aproximació successiva d'una matriu:

La descomposició SVD permet aproximar una matriu de forma successiva de manera que l'error comès és de l'ordre del primer valor singular no utilitzat
A1=A-S(1)*U(:,1)*V(:,1)' %aproximaxió amb el primer valor singular
A1 = 3×4
6.6667e+00 -3.3333e+00 -3.3333e+00 3.3307e-16 -3.3333e+00 6.6667e+00 -3.3333e+00 -2.2204e-16 -3.3333e+00 -3.3333e+00 6.6667e+00 0
A2=A-(S(1)*U(:,1)*V(:,1)'+S(2)*U(:,2)*V(:,2)') %primer i segon
A2 = 3×4
6.6667e+00 -3.3333e+00 -3.3333e+00 3.3307e-16 -3.3333e+00 1.6667e+00 1.6667e+00 -2.2204e-16 -3.3333e+00 1.6667e+00 1.6667e+00 0
A3=A-(S(1)*U(:,1)*V(:,1)'+S(2)*U(:,2)*V(:,2)'+S(3)*U(:,3)*V(:,3)') %tots
A3 = 3×4
0 0 -4.4409e-16 0 -2.6645e-15 5.3291e-15 8.8818e-16 0 -3.1086e-15 1.1102e-15 1.7764e-15 2.2204e-16
[norm(A1),norm(A2),norm(A3)]
ans = 1×3
1.0000e+01 1.0000e+01 6.6703e-15

Aplicació: Compressió d'imatges

Si considerem que una imatge és una matriu numèrica, la descomposició SVD es pot utilitzar per aproximar aquesta imatge utilitzant només uns poca valors singulars de la imatge, aconseguint així una reducció en els valors que cal guardar per aproximar una imatge (compressió)
A = imread('mandrill.jpg'); %carreguem una imatge en Matlab
Agray = rgb2gray(A); %si la imatge és RGB, passem la imatge a escala de grisos
Agray = im2double(Agray);
imshow(Agray); %mostrem la imatge ja en escala de grisos (valors dins [0,1])
tini=cputime; %iniciem un comptador per mesurar el temps de càlcul
figure('units','normalized','outerposition',[0 0 1 1]) %fem la propera figura full screen
% Calculem la descomposició SVD de la imatge
[U,D,V] = svd(Agray);
S=diag(D);
mostremFinsValSing=[1 2 5 10 25 50 100 298];
numImg =length(mostremFinsValSing); %número d'imatges que mostrarem
for k=1:numImg %fem aproximacions agafant fins a aquests valors
B=zeros(size(Agray));
for i=1:mostremFinsValSing(k) %aproximem fins el valor singular corresponent
B=B+S(i)*U(:,i)*V(:,i)';
end
% presentem les imatges utilitzant una figura múltiple (subplot)
subplot(2,4,k) %fem 2x4=8 imatges (el total ha de ser >= que numImg!!)
imshow(B);
title(['nVS= ',num2str(mostremFinsValSing(k))]);
end
tempsTotal=cputime-tini
tempsTotal =
3

Exercici: Memòria total

Si per cada pixel es guarda un valor que ocupa 64bits (en escala de grisos i valors double). Calculeu per la imatge de baboon quants bits necessitem per guardar la imatge original i quants si ens guardem només fins el valor singular numéro 100.
Sol: Imatge Original= 16777216, Imatge fins ValSingular_100= 6560000
(c)Numerical Factory 2020