Большинство людей не в курсе, но моей диссертацией была программа для чтения текста с изображения. Я думал, что, если смогу получить высокий уровень распознавания, то это можно будет использовать для улучшения результатов поиска. Мой отличный советник доктор Гао Джунбин предложил мне написать диссертацию на эту тему. Наконец-то я нашел время написать эту статью и здесь я постараюсь рассказать о всем том, что узнал. Если бы только было что-то подобное, когда я только начинал…
Как я уже говорил, я пытался взять обычные изображения из интернета и извлекать из них текст для улучшения результатов поиска. Большинство моих идей было основано на методах взлома капчи. Как всем известно, капча - это те самые всех раздражающее штуки, вроде «Введите буквы, которые вы видите на изображении» на страницах регистрации или обратной связи.
Капча устроена так, что человек может прочитать текст без труда, в то время, как машина - нет (привет, reCaptcha!). На практике это никогда не работало, т. к. почти каждую капчу, которую размещали на сайте взламывали в течении нескольких месяцев.
У меня неплохо получалось - более 60% изображений было успешно разгадано из моей небольшой коллекции. Довольно неплохо, учитывая количество разнообразных изображений в интернете.
При своем исследовании я не нашел никаких материалов, которые помогли бы мне. Да, статьи есть, но в них опубликованы очень простые алгоритмы. На самом деле я нашел несколько нерабочих примеров на PHP и Perl, взял из них несколько фрагментов и получил неплохие результаты для очень простой капчи. Но ни один из них мне особо не помог, т. к. это было слишком просто. Я из тех людей, которые могут читать теорию, но ничего не понять без реальных примеров. А в большинстве статей писалось, что они не будут публиковать код, т. к. боятся, что его будут использовать в плохих целях. Лично я думаю, что капча – это пустая трата времени, т. к. ее довольно легко обойти, если знать как.
Собственно по причине отсутствия каких-то материалов, показывающих взлом капчи для начинающих я и написал эту статью.
Давайте начнем. Вот список того, что я собираюсь осветить в этой статье:
Все примеры написаны на Python 2.5 с использованием библиотеки PIL. Должно работать и в Python 2.6.
Установите их в указанном выше порядке и вы готовы к запуску примеров.
В примерах я буду жестко задавать множество значений прямо в коде. У меня нет цели создать универсальный распознаватель капч, а только показать как это делается.
В основном капча является пример одностороннего преобразования. Вы можете легко взять набор символов и получить из него капчу, но не наоборот. Другая тонкость – она должна быть простая для чтения человеком, но не поддаваться машинному распознаванию. Капча может рассматриваться как простой тест типа «Вы человек?». В основном они реализуются как изображение с какими-то символами или словами.
Они используются для предотвращения спама на многих интернет-сайтах. Например, капчу можно найти на странице регистрации в Windows Live ID .
Вам показывают изображение, и, если вы действительно человек, то вам нужно ввести его текст в отдельное поле. Кажется неплохой идеей, которая может защитить вас от тысяч автоматических регистраций с целью спама или распространения виагры на вашем форуме? Проблема в том, что ИИ, а в частности методы распознавания изображений потерпели значительные изменения и становятся очень эффективными в определенных областях. OCR (оптическое распознавание символов) в наши дни является довольно точным и легко распознает печатный текст. Было принято решение добавить немного цвета и линий, чтобы затруднить работу компьютеру без каких-то неудобств для пользователей. Это своего рода гонка вооружений и как обычно на любую защиту придумывают более сильное оружие. Победить усиленную капчу сложнее, но все равно возможно. Плюс ко всему изображение должно оставаться довольно простым, чтобы не вызывать раздражение у обычных людей.
Это изображение является примером капчи, которую мы будем расшифровывать. Это реальная капча, которая размещена на реальном сайте.
Это довольно простая капча, которая состоит из символов одинакового цвета и размера на белом фоне с некоторым шумом (пиксели, цвета, линии). Вы думаете, что этот шум на заднем плане затруднит распознавание, но я покажу, как его легко удалить. Хоть это и не очень сильная капча, но она является хорошим примером для нашей программы.
Существует много методов для определения положения текста на изображении и его извлечения. С помощью Google вы можете найти тысячи статей, которые объясняют новые методы и алгоритмы для поиска текста.
Для этого примера я буду использовать извлечение цвета. Это довольно простая техника, с помощью которой я получил довольно неплохие результаты. Именно эту технику я использовал для своей диссертации.
Для наших примеров я буду использовать алгоритм многозначного разложения изображения. По сути, это означает, что мы сначала построим гистограмму цветов изображения. Это делается путем получения всех пикселей в изображении с группировкой по цвету, после чего производится подсчет по каждой группе. Если посмотреть на нашу тестовую капчу, то можно увидеть три основных цвета:
На Python это будет выглядеть очень просто.
Следующий код открывает изображение, преобразует его в GIF (облегчает нам работу, т. к. в нем всего 255 цветов) с печатает гистограмму цветов.
From PIL import Image im = Image.open("captcha.gif") im = im.convert("P") print im.histogram()
В итоге мы получим следующее:
Здесь мы видем количество пикселей каждого из 255 цветов в изображении. Вы можете увидеть, что белый (255, самый последний) встречается чаще всего. За ним идет красный (текст). Чтобы убедиться в этом, напишем небольшой скрипт:
From PIL import Image from operator import itemgetter im = Image.open("captcha.gif") im = im.convert("P") his = im.histogram() values = {} for i in range(256): values[i] = his[i] for j,k in sorted(values.items(), key=itemgetter(1), reverse=True)[:10]: print j,k
И получаем такие данные:
Это список из 10 наиболее распространенных цветов в изображении. Как ожидалось, белый повторяется чаще всего. Затем идут серый и красный.
Как только мы получили эту информацию, мы создаем новые изображения, основанные на этих цветовых группах. Для каждого из наиболее распространенных цветов мы создаем новое бинарное изображение (из 2 цветов), где пиксели этого цвета заполняется черным, а все остальное белым.
Красный у нас стал третьем среди наиболее распространенных цветов и это означает, что мы хотим сохранить группу пикселей с цветом 220. Когда я экспериментировал я обнаружил, что цвет 220 довольно близок к 220, так что мы сохраним и эту группу пикселей. Приведенный ниже код открывает капчу, преобразует ее в GIF, создает новое изображение такого же размера с белым фоном, а затем обходит оригинальное изображение в поисках нужного нам цвета. Если он находит пиксель с нужным нам цветом, то он отмечает этот же пиксель на втором изображении черным цветом. Перед завершением работы второе изображение сохраняется.
From PIL import Image im = Image.open("captcha.gif") im = im.convert("P") im2 = Image.new("P",im.size,255) im = im.convert("P") temp = {} for x in range(im.size): for y in range(im.size): pix = im.getpixel((y,x)) temp = pix if pix == 220 or pix == 227: # these are the numbers to get im2.putpixel((y,x),0) im2.save("output.gif")
Запуск этого фрагмента кода дает нам следующий результат.
На картинке вы можете увидеть, что у нас успешно получилось извлечь текст из фона. Чтобы автоматизировать этот процесс вы можете совместить первый и второй скрипт.
Слышу, как спрашиваете: «А что, если на капче текст написан разными цветами?». Да, наша техника все еще сможет работать. Предположите, что наиболее распространенный цвет – это цвет фона и тогда вы сможете найти цвета символов.
Таким образом, на данный момент мы успешно извлекли текст из изображения. Следующим шагом будет определение того, содержит ли изображение текст. Я пока не буду писать здесь код, т. к. это сделает понимание сложным, в то время как сам алгоритм довольно прост.
For each binary image: for each pixel in the binary image: if the pixel is on: if any pixel we have seen before is next to it: add to the same set else: add to a new set
На выходе у вас будет набор границ символов. Тогда все, что вам нужно будет сделать – это сравнить их между собой и посмотреть, идут ли они последовательно. Если да, то вам выпал джек-пот и вы правильно определили символы, идущие рядом. Вы так же можете проверять размеры полученных областей или просто создавать новое изображение и показывать его (метод show() у изображения), чтобы убедиться в точности алгоритма.
From PIL import Image im = Image.open("captcha.gif") im = im.convert("P") im2 = Image.new("P",im.size,255) im = im.convert("P") temp = {} for x in range(im.size): for y in range(im.size): pix = im.getpixel((y,x)) temp = pix if pix == 220 or pix == 227: # these are the numbers to get im2.putpixel((y,x),0) # new code starts here inletter = False foundletter=False start = 0 end = 0 letters = for y in range(im2.size): # slice across for x in range(im2.size): # slice down pix = im2.getpixel((y,x)) if pix != 255: inletter = True if foundletter == False and inletter == True: foundletter = True start = y if foundletter == True and inletter == False: foundletter = False end = y letters.append((start,end)) inletter=False print letters
В результате у нас получалось следующее:
[(6, 14), (15, 25), (27, 35), (37, 46), (48, 56), (57, 67)]
Это позиции по горизонтали начала и конца каждого символа.
Распознавание изображений можно считать самым большим успехом современного ИИ, что позволило ему внедриться во все виды коммерческих приложений. Прекрасным примером этого являются почтовые индексы. На самом деле во многих странах они читаются автоматически, т. к. научить компьютер распознавать номера довольно простая задача. Это может быть не очевидно, но распознавание образов считается проблемой ИИ, хоть и очень узкоспециализированной.
Чуть ли ни первой вещью, с которой сталкиваются при знакомстве с ИИ в распознавании образов являются нейронные сети. Лично я никогда не имел успеха с нейронными сетями при распознавании символов. Я обычно обучаю его 3-4 символам, после чего точность падает так низко, что она была бы на порядок выше, отгадывай я символы случайным образом. Сначала это вызвало у меня легкую панику, т. к. это было тем самым недостающем звеном в моей диссертации. К счастью, недавно я прочитал статью о vector-space поисковых системах и посчитал их альтернативным методом классификации данных. В конце концов они оказались лучшем выбором, т. к.
Конечно, бесплатного сыра не бывает. Главный недостаток в скорости. Они могут быть намного медленнее нейронных сетей. Но я думаю, что их плюсы все же перевешивают этот недостаток.
Если хотите понять, как работает векторное пространство, то советую почитать Vector Space Search Engine Theory . Это лучшее, что я нашел для начинающих.
Я построил свое распознавание изображений на основе вышеупомянутого документа и это было первой вещью, которую я попробовал написать на любимом ЯП, который я в это время изучал. Прочитайте этот документ и как вы поймете его суть – возвращайтесь сюда.
Уже вернулись? Хорошо. Теперь мы должны запрограммировать наше векторное пространство. К счастью, это совсем не сложно. Приступим.
Import math class VectorCompare: def magnitude(self,concordance): total = 0 for word,count in concordance.iteritems(): total += count ** 2 return math.sqrt(total) def relation(self,concordance1, concordance2): relevance = 0 topvalue = 0 for word, count in concordance1.iteritems(): if concordance2.has_key(word): topvalue += count * concordance2 return topvalue / (self.magnitude(concordance1) * self.magnitude(concordance2))
Это реализация векторного пространства на Python в 15 строк. По существу оно просто принимает 2 словаря и выдает число от 0 до 1, указывающее как они связаны. 0 означает, что они не связаны, а 1, что они идентичны.
Следующее, что нам нужно – это набор изображений, с которыми мы будем сравнивать наши символы. Нам нужно обучающее множество. Это множество может быть использовано для обучения любого рода ИИ, который мы будем использовать (нейронные сети и т. д.).
Используемые данные могут быть судьбоносными для успешности распознавания. Чем лучше данные, тем больше шансов на успех. Так как мы планируем распознавать конкретную капчу и уже можем извлечь из нее символы, то почему бы не использовать их в качестве обучающего множества?
Это я и сделал. Я скачал много сгенерированных капч и моя программа разбила их на буквы. Тогда я собрал полученные изображения в коллекции (группы). После нескольких попыток у меня было по крайней мере один пример каждого символа, которые генерировала капча. Добавление большего количества примеров повысит точность распознавания, но мне хватило и этого для подтверждения моей теории.
From PIL import Image import hashlib import time im = Image.open("captcha.gif") im2 = Image.new("P",im.size,255) im = im.convert("P") temp = {} print im.histogram() for x in range(im.size): for y in range(im.size): pix = im.getpixel((y,x)) temp = pix if pix == 220 or pix == 227: # these are the numbers to get im2.putpixel((y,x),0) inletter = False foundletter=False start = 0 end = 0 letters = for y in range(im2.size): # slice across for x in range(im2.size): # slice down pix = im2.getpixel((y,x)) if pix != 255: inletter = True if foundletter == False and inletter == True: foundletter = True start = y if foundletter == True and inletter == False: foundletter = False end = y letters.append((start,end)) inletter=False # New code is here. We just extract each image and save it to disk with # what is hopefully a unique name count = 0 for letter in letters: m = hashlib.md5() im3 = im2.crop((letter , 0, letter,im2.size)) m.update("%s%s"%(time.time(),count)) im3.save("./%s.gif"%(m.hexdigest())) count += 1
На выходе мы получаем набор изображений в этой же директории. Каждому из них присваивается уникальных хеш на случай, если вы будете обрабатывать несколько капч.
Вот результат этого кода для нашей тестовой капчи:
Вы сами решаете, как хранить эти изображения, но я просто поместил их в директории с тем же именем, что находится на изображении (символ или цифра).
Последний шаг. У нас есть извлекание текста, извлекание символов, техника распознавания и обучающее множество.
Мы получаем изображение капчи, выделяем текст, получаем символы, а затем сравниванием их с нашим обучающим множеством. Вы можете скачать окончательную программу с обучающим множеством и небольшим количеством капч по этой ссылке .
Здесь мы просто загружаем обучающее множество, чтобы иметь возможность сравнивать с ним:
Def buildvector(im): d1 = {} count = 0 for i in im.getdata(): d1 = i count += 1 return d1 v = VectorCompare() iconset = ["0","1","2","3","4","5","6","7","8","9","0","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t"," u","v","w","x","y","z"] imageset = for letter in iconset: for img in os.listdir("./iconset/%s/"%(letter)): temp = if img != "Thumbs.db": temp.append(buildvector(Image.open("./iconset/%s/%s"%(letter,img)))) imageset.append({letter:temp})
А тут уже происходит все волшебство. Мы определяем, где находится каждый символ и проверяем его с помощью нашего векторного пространства. Затем сортируем результаты и печатаем их.
Count = 0 for letter in letters: m = hashlib.md5() im3 = im2.crop((letter , 0, letter,im2.size)) guess = for image in imageset: for x,y in image.iteritems(): if len(y) != 0: guess.append((v.relation(y,buildvector(im3)),x)) guess.sort(reverse=True) print "",guess count += 1
Теперь у нас есть все, что нужно и мы можем попробовать запустить нашу чудо-машину.
Входной файл – captcha.gif . Ожидаемый результат: 7s9t9j
Python crack.py (0.96376811594202894, "7") (0.96234028545977002, "s") (0.9286884286888929, "9") (0.98350370609844473, "t") (0.96751165072506273, "9") (0.96989711688772628, "j")
Здесь мы видем предполагаемый символ и степень уверенности в том, что это действительно он (от 0 до 1).
Похоже, что у нас действительно все получилось!
На самом деле на тестовых капчах данный скрипт будет выдавать успешный результат примерно в 22% случаев.
Python crack_test.py Correct Guesses - 11.0 Wrong Guesses - 37.0 Percentage Correct - 22.9166666667 Percentage Wrong - 77.0833333333
Большинство неверных результатов приходится на неправильное распознаваине цифры «0» и буквы «О». Нет ничего неожиданного, т. к. даже люди их часто путают. У нас еще есть проблема с разбиванием на символы, но это можно решить просто проверив результат разбиения и найдя золотую середину.
Однако, даже с таким не очень совершенным алгоритмом мы можем разгадывать каждую пятую капчу за такое время, где человек не успел бы разгадать и одну.
Выполнение этого кода на Core 2 Duo E6550 дает следующие результаты:
Real 0m5.750s user 0m0.015s sys 0m0.000s
В нашем каталоге находится 48 капч, из чего следует, что на разгадывание одной уходит примерно 0.12 секунд. С нашими 22% процентами успешного разгадывания мы можем разгадывать около 432 000 капч в день и получать 95 040 правильных результатов. А если использовать многопоточность?
Вот и все. Надеюсь, что мой опыт будет использован вами в хороших целях. Я знаю, что вы можете использовать этот код во вред, но чтобы сделать действительно нечто опасное вы должны довольно сильно его изменить.
Для тех, кто пытается защитить себя капчей я могу сказать, что это вам не сильно поможет, т. к. их можно обойти программно или просто платить другим людям, которые будут разгадывать их вручную. Подумайте над другими способами защиты.
Доброго времени суток! Недавно, под некоторые нужды потребовалась капча на Python’e от «любопытных». Посмотрел в Google и ничего нормального без Django не увидел. В итоге пришёл в выводу, что напишу не как отдельное WSGI приложение, а просто CGI скриптом.
Для работы с изображениями был выбран пакет Python Imaging Library . К сожалению PIL даёт несколько скудные возможности по сравнению с GD2 в PHP .
Скачать пакет для Python версий 2 и 3 можно от сюда: http://www.lfd.uci.edu/~gohlke/pythonlibs/
Сразу хочу заметить, что используется Python 3.1 , хотя я думаю что на Python 2.6+ он тоже запуститься.
И так, в итоге мы должны получить генерацию изображения из 5-6 символов на разноцветном фоне.
Так как архив со всем готовым я тут не выкладываю, всё будем делать по руководству.
Каталоги и их иерархия:
Cgi-bin
—captcha
—backgrounds
—fonts
—index.py
Думаю с этим понятно, что в папке cgi-bin лежит папка captcha в которой лежат backgrounds и fonts и сам скрипт index.py.
Теперь нам нужны бэкграунды. Вбиваем «backgrounds» в Google.Картинки и качаем штук 15-20. И нужно сделать такие прямоугольники размером 200х60 px в формате JPEG .
Всё кидаем в папку backgrounds.
Теперь шрифты. Нас интересуют TrueType шрифты (*.ttf). Берём штук 15 шрифтов позаковыристей и кидаем в папку fonts.
Всё бэкграунды есть, шрифты есть, теперь сам index.py.
Print("Content-Type: image/jpeg"); print(""); import sys, os, re, random from PIL import Image, ImageFont, ImageDraw class captcha(object): def __init__(self): self.string = ""; self.root = os.getcwd(); self.path_backgrounds = self.root+"/backgrounds/"; self.path_fonts = self.root+"/fonts/"; def gen_string(self): chars = ("a", "b", "d", "e", "f", "g", "h", "j", "m", "n", "q", "r", "t", "u", "y", "A", "B", "D", "E", "F", "G", "H", "J", "M", "N", "Q", "R", "T", "U", "Y", "1", "2", "3", "4", "5", "6", "7", "8", "9"); for i in range(random.randint(5, 6)): self.string += chars; return self.string; def gen_backgrounds(self): images = ; if os.path.exists(self.path_backgrounds): for f in os.listdir(self.path_backgrounds): if os.path.isdir(self.path_backgrounds+"/"+f): continue; if re.search("\.(jpeg|jpg)$", f, re.IGNORECASE): images.append(self.path_backgrounds+"/"+f); else: sys.exit(); if len(images) == 0: sys.exit(); return images; def gen_fonts(self): fonts = ; if os.path.exists(self.path_fonts): for f in os.listdir(self.path_fonts): if os.path.isdir(self.path_fonts+"/"+f): continue; if re.search("\.(ttf)$", f, re.IGNORECASE): fonts.append(self.path_fonts+"/"+f); else: sys.exit(); if len(fonts) == 0: sys.exit(); return fonts; def gen_image(self): string = self.gen_string(); backgrounds = self.gen_backgrounds(); fonts = self.gen_fonts(); image = Image.new("RGB", (200,60), "#FFF") draw = ImageDraw.Draw(image); for i in range(5): background = Image.open(backgrounds); x = random.randint(0, 160); cp = background.crop((x, 0, x+40, 60)); image.paste(cp, (i*40, 0)); if len(string) == 5: x = random.randint(25, 30); else: x = random.randint(8, 11); for char in string: font = fonts; y = random.randint(5, 25); font_size = random.randint(24, 30); color_dark = "rgb("+str(random.randint(0,150))+","+str(random.randint(0,100))+","+str(random.randint(0,150))+")"; color_font = "rgb("+str(random.randint(50,200))+","+str(random.randint(0,150))+","+str(random.randint(50,200))+")"; ttf = ImageFont.truetype(font, font_size) draw.text((x+1, y+1), char, fill=color_dark, font=ttf) draw.text((x, y), char, fill=color_font, font=ttf) x += random.randint(13, 15) + 18; image.save(sys.stdout, "JPEG") cp = captcha(); cp.gen_image(); #cp.string; строка символов
Вот и всё. У меня по адресу http://localhost/cgi-bin/captcha/index.py генерируется изображение. Далее можно дописать механизм хранения генерированной строки (cp.string ) с сессиях или ещё где-нибудь.
Решил немного осилить Python, но осиливать "лишь бы не пхп" не интересно. Корыстным интересом стало авторазгадывание капчи Python .
Началось дело постом с хабра от 2012 года (графическая библиотека вообще 2009 года).
Код: https://habrahabr.ru/post/149091/
У меня из коробки стоит 2.7.10, а код писался под 2.5 (с либой PIL). Пишут, что на 2.7.3 отлично запускается.
PIL накатил так вот
Код: # download
curl -O -L http://effbot.org/media/downloads/Imaging-1.1.7.tar.gz
# extract
tar -xzf Imaging-1.1.7.tar.gz
cd Imaging-1.1.7
# build and install
python setup.py build
sudo python setup.py install
# or install it for just you without requiring admin permissions:
# python setup.py install --user
Потом импортировал модуль так вот
Код: #набрать в консольку
python
#включится интерпретатор, которому скомандовать
import PIL
#если все ок, нажать Ctrl+D для выхода
Змеюка не дружит с кирилицей, в начало файла добавил конструкцию (чтоб стало возможно комментить поделку кирилицей)
Код: # -*- coding: utf-8 -*-
Вот сам велосипед (не умею писать циклы и не знаю как eval, поэтому многое подставлял руками).
Код: # -*- coding: utf-8 -*-
#эта херь нужна для русских символов
from PIL import Image
from operator import itemgetter
im = im.convert("P")
his = im.histogram()
values = {}
for i in range(256):
values[i] = his[i]
for j,k in sorted(values.items(), key=itemgetter(1), reverse=True)[:15]:
print "or pix ==",j#,k
#в переменной j хранятся десять самых популярных цветов
from PIL import Image
im = Image.open("captcha.gif")
im = im.convert("P")
im = im.convert("P")
for x in range(im.size):
for y in range(im.size):
pix = im.getpixel((y,x))
temp = pix
#сюда цвета
im2.putpixel((y,x),0)
im2.save("output.gif")
#тут вроде опять все с начала
from PIL import Image
im = Image.open("output.gif")
im = im.convert("P")
im2 = Image.new("P",im.size,255)
im = im.convert("P")
for x in range(im.size):
for y in range(im.size):
pix = im.getpixel((y,x))
temp = pix
if pix == 255: # these are the numbers to get
im2.putpixel((y,x),0)
# new code starts here
inletter = False
foundletter=False
start = 0
end = 0
pix = im2.getpixel((y,x))
if pix != 255:
inletter = True
foundletter = True
start = y
foundletter = False
end = y
letters.append((start,end))
Inletter=False
print letters
#фиг знает
class VectorCompare:
def magnitude(self,concordance):
total = 0
for word,count in concordance.iteritems():
total += count ** 2
return math.sqrt(total)
Def relation(self,concordance1, concordance2):
relevance = 0
topvalue = 0
for word, count in concordance1.iteritems():
if concordance2.has_key(word):
topvalue += count * concordance2
return topvalue / (self.magnitude(concordance1) * self.magnitude(concordance2))
#набор символов
from PIL import Image
import hashlib
import time
im = Image.open("captcha.gif")
im2 = Image.new("P",im.size,255)
im = im.convert("P")
print im.histogram()
for x in range(im.size):
for y in range(im.size):
pix = im.getpixel((y,x))
temp = pix
#сюда цвета
if pix == 187 or pix == 224 or pix == 188 or pix == 223 or pix == 145 or pix == 151 or pix == 181 or pix == 144 or pix == 225 or pix == 182 or pix == 189 or pix == 12 or pix == 17 or pix == 139 or pix == 152: # or pix ==
im2.putpixel((y,x),0)
inletter = False
foundletter=False
start = 0
end = 0
for y in range(im2.size): # slice across
for x in range(im2.size): # slice down
pix = im2.getpixel((y,x))
#тут было "не равно 255" то есть - было "не равно белому"
if pix == 255:
inletter = True
If foundletter == False and inletter == True:
foundletter = True
start = y
If foundletter == True and inletter == False:
foundletter = False
end = y
letters.append((start,end))
inletter=False
# New code is here. We just extract each image and save it to disk with
# what is hopefully a unique name
count = 0
for letter in letters:
m = hashlib.md5()
im3 = im2.crop((letter , 0, letter,im2.size))
m.update("%s%s"%(time.time(),count))
im3.save("./%s.gif"%(m.hexdigest()))
count += 1
Принцип работы такой: составить гистограмму, убрать самый частые оттенки, оставшееся пересохранить черно-белым, разбить по границам символов, сравнивать символы с образцами.
Оригинальная капча, без 10 популярных оттенков, без 15 популярных оттенков (разбивать на символы не стал - ибо есть нецелый символ).
Оригинальная капча, без 15 популярных оттенков, разбитая на 2 символа (грязновато).
Под простую капчу вполне реально запилить разгадыватель. Нужны интересные места с простыми капчами для допиливания и обкатки.
Есть разные способы для обхода CAPTCHA, которыми защищены сайты. Во-первых, существуют специальные сервисы, которые используют дешевый ручной труд и буквально за $1 предлагают решить 1000 капч. В качестве альтернативы можно попробовать написать интеллектуальную систему, которая по определенным алгоритмам будет сама выполнять распознавание. Последнее теперь можно реализовать с помощью специальной утилиты.
Именно так называлась работа, представленная мной на Балтийском научно-инженерном конкурсе, и принёсшая мне очаровательную бумажку с римской единичкой, а также новенький ноутбук.
Работа заключалась в распознавании CAPTCHA, используемых крупными операторами сотовой связи в формах отправки SMS, и демонстрации недостаточной эффективности применяемого ими подхода. Чтобы не задевать ничью гордость, будем называть этих операторов иносказательно: красный, жёлтый, зелёный и синий.
Проект получил официальное название Captchure
и неофициальное Breaking Defective Security Measures
. Любые совпадения случайны.
Как ни странно, все (ну, почти все) эти CAPTCHA оказались довольно слабенькими. Наименьший результат - 20% - принадлежит жёлтому оператору, наибольший - 86% - синему. Таким образом, я считаю, что задача «демонстрации неэффективности» была успешно решена.
Причины выбора именно сотовых операторов тривиальны. Уважаемому Научному Жюри я рассказывал байку о том, что «сотовые операторы имеют достаточно денег, чтобы нанять программиста любой квалификации, и, в то же время, им необходимо минимизировать количество спама; таким образом, их CAPTCHA должны быть довольно мощными, что, как показывает моё исследование, совсем не так». На самом же деле всё было гораздо проще. Я хотел набраться опыта, взломав распознав какую-нибудь простую CAPTCHA, и выбрал жертвой CAPTCHA красного оператора. А уже после этого, задним числом родилась вышеупомянутая история.
Итак, ближе к телу. Никакого мегапродвинутого алгоритма для распознавания всех четырёх видов CAPTCHA у меня нет; вместо него я написал 4 различных алгоритма для каждого вида CAPTCHA по отдельности. Однако, несмотря на то, что алгоритмы в деталях различны, в целом они оказались очень похожими.
Как и многие авторы до меня, я разбил задачу распознавания CAPTCHA на 3 подзадачи: предварительную обработку (препроцесс), сегментацию и распознавание. На этапе препроцесса из исходного изображения удаляются различные шумы, искажения и пр. В сегментации из исходного изображения выделяются отдельные символы и производится из постобработка (например, обратный поворот). При распознавании символы по одному обрабатываются предварительно обученной нейросетью.
Существенно различался только препроцесс. Это связано с тем, что в различных CAPTCHA применяются различные методы искажения изображений, соответственно, и алгоритмы для удаления этих искажений сильно различаются. Сегментация эксплуатировала ключевую идею поиска компонентов связности с незначительными наворотами (значительными их пришлось сделать только у жёлто-полосатых). Распознавание было абсолютно одинаковым у трёх операторов из четырёх - опять-таки, отличался только жёлтый оператор.
Наконец, белым закрашиваются мелкие (меньше 10px) чёрные связные области:
Иногда (редко, но бывает) буква распадается на несколько частей; для исправления этого досадного недоразумения я применяю довольно простую эвристику, оценивающую принадлежность нескольких компонентов связности к одному символу. Эта оценка зависит только от горизонтального положения и размеров описывающих прямоугольников (bounding boxes) каждого символа.
Нетрудно заметить, что многие символы оказались объединены в один компонент связности, в связи с чем надо их разделять. Здесь на помощь приходит тот факт, что на изображении всегда ровно 5 символов. Это позволяет с большой точностью вычислять, сколько символов находится в каждом найденном компоненте.
Для объяснения принципа работы такого алгоритма придётся немного углубиться в матчасть. Обозначим количество найденных сегментов за n, а массив ширин (правильно сказал, да?) всех сегментов за widths[n]. Будем считать, что если после вышеупомянутых этапов n > 5, изображение распознать не удалось. Рассмотрим все возможные разложения числа 5 на целые положительные слагаемые. Их немного - всего 16. Каждое такое разложение соответствует некоторой возможной расстановке символов по найденным компонентам связности. Логично предположить, что чем шире получившийся сегмент, тем больше символов он содержит. Из всех разложений пятёрки выберем только те, в которых количество слагаемых равно n. Поделим каждый элемент из widths на widths - как бы нормализуем их. То же самое проделаем со всеми оставшимися разложениями - поделим каждое число в них на первое слагаемое. А теперь (внимание, кульминация!) заметим, что получившиеся упорядоченные n-ки можно мыслить как точки в n-мерном пространстве. С учётом этого, найдём ближайшее по Евклиду разложение пятёрки к нормализованному widths. Это и есть искомый результат.
Кстати, в связи с этим алгоритмом мне в голову пришёл ещё один интересный способ искать все разложения числа на слагаемые, который я, правда, так и не реализовал, закопавшись в питоновских структурах данных. Вкратце - он довольно очевидно вылезает, если заметить, что количество разложений определённой длины совпадает с соответствующим уровнем треугольника Паскаля. Впрочем, я уверен, что этот алгоритм давным-давно известен.
Так вот, после определения количества символов в каждом компоненте наступает следующая эвристика - мы считаем, что разделители между символами тоньше, чем сами символы. Для того чтобы воспользоваться этим сокровенным знанием, расставим по сегменту n-1 разделителей, где n - количество символов в сегменте, после чего в небольшой окрестности каждого разделителя посчитаем проекцию изображения вниз. В результате этого проецирования мы получим информацию о том, сколько в каждом столбце пикселей принадлежат символам. Наконец, в каждой проекции найдём минимум и сдвинем разделитель туда, после чего покромсаем изображение по этим разделителям.
Наконец, распознавание. Как я уже говорил, для него я применяю нейросеть. Для её обучения сначала я прогоняю две сотни изображений под общим заголовком trainset через уже написанные и отлаженные первые два этапа, в результате чего получаю папку с большим количеством аккуратно нарезанных сегментов. Затем, руками вычищаю мусор (результаты неправильной сегментации, например), после чего результат привожу к одному размеру и отдаю на растерзание FANN. На выходе получаю обученную нейросеть, которая и используется для распознавания. Эта схема дала сбой только один раз - но об этом позже.
В результате на тестовом наборе (не использованном для обучения, кодовое имя - testset ) из 100 картинок были правильно распознаны 45. Не слишком высокий результат - его, конечно, можно улучшить, например, уточнив препроцесс или переделав распознавание, но, честно говоря, мне было лень с этим возиться.
Кроме того, я использовал ещё один критерий оценки производительности алгоритма - средняя ошибка. Вычислялся он следующим образом. Для каждого изображения находилось расстояние Левенштейна между мнением алгоритма об этом изображении и правильным ответом - после чего бралось среднее арифметическое по всем изображениям. Для этого вида CAPTCHA средняя ошибка составила 0.75 символа/изображение. Мне кажется, что это более точный критерий, нежели просто процент распознавания.
Кстати говоря, почти везде (кроме жёлтого оператора) у меня использовалась именно такая схема - 200 картинок в trainset, 100 - в testset.
Следующей целью я выбрал зелёных - хотелось взяться за что-то более серьёзное, чем подбор матрицы искажений.
Достоинства:
Недостатки:
Оказалось, что даже несмотря на то, что эти недостатки, казалось бы, незначительны, их эксплуатация позволяет весьма эффективно расправиться со всеми достоинствами.
Опять начнём с предварительной обработки. Сначала оценим угол поворота прямоугольника, на котором лежат символы. Для этого применим к исходному изображению оператор Erode (поиск локального минимума), затем Threshold, чтобы выделить остатки прямоугольника и, наконец, инверсию. Получим симпатичное белое пятно на чёрном фоне.
Далее начинается глубокая мысль. Первое. Для оценки угла поворота всего прямоугольника достаточно оценить угол поворота его верхней стороны. Второе. Можно оценить угол поворота верхней стороны поиском прямой, параллельной этой стороне. Третье. Для описания любой прямой, кроме строго вертикальной, достаточно двух параметров - смещения по вертикали от центра координат и угла наклона, причём нас интересует только второй. Четвёртое. Задачу поиска прямой можно решить не очень большим перебором - слишком больших углов поворота там не бывает, да и сверхвысокая точность нам не нужна. Пятое. Для поиска необходимой прямой можно сопоставить каждой прямой оценку того, насколько она близка к искомой, после чего выбрать максимум. Шестое. Самое Важное. Чтобы оценить некоторый угол наклона прямой, представим, что изображения сверху касается прямая с таким углом наклона. Понятно, что из размеров изображения и угла наклона можно однозначно вычислить смещение прямой по вертикали, так что она задаётся однозначно. Далее, постепенно будем двигать эту прямую вниз. В какой-то момент она коснётся белого пятна. Запомним этот момент и площадь пересечения прямой с пятном. Напомню, что прямая имеет 8ми-связное на плоскости, поэтому гневные выкрики из зала о том, что прямая имеет одно измерение, а площадь - понятие двумерное, здесь неуместны. Затем, ещё некоторое время будем двигать эту прямую вниз, на каждом шаге запоминая площадь пересечения, после чего просуммируем полученные результаты. Эта сумма и будет оценкой данного угла поворота.
Подводя итог вышесказанного: будем искать такую прямую, что при движении её вниз по изображению яркость пикселей, лежащих на этой прямой, возрастает наиболее резко.
Итак, угол поворота найден. Но не следует спешить тут же применить полученное знание. Дело в том, что это испорит связность изображения, а она нам ещё понадобится.
Следующий шаг - отделение символов от фона. Здесь нам здорово поможет тот факт, что символы значительно темнее фона. Вполне логичный шаг со стороны разработчиков - иначе картинку было бы очень сложно прочитать. Кто не верит - может попробовать самостоятельно бинаризовать изображение и убедиться воочию.
Однако, подход «в лоб» - попытка отсечь символы пороговым преобразованием - здесь не работает. Наилучший результат, которого мне удалось добиться - при t=140 - выглядит весьма плачевно. Остаётся слишком много мусора. Поэтому пришлось применить обходной путь. Идея здесь следующая. Символы, как правило, связны. Причём им часто принадлежат самые тёмные точки на изображении. А что если попробовать применить заливку из этих самых тёмных точек, а затем выкинуть слишком маленькие залитые области - очевидный мусор?
Результат, честно говоря, поразителен. На большинстве изображений удаётся избавиться от фона полностью. Впрочем, бывает, что символ распадается на несколько частей - в этом случае может помочь один костыль в сегментации - но об этом чуть позже.
Наконец, комбинация операторов Dilate и Erode избавляет нас от мелких дырок, оставшихся в символах, что помогает упростить распознавание.
Сегментация здесь значительно проще, чем препроцесс. В первую очередь ищем компоненты связности.
Затем, объединяем близкие по горизонтали компоненты (процедура ровно та же, что и ранее):
Этот алгоритм позволил достичь результата в 69% успешно распознанных изображений и получить среднюю ошибку 0.3 символа/изображение.
Итак, третьим статус «defeated» получил синий оператор. Это была, так сказать, передышка перед действительно крупной рыбой…
Здесь сложно что-то записать в достоинства, но я, всё же, попробую:
В противовес этому:
Итак, препроцесс. Начнём с отсечения фона. Поскольку изображение трёхцветное, порежем его на каналы, а затем выбросим все точки, которые ярче 116 по всем каналам. Получим вот такую симпатичную маску:
Затем, преобразуем изображение в цветовое пространство HSV (Википедия). Это сохранит информацию о цвете символов, а заодно и уберёт градиент с их краёв.
Применим к результату полученную ранее маску:
На этом препроцесс заканчивается. Сегментация также весьма тривиальна. Начнём, как всегда, с компонентов связности:
Можно было бы на этом и остановиться, но так получается всего 73%, что меня совсем не устраивает - всего на 4% лучше, чем результат заведомо более сложной CAPTCHA. Итак, следующим шагом будет обратный поворот символов. Здесь нам пригодится уже упомянутый мной факт о том, что местные символы хорошо вписываются в прямоугольник. Идея состоит в том, чтобы найти описывающий прямоугольник для каждого символа, а затем по его наклону вычислить наклон собственно символа. Здесь под описывающим прямоугольником понимается такой, что он, во-первых, содержит в себе все пиксели данного символа, а, во-вторых, имеет наименьшую площадь из всех возможных. Я пользуюсь готовой реализацией алгоритма поиска такого прямоугольника из OpenCV (MinAreaRect2).
Этот алгоритм успешно распознаёт 86% изображений при средней ошибке в 0.16 символа/изображение, что подтверждает предположение о том, что эта CAPTCHA - действительно самая простая. Впрочем, и оператор не самый крупный…
Наступает самое интересное. Так сказать, апофеоз моей творческой деятельности 🙂 Эта CAPTCHA - действительно самая сложная как для компьютера, так и, к сожалению для человека.
Достоинства:
Недостатки:
Над первым шагом я думал долго. Первое, что приходило в голову - поиграться с локальными максимумами (Dilate), чтобы удалить мелкий шум. Однако, такой подход приводил к тому, что и от букв мало что оставалось - только рваные очертания. Проблема усугублялась тем, что текстура самих символов неоднородная - это хорошо видно при большом увеличении. Чтобы от неё избавиться, я решил выбрать самый тупой способ - открыл Paint и записал коды всех цветов, встречающихся в изображениях. Оказалось, что всего в этих изображениях встречаются четыре различных текстуры, причём на три из них приходится по 4 различных цвета, а на последнюю - 3; более того, все компоненты этих цветов оказались кратными 51. Далее я составил таблицу цветов, при помощи которой удалось избавиться от текстуры. Впрочем, перед этим «ремапом» я ещё затираю все слишком светлые пиксели, которые обычно находятся по краям символов - иначе приходится помечать их как шум, а потом с ними бороться, в то время как информации в них содержится немного.
Итак, после этого преобразования на изображении находится не более 6 цветов - 4 цвета символов (будем их условно называть серым, синим, светло-зелёным и тёмно-зелёным), белый (цвет фона) и «неизвестный», обозначающий, что цвет пикселя на его месте не удалось отождествить ни с одним из известных цветов. Называть условно - потому что к этому моменту я избавляюсь от трёх каналов и перехожу к привычному и удобному монохромному изображению.
Следующим шагом стала очистка изображения от линий. Здесь ситуацию спасает тот факт, что эти линии очень тонкие - всего 1 пиксель. Напрашивается простой фильтр: пройтись по всему изображению, сравнивая цвет каждого пикселя с цветами его соседей (парами - по вертикали и горизонтали); если соседи по цвету совпадают, и при этом не совпадают с цветом самого пикселя - сделать его таким же, как и соседи. Я применяю чуть более навороченную версию того же фильтра, который работает в два этапа. На первом он оценивает соседей на расстоянии 2, на втором - на расстоянии 1. Это позволяет добиться вот такого эффекта:
Далее я избавляюсь от большинства пятен, а также от «неизвестного» цвета. Для этого я сначала ищу все мелкие связные области (меньшие 15 по площади, если быть точным), наношу их на чёрно-белую маску, после чего результат объединяю с областями, занятыми «неизвестным» цветом.
При помощи этих масок я натравливаю алгоритм Inpaint (а точнее, его реализацию в OpenCV). Это позволяет весьма эффективно вычистить большую часть мусора из изображения.
Однако, реализация этого алгоритма в OpenCV была создана для работы с фотографиями и видео, а не распознавания искусственно созданных изображений с зашумлённым текстом. После его применения появляются градиенты, чего хотелось бы избежать, чтобы упростить сегментацию. Таким образом, приходится производить дополнительную обработку, а именно - повышение резкости. Для цвета каждого пикселя я вычисляю ближайший к нему из вышеупомянутой таблицы (напомню, там 5 цветов - по одному на каждую из текстур символов и белый).
Наконец, последним шагом препроцесса будет удаление всех оставшихся мелких связных областей. Появляются они после применения Inpaint, поэтому никакого повторения здесь нет.
Переходим к сегментации. Её сильно усложняет тот факт, что символы находятся очень близко друг к другу. Может случиться такая ситуация, что за одним символом не видно половину другого. Совсем плохо становится, когда эти символы ещё и одного цвета. Кроме того, остатки мусора также играют свою роль - может случиться так, что на исходном изображении линии в большом количестве пересекались в одном месте. В этом случае тот алгоритм, который я описал ранее, окажется неспособным от них избавиться.
После недели, проведённой в бесплодных попытках написать сегментацию так же, как и в предыдущих случаях, я забил на это дело и сменил тактику. Моя новая стратегия заключалась в том, чтобы разделить весь процесс сегментации на две части. В первой оценивается угол поворота символов и выполняется обратный поворот. Во второй из уже развёрнутого изображения заново выделяются символы. Итак, приступим. Начнём, как всегда, с поиска компонентов связности.
Затем нужно оценить угол поворота каждого символа. Ещё при работе с оператором-фанатом-гринписа я придумал алгоритм для этого, но написал и применил его только здесь. Для того чтобы проиллюстрировать его работу, проведу аналогию. Представьте себе поршень, который движется на чёрно-белое изображение символа снизу вверх. Ручка поршня, за которую его толкают, расположена вертикально, рабочая площадка, которой он толкает - горизонтально, параллельно нижней части изображения и перпендикулярно ручке. Ручка прикреплена к площадке посередине, и в месте присоединения находится подвижное сочленение, в результате чего площадка может поворачиваться. Да простят меня специалисты по терминологии.
Пусть ручка двигается вверх, толкая перед собой площадку по законам физики. Будем считать, что материальным является только белое изображение символа, а сквозь чёрный фон поршень с лёгкостью проходит. Тогда поршень, дойдя до белого цвета, начнёт с ним взаимодействовать, а именно, поворачиваться - при условии, что сила к ручке всё ещё прикладывается. Остановиться он может в двух случаях: если он упёрся в символ по обе стороны от точки приложения силы, или если он упёрся в символ самой точкой приложения силы. Во всех остальных случаях он сможет продолжать движение. Внимание, кульминация: будем считать, что угол поворота символа - это угол наклона поршня в тот момент, когда он остановился.
Этот алгоритм довольно точен, но заведомо слишком большие результаты (больше 27 градусов) я не учитываю. Из оставшихся я нахожу среднее арифметическое, после чего целиком всё изображение поворачиваю на минус этот угол. Затем выполняю поиск компонентов связности ещё раз.
Дальше становится всё интереснее и интереснее. В предыдущих примерах я начинал различные махинации с полученными сегментами, после чего передавал их нейросети. Здесь всё иначе. Сначала, для того чтобы хотя бы частично восстановить информацию, утраченную после разделения изображения на компоненты связности, я на каждом из них тёмно-серым цветом (96) дорисовываю «фон» - то, что было рядом с вырезанным сегментом, но в него не попало, после чего сглаживаю очертания символов, применяя ту же процедуру, что и в препроцессе для линий (с расстоянием до соседа, равным единице).
Формально (с точки зрения модулей программы) здесь сегментация заканчивается. Внимательный читатель, должно быть, заметил, что нигде не упоминалось разделение слипшихся символов. Да, это так - на распознавание я их передаю именно в таком виде, а допиливаю уже на месте.
Причина заключается в том, что тот метод разделения слипшихся символов, который был описан ранее (с наименьшей проекцией) здесь не работает - шрифт выбран авторами весьма удачно. Поэтому приходится применять другой, более сложный подход. В основе этого подхода лежит идея, что нейросеть можно использовать для сегментации.
В самом начале я описывал алгоритм, позволяющий найти количество символов в сегменте при известой ширине этого сегмента и общем количестве символов. Этот же алгоритм используется и здесь. Для каждого сегмента вычисляется количество символов в нём. Если он там один - ничего допиливать не нужно, и этот сегмент сразу отправляется >>= в нейросеть. Если же символ там не один, то вдоль сегмента на равных расстояниях расставляются потенциальные разделители. Затем каждый разделитель двигается в своей небольшой окрестности, и попутно вычисляется реакция нейросети на символы около этого разделителя, после чего остаётся лишь выбрать максимум (на самом деле, там всё это делает довольно тупой алгоритм, но, в принципе, всё действительно приблизительно так).
Естественно, участие нейросети в процессе сегментации (или досегментации, если угодно) исключает возможность использовать ту схему обучения нейросети, которую я уже описывал. Если точнее, он не позволяет получить самую первую нейросеть - для обучения других может использоваться она. Поэтому я поступаю довольно просто - использую обычные методы сегментации (проекция) для обучения нейросети, в то время как при её использовании в работу вступает вышеописанный алгоритм.
Есть ещё одна тонкость, связанная с использованием нейросети в этом алгоритме. В предыдущих примерах нейросеть обучалась на почти необработанных результатах препроцесса и сегментации. Здесь это позволяло получить не более 12% успешного распознавания. Меня это категорически не устраивало. Поэтому, прежде чем начинать очередную эпоху обучения нейросети, я вносил в исходные изображения различные искажений, грубо моделирующие реальные: добавить белых/серых/чёрных точек, серых линий/кругов/прямоугольников, повернуть. Также я увеличил trainset с 200 изображений до 300 и добавил так называемый validset для проверки качества обучения во время обучения на 100 изображений. Это позволило добиться увеличения производительности где-то процентов на пять, а вкупе с сегментацией нейросетью как раз и дало тот результат, о котором я говорил в начале статьи.
Предоставление статистики осложнено тем, что у меня в итоге получилось две нейросети: одна давала больший процент распознавания, а другая - меньшую ошибку. Здесь я привожу результаты первой.
Всего, как я уже говорил неоднократно, в testset насчитывалось 100 изображений. Из них успешно распознано было 20, неудачно, соответственно, 80, а ошибка составила 1.91 символа на изображение. Заметно хуже, чем у всех других операторов, но и CAPTCHA соответствующая.
Всё, что относится к этой работе, я выложил в специальной ветке форума на своём сайте, в частности:исходный код , Netsukuku). В то же время, хочется чего-то, что, во-первых, возможно сделать за год (хотя бы вдвоём), и во-вторых, серьёзно претендовало бы на высокое место на том же ISEF. Может быть, вы сможете подсказать, в каком направлении мне следует двигаться?