Содержание к диссертации
Введение
Г л а в а 1. Методологические и алгоритмические особенности распознавания арабских текстов 8
1.1. Элементы грамматики арабского языка в свете задач распознавания 8
1.2. Основные этапы распознавания и подходы к их решению 13
1.3. Сопоставление задач распознавания арабского и русского текстов 21
1.4. Интерактивные системы распознавания 23
1.5. Автономные системы распознавания 30
1.6. Выводы по первой главе и постановка задачи исследования 42
Г л а в а 2. Алгоритмы выделения скелета шрифта 44
2.1. Подготовка изображения 44
2.2. Выделение скелета 49
2.3. Определение ширины фонта 60
2.4. Конфигурация строк 66
2.5. Сегментация знаков 69
2.6. Выводы по второй главе 71
Г л а в а 3. Алгоритмы распознавания 72
3.1. Объекты арабского текста и карта строки 72
3.2. Распознавание знаков 75
3.3. Распознавание символов 82
3.3.1. Граф символа 84
3.3.2. Метод циркуляционной нумерации 87
3.3.3. Сектор относительного положения 89
3.3.4. Ширина линии 90
3.3.5. Тип соединения 91
3.3.6. Пример распознавания символа 94
3.4. Распознавание слов 101
3.5. Выводы по третьей главе , 105
Г л а в а 4. Система распознавания и базы данных 107
4.1. Описание программы 107
4.2. Структура базы данных 107
4.3. Анализ результатов распознавания 111
4.4. Испытания системы распознавания 111
4.4.1. Распознавание знаков 112
4.4.2. Арабский текст 112
4.4.3. Русский текст 114
4.4.4. Китайский текст 115
4.4.5. Линейные рисунки 116
4.4.6. Скорость распознавания 116
4.5. Выводы по четвертой главе 118
Заключение 119
- Элементы грамматики арабского языка в свете задач распознавания
- Подготовка изображения
- Объекты арабского текста и карта строки
- Структура базы данных
Введение к работе
Количество информации, которое может быть сохранено и обработано настольными компьютерами, увеличивается с большой скоростью, но легкость, с которой компьютер и пользователь обмениваются информацией, становится серьезным препятствием- Интерфейсы пользователя должны быть эффективны и естественны для пользователя. В то время как произошел сильный прогресс в представлении данных пользователю, например, инструменты визуализации данных, первичный режим ввода данных от человека в компьютер - все еще клавиатура. Речевое распознавание и распознавание текстов допускают другие, более естественные формы человеко-машинной связи, которые недавно были интегрированы во многие программы потребителя (например, Microsoft Office ХР, Apple s Newton, MessagePad, CrossPad A.T., Cross и IBM, и т.д). Однако, чтобы эти методы ввода были экономичны и адаптированы к пользователю, их точность распознавания должна быть достаточно высокой, чтобы пользователь выполнял только минимум исправлений.
В то время как многие из сегодняшних данных введены непосредственно в компьютеры, использующие клавиатуру, все еще существует много задач, в которых люди имеют тенденцию предпочитать почерк вводу с клавиатуры. Noteaking (например, в классной комнате) - задача, которую можно все еще решить более эффективно вручную для большинства пользователей. Кроме того, в то время как люди могут писать вручную очень быстро, ввод данных в компьютер, используя комбинацию мыши и клавиатуры - процесс, относительно занимающий время. Персональные цифровые помощники (PDAs) - карманные устройства потребителя, которые могут сохранять календари и записные книжки, обеспечивать доступ к email, и содержать другие инструментальные средства производительности. Эти устройства слишком маленькие, чтобы иметь
целые клавиатуры, или иногда могут быть слишком маленькие для любой клавиатуры вообще, требуя ручки или интерфейсы голоса для ввода данных. Наконец, некоторые естественные языки содержат очень большое количество символов (например, Kanji содержит 4,000 обычно используемых символов) делая ввод с клавиатуры более трудной задачей. Для этих языков, распознавание почерка имеет потенциал, чтобы обеспечить намного более эффективный метод ввода данных.
Проблема распознавания почерка была темой исследования в течение более чем трех десятилетий. Только в последние годы появилась прогрессивная технология, где программы потребителя, основанные на распознавании почерка, стали возможными и коммерчески доступными. Имеются много типов проблем (с изменяющейся сложностью) в пределах распознавания почерка, основанного на том, как данные представлены в системе распознавания, на каком уровне эти данные можно однозначно разделить на части (например, отдельные символы или слова), и кто будет использовать устройство распознавания. Типичная система распознавания почерка фокусируется на множестве этих проблем. Таблица, приведенная ниже, показывает основные области применения распознавания
текстов и технические требования к ним.
Некоторые области применения распознавания текстов
Применение Требования Точность
Интерфейс для персонального цифрового помощника (PDA) Зажатое распознавание символов; • скорость реального времени 99 % на неестественный набор символов (graffiti)
Рукописные примечания (интерактивное) Распознавание Сегментация в индивидуальные слова; большой словарь категорий слов; может быть выполнен в пакетном режиме, поэтому, не должны быть в режиме реального времени Приблизительно 85 % - 95 % точности слова если обучение пользователя (зависимо от автора) адекватное количество данных
Распознавание почтового адреса Большой объем; должно быть в реальном масштабе времени; требует минимум ошибок, поэтому, норма отказа большая 99 % на ПОЧТОВОМ ИНДЕКСЕ, городе и стране приблизительно 25 % - 35 % отклоняет
Интерактивное подтверждение подписи Должно иметь низкую ложную норму отклонения, при поддержании низкой ложной нормы ввода 2 % - 5 % Равная норма ошибок
В последние десять лет появились несколько программ распознавания арабского языка, разработанных арабскими фирмами и использующихся ара-боязычными странами, за исключением OMNI Page Pro от фирмы OMNI (США) выпускающей самую распространенную программу для распознавания английского языка. В настоящее время эти программы не пользуются спросом на рынке, за исключением Auto Reader компании Sakhr (Египет), дочерней корпорации Alamiya (Кувейт), Последние две версии этой программы продаются только со специальной электронной карточкой в целях защиты. Однако, в скором времени филиал всемирно известной компании IBM в Египте должен выпустить (или уже выпустил) свой продукт для распознавания арабского языка. Стоимость таких продуктов обычно $1500±$300.
Цель работы. Целью диссертационной работы является повышение достоверности распознавания рукописных и машинописных арабских текстов.
Для достижения поставленной цели в работе ставятся следующие задачи:
1. Исследование грамматических и графологических особенностей арабских текстов в свете задачи распознавания.
2. Разработка методики подготовки изображения текста к выделению информативных признаков.
3. Разработка метода выделения скелета, обеспечивающего требуемое качество.
4. Разработка методики выделения строк, знаков, символов, слов и под-слов.
5. Разработка модели текста, отображающей топологию, геометрические параметры и взаимосвязи элементов арабского текста.
6. Разработка метода распознавания рукописных и машинописных текстов арабского языка.
7. Сравнительный анализ достоверности и эффективности предложенных
алгоритмов.
Методы исследования. Теоретические исследования выполнены с использованием теории множеств, математической логики, теории распознавания образов.
Экспериментальные исследования выполнены с помощью разработанной программной системы и некоторых известных продуктов на реальных арабских и русских текстах, иероглифах китайского языка, а также реальных и искусственных рисунках.
Научная новизна. К наиболее значимым научным результатам исследования относятся:
1. Метод утончения участков объекта, отличающийся тем, что с целью повышения качества скелетных линий в бинарное изображение введено понятие "неопределенного" цвета и, с целью повышения надежности распознавания текстов - вычисление параметра ширины исходных линий.
2. Модель текста в виде плоского графа, отображающего топологию, геометрические параметры и взаимосвязи символов, знаков, специфических элементов синтаксиса языка и методика формирования (извлечения из изображения) этой модели.
3. Метод распознавания рукописных и машинописных текстов, заключающийся в сопоставлении предложенного плоского графа текста с эталонными моделями языка.
Практическая ценность. Разработанные методы выделения информативных признаков на изображениях текстов арабского языка, модели и методы их распознавания положены в основу программной системы OCReader, позволяющей обеспечить требуемую достоверность распознавания всех элементов арабских рукописных и машинописных текстов.
Кроме того, разработанные модели и методы обеспечивают дальнейшее
совершенствование программных продуктов, предназначенных для распознавания, сжатия, реферирования и поиска текстов в системах электронного документооборота
Реализация результатов работы. Результаты диссертационной работы внедрены в Центральном департаменте вычислительной техники (GHQ Armed Forces, Арабские эмираты) для ввода с бумажных носителей в электронные хранилища рукописных и машинописных текстов, написанных арабским шрифтом.
Апробация работы. Основные положения диссертационной работы докладывались на 3 международных конференциях: на III Международной научно-технической конференции 23-24 мая, 2001, Ижевск; Beirut, Lebanon 25-29 June 2001; на IV Международной научно-технической конференции 19-22 февраля, Ижевск, 2003.
Публикации. По теме диссертации опубликовано 5 работ.
Структура и объем работы Диссертационная работа состоит из введения, четырех глав, заключения и приложений. Основной текст изложен на 120 машинописных страницах с таблицами и иллюстрациями. Список литературы включает 114 наименований.
Элементы грамматики арабского языка в свете задач распознавания
В последние десять лет появились несколько программ распознавания арабского языка, разработанных арабскими фирмами и использующихся ара-боязычными странами, за исключением OMNI Page Pro от фирмы OMNI (США) выпускающей самую распространенную программу для распознавания английского языка. В настоящее время эти программы не пользуются спросом на рынке, за исключением Auto Reader компании Sakhr (Египет), дочерней корпорации Alamiya (Кувейт), Последние две версии этой программы продаются только со специальной электронной карточкой в целях защиты. Однако, в скором времени филиал всемирно известной компании IBM в Египте должен выпустить (или уже выпустил) свой продукт для распознавания арабского языка. Стоимость таких продуктов обычно $1500±$300.
Цель работы. Целью диссертационной работы является повышение достоверности распознавания рукописных и машинописных арабских текстов. Для достижения поставленной цели в работе ставятся следующие задачи: 1. Исследование грамматических и графологических особенностей арабских текстов в свете задачи распознавания. 2. Разработка методики подготовки изображения текста к выделению информативных признаков. 3. Разработка метода выделения скелета, обеспечивающего требуемое качество. 4. Разработка методики выделения строк, знаков, символов, слов и под-слов. 5. Разработка модели текста, отображающей топологию, геометрические параметры и взаимосвязи элементов арабского текста. 6. Разработка метода распознавания рукописных и машинописных текстов арабского языка. 7. Сравнительный анализ достоверности и эффективности предложенных алгоритмов. Методы исследования. Теоретические исследования выполнены с использованием теории множеств, математической логики, теории распознавания образов. Экспериментальные исследования выполнены с помощью разработанной программной системы и некоторых известных продуктов на реальных арабских и русских текстах, иероглифах китайского языка, а также реальных и искусственных рисунках. Научная новизна. К наиболее значимым научным результатам исследования относятся: 1. Метод утончения участков объекта, отличающийся тем, что с целью повышения качества скелетных линий в бинарное изображение введено понятие "неопределенного" цвета и, с целью повышения надежности распознавания текстов - вычисление параметра ширины исходных линий. 2. Модель текста в виде плоского графа, отображающего топологию, геометрические параметры и взаимосвязи символов, знаков, специфических элементов синтаксиса языка и методика формирования (извлечения из изображения) этой модели. 3. Метод распознавания рукописных и машинописных текстов, заключающийся в сопоставлении предложенного плоского графа текста с эталонными моделями языка.
Практическая ценность. Разработанные методы выделения информативных признаков на изображениях текстов арабского языка, модели и методы их распознавания положены в основу программной системы OCReader, позволяющей обеспечить требуемую достоверность распознавания всех элементов арабских рукописных и машинописных текстов.
Кроме того, разработанные модели и методы обеспечивают дальнейшее совершенствование программных продуктов, предназначенных для распознавания, сжатия, реферирования и поиска текстов в системах электронного документооборота
Реализация результатов работы. Результаты диссертационной работы внедрены в Центральном департаменте вычислительной техники (GHQ Armed Forces, Арабские эмираты) для ввода с бумажных носителей в электронные хранилища рукописных и машинописных текстов, написанных арабским шрифтом.
Апробация работы. Основные положения диссертационной работы докладывались на 3 международных конференциях: на III Международной научно-технической конференции 23-24 мая, 2001, Ижевск; Beirut, Lebanon 25-29 June 2001; на IV Международной научно-технической конференции 19-22 февраля, Ижевск, 2003. Публикации. По теме диссертации опубликовано 5 работ.
Структура и объем работы Диссертационная работа состоит из введения, четырех глав, заключения и приложений. Основной текст изложен на 120 машинописных страницах с таблицами и иллюстрациями. Список литературы включает 114 наименований.
Арабский язык является самым древним языком, его история насчитывает более 5000 лет. За это время язык сильно изменился, однако последняя государственная реформа правописания арабского языка производилась около 1350 лет назад, и с тех пор мало что изменилось.
В этой главе будет проведен анализ грамматических, графологических и алгоритмических особенностей распознавания арабских текстов. Рассмотрено правописание арабского языка, основные виды распознающих программ. Рассмотрены такие вопросы, как повышение надежности распознавания, в частности, когда лучше распознать слово целиком или по буквам после сегментации. Также в этой главе производится сравнение особенностей арабского и русского языков, дается обзор существующих методов распознавания текстов арабского языка.
Подготовка изображения
Известно, что признаки представляют минимальный набор, который может использоваться в целях разборчивости и для уникальной идентификации каждого символа. Признаки могут быть классифицированы в две категории: 1. Локальные особенности, которые являются обычно геометрическими (например вогнутые/выпуклые части, тип переходов: пересечения/Т-соедине-ния/конечные точки и т.д.). 2. Глобальные особенности, которые являются обычно топологическими (связность, число связанных компонентов, число отверстий, и т.д.) или статистическими (преобразование Fourier, преобразовывают постоянные моменты и т.д.).
Nouh и другие [76] предложил стандартный набор арабских символов, чтобы облегчить компьютерную обработку арабских символов. В этой работе, тринадцать особенностей или радикалы, которые представляют части символов, отобраны при осмотре. Распознавание основано на дереве решений и сильном измерении корреляции. Недостаток предложенной системы - предположение, что поступающие символы сгенерированы согласно указанным стандартным правилам.
Parhami и Taraghi [71] представили методику для автоматического распознавания машинного печатаного текста Farsi (который является подобным арабскому тексту). Авторы сначала сегментируют подслово на символы, определяя ряд потенциальных точек соединения на основной линии, в которой толщина линии изменяется от или до толщины основной линии. Хотя они также имеют некоторые правила, чтобы сохранять символы в конце целого полслова, они сегментируют некоторые из более широких символов (например SIIN о») до трех сегментов. Затем они выбирают двадцать особенностей, основанных на некоторых геометрических свойствах символов Farsi, чтобы создать 24 битовый вектор, который сравнивается с входами таблицы, где сначала проверяется точное соответствие. Система сильно зависит от шрифта, и процесс сегментации, как ожидается, дает в некоторых случаях неправильные результаты.
Поиск таблицы используется для распознавания изолированных рукописных арабских символов [93]. В этом подходе, символ помещен в рамку, которая разделена на шесть прямоугольников, и алгоритм прослеживания контура используется для кодирования контура как набора направленных векторов, используя код Freeman. Однако, эта информация не достаточна для определения арабских символов, поэтому добавляется дополнительная информация, связанная с числом точек и их позиции. Если нет никакого соответствия, система добавит вектор особенности к таблице и рассмотрит этот символ как новый вход.
Amin и Masini [40] приняли структурный подход для распознавания напечатанного арабского текста. Слова и подслова сегментированы на символы, использующие методику основной линии. Особенности типа вертикальных и горизонтальных решеток извлекаются из символа, используя горизонтальные и вертикальные проектирования (рис. 1.14). Использовались четыре дерева решений, выбранные согласно позиции символа в пределах слова, которое было вычислено процессом сегментации. Структура четырех деревьев решений позволяет выполнить быстрый поиск соответствующего символа. Кроме того, деревья используются в распознавании символов, которые имеют ту же самую форму, но появляются в различных позициях в слове.
Amin и Man [39] предложили новую методику для многошрифтового арабского текста, который включает распознавание слова и символ. Символ разделен на многие сегменты горизонтальным процессом просмотра (рис. 1.15). Таким образом, сегменты связываются для формирования основной формы символа. Сегменты, не связанные с любым другим сегментом, рассматриваются как дополнительные символы. Используя Freeman код [60], процесс обнаружения контура применяется к этим сегментам, чтобы проследить основную форму символа и генерировать направленный вектор через 2 2 окно. Дерево решений тогда используется для распознавания символов. Наконец, Viterbi алгоритм [59] используется для распознавания арабского слова, чтобы повысить уровень распознавания. Главное преимущество этой методики - использование автоматического процесса изучения.
Объекты арабского текста и карта строки
Объект арабского текста может быть буквой, полсловом, словом, или знаком (точка, две точки, три точки, HAMZA). Расстояние между символами и их положение по отношению друг к другу, играют основную роль в распознавании символа. Например, какой букве принадлежит точка, какому полслову принадлежит буква, какому слову принадлежит подслово. Сам символ - точка, подсло-во или слово. Какие свойства символа надо знать, чтобы надежно распознавать его и какие операции для этого нужно сделать.
В данной главе рассматриваются особенности распознавания элементов (объектов) арабского шрифта и взаимоотношений между ними. Предлагаются методы выделения и распознавания знаков и символов на основе базы знаний об объектах, где для каждого символа строится граф, таблица направлений (секторов) критических точек, сведения о ширине линий и типы соединений между критическими точками. Предложен простой метод синтаксического анализа для распознавания букв, подслов и слов.
С первого взгляда на странице, написанной на арабском языке, не трудно заметить, что объекты бывают маленькие или большие. Маленькие — это точка, две точки, три точки, HAMZA. Эти объекты будем называть знаками. Большие - это буквы, полслова или слова. Эти объекты будем называть символами. Тогда буква - это символ (например: ALIF, DAAL, SIIN, ...» а, б, с, ...) или символ и знак/знаки (например ВАА, ТАА, ТНАА, ..., е, й). Первый этап распознавания - определить, является ли объект символом или знаком, и вычислить расстояние до соседних объектов. Для этого создадим карту строки. В карте заменим сим 73 волы прямоугольниками, а знаки - точками: точка, две точки, три точки, HAMZA - красными, синими, желтыми, зелеными пикселями соответственно (рис. 3.1). Полезность карты заключается в более простом и надежном определении принадлежности знаков к символам и вычислении расстояния между символами, что поможет определить символ это, буква, подслово или слово. Мы решили создать карту для каждого слова в строке в отдельности, хотя можно было создать одну карту для страницы целиком, но это затрудняется тем, что высота строк бывает разная. Например, высота заголовка больше, чем других строк. От высоты зависит много параметров. Далее мы дадим объяснение этим параметрам, а затем создадим карту строки. Высота объектов в строке- Будем различать два вида высоты: высота и абсолютная высота. Высота - это расстояние по перпендикуляру от самого верхнего пикселя объекта до самого нижнего. Этот параметр важен, потому что именно им определяется тип объекта, символ или знак. Если объект был символом, то, наверное, у него есть знаки ниже или выше его. Абсолютная высота — это расстояние от самой нижней точки до самой верхней, включая знаки, отно 74 сящиеся к символу (рис. 3.2). Практически, знаки могут быть на любом расстоянии от символа сверху или снизу, но они не касаются других строк. Иногда знаки образуют отдельную строку, поэтому будет реально сравнивать абсолютную высоту всех символов с высотой строки + 1/3 высоты строки (см. п. 2.4). Место объекта. Местонахождение символа на карте обозначается абсолютным ограничивающим прямоугольником, ширина его равна горизонтальному расстоянию от самого крайнего пикселя справа до самого крайнего пикселя слева, а высота его считаться абсолютной высотой. Знак обозначается точкой, координаты ее являются центром ограничи-вающего прямоугольника, высота которого равна расстоянию по перпендикуляру от самого верхнего пикселя объекта, до самого нижнего. Карта строки. Карта представляет собой матрицу XD размерами nxm. Полезность карты состоит в представлении информации о распознаваемой картине в более упрощенном виде. По карте можно сразу определить вид объекта: символ он или знак. Также легко определить, какому символу принадлежит знак, а это очень важно, потому что в арабском языке, более чем половина букв имеют знаки, следовательно, почте все слова имеют один знак или больше. Чтобы нарисовать карту строки, символ обозначается абсолютным огра 75 ничивающим прямоугольником, а знак точкой. На рис. 3.3 показана строка и ее карта.
Структура базы данных
Этот тест был решающим. Результат распознавания символа на рис. 3.19 -это слово, изображенное на рис. 3.18.
Последний тест не всегда необходим. Мы внедрили его, чтобы различить некоторые буквы, если результат распознавания - слово, содержащее одну из букв WAAW - это может быть буква RAA, и наоборот. Первая буква обязательно содержит цикл, но при низкокачественной печати цикл может отсутствовать, и вместо него появится линия (цепочка), но ширина в ее начале свидетельствует о наличии буквы. Если найдется точка, у которой ширина символа в три раза больше средней ширины во всех остальных точках, то мы считаем, что данный символ содержится в букве из первой группы.
Обобщим процесс сравнения двух символов. Сначала проверяем сходство графа символа с графом модели. Результат принимается как истина или ложь. Если ложь - прекращаем сравнение, если истина - проверяем сходство секторов, результат также принимается как истина или ложь. Ложь - если результат меньше, чем определенный порог (65%), и истина - если выше. Если несколько моделей превышают определенный порог, то проверяем тип связей.
До сих пор мы рассматривали знаки и символы отдельно. Знаки всегда часть слова, т.е. знак никогда не представляет собой слово. Символ может быть словом, но скорее всего не является им. Значит надо искать знаки выше и ниже его, тогда, объединив их вместе, можно распознать слово. Количество символов и их место нахождения играет важную роль в распознании слова. На рис. 3.20 показаны 4 слова Символ у всех один, но знаки (точки) различают слова друг от друга.
Объединить символ и знаки - значит, охарактеризовать местонахождение знаков относительно символа. Для этого мы использовали основную линию символа. Подсчитав количество знаков выше и ниже ее, а также их положение вдоль длины символа, можно идентифицировать слово. Такой подход эффективен, если слово короткое -1-2 буквы. Но если слово содержит 3 буквы или больше, то такой подход недостаточен, надо точнее охарактеризовать месторасположение символов. Для этого мы в начале исследования разделили каждую часть на две подчасти - правую и левую, т.е. разделили слово на четыре четверти. Горизонтально по основной линии и вертикально линией, проходящей в середине основной линии. Оказалось, что даже этого недостаточно. Например, первая и вторая точка слова 1 и 4 на рис. 3.20, всегда будут в первой и третьей четверти, т.е. слова одинаковые, а это неправильно. Даже при разделении слова вертикально на три или четыре части, мы не получили точный результат. Только при разделении на пять частей, получили желаемый, достаточно точный результат (рис. 3.21). РІногда знак находится в двух полосах вертикальных частей одновременно, в таком случае считается, что знак находится в той полосе, где находится центр ограничивающего прямоугольника знака Программа запоминает, какие знаки и сколько их в каждой полосе. Но при распознавании, знак надо анализировать, например знак " Л " рассматривается как три точки. Объект сравнивается с шаблоном следующим образом: а) если количество знаков, находящихся ниже и выше символа не равня ется количеству знаков находящихся ниже и выше шаблона, то прекращаем сравнение знака с этим шаблоном. б) сравниваем количество знаков в каждой клетке символа с соответст вующей клеткой предполагаемого шаблона, если количество знаков одинако вое, то это оценивается в 10 баллов. в) сравниваем количество знаков в каждой клетке символа с соседними клетками предполагаемого шаблона. Если количество знаков одинаковое, то это оценивается в 5 баллов, если нет, то 0 баллов. г) окончательный результат это сумма всех баллов.
