Restauração de Imagens Utilizando Processamento Paralelo

Prévia do material em texto

UNIVERSIDADE FEDERAL DO RIO DE JANEIRO
ESCOLA DE ENGENHARIA
DEPARTAMENTO DE ELETRÔNICA E DE COMPUTAÇÃO
Autor:
Jaime Grande Vela
Orientador:
D. Sc. Eugenius Kaszkurewicz
Co-orientador:
Ph. D. Antônio Petraglia
Examinador:
Ph. D. Amit Bhaya
RESTAURAÇÃO DE IMAGENS MONOCROMÁTICAS 
UTILIZANDO PROCESSAMENTO PARALELO
DEL
Setembro de 2007
AGRADECIMENTO
Gostaria de agradecer a colaboração das pessoas que contribuíram na conclusão da minha for-
mação como engenheiro e sem as quais a realização deste projeto não teria sido possível.
Ao meu Orientador de Projeto de Fim de Curso Eugenius Kaszkurewicz, pela sua paciência, 
motivação e constante apoio, assim como meu co-orientador, Antônio Petraglia.
Aos meus pais pelo constante apoio e confiança que sempre depositaram em mim.
ii
RESUMO
Este trabalho tem por objetivo viabilizar o processamento e restauração de imagens que sofre-
ram efeitos de degradação, utilizando para tanto, algoritmos e redes neurais implementados 
em computadores paralelos. 
A necessidade de se dispor de algoritmos que possam restaurar imagens que sofreram degra-
dações utilizando a computação paralela, deve-se ao alto custo computacional dessas restau-
rações num ambiente seqüencial, especialmente nos casos em que se lida com imagens de alta 
resolução.
A quantidade de dados a ser processada nesses casos é elevada, o que torna o processamento 
seqüencial lento em ambiente computacional convencional. Assim, algoritmos paralelos mos-
tram-se como soluções adequadas.
As degradações de imagens podem ser de diversos tipos: perda de foco, deslocamento, ausên-
cia ou excesso de iluminação e ruído. A tecnologia de obtenção e transmissão de imagens tem 
imperfeições, o que provoca distorção de algum tipo. 
Neste trabalho consideramos que as distorções sofridas pelas imagens são invariantes no es-
paço, ou seja, todos os pixels (unidade mínima de discretização de uma imagem) da imagem 
sofreram o mesmo tipo de distorção e podem ser descritos por modelos lineares. Os modelos 
utilizados podem ser resolvidos pela utilização de algumas classes de métodos iterativos, que 
na realidade constituem-se em especializações de redes neurais. A opção pelos métodos itera-
tivos em relação aos diretos se deve à facilidade e conveniência de paralelização.
São apresentadas as equações integrais que descrevem o modelo contínuo e linear de forma-
ção da imagem, e a discretização da equação recaindo numa equação que descreve um modelo 
de sistema linear. Também são introduzidas as classes de métodos iterativos que podem solu-
cionar o problema e que atendem ao critério de convergência e as variações da matriz degra-
dação de acordo com o tipo de distorção sofrida pela imagem.
Apresenta-se e analisa-se a proposta de uma solução paralela para a recuperação de imagens, 
utilizando uma rede neural baseada no método iterativo de Jacobi, assim como no método de 
Polyak.
São apresentados os resultados computacionais com as curvas de desempenho do algoritmo 
paralelo quando aplicado às imagens submetidas a diferentes tipos de degradação.
iii
PALAVRAS-CHAVE
Restauração de imagens
Processamento de imagens
Distorção de imagens
Processamento paralelo
Métodos iterativos
iv
SUMÁRIO
 Figura 2.1: Convenção dos eixos para representação de imagens digitais. 4 ........................ viii 
 Figura 2.2. Matriz imagem e máscara. 6 ................................................................................ viii 
 Figura 2.3. Aplicação de filtros. 6 .......................................................................................... viii 
 Figura 2.4: Máscara 3x3 7 ...................................................................................................... viii 
 Figura 2.5: Máscara 5x5 (k = 25). 8 ....................................................................................... viii 
 Figura 2.6: Imagem da Lena sem degradação. 8 .................................................................... viii 
 Figura 2.7: Imagem da Lena após a filtragem (filtro de média 5x5). 8 .................................. viii 
 Figura 2.8: Máscara 5x5 (k = 65). 8 ....................................................................................... viii 
 Figura 2.9: Imagem da Lena sem degradação. 9 .................................................................... viii 
 Figura 2.10: Imagem da Lena após a filtragem (filtro Gaussiano 5x5). 9 .............................. viii 
 Figura 2.11: Representação gráfica do cálculo da mediana de um vetor. 9 ........................... viii 
 Figura 2.12: Imagem da Lena com ruído (Salt & Pepper 4%). 10 ......................................... viii 
 Figura 2.13: Imagem da Lena após a filtragem (filtro de Mediana 3x3). 10 .......................... viii 
 Figura 2.14: Formação de uma imagem pela passagem de radiação num meio não ideal. 10
 viii 
 Figura 2.15: Representação esquemática do sistema de formação de uma imagem. 12 ........ viii 
 Figura 2.16: Representação gráfica do rearranjo lexicográfico de uma matriz M. 12 ........... viii 
 Figura 2.17: Lena original. 14 .................................................................................. viii 
 Figura 2.18: Lena após filtro Motion Blur de 10 pixels e 0°. 14 ............................................ viii 
 Figura 2.19: Lena original. 14 .................................................................................. viii 
 Figura 2.20: Lena após filtro Motion Blur de 15 pixels e 0°. 14 ............................................ viii 
 Figura 2.21: Lena original. 15 .................................................................................. viii 
 Figura 2.22: Lena após filtro Motion Blur de 21 pixels e 0°. 15 ............................................ viii 
 Figura 2.23: Representação gráfica do comprimento da distorção. 15 .................................. viii 
 Figura 2.24: Distorção aplicada com um ângulo de 45°. 15 ................................................... viii 
 Figura 2.25: Distribuição dos pesos da distorção aplicada a 45°. 15 ..................................... viii 
 Figura 2.26: Lena original. 16 ................................................................................ viii 
 Figura 2.27: Lena após filtro Motion Blur de 10 pixels e 45°. 16 .......................................... viii 
 Figura 2.28: Lena original.17 ............................................................................... viii 
 Figura 2.29: Lena após filtro Motion Blur de 15 pixels e 45°. 17 .......................................... viii 
 Figura 2.30: Lena original. 18 ................................................................................ viii 
 Figura 2.31: Lena após filtro gaussiano 4 pixels de raio e σ = 2. 18 ...................................... viii 
 Figura 2.32: Matriz Toeplitz com valores crescentes. 18 ....................................................... viii 
 Figura 2.33: Matriz Toeplitz com valores decrescentes. 18 ................................................... viii 
 Figura 2.34: Imagem da Lena sem degradação. 19 ................................................................ viii 
 Figura 2.35: Imagem da Lena após a filtragem (matriz Toeplitz com n = 1,2). 19 ............... viii 
 Figura 2.36: Exemplo de arquivo PGM. 26 ............................................................................ viii 
 Figura 2.37: Visualização do exemplo (Fig. 2.36). 26 ........................................................... viii 
 Figura 2.38: Rede direta. 29 ................................................................................................... viii 
 Figura 2.39: Rede indireta. 29 ................................................................................................ viii 
 Figura 2.40: Rede de bus compartilhado. 29 .......................................................................... viii 
 Figura 2.41: Rede crossbar não bloqueante 30 ....................................................................... viii 
 Figura 2.42: Rede multiestágio. 30 ......................................................................................... viii 
 Figura 3.1: Representação discreta da cada pixel da imagem 33 ........................................... viii 
 Figura 3.2: Diagrama do processo de distorção e recuperação da imagem. 35 ...................... viii 
 Figura 3.3: Diagrama do processo de distorção da imagem. 35 ............................................. viii 
 Figura 3.4: Diagrama do processo de restauração. 35 ............................................................ viii 
v
 Figura 3.5: Imagem com distorção Motion Blur de 21 pixels e 45° e 6% de ruído. 36 ........ viii 
 Figura 3.6: Imagem da Lena após a filtra gem (filtro de Mediana 3x3). 36 ............................ viii 
 Figura 3.7: Diagrama de atividades do algoritmo seqüencial. 37 ............................................. ix 
 Figura 3.8: Tempo do processo vs número de iterações. 38 ..................................................... ix 
 Figura 3.8:Imagem original sem degrada ção. 39 ...................................................................... ix 
 Figura 3.9: Imagem degradada com efeito Toeplitz 1.3 e 7 % de ruído. 39 ............................. ix 
 Figura 3.10: Imagem recuperada após 40 iterações. 39 ............................................................ ix 
 Figura 3.11: Imagem recuperada após 320 iterações. 39 .......................................................... ix 
 Figura 3.12: Tempo do processo vs número de iterações. 40 ................................................... ix 
 Figura 3.13: Erro do processo vs número de iterações. 40 ....................................................... ix 
 Figura 3.14: Lena após distorção Motion Blur de 21 pixels e 45° e ruído aditivo 4%. 41 ....... ix 
 Figura 3.15: Imagem degradada após a pré- filtragem (Filtro Mediana Seletivo). 41 ............. ix 
 Figura 3.16: Imagem restaurada (Método de Polyak) após 4 iterações. 41 .............................. ix 
 Figura 3.17: Imagem restaurada (Método de Polyak) após 20 iterações. 41 ............................ ix 
 Figura 3.18: Lena após distorção Motion Blur de 15 pixels e 45° e ruído aditivo 4%. 42 ....... ix 
 Figura 3.19: Imagem degradada após a pré- filtragem (Filtro Mediana Seletivo). 42 ............. ix 
 Figura 3.20: Imagem restaurada (Método de Polyak) após 4 iterações. 42 .............................. ix 
 Figura 3.21: Imagem restaurada (Método de Polyak) após 30 iterações. 42 ............................ ix 
 Figura 4.1: Diagrama de atividades do algoritmo paralelo. 45 ................................................. ix 
 Figura 4.2 Tempos de execução do programa compilado com gcc (GNU) e icc (Intel) para 
320 iterações com uma imagem de 744x1024 pixels. 46 .......................................................... ix 
 Figura 4.3: Speed-up paralelo. 48 ............................................................................................. ix 
 Figura 4.4: Eficiência paralela. 48 ............................................................................................ ix 
 Figura 4.5: Imagem original degradada com efeito Toeplitz 1.3 e 3% de ruído. 49 ................ ix 
 Figura 4.6: Imagem recuperada com método direto (BLAS mkl). 49 ...................................... ix 
 Figura 4.7: Imagem recuperada com Polyak após 350 iterações em 8 processadores . 50 ...... ix 
 Figura 4.8: Imagem original. 50 ............................................................................................... ix 
 Figura 4.9: Imagem recuperada com Polyak após 350 iterações em 1 processador. 50 ........... ix 
 Figura B.1: Diagrama de atividades do algoritmo seqüencial. 59 ............................................ ix 
 Figura B.2: Fluxo de atividades da função mediana(). 61........................................................ ix 
 Figura B.3: Fluxo de atividades da função filtroMediana3x3(). 62 .......................................... ix 
 Figura B.4: Fluxo de atividades do algoritmo filtroMedianaSeletivo3x3(). 63 ........................ ix 
 Figura B.5: Representação gráfica do cálculo da mediana “seletiva” (caso 1). 64 .................. ix 
 Figura B.6: Representação gráfica do cálculo da mediana “seletiva” (caso 2). 64 .................. ix 
 Figura B.7: Fluxo de atividades da função polyak(). 65 ........................................................... ix 
 Figura B.8: Fluxo de atividades do algoritmo paralelo. 67 ...................................................... ix 
 Figura B.9: Fluxo de atividades da função distribuirLinhas(). 69 ............................................ ix 
 Figura B.10: Distribuição de linhas da matriz original em cada nó. 70 ................................... ix 
 Figura B.11: Tamanho da submatriz do processo local. 70 ...................................................... ix 
 Figura B.12: Cálculo do número de cada última linha das submatrizes. 71 ............................. ix 
 Figura B.13: Calculando endereço inicial e final da submatriz. 71 .......................................... ix 
 Figura B.14: Preenchendo submatriz(0). 72 ............................................................................. ix 
 Figura B.15: Preenchendo submatriz(1). 72 ............................................................................. ix 
 Figura B.16: Montagem da matriz final. 73 .............................................................................. ix 
 Figura B.17: Fluxo de atividades do algoritmo de montagem da matriz. 73 ............................ ix 
 Figura B.18: Representação gráfica da reconstrução da matriz de saída. 74 ............................ ix 
 Figura E.1: Grupo principal. 83 ................................................................................................ ix 
 Figura E.2: Comunicação ponto-a-ponto 84 ............................................................................ ix 
 Figura E.3: Comando Broadcast. 87 ......................................................................................... ix 
 Figura E.4: Exemplo de Reduce. 87 ......................................................................................... ix 
vi
 Figura E.5: Exemplo de Allreduce. 88 ..................................................................................... ix 
 Figura E.6: Exemplo de operação de soma com Scan. 89 ........................................................ ix 
 Figura E.7: Exemplo de Gather. 89 ........................................................................................... x 
 Figura E.8: Exemplo de Scatter. 90 ........................................................................................... x 
 Figura E.9: Exemplo de Allgather. 90 ....................................................................................... x 
1 INTRODUÇÃO ....................................................................................................................... 1 
2 FUNDAMENTOS TEÓRICOS ............................................................................................... 3 
3 ANÁLISE DA SOLUÇÃO .................................................................................................... 33 
4 PROPOSTA DE SOLUÇÃO PARALELA ........................................................................... 43 
 CONCLUSÕES ....................................................................................................................... 51 
 REFERÊNCIAS ...................................................................................................................... 53 
 APÊNDICE A – Tabelas de Dados ........................................................................................ 55 
 APÊNDICE B – Diagramas de Atividades .............................................................................. 59 
 APÊNDICE C – Código Seqüencial ........................................................................................ 74 
 APÊNDICE D – Código Paralelo ............................................................................................ 77 
 APÊNDICE E – MPI ............................................................................................................... 81 
vii
ÍNDICE DE FIGURAS
Figura 2.1: Convenção dos eixos para representação de imagens digitais. ............................... 4 
Figura 2.2. Matriz imagem e máscara. ........................................................................................ 6 
Figura 2.3. Aplicação de filtros. .................................................................................................. 6 
Figura 2.4: Máscara 3x3 ............................................................................................................. 7Figura 2.5: Máscara 5x5 (k = 25). ............................................................................................... 8 
Figura 2.6: Imagem da Lena sem degradação. ........................................................................... 8 
Figura 2.7: Imagem da Lena após a filtragem (filtro de média 5x5). ......................................... 8 
Figura 2.8: Máscara 5x5 (k = 65). ............................................................................................... 8 
Figura 2.9: Imagem da Lena sem degradação. ........................................................................... 9 
Figura 2.10: Imagem da Lena após a filtragem (filtro Gaussiano 5x5). ..................................... 9 
Figura 2.11: Representação gráfica do cálculo da mediana de um vetor. ................................... 9 
Figura 2.12: Imagem da Lena com ruído (Salt & Pepper 4%). ................................................ 10 
Figura 2.13: Imagem da Lena após a filtragem (filtro de Mediana 3x3). ................................. 10 
Figura 2.14: Formação de uma imagem pela passagem de radiação num meio não ideal. ...... 10 
Figura 2.15: Representação esquemática do sistema de formação de uma imagem. ............... 12 
Figura 2.16: Representação gráfica do rearranjo lexicográfico de uma matriz M. ................... 12 
 Figura 2.17: Lena original. .......................................................................................... 14 
Figura 2.18: Lena após filtro Motion Blur de 10 pixels e 0°. ................................................... 14 
 Figura 2.19: Lena original. .......................................................................................... 14 
Figura 2.20: Lena após filtro Motion Blur de 15 pixels e 0°. ................................................... 14 
 Figura 2.21: Lena original. .......................................................................................... 15 
Figura 2.22: Lena após filtro Motion Blur de 21 pixels e 0°. ................................................... 15 
Figura 2.23: Representação gráfica do comprimento da distorção. .......................................... 15 
Figura 2.24: Distorção aplicada com um ângulo de 45°. .......................................................... 15 
Figura 2.25: Distribuição dos pesos da distorção aplicada a 45°. ............................................. 15 
 Figura 2.26: Lena original. ........................................................................................ 16 
Figura 2.27: Lena após filtro Motion Blur de 10 pixels e 45°. ................................................. 16 
 Figura 2.28: Lena original. ....................................................................................... 17 
Figura 2.29: Lena após filtro Motion Blur de 15 pixels e 45°. ................................................. 17 
 Figura 2.30: Lena original. ........................................................................................ 18 
Figura 2.31: Lena após filtro gaussiano 4 pixels de raio e σ = 2. ............................................. 18 
Figura 2.32: Matriz Toeplitz com valores crescentes. .............................................................. 18 
Figura 2.33: Matriz Toeplitz com valores decrescentes. .......................................................... 18 
Figura 2.34: Imagem da Lena sem degradação. ....................................................................... 19 
Figura 2.35: Imagem da Lena após a filtragem (matriz Toeplitz com n = 1,2). ...................... 19 
Figura 2.36: Exemplo de arquivo PGM. ................................................................................... 26 
Figura 2.37: Visualização do exemplo (Fig. 2.36). ................................................................... 26 
Figura 2.38: Rede direta. ........................................................................................................... 29 
Figura 2.39: Rede indireta. ........................................................................................................ 29 
Figura 2.40: Rede de bus compartilhado. ................................................................................. 29 
Figura 2.41: Rede crossbar não bloqueante .............................................................................. 30 
Figura 2.42: Rede multiestágio. ................................................................................................ 30 
Figura 3.1: Representação discreta da cada pixel da imagem .................................................. 33 
Figura 3.2: Diagrama do processo de distorção e recuperação da imagem. ............................. 35 
Figura 3.3: Diagrama do processo de distorção da imagem. .................................................... 35 
Figura 3.4: Diagrama do processo de restauração. ................................................................... 35 
Figura 3.5: Imagem com distorção Motion Blur de 21 pixels e 45° e 6% de ruído. ............... 36 
Figura 3.6: Imagem da Lena após a filtra gem (filtro de Mediana 3x3).................................... 36 
viii
Figura 3.7: Diagrama de atividades do algoritmo seqüencial. .................................................. 37 
Figura 3.8: Tempo do processo vs número de iterações. .......................................................... 38 
Figura 3.8:Imagem original sem degrada ção. ........................................................................... 39 
Figura 3.9: Imagem degradada com efeito Toeplitz 1.3 e 7 % de ruído. .................................. 39 
Figura 3.10: Imagem recuperada após 40 iterações. ................................................................. 39 
Figura 3.11: Imagem recuperada após 320 iterações. ............................................................... 39 
Figura 3.12: Tempo do processo vs número de iterações. ........................................................ 40 
Figura 3.13: Erro do processo vs número de iterações. ............................................................ 40 
Figura 3.14: Lena após distorção Motion Blur de 21 pixels e 45° e ruído aditivo 4%. ............ 41 
Figura 3.15: Imagem degradada após a pré- filtragem (Filtro Mediana Seletivo). ................... 41 
Figura 3.16: Imagem restaurada (Método de Polyak) após 4 iterações. ................................... 41 
Figura 3.17: Imagem restaurada (Método de Polyak) após 20 iterações. ................................. 41 
Figura 3.18: Lena após distorção Motion Blur de 15 pixels e 45° e ruído aditivo 4%. ............ 42 
Figura 3.19: Imagem degradada após a pré- filtragem (Filtro Mediana Seletivo). ................... 42 
Figura 3.20: Imagem restaurada (Método de Polyak) após 4 iterações. ................................... 42 
Figura 3.21: Imagem restaurada (Método de Polyak) após 30 iterações. ................................. 42 
Figura 4.1: Diagrama de atividades do algoritmo paralelo. ...................................................... 45 
Figura 4.2 Tempos de execução do programa compilado com gcc (GNU) e icc (Intel) para 
320 iterações com uma imagem de 744x1024 pixels. .............................................................. 46 
Figura 4.3: Speed-up paralelo. .................................................................................................. 48 
Figura 4.4: Eficiência paralela. ................................................................................................. 48 
Figura 4.5: Imagem original degradada com efeito Toeplitz 1.3 e 3% de ruído. ..................... 49 
Figura 4.6: Imagem recuperada com método direto (BLAS mkl). ........................................... 49 
Figura 4.7: Imagem recuperada com Polyak após 350 iterações em 8 processadores . ........... 50 
Figura 4.8: Imagem original. .................................................................................................... 50 
Figura 4.9: Imagem recuperada com Polyak após 350 iterações em 1 processador. ................ 50 
Figura B.1: Diagrama de atividades do algoritmo seqüencial. ................................................. 59 
Figura B.2: Fluxo de atividades da função mediana(). ............................................................. 61 
Figura B.3: Fluxo de atividades da função filtroMediana3x3(). ............................................... 62 
Figura B.4: Fluxo de atividades do algoritmo filtroMedianaSeletivo3x3(). ............................. 63 
Figura B.5: Representação gráfica do cálculo da mediana “seletiva” (caso 1). ....................... 64 
Figura B.6: Representação gráfica do cálculo da mediana “seletiva” (caso 2). ....................... 64 
Figura B.7: Fluxo de atividades da função polyak(). ................................................................ 65 
Figura B.8: Fluxo de atividades do algoritmo paralelo. ............................................................ 67 
Figura B.9: Fluxo de atividades da função distribuirLinhas(). ................................................. 69 
Figura B.10: Distribuição de linhas da matriz original em cada nó. ......................................... 70 
Figura B.11: Tamanho da submatriz do processo local. ........................................................... 70 
Figura B.12: Cálculo do número de cada última linha das submatrizes. .................................. 71 
Figura B.13: Calculando endereço inicial e final da submatriz. ............................................... 71 
Figura B.14: Preenchendo submatriz(0). .................................................................................. 72 
Figura B.15: Preenchendo submatriz(1). .................................................................................. 72 
Figura B.16: Montagem da matriz final. ................................................................................... 73 
Figura B.17: Fluxo de atividades do algoritmo de montagem da matriz. ................................. 73 
Figura B.18: Representação gráfica da reconstrução da matriz de saída. ................................. 74 
Figura E.1: Grupo principal. ..................................................................................................... 83 
Figura E.2: Comunicação ponto-a-ponto ................................................................................. 84 
Figura E.3: Comando Broadcast. .............................................................................................. 87 
Figura E.4: Exemplo de Reduce............................................................................................... 87 
Figura E.5: Exemplo de Allreduce. ........................................................................................... 88 
Figura E.6: Exemplo de operação de soma com Scan. ............................................................. 89 
ix
Figura E.7: Exemplo de Gather. ............................................................................................... 89 
Figura E.8: Exemplo de Scatter. ............................................................................................... 90 
Figura E.9: Exemplo de Allgather. ........................................................................................... 90 
x
1 INTRODUÇÃO
1.1 MOTIVAÇÃO
A melhoria na qualidade de imagens ou processamento das mesmas para outros fins requer 
processos computacionalmente pesados e complexos. O desempenho destes processos pode 
ser melhorado utilizando-se implementações paralelas. Estas implementações paralelas po-
dem dar uma maior agilidade neste âmbito.
Este trabalho consiste no desenvolvimento de processos para restauração e tratamento de 
imagens que sofreram efeitos de degradação, utilizando para tanto, processos de redes neurais 
implementados em computadores paralelos assim como a otimização de alguns algoritmos 
usados no processamento de sinais.
Uma melhoria destes algoritmos, assim como a paralelização dos mesmos pode reduzir 
significativamente o tempo de execução dos processos, assim como melhores resultados des-
de o ponto de vista de medida de degradação.
1.2 DESCRIÇÃO DO PROJETO
O objetivo deste projeto é poder restaurar imagens digitais monocromáticas que sofreram 
algum tipo de degradação ou distorção. Para realizar esta restauração usamos métodos iterati-
vos para resolver os sistemas lineares que representam o fenômeno de degradação e recupera-
ção da imagem. Estes métodos iterativos são implementados com processos que usam redes 
neurais e são executados em um ambiente de computadores paralelos.
Uma imagem monocromática pode ser representada digitalmente por uma matriz bidimen-
sional, cada valor da matriz (pixel) representa o valor de brilho da imagem nesse ponto. À 
medida que a dimensão da matriz vai aumentando, temos uma imagem com maior resolução. 
Este aumento na resolução da imagem vai ser refletido em um aumento na memória necessá-
ria para poder armazenar o arquivo da imagem assim como na memória necessária no proces-
sador para poder tratar a mesma.
Para trabalhar na restauração destas imagens usamos um modelo linear (Jacobi e Polyak) 
[3], [4] que faz necessário o uso de matrizes de dimensões exponencialmente maiores que a 
dimensão da matriz que representa a imagem original. Este fato dificulta a execução destes 
processos em computadores comuns, já que para trabalhar com estas matrizes se requer de 
muita memória e de alto poder de processamento.
1
Os modelos lineares antes mencionados (Jacobi e Polyak) têm uma estrutura que facilita a 
divisão do processo em vários subprocessos menores que podem ser resolvidos ao mesmo 
tempo, é por isso que a computação paralela aparece como uma opção viável para trabalhar 
com estas grandes quantidades de dados. Alem da paralelização dos processos de restauração 
foram otimizados alguns dos algoritmos já conhecidos no processamento de imagens e que 
são utilizados neste trabalho. 
As imagens tratadas foram codificadas no formato PGM (Portable Gray Map) [11], este 
formato facilita a manipulação destas imagens já que as representa como uma matriz de valo-
res arbitrários de escala de cinzas colocados num arquivo tipo texto.
2
2 FUNDAMENTOS TEÓRICOS
2.1 PROCESSAMENTO DE IMAGENS
O processamento de imagens tem como objetivo melhorar a aparência das imagens e fazer 
mais evidente nelas determinados aspectos que se deseja ressaltar. O processamento pode ser 
feito por meios óticos ou por meios digitais usando métodos computacionais. Neste trabalho 
utilizamos o meio digital.
Da mesma maneira do método ótico, os fundamentos do processamento digital de imagens 
têm sido estabelecidos faz muitos anos, mas não eram realizados devido à falta de com-
putadores eficientes. Com o surgimento de computadores de alto desempenho e memória, co-
meçou-se a desenvolver este campo.
Um dos primeiros lugares onde se realizaram projetos de processamento de imagens foi no 
Laboratório de Propulsão a Jato (Jet Propulsion Laboratory) [18], no ano de 1959 com a fi-
nalidade de melhorar as imagens enviadas pelos satélites. Os resultados obtidos por este pro-
jeto foram tão impressionantes e num período de tempo tão curto que as aplicações foram le-
vadas rapidamente a outros campos.
2.2 PROCESSAMENTO DIGITAL DE IMAGENS
Nos últimos anos, o processamento digital de imagens tem sido usado amplamente em di-
versos campos da ciência humana tais como: Medicina, Biologia, Física e Engenharia [14].
Por meio do processamento digital, é possível manipular imagens digitais em um compu-
tador com o objetivo de obter informações objetivas e claras da cena capturada pela câmera. 
O processamento digital de imagens tem dois objetivos fundamentais:
• Melhoramento de uma imagem digital com fins de interpretação.
• Tomada de decisão de maneira automática de acordo com o conteúdo da imagem.
Como aplicações típicas, podemos mencionar: detecção de presença de objetos, inspeção 
visual automática, medição de características geométricas e de cor de objetos, classificação de 
objetos, restauração de imagens e melhoramento da qualidade das imagens.
2.2.1 Representação de Imagens Digitais
O termo imagem monocromática, ou simplesmente imagem, refere-se à função bidimensi-
onal de intensidade da luz f(x,y), onde x e y denotam as coordenadas espaciais e o valor f em 
3
qualquer ponto (x,y) é proporcional ao brilho (ou níveis de cinza) da imagem naquele ponto 
[14].
Uma imagem digital é uma imagem f(x,y) discretizada tanto em coordenadas espaciais 
quanto em brilho (intensidade da luz). Uma imagem digital pode ser considerada como uma 
matriz cujos índices de linhas e de colunas identificam um ponto na imagem, e o correspon-
dente valor do elemento da matriz, identifica o nível de cinza naquele ponto. Os elementos 
dessa matriz digital são chamados: elementos da imagem, elementos da figura, pixels ou pels 
(abreviações de picture elements). Quanto mais pixels uma imagem tiver melhor é a sua re-
solução e qualidade [14].
Figura 2.1: Convenção dos eixos para representação de imagens digi-
tais. 
2.3 FILTROS DIGITAIS
Em muitas aplicações no tratamento de imagens digitais é necessária a filtragem destas 
tanto na remoção de ruído quanto na segmentação, enfoque, suavizado, etc. Para estes propó-
sitos são utilizados os filtros digitais 2-D lineares e não lineares.
Os processos de melhoria da imagem podem agrupar-se tendo em conta o mecanismo utili-
zado na modificação da imagem digital. Assim existem algoritmos que modificam o histo-
grama ou função de distribuição de intensidade, algoritmos que modificam o conteúdo de 
cada pixel da imagem de acordo com os valores dos pixels vizinhos aplicando uma determi-
nada função pré-determinada e outros que filtram determinadas freqüências.
Uma parte muito importante no processo de restauração de imagens baseia-se na aplicação 
de funções, cujo resultado depende unicamente dos níveis de intensidade de cada pixel da 
imagem, mas não da posição dentro da imagem (Position-invariant), que permitemressaltar 
4
determinados elementos da imagem, melhorar o enfoque ou ainda reduzir o ruído no fundo da 
imagem.
Entre os principais objetivos da filtragem digital podemos mencionar a melhoria na quali-
dade de uma imagem (realce-sharpening-enhancement), eliminação de ruídos (noise), corre-
ção de imagens, segmentação, eliminação de distorções e criação de efeitos artísticos.
As funções aplicadas às imagens que por analogia com a teoria de processamento de sinais 
se denominam filtros, baseiam-se no processo de convolução e nas propriedades da convolu-
ção da transformação de Fourier, o que simplifica o cálculo matemático e os tempos de com-
putação. 
Por este motivo, muitos destes filtros herdam o nome segundo sua ação no espaço das fre-
qüências (filtros Passa-Alto, Passa-Baixo ou Direcionais). Embora cada vez mais freqüente, 
nos sistemas de processamento de imagens, se lhes atribui nomes de acordo com o resultado 
visual que produzem na imagem filtrada (filtros de enfoque ou dês-enfoque).
Um filtro de convolução, para uma imagem digital, no espaço real (x, y), pode representar-
se como uma matriz quadrada ou retangular (máscara), de dimensões pré-definidas (M×N). A 
matriz de convolução se desloca sob a imagem de tal forma que o elemento central da matriz 
de convolução coincida com cada um dos pixels da imagem. Em cada posição, se multiplica o 
valor de cada pixel da imagem, que coincide em posição com um elemento da matriz de con-
volução, pelo valor deste. O pixel da imagem, que coincide com o elemento central da matriz 
de convolução é substituído pela suma dos produtos.
2.3.1 Tipos de filtros digitais
Em filtragem digital existem dois tipos de domínio:
• Filtragem no Domínio da Freqüência. Neste domínio utilizamos a Transformada de 
Fourier, este tipo de filtragem é baseado no teorema da convolução.
• Filtragem no Domínio Espacial. Utilizamos máscaras.
2.3.2 Máscaras
O efeito que os filtros ocasionam representa-se digitalmente pela aplicação de máscaras 
nas matrizes que representam uma imagem.
Na figura 2.2 é representada uma matriz de valores onde aplicamos uma máscara de di-
mensão (3×3), o resultado da aplicação dessa máscara é um novo valor P33’ na posição do 
5
elemento P33 (figura 2.3). Este novo valor (P33’) é o resultado de uma função matemática 
dos elementos f contidos na máscara. 
66P65P64P63P62P61P
56P55P54P53P52P51P
46P45P44P43P42P41P
36P35P34P33P32P31P
26P25P24P23P22P21P
16P15P14P13P12P11P
987
654
321
fff
fff
fff
matriz máscara
Figura 2.2. Matriz imagem e máscara.
 
P33’=P22.f1+P23.f2+P24.f3+P32.f4+P33.f5+P34.f6+P42.f7+P43.f8+P44.f9
Figura 2.3. Aplicação de filtros.
2.3.3 Filtragem no domínio da freqüência (Domínio Fourier)
A base para a técnica baseada no domínio da freqüência é o teorema de Convolução. Con-
volução é o produto da transformada de Fourier aplicada pixel a pixel entre duas imagens en-
volvidas.
O efeito na aquisição de uma imagem é representado pela Função de Espalhamento de 
Pontos, PSF (Point Spread Function). 
Pequenas mudanças nos níveis de cinza são representadas como sendo de baixa freqüência 
e mudanças bruscas nos níveis de cinza (bordas) são representados como sendo de alta fre-
qüência.
Seja g(x,y) uma imagem formada pela convolução de uma imagem f(x,y) e um operador in-
variante h(x,y) (função de transferência do filtro), onde:
g(x,y) = h(x,y) * f(x,y)
6
Pelo teorema da convolução, tem-se a seguinte relação no domínio da freqüência.
G(x,y) = H(x,y) · F(x,y) onde:
G, H e F são as transformadas de Fourier de g, h e f.
A convolução no domínio da freqüência é mais fácil que no domínio espacial já que é sim-
plesmente o produto da transformada de Fourier pixel a pixel entre as imagens envolvidas, 
neste caso se o núcleo for menor, completa-se a matriz H com zeros.
Os principais filtros no domínio da freqüência são o Ideal, Batherworth, Cheby, Gaussiano 
e Filtro Wiener.
2.3.4 Filtragem Espacial
Esta técnica é baseada na aplicação de mascaras na imagem, estas máscaras são normal-
mente chamadas de Filtros Espaciais e são divididos em dois tipos principais.
• Filtros lineares. Onde temos os filtros de passa - alta, passa - baixa e passa-banda.
• Filtros não lineares. Podemos mencionar a filtragem morfológica. 
Filtros lineares
Os filtros lineares se baseiam na mudança do nível de cinza de um ponto (pixel) em função 
dos outros pontos da sua vizinhança mediante a aplicação de uma máscara do tipo:
987
654
321
ωωω
ωωω
ωωω
Figura 2.4: Máscara 
3x3
Onde o nível de cinza do pixel central é dado por:
( ) kpppppppppt /998877665544332211 ×+×+×+×+×+×+×+×+×= ωωωωωωωωωω s
endo k uma constante para evitar que o nível de cinza fique fora do limite máximo dos valores 
dos pixels e pi o valor de nível de cinza do pixel i dentro da máscara. Os coeficientes da más-
cara dependem do tipo de filtro linear, no caso do filtro passa-baixos, por exemplo, são todos 
positivos [16].
A seguir mostramos alguns exemplos para filtros lineares.
Exemplo 2.1: Filtro de média
7
Neste caso a máscara é uma matriz de dimensão (5×5) com valores iguais de 1/25.
11111
11111
11111
11111
11111
1
k
Figura 2.5: Máscara 5x5 (k = 
25).
Figura 2.6: Imagem da Lena sem degradação. Figura 2.7: Imagem da Lena após a filtragem 
(filtro de média 5x5).
Na figura 2.7 podemos observar os efeitos do filtro aplicado à imagem original (figura 2.6), 
este filtro cria o efeito de uma imagem embaçada.
Exemplo 2.2: Filtro Gaussiano
Neste caso a máscara é uma matriz com os valores mostrados na figura 2.8.
12321
23432
34543
23432
12321
1
k
Figura 2.8: Máscara 5x5 (k = 65).
Aplicando este filtro também podemos notar que o efeito na imagem (figura 2.10) é de uma 
imagem embaçada, a diferença deste filtro é que a influencia dos pixels vizinhos não é igual 
na mascara inteira, o peso dos vizinhos decai conforme o pixel vai se afastando do centro da 
máscara.
8
Figura 2.9: Imagem da Lena sem degradação. Figura 2.10: Imagem da Lena após a filtragem 
(filtro Gaussiano 5x5).
2.3.5 Filtros de Mediana
Este tipo de filtro é um exemplo de Filtro não Linear, o nível de cinza do pixel no qual se 
aplica a máscara também depende dos níveis de cinza dos pontos vizinhos, mas não é uma 
função linear destes. Neste caso é a mediana dos níveis de cinza dos pontos vizinhos [17].
Algoritmo da mediana:
Dado um conjunto de valores v = [a, b, c, ...] temos que ordenar os valores de maneira 
crescente ou decrescente, depois obtermos a mediana selecionando o valor que fica no meio 
deste novo vetor crescente. No caso de um número par de valores, podemos selecionar qual-
quer um dos valores que ficarem no meio.
Exemplo 2.3: Cálculo de mediana. 
v = [5, 6, 8, 9, 3, 1, 2, 4, 7] (Vetor original)
v’ = [1, 2, 3, 4, 5, 6, 7, 8, 9] (Vetor reordenado de forma crescente)
Mediana(v) = 5
Figura 2.11: Representação gráfica do cálculo da mediana de um vetor.
9
Figura 2.12: Imagem da Lena com ruído 
(Salt & Pepper 4%).
Figura 2.13: Imagem da Lena após a filtragem 
(filtro de Mediana 3x3).
2.4 DISTORÇÃO DE IMAGENS
Quando capturamos uma imagem, na verdade obtemos o resultado da penetração da radia-
ção refletida na imagem original num meio não ideal que geralmente tem propriedades físicas 
que ocasionam uma distorção no percurso da radiação que leva à formação da imagem.
Na figura 2.14 temos uma representação gráfica do processo de captura de uma imagem. 
Quando uma determinada radiação (luz visível) atinge um objeto não opaco, este reflete parte 
da radiação recebida.
Figura 2.14: Formação de uma imagem pela passagem de radiação num 
meio não ideal.
As degradações que são encontradas na imagem gerada são introduzidas pelo sistema de 
formação da imagem e/ou por fatores externos que geram mudanças no ambiente em que é 
feita a aquisição da imagem, como variação de temperatura ou pressão. As formas mais co-
muns de degradação são: A resolução finita dos sensores utilizados na aquisição da imagem, 
embaçamentodevido ao movimento dos sensores ou do alvo no momento da aquisição, refra-
10
ção e embaçamento provocado por problemas de foco [1]. As distorções em imagens podem 
ser classificadas em duas categorias [2]
• Variantes no espaço. A distorção sofrida depende da região da imagem que esta-
mos analisando. Este tipo de distorção é ocasionado por problemas na aquisição ou por 
fatores externos.
• Invariantes no espaço. A distorção é a mesma em todas as regiões da imagem. 
Este tipo de distorção pode ser provocado por problemas de foco ou movimento da câ-
mera. 
No pressente trabalho, consideramos somente as distorções invariantes no espaço e lineares 
por elas terem um modelo matemático mais simples. Muitas das distorções não-lineares po-
dem ser aproximadas por distorções lineares.
2.5 MODELAGEM MATEMÁTICA DA DISTORÇÃO DE IMAGENS
O processo de formação da imagem pode ser representado matematicamente pela equação 
integral de Fredholm [1] que mostramos a seguir.
∫ ∫
∞
∞−
∞
∞−
+= ),(),(),,,(),( yxddfyxhyxg εηξηξηξ (2.1)
Sendo f( , )ξ η e g(x,y) as funções que descrevem o objeto (no plano de coordenadas ( , )ξ η , 
que é referido como plano do objeto) e a imagem gravada (no plano de coordenadas (x,y), que 
é referido como plano da imagem), h(x, ,y, )ξ η é a forma analítica da função degradação e 
(x,y)ε representa o ruído presente na imagem. 
Na figura 2.15 mostramos um esquema representativo do objeto e da imagem em seus res-
pectivos sistemas de coordenadas.
11
Figura 2.15: Representação esquemática do sistema de formação de uma imagem.
O conhecimento do ruído (x,y)ε é limitado pelos métodos estatísticos. No processamento 
de imagens, a função de degradação h(x, ,y, )ξ η geralmente é conhecida a priori e representa a 
resposta do sistema a um impulso unitário nas coordenadas (x,y). Este impulso unitário é re-
presentado, no campo da ótica como um ponto de luz, é por isso que a função h(x, ,y, )ξ η é tam-
bém conhecida como Point Spread Function (PSF). A função PSF assume um papel fun-
damental no processo de restauração de uma imagem assim como na escolha do método de 
restauração. 
O modelo de Fredholm [1] para formação de imagens, mostrado na equação (2.1) pode ser 
reescrito no caso de sistemas discretos como se mostra na equação a seguir.
( ) ( ) ( ) ( )yxyxhfyxg
MN
,,;,,, εηξηξ
βα
+= ∑∑ (2.2)
Se considerarmos h(x, ,y, )ξ η uma função linear então a equação (2.1) pode ser reescrita 
considerando f( , )ξ η , g(x,y) e (x,y)ε como vetores coluna de dimensão (M×N). Para poder dei-
xar estas matrizes (f, g e ε) na forma de vetor temos que usar um rearranjo lexicográfico des-
tas informações. Um rearranjo lexicográfico consiste em reagrupar o conteúdo da matriz num 
vetor único que tem cada linha da matriz empilhada uma após a outra. 
Figura 2.16: Representação gráfica do rearranjo lexicográfico de uma matriz M.
Agora podemos representar a equação (2.1) como uma equação linear representada na 
equação (2.3). 
.ε+= Hfg (2.3)
Na equação linear acima (2.3) g e f representam os arranjos lexicográficos das matrizes de 
imagem degradada e imagem original respectivamente, ε representa a componente de ruído 
12
aditivo e H é uma matriz operador que representa a função h(x, ,y, ).ξ η A multiplicação da ma-
triz H com o vetor imagem f executa a mesma operação que convoluir f( , )ξ η com h(x, ,y, ).ξ η
2.6 TIPOS DE DISTORÇÃO
Existem muitos tipos de distorção, mas nesta seção vamos mencionar somente os que fo-
ram tratados no processo de restauração.
2.6.1 Motion Blur (Distorção por movimento)
No caso da distorção Motion Blur (Distorção por Movimento) a função PSF é representa 
por uma matriz que descreve as contribuições de brilho de cada um dos vizinhos do pixel cen-
tral que entram no processo de distorção. Para uma distorção deste tipo (Motion Blur) temos 
dois parâmetros a considerar, o tamanho da distorção e o ângulo da distorço.
Tamanho da distorção: É o comprimento da distorção em pixels, este valor representa o nú-
mero de pixels que entram na movimentação da câmera.
Ângulo da distorção: Este valor representa o ângulo em sentido anti-horário no qual se mo-
vimenta a câmera.
Quando o ângulo é 0 (zero) é fácil notar que a distorção Motion Blur é basicamente uma 
média dos valores dos pixels vizinhos que entram na distorção. 
Exemplo 2.4: Neste exemplo mostramos uma distorção do tipo Motion Blur com 10 (dez) pi-
xels de comprimento e 0° (zero graus).
PSF = [0.05 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.05]
Na figura 2.18 podemos ver que o efeito de aplicar esta distorção é a aparência de ter cap-
turado a imagem em movimento.
13
 Figura 2.17: Lena original. Figura 2.18: Lena após filtro Motion Blur de 
10 pixels e 0°.
Exemplo 2.5: Neste caso mostramos uma distorção do tipo Motion Blur com 15 (quinze) pi-
xels de comprimento e 0° (zero graus). Podemos notar que a distribuição dos valores dos pe-
sos dos pixels vizinhos da uma média aritmética dos mesmos.
PSF = [a a a a a a a a a a a a a a a] , a = 0.0667
Na figura 2.20 podemos ver o efeito deste filtro com 15 pixels, é evidente que a distorção é 
mais forte que no exemplo com 10 pixels.
 Figura 2.19: Lena original. Figura 2.20: Lena após filtro Motion Blur de 
15 pixels e 0°.
Exemplo 2.6: Neste caso mostramos uma distorção do tipo Motion Blur com 21 (vinte e um) 
pixels de comprimento e 0° (zero graus). 
PSF = [a a a a a a a a a a a a a a a a a a a a a], a = 0.0476
Neste ultimo exemplo podemos ver o aumento no numero de pixels que participam da dis-
torção aumenta também o grau de distorção da imagem (ver figura 2.22). 
14
 Figura 2.21: Lena original. Figura 2.22: Lena após filtro Motion Blur de 
21 pixels e 0°.
Quando mudamos o ângulo da distorção a representação deste efeito inclui pixels que de 
diferentes linhas e colunas já que neste caso, devido ao formato da matriz da imagem, se faz 
impossível colocar o vetor de distorção ocupando somente o número de pixels do vetor origi-
nal.
Figura 2.23: Representação 
gráfica do comprimento da dis-
torção.
Figura 2.24: Distorção aplicada 
com um ângulo de 45°.
Figura 2.25: Distribuição dos 
pesos da distorção aplicada a 
45°.
Exemplo 2.7: Neste caso mostramos uma distorção do tipo Motion Blur com 10 (dez) pixels 
de comprimento e 45° (quarenta e cinco graus).
15




























=
00000000
000000
000000
000000
000000
000000
000000
000000
00000000
c
bac
bab
bab
bab
bab
bab
cab
c
PSF
a = 0.089584
b = 0.026239
c = 0.014511
 Figura 2.26: Lena original. Figura 2.27: Lena após filtro Motion Blur de 10 
pixels e 45°.
Exemplo 2.8: Neste caso mostramos uma distorção do tipo Motion Blur com 15 (quinze) pi-
xels de comprimento e 45° (quarenta e cinco graus).


































=
000000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
000000000
bc
bab
bab
bab
bab
bab
bab
bab
bab
bab
cb
PSF
a = 0.059824
b = 0.017522
c = 0.055572
16
 Figura 2.28: Lena original. Figura 2.29: Lena após filtro Motion Blur de 15 
pixels e 45°.
No exemplo 2.7 e 2.8 podemos notar que a distorção é numa determinada direção do plano 
da imagem, isso vai depender de um dos parâmetros da distorção (ângulo).
2.6.2 Gaussian Blur (Distorção Gaussiana)
Este tipo de distorção é muito usado, ocasiona redução de níveis de detalhe nas imagens e 
pode servir para diminuir o ruído das mesmas. O efeito visual desta distorção é semelhante ao 
suavizado numa imagem vista através de uma tela translúcida, distintamente do efeito bokeh 
[10] produzido por uma lente do fora de foco.
Matematicamente falando, aplicar uma distorção gaussiana numa imagem equivale a con-voluir esta imagem com uma distribuição gaussiana ou normal. Esta convolução tem o efeito 
de filtro passa-baixas. 
Para gerar este efeito aplicamos a distribuição gaussiana em duas dimensões representada 
na seguinte equação.
eyxG 22
1),(
π σ
= )2/()( 222 σyx +− (2.4)
Onde σ é o desvio padrão da distribuição gaussiana e x e y são as coordenadas do pixel na 
matriz imagem. Esta formula aplicada na matriz imagem produz uma superfície cujos contor-
nos são círculos concêntricos com uma distribuição gaussiana do centro para fora.
A seguir mostramos um exemplo onde aplicou-se uma distorção gaussiana com um raio de 
4 pixels e um σ igual a 2.
17






















=
gjidijg
jfhchfj
ihebehi
dcbabcd
ihebehi
jfhchfj
gjidijg
PSF
a= 0.0467
b= 0.0412
c= 0.0283
d= 0.0152
e= 0.0364
f= 0.0172
g= 0.0049
h= 0.0250
i= 0.0134
j= 0.0092
 Figura 2.30: Lena original. Figura 2.31: Lena após filtro gaussiano 4 pixels 
de raio e = 2.σ
2.6.3 Distorção Toeplitz 
A matriz Toeplitz é uma matriz onde todo elemento que se situa na mesma diagonal possui 
o mesmo valor. Nas figuras 2.32 e 2.33 temos alguns exemplos de matriz de Toeplitz.
















12345
21234
32123
43212
54321


























11/n1/n1/n³1/n1/n1/n
n/1
1/n²11/n1/n1/n³1/n1/n
1/n³n/111/n1/n1/n³1/n
1/n1/n²n/111/n1/n1/n³
1/n1/n³1/n²n/111/n1/n
1/n1/n³1/n²n/111/n
1/n1/n1/n1/n³1/n²n/11
245
245
24
42
52
4
54








n
n
Figura 2.32: Matriz Toeplitz com 
valores crescentes.
Figura 2.33: Matriz Toeplitz com valores decres-
centes.
Se a nossa matriz H da equação (2.3) for representada por uma matriz Toepliz podemos ter 
uma distorção similar a distorção por movimento (Motion Blur) com a diferença que a medida 
18
que os pixels vizinhos de uma mesma linha vão se afastando o peso que eles têm na distorção 
do elemento central diminui. Neste tipo de distorção usou-se o modelo da figura 2.33, neste 
modelo existe um parâmetro que é dado para poder aplicar a distorção, é o valor de n. A se-
guir mostramos alguns exemplos deste tipo de distorção.
Na figura 2.35 podemos ver como o efeito desta distorção se assemelha à distorção motion 
blur.
Figura 2.34: Imagem da Lena sem de-
gradação.
Figura 2.35: Imagem da Lena após a fil-
tragem (matriz Toeplitz com n = 1,2). 
2.7 MÉTODOS DIRETOS PARA RESOLUÇÃO DE SISTEMAS LINEARES
Estes métodos são os que após um número finito de etapas nos dão a solução exata do pro-
blema. Esta solução é exata se assumimos a não existência de erros de erredondamento [21].
Nesta cessão apresentaremos os principais métodos numéricos diretos para a resolução de 
sistemas lineares do tipo Ax=b semelhante ao sistema proposto na equação (2.3). Neste tipo 
de sistemas assumimos que MNA R∈ onde NM ≤ . Os métodos diretos nos dão uma respos-
ta exata do sistema e com esses métodos é possível determinar, a priori, o tempo máximo gas-
to para resolver um sistema, uma vez que sua complexidade é conhecida. R
2.7.1 Método de eliminação de Gauss
O método de Gauss consiste em aplicar transformações elementares sobre as equações do 
sistema Ax = b até que, depois de (M – 1) passos se obtenha um sistema triangular superior do 
tipo Ux = c, após a obtenção deste novo sistema a resposta é obtida por substituições retroati-
vas (back substitution).
bAx = MNA R∈
LUA =
19
Após (M-1) passos: cUx =
A matriz L é uma matriz triangular inferior com a diagonal principal igual a um e a matriz 
U é uma matriz triangular superior. A matriz A também pode precisar de permutações para 
chegar ao modelo LU.
PA=LU
2.7.2 Métodos de Fatorização
No método de eliminação de Gauss vimos que quando não há permutações, podemos obter 
a fatorização da matriz A da forma A=LU, onde U seria a matriz triangular superior obtida ao 
final da fatorização e L a matriz triangular inferior com diagonal unitária, cujos elementos re-
presentariam os multiplicadores mij.
Método de Doolittle
Neste método pretendemos obter as matrizes L e U tal que A=LU
























=
− nn
n
nnn u
uu
ll
l
A
00
0
1
01
1
001 111
11
21








 L U
Depois, efetuando o produto, podemos obter as formulas correspondentes ao método de Doo-
little:
Passo 1: jj au 11 = (j=1,…,n)
 1111 / ual ii = (i=2,…,n)
Passo k: rj
k
r
krkjkj ulau ∑
−
=
−=
1
1
 (j=k,…,n)
 kkrk
k
r
irikik uulal /)(
1
1
∑
−
=
−= (i=k+1,…,n)
Para fatorizar a matriz A usando este método é usado o mesmo número de operações que no 
método de eliminação de Gauss. Mesmo assim há uma grande vantagem neste método que é o 
melhor uso de memória para armazenar os elementos da matriz, já que não são sucessivamen-
te alterados como no método de Gauss.
20
Método de Cholesky
Este método só pode ser aplicado quando a matriz A é simétrica (A=AT) e positiva definida.
Na prática para verificar se a matriz é positiva definida gastaríamos mais tempo do que resol-
vendo este sistema. Por isto só aplicamos este método quando sabemos a priori se a matriz A é 
positiva definida e simetrica. 
Para estes tipos de matrizes é valida a afirmação: A=LLT, e o método consiste nos seguintes 
passos:
Passo 1: 1111 al = 
 1111 / lal ii = para i=2,…,n
Passo k: ( )∑
−
=
−=
1
1
2
k
m
kmkkkk lal 
 
kk
km
k
m
imik
ik l
lla
l
)(
1
1
∑
−
=
−
= para i=k+1,…,n
2.8 MÉTODOS ITERATIVOS PARA RESOLUÇÃO DE SISTEMAS LINEA-
RES
Estes métodos nos dão uma resposta aproximada do sistema de equações. A precisão destas 
respostas depende do número de iterações que são efetuadas. Quando o número de iterações 
tende ao infinito a resposta do sistema será exata. Este tipo de métodos são mais simples de 
serem implementados computacionalmente que os métodos diretos e são facilmente paraleli-
zaveis, é por este motivo que a implementação deste projeto foi feita usando estes métodos. 
2.8.1 Método de Jacobi
Embora o método de Jacobi não seja viável para muitos problemas este método propor-
ciona um conveniente ponto de partida para a discussão de métodos iterativos [3].
Sendo A uma matriz não singular (N×N) e
bAx = (2.5)
o sistema pode ser resolvido. Assumiremos que os elementos da diagonal principal, aii, de A 
são diferentes de zero. O método de Jacobi pode ser representado como:
21




+−= ∑
≠
+
ij
i
k
jij
ii
k
j bxaa
x 11 , i=1,...,n k=0,1,... (2.6)
onde os superíndices indicam o número da iteração que eles assumem, como se faz em todo 
método iterativo, a seqüência 002
0
1 ,...,, nxxx representa o chute inicial.
Para poder entender melhor este algoritmo vamos considerar que a matriz A pode ser des-
composta da seguinte maneira: 












+












=
0
0
0
0
000
000
000
000
434241
343231
242321
141312
44
33
22
11
aaa
aaa
aaa
aaa
a
a
a
a
A
isto é, A = D + B, sendo D uma matriz diagonal. Podemos substituir agora a nova representa-
ção de A em (2.5) deixando a equação da seguinte forma:
( )Bxb
a
x
BxbDx
bBxDx
bxBD
ii
−=
−=
=+
=+
1'
)(
O método de Jacobi não é sempre convergente, existem dois teoremas de convergência que 
serão mostrados a seguir.
Teorema 2.1. Se A é estritamente diagonal dominante, então as iterações de Jacobi sempre 
convergirão para qualquer valor inicial de x0 . 
Teorema 2.2. Se A = D + B é positiva definida, então as iterações de Jacobi convergirão para 
qualquer valor inicial de x0 se e somente se (D - B) é positivo definido. 
Teste de convergência
Em cada iteração há um teste necessário que se faz para verificar a convergênciado mé-
todo. Se xk é a seqüência de uma iteração, dois testes comuns são:
ε≤−+ kk xx 1 ou kkk xxx ε≤−+1 (2.7)
22
2.8.2 Iterações de Gauss-Seider e SOR
Consideremos outro método iterativo para resolver o sistema bAx = , onde assumiremos 
novamente que os elementos da diagonal principal de A são diferentes que zero. Após calcu-
lar a nova iteração de Jacobi para x1,




+−= ∑
=
+
1
2
1
11
1
1
1 bxa
a
x
n
j
k
jj
k
é razoável usar este valor atualizado em lugar de kx1 no cálculo dos subseqüentes 
1+k
ix . O 
principio de Gauss-Seider [3] é usar nova informação tão rápido como esta esteja disponível e 
a iteração de Gauss-Seider é dada por




+−−= ∑∑
><
++
ij
i
k
jij
ij
k
jij
ii
k
i bxaxaa
x 11 1 , (2.8)
i = 1,...,n, k = 0,1,...
Façamos
ULDA −−= (2.9)
onde D é a diagonal de A e -L e -U são as partes estritamente diagonal superior e inferior de 
A. Então podemos escrever (2.9) como
bUxLxDx kkk ++= ++ 11
ou
dHxx kk += ++ 11 , k = 0,1,..., ULDH 1)( −−= , bLDd 1)( −−= (2.10)
Desde que D-L é a parte triangular inferior de A, sua inversa existe pela assunção de que os 
elementos da diagonal de A são diferentes que zero.
Uma importante modificação na iteração de Gauss-Seider é dada a seguir. Deixemos 1ˆ +kix 
representar o lado direito de (2.8), a iteração Gauss-Seider é definida como:
)ˆ( 11 ki
k
i
k
i
k
i xxxx −+=
++ ω (2.11)
Substituindo a representação de 1ˆ +kix em (2.11) e rearranjando os termos mostrados, 
1+k
ix satisfaz
i
ij
k
jij
k
iii
ij
k
jij
k
iii bxaxaxaxa ωωωω +−−=+ ∑∑
><
++ )1(11 (2.12)
ou, em termos de matrizes de (2.9),
,...1,0 ,)(])1[()( 111 =−++−−= −−+ kbLDxUDLDx kk ωωωωω (2.13)
23
Isto define a iteração de sucessiva de sobre relaxação (SOR). Note que se 1=ω , (2.13) se 
reduziria à iteração de Gauss-Seider. Note também que LD ω− é não singular pela assunção 
dos elementos da diagonal de A. 
A seguir mostraremos um teorema que garante a convergência das iterações de Gauss-Sei-
der.
Teorema 2.3. Se A é estrita ou irredutivelmente diagonal dominante, ou se A é uma matriz M, 
então as iterações de Gauss-Seider convergem para qualquer valor inicial x0.
2.8.3 Método de Polyak
Este método também serve para resolver um sistema linear na forma bAx = , onde b e x 
são vetores n x 1 e A é uma matriz n x n, assumimos que num ponto xk, medimos a variável 
kkk bAxy ξ+−= , onde bAx k − é conhecido , e kξ é o ruído randômico. Assumindo que as 
seguintes afirmações são satisfeitas (os superíndices indicam o número da iteração que eles 
assumem) [4].
1. A matriz A é uma matriz de Hurwitz, i.e., Re( j) > 0 para todos os autovalores de λ A. 
2. O Ruído kξ não é correlativo, com 0)( =kM ξ , 0))(( >= SM Tkk ξξ (S > 0 significa 
que S é positiva definida, e M é a média). 
Podemos considerar o seguinte método iterativo para achar o ponto bAx 1' −= :
,...1,0 
1
ˆˆˆ
 
.
1
1
=
+
−+=
+−=⋅−=
+
+
k
k
xxxx
bAxyyxx
kk
kk
kkkkkkk ξγ
 (2.14)
Neste ponto o processo para achar xk é um processo de aproximação estocástico ordinário, e 
∑
−
=
=
1
0
ˆ
k
i
k
k
k
xx , i.e., os pontos kx̂ são valores médios das iterações xj, j = 0,1,...,k-1. 
Considerando os valores iniciais x0 e o tamanho de passo kγ podemos assumir o seguinte.
3. O ponto x0 é também determinístico e arbitrário, ou randômico com ∞<− 2
0 'xxM
4. Também 
)Re(2min0 ,
2−
=<<≡ jjj
k λλγγγγ , (2.15)
ou
24
∑
∞
=
+ ∞=∞→+=
0
k
1 ),(1
k
kk
k
k
γγγδ
γ
γ
 (2.16)
A condição (2.16) é satisfeita, por exemplo, pela seqüência 10 , <<= − αγγ αkk , mas não por 
1−= kk γγ . Em outras palavras sk ')(γ decresce mais lentamente que k/1 . 
2.9 ARQUIVOS PGM
O formato PGM é uma denominação pouco comum para Grayscale File Format. Este for-
mato foi desenhado para ser extremamente fácil de aprender e aplicar em programas de pro-
cessamento de imagens. Um arquivo PGM é texto integral e pode ser processado por ferra-
mentas de processamento de texto [11].
Uma imagem PGM representa uma imagem em escala de cinzas. Há muitos pseudofor-
matos PGM em uso onde tudo é especificado como neste formato com exceção do valor indi-
vidual de cada pixel. Para a maioria dos propósitos, uma imagem PGM pode ser entendida 
simplesmente como uma matriz de valores inteiros arbitrários, nesse sentido todos os progra-
mas que trabalham com imagens em escala de cinza podem ser facilmente usados para pro-
cessar qualquer outra coisa. O nome PGM é o acrônimo derivado de Portable Gray Map.
Uma variante oficial de PGM é a máscara de transparências. Uma máscara de transparên-
cia é representada por uma imagem de PGM, com exceção que em lugar de intensidades de 
pixel, há representação de valores de opaco (vide abaixo).
Um arquivo PGM consiste numa seqüência de um ou mais imagens PGM. Não há nenhum 
dado, delimitadores ou recheio antes, depois ou no meio da imagem. 
Cada imagem PGM está formada pelas seguintes partes:
1. Um identificador para reconhecer o tipo de arquivo. O identificador de uma imagem 
PGM é P5 (P2 no caso de imagens monocromáticas).
2. Os comentários. Estes comentários têm que começar pelo símbolo sustenido (#) e vão 
até o final de cada linha. Estes comentários serão ignorados.
3. Largura e altura da matriz que representa a imagem (Width × Height). É usada a forma-
tação ASCII com caracteres decimais.
4. Máximo valor de brilho (Maxval). Também em ASCII decimal e menor que 65536.
25
5. Tom de cinza para cada pixel. Os elementos de cada linha são separados por um espaço 
em branco. Cada valor de cinza é um número proporcional à intensidade de cada pixel e 
têm que estar no intervalo de zero a Maxval (zero representa o valor de preto total).
F i-
gura 2.36: Exemplo de arquivo PGM.
 
Figura 2.37: Visualização do exemplo (Fig. 2.36).
2.10 PROCESSAMENTO PARALELO 
2.10.1 Motivação e aplicações
O principal motivo da aparição da computação paralela foi a demanda por poder computa-
cional, tanto nas aplicações comercias quanto nas aplicações científicas.
IDENTIFICADOR
COMENTARIOS}
LARGURA E 
ALTURA
MAXIMO VALOR DE 
BRILHO
TOM DE CINZA PARA 
CADA PIXEL
26
Pelo lado das aplicações comerciais podemos mencionar os bancos, seguradoras e sistemas 
industriais cuja demanda por acesso intensivo a dados, processamento de transações e alta dis-
ponibilidade foram aumentando criticamente.
Assim como as aplicações comerciais, as aplicações científicas foram exigindo um maior 
uso de sistemas eficientes e de alto desempenho para poder simular ou modelar processos 
cada vez mais complexos e pesados desde o ponto de vista computacional.
Computação paralela tem sido tradicionalmente aplicada com muito sucesso no desenho de 
superfícies aerodinâmicas, motores de combustão interna, circuitos de alta velocidade e dese-
nho de estruturas, entre outras. Mais recentemente, desenho de sistemas microeletromecâni-
cos e nanoeletromecânicos (MEMS e NEMS) tem atraído significativamente a atenção. En-
quanto muitas aplicações em engenharia e desenho propõem problemas de múltipla escala 
temporal e espacial e junto com fenômenos físicos. Podem-se tratar estes problemas como 
uma mistura de fenômenos quânticos, dinâmica molecular, modelos contínuos e estocásticos 
de processos físicos como condução, convecção, radiação, e estruturas mecânicas, tudo em 
um único sistema. Isto representa um formidável desafio para a modelagem geométrica, mo-
delagem matemática e desenvolvimento de algoritmos, tudo no contexto de processamento 
paralelo [6].
Entre as mais relevantes aplicações podemos mencionar aplicações científicas, aplicações co-
merciais