UNESP – UNIVERSIDADE ESTADUAL PAULISTA CAMPUS DE PRESIDENTE PRUDENTE FACULDADE DE CIÊNCIAS E TECNOLOGIA Presidente Prudente, SP Abril de 2019 RENATO CÉSAR DOS SANTOS EXTRAÇÃO E REGULARIZAÇÃO DE CONTORNOS DE TELHADOS DE EDIFICAÇÕES A PARTIR DE DADOS LiDAR USANDO O ALGORITMO ALPHA-SHAPE E CD-SPLINE RENATO CÉSAR DOS SANTOS EXTRAÇÃO E REGULARIZAÇÃO DE CONTORNOS DE TELHADOS DE EDIFICAÇÕES A PARTIR DE DADOS LiDAR USANDO O ALGORITMO ALPHA-SHAPE E CD-SPLINE Tese de doutorado apresentada ao Programa de Pós-Graduação em Ciências Cartográficas da Universidade Estadual Paulista – Faculdade de Ciências e Tecnologia – Campus de Presidente Prudente, como parte dos requisitos para a obtenção do título de Doutor em Ciências Cartográficas. Área de concentração em aquisição, análise e representação de informações espaciais. Orientador: Prof. Dr. Maurício Galo ___________________________________________________________________________ SANTOS, R. C ___________________________________________________________________________ SANTOS, R. C ___________________________________________________________________________ SANTOS, R. C DEDICATÓRIA Dedico este trabalho aos meus pais, Aparecido e Vera; e minha irmã Viviane, que sempre acreditaram em mim e me ajudaram a percorrer os caminhos em busca dos meus sonhos e objetivos. ___________________________________________________________________________ SANTOS, R. C AGRADECIMENTOS A realização deste trabalho teve a colaboração direta e indireta de diversas pessoas, as quais expresso meus sinceros agradecimentos. A Deus, pelo dom da vida, da sabedoria, pela graça e força para atingir meus objetivos. Aos meus pais, Aparecido e Vera, e minha irmã Viviane, por serem a minha base familiar, me auxiliando em todas as etapas já percorridas e alcançadas durante minha vida. Ao meu orientador, Prof. Dr. Maurício Galo, por sua dedicada e atenciosa orientação, constate empenho, sua paciência e conselhos valiosos. Ao meu supervisor durante o estágio de pesquisa no exterior, Prof. Dr. Ayman Fawzy Habib, que permitiu a minha participação em seu grupo de pesquisa na Universidade de Purdue nos Estados Unidos. Ao Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), pelo suporte financeiro durante os primeiros meses de doutorado (Proc. n° 140318/2015-1). À Fundação de Amparo à Pesquisa do Estado de São Paulo - FAPESP, pela concessão da bolsa de Doutorado nos meses subsequentes (Proc. n° 2016/12167-5) e pela concessão da Bolsa Estágio de Pesquisa no Exterior (BEPE) durante o período de oito meses (abril-novembro de 2017) (Proc. n° 2016/20814-0). Ao Programa de Pós-Graduação em Ciências Cartográficas (PPGCC), à Universidade Estadual Paulista (UNESP) e à Universidade de Purdue pela infraestrutura fornecida. Aos amigos do PPGCC pelas frequentes discussões, ajudas mútuas, e confraternizações, os quais auxiliam na execução dos projetos de pesquisa e contribuem para um ambiente de convívio agradável entre estudantes e professores. Aos meus irmãos de repúblicas pelas risadas, conselhos e companheirismo: Tiago, Pedro, Flávio, Willian, Fabiano, Lucas, Leomar, Bruno, Luis Fernando, Aruane e Viviane. A todos os professores, desde o ensino fundamental até a pós-graduação, que sempre estiveram dispostos a auxiliar os alunos e transmitirem seus amplos conhecimentos. Aos meus amigos de Lafayette, Indiana/EUA, os quais compartilharam momentos e histórias memoráveis: Doug, Gabriel, Geraldo, Talita, Mariana, Dio-Bala e Cesar. A todos os meus amigos e familiares que contribuíram direta ou indiretamente nessa caminhada. Em especial agradeço: André, Pacheco, Alemão, Luiz Eduardo, Aline Avance, Maria Tereza, Gisely e o tio Marco. ___________________________________________________________________________ SANTOS, R. C À banca de qualificação e da defesa final, pelas sugestões que contribuíram para a versão final deste trabalho. À empresa Sensormap Geotecnologia e à Sociedade Internacional de Fotogrametria e Sensoriamento Remoto (International Society for Photogrammetry and Remote Sensing - ISPRS) que forneceram os conjuntos de dados LiDAR. O presente trabalho foi realizado com apoio da Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Código de Financiamento 001. ___________________________________________________________________________ SANTOS, R. C RESUMO Esta tese trata da extração e regularização automática de contornos de telhados de edificações obtidos a partir de dados LiDAR (Light Detection and Ranging) adquiridos por sistema de varredura a LASER (Light Amplification by Stimulated Emission of Radiation) aerotransportado. Em linhas gerais, dois problemas são tratados. O primeiro corresponde à determinação adaptativa do parâmetro α do algoritmo alpha-shape, utilizado na obtenção do contorno aproximado, a partir da nuvem de pontos. O segundo refere-se à regularização/modelagem dos contornos de edificações no espaço tridimensional, incluindo edificações formadas por segmentos curvos de maior complexidade. Com relação ao primeiro problema, duas abordagens foram propostas, ambas baseadas no espaçamento médio entre os pontos. A principal contribuição das abordagens propostas está ligada à determinação adaptativa de α, possibilitando minimizar a influência da variação da densidade de pontos. Para solucionar o problema ligado a regularização de contornos, uma metodologia baseada no conceito de CD-Spline (Changeable Degree Spline) foi desenvolvida. A principal contribuição do uso da CD-Spline está ligada à habilidade de modelar contornos formados por segmentos com diferentes níveis de complexidade no espaço n-dimensional, sendo esses modelados por funções polinomiais de diferentes graus. Na metodologia proposta, a função polinomial que melhor modela cada segmento é selecionada de forma automática por meio da análise estatística dos resíduos em uma abordagem iterativa. Para validar as abordagens propostas dois conjuntos de dados LiDAR foram considerados. O primeiro corresponde ao Unesp Photogrammetric Dataset de Presidente Prudente/Brasil, e o segundo corresponde aos dados de Vaihingen/Alemanha, disponibilizado pela Sociedade Alemã de Fotogrametria. Considerando a determinação do parâmetro α, as análises qualitativa e quantitativa indicaram que as abordagens propostas possibilitam minimizar a influência da variação de densidade e apresentam potencial na extração de contornos de edificações, apresentando melhores resultados quando comparado com uma abordagem mais simples, como por exemplo, o uso de um parâmetro α global. Com relação a regularização de contornos, os resultados mostraram que o método proposto pode ser aplicado na modelagem de diferentes tipos de contornos, tendo resultados satisfatórios mesmo diante de contornos formados por segmentos curvos de diferente complexidade. Além disso, a abordagem foi capaz de recuperar o contorno em regiões com oclusão, causada por vegetação, e mostrou-se robusta a conjuntos de dados com diferentes densidades. Palavras-chave: Fotogrametria. Extração de contornos de telhados. Regularização de contornos de telhados. Modelagem de contornos. Dados LiDAR. Algoritmo alpha-shape. CD- Spline. ___________________________________________________________________________ SANTOS, R. C ABSTRACT This Doctoral dissertation deals with the automatic extraction and regularization of building roof boundaries from LiDAR (Light Detection and Ranging) data, obtained by airborne LASER (Light Amplification by Stimulated Emission of Radiation) scanning. In this context, two problems were explored. The first corresponds to the adaptive determination of the parameter α of the alpha-shape algorithm, used to extract the approximate contour, from the available point cloud. The second refers to the regularization/modeling of building boundaries in the three-dimensional space, including buildings formed by curved segments of high complexity. Regarding the first problem, two approaches were proposed, both based on average point spacing. The main contribution of the approaches is related to the adaptive determination of α, allowing to minimize the influence of the point density variation. In order to solve the problem related to boundary regularization, a method based on the concept of CD-Spline (Changeable Degree Spline) was developed. The CD-Spline has ability to model boundaries formed by segments with different levels of complexity in n-dimensional space, which are modeled by polynomial functions of different degrees. In order to select the polynomial function automatically, an iterative approach of the CD-Spline was proposed. In this methodology, the polynomial function that best models each segment is selected by means of the statistical analysis of the residuals in each iteration. Two LiDAR datasets were considered to validate the proposed approaches. The first corresponds to the Unesp Photogrammetric Dataset of Presidente Prudente/Brazil, whereas the second corresponds to Vaihingen/Germany, being made available by German Association of Photogrammetry. Considering the determination of the parameter α, the qualitative and quantitative analyzes indicated that the proposed approaches are robust to density variation and have potential in the building boundary extraction, having better results when compared to a simpler approach, for example, the use of a global parameter. With respect to boundary regularization, the results indicated that the proposed method has ability to model of different types of boundaries, having satisfactory results even in contours formed by curved segments of different complexity. In addition, the approach was able to recover the contour in occlusion regions, caused by vegetation, and was robust in different densities. Keywords: Photogrammetry. Building boundary extraction. Building roof boundary regularization. Contour modeling. LiDAR data. Alpha-shape algorithm. CD-Spline. ___________________________________________________________________________ SANTOS, R. C LISTA DE TABELAS Tabela 2.1 - Comparação entre dados LiDAR e a fotogrametria convencional no contexto de extração de edificações. ............................................................................................................ 18 Tabela 6.1 - Parâmetros utilizados no processo de detecção dos pontos de telhado para as diferentes nuvens de pontos LiDAR......................................................................................... 57 Tabela 6.2 - Parâmetros de qualidade para diferentes edificações e estratégias, considerando a nuvem de pontos com densidade de 5,8 pontos/m2.................................................................. 64 Tabela 6.3 - Parâmetros de qualidade para diferentes edificações e estratégias, considerando a nuvem de pontos com densidade de 12,5 pontos/m2................................................................ 65 Tabela 6.4 - Parâmetros de qualidade para diferentes edificações e estratégias, considerando os dados de Vaihingen/Alemanha (4 pontos/m2)...................................................................... 66 Tabela 6.5 - Parâmetros de qualidade usando o método de regularização baseado na abordagem iterativa da CB-Spline............................................................................................ 72 ___________________________________________________________________________ SANTOS, R. C LISTA DE FIGURAS Figura 1.1 - Variação da densidade de pontos em dados reais. Recortes realizados sobre a mesma nuvem de pontos. ........................................................................................................... 6 Figura 1.2 - Exemplo de aplicação do algoritmo alpha-shape. Densidade aproximadamente igual (a, b), densidade com variação significativa (c, d). ........................................................... 6 Figura 1.3 - Edificações compostas por contornos curvos na área urbana de Presidente Prudente - SP .............................................................................................................................. 8 Figura 2.1 – Exemplos de sistemas de varredura a LASER e respectivos padrões de amostragem. .............................................................................................................................. 12 Figura 2.2 - Representação de alguns elementos relacionados à geometria de aquisição dos dados LiDAR. Elementos envolvidos na projeção do feixe LASER no terreno (a) e largura da faixa de varredura (b). .............................................................................................................. 13 Figura 2.3 - Situações que ocorrem múltiplos retornos (múltiplos ecos). ................................ 14 Figura 2.4 - Componentes de um sistema de varredura a LASER aerotransportado e suas relações geométricas. ................................................................................................................ 15 Figura 2.5 - Elementos do formato “.LAS”, versão 1.1. .......................................................... 17 Figura 2.6 - Nuvem de pontos fotogramétrica (a) e LiDAR (b). Perfil gerado sobre a nuvem fotogramétrica (c) e LiDAR (d). ............................................................................................... 19 Figura 2.7 - Imagem aérea composição das bandas RGB (red, green, blue) (a), e imagem intensidade obtida pelo LASER (b). ......................................................................................... 19 Figura 2.8 - Pontos LiDAR amostrados sobre telhados de edificações, coloridos de acordo com a altura. Recorte realizado a partir de diferentes nuvens de pontos: 2,9 pontos/m2 (a), 5,8 pontos/m2 (b), 12,5 pontos/m2 (c). ...................................................................................... 20 Figura 2.9 - Recortes obtidos a partir da mesma nuvem de pontos LiDAR. Pontos coloridos de acordo com a densidade de pontos. .......................................................................................... 21 Figura 2.10 - Exemplos de oclusões causadas por construções altas. ...................................... 21 Figura 2.11 - Vegetação localizadas sobre parte da edificação (a, c). Pontos amostrados sobre os telhados (b, d). ...................................................................................................................... 22 Figura 2. 12 - Imagem aérea de uma cena com alta complexidade (a). Exemplo do processo de segmentação visto de diferentes pontos de vista (b, c). ............................................................ 22 Figura 3.1 - Nuvem de pontos contento outliers positivos e negativos. ................................... 24 ___________________________________________________________________________ SANTOS, R. C Figura 3.2 - Grade de células quadradas (a) e representação do histograma de frequência das alturas (c) para a célula selecionada (b).................................................................................... 25 Figura 3.3 - Pontos sementes e geração da estrutura de triângulos a partir dos pontos sementes. .................................................................................................................................. 26 Figura 3.4 - Princípio do método de filtragem. ........................................................................ 27 Figura 3.5 - Resultado do processo de crescimento de regiões antes (a) e após (b) eliminação dos pequenos agrupamentos. .................................................................................................... 29 Figura 3.6 - Agrupamentos coloridos de acordo com o valor de entropia médio (a), e resultado da separação em duas classes: edificação (vermelho), e não edificação (verde). .................... 32 Figura 3.7 - Representação dos elementos derivados da matriz de erro no contexto da extração de contornos. ............................................................................................................................. 33 Figura 3.8 - Distâncias entre os contornos extraído A (polígono azul) e de referência B (contorno laranja). Mínimas distâncias entre os vértices de A e B (retas em cinza) e distância Hausdorff (reta preta) (a). Distâncias utilizadas no cálculo da métrica PoLiS representadas pelas retas pretas (b). ................................................................................................................ 35 Figura 4.1 - Resultados obtidos considerando diferentes valores de α. ................................... 37 Figura 4.2 - Critério utilizado pelo algoritmo alpha-shape. Na Figura 4.2a os pontos pi e pj representam um segmento do contorno, enquanto que na Figura 4.2b pi e pj formam um segmento interno. ..................................................................................................................... 37 Figura 4.3 - Representação da malha triangular para uma dada edificação, antes (a) e após (b) executar o processo de identificação e eliminação das longas arestas. .................................... 39 Figura 4.4 - Seleção da vizinhança considerando um círculo centrado sobre o ponto de interesse. Vizinhança do ponto localizado sobre a borda da edificação (b) e no meio da edificação (c). ........................................................................................................................... 41 Figura 4.5 - Representação dos tipos de inconsistências (a). Extração do contorno antes (b) e após (c) aplicar o processo de refinamento. ............................................................................. 42 Figura 5.1 - Modelagem dos pontos de contorno. Pontos de contorno (a). Modelagem usando B-Spline (b) e CD-Spline (c). ................................................................................................... 45 Figura 5.2 - Determinação da curva fechada. Curva aberta (a), e curva fechada (c) obtida considerando injunção no ponto de fechamento. Padrão da matriz A correspondente a curva aberta (b) e fechada (d). ............................................................................................................ 48 Figura 5.3 - Identificação dos pontos críticos. Resultado derivado do algoritmo Douglas- Peucker (b), sendo destacados os pontos redundantes. Resultado após eliminação dos pontos redundantes (c). Representação do ângulo entre os segmentos sucessivos do contorno (d). ... 50 ___________________________________________________________________________ SANTOS, R. C Figura 5.4 – Exemplificação dos resultados derivados da abordagem iterativa da CD-Spline. Para cada iteração são apresentados os pontos de contornos (pontos em preto) e o contorno regularizado (contorno em azul), bem como o gráfico dos resíduos em módulo. As linhas verticais no gráfico delimitam cada segmento. Os pontos de contornos são ordenados no sentido anti-horário, sendo destacado em vermelho o ponto inicial. ....................................... 52 Figura 6.1 - Nuvem de pontos com diferentes densidades: 2,9 pontos/m2 (a), 5,8 pontos/m2 (b), 12,5 pontos/m2 (c). ............................................................................................................. 54 Figura 6.2 - Região da nuvem sem sobreposição (a) e com sobreposição de faixas (b). ......... 55 Figura 6.3 - Região selecionada sobre a nuvem de pontos com 12 pontos/m2. Imagem aérea (a) e dados LiDAR coloridos de acordo com a altura (b). ....................................................... 56 Figura 6.4 - Perfil dos dados LiDAR antes (a) e após da remoção dos outliers (b). ................ 57 Figura 6.5 - Resultado da filtragem. Pontos de terreno (marrom) e não terreno (azul). .......... 58 Figura 6.6 – Representação dos pontos de não terreno, sendo marcado na cor amarela os pontos relacionados aos pequenos agrupamentos. ................................................................... 59 Figura 6. 7 - Resultado derivados do processo de crescimento de regiões após eliminação de pequenas regiões. ...................................................................................................................... 60 Figura 6.8 - Separação dos agrupamentos em edificações (vermelho) e não edificação (verde).. .................................................................................................................................... 61 Figura 6.9 - Imagens das edificações selecionadas nos experimentos e perfil gerado a partir dos dados LiDAR considerando o segmento A-B. ................................................................... 63 Figura 6.10 - Resultados gerados a partir da nuvem de pontos com 5,8 pontos/m2. Espaçamento médio (a-d). Contornos considerando o parâmetro α fixo (α = 0,45 m) (e-h), parâmetro estimado para cada edificação (i-l) e usando o parâmetro adaptativo ponto-a-ponto (m-p). ........................................................................................................................................ 64 Figura 6.11 - Resultados gerados a partir da nuvem de pontos com 12,5 pontos/m2. Espaçamento médio (a-c). Contornos considerando o parâmetro α fixo (α = 0,33 m) (d-f), parâmetro estimado para cada edificação (g-i) e usando o parâmetro adaptativo ponto-a-ponto (j-l). ........................................................................................................................................... 65 Figura 6.12 - Resultados gerados a partir dos dados de Vaihingen/Alemanha. Espaçamento médio (a-d). Contornos considerando o parâmetro α fixo (α = 0,55 m) (e-h), parâmetro estimado para cada edificação (i-l) e usando o parâmetro adaptativo ponto-a-ponto (m-p). ... 66 Figura 6.13 - Imagens das edificações selecionadas e perfil dos telhados das edificações B2, B6 e B8. Os perfis foram gerados a partir dos dados LiDAR e coloridos de acordo com altura.. ....................................................................................................................................... 69 ___________________________________________________________________________ SANTOS, R. C Figura 6.14 - Parâmetros de qualidade para as edificações B2, B3, B6, B9 e B10, variando Tdist (a), Tang (b) e o nível de significância (c). ......................................................................... 70 Figura 6.15 – Resultados usando diferentes valores de Tang paras as edificações B2, B9 e B10. Representação dos contornos regularizados e pontos de quinas no espaço 2D (a), e contornos regularizados no espaço 3D (b). ............................................................................................... 71 Figura 6.16 - Contornos de edificações regularizados usando o método proposto, nuvem de pontos com densidade de 12,5 pontos/m2. Contornos regularizados e pontos de quinas sobrepostos aos pontos de telhados (a) e contornos projetados sobre a imagem aérea (b). ..... 72 Figura 6.17 - Resultados derivados da regularização de contorno considerando diferentes densidades de pontos: 2,9 pontos/m2 (a, d, g), 5,8 pontos/m2 (b, e, h) e 12,5 pontos/m2 (c, f, i).. .............................................................................................................................................. 73 Figura 6.18 - Edificações com vegetação próximas. Resultados usando o método proposto sobrepostos aos pontos de telhado da nuvem LiDAR (a) e projetados na imagem aérea (b). . 74 ___________________________________________________________________________ SANTOS, R. C SUMÁRIO CAPÍTULO 1 INTRODUÇÃO……………………………………………………………………………. 1 1.1 Caracterização do problema…………………………………………………………… 4 1.1.1 Extração do contorno aproximado………………………………………………… 4 1.1.2 Regularização dos contornos de telhados.................................................................. 6 1.2 Abordagem proposta....................................................................................................... 8 1.3 Hipótese........................................................................................................................... 9 1.4 Objetivos......................................................................................................................... 9 1.5 Estrutura do trabalho....................................................................................................... 10 CAPÍTULO 2 SISTEMA DE VARREDURA A LASER AEROTRANSPORTADO E AS CARACTERÍSTICAS DOS DADOS LIDAR..................................................................... 11 2.1 Sistemas de varredura a LASER aerotransportado......................................................... 11 2.1.1 Elementos associados à geometria de aquisição....................................................... 12 2.1.2 Modelo Matemático.................................................................................................. 14 2.1.3 Estrutura do formato LAS (LiDAR Exchange Format)............................................ 17 2.2 Comparação entre os dados LiDAR e a fotogrametria convencional............................. 18 2.3 Fatores que influenciam a extração de edificações a partir de dados LiDAR................. 20 CAPÍTULO 3 DETECÇÃO DOS PONTOS LIDAR AMOSTRADOS SOBRE TELHADOS DE EDIFICAÇÕES E AVALIAÇÃO DA QUALIDADE DOS CONTORNOS...................... 23 3.1 Detecção de outliers na nuvem de pontos LiDAR.......................................................... 23 3.2 Filtragem dos dados LiDAR............................................................................................ 25 3.3 Segmentação dos pontos de não terreno.......................................................................... 27 3.4 Detecção dos pontos LiDAR amostrados sobre edificações........................................... 30 3.5 Avaliação da qualidade................................................................................................... 32 3.5.1 Parâmetros de qualidade baseados em área............................................................... 32 3.5.2 Parâmetros de qualidade baseados em medidas lineares........................................... 33 ___________________________________________________________________________ SANTOS, R. C CAPÍTULO 4 PROPOSTA DE ABORDAGENS ADAPTATIVAS DO ALGORITMO ALPHA- SHAPE VISANDO A EXTRAÇÃO DE CONTORNOS DE TELHADOS........................ 36 4.1 Algoritmo alpha-shape.................................................................................................... 36 4.2 Extração de contornos de telhados de edificação a partir do parâmetro α estimado por edificação............................................................................................................................... 38 4.2.1 Geração da triangulação de Delaunay e eliminação das longas arestas.................... 38 4.2.2 Estimação do parâmetro α por edificação................................................................. 40 4.3 Extração de contornos de telhados de edificação a partir do parâmetro α estimado ponto-a-ponto........................................................................................................................ 40 4.3.1 Estimação do parâmetro α ponto-a-ponto................................................................. 40 4.3.2 Refinamento dos contornos derivados do algoritmo alpha-shape............................. 42 CAPÍTULO 5 PROPOSTA DE UMA ABORDAGEM ITERATIVA DA CD-SPLINE PARA A REGULARIZAÇÃO DE CONTORNOS DE TELHADOS................................................. 43 5.1 B-Spline e CD-Spline...................................................................................................... 43 5.2 Funções CD-Spline e estimação dos pontos de controle................................................. 45 5.3 Continuidade entre dois segmentos adjacentes............................................................... 47 5.4 Curva CD-Spline fechada................................................................................................ 47 5.5 Identificação dos pontos de nó........................................................................................ 49 5.6 Abordagem iterativa da CD-Spline proposta.................................................................. 50 CAPÍTULO 6 RESULTADOS E DISCUSSÕES........................................................................................ 53 6.1 Conjunto de dados LiDAR.............................................................................................. 53 6.1.1 Conjunto de pontos LiDAR de Presidente Prudente/Brasil...................................... 53 6.1.2 Conjunto de pontos LiDAR de Vaihingen/Alemanha............................................... 54 6.2 Detecção dos pontos LiDAR amostrados sobre telhados de edificações........................ 55 6.3 Extração de contornos de telhados de edificações considerando abordagens adaptativas do algoritmo alpha-shape................................................................................... 61 6.3.1 Resultados................................................................................................................. 61 6.3.2 Discussões................................................................................................................. 67 6.4 Regularização dos contornos de telhados de edificações por meio da abordagem iterativa da CD-Spline........................................................................................................... 68 6.4.1 Resultados................................................................................................................ 68 6.4.2 Discussões................................................................................................................ 74 ___________________________________________________________________________ SANTOS, R. C CAPÍTULO 7 CONCLUSÕES E RECOMENDAÇÕES............................................................................. 77 7.1 Síntese do trabalho.......................................................................................................... 77 7.2 Conclusões e Recomendações......................................................................................... 78 7.2.1 Conclusões................................................................................................................. 78 7.2.2 Recomendações......................................................................................................... 80 REFERÊNCIAS.................................................................................................................... 82 1 Introdução SANTOS, R. C 1 CAPÍTULO 1 Introdução Os Sistemas de Informações Geográficas (SIGs) são utilizados em diversas aplicações: planejamento urbano, avaliação dos danos causados por desastres naturais, planejamento de redes de telecomunicações, vigilância, transportes, dentre outras. Com isso, as tarefas executadas com o intuito de obter um produto cartográfico atualizado e acurado tornam-se fundamentais. De acordo com as Nações Unidas (2018), estima-se que 55% da população mundial reside na área urbana, sendo esperado um crescimento para 68% até o ano de 2050. Esses números reforçam a importância da aplicação do SIG visando o crescimento sustentável e organizado das cidades e de sua população. No contexto do planejamento urbano, as edificações têm um papel primordial, uma vez que uma alta porcentagem da superfície urbana é coberta por esse tipo construção. Além disso, o desenvolvimento das cidades impacta diretamente os processos de ampliações e implantação de novas edificações, bem como as ações relacionadas a manutenção e conservação do meio ambiente. Por tal importância, o tema relacionado à extração de edificações de forma automática, ou mesmo semiautomática, vem sendo pesquisada por diversos autores (KIM e HABIB, 2009; DAL POZ et al., 2009b; AWRANGJEB, 2016, GAVANKAR e GHOSH, 2018, SANTOS et al., 2019a). A extração de edificações pode ser realizada usando diferente tipos de dados obtidos remotamente: imagens aéreas (DOS SANTOS, 2002; MANNO-KOVACS e SZIRANYI, 2015), imagens de satélite (RASHA e MARPU, 2017), ou dados LiDAR (KWAK e HABIB, 2014; JUNG et al., 2017). O presente trabalho explora o uso de nuvem de pontos adquirida 1 Introdução SANTOS, R. C 2 por um sistema de varredura a LASER (Light Amplification by Stimulated Emission of Radiation) aerotransportado, que se baseia no princípio da medição de distância a partir da luz (Light Detection and Ranging – LiDAR). Embora os sistemas com este propósito adquiram várias informações, que, após tratamento adequado, permitem gerar a nuvem de pontos com coordenadas conhecidas no espaço tridimensional, o termo “dados LiDAR” será utilizado para se referir à nuvem de pontos gerada. É relevante destacar que o uso de dados LiDAR apresenta vantagens e desvantagens em relação a Fotogrametria convencional. A principal vantagem está relacionada a aquisição direta da nuvem de pontos tridimensional, eliminando a necessidade de um processo de correspondência. O processo de medição de pontos homólogos em imagens é considerado uma limitação na Fotogrametria convencional devido aos problemas de correspondência, especialmente em áreas homogêneas, regiões com oclusão, sombra e padrões repetitivos. Em contrapartida, os dados LiDAR não possuem informação semântica, armazenando apenas a intensidade do pulso, e a qualidade das bordas é dependente da densidade de pontos e do padrão de varredura. A integração dos dados LiDAR e imagens é uma alternativa para solucionar algumas dessas limitações, sendo esta explorada por alguns autores (KIM e HABIB, 2009; DU et al., 2016; DAL POZ, 2018). Apesar de apresentar resultados promissores, a integração tem o desafio de relacionar conjunto de dados com diferentes características. De acordo com Galvanin e Dal Poz (2012) os métodos para detecção e extração de edificações a partir de dados LiDAR são categorizados em quatro grupos: detecção de edificações, extração de contornos de telhados de edificações, extração de telhados de edificações, e extração de modelos de edificações. A detecção de edificações tem o objetivo de identificar o que é edificação. A extração de contornos de edificações consiste em obter os segmentos de reta, ou de curvas, que compõem o contorno de interesse. Normalmente, o processo é divido em duas etapas: primeiramente, o contorno aproximado é extraído, e na sequência submetido a um processo de regularização ou modelagem. A extração de telhados é baseada em um método de segmentação, o qual agrupa os pontos LiDAR em faces planas e outros objetos. O processo de segmentação utiliza-se de um critério de homogeneidade, por exemplo, similaridade de altura e/ou similaridade do vetor normal. Por fim, a extração de modelos de edificações consiste em gerar uma representação tridimensional das edificações, a qual envolve as três etapas: detecção das edificações, extração dos contornos e extração dos telhados. 1 Introdução SANTOS, R. C 3 Os métodos de extração de edificações podem variar de acordo com a estrutura dos dados de entrada, regular ou irregular. O armazenamento dos dados LiDAR em uma malhar regular facilita o processo manipulação dos dados, e possibilita que técnicas de processamento de imagens sejam aplicadas. No entanto, o processo de geração da malha regular, usualmente realizado por meio de um método de interpolação, provoca a degradação da acurácia posicional e perda de característica de descontinuidade nas regiões de borda. Alternativamente, as manipulações podem ser realizadas diretamente sobre a nuvem de pontos original, que possui uma distribuição não regular. Nesse último caso, é possível utilizar estruturas que permitem o armazenamento de dados irregularmente espaçados e têm o intuito de facilitar operações de buscas, como é o caso da rede de triângulos irregulares (TIN- Triangulated Irregular Network) e da estrutura Kd-Tree. Apesar de uma maior complexidade computacional, o uso da nuvem original permite conservar as características dos dados de entrada. Considerando a extração de contornos de telhados de edificações, os métodos podem ser divididos em duas abordagens: baseado em modelos (do inglês, model-driven) e dados (do inglês, data-driven). De acordo com Kwak e Habib (2014), a diferença entre as duas abordagens está relacionada à quantidade de informação que é incorporada a cada processo. Na abordagem baseada em modelos são pré-definidos modelos paramétricos, os quais são atualizados usando informações derivadas do conjunto de dados. Apesar de robusta, essa abordagem é limitada aos modelos pré-estabelecidos. Considerando essa limitação, uma alternativa é utilizar a abordagem baseada nos dados. Nesse caso, o contorno da edificação é modelado independente da sua forma, uma vez que o método tenta se ajustar aos dados. Antes de iniciar o processo de extração de contornos de edificações, os dados LiDAR usualmente são submetidos a um fluxo de processamento visando selecionar os pontos amostrados sobre os telhados dos edifícios. Na literatura são encontradas inúmeras metodologias, as quais combinam diferentes tipos de operações, tais como: remoção de pontos espúrios, filtragem, segmentação, classificação, detecção de planos. Nesse trabalho o foco está voltado para a extração e a regularização dos contornos de telhados de edificações sobre dados LiDAR. Diante disso, os pontos de telhados foram selecionados usando metodologias já desenvolvidas. 1 Introdução SANTOS, R. C 4 1.1 Caracterização do problema 1.1.1 Extração do contorno aproximado A extração do contorno aproximado dos telhados consiste em identificar os pontos de bordas e realizar o traçado do contorno. De acordo com Lee et al. (2011), pontos irregularmente distribuídos e a presença de regiões côncavas tornam complicada a tarefa de identificar os pontos de bordas. Para contornar esse problema várias abordagens têm sido utilizadas, dentre elas: modificação do fecho convexo, triangulação de Delaunay, e o algoritmo alpha-shape (α-shape). Sampath e Shan (2007) propuseram uma abordagem baseada no fecho convexo modificado, a qual tem sido explorada por diversos autores Lee et al. (2011), e Kwak e Habib (2014). Esse método consiste em identificar, de forma iterativa, os pontos de borda por meio do teste fecho convexo realizado localmente. A dificuldade está relacionada com a determinação do tamanho da vizinhança, e a limitação corresponde à não extração das bordas internas. Lee et al. (2011) apresentaram um melhoramento do método, com o intuito de identificar os contornos internos. Nesse sentido, algumas informações adicionais são consideradas: diferença de altura, ângulo máximo de varredura, e espaçamento médio dos pontos ao longo da direção de varredura. Outra forma de obter os pontos de bordas é por meio do uso da triangulação de Delaunay. Nessa abordagem, os segmentos de borda são identificados considerando as arestas externas da triangulação, relacionada a cada edificação, como pode ser visto em Maas e Vosselman (1999), Jing-zhong et al. (2010) e Awranjeb (2016). A abordagem original também não permite identificar os contornos internos. Para contornar esse problema Awranjeb (2016) propõe uma solução que analisa o comprimento das arestas e remove as arestas consideradas longas. O algoritmo α-shape (EDELSBRUNNER et al., 1983) tem a vantagem de realizar a extração dos contornos internos de forma direta, ou seja, sem a necessidade de uma etapa adicional como é o caso dos métodos baseados no fecho convexo modificado e na triangulação de Delaunay. O algoritmo tem sido explorado por vários autores no contexto da extração de contornos de edificações (JOCHEM et al., 2009, SHEN et al., 2011, SATARI et al., 2012, e ALBERS et al., 2016). O princípio consiste em identificar os pontos de bordas considerando um critério pré-estabelecido, o qual baseia-se no valor do parâmetro α. O valor de α corresponde ao raio do círculo utilizado para verificar se dois pontos vizinhos formam 1 Introdução SANTOS, R. C 5 um segmento de contorno. O grande desafio está relacionado à determinação de um valor ótimo para α, sendo este influenciado pela densidade de pontos e pelo nível de detalhamento desejado. Na literatura é possível encontrar trabalhos que incorporam a informação da densidade na execução do algoritmo alpha-shape, como é o caso do Locally-Density-Adaptive-α-shapes (LDA-α-shapes) (MAILLOT et al., 2010). Apesar do processo considerar a variação de densidade, a definição do valor de α continua sendo um problema. Com o intuito de contornar tal dificuldade, Presles et al (2011) propuseram uma abordagem que realiza a determinação automática do valor ótimo para α. O método considera um critério quantitativo definido a partir de algumas medidas: área, perímetro e convexidade. A limitação dessa última abordagem refere-se a não extração de contornos internos. Segundo Jochem et al. (2009), o espaçamento médio dos pontos LiDAR é um bom estimador para o parâmetro α. Shen (2008), Shen et al. (2011) e He et al. (2014) consideram uma ideia similar, sendo o valor de α obtido pela multiplicação do espaçamento médio dos pontos por um fator multiplicador, determinado empiricamente. No entanto, o uso de um valor constante para extrair os contornos de todas as edificações presentes na nuvem de pontos pode não ser a melhor alternativa, uma vez que a densidade de pontos pode variar ao longo da nuvem ou da própria edificação. As causas da variação de densidade podem estar relacionadas aos seguintes fatores: mudança de velocidade da aeronave, armazenamento de múltiplos retornos (normalmente em regiões de vegetação e bordas), mudança de altitude e orientação da aeronave, presença de oclusões, e sobreposição de faixas. Nesse caso, torna-se relevante o uso de um parâmetro α adaptativo para solucionar o problema relacionado à variação de densidade. Na Figura 1.1 são apresentados exemplos de variação de densidade em dados reais. A Figura 1.2 ilustra a aplicação do algoritmo alpha-shape a partir da adoção de um valor fixo para α. Nesse contexto, dois conjuntos de pontos simulados com diferentes densidades são considerados. No primeiro, a densidade de pontos é aproximadamente constante, enquanto que no segundo, o conjunto apresenta uma variação significativa. O uso de um valor constante para α permite recuperar o contorno completo quando a densidade é aproximadamente constante (Figura 1.2b). No caso de uma alta variação de densidade, o uso de um único parâmetro α pode produzir resultados incoerentes, como pode ser observado na Figura 1.2d. 1 Introdução SANTOS, R. C 6 Figura 1.1 - Variação da densidade de pontos em dados reais. Recortes realizados sobre a mesma nuvem de pontos. Figura 1.2 - Exemplo de aplicação do algoritmo alpha-shape. Densidade aproximadamente igual (a, b), densidade com variação significativa (c, d). 1.1.2 Regularização dos contornos de telhados Os contornos extraídos a partir de dados LiDAR apresentam uma forma serrilhada (zig-zag). Diante disso, os métodos de regularização tentam modelar segmentos de retas e/ou curvos aos pontos de contorno, obtendo resultados mais próximos da realidade. Além disso, o resultado derivado da regularização facilita a manipulação e representação dos contornos em bases cartográficas, bem como o seu uso em aplicações da Fotogrametria, como por exemplo, na obtenção de modelos 3D de edificações e geração de ortoimagem verdadeira. De modo geral, os métodos de regularização de contornos consideram técnicas que permitem realizar a estimação dos parâmetros de retas e/ou curvas, visando modelar os 1 Introdução SANTOS, R. C 7 diferentes segmentos que compõem o contorno. Mass e Vosselman (1999), Sampath e Shan (2007), Jing-zhong et al. (2010), Lee et al. (2011), Awranjeb (2016) e Xie et al. (2018) exploram o Método dos Mínimos Quadrados (MMQ) para obter os segmentos de retas que compõem o contorno. O conjunto de pontos referente a cada segmento é selecionado por meio da determinação dos pontos de quinas, também conhecidos como pontos críticos, e na sequência submetido ao processo de ajustamento. Usualmente, a metodologia de ajuste engloba injunções de paralelismo e perpendicularidade a partir da orientação dominante da edificação. Além disso, alguns trabalhos consideram contornos mais complexos, os quais são formados por quinas com ângulo diferente de 90° (non-right-angled corners) (JING-ZHONG et al., 2010, LEE et al., 2011 e XIE et al., 2018) e segmentos curvos (LEE et al., 2011). Em Satari et al. (2012) e Albers et al. (2016) as retas que compõem o contorno são obtidas por meio da transformada fuzzy Hough, e na sequência um processo de refinamento é executado, onde injunções de perpendicularidade e paralelismos são aplicadas. Kwak e Habib (2014) propuseram um algoritmo recursivo baseado no conceito do retângulo mínimo (RMBR - Recursive Minimum Bounding Rectangle), o qual determina o retângulo ou combinação de retângulos que melhor se ajusta aos pontos de contornos. Apesar dos vários trabalhos desenvolvidos, nenhum método é capaz de englobar todas as complexidades das edificações. Além disso, a maioria das metodologias consideram que os contornos são compostos apenas por segmentos retos. Considerando os métodos mencionados, apenas Lee et al. (2011) trabalharam com a modelagem de segmentos curvos. No entanto, estes autores se limitaram à curvas de segundo grau (parábola). Apesar de menos frequentes, edificações compostas por segmentos curvos são encontradas no ambiente real, como mostrado na Figura 1.3. Outra limitação identificada está relacionada ao espaço onde o processo de regularização é realizado, sendo usualmente executado no espaço bidimensional. Nesse caso, a informação altimétrica não é incluída e consequentemente o comportamento da altimetria ao longo do contorno não é modelado. Considerando os aspectos mencionados, torna-se relevante o desenvolvimento de uma metodologia capaz de modelar contornos de edificações mais complexas, composta por diferentes tipos de segmentos, inclusive curvos, e o comportamento altimétrico do contorno. 1 Introdução SANTOS, R. C 8 Figura 1.3 - Edificações compostas por contornos curvos na área urbana de Presidente Prudente - SP 1.2 Abordagem proposta Os problemas tratados na presente tese podem ser divididos em duas vertentes. A primeira está relacionada com a determinação, de forma adaptativa, do parâmetro α, utilizado no processo de extração de contornos a partir do algoritmo alpha-shape. A segunda, diz respeito ao desenvolvimento de uma metodologia de regularização de contornos no espaço tridimensional, englobando edificações compostas por segmentos de retas e curvos de diferentes complexidades. Com relação ao primeiro problema, duas diferentes abordagens são propostas. A primeira realiza a estimação de um parâmetro α para cada edificação de interesse. O processo baseia-se no espaçamento entre os pontos e considera como dados de entrada apenas os pontos amostrados sobre edificações. Na segunda abordagem também é considerado o espaçamento entre os pontos para estimar o parâmetro α. No entanto, a estimação é realizada ponto-a-ponto, isto é, para cada ponto é estimado um valor de α. A principal contribuição das abordagens está ligada à determinação adaptativa de α, o que pode minimizar a influência da variação da densidade de pontos no resultado final. Para solucionar o problema ligado à regularização de contornos, uma metodologia baseada no conceito de CD-Spline (Changeable Degree Spline) foi desenvolvida. O conceito de CD-Spline foi proposto por Shen e Wang (2010), e corresponde a uma variação da B- Spline. A principal vantagem do uso do CD-Spline está ligada à habilidade de modelar contornos formados por segmentos com diferentes níveis de complexidade no espaço n- dimensional, sendo esses modelados por funções polinomiais de diferente grau. Além disso, a 1 Introdução SANTOS, R. C 9 CD-Spline permite a inclusão de injunções aos pontos de junção entre os segmentos, e a determinação de uma função paramétrica que modela todo o contorno. O grande desafio do uso do conceito de CD-Spline está relacionado à definição dos dados de entrada: pontos do contorno, pontos críticos (responsáveis por identificar uma mudança de direção) e grau da função usada para modelar cada segmento. Nesse trabalho, os pontos de contornos são obtidos a partir da abordagem adaptativa ponto-a-ponto do algoritmo alpha-shape, proposta nessa tese; enquanto que, os pontos críticos são determinados usando o algoritmo Douglas-Peucker, seguido da generalização baseada em ângulos. Com o intuito de selecionar o grau da função polinomial de forma automática, uma abordagem iterativa usando o conceito CD-Spline foi proposta. Nessa metodologia, a função polinomial que melhor modela cada segmento é selecionada por meio da análise estatística dos resíduos em cada iteração. 1.3 Hipótese Em resumo, a tese de doutorado é estruturada sobre a seguinte hipótese: “Considerando o conjunto de pontos LiDAR obtidos por um sistema de varredura a LASER instalado em uma plataforma aérea, têm-se que a influência da variação da densidade de pontos, na extração de contornos de edificações, pode ser minimizada com o uso da abordagem adaptativa para a estimação do parâmetro α. Além disso, o uso da abordagem iterativa do conceito CD-Spline, juntamente com a análise estatística dos resíduos, pode contribuir na determinação automática do grau da função polinomial correspondente a cada segmento e na modelagem tridimensional de contornos de edificações formados por segmentos lineares e/ou curvos”. 1.4 Objetivos O objetivo central da tese pode ser divido em dois. O primeiro está relacionado a extração do contorno aproximado de telhados de edificações. Nesse caso, o objetivo consiste em desenvolver, implementar, aplicar e avaliar duas abordagens para a determinação automática do parâmetro α do algoritmo alpha-shape, sendo considerada em ambas a informação da variação da densidade de pontos. O segundo, refere-se à regularização de contornos. Nesse caso, o objetivo consiste em desenvolver, implementar, aplicar e avaliar o método de regularização baseado na abordagem iterativa da CD-Spline. Adicionalmente, a 1 Introdução SANTOS, R. C 10 robustez do método de regularização é analisada diante de diferentes aspectos: uso de diferentes limiares no processo de regularização, contornos com diferentes complexidades, e nuvem de pontos com diferentes densidades. 1.5 Estrutura do trabalho Esse trabalho está organizado em sete capítulos principais. No primeiro capítulo é apresentada uma introdução ao tema tratado, seguido da caracterização do problema, abordagem proposta, hipótese e objetivos. No segundo capítulo é apresentado o sistema de varredura a LASER aerotransportado, bem como algumas características da nuvem de pontos LiDAR. O terceiro capítulo trata da etapa de pré-processamento dos dados LiDAR, a qual engloba a detecção de pontos amostrados sobre edificações. Nesse capítulo também são descritos os parâmetros de qualidade utilizados na avaliação dos resultados. No quarto capítulo são apresentadas as duas abordagens desenvolvidas para a determinação adaptativa do parâmetro α. O quinto capítulo é usado para descrever a solução proposta para a regularização de contornos, baseada em uma abordagem iterativa do conceito CD-Spline. No sexto capítulo são descritos os conjuntos de dados utilizados e os experimentos realizados, além da discussão dos resultados. Finalmente, no sétimo capítulo são feitas as considerações finais sobre o trabalho realizado, bem como as conclusões e recomendações. 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 11 CAPÍTULO 2 Sistema de Varredura a LASER Aerotransportado e as Características dos Dados LiDAR Nesse capítulo é apresentada uma breve descrição dos princípios de um Sistema de Varredura a LASER Aerotransportado, englobando alguns parâmetros da geometria de aquisição e o modelo matemático usado na obtenção das coordenadas tridimensionais. Também é realizada uma breve comparação dos dados LiDAR e dos dados obtidos por aerofotogrametria convencional, no contexto da extração de edificações, destacando as vantagens e desvantagens do uso de cada abordagem. Por fim, alguns fatores que influenciam a extração de edificações a partir de dados LiDAR são apontados. 2.1 Sistemas de varredura a LASER aerotransportado Os sistemas de varredura LASER podem ser instalados em diferentes plataformas: barco, automóvel, veículo aéreo não tripulado (UAV – Unmanned aerial vehicle), e aeronave. No caso específico deste trabalho, considera-se os dados provenientes do sistema de varredura LASER instalado em uma plataforma aérea. Esse tipo de configuração é denominado por alguns autores (CENTENO e MITISHITA, 2007) como sistema de varredura a LASER aerotransportado (SVLA). O princípio de funcionamento do sistema de varredura aerotransportado baseia-se na utilização de um pulso de LASER que é disparado na direção da superfície terrestre, com o 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 12 auxílio de um sistema de varredura. Ao atingir a superfície, parte do sinal emitido é refletido na direção do sensor. O sensor mede a intensidade do sinal de retorno e o tempo decorrido entre a emissão e a captação do retorno. Esse último é usado para calcular a distância entre o sensor e o objeto, considerando que o pulso LASER se propaga à velocidade da luz (BALTSAVIAS, 1999). O padrão de amostragem dos pontos pode variar de acordo com o sistema óptico de lentes e espelhos utilizado para orientar os pulsos LASER na direção dos objetos. Na Figura 2.1 são apresentados alguns exemplos de sistemas de varredura, bem como o padrão de varredura gerado por cada um. Figura 2.1 – Exemplos de sistemas de varredura a LASER e respectivos padrões de amostragem. Adaptado de Vosselman e Mass (2010). 2.1.1 Elementos associados à geometria de aquisição Os elementos geométricos envolvidos na varredura de uma dada seção transversal do terreno são ilustrados na Figura 2.2. A projeção do feixe LASER no terreno ou footprint (D) depende do ângulo de divergência do pulso LASER (γ), da altura de voo (H), do ângulo de varredura instantâneo (β), bem como da inclinação local do terreno, como mostra a Figura 2.2a. Enquanto isso, a largura da faixa de varredura no terreno (Sw) é função da altura de voo média (Hm) e do ângulo de abertura máximo (θ) também conhecido como FOV (Field Of View) (Figura 2.2b). Os valores aproximados para o diâmetro (D) do footprint e a largura da faixa de varredura (Sw) podem ser obtidos a partir das Equações 2.1 e 2.2 (WEHR e LOHR, 1999). Para obter essas equações são consideradas algumas simplificações, tais como: terreno plano horizontal e ângulo de divergência do pulso muito pequeno. 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 13 𝐷 = 𝐻 𝑐𝑜𝑠2𝛽 𝛾 (2.1) 𝑆𝑊 = 2 𝐻𝑚 𝑡𝑔(𝜃 2⁄ ) (2.2) Figura 2.2 - Representação de alguns elementos relacionados à geometria de aquisição dos dados LiDAR. Elementos envolvidos na projeção do feixe LASER no terreno (a) e largura da faixa de varredura (b). Adaptado de Galo (2019). Em função do ângulo de divergência, o pulso LASER emitido pode ser refletido por diferentes objetos. Os múltiplos ecos geralmente ocorrem quando o feixe incide em superfícies que permitem a passagem de parte do feixe, como por exemplo, vegetação, ou bordas de objetos, como edificações. Na Figura 2.3 são apresentadas situações onde o feixe LASER atinge vários objetos. A parte do pulso que atinge o objeto mais próximo retorna primeiro e corresponde ao primeiro eco. Já a outra parte do pulso que continua até atingir o objeto mais distante origina o último eco. 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 14 Figura 2.3 - Situações que ocorrem múltiplos retornos (múltiplos ecos). O nível de detalhamento da superfície levantada por um sistema de varredura a LASER está diretamente relacionado com a densidade de pontos. Essa grandeza corresponde à quantidade de pontos amostrados por unidade de área, sendo expresso usualmente em pontos por metro quadrado (pts/m2). Segundo Ackermann (1999), a densidade de pontos depende de alguns elementos, tais como: altura de voo (H), velocidade da aeronave (v), ângulo de varredura (θ), taxa de repetição do pulso LASER (F), frequência de varredura (Fsc), direção do voo e tipo de terreno levantado. 2.1.2 Modelo Matemático As coordenadas dos pontos amostrados por um sistema de varredura aerotransportado são determinadas combinando as medidas derivadas de cada componente do sistema e os parâmetros que os relacionam. A Figura 2.4 apresenta a relação entre os sistemas coordenadas associados ao GNSS, unidade inercial (INS), sensor LASER e o ponto no terreno. Nessa ilustração considera-se, para efeito de simplificação, que o centro de fase da antena do receptor GNSS coincide com a origem do sistema de coordenadas do INS. Essa simplificação é possível desde de que o vetor ligando a origem do sistema de coordenadas do INS e o sistema de coordenadas do receptor GNNS seja conhecido ou determinado a priori com alta precisão. Com isso, o SVLA passa a envolver quatro sistemas de coordenada, os quais são (EL – SHEIMY et al., 2005): 1) Sistema de coordenadas terrestre; 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 15 2) Sistema de coordenadas GNSS/INS: origem no centro do sistema de coordenadas do INS; 3) Sistema de coordenadas da unidade LASER: origem no ponto de disparo do LASER. O eixo-x pode ser definido como coincidente com a direção do voo enquanto que o eixo-z aponta para o zênite; 4) Sistema de coordenadas do raio LASER: origem no ponto de disparo do LASER. O eixo-z coincide com a direção do raio LASER. Figura 2.4 - Componentes de um sistema de varredura a LASER aerotransportado e suas relações geométricas. Adaptado de Habib et al. (2008). A partir da Figura 2.4 observa-se que a posição de um ponto genérico i (𝑿𝑖𝑇⃗⃗⃗⃗ ⃗), pode ser obtida a partir da somatória de três vetores (𝑿𝒐⃗⃗ ⃗⃗ , 𝑷𝑮⃗⃗⃗⃗ ⃗ e �⃗⃗� ) após aplicar as rotações apropriadas: 𝑹𝜿,𝝋,𝝎, 𝑹∆𝜿,∆𝝋,∆𝝎 e 𝑹𝜶,𝜷 (HABIB et al., 2008). 𝑿𝒊𝑇⃗⃗⃗⃗ ⃗ = 𝑿𝒐⃗⃗ ⃗⃗ (𝑡) + 𝑹𝜿,𝝋,𝝎(𝑡) . 𝑷𝑮⃗⃗⃗⃗ ⃗ + 𝑹𝜿,𝝋,𝝎(𝑡) . 𝑹∆𝜿,∆𝝋,∆𝝎 . 𝑹𝜶,𝜷(𝑡) [ 0 0 −𝜌𝑖 ] (2.4) onde: 𝑿𝒊𝑇⃗⃗⃗⃗ ⃗ – Coordenadas de um ponto genérico i no sistema de coordenadas terrestre; 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 16 𝑿𝒐⃗⃗ ⃗⃗ – Coordenadas da origem do sistema de coordenadas do GNSS/INS, no sistema de coordenadas terrestre; 𝑹𝜿,𝝋,𝝎 – Matriz de rotação entre o sistema de coordenadas GNSS/INS e o sistema de coordenadas terrestre; 𝑹∆𝜿,∆𝝋,∆𝝎 – Matriz de rotação entre o sistema de coordenadas GNSS/INS e o sistema de coordenadas da unidade LASER. Os ângulos de rotação que compõem essa matriz são conhecidos como ângulos de desalinhamento (do inglês boresight angles); 𝑷𝑮⃗⃗⃗⃗ ⃗ – Vetor translação entre a origem do sistema de coordenadas GNSS/INS e a origem do sistema de coordenadas da unidade LASER. Esse vetor translação também é conhecido como lever arm offset; 𝑹𝜶,𝜷 – Matriz de rotação entre o sistema de coordenadas da unidade LASER e o sistema de coordenadas do raio LASER. Os ângulos que compõem essa matriz são conhecidos como ângulos de varredura; ρi – Medida de distância entre a origem do sistema de coordenadas da unidade LASER e o ponto objeto i no terreno; t – Instante de recepção do pulso LASER. A posição (Xo(t), Yo(t), Zo(t)) e a orientação (κ(t), φ(t), ω(t)) da plataforma durante o deslocamento são determinadas pela integração do GNSS e o INS. Segundo El-Sheimy e Niu (2007) as informações do GNSS (posicionamento, velocidade e tempo) permanecem estáveis por longos períodos, e quando o sinal de recepção é interrompido e/ou a geometria dos satélites não está dentro de limites aceitáveis, o sistema de navegação inercial pode prover informações para navegação. Em função do problema de deriva, inerente aos sistemas inerciais, as posições e velocidades obtidas pelo sistema GNSS podem ser usadas como medidas externas e utilizadas para atualizar a informação gerada pelo INS, melhorando sua estabilidade e precisão ao longo do tempo. Por esta razão os sistemas GNSS e INS são considerados complementares. As coordenadas obtidas por observações GNSS normalmente não coincidem com os instantes de emissão e recepção dos pulsos LASER, assim como as observações do sistema inercial. Por esse motivo é fundamental que seja estabelecido o sincronismo entre estes sistemas, para que todos os pontos amostrados possuam coordenadas e valores de atitudes relativos à sua real posição no instante de coleta. No trabalho desenvolvido por Reis (2009) são apresentados os fatores essenciais à realização deste sincronismo. 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 17 As quantidades envolvidas na equação do ponto LiDAR (Equação 2.4) são todas obtidas durante o processo de aquisição, exceto as componentes de translação (𝑷𝑮⃗⃗⃗⃗ ⃗) e desalinhamento angular (∆𝜅, ∆𝜑, ∆𝜔) (conhecidas como parâmetros de montagem), as quais normalmente são determinadas a partir do processo de calibração do sistema (HABIB et al., 2008). 2.1.3 Estrutura do formato LAS (LIDAR Exchange Format) O SVLA possibilita amostrar um conjunto de pontos tridimensionais sobre a área de interesse, o qual pode ser expresso em diversos formatos. Com o intuito de padronizar a estrutura desses dados e permitir o intercâmbio de dados obtidos por sistemas desta natureza a ASPRS (American Society for Photogrammetry and Remote Sensing) criou um formato denominado ASPRS LAS. Na Figura 2.5 é mostrada a estrutura, conforme Samberg (2007), para a versão 1.1. Figura 2.5 - Elementos do formato “.LAS”, versão 1.1. Adaptado de Samberg (2007). Como visto na Figura 2.5, o formato “.LAS” apresenta informações de metadados (informação sobre o sistema, número total de pontos e valores extremos - máximo e mínimo), informações relacionadas ao armazenamento e informações sobre os pontos (coordenadas tridimensionais, intensidade do retorno, tonalidades (caso haja sensor CCD – Charge Coupled Device) e classificação). O campo classificação representa a classe na qual o ponto foi classificado, como por exemplo, edificação, terreno, vegetação baixa etc. Para cada classe Cabeçalho Público Quantidade de Armazenamento Dados - Pontos Informação sobre o sistema Número total de pontos Valores máximos e mínimos Definição do desenvolvedor X. Y. Z. intensidade R. G. B Classificação 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 18 existe um número correspondente, por exemplo, se um ponto não foi classificado este é associado ao número zero. Para maiores detalhes sugere-se consultar o arquivo com as especificações do formato “.LAS”, disponibilizado na página oficial da ASPRS (ASPRS, 2013). 2.2 Comparação entre os dados LiDAR e a Fotogrametria convencional No contexto da extração de edificações, os dados LiDAR possuem algumas vantagens e desvantagens quando comparados à Fotogrametria convencional, que se baseia no uso de imagens aéreas. A Tabela 2.1 sumariza as principais diferenças entre os dois conjuntos de dados. Tabela 2.1 - Comparação entre dados LiDAR e a fotogrametria convencional no contexto de extração de edificações. Elementos de Comparação SVLA Fotogrametria convencional Linhas de descontinuidade Baixa densidade posicional Alta densidade posicional Regiões Homogêneas Densa informação posicional Problema de correspondência Precisão Posicional Melhor em altimetria Melhor em planimetria Informação Semântica Baixa Alta Adaptado de Dal Poz et al. (2009a) e Fernandes (2016) As linhas de descontinuidade são melhores representadas em imagens aéreas, uma vez que a imagem corresponde a uma representação contínua da superfície terrestre. Já os dados LiDAR correspondem a um representação amostral, não sendo possível garantir que os pontos obtidos coincidam com as bordas dos objetos. No caso dos dados LiDAR, o nível de detalhamento das bordas está diretamente relacionado a densidade de pontos. Em contrapartida, os planos de telhados são melhores determinados nos dados LiDAR. No SVLA as coordenadas tridimensionais são obtidas diretamente por meio de um sistema de posicionamento e orientação, englobando GNSS e INS. Ao passo que na Fotogrametria convencional as coordenadas são obtidas por meio de um conjunto de processos, realizados após a aquisição das imagens. As duas principais operações envolvidas são: aerotriangulação e correspondência de imagens. Como os telhados usualmente apresentam um padrão repetitivo ou homogêneo, o processo de correspondência é afetado negativamente, gerando falsas correspondências. Desta forma, os pontos amostrados sobre tais regiões podem 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 19 apresentar uma menor precisão em altimetria, como pode ser observado na Figura 2.6. Em Gehrke et al. (2010) é apresentada uma discussão mais detalhada sobre a comparação do modelo digital de superfície gerado a partir de dados LiDAR e imagens aéreas. Figura 2.6 - Nuvem de pontos fotogramétrica (a) e LiDAR (b). Perfil gerado sobre a nuvem fotogramétrica (c) e LiDAR (d). Com relação a informação semântica, em geral, a qualidade desse elemento é bem diferente nos dois tipos de dados. O sistema LiDAR considerado nesse trabalho registra apenas informação de intensidade de retorno do pulso LASER. Em contrapartida, as câmaras usualmente permitem o registro da energia refletida em diferentes bandas do espectro, possibilitando a geração da imagem colorida (Figura 2.7a). É importante salientar que mais recentemente surgiu o LiDAR multiespectral, permitindo o aumento da qualidade da informação semântica que pode ser extraída a partir da nuvem de pontos LiDAR (MORSY et al., 2017). Figura 2.7 - Imagem aérea composição das bandas RGB (red, green, blue) (a), e imagem intensidade obtida pelo LASER (b). 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 20 2.3 Fatores que influenciam a extração de edificações a partir de dados LiDAR O processo de extração de edificações a partir de dados LiDAR pode ser afetado por diversos fatores inerentes à geometria de aquisição e a complexidade da cena. Na sequência é apresentada uma breve descrição de alguns desses fatores: densidade da nuvem de pontos, variação da densidade ao longo da nuvem, oclusão causada por construções, oclusão parcial ou total causada por vegetação, e área com alta concentração de edificações. Um fator que influência diretamente o processo de extração de edificações, em especial a extração de contornos, é a densidade de pontos. Como mencionado na Subseção 2.2.1, a densidade depende de diferentes variáveis. Na Figura 2.8 é apresentado um conjunto de edificações selecionado a partir de nuvem de pontos com diferentes alturas de voo. Nota-se que as linhas de descontinuidade das edificações são melhores definidas à medida que a densidade de pontos aumenta. No caso da extração de planos de telhados, a densidade de pontos tem pouca influência sobre o resultado final. Figura 2.8 - Pontos LiDAR amostrados sobre telhados de edificações, coloridos de acordo com a altura. Recorte realizado a partir de diferentes nuvens de pontos: 2,9 pontos/m2 (a), 5,8 pontos/m2 (b), 12,5 pontos/m2 (c). Apesar do voo ser bem controlado em termos de trajetória e velocidade, os dados LiDAR podem apresentar variação de densidade ao longo da nuvem de pontos. Com isso, métodos de extração de contornos que dependem diretamente da densidade de pontos são afetados, como é o caso do algoritmo alpha-shape e do fecho convexo modificado. No trabalho de Lari e Habib (2012) é discutido a influência da densidade em diferentes etapas do processamento dos dados LiDAR, além disso, são apresentadas abordagens para o cálculo da densidade local. Na Figura 2.9 são apresentados dois recortes realizados sobre a mesma nuvem de pontos, onde é perceptível a variação de densidade ao longo da nuvem. Na Figura 2.9a nota-se uma maior densidade de pontos quando comparado com o recorte mostrado da Figura 2.9b. 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 21 Figura 2.9 - Recortes obtidos a partir da mesma nuvem de pontos LiDAR. Pontos coloridos de acordo com a densidade de pontos. Assim como na fotogrametria convencional, a oclusão causada por construções antrópicas e vegetação é um problema recorrente (Figura 2.10). Os objetos altos e localizados fora da linha de voo podem impedir que pontos sejam amostrados sobre objetos vizinhos mais baixos, caracterizando a perda de informação (Figuras 2.10a e 2.10b). Para minimizar tais efeitos, pode-se sobrevoar com uma maior altura de voo. No entanto, a densidade de pontos será reduzida, se forem mantidos os mesmos demais parâmetros do voo. Outra alternativa, refere-se ao aumento da área de sobreposição das faixas LiDAR, possibilitando observar um dado objeto de diferentes pontos vistas. Figura 2.10 - Exemplos de oclusões causadas por construções altas. Além disso, a oclusão pode ser causada por vegetação, como mostrado nas Figuras 2.11a e 2.11c. Entretanto, devido a característica do pulso LASER, alguns pontos podem ainda ser amostrados sobre o telhado da edificação (Figuras 2.11b e 2.11d). Nas 2 Sistema de Varredura a LASER Aerotransportados e as Características dos Dados LiDAR SANTOS, R. C 22 regiões de oclusão ocorre uma queda drástica na densidade de pontos LiDAR e perda de informação, afetando a reconstrução do contorno em tais regiões. Figura 2.11 - Vegetação localizadas sobre parte da edificação (a, c). Pontos amostrados sobre os telhados (b, d). Em termos de extração automática de edificações, diferentes técnicas de classificação e segmentação podem ser exploradas para obter o agrupamento relacionado a cada edificação. No entanto, em um ambiente urbano complexo, onde existem edificações localizadas próximas umas das outras e vegetação próximas das edificações (Figura 2.12a), a caracterização de cada edificação e a separação das classes por operações automáticas torna- se uma tarefa complexa. Na Figura 2.12b é apresentado um exemplo de resultado derivado do processo de segmentação, sendo possível observar o problema decorrente da proximidade dos objetos presentes na cena. Nesse caso, pontos amostrados sobre diferentes objetos foram erroneamente considerados como sendo de um mesmo grupo. Figura 2. 12 - Imagem aérea de uma cena com alta complexidade (a). Exemplo do processo de segmentação visto de diferentes pontos de vista (b, c). 3 Detecção dos Pontos LiDAR Amostrados sobre Telhados de Edificações e Avaliação da Qualidade dos Contornos SANTOS, R. C 23 CAPÍTULO 3 Detecção dos Pontos LiDAR Amostrados sobre Telhados de Edificações e Avaliação da Qualidade dos Contornos Nesta tese, o método proposto é divido em três principais fases: pré-processamento, extração e regularização dos contornos de telhados. As contribuições desta tese estão concentradas nas duas últimas fases e nesse capítulo é apresentada a metodologia relacionada ao pré-processamento, o qual consiste na seleção dos pontos amostrados sobre os telhados de edificações. O processo de detecção dos pontos de edificação é realizado a partir de métodos já consagrados e envolve as seguintes etapas: detecção e eliminação dos outliers, filtragem, segmentação e identificação dos agrupamentos relacionados à edificação. Além disso, é realizada uma breve descrição dos parâmetros de qualidade utilizados na avaliação quantitativa dos contornos de telhados obtidos pelo método proposto, sendo estes parâmetros categorizados em duas classes: baseados em área e em medidas lineares. 3.1 Detecção de outliers na nuvem de pontos LiDAR O conjunto de pontos derivado do sistema de varredura a LASER aerotransportado pode conter pontos espúrios também conhecidas como outliers. Esses pontos podem ser classificados em duas classes: positivos e negativos (Figura 3.1). Os outliers positivos são causados por objetos localizados próximo a plataforma aérea: pássaros, drones e pipas. Além dessas causas, Leslar et al. (2010) mencionam que partículas suspensas na atmosfera (neve e 3 Detecção dos Pontos LiDAR Amostrados sobre Telhados de Edificações e Avaliação da Qualidade dos Contornos SANTOS, R. C 24 poeira) são também possíveis fontes deste problema. Os outliers negativos podem ser atribuídos ao efeito de multicaminho da trajetória do pulso LiDAR, similar ao que ocorre no posicionamento por satélites, isto é, o pulso percorre uma trajetória mais longa que a real, resultando em pontos localizados abaixo da superfície do terreno. Figura 3.1 - Nuvem de pontos contento outliers positivos e negativos. De acordo com Sithole e Vosselman (2004) os pontos espúrios, em especial os negativos, podem causar problemas durante o processo de filtragem, uma vez que alguns métodos assumem que os pontos mais baixos são pontos de terreno. Para Ben-Gal (2005) a presença de pontos espúrios no conjunto de dados pode levar a modelagem incorreta, ou a estimação tendenciosa, e consequentemente, a resultados incorretos. Desta forma, a detecção e eliminação dos pontos espúrios é essencial. O processo de detecção dos pontos espúrios pode ser realizado de diferentes formas: ajuste de uma superfície paramétrica (RASHIDI e BRILAKIS, 2016), filtro morfológico de ruídos (MONGUS e ŽALIK, 2012), filtro baseado na frequência espacial (implementado no software LAStools), e filtro de remoção de ruídos baseado em análise estatística (implementado no software CloudCompare). Nesse trabalho, o método proposto por Carrilho et al. (2018), denominado de filtro baseado no histograma da célula, foi usado para detecção e eliminação dos outliers. No método proposto por Carrilho et al. (2018), o conjunto de dados LiDAR é divido em uma grade de células quadradas no espaço bidimensional, similar à estrutura de dados descrita em Mongus e Žalik (2012). Este tipo de estrutura permite realizar manipulações locais, e consequentemente otimizar as operações de busca. Para cada célula da grade de dimensões (Dg x Dg) é gerado um histograma de frequência das alturas a partir de um 3 Detecção dos Pontos LiDAR Amostrados sobre Telhados de Edificações e Avaliação da Qualidade dos Contornos SANTOS, R. C 25 parâmetro de amplitude de altura (AH), o qual é usado para dividir as alturas em intervalos. O método varre o histograma procurando o primeiro e último intervalo cuja frequência está acima de um limiar pré-estabelecido em termos de número de pontos (Lf). Os valores de mínimo e máximo determinados são utilizados para definir o intervalo de aceitação. Nesse caso, todos os pontos com altura fora do intervalo são definidos como pontos espúrios e eliminados. Figura 3.2 - Grade de células quadradas (a) e representação do histograma de frequência das alturas (c) para a célula selecionada (b). 3.2 Filtragem dos dados LiDAR As técnicas de filtragem de nuvens de pontos LiDAR obtidas por SVLA tem como objetivo identificar os pontos de terreno e não terreno. Os pontos de não terreno englobam os pontos amostrados sobre objetos altos: vegetação, edificação, veículos, muros, dentre outros. De acordo com Sithole e Vosselman (2004), o processo de filtragem é desenvolvido a partir da combinação de diferentes elementos, tais como: estrutura de dados, critérios de definição da vizinhança, medida de descontinuidade, princípio de filtragem, mecanismo de controle (iterativo e não iterativo), natureza da filtragem, uso do primeiro pulso e dados de refletância. Em Sithole e Vosselman (2004) e em Fernandes (2016) são apresentadas descrições detalhadas desses elementos. 3 Detecção dos Pontos LiDAR Amostrados sobre Telhados de Edificações e Avaliação da Qualidade dos Contornos SANTOS, R. C 26 Nesse trabalho, adotou-se o método de filtragem proposto por Axelsson (2000). Esse método opera de forma iterativa e usa como dados de entrada o conjunto de pontos irregularmente espaçados. Em linhas gerais, o processo toma um pequeno conjunto de pontos de terreno (pontos sementes) e os organiza segundo uma estrutura triangular, adensando progressivamente o conjunto inicial de pontos. Para obter os pontos sementes e realizar a construção do TIN, de maneira progressiva, inicialmente gera-se uma grade sobre a nuvem de pontos disponível (Figura 3.3). A grade é definida a partir das dimensões do retângulo envolvente que engloba a área de interesse e de um tamanho de célula predefinido. Para cada célula, o ponto de menor altitude é selecionado e marcado como ponto semente. Os vértices do retângulo envolvente também são marcados como pontos de terreno, sendo atribuído a eles a altura do ponto semente mais próximo. Nesse passo inicial os pontos sementes são utilizados para a geração do TIN, o qual representa uma aproximação inicial do terreno. Figura 3.3 - Pontos sementes e geração da estrutura de triângulos a partir dos pontos sementes. Adaptado de Zhang e Lin (2013). A cada iteração, os pontos da nuvem são avaliados individualmente com base na triangulação gerada na iteração anterior e de dois critérios pré-estabelecidos. O primeiro, consiste em verificar se a distância entre o ponto de interesse e o plano da face do triângulo (dp_tri) (Figura 3.4) é menor que um limar de distância. O segundo, está relacionado com a verificação dos ângulos formados pelos segmentos que ligam o ponto de interesse aos nós do 3 Detecção dos Pontos LiDAR Amostrados sobre Telhados de Edificações e Avaliação da Qualidade dos Contornos SANTOS, R. C 27 triângulo, representados por (α, β, γ) na Figura 3.4, devendo estes ângulos serem menores que um dado limiar angular. Figura 3.4 - Princípio do método de filtragem. Adaptado de Axelsson (2000). O ponto em análise é marcado como de terreno, se e somente se, os dois critérios forem atendidos. A partir dos pontos classificados como terreno gera-se um novo TIN, sendo os pontos de não terreno re-submetidos a um novo ciclo de filtragem. O processo iterativo é finalizado quando nenhum ponto satisfazer os critérios, ou seja, quando nenhum ponto for adicionado ao TIN. 3.3 Segmentação dos pontos de não terreno Segundo Kwak e Habib (2014), as técnicas de segmentação podem ser categorizadas em duas abordagens: crescimento de região no domínio espacial e crescimento de regiões no domínio dos parâmetros (atributos). Na primeira, pontos sementes são necessários, sendo adicionado a eles pontos candidatos que satisfazem um critério de proximidade pré- estabelecido. Na segunda abordagem, o processo é implementado no espaço dos parâmetros e consiste em agrupar os pontos que possuem atributos similares. Nesse último caso, o resultado final é diretamente dependente dos parâmetros estimados. Usualmente, os atributos são calculados considerando uma vizinhança no entorno do ponto de interesse, por exemplo, determinação do vetor normal que melhor se ajusta ao plano formado por um dado ponto e o seus pontos vizinhos. Nesse trabalho é utilizada a abordagem de crescimento de regiões baseada no domínio espacial. Para tanto, considerou-se uma metodologia similar a desenvolvida por Sampath e Shan (2007), sendo acrescentado um limiar de altura (LDh). O processo é executado no espaço tridimensional, e utiliza os pontos de não terreno como dados de entrada. Na separação dos agrupamentos, dois limiares são adotados: distância planimétrica (LDxy) e altimétrica (LDh). O 3 Detecção dos Pontos LiDAR Amostrados sobre Telhados de Edificações e Avaliação da Qualidade dos Contornos SANTOS, R. C 28 conjunto de pontos correspondente a cada agrupamento é armazenado no vetor B, o qual é inicialmente nulo. Na sequência são apresentados os passos envolvidos no crescimento de regiões. Passo 1 – Os pontos de entrada são armazenados no vetor 𝑺 = [𝑃0 𝑃1……𝑃𝑛]. Passo 2 – O primeiro ponto de 𝑺 (𝑃0) é adotado como ponto semente. Passo 3 – Considerando uma esfera de raio R centrada sobre o ponto de interesse, armazenar em 𝑮 = [𝑟𝑃1 𝑟𝑃2…… 𝑟𝑃𝑚] todos os pontos que estão no interior na esfera cujo raio é dado pela seguinte equação: 𝑅 = √𝐿𝐷𝑥𝑦 2 + 𝐿𝐷ℎ 2 (3.1) Passo 4 – A verificação do critério de proximidade é realizada a partir dos pontos localizados no interior da esfera. Os pontos que satisfazem os dois critérios (Equações 3.2 e 3.3) são armazenados no vetor 𝑨 = [𝑐𝑃1 𝑐𝑃2…… 𝑐𝑃𝑘]. √(𝑥𝑖 − 𝑥𝑗) 2 + (𝑦𝑖 − 𝑦𝑗) 2 < 𝐿𝐷𝑥𝑦 (3.2) |𝑧𝑖 − 𝑧𝑗| < 𝐿𝐷ℎ (3.3) onde 𝑥𝑖 , 𝑦𝑖 e 𝑧𝑖 corresponde as coordenadas do i-éssimo ponto localizado no interior da esfera; 𝑥𝑐, 𝑦𝑐 e 𝑧𝑐 são as coordenadas do centro da esfera. Passo 5 – Mover a esfera para cP1. Passo 6 – Coletar os pontos que satisfazem o critério de proximidade e armazena-los em um vetor temporário, 𝑻 = [𝑡𝑃1 𝑡𝑃2……𝑡𝑃𝑖]. Passo 7 – Mover a esfera para o próximo ponto. Armazenar os pontos recém identificados no vetor 𝑻, e verificar se dois pontos pertencentes ao vetor 𝑻 não são idênticos. Passo 8 – Continuar o processo até que a esfera seja “posicionada” sobre todos os pontos do conjunto 𝑨. Passo 9 – Unir os pontos dos vetores 𝑨 e 𝑻, e armazená-los em 𝑩 (𝑩 = {𝑩 ∪ 𝑨 ∪ 𝑻}). Passo 10 – Substituir os pontos em 𝑨 com os pontos de 𝑻, de forma que o novo conjunto 𝑨 seja equivalente a { 𝑻 ⊄ 𝑨}. Retornar ao Passo 5. 3 Detecção dos Pontos LiDAR Amostrados sobre Telhados de Edificações e Avaliação da Qualidade dos Contornos SANTOS, R. C 29 Passo 11 – Quando nenhum ponto for adicionado ao conjunto 𝑩, o vetor 𝑺 deve ser atualizado. O novo vetor 𝑺 é obtido por 𝑺 = { 𝑺 – 𝑩 }. O conjunto 𝑩 corresponde aos pontos pertencentes ao mesmo agrupamento. Retornar para o Passo 2. Passo 12 – Parar o processo quando o vetor 𝑺 estiver vazio. No processo de crescimento de regiões são gerados pequenos agrupamentos usualmente relacionados a veículos, paredes e árvores. Como o foco do trabalho é a extração de contornos de telhados, os pequenos agrupamentos podem ser eliminados. Para tanto, um critério baseado na quantidade de pontos do agrupamento foi considerado. Nesse caso, segmentos contendo menos que TNp são excluídos. O limar TNp pode ser determinado considerando a Equação 3.4, a qual envolve as seguintes informações: densidade média da nuvem de pontos (𝑑𝑎𝑣𝑔) e menor área da edificação a ser representada (𝐴𝑟𝑚𝑖𝑛). 𝑇𝑁𝑝 = 𝐴𝑟𝑚𝑖𝑛 ∗ 𝑑𝑎𝑣𝑔 (3.4) Na Figura 3.5 é mostrado um exemplo da aplicação do processo de crescimento de regiões antes e após a eliminação dos pequenos agrupamentos. O resultado final (Figura 3.5b) engloba agrupamentos maiores, usualmente relacionados aos telhados de edificação e vegetação, como destacado. Considerando que o interesse são os pontos amostrados sobre edificação, torna-se necessário uma etapa de refinamento com o intuito de identificar e eliminar os agrupamentos de não edificação. Figura 3.5 - Resultado do processo de crescimento de regiões antes (a) e após (b) eliminação dos pequenos agrupamentos. 3 Detecção dos Pontos LiDAR Amostrados sobre Telhados de Edificações e Avaliação da Qualidade dos Contornos SANTOS, R. C 30 3.4 Detecção dos pontos LiDAR amostrados sobre edificações O crescimento de regiões é usualmente realizado sobre os pontos de não terreno: edificação, vegetação, dentre outros objetos altos. Diante da variedade de objetos, o resultado do processo de segmentação é composto de agrupamentos de edificação e não edificação. Em geral, os agrupamentos de não edificação correspondem a vegetação, como mostrado na Figura 3.5b. Como o interesse é a extração de edificações, a tarefa de identificar os agrupamentos de edificação é essencial. Nesse trabalho, a identificação dos agrupamentos de edificação é realizada a partir do método proposto por Santos et al. (2019b). Em linhas gerais, o método utiliza o conceito de entropia para determinar o atributo relacionado a cada agrupamento, e o algoritmo k-médias para realizar a separação das classes. A grande vantagem dessa abordagem está relacionada a identificação automática dos agrupamentos, dispensando a necessidade de uma etapa de treinamento. Na linguagem da termodinâmica, entropia é uma medida de desordem de um sistema, sendo baixa entropia associada a pouca desordem e alta a muita desordem (ATKINS e JONES, 2006). No contexto da identificação de edificações, espera-se que os agrupamentos de edificação apresentem baixa entropia, e os agrupamentos que não são edificações uma alta entropia, decorrente dos múltiplos retornos em regiões de vegetação. Em Santos et al. (2019b), para cada agrupamento é estimado um valor de entropia médio, o qual é obtido a partir da média aritmética do valor de entropia calculado para cada ponto. O valor de entropia médio de um dado agrupamento j é estimado pela Equação 3.5. Já o valor de entropia estimado para um dado ponto i do agrupamento j é calculado a partir da Equação 3.6 (SHANNON, 1948, e WEINMANN et al., 2015). 𝐸𝑗 = 𝑛−1∑ 𝐸𝑖 𝑗𝑛 𝑖=1 (3.5) onde: 𝐸𝑖 𝑗 = −𝐿𝜆 ln(𝐿𝜆) − 𝑃𝜆 ln(𝑃𝜆) − 𝑆𝜆 ln(𝑆𝜆) (3.6) sendo: 3 Detecção dos Pontos LiDAR Amostrados sobre Telhados de Edificações e Avaliação da Qualidade dos Contornos SANTOS, R. C 31 𝐿𝜆 = 𝜆1−𝜆2 𝜆1 (3.7) 𝑃𝜆 = 𝜆2−𝜆3 𝜆1 (3.8) 𝑆𝜆 = 𝜆3 𝜆1 (3.9) valores correspondentes às medidas de linearidade (Lλ), planaridade (Pλ) e esfericidade (Sλ). Essas métricas são estimadas a partir dos autovalores λ1, λ2 e λ3 considerando a seguinte ordenação λ1 ≥ λ2 ≥ λ3, como pode ser visto em Gross e Thoennessen (2006), Weinmann et al. (2015), e Weinmann et al. (2017). Os autovalores são determinados a partir da matriz de variâncias e covariâncias (MVC) das coordenadas tridimensionais, a qual é obtida considerando o ponto de interesse e seus pontos vizinhos. No trabalho de Santos et al. (2019b) a vizinhança é definida pelos N pontos mais próximos, sendo o valor de N obtido a partir da densidade média da nuvem de pontos (davg) e da área do menor elemento a ser representado (Armin), similar à formulação usada para estimar TNp (Equação 3.4), isto é, N = Armin*davg. Usando os valores médios de entropia como dados de entrada, a próxima etapa consiste em separar os agrupamentos em duas classes: edificações e não edificações, usando o algoritmo k-médias. Esse algoritmo trata-se de uma classificação não supervisionada, sendo os centroides definidos de forma iterativa, como pode ser visto em Santos e Galo (2018). No processo de separação, a distância Euclidiana no espaço unidimensional é considerada como medida de similaridade. Para mais detalhes do algoritmo k-médias sugere-se Johnson e Wichern (2007). Na Figura 3.6a são apresentados os agrupamentos coloridos, de acordo com o valor de entropia médio (Equação 3.5), enquanto que a Figura 3.6b mostra a classificação dos agrupamentos em duas classes por meio do algoritmo k-médias. 3 Detecção dos Pontos LiDAR Amostrados sobre Telhados de Edificações e Avaliação da Qualidade dos Contornos SANTOS, R. C 32 Figura 3.6 - Agrupamentos coloridos de acordo com o valor de entropia médio (a), e resultado da separação em duas classes: edificação (vermelho), e não edificação (verde). 3.5 Avaliação da qualidade O processo de avalição tem o objetivo de verificar a qualidade dos resultados gerados por um método/abordagem. Usualmente, essa avaliação é realizada comparando os resultados com dados de referência. A maneira mais simples de avaliação, refere-se a análise qualitativa. Esse tipo de avaliação é realizado por meio da análise visual e de forma intuitiva, visando observar a coerência dos resultados. Outra alternativa é a análise quantitativa, a qual utiliza parâmetros/métricas de qualidade. Na literatura é possível encontrar vários parâmetros de qualidade. No contexto da extração e regularização de contornos, as métricas podem ser classificadas em dois grupos. O primeiro grupo engloba as métricas calculadas a partir do valor de área: completeza, nível de acerto e Fscore. Nesse caso, as métricas são estimadas no espaço bidimensional. O segundo grupo contém as métricas baseadas em medidas lineares: distância de Hausdorff, métrica