29o Colóquio Brasileiro de Matemática
22 de Julho a 03 de Agosto de 2013
Imagens Digitais e Decomposição SDV
Marcella Feitosa dos Santos
1
∗
Resumo
Uma imagem digital é a representação de uma imagem bidimensional usando números binários codificados de modo
a permitir seu armazenamento, transferência, impressão ou reprodução, e seu processamento por meios eletrônicos.
Existem dois tipos de imagens digitais: uma chamada rastreio (ou raster) e outra chamada vetorial. Uma imagem
do tipo raster, também identificada por matricial, ou bitmap, apresenta uma correspondência bit-a-bit entre os
pontos da imagem e os pontos reproduzidos na tela do monitor. As imagens vetoriais, dependem de equipamentos
de desenhos controlados numericamente, tais imagens são mais utilizadas em programas de engenharia e são geradas
a partir de pontos, retas, polı́gonos simples, curvas, etc.
Os fatores que influenciam na qualidade de uma imagem desse tipo são a quantidade de pixel por polegada
(resolução da imagem), e o número de pixels na horizontal e na vertical. Devido ao grande número de diferentes
tamanhos das telas de celulares, tablets, smartphones, etc, foi necessária a criação de padrões para definir cada
resolução, por exemplo, o padrão VGA (Video Graphics Array) presente em aparelhos que possuem câmeras com
telas de tamanho 5, 4cm × 4cm, possui uma resolução de 640 × 480 pixels.
Comumente uma imagem é decomposta em três cores, e a quantidade corresponde a um número que pode ser
transmitido e recuperado. O sistema RGB (Red-Green-Blue) é um dos mais populares, para cada quantidadde
de cor no pixel são atribuı́dos números referentes a presença do vermelho, verde e azul, feito isso os três valores
são somados e temos o número correspondente a cor no sistema RGB daquele pixel. Nosso trabalho consiste em
analisar a compactação e transmissão das imagens do tipo rastreio. A cada pixel da imagem faremos corresponder
um número, de modo que possamos armazenar a imagem digital em uma matriz, sendo assim, a quantidade de
pixels determina o tamanho da matriz de armazenamento.
Desejamos estabelecer um método eficiente para transmitir imagens digitais. Para simplificar nosso modelo
suponhamos que dispomos de uma imagem em preto e branco, por exemplo, cada pixel corresponde a uma tonalidade
dentre os 256 tons de cinza, assim é possı́vel associar cada um desses tons a um número de 0 à 255. Agora,
imagine que desejamos transmitir uma imagem de 640 × 480 pixels, em preto e branco. Para armazená-la podemos
utilizar uma matriz A 640x480, tal que cada elemento aij de A corresponde ao tom de cinza de cada pixel da
imagem e para transmiti-la devemos enviar 307.200 números, é de se imaginar que tal processo não seria rápido,
nem barato. Então seria muito natural pensar em uma forma de compactar a imagem a fim de transmiti-la sem
perda das informações e sem o alto custo, para resolver tal problema podemos recorrer às operações com matrizes,
particularmente trataremos da Decomposição em Valores Singulares (SDV). A compactação vem da ideia de que
algumas partes da imagem são menos importantes que outras, por exemplo, em uma fotografia de um casal em uma
região montanhosa, haverão muitos pixels parecidos na parte das montanhas, enquanto que há mais detalhes nos
pixels dos rostos, pode-se então evitar a transmissão de alguns pixels de regiões menos importantes, enquanto que
é desejável manter todos os pixels dos rostos.
t
A Decomposição em Valores Singulares (SDV) nos diz que se Am×n então Am×n = Um×m Sm×n Vn×n
, tais que U e
t
t
V são matrizes ortogonais, ou seja, U U e V V são matrizes identidades de tamanhos m×m e n×n, respectivamente,
e S é a matriz “diagonal” m × n, ou seja, cada si,j é zero se i 6= j e s1,1 ≥ s2,2 ≥ ... ≥ sr,r ≥ 0, r = min{m, n}.
Também podemos escrever a decomposição da matriz A como: A = U SV t = s1,1 u1 v1t + s2,2 u2 v2t + ... + sk,k uk vkt ,
em que u1 , u2 , ..., um são as colunas da matriz U e v1 , v2 , ..., vn são as colunas da matriz V .
∗ Graduanda
UFRPE, PE, Brasil, e-mail [email protected]
Sabe-se que toda matriz possui uma decomposição SDV. Mas como isso ajuda a resolver nosso problema? Suporemos o envio de uma imagem em preto e branco de 340 × 280 pixels, então a matriz A associada a essa imagem
conteria 95200 números. Faremos uma aproximação da matriz A por meio de matrizes Ak , k ≤ r (explicitar com
produto externo), de modo que Ak mantém apenas os k primeiros valores singulares e seus correspondentes vetores singulares. Observe que os primeiros valores da matriz S são os que nos interessam, os últimos são números
“pequenos”. É possı́vel observar que em nosso exemplo de 340x280 pixels é suficiente transmitir os valores correspondentes apenas aos 20 primeiros valores singulares da matriz A, juntamente com os 20 vetores u1 , u2 , ..., u2 0 de
R340 e os 20 vetores v1 , v2 , ..., v20 de R280 , totalizando 20 + 20 ∗ 340 + 20 ∗ 280 = 12.420 números, ao invés de 95.200,
perceba aqui quanta economia para transmitir a imagem utilizando o SDV!
Vamos dar uma ideia da prova do teorema que garante que toda matriz A possui uma decomposição SDV. O
principal prerrequisito da prova é o teorema espectral para operadores auto-adjuntos. Seja M = AAt , então M
é uma matriz simétrica associada a um operador auto-adjunto e portanto possui uma base ortonormal de autovetores associados a autovalores positivos cujas raı́zes são os valores singulares da matriz A. Queremos construir
uma matriz S como dissemos acima, a partir dos valores singulares de A. Para construir a matriz V devemos
encontrar uma base ortonormal v1 , v2 , ..., vn de Rn que será formada pelos autovetores da matriz At Anxn , sendo V
uma matriz ortogonal n × n. Para a matriz U devemos observar que {Av1 , Av2 , ..., Avn } é um conjunto ortogonal
de vetores de Rm . Como os valores singulares satisfazem σi = kAvi k, e que o primeiro r desses é não nulo podemos
normalizar Av1 , Av2 , ..., Avr , garantindo que tal conjunto é ortonormal em Rm , se r < m, não teremos uma base,
nesse caso estenderemos o conjunto até que possamos obtê-la. Feitos tais procedimentos basta verificar a igualdade
A = U SV t , que pode ser reescrita como AV = U S, uma vez que V t = V −1 .
Palavras Chave: Decomposição em Valores Singulares, SDV, Imagens Digitais, Compactação de Imagens .
[1]
[2]
[3]
[4]
[5]
Referências
lay, d. - Álgebra Linear e suas Aplicações.
poole, d - Álgebra Linear.
pesco, d. e bortolossi, h. - Matrizes e Imagens Digitais.
martin, c. e porter, m. - The Extraordinary SDV.
lages, e. - Curso de Análise Vol. 2.