Tecnología de corrección de distorsión de páginas

 (mzucker.github.io)
2 puntos por GN⁺ 2024-05-14 | 1 comentarios | Compartir por WhatsApp
  • Para convertir una foto de un documento curvado en una imagen plana, modela la pose 3D y la curvatura y lo resuelve como un problema de optimización que alinea puntos de referencia del texto
  • Sigue un flujo similar al de Leptonica y CTM: divide el texto por líneas y luego encuentra una transformación de coordenadas para que las líneas se vean paralelas y casi horizontales
  • El modelo incluye el vector de rotación r, el vector de traslación t, las pendientes de curvatura α, β, y los offsets x, y de los spans de texto, minimizando el error de reproyección
  • El pipeline continúa con recorte de bordes de página, detección de contornos de texto, ensamblado de spans, muestreo de puntos de referencia, generación de valores iniciales, optimización con Powell y remapeo con cv2.remap
  • En la ejecución de ejemplo, los parámetros iban de 104 a 600, el tiempo total fue de 5.3 a 24.8 segundos, y la mayor parte se usó en la optimización, por lo que todavía hay margen de mejora con otros solvers o lenguajes compilados

Resolver una página curvada como un problema de optimización

  • Un script previo para convertir fotos manuscritas a PDF apenas llegaba a usar adaptiveThreshold y unir varias imágenes en un PDF, pero en fotos de documentos archivados el enrollamiento de la página hacía que el texto se curvara mucho
  • El objetivo es crear un programa que convierta automáticamente una foto de una página curvada en una imagen de documento plana
  • El código está publicado en GitHub en page_dewarp

Flujo básico tomado de Leptonica y CTM

  • La corrección de distorsión en imágenes de documentos es un problema ya conocido, y también está implementado en la librería open source de procesamiento de imágenes Leptonica de Dan Bloomberg
  • Entre los materiales de referencia están el resumen de los resultados del dewarping contest y el paper sobre el método ganador, Coordinate Transform Model o CTM
  • Leptonica y CTM dividen el problema en dos etapas en común
    • Separan el texto por líneas
    • Buscan una distorsión o transformación de coordenadas para que las líneas queden paralelas y horizontales
  • Esta implementación representa la forma de la página con varios parámetros
    • r, t: vector de rotación y vector de traslación que representan la orientación y posición 3D de la página
    • α, β: dos pendientes que determinan la curvatura de la superficie de la página
    • y₁ ... yₙ: offsets verticales de n spans horizontales sobre la página
    • xᵢ: offsets horizontales para varios puntos de referencia dentro de cada span

Superficie 3D y error de reproyección

  • La forma 3D de la página se expresa como una superficie generada al barrer una curva a lo largo del eje local y
  • La coordenada horizontal x de la página se mapea al desplazamiento en dirección z de la superficie, y la sección horizontal se modela con un spline cúbico
    • Los extremos del spline se fijan en 0
    • La forma del spline queda determinada solo por las pendientes de los extremos α, β
  • Una vez definidos los parámetros de pose y curvatura, cada coordenada (x, y) de la página se proyecta a una posición específica en el plano de la imagen
  • Se buscan keypoints en los spans horizontales de texto de la foto original, y a partir de una estimación inicial se buscan parámetros que minimicen el error de reproyección de esos keypoints
  • Antes de la optimización se asume que no hay curvatura, por lo que los puntos reproyectados quedan en línea recta; después de optimizar, los puntos proyectados por el modelo casi coinciden con los keypoints detectados reales

Pipeline de procesamiento de imagen

  • Recorte de bordes de la página

    • En vez de usar toda la imagen, solo se recorta la zona central con un margen fijo para evitar regiones innecesarias de los bordes
    • No se usa detección inteligente del borde de la página

  • Detección de contornos de texto

    • Se aplica un adaptive threshold inicial
    • Se realiza morphological dilation) con una caja horizontal para conectar píxeles de máscara adyacentes en dirección horizontal
    • Se realiza erosion) con una caja vertical para eliminar ruido de un píxel de alto
    • Después de connected component analysis, se filtran blobs demasiado altos o gruesos
    • Los contornos de texto restantes se aproximan con el segmento de línea que mejor ajusta mediante PCA

  • Refuerzo de la detección de líneas horizontales

    • Como algunas entradas eran tablas con mucho texto vertical, si no se detectaba suficiente texto horizontal también se intentaba detectar líneas horizontales o rules

Construcción de spans de texto y muestreo de puntos de referencia

  • Para agrupar los contornos detectados en el mismo span horizontal, se crean aristas candidatas para todos los pares de contornos y se calcula su costo
  • Si dos contornos se solapan mucho en dirección longitudinal, están demasiado lejos o difieren mucho en ángulo, se asigna un costo infinito
  • El costo de una arista válida se calcula como una combinación lineal de distancia y cambio de ángulo
  • Tras ordenar las aristas por costo, se usa un método codicioso de tiempo cuadrático que solo conecta dos contornos cuando ninguno de los dos ha sido enlazado todavía
    • Como la mayor parte del tiempo de ejecución se va en la optimización, la complejidad cuadrática de esta etapa no resultó un problema importante
  • Una vez formados los spans, se eliminan los que son demasiado pequeños como para ayudar a determinar el modelo
  • Como el modelo de parámetros necesita puntos de referencia discretos, se elige un keypoint aproximadamente cada 20 píxeles de contorno de texto

Generación de valores iniciales y optimización con Powell

  • La dirección promedio de todos los spans se estima con PCA
  • Usando la componente principal del resultado de PCA, se establecen analíticamente las coordenadas iniciales x, y y la pose de una página plana sin curvatura
  • La reproyección obtiene el offset z de los puntos del objeto muestreando el spline cúbico y luego proyectándolos al plano de la imagen con funciones de OpenCV
    • cv2.solvePnP
    • cv2.projectPoints
  • Para minimizar el error de reproyección se usa scipy.optimize.minimize con el solver 'Powell'
    • Se usa como una herramienta de optimización sin derivadas de tipo caja negra
    • El problema en sí corresponde a mínimos cuadrados no lineales
    • No se experimentó mucho con otros solvers ni con solvers especializados de mínimos cuadrados no lineales
  • Casi el 100% del tiempo de ejecución del programa se consume en esta etapa de optimización

Remapeo y generación de la imagen de salida

  • Una vez terminada la optimización, se separan r, t, α, β para construir una transformación de coordenadas
  • El dewarp real se obtiene proyectando una malla densa de puntos 3D de la página con cv2.projectPoints y pasando esas coordenadas de imagen a cv2.remap
  • El resultado final se guarda como PNG binario usando cv2.adaptiveThreshold y Pillow

Resultados de ejemplo y tiempos de ejecución

  • El repositorio de GitHub incluye varias example images
  • Las estadísticas en una sola MacBook Pro de 2012 son las siguientes
Entrada Spans Keypoints Parámetros Tiempo de optimización Tiempo total
boston_cooking_a.jpg 38 554 600 23.3 s 24.8 s
boston_cooking_b.jpg 38 475 521 18.0 s 18.8 s
linguistics_thesis_a.jpg 20 161 189 5.1 s 6.1 s
linguistics_thesis_b.jpg 7 89 104 4.2 s 5.3 s
  • Incluso el modelo más pequeño tiene 104 parámetros, y el más grande 600, así que no es un problema de optimización pequeño
  • La velocidad de optimización podría mejorar probando otros métodos o usando un lenguaje compilado

Limitaciones pendientes

  • Todo el enfoque surge de leer algo de conocimiento previo y formular el problema completo como la salida de un proceso de optimización
  • Este enfoque recuerda a deformable part models y active appearance models, aunque no es tan sofisticado como esos dos
  • Leptonica y CTM intentan modelar y corregir no solo la distorsión vertical, sino también la distorsión horizontal
  • Esta implementación no llega a cubrir la corrección de distorsión horizontal
    • Como el spline cúbico no está parametrizado por arc-length, en regiones donde la pendiente del spline es grande el texto se comprime un poco
    • Como el proyecto era principalmente una prueba de concepto, no se avanzó más con este problema
  • El código final está publicado en el repositorio de GitHub, aunque todavía no tiene un refuerzo suficiente de comentarios detallados

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-05-14
Opiniones en Hacker News

  • Hay que tener cuidado al aplicar un umbral fuerte a la salida, como hizo el autor.
    Detecta bastante bien las páginas de texto normal, pero vi varias páginas de Google Books donde las ilustraciones o las notas al pie pequeñas quedaban tan dañadas que se volvían ilegibles.
    Si el escaneo de Google Books es la única fuente, quedas completamente bloqueado.

    • ¿El umbral no sirve para encontrar puntos de referencia con los cuales elegir los parámetros de corrección de distorsión?
      Una vez encontrados esos puntos, parece que esos parámetros podrían aplicarse a la imagen original.

  • Es frustrante que, estando en 2024, las apps de escaneo de documentos todavía no traigan esta función integrada por defecto.

    • En la escuela usamos GeniusScan y tiene esta función: https://blog.thegrizzlylabs.com/2024/03/genius-scan-7.16.htm...
    • Es muy buena.
      Parece que la clave para que este enfoque funcione bien es tener un modelo de deformación de página de baja dimensión para optimizar.
      Este es justo el tipo de problema ideal para YC. Unas semanas hasta salir al mercado y un costo de lanzamiento de unos cientos de miles de dólares, diría.
      La app de teléfono de Apple requiere demasiados ajustes manuales, y Microsoft Office Lens / Microsoft Lens tiene reseñas del tipo “los bordes terminan volviéndose locos y se ve horrible”.
      Así que hay mercado para un producto que simplemente funcione bien, y también parece viable una salida vendiéndolo a los compradores habituales.
    • Me parece que Google Drive antes hacía esto correctamente, pero en los últimos años se volvió mucho peor.
    • Supongo que producto habrá considerado que el riesgo técnico no valía la pena.
      Probablemente les pareció demasiado complejo y matemático, y en cambio decidieron que construir un modelo que revisara la actividad del usuario en redes sociales para afinar mejor el momento de las notificaciones mejoraría más las métricas de usuario.
      En su intento por reducir la tasa de abandono, quienes toman decisiones habrán decidido de forma estrictamente basada en datos.
    • vflat es buena para esto.

  • Después de que John Warnock dejó el cargo de CEO de Adobe, se involucró más con Octavo, una empresa dedicada a preservar libros históricos raros.
    Uno de los desafíos que enfrentaban era enderezar la curvatura de páginas escaneadas que no se podían presionar para dejarlas planas.
    https://en.m.wikipedia.org/wiki/Rare_Book_Room

  • El artículo fue excelente.
    También podría servir como referencia en una empresa como ejemplo de cómo documentar eficazmente un proyecto técnico y sus decisiones.

  • En la universidad intenté crear una app para escanear apuntes diferenciados por color, pero me encontré con otro problema.
    Los colores se alteraban de arriba hacia abajo en la página, lo que dificultaba distinguir de forma confiable entre pluma azul y pluma verde.
    Algún día debería volver a revisarlo.

    • Si asumes que el fondo blanco se altera de la misma manera, un buen truco es copiar la imagen, aplicarle un desenfoque muy grande y luego dividir la imagen original por esa versión desenfocada.
      Así, las variaciones de color/brillo de baja frecuencia prácticamente se eliminan.
      Se usa mucho para quitar sombras al fotografiar papel, y parece que funcionaría igual con gradientes de color.

  • Se ve suficientemente bien.
    Aunque el modelo de deformación parece un poco demasiado global.
    Algunas deformaciones más complejas del papel no quedan capturadas por el modelo, y se ven como distorsiones residuales en el resultado final.

  • Me da un error durante la instalación:
    ERROR: Could not find a version that satisfies the requirement cv2>=3.0 (from versions: none)
    ERROR: No matching distribution found for cv2>=3.0
    Abrí un issue en GitHub.

  • Muy genial.
    Me gustaría que hubiera una buena app de escaneo de documentos para móviles. Una que haga bien la corrección de distorsión, el umbralizado y la generación de PDF.
    Por ahora estoy atado a Adobe Scan, que es la que me da los resultados menos malos, aunque su corrección de distorsión sigue siendo bastante floja.

    • Escuché que Microsoft Lens es buena, pero cuando la abro en mi teléfono simplemente se congela.

  • Fue realmente interesante de leer.
    Parece un artículo que me perdí en 2016, y me gustó que muestra bien todo el recorrido: “existía este problema, se aplicaron técnicas inteligentes y se obtuvo una solución que funciona bien”.
    Personalmente no creo que vaya a necesitar algo así, pero es un gran ejemplo de cómo abordar un problema de buena manera y hacer compromisos razonables dentro de lo que permiten la salida y las expectativas.
    El artículo también está bien escrito y bien explicado.

  • Si no necesitas mostrar el libro visualmente y solo quieres hacer OCR, probablemente puedas saltarte este paso.
    Google resolvió este problema hace más de 10 años: https://hardware.slashdot.org/story/09/05/15/1834246/how-goo...
    Si el manuscrito realmente es valioso, también es posible hacer corrección de distorsión sin contacto mediante tomografía de rayos X: https://scrollprize.org/tutorial1

    • Entonces bastaría con encontrar software usable y recomendarlo.
      Lo de Google usaba hardware, y lo de la tomografía de rayos X suena mucho a ChatGPT.
      Aun así, el enfoque de este artículo se ve bien y simple para 2016.