Atividades da semana 6 | Guilherme (gbleite) | Atividades

activity_gbleite_6_3 - Rascunho para implementar tie-zone watershed por marcadores

Nesta atividade você deve programar utilizando varredura sequencial de pixels. Veja a página construída em aula e aprimorada:

Lá estão descritas as duas principais técnicas sugeridas para a implementação:

  • fila hierárquica
  • endereçamento do pixel e seus vizinhos

Leia a teoria associada ao watershed por tie-zone e veja o algoritmo

  • Lotufo, Falcão - The ordered queue and the optimality of the watershed approaches. Citeseer
  • Audigier, Lotufo - The tie-zone watershed: Definition, algorithm and applications. Citeseer

A diferença entre watershed clássico sem marcadores do watershed com marcadores é que no watershed clássimo, os marcadores iniciais são dados pelos mínimos regionais da imagem. Assim, o watershed por marcadores é mais simples, pois os marcadores não precisam ser calculados, pois eles são fornecidos diretamente.

Veja as implementações já existentes

Use o espaço abaixo para fazer a sua implementação:

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

Imagem

Imagem tratada

Marcadores

Imagem com Marcadores

Elemento Estruturante

Exemplo numérico para testar o tie-zone watershed por marcadores

[–] Comments
Roberto Lotufo at 2015-05-26 23:35h
 0
Oi Guilherme, só vi sua mensagem agora. É verdade, mas não é difícil criar a função de consulta.

Guilherme Leite at 2015-05-24 14:42h
 0
Olá Lotufo, Na implementação do artigo, o algoritmo utiliza de mecanismos de consulta e remoção da fila "THE TIE-ZONE WATERSHED: DEFINITION, ALGORITHM AND APPLICATIONS". Na fila hierárquica disponibilizada, não tem esse mecanismo. É isso mesmo? Obrigado