Salah satu sumber data utama untuk layanan Yandex.Maps adalah citra satelit. Agar mudah digunakan dengan peta, objek ditandai dengan poligon dalam gambar: hutan, kolam, jalan, rumah, dll. Biasanya, kartografer terlibat dalam penandaan. Kami memutuskan untuk membantu mereka dan mengajarkan komputer untuk menambahkan poligon rumah tanpa partisipasi orang.
Untuk operasi dengan gambar memenuhi bidang TI, yang disebut visi komputer. Selama beberapa tahun terakhir, sebagian besar tugas di bidang ini telah sangat berhasil diselesaikan menggunakan jaringan saraf. Hari ini kami akan memberi tahu pembaca Habr tentang pengalaman kami menggunakan jaringan saraf dalam pemetaan.
Pertama-tama, kita akan melatih grid saraf yang akan terlibat dalam segmentasi semantik, yaitu, akan menentukan apakah setiap titik dalam citra satelit terkait dengan rumah. Mengapa segmentasi semantik dan bukan hanya deteksi objek? Ketika masalah pendeteksian diselesaikan, kita akan mendapatkan satu set persegi panjang keluaran, lebih spesifik: dua sisi vertikal, dua horisontal. Dan rumah biasanya diputar relatif terhadap sumbu gambar, dan beberapa bangunan juga memiliki bentuk yang kompleks.
Tugas segmentasi semantik sekarang sedang diselesaikan oleh berbagai jaringan (
FCN ,
SegNet ,
UNet , dll.). Anda hanya perlu memilih mana yang terbaik untuk kami.
Setelah menerima topeng dari citra satelit, kami memilih kelompok titik yang cukup besar milik rumah-rumah, mengumpulkannya di area yang terhubung dan menyajikan batas-batas area dalam bentuk vektor dalam bentuk poligon.
Jelas bahwa topeng itu tidak akan sepenuhnya akurat, yang berarti bahwa rumah-rumah di dekatnya dapat tetap bersatu dalam satu area yang terhubung. Untuk mengatasi masalah ini, kami memutuskan untuk lebih lanjut melatih jaringan. Dia akan menemukan dalam gambar tulang rusuk (batas-batas rumah) dan memisahkan bangunan yang direkatkan.
Jadi, skema seperti itu tampak:
Kami tidak sepenuhnya membuang jaringan deteksi dan mencoba
Mask R-CNN . Kelebihannya dibandingkan dengan segmentasi biasa adalah bahwa Mask R-CNN mendeteksi objek dan menghasilkan topeng, sehingga tidak perlu mengotak-atik pembagian topeng umum ke dalam area yang terhubung. Nah, minus (seperti tanpa itu) dalam resolusi tetap topeng setiap objek, yaitu, untuk rumah besar dengan perbatasan kompleks, perbatasan ini jelas akan berubah menjadi disederhanakan.
Alat-alatnya
Maka itu perlu untuk memutuskan alat. Semuanya sangat jelas di sini:
OpenCV paling cocok untuk tugas-tugas visi komputer. Pilihan jaringan saraf agak lebih luas. Kami menetap di
Tensorflow . Keuntungannya:
- satu set “kubus” siap pakai yang dikembangkan dari mana Anda dapat mengumpulkan jaringan Anda;
- Python API, mudah untuk membuat struktur jaringan dan pelatihan dengan cepat;
- Jaringan terlatih dapat digunakan dalam program Anda melalui antarmuka C ++ (sangat buruk dibandingkan dengan bagian Python, tetapi cukup memadai untuk menjalankan jaringan yang sudah jadi).
Untuk pelatihan dan komputasi berat lainnya, kami berencana untuk menggunakan Nirvana - platform Yandex yang luar biasa
yang telah kami bicarakan .
Datacet
Keberhasilan delapan puluh persen dalam bekerja dengan jaringan saraf terdiri dari dataset yang baik. Jadi, sebagai permulaan, kita harus mengumpulkan dataset seperti itu. Yandex memiliki sejumlah besar gambar satelit dengan objek yang sudah ditandai. Segalanya tampak sederhana: cukup unggah data ini dan kumpulkan dalam dataset. Namun, ada satu peringatan.
Saring dataset
Ketika seseorang mencari rumah dalam citra satelit, hal pertama yang dilihatnya adalah atap. Tetapi ketinggian rumah bervariasi, satelit dapat mengambil medan yang sama dari sudut yang berbeda - dan jika kita menempatkan poligon yang sesuai dengan atap pada peta vektor, tidak ada jaminan bahwa atap tidak akan pergi ketika gambar diperbarui. Tetapi fondasi digali ke tanah dan, dari sudut mana pun Anda melepasnya, semua waktu tetap di satu tempat. Itulah sebabnya rumah-rumah pada vektor Yandex.Map ditandai "pada fondasi." Ini benar, tetapi untuk tugas segmentasi gambar, lebih baik mengajarkan jaringan untuk mencari atap: harapan bahwa jaringan dilatih untuk mengenali fondasi sangat kecil. Oleh karena itu, dalam dataset semuanya harus ditandai di atap. Jadi, untuk membuat dataset yang baik, kita perlu belajar bagaimana mengubah tata letak vektor rumah dari fondasi ke atap.
Kami mencoba untuk tidak bergeser, tetapi kualitasnya tidak terlalu bagus, dan ini dapat dimengerti: sudut pengambilan gambar satelit berbeda, ketinggian rumah berbeda, akibatnya, dalam foto-foto fondasi bergeser ke arah yang berbeda dan pada jarak yang berbeda dari atap. Jaringan hilang dari variasi seperti itu dan, paling-paling, melatih sesuatu di antaranya, paling buruk - untuk sesuatu yang tidak dapat dipahami. Selain itu, jaringan untuk segmentasi semantik menghasilkan hasil yang mirip dengan sesuatu yang dapat diterima, tetapi ketika mencari tepi, kualitasnya menurun secara dramatis.Pendekatan raster
Sejak kami masuk ke bidang visi komputer, hal pertama yang kami lakukan adalah mencoba pendekatan yang relevan dengan visi komputer ini. Pertama, peta vektor dirasterisasi (poligon rumah digambar dengan garis putih pada latar belakang hitam),
filter Sobel memilih tepi pada gambar satelit. Dan kemudian ada offset dari dua gambar relatif satu sama lain, yang memaksimalkan korelasi di antara mereka. Tepi setelah filter Sobel cukup berisik, oleh karena itu, jika pendekatan ini diterapkan pada satu bangunan, hasil yang dapat diterima tidak selalu diperoleh. Namun, metode ini bekerja dengan baik di wilayah dengan bangunan dengan ketinggian yang sama: jika Anda mencari offset segera di area gambar yang besar, hasilnya akan lebih stabil.
Pendekatan "Geometrik"
Jika wilayah tersebut dibangun bukan dengan tipe yang sama, tetapi dengan berbagai rumah, metode sebelumnya tidak akan berfungsi. Untungnya, kadang-kadang kita mengetahui ketinggian bangunan di peta vektor Yandex dan posisi satelit selama pemotretan. Dengan demikian, kita dapat menggunakan pengetahuan sekolah tentang geometri dan menghitung di mana dan pada jarak berapa atap akan bergerak relatif terhadap fondasi. Metode ini telah meningkatkan dataset di area dengan bangunan bertingkat tinggi.
Pendekatan "manual"
Cara yang paling memakan waktu: menyingsingkan lengan baju Anda, membuka mouse, menatap monitor dan secara manual menggeser tata letak vektor rumah-rumah dari fondasi ke atap. Teknik ini membawa hasil yang luar biasa dalam kualitas, tetapi tidak disarankan untuk menggunakannya dalam jumlah besar: pengembang yang terlibat dalam tugas-tugas seperti itu dengan cepat jatuh ke dalam sikap apatis dan kehilangan minat dalam hidup.
Jaringan saraf
Pada akhirnya, kami mendapat citra satelit yang cukup, ditandai dengan baik di atap. Jadi, ada kesempatan untuk melatih jaringan saraf (untuk saat ini, bukan untuk segmentasi, tetapi untuk meningkatkan tata letak gambar satelit lainnya). Dan kami berhasil.
Data input dari jaringan saraf convolutional adalah citra satelit dan tanda raster yang digeser. Pada output, kami menerima vektor dua dimensi: perpindahan vertikal dan horisontal.
Dengan bantuan jaringan saraf, kami menemukan perpindahan yang diperlukan, yang memungkinkan kami mencapai hasil yang baik pada bangunan yang ketinggiannya tidak ditunjukkan. Akibatnya, kami secara signifikan mengurangi koreksi markup manual.
Wilayah berbeda - beda rumah
Ada banyak wilayah dan negara yang menarik di Yandex.Maps. Tetapi bahkan di Rusia, rumah sangat beragam, yang memengaruhi penampilannya dalam citra satelit. Jadi, Anda harus mencerminkan keragaman dalam dataset. Dan awalnya kami tidak benar-benar mengerti bagaimana cara mengatasi semua kemegahan ini. Kumpulkan dataset besar dan latih satu jaringan di atasnya? Buat dataset Anda sendiri untuk setiap jenis pengembangan (kondisional) dan latih jaringan yang terpisah? Melatih jaringan inti tertentu dan kemudian melatihnya untuk jenis pengembangan tertentu?
Secara empiris, kami menemukan bahwa:
- Tidak diragukan lagi, perlu untuk memperluas dataset untuk berbagai jenis bangunan yang direncanakan untuk menggunakan alat ini. Sebuah jaringan yang dilatih pada satu jenis mampu membedakan bangunan dari jenis lain, meskipun sangat buruk.
- Lebih baik melatih satu jaringan besar di seluruh kumpulan data. Ini menggeneralisasi dengan cukup baik ke berbagai wilayah. Jika Anda melatih jaringan yang terpisah untuk setiap jenis pengembangan, kualitasnya akan tetap sama atau hampir tidak membaik. Jadi tidak ada gunanya menerapkan jaringan yang berbeda untuk wilayah yang berbeda. Selain itu, ini membutuhkan lebih banyak data dan tambahan jenis pengembangan.
- Jika Anda menggunakan jaringan lama saat menambahkan wilayah baru ke data, jaringan akan belajar lebih cepat. Pelatihan ulang jaringan lama pada data yang diperluas mengarah ke hasil yang kira-kira sama dengan melatih jaringan dari awal, tetapi membutuhkan waktu yang jauh lebih sedikit.
Opsi solusi
Segmentasi semantik
Segmentasi semantik adalah tugas yang diteliti dengan cukup baik. Setelah munculnya artikel
Jaringan Sepenuhnya Konvolusional , sebagian besar diselesaikan dengan menggunakan jaringan saraf. Yang tersisa hanyalah memilih jaringan (kami anggap
FCN ,
SegNet , dan
UNet ), pikirkan apakah kami membutuhkan trik tambahan seperti CRF di output, dan putuskan bagaimana dan dengan fungsi kesalahan apa pelatihan akan dilatih.
Sebagai hasilnya, kami memilih arsitektur seperti U-Net dengan fungsi
Intersection Over Union yang digeneralisasi sebagai fungsi kesalahan. Untuk pelatihan, kami memotong gambar satelit dan tanda-tanda yang sesuai (tentu saja, di-raster) menjadi kotak dan dikumpulkan menjadi kumpulan data. Ternyata cukup bagus, dan terkadang baik-baik saja.
Di wilayah dengan bangunan tunggal, segmentasi semantik sudah cukup untuk beralih ke tahap berikutnya - vektorisasi. Di mana bangunannya padat, rumah-rumah kadang-kadang saling menempel di area yang kohesif. Butuh untuk memisahkan mereka.
Deteksi tepi
Untuk mengatasi tugas ini, Anda dapat menemukan tepi pada gambar. Untuk mendeteksi tepi, kami juga memutuskan untuk melatih jaringan (algoritme pencarian tepi yang tidak menggunakan jaringan saraf jelas merupakan sesuatu dari masa lalu). Melatih jaringan tipe HED, yang dijelaskan dalam
Deteksi Tepi Bersarang Secara Holistik . Dalam artikel asli, jaringan dilatih pada set data BSDS-500, di mana semua tepi ditandai pada gambar. Sebuah jaringan yang terlatih menemukan semua sisi yang menonjol: batas-batas rumah, jalan, danau, dll. Ini sudah cukup untuk memisahkan bangunan di dekatnya. Tetapi kami memutuskan untuk melangkah lebih jauh dan menggunakan dataset yang sama untuk pelatihan seperti segmentasi semantik, tetapi ketika melakukan rasterisasi, jangan mengecat seluruh poligon bangunan, tetapi hanya menggambar batas-batasnya.
Hasilnya sangat indah sehingga kami memutuskan untuk membuat vektor bangunan secara langsung dengan tepian yang diterima dari jaringan. Dan itu terjadi begitu saja.
Deteksi vertex
Karena jaringan seperti HED memberikan hasil yang sangat baik di tepi, kami memutuskan untuk melatihnya untuk mendeteksi simpul. Faktanya, kami memiliki jaringan dengan bobot umum pada lapisan konvolusional. Dia memiliki dua pintu keluar pada saat yang sama: untuk tepi dan untuk puncak. Sebagai hasilnya, kami membuat versi lain dari vektorisasi bangunan, dan dalam beberapa kasus menunjukkan hasil yang cukup waras.
Topeng r-cnn
Mask R-CNN adalah perluasan jaringan yang relatif baru seperti F-R-CNN yang lebih cepat. Masker R-CNN mencari objek dan memilih topeng untuk masing-masing. Akibatnya, untuk rumah-rumah kita tidak hanya mengikat persegi panjang, tetapi juga struktur halus. Pendekatan ini lebih baik dibandingkan dengan deteksi sederhana (kami tidak tahu bagaimana bangunan itu berada di dalam persegi panjang) dan segmentasi normal (beberapa rumah dapat saling menempel menjadi satu, dan tidak jelas bagaimana memisahkannya). Dengan Mask R-CNN, Anda tidak perlu lagi memikirkan trik tambahan: cukup untuk membuat vektor batas mask untuk setiap objek dan segera mendapatkan hasilnya. Ada juga minus: ukuran topeng untuk objek selalu diperbaiki, mis. Untuk bangunan besar, akurasi tata letak piksel akan rendah. Hasil dari Mask R-CNN terlihat seperti ini:
Kami mencoba Mask R-CNN yang terakhir dan memastikan bahwa untuk beberapa jenis bangunan pendekatan ini mengungguli yang lain.
Vektorisasi
Vektorisasi Persegi Panjang
Dengan semua keragaman arsitektur modern, rumah-rumah pada citra satelit masih paling sering terlihat seperti persegi panjang. Selain itu, untuk massa wilayah, penandaan dengan poligon kompleks tidak diperlukan. Tapi saya tetap ingin rumah di peta ditandai. (Ya, misalnya, kemitraan hortikultura: biasanya ada banyak rumah di sana, penandaan secara manual tidak begitu penting, tetapi penandaan dengan persegi panjang pada peta sangat baik.) Oleh karena itu, pendekatan pertama untuk vektorisasi sangat sederhana.
- Ambil wilayah raster yang sesuai dengan "rumah".
- Temukan persegi panjang area minimum yang berisi area ini (misalnya, seperti ini: OpenCV :: minAreaRect ). Masalahnya terpecahkan.
Jelas bahwa kualitas pendekatan ini jauh dari ideal. Namun, algoritma ini cukup sederhana dan dalam banyak kasus berfungsi.
Vektorisasi Poligon
Jika kualitas segmentasi cukup baik, Anda dapat membuat ulang kontur rumah dengan lebih akurat. Pada sebagian besar bangunan dengan bentuk kompleks, sudut sebagian besar benar, jadi kami memutuskan untuk mengurangi masalah menjadi tugas membangun poligon dengan sisi ortogonal. Memecahkannya, kami ingin mencapai dua tujuan sekaligus: untuk menemukan poligon paling sederhana dan mengulangi bentuk bangunan seakurat mungkin. Sasaran-sasaran ini saling bertentangan, jadi Anda harus memperkenalkan kondisi tambahan: untuk membatasi panjang minimum dinding, deviasi maksimum dari wilayah raster, dll.
Algoritma yang pertama kali terjadi pada kita didasarkan pada konstruksi proyeksi titik pada garis lurus:
- Temukan garis besar wilayah raster yang sesuai dengan satu rumah.
- Kurangi jumlah titik dalam rangkaian dengan menyederhanakannya, misalnya, dengan algoritma Douglas-Pecker .
- Temukan sisi terpanjang di garis besar. Ini adalah sudut kemiringannya yang akan menentukan sudut seluruh poligon ortogonal di masa depan.
- Buatlah proyeksi dari titik kontur berikutnya ke sisi sebelumnya.
- Perpanjang sisi ke titik proyeksi. Jika jarak dari titik ke proyeksi lebih besar dari dinding terpendek bangunan, tambahkan segmen yang dihasilkan ke kontur bangunan.
- Ulangi langkah 4 dan 5 hingga sirkuit ditutup.
Algoritma ini sangat sederhana dan cepat membawa hasil, tetapi kontur bangunan terkadang berubah menjadi sangat berisik. Mencoba untuk mengatasi masalah ini, kami menemukan solusi yang agak menarik
untuk masalah ini, yang menggunakan kotak persegi di ruang untuk memperkirakan poligon. Dijelaskan secara singkat, algoritma terdiri dari tiga tindakan:
- Bangun kisi persegi di ruang yang berpusat pada nol.
- Pada titik grid yang terletak tidak jauh dari jarak tertentu dari kontur asli, buat poligon yang berbeda.
- Pilih poligon dengan jumlah simpul minimum.
Karena sudut rotasi yang diperlukan dari grid tidak diketahui sebelumnya, maka perlu untuk memilah beberapa nilai, yang mempengaruhi kinerja dengan buruk. Namun, algoritma ini memungkinkan Anda untuk mencapai hasil yang lebih indah secara visual.
Peningkatan Vektorisasi
Padahal kami benar-benar bekerja dengan masing-masing rumah secara terpisah. Ketika tahap pertama selesai, Anda sudah dapat bekerja dengan gambar secara keseluruhan dan meningkatkan hasilnya. Untuk ini, sebuah algoritma untuk pasca-pemrosesan serangkaian poligon telah ditambahkan. Kami menggunakan heuristik berikut:
- Biasanya dinding rumah yang berdekatan sejajar. Selain itu: paling sering, rumah dapat digabungkan menjadi set, di mana semua elemen disejajarkan.
- Jika jalan sudah ditandai pada gambar, maka sangat mungkin bahwa sisi poligon akan sejajar dengan jalan.
- Jika poligon berpotongan, maka kemungkinan besar masuk akal untuk memindahkan dinding sehingga persimpangan menghilang.
Akibatnya, algoritma berikut ini muncul:
- Kami mengelompokkan rumah-rumah yang ditemukan oleh jarak antara mereka dan sudut rotasi. Kami rata-rata pergantian bangunan di setiap kluster. Kami ulangi sampai posisi bangunan berhenti berubah atau sampai rumah mulai menyimpang terlalu banyak dari posisi awal.
- Kami memilih rumah di dekat jalan, kami menemukan yang terpanjang dan terdekat dengan sisi jalan. Kami mengubah rumah ke paralelisme sisi yang dipilih dan jalan.
- Kami menghapus persimpangan antara poligon, menggeser sisi dua bangunan yang berpotongan secara proporsional dengan ukuran sisi.
Hasil
Hasilnya, kami mendapat alat yang bisa mengenali bangunan dari berbagai jenis bangunan. Ini membantu para kartografer dalam kerja keras mereka: mempercepat pencarian rumah yang hilang dan mengisi daerah baru yang belum diolah. Saat ini, lebih dari 800 ribu objek baru telah ditambahkan ke Peta Orang menggunakan alat ini.
Di bawah ini Anda akan melihat beberapa contoh pengakuan.