Como transformar imagens de satélite em mapas. Visão computacional em Yandex

Uma das principais fontes de dados do serviço Yandex.Maps é a imagem de satélite. Para facilitar o trabalho com o mapa, os objetos são marcados com polígonos nas imagens: florestas, lagoas, ruas, casas, etc. Geralmente, os cartógrafos estão envolvidos na marcação. Decidimos ajudá-los e ensinar o computador a adicionar polígonos de casas sem a participação de pessoas.

Para operações com imagens, o campo de TI se chama visão de computador. Nos últimos anos, a maioria das tarefas nessa área foi resolvida com muito sucesso usando redes neurais. Hoje contaremos aos leitores de Habr sobre nossa experiência no uso de redes neurais no mapeamento.


Primeiro, treinaremos uma grade neural que se envolverá na segmentação semântica, ou seja, determinará se cada ponto na imagem de satélite está relacionado à casa. Por que a segmentação semântica e não apenas a detecção de objetos? Quando o problema de detecção for resolvido, obteremos na saída um conjunto de retângulos, além de específicos: dois lados são verticais, dois são horizontais. E as casas geralmente são giradas em relação aos eixos da imagem, e alguns edifícios também têm uma forma complexa.

A tarefa de segmentação semântica agora está sendo resolvida por várias redes ( FCN , SegNet , UNet , etc.). Você só precisa escolher qual é o melhor para nós.

Depois de receber a máscara da imagem de satélite, selecionamos grupos de pontos grandes o suficiente pertencentes às casas, os coletamos em áreas conectadas e apresentamos os limites das áreas em forma de vetor na forma de polígonos.

É claro que a máscara não será absolutamente precisa, o que significa que casas próximas podem se unir em uma área conectada. Para lidar com esse problema, decidimos treinar ainda mais a rede. Ela encontrará na imagem as costelas (os limites das casas) e separará os prédios que estão colados.

Então, esse esquema apareceu:


Não descartamos completamente as redes de detecção e tentamos o Mask R-CNN . Sua vantagem em comparação com a segmentação usual é que o Mask R-CNN detecta objetos e gera uma máscara, portanto, não há necessidade de mexer na divisão da máscara comum em áreas conectadas. Bem, menos (como sem ele) na resolução fixa da máscara de cada objeto, ou seja, para casas grandes com uma borda complexa, essa borda obviamente se tornará simplificada.

As ferramentas

Então foi necessário decidir sobre as ferramentas. Tudo era bem óbvio aqui: o OpenCV é mais adequado para tarefas de visão computacional. A escolha de redes neurais é um pouco mais ampla. Nós decidimos pelo Tensorflow . Suas vantagens:

• um conjunto bastante desenvolvido de "cubos" prontos a partir dos quais você pode montar suas redes;
• API Python, conveniente para criar rapidamente uma estrutura de rede e para treinamento;
• Uma rede treinada pode ser usada em seu programa por meio de uma interface C ++ (muito ruim em comparação com a parte Python, mas suficiente para executar redes prontas).

Para treinamento e outra computação pesada, planejamos usar o Nirvana - a maravilhosa plataforma Yandex da qual já falamos .

Datacet

Oitenta por cento de sucesso no trabalho com uma rede neural consiste em um bom conjunto de dados. Portanto, para iniciantes, deveríamos ter reunido esse conjunto de dados. O Yandex possui um grande número de imagens de satélite com objetos já marcados. Tudo parece ser simples: basta fazer o upload desses dados e coletá-los em um conjunto de dados. No entanto, há uma ressalva.

Refinar o conjunto de dados

Quando uma pessoa procura uma casa em uma imagem de satélite, a primeira coisa que vê é o telhado. Mas a altura das casas varia, o satélite pode tomar o mesmo terreno de diferentes ângulos - e se colocarmos um polígono correspondente ao telhado no mapa vetorial, não há garantia de que o telhado não saia quando a imagem for atualizada. Mas a fundação é cavada no chão e, de qualquer ângulo que você a retire, o tempo todo permanece em um só lugar. É por isso que as casas no vetor Yandex.Map estão marcadas "nas fundações". Isso está correto, mas para a tarefa de segmentar imagens, é melhor ensinar a rede a procurar telhados: a esperança de que a rede seja treinada para reconhecer as fundações é muito pequena. Portanto, no conjunto de dados, tudo deve ser marcado nos telhados. Portanto, para criar um bom conjunto de dados, precisamos aprender como mudar o layout vetorial das casas das fundações para os telhados.

Tentamos não mudar, mas a qualidade não era muito boa, e isso é compreensível: os ângulos de disparo do satélite são diferentes, as alturas das casas são diferentes, como resultado, nas fotografias, a fundação foi deslocada em diferentes direções e em diferentes distâncias do telhado. A rede se perde dessa variedade e, na melhor das hipóteses, treina para algo intermediário, na pior das hipóteses - para algo incompreensível. Além disso, a rede de segmentação semântica produz um resultado semelhante a algo aceitável, mas ao procurar arestas, a qualidade diminui drasticamente.

Abordagem raster

Desde que entramos no campo da visão computacional, a primeira coisa que fizemos foi tentar uma abordagem relevante para essa mesma visão computacional. Primeiro, o mapa vetorial é rasterizado (os polígonos das casas são desenhados com linhas brancas sobre fundo preto), o filtro Sobel seleciona as bordas da imagem de satélite. E então há um deslocamento de duas imagens uma em relação à outra, o que maximiza a correlação entre elas. As arestas após o filtro Sobel são bastante barulhentas, portanto, se essa abordagem é aplicada a um edifício, nem sempre um resultado aceitável é obtido. No entanto, o método funciona bem em territórios com edifícios da mesma altura: se você procurar um deslocamento imediatamente em uma grande área da imagem, o resultado será mais estável.

Abordagem "geométrica"

Se o território for construído não com o mesmo tipo, mas com várias casas, o método anterior não funcionará. Felizmente, às vezes sabemos a altura dos prédios no mapa vetorial Yandex e a posição do satélite durante as filmagens. Assim, podemos usar o conhecimento escolar de geometria e calcular onde e a que distância o telhado se moverá em relação à fundação. Este método melhorou o conjunto de dados em áreas com arranha-céus.

Abordagem "manual"

A maneira mais demorada: arregace as mangas, descubra o mouse, olhe fixamente para o monitor e mude manualmente o layout vetorial das casas das fundações para os telhados. A técnica traz um resultado que é simplesmente incrível em termos de qualidade, mas não é recomendável usá-lo em grandes quantidades: os desenvolvedores envolvidos nessas tarefas rapidamente caem em apatia e perdem o interesse pela vida.

Rede neural

No final, conseguimos imagens de satélite suficientes, bem marcadas nos telhados. Portanto, houve uma chance de treinar a rede neural (por enquanto, não para segmentação, mas para melhorar o layout de outras imagens de satélite). E nós fizemos isso.

Os dados de entrada da rede neural convolucional eram uma imagem de satélite e marcavam rasterizadas. Na saída, recebemos um vetor bidimensional: deslocamentos verticais e horizontais.


Com a ajuda de uma rede neural, encontramos o deslocamento necessário, o que nos permitiu obter bons resultados em edifícios para os quais a altura não é indicada. Como resultado, reduzimos significativamente a correção manual da marcação.

Territórios diferentes - casas diferentes

Existem muitos territórios e estados interessantes no Yandex.Maps. Mas, mesmo na Rússia, as casas são extremamente diversas, o que afeta a aparência das imagens de satélite. Portanto, você precisa refletir a diversidade no conjunto de dados. E, inicialmente, não entendemos realmente como lidar com todo esse esplendor. Colete um grande conjunto de dados e treine uma rede nele? Crie seu próprio conjunto de dados para cada tipo (condicional) de desenvolvimento e treine uma rede separada? Treinar uma determinada rede principal e treiná-la para um tipo específico de desenvolvimento?


Empiricamente, descobrimos que:

1. Sem dúvida, é necessário expandir o conjunto de dados para diferentes tipos de edifícios nos quais está planejado usar a ferramenta. Uma rede treinada em um tipo é capaz de distinguir edifícios de outro tipo, embora muito mal.
2. É melhor treinar uma rede grande em todo o conjunto de dados. Generaliza bastante bem para vários territórios. Se você treinar redes separadas para cada tipo de desenvolvimento, a qualidade permanecerá a mesma ou apenas melhorará. Portanto, não faz sentido implementar redes diferentes para diferentes territórios. Além disso, isso requer mais dados e um classificador adicional do tipo de desenvolvimento.
3. Se você usar redes antigas ao adicionar novos territórios aos dados, as redes aprenderão muito mais rapidamente. A reciclagem de redes antigas em dados estendidos leva a aproximadamente o mesmo resultado que o treinamento de uma rede a partir do zero, mas requer muito menos tempo.

Opções de solução

Segmentação semântica

A segmentação semântica é uma tarefa bastante bem pesquisada. Após o aparecimento do artigo Redes totalmente convolucionais , ele é resolvido principalmente usando redes neurais. Resta apenas escolher uma rede (consideramos FCN , SegNet e UNet ), pensar se precisamos de truques adicionais como CRF na saída e determinar como e com que função de erro o treinamento será treinado.


Como resultado, adotamos uma arquitetura do tipo U-Net com uma função de Intersecção sobre união generalizada como uma função de erro. Para o treinamento, cortamos imagens de satélite e suas marcações correspondentes (é claro, rasterizadas) em quadrados e montadas em conjuntos de dados. Acabou bem legal, e às vezes muito bem.


Em territórios com edifícios únicos, a segmentação semântica era suficiente para passar para o próximo estágio - a vetorização. Onde o prédio é denso, as casas às vezes ficam presas em uma área coesa. Demorou para separá-los.

Detecção de borda

Para lidar com esta tarefa, você pode encontrar as bordas da imagem. Para detectar arestas, também decidimos treinar a rede (algoritmos de busca de arestas que não usam redes neurais são claramente coisa do passado). Treina uma rede do tipo HED, descrita em Detecção de Borda Aninhada Holisticamente . No artigo original, a rede foi treinada no conjunto de dados BSDS-500, no qual todas as bordas estão marcadas nas imagens. Uma rede treinada encontra todas as arestas pronunciadas: os limites de casas, estradas, lagos etc. Isso já é suficiente para separar os prédios próximos. Mas decidimos ir além e usar o mesmo conjunto de dados para treinamento e para segmentação semântica, mas ao rasterizar, não pinte os polígonos inteiros dos edifícios, mas apenas trave seus limites.

O resultado foi tão impressionante que decidimos vetorizar os edifícios diretamente pelas bordas recebidas da rede. E aconteceu bastante.

Detecção de vértices

Como uma rede como o HED deu um excelente resultado nas arestas, decidimos treiná-la para detectar vértices. De fato, temos uma rede com pesos gerais em camadas convolucionais. Ela tinha duas saídas ao mesmo tempo: para bordas e picos. Como resultado, fizemos outra versão da vetorização dos edifícios e, em alguns casos, apresentou resultados bastante sãos.

Máscara r-cnn

O Mask R-CNN é uma expansão relativamente nova de redes como o Faster R-CNN. Máscara O R-CNN procura objetos e seleciona uma máscara para cada um deles. Como resultado, para casas, obtemos não apenas retângulos delimitadores, mas também uma estrutura refinada. Essa abordagem se compara favoravelmente com a detecção simples (não sabemos como o edifício está localizado dentro do retângulo) e a segmentação normal (várias casas podem se unir em uma, e não está claro como separá-las). Com o Mask R-CNN, você não precisa mais pensar em truques adicionais: basta vetorizar a borda da máscara para cada objeto e obter o resultado imediatamente. Há também um sinal de menos: o tamanho da máscara para o objeto é sempre fixo, ou seja, para edifícios grandes, a precisão do layout de pixels será baixa. O resultado do Mask R-CNN é assim:


Tentamos o Mask R-CNN por último e garantimos que, para alguns tipos de edifícios, essa abordagem supere outras.

Vetorização

Vetorização de retângulos

Com toda a diversidade arquitetônica moderna, casas em imagens de satélite ainda mais parecem retângulos. Além disso, para a massa de territórios, a marcação com polígonos complexos não é necessária. Mas ainda quero que as casas no mapa sejam marcadas. (Bem, por exemplo, uma parceria hortícola: geralmente há muitas casas lá, marcar manualmente não é tão importante, mas marcar com retângulos no mapa é muito bom.) Portanto, a primeira abordagem à vetorização foi extremamente simples.

1. Pegue a região raster correspondente à "casa".
2. Localize o retângulo da área mínima que contém essa área (por exemplo, assim: OpenCV :: minAreaRect ). O problema está resolvido.

É claro que a qualidade dessa abordagem está longe de ser ideal. No entanto, o algoritmo é bastante simples e, em muitos casos, está funcionando.

Vetorização de polígonos

Se a qualidade da segmentação for boa o suficiente, você poderá recriar com mais precisão o contorno da casa. Na maioria dos edifícios de formas complexas, os ângulos são geralmente corretos, por isso decidimos reduzir o problema à tarefa de construir um polígono com lados ortogonais. Para resolvê-lo, queremos atingir dois objetivos ao mesmo tempo: encontrar o polígono mais simples e repetir a forma dos edifícios com a maior precisão possível. Esses objetivos conflitam entre si; portanto, é necessário introduzir condições adicionais: limitar o comprimento mínimo das paredes, o desvio máximo da região de varredura etc.

O algoritmo que nos ocorreu pela primeira vez foi baseado na construção da projeção de pontos em linhas retas:

1. Encontre o contorno da região raster correspondente a uma casa.
2. Reduza o número de pontos no circuito, simplificando-o, por exemplo, com o algoritmo Douglas-Pecker .
3. Encontre o lado mais longo no contorno. É o seu ângulo de inclinação que determinará o ângulo de todo o futuro polígono ortogonal.
4. Construa uma projeção do próximo ponto de contorno para o lado anterior.
5. Estenda o lado para o ponto de projeção. Se a distância do ponto até a projeção for maior que a parede mais curta do edifício, adicione o segmento resultante ao contorno do edifício.
6. Repita as etapas 4 e 5 até o circuito fechar.

Esse algoritmo é extremamente simples e traz resultados rapidamente, mas ainda assim o contorno do edifício às vezes acaba sendo bastante barulhento. Tentando lidar com esse problema, encontramos uma solução bastante interessante para o problema, que usa uma grade quadrada no espaço para aproximar o polígono. Resumidamente, o algoritmo consiste em três ações:

1. Crie uma grade quadrada no espaço centralizado em zero.
2. Em pontos da grade localizados a uma distância maior do contorno original, construa polígonos diferentes.
3. Selecione um polígono com um número mínimo de vértices.

Como o ângulo de rotação necessário da grade não é conhecido antecipadamente, é necessário classificar vários valores, o que afeta mal o desempenho. No entanto, o algoritmo permite alcançar resultados visualmente mais bonitos.

Melhoria da vetorização

Enquanto nós trabalhamos com cada casa separadamente. Quando a primeira etapa estiver concluída, você já poderá trabalhar com a imagem como um todo e melhorar o resultado. Para isso, foi adicionado um algoritmo para pós-processamento de um conjunto de polígonos. Usamos as seguintes heurísticas:

• Geralmente as paredes das casas adjacentes são paralelas. Além disso: na maioria das vezes, as casas podem ser combinadas em conjuntos, dentro dos quais todos os elementos estão alinhados.
• Se as ruas já estiverem marcadas na imagem, é muito provável que os lados dos polígonos sejam paralelos às ruas.
• Se os polígonos se cruzarem, é mais provável que faça sentido mover as paredes para que a interseção desapareça.

Como resultado, o seguinte algoritmo apareceu:

1. Agrupamos as casas encontradas pela distância entre elas e pelo ângulo de rotação. Calculamos a média das voltas dos edifícios em cada cluster. Repetimos até que a posição dos edifícios deixe de mudar ou até que as casas comecem a se desviar muito da posição inicial.
2. Escolhemos casas próximas às estradas, encontramos as mais longas e próximas da beira da estrada. Transformamos a casa no paralelismo do lado selecionado e da estrada.
3. Removemos as interseções entre os polígonos, deslocando os lados de dois edifícios que se cruzam na proporção do tamanho dos lados.

Resultado

Como resultado, obtivemos uma ferramenta que pode reconhecer edifícios de vários tipos de edifícios. Ajuda os cartógrafos em seu trabalho árduo: acelera significativamente a busca por casas desaparecidas e o preenchimento de novas áreas ainda não cultivadas. Atualmente, mais de 800 mil novos objetos foram adicionados ao Mapa do Povo usando essa ferramenta.

Abaixo você verá alguns exemplos de reconhecimento.