UNIVERSIDADE ESTADUAL PAULISTA Faculdade de Ciências e Tecnologia Programa de Pós-Graduação em Ciências Cartográficas ÉRICO FERNANDO DE OLIVEIRA MARTINS Extração Semi-Automática de Rodovias no Espaço-Objeto: Uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Presidente Prudente 2010 UNIVERSIDADE ESTADUAL PAULISTA Faculdade de Ciências e Tecnologia Programa de Pós-Graduação em Ciências Cartográficas ÉRICO FERNANDO DE OLIVEIRA MARTINS Extração Semi-Automática de Rodovias no Espaço-Objeto: Uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Presidente Prudente 2010 Dissertação apresentada ao programa de Pós- Graduação em Ciências Cartográficas da Faculdade de Ciências e Tecnologia da UNESP, como parte dos requisitos para a obtenção do título de Mestre em Ciências Cartográficas. Orientador: Prof. Dr. Aluir Porfírio Dal Poz Martins, Érico Fernando de Oliveira. 336e Extração semi-automática de rodovias no espaço-objeto : uso integrado de um estéreo par de imagens aéreas e um MDT / Érico Fernando de Oliveira Martins. - Presidente Prudente : [s.n], 2010 97 f. : il Orientador: Aluir Porfírio Dal Poz Dissertação (mestrado) - Universidade Estadual Paulista, Faculdade de Ciências e Tecnologia Inclui bibliografia 1. Imagens aéreas. 2. Extração de feição. 3. Extração de rodovia. 4. Modelo de rodovia. 5. Programação dinâmica. I. Martins, Érico Fernando de Oliveira. II. Universidade Estadual Paulista. Faculdade de Ciências e Tecnologia. III. Título. CDD 623.72 Ficha catalográfica elaborada pela Seção Técnica de Aquisição e Tratamento da Informação- Serviço Técnico de Biblioteca e Documentação - UNESP, Câmpus de Presidente Prudente. DADOS CURRICULARES Érico Fernando de Oliveira Martins Nascimento: 15/10/1978 Filiação: José Afonso Martins Guazi. Marlene de Oliveira Martins. 1997-2002 Curso de Graduação Licenciatura Plena em Matemática Universidade do Estado de Mato Grosso 2008-2010 Curso de Pós-Graduação Mestrado em Ciências Cartográficas Linha de Pesquisa: Computação de Imagens Faculdade de Ciências e Tecnologia – UNESP DEDICATÓRIA À minha esposa Simone Pysklevitz, meu irmão Ariel Fernando e meus estimados pais, José Afonso e Marlene. AGRADECIMENTOS Meus agradecimentos a todos que em algum momento colaboraram com esta pesquisa, em particular: À minha esposa Simone, pelo amor, compreensão e incentivo durante todo o processo, inclusive nos períodos em que estivemos distantes. Ao meu irmão Ariel e sua família, por me acolher com tanto carinho. Aos meus pais José Afonso e Marlene, pelo apoio incondicional. Ao professor orientador Aluir Porfírio Dal Poz, por confiar em meu trabalho, direcionar minhas ações e servir de exemplo profissional. Aos demais professores do Programa de Pós-Graduação em Ciências Cartográficas: Amilton Amorim, Antonio Maria Garcia Tommaselli, Erivaldo Antonio da Silva, João Carlos Chaves, João Francisco Galera Monico, João Fernando Custódio da Silva, Julio Hasegawa, Maria de Lourdes, Maurício Galo, Messias Meneguette Junior, Milton Shimabukuro, Mônica Decanini, Nilton Imai e Vilma Tachibana por dividirem seu conhecimento e experiência. Aos amigos conquistados na sala de permanência: Yuri, Puga, João Paulo, Fazan, Guilherme, Cris, Marcelo Gaúcho, Eduardo, Fabinho, Tati, Lauri, Tiedtke, Letícia, Adilson, Luiz Henrique (do Espaço Fama) e muitos outros que foram minha família em Prudente e jamais serão esquecidos. Aos amigos Rodrigo Gallis, Roberto Ruy, Juliano Fazan e Fábio Feliciano, pelas importantes colaborações, dicas e discussões realizadas durante o desenvolvimento da pesquisa. Vocês foram de fundamental importância. Aos professores e hoje colegas de trabalho Rodrigo Bruno Zanin e Wilson Santana Cunha, por sempre terem acreditado que isto seria possível. Aos funcionários da Seção de Pós-Graduação: Marcia, Ivonete, André, Erynat e Cinthia, pelo atendimento sempre solícito. À Unesp, por ofertar o Programa de Pós-Graduação em Ciências Cartográficas de forma pública, gratuita e com excelência reconhecida. À Universidade do Estado de Mato Grosso, em especial aos colegas dos Departamentos de Administração, Contabilidade e Matemática, por viabilizarem esta conquista. RESUMO Nesta pesquisa é proposta uma metodologia semi-automática para extração de rodovias a partir de um estéreo par de imagens aéreas de baixa resolução e do respectivo Modelo Digital de Terreno, tendo por base a otimização por programação dinâmica no espaço-objeto. A metodologia consiste em um processo iterativo iniciado com pontos sementes fornecidos pelo operador no espaço-imagem, que após transformação para o espaço-objeto passam por ciclos de otimização via Programação Dinâmica até descreverem o eixo da rodovia. O desempenho da metodologia foi testado por meio de experimentos com dados reais, cujos resultados foram avaliados tanto na forma visual (qualitativamente) como numérica (quantitativamente). Os resultados alcançados nos experimentos demonstraram a robustez da metodologia diante de problemas de caráter geométrico e radiométrico comuns na extração semi-automática de rodovias a partir de imagens aéreas. Problemas de oclusão e baixa resposta radiométrica foram minimizados pelo uso de injunções globais, de natureza geométrica, bem como pela redundância e complementação de dados radiométricos provenientes das imagens que compõem o estéreo par. As linhas de busca multiresolução e os critérios de parada das iterações se mostraram como sendo importantes recursos na tentativa de conciliar extração de qualidade com baixo esforço computacional. Palavras-chave: Programação dinâmica; modelo de rodovia; extração de feição; extração de rodovia; imagens aéreas. ABSTRACT This research proposes a semi-automatic methodology for road extraction by using a stereo pair of aerial images with low resolution, as well as Digital Terrain Model and dynamic programming in object-space. The methodology consists of an interactive process that starts with seed points provided by the operator in the space-image, which are later projected onto the space-object. Next, cycles of optimization are accomplished by the dynamic programming algorithm until the axis of the highway is correctly described. The performance of the methodology was tested with experiments by using real data, and results were evaluated both visually and numerically. The results achieved in the experiments have demonstrated the robustness of the methodology in face of geometrical and radiometric problems which are common in road extraction. Occlusions and low radiometric responses were minimized by the use of global geometric constraints, as well as the redundancy and complementation of radiometric data from the images that build the stereo pair. The line of multi-resolution search and stopping criteria of the interactions have showed themselves that they have been an important resort in the attempt to reconcile the extraction of high quality with low consumption of computational resources. Keywords: Dynamic programming; road model; feature extraction; road extraction; aerial images. LISTA DE FIGURAS Figura 1: Representação do espaço-imagem. Fonte: Andrade (1998). ............................................ 18 Figura 2: Sistema de coordenadas fiducial. Fonte: Wolf e Dewitt (2000).......................................... 19 Figura 3: Sistema de coordenadas da imagem.............................................................................. 20 Figura 4: Definição do sistema intermediário em uma imagem digital. Fonte: Galo (2003)................ 20 Figura 5: Sistema fotogramétrico do positivo fotográfico. Fonte: Lugnani (1987). ............................. 22 Figura 6: Sistema fotogramétrico do negativo. Fonte: Lugnani (1987). ............................................ 22 Figura 7: Representação gráfica da distorção radial simétrica. Fonte: Andrade (1998)..................... 26 Figura 8: Distorção radial e as correções em x e y. Fonte: adaptado de Wolf e Dewitt (2000)........... 26 Figura 9: Componentes da distorção descentrada. Fonte: Andrade (1998)...................................... 27 Figura 10: Refração atmosférica em fotografia aérea. Fonte: Wolf e Dewitt (2000). ......................... 29 Figura 11: Efeito da curvatura da superfície terrestre. Fonte: Mikhail et al. (2001)............................ 31 Figura 12: Ilustração das três superfícies de referência. Fonte: Wolf e Dewitt (2000). ...................... 32 Figura 13: Coordenadas geodésicas. Fonte: Wolf e Dewitt (2000). ................................................. 33 Figura 14: Relação entre sistema geodésico e geodésico cartesiano. Fonte: Wolf e Dewitt (2000). ... 33 Figura 15: Sistema cartesiano local e sua relação com o geocêntrico e o geodésico. Fonte: Wolf e Dewitt (2000). ............................................................................................................................. 34 Figura 16: Cilindro secante da Projeção UTM. Fonte: http://commons.wikimedia.org. ...................... 35 Figura 17: Condição de colinearidade. Fonte: Wolf e Dewitt (2000). ............................................... 42 Figura 18: Problema clássico de programação dinâmica. Fonte: Li (1997). ..................................... 45 Figura 19: extração da rodovia no espaço-objeto. Fonte: Gallis (2006). .......................................... 50 Figura 20: Diagrama de Voronoi e Triangulação de Delaunay. Fonte: Li et al. (2004)....................... 56 Figura 21: Níveis de continuidade na união de duas curvas. Fonte: Azevedo e Conci (2003). .......... 57 Figura 22: A função B-Spline não passa pelos pontos de controle. Fonte: Azevedo e Conci (2003). . 58 Figura 23: Reconstrução por estéreo par e MDT da cena contendo a rodovia. ................................ 60 Figura 24: (a) Linha poligonal definida por três pontos sementes.(b) Dois novos vértices interpolados. .................................................................................................................................................. 60 Figura 25: (a) Planos perpendiculares a linha poligonal de referência.(b) Linhas de busca definidas. 61 Figura 26: (a) Linha de busca amostrada.(b) Linha poligonal obtida pela primeira iteração............... 62 Figura 27: (a) Resultado final dos ciclos de otimização. (b) Sobreposição do resultado no MDT. ...... 63 Figura 28: Fluxograma com as etapas da metodologia proposta. ................................................... 64 Figura 29:(a) Representação na imagem.(b) Pontos sementes sobre o MDT.(c) Visão em perspectiva. .................................................................................................................................................. 65 Figura 30: (a) Pontos adensados.(b) Linhas de busca.(c) Caminho ótimo. (d) Resultado da 1ª iteração. .................................................................................................................................................. 66 Figura 31: (a) Linha poligonal formada com os pontos da 1ª iteração. (b) Pontos sobre o MDT. ....... 66 Figura 32: Linha poligonal formada com os pontos da 2ª iteração. (b) Pontos sobre o MDT. ............ 66 Figura 33: (a) Representação na imagem.(b) Eixo da rodovia sobre o MDT.(c) Visão em perspectiva. .................................................................................................................................................. 67 Figura 34: Composição com as Imagens 0667, 0669 e 0671 utilizadas nos experimentos................ 68 Figura 35: Histogramas das imagens (a) 0667, (b) 0669 e (c) 0671. ............................................... 69 Figura 36: Visão ortogonal da nuvem de pontos do modelo digital do terreno.................................. 69 Figura 37: Representação do núcleo da biblioteca Opencv. ........................................................... 71 Figura 38: Representação do núcleo da biblioteca CGAL............................................................... 72 Figura 39: (a) Janela de instruções e (b) imagem para coleta de pontos sementes.......................... 73 Figura 40: Apresentação das coordenadas dos pontos sementes em ambos os espaços. ............... 73 Figura 41: (a) Informações sobre a progressão do processo e (b) finalização da extração. .............. 74 Figura 42: (a) Distâncias entre pontos no eixo. (b) Deslocamentos dos pontos entre as iterações. ... 74 Figura 43: (a) MDT com o eixo sobreposto.(b) Ampliação com visão ortogonal e (c) em perspectiva.75 Figura 44: (a, b, c) Diferentes configurações de pontos sementes. (d, e, f) Respectivos resultados para as três configurações de pontos sementes. ........................................................................... 76 Figura 45: Quatro pontos sementes fornecidos em diferentes posições. ......................................... 77 Figura 46: (a) Imagem da esquerda do primeiro estéreo par. (b) Malha extraída do estéreo par. ...... 79 Figura 47: (a) Imagem da esquerda do segundo estéreo par. (b) Malha extraída do estéreo par. ..... 80 Figura 48: (a) Pontos sementes e (b) respectivo eixo extraído no TC1............................................ 82 Figura 49: (a) Pontos sementes e (b) respectivo eixo extraído no TC2............................................ 82 Figura 50: (a) Pontos sementes e (b) respectivo eixo extraído no TC3............................................ 82 Figura 51: (a) Pontos sementes e (b) respectivo eixo extraído no TC4............................................ 83 Figura 52: (a) Pontos sementes e (b) respectivo eixo extraído no TM1. .......................................... 85 Figura 53: (a) Pontos sementes e (b) respectivo eixo extraído no TM2. .......................................... 86 Figura 54: (a) Pontos sementes e (b) respectivo eixo extraído no TM3. .......................................... 86 Figura 55: (a) Pontos sementes e (b) respectivo eixo extraído no TM4. .......................................... 87 Figura 56: Recorte na (a,c) imagem da esquerda e na (b,d) imagem direita do estéreo par.............. 89 Figura 57: (a) Pontos sementes e (b) respectivo eixo extraído no TL1. ........................................... 90 Figura 58: (a) Pontos sementes e (b) respectivo eixo extraído no TL2. ........................................... 91 LISTA DE TABELAS Tabela 1: Resumo das extrações de trechos curtos (TC). .............................................................. 81 Tabela 2: Resultados da análise numérica nos trechos curtos (TC). ............................................... 84 Tabela 3: Resumo das extrações de trechos médios (TM). ............................................................ 85 Tabela 4: Resultados da análise numérica nos trechos médios (TM). ............................................. 87 Tabela 5: Resumo das extrações de trechos longos (TL). .............................................................. 89 Tabela 6: Resultados da análise numérica nos trechos longos (TL). ............................................... 91 SUMÁRIO 1 INTRODUÇÃO .................................................................................................................15 1.1 CONSIDERAÇÕES INICIAIS ......................................................................................................... 15 1.2 OBJETIVOS ........................................................................................................................... 17 1.3 ESTRUTURA DO TRABALHO ....................................................................................................... 17 2 FUNDAMENTAÇÃO TEÓRICA ..........................................................................................18 2.1 INTRODUÇÃO ........................................................................................................................ 18 2.2 SISTEMAS DE COORDENADAS NO ESPAÇO-IMAGEM ........................................................................ 18 2.2.1 SISTEMA FIDUCIAL .................................................................................................................. 19 2.2.2 SISTEMA DE IMAGEM ............................................................................................................... 20 2.2.3 SISTEMA FOTOGRAMÉTRICO .................................................................................................. 21 2.3 REFINAMENTO DE COORDENADAS.............................................................................................. 23 2.3.1 DEFORMAÇÕES DO FILME....................................................................................................... 23 2.3.2 DESLOCAMENTO DO PONTO PRINCIPAL ................................................................................ 24 2.3.3 DISTORÇÃO DAS LENTES ........................................................................................................ 25 2.3.4 DISTORÇÕES DEVIDO A REFRAÇÃO ATMOSFÉRICA .............................................................. 28 2.3.5 EFEITO DA CURVATURA TERRESTRE ..................................................................................... 30 2.4 SISTEMAS DE COORDENADAS NO ESPAÇO-OBJETO ......................................................................... 31 2.4.1 SISTEMA GEODÉSICO ............................................................................................................. 32 2.4.2 SISTEMA GEODÉSICO CARTESIANO....................................................................................... 33 2.4.3 SISTEMA GEODÉSICO CARTESIANO LOCAL ........................................................................... 34 2.4.4 SISTEMA DE PROJEÇÃO UTM ................................................................................................ 34 2.5 TRANSFORMAÇÕES DE COORDENADAS NO ESPAÇO-OBJETO ............................................................. 36 2.5.1 TRANSFORMAÇÕES ENTRE UTM E TM.................................................................................. 36 2.5.2 TRANSFORMAÇÕES ENTRE TM E GEODÉSICA ...................................................................... 36 2.5.3 TRANSFORMAÇÕES ENTRE COORDENADA GEODÉSICA E GEODÉSICA CARTESIANA ......... 39 2.5.4 TRANSFORMAÇÕES ENTRE COORDENADAS GEODÉSICA CARTESIANA E GEODÉSICA CARTESIANA LOCAL ............................................................................................................................. 40 2.6 RELAÇÃO ENTRE COORDENADAS NO ESPAÇO-OBJETO E ESPAÇO-IMAGEM............................................ 41 2.6.1 TRANSFORMAÇÕES DE COORDENADAS ENTRE ESPAÇO-IMAGEM E ESPAÇO-OBJETO ...... 41 2.6.2 TRANSFORMAÇÃO DE COORDENADAS UTM PARA COORDENADAS DE IMAGEM.................. 43 2.7 PROGRAMAÇÃO DINÂMICA ...................................................................................................... 44 2.8 MODELOS MATEMÁTICOS DE RODOVIA....................................................................................... 46 2.8.1 MODELO MATEMÁTICOS DE RODOVIA NO ESPAÇO-IMAGEM.................................................. 46 2.8.2 MODELO MATEMÁTICO DE RODOVIA NO ESPAÇO-OBJETO PARA UMA IMAGEM ISOLADA ..... 48 2.8.3 MODELO MATEMÁTICO DE RODOVIA NO ESPAÇO-OBJETO PARA UM ESTÉREO PAR DE IMAGENS................................................................................................................................................ 49 2.9 MODELAGEM DE SUPERFÍCIE..................................................................................................... 52 2.9.1 FONTES DE DADOS PARA GERAÇÃO DO MDT ...................................................................... 53 2.9.2 ESTRUTURAS DE DADOS PARA MDT’S .................................................................................. 54 2.10 B-SPLINE............................................................................................................................ 57 3 METODOLOGIA PARA EXTRAÇÃO DE RODOVIAS ..........................................................59 3.1 CONSIDERAÇÕES INICIAIS ......................................................................................................... 59 3.2 METODOLOGIA PROPOSTA....................................................................................................... 59 3.3 DESCRIÇÃO ILUSTRATIVA DA METODOLOGIA................................................................................. 64 4 EXPERIMENTOS E ANÁLISE DOS RESULTADOS ............................................................68 4.1 CONSIDERAÇÕES INICIAIS ......................................................................................................... 68 4.2 DADOS UTILIZADOS ................................................................................................................ 68 4.3 ASPECTOS COMPUTACIONAIS.................................................................................................... 70 4.4 INICIALIZAÇÃO DO PROCESSO .................................................................................................... 76 4.5 FORMAS DE ANÁLISE DOS RESULTADOS ....................................................................................... 77 4.6 EXPERIMENTOS E ANÁLISE DOS RESULTADOS ................................................................................ 79 4.6.1 EXTRAÇÕES DE TRECHOS CURTOS ..................................................................................................... 81 4.6.2 EXTRAÇÃO DE TRECHOS MÉDIOS ...................................................................................................... 84 4.6.3 EXTRAÇÕES DE TRECHOS LONGOS .................................................................................................... 89 5 CONCLUSÕES E RECOMENDAÇÕES ..............................................................................92 6 REFERÊNCIAS ................................................................................................................94 1 INTRODUÇÃO 1.1 CONSIDERAÇÕES INICIAIS A aquisição de informações espaciais por meio de Sensoriamento Remoto, para criação e atualização de Sistemas de Informação Geográfica (SIG´s), é comumente realizada através de técnicas de extração baseadas em imagens, que são dependentes de um operador humano que realiza operações como a interpretação do conteúdo e delineamento dos objetos de interesse. Neste contexto a automação dos processos fotogramétricos pode ser entendida como uma tentativa de minimizar a participação humana nas etapas do processo de extração de dados das imagens. Os sistemas de extração de dados em imagens digitais são classificados como semi-automáticos e automáticos, dependendo do grau de automação que proporcionam. Pode ser considerado um sistema semi-automático quando o operador classifica o objeto de interesse e a tarefa de delineamento é deixada a cargo do algoritmo computacional. Como exemplo tem-se técnicas que utilizam pontos sementes posicionados pelo operador ao longo das rodovias na imagem digital, permitindo ao algoritmo identificar o contorno e o eixo desta feição. Os sistemas automáticos caracterizam-se por não haver a interferência do operador, porém, assumindo que é virtualmente impossível imitar plenamente o sistema visual humano, os sistemas automáticos sempre necessitarão de algum tipo de edição manual e validação das informações espaciais extraídas. O objeto rodovia constitui uma importante classe de informação espacial, fundamental no contexto de mapeamento e dos SIG´s. Muita pesquisa tem sido realizada desde a década de 1970, destacando-se os trabalhos pioneiros de Bajcsy e Tavakoli (1976) e Quam (1978). A maioria dos trabalhos baseia-se em problemas inteiramente formulados e resolvidos no espaço-imagem. A grande maioria destes trabalhos é de concepção semi-automática, com estratégias de delineamento sequencial ou global. As estratégias sequenciais combinam passos sucessivos de predição e refinamento para extrair ponto a ponto o eixo da rodovia, podendo-se citar como exemplos os trabalhos de McKeown e Denlinger (1988) e Kim et al. (2004). Já as estratégias globais se utilizam de alguma função objetivo para modelar todo o eixo da rodovia, utilizando os modelos de contorno ativo (KASS Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 16 et al., 1987) ou modelos derivados. Várias soluções foram propostas, como por exemplo as que se baseiam no conceito original de contorno ativo (KASS et al., 1987) ou no ajuste local de parábolas (HU et al., 2004) ou na otimização por programação dinâmica de um modelo geral de rodovia (GRUEN e LI, 1997). Por outro lado, os métodos de concepção automática geralmente requerem a integração de conhecimento contextual e de conhecimento a priori para reconhecer e delinear toda a malha viária, a fim de obter um todo topologicamente correto (BAUMGARTNER et al., 1999; HU et al., 2007). Poucas metodologias foram desenvolvidas tendo por base a formulação do problema no espaço-objeto ou em ambos os espaços: imagem e objeto. Estas metodologias podem basear-se em uma única imagem, necessariamente combinada a um MDT (Modelo Digital do Terreno), ou em duas ou mais imagens. Apesar de não ser pré-requisito, esse último caso pode beneficiar-se da integração de um MDT, tornando mais robusto o processo de extração. É possível, em ambos os casos, tratar de forma mais eficiente os problemas de oclusão e de ocorrência de falsos positivos (GRUEN e LI, 1997). Esses benefícios decorrem basicamente da facilidade em introduzir restrições de suavidade que considerem o componente vertical nos eixos das rodovias, o que não é possível para os métodos formulados no espaço-imagem. Gallis et al. (2005), Dal Poz et al. (2006) e Dal Poz et al. (2010a) propuseram uma metodologia semi-automática para a extração de rodovias no espaço-objeto utilizando uma imagem aérea e um MDT. Um modelo matemático de rodovia no espaço-objeto é formulado em dois passos. Primeiro, a rodovia é modelada no espaço-imagem considerando várias propriedades geométricas e radiométricas. Posteriormente, este modelo é modificado para descrever as rodovias no espaço-objeto, tendo por base, principalmente, o modelo do sensor. Como o modelo matemático de rodovia obtido desta forma não admite solução única, uma restrição é introduzida para forçar as rodovias extraídas a pertencerem à superfície de um MDT. Gallis (2006) e Dal Poz et al. (2010b) estenderam o método descrito de forma a utilizar somente um estéreo par com respectivos parâmetros de orientação interior e exterior, procurando estabelecer um método que fosse independente do MDT. Já o método proposto nesta pesquisa envolve os dois métodos descritos anteriormente, fazendo o uso integrado de um estéreo par de imagens aéreas de baixa resolução e um MDT. A motivação é garantir maior robustez à extração por Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 17 meio da redundância radiométrica obtida no estéreo par, e por injunções altimétricas possibilitadas pelo MDT. 1.2 OBJETIVOS Este trabalho tem por objetivo desenvolver uma metodologia semi- automática de extração do eixo da rodovia no espaço-objeto baseado na otimização por programação dinâmica, integrando um estéreo par de imagens aéreas de baixa resolução e um MDT. Os objetivos específicos são: � Desenvolver um modelo matemático de rodovia no espaço-objeto que integre um estéreo par de imagens aéreas e um MDT, � Desenvolver uma estratégia de otimização do modelo matemático de rodovia baseada em programação dinâmica; � Explorar bibliotecas computacionais que agreguem robustez às implementações; � Avaliar experimentalmente a metodologia proposta, comparando seus resultados com os obtidos por um operador humano. 1.3 ESTRUTURA DO TRABALHO Esta dissertação está estruturada em seis capítulos. O Capítulo 2 traz uma revisão bibliográfica que subsidia o desenvolvimento da metodologia proposta. Nele são apresentados tópicos de Fotogrametria, Programação Dinâmica, Modelagem de Rodovia e Ajuste de Superfície. No Capítulo 3 é apresentada e discutida a metodologia proposta. No Capítulo 4 são descritas nas implementações e os resultados obtidos na avaliação experimental da metodologia. O Capítulo 5 traz as principais conclusões a respeito dos resultados obtidos nos experimentos realizados e algumas recomendações para trabalhos futuros. Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 18 2 FUNDAMENTAÇÃO TEÓRICA 2.1 INTRODUÇÃO Neste capítulo são apresentados os fundamentos teóricos que embasam o desenvolvimento da metodologia proposta no Capítulo 3. Iniciando a fundamentação são abordadas uma séria de definições fotogramétricas clássicas (Seções 2.2 a 2.6). Em seguida são tratados os aspectos gerais da Programação Dinâmica (Seção 2.7), para posteriormente serem apresentados os Modelos Matemáticos de Rodovia (Seção 2.8) e os Modelos de Superfície (Seção 2.9), finalizando com uma breve descrição das curvas B-Spline. (Seção 2.10). 2.2 SISTEMAS DE COORDENADAS NO ESPAÇO-IMAGEM Os processos fotogramétricos fazem uso primariamente de duas categorias de sistemas de coordenadas, os Sistemas de Coordenadas do espaço- imagem e os Sistemas de Coordenadas do espaço-objeto, com seus sistemas derivados (MIKHAIL et al., 2001). De acordo com Lugnani (1987), entende-se por espaço-imagem o espaço envolvendo nodo posterior do sistema de lentes da câmera e o plano da superfície de registro da cena (negativo), e o espaço correspondente a este para o caso do diapositivo (Figura 1). Figura 1: Representação do espaço-imagem. Fonte: Andrade (1998). Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 19 Os sistemas de coordenadas do espaço-imagem convencionalmente estabelecidos na Fotogrametria são: Sistema Fiducial, Sistema de Imagem, Sistema Fotogramétrico. 2.2.1 SISTEMA FIDUCIAL Para expressar coordenadas em imagens capturadas por câmaras métricas analógicas, o sistema de referência adotado é o bidimensional de eixos cartesianos, materializado pelas marcas fiduciais fixadas rigidamente no corpo da câmara e consequentemente gravadas na imagem. A origem do sistema, denominado Centro Fiducial (CF), é estabelecida pela intersecção das linhas que unem marcas fiduciais opostas (linhas fiduciais). O eixo fx é definido como a linha fiducial mais próxima a direção de voo, sendo positiva neste sentido. O eixo fy tem sentido positivo a 90º (sentido anti-horário) do eixo fx no plano da imagem (WOLF e DEWITT, 2000). Com os eixos estabelecidos, a posição de um ponto a na imagem é indicada pelas coordenadas retangulares af x e af y , conforme mostrado na Figura 2. Figura 2: Sistema de coordenadas fiducial. Fonte: Wolf e Dewitt (2000). Para fotografias com marcas fiduciais fixadas nos cantos do quadro, após definir o CF e o eixo fx aplica-se uma rotação de 45º (sentido horário ou anti- horário) alinhando-o de forma mais próxima possível à linha voo, com o restante do sistema estabelecido da mesma maneira descrita anteriormente. Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 20 2.2.2 SISTEMA DE IMAGEM Imagens podem ser adquiridas diretamente no formato digital ou digitalizadas a partir de fotografias analógicas. Em ambos os casos, a captura é realizada por sensores que estão organizados em arranjo matricial ou linear. Cada sensor constitui um elemento de imagem conhecido como pixel (picture elements), com posição indicada por um par ordenado (coluna, linha). Este arranjo de pixels estabelece o sistema bidimensional de coordenadas de imagem ( )PP yx , , cuja origem é convencionada no canto superior esquerdo da imagem, com o eixo Px coincidindo com a primeira linha e o eixo Py coincidindo com a primeira coluna da imagem (Figura 3). Figura 3: Sistema de coordenadas da imagem. Dependendo da maneira como foi obtida a imagem digital, o Sistema de Imagem pode se relacionar de duas formas com um sistema equivalente ao Fiducial das câmaras métricas analógicas. Para as imagens capturadas diretamente no formato digital a relação é estabelecida pela translação da origem do sistema de imagem para o centro da imagem, seguida de uma reflexão no eixo y, resultando num sistema de coordenadas intermediário ( ix , iy ), conforme ilustrado na (Figura 4). Figura 4: Definição do sistema intermediário em uma imagem digital. Fonte: Galo (2003). Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 21 As coordenadas ( )yx cc , da origem C são obtidas pela expressão ( )       −−= 2 1 , 2 1 , HW cc yx , (1) onde W é o número de colunas (largura) e H número de linhas (altura) da imagem, todas contadas em pixels. Logo, as coordenadas ),( ii yx de qualquer ponto no sistema intermediário pode ser calculada em função de sua posição no Sistema de Imagem ( )PP yx , , aplicando um fator de escala no eixo x ( xS ) e no eixo y ( YS ) referente às dimensões do pixel a fim de estabelecer as coordenadas num sistema métrico, conforme Equação 2.       − − ⋅      − =      yP xP Y x i i cy cx S S y x 0 0 (2) A inversa da Equação 2 permite o cálculo das coordenadas ),( PP yx a partir de ),( ii yx (Equação 3).       +      ⋅      − =      y x i i y x P P c c y x S S y x /10 0/1 (3) Em contrapartida, nas imagens capturadas de forma analógica e posteriormente digitalizadas, a relação entre o Sistema de Imagem e o Fiducial é estabelecida por uma transformação geométrica plana (afim, por exemplo), cujos parâmetros são estimados a partir do ajustamento pelo método dos mínimos quadrados (MMQ), devendo ser conhecidas as coordenadas calibradas das marcas fiduciais no Sistema Fiducial (constantes no certificado de calibração) e as respectivas coordenadas medidas na imagem digital no Sistema de Imagem. 2.2.3 SISTEMA FOTOGRAMÉTRICO Trata-se de um sistema cartesiano tridimensional com origem estabelecida no centro perspectivo da câmara. Os eixos x e y são paralelos e orientados em relação aos eixos fx e fy do sistema fiducial ou intermediário ),( ii yx , com o eixo z perpendicular ao plano da imagem, de forma que torne o sistema dextrogiro (Figura 5). Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 22 Figura 5: Sistema fotogramétrico do positivo fotográfico. Fonte: Lugnani (1987). Desta forma, de posse das coordenadas de um ponto do positivo em um sistema bidimensional, fiducial ( )ff yx , ou intermediário ),( ii yx , pode-se estender essas coordenadas para o sistema fotogramétrico por meio da equação: ),,(),,( 00 fyyxxzyx ff −−−= , (4) onde f é a distância focal e ),( 00 yx as coordenadas do ponto principal (PP) dadas pelo certificado de calibração da câmara (MIKHAIL et. al., 2001). O ponto principal é definido como a interseção do eixo óptico do sistema de lentes da câmara com o plano da imagem. O sistema correspondente ao anterior, para o caso de emprego do negativo fotográfico (Figura 6), tem origem no centro perspectivo e os eixos x e y sofrem uma reflexão (LUGNANI, 1987). Figura 6: Sistema fotogramétrico do negativo. Fonte: Lugnani (1987). É possível observar na Figura 6 que a coordenada z dos pontos sobre a imagem assumirá o valor f. Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 23 2.3 REFINAMENTO DE COORDENADAS O objetivo do refinamento de coordenadas de imagem é assegurar que os erros presentes sejam estritamente randômicos, decorrentes dos modelos matemáticos adotados, sem componentes sistemáticos (MIKHAIL et al., 2001). As coordenadas de um ponto no espaço-imagem podem ser influenciadas por erros sistemáticos oriundos de diversas fontes e são corrigidas na ordem oposta a que acontecem, na etapa de pré-processamento, que faz parte do processo de orientação interior. Segundo Wolf e Dewitt (2000), as principais fontes de erros são: - Distorções devido ao trabalho e deformação do filme; - Deslocamento do ponto principal; - Distorção das lentes; - Distorções devido à refração atmosférica; - Distorção devido à curvatura da Terra. Nas próximas seções serão detalhados os erros sistemáticos, bem como os procedimentos de correção de cada um deles. 2.3.1 DEFORMAÇÕES DO FILME Devido a sua própria natureza, este tipo de deformação estará presente somente em imagens capturadas por câmaras métricas analógicas, digitalizadas posteriormente ou não. Medidas de fotocoordenadas inevitavelmente contêm deformações decorrentes da contração, dilatação e deformação do material base que suporta a emulsão do negativo ou diapositivo. Tais deformações são categorizadas como deformações do filme e normalmente são de natureza não homogênea, ou seja, distorções na direção x são frequentemente diferentes das distorções em y . Por consequência, o processo de correção faz uso das coordenadas das marcas fiduciais medidas na imagem e as correspondentes coordenadas disponibilizadas no certificado de calibração da câmara (WOLF e DEWITT, 2000). Em complemento as marcas fiduciais, ou substituindo essas, algumas câmeras são equipadas com um reseau, que consiste em uma série regular Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 24 de marcas gravadas em uma placa de vidro e cujas coordenadas são estimadas na calibração. Esta placa de vidro é colocada em frente ao filme, de forma que ao fazer a exposição, a grade seja impressa no negativo. A vantagem do reseau é a distribuição uniforme da grade de marcas, assim correções para distorções não uniformes podem ser feitas de forma precisa em toda a extensão do filme (MIKHAIL et al., 2001). Na realização da correção das deformações do filme para aplicações fotogramétricas, devem ser utilizadas transformações de coordenadas bidimensionais, que acabam por transformar as coordenadas de pixel para o sistema de coordenadas fiducial. Existem diferentes tipos de transformações a serem aplicadas, variando de acordo com o nível de acurácia desejada e o número de marcas fiduciais disponíveis, destacando-se a isogonal, afim, projetiva e polinomial (MIKHAIL et al., 2001). Se a opção for uma transformação geométrica (afim, por exemplo), são necessárias as coordenadas das marcas fiduciais (fornecidas pelo certificado de calibração) e suas correspondentes no sistema de imagem, empregando então a Equação 5.       ∆ ∆ +      ⋅      =      y x y x dc ba y x p p f f (5) Nesta equação, a, b, c, d, ∆x e ∆y são os parâmetros de transformação afim; ( )ff yx , são as coordenadas das marcas fiduciais; ( )PP yx , as coordenadas calibradas das marcas fiduciais. Pela inversa da Equação 5 se obtém as coordenadas das marcas fiduciais e dos demais pontos observados no sistema fiducial ou intermediário e, por conseguinte, corrigidas das deformações do filme.       ∆− ∆− ⋅      =      − yy xx dc ba y x f f P P 1 (6) 2.3.2 DESLOCAMENTO DO PONTO PRINCIPAL Durante o processo de montagem da câmara métrica procura-se enquadrar as marcas fiduciais e o conjunto de lentes de forma que o ponto principal e a intersecção das linhas fiduciais coincidam. No caso das câmaras digitais a Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 25 preocupação é que o ponto principal coincida com o centro da matriz de sensores. Em ambas as situações o enquadramento perfeito não ocorre na prática, havendo um deslocamento cuja magnitude é determinada durante o processo de calibração da câmara. Como as equações fotogramétricas assumem o ponto principal como origem das fotocoordenadas, se faz necessário realizar a correção deste deslocamento, assim as fotocoordenadas no sistema fiducial devem ser reduzidas ao sistema fotogramétrico, cuja origem é o ponto principal (WOLF e DEWITT, 2000). Admitindo-se o paralelismo dos sistemas fiducial e intermediário com o sistema fotogramétrico, a correção é efetuada por meio de uma translação. Para realizar tal correção as coordenadas do ponto principal constantes no certificado de calibração da câmara são subtraídos das coordenadas do ponto medido na imagem: 0' xxx i −= (7) 0' yyy i −= (8) onde, x’ e y’ são as coordenadas corrigidas do deslocamento do ponto principal (coordenadas fotogramétricas); ix e ix são as coordenadas do ponto no sistema intermediário (ou fiducial); 0x e 0y são as coordenadas do ponto principal constante no certificado de calibração. 2.3.3 DISTORÇÃO DAS LENTES Este tipo de distorção acarreta desvios na trajetória do raio de luz quando este atravessa o sistema de lentes, ocasionando um deslocamento nos pontos da imagem em relação à sua posição ideal. Este tipo de distorção pode ser decomposta em dois componentes, a distorção radial simétrica e a distorção descentrada. A distorção radial simétrica é decorrente do processo de fabricação das lentes, por consequência, havendo um cuidadoso processo de projeto e fabricação, podendo ser reduzido para um valor muito pequeno (WOLF e DEWITT, 2000). A distorção descentrada, por outro lado, é causada pela impossibilidade do fabricante em alinhar perfeitamente os eixos ópticos das lentes que compõem uma objetiva (ANDRADE, 1998). A distorção radial simétrica pode ser definida como sendo a parcela não desejável da refração sofrida por um raio de luz ao atravessar uma lente ou um sistema de lentes (ANDRADE, 1998). Tal distorção provoca os deslocamentos na Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 26 direção radial a partir do ponto principal. Um raio de luz que antes de penetrar a câmara forme um ângulo α com o eixo óptico, ao atravessar o sistema de lentes formará um ângulo α+δα (Figura 7), causando um deslocamento δr no ponto na imagem (ANDRADE, 1998). Figura 7: Representação gráfica da distorção radial simétrica. Fonte: Andrade (1998). O deslocamento δr, chamado de distorção longitudinal, é determinado pelo modelo definido por Conrady, sendo expresso por um polinômio de ordem ímpar (Equação 9) (Andrade, 1998). ...7 3 5 2 3 1 +++= rKrKrKrδ , (9) onde, rδ é a distorção radial; r é a distância radial do ponto imagem ao ponto principal; e iK é o coeficiente de distorção radial da lente. A distância radial (r), é dada em função das coordenadas fotogramétricas (x’,y’) por: 22 '' yxr += . (10) A Equação 9 permite o cálculo do valor rδ para cada um dos valores de r. No entanto, na prática é necessário calcular a influência para cada um dos componentes individualmente (Figura 8). Figura 8: Distorção radial e as correções em x e y. Fonte: adaptado de Wolf e Dewitt (2000). Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 27 A partir da Figura 8 nota-se que os componentes de distorção radial, designadas por xδ e yδ , são obtidos por semelhança de triângulos. (WOLF e DEWITT, 2000): y r x r r r yx δδδ == . (11) Logo, ( )...6 3 4 2 2 1 +++⋅=⋅= rkrkrkx r r xrx δδ , (12) ( )...6 3 4 2 2 1 +++⋅=⋅= rkrkrky r r yry δδ . (13) Com a origem do sistema de coordenadas já esteja no ponto principal, as coordenadas fotogramétricas corrigidas do efeito da distorção radial simétrica (x’,y’) são dadas por: xrxx δ−=' , (14) yryy δ−=' . (15) A distorção descentrada resulta em um deslocamento da imagem, sendo composta pelas distorções radial assimétrica e tangencial, conforme ilustrado na Figura 9 (ANDRADE, 1998) Figura 9: Componentes da distorção descentrada. Fonte: Andrade (1998). Conrady estabelece as equações para os componentes de distorção que compõem a distorção descentrada, são elas (ANDRADE, 1998): xVPr cos3 2 3 ⋅⋅⋅=δ (16) xsenVPt ⋅⋅= 2 3δ (17) onde rδ é a distorção radial assimétrica; tδ é a distorção radial tangencial; 3P é uma constante; V é a distância angular entre o eixo óptico e o ponto imagem; x é o Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 28 ângulo medido no plano das imagens, do eixo de máxima distorção radial (um eixo perpendicular ao eixo de máxima distorção tangencial) até a radial que contém a imagem não distorcida do ponto. Esse modelo sofreu algumas adaptações realizadas por Brown para aplicações fotogramétricas, transformando os componentes radial e tangencial em componentes xδ e yδ no sistema de coordenadas fotogramétricas. Dessa forma, as coordenadas afetadas pela distorção descentrada podem ser corrigidas por (ANDRADE, 1998): ( )[ ]yxPxrPdx ⋅⋅⋅+⋅+⋅= 2 22 1 22δ (18) ( )[ ]22 21 22 yrPyxPdy ⋅+⋅+⋅⋅⋅=δ (19) onde (x, y) são as coordenadas no sistema fotogramétricos; r é a distância radial do ponto imagem ao ponto principal; 1P e 2P coeficientes de distorção descentrada. Assim, as coordenadas corrigidas (x’,y’) da distorção descentrada podem ser obtidas por: dxxx δ−=' (20) dyyy δ−=' (21) 2.3.4 DISTORÇÕES DEVIDO A REFRAÇÃO ATMOSFÉRICA O índice de refração atmosférica reduz com o aumento da altitude. Wolf e Dewitt (2000), em função dessa condição, destacaram que os raios de luz não percorrem um caminho retilíneo na atmosfera, ou seja, são continuamente flexionados, havendo então a necessidade de corrigir as coordenadas de imagem em trabalhos aerofotogramétricos, podendo ser utilizada para isto uma atmosfera padrão. A Figura 10 ilustra uma situação na qual um raio luminoso que chega ao negativo a partir do ponto A, forma um ângulo α com a vertical. Se a refração atmosférica fosse ignorada, o raio de luz pareceria ser proveniente do ponto B e não do ponto A. Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 29 Figura 10: Refração atmosférica em fotografia aérea. Fonte: Wolf e Dewitt (2000). Como se pode notar (Figura 10), a refração causa um deslocamento na posição dos pontos na imagem. As equações de colinearidade assumem que o raio de luz percorre um caminho retilíneo, o que implica na necessidade de corrigir o efeito de refração sobre as coordenadas dos pontos da imagem. Se o raio de luz proveniente do ponto A tivesse percorrido um caminho linear, o ponto imagem corresponderia a a'. A distorção angular devido a refração atmosférica é dada por ∆α, e a distorção linear na fotografia é representada por ∆r. A magnitude da distorção devido à refração atmosférica aumenta com o aumento da altura de voo e do ângulo α. O efeito ocorre radialmente a partir do ponto principal sendo nulo na direção do nadir (WOLF e DEWITT, 2000). A relação que expressa a distorção do ângulo ∆α como uma função de α é expressa por (MIKHAIL et al., 2001; WOLF e DEWITT, 2000): αα tan.k=∆ (22) onde α é o ângulo formado entre a vertical e o raio de luz e k é uma constante relacionada com as condições atmosféricas, variando de acordo com a altura de voo. Existem diferentes abordagens para calcular o valor de k, sendo que a maioria assume uma atmosfera padrão para isso. Um método conveniente para calcular k é dado por (WOLF e DEWITT, 2000): ( ) ( ) ( )[ ]hHhHk −⋅−⋅−⋅⋅= − 202,01104,7 4 (23) Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 30 onde, H é a altura de voo e h é a altura do ponto objeto, ambos medidos em quilômetros. A partir da distância radial r calculada pela Equação 10, a distorção linear (∆r) em função da refração atmosférica, é determinada pelas equações abaixo (WOLF e DEWITT, 2000). f r=αtan (24) Então, k (Equação 23) e a tan α (Equação 24), são substituídos na Equação 22 para computar o ângulo de refração ∆α. f r k ⋅=∆α (25) A distância radial r’ do ponto principal para a localização corrigida da imagem pode ser calculada por: ( )αα ∆−⋅= tan' fr . (26) A mudança na distância ∆r é então computada por: 'rrr −=∆ . (27) Expressos os componentes, as coordenadas fotogramétricas corrigidas do efeito da refração atmosférica (x’, y’) de um ponto na imagem (x, y), são obtidas por: x r r xraxx x ⋅∆−=−= δ' (28) y r r yrayy y ⋅∆−=−= δ' (29) 2.3.5 EFEITO DA CURVATURA TERRESTRE As equações de colinearidade são escritas para transformações entre dois sistemas de coordenadas cartesianas. Contudo, a maioria dos trabalhos de medição em campo são realizados com base em sistemas de coordenados definidos por projeção cartográfica, tais como a UTM, com altura geométrica h. Se tais coordenadas não forem convertidas para coordenadas cartesianas antes de serem utilizadas em procedimentos fotogramétricos, uma correção para a curvatura terrestre deve ser aplicada às coordenadas (MIKHAIL et al., 2001). Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 31 Conforme ilustrado na Figura 11 um ponto P localizando sobre a superfície curva da Terra, de altura h, é localizado em P' sobre o plano de projeção. Figura 11: Efeito da curvatura da superfície terrestre. Fonte: Mikhail et al. (2001). Se a altitude de voo é H, o raio médio da Terra é R, a distância focal da câmara é f (em milímetros), a distância radial do ponto a partir do ponto principal é r (em milímetros), a correção, em mm, é dada pela seguinte equação (MIKHAIL et al., 2001): Rf Hr dE 2 3 2 = . (30) As coordenadas fotogramétricas (x’,y’) corrigidas do efeito da curvatura terrestre são dadas por: x r d x E ⋅      += 1' (31) y r d y E ⋅      += 1' (32) Se for adotado um sistema de coordenadas cartesiano local para os trabalhos no espaço-objeto, tais correções não são necessárias. 2.4 SISTEMAS DE COORDENADAS NO ESPAÇO-OBJETO O espaço-objeto é a região tridimensional coberta por uma fotografia ou imagem, ou seja, a região que envolve o ponto nodal anterior e todos os pontos Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 32 fotografados (LUGNANI, 1987). Neste espaço pode-se referenciar as coordenadas de objetos por meio de sistemas cartesianos e geodésicos (ou geodésicos elipsoidais). Tais sistemas podem ter origem no centro de massa da terra (um sistema geocêntrico) ou em algum ponto local mais conveniente (um sistema topocêntrico). Os referenciais do espaço-objeto que se destacam nos trabalhos fotogramétricos são: Sistema Geodésico, Sistema Geodésico Cartesiano e o Sistema Geodésico Cartesiano Local. Têm-se ainda as projeções cartográficas, sendo corriqueiramente utilizada a projeção conforme UTM com altura geométrica h. Tais referenciais serão detalhados a seguir. 2.4.1 SISTEMA GEODÉSICO Neste sistema, também chamado de Sistema Geodésico Elipsoidal, adota-se uma superfície (elipsóide de revolução) que sirva de referência para garantir uma concordância das coordenadas, e cujo modelo geométrico possibilite a simplificação dos cálculos. Tal elipsóide é definido pelos seus parâmetros f (achatamento) e a (semi-eixo maior). As coordenadas geodésicas que especificam a localização de objetos na superfície da Terra são estabelecidas por latitude φ, longitude λ e altura geométrica h. Os componentes latitude e longitude são componentes horizontais, enquanto a altura é a componente vertical (WOLF e DEWITT, 2000). A altura geométrica h é a distância da superfície do elipsóide até o ponto P na superfície da Terra, na mesma direção da normal (Figura 12 e Figura 13). A elevação do ponto P sobre o geóide (H) é conhecida como altura ortométrica (normalmente considerada a elevação em relação ao nível médio dos mares). Figura 12: Ilustração das três superfícies de referência. Fonte: Wolf e Dewitt (2000). Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 33 Na Figura 13 tem-se um ponto P com uma reta passando através dele, perpendicular ao elipsóide e se estendendo até o eixo polar. Esta linha é denominada normal. Figura 13: Coordenadas geodésicas. Fonte: Wolf e Dewitt (2000). A longitude λ de um ponto P é dada por um ângulo, formado no plano do equador, em relação ao meridiano origem (Greenwich) para o mediano local (meridiano interseccionado pela normal), com os valores negativos (0º a -180º) a oeste do meridiano principal e positivo (0º a 180º) a leste. A latitude φ de um ponto P é o ângulo do plano equatorial até a linha normal ao elipsóide no ponto P, com valores positivos (0º a 90º) ao norte do equador e negativo (0º a -90º) ao Sul. 2.4.2 SISTEMA GEODÉSICO CARTESIANO No sistema de coordenadas geodésicas a posição tridimensional de um ponto é referenciada a uma superfície curva (elipsóide) e, como tal, não adequadas para a utilização dos modelos fotogramétricos. O Sistema Geodésico Cartesiano, também conhecido como Sistema Cartesiano Geocêntrico, por outro lado, é um sistema de coordenadas cartesianas no espaço tridimensional (XYZ), com origem no centro do elipsóide de revolução adotado como modelo (WOLF e DEWITT, 2000). Figura 14: Relação entre sistema geodésico e geodésico cartesiano. Fonte: Wolf e Dewitt (2000). Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 34 Conforme ilustrado na FIGURA 14, os eixos X e Y estão localizados sobre o plano equatorial. O eixo X é positivo na direção de longitude 0° (dirigido para o meridiano de Greenwich) e o eixo Z é paralelo ao eixo de rotação da terra e positivo na direção da origem convencional internacional (CIO), ou seja, na direção do pólo norte. O eixo Y do sistema é disposto de tal modo que torna o sistema dextrogiro, positivo na direção de longitude 90°. 2.4.3 SISTEMA GEODÉSICO CARTESIANO LOCAL O Sistema Geodésico Cartesiano Local, ou simplesmente Sistema Cartesiano Local é um sistema de referência cartesiano tridimensional XYZ no qual a origem é estabelecida como um ponto sobre o elipsóide ou sobre um ponto de altura geométrica 0h , sobre o geóide ou nas imediações da superfície física da Terra (LUGNANI, 1987). Figura 15: Sistema cartesiano local e sua relação com o geocêntrico e o geodésico. Fonte: Wolf e Dewitt (2000). Na FIGURA 15 nota-se que o eixo lZ coincide com a normal ao elipsóide no ponto de origem do sistema, o eixo lY aponta na direção do norte geodésico e o eixo lX na direção e sentido que tornem o sistema dextrogiro. 2.4.4 SISTEMA DE PROJEÇÃO UTM As Projeções são formulações matemáticas para representar feições de uma superfície curva em outra plana. Existem diferentes projeções, uma das mais utilizada no Brasil é a UTM (Universal Transverse Mercator), derivada da Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 35 Projeção Cilíndrica Transversa de Mercator (TM). A projeção UTM tem por característica reduzir as deformações nos extremos do fuso. O cilindro que na projeção TM é tangente ao meridiano central, na UTM passa a ser secante ao elipsóide de revolução, conforme ilustrado na FIGURA 16 (GASPAR, 2000). Figura 16: Cilindro secante da Projeção UTM. Fonte: http://commons.wikimedia.org. De acordo com IBGE (BRASIL, 1999), algumas características básicas da projeção UTM são: 1) A Terra é dividida em 60 fusos, cada um com 6º de longitude, os quais são numerados de 1 a 60, a partir do anti-meridiano de Greenwich (de 180º a 174º). Os fusos são gerados a partir da rotação de um cilindro de forma que o meridiano de tangência (ou meridiano central - MC) divide o fuso em duas partes iguais de 3º; 2) O quadriculado é associado a um sistema plano-retangular, sendo que o eixo N aponta para o Norte (coincidente com o MC) e E aponta para o outro eixo (coincidente com o equador); 3) O coeficiente de deformação no MC é igual a 0,9996 no MC e aproximadamente a 1,000997 nos extremos do fuso; 4) Cada fuso tem um sistema cartesiano métrico de referência, no qual a origem é 500.000 m para E e para N adota-se 10.000.000 m ou 0 m (zero) para o hemisfério sul e norte, respectivamente; 5) Cada fuso é prolongado 30’ em ambos os extremos, obtendo uma superposição de 1º; 6) O sistema UTM é usado entre as latitudes 84ºN e 80ºS. As coordenadas (E, N) são componentes horizontais que indicam posições no plano UTM. O componente vertical (h), referido ao elipsóide, deve ser acrescido para expressar alturas, formando um sistema de referência híbrido. Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 36 2.5 TRANSFORMAÇÕES DE COORDENADAS NO ESPAÇO-OBJETO As transformações de coordenadas entre os referencias do espaço- objeto ocorrem por questões de compatibilidade, facilidade de manuseio e outros motivos. Nesta seção serão apresentados os modelos matemáticos utilizados para as transformações de coordenadas entre referenciais do espaço-objeto. 2.5.1 TRANSFORMAÇÕES ENTRE UTM E TM As coordenadas de um ponto no sistema UTM (N, E) são transformadas para o sistema TM (x, y) por meio das equações que seguem (MALING, 1992): 9996,0 N x = , (33) ( ) 9996,0 000.500−= E y , (34) ( ) 9996,0 000.000.10−= N x , (35) ( ) 9996,0 000.500−= E y . (36) As Equações 33 e 34 se referem ao hemisfério Norte, enquanto as 35 e 36 ao hemisfério Sul. Os valores 10.000.000 m e 500.000 m promovem as translações e o valor 0,9996 é o fator de escala do meridiano central. A transformação de coordenadas TM (x,y) para UTM (N,E) é obtido pela inversão das Equações 33 a 36. 2.5.2 TRANSFORMAÇÕES ENTRE TM E GEODÉSICA Conforme descrito por Fazan (2007), as coordenadas no sistema TM (x, y) podem ser transformadas em coordenadas geodésicas (φ, λ), por meio das seguintes equações tratadas em Yang et al. (2000):         ′+′+′+= 44 4 22 2 02 2 360122 u N y u N y u N y tB fff ffϕ , (37) Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 37 ( )         ′+′++= 44 4 22 2 0 1206 1 cos v N y v N y BN y ffff λλ . (38) Com os parâmetros ft e 2 fη obtidos por: ( )ff Bt tan= , (39) ( )ff Be 222 cos′=η . (40) Sendo os coeficientes 0u′ , 2u′ , 4u′ , 2v′ e 4v′ calculados em função de t e η: 2 0 1 fu η−−=′ , (41) 4242222 2 936635 fffffff tttu ηηηη −−−++=′ , (42) 2422242 4 45162107459061 fffffff ttttu ηηη ++−−−−=′ , (43) 22 2 21 fftv η−−−=′ , (44) 22242 4 8624285 fffff tttv ηη ++++=′ . (45) O parâmetro fB é a latitude inicial aproximada calculada em função da coordenada x e dos parâmetros do elipsóide de referência. O cálculo de fB é dado inicialmente por: A x B i f == )0( . (46) Com o valor de A sendo obtido pela Equação 55. A partir desse valor, calcula-se o valor do arco de meridiano ( )(iS ) correspondente (Equação 53). Um valor melhorado pode ser calculado por: A Sx BB i i f i f )( )()1( −+=+ . (47) Após esse procedimento calcula-se novamente o valor do arco de meridiano correspondente e um valor melhorado para fB . O processo termina quando o valor absoluto do termo ( ))(iSx− for menor que uma tolerância pré- estabelecida. Já a transformação do sistema de coordenadas geodésicas ),( λφ para o sistema de projeção TM y)(x, , apresentada por Fazan (2007), é obtida por meio das seguintes equações tratadas em Yang et al. (2000): Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 38       ++++= 6 6 4 4 2 22 4032036012 1 2 u L u L u LtNL Sx , (48)       +++= 6 6 4 4 2 2 50401206 1 v L v L v L NLy , (49) Com os parâmetros L , t , η e S obtidos por: ( )ϕλ cos∆=L , (50) ( )ϕtan=t , (51) ( )φη 222 cose′= , (52) ( ) ( ) ( ) ( ) ( )    +−+−−= ϕϕϕϕϕ 8sen 8 6sen 6 4sen 4 2sen 2 1 2 EDCB AeaS . (53) Com 0λλλ −=∆ (54) e 8642 16384 11025 256 175 64 45 4 3 1 eeeeA ++++= , (55) 8642 2048 2205 512 525 16 15 4 3 eeeeB +++= , (56) 864 4096 2205 256 105 64 15 eeeC ++= , (57) 86 2048 315 512 35 eeD += , (58) 8 16384 315 eE = . (59) Sendo 0λ a longitude do meridiano central no fuso UTM; S é o comprimento do arco de meridiano entre o equador e o ponto de latitude ϕ ; 2e′ é o quadrado da segunda excentricidade do elipsóide adotado como modelo; os coeficientes 2u , 4u , 6u , 2v , 4v e 6v são calculados em função de t e η: 422 2 495 ηη ++−= tu , (60) 22242 4 3302705861 ηη tttu −++−= , (61) 642 6 54331111385 tttu −+−= , (62) 22 2 1 η+−= tv , (63) Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 39 22242 4 5814185 ηη tttv −++−= , (64) 642 6 17947961 tttv −+−= . (65) 2.5.3 TRANSFORMAÇÕES ENTRE COORDENADA GEODÉSICA E GEODÉSICA CARTESIANA Um ponto de coordenadas geodésicas ϕ (latitude), λ (longitude) e h (altura geométrica), pode ser expresso em coordenadas cartesianas retangulares X, Y e Z, assumindo-se para isso um elipsóide de revolução com a mesma origem do sistema de coordenadas cartesianas (MONICO, 2000). A relação entre esses sistemas é estabelecida por (SEEBER, 2003): ( )           +− + + =           ϕ λϕ λϕ senheN senhN hN Z Y X )1( )()cos()( )cos()cos()( 2 (66) com N sendo a grande normal passando pelo ponto de coordenadas geodésicas ),( λϕ e definido por ( )2 1 22 )(1 ϕsene a N − = (67) com o termo a sendo o comprimento do semi-eixo maior do elipsóide de referência adotado e 2e o quadrado da primeira excentricidade, 2 2 22 2 2 ee ff a ba e −=−= (68) f o achatamento do elipsóide, a ba fe −= . (69) A transformação de coordenadas do sistema geodésico cartesiano para o sistema geodésico, tem solução direta pelas equações (IBGE, 1999; MONICO, 2000): ( )( )[ ] ( ) ( ) ( )         ⋅⋅−+ ⋅−−⋅+ = − uaeYX usenefaeZ 3222 3122 cos 11 arctanϕ , (70)      = X Y arctanλ , (71) Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 40 ( ) N YX h −+= ϕcos 22 , (72) nas quais, ( ) ( ) ( )u u usen 2tan1 tan + = , (73) ( ) ( )u u 2tan1 1 cos + = , (74) ( ) ( ) fYX Z u −+ = 1 1 tan 22 . (75) 2.5.4 TRANSFORMAÇÕES ENTRE COORDENADAS GEODÉSICA CARTESIANA E GEODÉSICA CARTESIANA LOCAL A transformação entre os sistemas geodésico cartesiano e geodésico cartesiano local é realizada por meio de translações e rotações, (WOLF e DEWITT, 2000): ( ) ( )           − − − ⋅+⋅−=           0 0 0 0301 22 ZZ YY XX RR Z Y X l l l λπϕπ (76) onde, 0ϕ e 0λ corresponde a latitude e a longitude do ponto adotado como origem no sistema cartesiano local; X , Y , Z são as coordenadas no referencial geodésico cartesiano de um ponto P; 0X , 0Y , 0Z são as coordenadas cartesianas da origem do sistema local obtidas pela Equação 66. 1R e 3R são as matrizes de rotação dadas em função de 0ϕ e 0λ do ponto origem: ( )           − =           −−− −−=− 00 00 00 0001 cos0 cos0 001 )2cos()2(0 )2()2cos(0 001 2 ϕϕ ϕϕ ϕπϕπ ϕπϕπϕπ sen sen sen senR (77) ( )           −− −− =           ++− +−+ =+ 100 0cos 0cos 100 0)2cos()2( 0)2()2cos( 2 00 00 00 00 03 λλ λλ λπλπ λπλπ λπ sen sen sen sen R . (78) Para a transformação inversa (Geodésica Cartesiana Local para Geodésica Cartesiana), utiliza-se: Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 41 ( ) ( )           ⋅+⋅++           =           L L L TT Z Y X RR Z Y X Z Y X 0103 0 0 0 22 ϕπλπ (79) 2.6 RELAÇÃO ENTRE COORDENADAS NO ESPAÇO-OBJETO E ESPAÇO-IMAGEM As equações de colinearidade, nas suas formas direta e inversa, definem um dos modelos matemáticos utilizado com o propósito de relacionar os espaços imagem e objeto por meio de transformações de coordenadas. Tais modelos requerem a determinação dos parâmetros de orientação exterior da imagem, ou seja, as três coordenadas CPCPCP ZYX ,, do ponto onde foi coletada (centro perspectivo), bem como os ângulos ( κϕω ,, ) que definem a atitude, de maneira que se aplicadas as rotações ao sistema terrestre fazem-no coincidir com o fotogramétrico. Para o desenvolvimento do método proposto nesta pesquisa os parâmetros ( κϕω ,,,,, CPCPCP ZYX ) considerados como conhecidos. 2.6.1 TRANSFORMAÇÕES DE COORDENADAS ENTRE ESPAÇO-IMAGEM E ESPAÇO- OBJETO A transformação de coordenadas cartesianas locais ( )lll ZYX ,, em fotogramétricas ( )',' yx faz uso das equações de colinearidade na sua forma direta (Equações 80 e 81). As equações de colinearidade são deduzidas com base na condição de que um ponto no espaço-objeto ( A ), seu correspondente no espaço- imagem (a ) e o centro perspectivo (CP) pertençam a uma mesma reta (MIKHAIL et al., 2001), conforme: ( ) ( ) ( ) ( ) ( ) ( )CPACPACPA CPACPACPA a ZZmYYmXXm ZZmYYmXXm fx −+−+− −+−+− −= 333231 131211' (80) ( ) ( ) ( ) ( ) ( ) ( )CPACPACPA CPACPACPA a ZZmYYmXXm ZZmYYmXXm fy −+−+− −+−+− −= 333231 232221' (81) Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 42 com f sendo a distância focal; ( )aa yx ',' as coordenadas fotogramétricas; ( )AAA ZYX ,, coordenadas do ponto no espaço-objeto referidas a um sistema local; ( )CPCPCP ZYX ,, coordenadas do centro perspectivo no espaço-objeto referidas a um sistema local; ijm elementos da matriz de rotação determinados em função dos ângulos de orientação exterior ( )ωϕκ ,, . A condição prevista nas Equações 80 e 81 é ilustrada na Figura 17, onde os pontos CP, a e A pertencem a uma mesma reta. Figura 17: Condição de colinearidade. Fonte: Wolf e Dewitt (2000). Na sua forma inversa (Equações 82 e 83) as equações de colinearidade permitem a transformação de coordenadas fotogramétricas ( )',' yx em coordenadas cartesianas locais ( )lll ZYX ,, . Com lX e lY obtidos pelas Equações 82 e 83 respectivamente, e lZ por informações altimétricas do relevo (MDT). ( ) fmymxm fmymxm ZZXX aa aa CPACPA 332313 312111 '' '' −+ −+ −+= (82) ( ) fmymxm fmymxm ZZYY aa aa CPACPA 332313 322212 '' '' −+ −+ −+= (83) As equações dadas não são, a rigor, equações inversas das Equações 80 e 81. Isto porque a determinação das coordenadas planimétricas )Y,(X AA depende do componente altimétrico )(Z A , porém isto pode ser resolvido se houver disponibilidade de informações do relevo (DAL POZ, 1998). Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 43 2.6.2 TRANSFORMAÇÃO DE COORDENADAS UTM PARA COORDENADAS DE IMAGEM A transformação direta de coordenadas no sistema UTM ( )EN, , com altura geométrica h , para o Sistema de Imagem ( )PP yx , requer uma série de conversões intermediárias entre sistemas do espaço-objeto e espaço-imagem. Nas Equações 84 a 90 estão sistematizadas tais conversões, bem como os parâmetros envolvidos. • UTM � TM ( )ii ENfx ,18= ( )ii ENfy ,17= (84) • TM � Geodésica ( )yxfaf ,,,16=ϕ ( )yxfaf ,,,15=λ (85) • Geodésica � Geodésica Cartesiana ( )ihfafX ,,,,14 λϕ= ( )ihfafY ,,,,13 λϕ= ( )ihfafZ ,,,,12 λϕ= (86) • Geodésica Cartesiana �Geodésica Cartesiana Local ( )ZYXhfXl ,,,,, 00011 λϕ= ( )ZYXhfYl ,,,,, 00010 λϕ= ( )ZYXhfZl ,,,,, 0009 λϕ= (87) • Geodésica Cartesiana Local � Fotogramétrica ( )lllCPCPCP ZYXfZYXfx ,,,,,,,,,' 8 ωϕκ= ( )lllCPCPCP ZYXfZYXfy ,,,,,,,,,' 7 ωϕκ= (88) • Fotogramétrica � Intermediário ( ) ( )( )Exxxi d,rarderrosyxyxfx δδδ ,,,,,',' 006= ( ) ( )( )Eyyyi d,rarderrosyxyxfy δδδ ,,,,,',' 005= (89) • Intermediário � Imagem ( )( )iiPi yxSySxHWdimensõesfxC ,,,,,4=⇔ ( )( )iiPi yxSySxHWdimensõesfyL ,,,,,3=⇔ (90) Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 44 Acompanhando o desenvolvimento das transformações nota-se que as coordenadas de Imagem ( )PP yx , são obtidas em função das coordenadas (E, N, h) e de todos os parâmetros envolvidos nas transformações. Pode-se então formular um modelo global, tal como: ),(2 iari VPfC = , ),(1 iari VPfL = , (91) onde (Li, Ci) são as coordenadas linha e coluna no sistema de imagem de um ponto i; Par é o vetor de parâmetros envolvidos (os parâmetros de orientação interior e exterior da imagem, os parâmetros geométricos elipsoidais e os parâmetros relacionados com a projeção UTM); e Vi é o vetor de coordenadas (Ei, Ni, hi) do ponto i no sistema UTM com altura geométrica h. Considerando que vetor Par é conhecido, um ponto no espaço-imagem pode ser expresso em função somente de Vi. 2.7 PROGRAMAÇÃO DINÂMICA A programação dinâmica é uma técnica para resolver problemas de otimização quando nem todas as variáveis envolvidas estão simultaneamente inter- relacionadas (BALLARD e BROWN, 1982). Esta estratégia de otimização para problemas combinatórios envolve a tomada de decisões sequenciais, aqui brevemente descrita por meio da análise da Figura 18, que apresenta o problema clássico da programação dinâmica (LI, 1997) expresso na forma de grafo. No grafo, deve-se encontrar o caminho ótimo entre os nós A e N . O primeiro passo consiste na escolha do caminho entre o nodo A e um dos três nós a ele relacionados (10, 11 ou 12). Se o nó 11 for o escolhido, então a próxima decisão deve ser tomada entre os nós 20, 21 e 22, assim por diante até atingir o nó N . Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 45 Figura 18: Problema clássico de programação dinâmica. Fonte: Li (1997). Li (1997) formaliza tal problema definindo um conjunto de nós }{ iP , ni ,,2,1 K= , com uma matriz custo associada ][ ijC , na qual ijC denota o custo para mover-se do nó iP para o nó jP . Assumindo que uma função de duas variáveis ),( jig descreve o custo (função custo) para se mover do nó iP ao nó jP e s os nós ao longo do caminho, pode-se escrever a equação: ),(),(),( jsgsigjig += (92) Para definir o caminho ótimo entre os nós iP e jP , é necessário encontrar ),( jig e um conjunto de nós s que satisfaçam a condição imposta. A otimização do problema clássico apresentado na Figura 18 é obtida ao encontrar o menor custo global (ou custo mínimo) para ir do nó inicial AP ao nó final NP , bem como o caminho associado. [ ]),(),(min),( jsgsigjig s += (93) Nas condições estabelecidas anteriormente, Ballard e Brown (1982) detalham os passos para obter o custo global e o caminho a ele associado, com i dependendo exclusivamente de 1s em 0g , 1s dependendo de 2s em 1g e assim por diante até 1−Ng , desta forma pode-se decompor o problema da forma como segue. [ ]),(),(),(),(),(min),( 4443332221110 jsgssgssgssgsigjig si ++++= (94) Selecionando o valor mínimo de i em 0g e armazenando este valor ótimo de ),( 10 sig para cada 1s obtém-se ).( 10 sf [ ]),(min)( 1010 0 sigsf s = (95) No passo seguinte ),( 211 ssg será acrescido de )( 10 sf e o processo repetido: Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 46 [ ]),()(min)( 2111021 1 ssgsfsf s += . (96) Assim, sucessivamente até )(min 1 NN s sf N − , que apresentará o custo mínimo global com o respectivo caminho associado, ou seja, ),...,(min)(min 11 n si NN s ssgsf N =− . Este procedimento pode ser generalizado para N variáveis, considerando o acréscimo a ),( 10 sig em )( 10 sf igual a 0, por não haver custo parcial a ser acrescido. [ ]),()(min)( 11111 1 nnnnn s nn ssgsfsf n −−−−− += − . (97) No problema da Figura 18 o caminho ótimo é definido pelos nós A , 11, 22, 32, 41, N .e o custo mínimo associado é 19. A formulação apresentada, que neste caso busca o custo mínimo, pode ser modificada para problemas de máximos, bastando substituir o operador min[.] pelo operador max[.] (LI, 1997). 2.8 MODELOS MATEMÁTICOS DE RODOVIA Os modelos de rodovias são formulações matemáticas que englobam nos seus parâmetros as particularidades geométricas e radiométricas deste tipo de feição. Serão apresentados nas seções seguintes os diferentes modelos matemáticos para rodovias no espaço-imagem e espaço-objeto. 2.8.1 MODELO MATEMÁTICOS DE RODOVIA NO ESPAÇO-IMAGEM Várias propriedades geométricas e radiométricas são usadas para formular um modelo de rodovia no espaço-imagem (GRUEN e LI 1997; DAL POZ e VALE, 2003; DAL POZ et al., 2006; GALLIS, et al. 2005). Assumindo que uma rodovia possa ser representada pela linha poligonal Pi= {p1, ..., pn}, onde pi é seu i- ésimo vértice, pode-se modelá-la matematicamente através da função objetivo (Equação 98) e da injunção de desigualdade (Equação 99), como segue (GRUEN e LI, 1997), Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 47 [ ] ( ) )/)cos(1( 1 1 11321∑ − = + ∆−+×+−= n i sippp i EEEE ααγβ (98) TC iii <−= +1αα (99) onde, 1pE é uma função que depende do vértice pi e expressa o fato de que os pixels de rodovia são mais claros que seus vizinhos em ambas as margens da rodovia; 2pE é uma função que depende de dois pontos consecutivos (pi-1 e pi) da linha poligonal Pi e expressa o fato de que os níveis de cinza ou cor da rodovia não variam muito, sobretudo em curtas distâncias; 3pE é uma função que depende do vértice pi e expressa o fato de que uma rodovia é uma feição linear de alto valor de brilho; iα é a direção do segmento de reta definido pelos pontos pi-1 e pi; β e γ são constantes positivas; si∆ é a distância entre os pontos pi-1 e pi; e T é um limiar angular que limita a mudança de direção entre dois segmentos sucessivos da linha poligonal Pi . A Equação 98 mostra que somente três pontos consecutivos (pi-1, pi, pi+1) da linha poligonal P são simultaneamente inter-relacionados e que, em decorrência, pode ser decomposta numa soma de n-1 subfunções do tipo Ei(pi-1, pi, pi+1), conforme mostra a Equação 100. Maiores detalhes podem ser visto em Gruen e Li (1997). ),,( 1 1 11∑ − = +−= n i iiii pppEE (100) A solução deste problema é uma linha poligonal Pi= {p1, ..., pn} que representa uma rodovia e corresponde ao máximo da função objetivo dada pela Equação 98 ou 100. Esta função é apropriada para a extração semi-automática de rodovias em imagens de baixa-resolução, com rodovias variando em espessura de 1 a 3 pixels. A fim de possibilitar a extração acurada do eixo de rodovia em imagens de maior resolução, Dal Poz e Vale (2003) propuseram uma modificação na Equação 100. Basicamente, um termo de injunção de borda foi adicionado na função objetivo original, forçando a linha poligonal extraída a coincidir com o eixo da rodovia. Na função objetivo modificada, somente os vértices consecutivos (pi-1, pi, pi+1) da linha poligonal Pi e as larguras da rodovia (wi-1, wi, wi+1) nestes vértices são simultaneamente inter-relacionados, ficando, ),,,,,( 1 1 1111∑ − = +−+−= n i iiiiiii m wwwpppEE (101) Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 48 A Equação 101 mostra que o objetivo do processo de otimização é similar ao que é baseado na Equação 100. A diferença básica é que o processo de otimização fornece não só a linha poligonal Pi= {p1, ..., pn} representando o eixo da rodovia, mas também as larguras da rodovia nos respectivos vértices. 2.8.2 MODELO MATEMÁTICO DE RODOVIA NO ESPAÇO-OBJETO PARA UMA IMAGEM ISOLADA As Equações 100 e 101 podem ser modificadas a fim de expressar as rodovias em função de coordenadas 3D do espaço-objeto (GALLIS et al., 2005; DAL POZ et al., 2006). O sistema de coordenadas do espaço-objeto escolhido para representar os vértices 3D do eixo de rodovia é o UTM (Universe Transverse Mercator) (E, N) com altura elipsoidal ou geométrica (h). A relação matemática, entre um ponto P(E, N, h) no espaço-objeto e seu correspondente ponto p(L, C) no espaço-imagem, é estabelecida levando em conta três passos (GALLIS et al., 2005): � Primeiro, tendo em vista uma solução rigorosa para o problema, é necessário relacionar matematicamente um ponto no sistema UTM com altura elipsoidal (h) ao correspondente ponto P(X, Y, Z) no sistema cartesiano local de coordenadas. � Segundo, as equações de colinearidade são usadas, juntamente com os parâmetros de orientação exterior, para transformar o ponto P(X, Y, Z) no sistema de coordenadas fotogramétricas. � Terceiro, o ponto resultante desta última operação matemática é transformado para o sistema de coordenadas de pixel (L, C), valendo-se do modelo de orientação interior e os parâmetros associados. Assumindo que todas as operações matemáticas, entre as coordenadas de um ponto pi no sistema de coordenadas de pixel (Li, Ci) e as coordenadas do ponto correspondente no sistema de referência UTM com altura elipsoidal (Ei, Ni, hi), possam ser estabelecidas através de duas funções conhecidas f1 e f2 (Equação 91), tem-se: )),,(),,,(())(),((),( 2121 iiiiiiiiiiiii hNEfhNEfpVfVfpCLp == . (102) Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 49 Incorporando a expressão 102 na equação 100 obtém-se: == +++ − = −−−∑ )),(),,(),,(( 111 1 1 111 iiiiii n i iiii CLpCLpCLpEE )),,,(),,,(()),,,(),,,((( 2111121111 1 1 1 iiiiiiiiiiiii n i ii hNEfhNEfphNEfhNEfpE −−−−−− − = −∑ ))),,(),,,(( 111211111 +++++++ iiiiiii hNEfhNEfp . (103) A Equação 103 mostra que ela depende simultaneamente das coordenadas de três pontos sucessivos da linha poligonal que representa a rodovia no espaço-objeto, quais sejam: Pi-1(Ei-1, Ni-1, hi-1), Pi(Ei, Ni, hi) e Pi+1(Ei+1, Ni+1, hi+1). Assim a Equação 103 pode ser simplificada e escrita como segue: )),,(),,,(),,,(( 1111111 1 1 1 ++++−−− − = −∑= iiiiiiiiiii n i ii hNEPhNEPhNEPEE . (104) A Equação 104 parece, em primeira análise, apropriada para a extração de rodovias no espaço-objeto usando apenas uma imagem de baixa- resolução. Isso não é possível porque a Equação 104 é ambígua, visto que existe uma classe não limitada de linhas poligonais que possibilitam obter um mesmo valor máximo para E. Isto decorre da conhecida propriedade da Equação 91, pela qual existem infinitos pontos no espaço-objeto que mapeiam para um mesmo ponto no espaço-imagem. Em Gallis et al.. (2005) e Dal Poz et al. (2006) essa ambigüidade foi removida forçando a rodovia extraída a pertencer à superfície de um MDT. Em se tratando de imagens de média e alta-resolução, demonstra-se que a Equação 100 pode ser modificada e expressa na forma (GALLIS et al., 2005; DAL POZ et al., 2006), ),),,,(),,,(),,,(( 111111111 1 1 1 +−++++−−− − = −∑= iiiiiiiiiiiiii n i ii WWWhNEPhNEPhNEPEE (105) onde, Wi-1, Wi, e Wi+1 são as larguras no espaço-objeto da rodovia nos pontos Pi-1, Pi, e Pi+1, respectivamente. A Equação 105 é desenvolvida seguindo os mesmos princípios para se obter a Equação 104. Nesse caso é necessário também transformar as larguras da rodovia no espaço-imagem (w1, …, wn-1) para as correspondentes larguras no espaço-objeto (W1, …, Wn-1). 2.8.3 MODELO MATEMÁTICO DE RODOVIA NO ESPAÇO-OBJETO PARA UM ESTÉREO PAR DE IMAGENS Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 50 A Figura 19 ilustra o princípio do método desenvolvido por Gallis (2006) e apresentado nesta seção, onde R é uma rodovia no espaço-objeto, cujas as correspondentes nas imagens da esquerda e da direita são respectivamente r e r´. Para traçar uma rodovia no espaço-objeto, via otimização de um modelo matemático de rodovia, é necessário que as propriedades geométricas e radiométricas de rodovia, além das relações matemáticas entre pontos de ambos os espaços envolvidos, sejam modeladas. A solução para este problema difere da solução fotogramétrica seqüencial geralmente empregada para extrair rodovias e outros objetos em 3D. A solução fotogramétrica seqüencial emprega três etapas básicas: a extração de rodovias homólogas (r e r´) em ambas as imagens; a determinação de correspondência, geralmente ponto a ponto (p e p´), entre as rodovias r e r´; a projeção das rodovias homólogas para o espaço-objeto, a fim de obter a rodovia R. A solução proposta por Gallis (2006) integra todas estas etapas numa única, tendo por base o modelo matemático de rodovia a ser desenvolvido abaixo. p C ́ L´ C L r r´ p ́ R P(E,N,h) E N h Figura 19: Extração da rodovia no espaço-objeto. Fonte: Gallis (2006). O desenvolvimento do modelo matemático de rodovia no espaço- objeto, que leva em conta informações radiométricas provenientes de um estéreo par de imagens, requer que a Equação 105 seja escrita para cada imagem (GALLIS, 2006), += ),,),,,(),,,(),,,(( 2102222111100001 WWWhNEPhNEPhNEPEE ll ++ ...),,),,,(),,,(),,,(( 3213333222211112 WWWhNEPhNEPhNEPEl ),,),,,(),,,(),,,(( 12111122221 nnnnnnnnnnnnnnn l n WWWhNEPhNEPhNEPE −−−−−−−−−−− (106) Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 51 += ),,),,,(),,,(),,,(( 2102222111100001 WWWhNEPhNEPhNEPEE rr ++ ...),,),,,(),,,(),,,(( 3213333222211112 WWWhNEPhNEPhNEPEr ),,),,,(),,,(),,,(( 12111122221 nnnnnnnnnnnnnnn r n WWWhNEPhNEPhNEPE −−−−−−−−−−− (107) onde, El é o modelo matemático de rodovia escrito para a imagem esquerda e Er para a imagem direita. Seja P= {P0(E0, N0, h0);…;Pn(En, Nn, hn)} uma linha poligonal representando uma rodovia no espaço-objeto. Assim, a linha poligonal P, juntamente com as larguras corretas da rodovia nos vértices de P, maximizam as Equações 106 e 107. Entretanto, a solução P não pode ser obtida usando a Equação 106 ou 107 isoladamente porque as mesmas são ambíguas. É possível provar que a soma das funções El e Er não é ambígua, isto é, ela possui uma solução única (P) para o eixo da rodovia R (GALLIS, 2006; DAL POZ, 2010), preservando a estrutura da Equação 105, o que é fundamental para a aplicação do algoritmo de otimização por programação dinâmica. Seja P´ uma linha poligonal que maximiza a função El. Se P´ não coincide com o eixo da rodovia R (isto é, P´ é uma falsa solução de El), então ela não maximizará a função Er. Se o mesmo raciocínio for aplicado para uma outra linha poligonal P´´, tem-se então uma falsa solução da função Er. Em outras palavras, P´ e P´´ maximizariam ambas as funções El e Er, se e somente se, P´= P´´= P. Como El e Er são funções positivas, P é a única solução de máximo do modelo matemático de rodovia definido pela soma das funções El e Er. Somando então as funções El e Er e agrupando os termos, obtém-se o modelo matemático de rodovia (ET) formulado no espaço-objeto para um estéreo par de imagens, como segue: =+= rlT EEE +)),,,(),,,(),,,(([ 2,1,02222111100001 WWWhNEPhNEPhNEPE l ++ ... )]),,,(),,,(),,,(( 2,1,02222111100001 WWWhNEPhNEPhNEPE r )]),,,(),,,(),,,(( )),,,(),,,(),,,(([ ,1,2111122221 ,1,2111122221 nnnnnnnnnnnnnnnn r nnnnnnnnnnnnnnnn l WWWhNEPhNEPhNEPE WWWhNEPhNEPhNEPE −−−−−−−−−−− −−−−−−−−−−− + (108) Na Equação 108 pode-se notar que o i-ésimo termo entre colchete depende de três vértices sucessivos (Pi-1, Pi, e Pi+1) da linha poligonal e das respectivas larguras de rodovia (Wi-1, Wi, e Wi+1). Assim, a notação acima pode ser Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 52 simplificada, substituindo os termos entre os colchetes (i= 1, …, n-1) com base na seguinte expressão geral, =+−++++−−−− ),,),,,(),,,(),,,(( 1111111111 iiiiiiiiiiiiiii T i WWWhNEPhNEPhNEPE ++−++++−−−− ),,),,,(),,,(),,,(([ 1111111111 iiiiiiiiiiiiiii l i WWWhNEPhNEPhNEPE )],,),,,(),,,(),,,(( 1111111111 +−++++−−−− iiiiiiiiiiiiiii r i WWWhNEPhNEPhNEPE (109) possibilitando escrever a equação 108 na forma, ),,),,,(),,,(),,,(( 111111 1 1 1111 +−++++ − = −−−−∑= iiiiiii n i iiiiiiii T i T WWWhNEPhNEPhNEPEE (110) A Equação 110 mostra que a estrutura da Equação 105 foi plenamente preservada. Embora esta equação tenha 12 variáveis inter-relacionadas simultaneamente, é possível reduzir o número de variáveis e, conseqüentemente, diminuir também o esforço computacional. De forma análoga, tendo por base agora a equação 110, pode-se desenvolver uma equação para um estéreo par de imagens de baixa resolução, sem as injunções de bordas. O resultado desse desenvolvimento é apresentado na Equação 111. )),,(),,,(),,,(( 1111 1 1 1111 ++++ − = −−−−∑= iiii n i iiiiiiii T i T hNEPhNEPhNEPEE (111) No Capítulo 3 está equação será retomada para desenvolvimento da metodologia. 2.9 MODELAGEM DE SUPERFÍCIE A utilização do conceito de modelo digital para representar a superfície terrestre é relativamente recente. No artigo de autoria dos engenheiros Charles Miller e R. A. LaFlamme do Instituto de Tecnologia de Massachusetts (MIT), intitulado The digital terrain model – theory and applications, publicado em 1958 na revista Photogrammetric Engineering, v.24, p. 433-442; o termo Modelo Digital de Terreno (MDT), foi utilizado pela primeira vez. No referido trabalho o MDT é definido como uma modelagem matemática da superfície contínua do terreno por um número de pontos que permita atingir o grau de exatidão requerida (MILLER e LAFLAMME, 1958 apud EL-SHEIMY, 1999). Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 53 A representação digital da superfície terrestre está atualmente associada a uma estrutura de dados, um conjunto de funções matemáticas para a realização das interpolações entre os pontos amostrados e a exatidão esperada na obtenção dos dados altimétricos. (MIKHAIL et al., 2001). Com o avanço das técnicas e aplicações dos modelos digitais de terreno, diferentes terminologias surgiram. Egels e Kasser (2002) fazem referência aos termos MDE, MDT e MDS. Os autores definem Modelo Digital de Elevação (MDE) como uma representação matemática e digital de um objeto e seu ambiente, destacando que, por se tratar de um conceito genérico, pode-se referir a elevação do terreno, mas também a qualquer nível acima dele. Quando a informação é limitada a elevação do terreno, o MDE é chamado de Modelo Digital do Terreno (MDT) e fornece informações sobre a elevação de qualquer ponto do terreno. Quando a informação se refere a elevação máxima de cada ponto, provenientes do terreno ou acima dele, o MDE é chamado de Modelo Digital de Superfície ou MDS (EGELS e KASSER, 2002). 2.9.1 FONTES DE DADOS PARA GERAÇÃO DO MDT A construção do MDT consiste em um processo de amostragem dos dados originais do terreno (elevações) e o estabelecimento das relações entre eles. Tais dados são obtidos de diferentes formas, sendo as mais comuns curvas de nível digitalizadas, métodos fotogramétricos ou levantamento de campo. Outras fontes de dados estão disponiveis atualmente, tais como radar, laser altimétrico e radar de abertura sintética (SAR) interferométrico. As curvas de nível são obtidas normalmente por digitalização de mapas analógicos, que constituem uma fonte abundante de dados devido aos acervos disponíveis. O levantamento de campo só é viável para projetos específicos que envolvam pequenas áreas pois demandam muito tempo na coleta. Já os dados obtidos por Fotogrametria derivam de duas fontes principais: as fotografias aéreas e as imagens de satélite. Segundo Schenk (1996) a geração do MDT a partir de um estereomodelo orientado compreende três etapas principais: 1. Correspondência de imagens: consiste em encontrar pontos homólogos; Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 54 2. Modelagem de superfície: consiste em interpolar e densificar uma superfície e; 3. Controle de qualidade: consiste em verificar e editar o MDT. Atualmente os sistemas fotogramétricos digitais executam de forma automatica as duas primeiras etapas, ficando a cargo do operador a terceira etapa, que consiste no controle de qualidade. 2.9.2 ESTRUTURAS DE DADOS PARA MDT’S Para construir um MDT é necessário estabelecer as relações topológicas entre os elementos amostrais, bem como o modelo de interpolação utilizado para aproximar o comportamento da superfície. Assim, um modelo de superfície eficiente deve possuir as seguintes características (EL-SHEIMY,1999): - Representar a superfície dentro da acurácia desejada; - Ser adequado para a eficiente coleta de dados; - Minimizar os requisitos de armazenamento de dados; - Maximizar a eficiência na manipulação de dados; e - Ser adequado para a análise de superfície. Três métodos são comumente utilizados para representar superfícies na forma digital: curvas de nível, malha regular e rede irregular de triângulos (TIN). 2.9.2.1 CURVAS DE NÍVEL Representações comuns da superfície as curvas de nível ou isolinhas indicam elevações por meio de contornos. El-Sheimy (1999) destaca como uma das principais desvantagens deste tipo de representação o fato de indicarem as elevações da superfície somente ao longo das isolinhas, assim as anomalias entre duas curvas não podem ser representadas. A elevação de pontos entre as isolinhas é obtida por interpolação. 2.9.2.2 MALHA REGULAR Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 55 A malha regular ou grid é uma estrutura matricial de dados que armazena uma amostra de pontos com uma origem comum e uma distância de amostragem constante nas direções X e Y, ou seja, com dados planimétricos indicados por linha e coluna da matriz. Cada ponto da malha possui um valor de elevação Z (EL-SHEIMY, 1999) Neste tipo de representação de superfície, o valor Z de pontos vizinhos aos amostrados pode ser obtido de forma aproximada por meio de interpolações entre os pontos adjacentes amostrados na malha. El-Sheimy (1999) destaca que se pode aumentar a acurácia desta representação diminuindo o intervalo entre os pontos, porém é importante destacar que: • Um intervalo muito grande entre os pontos provoca a perda de variações de relevo da superfície, • Diminuindo a distância entre os pontos pode resultar em um aumento na redundância dos dados. Isso principalmente nas áreas de superfície onde não existe uma variação de relevo muito grande (áreas planas). 2.9.2.3 REDE IRREGULAR DE TRIÂNGULOS (TIN) A Rede Irregular de Triângulos, ou TIN (Triangulated Irregular Network) sigla em inglês, é um modelo que gera uma superfície a partir de um conjunto de pontos irregularmente distribuídos. Ao contrário do modelo de malha regular, nesta estrutura os pontos amostrais irregularmente distribuídos podem ser adaptados ao terreno, com mais pontos nas áreas mais acidentadas do terreno e menos pontos nas áreas mais suaves (EL-SHEIMY, 1999). Desta forma a amostragem irregularmente espaçada é mais eficiente na representação de superfícies com variação de relevo do que a amostragem regularmente espaçada. No modelo TIN os pontos amostrais são conectados por linhas que formam triângulos e, em cada triângulo, a superfície é geralmente representada como um plano. O modelo da superfície gerado é contínuo, uma vez que cada superfície de triângulo é definida pelas elevações dos três vértices e os triângulos são adjacentes. Dissertação de Mestrado Extração Semi-Automática de Rodovias no Espaço-Objeto: uso Integrado de um Estéreo Par de Imagens Aéreas e um MDT Érico Fernando de Oliveira Martins Programa de Pós-Graduação em Ciências Cartográficas 56 Uma das vantagens deste modelo é que os pontos de amostragem distribuídos irregularmente podem ser adaptados para o terreno com mais pontos em áreas de terreno acidentado e menos em áreas de terreno liso. Assim, o modelo TIN é atraente por causa da simplicidade e economia (EL-SHEIMY, 1999). Embora ha