Автоматизация выявления модификаций в образе договорных документов с помощью модели N-грамм

Каждый современный человек знает о том, что подписывать какой-либо документ нужно не раньше, чем его прочитал. Нарушившие это несложное правило иногда удивляются неожиданным последствиям, которых можно было бы избежать, если до подписания изучить документа, включая то, что написано мелким шрифтом. Уловки в договорах со стороны поставщиков услуг используются как составная часть анекдотов и кинофильмов. Например, в фильме «Ослеплённый желаниями» главный герой расторг весьма невыгодную сделку с дьяволом, несмотря на незнание условий расторжения договора, описанного в статье 147, параграфа 3, 3-ей части договора. Подобная ситуация иногда возможна в реальной жизни с поставщиками услуг. В интернете можно найти описание курьёзных случаев, когда клиент банка изменил условия договора в свою пользу, и это явилось неожиданностью для банка. В сегодняшней статье мы расскажем про крайне полезный для банков и других кредитных организаций алгоритм, позволяющий в автоматическом режиме выявлять внесенные модификации в образах договорных документов. Так что заглядывайте под кат!

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

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

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

Шаблон или форма документа описывается заранее и состоит из статического текста и полей для внесения информации. Рассмотрим два часто встречающихся класса шаблонов: фиксированный шаблон и гибкий шаблон. Фиксированный шаблон не позволяет модифицировать статические тексты, например, при использовании формата PDF. Могут применяться гибкие шаблоны, позволяющие модификацию статических текстов, например, шаблоны в формате Microsoft Office. Соответственно будем различать фиксированные и гибкие документы.

Известны методы автоматизированного сравнения образа (скана или фото) подписанного документа с его прообразом [1]. В них проводится проверка возможных модификаций содержания:

• замена одного или нескольких символов в слове;
• замена одного слова на другое;
• добавление символа, слова или группы слов;
• удаление символа, слова или группы слов.

Также возможны модификации оформление документа:

• изменение стиля слов (размера, шрифтов, типа);
• изменение полей документа слов;
• изменение числа абзацев;
• изменение полей.

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

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

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

Текстовая особая точка аналогична «графической» особой точке изображения, под которой понимается точка, удовлетворяющая нескольким условиям:

• отличающие от точек в своей окрестности окрестность;
• устойчивость к шумам;
• устойчивость к некоторым преобразованиям (например, к аффинным преобразованиям или масштабированию) [2].

Свойствами особых точек являются:

• repeatability – особая точка должна находится в одном и том же месте объекта изображения, несмотря на изменения точки обзора и освещенности;
• distinctiveness/informativeness – окрестности особых точек должны иметь большие отличия друг от друга;
• locality – особая точка и ее окрестность должны занимать небольшую область изображения;
• quantity – число обнаруженных особых точек должно быть достаточно большим для обнаружения объектов;
• accuracy – обнаруженные особые точки должны точно локализовываться, как в исходном изображении, так и взятом в другом масштабе;
• efficiency – время детектирования особых точек на изображении должно быть допустимым для критичных по времени приложений.

Предполагается, что текстовая особая точка отличается от соседних текстовых особых точек в своей окрестности. Если под окрестностью понимать текстовую строку, то большинства слов в деловых документах отличаются от соседей по строке. Несколько одинаковых слов, размещенные в одной строке, не будут текстовыми особыми точками. Однако, если под окрестностью понимать одно или два соседних слова, то два одинаковых слова, размещенные в одной строке и различающиеся соседними словами, будут текстовыми особыми точками. Сопоставление особых точек проводится с помощью меру сходства d, которая должна принимать близкие к нулю значения в случае сравнения двух точек, соответствующих одному место в изображении, и большие значения при сравнении точек из различных мест изображения. Сравнения двух ядер текстовых особых точек в данной работе основано на расстоянии Левенштейна [3] и его модификации. Порог сравнения слова с другими словами вычисляется заранее. Если , то слово и текстовая особая точка являются идентичными, в противном случае – различающимися.

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

Метод извлечения особых точек из изображения называется детектором. Детектором текстовой особой точки является процедура распознавания с помощью некоторого OCR, извлекающего дескрипторы особых точек из образа документа. Перечисленные выше свойства особых точек справедливы для текстовых особых точек в случае умения современных OCR компенсировать разные виды image distortions. Уникальность дескрипторов текстовых особых точек определена структурой документов (однозначное разбиение документа на созвездия – разделы, параграфы и строки) и свойствами естественного языка (редкое совпадение в документах двух соседних слов). Различные отношения между текстовыми особыми точками (отношения выше — ниже, справа – слева или геометрическое расстояние между рамками) позволяет объединять точки в созвездия с помощью алгоритмов кластеризации.

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

Координация фиксированных документов включает в себя:

• поиск соответствия любой точки эталона в точках копии;
• поиск соответствия любой точки копии в точках эталона;
• поиск соответствия любой статической строки эталона в точках копии;
• поиск соответствия любой статической строки копии в точках эталона;
• проверка идентичности образов каждой пары скоординированных образов.

Любое найденное несоответствие является потенциальной модификацией. Разумеется, найденное несоответствие может быть вызвано ошибками детектора (OCR) или дисторсиями образа документа. Постановка задачи состоит в поиске всех модификацией в копии документа.

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

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



При полной координации слов копии и оригинала кроме ложных ошибок распознавания могут найтись и другие незначащие различия. Дело в том, что с точки зрения функционального пользователя программы для сравнения копии и оригинала не все слова имеют одинаковую ценность. Собственно говоря, ценность имеют подмножество слов страницы документа, которое определяет существенные условия договора. Предполагается, что задачей мошенника является внесение таких модификаций, которые в суде или в досудебном процессе могут принести ущерб организации, подписавшей договор с мошенником. Дать формальное определение таких существенных слов вряд ли возможно, их определяют специалисты. Более того некоторые слова становятся существенными в сочетании с соседними словами. Например, частица «не» в сочетании с соседним словом «гарантирует» являются существенной. Модификация слова «договору» в слово «недоговору» – несущественна, поскольку в судебном разбирательстве не может принести выгоды мошеннику.

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

Оказалось эффективным использование простой модели N-грамм слов. Модель N-грамм применяется в различных задачах, таких как сжатие или кодирование текстов. В обработке текстов, написанных на естественном языке, N-граммы оказываются полезными для поиска и исправления ошибок (мы уже писали про это раньше).

Для поиска ключевых слов используются N-граммы слов в следующих формах:










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

Модель параграфа состоит из упорядоченной последовательности N-грамм
с заранее определенными кортежами слов , с известными заранее расстояниями между парами . Отметим, что некоторые N-граммы являются уникальными для параграфа, а некоторые могут повторяться. Для обеспечения уникальности могут применяться N-граммы различной длины: биграммы, триграммы, тетраграммы и пентаграммы.

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

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

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

• обработка полутонового изображения (библиотека MinImage);
• нормализация изображения по углу с помощью методов, основанных на быстром преобразовании Хафа [4] (API Smart IDReader);
• выделение границ слов с помощью операций «эрозии» и «дилатации»(библиотека MinImage);
• распознавание символов в границах найденных слов (API Smart IDReader).

Параграф представлялся в виде одной длинной строки.

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

Использовалось модифицированное расстояние Левенштейна. Во-первых, для сравнения конкретного слова с другими словами выбирался уникальный порог. Для отказа от отождествления пар слов типа «МОРЕ»=«ГОРА» или для идентификаторов типа «ИДЕНТИФИКАТОР196»,«ИДЕНТИФИКАТОР296»,«ИДЕНТИФИКАТОР199» применялось другое правило. Для таких слов указывались сегменты, которые должны были остаться неизменными. То есть в начале слов «ИДЕНТИФИКАТОРddd» разрешалось большое число ошибок, но отождествление запрещалось при найденных редакционных предписаниях в 3-х последних символах слова.

Другая модификация состояла в компенсации случаев замены OCR некоторых символов на сходные по начертанию. Формально замены символов для латинского алфавита , , являются ошибками, однако уменьшение цены таких замен позволяет повысить точность отождествления слов. Цена замены буквы для сходных по начертанию символов выбиралась при обучении.
На основе нескольких расстояний центра и соседей N-граммы до выбранных аналогов формируется эвристическая оценка привязки N-граммы в целом.
Параметры модели (пороги, длины N-грамм) выбирались при обучении так, чтобы минимизировать число ошибок привязки N-грамм и максимизировать число правильно привязанных N-грамм.

После привязки N-грамм к словам параграфа можно провести следующие проверки:

• наличие всех ожидаемых N-грамм;
• наличие всех уникальных N-грамм в одном экземпляре;
• порядок следования N-грамм;
• расстояния между соседними N-граммами.

Невыполнение любой из проверок означает нахождение модификации важного ключевого слова.

Описанный метод был протестирован на датасете, состоящем из 161 образов документа типа «Соглашение», отсканированных с разрешающей способностью от 100 до 300 dpi. Исследовалось модель из 33 ключевых слов. Часть ключевых слов в образах датасета была сознательно удалена или модифицирована. Было сделано 740 удалений и 140 модификаций слов. Для распознавания использовался OCR Smart IDReader [5].

Качество алгоритма оценивалось критериями точности (Precision) и полноты (Recall), при определении которых использовались числа:

• найденных модифицированных слов ;
• корректных слов, классифицированных как модификации ;
• ненайденных модифицированных слов ;
• корректных слов, классифицированных как корректные .

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


Отметим, что при распознавании OCR Smart IDReader были найдены все модифицированные слова. Ошибки метола связаны с ошибками распознавания, прежде всего из-за дефектов сканирования (наличие переосветленных областей).

Нетрудно догадаться, что описанный метод имеет ограничение, связанное с точностью выделения границ слов. Указанные дефекты сканирования проводили к небольшому числу ошибок поиска границ слов (около 1-1,5% для некоторых ключевых слов). Для устранения этого ограничения мы предлагаем дополнительный способ поиска слов. Для некоторой ненайденной N-граммы выбирался подмножество слов распознанного параграфа, в котором ожидалось наличие этой N-граммы. Из выбранного подмножества слов удалялись пробелы и формировалась строка символов. Слова N-граммы конкатенировались, образуя подстрока для поиска. Далее проводился поиск подстрок, например, с помощью модифицированного алгоритма bitup, использующего модифицированное расстояние Левенштейна. Это позволяет уменьшить в 2-3 раза количество ошибок проверок N-граммы, связанных с ошибками поиска границ слов.

Краткое заключение

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