Skip to main content

Распознавание номеров в MatLab. Вторая часть. Машинное обучение

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

Введение.

Для начала я расскажу, что такое решающее дерево.
Статья в вики

Построение решающего дерева.

Пусть у нас есть некоторое параметрическое пространство (для простоты двумерное). В нем определены два класса объектов (синие и красные точки). Это наша обучающая выборка.
image

Мы хотим эти объекты кластеризовать. Для начала разделим наше пространство на две части прямой (гиперплоскостью). Любой (даже рандомной). Получим разбиение нашего пространства на два подпространства. Будет рекурсивно продолжать разбивать их, пока а каждом из них не останутся только объекты одного цвета (имеющие одну метку).
image
Так как подпространство мы разбивали рекурсивно, то мы можем, следуя этой рекурсии, построить дерево, в узлах которого будут наши прямые (гиперплоскости). Это так называемые предикаты — условия, которые делят наше параметрическое пространство на две группы, для которых предикат истина или ложь. Предикаты могут иметь как простую зависимость от параметров ( x + 2y > 241 ), так и сложную ( x^2 + y^2 > 25 ). Дерево предикатов называется Decision Tree ( решающее дерево или дерево принятия решения ).
Вот пример решающего дерева из гугля, по абстрактным предикатам ( A == blue ), ( B >= 4.5 ) и ( C ):
image

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

Использование решающего дерева.

Построив дерево для нашего параметрического пространства, мы можем попробовать добавить в нашу выборку объект с неизвестным классом, но известным набором параметров.
image
Казалось бы, если бы не было никакого дерева, мы бы отнесли этот объект к группе красных, так как он к ним ближе и вообще, синий там засланец. Но мы построили такое неудачное дерево, что, при использовании наших предикатов, мы получим для этого объекта синюю метку.
Эта проблема решается использованием так называемого решающего леса — множества решающих деревьев. И раз мы не можем взять качеством предикатов ( вот тут вроде руками строили, а все равно плохо вышло ), то попробуем взять количеством. Статья на Вики.

Решающий лес.

Random Forest — это алгоритм построения набора решающих деревьев, которые используют случайные предикаты, строят предикаты по случайному подмножеству параметров пространства, и строят предикаты на основе случайного подмножества нашей обучающей выборки. Процесс получается сильно рандомизированный. Тут надо пару слов сказать о контроле обучения леса (более подробно можно прочитать тут ).

Контроль обучения.

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

Использование леса при распознавании номеров.

Итак, теперь мы знаем, что такое решающий лес и как нам его применить к некоторому параметрическому пространству. Для решение задачи (описание в первой части ) нам была выдана готовая реализация RadnomForest для МатЛаба (правда в следующем семестре нам все таки пришлось прогать его ручками на плюсах). Готовые рализации есть также в тулките OpenCV. Также нам была дана обучающая выборка символов (22 класса символа, по 100 изображений в каждом классе).
У нас есть все тот же номерной знак.
Пример исходной картинки:
716.bmp

Необходимо выделить на нем 6 основных символов ( вида бцццбб, б — буква, ц — цифра).
Сначала мы обучим классификатор.

function model = CNR_train( classpath , debugga)
chars = '0123456789ABCEHKMOPTXY';
X = zeros([2200 10]);
Y = zeros([2200 1]);
time1 = tic;
if debugga
count = 3;
else
count = 100;
end
 
for char=1:22
time2=tic;
fprintf('time on char %s :: ', chars(char));
for sample=1:count
K = (char-1)*100 + sample;
 
sym = imread( [classpath '/' chars(char) '/' num2str(sample) '.bmp' ] );
sammod = sym;
sammod = imadjust(sammod);
us = fspecial('unsharp');
sammod = imfilter(sammod,us);
sammod = imadjust(sammod);
sammod = sammod < 150;
simresy = imresize(sammod,[64 NaN]);
simresx = imresize(sammod,[NaN 64]);
 
[~, n] = size(simresy);
IntensityX = sum(simresy,2)/n;
[m, ~] = size(simresx);
IntensityY = sum(simresx,1)/m;
syms = regionprops(sammod,'EulerNumber','Eccentricity','Centroid','Orientation','BoundingBox');
X(K,1) = syms(1).EulerNumber;
X(K,2) = syms(1).Eccentricity;
X(K,3) = syms(1).Centroid(1)/syms(1).BoundingBox(3);
X(K,4) = syms(1).Centroid(2)/syms(1).BoundingBox(4);
X(K,5) = syms(1).Orientation;
X(K,6) = syms(1).BoundingBox(3)/syms(1).BoundingBox(4);
X(K,7:70)= IntensityX(:);
X(K,71:134)= IntensityY(1,:);
Y(K) = char;
end
fprintf('%.2f (sec)\n', toc(time2));
end
model = classRF_train(X,Y,1000,15);
save model;
fprintf('total time %.2f\n',toc(time1));
end

Тут мы делаем следующее:

  1. — считываем изображения из всех классов;
  2. — каждое изображение фильтруем ( про фильтрацию можно почитать в первой части );
  3. — для отфильтрованного символа строим вектор признаков.

В качестве признаков можно выбрать что угодно, тут все зависит от вашей фантазии и навыков.
Навыков тогда у меня было не много, поэтому параметры я выбрал следующие:

  • сумма интенсивностей пикселей по горизонтали для картинки формата NaNx64 (ресайз с сохранением пропорций).;
  • аналогично сумма интенсивностей пикселей по вертикали для картинки формата (64xNaN). Обе суммы нормированы размером в которую переходил NaN (то есть это получался процент ярких пикселей в картинке) ;
  • число Эйлера;
  • положение центра масс (нормированное);
  • эксцентриситет;
  • ориентация.

Получается 134-мерный вектор-признак.
В строке 41 я записываю в вектор меток число, соотвествующее символу на картинке.
Далее мы просто запускаем
model = classRF_train(X,Y,1000,15);
и получаем обученную модель решающего леса. Осталось его сохранить.
Теперь код скрипта, который использует классификатор для поиска.

function number = CarNumberRecognition2(filename, vd)
 
load model;
I = imread(filename);
chars = '0123456789ABCEHKMOPTXY';
outstr = ' ';
 
Ires = imresize(I, [200 NaN]);
[m n] = size(Ires);
Ires = imcrop(Ires,[10 0 n-10 m]);
 
OutI = zeros([size(Ires) 3],'uint8');
OutI(:,:,1) = Ires;
OutI(:,:,2) = Ires;
OutI(:,:,3) = Ires;
[a b] = size(Ires);
shift = a*b;
 
Imod = imfilter(imadjust(Ires),fspecial('unsharp'));
LMap = medfilt2(Ires,[90 90],'symmetric');
Imod = (imadjust(0.7*Imod - 0.7*LMap) < 10);
 
NewI = zeros(size(Imod),'uint8');
areas = regionprops(Imod,'Image','Perimeter','EulerNumber','BoundingBox','Area','Orientation','Eccentricity','PixelIdxList');
 
if vd,figure,end
 
for i=1:size(areas)
if ~ ( test(areas(i)))
NewI(areas(i).PixelIdxList(:))= 255;
else
for j=1:size(areas(i).PixelIdxList(:))
OutI(areas(i).PixelIdxList(j)) = OutI(areas(i).PixelIdxList(j)) * 2;
end
end
end
 
NewMod = NewI == 255;
fprintf('%s -> ',filename);
X = zeros([1 134]);
p = 1;
areas = regionprops(NewMod,'Image','EulerNumber','BoundingBox','Area','Orientation','Eccentricity','PixelIdxList');
for i=1:size(areas)
subplot(3,10,p);
p = p +1;
 
symimg = areas(i).Image;
 
symresy = imresize(areas(i).Image,[64 NaN]);
symresx = imresize(areas(i).Image,[NaN 64]);
imshow(symresy);
[~, n] = size(symresy);
IntensityX = sum(symresy,2)/n;
 
[m, ~] = size(symresx);
IntensityY = sum(symresx,1)/m;
 
syms = regionprops(symimg,'EulerNumber','Eccentricity','Centroid','Orientation','BoundingBox');
 
X(1) = syms(1).EulerNumber;
X(2) = syms(1).Eccentricity;
X(3) = syms(1).Centroid(1)/syms(1).BoundingBox(3);
X(4) = syms(1).Centroid(2)/syms(1).BoundingBox(4);
X(5) = syms(1).Orientation;
X(6) = syms(1).BoundingBox(3)/syms(1).BoundingBox(4);
X(7:70) = IntensityX(:);
X(71:134)=IntensityY(:);
 
Y = classRF_predict(X,model);
title(chars(Y));
if vd
for j=1:size(areas(i).PixelIdxList(:))
OutI(areas(i).PixelIdxList(j)+ shift) = OutI(areas(i).PixelIdxList(j)+shift) + 70;
end
end
outstr(i) = chars(Y);
end
while (isletter(outstr(1)) && isletter(outstr(2))) || (~isletter(outstr(1)) && isletter(outstr(2)))
outstr(1:size(outstr,2)-1) = outstr(2:size(outstr,2));
end
 
fprintf('%s (origin. %s)\n',outstr(1: ( min ( 6 , size ( outstr,2 ) ) ) ) ,outstr);
if vd
subplot(3,1,3);
imshow(OutI);
end
number = sprintf('%s',outstr(1: ( min ( 6 , size ( outstr,2 ) ) ) ) );
end
function good = test(area)
good = (area.Area > 3500 ||...
area.Area < 400 || ...
area.Area > 0.8*area.BoundingBox(3)*area.BoundingBox(4) ||...
area.EulerNumber > 2 ||...
(abs(area.Orientation) < 25 && area.Eccentricity > 0.8)||...
area.BoundingBox(4)/area.BoundingBox(3) > 11 ...
);
end

Тут все очень похоже на предыдущую задачу. Небольшая предобработка картинки, выделение наиболее значимых областей. Все это я уже описывал в первой части, подробно останавливаться на этом не буду. Дальше мы для каждого тестируемого символа ( или подозрительного блоба ) строим такой же точно векто-признак, как и при обучении.
Далее скармливаем вектор-признак нашему лесу (загруженному из ранее сохраненной модели)

Y = classRF_predict(X,model);

и получаем на выходе метку.

Улучшения.

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

  1. Использовать более сложный вектор-признак
  2. Улучшить предобработку
  3. Обучить отдельный классификатор для мусора ( потому что если мусорный кусок пройдет тест на пригодность, то какая-нибудь метка ему присвоится точно).

Код и ссылки:

http://static.scaytrase.ru/cnr/cnr1.zip — Архив первого задания, в том виде, в котором я его сдал на проверку ( точность около 70% полностью распознанных номеров и около 80% распознанных цифр)
http://static.scaytrase.ru/cnr/cnr2.zip — Архив второго задания
http://static.scaytrase.ru/cnr/CV2010.zip — Полный архив исходных кодов, включая тестовую и обучающую выборку по всем трем заданиям. Код может содержать отладочные returnы, так что тестить лучше отправленный код.
http://courses.graphicon.ru/ — сайт курсов лаборатории КГиММ ВМК МГУ. Много интересных материалов по теме.
http://cgm.computergraphics.ru/ — сетевой журнал о КГиММ. Тоже много хороших статей.
http://static.scaytrase.ru/cnr/article-cnr-eng.pdf — статья о распознавании номеров на вагонах (немного другой подход к сегментированию )

http://static.scaytrase.ru/cnr/RandomForest.zip — Выданный нам классификатор на МатЛаб
http://static.scaytrase.ru/cnr/RF_tutorial.doc — Мануал по использованию RandomForest.