Bagaimana cara menemukan Waldo dengan Mathematica?

1542

Ini menggangguku selama akhir pekan: Apa cara yang baik untuk menyelesaikan masalah Where's Waldo? Teka-teki [ 'Wally' di luar Amerika Utara], menggunakan Mathematica (pemrosesan gambar dan fungsi lainnya)?

Inilah yang saya miliki sejauh ini, sebuah fungsi yang sedikit mengurangi kompleksitas visual dengan meredupkan beberapa warna non-merah:

whereIsWaldo[url_] := Module[{waldo, waldo2, waldoMask},
    waldo = Import[url];
    waldo2 = Image[ImageData[
        waldo] /. {{r_, g_, b_} /;
          Not[r > .7 && g < .3 && b < .3] :> {0, 0,
          0}, {r_, g_, b_} /; (r > .7 && g < .3 && b < .3) :> {1, 1,
          1}}];
    waldoMask = Closing[waldo2, 4];
    ImageCompose[waldo, {waldoMask, .5}]
]

Dan contoh URL tempat ini 'bekerja':

whereIsWaldo["http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/DepartmentStore.jpg"]

(Waldo ada di kasir):

Gambar asli

Grafik Mathematica

Arnoud Buzing
sumber
31
@yoda - kiri atas, meja dengan banyak sepatu, mesin kasir dan Waldo di dekat sudut meja.
Arnoud Buzing
8
Sebagai mahasiswa PhD dalam visi komputer saya tergoda untuk mencoba ini ... tapi saya harus menolak. Untuk apa layak itu aku akan pergi untuk Histogram dari Berorientasi Gradien + sliding window SVM, seperti dalam hal ini pekerjaan yang sangat berpengaruh (peringatan: pdf).
dimatura
54
"Di mana Wally ." >. <
Lightness Races di Orbit
2
Bisakah kita mengubah pertanyaan untuk mendukung bahasa lain juga? Saya berpikir untuk melakukannya dengan Matlab
Andrey Rubshtein
2
@ArnoudBuzing: Dalam pertanyaan Anda, Anda dapat menemukan Waldo dengan melihat pilihan yang paling putih di dalamnya. : /
Tamara Wijsman

Jawaban:

1640

Saya telah menemukan Waldo!

waldo telah ditemukan

Bagaimana saya melakukannya

Pertama, saya memfilter semua warna yang tidak merah

waldo = Import["http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/DepartmentStore.jpg"];
red = Fold[ImageSubtract, #[[1]], Rest[#]] &@ColorSeparate[waldo];

Selanjutnya, saya menghitung korelasi gambar ini dengan pola hitam dan putih sederhana untuk menemukan transisi merah dan putih di kemeja.

corr = ImageCorrelate[red, 
   Image@Join[ConstantArray[1, {2, 4}], ConstantArray[0, {2, 4}]], 
   NormalizedSquaredEuclideanDistance];

Saya gunakan Binarizeuntuk memilih piksel dalam gambar dengan korelasi yang cukup tinggi dan menggambar lingkaran putih di sekitarnya untuk menekankan mereka gunakanDilation

pos = Dilation[ColorNegate[Binarize[corr, .12]], DiskMatrix[30]];

Saya harus bermain-main sedikit dengan level. Jika levelnya terlalu tinggi, terlalu banyak false positive yang dipilih.

Akhirnya saya menggabungkan hasil ini dengan gambar asli untuk mendapatkan hasil di atas

found = ImageMultiply[waldo, ImageAdd[ColorConvert[pos, "GrayLevel"], .5]]
Heike
sumber
52
@ MikeBantegui Sementara solusi Heike hebat, saya tidak akan begitu cepat untuk mengemasnya menjadi suatu WhereIsWaldofungsi, karena itu bukan solusi umum. Heike sendiri telah menunjukkan bahwa level perlu dimainkan sebelum Anda bisa mendapatkan yang positif. Untuk melihat apa yang saya maksud, coba fungsi paket Anda seperti pada. "http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/AtTheBeach.jpg"Ini lebih sulit dengan yang ini.
abcd
17
Gambar ini lebih rumit: Waldo . Saya pikir, bahwa memiliki sesuatu yang dapat menyoroti potensi Waldos masih berguna (untuk beberapa definisi 'berguna'.) (Ini mengingatkan saya pada beberapa hal yang kadang-kadang akan diidentifikasi oleh iPhoto sebagai wajah dalam koleksi foto kami ...)
Brett Champion
33
Silakan lihat posting Meta ini: meta.stackexchange.com/questions/116401/...
Bill the Lizard
155
Anda tampaknya telah salah paham aturan Where's Waldo. Ini jelas curang.
Stefan Kendall
91
Meskipun ini adalah retasan yang bagus, itu tidak berhasil. Ini membutuhkan penyetelan manual dan hanya bekerja pada satu gambar. Saya tidak mengerti mengapa ini dibalik dan bahkan dipilih sebagai jawaban. Itu membuat orang lain enggan menjawab dengan metode kerja yang lebih baik.
sam hocevar
144

Tebakan saya pada "cara anti peluru untuk melakukan ini" (pikirkan CIA menemukan Waldo di citra satelit kapan saja, bukan hanya satu gambar tanpa elemen yang bersaing, seperti kemeja bergaris) ... Saya akan melatih mesin Boltzmann pada banyak gambar Waldo - semua variasi dia duduk, berdiri, menyumbat, dll.; baju, topi, kamera, dan semua karya. Anda tidak perlu korpus besar Waldos (mungkin 3-5 akan cukup), tetapi semakin banyak semakin baik.

Ini akan menetapkan awan probabilitas ke berbagai elemen yang terjadi dalam pengaturan apa pun yang benar, dan kemudian menetapkan (melalui segmentasi) apa ukuran objek rata-rata, memecah-mecah gambar sumber menjadi sel-sel objek yang paling menyerupai individu orang (mempertimbangkan kemungkinan penyumbatan dan menimbulkan perubahan) ), tetapi karena gambar Waldo biasanya menyertakan BANYAK orang pada skala yang sama, ini seharusnya menjadi tugas yang sangat mudah, kemudian memberi makan segmen-segmen ini dari mesin Boltzmann yang sudah dilatih sebelumnya. Ini akan memberi Anda kemungkinan masing-masing menjadi Waldo. Ambil satu dengan probabilitas tertinggi.

Beginilah cara kerja OCR, pembaca kode ZIP, dan pengenalan tulisan tangan yang tidak berbelit-belit hari ini. Pada dasarnya Anda tahu jawabannya ada di sana, Anda tahu kurang lebih seperti apa bentuknya, dan yang lainnya mungkin memiliki elemen yang sama, tetapi jelas "bukan", jadi Anda tidak repot dengan "bukan", Anda lihat saja kemungkinan "itu" di antara semua kemungkinan "itu" yang pernah Anda lihat sebelumnya "(dalam kode ZIP misalnya, Anda akan melatih BM hanya untuk 1s, hanya 2s, hanya 3s, dll, lalu beri makan setiap digit ke setiap mesin, dan pilih satu yang paling percaya diri) .Ini bekerja jauh lebih baik daripada fitur pembelajaran jaringan saraf tunggal dari semua angka.

Gregory Klopper
sumber
13
Bukankah jaringan saraf biasa cukup untuk itu? Selain itu, artikel wikipedia mengklaim bahwa mesin Boltzmann tidak praktis.
GClaramunt
2
Tanpa mencoba saya tidak yakin, tetapi jika cukup besar dan cukup kompleks jaringan saraf harus cukup untuk APA SAJA. Apalagi dengan perulangan. Mesin Boltzmann melakukan SANGAT SANGAT SANGAT baik untuk mengenali set data yang cukup sederhana dengan jumlah derau yang tinggi dalam lautan data yang berbeda dengan dirinya sendiri.
Gregory Klopper
14
Kode ZIP dibaca dengan mesin Boltzmann sepanjang waktu, dan keakuratan pengiriman surat telah meningkat.
Gregory Klopper
47

Saya setuju dengan @GregoryKlopper bahwa cara yang tepat untuk menyelesaikan masalah umum menemukan Waldo (atau objek yang menarik) dalam gambar sewenang-wenang adalah dengan melatih classifier pembelajaran mesin yang diawasi. Menggunakan banyak contoh berlabel positif dan negatif, suatu algoritma seperti Support Vector Machine , Boosted Decision Stump atau Boltzmann Machine kemungkinan bisa dilatih untuk mencapai akurasi tinggi pada masalah ini. Mathematica bahkan memasukkan algoritma ini ke dalam Kerangka Pembelajaran Mesinnya .

Dua tantangan dengan pelatihan classifier Waldo adalah:

  1. Menentukan transformasi fitur gambar yang tepat. Di sinilah jawaban @ Heike akan berguna: filter merah dan detektor pola yang dilucuti (misalnya, dekomposisi wavelet atau DCT) akan menjadi cara yang baik untuk mengubah piksel mentah menjadi format yang dapat dipelajari oleh algoritma klasifikasi. Dekomposisi berbasis blok yang menilai semua subbagian gambar juga akan diperlukan ... tetapi ini dipermudah oleh fakta bahwa Waldo adalah a) selalu kira-kira berukuran sama dan b) selalu hadir tepat sekali dalam setiap gambar.
  2. Mendapatkan contoh pelatihan yang cukup. SVM bekerja paling baik dengan setidaknya 100 contoh setiap kelas. Aplikasi komersial untuk meningkatkan (misalnya, pemfokusan wajah pada kamera digital) dilatih pada jutaan contoh positif dan negatif.

Pencarian gambar Google cepat menghasilkan beberapa data yang bagus - Saya akan mencoba mengumpulkan beberapa contoh pelatihan dan mengkodekannya sekarang!

Namun, bahkan pendekatan pembelajaran mesin (atau pendekatan berbasis aturan yang disarankan oleh @iND) akan berjuang untuk gambar seperti Land of Waldos !

lubar
sumber
Sistem visi komputer berbasis pembelajaran mesin yang mencoba memecahkan masalah "Di mana Waldo" di dunia nyata (yaitu, menemukan orang tertentu di foto kerumunan orang di Flickr) dipresentasikan pada konferensi Computer Vision and Pattern Recognition tahun lalu. Mereka sedikit curang meskipun dengan menambahkan beberapa info lokasi 3D dengan menggunakan beberapa foto dari adegan yang sama.
lubar
41

Saya tidak tahu Mathematica. . . sangat buruk. Tapi saya suka jawaban di atas, sebagian besar.

Masih ada kelemahan utama dalam mengandalkan strip sendirian untuk mendapatkan jawabannya (saya pribadi tidak punya masalah dengan satu penyesuaian manual). Ada sebuah contoh (terdaftar oleh Brett Champion, di sini ) yang disajikan yang menunjukkan bahwa mereka, kadang-kadang, memecah pola baju. Jadi itu menjadi pola yang lebih kompleks.

Saya akan mencoba pendekatan id bentuk dan warna, bersama dengan hubungan spasial. Sama seperti pengenalan wajah, Anda dapat mencari pola geometris pada rasio tertentu dari satu sama lain. Peringatannya adalah bahwa biasanya satu atau lebih bentuk itu tersumbat.

Dapatkan white balance pada gambar, dan red white balance dari gambar. Saya percaya Waldo selalu memiliki nilai yang sama / rona, tetapi gambar mungkin dari pemindaian, atau salinan yang buruk. Kemudian selalu merujuk pada array warna yang sebenarnya dimiliki Waldo: merah, putih, coklat tua, biru, persik, {warna sepatu}.

Ada pola baju, dan juga celana, kacamata, rambut, wajah, sepatu dan topi yang mendefinisikan Waldo. Juga, relatif terhadap orang lain dalam gambar, Waldo ada di sisi kurus.

Jadi, cari orang acak untuk mendapatkan ketinggian orang di foto ini. Ukur tinggi rata-rata banyak hal pada titik acak dalam gambar (garis besar sederhana akan menghasilkan beberapa orang secara individu). Jika setiap hal tidak berada dalam beberapa standar deviasi satu sama lain, mereka diabaikan untuk saat ini. Bandingkan rata-rata ketinggian dengan tinggi gambar. Jika rasionya terlalu besar (mis. 1: 2, 1: 4, atau hampir sama), lalu coba lagi. Jalankan 10 (?) Kali untuk memastikan bahwa sampel semuanya cukup berdekatan, tidak termasuk rata-rata di luar beberapa standar deviasi. Mungkinkah dalam Mathematica?

Ini adalah ukuran Waldo Anda. Walso kurus, jadi Anda mencari sesuatu 5: 1 atau 6: 1 (atau apa pun) ht: wd. Namun, ini tidak cukup. Jika Waldo sebagian tersembunyi, tingginya bisa berubah. Jadi, Anda mencari balok merah-putih yang ~ 2: 1. Tetapi harus ada lebih banyak indikator.

  1. Waldo punya kacamata. Cari dua lingkaran 0,5: 1 di atas merah-putih.
  2. Celana biru. Berapapun jumlah biru pada lebar yang sama dalam jarak apa pun antara ujung merah-putih dan jarak ke kakinya. Perhatikan bahwa ia memakai kemejanya pendek, sehingga kakinya tidak terlalu dekat.
  3. Topi. Merah-putih jaraknya hingga dua kali bagian atas kepalanya. Perhatikan bahwa rambutnya berwarna gelap di bawah, dan mungkin kacamata.
  4. Lengan panjang. merah-putih pada beberapa sudut dari merah-putih utama.
  5. Rambut hitam.
  6. Warna sepatu. Saya tidak tahu warnanya.

Semua itu bisa berlaku. Ini juga cek negatif terhadap orang-orang yang sama di foto - misalnya, # 2 meniadakan mengenakan celemek merah-putih (terlalu dekat dengan sepatu), # 5 menghilangkan rambut berwarna terang. Selain itu, bentuk hanya satu indikator untuk masing-masing tes ini. . . warna saja dalam jarak yang ditentukan dapat memberikan hasil yang baik.

Ini akan mempersempit area yang akan diproses.

Menyimpan hasil ini akan menghasilkan seperangkat area yang seharusnya memiliki Waldo di dalamnya. Kecualikan semua area lain (mis., Untuk setiap area, pilih satu lingkaran dua kali lebih besar dari ukuran rata-rata orang), dan kemudian jalankan proses yang diatur oleh @Heike dengan menghapus semua kecuali merah, dan seterusnya.

Adakah pemikiran tentang cara membuat kode ini?


Edit:

Pikiran tentang cara kode ini. . . kecualikan semua area kecuali Waldo red, skeletonize area merah, dan pangkas hingga satu titik. Lakukan hal yang sama untuk Waldo hair brown, celana Waldo blue, warna sepatu Waldo. Untuk warna kulit Waldo, singkirkan, lalu temukan garis besarnya.

Selanjutnya, kecualikan non-merah, melebarkan (banyak) semua area merah, kemudian skeletonize dan pangkas. Bagian ini akan memberikan daftar kemungkinan poin pusat Waldo. Ini akan menjadi penanda untuk membandingkan semua bagian warna Waldo lainnya.

Dari sini, menggunakan area merah kerangka (bukan yang melebar), hitung garis di setiap area. Jika ada nomor yang benar (empat, kan?), Ini tentunya merupakan area yang memungkinkan. Jika tidak, saya kira hanya mengecualikannya (sebagai pusat Waldo ... mungkin masih topinya).

Kemudian periksa apakah ada bentuk wajah di atas, titik rambut di atas, titik celana di bawah, titik sepatu di bawah, dan sebagainya.

Belum ada kode - masih membaca dokumen.

iND
sumber
8
Mungkin Anda bisa menunjukkan bukti konsep di sistem / bahasa apa pun yang Anda kenal. Ini juga akan memberi Anda perasaan di mana kesulitan mungkin datang.
Szabolcs
1
Oh, aku hanya menikmati tantangannya. Ini memberi saya sesuatu untuk dilakukan di antara berjalan-jalan di pantai dan berpakaian untuk makan malam.
iND
1
Begitu. . . mengapa downvotes? Bagaimana ini berbeda dari jawaban spekulatif lainnya di sini? Apakah ini saran agar pertanyaan ini harus ditanggapi dengan lebih serius? Atau hanya bahwa saya harus tampak lebih serius dalam penyelidikan saya? Apakah pendekatan saya sebenarnya salah?
iND
3
Saya tidak meremehkan Anda dan saya tidak berpikir downvote sesuai untuk upaya jujur ​​untuk menjawab (kecuali mereka memberikan informasi yang salah). Alasan yang paling mungkin untuk downvotes adalah bahwa Anda tampaknya tidak mencoba pendekatan (cukup rumit terdengar), dan menemukan solusi yang baik mungkin akan mengambil banyak eksperimen praktis dan mengesampingkan banyak ide. Jawaban spekulatif lainnya menyarankan metode umum (sebagai titik awal) yang telah digunakan di masa lalu untuk masalah yang sama, dan ada sejumlah literatur yang baik di dalamnya. Hanya berusaha menjelaskan apa yang terjadi.
Szabolcs
Terima kasih untuk penjelasannya. Saya kira saya tidak fokus pada sejarah ide.
iND
2

Saya punya solusi cepat untuk menemukan Waldo menggunakan OpenCV.

Saya menggunakan fungsi pencocokan templat yang tersedia di OpenCV untuk menemukan Waldo.

Untuk melakukan ini diperlukan templat. Jadi saya memotong Waldo dari gambar asli dan menggunakannya sebagai templat.

masukkan deskripsi gambar di sini

Selanjutnya saya memanggil cv2.matchTemplate()fungsi bersama dengan koefisien korelasi dinormalisasi sebagai metode yang digunakan. Ini mengembalikan probabilitas tinggi di satu wilayah seperti yang ditunjukkan dalam warna putih di bawah (di suatu tempat di wilayah kiri atas):

masukkan deskripsi gambar di sini

Posisi wilayah kemungkinan tertinggi ditemukan menggunakan cv2.minMaxLoc()fungsi, yang kemudian saya gunakan untuk menggambar persegi panjang untuk menyorot Waldo:

masukkan deskripsi gambar di sini

Jeru Luke
sumber
7
Mencoba menangani pertanyaan pemrosesan gambar SO yang paling terkenal? ;) Solusi Anda bagus dan mudah tetapi a / hanya berfungsi untuk gambar spesifik ini dan b / membutuhkan gambar persis Waldo yang ingin Anda temukan sebelumnya, sementara saya pikir pertanyaannya adalah tentang menemukan Waldo apa pun dalam "Di mana gambar Waldo" seperti Anda akan memainkan permainan normal: tanpa mengetahui seperti apa dia sebelumnya. Bagaimanapun
Soltius
@Solitus ha persis !!! Saya bekerja hanya untuk gambar ini pada khususnya. Mengerjakannya untuk gambar yang berbeda akan menjadi tantangan !!
Jeru Luke