Pengakuan Pola Titik

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:

Pembaruan 1:
Gambar berikut menunjukkan pandangan yang sedikit lebih realistis dari masalah yang sedang diselidiki.

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.

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.

• Mendaftarkan Gambar Menggunakan Korelasi Lintas-Normalisasi
• Pencocokan dan konvolusi berbasis template

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:

Target:

Korelasi silang:

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
  • bitwise-DAN semua piksel yang tumpang tindih (jauh lebih cepat daripada multiplikasi)
  • jumlah semua 1s di area yang tumpang tindih
• 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.

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.

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.

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.

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:

2. Gunakan implementasi OpenCV default dari transformasi Hough umum untuk mendapatkan:

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 .

Ini adalah aplikasi yang bagus untuk hashing geometris. halaman wikipedia geometris hashing