Форум АНТИЧАТ
Страница 1 из 2 1 2 >
Показывать 40 сообщений этой темы на одной странице

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)
-   Авторские статьи (https://forum.antichat.xyz/forumdisplay.php?f=31)
-   -   Распознавания элементарных Captcha часть I (https://forum.antichat.xyz/showthread.php?t=51141)

demonoid 14.10.2007 00:48
Распознавания элементарных Captcha часть I
 
Распознавания элементарных CAPTCHA часть I

I.Что такое CAPTCHA

II.Элементарная CAPTCHA ( beeline.ua )
  1. Анализ
  2. Элементарные преобразования

III.GD модуль ( Perl )
  1. Установка, описание

IV.Реализация ( Perl )

I.Что такое CAPTCHA

Очень кратко:
CAPTCHA (от англ. «Completely Automated Public Turing test to tell Computers and Humans Apart» — полностью автоматизированный публичный тест Тьюринга для различения компьютеров и людей) — торговая марка Университет Карнеги — Меллона, компьютерный тест, используемый для того чтобы определить, человек ли использует систему.
Термин появился в 2000 году. Основная идея теста: предложить пользователю такую задачу, которую легко решает человек, но которую невозможно (или крайне трудно) научить решать компьютер. В основном это задачи на узнавание образов.
wiki(c) http://ru.wikipedia.org/wiki/CAPTCHA

II.Элементарная CAPTCHA ( beeline.ua )
  1. Анализ

'Введите код, указанный на рисунке слева'.Слева указан рисунок с оранжевым фоном и фиксированным размером 50x20.
Это значит что высота картинки 20 пикселей, а ширина 50 пикселей.

Пиксель (англ. pixel, сокр. от англ. PICture'S ELement, элемент изображения)— мельчайшая единица цифрового изображения в растровой графике. Он представляет собой неделимый объект прямоугольной (обычно квадратной) формы, обладающий определённым цветом. Любое растровое компьютерное изображение состоит из пикселей, расположенных по строкам и столбцам. Если изображение увеличить, вы увидите ряды пикселей.
wiki(c)http://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D0%BA%D1%81%D0%B5%D0%BB

Код:
     
        '------>  Red  ■
        |         
1 pixel +------>  Green ■
        |         
        .------>  Blue  ■
               
 Три основных цвета, комбинация которых даёт цвет одного пикселя
Рассмотрим, как будет выглядеть попиксельно 3-ка:
Код:
    0                    x 
    +-------------------►
    |                   
    |  0 1 2 3 4 5 6 7  ^
    | 0 ■ ■ ■ ■ ■ ■ ■ ■  | 
    | 1 ■ ■ ■ ■ ■ ■ ■ ■  | 
    | 2 ■ ■ ■ ■ ■ ■ ■ ■  |
    | 3 ■ ■ ■ ■ ■ ■ ■ ■  |
    | 4 ■ ■ ■ ■ ■ ■ ■ ■ 10 pxl   
    | 5 ■ ■ ■ ■ ■ ■ ■ ■  |
    | 6 ■ ■ ■ ■ ■ ■ ■ ■  | 
    | 7 ■ ■ ■ ■ ■ ■ ■ ■  |   
    | 8 ■ ■ ■ ■ ■ ■ ■ ■  |
    | 9 ■ ■ ■ ■ ■ ■ ■ ■  v
    |               
 y  ▼ <---- 8 pxl --- >
оси x и у больше рисовать не буду, они были указаны для дальнейшей ориентации.
3-ка имеет формат 10 пикселей x 8 пикселей .
Все остальные цифры имеют точно такой же формат (10х8)

Схематически картинка целиком будет выглядеть так:

Код:
              8 pxl          1 pxl
              <--->          <->
              |  |          | |
      ^--  .---------------------------. 
      |    |  .---. .---. .---. .---.  | -- ^
20 pxl |    |  | A | | B | | C | | D |  |    | 10 pxl
      |    |  |  | |  | |  | |  |  |    |
      |    |  '---' '---' '---' '---'  | -- v
      v--  '---------------------------'
       
            |        50 xpl            |
            <---------------------------> 
 
  где A,B,C,D области в которых находятся цифры
  1. Элементарные преобразования
Рассмотрим всё цифры от 0-9

Код:
  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
 0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■
 1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■
 2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■
 3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■
 4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■
 5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■
 6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■
 7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■
 8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ м ■
 9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■


  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
 0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■
 1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■ 
 2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■
 3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■
 4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■
 5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■
 6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■
 7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■
 8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■
 9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■
Посчитаем суммарное количество активных пикселей:
*под активными пикселями подразумевается пиксели, попадающие в объем цифры.

Код:
q0 = 36
q1 = 27
q2 = 32
q3 = 31
q4 = 35
q5 = 37
q6 = 39
q7 = 26
q8 = 40
q9 = 39
Суммарное количество активных пикселей:
  9
  ∑ qi = 742
  i=0
Пример: на изображении число 1000 ,посчитаем, сколько итераций нам понадобиться для распознавания этого изображения.
*Под итерацией будем понимать один шаг цикла.

Код:
q1 + q0 + q0 +q0 = 27 + 36 + 36 + 36 = 135
Для распознавание числа 1000 на изображение понадобиться 135 итераций
Важно:
В данном случае нету никаких помех, позиции цифр неизменны. Поэтому можно выделить характерные активные пиксели для каждой цифры.
*под характерными активными пикселями подразумевается наличие 1-го или двух пикселей в объеме цифры .
В итого анализа стало известно, что каждую цифру можно описать 1-м или 2-мя пикселями:

Код:
  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
 0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■
 1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■
 2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■
 3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■
 4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■
 5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■
 6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■
 7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■
 8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■
 9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■


  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
 0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■  0 ■ ■ ■ ■ ■ ■ ■ ■
 1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■  1 ■ ■ ■ ■ ■ ■ ■ ■ 
 2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■  2 ■ ■ ■ ■ ■ ■ ■ ■
 3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■  3 ■ ■ ■ ■ ■ ■ ■ ■
 4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■  4 ■ ■ ■ ■ ■ ■ ■ ■
 5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■  5 ■ ■ ■ ■ ■ ■ ■ ■
 6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■  6 ■ ■ ■ ■ ■ ■ ■ ■
 7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■  7 ■ ■ ■ ■ ■ ■ ■ ■
 8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■  8 ■ ■ ■ ■ ■ ■ ■ ■
 9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■  9 ■ ■ ■ ■ ■ ■ ■ ■
Снова посчитаем суммарное количество характерных активных пикселей:

Код:

q0 = q1 = q4 = q5 = q6 = q8 = q9 = 2
q2 = q7 = 1

Суммарное количество активных пикселей:
  9
  ∑ qi = 16
  i=0
    ~ 46 раз меньше чем было.
Снова берём картинку с числом 1000 и считаем итерации:
Код:
q1 + q0 + q0 +q0 = 2 + 2 + 2 + 2 = 8

    ~ 16 раз меньше чем было.

demonoid 14.10.2007 00:49
III.GD модуль ( Perl )
  1. Установка, описание

GD — Библиотека для работы с графикой.
для ознакомления можно почитать _http://ru.wikipedia.org/wiki/GD и _http://search.cpan.org/dist/GD/GD.pm

Установка
Для Active Perl :

Код:
C:\>ppm help
NAME
    ppm - Perl Package Manager, version 4.01

SYNOPSIS
    Invoke the graphical user interface:

        ppm
        ppm gui

    Install, upgrade and remove packages:

        ppm install [--area <area>] [--force] <pkg>
    ......................

C:\>ppm gui
В графическом менеджере инсталлируем нужный пакет

или же
 
C:\>ppm install GD
можно и так
Код:
C:\>cpan

cpan shell -- CPAN exploration and modules installation (v1.9102)
ReadLine support enabled

cpan> install GD
Способов много , у кого ошибки или не получается советую почитать _

http://forum.vingrad.ru/faq/topic-158272.html


IV.Реализация ( Perl )
Проверяем установлен ли GD модуль
Код:
С:\>perl -e "use GD"
Ежели :
Код:
Can't locate GD.pm in @INC ....
Модуль GD неустановлен ставте

Код:
#!/usr/bin/perl -w
use GD;

use strict;
use warnings;

#Константы (RED,GREEN,BLUE) характеризуют активные пиксели
use constant RED    => 44;
use constant GREEN  => 18;
use constant BLUE  => 4;
 
my $image = shift || exit  print "\x09        bix_exemple.pl ~ / Beeline Image xek / \n".
                                "\x09\x09\x09\x09      / by demonoid / \n".
                                "\x09  specical for forum.antichat.ru / 13.10.2007 / \n\n".
                                                                "\x09\x09 usage    : $0 <image> \n".
                                                                "\x09\x09 example  : $0 5.jpg  \n";

my ( $x,$y,$index,$xek_image,$r,$g,$b,$x_position,$y_position,$i,$count ) = ( undef,undef,undef,undef,undef,undef,undef,5,5,0,0 );

my $myImage = newFromJpeg GD::Image( $image  );

my %Coordinates = ( '0' => [ '7:4', '0:4' ],
                    '1' => [ '2:2', '3:2' ], 
                    '2' => [ '7:9' ], 
                    '3' => [ '0:1', '0:8' ], 
                    '4' => [ '5:2', '6:9' ], 
                    '5' => [ '0:0', '0:1' ], 
                    '6' => [ '3:4', '0:4' ],
                    '7' => [ '7:0' ],
                    '8' => [ '2:4', '3:4' ],
                    '9' => [ '7:4', '7:7' ]) ;       
for(0..3)
{
    for(  $i = 0;$i<9;$i++ )
    {
        for( my $k=0;$k<2;$k++ )
        {
            if ( exists  $Coordinates{ $i }[ $k ] )
            {
                ( $x,$y ) = split( /\:/,$Coordinates{ $i }[ $k ] );
                $index = $myImage->getPixel( $x+$x_position,$y+$y_position );
                ( $r,$g,$b ) = $myImage->rgb( $index );
                ( ( RED>=$r )&&( GREEN>=$g )&&( $b=BLUE ) )?$count++:1;
            }
        }
        if ( ( $count ==2 )||( $count ==1 )&&( $i==2 )||( $count ==1 )&&( $i==7 ) )
        {
            $count = 0;
            last;
        }
        $count = 0;
    }
    $xek_image.=$i;
    $x_position+=9;
}
print "IMAGE: $xek_image \n";
Тестируем _http://beesms.beeline.ua/
Лентяям качаем пачку картинок _http://www.rapidshare.ru/429980 или _http://fileshare.in.ua/454150 или _http://upload.com.ua/get/899997654

Еcли можно перенесите в раздел 'Наши Статьи'

Digimortal 14.10.2007 03:24
отличная статья.. классно оформлена и, что самое главное, интересная тема - сам все хотел поработать в данном направлении (распознование образов), но все руки пока не доходили.. ) буду ждать в продолжении описание более интересных и продвинутых техник распознования каптчи..

p.s. На ActivePerl установить GD можно отсюда:
ppm install http://theoryx5.uwinnipeg.ca/ppms/GD.ppd (для версии perl 5.8)
ppm install http://theoryx5.uwinnipeg.ca/ppmpackages/GD.ppd (для 5.6)

p.p.s. форум кромсанул сорец в районе объявления переменной $y_position - поправьте.. )

ZaCo 14.10.2007 09:23
классное оформление, а вот сама статья об обычном эталонном сравнение с естественной оптимизацией. буду ждать продолжения.

Talisman 14.10.2007 09:42
оформление порадовало, а алгоритм самый элементарный =/

KSURi 14.10.2007 12:19
Я дела с распознаванием образов не имел еще, было весьма интересно

demonoid 14.10.2007 16:03
Цитата:
Сообщение от inv
Это напоминает былые времена тем настройка пинча и си

Автор а почему ты выбрал? перл)
почему например не си++

написал бы по нейронные сети...
Выбрал перл т. к недостаточно знаний в си++.
нейронные сети ммм, я подумаю об этом :)

blackybr 14.10.2007 21:19
Автор молодец. понравилось то как идет рспознавание, подход индивидуальный )

-Hormold- 24.10.2007 14:03
А возможно такое на php?

ЛифчиС5СВ 25.10.2007 15:29
РЕСПЕКТ! ;) Для регистрации в каталогах людям, занимающимся оптимизацией и раскруткой сайтов, весьма полезно ;)


Время: 22:54
Страница 1 из 2 1 2 >
Показывать 40 сообщений этой темы на одной странице