daniel_chiu_Ex1

  1. Se registrar no Adessowiki e criar a sua página de diário do curso - OK
  2. Estudar o Python (primer ou tutorial) http://docs.python.org/tutorial. Existe um site do Python no Brasil que pode ser útil também: http://www.pythonbrasil.com.br - OK
  3. Estudar o NumPy (tutorial, para entender arrays e pequenos truques de processamento de imagem). http://www.scipy.org/Tentative_NumPy_Tutorial - OK
  4. Fazer um exercício que mostre os principais conceitos aprendidos. Procure fazer exercícios com matriz numérica de tamanho reduzido. - ver abaixo - OK
  5. Estudar formas de gerar uma imagem xadrez e implementar algumas de sua preferência. Veja em http://calhau.dca.fee.unicamp.br/wiki/index.php/IA354I1S2007_Exercicios - ver abaixo - OK

Item 4

O Python pode manipular alguns tipos estruturas de dados.

Listas
  • Lista é uma das estruturas de dados mais versáteis no Python.
  • Ela é escrita com os dados separados por vírgulas e entre colchetes.
  • Os dados contidos na lista podem ser de diferentes tipos.
  • Cada elemento da lista pode ser modificado.
1 lista=[10, 'teste', -0.59687, 3299., 'aula']
2 print 'Esta é uma lista: ', lista, '\n'
3 lista[2]=8 #terceiro elemento substituído por 8
4 print 'Observe o terceiro elemento substituído para 8.\n', lista
Esta é uma lista:  [10, 'teste', -0.59687000000000001, 3299.0, 'aula'] 

Observe o terceiro elemento substituído para 8.
[10, 'teste', 8, 3299.0, 'aula']
Tuplas
  • Tupla pode consistir por zero ou mais dados separados por vírgula.
  • Uma tupla não pode ter seus elementos mudados individualmente.
  • Pode-se atribuir várias variáveis a uma tupla, atribuindo a cada variável um elemento da tupla.
1 tupla=100,'segundo elemento',[1,2,3,4]
2 i,s,l=tupla #atribuição de variáveis a uma tupla
3 print 'Inteiro i = ',i
4 print 'String s = ',s
5 print 'Lista l = ',l
Inteiro i =  100
String s =  segundo elemento
Lista l =  [1, 2, 3, 4]
Arrays
  • Arrays são como as listas, porém somente manipulam dados numéricos.
  • Esta estrutura pode ter uma, duas, três ou mais dimensões.
  • Pode-se realizar operações aritméticas com arrays (soma, subtração, multiplicação, divisão, mõdulo, etc.)
  • Os arrays podem ser criado utilizando-se a função array() do numpy, como abaixo:
  • Em particular, o elemento de um array é lido primeiro pela linha e depois pela coluna
 1 A=array([[1,2,3],[45,67,89],[9.87,65.4,321.]])
 2 B=array([[9,8,7],[55,33,11],[-9.,-3.5,-400]])
 3 print 'A[2,1] = ',A[2,1], '\n'
 4 print 'array A\n', A, '\n'
 5 print 'array B\n', B, '\n'
 6 print 'Somatória dos elementos de A e B\n', A+B, '\n'
 7 print 'Subtração dos elementos de B dos de A\n', A-B, '\n'
 8 
 9 #Criação de array de números em seqüência
10 S=arange(3,13)
11 print 'Array de números em seqüência: ', S, '\n'
12 
13 #Criação de array de zeros (2D)
14 Z=zeros((3,6))
15 print 'Array de zeros:\n',Z, '\n'
16 
17 #Criação de array de uns (2D)
18 UNS=ones((3,6))
19 print 'Array de uns:\n',UNS, '\n'
A[2,1] =  65.4 

array A
[[   1.      2.      3.  ]
 [  45.     67.     89.  ]
 [   9.87   65.4   321.  ]] 

array B
[[   9.     8.     7. ]
 [  55.    33.    11. ]
 [  -9.    -3.5 -400. ]] 

Somatória dos elementos de A e B
[[  10.     10.     10.  ]
 [ 100.    100.    100.  ]
 [   0.87   61.9   -79.  ]] 

Subtração dos elementos de B dos de A
[[  -8.     -6.     -4.  ]
 [ -10.     34.     78.  ]
 [  18.87   68.9   721.  ]] 

Array de números em seqüência:  [ 3  4  5  6  7  8  9 10 11 12] 

Array de zeros:
[[ 0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.]] 

Array de uns:
[[ 1.  1.  1.  1.  1.  1.]
 [ 1.  1.  1.  1.  1.  1.]
 [ 1.  1.  1.  1.  1.  1.]]

Item 5

Utilizei alguns métodos diferentes para gerar a imagem xadrez e medi o tempo decorrido para cada método. A imagem utilizada é de 50 linhas X 100 colunas.
Método com mgrid do numpy

Esta função utiliza o mgrid do numpy e foi inspirado no método com iameshgrid utilizado durante a aula.

Função chess_mgrid:

Entrada

  • h = altura da imagem
  • w = largura da imagem
  • print_img = mostra a imagem

Saída

  • A = array de dimensões h x w de zeros e uns intercalados.
 1 def chess_mgrid(h, w, print_img=True):
 2     t1=time.time() #tempo inicial da execução
 3 
 4     #mgrid gera duas matrizes: uma com cada elemento atribuído com o valor da sua
 5     #respectiva linha e outra com cada elemento atribuído com o valor da sua respectiva coluna
 6     M = mgrid[0:h, 0:w]
 7 
 8     A = (M[0]+M[1])%2 #soma-se cada elemento e tira módulo 2
 9 
10     t2=time.time() #tempo final da execução
11 
12     if(print_img):
13         mmshow(uint16(A), title = 'Imagem xadrez '+str(h)+' X '+str(w)+' - Tempo de execução = '+str(t2-t1) +'s')
14     return A
15 
16 
17 
18 #Imprime uma matriz 12x15 sem mostrar a imagem
19 print 'Essa é uma matriz xadrez 12x15'
20 M = chess_mgrid(12,15,False)
21 print M
22 
23 #Imprime uma imagem 50x100
24 chess_mgrid(50,100)
Essa é uma matriz xadrez 12x15
[[0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]]

Imagem xadrez 50 X 100 - Tempo de execução = 0.00032901763916s

Método com iameshgrid do ia636_toolbox

Esta função foi inspirada no método apresentado em aula e utiliza o iameshgrid do toolbox. Constrói a matriz de maneira similar ao método com mgrid do numpy.

Função chess_iameshgrid:

Entrada

  • h = altura da imagem
  • w = largura da imagem
  • print_img = mostra a imagem

Saída

  • A = array de dimensões h x w de zeros e uns intercalados.
 1 def chess_iameshgrid(h, w, print_img=True):
 2     t1=time.time() #tempo inicial da execução
 3 
 4     #iameshgrid gera duas matrizes: uma com cada elemento atribuído com o valor da sua
 5     #respectiva linha (J) e outra com
 6     #cada elemento atribuído com o valor da sua respectiva coluna (I)
 7     J,I=iameshgrid(range(0,w), range(0,h))
 8 
 9 
10     A = (I+J)%2 #soma-se cada elemento e tira módulo 2
11 
12     t2=time.time() #tempo final da execução
13 
14     if(print_img):
15         mmshow(uint16(A), title = 'Imagem xadrez '+str(h)+' X '+str(w)+' - Tempo de execução = '+str(t2-t1) +'s')
16     return A
17 
18 
19 
20 #Imprime uma matriz 12x15 sem mostrar a imagem
21 print 'Essa é uma matriz xadrez 12x15'
22 M = chess_iameshgrid(12,15,False)
23 print M
24 
25 #Imprime uma imagem 50x100
26 chess_iameshgrid(50,100)
Essa é uma matriz xadrez 12x15
[[0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]]

Imagem xadrez 50 X 100 - Tempo de execução = 0.000250816345215s

Método com redimensionamento e concatenação

Esta função gera um array unidimensional grande de zeros e uns, que depois é redimensionado ao tamanho desejado. A concatenação acontece quando a largura da imagem desejada for par, como explicado no código.

Função chess_resizing:

Entrada

  • h = altura da imagem
  • w = largura da imagem
  • print_img = mostra a imagem

Saída

  • A = array de dimensões h x w de zeros e uns intercalados.
 1 def chess_resizing(h, w, print_img=True):
 2     t1=time.time() #tempo inicial da execução
 3 
 4     #Se a largura w tiver valor ímpar, na hora que o array for redimensionado
 5     #para o tamanho desejado ele ficará no formato que desejamos.
 6     #Ex.: array 2x3: [0 1 0 1 0 1] -> [[0 1 0][1 0 1]]
 7     #Isso não funciona quando a largura w tiver valor par.
 8     #Ex.: array 3x4: [0 1 0 1 0 1 0 1 0 1 0 1] -> [[0 1 0 1][0 1 0 1][0 1 0 1]] -> não é o que desejamos
 9 
10     if (w%2)==1:    #largura w é ímpar
11         #formação do array de zeros e uns
12         A=arange(0,w*h)
13         A=A%2
14 
15         #redimensionamento
16         A.resize((h,w))
17 
18     #Se a largura w for par, pode-se construir um array de tamanho ímpar primeiro e
19     #concatenar com um array de largura unitária.
20     #No exemplo do array 3x4, constrói-se um array menor (3x3) antes e concatena-se com
21     #um array 3x1.
22     #array 3x3: [0 1 0 1 0 1 0 1 0] -> [[0 1 0][1 0 1][0 1 0]]
23     #array 3x1: sabemos que o último elemento da primeira linha começa com 1, então:
24     #[[1][0][1]]
25     #Concatenação entre [[0 1 0][1 0 1][0 1 0]] e [[1][0][1]]
26     #Resulta em: [[0 1 0 1][1 0 1 0][0 1 0 1]]
27 
28     else:     #largura w é par
29         #formaçãos dos arrays de zeros e uns (um de largura ímpar e outro de largura unitária)
30         A1=arange(0,(w-1)*h)
31         A2=arange(1, h+1)
32         A1,A2=A1%2,A2%2
33 
34         #redimensionamento
35         A1.resize((h,w-1))
36         A2.resize((h,1))
37 
38         #concatenação dos dois arrays
39         A=hstack((A1,A2))
40 
41     t2=time.time() #tempo final da execução
42 
43     if(print_img):
44         mmshow(uint16(A), title = 'Imagem xadrez '+str(h)+' X '+str(w)+' - Tempo de execução = '+str(t2-t1) +'s')
45     return A
46 
47 
48 
49 #Imprime uma matriz 12x15 sem mostrar a imagem
50 print 'Essa é uma matriz xadrez 12x15'
51 M = chess_resizing(12,15,False)
52 print M
53 
54 #Imprime uma matriz 12x16 sem mostrar a imagem
55 print 'Essa é uma matriz xadrez 12x16'
56 N = chess_resizing(12,16,False)
57 print N
58 
59 #Imprime uma imagem 50x100
60 chess_resizing(50,100)
Essa é uma matriz xadrez 12x15
[[0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]]
Essa é uma matriz xadrez 12x16
[[0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]]

Imagem xadrez 50 X 100 - Tempo de execução = 0.000143051147461s

Método utilizando fromfunction() do numpy

Criando-se e utilizando uma função que dá o módulo 2 da soma de dois números, podemos preencher o array com a função fromfunction do numpy.

Função bit_gen:

Entrada

  • i = valor que representa a linha de cada elemento
  • j = valor que representa a coluna de cada elemento

Saída

  • 0, se a soma de i e j for par, ou 1, se a soma de i e j for ímpar

Função chess_fromfunction:

Entrada

  • h = altura da imagem
  • w = largura da imagem
  • print_img = mostra a imagem

Saída

  • A = array de dimensões h x w de zeros e uns intercalados.
 1 def bit_gen(i, j):
 2     return (i+j)%2
 3 
 4 def chess_fromfunction(h, w, print_img=True):
 5     t1=time.time() #tempo inicial da execução
 6 
 7     A = fromfunction(bit_gen, (h, w)) #preenche-se o array segundo a função bit_gen
 8 
 9     t2=time.time() #tempo final da execução
10 
11     if(print_img):
12         mmshow(uint16(A), title = 'Imagem xadrez '+str(h)+' X '+str(w)+' - Tempo de execução = '+str(t2-t1) +'s')
13     return A
14 
15 
16 
17 #Imprime uma matriz 12x15 sem mostrar a imagem
18 print 'Essa é uma matriz xadrez 12x15'
19 M = chess_fromfunction(12,15,False)
20 print M
21 
22 #Imprime uma imagem 50x100
23 chess_fromfunction(50,100)
Essa é uma matriz xadrez 12x15
[[ 0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.]
 [ 1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.]
 [ 0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.]
 [ 1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.]
 [ 0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.]
 [ 1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.]
 [ 0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.]
 [ 1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.]
 [ 0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.]
 [ 1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.]
 [ 0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.]
 [ 1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.  0.  1.]]

Imagem xadrez 50 X 100 - Tempo de execução = 0.000137090682983s

Método com tile do numpy

Esta função utiliza a função tile do numpy, utilizando, como modelo a matriz quadrada: [[0 1][1 0]]. Função chess_tile:

Entrada

  • h = altura da imagem
  • w = largura da imagem
  • print_img = mostra a imagem

Saída

  • A = array de dimensões h x w de zeros e uns intercalados.
 1 def chess_tile(h, w, print_img=True):
 2     t1=time.time() #tempo inicial da execução
 3 
 4     BASE=array([[0,1],[1,0]])  #array-base para utilização da função tile
 5 
 6     #preenche-se o array além do tamanho da imagem desejada,
 7     #pois como o array-base possui dimensões de tamanho par,
 8     #deve-se contornar a situação de gerar array com dimensões
 9     #de tamanho ímpar.
10     A=tile(BASE,(h/2+1,w/2+1))
11 
12     #realiza-se o slicing desse array, obtendo a matriz desejada
13     A=A[0:h:1,0:w:1]
14 
15     t2=time.time() #tempo final da execução
16 
17     if(print_img):
18         mmshow(uint16(A), title = 'Imagem xadrez '+str(h)+' X '+str(w)+' - Tempo de execução = '+str(t2-t1) +'s')
19     return A
20 
21 
22 
23 #Imprime uma matriz 12x15 sem mostrar a imagem
24 print 'Essa é uma matriz xadrez 12x15'
25 M = chess_tile(12,15,False)
26 print M
27 
28 #Imprime uma imagem 50x100
29 chess_tile(50,100)
Essa é uma matriz xadrez 12x15
[[0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
 [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
 [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]]

Imagem xadrez 50 X 100 - Tempo de execução = 6.79492950439e-05s

Conclusão: dos métodos apresentados acima, o método que utiliza tile do numpy é o mais eficiente. Além disso, é curioso observar que os dois métodos que utilizam função do tipo meshgrid possuem tempos diferentes, sendo o mais eficiente o que utiliza o iameshgrid. Isso acontece provavelmente pelo fato do iameshgrid da ia636_toolbox ser mais eficiente que o mgrid do numpy. Contudo, não são mais eficientes que os demais métodos aqui apresentados.