Students
Register
Advertisement



Implementação da Transformada de Watershed por Imersão
Vilson Vieira



Resumo[]

A segmentação é uma importante ferramenta para as áreas que de alguma forma utilizam da análise de imagens. Pode ser utilizada para demarcar regiões específicas em uma imagem, levando ao reconhecimento destas. Para a implementação desta operação, pode-se recorrer à transformadas da Morfologia Matemática. O objetivo deste trabalho é descrever uma destas, a Transformada de Watershed. Detalhes sobre a transformada em si serão dados, assim como exemplos de sua aplicação. A sua implementação em linguagem de programação Python é então apresentada, tornando claro sua compreensão.

Introdução[]

A segmentação de imagens consiste em isolar do plano de fundo, objetos de uma imagem, tomando como base alguma propriedade, como os níveis de cinza de seus pixels constituintes [1]. Existem diversos tipos de segmentação, como as baseadas em tresholding, em contornos e em regiões [2]. Este trabalho descreve um método de segmentação baseado em regiões, a Transformada de Watershed.

Proveniente da área de Morfologia Matemática, a Transformada de Watershed, ou Transformada de Linhas Divisoras de Água, é um método bastante utilizado para segmentação de imagens [1]. Sua utilização é empregada na indústria para o controle de qualidade e automação industrial; no reconhecimento óptico de caracteres em imagens de textos digitalizados; na biologia para segmentar verminoses em amostras de sangue e de fibras de tecido muscular [3]. Diversas aplicações nestes grupos são descritas nos trabalhos de Roberto Hirata [3] e Serge Beucher [4]. Uma delas, o projeto PROMETHEUS, que visa a segmentação de rodovias, é descrita na seção 4.

A inspiração para a Transformada de Watershed é proveniente da Geografia. Em uma região de relevo acentuado, as linhas divisoras de água são os topos das regiões de maior altitude, onde a água não conseguiria atingir se o planalto fosse inundado. Se uma imagem qualquer em níveis de cinza for imaginada como uma foto de satélite de uma região de relevo, então as regiões inundadas serão os objetos segmentados da imagem, e suas linhas divisoras de água (as watersheds) serão os pixels que delineiam estas regiões.

Organização do trabalho[]

Este trabalho está organizado da seguinte forma: Na seção 3 será apresentada a Transformada de Watershed, seu histórico, definição prática e formal, além de um dos algoritmos que a implementa. A implementação deste algoritmo utilizando a linguagem de programação Python é demonstrada na subseção 3.1, seguido dos resultados obtidos com a aplicação desta implementação, analisados na subseção 3.2 seguinte. Um caso de sucesso do uso da transformada é demonstrado na seção 4, seguindo-se das conclusões resultantes com desenvolvimento do trabalho e das referências utilizadas, respectivamente nas seções 5 e 6.

A Transformada de Watershed[]

Proposta inicialmente por Digabel e Lantuéjoul e melhorada por Beucher e Lantuéjoul [1], a Transformada de Watershed se baseia no fenômeno natural da enchente de relevos topográficos [5]para implementar um dos principais métodos utilizados na segmentação de imagens.

Para se compreender o método, deve-se imaginar a imagem como sendo um relevo topográfico visto de cima, como se uma foto de satélite desta região fosse capturada. A Figura 3.1 apresenta um exemplo de imagem em níveis de cinza e sua analogia com um relevo de montanhas (Figura 3.2).

Watershed-figura9

Figura 3.1: Imagem em níveis de cinza.

Watershed-figura10

Figura 3.2: Relevo topográfico.

As regiões mais escuras da Figura 3.1 representam os vales, e as regiões mais claras, as montanhas. Ao se inundar a região com água, os vales vão se enchendo e transformam-se em bacias. Conforme vão enchendo, bacias maiores vão se formando pelo encontro das águas. Nos topos das montanhas, onde as bacias se dividem, são formadas as linhas divisórias de água, ou watersheds. Ao chegar neste ponto a inundação pára, e as watersheds separam as regiões segmentadas. A Figura 3.3 mostra todos os componentes envolvidos no processo de inundação.

Watershed-figura11

Figura 3.3: Componentes de um relevo topográfico.

Este fenômeno é modelado em um algoritmo. Existem dois tipos de algoritmos para a implementação da Transformada de Watershed, os seqüenciais e os paralelos [1]. Este trabalho utiliza o algoritmo seqüencial recursivo de Vincent e Soille [6]. Outros algoritmos seqüenciais são o de Meyer [7], baseado em funções de distância e as baseadas em operadores IFT (Image Foresting Transform) [8].

O algoritmo de Vincent e Soille pode ser expresso como uma recursão [1]





sendo uma imagem em níveis de cinza e seus mínimo e máximo valores de cinza. O nível de cinza é incrementado de a . representa a união de todas as bacias computadas no nível . representa a união de todos os mínimos regionais na altitude . é o conjunto threshold, ou conjunto de pontos iniciais, definido para um certo nível como [1]



.



Em um determinado nível , o conjunto de pontos iniciais pode ser tanto um novo mínimo quanto uma extensão da bacia hidrográfica em , nesta último caso, é calculado a zona de influência geodézica de com (), o que resulta em na atualização do estado [1].

A imagem rotulada da imagem original é dado pelo complemento de em [1]



Failed to parse (syntax error): {\displaystyle Watershed(f) = D \\ X_{h_{max}}} .



Para facilitar a compreensão é demonstrada em seguida o pseudo-código da implementação deste algoritmo.

Implementação do Algoritmo por Imersão[]

A seguir é apresentado o procedimento principal que implementa uma versão modificada proposta por Roerdink e Meijster [1] do algoritmo de Vincent e Soille para a Transformada de Watershed por imersão. A modificação visa eliminar passos redundantes do algoritmo original (como a checagens de pontos desnecessárias) diminuindo a complexidade do algoritmo de para [9]. O pseudo-código utilizado é baseado na linguagem de programação Python. O código-fonte completo de implementação está disponível no Anexo.

O algoritmo se divide em duas partes. Primeiramente é calculado o histograma e o histograma cumulativo dos níveis de cinza da imagem, criando-se uma representação linear da imagem pela rasterização de seus pixels da esquerda para a direita e de cima para baixo. Com base no histograma, este vetor é ordenado em ordem crescente de seus valores de níveis de cinza. Esta ordenação é útil para a segunda parte do algoritmo, que necessita inundar as regiões nível a nível. Portanto, a segunda parte compreende a inundação nível por nível, rotulando os pontos baseando-se em seus vizinhos e nele próprio. Os comentários no pseudo-código esclarecem outros detalhes importantes para o entendimento do algoritmo.

def wshed(im_in):
    mask = -2     # valor inicial para cada nível de cinza
    wshed = 0     # valor dos pontos que pertencem ao watershed
    init = -1     # valor inicial dos pontos de im_out
    ficticio = -4 # ponto fictício
    curlab = 0    # rótulo corrente
    
    # inicializa a fila FIFO
    fila = []

    # cria o vetor da a imagem de saída (g) e a aux. de distância (dist)
    rotu = vetoriza(zeros(im_in.shape))     
    dist = vetoriza(zeros(im_in.shape)) 

    # inicializa g e dist
    for p in range(len(rotu)): 
        rotu[p] = init
        dist[p] = 0
    
    #
    # PARTE 1: ordenação dos pontos por seus níveis de cinza
    #

    # vetor de pontos ordenado e valores de mínimo e máximo de cinza
    ordenados, hmin, hmax = orde(im_in)
    
    #
    # PARTE 2: alagamento para cada nível h de cinza
    #

    # para cada nível h de cinza...
    for h in range(hmin, hmax+1):
        
        # e para cada ponto com nível de cinza h...
        for p in range(len(ordenados)):
            if ordenados[p] == h:
                # todo ponto inicial com o rótulo igual a mask
                rotu[p] = mask
                # seus vizinhos-8 são analizados
                for q in vizinhos(p, im_in.shape[0], im_in.shape[1]):
                    # se algum vizinho já tiver sido analisado ou for wshed...
                    if (rotu[q] > 0) or (rotu[q] == wshed):
                        # ...propaga a dist. geodésica e inclui o ponto na fila
                        dist[p] = 1
                        fila.append(p)

        curdist = 1
        fila.append(ficticio)

        # propaga a bacia
        while (True):
            p = fila.pop(0)
            if (p == ficticio):
                if (len(fila) == 0):
                    break
                else:
                    fila.append(ficticio)
                    curdist += 1
                    p = fila.pop(0)
            
            # rotula p baseando-se no rótulo dos vizinhos
            for q in vizinhos(p, im_in.shape[0], im_in.shape[1]):
                if (dist[q] < curdist) and (rotu[q] > 0 or rotu[q] == wshed):
                    # vizinho q pertence a uma bacia existente ou é watershed
                    if rotu[q] > 0:
                        if (rotu[p] == mask) or (rotu[p] == wshed):
                            rotu[p] = rotu[q]
                        elif rotu[p] != rotu[q]:
                            rotu[p] = wshed
                    elif rotu[p] == mask:
                        rotu[p] = wshed
                # q é um ponto de um plateau
                elif (rotu[q] == mask) and (dist[q] == 0):
                    dist[q] = curdist + 1
                    fila.append(q)

        # detecta e processa os novos mínimos no nível h
        for p in range(len(ordenados)):
            if ordenados[p] == h:
                # reseta a distância para zero
                dist[p] = 0
                # p está dentro de um novo mínimo
                if (rotu[p] == mask):
                    curlab += 1
                    # cria um novo rótulo
                    fila.append(p)
                    rotu[p] = curlab
                    while (len(fila) != 0):
                        q = fila.pop(0)
                        # inspeciona os vizinhos de q
                        for r in vizinhos(q, im_in.shape[0], im_in.shape[1]):
                            if (rotu[r] == mask):
                                fila.append(r)
                                rotu[r] = curlab

    return devetoriza(rotu, im_in.shape[0], im_in.shape[1])

Resultados Obtidos[]

Pela aplicação do algoritmo para a Transformada de Watershed pode-ser obter a segmentação das regiões de uma imagem, como no exemplo da imagem na Figura 3.4 que apresenta as linhas divisoras de água sendo exibidas na Figura 3.5.

Watershed-figura12

Figura 3.4: Imagem original.

Watershed-figura13

Figura 3.5: Imagem com watersheds.

Espera-se em breve publicar os resultados obtidos com a própria implementação desenvolvida neste trabalho.

Aplicações[]

Um caso de sucesso da aplicação da Transformada de Watershed para a segmentação de imagens é o projeto PROMETHEUS. Seu objetivo é o desenvolvimento de um protótipo de veículo que utiliza câmeras e um dispositivo de telemetria para se localizar em uma rodovia. A Figura 4.1 exibe o protótipo do veículo PROLAB2.

Watershed-figura1

Figura 4.1: Protótipo de veículo PROLAB2 para projeto PROMETHEUS.

As imagens capturadas pelas câmeras do protótipo (Figura 4.2) são pré-processadas com o objetivo de conectar as faixas da pista e eliminar sombras, como mostra a Figura 4.3.

Watershed-figura2

Figura 4.2: Imagem original capturada.

Watershed-figura3

Figura 4.3: Imagem original pré-processada.

Logo após, a Transformada de Watershed é aplicada às imagens, que segmenta as faixas indicadoras da pista, definindo assim seu modelo geométrico, como mostrado nas Figuras 4.4 e 4.5.

Watershed-figura4

Figura 4.4: Segmentação por Transformada de Watershed

Watershed-figura5

Figura 4.5: Faixas da pista segmentadas

O processamento continua, utilizando vários critérios de contraste e geometria para selecionar os obstáculos (Figura 4.6). Os obstáculos não pertencentes à pista identificada pela Transformada de Watershed são desprezados, como mostra a Figura 4.7.

Watershed-figura6

Figura 4.6: Detecção de todos os obstáculos

Watershed-figura7

Figura 4.7: Somente os obstáculos na pista são selecionados

Por fim, através de toda esta seqüência de processamento, segmentação e análise, a imagem final (Figura 4.8) exibe ao motorista do veículo informações importantes, como o número e a geometria das faixas da pista, a presença e posição dos obstáculos e as distâncias de segurança até estes.

Watershed-figura8

Figura 4.8: Imagem final com todas as informações

Todas estas operações são executadas em tempo real, graças a um processador paralelo de Morfologia Matemática. Informações sobre este processador e versões animadas da captura e processamento das imagens pelo protótipo estão disponíveis nesta página Web.

Conclusões e Perspectivas[]

A segmentação é uma importante ferramenta no processamento de imagens, sendo a Transformada de Watershed uma de suas mais poderosas implementações. A utilização desta transformada é bem comum, estando presente em aplicações acadêmicas e industriais, que exigem resultanos de grande precisão.

A análise de uma aplicação real como a do projeto PROMETHEUS permitiu confirmar a eficiência da transformada aplicada em problemas com complexidade elevada.

A implementação foi facilitada pela linguagem Python e pela biblioteca IM, que permitiu as rotinas de leitura e escrita de imagens em formato PGM. Embora não se obteve o perfeito funcionamento da rotina principal da implementação, espera-se corrigí-la a ponto de se chegar aos resultados que eram então esperados. Tão logo estes forem alcançados, as modificações serão aqui publicadas.

Referências[]

  1. 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 ROERDINK, Jos B. T. M. e MEIJSTER, Arnold. The Watershed Transform: Definitions, Algorithms and Parallelization Strategies. Institute for Mathematics and Computer Science, University of Groningen, Groningen, The Netherlands, IWI 99--9-06, 1999
  2. BARBOZA, Cleber M. e FILHO, Fernando Mario de O. e SOARES, João Vitor B. Representação e Descrição de Imagens. USP. São Paulo, Julho de 2002
  3. 3.0 3.1 HIRATA, Roberto. Segmentação de Imagens por Morfologia Matemática. USP Thesis. São Paulo, 1997.
  4. BEUCHER, Serge. The Watershed Transformation Page. Acessado em 02 de Julho de 2007, às 23:30
  5. Russ, J. C. The Image Processing Handbook. CRC Press, Boca Raton, 1998.
  6. Vincent, L. e Soille, P. Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(6):583–598, 1991.
  7. Meyer, F. Topographic distance and watershed lines. Signal Processing, 38:113–125, 1994.
  8. Falcão, A. X., Stolfi, J., and Lotufo, R. A. The image foresting transform: Theory, algorithms, and applications. IEEE Trans. on Pattern Analysis and Machine Intelligence, 26(1):19–29, 2004.
  9. PECCINI, Grasiela e D'ORNELLAS, Marcos C. Segmentação de imagens por Watershds: Uma Implementação Utilizando a Linguagem Java

Anexo[]

É listado a seguir o código-fonte completo para a implementação em linguagem de programação Python para a Transformada de Watershed por imersão. A biblioteca IM e Numpy são necessárias para a execução.

from im import *
from Numeric import zeros

# Calcula a transformada de Watershed
# -----------------------------------
# Descrição: Dada uma imagem, calcula sua imagem rotulada, ou seja
#            desenha as linhas divisoras de água
#
# Entradas: im_in   matriz da imagem a ser segmentada
#
# Saídas:   im_out  matriz da imagem rotulada
def wshed(im_in):
    mask = -2     # valor inicial para cada nível de cinza
    wshed = 0     # valor dos pontos que pertencem ao watershed
    init = -1     # valor inicial dos pontos de im_out
    ficticio = -4 # ponto fictício
    curlab = 0    # rótulo corrente
    
    # inicializa a fila FIFO
    fila = []

    # cria o vetor da a imagem de saída (g) e a aux. de distância (dist)
    rotu = vetoriza(zeros(im_in.shape))     
    dist = vetoriza(zeros(im_in.shape)) 

    # inicializa g e dist
    for p in range(len(rotu)): 
        rotu[p] = init
        dist[p] = 0
    
    #
    # PARTE 1: ordenação dos pontos por seus níveis de cinza
    #

    # vetor de pontos ordenado e valores de mínimo e máximo de cinza
    ordenados, hmin, hmax = orde(im_in)
    
    #
    # PARTE 2: alagamento para cada nível h de cinza
    #

    # para cada nível h de cinza...
    for h in range(hmin, hmax+1):
        
        # e para cada ponto com nível de cinza h...
        for p in range(len(ordenados)):
            if ordenados[p] == h:
                # todo ponto inicial com o rótulo igual a mask
                rotu[p] = mask
                # seus vizinhos-8 são analizados
                for q in vizinhos(p, im_in.shape[0], im_in.shape[1]):
                    # se algum vizinho já tiver sido analisado ou for wshed...
                    if (rotu[q] > 0) or (rotu[q] == wshed):
                        # ...propaga a dist. geodésica e inclui o ponto na fila
                        dist[p] = 1
                        fila.append(p)

        curdist = 1
        fila.append(ficticio)

        # propaga a bacia
        while (True):
            p = fila.pop(0)
            if (p == ficticio):
                if (len(fila) == 0):
                    break
                else:
                    fila.append(ficticio)
                    curdist += 1
                    p = fila.pop(0)
            
            # rotula p baseando-se no rótulo dos vizinhos
            for q in vizinhos(p, im_in.shape[0], im_in.shape[1]):
                if (dist[q] < curdist) and (rotu[q] > 0 or rotu[q] == wshed):
                    # vizinho q pertence a uma bacia existente ou é watershed
                    if rotu[q] > 0:
                        if (rotu[p] == mask) or (rotu[p] == wshed):
                            rotu[p] = rotu[q]
                        elif rotu[p] != rotu[q]:
                            rotu[p] = wshed
                    elif rotu[p] == mask:
                        rotu[p] = wshed
                # q é um ponto de um plateau
                elif (rotu[q] == mask) and (dist[q] == 0):
                    dist[q] = curdist + 1
                    fila.append(q)

        # detecta e processa os novos mínimos no nível h
        for p in range(len(ordenados)):
            if ordenados[p] == h:
                # reseta a distância para zero
                dist[p] = 0
                # p está dentro de um novo mínimo
                if (rotu[p] == mask):
                    curlab += 1
                    # cria um novo rótulo
                    fila.append(p)
                    rotu[p] = curlab
                    while (len(fila) != 0):
                        q = fila.pop(0)
                        # inspeciona os vizinhos de q
                        for r in vizinhos(q, im_in.shape[0], im_in.shape[1]):
                            if (rotu[r] == mask):
                                fila.append(r)
                                rotu[r] = curlab

    return devetoriza(rotu, im_in.shape[0], im_in.shape[1])

# Retorna a lista de vizinhos-8 do ponto p
# ----------------------------------------
# Descrição: Dado um ponto p, retorna uma lista com seus vizinhos-8
#
# Entradas: p       coordenada linear do ponto
#           m       quantidade de linhas da imagem
#           n       quantidade de colunas da imagem
#
# Saídas:   lista de vizinhos-8 do ponto p
def vizinhos(p, m, n):
    if (p == 0):
        return [p+1, p+n, p+n+1]
            
    if (p == (n-1)):
        return [p-1, p+n-1, p+n]

    if (p == (n*(m-1))):
        return [p-n, p-n+1, p+1]

    if (p == ((n*m)-1)):
        return [p-n-1, p-n, p-1]

    for i in range(1, n-1):
        if (p == i):
            return [p-1, p+1, p+n-1, p+n, p+n+1]

    for i in range((n*(m-1))+1, (n*m)-1):
        if (p == i):
            return [p-n-1, p-n, p-n+1, p-1, p+1]

    for i in range(n, n * (m-1), n):
        if (p == i):
            return [p-n, p-n+1, p+1, p+n, p+n+1]
        if (p == i+(n-1)):
            return [p-n-1, p-n, p-1, p+n-1, p+n]

    return [p-n-1, p-n, p-n+1, p-1, p+1, p+n-1, p+n, p+n+1]

# Calcula o histograma de uma imagem
# ----------------------------------
# Entradas: matriz da imagem
#
# Saídas: histograma da imagem; valor de mínimo e máximo de cinza
def hist(im_in):
    # inicializa o vetor de histograma
    histograma = zeros(256)

    # inicializa os valores de mínimo e máximo do histograma
    min = max = im_in[0,0];

    # cria o histograma e acha os valores de mínimo e máximo
    for i in range(im_in.shape[0]):
        for j in range(im_in.shape[1]):
            aux = im_in[i,j]
            histograma[aux] += 1
            if (aux < min): min = aux
            if (aux > max): max = aux

    return histograma, min, max

# Calcula o vetor de endereços da imagem utilizando seu histograma cumulativo
# ----------------------------------
# Entradas: matriz da imagem
#
# Saídas: vetor de endereços, valores mínimo e máximo de cinza
def cumul(im_in):
    # inicializa o vetor do histograma cumulativo
    cumulativo = zeros(256);
    ims = zeros(im_in.shape[0] * im_in.shape[1]);
    histograma, min, max = hist(im_in)

    for i in range(min+1, max+1):
        cumulativo[i] = cumulativo[i-1] + histograma[i - 1]
    
    v = vetoriza(im_in)
    
    # calcula o histograma cumulativo e o vetor de endereços
    for i in range(v.shape[0]):
        ims[cumulativo[v[i]]] = i
        cumulativo[v[i]] += 1

    return ims, min, max

# Ordena o vetor da imagem por seus níveis de cinza, em ordem crescente
# ---------------------------------------------------------------------
# Entradas: matriz da imagem
#
# Saídas: vetor ordenado, valores mínimo e máximo de cinza
def ordena(im_in):
    enderecos, min, max = cumul(im_in)
    original = vetoriza(im_in)
    saida = vetoriza(zeros(im_in.shape))

    for i in range(len(saida)):
        saida[i] = original[enderecos[i]]

    return saida, min, max

# Retorna a representação linear da rasterização (left-right, up-down) da matriz   
# ------------------------------------------------------------------------------
# Entradas: matriz da imagem
#
# Saídas: representação linear da matriz
def vetoriza(im_in):
    im_vet = zeros(im_in.shape[0]*im_in.shape[1])
    count = 0

    for i in range(im_in.shape[0]):
        for j in range(im_in.shape[1]):
            im_vet[count] = im_in[i,j]
            count += 1

    return im_vet

# Operação inversa de vetoriza()
# ------------------------------
# Entradas: representação linear; dimensão m e n da matriz
#
# Saídas: representação matricial
def devetoriza(vet, m, n):
    im_out = zeros((m,n))
    cont = 0

    for i in range(m):
        for j in range(n):
            im_out[i,j] = vet[cont]
            cont += 1

    return im_out

Advertisement