На данную статью меня натолкнула статья Alex’а Поветкина — «Распознавание образов методом потенциальных функций»
Итак, мы собираемся написать программу на Delphi (я использую версию 6), способную перевести символы с картинки в текст. Задача довольно популярная в интернете, и на каждый пост «Хочу реализовать распознавание символов!!! Помогите» самые частые ответы «почитай в интернете» либо «не берись, используй файнридер» и тому подобное.
Я, как и многие другие, начал с изучения основных алгоритмов. Конечно, такие монстры как FineReader тратят на алгоритмическую составляющую огромные деньги, и их секретов нам не узнать, но прочей информации было найдено приличное количество, чтобы понять основные методы. Но начнем издалека.
В детстве, смотря на текст, мы видим всего лишь картинку. Мы ещё не наделены необходимыми критериями её анализа, для того чтобы понять, что на картинке не просто рисунок, а текст, и не просто текст, а какой-то рассказ. Мы растём, и начинаем получать образы символов, узнаём что рисунок с буквой «А» обозначает букву А, а не пароходик. Становясь старше, мы набираем базу образов (или базу критериев образов), по которой путем сравнения и анализа мы можем сказать, какой символ перед нами.
Точно такая же ситуация и с компьютером. Сперва он просто получает в память картинку, затем ищет на ней какие-то области, и после этого сравнивает эти области со своей базой и проводит анализ, результатом которого будет определение символа на изображении. На словах всё просто – передаем в память картинку, ищем на картинке какие-то области, сравниваем с базой, но методы сравнения картинки до сих пор непонятны. Идём в интернет.
Современные методы сравнения изображения делятся на две категории:
1.Сравнение с эталоном
2.Сравнение по критериям
И особняком стоит между ними метод нейронных сетей, поскольку применим в обоих случаях. Использовать его и рассматривать его работы мы не будем, постараемся сделать всё максимально просто и понятно.
Сравнение по критериям наиболее трудоёмко, потому что выполнить алгоритмическую задачу по определению характерных черт символа сложно, да и эффективность подобного алгоритма будет наверняка небольшой. Связано это со схожестью символов, а если мы будем распознавать текст низкого разрешения, то затрат на оттачивание подобного алгоритма будет в разы больше. Однако для столь сложной задачи был найден исходник с решением.
Также были найдены исходники незамысловатых программ, проверяющих крайние точки и точки изгибов на наличие черной области:
Распознавание почтовых индексов
Распознавание картинок Яндекса(CY)
Проблемы распознавания данных программ налицо – при несоответствии изображений(а также наличии шума, посторонних объектов и т.д.) данные программы малоэффективны. Однако они на ура справляются с узким кругом поставленных для них задач. Мы же хотим получить более универсальный пример реализации распознавания.
Сравнение с эталоном – задача более простая и более эффективная. Тут всё максимально просто — создать эталонное изображение и сравнить их. Методов сравнения довольно много – попиксельное, наложение, наложение со смещением и прочие. Статьями по этой теме интернет наполнен сполна. Наиболее интересные работы:
Распознавание образов мобильным роботом
Применение нейросетей в распознавании изображений
Реализация простейшего алгоритма распознавания графических образов
Мы будем использовать самый простой метод сравнения – попиксельный. Суть – поочередное сравнение двух соответствующих пикселей двух черно-белых картинок. Поскольку два пикселя должны быть соответствующими, то картинки должны быть одинаковы по размеру.
Сравнение очень долгий алгоритм, поэтому мы должны оптимизировать работу нашей программы на сравнение не двух картинок скажем 100х100 пикселей(10 000 операций сравнения), а что-то меньшее, но всё также актуальное (сравнивая картинки 8х8 пикселей, различить в них букву довольно сложно даже человеку, поэтому, чем больше пикселей мы берём, тем больше вероятность правильности распознавания и тем большее время требует наш алгоритм). Экспериментальным путём был выбран оптимальный размер – 16х16 пикселей. Но перед изменением размера необходим ещё найти то, что будем изменять.
см. function TForm1.PreParse1(Pic:TPicture):string;
Итак, нам необходимо найти на картинке символы, причем найти их все. Для этого картинка переводится в черно-белую (см. procedure TForm1.Mono(Bmp:TBitmap)), и ищутся все объекты через сравнение с крайними пикселями предположительного символа. Вокруг каждого найденного символа строится рамка красного цвета, именно по этой рамке происходит изменение размера изображения (функция StretchBlt) и его копирование для сравнения (см. function TForm1.Parce3(Pic:TPicture;x1, y1, x2, y2: Integer): TBitmap;)
См. function TForm1.ParceBMP(bmp1:Tbitmap):string;
Алгоритм прост – сравниваем попиксельно (см. function TForm1.Compare(b1,b2:TBitmap):integer), если два пикселя разные (один черный, другой белый), то увеличиваем счетчик R. После полного сравнения двух картинок подставляем счетчик в формулу
Значение, полученное в результате сравнения, получило название «расстояние Хэмминга».
Затем формируем массив результатов вычислений по данной формуле для разных сравнений (наша картинка со всеми эталонами). Берём максимальное значение массива и соответствующий ему символ. Это наш результат!
Следующий этап работы нашей программы – составление базы (массив записей символа и его графического представления). Мы сделаем стандартную базу изображений русских символов и цифр без применения графических редакторов – в исходном коде. Для этого потребуется задать изображение нужного размера, открыть режим канвы, и написать в изображении необходимую букву.
Тут же необходимо обработать полученную картинку так, как мы обрабатываем исходную, чтобы эталон был максимально приближен к распознаваемой картинке и наоборот (об этом читай ниже).
Куда же без них? Нам понадобится также метод обработки ошибок распознавания. Для этого перед распознаванием мы должны сделать специальную кнопочку, которая будет показывать символы и результат работы программы, и спрашивать нас, верно ли распознавание. Если да, то ничего не делать, иначе заносить в базу, структура которой следующая – файл-индексатор, в котором задается количество символов в базе, следующие строки – символ, и ссылка на файл с изображением (см. procedure TForm1.Learn(Pic:TPicture);).
Определяем задачи и рисуем форму:
Полученный исходник тут.
Скрин работающей программы:
— Не может программа распознавать буквы, состоящие из двух фигур: Ы, Й.
— При повороте/шумах/прочее распознавание не корректно.
— Порой распознает маленькие буквы как большие, большие как маленькие (что собственно логично для данного метода)
Вот и написан очередной «распознаватель» текста. Кому он пригодится? Практически никому. Это не FineReader, и не Cuneiform. Тут всё намного проще и понятнее, и менее эффективно. Но, несмотря на это надеюсь, эта статья будет полезна ИТ-сообществу. Данная система может быть изменена под какие-либо другие нужды.
В недалёком будущем хочу дополнить рассказ графиками результатов распознавания, а также сравнением данного метода распознавания с другими.
В ходе написания использовались материалы:
Распознавание образов методом потенциальных функций
Распознавание почтовых индексов (взят алгоритм выделения картинки)
UPD: были проблемы с базой, решил, исходник перезалил, спасибо AmoN'у
Итак, мы собираемся написать программу на Delphi (я использую версию 6), способную перевести символы с картинки в текст. Задача довольно популярная в интернете, и на каждый пост «Хочу реализовать распознавание символов!!! Помогите» самые частые ответы «почитай в интернете» либо «не берись, используй файнридер» и тому подобное.
Я, как и многие другие, начал с изучения основных алгоритмов. Конечно, такие монстры как FineReader тратят на алгоритмическую составляющую огромные деньги, и их секретов нам не узнать, но прочей информации было найдено приличное количество, чтобы понять основные методы. Но начнем издалека.
Суть распознавания – сравнение с образом.
В детстве, смотря на текст, мы видим всего лишь картинку. Мы ещё не наделены необходимыми критериями её анализа, для того чтобы понять, что на картинке не просто рисунок, а текст, и не просто текст, а какой-то рассказ. Мы растём, и начинаем получать образы символов, узнаём что рисунок с буквой «А» обозначает букву А, а не пароходик. Становясь старше, мы набираем базу образов (или базу критериев образов), по которой путем сравнения и анализа мы можем сказать, какой символ перед нами.
Точно такая же ситуация и с компьютером. Сперва он просто получает в память картинку, затем ищет на ней какие-то области, и после этого сравнивает эти области со своей базой и проводит анализ, результатом которого будет определение символа на изображении. На словах всё просто – передаем в память картинку, ищем на картинке какие-то области, сравниваем с базой, но методы сравнения картинки до сих пор непонятны. Идём в интернет.
Методы сравнения
Современные методы сравнения изображения делятся на две категории:
1.Сравнение с эталоном
2.Сравнение по критериям
И особняком стоит между ними метод нейронных сетей, поскольку применим в обоих случаях. Использовать его и рассматривать его работы мы не будем, постараемся сделать всё максимально просто и понятно.
Сравнение по критериям наиболее трудоёмко, потому что выполнить алгоритмическую задачу по определению характерных черт символа сложно, да и эффективность подобного алгоритма будет наверняка небольшой. Связано это со схожестью символов, а если мы будем распознавать текст низкого разрешения, то затрат на оттачивание подобного алгоритма будет в разы больше. Однако для столь сложной задачи был найден исходник с решением.
Также были найдены исходники незамысловатых программ, проверяющих крайние точки и точки изгибов на наличие черной области:
Распознавание почтовых индексов
Распознавание картинок Яндекса(CY)
Проблемы распознавания данных программ налицо – при несоответствии изображений(а также наличии шума, посторонних объектов и т.д.) данные программы малоэффективны. Однако они на ура справляются с узким кругом поставленных для них задач. Мы же хотим получить более универсальный пример реализации распознавания.
Сравнение с эталоном – задача более простая и более эффективная. Тут всё максимально просто — создать эталонное изображение и сравнить их. Методов сравнения довольно много – попиксельное, наложение, наложение со смещением и прочие. Статьями по этой теме интернет наполнен сполна. Наиболее интересные работы:
Распознавание образов мобильным роботом
Применение нейросетей в распознавании изображений
Реализация простейшего алгоритма распознавания графических образов
Мы будем использовать самый простой метод сравнения – попиксельный. Суть – поочередное сравнение двух соответствующих пикселей двух черно-белых картинок. Поскольку два пикселя должны быть соответствующими, то картинки должны быть одинаковы по размеру.
Сравнение очень долгий алгоритм, поэтому мы должны оптимизировать работу нашей программы на сравнение не двух картинок скажем 100х100 пикселей(10 000 операций сравнения), а что-то меньшее, но всё также актуальное (сравнивая картинки 8х8 пикселей, различить в них букву довольно сложно даже человеку, поэтому, чем больше пикселей мы берём, тем больше вероятность правильности распознавания и тем большее время требует наш алгоритм). Экспериментальным путём был выбран оптимальный размер – 16х16 пикселей. Но перед изменением размера необходим ещё найти то, что будем изменять.
Выделение
см. function TForm1.PreParse1(Pic:TPicture):string;
Итак, нам необходимо найти на картинке символы, причем найти их все. Для этого картинка переводится в черно-белую (см. procedure TForm1.Mono(Bmp:TBitmap)), и ищутся все объекты через сравнение с крайними пикселями предположительного символа. Вокруг каждого найденного символа строится рамка красного цвета, именно по этой рамке происходит изменение размера изображения (функция StretchBlt) и его копирование для сравнения (см. function TForm1.Parce3(Pic:TPicture;x1, y1, x2, y2: Integer): TBitmap;)
Алгоритм сравнения
См. function TForm1.ParceBMP(bmp1:Tbitmap):string;
Алгоритм прост – сравниваем попиксельно (см. function TForm1.Compare(b1,b2:TBitmap):integer), если два пикселя разные (один черный, другой белый), то увеличиваем счетчик R. После полного сравнения двух картинок подставляем счетчик в формулу
Значение, полученное в результате сравнения, получило название «расстояние Хэмминга».
Затем формируем массив результатов вычислений по данной формуле для разных сравнений (наша картинка со всеми эталонами). Берём максимальное значение массива и соответствующий ему символ. Это наш результат!
Составление базы
Следующий этап работы нашей программы – составление базы (массив записей символа и его графического представления). Мы сделаем стандартную базу изображений русских символов и цифр без применения графических редакторов – в исходном коде. Для этого потребуется задать изображение нужного размера, открыть режим канвы, и написать в изображении необходимую букву.
Тут же необходимо обработать полученную картинку так, как мы обрабатываем исходную, чтобы эталон был максимально приближен к распознаваемой картинке и наоборот (об этом читай ниже).
Var
myarray:array of record //задаем наш массив
ch:char; //символ
bmp:TBitmap; //соответствующее ему изображение
end;
i : integer; //счетчик
Img:TBitmap; //промежуточное(буферное) изображение
im:TPicture; //то же изображение, для передачи на обработку
begin
SetLength(myarray, 73);//выделяем массиву память
im:=TPicture.Create; //создаем необходимые объекты
Img:=TBitmap.Create;
for i := 0 to 31 do
with Img.Canvas do //открываем канву
begin
Img.Height:=16; //задаем ширину и высоту
Img.Width:=16;
Brush.Color := clWhite; //чертим белый фон
Pen.Color := clWhite;
Rectangle(0,0,16,16); //используя инструмент квадрат
Pen.Color := clBlack; //ставим ручке черную краску
Font.Color := clBlack;
Font.Charset:=form1.FontDialog1.Font.Charset; //выбираем шрифт (пользователь выбирает шрифт для базы) и его параметры
Font.Size := Form1.FontDialog1.Font.Size;
Font.Style := Form1.FontDialog1.Font.Style;
Font.Name := Form1.FontDialog1.Font.Name;
TextOut(0, 0, CHR(ORD('А')+i));//пишем в нашем изображении
myarray[i].bmp:=TBitmap.Create;//создаем объект в массиве
myarray[i].ch:=CHR(ORD('А')+i);//задаем что это за символ соответственно
im.Bitmap.Assign(Img);//задаем картинке изображение
myarray[i].bmp:=PreParse2(Im);//посылаем на обработку и присваиваем выходную картинку элементу массива(описание будет немного позже
end;Ошибки
Куда же без них? Нам понадобится также метод обработки ошибок распознавания. Для этого перед распознаванием мы должны сделать специальную кнопочку, которая будет показывать символы и результат работы программы, и спрашивать нас, верно ли распознавание. Если да, то ничего не делать, иначе заносить в базу, структура которой следующая – файл-индексатор, в котором задается количество символов в базе, следующие строки – символ, и ссылка на файл с изображением (см. procedure TForm1.Learn(Pic:TPicture);).
Краткая блок-схема
Реализация
Определяем задачи и рисуем форму:
Полученный исходник тут.
Скрин работающей программы:
Что упущено или планы на будущее
— Не может программа распознавать буквы, состоящие из двух фигур: Ы, Й.
— При повороте/шумах/прочее распознавание не корректно.
— Порой распознает маленькие буквы как большие, большие как маленькие (что собственно логично для данного метода)
Вывод
Вот и написан очередной «распознаватель» текста. Кому он пригодится? Практически никому. Это не FineReader, и не Cuneiform. Тут всё намного проще и понятнее, и менее эффективно. Но, несмотря на это надеюсь, эта статья будет полезна ИТ-сообществу. Данная система может быть изменена под какие-либо другие нужды.
В недалёком будущем хочу дополнить рассказ графиками результатов распознавания, а также сравнением данного метода распознавания с другими.
В ходе написания использовались материалы:
Распознавание образов методом потенциальных функций
Распознавание почтовых индексов (взят алгоритм выделения картинки)
UPD: были проблемы с базой, решил, исходник перезалил, спасибо AmoN'у
