ESTIMATION AUTOMATIQUE DE POSE PAR APPARIEMENT DE GRAPHES

Différents indices peuvent être exploités à partir de l’image pour établir une mise en correspondance entre deux ensembles de points extraits de l’image. Cela nécessite une représentation significative des données. Nous nous intéressons dans cette section à l’algorithme proposé pour l’appariement entre le graphe (G) issu de l’image réelle du montage d’usinage, appelé graphe réel, et le graphe (H ) issu de l’image théorique, appelé graphe théorique.

Certaines notions sont aussi importantes à prendre en compte dans la mise en cor-respondance. L’unicité, est un critère important, car les nœuds appariés vont servir pour le calcul de pose et le recalage du modèle CAO sur l’image. Ils ne peuvent donc être appariés qu’une seule fois. Néanmoins, les difficultés de l’extraction et la sélection de ces primitives, et l’incomplétude des ensembles de ces derniers pour la construction des graphes, i.e. fausse détection, etc. due aux performances des algorithmes de dé-tection et sélection des primitives, ainsi que les conditions photométrique de la scène, nécessite de prendre en compte ce cas de figure dans la mise en correspondance. De plus, l’ensemble des primitives sélectionnées peut être différent pour une même configu-ration, cas du montage conforme donné par la figure 4.6, ce qui entraîne une contrainte supplémentaire dans le processus de la mise en correspondance. Par exemple, la bride présentant un trou au milieu peut déclencher une détection du cercle autour de ce trou, alarmes de type faux positif ou faux négatifs, ce qui n’est pas le cas dans le modèle CAO, car la surface supérieure de la bride est représentée par une surface pleine, ca-chant tout détail intérieur. Par conséquence, même si le montage réalisé est conforme au modèle CAO, les graphes construits pourraient ne pas être isomorphe. Un exemple est donné sur la figure 4.8. Les colonnes (a-b) présentent, successivement, une bride réelle et sa définition numérique donnée en CAO. Les colonnes (c-d) illustrent, succes-sivement, le résultat de la détection de cercles à l’intérieur de la bride pour les deux cas, e.g. réel et théorique.

Figure 4.8 – L’impact de « l’infidélité » du modèle CAO à la réalité dans la conception du mon-tage d’usinage, (a) image de la bride réelle, (b) modèle numérique de la bride correspondante à (a), (c) contours sur la zone de la bride sur l’image réelle du montage d’usinage, (d) contours sur la zone de la bride dans l’image théorique.

De façon générale, nous proposons que l’ensemble des appariements retenus vérifie deux propriétés :

• Premièrement, les deux nœuds appariés doivent disposer de caractéristiques si-milaires, ressemblance mesurée sur la nature des nœuds. Cette information est donnée par les arêtes de partitionnement.

• Deuxièmement, l’ensemble des appariements doit respecter la relation géomé-trique entre les nœuds. Cette information est portée par la fonction de ressem-blance (S) que nous présenterons ultérieurement.

Par conséquence, l’algorithme proposé se déroule en deux étapes :

• La première étape consiste à réaliser des coupures sur les graphes à partir de l’information sur la nature de nœuds. Ce point est développé dans la section 4.4.1.

• La mise en correspondance est effectuée alors sur les plus grands sous-graphes, in-dicé « gsg », en tenant compte de la relation géométrique Φ entre les deux graphes. La section 4.4.2 en présente le détail.

Considérons un graphe G = (v, D, p) calculé à partir de l’image réelle (de même pour l’image théorique H  =  (w, E, q)). Le vecteur v = {vi, ∀i  ∈  I } (w = {wj , ∀j  ∈  J } pour le graphe théorique) représente les indicateurs des nœuds, où I = 1 |v| (J = 1 |w| pour le graphe théorique). Le vecteur d’étique-tages p = {p = (xi, yi, λi), ∀i ∈ I } (pour le graphe de l’image théorique q = {q = (xj , yj , λj ), ∀j ∈ J }) représente les coordonnées spatiales pour chaque nœud et l’étiquette associée, tel que pour un nœud représentant un centre de cercle, λi (λj pour H) vaut 0, et pour un nœud représentant une intersection des droites, λi (λj pour H) vaut 1. La matrice d’adjacence D (E pour le graphe H) contenant l’information de proximité, l’indice de voisinage entre les paires des nœuds (a,b) est donné pour Dab (de même pour Eab) par : Dab =1ssi va  et vbsont voisins(4.1) 0ailleurs

Avant de procéder au calcul des sous-graphes, rappelons que l’algorithme proposé normalise les deux graphes. La normalisation est une étape importante pour l’apparie-ment. En effet, la projection opérée pour obtenir l’image théorique, section 3.4.1, n’est pas dans la dimension réelle de la scène car la pose n’est pas encore connue. Il faut se mettre dans une situation unidimensionnelle comparable. Le but est de s’affranchir de cette différence en normalisant les deux graphes, selon l’équation (4.2), pour les ramener dans le même espace de variation [a, b], e.g. pour le graphe G (de même pour le graphe H).

Avec X et Y les vecteurs des coordonnées xi et yi respectivement. La nature du nœud doit être oubliée pour cette normalisation. Ce qui impose un premier traitement.

Ce premier traitement consiste à réaliser des coupures de graphe pour séparer le graphe des cercles et le graphe de l’intersection des droites. Les coupures sont obtenues par une analyse de la nature des arêtes, donnée par le vecteurs d’étiquetages des noeuds, (p) pour le graphe (G) et (q) pour le graphe (H ), et effectuée sur les arêtes entre un cercle et une intersection des droites. Ces arêtes sont appelées arêtes de séparation, Cut edge. La figure 4.9 montre le principe du critère de partitionnement de graphe et l’algorithme associé.

Figure 4.9 – Calcul de la coupe par analyse de la nature d’arêtes : Critère de partitionnement.
Cette coupure permet de réorganiser les deux jeux de données (primitives) et sim-plifier l’appariement sur les plus grand sous-graphes, tout en conservant les caractéris-tiques structurelle de la scène, ce qui conduit à une optimisation du temps de calcul. La figure 4.10 montre le résultat de l’application de ce critère de partitionnement sur des images de différentes configurations réalisées du montage d’usinage. Les centres des cercles sont représentés par des nœuds bleus et les arêtes bleues représentent la relation de voisinage entre deux primitives circulaires. De même pour les intersections des droites, avec la couleur rouge. Les lignes pointillées noires, illustrent les arêtes de séparations, reliant une primitive circulaire avec une primitive rectiligne, e.g. intersec-tion des droites. Dans le cas de notre exemple « fil rouge » de la plaque Norelem c , les primitives circulaires présentent une information riche de la topologie de la scène, sous graphe bleu, noté Gbgsg vis-à-vis des intersections de droites, sous graphe rouge, noté Grgsg .

Les coupures obtenues par séparation des nœuds produisent des sous graphes simi-laires au sens du critère de la nature des nœuds. Notre objectif, maintenant, consiste à déterminer la fonction objectif/coût permettant de maximiser/minimiser le critère de ressemblance/différence entre les graphes. Ce critère de ressemblance (S) est donné par l’équation suivante :  S = argmax {min F (G|H, Φ)}

Avec, Φ la relation géométrique permettant d’assurer un maximum de nœuds ap-pariés, N le nombre des nœuds appariés.

La méthode proposée doit calculer l’appariement quelle que soit la configura-tion réalisée du montage d’usinage, même si cette dernière est totalement différente

La recherche de la relation géométrique optimale ΦOptq, avec q le nombre des confi-gurations possibles du graphe (Ggsg ) centré sur Pi, est effectuée selon l’équation (4.5), et la maximisation de la relation (4.3) revient à minimiser cette dernière :

(wj1, wj2) représente les nœuds exprimant cette distance. Deux conclusions peuvent être tirées de cette condition : de référence (wj1, wj2) dans le graphe (H) et donnée du modèle numérique du montage d’usinage attendu, car la détection de l’anomalie se fait dans une étape ultérieure, présentée dans le chapitre 5 suivant. Cette étape s’intéresse à l’analyse locale des régions définies par la pose. Ces régions présentent les emplacements attendus des éléments de bridage .

Afin de pallier ce problème, nous proposons d’effectuer un changement de repère. Ce changement de repère est réalisé sur le nœud possédant le degré de connectivité le plus élevé, donné par Pi pour le plus grand sous-graphe réel (Ggsg ) et le nœud P ref dans le plus grand sous-graphe théorique (Hgsg ), respectivement, car le degré de connexité de chaque nœud dans le Gbgsg reflète « le degré d’importance d’une région » dans le montage d’usinage. En effet, un nœud représentant un degré de connexité élevé peut indiquer une zone de forte présence de primitives circulaires et rectilignes, i.e. région de brut. Le choix du nœud caractérisé par un degré de connexité élevé dans le graphe théorique (Hgsg ) augmente la probabilité de trouver son correspondant dans le graphe (Ggsg ), car le critère de voisinage a été utilisé dans la construction des graphes. Si plusieurs nœuds ont le même degré de connexité le plus élevé, un tirage aléatoire est effectué sur cet ensemble pour sélectionner un nœud.

En plus, nous nous intéressons ici à un objet rigide, qui ne peut pas subir une déformation importante, ce qui signifie que la matrice Φ est une matrice orthogonale. La difficulté pour calculer les paramètres de la matrice Φ provient de la méconnaissance des correspondances entre les nœuds. Le problème peut être résolu par un système d’équations linéaires, de type ||Piref − ΦPi|| = 0. Avec || || la norme euclidienne.

Certains travaux ont traité ce problème pour des applications de classification [Zhang 2007a], de reconnaissance de formes [Zhang 2006] et de calcul géométrique [Zheng 2006]. Ces solutions, ont souvent une complexité algorithmique non polyno-miale NP-complete. Pour éviter le problème du temps de calcul dans la recherche de l’appariement, nous proposons de poser une contrainte supplémentaire. La table de fixation du montage d’usinage au sein de la machine dispose des rainures droites per-mettant de limiter les orientations en positionnement du montage d’usinage. La figure 4.11 en montre un exemple. Finalement, Φ n’est qu’une matrice d’orientation du plan de la recherche de l’organisation topologique des éléments de bridage, avec 4 orien-tations possibles Φq = [0, π/2, π, 3π/2]. Dans le cas où l’organisation des éléments de bridage est symétrique par rapport aux deux axesox etoy , le problème n’est pas posé, car les rotations du plan Φq donnent le même appariement à chaque itération ”q”.