Exercício 6

Autor: Rodrigo Mologni Gonçalves dos Santos
Data: 21/04/2009

Enunciado

Vide Exercício 6.

Introdução

A convolução linear é o resultado da convolução de funções não-periódicas. A convolução circular é o resultado da convolução de funções periódicas.

Convolução Discreta

A convolução discreta bidimensional é formulada representando-se f(x, y) e g(x, y) como matrizes discretas de dimensão A x B e C x D, respectivamente. Como no caso unidimensional, essas matrizes devem ser periódicas com algum período M e N nas direções x e y, respectivamente. A sobreposição dos períodos individuais da convolução, também chamado de "erro de revestimento", é evitado pela escolha

As sequências periódicas são formadas ao se estender f(x, y) e g(x, y) como segue:

A convolução bidimensional de fₑ(x, y) e gₑ(x, y) é definida pela relação

para x = 0, 1, 2, ..., M - 1 e y = 0, 1, 2, ..., N - 1. A matriz M x M da equação é um período da convolução discreta bidimensional.

A função ConvolucaoDiscreta2D apresentada a seguir implementa a formulação de convolução bidimensional.

 1 def ConvolucaoDiscreta2D(f, g):
 2     # Converte f e g para a forma matricial
 3     f, g = asarray(f), asarray(g)
 4 
 5     # As dimensões de f e g correspondem a A x B e C x D, respectivamente
 6     A, B = f.shape
 7     C, D = g.shape
 8 
 9     # Cálculo da periodicidade
10     M = A + C - 1
11     N = B + D - 1
12 
13     # Cria duas matrizes de dimensões iguais a M x N
14     fe = zeros([M, N])
15     ge = zeros([M, N])
16 
17     # Extensão das funções f e g com zero, de modo que as dimensões sejam iguais a M x N
18     fe[0:A, 0:B] = f
19     ge[0:C, 0:D] = g
20 
21     # Cria uma matriz que receberá o resultado da convolução de fe com ge
22     he = zeros([M, N])
23 
24     # Cálcula a convolução de fe com ge
25     for x in range(M):
26         for y in range(N):
27             t = 0
28             for m in range(M):
29                 for n in range(N):
30                     t += fe[m, n] * ge[x - m, y - n]
31             he[x, y] = t
32 
33     # Retorna a convolução de fe com ge
34     return he

Para avaliar a eficácia e o desempenho da função criada, o código fonte abaixo exemplifica o uso desta função e da iaconv da biblioteca ia636.

 1 # Imagem de entrada
 2 f             = ones([15, 15])
 3 f[5:10, 5:10] = zeros([5, 5])
 4 mmshow(numpy.kron(f, numpy.ones([30, 30])),
 5     title='Imagem binária de entrada.')
 6 
 7 # Filtro aplicado a imagem: Laplaciano
 8 g = asarray(
 9     [[0, 1,0],
10      [1,-4,1],
11      [0, 1,0]])
12 
13 # Função iaconv da biblioteca ia636
14 ts = time.time()
15 he = iaconv(f, g)
16 te = time.time()
17 mmshow(numpy.kron(he, numpy.ones([30, 30])),
18     title='iaconv: ' + str(round((te - ts) * 100000) / 100) + ' milisegundos.')
19 
20 # Função ConvolucaoDiscreta2D
21 ts = time.time()
22 he = ConvolucaoDiscreta2D(f, g)
23 te = time.time()
24 mmshow(numpy.kron(he, numpy.ones([30, 30])),
25     title='ConvolucaoDiscreta2D: ' + str(round((te - ts) * 100000) / 100) + ' milisegundos.')

Imagem binária de entrada.

iaconv: 0.35 milisegundos.

ConvolucaoDiscreta2D: 145.71 milisegundos.

Pode-se verificar que a função ConvolucaoDiscreta2D possui um desempenho computacional baixo em relação a função iaconv, devido:

  • Ao grande número de laços utilizados para o cálculo;
  • Cálculos de funções com valores iguais a zero que poderiam ser descartáveis.

E ambas ampliam a dimensão da imagem de entrada, gerando bordas ao redor da imagem de saída.

Visando melhorar o desempenho da função ConvolucaoDiscreta2D, uma segunda versão foi criada.

 1 def ConvolucaoDiscreta2D_V2(f, g):
 2     # Converte f e g para a forma matricial
 3     f, g = asarray(f), asarray(g)
 4 
 5     # As dimensões de f e g correspondem a A x B e C x D, respectivamente
 6     A, B = f.shape
 7     C, D = g.shape
 8 
 9     # Cálculo da periodicidade
10     M = A + C - 1
11     N = B + D - 1
12 
13     # Cálcula a borda acrescentada a matriz f
14     px = (C - 1) / 2
15     py = (D - 1) / 2
16 
17     # Cria uma matriz identica a f, porém com bordas de valores iguais a 0
18     fe = zeros([M, N])
19     fe[px : A + px, py : B + py] = f
20 
21     # Cria uma matriz que receberá o resultado da convolução de fe com g
22     he = zeros([A, B])
23 
24     # Cálcula a convolução de fe com ge
25     for x in range(A):
26         for y in range(B):
27             he[x, y] = sum(fe[x : x + C, y : y + D] * g)
28 
29     # Retorna a convolução de fe com g
30     return he

Dado o mesmo filtro Laplaciano aplicado anteriormente, as imagens a seguir apresentam o desempenho da versão 2 da função ConvolucaoDiscreta2D e iaconv.

Imagem binária de entrada.

iaconv: 0.31 milisegundos.

ConvolucaoDiscreta2D_V2: 3.07 milisegundos.

A segunda versão da função ConvolucaoDiscreta2D apresentou uma melhoria significativa no tempo gasto com o processamento, porém ainda sim demonstrou-se inferior ao desempenho da função iaconv. Vale ressaltar que a nova versão implementa remoção de bordas, ou seja, a imagem de saída é da mesma dimensão que a imagem de entrada.

Referências

GONZALEZ, Rafael C.; WOODS, Richard E. Processamento de Imagens Digitais. Edgard Blücher, 2000. ISBN 85-212-0264-4.

Ferramentas de Análise: Aplicações da FFT. Disponível em http://ensino.univates.br/~chaet/Materiais/Cap%edtulo_12_Bloch.pdf. Acessado em 23/04/2009.