Введение
В данной статье коротко рассказывается о процессе взлома captcha используемой ранее при входе на сайт Хабрахабр.
Целью работы является применение знаний на практике и проверка сложности каптчи.
При разработке алгоритма использован Matlab.
Обзор задачи
Старая каптча Хабрахабр выглядела так:
Основные трудности распознавание данной каптчи:
- Искаженные символы
- Шумы и размытость
- Размеры символов сильно отличаются
- Пересечение символов
Честно говоря, у меня не всегда получалось с первого раза правильно прочитать каптчу, поскольку часто символы А и 4, L и 4 были неразличимые.
Все же, несмотря на некоторые сложности, рассмотрим основные идеи по чтению данной каптчи.
Этап 1. Построение системы сегментации
Каждую систему распознавания символов можно представить следующим образом:
В нашем случае необходимо реализовать последние две подсистемы.
Детальный анализ исследуемой каптчи позволил выделить ее основные особенности:
- На каптче всегда присутствуют 6 символов
- Всегда используется схожий (скорее всего один и тот же) метод зашумления
- Случаи пересечения или наложения символов редкие
Исходя из этого, был построен следующий алгоритм сегментации:
- Убрать шумы
- Бынаризировать изображение
- Выделить 6 наибольших областей связности
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