Algoritmo de rotulação por flood-fill com pilha — painel interativo com HTML e SVG
Passo a passo
Cards
Linha do tempo
Código Python
Fluxograma
Flood-fill com pilha
Rotulagem de componentes conexas
1
Criar imagem de saída g, inicializada com
zeros, mesma dimensão de f.2
Inicializar contador de rótulos (cor)
cor ← 1.3
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).4
Inserir a semente encontrada na pilha
pilha ← [[x,y]].5
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.6
Pilha vazia ⟹ Toda a componente conexa atual foi explorada e rotulada com sucesso.
7
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.01
Inicialização
Criar matriz de rótulos
g preenchida com zeros (fundo). Definir rótulo inicial cor ← 1.02
Varredura Raster
Percorrer a matriz bidimensional linha por linha, localizando pixels pertencentes ao objeto que ainda não possuem rótulo.
03
Semente inicial
Ao achar um pixel válido, inicializar a estrutura LIFO de busca:
pilha = [[x, y]].04
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.
05
Próxima Componente
Pilha esvaziada ⟹ Incrementar indexador
cor ← cor + 1 para diferenciar o próximo objeto isolado.01
Alocação Espacial
g ← zeros_like(f) e definição do primeiro identificador: cor ← 1.02
Varredura Bidimensional
Laços encadeados varrendo as dimensões
h e w da imagem.03
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.06
Fechamento do Objeto
Pilha vazia determina o fim do isolamento daquela componente.
07
Atualização do Rótulo
Incremento linear:
cor ← cor + 1. A varredura raster continua do ponto onde parou.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
1
g = np.zeros(f.shape, dtype=int) — Inicializa a matriz de saída com zeros. Zeros representam o fundo invariável.2
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.3
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.4
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. Description: Figure 4.15: Flood-fill labeling algorithm with stack.