Compressão de Imagens Usando a Função de Peano e a ... · A interface gráﬁca, os programas de processamento de imagens via Função de Peano e a Transformada Wavelet 1D foram

Universidade Federal do Rio Grande do Norte - UFRN

Programa de Pós-Graduação em Ciência e Engenharia do Petróleo - PPGCEP

DISSERTAÇÃO DE MESTRADO

C O M P R E S S Ã O D E I M A G E N S U S A N D O A F U N Ç Ã O D EP E A N O E A T R A N S F O R M A D A WAV E L E T 1 D

daniel teixeira dos santos

Natal-RN, Abril 2012

[ 6 de julho de 2012 at 11:24 ]

C O M P R E S S Ã O D E I M A G E N S U S A N D O A F U N Ç Ã O D EP E A N O E A T R A N S F O R M A D A WAV E L E T 1 D

daniel teixeira dos santos

Orientador: Prof. Dr. Joaquim Elias de Freitas

Natal-RN, Abril 2012

[ 6 de julho de 2012 at 11:24 ]

iii

[ 6 de julho de 2012 at 11:24 ]

Daniel Teixeira dos Santos

C O M P R E S S Ã O D E I M A G E N S U S A N D O A F U N Ç Ã O D E P E A N O E AT R A N S F O R M A D A WAV E L E T 1 D

Dissertação de Mestrado apresentada ao Programade Pós-Graduação em Ciência e Engenharia de Pe-tróleo - PPGCEP, da Universidade Federal do RioGrande do Norte, como parte dos requisitos para ob-tenção do título de Mestre em Ciência e Engenhariade Petróleo.

Aprovado em: de de 2012.

Prof. Dr. Joaquim Elias de FreitasOrientador - UFRN

Prof. Dr. Luciano Rodrigues da SilvaMembro Interno - UFRN

Dr. Samyr Silva Bezerra JácomeMembro Externo à Instituição

[ 6 de julho de 2012 at 11:24 ]

D E D I C AT Ó R I A

Dedico esta dissertação aos meus Pais, Luiz Manoel dos Santos e Josete Teixeira dos Santos peloamor e carinho com que me educaram, principalmente pela liberdade e o apoio que me deram na carreiraacadêmica que escolhi.À meu irmão Hamilton Teixeira dos Santos, pelo companheirismo, entendimento e amizade;E a todos os meus amigos.

v

[ 6 de julho de 2012 at 11:24 ]

TEIXEIRA DOS SANTOS, Daniel -Compressão de Imagens Usando a Função de Peano e aTransformada Wavelet 1D. Dissertação de Mestrado, UFRN, Programa de Pós-Graduação emCiência e Engenharia de Petróleo. Área de Concentração: Pesquisa e Desenvolvimento em Ciênciae Engenharia de Petróleo. Linha de Pesquisa: Física Aplicada à Exploração e à Produção dePetróleo e Gás Natural, Natal RN, Brasil.

Orientador: Prof. Dr. Joaquim Elias de Freitas.

R E S U M O

Neste trabalho, apresenta-se a importância da compressão de imagens para a indústria depetróleo, sabe-se que o processamento e armazenamento de imagens é sempre um desafio nasgrandes empresas de petróleo, para otimizar o tempo de armazenamento e armazenar umnúmero máximo de imagens e dados. É exposto algumas ferramentas para o processamento earmazenamento de imagens no domínio wavelet. A proposta apresentada baseia-se na Funçãode Peano e na transformada wavelet 1D. O sistema de armazenamento tem como objetivo aotimização do espaço computacional, tanto para o armazenamento como para transmissão deimagens. Sendo necessário para isso, a aplicação da Função de Peano para linearizar as imagenscom máxima concentração de pontos vizinhos e a transformada wavelet 1D para decompó-la.Estas aplicações permitem extrair informações relevantes para o armazenamento de uma imagemcom um menor custo computacional e com uma margem de erro muito pequena quando secompara as imagens, original e processada, ou seja, há pouca perda de qualidade ao aplicar osistema de processamento apresentado. Os resultados obtidos a partir das informações extraídasdas imagens são apresentados numa interface gráfica. É através da interface gráfica que o usuáriovisualiza as imagens e analisa os resultados do programa diretamente na tela do computador sema preocupação de lidar com os códigos fontes. A interface gráfica, os programas de processamentode imagens via Função de Peano e a Transformada Wavelet 1D foram desenvolvidos em linguagemjava, possibilitando uma troca direta de informações entre eles e o usuário.

Palavras-chave: Processamento de imagens, Função de Peano, Transformada Wavelet 1D,Compressão de Imagens.

vi

[ 6 de julho de 2012 at 11:24 ]

A B S T R A C T

In this work, spoke about the importance of image compression for the industry, it is known thatprocessing and image storage is always a challenge in petrobrás to optimize the storage time andstore a maximum number of images and data. We present an interactive system for processingand storing images in the wavelet domain and an interface for digital image processing. Theproposal is based on the Peano function and wavelet transform in 1D. The storage system aimsto optimize the computational space, both for storage and for transmission of images. Beingnecessary to the application of the Peano function to linearize the images and the 1D wavelettransform to decompose it. These applications allow you to extract relevant information for thestorage of an image with a lower computational cost and with a very small margin of error whencomparing the images, original and processed, ie, there is little loss of quality when applyingthe processing system presented . The results obtained from the information extracted from theimages are displayed in a graphical interface. It is through the graphical user interface that theuser uses the files to view and analyze the results of the programs directly on the computerscreen without the worry of dealing with the source code. The graphical user interface, programsfor image processing via Peano Function and Wavelet Transform 1D, were developed in Javalanguage, allowing a direct exchange of information between them and the user.

Keywords: Image Processing, fFnction Peano, 1D Wavelet Transform, Image Compression.

vii

[ 6 de julho de 2012 at 11:24 ]

A G R A D E C I M E N T O S

Primeiramente dedico meus agradecimentos à Deus, por me proporcionar a realização destetrabalho. Agradeço também a todos que colaboraram no desenvolvimento desta dissertação:principalmente meu Orientador Professor Dr. Joaquim Elias de Freitas pela valiosa orientação,dedicação e incentivo; aos membros da banca Professor Dr. Luciano Rodrigues da Silva eProfessor Dr. Samyr Silva Bezerra Jácome que muito contribuíram para a melhoria do trabalho;aos meus colegas e amigos de trabalho Daniel Ecco e Israel Araújo que influenciaram diretamenteno desenvolvimento do software; aos amigos sobreviventes da graduação: Dayvid Marques,José Carlos, Marconio da Silva e Thiago Valentim; aos amigos de outras turmas: Ana Paula,Elvis Sampaio, Hérica Priscila e Mariana Barbosa; Aos grandes companheiros: Isaque Nicácio,Graziela Mariano, Elielson Abrantes, Hianto Almeida e Iasmin Bezerra; a todos os meus alunose ex alunos; aos professores da pós-graduação: Liacir Lucena e Sílvio José; aos professores docurso de matemática: André Gustavo, Viviane Simioli, Ronaldo Freire, Rubens Leão, MarceloGomes, Grabriela Lucheze, Gurgel de Melo, Sílvio José, Benedito Tadeu e José Querginaldo; aoPPGCEP/UFRN e a todo o corpo docente, técnico e administrativo que contribuíram de algumaforma na realização deste trabalho e a CAPES Agência Financiadora.

viii

[ 6 de julho de 2012 at 11:24 ]

S U M Á R I O

Lista de Figuras xi

i parte i: introdução 1

1 introdução 3

1.1 Objetivos e Contribuições 5

ii parte ii: processamento de imagens 6

2 processamento de imagens 8

2.1 Imagem Digital 10

2.2 Armazenamento de Imagem Digital 12

2.3 Etapas do Processamento de Imagens 13

iii parte iii : teoria wavelet 17

3 teoria wavelet 19

3.1 Wavelets 19

3.2 Transformada Wavelet (TW) 25

3.2.1 Transformada Wavelet Contínua (TWC) 25

3.2.2 Função Wavelet Mãe 26

3.3 Transformada Wavelet Contínua Inversa (TWCI) 26

3.4 Transformada Wavelet Discreta (TWD) 26

3.5 Transformada Wavelet Discreta Inversa (TWDI) 27

3.6 Análise de Multirresolução (AMR) 28

3.7 Transformada Wavelet Discreta Bidimensional (TWD Bidimensional) 30

3.7.1 Um exemplo da aplicação da Transformada Wavelet de Haar na Compressãode um Sinal 31

3.7.2 Transformada 1D de Haar 33

iv parte iv : funções de peano 36

4 funções de peano de [0, 1] em [0, 1]n 38

4.1 Família de Funções de Peano 38

4.1.1 Uma Restrição Discreta importante da família de funções de Peano 43

4.1.2 Funções de Peano do Círculo em [0, 1]n 44

4.1.3 Área de Preenchimento da Função de Peano e Mudança de Base 46

4.1.4 Aprimoramento da Compressão para Imagens 512x512 47

v parte v : função de peano e wavelet 1d em processamento de imagens e

uma interface gráfica para o usário 49

5 função de peano e wavelet 1d em processamento de imagens e uma in-terface gráfica para o usário 51

5.1 Compressão de Imagens 51

5.2 Sistema de Armazenamento de Imagens através da Transformada Wavelet 52

5.2.1 Codificação da Imagem Comprimida 52

5.2.2 Decodificação da Imagem Comprimida 53

5.3 Função de Peano e Wavelet 1D em Processamento de Imagens e uma InterfaceGráfica para o Usuário 54

ix

[ 6 de julho de 2012 at 11:24 ]

sumário x

5.4 Interfaces Gráficas para o Sistema de Armazenamento de Imagens Comprimi-das 56

vi parte vi : conclusão 67

6 conclusão 69

referências bibliográficas 70

[ 6 de julho de 2012 at 11:24 ]

L I S TA D E F I G U R A S

Figura 1 (a) Imagem sísmica; (b) Imagem de geoprocessamento 10

Figura 2 (a) Imagem de dimensão 512 x 512 pixels; (b) Imagem de dimensão 256

x 256 pixels; (c) Imagem de dimensão 128 x 128 pixels; (d) Imagem dedimensão 64 x 64 pixels. 11

Figura 3 (a) Ponto indicado sobre o olho da Lenna (à esquerda); (b) Matriz de pixelsem uma região de interesse de 10 x 10 pixels em torno do ponto indicado (àdireita), onde cada elemento representa a intensidade na região indicadaem (a); (c) Nível de quantificação. 11

Figura 4 (a) Imagem adquirida da Orquídea; (b) Dispositivo de captura; (c) Sinaldigital. 13

Figura 5 Pré-processamento de uma Imagem. 14

Figura 6 (a) Ampliação de uma região da imagem da orquídea; (b) Valores deintensidade na região selecionada. 14

Figura 7 (a) Reconhecimento; (b) Interpretação 15

Figura 8 (a) Imagem original; (b) Imagem contaminada por ruído branco; (c) Imagemapós a eliminação do ruído utilizando a Transformada Wavelet. 16

Figura 9 (a) Função escala de Haar; (b) Função Wavelet de Haar. 21

Figura 10 Função wavelet de Morlet. 21

Figura 11 Matriz dos coeficientes da wavelet de Daubechies (DAUB4) na decomposição de um sinal. 23

Figura 12 (a) Função escala de Daubechies; (b) Função Wavelet de Daubechies. 23

Figura 13 Função Escala de Meyer; Função Wavelet de Meyer. 25

Figura 14 Bandas de frequência entre Vj e Vj+1 29

Figura 15 Decomposição padrão de uma imagem. 30

Figura 16 Decomposição não padrão de uma imagem. 31

Figura 17 (a) Representação gráfica do vetor <1, 1, 1, 1>; (b) Representação gráfica dovetor <1, 1, -1, -1>. 32

Figura 18 (a) Representação gráfica do vetor <1, -1, 0, 0>; (b) Representação gráfica dovetor <0, 0, 1, -1>. 32

Figura 19 Algorítmo para transformar um vetor de entrada em base Wavelets 34

Figura 20 Gráfico gerado através da tabela de pontos gerada pela função f2m. 44

Figura 21 Curvas de Peano gerados pela função (4.4) 47

Figura 22 Curva de Peano discretizada 55

Figura 23 Interface Gráfica 56

Figura 24 Histograma dos coeficientes 58

Figura 25 Seleção dos coeficientes a serem processados 59

Figura 26 Interface Pós-Processamento 60

Figura 27 Composição das imagens selecionadas 61

Figura 28 Interface Gráfica com aprimoramento ativo 63

Figura 29 Seleção da faixa de coeficientes a serem processados 64

Figura 30 Interface pós-processamento 65

xi

[ 6 de julho de 2012 at 11:24 ]

Lista de Figuras xii

Figura 31 (a) Imagem pós-processamento; (b) Imagem original 66

[ 6 de julho de 2012 at 11:24 ]

A B R E V I AT U R A S E S I G L A S

TW – Transformada Wavelet

TWC – Transformada Wavelet Contínua

TWCI – Transformada Wavelet Contínua Inversa

TWD – Transformada Wavelet Discreta

TWDI – Transformada Wavelet Discreta Inversa

AMR – Análise de Multiresolução

xiii

[ 6 de julho de 2012 at 11:24 ]

Parte I

PA RT E I : I N T R O D U Ç Ã O

[ 6 de julho de 2012 at 11:24 ]

Capítulo1I N T R O D U Ç Ã O

[ 6 de julho de 2012 at 11:24 ]

1I N T R O D U Ç Ã O

A indústria do petróleo, assim como tantos outros ramos da sociedade produtiva, está sempreà procura de novas técnicas, afim de otimizar seus processos de trabalho Mochizuki [22]. Estaotimização, como não poderia deixar de ser, leva sempre em consideração a redução de tempo ecustos das operações, aliada ao aumento da produtividade.

A compressão de dados, tema de nosso trabalho, vem contemplar estas necessidades dentroda indústria do petróleo, além de descortinar outras possibilidades, como a integração de váriosgrupos de trabalho.

As atividades de obtenção de imagens terrestres, sísmicas e de subsolo, que fazem parte de umtodo, passam a integrar-se afim de tornar o resultado sobre a procura de uma jazida mais precisae ainda contempla a procura da melhor localização de perfuração de um poço de petróleo, afimde aumentar a produção nas companhias petrolíferas.

Na literatura de processamento de sinais, uma função é chamada de sinal J. Gomes [17]. Ofato dos sinais, em geral, serem fontes de informações, as imagens essencialmente representadasem forma digital, são tipos de sinais cada vez mais presentes em nosso cotidiano, e a cadadia tem despertado a necessidade de processamentos indispensáveis, desde as imagens para omais simples entretenimento até as aplicações mais importantes, por exemplo, imagens sísmicasJ. Portilla[18].

Através do processamento de imagens, é possível que informações sejam disponibilizadas parauma determinada aplicação, como por exemplo, a localização e a gemetria de uma jazida depetróleo através de uma imagem sísmica, a presença de lençóis freáticos no subsolo, dentre outros.

A grande variedade de tipos de sinais gerados e os diversos métodos de obtê-los, muitas vezesacarretam perda de qualidade, pois a maioria dos sinais é contaminada por algum tipo de ruído(Ground Roll, no caso de imagens sísmicas). Por exemplo, ao adquirir uma imagem, o meioem que ela se encontra ou o dispositivo que a captura, pode fornecer uma imagem de baixaqualidade, com aspectos que comprometem uma boa análise por parte do observador.

O processamento de sinais visa, de modo geral, melhorar a qualidade de um sinal para possí-veis análises.

As companhias petrolíferas tem como objetivo a obtenção de várias imagens de uma mesmazona terrestre ou de imagens sísmicas, sem prejudicar o tempo nas transferências destas, o espaçode armazenamento dos computadores e a qualidade das imagens.

3

[ 6 de julho de 2012 at 11:24 ]

4

Uma das aplicações do processamento de sinais é a compressão, com o objetivo de uma trans-missão ou armazenamentos eficientes, com baixo custo computacional. A compressão geralmentese baseia na eliminação de redundâncias do sinal através do uso de alguma transformada, geral-mente transformadas integrais E. J. Stollnits[12].

Para efeitos de compressão, a Transformada Wavelet é uma ferramenta que disponibilizaalgoritmos rápidos, fundamentais para a compressão de imagens, ou para remoção de ruídos.Quando um sinal é analisado com a Transformada Wavelet, obtêm-se informações tanto nodomínio do tempo quanto no domínio da frequência, isto é, é possível determinar quando começae quando termina um determinado evento, este é o principal objetivo da Transformada Wavelet.

As wavelets são ondas pequenas, com determinadas propriedades, que as tornam adequadaspara decomposição de uma determinada função em outras funções M. Misiti[20].

A análise de multiresolução (ou autoresolução) contempla o processo de Compressão de Dadosusando a Transformada Wavelet que, ao ser aplicada em um sinal, evidencia seus detalhes,tornando possível a análise dos coeficientes Wavelets Daubechies[9].

Dentre as aplicações envolvendo imagens nas indústria de petróleo, está a compressão, poiscom o advento da internet e com a necessidade da criação diária de banco de dados, imagens sãotransmitidas a todo o momento, podendo causar lentidão no sistema no qual elas se encontramJ. F. Silvia[16].

Como objetivo principal, a compressão de imagens consiste em eliminar coeficientes dessaimagem que não comprometam a sua reconstrução ou que causem um erro mínimo entre aimagem original e a imagem processada. Esta eliminação não pode ser feita diretamente naimagem, para isso é aplicado algum tipo de transformada para que o sinal seja analisado nodomínio transformado, evidenciando seus detalhes assim como suas redundâncias.

Após a compressão, são armazenados apenas os coeficientes que não foram eliminados naimagem transformada e as informações que possibilitem a reconstrução da imagem através dessescoeficientes.

Um ponto negativo ao se aplicar a Transformada Wavelet em um sinal, é a geração de pontosde descontinuidade devido aos problemas de valores de contorno. Nosso objetivo, é linearizar aimagem através da função de Peano e aplicar a transformada wavelet 1D, evitando, desta forma,este problema.

Outra questão tão importante quanto às técnicas que envolvem o processamento de imagens é acriação de dispositivos que permitam o acesso rápido e fácil a qualquer usuário de computadores,de forma que o mesmo usuário, independentemente de seu nível de conhecimento computacional,possa manipular imagens e processá-las. Uma forma de resolver esse problema é a criação deinterfaces que permitam ao usuário o acesso ao processamento de imagens sem se preocupar coma complexidade computacional que está por trás do processo.

[ 6 de julho de 2012 at 11:24 ]

1.1 objetivos e contribuições 5

1.1 objetivos e contribuições

Este trabalho apresenta uma nova metodologia de armazenamento de imagens que consistena aplicação da Função de Peano para linearizar a imagens e da Transformada Wavelet 1Dpara decompô-las. Estas ferramentas atuarão juntas com o objetivo de conseguir uma economiaconsiderável no espaço computacional e corrigir os erros das condições de contorno encontradosao se aplicar a Transformada Wavelet diretamente na imagem.

A interface gráfica tem como principal objetivo o acesso ao processamento de imagens, deusuários que não tem domínio de linguagens de programação, mas que necessitam manusearimagens. Caso contrário, também é possível apenas lidar com os códigos fontes para eventuaismodificações e melhoramento no processamento.

[ 6 de julho de 2012 at 11:24 ]

Parte II

PA RT E I I : P R O C E S S A M E N T O D E I M A G E N S

[ 6 de julho de 2012 at 11:24 ]

Capítulo2P R O C E S S A M E N T O D E I M A G E N S

[ 6 de julho de 2012 at 11:24 ]

2P R O C E S S A M E N T O D E I M A G E N S

O processamento digital de imagens é uma subárea do processamento de sinais que consistena execução de operações matemáticas, com objetivo de extrair informações que geralmenterepresentam um fenômeno a ser estudado de forma específica. No processamento de umaimagem são realizados milhares de cálculos de forma rápida e segura para que o observador ouo computador possam analisar ou realçar de forma precisa estas informações.

A primeira aplicação da área de processamento de imagens foi na década de 20, na tentativade aprimorar imagens digitalizadas de um jornal para transmissão, entre Londres e Nova Iorque.O tempo necessário para esta transmissão era de uma semana. O sistema Bartlane de transmissãode imagens por cabo submarino conseguiu reduzir a transmissão para três horas Botelho[6].

A área de processamento digital de imagens tem atraído grande interesse nas últimas duasdécadas. A evolução da tecnologia de computação digital, bem como o desenvolvimento de novosalgoritmos para lidar com sinais bidimensionais está permitindo uma gama de aplicações cadavez maior.

Como resultado dessa evolução, a tecnologia de processamento digital de imagens vem am-pliando seus domínios, que incluem as mais diversas áreas, como por exemplo: análise derecursos naturais e meteorologia por meio de imagens de satélites; transmissão digital de sinaisde televisão ou facsímile; análise de imagens biomédicas, incluindo a contagem automática decélulas e exame de cromossomos; análise de imagens metalográficas e de fibras vegetais; obtençãode imagens médicas por ultrassom, radiação nuclear ou técnicas de tomografia computadorizada;aplicações em automação industrial envolvendo o uso de sensores visuais em robôs, etc.

O interesse em métodos de Processamento Digital de Imagens surgiu, principalmente, danecessidade de melhorar a qualidade da informação pictorial para interpretação humana, comotambém a compactação de informações, tornando-se assim uma ferramenta essencial no mundomoderno, cuja demanda de processamento é relativamente crescente R. E. Woods [27].

Mas as técnicas de processamento digital de imagens evoluíram em meados dos anos 60 como advento de computadores digitais e com o programa espacial norte-americano. Em 1964,as imagens da lua transmitidas pela sonda Ranger 7 foram processadas por um computadorpara corrigir vários tipos de distorções inerentes à câmara de televisão à bordo. As técnicas deprocessamento usadas nesta época serviram de base para o realce e restauração de imagens deoutros programas espaciais posteriores, como as expedições tripuladas da série Apollo para a lua,por exemplo.

8

[ 6 de julho de 2012 at 11:24 ]

9

O uso de imagens multiespectrais coletadas por satélites tais como, Landsat, SPOT ou similares,tem se mostrado como uma valiosa ferramenta para a extração dos dados destinados às váriasaplicações de pesquisa de recursos naturais. A obtenção das informações espectrais registradaspelos sistemas nas diferentes partes do espectro eletromagnético, visando a identificação e dis-criminação dos alvos de interesse, depende principalmente da qualidade da representação dosdados contidos nas imagens.

As técnicas de processamento digital de imagens, além de permitirem analisar uma cena nasvárias regiões do espectro eletromagnético, também possibilitam a integração de vários tipos dedados, os quais devem estar devidamente registrados.

As principais áreas de aplicações do Processamento Digital de Imagens geralmente requeremmétodos capazes de realçar as informações contidas nas imagens para a posterior interpretação eanálise humana. Algumas destas aplicações são:

Análise de recursos Naturais:

Geologia - estudo da composição e estrutura da superfície, detecção de minerais, óleo e outrosrecursos naturais.

Agricultura - previsão de safras e determinação do tipo de plantação nas áreas de agricultura.

Floresta - determinação do tipo de cobertura florestal.

Cartografia - mapeamento da superfície terrestre.

Análise ambiental:

Monitoramento da poluição.Planejamento urbano.

Meteorologia:

Análise de clima e temperatura.

Biomédica:

Contagem automática de células.

A Figura 1 apresenta dois exemplos de imagens muito usadas em estudos, uma imagembiomédica e uma imagem de geoprocessamento, ambas geradas no software do MATLAB.

[ 6 de julho de 2012 at 11:24 ]

2.1 imagem digital 10

Figura 1: (a) Imagem sísmica; (b) Imagem de geoprocessamento

O Processamento digital de imagens é sempre expresso através de algoritmos implementadospor software. É um processo extremamente dependente do sistema a que está associado e dométodo de extração de informações, que por sua vez, depende do tipo de imagem, da natureza edas informações contidas nela.

Geralmente, técnicas que funcionam bem em algumas áreas podem não ser adequadas emoutras. Assim, não existe até o momento uma solução única e abrangente para todos os problemas,abrindo espaço para varias pesquisas.

Algumas noções básicas serão abordadas a seguir de forma sucinta para um melhor entendi-mento de como analisar uma imagem digital.

2.1 imagem digital

As imagens são vistas como exemplos de sinais gerados em nosso cotidiano que apresentampapéis importantes, podendo ser desde os mais simples, usados para entretenimentos, até asaplicações médicas e tecnológicas mais avançadas M. P. Albuquerque[21].

O termo imagem monocromática, ou simplesmente imagem, refere-se à função bidimensionalde intensidade da luz f(x,y), onde x e y denotam as coordenadas espaciais e o valor f emqualquer ponto (x,y) é proporcional ao brilho (ou níveis de cinza) da imagem naquele ponto.

Às vezes se torna útil a visualização da função da imagem em perspectiva com um terceiro eixorepresentando o brilho. Neste caso, a Figura 02 apareceria como uma série de picos em regiõescom numerosas modificações do nível de brilho e regiões planas ou platôs em que os níveis debrilho variam pouco ou são constantes.

Usando-se esta convenção para atribuir proporcionalmente valores mais altos para áreas demaior brilho obtém-se a altura dos componentes da figura proporcional ao brilho correspondentena imagem.

[ 6 de julho de 2012 at 11:24 ]

2.1 imagem digital 11

Uma imagem digital é uma imagem f(x,y) discretizada tanto em coordenadas espaciais quantoem brilho. Uma imagem digital pode ser considerada como sendo uma matriz cujos índices delinhas e de colunas identificam um ponto na imagem, e o correspondente valor do elemento damatriz identifica o nível de cinza naquele ponto. Os elementos dessa matriz digital são chamadosde elementos da imagem, elementos da figura, "pixels"ou "pels", estes dois últimos, abreviaçõesde "picture elements"(elementos de figura). Quanto mais pixels uma imagem tiver melhor é a suaresolução e qualidade.

Figura 2: (a) Imagem de dimensão 512 x 512 pixels; (b) Imagem de dimensão 256 x 256 pixels; (c) Imagemde dimensão 128 x 128 pixels; (d) Imagem de dimensão 64 x 64 pixels.

A convenção dos eixos para representação de imagens digitais no Processamento de Imagens édiferente da convenção usada na Computação Gráfica.

Cada pixel contém um valor inteiro nas direções das coordenadas x e y que representa medidasdependentes de variáveis, como por exemplo, o nível de quantificação que normalmente é umapotência de 2. Estes pixeis podem estar associado a um valor da escala de cinza entre 0 e 2n−1.Na Figura 3, tem-se um modelo da digitalização de uma imagem radiográfica.

Figura 3: (a) Ponto indicado sobre o olho da Lenna (à esquerda); (b) Matriz de pixels em uma região deinteresse de 10 x 10 pixels em torno do ponto indicado (à direita), onde cada elemento representaa intensidade na região indicada em (a); (c) Nível de quantificação.

[ 6 de julho de 2012 at 11:24 ]

2.2 armazenamento de imagem digital 12

Muitas vezes a digitalização da imagem pode comprometer sua qualidade. Atualmente, existemvárias técnicas de análise de imagens, visto que as imagens carregam em seu interior determina-das informações e também capacidade para a troca das mesmas, possibilitando, desta forma, aqualidade de resolução.

2.2 armazenamento de imagem digital

O armazenamento de imagens digitais é um dos maiores desafios no projeto de sistemas deprocessamento de imagens, em razão da grande quantidade de bytes necessários para tanto. Umexemplo que apresenta essa necessidade são os milhares de exames de diagnósticos através deimagens geradas em hospitais, que em alguns casos, podem chegar a mais de 45 Gbytes por diaP. R. C. Alcocer [25].

Esse armazenamento pode ser dividido em três categorias: (1) armazenamento de curta duraçãode uma imagem, enquanto ela é utilizada nas várias etapas do processamento, (2) armazenamentode massa para operações de recuperação de imagens relativamente rápidas, e (3) arquivamentode imagens, para recuperação futura quando isto se fizer necessário. O espaço de armazenamentorequerido é normalmente especificado em bytes (8 bits) e seus múltiplos: KB (kilobyte = 1000

bytes), MB (megabyte = 1 milhão de bytes), GB (gigabyte = 1 bilhão de bytes) e TB (terabyte = 1

trilhão de bytes).

Atualmente, crescem os processos de transmissão dessas imagens através de redes informatiza-das, criando necessidades de se estabelecer e conhecer formatos padronizados e de processos detransmissão de dados em sistemas de rede local ou mesmo pela internet, com rapidez e segurança,envolvendo desta forma a compactação da imagem. Porém, ao passo que melhora a qualidadevisual da imagem, o volume de dados a serem armazenados processados ou transmitidos aumentatambém, o que proporciona o aumento no número de bits necessários para a codificação bináriada imagem.

O número de bits necessários para o armazenamento de uma imagem na memória do compu-tador é dado pela equação (2.1) R. E. Woods [28].

bits =MXNXn (2.1)onde:n = log2(M);M: É o número de linhas da imagem;N: É o número de colunas da imagem.

Existem dois tipos de compactação, com perda e sem perda de informações. Cada tipo deimagem tem suas exigências quanto ao tipo de compactação, além de ter um cabeçalho dosarquivos de imagens digitais que pode conter informações do tipo: número de linhas, número decolunas, número de bits usados na representação da imagem, resolução horizontal (dx), resoluçãovertical (dy), número de bandas da imagem, tipo de compactação usado para guardar os dados,data e hora de aquisição, tipo de sensor que captou a imagem, dados paramétricos dos sensores,bem como outras informações relevantes.

[ 6 de julho de 2012 at 11:24 ]

2.3 etapas do processamento de imagens 13

2.3 etapas do processamento de imagens

Existem diversas formas de representar as informações compactadas da imagem. O fluxo dessasinformações com um determinado objetivo é o que descreve as etapas do processamento deimagens Albuquerque[3].

01 AquisiçãoA fase de aquisição de imagens consiste em obter uma representação da informação visual,

esta deve ser a mais fiel possível e ao mesmo tempo ser processável por um computador, ou seja,que as informações sejam convertidas em sinais elétricos.

Os sinais elétricos têm sua representação no tempo contínuo. Porém, a tecnologia computaci-onal não processa sinal no tempo contínuo. Por exemplo, câmeras digitais são projetadas paralidar com computação seqüencial envolvendo números.

Para utilizar a tecnologia computacional é necessário saber quão rápida a informação variae assim, mostrar a informação no tempo contínuo e convertê-la em informações no tempo discreto.

Quando se trata de imagens digitais não é preciso essa conversão, pois o seu processamento édireto, como dito anteriormente.

Figura 4: (a) Imagem adquirida da Orquídea; (b) Dispositivo de captura; (c) Sinal digital.

02 Pré-processamentoTem a função de melhorar a qualidade da imagem através de dois métodos: o primeiro baseado

em filtros que manipulam o plano da imagem. O segundo que opera baseado em filtros que agemsobre o espectro da imagem. Ambos os métodos visam o melhoramento de contraste, remoção deruídos, regiões de interesse, reamostragem dos pixels em uma nova escala, treinamento e extraçãode características, melhorar a qualidade da imagem, permitindo uma melhor discriminação dosobjetos presentes na imagem, etc.

[ 6 de julho de 2012 at 11:24 ]


Figura 5: Pré-processamento de uma Imagem.

03 SegmentaçãoSignifica separar a imagem em regiões disjuntas com o objetivo de extrair informações dos

objetos da imagem, como ilustra a Figura 7.

Figura 6: (a) Ampliação de uma região da imagem da orquídea; (b) Valores de intensidade na regiãoselecionada.

Este processo divide uma imagem digital em múltiplas regiões (conjunto de pixels) ou objetos,com o objetivo de simplificar e/ou mudar a representação de uma imagem para facilitar a suaanálise. Segmentação de imagens é tipicamente usada para localizar objetos e formas (linhas,curvas, etc) em imagens.

O resultado da segmentação de imagens é um conjunto de regiões/objetos ou um conjuntode contornos extraídos da imagem (ver detecção de borda). Como resultado, cada um dospixels em uma mesma região é similar com referência a alguma característica ou propriedadecomputacional, tais como cor, intensidade, textura ou continuidade. Regiões adjacentes devempossuir diferenças significativas com respeito a mesma característica(s).

A denominação "objeto"da imagem refere-se aos grupos de pixels que fornecem informaçõesdesejadas.

[ 6 de julho de 2012 at 11:24 ]


Outro termo bastante usado nessa etapa é denominado "fundo"da imagem, que classifica ogrupo dos pixels que podem ser desprezados. Esses dois termos mencionados, juntos determinamregiões na imagem sem representar necessariamente um objeto presente na imagem processada.

Essa é uma etapa crítica, pois é preciso ter cuidados para não gerar erros, que posteriormenteserão refletidos nas etapas seguintes, produzindo ao final do processo resultados comprometedo-res.

A segmentação age de forma adaptativa às características particulares de cada tipo de imageme aos objetivos desejados. Deste modo, pode-se dizer que não existe um modelo específico desegmentação. Porém, as técnicas são bem diversificadas e despertam interesse no melhoramentoe desenvolvimento de novas técnicas.

04 Representação e DescriçãoÉ uma forma de armazenar as informações através de uma matriz, a qual caracteriza a forma e

a topologia dos objetos, seja a imagem representada como sinal unidimensional ou bidimensional.Essa etapa é classificada pela parametrização dos objetos da imagem.

Identifica os objetos segmentados na imagem associando um rótulo a cada objeto. Após isso,os objetos são classificados conforme sua forma apresentada, como ilustra a Figura 7.

Figura 7: (a) Reconhecimento; (b) Interpretação

As informações contidas nas imagens podem ser extraídas e analisadas tanto no domínio dotempo quanto no domínio da freqüência, ou ainda no domínio tempo-escala como é o caso datransformada wavelet Daubechies[8].

Duas transformadas muito usadas para o processamento de imagem são a Transformada deFourier A. V. Oppenheim [1] e a Transformada Wavelet E. J. Stollnits[13].

Na Figura 8 é apresentado um exemplo de redução de ruído em imagens através da transfor-mada wavelet Duarte[11].

[ 6 de julho de 2012 at 11:24 ]


Figura 8: (a) Imagem original; (b) Imagem contaminada por ruído branco; (c) Imagem após a eliminação doruído utilizando a Transformada Wavelet.

No campo do processamento de imagens, o presente trabalho apresenta duas propostas: umaé a criação de um sistema interativo para o armazenamento de imagens, que otimiza o espaçocomputacional que essas imagens ocupam, tendo a diminuição do número de bits usados paraarmazenamento. O processo de leitura da imagem será feito pela Função de Peano (capítulo 4)e a codificação será feita usando a Transformada Wavelet 1D (capítulo 3). A outra proposta é acriação de uma interface gráfica para processamento de imagens no que diz respeito à compressãoe redução de ruído. Esta interface é criada com o objetivo de facilitar o trabalho de quem precisamanipular imagens, mas não tem conhecimento de programação computacional.

[ 6 de julho de 2012 at 11:24 ]

Parte III

PA RT E I I I : T E O R I A WAV E L E T

[ 6 de julho de 2012 at 11:24 ]

Capítulo3T E O R I A WAV E L E T

[ 6 de julho de 2012 at 11:24 ]

3T E O R I A WAV E L E T

Uma função wavelet é a interpretação de uma onda de curta duração com crescimento e de-crescimento rápidos. Sua teoria baseia-se na representação de funções em diferentes escalas ediferentes resoluções (tempo-escala), considerando assim uma das suas principais característicasDaubechies[9].

Embora a primeira menção às wavelets tenha acontecido em 1909, por A. Haar[2], as waveletsde Haar ficaram no anonimato por muitos anos e, por um período muito longo, elas continuarama ser a única base ortonormal de wavelets conhecida. Só recentemente, 1985, Stephane Mallat(MALLAT, 1989 (a), MALLAT, 1989 (b)) deu às wavelets um grande impulso através de seutrabalho em processamento digital de wavelets de Haar, as wavelets de Meyer são continuamentediferenciáveis; contudo, elas não têm suportes compactos. Poucos anos mais tarde, Ingrid Daube-chies (Daubechies[8]; Daubechies[9]; Daubechies[10]) usou os trabalhos de Mallat para construirum conjunto de bases ortonormais de wavelets suaves, com suportes compactos. Os trabalhos deDaubechies são os alicerces das aplicações atuais de wavelets.

O algoritmo de Mallat (MALLAT, 1989 (a)) é considerado o elo definitivo entre wavelets eprocessamento de sinais. Desde então, pesquisas em wavelets tornaram-se difundidas internacio-nalmente (R. Coifman[26], Coifman[7], R. Coifman[26], O. Rioul[24]).

3.1 wavelets

As funções wavelets, geralmente denotadas por ψ(t), são definidas como um conjunto de funçõesoriginadas através das operações matemáticas de translação e escalonamento da função escala,com propriedades particulares que as tornam adequadas para servirem de base para a decompo-sição de outras funções Faria[14].

A função escala é uma função básica definida num espaco Vj, usualmente denotada por φ, tendocomo funções básicas associadas:

φji(t) := φ(2

jt− i), i = 0, ..., 2j−1 (3.1)

sendo:φ: função escala;i: deslocamento;j: escala;

19

[ 6 de julho de 2012 at 11:24 ]

3.1 wavelets 20

t: tempo.Para que uma função seja considerada uma wavelet é preciso satisfazer as seguintes condições

básicas e necessárias:

1. que φ(t) ∈ L2(<), ou seja, a função pertença ao espaço das funções de quadrado integrávelou, ainda, o espaço das funções de energia finita, no sentido que:

∫∞−∞ |ψ(t)|2dt <∞ (3.2)

2. que sua Transformada de Fourier ψ̄(ω) satisfaça a condição de admissibilidade Daube-chies[9]:

Cψ =

∫∞−∞

ψ̄(ω)

ωdω <∞. (3.3)

Segue da condição de admissibilidade que:

limω→0

ψ̄(ω) = 0 (3.4)

Assim, se ψ̄(ω) é contínua então, ψ̄(ω) = 0, ou seja,

∫∞−∞φ(t)dt = 0.

Geometricamente, a condição (3.3) estabelece que o gráfico de ψ(t) deve oscilar de modo acancelar as áreas negativas a fim de anular a integral (3.5). Portanto, o gráfico de ψ(t) tem aforma de onda, conforme ilustra a Figura 9 (b), que é um exemplo de wavelet.

Desde que ψ(t) esteja bem localizada no tempo, este decaimento será muito rápido, formandouma onda de curta duração.

Atualmente, existem inúmeras funções wavelets que geralmente recebem o nome de seuscriadores, dentre as quais serão apresentadas, a seguir, as mais conhecidas.

Começando pelo exemplo mais simples, proposto em 1909 pelo matemático húngaro AlfredHaar Haar[15]. A wavelet de Haar, que demonstra as grandezas que envolvem os valores de formanão contínua, tornando-se deste modo um caso particular da transformada wavelet discretadefinida por:

[ 6 de julho de 2012 at 11:24 ]

3.1 wavelets 21

ψji(t) = φ(2t) −φ(2t− 1). (3.6)

É através da equação (3.6) que podemos obter ψ(t), apresentada na figura 9 (b).

Figura 9: (a) Função escala de Haar; (b) Função Wavelet de Haar.

Outra função é a wavelet de Morlet, introduzida por Jean Morlet pertence a família das waveletsnão-ortogonais. A wavelet de Morlet não possui função escala e é explícita por uma Gaussianamodulada (shifted), levemente ajustada. De forma que ψ(0) = 0, conforme a equação (3.7), cujográfico é apresentado na Figura 10:

ψ(t) = Ce−t2/2cos(5t) (M. Misiti[20]). (3.7)

Figura 10: Função wavelet de Morlet.

Daubechies propôs um procedimento de partida para a construção das bases ortonormais aoinvés de construir a wavelet e a função de escala através de um subespaço Vj.

[ 6 de julho de 2012 at 11:24 ]

3.1 wavelets 22

O procedimento parte de coeficientes apropriados e então investiga se eles correspondem auma base de wavelet ortonormal. Esses coeficientes representam um conjunto particular denúmeros gerados por filtros. Em 1987 as bases ortonormais de wavelets foram consideradas comosendo funções de suporte compacto contidas no intervalo [0, 2r+ 1].

Quanto maior o número de coeficientes, mais suave será a wavelet. A construção de Daubechiesresulta em uma coleção de coeficientes Nhn , sendo:

N = 2, 3, 4, ... e 0 < n < 2N− 1.A seguir é apresentado um exemplo da wavelet mais simples de Daubechies, a DAUB4, gerada

a partir de apenas quatro coeficientes Nievergelt[23].

(h0,h1,h2,h3) =

(1+√3

4√2

,3+√3

4√2

,3−√3

4√2

,1−√3

4√2

)(3.8)

A partir desses coeficientes pode-se construir a função escala:

φ(t) =√2

2N−1∑k=0

hkφ(2t−K) (3.9)

e calcular gn:

(g0,g1,g2,g3) =

(1−√3

4√2

,−3+

√3

4√2

,3+√3

4√2

,−1−

√3

4√2

). (3.10)

Assim, a wavelet de Daubechies é dada por:

φ(t) =√2

2N−1∑k=0

gkφ(2t−K) (3.11)

Portanto, a matriz A representa os coeficientes da wavelet de Daubechies (DAUB4) na decom-posição de um sinal.

[ 6 de julho de 2012 at 11:24 ]

3.1 wavelets 23

Figura 11: Matriz dos coeficientes da wavelet de Daubechies (DAUB4) na decomposição de um sinal.

Observe que há certa semelhança nas linhas que contêm os coeficientes. As linhas ímparescontêm os coeficientes correspondentes à filtragem passa - baixa que suaviza os dados enquantoque as linhas pares correspondem à filtragem passa - alta que captura os detalhes que a filtragempassa - baixa perdeu.

Já a reconstrução do sinal é representada pela matriz B:

Figura 12: (a) Função escala de Daubechies; (b) Função Wavelet de Daubechies.

Tais wavelets de Daubechies possuem todos os momentos até ordem N− 1 nulos, ou seja,∫∞−∞ xlNψ(x)dx = 0, l = 0, ...,N− 1.

[ 6 de julho de 2012 at 11:24 ]

3.1 wavelets 24

A wavelet de Haar pode ser vista como um caso particular das Wavelets de Daubechies quandoN = 1.

Necessariamente toda wavelet satisfaz∫∞−∞ψ(x)dx = 0, ou seja, ela tem momento de ordem

zero nulo. Sob o ponto de vista prático, quanto mais momentos nulos uma wavelet possuir,menores serão os coeficientes de Wavelets correspondentes as partes de f que são suaves, ou seja,os coeficientes de wavelets serão apreciáveis onde f não for suave, o que nos permite usar waveletspara detectar singularidades de f. Em contra-partida, para uma função escala, φ, necessariamente∫∞−∞φ(x)dx 6= 0.Em termos de compressão, a vantagem de uma wavelet ψ ter vários momentos nulos nos

conduz a uma alta compressividade, porque os coeficientes de wavelets das escalas mais finas deuma função são essencialmente nulos onde a função é suave.

Yves Meyer em 1980 construiu a primeira wavelet trivial diferente da wavelet de Haar, que écontinuamente diferenciável, o que limita suas aplicações A.V. Silva[5]. Desta forma, uma basewavelet suave ortonormal foi criada. Primeiro, definiu-se a Transformada de Fourier φ̄(t) de umafunção escala φ(t) como:

φ̄(t) =

(2π)−1/2, se |t| <

2π

3

(2π)−1/2cos

[π

2v

(3

4π|t|− 1

)], se

2π

36 |t| 6

4π

3(3.12)

0, se |t| >4π

3

onde

v(a) = a4(35− 84a+ 70a2 − 20a3),a ∈ [0, 1] M. Misiti[20]. (3.13)

Deste modo, a função wavelet ψ̄(t) pode ser encontrada facilmente a partir de φ(t).

ψ̄(t) =

(2π)−1/2et/2sen

[π

2v

(3

2π|t|− 1

)], se

2π

36 |ω| 6

4π

3

(2π)−1/2et/2cos

[π

2v

(3

4π|ω|− 1

)], se

4π

36 |ω| 6

8π

3(3.14)

0, caso contrário

A figura 13 ilustra as equações (3.12) e (3.14)

[ 6 de julho de 2012 at 11:24 ]

3.2 transformada wavelet (tw) 25

Figura 13: Função Escala de Meyer; Função Wavelet de Meyer.

3.2 transformada wavelet (tw)

A Transformada Wavelet é uma ferramenta conhecida pela característica de transformar funções ede reconstruí-las, apresentando uma resolução razoavelmente boa. Por exemplo, a reconstruçãode um sinal que apresente coeficientes com valores próximos de zero requer um trabalho árduoalém de um alto custo computacional.

São apresentadas as duas formas da transformada, a contínua e a discreta. A transformadawavelet contínua é de grande interesse teórico, principalmente para a derivação e compreensãodas propriedades matemáticas das funções wavelets. Porém a sua discretização é necessária paraaplicações práticas, por exemplo, ao descrever um sinal unidimensional em uma representaçãobidimensional ou quando se tem a necessidade de se inverter a operação.

O problema dos parâmetros a e b variarem continuamente é resolvido com a operação dediscretização, surgindo, desta maneira, a transformada wavelet discreta, com a finalidade depropor mais eficiência ao trabalho.

3.2.1 Transformada Wavelet Contínua (TWC)

De acordo com Young Young[29], a TWC pode ser considerada como uma operação de ruptura,ou seja, a transformada wavelet "quebra"uma função em muitos pedaços e estes pedaços sãorepresentados por coeficientes, chamados de coeficientes wavelet definidas na equação (3.15).

Na decomposição de uma função surge um conjunto de funções especiais chamadas wavelets.As wavelets são funções resultantes da atuação simultânea de duas operações (escalamento etranslação) numa única função, denominada wavelet "mãe".

[ 6 de julho de 2012 at 11:24 ]

3.3 transformada wavelet cont ínua inversa (twci) 26

3.2.2 Função Wavelet Mãe

Matematicamente, uma função ψ(t) para ser considerada uma wavelet mãe, deve pertencer aoespaço L2(<) e satisfazer a condição de admissibilidade.

Sem muito rigor matemático, uma wavelet mãe é uma função que oscila, tem energia finita etem valor médio nulo. As funções básicas associadas são do tipo:

ψji = ψ(2

jt− i) (3.15)

3.3 transformada wavelet cont ínua inversa (twci)

A TWCI segue o raciocínio de reconstruir uma função x(t) decomposta pela transformada waveletcontínua através das wavelets filhas, combinando os coeficientes wavelets. Quanto melhor a uniãomaior será o valor do coeficiente wavelet. O conjunto de todos os coeficientes wavelet constitui arepresentação da função x(t) no domínio wavelet.

Assim, o sinal x(t) decomposto usando uma wavelet φ(t) que satisfaz a condição de admissibi-lidade, será reconstruído através da TWCI conforme a equação (3.16).

x(t) =1

Cψ

∫∞−∞∫∞−∞{

(Wψx

)(a,b)}

{1√|a|ψ

(t− b

a

)}dadb

a2(3.16)

Observa-se da equação (3.17) que tem o mesmo núcleo1√|a|ψ

(t− b

a

)é utilizado na TWC e

em sua inversa.

De acordo com Daubechies Daubechies[10], a equação (3.17) pode ser vista de dois modosdiferentes:

• Modo de reconstrução de x(t), desde que sua transformada wavelet inversa seja conhecida;

• Modo de representação de x(t), como uma superposição de wavelets filhas.

3.4 transformada wavelet discreta (twd)

Na TWC, mais especificamente na equação (3.16), depara-se com a presença de redundâncias, poisos parâmetros a e b variam continuamente. Esse problema é contornado por meio de discretizaçãode a e b.

Este processo origina a transformada wavelet discreta (TWD). De acordo com a literaturaJ. Gomes[17], uma discretização típica é do tipo:

a = am0

[ 6 de julho de 2012 at 11:24 ]

3.5 transformada wavelet discreta inversa (twdi) 27

eb = nam0 b0 (3.18)

com m e n ∈ Z, a0 > 1 e b0 6= 0.Deste modo, tem-se a transformada wavelet discreta:

(Wψx)(m,n) =1√am0

∫+∞−∞ x(t)ψ

(t−nam0 b0

am0

)dt (3.17)

Destas equações observa-se:

• A TWD é definida apenas para valores de escala positivos (a0 > 1);

• O passo de translação é proporcional à escala (b = nam0 b0);

• A TWD produz um número finito de coeficientes wavelet (Wψx)(m,n);

• O processo é realizado sobre tempo contínuo.

3.5 transformada wavelet discreta inversa (twdi)

No caso contínuo, dada uma função wavelet mãe, uma função qualquer x(t) pode sempre serrecuperada do seu conjunto de coeficientes wavelet contínuos. No caso discreto, entretanto, oprocesso de reconstrução pode não convergir para a função x(t). A reconstrução depende daescolha da wavelet mãe e do processo de discretização realizado.

De acordo com Daubechies Daubechies[9], a reconstrução ideal seria aquela que ocorressecom o máximo de eficiência e com um mínimo de perda de informação. Neste sentido, a funçãox(t) pode ser reconstruída a partir dos seus coeficientes wavelet discretos com uma aproximaçãorazoavelmente boa, através da equação (3.19).

x(t) ≈ c∞∑m=0

∞∑n=0

((Wψx)(m,n))(ψm,n(t)) (3.19)

sendo c uma constante que depende do processo de discretização e da wavelet mãe utilizada.

A seguir, tem-se um típico modelo TWD aplicada em um sinal unidimensional através datransformada de Haar, que consiste em calcular a média e a diferença entre os elementos de umvetor dois a dois E. J. Stollnits[13].

Considere Sn um vetor com n elementos representantes do sinal.

Sn = (s1, s2, ..., sn) (3.20)onde:

Mn/2 = (m1,m2, ...,mn/2) =(s1 + s22

,s3 + s42

, ...,sn−1 + sn

2

)(3.21)

Dn/2 = (d1,d2, ...,dn/2) =(s1 − s22

,s3 − s42

, ...,sn−1 − sn

2

)(3.22)

sendo:n: número de elementos pertencentes ao vetor;

[ 6 de julho de 2012 at 11:24 ]

3.6 análise de multirresolução (amr) 28

M: vetor que representa as médias (m1,m2, ...,mn/2) calculadas;D: vetor que representa as diferenças (d1,d2, ...,dn/2) calculadas.

A transformada inversa de Haar recalcula os valores originais a partir da média e das diferençasobtidas da seguinte maneira:

S′n = (m1 + d1,m1 − d1,m2 + d2,m2 − d2, ...,mn/2 + dn/2,mn/2 − dn/2) (3.23)

As equações (3.21), (3.22) e (3.23), respectivamente representam o comportamento da waveletde Haar na decomposição e reconstrução simultaneamente de um sinal.

Um tópico muito importante, que envolve a transformada wavelet para o processamento deimagens, é a Análise de Multirresolução (AMR).

A análise de Multirresolução permite analisar uma imagem em diferentes resoluções alémde ser versátil para aplicações em várias outras áreas tais como sinais de áudio e vídeo, sinaisbiomédicos, medidas industriais, análise de dados, dentre outros.

É através da análise de multirresolução que se pode comprimir ou remover ruídos, reconstruirdados perdidos, reconhecer padrões, entre outras aplicações.

3.6 análise de multirresolução (amr)

Mallat (1986) concebeu uma análise de multirresolução, estabelecendo uma sequência de subes-paços encaixantes Vj ⊂ L2(<), sendo:j: número inteiro (j ∈ Z);L2(<): espaço das funções de quadrado integrável a Lebesgue;Vj: sequência de espaços encaixantes, ou seja:

...V−1 ⊃ V0 ⊃ V1 ⊇ V2... (3.24)

Tem-se o complemento ortogonal de Vj como subconjunto de Vj+1, denotado por Wj.

Vj+1 = Vj ⊕Wj (3.25)

⊕: indica a soma direta dos subespaços ortogonais.Os subespaços Wj contêm os detalhes necessários para construir Vj+1 a partir de Vj.

Vj =Wj ⊕Wj−1 ⊕Wj−2 ⊕ ... (3.26)

A cada estágio de decomposição:

Wj = Vj − Vj+1 (3.27)

[ 6 de julho de 2012 at 11:24 ]

3.6 análise de multirresolução (amr) 29

no domínio da freqüência, tem-se:

Wj: componentes de alta frequência de Vj+1;

Vj: Componentes de baixa frequência de Vj+1.

Estes espaços têm as propriedades descritas a seguir Daubechies[8].

(M1) Vj = Vj+1 ⊕Wj+1: existe um subespaço complementar Wj em que os detalhes sãoarmazenados.

(M2) Vj+1 ⊂ Vj: são subespaços encaixados como citado anteriormente.

(M3) ¯∪Vj︸︷︷︸j∈Z

= L2(<): esta sequência possui a seguinte propriedade: Toda função f ∈ L2(<) pode

ser representada por suas projeções.

(M4) ¯∩Vj︸︷︷︸j∈Z

= {0}: a propriedade (M4) equivale dizer, que as projeções tem energia arbitraria-

mente pequena ao passo quando j aumenta, fazendo com que os detalhes sejam cada vez maisevidentes, nível por nível, em ordem crescente, conforme j→∞.

(M5) x(t) ∈ Vj+1 ⇔ x(2t) ∈ Vj: a função escalar gera um subespaço de referência e aplicandoa propriedade (M5) sucessivamente concluí-se, que todos os subespaços Vj também são geradospela função escala, assim como os subespaços Wj também são gerados pela função wavelet.

A projeção ortogonal de uma função f ∈ L2(<) em Vj é obtida através da função de escala,que por sua vez define um filtro passa-baixa. A frequência de corte desse filtro é indicado por α(j).

A Figura 14 explica como são representados esses cortes e quais os espaços criados por elesKosloski[19].

Figura 14: Bandas de frequência entre Vj e Vj+1

Pode-se observar que o espaço Vj contido em [−αj,αj] é obtido a partir do espaço Vj+1 queestá contido em [−αj−1,αj−1], e Wj+1 que está contido em [αj−1,αj].

[ 6 de julho de 2012 at 11:24 ]

3.7 transformada wavelet discreta bidimensional (twd bidimensional) 30

Quando se passa de Vj para Vj+1 a escala aumenta de 2j para 2j+1 e a banda de frequênciadiminui para um intervalo [−αj−1,αj−1]. O que significa do ponto de vista de processamento deimagens, melhorar a visão com relação à imagem, ou seja, dar um zoom na imagem.

A seguir serão abordados os principais tópicos que nos permite compreender como a análisede multiressolução é aplicada usando a transformada wavelet em processamento de imagens.

3.7 transformada wavelet discreta bidimensional (twd bidimensional)

Existem duas formas comuns nas quais as wavelets podem ser usadas para transformar osvalores dos pixels dentro de uma imagem. Cada uma destas transformações é uma generalizaçãobidimensional da TWD unidimensional.

A primeira transformada é chamada de decomposição padrão. Para obter a decomposiçãopadrão de uma imagem, aplica-se primeiro a TWD unidimensional a cada linha de valores depixels. Esta operação resulta em um valor médio para cada linha.

Feito isto, tratam-se estas linhas transformadas como se elas fossem uma imagem, e aplica-sea TWD unidimensional para cada coluna. Os valores resultantes são todos os coeficientes dedetalhes, exceto por um único coeficiente que representa a média geral.

Figura 15: Decomposição padrão de uma imagem.

O segundo tipo de TWD bidimensional, chamado de decomposição não-padrão. São realizadasoperações de decomposição alternadas entre linhas e colunas. Primeiro aplica-se o cálculo damédia nos pares horizontais e faz-se a diferença dos valores dos pixels em cada linha da matrizque representa a imagem. Depois, aplica-se o cálculo da média nos pares verticais e encontra-se adiferença para a coluna do resultado.

A transformação é completada, repetindo o processo recursivamente apenas no quadrantecontendo as médias em ambas as direções.

[ 6 de julho de 2012 at 11:24 ]


Figura 16: Decomposição não padrão de uma imagem.

3.7.1 Um exemplo da aplicação da Transformada Wavelet de Haar na Compressão de um Sinal

Considere que a sequência de números (2, 2, 2, 2) deve ser transmitida através de uma rede damaneira mais rápida possível, o que implica no envio de uma menor quantidade de dados.Tem-se algumas opções. Trivialmente, a primeira opção é apenas para enviar todos os quatronúmeros, ou seja, enviar o primeiro 2, depois o segundo 2, o terceiro, e por fim, o quarto. Istosugere, implicitamente, a escolha da seguinte base:

< 1, 0, 0, 0 >

< 0, 1, 0, 0 >

< 0, 0, 1, 0 >

< 0, 0, 0, 1 >

Esta é a opção mais simples, porém a mais lenta para transmissão. Uma boa maneira é aescolha de uma base que represente os dados com eficiência e de forma compacta. Como essesdados são uniformes, isto é, um sinal constante de 2. Explorando esta uniformidade. Escolhe-seo vetor de base < 1, 1, 1, 1 >, é possível representar os dados por apenas um número. Bastaenviar o número 2 sobre a rede, e a sequência de dados inteiro pode ser reconstruída por umamultiplicação (ou ponderação) com o vetor de base < 1, 1, 1, 1 >. Precisa-se de mais três vetoresbase para completar a base do espaço, que no exemplo é de dimensão 4. Estes vetores da basetêm que ser ortogonais. Isto significa que o produto escalar de quaisquer dois vetores da base,o resultado deve ser zero. Portanto, deve-se encontrar um vetor que é ortogonal a < 1, 1, 1, 1 >.Considere o vetor < 1, 1,−1,−1 >. O produto escalar destes dois vetores é zero. Graficamente,estes dois vetores representam:

[ 6 de julho de 2012 at 11:24 ]


Figura 17: (a) Representação gráfica do vetor <1, 1, 1, 1>; (b) Representação gráfica do vetor <1, 1, -1, -1>.

Graficamente esses vetores da base são parecidos com "ondas", daí o nome de wavelets. Tem-sedois vetores da base, precisa-se de mais dois. Haar construiu os vetores restantes da base porum processo de dilatação e contração. Dilatação basicamente significa "comprimir", portanto osvetores da base restantes foram construídos comprimindo e deslocando. Comprimindo o vetor< 1, 1,−1,−1 >, tem-se < 1,−1, 0, 0 >. O par 1, 1 é comprimido em um único 1, similarmente, opar −1, −1 torna-se um único valor −1. Em seguida, realiza-se um deslocamento no vetor dabase resultante e obtem-se: < 0, 0, 1,−1 >, que é o vetor da base final. Graficamente estes doisvetores representam:

Figura 18: (a) Representação gráfica do vetor <1, -1, 0, 0>; (b) Representação gráfica do vetor <0, 0, 1, -1>.

Agora a base está completa para o espaço de dimensão 4, constituído pelos seguintes vetoresde base ou wavelets.

< 1, 1, 1, 1 >

< 1, 1,−1,−1 >

< 1,−1, 0, 0 >

< 0, 0, 1,−1 >

Mesmo estes vetores da base sendo ortogonais, eles não são ortonormais. No entanto, é facil-mente possível normalizá-los através do cálculo da norma de cada um desses vetores e dividindosuas componentes por esse valor.

[ 6 de julho de 2012 at 11:24 ]


< 1, 1, 1, 1 > Norma =√12 + 12 + 12 + 12 = 2 − > < 1/2, 1/2, 1/2, 1/2 >

< 1, 1,−1,−1 > Norma =√12 + 12 + (−1)2 + (−1)2) = 2 − > < 1/2, 1/2,−1/2,−1/2 >

< 1,−1, 0, 0 > Norma =√12 + (−1)2 + 02 + 02 =

√2 − > < 1/

√2,−1/

√2, 0, 0 >

< 0, 0, 1,−1 > Norma =√02 + 02 + 12 + (−1)2 =

√2 − > < 0, 0, 1/

√2,−1/

√2 >

Agora com a base formada, segue um exemplo de como representar um vetor de entrada (sinal)para wavelets. Isto também é conhecido como a Transformada 1D de Haar.

3.7.2 Transformada 1D de Haar

Considere agora o vetor de entrada < 4, 2, 5, 5 >. Para representar por wavelets, simplismentetoma-se um produto escalar do vetor de entrada com cada um dos vetores da base.

< 4, 2, 5, 5 > . < 1/2, 1/2, 1/2, 1/2 >= 8

< 4, 2, 5, 5 > . < 1/2, 1/2,−1/2,−1/2 >= −2

< 4, 2, 5, 5 > . < 1/√2,−1/

√2, 0, 0 >= 2/

√2

< 4, 2, 5, 5 > . < 0, 0, 1/√2,−1/

√2 >= 0

Assim, o vetor de entrada foi transformado em < 8,−2, 2/√2, 0 >. Note que a quarta compo-

nente é 0. Isto significa que não é preciso do 4º vetor da base, pode-se reconstruir o vetor deentrada original com apenas os três primeiros vetores da base. Em outras palavras, escolhe-sedinamicamente três vetores da base dentre as 4 possibilidades, de acordo com o vetor de entrada.

8∗ < 1/2, 1/2, 1/2, 1/2 >=< 4, 4, 4, 4 >

−2∗ < 1/2, 1/2,−1/2,−1/2 >=< −1,−1, 1, 1 >

2/√2∗ < 1/

√2,−1/

√2, 0, 0 >=< 1,−1, 0, 0 >

Adicionando os vetores=< 4, 2, 5, 5 >

Se o vetor de entrada for maior que 4, por exemplo, com 8 componentes, não é necessário encon-trar os vetores da base mais uma vez. Pode-se usar a menor base obtida acima. De fato, pode-se

[ 6 de julho de 2012 at 11:24 ]


usar a função wavelet mais simples, que consiste em: < 1/√2, 1/√2 > e < 1/

√2,−1/

√2 >.

Essas são as menores ondas, nota-se que não é possível mais comprimí-los. No entanto, naescolha destes vetores de base menor para uma maior entrada, já que não se pode mais fazer atransformada wavelet de Haar como anteriormente, tem-se que transformar recursivamente ovetor de entrada até chegar ao resultado final. Para exemplificar, segue o mais simples, com duascomponentes na base para transformar em quatro componentes de entrada do vetor anterior. Oalgoritmo é descrito abaixo, e o exemplo é traçado ao lado.

Figura 19: Algorítmo para transformar um vetor de entrada em base Wavelets

Este algoritmo é muito simples. Tudo que se faz é tomar as somas e diferenças de cada parde números no vetor de entrada e dividí-los pela raiz quadrada de 2. Em seguida, o processoé repetido no vetor resultante da soma dos termos. A seguir tem-se uma implementação daTransformada de Haar 1D em C++:

[ 6 de julho de 2012 at 11:24 ]


/ * Entradas: entrada = vetor vec, n = tamanho do vetor de entrada * /

void haar1d (* VEC, int n float)

int i = 0;w = int n;float * vecp = new float [n];for (i = 0; i <n, i + +)vecp [i] = 0;

while (w> 1)

w / = 2;for (i = 0; i <w, i + +)

vecp [i] = (vec [2 * i] + vec [2 * i + 1]) / sqrt(2.0);vecp [i + w] = (vec [2 * i] - VEC [2 * i + 1]) / sqrt(2.0);

for (i = 0; i <( w*2); i + +)vec [i] = vecp [i];

delete []vecp;

[ 6 de julho de 2012 at 11:24 ]

Parte IV

PA RT E I V: F U N Ç Õ E S D E P E A N O

[ 6 de julho de 2012 at 11:24 ]

Capítulo4F U N Ç Õ E S D E P E A N O D E [0, 1] E M [0, 1]N

[ 6 de julho de 2012 at 11:24 ]

4F U N Ç Õ E S D E P E A N O D E [0, 1] E M [0, 1]N

As Curvas de Peano foram estudadas pela primeira vez pelo matemático italiano Giuseppe Peano(1858-1932), com o objetivo de preencher completamente, com uma curva contínua, um espaçobidimensional (como um quadrado), ou generalizando, um espaço n-dimensional (hipercubo).

Intuitivamente uma "curva contínua"em dimensões 2 ou 3 (ou mais) podem ser imaginadascomo "caminho de um ponto em movimento contínuo". Esta noção é muito vaga. Para torná-lamais prescisa, Camille Jordan(1838-1922) em 1887, introduziu a definição rigorosa que se segue,que tem sido usada como uma descrição precisa da noção de "curva contínua": Uma curva (compontos terminais) é uma função contínua cujo domínio é o intervalo unitário [0,1].

Na sua forma mais geral, o contradomínio de tal função pode ser num espaço topológicoarbitrário. Mas nos casos mais comuns, o contradomínio é um espaço euclidiano, tal como oplano bidimensional (uma "curva planar") ou um espaço tridimensional ("curva espacial").

Por vezes, a curva é identificada com o conjunto de valores ou a imagem da função (o conjuntode todos os valores possíveis da função), em vez da própria função. É ainda possível definircurvas sem pontos terminais que sejam funções contínuas numa linha real ou no intervalo unitárioaberto (0,1).

Em Mathematische Annalen Volume 36, Number 1, 157-160, DOI: 10.1007/BF01199438, mostra,de maneira não muito simples, a definição da Função de Peano descrita por Peano.

No artigo (a ser publicado) de Joaquim Elias de Freitas, é apresentado de forma clara umafunção que é uma Curva de Peano e que quando se restringe a um número de casas "decimais"finita, obtem-se uma Curva que preenche o quadrado discreto "continuamente". Esta curva émodelada por um algoritmo de baixa complexidade, desenvolvido neste trabalho, que permiteaplicações de matemática computacional.

4.1 fam ília de funções de peano

Defini-se a família de funções,

fn(x) : [0, 1]→ [0, 1]n,n = 2, 3, ... (4.1)

sendo x ∈ [0, 1] escrito em expansão ternária (com base 3), na forma

x = (0, x1x2...xj...xnx1+nx2+n...xj+n...xn+n...x1+inx2+in...xj+in...xn+in...)3

com xj+in ∈ {0, 1, 2}, j = 1, 2, ...,n e i = 0, 1, ...

38

[ 6 de julho de 2012 at 11:24 ]

4.1 fam ília de funções de peano 39

Ou de forma equivalente, x no formato matricial para melhor entendimento das fórmulas quevem posteriormente

x = (0, x1x2...xj...xn

x1+nx2+n...xj+n...xn+n

...

x1+inx2+in...xj+in...xn+in

...)3

Defini-se agora fn(x) como sendo:

fn(x) = fn((0, x1x2...xnx1+nx2+n...xn+n...x1+inx2+in...xj+in...)3) =

((0,X1X1+n...X1+in...)3,

...

(0,XjXj+n...Xj+in...)3,

...

(0,XnXn+n...Xn+in...)3).

Onde

Xj+in = 1+ (−1)Sxj+in(xj+in − 1),

com

Sxj+in =

j+in−1∑k=1

xk −

i−1∑q=0

xj+qn. (4.2)

Esta é uma família de funções de Peano que transforma um intervalo fechado em um cubo dedimensão n.

Segue um exemplo simples da construção de uma curva de Peano através da fórmula (4.2)considerando n = 2, i = 0. Com estes parâmetros, a fórmula reduz-se a:

Xj = 1+ (−1)Sxj(xj − 1),

com

Sxj =

j−1∑k=1

xk −

−1∑q=0

xj+q.2. (4.2.1)

Dada a sequência de 0 a 8 dos números naturais na base ternária:

00, 01, 02, 10, 11, 12, 20, 21, 22

Aplicando tais pontos na fórmula (4.2.1):

[ 6 de julho de 2012 at 11:24 ]


00− > Sx1 = x1 − x1 = 0− 0 = 0⇒ X1 = 1+ (−1)0(0− 1) = 0

Sx2 = x1 − x2 = 0− 0 = 0⇒ X2 = 1+ (−1)0(0− 1) = 0− > 00

01− > Sx1 = x1 − x1 = 0− 0 = 0⇒ X1 = 1+ (−1)0(0− 1) = 0

Sx2 = x1 − x2 = 0− 1 = −1⇒ X2 = 1+ (−1)−1(1− 1) = 1− > 01

02− > Sx1 = x1 − x1 = 0− 0 = 0⇒ X1 = 1+ (−1)0(0− 1) = 0

Sx2 = x1 − x2 = 0− 2 = −2⇒ X2 = 1+ (−1)−2(2− 1) = 2− > 02

Encontra-se a sequência de pontos: 00, 01, 02. Geometricamente, tem-se:

Continuando o processo para mais alguns pontos:

10− > Sx1 = x1 − x1 = 1− 1 = 0⇒ X1 = 1+ (−1)0(1− 1) = 1

Sx2 = x1 − x2 = 1− 0 = 1⇒ X2 = 1+ (−1)1(0− 1) = 2− > 12

11− > Sx1 = x1 − x1 = 1− 1 = 0⇒ X1 = 1+ (−1)0(1− 1) = 1

Sx2 = x1 − x2 = 1− 1 = 0⇒ X2 = 1+ (−1)0(1− 1) = 1− > 11

12− > Sx1 = x1 − x1 = 1− 1 = 0⇒ X1 = 1+ (−1)0(1− 1) = 1

Sx2 = x1 − x2 = 1− 2 = −1⇒ X2 = 1+ (−1)−1(2− 1) = 0− > 10

Completando a curva da imagem anterior com os pontos 12, 11, 10:

Prosseguindo para os demais elementos:

20− > Sx1 = x1 − x1 = 2− 2 = 0⇒ X1 = 1+ (−1)0(2− 1) = 2

Sx2 = x1 − x2 = 2− 0 = 2⇒ X2 = 1+ (−1)2(0− 1) = 0− > 20

21− > Sx1 = x1 − x1 = 2− 2 = 0⇒ X1 = 1+ (−1)0(2− 1) = 2

Sx2 = x1 − x2 = 2− 1 = 1⇒ X2 = 1+ (−1)1(1− 1) = 1− > 21

22− > Sx1 = x1 − x1 = 2− 2 = 0⇒ X1 = 1+ (−1)0(2− 1) = 2

Sx2 = x1 − x2 = 2− 2 = 0⇒ X2 = 1+ (−1)0(2− 1) = 2− > 22

[ 6 de julho de 2012 at 11:24 ]


Acrescentando os pontos 20, 21, 22:

Aumentando-se a sequência para 18 pontos, obtem-se:

Continuando a sequência de pontos, preenche-se um quadrado de dimensões maiores:

Este processo pode ser continuado indefinidamente.Das definições dadas em (4.2), observa-se que Xj+in pode ser visto como uma função de j+ in

variáveis, podendo ser denotado por:

Xj+in = G(x1, x2, ..., xj+in). (4.3)

Há casos que existem duas expansões ternárias para um mesmo número real. Neste sentido,prova-se a seguir que fn(x), calculado usando as fórmulas (4.2), quando aplicadas às duasexpansões de x, obtém-se o mesmo resultado.

Quando temos duas expansões, uma é finita e a outra é obtida a partir da expansão finita,substituindo o último algarismo não nulo, que é 2 ou 1, por ele mesmo menos 1 e os demais"dígitos"seguintes da expansão por 2.

Seja x0 = (0, x01x02...x0j+in000...)3 a expansão finita com x0j+in ∈ {1, 2} seu último algarismo não

nulo e x1 = (0, x11x12...x1n+in−1a

1j+in222...)3 a expansão infinita com a1j+in = x0j+in − 1, então

deve-se provar que:

fn(x0) = fn(x

1)

[ 6 de julho de 2012 at 11:24 ]


De acordo com a notação introduzida anteriormente, tem-se:

fn(x0) = ((0,X01X

01+n...X01+in...)3,

...

(0,X0jX0j+n...X0j+in...)3,

...

(0,X0nX0n+n...X0n+in...)3),

fn(x1) = ((0,X11X

11+n...X11+in...)3,

...

(0,X1jX1j+n...X1j+in...)3,

...

(0,X1nX1n+n...X1n+in...)3).

Como nas duas expansões de x, x0k = x1k para k = 1, 2, ..., j+ in− 1, usando (4.3), conclui-se que:

X0k = X1k para k = 1, 2, ..., j+ in− 1.

Logo tem-se as igualdades para índices menores que j+ in. As igualdades para índices maioresou iguais a j+ in podem ser reduzidos a cinco casos apresentados a seguir:

Considerando Sx0j+in par (ou ímpar), então Sx0j+pn com p = i, i+ 1, ... tem a mesma paridadee Sx1j+pn com p = i, i+ 1, ... também tem a mesma paridade. É mostrado a seguir a igualdadeentre as coordenadas CX0j = CX1j , onde CXj = (0,XjXj+n...Xj+in...)3 com as devidas adaptaçõespara os sobrescritos quando existirem.

1º Caso: Quando a paridade de Sx0j+in for par, tem-se:

CX0j = (0,X0jX0j+n...x0j+in000...)3 = CX1j = (0,X0jX

0j+n...(x0j+in − 1)222...)3

2º Caso: Quando a paridade de Sx0j+in for ímpar, com xj+in = 1, tem-se:

CX0j = (0,X0jX0j+n...X0

j+(i−1)n1222...)3 = CX1j = (0,X0jX0j+n...X0

j+(i−1)n2000...)3

3º Caso: Quando a paridade de Sx0j+in for ímpar, com xj+in = 2, tem-se:

CX0j = (0,X0jX0j+n...X0

j+(i−1)n0222...)3 = CX1j = (0,X0jX0j+n...X0

j+(i−1)n1000...)3

Agora, considerando-se u 6= j e u ∈ {1, 2, ...,n} e p̄ = min{p ∈N ; u+ pi > j+ni}. Se Sx0u+p̄ntem paridade par (ou ímpar), então Sx0u+pn com p = p̄, p̄+ 1, ..., tem a mesma paridade e Sx1u+pn,com p = p̄, p̄+ 1, ..., tem todos paridade oposta.

[ 6 de julho de 2012 at 11:24 ]


Portanto,

4º Caso: Quando a paridade de Sx0u+p̄n for par, tem-se:

X0u = (0,X0uX0u+n...x0u+(p̄−1)n000...)3 = X1u = (0,X0uX0u+n...x0

u+(p̄−1)n000...)3

5º Caso: Quando a paridade de Sx0u+p̄n for ímpar, tem-se:

X0u = (0,X0uX0u+n...x0u+(p̄−1)n222...)3 = X1u = (0,X0uX0u+n...x0

u+(p̄−1)n222...)3

Exemplo: Nota-se que f3(x0) = f3(x1) para as duas expanções de x, x0 = (0, 1111200...)3 e

x1 = (0, 11111222...)3.

f3((0, 111) = ((0, 11000...)3,120 (0, 10222...)3,000 (0, 12222...)3)...)3

= f3((0, 111) = ((0, 11000...)3,112 (0, 11000...)3,222 (0, 1222...)3)...)3

A seguir verificare-se algumas regras vistas anteriormente nos casos 3º, 4º e 5º.

Neste exemplo temos j = 2, i = 1 e como:

3º) Sx02+1.3 = 1+ 1+ 1+ 1− 1 = 3 é ímpar, tem-se

CX02 = (0, 10222...)3 = CX21 = (0, 11000...)3

4º) Sx01+2.3 = 1+ 1+ 1+ 1+ 2+ 0− 1− 1 = 4 é par e Sx11+2.3 = 1+ 1+ 1+ 1+ 1+ 2− 1− 1 = 5

é ímpar, tem-se

X01 = (0, 11000...)3 = X11 = (0, 11000...)3

5º) Sx03+1.3 = 1+ 1+ 1+ 1+ 2− 1 = 5 é ímpar e Sx13+1.3 = 1+ 1+ 1+ 1+ 1− 1 = 4 é par,tem-se

X03 = (0, 1222...)3 = X13 = (0, 1222...)3

No artigo citado, prova-se que fn : [0, 1]→ [0, 1]n está bem definida e é, de fato, uma famíliade curvas de Peano, isto é, são funções contínuas e sobrejetivas.

4.1.1 Uma Restrição Discreta importante da família de funções de Peano

Uma restrição importante da família fnm é ao domínio discreto Dnm, definidos a seguir:

Dnm = (0, x1, x2, ..., xnm)3

e

[ 6 de julho de 2012 at 11:24 ]


fnm|Dnm : Dnm → [0, 1]n

é tal que

fnm|Dnm(x) = fnm(x).

O conjunto de valores de f2m ligando pontos consecutivos é a família de funções de Peanooriginalmente apresentada em "gráficos"por Peano. O número nm representa o número de casasdecimais da expansão.

A seguir é apresentado um gráfico de f2m e uma tabela, de acordo com a terminologia adotadana seção 4.1, com os valores calculados na base ternária de seus 30 primeiros elementos. No grá-fico, são deslocados os pontos de colisão para que se perceba a sequência de pontos consecutivos.

Figura 20: Gráfico gerado através da tabela de pontos gerada pela função f2m.

4.1.2 Funções de Peano do Círculo em [0, 1]n

Considere o conjunto S = {(x,y)|x = cos(t), y = sen(t), t ∈ [0, 2π]} e a função u(x,y) definida aseguir:

u(x,y) : S→ [0, 1] com

u(x,y) = t/2π, onde

x = cos(t) e y = sen(t)

Defini-se a família de funções gn(x,y):

gn(x,y) : S→ [0, 1]n,n = 1, 2, ...

[ 6 de julho de 2012 at 11:24 ]


Seja (x,y) ∈ S e u(x,y) ∈ [0, 1] escrito em expansão mista, com bases 2 e 3, definida do seguintemodo:

t = u(x,y) = (0, t1t2...tnt1+nt2+n...t1+in...tj+in...tn+in...)23

com tj ∈ {0, 1}, j = 1, 2, ...,n, tj+in, tj+1+in, ..., tn+in, i = 1, 2, ...

e u(x,y) =n∑j=1

xj2−j +

n,∞∑j,i−1

xj+in3−(j+in).

Definindo agora gn(x,y):

gn((0, t1t2...tnt1+nt2+n...t1+in...tj+in...)23) =

((0,X1X1+n...X1+in...)3, (0,X2X2+n...X2+in...)3, ...(0,XjXj+n...Xj+in...)3, ...),

onde j = 1, 2, ...n, i = 0, 1, 2, ... e

Xj+in = 1+ (−1)S(tj+in − 1), com

S =

j+in∑p=1

(tp + 1) +

p+qn<j+in∑p=1,q=1

tp+qn −

q<i∑q=1

tj+qn (4.4)

Esta é uma família de funções de Peano que transforma continuamente um círculo em umcubo de dimensão n, adiante é estudada suas propriedades. Afim de facilitar as aplicações,considera-se t = u(x,y) ∈ [0, 1] a função

hn = gnou−1(t) : [0, 1]→ [0, 1]n com h(0) = h(1)

As funções hn : [0, 1]→ [0, 1]n podem ser definidas do seguinte modo: seja t ∈ [0, 1] escrito emexpansão mista, com bases 2 e 3, definida do seguinte modo:

t = (0, t1t2...tnt1+nt2+n...t1+in...tj+in...)23

com tj ∈ {0, 1}, j = 1, 2, ...,n,

tj+in, tj+1+in, ..., tn+in ∈ {0, 1, 2}, i = 1, 2, ...

e t =

n∑j=1

tj2−j +

n,∞∑j,i=1

tj+in3j+in

Portanto,hn((0, t1t2...tnt1+nt2+n...t1+in...tj+in...)23) =

= ((0,X1X1+n...X1+in...)3), (0,X2X2+n...X2+in...)3, ...(0,XjXj+n...Xj+in...)3, ...

onde j = 1, 2, ...,n, i = 0, 1, 2, ... e

[ 6 de julho de 2012 at 11:24 ]


Xj+in = 1+ (−1)S(tj+in − 1), com S = 1+

k=j+in−1∑p=1,q=1

tk −

q=i−1∑q=0

tj+qm.

4.1.3 Área de Preenchimento da Função de Peano e Mudança de Base

Na seção anterior foi visto que n.m gera o número de casas decimais da expansão ternária oubinária. Esta seção mostra a extensão deste conceito para qualquer base ímpar.

Da expansão discreta da função de Peano visto na seção anterior, o artigo a ser publicado deJoaquim Elias de Freitas mostra a adaptação da fórmula (4.2) à

Xj+in = (B[k] − 1) + (−1)Sxj+in(2xj+in −B[k] + 1)/2,

com

Sxj+in =

j+in−1∑k=1

xk −

i−1∑q=0

xj+qn. (4.5)

onde B[k] é uma base ímpar qualquer, podendo ser alterada durante a geração da imagem dafunção. O valor de k é n ∗m, isto é, pode-se ter n ∗m bases ímpares. Esta adaptação aindapermite a utilização da base 2 na última iteração a ser feita, ou seja, B[n ∗m− 2] = B[n ∗m− 1] = 2

(uma na expansão finita e uma na expansão infinita). Em outros casos não é possível a aplicaçãoda base par, por não ser manter o critério da curva de não se auto intersectar.

Esta mudança de base garante a flexibilidade de preencher uma área com tamanhos variáveis.

No caso anterior, onde se tem uma expansão discreta na base ternária, o número 3nm indicaa quantidade de pontos que a função irá gerar. Com esta mudança de base, é possível gerarpontos que não sejam exclusivamente na base 3, o que faz garantir o bom uso desta função noprocessamento de imagens digitais.

A seguir é apresentado alguns exemplos das Curvas de Peano gerados pela função (4.4) e osparâmetros apresentados em cada caso, considerando sempre n = 2.

[ 6 de julho de 2012 at 11:24 ]


Figura 21: Curvas de Peano gerados pela função (4.4)

4.1.4 Aprimoramento da Compressão para Imagens 512x512

Foi visto na seção anterior que a variação das bases é de extrema importância para se podertrabalhar com imagens de dimensões diferentes. Como o processo de preenchimento da imagemdepende necessariamente de bases ímpares, dificulta ainda mais a escolha de bases tais que oproduto entre elas resulte na quantidade de pontos da imagem (largura x comprimento). Destaforma, com um estudo mais aprofundado, foi possível aprimorar este processo para imagens512x512. Tornando objetivos futuros, o aprimoramento para imagens de quaisquer dimensões e aautomatização das escolhas das bases sem a influência do usuário.

Diante de tal dificuldade, subdividiu-se a imagem 512x512 em 4 retângulos, onde é possívelobter a quantidade de pontos de cada retângulo através do produto de bases ímpares, ou seja,cada retângulo tem o seu conjunto de bases. Somando as áreas de todas os retângulos, obtem-se aárea da imagem original. Desta forma foi sanada a impossibilidade de se trabalhar com imagensde dimensões 512x512 com as características inicialmente definidas.

[ 6 de julho de 2012 at 11:24 ]


Para tal resultado, foi necessário adaptar o algorítmo e implantar a escolha das bases na forma:

m[0] = 4;B[1][2] = 11;B[1][3] = 11;B[1][4] = 7;B[1][5] = 7;B[1][6] = 3;B[1][7] = 3;B[1][8] =2;B[1][9] = 2; (1ª Retângulo)

m[1] = 3;B[2][2] = 77;B[2][3] = 5;B[2][4] = 3;B[2][5] = 5;B[2][6] = 2;B[2][7] = 2; (2ª Retângulo)



Portanto, a quantidade de pontos representada por este modelo é dada pela soma do produtodas bases de Peano de cada retângulo. O resultado desta soma é 512x512, como anteriormentefoi afirmado.

Esta maneira de processar uma imagem 512x512 está integrada ao software como soluçãoaprimorada e que será futuramente estudada para imagens de quaisquer dimensões e até, au-tomatizar este processo, isto é, o soft escolher automaticamente as bases para as imagens dequaisquer dimensões.

[ 6 de julho de 2012 at 11:24 ]

Parte V

PA RT E V: F U N Ç Ã O D E P E A N O E WAV E L E T 1 D E MP R O C E S S A M E N T O D E I M A G E N S E U M A I N T E R FA C E

G R Á F I C A PA R A O U S Á R I O

[ 6 de julho de 2012 at 11:24 ]

Capítulo5F U N Ç Ã O D E P E A N O E WAV E L E T 1 D E M

P R O C E S S A M E N T O D E I M A G E N S E U M A I N T E R FA C EG R Á F I C A PA R A O U S Á R I O

[ 6 de julho de 2012 at 11:24 ]

5F U N Ç Ã O D E P E A N O E WAV E L E T 1 D E M P R O C E S S A M E N T O D EI M A G E N S E U M A I N T E R FA C E G R Á F I C A PA R A O U S Á R I O

5.1 compressão de imagens

Nas últimas décadas, a necessidade de compressão de dados com uma alta taxa de compressãose tornou muito necessária. O requerimento básico de qualquer método de compressão é que sepossa mudar rapidamente as informações originais e vice- versa.

Há dois tipos de compressão: compressão sem perda e compressão com perda.

Compressão sem perda: é normalemte aplicada quando a qualidade e a fidelidade da imagem sãoimportantes e devem ser mantidas, consistindo na recuperação das informações sem perdas daqualidade, ou seja, os coeficientes eliminados não compromentem o processo de reconstruçãoA. X. Falcão[2].

Compressão com perda: é utilizada quando a portabilidade e a redução do tamanho da imagemsão mais importantes que a qualidade visual, sem no entanto menosprezá-la, neste caso podeocorrer perda de informações. Este problema pode ser contornado desde que a decomposiçãoseja aceitável. Esse tipo de compressão permite que os fatores de resolução sejam atingidos emum grau maior, porém, só poderá ser usada quando os dados originais forem substituídos poruma aproximação fácil de comprimir A. X. Falcão[2]. Normalmente o uso de transformada estáassociado a métodos com perda.

A idéia geral de representar os dados é utilizar uma base matemática. Tal base deve satisfazercertas condições, como boa localização no tempo e na frequência, tornando os coeficientes muitopequenos ? [? ]).

O uso da TW no processo de compressão faz com que coeficientes que são menores de umdeterminado valor possam ser eliminados sem comprometer a reconstrução da imagem. Destaforma, o número de coeficientes significativos para a reconstrução do sinal se torna cada vezmenor e as informações mais importantes estão concentradas nesse conjunto. Porém, há certosrequisitos para satisfazer as condições de um algoritmo baseado em compressão atual.[4]:

1) ser independente dos dados;2) ter um baixo custo computacional;3) ser capaz de remover a correlaçao para um conjunto grande de dados.

51

[ 6 de julho de 2012 at 11:24 ]

5.2 sistema de armazenamento de imagens através da transformada wavelet 52

As bases de funções wavelets se encaixam nessas condições, tornando-se uma alternativa detrabalho. A compressão de imagens usando a TW segue três passos descritos a seguir.

1) calcular os coeficientes através de um algoritmo rápido tanto na decomposição quanto nareconstrução, a partir de seus coeficientes do filtro.

2) produzir uma sequência em ordem decrescente do valor dos coeficientes, podendo usarfunções bases para normalizar e usar qualquer técnica padrão;

3) estipular um erro, onde qualquer busca padrão poderá ser usada. Porém, para imagens,grandes escolhas tornam o processo lento.

Em geral, a compressão de uma imagem consiste na eliminação dos coeficintes redundantesno domínio transformado, que são trocados por zero. A imagem comprimida é armazenada nodomínio transformado e, para tanto, a sua recuperação deve ser feita usando a transformadainversa.

5.2 sistema de armazenamento de imagens através da transformada wavelet

Quando a Transformada Wavelet é aplicada a uma imagem, ela a decompõe em vários níveis deresolução, devido à Análise de Multirresolução J. F. Silvia[16]. Após a decomposição completa daimagem, sua energia está concentrada em poucos coeficientes wavelet, ou seja, a imagem podeser reconstruída usando apenas estes coeficientes, praticamente sem perda de informações.

Através da análise do histograma que será apresentada, permite analizar a faixa de coeficientesque se deseja desprezar. Os coeficientes próximos de zero, influenciam muito pouco na qualidadeda imagem, desta forma, pode-se desprezá-los afim obter uma boa compressão.

O algoritmo proposto neste trabalho cria um vetor apenas para o armazenamento dos coefici-entes significativos para a reconstrução da imagem. Através desse vetor, é possível reconstruira imagem original. Além do valor de cada coeficiente não eliminado pelo limiar escolhido nohistograma, é necessário que este vetor contenha também informações como a dimensão daimagem e a posição dos coeficientes na imagem original.

5.2.1 Codificação da Imagem Comprimida

A Transformada Wavelet, usada nesse trabalho, é a Transformada Wavelet Discreta Unidimensio-nal e, a escala de resolução usada nas imagens é a escala por linha, ou seja, a cada autoresoluçãoapresenta-se a imagem resultante e os detalhes retirados pela transformada Wavelet.

A primeira componente desse vetor deverá ser a dimensão do vetor que representa a imagem,ou seja, largura x altura. A partir da segunda componente, os coeficientes já podem ser armaze-nados. Como a imagem processada contém muitos zeros, para se obter uma boa compressão,cada coeficiente deverá trazer consigo a distância até o próximo elemento diferente de zero,este procedimento continua até codificação de todo o vetor. A seguir, é feita uma ilustração dofuncionamento desse sistema de armazenamento para um vetor de 20 posições.

[ 6 de julho de 2012 at 11:24 ]

5.2 sistema de armazenamento de imagens através da transformada wavelet 53

Seja A, um vetor, ~A sua versão decomposta pela Transformada Wavelet Discreta (TWD) e AL ovetor após a escolha da faixa dos coeficientes a serem desprezados.

A = (∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗, ∗)→ TWD

→ ~A = (∗, ∗,o,o,o, ∗,o, ∗,o,o,o, ∗, ∗, ∗,o,o,o, ∗,o,o)

Em ~A, os coeficientes representados por ∗ são coeficientes significantes, enquanto que os queestão representados por 0 podem ser eliminados.

Supondo que os coeficientes que podem ser eliminados trazem poucas informações a imagem,ou seja, são próximos de zero, é indicado desprezá-los através da análise no histograma. Destaforma, o vetor AL resultante é o seguinte:

AL = (∗, ∗, 0, 0, 0, ∗, 0, ∗, 0, 0, 0, ∗, 0, ∗, 0, 0, 0, ∗, 0, 0)

O vetor AL é um vetor esparso com poucos coeficientes, por isso só há a necessidade dearmazenar os coeficientes não-nulos. Assim, o vetor que representaria o vetor comprimido seria:

Vcod = (20, ∗, ∗, 3, ∗, 2, ∗, 3, ∗, 2, ∗, 3, ∗)

sendo que o número 20 na primeira posição indica a dimensão do vetor. Após os dois primeiroselementos *, o número 3 indica que o próximo coeficiente diferente de zero se encontra auma distância 3 do anterior e, assim por diante. Dessa forma, para um vetor transformado ecomprimido de ordem N, o vetor Vcod seria escrito da seguinte maneira:

Vcod = (N, ∗,d, ∗, ...)

sendo d a distância de um elemento diferente de zero a outro elemento também diferente de zero.

O vetor Vcod pode ser gerado na mesma rotina que faz a eliminação dos coeficientes escolhidosna análise do histograma, pois nesta rotina há a identificação dos coeficientes que estão acima dolimiar. Logo, o custo computacional para gerar este vetor será desprezível.

O vetor Vcod é a versão compactada do vetor no domínio Wavelet.

5.2.2 Decodificação da Imagem Comprimida

O procedimento de reconstrução do vetor, a partir do vetor Vcod, também é muito simples. Aordem do vetor é o valor do primeiro elemento do vetor Vcod. Portanto, o primeiro passo é acriação de um vetor nulo cuja ordem seja igual ao primeiro elemento do vetor Vcod.

[ 6 de julho de 2012 at 11:24 ]

5.3 função de peano e wavelet 1d em processamento de imagens e uma interface gráfica para o usuário 54

A partir do primeiro elemento, tem-se a tarefa de colocar cada coeficiente em seu lugar originalno vetor inicial. Como os coeficientes da imagem variam em uma escala de −1 a 1 e não existedistância 1 no processo, não há perigo de confusão entre distância e coeficiente.

Desta forma, se o primeiro elemento após a dimensão do vetor pertencer a escala, significaque este será o primeiro coeficiente do vetor, caso contrário, o número fora da escala indicará aque distância estará o primeiro elemento diferente de zero. Como o vetor de decodificação foiiniciado como vetor nulo, basta repetir este procedimento para cada elemento do vetor Vcod, ouseja, a cada distância d, substitui o 0 do vetor de decodificação pelo elemento que vem após oelemento que representa a distância d no vetor Vcod.

Cada dois elementos representam, respectivamente, o valor do coeficiente preservado no vetortransformado e sua localização no vetor de domínio wavelet, então basta usar esses dois valorespara localizar e posicionar o coeficiente no seu lugar no vetor nulo criado incialmente. Apóso preenchimento de todos os elementos do vetor, aplica-se sobre este a transformada waveletdiscreta inversa (TWDI).

5.3 função de peano e wavelet 1d em processamento de imagens e uma inter-face gráfica para o usuário

O uso da Função de Peano no processamento de uma imagem consiste em percorrer todos ospontos da imagem continuamente e sem autointerseções, isto evita o problema das condições decontorno periódicas encontrados ao se aplicar as Wavelets.

No final deste processo de varredura da imagem, gera-se um vetor contendo LxC (larguraX-Comprimento da imagem) elementos.

Dentre as diversas curvas apresentadas por Peano que poderiam fazer este papel de percorreros pontos da imagem, utiliza-se nesse trabalho a curva apresentada a seguir:

[ 6 de julho de 2012 at 11:24 ]

5.4 interfaces gráficas para o sistema de armazenamento de imagens comprimidas 55

Figura 22: Curva de Peano discretizada

A curva acima foi gerada utilizando a função (4.5) definida na seção 4:

Xj+in = (B[k] − 1) + (−1)Sxj+in(2xj+in −B[k] + 1)/2,

com

Sxj+in =

j+in−1∑k=1

xk −

i−1∑q=0

xj+qn.

e os parâmetros: n = 2; m = 6.

Como n ∗m = 12, pode-se escolher 12 valores para B, no caso acima tem-se: B[i] = 3, i = 0..9,B[n ∗m− 2] = B[n ∗m− 1] = 2.

Está curva foi escolhida por apresentar uma maior proximidade dos pontos vizinhos, aumentando-se desta forma, a correlação entre os pixels, o que melhora a compressão da imagem.

Ao se usar esta curva, armazena-se os pontos da imagem em um vetor, ou seja, tem-se aimagem linearizada. Em seguida aplica-se a Transformada Wavelet 1D para decompor a imagemem coeficientes Wavelets. Afim de obter uma boa decomposição, foi implatado o processo deautoresolução, escolha da faixa de comprimento de onda a ser desprezada e o uso da variação depontos da base de Daubechies a cada autoresolução.

A seguir é apresentado a interface gráfica ao usuário, mostrando todas as funcionalidades doprograma.

[ 6 de julho de 2012 at 11:24 ]


Figura 23: Interface Gráfica

5.4 interfaces gráficas para o sistema de armazenamento de imagens compri-midas

Neste trabalho, são utilizadas imagens de tamanho 512x512 e no formato ppm, para este caso éapresentado um estudo para a melhor base Wavelets e a melhor base de Peano, afim de obter omelhor tempo de execução do software, a melhor qualidade da imagem recuperada e a melhorcompressão. O software também possibilita trabalhar com outros formatos de imagem, bastandopara isto uma pequena variação de escala em cada bit da imagem, como também possibilitaimagens de outras dimensões, necessitando neste caso, a escolha do m e das bases de Peano.Cabe, em trabalhos futuros, o apefeiçoamento para automatizar este processo.

Inicialmente, apresenta-se a interface acima sem usar o aperfeiçoamento. Seguem, então, ospassos que devem ser tomados para obter a compressão de uma imagem:

[ 6 de julho de 2012 at 11:24 ]


(1) Escolha da imagem. O usuário poderá entrar com qualquer imagem ppm ou pgm, além doconjunto de exemplos fornecidos pelo sistema;

(2) As dimensões da imagem (altura e largura);

(3) O número de Autoresoluções;

(4) A escolha da quantidade de pontos da base de Daubechies, neste caso, tem-se o defaultque consta na imagem acima. Note que há mudanças de base em algumas autoresoluções. Oconveniente é começar com a máxima quantidade de pontos, já que na primeira resolução asondas possuem um grande comprimento de onda e tendem a diminuir a cada autoresolução, jáque a quantidade de pontos vai se reduzindo a metade.

(5) As bases de Peano. Neste caso também foi optado pelas que estão na interface acima. Vejaque é a mesma curva apresentada na figura 24, havendo uma mudança apenas no valor de m,sendo utlizado aqui m = 6 com 3 nas bases adicionadas. Isto faz com o que o produto das basesse aproxime à quantidade de pontos da imagem. Neste exemplo, usando estas bases e sem oaprimoramento, obtem-se uma imagem de dimensões 486x486, ou seja, as dimensções foramtruncadas em relação a imagem orginal. O soft também possibilita trabalhar com m > 6 ou basesímpares que não sejam apenas 3, de forma a preencher uma região de dimensões maiores que512x512. Neste caso, a imagem 512x512 fica interior a um quadro de dimensões maiores, onde ospixeis fora da imagem tem valor 1. Com isto, não se perde os dados da imagem, mas prejudica ataxa de compressão e cria-se problemas na borda da imagem, o que não é a intenção deste trabalho.

Após o preenchimento da interface acima, clica-se em ok. Em poucos segundos é apresentadoo histograma para a escolha dos coeficientes a serem processados.

[ 6 de julho de 2012 at 11:24 ]


Figura 24: Histograma dos coeficientes

Na figura acima, nota-se que na proximidade do zero contém uma grande quantidade depontos, estes pontos influenciam pouco na qualidade da imagem e são estes os que devem serdesprezados no processamento. Neste exemplo, deixa-se passar todos os pontos, para isto, bastaum click com o botão esquerdo do mouse numa região anterior a todos os coeficientes, isto gerauma reta vertical vermelha no ponto onde houve o click. Como a intenção é selecionar todos oscoeficientes, clica-se com o botão direito do mouse em qualquer lugar a direita da reta criada detal forma a selecionar todo o histograma. A tela a seguir mostra a seleção realizada.

[ 6 de julho de 2012 at 11:24 ]


Figura 25: Seleção dos coeficientes a serem processados

Após clicar no botão avançar, é gerada a interface com o processamento da imagem a cadaautoresolução.

[ 6 de julho de 2012 at 11:24 ]


Figura 26: Interface Pós-Processamento

Na primeira imagem inferior da segunda coluna, tem-se a imagem original. Na primeira colunade baixo para cima, apresenta-se a cada autoresolução, a imagem resultante a cada processa-mento Wavelet 1D; e na segunda coluna, os detalhes retirados a cada processamento. A cadaautoresolução, a quantidade de pontos da imagem se reduz a metade.

Nesta interface, é possível escolher os detalhes na coluna 2 à serem adicionados à imagemresultante da última autoresolução. A adição destes detalhes melhora a qualidade da imagem,e por consequência, diminui a compressibilidade. Cabe ao usuário indentificar as imagens deacordo com a sua necessidade. O duplo click com o botão esquerdo do mouse, mostra a imagemno seu tamanho padrão.

Apresenta-se a seguir a escolha de alguns detalhes para observar a funcionalidade do programa.Então, para realizar a seleção das imagens, clica-se com o botão direito do mouse nos quadrosque se deseja adicionar. As imagens selecionadas apresentam a borda vermelha, como segue nafigura:

[ 6 de julho de 2012 at 11:24 ]


Figura 27: Composição das imagens selecionadas

Após a seleção, clica-se no botão atualizar, isto faz renderizar todas as imagens, ou seja,reapresenta-se a interface com a imagem resultante da soma das imagens selecionadas, ao lado daimagem original. Como se percebe, a imagem resultante da última autoresolução, deve-se sempreser somada para se obter uma imagem razoálvel. A soma apenas dos detalhes, não reconstróiuma imagem nítida. A soma de uma imagem com o seu detalhe, gera a imagem da autoresoluçãoanterior; Por sua vez, a adição de todos os detalhes contrói a imagem original, desde que nãotenha ocorrido seleção da faixa dos coeficientes a serem desprezados, como neste exemplo.

No quadro à direita da interface, é apresenta algumas propriedades sobre o processamento deimagens. São elas:

# PSNR

O PSNR (Peak Signal Noise Ratio) é uma relação entre o máximo possível de potência deum sinal, pela potência do ruído, quando se tem um sinal antes e depois de um processo dedegradação, sendo que a unidade utilizada para representa-lo é o dB (decibel). Aplicando esteconceito em vídeos e imagens, o PSNR é a relação entre a entrada e a saída de um processo decompressão com perdas, que avalia o quanto a compressão introduziu ruídos na imagem ouframe original. Matematicamente o PSNR de uma imagem de dimensão m por n é definido por:

PSNR = 10.log

(MAX2IMSE

)= 20.log

(MAXI√MSE

)onde MAX é o valor máximo possível de um pixel e MSE (Mean Square Error - Erro médioquadrado):

[ 6 de julho de 2012 at 11:24 ]


MSE =1

MN

m−1∑i=0

n−1∑j=0

||I(i, j) −K(i, j)||2

Desta forma, quanto maior o valor do PSNR, maior é a relação entre a potência do sinal pelapotência do ruído, o que significa melhor qualidade. Em termos gerais, valores de PSNR acimade 42dB correspondem à compressões que introduzem perdas imperceptíveis ao olho humano, oque significa uma qualidade excepcional. Considera-se que imagens com PSNR acima de 36dBtem qualidade bastante aceitável, entre 30dB e 36dB apresenta uma qualidade mediana e abaixode 30dB a qualidade já é bem ruim.

Com esta propriedade, é possível controlar a faixa de coeficientes a serem eliminados, de talforma a obter uma boa qualidade de imagem.

# Energia do Sinal

Intuitivamente, a energia é uma medida da amplitude de um sinal. Quanto maiores forem osvalores da amplitude, maior é a energia do sinal. Na interface tem-se o percentual entre a energiado sinal original e do sinal processado. Este valor é calculado pela fórmula:

E =Norma do sinal processado

Norma do sinal originalX100

Se x é um vetor de dimensão n que representa um sinal, a norma (N) de x é calculada por

N =

√√√√ n∑i=1

x2i

.Neste trabalho, o percentual da energia do sinal indica o quanto a amplitude foi preservada no

processamento. Este valor se torna importante, uma vez que as ondas de alta amplitude trazemas informações mais importantes para a qualidade da imagem.

# A Taxa de Compressão

A taxa de compressão C, em porcentagem, é a razão entre o número de coeficientes eliminadose o número total de coeficientes, definida por:

C =CelTx100

sendo Cel o número de coeficientes eliminados e T , o número total de coeficientes.

# Número de Coeficientes da Imagem Original

Representa o número de coeficientes da imagem antes do processamento.

# Número de Coeficientes da Imagem Resultante

[ 6 de julho de 2012 at 11:24 ]


Representa o número de coeficientes da imagem pós-processamento.

# Número de Bits da Imagem Original

Representa o número de bits da imagem antes do processamento.

# Número de Bits da Imagem Processada

Representa o número de bits da imagem pós-processamento.

# Redução do Número de Bits

Representa a redução do número de bits da imagem após o processamento.

# Normas

A norma tem a propriedade de indicar a energia do sinal em cada imagem processada porautoresolução.

Em seguida, apresenta-se a interface com o aprimoramento e com uma escolha da faixa decomprimento de onda a ser desprezada durante o processamento.

Figura 28: Interface Gráfica com aprimoramento ativo

Escolhendo-se a faixa de coeficientes:

[ 6 de julho de 2012 at 11:24 ]


Figura 29: Seleção da faixa de coeficientes a serem processados

Exibição das imagens processadas:

[ 6 de julho de 2012 at 11:24 ]


Figura 30: Interface pós-processamento

Clicando-se sobre quaisquer uma das imagens, apresenta-se uma nova janela com a imagemampliada. A seguir, é mostrado a comparação visual entre a imagem original e a processada noseu tamanho padrão. Tais imagens é representada na última linha da interface acima.

[ 6 de julho de 2012 at 11:24 ]


Figura 31: (a) Imagem pós-processamento; (b) Imagem original

Nestas imagens, percebe-se a diferença mínima na qualidade da imagem sob uma grandediferença da quantidade de coeficientes resultantes. A imagem original possui 264.144 coeficientes,enquanto a processada 13.464 coeficientes. Em bits, houve uma redução de 2.359,296 bits para92.341,625 bits, ou seja, uma redução de aproximadamente 96% sob uma taxa de compressão de94.8%.

[ 6 de julho de 2012 at 11:24 ]

Parte VI

PA RT E V I : C O N C L U S Ã O

[ 6 de julho de 2012 at 11:24 ]

Capítulo6C O N C L U S Ã O

[ 6 de julho de 2012 at 11:24 ]

6C O N C L U S Ã O

Neste trabalho foi proposto um sistema de armazenamento de imagens, que por sua vez sãocomprimidas usando a Função de Peano e a Transformada Wavelet 1D com o objetivo de reduziro espaço de memória computacional utilizado para armazenamento de imagens. Este sistemaarmazena apenas os coeficientes que não são eliminados na compressão, suas posições e adimensão desta imagem. Tornando assim bem menor o espaço utilizado para armazená-la. Deacordo com o conjunto de imagens usado para testes, este sistema reduz em torno de 95% o espaçode armazenamento da imagem. Embora o sistema de armazenamento tenha sido implementadona linguagem java, o mesmo pode ser feito em qualquer linguagem de programação e paracompressão de imagens usando qualquer tipo de técnica, não apenas as técnicas baseadasna transformada wavelet. Também foi proposta uma interface gráfica para o processamentode imagens com o objetivo de proporcionar o acesso ao processamento de imagens a todotipo de usuário de computadores, principalmente aqueles que não têm domínio de nenhumalinguagem de programação. A interface proposta permite ao usuário selecionar uma imagempara processamento, escolher a faixa de coeficientes a serem desprezados no processamento daimagem, comparar visualmente as imagens, original e processada, analisar os dados referentes àoperação realizada e salvar a imagem processada. Como sugestão para futuros trabalhos, estáa questão do processamento de imagens coloridas, pois a interface proposta processa apenasimagens em tom cinza. E, a possibilidade de uma interface onde se possam fazer as escolhasautomáticas das bases de Peano.

69

[ 6 de julho de 2012 at 11:24 ]

R E F E R Ê N C I A S B I B L I O G R Á F I C A S

[1] J. R. Buck; A. V. Oppenheim, R. W. Schafer. Discrete-time signal processing. New Jersey: PrenticeHall. 1998. (Citado na pagina 15.)

[2] N. J. Leite A. X. Falcão. Fundamentos de Processamento de Imagem Digital. Campinas: Unicamp.1998. (Citado na pagina 51.)

[3] M. P. Albuquerque. Processamento de imagens: métodos e análises. Rio de Janeiro: FACET. 2001.(Citado na pagina 13.)

[4] Cenário atual. Rio de Janeiro: Pontifica Universidade Católica. Centro Digitalde Referência. 2004. p. 1-15. Disponível em: < http://www.maxwell.lambda.ele.puc-rio.br/cgi-bin/PRG0599.EXE/76263.PDF?NrOcoSis = 22053CdLinPrg = pt >

.2004.(Citadonapagina 51.)

[5] J. Eyng; A.V. Silva. Wavelets e wavelet de packets. In: SEMINÁRIO VISÃO COMPUTACIONAL,2, 2000, Florianópolis. Visão computacional... Florianópolis: PPGCC - INE - UFSC. 2000. (Citadona pagina 24.)

[6] S. S. C. Botelho. Processamento digital de imagens: conceitos básicos de imagens. 2005. (Citado napagina 8.)

[7] R. Coifman. Adapted multiresolution analysis, computation, signal processing and operator theory.In: CONGRESS OF MATHEMATICIANS, Kioto. Proceedings... Kioto:(s.n.), p. 879-887. 1990.(Citado na pagina 19.)

[8] I. Daubechies. The wavelet transform, time frequency localization and signal analysis. IEEETransactions on Information Theory, New York, v.36, p.961-1005. 1990. (Citado na pagina 15, 19,and 29.)

[9] I. Daubechies. Ten lectures on wavelets. Philadelphia: SIAM Books. 1992. (Citado na pagina 4,19, 20, and 27.)

[10] I. Daubechies. Orthonormal bases of compactly supported wavelets. Communications on Pure andApplied Mathematics, New York, v. 41, p. 909-996. 1998. (Citado na pagina 19 and 26.)

[11] M. A. Duarte. Redução de ruído em sinais de voz no domínio Wavelet. 2005. 105 f. Tese (Doutorado)-Faculdade de Engenharia, Universidade Estadual Paulista, Ilha Solteira. 2005. (Citado na pa-gina 15.)

[12] D. H. Salentin; E. J. Stollnits, T. D. Derose. Wavelets for computer graphics theory and applications.2004. (Citado na pagina 4.)

[13] D. H. Salesin; E. J. Stollnits, T. D. Derose. Wavelets for computer graphics theory and applications.San Francisco: Morgan Kaufmann Publishers. 1996. (Citado na pagina 15 and 27.)

[14] R. R. A. Faria. Wavelets e as artes multirresolucionárias. 1997. (Citado na pagina 19.)

[15] A. Haar. Zur theorie der orthogonalen functionen-systeme. Mathematische Annalen, Berlin, v.69, p.331-371. 1910. (Citado na pagina 20.)

70

[ 6 de julho de 2012 at 11:24 ]

referências bibliográficas 71

[16] F. Villarreal W.C Soares; J. F. Silvia, M. A. Duarte. Processamento digital de imagens e atransformada Wavelet. In: BRAZILIAN CONFERENCE ON DYNAMICS, CONTROL ANDTHEIR APPLICATIONS. 2007. (Citado na pagina 4 and 52.)

[17] S. Goldstein; J. Gomes, L. Velho. Wavelets: teoria, software e aplicações. São Paulo: IMPA. 1997.(Citado na pagina 3 and 26.)

[18] E. P. Somoncelli; J. Portilla. Image denoising via adjustment of wavelet coefficient magnitudecorrelation. p.277-280. 2000. (Citado na pagina 3.)

[19] R. P. Kosloski. Wavelet: um estudo e aplicação à detecção e caracterização de distúrbios em sistema deenergia elétrica. 2000. 84 f. Dissertação (Mestrado) Faculdade de Engenharia, Universidade EstadualPaulista, Ilha Solteira. 2000. (Citado na pagina 29.)

[20] G. Oppenheim J. Poggi; M. Misiti, Y. Misiti. Matlab: wavelet toolbox user’s guide. Natick: MathWorks. 1996. (Citado na pagina 4, 21, and 24.)

[21] A. G. Melo; M. P. Albuquerque, E. S. Caner. Análise de imagem e visão computacional. Rio deJaneiro: CBPF. 2004. (Citado na pagina 10.)

[22] S. Mochizuki. Real Time Optimization: Classification and Assesment. 2004. (Citado na pagina 3.)

[23] Y. Nievergelt. Wavelets made easy. Boston: Bikhäuser. 1999. (Citado na pagina 22.)

[24] M. Vetterli; O. Rioul. Wavelets and signal processing. IEEE Signal Processing Magazine, New York,v.8, n.4, p. 14-38. 1991. (Citado na pagina 19.)

[25] S. Arie C. P Melo; P. R. C. Alcocer, S. S. Furuir. A DICOM graphic user interface for PC’s:towards a hierarchical system for dynamic digital angiographic image storage and visualization. RBERevista Brasileira de Engenharia. Caderno de Engenharia Biomédica, Rio de Janeiro, v.12, p.191-201.1996. (Citado na pagina 12.)

[26] S. Quake M. V. Wickerhauser; R. Coifman, Y. Meyer. Signal processing and compression withwavelet packets. In: MEYER, Y.; ROQUESED, S. Progress in wavelet analysis and applications. p.77-93. 1993. (Citado na pagina 19.)

[27] R. C. Gonzáles; R. E. Woods. Digital image processing. (s.l.): Publishing Company. 1992. (Citadona pagina 8.)

[28] R. C. Gonzáles; R. E. Woods. Processamento de imagens digitais. São Paulo: Edgard Blucher. 2000.(Citado na pagina 12.)

[29] R. K. Young. Wavelet theory and its applications. Boston: Kluwer Academic Publisher. 1995.(Citado na pagina 25.)

[ 6 de julho de 2012 at 11:24 ]

Documents

Compressão de Imagens Usando a Função de Peano e a ... · A interface gráﬁca, os programas de processamento de imagens via Função de Peano e a Transformada Wavelet 1D foram