Exercício 7

Autor: Rodrigo Mologni Gonçalves dos Santos
Data: 01/05/2009

Enunciado

Vide Exercício 7.

Índice

1. Descrição matemática do algoritmo usado na função iaconv

2. Obtenção do filtro aplicado sobre uma imagem através da propriedade de impulso

3. Desempenho computacional do algoritmo usado na função iaconv

1. Descrição matemática do algoritmo usado na função iaconv

Como já foi verificado na atividade anterior, o algoritmo utilizado na função iaconv da biblioteca ia636 possui um desempenho computacional superior aos demais que implementam com exatidão a equação da convolução discreta. Visando esclarecer o alto desempenho desta função, neste tópico será descrito matematicamente o algoritmo usado por ela.

A convolução discreta bidimensional é formulada representando-se f(x, y) e h(x, y) como matrizes discretas de dimensão a x b e c x d, respectivamente.

A sobreposição dos períodos individuais da convolução, também chamado de "erro de revestimento", é evitado pela escolha de

Cujos valores compõem as dimensões de uma matriz nula G.

A convolução discreta bidiomensional de F por H é dada pela somatória das matrizes Gij para todo i = 1, 2, 3, ..., c e j = 1, 2, 3, ..., d.

Onde

Por exemplo,

E

O exemplo a seguir visa verificar se a descrição matemática realmente condiz com o algoritmo da função iaconv. Dado uma imagem e um filtro representados, respectivamente, pelas matrizes F e H

Obtém-se que

Portanto, a matriz nula G é dada por

Para obter a convolução, necessita-se calcular os valores de G para i = 1, 2 e j = 1, 2

A convolução discreta bidimensional de F por H é dada pela seguinte soma matricial

A função iaconv2 apresentada a seguir equivale a iaconv. Porém esta foi modificada para imprimir cada iteração do processo de convolução.

 1 def iaconv2(f, h):
 2     f, h = asarray(f), asarray(h)
 3     if len(f.shape) == 1: f = f[newaxis,:]
 4     if len(h.shape) == 1: h = h[newaxis,:]
 5     if product(f.shape) < product(h.shape):
 6         f, h = h, f
 7     g = zeros(array(f.shape) + array(h.shape) - 1)
 8     print 'G =', g
 9     a = zeros(array(f.shape) + array(h.shape) - 1)
10     for i in range(h.shape[0]):
11         for j in range(h.shape[1]):
12             g[i:i+f.shape[0], j:j+f.shape[1]] += h[i,j] * f
13             a[i:i+f.shape[0], j:j+f.shape[1]] = h[i,j] * f
14             print 'G'+str(i)+str(j)+' =', a
15     return g
16 
17 f      = zeros((3,3))
18 f[1,1] = 1
19 print 'F =', f
20 
21 h = array([[1,2],[3,4]])
22 print 'H =', h
23 
24 g = iaconv2(f, h)
25 print 'G = ', g
F = [[ 0.  0.  0.]
 [ 0.  1.  0.]
 [ 0.  0.  0.]]
H = [[1 2]
 [3 4]]
G = [[ 0.  0.  0.  0.]
 [ 0.  0.  0.  0.]
 [ 0.  0.  0.  0.]
 [ 0.  0.  0.  0.]]
G00 = [[ 0.  0.  0.  0.]
 [ 0.  1.  0.  0.]
 [ 0.  0.  0.  0.]
 [ 0.  0.  0.  0.]]
G01 = [[ 0.  0.  0.  0.]
 [ 0.  0.  2.  0.]
 [ 0.  0.  0.  0.]
 [ 0.  0.  0.  0.]]
G10 = [[ 0.  0.  0.  0.]
 [ 0.  0.  0.  0.]
 [ 0.  3.  0.  0.]
 [ 0.  0.  0.  0.]]
G11 = [[ 0.  0.  0.  0.]
 [ 0.  0.  0.  0.]
 [ 0.  0.  4.  0.]
 [ 0.  0.  0.  0.]]
G =  [[ 0.  0.  0.  0.]
 [ 0.  1.  2.  0.]
 [ 0.  3.  4.  0.]
 [ 0.  0.  0.  0.]]

É possível verificar que o resultado de cada iteração impresso pela função iaconv2 condiz com o cálculo obtido pela descrição matemática do algoritmo.

2. Obtenção do filtro aplicado sobre uma imagem através da propriedade de impulso

O impulso é o elemento neutro da convolução. E a partir desta propriedade é possível, por exemplo, descobrir o filtro aplicado sobre uma determinada imagem.

Seja F a matriz de uma imagem binária composta por elementos nulos e apenas um elemento de valor igual a um, localizado na posição i = j = 1.

E H a matriz de um filtro.

A convolução discreta bidimensional de F por H é dada pela matriz G, cuja submatriz formada pelos elementos contidos entre i = 1, 2, 3, ..., c e j = 1, 2, 3, ..., d equivale a H, ou seja, ao filtro aplicado sobre a imagem binária.

A dimensão da submatriz de G é obtida pela expressão

O código fonte a seguir exemplifica o uso da propriedade de impulso para se obter a matriz de um filtro aplicado sobre a matriz de uma imagem binária.

 1 # f = matriz de uma imagem binária
 2 # g = matriz resultante da convolução de uma imagem binária com um filtro
 3 def getFilter(f, g):
 4     f, g = asarray(f), asarray(g)
 5     a, b = f.shape
 6     m, n = g.shape
 7     c, d = m - a + 1, n - b + 1
 8     return g[0:c, 0:d]
 9 
10 # Matriz de uma imagem binária
11 f      = zeros([3,3])
12 f[0,0] = 1
13 
14 # Filtro aplicado sobre uma imagem binária
15 h = array([[0,1,0],[1,-4,1],[0,1,0]])
16 
17 # Imagem gerada pela convolução da imagem binária com o filtro
18 g = iaconv(f, h)
19 
20 # Filtro obtido através da propriedade de impulso
21 H = getFilter(f, g)
22 
23 print 'Filtro aplicado sobre a imagem binária:'
24 print h
25 print ''
26 print 'Filtro obtido pela propriedade de impulso:'
27 print H
28 print ''
29 print 'Equivalência:'
30 if alltrue(equal(h, H)):
31     print 'O filtro aplicado sobre a imagem binária EQUIVALE ao filtro obtido pela propriedade de impulso.'
32 else:
33     print 'O filtro aplicado sobre a imagem binária NÃO equivale ao filtro obtido pela propriedade de impulso.'
Filtro aplicado sobre a imagem binária:
[[ 0  1  0]
 [ 1 -4  1]
 [ 0  1  0]]

Filtro obtido pela propriedade de impulso:
[[ 0.  1.  0.]
 [ 1. -4.  1.]
 [ 0.  1.  0.]]

Equivalência:
O filtro aplicado sobre a imagem binária EQUIVALE ao filtro obtido pela propriedade de impulso.

3. Desempenho computacional do algoritmo usado na função iaconv

Como já foi dito anteriormente, o algoritmo utilizado na função iaconv possui um desempenho computacional superior aos demais que implementam com exatidão a equação da convolução discreta. Isto se deve ao baixo número de laços existentes neste algoritmo, dado por

Enquanto o número de laços dos algoritmos que implementam com exatidão a equação da convolução discreta é

Por exemplo, dado duas imagem F de dimensões 250 x 250 e 500 x 500, e dois filtros de dimensões 3 x 3 e 5 x 5, obtém-se

a b c d Liaconv Lx Liaconv / Lx
250 250 3 3 562500 4032758016 0.0001394827
250 250 5 5 1562500 4162314256 0.00037539212
500 500 3 3 2250000 63506016000 0.000035429
500 500 5 5 6250000 64524128000 0.000096862

Através da tabela é possível verificar o alto desempenho do algoritmo usado na função iaconv. Isto acarreta em uma redução do tempo gasto com o processamento da convolução discreta. É o que pode ser verificado quando comparamos a função ConvolucaoDiscreta2D, apresentada abaixo, com a iaconv.

 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

O código fonte abaixo apresenta uma breve comparação do tempo gasto com o processamento da convolução discreta de uma matriz F com um filtro H entre ambas as funções.

 1 # Matriz de uma imagem binária
 2 f      = zeros((7,7))
 3 f[3,3] = 1
 4 print 'F =', f
 5 print ''
 6 
 7 # Matriz de um filtro passa-baixa
 8 h = array([[1,2,3],[4,5,6],[7,8,9]])
 9 print 'H =', h
10 print ''
11 
12 a, b = f.shape
13 c, d = h.shape
14 
15 print 'a x b = ' + str(a) + ' x ' + str(b)
16 print 'c x d = ' + str(c) + ' x ' + str(d)
17 print ''
18 
19 # Função iaconv da biblioteca ia636
20 ts = time.time()
21 g  = iaconv(f, h)
22 te = time.time()
23 print 'Função iaconv:'
24 print 'G = ', g
25 print 'Tempo gasto = ' + str(round((te - ts) * 100000) / 100) + ' milisegundos'
26 print 'Número de laços = ' + str(a*b*c*d)
27 print ''
28 
29 # Função ConvolucaoDiscreta2D
30 ts = time.time()
31 g  = ConvolucaoDiscreta2D(f, h)
32 te = time.time()
33 print 'Função ConvolucaoDiscreta2D:'
34 print 'G = ', g
35 print 'Tempo gasto = ' + str(round((te - ts) * 100000) / 100) + ' milisegundos'
36 print 'Número de laços = ' + str(pow((a+c-1)*(b+d-1),2))
F = [[ 0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  1.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.]]

H = [[1 2 3]
 [4 5 6]
 [7 8 9]]

a x b = 7 x 7
c x d = 3 x 3

Função iaconv:
G =  [[ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  1.  2.  3.  0.  0.  0.]
 [ 0.  0.  0.  4.  5.  6.  0.  0.  0.]
 [ 0.  0.  0.  7.  8.  9.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]]
Tempo gasto = 0.26 milisegundos
Número de laços = 441

Função ConvolucaoDiscreta2D:
G =  [[ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  1.  2.  3.  0.  0.  0.]
 [ 0.  0.  0.  4.  5.  6.  0.  0.  0.]
 [ 0.  0.  0.  7.  8.  9.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.]]
Tempo gasto = 11.78 milisegundos
Número de laços = 6561

Como o tempo gasto com o processamento da convolução pela função ConvolucaoDiscreta2D é muito alto, torna-se inviável exemplificar o uso de filtros em imagens, que possuem alto número de pixels, por ela. Por isso, será utilizado apenas a função iaconv.

Uma imagem de um fotógrafo apresentado na Figura 1 será utilizado para exemplificar o uso de filtros passa-baixa e passa-alta usando a função iaconv.

Figura 1 - Imagem de um fotógrafo.

A Figura 2 ilustra um filtro passa-baixa aplicado sobre a imagem da Figura 1. Nesta caso um filtro de média que visa suavizar a imagem.

(a) Máscara 3 x 3.

(b) Máscara 5 x 5.

Figura 2 - Filtro passa-baixa.

Já a Figura 3 apresenta um filtro passa-alta aplicado sobre a imagem da Figura 1, que visa destacar as bordas da imagem.

(a) Máscara 3 x 3.

(b) Máscara 5 x 5.

Figura 3 - Filtro passa-alta.