В этой статье я попробую пройти весь путь в распознавании text-based CAPTCHA, от эвристик до полностью автоматических систем распознавания. Попробую проанализировать, жива ли еще капча(речь про текстовую), или пора ей на покой.
Впервые текстовая капча(text-based CAPTCHA), дальше я ее буду называть просто капча, использовалась в поисковике AltaVista, это был 1997 год, она предотвращала автоматическое добавление URL в поисковую систему. В те годы это была надежная защита от ботов, но прогресс не стоял на месте, и эту защиту начали обходить, используя доступные на то время OCR(например, FineReader).
Капча начала усложняться, в неё добавляли небольшой шум, искажения, чтобы распространенные OCR не могли распознать текст. Тогда начали появляться написанные под конкретные капчи OCR, что требовало дополнительных затрат и знаний у атакующей стороны. И от разработчиков капчей требовалось понимание, в чем сейчас трудности у атакующего, и какие искажения нужно внести, чтобы было сложно автоматизировать распознавание капчи. Часто из-за непонимания, как работает OCR, вносились искажения, которые больше создавали проблем человеку, чем машине. OCR для разных типов капч писались с использованием эвристик, и одним из сложных этапов была сегментация капчи на отдельные символы, которые потом можно было легко распознать с помощью тех же CNN(например LeNet-5), да и SVM покажут неплохой результат даже на сырых пикселях.
В качестве объекта распознавания возьму капчу Яндекса с сайта Yandex.com. На русскоязычной версии сайта капчи немного сложнее из-за того, что используются как русские, так и английские слова.
На первый взгляд, достаточно правильно бинаризировать картинку(перевести в черно-белый вариант) и дело в шляпе, можно получить большой процентов правильных распознаваний, так как сегментация на отдельные буквы выглядит довольно простой.
Для снижения эффективности эвристических алгоритмов Яндекс сделал упор на сложность бинаризации: есть капчи, для которых в каждой области изображения будет свой порог бинаризации, и надо подбирать его адаптивно. В среднем капча содержит 14 символов. Даже если мы сделаем классификатор с точностью 99%, и все капчи будем правильно сегментировать, то это нам даст точность в 87% распознавания всей капчи из двух слов. Здесь еще стоит упомянуть, что на сложность модели влияет количество классов(букв, цифр, знаков), используемых во всем наборе капч - чем их больше, тем сложнее достичь высоких процентов распознавания отдельных символов на простых моделях, поэтому капча на яндекс.ру будет сложнее, т.к. в ней используются русские и английские слова.
Из слабых мест этой капчи можно отметить, что буквы легко сегментируются при правильной бинаризации, и можно использовать проверку по словарю.
Далее будет описан эвристический алгоритм распознавания, а также я оставлю здесь ссылку на обучающую и тренировочную выборки.
Подготовительный этап
Для начала скачаем капчи и разделим их на тренировочную выборку и тестовую. Скачивание изображений капчи происходило через ВПН(с сайта yandex.com). При попытке сделать аккаунт вручную через браузер система меня распознавала ботом(думаю, из-за ВПН). Поэтому, предполагаю, я получил капчи с повышенной сложностью - "Если на втором этапе мы по-прежнему считаем запрос подозрительным, но степень уверенности в этом не такая высокая, то показываем простейшую капчу. А вот если мы уверены, что перед нами робот, то можем сложность и приподнять. Простое, но эффективное решение. " https://habr.com/ru/company/yandex/blog/549996/ Тип браузера, похоже, на результат не влиял (Opera, Chrome, Edge).
Итого набралось 4847 капч в тренировочную выбрку, и 354 - в тестовую. На распознавание обеих выборок было потрачено несколько долларов на сервисе decaptcher.com.
Эвристический алгоритм распознавания
Алгоритм будет состоять из нескольких шагов, это бинаризация, очистка от шума, извлечение двух слов, при необходимости - нормализация наклона для каждого слова, потом сегментация и распознавание.
1. Бинаризируем картинку - перевод цветного изображения, или изображения в градациях серого в черно-белое изображения. Цель - получение фона(0) и объекта(1), и уменьшение шума после бинаризации. Алгоритмы бинаризации будут описаны ближе к концу. Далее для каждого этапа сформируем параметры, которые будем потом оптимизировать. С этого момента работаем только с бинарным изображением.
2. Бинарное изображение очищаем от шума. Извлекаем связанные области из изображения - это наши объекты. Далее по количеству пикселей, которые входят в объект, разделяем их на шум и полезный объект. Все, что входит в наш интервал от А до В (по числу пикселей), это полезные объекты, остальное отсеиваем. В этом случае, например, у буквы i точка может быть определена как шум, чтобы этого не происходило, введем еще третью величину, расстояние С, это расстояние шума малого размера(эту величину мы тоже будем подбирать) до полезного объекта. Параметры А,В и С найдем простым перебором на тренировочном наборе, где максимизируем количество правильно распознанных капч.
3. Извлекаем из изображения 2 слова. Пробел между словами находится примерно по центру изображения. Величину "примерно" будем искать в окне ширины X, это будет еще одним параметром для оптимизации. Далее получаем горизонтальную гистограмму яркости в этом окне, вводим еще одно значение - порог, который будет нам показывать в этом столбце пробел, или объект, наибольшее кол-во пробелов подряд будут нам говорить о том, что это место разделения двух слов. В этой процедуре нам нужно подобрать 2 параметра, оптимальная ширина окна в центре изображения, и порог, который нам показывает, объект это, или пробел.
4. Нормализация наклона текста(для тех капч, где она нужна). Чтобы получить точность распознавания отдельных букв выше, нужно в некоторых капчах нормализовать наклон. Для этого мы проводим морфологическую операцию закрытие, и у нас получается единый объект. Далее находим ориентацию этого объекта, это угол между осью Х и главной осью элипса, в который вписывается наш объект.
5. Сегментация. На этом этапе у нас есть изображения 2-х слов, теперь нужно разбить их на отдельные буквы, для дальнейшего распознавания. Так как в нашем случае буквы не соприкасаются вместе, то можем извлечь связные области из изображения, это и будут наши символы, пригодные для дальнейшего распознавания.
6. Распознавание символов. Для распознавания я использовал сверточную сеть Lenet-5, только в моем случае классов было 26, в оригинале - 10. Для предобучения сети я сделал выборку в 52 тыс. изображений букв(по 2 тыс. на класс), отобрал несколько шрифтов, добавил различные искажения и обучил сверточную сеть. Подбирая параметры к алгоритму бинаризации и сегментации, мы получаем выборку для обучения классификатора. Эта выборка будет использована на втором и последующих шагах обучения классификатора, первый шаг обучения проходил с искуственно сгенерированными символами. Процесс итерационный, итого я смог насобирать 47 тыс. изображений букв с капч. Классы распределялись неравномерно, но это ожидаемо, так как в капче используют слова, а не случайные наборы букв. Итоговый классификатор имел точность 98.48%.
Теперь, в зависимости от метода бинаризации, я представлю результаты распознаваний. Сначала я использовал один порог бинаризации для всех капч, порог подобрал на тренировочной выборке, и получил 15% правильно распознанных капч на тренировочной и 15% на тестовой.
Использование алгоритма Оцу дало 13.6% на тренировочной и 12.25% на тестовой.
Метод бинаризации Sauvola, после подбора параметров он дал 26.01% на тренировочной и 25.8% на тестовой.
Подметив, что капчи можно разделить по фону на группы, сделаем кластеризацию. Признаки извлечем с помощью метода Zoning. Суть метода такова - изображение делится на непересекающиеся области заданного размера, после чего извлекаем из каждой области среднее значение яркости. Чем меньше у нас размер окна, тем точнее описывается изображение. Для разделения на кластеры используем алгоритм кластеризации k-means. Классические методы определения оптимального количества кластеров показывали 2 кластера. Эмпирически я выбрал количество кластеров равное 5. Разбивка по кластерам получилась такая: в первом - 842 шт, во втором - 1300 шт, в третьем -1237 шт, в четвертом - 770 шт, в - пятом 698 шт изображений. Для каждого кластера подбираем свои параметры бинаризации алгоритма Sauvola на тренировочном наборе. В итоге получаем точность в 31.22%, на тестовом - 30.8%.
Примеры кластеров:
Теперь у нас есть капчи, которые мы правильно бинаризировали, можно попробовать что-нибудь потяжелее, например U-Net для бинаризации, сеть с 13.5+ млн. параметров. Получили на тренировочных данных 39,2% правильных ответов, на тесте - 38.7%.
Для каждого нового типа капч, нам приходилось бы придумывать какие то новые схемы бинаризации, сегментации, что делает задачу трудоемкой в зависимости от капчи, но не невозможной. И затраты на разработку такой системы был порогом, который не каждый мог преодолеть для автоматического распознавания капчи и использования сервиса ботами.
А что на счет полностью автоматизированного процесса создания модели для распознавания, где не надо ничего придумывать, никакой эвристики? На вход - капчи с ответами, на выходе - готовая модель. Относительно недавно на сайте библиотеки Keras появились исходники, которые, при небольшой модификации, можно использовать для распознавания любых текстовых капч https://keras.io/examples/vision/captcha_ocr/
На Яндекс капче у меня получились такие цифры: на тренировочных данных сеть показала точность 55%, на тестовых - 39%. Из-за слишком маленькой тренировочной выборки для такой большой сети происходило быстро переобучение, но при правильно подобранных параметрах регуляризации сеть могла обучаться. Если увеличить тренировочную выборку, добавив туда отраженные картинки, то получим на тренировочных 58% точности, а на тесте - 43%. Увеличение тренировочной выборки новыми капчами даст еще прирост правильных ответов.
Сеть чаще всего ошибается на капчах такого вида:
Это коррелирует с тезисом авторов Яндекс капчи, в своей статье они писали -"Наиболее сложные датасеты с распознаванием слов на сегодняшний день представляют собой сильно искривлённые тексты (irregular text recognition)." Но в данном случае это скорее ограничение архитектуры используемой сети. Полученные фичи после слоев CNN мы распознаем lstm слоем последовательно слева направо, и в некоторых срезах возможного символа у нас находится сразу несколько символов. Это легко показать, сделав набор вот таких "капч"(рис. 1 ) в 10 тыс тренеровочных и 1 тыс тестовых. Обучив сетку, получим правильных ответов всего 20%, и 80% ошибок.
Но если сделать капчи, написав текст в одну строчку и добавив в текст искажения, усложняя ее (рис. 2), то получим 97% правильных ответов и 3% ошибочных.
Для увеличения процента успешных распознаваний яндекс капч можно использовать детектор текста, после чего нормализовать наклон и далее распознать нейронной сетью. Примеры сложных яндекс капч и детектора текста(рис. 3)
Если использовать детектор текста, то мы получим на тренировочных 60% точности, а на тесте — 51%. Я использовал уже предобученный на синтетике детектор текса - CRAFT: Character-Region Awareness For Text detection, а распознаванием отдельных слов занималась уже обученная модель на самой Яндекс капче.
Разработчики из Яндекса при проектировании капчи решали сразу две проблемы - уменьшение потенциальной эффективности ОЦР при "дружелюбности" для человека. Но чаще встречается такой подход к созданию текстовых капч - если человеку трудно ее распознать, то сложно и машине(рис. 4)
Но это не так, нейронные сети без труда "ломают" такие капчи и могут показать уровень расознавания выше человеческого. При этом не нужно придумывать какие-то эвристические алгоритмы, достаточно скачать готовую сетку и обучить, 99% текстовых капч она решит.
Если подвести итог, то проектирование текстовой капчи в текущих реалиях требует понимания методов и подходов, которыми будет пользоваться злоумышленник для ее распознавания и исходя из этого проектировать капчу, которая эффективно сможет противостоять роботам, и при этом будет простой для восприятия человеком.
Прошу вас поделиться своими мыслями в комментариях, как может выглядеть текстовая капча, которая будет сложной для распознавания машиной.