Pengakuan Pola Titik

46

Memiliki dua ukuran set poin yang berbeda (2D untuk kesederhanaan) tersebar dalam dua kotak ukuran yang berbeda, pertanyaannya adalah:

1 - bagaimana menemukan kejadian yang kecil melalui yang besar?
2- Adakah gagasan tentang bagaimana memeringkat kejadian seperti yang ditunjukkan pada gambar berikut?

Berikut ini adalah demonstrasi sederhana dari pertanyaan dan solusi yang diinginkan: masukkan deskripsi gambar di sini


Pembaruan 1:
Gambar berikut menunjukkan pandangan yang sedikit lebih realistis dari masalah yang sedang diselidiki. masukkan deskripsi gambar di sini

Mengenai komentar, properti berikut berlaku:

  • lokasi tepat titik tersedia
  • ukuran poin yang tepat tersedia
    • ukuran bisa nol (~ 1) = hanya satu titik
  • semua titik berwarna hitam dengan latar belakang putih
  • tidak ada efek skala abu-abu / anti-aliasing

Inilah implementasi metode yang saya sajikan endolithdengan beberapa perubahan kecil (saya memutar target alih-alih sumber karena lebih kecil dan lebih cepat dalam rotasi). Saya menerima jawaban endolith karena saya memikirkan hal itu sebelumnya. Tentang RANSAC saya tidak punya pengalaman sejauh ini. Selanjutnya implementasi RANSAC membutuhkan banyak kode. masukkan deskripsi gambar di sini

Pengembang
sumber
1
Apakah Anda mencari solusi untuk mencocokkan titik-titik seperti itu, atau untuk gambar yang lebih kompleks? Berapa banyak titik di foto?
Ya, itu sangat penting. Jika hanya titik-titik dengan ukuran yang diketahui, Anda dapat mengoptimalkannya. Jika penanda fidusia yang Anda kendalikan, Anda dapat mengoptimalkannya. Lebih spesifik untuk apa Anda menggunakan ini.
endolith
Untuk masalah yang saya kerjakan ada set poin (masing-masing beberapa ratus poin) di mana set poin ukuran lebih kecil lainnya (katakanlah <100) sedang dicari. Demonstrasi di atas sangat sederhana dan jelas, namun masalah sebenarnya terlihat rumit. Ada juga minat untuk menemukan pertandingan yang didasarkan pada poin yang tidak diinginkan di antara mereka.
Pengembang
1
Apakah hanya akan ada titik hitam dan putih? Apakah Anda mendapatkannya dari kamera / pemindai / sesuatu yang lain? Nilai biner dapat membuat perhitungan lebih cepat.
endolith
Apakah Anda memiliki masalah dengan menemukan pusat-pusat titik, atau hanya dengan menemukan miniatur di gambar besar mengetahui posisi titik-titik?

Jawaban:

17

Ini bukan solusi terbaik, tapi itu sebuah solusi. Saya ingin belajar teknik yang lebih baik:

Jika tidak akan diputar atau diskalakan, Anda bisa menggunakan korelasi silang sederhana dari gambar. Akan ada puncak cerah di mana pun gambar kecil terjadi pada gambar besar.

Anda dapat mempercepat korelasi silang dengan menggunakan metode FFT, tetapi jika Anda hanya mencocokkan gambar sumber kecil dengan gambar target besar, metode multiplikasi tambah tambah kasar kadang-kadang (biasanya tidak) lebih cepat.

Sumber:

masukkan deskripsi gambar di sini

Target:

masukkan deskripsi gambar di sini

Korelasi silang:

masukkan deskripsi gambar di sini

Dua titik terang adalah lokasi yang cocok.

Tapi Anda lakukan memiliki parameter rotasi dalam contoh gambar Anda, sehingga tidak akan bekerja dengan sendirinya. Jika hanya rotasi yang diizinkan, dan bukan penskalaan, maka masih dimungkinkan untuk menggunakan korelasi silang, tetapi Anda harus berkorelasi silang, memutar sumber, menghubungkannya dengan seluruh gambar target, memutarnya lagi, dll untuk semua rotasi.

Perhatikan bahwa ini tidak akan selalu menemukan gambar. Jika gambar sumber adalah noise acak, dan targetnya adalah noise acak, Anda tidak akan menemukannya kecuali jika Anda mencari pada sudut yang tepat. Untuk situasi normal, mungkin akan menemukannya, tetapi itu tergantung pada properti gambar dan sudut yang Anda cari.

Halaman ini menunjukkan contoh bagaimana hal itu akan dilakukan, tetapi tidak memberikan algoritma.

Offset apa pun yang jumlahnya di atas ambang tertentu adalah kecocokan. Anda dapat menghitung kebaikan pertandingan dengan menghubungkan gambar sumber dengan dirinya sendiri dan membagi semua jumlah Anda dengan nomor ini. Pertandingan yang sempurna adalah 1,0.

Ini akan sangat berat secara komputasi, dan mungkin ada metode yang lebih baik untuk mencocokkan pola titik-titik (yang ingin saya ketahui).

Contoh Python cepat menggunakan metode grayscale dan FFT:

from __future__ import division
from pylab import *
import Image
import ImageOps

source_file = 'dots source.png'
target_file = 'dots target.png'

# Load file as grayscale with white dots
target = asarray(ImageOps.invert(Image.open(target_file).convert('L')))

close('all')
figure()
imshow(target)
gray()
show()

source_Image = ImageOps.invert(Image.open(source_file).convert('L'))

for angle in (0, 180):
    source = asarray(source_Image.rotate(angle, expand = True))
    best_match = max(fftconvolve(source[::-1,::-1], source).flat)

    # Cross-correlation using FFT
    d = fftconvolve(source[::-1,::-1], target, mode='same')

    figure()
    imshow(source)


    # This only finds a single peak.  Use something that finds multiple peaks instead:
    peak_x, peak_y = unravel_index(argmax(d),shape(d))

    figure()    
    plot(peak_y, peak_x,'ro')
    imshow(d)

    # Keep track of all these matches:
    print angle, peak_x, peak_y, d[peak_x,peak_y] / best_match

Bitmap 1 warna

Untuk bitmap 1-warna, ini akan jauh lebih cepat. Korelasi silang menjadi:

  • Tempatkan gambar sumber di atas gambar target
  • Pindahkan gambar sumber dengan 1 piksel
    • bitwise-DAN semua piksel yang tumpang tindih
    • jumlah semua 1s
  • ...

Mengubah gambar abu-abu menjadi biner dan kemudian melakukan ini mungkin cukup baik.

Awan titik

Jika sumber dan target adalah kedua pola titik, metode yang lebih cepat adalah menemukan pusat setiap titik (berkorelasi silang satu kali dengan titik yang diketahui dan kemudian menemukan puncak) dan menyimpannya sebagai satu set titik, kemudian mencocokkan sumber untuk menargetkan dengan memutar, menerjemahkan, dan menemukan kesalahan kuadrat terkecil antara titik-titik terdekat dalam dua set.

endolith
sumber
1
Itu benar, untuk masalah yang diselidiki tidak ada penskalaan tetapi rotasi dapat terjadi. Terima kasih atas tautan dan jawabannya.
Pengembang
@ Pengembang: Ya, ini akan berhasil kalau begitu, tetapi mungkin ada cara yang lebih baik. Jika itu hanya gambar biner, korelasi silang akan jauh lebih cepat. (Apakah ada yang disebut FFT untuk sinyal biner?) Apakah rotasi arbitrer? Anda harus bereksperimen dengan seperangkat nilai rotasi yang memberikan hasil yang baik, seperti bertambah 1 derajat, atau 5 derajat, dll.
endolith
1
Ya itu adalah masalah biner. Saya juga ingat dari suatu tempat bahwa ada suatu metode untuk menemukan sinyal yang lebih pendek yang dimodulasi pada sinyal yang lebih panjang dengan amplitudo yang berbeda. Saya ingat terlepas dari kerumitannya itu bekerja dengan sangat baik menunjukkan pick point sebagai titik awal kejadian. Karena masalahnya adalah dalam 2D, tidak jelas bagi saya bagaimana menggunakan konsep serupa. Ini juga rumit karena rotasi yang berlaku dalam 2D.
Pengembang
1
Ya, ini menjadi tidak mungkin ketika menambahkan kebebasan rotasi. Inilah sebabnya mengapa metode seperti RANSAC dikembangkan. Saya pikir ini membantu untuk berpikir di luar kotak DSP yang satu ini.
Matt M.
@MattM .: Berhasil, ini hanya lambat. :)
endolith
22

Dari perspektif visi komputer: masalah dasar adalah memperkirakan homografi antara set titik target Anda dan subset poin dalam set besar. Dalam kasus Anda, hanya dengan rotasi, itu akan menjadi homografi afin. Anda harus melihat ke metode RANSAC . Ini dirancang untuk menemukan kecocokan dalam satu set dengan banyak outlier. Jadi, Anda dipersenjatai dengan dua kata kunci penting, homografi dan RANSAC .

OpenCV menawarkan alat untuk menghitung solusi ini, tetapi Anda juga dapat menggunakan MATLAB. Berikut ini adalah contoh RANSAC menggunakan OpenCV . Dan implementasi lengkap lainnya .

Aplikasi khas mungkin untuk menemukan sampul buku dalam gambar. Anda memiliki gambar sampul buku, dan foto buku di atas meja. Pendekatannya bukan untuk melakukan pencocokan templat, tetapi untuk menemukan sudut-sudut yang menonjol pada setiap gambar, dan membandingkan set poin tersebut. Masalah Anda terlihat seperti bagian kedua dari proses ini - menemukan titik yang diatur dalam awan besar. RANSAC dirancang untuk melakukan ini dengan kuat.

masukkan deskripsi gambar di sini

Saya kira metode korelasi silang juga dapat bekerja untuk Anda karena datanya sangat bersih. Masalahnya adalah, Anda menambah derajat kebebasan dengan rotasi, dan metode ini menjadi sangat lambat.

Matt M.
sumber
Saya menambahkan sedikit lebih detail dalam pertanyaan. Saya akan memeriksa secara mendalam tautan Anda namun kesan singkatnya adalah mereka adalah konsep yang berbeda!
Pengembang
1
Sepertinya itu memang masalah RANSAC / homografi :)
Matt M.
Baik. Itu konsep baru bagi saya. Saya akan mencobanya sesegera mungkin. Jika saya menghadapi kesulitan, saya akan berbagi dengan Anda, anggota komunitas yang hebat dan suportif.
Pengembang
Sederhana T: Apakah mungkin / layak untuk menerapkan metode RANSAC / homografi ke cloud titik 3D?
Pengembang
Ini bukan solusi yang valid. Sayangnya pertanyaannya tidak mengandung informasi intensitas dan oleh karena itu skema deskripsi sederhana tidak akan berfungsi. Masalahnya agak lebih geometris dari itu.
Tolga Birdal
3

Jika polanya jarang biner, Anda dapat melakukan kovarians vektor koordinat sederhana alih-alih gambar. Ambil koordinat titik di sub-jendela yang disortir ke kiri, buat vektor dari semua koordinat, dan hitung kovarians dengan vektor yang dibuat dari koordinat titik pola yang disortir ke kiri. Anda juga bisa menggunakan beban. Setelah itu buat brute force tetangga terdekat untuk mencari kovarians maks pada beberapa grid di jendela besar (dan juga grid dalam sudut rotasi). Setelah menemukan perkiraan koordinat dengan pencarian, Anda dapat memperbaikinya dengan metode kuadrat terkecil reweighted.

Gagasan PS, alih-alih bekerja dengan gambar, Anda dapat bekerja dengan koordinat piksel yang tidak nol. Pencarian tetangga terdekat yang umum. Anda harus melakukan pencarian lengkap dari semua ruang pencarian, baik translasi maupun rotasi menggunakan beberapa kisi, yaitu beberapa langkah dalam koordinat dan sudut rot. Untuk setiap koordinat / sudut Anda mengambil subset piksel di jendela dengan pusat dengan koordinat yang diputar ke sudut itu, mengambil koordinatnya (rel ke pusat) dan membandingkannya dengan koordinat piksel dari pola yang Anda cari. Anda harus memastikan bahwa di kedua set poin diurutkan dengan cara yang sama. Anda menemukan koordinat dengan perbedaan minimum (kovarians maksimum). Setelah pencocokan kasar itu, Anda dapat menemukan kecocokan yang tepat dengan beberapa metode optimasi. Maaf saya tidak bisa menyampaikannya lebih sederhana dari itu.

mirror2image
sumber
1
Apakah Anda memberi kami contoh dengan lebih banyak penjelasan tentang ide Anda? Versi jawaban Anda saat ini membingungkan saya.
Pengembang
3

Saya sangat terkejut mengapa tidak ada yang menyebutkan metode keluarga Generalized Hough Transform . Mereka langsung memecahkan masalah khusus ini.

Inilah yang saya usulkan:

  1. Ambil templat dan buat tabel-R , buat indeks tepi templat. Tepi yang saya pilih adalah sebagai berikut:

masukkan deskripsi gambar di sini

  1. Gunakan implementasi OpenCV default dari transformasi Hough umum untuk mendapatkan: masukkan deskripsi gambar di sini

di mana lokasi yang cocok ditandai. Metode yang sama masih akan berfungsi bahkan jika tepinya berkurang menjadi satu titik, karena metode ini tidak memerlukan intensitas gambar.

Selain itu, penanganan rotasi sangat alami untuk skema Hough. Bahkan, untuk kasus 2D, itu hanya dimensi tambahan dalam akumulator. Jika Anda ingin masuk ke rincian membuatnya benar-benar efisien M. Ulrich menjelaskan banyak trik dalam makalahnya .

Tolga Birdal
sumber