Как стать автором
Обновить

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

Время на прочтение 9 мин
Количество просмотров 44K

Введение



В данной статье коротко рассказывается о процессе взлома 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. А то «дети» балуются :)

Теги:
Хабы:
+173
Комментарии 68
Комментарии Комментарии 68

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн