Пользователь
0,0
рейтинг
3 декабря 2012 в 15:38

Разработка → Взлом старой каптчи сайта Хабрахабр из песочницы

Введение



В данной статье кратко рассказывается о процессе взлома captcha используемой ранее при входе на сайт Хабрахабр.
Целью работы является применение знаний на практике и проверка сложности каптчи.
При разработке алгоритма использован Matlab.


Обзор задачи



Старая каптча Хабрахабр выглядела так:





Основные трудности распознавания данной каптчи:
  1. Искаженные символы
  2. Шумы и размытость
  3. Размеры символов сильно отличаются
  4. Пересечение символов

Честно говоря, у меня не всегда получалось с первого раза правильно прочитать каптчу, поскольку часто символы А и 4, L и 4 были неразличимые.

Все же, несмотря на некоторые сложности, рассмотрим основные идеи по чтению данной каптчи.

Этап 1. Построение системы сегментации



Каждую систему распознавания символов можно представить следующим образом:


В нашем случае необходимо реализовать последние две подсистемы.

Детальный анализ исследуемой каптчи позволил выделить ее основные особенности:
  1. На каптче всегда присутствуют 6 символов
  2. Всегда используется схожий (скорее всего один и тот же) метод зашумления
  3. Случаи пересечения или наложения символов редкие

Исходя из этого, был построен следующий алгоритм сегментации:
  1. Убрать шумы
  2. Бинаризировать изображение
  3. Выделить 6 наибольших областей связности


Реализация сегментации в Matlab
function [ rects ] = segmentator( aImg, nRect, lightMode )
%find all symbols on habrahabr login captcha
%use:  rects = segmentator( aImg, nRect )
%where:
%       rects       - rects coordinates
%       aImg        - resized image data
%       nRect       - count of rect to find
%       lightMode   - find all rects without imOpen

%Много кода, из которого большая часть предназначена для случая когда символы склеены.
if nargin < 4
    fSRects = 0;
end
if nargin < 3
    lightMode = 0;
end
    
minX =  8;      if lightMode minX = 11; end     %px 
minY = 16;      if lightMode minY = 18; end     %px

%% Change color mode to 8-bit gray
if(size(size(aImg),2) > 2)
    aImg = imadjust(rgb2gray(aImg));
end

%Save aImg
aImgCopy = aImg;

%structuring element for imopen
se = strel('disk', 2);

%Remove some noise 
aImg(aImg > 0.92) = 1;
aImg = imopen(imadjust(aImg), se);

if lightMode
    aImg = aImgCopy;
end

imBW3 = adaptivethreshold(aImg,50,0.2,0);

if ~lightMode
    imBW3 = imopen(imBW3, se);
end

%% find rects
imBin = 1 - imBW3;
CC = bwconncomp(imBin);
numPixels = cellfun(@numel,CC.PixelIdxList);
[biggest, idx] = sort(numPixels, 'descend');
bb = regionprops(CC, 'BoundingBox');

if lightMode
    imshow(aImgCopy);
end

%Primitive filter
%copy only good rects
bbCounter = 1;
for i = 1 : length(bb)
    curRect = bb(i).BoundingBox;
    if (curRect(3) < minX || curRect(4) < minY)
        continue;
    end
    bbNew(bbCounter) = bb(i);
    bbCounter = bbCounter + 1;
end

if bbCounter == 1
    rects = {-1};
    return;
end

if DEBUG_MODE
    for i = 1:length(bbNew)
        rectangle('Position', bbNew(i).BoundingBox, 'EdgeColor', 'r');
    end
end

%analize count of rects
%1: if rectC == nrect -> all rects find
%2: else if rectC > nrect -> delete smallest
%3: else -> find subrects

if nRect == length(bbNew) || fSRects == 1
    rects = {bbNew(1:end).BoundingBox};
elseif nRect < length(bbNew)
    rects = deleteSmallest( bbNew, nRect )
else 
    for i = 1 : length(bbNew)
        curRect = bbNew(i).BoundingBox;
        rectArea(i) = curRect(3) .* curRect(4);
    end
    
    needRect = nRect - length(bbNew);
    
    aImg = aImgCopy;
    [biggest, idx] = sort(rectArea, 'descend');
                
    switch(needRect) %@todo: Redesign (check constant)
        case 1
            subRects{1} = findSubRects( aImg, bbNew( idx(1)).BoundingBox, 2 );
            subRectIdx = idx(1);
        case 2
            if( biggest(1) > 2 * biggest(2) )
                subRects{1} = findSubRects( aImg, bbNew(idx(1)).BoundingBox, 3 );
                subRectIdx = idx(1);
            else
                subRects{1} = findSubRects( aImg, bbNew(idx(1)).BoundingBox, 2 );
                subRects{2} = findSubRects( aImg, bbNew(idx(2)).BoundingBox, 2 );
                subRectIdx = idx(1:2);
            end
        case 3
            if( biggest(1)  > 3 * biggest(2) )
                subRects{1} = findSubRects( aImg, bbNew(idx(1)).BoundingBox, 4 );
                subRectIdx = idx(1);
            elseif( biggest(1) > 1.5 * biggest(2) )
                subRects{1} = findSubRects( aImg, bbNew(idx(1)).BoundingBox, 3 );
                subRects{2} = findSubRects( aImg, bbNew(idx(2)).BoundingBox, 2 );
                subRectIdx = idx(1:2);
            else
                subRects{1} = findSubRects( aImg, bbNew(idx(1)).BoundingBox, 2 );
                subRects{2} = findSubRects( aImg, bbNew(idx(2)).BoundingBox, 2 );
                subRects{3} = findSubRects( aImg, bbNew(idx(3)).BoundingBox, 2 );
                subRectIdx = idx(1:3);
            end
        otherwise
            display('Not supported now'); %@todo: add more mode
            rects = {-1};
            return;
    end
    
    %create return value
    rC = 1;
    for srC = 1:length(bbNew)
        if(sum(srC == subRectIdx))
            curIdx = find(subRectIdx == srC);
            for srC2 = 1 : length(subRects{curIdx})
                rects(rC) = subRects{curIdx}(srC2);
                rC = rC + 1; 
            end
        else
            rects{rC} = bbNew(srC).BoundingBox;
            rC = rC + 1;
        end
    end
end
end

function [ subRects ] = findSubRects( aImg, curRect, nSubRect )
    coord{1} = [0];                 pr(1) = 100;
    coord{2} = [0 40];              pr(2) = 60;
    coord{3} = [0 30 56];           pr(3) = 44;
    coord{4} = [0 23 46 70];        pr(4) = 30;

    MIN_AREA = 250;

    if DEBUG_MODE
        imshow(aImg);
    end

    wide = curRect(3);

    for i = 1 : nSubRect
        subRects{i}(1) = curRect(1) + coord{nSubRect}(i) * wide / 100;
        subRects{i}(2) = curRect(2);
        subRects{i}(3) = wide * pr(nSubRect) / 100;
        subRects{i}(4) = curRect(4);

        rect{i} = imcrop(aImg, subRects{i});

        tmpRect = rect{i};
        lvl = graythresh(tmpRect);
        tmpRect = imadjust(tmpRect);
        tmpRect(tmpRect > lvl + 0.3) = 1;imshow(tmpRect);
        tmpRect(tmpRect < lvl - 0.3) = 0;imshow(tmpRect);
        imbw3 = multiScaleBin(tmpRect,  0.22, 1.4, 30, 1);imshow(imbw3);
        imbin = 1 - imbw3;
        %imBin = binBlur(tmpRect, 13, 1); imshow(imBin); %other method of
        %adaptive binarization

        cc = bwconncomp(imbin);
        numpixels = cellfun(@numel,cc.PixelIdxList);
        [biggest, idx] = sort(numpixels, 'descend');
        bb = regionprops(cc, 'Boundingbox');
        imshow(rect{i});

        %find biggest rect
        clear rectArea;
        for j = 1 : length(bb)
            rectArea(j) = bb(j).BoundingBox(3) .* bb(j).BoundingBox(4);
        end

        [biggest, idx] = sort(rectArea, 'descend');

        newRect = bb(idx(1)).BoundingBox;


        rectangle('Position', newRect, 'EdgeColor', 'r');

        if newRect(3) * newRect(4) > MIN_AREA
            subRects{i}(1) = subRects{i}(1) + newRect(1) - 1;
            subRects{i}(2) = subRects{i}(2) + newRect(2) - 1;
            subRects{i}(3) = newRect(3);
            subRects{i}(4) = newRect(4);
        end
    end
end

function [ retValue ] = deleteSmallest( bbRects, nRects )
    %1: calc area
    for i = 1 : length(bbRects)
        curRect = bbRects(i).BoundingBox;
        rectArea(i) = curRect(3) .* curRect(4);
    end
    
    %2: sort area
    [~, idx] = sort(rectArea, 'descend');
    idx = idx(1:nRects);
    idx = sort(idx);
    
    %copy biggest
    retValue = {bbRects(idx).BoundingBox};
end

function [ imBIN ] = sauvola( X, k )
    h = fspecial('average');
    local_mean = imfilter(X, h, 'symmetric');
    local_std = sqrt(imfilter(X .^ 2, h, 'symmetric'));
    imBIN = X >= (local_mean + k * local_std);
end





Шумы убираем очень просто, для этого все пиксели изображения которые светлее некоторого уровня делаем белыми.
Пример обработки:
Оригинальное изображение
Изображение после обработки



Для бинаризации используем адаптивный алгоритм бинаризации, в котором для каждого пикселя (или областей пикселей) определяется свой порог бинаризации [ Адаптивная бинаризация].
Примеры бинаризации:
Хороший пример сегментации (3XJ6YR)
Пример склеенных и разорванных символов (4TAMMY)



Для поиска символов на изображении решено использовать метод поиска связных областей, что в Matlab можно сделать с помощью функций:
CC = bwconncomp(imBin);
bb = regionprops(CC, 'BoundingBox');

После чего провести анализ полученных областей, выделить из них самые большие, при необходимости разбить на подобласти (в случае склеенных символов). Случай, когда в символах появляются разрывы не предусмотрен.

Примеры конечного результата сегментации:







Качество сегментации удовлетворительное, переходим к следующему этапу.

Этап 2. Создание обучающей выборки


После сегментации мы получаем набор координат прямоугольников, которые предположительно содержат символы каптчи.
Поэтому, сначала распознаем вручную все капчти и переименуем их (в этот момент я чувствовал себя профессиональным распознавателем каптч, жаль что не платили 1 цент за каждую распознанную). После чего используем следующий скрипт, для формирования обучающей выборки:
Скрипт для создания обучающей выборки
%CreateTrainSet.m

clear; clc;

workDir = '.\captch';
fileList = dir([workDir '\*.png']);

N_SYMB = 6;

SYMB_W = 18; %px
SYMB_H = 28; %px

WIDTH = 166; %px
HIGH  =  75; %px

SAVE_DIR = [workDir '\Alphabet'];

%process data
for CC = 1 : length(fileList)
    imName = fileList(CC).name;
    
    recognizedRes = imName(1:N_SYMB);
    %open image
    [cdata, map] = imread( [workDir '\' imName] );
   
    %change color mode
    if ~isempty( map )
        cdata = ind2rgb( cdata, map );                  
    end
    %resize image
    cdata = imresize(cdata, [HIGH WIDTH], 'lanczos3'); 
    
    %find all symbols on image
    rects = segmentator(cdata, N_SYMB, 1);
    if rects{1} == -1
        continue;
    end
    
    %imcrop and save
    if length(rects) == N_SYMB
        if ~exist(SAVE_DIR)
            mkdir(SAVE_DIR);
        end
        for j = 1 : N_SYMB
            if ~exist([SAVE_DIR '\' recognizedRes(j)])
                mkdir([SAVE_DIR '\' recognizedRes(j)]);
            end
            
            imList = dir([SAVE_DIR '\' recognizedRes(j) '\*.jpg']);
          
            newname = num2str(length(imList) + 1);
            nameS = floor(log10(length(imList) + 1)) + 1;
            for z = nameS : 4
                newname = ['0' newname];
            end
            
            tim = imcrop(cdata, rects{j});
            
            if (  size( size(tim), 2 ) > 2  )
                tim = imadjust(rgb2gray(tim));
            end
            
            tim = imresize(tim, [SYMB_H SYMB_W], 'lanczos3');

            imwrite(tim, [SAVE_DIR '\' recognizedRes(j) '\' newname '.jpg']);
        end
    end
end



После создания выборки нужно ее почистить от неправильных символов, которые появляются в связи с неточной сегментацией.
Интересным фактом стало то, что в каптче используется всего 23 символа латиницы.
Обучающая выборка присутствует в материалах приложенных к статье.

Этап 3. Обучение нейронной сети


Для обучения нейронной сети использовано Neural Network Toolbox.
Функция обучение описана ниже:
Создание и обучение нейронной сети
function [net, alphabet, inpD, tarD] = train_NN(alphabet_dir, IM_W, IM_H, neuronC)
%inputs:
%   alphabet_dir - path to directory with alphabet
%   IM_W - image width
%   IM_H - image height
%   neuronC - count of neuron in hidden layer
%outputs:
%   net - trained net
%   alphabet - net alphabet
%   inpD - input data
%   tarD - target data
%
%   Vadym Drozd drozdvadym@gmail.com

    dirList = dir([alphabet_dir '\']);
    dir_name = {dirList([dirList(:).isdir]).name};

    alphabetSize = length(dir_name) - 2;

    try
        a =  load([alphabet_dir '\' 'trainData_' num2str(IM_W) 'x' num2str(IM_H) '_.dat'], '-mat');
    catch
    end

    try
        target = a.target;
        inpData = a.inpData;
        alphabet = a.alphabet;
    catch
        for i = 3 : length(dir_name)
            alphabet(i - 2) = dir_name{i};

            imgList = dir([alphabet_dir '\' alphabet(i - 2) '\*.jpg']);
            t_tar = zeros(alphabetSize, length(imgList));
            t_tar(i - 2,:) = 1;

            for j = 1 : length(imgList)
                im = imread([alphabet_dir '\' dir_name{i} '\' imgList(j).name]);
                im = imresize(im, [IM_H IM_W], 'lanczos3');  %resize image
                im = imadjust(im);
                im = double(im) /255.0;
                im = im(:);
                if i == 3 && j == 1
                    inpData = im;
                else
                    inpData = [inpData im];
                end
            end
            if i == 3
                target = t_tar;
            else
                target = [target t_tar ];
            end
        end
    end

    %create and train NN
    toc
    min_max = minmax(inpData);
    habrNN = newff(min_max, [IM_H * IM_W neuronC 23], {'logsig', 'tansig','logsig'}, 'trainrp');
    habrNN.trainParam.min_grad = 10E-12;
    habrNN = train(habrNN, inpData, target);

    display('Training time:');
    timeE = toc;
    display(timeE);

    net = habrNN;
    inpD = inpData;
    tarD= target;

    save([alphabet_dir '\' 'trainData_' num2str(IM_W) 'x' num2str(IM_H) '_.dat'], 'inpData', 'target', 'alphabet');
end



Избрана следующая архитектура нейронной сети:


Размер изображений поступающих на вход нейронной сети 10*12 пикселей. Как известно обучение нейронной сети дело непростое, поскольку неизвестно сразу какой должна быть архитектура сети, количество нейронов в каждом из слоев, а также не известно к какому из множества минимумов скатится обучение сети. Поэтому обучение проводилось несколько раз, после чего был выбран один из лучших результатов.

Этап 4. Тестирование алгоритма


Для тестирование алгоритма написан следующий скрипт:

Скрипт для распознавания каптчи
%% captchReader.m
clear; close all; clc;
cdir = './captch/';
fileList = dir([ cdir '\*.png']);
load('49_67_net.mat');
load('alphabet.mat');
N_SYMB = 6;

SYMB_W = 10;
SYMB_H = 12;

WIDTH = 166; %px
HIGH  =  75; %px

SHOW_RECT = 1; %1 - show rects, else - don't show

correct = 0; %correct recognized results
correctSymbC = 0;
allSymbC = 0;

for CC = 1 : length(fileList)
    imName = fileList(CC).name;
    %open image
    [cdata, map] = imread( [cdir '\' imName] );
    %change color mode
    if ~isempty( map )
        cdata = ind2rgb( cdata, map );
    end
    %resize image
    cdata = imresize(cdata, [HIGH WIDTH], 'lanczos3');
    display(CC);
    if (  size( size(cdata), 2 ) > 2  )
        cdata = imadjust(rgb2gray(cdata));
    end
    rects = segmentator(cdata, N_SYMB, 0);
    
    if SHOW_RECT
        imshow(cdata);
        for i = 1:length(rects)
            colors = {'r', 'y', 'b', 'g', 'c', 'm'};
            rectangle('Position', rects{i}, 'EdgeColor', colors{i});
        end
    end
    if rects{1} == -1
        continue;
    end
    
    %recognize
    recognized = zeros(1, N_SYMB);
    if length(rects) == N_SYMB
        for j = 1 : N_SYMB
            tim = imcrop(cdata, rects{j});
            %resize image
            tim = imadjust(imresize(tim, [SYMB_H SYMB_W], 'lanczos3'));
            res = net(tim(:));
            [sort_res, idx] = sort(res, 'descend');
            recognized(j) = alphabet(idx(1));
        end
    end
    correctSymbC = sum( (recognized - imName(1:6)) == 0); 
    allSymbC = allSymbC + N_SYMB;
    if strcmp(recognized, imName(1:6))
        correct = correct + 1;
    end
    if SHOW_RECT
        title(['Recognize: ' recognized]);
    end
    
end

fprintf('CAPTCH precision is: %2.2f %%', 100 * correct / length(fileList));
fprintf('Symbol precision: %2.2f %%', 100 * correctSymbC / allSymbC);



Примеры распознавания:








В результате получили следующие результаты:
Количество правильно распознанных каптч: 49.17 %
Количество правильно распознанных символов: 87.02 %

Выводы


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


Если статья понравилась, в следующей могу подробно рассказать о основных подходах к распознаванию человеческого лица.

Исходники с обучающей выборкой


Исходники. Дропбокс
Яндекс Народ
@drozdVadym
карма
42,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (118)

  • +127
    Так это из-за Вас теперь сраная рекапча, которую раза с 5 получается угадать? Ну спасибо.
    • +15
      Если бы. Я начал писать пост уже где-то пол года назад, никак не хватало времени дописать. А тут, недавно зашел на сайт и увидел что уже рекапча стоит, поэтому и решил, что если уж и публиковать так сейчас.
      • +28
        У меня в памяти сразу всплыла история с предпредыдущей капчей Хабра. Автор тоже изложил алгоритм распознавания, после чего незамедлительно получил бан и капча была изменена. Ваше счастье, drozdVadym!
        • 0
          Хм, может это случилось когда еще действовала и кто то мог воспользоваться такой возможностью, а тут автор написал пост после того как ее уже заменили?!
          П.с не слышал про эту историю.
          • +1
            Ссылка на лурк.
            • +3
              Спасибо.
              основной текст удален НЛО, дабы избавить Хабр от притоков мудаков, которые, вдохновившись топиком, будут класть сайт экспериментами

              Улыбнуло)
    • +31
      которую раза с 5 получается угадать?
      Если ее вообще возможно разгадать. Мне, например, сегодня хабр подсунул такую вот рекапчу:
      Скрытый текст
      • +2
        Не очень хорошо распознаются прописные r, n и m. Толи crnsterna толи cmstema. Первое слово не обязательно распознавать.
        • +3
          Не очень хорошо распознаются прописные r, n и m.

          То есть дроби «восемь целых пять шестых» и «пять целых три (то ли шестых, то ли восьмых)», повернутые на 90 градусов, в качестве первого слова, вас не смущают?)
          Первое слово не обязательно распознавать.
          Но ведь очень хочется!
          • +4
            Их можно не писать, точнее вместо этого можно написать любую последовательность символов.
            Это не распознанный текст из отсканированых книг.
            • –3
              Я там обычно кое-что неприличное пишу
              • +11
                Статьи в Википедии тоже вы портите?
            • +5
              Сейчас туда (в рекапчу) еще попадают номера домов, видимо с Google Streetview
            • 0
              Спасибо! Теперь всё стало понятно!
        • +4
          А разве там не 'crostema'? =)
          • +2
            Видимо, у вас более натренированная «нейронная сеть».
          • +4
            crustema там
        • +4
          Первое слово не обязательно распознавать?..
          Где Вы были раньше? :(
          • 0
            В reCaptcha подсовывают слова из отсканированных книг. Одно слово, которое уже распознано, а второе — которое еще не распознано. По распознанному слову отсекают ботов, а распознавая нераспознанное слово, пользователь помогает оцифровывать книги. Так что да — вместо слова, которое невозможно распознать, можно написать что угодно.
            • 0
              А я вначале подумал, что это шутка. Гениально придумано.
            • 0
              по моему одно слово это из книги а второе они генерируют сами, что б если первое не правильно было распознано не было ошибок.
      • 0
        Заметил, что если в слове на рекапче есть знак препинания, то это слово можно вообще не вводить.
        • +14
          Специально для Вас.
          image
          • 0
            Я это знаю, но спасибо что повторили и посмотрели комментарий, на который я ответил.
          • +2
            Ну, иногда они ТАКОЕ подсовывают (примерно в половине случаев) в обязательной части, что это уже не распознание книг, а неуважение к пользователю.
        • 0
          Одн из слов контрольное, второе — вы вводите что видите и помогаете распознавать книги
          • +3
            А где эти книги потом можно бесплатно получить?
            • 0
              Google Books…
              А так же www.gutenberg.org
      • +30
        Это еще что. Иногда, когда не можешь долго угадать, рекапча еще и издевается.
        Скрытая картинка


      • +1
        Inglip has been summoned. It has begun.
    • +1
      Капчу поменяли после того, как мне в ЛС продемонстрировали слабую устойчивость текущей капчи — там был несколько другой алгоритм работы, но тем не менее, работал. Так что теперь рекапча, а входить на сайт по-прежнему удобней и быстрей всего через привязку аккаунта к социальным сетям.
      • +1
        мне тут подсказывают, что на /settings/upgrade/ все еще старая капча
        • 0
          В некоторых местах (некритических, в том числе таких как /settings/upgrade/) оставили старую, так как она всё же полегче, а ломать её сложнее и особого смысла нет )
      • +3
        Лучше сделайте чтобы капчу не надо было вводить при первой попытке входа.

        К социальным сетям далеко не каждый захочет привязываться. Лично я не доверяю социалочкам.
        • +3
          К сожалению, именно из-за того, что капча показывалась только со второго раза, во время выборов на Хабре бывали случаи размещения всякой ненужной всячины.
          • 0
            Можно не показывать капчу первый раз, при условии входа с того же айпи/подсети, что и в прошлый раз.
    • +1
      Если гора не идет к магомеду,… напишите в росреестр, пусть забанят рекапчу.
      То-то радости будет когда пол-интернета залогиниться или запостить что-то не сможет. И в отличие от html-сайта, не сразу видно проблему.
      • 0
        Интересно, каким образом Росреестр, который регистрирует объекты недвижимости и сделки с ними, может повлиять на рекапчу? :)
    • 0
      Можно привязать к аккаунту социалку и через неё входить без всяких капч.
  • +3
    Люблю подобные статьи с точки зрения подходов к проблеме и её решению. Спасибо за старания :)
  • +22
    Этот алгоритм угадывает каптчи лучше чем я :(
    • +6
      Такие нынче пошли капчи, что люди справляются хуже роботов.
    • +4
      Почему то на ваш комментарий вспомнилось )

      P.S. хабр картинку съел почему то…
      twipic2.s3.amazonaws.com/15763418/3_4003.jpg
      • 0
        Потому что карма отрицательная.
  • +7
    Если статья понравилась, в следующей могу подробно рассказать о основных подходах к распознаванию человеческого лица.


    да! в карму плюсанул, за пост проголосовал, с тебя статья -)
  • +1
    А зачем вообще нужна капча на входе в хабр?
    • 0
      Может быть для того, чтобы было сложнее брутфорсить пароли? Тут все таки закрытая регистрация и увод аккаунта может быть даже выгоден с точки зрения финансов.
      • +2
        Именно из-за этого.
        • 0
          Есть предложение которое облегчит всем жизнь – надо сделать как в гугле, что капча появляется только после N неудачных попыток входа.
    • +1
      Чтобы нельзя было пройтись по всем пользователям на предмет паролей, угадывающихся с первой попытки.
    • +2
      Обычное перекладывание с больной головы на плечи пользователей.
      • 0
        Как раз наоборот. Забота о тех пользователях, которые о себе не позаботились.
        • +8
          Ага, забота о нескольких раздолбаях, за которую расплачиваются все пользователи.
  • 0
    Даешь взлом рекапчи, что бы на Хабр можно было зайти с 10-й попытки!

    А если серьезно, то сколько времени заняла эта работа?
    • +1
      Изначально набросал алгоритм и код в Matlab где-то за 3 часа, но точность была 25-30%, много времени заняло ручное распознавание каптчи (честно, не засекал сколько). Потом начал оптимизировать, даже начал переписывать на C c использованием OpenCV, но закинул, в связи с дипломом и поступлением в магистратуру. Неделю назад вспомнил, что-то исправил, привел код к лучшему виду (хотя и сейчас он мне не особо нравиться) и опубликовал. Если считать суммарное количество времени на реализацию — где-то 20 часов.
      • 0
        Позанудствую: использовать i и j в качестве счетчика цикла в Матлабе не рекомендуется, это зарезервированные символы мнимой единицы.
        • 0
          Изначально думал написать на С, в Matlab алгоритм набросал на скорую руку.
          Хотя да, спасибо за замечание, буду знать.
  • +8
    О, а я когда-то через OpenCV это делал. Серый шум, кажется, убирался вот так 1 строчкой на Python'е:

    cv.Threshold(image, image, 100, 255, cv.CV_THRESH_OTSU)

    Получалось примерно так:

    image

    (Точной картинки сейчас нет, но выглядела она как-то так)

    Потом по контурам легко находим символы и…

    image

    … и нейронная сеть рулит :-)

    image
    • 0
      Используя адаптивный алгоритм бинаризации (Например Саволы) шумы можно тоже перед обработкой не убирать, и результат будет тот же. Отсу пробовал, но получалось много разрывов.
  • +26
    Вот никогда не понимал, зачем на капчах делают шум, который мешает пользователю, а для ботов никакой сложности не представляет. Гораздо лучше, по-моему, использовать противоположные эффекты и способности мозга к распознаванию образов обыкновенных знакомых слов.
    Что-то вроде такого (свободная импровизация, без искажений букв):

    Глазами это прочесть не составит труда. Прост ли будет алгоритм её распознавания?
    • 0
      Капча с искажениями генерируется автоматически, когда вы придумаете как сгенерировать то что у вас в примере — вы автоматически решите и обратную задачу :) А простые подходы вроде «нарисовать все буквы 1 раз и переставлять местами» взламываются и без всяких нейросетей.
      • +2
        То, что в примере генерируется элементарно:

        1. Рисуем слово чёрным поверх серого фона, накладывая слегка искаженные буквы краями друг на друга.
        2. Рисуем то же самое белым, со смещением на 2 пикселя вверх и влево.
        3. Рисуем то же самое цветом фона, со смещением на 1 пиксель вверх и влево относительно п 1.
        4. Добавляем случайные кляксы цветом фона, чтобы усложнить задачу поиска контуров.

        Эту информацию можно как-то использовать для распознавания данного примера?
        • 0
          Вы при этом предлагаете не искажать буквы? Тогда перебором добивается полного алфавита из которого генерируется капча и тупо сохраняет каждую букву отдельно. Ищем по маске.
          • +1
            Почему вы решили, что я предлагаю не искажать буквы? Я написал, что буквы искажены. Получить одинаковое искажение букв для всех трёх слоёв не проблема.
    • 0
      Вот такую капчу расшифровать очень сложно будет. Надо подумать — и над использованием, и над алгоритмом. Спасибо!
    • 0
      Отличный вариант. Можно два коротких слова, разным шрифтом и тень выворачивать рандомно в стороны.
      • 0
        Да, лучше несколько понятных слов, чем случайный набор букв. Угол тени определить легко, она тут для удобства восприятия. Дополнительный шрифт, на мой взгляд, слегка повысит стойкость, но осложнит задачу пользователю. Дополнительную стойкость, тоеоретически, можно получить искажением контура, вращением букв на небольшой угол и смещением их по вертикали. Так может быть сложнее выделить из неё отдельные буквы.
    • +1
      Есть ощущение, что без деформаций это разгадывается элементарным алгоритмом. Нужно просто брать буквы не во всю ширину.



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

      Хотя сама идея классная, да.
      • 0
        Да, вы правы, если позиции букв известны, конечно можно сопоставить с шаблонами. Поэтому рабочий вариант требует искажений, в том числе сдвигов, изменения размера букв и их поворота.
        • 0
          Позиции могут быть и не известны, обучить можно вручную. Искажения гораздо важнее.
  • 0
    Прокомментировать чуть подробнее код (в частности, интересна findSubRects) можете? А то сразу не получилось понять :)
    • 0
      когда количество найденных прямоугольников меньше чем нужно найти, мы делаем предположение, что некоторые символы склеены, потом с помощью сравнений площадей определяем необходимое количество прямоугольников, которое нужно найти на части изображения, и вызываем findSubRects .
      В самой findSubRects делим картинку на нужное количество прямоугольников по заданным координатам.
      Потом в каждом из полученных прямоугольников ищем наибольшую связанную область.
      Код не инвариантен, и на самом деле дал не очень большой прирост качества распознавания.

      Постараюсь потом прокомментировать все спорные участки кода, о обновлю листинг.
      • 0
        Почему nRects может быть максимум 3? И да, манипуляции в каждом кейзе совсем неясны.
  • –2
    «Как оказалось каптча не очень сложная и легко поддается взлому.» – чудесно!
  • 0
    Вообще капча — уходящий век. Есть масса способов отделить роботов от человека, просто капчу, видимо, проще всего прикрутить.
    • +2
      Есть масса способов отделить роботов от человека

      А поподробней?
      • –5
        image
        • 0
          Галерею картинок придётся всё время обновлять, так что очень непрактично. Да и тупо выбирая картинки наугад каждый 84-й раз вы будете правильно опознавать котят.
          • 0
            Зачем же самим напрягаться? www.flickr.com/search/?q=kittens
            • +4
              Не, ну фотки там, конечно, прикольные, но не всегда понятно, где там котята.
        • +1
          О, вариант то хороший. Только вот я уже представляю, как мои родители с нулевым знанием английского будут искать какого-нибудь «розовато-лилового бурундучка». Да и самому как то попадалась капча, в которой требовалось найти (вроде) какой то определенный цветок, о котором я разве что только слышал.
          • 0
            У меня для вас и ваших пользователей бесплатное решение: напишите сверху «Выберите 3 картинки с котятами». И даже не благодарите.
            • 0
              Вам напомнить, что один из прогонов нейросетей (в целях классификации) для обучения на YouTube в результате сам без поставленной на то задачи сгенерировал нейросеть для распознавания котов? Прошу прощения за формулировки, просто незнаком с этой темой
              • +1
                Напомните. Заодно с обосованием, что 1) такая сеть проще сети для взлома текстовых капч, и 2) что котята распознаются людьми тяжелее, чем смазанные буквы.
        • +4
          Я люто ненавижу распознавать такие капчи, это хуже любого текста.
        • 0
          Ну да, на этой картинке робота озадачит то, что котят четыре, а кликнуть просят на троих
          • 0
            Просят кликнуть на три картинки с котятами.
            • +1
              Извините за мой плохой английский. Видимо я даже до робота не дотягиваю.
        • 0
          Все пропало — harthur.github.com/kittydar/
      • 0
        Тут надо статью писать. В паре предложений не уложиться.
  • 0
    > Как оказалось каптча не очень сложная и легко поддается взлому.
    > Количество правильно распознанных каптч: 49.17 %

    А если мой алгоритм объединить с вашей нейронной сетью, то получится отличный онлайн-OCR. Красивая тема :-)
    Да, осталось придумать, кому и зачем нужна онлайн-OCRка…
    • 0
      Альтернатива какому-нибудь antigate? Хотя, не думаю, что _онлайн_ OCR сейчас кого-нибудь заинтересует. И antigate и ваша онлайн OCR — оба будут иметь проблемы с производительностью (т.к. оба — сторонние сервисы), при этом antigate всегда будет распознавать лучше, т.к. там куча народу разгадывает картинки вручную за копейки. Для спама больше подходит распознавалка, работающая на той же машине, что и бот.

      Альтернатива FineReader? Тоже нет, т.к. алгоритма распознавания однотипной капчи недостаточно для распознавания разных-разных документов.
      • 0
        Нет, зачем? Распознавалка не капч, а сканированных документов. Или это уже не актуально?
        А что ещё можно по такому же алгоритму распознавать? Лица? Звуки?.. (пошёл думать)
    • +1
      Есть же онлайн OCR-ка pixodrom. Но там кажется люди распознают.
  • 0
    а рекаптчу никто не пробовал распознавать нейронными сетями?
  • 0
    По мне так эту рекапчу только боты умеют хорошо разбирать. Был у меня сайт с рекапчей и она ни коим образом не помогла в борьбе с автоматическими регистрациями
    • 0
      Это не из-за рекапчи, а потому что сессию не чистили, известная дырка. По-моему информация об этом где-то даже на хабре пробегала.
  • +1
    А она ведь еще кое-где есть на Хабре! habrahabr.ru/info/advertising/workshops/
  • 0
    А что автор скажет про
    image

    Сами буквы без искажений, никаких поворотов, только искривление всего изображения. Разумеется, сетка для отладочных целей.
    • +1
      Я понял, что там написано, только после очень вдумчивого разглядывания.
      • 0
        даже последний вариант, где линии гладкие?
        • 0
          Если бы добавить немного антиалиасинга, хотя бы x4 (а лучше x8, т.к. у вас довольно сильные искажения), то было бы уже лучше — как минимум в последнем варианте. Первый из трех вообще нечитаем, у второго нечитаемы отдельные буквы, если их «раздувает» так, что они превращаются в одно пятно.
          • 0
            Антиалиасинг — это дорого с точки зрения генерации. Когда насируют капчу, то могут легко положить сервер. Поэтому нужен быстрый алгоритм, который будет просто не только реализовать, но и исполнять.
            • 0
              Совсем недорого, если вы будете искажать не пиксельную карту, а векторное представление шрифта (и сетки, если захотите).

              В самом простом случае, без применения сплайнов или кривых Безье, считайте, что буквы состоят из замкнутой цепи направленной отрезков, узловые точки которого вы определяете с высокой плотностью. Допустим, что при движении по часовой стрелке, область, ограниченная этими отрезками, заполняется цветом тела, а при движении против часовой стрелки — цветом фона, это даст вам возможность создавать дырки в буквах (например, в «б») и цифрах («8»).

              Таким образом, перед построением капчи у вас должны быть в распоряжении несколько массивов узловых точек, с указанием направления (CW/CCW) для каждого из массивов. Координаты каждой точки, вне зависимости от принадлежности к какому-либо массиву, вы умножаете на ту же матричную функцию, что у вас использовалась для искажения оригинального изображения на попиксельной основе.

              Затем скармливаете вашей графической библиотеке по очереди все полигоны с цветом тела, затем с цветом дырок. Можно, конечно, делать еще и occlusion mapping, но я не помню ни в кириллице, ни в латинице букв с двумя областями связности, одна из которых находилась бы в «дырке» от другой, так что это будет немного перебором.

              Экономия будет значительной, даже с расходами на растеризацию полигонов — вам все-таки нужно умножать не каждый пиксель, а только узловые точки векторых букв. Пиксельное зашумление можно добавить в пост-обработке.
              • 0
                цепи направленной отрезков, узловые точки которого

                «цепи направленных отрезков, узловые точки которых», конечно же. Не знаю, что на меня нашло.
              • 0
                Все заканчивается на «скармливаете вашей графической библиотеке» — лично я быстрых растеризаторов просто не знаю. И даже результат сравнительно быстрого Фритайпа лучше предварительно растеризировать. В принципе, перед растеризацией к глифу можно применить матрицу трансформаций, но этим мы получим набор шаблонов, который очень просто ломается. Пиксельный битмап же можно хранить в памяти, часть трансформаций проводить вообще через memmove (горизонтальные сдвиги) и переставление байт по заранее расчитанным трансформациям (найти в них повторы сложнее).

                Если вы знаете быстрые растеризаторы — напишите, поиграюсь с бенчмарками (как раз пришла пора написать очередную ненужную говностатейку для поднятия кармочки)

                Еще узкий момент — компрессия, сжимать в GIF достаточно дорого, у меня выходило порядка 3000 каптч в секунду (неоптимизированный кодер из Libavcodec, в принципе можно его обкромсать до сжатия битмапа, выкинуть подсчет палитры, формирование хидера и т.д., производительность должна быть выше). Сжатие в PNG по моему опыту менее эффективно для деформированнх цифирок, бенчмарков не делал. НО! В том же PNG я могу сделать 1-битный битмап без сжатия, т.е. просто к буферу-заголовку приклеить буфер с телом капчи. Никакого дефлейта вообще. Все просто летает, размер 1-битного рисунка небольшой и вполне приемлем. Но никакого антиалиасинга.

                Только не надо писать «ой, да это ж хайлоад, у тебя должно быть 50 серверов». У меня не хайлоад, я просто не хочу позволить насильнику капчи сломать сервер. К примеру, надо обслужить множество запросов, в том числе от ботов (которых и фильтровать), а боты любят насиловать именно динамику, поэтому насилуют именно капчу.
                • 0
                  В случае векторных букв антиалиасинг не очень-то будет и нужен, нежатого однобитного битмапа вполне хватит. Вместо существующего растеризатора я бы вспомнил спектрум и сделал на Си свой велосипед — благо, только для отрезков с одним цветом заливки это совсем несложно.
                  • 0
                    Как сделаете — залейте на гитхаб :)
                    Линии рисовать несложно (однако с реализацией может быть множество нюансов), а проводить пермутацию байтов по шаблону — еще проще.
                    Да и скоростной растеризатор отрезков — это не та задача, которую я бы хотел решать (геометрию никогда не любил), а потом тюнить долгие месяцы.
                    • 0
                      Challenge accepted.
                      • 0
                        dump.bitcheese.net/files/odaxyry/captcha_0022.gif

                        вот решил сделать кучу крутилок и свистелок
                      • 0
                        Ну как там дела? А то я вот такое придумал:

                        • 0
                          По-моему, тут анимация лишняя. Если наложить все кадры друг на друга, то неплохой эффект «дырявости» символов исчезнет (не пробывал, но кажется, что так). Можно выбрать любой кадр, и показывать только его: будет и надежнее, и быстрее (рендерить надо только одну картинку).

                          А что это за эффект вообще? Как определяется где рисовать символ, а где нет?
                          • 0
                            Ну тут и имелось в виду, что каждый кадр — отдельная капча. Не рендерить же портянку из 150 каптч друг на друге. Хотя вот скажем в habrahabr.ru/qa/32069/ вообще читать не умеют, даже когда на это прямо указал.

                            Эффект — банальная матрица свертки с рандомом + порог на выходе. Но что-то оно мне разонравилось уже, я вот с таким экспериментирую: rghost.net/42890070/image.png — самому страшно.
              • 0
                Здесь удобнее использовать шрифты из библиотеки Hershey, которые рисуются множеством толстых линий. Обычными линиями, без сплайнов и кривых Безье.

                Буква а
                Надпись
                • 0
                  Это просто прекрасно, толстые линии (т.е. прямоугольники и полукруги) рисовать еще дешевле, чем выпуклые полигоны :)
  • 0
    А почему у вас в архиве из цифр только 3 4 6 9?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.