demonoid
14.10.2007, 00:48
Распознавания элементарных CAPTCHA часть I
I.Что такое CAPTCHA
II.Элементарная CAPTCHA ( beeline.ua )
Анализ
Элементарные преобразования
III.GD модуль ( Perl )
Установка, описание
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 )
Анализ
'Введите код, указанный на рисунке слева'.Слева указан рисунок с оранжевым фоном и фиксированным размером 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 области в которых находятся цифры
Элементарные преобразования
Рассмотрим всё цифры от 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 раз меньше чем было.
I.Что такое CAPTCHA
II.Элементарная CAPTCHA ( beeline.ua )
Анализ
Элементарные преобразования
III.GD модуль ( Perl )
Установка, описание
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 )
Анализ
'Введите код, указанный на рисунке слева'.Слева указан рисунок с оранжевым фоном и фиксированным размером 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 области в которых находятся цифры
Элементарные преобразования
Рассмотрим всё цифры от 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 раз меньше чем было.