algorithm - programa - Detectar páginas vacías en documentos escaneados

programa para escanear texto y pasarlo a word (8)

Parece que intenta convertir todos los documentos de una empresa en documentos digitales. Parte de este documento puede ser muy viejo.

Supongamos que el texto es negro y cualquier otro color es el fondo. Si toma dos promedios ponderados, uno que consiste en lo que cree que es el texto, y uno que consiste en el fondo, puede comparar esos dos y ver si están lo suficientemente distantes para considerar una evaluación posterior. Esto eliminará cualquier envejecimiento desigual del papel.

Los orificios con grapas y perforados en papel son bastante estándar, pero aparecerán grises o no se verán si está escaneando en un fondo blanco. Si no, entonces puedes adivinar dónde están y eliminarlos.

Ahora, observamos áreas de gran interés, áreas donde los píxeles negros son los más densos. Seleccione una parte de eso y OCR. Coloque el inicio superior izquierdo más cercano a un área donde comienza el texto. En un documento típico, un área lineal en blanco sólida que va de izquierda a derecha y otra que va de arriba a abajo denota los lados superior e izquierdo de un párrafo. Puede estar seguro de que tiene una línea de texto porque debajo de una línea de texto hay otro área en blanco de izquierda a derecha. Por lo tanto, no debe preocuparse por seleccionar una parte que corte el texto a la mitad.

Entonces, debemos detectar si una imagen, creada por un escáner, representa una página vacía. Estoy fuera de mi profundidad cuando se trata de procesamiento de imágenes, así que tengo que ejecutar esto por la comunidad.

Esto es lo que se me ocurrió hasta ahora:

Las páginas vacías pueden ser notoriamente blancas, de papel gris reciclado o de papel viejo amarillento. La idea actual es crear un histograma para una página, buscar un aumento pronunciado de la curva y obtener el porcentaje de píxeles más oscuro que eso. Si eso excede un umbral, la página probablemente no esté vacía.
Dado que es probable que clasifique una página que contenga una sola línea de texto en la parte superior como vacía, ubicaríamos la página en mosaico y recopilaremos estadísticas sobre cada mosaico.
Tendríamos que detectar las grapadoras escaneadas y los agujeros de la unión (probablemente solo en ciertos mosaicos), pero esto puede posponerse en una etapa posterior. Sin embargo, si tiene una idea de qué buscar además de estos dos, mencione en un comentario.
Esto necesita ser rápido. Es parte de un flujo de trabajo de procesamiento de documentos que procesa (decenas) de miles de páginas por día. Si procesar una página demora diez segundos más, nuestros clientes tendrán que decirles a sus clientes que tendrán que esperar varios días más para obtener los resultados. (Si esto da como resultado más falsos positivos, algunos clientes preferirían que alguien verifique unas pocas docenas de páginas "vacías" encontradas, antes de que su cliente espere un día más).

Así que aquí están mis preguntas:

¿Es una buena idea tomar esta ruta o hay algo mejor?
Si lo hacemos de esta manera, ¿cómo haré esto? ¿Qué es un algoritmo bueno (barato) para encontrar un umbral para una página? ¿Podríamos ganar una velocidad significativa asumiendo un umbral similar para un lote de documentos? ¿A qué precisión se pueden redondear los valores de brillo antes de registrar? ¿Qué peculiaridades podríamos esperar?

Realice algún tipo de detección de bordes simple. Si el número de píxeles que constituyen los bordes está por debajo de cierto umbral, entonces habrá una alta probabilidad de que la página esté vacía. Esto podría mejorarse clasificando ciertos bordes que corresponden con alta certeza (por forma y ubicación) a los agujeros perforados y grapas como triviales y descontándolos de la métrica.

Si sabe que una página escaneada va a llenar la imagen por completo, entonces el cálculo de la desviación estándar podría ser una buena forma de hacerlo.

Sugiero que se borre ligeramente la página para reducir el ruido. Luego calcule la SD para la página, en teoría, una página donde más o menos todo un color tendrá una SD baja y una con mucho texto tendrá una SD más alta. Luego, se trata de "entrenar" al sistema para que funcione cuando una página es simple y cuando es texto. Puede encontrar que ciertas páginas son difíciles de contar.

Podrías entrenarlo haciéndolo procesar un gran número de páginas, y las repasa todas, y tú dices si es claro o no.

EDITAR

ok, una página en blanco con texto en negro, si solo tenemos la página y nada en el entorno, tendrá un color gris medio, probablemente gris claro. Obtener el promedio es un ciclo para recorrer todos los píxeles, agregar sus valores y luego dividir por el número de píxeles. No soy bueno con esto de o (logN), pero basta con decir que no durará tanto. A menos que tengas imágenes ENORMES.

SD es un segundo bucle for, esta vez estamos contando cuán diferente es cada píxel de la media, y luego dividiéndolo por la media. Esto tomará un poco más de tiempo que el promedio, ya que tenemos que hacer algo como

diff = thispixel - mean; if(diff < 0) { diff = -diff; } runningTotal += diff;

Para una página de color normal, cada píxel estará cerca del valor medio, por lo tanto nuestra SD será baja. Si la SD está por debajo de cierto valor, podemos suponer que esto significa que la página tiene un solo color.

Esto puede tener problemas si su cantidad de texto es muy mínima, ya que no tendrá una gran influencia en la SD, así que tal como sugirió en la pregunta, divida la página en secciones. Sugiero tiras horizontalmente, ya que el texto tiende a ir por este camino. Si hacemos una de estas tiras de a una por vez, una vez que una tira sugiere que tiene texto, podemos detenernos ya que no nos importa si el resto está en blanco o no.

Si borra la página, reducirá el ruido, ya que el impagable píxel del ruido se verá reducido, lo que le proporcionará una SD más "tensa". También podría usarlo para reducir la resolución de su imagen.

Supongamos que la imagen de salsa tiene 300 de ancho por 900 de alto, puede muestrear píxeles en bloques de nueve, 3 * 3, y así terminar con una imagen de 100 de ancho por 300 de alto, por lo que puede usarse para reducir la cantidad de cálculos que debe hacer, en este caso por un noveno!

El principal problema será determinar qué tan alta puede ser una SD con solo una página simple. Tal vez tenga que encontrar la SD de una carga de páginas en blanco.

Por lo que parece, probablemente querrá tener un término medio que le permita estar inseguro y pedir intervención humana, posiblemente permitiendo que el valor humano capacite al sistema para que mejore.

Puede tomar el nivel medio de gris (entero) de cada pocas filas de la imagen escaneada (dependiendo de la resolución y cuántas líneas se requieren para capturar una línea de texto), luego considere la extensión de las filas. Si no hay texto en la página, la extensión de los medios debe ser pequeña (es decir, el fondo varía de 250 a 255), y si hay texto en toda la página o en parte de la página, la extensión sería mucho mayor (es decir, 15 para texto a 250 para fondo).

Me parece que la solución debe ser computacionalmente simple debido a la gran cantidad de páginas que se deben verificar. Los enfoques que requieren un procesamiento posterior (detección de bordes, filtrado, etc.) parecen exagerados y su ejecución tardará mucho más.

No hay necesidad de procesar píxel por píxel, el uso de matrices ayudará a que sea más eficiente, por ejemplo, al utilizar Numpy puedes calcular medias, sumas, etc. para filas, columnas o matrices enteras a la vez de manera mucho más eficiente. Tampoco es necesario procesar CADA píxel, una buena muestra de filas debería ser capaz de realizar la tarea con una precisión similar. La precisión de 8 bits debería estar bien, e incluso podría remuestrear a píxeles grandes antes de ejecutar este algoritmo de procesamiento.

Cuando trabajé para un procesador de documentos (hace ~ 8 años), manejamos proyectos de clientes que variaban desde páginas del tamaño de una letra única de EE. UU. "Limpia" hasta cubiertas / cartulinas de formas irregulares mezcladas con páginas normales. Los operadores alimentaron los archivos previamente ordenados en las máquinas de escaneo y solo tuvieron que observar las esquinas dobladas y problemas mecánicos similares. Su resultado fue múltiples flujos de cientos de imágenes correspondientes a un rango de archivos. Un único operador del escáner podría escanear 15k trozos de papel en un turno (eso es solo 0.60 páginas / seg, mientras que un escáner a velocidad podría manejar 3 páginas / seg y aún escanear ambos lados). Los operadores posteriores procesaron aquellos que buscaban páginas clave para marcar el inicio y el final del archivo. (El reconocimiento de imágenes se puede usar aquí, a veces, pero las personas también proporcionan un control de calidad a los primeros operadores). Teníamos muchas variables que podían establecerse por proyecto del cliente.

Estoy basando el esquema aproximado a continuación en esa experiencia y cómo parece que sus objetivos y flujo de trabajo son similares.

(Terminología: por cliente me refiero a nuestro cliente, por ejemplo, un banco específico. Un proyecto o proyecto de cliente es un conjunto de documentos de ese cliente que contiene muchos archivos, por ejemplo, todas las hipotecas manejadas por una sucursal específica en un año determinado. arreglo lógico que normalmente sería una carpeta de archivos físicos para uno de los clientes del cliente, por ejemplo, todos los documentos de hipoteca para una dirección).

Corta la parte superior, inferior, lados y esquinas. Elimina esto de tus cálculos (aunque probablemente los guardes en la imagen final). Esto cubrirá orificios de grapas, orificios de encuadernación, pero también (minúsculas) esquinas dobladas y bordes rasgados muy pequeños que aparecen como manchas negras. Dependiendo de cómo escanee, los dos últimos pueden ser un problema menor.
Varíe los tamaños de estos cortes para cada proyecto de cliente, según sea necesario. Por ejemplo, incluso un corte de borde muy delgado, digamos 1-2 mm, eliminará la mayoría de los bordes irregulares sin aumentar la tasa de falsos positivos.
Convierte a blanco y negro, 1 bit por píxel. Sospecho que ya está haciendo esto para algunos proyectos de clientes, por lo que hacer esto de manera eficiente y eficaz, que puede ser sutil, no debería ser un trabajo adicional. (Incluso si no almacena la imagen de 1bpp como el resultado final, la conversión será útil para la detección de páginas vacías). Elimine el ruido eliminando los píxeles negros con ninguno o solo un vecino negro (utilizando los 8 vecinos como vecinos).
Después de cortar las extremidades (n. ° 1) y esta reducción de ruido simplista, las páginas en blanco tendrán un número muy bajo de píxeles negros; la mayoría de los espacios en blanco no tendrán píxeles negros, lo que exime a la calidad de página excepcionalmente baja, los sellos entintados (al escanear fondos, se mencionan más abajo) u otras circunstancias en todo el proyecto, y así sucesivamente.
Dependiendo del proyecto del cliente, puede establecer puntos de acceso para ser vistos, lo contrario de cortar los lados. Por ejemplo, mirar una tira de 1 "donde aparecería una sola línea en la parte superior de la página puede reducir los falsos positivos. Escaneo de bajo contraste o copia impresa difuminada (tal vez incluso lápiz, que puede ser común en las caras posteriores) con una sola línea del texto se distinguirá de una página en blanco de esta manera.
Qué secciones vale la pena ver depende de cada proyecto, pero no trates de dividir la página en mosaicos y luego subdividirlas en áreas de interés. En cambio, paraleliza esto en el nivel de página; por ejemplo, 1 trabajador por núcleo, cada trabajador maneja una página completa a la vez.
Según cómo esté manipulando archivos individuales, puede resultarle útil dejar espacios en blanco (antes de marcar las páginas de inicio de archivo, que a menudo es un proceso manual incluso a gran volumen) y luego buscar páginas en blanco en puntos inesperados después de los archivos han sido codificados (por ejemplo, se espera que sea la última página del archivo, sin ser dos espacios en blanco, etc.).
Por ejemplo, si un proyecto en particular solo está escaneando un lado de cada página, entonces detectar dos páginas en blanco es una buena indicación de que un par de páginas en un archivo se voltearon al revés (los clientes a menudo entregan archivos impresos como este) . O bien los clasificadores (que eliminan cosas como grapas y clips) o los primeros operadores de la máquina deberían haber captado este error, pero, independientemente, ahora necesitará una verificación manual para verificar.
Por otro lado, había proyectos que tenían archivos muy limpios por lo que los clasificadores podían insertar páginas en blanco (generalmente de colores) que marcaban los límites de los archivos. En este caso, el segundo grupo de personas siguió haciendo la codificación por número de archivo, pero solo tuvo que examinar la primera página de cada archivo. Esto no fue raro, pero tampoco es común.

Antes de comenzar a hablar un poco, espero encontrar mi punto principal: debes decidir cómo mitigar las tasas de falsos positivos (= pérdida de datos) y falsos negativos (= molestos espacios en blanco y de otra manera inofensivos, pero una tasa máxima permitida aún puede ser especificado en el contrato del proyecto). Eso varía drásticamente según el proyecto y el tipo de archivos / documentos que está manejando, pero le guía sobre cómo hacer la detección. Obtendrá resultados mucho mejores a partir de un enfoque personalizado que intentar un ajuste para todos, incluso si los enfoques personalizados son 80-98% similares.

Si está entregando imágenes de 1bpp al cliente, por ejemplo, es posible que ni siquiera quiera / necesite eliminar espacios en blanco, ya que el tamaño del archivo (y, finalmente, el tamaño del conjunto de datos entregado) no será un problema. Esto puede ser una compensación aceptable cuando la eliminación de la mayoría de los espacios en blanco es más difícil mientras se mantiene una baja tasa de falsos positivos; por ejemplo, para archivos con sellos entintados ("recibido en", "aceptado", "fecha de vencimiento", etc., sangran hasta la parte posterior) u otros problemas, por ejemplo.

Mi clase de otoño hace un montón de proyectos de procesamiento de imágenes. Esto es lo que probaría:

Proyecto de color a escala de grises
Vierta todos los píxeles en un histograma simple con decir 100 cubos entre 0 y 1
Encuentre un mínimo local en el histograma de modo que el valor absoluto de above - below sea lo más pequeño posible, donde above encuentra el número de píxeles más brillantes y below está el número de píxeles más oscuros
Forzar los píxeles above a blanco y los píxeles below a negro
Si lo desea, como medida adicional, puede eliminar los bordes negros
Si apenas hay píxeles negros, la página está en blanco

Los primeros dos pasos deben combinarse, y son los únicos pasos que requieren mucho tiempo; en una imagen de 600 ppp, puede que tenga que tocar muchos millones de píxeles. El resto será rápido como un rayo. Me sorprendería mucho si no puedes clasificar múltiples imágenes por segundo, especialmente si sabes que no habrá bordes negros.

La única parte que requiere entrenamiento o experimento es el último paso. También es posible que tenga que juguetear con la cantidad de cubos en el histograma; si hay demasiados cubos, puede tener un mínimo local incorrecto.

¡Buena suerte, e infórmenos cómo se las arregla!

Consulte este algoritmo de detección de línea: http://homepages.inf.ed.ac.uk/rbf/HIPR2/linedet.htm . Además de una explicación detallada de cómo funciona el algoritmo, hay una demostración donde puedes usar tu propia imagen y ver los resultados. Probé dos imágenes: 1) un escaneo en blanco y negro de un recibo , 2) el lado posterior en blanco y negro, en "blanco" de ese mismo recibo . Todos los algoritmos de detección de bordes que probé encontraron bordes en la página "en blanco". Pero, este algoritmo de detección de línea fue el único algoritmo que encontró correctamente las líneas en la página principal y, sin embargo, no encontró nada en la página posterior "en blanco".

Puede hacer un ajuste ruidoso , es decir, desenfocar la imagen y realizar un ajuste automático (sin modificar realmente la imagen). Si el ancho o alto del resultado del ajuste está por debajo de un umbral (por ejemplo, 80 a 100 para una imagen de 600 ppp), entonces la página está vacía.

Una prueba de concepto usando el front-end de línea de comando de ImageMagick :

$ convert scan.png -shave 300x0 -virtual-pixel White -blur 0x15 -fuzz 15% / -trim info:

El comando anterior supone una imagen en blanco y negro (1 bit) DIN A4 de 600 ppp. También ignora un margen de 300 píxeles para que los artefactos como los agujeros de perforación no produzcan falsos negativos .