Pull to refresh

Взлом старой каптчи сайта Хабрахабр

Reading time 9 min
Views 47K

Введение



В данной статье кратко рассказывается о процессе взлома 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 %

Выводы


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


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

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


Исходники. Дропбокс
Яндекс Народ
Tags:
Hubs:
+169
Comments 118
Comments Comments 118

Articles