Descomposición en Valores Singulares: Compresión de Imágenes

(Este artículo es de carácter muy técnico. Puedes saltarte la primera parte e ir directamente más abajo, donde se ilustra la aplicación de la descomposición en valores singulares a la aproximación de imágenes.)

El análisis de componentes principales (PCA) (Principal Component Analysis) se basa en aproximar una matriz por la suma de una cierta colección (pequeña) de matrices de rango uno. En concreto, si

A=U\Sigma V^{T}

es una descomposición en valores singulares normalizada de una matriz A de orden m\times n y rango r, se verifica que

A=U\Sigma V^{T}=\sigma _{1}u_{1}v_{1}^{T}+\sigma _{2}u_{2}v_{2}^{T}+\cdots +\sigma_{r}u_{r}v_{r}^{T},

donde \sigma_1\geq \sigma_2\geq\cdots\geq\sigma_r>0 son los elementos de la diagonal de \Sigma (es decir, los valores singulares de A) y u_{i}, v_{j} denotan las columnas de U y V, respectivamente.

Si escribimos E_k:=\sigma _{k}u_{k}v_{k}^{T}, se puede comprobar que E_k es de rango uno, con \|E_k\|_2=\sigma_k. Por tanto, si tomamos p<r de modo que \sigma_p>>\sigma_j, para j=p+1,...,r, es natural asumir que la matriz

A_p:=E_1+E_2+\cdots+E_p

recoge (condensa) en cierto sentido toda la información relevante de la matriz A.

El análisis de componentes principales se usa en una enorme variedad de campos científicos, tales como la Geología, la Estadística, la Arqueología,… En el tratamiento digital de imágenes, el (PCA) es especialmente apreciado en el reconocimiento de patrones. A pesar de su evidente aplicación a la compresión de imágenes, ésta suele realizarse con otras técnicas computacionales, como la teoría de wavelets.

Si tenemos, por ejemplo, una imagen en escala de grises (por tanto con un único canal de color) de tamaño m \times n píxeles, consideremos la matriz del mismo tamaño m \times n que resulta de asignar un valor numérico a cada valor de gris de la imagen. Sea una descomposición en valores singulares de esta matriz

A=USV^T=\displaystyle\sum_{k=1}^{r}\sigma _{k}u_{k}v_{k}^{t}.

Cada matriz de rango uno E_{k} contiene información sobre los píxeles de la imagen y cada valor singular \sigma _{k} mide la importancia de esa información desde el punto de vista de la resolución.

En general, suele haber un valor p<<r de modo que toda la información crucial está en las p primeras matrices E_{k}. Por tanto,

\displaystyle\sum_{k=1}^{p}\sigma_{k}u_{k}v_{k}^{t}

suele ser una aproximación gráfica bastante buena de la imagen asociada a A.

Vamos a ilustrar los comentarios anteriores obteniendo aproximaciones de rango creciente (y por tanto sucesivamente mejores aproximaciones) de la siguiente imagen de muestra, de tamaño 500 x 350 píxeles. La matriz que representa la imagen tiene rango máximo, es decir, 350.  Podemos, pues, aproximar tomando el valor de p desde 1 hasta 350.

bh_12_03
Imagen original.

 

svd_1
Imagen aproximada con p=1. Es la peor de las aproximaciones y, de hecho, debido al rango uno de la matriz que representa a la imagen, ésta no es más que un patrón abstracto de líneas horizontales y verticales.

 

svd_5
Imagen aproximada con p=5. Comienza a aparecer el barco, aunque aún está muy difuso.

 

svd_10
Imagen aproximada con p=10. El barco se hace más visible.

 

svd_20
Imagen aproximada con p=20. Nos acercamos más a la imagen original, aunque aún estamos lejos.

 

svd_60
Imagen aproximada con p=60. El barco aparece con mucha mayor claridad.

 

svd_100
Imagen aproximada con p=100. Ésta es ya una aproximación razonablemente aceptable.

 

svd_150
Imagen aproximada con p=150. Buena aproximación.

 

svd_200
Imagen aproximada con p=200. Aproximación apenas distinguible de la original.

 

svd_350
Imagen aproximada con p=350. Ésta es la aproximación de máximo rango, r=350, y por tanto coincide totalmente con la original.

Leave a Reply