Algoritma apa yang digunakan Google untuk situs "Search By Image"?

Apa tebakan terbaik Anda tentang cara Pencarian Gambar Google? Saya dapat mengunggah foto dan dapat mencari gambar yang serupa. Algoritma apa yang digunakan untuk mengidentifikasi gambar yang serupa?

Saya tidak tahu algoritma apa yang digunakan Google. Tetapi, karena Anda menginginkan tebakan terbaik, izinkan saya memberikan beberapa ide tentang bagaimana sistem serupa dapat dibangun .

Seluruh bidang yang berhubungan dengan pencarian-gambar-basis-oleh-gambar disebut Content Based Image Retrieval (CBIR) . Idenya adalah untuk, entah bagaimana, membangun representasi gambar (tidak selalu dapat dimengerti oleh manusia) yang berisi informasi tentang konten gambar .

Ada dua pendekatan dasar:

• pengambilan menggunakan fitur tingkat rendah (lokal): warna, tekstur, bentuk pada bagian-bagian tertentu dari gambar (gambar adalah kumpulan deskriptor fitur lokal )
• pendekatan semantik di mana gambar, dalam beberapa cara, direpresentasikan sebagai kumpulan objek dan hubungan mereka

Pendekatan lokal tingkat rendah diteliti dengan sangat baik. Pendekatan terbaik saat ini mengekstrak fitur lokal (ada pilihan algoritma ekstraksi fitur yang terlibat di sini) dan menggunakan deskriptor lokal mereka (sekali lagi, pilihan deskriptor) untuk membandingkan gambar.

Dalam karya-karya baru, deskriptor lokal dikelompokkan terlebih dahulu dan kemudian cluster diperlakukan sebagai kata - kata visual - teknik ini kemudian sangat mirip dengan pencarian dokumen Google, tetapi menggunakan kata-kata visual, bukan kata-kata.

Anda dapat menganggap kata-kata visual sebagai padanan dengan akar kata dalam bahasa: misalnya, kata-kata: kerja, kerja, bekerja semua milik kata akar kata yang sama.

Salah satu kelemahan dari metode semacam ini adalah bahwa mereka biasanya berkinerja rendah pada gambar dengan tekstur rendah.

Saya sudah memberikan dan melihat banyak jawaban yang merinci pendekatan ini, jadi saya hanya akan memberikan tautan ke jawaban-jawaban itu:

• CBIR: 1 , 2
• ekstraksi / deskripsi fitur: 1 , 2 , 3 , 4

Pendekatan semantik biasanya didasarkan pada representasi hierarkis dari keseluruhan gambar. Pendekatan-pendekatan ini belum disempurnakan, terutama untuk tipe gambar umum. Ada beberapa keberhasilan dalam menerapkan teknik semacam ini pada domain gambar tertentu.

Saat ini saya sedang dalam penelitian pendekatan ini, saya tidak dapat membuat kesimpulan. Nah, yang mengatakan, saya menjelaskan ide umum di balik teknik-teknik ini dalam jawaban ini .

Sekali lagi, singkat: ide umumnya adalah untuk merepresentasikan gambar dengan struktur berbentuk pohon, di mana daun berisi detail gambar dan objek dapat ditemukan di simpul yang lebih dekat ke akar pohon tersebut. Kemudian, entah bagaimana, Anda membandingkan sub-pohon untuk mengidentifikasi objek yang terdapat dalam gambar yang berbeda.

Berikut adalah beberapa referensi untuk representasi pohon yang berbeda. Saya tidak membaca semuanya, dan beberapa dari mereka menggunakan representasi seperti ini untuk segmentasi daripada CBIR, tapi tetap saja, ini dia:

• pohon partisi biner dan penyebutan pohon min / maks: P. Salembier, MHF Wilkinson: Operator Terhubung
• pohon partisi biner: V. Vilaplana, F. Marques, P. Selembier: Pohon Partisi Biner untuk Deteksi Objek
• pohon bentuk (pohon komponen): P. Monasse, F. Guichard: Komputasi Cepat Representasi Gambar Kontras-Invarian , C. Ballester, V. Castellis, P. Monasse: Pohon Bentuk Gambar
• pohon monoton: Y. Song, A. Zhang: Menganalisis gambar pemandangan dengan pohon monoton
• edit: menggali lebih lanjut menunjukkan bahwa pohon bentuk dan pohon monoton yang setara , kecuali pengolahan gambar di 4- / 8- (pohon bentuk) atau 6-konektivitas (monoton)
• pohon DAS ekstrema : A. Vichik, R. Keshet, D. Malah: Self-dual morfologi pada semilattice dan aplikasi pohon
• konektivitas terkendala, pohon alpha, daerah aliran air ultrametrik : P. Soille, L. Najman: Tentang representasi hierarkis morfologis untuk pemrosesan gambar dan pengelompokan data spasial

Selain jawaban penelope, ada dua pendekatan, hashing perceptual dan model bag-of-words yang fungsi dasarnya mudah diimplementasikan dan karenanya menyenangkan untuk dimainkan atau dipelajari, sebelum menjelajah ke wilayah yang lebih maju.

Hashing perseptual

Algoritma hashing perceptual bertujuan untuk membangun hash, yang tidak seperti hash kriptografi, akan memberikan nilai hash yang serupa, atau hampir serupa untuk gambar yang identik yang telah sedikit terdistorsi misalnya dengan penskalaan atau kompresi JPEG. Mereka melayani tujuan yang berguna dalam mendeteksi duplikat dekat dalam koleksi gambar.

Dalam bentuknya yang paling dasar, Anda dapat menerapkan ini sebagai berikut:

1. Konversi gambar ke skala abu-abu

2. Jadikan gambar Anda nol berarti

3. Hancurkan gambar Anda ke ukuran thumbnail, katakan [32x32]
4. Jalankan Discrete Cosine Transform dua dimensi
5. Tetap di kiri atas [8 x 8], komponen frekuensi rendah paling signifikan
6. Binari blok, berdasarkan tanda komponen

Hasilnya adalah hash 64 bit tangguh, karena didasarkan pada komponen frekuensi rendah gambar. Varian pada tema ini adalah untuk membagi setiap gambar menjadi 64 subblok dan membandingkan rata-rata gambar global dengan rata-rata subblok lokal dan menuliskan 1 atau 0 yang sesuai.

Hash perceptual diimplementasikan misalnya dengan phash

Model bag-of-words

Model bag-of-words bertujuan untuk secara semantik mengidentifikasi suatu gambar, misalnya semua gambar dengan anjing di dalamnya. Hal ini dilakukan dengan menggunakan tambalan gambar tertentu dalam semangat yang sama bahwa seseorang akan mengklasifikasikan dokumen teks berdasarkan kemunculan kata-kata tertentu. Seseorang dapat mengkategorikan kata-kata, mengucapkan "anjing" dan "anjing" dan menyimpannya sebagai pengidentifikasi dalam file terbalik di mana "anjing" sekarang menunjuk ke semua dokumen yang mengandung "anjing" atau "anjing".

Dalam bentuknya yang paling sederhana, seseorang dapat melakukan ini dengan gambar-gambar sebagai berikut:

1. Menyebarkan yang disebut fitur SIFT, misalnya menggunakan perpustakaan vlfeat yang sangat baik , yang akan mendeteksi poin fitur SIFT dan deskriptor SIFT per poin. Deskriptor ini pada dasarnya adalah template yang dibangun dengan cerdas dari patch gambar yang mengelilingi titik fitur tersebut. Deskriptor ini adalah kata-kata kasar Anda.
2. Kumpulkan deskriptor SIFT untuk semua gambar yang relevan

Anda sekarang memiliki banyak koleksi deskriptor SIFT. Masalahnya adalah, apakah bahkan dari gambar yang hampir identik, akan ada beberapa ketidakcocokan antara deskriptor. Anda ingin mengelompokkan yang identik bersama-sama seperti memperlakukan beberapa kata, sebagai "anjing" dan "anjing" sebagai identik dan Anda perlu mengkompensasi kesalahan. Di sinilah pengelompokan untuk bermain.

1. Ambil semua deskriptor SIFT dan cluster mereka, misalnya dengan algoritma seperti k-means. Ini akan menemukan jumlah cluster yang ditentukan sebelumnya dengan centroid dalam data deskriptor Anda. Centroid ini adalah kata-kata visual baru Anda.
2. Sekarang per gambar dan deskriptor asli yang ditemukan, Anda dapat melihat cluster yang ditugaskan deskriptor ini. Dari sini, Anda tahu centroid atau kata visual 'milik' gambar Anda. Centroid atau kata-kata visual ini menjadi deskriptor semantik baru dari gambar Anda yang dapat disimpan dalam file terbalik.

Kueri gambar, mis. Menemukan saya gambar yang mirip dengan kueri-gambar, kemudian diselesaikan sebagai berikut:

1. Temukan poin SIFT dan deskriptornya di gambar permintaan
2. Tetapkan deskriptor kueri ke centroid yang sebelumnya Anda temukan pada fase pendaftaran. Anda sekarang memiliki satu set centroid atau kata-kata visual yang berhubungan dengan gambar permintaan Anda
3. Cocokkan kata-kata visual kueri dengan kata-kata visual dalam file terbalik Anda dan kembalikan gambar yang cocok

Pendekatan menarik lainnya yang tampaknya diabaikan dalam jawaban di atas adalah Deep Neural Networks Deep Convolutional. Tampaknya Google menggunakannya sekarang untuk mesin pencari gambar dan layanan terjemahannya . CNN sangat kuat dalam tugas-tugas kognitif seperti penemuan kesamaan. Tampaknya, CNN melaksanakan prosedur serupa dari Bag-of-worlds yang tertanam melalui lapisan jaringannya. Kelemahan dari teknik ini adalah ketidakmampuan untuk melepaskan dan persyaratan dataset yang besar untuk pelatihan dan tentu saja biaya komputasi yang berat pada tahap pelatihan.

Makalah yang disarankan tentang hal ini:

• Pembelajaran yang mendalam untuk Kesamaan Semantik
• Mempelajari Kesamaan Gambar Butiran Halus dengan Ranking Tinggi

dan implementasi pengambilan gambar pembelajaran pembelajaran dalam sumber terbuka (makalah selanjutnya): https://github.com/paucarre/tiefvision