Deteksi lingkaran (elips) di awan titik 2D

14

Diberikan satu set poin (2D) yaitu, point cloud (PC), pertanyaannya adalah tentang a robust, accuratedan computing-friendlymetode untuk menemukan lingkaran (atau elips dalam versi lanjutan).

Gagasan intuitifnya adalah menggunakan Pencarian Brute-Force pada semua titik yang memungkinkan (sebagai pusat) {infinite!} Dan jari-jari (lagi-lagi tak terbatas!). Ini sangat lambat dan tidak efisien.

Seperti yang diperlihatkan di bawah ini, setiap lingkaran yang dipasang akan diberi peringkat berdasarkan jumlah titik ( nn) yang diposisikan pada lingkaran-keliling dalam jarak yang lebih pendek dari ambang batas ( t). Jadi ada derruntuk menyajikan jarak rata-rata.

Dalam bentuk elips maju menarik untuk dipasang.

Adakah ide, brainstorming, pengalaman, komentar? masukkan deskripsi gambar di sini

edge-detection local-features point-cloud hough-transform Pengembang
sumber
Pertanyaan bagus. Program apa yang Anda gunakan untuk menghasilkan diagram itu?
Jason R
@JasonR Seperti biasa, Python + MatPlotLib .
Pengembang

Jawaban:

14

Ide-ide terbaik yang persis mencoba untuk memecahkan masalah ini adalah Hough Transform .

Pada dasarnya, sinyal di ruang hough akan r, x, ydikoordinasikan. Di sini r singkatan radius dan x,ysingkatan dari center. Setiap poin dapat dimiliki oleh satu atau banyak lingkaran. Jadi di pesawat Hough, lewati semua lingkaran yang memungkinkan di mana titik ini bisa menjadi milik dan lakukan +1. Ini bukan pencarian, hanya koleksi.

Sekarang, jika lingkaran nyata ada, begitu banyak poin akan ditambahkan dan skor seperti itu r, x, yakan jauh lebih tinggi daripada yang lainnya. Memilih titik seperti itu akan memungkinkan Anda memilih lingkaran yang tepat.

Ini adalah makalah klasik pada tahun 1971 (sebelum saya lahir!) Yang menemukan konsep ini.

  1. PENGGUNAAN TRASFORMASI HOUGH UNTUK MENDETEKSI GARIS DAN LINGKARAN DALAM GAMBAR Oleh: Richard O. Duda, laporan Peter E. Hart Tech Artificial Intelligence Cente April 1971.

Untuk Tutorial saya akan menyarankan referensi di bawah ini:

  1. HIPR2 -Link
  2. Amos bangau
  3. Referensi IDL

Khusus untuk deteksi lingkaran, Anda dapat merujuk ini di bawah:

  1. AI Shack
  2. Laporan Teknologi dari Chicago Univ.
  3. Catatan Kuliah dari Rochester Institute

Metode ini sangat efisien, dan sangat ramah komputer.

Dipan Mehta
sumber
1
Saya dapat menjamin untuk artikel AI Shack, mereka benar-benar membantu grok matematika yang lebih ketat yang akan Anda baca di tempat lain.
Ivo Flipse
1
Jawaban yang bagus. Saya sudah terbiasa dengan Hough Transform (HT). Yang saya gunakan adalah untuk mendeteksi garis. Ada sedikit kesulitan untuk menentukan segmen garis. Disarankan agar menggunakan Probabilistic Hough Transform (PHT). Saya tidak mendapatkan ide yang jelas tentang ekstensi. Saya pikir itu mungkin sangat kompleks untuk lingkaran atau muncul kesulitan lain. Mengenai pengalaman saya, HT bagus tapi tidak sempurna. Ini juga menjadi perhatian saya bagaimana memperluas HT ke 3D. Saya akan mencoba meninjau tautan yang Anda berikan. Jawaban Anda cukup baik untuk menjadi kandidat sebagai jawabannya.
Pengembang
AI Shack, dan Tech Report dari tautan Chicaco sudah mati
Mehdi