Automatisierung der Identifizierung von Änderungen im Bild von Vertragsdokumenten mithilfe des N-Gramm-Modells

Jeder moderne Mensch weiß, dass Sie ein Dokument nicht früher unterschreiben müssen, als er es gelesen hat. Verstöße gegen diese einfache Regel werden manchmal von unerwarteten Konsequenzen überrascht, die hätten vermieden werden können, wenn Sie das Dokument vor der Unterzeichnung geprüft hätten, einschließlich dessen, was in Kleinbuchstaben geschrieben ist. Tricks in Verträgen von Dienstleistern werden als Teil von Witzen und Filmen verwendet. Zum Beispiel in dem Film Blinded by DesiresDer Protagonist beendete einen sehr ungünstigen Deal mit dem Teufel, obwohl er die in Artikel 147 Absatz 3 Teil 3 des Vertrags beschriebenen Bedingungen für die Beendigung des Vertrages nicht kannte. Eine ähnliche Situation ist im wirklichen Leben manchmal bei Dienstleistern möglich. Im Internet finden Sie eine Beschreibung von merkwürdigen Fällen, in denen ein Bankkunde die Vertragsbedingungen zu seinen Gunsten geändert hat. Dies war eine Überraschung für die Bank. Im heutigen Artikel werden wir über einen Algorithmus sprechen, der für Banken und andere Kreditorganisationen äußerst nützlich ist und automatisch Änderungen an den Bildern von Vertragsdokumenten erkennt. Also schau unter die Katze!

Derzeit bieten viele Unternehmen, die eine große Anzahl neuer Kunden anziehen, an, eine Vertragsvorlage zur Selbstvorbereitung von ihrer Website herunterzuladen. Der gedruckte, ausgefüllte und unterschriebene Vertrag wird zur Unterzeichnung an die zweite Partei übertragen. Natürlich überprüft die zweite Partei die von potenziellen Kunden erstellten Verträge, indem sie beispielsweise die eingereichten Dokumente manuell überprüft. Die Anzahl solcher Dokumente kann sehr groß sein, daher sind mehrere aufmerksame Mitarbeiter an der Prüfung beteiligt. Wenn Sie jedoch mehrere Dutzend identischer (bedeutungsvoller) Dokumente pro Tag überprüfen, kann selbst ein ordentlicher Mitarbeiter Fehler überspringen. Dies erklärt die Betrugsfälle, die bei der manuellen Überprüfung nicht erkannt wurden.

Wir werden über die Automatisierung der oben genannten routinemäßigen Überprüfung eines großen Flusses von Vertragsdokumenten unter Verwendung optischer Erkennungstechnologien sprechen, die mehr als einmal (zum Beispiel ein- und zweimal ) Gegenstand von Smart Engines-Artikeln über Habr waren .

Vertragsdokumente gehören zur Klasse der Geschäftsdokumente, die in einigen Büro- und Dokumentenverwaltungssystemen für den Umlauf erstellt werden. Eine Besonderheit von Geschäftsdokumenten ist die Einschränkung des verwendeten Vokabulars und der Art und Weise, wie es gestaltet ist. Dies ist auf den Wunsch zurückzuführen, die Formen von Dokumenten zu vereinheitlichen, um das Verständnis von Geschäftsdokumenten vor allem durch eine Person zu vereinfachen.

Die Vorlage oder Form des Dokuments wird im Voraus beschrieben und besteht aus statischem Text und Feldern zur Eingabe von Informationen. Betrachten Sie zwei gängige Klassen von Vorlagen: eine feste Vorlage und eine flexible Vorlage. Die feste Vorlage erlaubt keine Änderung statischer Texte, beispielsweise bei Verwendung des PDF-Formats. Mit flexiblen Vorlagen können statische Texte geändert werden, z. B. Vorlagen im Microsoft Office-Format. Dementsprechend werden wir zwischen festen und flexiblen Dokumenten unterscheiden.

Bekannte Methoden zum automatisierten Vergleich des Bildes (Scan oder Foto) eines signierten Dokuments mit seinem Prototyp [1]. Sie prüfen auf mögliche Änderungen am Inhalt:

• Ersetzen eines oder mehrerer Zeichen in einem Wort;
• ein Wort durch ein anderes ersetzen;
• Fügen Sie ein Zeichen, ein Wort oder eine Wortgruppe hinzu
• Löschen Sie ein Zeichen, ein Wort oder eine Wortgruppe.

Änderungen am Design des Dokuments sind ebenfalls möglich:

• Ändern des Wortstils (Größe, Schriftarten, Typ);
• Ändern der Felder eines Word-Dokuments;
• Änderung der Anzahl der Absätze;
• Felder ändern.

Das Ändern einer festen Vorlage ist eine absichtliche Fälschung, da es keine andere Möglichkeit gibt, den Wunsch zu erklären, den geschützten Text zu ändern. Die Änderung einer flexiblen Vorlage kann entweder eine Fälschung, ein versehentlicher Tippfehler oder das Ergebnis einer verbesserten Formatierung sein.

Als Nächstes beschreiben wir die Modelle und Methoden für die Suche nach Betrug in Kopien von Geschäftsdokumenten, die sowohl mit festen als auch mit flexiblen Vorlagen gedruckt wurden.

Die Grundlage für den Vergleich des Testbildes (Kopie) und des Referenzbildes (Original) sind die Bilder von Wörtern, die mit einer beliebigen Methode gefunden wurden. Das Bild des Wortes wird durch eine Beschreibung (Deskriptor) dargestellt, der offensichtlichste Deskriptor sind die erkannten Zeichen des Wortes. Wort$$$W$als Text-Feature-Punkt definiert $$$W=(T(W),B(W))$wo - $$$T(W)$- der Kern des Textmerkmalspunkts, dh eine Folge von Zeichen eines Wortes, das aus Zeichen eines bestimmten Alphabets besteht, oder eine Folge von Vertrautheit mit Konformitätsbewertungen der Vertrautheit mit den Zeichen des Alphabets; $$$B(W)$- Rahmen des Textmerkmalspunkts, bestehend aus den Koordinaten des Rahmens $$$B_{x1}(W)$, $$$B_{y1}(W)$, $$$B_{x2}(W)$, $$$B_{y2}(W)$die in einem bestimmten Bereich normalisiert werden können, sowie $$$F(W)$- Zeichen eines Textmerkmals (z. B. ein Headset und eine Änderung der Schriftart).

Ein Text-Feature-Punkt ähnelt einem „grafischen“ Feature-Punkt in einem Bild. Dies bedeutet, dass ein Punkt mehrere Bedingungen erfüllt:

• eine Nachbarschaft, die sich von Punkten in ihrer Umgebung unterscheidet;
• Geräuschunempfindlichkeit;
• Widerstand gegen bestimmte Transformationen (z. B. gegen affine Transformationen oder Skalierung) [2].

Die Eigenschaften der singulären Punkte sind:

• repeatability – , ;
• distinctiveness/informativeness – ;
• locality – ;
• quantity – ;
• accuracy – , , ;
• efficiency – .

Es wird angenommen, dass sich ein Textmerkmalspunkt von benachbarten Textmerkmalpunkten in seiner Umgebung unterscheidet. Wenn mit Nachbarschaft eine Textzeile gemeint ist, unterscheiden sich die meisten Wörter in Geschäftsdokumenten von den Nachbarn in der Zeile. Mehrere identische Wörter in derselben Zeile sind keine einzelnen Textpunkte. Wenn wir jedoch mit Nachbarschaft ein oder zwei benachbarte Wörter meinen, dann sind zwei identische Wörter, die in derselben Zeile stehen und durch benachbarte Wörter unterschieden werden, singuläre Textpunkte. Der Vergleich einzelner Punkte wird unter Verwendung des Ähnlichkeitsmaßes d durchgeführt, das beim Vergleich von zwei Punkten, die einer Stelle im Bild entsprechen, Werte nahe Null und beim Vergleich von Punkten von verschiedenen Stellen im Bild große Werte annehmen sollte.Vergleiche von zwei Kernen von Text-Singularpunkten in diesem Artikel basieren auf der Levenshtein-Entfernung$$$\rho_{Lev}$[3] und seine Modifikationen. Schwelle$$$d(W)$ Wortvergleiche $$$T(W)$mit anderen Worten wird es im Voraus berechnet. Wenn$$$\rho_{Lev}(W, W_r)\lt d(W)$dann das Wort $$$W_r$und Textmerkmalspunkt $$$W$sind identisch , sonst unterschiedlich.

Ein Feature-Point-Deskriptor ist eine Kennung, die beim Abgleichen von Feature-Punkten verwendet wird. Es wird erwartet, dass der Deskriptor unveränderlich ist, wenn einzelne Punkte in Bezug auf Bildtransformationen abgeglichen werden.

Die Methode zum Extrahieren einzelner Punkte aus einem Bild wird als Detektor bezeichnet. DetektorEin Text-Feature-Point ist eine Erkennungsprozedur unter Verwendung einer OCR, die Feature-Point-Deskriptoren aus einem Dokumentbild extrahiert. Die Eigenschaften der oben aufgeführten Merkmalspunkte gelten für Textmerkmalspunkte im Fall der Fähigkeit moderner OCR, verschiedene Arten von Bildverzerrungen zu kompensieren. Die Einzigartigkeit von Textsingularitätsdeskriptoren wird durch die Struktur von Dokumenten (eindeutige Aufteilung eines Dokuments in Konstellationen - Abschnitte, Absätze und Zeilen) und natürliche Spracheigenschaften (ein seltener Zufall in Dokumenten mit zwei benachbarten Wörtern) bestimmt. Verschiedene Beziehungen zwischen textuellen Singularpunkten (Beziehungen oben - unten, rechts - links oder geometrischer Abstand zwischen Frames) ermöglichen es Ihnen, Punkte mithilfe von Clustering-Algorithmen zu Konstellationen zu kombinieren.

Im Idealfall extrahiert OCR alle textspezifischen Punkte fehlerfrei aus dem Bild und der Dokumentvorlage. Auf diese Weise können Sie Konstellationen bilden, insbesondere die Linie. Der Vergleich einer Kopie mit einer Referenz besteht darin, eine eindeutige Entsprechung zwischen allen oder einem Teil der einzelnen Textpunkte der Referenz und einer Reihe von textspezifischen Punkten der Kopie herzustellen. Der Prozess der Herstellung der Korrespondenz zwischen Punkten oder Konstellationen von Punkten wird als Koordination bezeichnet.

Die Koordination fester Dokumente umfasst:

• die Suche nach Korrespondenz eines beliebigen Punktes im Referenzpunkt in der Kopie;
• Suche nach Korrespondenz eines beliebigen Punktes in der Kopie an den Punkten des Standards;
• Suche nach Korrespondenz einer statischen Linie des Standards an Punkten der Kopie;
• Suche nach Korrespondenz einer statischen Kopierzeile an den Punkten des Standards;
• Überprüfung der Identität der Bilder jedes Paares koordinierter Bilder.

Jede festgestellte Inkonsistenz ist eine mögliche Änderung. Natürlich kann die festgestellte Inkonsistenz auf Detektorfehler (OCR) oder Dokumentbildverzerrungen zurückzuführen sein. Die Erklärung des Problems besteht darin, alle Änderungen in der Kopie des Dokuments zu finden.

Bei der Koordination flexibler Dokumente wird eine Entsprechung zwischen allen Wörtern eines statischen Textes hergestellt. Im Gegensatz zu festen Dokumenten wird jedoch keine Entsprechung zwischen statischen Textzeilen eines flexiblen Dokuments angenommen. In flexiblen Dokumenten sind legitime Änderungen möglich, die die Bedeutung des Textes nicht ändern, z. B. das Ändern der Schriftart, das Ändern der Zeilengrenzen und Zeilenumbrüche. Solche Änderungen können zu Zeilenumbrüchen auf einer anderen Seite führen. Daher sollte ein Vergleich mehrseitiger flexibler Dokumente für die gesamte Seitenfolge durchgeführt werden.

Im allgemeinen Fall ist ohne Kenntnis der Struktur des Dokuments die Koordination aller Wörter der Test- und Referenzdokumente erforderlich. Ein klarer Nachteil der vollständigen Koordination von Wörtern sind die unvermeidlichen Erkennungsfehler, insbesondere bei Fotos (siehe Beispiel eines Fragmentes eines Textbildes mit Verzerrungen in der folgenden Abbildung), die als Modifikationen interpretiert werden. Die für die Überprüfung verantwortliche Person muss zusätzliche Zeit damit verbringen, nach falschen Änderungen zu suchen.



Bei vollständiger Abstimmung der Wörter der Kopie und des Originals können neben falschen Erkennungsfehlern auch andere unbedeutende Unterschiede auftreten. Tatsache ist, dass aus Sicht des funktionalen Benutzers des Programms zum Vergleichen der Kopie und des Originals nicht alle Wörter den gleichen Wert haben. In der Tat ist eine Teilmenge der Wörter einer Seite eines Dokuments, die die wesentlichen Vertragsbedingungen bestimmt, wertvoll. Es wird davon ausgegangen, dass die Aufgabe des Betrügers darin besteht, solche Änderungen vorzunehmen, die vor Gericht oder in einem Gerichtsverfahren der Organisation, die den Vertrag mit dem Betrüger unterzeichnet hat, Schaden zufügen können. Geben Sie eine formale Definition dieser BedeutungWorte sind kaum möglich, sie werden von Experten bestimmt. Darüber hinaus werden einige Wörter in Kombination mit benachbarten Wörtern signifikant. Zum Beispiel ist das Teilchen "nicht" in Kombination mit dem benachbarten Wort "Garantien" signifikant. Die Änderung des Wortes „Vertrag“ in das Wort „Nichtvertrag“ ist unerheblich, da es in einem Gerichtsverfahren einem Betrüger keine Vorteile bringen kann.

Somit ist eine andere Formulierung des Problems möglich, bei der sowohl die Struktur des Dokuments als auch die Platzierung der für die Überprüfung wesentlichen Wörter bekannt sind. In dieser Anweisung besteht das Dokumentmodell aus Absätzen und Textzeichenfolgen. Jede Textzeile und jeder Absatz wird durch eine Reihe von Text-Singularpunkten dargestellt, deren Reihenfolge für einen bestimmten Absatz oder eine bestimmte Zeile eindeutig ist. Zeilen und Absätze können auch Wörter enthalten, die nicht eindeutig sind, dh wiederholt werden oder sich sogar in der Nähe befinden. In besonderen Fällen ist es möglich, den Abstand zwischen eindeutigen Wörtern zu kennen, der durch die Anzahl der Zwischenzeichen oder den geometrischen Abstand zwischen den Bildern von Wörtern bestimmt wird.

Die Verwendung eines einfachen N-Gramm-Wortmodells hat sich als effektiv erwiesen. Das N-Gramm-Modell wird für verschiedene Aufgaben verwendet, z. B. zum Komprimieren oder Codieren von Texten. Bei der Verarbeitung von Texten in einer natürlichen Sprache sind N-Gramm nützlich, um Fehler zu finden und zu korrigieren (darüber haben wir bereits zuvor geschrieben ).

Um nach Schlüsselwörtern zu suchen, werden N-Gramm Wörter in den folgenden Formen verwendet:

$$$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_2 (w_i )=〈l_1 (w_i ),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_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_5 (w_i )=〈l_2 (w_i ),l_1 (w_i ),w_i,r_1 (w_i ),r_2 (w_i ) 〉 ,$

Wo $$$r_k (w_i)$, $$$l_q (w_i)$ein Wort rechts oder links vom zentralen Wort $$$w_i$zulässige Abstände sind ebenfalls bekannt $$$\rho_{BT}(w_i, r_1 (w_i))$, $$$\rho_{BT}(r_1 (w_i), r_2 (w_i))$, $$$\rho_{BT}(l_1 (w_i), w_i)$, $$$\rho_{BT}(l_2 (w_i), l_1 (w_i))$zwischen benachbarten Wörtern. Index$$$k$ in der Bezeichnung von N-Gramm $$$n_k (w_i)$Nennen Sie die Länge des N-Gramms.

Ein Absatzmodell besteht aus einer geordneten Folge von N-Gramm
$$$n^1 (w_1), n^2 (w_2), …, n^m (w_m)$mit vordefinierten Tupeln von Wörtern $$$n^i (w_i)$mit bekannten Abständen zwischen Paaren $$$\{n^{j-1}(w_{j-1}), n^j(w_j)\}$. Beachten Sie, dass einige N-Gramm nur für einen Absatz gelten und einige wiederholt werden können. Um die Eindeutigkeit sicherzustellen, können N-Gramm verschiedener Längen verwendet werden: Bigramme, Trigramme, Tetragramme und Pentagramme.

Beim Erstellen eines Absatzmodells werden N-Gramm gebildet, um die Anzahl der eindeutigen N-Gramm zu maximieren. Die Verwendung von N-Gramm im Vergleich zu einzelnen Schlüsselwörtern gewährleistet die Eindeutigkeit für die meisten Absätze von Vertragsdokumenten, vor allem aufgrund der erheblichen Einschränkung der Wortmenge im oben genannten statischen Text.

Es ist sinnvoll, Parameter an realen Datensätzen zu trainieren und zu optimieren. Beachten Sie, dass wir selbst bei realen Datensätzen keine möglichen Änderungen sehen werden, vor allem aufgrund der Klassifizierung solcher Daten durch Datensatzbesitzer. Ich muss Änderungen mit meinen eigenen Händen vornehmen.

Der Trigram-Suchalgorithmus besteht darin, mehrere aufeinanderfolgende Wörter auszuwählen. Natürlich müssen Sie zuerst eine Reihe von Text-Singularpunkten bilden. Dazu haben wir folgende Schritte unternommen:

• Halbtonverarbeitung (MinImage-Bibliothek);
• Normalisierung des Bildes durch Winkel unter Verwendung von Methoden basierend auf der schnellen Hough-Transformation [4] (Smart IDReader API);
• Hervorheben von Wortgrenzen unter Verwendung der Operationen "Erosion" und "Dilatation" (MinImage-Bibliothek);
• Erkennung von Zeichen innerhalb der Grenzen der gefundenen Wörter (Smart IDReader API).

Der Absatz wurde als eine lange Zeile dargestellt.

Ein Vergleich von idealen Wörtern und erkannten Wörtern eines Absatzes wurde unter Verwendung des modifizierten Levenshtein-Abstands durchgeführt. Die Levenshtein-Entfernungsberechnungsalgorithmen sind bekannt. Sie ermöglichen es Ihnen, nicht nur die Anzahl der redaktionellen Vorschriften, sondern auch die Vorschriften selbst zu ermitteln.

Der modifizierte Levenshtein-Abstand wurde verwendet. Zunächst wurde ein eindeutiger Schwellenwert ausgewählt, um ein bestimmtes Wort mit anderen Wörtern zu vergleichen. Für die Weigerung, Wortpaare vom Typ "SEA" = "MOUNTAIN" oder für Bezeichner vom Typ "IDENTIFICATOR196", "IDENTIFIER296", "IDENTIFIER199" zu identifizieren, wurde eine andere Regel angewendet. Für solche Wörter wurden Segmente angegeben, die unverändert bleiben sollten. Das heißt, am Anfang der Wörter "IDENTIFIER ddd" war eine große Anzahl von Fehlern zulässig, aber die Identifizierung mit den gefundenen redaktionellen Anweisungen in den letzten 3 Zeichen des Wortes war verboten.

Eine weitere Änderung bestand darin, das Ersetzen der OCR einiger Zeichen durch ähnliche Zeichen zu kompensieren. Ersetzen Sie formal die Zeichen für das lateinische Alphabet$$$B8$, $$$DO$, $$$1I$Fehler sind, kann jedoch eine Reduzierung des Preises solcher Ersetzungen die Genauigkeit der Wortidentifikation verbessern. Der Preis für das Ersetzen eines Buchstabens für Zeichen mit ähnlichen Stilen wurde während des Trainings gewählt.
Basierend auf mehreren Abständen des Zentrums und der Nachbarn des N-Gramms zu den ausgewählten Analoga wird eine heuristische Schätzung der Bindung des N-Gramms als Ganzes gebildet.
Die Modellparameter (Schwellenwerte, N-Gramm-Längen) wurden während des Trainings ausgewählt, um die Anzahl der N-Gramm-Bindungsfehler zu minimieren und die Anzahl der korrekt gebundenen N-Gramm zu maximieren.

Nach dem Binden der N-Gramm an die Wörter des Absatzes können die folgenden Überprüfungen durchgeführt werden:

• das Vorhandensein aller erwarteten N-Gramm;
• das Vorhandensein aller einzigartigen N-Gramme in einer Kopie;
• die Sequenz von N-Gramm;
• Abstand zwischen benachbarten N-Gramm.

Wenn keine der Überprüfungen durchgeführt wird, muss eine Änderung am wichtigen Schlüsselwort gefunden werden.

Das beschriebene Verfahren wurde an einem Datensatz getestet, der aus 161 Bildern eines Dokuments vom Typ "Vereinbarung" bestand, das mit einer Auflösung von 100 bis 300 dpi gescannt wurde. Wir haben ein Modell mit 33 Schlüsselwörtern untersucht. Einige der Schlüsselwörter in den Datensatzbildern wurden absichtlich gelöscht oder geändert. Es wurden 740 Löschungen und 140 Wortänderungen vorgenommen. OCR Smart IDReader [5] wurde zur Erkennung verwendet.

Die Qualität des Algorithmus wurde anhand der Kriterien Genauigkeit (Präzision) und Vollständigkeit (Rückruf) bewertet, bei deren Bestimmung die Zahlen verwendet wurden:

• modifizierte Wörter gefunden $$$tp$;;
• korrekte Wörter als Modifikationen klassifiziert $$$fp$;;
• modifizierte Wörter nicht gefunden $$$fn$;;
• richtige Wörter als richtig eingestuft $$$tn$.

Die Ergebnisse sind in der Tabelle dargestellt. Die Tabelle zeigt die für mehrere Schwellenwerte berechneten Eigenschaften.$$$d(w_i)$ Einschätzung der Richtigkeit des Wortes im Vergleich zum Referenzwort.


Beachten Sie, dass beim Erkennen von OCR Smart IDReader alle geänderten Wörter gefunden wurden. Metol-Fehler sind mit Erkennungsfehlern verbunden, hauptsächlich aufgrund von Scanfehlern (Vorhandensein überbelichteter Bereiche).

Es ist leicht zu erraten, dass das beschriebene Verfahren eine Einschränkung aufweist, die mit der Genauigkeit der Unterscheidung von Wortgrenzen verbunden ist. Die angegebenen Scanfehler führten zu einer geringen Anzahl von Wortgrenzensuchfehlern (etwa 1-1,5% für einige Schlüsselwörter). Um diese Einschränkung zu beseitigen, bieten wir eine zusätzliche Möglichkeit, nach Wörtern zu suchen. Für einige nicht erkannte N-Gramm wurde eine Teilmenge der Wörter des erkannten Absatzes ausgewählt, in der das Vorhandensein dieses N-Gramms erwartet wurde. Lücken wurden aus der ausgewählten Teilmenge von Wörtern entfernt und eine Zeichenfolge wurde gebildet. Die Wörter des N-Gramms verketteten sich und bildeten einen Teilstring für die Suche. Als nächstes suchten wir nach Teilzeichenfolgen, beispielsweise unter Verwendung eines modifizierten Bitup-Algorithmus unter Verwendung eines modifizierten Levenshtein-Abstands. Dies ermöglicht es, die Anzahl der Fehler von N-Gramm-Prüfungen, die mit Fehlern bei der Suche nach Wortgrenzen verbunden sind, um das 2-3-fache zu reduzieren.

Kurzer Abschluss

Wir haben über ein Tool zur Suche nach Fälschungen von Vertragsdokumenten gesprochen. Natürlich löst dieses Tool das Problem nicht vollständig und es sind manuelle Überprüfungen der gefundenen vermeintlich geänderten Wörter erforderlich. Mit dieser Methode können Sie die Suche nach Änderungen zuverlässig automatisieren und die Anzahl der routinemäßigen manuellen Überprüfungen erheblich reduzieren. Die Komplexität der Entwicklung der beschriebenen Methode war die Schwierigkeit, reale Datensätze mit Fälschungen zu erhalten.