Введение
В данной статье коротко рассказывается о процессе взлома 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()
lines = cvHoughLines2( img, storage, CV_HOUGH_PROBABILISTIC, 1, CV_PI/180, 35, 35, 3 )
for line in lines:
cvLine( dst, line[], line[1], bgcolor, 2, )
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[]:
if colordist(img.getpixel((j, i)), bgcolor) < 10:
sample[j + i * img.size[]] =
else:
sample[j + i * img.size[]] = 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. А то «дети» балуются :)
_________
Текст подготовлен в
ХабраРедакторе
комментарии (66)
Сложную защиту с интеллектом я пока не разрабатывал, если будут идеи, отпишусь. Я вобщем не продвигал вопрос-ответ как панацею, а лишь сказал, что в задаче подбора должно не хватать входных данных. В каптче вот все входные данные на картинке. Нужно только подстроить под нее нейронную сеть и прогнать. А вопрос-ответ это задача, в которой требуются «знания», т.е. что-то помимо самого вопроса.
Как вариант, можно отображать свои вопросы в виде несильно зашумленной капчи.
Только чтобы не в формате bmp ))
Но у такого типа каптч есть будущее, если научится генерировать картинки автоматически.
Ммм, не сказал бы, что все так просто. Часто встречаются роботы на основе браузеров :)
Знаете систему тестирования SeleniumRC (http://seleniumhq.org/projects/remote-control/)? Вот на ее основе можно спамеру делать ботов и жить припеваючи.
Основная моя мысль — что каптча задача устаревшая, надо придумывать что-то другое, причем что-то, где требуются «мозги». Вот например с картинками — шаг в эту сторону. Роботу нужно уметь сопостовлять изображения и понятия — это уже «кусок» искусственного интеллекта.
Кстати если думать совсем абстрактно о далеком будущем, то с изобретением искусственного интеллекта борьба со спамом станет невозможным :D
Это наверняка был спам вручную. Некоторые спаммеры даже начинают разговаривать в комментах, если их потравить. Обижаются. Школьникам летом нечего делать, вот и занимаются «SEO».
Так и представляю толпы студентов прочитавших Пых-Пых за 21 день и ломающих каптчу.
Не будет этого. Возможно появятся библиотеки заточеные под конкретные виды каптчи, но масового не будет потому что образовательный уровень масы веб-разработчиков в части математики и обработки сигналов нулевой, а без него даже простую каптчу не разпознаешь.
Основная маса разработчиков «Где найти библиотеку на Пых-Пых которая делает то-то».
в мое время самым популярным вопросам было «где найти компонент для дельфи» :-)
Вообще подобный материал очень увлекателен. Я года 4 назад изучал труды нейронных сетей Кохонена и тогда не хватало примера для наглядности. Теперь и на моей улице праздник =)
Спасибо.
Может, Любая точка а не прямая? Идея мне понравилась, перевод в другую систему координат :) Оригинально!
Одна прямая конечно задана быть не может.
Лучше трактовать не как угол между прямой и осью ординат, а как угол между нормалью и осью абсцисс.
Вам впору написать книжку, посвященную подобным вещам) Наверняка будет классикой для интересующихся)
После всех статей про распознавание CAPTCHA неизменно возникает вопрос: какая CAPTCHA, на ваш взгляд, самая стойкая?
Как со стойкостью, к примеру, у ReCAPTCHA?
Помнится на рапидшаре была каптча с котятами и собачками. Там я с 5го раза угадывал :)
habrahabr.ru/ blogs/php/28151/
читать легко и приятно, так же как программировать на Python!
Разделение -> очистка и векторизация символов -> нахождение наиболее похожих в базе.
Правда забросил это дело, возможно если исходники разищу тоже выложу.
Разделял примерно так же как и здесь (данные о предварительном разделении сохранялись для последующего откидывания помеховых линий).
Потом просто откидывались ровные длинные линии (>1 знака или явно выходящие за рамки основного текста), а при векторизации бралась любая точка и от нее просматривало периметр(при перегибе более вероятным считался плавный изгиб), отметки о наличии точки писались как угол, потом это все склеивалось(т.е. проход в одну и другую сторону).
Хотел еще вероятностную карту создавать по типу (Ж60%; Ш90%; Щ95%), а пртом сверять по словарю на чем и забросил это дело.
Вот никогда не понимал. Массив из 432 пикселей линейный? Нейросетка никак не знает, что каждые 18 пикселей «пристыковываются» снизу? Если так, то результат будет весьма посредственный. А если не так, то объясните, каким образом нейросетка рассматривает двумерное изображение действительно как двумерное изображение?
> Создаётся ещё один скрытый слой с числом нейронов == 432 / 3.
Что означает это число? Из каких соображений взято?
100 — человек
101 — кошка
110 — собака
Потом вы сможете «распознавать» эти объекты по «кодам» :) Только наш мозг не в состоянии воспринять 432 бита, а искусственной нейросети всё равно сколько бит.
2. Если упрощённо, то промежуточный слой берётся для того, чтобы сеть сходилась более плавно, что повышает устойчивость сети. Число получено эмпирически. Единого ответа на вопрос «сколько брать скрытых слоёв и сколько ставить нейронов», насколько мне известно, не существует.
> 100 — человек
> 101 — кошка
> 110 — собака
> Потом вы сможете «распознавать» эти объекты по «кодам» :) Только наш мозг не в состоянии воспринять 432 бита, а искусственной нейросети всё равно сколько бит.
Вы сейчас говорите о линейных цифровых образах. Такие образы да, хорошо обрабатываются нейросеткой с линейным входом. А мы говорим о распознавании символов, которые являются двумерными объектами.
Я слабо разбираюсь в нейросетях, но мне представляется, что для хорошего распознавания двумерных объектов нужна двумерная нейросетка (а существует ли такие?).
Либо исходное изображение символа надо переводить в какое-то промежуточное представление, которое «транслирует» объект из двумерного представления в естественное для такого объекта одномерное представление. Например, букву «A» можно написать обычным образом, сильно вытянутым, наклонным, изогнутым. Если, например смотреть на «А» сверху вниз, то как бы не была написана буква, можно сказать что образ описывается по строкам
пусто
пусто, точка, пусто
пусто, точка, пусто, точка, пусто
пусто, линия, пусто
пусто, точка, пусто, точка, пусто
пусто
далее по вертикальным строкам тоже самое. Таким образом, двумерное представление преобразовано в линейное, сохранив совокупную информацию об образе не в виде разрозненных пикселей, а в виде взаимосвязей между основными точками и линиями. Понятно, что для одной буквы «A» может быть несколько «преобразованных» таким (или подобным) методом образов. Но нейросетку надо обучать именно на таких данных, а не просто на наборе абстрактных нулей и единиц (что тоже впринципе даст результат).
Вообще думаю, что как минимум, нужно каким-то образом рассказать нейросетке какой размер в пикселях по вертикали и горизонтали имеется, что бы как-то сбалансировать связи между соседними точками в одной строке и в одном столбце.