Взлом каптчи файлообменника

:

Введение

В данной статье коротко рассказывается о процессе взлома captcha с ifolder.ru. Применение в процессе языка Python и сторонних библиотек. Применение алгоритма преобразований Хафа в составе библиотеки Open Computer Vision © Intel позволит нам избавиться от шума на изображении, простая в использовании и быстрая библиотека FANN (Fast Artificial Neural Network) сделает возможным применение искусственной нейронной сети для задачи распознавания образа.

Моя мотивация состояла, прежде всего, в том, чтобы попробовать язык Python. Как известно, лучший способ изучить язык — решить на нём какую-нибудь прикладную задачу. Поэтому параллельно описанию процесса обработки изображения я буду рассказывать о том, какие библиотеки и для чего я использовал.

Обзор проблемы

Имеем следующий вид captcha:

ifolder.ru это файлообменник, который при скачивании и закачивании хочет удостовериться в том, что вы не робот. Ресурс был взят потому, что я давно хотел применить нижеописанный алгоритм преобразований Хафа к данной задаче.

В чём трудности распознавания данной captcha? Их несколько, опишем их в порядке влияния на сложность решения задачи:

1. Наличие пересечений символов. Наглядный пример таких случаев:

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

2. Наличие линий. На каждом изображении имеются 4 линии разной длины(причём длина может быть эквивалентна линейным элементам распознаваемых объектов), толщины и угла наклона. Их мы рассматривает как главный элемент шума, от которого придётся избавляться.

3. Большой разброс в расположении символов на изображении. Символы расположены на разном уровне, на разном расстоянии.

4. Поворот символов. Символы имеют наклон по одной оси, но не более, чем на ~30 градусов (величина получена эмпирически).

5. Плавающий размер и толщина символов.

С виду достаточно простая captcha при более детальном изучении не такая уж и простая. :) Но всё не так плохо. Let’s start.

Этап 1. Создание обучающей выборки и препроцессинг

Начнём с того, что скачаем с сайта несколько сотен образцов captcha, скажем 500. Этого хватит для того, чтобы отработать алгоритмы и составить первичную обучающую выборку для нашей нейронной сети.
С помощью библиотеки urllib и незамысловатого скрипта, мы скачиваем n-ое количество необходимых образцов с сайта. После чего конвертируем их из gif в 8битный bitmap, именно с таким форматом мы продолжим работу. Важным моментом является инверсия изображения. Т.е. белые объекты на чёрном фоне. Позже будет понятно, зачем это.

Скрипт, который осуществляет всё вышеописанное:

from  urllib2  import urlopen
from  urllib  import urlretrieve
from PIL  import Image, ImageOps, ImageEnhance
import  os
import  sys
import  re
import  time
def main (url, n ):
# get url session url
data = urlopen (url ). read ( )
match =  re. search (r "/random/images/\?session=[a-z0-9]+\", data )
if match:
imgurl =  "ifolder.ru" + match. group ( )
else:
return - 1
# gen imgs
for i  in  range (n ):
urlretrieve (imgurl,  '/test/' +  str (i ) +  '.gif' )
time. sleep ( 1 )
print  str (i ) +  ' of ' +  str (n ) +  ' downloaded'
# convert them
for i  in  range (n ):
img = Image. open ( '/test/' +  str (i ) +  '.gif' ). convert ( 'L' )
img = ImageOps. invert (img )
img = ImageEnhance. Contrast (img ). enhance ( 1.9 )
img. save ( '/test/' +  str (i ) +  '.bmp' )
#os.unlink('/test/' + str(i) + '.gif')
if __name__ ==  "__main__":
url =  sys. argv [- 1 ]
if  not url. lower ( ). startswith ( "http" ):
print  "usage: python dumpimages.py http://ifolder.com/?num"
sys. exit (- 1 )
main (url,  500 )

Этап 2. Удаление шума, локализация и разделение объектов.

Самый интересный и трудоёмкий этап. Примеры captcha, что я показал в обзоре, мы возьмём за образец в данной статье и будем работать с ними дальше. Итак, после первого этапа мы имеем следующее:

Для работы с изображениями я пользовался библиотеки PIL. Простая в использовании как тяпка, но достаточно функциональная и очень удобная библиотека.

Вернёмся к нашим баранам. В данном случае под шумом я подразумеваю линии.
В качестве решения проблемы я вижу несколько вариантов:
1. Генетические алгоритмы.
2. Преобразования Хафа. Можно рассматривать как разновидность автоматической векторизации.

ГА освещались на Хабре несколько раз, в том числе в процессе решения схожей задачи по взлому captcha Яндекса. Не составит труда написать модификацию генетического алгоритма для детекта прямых линий.

Тем не менее, я сделал выбор в пользу второго алгоритма. По сравнению с ГА, преобразования Хафа являются математически более строгим и детерминированным алгоритмом, в котором нет влияния случайного фактора. В данном случае он менее ресурсоёмок, в тоже время достаточно прост для понимания и применения.
Кратко, смысл алгоритма заключается в том, что любая прямая на плоскости может быть задана двумя переменными – углом наклона и расстоянием от начала координат (theta, r). Эти переменными можно рассмотреть как признаки, они формируют своё собственное двумерное пространство. Поскольку прямая есть совокупность точек и каждой из них соответствует своя пара признаков (theta, r), то в пространстве этих признаков мы будем иметь скопления точек (максимумы или peaks на пересечении) в пределах конечных окрестностей признаков соответствующие точкам прямой на исходной плоскости(изображении). Но всё проще, чем кажется. :)
Более подробно можно прочитать в Википедии и посмотреть визуализацию работы алгоритма здесь. Сразу станет ясно о чём речь.

Писать реализацию самостоятельно естественно лень. К тому же она есть в библиотеке OpenCV, с которой я достаточно часто работаю на С/С++. Есть биндинги для Python’a, которые легко собираются и устанавливаются.

В целом OpenCV достаточно низкоуровневая библиотека и работать с ней на питоне не очень удобно, поэтому авторы предусмотрели adaptors для преобразования в формат объектов PIL. Делается это очень просто:

src = cvLoadImage ( 'image.bmp'1 )  # OpenCV object
pil_image = adaptors. Ipl2PIL (src )  # PIL object

Процедура удаления линий выглядит следующим образом:

def RemoveLines (img ):
dst = cvCreateImage ( cvGetSize (img ), IPL_DEPTH_8U,  1  )
cvCopy (img, dst )
storage = cvCreateMemStorage ( 0 )
lines = cvHoughLines2 ( img, storage, CV_HOUGH_PROBABILISTIC,  1, CV_PI/ 18035353  )
for line  in lines:
cvLine ( dst, line [ 0 ], line [ 1 ], bgcolor,  20  )
return dst

Изображения должны быть монохромными, значащие пиксели белыми. Именно поэтому мы инвертировали изображение на первом этапе и будем инвертировать при распознавании.
Ключевым моментом является вызов функции cvHoughLines2. Следует обратить внимание на параметр CV_HOUGH_PROBABILISTIC, который означает применение более «умной» модификации алгоритма. Три последних параметра так же очень важны, они отражают: количество попавших точек в ячейку пространства признаков; минимальную длину линии; и максимальный пробел (gap), т.е. количество пропущенных пикселей на линии. Подробнее в документации к библиотеке.
Очень важно правильно подобрать эти параметры, иначе мы удалим с изображения прямые являющиеся частью символов или наоборот оставим много шума. Я считаю, что подобранные мною параметры являются оптимальными, но далеко не идеальными. Давайте, например, в два раза увеличим максимальный gap. Это приведёт к такому эффекту:

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

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

Следующая задача это локализация и разделение символов. Здесь возникают проблемы, описанные в пунктах 1 и 3 в обзоре. Плавающее положение символов и поворот не позволяют нам опираться на единые координаты и расположение. Символы часто «соприкасаются», что мешает нам применить какой-нибудь алгоритм из серии contours detection.
Ясно, что делить надо по вертикали. Недолго думая, посчитаем количество белых пикселей в каждом столбце изображения и отобразим их в окне:

Чтобы построить графики я использовал библиотеку matplotlib. Библиотека поражает своей гибкостью и заложенным функционалом, ничего подобного на других языках не встречал. В качестве front-end GUI использовался PyQt4.

Если соотнести графики с изображением, то видно наличие 3х локальных минимумов. По ним и будем «обрезать» изображение. Оптимальный алгоритм поиска минимумов в данном случае трудно придумать, если он вообще есть. Поэтому мною был реализован простой алгоритм поиска локального минимума, параметры получены эмпирически, и он далеко не оптимален. Это важный момент и более продуманный алгоритм может существенно повысить качество распознавания.
Процедуру разделения изображения на символы вы можете найти в исходниках(FindDividingCols и DivideDigits).

Далее мы обрезаем символы т.к. остаётся много фоновой области. После можно попытаться восстановить потерянную полезную информацию. Могу посоветовать применить морфологические алгоритмы, например Erosion & Dilation (Эрозия и Дилатация) или Closing (Замыкание). Их можно найти в библиотеке OpenCV, пример использования на питоне есть в репозитории библиотеки — OpenCV\samples\python\morphology.py. Все полученные изображения отдельных символов приводятся к единому размеру 18х24.

Результат разделения на символы:

Этап 3. Распознавание

Следующий этап это создание нейросети и её обучение. Из 500 изображений (по 4 символа на каждом) я получил меньше 1000 образцов приемлемого качества и содержания использованных для обучения. Если мы обучим сеть до уровня распознавания одного символа с вероятностью 0.5, то получим общую эффективность 0.5^4 = 0.0625 или 6%. Цель более, чем достижима. Полученной выборки для неё хватило. Если у вас есть желание поработать «китайцем» несколько дней, то велика вероятность добиться лучших результатов, тут главное терпение, которого у меня нет. :)
Для создания и использования нейросетей удобно использовать библиотеку FANN. Wrapper для питона без напильника никак собираться не хотел, пришлось править код полученный SWIG’ом. Я решил выложить скомпилирированную библиотеку, инсталлер для питона 2.6 и несколько примеров использования. Скачать можно здесь. Я написал небольшие инструкции по установке, смотрите INSTALL.

На вход подаём массив из 18*24 = 432 пикселей (точнее передаём 1 если пиксель значащий и 0 если фон), на выходе получаем массив из 10 чисел, каждый из которых отражает вероятность принадлежности входного массива к тому или иному классу (цифре). Таким образом входной слой нашей нейросети состоит из 432 нейронов, выходной из 10. Создаётся ещё один скрытый слой с числом нейронов == 432 / 3.

Код для создания и обучения сети:

from pyfann  import libfann
num_input =  432
num_output =  10
num_layers =  3
num_neurons_hidden =  144
desired_error =  0.00006
max_epochs =  50000
epochs_between_reports =  1000
ann = libfann. neural_net ( )
ann. create_standard (num_layers, num_input, num_neurons_hidden, num_output )
ann. set_activation_function_hidden (libfann. SIGMOID_SYMMETRIC_STEPWISE )
ann. set_activation_function_output (libfann. SIGMOID_SYMMETRIC_STEPWISE )
ann. train_on_file ( 'samples.txt', max_epochs, epochs_between_reports, desired_error )
ann. save ( 'fann.data' )
ann. destroy ( )

Использование:

def MagicRegognition (img, ann ):
ann = libfann. neural_net ( )
ann. create_from_file ( 'fann.data' )
sample =  [ ]
for i  in img. size [ 1 ]:
for j  in img. size [ 0 ]:
if colordist (img. getpixel ( (j, i ) ), bgcolor )  <  10:
sample [j + i  * img. size [ 0 ] ] =  0
else:
sample [j + i  * img. size [ 0 ] ] =  1
res = ann. run (sample )
return res. index ( max (res ) )

Заключение

Python великолепный язык, очень лаконичный и красивый, с множеством сторонних библиотек, которые покрывают все мои повседневные потребности. Низкий порог вхождения, во многом благодаря солидному сообществу и количеству документации. Питонщики, теперь я с вами ;)

Дополнительные библиотеки, которые использовались:
NumPy
SciPy

Исходники ( mirror 1, mirror 2)

Для подстветки синтаксиса использовался ресурс highlight.hohli.com.

UPD: 1. Перезалил исходники на 3 ресурса. 2. По просьбе, из файла dumpimages.py убрал три последних символа в регулярном выражении для ссылки на каптчу на странице ifolder. А то «дети» балуются :)