Cari gambar serupa, parsing satu algoritma

Saya baru-baru ini harus menyelesaikan masalah mengoptimalkan pencarian untuk duplikat gambar.

Solusi yang ada berjalan pada perpustakaan Python yang cukup terkenal, Pencocokan Gambar , berdasarkan TANDA TANGAN GAMBAR UNTUK SETIAP JENIS GAMBAR, yang ditulis oleh H. Chi Wong, Marshall Bern, dan David Goldberg.

Karena beberapa alasan, diputuskan untuk menulis ulang semuanya ke Kotlin, pada saat yang sama meninggalkan penyimpanan dan pencarian di ElasticSearch, yang membutuhkan lebih banyak sumber daya, baik besi dan manusia, untuk dukungan dan administrasi, demi mencari dalam cache dalam memori lokal.

Untuk memahami cara kerjanya, saya harus membenamkan diri dalam "referensi" kode Python, karena karya aslinya kadang-kadang tidak sepenuhnya jelas, dan di beberapa tempat itu membuat saya ingat "cara menggambar burung hantu". Sebenarnya, saya ingin membagikan hasil penelitian ini, sekaligus menceritakan beberapa optimasi, baik dari segi volume data dan kecepatan pencarian. Mungkin seseorang akan berguna.

Penafian: Ada kemungkinan bahwa saya mengacaukan suatu tempat, apakah itu salah atau tidak secara optimal. Yah, saya akan senang dengan kritik dan komentar. :)

Bagaimana cara kerjanya:

1. Gambar dikonversi ke format hitam-putih 8-bit (satu titik bernilai satu byte pada nilai 0-255)
2. Gambar dipotong sedemikian rupa untuk membuang 5% dari akumulasi perbedaan (lebih banyak di bawah) dari masing-masing dari empat sisi. Misalnya, bingkai hitam di sekitar gambar.
3. Grid pekerjaan dipilih (9x9 secara default), yang simpulnya akan berfungsi sebagai titik referensi dari tanda tangan gambar.
4. Untuk setiap titik referensi, berdasarkan area tertentu di sekitarnya, kecerahannya dihitung.
5. Untuk setiap titik referensi, dihitung berapa banyak lebih terang / lebih gelap dari delapan tetangganya. Lima gradasi digunakan, dari -2 (lebih gelap) hingga 2 (lebih terang).
6. Semua "kegembiraan" ini terungkap dalam array satu dimensi (vektor) dan disebut oleh tanda tangan gambar.

Kesamaan dua gambar diperiksa sebagai berikut:



Semakin rendah d, semakin baik. Bahkan, d <0,3 hampir merupakan jaminan identitas.

Sekarang lebih detail.

Langkah pertama

Saya berpikir bahwa berbicara tentang konversi ke skala abu-abu tidak masuk akal.

Langkah kedua

Katakanlah kita memiliki gambar seperti ini:


Dapat dilihat bahwa ada bingkai hitam 3 piksel di kanan dan kiri dan 2 piksel di atas dan bawah, yang tidak kita perlukan sama sekali dibandingkan

Batas cutoff ditentukan oleh algoritma berikut:

1. Untuk setiap kolom, kami menghitung jumlah perbedaan absolut dari elemen tetangga.
   
2. Kami memangkas kiri dan kanan jumlah piksel yang kontribusinya terhadap perbedaan kumulatif total kurang dari 5%.

Kami melakukan hal yang sama untuk kolom.

Klarifikasi penting: jika dimensi gambar yang dihasilkan tidak cukup untuk langkah 4, maka kami tidak memotong!

Langkah ketiga

Nah, semuanya cukup sederhana di sini, kami membagi gambar menjadi bagian yang sama dan memilih titik nodal.

Langkah keempat

Kecerahan titik jangkar dihitung sebagai kecerahan rata-rata semua titik di area persegi di sekitarnya. Dalam karya aslinya, rumus berikut digunakan untuk menghitung sisi-sisi dari persegi ini:

Langkah kelima

Untuk setiap titik referensi, perbedaan kecerahannya dengan kecerahan delapan tetangganya dihitung. Untuk titik-titik yang tidak ada tetangganya (baris atas dan bawah, kolom kiri dan kanan), perbedaannya diambil sebagai 0.

Selanjutnya, perbedaan-perbedaan ini dikurangi menjadi lima gradasi:


Ternyata sesuatu seperti matriks ini:

Langkah keenam

Saya pikir tidak ada penjelasan yang diperlukan.

Dan sekarang tentang optimasi

Dalam karya asli, benar menunjukkan bahwa dari tanda tangan yang dihasilkan adalah mungkin untuk sepenuhnya menghapus nilai nol di sepanjang tepi matriks, karena mereka akan identik untuk semua gambar.


Namun, jika Anda perhatikan dengan seksama, Anda dapat melihat bahwa untuk dua tetangga mana pun, nilai timbal balik mereka akan sama nilainya. Oleh karena itu, pada kenyataannya, Anda dapat dengan aman membuang empat nilai duplikat untuk setiap titik referensi, mengurangi ukuran tanda tangan hingga setengah (tidak termasuk nol sisi).


Jelas, ketika menghitung jumlah kuadrat, untuk setiap x pasti akan ada modulo x 'yang sama dan rumus untuk menghitung norma dapat dituliskan sesuatu seperti ini (tanpa mempelajari pengindeksan kembali):


Ini berlaku baik untuk pembilang dan untuk kedua istilah penyebut.

Lebih lanjut dalam karya asli, dicatat bahwa tiga bit cukup untuk menyimpan setiap gradasi. Misalnya, dalam Unsigned Long akan muat 21 gradasi. Ini adalah penghematan yang cukup besar dalam ukuran, tetapi, di sisi lain, menambah kompleksitas ketika menghitung jumlah kuadrat dari perbedaan antara dua tanda tangan. Saya harus mengatakan bahwa ide ini benar-benar mengaitkan saya dengan sesuatu dan tidak melepaskan selama beberapa hari, sampai suatu malam ide tentang makan ikan , tempat untuk menyimpan dan menyederhanakan perhitungan. Awasi tangan Anda.

Kami menggunakan skema seperti itu untuk penyimpanan, 4 bit per gradasi:

Ya, hanya 16 gradasi yang akan cocok menjadi satu Unsigned Long, melawan 21, tetapi kemudian susunan perbedaan dari dua tanda tangan akan dihitung dengan satu xor dan 15 shift ke kanan dengan perhitungan jumlah bit yang ditetapkan untuk setiap iterasi dari shift. Yaitu


Tanda itu tidak masalah bagi kami, karena semua nilai akan dikuadratkan.

Selain itu, jika nilai ambang jarak ditentukan sebelumnya, nilai-nilai yang tidak menarik bagi kami lagi, maka setelah menari sedikit di sekitar rumus perhitungan, Anda dapat memperoleh kondisi penyaringan yang agak ringan untuk sejumlah bit yang ditetapkan.

Rincian lebih lanjut tentang optimalisasi algoritma ini, dengan contoh kode, dapat ditemukan di artikel sebelumnya . Saya secara terpisah merekomendasikan membaca komentar tentang itu - masyaman penduduk Khabrovsk mengusulkan beberapa metode yang agak menarik untuk menghitung, termasuk mengemas gradasi dalam tiga bit, menggunakan bit magic.

Sebenarnya itu saja. Terima kasih atas perhatian anda :)