Быстрые структурные преобразования изображений в системах распознавания изображений документов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Безматерных Павел Владимирович

• Безматерных Павел Владимирович
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Безматерных Павел Владимирович

Введение

Глава 1. Место структурных преобразований изображений в

системах распознавания документов

1.1 Системы распознавания изображений документов

1.1.1 Цифровой образ документа и его структура

1.1.2 Типовая схема системы распознавания структурированных изображений документов

1.1.3 Системы чтения штриховых и матричных кодов

1.1.4 Целевые характеристики модулей в системах распознавания документов

1.2 Элементы обработки изображений в системах распознавания документов

1.2.1 Понятие цифрового изображения

1.2.2 Анализ проекций цифровых изображений

1.2.3 Методы математической морфологии

1.2.4 Преобразование Хафа

1.2.5 Интегральное изображение

1.3 Понятие структурного преобразования изображений

1.4 Методы ускорения структурных преобразований изображений

1.4.1 Алгоритмическая оптимизация вычислений

1.4.2 Приближение множества паттернов, снижающее вычислительную сложность

1.4.3 Аналитическое упрощение композиции структурных преобразований

1.5 Выводы по главе. Задачи диссертационной работы

Глава 2. Детектирование рукописных пометок на фоне

статических элементов формы

2.1 Формальная постановка задачи

2.2 Базовый алгоритм на основе анализа краевых точек изображения

2.2.1 Модель краевого пикселя

2.2.2 Описание пометки с помощью краевых пикселей

2.2.3 Критерий детектирования пометки

2.3 Экспериментальные результаты

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

2.5 Выводы по главе

Глава 3. Геометрическая нормализация изображения

документа и его текстовых фрагментов

3.1 Быстрое преобразование Хафа как быстрое структурное преобразование изображения

3.2 Общие положения предлагаемого подхода

3.3 Экспериментальные результаты

3.3.1 Способы оценки точности определения угла наклона

3.3.2 Нормализация текстовых фрагментов

3.3.3 Нормализация угла наклона документа

3.4 Выводы по главе

Глава 4. Автоматическая типизация сканированного

изображения структурированного документа

4.1 Типизация документов на основе деформации объектов

4.2 Потенциальные проблемы метода

4.3 Алгоритм динамической трансформации временной оси

4.4 Алгоритм идентификации типа документа

4.5 Алгоритм автоматического построения эталона типа документа

4.6 Выводы по главе

Глава 5. Генеративное распознавание поврежденных

матричных кодов

5.1 Формальная постановка задачи

5.2 Предлагаемый метод

5.2.1 Жадный алгоритм оптимизации вычисления структурного преобразования

5.2.2 Варианты оптимизации жадного алгоритма

5.3 Схема работы системы с использованием метода генеративного распознавания

5.4 Сравнение реализаций генеративного распознавания Aztec кодов

5.5 Генеративное распознавание кодовых слов символики PDF417

5.6 Апробация генеративного метода распознавания матричных кодов

5.7 Выводы по главе

Заключение

Список рисунков

Список таблиц

Приложение А. Акты о внедрении

Приложение Б. Свидетельства о государственной регистрации

программы для ЭВМ

Введение диссертации (часть автореферата) на тему «Быстрые структурные преобразования изображений в системах распознавания изображений документов»

Введение

Актуальность. Системы распознавания изображений документов (далее - СРИД) имеют высокое прикладное значение во многих областях человеческой деятельности. Без их использования уже немыслим массовый ввод и обработка бланков голосования и тестирования, построение индекса для эффективного поиска в базах архивных документов, а также верификация документов, удостоверяющих личность (далее - ДУЛ). Как правило, автоматической обработке подвергаются структурированные документы, часто для краткости именуемые просто «формами». К ним относятся такие типы документов как анкеты, товарно-транспортные накладные, таблицы учета платежей, ДУЛ, а также многие другие. В системах обработки форм должны решаться следующие задачи из области обработки изображений:

— нормализовать входное изображение документа;

— идентифицировать тип входного документа;

— разобрать структуру входного документа (выделить элементы разграфки, а также определить положение значимого заполнения);

— распознать содержимое найденных полей ввода данных;

— локализовать и распознать специализированные машиночитаемые зоны (например, штриховые коды).

Подобные СРИД активно исследовалась как российскими, так и зарубежными учеными. Среди представителей российских ученых особенно выделяются В.Л. Арлазаров, Н.Е. Емельянов, О.А. Славин, Д.Е. Ян, В.В. Постников; среди зарубежных - Г. Баирд, Д. Доерманн, К. Томбре, Б. Гатос, С. Учида. Для построения СРИД требуется одновременное применение знаний из множества областей: компьютерного зрения, распознавания образов, различных разделов математики, и особенно обработки и анализа изображений.

Область обработки и анализа изображений имеет богатую историю, весомый вклад в которую был внесен многими специалистами. Среди отечественных ученых стоит отметить Ю.В. Вильзитера, В.А. Сойфера, И.Б. Гуревича, А.И. Чуличкова, Ю.П. Пытьева, среди зарубежных специалистов - Т. Хуанга, Ж. Серра, К. Шапиро.

С точки зрения количества операций, производимых в СРИД, наибольшая часть приходится на обработку и анализ изображений. В настоящее время идет процесс переноса функционирования СРИД с серверных станций и персональных компьютеров на различные мобильные устройства. И хотя такие устройства зачастую оснащены куда более слабыми вычислительными мощностями, они почти наверняка имеют (а) встроенную камеру, позволяющую провести регистрацию изображения документа по месту; (б) удовлетворительные мощности для обработки полученного изображения документа без его передачи во внешний контур. Это особенно важно с точки зрения защиты персональных данных при обработке ДУЛ. Кроме того, в обществе растет спрос на использование продуктов, базирующихся на парадигме «зеленых вычислений». Эта парадигма подразумевает минимизацию «углеродного следа» устройства при выполнении на нем вычислительных процедур. Поэтому необходимо использовать вычислительно эффективные алгоритмы, а также изыскивать методы их оптимизации при решении конкретных прикладных задач.

Входными данными для СРИД является цифровое изображение, минимальные логические элементы которого традиционно именуются пикселями. Всевозможные высокоуровневые объекты на изображении (текстовые фрагменты, элементы разграфки и т.д.) могут быть представлены как сгруппированные по некоторым признакам множества этих пикселей. Структурным преобразованием изображения (далее - СПИ) будем называть применение ассоциативной операции (например, сложение или взятие максимума) к выделенному подмножеству пикселей из исходного изображения, далее именуемого паттерном. Тогда многие уже известные преобразования изображений, на первый взгляд сильно различные, попадут в данную группу. Через аппарат структурных преобразований оказывается удобно выразить множество методов низкоуровневого анализа и обработки изображений, таких как локальное усреднение изображения по окрестности, морфологическую фильтрацию, преобразование Хафа. Частные случаи указанных преобразований хорошо исследованы и широко применяются на практике, а для ряда из них известны специализированные вычислительно эффективные алгоритмы. Структурные преобразования являются важной общей низкоуровневой частью обработки изображений для многих прикладных областей, радующих нас успехами и достижениями. Для каждого

структурного преобразования можно определить его сложность: количество применений операции, требуемое для его вычисления. Быстрым структурным преобразованием изображений (далее - БСПИ) будем называть структурное преобразование, обладающее уменьшенной сложностью относительно алгоритма, независимо применяющего заданную операцию для каждого подмножества пикселей исходного СПИ. Вопросами построения быстрых структурных преобразований занимались такие ученые как М. ван Херк, Й. Гил, М. Брейди, В. Гётц, Ж. Виймен, С.М. Карпенко, Д.П. Николаев. Использование БСПИ вместо СПИ позволяет улучшить одну из ключевых характеристик системы распознавания изображений документов - скорость ее работы при фиксированном вычислителе. К сожалению, общий подход к использованию БСПИ в рамках СРИСД до сих пор недостаточно освещен.

Таким образом, актуальным является вопрос идентификации применений структурных преобразований изображений при решении прикладных задач в области распознавания документов, повышение эффективности их вычисления (построение быстрых структурных преобразований), а также исследование целевых характеристик решений, построенных с использованием БСПИ.

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

Для достижения поставленной цели были сформулированы и решены следующие задачи:

1. Идентифицировать и систематизировать типовые задачи анализа изображений при распознавании изображений документов, решаемые с использованием структурных преобразований изображений.

2. Для выявленных типовых задач разработать методы решения, ускоренные за счет использования аппарата быстрых структурных преобразований изображений.

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

Научная новизна:

1. Введено понятие структурных преобразований изображений, что позволило единым образом сформулировать и оптимизировать ряд задач из области обработки изображений в рамках систем распознавания изображений документов.

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

3. Создан и выложен в открытый доступ корпус данных ICrus, состоящий из 2750 изображений кириллических рукописных фрагментов с эталонными значениям углов наклона фрагментов, пригодный для оценки точности алгоритмов определения наклона текстовых элементов.

4. Впервые предложен алгоритм для определения типа сканированного документа по структуре его проекций на координатные оси методом динамического программирования.

5. Впервые предложен метод генеративного распознавания матричных кодов фиксированной размерности с поврежденными метаинформационными модулями.

Практическая значимость Разработанные в рамках диссертации методы и алгоритмы автоматического анализа изображений документов с привлечением аппарата быстрых структурных преобразований изображений реализованы в виде программных компонент и внедрены в программное обеспечение ряда коммерческих компаний. Так, быстрый алгоритм детектирования рукописных пометок на фоне статических элементов бланка внедрен в продукт «Smart PassportReader» компании ООО «Смарт Энджинс РУС» и системы распознавания структурированных документов «Smart IDReader» и «Smart ID Engine» компании ООО «Смарт Энджинс Сервис», а также в систему автоматического ввода форм документов «Cognitive Forms», разработанную компанией «Cognitive Technologies». В последнюю систему также внедрен быстрый алгоритм классификации документов фиксированной геометрии на сканированных документах. Методы автоматического устранения наклона документа и текстовых фрагментов используются в уже упомянутых системах «Smart PassportReader», «Smart IDReader», «Smart ID Engine». Элементы генеративного распознавания матричных кодов и их

кодовых слов внедрены в продукты «Smart Code Engine» и «Smart Aztec Code Engine» компании ООО «Смарт Энджинс Сервис». Перечисленные выше продукты встроены в информационные и промышленные системы ряда крупных отечественных и зарубежных организаций, в том числе в государственные структуры Российской Федерации.

Методология и методы исследования. При написании диссертационной работы использовались методы системного анализа, цифровой обработки и анализа изображений, распознавания образов, а также методы вычислительной оптимизации. Содержание диссертации соответствует специальности 2.3.1. Системный анализ, управление и обработка информации, статистика, а именно пунктам:

— 4. Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений, обработки информации и искусственного интеллекта;

— 5. Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений, обработки информации и искусственного интеллекта;

— 9. Разработка проблемно-ориентированных систем управления, принятия решений и оптимизации технических объектов.

Основные положения, выносимые на защиту:

1. Показано, что СПИ используются при решении множества прикладных задач Т в рамках различных модулей М из СРИСД.

2. Для алгоритма определения наличия рукописной пометки А^^ на растре RnхМ предложен способ сокращения количества требуемых операций суммирования в 4,5 раза за счет предварительного вычисления префиксных сумм, для хранения которых достаточно дополнительного массива из N • (М + 1) элементов.

3. На основе алгоритмов нормализации текста А^Щ и A

м Р TJT Л Р TIT

синтезированы алгоритмы Ag^nt и Ag^, принципиальным отличием которых является замена вычисления преобразования Хафа на его аппроксимацию алгоритмом Брейди-Ёна. Для новых алгоритмов показано более чем десятикратное увеличение производительности при сохранении достаточной точности определения угловых характеристик в рамках СРИСД.

4. Задача генеративного распознавания штриховых кодов сведена к вычислению СПИ, для алгоритмической оптимизации которого предложен жадный метод , позволивший сократить количество

суммаций в 3,3 раза при опознавании кодовых слов символики PDF417 и в 24 раза при распознавании Aztec символов фиксированной размерности 15 х 15 модулей.

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

Апробация работы. Основные результаты работы докладывались на следующих семинарах и конференциях:

1. Международные конференции серии International Conference on Machine Vision (ICMV); Франция, 2016; Австрия, 2017; Нидерланды, 2019; Италия, 2022;

2. Конференция «Информационные технологии и системы» (ИТиС), Россия, (2008, 2010 годы).

3. Открытый семинар лаборатории №11 Федерального государственного бюджетного учреждения науки Институт проблем передачи информации им. А.А. Харкевича Российской академии наук (ИППИ РАН);

4. Семинар отделения №9 Федерального исследовательского центра «Информатика и управление» Российской академии наук (ФИЦ ИУ РАН).

Личный вклад. Результаты диссертации, вынесенные на защиту, получены автором самостоятельно. Постановка задач и обсуждение результатов проводились совместно с научным руководителем. В совместных работах [139—145] выработка принципиальных методов решения поставленных задач, детальная разработка соответствующих алгоритмов, а также планирование и проведение экспериментов, включая создание релевантных корпусов данных, проведено диссертантом. Тексты публикаций [139—142; 144—146] написаны диссертантом. Кроме того, в работах [139; 141—145] автору принадлежит реализация заявленных в них алгоритмов. В работе [147]

результаты работы диссертанта изложены в разделах «Scanners» и «Documents with fixed layout». Также диссертантом написаны соответствующие части введения и литературного обзора. В рамках работы [148] диссертантом осуществлено планирование и проведение экспериментов, а также выполнен анализ полученных результатов. Работа [149] выполнена автором самостоятельно в полном объеме.

Публикации. Основные результаты по теме диссертации изложены в 15 печатных изданиях, 3 из которых изданы в журналах, рекомендованных ВАК, 2 —в научных журналах, индексируемых Web of Science и Scopus, 6в тезисах докладов.

Объем и структура работы. Диссертация состоит из введения, 5 глав, заключения и двух приложений. Полный объём диссертации составляет 150 страниц, включая 56 рисунков и 8 таблиц. Список литературы содержит 149 наименований. Зарегистрированы 2 патента и 2 программы для ЭВМ.

Глава 1. Место структурных преобразований изображений в системах распознавания документов

1.1 Системы распознавания изображений документов

Распознавание изображений - важная область теории распознавания образов [1; 2]. Большинство задач распознавания в ней заключается в автоматическом вынесении качественных или количественных суждений относительно свойств изображений или же их прообразов. Классификация или узнавание изображений, поиск на них заранее определенных примитивов, оценка их численных характеристик, преобразование графических представлений объектов в удобную для обработки форму - все это разновидности задач распознавания изображений.

В диссертационной работе рассматриваются задачи распознавания изображений, возникающие в различных модулях систем распознавания изображений документов (далее - СРИД), качество решения которых напрямую влияет на целевые характеристики этих систем. Интерес к СРИД продиктован их широким проникновением как во многие аспекты нашей повседневной жизни, так и во множество разнообразных бизнес-процессов.

Дальнейшее изложение организовано следующим образом. В подразделе 1.1.1 вводится ключевое понятие документа, а также рассматриваются связанные с ним понятия структуры и типа. Затем в подразделе 1.1.2 разбирается схема устройства типовой СРИД и приводится краткое описание ее основных модулей. Отдельный подраздел 1.1.3 посвящен системам чтения штриховых и матричных кодов, которые могут функционировать как независимые системы распознавания, так и выступать в роли вспомогательных модулей СРИД. Целевые характеристики систем распознавания документов рассматриваются в подразделе 1.1.4.

1.1.1 Цифровой образ документа и его структура

Заполнить анкету, оплатить счет, предъявить паспорт, послать письмо -понятные всем задачи, в которых приходится иметь дело с тем или иным документом. В соответствии с российским ГОСТ [3] документ определен как «материальный носитель с зафиксированной на нем в любой форме информацией в виде текста, звукозаписи, изображения и (или) их сочетания, который имеет реквизиты, позволяющие его идентифицировать, и предназначен для передачи во времени и в пространстве в целях общественного использования и хранения». При этом контекст данной работы ограничен исключительно визуальными образами или изображениями документов, исходно представленных на некотором материальном носителе, чаще всего - бумаге или пластике.

Перевод материального носителя документа в цифровой образ документа осуществляется с помощью устройства регистрации изображения. В его роли может выступать планшетный сканер, фотоаппарат, камера мобильного телефона [4] или же специализированная система [5].

Цифровой образ документа обладает рядом преимуществ: в таком виде документы удобно хранить, пересылать на большие расстояния, автоматически обрабатывать с помощью СРИД на ЭВМ. Такие системы решают задачи массового автоматического ввода бланков голосования и анкет [6], перевода книг в электронный вид, распознавания документов, удостоверяющих личность (далее - ДУЛ) [147], чтения штриховых и матричных кодов.

В целях повышения эффективности СРИД в них закладывается априорная информация о типах документов, которые им предстоит обрабатывать. Неформально, тип документа определяет правила извлечения смысловой информации из его реквизитов. Эти правила позволяют ответить на два важных вопроса: как на носителе расположены реквизиты (геометрия документа) и как интерпретировать их содержимое (семантика документа)? С практической точки зрения наиболее важными оказываются типы документов, геометрия которых, также как и семантика варьируется не произвольно от образца к образцу, а оказывается подчинена набору некоторых соотношений, быть может весьма строгих. Такие типы документов

называются структурированными [7]. Например, паспорт гражданина РФ обладает строгой геометрической структурой - точно известно, где располагаются все его реквизиты. Отличный вариант формализации упомянутых в данном абзаце терминов приведен в работе [8].

Будем называть статическими элементами документа его текстовые фрагменты и элементы оформления, которые не изменяются от образца к образцу в рамках одного типа (например, текстовый фрагмент «Код подразделения» в паспорте РФ); заполнением - реквизиты документа, непосредственно определяющие его информационное содержимое, которое варьируется от одного экземпляра к другому; жесткой формой - документ, у которого все статические элементы его визуальных образов совпадают при совмещении на просвет. Типовыми примерами жестких форм являются анкеты и бланки для голосования, тестирования, сдачи медицинских анализов, внесения показания счетчиков ЖКХ.

Жесткие формы, как правило, исходно проектируются для обработки с помощью СРИД. Штриховые и матричные коды также являются примерами документов, специально спроектированными для чтения СРИД, а не человеком. Иногда структурированным оказывается не документ целиком, а только его часть. В таком случае принято говорить о машиночитаемых зонах (МЧЗ) документов. Ярким примером такой зоны, стандартизованной международной организацией гражданской авиации, является МИ^ [9]. Очевидно, что все упомянутые выше документы являются структурированными, а СРИД для структурированных документов (далее -СРИСД) становятся важным классом подобных систем. Именно этот класс и рассматривается далее в данной работе.

1.1.2 Типовая схема системы распознавания структурированных

изображений документов

Системы распознавания структурированных изображений документов исследуются уже более пятидесяти лет. В популярной работе известной норвежской ученой Л. Эйквиль [10] описаны основные этапы становления

подобных систем, выделены «поколения» СРИСД, а также представлены их базовые блоки.

Тематике автоматической обработки документов посвящен фундаментальный труд под редакцией Д. Доэрмана и К. Томбре [11], где детально рассматриваются все этапы анализа и распознавания изображений данного домена. Детальный разбор с учетом актуального положения дел в области представлен в работе [12]. Вопросам и специфичным задачам распознавания ДУЛ посвящена недавняя работа [147].

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

По функциональному признаку система распознавания документа обычно подразделяется на следующие модули [7]:

1. М.1 - ввода изображения;

2. Мр - нормализации и оценки качества изображения;

3. Мг - идентификации типа документа и установления его внутренней системы координат;

4. Мг - распознавания реквизитов;

5. Мс - пост-обработки реквизитов и контроля заполнения документа;

6. Ме - экспорта результатов обработки.

Схема типовой СРИСД проиллюстрирована рисунком 1.1. Рассмотрим подробнее каждый из указанных модулей.

Модуль ввода изображения М^, обеспечивает поступление образа документа для его автоматической обработки в СРИСД при помощи пользовательского инструментария ввода. Этот инструментарий включает в себя прикладной программный интерфейс, позволяющий принимать уже сформированный извне образ документа. Однако часто бывает, что изображение документа требуется сформировать «по месту», например, при персональном визите в отделение банка. В таком случае, в рамках того же инструментария оператором производится регистрация изображения с помощью устройства ввода, чаще всего - сканера или камеры мобильного телефона.

Рукописные поля Машиночитаемые поля Штрих-коды Пометки

> 1

Модуль пост-обработки и контроля заполнения документа

Рисунок 1.1 — Схема типовой системы распознавания документов. Желтым цветом помечены модули, являющиеся предметом интереса данной работы.

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

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

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

Как итог, тип используемого устройства регистрации изображения во многом определяет процесс обработки образа документа, а иногда и «архитектуру» самой СРИСД. Очевидно, что для распознавания изображений, полученных в сильно варьирующихся условиях с помощью камеры мобильного телефона требуется задействовать вычислительно более затратный, по сравнению со сканерами, аппарат обработки и анализа изображений. Указанные особенности регистрации изображений учитываются в модулях Мр и Мг, куда закладываются соответствующие этапы обработки изображений.

Модуль нормализации и оценки качества

изображения Мр предназначен для решения двух проблем. Во-первых, он позволяет оценить пригодность изображения для дальнейшей обработки и анализа. Во-вторых, он позволяет нивелировать различия в способах регистрации изображения, т.е. преобразовать входное изображения к некоторому «каноничному», с точки зрения проектировщика СРИД, виду. Подобное преобразование принято называть нормализацией изображения [13]. Нормализация изображения документа существенно упрощает все

последующие этапы его распознавания и анализа. Многие вопросы нормализации изображений документов прекрасно изложены в диссертационной работе И.А. Коноваленко [14]. В контексте СРИСД речь, как правило, идет о геометрической и цветовой нормализациях.

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

Проективная нормализация позволяет использовать на дальнейших этапах обработки и анализа более простую геометрическую модель, характерную для сканированных документов, что благоприятно сказывается на общей сложности и быстродействии СРИД. Для компенсации проективных искажений документа требуется вычисление матрицы проективного преобразования, что, как правило, делается с помощью определения границ документа при априорном знании о физических размерах бланка. Данная тема прекрасно раскрыта в диссертации Д.В. Тропина [15]. Конечно, существуют методы, позволяющие провести нормализацию и другими способами (например, TILT [16]), однако их использование является вычислительно «неподъемным» для большинства промышленных СРИД. Кроме того, точность работы данных методов в контексте нормализации документов еще не исследована.

Список литературы диссертационного исследования кандидат наук Безматерных Павел Владимирович, 2025 год

/ / /

* -->

Рисунок 2.10 — Пример системы координат (и,у) (слева); пример краевого пикселя в данной системе координат (справа).

Итого, для вычисления краевых пикселей по направлениям требуется вычислить предварительный набор префиксных сумм Л = { J(ф) | ф € Ф}. Тогда оптимизированное БСПИ выглядит следующим образом:

F§STCж = и (Лф и Вф)- (2.11)

ф€Ф

Очевидным преимуществом данного БСПИ является то, что число операций в нем вообще не зависит от 6. При этом для одного направления ф требуется предварительно вычислить N • М сумм. При фиксированном значении 6 = 7 для вычисления необходимых признаков потребуется вычислить 3 • N • М разностей. Общее число операций тогда составит 4 • N • М, что в 4.5 раз меньше, чем 3 • (7 — 1) • N • М при вычислении методом грубой силы. Таким образом алгоритм отличается существенно меньшим количеством операций при неизменной точности работы. Отметим, что хранения префиксных сумм для растра хМ достаточно дополнительного массива из N • (М + 1) элементов.

2.5 Выводы по главе

В данной главе представлен алгоритм ^дП для определения наличия рукописной пометки в заданной области, в присутствии возможных регулярных помех. Предложенный алгоритм базируется на вычислении суммарных интенсивностей пикселей на триплетах прямолинейных паттернов длины 6, ориентированных вдоль выделенного набора направлений Ф. Задача подсчета суммарных интенсивностей пикселей сформулирована в виде СПИ. В главе также предложен подход к оптимизации данного СПИ, который опирается на предподсчёт префиксных сумм по используемым направлениям. Данный подход привел к синтезу оптимизированной версии алгоритма который требует существенно меньшего количества суммаций при сохранении той же точности, однако для растра RNхМ требует хранить дополнительный массив из N • (М + 1) элементов с кумулятивными суммами.

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

Оптимизированный алгоритм был опубликован автором

диссертации в статье [139]. Имплементация данного алгоритма детектирования рукописных пометок на фоне статических элементов бланка внедрена и уже длительное время используется в продуктах «Cognitive Forms» компании Cognitive Technologies, «Smart PassportReader» компании ООО «Смарт Энджинс РУС» и СРИСД «Smart ID Engine» и «Smart IDReader» компании ООО «Смарт Энджинс Сервис», что подчеркивает его высокую практическую значимость.

Глава 3. Геометрическая нормализация изображения документа и

его текстовых фрагментов

В данной главе рассматриваются две классические задачи из области автоматической обработки изображений документов, связанные с геометрической нормализацией их цифровых образов: Vskew - компенсация наклона всего документа и Vsiant - исправление наклонного начертания его отдельных текстовых фрагментов. В рамках СРИСД эти задачи возникают в модулях Мр и Мг соответственно (раздел 1.1.2).

Как было показано ранее в разделе 1.1.2, входное изображение документа для СРИСД, как правило, получается путем сканирования или фотографирования физического носителя. Влияние как человеческого, так и технического факторов, может приводить к геометрическим искажениям результирующих образов [12]. Наклон документа является одним из наиболее распространенных примеров подобных искажений, а его компенсация ключевым этапом обработки изображения документов [95]. После его устранения все последующие стадии, такие как, например, выделение текстовых фрагментов и их обработка с помощью модулей распознавания отдельных символов, могут быть существенно упрощены [10]. Рисунки 3.1а,б демонстрируют изображение документа до компенсации его наклона (слева) и после (справа).

(а) (б)

Рисунок 3.1 — Цифровой образ паспорта РФ: (а) до компенсации его наклона,

(б) после компенсации.

Точность распознавания текстового фрагмента существенно зависит от точности процедуры его сегментации на отдельные символы. Если шрифтовое начертание символов фрагмента является стандартным, то для его сегментации можно использовать модель вертикальных разрезов. Данная одномерная модель ранее отлично зарекомендовала себя при решении задачи сегментации печатных символов [27; 96]. При этом она не потеряла своей актуальности и сейчас [97]. Чтобы ею можно было воспользоваться для текстовых фрагментов с нестандартными начертаниями, их стоит предварительно нормализовать. К нестандартным начертаниям относятся: а) механически наклонные (англ. «oblique»), (б) курсивные (англ. «italic»), в) рукописные фрагменты. На рисунке 3.2 приведены примеры реальных входных данных с нестандартным начертанием, а также ожидаемый результат их нормализации.

а

б

в

Т

Василий 'Шшмкя Ш 1С I

д

Т

ж

ШтЛт

Рисунок 3.2 — Общая схема координатного скоса для нестандартных начертаний (а) и результат нормализации (д). Примеры курсивного (б рукописного (в) и наклонного (г) начертаний и результаты их нормализации (е (ж) и (з) для реквизитов «Фамилия», «Имя», «Отчество» соответственно.

Возможность успешного распознавания текстовых фрагментов с нестандартными начертаниями является существенным преимуществом при выборе системы распознавания для промышленного применения. Так, в задаче автоматического ввода паспортов гражданина РФ нередко встречаются документы, заполненные от руки, а некоторые ДУЛ изначально содержат атрибуты, напечатанные с наклонным начертанием. Наличие нестандартного начертания особенно сильно влияет на процедуру сегментации фрагмента на отдельные символы [27].

Для решения задачи *Vskew к изображению не нормализованного документа применяется преобразование поворота R (англ. «rotate»), а в задаче 'Dsiant к изображениям текстовых фрагментов применяется

преобразование скоса S (англ. «slant»). Эти преобразования определяются матрицами (3.1):

Таким образом, обе задачи и сводятся к автоматическому

определению угла наклона а по входному изображению.

Для решения указанных задач в рамках СРИСД зачастую используется анализ результата ПХ, рассмотренного нами ранее в разделе 1.2.4. В разделе 1.3 было установлено, что вычисление ПХ само по себе является задачей вычисления СПИ. Затем в разделе 1.4.2 было упомянуто, что данное СПИ может быть сконвертировано в БСПИ за счет замены множества паттернов, по которым производится суммирование. Такому БСПИ, как показано далее в разделе 3.1, соответствует задача вычисления БПХ.

Вообще, идея возможности применения БПХ для решения задачи 'Одке-ш была, по-видимому впервые, предложена в упомянутой ранее работе [98]. К сожалению, в ней не приведен ни алгоритм, ни какие-либо характеристики метода, опирающегося на данную аппроксимацию. И хотя оценка неточности быстрой аппроксимации БПХ хорошо исследована теоретически [99], вопрос насколько сильно данная неточность влияет на результаты в практических приложениях является открытым. Таким образом, исследование скоростных и точностных характеристик предлагаемого подхода является важным для установления границ применимости методов определения угла наклона в рамках промышленных СРИСД. В тоже время, для задачи определения угла наклона текстового фрагмента решений с использованием такой аппроксимации выявить не удалось. Поэтому целью, поставленной в данной главе, является синтез алгоритмов для решения задач 'Одке-ш и гО&1а1Пг с помощью методов БСПИ и проведение вычислительных экспериментов на релевантных массивах данных для установления границ их практической применимости.

R(a)

cos а — sin а

sin а cos а

(3.1)

3.1 Быстрое преобразование Хафа как быстрое структурное

преобразование изображения

В БПХ для задания диадических паттернов используется ($,£) параметризация, где в это сдвиг, а I это наклон прямой - разница в координатах двух точек пересечения противоположных сторон растра. На рисунке 3.3 приведен пример диадического паттерна при в = 1 и £ = 2 на растре Д5х8, а также продемонстрировано его отличие от «ближайшей дискретной прямой» п8 1 с рисунка 1.11. Видно, что диадический паттерн

3

обладает симметричной структурой.

í = 2

Рисунок 3.3 — Пример расхождения «ближайшей» дискретной прямой п| 1

3

и диадического паттерна ^(1,2). Различие в одной позиции растра в пятом столбце: темно-серым цветом выделена позиция для ближайшей прямой, для диадического паттерна соответствующая позиция выделена светло-серым

цветом.

Необходимо установить способ систематического определения всех дискретных паттернов, требуемых для вычисления Хаф-образа. Так, в работе Д. Николаева и соавторов [98] приводится реккурентное определение набора «порождающих» диадических паттернов для квадратного изображения со стороной 2^ (3.2):

рк _ гг =

{(0,0)},

к =0,

» (Г#/21,2'-1)) к> 0.

(3.2)

где I € {0,1,..., 2^ — 1} это упомянутый ранее наклон. Имея в наличии порождающий паттерн, простым его сдвигом можно получить целое семейство других паттернов на растре с помощью соотношения:

(м) —^ р? >> (0,«).

(3.3)

Обозначим множество генерируемых таким образом паттернов П^.

1

8

Заметим, что соотношение (3.2) строит «преимущественно вертикальные» порождающие паттерны с наклоном вправо. На рисунке 3.4 приведен пример таких паттернов Р]8 с наклоном, изменяющимся в диапазоне [0, 7].

/ / / / / / /

Рисунок 3.4 — «Преимущественно вертикальные» порождающие паттерны Р]8 с наклонами £ = (0,1, 2,3,4, 5,6, 7) (слева-направо).

По аналогии может быть задано и множество «преимущественно вертикальных» паттернов с наклоном влево П?. Для этого требуется просто поменять знак в соответствующей координате векторе сдвига в соотношении (3.2). Если же в нем поменять местами значения сдвига \1/2~\ и 2к-1, то получатся уже «преимущественно горизонтальные» порождающие паттерны, из которых можно сформировать множества П? и П^. Каждое из указанных множеств П соответствует множеству прямых, укладывающихся в четыре определенных угловых диапазона: [0°,45°] для П?, [45°,90°] для П^, [90°,135°] для П? и, наконец, [135°,180°] для П^. На рисунке 3.5 продемонстрировано соотношение между указанными множествами и диапазонами углов.

У

х

Рисунок 3.5 — Связь между диапазонами углов и множествами порождающих

паттернов П.

Таким образом, алгоритм Брейди-Ёна является методом быстрого построения ПХ по одному из указанных наборов диадических паттернов. Тщательный анализ для одного из диапазонов углов приведен в недавней

работе [100]. Чтобы посчитать ПХ, т.е. построить отображение для всех прямых, требуется применить данный алгоритм четыре раза и объединить их результаты в единый Хаф-образ. Вопрос их объединения не является тривиальным, в деталях он рассмотрен в работах [101—103]. На рисунке 3.6 представлен результат вычисления БПХ-образа для всех диапазонов углов. Однако сразу отметим, что в ряде прикладных задач оказывается достаточным провести редукции только по некоторым из указанных наборов паттернов. Примеры таких случаев будут рассмотрены далее в данной главе диссертации.

Рисунок 3.6 — Пример вычисления БПХ-образа для полного диапазона углов: (а) исходное изображение; (б) инвертированный итоговый БПХ-образ (скобками сгруппированы строки, соответствующие множествам указанных паттернов, белому цвету соответствует область «незначащих» пикселей).

В результате, для того, чтобы получить Хаф-образ для изображения I требуется вычислить следующее структурное преобразование:

(а)

(б)

§ гнт = <

, +), Упы € Пр, К(пНг, +), УпНг € Пу,

¡, +), Уп 1 € пр,

г, +), Упг € пу.

(3.4)

Таким образом, задача вычисления БПХ также является задачей вычисления БСПИ.

Крайне важным является вопрос точности аппроксимации исходного множества «ближайших» дискретных прямых с помощью диадических паттернов. В работе М. Брейди [104] для квадратного изображения со стороной К максимальная ошибка аппроксимации была экспериментально оценена как 1 • 1одК. Это означает, что с увеличением размера изображения абсолютная ошибка аппроксимации растет сублинейным образом, а вот относительная ошибка в долях растра падает. Наконец, в работе [99] была доказана точная оценка неточностей аппроксимации прямых в алгоритме БПХ, которая полностью согласована с экспериментальными оценками М. Брейди.

3.2 Общие положения предлагаемого подхода

В качестве метода решения рассматриваемых задач автоматического определения угла наклона предлагается использовать методы, основанные на вычислении БСПИ, определяемого формулой (3.4).

Пусть I это входное изображение в градациях серого, а FHT(I) - его БПХ образ. В этом образе каждая строка соответствует некоторому направлению ф. Исходные задачи нормализации наклона сводятся к выбору индекса строки FHT(I), соответствующей искомому направлению а. Этот выбор базируется на использовании критерия f (г), который вычисляется для каждой строки г матрицы FHT (I ). В качестве критерия f (г) часто применяется сумма квадратов производной яркости [72; 95] (далее - SSG):

w— 1

f (г) = SSG(r) = r[c] — r[c — I])2. (3.5)

с=1

В формуле (3.5) w означает число столбцов FHT(I), а г [с] - значение яркости пикселя в строке г и столбце с. Искомый индекс выражается следующим образом:

ires = arg max f (r ). (3 6)

rerows(FHT(I)) V '

В ряде случаев, например при обработке печатных фрагментов или фрагментов, написанных кириллицей, в задаче \ ап ^ почти всегда встречаются наклоны только «вправо», при этом диапазон допустимых углов очевидно оказывается ограничен классом «преимущественно вертикальных» прямых, что позволяет обойтись вычислением единственного диапазона углов и тем самым существенно сократить количество операций.

На рисунках 3.7 приведены примеры результатов быстрых аппроксимаций ДПР, построенных с помощью алгоритма Брейди-Ёна, для производной, взятой по оси х. Квадранты соответствуют прямым с наклоном «вправо».

(а)

(б)

шт и II

а вмшит

Рисунок 3.7 — Примеры вычисления БПХ для одного квадранта Пу.

В задаче автоматического определения угла наклона предлагается анализировать не исходное изображение, а его производную по вертикальным и горизонтальным направлениям (из соображений симметрии) [56]. В задаче выпрямления текстового фрагмента более важными являются преимущественно вертикальные компоненты текстовых фрагментов, поэтому можно обойтись анализом производной, взятой только по оси х. Это позволяет нивелировать влияние преимущественно горизонтальных компонент.

Стоит отметить, что рукописное заполнение документов как правило отличается весьма высоким качеством и в основном имеет одно доминирующее направление, однако угол наклона может не попадать в один квадрант. Пример такого случая проиллюстрирован рисунком 3.8.

(а)

(б)

Рисунок 3.8 — Пример рукописного фрагмента с большим значением а.

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

рассматриваемый угол составлял аге1ап(1) = п/4, то после сжатия он увеличился до аге1ап(2), что соответствует примерно 63,5° (большие углы уже нет смысла рассматривать). Для возврата к наклону в исходном изображении достаточно просто умножить найденный на сжатой картинке наклон обратно в два раза.

Важной особенностью БПХ является использование неравномерной системы координат для результирующего аккумулятора [87]. Строке БПХ с фиксированным наклоном £ в ДПР соответствует угол:

где h - высота исходного изображения. Это приводит к тому, что каждая строка БПХ масштабирована относительно соответствующей строки в ДПР в kt = 1/cos (ф раз. Поэтому, при вычислении критерия по отдельной строке БПХ это обстоятельство требуется учитывать и умножать исходное значение критерия на функцию от kt, которая зависит от конкретного критерия. Для часто используемых критериев эти функции приведены в работе [105]. В частности, для критерия SSG эта функция равна Щ. Тогда, вычисляемый по строке t критерий SSGdrt с использованием БПХ приближается следующим образом:

Как видно из рисунка 3.6 для не квадратного изображения в

БПХ-образе |П£| = |Щ?|, |Щ>| = |Пр|, но |Щ>| = |П£|. Согласно

уравнению (3.7) это означает, что множества углов и Qy, покрываемые по горизонтали и вертикали соответственно, могут существенно различаться. Если возникает необходимость привести их к одному диапазону, то требуется зафиксировать одно из множеств, например Qh, в качестве опорного, и провести соответствующую интерполяцию значений другого множества к опорному (процедура Recalculate). Такая необходимость может возникнуть из следующего изображения: вертикальные и горизонтальные элементы изображения как правило перпендикулярны друг другу (линии разграфки, штрихи в буквах и т.д.), поэтому следует анализировать их совместный вклад [106]. Совместный вклад определяется суммой критериев с весами в и 1 — в соответственно (процедура Combine).

(3.7)

SSGdrt(t) ~ $ • SSGfht(t).

(3.8)

Приведенным выше описаниям соответствуют базовые алгоритмы А^^, и ^1ага, предназначенные для решения задач и соответственно 3.9.

I def deбlantег{I , к): 1 def deskebTer(l, в):

2 ¿Литап Dotvnscala{I, к.) 2

3 - И or i zimШ Derivative(i,h,w n) 3 Dx t— Horizontal Derivative^!)

1 I Dy <— VerticalDerivative(I)

Г) - P(wfHочдКТго.п$form (Dx, IIv) r> Fo-$tHotighTransform(D:i;, ilv)

fi fi FastHoughlVansform(Dy,llji)

7 К - height^j.) 7 Nv ^ hftight{T%)

8 8 Nh height{T^)

0 for i in rows () : for i in rowE(J-"|j) :

10 Kv\i\ <- P/(NV - 1)2 10 Kv[i] <r- /1 + P/{NV - I)2

л Cy[i] Kl\i\ ■ 11 Cv[i\ ■ SSGFHT{7%\A)

12 12

13 13 for i in rows (J-^) :

11 11 К и [г] 0+*2/№-1)2

15 15 СнЩ <- К% й -

16 16 Су 4— R<'CMlciilat(i(Cv)

17 17 С «- Combine(CH,0,CVf 1 - /?)

18 ^be&t i— iir^iiiiix (Cv) 18 ibejit argmax (C)

10 ^be&t 4— к ' i'beif 10

20 ft Cretan (if f,eBi) 20 a arctan(sbeit)

21 return o 21 return r*

Листинг 1: Алгоритм Aalant. Листинг 2: Алгоритм

Рисунок 3.9 — Листинги алгоритмов.

3.3 Экспериментальные результаты

Для проведения вычислительных экспериментов необходимо зафиксировать тестовые корпуса данных и способы оценки точности определения угла наклона в рамках задач Vskew и Vsiant. Такие способы описаны в подразделе 3.3.1, после чего в подразделе 3.3.2 приводится описание тестовых корпусов данных для ^Dsiant и результы вычислительного эксперимента по выпрямлению текстовых фрагментов. Подраздел 3.3.3 повторяет структуру предыдущего раздела для вычислительного эксперимента по определению угла наклона документа.

3.3.1 Способы оценки точности определения угла наклона

В 2013 году был проведен конкурс Document Image Skew Estimation Contest (далее - DISEC) [45], посвященный задаче Vskew. Организаторы конкурса отобрали 155 различных документов, каждый из которых представлен десятью изображениями со случайными углами наклона в диапазоне ±15° с указанием соответствующего эталонного значения угла. Эти документы существенно различаются по размерам бумажного листа, содержат различные виды алфавитов и начертаний символов, на части документов присутствуют разнообразные графические элементы, а также табличные структуры. По завершению конкурса были опубликованы отранжированные результаты всех присланных методов, а сам корпус данных выложен в открытый доступ [107] и де-факто стал базовым корпусом данных для задачи

^skew.

В рамках DISEC было предложено три способа оценки точности определения угла наклона [45]. Для каждого изображения вычисляется E -модуль отклонения полученного угла наклона от эталонного значения, выраженного в градусах. На множестве всех полученных модулей отклонений вычисляются следующие величины: (а) AED - среднее значение отклонения;

(б) ТОР80 - среднее значение отклонения среди 80% лучших значений;

(в) CEt - доля отклонений, меньших порога t (по утверждению организаторов

порог различения ошибки в задаче Vskew составляет 0.1°).

1 N

AED = Ег (3.9)

¿=0

1 М

ТОР80 = —SE% = sorted(E), М = 0.8 • N (3.10)

¿=0

1 N

CEt = NJ2E < t]. (3.11)

i=0

В критерии CE [•] означает скобку Айверсена. Значения первых двух критериев требуется минимизировать, последней - максимизировать. В данной работе при проведении обоих вычислительных экспериментов используются эти же критерии.

3.3.2 Нормализация текстовых фрагментов

Описание тестовых корпусов данных

В 2019 году была опубликована работа С. Бера и его соавторов [108], посвященная проблеме геометрической нормализации рукописных текстовых фрагментов, в рамках которой было представлено несколько корпусов данных для проведения вычислительных экспериментов. В трех корпусах K-ben, K-hin и fcENG содержатся изображения реальных рукописных фрагментов на бенгали, хинди и латинице соответственно. Каждый из них состоит из 500 образцов, повернутых на некоторый угол askew и скошенных на некоторый угол as i ant. Точные значения этих углов закодированы в имени соответствующих файлов и выступают в качестве эталона. В рамках данного эксперимента для задачи Vsiant интерес представляет только определение угла a s i ant. Поэтому все изображения были предварительно довернуты на эталонное значение угла, предоставленного авторами, в результате чего были сформированы корпуса K-BiEN, ^HfiN, ^Еж?, на которых в дальнейшем и производились измерения. На рисунке 3.10 приведены примеры текстовых фрагментов из исходных и довернутых на эталонный угол корпусов данных.

(а) (б) (в)

(д)

Рисунок 3.10 — Примеры изображений из корпусов данных, взятых из работы [108] (верхний ряд) и соответствующие результаты предварительной нормализации (нижний ряд): (а) К,вем; (б) ; (в) К-емс] (г) ^ВзЕМ]

(д) К

desk . (v^desk

HIN; (е) ^ENG.

К сожалению, в описанных выше датасетах отсутствуют кириллические текстовые фрагменты. Поэтому в рамках текущей работы были сформирован

дополнительный корпус данных 1Сшб• Он состоит из 2750 рукописных фрагментов, извлеченных с изображений паспортов гражданина Российской Федерации, полученных с помощью сканирования и фотографирования носителей камерами мобильных устройств. Примеры текстовых фрагментов приведены ранее на рисунке 3.2. Все фрагменты в К-жв состоят исключительно из кириллического или цифрового заполнения, для каждого фрагмента также представлен эталонный угол его наклона. Для рукописного текста, в отличие от печатных образцов, такой угол не всегда может быть указан однозначным образом ввиду неравномерности наклона внутри строки или же специфики самого содержимого. В таких случаях угол наклона указывался в соответствии с ожидаемым экспертом значением. В соответствии с распространенной конвенцией [45; 108], значение эталонного угла закодировано в именах файлов. Все используемые корпуса данных, включая предварительно нормализованные корпуса из работы [108], выложены в открытый доступ по адресу ftp://smartengines.com/text-norm-fht.

Распределения углов наклона для рассматриваемых в работе корпусов данных проиллюстрированы рисунками 3.11а-г.

(а) (б)

Рисунок 3.11 — Распределение угла наклона текстовых фрагментов в корпусах данных: (а) КВеи; (б) £нт; (в) КеиС; (г) Кшб.

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

Результаты экспериментов

Для замеров точности и скорости решения задачи Vsiant использовалось два алгоритма: А^^ и Af^t. Первый алгоритм описан листингом 1, а второй выступает в качестве референтного. По сути, он является модификацией А™^ с заменой вычисления БПХ на ДПР.

При вычислении ДПР требуется явно указывать шаг угла (в градусах), а также минимальное и максимальное значение обрабатываемых углов. Поскольку эталон для изображений в используемых корпусах данных установлен в 1°, то и для критерия CEt был установлен такой же порог различения, как и шаг угла при вычислении ДПР.

Напомним, что по построению БПХ, покрываемый им набор углов зависит от размеров входного изображения. Поскольку из рисунков 3.11 видно, что диапазона [-45°, + 45°] не хватает для полноценной обработки

л р тгт

данных, то в случае AralI^r^t используется описанный ранее прием с сжатием изображения в два раза по горизонтали, чтобы полностью покрыть весь требуемый диапазон углов (хотя из вида распределения на рисунке 3.11г необходимость такого шага уже не выглядит очевидной). Поэтому диапазон обрабатываемых углов для Af^t установлен в [-64°;+64°].

На рисунке 3.12 проиллюстрированы основные этапы процесса обработки изображения WENG_001 со словом «Anemone». На данном примере ответы алгоритмов Af¿^t и А^^ совпали и оказались равны -22°, в то время как значение эталонного угла наклона равно -28°. Таким образом для данного примера ошибка обоих методов составляет 6°.

Средний размер символа в указанных корпусах данных составляет 50 х 40 пикселей. В таблице 2 показано насколько сильно влияет неточность определения угла наклона на смещение символов по горизонтали.

Рисунок 3.12 — Визуализация результатов основных этапов работы алгоритмов

afhtи adrt

^ slant и ^ slant'

Таблица 2 — Смещение символа по горизонтали в зависимости от ошибки определения угла наклона текстового фрагмента IE|.

Ошибка (°) Смещение (px) Доля символа (%)

1.00 0.870 2.18

2.50 2.185 5.46

5.00 4.375 10.94

7.50 6.585 16.46

10.00 8.815 22.04

На рисунке 3.13 проиллюстрировано распределение |Е| - модуля отклонений угла наклона текстовых фрагментов от эталонных значений для алгоритма А™^ для корпусов данных 1Свек, К-нт, К-емс, и К-тя- Для удобства отображения на данном рисунке используется логарифмическая ось ординат.

О 10 2 0 30 40 50 6 0 70 0 10 20 30 40 50

Угол наклона, * Угол наклона, *

Рисунок 3.13 — Распределение модуля отклонений угла наклона текстовых фрагментов от эталонных значений Е для алгоритма A^^t в корпусах данных:

(a) Kben; (б) IChin; (в) 1СENG; (д) К,rus.

Предлагаемые методы реализованы на языке программирования C++ с использованием открытого компилятора GCC версии 11.4.0 и открытой библиотеки компьютерного зрения OpenCV. БПХ-образы для прямых вычислены с помощью OpenCV-contrib - ее открытого расширения. Все показатели производительности получены на ПК под управлением ОС Ubuntu 22.04.4 LTS, на базе процессора AMD Ryzen 7 2700X.

Полученные результаты работы методов нормализации наклона представлены далее в таблице 3. Из таблицы видно, что метод на основе БПХ работает гораздо быстрее аналога с использованием ДПР (в некоторых случаях - на порядок), при этом разность в точности детекции оказывается не столь значительной. При этом ошибка в 6 градусов, как следует из рисунка 3.12 не является серьезной, а время работы метода позволяет свободно использовать его в рамках СРИСД, в том числе и тех, что функционируют на мобильных устройствах. Следует отметить, что с помощью предварительной обработки изображения можно повысить точность

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

Таблица 3 — Результаты замеров на корпусах данных для задачи Vaiant.

Алгоритм Корпус AED (°) TOP8O (°) CEi.0 (%) t'mean (мс) tstd (мс)

ADRT ^ slant V"desk /V-BEN V"desk /V-HIN desk ^ENG K-RUS 7.142 6.716 5.606 4.729 4.365 2.940 3.600 2.082 17.8 25.2 19.2 29.7 85.629 86.351 91.335 95.673 13.703 17.243 12.191 30.915

AF НТ ^ slant desk ^BEN desk ^HIN desk ^ENG K-RUS 7.923 7.010 6.177 3.850 4.884 3.336 3.907 2.131 10.2 16.0 11.4 23.4 2.816 2.704 4.380 1.881 1.390 1.269 2.324 0.852

3.3.3 Нормализация угла наклона документа

Для вычислительных экспериментов, связанных с задачей 'Одке-ш, будем пользоваться описанным ранее в подразделе 3.3.1 корпусом данных Э^ЕО. Распределение углов наклона на корпусе данных ЭКЕС проиллюстрировано рисунком 3.14.

Угол

Рисунок 3.14 — Распределение углов наклона на корпусе данных ЭКЕС.

Как и в предыдущем разделе, рассмотрим как на целевом корпусе данных работают алгоритмы Aи А^^, основанные на вычислении ДПР и БПХ, соответственно. При этом, учтем что максимальное значение угла наклона в данном корпусе данных по модулю не превышает 15°, а ожидаемая точность определения угла наклона по мнению организаторов конкурса составляет 0.1°, что соответствует функции оценки CEo.i. Требуется отметить, что в контексте функционирования СРИСД подобная точность является избыточной. На практике все последующие этапы обработки изображения документа должны толерировать, как минимум, ошибку в один градус.

Заметим, что по сравнению с задачей Vsiant, линейные размеры изображений в данной задаче существенно больше. Из-за этого скорость работы методов может стать серьезной проблемой. Поэтому для начала проведем замер метода Af^ в диапазоне углов [-15°, + 15°] с шагом в 1°. В таком случае, для каждого изображения потребуется вычислить (2 • 15 — 1) проекций.

В таблице 4 приведено время работы данного метода на корпусе DISEC. Из таблицы видно, что время работы метода является неприемлемо долгим.

Таблица 4 — Результаты замеров времени для метода Afk^с шагом в 1° на корпусе данных DISEC.

tmean Tstd tmin ^25% ¿50% ¿75% tmax

0.224336 1.130996 0.051732 0.075375 0.106428 0.122396 16.033500

Результаты по точности детекции угла приведены в таблице 5. При дальнейшем повышении углового разрешения время работы ощутимо увеличивается. Так, для изображения с размерами 1095 х 894 пикселей, взятого из корпуса данных DISEC, число проекций для БПХ составит 3975 (для горизонтальных и вертикальных направлений) и время его вычисления составляет 45мс, в то время как для ДПР для того же числа проекций потребуется уже 21000мс (данный замер был получен на ПК под управлением ОС Ubuntu версии 18.04 с процессором AMD Ryzen 7 1700).

В таблице 5 приведена точность работы некоторых методов на корпусе данных DISEC. Метод LRDE-EPITA-a, представленный в работе [109], основан на специальной предобработке изображения и последующего анализа его Фурье-образа. Метод, представленный в статье [110], находит на изображении линии специального вида и оценивает угол наклона путем

взвешенного голосования на множетсве данных линий. Метод ЬКЭЕ-ЕР1ТЛ-Ь также основан на предобработке изображения и последующим анализом образа «классического» преобразования Хафа. Следует отметить, что полученное значение ОЕ у предлагаемого метода существенно хуже, чем у метода ЬЯОЕ-ЕИТА-а. Максимальная ошибка на корпусе данных составляет всего 0.57°, что указывает на то, что метод не порождает на нем грубых ошибок. В методе А^^ для БПХ вычисляется весь покрываемый диапазон углов в [-45°, + 45°], однако оцениваются только те углы, что входят в допустимый диапазон по условиям задачи.

Таблица 5 — Результаты замеров некоторых методов на корпусе данных ОТБЕО.

Метод ЛЕБ (°) ТОР80 (°) СЕ(%)

ЬЯОЕ-ЕИТА-а 0.072 0.046 77.48

Л^и-БШ 0.085 0.051 71.23

ЬНБЕ-ЕР1ТЛ-Ь 0.097 0.053 68.32

Сашега 0.184 0.057 68.90

ОУЬ-Т^1ЕК 0.103 0.058 65.42

лВКТ ^вке-ш 0.411 0.240 18.80

Арнт 0.083 0.054 68.80

Распределение ошибок Е на корпусе данных ЭКЕС приведено на рисунке 3.15.

о

-0.4 -0.2 0.0 0.2

Рисунок 3.15 — Распределение ошибок Е на корпусе данных ЭКЕС.

Поскольку в ЭКЕС каждое изображение представлено 10 различными наклонами, была произведена группировка изображений и оценивались критерии внутри получившихся групп. Десять худших групп были отобраны и представлены в таблице 6.

Таблица 6 — Распределение ошибок по группам изображений на корпусе данных

ЭКЗЕС.

Индекс AED(0) TOP80(°) CE(%) ем ах (0) емт(0) Ееаысе (0)

68 0.307 0.299 0.0 0.340 0.266 0.074

74 0.279 0.249 0.0 0.417 0.125 0.292

18 0.260 0.235 0.0 0.406 0.124 0.282

61 0.256 0.245 0.0 0.315 0.211 0.104

84 0.253 0.244 0.0 0.305 0.202 0.103

20 0.246 0.222 0.0 0.355 0.109 0.246

40 0.243 0.232 0.0 0.289 0.212 0.077

99 0.237 0.225 0.0 0.308 0.182 0.126

35 0.229 0.222 0.0 0.258 0.188 0.070

65 0.228 0.220 0.0 0.265 0.183 0.082

Дополнительно была проведена группировка всех примеров изображений с шагом в один градус. Внутри полученных групп было оценен показатель ЛЕЭ. Результат проиллюстрирован рисунком 3.16.

Рисунок 3.16 — Распределение ошибок по наборам изображений, сгруппированным с шагом в один градус, на корпусе данных ЭКЕС.

3.4 Выводы по главе

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

СРИСД: задаче нормализации угла изображения документа и задаче нормализации угла наклона отдельно взятого реквизита. Типовой подход к решению данных задач опирается на использование ПХ. В данной главе приведены решения указанных задач на базе анализа БПХ-образа, построение которого соответствует построению БСПИ. Замена ПХ на БПХ благотворно сказывается на производительности методов детекции углов наклонов (в ряде случаев - в десятки раз). Для задачи Vsiant это наглядно продемонстрировано таблицей 7.

Таблица 7 — Выигрыш в производительности для задачи Vsiant.

Корпус topt/t

V"desk /v-BEN desk ^HIN desk ^ENG K-rus 30.40 31.93 20.85 50.86

На базе единого подхода синтезировано два алгоритма А^^ и А^Ш, которые не требуют ни проведения предварительной бинаризации входного изображения, ни выделения компонент связности, однако способны при этом эффективно обрабатывать широкие диапазоны углов. Реализации предложенных методов были апробированы на открытых корпусах данных, специфичных для указанных задач. Конкретнее, алгоритм детектирования угла наклона документа апробировался на известном корпусе данных DISEC, а алгоритм определения наклона текстового фрагмента - на корпусах данных из работы [108] и на расширенном наборе данных K-rus , подготовленным и опубликованным диссертантом.

Предложенные методы могут быть внедрены, например, в промышленные СРИСД для обработки ДУЛ, в том числе функционирующих на мобильных устройствах, где вопросам быстродействия традиционно уделяется повышенное внимание.

Алгоритм А^т был впервые реализован автором и внедрен в рамках СРИСД «Cognitive Forms» компании «Cognitive Technologies». Он пережил несколько модификаций и впервые был представлен автором в работе [145]. Алгоритм А^ был реализован автором диссертации и опубликован в работах [143; 144]. Обобщающая результаты работа по нормализации текста с помощью БПХ была представлена автором в статье [149].

В настоящее время имплементации предложенных алгоритмов внедрены и широко используются в СРИСД «Smart ID Engine», «Smart Document Engine» и «Smart Code Engine» компании ООО «Смарт Энджинс Сервис», в том числе и рамках обработки изображений документов с помощью мобильных устройств.

Глава 4. Автоматическая типизация сканированного изображения

структурированного документа

В данной главе рассматривается применение СПИ в задаче определения типа структурированного документа Ttype при потоковом вводе машиночитаемых анкет, цифровой образ которых получен с помощью сканера. Напомним, что такая задача возникает в СРИСД в модуле идентификации типа документа и установления его внутренней системы координат Mt, а результат ее решения определяет весь дальнейший контекст обработки изображения документа.

Далее в разделе 4.1 обсуждается актуальность задачи идентификации типа документа без использования поиска атрибутов и описывается подход к типизации документов на основе метода деформации объектов, а также класс документов, для которого осмысленно его применение. Раздел 4.2 посвящен проблемам, характерным для выбранного метода, а именно влиянию ориентации документа на вид его параллельных проекций и варьированию заполнения реквизитов от одного образца документа к другому. В разделе 4.3 приводится краткое описание метода трансформации временной оси из области динамического программирования, используемого в данной главе для решения задачи типизации. Описание предлагаемого алгоритма типизации Afypl приводится в разделе 4.4. Для рассматриваемого метода типизации документов в разделе 4.5 предлагается алгоритм автоматического построения эталона типа документа по набору образцов А^у.аре. В заключительном разделе приводится обсуждение работы алгоритма и достигнутых результатов на примере распознавания квитанций об оплате водоснабжения в рамках единого информационно-расчетного центра (далее - ЕИРЦ), а также способ его оптимизации и синтеза алгоритма A%!ype.

4.1 Типизация документов на основе деформации объектов

В разделе 1.1.2 были кратко освещены основные подходы к решению задачи Цуре. Методы идентификации структурированного типа документа

существенно различаются в зависимости от класса трансформаций бланка документа, допустимого внутри типа.

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

Рассмотрим класс структурированных документов С, при регистрации которых выполняются следующие условия:

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

2. модель класса допустимых искажений это «сдвиг, поворот, масштаб» (в пределах 10%), с допустимой незначительной локальной деформацией.

К данному классу относятся, например:

— развороты паспортов, деформированные за счёт неточного совмещения листов в тетради;

— анкеты, распечатываемые из файлов, случайно масштабированные в пределах 10% в зависимости от драйвера принтера;

— «жировки» ЕИРЦ, представленные большим количеством разнотиражных бланков, отличающихся шириной зазоров в таблице.

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

Задача ТгУРе для документов из С может быть сведена к задаче оптимальной деформации представления документа до соответствия одному из набора эталонов, определяющих типы документов. К сожалению, даже лучшие из известных алгоритмов «эластичного совмещения» изображений имеют сложность не менее 6) для растров ЯмхМ [111]. Поэтому интерес

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

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

Сведения о показаниях квартирных приборов за

Ф.ИО ГЕДНЕ8А Е А Адрес: Мурамокчаяул.,д.6.№. 153

Предоставить до 3-го числе кеящого месяца в ЁИРИ района Бибирево ул. Пришвина, За

1686133335 Холоди» мдосиаенйнив Горячее водоснабжение

Номер сметчика N»0535778 N105014029

Показания огетчяка □□□ППИНЛСЕ □□□□□шша

Рисунок 4.1 — Пример параллельных проекций изображения документа на оси

координат.

Вопросами восстановления структуры объекта большей размерности по его проекциям меньшей размерности занимаются в области реконструктивной томографии. На рисунке 4.2 продемонстрированы результаты томографической реконструкции нормализованного по углу изображения документа по двум его ортотропным проекциям.

1686138825

94 (б)

;г) (д) (е)

Рисунок 4.2 — Примеры изображений документов различных типов и результат их томографической реконструкции по двум проекциям: (а) «жировка» ЕИРЦ; (б) бланк «Инвестиционный портфель»; (в) регистрационный бланк;

(г-е) реконструкция (а, б, в) соответственно.

Данная реконструкция проведена «классическим» методом фильтрованной обратной проекции (англ. filtered back projection) [112]. Из приведенного рисунка видно, что две проекции вполне могут быть использованы в качестве описателя типа документа.

Для сравнения структур проекций с соответствующими эталонами предлагается использовать алгоритм динамической трансформации временной оси (англ. dynamic time warping, далее - ДТВО) [113], описанного далее в разделе 4.3.

4.2 Потенциальные проблемы метода

Алгоритмы типизации документов, как с использованием графических примитивов, так и основанных на атрибутивном поиске, обладают общим недостатком. И выделение примитивов, и распознавание реквизитов документа зачастую требуют корректной бинаризации изображения, то есть решения задачи Тып. К сожалению, опыт показывает, что для корректной бинаризации документа требуется априорное знание его типа. Проиллюстрируем данное утверждение рисунком 4.3 [142].

АНАТОЛИЙ ВАСИЛЬЕВИЧ

(а) (б) (в)

Рисунок 4.3 — Пример бинаризации пенсионной карточки гражданина РФ. (а) Исходное изображение; (б) бинаризация методом Ниблека, настроенного для обработки типового бланка; (в) специализированная настройка алгоритма бинаризация для документа типа «пенсионная карточка».

Метод Ниблэка является одним из самых универсальных методов бинаризации [114]. На рисунке 4.3б приведен результат применения этого метода к изображению карточки пенсионного страхования 4.3а. Неудовлетворительный результат связан с тем, что данные карточки обладают текстурным фоном с контрастом, близким к контрасту заполнения. Однако если воспользоваться априорным знанием о структуре фона данного типа документа, то результат бинаризации может быть существенно улучшен (рисунок 4.3в). К сожалению, не существует методов бинаризации, одинаково хорошо применимых ко всем типам документов.

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

К сожалению, ошибка углового позиционирования документа на сканере может достигать пятнадцати градусов [45]. Как было показано ранее в главе 3 подобный наклон может полностью разрушить яркостные проекции. Поэтому при таком подходе критически важным этапом становится проведение предварительной геометрической нормализации изображения для нивелирования существенного варьирования вида получаемых проекций, то есть устранение угла наклона образа документа, например, методом из главы 3. На рисунке 4.4 приведен пример неточно нормализованного документа типа ТЕ1ЕС.

Рисунок 4.4

Пример изображения неточно нормализованного документа типа

гр ЕШС

На рисунке 4.5 приведена проекция яркости на ось У документа типа ТЕ1ЕС, изображенного на рисунке 4.4.

120 -|

100 -

80 - Л I Д

60 ■ У Л И \ А п\

40 - А 11[у \ 1 / 1 ЛЛ

20 ■ \г V и У и |

8 15 22 29 36 -В 50 57 М 71 78 Э5 92 99 106

Рисунок 4.5 — Параллельная проекция яркости на ось У документа типа ТЕ1ЕС,

изображенного на рисунке 4.4.

На рисунке 4.6 приведена параллельная проекция яркости на ось У документа типа ТЕ1ЕС, изображенного на рисунке 4.4, после его точной геометрической нормализации.

250

1 8 15 22 29 36 43 30 57 64 71 73 85 92 99 106

Рисунок 4.6 — Параллельная проекция яркости изображения на ось У документа типа ТЕШС с рисунка 4.4, после его геометрической нормализации.

На рисунке 4.7 эталон проекции яркости на ось У для типа документа, изображенного на рисунке 4.4.

300

1 6 11 16 21 36 31 36 41 46 51 56 61 66 71 76 81 86 91

Рисунок 4.7 — Эталон проекции яркости на ось У для типа документа,

изображенного на рисунке 4.4.

Очевидно, что изображения 4.7 и 4.6 похожи друг на друга.

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

4.3 Алгоритм динамической трансформации временной оси

В данном разделе кратко опишем алгоритм динамической трансформации временной оси [113], используемый в данной главе для

сравнения двух проекций изображения. Пусть заданы две числовые последовательности X = х\,х2,... ,х\х| и Y = у\,у2,... ,У\у|. Первую последовательность будем называть образцом, вторую последовательность -эталоном. Пусть требуется найти путь деформации двух последовательностей, а также его длину. Путем деформации будем называть последовательность вида:

W = W!,W2,...,w\K\, тах(\Х\,\Y|) < К < \Х\ + \Y|, wk = (i,j) (4.1)

В формуле (4.1) индекс i соответствует последовательности X, а индекс у последовательности Y. Для пути деформации определим его длину:

к

Dist(W) = ^ Dist(X(wkti),Y(wk,2)) + nd • Pdel + пг • Pms (4.2) k=1

В формуле (4.2) через Dist(Xt,Yi) обозначено расстояние между элементами числовых последовательностей (например, Евклидово), и пг -число вставок в образец и эталон, а Pdei и Pins - величина штрафов за вставку в образец и эталон соответственно. Тогда задача состоит в поиске пути деформации минимальной длины.

Данная задача может быть решена методами динамического программирования [115] в два прохода. Цель прямого прохода - вычислить меру различия двух последовательностей. Для этого производится заполнение матрицы расстояний по правилу (4.3):

D(i,j ) = Dist(i,j)+ mrn[Pdel + D(i - lj); D(i - l,j -1); Pms + D(i,j -1)} (4.3)

Последовательность точек (i,j) определяет путь, каждая точка которого обеспечивает локально-оптимальное соответствие между ¿-ой точкой образца и j-той точкой эталона. По окончании заполнения матрицы D в ее правом нижнем углу будет содержаться мера различия двух последовательностей.

Обратный проход по уже установленному пути позволяет восстановить оптимальное соответствие последовательностей.

4.4 Алгоритм идентификации типа документа

Приведем формальную постановку задачи типизации документов. Пусть задано конечное множество рассматриваемых типов

документов Т = {¿1,^2,.. Л^}. Пусть для входного изображения I зафиксирован некоторый способ ^ для построения его описателя и для каждого элемента из множества Т известны эталонные описатели типов документов £ = {е1,^,...ем}. Пусть определен способ оценки близости 0(е(1{), )), где ) описатель для входного изображения, а е(1,{) - описатель эталона. Тогда, задача определения типа документа Цуре сводится к выбору наиболее близкого эталона к описателю:

це81 = а^ш1п И(е(1г), П(1)) (4.4)

Чтобы добиться устойчивости относительно вариации заполнения, предлагается ввести весовую функцию в алгоритме ДТВО:

Щ = , (4.5)

+

где - штраф несоответствия значению проекции образца в точке ] эталонному значению еГ1 в точке г, а\ - оценка дисперсии значения по выборке документов, а а20 ^ 0 - экспериментально подбираемый параметр. В результате алгоритм будет фактически игнорировать невязки сопоставления в зонах заполнения документа.

Итак, предлагаемый алгоритм А\урее использует в качестве эталона каждого типа документов 4 массива (ех, ах,еу, ау), и состоит из следующих четырех шагов:

— Шаг 1. Автоматическая ориентация образца документа.

— Шаг 2. Вычисление проекций яркости исследуемого изображения на координатные оси.

— Шаг 3. Вычисление расхождения полученных проекций с эталонными (для каждого типа документов, обрабатываемых в потоке).

— Шаг 4. Выбор наиболее подходящего эталона (давшего минимальную меру расхождения) и соответствующего ей типа документа.

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

На первом шаге для автоматической ориентации образца документа можно воспользоваться методом на базе анализа БПХ-образа, представленным ранее в главе 3.2. Напомним, что каждой строке БПХ соответствует проекция изображения на некоторое направление (раздел 3.1). Определив наклон документа по БПХ образу, можно идентифицировать те проекции, которые станут ортотропными после нормализации наклона изображения. Тогда можно не вычислять проекции повторно, а просто «забирать» их из БПХ образа и, тем самым, уменьшать количество требуемых операций в предлагаемом методе. Это позволяет синтезировать оптимизированный алгоритм отличающийся меньшей вычислительной

сложностью шага 1.

4.5 Алгоритм автоматического построения эталона типа документа

Рассмотрим теперь важную задачу автоматического построения эталона типа документа по набору образцов изображений документов этого типа. Предполагается, что количество образцов для каждого типа документа не должно превышать к. Для построения такого эталона предлагается алгоритм

ЛеЬа . ^Ьуре'

— Шаг 1. Сориентируем каждый образец.

— Шаг 2. Для всевозможных пар образцов оценим взаимное соответствие образцов алгоритмом (о^ равно 0) и найдём наилучшую пару.

— Шаг 3. Усредним образцы с учётом взаимной деформации.

— Шаг 4. Среди оставшихся образцов найдём ближайший к усредненному алгоритмом (Ог считается равной 0). Если число усреднённых образцов меньше к, перейдём к Шагу 3.

— Шаг 5. Усредним образцы с учётом взаимной деформации и оценим Оi

— Шаг 6. Если набор не исчерпан, то среди оставшихся образцов найдём ближайший к усреднённому и перейдём к Шагу 5.

После выполнения указанной последовательность шагов, эталон для типа изображения оказывает построен.

На основании оптимизированного алгоритма была разработана

программа для автоматической идентификации типа документа, позволяющая выделять квитанции ЕИРЦ об оплате водоснабжения из смешанного потока документов 8 различных типов. Приемочное тестирование проводилось на наборе из 2000 изображений документов, 500 из которых составляли искомые квитанции. Из них правильно были идентифицированы 498 документов. Случаев ложной идентификации не произошло. Среднее время сравнения двух проекций документов при реализации метода на языке программирования C++ с помощью компилятора GCC составляет 0.5мс на процессоре типа AMD Ryzen 5 5600X.

В дальнейшем, подобный подход стал активно применяться, например, в задаче автоматического выбора типа номера автомобиля [116].

4.6 Выводы по главе

В данной главе представлен алгоритм идентификации типа документа Afypt для обработки входного потока сканированных документов фиксированной геометрии, подверженных небольшим деформациям в модели «сдвиг, поворот, масштаб». Алгоритм не требует ни предварительной бинаризации входных изображений, ни выделения графических примитивов, ни ключевых точек изображения, ни предварительного распознавания, ни применения решений на базе ИНС. В своей основе алгоритм опирается

на вычисление сразу двух СПИ. Первое используется для определения угла наклона документа с помощью преобразования Хафа Xht, второе для сбора вертикальной и горизонтальной проекции изображения на координатные оси Хц. Данные проекции служат в качестве описателя документа, а его типизация проводится путем деформации данного описателя до ближайшего эталонного описателя. Данная деформация осуществляется с помощью классического алгоритма из области динамического программирования, а именно ДТВО. Для устойчивости к варьированию заполнения предложен специальный способ подсчета отклонения. Для рассмотренного алгоритма

предложена процедура автоматического построения эталонов документов по набору образцов

В завершающем разделе главы показано как синтезировать оптимизированную версию алгоритма А%уре за счет замены СПИ соответствующего вычислению ПХ на БСПИ соответствующее БПХ. Такая замена позволяет не только провести нормализацию изображения значительно более эффективным образом, но и извлечь пару параллельных проекций сразу из БПХ-образа.

Алгоритмы Ajf£pe и A^ypl были впервые опубликованы автором диссертации в работе [142]. Реализация данных алгоритмов интегрирована в СРИСД «Cognitive Forms» компании «Cognitive Technologies» и прошла успешную апробацию в задаче выявления квитанций ЕИРЦ об оплате водоснабжения без случаев ложной идентификации типов.

Глава 5. Генеративное распознавание поврежденных матричных

кодов

В данной главе рассмотрим задачу распознавания штриховых кодов %аг, которая возникает в рамках модуля Мг.

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

К первой группе относятся коды, графические образы которых состоят из чередующихся черных и белых полос (штрихов) различной ширины и, возможно, высоты. Это, исторически первое, поколение штрихкодов часто именуется «линейными» штрихкодами. К нему относятся такие популярные символики как UPC, EAN, I2of5, Code128. Штрихи принципиально различной высоты используются, например, в символике 1MB, широко используемой в почтовой службе США.

Оставшиеся две группы объединяются под названием «двумерных» или «матричных» кодов. Для не специалиста их графические образы выглядят как множество чередующихся в случайном порядке черных и белых элементов, размещенных, как правило, в узлах прямоугольной (чаще квадратной) решетки. Эти элементы решетки вместе с соответствующими им бинарными значениями называются «модулями» и расположены они не случайным образом, а в строгом соответствии со спецификацией символики.

Форма модулей чаще всего является квадратной или прямоугольной, хотя иногда встречаются и круглые модули. В таком случае штрихкоды носят названия «точечных».

Отличие между двумя группами матричных кодов состоит в том, как именно формируются их структуры. В первом случае они получаются путем наложения нескольких линейных штрихкодов друг на друга в одну «стопку» (англ. «stacked»), и обрамляются вспомогательными модулями, отвечающими за хранение параметров, необходимых для чтения всего кода. Наиболее популярным представителем такой группы является символика PDF417 [117]. Во втором же случае все множество модулей определяет один штрихкод целиком. Повсеместно используемыми примерами таких символик являются DataMatrix, Aztec и, конечно же, QR-коды.

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

На этапе проектирования более емких кодов указанные недостатки были учтены и сейчас все распространенные матричные символики позволяют успешно их преодолеть. Во-первых, информация в них кодируется по двум направлениям небольшими модулями, что позволяет существенно повысить плотность информации на единицу площади. Во-вторых, к исходному сообщению добавляются специальные проверочные блоки данных, что делает возможным детектирование и исправление ошибок в процессе декодирования. Для этого широко используются коды Боуза-Чоудхури-Хоквингема, а именно - циклические коды Рида-Соломона. Вопросы обработки данных кодов прекрасно освещены в популярной монографии [118].

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

К первой группе относятся ориентационные модули - их значение фиксировано для каждой символики, а назначение - служить метками для алгоритмов локализации и для определения ориентации штрихкода. Такие группы модулей, схожие со статическими элементами бланков документов, не изменяются от образца к образцу и не содержат никакой информации об исходном закодированном сообщении. Алгоритм чтения ориентирует штрихкод, основываясь на значениях этой группы модулей. Например, для распространенной символики типа Aztec [119] используется специальный шаблон поиска в виде набора вложенных концентрических квадратов, расположенных в центре кода, часто называемого «bullseye», по углам которого размещаются группы ориентировочных модулей (способ поиска данного ориентировочного шаблона описан, например, в работе [120]). Четыре группы ориентировочных модулей по углам шаблона поиска и состоят из 3, 2, 1 и 0 черных модулей соответственно, а порядок их расположения строго

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

Ко второй группе относятся модули, содержащие метаинформацию -алфавит кодируемого значения, длину закодированной строки и т.д. Алгоритм распознавания настраивает свои параметры по этой группе модулей перед началом работы. Третья группа содержит исходную закодированную информацию и контрольные кодовые слова, необходимые для ее восстановления в случае повреждения отдельных модулей. На рисунке 5.1 показана структура расположения упомянутых групп модулей для штрихкода Aztec символики.

Рисунок 5.1 — Цветовое кодирование модулей Aztec кодов: метаинформационные - желтый, группы ориентировочных - зеленый, шаблона поиска - голубой, шаблона синхронизации - красный, информационные - без цвета. Цифрами показано упорядочение ориентировочных модулей.

Как правило, работа систем чтения штрихкодов подразделяется на несколько основных этапов [121]. На первом из них на входном изображении грубо локализуются зоны, содержащие изображение штрихкода. Затем, внутри этих зон точно определяются его границы и опорные элементы [122], после чего он сегментируется на отдельные модули. Из этих модулей составляется битовая матрица штрихового кода, которая подается на вход декодеру. Декодер, в соответствии со спецификациями символик, извлекает из матрицы значения в определенном порядке и формирует из них битовые последовательности. Затем в этих последовательностях с помощью кодов коррекции исправляются ошибки и восстанавливается оригинального сообщение или же принимается решение об отказе от чтения. На рисунке 5.2 приведена типовая схема чтения штрихового кода с учетом целевых особенностей различных групп модулей.

Рисунок 5.2 — Типовая схема обработки изображения штрихкода.

Важно отметить, что, как правило, уже на самых ранних стадиях выполняется бинаризация изображения штрихового кода [123]. Это существенно упрощает работу алгоритмов чтения, однако при этом часть информации может оказаться утерянной. Выбор подходящего метода бинаризации является нетривиальной задачей, особенно в условиях неконтролируемой съемки (например, с использованием мобильного телефона) [124; 125]. Поэтому вопросам бинаризации штриховых кодов в литературе уделено много внимания, а сами методы зачастую являются символико-ориентрированными, т.е. предполагают наличие априорной информации о типовой структуре обрабатываемого кода [126; 127].

Другой недостаток описанного подхода к чтению штриховых кодов -потеря возможности распознания штрихкода в случае повреждения метаинформации, которая в отличие от полезной информации менее защищена контрольными суммами [119].

В некоторых сценариях применимы методы распознавания, позволяющие обойтись без бинаризации изображения штрихового кода. Рассмотрим, например, «классическую» одномерную символику ИРС-Л [128], в которой кодируемое сообщение может содержать только символы из

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

9 8 7 6 5 4 3 2 1 0

Рисунок 5.3

Кодовые слова символики ИРС-Л («левая» половина, «правая» половина получается инвертированием левой).

При априорном знании о количестве символов в коде (12 цифр в случае UPC-A) и корректном определении его границ на изображении, можно не сегментировать образ кода на отдельные штрихи, а последовательно «пристраивать» наиболее близкое изображение шаблона из К-ирс к сегменту множества пикселей s, взятому из нормализованной строки изображения штрихкода L. Пристроение к изображению шаблона к G K-upc заключается в подсчете суммарных интенсивностей пикселей I™ и из s, соответствующих «светлым» и «темным» пикселям к, с последующей оценкой их разности С (s, к) = ï^ - ï\. Чем больше величина С (s,к), тем больше сегмент похож на шаблон. В случае, когда используется изображение в оттенках серого, оценка отклонения символа штрихкода от монохромного шаблона-идеала С (s, к) оказывается куда более гладкой, чем в случае сравнения двух бинарных строк, и при этом удается избежать вероятной потери части значимой информации. С помощью методов динамического программирования можно решить задачу оптимального пристроения последовательности шаблонов-идеалов и тем самым решить задачу декодирования всего штрихового кода. Для рассматриваемой символики UPC-A подобный подход был опубликован в 2011 году в замечательной работе О. Галло и Р. Мандуки [129].