# activity_gbleite_6_twsm - Tie-zone Watershed from labeled markers

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

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
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()
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
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]]
[[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]]
[[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) )
10     print 'Bc=\n',Bc * 1
11     k1 = tester.get_output(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]]
```

## 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%