Reconhecer dígitos manuscritos

22

Sua tarefa é ler uma imagem contendo um dígito manuscrito, reconhecer e imprimir o dígito.

Entrada: Uma imagem em escala de cinza de 28 * 28, fornecida como uma sequência de 784 números de texto sem formatação de 0 a 255, separados por espaço. 0 significa branco e 255 significa preto.

Saída: o dígito reconhecido.

Pontuação: testarei seu programa com 1000 das imagens do conjunto de treinamento do banco de dados MNIST (convertido para o formulário ASCII). Eu já selecionei as imagens (aleatoriamente), mas não publicarei a lista. O teste deve terminar dentro de 1 hora e determinará n- o número de respostas corretas.
ndeve ter pelo menos 200 para o seu programa se qualificar. Se o tamanho do seu código-fonte for s, sua pontuação será calculada como s * (1200 - n) / 1000. Menor pontuação ganha.

Regras:

  • Seu programa deve ler a imagem da entrada padrão e escrever o dígito na saída padrão
  • Nenhuma função OCR embutida
  • Nenhuma biblioteca de terceiros
  • Nenhum recurso externo (arquivos, programas, sites)
  • Seu programa deve ser executável no Linux usando um software disponível gratuitamente (o Wine é aceitável se necessário)
  • O código fonte deve usar apenas caracteres ASCII
  • Poste sua pontuação estimada e um número de versão exclusivo sempre que modificar sua resposta

Exemplo de entrada:

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

A propósito, se você anexar esta linha à entrada:

P2 28 28 255

você obterá um arquivo de imagem válido no formato pgm, com cores invertidas / negadas.

Isto é o que parece com cores corretas: dígito

Exemplo de saída:

5

Classificação:

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
fonte
Relacionado, mas não exatamente o mesmo (não é um desafio, mas é muito útil para encontrar os códigos de látex): detexify.kirelabs.org/classify.html . Também reconhece números.
237 Justin
1
Podemos assumir com segurança que precisamos considerar apenas os pixels pretos? Os> 127 pixels? O que podemos assumir?
196 Justin Justin
2
Especialmente se for uma questão de código de golfe, restrinja-o à entrada em preto e branco. As pessoas fazem suas carreiras inteiras resolvendo esse problema sem precisar contar caracteres em seu código. Não publicar quais personagens você escolheu é uma maneira de parar de trapacear, e torna uma espécie de aposta ... e, dado que não é razoável que as pessoas escrevam IA aqui, a diversão é fazer uma heurística estranha e ver como é bom isso acontece no torneio x competição.
Dr. Rebmu
3
@aditsu Sim, qualquer um pode fazer mal. Mas você não está pedindo para que isso seja feito mal; você quer que alguém "vença" em uma competição, onde a contagem de caracteres é medida. Eu acho que reduzir o problema um pouco é mais realista para os solucionadores de quebra-cabeças amadores. Restringir a entrada parece um bom começo para torná-la razoável. Sugiro um pré-passe na entrada para dizer que é preto e branco.
Dr. Rebmu
2
@ Dr.Rebmu e qualquer outra pessoa que queira entrada em preto e branco: fique à vontade para converter a entrada usando um limite como 128. Eu verifiquei e os dígitos ainda são reconhecíveis (pelo meu cérebro). Você pode tentar outros limites também, eles podem dar melhores resultados.
Aditsu

Respostas:

6

GolfScript 6D (v2: pontuação estimada 101 * 0,63 ~ = 64)

Essa é uma abordagem muito diferente da minha resposta anterior do GolfScript, portanto, faz mais sentido publicá-la como uma resposta separada na v1 do que editar a outra resposta e fazer essa v2.

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

Ungolfed

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

Explicação

O problema bruto é a classificação de pontos em um espaço 784-dimensional. Uma abordagem padrão é a redução de dimensão: identificando um pequeno subconjunto de dimensões que fornece poder de distinção suficiente para fazer a classificação. Avaliei cada dimensão e cada limite possível para identificar 18 pares de (dimensão, faixa de limite) que pareciam promissores. Escolhi o centro de cada faixa de limiar e avaliei subconjuntos de 6 elementos dos 18 pares. Finalmente, otimizei o limite para cada dimensão da melhor projeção em 6-D, melhorando sua precisão de 56,3% para 56,6%.

Como a projeção está em 6 dimensões e para cada dimensão eu aplico um limite simples, a tabela de pesquisa final precisa apenas de 64 elementos. Não parece ser particularmente compressível; portanto, o principal objetivo é converter com base as duas tabelas de pesquisa (a lista de dimensão e limites; e o vetor de meio espaço para o mapa de dígitos) e compartilhar o código de conversão de base.

Peter Taylor
fonte
7
Você me perdeu no "espaço 784-dimensional" ;-)
Digital Trauma
Receio que haja algum erro em algum lugar, estou recebendo apenas 37 respostas corretas. Além disso, você está tornando as coisas um pouco ambíguas, poderia adicionar (1) e (2) (como eu fiz) ou algo semelhante aos seus títulos?
Aditsu 21/05
@aditsu, erro lógico simples. Agora consertado.
Peter Taylor
Então, basicamente, você está amostrando 6 pixels "relevantes", cada um com um limite diferente, obtendo 6 bits?
Aditsu
@aditsu, exatamente.
Peter Taylor
5

GolfScript 3x3 (v1: pontuação estimada 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 na visão geral,

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

Explicação

Minha abordagem em alto nível é:

  1. Limite de pixels: se o pixel estiver acima t1, defina-o como 1; caso contrário, para 0.
  2. Agrupe os pixels. Inicialmente, quebrei a grade 28x28 em uma grade 4x4 (cada sub-grade sendo 7x7 pixels); mas dividi-lo em uma grade 3x3 (subgrades de 10x10, 10x8 ou 8x8 pixels) proporciona uma redução maciça no tamanho da tabela de pesquisa, ao mesmo tempo em que reduz a taxa de precisão de cerca de 56% para cerca de 40%.
  3. Soma os pixels em cada grupo e limite novamente: se o número de pixels definidos estiver acima t2, marque o grupo como 1; caso contrário, como 0.
  4. Faça uma pesquisa de tabela pelo vetor de pontuações de grupo. (A tabela é compactada usando a codificação de comprimento de execução e o truque de conversão de base padrão. A maioria das opções t1e t2deixa entre 50% e 63% da tabela como valores "não me importo", que podem ser combinados com valores adjacentes para aumentar comprimentos de execução; o comprimento médio de execução na minha tabela v1 é 3.6).

Acontece que essa configuração t1=t2=0, embora não seja ótima, não está muito longe dos melhores valores t1e t2em termos de precisão; é muito bom em termos de compressibilidade da tabela; e permite-me combinar as duas operações de limiarização []*0-!!(achatar a matriz 2D para 1D; remover 0s; verificar se está vazia).

A tabela de pesquisa fornece o candidato mais provável para o vetor determinado de pontuações de grupo. Pode ser possível melhorar a pontuação identificando entradas da tabela que podem ser alteradas de modo que a compressibilidade aprimorada da tabela supere a precisão diminuída.

Peter Taylor
fonte
Impressionante, eu tive uma idéia semelhante, mas não imaginava que pudesse se comprimir tão bem. Agora, acho que precisava de mais ênfase na precisão: p, mas não pretendo alterá-la.
Aditsu 20/05