Automatización de la identificación de modificaciones en la imagen de documentos contractuales utilizando el modelo N-gram

Toda persona moderna sabe que debe firmar un documento antes de que lo haya leído. Los infractores de esta regla simple a veces se sorprenden de las consecuencias inesperadas que podrían haberse evitado si examinara el documento antes de firmar, incluido lo que está escrito en letra pequeña. Los trucos en los contratos de los proveedores de servicios se utilizan como parte de bromas y películas. Por ejemplo, en la película Cegado por los deseosel protagonista terminó un trato muy desfavorable con el diablo, a pesar de la ignorancia de los términos de terminación del contrato descritos en el artículo 147, párrafo 3, parte 3 del contrato. Una situación similar a veces es posible en la vida real con los proveedores de servicios. En Internet puede encontrar una descripción de casos curiosos en los que un cliente bancario cambió los términos del acuerdo a su favor, y esto fue una sorpresa para el banco. En el artículo de hoy, hablaremos sobre un algoritmo que es extremadamente útil para los bancos y otras organizaciones de crédito, que detecta automáticamente las modificaciones realizadas en las imágenes de los documentos del contrato. ¡Así que mira debajo del gato!

Actualmente, muchas organizaciones que atraen a una gran cantidad de nuevos clientes, ofrecen descargar una plantilla de contrato de su sitio web para la preparación propia. El contrato impreso, completado y firmado se transfiere para su firma a la segunda parte. Por supuesto, la segunda parte verifica los contratos preparados por clientes potenciales, por ejemplo, verificando manualmente los documentos enviados. El número de dichos documentos puede ser bastante grande, por lo tanto, varios empleados atentos están involucrados en su verificación. Sin embargo, cuando se comprueban varias docenas de documentos idénticos (en sentido) por día, incluso un empleado ordenado puede omitir errores. Esto explica los casos de fraude que no se detectaron durante la verificación manual.

Hablaremos sobre la automatización de la verificación de rutina de un gran flujo de documentos contractuales descritos anteriormente utilizando tecnologías de reconocimiento óptico, que han sido objeto de artículos de Smart Engines sobre Habr más de una vez (por ejemplo, una y dos veces ).

Los documentos contractuales pertenecen a la clase de documentos comerciales que se crean para su circulación en algunos sistemas de gestión de documentos y gestión de oficinas. Una característica distintiva de los documentos comerciales es la limitación del vocabulario utilizado y la forma en que está diseñado. Esto se debe al deseo de unificar las formas de los documentos para simplificar la comprensión de los documentos comerciales, en primer lugar, por una persona.

La plantilla o forma del documento se describe de antemano y consta de texto estático y campos para ingresar información. Considere dos clases comunes de plantillas: una plantilla fija y una plantilla flexible. La plantilla fija no permite la modificación de textos estáticos, por ejemplo, cuando se utiliza el formato PDF. Se pueden usar plantillas flexibles para permitir la modificación de textos estáticos, por ejemplo, plantillas en el formato de Microsoft Office. En consecuencia, distinguiremos entre documentos fijos y flexibles.

Métodos conocidos para la comparación automática de la imagen (escaneo o foto) de un documento firmado con su prototipo [1]. Verifican posibles modificaciones al contenido:

• reemplazo de uno o más caracteres en una palabra;
• reemplazar una palabra con otra;
• Agregar un carácter, palabra o grupo de palabras
• Eliminar un carácter, palabra o grupo de palabras.

También son posibles modificaciones en el diseño del documento:

• cambiar el estilo de las palabras (tamaño, fuentes, tipo);
• cambiar los campos de un documento de Word;
• cambio en el número de párrafos;
• cambiar los campos

La modificación de una plantilla fija es una falsificación intencional, porque no hay otra forma de explicar el deseo de cambiar el texto protegido. La modificación de una plantilla flexible puede ser una falsificación, un error tipográfico accidental o el resultado de un formato mejorado.

A continuación, describimos los modelos y métodos de búsqueda de fraude en copias de documentos comerciales impresos utilizando plantillas fijas y flexibles.

La base para comparar la imagen de prueba (copia) y la imagen de referencia (original) son las imágenes de palabras encontradas por cualquier método. La imagen de la palabra está representada por alguna descripción (descriptor), el descriptor más obvio son los caracteres reconocidos de la palabra. Palabra$$$W$ define como unpunto de característica de texto $$$W=(T(W),B(W))$, donde -$$$T(W)$ es el núcleo de un punto de característica de texto, es decir, una secuencia de caracteres de una palabra que consiste en caracteres de un alfabeto particular o una secuencia de familiaridad con índices de conformidad de familiaridad con caracteres del alfabeto,$$$B(W)$ : marco de punto de característica de texto que consiste en coordenadas de borde$$$B_{x1}(W)$ ,$$$B_{y1}(W)$ ,$$$B_{x2}(W)$ ,$$$B_{y2}(W)$ , que se puede normalizar en un cierto rango, así como$$$F(W)$ : atributos del punto de característica de texto (por ejemplo, modificación de auriculares y fuente).

Un punto de característica de texto es similar a un punto de característica "gráfico" en una imagen, lo que significa un punto que satisface varias condiciones:

• un barrio que difiere de los puntos en su vecindad;
• inmunidad al ruido;
• resistencia a ciertas transformaciones (por ejemplo, a transformaciones afines o escalado) [2].

Las propiedades de los puntos singulares son:

• repetibilidad: un punto particular debe estar en el mismo lugar del objeto de imagen, a pesar de los cambios en el punto de vista y la iluminación;
• distinctiveness/informativeness – ;
• locality – ;
• quantity – ;
• accuracy – , , ;
• efficiency – .

Se supone que un punto de característica de texto es diferente de los puntos de característica de texto vecinos en su vecindad. Si por vecindario nos referimos a una línea de texto, entonces la mayoría de las palabras en los documentos comerciales difieren de los vecinos en la línea. Múltiples palabras idénticas colocadas en la misma línea no serán puntos singulares de texto. Sin embargo, si por vecindario queremos decir una o dos palabras vecinas, entonces dos palabras idénticas colocadas en la misma línea y distinguidas por palabras vecinas serán puntos singulares de texto. La comparación de puntos singulares se lleva a cabo utilizando la medida de similitud d, que debe tomar valores cercanos a cero en el caso de comparar dos puntos correspondientes a un lugar en la imagen, y valores grandes al comparar puntos de diferentes lugares en la imagen.Las comparaciones de dos núcleos de puntos singulares de texto en este documento se basan en la distancia de Levenshtein$$$\rho_{Lev}$ [3] y sus modificaciones. Límite$$$d(W)$ comparaciones de palabras$$$T(W)$ con otras palabras se calcula de antemano. Si$$$\rho_{Lev}(W, W_r)\lt d(W)$ , entonces la palabra$$$W_r$ y punto de característica de texto$$$W$ sonidénticos, de lo contrario diferentes.

Un descriptor de puntos de características es un identificador que se utiliza al hacer coincidir puntos de características. Se espera que el descriptor sea invariable al hacer coincidir puntos singulares con respecto a las transformaciones de imagen.

El método para extraer puntos singulares de una imagen se llama detector.DetectorUn punto de característica de texto es un procedimiento de reconocimiento que utiliza un OCR que extrae descriptores de puntos de característica de una imagen de documento. Las propiedades de los puntos de características enumerados anteriormente son válidas para los puntos de características de texto en el caso de la capacidad del OCR moderno para compensar los diferentes tipos de distorsiones de imagen. La singularidad de los descriptores de singularidad de texto está determinada por la estructura de los documentos (división inequívoca de un documento en constelaciones: secciones, párrafos y líneas) y propiedades del lenguaje natural (una rara coincidencia en documentos de dos palabras adyacentes). Las diversas relaciones entre puntos singulares de texto (las relaciones arriba - abajo, a la derecha - a la izquierda o la distancia geométrica entre los cuadros) le permite combinar los puntos en constelaciones usando algoritmos de agrupamiento.

Idealmente, OCR extrae todos los puntos específicos de texto de la imagen de copia y la plantilla del documento sin errores. Esto le permite formar constelaciones, especialmente la línea. La comparación de una copia y una referencia consiste en establecer una correspondencia inequívoca entre todo o parte de los puntos singulares del texto de la referencia y un conjunto de puntos específicos del texto de la copia. El proceso de establecer correspondencia entre puntos o constelaciones de puntos se llama coordinación.

La coordinación de documentos fijos incluye:

• la búsqueda de correspondencia de cualquier punto en el punto de referencia en la copia;
• buscar correspondencia de cualquier punto de la copia en los puntos de la norma;
• buscar correspondencia de cualquier línea estática del estándar en los puntos de la copia;
• buscar correspondencia de cualquier línea de copia estática en los puntos del estándar;
• verificación de la identidad de las imágenes de cada par de imágenes coordinadas.

Cualquier inconsistencia encontrada es una modificación potencial. Por supuesto, la inconsistencia encontrada puede deberse a errores del detector (OCR) o distorsiones de la imagen del documento. La declaración del problema es encontrar todas las modificaciones en la copia del documento.

La coordinación de documentos flexibles implica establecer una correspondencia entre todas las palabras de un texto estático. Sin embargo, a diferencia de los documentos fijos, no se supone correspondencia entre líneas de texto estático de un documento flexible. En documentos flexibles, son posibles cambios legítimos que no cambian el significado del texto, como cambiar la fuente, cambiar los límites de las líneas, los saltos de línea. Dichas modificaciones pueden provocar saltos de línea en otra página, por lo que se debe realizar una comparación de documentos flexibles de varias páginas para toda la secuencia de páginas.

En el caso general, sin conocimiento de la estructura del documento, es necesaria la coordinación de todas las palabras de la prueba y los documentos de referencia. Un inconveniente definitivo de la coordinación total de las palabras son los inevitables errores de reconocimiento, especialmente para las fotos (ver un ejemplo de un fragmento de una imagen de texto con distorsiones en la figura a continuación), interpretado como modificaciones. La persona responsable de la verificación se verá obligada a pasar más tiempo buscando modificaciones falsas.



Con la coordinación completa de las palabras de la copia y el original, además de los errores de reconocimiento falso, puede haber otras diferencias insignificantes. El hecho es que desde el punto de vista del usuario funcional del programa para comparar la copia y el original, no todas las palabras tienen el mismo valor. De hecho, un subconjunto de las palabras de una página de un documento, que determina los términos esenciales del contrato, es valioso. Se supone que la tarea del estafador es realizar modificaciones que, en los tribunales o en los procedimientos previos al juicio, puedan causar daños a la organización que firmó el contrato con el estafador. Dar una definición formal de tan significativolas palabras apenas son posibles, están determinadas por expertos. Además, algunas palabras se vuelven significativas en combinación con palabras vecinas. Por ejemplo, la partícula "no" en combinación con la palabra adyacente "garantías" son significativas. La modificación de la palabra "contrato" a la palabra "sin contrato" es insignificante, ya que en un proceso judicial no puede aportar beneficios a un estafador.

Por lo tanto, es posible otra formulación del problema, utilizando el conocimiento de la estructura del documento y la colocación de palabras esenciales para la verificación. En esta declaración, el modelo de documento consta de párrafos y cadenas de texto. Cada línea de texto y cada párrafo están representados por un conjunto de puntos singulares de texto cuya secuencia es única para un párrafo o línea dados. Las líneas y los párrafos también pueden contener palabras que no son únicas, es decir, repetidas o incluso ubicadas cerca. En casos especiales, es posible conocer la distancia entre palabras únicas, determinada por el número de caracteres intermedios o la distancia geométrica entre las imágenes de las palabras.

El uso de un modelo simple de palabras de N-gram ha demostrado ser efectivo. El modelo N-gram se utiliza en diversas tareas, como la compresión o la codificación de textos. En el procesamiento de textos escritos en un lenguaje natural, los N-gramos son útiles para encontrar y corregir errores (ya escribimos sobre esto antes ).

Para buscar palabras clave, se usan N-gramos de palabras en las siguientes formas:

$$$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 ) 〉 ,$

Dónde $$$r_k (w_i)$, $$$l_q (w_i)$una palabra a la derecha o izquierda de la palabra central $$$w_i$también se conocen distancias permitidas $$$\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))$entre palabras adyacentes. Índice$$$k$ en la designación de N-gramos $$$n_k (w_i)$llame a la longitud del N-gramo.

Un modelo de párrafo consta de una secuencia ordenada de N-gramos
$$$n^1 (w_1), n^2 (w_2), …, n^m (w_m)$con tuplas de palabras predefinidas $$$n^i (w_i)$, con distancias conocidas entre pares $$$\{n^{j-1}(w_{j-1}), n^j(w_j)\}$. Tenga en cuenta que algunos N-gramos son exclusivos de un párrafo, y algunos pueden repetirse. Para garantizar la unicidad, se pueden usar N-gramos de varias longitudes: bigramas, trigramas, tetragramas y pentagramas.

Al construir un modelo de párrafo, se forman N gramos para maximizar el número de N gramos únicos. El uso de N-gramos en comparación con palabras clave individuales garantiza la unicidad para la mayoría de los párrafos de los documentos del contrato, en primer lugar, debido a la limitación significativa del conjunto de palabras en el texto estático mencionado anteriormente.

Tiene sentido realizar capacitación y optimización de parámetros en conjuntos de datos reales. Tenga en cuenta que incluso en conjuntos de datos reales, no veremos posibles modificaciones, en primer lugar, debido a la clasificación de dichos datos por parte de los propietarios de los conjuntos de datos. Tengo que hacer modificaciones con mis propias manos.

El algoritmo de búsqueda de trigram se reduce a seleccionar varias palabras consecutivas. Por supuesto, primero debe formar un conjunto de puntos singulares de texto. Para hacer esto, hemos tomado los siguientes pasos:

• procesamiento de medios tonos (biblioteca MinImage);
• normalización de la imagen por ángulo usando métodos basados ​​en la transformación rápida de Hough [4] (Smart IDReader API);
• destacando los límites de palabras usando las operaciones de "erosión" y "dilatación" (biblioteca MinImage);
• reconocimiento de caracteres dentro de los límites de las palabras encontradas (API Smart IDReader).

El párrafo se presentó como una larga línea.

Se realizó una comparación de palabras ideales y palabras reconocidas de un párrafo utilizando la distancia de Levenshtein modificada. Los algoritmos de cálculo de distancia de Levenshtein son bien conocidos, le permiten encontrar no solo el número de recetas editoriales, sino también las recetas mismas.

Se utilizó la distancia de Levenshtein modificada. Primero, se eligió un umbral único para comparar una palabra en particular con otras palabras. Para la negativa a identificar pares de palabras del tipo “MAR” = “MONTAÑA” o para identificadores del tipo “IDENTIFICADOR196”, “IDENTIFICADOR296”, “IDENTIFICADOR199”, se aplicó otra regla. Para tales palabras se indicaron segmentos que debían permanecer sin cambios. Es decir, al comienzo de las palabras "IDENTIFICADOR ddd" se permitía una gran cantidad de errores, pero la identificación estaba prohibida con las instrucciones editoriales encontradas en los últimos 3 caracteres de la palabra.

Otra modificación fue para compensar el reemplazo del OCR de algunos caracteres con caracteres similares. Reemplazar formalmente los caracteres del alfabeto latino$$$B8$, $$$DO$, $$$1I$son errores, sin embargo, reducir el precio de tales sustituciones puede mejorar la precisión de la identificación de palabras. El precio de reemplazar una letra por caracteres con estilos similares se eligió durante el entrenamiento.
Basado en varias distancias del centro y vecinos del N-gramo a los análogos seleccionados, se forma una estimación heurística de la unión del N-gramo en su conjunto.
Los parámetros del modelo (umbrales, longitudes de N-gramos) se eligieron durante el entrenamiento para minimizar el número de errores de unión de N-gramo y maximizar el número de N-gramos correctamente unidos.

Después de vincular los N-gramos a las palabras del párrafo, se pueden realizar las siguientes verificaciones:

• la presencia de todos los N-gramos esperados;
• la presencia de todos los N-gramos únicos en una copia;
• la secuencia de N-gramos;
• distancia entre N-gramos adyacentes.

No realizar ninguna de las verificaciones significa encontrar una modificación a la palabra clave importante.

El método descrito se probó en un conjunto de datos que consta de 161 imágenes de un documento del tipo "Acuerdo" escaneadas con una resolución de 100 a 300 ppp. Investigamos un modelo de 33 palabras clave. Algunas de las palabras clave en las imágenes del conjunto de datos se eliminaron o modificaron deliberadamente. Se realizaron 740 eliminaciones y modificaciones de 140 palabras. OCR Smart IDReader [5] se utilizó para el reconocimiento.

La calidad del algoritmo se evaluó mediante los criterios de precisión (Precisión) e integridad (Recuperación), en la determinación de qué números se utilizaron:

• palabras modificadas encontradas $$$tp$;
• palabras correctas clasificadas como modificaciones $$$fp$;
• palabras modificadas no encontradas $$$fn$;
• palabras correctas clasificadas como correctas $$$tn$.

Los resultados se presentan en la tabla. La tabla muestra las características calculadas para varios umbrales.$$$d(w_i)$ evaluación de la corrección de la palabra en comparación con la palabra de referencia.


Tenga en cuenta que cuando se reconoció OCR Smart IDReader, se encontraron todas las palabras modificadas. Los errores de Metol están asociados con errores de reconocimiento, principalmente debido a defectos de escaneo (presencia de áreas sobreexpuestas).

Es fácil adivinar que el método descrito tiene una limitación asociada con la precisión de distinguir los límites de las palabras. Los defectos de escaneo indicados condujeron a un pequeño número de errores de búsqueda de límites de palabras (aproximadamente 1-1.5% para algunas palabras clave). Para eliminar esta limitación, ofrecemos una forma adicional de buscar palabras. Para algunos N-gram no detectados, se seleccionó un subconjunto de las palabras del párrafo reconocido en el que se esperaba la presencia de este N-gram. Se eliminaron las brechas del subconjunto de palabras seleccionado y se formó una cadena de caracteres. Las palabras del N-gram se concatenaron, formando una subcadena para la búsqueda. Luego, buscamos subcadenas, por ejemplo, usando un algoritmo de bitup modificado usando una distancia de Levenshtein modificada. Esto permite reducir en 2-3 veces el número de errores de las comprobaciones de N-gram asociadas con errores en la búsqueda de límites de palabras.

Breve conclusión

Hablamos de una herramienta para buscar falsificaciones de documentos contractuales. Por supuesto, esta herramienta no resuelve completamente el problema y se requieren verificaciones manuales de las palabras supuestamente modificadas encontradas. El método le permite automatizar de manera confiable la búsqueda de modificaciones y reducir significativamente el número de verificaciones manuales de rutina. La complejidad de desarrollar el método descrito fue la dificultad de obtener conjuntos de datos reales con falsificaciones.