Reconnaître les chiffres manuscrits

22

Votre tâche consiste à lire une image contenant un chiffre manuscrit, à reconnaître et à imprimer le chiffre.

Entrée: Une image en niveaux de gris 28 * 28, donnée sous la forme d'une séquence de 784 nombres en texte brut de 0 à 255, séparés par un espace. 0 signifie blanc et 255 signifie noir.

Sortie: Le chiffre reconnu.

Notation: Je vais tester votre programme avec 1000 des images de l' ensemble de formation de la base de données MNIST (converties au format ASCII). J'ai déjà sélectionné les images (au hasard), mais je ne publierai pas la liste. Le test doit se terminer en 1 heure et déterminera n- le nombre de bonnes réponses.
ndoit être d'au moins 200 pour que votre programme soit admissible. Si la taille de votre code source est s, votre score sera calculé comme suit s * (1200 - n) / 1000. Le score le plus bas l'emporte.

Règles:

  • Votre programme doit lire l'image de l'entrée standard et écrire le chiffre sur la sortie standard
  • Pas de fonction OCR intégrée
  • Pas de bibliothèques tierces
  • Pas de ressources externes (fichiers, programmes, sites Web)
  • Votre programme doit être exécutable sous Linux en utilisant un logiciel disponible gratuitement (Wine est acceptable si nécessaire)
  • Le code source doit utiliser uniquement des caractères ASCII
  • Veuillez publier votre score estimé et un numéro de version unique chaque fois que vous modifiez votre réponse

Exemple d'entrée:

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

Soit dit en passant, si vous ajoutez cette ligne à l'entrée:

P2 28 28 255

vous obtiendrez un fichier image valide au format pgm, avec des couleurs inversées / négatives.

Voici à quoi cela ressemble avec des couleurs correctes: chiffre

Exemple de sortie:

5

Classement:

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
aditsu
la source
Lié, mais pas tout à fait le même (pas un défi, mais très utile pour trouver les codes latex): detexify.kirelabs.org/classify.html . Il reconnaît également les nombres.
Justin
1
Pouvons-nous supposer en toute sécurité que nous devons seulement considérer les pixels noirs? Les> 127 pixels? Que pouvons-nous supposer?
Justin
2
Surtout s'il s'agit d'une question de code de golf, veuillez limiter la saisie en noir et blanc. Les gens font toute leur carrière pour résoudre ce problème sans avoir à compter les caractères dans leur code. Ne pas publier les personnages que vous avez choisis est un moyen d'arrêter la tricherie, ce qui en fait une sorte de pari ... et étant donné qu'il est déraisonnable pour les gens d'écrire de l'IA ici, le plaisir est de faire une heuristique bizarre, puis de voir à quel point c'est le cas dans le tournoi contre la compétition.
Dr Rebmu
3
@aditsu Oui, tout le monde peut mal le faire. Mais vous ne demandez pas que cela soit mal fait, vous voulez que quelqu'un "gagne" dans une compétition, où le nombre de personnages est mesuré. Je pense que réduire le problème est un peu plus réaliste pour les résolveurs de casse-tête amateurs. Contraindre l'entrée semble un bon début pour la rendre raisonnable. Je suggère une pré-passe sur l'entrée pour dire que c'est en noir et blanc.
Dr Rebmu
2
@ Dr.Rebmu et tous ceux qui veulent une entrée en noir et blanc: n'hésitez pas à convertir l'entrée en utilisant un seuil tel que 128. J'ai vérifié et les chiffres sont toujours reconnaissables (par mon cerveau). Vous pouvez également essayer d'autres seuils, ils peuvent donner de meilleurs résultats.
aditsu

Réponses:

6

GolfScript 6D (v2: score estimé 101 * 0,63 ~ = 64)

Il s'agit d'une approche très différente de ma réponse GolfScript précédente, il est donc plus logique de la publier en tant que réponse distincte à la v1 que de modifier l'autre réponse et de créer cette v2.

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

Non golfé

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

Explication

Le problème brut est la classification des points dans un espace de 784 dimensions. Une approche standard est la réduction des dimensions: identifier un petit sous-ensemble de dimensions qui fournissent un pouvoir distinctif suffisant pour effectuer la classification. J'ai évalué chaque dimension et chaque seuil possible pour identifier 18 paires de (dimension, plage de seuil) qui semblaient prometteuses. J'ai ensuite choisi le centre de chaque plage de seuil et évalué les sous-ensembles à 6 éléments des 18 paires. Enfin, j'ai optimisé le seuil pour chaque dimension de la meilleure projection 6-D, améliorant sa précision de 56,3% à 56,6%.

Parce que la projection est en 6 dimensions et pour chaque dimension j'applique un seuil simple, la table de recherche finale n'a besoin que de 64 éléments. Il ne semble pas être particulièrement compressible, donc le golf principal consiste à convertir en base les deux tables de recherche (la liste des dimensions et des seuils; et le vecteur demi-espace à la carte numérique) et de partager le code de conversion de base.

Peter Taylor
la source
7
Vous m'avez perdu à "l'espace 784-dimensionnel" ;-)
Digital Trauma
J'ai peur qu'il y ait une erreur quelque part, je n'ai que 37 bonnes réponses. De plus, vous rendez les choses un peu ambiguës, pourriez-vous s'il vous plaît ajouter (1) et (2) (comme je l'ai fait) ou quelque chose de similaire à vos titres?
aditsu
@aditsu, simple erreur logique. Maintenant corrigé.
Peter Taylor
Donc, fondamentalement, vous échantillonnez 6 pixels "pertinents", chacun avec un seuil différent, obtenant 6 bits?
aditsu
@aditsu, exactement.
Peter Taylor
5

GolfScript 3x3 (v1: score estimé 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/{))*~}%=

Ou en aperçu,

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

Explication

Mon approche à un haut niveau est:

  1. Seuil des pixels: si le pixel est au-dessus, t1réglez-le sur 1; sinon 0.
  2. Regroupez les pixels. Au départ, j'ai cassé la grille 28x28 en une grille 4x4 (chaque sous-grille étant de 7x7 pixels); mais le diviser en une grille 3x3 (les sous-grilles étant de 10x10, 10x8 ou 8x8 pixels) donne une réduction massive de la taille de la table de recherche tout en faisant chuter le taux de précision d'environ 56% à environ 40%.
  3. Additionnez à nouveau les pixels de chaque groupe et seuil: si le nombre de pixels définis est supérieur, t2notez le groupe comme 1; sinon comme 0.
  4. Faites une recherche de table par le vecteur des scores de groupe. (Le tableau est compressé à l'aide de l'encodage de longueur et de l'astuce de conversion de base standard. La plupart des choix t1et t2laissent entre 50% et 63% du tableau comme valeurs "ne se soucient pas", qui peuvent être combinées avec des valeurs adjacentes pour augmenter longueurs de course; la longueur de course moyenne dans ma table v1 est de 3,6).

Il s'avère que le réglage t1=t2=0, bien que non optimal, n'est pas loin des meilleures valeurs de t1et t2en termes de précision; est assez bon en termes de compressibilité de table; et me permet de combiner les deux opérations de seuillage en []*0-!!(aplatir le tableau 2D à 1D; supprimer 0s; vérifier s'il est vide).

Le tableau de recherche donne le candidat le plus probable pour le vecteur donné de scores de groupe. Il peut être possible d'améliorer le score en identifiant les entrées de table qui peuvent être modifiées de telle sorte que la compressibilité améliorée de la table l'emporte sur la précision diminuée.

Peter Taylor
la source
Génial, j'ai eu une idée similaire, mais je n'imaginais pas qu'elle pouvait si bien compresser. Maintenant, je pense que je devais mettre davantage l'accent sur la précision: p mais je ne prévois pas de la changer.
aditsu