Распознать рукописные цифры

22

Ваша задача - прочитать изображение, содержащее рукописную цифру, распознать и распечатать эту цифру.

Входные данные: изображение в градациях серого 28 * 28, представленное в виде последовательности из 784 чисел в формате от 0 до 255, разделенных пробелом. 0 означает белый и 255 означает черный.

Выход: распознанная цифра.

Оценка: я протестирую вашу программу с 1000 изображений из учебного набора базы данных MNIST (преобразованного в форму ASCII). Я уже выбрал изображения (случайным образом), но не буду публиковать список. Тест должен закончиться в течение 1 часа, и будет определено n- количество правильных ответов.
nдолжно быть не менее 200 для вашей программы, чтобы претендовать. Если размер вашего исходного кода равен s, то ваш счет будет рассчитываться как s * (1200 - n) / 1000. Самый низкий балл побеждает.

Правила:

  • Ваша программа должна прочитать изображение со стандартного ввода и записать цифру в стандартный вывод
  • Нет встроенной функции OCR
  • Нет сторонних библиотек
  • Нет внешних ресурсов (файлы, программы, веб-сайты)
  • Ваша программа должна быть запущена в Linux с использованием свободно доступного программного обеспечения (Wine допускается при необходимости)
  • Исходный код должен использовать только символы ASCII
  • Пожалуйста, публикуйте свои оценки и уникальный номер версии каждый раз, когда вы изменяете свой ответ

Пример ввода:

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

Кстати, если вы добавите эту строку ко входу:

P2 28 28 255

Вы получите действительный файл изображения в формате pgm с инвертированными / отрицательными цветами.

Вот как это выглядит с правильными цветами: цифра

Пример вывода:

5

Турнирное положение:

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
источник
Связано, но не совсем то же самое (не сложно, но очень полезно для поиска латексных кодов): detexify.kirelabs.org/classify.html . Он также распознает номера.
Джастин
1
Можем ли мы с уверенностью предположить, что нам нужно учитывать только черные пиксели? Чем> 127 пикселей? Что мы можем предположить?
Джастин
2
Особенно, если речь идет о коде, пожалуйста, ограничивайтесь черно-белым вводом. Люди делают всю свою карьеру, решая эту проблему, не считая символов в своем коде. Отсутствие публикации о том, какие персонажи вы выбрали, является способом прекращения мошенничества и делает это своего рода азартной игрой ... и учитывая, что для людей неуместно писать ИИ здесь, забавно делать какую-то странную эвристику, а затем видеть, насколько хорошо это в турнире против конкуренции.
Доктор Ребму
3
@aditsu Да, любой может сделать это плохо. Но вы не просите, чтобы это было сделано плохо, вы хотите, чтобы кто-то «победил» в соревновании, где измеряется количество персонажей. Я думаю, что решение проблемы немного более реалистично для любителей головоломок. Ограничение ввода кажется хорошим началом для того, чтобы сделать его разумным. Я бы предложил предварительный проход на входе, чтобы сказать, что он черно-белый.
Доктор Ребму
2
@ Dr.Rebmu и любой другой, кто хочет черно-белый ввод: не стесняйтесь конвертировать ввод, используя порог, такой как 128. Я проверил, и цифры все еще узнаваемы (по моему разумению). Вы можете попробовать и другие пороговые значения, они могут дать лучшие результаты.
aditsu

Ответы:

6

GolfScript 6D (версия 2: оценка 101 * 0,63 ~ = 64)

Это совсем другой подход к моему более раннему ответу на GolfScript, поэтому более разумно опубликовать его как отдельный ответ на v1, чем редактировать другой ответ и сделать этот 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
=

объяснение

Грубая проблема - классификация точек в 784-мерном пространстве. Одним из стандартных подходов является уменьшение размеров: определение небольшого подмножества измерений, которые обеспечивают достаточную различающую способность для выполнения классификации. Я оценил каждое измерение и каждый возможный порог, чтобы определить 18 пар (размер, диапазон порога), которые выглядели многообещающими. Затем я выбрал центр каждого диапазона порогов и оценил 6-элементные подмножества из 18 пар. Наконец, я оптимизировал порог для каждого измерения наилучшей 6-D проекции, улучшив его точность с 56,3% до 56,6%.

Поскольку проекция делится на 6 измерений, и для каждого измерения я применяю простой порог, итоговая таблица поиска требует только 64 элемента. Кажется, это не особенно сжимаемо, поэтому основная задача игры в гольф состоит в том, чтобы преобразовать базы обоих таблиц поиска (список измерений и пороговых значений, а также вектор полупространства в цифровую карту) и совместно использовать код преобразования базы.

Питер Тейлор
источник
7
Вы потеряли меня в "784-мерном пространстве" ;-)
Digital Trauma
Боюсь, что где-то есть ошибка, я получаю только 37 правильных ответов. Кроме того, вы делаете вещи немного двусмысленными, не могли бы вы добавить (1) и (2) (как я сделал) или что-то похожее на ваши заголовки?
aditsu
@aditsu, простая логическая ошибка. Сейчас исправлено.
Питер Тейлор
Таким образом, вы выбираете 6 «соответствующих» пикселей, каждый с разным порогом, получая 6 бит?
aditsu
@aditsu, точно.
Питер Тейлор
5

GolfScript 3x3 (v1: оценка 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/{))*~}%=

Или в обзоре,

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

объяснение

Мой подход на высоком уровне:

  1. Порог пикселей: если пиксель выше, t1установите его на 1; в противном случае 0.
  2. Сгруппируйте пиксели. Сначала я разбил сетку 28x28 на сетку 4x4 (каждая подсетка 7x7 пикселей); но разбиение его на сетку 3x3 (подрешетки 10x10, 10x8 или 8x8 пикселей) дает значительное сокращение размера таблицы поиска при снижении точности с примерно 56% до примерно 40%.
  3. Снова суммируйте пиксели в каждой группе и пороговом значении: если количество установленных пикселей больше, t2тогда оцените группу как 1; иначе как 0.
  4. Сделайте поиск таблицы по вектору групповых баллов. (Таблица сжимается с использованием кодирования по длине прогона и стандартного трюка с базовым преобразованием. Большинство вариантов выбора t1и t2оставляют от 50% до 63% таблицы в качестве значений "все равно", которые можно комбинировать с соседними значениями для увеличения длина пробега; средняя длина пробега в моей таблице v1 составляет 3,6).

Оказывается, что настройки t1=t2=0, хотя и не оптимальные, не далеки от лучших значений t1и t2с точки зрения точности; довольно хорошо с точки зрения сжимаемости таблиц; и позволяет мне объединить две операции порога в []*0-!!(сгладить 2D-массив в 1D; удалить 0s; проверить, не пусто ли оно).

Таблица поиска дает наиболее вероятного кандидата для данного вектора групповых баллов. Вполне возможно, что можно улучшить оценку путем определения записей в таблице, которые можно изменить так, чтобы улучшенная сжимаемость таблицы перевешивала сниженную точность.

Питер Тейлор
источник
Круто, у меня была похожая идея, но я не думал, что она может так хорошо сжиматься. Теперь я думаю, что мне нужно больше внимания уделять точности: но я не планирую ее менять.
aditsu