Algoritmo de etiquetado por flood-fill con pila.

Passo a passo

Cards

Linha do tempo

Código Python

Fluxograma

Flood-fill com pilha

Rotulagem de componentes conexas

Criar imagem de saída g, inicializada com zeros, mesma dimensão de f.

Inicializar contador de rótulos (cor) cor ← 1.

Percorrer f em ordem raster (coordenadas x e y) até encontrar uma semente: pixel ativo (f[x,y] ≠ 0) ainda não rotulado (g[x,y] = 0).

Inserir a semente encontrada na pilha pilha ← [[x,y]].

Enquanto a pilha contiver coordenadas (while pilha):

Desempilhar pixel atual: i, j ← pilha.pop() e atribuir o rótulo: g[i,j] ← cor.

Buscar vizinhos usando o iterador mm._viz(f,b,i,j). Se o vizinho for ativo no elemento estruturante (bv ≠ 0), ativo na imagem (f[vy,vx] ≠ 0) e não rotulado (g[vy,vx] = 0), empilhá-lo.

Pilha vazia ⟹ Toda a componente conexa atual foi explorada e rotulada com sucesso.

Incrementar o rótulo para a próxima componente: cor ← cor + 1 e continuar a varredura raster.

A conectividade (4 ou 8 vizinhos) é definida unicamente pela matriz morfológica b passada como parâmetro, alterando os pixels retornados em mm._viz.

Inicialização

Criar matriz de rótulos g preenchida com zeros (fundo). Definir rótulo inicial cor ← 1.

Varredura Raster

Percorrer a matriz bidimensional linha por linha, localizando pixels pertencentes ao objeto que ainda não possuem rótulo.

Semente inicial

Ao achar um pixel válido, inicializar a estrutura LIFO de busca: pilha = [[x, y]].

Expansão por Flood-Fill

Enquanto houver elementos na pilha:

Extrair (i, j) via pop() e marcar g[i, j] = cor.

Inspecionar vizinhança geométrica e adicionar novos candidatos à pilha.

Próxima Componente

Pilha esvaziada ⟹ Incrementar indexador cor ← cor + 1 para diferenciar o próximo objeto isolado.

Alocação Espacial

g ← zeros_like(f) e definição do primeiro identificador: cor ← 1.

Varredura Bidimensional

Laços encadeados varrendo as dimensões h e w da imagem.

Descoberta de Objeto

Filtro condicional localiza pixel ativo não indexado e cria a pilha semente.

04–05

Preenchimento por Região (Flood-fill)

while pilha

Remover último da pilha (i,j) e aplicar rótulo atual.

Empilhar vizinhos conectados que atendam aos critérios morfológicos de b.

Fechamento do Objeto

Pilha vazia determina o fim do isolamento daquela componente.

Atualização do Rótulo

Incremento linear: cor ← cor + 1. A varredura raster continua do ponto onde parou.

label0.py flood-fill com pilha

def label0(f, b=np.ones((3,3),dtype='uint8')):
    """Rotulagem por flood-fill com pilha."""
    h, w = f.shape
    g = np.zeros(f.shape, dtype=int)
    cor = 1
    for x in range(h):
        for y in range(w):
            if f[x,y] and not g[x,y]:
                pilha = [[x,y]]
                while pilha:
                    i,j = pilha.pop(); g[i,j] = cor
                    for vy,vx,bv in mm._viz(f,b,i,j):
                        if bv and f[vy,vx] and not g[vy,vx]:
                            pilha.append([vy,vx])
                cor += 1
    return g

g = np.zeros(f.shape, dtype=int) — Inicializa a matriz de saída com zeros. Zeros representam o fundo invariável.

mm._viz(f, b, i, j) — O iterador morfológico avalia a conectividade. Passando B_cruz a busca expande em 4-vizinhança; passando quadrado (ones) expande em 8-vizinhança.

pilha.pop() — Remove o último par de coordenadas inserido, caracterizando um comportamento LIFO de busca em profundidade (DFS) para varrer o objeto de forma contígua.

cor += 1 — O incremento ocorre estritamente fora do laço while, garantindo que o mesmo número marque toda a extensão da componente concluída antes de passar para a próxima semente raster.

Descripción: Figura 4.15: Algoritmo de etiquetado por flood-fill con pila.

Algoritmo de rotulação por flood-fill com pilha — painel interativo com HTML e SVG