Ломаем капчу — распознавание символов при помощи многослойной нейронной сети

15 мая 2014

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

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

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

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

LOG|k|0000000100000000000000000000011010000000000000000000011111000...
LOG|c|0011111100000000000000000011111111100000000000000011100011111...
LOG|z|0000000000001000000000000000000000000000000000000000000000000...
LOG|w|0000000000000001000000000000000000000000000000000000000000000...
...

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

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

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

import qualified Data.List as L
import Data.List.Split (chunksOf)

to2DImage = chunksOf 25

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

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

crop = crop' . crop'
  where
    crop' = L.transpose . reverse . filt . reverse . filt
    filt = dropWhile (all (== -1))

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

compress :: Double -> [[Double]] -> [Double]
compress scaledwh lst2d =
  let mh = fromIntegral $ length lst2d - 1
      mw = fromIntegral $ length (head lst2d) - 1
      notneg x = if x < 0 then 0 else x
  in [ sum [ (if x == cx && y == cy then 0.8 else 0.1) *
                    lst2d !! notneg y !! notneg x
               | x <- [cx-1 .. cx+1],
                 y <- [cy-1 .. cy+1]
           ] / 1.6
       | i <- [1 :: Double .. scaledwh],
         j <- [1 :: Double .. scaledwh],
         let cx = truncate (mw * i / scaledwh) - 1,
         let cy = truncate (mh * j / scaledwh) - 1
     ]

Для минимизации потери информации во время «сжатия» (которое, кстати, вполне может оказаться и расширением, смотря как много белых пикселей отрезала функция 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) в конечном счете процент правильно распознанных букв на проверочном множестве был максимален. Выход сети интерпретировался по принципу «победитель получает все»:

recognizeLetter input =
  let output = runNeuralNetwork neuralNetwork input
      mn = maximum output
      (ans:_) = [ c | (c, n) <- zip "acgkmopqsuvwxyz" output, n == mn ]
  in ans

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

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

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

Метки: , , , .

Подпишись через RSS, E-Mail, Google+, Facebook, Vk или Twitter!

Понравился пост? Поделись с другими: