.
Место для Вашей рекламы
7 Август 2007

Распознаём капчу PHPBB2

posted in Программирование |

Пропалю алгоритм распознавания капчи PHPBB2 🙂

Хотя конечно тут «палева» особого нет — всем и так всё видно и если поднапречься думаю каждый, при наличии базовых навыков PHP или какого нибудь другого языка программирования, сможет придумать и реализовать подобный алгоритм.

Ладно, приступим !

На входе имеем стандартную phpbb2 капчу (графический PNG файл , пусть будет такая:

captcha

На выходе хотелось бы получить строчку из 6ти символов KXLDXL 🙂

Вступление

Пойдем от простого к сложному — как сравнить две однопиксельные картинки ? Допустим чёрная — единичка, белая — нуль. Правильно: оцифровываем и вычитаем, т.е. преобразовали картинку в циферку $in — если (1-$in)==0 имеем чёрную картинку т.е. единичку. В реализуемом алгоритме именно так и будем делать, только сравнивать будем массивы с эталонными массивами и выбирать тот где расхождение минимально.

Что потребуется

Для сего действа нам понадобится эталонный набор символов для используемых в кодировании- это циферки от 1 до 9 (нуля нет — чтоб не путать с буквой О) и буковки от A до Z одинаковой размерности (как его получить — чуть позже …). Предположим он у нас есть — 35 png файлов, для каждой буквы свой файлик. Например буква G

g.png

Так же понадобится установленная библиотека 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

Эталонные символы из моего скрипта (к нужному виду доведёте сами) — набора два, исторически так сложилось …

С помехами

Без помех

У нас 30 комментариев на запись “Распознаём капчу PHPBB2”

Почему бы Вам не высказать своем мнение! Позвольте нам узнать, что Вы думаете...

  1. 1 On 13.09.2007, admin said:

    косячёк в алгоритме — если центр масс слева то добавлять нужно было слева, а я справа — впринципе на итог не влияет, если и там и сям придерживаться одного алгоритма выравнимания.

  2. 2 On 13.09.2007, snoopckuu said:

    я имел ввиду по высоте, а не по краям.

  3. 3 On 13.09.2007, GTAlex said:

    принцип один — что по высоте, что по ширине

  4. 4 On 14.09.2007, admin said:

    Хорошая заметка по капчам http://zhilinsky.ru/2007/09/13/captcha/

  5. 5 On 27.09.2007, Soocaicorgo said:

    Продвижение, оптимизация сайтов.
    Реклама по: форумам, доскам объявлений, сайтам знакомств.

    Контакты:
    ICQ: 393-513
    e-mail: bary_m@mail.ru

  6. 6 On 01.10.2007, Blubollursono said:

    Всем привет !!

    Вероятно я не в тему тут, но больно уж интересует вопрос, где можно заработать в интернет ?

    Пробовала много различных способов, таких как клики, Nocs, регистрации, да к сожалению заработала всего несколько долларов.

    Вот и хотелось узнать, может кто поможет девушке — бросит пару ссылок на хорошие компании. Только лишь, пожалуйста, никаких MLM и волшебных кошельков.

  7. 7 On 01.10.2007, GTAlex said:

    привет!

    >клики, Nocs, регистрации
    где и как пробовала если не секрет ?

    и куда собственно бросить пару ссылок ?

    p.s. хоть и баян, но всё таки надо статейку для новичков оформить а ля «Заработок в интернете», а пока статья не написана рекомендую ознакомиться со следующим материалом от Даниила «Способы заработка в Рунете»

  8. 8 On 10.10.2007, softyes said:

    Куплю Windows Куплю Office -2003/XP/Vista softyes@mail.ru
    и другой ЛИЦЕНЗИОННЫЙ софт
    предложения на е-мейл softyes@mail.ru

  9. 9 On 11.10.2007, Autosite said:

    Зачетная статья, пиши еще 🙂

  10. 10 On 26.10.2007, mari4ek said:

    ну частенько все возможно, но важно целесообразна ли такая затея? некоторые капчи *очень* трудно распознать!

  11. 11 On 08.11.2007, Алексей said:

    блин хочу распознать капчу блогспота…. как бы, а?

  12. 12 On 01.12.2007, BrancyBah said:

    ЗАХОДИТЕ! ТУТ ВСЕ ОПИСАНО. http://doxodgold.ru вчера 56 баксов заработал. Лучше сохраните эту ссылку. просто админ может
    удалить. всетаки спам))

  13. 13 On 20.02.2008, GTAlex said:

    Похоже где то вылезла страничка по собирательным запросам типа phpbb — лезет конкретный спам, поэтому комментарии в данной ветке вынужден отключить.

  14. 14 On 20.02.2008, GTAlex said:

    Все — «Всегда Последнего» починил — закрываю комменты !

  15. 15 On 20.02.2008, Always last said:

    Самое обсуждаемое на блогах:
    Косовo
    Фидель ушёл в отставку
    Умер Егoр Летов

Яндекс.Метрика