Содержание к диссертации
Введение
Глава 1. Анализ методов и систем обработки и распознавания рукописных символов и текста 8
1.1 Классификация существующих методов обработки изображений рукописных документов 8
1.1.1 Предварительная обработка изображений 8
1.1.2 Сегментация изображений рукописных документов 19
1.2 Сравнительный анализ подходов к распознаванию рукописных символов и текста 23
1.2.1 Распознавание рукописных символов в пассивном режиме 23
1.2.2 Распознавание рукописного текста 25
1.3 Анализ существующих систем распознавания рукописных символов и текста 31
1.4 Выводы по главе 39
Глава 2. Построение моделей сегментации и распознавания рукописных символов и текста в пассивном режиме 42
2.1 Метод обнаружения информативных зон на изображении 43
2.2 Метод сегментации изображений текстовых зон на отдельные символы 48
2.3 Векторный подход к распознаванию рукописных символов 52
2.3.1 Построение векторной модели 52
2.3.2 Преобразование векторной модели к инвариантному виду 56
2.3.3 Распознавание рукописных символов на основе инвариантной векторной модели 58
2.4 Метод распознавания рукописного текста с использованием вероятностного подхода на основе лингвистической модели слова 61
2.4.1 Разработка лингвистической модели слова 61
2.4.2 Адаптивное построение дерева решений на основе вероятностного подхода 62
2.5 Выводы по главе 64
Глава 3. Построение экспериментальной комплексной системы распознавания рукописного текста 66
3.1 Структурная схема комплекса по распознаванию рукописного текста 66
3.2 Описание основных модулей системы 68
3.3 Результаты экспериментальных исследований 75
3.4 Программа «Модуль ввода данных» 79
3.5 Выводы по главе 83
Заключение 85
Библиографический список 89
Приложение 105
- Предварительная обработка изображений
- Метод обнаружения информативных зон на изображении
- Адаптивное построение дерева решений на основе вероятностного подхода
- Программа «Модуль ввода данных»
Введение к работе
Актуальность работы. Входной информацией в системах электронного документооборота могут быть не только документы с печатным текстом, но и рукописные документы (документация паспортно-визовой службы, анкетирование, прием заявлений от населения). Также имеется большое количество унаследованных рукописных документов, содержащих важную техническую информацию, которые желательно перевести в электронный вид.
Несмотря на то, что задачей распознавания рукописных символов исследователи начали заниматься с 70-х гг. XX в. (Ковалевский В.А., Рыбак В.И., Фукунага К. и др.), до сих пор имеются как теоретические, так и практические проблемы, связанные с большим многообразием написания отдельных рукописных символов и текста. В настоящее время наиболее активные разработки в данном направлении проводятся университетами State University of New York at Buffalo, University of Massachusetts Amherst (США), Concordia University (Канада), Univesite de Monreal (Франция), Московский государственный университет, Московский физико-технический институт (Государственный университет)
(РФ).
Известны два основных подхода к распознаванию рукописного текста: распознавание в режиме текущего ввода символов и распознавание ранее написанных документов. Первый подход используется в системах реального времени, к которым относятся системы сенсорного ввода рукописных символов. Входными данными являются траектории указывающего устройства (стилус, перо и т.д.). Системы, решающие задачу в рамках второго подхода, имеют невысокую точность распознавания (около 70-75%), требуют настройки на конкретный почерк и стиль написания. Данные системы используются при вводе информации с бумажных носителей. Входными данными в этом случае являются изображения, полученные со сканера или других цифровых устройств. Разработка методов и алгоритмов распознавания ранее написанного рукописного текста позволит повысить эффективность работы таких систем. Таким образом, задача обработки и распознавания рукописного текста является актуальной и востребованной в различных сферах деятельности.
Целью диссертационной работы является усовершенствование методов и алгоритмов обработки и распознавания рукописного текста в системах электронного документооборота, представленного в виде изображений текстовых документов.
Поставленная цель определила необходимость решения следующих задач:
1. Провести анализ подходов для построения систем обработки изображений текстовых документов, методов сегментации изображений на информативные текстовые зоны, а также методов распознавания отдельных рукописных символов и рукописного текста.
Усовершенствовать методы и алгоритмы сегментации изображений на текстовые зоны, содержащие рукописные слова, а также сегментации текстовых зон на отдельные символы.
Модифицировать методы и алгоритмы распознавания рукописных символов и текста на основе векторного подхода.
На основе предложенных методов и алгоритмов создать программные модули для реализации системы обработки и распознавания рукописных символов и текста, представленных в виде изображений.
Разработать экспериментальную систему распознавания для оценки эффективности предложенных алгоритмов при решении различных задач распознавания, основанных на контурной информации об объектах.
Методы исследования. При выполнении диссертационной работы использовались методы теории информации, теория обработки сигналов, теория распознавания образов, теория математической морфологии, методы аналитической геометрии, методы объектно-ориентированного программирования.
Научная новизна диссертационной работы состоит в следующем:
Усовершенствован метод сегментации изображений, содержащих рукописный текст, на отдельные текстовые зоны (строки и слова) на основе операций морфологической обработки и на отдельные символы с использованием процедуры адаптивной подстройки выделяющей ячейки и усиления ядра символов. Это позволило сократить количество ложных сегментаций и увеличило точность сегментации на 5-7%.
Предложена векторная модель описания внешнего контура изображений рукописных символов, основанная на нахождении опорных точек с применением модифицированного фильтра Робертса, а также алгоритм построения модели на основе процедур уплотнения и нормализации параметров векторного представления. Данные процедуры позволили получить векторное описание, инвариантное к преобразованиям аффинной группы (масштабирование, сдвиги, поворот).
Разработаны алгоритмы распознавания рукописных символов, использующий базу эталонных векторных описаний с обучением и без обучения на конкретный почерк, и распознавания текста с использованием тематических электронных словарей, что обеспечивает повышение точности распознавания в среднем на 5-9%.
Практическая значимость. Предложенные в диссертационной работе методы и алгоритмы предназначены для практического применения в системах документооборота предприятий, анкетирования населения, паспортно-визовой службы и других систем, где входными данными являются изображения текста, написанного от руки. На основе диссертационных исследований разработана библиотека компонентов для создания систем обработки и распознавания изображений рукописного текста.
Реализация результатов работы. Разработанная программа «Система векторизации и распознавания внешнего контура изображений рукописных
символов (Vectoryzator)» зарегистрирована в Российском реестре программ для ЭВМ г. Москва, 7 июня 2007 г. (свидетельство №2007612407), а также программа «Сегментация изображений рукописного текста (SegPic)» зарегистрирована в Российском реестре программ для ЭВМ г. Москва, 5 сентября 2008 г. (свидетельство №2008614243).
Разработанные алгоритмы и программное обеспечение используются в учебном процессе при проведении занятий по дисциплинам «Интеллектуальная обработка данных», «Теоретические основы цифровой обработки изображений» в Сибирском государственном аэрокосмическом университете им. академика М. Ф. Решетнева (СибГАУ), а также в программном комплексе по обработке результатов социологических исследований «Социорасчет» социологической лаборатории Центра общественных связей СибГАУ.
Основные положения, выносимые на защиту:
Метод сегментации изображений рукописного текста на отдельные текстовые зоны и символы на основе морфологической обработки и процедуры адаптивной подстройки выделяющей ячейки.
Векторная модель описания внешнего контура изображений рукописных символов, основанная на нахождении опорных точек, а также алгоритм построения данной модели.
Алгоритм распознавания рукописных символов и текста на основе векторного подхода с использованием тематических словарей.
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 10-й международной конференции и выставке «Цифровая обработка сигналов и ее применение» (Москва 2008), IX международной научно-технической конференции «Кибернетика и высокие технологии XXI века» (Воронеж 2008), всероссийской конференции «Модели и методы обработки изображений» (Красноярск 2007г.), всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Решет-невские чтения» (Красноярск 2004, 2005, 2006, 2007 гг.), всероссийской научной конференции студентов, аспирантов и молодых ученых «Наука. Технологии. Инновации» (Новосибирск 2004 г.), региональном смотре-конкурсе программных проектов «5'оД-Парад-2007» (Красноярск 2007 г.), всероссийской конференции творческой молодежи, посвященной дню космонавтики «Актуальные проблемы авиации и космонавтики» (Красноярск 2005, 2006, 2007 гг.), студенческом семинаре Летней школы компании «Интел» (Москва, Нижний Новгород 2008г.), а также на научных семинарах лаборатории систем цифровой обработки изображений СибГАУ.
Публикации. По результатам диссертационного исследования опубликовано 18 печатных работ, из них 4 статьи, 12 докладов, 2 свидетельства, зарегистрированных в Российском реестре программ для ЭВМ.
Структура работы. Работа состоит из введения, трех глав, заключения, списка литературы и приложения.
Предварительная обработка изображений
При решении задачи распознавания рукописных символов и текста важным этапом является предварительная обработка изображений документов, которая включает процедуры бинаризации, выделения границ, построение скелета изображения, а также морфологические методы расширения и сжатия [32, 34, 37, 45, 47, 66, 111]. Известны ряд методов приведения изображения к бинарному виду, а именно, метод пороговой бинаризации, метод бинаризации по площади, метод преобразования на основе анализа гистограммы распределения яркости элементов изображения [46, 53-55, 65].
В случае использования двух первых методов для каждого элемента изображения, являющегося центром некоторой окрестности, вычисляется среднее и дисперсия по этой окрестности. В процессе пороговой бинаризации присвоение значения выходному элементу выполняется по формуле
Для бинаризации изображений также может использоваться преобразование на основе анализа гистограммы распределения яркости исходных элементов. Вначале выполняется построение гистограммы яркости элементов изображения, затем анализируется ее форма. Если в результате анализа выявлена двухмодальная форма гистограммы, то значение локального минимума выбирается в качестве порогового значения. Затем выполняется бинарное преобразование исходной матрицы данных аналогично бинаризации по площади (при этом в качестве среднего принимается найденное пороговое значение, а дисперсия полагается равной нулю). Если же гистограмма не имеет двухмодальную форму, то в этом случае на гистограмме выполняется поиск точки, в которой от начала гистограммы до этой точки сосредоточено значительное количество элементов исходного изображения. Значение этой точки принимается в качестве порога бинарного преобразования, затем выполняется преобразование, как и в предыдущем случае. По окончании работы алгоритма выходная последовательность будет состоять только из нулей и единиц. Для выделения границ на изображении могут применяться различные фильтры, среди которых наиболее простыми по реализации являются методы Робертса и Собела [9, 55]. Метод Робертса работает с двумерным окном 2x2 следующего вида
Выделение границ в ряде случаев позволяет осуществить поиск символов на изображении, а также осуществить построение внешнего контура. При этом возможны и комбинации этих методов, что позволяет получить определенные преимущества, однако усложняет процедуры и требует больше машинного времени.
Морфологические методы предварительной обработки позволяют восстанавливать изображения, имеющие разрывы, и тем самым повышать качество распознавания [46, 85]. Для сглаживания бинарных растровых изображений и удаления отдельных дефектов используются базовые операторы математической морфологии - сжатия и расширения (см. рис. 1.3), а также их комбинации [9].
Последовательное применение операций сжатия и расширения приводит к сглаживанию бинарных изображений. Результат обработки существенно зависит от двух факторов: конфигурации структурирующего элемента и его размера. Выбор конфигурации является скорее эмпирическим и интуитивным процессом. Операции сжатия и расширения должны использовать один и тот же размер структурирующего элемента, в противном случае толщина линий объекта изменится по окончании процесса обработки. Однако корректный выбор размера структурирующего элемента для конкретного изображения или его отдельных частей является оптимизационной задачей, решение которой зависит от ряда факторов. Во-первых, желательно освободить изображение от дефектов настолько, насколько методы математической морфологии позволяют в принципе. Во-вторых, одним из основных условий является сохранение топологии интересующего объекта. В-третьих, время обработки должно быть достаточно малым в случае использования метода для интерактивных систем распознавания рукописного текста [32].
Во многих методах распознавания одним из ключевых моментов при предварительной обработке изображений рукописных символов является построение скелета изображения. Это связано с тем, что множество методов распознавания используют скелет изображения в качестве базовой характеристики. Наиболее простой метод построения скелета заключается в том, что на изображении удаляются последовательно слои пикселей [109, 121]. Рассмотрим данный алгоритм. В каждой компоненте для каждого внешнего и каждого внутреннего контура находятся исходные левые верхние точки. Далее шаг за шагом удаляется один слой точек. Для очередной точки контура рассматривается конфигурация восьми соседних точек. Точка удаляется, если она не является концевой (т. е. не лежит на начальном или концевом интервале прямой или поворотной линии) и если после ее удаления восемь ее соседей будут по-прежнему образовывать связное множество. За один проход снятие одного слоя точек проводится для каждой компоненты поочередно для каждого внешнего и внутреннего контура. Процедура повторяется до тех пор, пока не останутся только неудаляемые точки (см. рис. 1.4). Для ускорения получения скелетного представления применяется ряд технических приемов таких, как получение сведений о возможности удаления точки и о последующей точке перехода по границе с использованием предварительно подготовленных таблиц, а не с помощью вычисления нужных величин. Наибольшее преимущество этих алгоритмов заключается в равномерности удаления слоев, таким образом, что скелет будет проходить по «центру» толстой линии. Существенный недостаток таких алгоритмов состоит в низкой производительности и сильной зависимости от искажений контуров. Также на обработку одного пикселя влияет конфигурация его окрестности. Для классического алгоритма используется окрестность 3x3 пикселей, для иных алгоритмов она может быть больше.
Метод обнаружения информативных зон на изображении
При распознавании рукописных символов на изображениях важную роль занимает обнаружение зон, содержащих рукописные знаки. Для обнаружения таких зон очень часто используют метод гистограмм. Для этого изображение последовательно сканируют построчно, суммируя при этом количество пикселей в строке, далее на основе полученных результатов строят гистограмму. Затем производится анализ гистограммы на максимумы и минимумы. Максимальное значение показывает вероятное расположение строки, содержащей символы. Данный подход эффективен в случае, если строки расположены горизонтально. Когда строки расположены не горизонтально, необходимо многократное сканирование в различных направлениях и выбор такого направления, который обеспечивает максимально выраженные максимумы и минимумы на полученной гистограмме. Это накладывает существенные вычислительные ограничения и требует больших ресурсов машинного времени и памяти. В диссертационной работе предлагается модифицированный метод, основанный на обнаружении текстовых зон при помощи морфологической обработки с последующим обнаружением связанных областей, кроме того, метод позволяет определить ориентацию входного изображения, что существенно упрощает процедуру распознавания и тем самым увеличивает эффективность системы распознавания.
В общем случае модель определения текстовых зон на изображении (I этап) можно выразить следующей формулой [12]: где Orirz - оператор предварительной нормализации текстовых зон; Om-rz — оператор морфологической обработки; OCTZ — оператор категоризации символов; OSTZ оператор нахождения специальных символов.
Таким образом, модифицированный метод обнаружения можно разделить на следующие этапы [19, 20]:
— предварительная обработка (устранение шумов, бинаризация);
— морфологическая обработка (операции расширения и сжатия);
— обнаружение связанных областей и построение текстовых зон;
— определение угла поворота текстовых зон относительно горизонтального направления.
На этапе предварительной обработки для устранения помех на изображении применяются различные методы фильтрации. Наиболее простыми являются сглаживающие фильтры: линейный и медианный [54]. Поскольку изображение с рукописными символами чаще всего представляет собой двухцветное изображение, то целесообразно преобразовать его к бинарному виду методом пороговой бинаризации. В качестве порога можно использовать среднее значение яркости пикселей изображения. Существуют более сложные схемы выбора порога [9]. Однако, поскольку в данном случае интерес представляет лишь контурная информация, их применение является нецелесообразным. При пороговой бинаризации присвоение значения выходному элементу выполняется по формуле: где A(iJ) — значение яркости элемента исходного изображения; Q(iJ) — значение бинарного изображения; Р — значение порога.
На этапе морфологической обработки осуществляется последовательное применение операции расширения и сжатия [16]. В морфологических алгоритмах участвуют цифровые изображения, заданные функциями fixy) и Ь(ху), где ДхУ) - исходное изображение, а Ь(х у) -изображение примитива. Тогда операция расширения f по b определяется как: где DfttDb — области определений изображений/и Ъ соответственно, s и t — сдвиги координат по осям X и Y.
Аналогичным образом определяется операция сжатия/по Ь\ где DfHDb — области определений изображений/и b соответственно, s и t — сдвиги координат по осям X и Y.
В качестве примитивов в операции расширения используются маски апертурой 3x5, 3x7 и выше (в зависимости от средней высоты рукописных символов), в результате чего контуры близко стоящих символов будут связаны в общий контур текстовой зоны. Далее применяется операция сжатия для сглаживания внешних краев связанных областей. В качестве примитива используется маска апертурой 3x3. Данные операции могут осуществляться последовательно несколько раз для более эффективного слияния в общие области (выбираются эмпирическим путем для соответствующих примитивов операций) (см. рис. 2.1 б). Исследование показывает, что для маски апертурой 3 5 необходимо в среднем выполнить 3 операции расширения и сжатия, а для маски апертурой 3x7 достаточно 1-2 операции расширения и сжатия. После этого осуществляется маркировка связанных областей с учетом окружающих маркеров (см. рис. 2.1 в). В качестве окружающих маркеров используется маркер вышестоящего пикселя и пикселя слева. Если вышестоящий пиксель помечен маркером, то для текущего пикселя при сканировании изображения устанавливается аналогичный маркер. В противном случае текущий пиксель помечается маркером, которым обладает пиксель слева. Если этот пиксель не имеет маркера, то текущий пиксель маркируется следующим маркером.
Адаптивное построение дерева решений на основе вероятностного подхода
Как было описано ранее, для построения алгоритма распознавания используется метод максимального правдоподобия. Решающее правило определяется выражением:
Здесь максимум ищется по всем классам и всем возможным эталонам. С помощью этого правила находится эталон длиной /, ближайший к изображению Х\. Мера близости изображения и эталонов вычисляется по формуле: где j — мера близости входной модели символа с у -ой эталонной моделью, Alfah Lerij - координаты /-го вектора во входной модели, E_Alfah E_Lerii -координаты /-го вектора ву-ой эталонной модели.
В качестве метрик было исследовано несколько различных вариантов:
1. \Alfah Len\ - \E_AIfa/, E_benf\ = Alfa \ Len, - E_Alfa \j x EJLmf
2. \Alfah Lent\ - \E_Alfa/, E_Len/\ - Alfa \ - E_Alfa/
3. \Alfah Lent\ — \E_Alfa/, E_Len/\ = Lent - E_Len/
4. \Alfah Lent\ - \E_Alfat\ E_Len/\ = {Alfa \ + Ьещ ) - (E_Alfa / + E_Len/)
Здесь Alfa » E_Alfa\ J - нормализованные значения углов в векторных моделях.
Исследования показывают (см. рис. 2.11), что наибольшая точность распознавания достигается при использовании первой метрики. Поэтому в системе распознавания предлагается использовать именно ее.
Вероятность того, что входная модель относится к данному классу, может быть вычислена по следующей формуле:
Окончательное значение вероятности принадлежности входной модели у-ой эталонной модели с учетом вероятностной модели слова будет равна
Если значение вероятности P(XiJE{) ниже некоторого порогового значения, то предполагается, что в тексте идет слово, которое не содержится в словаре. В этом случае вероятность очередного эталонного символа /V принимается равной единице, и слово распознается побуквенно без учета модели слова и заносится в текущий вспомогательный словарь. Таким образом, необходимо иметь определенный набор словарей и в зависимости от тематики текста осуществлять выбор того или иного словаря, что позволяет учитывать особенность текста в целом. В качестве таких словарей использовались следующие электронные словари: словарь Ожегова, орфографический словарь Лопатина, русско-английский и англо-русский словари, толковый словарь В. Даля.
Программа «Модуль ввода данных»
На основе разработанного программного комплекса была создана программа для ввода данных из анкетных форм в специализированный программный комплекс по обработке результатов социологических исследований «Социорасчет». Данная программа предназначена для ввода данных в автоматизированном режиме, что позволяет сократить время на проведение социологических исследований. Программа была внедрена в социологическую лабораторию Центра общественных связей СибГАУ и прошла апробацию, показав хорошие результаты, существенно сократив время обработки анкетных форм. Структурная схема программы приведена нарис. 3.8.
Программа состоит из следующих модулей:
1. Модуль организации интерфейса с пользователем.
2. Модуль распознавания и принятия решения.
3. Модуль выделения изображений символов.
4. Конфигурационный модуль.
Кроме того, в состав программы входят различные конфигурационные файлы и база данных эталонных векторных моделей. Конфигурационные файлы хранят информацию о шаблоне анкетных форм, а также их основных характеристиках. Для того чтобы ускорить процесс ввода данных, предусмотрена возможность указания зон в шаблоне формы, которые будут содержать вводимую информацию, что позволяет сократить время обработки документов, исключая из анализа области изображения, содержащие не интересующую информацию (картинки, таблицы и др.).
Входное изображение с анкетной формой поступает в модуль организации интерфейса с пользователем, на основе файла конфигурации в конфигурационном модуле осуществляется выборка параметров на конкретный тип анкетной формы (в зависимости от того, какое социологическое исследование проводится, используется соответствующая форма). После этого на основе параметров из конфигурационного модуля в модуле выделения изображений символов происходит сегментация изображения анкетной формы на текстовые зоны с выделением отдельных символов. Далее в модуле распознавания и принятия решения осуществляется построение векторных моделей символов и их классификация на основе базы данных эталонных моделей символов. Затем результат распознавания сохраняется в специальном формате, предназначенном для программного комплекса «Социорасчет», в котором осуществляется анализ результатов социологических исследований.
Программа «Модуль ввода данных» может работать в двух режимах: в режиме без обучения и в режиме с обучением. В случае, когда система работает в режиме обучения, возможна ее корректировка на конкретный тип почерка, что значительно повышает точность распознавания. С учетом специфики социологических исследований (большинство вопросов предполагают ответ «да»/«нет») предлагается использовать ячейку, в которой можно поставить либо галочку, либо крестик, и таким образом указать принадлежность ответа к категории «да», в противном случае предполагается ответ «нет». При этом система позволяет помимо распознавания символов алфавита осуществлять распознавание специальных символов (галочка, крестик и т.д.). Эта процедура является более простой по количеству операций и машинному времени, что позволяет ускорить работу системы.
Для тестирования системы применялся метод многократной прогонки. В этом случае на вход системы последовательно предъявлялись образцы рукописных символов и подсчитывалось общее количество рукописных символов, а также количество верно распознанных символов. На основе данных подсчетов вычислялась численная характеристика точности распознавания по формуле: где NOK — количество верно распознанных символов YLN0 — общее количество предъявленных символов.
В результате тестирования была сгенерирована база данных эталонных векторных моделей, состоящая из 10-15 моделей на каждый символ алфавита, при этом точность распознавания составила 70% при произвольном стиле написания. Для распознавания были взяты эталонные векторные модели длиной 20 векторов. В случае подстройки системы на конкретный стиль написания и почерк база данных эталонных векторных моделей стала содержать по 20—30 моделей на каждый символ алфавита, при этом точность распознавания составила в среднем 92—95%. Результаты распознавания для каждого класса символов изображены на рис. 3.9, ЗЛО и 3.11.
Данная программа может быть адаптирована для изображений банковских форм. В этом случае, целесообразно осуществлять коррекцию системы на конкретный тип почерка при помощи заполнения алфавита в специальной отведенной области, что получило широкое применение в подобного рода системах. Наличие распознающего ядра на основе векторного подхода обеспечит высокое быстродействие и гибкую возможность распараллеливания системы.
