So verwandeln Sie Satellitenbilder in Karten. Computer Vision in Yandex

Eine der Hauptdatenquellen für den Yandex.Maps-Dienst sind Satellitenbilder. Um die Arbeit mit der Karte zu vereinfachen, sind Objekte: Wälder, Teiche, Straßen, Häuser usw. auf den Fotos mit Polygonen gekennzeichnet. In der Regel sind Kartografen mit der Kennzeichnung beschäftigt. Wir beschlossen, ihnen zu helfen und dem Computer beizubringen, Polygone von Häusern ohne die Beteiligung von Menschen hinzuzufügen.

Für Operationen mit Bildern trifft der Bereich der IT, der als Computer Vision bezeichnet wird. In den letzten Jahren wurden die meisten Aufgaben in diesem Bereich mithilfe neuronaler Netze sehr erfolgreich gelöst. Heute werden wir den Lesern von Habr über unsere Erfahrungen mit der Verwendung neuronaler Netze beim Mapping berichten.


Zunächst werden wir ein neuronales Gitter trainieren, das sich mit der semantischen Segmentierung befasst, d. H. Bestimmt, ob jeder Punkt im Satellitenbild mit dem Haus zusammenhängt. Warum ist semantische Segmentierung und nicht nur Objekterkennung? Wenn das Erkennungsproblem gelöst ist, erhalten wir am Ausgang eine Reihe von Rechtecken, die außerdem spezifisch sind: Zwei Seiten sind vertikal, zwei sind horizontal. Und Häuser werden normalerweise relativ zu den Bildachsen gedreht, und einige Gebäude haben auch eine komplexe Form.

Die Aufgabe der semantischen Segmentierung wird nun von verschiedenen Netzwerken ( FCN , SegNet , UNet usw.) gelöst. Sie müssen nur auswählen, welches für uns am besten geeignet ist.

Nachdem wir die Maske vom Satellitenbild erhalten haben, wählen wir ausreichend große Gruppen von Punkten aus, die zu den Häusern gehören, sammeln sie in verbundenen Bereichen und präsentieren die Grenzen der Bereiche in Vektorform in Form von Polygonen.

Es ist klar, dass die Maske nicht absolut genau ist, was bedeutet, dass Häuser in der Nähe in einem verbundenen Bereich zusammenkleben können. Um dieses Problem zu lösen, haben wir beschlossen, das Netzwerk weiter auszubilden. Sie findet im Bild die Rippen (die Grenzen der Häuser) und trennt die zusammengeklebten Gebäude.

Ein solches Schema zeichnete sich ab:


Wir haben die Erkennungsnetzwerke nicht vollständig verworfen und Mask R-CNN ausprobiert. Das Plus im Vergleich zur üblichen Segmentierung besteht darin, dass die Maske R-CNN Objekte erkennt und eine Maske generiert, sodass die gemeinsame Maske nicht in verbundene Bereiche unterteilt werden muss. Nun, minus (wie ohne) in der festen Auflösung der Maske jedes Objekts, d. H. Für große Häuser mit einer komplexen Grenze, wird sich diese Grenze offensichtlich als vereinfacht herausstellen.

Die Werkzeuge

Dann musste man sich für die Werkzeuge entscheiden. Hier war alles ziemlich offensichtlich: OpenCV eignet sich am besten für Computer Vision-Aufgaben. Die Auswahl an neuronalen Netzen ist etwas größer. Wir haben uns für Tensorflow entschieden . Seine Vorteile:

• ein ziemlich entwickelter Satz vorgefertigter „Würfel“, aus denen Sie Ihre Netzwerke zusammenstellen können;
• Python-API, praktisch zum schnellen Erstellen einer Netzwerkstruktur und zum Trainieren;
• Ein trainiertes Netzwerk kann in Ihrem Programm über eine C ++ - Schnittstelle verwendet werden (im Vergleich zum Python-Teil sehr schlecht, aber ausreichend, um vorgefertigte Netzwerke auszuführen).

Für Schulungen und andere schwere Computer wollten wir Nirvana verwenden - die wunderbare Yandex-Plattform , über die wir bereits gesprochen haben .

Datacet

Achtzig Prozent Erfolg bei der Arbeit mit einem neuronalen Netzwerk bestehen aus einem guten Datensatz. Für den Anfang hätten wir also einen solchen Datensatz zusammenstellen sollen. Yandex hat eine große Anzahl von Satellitenbildern mit bereits markierten Objekten. Alles scheint einfach zu sein: Laden Sie diese Daten einfach hoch und sammeln Sie sie in einem Datensatz. Es gibt jedoch eine Einschränkung.

Datensatz verfeinern

Wenn eine Person in einem Satellitenbild nach einem Haus sucht, sieht sie als erstes das Dach. Die Höhe der Häuser variiert jedoch, der Satellit kann dasselbe Gelände aus verschiedenen Winkeln aufnehmen - und wenn wir ein dem Dach entsprechendes Polygon auf einer Vektorkarte platzieren, gibt es keine Garantie dafür, dass das Dach beim Aktualisieren des Bildes nicht verlässt. Aber das Fundament wird in den Boden gegraben und bleibt aus jedem Winkel, den Sie abnehmen, die ganze Zeit an einem Ort. Deshalb sind die Häuser auf dem Vektor Yandex.Map "auf den Fundamenten" markiert. Dies ist richtig, aber für die Segmentierung von Bildern ist es besser, dem Netzwerk das Suchen nach Dächern beizubringen: Die Hoffnung, dass das Netzwerk darauf trainiert ist, die Fundamente zu erkennen, ist sehr gering. Daher sollte im Datensatz alles auf den Dächern markiert sein. Um einen guten Datensatz zu erstellen, müssen wir lernen, wie das Vektorlayout von Häusern von Fundamenten auf Dächer verschoben wird.

Wir haben versucht, uns nicht zu verschieben, aber die Qualität war nicht sehr gut, und das ist verständlich: Die Aufnahmewinkel des Satelliten sind unterschiedlich, die Höhen der Häuser sind unterschiedlich, daher wurde das Fundament auf den Fotos in verschiedene Richtungen und in unterschiedlichen Abständen vom Dach verschoben. Das Netzwerk geht durch eine solche Vielfalt verloren und trainiert bestenfalls für etwas dazwischen, im schlimmsten Fall für etwas Unverständliches. Darüber hinaus liefert das Netzwerk für die semantische Segmentierung ein Ergebnis, das einem akzeptablen ähnelt, aber bei der Suche nach Kanten sinkt die Qualität dramatisch.

Raster-Ansatz

Seit wir auf dem Gebiet der Computer Vision tätig sind, haben wir als erstes einen Ansatz ausprobiert, der für diese Computer Vision relevant ist. Zuerst wird die Vektorkarte gerastert (die Polygone der Häuser werden mit weißen Linien auf schwarzem Hintergrund gezeichnet), der Sobel-Filter wählt die Kanten im Satellitenbild aus. Und dann gibt es einen Versatz von zwei Bildern relativ zueinander, wodurch die Korrelation zwischen ihnen maximiert wird. Die Kanten nach dem Sobel-Filter sind ziemlich verrauscht. Wenn dieser Ansatz auf ein Gebäude angewendet wird, wird daher nicht immer ein akzeptables Ergebnis erzielt. Die Methode funktioniert jedoch gut in Gebieten mit Gebäuden gleicher Höhe: Wenn Sie sofort nach einem Versatz über einen großen Bereich des Bildes suchen, ist das Ergebnis stabiler.

"Geometrischer" Ansatz

Wenn das Gebiet nicht mit demselben Typ, sondern mit verschiedenen Häusern aufgebaut ist, funktioniert die vorherige Methode nicht. Glücklicherweise kennen wir manchmal die Höhe von Gebäuden auf der Yandex-Vektorkarte und die Position des Satelliten während der Aufnahme. Auf diese Weise können wir schulische Kenntnisse der Geometrie nutzen und berechnen, wo und in welcher Entfernung sich das Dach relativ zum Fundament bewegt. Diese Methode hat den Datensatz in Gebieten mit Hochhäusern verbessert.

"Manueller" Ansatz

Der zeitaufwändigste Weg: Krempeln Sie die Ärmel hoch, decken Sie die Maus auf, starren Sie auf den Monitor und verschieben Sie das Vektorlayout der Häuser manuell von den Fundamenten auf die Dächer. Die Technik führt zu einem Ergebnis, das von erstaunlicher Qualität ist, aber es wird nicht empfohlen, es in großen Mengen zu verwenden: Entwickler, die mit solchen Aufgaben beschäftigt sind, geraten schnell in Apathie und verlieren das Interesse am Leben.

Neuronales Netz

Am Ende haben wir genug Satellitenbilder, die auf den Dächern gut markiert sind. Es bestand also die Möglichkeit, das neuronale Netzwerk zu trainieren (vorerst jedoch nicht zur Segmentierung, sondern zur Verbesserung des Layouts anderer Satellitenbilder). Und wir haben es geschafft.

Die Eingabedaten des Faltungsnetzwerks waren ein Satellitenbild und eine verschobene rasterisierte Markierung. Am Ausgang erhielten wir einen zweidimensionalen Vektor: vertikale und horizontale Verschiebungen.


Mit Hilfe eines neuronalen Netzwerks fanden wir die notwendige Verschiebung, die es uns ermöglichte, gute Ergebnisse bei Gebäuden zu erzielen, für die die Höhe nicht angegeben ist. Infolgedessen haben wir die manuelle Markup-Korrektur erheblich reduziert.

Unterschiedliche Gebiete - unterschiedliche Häuser

Es gibt viele interessante Gebiete und Staaten auf Yandex.Maps. Aber auch in Russland sind die Häuser äußerst unterschiedlich, was sich auf das Aussehen in Satellitenbildern auswirkt. Sie müssen also die Vielfalt im Datensatz widerspiegeln. Und anfangs haben wir nicht wirklich verstanden, wie wir mit all dieser Pracht umgehen sollen. Einen riesigen Datensatz sammeln und dann ein Netzwerk darauf trainieren? Erstellen Sie Ihren eigenen Datensatz für jede (bedingte) Art der Entwicklung und trainieren Sie ein separates Netzwerk? Ein bestimmtes Kernnetzwerk trainieren und es dann für eine bestimmte Art von Entwicklung trainieren?


Empirisch fanden wir Folgendes:

1. Zweifellos ist es notwendig, den Datensatz für verschiedene Gebäudetypen zu erweitern, für die das Tool verwendet werden soll. Ein auf einen Typ geschultes Netzwerk kann Gebäude eines anderen Typs unterscheiden, wenn auch sehr schlecht.
2. Es ist besser, ein großes Netzwerk für den gesamten Datensatz zu trainieren. Es verallgemeinert sich recht gut auf verschiedene Gebiete. Wenn Sie für jede Art von Entwicklung separate Netzwerke trainieren, bleibt die Qualität entweder gleich oder verbessert sich kaum. Es ist daher sinnlos, unterschiedliche Netzwerke für unterschiedliche Gebiete zu implementieren. Darüber hinaus erfordert dies mehr Daten und einen zusätzlichen Klassifikator für die Art der Entwicklung.
3. Wenn Sie beim Hinzufügen neuer Gebiete zu den Daten alte Netzwerke verwenden, lernen die Netzwerke viel schneller. Die Umschulung alter Netzwerke in erweiterte Daten führt zu ungefähr dem gleichen Ergebnis wie das Training eines Netzwerks von Grund auf neu, erfordert jedoch viel weniger Zeit.

Lösungsoptionen

Semantische Segmentierung

Die semantische Segmentierung ist eine ziemlich gut erforschte Aufgabe. Nach dem Erscheinen des Artikels Fully Convolutional Networks wird dieser meist mithilfe neuronaler Netze gelöst. Es bleibt nur die Auswahl eines Netzwerks (wir haben FCN , SegNet und UNet in Betracht gezogen ), die Überlegung, ob wir zusätzliche Tricks wie CRF am Ausgang benötigen, und die Bestimmung, wie und mit welcher Fehlerfunktion das Training trainiert wird.


Infolgedessen haben wir uns für eine U-Net-ähnliche Architektur mit einer verallgemeinerten Intersection Over Union- Funktion als Fehlerfunktion entschieden. Für das Training schneiden wir Satellitenbilder und ihre entsprechenden Markierungen (natürlich gerastert) in Quadrate und setzen sie zu Datensätzen zusammen. Es stellte sich als ziemlich schön heraus und manchmal ganz gut.


In Gebieten mit einzelnen Gebäuden reichte die semantische Segmentierung aus, um zur nächsten Stufe überzugehen - der Vektorisierung. Wo das Gebäude dicht ist, kleben Häuser manchmal in einem zusammenhängenden Bereich zusammen. Es dauerte, um sie zu trennen.

Kantenerkennung

Um diese Aufgabe zu bewältigen, finden Sie die Kanten im Bild. Um Kanten zu erkennen, haben wir uns auch entschlossen, das Netzwerk zu trainieren (Kanten-Suchalgorithmen, die keine neuronalen Netzwerke verwenden, gehören eindeutig der Vergangenheit an). Schulung eines Netzwerks vom Typ HED, das unter Ganzheitlich verschachtelte Kantenerkennung beschrieben wird . Im Originalartikel wurde das Netzwerk auf den BSDS-500-Datensatz trainiert, in dem alle Kanten auf den Bildern markiert sind. Ein geschultes Netzwerk findet alle ausgeprägten Kanten: die Grenzen von Häusern, Straßen, Seen usw. Dies reicht bereits aus, um die nahe gelegenen Gebäude zu trennen. Wir haben uns jedoch entschlossen, weiter zu gehen und denselben Datensatz für das Training wie für die semantische Segmentierung zu verwenden. Malen Sie jedoch beim Rastern nicht die gesamten Polygone von Gebäuden, sondern zeichnen Sie nur deren Grenzen.

Das Ergebnis war so überwältigend schön, dass wir beschlossen, die Gebäude direkt an den vom Netzwerk empfangenen Kanten zu vektorisieren. Und es ist ganz passiert.

Scheitelpunkterkennung

Da ein Netzwerk wie HED an Kanten ein hervorragendes Ergebnis liefert, haben wir beschlossen, es so zu trainieren, dass es Scheitelpunkte erkennt. Tatsächlich haben wir ein Netzwerk mit allgemeinen Gewichten für Faltungsschichten. Sie hatte zwei Ausgänge gleichzeitig: für Kanten und für Spitzen. Infolgedessen haben wir eine andere Version der Gebäudevektorisierung erstellt, und in einigen Fällen wurden recht vernünftige Ergebnisse erzielt.

Maske r-cnn

Mask R-CNN ist eine relativ neue Erweiterung von Netzwerken wie Faster R-CNN. Maske R-CNN sucht nach Objekten und wählt für jedes eine Maske aus. Als Ergebnis erhalten wir für Häuser nicht nur Begrenzungsrechtecke, sondern auch eine raffinierte Struktur. Dieser Ansatz ist im Vergleich zu einer einfachen Erkennung (wir wissen nicht, wie sich das Gebäude innerhalb des Rechtecks ​​befindet) und einer normalen Segmentierung (mehrere Häuser können zu einem zusammenkleben, und es ist nicht klar, wie sie getrennt werden sollen) günstig. Mit Mask R-CNN müssen Sie nicht mehr über zusätzliche Tricks nachdenken: Es reicht aus, den Maskenrand für jedes Objekt zu vektorisieren und sofort das Ergebnis zu erhalten. Es gibt auch ein Minus: Die Größe der Maske für das Objekt ist immer festgelegt, d. H. Bei großen Gebäuden ist die Genauigkeit des Pixellayouts gering. Das Ergebnis von Mask R-CNN sieht folgendermaßen aus:


Wir haben zuletzt Mask R-CNN ausprobiert und sichergestellt, dass dieser Ansatz bei einigen Gebäudetypen andere übertrifft.

Vektorisierung

Rechteckvektorisierung

Bei aller modernen architektonischen Vielfalt sehen Häuser auf Satellitenbildern immer noch meistens wie Rechtecke aus. Darüber hinaus ist für die Masse der Gebiete eine Kennzeichnung mit komplexen Polygonen nicht erforderlich. Trotzdem möchte ich, dass Häuser auf der Karte markiert werden. (Nun, zum Beispiel eine Gartenbaupartnerschaft: Es gibt dort normalerweise viele Häuser, manuelles Markieren ist nicht so wichtig, aber das Markieren mit Rechtecken auf der Karte ist sehr gut.) Daher war der erste Ansatz zur Vektorisierung äußerst einfach.

1. Nehmen Sie die Rasterregion, die dem "Haus" entspricht.
2. Suchen Sie das Rechteck des Mindestbereichs, der diesen Bereich enthält (z. B. OpenCV :: minAreaRect ). Das Problem ist gelöst.

Es ist klar, dass die Qualität dieses Ansatzes alles andere als ideal ist. Der Algorithmus ist jedoch recht einfach und funktioniert in vielen Fällen.

Polygonvektorisierung

Wenn die Qualität der Segmentierung gut genug ist, können Sie die Kontur des Hauses genauer nachbilden. In den meisten Gebäuden mit komplexer Form sind die Winkel größtenteils richtig, daher haben wir beschlossen, das Problem auf die Aufgabe zu reduzieren, ein Polygon mit orthogonalen Seiten zu konstruieren. Um dies zu lösen, möchten wir zwei Ziele gleichzeitig erreichen: das einfachste Polygon finden und die Form von Gebäuden so genau wie möglich wiederholen. Diese Ziele stehen in Konflikt miteinander, daher müssen Sie zusätzliche Bedingungen einführen: um die minimale Länge der Wände, die maximale Abweichung von der Rasterregion usw. zu begrenzen.

Der Algorithmus, der uns zuerst einfiel, basierte auf der Konstruktion der Projektion von Punkten auf geraden Linien:

1. Finden Sie den Umriss der Rasterregion, die einem Haus entspricht.
2. Reduzieren Sie die Anzahl der Punkte in der Schaltung, indem Sie sie beispielsweise mit dem Douglas-Pecker-Algorithmus vereinfachen.
3. Finden Sie die längste Seite in der Gliederung. Es ist sein Neigungswinkel, der den Winkel des gesamten zukünftigen orthogonalen Polygons bestimmt.
4. Konstruieren Sie eine Projektion vom nächsten Konturpunkt zur vorherigen Seite.
5. Seite zum Projektionspunkt ausfahren. Wenn der Abstand vom Punkt zu seiner Projektion größer als die kürzeste Wand des Gebäudes ist, fügen Sie das resultierende Segment zur Kontur des Gebäudes hinzu.
6. Wiederholen Sie die Schritte 4 und 5, bis der Stromkreis schließt.

Dieser Algorithmus ist extrem einfach und bringt schnell Ergebnisse, aber die Kontur des Gebäudes ist manchmal ziemlich verrauscht. Bei dem Versuch, dieses Problem zu lösen, haben wir eine ziemlich interessante Lösung für das Problem gefunden, bei der ein quadratisches Gitter im Raum verwendet wird, um das Polygon zu approximieren. Kurz beschrieben besteht der Algorithmus aus drei Aktionen:

1. Erstellen Sie ein quadratisches Gitter im Raum, der auf Null zentriert ist.
2. Konstruieren Sie an Gitterpunkten, die nicht weiter als einen bestimmten Abstand von der ursprünglichen Kontur entfernt sind, verschiedene Polygone.
3. Wählen Sie ein Polygon mit einer Mindestanzahl von Scheitelpunkten aus.

Da der erforderliche Drehwinkel des Gitters nicht im Voraus bekannt ist, müssen mehrere Werte aussortiert werden, was sich negativ auf die Leistung auswirkt. Mit dem Algorithmus können Sie jedoch visuell schönere Ergebnisse erzielen.

Verbesserung der Vektorisierung

Während wir tatsächlich mit jedem Haus separat gearbeitet haben. Wenn die erste Phase abgeschlossen ist, können Sie bereits mit dem gesamten Bild arbeiten und das Ergebnis verbessern. Hierzu wurde ein Algorithmus zur Nachbearbeitung eines Satzes von Polygonen hinzugefügt. Wir haben folgende Heuristiken verwendet:

• Normalerweise sind die Wände benachbarter Häuser parallel. Außerdem: Meistens können Häuser zu Sets zusammengefasst werden, in denen alle Elemente ausgerichtet sind.
• Wenn auf dem Bild bereits Straßen markiert sind, ist es sehr wahrscheinlich, dass die Seiten der Polygone parallel zu den Straßen verlaufen.
• Wenn sich die Polygone schneiden, ist es höchstwahrscheinlich sinnvoll, die Wände so zu verschieben, dass der Schnitt verschwindet.

Als Ergebnis erschien der folgende Algorithmus:

1. Wir gruppieren die Häuser, die sich aus dem Abstand zwischen ihnen und dem Drehwinkel ergeben. Wir mitteln die Umdrehungen von Gebäuden in jedem Cluster. Wir wiederholen, bis sich die Position der Gebäude nicht mehr ändert oder bis die Häuser zu stark von der ursprünglichen Position abweichen.
2. Wir wählen Häuser in der Nähe der Straßen, wir finden die längsten und am nächsten an der Straßenseite. Wir drehen das Haus bis zur Parallelität der ausgewählten Seite und der Straße.
3. Wir entfernen die Schnittpunkte zwischen den Polygonen und verschieben die Seiten zweier sich kreuzender Gebäude proportional zur Größe der Seiten.

Ergebnis

Als Ergebnis haben wir ein Tool erhalten, das Gebäude verschiedener Gebäudetypen erkennen kann. Es hilft Kartographen bei ihrer harten Arbeit: Es beschleunigt die Suche nach vermissten Häusern erheblich und füllt neue, noch nicht bebaute Gebiete aus. Derzeit wurden mit diesem Tool mehr als 800.000 neue Objekte zur Personenkarte hinzugefügt.

Nachfolgend sehen Sie einige Beispiele für die Erkennung.