Записки программиста

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

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

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

При помощи алгоритма, выведенного на предыдущем шаге, я получил вот такой текстовый файлик:

Здесь мы видим букву и ее черно-белое изображение 25×25, закодированное при помощи строки из единичек (черный цвет) и ноликов (белый цвет). Это — наши входные данные. Работать с таким форматом намного проще, чем с множеством изображений. При считывании файла делалось преобразование символов в числа таким образом: ’1′ → 1, ’0′ → -1. Почему так было сделано, вскоре станет ясно.

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

Сначала список из 625-и цифр преобразуется в список из 25 списков длиной 25:

Таким образом, картинке как бы снова возвращается двумерность. Так сделано просто для удобства.

Затем по краям изображения обрезаются строчки и столбцы, состоящие только из белых пикселей:

Далее полученная картина преобразуется в квадрат фиксированного размера и снова разворачивается в одномерный список следующим образом:

Для минимизации потери информации во время «сжатия» (которое, кстати, вполне может оказаться и расширением, смотря как много белых пикселей отрезала функция crop) делается не простое копирование пикселей, а берется взвешенное среднее арифметическое пикселей в соответствующем квадрате 3×3.

Обучение многослойной нейронной сети производилось на преобразованных таким вот образом данных. В обучающее множество было включено 840 примеров, выбранных случайным образом, по 56 примеров на каждую букву. Примеров в проверочном множестве было в два раза меньше, 420 штук, по 28 на каждую букву. Было специально проверено, что обучающие и проверочное множество не пересекаются.

Сложнее всего было с выбором количества нейронов в каждом слое, функции активации и так далее. После множества экспериментов в конечном счете была выбрана нейронная сеть из трех слоев, имеющая 196 входов (соответственно, изображение сжималось до размеров 12×12), 15 выходов и 65 нейронов в скрытом слое. В качестве функции активации был выбран гиперболический тангенс. Поэтому на входы подавались числа от -1 до 1, а не от 0 до 1, как было бы при использовании логистической функции. Перед началом обучения весам сети присваивались случайные значения от -0.075 до 0.075. В качестве скорости обучения было выбрано число 0.0003. Этот параметр был подобран так, чтобы среднеквадратичная ошибка (mean square error, MSE) на обучающем и проверочном множествах уменьшалась монотонно (не «прыгала»), но при этом достаточно быстро. Прочие параметры были подобраны так, чтобы (1) сеть обучалась достаточно быстро и (2) в конечном счете процент правильно распознанных букв на проверочном множестве был максимален. Выход сети интерпретировался по принципу «победитель получает все»:

Обучение нейронной сети происходило в пакетном (batch) режиме. За 273 шага была получена сеть, правильно определяющая буквы из проверочного множества примерно в 55% случаев (против 7%, если использовать простое угадывание). Конечно, это далеко до человеческой точности, но, как мы вскоре выясним, в случае с распознаванием капчи из шести букв даже этого вполне достаточно.

Такие дела. На сегодня это все. Завтра будет опубликован заключительный пост, в котором я поделюсь кое-какими своими мыслями касательно распознавания капч, нейронных сетей, а также приведу несколько интересных, как мне кажется, ссылок. И, само собой разумеется, подведу итоги, куда же без этого. Следите за обновлениями.

Дополнение: Взлом капчи — полученные результаты и сделанные выводы

Метки: Haskell, Безопасность, Искусственный интеллект, Функциональное программирование.