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.

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

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:

Original

SVD-Quantizada

Original

SVD-Quantizada

Original

SVD-Quantizada

Os resultados objetivos são:

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

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.