Распознавание образов с помощью шаблонов

Распознавание образов с помощью шаблонов

© 2006 Игнатьев Дмитрий,
http://dign.narod.ru

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

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

На самом деле, многие и не подозревают, что их ухищрения не непреодолимы. Рассмотрим примеры, начиная с легкого и заканчивая сложным.

Пример 1. www.kyivstar.net

Картинки взяты с сайта мобильного оператора: http://www.kyivstar.net/ru/sms. Размер увеличен в 6 раз.

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

Далее необходимо разделить рисунок на отдельные изображения. Это просто. Если подсчитывать количество черных пикселей в каждой вертикали, то в тех вертикалях, где сумма равна нулю, есть разрыв между символами. Для начала получим крайние значения первого элемента: Left, Top, Right, Bottom.

Pascal C
Left := 0;
Top := 0;
Right := Width-1;
Bottom := Height;
Left = 0;
Top = 0;
Right = Width-1;
Bottom = Height;

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

Pascal C
for X := Left to Right do
for Y := Top to Bottom do
 if Pixel[X,Y] = Black then begin
 Left := X;
 Exit;
 end;
for (X=Left; X<=Right; X++) {
 for (Y=Top; Y<=Bottom; Y++) {
 if (Pixel[X,Y] == Black) {
 Left = X;
 return;
 };
 };
};

Находим правую точку. В цикле проверяем суммы черных, если сумма по вертикали равна нулю, значит, достигли конца элемента.

Pascal C
for X := Left to Right do begin
 Count := 0;
 for Y := Top to Bottom do
 if Pixel[X,Y] = Black then Inc(Count);
 if Count = 0 then begin
 Right := X-1;
 Exit;
 end;
end;
for (X=Left; X<=Right; X++) {
 Count = 0;
 for (Y=Top; Y<=Bottom; Y++) 
 if (Pixel[X,Y] == Black) Count++;
 if !(Count) {
 Right = X-1;
 return;
 };
};

Таким же образом находим верхнюю и нижнюю точки.

Pascal C
for Y := Top to Bottom do
for X := Left to Right do
 if Pixel[X,Y] = Black then begin
 Top := Y;
 Exit;
 end;
...
for Y := Top to Bottom do begin
 Count := 0;
 for X := Left to Right do
 if Pixel[X,Y] = Black then Inc(Count);
 if Count = 0 then begin
 Bottom := Y-1;
 Exit;
 end;
end;
for (Y=Top; Y<=Bottom; Y++) {
 for (X=Left; X<=Right; X++) {
 if (Pixel[X,Y] == Black) {
 Top = Y;
 return;
 };
 };
};
...
for (Y=Top; Y<=Bottom; Y++) {
 Count = 0;
 for (X=Left; X<=Right; X++)
 if (Pixel[X,Y] == Black) Count++;
 if !(Count) {
 Bottom = Y-1;
 return;
 };
};

Для нахождения следующих элементов точкой поиска является правая точка предыдущего элемента.

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

Pascal
function GetPixel(X,Y: integer): Boolean;
begin
 if (X >= 0) and (X < Width) and (Y >= 0) and (Y < Height)
 then Result := Data^[Y*Width+X]
 else Result := false;
end;

procedure SetPixel(X,Y: integer; Value: boolean): Boolean;
begin
 if (X >= 0) and (X < Width) and (Y >= 0) and (Y < Height)
 then Data^[Y*Width+X] := Value;
end;
C
bool GetPixel(int X, int Y) {
 if ((X >= 0) && (X < Width) && (Y >= 0) && (Y < Height))
 return *Data[Y*Width+X] else return false;
};

void SetPixel(int X, int Y, bool Value) {
 if ((X >= 0) && (X < Width) && (Y >= 0) && (Y < Height)) 
 *Data[Y*Width+X] = Value;
};

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

Теперь каждый полученный элемент сравниваем с каждым изображением из массива эталонов. Массив эталонов (Patterns) готовится заранее, в нашем случае это массив из десяти изображений '0123456789'. Каждое эталонное изображение ассоциируется с определенным символом. Сравнение двух изображений заключается в подсчете совпадающих черных точек. Чем больше совпадений, тем лучше.

Упрощенно сравнение выгладит так:

Pascal
Count := 0;
for X := 0 to Width-1 do
for Y := 0 to Height-1 do
 if (Pixel1[X,Y] = Black) and (Pixel2[X,Y] = Black) then Inc(Count);
Result := Count * 200 div (CountBlack1+CountBlack2);
C
Count = 0;
for (X=0; X<Width; X++) {
 for (Y=0; Y<Height; Y++)
 if ((Pixel1[X,Y] == Black) && (Pixel2[X,Y] == Black)) Count++;
}
return Count * 200 div (CountBlack1+CountBlack2);

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

Здесь вы можете загрузить пример программы, который реализует данный алгоритм распознавания текста. Для того, чтобы увидеть статистику распознания каждого символа, наведите мышку на этот символ на картинке. Эталонные изображения цифр находятся в контейнере kyivstar.dat, который можно распаковать любым zip-совместимым архиватором.

Пример 2. Больше шума.

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

Если, кто знает, откуда эти картинки, пишите мне.


Первым делом переводим картинку в монохромное изображение.

Pascal
for Y := 0 to Height-1 do
for X := 0 to Width-1 do begin
 Color := Pixel[X,Y];
 Color := (Red(Color)+Green(Color)+Blue(Color)) div 3;
 if Color > 100 then Pixel[X,Y] := White
 else Pixel[X,Y] := Black;
end;
C
for (Y=0; Y<Height; Y++) {
 for (X=0; X<Width; X++) {
 Color = Pixel[X,Y];
 Color = (Red(Color)+Green(Color)+Blue(Color)) div 3;
 Pixel[X,Y] = ?(Color > 100, White, Black);
 };
};

Теперь избавляемся от полос. Узнаем их цвет. Для черных полос сумма черных пикселей в каждой строчке или столбцу всегда больше нуля.

Pascal
ColorLine := Black;
for X := 0 to Width-1 do begin
 Count := 0;
 for Y := 0 to Height-1 do if Pixel[X,Y] then Inc(Count);
 if Count = 0 then begin
 ColorLine := White;
 Break;
 end;
end;
C
ColorLine = Black;
for (X=0; X<Width; X++) {
 Count = 0;
 for (Y=0; Y<Height; Y++) if (Pixel[X,Y]) Count++;
 if !(Count) {
 ColorLine = White;
 Break;
 };
};

Данные о вертикальных и горизонтальных линиях заносим в массивы Vertical и Horizontal. Затем восстанавливаем утраченный цвет. Черный пиксель на линии меняем на белый, если пара смежных точек по вертикали или горизонтали имеют белый цвет. Аналогично действуем для белого пикселя.

Еще проще сделать так: пиксель на линии будет черным, если один из смежных пикселей тоже черный.

Pascal
for Y := 0 to Height-1 do
for X := 0 to Width-1 do
 if Vertical[X] then Pixel[X,Y] := Pixel[X-1,Y] or Pixel[X+1,Y];
for Y := 0 to Height-1 do
for X := 0 to Width-1 do
 if Horizontal[Y] then Pixel[X,Y] := Pixel[X,Y-1] or Pixel[X,Y+1];
C
for (Y=0; Y<Height; Y++) {
 for (X=0; X<Width; X++)
 if (Vertical[X]) Pixel[X,Y] := Pixel[X-1,Y] || Pixel[X+1,Y];
}
for (Y=0; Y<Height; Y++) {
 for (X=0; X<Width; X++)
 if (Horizontal[Y]) Pixel[X,Y] := Pixel[X,Y-1] || Pixel[X,Y+1];
}

Получаем следующую картинку:


Следует обратить внимание, что полностью воссоздать изображение под линиями невозможно, символы могут быть обрезаны с любой из сторон или наоборот быть шире и выше.

и оригинал

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


X-1,Y-1

X,Y-1

X+1,Y-1

X-1,Y
X,Y

X+1,Y

X-1,Y+1

X,Y+1

X+1,Y+1

В одном из 9 случаев результат сравнения будет самым высоким 90% - 98%.

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

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

Пример 3. rapidshare.de

Сайт предназначен для файлового обмена. Скачивание файлов защищено картинками следующего вида:

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

Далее сканируем картинку слева направо и выявляем первых три цвета. Для первого случая это:

Находим крайнюю левую точку символа и рисуем два новых изображения. Первые изображение получается путем перебора цветов 1 и 2, а второй - 1 и 3. Для перебора используем рекурсию.

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

Таким вот образом получаем два изображения, которые обрезаются и преобразуются в монохромные цвета.

Далее каждое изображение вращаем и сравниваем с эталоном. Если использовать один поворот влево и один поворот вправо на 4 градуса, плюс 1 пиксель на смещение, чтоб уменьшить погрешность, получаем 3 * 9 = 27 сравнений. А так как у нас два изображения, то всего будет 54 проверки на один эталон. В базе 34 эталонных изображений и 3 символа на картинке, то всего сравнений будет 5508.

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

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

Значение бегунка Максимальный угол Шаг угла
1 0 0
2 4 4
3 6 3
3 6 2
3 6 1

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

Заключение

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

Исключением являются алгоритмы эффекта "искривленного стекла". Картинка с текстом обрабатывается так, что отдельные элементы символа искривляются, словно его поместили под стекло с оптическими искажениями. Такое можно увидеть на поисковом сайте google или на yahoo:

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

Copyright© 2006 Игнатьев Дмитрий
Специально для Delphi Plus


Пожалуйста, оцените статью

Отлично
Хорошо
Средне
Плохо
Очень плохо



Новости за месяц

  • Ноябрь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс