На прошлой неделе был топик «Ломаем капчу» — каптча там была довольно простая, но в комментариях предложили сломать каптчу Яндекса. Мне эта идея показалась интересной, и я решил попробовать.

Постановка задачи

Итак, у нас есть вот такая каптча:



Основные особенности:

• 6 цифр;
• Изображение монохромное;
• Фон белый;
• Искажения, которые, однако, незначительно смещают цифры со своих позиций;
• Две шумовые линии очень похожие на синусоиды.

Эту каптчу Яндекс использует давно (больше года, насколько я помню), что означает никто за это время её не сломал, они бы заметили, наверное. Поскольку даже человек иногда не в состоянии распознать все цифры, ставить задачу стопроцентного распознавания было бы глупо, да и цель у меня — просто решить интересную задачу, а не написать спам-бота. Поэтому поставим задачу распознавания каптчи с некоторой вероятность, даже одного процента будет достаточно.

Задача: написать программу, распознающую каптчу Яндекса с вероятностью не менее одного процента.
 

Первичная обработка

Приступим. Для начала сделаем самую простую часть — приведем изображение к удобному для распознаванию виду. Код написан на PHP (скриптовые языки для таких экспериментов удобнее), внизу будет ссылка на архив с исходниками.

Для начала закрасим логотип Яндекса белым прямоугольником (его координаты не меняются):



Иногда этот прямоугольник «откусывает» часть последней цифры, но это не страшно.

Теперь обрежем изображение по краям до первых отличных от фона пикселей (рамка добавлена для наглядности):

Убираем линии

И вот первая серьезная проблема — как убрать эти линии? Первое что пришло в голову — не убирать их совсем :) Однако, позже выяснилось, что шум они создают значительный и заметно увеличивают разность между двумя экземплярами одной и той же цифры. Придется убирать.

Второе решение, которое пришло в голову, — векторизовать изображение и удалить две самые длинные линии. Беглый взгляд по доступным готовым решениям показал, что в результате векторизации эти линии будут разбиты на несколько кривых, что усложняет задачу (придется как-то отличать их от кривых, принадлежащих цифрам). Хотя векторизация, на мой взгяд, более правильный путь, я решил от нее отказаться.

В итоге решено было использовать генетические алгоритмы, тем более, опыт работы с ними у меня большой. Останавливаться на описании ГА я не буду — об этом можно прочитать в Википедии.

Суть работы ГА в нашем случае — подобрать такую линию (а точнее набор точек), которая лучше всего удовлетворяет нашей целевой функции. Целевая функция (fitness) для каждого предложенного ГА варианта решения считает его приспособленность в виде одного положительного числа. В нашем случае это количество точек решения, которые попадают на пиксели, отличные от цвета фона, плюс дополнительные очки за «связность линии» (иначе решение будет состоять из отдельные точек).

Начальная популяция генерируется из линий, типичных для этой каптчи. Оператор мутации — «вытягивание» линии в случайном месте. Оператор кроссовера стандартный. Выбор особей в новую популяции по принципу рулетки.

Однако, генетический алгоритм — прожорливая штука. Адекватные решения он находил за 2-3 минуты, что в нашем случае неприемлемо, а также почти в каждом случае возникала одна проблема — линия «перескакивала» с полосы на часть цифры. С точки зрения нашей целевой функции такое поведение выявить было невозможно (см. 1-ю и 4-ю цифры):



В начале статьи я упомянул, что линии похожи на синусоиды — этот предположение оказалось полезным. В качестве решения я взял не набор точек, а параметры синусоиды (растяжение по осям, угол наклона, начальная фаза, сдвиг по вертикали). Перебирать 5 параметров намного проще, чем почти 200. К тому же теперь нам не надо следить за формой кривой — она изначально такая, которая нам необходима. Оператор мутации теперь меняет случайный параметр синусоиды, а оператор кроссовера не используется. В итоге за 8-10 секунд алгоритм неплохо справляется с поставленной задачей:



Теперь остается только закрасить белыми линиями толщиной в 3 пикселя (небольшой мусор остался):



И обрезать края с порогом в несколько пикселей:

Divide and conquer

Разделяем изображение на 6 равных частей, обрезаем лишние края, масштабируем каждое до размеров 20х30 пикселей:



Качество немного пострадало, но мы все ещё можем легко сказать, какие там изображены цифры, значит и робот сможет :) Задача сводится к распознаванию каждой отдельной цифры.

Если удастся добиться распознавания отдельной цифры с вероятностью не менее 50%, общая вероятность правильного распознавания каптчи будет 0,5^6 ~ 0.015, т.е. 1,5%, что нам и требуется.

Сначала я попробовал сгенерировать усредненный шаблон для каждой цифры и затем по наименьшему отклонению от шаблона проводить распознавание. Затея успехом не увенчалась — искажения слишком сильные, а некоторые цифры (8 и 9, например) отличаются незначительно. Лучше всего для таких задач подходит искусственная нейронная сеть, её я и решил использовать.

Самому кодить нейросеть дело неблагодарное, да ещё и на PHP — пошел искать библиотеку. Первое, что выдал Гугл, — Fast Artificial Neural Network Library. Библиотека написана на C++, но имеет интерфейсы для большинства распространенных сред. Есть extension и для PHP (правда на последнюю версию он ставится не без напильника).

На вход нейросети подается массив из 600 элементов (изображение 20х30 пикселей), каждый элемент задает яркость соответствующего пикселя вещественным числом 0 до 1. На выходе — массив из 10 элементов от 0 до 1, каждый из которых задает близость входных данных к соответствующей цифре. Между входным и выходным слоями всего лишь один слой из 150 нейронов. Почему один? Так получилось в результате практических экспериментов, что такая конфигурация работает лучше всего на этой задаче.

Библиотека действительно очень быстрая — на 300 образцах (50 каптчей) за 5 минут она обучила нейросеть до 30% вероятности распознавания. Неплохо, но нам нужны как минимум 50%.

Постепенно добавляя новые образцы для обучения (пришлось поработать китайцем), заветные 50% были получены на 1800 образцах после 3 часов обучения. На тестовом наборе из 100 каптчей (не участвовавших в обучении) удалось успешно распознать 2, что соответствует нашим предположениям. Время распознавания одной каптчи — 8-10 секунд.
 

Заключение

Поставленная задача выполнена. На все ушло два вечера (+ ночью компьютер сеть обучал). Можно было «добивать» каптчу и дальше, добавляя новые и новые образцы для обучения, но у меня на это нет времени да и желания. Хотя, если кто-то захочет, за пару дней сможет довести дело до конца, а пока у ребят из Яндекса есть время на усложнение каптчи :)

Архив с исходниками выложу минут через 30.

UPD: исходники: yandex_captcha.tar.gz (1 Мб).

По просьбам в комментариях выкладываю без скриптов для обучения и вариант с 40% вероятностью распознавания (для каждой цифры). Думаю, Яндексу это не навредит.

UPD2: небольшое FAQ:

Q: 1,5% — это же мало!?
A: Дальнейшее увеличение точности зависит лишь от количества образцов для обучения и проблемы не представляет.

Q: Почему бы не попытаться «выправить» линии вместе с цифрами?
A: Искажения цифр и линий не зависят друг от друга.