Algoritma untuk pencocokan segmen

Apa algoritma terbaik untuk mencocokkan segmen?

Saya mencoba mencocokkan segmen yang sesuai dari dua sumber peta, satu kurang akurat tetapi dengan nama segmen, dan satu lagi lebih akurat tanpa nama segmen. Saya ingin menerapkan nama segmen secara semi-otomatis ke peta yang lebih akurat.

Algoritme yang diminta memiliki deskripsi yang cukup kabur karena "kecocokan" tidak didefinisikan dengan baik, dan banyak faktor (orientasi, panjang relatif, jarak) mungkin memiliki bobot yang berbeda dalam skenario yang berbeda; Namun, saya mencari pengetahuan dasar tentang pendekatan umum untuk menangani masalah ini.

Implementasi kerja untuk lingkungan open-source (PostGIS, rupawan, ...) disambut hangat.

Segmen sampel : Lihat deskripsi di bawah gambar.

The Hausdorff jarak dapat digunakan: segmen yang cocok bisa menjadi 'dekat' segmen sesuai dengan jarak ini. Cukup sederhana untuk menghitung segmen.

Implementasi java gratis tersedia di JTS - lihat Paket Jarak JTS . Anda juga dapat melihat JCS Conflation Suite (sekarang ditinggalkan, salinan sumber misalnya di https://github.com/oschrenk/jcs ).

Saya tidak tahu apa yang akan menjadi "terbaik," karena itu akan tergantung pada rincian segmen Anda.

Pendekatan yang umumnya baik adalah mengelompokkan segmen menjadi informasi geometris yang penting . Ini akan mencakup, minimal, lokasi pusat (x, y), orientasi (0 hingga 180 derajat), dan panjang. Dengan bobot yang sesuai diterapkan, dan beberapa orientasi (karena 180 "membungkus" kembali ke 0), Anda kemudian dapat menerapkan hampir semua algoritma pengelompokan statistik untuk pengumpulan semua segmen. ( K-means akan menjadi pilihan yang baik, tetapi sebagian besar metode hierarkis harus bekerja dengan baik. Analisis klaster semacam itu cenderung cepat dan mudah diterapkan.) Idealnya, segmen akan muncul berpasangan (atau lajang untuk segmen yang tidak cocok) dan sisanya gampang.

Salah satu cara untuk menangani masalah orientasi adalah membuat salinan segmen berlabel. Tambahkan 180 derajat ke orientasi salinan pertama, jika kurang dari 90, dan kurangi 180 derajat dari orientasi. Ini memperbesar dataset Anda (jelas) tetapi sebaliknya tidak mengubah algoritma dengan cara apa pun.

Bobot diperlukan karena perbedaan koordinat, panjang, dan orientasi dapat berarti hal-hal yang sangat berbeda mengenai kesamaan segmen yang sesuai. Dalam banyak aplikasi, perbedaan antar segmen muncul dari perbedaan lokasi titik akhir mereka. Sebagai perkiraan kasar, kita bisa mengharapkan variasi khas dalam panjang segmen hampir sama dengan variasi khas antara titik akhir mereka. Oleh karena itu, bobot yang terkait dengan x, y, dan panjangnya harus hampir sama. Bagian yang sulit adalah orientasi pembobotan, karena orientasi tidak dapat disamakan dengan jarak dan, lebih buruk lagi, segmen pendek akan lebih cenderung menjadi salah orientasi daripada segmen panjang. Pertimbangkan metode percobaan-dan-kesalahan yang menyamakan beberapa derajat misorientasi dengan ukuran kesenjangan khas antara segmen dan kemudian sesuaikan sampai prosedur tampak bekerja dengan baik. Untuk panduan, mariL menjadi panjang segmen tipikal. Perubahan orientasi dengan sudut t bertubuh kecil akan menyapu jarak sekitar L / 2 * t / 60 (60 mendekati jumlah derajat dalam satu radian), yaitu L / 120 kali t . Itu menyarankan dimulai dengan satuan bobot untuk x, y, dan panjang dan berat L / 120 untuk orientasi.

Singkatnya , saran ini adalah:

1. Buat salinan segmen berlabel (seperti yang dijelaskan dalam paragraf tentang kelayakan orientasi).

2. Konversi setiap segmen menjadi quadruple (x, y, panjang, orientasi L / 120 *) di mana L adalah panjang segmen tipikal.

3. Lakukan analisis kluster empat kali lipat. Gunakan paket statistik yang baik ( R gratis).

4. Gunakan output analisis kluster sebagai tabel pencarian untuk mengaitkan segmen berlabel dengan segmen tak berlabel terdekat.

Saya mengerjakan proyek dengan persyaratan yang sama sekitar 5 tahun yang lalu. Ini melibatkan menggabungkan koordinat dari garis tengah jalan (dengan presisi koordinat yang relatif tinggi) dengan tautan jaringan lalu lintas Highway Monitoring System (HPMS).

Pada saat itu FHWA tidak menyediakan alat untuk melakukan hal semacam ini. Itu mungkin telah berubah, Anda mungkin ingin memeriksa. Bahkan jika Anda tidak bekerja dengan data jalan raya, alat mungkin masih relevan.

Saya menulisnya dengan ArcGIS, tetapi algoritme harus bekerja di opensource, asalkan menyediakan kemampuan penelusuran yang mirip dengan ISegmentGraph :

// features is a collection of features with higher geometry
// Links are a collection features with attributes but low res geometry
For each Link in lowResFeatureclass
    point startPoint = SnapToClosestPoint(Link.StartPoint, hiResfeatures);
    if(startPoint == null)
       continue;
    point endPoint = SnapToClosest(Link.EndPoint, hiResfeatures);
    if(endPoint == null)
       continue;
    polyline trace = Trace(hiResfeatures,startPoint,endPoint);
    if(polyline != null)
    {
        // write out a link with high precision polyline
        Write(Link,polyline);
    }
Next Link

Ini dia ide

Jika Anda merobek salah satu linestrings untuk membandingkan dan menguji apakah titik vertex berada dalam jarak tertentu dari linestring lain untuk membandingkan, Anda dapat mengontrol tes dengan banyak cara.

contoh-contoh itu berfungsi di PostGIS (siapa yang bisa menebak :-))

Pertama, jika kita mengatakan bahwa ada kecocokan jika semua titik simpul dalam linestring di table_1 adalah 0,5 meter (unit peta) atau lebih dekat dengan linestring di table_2:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points,
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(*)=num_of_points;

Maka kita dapat mengatakan bahwa ada kecocokan jika lebih dari 60% dari vertex_points dalam linestring di table_1 berada dalam jarak linestring di table_2

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)/num_of_points::float > 0.6

Atau kami dapat menerima bahwa satu poin tidak dalam jangkauan:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)-num_of_points <= 1;

Anda juga harus menjalankan kueri dengan table_1 dan table_2 dalam peran terbalik.

Saya tidak tahu seberapa cepat itu. ST_Dumppoints saat ini merupakan fungsi sql di PostGIS dan bukan fungsi-C yang membuatnya lebih lambat dari yang seharusnya. Tapi saya pikir itu akan cukup cepat.

Indeks spasial akan banyak membantu ST_Dwithin agar efektif.

HTH Nicklas

Saya sudah menulis kode untuk menangani pencocokan segmen garis ceroboh (dan tumpang tindih) di Boundary Generator. Saya menulis matematika (cukup mendasar) di belakangnya di sini: http://blog.shoutis.org/2008/10/inside-boundary-generator-computational.html . Kode ini open source & ditautkan dari posting blog itu.

Kode mengikuti pendekatan yang sangat sederhana:

• Tes segmen-segmen yang akan memberi tahu Anda apakah dua segmen garis tumpang tindih dalam toleransi sudut dan jarak yang diberikan, dan jumlah tumpang tindih.
• Indeks spasial quick'n'dirty yang menghilangkan kebutuhan untuk menguji setiap segmen garis dalam dataset terhadap semua segmen garis lainnya dalam dataset.

Keuntungan utama dari pendekatan ini adalah Anda mendapatkan tombol yang tepat untuk sudut, jarak, dan panjang yang tumpang tindih; pada sisi negatifnya, ini bukan cara mengukur kemiripan dua segmen garis secara umum sehingga lebih sulit untuk misalnya melakukan pengelompokan statistik untuk menentukan kemungkinan kecocokan - Anda terjebak dengan kenop yang tepat.

Catatan: Saya menduga bahwa dengan SQL chops yang cukup, Anda dapat menjejalkan tes segmen-segmen menjadi klausa WHERE ... :)

Tepuk tangan!

Saya telah mengimplementasikan prototipe kasar untuk pencocokan peta di sini , yang relatif mudah digunakan. Ini didasarkan pada mesin routing sumber terbuka dan ditulis dalam Java. Algoritma yang digunakan dijelaskan di sini .