Comment transformer l'imagerie satellite en cartes. Vision par ordinateur dans Yandex

L'imagerie satellite est l'une des principales sources de données du service Yandex.Maps. Afin de faciliter le travail avec la carte, les objets sont marqués de polygones sur les photographies: forêts, étangs, rues, maisons, etc. Habituellement, les cartographes sont engagés dans le marquage. Nous avons décidé de les aider et d'apprendre à l'ordinateur à ajouter des polygones de maisons sans intervention humaine.

Pour les opérations avec images rencontre le domaine de l'informatique, qui est appelé vision par ordinateur. Au cours des dernières années, la plupart des tâches dans ce domaine ont été résolues avec succès en utilisant des réseaux de neurones. Aujourd'hui, nous parlerons aux lecteurs de Habr de notre expérience de l'utilisation des réseaux de neurones dans la cartographie.


Tout d'abord, nous allons former une grille neuronale, qui va s'engager dans la segmentation sémantique, c'est-à-dire déterminer si chaque point de l'image satellite est lié à la maison. Pourquoi la segmentation sémantique et pas seulement la détection d'objets? Lorsque le problème de détection sera résolu, on obtiendra en sortie un ensemble de rectangles, d'ailleurs spécifiques: deux côtés sont verticaux, deux horizontaux. Et les maisons sont généralement tournées par rapport aux axes de l'image, et certains bâtiments ont également une forme complexe.

La tâche de segmentation sémantique est désormais résolue par différents réseaux ( FCN , SegNet , UNet , etc.). Il vous suffit de choisir celui qui nous convient le mieux.

Après avoir reçu le masque de l'image satellite, nous sélectionnons des groupes de points suffisamment grands appartenant aux maisons, les collectons dans les zones connectées et présentons les limites des zones sous forme vectorielle sous forme de polygones.

Il est clair que le masque ne sera pas absolument précis, ce qui signifie que les maisons voisines peuvent rester ensemble dans une zone connectée. Pour faire face à ce problème, nous avons décidé de poursuivre la formation du réseau. Elle trouvera dans l'image les nervures (les limites des maisons) et séparera les bâtiments collés.

Donc, un tel schéma se profilait:


Nous n'avons pas complètement éliminé les réseaux de détection et essayé le masque R-CNN . Son avantage par rapport à la segmentation habituelle est que le masque R-CNN détecte des objets et génère un masque, il n'est donc pas nécessaire de bricoler en divisant le masque commun en zones connectées. Eh bien, moins (comme sans lui) dans la résolution fixe du masque de chaque objet, c'est-à-dire pour les grandes maisons avec une bordure complexe, cette bordure se révélera évidemment simplifiée.

Les outils

Ensuite, il a fallu décider des outils. Tout était assez évident ici: OpenCV est le mieux adapté aux tâches de vision par ordinateur. Le choix des réseaux de neurones est un peu plus large. Nous nous sommes installés sur Tensorflow . Ses avantages:

• un ensemble assez développé de «cubes» prêts à l'emploi à partir desquels vous pouvez assembler vos réseaux;
• API Python, pratique pour créer rapidement une structure de réseau et pour la formation;
• Un réseau formé peut être utilisé dans votre programme via une interface C ++ (très pauvre en comparaison avec la partie Python, mais tout à fait suffisant pour exécuter des réseaux prêts à l'emploi).

Pour la formation et autres calculs lourds, nous avions prévu d'utiliser Nirvana - la merveilleuse plateforme Yandex dont nous avons déjà parlé .

Datacet

Quatre-vingt pour cent de réussite dans l'utilisation d'un réseau de neurones consiste en un bon ensemble de données. Donc, pour commencer, nous aurions dû assembler un tel ensemble de données. Yandex possède un grand nombre d'images satellites avec des objets déjà marqués. Tout semble simple: il suffit de télécharger ces données et de les collecter dans un ensemble de données. Cependant, il y a une mise en garde.

Affiner l'ensemble de données

Lorsqu'une personne recherche une maison sur une image satellite, la première chose qu'elle voit est le toit. Mais la hauteur des maisons varie, le satellite peut prendre le même terrain sous différents angles - et si nous plaçons un polygone correspondant au toit sur la carte vectorielle, rien ne garantit que le toit ne partira pas lorsque l'image sera mise à jour. Mais la fondation est enfouie dans le sol et, quel que soit l'angle sous lequel vous la retirez, elle reste tout le temps au même endroit. C'est pourquoi les maisons sur le vecteur Yandex.Map sont marquées "sur les fondations". C'est exact, mais pour la tâche de segmentation des images, il est préférable d'apprendre au réseau à rechercher des toits: l'espoir que le réseau soit formé pour reconnaître les fondations est très faible. Par conséquent, dans l'ensemble de données, tout doit être marqué sur les toits. Donc, pour créer un bon ensemble de données, nous devons apprendre à déplacer la disposition vectorielle des maisons des fondations aux toits.

Nous avons essayé de ne pas bouger, mais la qualité n'était pas très bonne, et cela est compréhensible: les angles de prise de vue du satellite sont différents, les hauteurs des maisons sont différentes, en conséquence, sur les photographies, la fondation a été déplacée dans différentes directions et à différentes distances du toit. Le réseau est perdu d'une telle variété et, au mieux, s'entraîne pour quelque chose entre les deux, au pire - pour quelque chose d'incompréhensible. De plus, le réseau de segmentation sémantique produit un résultat similaire à quelque chose d'acceptable, mais lors de la recherche de bords, la qualité chute considérablement.

Approche raster

Depuis que nous sommes entrés dans le domaine de la vision par ordinateur, la première chose que nous avons faite a été d'essayer une approche pertinente à cette vision par ordinateur. Tout d'abord, la carte vectorielle est tramée (les polygones des maisons sont dessinés avec des lignes blanches sur fond noir), le filtre Sobel sélectionne les bords de l'image satellite. Et puis il y a un décalage de deux images l'une par rapport à l'autre, ce qui maximise la corrélation entre elles. Les bords après le filtre Sobel sont assez bruyants, par conséquent, si cette approche est appliquée à un bâtiment, un résultat acceptable n'est pas toujours obtenu. Cependant, la méthode fonctionne bien dans les territoires avec des bâtiments de même hauteur: si vous recherchez un décalage immédiatement sur une grande zone de l'image, le résultat sera plus stable.

Approche "géométrique"

Si le territoire n'est pas construit avec le même type, mais avec différentes maisons, la méthode précédente ne fonctionnera pas. Heureusement, nous connaissons parfois la hauteur des bâtiments sur la carte vectorielle Yandex et la position du satellite lors du tournage. Ainsi, nous pouvons utiliser les connaissances scolaires de la géométrie et calculer où et à quelle distance le toit se déplacera par rapport à la fondation. Cette méthode a amélioré l'ensemble de données dans les zones avec des immeubles de grande hauteur.

Approche "manuelle"

Le moyen le plus long: retroussez vos manches, découvrez la souris, regardez le moniteur et déplacez manuellement la disposition vectorielle des maisons des fondations aux toits. La technique apporte un résultat tout simplement incroyable en qualité, mais il n'est pas recommandé de l'utiliser en grande quantité: les développeurs qui sont engagés dans de telles tâches tombent rapidement dans l'apathie et perdent tout intérêt pour la vie.

Réseau de neurones

Au final, nous avons obtenu suffisamment d'images satellites bien marquées sur les toits. Ainsi, il y avait une chance de former le réseau neuronal (pour l'instant, cependant, pas pour la segmentation, mais pour améliorer la disposition d'autres images satellite). Et nous l'avons fait.

Les données d'entrée du réseau neuronal convolutif étaient une image satellite et un marquage tramé décalé. En sortie, nous avons reçu un vecteur bidimensionnel: les déplacements verticaux et horizontaux.


A l'aide d'un réseau neuronal, nous avons trouvé le déplacement nécessaire, ce qui nous a permis d'obtenir de bons résultats sur des bâtiments dont la hauteur n'est pas indiquée. Par conséquent, nous avons considérablement réduit la correction manuelle du balisage.

Différents territoires - différentes maisons

Il existe de nombreux territoires et États intéressants sur Yandex.Maps. Mais même en Russie, les maisons sont extrêmement diverses, ce qui affecte leur apparence dans l'imagerie satellite. Vous devez donc refléter la diversité de l'ensemble de données. Et au début, nous ne comprenions pas vraiment comment faire face à toute cette splendeur. Collecter un énorme ensemble de données puis former un réseau dessus? Créer votre propre ensemble de données pour chaque type de développement (conditionnel) et former un réseau distinct? Former un certain réseau central puis le former à un type de développement spécifique?


Empiriquement, nous avons constaté que:

1. Sans aucun doute, il est nécessaire d'élargir l'ensemble de données pour différents types de bâtiments sur lesquels il est prévu d'utiliser l'outil. Un réseau formé sur un type est capable de distinguer des bâtiments d'un autre type, bien que très mal.
2. Il est préférable de former un grand réseau sur l'ensemble des données. Il se généralise assez bien à divers territoires. Si vous formez des réseaux distincts pour chaque type de développement, la qualité restera la même ou s'améliorera à peine. Il est donc inutile de mettre en œuvre différents réseaux pour différents territoires. De plus, cela nécessite plus de données et un classificateur supplémentaire de type de développement.
3. Si vous utilisez d'anciens réseaux lors de l'ajout de nouveaux territoires aux données, les réseaux apprennent beaucoup plus rapidement. Le recyclage des anciens réseaux sur des données étendues conduit à peu près au même résultat que la formation d'un réseau à partir de zéro, mais cela nécessite beaucoup moins de temps.

Options de solution

Segmentation sémantique

La segmentation sémantique est une tâche assez bien étudiée. Après la parution de l'article Réseaux entièrement convolutionnels , il est principalement résolu à l'aide de réseaux de neurones. Il ne reste plus qu'à choisir un réseau (nous avons considéré FCN , SegNet et UNet ), à réfléchir si nous avons besoin de trucs supplémentaires comme CRF à la sortie, et à décider comment et avec quelle fonction d'erreur la formation sera formée.


En conséquence, nous avons opté pour une architecture de type U-Net avec une fonction généralisée d'intersection sur union comme fonction d'erreur. Pour la formation, nous avons découpé des images satellites et leurs marquages ​​correspondants (bien sûr, tramées) en carrés et assemblés en ensembles de données. Cela s'est avéré assez agréable, et parfois très bien.


Dans les territoires à bâtiments uniques, la segmentation sémantique était suffisante pour passer à l'étape suivante - la vectorisation. Lorsque le bâtiment est dense, les maisons sont parfois collées ensemble dans une zone cohésive. Il a fallu les séparer.

Détection des contours

Pour faire face à cette tâche, vous pouvez trouver les bords de l'image. Pour détecter les bords, nous avons également décidé de former le réseau (les algorithmes de recherche de bords qui n'utilisent pas de réseaux de neurones appartiennent clairement au passé). Formation d'un réseau de type HED, qui est décrit dans Holistically-Nested Edge Detection . Dans l'article d'origine, le réseau a été formé sur l'ensemble de données BSDS-500, dans lequel tous les bords sont marqués sur les images. Un réseau formé trouve tous les bords prononcés: les limites des maisons, des routes, des lacs, etc. C'est déjà suffisant pour séparer les bâtiments voisins. Mais nous avons décidé d'aller plus loin et d'utiliser le même ensemble de données pour la formation que pour la segmentation sémantique, mais lors de la pixellisation, ne peignez pas tous les polygones des bâtiments, mais dessinez uniquement leurs limites.

Le résultat était si incroyablement beau que nous avons décidé de vectoriser les bâtiments directement par les bords reçus du réseau. Et c'est tout à fait arrivé.

Détection de sommet

Puisqu'un réseau comme HED a donné un excellent résultat sur les bords, nous avons décidé de l'entraîner à détecter les sommets. En fait, nous avons un réseau avec des poids généraux sur les couches convolutives. Elle avait deux sorties en même temps: pour les bords et pour les pics. En conséquence, nous avons fait une autre version de la vectorisation des bâtiments, et dans certains cas, elle a donné des résultats assez raisonnables.

Masque r-cnn

Mask R-CNN est une extension relativement nouvelle de réseaux tels que Faster R-CNN. Masque R-CNN recherche des objets et sélectionne un masque pour chacun d'eux. En conséquence, pour les maisons, nous obtenons non seulement des rectangles de délimitation, mais également une structure raffinée. Cette approche se compare favorablement à la détection simple (nous ne savons pas comment le bâtiment est situé à l'intérieur du rectangle) et à la segmentation normale (plusieurs maisons peuvent se coller en une seule, et il n'est pas clair comment les séparer). Avec Mask R-CNN, plus besoin de penser à des astuces supplémentaires: il suffit de vectoriser la bordure du masque pour chaque objet et d'obtenir immédiatement le résultat. Il y a aussi un inconvénient: la taille du masque pour l'objet est toujours fixe, c'est-à-dire que pour les grands bâtiments, la précision de la disposition des pixels sera faible. Le résultat du masque R-CNN ressemble à ceci:


Nous avons essayé le Mask R-CNN en dernier et nous nous sommes assurés que pour certains types de bâtiments, cette approche surpasse d'autres.

Vectorisation

Vectorisation rectangle

Avec toute la diversité architecturale moderne, les maisons sur images satellite ressemblent encore le plus souvent à des rectangles. De plus, pour la masse des territoires, le marquage avec des polygones complexes n'est pas nécessaire. Mais je veux quand même que les maisons sur la carte soient marquées. (Eh bien, par exemple, un partenariat horticole: il y a généralement beaucoup de maisons là-bas, le marquage manuel n'est pas si important, mais le marquage avec des rectangles sur la carte est très bon.) Par conséquent, la première approche de la vectorisation était extrêmement simple.

1. Prenez la région raster correspondant à la "maison".
2. Recherchez le rectangle de la zone minimale qui contient cette zone (par exemple, comme ceci: OpenCV :: minAreaRect ). Le problème est résolu.

Il est clair que la qualité de cette approche est loin d'être idéale. Cependant, l'algorithme est assez simple et fonctionne dans de nombreux cas.

Vectorisation de polygone

Si la qualité de la segmentation est assez bonne, vous pouvez recréer plus précisément le contour de la maison. Dans la plupart des bâtiments de forme complexe, les angles sont généralement droits, nous avons donc décidé de réduire le problème à la construction d'un polygone à côtés orthogonaux. Pour le résoudre, nous voulons atteindre deux objectifs à la fois: trouver le polygone le plus simple et répéter la forme des bâtiments aussi précisément que possible. Ces objectifs sont en conflit les uns avec les autres, vous devez donc introduire des conditions supplémentaires: pour limiter la longueur minimale des murs, l'écart maximal par rapport à la zone raster, etc.

L'algorithme qui nous est venu à l'esprit pour la première fois était basé sur la construction de la projection de points sur des lignes droites:

1. Trouvez le contour de la région raster correspondant à une maison.
2. Réduisez le nombre de points dans le circuit en le simplifiant, par exemple, avec l'algorithme Douglas-Pecker .
3. Trouvez le côté le plus long dans le contour. C'est son angle d'inclinaison qui déterminera l'angle de tout le futur polygone orthogonal.
4. Construisez une projection du point de contour suivant au côté précédent.
5. Étendez le côté jusqu'au point de projection. Si la distance entre le point et sa projection est supérieure au mur le plus court du bâtiment, ajoutez le segment résultant au contour du bâtiment.
6. Répétez les étapes 4 et 5 jusqu'à la fermeture du circuit.

Cet algorithme est extrêmement simple et donne rapidement des résultats, mais le contour du bâtiment se révèle cependant parfois assez bruyant. En essayant de faire face à ce problème, nous sommes tombés sur une solution plutôt intéressante au problème, qui utilise une grille carrée dans l'espace pour approximer le polygone. En bref, l'algorithme se compose de trois actions:

1. Construisez une grille carrée dans l'espace centrée sur zéro.
2. Aux points de la grille situés à une certaine distance du contour d'origine, construisez différents polygones.
3. Sélectionnez un polygone avec un nombre minimum de sommets.

L'angle de rotation requis de la grille n'étant pas connu à l'avance, il est nécessaire de trier plusieurs valeurs, ce qui affecte mal les performances. Cependant, l'algorithme vous permet d'obtenir des résultats visuellement plus beaux.

Amélioration de la vectorisation

Alors que nous travaillions avec chaque maison séparément. Lorsque la première étape est terminée, vous pouvez déjà travailler avec l'image dans son ensemble et améliorer le résultat. Pour cela, un algorithme de post-traitement d'un ensemble de polygones a été ajouté. Nous avons utilisé les heuristiques suivantes:

• Habituellement, les murs des maisons adjacentes sont parallèles. De plus: le plus souvent, les maisons peuvent être combinées en ensembles, à l'intérieur desquels tous les éléments sont alignés.
• Si les rues sont déjà marquées sur l'image, il est très probable que les côtés des polygones soient parallèles aux rues.
• Si les polygones se croisent, il est très probable qu'il soit logique de déplacer les murs afin que l'intersection disparaisse.

En conséquence, l'algorithme suivant est apparu:

1. Nous regroupons les maisons trouvées par la distance entre elles et l'angle de rotation. Nous faisons la moyenne des tours de bâtiments dans chaque cluster. Nous répétons jusqu'à ce que la position des bâtiments cesse de changer ou jusqu'à ce que les maisons commencent à s'écarter trop de la position initiale.
2. Nous choisissons des maisons près des routes, nous trouvons les plus longues et les plus proches du bord de la route. Nous transformons la maison au parallélisme du côté sélectionné et de la route.
3. Nous supprimons les intersections entre les polygones, en décalant les côtés de deux bâtiments qui se croisent proportionnellement à la taille des côtés.

Résultat

En conséquence, nous avons obtenu un outil qui peut reconnaître les bâtiments de différents types de bâtiments. Il aide les cartographes dans leur travail acharné: accélère considérablement la recherche de maisons manquantes et remplit de nouvelles zones non encore cultivées. Actuellement, plus de 800 000 nouveaux objets ont été ajoutés à la carte des personnes à l'aide de cet outil.

Ci-dessous, vous verrez quelques exemples de reconnaissance.