Sélection des primitives 2D/3D pour la construction des graphes

Modélisation de l’histogramme du module des gradients

De nombreuse méthodes de détermination automatique du seuil de binarisation utilisent la forme de l’histogramme du module des gradients [Ku 2005] [Debashis 2010].
Dans le cas d’images ne présentant pas de textures très marquées on constate une forme bimodale de l’histogramme. Un mode existe pour les niveaux de gris faibles des gradients représentant des zones homogènes bruitées ou de petite zones texturées. Le second mode, à des niveaux de gris élevés, représente les discontinuités de luminance plus marquées, probablement les contours et le bruit « poivre et sel ».
Pour déterminer le seuil de binarisation, deux solutions sont envisageables, soit construire un modèle de l’histogramme et en déduire une valeur de séparation entre les deux modes à partir des paramètres du modèle, soit considérer la forme de l’histogramme comme un mélange de deux lois de probabilité, probabilité d’appartenance d’un niveau de gris à une classe de contour ou « non-contour ». Le principe est de construire une fonction coût séparant au mieux les 2 lois.
Debashis Sen et Sankar K. Pal [Debashis 2010] ont proposé un modèle composé de la somme d’une fonction de Rayleigh et d’une fonction gaussienne, et construisent une règle de séparation à partir des valeurs des coefficients de dissymétrie et d’aplatissement pour déterminer la région d’intérêt (ROI) dans l’histogramme afin d’y placer un seuil de binarisation. Les coefficients statistiques de dissymétrie et d’aplatissement donnés par les moments d’ordre 3 et 4 sont constants pour ces lois. Ce travail montre l’intérêt permanent pour la mise en œuvre de la détermination automatique de seuil de binarisation et l’intérêt de l’utilisation de deux modèles dans la modélisation de l’histogramme du module des gradients.
Afin d’obtenir une grande variété de formes, notamment présentant des dissymétries, nous proposons 1 de modéliser l’histogramme du module des gradients par la somme de 2 fonctions Gamma. Ces deux méthodes s’inscrivent dans la première catégorie suivant la classification donnée en figure 3.2.
Pour établir une comparaison pour l’évaluation des performances, nous avons testé deux méthodes s’inscrivant dans la 2eme catégorie : la méthode très connue d’Otsu améliorée par [Ku 2005] dont la fonction coût à maximiser est calculée à partir de la variance interclasse.
Le seuil Topt est la valeur du niveau de gris pour lequel la somme des deux entropies Hf et Hb pour le fond et les contours, respectivement, est maximale.
Les trois méthodes entropie [Kapur 1985], la nouvelle méthode d’Otsu [Ku 2005] et [Debashis 2010] considèrent le seuil de binarisation comme étant la valeur du niveau de gris séparant au mieux les deux classes, contours et non contours. Nous nous intéressons dans la section suivante à la méthode proposée qui s’appuie sur un principe de modélisation géométrique de l’histogramme du module des gradients.

Méthode initiale

La méthode initiale proposée [Simon 1994] utilise la forme constante de l’histogramme du module des gradients modélisée par l’expression (3.4), somme de deux fonctions de Gamma pour marquer l’asymétrie du mode, où x ∈ [0, 255] le niveau de gris, α, β, n et m des paramètres à identifier :

Amélioration proposée

L’amélioration proposée consiste à tenir compte du deuxième mode et d’estimer sa largeur. Si on applique la méthode de modélisation initiale sur l’histogramme de la première modélisation, le résultat n’est pas satisfaisant. La forme du mode étant plus bruitée, les paramètres estimés ne donnent pas un bon modèle, car la modélisation de la forme du second mode est écartée. Compte tenu de l’asymétrie du ce dernier, nous proposons de prendre un développement limité de la forme initiale, soit l’expression (3.12) pour privilégier une forme parabolique du second mode.
Nous considérons l’histogramme comme une densité de probabilité (probabilité d’apparition d’un niveau de gris par rapport à l’ensemble des pixels) ce qui implique une renormalisation, les paramètres a, b, c et λ seront calculés pour respecter : R 255 0 Hd(x) dx = 1.
Le triplet (a, b, c) contient les coefficients du polynôme de la forme parabolique.
Ils sont déterminés par approximation régressive aux moindres carrés. La figure 3.5 présente l’histogramme du module des gradients d’une image issue de la base BSDS300 et le modèle associé.
La détermination des coefficients du modèle parabolique est réalisée sur un intervalle de niveau de gris x ∈ [ε1, ε2]. La valeur ε1 est calculée comme la première valeur de la densité réduite (dans le sens des niveaux de gris croissant), valeur absolue de la différence entre l’histogramme expérimental complet et son modèle unimodal, supérieur à un seuil significatif, seuil fixé heuristiquement à 10−4 . La borne supérieure ε2 est obtenue par la même technique mais dans le sens des niveaux de gris décroissants.
Le seuil est calculé en prenant l’abscisse du point d’intersection des deux tangentes D1 et D2 (figure 3.6.a), respectivement au point d’inflexion du modèle Gamma, et au point d’abscisse la plus petite du modèle polynomial (figure 3.6.b).

Résultats et comparaison

Afin de comparer notre méthode par rapport aux méthodes citées précédemment, et classées dans la même catégorie, nous proposons de reprendre les indicateurs de performance proposés par le groupe de vision de l’Université de Berkeley. La binarisation est considérée comme une classification des pixels en deux classes. Celle des « contours » (Classe A) et celle des « non contours » (Classe A¯). Cela suppose qu’il existe une référence pour contrôler la classification. Cette référence a été produite à partir de propositions d’experts.
Ces indicateurs sont résumés par deux courbes. La courbe ROC qui caractérise la qualité de discrimination du processus de classification, et la courbe (P R) de la précision (P) en fonction du rappel (R). Enfin la mesure (F) ou F − score proposée par [Huijsmans 1993] et [Swets 1996] évalue l’efficacité de la méthode par rapport à l’exactitude (E), fraction des pixels bien classés. La mesure F exploite la précision et le rappel combiné par l’expression suivante.
Avant de procéder à l’évaluation de la méthode et la comparaison par rapport aux méthodes de même catégorie, le résultat de la détection des contours est illustré sur les figures 3.7 et 3.8 qui donnent des exemples de résultats. Dans la première ligne un extrait de la base de référence définie par des experts, la deuxième ligne les contours de référence, la troisième ligne les contours obtenus par notre méthode, la quatrième par la méthode d’entropie et la cinquième par la méthode Otsu.
L’étude des performances de la méthode est réalisée sur une centaine d’images tirées aléatoirement de la base BSDS300.
La figure 3.9 présente les courbes (P R) de ces méthodes placées dans le graphe des méthodes testées par le groupe vision de l’Université de Berkeley dans le travail de thèse de M.R Maire [Maire 2009], le F − score de notre méthode est précisé. Le point vert indique la mesure F des experts. Nous constatons que notre méthode, marquée en bleu continu, se situe au niveau de la méthode d’entropie et légèrement supérieure à celle d’Otsu avec un F − score honorable de 0.56.
La figure 3.10 présente la courbe ROC pour chaque méthode de calcul automatique du seuil de binarisation pour les quatre méthodes. La courbe ROC de notre méthode produit son maximum pour une valeur de spécification plus petite que la méthode d’Otsu, mais plus grande que la méthode initiale et d’entropie, et se situe bien au-dessus de cette dernière en sensibilité. La courbe ROC idéale vaut 1 pour toute spécificité.
La figure 3.11 présente l’évaluation de l’exactitude pour les quatre méthodes de binarisation. On retrouve en abcisse la méthode utilisée et en ordonnée la valeur moyenne de E et l’écart-type moyen du processus de calcul d’exactitude sur la même centaine d’images de la base BSDS300.
L’étude de l’exactitude confirme le bon classement de notre méthode par rapport aux autres méthodes de même catégorie (classification donnée en figure 3.2), avec une valeur moyenne autour de 68% et un écart-type moyen de 37%, alors que la méthode d’entropie et la méthode initiale ont leur valeur autour de 25% et 59% et un écart-type moyen de 39% et 43%, respectivement. Cette expérience montre la capacité de chaque méthode à bien détecter les pixels des contours en écartant les pixels des non-contours.
Pour l’ensemble des images nous évaluons aussi le temps moyen de calcul enregistré sur un calculateur Xeon 2.53 Ghz avec 4 Go de mémoire vive. Le résultat est présenté sur la figure 3.12 sous forme d’un diagramme à barres. L’axe des abscisses porte le nom de l’algorithme utilisé et l’axe des ordonnées le temps de calcul moyen du seuil exprimé en secondes. Ces résultats montrent que la méthode proposée est beaucoup plus rapide que celle d’Otsu et d’entropie.
Cette méthode répond aux besoins de disposer d’un détecteur de contours rapide.
La figure 3.13 donne les résultats obtenus par l’application des trois méthodes et la méthode proposée sur l’image de notre montage d’usinage. L’image des contours obtenue va être utilisée pour détecter et sélectionner les primitives 2D.

Sélection des cercles

Nous utilisons la transformée de Hough (TH) pour la détection des cercles. La transformée de Hough est une méthode classique pour la détection des formes spécifiques à partir de l’image des contours, elle tente d’accumuler des évidences sur l’existence d’uneforme particulière, e.g. circulaire, dans l’espace des paramètres décrivant cette forme.
Le choix de l’espace des paramètres est une étape importante dans la représentation de Hough. En effet, représenter un cercle dans l’espace cartésien r 2 = (x − a) 2 + (y − b) 2 peut sembler un choix judicieux, mais pour pouvoir traiter complètement l’ensemble des cercles possibles, a et b doivent varier entre ] − ∞, +∞[ ce qui conduit à une difficulté de quantification de l’espace des paramètres, e.g. une grande taille de la matrice d’accumulation. En général, cette étape est délicate, si la forme circulaire à détecter est affectée par le bruit, ce qui est souvent le cas en traitement d’image. Nous avons choisi une représentation plus adaptée et bornée. La forme circulaire est donc, caractérisée par le rayon r et l’angle θ dans le plan polaire. Ce changement de repère est calculé en utilisant les relations données par l’équation (3.14).

Sélection des droites

Les segments des droites donnent une information importante sur l’organisation topologique de l’image du montage d’usinage. La détection des segments de droites est un problème ancien en vision par ordinateur [Frei 1977] mais qui reste d’actualité [Grompone von Gioi 2010]. Certaines méthodes classiques utilisent l’information des contours pour détecter une forme rectiligne. Elles s’appuient sur la forme de la courbure de contour pour en extraire une forme droite [Deschenes 2004], mais elles sont gourmandes en temps de calcul.
Une méthode récente s’appuyant sur l’information de gradient, module et direction proposée par Rafael Grompone von Gioi et al.[Grompone von Gioi 2010] a été utilisée pour notre application. Cette méthode est basée sur la méthode de Burns et al.[Burns 1986] et une approche a contrario [Beveridge 1996] pour la validation d’un segment. Elle s’appuie sur l’information de la direction du gradient. En pratique, à partir de l’image de gradient, nous prenons un pixel et nous regardons dans un voisinage de 3×3 la présence d’un autre pixel dont la valeur du gradient est maximum avec une direction comparable à celle du pixel de référence, avec une certaine tolérance τ , permettant de définir une région des pixels connexes. Chaque région est approximée par un rectangle englobant la région. La taille du rectangle est choisie comme l’enveloppe convexe de la région. Le principe du rectangle caractérisant la région et le résultat de calcul des régions sur l’image du montage d’usinage sont illustrés sur la figure 3.16.