Рассматриваются алгоритмы разрезания и склеивания символов, используемые при распознавании рукопечатного
текста в системе ввода стандартных форм Cognitive Forms.
(А. А. Михайлов, В. В. Постников)
|
Разрезание и склеивание символов в процессе распознавания, т.е. фрагментация графического образа строки текста на отдельные символы - одна из наиболее трудоемких проблем, возникающих как при решении задачи распознавания печатного текста (см рис. 1, 2), так и для рукопечатного (рис.3) и слитного рукописного текста (рис. 4).
Постановка задачи разрезания и склеивания для случая рукопечатного текста, когда символы заполняются от руки в специально отведенные для них клетки (блоклеттерсы), является более "простой" по сравнению, например, с фрагментацией слитного рукописного текста, но, в то же время, к ее решению предъявляются более высокие требования - как этого требует реальное промышленное использование систем ввода анкет, заполненных от руки.
Специфика задачи в данном случае состоит в том, что клетки для вписывания символов при дизайне бланков, оптимизированном для машинного ввода, делаются такой яркости или цвета, чтобы быть заметными для заполняющего и в то же время невидимыми при наиболее скоростном черно-белом сканировании. Таким образом, программе распознавания дается "подсказка", что все символы заполнены по некоторой сетке, габариты которой можно считать известными, но точное расположение на отсканированном графическом образе не известно. Альтернативные варианты дизайна бланков, при которых клетки явно выделяются линиями упрощают данную задачу, но выдвигают не менее сложную проблему отделения символов от линий. Достаточно подробный обзор вопроса как изменяется качество распознавания в зависимости от способа макетирования полей формы содержится в статье Гарриса и Диммика [1]. Сканирование бланка в градациях серого или в цвете дает идеальную возможность для решения задачи (см. [2]), но для больших объемов ввода недопустимо по технологическим ограничениям, поскольку время сканирования в таких режимах возрастает в несколько раз.
Несколько усложняют задачу следующие два обстоятельства.
1. Характерной проблемой является случай, когда яркость фона, с помощью которого напечатаны блоклеттерсы пересекается с диапазоном яркости символов. К этому часто приводит бледная ручка заполняющего или неудачный типографский тираж с повышенной яркостью фона. В этом случае, в зависимости от значения порога яркости, при котором пиксели считаются черными, либо вблизи символов появляются пятна фона (см. рис. 5), либо символ теряет свои фрагменты и "рассыпается" на мелкие компоненты связности (рис 6). Поскольку эти случаи смешиваются в одном потоке, алгоритм разрезания-склеивания символов должен рассматривать варианты как комбинирующие мелкие компоненты связности вокруг буквы, так и игнорирующие их.
Наиболее "неприятным" является случай, когда эффекты проступающего фона и пропадания фрагментов символов проявляются одновременно (рис. 7а, 7б). При этом, простые критерии отбраковки компонент связности, такие как небольшой размер или близость к большим компонентам связности не являются достаточными для принятие решения.
Пример на рис. 7а показывает случай когда символ касается границы блоклеттерса и мелкие компоненты фона находятся вблизи границ символа. Некоторые из компонент связности символа имеют размер близкий к размеру компонент связности фона. Пример на рисунке 7б показывает случай, когда проступающее пятно фона блоклеттерса образует достаточно большую компоненту связности (она видна на рисунке).
В хорошо настроенной технологической цепочке приведенный негативный эффект удается подавить за счет использования цветофильтров при сканировании - если бланк имеет розовый или зеленый фон, либо за счет более высококачественной одноцветной печати бланка - точки фона на рисунках появляются в связи с низкой линеатурой (разрешающей способностью) печатающего устройства. Как показывают опыты, при печати с линеатурой 133 lpi удается достичь устойчивого серого фона с яркостью 4-6% черного, которая является вполне приемлемой. Бумага на которой печатаются такие бланки должна также отвечать требованиям технологии иметь достаточную белизну и низкий уровень пылеотдачи. Таким образом, для недорогих вариантов реализации систем ввода приведенная проблема остается весьма актуальной.
2. Вторым обстоятельством, затрудняющим фрагментацию графического образа строки рукопечатного текста на отдельные символы является тот факт, что "подсказка" о заполнении символов по сетке блоклеттерсов не всегда может использоваться жестко - довольно часто заполняющие отклоняются от правила заполнения "каждый символ в отдельной клетке". В особенности это касается знаков препинания, а также широких и узких букв. Узкие буквы часто вписываются в бланк по две в одну клетку; точки, запятые и другие знаки препинания иногда вписываются между клетками. Широкие буквы часто выходят за границы отведенного для символа пространства. Алгоритм вычисления расположения сетки блоклеттерсов и алгоритм собственно фрагментации должны существенно учитывать этот факт (см рис. 8).
В ряде случаев отличить знак препинания от фрагмента буквы можно только при использовании контекстных соображений.
Рис.9 демонстрирует пример, когда символ "К" успешно распознается как в комбинации с точкой, так и без нее. От алгоритма фрагментации в такого типа случаях требуется не только выбрать наиболее вероятную комбинацию пикселей, которая получает наилучшую оценку от алгоритма распознавания отдельного символа, но и сохранить альтернативный вариант для этапа последующей контекстной обработки, который пытаясь проинтерпретировать результаты строки вполне может восстановить конструкцию адреса (дом-корпус-квартира) типа:
и принять положительное решение о надежности распознавания данной строки. Рис. 10 показывает сроку целиком.
Вопрос сегментации рукопечатных символов латиницы, цифр а также китайских и японских иероглифов достаточно хорошо освящен в публикациях за последние несколько лет. Классический подход, представленный, например, в статьях [3], [4], [5] состоит в сохранении результатов распознавания разных вариантов фрагментации и последующем комбинаторном анализе на фазе контекстной обработки с использованием словаря - фактически решается задача поиска кратчайшего пути в графе альтернатив распознавания символов. В отчете 5843 Американского национального института стандартов и технологий (NIST) [6] предлагается подход, в большей степени ориентированный на фрагментацию цифровых полей, в которых контекстная поддержка в виде словарей не может быть использована как основа схемы. Основной акцент в этой работе делается на исследовании и использовании характеристических особенностей строки - средней высоты символов и толщины пера. Обращает на себя внимание продемонстрированная в этом отчете техника проведения косых разрезов, см рис. 11, фрагмент иллюстрации из этой работы.
В рамках данной работы рассматривается подход, относящийся к классу схем фрагментации, существенно комбинирующих процесс перебора фрагментов и распознавание потенциального символа, оптимизирующих некоторую целевую функцию, аргументами которой являются оценки результата распознавания символа, полученные от алгоритма распознавания. Монотонность и гладкость функции оценки результата распознавания от качества поданной на распознавание комбинации пикселей являются необходимыми свойствами алгоритма распознавания символа, без которых он не может использоваться в рамках такой схемы фрагментации. В рамках подхода, излагаемого в данной работе, в качестве блока распознавания отдельного символа используется комбинация методов распознавания - нейронно-сетевых, структурно-признаковых и метрических (см. [7], [8], [9]), которая позволяет достичь приемлемого свойства функции оценок качества символа, позволяющих произвести финальную балансировку целевой фунции алгоритма фрагментации.
В рамках предложенного подхода фрагментация строки рукопечатного текста на символы состоит из следующих этапов:
К моменту запуска этапа распознавания очередного поля вычислен угол наклона, под которым страница попала в сканер, а также приблизительное расположение границ полей бланка, основанное на расположении его статических частей (линий разграфки, статического текста, реперных точек и др.). Алгоритмы определения угла наклона и координат полей описаны в [10]. Точность, с которой определено расположение поля обычно составляет 3-5 пикселей (при сканировании в режиме 200 dpi), но в некоторых случаях может быть до 10 пикселей, например, когда графический образ бланка содержит большое количество шумовых элементов и угол наклона определен неточно. Обработка в одном потоке бланков из разных типографских тиражей, построенных по одному макету, который прошел несколько стадий конвертации в разных системах верстки может существенно увеличить погрешность.
В рамках поля, расширенных на размер максимально допустимой погрешности выделяются компоненты связности. Далее, вычисляются приблизительные базовые линии текста и положение поля слегка корректируется по вертикали. Учитываются также результаты корректировки близко расположенных и уже распознанных полей.
Вычисление расположения сетки блоклеттерсов производится с помощью процедуры динамического программирования, отыскивающей наилучшую последовательность положений границ клеток минимизируя штрафы за пересечение компонент связности. В ряде случаев алгоритм дает отказ - когда расположение сетки неоднозначно, что часто встречается на коротких строках текста, или имеет слишком высокий штраф. В положительном случае алгоритм фиксирует границы клеток.
В случае, когда алгоритм вычисления расположения сетки блоклеттерсов дал отказ, происходит запуск алгоритма распознавания строки по схеме динамического программирования, при которой слева направо, с шагом в максимальную ширину буквы производится комбинирование компонент связности, распознавание полученного фрагмента, и выбор наилучшей последовательности. Простая в своей основе схема дополняется обработкой специфических случаев, когда в зависимости от результата распознавания текущей комбинации (например, в ответе - 'Ь') производится попытка поиска потенциально потерянных фрагментов и распознавания в комбинации с ними (в нашем примере возможно 'Б'). Оптимизация результирующей комбинации по строке ведется по оценкам, полученным от алгоритмов распознавания символов строки.
Если расположение сетки блоклеттерсов прошло успешно, запускается схема распознавания строки, которая анализирует изображение строки, отдельно выделяя случай проступающего фона (например, рис. 5), а также случай сильно рассыпанных символов (например, рис. 6). Далее, в зависимости от того какой случай определен на предыдущей фазе работы алгоритма, выбирается стратегия сборки символов. Комбинаторные схемы, положенные в основу этого блока алгоритма производят не полный перебор вариантов, а останавливают свою работу при достижении приемлемой оценки от алгоритма распознавания. Удачный выбор стратегии помогает сократить время обработки, и, что наиболее важно, уменьшает вероятность ошибочного останова перебора на неправильной комбинации пикселей. Обработка специфических случаев на основе результата распознавания текущей комбинации также дополняет этот фрагмент схемы.
В ответе алгоритма для каждого выделенного знакоместа сохраняется набор альтернатив, который был получен от алгоритмов распознавания. В последствии он может использоваться в блоках контекстной постобработки строки, либо конвертироваться к текстовой строке по альтернативам, имеющим наилучшие оценки. В последнем случае решение о необходимости предъявления результата распознавания поля оператору для подтверждения или коррекции принимается на основе оценок альтернатив, которые также сохраняются на выходе из алгоритма.
Рассмотрены основные проблемы сегментации строки, возникающие при распознавании рукопечатного текста. Предложенные алгоритмы решения реализованы в системе распознавания стандартных форм Cognitive Forms ([11]), которая в настоящее время широко используется в России для ввода форм рукопечатного заполнения - пенсионных, налоговых, медицинских и других.
1. Michael D. Garris, Darrin L. Dimmick. Form Design for High Accuracy Optical Character Recognition. IEEE Transactions PAMI, June 1996.
2. J. Rocha, B. Sakoda, J. Zhou, and T. Pavlidis, "Deferred Interpretation of Grayscale Saddle Features for Recognition of Touching and Broken Characters," Proceedings of Document Recognition, SPIE, vol. 2181, San Jose, CA,pp. 342-350, February 1994.
3. A. Gillies, D. Hepp, R. Rovner, M. Whalen, "Handwritten Text Recognition System for Processing Census Forms," Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, vol. 3, pp. 2335-2340, October 1995.
4. P. D. Gader, M. Mohamed, and J. H. Chiang, "Segmentation-Based Handwritten Work Recognition," Proceedings of the USPS Advanced Technology Conference, Washington, DC, 1992.
5. F. Kimura, M. Shridar, and N. Narasimhamurthi, "Lexicon Directed Segmentation-Recognition Procedure for Unconstrained Handwritten Words," Proceedings of the Third International Workshop on Frontiers in Handwriting Recognition, Buffalo, NY, 1993.
6. Michael D. Garris. Component-Based Handprint Segmentation Using Adaptive Writing Style Model. NISTIR 5843 (Internal report of National Institute of Standards and Technology).
7. Арлазаров В.Л., Славин О.А. Алгоритмы распознавания и технологии ввода текстов в ЭВМ. Информационные технологии и вычислительные системы 1996, No 1.
8. Арлазаров В.Л., Астахов А.Д., Троянкер В.В., Котович Н. В. Адаптивное распознавание символов. В сб. "Интеллектуальные технологии ввода и бработки информации", М.: Эдиториал УРСС, 1998
9. А.В.Мисюрёв. Использование искусственных нейронных сетей для распознавания рукопечатных символов. В сб. "Интеллектуальные технологии ввода и обработки информации", М.: Эдиториал УРСС, 1998
10. В.В. Постников. Разработка методов наложения формы на графическое изображение документа. В сб. "Интеллектуальные технологии ввода и обработки информации", М.: Эдиториал УРСС, 1998
11. Система распознавания стандартных форм Cognitive Forms. http://www.cognitive.ru
http://ocrai.narod.ru E-Mail: ocrai@narod.ru последнее обновление: 01;03;2003
