Deteksi Gambar Hampir Duplikat [ditutup]

Sungguh cara yang cepat untuk mengurutkan kumpulan gambar tertentu berdasarkan kemiripannya satu sama lain.

Saat ini saya memiliki sistem yang melakukan analisis histogram antara dua gambar, tetapi ini adalah operasi yang sangat mahal dan tampaknya terlalu berlebihan.

Secara optimal, saya mencari algoritme yang akan memberikan skor pada setiap gambar (misalnya skor integer, seperti RGB Average) dan saya bisa mengurutkan berdasarkan skor itu. Skor Identik atau skor yang bersebelahan adalah kemungkinan duplikat.

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994 

RGB Average per gambar menyebalkan, apakah ada yang serupa?

Telah banyak penelitian tentang pencarian gambar dan ukuran kesamaan. Ini bukan masalah yang mudah. Secara umum, satu gambar inttidak akan cukup untuk menentukan apakah gambar sangat mirip. Anda akan mendapatkan rasio positif palsu yang tinggi.

Namun, karena ada banyak penelitian yang dilakukan, Anda dapat melihat beberapa di antaranya. Misalnya, makalah ini (PDF) memberikan algoritma sidik jari gambar kompak yang cocok untuk menemukan gambar duplikat dengan cepat dan tanpa banyak menyimpan data. Sepertinya ini yang benar pendekatan yang jika Anda menginginkan sesuatu yang kuat.

Jika Anda mencari sesuatu yang lebih sederhana, tetapi pasti lebih ad-hoc, pertanyaan SO ini memiliki beberapa ide yang bagus.

Saya akan merekomendasikan mempertimbangkan untuk menjauh dari hanya menggunakan histogram RGB.

Pencernaan yang lebih baik dari gambar Anda dapat diperoleh jika Anda mengambil wavelet 2d Haar dari gambar (ini jauh lebih mudah daripada kedengarannya, hanya banyak rata-rata dan beberapa akar kuadrat digunakan untuk membobot koefisien Anda) dan hanya mempertahankan k terbesar koefisien tertimbang di wavelet sebagai vektor jarang, menormalkannya, dan menyimpannya untuk mengurangi ukurannya. Anda harus mengubah skala RG dan B menggunakan bobot persepsi sebelumnya setidaknya atau saya sarankan beralih ke YIQ (atau YCoCg, untuk menghindari derau kuantisasi) sehingga Anda dapat mengambil sampel informasi chrominance dengan tingkat kepentingan yang berkurang.

Anda sekarang dapat menggunakan perkalian titik dari dua vektor normalisasi renggang ini sebagai ukuran kemiripan. Pasangan gambar dengan hasil perkalian titik terbesar akan memiliki struktur yang sangat mirip. Manfaatnya karena sedikit tahan terhadap pengubahan ukuran, pergeseran rona dan tanda air, serta sangat mudah diterapkan dan dipadatkan.

Anda dapat menukar penyimpanan dan akurasi dengan menambah atau mengurangi k.

Mengurutkan berdasarkan skor numerik tunggal akan menjadi sulit untuk masalah klasifikasi semacam ini. Jika Anda memikirkannya, diperlukan gambar untuk hanya dapat 'berubah' sepanjang satu sumbu, tetapi ternyata tidak. Inilah mengapa Anda membutuhkan vektor fitur. Dalam kasus wavelet Haar, kira-kira di mana diskontinuitas paling tajam dalam gambar terjadi. Anda dapat menghitung jarak antara gambar secara berpasangan, tetapi karena yang Anda miliki hanyalah metrik jarak, pengurutan linier tidak memiliki cara untuk menyatakan 'segitiga' dari 3 gambar yang semuanya sama jauhnya. (misal, pikirkan gambar yang semuanya hijau, gambar yang semuanya merah dan gambar yang semuanya biru.)

Itu berarti bahwa solusi nyata apa pun untuk masalah Anda akan memerlukan operasi O (n ^ 2) dalam jumlah gambar yang Anda miliki. Sedangkan jika dimungkinkan untuk melinierisasi ukuran, Anda dapat memerlukan O (n log n), atau O (n) jika ukuran tersebut cocok untuk, katakanlah, jenis radix. Meskipun demikian, Anda tidak perlu menghabiskan O (n ^ 2) karena dalam praktiknya Anda tidak perlu menyaring seluruh rangkaian, Anda hanya perlu menemukan barang yang lebih dekat dari ambang batas tertentu. Jadi dengan menerapkan salah satu dari beberapa teknik untuk mempartisi ruang vektor renggang Anda, Anda dapat memperoleh asimtotik yang jauh lebih cepat untuk masalah 'menemukan saya k dari gambar yang lebih mirip daripada ambang batas yang diberikan' daripada secara naif membandingkan setiap gambar dengan setiap gambar, memberi Anda apa Anda mungkin perlu ... jika tidak persis seperti yang Anda minta.

Bagaimanapun, saya menggunakan ini beberapa tahun yang lalu untuk efek yang baik secara pribadi ketika mencoba meminimalkan jumlah tekstur berbeda yang saya simpan, tetapi ada juga banyak kebisingan penelitian di ruang ini yang menunjukkan kemanjurannya (dan dalam hal ini membandingkan ke bentuk klasifikasi histogram yang lebih canggih):

http://www.cs.princeton.edu/cass/papers/spam_ceas07.pdf

Jika Anda membutuhkan akurasi yang lebih baik dalam pendeteksian, algoritma minHash dan tf-idf dapat digunakan dengan Haar wavelet (atau histogram) untuk menangani pengeditan dengan lebih kuat:

http://cmp.felk.cvut.cz/~chum/papers/chum_bmvc08.pdf

Terakhir, Stanford memiliki penelusuran gambar berdasarkan varian yang lebih eksotis dari pendekatan semacam ini, berdasarkan melakukan lebih banyak ekstraksi fitur dari wavelet untuk menemukan bagian gambar yang diputar atau diskalakan, dll, tetapi itu mungkin jauh melampaui jumlah pekerjaan Anda. ingin melakukannya.

http://wang14.ist.psu.edu/cgi-bin/zwang/regionsearch_show.cgi

Saya menerapkan algoritme yang sangat andal untuk ini yang disebut Fast Multiresolution Image Querying . Kode saya (kuno, tidak terawat) untuk itu ada di sini .

Apa yang dilakukan Fast Multiresolution Image Querying adalah membagi gambar menjadi 3 bagian berdasarkan ruang warna YIQ (lebih baik untuk mencocokkan perbedaan daripada RGB). Kemudian gambar pada dasarnya dikompresi menggunakan algoritma wavelet sampai hanya fitur paling menonjol dari setiap ruang warna yang tersedia. Titik-titik ini disimpan dalam struktur data. Gambar kueri melalui proses yang sama, dan fitur menonjol di gambar kueri dicocokkan dengan yang ada di database yang disimpan. Semakin banyak kecocokan, semakin besar kemungkinan gambarnya serupa.

Algoritme ini sering digunakan untuk fungsionalitas "kueri dengan sketsa". Perangkat lunak saya hanya mengizinkan memasukkan gambar kueri melalui URL, jadi tidak ada antarmuka pengguna. Namun, menurut saya ini bekerja sangat baik untuk mencocokkan thumbnail dengan versi besar gambar itu.

Jauh lebih mengesankan daripada software saya adalah Retrievr yang memungkinkan Anda mencoba algoritma FMIQ menggunakan Flickr gambar sebagai sumber. Sangat keren! Cobalah melalui sketsa atau menggunakan gambar sumber, dan Anda dapat melihat seberapa baik kerjanya.

Sebuah gambar memiliki banyak fitur, jadi kecuali Anda mempersempit diri Anda menjadi satu, seperti kecerahan rata-rata, Anda berurusan dengan masalah ruang dimensi-n.

Jika saya meminta Anda untuk menetapkan satu bilangan bulat ke kota-kota di dunia, jadi saya tahu mana yang dekat, hasilnya tidak akan bagus. Anda mungkin, misalnya, memilih zona waktu sebagai bilangan bulat tunggal dan mendapatkan hasil yang bagus untuk kota-kota tertentu. Namun, kota di dekat kutub utara dan kota lain di dekat kutub selatan juga bisa berada di zona waktu yang sama, meskipun mereka berada di ujung planet yang berlawanan. Jika saya membiarkan Anda menggunakan dua bilangan bulat, Anda bisa mendapatkan hasil yang sangat bagus dengan garis lintang dan garis bujur. Masalahnya sama untuk kemiripan gambar.

Semua yang dikatakan, ada algoritme yang mencoba mengelompokkan gambar serupa bersama-sama, yang secara efektif adalah apa yang Anda minta. Inilah yang terjadi bila Anda melakukan deteksi wajah dengan Picasa. Bahkan sebelum Anda mengidentifikasi wajah apa pun, fitur ini akan mengelompokkan wajah yang mirip sehingga mudah untuk melihat sekumpulan wajah yang mirip dan memberi sebagian besar dari mereka nama yang sama.

Ada juga teknik yang disebut Principle Component Analysis, yang memungkinkan Anda mengurangi data n-dimensi menjadi beberapa dimensi yang lebih kecil. Jadi gambar dengan n fitur bisa direduksi menjadi satu fitur. Namun demikian, ini masih bukan pendekatan terbaik untuk membandingkan gambar.

Ada pustaka C ("libphash" - http://phash.org/ ) yang akan menghitung "hash perseptual" dari sebuah gambar dan memungkinkan Anda mendeteksi gambar serupa dengan membandingkan hash (jadi Anda tidak perlu membandingkan setiap gambar langsung terhadap setiap gambar lainnya) tetapi sayangnya tampaknya tidak terlalu akurat ketika saya mencobanya.

Anda harus memutuskan apa yang "serupa". Kontras? Warna?

Apakah gambar "mirip" dengan gambar yang sama secara terbalik?

Saya yakin Anda dapat menemukan banyak "panggilan akrab" dengan memecah gambar menjadi bagian 4x4 dan mendapatkan warna rata-rata untuk setiap sel kisi. Anda akan memiliki enam belas skor per gambar. Untuk menilai kesamaan, Anda hanya perlu melakukan penjumlahan kuadrat perbedaan antara gambar.

Saya rasa satu hash tidak masuk akal, kecuali bertentangan dengan konsep tunggal seperti hue, atau kecerahan, atau kontras.

Inilah ide Anda:

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994

Pertama-tama, saya akan menganggap ini adalah bilangan desimal yang R * (2 ^ 16) + G * (2 ^ 8) + B, atau semacamnya. Jelas itu tidak bagus karena warna merah terlalu berbobot.

Pindah ke ruang HSV akan lebih baik. Anda dapat menyebarkan bit HSV ke dalam hash, atau Anda dapat menetapkan H atau S atau V satu per satu, atau Anda dapat memiliki tiga hash per gambar.

Satu hal lagi. Jika Anda melakukan bobot R, G, dan B. Bobot hijau paling tinggi, lalu merah, lalu biru agar sesuai dengan kepekaan visual manusia.

Di era layanan web, Anda dapat mencoba http://tineye.com

Pertanyaan Cara yang baik untuk mengidentifikasi gambar yang mirip? tampaknya memberikan solusi untuk pertanyaan Anda.

Saya berasumsi bahwa perangkat lunak pencarian gambar duplikat lainnya melakukan FFT pada gambar, dan menyimpan nilai frekuensi yang berbeda sebagai vektor:

Image1 = (u1, u2, u3, ..., un)
Image2 = (v1, v2, v3, ..., vn)

dan kemudian Anda dapat membandingkan dua gambar untuk persamaan dengan menghitung jarak antara vektor bobot dua gambar:

distance = Sqrt(
     (u1-v1)^2 +
     (u2-v2)^2 +
     (u2-v3)^2 +
     ...
     (un-vn)^2);

Salah satu solusinya adalah dengan melakukan perbandingan RMS / RSS pada setiap pasang gambar yang diperlukan untuk melakukan semacam gelembung. Kedua, Anda dapat melakukan FFT pada setiap gambar dan melakukan beberapa sumbu rata-rata untuk mengambil satu bilangan bulat untuk setiap gambar yang akan Anda gunakan sebagai indeks untuk diurutkan. Anda dapat mempertimbangkan untuk melakukan perbandingan apa pun pada versi asli yang diubah ukurannya (25%, 10%) tergantung pada seberapa kecil perbedaan yang Anda pilih untuk diabaikan dan berapa banyak percepatan yang Anda butuhkan. Beri tahu saya jika solusi ini menarik, dan kita dapat berdiskusi atau saya dapat memberikan kode contoh.

Kebanyakan pendekatan modern untuk mendeteksi deteksi gambar duplikat Dekat menggunakan deteksi titik menarik dan deskriptor yang mendeskripsikan area di sekitar titik tersebut. Seringkali SIFT digunakan. Kemudian Anda dapat membuat quatize deskriptor dan menggunakan cluster sebagai kosakata visual kata.

Jadi jika kita melihat rasio kata-kata visual yang umum dari dua gambar dengan semua kata-kata visual dari gambar-gambar ini, Anda memperkirakan kesamaan antar gambar. Ada banyak sekali artikel menarik. Salah satunya adalah Near Duplicate Image Detection: minHash dan tf-idf Weighting

Misalnya menggunakan ekstensi IMMI dan IMMI, Anda dapat memeriksa berbagai cara untuk mengukur kesamaan antara gambar: http://spl.utko.feec.vutbr.cz/en/component/content/article/46-image-processing-extension- untuk-rapidminer-5

Dengan menentukan beberapa ambang dan memilih beberapa metode, Anda dapat mengukur kesamaan.