Quantização de Imagens Usando Decomposição em Valores Singulares

A compressão sem perdas consiste em reduzir o tamanho de um dado através da codificação da informação com símbolos menores, que ocupam menos espaço. Este tipo de compressão sempre será limitada à entropia da fonte original. Contudo, para algumas aplicações pode ser necessário comprimir a informação para taxas menores que a entropia. Para conseguir essas taxas de compressão, devemos eliminar informação da fonte e codificá-la considerando essas perdas. Este processo de descarte requer que o número de palavras-código da fonte sejam limitados, fazendo com que a quantidade de possíveis saídas da fonte seja maior do que a quantidade de palavras-códigos do objeto comprimido. Sendo assim, as técnicas de limitar a quantidade de palavras-códigos são denominadas técnicas de quantização.

No contexto do processamento de imagens, a quantização é geralmente feita reduzindo-se a quantidade de níveis de cor (quantização espacial) ou reduzindo-se a quantidade de coeficientes no domínio da frequência (quantização do espaço transformado de Fourier, wavelets, etc). Por exemplo, no padrão JPEG, a quantização é feita sobre os coeficientes da transformada discreta de cosseno, eliminando-se aqueles menos significativos. Nest post, mostramos exemplos de quantização no espaço transformado pela decomposição SVD.

Nas imagens abaixo, decompomos uma imagem $I$ em três matrizes $U$, $S$ e $V$. Tal decomposição distribui os coeficientes mais significantes da informação ao longo do vetor $S$, de forma ordenada e decrescente em importância. Com esta decomposição reconstruímos a imagem $I = U \times S \times V^T$ utilizando apenas uma fração dos coeficientes. A listagem mostra a imagem original (primeira) quantizada com 5, 20, 35, 50 e 65% dos coeficientes decompostos da imagem original. Sem seguida, as imagens são codificadas em JPEG, sendo novamente quantizadas, conforme especificações desse padrão.

</p> <tr valign="top""> </tr>

Original	Reconstruída com 5% dos coeficientes SVD	Reconstruída com 20% dos coeficientes SVD
Reconstruída com 35% dos coeficientes SVD	Reconstruída com 50% dos coeficientes SVD	Reconstruída com 65% dos coeficientes SVD

</center>

Visualmente, podemos notar que a qualidade da imagem melhora, conforme mais valores singulares são selecionados na reconstrução. Contudo, considerando que a codificação JPEG realiza uma segunda quantização, os resultados visuais são satisfatórios.

Para analisar objetivamente a influencia da quantização SVD sobre as imagens, codificamos o conjunto de imagens abaixo com as componentes SVD, aproveitando 50% dos coeficientes e descartando os outros 50. Com o resultado dessa quantização calculamos o PSNR e a taxa de compressão obtida.

As imagens são:

</p>

Original	SVD-Quantizada
Original	SVD-Quantizada
Original	SVD-Quantizada

</center>

Os resultados objetivos são:

</p>

Imagem	PSNR	Tamanho do Arquivo Sem SVD (bytes)	Tamanho do Arquivo com SVD (bytes)	Taxa de Compressão
peppers	23.51	73441	36443	2.01
lena	28.79	65294	34995	1.86
cameraman	33.92	19545	10914	1.79
rose	38.99	169752	64131	2.64

</center>

Segue abaixo o código para quantização usando SVD.

import numpy
from numpy import array
from numpy import linalg
from scipy.misc.pilutil import imsave, imread, imresize


def svd_encode(im, number_of_coefficients=50.0):
    img = im.astype('double')
    [rows, cols] = img.shape
    mindim = min(rows, cols)
    total = int(numpy.floor(number_of_coefficients * mindim / 100.0))
    [u, s, v] = linalg.svd(img)
    v = v.T
    compressed = numpy.zeros((rows, cols))
    for j in xrange(total):
        l = s[j] * numpy.matrix(u[:, j]).T
        vm = numpy.matrix(v[:, j])
        r = numpy.dot(l, vm)
        compressed = compressed + r
    compressed = numpy.floor(compressed)
    return compressed


# Testing
if __name__ == '__main__':
    imgs = ['peppers', 'lena', 'cameraman', 'rose']
    f = imread(imgs[0] + ".jpg", flatten=True)
    for i in xrange(5, 75, 15):
        f1 = svd_encode(f, float(i))
        imsave(imgs[0] + str(i) + ".jpg", f1)
    for im in imgs:
        print im + ".jpg"
        f = imread(im + ".jpg", flatten=True)
        g = svd_encode(f, 50)
        imsave(im + "_svd.jpg", g)

O código completo e a comparação das imagens pode ser obtido no endereço: http://www.sawp.com.br/code/ip/post68_svd_processing_image.tar.gz.