Sidik jari gambar untuk membandingkan kesamaan banyak gambar

Saya perlu membuat sidik jari dari banyak gambar (sekitar 100.000 yang ada, 1000 baru per hari, RGB, JPEG, ukuran maks 800x800) untuk membandingkan setiap gambar dengan setiap gambar lainnya dengan sangat cepat. Saya tidak dapat menggunakan metode perbandingan biner karena gambar yang hampir mirip juga harus dikenali.

Yang terbaik adalah pustaka yang ada, tetapi juga beberapa petunjuk untuk algoritme yang ada akan banyak membantu saya.

Algoritme penghitungan hashing atau CRC normal tidak berfungsi dengan baik dengan data gambar. Sifat dimensi informasi harus diperhitungkan.

Jika Anda memerlukan sidik jari yang sangat kuat, sehingga transformasi affine (penskalaan, rotasi, terjemahan, membalik) diperhitungkan, Anda dapat menggunakan transformasi Radon pada sumber gambar untuk menghasilkan pemetaan normatif dari data gambar - simpan ini dengan setiap gambar dan lalu bandingkan hanya dengan sidik jarinya. Ini adalah algoritma yang kompleks dan bukan untuk orang yang lemah hati.

beberapa solusi sederhana dimungkinkan:

1. Buat histogram luminositas untuk gambar sebagai sidik jari
2. Buat versi yang diperkecil dari setiap gambar sebagai sidik jari
3. Gabungkan teknik (1) dan (2) ke dalam pendekatan hybrid untuk meningkatkan kualitas perbandingan

Histogram luminositas (terutama yang dipisahkan menjadi komponen RGB) adalah sidik jari yang wajar untuk sebuah gambar - dan dapat diimplementasikan dengan cukup efisien. Mengurangkan satu histogram dari yang lain akan menghasilkan histogram baru yang dapat Anda proses untuk memutuskan seberapa mirip dua gambar tersebut. Histogram, karena hanya mengevaluasi distribusi dan kemunculan luminositas / informasi warna menangani transformasi affine dengan cukup baik. Jika Anda mengukur informasi luminositas setiap komponen warna hingga nilai 8-bit, penyimpanan 768 byte sudah cukup untuk sidik jari dari gambar dengan ukuran apa pun yang wajar. Histogram luminositas menghasilkan negatif palsu saat informasi warna dalam gambar dimanipulasi. Jika Anda menerapkan transformasi seperti kontras / kecerahan, posterize, perubahan warna, perubahan informasi luminositas.

Menggunakan gambar berskala adalah cara lain untuk mengurangi kepadatan informasi gambar ke tingkat yang lebih mudah untuk dibandingkan. Pengurangan di bawah 10% dari ukuran gambar asli umumnya kehilangan terlalu banyak informasi untuk digunakan - sehingga gambar 800x800 piksel dapat diperkecil menjadi 80x80 dan masih memberikan informasi yang cukup untuk melakukan sidik jari yang layak. Tidak seperti data histogram, Anda harus melakukan penskalaan anisotropik pada data gambar jika resolusi sumber memiliki rasio aspek yang berbeda-beda. Dengan kata lain, memperkecil gambar 300x800 menjadi thumbnail 80x80 menyebabkan deformasi gambar, sehingga jika dibandingkan dengan gambar 300x500 (yang sangat mirip) akan menyebabkan negatif palsu. Sidik jari thumbnail juga sering menghasilkan negatif palsu saat transformasi affine terlibat. Jika Anda membalik atau memutar gambar,

Menggabungkan kedua teknik adalah cara yang masuk akal untuk melindungi taruhan Anda dan mengurangi terjadinya positif palsu dan negatif palsu.

Ada pendekatan ad-hoc yang jauh lebih sedikit daripada varian gambar yang diperkecil yang telah diusulkan di sini yang mempertahankan cita rasa umumnya, tetapi yang memberikan dasar matematika yang jauh lebih ketat untuk apa yang sedang terjadi.

Ambil gambar wavelet Haar . Pada dasarnya, Haar wavelet adalah rangkaian perbedaan dari gambar beresolusi lebih rendah ke setiap gambar beresolusi lebih tinggi, tetapi dibobotkan oleh seberapa dalam Anda berada di 'pohon' mipmap. Perhitungannya mudah. Kemudian setelah Anda memiliki wavelet Haar dengan bobot yang tepat, buang semua kecuali k koefisien terbesar (dalam hal nilai absolut), normalisasi vektor dan simpan.

Jika Anda mengambil perkalian titik dari dua vektor yang dinormalisasi itu memberi Anda ukuran kemiripan dengan 1 hampir identik. Saya memposting lebih banyak informasi di sini .

Anda pasti harus melihat phash .

Untuk perbandingan gambar ada proyek php ini: https://github.com/kennethrapp/phasher

Dan klon javascript kecil saya : https://redaktor.me/phasher/demo_js/index.html

Sayangnya ini berbasis "bitcount" tetapi akan mengenali gambar yang diputar. Pendekatan lain dalam javascript adalah membangun histogram luminositas dari gambar dengan bantuan kanvas. Anda dapat memvisualisasikan histogram poligon di kanvas dan membandingkan poligon tersebut di database Anda (mis. MySQL spatial ...)

Dahulu kala saya mengerjakan sistem yang memiliki beberapa karakteristik serupa, dan ini adalah perkiraan dari algoritme yang kami ikuti:

1. Bagilah gambar menjadi beberapa zona. Dalam kasus kami, kami berurusan dengan video resolusi 4: 3, jadi kami menggunakan 12 zona. Melakukan ini akan menghilangkan resolusi gambar sumber dari gambar.
2. Untuk setiap zona, hitung warna keseluruhan - rata-rata semua piksel di zona tersebut
3. Untuk seluruh gambar, hitung warna keseluruhan - rata-rata semua zona

Jadi untuk setiap gambar, Anda menyimpan n + 1nilai integer, di mana njumlah zona yang Anda lacak.

Untuk perbandingan, Anda juga perlu melihat setiap saluran warna satu per satu.

1. Untuk gambar keseluruhan, bandingkan saluran warna untuk warna keseluruhan untuk melihat apakah mereka berada dalam ambang tertentu - katakanlah, 10%
2. Jika gambar berada dalam ambang batas, selanjutnya bandingkan setiap zona. Jika semua zona juga berada dalam ambang batas, gambar tersebut cukup cocok sehingga Anda setidaknya dapat menandainya untuk perbandingan lebih lanjut.

Ini memungkinkan Anda dengan cepat membuang gambar yang tidak cocok; Anda juga dapat menggunakan lebih banyak zona dan / atau menerapkan algoritme secara rekursif untuk mendapatkan keyakinan kecocokan yang lebih kuat.

Mirip dengan jawaban Ic - Anda dapat mencoba membandingkan gambar pada berbagai resolusi. Jadi setiap gambar disimpan sebagai 1x1, 2x2, 4x4 .. 800x800. Jika resolusi terendah tidak cocok (tunduk pada ambang batas), Anda dapat langsung menolaknya. Jika cocok, Anda dapat membandingkannya pada resolusi lebih tinggi berikutnya, dan seterusnya ..

Selain itu - jika gambar memiliki struktur yang serupa, seperti gambar medis, Anda mungkin dapat mengekstrak struktur tersebut menjadi deskripsi yang lebih mudah / cepat untuk dibandingkan.

Jadi, Anda ingin melakukan "pencocokan sidik jari" yang sangat berbeda dari "pencocokan gambar". Analisis sidik jari telah dipelajari secara mendalam selama 20 tahun terakhir, dan beberapa algoritme menarik telah dikembangkan untuk memastikan tingkat deteksi yang tepat (sehubungan dengan pengukuran FAR dan FRR - Tingkat Penerimaan Palsu dan Tingkat Penolakan Palsu ).

Saya menyarankan Anda untuk lebih melihat kelas teknik deteksi LFA (Local Feature Analysis) , yang sebagian besar dibangun di atas inspeksi kecil-kecilan. Minutiae adalah karakteristik khusus dari setiap sidik jari, dan telah diklasifikasikan dalam beberapa kelas. Memetakan gambar raster ke peta detail adalah apa yang sebenarnya dilakukan oleh sebagian besar Otoritas Publik untuk mengajukan penjahat atau teroris.

Lihat di sini untuk referensi lebih lanjut

Untuk perbandingan gambar iPhone dan pengembangan kemiripan gambar, lihat: http://sites.google.com/site/imagecomparison/

Untuk melihatnya beraksi, lihat pencarian visual eyeBuy di iTunes AppStore.

Pada 2015 (kembali ke masa depan ... pada pertanyaan 2009 ini yang sekarang menduduki peringkat tinggi di Google), kesamaan gambar dapat dihitung menggunakan teknik Deep Learning. Keluarga algoritma yang dikenal sebagai Auto Encoders dapat membuat representasi vektor yang dapat dicari kemiripannya. Ada demo di sini .

Salah satu cara Anda dapat melakukannya adalah dengan mengubah ukuran gambar dan menurunkan resolusi secara signifikan (mungkin 200x200?), Menyimpan versi yang lebih kecil (rata-rata piksel) untuk melakukan perbandingan. Kemudian tentukan ambang toleransi dan bandingkan setiap piksel. Jika RGB dari semua piksel berada dalam toleransi, Anda memiliki kecocokan.

Proses awal Anda adalah O (n ^ 2) tetapi jika Anda membuat katalog semua kecocokan, setiap gambar baru hanyalah algoritme O (n) untuk dibandingkan (Anda hanya perlu membandingkannya dengan setiap gambar yang disisipkan sebelumnya). Namun pada akhirnya akan rusak karena daftar gambar untuk dibandingkan menjadi lebih besar, tetapi saya pikir Anda aman untuk sementara waktu.

Setelah 400 hari berjalan, Anda akan memiliki 500.000 gambar, yang berarti (dengan mengabaikan waktu untuk mengubah ukuran gambar) 200(H)*200(W)*500,000(images)*3(RGB)= 60.000.000.000 perbandingan. Jika setiap gambar sama persis, Anda akan tertinggal, tapi itu mungkin tidak akan menjadi masalah, bukan? Ingat, Anda dapat mendiskon gambar sebagai pertandingan segera setelah perbandingan tunggal berada di luar ambang batas Anda.

Apakah Anda benar-benar ingin membandingkan setiap gambar dengan yang lain? Apa aplikasinya? Mungkin Anda hanya perlu semacam pengindeksan dan pengambilan gambar berdasarkan deskriptor tertentu? Kemudian misalnya Anda dapat melihat standar MPEG-7 untuk Antarmuka Deskripsi Konten Multimedia. Kemudian Anda dapat membandingkan deskriptor gambar yang berbeda, yang tidak akan terlalu akurat tetapi jauh lebih cepat.

Tampaknya algoritme hashing gambar khusus adalah area penelitian aktif tetapi mungkin penghitungan hash normal dari byte gambar akan berhasil.

Apakah Anda mencari gambar yang identik dengan byte daripada mencari gambar yang berasal dari sumber yang sama tetapi mungkin format atau resolusi yang berbeda (menurut saya sebagai masalah yang agak sulit).