Ордена Ленина
ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ
имени М.В.Келдыша
Российской академии наук
Исследование подходов к построению систем автоматического считывания символьной информации
А.В. Бондаренко, В.А. Галактионов, В.И. Горемычкин, А.В. Ермаков, С.Ю. Желтов
Москва 2003
УДК 519.68
А.В.Бондаренко, В.А.Галактионов, В.И.Горемычкин, А.В.Ермаков, С.Ю.Желтов Исследование подходов к построению систем автоматического считывания символьной информации.
Данная работа посвящена разработке прототипа алгоритмического и программного обеспечения для информационных систем автоматизации документооборота. Рассмотрены основные принципы построения системы автоматического считывания. Предложены оригинальные алгоритмы обнаружения текстовых строк, определения знако-мест и адаптивной бинаризации изображений. Для распознавания символов OCR-B-кода реализованы метод зон и метод пересечений.
A.V.Bondarenko, V.A.Galaktionov, V.I.Goremychkin, A.V.Yermakov, S.Y.Zgeltov Research of the approaches to construction of systems of automatic reading of the symbolical information.
The given work is devoted to development of the prototype of algorithm and software for information systems of automation of document circulation. The basic principles of construction of automatic reading system are considered. The original algorithms of detection of textual lines, determination of symbol places and adaptive binarization of the images are offered. Method of zones and method of crossings are implemented for recognition of OCR-B-code symbols.
Введение
Задача распознавания текстовой информации при переводе печатного и рукописного текста в машинные коды является одной из важнейших составляющих проектов, имеющих целью автоматизацию документооборота. Вместе с тем эта задача является одной из наиболее сложных и наукоемких в области автоматического анализа изображений. Даже человек, читающий рукописный текст, в отрыве от контекста делает в среднем 4% ошибок. Что касается систем считывания печатных документов, то здесь сложность заключается в том, что в ответственных приложениях, таких как, например, автоматизация ввода паспортно-визовой информации, необходимо обеспечить высокую надежность распознавания (более 98-99%) даже при плохом качестве печати и оцифровки исходного текста.
В последние десятилетия, благодаря использованию современных достижений компьютерных технологий, были развиты новые методы обработки изображений и распознавания образов ([l]-[ll]), благодаря чему стало возможным создание таких систем распознавания печатного текста, которые удовлетворяли бы основным требованиям систем автоматизации документооборота. Тем не менее, создание каждого нового приложения в данной области по-прежнему остается творческой задачей и требует дополнительных исследований в связи со специфическими требованиями по разрешению, быстродействию, надежности распознавания и объему памяти, которыми характеризуется каждая конкретная задача разработки проблемно-ориентированной системы автоматического ввода в компьютер бумажной документации.
Различные технологии, объединенные под общим термином "распознавание символов", подразделяются на распознавание в реальном режиме времени и распознавание в пакетном режиме, каждый из которых характеризуется собственной аппаратной частью и собственными алгоритмами распознавания.
В данной работе будет рассматриваться только распознавание в пакетном режиме, то есть такое, которое осуществляется после завершения ввода печатных символов.
В типичной системе оптического распознавания текстов (OCR) вводимые символы читаются и оцифровываются оптическим сканером. После этого каждый символ подвергается локализации и выделению, и получившаяся матрица подвергается предобработке, т. е. сглаживанию, фильтрации и нормализации. В результате предобработки выделяются характерные признаки, после чего производится классификация. В работе описываются базовые идеи и методы, позволяющие решить указанные подзадачи, а также их модификации, используемые в современных системах распознавания.
1. Типовые проблемы, связанные с распознаванием символов
Существует ряд существенных проблем, связанных с распознаванием рукописных и печатных символов. Наиболее важные из них следующие:
* разнообразие форм начертания символов;
* искажения изображений;
* вариации размеров и масштаба символов.
Каждый отдельный символ может быть написан различными стандартными шрифтами, например (Gothic, Elite, Courier, Orator), специальными шрифтами, использующимися в системах OCR, а также множеством нестандартных шрифтов. Кроме того, различные символы могут обладать сходными очертаниями. Например, 'U и 'V, 'S' и '5', 'Z' и '2', 'G' и '6 '.
Искажения цифровых изображений символов могут быть следующих видов:
Искажения формы: разорванность строк, непропечатанность символов, изолированность отдельных точек, неплоский характер информационного носителя (например, эффект коробления), смещения символов или их частей относительно местоположения в строке;
вращения с изменением наклона символов;
грубым дискретом оцифровке изображений;
Кроме того, необходимо выделить радиометрические искажения: дефекты освещения, тени, блики, неравномерный фон, ошибки при сканировании или при съемке видеокамерой.
Существенным является и влияние исходного масштаба печати. В принятой терминологии масштаб 10, 12 или 17 означает, что в дюйме строки помещаются 10, 12 или 17 символов. При этом, например, символы масштаба 10 обычно крупнее и шире символа масштаба 12.
Помимо указанных проблем, система оптического распознавания текста (OCR), должна выделять на изображении текстовые области, в них выделять отдельные символы, распознавать эти символы и быть нечувствительной к способу печати (верстки) и расстоянию между строками.
2. Структура систем оптического распознавания текстов
информационный документооборот считывание бинаризация
Как правило, системы OCR состоят из нескольких блоков, предполагающих аппаратную или программную реализацию:
- оптический сканер;
- блок локализации и выделения элементов текста;
- блок предобработки изображений;
- блок выделения признаков;
- блок распознавания;
- блок постобработки результатов распознавания.
В результате работы оптического сканера исходный текст вводится в компьютер в виде полутонового или бинарного изображения.
В целях экономии памяти и уменьшения затрат времени на обработку информации, в системах OCR, как правило, применяется преобразование полутонового изображения в черно-белое. Такую операцию называют бинаризацией. Однако необходимо иметь в виду, что операция бинаризации может привести к ухудшению эффективности распознавания.
Программное обеспечение в системах OCR отвечает за представление данных в цифровом виде и разбиение связного текста на отдельные символы.
После разбиения символы, представленные в виде бинарных матриц, подвергаются сглаживанию, фильтрации с целью устранения шумов, нормализации размера, а также другим преобразованиям с целью выделения признаков, используемых впоследствии для распознавания.
Распознавание символов происходит в процессе сравнения выделенных характерных признаков с эталонными признаками, отбираемыми в ходе статистического анализа результатов, полученных в процессе обучения системы.
Таким образом, смысловая или контекстная информация может быть использована как для разрешения неопределенностей, возникающих при распознавании символов, обладающих идентичными размерами, так и для корректировки слов и фраз в целом.
3. Оптическое сканирование изображений
Одна из наиболее ранних попыток создать систему, способную считывать тексты, была предпринята в 1870 году. Она представляла собой сканер-сетчатку, работа которого была основана на фотоэлементах. В дальнейшем появились Fourier d'Albe's Optophone в 1912 г. и Thomas tactile relief device в 1926 г. Системы оптического считывания текстов появились в середине XXв. в результате развития цифровых компьютеров. Дэвид Шепард, основатель компании Intelligent Machine Research, считается родоначальником создания коммерческих систем OCR. Несмотря на возможность считывания весьма ограниченного числа шрифтов и на ограничения, накладываемые на ориентацию символов, в начале 60-х г.г. системы автоматического считывания получили широкое распространение. С развитием микроэлектроники эти системы постоянно совершенствовались.
В настоящее время наиболее распространены следующие методы сканирования:
- Раздельно-щелевое сканирование. Этот метод использует массив фотоэлектрических элементов.
- Сканирование лазерным лучом.
- Сканирование матрицей фотоэлементов.
- Механическое сканирование (диском Нипкова). Принцип действия основан на вращении диска с щелями, сквозь которые проходящий отраженный свет попадает на фотодиоды.
В прошлом раздельно-щелевое сканирование активно применялось в системах OCR. Данный метод позволял производить сканирование по горизонтали, тогда как сканирование по вертикали обеспечивалось перемещением сканируемого документа.
Напечатанный документ перемещается по освещенной области. Отраженный свет, собранный линзами, попадает на фотодиоды, расположенные по горизонтали. Блок видеоусиления увеличивает амплитуду сигналов, поступающих от фотодиодов, и преобразует их в сетку черных и белых точек. Раздельно-щелевое сканирование последнего поколения использует технологию приборов с зарядовой связью (ПЗС матрицы).
4. Методы предобработки изображений текстовых символов
Предобработка является важным этапом в процессе распознавания образов и позволяет производить сглаживание, нормализацию, сегментацию и аппроксимацию отрезков линий.
Сглаживание состоит из операций заполнения и утоньшения. Заполнение устраняет небольшие разрывы и пробелы.
Утоньшение представляет собой процесс уменьшения толщины линии, в которой сразу несколько пикселов ставятся в соответствие только одному пикселу. Известны последовательные, параллельные и гибридные алгоритмы утоньшения. Наиболее общие методы утоньшения основаны на итеративном размывании контуров, при котором окно (3х3) движется по изображению, и внутри окна выполняются соответствующие операции. После завершения каждого этапа все выделенные точки удаляются.
Нормализация состоит из алгоритмов, устраняющих перекосы отдельных символов и слов, а также включает в себя процедуры, осуществляющие нормализацию символов по высоте и ширине после соответствующей их обработки.
Сегментация осуществляет разбиение изображения на отдельные области. Как правило, прежде всего необходимо очистить текст от графики и рукописных пометок, поскольку перечисленные методы позволяют обрабатывать лишь незашумленный текст. Очищенный от различных пометок текст уже может быть сегментирован.
Большинство алгоритмов оптического распознавания разделяют текст на символы и распознают их по отдельности.
Это простое решение действительно эффективно, если только символы текста не перекрывают друг друга. Слияние символов может быть вызвано типом шрифта, которым был набран текст, плохим разрешением печатающего устройства или высоким уровнем яркости, выбранном для восстановления разорванных символов.
Разбиение текста на слова возможно в том случае, если слово является состоятельным признаком, в соответствии с которым выполняется сегментация. Подобный подход сложно реализовать из-за большого числа элементов, подлежащих распознаванию, но он может быть полезен, если набор слов в кодовом словаре ограничен по условию задачи.
Под аппроксимацией отрезков линий понимают составление графа описания символа в виде набора вершин и прямых ребер, которые непосредственно аппроксимируют цепочки пикселов исходного изображения. Данная аппроксимация осуществляется в целях уменьшения объема данных и может использоваться при распознавании, основанном на выделении признаков, описывающих геометрию и топологию изображения.
5. Признаки символов, используемые для автоматического распознавания
Считается, что выделение признаков является одной из наиболее трудных и важных задач в распознавании образов. Для распознавания символов может быть введено большое количество различных систем признаков. Проблема заключается в том, чтобы выделить именно те признаки, которые позволят эффективно отличать один класс символов от всех остальных.
В данном разделе описан ряд основных методик распознавания символов.
5.1 Корреляция и сопоставление шаблонов
Введенная матрица символов сравнивается с набором эталонов. Вычисляется степень сходства между образом и каждым из эталонов. Классификация тестируемого изображения символа происходит по методу ближайшего соседа.
С практической точки зрения этот метод легко реализовать, и многие коммерческие системы его используют. Однако даже небольшое темное пятно, попавшее на внешний контур символа, может существенно повлиять на результат распознавания. Поэтому для достижения хорошего качества распознавания в системах, использующих сопоставление шаблонов, применяются другие способы сравнения изображений.
- Одна из основных модификаций алгоритма сравнения шаблонов использует представление шаблонов в виде набора логических правил.
5.2 Статистические распределения точек
В данной группе методов выделение признаков осуществляется на основе анализа различных статистических распределений точек. Наиболее известные методики этой группы используют вычисление моментов и подсчет пересечений,