Segmenter des documents sans processus d'apprentissage en utilisant les algorithmes de détection des points d'intérêt

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