Tautan dan gagasan pencocokan peta? [Tutup]

44

Saya menggunakan OpenStreetMap dan jaringan jalan vektorialnya dan saya ingin menerapkan algoritma pencocokan peta.

Saat ini saya dapat, untuk setiap posisi GPS, untuk mengambil segmen jalan terdekat dan menghitung proyeksi posisi ini untuk segmen itu, seperti pada gambar ini (Pin merah adalah posisi GPS murni, berwarna biru pada segmen yang dipetakan dan dalam warna Hijau) posisi yang dipetakan):

masukkan deskripsi gambar di sini

Namun, karena kurangnya keakuratan GPS, terkadang posisi yang dipetakan melompat dari segmen ke segmen yang lain dan dapat memberikan beberapa posisi pemetaan yang tidak konsisten dari waktu ke waktu.

Algoritme saya saat ini sangat mendasar: dari posisi GPS murni, saya mendapatkan segmen terdekat dan memutuskan bahwa posisi yang cocok yang dipetakan ada pada yang ini. Saya tahu ini bisa sangat ditingkatkan.

Saya dapat membayangkan bahwa dengan mempertimbangkan arah kendaraan akan meningkatkan pencocokan peta tetapi apakah Anda tahu pendekatan lain yang memungkinkan saya meningkatkan pencocokan peta saya?

Saya mencari tautan, dan / atau perangkat lunak sumber terbuka?

yonel
sumber
4
Anda bisa menambahkan lingkaran - Google menggunakan penerimaan sel dan membuat lingkaran biru muda untuk menunjukkan perkiraan lokasi Anda. Aplikasi Anda terlihat bagus, kerja bagus. Jika Anda memiliki data vektor, Anda dapat mengambil ke garis terdekat dari titik GPS Anda - lihat posting oleh Paul Ramsey blog.cleverelephant.ca/2008/04/snapping-points-in-postgis.html
Mapperz
4
Kata kunci yang Anda cari adalah Pencocokan Peta. Subjek besar.
Uffe Kousgaard
1
Uffe benar, pencocokan peta. Periksa makalah ini untuk beberapa pendekatan: cens.ucla.edu/~mhr/cs219/maps/white00.pdf
lexicore
Terima kasih! lexicore, kertas sedang dikirim ke printer saya saat saya mengetik ini. Saatnya mendapatkan gambaran umum. Terima kasih atas tautannya.
scrrr
Saya akan meningkatkan Algoritma, dengan juga mencoba untuk mengambil jalan yang sebenarnya, bukan hanya simpul.
Devdatta Tengshe

Jawaban:

11

Memproyeksikan poin ke garis seperti yang sudah Anda lakukan dimungkinkan untuk dilakukan secara langsung di PostGIS. Saya menulis tentang beberapa waktu lalu, di sini

Tetapi untuk memecahkan masalah Anda ketika poin lebih dekat ke segmen yang salah daripada segmen yang tepat mungkin ini bisa menjadi pendekatan yang mungkin.

  1. Bangun linestring poin
  2. Coba solusi yang disarankan dalam Algoritma untuk pencocokan segmen agar cocok dengan seluruh baris, bukan hanya poin demi poin
Nicklas Avén
sumber
Terima kasih atas balasan Anda. Proyeksi OK: Saya sudah melakukannya (bukan melalui ST_Closest karena tidak tersedia di spasial yang saya gunakan tetapi tidak apa-apa). Saya juga hanya melihat Pertanyaan yang Anda sebutkan dan belajar tentang keberadaan "jarak Hausdorff" yang mungkin menarik untuk dilihat.
yonel
10

Setelah membaca Pertanyaan Anda, dan berbagai Jawaban, saya tertarik pada masalah ini. Setelah sedikit membaca tentang algoritma Pencocokan Peta, saya memahami yang berikut:

  • Untuk mencocokkan lokasi gps dengan jalan, Anda memerlukan data jalan aktual dalam format vektor
  • Ini akan membantu jika Anda memiliki bobot yang berbeda untuk jalan yang berbeda. Jadi peluang titik yang cocok dengan jalan raya akan lebih tinggi, kemudian dengan mencocokkan garis samping.
  • Anda perlu mengambil sejarah, dan kecepatan bacaan gps. Misalnya jika titik gps telah cocok dengan jalur samping untuk waktu yang lama, Anda harus memperhitungkannya, dan tidak mencocokkannya langsung ke jalan raya. -Pasangan yang sebenarnya dilakukan dengan menggunakan berbagai teknik statistik.

Untuk bacaan lebih lanjut, saya sarankan yang berikut:

Devdatta Tengshe
sumber
Ya, saya juga membaca dan mulai bermain dengan menerapkan algoritma sederhana yang dapat saya kembangkan. Sejauh ini saya telah mengunduh beberapa data dari OSM dan saya bermain dengan cara terbaik untuk menyimpan (dan mengakses) untuk tujuan saya. Itu topik yang menarik menurut saya. :) Saya akan memperbarui pertanyaan ini setelah saya memiliki sesuatu yang berfungsi. Juga, terima kasih atas tautannya!
scrrr
Saya akan berhati-hati dengan menggunakan bobot "Jadi peluang titik yang cocok dengan jalan raya akan lebih tinggi, kemudian dengan mencocokkan garis samping." ... Itu tergantung pada input data dan bisa salah.
underdark
@ David, saya mendapatkan 404 di tautan kedua. Alih-alih saya hanya mengeditnya, apakah Anda memiliki tautan alternatif?
Chau
Saya tidak memiliki tautan akses gratis ke artikel itu. Tetapi jika Anda berada dalam pengaturan akademik. Artikel harus tersedia setelah pencarian cepat
Devdatta Tengshe
@ Chau: Saya menemukan PDF di: researchgate.net/profile/Alain_Kornhauser/publication/…
Devdatta Tengshe
7

Menjawab pertanyaan saya sendiri!

1- .pdf yang bagus Saya baru saja menemukan tentang subjek ini:

http://safari.ce.sharif.edu/file/2011-06-06/259/2009_An%20off-line%20map-matching%20algorithm%20for%20incomplete%20map%20databases.pdf

yang juga menautkan ke implementasi sumber terbuka C ++ dari pencocokan peta yang dijelaskan dalam dokumen: http://eden.dei.uc.pt/~camara/files/mgemma.zip
(yang ini pencocokan peta offline, pemahaman saya adalah bahwa itu menghitung peta posisi yang cocok dengan jalur WHOLE sebagai input dan tidak dapat melakukannya dengan cepat untuk setiap posisi).

2- Kemudian, saya baru saja membaca yang ini secara mendalam dan itu sangat bagus menurut saya: https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/4860/1/velaga.pdf "Berkembang Algoritma Pencocokan Peta Topologi Berbasis Berat yang Ditingkatkan untuk Sistem Transportasi Cerdas "
Algoritma ini dijelaskan dengan jelas dan nilai penyesuaian berat juga disediakan dalam dokumen ini.

yonel
sumber
4

Ada banyak pekerjaan pada Pencocokan Peta, lihat makalah ini untuk survei singkat tentang beberapa pekerjaan yang cukup baru (sebelum 2007). Baru-baru ini, pendekatan berdasarkan Model Hidden Markov tampaknya berkinerja cukup baik dalam keadaan normal. Misalnya, lihat makalah ini dari 2009. Ide dan modelnya cukup sederhana dan tidak akan membuat Anda terlalu kesulitan untuk mengimplementasikannya bahkan jika Anda tidak terbiasa dengan HMM (dalam hal ini, jangan panik, ada banyak dari tutorial dan perkenalan online)

Nick
sumber
1
Baru menyadari bahwa Barefoot -Project yang saya sebutkan dalam jawaban saya didasarkan pada kertas yang direkomendasikan oleh @Nick.
nik
4

Metode ini juga disebut "penggabungan vektor". Ada halaman Wiki khusus ( http://wiki.openstreetmap.org/wiki/Conflation ) yang memberikan gambaran umum dan daftar paket perangkat lunak (Sumber Terbuka) untuk melakukan penggabungan vektor jalan seperti "JOSM conflation plugin", "penggabungan Potlatch 2," penggabungan Potlatch 2 alat "," RoadMatcher "(untuk OpenJUMP), dan lainnya.

markN
sumber
1
Saya selalu berpikir bahwa penyatuan adalah sesuatu yang Anda lakukan dengan dua lapisan garis alih-alih mencocokkan poin ke garis. Apakah ini benar-benar sama?
underdark
4

Untuk algoritme Pencocokan Peta, tergantung apakah Anda memerlukan pemrosesan waktu nyata atau offline. Dalam kasus selanjutnya, algo yang canggih dapat memproses ~ 1000 poin per detik. Persyaratan memori tergantung pada cakupan saja. Kami telah berhasil memeras jaringan jalan OSM di planet ini sekitar 16 Gb untuk tujuan itu.

Selain itu, Anda perlu membedakan pencocokan peta dari inferensi jalur : ini adalah dua proses terpisah tergantung jika Anda memiliki data frekuensi tinggi atau rendah. Ketika Anda memiliki titik yang relatif sedikit (mis. 1 data setiap kilometer dalam konteks perkotaan), itu kesimpulan jalur karena biasanya ada beberapa asumsi yang harus dilakukan untuk menebak di mana perangkat bepergian. Path inference biasanya lebih sulit tetapi semakin sedikit masalah dengan perangkat modern / harga perolehan data.

Anda dapat memeriksa profil saya untuk API yang melakukan pencocokan peta langsung pada OSM: ia menggunakan pencocokan topologi dan berfungsi dengan baik dengan data mobil apung misalnya.

Fabrice Marchal
sumber
Bisakah Anda mengembangkan algoritma yang Anda gunakan? Dan bagaimana mengurangi ukuran jaringan jalan membantu?
Devdatta Tengshe
Kurang cakupan = jaringan yang lebih kecil untuk disimpan dalam memori. Itu mempercepat perhitungan sedikit. Referensi: trb.metapress.com/content/p31485vw72645686
Fabrice Marchal
3

Strava Slide menjelaskan bagaimana kumulatif data trek melalui jaringan jalan dapat berperilaku seperti "lembah", dan bagaimana rute yang diusulkan akan "jatuh ke tempatnya" seperti seutas tali manik-manik.

heltonbiker
sumber
2

Setelah menguji sebagian besar kerangka yang disebutkan sebelumnya saya menemukan Barefoot dan benar-benar dapat merekomendasikannya. Ini menggunakan model markov tersembunyi sebagai pendekatan pencocokan peta probabilistik (rincian dalam makalah mereka "Menempatkan mobil di peta" ) dan diimplementasikan di Jawa. Ini adalah open-source dan dikembangkan secara aktif oleh Departemen CarIT BMW.

nik
sumber
2

Subjek disebut pencocokan peta. Tetapi sebagai perkiraan pertama yang sangat baik mungkin cukup baik untuk hanya mencari titik terdekat untuk setiap titik gps (tanpa koreksi menebak dengan cara yang benar).

Proyek Open Source saya bernama graphhopper bukanlah sesuatu yang berfungsi untuk iOS ( pembaruan : sekarang juga berfungsi di iOS), juga tidak memiliki aplikasi Android yang berfungsi penuh untuk apa yang Anda inginkan. Tapi Anda bisa menggunakan versi server untuk membangun aplikasi iOS atau menggunakan demo Android offline sebagai permulaan. Saya telah merilis algoritma pencocokan peta di sini , hanya sebuah prototipe kasar tetapi bekerja sangat baik.

Karussell
sumber
1

Coba dan dapatkan beberapa data uji yang bagus. Gunakan tambahan trek logging GPS dengan akurasi yang lebih tinggi, selain titik-titik logging pada perangkat target Anda. Ini akan mengidentifikasi kesalahan dalam GPS dan data OSM yang mendasarinya. Mengetahui ambang batas yang masuk akal akan membuatnya lebih mudah untuk merancang algoritma.

Matthew Snape
sumber
1

Jika Anda dapat memperoleh data jalan untuk wilayah Anda, Anda mungkin tertarik dengan Pemotongan massal otomatis dengan FOSS

Bergantung pada apakah Anda ingin memplot data secara real time, atau Anda berencana melakukan beberapa postprocessing di PC Anda sesudahnya, GRASS mungkin bisa membantu.

Michal Zimmermann
sumber
1

Saya telah menemukan API yang mungkin hanya melakukan pekerjaan tanpa harus melalui upaya mengembangkan solusi sendiri segera.

Mereka menggunakan data OSM untuk melakukan pencocokan peta. Mereka juga memiliki halaman demo yang memungkinkan pengunggahan file GPX untuk melihat seberapa baik ini bekerja untuk Anda.

Arthur McFlint
sumber