Resultados | Exercícios 6 | Guilherme Leite (gbleite)

activity_gbleite_6_twsm - Tie-zone Watershed from labeled markers

1. Definição da função a ser feita e testada

Implementar a transformada tie-zone watershed por marcadores rotulados similar à ia870:iatz, porém com a opção onde os marcadores já entram rotulados e o resultado é uma imagem rotulada e não as linhas do watershed.

O objetivo desta implementação é dar uma experiência sobre a implementação do watershed. A parte fundamental é a fila hierárquica e o desempenho do algoritmo é diretamente relacionada à eficiência desta fila hierárquica.

Sinta-se à vontade para fazer as otimizações que achar conveniente.

  1 import numpy as np
  2 import Queue
  3 import ia636 as ia
  4 import ia870 as MT
  5 
  6 class wsHeapQueue():
  7     """ Priority queue class for abstracting list methods with FIFO policy """
  8 
  9     def __init__(self):
 10         self.queue = dict()
 11 
 12     def push(self, a, c):
 13         """ Pushes an element to the queue """
 14         if self.queue.has_key(c):
 15             self.queue[c].append(a)
 16         else:
 17             self.queue[c] = [a]
 18 
 19     def remove(self, a, c):
 20         """ remove an element to the queue """
 21         if self.queue.has_key(c):
 22             self.queue[c].remove(a)
 23 
 24     def pop(self):
 25         """ Pops the first element of the queue """
 26         key = min(self.queue.keys())
 27         element = self.queue[key].pop(0)
 28         if len(self.queue[key]) == 0:
 29             self.queue.pop(key)
 30         return element
 31 
 32     def empty(self):
 33         """ Returns whether the queue is empty or not """
 34         return len(self.queue) == 0
 35 
 36 def se2off(Bc):
 37     '''Converts structuring element to list of neighbor offsets in graph image'''
 38     h,w = Bc.shape
 39     hc,wc = h/2,w/2
 40     B = Bc.copy()
 41     B[hc,wc] = 0  # remove origin
 42     off = np.transpose(B.nonzero()) - np.array([hc,wc])
 43     return off  # 2 columns x n. of neighbors rows
 44 
 45 def N(fs,off):
 46     '''Precompute array of neighbors. Optimized by broadcast.
 47 
 48     fs - image shape
 49     off - offset matrix, 2 columns (dh,dw) x n. of neighbors
 50     '''
 51     H,W = fs
 52     n = H*W
 53     hi = np.arange(H).reshape(-1,1)
 54     wi = np.arange(W).reshape(1,-1)
 55     hoff = off[:,0]
 56     woff = off[:,1]
 57     h = hi + hoff.reshape(-1,1,1)
 58     w = wi + woff.reshape(-1,1,1)
 59     h[(h<0) | (h>=H)] = n
 60     w[(w<0) | (w>=W)] = n
 61     Nid = np.clip(h * W + w,0,n)
 62     return Nid.reshape(len(off),-1).transpose()
 63 
 64 def twsm(f,m,Bc):
 65 
 66  ####implementacao
 67  #preparando valores da entrada. Transformando em ravel e salvando o shape
 68  fShape = f.shape
 69  fRavel = f.ravel()
 70  fSize = f.size
 71  m = m.ravel()
 72 
 73  ##Inicializando os valores
 74 
 75  #estrutura para salvar se o pixel já foi processado ou não
 76  #false - Não processado
 77  #true - Processado
 78  done = np.empty(fSize)
 79  done[:] = False
 80 
 81  #auxiliares do algoritmo de TieZone
 82  C1 = np.empty(fSize)
 83  C1[:] = np.inf
 84  C2 = np.zeros(fSize)
 85  L = np.empty(fSize)
 86  L[:] = fSize
 87 
 88  #calculando a lista de vizinhos
 89  nList = N(fShape,se2off(Bc))
 90 
 91  #inicializando a lista hierarquica
 92  pList = wsHeapQueue()
 93  #adicionando os nós dos marcadores na lista
 94  nz = np.nonzero(m)[0]
 95  for i in nz:
 96    pList.push(i,fRavel[i])
 97    C1[i] = fRavel[i]
 98    L[i] = m[i]
 99 
100  ##processamento
101  #enquanto lista nao vazia
102  while not pList.empty():
103    #pega o pixel de maior prioridade da lista hierárquica e marca o pixel como processado
104    p = pList.pop()
105    done[p] = True
106 
107    #faz as verificaçoes com a vizinhanca
108    for q in nList[p]:
109      #nos casos da borda, os elementos fora do dominio tem valor fSize
110      if q<fSize:
111        #se o pixel ja foi processado, checa o proximo elemento
112        if done[q]:
113          continue
114 
115        ##algoritmo tie zone
116        c = max(C1[p], fRavel[q])
117 
118        if c < C1[q] :
119          #if q, C1[q] in Q dequeue
120          pList.remove(q, C1[q])
121          C1[q] = c
122          L[q] = L[p]
123          pList.push(q,C1[q])
124          if c == C1[p] :
125            C2[q] = C2[p]+1
126        elif c == C1[q] and L[q] != L[p] :
127          if c == C1[p] :
128            if C2[q] == C2[p]+1 :
129              L[q] = 0
130          else :
131            L[q] = 0
132 
133  result = L.reshape(fShape)
134  return result.astype(int)

2. Testando as funções

1 from result_6_twsm import tester
2 import activity_gbleite_6_twsm as my

Testes numéricos, 1 casos:

 1 for i in range(1):
 2 
 3     f,m,Bc = tester.get_input(i)
 4     k1 = tester.get_output(i)
 5 
 6     print
 7     print 'Caso ', i
 8     print
 9     print 'f=\n', f * 1
10     print 'm=\n', m
11     print 'Bc=\n', Bc * 1
12     print 'Resultado esperado =\n', k1
13     g1 = my.twsm(f,m,Bc)
14     #g2 = my.twsm_2(f,m,Bc)
15     print 'Meu resultado =\n', g1
16     #print 'Meu resultado =\n', g2
Caso  0

f=
[[10 10 10 10 10 10 10]
 [10  9  6 18  6  5 10]
 [10  9  6 18  6  8 10]
 [10  9  9 15  9  9 10]
 [10  9  9 15 12 10 10]
 [10 10 10  8 10 10 10]]
m=
[[0 0 0 0 0 0 0]
 [0 0 1 0 0 2 0]
 [0 0 1 0 0 0 0]
 [0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0]
 [0 0 0 3 0 0 0]]
Bc=
[[0 1 0]
 [1 0 1]
 [0 1 0]]
Resultado esperado =
[[1 1 1 0 2 2 2]
 [1 1 1 0 2 2 2]
 [1 1 1 0 2 2 2]
 [1 1 1 0 2 2 2]
 [1 1 1 0 0 2 2]
 [1 1 0 3 3 0 0]]
Meu resultado =
[[1 1 1 0 2 2 2]
 [1 1 1 0 2 2 2]
 [1 1 1 0 2 2 2]
 [1 1 1 0 2 2 2]
 [1 1 1 0 0 2 2]
 [1 1 0 3 3 0 0]]

Testes com imagens, 1 caso:

 1 import numpy as np
 2 import ia636,ia870
 3 for i in range(1,2):
 4     print
 5     print 'Caso', i
 6     print
 7     f,m,Bc = tester.get_input(i)
 8     adshow(f, 'f.shape=%s caso %d' % (f.shape, i) )
 9     adshow(ia870.iaglblshow(m), 'marcador rotulado' )
10     print 'Bc=\n',Bc * 1
11     k1 = tester.get_output(i)
12     adshow(ia870.iaglblshow(k1), 'esperado, k1.shape=%s caso %d' % (k1.shape,i,) )
13     kmy1 = my.twsm(f,m,Bc)
14     adshow(ia870.iaglblshow(kmy1), 'meu, kmy1.shape=%s caso %d' % (kmy1.shape,i,) )
15     #kmy2 = my.twsm_2(f,m,Bc)
16     #adshow(ia870.iaglblshow(kmy2), 'meu, kmy2.shape=%s caso %d' % (kmy2.shape,i,) )
Caso 1

Bc=
[[1 1 1]
 [1 0 1]
 [1 1 1]]

f.shape=(128, 128) caso 1

marcador rotulado

esperado, k1.shape=(128, 128) caso 1

meu, kmy1.shape=(128, 128) caso 1

3. Colocando a função no sistema de testes do Adessowiki

Uma vez feita a função que você considera que esta funcionando, este trecho abaixo irá registrá-lo no teste automático, aparecendo na página resultados.

1 # Na linha abaixo, adiciona-se a função a ser testado. Caso queira registrar mais de uma
2 # função, é só adicionar mais uma linha com o run_test:
3 tester.run_test(my.twsm,'gbleite')
4 tester.show_results_table()
Tabela de resultados consolidados de 0 funções distribuídas em 0 páginas distintas.
Ranking do autor Ranking da função Autor Função num 1 (tempo em ms) num 1 (pontuação) img 1 (tempo em ms) img 1 (pontuação) Tempo total (ms) Pontuação total
1 1 gbleite twsm() 2.304 100% 709.920 100% 712.223 100%
[–] Comments
Roberto Lotufo at 2015-05-26 21:56h
 0
Olá Guilherme, você fez conforme minha recomendação. Muito bem. Se quiser otimizar um pouco, procure tornar mais eficiente a inicialização dos marcadores, laço for i in nz.