Kenali digit tulisan tangan

22

Tugas Anda adalah membaca gambar yang mengandung digit tulisan tangan, mengenali dan mencetak digit tersebut.

Input: Gambar skala abu-abu 28 * 28, diberikan sebagai urutan 784 angka teks biasa dari 0 hingga 255, dipisahkan oleh spasi. 0 berarti putih dan 255 berarti hitam.

Output: Digit yang dikenali.

Penilaian: Saya akan menguji program Anda dengan 1000 gambar dari set pelatihan database MNIST (dikonversi ke bentuk ASCII). Saya sudah memilih gambar (secara acak), tetapi tidak akan menerbitkan daftar. Tes harus selesai dalam 1 jam, dan akan menentukan n- jumlah jawaban yang benar.
nminimal harus 200 agar program Anda memenuhi syarat. Jika ukuran kode sumber Anda s, maka skor Anda akan dihitung sebagai s * (1200 - n) / 1000. Skor terendah menang.

Aturan:

  • Program Anda harus membaca gambar dari input standar dan menulis digit ke output standar
  • Tidak ada fungsi OCR bawaan
  • Tidak ada perpustakaan pihak ketiga
  • Tidak ada sumber daya eksternal (file, program, situs web)
  • Program Anda harus dapat dijalankan di Linux menggunakan perangkat lunak yang tersedia secara bebas (Wine dapat diterima jika perlu)
  • Kode sumber harus hanya menggunakan karakter ASCII
  • Silakan kirim perkiraan skor Anda dan nomor versi unik setiap kali Anda mengubah jawaban Anda

Input contoh:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 18 18 18 126 136 175 26 166 255 247 127 0 0 0 0 0 0 0 0 0 0 0 0 30 36 94 154 170 253 253 253 253 253 225 172 253 242 195 64 0 0 0 0 0 0 0 0 0 0 0 49 238 253 253 253 253 253 253 253 253 251 93 82 82 56 39 0 0 0 0 0 0 0 0 0 0 0 0 18 219 253 253 253 253 253 198 182 247 241 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 80 156 107 253 253 205 11 0 43 154 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 1 154 253 90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 139 253 190 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 190 253 70 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 35 241 225 160 108 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 81 240 253 253 119 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 45 186 253 253 150 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 93 252 253 187 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 249 253 249 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 130 183 253 253 207 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 39 148 229 253 253 253 250 182 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 24 114 221 253 253 253 253 201 78 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 66 213 253 253 253 253 198 81 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 171 219 253 253 253 253 195 80 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 55 172 226 253 253 253 253 244 133 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 136 253 253 253 212 135 132 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Omong-omong, jika Anda menambahkan baris ini ke input:

P2 28 28 255

Anda akan mendapatkan file gambar yang valid dalam format pgm, dengan warna terbalik / dinegasikan.

Seperti inilah warna yang benar: angka

Contoh output:

5

Klasemen:

No.| Name         | Language   | Alg | Ver | n   | s   |  Score
----------------------------------------------------------------
 1 | Peter Taylor | GolfScript | 6D  | v2  | 567 | 101 |  63.933
 2 | Peter Taylor | GolfScript | 3x3 | v1  | 414 | 207 | 162.702
code-challenge optical-char-recognition aditsu
sumber
Terkait, tetapi tidak persis sama (bukan tantangan, tetapi sangat berguna untuk menemukan kode lateks): detexify.kirelabs.org/classify.html . Ia juga mengenali angka.
Justin
1
Bisakah kita dengan aman berasumsi bahwa kita hanya perlu mempertimbangkan piksel hitam? > 127 piksel? Apa yang bisa kita asumsikan?
Justin
2
Terutama jika ini adalah pertanyaan kode golf, harap batasi input hitam putih. Orang-orang membuat seluruh karier mereka dari menyelesaikan masalah ini tanpa harus menghitung karakter dalam kode mereka. Tidak menerbitkan karakter mana yang Anda pilih adalah cara untuk menghentikan kecurangan, dan membuatnya menjadi semacam pertaruhan ... dan mengingat bahwa tidak masuk akal bagi orang untuk menulis AI di sini, kesenangannya adalah melakukan heuristik aneh dan kemudian melihat seberapa baik itu terjadi di turnamen vs kompetisi.
Dr. Rebmu
3
@aditsu Ya, siapa pun dapat melakukannya dengan buruk. Tetapi Anda tidak memintanya untuk dilakukan dengan buruk, Anda ingin seseorang "menang" dalam suatu kompetisi, di mana jumlah karakter diukur. Saya pikir sedikit mengurangi masalah lebih realistis untuk pemecah teka-teki hobi. Membatasi input tampaknya merupakan awal yang baik untuk membuatnya masuk akal. Saya akan menyarankan pra-pass pada input untuk mengatakan bahwa itu hitam dan putih.
Dr. Rebmu
2
@ Dr.Rebmu dan siapa pun yang menginginkan input hitam dan putih: jangan ragu untuk mengonversi input menggunakan ambang batas seperti 128. Saya memeriksa dan digit masih dapat dikenali (oleh otak saya). Anda dapat mencoba ambang lainnya juga, mereka dapat memberikan hasil yang lebih baik.
aditsu

Jawaban:

6

GolfScript 6D (v2: estimasi skor 101 * 0.63 ~ = 64)

Ini adalah pendekatan yang sangat berbeda dengan jawaban GolfScript saya sebelumnya, jadi lebih masuk akal untuk mempostingnya sebagai jawaban terpisah di v1 daripada mengedit jawaban lain dan membuat v2 ini.

~]:B;569'!EM,R.==|%NL2+^=1'{{32-}%95{base}:^~\^}:&~2/{~B=<}%2^10'#]8Y,;KiZfnnRsDzPsvQ!%4C&..z,g,$m'&=

Tidak disatukan

~]:B;
[30 183 21 378 31 381 7 461 113 543 15 568]
2/{~B=<}%2base
7060456576664262556515119565486100005262700292623582181233639882 10base
=

Penjelasan

Masalah utamanya adalah klasifikasi titik dalam ruang 784 dimensi. Salah satu pendekatan standar adalah pengurangan dimensi: mengidentifikasi subset kecil dari dimensi yang memberikan kekuatan pembeda yang cukup untuk melakukan klasifikasi. Saya mengevaluasi setiap dimensi dan setiap kemungkinan ambang untuk mengidentifikasi 18 pasang (dimensi, rentang ambang) yang tampak menjanjikan. Saya kemudian memilih pusat setiap rentang ambang, dan mengevaluasi himpunan bagian 6 elemen dari 18 pasang. Akhirnya saya mengoptimalkan ambang untuk setiap dimensi proyeksi 6-D terbaik, meningkatkan akurasinya dari 56,3% menjadi 56,6%.

Karena proyeksi menjadi 6 dimensi dan untuk setiap dimensi saya menerapkan ambang sederhana, tabel pencarian terakhir hanya membutuhkan 64 elemen. Tampaknya tidak terlalu kompresibel, jadi main golf adalah untuk melakukan konversi basis-tabel kedua pencarian (daftar dimensi dan ambang batas; dan vektor halfspace ke digit peta) dan membagikan kode konversi-dasar.

Peter Taylor
sumber
7
Anda kehilangan saya di "ruang 784 dimensi" ;-)
Digital Trauma
Saya khawatir ada kesalahan di suatu tempat, saya hanya mendapatkan 37 jawaban yang benar. Selain itu, Anda membuat hal-hal yang agak ambigu, bisakah Anda menambahkan (1) dan (2) (seperti yang saya lakukan) atau sesuatu yang mirip dengan pos Anda?
aditsu
@aditsu, kesalahan logika sederhana. Sekarang sudah diperbaiki.
Peter Taylor
Jadi pada dasarnya Anda mengambil sampel 6 "relevan" piksel, masing-masing dengan ambang yang berbeda, memperoleh 6 bit?
aditsu
@ aditsu, tepatnya.
Peter Taylor
5

GolfScript 3x3 (v1: estimasi skor 207 * 0.8 ~ = 166)

~]28/10:?/{zip?/{[]*0-!!}/}%2{base}:^~'"yN(YZ5B 7k{&w,M`f>wMb>}F2A#.{E6T9kNP_s 3Q?V`;Z\'C-z*kA5M@?l=^3ASH/@*@HeI@A<^)YN_bDI^hgD>jI"OUWiGct%7/U($*;h*<"r@xdTz6x~,/M:gT|\\:#cII8[lBr<%0r&y4'{32-}%95^?^2/{))*~}%=

Atau dalam ikhtisar,

~]28/10:?/{zip?/{[]*0-!!}/}%2{base}:^~'MAGIC STRING'{32-}%95^?^2/{))*~}%=

Penjelasan

Pendekatan saya di tingkat tinggi adalah:

  1. Ambang piksel: jika piksel di atas t1maka atur ke 1; sebaliknya untuk 0.
  2. Kelompokkan piksel. Awalnya saya memecah kotak 28x28 menjadi kotak 4x4 (masing-masing subgrid berukuran 7x7 piksel); tetapi memecahnya menjadi kisi 3x3 (subgrid menjadi 10x10, 10x8, atau 8x8 piksel) memberikan pengurangan besar-besaran dalam ukuran tabel pencarian sambil menurunkan tingkat akurasi dari sekitar 56% menjadi sekitar 40%.
  3. Jumlah piksel dalam setiap grup dan ambang lagi: jika jumlah piksel yang ditetapkan di atas t2maka nilai grup sebagai 1; jika tidak 0.
  4. Lakukan pencarian tabel dengan vektor skor kelompok. (Tabel dikompresi menggunakan run-length encoding dan trik konversi basis standar. Sebagian besar pilihan t1dan t2biarkan antara 50% dan 63% dari tabel sebagai nilai "tidak peduli", yang dapat dikombinasikan dengan nilai yang berdekatan untuk meningkatkan run lengths; rata-rata run length dalam tabel v1 saya adalah 3.6).

Ternyata pengaturan itu t1=t2=0, meskipun tidak optimal, tidak jauh dari nilai terbaik t1dan t2dalam hal akurasi; cukup baik dalam hal kompresibilitas tabel; dan memungkinkan saya untuk menggabungkan dua operasi ambang ke dalam []*0-!!(ratakan 2D array ke 1D; hapus 0s; periksa apakah itu kosong).

Tabel pencarian memberikan kandidat yang paling mungkin untuk vektor skor kelompok yang diberikan. Dimungkinkan untuk meningkatkan skor dengan mengidentifikasi entri tabel yang dapat diubah sedemikian rupa sehingga peningkatan kompresibilitas tabel melebihi akurasi yang menurun.

Peter Taylor
sumber
Luar biasa, saya punya ide serupa tetapi tidak membayangkan itu bisa dikompres dengan baik. Sekarang saya berpikir saya perlu lebih menekankan pada keakuratan: p tapi saya tidak berencana untuk mengubahnya.
aditsu