Распознаём капчу PHPBB2
posted in Программирование |Пропалю алгоритм распознавания капчи PHPBB2 🙂
Хотя конечно тут «палева» особого нет — всем и так всё видно и если поднапречься думаю каждый, при наличии базовых навыков PHP или какого нибудь другого языка программирования, сможет придумать и реализовать подобный алгоритм.
Ладно, приступим !
На входе имеем стандартную phpbb2 капчу (графический PNG файл , пусть будет такая:
На выходе хотелось бы получить строчку из 6ти символов KXLDXL 🙂
Вступление
Пойдем от простого к сложному — как сравнить две однопиксельные картинки ? Допустим чёрная — единичка, белая — нуль. Правильно: оцифровываем и вычитаем, т.е. преобразовали картинку в циферку $in — если (1-$in)==0 имеем чёрную картинку т.е. единичку. В реализуемом алгоритме именно так и будем делать, только сравнивать будем массивы с эталонными массивами и выбирать тот где расхождение минимально.
Что потребуется
Для сего действа нам понадобится эталонный набор символов для используемых в кодировании- это циферки от 1 до 9 (нуля нет — чтоб не путать с буквой О) и буковки от A до Z одинаковой размерности (как его получить — чуть позже …). Предположим он у нас есть — 35 png файлов, для каждой буквы свой файлик. Например буква G
Так же понадобится установленная библиотека GD2 (считаем что реализовывать будем на PHP), хотя думаю данная библиотечка (или аналогичная для работы с изображениями) имеется и для других языков. Библиотека нужна только для того чтоб преобразовывать изображения в матричное представление. Т.е. изображение NхM (N высота M ширина) преобразовывается в матрицу (двумерный массив) NхM (N строк M столбцов) каждый элемент которой — пиксель в изображении.
Как вы уже догадались все дальнейшие преобразования будут вестись уже с матрицами, поэтому неплохо было бы обзавестись классом для работы с матрицами (я такого не нашел, поэтому пришлось написать свой). Какие именно функции понадобятся поймете на шаге программирования алгоритма :).
0. Загружаем эталонные символы
Будем считать что эталонные символы у нас уже есть (как и где их получить — чуть позже). Загружаем в поле объекта класса его конструктором на лету преобразовывая изображение в матрицу (двумерный массив). Загружаем именно так чтоб данный набор всегда был в памяти и каждый раз не повторять эту операцию.
1. Получаем символы для сравнения с эталонными
Получаем запросом капчу, преобразуем в матрицу, убираем шум в два этапа —
Переводим в черно белый: выбирается среднее значение (экспериментально подбираем константу)- если обрабатываемое больше среднегоо ставим 1, если меньше 0)
Сглаживаем (одиночные и двоичные нули делаем единичками, единички делаем нулями
Вычленяем символы для распознавания из всего изображения (в цикле сначала разбиваем по вертикали, потом по горизонтали) по условию — если 2 и более подряд идущих столбца(строки) в сумме дают больше чем (константа — допустим 3 или 4) — считаем что пошла буква — запихиваем её в массив, в итоге получаем массив из 6ти символов. (говоря символ на самом деле имеем матрицу т.е. массив чисел).
Далее доводим размерность полученных символов до эталонной, для этого нам нужно знать с какой стороны добавить пустой столбец(строку). Это делается путём определения центра масс изображения и в зависимости куда он попадает добавлять именно в ту сторону. Поясню — допустим эталонная размерность 40х40 (из за какой нибудь толстой буквы W или G или M), а на входе имеем букву L — наш алгоритм вычленил её из начальной капчи у неё размерность (25х37). Как её довести до 40×40? вот именно с использованием центра масс и доводим. /Вот на этом этапе можно сохранять получившиеся символы и выбирать из них эталонные — муторно конечно, т.е. нужно наформировать 35 разных … но с другой стороны универсальнее и проще чем разбираться в каком формате храняться символы в конкретном движке, других минусов я не вижу — быстродействие думаю от такого представления не уменьшится/
Ну и наконец то:
2. Определяем символы
Сравниваем обрабатываемые символы с эталонными и выбираем те, где разница минимальна.
Для ускорения обработки можно задать максимальный минимум 🙂 т.е. значение ниже которого — уже с большой вероятностью имеем эталон. (допустим обрабатываем цифру 2 — она в массиве эталонов идёт второй по счёту, в результате вычитания получили число 25 (а для всех других на тестах было больше 100), допустим экспеприментально выявили константу 60 (максимальное количество несовпадений). Т.е. получив значение 20 (меньше константы) дальше можно не сравнивать и признать распознаваемый символ эталонным на данном шаге.
Всё ! Ошибок в работе скрипта (неправильное определение) я на стадии тестирования не выявил ни одной.
p.s. Имхо такие вещи нужно на c++ реализовывать и подключать к php уже в виде готового модуля, но что то пока руки не дойдут до такой реализации. Ну и конечно интересно потестить скорость разных реализаций разных алгоритмов для определённых капч, типа померяться реализация чьего алгоритма самая быстрая ?! — хотя тут тоже субъективно: один и тот же алгоритм два разных программиста очень по разному в плане быстродействия могут реализовать… а я себя не считаю профессионалом в PHP 🙂
p.p.s
Эталонные символы из моего скрипта (к нужному виду доведёте сами) — набора два, исторически так сложилось …