Pencocokan Profil di Point Cloud

Sebuah titik awan yang dihasilkan menggunakan fungsi acak seragam untuk (x,y,z). Seperti yang ditunjukkan pada gambar berikut, sebuah pesawat berpotongan datar ( profil ) sedang diselidiki yang cocok sebagai yang terbaik (bahkan jika bukan yang tepat) yaitu profil target, diberikan di sudut kiri bawah. Jadi pertanyaannya adalah:

1- Bagaimana menemukan kecocokan yang diberikan target 2D point mapdengan point cloudmempertimbangkan catatan / ketentuan berikut?
2- Apa yang kemudian koordinat / orientasi / derajat kesamaan dll?

Catatan 1: Profil yang menarik bisa di mana saja dengan rotasi di sepanjang sumbu dan juga bisa dalam bentuk yang berbeda misalnya, segitiga, persegi panjang, segi empat dll tergantung pada lokasi dan orientasinya. Pada demonstrasi berikut ini hanya satu persegi panjang sederhana yang ditampilkan.

Catatan 2: Nilai toleransi dapat dianggap sebagai jarak titik dari profil. Untuk menunjukkan ini untuk gambar berikut anggaplah toleransi 0.01kali dimensi terkecil (~1)begitu tol=0.01. Jadi jika kita menghapus sisanya dan memproyeksikan semua poin yang tersisa di bidang profil yang sedang diselidiki maka kita akan dapat memeriksa kesamaannya dengan profil target.

Catatan 3: Topik terkait dapat ditemukan di Pengenalan Pola Titik .

Ini akan selalu membutuhkan banyak perhitungan, terutama jika Anda ingin memproses sebanyak 2000 poin. Saya yakin sudah ada solusi yang sangat optimal untuk pencocokan pola semacam ini, tetapi Anda harus mencari tahu apa namanya untuk menemukan mereka.

Karena Anda berbicara tentang cloud titik (data jarang) alih-alih gambar, metode korelasi silang saya tidak benar-benar berlaku (dan akan lebih buruk secara komputasi). Sesuatu seperti RANSAC mungkin menemukan kecocokan dengan cepat, tetapi saya tidak tahu banyak tentang itu.

Upaya saya untuk solusi:

Asumsi:

• Anda ingin menemukan kecocokan terbaik, bukan hanya kecocokan longgar atau "mungkin benar"
• Kecocokan akan memiliki sejumlah kesalahan kecil karena kebisingan dalam pengukuran atau perhitungan
• Poin sumber adalah coplanar
• Semua poin sumber harus ada dalam target (= setiap titik yang tak tertandingi ketidaksesuaian untuk seluruh profil)

Jadi, Anda harus dapat mengambil banyak pintasan dengan mendiskualifikasi hal-hal dan mengurangi waktu perhitungan. Pendeknya:

1. pilih tiga poin dari sumber
2. cari melalui titik target, temukan set 3 titik dengan bentuk yang sama
3. ketika kecocokan 3 poin ditemukan, periksa semua poin lain di pesawat yang mereka tentukan untuk melihat apakah mereka cocok atau tidak
4. jika lebih dari satu kecocokan dari semua titik ditemukan, pilih satu dengan jumlah kesalahan jarak 3D terkecil

Lebih detail:

pick a point from the source for testing s1 = (x1, y1)
Find nearest point in source s2 = (x2, y2)
d12 = (x1-x2)^2 + (y1-y2)^2
Find second nearest point in source s3 = (x3, y3)
d13 = (x1-x3)^2 + (y1-y3)^2
d23 = (x2-x3)^2 + (y2-y3)^2

for all (x,y,z) test points t1 in target:
    # imagine s1 and t1 are coincident
    for all other points t2 in target:
        if distance from test point > d12:    
            break out of loop and try another t2 point
        if distance ≈ d12:
            # imagine source is now rotated so that s1 and s2 are collinear with t1 and t2
            for all other points t3 in target:
                if distance from t1 > d13 or from t2 > d23:
                    break and try another t3
                if distance from t1 ≈ d13 and from t2 ≈ d23:
                    # Now you've found matching triangles in source and target
                    # align source so that s1, s2, s3 are coplanar with t1, t2, t3
                    project all source points onto this target plane 
                    for all other points in source:
                        find nearest point in target
                        measure distance from source point to target point
                        if it's not within a threshold:
                            break and try a new t3
                        else:
                            sum errors of all matched points for this configuration (defined by t1, t2, t3)

Konfigurasi mana pun yang memiliki kesalahan kuadrat terkecil untuk semua poin lainnya adalah yang paling cocok

Karena kami bekerja dengan 3 titik pengujian tetangga terdekat, mencocokkan poin target dapat disederhanakan dengan memeriksa apakah mereka berada dalam beberapa radius. Jika mencari jari-jari 1 dari (0, 0), misalnya, kita dapat mendiskualifikasi (2, 0) berdasarkan x1 - x2, tanpa menghitung jarak Euclidean yang sebenarnya, untuk mempercepatnya sedikit. Ini mengasumsikan bahwa pengurangan lebih cepat daripada perkalian. Ada pencarian yang dioptimalkan berdasarkan radius tetap yang lebih sewenang-wenang juga.

function is_closer_than(x1, y1, z1, x2, y2, z2, distance):
    if abs(x1 - x2) or abs(y1 - y2) or abs(z1 - z2) > distance:
        return False
    return (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 > distance^2 # sqrt is slow

$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2+(z_1 - z_2)^2}$

Waktu perhitungan minimum adalah jika tidak ada kecocokan 2 poin yang ditemukan. Jika ada 2000 poin dalam target, ini akan menjadi perhitungan jarak 2000 * 2000, meskipun banyak yang akan didiskualifikasi dengan pengurangan, dan hasil perhitungan sebelumnya dapat disimpan sehingga Anda hanya perlu melakukan = 1.999.000.$2000 \choose 2$

Sebenarnya, karena Anda tetap harus menghitung semua ini, apakah Anda menemukan kecocokan atau tidak, dan karena Anda hanya peduli dengan tetangga terdekat untuk langkah ini, jika Anda memiliki memori, mungkin lebih baik untuk melakukan pra-perhitungan nilai-nilai ini menggunakan algoritma yang dioptimalkan . Sesuatu seperti triangulasi Delaunay atau Pitteway , di mana setiap titik di target terhubung ke tetangga terdekatnya. Simpan yang ada di dalam tabel, lalu cari untuk setiap titik ketika mencoba menyesuaikan sumber segitiga dengan salah satu segitiga target.

Ada banyak perhitungan yang terlibat, tetapi harus relatif cepat karena hanya beroperasi pada data, yang jarang, daripada mengalikan banyak nol yang tidak berarti bersama-sama seperti korelasi silang dari data volumetrik yang akan terlibat. Ide yang sama ini akan bekerja untuk case 2D jika Anda menemukan pusat titik pertama dan menyimpannya sebagai satu set koordinat.

Saya akan menambahkan deskripsi @ mirror2image pada solusi alternatif di samping RANSAC, Anda dapat mempertimbangkan algoritma ICP (titik terdekat berulang), deskripsi dapat ditemukan di sini !

Saya pikir tantangan berikutnya dalam menggunakan ICP ini adalah untuk menentukan fungsi biaya Anda sendiri, dan pose awal pesawat target sehubungan dengan data titik awan 3d. Beberapa pendekatan praktis adalah untuk memperkenalkan beberapa noise acak dalam data selama iterasi untuk menghindari konvergensi ke minimum minimum. Ini adalah bagian heuristik yang saya kira perlu Anda desain.

Memperbarui:

Langkah-langkah dalam bentuk yang disederhanakan adalah:

1. Temukan titik terdekat untuk setiap titik input.
2. Hitung transformasi dari input ke target, dan kemudian pindahkan titik input menggunakan transformasi.
3. Hitung fungsi kesamaan (misalnya jarak untuk setiap titik input wrt ke titik target pasangan yang sesuai).
4. Periksa kondisi berhenti.

Iterasi langkah 1-4.

Ada perpustakaan yang tersedia yang dapat Anda pertimbangkan di sini ! (Saya belum mencobanya), ada satu bagian di bagian pendaftaran (termasuk metode lain).