FILTRAGEM DE NUVEM DE PONTOS POR NAIVE BAYES PARA OBTENÇÃO DE UM MODELO DIGITAL DO TERRENO. Filtering Cloud of Points by Naïve Bayes for Obtaining a Digital Terrain Model. Luis Fernando Chimelo Ruiz1 Laurindo Antonio Guasselli 1 Alexandre ten Caten 2 Fernando Vitalis 2 1 Universidade Federal do Rio Grande do Sul Programa de Pós-Graduação em Sensoriamento Remoto [email protected], [email protected] 2 Universidade Federal de Santa Catarina Campus Curitibanos, Departamento de Geomática [email protected], [email protected] RESUMO Modelo Digital do Terreno (MDT) é utilizado como informação base para diversos estudos, como mapeamento digital de solos, gestão de desastres e projetos de engenharia. Atualmente, há diversas tecnologias para obtenção de um MDT, variando entre essas tecnologias a escala, tempo e custo de aquisição desses dados. Algumas tecnologias são dependentes da liberação de voo e das condições climáticas, essa dependência dificulta a repetividade de voos. Uma alternativa a isso seriam os Veículos Aéreos Não Tripulado (VANT), pois possibilitam a obtenção de imagens em altas resoluções temporais e espaciais. Essas imagens aliadas as técnicas de computação visual e fotogrametria digital, possibilitam a obtenção de mosaicos de imagens ortorretificados e nuvem de pontos. Mas esses pontos não representam o terreno e sim a superfície imageada. Para gerar o MDT por meio dessa nuvem de pontos é necessário aplicar técnicas de filtragem e de interpolação, entre as técnicas de filtragem as estratégias mais utilizadas consideram apenas parâmetros geométricos. Neste sentido, este trabalho teve como objetivo aplicar um método de filtragem de nuvem de pontos por Naive Bayes e avaliar a qualidade do MDT gerado pelo interlado Thin Plate Spline (TPS). A filtragem por Naive Bayes não conseguiu remover todos os pontos indesejáveis, com isso foi necessário aplicar conjuntamente, outro método de filtragem e assim foi possível remover todos os pontos que não representam o terreno. Com essa nuvem de pontos filtrada foi gerado o MDT pelo interpolador TPS, o MDT obtido foi coerente com o terreno da área de estudo, mas o valor RMSE, calculado a partir das amostras de campo, apresentou valores altos. Palavras chaves: (Modelo Digital do Terreno, Naive Bayes, Veículo Aéreo Não Tripuado) ABSTRACT Digital Terrain Model (DTM) is used as basic information for various studies, such as digital soil mapping, disaster management and engineering projects. Currently, there are several technologies for obtaining an MDT, these technologies ranging from the scale, time and cost of acquisition of the data. Some technologies are dependent on the release flight and of weather conditions, this dependence hinders the flights repeatability. An alternative to this would be the Unmanned Aerial Vehicles (UAV), because they allow get imaging high resolutions spatial and temporal . These images combined with the techniques of computer vision and digital photogrammetry, enable obtaining orthorectified mosaics of images and point clouds. These points do not represent the terrain but the imaged surface. Para gerar o MDT através dessa nuvem de pontos é necessário aplicar técnicas de filtragem e interpolação, entre as técnicas de filtragem estratégias utilizadas frequentemente consideram apenas os parâmetros geométricos. Assim, este estudo teve como objetivo aplicar um método de filtragem de ponto nuvem de Naive Bayes e avaliar a qualidade do MDT interpolados por fina Placa Spline (TPS). The Naive Bayes filtering failed to remove all the unwanted points, it was necessary to apply another method of filtering. With this cloud of filtered points was generated by interpolation the MDT, the result obtained was consistent with the terrain of the study area, but the RMSE value calculated from field samples showed high values. Keywords: (Digital Terrain Model , Naive Bayes, Unmanned Aerial Vehicles ) 1 1. INTRODUÇÃO Modelo Digital do Terreno (MDT) é utilizado como informação base para diversos estudos, como mapeamento digital de solos, gestão de desastres e projetos de engenharia. Um MDT é uma representação contínua da superfície do terreno, no qual não são consideradas as elevações de prédios, pontes, árvores, entre outros (PODOBNIKAR, 2009). Atualmente, há diversas tecnologias para obtenção de um MDT, variando entre essas tecnologias a escala, tempo e custo de aquisição desses dados. As tencnologias que necessitam de uma aeronave tripulada para a obtenção de dados são dependentes da liberação de voo e das condições climáticas, essa dependência dificulta a repetividade de voos. E também são levantamentos custosos devido aos equipamentos utilizados e pela necessidade de uma equipe a bordo da aeronave. Uma alternativa viável para alguns casos, são os aerolevantamentos utilizando Veículos Aéreos Não Tripulado (VANT), acoplados com uma câmera fotográfica de baixo custo. Com os VANT as imagens podem ser obtidas com tempo nublado, alta resolução espacial e temporal (EVERAERTS, 2008). Mas a realização dos voos dependem da velocidade do vento. Outro empecilho, é que no Brasil ainda não há uma lei que regulamente voos com fins comerciais. As imagens obtidas com câmeras de baixo custo, processadas por meio de técnicas de fotogrametria e de computação visual, possibilitam a obtenção de mosaico de imagens ortoretificados e de nuvem de pontos cotados. O mosaico de imagens pode apresentar acurácias centimétricas e como há redundância de imagens para o mesmo ponto da superfície é possível gerar uma densa nuvem de pontos (TURNER et al., 2012). Com essa nuvem de pontos são gerados os MDT, mas para que isso seja possível é necessário aplicar um método de filtragem e um de interpolação. O método de filtragem tem como objetivo selecionar apenas os pontos sobre o terreno e o de interpolação, gerar uma grade regular para a área de estudo (CONTE et al., 2013). As técnicas de filtragem mais utilizadas nessas nuvem de pontos, consideram apenas informações geométrica dos dados, como declividade, altimetria e largura máxima da feição a ser removida (BANDARA et al., 2011). Já o método de interpolação mais comum aplicado nesses dados é a Rede Irregular de Triângulos (TIN - Triangular Irregular Network), com função polinomial de primeira ordem. Mas a interpolação por TIN não é a mais indicada para modelagem do terreno (GUO et al., 2010). Neste sentido, este trabalho tem como objetivo propor e avaliar um método supervisionado de filtragem de nuvem pontos, utilizando o algoritmo Naive Bayes. E também avaliar a elaboração do MDT pelo interpolador Thin Plate Spline. 2. METODOLOGIA 2.2 Aerolevantamento Para o desenvolvimento deste trabalho foi efetuado um aerolevantamento a partir de um Veículo Aéreo Não Tripulado (VANT) hexacoptero, foi acoplado nessa plataforma uma câmera de baixo custo da marca Canon, que possui 12 Megapixel de resolução. O voo foi realizado sobre a Universidade Federal de Santa Catarina (UFSC), Campus Curitibanos, como medida de segurança o voo foi realizado em um final de semana, quando não houve expediente na universidade. Outras medidas de segurança tomadas foram em relação ao voo não ser totalmente autônomo, se houvesse necessidade o operador poderia interferir na direção da aeronave, sendo que a aeronave sempre esteve no seu campo de visada. Também foi utilizado um sistema de telemetria para medir as condições dos sensores da aeronave, assim quando acontecesse algum problema o segundo membro da equipe avisaria o operador. Os parâmetros do aerolevantamento foram estabelecidos conforme a Tabela 1, como resultado foram obtidas 91 imagens. TABELA 1 – PARÂMETROS DO AEROLEVANTAMENTO. Tempo de voo 12 minutos Velocidade 15 km/h Altura do voo 90 metros Sobreposição entre faixas 70% Sobreposição entre fotos 60% Antes do voo foi inserido na área de estudo quadros com a dimensão de 50 cm por 50 cm, nesses quadros foi feito um xadrez de duas cores, preto e branco. No total foram distribuídos dez quadros na área em distintas localizações, como esse material serviu de ponto de controle para a correção geométrica das imagens, foi coletado sobre eles coordenadas tridimensionais com um Sistema de Posicionamento Global (GPS - Global Positioning System ), no sistema de coordenadas Universal Transversa de Mercator (UTM), fuso 22 e no sistema de referência SIRGAS2000. 2 Foi utilizado o posicionamento relativo cinemático em tempo real (RTK – Real Time Kinematic), obtendo uma precisão de menos de 2 cm para cada ponto. 2.3 Processando as imagens As imagens foram processadas no programa PhotoScan da empresa AgiSoft, foi seguido o fluxo de trabalho conforme o proposto pelo programa, este fluxo está explicado abaixo: • Adicionar as fotos: Inserção das imagens com as respectivas coordenadas tridimensionais e seus ângulos de orientação. • Alinhar as fotos: Determinação dos pontos homólogos entre as imagens, com isso gera a correspondência entre elas e faz um refinamento da posição da câmera para cada imagem. Para determinação da acurácia das posições das imagens foi selecionado a opção alto e para o número total de pontos entre pares estereoscópicos foi inserido o valor 100000. Nessa etapa é gerada a nuvem de pontos. • Construir a malha triangular: Construção da geometria do terreno a partir da nuvem de pontos. Na opção tipo de superfície foi selecionado Sharp. • Inserir os pontos de controle: Ajuste do bloco fotogramétrico utilizando transformação afim, com pontos de controle coletado a campo. Foram marcados os dez pontos sobre as imagens que aparecem os quadros e inseridas as coordenadas tridimensionais. Foi configurado o sistema de coordenadas e o sistema de referência de acordo com o levantamento a campo e também foi selecionado a opção de otimizar alinhamento das imagens, com isso é considerado no ajuste parâmetros externos e internos das câmeras, como também, as distorções das lentes. • Exportar a ortofoto e a nuvem de pontos: Foi exportada a ortoimagem e a nuvem de pontos com extensões compatíveis ao programa QGIS 2.0. Para diminuir a área de estudo e assim o tempo de processamento dos testes, a ortoimagem foi recortada (Figura 1a) e a nuvem de pontos foi selecionada conforme um polígono gerado no centro da ortoimagem original. A área de estudo abrangeu um total de 3 hectares e o número total de pontos selecionados foram 132.478 (Figura 1b). Para avaliar as altitudes dos Modelos Digitais do Terreno (MDT) foram coletados a campo 76 pontos de apoio, utilizando um GPS RTK, a distribuição desses pontos na área do estudo está apresentada na Figura 1c. Fig. 1 – a) Ortoimagem, b) nuvem de pontos com valores das altitudes e c) amostras de altitudes coletada a campo. 2.4 Aplicando a filtragem na nuvem de pontos A nuvem de pontos foi submetida a uma classificação supervisionada utilizando o algoritmos Naive Bayes e a uma filtragem, por meio do cálculo da declividade dos seus vizinhos mais próximos. Esses processamentos foram 3 efetuados utilizando a linguagem de programação Python 2.7 e a biblioteca de desenvolvimento pyqgis, essa biblioteca possibilita utilizar os recursos de processamento disponíveis no programa QGIS. Na classificação supervisionada pelo algoritmo Naive Bayes foi selecionado duas classes de pontos, a primeira classe refere-se a pontos indesejáveis, por isso selecionou-se pontos sobre o prédio e árvores. A segunda classe são os pontos que estão sobre o terreno, no qual foram selecionados os pontos sobre as classes de cobertura da terra solo exposto, calçadas, campo e asfalto. No total foram selecionados 7001 pontos sobre o terreno e 6355 pontos indesejáveis, esses pontos foram divididos em dois arquivos, o primeiro contempla os dados de treinamento e o segundo os de validação do modelo, com a divisão de 70% e de 30% do total dos pontos, respectivamente. Como variáveis preditoras foram utilizadas as três bandas da imagem e os valores de altitudes. Para realizar a classificação desses pontos por Naive Bayes utilizou-se a biblioteca Scikit-Learn, essa biblioteca é um repositório de algoritmos para aprendizagem de máquina para linguagem Python. Para calcular a classe mais provável de uma nova instância por Naive Bayes, é necessário calcular a probabilidade dessa instância pertencer a cada classe, essa instância será rotulada (classificada) para a classe que apresentar maior probabilidade. A probabilidade da instância pertencer a uma classe pode ser computada pelo cálculo da Máxima probabilidade A Posteriori (MAP), como está representado na Equação 1. n ŷ =arg max i P ( y ) ∏ P (x i∣ y) Eq. (1) i=1 Em que, ŷ , é o valor da maior probabilidade da nova instância em relação as classes; P ( y) , é a n probabilidade a priori da classe; ∏ P( x i∣ y) , é o produto da probabilidade dos atributos preditores pertencerem a i=1 uma classe. Para o cálculo da P ( xi∣ y ) , está sendo considerado que os atributos preditores nos dados de treinamento seguem uma distribuição normal em relação as classes, assim a probabilidade de um atributo preditor pertencer a uma classe, pode ser calculado pela Equação 2. P ( xi∣ y )= 1 √ (2 π σ 2) exp− y ( xi −μ y ) 2 2 π σ2y Eq. (2) Sendo, μ , é o valor médio do atributo preditor em relação a classe e σ , é o desvio-padrão do atributo preditor em relação a classe. Esses valores são determinados nos dados de treinamento. Mais informações podem ser obtidas em Zhang ( 2004). Os pontos de validação também foram classificados gerando com isso uma matriz de confusão e a partir da matriz foi calculado a exatidão global e o índice kappa (CONGALTON, 1991). Após a aplicação da classificação dos pontos, os mesmos pontos foram submetidos a uma nova filtragem, essa filtragem foi necessário porque na classificação não foi removido totalmente os pontos sobre o prédio e árvores. Esse segundo filtro consiste em calcular a declividade de um ponto em relação aos seu vizinhos. A partir desses pontos vizinhos é calculado a média para os valores das declividades, o ponto só será selecionado se o valor médio da declividade for menor que a declividade pré-definida pelo usuário. Esses procedimentos foram executados utilizando a biblioteca de programação Pyqgis, por meio da função NearestNeighbor e pela biblioteca math da linguagem Python. 2.5 Gerando o MDT Com os pontos sobre terreno foi gerado o MDT por meio da técnica de interpolação curvatura mínima spline, mas também é denominada como Thin Plate Spline (TPS). Nesse interpolador os novos valores para a variável são calculados por meio de um polinômio (Equação 3), que tem como propósito gerar uma superfície que minimize a curvatura entre o novo valor com o valor de controle, gerando uma superfície suavizada. Essa suavização é utilizada no polinômio como um parâmetro, no qual pode ser modificada. Valores para esse parâmetro igual a zero, conservam os valores dos dados de entrada, assim o modelo gerado não será suavizado. Sabendo as coordenadas tridimensionais de alguns pontos de controle ( X i , Y i , Z i ) , com i = 1, 2, 3,...,n, a interpolação do atributo Z, conhecendo as coordenadas horizontais (X, Y), é dada pela Equação 3. n Z ( X , Y )=a0 +a1 X+a 2 Y +∑ F i r 2i ln (r 2i +ε) Eq. (3) i=1 Em que, Z ( X , Y ), é o valor do atributo a ser calculado e suas respectivas coordenadas horizontais, a0 , a1 , a 2 , F i , são as incógnitas da equação e são encontradas a partir de um sistema, gerado pela Eq. 3, mas utilizando 4 2 os valores das amostras (Z k , X k e Y k ) , ε , é o grau de variação da curvatura da superfície e r i , é a distância entre as coordenadas do ponto de controle com a coordenada onde será calculado o valor para o atributo, descrito na Equação 4. Para obter mais informações sobre esse método de interpolação consulte Barbosa et al. (2008). 2 2 2 Eq. (4). r i = ( X− X i ) +(Y −Y i ) Neste trabalho foram testados para esse parâmetro os valores 0,1, 0,01 e 1. Esses processamentos foram elaborados no programa SAGA-GIS 2.1. A avaliação do erro dos MDT foram definidas pelo calculo do Raiz quadrada do Erro Quadrático Médio (RMSE - Root Mean Square Error), conforme a Equação 3 (SANTOS et al., 2003), utilizando como verdade terreno os 76 pontos de apoio coletados com GPS RTK. RMSE= Em que, √ ∑ ( X obs,i− X modelo ,i )2 Eq. (5) n X obs,i = Valor observado a campo, X modelo,i = Valor obtido pelo modelo e n = número total de pontos. 3. RESULTADOS A georreferencia da ortoimagem apresentou uma acurácia de menos de um pixel, tanto na horizontal como na vertical, sendo que o tamanho do pixel da imagem foi de 10 cm. A ortoimagem produzida pelo PhotoScan apresentou algumas deformações nos cantos dos prédios. Outro problema encontrado é a diferença de brilho em alguns locais no mosaico de imagens, devido a algumas imagens receberem iluminação diferente das demais. Na classificação por Naive Bayes foram classificados como pontos sobre o terreno 84.801 (Figura 2a) dos 132.478 pontos. Esse modelo não conseguiu remover totalmente os pontos que estavam sobre o prédio e árvores, isso pode ter acontecido porque as alguns pontos das classes de treinamento possuíam semelhança espectral, por exemplo, os pontos que estavam sobre o prédio ou calçadas, no qual eram de classes distintas nos dados de treinamento. Esses equívocos na classificação também podem serem vistos na matriz de confusão, em que foi formada pelos dados de validação. O mesmo modelo por Naive Bayes aplicado nos dados de validação resultaram nos erros conforme a Quadro 1, esses erros de classificação foram semelhante para ambas as classes, resultando em uma exatidão global de 88,6% e um valor para o kappa de 76%. Apesar desses valores serem considerados satisfatórios, um ponto de altitude que não seja removido do prédio, por exemplo, faz com que o MDT apresente inconsistências. QUADRO 1 – MATRIZ DE CONFUSÃO. Classes dos dados de Classes atribuída por Naive Bayes validação Pontos sobre o terreno Pontos indesejáveis Pontos sobre o terreno 1875 225 Pontos indesejáveis 231 1675 Com o proposito de remover todos os pontos indesejáveis foi aplicado um segundo filtro, nesse filtro é calculada a declividade média de um ponto em relação aos seus vizinhos, o ponto é removido se o valor da média ficar acima do valor máximo para a declividade. Foram testados valores de 1 até 15 para o número de vizinhos a ser analisados e valores máximos para a declividade de 5 a 35 graus. Quando foi considerado valores maiores que 5 para o número de vizinhos e valores menores que 25 graus para a declividade máxima, houve a remoção de quase todos os pontos nos dados. Considerando o número de pontos removidos e o número de pontos sobre o prédio, os melhores valores encontrados para esses parâmetros foram de quatro para o número de vizinhos e 30 graus para a declividade máxima. Utilizando esses valores todos os pontos sobre o prédio foram removidos, mas permaneceram alguns pontos sobre as árvores, o total de pontos de altitudes que restaram dessa filtragem foi de 2511 (Figura 2b). Na Figura 2c está ilustrado um mapa de densidade dos pontos restantes, com esse mapa é possível verificar que as áreas da metade sul, onde possuem árvores agrupadas, estão com menos pontos de altitudes. 5 Fig. 2 – a) Nuvem de pontos após a classificação por Naive Bayes, b) nuvem de pontos após a filtragem pela declividade e c) mapa de densidade dos pontos. Os pontos restantes dos processos de filtragem foram interpolados utilizando a técnica TPS, o primeiro valor utilizado para a suavização foi de 0,01 (Figura 3a), agora denominado de MDT_001. O MDT resultante dessa interpolação apresentou um pico no centro do mapa, esse local apresenta as maiores altitudes do terreno, mas os valores estão acima do esperado. Então, inferi-se que pontos sobre as árvores foram considerados na interpolação. Na segunda interpolação foi utilizado o valor de 0,1 (MDT_01) para o parâmetro de suavização (Figura 3b), o MDT gerado desse processo diminui o pico visto no mapa anterior, mas foi gerada uma forma arredondada para a parte mais baixa, ao sul da imagem. No terreno não é observado esse comportamento. A elaboração do último MDT foi produzido com um parâmetro de suavização igual a 1 (MDT_1) (Figura 3c), esse valor fez com que a curva que interpola os dados não fosse forçada a passar pelos pontos de entrada e com isso gerando uma superfície mais suave. Fig. 3 – a) MDT_001, b) MDT_01 e c) MDT_1. 6 Avaliando os valores que estão na Tabela 2, verifica-se que O MDT mais próximos aos dados de campo, foi o que utilizou o parâmetro de suavização igual a 1. Os valores para RMSE foram altos para os três modelos , isso pode ter acontecido porque na metade sul foram retirados muitos pontos, forçando o interpolador a calcular valores para esses locais com altitudes que não representam esse local. E também como o cálculo RMSE valoriza valores altos, pois eleva a diferença do valores ao quadrado, esses resultados apresentaram valores alto. Estatísticas TABELA 2 – ESTATÍSTICAS DOS DADOS Valor observado a campo (m) MDT_001 (m) MDT_01 (m) MDT_1 (m) Mínimo 1094,51 1090,25 1091,91 1094,04 Máximo 1100,38 1102,81 1101,04 1100,60 Média 1097,58 1098,15 1097,95 1097,82 RMSE não considerar 2,03 1,65 1,35 3. CONCLUSÃO As imagens processadas no PhotoScan apresentaram alguns problemas na ortorretificação das imagens sobre prédios. A filtragem por Naive Bayes não conseguiu remover totalmente os pontos sobre o prédio e árvores, devido a isso foi necessário aplicar mais uma técnica de filtragem, essa técnica de filtragem utilizando o cálculo da declividade possibilitou a remoção dos pontos indesejáveis. A interpolação dessa nuvem de pontos por TPS, com o valor para o parâmetro de suavização igual a 1, resultou em um modelo consistente com o terreno da área de estudo, mas ao avaliar a qualidade desse modelo com amostras de campo, os resultados mostraram que há pontos com grandes diferenças, assim gerando um RMSE com valor alto. REFERÊNCIAS BIBLIOGRÁFICAS BANDARA, K. R.; SAMARAKOON, L.; SHRESTHA, R. P.; KAMIYA, Y. Automated generation of digital terrain model using point clouds of digital surface model in forest area, Remote Sensing, v. 3, n. 5, p. 845-858, Feb., 2011. BARBOSA, R.L.; MENEGUETTE JR, M.; SILVA, J.F.C.; GAITAME, O.Y. Análise estatística da qualidade de um modelo digital do terreno gerado com thin plate spline. Revista Brasileira de Cartografia, v. 60, n.2, Ago 2008. (ISSN 1808-0936) . CONTE, G. et al. Performance evaluation of a light-weight multi-echo Lidar for unmanned rotorcraft applications. In: CONFERENCE ON UNMANNED AERIAL VEHICLE IN GEOMATICS, 2013, Rostock. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Enschede, v.40, n.1, p. 87-92, Nov., 2013. CONGALTON, R.G. A review of assessing the accuracy of classifications of remotely sensed data. Remote Sensing of Environment, v.37, p.35-46, 1991. Disponível em: <http://dx.doi. org/10.1016/0034-4257(91)90048-B>. Acesso em: 12 jun. 2014. doi: 10.1016/0034-4257(91)90048-B. EVERAERTS, J. The use of unmanned aerial vehicles (UAVs) for remote sensing and mapping. In: INTERNATIONAL SOCIETY FOR PHOTOGRAMMETRY AND REMOTE SENSING, 21st, 2008, Beijing. Proceedings. v.37, n.1, p. 1187-1192. GUO, Q.; LI. W; YU, H. AND ALVAREZ, O. Effects of topographic variability and lidar sampling density on several DEM interpolation methods, Photogrammetric Engineering and Remote Sensing, 2010, 76 (6), 701-712. PODOBNIKAR, T. Methods for Visual Quality Assessment of A Digital Terrain Model. S.A.P.I.EN.S, Vienna, v. 2, n. 2, jan. 2009. SANTOS, C. J. B.; SILVA, J. F. C.; MELLO, M. P. Controle da qualidade da altimetria de modelos digitais do terreno com a utilização de equipamentos GPS ocupando referências de nível. In: XXI Congresso Brasileiro de Cartografia, Belo Horizonte, 2003. Anais. v. 1, p. 1-10, 2003. 7 TURNER, D.; LUCIEER, A. AND WATSON, C. An Automated Technique for Generating Georectified Mosaics from Ultra-High Resolution Unmanned Aerial Vehicle (UAV) Imagery, Based on Structure from Motion (SfM) Point Clouds, Remote Sensing, v. 4, n. 5, p. 1392-1410, Mar., 2012. ZHANG, H. The optimality of Naive Bayes. In: INTERNATIONAL FLORIDA ARTIFICIAL INTELLIGENCE RESEARCH SOCIETY CONFERENCE (FLAIRS), 7th, 2004, Florida. Proceedings. v.7, n.1, p. 562-567. 8