Введение
В данной статье кратко рассказывается о процессе взлома 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
Шумы убираем очень просто, для этого все пиксели изображения которые светлее некоторого уровня делаем белыми.
Пример обработки:
| Оригинальное изображение |
Изображение после обработки |
|---|---|
 |
 |
Для бинаризации используем адаптивный алгоритм бинаризации, в котором для каждого пикселя (или областей пикселей) определяется свой порог бинаризации [ Адаптивная бинаризация].
Примеры бинаризации:
| Хороший пример сегментации (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 %
Выводы
Как оказалось каптча не очень сложная и легко поддается взлому. Для ее усложнения необходимо использовать больше пересечений символов, а также их разное количество.
Чтобы улучшить текущее качество распознавания можно сделать следующие улучшения:
- улучшить алгоритм сегментации (например используя гистограмму)
- увеличить обучающую выборку
Если статья понравилась, в следующей могу подробно рассказать о основных подходах к распознаванию человеческого лица.
Исходники с обучающей выборкой
Исходники. Дропбокс
Яндекс Народ
