Deteccao de Arestas em Imagens Digitais

Helder C. R. de OliveiraOrientador: Prof. Marco A. Piteri

Presidente Prudente2011

Sumario

1 Introducao 1

2 Processamento de Imagens e Deteccao de Arestas 32.1 O que sao as Arestas? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Modelos de Arestas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Abordagem Algorıtmica 83.1 Algoritmo de Marr e Hildreth . . . . . . . . . . . . . . . . . . . . . . . . . 123.2 Algoritmo de Canny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3 Algoritmo de Shen e Castan . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4 Ambiente de Desenvolvimento 234.1 Ferramentas Utilizadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.2 Prototipo Desenvolvido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5 Conclusao 28

i

Lista de Figuras

2.1 Relacionamento as areas da Computacao Grafica, Processamento de Ima-gens e Visao Computacional. . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Destaque de um pixel em uma imagem. . . . . . . . . . . . . . . . . . . . . 42.3 Modelos de arestas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.4 Aresta em uma imagem (a esquerda) e suas derivadas de primeira e segunda

ordem (a direita). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.1 Vetor gradiente (∇f(x, y)) formando um angulo α com o eixo x. . . . . . . 93.2 Mascaras unidimensionais utilizadas para implementar as Equacoes 3.4 e 3.5. 93.3 Modelo base para mascaras 3D. . . . . . . . . . . . . . . . . . . . . . . . . 103.4 Mascaras 2D de Prewitt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.5 Mascaras 2D de Sobel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.6 Mascaras 2D de Sobel para deteccao de arestas nas diagonais. . . . . . . . 113.7 Mascaras 2D de Prewitt para deteccao de arestas nas diagonais. . . . . . . 123.8 Resultados da aplicacao do operador de Sobel. . . . . . . . . . . . . . . . . 123.9 Grafico da funcao LoG mostrada em 3.13, tambem conhecida como “som-

brero” ou “chapeu mexicano”. . . . . . . . . . . . . . . . . . . . . . . . . . 143.10 Vista em corte do grafico da funcao LoG. . . . . . . . . . . . . . . . . . . . 143.11 Mascara 5× 5 referente a funcao LoG. . . . . . . . . . . . . . . . . . . . . 153.12 Resultados obtidos com algoritmo de Marr-Hildreth utilizando diferentes

valores de desvio padrao σ. . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.13 Intervalo de valores mostrando um α para uma aresta horizontal. . . . . . 173.14 Resultado obtido com o algoritmo de Canny. . . . . . . . . . . . . . . . . . 203.15 Resultado obtido com o algoritmo de Shen e Castan. . . . . . . . . . . . . 22

4.1 Interface do prototipo do sistema. . . . . . . . . . . . . . . . . . . . . . . . 254.2 Partes da interface principal. . . . . . . . . . . . . . . . . . . . . . . . . . . 264.3 Entradas do menu Ferramentas. . . . . . . . . . . . . . . . . . . . . . . . . 27

ii

Capıtulo

1

Introducao

Com o crescente uso da tecnologia, cada vez mais o homem tem buscado tecnicas parareproduzir a visao humana em maquinas. Essas tecnicas visam fazer com que as maquinaspossam identificar em qual ambiente se encontram, juntamente com os objetos que estaoem tais ambientes.

Neste sentido, o processamento de imagens digitais tem se mostrado um amplo campode pesquisa, no qual utilizamos tecnicas para destacar objetos ou partes de uma imagembaseado em sua mudanca de cor ou textura. Tudo isso para que depois o computadorpossa distinguir e identificar o que se encontra na imagem.

Diversas areas tem se beneficiado com o processamento de imagens independente docampo de atuacao, dentre as mais variadas podemos citar, a medicina, o sensoriamentoremoto e os sistemas de vigilancia.

A medicina e uma das areas que mais utiliza o processamento de imagens nos diasatuais, pois tem se tornado cada vez mais comum a analise de uma imagem obtida pormeio de raio x, ultrassonografia, tomografia ou ressonancia magnetica, onde o resultado eum pre-diagnostico feito pelo computador. Podemos citar tambem as areas da oncologiae da ortopedia que se beneficiam cada vez mais com esse tipo de procedimento. Ematividades laboratoriais nas quais e necessario fazer uma contagem de celulas, tambem eusado como tarefa de pre-processamento da imagem microscopica, a deteccao de arestascomo uma parte imprescindıvel da contagem como um todo.

O sensoriamento remoto e outra grande area que tem se desenvolvido com a ajuda desoftwares especıficos para a analise de imagens de satelite por exemplo. Baseado nessasimagens estes softwares podem estimar a metragem total de uma area desmatada, a areade uma floresta que foi atingida por uma queimada, uma estimativa de desmatamento,ou ate mesmo uma estimativa da quantidade de area plantada de determinada cultura.

A area de vigilancia (seguranca) tambem tem se beneficiado com os avancos do pro-cessamento de imagens. E comum encontrarmos sistemas de vigilancia compostos porcameras que identificam em tempo real objetos “suspeitos” que possam estar sendo car-regados. Com isso tambem se tem o reconhecimento facial, onde a camera pode dar uma“atencao especial” ao rosto do indivıduo, fazendo com que o foco da imagem seja ajustadonessa regiao.

Baseando-se em todas as “poucas” aplicacoes que citamos anteriormente, e possıvelafirmar com toda a certeza que a deteccao de arestas e muitas vezes uma das primeirastarefas a ser feita no processamento de uma imagem. E claro que existem ainda incontaveisoutras aplicacoes que envolvem, e dependem, totalmente de uma boa deteccao de arestas

1

para que todo o processo proposto (em qualquer que seja a area de aplicacao) possa serlevado a diante com uma certa confiabilidade e seriedade.

No Capıtulo 2 iremos fazer uma explicacao de como funciona o processamento deimagens e o que sao as arestas. Discutiremos sobre como uma imagem e vista do pontode vista computacional de modo a possibilitar o processamento da mesma. Tambemveremos os tipos de processamento nos seus nıveis alto, medio e baixo. Ainda nesteprimeiro capıtulo explicamos o que sao as arestas e quais sao os tipos de arestas comumenteencontradas nas imagens. Ainda nesse capıtulo, falaremos a respeito das imagens digitaise como sao as arestas, apos isso, entramos no nosso principal assunto que e a deteccao dearestas. Faremos uma breve descricao de como e feita a deteccao das arestas utilizandoprimeiramente operadores basicos como o de Sobel e o de Prewitt.

Depois dos operadores basicos, no Capıtulo 3 nos elevamos o nıvel de complexidadeseguindo uma cronologia sistemica ao tratar os algoritmos de Marr e Hildreth, que seraoseguidos pelo algoritmo de Canny e por fim tratamos do algoritmo de Shen e Castan.

A discussao do prototipo do sistema desenvolvido e feita no Capıtulo 4, onde mostra-mos algumas partes de sua interface grafica e tambem explicamos suas funcionalidades.Tambem comentamos as bibliotecas que foram usadas e ressaltamos a importancia de taisferramentas no cenario mundial do desenvolvimento de software.

No capıtulo de conclusao fazemos um comentario sobre tudo o que foi apresentado, doprimeiro ao ultimo capıtulo e, depois citamos alguns trabalhos que sao pertinentes paradar continuidade e quais trabalhos que tem como base, ou seja, quais trabalhos que temcomo uma das principais e primeiras tarefas, a deteccao de arestas.

2

Capıtulo

2

Processamento de Imagens e Deteccao deArestas

O Processamento de Imagens e a area onde a informacao a ser tratada esta inicialmenteem algum formato grafico. Essa imagem de entrada e processada e as informacoes saoextraıdas, ficando tambem em formato de imagem. Um pouco diferente do processamentode imagens e a Visao Computacional, onde os dados de entrada estao no formato deimagem, e apos o seu processamento, eles ficam dispostos em outro formato, por exemploem texto, como e o caso do Reconhecimento Optico de Caracteres. Por outro lado temosa Computacao Grafica, onde inicialmente os dados estao dispostos em algum formato, eapos seu processamento, eles ficam em formato de imagem.

A relacao entre as areas de Processamento de Imagens, Visao Computacional e Com-putacao Grafica, estao melhor dispostas na Imagem 2.1 onde mostramos graficamente orelacionamento entre elas.

imagem

visao computacional computacao grafica

informacao

processamento de imagem

Figura 2.1: Relacionamento as areas da Computacao Grafica, Processamento de Imagense Visao Computacional.

A representacao e manipulacao de uma imagem no computador requer a definicao deum modelo matematico adequado da imagem.

3

Uma imagem pode ser definida como uma funcao de intensidade luminosa, denotadapor uma funcao f(x, y) com f : <2 → <, cujo valor ou amplitude nas coordenadasespaciais (x, y) fornecem a intensidade ou o brilho da imagem (nıvel de cinza) naqueleponto.

Notamos que uma imagem digital e composta por um numero finito de elementoschamados de pixel (juncao das palavras Picture e Element - Elemento de Imagem). Umpixel e a menor unidade de representacao de uma imagem, possuindo uma localizacao((i, j) ∈ f(x, y)) e valores especıficos. Sendo assim, uma imagem pode ser representada(vide Imagem 2.2) por meio de uma matriz bidimensional, na qual cada elemento damatriz corresponde a um pixel da imagem.

pixel

..

.

..

.

..

.

...

...

...

...

..

.

..

.

...

Imagem

Figura 2.2: Destaque de um pixel em uma imagem.

Algumas vezes, o processamento de imagens e definido como uma area na qual tanto aentrada quanto a saıda de um processo sao imagens. Essa definicao e um tanto restritiva e,de certa forma artificial. Por exemplo, nessa definicao, a tarefa de calcular a intensidademedia de uma imagem (que resulta em um unico numero) nao seria considerada umaoperacao de processamento de imagens. Por outro lado, existem campos como o da visaocomputacional, cuja meta e utilizar computadores para simular a visao humana, incluindoo aprendizado e a capacidade de tomar decisoes agindo com base em informacoes visuais.

Se tomarmos uma linha contınua, onde em uma ponta esta o processamento de imagense em outro esta a visao computacional, vamos notar que nao existe um limite claro entreum e outro. Porem, para termos uma base seria util considerar tres tipos de processoscomputacionais nessa linha contınua:

Processos de Baixo Nıvel: Nestes processos podemos categorizar as operacoes primiti-vas como o pre-processamento de imagens, operacoes como reducao de ruıdos, realcede contraste, agucamento de imagens, entre outras. Um processo de nıvel baixo edefinido pelo fato de tanto a entrada quanto a saıda serem imagens;

Processos de Medio Nıvel: Aqui podemos citar a operacao de segmentacao (divisaoda imagem em regioes ou objetos, distintos), a descricao desses objetos para umaclassificacao (reconhecimento) posterior. Um processo de nıvel media e definido porgeralmente a entrada ser uma imagem e a saıda serem informacoes que sao extraıdasda imagem;

Processos de Alto Nıvel: Estes processos envolvem em o “dar sentido” aos objetos queforam reconhecidos.

4

Com base nos itens citados anteriormente, vemos que existe um ponto comum entre oprocessamento e a analise de imagens e o reconhecimento de regioes ou objetos em umaimagem.

2.1 O que sao as Arestas?Uma aresta e um conjunto de pixels conectados localizados no contorno ou borda entreduas regioes. Muito se confunde borda com aresta. A borda de uma regiao finita formaum caminho fechado e e, portanto um conceito global, enquanto a aresta e formada porpixels onde ocorre uma grande variacao de intensidade de cor na imagem e e, portanto,um conceito local.

A deteccao das arestas em uma imagem, ocorre quando existe uma grande variacaonos tons de cinza e quanto maior for essa variacao, mais facilmente ela sera detectada,exceto no caso ideal, onde qualquer que seja a variacao, a deteccao sera feita.

Matematicamente a intensidade de mudanca a respeito de uma distancia e conhecidacom sendo a primeira derivada de uma funcao, portanto e admissıvel o uso das derivadaspelos mais diversos detectores de arestas, como pode ser visto no Capıtulo 3.

2.2 Modelos de ArestasOs modelos de arestas sao classificados de acordo com a distancia da variacao de inten-sidade. O modelo no qual ocorre essa variacao com a distancia de 1 pixel e chamadode aresta em degrau, ocorrendo, por exemplo, em imagens geradas para o uso em areascomo a modelagem de solidos e animacoes. A Figura 2.3(a) mostra um exemplo destemodelo e o seu perfil horizontal de intensidade. Ele e considerado um modelo limpo eideal, pois a mudanca de intensidade com a distancia de 1 pixel ocorre de modo natural,sem a necessidade de qualquer processamento adicional como por exemplo a suavizacao,para faze-las aparecer. As arestas em degrau sao utilizadas frequentemente como modelospara o desenvolvimento de metodos que automatizem a deteccao de arestas, o algoritmode Canny (Secao 3.2) e um exemplo.

No mundo real, as imagens digitais possuem arestas que sao desfocadas ou possuemruıdos. Nessas arestas o grau de indefinicao esta determinado pelos mecanismos de focali-zacao como por exemplo lentes (no caso de imagens oticas) e o nıvel de ruıdo e determinadoprincipalmente pelo componente eletronico do sistema de imagens ou seja, ruıdos podemtambem ocorrer durante o processo de transferencia de uma imagem de um local (com-putador) para outro. Nessas situacoes, as arestas sao classificadas por apresentarem umperfil de rampa na sua variacao de intensidade, um exemplo desse modelo e mostrado naFigura 2.3(b). A inclinacao da rampa e inversamente proporcional ao grau de definicaoda aresta, [1]. Como podemos notar, nesse modelo nao existe mais uma aresta fina ondea sua variacao possui uma distancia de 1 pixel. Ao inves disso, temos uma distancia bemmaior, e um ponto de aresta e qualquer ponto contido na rampa, e um segmento de arestasera o conjunto conectado dos pontos que estao na rampa.

Um outro modelo de aresta e o que chamamos de aresta em forma de telhado tambemconhecido como roof edge. Ela e composta basicamente de apenas uma linha que se destacaao cortar uma determinada regiao da imagem. Se esta aresta possui uma distancia (essadistancia e o comprimento entre os dois lados que a cercam) mınima (1 pixel), esta nadamais e do que uma linha com 1 pixel de espessura que atravessa determinada regiao daimagem. Ilustramos esse tipo de aresta na Figura 2.3(c).

Essa forma de telhado, surge normalmente em imagens em profundidade, por exemplo.Em casos onde existem objetos que esta mais proximos do sensor do que o seu fundo.Outras imagens que apresentam esse tipo de aresta aparecem tambem em imagens de

5

2.2 Modelos de Arestas

(a) Degrau. (b) Rampa. (c) Telhado.

Figura 2.3: Modelos de arestas.

satelite, onde estradas podem ser modeladas por esse tipo de borda.Nao e difıcil encontrar imagens que possuam os tres modelos mencionados na Figura

2.3. Porem, a alteracao das formas ideais sao frutos do borramento e do ruıdo. No en-tanto, uma imagem que contem uma quantidade moderada de ruıdos possuem arestas queestao bem proximas das arestas ilustradas. O que podemos fazer e construir expressoesmatematicas baseadas nos modelos que foram apresentados, e com isso desenvolver algo-ritmos para as bordas. O desempenho dos algoritmos desenvolvidos depende diretamentedo quao diferente e a borda da imagem real em relacao aos modelos mostrados.

passagem por zero

horizontal

primeira derivada

segunda derivada

(b)

perfil de intensidade

(a)

Figura 2.4: Aresta em uma imagem (a esquerda) e suas derivadas de primeira e segundaordem (a direita).

A Figura 2.4(a) nos mostra uma aresta parecida com o modelo da Figura 2.3(b). NaFigura 2.4 (b) temos o perfil da intensidade horizontal da aresta em (a). Nesta mesmafigura mostramos tambem o comportamento das derivadas de primeira e segunda ordem doperfil de intensidade. Analisando o perfil de intensidade em forma de rampa (da esquerdapara a direita) podemos notar que no inicio da rampa e em determinados pontos delaa sua primeira derivada e positiva e, nas areas onde temos a intensidade constante, suaprimeira derivada e zero. A segunda derivada como podemos observar e positiva no inıcioda rampa e zero no final dele, mas logo depois do inicio da rampa a segunda derivadapassa a ser zero, voltando a ser positiva apenas no final da rampa e retornando a ser zerodepois do final da rampa. A borda que analisamos vai do escuro para o claro. Se uma

6

2.2 Modelos de Arestas

borda vai do claro para o escuro, e natural que os sinais das derivadas sejam invertidos.O ponto onde ocorre a interseccao entre o eixo de intensidade zero e a linha que vai oextremo (intensidade maxima) da segunda derivada, e chamado de cruzamento por zeroda segunda derivada.

Portanto, com base nas informacoes discutidas anteriormente, a magnitude (grandeza)da primeira derivada em um determinado ponto pode ser usada para verificar se o pontopertence ou nao a aresta. Sendo assim, podemos fazer uso do sinal da segunda derivadapara saber se determinado pixel esta do lado escuro ou claro da borda. E possıvel notarmostambem outras duas propriedades em relacao a derivada de segunda ordem:

1. Tem como resultado dois valores para cada aresta (esta caracterıstica nao e impor-tante);

2. Os cruzamentos por zero podem ser uteis quando se pretende achar o centro daborda.

Apesar de termos analisado apenas perfis de arestas de 1D, a mesma ideia e aplicadapara diversas orientacoes da imagem. Basta definirmos um perfil perpendicular, em umponto qualquer, na direcao da aresta e depois analisar os resultados assim como fizemosanteriormente.

7

Capıtulo

3

Abordagem Algorıtmica

Neste capıtulo iremos abordar alguns algoritmos dos detectores de arestas. Para isso,iremos iniciar fazendo uma explanacao sobre o que sao os detectores e quais criterios foramlevados em conta no desenvolvimento de um, em seguida, mostramos detalhadamente osoperadores de Sobel e o de Prewitt, que fizeram parte dos primordios dos detectores dearestas, e depois entramos nos algoritmos mais robustos. O primeiro deles foi desenvolvidopor Marr e Hildreth, o segundo por Canny, e o terceiro e ultimo algoritmo por Shen eCastan

Os detectores de arestas sao metodos de processamento de imagem local desenvolvidospara detectar os pixels que estao na aresta. Uma linha pode ser vista como uma arestaem que a intensidade do fundo de cada lado da linha ou e muito superior ou muito inferiora intensidade dos pixels da aresta.

Em geral os passos fundamentais que sao considerados na deteccao de uma aresta sao:

Suavizar a imagem para reduzir o ruıdo: A segunda derivada de um ponto qual-quer da imagem e muito sensıvel a ruıdos. Se uma imagem possui ruıdos em grandequantidade, pode ser quase impossıvel detectar suas arestas;

Deteccao dos pontos da aresta: Esta e uma operacao que ocorre localmente na ima-gem e que determina os pontos candidatos a serem pontos da aresta;

Localizacao da aresta: Esta operacao retira os pontos (falsos candidatos) que nao per-tencem a aresta, deixando apenas os que realmente a pertencem.

O metodo ideal para encontrar a intensidade e a direcao da aresta em uma posicao(x, y) de uma imagem f , e o vetor gradiente (∇f), definido pela Equacao 3.1.

∇f = grad(f) =

[gxgy

]=

∂f

∂x

∂f

∂y

(3.1)

A propriedade geometrica do vetor gradiente e apontar o sentido da maior variacaoda imagem f no ponto (x, y). A magnitude (tamanho ou valor da taxa de variacao) dovetor gradiente (∇f), sera chamado de M(x, y), e e dado pela Equacao 3.2.

M(x, y) = mag(∇f) =√g2x + g2y (3.2)

8

Na Equacao 3.2, as imagens que quando combinadas resultam em M(x, y) (tambemchamada de imagem gradiente), sao g2x e g2y , elas possuem o mesmo tamanho que a imagemoriginal, pois sao criadas no momento em que x e y assumem todos os valores dos pixelsde f .

A direcao para onde o vetor gradiente, de determinado ponto (x, y) aponta, e dadopelo angulo α em relacao ao eixo x, a Imagem 3.1 ilustra esse fato.

x

α

y

(x, y)

∇(x, y)

Figura 3.1: Vetor gradiente (∇f(x, y)) formando um angulo α com o eixo x.

Na Equacao 3.3 temos a representacao de como α e definido matematicamente.

α(x, y) = tg−1[gygx

](3.3)

Assim como a imagem da magnitude (Equacao 3.2), α(x, y) e tambem uma imagemque possui o mesmo tamanho da imagem original, pois ela foi criada pela divisao doarranjo das imagens gy e gx. Entao, a direcao de uma aresta em um ponto qualquer (x, y)e ortogonal a direcao, α(x, y), do vetor gradiente.

Para calcular o gradiente de uma imagem, vimos na Equacao 3.1, que e necessariocalcular as derivadas parciais ∂f

∂xe ∂f∂y

em todos os pontos da imagem. Uma discretizacaodas derivadas parciais nas vizinhancas de um ponto, e dada por:

gx =∂f(x, y)

∂x= f(x+ 1, y)− f(x, y) (3.4)

gy =∂f(x, y)

∂y= f(x, y + 1)− f(x, y) (3.5)

As equacoes anteriores sao validas para todos os valores de x e y da imagem filtrando-acom as mascaras unidimensionais mostradas na Figura 3.2.

−1

1

(a)

−1 1

(b)

Figura 3.2: Mascaras unidimensionais utilizadas para implementar as Equacoes 3.4 e 3.5.

Se o objeto que nos interessa e uma aresta inclinada, entao iremos precisar de umamascara 2D. Mascaras 2 × 2 sao simples do ponto de vista conceitual, porem nao sao

9

tao eficientes para calcular a direcao de uma aresta se comparadas com mascaras que saosimetricas ao redor de um ponto e, assim, possuem mais informacoes a respeito da direcaode uma aresta. As aproximacoes mais simples para as derivadas parciais que fazem usode mascaras de tamanho 3× 3 que sao definidas a seguir:

gx =∂f

∂x= (z7 + z8 + z9)− (z1 + z2 + z3) (3.6)

gy =∂f

∂y= (z3 + z6 + z9)− (z1 + z4 + z7) (3.7)

z7

z1 z2 z3

z4 z5 z6

z8 z9

Figura 3.3: Modelo base para mascaras 3D.

Os valores de z utilizados nas Equacoes 3.6 e 3.7 sao especificados na imagem 3.3.Essas equacoes poder ser executadas de modo que x e y assumam todos os valores daimagem, filtrando entao f com as duas mascaras (chamadas de operadores de Prewitt)mostradas nas Figuras 3.4(a) e 3.4(b). Na Equacao 3.6, a diferenca explicitada da regiao3 × 3 faz com que a derivada se aproxime na direcao do eixo x, e a que foi mostrada naEquacao 3.7 faz com que a derivada se aproxime do eixo y.

1

−1 −1 −1

0

1

0 0

1

(a)

−1

0

1

−1

−1

0

1

1

0

(b)

Figura 3.4: Mascaras 2D de Prewitt.

Uma variacao das Equacoes 3.6 e 3.7 faz uso do valor 2 como peso no centro docoeficiente, ficando entao da maneira mostrada nas Equacoes 3.8 e 3.9. O resultadodesta modificacao, causa uma suavizacao na imagem. Como foi feita uma mudanca nasequacoes, e natural que as mascaras tambem sofram alteracoes. As novas mascaras saochamadas de operadores de Sobel e sao mostradas nas Figuras 3.5(a) e 3.5(b).

gx =∂f

∂x= (z7 + 2z8 + z9)− (z1 + 2z2 + z3) (3.8)

gy =∂f

∂y= (z3 + 2z6 + z9)− (z1 + 2z4 + z7) (3.9)

10

0

1

0

1

0

2

−2−1 −1

(a)

0

1

−1

−2

−1

0

2

0

1

(b)

Figura 3.5: Mascaras 2D de Sobel.

Como podemos ja prever, as mascaras de Sobel sao as mais usadas, pois, elas possuemuma melhor reducao de ruıdos, e isso e importante quando estamos trabalhando comderivadas. Veja que a soma dos coeficientes das mascaras, mostradas nas Imagens 3.5 e3.4 vao resultar em zero, esta e uma resposta esperada quando se trabalha com intensidadeconstante em operadores derivativos.

As duas mascaras vistas anteriormente sao utilizadas para calcular os componentesdo gradiente gx e gy em cada pixel da imagem. As derivadas parciais, correspondentes asmascaras, sao utilizadas para fazer uma estimativa da intensidade e a direcao da borda.No caso do calculo da magnitude do gradiente, e necessario que gx e gy sejam combinadoscomo foi mostrado na Equacao 3.2. Mas esta aplicacao nem sempre e interessante devidoao seu custo computacional. Uma saıda normalmente usada, e aproximar a magnitude dogradiente usando valores absolutos, dado pela Equacao 3.10.

M(x, y) ≈ |gx|+ |gy| (3.10)

A equacao anterior e muito mais “barata” computacionalmente e ainda mantem asmudancas relativas de intensidade. O “preco pago” pela utilizacao dessa abordagem e queos filtros resultantes geralmente nao sao isotropicos, ou seja, nao variam com a rotacao.Mas esse nao e um problema quando sao usadas as mascaras de Sobel e de Prewitt paracalcular gx e gy, pois essas mascaras resultam em filtros isotropicos apenas em arestasverticais e horizontais. Os resultados seriam isotropicos somente para arestas nessas duasdirecoes, independente das equacoes utilizadas. Contudo, as Equacoes 3.2 e 3.10 produzemo mesmo resultado para as bordas tanto verticais quanto horizontais quando sao usadasas mascaras de Sobel ou de Prewitt.

E possıvel alterar as mascaras 3× 3 mostradas nas Figuras 3.5 e 3.4 fazendo com queas suas respostas tenham “peso” ao longo das diagonais. Essas alteracoes sao ilustradasnas Figuras 3.6 e 3.7, onde mostramos respectivamente as mascaras adicionais de Sobel ePrewitt que sao utilizadas para a deteccao de arestas nesse sentido.

0−1 1

0 1 2

0−1−2

(a)

0−1 1

0

−1−2 0

21

(b)

Figura 3.6: Mascaras 2D de Sobel para deteccao de arestas nas diagonais.

11

0

0

−1

1 1

1

0−1−1

(a)

0−1 1

−1 0

0 1 1

−1

(b)

Figura 3.7: Mascaras 2D de Prewitt para deteccao de arestas nas diagonais.

As imagens ilustradas na Figura 3.8 mostram os resultados do operador de Sobel emdiferentes situacoes. Essa Imagem 3.8(a), foi escolhida devido ao seu conteudo compostopor objetos na posicao vertical e horizontal, essa peculiaridade faz com que fique bemevidente a aplicacao do operador em cada um dos eixos. Em 3.8(b) o operador foi aplicadoapenas para os valores de x e na Imagem 3.8(c) apenas para os valores de y. Por fim,temos a Imagem 3.8(d) onde o operador foi aplicado tanto em x quanto em y, ondepodemos notar que o resultado e uma “mescla” das imagens resultante da aplicacao noseixos separados.

(a) Imagem original. (b) Sobel aplicado nos valores de x.

(c) Sobel aplicado nos valores de y. (d) Sobel aplicado nos valores de x e y.

Figura 3.8: Resultados da aplicacao do operador de Sobel.

3.1 Algoritmo de Marr e HildrethO algoritmo de deteccao de arestas de Marr e Hildreth foi motivado pelos estudos bio-logicos do sistema de visao dos mamıferos. Ele foi desenvolvido por David Marr e Ellen

12

3.1 Algoritmo de Marr e Hildreth

Hildreth, e foi uma das primeiras tentativas de deteccao de arestas que usavam tecnicasmais avancadas do que apenas operadores como as mascaras de Sobel. Marr e Hildrethacreditavam que:

• Qualquer mudanca de intensidade na imagem, nao depende de sua escala e, portanto,neste caso a deteccao de arestas requer o uso de operadores de tamanhos diferentes;

• Se houver uma mudanca brusca de intensidade na imagem, ira dar origem a um picoou um vale na primeira derivada ou, um cruzamento por zero na segunda derivada.

As ideias citadas anteriormente sugerem que na deteccao de arestas, o operador usadodeveria ter duas caracterısticas principais: Ele deve ser uma operador diferencial capaz decalcular uma aproximacao discreta da primeira ou da segunda derivada em cada ponto daimagem; e ele deve ser capaz de atuar em qualquer escala desejada, assim, os operadoresgrandes seriam usados para a deteccao de arestas borradas, e os operadores pequenos paradetectar arestas finas.

Marr e Hildreth argumentaram entao que o operador que poderia fazer com que ascondicoes fossem satisfeitas era o filtro ∇2G, tambem chamado de LoG (Laplacian ofGaussian, Laplaciano da Gaussiana), onde o ∇2 e o operador laplaciano mostrado em3.12, e G e a funcao gaussiana 2D, com o desvio padrao σ, mostrada em 3.11.

G(x, y) = e−x2+y2

2σ2 (3.11)

∇2 =∂2

∂x2+

∂2

∂y2(3.12)

Para se chegar ate a funcao ∇2G, e realizado o desenvolvimento mostrado a seguir,partindo das equacoes 3.11 e 3.12.

∇2G(x, y) =∂2G(x, y)

∂x2+∂2G(x, y)

∂y2

=∂

∂x

[−x∂2e−

x2+y2

2σ2

]+

∂

∂y

[−y∂2e−

x2+y2

2σ2

]

=

[x2

σ4− 1

σ2

]e−

x2+y2

2σ2 +

[y2

σ4− 1

σ2

]e−

x2+y2

2σ2

Agrupando os termos semelhantes, chegamos a seguinte equacao:

∇2G(x, y) =

[x2 + y2 − σ2

σ4

]e−

x2+y2

2σ2 (3.13)

Na Figura 3.9 ilustramos o grafico da superfıcie ∇2G mostrada anteriormente. AFigura 3.10 e a vista em corte da Figura 3.9, nela observamos que o cruzamento por zeroda funcao ocorre onde x2 + y2 = 2σ2, o que ilustra um cırculo de raio

√2σ e centro na

origem. Em 3.11 mostramos uma mascara 5×5 que se aproxima da forma da funcao LoG.Essa aproximacao da mascara nao e unica e, ela pode ser substituıda por qualquer outramascara cujo o ponto central seja positivo rodeado por valores negativos que aumentam amedida que se distanciam da origem porem, e necessario que a soma dos coeficientes sejazero para que o valor de saıda da mascara seja zero nos locais de intensidade constante.

13

3.1 Algoritmo de Marr e Hildreth

xy

∇2G

Figura 3.9: Grafico da funcao LoG mostrada em 3.13, tambem conhecida como“sombrero”ou “chapeu mexicano”.

∇2G

Cruzamento por zero

2√

2σ

Figura 3.10: Vista em corte do grafico da funcao LoG.

A ideia por tras do operador ∇2G e que, o uso da funcao gaussiana G ira borrar aimagem fazendo com que os nıveis de intensidade sejam reduzidos (incluindo os ruıdos)para uma escala menor que σ pois, a gaussiana e suave nos domınios espaciais e defrequencia. Apos isso o operador ∇2 e a segunda derivada do filtro usado. A primeiraderivada pode ser utilizada para encontrar mudancas bruscas de intensidade mas, elas saooperadores direcionais. O laplaciano tem a propriedade de ser isotropico (invariante coma rotacao), assim como o sistema de visao humano, e isso e uma vantagem em relacao aouso da primeira derivada.

Em sıntese, o algoritmo de Marr-Hildreth pode ser resumido nos tres seguintes passos:

1. Envolver um imagem original I em uma funcao gaussiana G de duas dimensoes, deacordo com a Equacao 3.14;

2. Calcular a laplaciana da imagem resultante, e chamar isso de L;

3. Encontrar os pixels de L que passam por zero. Esses pixels pertencem as arestas.

No primeiro passo citado anteriormente, o resultado da convolucao com o operadorgaussiano resulta em uma variedade de desvios padroes que sao combinados formandouma unica imagem de aresta portanto, a imagem e suavizada, eliminando entao algunsruıdos. A convolucao em duas dimensoes e mostrada na equacao a seguir:

I ∗G(i, j) =∑n

∑m

I(n,m)G(i− n, j −m) (3.14)

14

3.1 Algoritmo de Marr e Hildreth

0

0

0 -1

-1

-1

-1

-1

-1

0

0000

0

00

0-1

-1

-2

-2 -2

-2

16

Figura 3.11: Mascara 5× 5 referente a funcao LoG.

O proximo passo consiste em calcular a laplaciana da imagem que foi obtida comoresultado do passo anterior, entao, teremos:

L = ∇2[I ∗G(i, j)] (3.15)

Neste caso a ordem de aplicacao dos operadores nao importa, tanto faz aplicar umlaplaciano e logo apos um gaussiano ou aplica-se primeiro um gaussiano e depois umlaplaciano. Para facilitar os calculos, podera ser criada apenas uma equacao baseando-senas duas (3.11 e 3.12), criando entao uma mascara de convolucao podendo ser aplicada aimagem e assim obter o mesmo resultado.

As passagens por zero sao os pontos mais significativos do algoritmo de Marr-Hildreth.Mar notou que elas podem ser detectadas (sem que haja um alto custo computacional)em cada uma das escalas da imagem resultante, no entanto, a sua identificacao nao geracontornos ligados.

No algoritmo que foi implementado, para garantir que uma variedade de escalas sejamusadas, o programa usa duas gaussianas diferentes (e convencional usar duas gaussianasdiferentes), e seleciona os pixels que passam por zero em ambas escalas como sendo ospixels das arestas. O programa necessita de valor σ como parametro de entrada. Eleentao usa σ − 0.8 e σ + 0.8 como valores de desvio padrao, faz as duas convolucoes, elocaliza dois conjuntos de passagem por zero (cada conjunto desse e uma imagem distinta.Uma imagem e com desvio padrao σ − 0.8 e a outra e de desvio padrao σ + 0.8), entao oprograma faz uma uniao dos dois conjuntos onde os pixels que sao comuns as duas imagenssao pixels de aresta e portanto estarao na imagem resultante.

No conjunto de figuras 3.12 mostramos os resultados da aplicacao do algoritmo deMarr e Hildreth na Figura 3.12(a). Para os testes, inserimos no sistema desenvolvido comtres valores distintos de desvio padrao, um com σ = 2, Figura 3.12(b), σ = 3, Figura3.12(c), e por fim σ = 4 que deu origem a Figura 3.12(d).

3.2 Algoritmo de CannyEm 1986, John Canny definiu um conjunto de objetivos (tres deles) que deveriam seratingidos por um detector de arestas, descrevendo entao um metodo otimo:

Taxa de Erro: O detector de arestas deve responder apenas as arestas e encontrar todaselas sem que nenhuma seja perdida;

Localizacao: A distancia entre os pixels de uma aresta e o centro da mesma arestaencontrada por um detector deve ser tao pequena quanto possıvel;

15

3.2 Algoritmo de Canny

(a) Imagem original. (b) σ = 2

(c) σ = 3 (d) σ = 4

Figura 3.12: Resultados obtidos com algoritmo de Marr-Hildreth utilizando diferentesvalores de desvio padrao σ.

Quantidade de Respostas : O detector nao identificaria multiplos pixels na arestaonde apenas uma simples aresta existe. Em outras palavras, o numero de maximoslocais em torno da aresta verdadeira deve ser mınimo.

O algoritmo de Canny consiste em expressar matematicamente os tres criterios citadosanteriormente, bem como encontrar solucoes otimas para eles. Como e difıcil encontraralgo que os satisfacam completamente, o uso de otimizacoes com arestas de degrau unidi-mensionais que foram corrompidas por ruıdo branco gaussiano, levam a conclusao de que,uma aproximacao interessante, para este detector otimo, e a primeira derivada de umagaussiana, como mostra a Equacao 3.16.

G′(x) =d

dxe−

x2

2σ2 = − x

σ2e−

x2

2σ2 (3.16)

Fazer um mudanca para o caso bidimensional exigiria que a direcao do vetor normala aresta fosse conhecida, isso implica que seria necessario utilizar um detector de arestasde uma dimensao em todas as direcoes possıveis, o que e inviavel. Para resolver esse

16

3.2 Algoritmo de Canny

problema, podemos suavizar a imagem com uma gaussiana de duas dimensoes, calcular ogradiente e sua magnitude, de modo a estimar a intensidade da borda e a direcao de cadaponto.

Supondo que f(x, y) seja a imagem a ser processada e, temos entao a funcao G(x, y),ilustrada na Equacao 3.17.

G(x, y) = e−x2+y2

2σ2 (3.17)

Agora fazendo a convolucao da imagem f com a funcao gaussiana G temos:

fs(x, y) = G(x, y)× f(x, y) (3.18)

Logo apos calculamos a magnitude e a direcao (angulo) do vetor gradiente:

M(x, y) =√g2x + g2y (3.19)

α(x, y) = tg−1[gygx

](3.20)

onde:

gx =∂fs∂x

e gy =∂fs∂y

(3.21)

Para obtermos gx e gy poderıamos usar qualquer uma das mascaras (Figura 3.7 ouFigura 3.6), citadas anteriormente nas equacoes 3.8 e 3.9.

O proximo passo e afinar as bordas que foram criadas em torno dos maximos locaispelo uso do gradiente M(x, y). O metodo utilizado e o da supressao dos nao maximos, queconsiste em especificar um numero de orientacoes da reta normal ao vetor gradiente. E adirecao da aresta e obtida atraves da direcao do vetor normal a ela atraves da Equacao3.20.

norma da aresta(vetor gradiente)

+157, 5◦−157, 5◦

y

aresta

−22, 5◦ +22, 5◦

α

x

Figura 3.13: Intervalo de valores mostrando um α para uma aresta horizontal.

Assumindo que d1, d2, d3 e d4 indicam as quatro direcoes (horizontal, −45◦, vertical e+45◦) possıveis para uma aresta 3 × 3. O esquema de supressao para esse caso consisteem:

17

3.2 Algoritmo de Canny

• Encontrar a direcao dk que esta mais proxima de α(x, y);

• Se M(x, y) e menor a pelo menos um dos pixels de sua vizinhanca (dk), entaogn(x, y) = 0 ocasionando uma supressao, caso contrario gn(x, y) = M(x, y).

O gn(x, y) citado anteriormente e a imagem com a supressao de nao maximos ou seja,gn(x, y) e a imagem com as bordas afinadas.

A seguir, e necessario fazer a limiarizacao da imagem gn(x, y) para que sejam removidosos falsos pixels da aresta. Um modo simples de fazer essa operacao, e definir um valor(chamado de limiar) e fazer com que todos os valores de intensidade abaixo desse valorsejam 0. Se o valor do limiar for muito baixo, haverao locais onde vao existir arestas falsas,as chamadas de falsos positivos. Por outro lado se o valor do limiar for muito alto, haverao surgimento de bordas chamadas de falsos negativos. Para melhorar a limiarizacao, ometodo de Canny faz uso de uma tecnica chamada de limiarizacao por histerese, queutiliza dois limiares, um alto TH e um baixo TL.

A operacao de limiarizacao de Canny pode ser visualizada utilizando a criacao de duasoutras imagens:

gnH(x, y) = gn(x, y) 6 TH (3.22)

e

gnL(x, y) = gn(x, y) 6 TL (3.23)

onde no comeco tanto gnH quanto gnL ira ter apenas valores 0 e, apos a limiarizacao, gnHtera uma quantidade de pixels zero menor do que gnL, porem, todos os pixels que foremdiferentes de zero em gnH serao adicionados a imagem gnL porque a ultima imagem seraformada com um limiar mais baixo ainda:

gnL(x, y) = gnL(x, y)− gnH(x, y) (3.24)

Depois de feitas as operacoes de limiarizacao, os pixels poderao ser classificados comofortes e fracos. Todos os pixels fortes de gnH(x, y) sao marcados como pixels verdadeirosda aresta. As arestas mais longas, seguem o seguinte procedimento:

1. Localizar na borda da imagem gnH o proximo pixel p a ser revisado;

2. Marcar como pixels validos da aresta todos os pixels fracos em gnL que estao conec-tados a p usando por exemplo, conectividade-8;

3. Se os pixels diferentes de zero em gnH foram revisados, entao siga para a etapaseguinte, caso contrario, va para a etapa 1;

4. Atribuir zero aos pixels de arestas invalidos em gnL.

Ao fim de todo o processo citado acima, a imagem final e formada passando para gnHtodos os pixels diferentes de zero em gnL.

Mesmo ao termos usado duas imagens adicionais (gnH e gnL) para entender a limi-arizacao por histerese, na pratica o algoritmo pode ser aplicado durante o processo desupressao de nao maxima diretamente na imagem gn, formando entao uma lista dos pixelsfracos e fortes conectados entre si.

Assim, o algoritmo de deteccao de arestas de Canny pode ser simplificado nos seguintespassos:

18

3.2 Algoritmo de Canny

1. Leitura da imagem I a ser processada;

2. Criacao da mascara gaussiana de uma dimensao, e suavizar a imagem com essamascara;

3. Fazer o calculo da magnitude do gradiente e dos angulos das imagens;

4. Fazer a aplicacao de supressao de nao maxima na imagem resultante do passo an-terior;

5. Aplicar a limiarizacao (thresholding) utilizando duas imagens e depois fazer a analisede conectividade para detectar as arestas.

Apesar de o algoritmo de supressao de nao maxima afinar as arestas, ao final desteprocesso ainda podem existir arestas que possuem uma largura maior que um pixel. Entao,e comum o uso de algum algoritmo de afinamento, thinning, para que todas as arestastenham uma largura de apenas um pixel.

Como ja discutimos, a suavizacao da imagem de entrada deve ser feita com umamascara gaussiana de tamanho n × n. Para estimar o tamanho de n podemos usar ometodo discutido no algoritmo de Marr-Hildreth, ou seja, utilizar a mascara de filtragemfruto da amostragem gerada pela Equacao 3.17, e garantir que n seja o menor numerointeiro ımpar maior ou igual a 6σ que ira fornecer uma total capacidade de suavizacao dofiltro gaussiano.

No algoritmo implementado, apos a leitura da imagem e pedido um valor para σ quesera usado para definir o tamanho da mascara gaussiana que sera usada. Para valorespequenos de σ o tamanho da mascara sera proximo de zero, mas o proprio algoritmoira determinar o melhor tamanho necessario para a mascara. Serao criadas outras duasmascaras que serao baseadas na derivada da gaussiana em relacao a x, chamaremos de Gx

e em relacao a y, chamaremos de Gy. O proximo passo do algoritmo, e filtrar a imagem Icom a gaussiana e separa-la em duas outras imagens, uma contendo a gaussiana na direcaox, chamaremos de Ix, e outra na direcao y que chamaremos de Iy. Em seguida e feita aconvolucao das imagens Ix e Iy com a derivada da gaussiana, Gx e Gy, respectivamente.As imagens resultantes dessa convolucao serao chamadas de I ′x e I ′y. Agora sera calculadoa magnitude M do gradiente, em cada pixel (x, y) das imagens I ′x e I ′y com a seguinteequacao:

M(x, y) =√I ′x(x, y)2 + I ′y(x, y)2 (3.25)

O valor de M sera grande se o pixel analisado for um pixel de aresta, caso contrario eletera um valor pequeno, uma limiarizacao na imagem resultante da convolucao com M efeita baseando-se parcialmente na direcao do gradiente de cada pixel. A ideia basica e quecada pixel tenha uma direcao associada a si e, sendo um pixel de aresta, a magnitude dogradiente deve ser maior que a magnitude dos pixels que ficam dos dois lados da aresta.A etapa final e a supressao de nao maximos, onde os pixels que sao maximo local seraoremovidos.

O resultado da aplicacao do algoritmo de Canny que discutimos ao longo desta secao,fizemos o teste na Figura 3.14(a) e, como imagem resultante obtivemos a Figura 3.14(b).Esta imagem tambem foi processada pelo sistema desenvolvido. Para os testes, utilizamosos parametros: σ = 1, limiar inferior = 0 e limiar superior = −1.

19

3.3 Algoritmo de Shen e Castan

(a) Imagem original. (b) σ = 1; limiar inferior = 0; limiar superior= −1

Figura 3.14: Resultado obtido com o algoritmo de Canny.

3.3 Algoritmo de Shen e CastanO detector de arestas de Canny definiu uma otimizacao levando em consideracao umconjunto especıfico de criterios. Mesmo que esses criterios parecam razoaveis, nao harazoes para pensar que eles sao os unicos. Isto significa que o conceito de “otimo” erelativo, entao e possıvel a existencia de um detector de arestas melhor do que o deCanny em algumas circunstancias.

Shen e Castan concordam com Canny sobre a forma geral de um detector de arestas:uma convolucao com um nucleo de suavizacao, seguido por uma busca pelos pixels daaresta. No entanto, sua analise resulta em uma forma diferente de otimizacao, isto e, elessugerem uma reducao do criterio infinito normalizado, a uma dimensao:

C2n =

4

∫ ∞0

f 2(x)dx ·∫ ∞0

f ′2(x)dx

f 4(0)(3.26)

Em outras palavras, a funcao que maximiza Cn e o filtro “otimo” de suavizacao paraum detector de arestas. O desenvolvimento do filtro de Shen e Castan resultou em algoque foi chamado de Infinite Symmetric Exponential Filter ou simplesmente ISEF, onde afuncao f e dada pela Equacao 3.27.

f(x) =p

2e−p|x| (3.27)

Shen e Castan afirmam que este filtro oferece uma melhor relacao sinal-ruıdo, e por-tanto conseguem uma melhor localizacao. Isso poderia ocorrer pelo fato de que a im-plementacao do algoritmo de Canny aproxima seu filtro otimo pela derivada de umagaussiana, quando e usado o filtro otimo diretamente, ou poderia ser devido a maneiracom que os criterios de otimizacao sao refletidos na realidade. Por outro lado, eles naoabordam o criterio de respostas multiplas, e como resultado e possıvel que seu metodocrie resultados falsos na presenca de ruıdos e bordas turvas.

Para uma abordagem em duas dimensoes, o ISEF e dado pela Equacao 3.28.

f(x, y) = a · e−p(|x|+|y|) (3.28)

20

3.3 Algoritmo de Shen e Castan

A Equacao 3.28, mostrada anteriormente, pode ser aplicada a uma imagem da mesmamaneira que a derivada de um filtro gaussiano, com o filtro unidimensional na direcao xe depois na direcao y. No entanto Shen e Castan deram um passo a mais na realizacaode seus filtros, eles usaram varios filtros recursivos de uma dimensao.

A funcao do filtro f mostrada em 3.28 e uma funcao real e contınua. Ela pode serdiscretizada para a Equacao 3.29 onde o resultado agora e normalizado tambem.

f [i, j] =(1− b)b|i|+|j|

1 + b(3.29)

Para envolver uma imagem com este filtro, primeiro e feita uma filtragem recursivana direcao x. Nas equacoes 3.31 e 3.31, x1 e x2 correspondem as duas iteracoes feitas nadirecao x, que ao serem somadas resultam em x[i, j], que mostramos na Equacao 3.32.

x1[i, j] =1− b1 + b

I[i, j] + bx1[i, j − 1], j = 1 . . . N, i = 1 . . .M (3.30)

x2[i, j] = b1− b1 + b

I[i, j] + bx1[i, j + 1], j = N . . . 1, i = 1 . . .M (3.31)

x[i, j] = x1[i, j] + x2[i, j + 1] (3.32)

com as seguintes condicoes de limites:

I[i, 0] = 0

x1[i, 0] = 0

x2[i,M + 1] = 0

Agora a filtragem e feita na direcao y, assim como fizemos anteriormente para a direcaox, onde neste caso a soma de y1 e y2, mostrados nas equacoes 3.33 e 3.34 respectivamente,ira ter como resultado final y, que ilustramos na Equacao 3.35.

y1[i, j] =1− b1 + b

I[i, j] + by1[i− 1, j], i = 1 . . .M, j = 1 . . . N (3.33)

y2[i, j] = b1− b1 + b

I[i, j] + by1[i+ 1, j], i = N . . . 1, j = 1 . . . N (3.34)

y[i, j] = y1[i, j] + y2[i+ 1, j] (3.35)

para o caso da filtragem na direcao y tambem ha restricoes sendo elas:

I[0, j] = 0

y1[0, j] = 0

y2[N + 1, j] = 0

O uso de filtragens recursivas acelera significativamente a convolucao.O algoritmo de Shen e Castan, para efeito de testes, foi aplicado na Imagem 3.15(a).

O resultado desta imagem apos o seu processamento e ilustrado na Imagem 3.15(b).

21

3.3 Algoritmo de Shen e Castan

(a) Imagem original. (b) Imagem processada.

Figura 3.15: Resultado obtido com o algoritmo de Shen e Castan.

22

Capıtulo

4

Ambiente de Desenvolvimento

O prototipo de um sistema de processamento de imagens, com foco inicial nos algoritmosde deteccao de arestas, foi desenvolvido durante o estudo dos metodos que discutimos nodecorrer deste documento.

Vamos fazer uma explicacao do porque termos usado determinadas bibliotecas e lin-guagem de programacao. Iremos comentar sobre cada um desses itens ressaltando seuspontos positivos e sua usabilidade no cenario mundial.

Logo apos o comentario sobre as ferramentas utilizadas, falaremos sobre o prototipodo sistema que desenvolvemos, mostrando cada parte da sua interface juntamente com asfuncoes que foram implementadas.

4.1 Ferramentas UtilizadasO prototipo foi desenvolvido utilizando a linguagem C++, pois ela oferece uma certarobustez e confiabilidade nos algoritmos desenvolvidos. Esta linguagem tambem nos pro-porciona a utilizacao das tecnicas de orientacao a objetos, facilitando a modularizacaodo sistema e oferecendo uma melhor legibilidade do codigo. Alem desses pontos fortesnao podemos deixar de citar alguns outros como: simples acesso ao baixo nıvel, caso sejanecessario trabalhar a nıvel de bits; vasta biblioteca padrao, o C++ possui em seu nucleoa biblioteca STL1 (Standard Template Library), que deixa a disposicao do programadoruma grande quantidade de estruturas de dados, como listas encadeadas e filas, alem demetodos para manipula-las.

Utilizamos tambem a biblioteca Qt2 para o desenvolvimento de toda a interface do pro-totipo, mantendo uma uniformidade na aparencia onde quer que o sistema seja executado.Tambem a utilizamos para facilitar a manipulacao dos pixels das imagens a serem proces-sadas, mantendo um certo “alto nıvel” de desenvolvimento pois, caso contrario, terıamosque manipula-los em “baixo nıvel”, ou seja, a nıvel de bits. Ainda, a Qt proporcionou umafacilidade unica de manipulacao das imagens independente de quais formatos estarıamostrabalhando, assim, o nosso sistema pode atuar em cima dos principais formatos de ima-gem do mercado atual como: JPG, PNG, BMP, GIF e outros. Mas a Qt vai muito alemdo uso que fizemos, a biblioteca possui mais de 800 classes com o objetivo de proporcionaruma ambiente de facil aprendizado e uso para a construcao de interfaces graficas ricas eintuitivas, assim como a manipulacao de tipos abstratos dados sem que o programadorprecise se desprender do foco principal, que e o desenvolvimento da aplicacao. Esta bibli-

1http://pt.wikipedia.org/wiki/Standard_Template_Library2http://qt.nokia.com

23

4.1 Ferramentas Utilizadas

oteca e nativamente escrita em C++, mas ela possui algumas versoes para uso em outraslinguagens como Python (PyQt, PySide) e Java (Qt Jambi), por exemplo. Alem disso Qte a base do ambiente desktop grafico KDE, utilizacao esta, que confirma a confiabilidadeda biblioteca.

Uma outra biblioteca que utilizamos foi a OpenCV3. Esta biblioteca foi inicialmentedesenvolvida pela Intel e depois doada a comunidade, onde esta agora e desenvolvidapelos mais diversos programadores espalhados pelo mundo. A OpenCV e especıfica para oramo da Visao Computacional, possuindo varios modulos para a manipulacao de imagens,vıdeos alem de estruturas de dados e algoritmos para algebra linear. Assim como a Qt,a OpenCV foi desenvolvida na linguagem C++, mas tambem existem versoes para aslinguagens Java, Python e Visual Basic. Seu uso em nosso sistema foi limitado inicialmentea apenas dois propositos: captura de imagens via webcam e uso da tecnica de deteccao dearestas de Canny. Como o algoritmo de Canny se mostra bastante eficaz para a maioria dassituacoes, a OpenCV traz somente ele consigo. A captura de imagens atraves de webcamse uma tarefa um tanto complicada para os programadores, sendo assim, e comum a buscapor mecanismos que facilitem esta tarefa, e foi onde a OpenCV nos ajudou. Gostarıamosde ressaltar que o pouco uso que fizemos da da biblioteca, nao reflete de modo algum emsua usabilidade e utilidade. Como pretendemos continuar este projeto e amplia-lo, serade extrema importancia a incorporacao desta biblioteca.

Ambas as bibliotecas, Qt e OpenCV, sao codigo aberto e de uso livre, isso quer dizerque qualquer usuario podera utiliza-las para o proposito que desejar, sendo este comercial,academico ou pessoal, sem que necessite pagar qualquer quantia por isso.

Vale a pena dizer que e comum o uso de bibliotecas no desenvolvimento de qualquersoftware. Esta pratica ajuda o desenvolvedor de duas maneiras: facilita o desenvolvimentoda aplicacao, pois ele estara usando codigos (das bibliotecas) que sao otimizados para oproposito que foram desenvolvidas; e faz com o que o desenvolvedor mantenha sua atencaoapenas no proposito da aplicacao, entao ele nao precisa se preocupar em coisas como, porexemplo, implementar uma lista encadeada, se necessitar de tal estrutura. E foi com essesdois objetivos em mente que optamos pelo uso dessas bibliotecas. Isso sem contar quesao ferramentas usadas em larga escala pela industria de software, fator que garante aconfiabilidade do uso das mesmas.

4.2 Prototipo DesenvolvidoNo prototipo que desenvolvemos adicionamos os algoritmos que foram estudados e, adici-onamos as entradas em seu menu principal, para facilitar o acesso aos mesmos. O sistemase constitui de uma GUI (Graphical User Interface), onde a iteracao com usuario e fa-cilitada. Assim, o usuario carrega no sistema a imagem que deseja processar, acessa afuncao que deseja no menu, e por fim especifica alguns parametros a serem utilizados peloalgoritmo. A propria interface ja possui alguns parametros pre-definidos para auxiliar ousuario, se este nao souber qual valor colocar. Na Figura 4.1 mostramos a janela principal.

Poucos foram os recursos incorporados ao sistema nesse primeiro momento. Comovamos continuar o estudo, no decorrer do tempo, mais funcoes serao implantadas. Valelembrar que o modo como o sistema foi feito, altamente modularizado, possibilita queoutros alunos que estejam desenvolvendo seu Trabalho de Conclusao de Curso (TCC),na area de processamento de imagens, possam utilizar esse prototipo como base para aimplementacao de seus proprios algoritmos. Bastando que para isso apenas adicionem arespectiva classe (classe e um modulo na programacao orientada a objetos) ao sistema, efacam as devidas entradas no menu principal ligando-o aos algoritmos. O mesmo prototipo

3http://opencvlibrary.sourceforge.net

24

4.2 Prototipo Desenvolvido

Figura 4.1: Interface do prototipo do sistema.

tambem pode servir como ferramenta base para alunos da disciplina de Processamentode Imagens, que poderao usa-lo como uma aplicacao basica, que manipula imagens, ondepoderao ser adicionados os codigos desenvolvidos, na disciplina, para se certificarem desua aplicacao.

Na interface principal, vamos comentar as suas partes e divisoes, que sao ilustradasna Figura 4.2, com base nesta figura vamos, fazer as devidas explicacoes a seguir:

Menu principal (Retangulo 1): E onde temos a mais completa quantidade de recursosdo sistema. E neste menu que podemos acessar os algoritmos implementados entreoutras funcoes basicas como abrir e salvar imagens;

Barra de ferramentas (Retangulo 2): Neste local temos alguns poucos, apenas 5, re-cursos do sistema. Estes mesmos recursos poderao ser acessados pelo menu prin-cipal, mas estao dispostos desta forma para facilitar o acesso. Da esquerda para adireita, os botoes correspondem as funcoes: Abrir imagem, com esta funcao pode-mos abrir uma imagem qualquer para que o sistema possa trabalhar nela; Salvarimagem, possibilita salvar uma imagem que foi previamente processada; Desfazer,desfaz qualquer alteracao que tenha ocorrido na imagem original; Sobre, mostrauma janela com algumas informacoes do sistema; e Sair, fecha a aplicacao;

Painel de informacoes(Retangulo 3): Aqui e mostrada uma miniatura da imagem ori-ginal para que o usuario possa comparar a imagem processada com a que foi car-regada no sistema. Ainda neste painel tem o botao capturar webcam, que ao serclicado, dispara um contador regressivo de 5 segundos. Durante o tempo da conta-gem e feita a captura do sinal da webcam, permitindo ao usuario inserir no sistemade uma imagem que nao esta em seu computador. Ao termino da contagem, o ultimoframe (quadro) e capturado, possibilitando o seu processamento como se fosse umaimagem qualquer. Ainda nesta area mostramos o tamanho da imagem em pixels.

25

4.2 Prototipo Desenvolvido

Figura 4.2: Partes da interface principal.

Pretendemos futuramente adicionar mais recursos a este painel ao adicionar maisinformacoes que podera ser retirada da imagem de entrada;

Imagem processada(Retangulo 4): Este e o local onde e mostrada inicialmente a ima-gem que foi carregada. Todo e qualquer processamento efetuado, sera imediatamentevisualizado neste quadro.

As entradas existentes no menu principal, sao essencialmente as mais comuns paraqualquer sistema computacional de processamento de imagens. A diferenca esta no menuferramentas, que e mostrado em detalhe na Figura 4.3, onde temos as entradas referentesaos algoritmos implementados.

Agora, vamos explicar cada uma das funcoes mostradas:

Deteccao de Arestas (Figura 4.3(a)): Atraves desta entrada podemos acessar os algo-ritmos de Canny, Shen-Castan e Marr-Hildreth, ambos foram alvo deste relatorio.Ao escolher qualquer um dessas entradas, sera mostrado ao usuario uma janela re-ferente aos parametros necessarios para cada algoritmo. A mesma janela que pedetal(is) valor(es) ja possui um valor padrao para o caso do usuario nao saber qualvalor inserir, bastando entao clicar me “Ok”;

Algoritmos (Figura 4.3(b)): Nessa parte do menu, foi implementado apenas um algo-ritmo de medicao de ruıdos, que quando selecionado, ira analisar a imagem aberta,e mostrara uma janela com os valores da media e desvio padrao encontrados naimagem e no ruıdo;

Filtros (Figura 4.3(c)): A parte de filtros e composta por apenas duas entradas. Umae chamada de “Tons de Cinza”, que quando ativada deixa a imagem (colorida) emtons de cinza. A outra entrada, chamada de “Sobel”, e para a aplicacao do filtro deSobel Podendo ainda aplicar este filtro apenas na direcao x, onde sao destacadas

26

4.2 Prototipo Desenvolvido

(a) Deteccao de Arestas. (b) Algoritmos.

(c) Filtros. (d) Efeitos.

Figura 4.3: Entradas do menu Ferramentas.

as linhas na horizontal, ou apenas na direcao y, onde o destaque sao para linhasverticais ou ainda nas duas coordenadas, ressaltando assim as linhas horizontais everticais ao mesmo tempo;

Efeitos (Figura 4.3(d)): Por fim temos a entrada “Negativo” no menu de efeitos. Estaentrada foi incluıda por se tratar apenas de um comando da biblioteca Qt, apenasisso. No decorrer do estudo, ao ler a documentacao da biblioteca, nos deparamoscom um metodo que ao ser aplicado em uma imagem e feita a inversao dos valoresRGB de cada pixel, causando um efeito de negativo.

27

Capıtulo

5

Conclusao

E notavel a evolucao dos algoritmos de deteccao de arestas que mostramos aqui. Estaevolucao ocorre de duas formas: uma e em relacao a otimizacao e acuracia no momentoda deteccao das arestas; e outra e em relacao a complexidade, eles apresentam um certoaumento no uso de metodos matematicos, desde a simples manipulacao de pixels calcu-lando suas primeiras derivadas, ate o uso do calculo de derivadas de segunda ordem evetores gradientes para a analise do crescimento e decrescimento de uma funcao.

Mostramos detalhadamente os principais algoritmos para a deteccao de arestas e,ressaltamos suas particularidades no modelo matematico, finalizando com uma imagemque foi processada por tal algoritmo.

Todas as imagens que mostramos aqui como o resultado de algum algoritmo, foramobtidas por meio da implementacao do mesmo no prototipo de um sistema desenvolvidocomo segundo objetivo do presente projeto.

Durante todo o estudo, a medida que ıamos finalizando as respectivas etapas, rapida-mente a implementacao era feita e adicionada ao prototipo. Logo em seguida foram feitosalguns testes para verificar a validade dos resultados obtidos.

Para trabalhos futuros pretendemos estender ainda mais o uso das tecnicas de detec-cao de arestas para, por exemplo, fazer o reconhecimento de caracteres (OCR - OpticalCharacter Recognition) manuscritos e/ou impressos, pois e uma tarefa bastante utilizadaatualmente e exige um processamento da imagem que tenha uma determinada robustez.No processo de OCR a imagem primeiro precisa passar por um pre-processamento ondee feita uma reducao de ruıdos (se houverem muitos), binarizacao, limiarizacao e tambemuma deteccao de bordas (arestas), logo apos a etapa do pre-processamento a imagempassa por outra sequencia de tratamento conhecida como pos-processamento, ate que porfim seja recuperado o texto em si.

Como foi possıvel notar na Secao 4.2, ha muito o que melhorar no prototipo quedesenvolvemos, portanto pretendemos enriquecer ainda mais sua interface, com a adicaode novos algoritmos de processamento de imagens, tornando-o de facto uma plataformaconsistente de aprendizado nesta area.

28

Referencias Bibliograficas

[1] GONZALEZ R. C.; WOODS, R. E. Digital image processing. 3rd edition. ed. UpperSaddle River, New Jersey: Prentice-Hall, Inc., 2006.

[2] MARTIN, D. et al. A database of human segmented natural images and its applicationto evaluating segmentation algorithms and measuring ecological statistics. In: Proc. 8thInt’l Conf. Computer Vision. [S.l.: s.n.], 2001. v. 2, p. 416–423.

[3] BURGER, W.; BURGE, M. J. Principles of digital image processing : Core algorithms.[S.l.]: Springer Publishing Company, Incorporated, 2009.

[4] DAVIES, E. R. Machine vision: Theory, algorithms, practicalities. 3rd edition. ed.London: Elsevier, 2005.

[5] FORSYTH, D.; PONCE, J. Computer vision: A modern approach. Upper SaddleRiver, New Jersey: Prentice Hall, 2003. (Prentice Hall series in artificial intelligence).

[6] MARR D.; HILDRETH, E. Theory of edge detection. Proceedings of the Royal Societyof London. Series B, Biological Sciences, The Royal Society, v. 207, n. 1167, p. pp. 187–217, 1980. Disponıvel em: <http://www.jstor.org/stable/35407>.

[7] MIRANDA J. I.; NETO, J. C. Filtro Shen-Castan (ISEF) para deteccao de bordas.Sao Paulo, Janeiro 2009.

[8] NIXON, M. S.; AGUADO, A. S. Feature Extraction and Image Processing. Delhi:Newnes, 2002.

[9] PARKER, J. R. Algorithms for image processing and computer vision. United Statesof America: Wiley Computing, 1997. 417 p.

[10] PEDRINI H.; SCHWARTZ, W. R. Analise de imagens digitais : Princıpios algoritmose aplicacoes. Sao Paulo: Thomson Learning, 2007.

[11] PITERI, M. A.; RODRIGUES, J. C.; ORG. Fundamentos de visao computacional.Presidente Prudente: [s.n.], 2011.

[12] SHEN, J.; CASTAN, S. An optimal linear operator for step edge detection. CV-GIP: Graphical Models and Image Processing, v. 54, n. 2, p. 112 – 133, 1992. ISSN1049-9652. Disponıvel em: <http://www.sciencedirect.com/science/article/B6WDC-4D7CTBD-35/2/bf591a0c6c3c39c32a29548961f672da>.

[13] D. Martin and C. Fowlkes and D. Tal and J. Malik. The Berkeley Segmen-tation Dataset and Benchmark. Acesso em: 20 de jan. 2011. Disponıvel em:<http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/>.

29