Pas garis melalui awan titik besar

Saya memiliki satu set besar poin (urutan 10k poin) yang dibentuk oleh trek partikel (pergerakan di bidang xy pada waktunya difilmkan oleh kamera, jadi 3d - 256x256px dan ca 3k frame dalam set contoh saya) dan kebisingan. Partikel-partikel ini bergerak pada garis yang kira-kira lurus kira-kira (tetapi hanya kira-kira) dalam arah yang sama, dan untuk analisis lintasan mereka, saya mencoba menyesuaikan garis melalui titik-titik. Saya mencoba menggunakan Sequential RANSAC, tetapi tidak dapat menemukan kriteria untuk secara pasti memilih positif palsu, serta T- dan J-Linkage, yang terlalu lambat dan juga tidak cukup dapat diandalkan.

Berikut ini adalah gambar dari bagian dataset dengan cocok baik dan buruk yang saya dapatkan dengan Ransac berurutan: Saya menggunakan centroid gumpalan partikel di sini, ukuran gumpalan bervariasi antara 1 dan sekitar 20 piksel.

Saya menemukan bahwa contoh menggunakan hanya setiap frame 10 bekerja dengan sangat baik, sehingga ukuran data yang akan diproses dapat dikurangi dengan cara ini.

Saya membaca posting blog tentang semua hal yang dapat dicapai jaringan saraf, dan ingin bertanya apakah ini akan menjadi aplikasi yang layak sebelum saya mulai membaca (saya berasal dari latar belakang non-matematika, jadi saya harus melakukan cukup sedikit membaca)?

Atau bisakah Anda menyarankan metode yang berbeda?

Terima kasih!

Tambahan: Ini adalah kode untuk fungsi Matlab untuk menghasilkan cloud titik sampel yang berisi 30 garis bising paralel, yang belum dapat saya bedakan:

function coords = generateSampleData()
coords = [];
for i = 1:30
    randOffset = i*2;
    coords = vertcat(coords, makeLine([100+randOffset 100 100], [200+randOffset 200 200], 150, 0.2));
end

figure
scatter3(coords(:,1),coords(:,2),coords(:,3),'.')

function linepts = makeLine(startpt, endpt, numpts, noiseOffset)
    dirvec = endpt - startpt;
    linepts = bsxfun( @plus, startpt, rand(numpts,1)*dirvec); % random points on line
    linepts = linepts + noiseOffset*randn(numpts,3); % add random offsets to points
end

end

Berdasarkan umpan balik dan mencoba menemukan pendekatan yang lebih efektif, saya mengembangkan algoritma berikut ini menggunakan ukuran jarak khusus.

Langkah-langkah berikut dilakukan:

1) Tentukan metrik jarak yang kembali:

nol - jika poin bukan milik garis

Jarak Euclidian dari titik - jika titik merupakan garis sesuai dengan parameter yang ditentukan, yaitu

• jarak mereka lebih tinggi atau sama dengan min_line_length dan

• jarak mereka lebih rendah atau sama dengan panjang max_line_length dan

• garis terdiri dari setidaknya titik min_line_points dengan jarak lebih rendah dari garis_2 / 2 dari garis

2) Hitung matriks jarak menggunakan ukuran jarak ini (gunakan sampel data untuk kumpulan data besar; sesuaikan parameter garis sesuai)

3) Temukan titik A dan B dengan jarak maksimum - istirahat ke langkah 5) jika jaraknya nol

Perhatikan bahwa jika jarak lebih tinggi dari nol, titik A dan B membangun garis berdasarkan definisi kami

4) Dapatkan semua poin milik garis AB dan hapus dari matriks jarak. Ulangi langkah 3) untuk menemukan baris lain

5) Periksa cakupan titik dengan garis yang dipilih, jika sejumlah besar titik tetap terbuka, ulangi seluruh algoritma dengan parameter garis yang disesuaikan.

6) Dalam hal sampel data digunakan - tetapkan kembali semua titik ke garis dan hitung ulang titik batas.

Parameter berikut digunakan:

lebar garis - line_width / 2 adalah jarak yang diizinkan dari titik dari garis ideal = r line_width

panjang garis minimum - titik dengan jarak lebih pendek tidak dianggap milik garis yang sama = r min_line_length

panjang garis maksimum - titik dengan jarak yang lebih jauh tidak dianggap milik garis yang sama = r max_line_length

titik minimum pada suatu garis - garis dengan lebih sedikit titik diabaikan =r min_line_points

Dengan data Anda (setelah beberapa mengutak-atik parameter) saya mendapat hasil yang baik yang mencakup semua 30 baris.

Rincian lebih lanjut dapat ditemukan di skrip knitr

Saya menyelesaikan tugas yang serupa, meski lebih sederhana, dengan pendekatan brute force. Penyederhanaan dalam asumsi, bahwa garis adalah fungsi linier (dalam kasus saya bahkan koefisien dan intersepsi berada dalam beberapa rentang yang diketahui).

Ini karena itu tidak akan menyelesaikan masalah Anda secara umum, di mana sebuah partikel dapat bergerak ortogonal dengan sumbu x (yaitu tidak melacak fungsi), tetapi saya memposting solusi sebagai inspirasi yang mungkin.

1) Ambil semua kombinasi dua titik A dan B dengan A (x)> B (x) + konstan (untuk menghindari simetri dan kesalahan tinggi saat menghitung koefisien)

2) Hitung koefisien c dan potong i dari garis AB

 A(y) = i + c * A(x)
 B(y) = i + c * B(x)
 A(y) - B(y) = c * (A(x) - B(x))
 c = (A(y) - B(y)) / (A(x) - B(x))
 i = A(y) - c * A(x)

3) Bulatkan koefisien dan potong (ini harus menghilangkan / menurunkan masalah dengan kesalahan yang disebabkan oleh titik-titik dalam kotak)

4) Untuk setiap intersep dan koefisien, hitung jumlah titik pada baris ini

5) Pertimbangkan hanya garis dengan titik di atas ambang tertentu.

Contoh sederhana lihat di sini