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

1. Постановка задачи

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

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

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

Для анализа информации, содержащейся в образе документа (в частности, классификации) можно использовать программы распознавания произвольного текста (OCR). В настоящее время одним из самых популярных решений является OCR Tesseract, например, в диссертации [2] эта OCR была выбрана для распознавания корпуса архивных документов по следующим причинам: возможность свободного распространения, а также представление результатов распознавания в формате HOCR (HTML OCR) с сохранением информации о координатах распознанных слов.

OCR Tesseract в зависимости от степени зашумления текста и собственных способностей может распознавать образы страниц успешно или неуспешно. Систематический неуспех может быть связан с объективными сложностями распознавания определенных классов документов, например, паспортов гражданина РФ, программа распознавания которой была нами описана в другой статье [3]. Характерные ошибки OCR Tesseract можно разделить на несколько видов:

• Е₁: полный отказ от распознавания страницы, вплоть до того, что не распознано ни одного слова;
• Е₂: число ошибок столь велико, что человек не может понять документ по его текстовому представлению в формате HOCR (например, см. на иллюстрации выше – на ней приведен реальный пример неудачного распознавания документа "Свидетельство о постановке на учет в ИМНС" с помощью OCR Tesseract версии 3.04.00);
• Е₃: неверно распознана структура страницы, например, когда расположенные рядом фрагменты текста в результате оказались разнесенными на значительное расстояние;
• Е₄: наличие небольшого числа ошибок, когда в большинстве неверно распознанных слов присутствует 1-2 ошибки.

В этой статье мы будем рассматривать классификацию страниц только таких документов, которые массово распознаются OCR Tesseract, в предположении о вероятном возникновении ошибок типа Е₃ и Е₄.

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

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

2. Описание шаблонов и сопоставления с шаблонами

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

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

• векторной модели или "мешка слов", т.е. мультимножества входящих в документ слов [4],
• языковой модели, учитывающей порядок слов (учитывающей вероятность появления последовательности слов) [5],
• тематической модели, использующей темы, состоящие из наборов слов [6, 7].

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

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

W = (T(W), m₁(W), m₂(W), m₃(W), m₄(W), m₅(W), m₆(W)),

где T(W) – ядро слова, то есть последовательность символов и знаков "?" и "?", последние используются для задания множества слов, например, "?ab?c" задает множество слов с произвольным числом символов, с последними символами ab?c, на месте "?" может присутствовать произвольный символ.

m₁(W) – порог расстояния при сравнении двух слов T(W) и W_r. Для сравнения двух слов необходимо выбрать метрику (функцию расстояния), мы использовали расстояние Левенштейна [8] или упрощенную функцию, учитывающую только количество операций замены одного символа на другой. В последнем случае расстояние d(T(W), W_r) подсчитывается только для слов одинаковой длины, для слов с знаками "?" соответствующие символы в сравнении не участвуют, а для слов с знаками "?" сравниваются нужные подстроки. Если d(T(W), W_r)<m₂(W), то слова являются идентичными, в противном случае – различными. В простейшем случае m₂(W) – это максимальное числа операций замены при трансформации T(W) в W_r.

m₂(W) – ограничение на длину слова W_r при сравнении T(W) и W_r, имеет смысл для слов, содержащих "?".

m₃(W) – признак зависимости от регистра (case sensitive/insensitive) при сравнении символов.

m₄(W) – прямоугольник слова, состоящая из координат в диапазон [0,1], используемых для проверки попадания слова в указанный прямоугольник.

m₅(W) – признак отрицания слова, указывающий, что данного слова не должно быть в тексте. С помощью m₅(W) можно организовать проверку как наличия, так и отсутствия слова W в тексте.

m₆(W) – будет описан ниже.

При поиске слова T(W) в тексте распознанного документа T мы проверяем истинность условия

? W_r ? T: d(T(W), W_r) < m₂(W) ? (F(W_r) ? m₄(W) = F(W_r))

где F(W_r) – прямоугольник слова W_r, то есть координаты слова, извлеченные из результатов распознавания в формате HOCR, абсциссы и ординаты нормируются на ширину и высоту исходного изображения. При сравнении используется параметр m₃(W). Вообще говоря, может быть найдено несколько слов {W_r}, идентичных ключевому слову T(W).

Определим для случая m₅(W)=0 предикат P(W, T)=1, если в тексте распознанного документа T найдено хотя бы одно слово, идентичное слову W, и P(W, T)=0, если в тексте не найдено ни одного слова, идентичного слову W. Если слово обладало признаком m₅(W)=1, то P(W, T)=0, если в тексте распознанного документа T найдено хотя бы одно слово, идентичное слову W, и P(W, T)=1, если в тексте не найдено ни одного слова, идентичного слову W.

Также нам потребуется оценки d(T(W), W_r) слов, идентичных слову T(W).

Далее определим размещение слов как упорядоченное множество слов R = W₁,W₂,…, для которого проверятся наличие каждого из слов в распознанном документе T:

P(W₁, T) ? P(W_r, T) ? … (1)

и дополнительно для каждой пары слов W_i и W_i+1 проверяется условие

r(W_i+1) – r(W_i) < m₅(W), (2)

где функция r(W) дает номер слова W в тексте T, упорядоченном механизмами OCR. То есть параметр m_r6(W) определяет расстояние между соседними словами в размещении, при m_r(W_i+1) = ? условие (2) не проверяется, а проверяется только порядок следования слов.

Для размещения R может быть задан m₇(R) – прямоугольник размещения, смысл которого аналогичен прямоугольнику слова, проверяется, содержатся ли полностью найденные в тексте T слова, идентичные словам W₁,W₂…, в прямоугольнике m₆(R).

Выполнение условий (1), (2) и условия проверки соответствия рамке m₇(R) прямоугольника определяет предикат принадлежности размещения R тексту T: P(R, T)=1. В простейшем случае размещение может состоять из одного единственно слова, в общем случае для вычисления P(R, T) требуется перебор множеств, идентичных словам W₁,W₂… .

Определим оценку d(R, T) размещения как минимальную из оценок слов: min(d(W₁, T), d(W₂, T), …).

Теперь определим сочетание как множество размещений S = R₁,R₂,…, для которого проверятся наличие каждого из размещений в распознанном документе T:

P(R₁, T) ? P(R₂, T) ? … (3)

Порядок размещений неважен. В дополнение к условию (3) может быть добавлено сравнение прямоугольников всех слов из сочетания с прямоугольником сочетания m₈(S). Указанные условия определяют предикат принадлежности сочетания S тексту T: P(S, T)=1.

Оценку d(S, T) сочетания определим как минимальную из оценок размещений, входящих в сочетание: min(d(R₁, T), d(R₂, T), …).

И, наконец, определим шаблон M как множество сочетаний S₁,S₂,…, для которого принадлежность шаблона распознанному тексту T устанавливается проверкой выражения

P(M, T) = P(S₁, T) ? P(S₂, T) ? … (4)

В дополнение к условию (4) может быть добавлено сравнение прямоугольников всех слов шаблона с прямоугольником сочетания m₈(M).

Оценку d(M, T) шаблона определим как максимальную из оценок сочетаний, входящих в шаблон: max(d(S₁, T), d(S₂, T), …).

К имеющимся сравнениям шаблона с распознанным текстом добавим проверки соответствия некоторых свойств текста (количество символов на странице m₉(T), количество колонок текста m₁₀(T)) с аналогичными свойствами шаблона m₉(M), m₁₀(M).

Если для n классов готов набор шаблонов M₁, …, M_n, то задача проверки соответствия классу M_i распознанной страницы документа T сводится к вычислению расстояния d(M_i, T) по изложенной схеме и сравнению этого расстояния с заранее известным порогом d₁. Если справедливо max(M_i) < d₁, то документ T соответствует классу i.

Поясним необходимость использования элементов предложенных шаблонов.

Простые единичные ошибки вида Е₄, часто появляющееся в некотором слове, могут быть проигнорированы с помощью знаков "?" и "?" в маске слова. Для контроля длины слова, включающего знак "?", может быть использован параметр m₂, например, ключевые слова "ДОГОВОР", "Договора" могут быть описаны ядром "ДОГОВОР?" с ограничение m₂=8, что исключает из рассмотрения слова типа "договороспособность". Ядро "? ОГОВОР" позволяет не различать слова "ДОГОВОР" и "АОГОВОР".

Порог m₁ может быть использован для требования полного совпадения ключевого слова и слова из текста, например, при m₁=0 ядро "ДОГОВОР" при поиске в тексте не допускает выбора слов "АОГОВОР" или "ДОГО8ОР", отличающиеся одной операций замены символа.

Параметр m₃ также позволяет игнорировать ошибки распознавания регистра символа.

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

Ошибки вида Е₃, то есть неверно распознанная структура страницы, могут быть иногда проигнорированы настройкой размещений. Размещение естественным образом описывает словосочетание или несколько расположенных рядом слов. В случае разбиения колонки текста на два столбца из-за ошибок распознавания описанное размещение будет найдено, если не указывать расстояния между словами m₆.

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

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

• ключевые слова:

• размещения: R₁=W₁, R₂=W₂&W₃&W₄, R₃=W₂&W₅&W₆, R₄=W₇&W₈&W₉&W₁₀, рамки у всех размещений отсутствуют,
• сочетания: S₁ =R₁?R₂, S₂ =R₁&R₃, S₃ = R₃, рамки у всех сочетаний отсутствуют,
• шаблон: M = S₁&S₂&S₃, у шаблона есть рамка m₈(M) = {(0.0,0.0), (0.3,0.9)}.

Задача выбора наилучшего класса решается вычислением расстояний d(M₁, T), …, d(M_n, T), отбрасыванию таких классов M_j, что справедливо d(M_j, T) > d₁, упорядочиванием получившегося набора по возрастанию (по сути, мы хотим выбрать один или несколько классов с минимальным штрафом за не соответствие шаблона тексту) и сохранением одной или нескольких альтернатив d(M_i1, T), d(M_i2, T),…. То есть наилучшим образом тексту T соответствует класс i1, а другие классы i2,… упорядочены по расстоянию. Разрешение конфликтов d(M_i1, T) = d(M_i2, T) в простейшем случае провести, отказавшись от классификации, в некоторых случаях конфликт устраняется использованием дополнительных признаков m₉, m₁₀.

3. Формирование шаблонов (обучение)

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

Рассмотрим процесс формирования шаблонов на реальном примере для потока документов 45 классов. Мы готовили шаблоны в несколько этапов, ориентируясь на ключевые слова на первой странице многостраничных документов.

Этап 1. Вначале мы рассматривали множество эталонных документов. Для каждого класса были подготовлены несколько образцов идеальных документов, в результатах распознавания которых ошибки отсутствовали. Текстовые представления этих документов были преобразованы в мешки слов, т.е. в мультимножества слов, из числа которых были удалены стоп-слова (короткие слова, ФИО, числовые данные, даты и т.п.). Далее простыми переборными алгоритмами из этих мультимножеств были выбраны одиночные слова и словосочетания из нескольких слов, присущие одному из классов. Основное внимание обращалось на характерные слова из заголовков и названий разделов документа. Таким образом было составлено по нескольку размещений, хорошо отделяющими одни классы от других. Таким образом мы искали ядра ключевых слов, а остальные параметры устанавливали по умолчанию. Сразу же было выявлено несколько проблемных классов, например, первая страница документов класса "Устав" могла быть представлена одним единственным ключевым словом "Устав", которое часто встречается в других документах, например, в документах класса "Договор". Для устранения этой проблемы мы использовали два приема:

• использование слов, которые не должны встречаться на первой странице документов класса "Устав",
• использование признака m₉(T) – количество символов на странице – который хорошо выделял страницы документов класса "Устав".

Этап 2. Далее, несмотря на некоторые несовершенства классификации с получившимися шаблонами, мы перешли к выборке документов, состоящей из 50-100 образцов реальных документов (одностраничных и многостраничных), распознавание которых давало широкий спектр ошибок всех видов Е₁ – Е₄. Анализ ошибок позволил выявить некоторое количество страниц, которые требовали модификации шаблонов, и страницы, которые не могли быть классифицированы нашей технологией (прежде всего, из-за большого количества ошибок распознавания). Модификация шаблонов сводилась к поиску новых размещений и сочетаний, поиску слов, которые не должны встречаться в документе, а также к выбору параметров ключевых слов, прежде всего, прямоугольников m₄ и расстояний между словами m₆. Анализ результатов классификации проводился по следующим критериям:

Правильно классифицированные страницы оцениваются точностью (n₁+m₂)/(n₁+ n₂+ n₃+m₁+m₂), ошибок ложной классификации – как (n₂+m₂)/(n₁+n₂+n₃+m₁+m₂), а отказы от классификации – как (n₃)/(n₁+ n₂+ n₃+m₁+m₂).

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

Этап 3. Первые два этапа основаны на использовании правил (собственно шаблонов) для отнести к тому или иному классу. Для выборок большого объема (3000 – 30000 образцов каждого класса) возможно проведение машинного обучения, например, известным методом построения бинарного дерева решений CART (Classification and Regression Trees [9]). Исходными данными для обучения являются описания известных по предыдущим этапам ключевых слов в виде ядра и признаков. На этих признаках строилось несколько деревьев, для каждого класса, по стратегии один против всех. Если некоторый документ в процессе классификации не был распознан не одним из деревьев, формируется отказ классификации. Из известных особенностей метода CART, отметим необходимость достаточно большого объема обучающей выборки для стабильного обучения. Из-за этого мы не будем приводить результаты классификации, полученные с помощью метода CART, хотя в целом они превосходят результаты классификации, полученные с помощью обучения на этапах 1 и 2.

4. Эксперименты

Для экспериментов было использованы два тестовых множества:

• содержащего образы документов среднего и плохого качества оцифровки, подобранные для этапа обучения (884 страницы),
• содержащего образы документов среднего качества оцифровки, полученные независимо от этапа обучения (3014 страниц).

Результаты классификации приведены ниже в двух таблицах:

Из приведенных таблиц ясно, что описанная нами технология классификации дает точность 0.86 – 0.95, при этом ложная классификация не превышает 0.01, остальные ошибки относятся к отказам от классификации. То есть предложенный метод не всегда срабатывает, но редко предлагает неверный класс.

Быстродействие реализованной классификации (сборка Release с помощью Microsoft Visual Studio 2013) достаточно велико: 3000 распознанных страниц обрабатываются примерно за 1 минуту на компьютере Intel® Core(TM) i7-4790 CPU 3.60 GHz, 16,0 GB, Windows 7 prof 64-bit. Однако собственно распознавание OCR Tesseract, необходимое для исходного файла HOCR, занимает несколько секунд.

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

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

Заключение

Описанная технология классификации была использована в реализованных Smart Engines проектах ввода и анализа потока отсканированных документов.

Описанная технология является простой для понимания и самостоятельной реализации для решения аналогичных задач.

Список полезных источников

1. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М: Техносфера, 2005. 1070 с.
2. Смирнов С. В. ТЕХНОЛОГИЯ И СИСТЕМА АВТОМАТИЧЕСКОЙ КОРРЕКТИРОВКИ РЕЗУЛЬТАТОВ ПРИ РАСПОЗНАВАНИИ АРХИВНЫХ ДОКУМЕНТОВ. Диссертация на соискание ученой степени кандидата технических наук, СПт:, 2015. – 130 с.
3. "Распознавание Паспорта РФ на мобильном телефоне" (https://habrahabr.ru/company/smartengines/blog/252703/)
4. Martin D., Jurafsky D. Speech and Language Processing. An introduction to natural language processing, computational linguistics, and speech recognition. Pearson Prentice Hall, 2009. – 988 p.
5. Ponte J. M., Croft W. B. A Language modeling Approach to Information Retrieval // Proc. Conference on Research and Development in Information Retrieval. ACM. 1998. – С. 275–281.
6. Indexing by Latent Semantic Analysis / S. Deerwester [и др.] // Journal of the American Society for Information Science. 1990. – Т. 41, № 6. – С. 391.
7. Черняк Е. Л. РАЗРАБОТКА ВЫЧИСЛИТЕЛЬНЫХ МЕТОДОВ АНАЛИЗА ТЕКСТОВ С ИСПОЛЬЗОВАНИЕМ АННОТИРОВАННЫХ СУФФИКСНЫХ ДЕРЕВЬЕВ. Диссертация на соискание ученой степени кандидата технических наук, М:, 2016. – 124 с
8. Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов, – М.: Доклады АН СССР, т.163.4, 1965. — 845-848 с.
9. Breiman L., Friedman J. H., Olshen R. A., & Stone C. J. Classification and regression trees. Monterey // CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984. – 368 p.