aula11 - Transformada Watershed

Funções para auxiliar a implementação do watershed por marcadores e zona de empate.

Infelizmente, os algoritmos eficientes do watershed são todos sequenciais e que exigem a varredura aleatória dos pixels dependendo da relação de vizinhança e dos valores da imagem do gradiente. Assim, neste exercícios, iremos fazer programa no Python/Numpy utilizando varredura de pixels baseado numa janela de vizinho de pixels.

Existem duas dificuldades principais na implementação dos algoritmos do watershed:

  • implementação de fila hierárquica com política FIFO
  • indexação dos vizinhos de um pixel

Em relação à fila hierárquica, uma implementação é utilizando dicionários dos Python onde cada nível de cinza (valor do pixel) é um índice do dicionário e para cada índice, cria-se uma lista com inserção por append (final da lista) e retirada pelo ínicio utilizando-se o pop. Se alguém tiver alguma outra implementação mais eficiente, seria interessante compararmos com esta:

Fila hierárquica FIFO: implementação em Python usando dicionários

 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 pop(self):
17         """ Pops the first element of the queue """
18         key = min(self.queue.keys())
19         element = self.queue[key].pop(0)
20         if len(self.queue[key]) == 0:
21             self.queue.pop(key)
22         return element
23 
24     def empty(self):
25         """ Returns whether the queue is empty or not """
26         return len(self.queue) == 0

Indexação dos pixels e seus vizinhos

A forma de indexação dos pixels de uma imagem bidimensional é usualmente feita com dois índices, [r,c] linha,coluna. Entretanto, a indexação da imagem linearizada pode ser conveniente pela fato do índice poder ser representado por um único índice. A passagem de um formato para outro é simples e eficiente no Numpy utilizando o ravel e o reshape.

A relação dos vizinhos será simplificada pelo uso das funções abaixo: se2off e Nlut relativo a Neighbors Look-up Table. Ela é construída de modo que podemos chamá-la da forma:

N = Nlut(f.shape,se2off(B))

onde B é uma imagem binária com origem no centro da imagem e onde os pixels True indicam os vizinhos do pixel central.

Quando N é construído como acima, N(p) retorna um array de índices dos vizinhos de p. Caso o vizinho de p esteja fora da imagem, seu valor é f.size, isto é um valor fora de 0 a f.size-1. Desta forma para visitarmos todos os pixels vizinhos de p, fazemos:

for i in N(p):
    if i < f.size:
        print 'N(%d)=%d' % (p,i)

As implementações de se2off e Nlut estão a seguir:

 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()

Exemplo de uso da fila hierárquica

 1 import numpy as np
 2 import aula11_ws as ws
 3 
 4 HQ = ws.wsHeapQueue()
 5 pi = (np.random.rand(10) * 20).astype(np.int)
 6 values = (np.random.rand(10) * 5).astype(np.int)
 7 print 'pares:',zip(pi,values)
 8 for p,v in zip(pi,values):
 9     HQ.push(p,v)
10 print 'Situação da fila hierárquica:\n',HQ.queue
11 print 'Retirando na ordem'
12 while not HQ.empty():
13     p = HQ.pop()
14     print 'p:',p
pares: [(19, 2), (11, 2), (15, 1), (15, 4), (17, 2), (5, 0), (14, 1), (12, 2), (15, 4), (13, 1)]
Situação da fila hierárquica:
{0: [5], 1: [15, 14, 13], 2: [19, 11, 17, 12], 4: [15, 15]}
Retirando na ordem
p: 5
p: 15
p: 14
p: 13
p: 19
p: 11
p: 17
p: 12
p: 15
p: 15

Referências

  • 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