автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Адаптивные алгоритмы распознавания текстов

На правах рукописи

ООЗ 165658

Титов Юрий Васильевич

АДАПТИВНЫЕ АЛГОРИТМЫ РАСПОЗНАВАНИЯ ТЕКСТОВ

Специальность 05 13.01 Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2007

003165658

Работа выполнена в Институте системного анализа Российской академии наук в лаборатории 9-4 «Дискретные методы в управлении»

Научный руководитель кандидат технических наук

Славин Олег Анатольевич

Официальные оппоненты доктор технических наук, профессор

Гливенко Елена Валерьевна Российский государственный университет нефти и газа им. И М. Губкина

кандидат технических наук Соловьев Александр Владимирович Институт системного анализа РАН

Ведущая организация- Институт конструкторско-технологической

информатики РАН

Защита состоится 12 ноября 2007 года в

цЮ

часов на заседании диссертационного совета Д 002.086 02 при Институте системного анализа РАН, расположенного по адресу Москва, 117312, Проспект 60 лет Октября, д. 9

С диссертацией можно ознакомиться в библиотеке Института системного анализа РАН

Автореферат разослан « /( » октября 2007 г

Ученый секретарь диссертационного совета Д 002 086 02

дтн А И Пропой

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Для достижения поставленных целей были сформулированы и решены следующие задачи

1) исследование преобразования символов при сканировании с целью получения модели возникающих искажений,

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

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

Методы исследования. В работе используются методы теории искусственного интеллекта, теории вероятности, теории построения алгоритмов и систем

Результаты, выносимые на защиту:

• модель искажения символов при сканировании,

• использование уплотненных взвешенных растров в качестве идеальных образов в адаптивном распознавании;

• алгоритм адаптивного распознавания, использующий динамическое построение функций сравнения с эталоном

Научная новизна работы. В диссертации получены следующие новые научные результаты

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

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

• введено понятие уплотненных взвешенных растров и обоснована необходимость их применения,

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

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

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

Среди результатов исследований изложенных в диссертации — модель искажения изображений во время сканирования применительно к текстовым символам Данные результаты могут быть полезны специалистам в области распознавания

Реализация результатов. Приведенный в работе алгоритм реализован в качестве составной части программы распознавания текстов OCR Cognitive Cuneiform® В классе печатных документов среднего качества точность распознавания символов возрастает с 99 6-99 7% до 99 7-99 8%

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

Апробация работы. Результаты диссертации и материалы исследований докладывались на четырнадцатой международной конференции «Математика Компьютер Образование», Пущино, Россия, 22-27 января 2007 г

Кроме того, результаты исследований и разработки, отраженные в работе, представлялись на семинарах Института системного анализа РАН Публикации. По материалам диссертации опубликовано 4 работы (в том числе 3 публикации в ведущих рецензируемых научных изданиях, рекомендованных ВАК, 1 публикация в трудах научных конференций) и получен 1 патент

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка иллюстраций, списка литературы (50 наименований), и двух приложений. Общий объем работы составляет 115 страниц, включая 3 таблицы и 54 иллюстрации

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность работы, формулируется ее цель, научная новизна и раскрывается структура диссертации

В первой главе приведен обзор существующих признаковых и адаптивных алгоритмов распознавания текстов На примере опубликованных работ конкретных авторов рассмотрены этапы развития алгоритмов данного класса

• метод характерных фрагментов,

• адаптивное распознавание,

• штрафные функции в адаптивном распознавании

Алгоритм Бравермана, разработанный в 70-80-х годах, использует выделение характерных фрагментов, и основан на геометрии символов Локальными геометрическими особенностями считаются как особые точки на контурных линиях — изломы, пересечения, окончания, так и особые точки на границах черных или белых пятен. Процесс анализа предъявлен-

ного множества изображений начинается с выделения на них так называемых характерных фрагментов — участков изображений, содержащих локальные геометрические особенности

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

Для каждого из выделенных фрагментов строится набор характеристик его места на изображении Эти характеристики необходимы для описания взаимного расположения геометрических особенностей Аналогично словарю форм строится словарь мест

Следующий этап алгоритма Бравермана состоит в построении описаний изображений и формировании правила сравнения (распознавания) полученных описаний Основное требование, предъявляемое к этому правилу, заключается в том, чтобы с его помощью можно было бы объединять в классы (образы) такие описания, которые соответствуют изображениям, визуально похожим с человеческой точки зрения

Разработанный в 90-е года алгоритм адаптивного распознавания также использует накопление характеристик распознаваемых символов Алгоритм представляет собой двух ггроходный процесс с обучением на результатах первого прохода

Схема адаптивного распознавания разделяется на несколько этапов первичное распознавание, сбор статистики, кластеризация собранной статистики, формирование эталонов и дораспознавание

Определим каждый из названных этапов

- Первичное распознавание - это распознавание всей страницы с помощью шрифтонезависимого алгоритма

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

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

- Формирование эталонов — это создание окончательных наборов данных, по которым будет производиться дораспознавание

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

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

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

После формирования эталонов для каждого символа необходимо построить алгоритм распознавания Наиболее часто используемый прием

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

где ау и b,j - элементы матриц А и В соответственно (матрицы А и В -суть полутоновые растровые изображения размером тх п), г = 1,т , j =

Тп

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

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

По результатам ряда экспериментов и проведенных исследований описывается полученная модель искажения образа при сканировании Среди основных типов искажений выделяются следующие • дефокусировка («размазываение»),

• розовый шум

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

х2+ 2

/(х, у) =

Функция образа g(x,y) для черно-белого изображения равна 1, если образ в данной точке (х,у) черный, и равна 0 в противном случае Для произвольного серого изображения ё(х,у) в точке (х,у) принимает значение полутона исходного оригинала в пикселе с координатами (х,у) Параметры А и а задают характер дофокусировки и зависят от конкретной модели сканера

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

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

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

В третьей главе предлагаются решения для поставленных во второй главе двух основных задач адаптивного распознавания

1) формирования идеальных образов,

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

Возможность адаптации (на результатах первого прохода распознавания) является существенным фактором для построения идеального образа для каждой группы

Идеальные образы - это объекты, обладающие свойством наименьшей средней близости со всеми элементами рассматриваемого множества образов в смысле некоторой определенной функции близости

Рассмотрим растры Щт, п) = II гу где ширина т и высота п — размеры растра, г = 1, т , _/ = 1,п , г,; — значение растра в точке (г, /) Для полутоновых изображений значение растра принимает целочисленные значения от 0 до максимальной интенсивности О (обычно Э равно 255), а для бинарных изображений - равно 0 или в Назовем точкой растра (или пикселем) Щт, п), пару чисел («, ]), где г иу - значения индексов элемента ги

Для множества Б(а) растров одноименных символов а идеальный образ определяется как растр Я^еа1(т,п), на котором достигается минимум выражения

1 м

— £ «"л

N кИ

где N — количество элементов в множестве Б(а), а Л* е $(а). Минимум ищется по всевозможным растрам Щт, п), необязательно из множества Б (а) Функция близости ц зависит от конкретного выбранного алгоритма вычисления расстояния между двумя растрами

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

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

Два растра и К2(т2,П2) будем называть равновеликими, если

т1=т2 и и/=«2 Пусть 5 - произвольное множество N равновеликих растров

5 = {В.к(т,п)} = /1| г,® где к=йК', г =\,т иу = 1,и Тогда взвешенным растром для множества 5 назовем растр Щт, п) = |\гу\| такой, что

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

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

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

1) среднее арифметическое по всем точкам (г, ]) взвешенного растра, отличных от в

1 п гп

м(Я) = —-—У У (о-о

п т

где Уг(11) = ^]Г ^) > а Щ) - индикаторная функция - равна 1 при

1=1 7=1

значении аргумента менее в, и 0 в противном случае,

2) альтернативная мера - нормированная поточечная сумма модулей разности плотностей взвешенного растра и его бинаризации-

Ь . = 1 У = 1

Рассматриваются достоинства и недостатки функций М(Я) и В (Я) Результат - уплотненные взвешенные растры в среднем на 5—10% уложены более плотно

Также в третьей главе изучен вопрос о вероятности отличия бинари-зованых отсканированных символов от оригинальных бинарных образов Выводится формула для вероятности Р(Т) отклонения ровно на Т единиц

{¡>1,г>2 Мелу »=о

где Ь¡, ,Ъа - решение в неотрицательных целых числах уравнения Ь/ + Ь2+ + Ъа=Т, при ограничениях Ь,< а,, ^-множество этих решений, а, - количество пикселей интенсивности X в растре

В дальнейшем рассматриваются различные функции сравнения двух растров, анализируются их недостатки, а затем обосновывается необходимость использования специальной функции сравнения двух альтернатив В итоге предлагается алгоритм построения функции для сравнения распознаваемого символа с идеальными образами символов Б, из соответствующей коллекции альтернатив X = {(Sj.Pi), , (Б^Р^} Данное сравнение на втором проходе адаптивного распознавания применяется

при пересчете оценок Р, только для плохо распознанных на первом проходе символов, то есть получивших низкие оценки Р, для всех Я,, или наибольшие оценки которых Р/ и Р2 примерно равны

Как правило, в указанной ситуации реальное отличие символов сосредоточено в небольшой области или объединении нескольких областей, относительный вклад которых в общую площадь, занимаемую символами, невелик. Предполагается также, что существует контроль того, что взвешенные растры формируются из хорошо распознанных символов. Итак, для распознаваемого растра Я имеется коллекция альтернатив X, для каждого символа Я, которой построен идеальный образ 5, Без ограничения

общности можно считать, что 5, равновелики с Я Приведем общую схему алгоритма

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

2) В найденном наилучшем положении, если это необходимо, растры 5, приводятся к одинаковому (расширенному) размеру

3) Строится матрица М' = ||/Ид[|, каждый элемент которой равен максимальной разности соответствующих элементов растров 5,

т'к = тах(5,0, к)) - тш(5,0, к)) * 1 »

где - значение растра в точке (¡,к)

4) Вторая матрица А/=||»гд|| заполняется штрафными коэффициентами В каждом пикселе штраф вычисляется как неубывающая функция /(х) от значения соответствующего элемента М', т е т^ =/(т')).

5) Ищется наилучшее положение растра Я на каждом 51, (при этом используется интегральная метрика)

6) В найденном в пункте 5) положении для каждого 5, вычисляется штраф за несовпадение с растром Я В пикселе с координатами (],к) штраф определяется как произведение т1к х|5,0Д)~>>| соответствующего элемента штрафной матрицы М и модуля разности значений растра Я и идеального образа Я, (М жестко зафиксирована по отношению к ) Считается сумма штрафов по всем пикселям рас-

7) Из множества альтернатив 5, результатом распознавания считается

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

где а - параметр, подбираемый при обучении Цель функции /(х) -усилить влияние существенных точек на величину штрафа при сравнении распознаваемого символа Л с идеальными образами 5,

В четвертой главе предложена схема распознавания, использующая динамический подбор по обучающей выборке оптимального значения параметра а в функции/(х) Блок-схема модернизированного алгоритма приведена на Рисунке 1

т п

тот символ, для идеального образа которого в пункте 5) получен

0,х < а (х - а), х > а '

Рисунок 1. Блок-схема адаптивного алгоритма использующего уплотненные

взвешенные растры

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

Кроме того, в четвертой главе описываются программные компоненты, с помощью которых проводились исследования взвешенных растров (кластеров) и тестировались различные алгоритмы распознавания

Сравнение количества ошибок

номер теста

-Альтернативная -Спец Функция - Интегральная

9 10

Рисунок 2. Различные функции сравнения В заключении изложены основные результаты и выводы по диссертационной работе

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1 На основе экспериментальных данных и теоретических расчетов построена модель рассеивания образа при сканировании для непрерывного случая

2 Предложена модель для расчета вероятности возникновения ошибки заданной величины при сканировании бинарного образа с последующей бинаризацией

3 Предложено использовать уплотненные взвешенные растры в качестве идеальных образов

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

5 С помощью разработанного алгоритма поиска характерных фрагментов была существенно улучшена схема адаптивного распознавания с дообучением Приведенный в работе алгоритм реализован в качестве

составной части программы распознавания текстов OCR Cognitive

Cuneiform®

В приложении 1 изложены общие закономерности формирования функции распределения полутонов в отсканированном изображении символа в зависимости от геометрии последнего

В приложении 2 приведен характерный пример уплотненных взвешенных растров, иллюстрирующий их качественное отличие от обычных взвешенных растров

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Титов Ю В Об искажении символов при сканировании // Сб тр ИСА РАН «Системный подход к управлению информацией», 2006 — С 260-288

2. Титов Ю В О восстановлении идеального прообраза по коллекции образов // Сб тр. ИСА РАН «Системный подход к управлению информацией», Москва URSS, 2006 — С 252-259

3 Титов Ю В Модель искажения полутоновых изображений при сканировании // 14 конференция «Математика Компьютер Образование» Тезисы Москва Ижевск, 2007 — С 103

4 Славин О А Титов Ю В Динамическое построение функций сравнения с идеальным образом в задаче адаптивного распознавания текстовых символов // Информационные технологии и вычислительные системы № 1, 2007 —С 3-12

5 Романов А Н, Славин О А, Титов Ю В Система адаптивного распознавания символов Патент на полезную модель РФ № 63571, опублик 27 05 2007, Бюл № 15

Подписано в печать 11 10 2007 г Исполнено 11 10 2007 г Печать трафаретная

Заказ № 872 Тираж 100 экз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш , 36 (495) 975-78-56 www autoreferat ru

ВВЕДЕНИЕ.

ГЛАВА 1 «ОБЗОР ПРИЗНАКОВЫХ И АДАПТИВНЫХ АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТОВ».

1.1 вступление.

1.2 Метод характерных фрагментов.

1.2.1 Описание двухградационных изображений.

1.2.2 Алгоритмы выделения характерных фрагментов.

1.2.3 Векторы, задающих форму характерных фрагментов.

1.2.4 Векторы, задающие местоположение характерных фрагментов.

1.3 Адаптивное распознавание.

1.3.1 Общая схема адаптивного распознавания.

1.3.2 Создание эталонов.

1.3.3 Дораспознавание.

1.4 Штрафные функции.

1.5 Выводы.

ГЛАВА 2 «МЕТОДЫ И ПРОБЛЕМЫ АДАПТИВНОГО РАСПОЗНАВАНИЯ ОТСКАНИРОВАННОГО ТЕКСТА».

2.1 Основные задачи адаптивного распознавания.

2.1.1 Построение идеального образа.

2.1.2 Сравнение символа с эталоном.

2.2 Искажение символов при сканировании.

2.2.1 Определения.

2.2.2 Представление символа.

2.2.3 Влияние аппаратной функции.

2.2.4 Размеры прообраза.

2.2.5 Тонкие линии.

2.2.6 Наклонные линии на сетке.

2.2.7 Распределение полутонов. Количественные характеристики.

2.3 выводы.

ГЛАВА 3 «ФУНКЦИИ СРАВНЕНИЯ С ИДЕАЛЬНЫМ ОБРАЗОМ В АДАПТИВНОМ РАСПОЗНАВАНИИ»

3.1 Построение идеальных образов.

3.2 Уплотненные взвешенные растры.

3.2.1 Простейший случай укладки взвешенного растра.

3.2.2 Мера плотности укладки взвеш енных растров.

3.2.3 Укладка сложных растров.

3.3 Отличие символов от идеальных образов.

3.4 Стандартные функции сравнения - основные недостатки.

3.5 Алгоритм построения специальной функции сравнения.

3.6 Выводы.

ГЛАВА 4 «РЕАЛИЗАЦИЯ АДАПТИВНОГО АЛГОРИТМА».

4.1 Подбор параметров при обучении.

4.2 Инструментарий исследователя.

4.2.1 Компонента кластеризации.

4.2.2 Компонента просмотра и редактирования кластеров.

4.3 Полная схема алгоритма распознавания.

4.4 Выводы.

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

Во всех системах электронного документооборота и системах ввода печатных текстов одним из ключевых этапов является этап распознавания текстовых символов - перевод информации из графической формы - результата сканирования - в текстовую форму. Несмотря на многолетнюю историю развития алгоритмов распознавания [7, 11, 15, 21, 33, 37, 40] и существование большого количества алгоритмов хорошо распознающих четко напечатанные тексты, задача распознавания в более сложных случаях далека от решения. Деловой мир и все отрасли экономики ставят задачу дальнейшего увеличения точности распознавания, включая, в том числе, распознавание документов низкого качества. В частности, существующие алгоритмы обеспечивают относительно невысокую по сравнению с человеком-оператором точность распознавания текстов с графических изображений, полученных сканированием с малыми разрешениями. Среди прочего стоит отметить класс задач, в которых имеющееся графическое изображение невозможно улучшить путем увеличения разрешения сканирования или изменением параметров сканирования. К таким задачам относятся уже созданные ранее электронные архивы документов в виде растровых изображений, электронные библиотеки, факсимильные сообщения и пр.

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

Одной из распространенных схем распознавания текстов показавшей высокую точность является адаптивное распознавание - шрифтонезависи-мый алгоритм, использующий особенности распознаваемых символов. Данный алгоритм является представителем класса алгоритмов основанных на сравнении с эталоном. Одним из ключевых моментов любого алгоритма распознавания этого класса является используемая функция сравнения (мера близости [25], функция правдоподобия [14], функция расстояния [30]) - с помощью которой и происходит определение принадлежности распознаваемого символа к одному из классов.

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

Целями диссертации являются:

1) исследование преобразования символов при сканировании с целью получения точной картины возникающих искажений;

2) разработка улучшенных алгоритмов построения идеального образа распознаваемого символа - эталона;

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

Научная новизна работы состоит в следующем:

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

• проведено исследование искажений образов при сканировании и предложена модель для расчета вероятности возникновения ошибки заданной величины при сканировании бинарного образа с последующей бинаризацией;

• введено понятие уплотненных взвешенных растров и обоснована необходимость их применения;

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

Содержание диссертации организовано в соответствии с указанными выше целями.

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

Рассмотрены алгоритмы, разработанные в 70-80-х годах использующих выделение характерных фрагментов, основанные на геометрии символов.

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

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

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

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

Описана модель искажения образа при сканировании.

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

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

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

В четвертой главе описаны особенности реализации алгоритма сравнения символов с идеальными образами и его внедрение в программу распознавания текста OCR Cognitive Cuneiform®. Описаны использованные программные компоненты, созданные специально для исследования алгоритмов распознавания. Протестировано обучение при подборе параметров в функции близости, предложенной в третьей главе.

По теме диссертации опубликовано 4 работы, одна из них в соавторстве; зарегистрирован патент на полезную модель.

Выводы и заключение

Основные теоретические и практические результаты работы заключаются в следующем:

1. На основе экспериментальных данных и теоретических расчетов построена модель рассеивания образа при сканировании для непрерывного случая.

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

3. Предложено использовать уплотненные взвешенные растры в качестве идеальных образов.

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

5. С помощью разработанного алгоритма поиска характерных фрагментов была существенно улучшена схема адаптивного распознавания с дообучением. Приведенный в работе алгоритм реализован в качестве составной части программы распознавания текстов OCR Cognitive Cuneiform®.

1. Ануфриев И. MATLAB 7.0 Наиболее полное руководство - БХВ-Петербург, 2005 г. 1104 стр.

2. Арлазаров В.В. Структурирование визуальных представлений информационной среды и методы определения надежности распознавания: дис. канд. тех. наук М., 2004. 120 с.

3. Арлазаров B.J7., Котович Н.В., Славин O.A. Адаптивное распознавание // Информационные технологии и вычислительные системы № 4, 2002. С. 11-22

4. Арлазаров B.JL, Котович Н.В., Троянкер В.В. Адаптивное распознавание символов // Сб. трудов ИСА РАН "Интеллектуальные технологии ввода и обработки информации", 1998

5. Арлазаров В.Л., Логинов A.C., Славин O.A. Характеристики программ оптического распознавания текста// Программирование № 3, 2002. С. 45-63

6. Арлазаров В.Л., Славин O.A. Алгоритмы распознавания и технологии ввода текстов в ЭВМ. // Информационные технологии и вычислительные системы 1996. № 1. С. 48-54

7. Бонгард ММ Проблема узнавания. М.: Наука. 1967.

8. Браверман Э.М., Мучник И.Б. Структурные методы обработки эмпирических данных. М.: Наука. 1983.- 464 с.

9. Гинзбург А., Милчев М., Солоницын Ю. Периферийные устройства. Принтеры, сканеры, цифровые камеры Питер 2001.-448 стр.

10. Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MATLAB Техносфера, 2006 г. - 616 стр.11 .Дуда Р., Харт П. Распознавание образов и анализ сцен./ Пер. с анг. М.: Мир, 1976.-511 с.

11. Дьяконов В. Maple 8 в математике, физике и образовании Солон-Пресс, 2003 г. 656 стр.

12. Завалишин Н.В., Мучник И.Б. Модели зрительного восприятия и алгоритмы анализа изображений. М.: Наука, 1974.

13. Ковалевский В.А. Методы оптимальных решений в распознавании изображений. М.: Наука, 1976 г. - 328 стр.

14. Ковалевский В.А. Современное состояние проблемы распознавания образов. Кибернетика, №5, 1967

15. Мисюрёв A.B. Использование искусственных нейронных сетей для распознавания рукопечатных символов. // Сб. трудов ИСА РАН "Интеллектуальные технологии ввода и обработки информации", 1998, С.122-127

16. Мучник КБ. Формирование языка описания зрительных образов. // В сб. под ред. Э.М.Бравермана «Автоматический анализ сложных изображений»,— М.: Мир, 1969

17. Постное КА. Лекции по Общей Астрофизике для Физиков, курс лекций 2001 г., физический факультет МГУ // http://www.astronet.ru/db/msg/1170612/31ec/node5. html

18. Потемкин В. Г. Вычисления в среде MATLAB Диалог-МИФИ, 2004 г. 720 стр.

19. Роджерс Д. Алгоритмические основы машинной графики. — М.: Мир, 1989. —512 стр.

20. Розенфелъд А. Распознавание и обработка изображений. — М.: Мир, 1972.

21. Славин O.A. Комбинированные методы распознавания печатных и рукопечатных символов. // Сб. трудов ИСА РАН "Документооборот. Концепции и инструментарий", 2004, С. 151-173

22. Славин O.A. Распознавание атрибутов текстовых символов. // Сб. трудов ИСА РАН "Документооборот. Концепции и инструментарий", 2004, С. 142-150

23. Славин O.A. Средства управления базами графических образов символов и их место в системе распознавания // Сборник трудов ИСА РАН «Развитие безбумажных технологий в организациях», 1999, с. 317-330

24. Славин О.А., Подрабинович А.А. Древовидное распознавание нормализованных символов // Сборник трудов ИСА РАН «Интеллектуальные технологии ввода и обработки информации», 1998, с. 137-156.

25. Славин О.А. Титов Ю.В. Динамическое построение функций сравнения с идеальным образом в задаче адаптивного распознавания текстовых символов. // Информационные технологии и вычислительные системы 2007. № 1.С. 3-12

26. Степаненко О.С. Сканеры и сканирование. Краткое руководство, Диалектика, 2004 г. 288 стр.

27. Титов Ю.В. Об искажении символов при сканировании // Сб. тр. ИСА РАН «Системный подход к управлению информацией», 2006. С. 260288.

28. Титов Ю. В. О восстановлении идеального прообраза по коллекции образов // Сб. тр. ИСА РАН «Системный подход к управлению информацией», Москва: URSS, 2006. С. 252-259.

29. Дж.Ту, Р.Гонсалес Принципы распознавания образов Мир, 1978, -414 стр.

30. Шарыгин М. Е. Сканеры и цифровые камеры, BHV Санкт - Петербург, Арлит 2000, - 384 стр.

31. Breuel Т. М. An Algorithm for Finding Maximal Whitespace Rectangles at Arbitrary Orientations for Document Layout Analysis. Proceedings of the Seventh International Conference on Document Analysis and Recognition (ICDAR'03), NJ, USA, 2003. P. 66-71

32. Cooper D.B., Cooper P.W., Non-supervised Adaptive Signal Detection and Pattern Recognition. Information and Control, vol. 7, Sept., 1969

33. Dias A.P. Minimum Spanning Trees for Text Segmentation // In Proc. of the Fifth Annual Symposium on Document Analysis and Information Retrieval, Las Vegas, Nevada, 1995. P. 61-65.

34. O'Gorman L. The Document Spectrum for Page Layout Analysis // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993. V. 15. №11. P. 1162-1173

35. Green E., Krishnamoorthy M. Model-based analysis of printed tables // In Proceedings of International Conference on Document Analysis and Recognition (ICDAR), 1995. P. 214-217.

36. Haung T., Fu K.S., Stochastic Syntactic Analysis for Programmed Grammars and Syntactic Pattern Recognition, vol 1, №3, 1972

37. Ittner D. Automatic Inference of Textline Orientation // In Proc. of the Second Annual Symposium on Document Analysis and Information Retrieval, Las Vegas, Nevada, 1993. P. 123-133

38. Kise K., Yanagida O., Takamatsu S. Page Segmentation Base on Thinning of Background // In Proc. of the 13th International Conference on Pattern Recognition, page 788-792, Vienna, Austria, August 1996. P. 788-792

39. Kovalevsky V.A. Present and Future of Pattern Recognition Theory, Proceeding of IFIP Congress 65, Spartan Books, Washington D.C. 1965

40. Lebourgeois F., Henry J.L. An Evolutive OCR System Based on Continuous Learning // Proceedings of the 3rd IEEE Workshop on Applications of Computer Vision (WACV '96), December 1996. P. 272-277

41. Sawaki M., Hagita N., Ishii K. Robust Character Recognition of Gray-Scaled Images with Graphical Designs and Noise // Proceedings of Fourth International Conference Document Analysis and Recognition (ICDAR'97), 1997. P. 491-494.

42. Trier 0. D., Taxt T. Evaluation of Binarization Methods for Document Images // IEEE Transactions on pattern analysis and machine intelligence, vol. 17, No 3, March 1995. P. 312-315

43. Tubbs К. M, Embley D. W. Recognizing records from the extracted cells of microfilm tables // In Proceedings of the 2002 ACM Symposium on Document Engineering, ACM Press, New York, NY, 2002. P. 149-156.

44. Zlatopolsky A.A. Automated document segmentation // Pattern Recognition Letters, July 1994. V. 15. №7. P. 699-704.

45. CR CuneiForm система оптического распознавания текстов. // http://www.cuneiform.ru/

46. Система оптического распознавания текстов CuneiForm // http://www.cognitive.ru/products/cuneiform.htm

47. Пакет компьютерной алгебры Maple официальный сайт // http://www.maplesoft.com/

48. Пакет математического моделирования MATLAB официальный сайт // http ://www. mathworks. com/products/matlab/