Cepat menemukan garis kasar di set poin

12

Di kelas detektor tertentu, data kami keluar sebagai pasangan titik dalam dua dimensi, dan kami ingin merangkai titik-titik ini menjadi garis.

Data berisik, dan dibuang dalam satu arah tetapi tidak di yang lain. Kami tidak dapat menjamin hit di setiap nampan bahkan ketika setiap elemen detektor berfungsi, jadi mungkin ada lompatan.

Rantai analisis kami saat ini terlihat seperti

  1. Sesuaikan hit untuk kalibrasi elemen detektor individual
  2. Temukan kelompok
  3. Garis-garis pas kasar ke kluster
  4. Hubungkan cluster ke struktur seperti garis yang lebih panjang
  5. ...

Pertanyaan ini menyangkut langkah (3).

Kami telah menggunakan transformasi Hough untuk langkah itu dan itu bekerja dengan baik, tetapi ketika kami mencoba untuk meningkatkan dari test-bed ke simulasi proyek skala penuh itu menjadi sangat lambat.

Saya mencari cara yang lebih cepat.

Bagi mereka yang mungkin peduli kasus penggunaan yang sebenarnya di sini adalah Kamar Proyeksi-Waktu Liquid Argon

regression computer-vision pattern-recognition dmckee --- mantan kucing moderator
sumber
1
Kami juga melakukan metode Hough Transform rekursif untuk pelacakan jalur melalui Kamar Proportional Multi-Kawat di FermiLab. Tesis senior Erik Kangas memiliki semua detail. Saya pikir ini masih cara terbaik untuk melakukannya.
Matt Knepley
1
Apakah maksud Anda "... berpasangan pada titik ..." atau "... berpasangan poin ..." dalam kalimat pertama?
Bill Barth

Jawaban:

2

Ada versi probabilistik dari Hough transform (PHT) yang lebih cepat. Seperti yang dijelaskan oleh Bradski & Kaehler dalam buku OpenCV mereka:

Idenya adalah bahwa puncaknya akan cukup tinggi bagaimanapun, kemudian memukulnya hanya sebagian kecil dari waktu akan cukup untuk menemukannya.

Pustaka OpenCV menyajikan implementasi untuk PHT.

Ada alternatif lain. Tidak sulit untuk membuat versi terdistribusi dari transformasi Hough. Hanya mematahkan set poin Anda menjadi potongan yang lebih kecil dan gunakan kerangka kerja MapReduce untuk merangkum semua akumulator. Gagasan lain adalah melakukan versi Hough transform kasar menggunakan ruang parameter dengan resolusi rendah. Pilih kandidat terbaik Anda dan jalankan iterasi yang lebih baik menggunakan ruang parameter yang menyajikan resolusi lebih tinggi. Mungkin ini adalah ide di balik FHT Gandalf.

TH.
sumber
1
PHT diusulkan dalam: Matas, J. dan Galambos, C. dan Kittler, JV, Deteksi Garis yang Kuat Menggunakan Progresif Probabilistik Hough Transform. CVIU 78 1, hal 119-137 (2000).
TH.
Kursus kemudian prosedur yang bagus dapat digeneralisasi menjadi beberapa langkah yang dilakukan Gandalf.
dmckee --- ex-moderator kitten
BTW - Pada saat saya mengajukan pertanyaan ini, seorang kolega telah menambahkan modul dengan menggunakan versi progresif probabilitas probabilistik dari transformasi ke kode kita. Ini datang dengan beberapa perubahan yang terkait sehingga sulit untuk mengkarakterisasi persis apa perbedaan yang dibuatnya, tetapi itu adalah bagian dari paket yang mempercepat beberapa langkah analisis. Jadi, saya akan menerima ini sebagai saran "menang".
dmckee --- ex-moderator kitten
5

Saya rekan telah menemukan Fast Hough Transform di perpustakaan Gandalf , yang terlihat sangat menjanjikan tetapi mungkin banyak pekerjaan untuk diintegrasikan, jadi saya mencari pendekatan lain.

Implementasi Gandalf menarik: mereka mengevaluasi ruang akumulator dengan cara rekursif seolah-olah melintasi quad atau oct-tree. Daerah tanpa kepadatan banyak dibuang saat mereka pergi.

dmckee --- mantan kucing moderator
sumber