Transformada de Distância
por Morfologia Matemática
Francisco de Assis Zampirolli
Orientador: Roberto de Alencar Lotufo
DCA - FEEC – UNICAMP
1
Conteúdo
Introdução
Erosão & Dilatação
Padrões Erosão
TD por Erosão
Conclusões
2
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Conteúdo
3
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Transformada de Distância (TD)
Distância mínima dos pixels do objeto ao fundo
TD
00kkkkkkkk00
001234432100
0
k
TD
4
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Métricas para a TD
Chanfrada
City-Block
ou 4 conexo
Chessboard
ou 8 conexo
Euclidiana
Outras:
3:4, 5:7:11, ...
5
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Principais contribuições
• Novo enfoque de padrões de algoritmos da erosão
morfológica:
– Paralelo
– Seqüencial
– Propagação
Estudo da equivalência entre estes padrões
• Classificação de algoritmos clássicos da TD:
– Paralelo e Seqüencial - Rosenfeld e Pfaltz
– Propagação - Vincent
• Construção de novos algoritmos da TDE:
– Direcional
– Multidimensional
6
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Conteúdo
7
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Erosão Binária
 Subtração de Minkowski
X  B = {y  E : By  X}
y
X
XB E
8
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Dilatação Binária
 Soma de Minkowski
X  B = {Xy : y  B}
B
y
XB
X
Xy
E
9
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Definições
Infinito:
X  B = {Xy : y  B}
Limitado:
X  B = {Xy
 E: y  B}
B
y
Xy
Xy  E
y
X
X
E
E
Infinito
Limitado
10
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Erosão em Níveis de Cinza
f  b  b(f) :
 x  E,
b(f)(x) =
onde
E
f  [0,k] , b  
B
e

 y  Bx  E
{ f(y)
b(y-x) }
Bx
11
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Dilatação em Níveis de Cinza
f  b  b(f) :
 x  E,
b(f)(x) =
onde
E
f  [0,k] , b  
B
e

{ f(y) + b(x-y) }
 y  Bx  E
Bx
12
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Decomposições
Se
então
Caso particular 1:
Caso particular 2:
bG = b 1  . . .  bk
bG(f) = bk(. . .(b1(f)). . .)
bG = kb
bG = b
k=10
b
-1
-1 0 -1
-1
13
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Conteúdo
14
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Motivação para o estudo da erosão
• Erosões e Dilatações podem ser caracterizadas por
funções estruturantes [Serra’88]
• Qualquer operador entre reticulados pode ser decomposto por
operadores elementares: erosões, dilatações, anti-erosões e
anti-dilatações [Banon&Barrera’92]
• Funções Estruturantes podem ser decompostas para melhorar
a eficiência dos algoritmos
• Será classificado a erosão em níveis de cinza com relação à
ordem de varredura dos pixels:
paralelo, seqüencial e propagação
Analogias podem ser feitas para outros operadores elementares
15
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Erosão Paralela

x  E, b(f)(x) =

yBxE
{ f(y) b(y-x) };
onde f  [0,k]E , b  B e B   x 
–1 –1 –1
–1 0 –1
–1 –1 –1 b
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
k
k
k
0
0
0
0
k
k
k
0
0
0
0
k
k
k
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
b
E
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
1
k
1
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
E
16
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Características da Erosão Paralela
 Simples para implementar
 Provavelmente o mais simples




Baixa eficiência devido à varredura desnecessária
Simples implementar em hardware
Permite computação paralela
bG = b1  . . .  bk

bG(f) = bk(. . .(b1(f)). . .)
17
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Erosão Seqüencial
 { (f)(y)
 {- (f) (y)
+b+(f) (x) =
 x  E na ordem raster,
yB+xE
 x  E na ordem anti-raster, -b-(f) (x) =
yB-xE
B+
+
b  ,
E
onde f[0,k] ,
Bb 
+ +
b
b+(y-x)};
b-
b-(y-x)};
e Bx
–1 –1 –1
–1 0
b0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
k
k
k
0
0
0
0
k
k
k
0
0
0
0
k
k
k
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
+b+
E
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
k
0
0
0
0
2
k
k
0
0
0
0
3
k
k
0
0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 –1
–1 –1 –1
b+
E
18
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Decomposições
[Rosenfeld’66]
Aplicar um operador seqüencial com vizinhança local

Aplicar uma seqüência de operadores paralelos com mesma
vizinhança
+b+(f) = b+(. . .(b+(f)). . .) = kb (f)
+
b : b0 = 0
e bG=kb+ 
kbb estável (kb =
(k+1)b)
e bG = kb+  kb-
+b+(f)
-

 bG(f) =
( f)
+
 bG(f) =  b+(  b-(f) )
b-
19
Introdução
Erosão & Dilatação
Padrões da Erosão
Ilustração de bG =
–1 –1 –1
–1 0
0 –1
–1 –1 –1
b-
2b–2 –2 –2 –2 –2
–2 –1 –1 –1
–2 –1 0
TD por Erosões
kb
Conclusão

+
kb
b+
2b+

0 –1 –2
–1 –1 –1 –2
–2 –2 –2 –2 –2
=
–2 –2 –2 –2
–2 –1 –1 –1
–2 –1 0 –1
–1 –1 –1
–2 –2 –2 –2
–2
–2
–2
–2
bG = 2b-  2b+
20
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Características da Erosão Seqüencial
 Mais eficiente
 Simples de implementar em hardware
 Restrito à máquinas seqüenciais
 Equivalência restrita entre erosão paralela e
seqüencial:
bG = kb-  kb+  b genérico e não cobre E
b = kb-  kb+  b estável e aplicável à TD
G
21
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Erosão por Propagação
• A idéia é processar somente os pixels
que podem mudar na erosão:
– Fronteira: conjunto de pixels que podem
causar mudança nos pixels vizinhos
• Enquanto processa a erosão a próxima
fronteira é calculada
• É adequado para uma seqüência de
funções estruturantes não crescentes
22
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Erosão por Propagação
f
b
fb

p
g
b
’fb
23
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Fronteira
(f,b) = {xE: yBx, f(y) > f(x) b(x-y)}
0
0
0
0
0
0
0
0
[0]
[0]
[0]
[0]
[0]
0
0
[0]
k
k
k
[0]
0
0
[0]
k
k
k
[0]
0
0
[0]
k
k
k
[0]
0
0
[0]
[0]
[0]
[0]
[0]
0
0
0
0
0
0
0
0
0
0
0
0
0
Exemplo 2 0
0
Exemplo 1
0 0 0 0 0
0 0 0 0 0
0 [1] [1] [1] 0
0 [1] k [1] 0
0 [1] [1] [1] 0
0 0 0 0 0
0 0 0 0 0
0
0
0
0
0
0
0
–1 –1 –1
–1 0 –1
–1 –1 –1 b
24
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Erosão por Propagação
x  (f,b), y  Bx  E ,
if pb(f)(y) > f(x) b(x-y)
pb(f)(y) = f(x) b(x-y);
fifo_add(’(f,b), y);
onde f  [0,k] , b   , B   x 
E
0
0
0
0
0
0
0
[0]
[0]
[0]
[0]
[0]
0
[0]
k
k
k
[0]
0
[0]
k
k
k
[0]
0
[0]
k
k
k
[0]
0
[0]
[0]
[0]
[0]
[0]
0
0
0
0
0
0
0
0
0
0
0
0
0
B
pb
–1 –1 –1
–1 0 –1
–1 –1 –1 b
0
0
0
0
0
0
0 0 0 0 0
0 0 0 0 0
0 [1] [1] [1] 0
0 [1] k [1] 0
0 [1] [1] [1] 0
0 0 0 0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
25
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Decomposição da Função Estruturante
Se existe bi tal que
bG = b1  . . .  bk
onde:
b1  . . .  bk
[ ordem no reticulado ]
Então:
f
fb

f1

p
f1b
b1
f2
...
p
f2b
1
b2
...

fk = bG(f)
p
fkb
2
k
bk
26
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Características da Erosão por Propagação
Elimina varreduras desnecessárias
Menor restrição de bG (se b1  . . .  bk )
Implementação em hardware mais
complexa
Requer estrutura de armazenamento
Util quando aplicado em uma
seqüência de algoritmos paralelos
27
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Conteúdo
28
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Motivação
Mitchell mostrou que:
– TD  simples erosões em níveis de cinza
– Função estruturante
• Negativo da distância à origem
– Para métrica euclidiana
• Negativo do quadrado da distância à origem
 TDE2
29
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Transformada de Distância
TD através de erosões por bG
 x  E,
TD(f)(x) = bG(f)(x) =
k

{ f(y) b(y-x) };
yBxE
TD(f) = bG(f)
f
Propriedade:
bG(bG(f)) = bG(f)
bG(x) = - d(x,(0,0))
30
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Decomposição da TD
bG = b1  b2 . . .
g = f;
f  g { g = f; f = b (g); }
i
function g = distPar (f,b1, b2, … )
g = f;
while f ~= g
g = f;
f = eroPar (g,bi);
end
Function g = eroPar(f,b)
For all x  E in parallel
For all y  Bx  E
g(x) = min{f(y) - b(y-x)};
k
b4
b3
b2
f
TD(f) = b (f)=b (b ( b ( (f))))
G
4
3
2
1
b1
31
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Decomposição da TDE
f
b1(f)
b4
b3
b2(b1(f))
b3(b2(b1(f)))
b4(b3(b2(b1(f))))
= TDE(f) = bG(f)
b2
b1
32
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
TD com métrica euclidiana (TDE)
Decomposição da função estruturante bG
-4i+2
bi
=
-2i+1
-4i+2
-2i+1 -4i+2
0
-2i+1
-2i+1 -4i+2
bG = b1  b2  . . .
f
bG(f) = bk(. . .(b1(f)). . .)
33
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Classificação da TD por Erosão
Métricas
Padrões de Algoritmos
TD
Paralelo Seqüencial Propagação
X
Rosenfeld66
Rosenfeld68
X
Borgerfors86
X
Mitchell92
X
Vincent92
X
Mitchell94
X
b8
bO
X
X
X
X
X
X
X
X
X
X
b3:4
b5:7:11
bE
X
X
X
X
X
X
X
X
X
b4
X
X
X
34
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Conteúdo
35
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Erosão inicial
x  E, y  Bx  E ,
if inib(f)(y) > f(x) b(x-y)
inib(f)(y) = f(x) b(x-y);
fifo_add(’(f,b), [y d++]);
5
6
4
3
7
8
2
1
direções
–2 –1 –2
–1
0 -1
-2 –1 -2
b1
inib
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
1
k
k
k
k
0
0
1
k
k
k
k
0
0
1
k
k
k
k
f
36
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Erosão Direcional
[x k]  (f,b), y  Bx [k--, k, k++]  E ,
if dirb(f)(y) > f(x) b(x-y)
dirb(f)(y) = f(x) b(x-y);
fifo_add(’(f,b), [y d]);
k-k
k ++
–6 –3 –6
–3
0 -3
-6 –3 -6
b2
dirb
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
1
2
4
4
4
0
0
1
4
k
k
k
f
0
0
1
4
k
k
k
37
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Conteúdo
38
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
TDE = b (f)  1D
G
f
TDE(f) = b (f)
G
bG
39
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Decomposição da função estruturante
bi = -2i+1 0 -2i+1
-1 0 -1
b 1  b2
b2
b1

-3 0 -3
=
-4 -1 0 -1 -4
40
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Decomposição da função estruturante
• 4 seqüências decrescentes de funções
estruturantes 1-D direcional:
– North, South, East, West
bNi -2i+1
0
bWi
-2i+1
bEi
0
0
-2i+1
0
bSi -2i+1
41
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Decomposição da função estruturante
• Vantagens desta decomposição
– Linhas e colunas podem ser processadas
independentemente (processamento paralelo)
• Processamento 1-D
– algoritmos simples
• Família decrescente direcional de funções
estruturantes
– Implementações eficientes de erosões por
propagação
42
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Algoritmo em dois passos
• Primeiro passo
– TDE para todas as colunas (North/South)
– Varreduras raster e anti-raster
• Segundo passo
– TDE para todas as linhas (West/East)
– Erosão por propagação
• Nota: somente processamento 1-D
43
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Erosão 1-D direcional para TDE
Melhorias adicionais
• Para funções estruturantes direcionais
– East e West: é possível usar uma fila (FIFO) e
usar um processamento seqüencial
– usar imagens de entrada e saída iguais
• Evita cópias de imagens
44
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Exemplo 1
Primeiro passo: colunas da imagem binária original
Raster
Anti-raster
Este passo é muito eficiente:
1.5 acessos por pixel
45
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Exemplo 1
Segundo passo
Entrada
East
West
Este passo é mais lento:
Usa erosões por propagação
46
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Exemplo 2
k
k
f=
k
0
-5
-3
-1
b= 0
-1
-3
-5
9
4
fv=b(f) =
1
0
4
1
0
1
0
1
4
9
k
k
k
k
b1 = -1 0 -1
5
2
f1= b1(fv) =
1
0
1
1
0
1
0
1
1
2
1
2
5
10
b2 = -3 0 -3
4
2
b2(f1) =
1
0
1
1
0
1
0
1
1
2
1
2
4
5
k
k
0
k
0
k
k
k
k
k
k
k
47
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Desempenho
image2
80
60
100
90
90
80
121
120
90
101
EroDir
190
210
EroPro
230
240
Saito
Eggers
PMN
Meijster
LZ
EroPar
1012
701
mili-segundos
Desempenho de Algoritomos da TDE
0,3
Saito
0,2
Eggers
segundos
image1
512x512
PMN
Meijster
LZ
EroDir
0,1
EroPro
0
Pentium III - 800 MHz - 256 MB
image1
image2
48
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Comparação de desempenho
• A TDE proposta é comparável com os
algoritmos mais eficientes da TD
• É o mais simples algoritmo da TDE
– Para entendimento
– Para codificação
• É satisfatório para processamento
paralelo
• É satisfatório para dimensões mais altas
49
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
O que tem de ruim
• A condição de pior caso
– Acontece com uma linha diagonal de fundo
– O número de vezes que os pixels entram na fila é
O(n3), considerando uma imagem nxn
O que tem de bom
• Para imagens típicas, eficiência OK
64K
LZ
256K 1M
4M
0.022 0.153 0.659 2.81
Mei 0.028 0.181 0.763 3.08
segundos
Pentium III
750 MHz
128 MB
50
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Conteúdo
51
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Resultados
• Foram apresentados algoritmos da erosão em três
padrões de varredura:
– paralelo,
– seqüencial e
– por propagação
• Foram feitos estudos da equivalências entre estes
padrões
• Foram classificados algoritmos da TD usando estes
padrões
• Foram definidos algoritmos simples e eficientes para o
cômputo da TDE
– Direcional
– Multimensional
• Existe algoritmo linear para a TDE
– Meijster, Roerdink, Hesselink (00)
52
Introdução
Erosão & Dilatação
Padrões da Erosão
TD por Erosões
Conclusão
Conclusões
• É possível aplicar os conceitos
apresentados em outros algoritmos, como
MAT e reconstrução
• Morfologia Matemática é uma boa teoria
para entender e desenvolver algoritmos
novos e eficientes
Fim
53
54
55