Записки Зверобоя

Сегодня перед сном просматривал чужие блоги, наткнулся на интересное сообщение о распознавании captcha phpBB. Капча эта примитивная, я сам в своё время делал для неё распознавалку. Подход был примерно такой же, как у автора той заметки, но некоторые различия в реализации всё-таки были.
В этой заметке я поделюсь своим опытом по распознаванию другой простой каптчи форума ipb version 2.0-2.1.
Почему выбрана эта картинка? Не знаю, просто так. Я в прошлом году больше десятка разных картинок пробил, в конце на разгадывание простых уходило не больше часа. Вся реализация была на php, как Вы можете догадаться из заголовка блога.
Вот как выглядит эта картинка:

Распознавание картинки можно разбить на несколько этапов:

1. Получение картинки. Этот этап выходит за рамки данной статьи. Задача тривиальна и неинтересна. При разработке распознавалки этой каптчи я даже не смотрел в исходники кода ipb, просто спросил у гугла “powered by Invision Power Board v2.0″, зашел на первый попавшийся форум и накачал картинок из формы регистрации. В дальнейшем, для других более сложных картинок я сделал скриптик, который много раз заходит на нужную страницу, скачивает и сохраняет интересующую картинку - но это уже “совсем другая история”(с).
2. Анализ картинки. Этот этап конечно лучше всего производить, если видишь исходники генератора картинок. Для скриптов с открытым кодом у нас всегда есть возможность по исходникам точно определить все используемые цвета, шрифты, шумы и прочее. В сложных каптчах я часто пользовался этой возможностью, но в этой было всё так очевидно и примитивно, что даже лень было искать и качать исходники ipb. Анализ нескольких десятков картинок показал следующее:
   • на всех картинках изображено 6 символов;
   • символы - цифры от 0 до 9;
   • цвет символов - черный;
   • фон один и тот же, но разноцветные яркие пятна и мелкие шумы меняются;
   • размер шрифта и положение символов не меняется.

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

3. Создание “маски”. Исходя из анализа картинки я сделал так называемую “маску” - картинку, которая нужна моему скрипту для выбора знакомест.
   Маску делал в обычном графическом редакторе, позиции пикселов указывал сверяясь с оригинальными картинками. На выходе получил картинку с таким же размером как и у исходной (210*65), состоящую из 6 одинаковых прямоугольников:
   
   Для удобства дальнейшей работы я перевёл с помощью подскрипта эту картинку в текстовый файл, состоящий из 210 строчек и 65 столбиков единиц и нулей. Единицы соответствовали черным пикселам, нули - белым.
4. Выделение из исходной картинки всех нужных символов. Эта процедура проходила по такому алгоритму: php открывал jpg-файл каптчи и txt-файл маски, затем “пробегал” каждый пиксель картинки. Если цвет пиксела был довольно черным и в текстовом файле его координате соответствовала единица, то в другой массив запоминалась единица, иначе - нуль. Для контроля хода процесса я превращал полученный массив в картинку. В результате я получил вот такую картинку:
   
   Как видим, картинка существенно упростилась.
5. Разделение полученной картинки на символы. В данном случае всё было просто - на этой картинке символы находятся на большом расстоянии друг от друга и разделены широкими вертикальными белыми промежутками. Этим я и воспользовался. На выходе я получил 6 маленьких прямоугольников с черными и белыми писелами, которые по аналогии с маской перегнал в текстовые файлы из единичек и ноликов.
6. Создание эталонных цифр. Для создания эталонных цифр я использовал полученные на прошлой стадии текстовые файлы с ноликами и единичками. Прогнав через скрипт несколько картинок я получил все 10 возможных цифр, затем в блокноте убрал “шумы” и получил 10 красивых файликов из нулей и единиц. Это была наверное самая трудоёмкая стадия всего процесса, т.к. муторно было удалять все эти шумы, она заняла у меня около часа (весь скрипт создавался, тестировался и отлаживался примерно часа три). В идеале для генерации библиотеки эталонов лучше всего использовать те же шрифты, что используются на сервере для генерации каптчи. Но я тогда поленился глянуть в её исходники и все файлы правил ручками. В более сложных случаях я использовал в этих целях уже специальные генераторы эталонов.
7. Собственно распознавание. Теперь у меня была маска и библиотека эталонов, а скрипт умел разделять входящую картинку на символы и превращать их в прямоугольную матрицу из единичек и нулей. Следующим шагом было сравнение полученной матрицы с эталонными символами. Если в одинаковых ячейках этих матриц были одинаковые цифры - то “переменная совпадений” увеличивалась на единичку. Разделив итоговую “переменную совпадений” на общее количество ячеек данной матрицы я получал коэффициент похожести данного символа и эталона. Потом скрипт сравнивал символ со следующими эталонами и для каждого находил коэффициент похожести. Для какого эталона коэффициент похожести был максимален - тот и соответствовал данному символу. Найдя соответствия для всех символов скрипт выдавал итоговый вариант.

Теперь пару слов про быстродействие скрипта. Как видим, самой затратной операцией является сравнение каждого символа с каждым из эталоном. В данном примере у нас 6 символов, 10 эталонов, примерно 420 пикселей в каждом эталоне, что в произведении даёт около 30 тысяч операций сравнения. Для выделения из каптчи искомых символов и разделения их между собою нужно гораздо меньше операций, этот процесс занимает сотые доли секунды. А в целом, мой скрипт тратит на распознание картинки 0,145 секунды. Точность распознавания - очень хорошая, из сотни картинок-примеров ни одной ошибки.
Вот на Каптча.Ру у меня ломалка на первой же картинке сбой дала, можете проверить:

Сам скрипт я не буду выкладывать. Зачем лишний раз палить уже тысячу раз спаленную тему. Уверен, что где-то в паблике есть красивая реализация того, что я описывал выше, правда я сам эту реализацию не встречал. Но всё должно быть очень просто - у меня это заняло примерно 70 строк кода + 10 созданных эталонов + 1 маска. Интересующимся могу сказать, что была использована библиотека GD и её функции imagecreatefromjpeg, imagecolorallocate, imagesx, imagesy, imagecolorat.
Для более сложных картинок общая схема подбора картинки примерно та же, но на разных стадиях есть изменения и вариации. Первые 2 стадии - те же самые, картинку ведь в любом случае надо где-то получать и анализировать перед написанием скрипта. Маски для сложных картинок обычно не нужны, т.к. там обычно символы могут находиться где угодно в пределах каптчи. Иногда маска нужна для того, чтобы убирать у картинки статический фон. Частенько для улучшения качества картинки или вытирания каких-то цветов приходится применять различные эффекты, вроде блюра и других.
Очень часто бывают проблемы на стадии разделения картинки на отдельные символы, т.к. они касаются друг друга и могут быть похожего цвета. Также часто на картинках есть мешающие линии или кривые, которые трудно отличить от символов.
Стадия создания эталонов обычно полегче, чем предыдущая, но и на ней могут возникнуть проблемы в тех случаях, когда используется много разных шрифтов и их размеров. Например, если эталонных шрифтов 10, размеров 15, а в качестве символов используются как буквы, так и цифры, то мы будем иметь уже более 5 000 эталонов. Сильно увеличивают количество вариантов и повороты символов на картинке. А искажения, изгибы символов делают задачу сложнее на порядок.
Я уверен, что любую каптчу можно распознать автоматически, так же, как для любого замка можно найти ключ. Вопрос только во времени и количестве ресурсов, необходимых на решение этой задачи.