Mendeteksi pola melingkar dalam data cloud titik

Untuk beberapa algoritma rekonstruksi volume yang sedang saya kerjakan, saya perlu mendeteksi sejumlah pola melingkar dalam data titik 3d (yang berasal dari perangkat LIDAR). Pola-pola ini dapat diorientasikan secara sewenang-wenang di ruang angkasa, dan diasumsikan terletak (meskipun tidak sempurna) di bidang tipis 2d. Berikut ini adalah contoh dengan dua lingkaran di bidang yang sama (walaupun ingat ini adalah ruang 3d):

masukkan deskripsi gambar di sini

Saya mencoba banyak pendekatan .. yang paling sederhana (tapi yang paling berhasil sejauh ini) adalah pengelompokan berdasarkan set terpisah dari grafik tetangga terdekat. Ini bekerja cukup baik ketika polanya berjauhan, tetapi kurang begitu dengan lingkaran seperti pada contoh, benar-benar dekat satu sama lain.

Saya mencoba K-means, tetapi tidak berhasil: Saya kira pengaturan titik melingkar mungkin tidak cocok untuk itu. Ditambah lagi, saya memiliki masalah tambahan karena tidak mengetahui sebelumnya nilai K.

Saya mencoba pendekatan yang lebih rumit, berdasarkan deteksi siklus dalam grafik tetangga terdekat, tetapi apa yang saya dapatkan terlalu rapuh atau mahal secara komputasi.

Saya juga membaca tentang banyak topik terkait (transformasi Hough, dll) tetapi tampaknya tidak ada yang berlaku dengan sempurna dalam konteks khusus ini. Ide atau inspirasi apa pun akan dihargai.

clustering image-processing cjauvin
sumber

Sebuah pertanyaan sederhana: bagaimana Anda akan mendeteksi segmen garis dalam data dua dimensi?

charles.y.zheng

"..seperti yang ada di contoh"? Contoh apa? Bisakah Anda menambahkan tautan?

onestop

Transformasi Hough adalah pilihan yang jelas. Itu harus bekerja dengan baik.

whuber

Saya baru saja mendapatkan reputasi yang cukup untuk menambahkan contoh gambar yang saya maksud.

cjauvin

Ini bukan masalah pengelompokan. Dalam statistik, "cluster" terdiri dari set objek yang saling lebih dekat satu sama lain daripada objek lain. Kedekatan tidak menangkap sirkularitas: itu sebabnya K-means atau algoritma pengelompokan lainnya tidak akan berfungsi. Karena alasan ini, pertanyaan ini mungkin lebih cocok di situs pemrosesan gambar atau GIS, di mana Anda mungkin menemukan beberapa pakar tentang masalah ini.

whuber

Jawaban:

Transformasi Hough umum adalah persis apa yang Anda inginkan. Kesulitannya adalah melakukannya secara efisien, karena ruang lingkaran dalam 3D memiliki enam dimensi (tiga untuk pusat, dua untuk mengarahkan pesawat, satu untuk jari-jari). Ini tampaknya mengesampingkan perhitungan langsung.

Satu kemungkinan adalah untuk menyelinap pada hasil melalui serangkaian transformasi Hough sederhana. Misalnya, Anda bisa mulai dengan transformasi Hough (biasa) untuk mendeteksi himpunan bagian planar: yang hanya memerlukan kisi 3D untuk perhitungan. Untuk setiap himpunan planar yang terdeteksi, potong titik-titik asli di sepanjang bidang itu dan lakukan transformasi Hough umum untuk deteksi lingkaran. Ini harus bekerja dengan baik asalkan gambar asli tidak memiliki banyak titik coplanar (selain yang dibentuk oleh lingkaran) yang bisa menenggelamkan sinyal yang dihasilkan oleh lingkaran.

Jika ukuran lingkaran memiliki batas atas yang telah ditentukan, Anda berpotensi menyimpan banyak perhitungan: daripada melihat semua pasangan atau tiga kali lipat poin dalam gambar asli, Anda dapat fokus pada pasangan atau tiga kali lipat dalam lingkungan yang dibatasi pada setiap titik.

whuber
sumber

Saya akan mencoba menggabungkan semua pendekatan yang disarankan: cluster pertama berdasarkan jarak saja, seperti yang dibahas poster asli, yang akan memberi Anda cluster yang mungkin terdiri dari beberapa lingkaran. Kemudian gunakan Hough untuk mendeteksi himpunan bagian planar dalam setiap kelompok. Kemudian dalam setiap subset planar lagi gunakan Hough untuk menemukan lingkaran. Jika langkah terakhir ini mahal, Anda mungkin dapat melakukan hubungan arus pendek yang efektif: coba beberapa kali lipat, tebak satu lingkaran, dan lihat apakah sebagian kecil dari titik-titik dalam subset Anda terletak sangat dekat dengan lingkaran itu. Jika demikian, rekam lingkaran itu dan hapus semua titik itu, lalu lanjutkan.

Erik P.

Ide terakhir ini disebut RANSAC dan mungkin dapat digunakan dengan sendirinya, terutama jika jumlah lingkaran per gambar kecil.

SheldonCooper

Terima kasih atas ide-ide yang menerangi! Transformasi multi-langkah Hough menurut saya solusi yang paling kuat dan umum, tetapi RANSAC benar-benar terlihat lebih mudah diimplementasikan, dan mungkin cukup dalam konteks saya. Namun, satu masalah yang saya perhatikan dengan cepat adalah kasus di mana Anda memiliki pola ukuran yang tidak seimbang, yang jelas-jelas membuat sampel menjadi bias terhadap objek yang lebih besar. Adakah pemikiran tentang masalah ini?

cjauvin

Setelah Anda mendeteksi lingkaran yang lebih besar, hapus semua titik yang menjadi miliknya dari pengambilan sampel.

SheldonCooper

$\textit{number}$

sdgaw erzswer
sumber