MatiasEx1

Autor:Matias
Data:12/03/2009

Exercício de gerar uma imagem com padrão Xadrez

Solução feita como estudo da linguagem, utilizando a função tile

Essa solução foi criada como estudo da linguagem python, consultando a documentação fornecida. Portanto deixa a desejar em termos de otimização.

  • Ela utiliza a função tile, que repete uma matriz menor dentro de uma maior.
  • Entrentato, em testes, ele pareceu gerar erro em alguns casos onde o número de repetições não era inteiro. Isso acontece quando o tamanho da imagem não é um multiplo do tamanho da célula.
  • Para esses casos, foi criada uma matriz maior, e então cortada para o tamanho da imagem desejada.
  • O código está bem "sujo". Parte do problema foi tentar evitar o "bug severo" descrito em http://parati.dca.fee.unicamp.br/adesso/wiki/ia636-2009/Bugs/view/
 1 def cria_xadrez_tile(imagemw, imagemh, casaw, casah):
 2 
 3     # Cria a matriz / tile inicial
 4     # Mantido em várias linhas devido ao bug severo descrito na página de bugs
 5     # (caso contrário vai referenciar a mesma variável mais de uma vez na mesma atribuição)
 6 
 7     # Matriz de 0 (preto)
 8     A = zeros([casah,casaw])
 9 
10     # Matriz de 1 (branco)
11     B = ones([casah,casaw])
12 
13     # Concatena as matrizes de forma a criar um TILE completo.
14     C = concatenate((A,B),axis=1)
15     D = concatenate((B,A),axis=1)
16     TILE = concatenate((C,D),axis=0)
17 
18 
19     # resto é usado para determinar se os tiles se encaixam perfeitamente no tamanho da imagem.
20     restow = imagemw % (2*casaw)
21     restoh = imagemh % (2*casah)
22 
23     # Caso se encaixe exatamente, cria a matriz direto do comando TILE
24     if (restoh==0) and (restow==0):
25         MATRIZ = tile(TILE, [(imagemh//(2*casah)),(imagemw // (2*casaw))])
26     else:
27     # Caso contrário, cria uma matriz com um TILE a mais, e dai corta para o tamanho da imagem.
28         MATRIZ_TEMP = tile(TILE, [(imagemh//(2*casah))+1,(imagemw // (2*casaw))+1])
29         MATRIZ=zeros([imagemh,imagemw])
30         MATRIZ=MATRIZ_TEMP[0:imagemh,0:imagemw]
31 
32     # Mostra a imagem do TILE, e a imagem final.
33     mmshow(uint16(TILE),title = "Tile usado para a criação da imagem")
34     mmshow(uint16(MATRIZ),title = "Imagem final")
35 
36 # Chama o procedimento e escreve o tempo de processamento.
37 time1 = time.time()
38 cria_xadrez_tile(200,200,20,20)
39 print "Tempo de processamento", time.time()-time1
Tempo de processamento 0.00740313529968

Tile usado para a criação da imagem

Imagem final

Soluções utilizando técnicas fornceidas

As bases para essas implementações foram tiradas de: http://calhau.dca.fee.unicamp.br/wiki/index.php/IA354I1S2007_Exercicios

Foram utilizadas as seguintes ténicas:

  • Técnica iterativa (não matricial):
    • Baseado no algoritimo fornecido, mas alterada para suportar quadriculados de diversos tamanhos.
  • Técnica de slice
    • Esta técnica tem a limitação de só produzir imagem quadriculada pixel a pixel, ou seja, o equivalente a especificar o tamanho da casa de "1" nos demais algoritimos.
 1 def cria_xadrez_iter(imagemw, imagemh, casaw, casah):
 2 
 3     # Cria Matriz inicial de zeros, do tamanho da imagem.
 4     MATRIZ=zeros([imagemh,imagemw])
 5 
 6     # Esses valores são usados, novamente, para evitar o "bug severo" e não referenciar a mesma variável em atribuições.
 7     # Na prática, também devem melhorar a performace ao custo de alguma memória.
 8     casahx2=casah*2
 9     casawx2=casaw*2
10 
11     for i in range(imagemh):
12         for j in range(imagemw):
13             # para cada pixel, primeiro cria faixas horizontais de acordo com o tamanho de casah
14             MATRIZ[i,j]=double( (i%casahx2>=casah))
15 
16             # Agora, nas faixas verticais baseadas no tamanho de casaw, inverte o valor atual presente
17             # na matriz.
18             if (j%casahx2>=casah):
19                 MATRIZ[i,j]=double( not (MATRIZ[i,j]==1))
20     return MATRIZ
21 
22 # Utiliza função slice para criar a imagem. Limitado a quadriculados de 1 pixel.
23 def cria_xadrez_slice(imagemw, imagemh):
24     # Cria matriz incial
25     MATRIZ = zeros([imagemw,imagemh])
26     # de dois em dois pixels, associa valor 1 (branco) ao quadriculado.
27     MATRIZ[::2,1::2]=1
28     MATRIZ[1::2,::2]=1
29     return MATRIZ
30 
31 # Chama as duas funções
32 mmshow(uint16(cria_xadrez_iter(200,200,20,20)),title = "Método iterativo")
33 mmshow(uint16(cria_xadrez_slice(200,200)),title = "Método de slice")

Método iterativo

Método de slice

Comparação de desempenho

  • Devido a limitação do algoritimo de slice, essa comparação é feita com quadriculados de 1 pixel de largura.
  • No final, é feita uma comparação apenas entre os algoritimos que suportam tamanho diferentes de quadriculados.

Tile: 0.40317ms

Iterativo: 61.31101ms

Slice: 0.11492ms

Tile (10pixels): 0.14901ms

Iterativo (10pixels): 60.95219ms

Conclusão

  • Os algoritimos matriciais (tile e slice) se mostraram ordens de grandeza mais eficientes que o iterativo. Isso deixa bem claro a necessidade de se trabalhar com matrizes ao invés dos métodos que eu pessoalmente estou mais acostumado.
  • Embora o de Slice também tenha se mostrado muito mais eficiente que o do Tile, deve-se levar em conta que ele possui a limitação de não ter a versatilidade de produzir imagens com quadriculados de tamanhos diferentes.
  • Outro ponto importante é mostrado pela comaparação entre o algoritimo de Tile e o Iterativo com quadriculados de 10 pixels de largura. O iterativo, por sempre fazer o processamento pixel a pixel, não tem o tempo de processamento alterado. O método matricial já mostra uma melhora significativa de desempenho.