Prologo

Buenas tardes, queridos lectores. En este artículo hablaré sobre cómo analizar un número escrito en palabras en ruso.

Este analizador hace que sea inteligente extraer números del texto con errores cometidos como resultado de una entrada incorrecta o como resultado del reconocimiento óptico de texto de una imagen (OCR).

Para los perezosos:
Enlace al proyecto github: enlace .

Del algoritmo al resultado

Esta sección describirá los algoritmos utilizados. ¡Atención, muchas cartas!

Declaración del problema.

En el trabajo, necesito reconocer el texto de un documento impreso fotografiado con una cámara de teléfono inteligente / tableta. Debido al acuerdo de no divulgación, no puedo dar un ejemplo de una fotografía, pero el punto es que el documento tiene una tabla en la que ciertos indicadores están escritos en números y en palabras, y estos datos deben leerse. Es necesario analizar el texto en palabras como una herramienta de validación adicional para garantizar que el número se reconozca correctamente. Pero, como sabe, OCR no garantiza el reconocimiento preciso de texto. Por ejemplo, el número veinte, escrito en palabras, puede reconocerse como "dvupat" o incluso como "dvupat". Es necesario tener esto en cuenta y extraer la cantidad máxima de información, evaluando la magnitud del posible error.

Nota Para el reconocimiento de texto, uso tesseract 4. Para .NET, no hay un paquete NuGet listo para usar de la cuarta versión, así que creé uno de la rama principal del proyecto, que puede ser útil: Genesis.Tesseract4 .

Algoritmo de análisis numérico básico

Comencemos con uno simple, es decir, con un algoritmo de reconocimiento de texto escrito en palabras, hasta ahora sin errores. Si está interesado en el análisis inteligente, omita esta sección.

No soy particularmente bueno para buscar en Google, por lo que no encontré de inmediato un algoritmo listo para resolver este problema. Sin embargo, esto es incluso para mejor, porque Un algoritmo inventado por nosotros mismos da más espacio para la codificación. Y la tarea en sí resultó ser interesante.

Entonces, tomemos un pequeño número, por ejemplo, "ciento veintitrés". Se compone de tres palabras ( tokens ), cada una de las cuales corresponde a un número, todos estos números se resumen:

Hasta ahora, todo es simple, pero profundizamos, por ejemplo, consideremos el número "doscientos doce mil ciento cinco".

Como puede ver, cuando hay miles en el número (así como millones y otros grados de mil), el número se divide en partes que consisten en un número pequeño local, en el ejemplo anterior, 212, y un factor (1000). Puede haber varios fragmentos de este tipo, pero todos van en orden descendente del multiplicador, por ejemplo, mil o mil no pueden seguir a mil. Esto también es cierto para partes de un número pequeño, ya que cientos no pueden seguir a cientos y decenas de decenas, por lo que la entrada "ciento quinientos" es incorrecta. Llamaremos a una característica que relaciona dos tokens del mismo tipo con un nivel , por ejemplo, los tokens "cien" y "trescientos" tienen un nivel, y es mayor que el token "cincuenta".

De estas consideraciones, nace la idea de un algoritmo. Escribamos todos los tokens ( muestras ) posibles, a cada uno de los cuales asignaremos un número, así como dos parámetros: el nivel y el signo del multiplicador.

De hecho, puede agregar cualquier otro token a esta tabla, incluso para idiomas extranjeros, solo no olvide que en algunos países se usa un sistema de nombres largo, en lugar de uno corto.

Ahora pasemos al análisis. Obtendremos cuatro cantidades:

1. Nivel global (globalLevel). Indica el nivel del último multiplicador. Inicialmente indefinido y necesario para el control. Si nos encontramos con un token multiplicador cuyo nivel es mayor o igual que el global, entonces este es un error.
2. Valor global (globalValue). El sumador total, donde el resultado es el resultado de multiplicar el número local y el factor.
3. Nivel local (localLevel). Indica qué nivel tenía el último token. Inicialmente indefinido, funciona de manera similar al nivel global, pero se restablece después del descubrimiento del multiplicador.
4. Valor local ( valor local ) Un sumador de tokens no multiplicador, es decir números hasta 999.

El algoritmo es el siguiente:

1. Divide la cadena en tokens usando el "\ s +" regular.
2. Tomamos el siguiente token, obtenemos información al respecto de la muestra.
3. Si es un multiplicador:
   
   • Si se establece el nivel global, nos aseguramos de que sea mayor o igual que el nivel del token. Si no, esto es un error; el número es incorrecto.
   • Establece el nivel global al nivel del token actual.
   • Multiplique el valor del token por el valor local y agregue el resultado al valor global.
   • Limpiamos el valor local y el nivel.
4. Si esto no es un multiplicador:
   
   • Si se establece el nivel local, nos aseguramos de que sea mayor o igual que el nivel del token. Si no, esto es un error; el número es incorrecto.
   • Establece el nivel local al nivel del token actual.
   • Agregue el valor del token al valor local.
5. Devolvemos el resultado como la suma de valores globales y locales.

Un ejemplo de trabajo para el número "dos millones doscientos doce mil ciento ochenta y cinco".

El resultado será 2.212.185.

Análisis inteligente

Este algoritmo se puede usar para implementar otras comparaciones, y no solo para analizar números, por esta razón trataré de describirlo con más detalle.

Con el análisis del número escrito correctamente resuelto. Ahora pensemos qué errores pueden ocurrir si el número obtenido como resultado de OCR se escribe incorrectamente. No considero otras opciones, pero puede modificar el algoritmo para una tarea específica.

He identificado tres tipos de errores que encontré en el proceso de trabajo:

1. Reemplazar personajes con otros con un estilo similar. Por ejemplo, la letra "c" se reemplaza por alguna razón por "p" y "n" por "y" y viceversa. Cuando se utiliza la tercera versión de tesseract, es posible reemplazar la letra "o" con cero. Estos errores, por sí solos, son los más comunes y requieren ajuste para una biblioteca de reconocimiento específica. Entonces, los principios de funcionamiento de las versiones 3 y 4 de tesseract tienen diferencias cardinales, por lo tanto, los errores allí serán diferentes.
   
2. Token merge. Las palabras pueden fusionarse (aún no han encontrado lo contrario). En combinación con el primer error, genera frases demoníacas como "doble uno". Tratemos de demonizar a esos monstruos también.
   
3. Ruido: dejó caracteres y frases en el texto. Desafortunadamente, hay poco que se pueda hacer en este momento, pero hay una posibilidad cuando se recopilan estadísticas suficientemente significativas.
   

Al mismo tiempo, el algoritmo de análisis descrito anteriormente casi no cambia, la principal diferencia está en dividir la cadena en tokens.

Pero comencemos recopilando algunas estadísticas sobre el uso de letras en tokens. De las 33 letras del idioma ruso, solo 20 se usan al escribir enteros no negativos, llamémoslas buenas letras :

Los 13 restantes, respectivamente, se llamarán letras malas . El tamaño máximo de la ficha es de 12 caracteres (13 cuando se cuenta hasta cuatro mil millones). Las subcadenas más largas que este valor deben dividirse.

Para comparar cadenas y tokens, decidí usar el algoritmo Wagner-Fisher , aunque lo llamé el nombre de Levenshtein en el código. No necesito una instrucción editorial, así que implementé una versión del algoritmo compatible con la memoria. Debo admitir que la implementación de este algoritmo resultó ser una tarea más difícil que el analizador en sí.

Un pequeño programa educativo: la distancia de Levenshtein es un caso especial del algoritmo Wagner-Fisher, cuando el costo de insertar, eliminar y reemplazar caracteres es estático. Esto no es así en nuestra tarea. Obviamente, si encontramos una letra mala en una subcadena, entonces debe ser reemplazada por una buena letra, pero reemplazar una buena por una mala es extremadamente indeseable. En términos generales, es imposible, pero la situación depende de la tarea específica.

Para describir el costo de insertar, eliminar y reemplazar caracteres, creé una tabla como esta: un enlace a una tabla con pesos . Si bien se llena con el método de tres P (género, dedo, techo), pero si lo llena con datos basados ​​en estadísticas OCR, puede mejorar significativamente la calidad del reconocimiento de números. El código de la biblioteca contiene el archivo de recursos NumeralLevenshteinData.txt, en el que puede insertar datos de una tabla similar usando Ctrl + A, Ctrl + C y Ctrl + V.

Si se encuentra un carácter que no es de tabla en el texto, por ejemplo, cero, entonces el costo de insertarlo es igual al valor máximo de la tabla, y el costo de eliminar y reemplazar es igual al mínimo, por lo que es más probable que el algoritmo reemplace cero con la letra "o", y si usa la tercera versión de tesseract , entonces tiene sentido agregar cero a la tabla y escribir el precio mínimo para reemplazarlo con la letra "o".

Entonces, preparamos los datos para el algoritmo Wagner-Fisher, hagamos cambios en el algoritmo para dividir la cadena en tokens. Para hacer esto, realizaremos un análisis adicional de cada token, pero antes de eso ampliaremos la información sobre el token con las siguientes características:

• Nivel de error Un número real de 0 (sin error) a 1 (el token es incorrecto), lo que significa qué tan bien se comparó el token con la muestra.
  
• Una señal de uso de un token . Al analizar una cadena con desechos intercalados, parte de los tokens se descartarán, ya que este atributo no se establecerá. En este caso, el valor de error total se considerará como el promedio aritmético de los errores de los tokens utilizados.
  

Algoritmo de análisis de tokens:

1. Estamos tratando de encontrar el token en la tabla tal como está. Si encontramos que todo está bien, devuélvelo.
2. Si no, haga una lista de posibles opciones:

3. Estamos tratando de hacer coincidir el token con la muestra utilizando el algoritmo Wagner-Fisher. Esta opción consta de un token (muestra mapeada) y su error es igual a la mejor distancia dividida por la longitud de la muestra.

   
   Ejemplo: el token "cero" se compara con la muestra "cero", mientras que la distancia es 0.5, porque el costo de reemplazar la letra incorrecta "y" con una buena "o" es 0.5. El error total para este token será 0.5 / 4 = 0.125.
   

4. Si la subcadena es lo suficientemente grande (tengo 6 caracteres), intentamos dividirla en dos partes de al menos 3 caracteres en cada una. Para una cadena de 6 caracteres habrá una sola división: 3 + 3 caracteres. Para una cadena de 7 caracteres, ya hay dos opciones, 3 + 4 y 4 + 3, etc. Para cada una de las opciones, llamamos a la misma función de análisis de tokens de forma recursiva, ingresamos las opciones recibidas en la lista.

   
   

   Para no morir en la recursión, determinamos el nivel máximo de falla. Además, las opciones obtenidas como resultado de la división se degradan artificialmente en una cierta cantidad (opción, por defecto 0.1), de modo que la opción de comparación directa es más valiosa. Tuve que agregar esta operación, porque Los pasos del tipo "doble" se dividieron con éxito en tokens "dos" y "cinco", y no se redujeron a "veinte". Por desgracia, estas son las características del idioma ruso.

   
   

   Ejemplo: el token "doble" tiene una comparación directa con la muestra "veinte", error 0.25. Además, la mejor opción para dividir es "dos" + "cinco" con un costo de 0.25 (reemplazando "a" con "i"), empeorado artificialmente a 0.35, por lo que se prefiere la ficha "veinte".

   
   
5. Después de compilar todas las opciones, seleccionamos la mejor por la cantidad mínima de errores de los tokens que participan en ella. El resultado es devuelto.

Además, la verificación del token se introduce en el algoritmo principal de generación de números para que su error no exceda un cierto valor (opción, por defecto 0,67). Con esto, eliminamos la basura potencial, aunque no con mucho éxito.

El algoritmo en pocas palabras para aquellos que eran demasiado vagos para leer el texto de arriba

Dividimos la cadena de entrada, que es el número en palabras, en subcadenas usando la regularidad \ s +, luego intentamos hacer coincidir cada subcadena con tokens de muestra o dividirla en subcadenas más pequeñas, eligiendo los mejores resultados. Como resultado, obtenemos un conjunto de tokens mediante los cuales generamos un número, y el valor del error se toma como la media aritmética de los errores entre los tokens utilizados en la generación.

Afilar un algoritmo para una tarea específica

En mi tarea, los números no son negativos y son relativamente pequeños, por lo que excluiré tokens innecesarios del "millón" o más. Para la prueba, queridos lectores, por el contrario, agregué tokens de jerga adicionales, lo que permitió analizar cadenas como "cinco piezas", "cortar doscientos" e incluso "tres stolniks y dos piezas de oro". Es divertido, pero ni siquiera requirió cambios en el algoritmo.

Mejora adicional

El algoritmo existente tiene fallas:

1. Control de casos. Las cadenas "dos mil" y "dos mil" se reconocerán con un error cero como 2000. En mi tarea, el control de casos no es necesario, incluso es dañino, pero si necesita dicha función, esto se resuelve mediante la introducción de una bandera adicional en el token que es responsable del caso del próximo token .
   
2. Números negativos Se introduce un token negativo adicional con un procesamiento especial. Nada complicado, pero no olvide que la letra "y" es mala y no aparece en los números, deberá cambiar sus características de peso o esperar que no cambie durante el proceso de OCR.
   
3. Números fraccionarios Se resuelve reemplazando el tipo largo con un doble e introduciendo tokens de "décimos", "centésimos", etc. ... No olvides revisar las escalas de letras.
   
4. Reconocimiento de números ingresados ​​por los usuarios. Porque al ingresar texto manualmente, con frecuencia cometemos errores relacionados con la reedición de siVMolov, debe agregar esta operación al algoritmo Wagner-Fisher.
   
5. Soporte para otros idiomas. Introducimos nuevos tokens, ampliamos la tabla de pesos.
   
6. Manejo de basura. En algunos documentos, se imprimen datos, la calidad de la imagen puede ser deficiente, la celda puede estar curiosamente vacía. En este caso, la basura que debe limpiarse de alguna manera entra en la línea. Lo mejor que puedo ofrecer en este momento es preprocesar el documento antes de OCR. Quitar las líneas de la tabla y llenarlas con un color cercano al color del espacio libre de la celda me ayudó mucho. Esto no resolvió todos los problemas, pero mejoró la calidad del reconocimiento de texto de documentos donde la tabla tenía curvaturas debido a los hematomas del documento o un fotógrafo torcido. Idealmente, debe rotar la celda y reconocerla por separado, si, por supuesto, tiene una tabla.
   

Entonces, ¿cuál es el resultado final?

El proyecto tiene un ejemplo de una aplicación de consola que se ejecuta a través del archivo samples.txt con ejemplos para el analizador. Aquí hay una captura de pantalla de los resultados:

Le cobro que evalúe el resultado, pero en cuanto a mí, no está mal. El error para los ejemplos de reconocimiento real no supera 0.25, aunque todavía no he ejecutado todo el conjunto de documentos disponibles, probablemente no todo será tan fácil allí.

En cuanto a la última sección, siempre me preguntaba cuánto es "dofiga". Además, el programa se dio una respuesta adecuada a cuánto se tarda en tomar (no lo uso, pero aún así) e incluso determinó con precisión el significado de la antigua palabra rusa "oscuridad". Y sí, la conclusión no incluyó otra medida que la educación no permitió agregar, pero el programa cree que es igual a mil =)

Algunas palabras sobre la biblioteca.

Inicialmente, mis planes no incluían la creación de una biblioteca, decidí diseñarla exclusivamente para un Habr. Traté de ordenar el código, pero si lo usa, haga un tenedor o una copia, como lo más probable es que no necesite jerga y otros tokens incluidos en los ejemplos.

La biblioteca en sí está escrita bajo .NET Standart 2.0 y C # 7.x, y los algoritmos se traducen fácilmente a otros idiomas.

En caso de una posible expansión de la biblioteca, agregaré la composición de los componentes importantes del analizador numérico en palabras (espacio de nombres Genesis.CV.NumberUtils):

• RussianNumber.cs: analizador directo
• RussianNumber.Data.cs - archivo con descripción de tokens
• RussianNumber.ToString.cs - convertidor de número a texto en palabras
• RussianNumberParserOptions.cs - opciones de analizador
• NumeralLevenshtein.cs: implementación del algoritmo Wagner-Fisher
• NumeralLevenshteinData.txt - recurso, datos de ponderaciones de letras

Uso:

• RussianNumber.ToString (valor): convierte un número en texto
• RussianNumber.Parse (valor, [opciones]) - convierte texto a número

Conclusión

Realmente espero que el artículo no te haya parecido aburrido a pesar de la abundancia de texto. Recientemente, se me ocurrieron muchos temas relacionados con la visión por computadora, sobre los cuales hay algo que contar, por lo que me gustaría saber una opinión sobre este formato de artículos. ¿Qué vale la pena agregar o, por el contrario, eliminar? ¿Qué es más interesante para ustedes, lectores, los algoritmos mismos o los fragmentos de código?

¿Te gusta el artículo? Mira los otros:

• Soporte de serialización JavaScript JavaScript de clase
  
• Relleno de plantillas de texto con datos basados ​​en modelos. Implementación de .NET usando funciones de bytecode dinámico (IL)