IA365I:1S2007 Exercicios

De DCA-Wiki

(Redirecionado de IA354I1S2007 Exercicios)

Contents

Exercícios

1a. aula - Geração de imagem xadrez

Objetivo
Expor o aluno para explorar as diferentes formas de se resolver um problema. Em particular, o MATLAB é bastante ineficiente para execução de algoritmos onde se exige a varredura explícita através de for de todos os pixels. A idéia é explorar a programação de altíssimo nível, usando primitivas eficientes de processamento de matrizes.
Enunciado
Fazer diversas funções de geração de imagem sintéticas de xadrez, onde os parâmetros passados são 4: h, w (altura e largura da imagem em número de pixels; e ph e pw (altura e largura da casa do xadrez, em pixels). Prover também um programa que calcule automaticamente o desempenho comparativo da execução das diversas soluções. Atenção: Estou solicitando que sejam implementadas várias algoritmos diferentes, inspirados na solução em python.


Template:

function a = xadrez_1(h,w,ph,pw)
% Cria imagem xadrez onde:
% h: altura da imagem em pixels
% w: largura da imagem em pixels
% ph: altura da casa de xadrez em pixels
% pw: largura da casa de xadrez em pixels

Informações de anos anteriores

  • Exercício 2001 no MATLAB - Enunciado do exercício dado em 2001 para ser feito no MATLAB, contendo três orientações de solução: varredura pixel a pixel usando for, replicação de matrizes e usando o meshgrid
  • Soluções em python - 7 programas que criam uma imagem xadrez, juntamente com um programa que calcula o seu tempo de execução.

Dúvidas

De
Andre Gomes
para
Lotufo

Olá professor

Tenho uma dúvida no exercício 01 proposto.

O programa deverá ser capaz de construir matrizes do tipo abaixo (ph=pw=2; h=3 e w=5; ou seja, com casas incompletas)?

0 0 1 1 0
0 0 1 1 0
1 1 0 0 1

Atenciosamente,

André

Resposta
Sim, seu exemplo está correto.

--Lotufo 09:35, 4 March 2007 (BRDT)


De
juliana.verga
para
Lotufo

Oi Prof., podemos usar a função checkerboard para gerar essa imagem? Uma outra opção seria usar o meshgrid, mas usando-o, não estamos achando um jeito de utilizar os parametros ph e pw. Atenciosamente,

                Juliana e Ingrid
Resposta
Juliana e Ingrid. A função checkerboard é da toolbox de PI. No caso vale a pena verificar como ela é implementada. Para ver o programa fonte basta dar "type checkerboard". Vale a pena comparar para ver as diferenças das nossas versões.

--Lotufo 23:27, 6 March 2007 (BRT)


De
pedro.soares
para
Lotufo

Boa noite Professor Lotufo e colegas,

Mesmo lendo o help da função "meshgrid", também tive a mesma dúvida que a Juliana e Ingrid, sobre como utilizar os parâmetros "ph" e "pw" nesta. Poderia nos ajudar?

Grato,

Pedro Paulo

Resposta
Para usar o meshgrid deve ser necessário achar uma equação matemática que gere o n. de zeros e uns corretamente. Pode não ser simples. Não pensei muito na resposta, mas acredito ser possível. Fica o desafio para a turma.

--Lotufo 23:27, 6 March 2007 (BRT)


De
giuliano.vitor
para
Lotufo e colegas

Boa noite Prof Lotufo e colegas,

Alguém saberia me dizer se é possível transformar uma função desenvolvida no Matlab (m file) em código compilado (pra ser usado no próprio Matlab, mas não de forma interpretada). Será que isso não deixaria uma função desenvolvida com for mais rápida ?

Obrigado,

Resposta
Olá Giuliano, encontrei referência sobre o assunto no site da desenvolvedora do produto. Realmente é possível compilar o código, mas existem algumas restrições que devem ser observadas. Maiores detalhes podem ser encontrados no link abaixo:
http://www.mathworks.com/access/helpdesk_r13/help/toolbox/compiler/compiler.html

--André 01:22, 14 March 2007 (BRDT)


Soluções por alunos (ou equipe)

Dicas
Vejam e estudem as seguintes expressões e funções:
mod((1:20),4)<2
kron([1 0;0 1],[1 1])

Cada aluno ou equipe deve colocar aqui suas soluções:

Soluções Consolidadas

Foram utilizados os seguintes critérios para a seleção das soluções:

  1. Não há loops de iteração nos elementos das matrizes,
  2. Simplicidade,
  3. Utilizam técnicas diferentes das outras soluções selecionadas.

Utilizando KRON

function a = xadrez_1(h, w, ph, pw)
% Cria imagem xadrez onde:
% h: altura da imagem em pixels
% w: largura da imagem em pixels
% ph: altura da casa de xadrez em pixels
% pw: largura da casa de xadrez em pixels

tic;
%Prepara padrao:
taux=clock;
padrao=kron([1,0;0,1],ones(ph,pw));
tempo_padrao=etime(clock,taux)
%cria uma matriz de uns dizendo quantas vezes o padrao precisa ser
%repetido
taux=clock;
base=ones(ceil(h/(2*ph)),ceil(w/(2*pw)));
%realiza multiplicacao KRON:
matriz=kron(base,padrao);
tempo_matriz=etime(clock,taux)
%Retira excessos:
taux=clock;
a=matriz(1:h,1:w);
tempo_corte=etime(clock,taux)
toc

Utilizando MESHGRID

function a = xadrez_2(h,w,ph,pw)
% Cria imagem xadrez onde:
% h: altura da imagem em pixels
% w: largura da imagem em pixels
% ph: altura da casa de xadrez em pixels
% pw: largura da casa de xadrez em pixels

disp(' ');
disp('Solucao 2 - Utilizando a funcao MESHGRID');
disp(' ');

tic;
% Funcao MESHGRID
[x, y] = meshgrid(floor((0:w-1)/pw), floor((0:h-1)/ph));
a = mod((x+y),2);
t2 = toc;

asw2 = sprintf('Tempo de execucao: %i s',t2);
disp(asw2);

Utilizando REPMAT

function a = xadrez_2(h, w, ph, pw)
% Cria imagem xadrez onde:
% h: altura da imagem em pixels
% w: largura da imagem em pixels
% ph: altura da casa de xadrez em pixels
% pw: largura da casa de xadrez em pixels

tic % comeca a contar o tempo

matriz1 = repmat(0, ph, pw);    % celula de zeros
matriz2 = repmat(1, ph, pw);    % celula de ums

celula = [matriz1 matriz2; matriz2 matriz1]; % menor celula xadrez

a = repmat(celula, ceil(h / (2*ph)), ceil(w / (2*pw))) ;

% Se a ja for do tamanho esperado nao e necessario extrair a parte da
% matriz que nos interessa
if mod(h, 2*ph) ~= 0 || mod(w, 2*pw) ~= 0 
   a = a(1:h, 1:w);
end 

toc % para o cronometro

Em Python

Solução 1: Geração da matriz do xadrez com `scan` pixel a pixel

def xadrez1(h,w,ph,pw):
   from Numeric import zeros
   chess=zeros((h,w))
   fill=0
   fillinit=0
   col=0
   row=1
   fill=0
   for i in range(h):
       for j in range(w):
           if col<pw:
                   chess[i,j]=fill
                   col=col+1
           else:
               col=0
               fill=abs(fill-1)
               chess[i,j]=fill
               col=col+1           
       col=0
       if row<ph:
               row=row+1
               fill=fillinit
       else:
           row=0
           fillinit=abs(fillinit-1)
           fill=fillinit
           row=row+1
   return chess

Solução 2: Geração da matriz utilizando funções `resize`

def xadrez2(h,w,ph,pw):

from Numeric import zeros
from Numeric import ones
from Numeric import concatenate
from Numeric import resize
from Numeric import reshape
       # Generate a row starting with zeros of the desired final chess matrix
aux_vector=concatenate((zeros((1,pw)),ones((1,pw))),1)
base_row_starting_zero=resize(aux_vector,(1,w))

# Generate a row starting with ones of the desired final chess matrix

aux_vector=concatenate((ones((1,pw)),zeros((1,pw))),1)
base_row_starting_one=resize(aux_vector,(1,w))
aux_submatrix_starting_zero=resize(base_row_starting_zero,(ph,w))
aux_submatrix_starting_one=resize(base_row_starting_one,(ph,w))
chess=concatenate((aux_submatrix_starting_zero,aux_submatrix_starting_one))
chess=resize((chess),(h,w))
return chess 

Função para cálculo do tempo de execução de cada solução proposta

def xadrezperf(h,w,ph,pw):
from time import time
funlist = (xadrez1,xadrez2)
fundesc = ("Pixel scan: ","Using 'resize':")
i=0
for fun in funlist:
   t1,f,t2 = time(), fun(h,w,ph,pw), time()
   print fun, fundesc[i], t2-t1," seconds"
   i = i+1
Ferramentas pessoais