Доброго времени суток! Недавно, под некоторые нужды потребовалась капча на 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 ) с сессиях или ещё где-нибудь.
Именно так называлась работа, представленная мной на Балтийском научно-инженерном конкурсе, и принёсшая мне очаровательную бумажку с римской единичкой, а также новенький ноутбук.
Работа заключалась в распознавании 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.
Green
Следующей целью я выбрал зелёных - хотелось взяться за что-то более серьёзное, чем подбор матрицы искажений.
Достоинства:
- Эффект трёхмерности
- Поворот и смещение
- Неравномерная яркость
Недостатки:
- Символы заметно темнее фона
- Верхнюю сторону прямоугольника хорошо видно - можно использовать для обратного поворота
Оказалось, что даже несмотря на то, что эти недостатки, казалось бы, незначительны, их эксплуатация позволяет весьма эффективно расправиться со всеми достоинствами.
Опять начнём с предварительной обработки. Сначала оценим угол поворота прямоугольника, на котором лежат символы. Для этого применим к исходному изображению оператор Erode (поиск локального минимума), затем Threshold, чтобы выделить остатки прямоугольника и, наконец, инверсию. Получим симпатичное белое пятно на чёрном фоне.
Далее начинается глубокая мысль. Первое. Для оценки угла поворота всего прямоугольника достаточно оценить угол поворота его верхней стороны. Второе. Можно оценить угол поворота верхней стороны поиском прямой, параллельной этой стороне. Третье. Для описания любой прямой, кроме строго вертикальной, достаточно двух параметров - смещения по вертикали от центра координат и угла наклона, причём нас интересует только второй. Четвёртое. Задачу поиска прямой можно решить не очень большим перебором - слишком больших углов поворота там не бывает, да и сверхвысокая точность нам не нужна. Пятое. Для поиска необходимой прямой можно сопоставить каждой прямой оценку того, насколько она близка к искомой, после чего выбрать максимум. Шестое. Самое Важное. Чтобы оценить некоторый угол наклона прямой, представим, что изображения сверху касается прямая с таким углом наклона. Понятно, что из размеров изображения и угла наклона можно однозначно вычислить смещение прямой по вертикали, так что она задаётся однозначно. Далее, постепенно будем двигать эту прямую вниз. В какой-то момент она коснётся белого пятна. Запомним этот момент и площадь пересечения прямой с пятном. Напомню, что прямая имеет 8ми-связное на плоскости, поэтому гневные выкрики из зала о том, что прямая имеет одно измерение, а площадь - понятие двумерное, здесь неуместны. Затем, ещё некоторое время будем двигать эту прямую вниз, на каждом шаге запоминая площадь пересечения, после чего просуммируем полученные результаты. Эта сумма и будет оценкой данного угла поворота.
Подводя итог вышесказанного: будем искать такую прямую, что при движении её вниз по изображению яркость пикселей, лежащих на этой прямой, возрастает наиболее резко.
Итак, угол поворота найден. Но не следует спешить тут же применить полученное знание. Дело в том, что это испорит связность изображения, а она нам ещё понадобится.
Следующий шаг - отделение символов от фона. Здесь нам здорово поможет тот факт, что символы значительно темнее фона. Вполне логичный шаг со стороны разработчиков - иначе картинку было бы очень сложно прочитать. Кто не верит - может попробовать самостоятельно бинаризовать изображение и убедиться воочию.
Однако, подход «в лоб» - попытка отсечь символы пороговым преобразованием - здесь не работает. Наилучший результат, которого мне удалось добиться - при t=140 - выглядит весьма плачевно. Остаётся слишком много мусора. Поэтому пришлось применить обходной путь. Идея здесь следующая. Символы, как правило, связны. Причём им часто принадлежат самые тёмные точки на изображении. А что если попробовать применить заливку из этих самых тёмных точек, а затем выкинуть слишком маленькие залитые области - очевидный мусор?
Результат, честно говоря, поразителен. На большинстве изображений удаётся избавиться от фона полностью. Впрочем, бывает, что символ распадается на несколько частей - в этом случае может помочь один костыль в сегментации - но об этом чуть позже.
Наконец, комбинация операторов Dilate и Erode избавляет нас от мелких дырок, оставшихся в символах, что помогает упростить распознавание.
Сегментация здесь значительно проще, чем препроцесс. В первую очередь ищем компоненты связности.
Затем, объединяем близкие по горизонтали компоненты (процедура ровно та же, что и ранее):
Этот алгоритм позволил достичь результата в 69% успешно распознанных изображений и получить среднюю ошибку 0.3 символа/изображение.
Blue
Итак, третьим статус «defeated» получил синий оператор. Это была, так сказать, передышка перед действительно крупной рыбой…
Здесь сложно что-то записать в достоинства, но я, всё же, попробую:
- Поворот символов - единственное более-менее серьёзное препятствие
- Фоновый шум в виде символов
- Символы иногда касаются друг друга
В противовес этому:
- Фон значительное светлее символов
- Символы хорошо вписываются в прямоугольник
- Разный цвет символов позволяет легко отделять их друг от друга
Итак, препроцесс. Начнём с отсечения фона. Поскольку изображение трёхцветное, порежем его на каналы, а затем выбросим все точки, которые ярче 116 по всем каналам. Получим вот такую симпатичную маску:
Затем, преобразуем изображение в цветовое пространство HSV (Википедия). Это сохранит информацию о цвете символов, а заодно и уберёт градиент с их краёв.
Применим к результату полученную ранее маску:
На этом препроцесс заканчивается. Сегментация также весьма тривиальна. Начнём, как всегда, с компонентов связности:
Можно было бы на этом и остановиться, но так получается всего 73%, что меня совсем не устраивает - всего на 4% лучше, чем результат заведомо более сложной CAPTCHA. Итак, следующим шагом будет обратный поворот символов. Здесь нам пригодится уже упомянутый мной факт о том, что местные символы хорошо вписываются в прямоугольник. Идея состоит в том, чтобы найти описывающий прямоугольник для каждого символа, а затем по его наклону вычислить наклон собственно символа. Здесь под описывающим прямоугольником понимается такой, что он, во-первых, содержит в себе все пиксели данного символа, а, во-вторых, имеет наименьшую площадь из всех возможных. Я пользуюсь готовой реализацией алгоритма поиска такого прямоугольника из OpenCV (MinAreaRect2).
Этот алгоритм успешно распознаёт 86% изображений при средней ошибке в 0.16 символа/изображение, что подтверждает предположение о том, что эта CAPTCHA - действительно самая простая. Впрочем, и оператор не самый крупный…
Yellow
Наступает самое интересное. Так сказать, апофеоз моей творческой деятельности 🙂 Эта 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. Может быть, вы сможете подсказать, в каком направлении мне следует двигаться?
Большинство людей не в курсе, но моей диссертацией была программа для чтения текста с изображения. Я думал, что, если смогу получить высокий уровень распознавания, то это можно будет использовать для улучшения результатов поиска. Мой отличный советник доктор Гао Джунбин предложил мне написать диссертацию на эту тему. Наконец-то я нашел время написать эту статью и здесь я постараюсь рассказать о всем том, что узнал. Если бы только было что-то подобное, когда я только начинал…
Как я уже говорил, я пытался взять обычные изображения из интернета и извлекать из них текст для улучшения результатов поиска. Большинство моих идей было основано на методах взлома капчи. Как всем известно, капча - это те самые всех раздражающее штуки, вроде «Введите буквы, которые вы видите на изображении» на страницах регистрации или обратной связи.
Капча устроена так, что человек может прочитать текст без труда, в то время, как машина - нет (привет, 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 поисковых системах и посчитал их альтернативным методом классификации данных. В конце концов они оказались лучшем выбором, т. к.
- Они не требуют обширного изучения
- Вы можете добавлять/удалять неправильные данные и сразу видеть результат
- Их легче понять и запрограммировать
- Они обеспечивают классифицированные результаты, таким образом вы сможете видеть топ X совпадений
- Не можете что-то распознать? Добавьте это и вы сможете разпознать это моментально, даже если оно полностью отличается от чего-то замеченного ранее.
Конечно, бесплатного сыра не бывает. Главный недостаток в скорости. Они могут быть намного медленнее нейронных сетей. Но я думаю, что их плюсы все же перевешивают этот недостаток.
Если хотите понять, как работает векторное пространство, то советую почитать 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 правильных результатов. А если использовать многопоточность?
Вот и все. Надеюсь, что мой опыт будет использован вами в хороших целях. Я знаю, что вы можете использовать этот код во вред, но чтобы сделать действительно нечто опасное вы должны довольно сильно его изменить.
Для тех, кто пытается защитить себя капчей я могу сказать, что это вам не сильно поможет, т. к. их можно обойти программно или просто платить другим людям, которые будут разгадывать их вручную. Подумайте над другими способами защиты.
Есть разные способы для обхода CAPTCHA, которыми защищены сайты. Во-первых, существуют специальные сервисы, которые используют дешевый ручной труд и буквально за $1 предлагают решить 1000 капч. В качестве альтернативы можно попробовать написать интеллектуальную систему, которая по определенным алгоритмам будет сама выполнять распознавание. Последнее теперь можно реализовать с помощью специальной утилиты.
Решить CAPTCHA
Распознавание CAPTCHA - задача чаще всего нетривиальная. На изображение необходимо накладывать массу различных фильтров, чтобы убрать искажения и помехи, которыми разработчики желают укрепить стойкость защиты. Зачастую приходится реализовывать обучаемую систему на основе нейронные сетей (это, к слову, не так сложно, как может показаться), чтобы добиться приемлемого результата по автоматизированному решению капч. Чтобы понять, о чем я говорю, лучше поднять архив и прочитать замечательные статьи «Взлом CAPTCHA: теория и практика. Разбираемся, как ломают капчи» и «Подсмотрим и распознаем. Взлом Captcha-фильтров» из #135 и #126 номеров соответственно. Сегодня же я хочу рассказать тебе о разработке TesserCap, которую автор называет универсальной решалкой CAPTCHA. Любопытная штука, как ни крути.Первый взгляд на TesserCap
Что сделал автор программы? Он посмотрел, как обычно подходят к проблеме автоматизированного решения CAPTCHA и попробовал обобщить этот опыт в одном инструменте. Автор заметил, что для удаления шумов с изображения, то есть решения самой сложной задачи при распознавании капч, чаще всего применяются одни и те же фильтры. Получается, что если реализовать удобный инструмент, позволяющий без сложных математических преобразований накладывать фильтры на изображения, и совместить его с OCR-системой для распознавания текста, то можно получить вполне работоспособную программу. Это, собственно, и сделал Гурсев Сингх Калра из компании McAfee. Зачем это было нужно? Автор утилиты решил таким образом проверить, насколько безопасны капчи крупных ресурсов. Для тестирования были выбраны те интернет-сайты, которые являются самыми посещаемыми по версии известного сервиса статистики . Кандидатами на участие в тестировании стали такие монстры, как Wikipedia, eBay, а также провайдер капч reCaptcha. Если рассматривать в общих чертах принцип функционирования программы, то он достаточно прост. Исходная капча поступает в систему предварительной обработки изображений, очищающей капчу от всяких шумов и искажений и по конвейеру передающей полученное изображение OCR-системе, которая старается распознать текст на нем. TesserCap имеет интерактивный графический интерфейс и обладает следующими свойствами:- Имеет универсальную систему предварительной обработки изображений, которую можно настроить для каждой отдельной капчи.
- Включает в себя систему распознавания Tesseract , которая извлекает текст из предварительно проанализированного и подготовленного CAPTCHA-изображения.
- Поддерживает использование различных кодировок в системе распознавания.
Предварительная обработка изображений и извлечениетекста из капчи
About
Мы не могли не сказать хотя бы пары слов об авторе замечательной утилиты TesserCap. Его зовут Гурсев Сингх Калра. Он работает главным консультантом в подразделении профессиональных услуг Foundstone, которое входит в состав компании McAfee. Гурсев выступал на таких конференциях, как ToorCon, NullCon и ClubHack. Является автором инструментов TesserCap и SSLSmart. Помимо этого, разработал несколько инструментов для внутренних нужд компании. Любимые языки программирования - Ruby, Ruby on Rails и C#. Подразделение профессиональных услуг Foundstone®, в котором он трудится, предлагает организациям экспертные услуги и обучение, обеспечивает постоянную и действенную защиту их активов от самых серьезных угроз. Команда подразделения профессиональных услуг состоит из признанных экспертов в области безопасности и разработчиков, имеющих богатый опыт сотрудничества с международными корпорациями и государственнымиИнтерфейс. Вкладка Main
После запуска программы перед нами предстает окно с тремя вкладками: Main, Options, Image Preprocessing. Основная вкладка содержит элементы управления, которые используются для запуска и остановки теста CAPTCHA-изображения, формирования статистики теста (сколько отгадано, а сколько нет), навигации и выбора изображения для предварительной обработки. В поле для ввода URL-адреса (элемент управления № 1) должен быть указан точный URL-адрес, который веб-приложение использует для извлечения капч. URL-адрес можно получить следующим образом: кликнуть в правой части CAPTCHA-изображения, скопировать или просмотреть код страницы и извлечь URL-адрес из атрибута src тега изображения ..сайт/common/rateit/captcha.asp?. Рядом со строкой адреса находится элемент, задающий количество капч, которые нужно загрузить для тестирования. Так как приложение может одновременно показывать только 12 изображений, в нем предусмотрены элементы управления для постраничного пролистывания загруженных капч. Таким образом, при масштабном тестировании мы сможем пролистывать загруженные капчи и просматривать результаты их распознавания. Кнопки Start и Stop запускают и останавливают тестирование соответственно. После тестирования нужно оценить результаты распознавания изображений, отметив каждый из них как корректный или некорректный. Ну и последняя, наиболее значимая функция служит для передачи любого изображения в систему предварительной обработки, в которой задается фильтр, удаляющий с изображения шумы и искажения. Чтобы передать картинку в систему предварительной обработки, надо щелкнуть на требуемом изображении правой кнопкой мыши и в контекстном меню выбрать пункт Send To Image Preprocessor.Интерфейс. Вкладка Options
Вкладка опций содержит различные элементы управления для конфигурирования TesserCap. Здесь можно выбрать OCR-систему, задать параметры веб-прокси, включить переадресацию и предварительную обработку изображений, добавить пользовательские HTTP-заголовки, а также указать диапазон символов для системы распознавания: цифры, буквы в нижнем регистре, буквы в верхнем регистре, специальные символы. Теперь о каждой опции поподробней. Прежде всего, можно выбрать OCR-систему. По умолчанию доступна только одна - Tesseract-ORC, так что заморачиваться с выбором тут не придется. Еще одна очень интересная возможность программы - выбор диапазона символов. Возьмем, например, капчу с сайт - видно, что она не содержит ни одной буквы, а состоит только из цифр. Так зачем нам лишние символы, которые только увеличат вероятность некорректного распознавания?. Но что если выбрать Upper Case? Сможет ли программа распознать капчу, состоящую из заглавных букв любого языка? Нет, не сможет. Программа берет список символов, используемых для распознавания, из конфигурационных файлов, находящихся в \Program Files\Foundstone Free Tools\TesserCap 1.0\tessdata\configs. Поясню на примере: если мы выбрали опции Numerics и Lower Case, то программа обратится к файлу lowernumeric, начинающемуся с параметра tesseditchar whitelist. За ним следует список символов, которые будут использоваться для решения капчи. По умолчанию в файлах содержатся только буквы латинского алфавита, так что для распознавания кириллицы надо заменить или дополнить список символов. Теперь немного о том, для чего нужно поле Http Request Headers. Например, на некоторых веб-сайтах нужно залогиниться, для того чтобы увидеть капчу. Чтобы TesserCap смогла получить доступ к капче, программе необходимо передать в запросе HTTP такие заголовки, как Accept, Cookie и Referrer и т. д. Используя веб-прокси (Fiddler, Burp, Charles, WebScarab, Paros и т. д.), можно перехватить посылаемые заголовки запроса и ввести их в поле ввода Http Request Headers. Еще одна опция, которая наверняка пригодится, - это Follow Redirects. Дело в том, что TesserCap по умолчанию не следует переадресации. Если тестовый URL-адрес должен следовать переадресации для получения изображения, нужно выбрать эту опцию. Ну и осталась последняя опция, включающая/отключающая механизм предварительной обработки изображений, который мы рассмотрим далее. По умолчанию предварительная обработка изображений отключена. Пользователи сначала настраивают фильтры предварительной обработки изображений согласно тестируемым CAPTCHA-изображениям и затем активируют этот модуль. Все CAPTCHA-изображения, загружаемые после включения опции Enable Image Preprocessing, проходят предварительную обработку и уже затем передаются в OCR-систему Tesseract для извлечения текста.Интерфейс. Вкладка Image Preprocessing
Ну вот мы и добрались до самой интересной вкладки. Именно тут настраиваются фильтры для удаления с капч различных шумов и размытий, которые стараются максимально усложнить задачу системе распознавания. Процесс настройки универсального фильтра предельно прост и состоит из девяти этапов. На каждом этапе предварительной обработки изображения его изменения отображаются. Кроме того, на странице имеется компонент проверки, который позволяет оценить правильность распознавания капчи при наложенном фильтре. Рассмотрим подробно каждый этап. Этап 1. Инверсия цвета На данном этапе инвертируются цвета пикселей для CAPTCHA-изображений. Код, представленный ниже, демонстрирует, как это происходит: for(each pixel in CAPTCHA) { if (invertRed is true) new red = 255 – current red if (invertBlue is true) new blue = 255 – current blue if (invertGreen is true) new green = 255 – current green } Инверсия одного или нескольких цветов часто открывает новые возможности для проверки тестируемого CAPTCHA-изображения. Этап 2. Изменение цвета На данном шаге можно изменить цветовые компоненты для всех пикселей изображения. Каждое числовое поле может содержать 257 (от 1 до 255) возможных значений. Для RGB-компонентов каждого пикселя в зависимости от значения в поле выполняются следующие действия:- Если значение равно -1, соответствующий цветовой компонент не меняется.
- Если значение не равно -1, все найденные компоненты указанного цвета (красный, зеленый или синий) меняются в соответствии с введенным в поля значением. Значение 0 удаляет компонент, значение 255 устанавливает его максимальную интенсивность и т. д.
- Average -> (Red + Green + Blue)/3.
- Human -> (0.21 * Red + 0.71 * Green + 0.07 * Blue).
- Average of minimum and maximum color components -> (Minimum (Red + Green + Blue) + Maximum (Red + Green + Blue))/2.
- Minimum -> Minimum (Red + Green + Blue).
- Maximum -> Maximum (Red + Green + Blue).
Этап 4. Сглаживание и резкость
Чтобы усложнить извлечение текста из CAPTCHA-изображений, в них добавляют шум в форме однопиксельных или многопиксельных точек, посторонних линий и пространственных искажений. При сглаживании изображения возрастает случайный шум, для устранения которого потом используются фильтры Bucket или Cutoff. В числовом поле Passes следует указать, сколько раз нужно применить соответствующую маску изображения перед переходом на следующий этап. Давай рассмотрим компоненты фильтра для сглаживания и повышения резкости. Доступны два типа масок изображения:
- Фиксированные маски. По умолчанию TesserCap имеет шесть наиболее популярных масок изображения. Эти маски могут сглаживать изображение или повышать резкость (преобразование Лапласа). Изменения отображаются сразу же после выбора маски с помощью соответствующих кнопок.
- Пользовательские маски изображения. Пользователь также может настроить пользовательские маски обработки изображений, вводя значения в числовые поля и нажимая кнопку Save Mask. если сумма коэффициентов в этих окошках меньше нуля, выдается ошибка и маска не применяется. При выборе фиксированной маски кнопку Save Mask использовать не требуется.
- Оставить без изменения (Leave As Is).
- Заменить белым (White).
- Заменить черным (Black).
Распознаем капчи
Ну что ж, пожалуй, мы рассмотрели все опции этой утилиты, и теперь неплохо было бы протестировать какую-нибудь капчу на прочность..
Результат анализа капчи сайт с предварительнойобработкой изображений. Судя по результатам, фильтр
подобрать не удалось Итак, запускаем утилиту и идем на сайт журнала. Видим список свежих новостей, заходим в первую попавшуюся и пролистываем до места, где можно оставить свой комментарий. Ага, коммент так просто не добавить (еще бы, а то бы давно уже всё заспамили) - нужно вводить капчу. Ну что ж, проверим, можно ли это автоматизировать. Копируем URL картинки и вставляем его в адресную строку TesserCap. Указываем, что нужно загрузить 12 капч, и нажимаем Start. Программа послушно загрузила 12 картинок и попыталась их распознать. К сожалению, все капчи оказались либо не распознаны, о чем свидетельствует надпись -Failed- под ними, либо распознаны неправильно. В общем, неудивительно, так как посторонние шумы и искажения не были удалены. Этим мы сейчас и займемся. Жмем правой кнопкой мыши на одну из 12 загруженных картинок и отправляем ее в систему предварительной обработки (Send To Image Preprocessor). Внимательно рассмотрев все 12 капч, видим, что они содержат только цифры, поэтому идем на вкладку опций и указываем, что распознавать нужно только цифры (Character Set = Numerics). Теперь можно переходить на вкладку Image Preprocessing для настройки фильтров. Сразу скажу, что поигравшись с первыми тремя фильтрами («Инверсия цвета», «Изменение цвета», «Градация серого») я не увидел никакого положительного эффекта, поэтому оставил там всё по дефолту. Я выбрал маску Smooth Mask 2 и установил количество проходов равным одному. Фильтр Grayscale buckets я пропустил и перешел сразу к настройке отсечения. Выбрал значение 154 и указал, что те пиксели, которых меньше, нужно установить в 0, а те, которых больше, в 255. Чтобы избавиться от оставшихся точек, включил chopping и изменил ширину границы до 10. Последний фильтр включать не было смысла, поэтому я сразу нажал на Solve. На капче у меня было число 714945, но программа распознала его как 711435. Это, как видишь, совершенно неверно. В конечном итоге, как я ни бился, нормально распознать капчу у меня так и не получилось. Пришлось экспериментировать с pastebin.com, которые без проблем удалось распознать. Но если ты окажешься усидчивее и терпеливее и сумеешь получить корректное распознавание капч с сайт, то сразу заходи на вкладку опций и включай предварительную обработку изображений (Enable Image Preprocessing). Затем переходи на Main и, кликнув на Start, загружай свежую порцию капч, которые теперь будут предварительно обрабатываться твоим фильтром. После того, как программа отработает, отметь корректно/некорректно распознанные капчи (кнопки Mark as Correct/Mark as InCorrect). С этого момента можно посматривать сводную статистику по распознаванию с помощью Show Statistics. В общем-то, это своеобразный отчет о защищенности той или иной CAPTCHA. Если стоит вопрос о выборе того или другого решения, то с помощью TesserCap вполне можно провести свое собственное тестирование.
Результат проверки CAPTCHA на популярных сайтах
Веб-сайт и доля распознанных капч:- Wikipedia > 20–30 %
- Ebay > 20–30 %
- reddit.com > 20–30 %
- CNBC > 50 %
- foodnetwork.com > 80–90 %
- dailymail.co.uk > 30 %
- megaupload.com > 80 %
- pastebin.com > 70–80 %
- cavenue.com > 80 %
Заключение
CAPTCHA-изображения являются одним из самых эффективных механизмов по защите веб-приложений от автоматизированного заполнения форм. Однако слабые капчи смогут защитить от случайных роботов и не устоят перед целенаправленными попытками их решить. Как и криптографические алгоритмы, CAPTCHA-изображения, тщательно протестированные и обеспечивающие высокий уровень безопасности, являются самым лучшим способом защиты. На основе статистики, которую привел автор программы, я выбрал для своих проектов reCaptcha и буду рекомендовать ее всем своим друзьям - она оказалось самой стойкой из протестированных. В любом случае не стоит забывать, что в Сети есть немало сервисов, которые предлагают полуавтоматизированное решение CAPTCHA. Через специальный API ты передаешь сервису изображение, а тот через непродолжительное время возвращает решение. Решает капчу реальный человек (например, из Китая), получая за это свою копеечку. Тут уже никакой защиты нет. 🙂Решил немного осилить 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 символа (грязновато).
Под простую капчу вполне реально запилить разгадыватель. Нужны интересные места с простыми капчами для допиливания и обкатки.
Загрузка...
