Projeto Final - Andressa Kalil - monografias.poli.ufrj.brmonografias.poli.ufrj.br/monografias/monopoli10002272.… · · 2011-09-26Universidade Federal do Rio de Janeiro CODIFICAÇÃO

Universidade Federal do Rio de Janeiro

CODIFICAO DE IMAGENS USANDO WFA - WEIGHTED FINITE AUTOMATA

Andressa Fortuna Kalil de Faria

2011

i

Universidade Federal do Rio de Janeiro

Escola Politcnica

Departamento de Eletrnica e Computao


Autora:

_________________________________________________ Andressa Fortuna Kalil de Faria

Orientador:

_________________________________________________ Prof. Gelson Vieira Mendona, Ph. D.

Examinador:

_________________________________________________ Prof. Jos Gabriel Rodriguez Carneiro Gomes, Ph. D.

Examinador:

_________________________________________________ Jos Fernando Leite de Oliveira, D. Sc.

DEL

Abril de 2011

ii


Andressa Fortuna Kalil de Faria

Projeto de Graduao apresentado ao Curso de Engenharia Eletrnica e de Computao da Escola Politcnica, Universidade Federal do Rio de Janeiro, como parte dos requisitos necessrios obteno do ttulo de Engenheira.

Orientador: Gelson Vieira Mendona, PhD.

Rio de Janeiro Abril 2011

iii

Captulo 1 Introduo ....................................................................................................................... 1

1.1. Tema ...................................................................................................................................... 1 1.2. Delimitao ............................................................................................................................ 1 1.3. Justificativa ............................................................................................................................ 1 1.4. Objetivos ............................................................................................................................... 2 1.5. Metodologia ........................................................................................................................... 2 1.6. Descrio ............................................................................................................................... 2

Captulo 2 Reviso Terica ................................................................................................................ 2

2.1. Segmentao de Imagens - rvore ......................................................................................... 4 2.2. Segmentao de Imagens - Quadtree ...................................................................................... 4 2.3. Imagens em escala de cinza (ou em tons de cinza) .................................................................. 9 2.4. Upsample (super-amostragem) ............................................................................................. 10 2.5. Downsample (sub-amostragem) ........................................................................................... 12 2.6. Mquina de Estados Finita (MEF) ........................................................................................ 13 2.7. Multiresoluo ..................................................................................................................... 17 2.8. Pseudoinversa de uma matriz ou matriz inversa de Moore-Penrose ...................................... 17 2.9. Fractais ................................................................................................................................ 19 2.10. PSNR ................................................................................................................................... 21 2.11. Wavelet ................................................................................................................................ 22

Captulo 3 Weighted Finite Automata (WFA Autmato Finito e Proporcional) ....................... 24

Captulo 4 Desenvolvimento do Algoritmo da WFA ....................................................................... 40

4.1. Codificador WFA ................................................................................................................. 40 4.2. Decodificador WFA ............................................................................................................. 45 4.3. Codificador/Decodificador WFA combinado ao codificador/Decodificador wavelet ............ 45

Captulo 5 Anlise dos Resultados ................................................................................................... 46

5.1. Consideraes sobre varivel G ............................................................................................ 46 5.2. Consideraes sobre varivel H ............................................................................................ 47 5.3. Consideraes sobre as funes wavelets ............................................................................. 47 5.4. Consideraes sobre erros e comparaes ............................................................................ 47 5.5. Consideraes sobre as configuraes da mquina utilizada ................................................. 48 5.6. Imagens Originais ................................................................................................................ 49 5.7. Resultados ............................................................................................................................ 53

Captulo 6 Concluso ....................................................................................................................... 65

6.1. Proposies para Projetos Futuros ........................................................................................ 65 6.2. Concluso ............................................................................................................................ 66

Bibliografia ....................................................................................................................................... 67

Anexo I Algoritmos ........................................................................................................................... 68

I.1 Funo EncodeWFAAndressaKalilProjetoFinal ......................................................................... 68 I.2 Funo DecodeWFAAndressaKalilProjetoFinal ......................................................................... 70 I.3 Funo codeWFA ....................................................................................................................... 71 I.4 Funo ConstructingFwTreeMatrix ............................................................................................ 72 I.5 Funes AddressFunc ................................................................................................................. 74 I.6 Funo getCellArrayAddressFunc .............................................................................................. 76 I.7 Funo WfaEncodeOrNewState ................................................................................................. 77

iv

I.8 Funo getImageAsLevelInFwTree ............................................................................................ 79 I.9 Funo GetFwTreeMatrixValue ................................................................................................. 81 I.10 Funo DecodeWFA ................................................................................................................ 81 I.11 Funo decodeTestWFA ........................................................................................................... 82 I.12 Funo remakeStatesResolution ............................................................................................... 83 I.13 Funo ResolutionIncrease ....................................................................................................... 84 I.14 Funo ResolutionReduction .................................................................................................... 85 I.15 Funo psnr .............................................................................................................................. 85

Anexo II Cdigos Fonte .................................................................................................................... 87

II.1 EncodeWFAAndressaKalilProjetoFinal.m................................................................................. 87 II.2 DecodeWFAAndressaKalilProjetoFinal.m ................................................................................ 89 II.3 codeWFA.m .............................................................................................................................. 91 II.4 ConstructingFwTreeMatrix.m ................................................................................................... 93 II.5 AddressFunc1.m ....................................................................................................................... 93 II.6 AddressFunc2.m ....................................................................................................................... 94 II.7 AddressFunc3.m ....................................................................................................................... 94 II.8 AddressFunc4.m ....................................................................................................................... 94 II.9 AddressFunc5.m ....................................................................................................................... 95 II.10 getCellArrayAddressFunc.m ................................................................................................... 95 II.11 WfaEncodeOrNewState.m....................................................................................................... 96 II.12 getImageAsLevelInFwTree.m ................................................................................................. 99 II.13 GetFwTreeMatrixValue.m ..................................................................................................... 100 II.14 DecodeWFA.m ..................................................................................................................... 100 II.15 decodeTestWFA.m ................................................................................................................ 101 II.16 ResolutionIncrease.m ............................................................................................................ 102 II.17 ResolutionReduction.m ......................................................................................................... 102 II.18 psnr.m ................................................................................................................................... 103

Anexo III Dados Coletados ............................................................................................................. 104

III.1 Codificao ............................................................................................................................ 104 III.2 Decodificao ........................................................................................................................ 260

1

Captulo 1 Introduo

1.1. Tema

Este trabalho tem como objetivo estudar o algoritmo de codificao e decodificao WFA -

Weighted Finite Automata ou Autmato Finito e Proporcional. WFA uma tcnica de processamento

de sinais, mais especificadamente de imagens, que tem como objetivo final a compresso.

Essa tcnica foi desenvolvida no incio da dcada de 1990 por Karel Culik II e Jarkko Kari a

partir da Mutual Recursive Function Systems (MRFS) e desenvolvida posteriormente para Generalized

Finite Automata (GFA).

1.2. Delimitao

Esse projeto tem como publico alvo os acadmicos estudiosos de processamento de imagens,

mais especificamente, aqueles que estudam tcnicas de compresso de imagens. O maior objetivo deste

projeto atingir, dentro do subgrupo acadmico especificado, aqueles que esto desenvolvendo seus

trabalhos nas universidades brasileiras.

1.3. Justificativa

A principal relevncia deste trabalho dar continuidade discusso do mtodo WFA no meio

acadmico brasileiro, criando uma base mais slida para o estudo. Estudo este que a partir deste

trabalho, sobe de nvel, deixa de ser sobre a soluo WFA em si, para a anlise de resultados e

vislumbramento de novas possibilidades.

WFA conhecido pelas altas taxas de compresso; por seu escopo amplo por ser usado em

vrios tipos de imagens, inclusive em vdeos; por ser multiresolucional; por ser um mtodo com opo

de variao da qualidade na codificao; por fazer Zooming (parte da imagem pode ser regenerada sem

a necessidade de se regenerar a imagem por completo); por suportar manipulao de imagens, isto ,

qualquer transformao matemtica que se deseje aplicar a uma imagem, um operador linear (filtros,

wavelet, etc.), por exemplo, pode ser aplicada diretamente na imagem codificada, sem a necessidade de

regener-la. Por tudo isso, o WFA se destaca como uma importante tcnica a ser estudada dentro do

processamento de imagens.

2

1.4. Objetivos

O escopo deste projeto no possui como principal objetivo a anlise do WFA como tcnica de

compresso, mas sim suas propriedades de codificao e decodificao. A inteno que este projeto

seja capaz de implementar o algoritmo WFA em cdigo Matlab de forma genrica, isto , que o cdigo

seja vlido para qualquer imagem, com sucesso. Alm da implementao, ser estudada a relao entre

a qualidade do algoritmo e a imagem resultante.

1.5. Metodologia

O algoritmo foi desenvolvido utilizando Matlab, sua linguagem e algumas de suas funes.

1.6. Descrio

O projeto tem como produto um conjunto de arquivos em linguagem Matlab e as anlises dos

resultados feitas neste documento.

No captulo 2 ser feita a reviso terica das tcnicas utilizadas para o desenvolvimento da

WFA. No captulo 3, o WFA ser estudado em detalhes. O captulo 4 apresenta o desenvolvimento do

algoritmo da WFA. O captulo 5, as anlises feitas e os resultados alcanados. J o captulo 6 apresenta

as concluses deste trabalho e sugestes para o aprimoramento da ferramenta desenvolvida. O anexo I

contm os algoritmos, o II explica o cdigo fonte e o III apresenta os dados coletados.

2

Captulo 2 Reviso Terica

Sabendo que uma imagem, neste projeto, definida como um conjunto de dados representado

digitalmente, a compresso de imagens , ento, um conjunto de tcnicas de processamento de sinais

que tem como objetivo reduzir a redundncia dest dados para armazen-los ou transmiti-los esses dados

de forma mais eficiente. Assim, este conjunto de tcnicas tem como objetivo representar uma imagem

com o menor nmero de bits possvel, permitindo a sua compresso. A compresso pode ser de dois

tipos, com ou sem perda de dados.

A compresso com perda de dados utilizada nos casos em que a portabilidade e a reduo do

nmero de bits da imagem so mais importantes que a preservao integral da imagem. No entanto a

qualidade, para este caso, ainda um fator de grande importncia. J a compresso de dados sem perda

normalmente aplicada em imagens que possuem a preservao da fidelidade como fator de maior

importncia, sendo que, a imagem refeita aps a descompresso, deve ser idntica imagem original.

Figura 2.1 Processo de compresso e descompresso de uma imagem

S h sentido em representar uma imagem de forma comprimida, se for possvel depois

descomprimir os dados, e esse processo for capaz de representar a imagem novamente. Para tanto,

necessrio construir alm do compressor, um descompressor. Sabendo que a imagem est sendo

codificada, ou seja, representada em outra forma de codificao que no a original, o mtodo de

compresso tambm chamado de codificao, e o mtodo de descompresso de decodificao. A

Figura 2.1 indica como se d o fluxo do processo de compresso e descompresso de uma imagem.

Arquivo Imagem Original

Arquivo Imagem

Comprimida

Arquivo Imagem

Comprimida

Arquivo Imagem

Descomprimida

Entrada Processamento Sada

Algoritmo de Compresso

Algoritmo de Descompresso

3

Existem diversos mtodos de compresso/descompresso, entre eles o da transformada DCT

(Discrete Cosine Transform), o da transformada WT (Wavelet Transform), o mtodo de Fractal, o

mtodo de WFA (Weighted Finite Automata), etc. Este projeto trabalhar apenas com o mtodo WFA.

O algoritmo de compresso WFA tem como entrada uma imagem em componentes RGB, e

como sada seis matrizes. O algoritmo do WFA uma mquina de estados finita, tambm chamada de

autmato finito. As matrizes resultantes so as quatro matrizes de transio W0, W1, W2 e W3, o estado

inicial da MEF (Mquina de Estados Finita), chamado de vetor I, e o valor relacionado a cada estado,

que so colocados no vetor F. Mais a frente, esclarecer-se- toda essa descrio.

Para auxiliar na criao da mquina de estados da WFA, que resultar na codificao da

imagem, o algoritmo se utiliza de algumas ferramentas. Primeiro segmenta a imagem e a representa em

uma estrutura em rvore, cada n desta rvore analisado, verifica-se se este n pode ou no ser

representado como uma combinao linear de outros ns, seguindo a MEF apresentada. Caso seja

possvel, no h alteraes na MEF, caso no seja possvel, a MEF recalculada, incluindo um novo

estado que representar o n em anlise. A sada do algoritmo a mquina de estados finita,

representada pelas matrizes indicadas anteriormente.

A decodificao da imagem feita atravs da execuo do algoritmo da MEF. Coloca-se a

mquina em seu estado inicial I, atribui-se um valor a cada estado segundo F, e calcula-se o valor de

cada pixel a partir das transies W. A Figura 2.2 ilustra esse processo.

Figura 2.2 Processo de codificao e decodificao WFA

Todo o processo descrito nesta seo ser detalhado assim que todo o embasamento terico

necessrio para seu entendimento seja descrito neste projeto.

Arquivo Imagem em

formato bitmap

Arquivo Matrizes W0, W1,

W2, W3, I e F


W2, W3, I e F

Imagem


Encode WFA

Decode WFA

4

2.1. Segmentao de Imagens - rvore

A segmentao de imagens consiste em subdividir uma imagem em regies ou em objetos que a

constituem. Geralmente, a segmentao constitui um passo preliminar anlise de imagens e a noo de

regio ou objeto pode depender da particular aplicao ou anlise pretendida. A segmentao

reorganiza a imagem, que ao invs de uma matriz, utiliza a estrutura em rvore como mtodo de

organizao.

Uma rvore uma estrutura que contm um conjunto finito de um ou mais ns. Sendo assim, o

n um elemento da rvore. Um n que no tem subrvores denominado n folha. Ns razes das

subrvores so denominados ns pais. Em uma estrutura em rvore cada n tem apenas um n pai. O n

que no tem n pai denominado n raiz. Neste trabalho, os ns sero representados como crculos ou

quadrados, no havendo nenhuma diferena entre uma representao ou outra. A Figura 2.3 apresenta

uma estrutura em rvore.

Figura 2.3 - Estrutura em rvore

2.2. Segmentao de Imagens - Quadtree

A codificao WFA (Weighted Finite Automata) se baseia em segmentao de imagem em

regies (subimagens) na composio de seu algoritmo. O modo de segmentao de uma WFA pode ser

de vrios tipos, como rvores binrias e rvores binrias HV (Horizontal Vertical), porm, para este

projeto, foi escolhido o mtodo quadtree.

Esse mtodo assume que a imagem tenha lados de tamanho 2k, k N, ou seja, uma imagem

quadrada, e divide a imagem em quatro regies ou subimagens de tamanhos iguais. A quadtree uma

estrutura de dados em rvore. Cada um de seus ns pode possuir at quatro filhos (rvore de grau

N folha (sem filhos)

N filho do n raiz. N pai do n folha.

N raiz (sem pai). N pai (possui subrvore).

5

quatro), assim, a imagem, que originalmente deve ser quadrada, ento dividida em quatro subimagens

de tamanhos iguais e quadradas.

Quadtree uma estrutura de dados hierrquica baseada no princpio de particionamento

recursivo. A regio de um quadtree divide a imagem de entrada recursivamente em quatro quadrantes

de lados iguais. A diviso da imagem em subquadrantes pra apenas quando um critrio de

simplicidade satisfeito. O critrio de simplicidade ocorre quando um n pai (ou o quadrante da

imagem que est sendo analisado) teria todos os seus ns filhos da mesma cor que a sua, assim uma

nova diviso da imagem no necessria j que o n pai representa os ns filhos satisfatoriamente. No

algoritmo original de compresso de imagem quadtree, a imagem de entrada dividida at que todos os

pixels de um quadrante tenham valores de cor iguais (KATRITRZKE, 2001).

Cada subquadrante, ou subimagem, ganha um identificador, que vai indicar o endereo deste

quadrante, ou subimagem dentro da rvore e a sua posio na imagem original. Conforme a Tabela 2.1.

Tabela 2.1 Endereamento dos quadrantes de uma imagem e na rvore quadtree

0 3

1 2

Cada quadrante pode ser subdividido em mais quatro quadrantes, esses novos quadrantes tm

em seu endereo, como primeiro identificador o quadrante original (n pai), e seu endereo dentro deste

quadrante. A Tabela 2.2 indica como feito o endereamento.

Tabela 2.2 Endereamento dos subquadrantes

01 03 31 33

00 02 30 32

11 13 21 23

10 12 20 22

A mesma lgica se aplica na rvore quadtree. Como se pode observar na Figura 2.4, cada

crculo um n da rvore, e cada n est preenchido com uma intensidade de cor em escala de cinza

(preto, branco e cinza).

6

Figura 2.4 Endereamento dos ns em uma rvore quadtree

Utilizaremos a rvore em quadtree neste projeto para representar uma imagem. Um exemplo de

representao de uma imagem 8x8 se encontra na Figura 2.5. Repare que, para melhor compreenso os

ns esto representados como quadrados agora, porm no haveria nenhuma diferena caso fossem

representados como crculos. As cores dentro dos ns representam a intensidade de cor em escala de

cinza para o n na imagem original.

Figura 2.5 Exemplo de codificao em quadtree de uma imagem

Observa-se que o endereamento das subimagens feita a partir dos quadrantes, compondo a

rvore. A cor de um n corresponde mdia dos valores das cores dos seus quatros quadrantes filhos.

Na rvore, o primeiro n, no nvel 8x8, representa a imagem inteira, sua intensidade de cor dada pela

mdia de cores de toda a imagem, observe a representao na Figura 2.6. A intensidade mdia feita

como uma mistura de cores em uma paleta de cor, a imagem para o exemplo, ento, seria um cinza mais

claro, j que a imagem tem mais tinta branca do que tinta preta.

0

0 0

1 2 3

3 2 1 3 2 1

3 2 1 0 3 2 1 0

7

Figura 2.6 - Representao da imagem no nvel 8x8

Dividindo a imagem inteira em quatro quadrantes de tamanhos iguais chega-se ao nvel 4x4.

Para cada quadrante, ento feita a mdia de cores. Assim, o quadrante 0, s possui tinta branca ser

branco, assim como o quadrante 1 s tem tinta preta e ser preto. J os quadrantes 2 e 3 sero cinza

clara, j que seus subquadrantes possuem mais tinta branca do que tinta preta, e por isso devem ser

divididos para que se tenha maior clareza dos seus detalhes de cor. Cada quadrante corresponde a um

n da rvore, filhos do n em 8x8, com dimenso 4x4, veja a Figura 2.7.

0 3

1 2


Descendo mais um nvel, ao nvel 2x2, e seguindo a mesma lgica de raciocnio, no se divide

mais os quadrantes que possuem filhos com a mesma cor do n analisado, e aqueles quadrantes que

ainda so mdias de cores sofrem diviso, criando mais um nvel da rvore, o nvel 2x2. Assim, os

quadrantes 2 e 3 criam novos ns, como na Figura 2.8.

8

0

30 33

31 32

1

20 23

21 22


Por fim, temos a imagem subdividida em quadrantes que correspondem todos os ns da rvore,

representada pela Figura 2.9.

0

30 33

31 320 323

321 322

1

20 23

21 220 223

221 222

Figura 2.9 Representao da imagem no nvel de 1 pixel

Na implementao do algoritmo aqui proposto, a rvore de quadtree sempre ter quatro filhos.

Essa metodologia foi escolhida para facilitar o algoritmo de construo da rvore, apesar dessa escolha

ter como conseqncia informaes redundantes, j que quando um quadrante s tem uma cor, suas

subimagens (regies) tero necessariamente a mesma cor. Assim, para o exemplo da Figura 2.5, no

algoritmo implementado todos os ramos de sua rvore de quadtree tero 4 nveis, como mostrado na

Figura 2.10.

9

Figura 2.10 rvore quadtree com todos os nveis explcitos

2.3. Imagens em escala de Cinza (ou em tons de cinza)

Em fotografia e computao, uma imagem em escala de cinza (tons de cinza) uma aquela cujo

valor de cor de cada pixel carrega apenas a informao de intensidade de cor, chamada de luminncia

ou Y, quanto maior a intensidade luminosa (mais branco o pixel), maior o valor da funo. Imagens

desse tipo, tambm conhecidas como imagens em preto-e-branco, so compostas exclusivamente de

tons cinzentos, tento o preto como a menor intensidade e o branco como a maior intensidade. A

intensidade de um pixel dada dentro de um intervalo com mnimo e mximo, incluindo os extremos.

Para o projeto aqui desenvolvido, o valor mnimo do intervalo zero, valor este que representa a cor

preta, e o valor mximo igual a um, representando a cor branca. As cores intermedirias desse intervalo

representam apenas tons cinzentos. Quanto menor for valor, mais escuro ser o tom. Os valores deste

intervalo pertencem ao conjunto dos nmeros reais.

Em uma imagem colorida, cada pixel composto como uma combinao de trs sinais de

natureza diferentes, ou seja, trs cores da base. Sendo assim, para associar valores a uma cor,

necessrio escolher uma base no espao de cores. Uma das bases mais utilizadas em processos

computacionais o RGB, que decompe uma cor nas componentes vermelha (Red), verde (Green) e

azul (Blue).

Quando se transforma uma imagem colorida em uma imagem preto-e-branco, o que se busca

uma propriedade da cor que esteja relacionada a quo luminosa a imagem em cada ponto. Esta

propriedade da cor se chama luminncia, correspondendo a uma mdia ponderada entre as componentes

0

3 2

1

1 2 3 0

1 2 3 0

1 2 3 0

1 2 3 0

10

RGB. A converso de uma imagem colorida (em RGB) em uma imagem em escala de cinza no possui

uma soluo nica. Diferentes pesos podem ser associados s camadas de cores na representao da

imagem em preto-e-branco. O valor da intensidade igual soma dos valores de vermelho, verde e

azul, cada um multiplicado por seu peso, conforme a equao 2.1.

azulverdevermelhoePixelIntensidad *11,0*59,0*3,0 ++= (2.1)

Para executar a converso das imagens coloridas em preto-e-branco, foi utilizada uma funo do

Matlab1 que capaz de fazer o clculo descrito na equao 2.1, e seu nome rgb2gray. importante

lembrar que uma imagem RGB dentro do Matlab interpretada como uma matriz 3x3, Imagem(x,y,C),

que tem em x(linha) e y(coluna) a posio do pixel, e em C as componentes RGB. Assim, C tem

dimenso trs, correspondente as trs cores do RGB. Os valores RGB variam de 0 a 255, e antes de

utilizar a funo rgb2gray dividimos os valores das componentes por 255 para que a escala de cinza

fique entre 0 e 1 como proposto. Assim, temos na Figura 2.11.

disp('Por favor, escolha a imagem:');

imageName = input('imageName = ', 's');

figure ('Name','Input Image'), imshow(imageName);

E = getimage;

RGB64 = double(E)/255;

InputImage = rgb2gray(RGB64);

Figura 2.11 - Script de converso RGB em escala de cinza no Matlab

2.4. Upsample (super-amostragem)

Upsampling processo de aumentar a resoluo da imagem.

Imagine uma imagem de dimenso 2x2, como na Figura 2.12. Cada quadrado representa um

pixel, e os valores dentro de cada quadrado representam a luminncia, ou seja, a intensidade em escala

de cinza de cada pixel.

1 Matlab (MATrix LABoratory) um software interativo de alta performance voltado para o clculo numrico, que integra anlise numrica, clculo com matrizes, processamento de sinais e construo de grficos em um s ambiente.

11

0,5 0,25

0,75 1

Figura 2.12 Imagem 2x2 com seus valores em escala de cinza.

O processo de aumento de resoluo de uma imagem no algoritmo WFA dado a partir da

rvore de quadtree. Assim, a representao da imagem 2x2 em rvore apresentada na Figura 2.13.

Figura 2.13 Imagem 2x2 representada em rvore (antes do upsample)

O upsample cria quatro novas folhas filhas, repetindo-se o valor do n que deu origem s novas

folhas. A conseqncia disso o aumento da dimenso da imagem original. A Figura 2.14, apresenta o

resultado do upsample da imagem 2x2 em rvore.

Figura 2.14 Imagem aps o upsample, agora com dimenso 4x4

A imagem que possua dimenso 2x2 agora passa a ter dimenso 4x4, resultando na Figura 2.15.

0,25 0,25 0,25 0,25 0,5 1 0,5 0,5 0,5 0,75 1 0,75 0,75 1 1

0,5 1 0,75 0,25

2,5 4

0,75

0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1

0

3 2

1

0,5 1 0,75 0,25

2,5 4

0

3 2

1

12

0,5 0,5 0,25 0,25

0,5 0,5 0,25 0,25

0,75 0,75 1 1

0,75 0,75 1 1

Figura 2.15 Resultado do upsample da imagem: aumento de resoluo.

2.5. Downsample (sub-amostragem)

Downsampling processo de reduzir a resoluo da imagem.

O processo de diminuio da resoluo de uma imagem no algoritmo WFA dado a partir da

rvore de quadtree, reduzindo um nvel fazendo a mdia aritmtica entre os quatro quadrantes filhos do

n da imagem, conforme a equao 2.2.

[ ])3()2()1()0(4

1)( wfwfwfwfwf +++=

(2.2)

Em que f(w) significa o valor mdio dos seus quatro ns filhos. O resultado uma imagem de

resoluo menor em que um pixel na nova dimenso representa os quatro que lhe deram origem por

uma mdia aritmtica.

1 0 0,4 1

0,9 0,1 0,5 0,5

0,8 0,8 0 0,7

0,8 0,8 0 0,1

Figura 2.16 Imagem 4x4 antes do downsample

13

Figura 2.17 Imagem original em rvore (antes do downsample)

Por exemplo, dada a imagem na Figura 2.16 de resoluo 4x4 e sua representao em rvore na

Figura 2.17, aplicamos o downsample para reduzir a dimenso da imagem. A rvore da Figura 2.17,

para possuir uma resoluo menor, perde os ns folhas, resultando na nova rvore da Figura 2.18.

Figura 2.18 Imagem aps o downsample

A imagem reconstituda ter dimenso 2x2, representada pela Figura 2.19.

0,5 0,6

0,8 0,2

Figura 2.19 Resultado do downsample da imagem, diminuio da resoluo.

2.6. Mquina de Estados Finita (MEF)

Tudo o que foi visto at aqui compe a preparao para a codificao WFA. Utilizam-se as

ferramentas descritas anteriormente como suporte na criao de uma mquina de estados finita, ou seja,

0,5 0,2 0,8 0,6

2,1 4

0

3 2

1

0,4 0,5 1 0,5 0,1 0 1 0,9 0 0,8 0,8

0 0,8 0,8 0,7 0,1

0,5 0,2 0,8 0,6

2,1 4

0

3 2

1

0 3 2 3 0 3 2 1 0 3 2 1 0 3 2 1

14

um autmato finito, que a WFA. Esta seo tem como objetivo esclarecer o que uma mquina de

estados finita, porm, no se tem como objetivo, ainda, explicar a WFA.

A mquina de estados finita ou autmatos finitos um modelo usado na teoria da cincia da

computao para descrever a execuo de um algoritmo (KATRITRZKE, 2001). Seu comportamento

especificado por um conjunto finito de smbolos de entrada (inputs), por um alfabeto (conjunto) de

smbolos, ; por um conjunto de estados, Q; e por uma funo de estados, : x Q Q. s vezes, a

mquina de estados tambm pode possuir um conjunto finito de smbolos de sada (output), O, sendo a

funo de estados, ento, redefinida como : x Q O. A MEF s pode estar em um estado por vez,

quando a MEF recebe um input, ela muda de estado de acordo com a sua funo. Outra possibilidade

a funo retornar um output em vez de um estado. Um dos estados chamado estado inicial. Dado uma

seqncia de smbolos de entradas o comportamento da MEF pode ser determinado. Como dito, a MEF

muda de estado de acordo com os inputs. Existem, portanto, estados intermedirios, os quais esto

ligados a outros estados pela funo de estados da MEF. Um dos estados pode ser definido como estado

final uma vez nesse estado a MEF nunca alcanar outro estado. O estado final modela o sucesso da

execuo do algoritmo.

A MEF representada pelo grfico de transio. Cada estado representado por um vertex2 no

grfico, e uma flecha direcional de um estado si a um estado sj que utilizada para indicar que um

smbolo de entrada, a , faz com que a mquina mude do estado si ao estado sj. Este fenmeno

denominado transio e referenciado pelo smbolo de entrada a que o causou. A flecha tambm pode

indicar a gerao de um output, o O. O vertex representando um estado inicial freqentemente

representado por um quadrado, enquanto o estado final por dois crculos concntricos.

Considere, por exemplo, uma MEF genrica com = {0,1}; Q = {s0, s1, s2, s3}, em que s0 o

estado inicial e s3 o estado final, e a funo de estados definida pela matriz de transio de estados

conforme mostrado na Tabela 2.3. Os smbolos de entrada (inputs) 0 e 1 podem representar

respectivamente, por exemplo, as palavras no e sim, e os estados as seguintes perguntas: s0: Voc

homem?, s1: Voc tem menos de 22 anos?, s2: Tem mais de 25 anos?, s3: Est querendo casar?.

Chegar ao estado s3 indica maturidade para o casamento, e no h outputs para a funo da MEF em

questo. A MEF correspondente est representada pelo grfico de transio na Figura 2.20 (MEF de

maturidade para o casamento).

2 Padro de vnculo onde se encontram entrada e sada de vnculos, neste caso especfico, os vnculos so as flechas de transio.

15

Tabela 2.3 Exemplo: transio de estados

Q

s0 s1 s2 s3

0 s1 s3 s2 s3

1 s2 s1 s3 s3

Para a mquina de estados apresentada, so produzidos dois exemplos. Roberto tem 25 anos, e

por enquanto no quer casar, namora Roberta 23 anos que j tem vontade de casar.

Para Roberto, se faz a pergunta em s0: Voc homem?, como Roberto do sexo masculino, a

resposta sim, o que o leva ao estado s2. No estado s2 pergunta se Roberto tem mais de 25 anos,

como Roberto ainda no completou 26 anos, a resposta no, o que o mantm no estado s2 at que

ele complete 26 anos. Aos 26 anos Roberto j ter maturidade para se casar, fazendo com que ele

evolua ao estado s3. Repare que a mquina de estados diz que ele j tem maturidade para se casar

mesmo que ele no queira se casar, pergunta referente ao estado s3.

Figura 2.20 Grafo de transio

Quanto a Roberta, ela no homem, o que a leva ao estado s1. Em s1 pergunta-se se Roberta tem

mais de 22 anos, como ela j possui mais de 22 anos ela ento muda de estado e vai a s3. O mesmo vale

para Roberta, mesmo que aos 23 anos ela no quisesse se casar, a mquina de estados nos diz que ela j

tem maturidade suficiente para tanto, mas como observado anteriormente, ela j quer se casar.

A informao contida no grfico de transio tambm pode ser especificada pela matriz de

transio. Dada uma MEF com n estados, a matriz de transio n x n, onde cada estado se relaciona

com os outros n estados, cada valor da posio (i, j) corresponde transio do estado si ao estado sj

0

1

0

0

1

1

1 s0

s2

s3

s1

0

16

causada pelo smbolo de entrada. Caso a MEF gere smbolos de sada, cada smbolo seria guardado na

posio (i,j) junto com o input que o causou. A matriz de transio correspondente ao exemplo dado

ilustrada na Tabela 2.4. O valor - indica que no existe um smbolo de entrada que cause a transio

do estado si ao estado sj.

Tabela 2.4 Matriz de Transio

destino

s0 s1 s2 s3

Ori

gem

s0 - 0 1 -

s1 - 1 - 0

s2 - - 0 1

s3 - - - 0;1

O nmero de smbolos no conjunto dado pelo cardeal do conjunto, ou seja, | |, que

corresponde ao nmero de smbolos, para o exemplo, = {0,1} = {no, sim}, ou seja, | | = 2.

Uma palavra w um nmero finito de smbolos de em seqncia. No caso de Roberto, w = 10010

onde os dois primeiros 0 correspondem as duas vezes que perguntado a Roberto se ele tem mais de

25 anos, e sua resposta foi negativa. Para Roberta w = 011.

Uma palavra vazia, , uma palavra que no consiste de smbolos. O tamanho de uma palavra w

dado por |w|. k o conjunto de todas as palavras de tamanho k em . Enquanto * o grupo de todas

as palavras, incluindo a palavra vazia .

Considere outro exemplo, um alfabeto = {0, 1, 2, 3}, alfabeto este sendo, ento, um conjunto

de smbolos, 0, 1, 2 e 3. Assim, o cardeal do conjunto, dado por || = 4. A palavra w1=000 uma

seqncia de smbolos de , com |w1|=3, ela pertence, ento, ao conjunto de palavras com trs smbolos,

ou seja, 3, e tambm ao conjunto de todas as palavras *. Uma palavra w2=0111, de tamanho quatro,

pertence aos conjuntos 4 e *.

17

2.7. Multiresoluo

Formalmente, uma imagem multiresolucional uma funo real () em *. A compatibilidade

de diferentes resolues tem como precondio que : * seja uma funo que preserve as mdias.

Uma funo : * preserva as mdias (ap average preserving) se:

[ ])3()2()1()0(4

1)( wfwfwfwfwf +++=

(2.3)

Onde w refere-se ao endereo do n em anlise, w0 ao endereo do quadrante 0 do n em

anlise, w2 endereo do quadrante 2, e assim por diante.

2.8. Pseudo-inversa de uma Matriz ou Matriz Inversa de Moore-Penrose

A noo de matriz inversa aplicvel a matrizes quadradas, porm existe uma generalizao que

aplica a inverso de matrizes de qualquer dimenso, chamada de pseudo-inverso ou inverso de

Moore-Penrose. A pseudo-inversa no nica. Supondo que A mxn, onde n < m, a pseudo-inversa pode

ser calculada da forma:

( ) ( ) IAAAA nxnTnxnmxnTnxm =1 (2.4)

No algoritmo, ao invs de desenvolver os clculos, utilizada funo pinv(.) que corresponde

pseudo-inversa da matriz. Em todo o caso, nesta seo, apresenta-se a definio de pseudo-inversa,

porm ela no necessria para o entendimento da soluo apresentada j que a funo Matlab

utilizada e apresentada aqui por formalidade.

A pseudo-inversa, A+, (Inversa de Moore-Penrose) a matriz n por m que inverte A de espao

coluna de volta para espao linha, em que N (A+) = N (AT). A+ A e AA+ so as matrizes de projeo no

espao linha e no espao coluna, para tanto, Posto (A+) = Posto (A) (HAGEN, 2001).

18

Os valores singulares 1, 2, . . . , r de uma matriz A, do tipo m n, so as razes quadradas

positivas dos valores prprios da matriz de Gram3 K = ATA, isto , = > 0, Dada uma matriz A

do tipo m n, com m n, se a equao 2.5 for respeitada.

TVUA = (2.5)

Em que U e V, m r e n r, resp., so matrizes cujas colunas so ortonormais e onde a

matriz diagonal r r, identificada pela equao 2.6.

=

r

...2

1

(2.6)

Ento, diremos que UVT a fatorizao em valores singulares de A. Qualquer matriz admite

uma fatorizao em valores singulares, se:

ATA: n n; simtrica; valores prprios reais no negativos.

Os valores prprios no nulos de ATA so como na equao 2.7 (ordenados de modo decrescente):

1 2 _ r > 0 = r+1 = = n. (2.7)

= > 0, para = 1, . . . , r.

=

r

...2

1

v1, v2, . . . , vr vetores prprios ortonormais de ATA associados aos valores prprios 1, 2, . . . , r,

respectivamente.

V = [v1 v2 vr]

u = (1/)Av, para = 1, . . . , r, so ortonormais.

U = [u1 u2 ur].

3 A matriz de Gram de um conjunto de vetores em um. espao pr-hilbertiano a matriz que define o produto escalar, cujas entradas vm dadas por Gij = (vi | vj). Jrgen Pedersen Gram d nome a essa matriz. Uma das aplicaes mais importantes da matriz de Gram a comprovao da independncia linear: um conjunto de vetores ser linearmente independente entre si somente se o determinante de Gram no for nulo.

19

As seguintes observaes devem ser feitas:

1) Os valores singulares de uma matriz so nicos; contudo, as matrizes U e V no so nicas.

2) U diagonaliza ATA.

3) v1, v2, . . . , vk base ortonormal para (A).

4) u1, u2, . . . , uk base ortonormal para C (AT ).

5) car(A) = nmero de valores singulares.

Suponha que UVT a fatorizao em valores singulares de A. A pseudo-inversa ou a inversa

de Moore-Penrose de A a matriz n m A+ = V-1UT .

Condies de Penrose:

1. AXA = A

2. XAX = X

3. (AX)T = AX

4. (XA)T = XA

Se A do tipo m n, ento existe uma nica matriz X, n m, que satisfaz estas condies. Se

(quadrada) no singular, ento A+ = A1.

2.9. Fractais

Fractais so imagens (ou conjuntos) que apresentam fragmentao independente da escala. Esta

fragmentao pode ser exatamente ou aproximadamente auto-similar. A Figura 2.21 e a Figura 2.22

demonstram imagens em fractais.

20

Figura 2.21 Figura 2.22

Uma definio mais genrica de fractal qualquer objeto geomtrico que pode ser dividido em

partes, cada uma das quais semelhante ao objeto original, desde que as partes apresentem fragmentao.

Na natureza, temos vrios exemplos de fractais, como as rvores e as samambaias, onde podemos

observar propriedades de repetio ou recursividade claramente. Um brcolis tambm um fractal,

observa-se a mesma forma geomtrica repetida com a mesma preciso em qualquer escala, sua imagem

se encontra na Figura 2.23.

Figura 2.23 Brcolis

A WFA pode ser caracterizada como um fractal, pois a sua MEF (Mquina de Estados Finita)

descreve o quadrante da imagem como uma combinao linear de outros quadrantes e subquadrantes

(subimagens), quadrantes estes caracterizados como estados da MEF. Isso permite gerar padres

fractais.

21

Na WFA, a mesma complexidade algortmica aplicada a toda a imagem, ou seja, a MEF

vlida e aplicada para a reconstruo de toda a imagem. Para se descobrir o valor do menor quadrante

da rvore de quadtree, se aplica o mesmo algoritmo do quadrante maior. Ao mesmo tempo, a WFA por

ser multiresolucional, possui detalhes em qualquer escala, definida por um algoritmo simples, a MEF.

E o algoritmo simples da MEF que define a combinao linear entre os quadrantes (estados).

No algoritmo implementado no utilizada nenhuma teoria de fractais. O intuito desta seo

identificar a WFA como um fractal para possvel desenvolvimento posterior.

2.10. PSNR

A Peak Signal Noise Ratio ou PSNR a medida mais aceita entre os mtodos atuais para a

avaliao de qualidade de vdeo e imagens. A PSNR uma relao entre o mximo possvel de potncia

de um sinal, pela potncia do rudo, quando comparamos um sinal antes e depois de um processo de

degradao, sendo normalmente representada em dB (Decibel). Aplicando este conceito em imagens

comprimidas, tem-se que o PSNR a relao entre a entrada e a sada de um processo de compresso

com perdas, que avalia o quanto de rudo a compresso introduziu na imagem original, sendo dada pela

expresso 2.8.

=

=

MSE

Max

MSE

MaxPSNR II

||log20log*10 10

2

10 (2.8)

onde MaxI o valor mximo possvel de um pixel na imagem e o MSE (Mean Square Error):

=

=

=1

0

1

0

2||),(),(||1 m

i

n

j

jiKjiImn

MSE (2.9)

onde K a imagem reconstruda, I a imagem original, m e n definem o tamanho da imagem avaliada.

No caso deste projeto final, MaxI igual a 1.

Avaliando as equaes, quanto maior o valor do PSNR, maior a relao entre a potncia do

sinal pela potncia do rudo, o que significa melhor qualidade, ou seja, a imagem original e a

descomprimida so quase iguais, em termos gerais, valores de PSNR acima de 42dB correspondem

22

compresses que introduzem perdas imperceptveis ao olho humano, o que significa uma qualidade

excepcional.

2.11. Wavelet

Wavelet uma funo capaz de decompor e descrever outras funes no domnio da freqncia,

de tal forma que possvel analisar essas funes em diferentes escalas de freqncia e de tempo. A

decomposio de uma funo de wavelets conhecida como transformada wavelet e tem duas variantes

conhecidas como contnua e discreta. Precisa-se tambm da transformada inversa, de forma a recompor

o sinal no domnio do tempo a partir da sua decomposio wavelet, a transformada inversa tambm tem

suas variantes conhecidas como continua e discreta.

Alm disso, na anlise wavelets, pode-se usar funes que esto contidas em regies finitas,

tornando-as convenientes na aproximao de dados com descontinuidades. O princpio mais geral da

construo das wavelets o uso de dilataes e translaes. As wavelets mais usadas formam um

sistema ortogonal de funes com suportes compactos construdos desta forma. Esta a razo pela qual

elas podem distinguir as caractersticas locais de um sinal em diferentes escalas e, por translaes, elas

cobrem toda a regio na qual o sinal estudado. Na anlise de sinais noestacionrios, a propriedade

de localidade das wavelets conduz s suas vantagens sobre a transformada de Fourier. Os algoritmos de

wavelets processam dados em diferentes escalas ou resolues e, independentemente da funo de

interesse ser uma imagem, uma curva ou uma superfcie, wavelets oferecem uma tcnica elegante na

representao dos nveis de detalhes presentes. Elas constituem uma ferramenta matemtica para

decompor funes hierarquicamente.

A transformada discreta de wavelet consiste em identificar os parmetros ck e dj,k, k N, j N na

equao 2.10:

=

=

+=k k

jkjk ktdktctf )2()()( ,

(2.10)

onde (t) e (t) so as funes conhecidas respectivamente como wavelet pai e wavelet me. A

wavelet pai na verdade uma funo de escala, que depende da wavelet me. Das funes (t) e (t)

podemos calcular as seqncias h = {hn} n Z e g={gn} n Z:

23

==Zn

nnn nthth

)2(2)(;, ,10,0 (2.11)

e

==Zn

nnn ntgtg

)2(2)(;, ,10,0 (2.12)

.

Os coeficientes hn e gn so denominados coeficientes de filtros da wavelet, onde hn define o

filtro passabaixa e o gn o filtro passa-alta. Eles so denominados par de filtros QMF (Quadrature

Mirror Filter). As equaes 2.11 e 2.12, que na verdade so seqncias, so a base da transformada

discreta de wavelet. Para o trabalho aqui desenvolvido, utiliza-se a transformada discreta wavelet e sua

inversa provida pelo Matlab, dwt2 e idwt2. Essas duas funes so de primeiro nvel e para duas

dimenses.

24

Captulo 3

Weighted Finite Automata (WFA Autmato Finito e Proporcional)

Antes de formalizar a WFA matematicamente, importante fazer uma associao conceitual

entre as ferramentas tericas vistas anteriormente e a WFA. Considere um alfabeto = {0, 1, 2, 3},

onde cada uma das letras desse alfabeto corresponde ao endereamento de um quadrante de uma

imagem. O padro de endereamento utilizado se encontra na Tabela 3.1. Caso seja necessrio dividir a

imagem em mais subquadrantes, cada subquadrante ter como primeira letra de sua palavra, o

quadrante maior, como na Tabela 3.2, para melhor entendimento, os quadrantes da Tabela 3.1 foram

coloridos para facilitar a identificao. Pode-se ter, ento, para uma imagem qualquer, o endereamento

de um quadrante em vrios nveis de profundidade. Cada nvel diferente gerar uma palavra de

comprimento diferente. A palavra de tamanho 0 assume endereo , e refere-se imagem inteira, sem

quadrantes. Forma-se, portanto, um conjunto de palavras, que chamaremos de w, de tamanhos

diferentes que tem como objetivo identificar o quadrante na imagem, ou a posio dentro da rvore

quadtree, para anlise.

Tabela 3.1 Padro de endereamento de quadrantes utilizado

0 3

1 2

Tabela 3.2 Padro de endereamento de quadrantes

01 03 31 33

00 02 30 32

11 13 21 23

10 12 20 22

Como visto anteriormente, esse endereamento pode referenciar a posio do quadrante em

uma rvore quadtree. A rvore montada de forma que o endereo tenha associado a ele um valor que

represente a mdia de cor de toda a imagem, em escala de cinza, o que ser um valor entre 0 e 1 como

visto na seo 2.3. Para montar a rvore, comea-se do pixel, o nvel mais profundo, anotando seus

valores em escala de cinza. A partir da, calcula-se os valores dos ns pais pela mdia dos ns filhos, ou

seja, conforme a equao 3.1 repetida abaixo:

25

[ ])3()2()1()0(4

1)( wfwfwfwfwf +++=

(3.1)

Onde w o endereo do n pai, assim, para o exemplo da Figura 2.5, se tem:

[ ] =+++= )223()222()221()220(4

1)22( fffff

[ ] 75.010114

1 =+++ (3.2)

Calcula-se o valor desta funo para todos os ns, at que se chegue ao endereo . A Figura 3.1

contm a Figura 2.5, apresentada na seo 2.2, e mostra o valor correspondente, em escala de cinza, de

cada um dos ns da rvore.

Figura 3.1 Figura 2.5, e a rvore montada para ela, com os valores da escala de cinza para cada n da rvore.

0 0 0 0 1 1 1 0 1 1 1 1 1 1 11

1 0,75 1 0

0,6875

1 1 1 1 1 0 11 1 1 1 1 0 0 0 0

1 0,75 0 1

0,687

0,59385

0

0 0 0 0 0 0 00 0 0 0 0 0 0 0 0

0 0 0 0

1 2 3 0

1 2 3 0

1 2 3 0 1 2 3

0

0

3 2

1

1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1

26

Com os endereos de cada quadrante, a rvore montada, e os valores de cor associados a cada n

da rvore, a imagem pode ser analisada pela WFA. A WFA no , nada mais nada menos que, uma

mquina de estados, e o algoritmo de codificao o que monta a mquina de estados para a imagem

analisada. O algoritmo de codificao constri uma mquina de estados que tem como expresso

fundamental a equao 3.3:

;,,...)...,,()( *21321 kwwFWWIWaaaafwf akaak === (3.3)

J se sabe que f(w) a intensidade mdia da regio da imagem em escala de cinza, como visto

na equao 3.1. Considere agora I apenas como uma matriz linha qualquer e F apenas como uma matriz

coluna qualquer, e mais adiante se explicar os seus significados. A inteno, neste momento, explicar

o que so as matrizes W. As matrizes W0, W1, W2, W3 so matrizes de transio de uma Mquina de

Estados Finitos (MEF). A matriz de transio W0 representa a transio a partir do endereo chamado

Q, neste caso como W0, Q = 0, do estado X, para o estado Y, como mostrado na Figura 3.2. Repare

que Q identifica o quadrante da matriz W e o quadrante do estado analisado. A posio do valor desta

transio dentro da matiz pode ser dada por: W0(x,y) = T.

Figura 3.2 Transio a partir do Quadrante 0 do Estado X para o Estado Y, onde Estado X o Quadrante 0 do

Estado Y.

Como dito, a matriz W0 representa a transio a partir do quadrante 0 de cada estado, o peso necessrio

para se mudar para o estado destino. O significado de cada transio na matriz de transio para W0

apresentada na Tabela 3.3.

Estado Y (destino)

Estado X (origem em Q=0, para W0)

27

Tabela 3.3 Matriz de transio W0

Estado de destino

S1 S2 S3 S4

Est

ado

de O

rige

m

S1 Q0estado1

para estado1

Q0estado1

para estado2

Q0estado1

para estado3

Q0estado1

para estado4

S2 Q0estado2

para estado1

Q0estado2

para estado2

Q0estado2

para estado3

Q0estado2

para estado4

S3 Q0estado3

para estado1

Q0estado3

para estado2

Q0estado3

para estado3

Q0estado3

para estado4

S4 Q0estado4

para estado1

Q0estado4

para estado2

Q0estado4

para estado3

Q0estado4

para estado4

O mesmo vlido para a matriz W1, que ter a seguinte configurao:

Tabela 3.4 Matriz de transio W1

Estado de destino

S1 S2 S3 S4

Est

ado

de O

rige

m

S1 Q1estado1

para estado1

Q1estado1

para estado2

Q1estado1

para estado3

Q1estado1

para estado4

S2 Q1estado2

para estado1

Q1estado2

para estado2

Q1estado2

para estado3

Q1estado2

para estado4

S3 Q1estado3

para estado1

Q1estado3

para estado2

Q1estado3

para estado3

Q1estado3

para estado4

S4 Q1estado4

para estado1

Q1estado4

para estado2

Q1estado4

para estado3

Q1estado4

para estado4

E assim, o mesmo vale para W2 e W3. A Figura 3.3 representa o grfico de transio para dois

estados:

28

Figura 3.3 Grfico de transio para dois estados.

Especificado o que so as matrizes W, volta-se s matrizes linha e coluna I e F. A matriz coluna

F contm o valor da funo f para cada estado, assim o valor mdio da intensidade em escala de cinza

para a imagem que representa o estado, como j visto anteriormente. Na Figura 3.4, apresenta-se um

exemplo do clculo da matriz F para dois estados especficos:

Figura 3.4 Calculando f para dois estados

A matriz I a matriz que identifica o estado inicial da nossa mquina de estado. A mquina de

estados poderia ser iniciada por vrios estados ao mesmo tempo, mas isso no ser mostrado no

algoritmo desenvolvido neste trabalho. A matriz I sempre vai ser da forma [1 0 0 0 ... 0], sua dimenso

sempre ser 1 x n, onde n o nmero de estados que compem a mquina, onde o estado identificado

como inicial sempre representar a imagem inteira, e esse estado que representa a imagem inteira

Estado1

f() = 0,59375 f(0) = 1 f(1) = 0

f(2) = 0,6875 f(3)=0,6875

Estado2 f(0) = 1 f(00) = 1 f(01)= 1 f(02) = 1 f(03) = 1

f(estado1)=0,59375 f(estado2)=1

F=[f(estado1) f(estado2)]T

F=[0,59375 1]T

I = [1 0]

1;f(estado1) 2;f(estado2)

1;W1(1,2)

2;W2(1,2)

3;W3(1,2)

0;W0(1,1)

1;W1(1,1)

2;W2(1,1)

3;W3(1,1)

0;W0(2,2)

2;W2(2,2)

3;W3(2,2)

1;W1(2,2)

0;W0(1,2)

2;W2(2,1)

3;W3(2,1)

1;W1(2,1)

0;W0(2,1)

29

sempre ser o primeiro estado. Para o exemplo com dois estados a matriz I ser [1 0]. Definidas I e F,

definem-se as matrizes W.

No exemplo mostrado na Figura 3.6, existe dois estados. A transio que queremos definir

W0(2,1). Essa transio define qual o peso que devemos dar quando samos do estado 2, pelo

quadrante 0 e vamos para o estado 1. Nada mais justo que utilizar a funo f para calcular o peso da

transio. Ento, W0(2,1) igual a f(Q0estado2) dividido por f(estado1).

Figura 3.5 Transio do estado dois no subquadrante 0, para o estado 1.

Porm, essa forma de definir o peso, no reflete bem a realidade, j que a funo f uma

representao resumida, ou seja, uma mdia de valores da imagem. Porque no definir o valor da

transio utilizando uma operao de matrizes, matrizes que contenham os verdadeiros valores, ponto a

ponto dos estados, utilizando a maior resoluo entre as dimenses das matrizes no clculo? Isso faria

com que os resultados fossem mais fiis a realidade. o que realmente acontece, e para isso utiliza-se

no desenvolvimento do algoritmo a funo pinv(.) do Matlab, vista na seo 2.8.

Figura 3.6 Calculando W0(2,1)

A pergunta que fica como definir se um estado novo deve ser criado ou no. Fazendo-se a

seguinte pergunta resolve-se a questo: O n da rvore sob anlise pode ser codificado como uma

Estado 1 Estado 2

W0(2,1)= Q0estado2 para estado1

upsample

Estado 1

Estado 2

W0(2,1)=f(00)/f()

30

combinao linear dos estados existentes na MEF? Caso a resposta seja afirmativa, a mquina de

estados se mantm, caso a resposta seja negativa, um estado novo criado na mquina de estados,

associando a este estado, o valor de f(w) do n em anlise. Caso seja necessrio criar um novo n, toda

a MEF recalculada utilizando a funo pinv(.), construindo as transies dos outros estados ao estado

novo e vice-versa. Os valores de f(w) para todos os ns que viraram estados ficam guardados em uma

matriz F; as condies iniciais da MEF so colocadas em uma matriz I; e as transies, em matrizes W.

Existe uma matriz W para cada quadrante estudado, W0, W1, W2 e W3.

A Figura 3.7 ilustra todo o processo de codificao WFA.

Figura 3.7 Processo de codificao da WFA

Para decodificar a imagem, basta executar a mquina de estados, o que remontar a rvore de

quadtree, associando-se novamente os valores de f(w) para cada n, a partir da rvore fica ento fcil

Imagem em rvore

Subimagem em rvore

WFA W0, W1, W2,

W3, I e F

Imagem original

Subimagem Em anlise

1

0

32

1

WFA recalculada W0, W1, W2, W3, I

e F. Criando um novo estado. Analisar outra subimagem.

endereamento w=22

Calcula-se a subimagem usando a WFA e seu endereo.

input w=22

output subimagem decodificada

Verifica-se qual sada tem melhor qualidade ao menor custo. Aquela MEF que tiver melhor qualidade ao

menor custo assumida como a WFA.

Depois da escolha feita, o algoritmo segue e uma nova subimagem

analisada. Ou?

Qual a melhor MEF?

1111

2222

3333

4444 5555

6666

0000

30

2

1

1

121

23

0

2

3

0

31

reconstruir a imagem. Para calcular o valor de cada n, basta fazer o clculo indicado na equao 2.9 e

repedido em 3.1:

;,,...)...,,()( *21321 kwwFWWIWaaaafwf akaak === (3.4)

Assim:

FWWIf *2*2*)22( = (3.5)

FWWWIf *3*2*2*)223( = (3.6) FWWWIf *2*1*0*)012( = (3.7)

Conclui-se que a WFA uma mquina de estados representada por uma distribuio inicial I,

pelas transies W e pela distribuio final F. Agora, depois de esquematizado todo o processo de

codificao e decodificao, fica mais fcil entender a formalizao matemtica da WFA.

Por imagem de resoluo finita entende-se uma imagem digitalizada em preto-e-branco (escala

de cinza) com 2m x 2m pixels (tipicamente 7 m 11), de valores reais (valores entre 0 e 2k-1,

geralmente k=8, em nosso caso k=1).

Por imagem multiresolucional entende-se um conjunto compatvel de imagens com resoluo 2n

x 2n, n =0,1,2...

Tabela 3.5 Padro de endereamento de quadrantes utilizado 0 3

1 2

atribudo a cada pixel em resoluo 2n x 2n uma palavra de tamanho n dentro do alfabeto =

{0, 1, 2, 3}. Cada letra de refere-se a uma unidade quadrtica (quadrado, ou quadrante se preferir),

como mostrado na Tabela 3.1 e representada novamente pela 3.5. Define-se como o endereo da raiz

da rvore quadtree da imagem. Cada letra de compe o endereo dos filhos da raiz. Cada palavra em

* de tamanho k, dita w, ento endereo nico de um dos ns da rvore quadtree, com nvel de

profundidade k. Os filhos desse n tm endereo w0, w1, w2, w3. Assim, formalmente uma imagem

multiresolucional uma funo real () em *. A compatibilidade de diferentes resolues tem como

precondio que : * seja uma funo que preserve as mdias. Uma funo : * preserva

as mdias (ap average preserving) se:

32

[ ])3()2()1()0(4

1)( wfwfwfwfwf +++= (3.8)

Equao que j havia sido apresentada como equao 2.3. Uma funo ap representada por

um nmero infinito de quadtree rotuladas. A raiz rotulada por (), seus filhos so rotulados da direita

para a esquerda por (0), (1), (2), (3). Intuitivamente, (w) a mdia em escala de cinza dos

subquadrantes w para um dado tom cinza da imagem.

Um WFA de m-estados com o alfabeto definido por:

i. Um vetor linha I 1xm (chamado distribuio inicial);

ii. Um vetor coluna F mx1 (chamado de distribuio final); e

iii. Matrizes de transio (ou de proporo, ou de pesos) Wa mxm para todo a

O WFA A define uma funo multiresolucional em por:

FWWWIaaaaf akaakA ...)...,,( 21321 = (3.9)

Equao que j havia sido apresentada anteriormente em 3.3 e 3.4. No WFA, cada transio

identificada por um nmero real, conhecido como peso da transio, e pelo smbolo de entrada. Ao

invs de se ter estados iniciais e finais, se tem distribuies iniciais e finais, a distribuio final tem o

valor de f(w) associado a cada estado. Um exemplo de grfico de transio para a WFA com = {0, 1,

2, 3} e dois estados mostrado na Figura 3.8. A distribuio inicial e a distribuio final esto escritos

dentro de cada estado (MULLER, 2005).

Figura 3.8 Exemplo de um grfico de transio WFA.

0;1 1;1

1;

2;

3;1 0; 1;

2; 3;

0;1 1;1

2;1 3;1

33

Dada o WFA com um alfabeto consistindo de n estados, ele representado por || matrizes de

transies Wa, a , cada uma com o tamanho n x n, um vetor linha 1 x n, I, e um vetor coluna n x 1,

F. O valor em Wa(i,j) o peso da transio do estado i para o estado j dado um smbolo de entrada a,

caso no seja zero. Se o valor for zero, no existe transio do estado i para o estado j para o input a. O

elemento i dos vetores I e F correspondem ao valor de distribuio inicial e final, respectivamente do

estado i.

A WFA pode ser utilizada para especificar uma imagem em escala cinza de resoluo 2n x 2n.

Fazendo ={0, 1, 2, 3} e fazendo a corresponder a cada quadrante do quadrado (ou imagem),

como na Tabela 3.1, apresentada novamente na Tabela 3.6. Isso aplicado recursivamente at que o

quadrado (ou imagem) tenha se dividido em 2n x 2n subquadrados. Uma palavra w de tamanho n em

representa o endereo de um dos subquadrados.

Tabela 3.6 Padro de endereamento de quadrantes utilizado

0 3

1 2

Em geral, se o subquadrado endereado por uma palavra w, os seus quadrantes vo ser

endereados por w0, w1, w2 e w3. A palavra vazia utilizada para enderear toda a imagem. Isso nos

leva a uma representao da imagem por quadtree: a raiz da rvore tem endereo , os quatro

quadrantes da imagem correspondem aos quatro filhos da raiz, etc. Assim, cada palavra de tamanho k

o endereo de um nico n da rvore de profundidade k.

Define-se a funo : * por:

;,,...)...,,()( *21321 kwwFWWIWaaaaFwf akaak === (3.10)

Em outras palavras, especifica o valor da escala de cinza cada quadrado na resoluo 2n x 2n,

definindo assim uma imagem em multiresoluo. Para que as diferentes resolues sejam compatveis,

requerido que preserve a sua mdia. Equao j apresentada em 2.3, e em 3.8.

[ ])3()2()1()0(4

1)( wfwfwfwfwf +++=

(3.11)

34

Um exemplo com uma imagem 4x4 mostrado na Figura 3.9 com sua correspondente

representao quadtree mostrada na Figura 3.10.

1 0 0,4 1

0,9 0,1 0,5 0,5

0,8 0,8 0 0,7

0,8 0,8 0 0,1

Figura 3.9 - Imagem 4x4

Figura 3.10 Imagem 4x4 em rvore quadtree

O valor em escala de cinza de um quadrado com endereo w a mdia dos valores em escala de

cinza dos seus quarto quadrantes (subquadrados), com endereos w0, w1, w2, e w3. Especificamente, o

valor de () a mdia em escala de cinza de toda a imagem.

Caminhando-se para o nvel acima, reduzindo a resoluo da imagem, fazermos o downsample.

Caminhando-se para um nvel abaixo, fazemos o upsample, aumentando a resoluo da imagem.

Quanto maior a quantidade de folhas na rvore, maior o nvel.

O modo com que a WFA define uma imagem deve ser interpretado como: cada estado i na WFA

corresponde a alguma subimagem da imagem, com cada elemento do vetor F, F(i) sendo a mdia em

escala de cinza dessa subimagem. Um estado em particular corresponde imagem por completo, e o

vetor I indica que estado esse. Se o estado k corresponde imagem por inteiro, ento: I(k) = 1, e

0,4 0,5 1 0,5 0,1 0 1 0,9 0 0.8 0,8 0 0,8 0,8 0,7 0,1

0,5 0,2 0,8 0,6

2,1 4

0

3 2

3

0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1

35

I(l)=0, l k. O peso das transies indica como os quadrantes de uma subimagem so expressos como

uma combinao linear de outra subimagem (possivelmente incluindo a subimagem que o quadrante

pertence), com os pesos especificando os coeficientes das combinaes lineares, e os smbolos de

entrada especificando o quadrante em questo, como na equao 2.3, repetida em 3.8 e 3.11:

( ) ( ) ( ) ( ) naaaai niWiWiW ,...2,1, 21 +++= (3.12)

Em que i a imagem associada ao estado i e ( )ai o quadrante a da imagem i , para i = 1,2,,n. Assim, o quadrante da imagem i uma combinao linear das imagens 1 , 2 , n com

coeficientes dados pelo ndice i da linha da matriz Wa.

Considere como exemplo a WFA mostrada na Figura 3.12. Essa WFA especificada pelas

matrizes da Figura 3.11:

[ ] ,2/1

2/1,01

== FI

.10

12/1,

10

2/12/1

,10

02/1,

10

2/12/1

32

10

=

=

=

=

WW

WW

Figura 3.11 Matrizes I, F e W para o grfico de transio da Figura 3.12

Essa WFA , na verdade, uma codificao da escala linear de cinza da funo h(x,y) = x + y.

A Figura 3.12 a imagem que est codificada por essa funo, ela mostrada na

resoluo 128 x 128. Sabendo que a distribuio inicial I = [1 0], 1 (a imagem do estado 1)

tambm h (a imagem inteira). O estado 1, 1 , e o estado 2, representado pela imagem 2 so as

Figures 3.12 e Figura 3.13, respectivamente. ( 2 tem para todos os valores de entrada de sua funo, 1

como sada). O vetor de estados F, tem a mdia da escala em cinza de 1 e de 2 , para ambos 1/2.

36

Figura 3.12 Estado 1 Figura 3.13 Estado 2

A informao contida na primeira linha das matrizes W0, W1, W2 e W3 so ilustradas na Figura

3.14: a primeira linha de W0 nos diz que o quadrante 0 de toda a imagem igual a imagem completa

com sua escala de cinza uniformemente multiplicado por , como na equao 3.13:

( ) 111 21 =

(3.13)

De acordo com a primeira linha de W1 e W2 os dois quadrantes 1 e 2 da imagem inteira podem

ser expressos pela combinao linear na equao 3.14:

( ) ( ) 212101 21

2

1 +== (3.14)

E o quadrante 3 de f=1 descrito pela equao3.15:

( ) 2131 21 +=

(3.15)

As segundas linhas de W0, W1, W2 e W3 indicam que os quatro quadrantes de 2 so idnticos a

2 . Note que 2 possui perfeita auto similaridade (uma imagem completamente descrita por ela mesma)

WFA uma maneira geral de descrever fractais.

37

Figura 3.14 Relao entre os estados

Uma imagem descrita por WFA pode ser decodificada em qualquer resoluo 2n x 2n.

Decodificando a imagem definida pela WFA no exemplo dado na resoluo 4 x 4; o endereo dos pixels

so mostrados na Tabela 3.7. A escala em cinza computada como em 3.16 e em 3.17:

[ ]8

1

2/1

2/1

10

021

10

02101)11( 11 =

== FWIWf

(3.16)

[ ]4

1

2/1

2/1

10

2121

10

02101)10( 01 =

== FWIWf

(3.17)

Seguindo o mesmo raciocnio para (00), ..., (33). O resultado da imagem decodificada pode

ser ilustrado pela Tabela 3.7. Assim, como nas imagens codificadas por fractais, imagens codificadas

por WFA possuem independncia de resoluo. Verificando, assim, que a compresso por fractais e por

WFA possuem similaridades.

=

=

=

+

+

( ) ( )2101 =

( )11 1

1

1

2

( )31 2

38

Tabela 3.7 Imagem decodificada na resoluo 4x4

1 5/8 3/4 7/8

3/8 1 5/8 3/4

1/4 3/8 1 5/8

1/8 1/4 3/8 1

Depois deste exemplo grfico, apresenta-se um exemplo numrico. Considere uma imagem em

escala de cinza, em uma dimenso qualquer, que possui os seguintes valores em seus quadrantes

(Tabela 3.8):

Tabela 3.8 Exemplo numrico

0,5 0,25

0,75 1

Para codific-la utilizando o algoritmo WFA, criamos o estado 1, correspondente a imagem

inteira, que a prpria imagem (Tabela 3.9).

Tabela 3.9 - Estado 1

0,5 0,25

0,75 1

O valor da funo , para a imagem inteira 3.18:

625,04

25,0175,0 0,5 1) (estado fw =+++==

(3.18)

Calculando as matrizes de transio W, para o estado em questo em 3.19, 3.20, 3.21 e 3.22:

[ ]8,0625,0

5,0

1

100 =

=

=estado

DoEstadowW

(3.19)

[ ]2,1625,0

75,0

1

111 =

=

=estado

DoEstadowW

(3.20)

[ ]6,1625,0

1

1

122 =

=

=estado

DoEstadowW

(3.21)

39

[ ]4,0625,0

25,0

1

133 =

=

=estado

DoEstadowW

(3.22)

Os vetores F e I ficam iguais a 3.23:

[ ] [ ],625,0,1 == FI (3.23)

Agora, recompondo a imagem utilizando as matrizes dadas, tem-se 3.24, 3.25, 3.26 e 3.27:

[ ][ ][ ] 5,0625,08,01)0( 0 === FIWf (3.24) [ ][ ][ ] 75,0625,02,11)1( 1 === FIWf (3.25) [ ][ ][ ] 1625,06,11)2( 2 === FIWf (3.26) [ ][ ][ ] 25,0625,04,01)3( 3 === FIWf (3.27)

A imagem foi recriada com sucesso, veja a Tabela 3.10 e Tabela 3.11.

Tabela 3.10 - Valores da imagem reconstituda

f(0) f(3)

f(1) f(2)

Tabela 3.11 - Imagem reconstituda

0,5 0,25

0,75 1

Na Figura 3.15, apresentada a mquina de estados para a soluo:

Figura 3.15 Mquina de estados4

4 O resultado aqui apresentado parte do princpio que no necessrio fazer um estado que represente a imagem inteira. A soluo do algoritmo implementado para a figura squares, que ser apresentada mais adiante nos resultados, apresentar dois estados , pois o algoritmo presume que necessrio criar um estado que represente a imagem inteira.

1;0,625

0;0,8 1;1,2

2;1,6 3;0,4

40

Captulo 4 Desenvolvimento do Algoritmo da WFA

Neste captulo, esto documentados todos os arquivos implementados no Matlab que fazem

parte da soluo do codificador e decodificador WFA, desenvolvidos durante este projeto final. A

inteno explicar o algoritmo WFA junto com a soluo para melhor entendimento.

4.1. Codificador WFA

O codificador WFA tem como principais desafios: descobrir a combinao linear entre os

estados, fazer com que a quantidade de estados seja mnima, e que a WFA proposta reconstitua a

imagem com qualidade.

A primeira e maior dificuldade encontrada foi achar as matrizes de transio W. A soluo se

deu da seguinte forma: os estados, representados pelos seus ns folhas da rvore quadtree, so

colocados como colunas de uma matriz. Todos os estados esto na mesma resoluo, ou seja, contm o

mesmo nmero de folhas, para tanto, se necessrio feito o upsample ou downsample. Constituda a

matriz com todos os estados representados em colunas, analisa-se um desses estados. O estado em

anlise decomposto em quadtree, e ento representado por quatro quadrantes: Q0, Q1, Q2, Q3. Em

cada quadrante, feito o upsample ou downsample, para que eles tenham a mesma resoluo da matriz

de estados, e cada quadrante origina uma matriz linha. As matrizes W so calculadas linha por linha,

indicando a transio a partir do quadrante do estado em anlise para todos os estados. No clculo,

utilizada a funo do Matlab chamada pinv(.). A Figura 4.1 ilustra todo esse processo. A equao 4.1

a equao utilizada no clculo das matrizes W, onde a representa o quadrante em anlise e i o estado em

anlise.

EstadoiQa

estados

de

matriz

pinviWa _*:),(

= (4.1)

41

Figura 4.1 Calculando valores da matriz de transio W

Com as matrizes W calculadas, cabe a pergunta: O estado criado agregou na qualidade de

reconstituio da imagem? O custo, em nmero de bits compensa ou no a adio desse estado?. Esse

questionamento feito comparando-se a qualidade de reconstruo das matrizes F, I e W com o estado

novo, com a anterior, sem o estado novo, ou seja, a imagem decodificada e comparada.

Estado 1

Estado 2

Estado 3

1101

0000

1111 1111 1111 1111 0000 0000 0000 0000 0000 11111101 0000 0000 00001000 0000

0000

1111 2222

3333

0000 1111 2222 3333

0000 1111 2222 3333 0000 1111 2222 3333 0000 1111 2222 3333 0000 1111 2222 3333

Imagem em anlise

Quadrante em anlise:

Q0 do estado 4

1111

Upsample ou Downsample

1111 0000 0111 1111

0000

1111 2222

3333

0000 1111 2222 3333

Estado 4

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0,75 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0,75 1 1 1 1 1 1 1

E S T A D O 3

E S T A D O 2

E S T A D O 1

E S T AD O 4

Matriz coluna de estados

Quadrante em anlise: W0

1111 1111 1111 1111 W0 (4,:) = pinv *

Quadrante em anlise: W0

Estado em anlise: 4

Quadrante Q0 do Estado 4

42

Essa comparao feita utilizando o MSE do PSNR apresentado na seo 2.10, adicionado, a

esse erro, um peso multiplicado quantidade de bits utilizada na mquina de estados. Como na equao

4.2:

tsDaWFAnmeroDeBiHficadaagemDecodialagemOriginMSECustoDaWFA *)Im,(Im += (4.2)

O valor timo para o peso H varia de acordo com a imagem que est sendo codificada. ele

quem define a qualidade da WFA e seu nmero de estados. H, em seu valor timo, d a WFA a maior

qualidade para o menor nmero de estados. Duas observaes podem ser feitas quanto soluo

apresentada neste projeto final (CULIK II e KARI, 1993):

1. Mesmo que a WFA produzida pelo algoritmo seja mnimo em nmero de estados, ele

no necessariamente mnimo em nmero de arestas5. Geralmente, a mesma imagem

pode ser gerada por diversas WFAs, todas tendo o nmero mnimo de estados, porm

variando bastante em termos de arestas. Achar um algoritmo que produza um nmero

mnimo de arestas sem sacrificar a eficincia do algoritmo um importante problema.

2. No uma boa estratgia requerer que o algoritmo produza uma WFA capaz de recriar a

imagem original. Qualquer imagem de resoluo finita pode ser reconstituda

perfeitamente por um WFA, contudo, na maioria dos casos, o autmato vai ser muito

grande. Entretanto, se for permitido que a imagem seja reproduzida com algum erro,

uma soluo bem menor geralmente encontrada. Como achar um autmato que

reconstrua a imagem de forma mais aproximada da original o outro problema.

O peso H responsvel por encontrar a quantidade mnima de estados. Quanto ao nmero de

arestas, alm de H, o que varia a sua qualidade so os estados escolhidos para compor a WFA. Os

estados so escolhidos de acordo com o tipo de varredura feita pelo algoritmo buscando e analisando os

quadrantes da imagem. Foram desenvolvidos trs codificadores WFA que apenas diferenciam entre si

no tipo de varredura feita por eles na imagem, e em todos eles pode-se considerar o uso de estados

iniciais.

5 Aresta a linha que liga dois ns de uma rvore, no nosso caso a rvore criada a partir da imagem decodificada.

43

O primeiro estado a ser analisado, sempre, no importa a varredura utilizada, o estado que

representa a imagem inteira. A varredura por quadrante, Figura 4.2, desce na imagem executando a

WFA por quadrante, descendo at o pixel, antes de passar para o prximo quadrante. A Figura 4.3

tambm uma varredura por quadrante, s que ela visita o quadrante antes de descer at o pixel. J a

varredura por quadrante invertida, mostrada na Figura 4.4, visita todos os ns terminados em 0, depois

todos os ns terminados em 1 e assim por diante. A varredura up-down executa o algoritmo do nvel

mais alto para o nvel mais profundo da rvore, a Figura 4.5 ilustra o processo. J a varredura down-up

executa o algoritmo do nvel mais profundo ao nvel mais alto, ela est apresentada na Figura 4.6.

Figura 4.2Varredura por quadrante down-up (addressFunc1)

Figura 4.3 Varredura por quadrante up-down (addressFunc2)

0

0 1 2 3

0

0 1

0 1 2 3

0

(...)

0 1 2 3

0

2

0 1 2 3

0

3

1

0

1 2 3

0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3

0

0 1

0 1 2 3

0

(...)

(...)

(...)

(...)

44

Figura 4.4 Varredura por quadrante invertida (addressFunc3)

Figura 4.5 Varredura up-down (addressFunc4)

Figura 4.6 Varredura down-up (addressFunc5)

0

1 2

3

0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3

0

1 2

3

0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3

0

1 2

3

0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3

45

A quantidade de estados iniciais pode ser escolhida pelo usurio, e eles so derivados da funo

cosseno. No foi feito nenhum estudo sobre qual melhor funo para os estados iniciais, a funo

cosseno foi escolhida baseada na bibliografia (MULLER, 2005).

4.2. Decodificador WFA

O decodificador WFA muito simples, ele s precisa multiplicar as matrizes para cada pixel da

imagem decodificada. Ele recursivo e ser detalhado neste captulo na sesso I.10.

4.3. Codificador/Decodificador WFA Combinado ao Codificador/Decodificador

Wavelet

Com o intuito de verificar se a WFA suporta a manipulao de imagens, combinou-se a WFA

com a funo de Matlab dwt2 e idwt2, respectivamente a transformada wavelet discreta de primeiro

nvel para duas dimenses, e a transformada inversa wavelet de primeiro nvel, tambm para duas

dimenses. Por manipulao de imagens entende-se qualquer transformao matemtica aplicada na

imagem, um operador linear (filtros, wavelet, etc.), por exemplo, sendo que a transformao WFA pode

ser aplicada diretamente na imagem codificada, sem a necessidade de regener-la. A Figura 4.7 indica

como se configura o novo codificador combinando wavelet com WFA.

Figura 4.7 Combinao codificao/decodificao WFA e wavelet.

Arquivo Imagem em

formato bitmap


W2, W3, I e F


W2, W3, I e F

Imagem


Encode wavelet

Encode WFA

Decode WFA

Decode wavelet

46

Captulo 5 Anlise dos Resultados

A inteno deste projeto final foi o desenvolvimento de um algoritmo de codificao e

decodificao WFA. Houve compromisso com a compresso de dados, porm ele no foi alcanado

satisfatoriamente. Sabendo disso, a anlise dos resultados se dar na otimizao do algoritmo e na

qualidade dos resultados.

Para efeito de informao, pode-se verificar que os dados codificados de uma imagem sob o

algoritmo WFA desenvolvido aqui, alguma das vezes utilizou mais bytes que a imagem original. Um

exemplo disso seriam os exemplos numricos do Captulo 3.

5.1. Consideraes sobre a Varivel G

Existe uma varivel que deve ser definida na codificao do algoritmo, essa varivel define em

que resoluo os clculos sero feitos, chamada de G. Dentro do algoritmo, ela o expoente de 2, ou

seja, definem as potncia de dois das resolues. Quanto maior a potncia, maior vai ser a quantidade

de linhas e colunas nas matrizes, e assim maior vai ser a complexidade do algoritmo.

A criao dessa varivel deu-se pelo fato de algumas codificaes chegarem a levar mais de um

dia para serem executadas, resolveu-se ento, diminuir o tamanho das matrizes e verificar o que

aconteceria. Depois de se fazer alguns ensaios, pode-se verificar que para a WFA, custo maior, no

necessariamente significa preciso ou qualidade mais apurada. Existe uma combinao tima G que

capaz de fornecer o melhor custo e o melhor resultado.

G a varivel que define em qual resoluo o clculo da combinao linear entre os estados,

para acrscimo de um estado novo, ser feito, esse clculo tem como resultado o array de matrizes ou

clula WTemp.

statesAsLevelInColumns(:,NewStateNumber)=getImageAsLevelInFwTree([stateAddress{NewStateNumber}],

2^((maxlevel-1)*G))';

WTemp{1} = zeros(NewStateNumber, NewStateNumber);




47

for stateLineNumber=1:1:NewStateNumber

NewLineInW0Matrix=pinv(statesAsLevelInColumns)*getImageAsLevelInFwTree([stateAddress{stateLineNu

mber} 0], 2^((maxlevel-1)*G))';







WTemp{1}(stateLineNumber,:) = NewLineInW0Matrix;




End Figura 5.1 Calculando as novas matrizes W pela combinao linear na resoluo 2^G

5.2. Consideraes sobre a Varivel H

A varivel H, definida pelo usurio, dimensiona o peso da quantidade de bits das matrizes W no

clculo do custo da WFA. Quando menor o valor de H, menos determinante a quantidade de bits de W

na definio do custo da WFA.

HtesnmeroDeByEstadoErroDoNovoovoEstadocustoDeUmN *8*+=

(5.1)

Os valores de H geralmente so muito pequenos, sempre variando entre 0,00001 a 0,0001 nos

resultados aqui produzidos.

5.3. Consideraes sobre as Funes Wavelets

As funes Haar, Symlets, BiorSplines e ReverseBior fornecidas pelo Matlab foram escolhidas

para a gerao de resultados por serem filtros que possuem transformada inversa wavelet. As outras

funes oferecidas pelo Matlab no possuem essa propriedade.

5.4. Consideraes sobre Erros e Comparaes

Na execuo do algoritmo, h a escolha entre o acrscimo de um estado novo s matrizes W ou

a manuteno da matriz W atual. Para tanto compara-se o resultado de das novas matrizes W com o

48

estado novo, colocadas em WTemp, e as matrizes W atuais. Regenera-se a subimagem utilizando as

WTemp e W, o que nos gera duas imagens. , ento, comparado o custo de se refazer a imagem inteira

por W e por WTemp.

Alm disso, custo calculado pelo erro (MSE) somado a quantidade de bits vezes o peso H.

Essa comparao feita na escolha da matriz W a ser utilizada. O MSE e o peso H so determinantes

para o resultado do algoritmo.

5.5. Consideraes sobre as Configuraes da Mquina Utilizada

Nos resultados apresenta-se a quantidade de tempo em que cada imagem foi processada. Para

que os resultados possam ser comparados e faam sentido necessrio saber a configurao da mquina

em que se fez a codificao e a decodificao. A verso Matlab utilizada foi a 7.0,0,19920 (R14)

rodando sobre Windows XP service Pack 3. O hardware utilizado foi um HP Compaq 8510w que

possui processador Intel Core Duo T9300, com velocidade de 2.5 GH

Documents

Projeto Final - Andressa Kalil - monografias.poli.ufrj.brmonografias.poli.ufrj.br/monografias/monopoli10002272.… · · 2011-09-26Universidade Federal do Rio de Janeiro CODIFICAÇÃO