jishi Nov 13 2012 at 13:06

Разбор картинки в текст: простой алгоритм

2 min

35K

Programming*Algorithms*

From sandbox

+18

Comments 30

xsash Nov 13 2012 at 13:48

Надеюсь за капчу «2812» для автора уже готов свой маленький ад

+37

jishi Nov 13 2012 at 13:50

Автор сломал четыре глаза, чтобы её разглядеть. Это самая читаемая из капч той серии, остальные просто ломают мозг.

xsash Nov 13 2012 at 14:04

К сожалению, у разработчиков в погоне за «кто придумает защиту от ботов», получается все чаще «кто придумает защиту от людей»

StopDesign Nov 13 2012 at 16:06

А до сих пор существует такая текстовая капча, которую средний пользователь распознает с вероятностью хотя бы лучше 90%, а робот не распознает (хуже 5%)? Мне кажется, разработчикам пора признать, что распознать текстовую капчу чуть ли не проще, чем написать приличный парсер сайта.

samodum Nov 13 2012 at 14:43

Перенаправляем её на антикапчу pixodrom pixodrom.com и глаза ломают уже китайцы :)

ohifck Nov 13 2012 at 14:17

2812 дискриминирует дальтоников.

Dima_Sharihin Nov 13 2012 at 14:19

10 минут пытался разобрать, где же цифры.
Это та самая капча, которая парсится машиной легче, чем компьютером.

Но моя любимая эта:, проскакивала 31 июля 2011 в комментариях к статье на Хабре

+10

bethrezen Nov 13 2012 at 14:31

Машиной легче, чем компьютером говорите?

Dima_Sharihin Nov 13 2012 at 14:35

ну, по крайней мере, здесь моноширинный текст, точки находятся строго в ячейках, фон одного цвета, а цифры другого.
Тем более, в капче может быть только [0-9]{4,4}, следовательно, парсер не будет слишком большим.

Это если формат картинки не сменится

jishi Nov 13 2012 at 14:48

На тот момент алгоритм парсера подразумевал перевод изображения в greyscale и проверку границы. Данная капча только от этого парсера и защищена, если её перевести в серый, то все кружки будут одного цвета. Взламывали её тоже элегантно — проверкой контрольных точек.

colonel Nov 13 2012 at 16:54

Ну а чем, все-же компьютер от машины отличается?
Чем он тупее ее ;)

Dima_Sharihin Nov 13 2012 at 22:14

Понимаю сарказм, но во время учебы и вообще под машиной подразумеваю «электронную вычислительную»

colonel Nov 14 2012 at 05:21

А, да.
От ЭВМ компьютер отличается, точно. Как я сразу не понял!

zoommy Nov 13 2012 at 14:53

Спасибо, что прочитали — у меня не получилось.

someoneisusingmyusualnick Nov 13 2012 at 14:58

Алгоритм без кода — это как пиво без водки… Ну вы поняли.

jishi Nov 13 2012 at 15:06

Кода полно, но в правилах Песочницы:

«С большой вероятностью не пройдут премодерацию:
…
— куски программного кода;»

-1

StopDesign Nov 13 2012 at 16:07

Это если только куски, без статьи.

akalend Nov 13 2012 at 15:24

пиво тоже вкусно…
а самому влом алгоритм написать?

спасибо за идею, сам когда-то занимался разбором капчи,
использовал немного другой, более трудоемкий подход… потом надоело

jishi Nov 13 2012 at 15:32

Спасибо на добром слове!

1Tiger1 Nov 13 2012 at 15:03

Не знаю, может я излишне щепетилен, но ломать собственную капчу, как то неправильно это. Все равно что взламывать сайт который сам писал, имея все исходники, зная уязвимости. Вам заплатили за защиту, вы ее сделали, деньги получили, а потом сами же сломали. При этом клиент продолжает думать что он защищен, и мучать пользователей уже бесполезной вещью. Ну должна же быть какая-то профессиональная этика.

Что-то я не могу понять почему разбор собственной капчи, с известным алгоритмом, и довольно простой (судя по виду) занял много времени, зачем все эти сложности, вырезали мусор (алгоритм формирования знаете), если там конечно есть хоть какая-то случайность в мусоре, разбили на цифры, сравнили с эталонами. Если количество цифр фиксированное, можно даже не бить на цифры, сравнивать эти 10000 комбинаций через тот же md5 например. Сравнить 10К строк — копейки по времени, md5 только 1 раз посчитать надо. Думаю есть и более эффективные способы, я капчами сильно не занимался.

Ну и таким алгоритмом можно сломать только капчи без особого рандома в символах, если в капче случайные искажения шрифта, или как у рекапчи вообще шрифт неизвестен (скан книг), т.е. рандом абсолютный, алгоритм не работает. Ну и память конечно, не знаю как дела у перла с этим, но такие матрицы могут сожрать очень много.

Ну а последняя конечно вставляет, действительно комьютеру справится с ней проще чем человеку. В чем смысл?

jishi Nov 13 2012 at 15:13

Ломалось как black box, иначе неспортивно. Неэтично использовать бэкдоры и неэтично быть гадом, а из спортивного азарта пройти несколько итераций совершенствования навыка забавно.

На самом деле, смысл не в ломании капчи, а в OCR. Принципиально, я уже несколько раз думал этот алгоритм положить в основу какой-нибудь онлайн OCR-системы, почему бы и нет?

jishi Nov 13 2012 at 21:51

Кстати, спасибо за совет про md5, даже не подумал.

debug22 Nov 13 2012 at 15:14

очень доставляет тег PHP. при чем это здесь? ну да. вы реализовали алгоритм на пхп. но ни листинга кода. ни нюансов языка, ни каких-либо ништячков. думаете сам факт выбора языка и фраза про сравнение строк за n^3 с помощью встроенной функции php — это повод?

jishi Nov 13 2012 at 15:23

Если честно — язык мог быть любым, вот совсем-совсем. Изначально алгоритм был на Perl, но для удобства был переписан на PHP. Никаких «фишечек», никаких особенностей — код очень простой, и любой девелопер сможет этот алгоритм повторить хоть на бейсике.

someoneisusingmyusualnick Nov 13 2012 at 19:27

Так вы и не ответили — а причем тут тогда хаб пхп? Писали бы в хаб с алгоритмами.
Мой заминусованный комментарий о том же.
Пост в хабе где предполагается в большинстве своем готовое решние, код. А у вас чистая теория — алгоритм. Переместите что ли.

jishi Nov 13 2012 at 21:17

Спасибо за подсказку, переместил. К сожалению, код правда никакого интереса не представляет.
Вот для интереса пример аппроксимации. Говорят, её ещё можно как-то рассчитывать методом среднеквадратичного отклонения, но я так не умею.

function unify($pix_arr, $width, $height)
{
GLOBAL $maincolors, $approx_lvl;

reset($pix_arr);
$new_arr=array();

$nw=0;
for ($w=1; $w<=$width; $w+=$approx_lvl)
	{
	$nh=0;
	
	for ($h=1; $h<=$height; $h+=$approx_lvl)
		{
		$pix1=$pix_arr[$h][$w];
		$pix2=$pix_arr[$h][$w+1];
		$pix3=$pix_arr[$h+1][$w];
		$pix4=$pix_arr[$h+1][$w+1];
		
		if (!$maincolors[$pix1] || !$maincolors[$pix2] || !$maincolors[$pix3] || !$maincolors[$pix4]) 
			{
			$new_arr[$nh][$nw]=1;
			}
		else $new_arr[$nh][$nw]=0;
		$nh++;
		}
	$nw++;
	}
	
return $new_arr;	
}