Средства управления базами графических образов символов и их место в системах распознавания. О. А. Славин



Скачать 127.48 Kb.
Дата22.04.2016
Размер127.48 Kb.


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


  1. Введение

Существующие программы распознавания текстов и документов используют при анализе одного образа, один или несколько базовых алгоритмов распознавания символов [1]. Базовые алгоритмы обладают различными свойствами, среди которых одним из важнейших является обучаемость, заключающаяся в накоплении свойств большого числа графических образов, составляющих обучающую последовательность. Одним из таких методов является, например, нейронные сети [2]. Для сеанса обучения требуется наличие обучающей последовательности объемом до нескольких миллионов образов, каждому из которых приписан код символа и, возможно, дополнительные атрибуты. Подготовка длинных обучающих последовательностей требует как участия операторов, так и специальных инструментальных программных средств для создания и ведения графических баз данных (ГБД), описываемых в данной статье.




  1. Хранение графических образов и структура ГБД

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

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

Для этих целей могут быть использованы как готовые решения, состоящие в использования универсальных СУБД типа Microsoft Access или средств ODBC, так и собственные ГБД. Созданные оригинальные ГБД обладают следующими достоинствами:



  • эффективной упаковкой изображений

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

  • согласованностью программного интерфейса с другими разрабатываемыми компонентами

  • простотой модификации структуры ГБД для решения прикладных задач.

Эти обстоятельства обусловили разработку нами собственной ГБД.

Разработанная ГБД имеет следующую структуру. Каждая БД состоит из двух наборов данных, один из которых является индексом и обеспечивает доступ к изображению по его номеру, а второй содержит общие атрибуты изображений в БД, пользовательскую информацию о всей базе и собственно записи (переменной длины), то есть упакованные изображения, каждое из которых снабжено постоянными атрибутами и переменной информацией. В число общих атрибутов базы входят разрядность изображений (черно-белые, полутоновые или цветные), их максимальный размер, количество записей и т.п. Постоянными атрибутами изображения являются его размеры и код символа, назначенный данному образу. Некоторое число служебных атрибутов базы и изображения предназначено для обеспечения оптимальной работы основных приложений с ГБД. Пользовательские атрибуты позволяют наполнять ГБД дополнительной информацией, интерпретация которой лежит на пользовательском приложении. Графическая информация упаковывается алгоритмами, существенно использующими геометрические свойства отдельных символов подобно стандартам Group3 и Group4 [3].

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


4 (KILLED)


1

LOST BLOCK



4 (KILLED)





1


2


1


2


3


5


3


2

LOST BLOCK



5




Индексный набор Записи основного набора
Рис. 1. Пример структуры ГБД, содержащей неотсортированные и убитые записи, и потерянные блоки
Такая структура данных позволяет хранить атрибутированные графические записи со следующими возможностями:

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

  • добавление новой записи, создавая новый ключ

  • сохранение новой записи, используя ключ существующей записи

  • пометка записи для удаления

  • обмен ключей доступа к двум записям.




  1. Операции над ГБД

Первой из операций над ГБД является инициализация, то есть создание пустой базы. В пустую или наполненную базу могут быть дописаны образы из текстового протокола. Парной операцией является отписывание готовой базы в протокол.

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


  • количество компонент связности в образе символа (одна, много. См. рис. 2)

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

  • пользовательские пометки изображений, которые при инициализации ГБД и ее первоначальной накачке по умолчанию не помечены

  • четность номеров изображений. Эта характеристика позволяет разделить базу на две половины одинакового объема.

Р
ис.2. Однокомпонентный и многокомпонентный образы

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

ГБД, рассматриваемые как отдельные объекты, также допускают над собой операции. Унарными операциями являются


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

  • перемешивание изображений в случайном порядке

  • сортировка базы по размерам и кодам символов.

Бинарные операции манипулируют над двумя ГБД B1 и B2, образуя в результате новую базу Br , замещающую базу B1:

  • сложение, то есть добавление к базе B1 изображений из B2, которые отличаются геометрически от всех изображений B1

  • пересечение, то есть удаление из базы B1 изображений, которые отсутствуют в базе B2

  • вычитание, то есть удаление из базы B1 изображений, которые отличаются от всех изображений B2.

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


  1. Тестирование и обучение алгоритмов распознавания

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

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

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

Известны схемы обучения, состоящие из последовательности этапов, в которых обучение алгоритмам очередного этапа производится на образах, неудовлетворительно распознанных алгоритмами предыдущих этапов [4]. Такие схемы поддерживаются бинарными операциями над ГБД, такими как пересечение. Операция пересечения баз необходима при комбинировании нескольких алгоритмов распознавания в один комплексный метод.


  1. Реализация ГБД и утилит

Ядром работы с ГБД является библиотека доступа к описанному выше формату индексированных наборов данных, содержащая следующие секции



  • секция СОЗДАНИЯ-ОТКРЫТИЯ БД с различными типами хранимых изображений

  • секция ЧТЕНИЯ изображений, атрибутов изображений и атрибутов БД

  • секция ЗАПИСИ изображений в конец БД или вставки изображения после существующей записи. Также содержит функции модификации атрибутов изображений или атрибутов БД

  • секция УПАКОВКИ-РАСПАКОВКИ, реализующая возможности встроенной и внешней упаковок

  • секция СЛУЖЕБНЫХ ФУНКЦИЙ для сортировки БД и очищения БД от записей, помеченных как удаленные.

Библиотека реализована на языке C в виде 32-разрядного DLL для MS WINDOWS 95 и MS WINDOWS NT (версия не ниже 4.0) и 16-разрядной статической библиотеки для среды MS DOS (версия не ниже 5.0). Скорость последовательного чтения изображений из готовой отсортированной ГБД составляет не менее 2500 символов в секунду на компьютере с процессором Intel Pentium 200 и жестким диском Quantum Fireball TM 3840A.

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

Важнейшей операцией является разметка ГБД операторами, классифицирующими изображения по внешнему виду. Этот режим предлагает оператору именовать выведенный на экран образ символа каким-либо кодом символа. Имеются возможности просмотра изображения в порядке возрастания или убывания номеров и перехода к изображению с произвольным номером (см. рис. 3). Код, вводимый в клавиатуры, ограничен заданным алфавитом и кодовой страницей Microsoft Windows. Дополнительная фильтрация изображений определяется запросом, позволяющим организовать режим оператор работы с подмножеством ГБД.


Рис. 3. Вид менеджера ГБД в режиме редактирования кодов изображений


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

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


Рис 4. Прогресс-монитор программы распознавания

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

Программа тестирования и утилита ведения ГБД реализованы на языке C++ в виде 32-разрядного DLL для WINDOWS 95 и WINDOWS NT. В программах используется библиотека доступа к содержимому ГБД.



  1. Технологии сбора символов

Изображения попадают в ГБД различными путями, простейшим из которых является ручное отписывание образов со своими атрибутами. Можно накапливать изображения по одному, принимая геометрические образы из буфера обмена (Clipboard) системы Windows, в который образы заносятся из произвольного графического приложения. Более профессиональный способ состоит в отписывании одиночных образов из прграмм распознавания текстов и документов. При этом границы образа определяются точнее, нежели в графическом редакторе. Одиночным отписыванием целесообразно собирать небольшие ГБД (не более 1000 образов) для целей отладки или грубого первичного обучения.

В условиях имеющейся системы распознавания выгоднее организовать массовый автоматический сбор образов. Образы отписываются либо в тестовый протокол, либо в ГБД, пользуяюсь библиотекой доступа. Настройки программ распознавания позволяют собирать образы, отобранные в соответствии с критериями


  • распознанные (нераспознанные) с различной степенью надежности всей системой ввода документов

  • распознанные каким-либо базовым алгоритмом

  • подтвержденные (неподтвержденные) словарными и лингвистическими подсистемами

  • образы, порожденные обработкой исходных изображений, например, выпрямленные курсивные буквы (см. рис. 5а)

  • образы, получившиеся в результате комбинаторных алгоритмов разрезания и склеивания [1] (см. рис. 5б)

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


Рис. 5. Образы, порожденные системой распознавания. Выпрямленный курсив (а) и временные образы разрезания (б)


Собранные автоматическими технологиями ГБД необходимо верифицировать, то есть проверить соответствие изображений и их кодов символов, полученных из систем распознавания. Для этого используется утилита-менеджер ГБД в режиме просмотра и редактирования (см. рис. 3). При верификации больших ГБД их элементы сортируются по кодам символов, иногда полезно разделить ГБД на базы, каждая из которых содержит изображения помеченные одним символом. Отсортированные и разделенные по символам ГБД позволяют организовать совместную работу нескольких операторов, выполняющих однородные действия. Основными недостатками посимвольного редактирования изображений в базах являются затруднения или невозможность различения близких в рассматриваемом классе символов. Например, рукописные образы русских букв ‘O’ и ‘0’(ноль) неразличимы, а некоторые образы символов ‘Ь’ и ’6’ очень похожи, как видно из рис.6. Случай похожих букв иногда приводит к исключению из эталонных ГБД спорных образов, что сказывается на обучении.



Рис. 6. Сходные рукопечатные образы русского языка


Устранить проблемы наименования спорных образов возможно в случае редактирования буквы в контексте ее соседей. На рис. 7. выведен контекст редактора внутреннего формата системы ввода текстов Cuneiform [1]. Внутренний редактор состоит из двух окон : окна изображения и текстового окна, причем распознанные буквы привязаны к координатам исходного изображения. В такой системе путаница спорных образов невозможна. Распознанные документы после редактирования конвертируются из внутреннего формата Cuneiform в ГБД.


Рис. 7. Окна редактора распознанного текста, привязанного к исходному изображению


Комбинации из трех рассмотренных систем сбора графических образов (автоматической, контекстно-диалоговой и одиночной) позволят собирать ГБД произвольного объема с высокой степенью надежности наименования образов.



  1. Рекомендации по использованию

Описанные в настоящей работе программные средства позволяют организовать профессиональную схему автоматизированного обучения алгоритмов распознавания (см. рис. 8). Эта схема обладает рядом существенных достоинств:



  • высокая точность итерационно обученных алгоритмов распознавания

  • получение в результате итерационного обучения ГБД большого объема, представляющих ценность для будущих работ

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

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

В качестве примера приведем разработку подсистемы распознавания рукопечатного символа в программном комплексе ввода документов FormReader фирмы Congitvie Technologies [5]. В процессе этой разработки были собраны надежно размеченные ГБД общим объемом в несколько миллионов различных образов, на которых обучились семь различных алгоритмов распознавания, обеспечивших высокую надежность ввода отсканированных документов.

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




Одиночный сбор образов


Распознавание с автоматическим сбором


Верификация




Контекстно-диалоговый сбор образов





Обучение







Рис. 8. Итерационная схема автоматизированного обучения


Литература
[1] Арлазаров В.Л., Славин О.А. Алгоритмы распознавания и технологии ввода текстов в ЭВМ.

Информационные технологии и вычислительные системы 1996, No 1


[2] Bishop C.M. Neural Networks for pattern Recongnition, Oxfrord, Oxfrord University Press, 1995
[3] Tag Image File Format Specification Revision 5.0 Final. CCITT, Geneva 1985
[4] Schapire R., “The Strenght of Weak Learnability”, Mashine Learning 1990, No 5
[5] Чернобровцев А. Персонификация и автоматизация. Computer World Россия 1998, No 7


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница