衛星画像を地図に変換する方法。 Yandexのコンピュータービジョン

Yandex.Mapsサービスの主なデータソースの1つは、衛星画像です。 地図を操作しやすくするため、写真では、森林、池、通り、家などのオブジェクトにポリゴンでマークが付けられています。 私たちは彼らを助け、人々の参加なしに家のポリゴンを追加するようコンピューターに教えることにしました。

コンピュータービジョンと呼ばれる、ITの責任領域である画像を使用した操作の場合。 過去数年にわたって、この分野のほとんどのタスクは、ニューラルネットワークを使用して非常にうまく解決されてきました。 今日は、マッピングでニューラルネットワークを使用した経験についてHabrの読者に伝えます。


まず、セマンティックセグメンテーションを行うニューラルグリッドをトレーニングします。つまり、衛星画像の各ポイントが家に関連しているかどうかを判断します。 オブジェクト検出だけでなくセマンティックセグメンテーションが必要なのはなぜですか？ 検出の問題が解決されると、出力で一連の長方形が得られます。さらに具体的には、2つの辺が垂直で、2つの辺が水平になります。 また、家は通常、画像軸に対して回転します。一部の建物も複雑な形状をしています。

セマンティックセグメンテーションのタスクは、現在、さまざまなネットワーク（ FCN 、 SegNet 、 UNetなど）によって解決されています。 あなたは私たちにとって最適なものを選択する必要があります。

衛星画像からマスクを受け取ったら、家に属するポイントの十分に大きなクラスターを選択し、それらを接続エリアに収集し、エリアの境界を多角形のベクター形式で提示します。

マスクが完全に正確ではないことは明らかです。つまり、近くの家が1つの接続された領域で互いにくっつくことがあります。 この問題に対処するために、ネットワークをさらにトレーニングすることにしました。 彼女は画像でrib骨（家の境界）を見つけ、接着された建物を分離します。

それで、そのようなスキームが迫りました：


検出ネットワークを完全に破棄することはせず、 Mask R-CNNを試しました。 通常のセグメンテーションと比較すると、マスクR-CNNはオブジェクトを検出してマスクを生成するため、共通のマスクを接続エリアに分割する必要はありません。 さて、各オブジェクトのマスクの固定解像度のマイナス（それなしの場合）、つまり、複雑な境界線を持つ大きな家の場合、この境界線は明らかに単純化されます。

ツール

次に、ツールを決定する必要がありました。 ここではすべてが明白でした。OpenCVはコンピュータービジョンタスクに最適です。 ニューラルネットワークの選択はいくぶん幅があります。 Tensorflowに決めました。 その利点：

• ネットワークを組み立てることができる、かなり開発された既製の「キューブ」セット。
• ネットワーク構造の迅速な作成とトレーニングに便利なPython API。
• トレーニング済みのネットワークは、C ++インターフェイスを介してプログラムで使用できます（Pythonの部分と比較すると非常に貧弱ですが、既製のネットワークを実行するには十分です）。

トレーニングやその他のヘビーコンピューティングのために、 既に説明した素晴らしいYandexプラットフォームである Nirvanaを使用することを計画しました。

データセット

ニューラルネットワークでの作業の80％の成功は、優れたデータセットで構成されています。 したがって、まず最初に、このようなデータセットを組み立てる必要があります。 Yandexには、すでにマークされたオブジェクトを含む膨大な数の衛星画像があります。 すべてが単純なようです。このデータをアップロードして、データセットに収集するだけです。 ただし、注意点が1つあります。

データセットの洗練

人が衛星画像で家を検索するとき、最初に行うことは屋根に気づくことです。 しかし、家の高さはさまざまであり、衛星は異なる角度から同じ地形を取ることができます。また、ベクトルマップに屋根に対応するポリゴンを配置すると、画像が更新されたときに屋根が離れないという保証はありません。 しかし、土台は地面に掘られており、どんな角度からでもそれをどこからでも、常に1か所に残っています。 そのため、ベクターYandex.Mapの家は「基礎上」とマークされています。 これは正しいですが、画像をセグメント化するタスクでは、屋根を検索するようネットワークに教える方が良いです。ネットワークが基礎を認識するように訓練されるという希望は非常に小さいです。 したがって、データセットでは、すべてを屋根にマークする必要があります。 したがって、優れたデータセットを作成するには、家のベクターレイアウトを基礎から屋根にシフトする方法を学ぶ必要があります。

移動させないようにしましたが、品質はあまり良くありませんでした。これは理解できます。衛星の撮影角度が異なり、家の高さが異なるため、写真では基礎が異なる方向に、屋根から異なる距離に移動しました。 ネットワークはそのような多様性から失われ、せいぜい、その間の何かのために、最悪の場合、理解できない何かのために訓練します。 さらに、セマンティックセグメンテーションのネットワークは、許容可能なものと同様の結果を生成しますが、エッジを検索すると、品質が劇的に低下します。

ラスターアプローチ

コンピュータービジョンの分野に入ったので、最初にしたことは、このコンピュータービジョンに関連するアプローチを試すことでした。 最初に、ベクトルマップがラスタライズされ（家のポリゴンが黒い背景に白い線で描かれます）、 Sobelフィルターが衛星画像のエッジを選択します。 また、2つの画像の相対的なオフセットがあり、これらの画像間の相関が最大になります。 Sobelフィルターの後のエッジは非常にノイズが多いため、このアプローチを1つの建物に適用すると、常に許容できる結果が得られるとは限りません。 ただし、この方法は同じ高さの建物がある地域でうまく機能します。画像の広い領域ですぐにオフセットを探すと、結果はより安定します。

「幾何学的」アプローチ

テリトリーが同じタイプではなく、さまざまな家で構築されている場合、以前の方法は機能しません。 幸い、Yandexベクトルマップ上の建物の高さと、撮影中の衛星の位置がわかっている場合があります。 したがって、幾何学の学校の知識を使用して、屋根が基礎に対してどこでどの距離を移動するかを計算できます。 この方法により、高層ビルのある地域のデータセットが改善されました。

「手動」アプローチ

最も時間のかかる方法：袖をまくり、マウスを覆い、モニターを見つめ、家のベクトルレイアウトを基礎から屋根に手動で移動します。 この手法は、驚くほどの品質の結果をもたらしますが、大量に使用することはお勧めしません。そのようなタスクに従事している開発者は、すぐに無関心になり、人生への関心を失います。

ニューラルネットワーク

最終的に、屋根の上に十分にマークされた十分な衛星画像を取得しました。 そのため、ニューラルネットワークをトレーニングする機会がありました（ただし、現時点では、セグメンテーションではなく、他の衛星画像のレイアウトを改善します）。 そしてそれをやった。

畳み込みニューラルネットワーク入力は、衛星画像とオフセットラスタライズマーキングでした。 出力では、垂直方向と水平方向の変位という2次元のベクトルを受け取りました。


ニューラルネットワークの助けを借りて、必要な変位を見つけました。これにより、高さが示されていない建物で良好な結果を得ることができました。 その結果、手動のマークアップ修正を大幅に削減しました。

異なる地域-異なる家

Yandex.Mapsには、多くの興味深い地域と州があります。 しかし、ロシアでも、家は非常に多様であり、衛星画像での外観に影響します。 したがって、データセットに多様性を反映する必要があります。 さらに、最初は、このすべての素晴らしさに対処する方法を本当に理解していませんでした。 巨大なデータセットを収集してから、1つのネットワークをトレーニングしますか？ 開発の（条件付き）タイプごとに独自のデータセットを作成し、個別のネットワークをトレーニングしますか？ 特定のコアネットワークをトレーニングしてから、特定のタイプの開発向けにトレーニングしますか？


経験的に、次のことがわかりました。

1. 間違いなく、ツールの使用が計画されているさまざまな種類の建物のデータセットを拡張する必要があります。 あるタイプでトレーニングされたネットワークは、非常に貧弱ですが、別のタイプの建物を区別することができます。
2. データセット全体で1つの大きなネットワークをトレーニングすることをお勧めします。 さまざまな地域に非常によく一般化されます。 開発の種類ごとに個別のネットワークをトレーニングする場合、品質は同じままか、ほとんど向上しません。 したがって、地域ごとに異なるネットワークを実装するのは無意味です。 さらに、これには、より多くのデータと、開発タイプの追加の分類子が必要です。
3. データに新しい領域を追加するときに古いネットワークを使用すると、ネットワークの学習速度が大幅に向上します。 拡張データで古いネットワークを再トレーニングすると、ネットワークをゼロから学習するのとほぼ同じ結果になりますが、必要な時間ははるかに短くなります。

ソリューションオプション

セマンティックセグメンテーション

セマンティックセグメンテーションは、かなりよく研究されたタスクです。 Fully Convolutional Networksの記事が登場した後、ほとんどはニューラルネットワークを使用して解決されます。 ネットワーク（ FCN 、 SegNet 、およびUNetを調べました ）を選択し、出力でCRFのような追加のトリックが必要かどうかを検討し、トレーニングがどのエラー関数でトレーニングされるかを決定するだけです。


その結果、 一般化されたIntersection Over Union関数をエラー関数として使用したU-Netのようなアーキテクチャに落ち着きました。 トレーニングのために、衛星画像とそれに対応するマーキング（自然にラスタライズされた）を正方形に切り取り、データセットに収集しました。 それはかなり良いことが判明し、時にはうまくいきました。


単一の建物がある地域では、セマンティックセグメンテーションは次の段階であるベクトル化に移行するのに十分でした。 建物が密集している場所では、住宅は粘着性のあるエリアでつまっていることがあります。 それらを分離するのにかかった。

エッジ検出

このタスクに対処するために、画像内のエッジを見つけることができます。 エッジを検出するために、ネットワークをトレーニングすることも決定しました（ニューラルネットワークを使用しないエッジ検索アルゴリズムは明らかに過去のものです）。 タイプHEDのネットワークをトレーニングしました。これについては、「 全体的にネストされたエッジ検出」で説明しています。 元の記事では、ネットワークはBSDS-500データセットでトレーニングされており、すべてのエッジが画像にマークされています。 訓練されたネットワークは、家、道路、湖などの境界など、すべての顕著なエッジを検出します。これはすでに近くの建物を分離するのに十分です。 しかし、さらに進んで、セマンティックセグメンテーションと同じデータセットをトレーニングに使用することにしましたが、ラスター化するときは、建物のポリゴン全体をペイントせず、境界のみを描画します。

結果は非常に美しいため、ネットワークから受け取ったエッジによって建物を直接ベクトル化することにしました。 そして、それはかなり起こりました。

頂点検出

HEDのようなネットワークはエッジで優れた結果をもたらしたため、頂点を検出するようにトレーニングすることにしました。 実際、畳み込み層に一般的な重みを持つネットワークがあります。 彼女には同時に2つの出口がありました。エッジ用とピーク用です。 その結果、建物のベクトル化の別のバージョンを作成し、場合によっては非常に健全な結果を示しました。

マスクr-cnn

マスクR-CNNは、Faster R-CNNなどの比較的新しいネットワークの拡張です。 マスクR-CNNはオブジェクトを検索し、オブジェクトごとにマスクを選択します。 その結果、住宅の場合、境界を示す四角形だけでなく、洗練された構造も得られます。 このアプローチは、単純な検出（建物が長方形内にどのように配置されているかはわかりません）および通常のセグメンテーション（複数の家が1つにまとめることができ、それらを分離する方法が明確ではありません）と比べて有利です。 Mask R-CNNを使用すると、追加のトリックについて考える必要がなくなります。各オブジェクトのマスク境界をベクトル化し、すぐに結果を取得します。 マイナスもあります。オブジェクトのマスクのサイズは常に固定されています。つまり、大きな建物の場合、ピクセルレイアウトの精度は低くなります。 Mask R-CNNの結果は次のようになります。


最後にMask R-CNNを試し、一部のタイプの建物ではこのアプローチが他のパフォーマンスよりも優れていることを確認しました。

ベクトル化

長方形のベクトル化

現代のすべての建築の多様性により、衛星画像上の家は依然としてほとんどの場合長方形のように見えます。 さらに、多数のテリトリーの場合、複雑なポリゴンでマーキングする必要はありません。 しかし、それでも地図上の家に印を付けたい。 （たとえば、園芸パートナーシップ：通常、そこには多くの家があります。手動でマークアップすることはそれほど重要ではありませんが、地図上の長方形でマークすることは非常に良いことです。）したがって、ベクトル化の最初のアプローチは非常に簡単でした。

1. 「家」に対応するラスタ領域を取得します。
2. この領域を含む最小領域の長方形を見つけます（たとえば、次のように： OpenCV :: minAreaRect ）。 問題は解決しました。

このアプローチの品質が理想からかけ離れていることは明らかです。 ただし、アルゴリズムは非常にシンプルで、多くの場合機能します。

ポリゴンのベクトル化

セグメンテーションの品質が十分であれば、家の輪郭をより正確に再現できます。 複雑な形状のほとんどの建物では、角度はほとんど正しいので、直交する辺を持つ多角形を構築するタスクに問題を減らすことにしました。 それを解決するために、2つの目標を一度に達成します。最も単純なポリゴンを見つけ、建物の形状をできるだけ正確に繰り返すことです。 これらの目標は互いに競合するため、追加の条件を導入する必要があります。壁の最小長さ、ラスター領域からの最大偏差などを制限するためです。

私たちが最初に思いついたアルゴリズムは、直線上の点の投影の構築に基づいていました。

1. 1つの家に対応するラスター領域の輪郭を見つけます。
2. ダグラスペッカーアルゴリズムなどを使用して、回路を単純化することにより、回路内のポイント数を減らします 。
3. アウトラインで最も長い辺を見つけます。 将来の直交ポリゴン全体の角度を決定するのは、その傾斜角です。
4. 次の輪郭点から前の側への投影を作成します。
5. 側面を投影点まで延長します。 ポイントからその投影までの距離が建物の最短壁よりも大きい場合、結果のセグメントを建物の輪郭に追加します。
6. 回路が閉じるまで、手順4と5を繰り返します。

このアルゴリズムは非常に単純で、すぐに結果が得られますが、それでも建物の輪郭が非常にうるさいことがわかります。 この問題に対処しようとして、この問題のかなり興味深い解決策に出会いました。これは、空間内の正方形グリッドを使用してポリゴンを近似するものです。 簡単に説明すると、アルゴリズムは3つのアクションで構成されています。

1. ゼロを中心とした空間に正方形のグリッドを作成します。
2. 元の輪郭から少し離れた位置にあるグリッドポイントで、異なるポリゴンを作成します。
3. 頂点の数が最小のポリゴンを選択します。

グリッドの必要な回転角度は事前にわかっていないため、いくつかの値を整理する必要があり、パフォーマンスにほとんど影響しません。 ただし、このアルゴリズムにより、視覚的に美しい結果を得ることができます。

ベクトル化の改善

私たちは実際にそれぞれの家で別々に働いていましたが。 最初の段階が完了すると、画像全体を既に使用して結果を改善できます。 これを行うために、一連のポリゴンに対する後処理アルゴリズムが追加されました。 次のヒューリスティックを使用しました。

• 通常、隣接する家の壁は平行です。 さらに、ほとんどの場合、家はセットに結合され、その中にすべての要素が配置されます。
• 画像上で道路がすでにマークされている場合、ポリゴンの側面が道路と平行になる可能性が非常に高くなります。
• ポリゴンが交差する場合は、おそらく、交差点が消えるように壁を移動するのが理にかなっています。

その結果、次のアルゴリズムが登場しました。

1. 私たちは、それらの間の距離と回転角度によって見つかった家をクラスター化します。 各クラスターの建物の回転を平均します。 建物の位置が変化しなくなるまで、または家が初期位置から大きく外れ始めるまで繰り返します。
2. 道路の近くに家を選び、道路側に最も長くて最も近い家を見つけます。 家を、選択した側と道路の平行度まで上げます。
3. ポリゴン間の交差を削除し、交差する2つの建物の辺を辺のサイズに比例してシフトします。

結果

その結果、さまざまな種類の建物を認識できるツールを手に入れました。 これは、地図製作者の大変な作業に役立ちます。行方不明の家の検索を大幅に高速化し、まだ耕作されていない新しいエリアを埋めます。 現時点では、このツールを使用して800,000以上の新しいオブジェクトが人民マップに追加されています。

以下に、認識の例をいくつか示します。