👧 🏇🏽 👆🏽 Algoritmos para el procesamiento posterior de los resultados de reconocimiento de campos de texto ♠️ 🍳 💆🏿

(imagen tomada de aquí )

Hoy nos gustaría informarle sobre la tarea de postprocesar los resultados del reconocimiento de campos de texto basados en el conocimiento a priori del campo. Anteriormente, ya escribimos sobre el método de corrección de campo basado en trigramas , que le permite corregir algunos errores de reconocimiento de palabras escritas en lenguajes naturales. Sin embargo, una parte importante de los documentos importantes, incluidos los documentos de identificación, son campos de diferente naturaleza: fechas, números, códigos VIN de automóviles, números TIN y SNILS, zonas legibles por máquinacon sus sumas de comprobación y más. Aunque no pueden atribuirse a los campos de un lenguaje natural, sin embargo, tales campos a menudo tienen algún modelo de lenguaje, a veces implícito, lo que significa que también se les pueden aplicar algunos algoritmos de corrección. En esta publicación, analizaremos dos mecanismos para los resultados del reconocimiento posterior al procesamiento que se pueden utilizar para una gran cantidad de documentos y tipos de campo.

El modelo de lenguaje del campo se puede dividir condicionalmente en tres componentes:

Sintaxis : reglas que gobiernan la estructura de una representación de campo de texto. Ejemplo: el campo "fecha de vencimiento del documento" en una zona legible por máquina se representa con siete dígitos "DDDDDDD".
: , . : “ ” - – , 3- 4- – , 5- 6- – , 7- – .
: , . : “ ” , , “ ”.

Al tener información sobre la estructura semántica y sintáctica del documento y el campo reconocido, puede crear un algoritmo especializado para el procesamiento posterior del resultado del reconocimiento. Sin embargo, teniendo en cuenta la necesidad de soportar y desarrollar sistemas de reconocimiento y la complejidad de su desarrollo, es interesante considerar métodos y herramientas "universales" que permitan, con un mínimo esfuerzo (de los desarrolladores), construir un algoritmo de posprocesamiento bastante bueno que funcione con una clase extensa. documentos y campos. La metodología para configurar y soportar dicho algoritmo estaría unificada, y solo el modelo de lenguaje sería un componente variable de la estructura del algoritmo.

Vale la pena señalar que el procesamiento posterior de los resultados del reconocimiento de campos de texto no siempre es útil, y a veces incluso perjudicial: si tiene un módulo de reconocimiento de línea bastante bueno y trabaja en sistemas críticos con documentos de identificación, entonces algún tipo de procesamiento posterior es mejor minimizar y producir resultados "tal cual", o monitorear claramente cualquier cambio e informarlo al cliente. Sin embargo, en muchos casos, cuando se sabe que el documento es válido y que el modelo de lenguaje del campo es confiable, el uso de algoritmos de procesamiento posterior puede aumentar significativamente la calidad del reconocimiento final.

Entonces, el artículo discutirá dos métodos de procesamiento posterior que dicen ser universales. El primero se basa en convertidores finitos ponderados, requiere una descripción del modelo de lenguaje en forma de máquina de estados finitos, no es muy fácil de usar, pero es más universal. El segundo es más fácil de usar, más eficiente, solo requiere escribir una función para verificar la validez del valor del campo, pero también tiene una serie de desventajas.

Método de transmisor de extremo ponderado

En este trabajo se describe un modelo hermoso y bastante general que le permite construir un algoritmo universal para los resultados del reconocimiento posterior al procesamiento . El modelo se basa en la estructura de datos de los Transductores de estado finito ponderados (WFST).

Los WFST son una generalización de máquinas de estados finitos ponderados: si una máquina de estados finitos ponderados codifica algún idioma ponderado

(es decir, un conjunto ponderado de líneas sobre un cierto alfabeto UNA

), entonces WFST codifica un mapa ponderado de un idioma L_1

sobre el alfabeto A_1

en un idioma L_2

sobre el alfabeto A_2

. Una máquina de estados finitos ponderada, que toma una cadena

sobre el alfabeto UNA

, le asigna algo de peso

, mientras que WFST, toma una cadena S_1

sobre el alfabeto A_1

, asocia con él un conjunto de pares (posiblemente infinitos) $\ {& lt; S_2 ^ 1, w_1 & gt;, \ ldots, & lt; S_2 ^ k, w_k & gt;, \ ldots \}$ , donde S_2 ^ i

está la línea sobre el alfabeto A_2

en la que se convierte la línea S_1

, y

es el peso de tal conversión. Cada transición del convertidor se caracteriza por dos estados (entre los cuales se realiza la transición), los caracteres de entrada (del alfabeto A_1

), los caracteres de salida (del alfabeto A_2

) y el peso de la transición. Un carácter vacío (cadena vacía) se considera un elemento de ambos alfabetos. El peso de la conversión de

cadena a cadena

es la suma de los productos de los pesos de transición a lo largo de todas las rutas en las que la concatenación de los caracteres de entrada forma la cadena

, y la concatenación de los caracteres de salida forma la cadena

, y que transfieren el convertidor del estado inicial a uno de los terminales.

La operación de composición se determina a través de WFST, en la que se basa el método de procesamiento posterior. Dése dos transformadores T_1

, y

convertir la línea

por encima Hacha

de la línea

con el peso w_1

, y

se convierten

más

a la línea

con el peso w_2

. Luego, el convertidor $T_1 \ circ T_2$ , llamado la composición de los convertidores, convierte la cadena

en una cadena

con un peso $w_1 \ cdot w_2$ . La composición de los transductores es una operación computacionalmente costosa, pero se puede calcular perezosamente: los estados y las transiciones del transductor resultante se pueden construir en el momento en que se necesita acceder.

El algoritmo para el procesamiento posterior del resultado del reconocimiento basado en WFST se basa en tres fuentes principales de información: el

modelo de hipótesis , el modelo de error

y el modelo de lenguaje

. Los tres modelos se presentan en forma de transductores finales ponderados:

( WFST – , ), , . , $C_1, C_2, \ldots, C_N$ , (): $C_i = \{<a_{i1}, q_{i1}>, \ldots, <a_{ik}, q_{ik}>\}$ , $a_{ij}$ – - , $q_{ij}$ – () . - , : - , - – , - - . - $a_{ij}$ , . , .

. 1. , WFST ( ). .

, , . WFST ( ). . , .
. .. , ( ).

Después de definir un modelo de hipótesis, errores y un modelo de lenguaje, la tarea de los resultados del reconocimiento posterior al procesamiento ahora se puede plantear de la siguiente manera: considere la composición de los tres modelos $T=HM\circ EM\circ LM$ (en términos de composición WFST). El convertidor

codifica todas las conversiones posibles de cadenas

del modelo de hipótesis

en cadenas

del modelo de lenguaje

, aplicando

transformaciones codificadas en el modelo de error a cadenas

. Además, el peso de tal transformación incluye el peso de la hipótesis original, el peso de la transformación y el peso de la cadena resultante (en el caso de un modelo de lenguaje ponderado). En consecuencia, en dicho modelo, el posprocesamiento óptimo del resultado del reconocimiento corresponderá a la ruta óptima (en términos de peso) en el convertidor

traduciéndolo de la inicial a uno de los estados terminales. La línea de entrada a lo largo de esta ruta corresponderá a la hipótesis inicial seleccionada, y la línea de salida al resultado de reconocimiento corregido. Se puede buscar la ruta óptima utilizando algoritmos para encontrar las rutas más cortas en gráficos dirigidos.

Las ventajas de este enfoque son su generalidad y flexibilidad. El modelo de error, por ejemplo, puede expandirse fácilmente de tal manera que tenga en cuenta la eliminación y la adición de caracteres (para esto, solo vale la pena agregar transiciones con un símbolo de salida o entrada vacío, respectivamente, al modelo de error). Sin embargo, este modelo tiene desventajas significativas. Primero, el modelo de lenguaje aquí debe presentarse como un transformador finito ponderado finito. Para lenguajes complejos, dicho autómata puede resultar bastante engorroso, y en caso de un cambio o refinamiento del modelo de lenguaje, será necesario reconstruirlo. También se debe tener en cuenta que la composición de los tres transductores como resultado tiene, por regla general, un transductor aún más voluminoso,y esta composición se calcula cada vez que inicia el procesamiento posterior de un resultado de reconocimiento. Debido al volumen de la composición, la búsqueda del camino óptimo en la práctica debe realizarse con métodos heurísticos, como la búsqueda A *.

Utilizando el modelo de verificación de gramáticas, es posible construir un modelo más simple de la tarea de los resultados del reconocimiento posterior al procesamiento, que no será tan general como el modelo basado en WFST, pero será fácilmente extensible y fácil de implementar.

Una gramática de verificación es un par G=<A,P>

, donde

está el alfabeto, y

es el predicado de la admisibilidad de una cadena sobre el alfabeto

, es decir. $P:A^*\rightarrow\{0,1\}$ . Una gramática de verificación codifica un determinado idioma sobre el alfabeto de la

siguiente manera: una línea $S\in A^*$ pertenece al idioma si el predicado

toma un valor verdadero en esta línea. Vale la pena señalar que verificar la gramática es una forma más general de representar un modelo de lenguaje que una máquina de estados. De hecho, cualquier lenguaje representado como una máquina de estados finitos

, puede representarse en forma de una gramática de verificación (con un predicado $P(S)\Leftrightarrow S\in \mathrm{acc}(T)$ , donde $\mathrm{acc}(T)$ es el conjunto de líneas aceptadas por el autómata

. Sin embargo, no todos los idiomas que pueden representarse como una gramática de verificación son representables como un autómata finito en el caso general (por ejemplo, un lenguaje de palabras de longitud ilimitada sobre alfabeto $A=\{a,b\}$ , en el que el número de caracteres es

mayor que el número de caracteres

.)

Deje que el resultado del reconocimiento (modelo de hipótesis) se dé como una secuencia de celdas $C_1, C_2, \ldots, C_N$ (igual que en la sección anterior). Por conveniencia, suponemos que cada celda contiene K alternativas y todas las estimaciones alternativas toman un valor positivo. La evaluación (peso) de la cadena se considerará el producto de las calificaciones de cada uno de los caracteres de esta cadena. Si el modelo de lenguaje se da en forma de una gramática de verificación G=<A,P>

, entonces el problema de posprocesamiento se puede formular como un problema de optimización discreta (maximización) en el conjunto de controles A^N

(el conjunto de todas las líneas de longitud

sobre el alfabeto

) con el predicado de admisibilidad

y funcional $F(S)=\prod_{i=1}^{N}q_i(S_i)$ , donde

es la estimación del símbolo S_i

en la

celda i-ésima .

Cualquier problema de optimización discreta (es decir, con un conjunto finito de controles) se puede resolver utilizando una enumeración completa de controles. El algoritmo descrito itera eficientemente sobre los controles (filas) en orden decreciente del valor funcional hasta que el predicado de validez acepte el valor verdadero. Establecemos como el

número máximo de iteraciones del algoritmo, es decir El número máximo de filas con la estimación máxima sobre la cual se calculará el predicado.

En primer lugar, ordenar las alternativas en orden descendente de las estimaciones, y suponemos además que para cualquier celda de la C_i

desigualdad $q_{ij}\ge q_{ik}$ de que es cierto j<k

. La posición será la secuencia de índices $j_1,\ldots,j_N$ correspondientes a la fila. $a_{1j_1},\ldots,a_{Nj_N}$ . Evaluación de posición, es decir valor funcional en esa posición, tenga en cuenta las evaluaciones de alternativas de productos que corresponden a los índices incluidos en la posición: $\prod_{i=1}^N q_i{j_i}$ . Para almacenar posiciones, necesita la estructura de datos de PositionBase , que le permite agregar nuevas posiciones (obteniendo sus direcciones), obtener la posición en la dirección y verificar si la posición especificada se agrega a la base de datos.

En el proceso de enumerar posiciones, seleccionaremos una posición no vista con una calificación máxima, y luego agregaremos a la cola para consideración PositionQueue todas las posiciones que se pueden obtener de la actual agregando uno a uno de los índices incluidos en la posición. La cola para consideración PositionQueue contendrá triples <Q,R,I>

, donde

- evaluación de la posición no

revisada , - dirección de la posición vista en PositionBase desde la cual se obtuvo esta posición,

- índice del elemento de posición con la dirección

que se incrementó en uno para obtener esta posición. Posicionar una cola PositionQueue requerirá una estructura de datos que le permita agregar otro triple <Q,R,I>

, así como recuperar un triple con la calificación máxima

.

En la primera iteración del algoritmo, es necesario considerar la posición $S_1=\{1,1,\ldots,1\}$ con la estimación máxima. Si el predicado

toma el valor verdadero en la línea correspondiente a esta posición, entonces el algoritmo termina. De lo contrario, la posición se S_1

agrega a PositionBase y enPositionQueue agrega todos los triples de la vista $<Q\cdot q_{i2}/q_{i1},R(S_1),i>$ , para todos $i\in\{1,\ldots,N\}$ , dónde R(S_1)

está la dirección de la posición inicial en PositionBase . En cada iteración posterior del algoritmo, el triple con el valor máximo de la estimación se extrae de PositionQueue , la posición en cuestión se restaura a la dirección de la posición inicial y el índice . Si la posición ya se ha agregado a la base de datos de las posiciones consideradas de PositionBase , se omite y las tres siguientes con el valor máximo de la estimación se extraen de PositionQueue . De lo contrario, el valor del predicado se verifica en la línea correspondiente a la posición . Si el predicado <Q,R,I>

toma el valor verdadero en esta línea, luego termina el algoritmo. Si el predicado

no acepta el valor verdadero en esta línea, entonces la línea se

agrega a PositionBase (con la dirección asignada R(S)

), todas las posiciones derivadas se agregan a la cola PositionQueue y continúa la siguiente iteración.

FindSuitableString(M, N, K, P, C[1], ..., C[N]):
      i : 1 ... N:
         C[i]    
    ( )
     PositionBase  PositionQueue
    S_1 = {1, 1, 1, ..., 1}
     P(S_1): 
        : S_1,  
    ( )
     S_1  PositionBase   R(S_1)
      i : 1 ... N:
         K > 1, :
              <Q * q[i][2] / q[i][1], R(S_1), i>  PositionQueue
        ( )
    ( )
        PositionBase  M:
           PositionQueue:
              PositionQueue  <Q, R, I>   Q
            S_from =   PositionBase   R
            S_curr = {S_from[1], S_from[2], ..., S_from[I] + 1, ..., S_from[N]}
             S_curr   PositionBase:
                 
            :
                 S_curr  PositionBase   R(S_curr)
            ( )
             P(S_curr):
                : S_curr,  
            ( )
              i : 1 ... N:
                 K > S_curr[i]:
                      <Q * q[i][S_curr[i] + 1] / q[i][S_curr[i]], 
                                     R(S_curr),
                                     i>  PositionQueue
                ( )
            ( )
               
        ( )
    ( )
        M

Tenga en cuenta que durante las

iteraciones, el predicado se verificará no más de

una vez, no habrá más

adiciones a PositionBase , y además de PositionQueue , la extracción de PositionQueue , así como una búsqueda en PositionBase , no ocurrirá más de $M\cdot N$ una vez. Si la implementación PositionQueue usó "grupo" de estructura de datos, y para la organización PositionBase que usó la estructura de datos "Bor", la complejidad del algoritmo es $O\left(M \cdot \left(p(N) +N^2+N \log(M\cdot N)\right)\right)$ , donde p(N)

- el predicado de prueba más extremo

en la longitud de la línea

.

Quizás el inconveniente más importante del algoritmo basado en el control de las gramáticas es que no puede procesar hipótesis de diferentes longitudes (que pueden surgir debido a errores de segmentación : pérdida u ocurrencia de caracteres adicionales, pegado y corte de caracteres, etc.), mientras que Los cambios en hipótesis tales como “eliminar un carácter”, “agregar un carácter” o incluso “reemplazar un carácter con un par” pueden codificarse en el modelo de error del algoritmo basado en WFST.

Sin embargo, la velocidad y la facilidad de uso (cuando se trabaja con un nuevo tipo de campo, solo necesita dar acceso al algoritmo a la función de validación de valor) hacen que el método basado en las gramáticas de verificación sea una herramienta muy poderosa en el arsenal del desarrollador de sistemas de reconocimiento de documentos. Utilizamos este enfoque para una gran cantidad de diversos campos, como varias fechas, número de tarjeta bancaria (predicado: verificar el código lunar ), campos de áreas de documentos legibles por máquina con sumas de verificación y muchos otros.

La publicación se preparó sobre la base del artículo : Un algoritmo universal para los resultados del reconocimiento posterior al procesamiento basado en la validación de gramáticas. K.B. Bulatov, D.P. Nikolaev, V.V. Postnikov. Actas de ISA RAS, Vol. 65, No. 4, 2015, pp. 68-73.

Algoritmos para el procesamiento posterior de los resultados de reconocimiento de campos de texto

Método de transmisor de extremo ponderado

More articles: