🎥 🖨️ 👦🏿 使用N-gram模型自动识别合同文件图像中的修改 👇🏻 👃🏿 🗯️

每个现代人都知道您需要在阅读文件之前签署文件。违反此简单规则的人有时会对意外的后果感到惊讶，如果您在签名前检查了文件（包括小写内容），这些后果是可以避免的。服务提供商的合同技巧被用作笑话和电影的一部分。例如，电影《欲望蒙蔽》尽管对合同第147条第3款第3项中所述的合同终止条款无知，但主角还是终止了与恶魔的非常不利的交易。服务提供商在现实生活中有时可能会出现类似情况。在Internet上，您可以找到有关银行客户以其有利的方式更改协议条款的奇怪案例的描述，这对银行来说是一个惊喜。在今天的文章中，我们将讨论一种对银行和其他信贷组织非常有用的算法，该算法可以自动检测对合同单据图像所做的修改。因此，在猫下看！

当前，许多吸引大量新客户的组织都提供从其网站下载合同模板以进行自我准备。已打印，已完成并已签署的合同将转移给第二方进行签署。当然，第二方检查潜在客户准备的合同，例如，手动检查提交的文档。此类文档的数量可能很大，因此需要几个专心的员工来检查它们。但是，每天检查数十个相同（含义）的文档时，即使是整洁的员工也可以跳过错误。这解释了在手动验证过程中未发现的欺诈案件。

我们将讨论使用光学识别技术对上述大量合同文件进行例行验证的自动化，这种技术已经多次（例如一次和两次）成为Habr上Smart Engines文章的主题。

合同文件属于为在某些办公室管理和文件管理系统中分发而创建的业务文件类别。商业文档的一个显着特征是所用词汇及其设计方式的局限性。这是由于希望统一文档的形式以简化人首先对业务文档的理解。

文档的模板或形式已预先说明，由静态文本和用于输入信息的字段组成。考虑两种常见的模板类别：固定模板和灵活模板。固定模板不允许修改静态文本，例如，在使用PDF格式时。灵活的模板可用于允许修改静态文本，例如Microsoft Office格式的模板。因此，我们将区分固定文件和灵活文件。

自动比较签名文档的图像（扫描或照片）及其原型的方法[1]。他们检查内容的可能修改：

替换一个单词中的一个或多个字符；
用另一个替换一个词；
添加字符，单词或单词组
删除字符，单词或单词组。

也可以对文档的设计进行修改：

更改文字样式（大小，字体，类型）；
更改word文档的字段；
更改段落数；
更改字段。

固定模板的修改是故意的伪造，因为没有其他方法可以解释更改受保护文本的愿望。修改灵活模板可以是伪造，偶然的错字或格式改进的结果。

接下来，我们描述使用固定和灵活模板在打印的商业文档副本中搜索欺诈的模型和方法。

比较测试图像（副本）和参考图像（原始图像）的基础是通过任何方法找到的单词图像。单词的图像由某种描述（描述符）表示，最明显的描述符是单词的可识别字符。字

W

$W$ 定义为文本特征点

，其中-

W = (T (W), B (W))

$W=(T(W),B(W))$

是文本特征点的核心，也就是说，一个单词的字符序列由特定字母的字符组成，或者具有对字母字符的熟悉程度的符合度等级，

T (W)

$T(W)$

-由边界坐标组成的文本特征点框架

B (W)

$B(W)$

，

B_{x 1} (W)

$B_{x1}(W)$

，

B_{y 1} (W)

$B_{y1}(W)$

，

B_{x 2} (W)

$B_{x2}(W)$

B_{y 2} (W)

$B_{y2}(W)$ ，可以在一定范围内进行归一化

F (W)

$F(W)$ -文本特征点的属性（例如，耳机和字体修改）。

文本特征点类似于图像中的“图形”特征点，这意味着可以满足以下条件：

与周围的点不同的邻里；
抗噪声能力
抵抗某些变换（例如仿射变换或缩放）[2]。

奇异点的属性是：

重复性-尽管视点和照明发生了变化，特定点仍应位于图像对象的同一位置；
distinctiveness/informativeness – ;
locality – ;
quantity – ;
accuracy – , , ;
efficiency – .

假定文本特征点与其附近的相邻文本特征点不同。如果说邻居是指文本行，那么业务文档中的大多数单词都与该行中的邻居不同。放在同一行上的多个相同单词将不是文本单数点。但是，如果用邻域表示一个或两个相邻的单词，那么放在同一行上并由相邻单词区分的两个相同的单词将是文本奇异点。奇异点的比较是使用相似性度量d进行的，在比较与图像中一个位置相对应的两个点时，其取值应接近零，而在比较来自图像中不同位置的点时，则取较大的值。本文基于Levenshtein距离对文本奇异点的两个核心进行比较

ρ_{L e v}

$\rho_{Lev}$ [3]和它的修改。阈

d (W)

$d(W)$ 词比较

T (W)

$T(W)$ 换句话说，

是预先计算的。如果

ρ_{L e v} (W, W_{r}) < d (W)

$\rho_{Lev}(W, W_r)\lt d(W)$ 然后这个词

W_{r}

$W_r$ 和文字特征点

W

$W$ 是相同的，否则不同。

特征点描述符是匹配特征点时使用的标识符。当针对图像变换匹配奇异点时，预期描述符是不变的。

从图像中提取奇异点的方法称为检测器。探测器文本特征点是使用某些OCR的识别过程，该过程从文档图像中提取特征点描述符。在现代OCR能够补偿不同类型的图像失真的情况下，上面列出的特征点的属性对文本特征点有效。文本奇异性描述符的唯一性取决于文档的结构（文档清楚地分为星座-部分，段落和行）和自然语言属性（两个相邻单词的文档中很少见的巧合）。文本奇异点之间的各种关系（上-下，右-左的关系或帧之间的几何距离）使您可以使用聚类算法将这些点组合为星座。

理想情况下，OCR将从复印图像和文档模板中提取所有特定于文本的点，而不会出错。这使您可以形成星座，尤其是直线。副本和参考的比较在于在参考的全部或部分文本奇异点与副本的一组文本特定点之间建立明确的对应关系。在点或点星座之间建立对应关系的过程称为协调。

固定文件的协调包括：

搜索副本中参考点中任何点的对应关系；
在标准中的点上搜索副本中任何点的对应关系；
在复制点搜索标准的任何静态线的对应关系
在标准点搜索任何静态复制行的对应关系；
验证每对协同图像的图像身份。

发现的任何不一致都是潜在的修改。当然，发现的不一致可能是由于检测器错误（OCR）或文档图像失真引起的。问题的陈述是在文档副本中搜索所有修改。

灵活文档的协调涉及在静态文本的所有单词之间建立对应关系。但是，与固定文档不同的是，不假设柔性文档的静态文本行之间存在对应关系。在灵活的文档中，可能会进行不改变文本含义的合法更改，例如更改字体，更改行边界，换行符。此类修改可能导致另一页上出现换行符，因此应针对整个页面序列对多页柔性文档进行比较。

通常，在不了解文档结构的情况下，必须对测试文档和参考文档的所有单词进行协调。单词完全协调的一个明显缺点是不可避免的识别错误，尤其是照片（请参见下图中带有失真的文本图像片段的示例），它被解释为修改。负责验证的人员将被迫花费额外的时间检查错误的修改。

在副本和原始文字完全协调的基础上，除了错误的识别错误之外，还可能存在其他无关紧要的差异。事实是，从用于比较副本和原始内容的程序功能用户的角度来看，并非所有单词都具有相同的值。实际上，确定合同基本条款的文档页面中某些单词的子集很有价值。假定欺诈者的任务是进行修改，以便在法庭上或在预审程序中可能对与欺诈者签订合同的组织造成损害。给出如此重要的正式定义单词是不可能的，它们是由专家确定的。此外，一些单词与相邻单词结合起来变得有意义。例如，粒子“ not”与相邻单词“ guarantees”的组合很重要。将“合同”一词修改为“非合同”一词是微不足道的，因为在法院诉讼中，它不能给欺诈者带来好处。

因此，利用文件的结构和验证所必需的词的位置的知识，可以对问题进行另一种表述。在此语句中，文档模型由段落和文本字符串组成。每个文本行和每个段落都由一组文本奇异点表示，其顺序对于给定的段落或行是唯一的。行和段落也可能包含不唯一的单词，即重复甚至位于附近。在特殊情况下，有可能知道唯一单词之间的距离，该距离取决于中间字符的数量或单词图像之间的几何距离。

已证明使用简单的N元语法词模型是有效的。N-gram模型用于各种任务，例如文本的压缩或编码。在处理以自然语言编写的文本时，N元语法对于发现和纠正错误很有用（我们之前已经写过有关此的内容）。

为了搜索关键字，N-gram单词以以下形式使用：

n_{2} (w_{i}) = 〈 w_{i}, r_{1} (w_{i}) 〉

$n_2 (w_i )=〈w_i,r_1 (w_i ) 〉$

n_{3} (w_{i}) = 〈 w_{i}, r_{1} (w_{i}), r_{2} (w_{i}) 〉

$n_3 (w_i )=〈w_i,r_1 (w_i ),r_2 (w_i ) 〉$

n_{2} (w_{i}) = 〈 l_{1} (w_{i}), w_{i} 〉

$n_2 (w_i )=〈l_1 (w_i ),w_i 〉$

n_{3} (w_{i}) = 〈 l_{1} (w_{i}), w_{i}, r_{1} (w_{i}) 〉

$n_3 (w_i )=〈l_1 (w_i ),w_i,r_1 (w_i ) 〉$

n_{4} (w_{i}) = 〈 l_{1} (w_{i}), w_{i}, r_{1} (w_{i}), r_{2} (w_{i}) 〉

$n_4 (w_i )=〈l_1 (w_i ),w_i,r_1 (w_i ),r_2 (w_i ) 〉$

n_{3} (w_{i}) = 〈 l_{2} (w_{i}), l_{1} (w_{i}), w_{i} 〉

$n_3 (w_i )=〈l_2 (w_i ),l_1 (w_i ),w_i 〉$

n_{4} (w_{i}) = 〈 l_{2} (w_{i}), l_{1} (w_{i}), w_{i}, r_{1} (w_{i}) 〉

$n_4 (w_i )=〈l_2 (w_i ),l_1 (w_i ),w_i,r_1 (w_i ) 〉$

n_{5} (w_{i}) = 〈 l_{2} (w_{i}), l_{1} (w_{i}), w_{i}, r_{1} (w_{i}), r_{2} (w_{i}) 〉,

$n_5 (w_i )=〈l_2 (w_i ),l_1 (w_i ),w_i,r_1 (w_i ),r_2 (w_i ) 〉 ,$

哪里

r_{k} (w_{i})

$r_k (w_i)$ ，

l_{q} (w_{i})

$l_q (w_i)$ 中心词右边或左边的词

w_{i}

$w_i$ 允许距离也是已知的

ρ_{B T} (w_{i}, r_{1} (w_{i}))

$\rho_{BT}(w_i, r_1 (w_i))$ ，

ρ_{B T} (r_{1} (w_{i}), r_{2} (w_{i}))

$\rho_{BT}(r_1 (w_i), r_2 (w_i))$ ，

ρ_{B T} (l_{1} (w_{i}), w_{i})

$\rho_{BT}(l_1 (w_i), w_i)$ ，

ρ_{B T} (l_{2} (w_{i}), l_{1} (w_{i}))

$\rho_{BT}(l_2 (w_i), l_1 (w_i))$ 相邻单词之间。指数

k

$k$ 在指定N-gram

n_{k} (w_{i})

$n_k (w_i)$ 称N-gram的长度。

段落模型由N-gram的有序序列组成

n^{1} (w_{1}), n^{2} (w_{2}), \dots, n^{m} (w_{m})

$n^1 (w_1), n^2 (w_2), …, n^m (w_m)$ 带有预定义的单词元组

n^{i} (w_{i})

$n^i (w_i)$ ，对之间的距离已知

{n^{j - 1} (w_{j - 1}), n^{j} (w_{j})}

$\{n^{j-1}(w_{j-1}), n^j(w_j)\}$ 。请注意，有些N-gram对一个段落是唯一的，有些可以重复。为了确保唯一性，可以使用各种长度的N-gram：双字母组，三字母组，四字母组和五字母组。

在构建段落模型时，会形成N-gram，以使唯一N-gram的数量最大化。与单个关键字相比，使用N-gram可以确保合同文档大多数段落的唯一性，这主要是因为上述静态文本中单词集的上述重大限制。

在实际数据集上进行参数的训练和优化是有意义的。请注意，即使在真实数据集上，由于数据集拥有者分泌的此类数据，我们首先也不会看到可能的修改。我必须用自己的双手进行修改。

Trigram搜索算法归结为选择几个连续的单词。当然，首先您需要形成一组文本奇点。为此，我们采取了以下步骤：

半色调处理（MinImage库）；
使用基于快速霍夫变换[4]（Smart IDReader API）的方法按角度对图像进行归一化；
使用“侵蚀”和“膨胀”操作突出显示单词边界（MinImage库）；
识别找到的单词范围内的字符（Smart IDReader API）。

该段以长行显示。

使用修改后的Levenshtein距离对段落的理想单词和公认单词进行了比较。 Levenshtein距离计算算法是众所周知的，它们使您不仅可以找到编辑处方的数量，还可以查找处方本身。

使用修正的Levenshtein距离。首先，选择一个唯一的阈值以将特定单词与其他单词进行比较。为了拒绝识别类型为“ SEA” =“山”的单词对或类型为“ IDENTIFIER196”，“ IDENTIFIER296”，“ IDENTIFIER199”的标识符，应用了另一条规则。对于这样的单词，指出将保持不变的片段。也就是说，在“ IDENTIFIERddd”一词的开头允许有很多错误，但是禁止使用该词的后3个字符中发现的编辑说明进行识别。

另一个修改是补偿用相似字符替换某些字符的OCR。正式替换拉丁字母的字符

B 8

$B8$ ，

D O

$DO$ ，

1 I

$1I$ 是错误的，但是，降低此类替换的价格可以提高单词识别的准确性。在培训期间，选择了替换字母以替换具有相似样式的价格。
基于N-gram的中心和邻居到选定类似物的若干距离，形成了对N-gram整体绑定的启发式估计。
在训练过程中选择模型参数（阈值，N-gram长度），以最小化N-gram绑定错误的数量并最大化正确绑定的N-gram的数量。

将N-gram绑定到该段落的单词后，可以进行以下检查：

所有预期的N-gram的存在；
一份副本中存在所有唯一的N-gram；
N-gram的序列；
相邻N克之间的距离。

不执行任何检查都意味着找到对重要关键字的修改。

对描述的方法进行了测试，该数据集包含161张“协议”类型文档的图像，并以100至300 dpi的分辨率扫描。我们调查了33个关键字的模型。故意删除或修改了数据集中图像中的某些关键字。进行了740次删除和140个单词的修改。OCR Smart IDReader [5]用于识别。

算法的质量通过准确性（Precision）和完整性（Recall）的标准进行评估，确定使用哪些数字：

找到修饰词 $tp$ ;
分类为修饰词的正确单词 $fp$ ;
找不到修饰词 $fn$ ;
分类为正确的正确单词 $tn$ 。

结果列于表中。该表显示了针对多个阈值计算的特性。

d (w_{i})

$d(w_i)$ 评估与参考单词相比单词的正确性。

d（_wi）	p	fp	n	n	精确	召回
1个	216	414	738	0	0.34	1.00
2	216	90	1062	0	0.70	1.00
3以上	216	54	1098	0	0.80	1.00

请注意，当识别出OCR Smart IDReader时，将找到所有修改的单词。Metol错误与识别错误相关，主要是由于扫描缺陷（存在曝光过度的区域）引起的。

容易猜测，所描述的方法具有与区分单词边界的准确性有关的限制。所指示的扫描缺陷导致少数单词边界搜索错误（某些关键字大约为1-1.5％）。为了消除此限制，我们提供了一种其他搜索词的方法。对于某些未检测到的N-gram，选择了已识别段落的单词的子集，预计该N-gram的存在。从选定的单词子集中删除空白，并形成一个字符串。 N-gram的单词串联在一起，形成用于搜索的子字符串。接下来，我们搜索子字符串，例如，使用经过修改的Levenshtein距离的经过修改的bitup算法。这允许将与搜索词边界中的错误相关联的N元语法检查的错误数量减少2-3倍。

简要结论

我们讨论了一种用于搜索合同文件伪造品的工具。当然，该工具不能完全解决问题，需要对发现的所谓修饰词进行人工检查。该方法使您能够可靠地自动进行修改搜索，并显着减少例行手动检查的次数。开发描述的方法的复杂性是难以获得带有伪造品的真实数据集。

参考书目

Sidere N. et al. A dataset for forgery detection and spotting in document images // 2017 Seventh International Conference on Emerging Security Technologies (EST). – IEEE, 2017. – P. 26-31.
Bertrand R. et al. A conditional random field model for font forgery detection // 2015 13th International Conference on Document Analysis and Recognition (ICDAR). – IEEE, 2015. – P. 576-580.
. . , // . – , 1965. – . 163. – №. 4. – . 845-848.
Bezmaternykh P. V., Nikolaev D. P. A document skew detection method using fast Hough transform // Twelfth International Conference on Machine Vision (ICMV 2019). – International Society for Optics and Photonics, 2020. – Vol. 11433. – P. 114330J.
Bulatov K. et al. Smart IDReader: Document recognition in video stream // 2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR). – IEEE, 2017. – Vol. 6. – P. 39-44.

使用N-gram模型自动识别合同文件图像中的修改

简要结论

More articles: