Reconnaissance de Plans Discrets

Reconnaissance de Plans Discrets

Introduction

Comme nous l’avons vu dans le chapitre 3, la reconnaissance de plans discrets est un problème largement étudié en géométrie discrète. Nous décrivons dans ce chapitre une nouvelle méthode pour décider si un ensemble de n points de Z 3 correspond à la discrétisation d’un morceau de plan euclidien. La méthode que nous décrivons ici est celle proposée à la conférence internationale DGCI (Discrete Geometry for Computer Imagery) de 2008 (voir [CB08a]). Une version préliminaire de cet algorithme avait déjà été présentée en 2006 par Lilian Buzer dans [Buz06]. La plupart des méthodes existantes ne combinent pas à la fois une complexité intéressante dans le pire cas et une efficacité en pratique. Par exemple, les méthodes utilisant les résultats optimaux de Megiddo (voir [Meg84]) ont beau ˆetre linéaires, elles peuvent difficilement ˆetre utilisées en pratique. Quant à la méthode des cordes (voir [GDRZ05]), elle parvient à traiter un ensemble de 106 points en parcourant environ 10 fois l’ensemble des cordes mais sa complexité dans le pire cas est de l’ordre de O(n 7 ). La méthode de 2006 de Lilian Buzer [Buz06] atteint une complexité dans le pire cas de O(n log2 D) o`u D − 1 représente la plus grande longueur d’une boite englobant l’ensemble de points et elle reconnaˆıt un ensemble dense de 106 points en environ 360 itérations linéaires. Notre méthode actuelle est plus efficace en pratique puisqu’elle reconnaˆıt un ensemble dense de 106 points en environ 10 itérations linéaires et elle atteint une complexité dans le pire cas de O(n log D). La méthode de 2006 et la méthode présentée ici transforment le problème de reconnaissance de plans discrets na¨ıfs en un problème de réalisabilité sur une fonction convexe bi-dimensionelle dite fonction épaisseur. Par conséquent, ces méthodes ne prennent en compte que deux paramètres et nous pouvons utiliser des techniques de géométrie discrète planaire afin de déterminer si l’espace des solutions 2D est vide ou pas. Pour résoudre le problème de réalisabilité, notre approche actuelle utilise une propriété du centre de gravité tandis que la méthode de 2006 combine l’oracle de Megiddo et une recherche dichotomique mono-dimensionnelle. Ce principal changement améliore la complexité en temps de la méthode et diminue considérablement son nombre d’itérations. Notre algorithme peut également ˆetre con¸cu de fa¸con incrémentale. Dans la section 4.2, nous montrons comment le problème de reconnaissance de plans discrets peut ˆetre transformé en un problème de réalisabilité sur une fonction convexe bi75 Nouvelle Approche Efficace pour la Reconnaissance de Plans Discrets dimensionnelle, la fonction épaisseur. Nous introduisons dans la section 4.3 une méthode pour résoudre ce problème de réalisabilité en utilisant le calcul d’un sous-gradient de la fonction épaisseur. Pour résoudre le problème de réalisabilité, nous réduisons l’espace de recherche continu en appliquant itérativement des coupes jusqu’à trouver un point solution ou jusqu’à ce que l’espace de recherche devienne vide. Dans la section 4.4, nous décrivons cette étape de réduction et nous commentons sont efficacité. Pour améliorer notre algorithme, nous discrétisons le domaine de recherche du problème de réalisabilité. Nous justifions dans la section 4.5 le choix du pas de discrétisation et nous expliquons comment adapter notre méthode à un domaine de recherche discrétisé. Nous analysons la complexité en temps de notre méthode dans la section 4.6. Dans la section 4.7, nous décrivons la version incrémentale de notre algorithme et nous terminons ce chapitre avec quelques résultats expérimentaux et la description d’améliorations pratiques.

La Reconnaissance de Plans

Comme un Problème de Réalisabilité Dans la section 3.2, nous avons défini la fonction épaisseur par rapport à un ensemble de points de Z 3 noté S comme une fonction de [−1, 1]2 vers R + définie par : epS(u) = max 1≤i≤n (Nu · p i ) − min 1≤i≤n (Nu · p i ) (4.1) o`u u = (u1,u2) appartient à [−1, 1]2 et Nu correspond au vecteur (u1,u2, 1). D’après la proposition 4, l’ensemble de points S correspond à un morceau de plan discret s’il existe un vecteur u de [−1, 1]2 qui vérifie epS(u) < 1. Notre problème de reconnaissance de plans discrets revient donc à déterminer un tel vecteur u ou à montrer qu’aucun vecteur de [−1, 1]2 ne satisfait epS(u) < 1. Par conséquent, nous nous ramènons à un problème de réalisabilité sur la fonction bi-dimensionnelle epS. Proposition 6 La fonction epS est une fonction convexe. Preuve 7 Soit Nu le vecteur associé au vecteur u ∈ [−1, 1]2 . Considérons la fonction g i (u) de [−1, 1]2 vers R qui associe au vecteur u la valeur Nu · p i . Cette fonction est une fonction affine, elle est donc convexe. Remarquons à présent que la fonction epS(u) peut ˆetre ré-écrite comme max1≤i≤n(g i (u)) + max1≤i≤n(−g i (u)). Comme le maximum des fonctions (g i )1≤i≤n est également convexe et comme la somme de deux fonctions convexes est convexe, nous en déduisons que la fonction epS est elle-mˆeme convexe. Le problème de reconnaissance de plans discrets est équivalent à un problème de réalisabilité sur une fonction convexe bi-dimensionnelle de domaine de recherche [−1, 1]2 . Si l’ensemble S ne correspond pas à un morceau de plan discret na¨ıf alors l’espace des solutions du problème de réalisabilité est vide. Sinon, l’espace des solutions correspond à un polygone convexe non-vide inclus dans [−1, 1]2 .

Résoudre le Problème de Réalisabilité

Introduction Générale Remarquons tout d’abord que nous ne traitons pas un problème d’optimisation mais un problème de réalisabilité. Ceci signifie que nous ne souhaitons pas déterminer d’un point u 76 dans le domaine de recherche tel que la valeur epS(u) est minimum mais nous recherchons un point u tel que epS(u) est strictement inférieure à 1. Cependant, certaines méthodes utilisées en optimisation convexe peuvent ˆetre adaptées pour résoudre des problèmes de réalisabilité. De fa¸con générale, pour optimiser une fonction convexe f : R d → R, nous devons déterminer le point x pour lequel la valeur f(x) est minimum ou maximum. Pour cela, nous pouvons utiliser la méthode de descente du gradient. En utilisant cette méthode, nous approchons le minimum de la fonction en nous dépla¸cant itérativement dans la direction de plus forte pente. A l’itération ` i, le gradient ∇(x i ) de f au point x i est calculé. Par définition du gradient, il existe une valeur réelle τi telle que f(x i ) est inférieure à f(x i + τi∇(x i )). Le point x i+1 de référence à l’itération suivante est alors égal à : x i+1 = x i + τi∇(x i ) (4.2) Cependant, dans un souci d’efficacité, nous pouvons difficilement appliquer ce type d’algorithmes pour résoudre notre problème de réalisabilité. En effet, pour procéder à des calculs numériques exacts, les valeurs successives τi et par conséquent les coordonnées des points x i doivent ˆetre représentées par des nombres rationnels. D’après (4.2), la taille du numérateur et du dénominateur de ces rationnels augmenteraient à chaque itération et ceci ralentirait significativement le calcul. Nous proposons donc une autre approche qui évite ce problème. Notre approche pour résoudre le problème réalisabilité consiste à réduire itérativement le domaine de recherche jusqu’à ce que nous trouvions un point solution ou jusqu’à ce que le domaine de recherche soit vide. Cette réduction du domaine de recherche est faite grˆace au calcul d’un sous-gradient de la fonction épaisseur. 

Calcul du Sous-Gradient

Nous rappelons tout d’abord qu’un sous-gradient g ∈ R d d’une fonction convexe f : R d → R au point x vérifie : pour tout x ′ ∈ R d , f(x ′ )−f(x) ≥ g ·(x ′ −x). Le sous-gradient est un vecteur qui indique la direction de plus forte pente de la fonction f au point x. Ceci signifie que si nous savons calculer un sous-gradient de la fonction epS en un point donné, nous connaissons un moyen de réduire le domaine de recherche. En effet, soit gu un sousgradient de la fonction epS au point u, alors pour tout vecteur v ∈ [−1, 1]2 satisfaisant gu · v ≥ gu · u, nous avons epS(v) ≥ epS(u). Si epS(u) est plus grand que 1 alors epS(v) est également plus grand que 1 et nous pouvons donc retirer tous ces points v du domaine de recherche. Les points à retirer correspondent à un des demi-plans portés par la droite de vecteur normal gu passant par le point u. Vous remarquerez que nous utilisons le terme “sous-gradient”à la place du terme“gradient”car la fonction épaisseur n’est pas dérivable en tout point. Pour résoudre notre problème de réalisabilité dans R 2 , nous devons déterminer comment calculer un sous-gradient de la fonction convexe epS à un point u donné. En accord avec la définition du sous-gradient, nous devons déterminer g tel que pour tout v ∈ [−1, 1]2 nous avons : epS(v) − epS(u) ≥ g · (v − u) (4.3) D’après la définition de epS, nous savons que epS(u) est égal à max1≤i≤n(Nu · p i ) − min1≤i≤n(Nu · p i ). Par conséquent, il existe deux points particuliers de S qui sont associés au produit scalaire maximum et au produit scalaire minimum. Notons respectivement p a et p b ces deux points (comme sur la figure 4.1), nous avons epS(u) = Nu · (p a − p b ). 77 projR2 (p a − p b ) x y α β epS(α, β) ≥ epS(x, y) epS(x, y) Fig. 4.1 – Un sous-gradient de epS Soit T l’ensemble de deux points {p a ,pb}. Comme T est inclus dans S, pour tout point v ∈ [−1, 1]2 , l’épaisseur par rapport à l’ensemble T au point v est plus petite que l’épaisseur par rapport à l’ensemble S au point v. Nous avons : ∀v ∈ [−1, 1]2 ,epT (v) ≤ epS(v) (4.4) Comme l’ensemble T ne contient que deux points, la valeur epT (v) est forcément égale à |Nv · (p a − p b )|. De plus, nous remarquons que tout vecteur v peut ˆetre écrit comme v + u − u et il s’en suit : epT (v) = |Nv−u+u · (p a − p b )| = |Nu · (p a − p b ) + (v − u) · projR2 (p a − p b )| = |epT (u) + (v − u) · projR2 (p a − p b )| D’après (4.4) et par définition de la valeur absolue, nous obtenons : ∀v ∈ R 2 ,epS(v) ≥ epT (v) ≥ epT (u) + (v − u) · projR2 (p a − p b ) (4.5) Nous rappelons que nous pouvons remplacer epT (u) par epS(u) et nous avons donc : ∀v ∈ R 2 ,epS(v) ≥ epS(u) + (v − u) · projR2 (p a − p b ) (4.6) D’après (4.3), nous pouvons à présent conclure que l’expression projR2 (p a − p b ) est un sous-gradient de epS au point u (voir la figure 4.1). Cette valeur correspond à la projection du vecteur p ap b dans R 2 . Nous constatons donc que les deux premières coordonnées du vecteur p ap b sont suffisantes pour déterminer localement la variation de la fonction epS. Lorsque nous calculons epS(u), nous déduisons indirectement les deux points p a et p b . Nous calculons donc en temps constant un sous-gradient. Remarque 4 Nous remarquons que si les deux points p a et p b associés respectivement à la valeur maximum et à la valeur minimum de la fonction épaisseur en un point ont les deux mˆemes premières coordonnées, alors le sous-gradient projR2 (p a − p b ) correspond au vecteur nul. Dans ce cas, le sous-gradient n’indique pas la direction de plus forte pente. Cependant, si l’ensemble de points S contient au moins deux points distincts avec les deux mˆemes premières composantes, alors l’ensemble S ne peut pas correspondre à un morceau de plan discret. Par conséquent, si nous calculons un sous-gradient nul, nous pouvons en déduire que l’ensemble de points ne correspond pas à un morceau de plan discret.