Предисловие
В статье будет рассмотрен пример распознавания реальной каптчи, которая используется на сайте xakep.ru для защиты от спама в комментариях и создания ботов на почте. Я хочу показать, что зная минимум вычислительной математики можно решить эту частную задачу. Более того, не подразумевается знание концепций нейронных сетей. В статье приводятся ссылки на другие статьи с Хабра для сравнения, но при создании программы я не пользовался ими вовсе.
В изложении я постараюсь не вдаваться в тонкости алгоритма и рассматривать то, что следовало бы сделать для более общего случая. Интересующийся читатель может задать вопросы мне лично, посетить блог или обратиться к моей курсовой работе по этой теме. На момент написания курсовая еще не готова.
Задача
Главная задача - создание программы распознавания каптчи сайта xakep.ru с приемлемой вероятностью. Для решения несущественно количество используемых ресурсов и скорость работы программы. Преследуется только исследовательские цели.
Каптча представляет собой 4 цифры, расположенных примерно посередине(+-10px), наклонены в стороны( +-45 градусов ) и имеют разную высоту (+-5px). Для защиты используется 3 вида шума: это точки, пятна и отрезки. На рисунке слева показан пример.
<br/>
Проект решения
- Очистить шум
- Найти цифры
- Распознать цифры
Очистка шума будут сведены на минимум точки и пятна. Линии и цифры почти не пострадают от этих преобразований.
Задача нахождения цифр - это задача нарезки каптчи так, что бы выделить в ней 4 изображения по цифре каждом.
Распознавание цифр - это создание алгоритма приятия решения о том, образ какой цифры находится в изображении.
<br/>
Очистка шума
<br/>
Очистка шума нужна только для нахождения цифр, не для их распознания. Именно на этом стоит заострить внимание. Из-за неправильного принятия решения о предназначении очистки шума мне пришлось переписывать алгоритм нарезки. Удаление шума должно пройти таким образом, чтобы убрать точки и пятна (далее я не буду их различать и называть просто шум), что бы с одной стороны, убрать "лишнюю" информацию, а с другой - сохранить существующую. Под сохранением и потерей информацией я подразумеваю сохранение и потерю тех пикселей, которые будут ключевыми для принятия решения о положении каждой цифры. В связи с этим, возникает два типа очистки шума: по избытку и недостатку. Первый - это очистка таким образом, что бы сохранилось максимум пикселей цифр, второй - минимум шума. Слева показаны примеры. Первое - избыток. Второе - недостаток.
Какой из способов лучше предстоит выяснить когда будет этап нахождения цифр. Сейчас важнее каким образом убирается шум. Для теории понадобиться: Введение в создание графических фильтров. Замечу, что сам OpenGL я не использовал, ссылку привожу только для теории. Через матрицы преобразований я вывел эмпирическим путем самый оптимальный алгоритм. Если в двух словах, я создал фильтры, похожие на размытие и увеличение резкости. Для реализации мне потребовались разработки Кристиана Грауса и его фильтр Mean Removal.
Нахождение цифр
Этап нахождения цифр очень тесно связан с этапом очистки шума. На этом этапе предстоит выяснить положение четырех цифр так, чтобы не запутаться в оставшемся шуме и отрезках. Качество результатов зависит от того, что остается после удаления шума. Линии я решил оставить, хоть и у меня есть такой фильтр, который пытается их стереть.
В этой статье решали схожую задачу нахождения цифр. Я стал считать не только по вертикали, но и по диагонали и ввел 7 степени наклона, где
-3 - наклон максимально влево.
0 - наклона нет.
3 - наклон максимально вправо.
Посему будет не один график, как в статье по ссылке, а 7.
Примеры диагональных площадей
Иллюстрацию надо смотреть как букву U. Диаграммы сгенерированы при разборе каптчи 6924. Невооруженным глазом видно, что пробегаясь от "Очень сильно влево" (верхняя левая стрелка) до "Очень сильно вправо" (верхняя правая стрелка), появляються хорошие минимумы и максимумы. Дисперсия есть тот показатель, говорящий где самые лучшие минимумы и максимумы. Этот коэффициент и будет ключевым для принятия решения о том, как наклонены цифры. Спасибо дисперсии, так как работает алгоритм успешно и принимает правильное решение о наклоне с вероятностью 90%.
После того, как выбран угол, необходимо определить способ разрезки цифр. Вопрос: "Как объяснить алгоритму, какие минимумы ему брать?". Здесь я пробовал делить диаграмму на 4 части и смотреть, какие минимумы лучше подходят к тому месту, где предполагается, что они будут. Эти все рассуждения меня завели в тупик.
Функцию надо сгладить. Сгладить так, что бы увеличить максимумы и уменьшить минимумы. Для этого я придумал свой способ аппроксимации. На рисунках слева я показал сначала оригинальный массив данных, потом сглаженный, потом мой алгоритм сглаживания. В последнем показаны все зависимости на одном графике. Если в двух словах, то аппроксимация проходит таким образом: берется прямоугольник, потом считается кол-во черных пикселей, которые попадают в него, далее этот прямоугольник двигается по горизонтали и создает таким образом еще одну серию значений. Для аналогии можно привести уже упоминавшуюся статью, только в моем случае это не столбик, а прямоугольник. Мой алгоритм аппроксимации вместо прямоугольника использует что-то вроде треугольника, т.е. пиксели при складывании умножаются на расстояние до центра прямоугольника. Таким образом, получаются более глубокие минимумы. См. иллюстрации:
Теперь на графике видны четкие максимумы и минимумы. Осталось их собрать. Для их нахождения я просто ищу перегибы функции, сортирую их, потом выбираю 4 максимума и 3 минимума. К сожалению, при выборе минимумов и максимумов возникают ошибки. Иногда выбираются максимумы, но не понятно как находить минимумы, потому что все минимумы равны нулю. Вернемся к вопросу очистки шума по избытку и недостатку. Для сравнения я показал 2 примера. Иллюстрации справа говорят сами за себя.
На втором примере видно, что алгоритм совсем не нашел минимумов. Это не страшно. Главная цель - это сохранение ключевой информации, а не успех на конкретном шаге. Честно говоря, дело обстоит куда хуже. Иногда бывает так, что 2 максимума находятся на расстоянии 2-х пикселей друг от друга. Или, наоборот, максимумы сливаются в один, между ними пропадает минимум и идет каким-нибудь 2-м минимумом между 2-мя максимумами. Обработкой таких ситуаций я назвал нормализацией. Нормализация создана для принятия решения о том, когда появляется какой-нибудь минимум или максимум, где не ожидается его увидеть, либо его нет вовсе на этом месте. Кроме того, я еще создал супернормализацию, необходимую для повторений итераций нормализации до тех пор, пока наконец не будет получена последовательность: Макс, Мин, Макс, Мин, Макс, Мин, Макс. Супернормализация на то и супер, потому что может вернуться к шагу сглаживания с делать свою аппроксимацию, смешивая прямоугольную и треугольную. После этого добавляется еще два минимума по краям. По ходу работы, нормализация старается свести расстояние между минимумами на одно среднее значение. Нахождение максимумов необходимо именно для нормализации, так как они являются той ключевой информацией для установки минимумов. Если рассматривать по избытку, то появляются неплохие минимумы и более-менее четкие максимумы. Однако, если брать каптчу по недостатку, появляются очень хорошие максимумы, а нормализации можно доверить расстановку минимумов. К сожалению, если на капче будут нули, то есть вероятность того, что ноль порежется как две единицы. Я выбрал недостаток.
На примерах видно, что я еще отделяю цифры по горизонтали. Для этого просто ищу площади по горизонтали, делаю прямоугольную аппроксимацию, выбираю максимум и в зависимости от его высоты определяю положение верхней и нижней точки цифр.
Так как я обладаю информацией об угле наклона цифр, то будет логично не только нарезать цифры, но и сразу выпрямить их. Тогда решается сразу две проблемы: упрощается чтение (просто своевременный сдвиг указателя вперед\назад ), а на выходе будет более четкие образы, без наклона, которые можно будет проще распознать! Далее я показал как порезалась каптча 6924 и выпрямилась и другие.
Вот они, заветные картинки, крупицы золота, которые станут отправной точкой для самой ответственной части алгоритма!
Распознание образов
Введение
Рассмотрим задачу распознавания. Задача состоит в создании алгоритма, который сможет с приемлемой вероятностью правильно распознавать цифры, которые подаются ему на вход. Цифры, хоть и алгоритм нарезки выпрямляет их, могут приходить под небольшим углом и смещены по горизонтали и вертикали. Более того, сохраняется вообще весь шум, который был изначально в каптче.
Решение о том, что надо оставить шум, было принято только после того, как я написал первую версию алгоритма. Сейчас я могу только сказать о том, что при удалении шума происходит потеря информации, необходимая для принятия решения. Единственный фильтр, который я применяю - это фильтр размытия. Фильтр размытия я считаю единственным естественным фильтром, так как даже образы у человека хранятся в размытом виде. Посему, всю базу образов, которую знает мой компьютер, я решил размыть, сопоставить с входными данными и принять решение о том, что изображено на рассматриваемой вырезке из каптчи.
Образы
Я отсортировал 2262 файла в 10 разных папках. Каждая папка - каждая цифра. Кого-то больше, кого-то меньше. Кстати 4-ки меньше всего(194), а 5-больше всего (270 штук). Это связано с тем, что пятерке нравится путаться с шестеркой. Вот пример образов 5-ки.(кликабельно)
<br/>
Сопоставление
Как я говорил, я не стал убирать шум. Еще я говорил то, что буду использовать только один фильтр - размытие. Давайте возьмем случайную вырезку X и произвольный образ Y. После этого мы применим фильтр размытие и наложим друг на друга две плоскости. Накладывать будем так, что бы X оказалась ровно посередине. Обратите внимание, что в образах пятерки есть образы, которые еще имеют отступы в 10 пикселей. Они нужны для тех случаев, когда размеры X больше размеров Y.
Когда я создавал этот участок программы, я очень сильно ошибся, когда стал считать то, насколько образы похожи друг на друга. Это очень большая глупость! Я создал зависимость через кубическую параболу и это мне мало что дало. Если искать не то, насколько похожи образы, а насколько они различны, то достаточно просто посчитать модуль разницы. Итак, возьмем образ X и образ Y:
На иллюстрации я попробовал показать, как работает алгоритм. Представьте себе два листочка, наложенные друг на друга. Первый листочек - это X, а другой - Y. Потом мы берем произвольный пиксель (зеленый квадрат и красной рамкой) из X (цифра, которую мы распознаем) и сопоставляем его с пикселем на том же месте из Y (образ, который есть в базе). Пусть x - это цвет обрабатываемого пикселя из X, а y - цвет обрабатываемого пикселя из Y. Возьмем модуль из разности: |x-y| - это и будет степень различия пикселей. Осталось пройтись по всем остальным и сложить модули различия. В конечном счете, получиться одно число, например, 4231, назовем из поинты. Мы ищем разности, подчеркну. А перед тем как искать разность, я попросил компьютер применить фильтр размытия для каждого образа, который есть в базе. Это будет первый шаг для борьбы с шумом. Осталось еще 2261 образов, с которыми нужно сравнить цифру. На нижней части рисунка я постарался иллюстрировать, как это можно вообразить.
<br/>
Принятие решения
Как только вырезка из каптчи будет сопоставлена с каждым образом из данных, в распоряжении программы окажется набор данных. В этом наборе каждому образу будет сопоставлено число, показывающее то, насколько этот образ отличается от цифры, которую программа распознает. На этом этапе можно выбрать такой образ, который меньше всего различается с тем, который мы сравниваем и на этом остановиться, но это будет не честно по отношению к остальным результатам.
Если не вдаваться в подробности, я вывел одну последовательность отбора из полученных данных образа, чтобы учитывались и то сколько каждый образ набрал поинтов и какой из них набрал поинтов наименьше. Берется 100 образов с наименьшим разлчием, сортираются по тому какой цифре они принадлежат. После этого устравивается конкурентция между 10-ю цифрами, где половини решения - это наименьший образ, остальное - конкуренция. Получается так, что если обучить компьютер новым образом, то это, конечно станет для него новым знанием, но это не станет единственным при принятии решения о выборе. Например, если программа однажды ошибется и примет неправильное решение, а после этого взять ту цифру, на которой она ошиблась, положить ее в папку с нужными образами, то программа может снова ошибиться. Я сделал это для того, чтобы программу не нужно было обучать каким-то частностям, а описать как примерно должна выглядить, скажем, пятерка. Благодаря такому подходу сокращается размеры базы образов.
Демонстрационное видео
Видео лучше смотреть в HD качестве.
Вероятность разбора: 30%
Все исходные коды я выложу позже на моем блоге. Коды на C# я выложу либо после того, как хакеры сменят каптчу либо после того, как пойму что они меня просто проигнорировали. В своем твиттере я сообщу о том, когда напишу курсовую формальным языком все то, что здесь описал в свободном стиле.
