MatiasEx7

Autor: Matias
Data: 08/05/2009

Item 1

Para manter uma consistência, todos os indices de matrizes descritos aqui começam no número 0, isto é, F(0,0) é o primeiro elemento da matriz F.

O código da função iaconv() do toolbox é o seguinte:

 1 def iaconv_exemplo(f, h):
 2     from numpy import asarray, newaxis, zeros, array, product
 3 
 4     f, h = asarray(f), asarray(h)
 5     if len(f.shape) == 1: f = f[newaxis,:]
 6     if len(h.shape) == 1: h = h[newaxis,:]
 7     if product(f.shape) < product(h.shape):
 8         f, h = h, f
 9     g = 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     return g
Alguns itens importantes de se notar:
  1. Na linha 7 existe uma comparação entre o tamanho total das matrizes F e H, para se garantir que h é matriz menor.
  2. G é uma matriz de elementos zeros com dimensões iguais as somas das dimensões equivalentes de F e H e subtraindo-se 1.
  3. Por motivos de otimização e aproveitando a propriedade de comutação da convolução, a função faz a interação somando a matriz maior (F) multiplicada por um elemento de H, dentro da matriz resultado (G).

Assim, temos:

Pensando-se apenas em termos do um elemento de cooredenadas i e j, a formulação da função é a seguinte:

Onde:

Entretanto, embora essa seja uma descrição válida, e a base da implementação feita no exercício 6, na prática como foi notado a função iaconv() não faz a interação elemento a elemento, e sim trabalha de forma matricial, somanndo matrizes dentro da matriz resultado G.

Para expressar isso de forma matemática, primeiro será definido uma matriz O de elementos zeros, que pode ter dimensões variadas, da seguinte forma:

Em outras palavras, O(5x5) é uma matriz de zeros de dimensões 5 por 5, e O(0,0) é uma matriz inexistente, que não afeta a concatenação a seguir.

Utilizando essa definição, a forma como é feita a interação na função iaconv() é a seguinte:

Item 2

Description

In this lesson we review and demonstrate some important properties of the convolution operation.

Commutation

Commutation is one important property of convolution.

The function iaconv() uses this property to optimize the implementation, by swapping the order of the matrixes according to their sizes. For example, the following function is the same as the original iaconv() but without this optimization.

 1 def iaconv2(f, h):
 2     from numpy import asarray, newaxis, zeros, array, product
 3 
 4     f, h = asarray(f), asarray(h)
 5     if len(f.shape) == 1: f = f[newaxis,:]
 6     if len(h.shape) == 1: h = h[newaxis,:]
 7     g = zeros(array(f.shape) + array(h.shape) - 1)
 8     for i in range(h.shape[0]):
 9         for j in range(h.shape[1]):
10             g[i:i+f.shape[0], j:j+f.shape[1]] += h[i,j] * f
11     return g
12 
13 
14 imagem = ones([1000,1000])
15 kernel = ones([3,3]) / 9
16 
17 time1 = time.time()
18 imagem1 = iaconv(imagem,kernel)
19 tempo1_1 = str(round((time.time()-time1)*1000,5))+"ms"
20 time1 = time.time()
21 imagem1 = iaconv(imagem,kernel)
22 tempo1_2 = str(round((time.time()-time1)*1000,5))+"ms"
23 
24 time1 = time.time()
25 imagem2 = iaconv2(imagem,kernel)
26 tempo2_1 = str(round((time.time()-time1)*1000,5))+"ms"
27 time1 = time.time()
28 imagem2 = iaconv2(imagem,kernel)
29 tempo2_2 = str(round((time.time()-time1)*1000,5))+"ms"
30 
31 print tempo1_1,tempo1_2,tempo2_1,tempo2_2
32 
33 kernel = ones([3,3]) / 9
34 
35 print "Difference between matrixes:",any(imagem2-imagem1)
36 
37 imagem = mmreadgray('boat.ppm')
38 imagem1 = iaconv(imagem,kernel)
39 imagem2 = iaconv(kernel,imagem)
40 
41 adshow(imagem1,title = "iaconv2(image,kernel)")
42 adshow(imagem2,title = "iaconv2(kernel,imagem)")
43 
44 print "Difference between images:",any(imagem2-imagem1)
228.95598ms 224.90716ms 261.27791ms 201.91598ms
Difference between matrixes: False
Difference between images: False

iaconv2(image,kernel)

iaconv2(kernel,imagem)

The result images are exactly the same, but using a 1000x1000 and a 3x3 matrix, there are gains in processing time. The second example uses images to show that the results are the same with swapped operators.

Response to Impulse

1 h = arange(25).reshape([5,5])
2 f = [1]
3 
4 result = iaconv(f,h)
5 print "h = ",h
6 print "f = ",f
7 print "result =",result
h =  [[ 0  1  2  3  4]
 [ 5  6  7  8  9]
 [10 11 12 13 14]
 [15 16 17 18 19]
 [20 21 22 23 24]]
f =  [1]
result = [[  0.   1.   2.   3.   4.]
 [  5.   6.   7.   8.   9.]
 [ 10.  11.  12.  13.  14.]
 [ 15.  16.  17.  18.  19.]
 [ 20.  21.  22.  23.  24.]]

Item 3

Observação: A função convolution (disponível em ia636-2009:Matias_Modulos) foi corrigida pois a apresentada no exercício 6 possuía erros.

Detalhes

 1 from Matias_Modulos import *
 2 
 3 imagem = mmreadgray('leaf.tif')
 4 
 5 kernel = ones([3,3])
 6 kernel[1,1]=-8
 7 
 8 adshow(imagem,title='Imagem original')
 9 
10 
11 imagem_nova_matiasconv = convolution(imagem,kernel,periodic='false');
12 imagem_nova_iaconv = iaconv(imagem,kernel);
13 adshow(ianormalize(imagem_nova_matiasconv,[0,255]),title='convolution(): Imagem filtrada, detalhes, 3x3')
14 adshow(ianormalize(imagem_nova_iaconv,[0,255]),title='iaconv(): Imagem filtrada, detalhes, 3x3')
15 print "Diferença entre imagens geradas das funções (3x3): ",any(imagem_nova_matiasconv-imagem_nova_iaconv)
16 
17 
18 imagem_nova_matiasconv = ianormalize(imagem_nova_matiasconv,[-80,80])
19 imagem_nova_iaconv = ianormalize(imagem_nova_iaconv,[-80,80])
20 
21 imagem_padded = iapad(imagem,[kernel.shape[0]/2,kernel.shape[1]/2])
22 imagem_final_matiasconv = imagem_padded - imagem_nova_matiasconv
23 imagem_final_matiasconv = maximum(imagem_final_matiasconv,0)
24 imagem_final_matiasconv = minimum(imagem_final_matiasconv,255)
25 imagem_final_iaconv = imagem_padded - imagem_nova_iaconv
26 imagem_final_iaconv = maximum(imagem_final_iaconv,0)
27 imagem_final_iaconv = minimum(imagem_final_iaconv,255)
28 adshow(imagem_final_matiasconv,title='convolution(): Imagem combinada, 3x3')
29 adshow(imagem_final_iaconv,title='iaconv(): Imagem combinada, 3x3')
30 
31 kernel = ones([5,5])
32 kernel[1,1]=-24
33 imagem_nova_matiasconv = convolution(imagem,kernel,periodic='false');
34 imagem_nova_iaconv = iaconv(imagem,kernel);
35 
36 adshow(ianormalize(imagem_nova_matiasconv,[0,255]),title='convolution(): Imagem filtrada, detalhes, 5x5')
37 adshow(ianormalize(imagem_nova_iaconv,[0,255]),title='iaconv(): Imagem filtrada, detalhes, 5x5')
38 print "Diferença entre imagens geradas das funções (5x5): ",any(imagem_nova_matiasconv-imagem_nova_iaconv)
39 imagem_nova_matiasconv = ianormalize(imagem_nova_matiasconv,[-80,80])
40 imagem_nova_iaconv = ianormalize(imagem_nova_iaconv,[-80,80])
41 imagem_padded = iapad(imagem,[kernel.shape[0]/2,kernel.shape[1]/2])
42 imagem_final_matiasconv = imagem_padded - imagem_nova_matiasconv
43 imagem_final_matiasconv = maximum(imagem_final_matiasconv,0)
44 imagem_final_matiasconv = minimum(imagem_final_matiasconv,255)
45 imagem_final_iaconv = imagem_padded - imagem_nova_iaconv
46 imagem_final_iaconv = maximum(imagem_final_iaconv,0)
47 
48 adshow(imagem_final_matiasconv,title='convolution(): Imagem combinada, 5x5')
49 adshow(imagem_final_iaconv,title='iaconv(): Imagem combinada, 5x5')
Diferença entre imagens geradas das funções (3x3):  False
Diferença entre imagens geradas das funções (5x5):  False

Imagem original

convolution(): Imagem filtrada, detalhes, 3x3

iaconv(): Imagem filtrada, detalhes, 3x3

convolution(): Imagem combinada, 3x3

iaconv(): Imagem combinada, 3x3

convolution(): Imagem filtrada, detalhes, 5x5

iaconv(): Imagem filtrada, detalhes, 5x5

convolution(): Imagem combinada, 5x5

iaconv(): Imagem combinada, 5x5

Suavização

 1 from Matias_Modulos import *
 2 
 3 imagem = mmreadgray('boat.ppm')
 4 
 5 kernel = ones([3,3]) / 9
 6 
 7 imagem_nova_matiasconv = convolution(imagem,kernel,periodic='false');
 8 imagem_nova_iaconv = iaconv(imagem,kernel);
 9 
10 adshow(imagem,title='Imagem original')
11 adshow(imagem_nova_matiasconv,title='convolution(): Imagem filtrada, suavização, 3x3')
12 adshow(imagem_nova_iaconv,title='iaconv(): Imagem filtrada, suavização,3x3')
13 
14 print "Diferença entre imagens geradas das funções (3x3): ",any((imagem_nova_matiasconv-imagem_nova_iaconv).round(5))
15 
16 kernel = ones([5,5]) / 25
17 
18 imagem_nova_matiasconv = convolution(imagem,kernel,periodic='false');
19 imagem_nova_iaconv = iaconv(imagem,kernel);
20 
21 adshow(imagem_nova_matiasconv,title='convolution(): Imagem filtrada, suavização, 5x5')
22 adshow(imagem_nova_iaconv,title='iaconv(): Imagem filtrada, suavização,5x5')
23 
24 print "Diferença entre imagens geradas das funções (5x5): ",any((imagem_nova_matiasconv-imagem_nova_iaconv).round(5))
Diferença entre imagens geradas das funções (3x3):  False
Diferença entre imagens geradas das funções (5x5):  False

Imagem original

convolution(): Imagem filtrada, suavização, 3x3

iaconv(): Imagem filtrada, suavização,3x3

convolution(): Imagem filtrada, suavização, 5x5

iaconv(): Imagem filtrada, suavização,5x5