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

Введение

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

Обзор задачи

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

Основные трудности распознавание данной каптчи:

Искаженные символы
Шумы и размытость
Размеры символов сильно отличаются
Пересечение символов

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

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

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

Каждую систему распознавания символов можно представить следующим образом:
Взлом старой каптчи сайта Хабрахабр

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

Детальный анализ исследуемой каптчи позволил выделить ее основные особенности:

На каптче всегда присутствуют 6 символов
Всегда используется схожий (скорее всего один и тот же) метод зашумления
Случаи пересечения или наложения символов редкие

Исходя из этого, был построен следующий алгоритм сегментации:

Убрать шумы
Бынаризировать изображение
Выделить 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

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

Оригинальное изображение	Изображение после обработки

Для бинаризации используем адаптивный алгоритм бинаризации, в котором для каждого пикселя (или областей пикселей) определяется свой порог бинаризации [ Адаптивная бинаризация ^[1]].
Примеры бинаризации:

Хороший пример сегментации (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 %

Выводы

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

улучшить алгоритм сегментации (например используя гистограмму)
увеличить обучающую выборку

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

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

Исходники. Дропбокс ^[2]

Автор: drozdVadym

Источник ^[3]

Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/matlab/21678

Ссылки в тексте:

[1] Адаптивная бинаризация: http://homepages.inf.ed.ac.uk/rbf/HIPR2/adpthrsh.htm

[2] Исходники. Дропбокс : https://dl.dropbox.com/u/19475056/HabrahabrCaptchReader/HabrahabrCaptchReader.zip

[3] Источник: http://habrahabr.ru/post/161159/

Нажмите здесь для печати.