Segmenter des documents sans processus d'apprentissage en utilisant les algorithmes de détection des points d'intérêt
Isoler et redresser un objet ou un document précis constitue assez souvent un première étape dans l’analyse d’image. La lecture automatique de documents par le biais de la reconnaissance automatique de caractères (OCR) est grandement facilitée par une segmentation suivie d’un redressement automatique de la portion intéressante de l’image. Lorsque beaucoup de couples : (image, zone d’intérêt de l’image) sont disponibles, les réseaux de neurones d’Intelligence Artificielle fournissent la méthode la plus robuste actuellement pour segmenter toute sorte d’objets.
Cependant, dans les situations où l’on ne dispose que de très peu de données (jusqu’à un couple : image ; zone d’intérêt), mais que la portion intéressante de l’image est bien structurée, il est possible d’utiliser des algorithmes générant des points d’intérêt pour reconnaître une zone caractéristique, même si elle est déformée par rapport à l’original.
Points d’intérêt, intérêt des points d’intérêt
Les points d’intérêts d’une image sont des points reliés à des caractéristiques locales de l’image. Ces caractéristiques ont pour but de rendre compte de certaines propriétés de l’image et doivent idéalement être invariantes par translation, rotation, changement d’échelle, changement de photométrie. Le but principal de ces caractéristiques est de décrire et de transformer l’information visuelle en une ensemble de vecteurs dans un espace de représentation. Les points d’intérêt où points-clés sont déterminés en fonctions d’une certaine grandeur associée à chaque points de l’image. A chaque point-clé est ensuite associée une série de vecteurs (caractéristiques du point d’intérêt). La mise au point de points d’intérêt locaux élaborés ont commencé en 1981 grâce aux travaux de Hans Moravec. Ces points correspondent à des valeurs maximales locales de l’intensité de l’image en niveaux de gris. Hans Moravec travaillait sur la robotique (déplacement de robots grâce à des caméras) et est l’auteur de plusieurs livres sur l’avenir de l’intelligence artificielle . Un peu plus tard, Harris progresse dans la définition des points d’intérêts , en étudiant la matrice de corrélation du gradient de l’intensité. En 1999 David Lowe propose l’algorithme SIFT (scale-invariant feature transform) , il est ensuite amélioré et décrit en détail dans une publication en 2004 . A partir d’une image, l’algorithme donne une suite de points d’intérêt avec leur descripteur (vecteur associé à chaque points-clés).
Exemples d’applications des points d’intérêt :
- L’assemblage de panoramas
- Reconnaissance d’objets (présence où localisation)
- Localisation de robots en environnement inconnu
- Reconnaissance de mouvements humains
Un algorithme générateur de points d’intérêt insensibles aux changements d’échelle : SIFT
Recherche des points-clés
Détection préliminaire
On commence par définir les points-clés par les 3 paramètres (x,y,\sigma) dans l’espace des échelles. Les variables x et y sont les coordonnées cartésiennes dans l’image et \sigma est le facteur d’échelle. Un candidat point d’intérêt sera un point extremum du DoG (différence de gaussiènnes). On appelle gradient de facteur d’échelle \sigma noté L, le résultat de la convolution d’une image I par un filtre gaussien G de paramètre \sigma :
L(x,y,\sigma) = G(x,y,\sigma)*I(x,y)
avec
G(x,y,\sigma) = \frac{1}{2\pi\sigma^2}e^{-\frac{-(x^2+y^2)}{2\sigma^2}}
Pour une valeur de k fixée dans l’algorithme, on appelle différence des gaussiènnes la valeur :
D(x,y,\sigma)=L(x,y,k\sigma)-L(x,y,\sigma)
Un point éligible (x,y,\sigma) au titre de point-clé est un extremum du DoG D(x,y,\sigma) sur les proches voisins de l’espace des échelles. On recherche les extremum de l’ensemble :
\hskip -0.25 cm\big\{ D(x+\delta_x,y+\delta_y,s\sigma), \delta_x\in\{1,0,-1\}, \delta_y\in\{1,0,-1\}s\in\{k,1,k^{-1}\}\big\}
La convolution d’une image par le filtre gaussien produit une image floutée où tous les détails plus petits que le facteur d’échelle vont disparaître. Le DoG est en fait la différence entre deux images en niveau de gris. La différence entre deux images issues d’une même troisième mais lissés à deux échelles différentes par des gaussiènnes est une approximation du Laplacien de gaussien utilisée en analyse d’image pour l’analyse des contours. Même si pour la recherche des extremum d’un certain (x,y,\sigma_0), on se limite à quelques voisins, plusieurs niveaux de lissages gaussiens sont explorés. L’espace discrétisé des facteurs d’échelle est choisi en progression géométrique : \{\sigma_0,k\sigma_0,k^2\sigma_0\ldots \}. Cette progression permet de simplifier les calculs, car diviser la résolution par 2 revient à multiplier par 2 le facteur d’échelle. On peut remarquer qu’au maximum 2 points sur 27 sont des extremums et que le fait d’appliquer des changements d’échelle rend moins précise la localisation des points-clés et en conséquence cela diminue leur densité. Remarquons que si un point-clé apparait au centre d’une zone blanche uniforme, c’est qu’il est lié à un grand facteur d’échelle. Pour des calculs plus rapides, on peut approximer les filtres gaussiens par une simple moyenne pondérée des niveaux de gris des pixels voisins.
Visualisation de la différence des gaussiènnes. L’image de droite représente L(x,y,\sigma) et l’image de gauche L(x,y,k\sigma).
Localisation précise des points d’intérêt et élimination des points non pertinents
A cause des changements d’échelle lors de la détection préliminaire des points-clés, les coordonnées cartésiennes ne sont pas déterminées avec précision. La localisation précise se fait par interpolation en utilisant le développement de Taylor à l’ordre 2 de la différence de gaussiennes D. Pour augmenter la spécificité des points-clés, on va éliminer les points-clés de faible contraste et ceux situés sur des arêtes.
Orientation des points-clés
Pour assigner des orientations à un point-clé (x_0,y_0,\sigma_0), on étudie la direction et la norme des gradients dans un voisinage de (x_0,y_0). Ce voisinage est une fenêtre dont les cotés ont 1.5 fois la taille du facteur d’échelle \sigma_0. Un histogramme des orientations des gradients dans ce voisinage est réalisé avec 36 intervalles de 10°. La contribution de chaque points voisins est pondéré par la norme de son gradient. On va retenir comme orientations du point-clé que les orientations de gradient dont la norme est d’au moins 80% de la valeur maximale. On pourra donc avoir plusieurs points-clés (x_0,y_0,\sigma_0,\theta_i) à partir du point-clé (x_0,y_0,\sigma_0).
Pour chaque position voisine (x,y,\sigma_0) du point-clé (x_0,y_0,\sigma_0), on calcule les normes m(x,y) et orientations \theta(x,y) des gradiens par différences finies :
m(x,y) =\newline \sqrt{\big(L(x+1,y)-L(x-1,y)\big)^2+\big(L(x,y+1)-L(x,y-1)\big)^2}
\theta(x,y)=\tan^{-1}\bigg(\frac{L(x,y+1)-L(x,y-1)}{L(x+1,y)-L(x-1,y)}\bigg)
Descripteur des points-clés
Ces descripteurs s’inspirent d’un modèle proposé par Edelman, Intrator, et Poggio (1997). Celui ci s’inspire du comportement des neurones du cortex visuel primaire (V1). Pour chaque points-clés, on commence par modifier le système de coordonnées locales de manière à annuler la composante globale d’orientation. C’est cette dernière qui est surtout modifiée par des rotations. Ceci va permettre au vecteur descripteur d’être indépendant vis à vis des rotations. Pour chaque points-clé on considère un voisinage de 16 blocs de 4×4 autour des coordonnées (x,y). Pour chacun de ces 16 blocs, on calcule l’orientation et la norme des gradients dans chacun des sous blocs de ce bloc 4×4 (comme pour l’orientation générale). Les 16 orientations sont ensuite mises dans un histogramme à 8 graduations (360°/45°). On obtient 16 histogrammes avec 8 orientations possibles ce qui donne un vecteurs descripteurs à 128 dimensions.
Autres algorithmes plus récents
D’autres algorithmes du même type apparaissent : SURF ; ORB; BRISK ; KAZE (2012) et AKAZE (version accélérée de KAZE en 2016). Les algorithmes SIFT et SURF ont acquis une licence ne leur permettant plus d’être utilisés dans un projet professionnel hors du cadre de la recherche académique. Ces derniers ont été supprimés des versions récentes de la bibliothèque Open Source : OpenCV. Pour l’utilisation dans un cadre professionnel, il reste donc ORB, BRISK, KAZE et AKAZE tous disponibles dans les dernières versions de la bibliothèque OpenCV. Kaze diffère principalement de SIFT dans le sens où il utilise un filtrage non linéaire. AKAZE est une version plus rapide de KAZE. Les concepteurs de KAZE décrivent KAZE comme très concurrentiels. Dans notre étude, bien que n’ayant pas comparé cet algorithme avec SIFT et SURF (pour les raisons évoquées plus haut et la non disponibilité dans OPENCV), KAZE été le seul à priori à donner des résultats exploitables dans le cadre de nos travaux de segmentation de pièces d’identités. Bien que nettement plus rapide, AKAZE n’a pas donné le même niveau de performance en terme de segmentation de document de pièces d’identité.
Points clés et descripteurs de points clés avec python et OpenCV
La bibliothèque OpenCV pour Python permet une utilisation des algorithmes ORB, BRISK, AKAZE,KAZE. Les algorithmes SIFT et SURF ne font plus partie des version > 3.4.2.
Le nombre de points est variable selon les méthodes ainsi que les vecteurs du descripteur. Pour l’image suivante, on obtient les nombres de points-clefs et nombres de coordonnées des vecteurs des descripteurs suivants :
- SIFT : 128 dimensions, points-clés
- KAZE : 128 dimensions, points-clés
- ORB : 32 dimensions, points-clés
- BRISK : 64 dimensions, points-clés
- AKAZE : 61 dimensions, points-clés
- SURF(128D) : 128 dimensions, (nombre points non testé)
Dans apparait divers tests et descriptions des différents algorithme. On peut utiliser ces couples (points clefs, descripteurs) de différentes façons :
- Pour identifier un objet si un certain nombre de points clefs ont des descripteurs proches (au sens de la distance euclidienne entre vecteurs) des descripteurs de points clefs d’une image de référence de l’objet. Dans ce cas, seuls les descripteurs de points ont de l’importance.
- Pour rechercher une transformation géométrique entre les points du contour d’un objet dans une image de référence et les points du contour du même objet dans une autre image. Pour déterminer la transformation géométrique, n’importe quel couple de points en correspondances entre les deux images peut être exploité (il faut au minimum 4 couples de points).
Transformations affines, transformations projectives dans le plan
Transformation affine
En dimension 2, les transformations affines (rotations, transvections, symétries, changements d’échelle ) peuvent s’écrire uniquement à l’aide de matrice 2×2, mais pas les translations. En général on peut écrire :
\begin{pmatrix} x' \\ y' \end{pmatrix}=\begin{pmatrix} a & b \\ c & d \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}+\begin{pmatrix} a \\ b \end{pmatrix}
Pour pouvoir n’utiliser qu’un calcul matriciel, on peut exprimer la transformation en coordonnées homogènes :
\begin{pmatrix} x' \\ y' \\1\end{pmatrix}=\begin{pmatrix} a_{11} & a_{12}&a_{13}\\a_{21} & a_{22}&a_{23}\\a_{31} & a_{32}&a_{33} \end{pmatrix}\begin{pmatrix} x \\ y \\1\end{pmatrix}
Les transformations affines conservent les parallélogrammes, ont 6 degrés de liberté et peuvent se formuler à l’aide de matrices de la forme :
\begin{pmatrix} a_{11} & a_{12}&a_{13}\\a_{21} & a_{22}&a_{23}\\0 & 0&1 \end{pmatrix}
La donnée de 3 points de départ et de leurs 3 points cibles correspondants permet ainsi de définir les 6 constantes de la matrice de la transformation affine. Un point de coordonnée cartésienne (x,y) a des coordonnées homogènes (x,y,1).
Transformation projective, plan projectif
Ces coordonnées homogènes permettent aussi d’exprimer les transformations projectives (prise en compte de la perspective) qui opèrent sur un espace projectif (existence de points à l’infini). Dans le plan projectif deux ensembles de coordonnées (x,y,w) et (K.x,K.Y,K.w) avec K non nul représentent le même vecteur. Un point situé à l’infini est de la forme (x,y,0). Un exemple concret de point situé à l’infini est l’image de la limite d’une voie ferrée rectiligne. Une transformation projective en dimension 2 transforme une droite en une droite, possède 8 degrés de libertés et peut se formuler par :
\begin{pmatrix} x' \\ y' \\w'\end{pmatrix}=\begin{pmatrix} a_{11} & a_{12}&a_{13}\\a_{21} & a_{22}&a_{23}\\a_{31} & a_{32}&1 \end{pmatrix}\begin{pmatrix} x \\ y \\w\end{pmatrix}
Ainsi la données de 4 points de départ et des 4 points d’arrivé correspondant permet de définir les 8 coefficients de la matrice de transformation.
Reconnaissance d’une pièces d’identités dans une image, transformations projectives
Des pièces d’identités prises en photo ou scannées par des clients sont téléchargées sur un site. Le projet consiste à simplifier l’analyse de ces documents par des procédés d’intelligence artificielle. L’utilisation assez massive des smartphones pour prendre des clichés et les télécharger implique que le système automatique de reconnaissance, de traitement et de vérification des documents doit pouvoir segmenter dans un premier temps le document dans l’image pour ensuite le redresser par une transformation géométrique.
Les pièces d’identité sont rectangulaires en vision directe. Dans une prise de vue, cette région rectangulaire subie des translations, rotations, déformations projectives. D’après le paragraphe précédent, pour déterminer la matrice 3×3 de transformation projective, on a besoin de 4 points dans l’image de référence et des 4 points correspondant dans l’image à segmenter. Dans l’image de référence, il ne doit pas y avoir de structures spécifiques à un document particulier. On doit donc effacer tous les parties spécifiques de l’image et ne garder qu’un squelette du document comme préconisé dans .
Objectif : Trouver 4 points-clés dans l’image de référence correspondant à 4 points-clés de l’image à segmenter.
Méthodes : Calculer les distances entre les descripteurs de points clefs et classer les couples de points par ordre décroissant de leur distances respectives à l’aide de la fonction brute force : BFmatcher (cv2.BFMatcher()).
Du fait des imperfections des images, le fait de choisir les 4 couples de points les plus proches au sens de la distance euclidiene à peu de chance de donner la bonne matrice de transformation en écrivant :
En supposant que le choix des 4 couples de points soit bien fait, la matrice de transformation au dessus permet de transformer des points de l’image de référence dans l’image à analyser. En prenant les points extrême de l’image d’origine ((0,0),(0,largeur),(largeur,hauteur),(0,hauteur)) on obtient les 4 points délimitant le quadrilatère du document dans l’image à analyser. Ensuite ayant ces 4 points, il faut utiliser la matrice de la transformation inverse pour passer de ces 4 points aux 4 points extrêmes de l’image et obtenir le document redressé en entier.
Algorithme RANSAC
Il est bien meilleur de prendre beaucoup plus que 4 couples de points et d’essayer de choisir parmi tous ces points les 4 meilleurs autrement qu’en regardant seulement la distance euclidienne des vecteurs des descripteurs. Une première solution est d’utiliser l’algorithme RANSAC (RANdom SAmple Consensus). L’hypothèse de base est que les données sont constituées d’« inliers », des données qui représente l’image à segmenter et d’autres, des outliers, des données à rejeter. Le principe de cet algorithme est de choisir aléatoirement des points, de tester la qualité de la transformation liée au choix de ces points et de recommencer. La qualité de la transformation est liée à la capacité de la transformation à échanger correctement les autres couples de points. Cet algorithme va fonctionner correctement si la probabilité de tirer au hasard de points pertinent est suffisamment élevée. Cette méthode RANSAC est intégrée à la méthode findHomography de OpenCV.
Cette solution est améliorable en sélectionnant plus finement les couples de points à rentrer dans l’algorithme RANSAC avant de pouvoir déterminer la matrice de transformation.
Sélection des points-clés avant l’utilisation de l’algorithme RANSAC
Sur des images de (1600,2130) pixels, l’ordre de grandeur du nombre de couples de points-clés sélectionnés (issus de l’image et de l’ image de référence) par cv2.BFMatcher() est de 1000 à 1500 points. C’est beaucoup trop pour un bon fonctionnement de l’algorithme RANSAC. Le critère du ratio test introduit par D. Lowe pour SIFT permet de limiter le nombre de points à analyser par RANSAC en ne gardant que quelques dizaines de couples de points sur les milles initiaux.
Ratio test, constantes et choix de KAZE
Le créateur de l’algorithme SIFT, David Lowe, propose la technique du ratio test pour améliorer le choix de bons points d’intérêt . Etant donné un point d’intérêt de l’image de référence, on recherche par force brute les 2 points d’intérêt les plus proches dans l’image à analyser. Cette distance est toujours la distance entre les vecteurs du descripteur des points. On fixe ensuite un ratio entre les distance entre le plus proche voisin et le second plus proche voisin. Ce ratio est fixé est fixé à 0.75.
Kaze
Bien que proposée pour SIFT, cette technique du ratio test peut s’appliquer aux autres algorithmes générateur de points d’intérêt. Des tests sur les images de passeports et de nouveaux permis de conduire, ne donne cependant pas de résultats corrects avec les algorithmes ORB, BRISK et AKAZE. On remarque aussi que le nombre de points sélectionnées par le ratio test est aussi assez différents selon les méthodes employées. La méthode KAZE bien que plus couteuse en temps de calcul donne des résultats bien meilleurs que les autres algorithmes. Il est à noter par contre que l’algorithme KAZE apparait sensible aux changements d’échelles. Des normalisations de la taille de l’image se sont avérées indispensable au bon fonctionnement de cet algorithme.
Une autre amélioration expérimentale a été testée : L’utilisation du ratio test avec plusieurs constantes de ratio test. Des essais montrent que la qualité de la segmentation issue de la transformation géométrique est dépendante de cette constante. Bien que couteuse en temps de calcul, il est possible d’essayer successivement plusieurs segmentations en utilisant des constantes successives de ratio test. On peut s’arrêter à la première bonne segmentation en réalisant un test de bonne segmentation en cherchant à reconnaitre un champs du document à l’endroit où il doit être par ocr.
Pseudo code sans indentation :
Extension du ratio test et méthodes expérimentales employées pour la reconnaissance des pièces d’identité
Sur des images de passeports et nouveaux permis de conduire une extension du ratio test a été testée avec succès. La méthode consiste à considérer les 3 ou 4 points de l’image à analyser avec la description la plus similaire à un point d’intérêt de l’image de référence. Le ratio test originel utilise le principe qu’un point valide se distingue des autres points par une proximité relative avec le point de l’image de référence. Nous étendons ce principe en conservant le premier ratio test et en en fixant un second qui va marquer au contraire une certaine proximité entre le second et le troisième plus proche point. Cela dénote une certaine homogénéité des seconds et troisième voisins. Des extensions dans le même esprit ont été tentées avec les 4 plus proches voisins sans amélioration constatée.
Le passage de un à deux ratio test implique un nette amélioration. Comme pour le ratio test normal des valeurs différentes des ratio test sont appliquées. Dans ce dernier cas, toutes les images de passeports sans reflets excessifs sont correctement segmentées. Ce double ratio test est plus performant sur les images de passeport par rapport aux permis de conduire de dernière génération. Les couples de ratio test suivant sont utilisés : rt1=0.78; rt2=0.9;rt1=0.785; rt2=0.9; rt1=0.788,rt2=0.9; rt1=0.8,rt2=0.88.
Ce genre de travaux ne semble pas apparaître dans la littérature sur le sujet. Toutes ces améliorations sont à priori dû à une certaine défaillance des algorithmes vis à vis des transformations projectives, peut être moins conservatrices au niveau des descripteurs que les translations, rotations, transformations affine en général.
Conclusion, perspectives
Pour le point particulier de la segmentation, il existe des liens entre l’approche réseau de neurones et l’approche points d’intérêt comme la représentation de l’information visuelle par des vecteurs dans un ensemble de représentation. L’approche réseau de neurone par son aspect brute force est plus robuste en prenant en compte plus d’informations mais est moins explicative. On peut imaginer que pour la segmentions de documents structurés, ces deux techniques puissent être couplées, en utilisant la robustesse du réseau de neurone, puis la précision des méthodes à base de points d’intérêt. Le premier étage serait constitué d’un réseau de neurones et le second étages par une recherche des points clefs communs avec une image de référence. Il serait possible de faire un « redressement de l’image » (rotation, correction de perspective) pour faciliter l’OCR de l’image. On peut noter qu’il existe des travaux à base des réseaux de neurones qui segmentent et redressent des images. D’un point de vue purement pratique, ce type d’algorithmes présentent l’avantage de permettre une modification rapide en cas de changement du document à reconnaitre. Le manque de données étant dans ce cas sans solutions à court terme.
Bibliographie