- Modélise la pose 3D et la courbure pour transformer la photo d’un document courbé en image plane, et formule le problème comme une optimisation alignant des points de référence du texte
- Suit une approche similaire à Leptonica et CTM : découper le texte en lignes, puis trouver une transformation de coordonnées pour que ces lignes paraissent parallèles et proches de l’horizontale
- Le modèle comprend un vecteur de rotation
r, un vecteur de translationt, des pentes de courbureα,β, ainsi que les décalagesx,ydes spans de texte, et minimise l’erreur de reprojection - Le pipeline enchaîne recadrage des limites de page, détection des contours de texte, assemblage des spans, échantillonnage des points de référence, génération des valeurs initiales, optimisation de Powell, puis remapping avec
cv2.remap - Dans les exemples d’exécution, les paramètres vont de 104 à 600, le temps total de 5,3 à 24,8 secondes, l’essentiel étant consacré à l’optimisation, ce qui laisse une marge d’amélioration via un autre solver ou un langage compilé
Résoudre les pages courbées comme un problème d’optimisation
- Le script existant qui transformait des photos manuscrites en PDF se limitait à
adaptiveThresholdet à l’assemblage de plusieurs images en PDF, mais sur des photos de documents d’archives, le gondolement de la page courbait fortement le texte - L’objectif est de créer un programme qui convertit automatiquement la photo d’une page courbée en image de document plane
- Le code est publié sur GitHub dans page_dewarp
Flux de base repris de Leptonica et CTM
- La correction de déformation des images de documents est un problème déjà connu, également implémenté dans Leptonica, la bibliothèque open source de traitement d’images de Dan Bloomberg
- Les références incluent un résumé des résultats du dewarping contest et un article sur la méthode gagnante, le Coordinate Transform Model, ou CTM
- Leptonica et CTM divisent tous deux le problème en deux étapes communes
- Séparer le texte ligne par ligne
- Trouver une déformation ou transformation de coordonnées pour que les lignes deviennent parallèles et horizontales
- Cette implémentation représente l’apparence de la page par plusieurs paramètres
r,t: vecteurs de rotation et de translation représentant l’orientation et la position 3D de la pageα,β: deux pentes qui déterminent la courbure de la surface de la pagey₁ ... yₙ: décalages verticaux denspans horizontaux sur la pagexᵢ: décalages horizontaux pour plusieurs points de référence dans chaque span
Surface 3D et erreur de reprojection
- La forme 3D de la page est représentée comme une surface obtenue en balayant une courbe le long de l’axe local
y - La coordonnée horizontale
xde la page est mappée vers un déplacement dans la directionzde la surface, et la section horizontale est modélisée par une spline cubique- Les deux extrémités de la spline sont fixées à 0
- La forme de la spline est déterminée uniquement par les pentes aux extrémités
α,β
- Une fois les paramètres de pose et de courbure définis, chaque coordonnée
(x, y)de la page est projetée vers une position donnée dans le plan image - On détecte les keypoints des spans de texte horizontaux dans la photo d’origine, puis, à partir d’une estimation initiale, on cherche les paramètres qui minimisent l’erreur de reprojection des keypoints
- Avant l’optimisation, en supposant l’absence de courbure, les points reprojetés se trouvent sur une ligne droite ; après optimisation, les points projetés par le modèle se superposent presque aux keypoints réellement détectés
Pipeline de traitement d’image
-
Recadrage des limites de page
- Au lieu d’utiliser toute l’image, seule la zone centrale est recadrée avec une marge fixe afin d’éviter les régions inutiles sur les bords
- Aucune détection intelligente des limites de page n’est utilisée
-
Détection des contours de texte
- Un seuillage adaptatif initial est appliqué
- Une dilatation morphologique est effectuée avec une boîte horizontale pour relier les pixels de masque adjacents horizontalement
- Une érosion est effectuée avec une boîte verticale pour supprimer le bruit d’un pixel de haut
- Après une analyse des composantes connexes, les blobs trop hauts ou trop épais sont filtrés
- Les contours de texte restants sont approximés par le segment le mieux ajusté via PCA
-
Complément à la détection des lignes horizontales
- Certains inputs étant sous forme de tableaux avec beaucoup de texte vertical, si la quantité de texte horizontal détectée est insuffisante, la détection de lignes horizontales ou de règles est également tentée
Construction des spans de texte et échantillonnage des points de référence
- Pour regrouper les contours détectés dans un même span horizontal, des arêtes candidates sont créées pour toutes les paires de contours, puis un coût est calculé
- Si deux contours se chevauchent fortement dans le sens de leur longueur, sont trop éloignés ou présentent un écart d’angle important, leur coût est fixé à l’infini
- Le coût d’une arête valide est calculé comme une combinaison linéaire de la distance et de la variation d’angle
- Après tri des arêtes par coût, une méthode gloutonne en temps quadratique relie deux contours uniquement si aucun des deux n’est déjà connecté de ce côté
- Comme la majeure partie du temps d’exécution est consacrée à l’optimisation, la complexité quadratique de cette étape ne posait pas de problème majeur
- Une fois les spans créés, ceux qui sont trop petits pour aider à déterminer le modèle sont supprimés
- Le modèle paramétrique nécessitant des points de référence discrets, un keypoint est choisi environ tous les 20 pixels de contour de texte
Génération des valeurs initiales et optimisation de Powell
- La direction moyenne de tous les spans est estimée par PCA
- À l’aide de la composante principale issue de la PCA, les coordonnées initiales
x,yet la pose d’une page plane sans courbure sont définies analytiquement - La reprojection échantillonne la spline cubique pour obtenir les décalages
zdes points objet, puis les projette dans le plan image avec des fonctions OpenCVcv2.solvePnPcv2.projectPoints
- La minimisation de l’erreur de reprojection utilise
scipy.optimize.minimizeet le solver'Powell'- Il est utilisé comme outil d’optimisation boîte noire sans dérivées
- Le problème lui-même relève des moindres carrés non linéaires
- D’autres solvers ou des solvers spécialisés de moindres carrés non linéaires n’ont pas été beaucoup expérimentés
- Pratiquement 100 % du temps d’exécution du programme est consacré à cette étape d’optimisation
Remapping et génération de l’image de sortie
- Une fois l’optimisation terminée, seuls
r,t,α,βsont isolés pour créer la transformation de coordonnées - Le dewarp effectif est obtenu en projetant un dense mesh de points 3D de la page avec
cv2.projectPoints, puis en transmettant ces coordonnées image àcv2.remap - Le résultat final est enregistré sous forme de PNG bilevel avec
cv2.adaptiveThresholdet Pillow
Résultats d’exemple et temps d’exécution
- Le dépôt GitHub inclut plusieurs images d’exemple
- Les statistiques ci-dessous correspondent à une exécution sur un seul MacBook Pro 2012
| Entrée | Spans | Keypoints | Paramètres | Temps d’optimisation | Temps 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 |
- Même le plus petit modèle compte 104 paramètres, et le plus grand 600, ce qui n’en fait pas un petit problème d’optimisation
- La vitesse d’optimisation pourrait être améliorée en essayant d’autres méthodes ou en utilisant un langage compilé
Limites restantes
- L’approche globale consiste à lire un peu de contexte, puis à formuler tout le problème comme la sortie d’un processus d’optimisation
- Elle rappelle les deformable part models et les active appearance models, sans être aussi sophistiquée qu’eux
- Leptonica et CTM tentent de modéliser et de corriger non seulement la distorsion verticale, mais aussi la distorsion horizontale
- Cette implémentation ne va pas jusqu’à corriger la distorsion horizontale
- Comme la spline cubique n’est pas paramétrée par longueur d’arc, le texte est légèrement comprimé dans les zones où la pente de la spline est forte
- Le projet étant surtout un proof-of-concept, ce point n’a pas été poussé plus loin
- Le code final est publié dans le dépôt GitHub, et les commentaires détaillés restent encore insuffisants
1 commentaires
Commentaires sur Hacker News
Il faut être prudent quand on applique un seuillage fort à la sortie, comme l’a fait l’auteur
Ça fonctionne assez bien sur les pages de texte brut, mais j’ai vu plusieurs pages de Google Books où des illustrations ou de petites notes de bas de page étaient dégradées au point de devenir illisibles
Si les scans Google Books sont la seule source disponible, on se retrouve complètement bloqué
Une fois ces points trouvés, on devrait pouvoir appliquer ces paramètres à l’image d’origine
On est en 2024, et je trouve frustrant que ce genre de fonction ne soit toujours pas intégré par défaut dans les apps de scan de documents
Le fait d’avoir un modèle de déformation de page de faible dimension à optimiser semble être la clé de cette approche
C’est exactement le genre de problème à la bonne échelle pour YC. Quelques semaines jusqu’au lancement, et probablement quelques centaines de milliers de dollars de coût de lancement
L’app mobile d’Apple demande beaucoup trop d’ajustements manuels, et Microsoft Office Lens / Microsoft Lens reçoit des avis du genre « les bords finissent par partir complètement en vrille et le résultat est horrible »
Il semble donc y avoir un marché pour un produit qui fonctionne simplement bien, avec une sortie possible par revente aux acquéreurs habituels
Ils ont dû trouver ça trop complexe et trop mathématique, et juger qu’à la place, construire un modèle qui analyse l’activité des utilisateurs sur les réseaux sociaux pour affiner le timing des notifications améliorerait davantage les métriques utilisateur
En cherchant à réduire le churn, les décideurs ont donc pris une décision strictement guidée par les données
Après que John Warnock a quitté son poste de CEO d’Adobe, il s’est davantage impliqué dans Octavo, une entreprise qui préservait des livres historiques rares
L’un des problèmes auxquels ils étaient confrontés était de redresser la courbure de pages scannées qu’on ne pouvait pas aplatir en les pressant
https://en.m.wikipedia.org/wiki/Rare_Book_Room
L’article était excellent
On pourrait même s’en servir en entreprise comme exemple de documentation efficace d’un projet technique et de ses décisions
À l’université, en essayant de créer une app pour scanner des notes codées par couleur, je suis tombé sur un autre problème
Les couleurs dérivaient du haut vers le bas de la page, ce qui rendait difficile de distinguer de manière fiable le stylo bleu du stylo vert
Il faudra que je m’y replonge un jour
Cela supprime en pratique les variations de couleur/luminosité à basse fréquence
On l’utilise souvent pour enlever les ombres sur des photos de papier, et ça devrait fonctionner tout aussi bien pour les gradients de couleur
Ça a l’air largement correct
Cela dit, le modèle de déformation me paraît un peu trop global
Certaines déformations plus complexes du papier ne sont pas capturées par le modèle, et elles restent visibles dans le résultat final sous forme de distorsions résiduelles
J’obtiens une erreur pendant l’installation :
ERROR: Could not find a version that satisfies the requirement cv2>=3.0 (from versions: none)ERROR: No matching distribution found for cv2>=3.0J’ai ouvert une issue GitHub
Vraiment très chouette
J’aimerais bien avoir une bonne app de scan de documents utilisable sur mobile, avec correction de distorsion, seuillage et génération de PDF qui fonctionnent bien
Pour l’instant, je suis coincé avec Adobe Scan, qui donne à peu près les meilleurs résultats, même si sa correction de distorsion reste assez médiocre
Lecture vraiment intéressante
On dirait un article que j’ai manqué en 2016, et j’aime la façon dont il montre tout le cheminement : « il y avait ce problème, on a appliqué une technique intelligente, et on a obtenu une solution qui fonctionne bien »
Personnellement, je ne pense pas avoir besoin de ça un jour, mais c’est un excellent exemple de traitement d’un problème de la bonne manière, avec des compromis raisonnables selon ce que la sortie et les attentes permettent
L’article est aussi bien écrit et bien expliqué
Si l’on n’a pas besoin de représenter visuellement le livre et qu’on veut seulement faire de l’OCR, on peut probablement sauter cette étape
Google a résolu ce problème il y a plus de dix ans : https://hardware.slashdot.org/story/09/05/15/1834246/how-goo...
Si le manuscrit a vraiment de la valeur, une correction de distorsion sans contact est aussi possible par tomographie à rayons X : https://scrollprize.org/tutorial1
Du côté de Google, ils utilisaient du matériel, et la mention de la tomographie à rayons X fait très ChatGPT
Cela dit, la méthode de cet article est élégante et simple pour 2016