DETECÇÃO E AFINAMENTO DE BORDAS EM DIREÇÕES PREVIAMENTE CONHECIDAS Detection and thinning of edges in previously known directions ALMIR OLIVETTE ARTERO1,2 ANTONIO MARIA GARCIA TOMMASELLI2 1 Universidade do Oeste Paulista - Unoeste Faculdade de Informática de Presidente Prudente 2 Universidade Estadual Paulista - Unesp Faculdade de Ciências e Tecnologia almir@ unoeste.br; tomaseli@fct.unesp.br RESUMO Este trabalho apresenta um método para a construção de filtros para detecção de bordas que apresentam uma maior resposta em direções previamente estabelecidas. Esta solução é importante quando se deseja extrair linhas cuja direção é previamente conhecida, tanto a partir de um histograma de direções predominantes, quanto pela predição com base nos modelos de câmara e do objeto. Apresenta-se também uma modificação no método de afinamento por supressão não–máxima, permitindo o tratamento de bordas com qualquer direção. Por fim, são apresentados alguns resultados com uma imagem sintética e com recortes de imagens orbitais CBERS, mostrando exemplos de aplicação dos filtros propostos para detectar bordas de rodovias, cujas direções são conhecidas. Palavras-chave: Segmentação; Detecção adaptativa de bordas; Afinamento. ABSTRACT This work presents a study on the generation of digital masks aiming at edge detection with previously known directions. This solution is important when edge direction is available either from a direction histogram or from a prediction based on camera and object models. A modification in the non-maximum suppression method of thinning is also presented enabling the comparison of local maxima for any edge directions. Results with a synthetic image and with crops of a CBERS satellite images are presented showing an example with its application in road detection, provided that directions are previously known. Keywords: Segmentation; Adaptative Edge Detection; Thinning. Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2 p.157-177, abr-jun, 2009. mailto:almir@%20unoeste.br mailto:tomaseli@fct.unesp.br Detecção e afinamento de bordas em direções... 1 5 8 1. INTRODUÇÃO A análise de imagens por meio de procedimentos genéricos continua sendo uma tarefa de difícil implementação recorrendo-se, na maioria das vezes, a técnicas de processamento de imagens particulares para cada tipo de problema. De fato, muitas tarefas que atualmente são executadas por seres humanos, continuam ainda sem uma solução automática, devido à impossibilidade de uma análise confiável das imagens obtidas. A maior parte dos sistemas de análise de imagens adota uma sequência de processamento bem conhecida (PAINE e LODWICK, 1989), em que a primeira etapa, chamada pré-processamento, é responsável pela filtragem inicial da imagem, objetivando reduzir o ruído e também o excesso de detalhes que não contribuem para a análise da imagem. A segunda etapa, chamada segmentação, é responsável pela divisão da imagem em seus elementos constituintes. Embora exista um grande número de técnicas para a segmentação (métodos baseados em classificação, métodos baseados em bordas, métodos baseados em regiões, métodos baseados em formas e métodos híbridos), não existe ainda um processo único, que apresente resultados satisfatórios em todas as situações. Assim, a definição dos elementos que devem ser considerados depende da aplicação a que se destina a segmentação. Como os objetos existentes nas imagens são limitados por suas linhas de borda, a detecção de bordas é uma estratégia muito usada nesta etapa, geralmente, seguida de uma limiarização, com o objetivo de eliminar pixels de bordas de baixa magnitude e também ruídos. Na etapa seguinte, os pixels de borda devem passar por um processo de afinamento que objetiva reduzir a largura das bordas a um pixel. Finalmente, os pixels de borda podem então ser usados para descrever os objetos nas imagens, na maioria das vezes, gerando segmentos de retas que delimitam os objetos existentes nas imagens. Uma informação importante que pode ser usada para melhorar o processo é o conhecimento a priori sobre a direção das bordas de interesse em uma determinada análise. A primeira hipótese para definir a direção é admitir que são conhecidas as coordenadas de vértices da linha no espaço objeto e que estas coordenadas possam ser projetadas para a imagem por meio de parâmetros de relacionamento entre o espaço objeto e o espaço imagem. Outra maneira de definir uma direção predominante para as bordas é aplicar um processo de determinação de gradientes, e calcular um histograma das direções destes, escolhendo-se a direção que apresentar maior número de ocorrências. Um destes problemas no qual as técnicas de processamento de imagens podem ser aplicadas é a extração automática de feições em imagens de satélite, particularmente para os problemas de registro e correção geométrica (HABIB et al, 2000; WANG et al, 2008). Uma das alternativas atualmente em estudo é o uso de feições lineares para a orientação de imagens orbitais, em particular, eixos de rodovias (MEDEIROS e TOMMASELLI, 2007). Normalmente, as imagens são distribuídas com dados de georreferenciamento, o que permite estimar a posição e orientação aproximada de uma feição na imagem, a Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Artero, A. O. e Tommaselli, A. M. T. 1 5 9 partir das coordenadas de seus vértices no referencial do terreno. Como a qualidade destes dados de georreferenciamento não é alta, obviamente a feição projetada não coincidirá com a feição na imagem, mas a orientação e a posição projetadas podem ser usadas para incrementar o processo de extração de feições. Problemas similares podem ser encontrados na área de Visão de Máquina, como a chamada Visão de Verificação, cujo objetivo é verificar a presença de uma entidade em uma área prevista e então refinar a posição e orientação deste objeto ou mesmo da câmara (BOLLES, 1977; FEDDEMA e LEE, 1990; MORSY e KANAYAMA, 1997). Neste trabalho são apresentadas algumas estratégias para serem utilizadas na etapa de segmentação de imagens, sugerindo que o processo de extração de bordas seja direcionado pelo conhecimento a priori das direções das bordas dos objetos de interesse (ARTERO e TOMMASELLI, 1999). Como as bordas obtidas pelo detector de bordas podem ter direções entre 0o e 360o, também se propõe uma generalização no processo de afinamento por supressão não máxima, idealizado inicialmente para operar com bordas com direções discretas (ver Figura 5(a)). As demais seções deste trabalho estão organizadas da seguinte maneira: na Seção 2 são apresentados os detectores de bordas baseados em diferenciação mais conhecidos, assim como a técnica de afinamento de bordas por supressão não-máxima. Na Seção 3, é apresentada a técnica para a geração de máscaras para detectar bordas com direções específicas e também uma modificação na técnica de afinamento por supressão não-máxima. Na Seção 4 são apresentados alguns resultados obtidos com a aplicação das técnicas propostas em uma imagem sintética e também em duas imagens orbitais CBERS. Por fim, na Seção 5 são apresentados os comentários finais e algumas sugestões para trabalhos futuros. 2. TRABALHOS RELACIONADOS Esta seção apresenta algumas técnicas de detecção e afinamento de bordas mais usadas no processo de segmentação de imagens, observando que estas técnicas foram propostas para a identificação de bordas em todas as direções. São técnicas clássicas e de domínio generalizado na área de processamento de imagens. 2.1 Detecção de bordas A maioria dos processos de detecção de bordas baseia-se na análise de descontinuidades do nível de cinza no pixel analisado em relação a seus vizinhos. Assim, tal diferença pode ser determinada pela derivada do sinal no pixel, cuja definição clássica é dada pela Equação 1, que resulta em f (x+1) – f (x), quando h=1, ou seja, a derivada é obtida com a diferença (gradiente) entre o valor da tonalidade do pixel x+1 e o pixel x. h xfhxfxf h )()(lim)( 0 −+ =′ → (1) Na etapa de detecção de bordas, normalmente são usadas máscaras de Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Detecção e afinamento de bordas em direções... 1 6 0 convolução, construídas de modo a se obter uma aproximação da primeira derivada. Este é o caso dos operadores de Prewitt (PREWITT,1970), Sobel (ROSENFELD e KAK, 1982) e também Nevatia e Babu (NEVATIA e BABU, 1980). O primeiro deles utiliza as máscaras de convolução que aparecem na Figura 1(a), definindo os gradientes em x e y, respectivamente, como Gx e Gy. Estas máscaras são então a expressão da média dos valores da primeira derivada na vizinhança do pixel central. Considerando que os pixels mais próximos ao centro devem apresentar uma maior influência sobre o mesmo, o operador de Sobel define suas máscaras com valores maiores na região central, conforme ilustrado na Figura 1(b). Figura 1 – Máscaras para o cálculo de gradientes usadas no detector de: a) Prewitt; b) Sobel. Gx Gy Gx Gy (a) (b) A partir de Gx e Gy obtidos por Prewitt ou Sobel, é possível obter a magnitude da borda e também a direção do gradiente em cada pixel da imagem, usando as Equações (2) e (3), observando que direção da borda = direção do gradiente + 90o. 22 GyGxmagnitude += (2) ⎟ ⎠ ⎞ ⎜ ⎝ ⎛= Gx Gyarctanα (3) Como as máscaras são construídas baseadas em uma diferenciação no local, elas tendem a apresentar baixas respostas em regiões homogêneas, ou seja, com baixa variação entre as tonalidades dos pixels e altas respostas em regiões de borda, que possuem grande variação entre as tonalidades dos pixels no local. Porém, quando aplicadas em regiões de muita variação, devido à presença de ruídos, os resultados ficam comprometidos. Este problema, geralmente, é resolvido processando a imagem com um filtro passa-baixa, que faz uma suavização no local, antes da operação de detecção de bordas. Uma outra alternativa consiste em aumentar o tamanho das máscaras utilizadas na detecção de bordas (ARTERO, 1999), o que significa considerar uma maior vizinhança do pixel a ser analisado, embutindo uma suavização no local. Entretanto, é preciso considerar que um aumento exagerado no tamanho das máscaras diminui a sensibilidade do detector Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Artero, A. O. e Tommaselli, A. M. T. 1 6 1 quanto às pequenas variações de direção das bordas, sendo preciso considerar o tamanho de máscara mais adequado aos diversos casos. Uma alternativa interessante neste caso é a possibilidade de modificar os tamanhos de acordo com o nível de ruído presente na região, constituindo-se assim em um detector adaptativo. Nevatia e Babu (1980) sugerem que a detecção das bordas seja feita através da aplicação de um conjunto de máscaras construídas de tal forma a apresentarem uma maior resposta para bordas com determinados ângulos de inclinação. A Figura 2 mostra um conjunto de seis máscaras (PRATT, 1991) que respondem com maior intensidade em locais onde o gradiente tem direção de 0o, 30o, 60o, 90 o, 120o e 150o, observando que as máscaras utilizadas para detectar bordas em que o gradiente tem direção α e (α+π) são similares, sendo a única diferença definida pela troca dos sinais. Assim, máscaras para a detecção de bordas com direções de gradientes entre 180o e 330o podem ser obtidas a partir destas seis máscaras. Figura 2 – Máscaras utilizadas pelo operador de Nevatia e Babu (PRATT,1991). A Figura 3 apresenta os resultados da aplicação das máscaras de Prewitt, Sobel e também Nevatia e Babu. Em (a), tem-se um recorte da imagem original usada no experimento, que é uma imagem CBERS, enquanto que em (b), (c) e (d) tem-se os resultados obtidos, respectivamente, com os operadores de Prewitt, Sobel e Nevatia e Babu. Entretanto, vale ressaltar que os bons resultados obtidos com os filtros de Nevatia e Babu, se devem, em parte, ao uso de máscaras de maior tamanho (5x5) do que as máscaras usadas com Prewitt e Sobel de tamanho 3x3. Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Detecção e afinamento de bordas em direções... 1 6 2 Figura 3 – a) Recorte da Imagem original, b) bordas detectadas com o operador de Prewitt; c) Sobel e d) Nevatia e Babu. (a) (b) (c) (d) 2.2 Eliminação de bordas insignificantes (limiarização) Após a etapa de detecção de bordas, a imagem de gradientes resultante (derivada da imagem) deve passar por um processo de limiarização, para eliminar pixels que apresentam magnitudes muito pequenas e, portanto, não pertencem de fato a regiões de bordas. Embora exista uma grande quantidade de métodos de limiarização (SAHOO, 1988), um dos mais conhecidos na literatura é o método de Otsu (OTSU, 1979), que é baseado na análise discriminante, sendo o valor do limiar obtido a partir da suposição que os pixels da imagem podem ser classificados em duas classes c0 e c1, que são o objeto e o fundo. Supondo que e sejam as variâncias entre as classes e total, respectivamente, a variância entre as classes é σ B 2 σ T 2 dada por: onde: , 2 1010 2 )( μμωωσ =B ∑ = = t i ip 0 0ω 01 1 ωω −= e 0 0 ω μμ t= com e ∑ = = t i it pi 0 .μ n np i i = , enquanto que a variância total entre as classes é dada Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Artero, A. O. e Tommaselli, A. M. T. 1 6 3 por: onde: e n iT l i T pi .)( 2 1 0 2 μσ −=∑ − = ∑ − = = 1 0 . l i iT piμ i é a freqüência que o valor i ocorre na imagem e n o valor total de pixels na imagem. O valor ótimo para o limiar, segundo este método, é dado pelo valor de t, tal que n minimiza a relação 2 2 T Bn σ σ = . Um outro método de grande interesse, e usado no detector de Canny, é chamado Limiarização por Histerese, e define quais pixels pertencem às bordas, usando dois limiares TH e TL. Inicialmente, todo pixel da imagem que tem nível de cinza maior que o limiar superior TH, é identificado como um pixel de borda. Em seguida, todos os pixels que estejam conectados aos pixels de borda e que possuam nível de cinza maior que TL são também definidos como pixels de borda. Com isto, consegue-se evitar o excessivo rompimento das linhas de bordas, decorrente das variações dos níveis de cinza ao longo de uma mesma borda da imagem. 2.3 Afinamento de bordas Após a etapa de limiarização, as bordas continuam apresentando uma espessura maior do que um pixel. Assim, a etapa seguinte no processo deve ser capaz de executar um afinamento das linhas de bordas, mantendo apenas os pixels que melhor representam estas linhas. Algumas das técnicas mais conhecidas que realizam o afinamento são as operações morfológicas de afinamento (Thinning) e obtenção do esqueleto (Skeletonization). Porém, estas operações apresentam resultados satisfatórios apenas em imagens binárias, pois, neste caso todos os pixels possuem um entre dois valores de brilho possíveis ( 0 ou 1 ), que se resumem em cor de fundo e cor de objeto. Estes métodos de afinamento realizam uma eliminação gradual dos pixels mais externos, seguindo em direção ao interior das linhas, de modo que no final restam somente os pixels centrais. No caso de imagens de bordas, os pixels possuem tonalidades de brilho com valor proporcional à proximidade que apresentam em relação à verdadeira posição da borda, como ilustrado na Figura 4, e uma técnica que faz esta consideração é conhecida por Supressão Não-Máxima (CANNY, 1983; DERICHE, 1987; DEVERNAY, 1995), que realiza uma eliminação dos pixels de menor magnitude, perpendicularmente à direção da borda, preservando nesta linha apenas o pixel de maior magnitude. A Figura 4 mostra o perfil de uma borda obtida por meio de algum dos operadores descritos anteriormente, verificando-se a necessidade de seu afinamento. Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Detecção e afinamento de bordas em direções... 1 6 4 Figura 4 – Afinamento por supressão não máxima. (pixel central) (pixel de maior magnitude) 2.3.1 Afinamento por Supressão não-máxima O método sugere uma quantização das direções das bordas em apenas oito direções (VENKATESWAR e CHELLAPA, 1992), conforme mostra a Figura 5(a), observando ainda que os ângulos indicados nesta figura se referem às direções das bordas e não dos gradientes (defasados entre si em 90 o). A Figura 5(b) mostra que pixels com direção 90o ou 270o devem ser comparados com seus dois vizinhos horizontais (à direita e à esquerda), enquanto que pixels com direção horizontal (0o ou 180o) (Figura 5(b)), deverão ser comparados com seus dois vizinhos verticais (pixels acima e abaixo). No caso de retas inclinadas, tal como se mostra na Figura 5(b), os pixels também devem ser comparados com seus vizinhos na normal ao ponto, do mesmo modo como nos casos anteriores. Entretanto, o processo não é tão simples como nos dois casos anteriores, sendo preciso encontrar a magnitude resultante a uma distância unitária do pixel a ser comparado, o que pode ser feito com uma interpolação bilinear, tal como ilustrado na Figura 5(c). Figura 5 – a) Direções normalmente consideradas na supressão não máxima; b) Processo de afinamento de três linhas de borda com diferentes inclinações; c) Detalhe da localização do pixel a ser interpolado. (a) (b) (c) Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Artero, A. O. e Tommaselli, A. M. T. 1 6 5 Em (c), os pontos x1 e x2 são obtidos por duas interpolações lineares, utilizando as equações paramétricas das retas ab e cd, respectivamente, dadas por : x1 = a + (b – a)k1 (4) x2 = c + (d – c)k2 (5) e o ponto x é obtido por uma terceira interpolação, desta vez utilizando a equação paramétrica da reta x1 x2, dada por : x = x1 + (x2 – x1)k2 (6) onde x é a magnitude interpolada procurada. Aplicando (4) e (5) em (6) tem-se: x = a + ( b – a ) k1 + [( c + ( d – c) k1 ) – ( a + ( b – a ) k1 )] k2 (7) assim x = a + ( b – a ) k1+ ( c – a ) k2) + ( d – c – b + a ) k1 k2 (8) e para o caso particular em que k1 = k2 tem-se que : x = a + ( b – 2a + c ) k1+ ( d – c – b + a ) k2 (9) Os valores de k1 e k2 são dados pelo cosseno e seno da direção da borda, respectivamente (ambos em valor absoluto). O detector de Canny utiliza a supressão não máxima juntamente com a limiarização por histerese, para obter excelentes resultados, como ilustrado na Figura 6. Figura 6 – Imagem original; b) Bordas obtidas com o detector de Canny. (a) (b) Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Detecção e afinamento de bordas em direções... 1 6 6 3. DETECÇÃO E AFINAMENTO DE BORDAS COM DIREÇÕES ESPECÍFICAS Esta seção apresenta uma estratégia simples para a construção de máscaras similares às de Nevatia e Babu em tempo de execução, que também evita a necessidade da discretização em apenas doze direções, como proposta originalmente (ver Figura 2), bem como a discretização inicial necessária no afinamento por supressão não máxima (ver Figura 5(a)). Uma outra vantagem importante é que a construção das máscaras, em tempo de execução, permite que sejam criadas máscaras para detectar bordas com direções específicas, de acordo com o interesse do usuário e também máscaras de diferentes dimensões, que não precisam, necessariamente, ser quadradas, de modo a atender necessidades específicas de uma aplicação. 3.1 Construção das máscaras de Nevatia e Babu em tempo de execução A abordagem proposta neste trabalho parte do princípio que os valores das células das máscaras para cálculo do gradiente podem ser obtidos dinamicamente, calculando-se a área das células acima e abaixo da reta centrada na máscara, usando o coeficiente angular previamente conhecido. Uma maneira de obter estas áreas pode ser pelo teste de todos os pontos limites de uma célula (canto superior esquerdo e direito, e canto inferior esquerdo e direito) e, caso todos estes se encontrem acima ou abaixo da reta, a célula receberá imediatamente o valor –100 ou 100, respectivamente (Figura 7(a) e 7(e)). De fato, o cálculo da área pode ser feito apenas calculando as interseções entre os limites das células, considerando que podem ocorrer as demais situações indicadas na Figura 7. Figura 7 – Possíveis situações de interseção entre uma célula e a reta y = ax + b. (a) (b) (c) (d) (e) p3 p4 p2 p1 p3 p4p2 p1 p5 p6 p2 p3 p4 p1 p5 p6 p3 p4 p2 p1 p5 p6 p3 p4 p2 p1 Nas Figuras 7(a) e 7(e), todos os quatro pontos de interseção pi entre as retas que limitam a célula estão abaixo e acima da reta y = a x + b, assim, os valores correspondentes das células são 100 e –100, respectivamente. Em 7(b), 7(c) e 7(d) são encontrados os pontos de interseção p1, p2, p3, p4, p5 e p6 e, os valores das células (VC) são então dados pelas áreas dos polígonos, que podem ser calculadas usando a expressão 10, que permite o cálculo da área de um polígono qualquer. Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Artero, A. O. e Tommaselli, A. M. T. 1 6 7 (∑ ++ −= iiii yxyxVC 112 1 ) (10) Uma outra opção, implementada neste trabalho, sugere que o valor em cada uma das células seja obtido considerando que cada célula é formada por uma quantidade fixa de pontos k x k, obtida a partir das dimensões das células, então, usando a Equação 11, verifica-se quantos destes pontos existentes no interior das células estão acima e abaixo da reta. VC = Área sob a reta – Área sobre a reta (11) Sendo que a reta considerada deve sempre ser posicionada de modo a passar pelo centro da máscara, e possuir a inclinação α (do gradiente) da borda a ser detectada. Por este método, o cálculo das máscaras fica totalmente reduzido à soma da quantidade de pontos dentro das células, acima e abaixo da linha reta. Neste trabalho, para a obtenção de uma máscara m x n, foi utilizada a geometria apresentada na Figura 8, que no caso, gera uma máscara que responde com maior intensidade em bordas com direção de 120o, ou seja, em locais onde o gradiente tem direção de 30o. Figura 8 – Representação gráfica para a estratégia proposta para a construção de máscaras de Nevatia e Babu em tempo de execução. Analiticamente, dada a equação da reta, definida a partir da direção α do gradiente: y = a x + b (12) com a e b dados por a = arctan(α) (13) e b = -a xc + yc (14) Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Detecção e afinamento de bordas em direções... 1 6 8 onde xc e yc são as coordenadas do centro da máscara a ser obtida, dadas por : 5.0 2 1 −= kmxc (15) e 5.0 2 2 −= knyc (16) Nas Equações (15) e (16), m e n são as dimensões da máscara, sendo que m ≠ n produzem máscaras retangulares. As constantes k1 e k2 definem a quantidade de pontos que estão dentro de cada célula (nas direções x e y) e servem para controlar a qualidade dos resultados obtidos por este método, sendo que os testes executados mostraram que valores adequados são obtidos com k1 e k2 >100. O método sugerido neste trabalho, para o cálculo das áreas é bastante simples e assemelha-se à forma como as pessoas fariam para obtê-lo, caso dispusessem de uma grade com pontos, onde fosse possível contar o número destes elementos que se situam acima e abaixo da reta (Equação 11). A Figura 9 mostra como os elementos de cada célula são classificados como acima e abaixo da reta. Figura 9 – Determinação da posição dos elementos acima e abaixo da reta. Na Figura 9, para todo elemento xf , yf (cada ponto da célula), calcula-se ye = axf + b e, se ye > yf , então o elemento está abaixo da reta, e deve ser somado à área total da célula. Caso ye< yf então o elemento está acima da reta, e precisa ser subtraído da área calculada. Com isto, no final do processo, haverá um valor total acumulado (VTA) na célula e o valor final a ser atribuído à célula (VC) é dado por: 2k VTAVC = (17) Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Artero, A. O. e Tommaselli, A. M. T. 1 6 9 sendo k = k1 = k2 o mesmo valor definido inicialmente nas Equações (4) e (5) (considerando que cada célula é quadrada com dimensão k x k). Uma boa melhora neste método pode ser obtida testando inicialmente os quatro pontos limites de uma célula e, caso todos eles se encontrem acima ou abaixo da reta, a célula receberá imediatamente o valor –100 ou 100, respectivamente (Fig. 7(a) e 7(e)). A Figura 10 mostra algumas máscaras obtidas usando a estratégia proposta e permite uma comparação com as máscaras da Figura 2 (PRATT, 1991). Nota-se uma pequena variação nos valores de algumas células, com a troca dos valores ±78 por ±76 e ±32 por ±30, que em aplicações práticas, não causam diferenças significativas. Figura 10 – Máscaras geradas pelo método proposto. A Figura 11 apresenta máscaras construídas usando o método proposto, sendo especificadas para a detecção de gradientes com direções diferentes daquelas apresentadas por Nevatia e Babu na Figura 2. Em (a) tem-se uma máscara que terá alta resposta onde o gradiente tem direção de 10º, ou seja, uma borda com direção de 100o. A estratégia proposta pode ser usada para obter máscaras com qualquer dimensão, incluindo também máscaras retangulares, ou seja, quando possuem m x n Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Detecção e afinamento de bordas em direções... 1 7 0 células, com m ≠ n, conforme ilustrado na Figura 11(b), que apresenta uma máscara 5 x 7 para detectar locais onde o gradiente tem direção de 30o. Figura 11 – a) Máscara 5x5 gerada para detectar gradientes com direção de 10o; b) Máscara 5x7 gerada para detectar gradientes com direção de 30o. (a) (b) 3.2 Supressão não máxima generalizada Com o objetivo de tratar bordas com qualquer direção, dispensando a necessidade de discretização em apenas oito direções, como ilustrado na Figura 5(a), esta seção propõe um método onde a supressão não máxima opera com direções de qualquer valor, determinando em tempo real quais os pixels devem participar da interpolação bilinear. A Figura 12 mostra uma situação genérica para o afinamento de uma linha com direção de borda α e também os pixels que participam do afinamento (interpolação e posterior comparação de magnitudes) e precisam ser eliminados no processo de supressão. Nesta Figura 12, os valores de α1 e α2 são dados por : 21 παα += e 22 παα −= (18) e Sc e Ss são funções que retornam seus valores de acordo com (19) e (20) ⎪ ⎩ ⎪ ⎨ ⎧ <− > = = 0)cos( 1 0)cos( 1 0)cos( 0 )( xse xse xse xsc (19) e ⎪ ⎩ ⎪ ⎨ ⎧ <− > = = 0)(sen 1 0)(sen 1 0)(en 0 )( xse xse xsse xss (20) Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Artero, A. O. e Tommaselli, A. M. T. 1 7 1 Figura 12 Determinação dos pontos a serem verificados no processo de afinamento. Na Figura 12, o valor da magnitude no ponto m1 , que possui distância unitária ao pixel central, pode ser calculado, por meio de uma interpolação bilinear, após a determinação dos pontos a1, b1, c1 e d1, conforme abordado anteriormente (Eq. 9). O mesmo procedimento deve ser realizado para a determinação de m2, a partir de a2, b2, c2 e d2. Os valores das magnitudes em m1 e m2 são, então, comparados com a magnitude do pixel i, j, sendo que este último tem a sua magnitude preservada, caso apresente o maior valor entre os três. Caso contrário, o pixel em i, j recebe o valor zero em sua magnitude, o que corresponde a sua eliminação. 4. RESULTADOS A Figura 13 apresenta os resultados obtidos com uma imagem de teste, que possui bordas bem definidas em várias direções. Em (a) tem-se a imagem sintética usada no experimento, enquanto que em (b) tem-se as bordas obtidas com a aplicação do detector de Nevatia e Babu, seguido de uma limiarização com o método de Otsu. Em (c) tem-se o resultado obtido com o detector específico para gradientes com zero grau, também seguido pela limiarização usando o método de Otsu. O processamento realizado para gerar o resultado mostrado em (c) é mais rápido, pois utiliza apenas uma máscara com a direção do gradiente previamente conhecida, ao passo que o detector de Nevatia e Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Detecção e afinamento de bordas em direções... 1 7 2 Babu aplica as seis máscaras apresentadas na Figura 2. Figura 13 – a) Imagem sintética; Resultados obtidos com b) detector de Nevatia e Babu; c) detector específico para gradiente com direção de zero grau. Magnitude =255 Dir. Grad.= 0o Dir. Borda = 90o Magnitude =100 Dir. Grad.= -122o Dir. Borda = -32o (a) (b) (c) Também se verifica que todas as bordas obtidas com o detector de Nevatia e Babu, possuem valores máximos de magnitude, 255 após a normalização para 8 bits, enquanto que nas bordas obtidas com o detector específico, as magnitudes são proporcionais à similaridade com a direção de gradiente especificada. Ou seja, bordas com direções próximas à direção predita (zero grau) possuem valores altos de magnitudes, enquanto que as bordas com direções muito diferentes desta direção possuem valores de magnitude muito baixos, sendo então, completamente eliminadas durante a etapa de limiarização. Com isto, o processamento posterior, de afinamento de bordas e conexão dos pixels pertencentes às linhas retas, fica também bastante reduzido. A Figura 14 apresenta os resultados do processamento de uma imagem orbital CBERS, onde a feição de maior interesse é uma rodovia, que tem a direção (borda) aproximada de 78 graus (direção do gradiente = 168o). Em (a) tem-se a imagem original e, em (b), as bordas obtidas com o detector de Nevatia e Babu, que usa as seis máscaras da Figura 2. Em (c) tem-se as bordas obtidas com o detector de Canny e, em (d), as bordas obtidas com o detector específico para bordas com direção de 78o. Além do processamento resultante, ser mais rápido na etapa de detecção, pois, usa apenas uma máscara, a menor quantidade de pixels de borda obtidos em (d) é importante também, porque acelera a próxima etapa do processo de obtenção das linhas retas, que delimitam a feição de interesse e, que no caso, é a rodovia. Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Artero, A. O. e Tommaselli, A. M. T. 1 7 3 Figura 14 – a) Imagem orbital CBERS; Bordas obtidas com os detectores: b) de Nevatia e Babu; c) de Canny; d) específico para bordas com direção de 78º. (a) (b) (c) (d) Por fim, é preciso observar que o detector de Canny é considerado um detector ótimo para bordas do tipo degrau e, portanto, pode ser modificado, de modo a identificar apenas as bordas com direções de interesse, evitando o resultado obtido na Figura 14(c). Com isto, espera-se manter a qualidade do detector e também obter uma sensível melhora no seu próprio processamento, especificamente, nas etapas de limiarização (histerese) e afinamento (supressão não máxima). A Figura 15 apresenta o resultado do processamento de uma outra imagem orbital CBERS, onde a feição de maior interesse é também uma rodovia, que tem a direção aproximada de 149 graus. Em (a) tem-se a imagem original. De (b) até (e) tem-se os segmentos de borda com mais de 25 pixels, obtidos, respectivamente, com a aplicação do filtro de Prewitt, Sobel, Nevatia e Babu e o filtro específico para a Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Detecção e afinamento de bordas em direções... 1 7 4 detecção de bordas com 149o. Em todos os casos, após a detecção das bordas é aplicada uma limiarização, usando o método de Otsu. Figura 15– a) Imagem original; Bordas com mais de 25 pixels obtidas com o detector: b) Prewitt, c) Sobel; d) Nevatia e Babu e e) específico para bordas com 149 graus. (a) (b) (c) (d) Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Artero, A. O. e Tommaselli, A. M. T. 1 7 5 Quanto à identificação dos pixels pertencentes à mesma borda, em (b), (c) e (d), esta etapa pode ser realizada usando o método da varredura e rotulação (Scan & Label- VENKATESWAR e CHELLAPA, 1992), se as direções das bordas obtidas são possuem os valores discretos apresentados na Figura 5(a), enquanto que em (e), usa-se o método de agregação de pixels (Flood-Fill), para conectar todos os pixels vizinhos com a mesma direção. Obviamente, quando se deseja identificar a feição principal que tem direção de 149 graus, os resultados do processamento usando Prewitt, Sobel ou Nevatia e Babu podem ser usados. Pois, após a identificação de todos os pixels de borda da imagem, os pixels com direção diferente da desejada podem ser facilmente eliminados, porém, no caso do detector de Sobel, nota-se que algumas partes da feição principal não foram devidamente identificadas. Por outro lado, no caso do detector de Nevatia e Babu, também não faz sentido aplicar todos os filtros da Figura 2 (máscaras de Nevatia e Babu), de alto custo computacional e, em seguida, eliminar as bordas com direções que não interessam. Nesta figura, uma contagem, considerando somente os segmentos com mais de 25 pixels e excluindo a feição principal (bordas da rodovia), revelou que foram detectados 42 segmentos pelo detector de Prewitt, 45 segmentos pelo detector de Sobel, 44 segmentos pelo detector de Nevatia e Babu, e apenas 14 segmentos usando o método proposto. Isto indica que o número de elementos a analisar nas etapas seguintes é de 30% em relação aos métodos citados. (e) 5. CONCLUSÃO A implementação de uma rotina que possibilita a criação em tempo de execução, de máscaras para a detecção de bordas é importante para processos automáticos e também semi-automáticos de extração de feições. Além disso, a possibilidade de modificar os tamanhos das máscaras permite ainda a implementação de um filtro (detector de bordas) adaptativo (de acordo com a presença de ruídos na imagem). A rotina para a geração de máscaras já implementada apresenta bons resultados, devendo ser integrada em processos automáticos e semi-automáticos de extração de feições. Por fim, a modificação no método da supressão não-máxima elimina a necessidade de uma discretização ainda maior nas direções dos pixels de borda, caracterizando assim um perfeito acoplamento entre estas duas etapas da segmentação. Por fim, é preciso observar que a estratégia apresentada neste trabalho não pretende ser uma técnica alternativa à detectores consagrados na literatura, como é o caso do detector de Canny. O que se espera de fato, é que todos os detectores baseados em derivadas possam usar a estratégia sugerida neste trabalho, o que inclui o próprio detector de Canny, que embute no processo, uma suavização da imagem, seguida da aplicação de um filtro derivativo, limiarização usando histerese e do afinamento das bordas usando a supressão não máxima. Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Detecção e afinamento de bordas em direções... 1 7 6 REFERÊNCIAS BIBLIOGRÁFICAS ARTERO, A. O., Técnicas para a extração automática de feições retas em imagens digitais, 117p, Dissertação de Mestrado, UNESP/FCT, Presidente Prudente, 1999. ARTERO, A. O., TOMMASELLI, A. M. G., Técnicas para a Extração de Feições Lineares em Direções Pré-Especificadas. In: XIX Congresso Brasileiro de Cartografia, Recife, 1999. BOLLES, R. Verification Vision for Programmable Assembly. In: Proceedings of 5th IJCAI, pp. 569-575, 1977. CANNY, J. F. Finding edges and lines in images. Massachusets Institute of Technology, Artificial Intelligence Laboratory. Technical Report AI-TR-72983, 1983. DERICHE, R. Using Canny’s criteria to derive a recursively implemented optimal edge detector. The International Journal of Computer Vision. v.1, n.2, pp.167- 187, 1987. DEVERNAY, F., A Non-Maxima Suppression Method for Edge Detection with Sub-Pixel Accuracy, Sophia-Antipolis: Inria, Institut National de Recherche en Informatique et En Automatique, Rapport de recherche n°2724, 1995. FEDDEMA, J.T.; LEE, C.S.G., Adaptive image feature prediction and control for visual tracking with a moving camera. In: IEEE International Conference on Systems, Man and Cybernetics, pp.20-24, 1990. HABIB, A., KELLEY, D., ASMAMAW, A., Utilizing Straight Lines in Object Space for Linear Array Scanner Imagery. In: XIXth ISPRS Congress, Amsterdam. International Archives of Photogrammetry and Remote Sensing. 2000. MEDEIROS, N.G.; TOMMASELLI, A. M. G. Orientation of orbital pushbroom images using control straight lines In: 7th Geomatic Week, Institut of Geomatics, Barcelona, pp.1 - 11, 2007. MORSY, K.A.; KANAYAMA, Y A new straight edge detection algorithm using direction-controlled edge tracking and random hitting. In: IEEE International Symposium on Computational Intelligence in Robotics and Automation, pp. 398 – 405, 1997. NEVATIA, R.; BABU, K. R. Linear feature extraction and description. Computer. Graphics Image Processing, v. 13, p. 257-269, 1980. OTSU, N., A Threshold Selection Method from Grey-level Histograms, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 9, 1, pp.377-393, 1979. PAINE, S. H. e LODWICK, G. D., Edge Detection and Processing of Remotely Sensed Digital Images, Photommetria, v. 43, n. 6, pp. 323-336, 1989. PARKER, J. R. Algorithms for Image Processing and Computer Vision, John Wiley & Sons, New York, 1996. PRATT, W. K., Digital Image Processing. New York : John Wiley & Sons, 1991. Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. Artero, A. O. e Tommaselli, A. M. T. 1 7 7 PREWITT, J.M.S. Object enhancement and extraction. In: LIPKIN, B.S., ROSENFELD, A. Picture Processing and Psychopictorics, Academic Press, 1970. ROSENFELD, A.; KAK, A.C. Digital Picture Processing, Academic Press, Inc., 1982. SAHOO, P. K.; SOLTANI, S.; WONG, A. K. C., An Survey of Thresholding Techniques, Computer Vision, Graphics and Image Processing, n. 41, pp. 233 – 260, 1988. VENKATESWAR, V.; CHELLAPA, R., Extraction of Straight Lines in Aerial Images, IEEE Transactions On Pattern Analysis And Machine Intelligence, v. 14, n.11, 1992. WANG, C; STEFANIDIS, A.; CROITORU, A.; AGOURIS, P., Map Registration of Image Sequences Using Linear Features. Photogrammetric Engineering and Remote Sensing, v. 74, n. 1, pp. 25-38, 2008. (Recebido em agosto / 2008. Aceito em março / 2009). Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 2, p.157-177, abr-jun, 2009. REFERÊNCIAS BIBLIOGRÁFICAS