A-048

Prévia do material em texto

Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002. p.292-303.
G. Vale; A.. Dal Poz
O PROCESSO DE DETECÇÃO DE BORDAS DE CANNY:
FUNDAMENTOS, ALGORITMOS E AVALIAÇÃO EXPERIMENTAL
GIOVANE MAIA DO VALE
ALUIR PORFÍRIO DAL POZ
Universidade Estadual Paulista - Unesp
Faculdade de Ciências e Tecnologia - FCT
Departamento de Cartografia, Presidente Prudente - SP
{gmvale, aluir}@prudente.unesp.br
RESUMO: Este artigo descreve e discute os fundamentos teóricos e os aspectos algorítmico e
computacional do processo de detecção de bordas de Canny. Baseia-se em dois critérios básicos de
desempenho, i.e., os critérios de detecção e localização. Estes dois critérios estão sujeitos ainda a um
terceiro, conhecido como injunção de resposta múltipla, que força o processo detecção a detectar uma
única borda onde existe somente uma borda verdadeira. O principal objetivo do trabalho de Canny é o
desenvolvimento de um detector ótimo para o tipo de bordas mais comum em imagens digitais, i.e., as
bordas tipo degrau. Um das principais constatações de Canny é que o operador ótimo encontrado é muito
semelhante à função gerada pela primeira derivada da função Gaussiana. Em complemento a este
operador, são também propostos um processo conhecido como supressão não máxima, que tem por
função principal o afinamento das bordas, e um outro processo conhecido como histerese e que se baseia
numa dupla limiarização, cuja função é a de eliminar a fragmentação das bordas causada pelo ruído da
imagem. Este trabalho apresenta, além dos aspectos teóricos e computacionais acima mencionados,
também alguns resultados experimentais obtidos com imagens sintéticas e reais.
ABSTRACT: This paper describes and discusses the theoretical fundamentals and the computational and
algorithmic aspects of the Canny edge detection process. It is based on two basic performance criteria,
i.e., the detection and localization criteria. Both criteria must be still under a third one, which is known as
the multiple response constraint and enforces the edge detection process to detect single edge where there
is only one true edge. The major goal of Canny work is the development of an optimal detector for the
most common edge occurrence in digital images, i.e., the step edges. One of most important finding of
Canny is that the optimal operator found is very similar to the first derivative of the gaussian function. In
complement to this operator, it is proposed two processes that are known as the nonmaximum suppression
and the hysteresis. The goal of the nonmaximum suppression is the edge thinning, which allows the
detected edges to be one-pixel width. The hysteresis is based on a double thresholding and its goal is to
eliminate edge fragmentation due to the image noisy. This paper also presents, in addition to the
theoretical and computational aspects above mentioned, some experimental results obtained with
synthetic and real images.
1 INTRODUÇÃO
As bordas constituem informação de alta
freqüência e encerram propriedades significativas de uma
imagem. Estas propriedades incluem descontinuidades
fotométricas, geométricas e as características físicas dos
objetos. Tais propriedades do objeto são passadas à
imagem pois, variações pertinentes ao objeto ocasionam
variações nos tons de cinza da imagem.
Para que se obtenha resultados acurados nos
passos subsequentes à detecção das bordas, é necessário
que esta detecção seja eficiente e confiável. A fim de que
as variações dos tons de cinza sejam detectadas (bordas) é
necessário diferenciar a imagem. Quando a imagem é
diferenciada, as variações dos níveis de cinza são
detectadas e, por conseqüência, detecta-se também o
ruído, que é uma forma indesejável de variação. Para que
as bordas espúrias não sejam então detectadas, deve-se
suavizar a imagem antes da detecção. Contudo, existem
efeitos inoportunos ligados à suavização, i. e., perda de
informação e deslocamento de estruturas de feições
proeminentes no plano da imagem. Além disso, existem
diferenças entre as propriedades dos operadores
diferenciais comumente utilizados, o que ocasiona bordas
diferentes. Logo, é difícil formular um algoritmo de
detecção de bordas que possua um bom desempenho em
diferenciados contextos e capture os requisitos
necessários aos estágios subsequentes de processamento
(Ziou e Tabbone, 1997). Consequentemente, no tocante
ao processamento de imagem digital, uma variedade de
Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002.
G. Vale; A.. Dal Poz
detetores de bordas tem sido desenvolvidos visando
diferentes propósitos, com formulações matemáticas
diferenciadas e com propriedades algorítmicas distintas.
Com base nos problemas acima mencionados,
Canny (1986), desenvolveu um processo de detecção de
bordas a partir de critérios de quantificação de
desempenho de operadores de bordas conhecidos como:
critério de detecção e critério de localização. Estes
critérios de desempenho ainda estão sujeitos ao critério de
resposta múltipla, que corresponde ao fato de que deve
haver, na saída do operador, uma única resposta para uma
única borda. Para que os critérios sejam aproximadamente
atendidos, Canny aproxima o operador ótimo, obtido a
partir dos três critérios de desempenho, pela primeira
derivada da função Gaussiana. Em complemento a este
operador, foi proposto um processo chamado supressão
não máxima (supressão de valores de pixels que não
forem máximos locais na direção transversal à borda), que
causaria um afinamento da borda, atendendo à injunção
de resposta múltipla, e uma limiarização adaptativa
(histerese) com “complementação de bordas”, para
eliminar a fragmentação dos contornos das bordas.
Este trabalho tem por motivação a discussão de
aspectos teóricos e computacionais do processo de
detecção de bordas de Canny. A seção 2 apresenta a
definição e o desenvolvimento dos critérios de
desempenho. A dedução do filtro ótimo a partir dos
critérios de desempenho, é apresentada na seção 3. A
justificativa da aproximação do filtro ótimo pela primeira
derivada da função Gaussiana encontra-se na seção 4. Na
seção 5 encontram-se aspectos pertinentes à estimação do
ruído e limiarização. A seguir, na seção 7 são
apresentados os aspectos algorítmico e computacional. As
considerações finais são apresentadas na seção 8.
2 CRITÉRIOS DE DESEMPENHO
Dada sua importância, os detetores de borda (step
edge detectors) fazem parte de muitos sistemas de visão
computacional. Suas aplicações são incontáveis e uma de
suas principais características é a de reduzir drasticamente
a quantidade de dados a serem processados, preservando
informações estruturais importantes sobre a fronteira dos
objetos.
Qualquer que seja o detetor e a técnica envolvida,
é necessário que este atenda à três critérios básicos
(Canny, 1986), a saber:
1) Taxa de Erro: (SNR)
As bordas que ocorrem na imagem não devem ser
confundidas e não se deve detectar bordas falsas, ou seja,
o detetor deveria ter baixa probabilidade de:
• Falhar ao detectar pontos de borda
verdadeiros;
• detectar, falsamente, pontos não pertencentes
à borda.
Visto que ambas as probabilidades são funções
monotonicamente decrescentes, em função da razão
sinal/ruído, este critério eqüivale a maximizar a razão
sinal/ruído.
Maximizar a razão sinal/ruído implica em
minimizar o ruído.
2) Localização:
Pontos de borda devem estar bem localizados, isto
é a distância entre os pontos extraídos pelo detetor e o
"centro" verdadeiro da borda deve ser minimizada.
3) Resposta:
O detetor de borda não deve identificar múltiplos
pixels de borda onde existe um único, ou seja, deve-se
obter uma única resposta para uma única borda.
Este critério está implicitamente contido no 1º
critério pois quando ocorrem duas respostas para uma
mesma borda, então, uma deverá ser considerada falsa.
Contudo, a formulação matemática do 1º critério
não engloba necessariamente a questão de resposta
múltipla, sendo necessário explicitá-la.
2.1 Detecção e Localização
Teoricamenteestabelecidas as metas de
desempenho de um detetor de bordas, o que se quer agora
é sintetizá-las matematicamente de modo a se tornarem
uma ferramenta aplicável. Sem perda de generalidade, os
sinais serão trabalhados de forma unidimensional, pois o
comportamento das bordas é análogo para o caso
bidimensional, exceto no caso da ocorrência de quinas.
A filtragem de uma borda ruidosa com o filtro da
figura 1a) (operador diferença), dá origem a um sinal
filtrado que apresenta muitos máximos locais
(serrilhamento). Porém, quando a borda é filtrada com o
filtro mostrado na figura 1b), o que se obtém é um sinal
filtrado mais suave (Canny, 1986).
Figura 1 – Filtros diferenciais
Em seu trabalho, Canny (1986) explicita que as
bordas devem ser consideradas como um máximo local no
resultado da filtragem (figura 2). Por este motivo, o filtro
da figura 1a) não tem desempenho tão bom quando
comparado ao filtro da figura 1b), pois o sinal resultante
da filtragem é "serrilhado", podendo apresentar mais de
um máximo nas adjacências da borda.
b)
g(x)
x
f(x)
a) x
Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002.
G. Vale; A.. Dal Poz
Figura 2 - Ilustração da borda G(x) como máximo local
na saída do operador (H G (x))
Serão abordadas inicialmente as questões relativas
à razão sinal/ruído e à localização.
Seja f(x) a resposta de impulso do filtro e G(x) a
borda. Assumi-se que a borda está centrada em x = 0.
Então, a resposta de impulso do filtro para esta borda, em
relação ao seu centro, é dada pela convolução:
∫− −=
W
W
G dx)x(f)x(GH (1)
assumindo que o filtro tem resposta de impulso finito no
intervalo [-W , W] com W < ∞ , ou seja, o suporte do
filtro (conjunto de pontos do domínio onde a função não
se anula) é compacto (Limitado e Fechado) (Gomes,
1994). O erro médio quadrático da resposta para o ruído
n(x) somente, será:
[ ]{ } 2
1
W
W
2
0
2
12
n dx)x(fn)x(f*)x(nEH 


== ∫− (2)
onde n² 0 é a amplitude do ruído médio quadrático por
unidade de comprimento, ou seja, n² 0 é o quadrado da
quantização do ruído (Lim, 1990). Defini-se então o
primeiro critério como o resultado da razão sinal/ruído,
expresso pelo quociente das respostas acima descritas:
∫
∫
−
−
−
=
W
W
2
0
W
W
dx)x(fn
dx)x(f)x(G
SNR (3)
Na equação 3, acima, pode-se perceber que se o
denominador, que é o erro médio quadrático da resposta
para o ruído somente, tender à zero, SNR aumentará, isto
é, se o ruído na imagem for próximo de zero a detecção
será tanto melhor. Dessa forma percebe-se que a forma
matemática sintetiza bem a noção intuitiva.
Como as bordas estão centradas em x = 0, na
ausência do ruído deveria haver neste ponto um máximo
local, para a resposta. Sendo esta representada por
H G (x), então H' G (0) = 0. Se H n (x) é a resposta do filtro
para o ruído somente, então a resposta total pode ser
expressa como H n (x) + H G (x). Se esta resposta total tem
um máximo em x 0 , então:
H' n (x 0 ) + H' G (x 0 ) = 0 (4)
Lembrando que a Série de Taylor é dada por:
f(x) = f(x 0 ) + !1
h f '(x 0 ) + !2
h2 f '' (x 0 )+ ...+ !n
hn f n ( x 0 )+..
onde h = x - x 0 , com x∈ℜ .
Logo, a expansão de Taylor de H' G (x 0 ), em
relação à origem (Mac-Laurin), é dada por:
H' G (x 0 ) = H' G (0) + x 0 H'' G (0) + O(x
2
0 ) (5)
Notar que:
H' G (x 0 ) = H' G (0) + (x 0 - 0)/ 1! H'' G (0) + O(x
2
0 ) (6)
Como H' G (0) = 0 o primeiro termo da expansão
(eq. 5) é ignorado. Além disso, como x 0 é pequeno,
ignora-se os termos quadrático e de ordem superior.
Assim, das equações 4 e 5, tem-se:
H'' G (0) x 0 ≅ - H' n (x 0 ) (7)
Pois:
H' G (x 0 ) ≅ x 0 H'' G (0)
E, substituindo a equação acima na equação 4:
H' n (x 0 ) + H'' G (0) x 0 ≅ 0
H' n (x 0 ) é uma quantidade randômica Gaussiana e
segundo Canny (1986) sua variância é dada por:
∫−
W
W
22
00n dx)x('fn = )²] (x E[H' (8)
onde E[y] é o valor esperado de y (esperança de y).
Combinando este resultado com a equação 7 (substituindo
H' G (x 0 ) por x 0 H'' G (0)), tem-se:
G(x)
H G (x)
x
x
Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002.
G. Vale; A.. Dal Poz
2
02W
W
W
W
22
02
0 x
dx)x('f)x('G
dx)x('fn
]x[E δ=



 −
≅
∫
∫
−
− (9)
onde 0xδ é uma aproximação para o desvio padrão de
x 0 .
Finalmente, a localização é definida como o
inverso de 0xδ , isto é:
∫
∫
−
−
−
=
W
W
2
0
W
W
dx)x('fn
dx)x('f)x('G
oLocalizaçã (10)
As equações 3 e 10 são as fórmulas matemáticas
para o primeiro e o segundo critérios e reduzem o
problema de projeto do filtro à maximização de ambas as
fórmulas, simultaneamente. A fim de que isso ocorra,
maximiza-se o produto da primeira equação pela segunda.
Por enquanto será usado o produto dos critérios para
bordas arbitrárias, isto é, se buscará maximizar:
∫
∫
−
−
−
W
W
2
0
W
W
dx)x(fn
dx)x(f)x(G
 
∫
∫
−
−
−
W
W
2
0
W
W
dx)x('fn
dx)x('f)x('G
 (11)
Esta equação deve possuir uma injunção adicional
na solução, pois, até aqui, nenhuma definição sobre a
eliminação de respostas múltiplas foi descrita
matematicamente. Tal problema será explicitado na
próxima seção.
2.2 Eliminação de Respostas Múltiplas
Ao se estabelecer o problema de detecção de
bordas, foi especificado que as bordas deveriam ser
detectadas como máximos locais na resposta de um filtro
linear aplicado à imagem. Os critérios de detecção até
aqui introduzidos medem a eficácia do filtro na
discriminação entre o sinal e o ruído no centro da borda.
Porém tais critérios não levam em consideração o
comportamento nas proximidades da borda.
Como poderá ser visto a seguir, o primeiro e o
segundo critérios podem ser trivialmente maximizados.
Seja k e h duas funções reais integráveis em [a, b],
então a desigualdade de Schwarz para integrais é dada
por:
dx)]x(h[.dx)]x(k[dx)x(h).x(k
b
a
2b
a
2
2b
a ∫ ∫∫ ≤



Pela desigualdade de Schwarz, acima descrita, para
integrais, mostra-se que SNR é limitado superiormente
por:
n ∫−
− −
W
W
21
0 dx)x(G (12)
E o limite superior para a Localização:
n ∫−
− −
W
W
21
0 dx)x('G (13)
Se ambos os limites são atendidos, então o produto
de SNR pela localização é maximizado quando
f(x) = G(-x) para x ∈[-W, W].
Assim, de acordo com os dois primeiros critérios,
o detetor ótimo de bordas tipo degrau deve possuir
também a forma de um degrau, como o operador
diferença. Como este operador possui uma banda muito
larga, sua aplicação, gera, devido ao ruído, respostas com
muitos máximos, gerando muitos máximos falsos de
borda. Como foi visto anteriormente a filtragem com
operadores diferença apresenta inúmeros picos
(serrilhado), nas adjacências da borda verdadeira,
dificultando ou impossibilitando a seleção de um único
ponto de borda. É necessário adicionar aos critérios um
quesito que diga que a função f não terá muitas respostas
para uma única borda na vizinhança do degrau. É antes
necessário limitar o número de picos na resposta, de modo
que haja baixa probabilidade de serem detectadas mais
que uma borda. O ideal seria fazer a distância entre os
picos na resposta do ruído se aproximar à largura da
resposta do operador para um único degrau de borda. Esta
largura seria uma fração da largura do operador.
A distância entre máximos adjacentes na resposta
de f devido ao ruído, denotado por x max , será o dobro de
x zc , que é a distância média entre pontos críticos desta
resposta, ou seja:
zcmax x2x = (14)
onde, x zc é dado por:
2
1
2
2
zc
dx)x("f
dx)x('f
x










π=
∫
∫
∞+
∞−
∞+
∞− (15)
Pode-se, então, aproximar a distância x max para
alguma fração k da largura do operador:
kW)f(xmax = (16)
Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002.
G. Vale; A.. Dal Poz
A expressão15 representa a injunção de resposta
múltipla. Note que o número ótimo de k seria o que
proporcionasse apenas um máximo para a região de
resposta do filtro. Sendo 2W a largura da região onde se
concentra o suporte do filtro, o número de máximos (N n )
da resposta devido ao ruído é dado por:
k
2
kW
W2
x
W2N
max
n === (17)
Lembrando que k é o número que estabelece a
distância entre máximos na região de suporte do operador,
verifica-se que quanto mais próximo de zero k estiver,
maior será o número máximos devido ao ruído.
É interessante notar que a distância entre máximos
varia na mesma proporção com que a largura do operador
é escalonado. Para tanto, supor que λf é obtido
escalonando f por um fator de escala λ , i. e.,
λf (x) = f( λ
x ). Substituindo esta expressão na equação
14, tem-se que )f(x)f(x maxmax λ=λ , visto que se está
lidando com um espaço de funções. Assumindo agora que
o suporte do filtro f é [-W, W], tem-se que o suporte de
λf é escalonado por λ , i. e., o suporte de λf é [-λW,
λW]. Portanto, as larguras de suporte de f e λf são,
respectivamente, 2 W e 2 (λW). Fica então provado que
a distância entre máximos e a largura do operador são
escalonadas pelo fator de escala λ . Outra constatação
importante é que o número de máximos no intervalo de
suporte de f é invariante em relação ao escalonamento de
f. De fato, o número de máximos Nn ( λf ) para λf é a
razão entre a largura de suporte de λf (i. e., λ (2W)) e o
intervalo entre máximos para λf (i.e., λ x max (f)), i. e.,
Nn ( λf ) = λ (2W) / λ x max (f) = 2W / x max (f). Este é
exatamente o número de máximos para f .
3 UM DETETOR PARA BORDAS (STEP EDGES)
Uma borda tipo degrau pode ser expressa
matematicamente por G(x) = A u 1− (x), onde A é a
amplitude da borda e u 1− (x) é dada por:



≥
<
=− 0xpara,1
0xpara,0
)x(u 1 (18)
E substituindo G(x) na equação 3:
∫
∫
−
−
− −
=
W
W
2
0
W
W
1
dx)x(fn
dx)x(f)x(Au
SNR (19)
Como A é uma constante positiva, pode-se retirá-la
da integral e do módulo e, como também u 1− (x) é nulo
para x<0, a equação pode ser rescrita como:
∫
∫
+
−
−
=
W
W
2
0
0
W
dx)x(fn
dx)x(fA
SNR (20)
Substituindo G(x) na equação 10:
∫
∫
+
−
+
−
− −
=
W
W
2
0
W
W
1
dx)x('fn
dx)x('f.))'x(u(A
oLocalizaçã (21)
Como u 1− (x) varia muito abruptamente em x = 0,
logo (u 1− (-x))' ∞−→ , isto é (u 1− (x))' = - δ (x), sendo
δ (x) o delta de Dirac (Butkov, 1968). Pode-se então
rescrever a equação 21 como:
∫∫
∫
+
−
+
−
+
−
=
δ−
=
W
W
2
0
W
W
2
0
W
W
dx)x('fn
)0('fA
dx)x('fn
dx)x('f)]x([A
oLocalizaçã
(22)
O numerador da Localização possui tal forma pois,
pela propriedade de filtragem da função δ (x), tem-se
(Butkov, 1968):
)0(hdx)x(h)x( =δ∫
+∞
∞−
 (23)
onde h(x) é uma função contínua qualquer.
Quando se toma h (x) = f '(x), chega-se ao
numerador da equação 22.
Ambos os critérios melhoram diretamente com a
razão A/n 0 , que pode ser chamada razão sinal/ruído da
imagem. Agora, remove-se esta dependência da imagem e
define-se duas medidas de desempenho ΛΣ e , as quais
dependem somente do filtro:
∑ ∑
∫
∫
+
−
−
==
W
W
2
0
W
0 dx)x(f
dx)x(f
)f(onde)f(
n
ASNR (24)
Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002.
G. Vale; A.. Dal Poz
∫
+
−
=ΛΛ=
W
W
20 dx)x('f
)0('f
)'f(onde)'f(
n
AoLocalizaçã (25)
Supor agora que λf seja um filtro escalonado
espacialmente, construído a partir de f, onde
λf (x) = f ( λx ), com λ >1 sendo um fator de escala.
Notar que se o intervalo de suporte de f é [-W, W], então
o intervalo correspondente para λf é [-λW, λW]. Isso
significa que as larguras de suporte de impulso de f e λf
são respectivamente 2W e λ (2W). Pode-se dizer então
que f é um filtro estreito e λf um filtro mais largo.
Quando se substitui λf nas equações (24) e (25), obtém-
se as funções de desempenho do filtro escalonado:
)'f(1)'f(e)f()f( Λ
λ
=ΛΣλ= λλ∑ (26)
A primeira destas equações mostra que um filtro
λf com larga resposta de impulso terá melhor razão
sinal/ruído que um filtro estreito quando aplicado à
imagem. Matematicamente, se λ variar é imediato que
∑ λ )f( variará diretamente. A segunda implica que um
filtro estreito dará melhor localização que um largo.
Matematicamente, se λ variar, então )f( 'λΛ terá uma
variação inversamente proporcional a λ . Nota-se que as
variações são inversamente relacionadas, isto é, ambos os
critérios ou crescem ou decrescem por λ . Trata-se
então de um princípio de incerteza relacionado com a
detecção (SNR) e localização, não podendo melhorá-los
simultaneamente, ou seja, se a localização melhora, então
a detecção tem seu resultado piorado e vice-versa.
É interessante notar que esse resultado teórico está
relacionado com questões práticas de projetos de filtros de
detecção de borda. Por exemplo, quando se usa uma
máscara de dimensão pequena, a sensibilidade aos
detalhes será maior. Infelizmente esta sensibilidade não
aumenta apenas pelos detalhes reais da imagem, mas
também pelos detalhes espúrios da imagem, causados
principalmente pelo ruído da imagem. Com um filtro
largo ganha-se na detecção de detalhes mas perde-se em
localização. A discussão acima sugere que o critério para
determinação do filtro (f) ótimo é dado pelo produto das
equações (24) e (25), visto que este produto é invariante
às mudanças de escala:
∫∫
∫
+
−
+
−
−
=ΛΣ
W
W
2W
W
2
0
W
dx)x('f
)0('f
.
dx)x(f
dx)x(f
)'f(.)f( (27)
A solução obtida a partir da maximização da
expressão 27 é uma classe de funções, todas relacionadas
ao longo do espaço-escala.
Encontrar a função f que maximize a equação 27 é
um trabalho bastante complexo, que envolve o uso de
cálculo variacional. A aplicação desta técnica ainda
requer que a equação 26 seja rearranjada através da
técnica dos multiplicadores de Lagrange, que possibilita a
obtenção de uma forma passível de ser, posteriormente,
transformada na equação diferencial de 4ª ordem de
Euler-Lagrange.
A solução geral para a equação de Euler-Lagrange
no semi-intervalo de suporte [-W, 0] tem a seguinte
forma:
cxcosea
xseneaxcoseaxsenea)x(f
x
4
x
3
x
2
x
1
+ω+
+ω+ω+ω=
α−
α−αα
 (28)
onde ce,,a,a,a,a 4321 ωα são as incógnitas a
determinar.
A função 28 está sujeita às seguintes condições de
contorno:
f (0) = 0 f (-W) = 0 f ' (0) = s f ' (-W) = 0 (29)
onde s é um incógnita constante igual à declividade da
função f na origem. Visto que f (x) é assimétrica, pode-se
estender a equação 28 para todo o intervalo de suporte
[-W, W] usando o fato de que f (-x) = -f (x). As quatro
condições de contorno possibilitam encontrar as
quantidades de 4321 aea,a,a em função das incógnitas
sec,, ωα . Aplicando as condições de contorno 29 à
equação 28, obtém-se um sistema de equações para a
obtenção dos valores de 4321 aea,a,a em função das
incógnitas sec,, ωα .
Como c é uma constante de integração gerada na
obtenção da equação 28, pode-se arbitrá-la, ficando os
parâmetros incógnitos reduzidos a 3 ( βωα e, =s/c).
Infelizmente isso não reduz a complexidade do problema,
pois ainda é necessário determinar os valores destes
parâmetros que maximizam a condição de filtro ótimo
(eq. 27). Se não bastasse, falta impor o critério de resposta
múltipla. Como uma solução analítica para este problema
é inviável, um processo de otimização numérica é
recomendado.
A forma do filtro f depende, então, da injunção de
respostas múltiplas, isto é, depende da distâncias entre as
respostas adjacentes (x max ). Em geral, o ideal é que as
respostas adjacentes estejam o mais distantes possível,
facilitando a separação do pico verdadeiro dos falsos.
Segundo Canny (1986), quanto menor o espaçamento
entre as respostas adjacentes, mais íngreme é a função f
na origem. Assim, um filtro muito íngreme, em relação à
origem, beneficia o critério de localização, mas não é
favorável aos outros critérios. Por outro lado, um filtro
menos íngreme,em relação à origem, é desfavorável ao
Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002.
G. Vale; A.. Dal Poz
critério de localização, mas os critérios de detecção e de
respostas múltiplas são beneficiados.
Portanto, o critério de otimização numérica
mencionado acima deve encontrar um conjunto de
parâmetros que balanceie otimamente os três critérios.
Canny (1986) apresenta a seguinte expressão matemática
para o critério de resposta múltipla:
Σ=
σ
r
)0('f
s
 (30)
onde sσ é o desvio padrão do ruído e r é o fator de
desempenho de resposta múltipla. O fator r varia no
intervalo [0, 1] e, quanto mais próximo estiver de 1, mais
afastadas estarão as respostas múltiplas.
Os resultados obtidos por otimização numérica
para vários filtros são dados na tabela 1. Os coeficientes
4321 aea,a,a , para todos estes filtros podem ser
encontrados tomado c = 1. O maior valor de r obtido
usando otimização numérica é 0,576, que corresponde ao
filtro n.º 6 da tabela 1.
Como mostra a tabela 1, o filtro que apresenta um
melhor balanceamento é o 6, sendo desta forma
denominado ótimo. Entretanto, caso se esteja disposto à
tolerar uma ligeira redução no desempenho r de resposta
múltipla, pode-se obter uma melhora significativa nos
outros dois critérios. Por exemplo, os filtros 4 e 5 tem um
produto ΛΣ significativamente melhor que o filtro 6 e
somente uma pequena redução de r. Quando plotados
(figura 3), pode-se ver que os filtros 4 e 5 têm uma
declividade maior em relação à origem, sugerindo que o
ganho no desempenho está principalmente na localização.
O desnível abrupto próximo à origem sugere que, na
convolução, as diferenças sejam drásticas, privilegiando a
localização, ao passo que, no filtro 6, a transição, na
origem, é mais suave e fornece um melhor balanceamento
entre detecção e localização, apesar de fornecer um menor
índice r.
Fonte: Canny, 1986
Figura 3 - O operador ótimo para vários valores de x max .
De cima para baixo, se tem os seguintes valores de x max :
0,15, 0,3, 0,5, 0,8, 1, 1,2, e 1,4.
Tabela 1 - Parâmetros dos filtros e medidas de
desempenho de vários filtros
n maxx ΣΛ r α ω β
1 0,15 4,21 0,215 24,5955 0,12250 63,97566
2 0,3 2,87 0,313 12,4712 0,38284 31,26860
3 0,5 2,13 0,417 7,85869 2,62856 18,28800
4 0,8 1,57 0,515 5,06500 2,56770 11,06100
5 1,0 1,33 0,561 3,45580 0,07161 4,80684
6 1,2 1,12 0,576 2,05220 1,56939 2,91540
7 1,4 0,75 0,484 0,00297 3,50350 7,47700
Fonte: Canny, 1986.
4 UMA APROXIMAÇÃO EFICIENTE
O filtro ótimo recém derivado (n.º 6, tabela 1),
pode ser aproximado pela primeira derivada da função
Gaussiana G'(x) (figura 4), onde:








σ
−= 2
2
2
xexp)x(G (31)
A razão para que se utilize esta função reside no
fato de que ela apresenta uma eficiente forma para
computar a extensão bidimensional do filtro. Para o
momento, serão comparados o desempenho teórico da
primeira derivada da função Gaussiana com o operador
ótimo.
Figura 4 - Primeira derivada da função Gaussiana
O filtro f fica então:








σ
−
σ
−= 2
2
2 2
xexpx)x('G (32)
e os termos do critério de desempenho (eqs. 27 e 30) são
dados por:
∫∫
∫
∞+
∞−
∞+
∞−
∞−
σ
π
=
σ
π
=
=
σ
=
3
22
0
s
4
3)x('f
2
dx)x(f
1dx)x(f1)0('f
 (33)
O índice de desempenho total (eq. 27) para este
operador é:
92,0)'f(.)f( =ΛΣ (34)
1)
2)
3)
4)
5)
6)
7)
x
G’(x)
Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002.
G. Vale; A.. Dal Poz
Enquanto o valor r calculado a partir da equação
(30) é:
51,0rr
)0('f
s
=⇒Σ=
σ
 (35)
O desempenho ΣΛ da primeira derivada da função
Gaussiana é 20% pior que o desempenho do operador
ótimo. Quanto ao fator r, verifica-se que é pior 10%.
Provavelmente, seria difícil detectar uma diferença desta
magnitude visualmente, verificando-se o desempenho dos
dois operadores em imagens reais, e, por causa da
primeira derivada do operador Gaussiano poder ser
computada com muito menos esforço em duas dimensões,
dada também a sua simplicidade e separabilidade, ela tem
sido, na prática, usada com exclusividade.
A resposta de impulso dos dois operadores podem
ser comparadas, visualmente, na figura 5. Notar que as
respostas de impulso de ambos os filtros são bastante
semelhantes, o que intuitivamente sugere um desempenho
semelhante.
Figura 5 - a) Detetor Ótimo de Bordas; b) Primeira
derivada da função Gaussiana
5 ESTIMAÇÃO DO RUÍDO E LIMIARIZAÇÃO
A afirmação "não há imagem sem ruído",
infelizmente é verdadeira. Independente da causa ou do
tipo de ruído, a verdade é que ele sempre está presente e,
por ser um evento randômico, não pode ser predito ou
medido acuradamente em uma imagem, visto que, não se
pode separar ruído de dados da imagem. Dada a natureza
randômica do ruído, o que se pode fazer, algumas vezes, é
caracterizar seu efeito na imagem através de uma
distribuição de probabilidade com média e desvio-padrão
específicos.
Existem dois tipos de ruído que podem ser tratados
dessa forma: ruído independente do sinal e ruído
dependente do sinal.
O ruído independente do sinal é randômico e
estatisticamente independente do dados da imagem, isto é,
é adicionado aos pixels da imagem resultando uma
imagem ruidosa (Parker, 1997). Freqüentemente, isto
ocorre quando uma imagem é eletronicamente transmitida
de um local a outro ou até mesmo quando de sua
aquisição (sensor). Pode-se expressar esta idéia através da
adição:
B = A + N
onde B é a imagem ruidosa, A é a imagem sem ruído e N
é o ruído, lembrando que A e N não são correlacionados.
Comumente, por uma questão prática, assume-se que este
tipo de ruído segue a distribuição normal (ruído
Gaussiano), com média zero e um presumido desvio-
padrão.
Quando se toma imagens com os parâmetros de
ruído conhecidos ( σµ e ), o que se verifica é que este
ruído possui uma distribuição homogênea sobre a
imagem. Dessa forma pode-se então, tratar o problema de
estimação do ruído através da idéia de que bordas também
fazem parte do ruído (Wiener-Hopf, apud Parker, 1997).
A imagem seria filtrada e a variância do ruído seria
estimada a partir de uma média local calculada em uma
área restrita da imagem filtrada. Contudo, esta forma de
estimação de parâmetros do ruído é sensível às bordas e
os parâmetros estimados serão tendenciosos, tornando-se
pouco úteis.
Uma solução para este problema consiste em se
construir um histograma global da imagem filtrada
(amplitude/freqüência) e analisá-lo, considerando que a
resposta para as bordas são baixas freqüências com
valores altos de amplitude e que o ruído representará o
restante das respostas. Assim, pode-se efetuar a média
com valores de amplitude da imagem de entrada que, no
histograma, apresentem amplitudes menores que 80%, por
exemplo.
No caso de ruído dependente do sinal o nível de
ruído para cada ponto na imagem é uma função de seu
nível de cinza (Parker, 1997). Isto é, o ruído esta
relacionado ao nível de cinza dos pixels da imagem
através de alguma função. Felizmente esta forma de ruído
é menos importante e pode ser melhor contornado
(Parker, 1997).
Até mesmo com a estimação do ruído, o detetor de
borda é suscetível à fragmentação, principalmente se um
único limiar for usado. A fragmentação é a separação de
um contorno de borda causado pela flutuação da saída do
operador acima e abaixo do limiar, ao longo do contorno
(Canny, 1986). Caso se tenha um único limiar 1T e,
supondo que se tenha uma borda que possua uma média
de tons de cinza de mesmo valor ( 1T ), haverão valores da
borda acima e abaixo do limar até mesmo quando o ruído
é insignificante. O resultado da limiarização serão
fragmentos de bordas.
É também muito difícil fixar um limiar tal que haja
uma pequena probabilidade de se detectar borda espúria
quando o detetor possui grande sensibilidade. Uma
solução possível para este problema é efetuar a média da
magnitude ao longo de parte do contorno da borda.Se a
média está acima de um limiar, o segmento inteiro é
detectado. Se a média está abaixo do limiar, não se
detecta nenhuma parte do contorno.
Na implementação do operador de Canny a
limiarização é efetuada com histerese (duplo limiar) e é
acompanhada de um processo de "complementação das
bordas", isto é, se qualquer parte de um contorno está
acima do maior limar T 1 , então estes pontos são
imediatamente detectados, formando um conjunto L1. O
a)
b)
f(x)
G(x)
x
x
Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002.
G. Vale; A.. Dal Poz
restante dos pontos que se encontram abaixo do maior
limiar T 1 e acima do menor limiar T 2 (pontos do
contorno e pontos não pertencentes a ele) formam um
segundo grupo de pixels L2. O procedimento algorítmico
consiste em buscar no conjunto de pontos detectados L1 a
ocorrência de extremidades de contornos e, no segundo
conjunto de pontos L2, escolher pixels que completem
estes contornos. O algoritmo efetua este preenchimento
até que não hajam mais fragmentos de contornos isolados
em L1 ou que não hajam mais pontos em L2 que possam
ser aproveitados.
A probabilidade de fragmentação é muito reduzida
pois, para um contorno ser fragmentado, ele precisa
flutuar sobre o maior limiar e abaixo do menor limiar.
Também a probabilidade de falsos pontos de borda
isolados é reduzida pois a magnitude de tais pontos
precisa estar acima do maior limiar. A razão do maior
para o menor limiar na implementação está na faixa de
dois ou três para um, isto é:
2121 T3TouT2T == (36)
6 ASPECTOS ALGORÍTMICO E COMPUTACIONAL
No que diz respeito aos aspectos algorítmicos e
computacionais, serão expostos abaixo alguns detalhes
que se destinam à implementação do processo de detecção
elaborado por Canny. Como se sabe, a convolução e a
diferenciação são associáveis e a Gaussiana separável,
dessa forma pode-se efetuar, a princípio, a suavização da
imagem com o filtro de suavização Gaussiano, usando
filtragem separável. O resultado será uma matriz de dados
S[i, j], onde:
S[i, j] = G[i, j, σ ] * I[i, j] (37)
e σ é o desvio padrão da Gaussiana e controla o grau de
suavização.
Esta etapa, por ser uma bastante usual, não requer
uma explicação mais aprofundada.
O gradiente da matriz suavizada S[i, j] pode ser
então computado por uma máscara 2x2 de aproximações
de primeira-diferença, para produzir duas matrizes de
derivadas parciais P[i, j], derivada em x, e Q[i, j],
derivada em y (Jain, 1995):
 ou
P[i, j] ≅ (S[i, j+1] - S[i, j] + S[i+1, j+1] - S[i+1, j])/2
(38)
 ou
Q[i, j] ≅ (S[i, j] - S[i+1, j] +S[i, j+1] - S[i+1, j+1])/2
(39)
onde * denota a convolução.
As diferenças finitas tem sua média efetuada
através das máscaras 2x2, mostradas acima, tal que, as
derivadas parciais são computadas em pontos de mesmas
coordenadas. A magnitude e orientação do gradiente são
computadas por fórmulas de conversão de coordenadas
retangulares para polar:
22 ]j,i[Q]j,,i[P]j,i[M += (40)
])j,i[P],j,i[Qarctan(]j,i[ =θ (41)
onde a função arco-tangente toma duas componentes, em
y e em x, e gera o ângulo da direção do gradiente.
Sabendo-se que pontos de borda são máximos no
resultado da filtragem, pode-se então, selecionar estes
pontos e obter uma melhor localização para a borda
através da técnica de supressão não máxima. A supressão
não máxima é o anulamento de pixels cujos valores não
são máximos locais, em perfis limitados, na direção
perpendicular à borda, ou seja, busca-se, na direção do
gradiente da imagem, por valores de pixels que são
máximos locais.
A matriz de magnitudes da imagem M[i, j] terá
valores maiores onde o gradiente é maior, porém, este
fato não é suficiente para identificar as bordas. Note que
bordas são caracterizadas por mudanças bruscas no nível
de brilho, logo, encontrá-las implica em encontrar locais
onde a magnitude de M[i, j] é um máximo local. Para
identificar bordas, os cumes largos da matriz M[i, j]
precisam ser afinados, tal que, somente a magnitude em
pontos de grande intensidade permaneçam.
A figura 6 ilustra o caso onde o pixel central (c, l)
é examinado. O valor de (c, l) é um máximo local e a
direção do gradiente é de 45º.
Neste caso, supondo que uma máscara 3x3
percorre M[i, j] e compara a magnitude do gradiente do
pixel central (c, l) com a magnitude de seu vizinho no
sentido do gradiente (c+1, l-1) e com a magnitude de seu
vizinho no sentido contrário ao do gradiente (c-1, l+1),
verifica-se que os pixels em cinza terão seus valores
igualados a zero.
P[i, j] ≅ 1/2 x * S[i, j]
Q[i, j] ≅ 1/2 x * S[i, j]
Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002.
G. Vale; A.. Dal Poz
Figura 6 - Esquema de supressão não máxima quando a
direção do gradiente é de 45º.
A supressão não máxima, então, afina os cumes de
magnitude do gradiente em M[i, j], pela supressão de
todos os valores ao longo da linha do gradiente que não
são valores pico dos cumes.
O algoritmo começa por limitar o ângulo θ [i, j] do
gradiente em um dos quatro setores da figura 7:
])j,i[(Setor]j,i[ θ=ζ (42)
Figura 7 –Setores considerados para a supressão não
máxima
Esta forma de distribuição de setores é proposta
em Jain (1995) e tem como objetivo classificar ângulos
intermediários do gradiente por setores, visto que, na
prática, pixels vizinhos do pixel de referência estarão em
um destes quatro setores.
Estabelecidos os setores, uma máscara 3x3 é
passada, de modo que seja feita a comparação do pixel
central M[i, j], ao longo da linha do gradiente,
comparando-o com seu dois vizinhos, de acordo com o
setor ]j,i[ζ determinado.
Se a magnitude do elemento examinado M[i, j] não
for maior que a de seus vizinhos, ao longo da linha do
gradiente, então M[i, j] recebe zero de magnitude. Este
processo afina de modo geral os cumes até a espessura de
um pixel. Assim, considerando esta etapa tem-se:
])j,i[],j,i[M(snm]j,i[N ζ= (43)
onde N[i, j] denota o processo de supressão não máxima.
Os valores não nulos em N[i, j] correspondem a picos em
M[i, j].
Apesar da filtragem Gaussiana suavizar a imagem
inicialmente, N[i, j] conterá muitos fragmentos de falsas
bordas causadas por ruídos e detalhes de textura. O
contraste dos fragmentos de falsas bordas é pequeno e,
como já foi discutido anteriormente, pode-se pensar em
eliminar detalhes espúrios por meio de uma limiarização
aplicada em N[i, j], ou seja, os valores N[i, j] abaixo do
limiar serão mudados para zero.
Mesmo com a aplicação da limiarização, falsas
bordas ainda ocorrerão. A permanência de falsas bordas,
após a limiarização de N[i, j], pode ter como motivo a
escolha de um limiar τ baixo (falso positivo) e/ou pela
ocorrência de porções de contorno real que podem ter
sido perdidos (falso negativo) devido à suavização do
contraste da borda por uma sombra ou devido à escolha
de um limiar τ alto demais. A escolha do correto limiar é
difícil e envolve tentativa e erro.
Um esquema de limiarização eficaz, como foi
visto, envolve o uso de histerese, que consiste na
limiarização com dois limiares 1τ e 2τ , com
1τ ≅ 2 2τ ou 1τ ≅ 3 2τ .
Aplica-se a limiarização duas vezes, em N[i, j],
uma com 1τ e outra com 2τ , e se obtém,
respectivamente, duas imagens limiarizadas T1 [i, j] e
T 2 [i, j]. Dessa forma T 1 conterá poucas falsas bordas,
porém poderá ter falhas de contorno (falsos negativos). O
algoritmo de dupla limiarização liga bordas por curvas.
Quando o algoritmo encontra o fim de um
contorno em T 1 ele busca em T 2 , através de uma
vizinhança-de-8, por as bordas que podem ser ligadas ao
contorno em T 1 . O algoritmo continua a completar
bordas de T1 a partir de pontos buscados em T 2 até que
descontinuidades de bordas de T1 tenham sido eliminadas
ou que não hajam pontos em T2 que possam ser
aproveitados. O algoritmo efetua a complementaçãodas
bordas como um subproduto do histerese e soluciona
alguns problemas da escolha de limiar.
O algoritmo do Operador de Canny fica:
1. Ler a imagem I[i, j] a ser processada;
2. Criar uma máscara de suavização Gaussiana
G[i, j, σ ] para convoluir com a imagem de
entrada I[i, j]. O desvio padrão desta
Gaussiana é um parâmetro para o detetor de
borda;
3. Usar aproximações de diferenças finitas
(equações 38 e 39) para se obter as derivadas
parciais sobre a imagem suavizada e compute
a magnitude M[i, j] e orientação do gradiente
θ [i, j](equações 40 e 41);
4. Aplicar a supressão não máxima na magnitude
do gradiente (equação 43);
5. Usar o algoritmo de histerese para detectar e
efetuar a complementação das bordas (síntese
de feição); e;
00
1
1 3
2
2
3
90º
135º
180º
225º
270º
315º
0º
45º
c -1 c c +1
l - 1
 l
l+1
Direção da
Borda
M[i, j]
Direção do
Gradiente
Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002.
G. Vale; A.. Dal Poz
6. Armazenar/visualizar as borda detectadas.
7 EXPERIMENTO E AVALIAÇÃO
Nesta subseção são apresentados alguns relutados
e a avaliação do processo de detecção de bordas. Os
resultados obtidos foram gerados através de um programa
de computador em linguagem C.
Figura 8 – Imagem de sintética
Figura 9 – Detecção efetuada com σ =1
Figura 10 – Detecção efetuada com σ =3
A detecção foi efetuada em uma imagem sintética
(figura 8) e em uma imagem real (figura 11). De acordo
com a teoria de Canny, os limiares foram mantidos fixos,
sendo que o maior limiar corresponde a 30% da escala de
tons de cinza e o maior limiar corresponde a 80%. O
desvio-padrão da Gaussiana utilizada para suavização
variou, sendo que os valores utilizados foram: σ = 1 nas
figuras .9 e 12 e σ = 3, nas figuras 10 e 13. A imagem
sintética foi feita no software Paint Shop Pro™ e nela foi
adicionado 25% de ruído.
Figura 11 – Imagem de sintética
Figura 12 – Detecção efetuada com σ =1
Figura 13 – Detecção efetuada com σ =3
Anais do Simpósio Brasileiro de Geomática, Presidente Prudente - SP, 9-13 de julho de 2002.
G. Vale; A.. Dal Poz
Tanto na detecção com a imagem sintética como
na detecção com a imagem real, pode-se ver nitidamente
que quanto maior o desvio-padrão menor a quantidade de
bordas espúrias. É necessário, no entanto, se tomar
cuidado com o σ adotado na suavização pois, se for
muito alto haverá um borramento das bordas e,
consequentemente, um decréscimo na localização e
detecção. Os resultados do detetor, em ambos os casos,
mostrou-se satisfatório. Verifica-se que em todas as
imagens, mesmo aquelas detectadas com alto σ ,
praticamente não houve fragmentação das bordas, o que,
comprova a eficácia do "processo de completar bordas"
com os resultados do histerese. O detetor também se
mostrou eficiente na localização das bordas. Tal
desempenho é devido à supressão não máxima, que reduz
as bordas a um pixels de espessura.
8 CONSIDERAÇÕES FINAIS
Ao se utilizar um detetor de bordas, espera-se que,
a partir de seu resultado final, se possa encontrar os
objetos de interesse com pouco esforço computacional,
com baixa probabilidade de ambigüidade e com nível
satisfatório de acurácia.
De acordo com os exemplos analisados, verificou-
se que o processo de detecção de bordas de Canny
mostrou-se bastante flexível, independente da origem da
imagem utilizada. Mesmo visualmente, pode-se verificar
que a fragmentação das bordas relevantes da imagem foi
minimizada, mesmo com o uso de um alto σ . Tal fato
pode ser atribuído ao comportamento satisfatório do
processo de histerese. Cabe lembrar que, mesmo sendo
robusto e eficiente ao detectar bordas, o operador de
Canny ainda está suscetível aos efeitos indesejáveis da
suavização Gaussiana. No entanto, se σ é adotado de
modo coerente, i. e., estimado a partir da quantização do
ruído o balanceamento entre detecção e localização
propicia uma resultado de ótima qualidade.
Por último, vale ressaltar que a supressão não
máxima combinada com a histerese permite obter
informações de contorno com alta qualidade e riqueza de
detalhes, o que certamente beneficia as etapas
subsequentes de qualquer processo automático ou semi-
automático de extração de feições cartográficas em
imagens digitais.
AGRADECIMENTOS
Os autores agradecem à CAPES, pelo suporte, sob
a forma de bolsa de Demanda Social CAPES, concedida
ao mestrando Giovane Maia do Vale a partir de 1 de maio
de 2001.
REFERÊNCIAS
BUTKOV, E. Física Matemática. St. Jhns's University,
New York - Editora Guanabara S. A. - pp. 224 - 239,
1968.
CANNY, J. A Computational Approach to Edge
Detection. IEEE Transactions on Pattern Analysis and
Machine Intelligence, V. 8, n. 6, pp. 679-698, 1986.
GOMES J., VELHO L. Computação Gráfica: Imagem.
Série de Computação e Matemática. IMPA/SBM, Rio de
Janeiro, 424 p, 1994.
JAIN, R.; Kasturi, R; Schunck, B. G. Machine Vision.
MIT Press and McGraw-Hill, Inc New York – 1995
LIM, Jae S. Two-dimensional signal and image
prossecing. Department of Engineering and Computer
Science Massachusetts Institute of Technology - Pentice
Hall PTR - 1990.
PARKER, J. R. Algorithms for Image Processing and
Computer Vision. John Wiley & Sons, Inc., New York,
417p, 1997.
ZIOU D., TABBONE S. Edge Detection Techniques -
An Overview. International Journal of Pattern
Recognition and Image Analysis,Vol. 8, No. 4, pp. 537-
559, 1998. also Technical Report, No. 195, Dept. Math. et
Informatique, Université de Sherbrooke, 41 pages, 1997.