Reconocer dígitos escritos a mano

22

Su tarea es leer una imagen que contenga un dígito escrito a mano, reconocer e imprimir el dígito.

Entrada: una imagen en escala de grises de 28 * 28, dada como una secuencia de 784 números de texto sin formato del 0 al 255, separados por espacio. 0 significa blanco y 255 significa negro.

Salida: el dígito reconocido.

Puntuación: Probaré su programa con 1000 de las imágenes del conjunto de entrenamiento de la base de datos MNIST (convertido a formato ASCII). Ya he seleccionado las imágenes (al azar), pero no publicaré la lista. La prueba debe finalizar dentro de 1 hora y determinará nla cantidad de respuestas correctas.
ndebe ser de al menos 200 para que su programa califique. Si el tamaño de su código fuente es s, entonces su puntaje se calculará como s * (1200 - n) / 1000. La puntuación más baja gana.

Reglas:

  • Su programa debe leer la imagen de la entrada estándar y escribir el dígito en la salida estándar
  • Sin función OCR incorporada
  • No hay bibliotecas de terceros.
  • Sin recursos externos (archivos, programas, sitios web)
  • Su programa debe ser ejecutable en Linux utilizando software disponible gratuitamente (Wine es aceptable si es necesario)
  • El código fuente debe usar solo caracteres ASCII
  • Publique su puntaje estimado y un número de versión único cada vez que modifique su respuesta

Entrada de ejemplo:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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

Por cierto, si antepone esta línea a la entrada:

P2 28 28 255

obtendrá un archivo de imagen válido en formato pgm, con colores invertidos / negados.

Así es como se ve con los colores correctos: dígito

Salida de ejemplo:

5

Posiciones:

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
fuente
Relacionado, pero no exactamente lo mismo (no es un desafío, pero es muy útil para encontrar los códigos de látex): detexify.kirelabs.org/classify.html . También reconoce números.
Justin
1
¿Podemos suponer con seguridad que solo necesitamos considerar los píxeles negros? ¿Los> 127 píxeles? ¿Qué podemos asumir?
Justin
2
Especialmente si esta es una pregunta de código de golf, limite la entrada en blanco y negro. La gente hace toda su carrera resolviendo este problema sin tener que contar los caracteres en su código. No publicar qué personajes has elegido es una forma de dejar de hacer trampa, y es una especie de apuesta ... y dado que no es razonable que las personas escriban IA aquí, la diversión es hacer una heurística extraña y luego ver qué tan bien Lo hace en el torneo vs. competencia.
Dr. Rebmu
3
@aditsu Sí, cualquiera puede hacerlo mal. Pero no estás pidiendo que se haga mal, quieres que alguien "gane" en una competencia, donde se mide el número de personajes. Creo que reducir un poco el problema es más realista para los que resuelven acertijos. Restringir la entrada parece un buen comienzo para hacerlo razonable. Sugeriría un pase previo en la entrada para decir que es en blanco y negro.
Dr. Rebmu
2
@ Dr.Rebmu y cualquier otra persona que quiera una entrada en blanco y negro: siéntase libre de convertir la entrada usando un umbral como 128. Verifiqué y los dígitos todavía son reconocibles (por mi cerebro). También puede probar otros umbrales, pueden dar mejores resultados.
Aditsu

Respuestas:

6

GolfScript 6D (v2: puntaje estimado 101 * 0.63 ~ = 64)

Este es un enfoque muy diferente a mi respuesta anterior de GolfScript, por lo que tiene más sentido publicarlo como una respuesta separada en v1 que editar la otra respuesta y hacer esta v2.

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

Sin golf

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

Explicación

El problema en bruto es la clasificación de puntos en un espacio de 784 dimensiones. Un enfoque estándar es la reducción de dimensiones: identificar un pequeño subconjunto de dimensiones que proporcionan suficiente poder de distinción para hacer la clasificación. Evalué cada dimensión y cada umbral posible para identificar 18 pares de (dimensión, rango de umbral) que parecían prometedores. Luego elegí el centro de cada rango de umbral y evalué los subconjuntos de 6 elementos de los 18 pares. Finalmente, optimicé el umbral para cada dimensión de la mejor proyección 6-D, mejorando su precisión del 56,3% al 56,6%.

Debido a que la proyección está en 6 dimensiones y para cada dimensión aplico un umbral simple, la tabla de búsqueda final solo necesita 64 elementos. No parece ser particularmente compresible, por lo que el golf principal es convertir ambas tablas de búsqueda (la lista de dimensiones y umbrales; y el vector de medio espacio en el mapa de dígitos) y compartir el código de conversión de base.

Peter Taylor
fuente
77
Me perdiste en "784-dimensional space" ;-)
Digital Trauma
Me temo que hay un error en alguna parte, solo obtengo 37 respuestas correctas. Además, estás haciendo las cosas un poco ambiguas, ¿podrías agregar (1) y (2) (como hice yo) o algo similar a tus encabezados?
Aditsu
@aditsu, error lógico simple. Ahora arreglado.
Peter Taylor
Entonces, ¿básicamente estás muestreando 6 píxeles "relevantes", cada uno con un umbral diferente, obteniendo 6 bits?
aditsu
@aditsu, exactamente.
Peter Taylor
5

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

O en resumen,

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

Explicación

Mi enfoque a un alto nivel es:

  1. Umbral los píxeles: si el píxel está arriba t1, configúrelo en 1; de lo contrario a 0.
  2. Agrupa los píxeles. Inicialmente dividí la cuadrícula de 28x28 en una cuadrícula de 4x4 (cada subcuadrícula tenía 7x7 píxeles); pero dividirlo en una cuadrícula de 3x3 (las subcuadrículas son 10x10, 10x8 u 8x8 píxeles) proporciona una reducción masiva en el tamaño de la tabla de búsqueda al tiempo que reduce la tasa de precisión de aproximadamente 56% a aproximadamente 40%.
  3. Sume los píxeles en cada grupo y umbral nuevamente: si el número de píxeles establecidos es superior t2, califique el grupo como 1; de lo contrario como 0.
  4. Haga una búsqueda en la tabla por el vector de puntajes de grupo (La tabla se comprime utilizando la codificación de longitud de ejecución y el truco estándar de conversión de base. La mayoría de las opciones t1y t2dejan entre el 50% y el 63% de la tabla como valores de "no importa", que se pueden combinar con valores adyacentes para aumentar longitudes de ejecución; la longitud promedio de ejecución en mi tabla v1 es 3.6).

Resulta que esa configuración t1=t2=0, aunque no es óptima, no está muy lejos de los mejores valores det1 y t2en términos de precisión; es bastante bueno en términos de compresibilidad de la tabla; y me permite combinar las dos operaciones de umbral en []*0-!!(aplanar matriz 2D a 1D; eliminar 0s; verificar si está vacío).

La tabla de búsqueda proporciona el candidato más probable para el vector dado de puntajes de grupo. Es muy posible mejorar la puntuación identificando las entradas de la tabla que se pueden cambiar de modo que la compresibilidad mejorada de la tabla supere la precisión disminuida.

Peter Taylor
fuente
Impresionante, tuve una idea similar pero no imaginé que se pudiera comprimir tan bien. Ahora estoy pensando que necesitaba un mayor énfasis en la precisión: p pero no planeo cambiarlo.
aditsu