daniel_chiu_Ex7

Autor: daniel_chiu
Data: 01/05/2009

Item 1

A equação utilizada na função iaconv é a seguinte.

Onde:

E os tamanhos dos arrrays são dados por:

Item 2

Convolução

A convolução é uma operação matemática entre duas funções que é comumente aplicada em Processamento de Imagens Digitais.

A operação de convolução pode ser descrita da seguinte forma:

Na forma discreta, tal equação pode ser escrita assim:

No tratamento de imagens digitais, a convolução é realizada no modo discreto e dentro do domínio da imagem. A equação para a convolução discreta em duas dimensões é:

Onde os tamanhos das imagens são definidos por: .

O tamanho da matriz de convolução é , onde e

Dessa maneira, a imagem convoluída terá dimensões maiores que a imagem original, a não ser que a máscara seja de tamanho 1x1.

Propriedades matemáticas da convolução

A convolução satisfaz as seguintes propriedades algébricas:

  • Comutativa:
F
[[1 2 3 1 0]
 [3 4 2 2 1]
 [2 1 2 1 3]
 [0 2 2 1 4]
 [1 4 3 2 1]] 

G
[[1 1 1]
 [1 1 1]
 [1 1 1]] 

F*G
[[ 1  3  6  6  4  1  0]
 [ 4 10 15 14  9  4  1]
 [ 6 13 20 18 15  8  4]
 [ 5 12 18 17 18 12  8]
 [ 3 10 17 18 19 12  8]
 [ 1  7 12 14 13  8  5]
 [ 1  5  8  9  6  3  1]] 

G*F
[[ 1  3  6  6  4  1  0]
 [ 4 10 15 14  9  4  1]
 [ 6 13 20 18 15  8  4]
 [ 5 12 18 17 18 12  8]
 [ 3 10 17 18 19 12  8]
 [ 1  7 12 14 13  8  5]
 [ 1  5  8  9  6  3  1]]
  • Distributiva:
H
[[ 0  1  0]
 [ 1 -4  1]
 [ 0  1  0]] 

F*(G+H)
[[ 1  4  8  9  5  1  0]
 [ 5 11 15  7 10  6  1]
 [ 9  8 12 21 12  9  5]
 [ 7  8 24 15 22  6 11]
 [ 3 15 16 18 24  1 12]
 [ 2  7  2 10 10 10  6]
 [ 1  6 12 12  8  4  1]] 

F*G+F*H
[[ 1  4  8  9  5  1  0]
 [ 5 11 15  7 10  6  1]
 [ 9  8 12 21 12  9  5]
 [ 7  8 24 15 22  6 11]
 [ 3 15 16 18 24  1 12]
 [ 2  7  2 10 10 10  6]
 [ 1  6 12 12  8  4  1]]
  • Associativa:

    entre funções

    F
    [[1 2 3 1 0]
     [3 4 2 2 1]
     [2 1 2 1 3]
     [0 2 2 1 4]
     [1 4 3 2 1]] 
    
    G
    [[1 0 1]] 
    
    H
    [[ 1]
     [-2]
     [ 1]] 
    
    F*(G*H)
    [[ 1  2  4  3  3  1  0]
     [ 1  0 -3  0 -3  0  1]
     [-3 -5 -2 -7  2 -2  1]
     [-1  4 -1  5 -1  1 -1]
     [ 3  1  4  2 -3  1 -4]
     [-2 -6 -6 -9 -2 -3  2]
     [ 1  4  4  6  4  2  1]] 
    
    (F*G)*H
    [[ 1  2  4  3  3  1  0]
     [ 1  0 -3  0 -3  0  1]
     [-3 -5 -2 -7  2 -2  1]
     [-1  4 -1  5 -1  1 -1]
     [ 3  1  4  2 -3  1 -4]
     [-2 -6 -6 -9 -2 -3  2]
     [ 1  4  4  6  4  2  1]]
    

    com multiplicação escalar

    k= 0.111111111111 
    
    F
    [[1 2 3 1 0]
     [3 4 2 2 1]
     [2 1 2 1 3]
     [0 2 2 1 4]
     [1 4 3 2 1]] 
    
    G
    [[1 1 1]
     [1 1 1]
     [1 1 1]] 
    
    F*(kG)
    [[0 0 0 0 0 0 0]
     [0 1 1 1 1 0 0]
     [0 1 2 2 1 0 0]
     [0 1 1 1 2 1 0]
     [0 1 1 2 2 1 0]
     [0 0 1 1 1 0 0]
     [0 0 0 1 0 0 0]] 
    
    (kF)*G
    [[0 0 0 0 0 0 0]
     [0 1 1 1 1 0 0]
     [0 1 2 2 1 0 0]
     [0 1 1 1 2 1 0]
     [0 1 1 2 2 1 0]
     [0 0 1 1 1 0 0]
     [0 0 0 1 0 0 0]] 
    
    k(F*G)
    [[0 0 0 0 0 0 0]
     [0 1 1 1 1 0 0]
     [0 1 2 2 1 0 0]
     [0 1 2 1 2 1 0]
     [0 1 1 2 2 1 0]
     [0 0 1 1 1 0 0]
     [0 0 0 1 0 0 0]]
    

A partir das propriedades acima, podemos deduzir que:

k1= 0.111111111111 

k2= 0.0625 

F
[[1 2 3 1 0]
 [3 4 2 2 1]
 [2 1 2 1 3]
 [0 2 2 1 4]
 [1 4 3 2 1]] 

G1
[[1 1 1]
 [1 1 1]
 [1 1 1]] 

G2
[[1 2 1]
 [2 4 2]
 [1 2 1]] 

F*(k1.G1+k2.G2)
[[0 0 1 1 0 0 0]
 [0 2 3 3 2 0 0]
 [1 3 4 4 3 1 0]
 [0 2 3 3 3 3 1]
 [0 2 3 4 4 3 1]
 [0 1 3 3 2 1 0]
 [0 0 1 1 1 0 0]] 

k1.(F*G1)+k2.(F*G2)
[[0 0 1 1 0 0 0]
 [0 2 3 3 2 0 0]
 [1 3 4 4 3 1 0]
 [0 2 3 3 3 3 1]
 [0 2 3 4 4 3 1]
 [0 1 3 3 2 1 0]
 [0 0 1 1 1 0 0]]

Resposta ao impulso

Ao realizar a convolução entre um sinal de impulso e uma matriz, o resultado será a própria matriz, como se vê abaixo.

F
[[1 2 3]
 [4 5 6]
 [7 8 9]]

DELTA
[[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]]

F*DELTA
[[0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0]
 [0 0 1 2 3 0 0]
 [0 0 4 5 6 0 0]
 [0 0 7 8 9 0 0]
 [0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0]]

Invariância à translação

A convolução é um operador invariante à translação, isto é:

Disso, pode-se inferir que o resultado da imagem convoluída depende da origem da máscara de convolução.

Imagem original

Imagem deslocada - 100 px à direita e 100 px abaixo

F deslocado * G

(F*G) deslocado

É possível, também, através da propriedade associativa, simplificar operações de convolução em cadeia. Isso é uma maneira de otimizar o código, exigindo menos processamento na imagem.

Exemplo: Pode-se utilizar a operação de convolução de uma matriz 1x3 com uma matriz 3x1, para gerar uma máscara de convolução 3x3.

A máscara de convolução pode ser feita através a convolução das duas matrizes acima

Imagem original

Imagem utilizando a máscara de convolução diretamente

Imagem utilizando a máscara de maneira otimizada

Corte de bordas

Como visto acima, a imagem convoluída possui um tamanho maior que a imagem original e, para realizar operações entre as imagens, é necessário cortar as bordas. Essas bordas são dependentes da origem da máscara.

Caso a máscara esteja no centro da imagem, por exemplo, a imagem ficará também centralizada e a borda a ser cortada possui tamanho Caso a máscara esteja no ponto (0,0), corta-se as extremidades da imagem.

No caso do exemplo acima, a máscara 15x15 está no centro da imagem. A borda possui tamanho .

Tamanho de IMG =  256 x 256 

Tamanho de IMG convoluído =  270 x 270

IMG convoluído sem corte de borda

IMG convoluído, com borda cortada

Item 3

Função dwsc_convolute implementado no exercício anterior:

 1 def dwsc_convolute(F,W,crop=1):
 2 
 3      b,a=F.shape
 4      d,c=W.shape
 5      m=a+c-1
 6      n=b+d-1
 7 
 8      G=zeros((n,m))
 9 
10      for s in range(0,c):
11          for t in range(0,d):
12             AUX=F
13 
14             # padding nos índices fora do limite das dimensões de f
15             if s>0:
16                 AUX=hstack((zeros((a,s)) ,AUX))
17             if c-1-s>0:
18                 AUX=hstack((AUX, zeros((a,c-1-s))))
19             if t>0:
20                 AUX=vstack((zeros((t,m)), AUX))
21             if d-1-t>0:
22                 AUX=vstack((AUX, zeros((d-1-t,m))))
23 
24             G=G+AUX*W[t,s]
25 
26      if crop==1:
27          G=G[(d-1)/2:n-(d-1)/2,(c-1)/2:m-(c-1)/2]
28 
29      return G
1 IMG=mmreadgray('lenina.pgm')
2 adshow(IMG, title='Imagem original')

Imagem original

Abaixo, utiliza-se a função acima para fazer a suavização e realce da imagem (usando "Unsharp masking").

 1 SMOOTH3=1.0/9 * ones((3,3))
 2 SMOOTH5=1.0/25 * ones((5,5))
 3 
 4 SMOOTHED_IMG3=dwsc_convolute(IMG,SMOOTH3).astype(int32)
 5 adshow(SMOOTHED_IMG3, title='Imagem suavizada com máscara 3x3')
 6 
 7 SMOOTHED_IMG5=dwsc_convolute(IMG,SMOOTH5).astype(int32)
 8 adshow(SMOOTHED_IMG5, title='Imagem suavizada com máscara 5x5')
 9 
10 DIFF3 = IMG-SMOOTHED_IMG3
11 DIFF5 = IMG-SMOOTHED_IMG5
12 
13 SHARP_IMG3 = IMG+DIFF3
14 SHARP_IMG5 = IMG+DIFF5
15 
16 SHARP_IMG3 *= 255.0/SHARP_IMG3.max() # normalização
17 SHARP_IMG5 *= 255.0/SHARP_IMG5.max() # normalização
18 
19 adshow(SHARP_IMG3.astype(int32), title='Imagem realçada com máscara 3x3, k=1.0')
20 adshow(SHARP_IMG5.astype(int32), title='Imagem realçada com máscara 5x5, k=1.0')
21 
22 SHARP_IMG3 = IMG+0.5*DIFF3
23 SHARP_IMG5 = IMG+0.5*DIFF5
24 
25 SHARP_IMG3 *= 255.0/SHARP_IMG3.max() # normalização
26 SHARP_IMG5 *= 255.0/SHARP_IMG5.max() # normalização
27 
28 adshow(SHARP_IMG3.astype(int32), title='Imagem realçada com máscara 3x3, k=0.5')
29 adshow(SHARP_IMG5.astype(int32), title='Imagem realçada com máscara 5x5, k=0.5')

Imagem suavizada com máscara 3x3

Imagem suavizada com máscara 5x5

Imagem realçada com máscara 3x3, k=1.0

Imagem realçada com máscara 5x5, k=1.0

Imagem realçada com máscara 3x3, k=0.5

Imagem realçada com máscara 5x5, k=0.5

Abaixo, utiliza-se a função iaconv para fazer a suavização e realce da imagem (usando "Unsharp masking").

 1 SMOOTHED_IMG3=iaconv(IMG,SMOOTH3).astype(int32)
 2 SMOOTHED_IMG3=SMOOTHED_IMG3[1:IMG.shape[0]+1,1:IMG.shape[1]+1] # corte de bordas
 3 adshow(SMOOTHED_IMG3, title='Imagem suavizada com máscara 3x3')
 4 
 5 SMOOTHED_IMG5=iaconv(IMG,SMOOTH5).astype(int32)
 6 SMOOTHED_IMG5=SMOOTHED_IMG5[2:IMG.shape[0]+2,2:IMG.shape[1]+2] # corte de bordas
 7 adshow(SMOOTHED_IMG5, title='Imagem suavizada com máscara 5x5')
 8 
 9 DIFF3 = IMG-SMOOTHED_IMG3
10 DIFF5 = IMG-SMOOTHED_IMG5
11 
12 SHARP_IMG3 = IMG+DIFF3
13 SHARP_IMG5 = IMG+DIFF5
14 
15 SHARP_IMG3 *= 255.0/SHARP_IMG3.max() # normalização
16 SHARP_IMG5 *= 255.0/SHARP_IMG5.max() # normalização
17 
18 adshow(SHARP_IMG3.astype(int32), title='Imagem realçada com máscara 3x3, k=1.0')
19 adshow(SHARP_IMG5.astype(int32), title='Imagem realçada com máscara 5x5, k=1.0')
20 
21 SHARP_IMG3 = IMG+0.5*DIFF3
22 SHARP_IMG5 = IMG+0.5*DIFF5
23 
24 SHARP_IMG3 *= 255.0/SHARP_IMG3.max() # normalização
25 SHARP_IMG5 *= 255.0/SHARP_IMG5.max() # normalização
26 
27 adshow(SHARP_IMG3.astype(int32), title='Imagem realçada com máscara 3x3, k=0.5')
28 adshow(SHARP_IMG5.astype(int32), title='Imagem realçada com máscara 5x5, k=0.5')

Imagem suavizada com máscara 3x3

Imagem suavizada com máscara 5x5

Imagem realçada com máscara 3x3, k=1.0

Imagem realçada com máscara 5x5, k=1.0

Imagem realçada com máscara 3x3, k=0.5

Imagem realçada com máscara 5x5, k=0.5