EXTRAÇÃO AUTOMATICA DE SEGMENTOS LINEARES DE RODOVIAS EM IMAGENS DE RESOLUÇÕES VARIADAS Automatic road segment extraction from images with different resolutions REGINA ISHIBASHI 1 ALUIR PORFÍRIO DAL POZ 2 Universidade Estadual Paulista – UNESP Faculdade de Ciências e Tecnologia – FCT 2 Departamento de Cartografia 1 Programa de Pós-Graduação em Ciências Cartográficas da FCT/UNESP Rua Roberto Simonsen, 305, 19060-900 - Presidente Prudente, SP regina.ishibashi@gmail.com; aluir@fct.unesp.br RESUMO Neste trabalho é apresentada uma metodologia para a extração automática de segmentos de rodovia em imagens de diferentes resoluções (baixa, média e alta resolução). A metodologia é baseada num conceito generalizado de linhas em imagens digitais, pelo qual as linhas podem ser descritas por feições centrais de duas bordas paralelas. No caso específico de imagens de baixa resolução, onde as rodovias manifestam-se como entidades de 1 ou 2 pixels de espessura, a metodologia proposta combina uma operação de realce com as seguintes estratégias: escolha automática dos limiares de histerese e do fator de escala gaussiana; limiarização por comprimento; e poligonação. Em imagens de média e alta resolução as rodovias manifestam-se como faixas estreitas e alongadas e, conseqüentemente, o alvo de extração torna-se os eixos centrais das rodovias. Neste caso, não é necessário aplicar o passo prévio de realce usado para realçar rodovias em imagem de baixa resolução. Os resultados obtidos na avaliação experimental atenderam todos os critérios estabelecidos para a extração eficiente de segmentos de rodovias em imagens de resoluções diferentes, proporcionando resultados satisfatórios de maneira inteiramente automática. Palavras-Chave: Automação; Fotogrametria; Extração de Feições; Bordas Paralelas; Feições Rodoviárias. Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Ishibashi, R. e Dal Poz, A. P. 3 5 3 ABSTRACT In this paper a methodology for automatic extraction of road segments from images with different resolutions (low, middle and high resolution) is presented. It is based on a generalized concept of lines in digital images, by which lines can be described by the centerlines of two parallel edges. In the specific case of low resolution images, where roads are manifested as entities of 1 or 2 pixels wide, the proposed methodology combines an automatic image enhancement operation with the following strategies: automatic selection of the hysteresis thresholds and the Gaussian scale factor; line length thresholding; and polygonization. In medium and high resolution images roads manifest as narrow and elongated ribbons and, consequently, the extraction goal becomes the road centerlines. In this case, it is not necessary to apply the previous enhancement step used to enhance roads in low resolution images. The results obtained in the experimental evaluation satisfied all criteria established for the efficient extraction of road segments from different resolution images, providing satisfactory results in a completely automatic way. Keywords: Automation; Photogrammetry; Feature Extraction; Line Features; Parallel Edges; Road Features. 1. INTRODUÇÃO Com os avanços tecnológicos em Sensoriamento Remoto e Fotogrametria Digital, a extração de feições cartográficas em imagens aéreas e de satélites vem, nas últimas décadas, despertando interesse da comunidade científica. Os processos de extração são utilizados principalmente na captura de dados ou atualização de bases de dados em Sistemas de Informações Geográficas (SIGs) voltados, por exemplo, ao monitoramento ambiental, ao planejamento urbano e ao gerenciamento de tráfego. Em geral desde a década de 1960, vários estudos voltados à extração de feições em imagens digitais foram desenvolvidos, envolvendo as mais variadas comunidades cientificas. Por exemplo, Kovalevskii (1967) utilizou a programação dinâmica para extração de características tipografadas ou de manuscritos. Em Yamada et al. (1988) a extração de feições foi aplicada na área médica, realizando a extração de glomérulos em imagens de microscópio de seções renais e, em Tommaselli (1993), a extração de feições foi voltada à determinação da posição e orientação de um sistema de visão estéreo aplicado à visão robótica. Em Cartografia, há várias décadas, a extração de feições tem sido de fundamental importância na automação dos processos voltados à coleta de informações espaciais, tais como edifícios, rios e rodovias. Os métodos utilizados na extração de feições podem ser classificados em semi-automáticos e automáticos. O método semi-automático envolve a interação do operador durante o processo de extração, já o automático, a extração é realizada sem a intervenção humana. Atualmente, grandes esforços vêm sendo empregados Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Extração automática de segmentos lineares de rodovias... 3 5 4 para o desenvolvimento de estratégias, em nível de algoritmos e softwares voltados à extração de feições de maneira cada vez mais automatizada. Muita pesquisa em extração de rodovia foi desenvolvida desde o trabalho pioneiro de Bajcsy e Tavakoli (1976) e, boa parte das metodologias desenvolvidas, é de concepção semi-automática. O espaço-imagem tem sido usado quase que exclusivamente na concepção das metodologias, muito embora, o espaço-objeto seja reconhecidamente útil para a formulação de várias restrições geométricas em 3D, como é o caso da restrição de suavidade vertical do eixo de rodovia. Em Gruen e Li (1997) é proposta a metodologia pioneira para a extração de rodovia no espaço- objeto usando um estereopar de imagens aéreas. Dal Poz et al. (2006) propuseram uma solução para o mesmo problema, só que utilizando apenas uma imagem aérea e um MDT (Modelo Digital do Terreno). As inúmeras metodologias formuladas no espaço-imagem baseiam-se em diversas estratégias, dentre as quais se destacam as que se baseiam em análise morfológica (AMINI et al., 2002, ISHIKAWA, 2008), análise de perfis transversais de rodovia usando técnicas de correlação unidimensional (ZHOU et al., 2006), programação dinâmica e snakes (AGOURIS et al., 2001, DAL POZ e VALE, 2003), análise multi-escala e contextual (BAUMGARTNER et al., 1999, HINZ et al., 2000, HU et al., 2007), redes neurais (MOKHTARZADE e ZOEJ, 2007), combinação de geodados e imagens (SONG et al., 2009) e lógica fuzzy (AGOURIS et al., 1998, MOHAMMADZADEH et al., 2006). Este trabalho apresenta um estudo voltado à extração automática de segmentos de rodovias em imagens de resoluções variadas (baixa, média e alta resolução), via detector de linhas proposto por Steger (2000). Este detector de linhas foi formulado tendo por inspiração o perfil transversal típico de uma rodovia, cuja largura pode variar de 1 ou 2 pixels até dezenas de pixels. Em Baumgartner et al. (1999), o detector de Steger é utilizado para rastrear as rodovias ao longo do espaço-escala. Hinz et al. (2001) utilizou o detector de Steger para extrair aproximadamente a malha viária urbana a partir de um MDE (Modelo Digital de Elevação), cujo resultado era utilizado para localizar aproximadamente a malha viária em imagens aéreas de alta-resolução. Embora o detector de Steger não seja uma novidade em extração de rodovias, nenhum estudo sobre a escolha dos limiares de histerese (responsável pela eliminação de parte dos fragmentos de linha de pequenas extensões) e do fator de escala gaussiana foi reportado até então. Estes parâmetros são geralmente escolhidos por tentativa e erro para cada imagem, implicando em mais interação do operador com o sistema de extração. A escolha automática destes parâmetros é então um problema relevante no contexto de metodologias automáticas para a extração de rodovias e, como tal, é a principal motivação deste artigo. A estratégia proposta visa selecionar automaticamente os limiares de histerese e fator de escala gaussiano, proporcionando segmentos de rodovias com um mínimo de falsos positivos e negativos. Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Ishibashi, R. e Dal Poz, A. P. 3 5 5 O presente artigo está estruturado em cinco seções. A Seção 2 apresenta os modelos existentes de linhas e o princípio do detector de linhas de Steger. A metodologia automática para extração de rodovias via detector de Steger é apresentada na Seção 3. Os resultados obtidos e as principais conclusões são apresentados, respectivamente, nas Seções 4 e 5. 2. FUNDAMENTAÇÃO TEÓRICA Nesta seção serão apresentados os modelos de linhas existentes e o princípio básico do detector de linhas de Steger necessários para o entendimento do trabalho desenvolvido. 2.1 Modelos de Linhas As rodovias em imagens de baixa (pixels maiores que 2 m), média (pixels variando entre 0,7 m e 2 m) e alta (pixels menores que 0,7 m) resolução são muitas vezes representadas por linhas que podem ser caracterizadas pelo atributo intensidade (tons de cinza) em perfis perpendiculares e que podem também ser descritas por feições simétricas entre duas bordas paralelas. É possível identificar dois tipos diferentes de perfis: com bordas de mesma polaridade e de diferente polaridade. Uma forma de tratamento matemático destes perfis será apresentada a seguir, tendo por base Steger (1998) e Steger (2000). Um modelo de linha ideal de largura 2w e altura 1 de mesma polaridade possui um perfil (figura 1) do tipo barra, dado pela Equação 1. b 1, x w f (x)= 0, x > w ⎧ ≤⎪ ⎨ ⎪⎩ (1) Figura 1 - Perfil simétrico da linha ideal AB de mesma polaridade. Se o contraste de um dos lados da linha for diferente, ou seja, casos em que se tem um perfil do tipo barra assimétrica (figura 2), utiliza-se a seguinte equação para modelar o perfil de linha: Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Extração automática de segmentos lineares de rodovias... 3 5 6 Figura 2 - Perfil assimétrico de linha AB de mesma polaridade. Para linhas com polaridades diferentes, isto é, com perfil semelhante a uma escada, pode-se utilizar a Equação 2 com . Entretanto, uma linha com polaridade diferente (figura 3) é melhor representada por: 1a > s 0, x < -w f (x)= a, | x | w 1, x > w ⎧ ⎪ ≤⎨ ⎪ ⎩ (2) em que . [ [a 0,1∈ Figura 3 - Perfil de linha AB com polaridades diferentes. Em geral, uma linha de altura h pode ser obtida escalonando a função f(x) , o que resulta em hf( . Como geralmente as rodovias em imagens digitais são linhas ou faixas estreitas de alta intensidade de brilho, seus perfis transversais podem ser adequadamente representados conforme a Equação 2. x) Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Ishibashi, R. e Dal Poz, A. P. 3 5 7 2.2 Detector de linhas de Steger Para detectar um ponto de eixo de rodovia, Steger (1998, 2000) utiliza as derivadas parcias do perfil de linha. Um ponto pertencente a um eixo de rodovias em uma imagem é encontrado no ponto de máximo da função fa(x), ocorrendo onde a primeira derivada de fa(x) se anula. Além disso, neste ponto de máximo a segunda derivada para linhas não espúrias (sem ruidos) assume altos valores. Entretanto como as imagens contêm ruídos, a primeira e a segunda derivada da função fa(x) podem ser estimadas convoluindo-a com as derivadas do núcleo Gaussiano conduzindo a uma descrição do espaço-escala do perfil linha, como segue: (3) a σ a σ σr (x;σ;w;a)= g (x)* f (x)= φ (x+ w)+(a -1)φ (x - w) a σ a σ σr '(x;σ;w;a)= g '(x)* f (x)= g (x+ w)+(a -1)g (x - w) (4) a σ a σ σr ' '(x;σ;w;a)= g ''(x)* f (x)= g '(x+ w)+(a - 1)g '(x - w) (5) em que, é a integral do núcleo Gaussiano. σφ (x ) Figura 4 - Comportamento da linha af com a = 0 e w = 1 ao longo do espaço- escala, obtido com núcleos gaussianos para [ 3;3]x∈ − e σ [0,2;2]∈ : (a) Comportamento ao longo do espaço-escala para ; (b) Comportamento ao longo do espaço-escala para ; (c) Comportamento ao longo do espaço- escala para (Fonte: STEGER, 1998, 2000). ar (x;σ;1;0) ar '(x;σ;1;0) ar "(x;σ;1;0) (a) (b) (c) A figura 4 mostra o comportamento de perfil de uma linha com semi largura igual a 1 ( ) e assimetria igual a zero ( ), ao longo do espaço-escala. Verifica-se, que com o aumento do valor de sigma ( w = 1 a = 0 σ ), as linhas vão se tornando cada vez mais suavizadas. Dessa forma, é necessário estimar o melhor valor de σ de forma a salientar as linhas mais importantes contidas na imagem. Steger (1998) propõe a seguinte relação: Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Extração automática de segmentos lineares de rodovias... 3 5 8 3 wσ ≥ (7) Este valor de σ é obtido através da solução da equação ( )( ' ' 0; ; ; 0ar w hσ σ ∂ = ∂ ) , a qual garante que é máxima ou mínima nos pontos pertencentes à linha (x=0). ' 'r A posição (x) ideal para linha é dado onde '( ; ; ; ) 0ar x w aσ = , isto é (STEGER, 1998): 2σx = - ln(1- a) 2w (8) A Equação 8 mostra claramente que a linha será extraída na posição correta ( x = 0 ) somente se o contraste em ambos os lados da linha forem iguais, ou seja, . 0a = Numa imagem digital, envolvendo imagens de diferentes resoluções, uma linha pode ser modelada como uma curva paramétrica s(t), para a qual se tem na direção transversal um comportamento semelhante ao perfil unidimensional dado pela Equação 2. Assim, dado um ponto p de s(t), deve-se analisar a direção transversal ( à linha em p. Conseqüentemente, pode-se extrair pontos de linhas em 2D com a primeira derivada direcional na direção )( )n t r ( )n t r . Dessa forma, o problema central é a determinação da direção ( )n t r em cada ponto da linha. A direção pode ser obtida a partir do autovetor ( )n t r ( ),x yn n , correspondente ao autovalor de maior magnitude da matriz Hessiana da imagem suavizada. A fim de determinar onde a primeira derivada direcional em ( ),x yn n se anula, é necessário modelar localmente a imagem com o polinômio de Taylor de segunda ordem. Este ponto pode ser obtido inserindo ( ,x ytn tn ) no polinômio de Taylor, obtendo posteriormente o valor de ( ) que minimize o polinômio. As coordenadas ( 't ' , 'x yt n t n ) correspondem a um ponto de linha com precisão sub-pixel. Para ser validado, a derivada segunda do polinômio em deve ser, segundo um limiar, muito grande ou muito pequeno. Este processo deverá ser repetido para todos os pontos. 't Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Ishibashi, R. e Dal Poz, A. P. 3 5 9 3. METODOLOGIA PARA EXTRAÇÃO AUTOMÁTICA DE RODOVIAS As etapas da metodologia para extração de segmentos de rodovias no contexto desta pesquisa são mostradas no fluxograma apresentada na figura 5. Figura 5 - Fluxograma das etapas de extração de segmentos de Rodovias. Conforme mostra a figura 5, a metodologia é dividida em 5 etapas principais. A primeira etapa se diferencia pela resolução da imagem. Em se tratando de imagens de baixa resolução esta etapa de pré-processamento é normalmente necessária, entretanto, em imagens de média e alta resolução este pré- processamento é dispensável. As demais etapas são comuns, independentes da resolução ou quaisquer outros atributos da imagem. Na seqüência são detalhadas as etapas para detecção e extração das linhas que representam segmentos de rodovias, considerando-se imagens de baixa resolução. 1ª) Pré-processamento para realce de rodovias: Em imagens de baixa resolução as estruturas que compõem a malha viária não se apresentam geralmente bem pronunciadas, necessitando de um realce prévio através de operadores Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Extração automática de segmentos lineares de rodovias... 3 6 0 apropriados. Nesta etapa é utilizado o operador dado pela equação 9, cuja finalidade é realçar as áreas de alta freqüência da imagem, combinando operações de suavização e melhoria de contraste. Na equação 9 ip(x) é o operador de arredondamento de x para o inteiro mais próximo, f é um fator de ampliação de contraste e os pixels correspondentes nas imagens original, suavizada e realçada são io, is e ir, respectivamente. ir= ip((io - is).f) + io (9) Optou-se por utilizar o operador acima devido à alta qualidade dos resultados obtidos e a maior automação das etapas de extração. Este operador permite realçar as altas-frequências da imagem, independente das variações geométricas das feições de interesse. Além disso, não é necessário inserir, constantemente, dados de entrada (limiares) que variam conforme a imagem utilizada. Basta apenas fixar a máscara de suavização e o fator de ampliação do contraste para todas as imagens, de modo a auxiliar na automação do processo de extração de rodovias. Durante está etapa utilizou-se uma máscara 7x7 de suavização pela média e um fator de ampliação do contraste igual a 3,0 para serem utilizados durante o processo de realce. 2ª) Aquisição automática dos limiares de histerese: Nesta etapa são determinados automaticamente os limiares de histerese. A limiarização por histerese tem como objetivo eliminar parte dos fragmentos de linha de pequenas extensões provindas do processo de extração. Este processo utiliza dois limiares, sendo eles, o 1τ (limiar inferior) e o 2τ (limiar superior). A escolha desses limiares não é algo tão trivial e normalmente baseia-se em tentativa e erro e experiência do usuário. Figura 6 - Representação do histograma da segunda derivada de uma imagem. 0 500 1000 1500 2000 2500 0 50 100 150 200 250 300 350 400 450 500 550 600 650 700 750 800 850 900 950 1000 n° d e pí xe ls Laplaciano Histograma do Laplaciano (1/100) 30 % 90 % Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Ishibashi, R. e Dal Poz, A. P. 3 6 1 Uma maneira eficiente de análise para a escolha dos limiares é através do histograma da segunda derivada para o menor valor de sigma obtido pela Expressão 7. O menor e o maior limiar foram fixados após inúmeros testes como sendo, respectivamente, 30% e 90% dos valores absolutos do Laplaciano (figura 6). Vale ressaltar que as linhas físicas (correspondem a objetos presentes na imagem, tais como, as rodovias) normalmente possuem valores médios de segunda derivada maiores, localizando-se então à direita da distribuição (acima de 90% dos dados). Já as linhas espúrias possuem valores baixos, concentrando-se então no início da distribuição (0 a 30% dos dados). Entre 30 e 90% estão contidas as linhas espúrias juntamente com as físicas, sendo que as linhas físicas somente são aceitas se complementarem as estruturas contidas acima do maior limiar. O limiar superior é um parâmetro de fundamental importância no processo de extração, visto que ele é responsável pela permanência das linhas físicas e evita ao máximo as linhas indesejáveis. Já o limiar inferior se presta à complementação de linhas físicas encontradas no plano superior (definida pelo limiar superior) e a continuidade das mesmas são baseadas no plano inferior. Logo, ruídos presentes apenas no plano inferior não influenciam o resultado. Apesar dos limiares de histerese serem responsáveis pela eliminação de boa parte das linhas espúrias, a eliminação final dessas linhas será realizada pela etapa seguinte, com a escolha automática do melhor sigma. 3ª) Detecção de Linhas com seleção automática de escala: Nesta etapa, o método de detecção de linhas de Steger é utilizado para detectar linhas na imagem contendo a estrutura de rodovias realçadas. Para utilização deste método é necessário inserir três parâmetros: desvio-padrão (σ ) e os limiares de histerese ( 1 2,τ τ ), sendo que estes últimos foram adquiridos na etapa anterior. Para selecionar os pontos mais importantes que possivelmente representam uma rodovia, é necessário estimar um desvio-padrão que possibilite salientar essas linhas. Assim, Steger (2000) estabeleceu que as linhas mais importantes prevaleçam quando 3 wσ ≥ , em que w é a semi-largura da linha. No entanto, se numa imagem têm-se rodovias principais de semi-largura pw e rodovias secundárias de semi- largura sw , sendo p sw >> w , então nessas condições pσ não seria ideal para rodovias secundárias, pois estas não seriam detectadas. Por outro lado, se sσ for escolhido, manteria ambos os tipos de rodovia, mas certamente ficaria uma quantidade indesejável de linhas espúrias. Sendo assim, a escolha da escala ótima não é algo tão trivial e tem influência na eficiência da metodologia para a extração automática das rodovias. Dessa forma, o processo de extração se torna dependente da intervenção do operador humano para a escolha ótima da escala. Este fator implica na necessidade de Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Extração automática de segmentos lineares de rodovias... 3 6 2 desenvolvimentos adicionais, a fim de se obter automaticamente, ou seja, sem intervenção humana, um valor de escala ideal em função da quantidade de detalhes espúrios contidos na imagem. Nesse contexto, é proposto um critério para a eliminação de linhas espúrias presentes nas imagens processadas, baseado no seguinte princípio: as linhas espúrias geralmente possuem valor de magnitude de segunda derivada bem menores que as linhas físicas. Esse princípio pode, em linhas gerais, dar origem ao seguinte algoritmo: 1. Vetorizar o mapa de linhas gerado pelo detector de Steger; 2. Para cada cadeia de linhas detectada, calcula-se o valor médio (Md) da segunda derivada com o auxílio da interpolação bilinear, visto que, o processo de vetorização fornece resultados sub-pixel; 3. Encontrar o maior valor médio da segunda derivada (Gmáx) das cadeias e o menor valor (Gmin), para posteriormente obter a amplitude entre os valores médios das magnitudes da segunda derivada, ou seja: Amplitude = Gmáx - Gmin (10) 4. Dividir a amplitude em, por exemplo, 100 classes, possibilitando uma descrição fiel das freqüências do valor médio, visto que, todas as cadeias de linha extraídas serão classificadas em diversas classes conforme o valor da segunda derivada, sendo possível criar um histograma de freqüência das cadeias de linhas; 5. Ordenar os dados dos valores médios da segunda derivada; 6. Calcular a mediana ( Mr ) da segunda derivada; 7. Obter os extremos do intervalo [ ]*min minG ,2 Mr - G através da análise das freqüências, sendo que apenas as cadeias pertencentes a este intervalo serão alvos da purificação. Figura 7 - Descrição da freqüência do valor médio conforme a variação do sigma: (a) Variação da freqüência para σ ; (b) Variação da freqüência para σ σ>2 ; (c) Variação da freqüência para σ σ>3 2 ; (d) Variação da freqüência para σ σ>4 3 . (a) (b) (c) (d) Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Ishibashi, R. e Dal Poz, A. P. 3 6 3 As linhas espúrias deverão gerar um pico único e proeminente nas proximidades de Mr, principalmente para escalas finas. Iniciando com um fator de escala fino (por exemplo, 1σ = ), proceder ao longo da escala, através do incremento do sigma, até que o pico seja achatado, como mostra a figura 7. Um critério de parada poderia ser quando, por exemplo, 99% das cadeias com segunda derivada média pertencente ao intervalo, ou seja, de até sejam pulverizados à medida que se move na direção de escalas mais grosseiras. As linhas físicas normalmente possuem valores médios da segunda derivada maiores, sendo assim, suas classes de freqüências localizam-se a direita do pico de freqüência. minG min2* Mr - G 4ª) Pós-processamento baseado em limiarização por comprimento: Com o pré-processamento de realce, muitos ruídos também são realçados, resultando em linhas espúrias indesejáveis, geralmente de pequenos comprimentos que prejudicam a qualidade da extração. Para melhorar esta qualidade, após a detecção das cadeias com escolha automática de limiares de histerese ( 1 2,τ τ ) e escala (σ ), pode-se aplicar um processo de limiarização por comprimento visando eliminar quase que totalmente as linhas espúrias, cujos comprimentos estejam abaixo de um limiar. 5ª) Pós-processamento baseado em poligonização: As rodovias em imagens digitais apresentam-se como faixas suaves, podendo ser modeladas eficientemente por linhas poligonais. Assim, após o processo de detecção de linhas, pode-se aplicar um algoritmo de poligonização, para reduzir significativamente o número de pontos de linhas previamente detectadas, mas mantendo a qualidade geométrica das linhas. O resultado do processo descrito é um conjunto de linhas poligonais representando geralmente segmentos de rodovias. Vale ressaltar que a complementação (reconstrução de falsos negativos, reconstrução de cruzamentos de rodovias e eliminação de falsos positivos) não é alvo da metodologia proposta. 4. RESULTADOS E ANÁLISES A metodologia proposta para extração de segmentos de rodovias foi testada em inúmeras imagens de resoluções variadas. A seguir são apresentados os resultados obtidos com três imagens (uma de baixa resolução, outra de média resolução e outra de alta resolução). Os resultados experimentais serão analisados visual e numericamente, sendo que em ambos os casos os parâmetros de qualidade de interesse são a completeza e a correção. A análise visual é realizada através da superposição dos vetores extraídos sobre a imagem original. A análise numérica é realizada a partir da comparação numérica entre os segmentos de rodovia extraídos pela metodologia proposta e os segmentos de rodovia extraídos por digitalização manual. A partir destes dois conjuntos de resultados, especifica-se os seguintes parâmetros de análise: Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Extração automática de segmentos lineares de rodovias... 3 6 4 − Completeza (COM): razão entre o comprimento total dos segmentos extraídos pela metodologia e o comprimento total de segmentos de rodovias de referências extraídos manualmente. − Correção (COR): A correção é definida como a razão entre o comprimento total dos segmentos de rodovias extraídos corretamente e o comprimento total dos segmentos de rodovias extraídos. A imagem teste 1 (figura 8) é uma imagem aérea de alta resolução, contendo rodovias de aproximadamente 33 pixels de largura e dimensão de 535x498 pixels. O valor obtido automaticamente para o sigma da função gaussiana é igual a 11,5, com limiares de histerese ( 1 2,τ τ ) iguais a 0,04 e 0,17. Observa-se que uma grande quantidade de detalhes espúrios foi eliminada através do processo de extração automática. Como mostra a figura 8a, o valor unitário para o sigma gera um resultado bastante confuso. Isto ocorre porque para este valor de sigma geralmente os ruídos praticamente não são atenuados. A figura 8b mostra que a restrição de escala mínima ( 3/w≥σ ) propiciou um resultado inferior ao obtido (figura 8c) pela metodologia proposta. Nota-se também que na figura 8c algumas regiões foram extraídas erroneamente (falsos positivos). A metodologia é vulnerável a estes tipos de erros, pois o extrator confunde estas regiões com as regiões de interesse. Figura 8 - Experimento realizado com a imagem teste 1: (a) Resultado da extração com sigma igual a 1,0; (b) Resultado da extração para o menor sigma aceito pela restrição de escala mínima 3 wσ ⎛ ≥⎜ ⎝ ⎠ ⎞ ⎟ igual a 9,5; (c) Resultado da extração para o sigma selecionado automaticamente igual a 11,5; (d) Sobreposição. (a) (b) Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Ishibashi, R. e Dal Poz, A. P. 3 6 5 Cruzamento Falsos Positivos (c) (d) Efetuando a análise visual do resultado sobreposto na imagem de entrada (figura 8d), pode-se notar problemas na extração na região de cruzamento e em um pequeno trecho no limite da rodovia superior direita. O problema verificado com a extração do cruzamento é geralmente esperado porque nestas regiões, principalmente em se tratando de imagens de alta-resolução, o modelo de linhas (Seção 2.1) não se verifica. Vale lembrar que, conforme foi estatuído na Seção 1 (Introdução), a extração de cruzamentos de rodovias está fora do escopo deste trabalho. A eficiência da metodologia proposta foi examinada também através da análise numérica, na qual foram avaliadas a completeza e a correção. Devido à falha do trecho no limite da rodovia superior direita, o parâmetro de completeza atingiu 97%, já o percentual de correção atingiu 100% devido à qualidade geométrica das linhas extraídas. A imagem teste 2 é uma imagem de média resolução, adquirida pelo satélite Ikonos com dimensão de 546x341. Nesta imagem, as rodovias possuem largura média de 4 pixels, podendo-se notar em suas adjacências algumas regiões com solo exposto de semelhante resposta espectral das rodovias. Para esta imagem, o valor do desvio-padrão calculado automaticamente é igual a 2,0 e os valores menor e maior de histerese ( 1 2,τ τ ) obtidos são 0,9 e 5,4. O resultado obtido é bastante satisfatório, já que poucos falsos positivos foram extraídos (figura 9c). Notar que o resultado obtido usando o sigma unitário (figura 9a) é bem inferior ao obtido (figura 9b) usando o sigma dado pala restrição de escala mínima ( 3/w≥σ ). Por sua vez, este último resultado é bem inferior ao resultado final (figura 9c) obtido pela metodologia proposta. Neste experimento, existem alguns falsos positivos (figura 9c) provindos de regiões que se confundem com a entidade rodovia e alguns problemas geométricos Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Extração automática de segmentos lineares de rodovias... 3 6 6 de extração causados pela diferença de contraste lateral e pela variação da largura de um pequeno trecho da rodovia. Figura 9 - Resultado da Extração: (a) Resultado da extração para o sigma igual a 1,0; (b) Resultado da extração para o menor sigma aceito pela restrição de escala mínima ( 3 1, 5wσ == ); (c) Resultado da extração com sigma igual a 2,0. (a) (b) (c) Exemplo de Falsos Positivos Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Ishibashi, R. e Dal Poz, A. P. 3 6 7 Como os falsos positivos possuem pequenas extensões, eles podem facilmente ser eliminados através da limiarização por comprimento de cadeias. Neste caso aplicou-se um limiar igual a 10w. A figura 10 mostra o resultado final obtido após a etapa de limiarização por comprimento. Figura 10 - Sobreposição da imagem resultante após limiarização. Os parâmetros de qualidade de completeza e correção atingiram respectivamente 100% e 97%, comprovando dessa forma o bom desempenho da metodologia neste experimento. Figura 11 – Imagem realçada. Imagem Original Imagem Realçada Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Extração automática de segmentos lineares de rodovias... 3 6 8 A imagem teste 3 é uma imagem de baixa resolução adquirida pelo Satélite Sino-Brasileiro CBERS, de 630x370 pixels com uma rodovia de largura média de 2 pixels. Como em imagens de baixa resolução geralmente as rodovias apresentam-se pouco pronunciadas, é necessário um pré-processamento de realce para acentuar os detalhes. A figura 11 apresenta o resultado do pré-processamento de realce aplicado à imagem em questão. A figura 12 apresenta os resultados obtidos para a imagem teste 3 com sigma igual a 0,7 (figura 12a) e para o sigma obtido automaticamente igual a 1,5 (figura 12b), com limiares de histerese iguais a 4,80 e 26,80. Figura 12 - Resultado da extração: (a) Extração para escala fina igual a 0,7; (b) Extração para o sigma obtido automaticamente igual a 1,5. Exemplo de Falsos Positivos (b) (a) A linha extraída possui algumas irregularidades causadas por pequenos trechos contendo respostas espectrais diferenciadas que são aguçadas durante o processo de realce. Já os falsos positivos são facilmente eliminados através da limiarização por comprimento. O limiar usado neste teste é igual a 30w. O resultado obtido é visualizado na figura 13. Após o processo de limiarização das pequenas cadeias, o parâmetro de completeza atingiu 100% e de correção 95%, sendo este último valor decorrente das irregularidades contidas na linha extraída. Notar que no canto inferior direto (figura Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Ishibashi, R. e Dal Poz, A. P. 3 6 9 11) existe uma rodovia bastante sinuosa e tênue. O método de realce não conseguiu realçar esta rodovia a ponto de permitir sua detecção pelo detector de Steger. Portanto, os parâmetros de qualidade não estão levando em conta este falso negativo. Mesmo após a limiarização, alguns falsos positivos de grande extensão ainda mantiveram-se no resultado da extração, totalizando 15% do total de cadeias extraídas (figura 13). Figura 13 - Sobreposição da imagem resultante da limiarização sobreposta a imagem original. 5. CONCLUSÃO Neste trabalho foram apresentadas as características básicas do detector de linhas baseado em bordas paralelas, bem como os métodos utilizados para a seleção automática dos limiares de histerese e dos fatores de escalas para detecção de rodovias com precisão sub-pixel. A metodologia para a seleção automática dos limiares de histerese e escala, mostrou-se eficiente ao ser aplicada em imagem de alta resolução. Poucos falsos positivos, decorrentes das regiões com mesmo padrão geométrico e espectral das feições de interesse, foram detectados. A região de cruzamento, contida na imagem teste, foi responsável pela geração de descontinuidades das vias extraídas. Entretanto, o objetivo do trabalho é a extração dos eixos de rodovias e não as regiões contendo os cruzamentos de rodovias. Dessa forma a qualidade dos resultados obtidos foi boa, tendo em vista que parâmetro de completeza atingiu 97% e o de correção 100%. O experimento realizado com a imagem de média resolução apresentou também bom resultado, visto que apenas alguns falsos positivos foram detectados. Entretanto, como estes falsos positivos possuem pequeno comprimento, os mesmos foram facilmente eliminados pela limiarização por comprimento das cadeias. Este Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Extração automática de segmentos lineares de rodovias... 3 7 0 experimento obteve parâmetros de qualidade de completeza e correção, respectivamente, iguais a 100% e 97%, evidenciando assim um bom desempenho da metodologia proposta. Para a imagem de baixa resolução, o pré-processamento de realce acarretou também o aguçamento das pequenas áreas não correspondentes às rodovias, resultando na extração de linhas espúrias (falsos positivos). Como estes falsos positivos possuem pequenas extensões, eles foram quase que totalmente eliminados pelo processo de limiarização por comprimento, melhorando a qualidade da extração. O parâmetro de completeza atingiu o valor ótimo de 100%. Já o parâmetro de correção atingiu 95% devido aos deslocamentos sofridos pela linha extraída. De forma geral, os experimentos realizados com imagens de diferentes resoluções, incluindo os que não foram apresentados neste artigo, apresentaram desempenho satisfatório, comprovado pelos parâmetros médios de completeza igual a 90% e de correção igual a 96%. Estes valores foram afetados principalmente por regiões contendo anomalias, tais como: sombras, oclusões (árvores, automóveis etc.), estradas rurais e regiões de cruzamentos. Regiões como estas acarretam irregularidades no processo de extração, tais como, descontinuidades, deslocamentos e extração de falsos positivos/negativos que prejudicam a qualidade de extração. A metodologia proposta provou então ser eficiente na extração de segmentos de rodovias em cenas rurais, proporcionando resultados satisfatórios de maneira inteiramente automática. Os resultados obtidos poderão ser tratados por metodologias automáticas de complementação, como a apresentada por Vale (2007), que busca reconstruir, através da análise topológica, as falhas nas conexões e nos cruzamentos dos segmentos de rodovias extraídos. AGRADECIMENTOS Os autores gostariam de manifestar seus agradecimentos à Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) pelo apoio financeiro a esta pesquisa sob o processo n. 2005/03184-9 (mestrado). REFERÊNCIAS BIBLIOGRÁFICAS AGOURIS, P.; GYFTAKIS, S.; STEFANIDIS, A. Using a fuzzy supervisor for object extraction within an integrated geospatial environment. In: International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, v. 22, Part III/1, p. 191-195, 1998. AGOURIS, P.; GYFTAKIS, S.; STEFANIDIS, A. Quality-aware deformable models for change detection. IEEE International Conference on Image Processing. Thessaloniki, v. 2, p. 805-808, 2001. AMINI, J.; SARADJIAN, M. R.; BLAIS, J. A. R.; LUCAS, C.; AZIZI, A. Automatic road side extraction from large scale image maps. International Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Ishibashi, R. e Dal Poz, A. P. 3 7 1 Journal of Applied Earth Observation and Geoinformation, v. 4, pp. 95–107, 2002. BAJCSY, R.; TAVAKOLI, M. Computer recognition of roads from satellite pictures. IEEE Transactions on Systems, Man, and Cybernetics, v. 6, n. 9, p. 76- 84, 1976. BAUMGARTNER, A.; STEGER, C.; MAYER, H.; ECKSTEIN, W.; EBNER, H. Automatic road extraction based on multi-scale, grouping, and context. Photogrammetric Engineering and Remote Sensing, v. 65, n. 7, p. 777-785, 1999. DAL POZ, A. P.; VALE, G. M. Dynamic programming approach for semi- automated road extraction from mediumand high-resolution images. In: International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, v. 34, Part 3/W8, p. 87-92, 2003. DAL POZ, A. P.; GALLIS, R. B.; SILVA, J. F. C. Semiautomatic road extraction by dynamic programming optimisation in the object space: Single image case. In: International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, v. 36, pp. 215-220, 2006. GRUEN, A.; LI, H. Semi-automatic linear feature extraction by dynamic programming and LSB-snakes. Photogrammetric Engineering & Remote Sensing, v.63, n.8, p. 985–995, 1997. HINZ, S.; WIEDEMANN, C.; BAUMGARTNER A. A scheme for road extraction in rural areas and its evaluation. In: V IEEE Workshop on Applications of Computer Vision, Palm Spring, p.134-139. 2000. HINZ, S.; BAUMGARTNER, A.; MAYER, H.; WIEDEMANN, C.; EBNER, H. Road Extraction Focussing on Urban Areas. In: Automatic Extraction of Man- Made Objects From Aerial and Space Images, p. 255-265, 2001. HU, J.; RAZDAN, A.; FEMIANE, J. C.; CUI, M.; WONKA, P. Road network extraction and intersection detection from aerial images by tracking road footprints. IEEE Transaction on Geosciences and Remote Sensing, v. 50, n. 12, p. 4144-4157, 2007. ISHIBASHI, R. Extração de segmentos de rodovias em imagens de resoluções variadas usando o princípio de bordas paralelas. 2008. 136 f. Dissertação (Mestrado em Ciências Cartográficas) - Universidade Estadual Paulista Júlio de Mesquita Filho. ISHIKAWA, A. S.; Detecção de rodovias em imagens digitais de alta resolução com o uso da teoria de morfologia matemática. 2008. 111 f. Dissertação (Mestrado em Ciências Cartográficas) - Universidade Estadual Paulista Júlio de Mesquita Filho. KOVALEVSKII, V. A. An optimal recognition algorithm for some sequences of patterns. Cybernetics and Systems Analysis, v.3, n.4, p. 62-66, 1967. Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. Extração automática de segmentos lineares de rodovias... 3 7 2 MOHAMMADZADEH, A.; TAVAKOLI, A.; ZOEJ, M. J. V. Road extraction based on fuzzy logic and mathematical morphology from pan-sharpened ikonos images. The Photogrammetric Record, v. 21, n. 113, p. 44-60, 2006. MOKHTARZDAE, M.; ZOEJ, M. J. V. Road detection from high resolution satellite images using artificial neural networks. International journal of applied earth observation and geoinformation, v.9, n. 1, p. 32-40, 2007. STEGER, C. An unbiased detector of curvilinear structures. IEEE Transactions on Pattern Analysis and Machine Intelligence, v. 20, n. 2, p. 62-75, 1998. STEGER, C, Subpixel – Precise extraction of lines and edges. In: International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, v. 33, Part B3, p. 141-156, 2000. SONG, W, KELLER, J. M.; HAITHCOAT, T. L.; DAVIS, C. H. Automated geospatial conflation of vector road maps to high resolution imagery. IEEE Transactions on Image Processing, v.18, n. 2, p. 388-400, 2009. TOMMASELLI, A. M. G. Um método recursivo aplicado ao problema de localização em Visão de Máquina. 1993. Tese (Doutorado em engenharia elétrica), Faculdade de Engenharia Elétrica da Universidade Estadual de Campinas - UNICAMP. VALE, G. M. Uso de técnicas de otimização e agrupamento hierárquico para a complementação automática da malha viária em regiões rurais a partir de imagens aéreas de média e alta resolução. 2007. 184 f. Tese (Doutorado em Ciências Cartográficas) - Universidade Estadual Paulista Júlio de Mesquita Filho. YAMADA, H.; MERRITT, C., KASVAND, T. Recognition of kidney glomerulus by dynamic programming matching method. IEEE Transactions on Pattern Analysis and Machine Intelligence, v. 10, n. 5, p. 731-737, 1988. ZHOU, J; BISCHOF, W. F.; CAELLI, T. Road tracking in aerial images based on human-computer interaction and Bayesian filtering. ISPRS Journal of Photogrammetry and Remote Sensing, v. 61, n. 2, p. 108-124, 2006. (Recebido em outubro / 2008. Aceito em maio / 2009). Bol. Ciênc. Geod., sec. Artigos, Curitiba, v. 15, no 3, p.352-372, jul-set, 2009. http://www.labmeeting.com/papers/author/song-w http://www.labmeeting.com/papers/author/keller-jm http://www.labmeeting.com/papers/author/haithcoat-tl http://www.labmeeting.com/papers/author/davis-ch http://www.labmeeting.com/paper/28650678/song-2009-automated-geospatial-conflation-of-vector-road-maps-to-high-resolution-imagery http://www.labmeeting.com/paper/28650678/song-2009-automated-geospatial-conflation-of-vector-road-maps-to-high-resolution-imagery RESUMO ABSTRACT