Aller au contenu

Géométrie Discrète - CM séance 01

0. Description de l'UE

Présentation :

  • UE SINCU78L - "Géométrie Discrète"
  • Responsable : Edouard.Thiel@univ-amu.fr
  • Lien court vers ce site du cours : https://j.mp/gd-et

Contenu :

  • Géométrie discrète : étude de la géométrie dans une image discrète
  • droites et plans discrets, polygonalisation
  • distances discrètes
  • axe médian, squelette
  • morphologie mathématique
  • etc
  • Conférences du domaine : DGCI (<= 2019), DGMM (>= 2021)

Intervenants :

  • Édouard Thiel : 6 séances
  • Aldo Gonzalez Lorenzo : 3 séances
  • Ricardo Uribe Lobello : 3 séances

MCC :

  • Note finale = notes de TP 50% + examen 50%
  • à l'examen : notes de cours et TP autorisées ; dispositifs électroniques interdits.

1. Librairie pour les TP en 2D

Librairie OpenCV : en C++, logiciel libre, créée par Gary Bradski

Librairie de "computer Vision" : plus de 500 fonctions

  • traiter les images 2D, vidéos (fichiers, flux caméras), tracking, machine learning...
  • GUI intégré simpliste : HighGUI en 2D (on peut aussi utiliser Qt, GTK, ...)
  • permet de manipuler des images en dimension \(n\)
  • wrappers en C et en python

Tutorial : https://docs.opencv.org/master/d9/df8/tutorial_root.html

En TP, utilisation d'une interface minimaliste au clavier : Astico2D

  • téléchargez les sources et les images de test ;
  • suivez les instruction pour l'installation.

Tous les TP devront être rendus, sur la page Ametice du cours.

Buts au niveau de la façon de programmer :

  • robustesse : le code fonctionne pour toutes les images et tous les seuils ;
  • efficacité : les calculs sont quasi-instantanés ;
  • simplicité : le code est facile à relire et à maintenir.

2. Notions de topologie discrète

2.1 Espace de travail

\({\Bbb Z}^d\) avec \(d = 2, 3\)

Grille discrète = réseau fondamental de \({\Bbb Z}^d\) = maillage sur le plan.

  • points à coordonnées entières
  • pixel = pavé centré sur un point : pavage du plan
Les 3 seuls pavages réguliers du plan :
carré, triangulaire, hexagonal

Dualité maillage / pavage :

  • carré / carré
  • triangulaire / hexagonal
  • hexagonal / triangulaire

Intérêt maillage carré : accès direct au point par les coordonnées

Codage : avec des valeurs entières

On a 2 choses \(\neq\) :

  • la grille discrète
  • les points à valeur entière

2.2 Voisinages et connexité

En 2D :

  • 4-voisinage de \(P\) = voisins directs de \(P\)
  • 8-voisinage de \(P\) = voisins directs + indirects de \(P\)

En 3D :

  • 6-voisinage de \(P\) = voisins directs de \(P\)
  • 18-voisinage de \(P\) : voisins directs + adjacents par une arête
  • 26-voisinage de \(P\) : voisins directs + adjacents par un sommet ou une arête

On dit que 2 points \(P,\;Q\) sont \(n\)-voisins (\(n = 4, 8, \ldots\)), ou \(n\)-connexes, ou encore adjacents pour la \(n\)-connexité, si \(Q \in n\)-voisinage de \(P\) (ou vice-versa).

2.3 Cas général

Une \(k\)-face est une face de dimension \(k\).

Deux voxels sont \(k\)-voisins s'ils partagent au moins une \(k\)-face.

Formellement : soit \(p,\,q \in {\Bbb Z}^n, \; 0 \leq k \leq n\) ; \(p\) et \(q\) sont \(k\)-voisins ssi : \(|p_i - q_i| \leq 1 \; \forall i\), et \(k \leq n - \sum_{i=1}^n | p_i - q_i|\).   [Andres 2000]

Combinatoire : on note

  • \(U_k^n\) le nombre de \(k\)-faces du \(n\)-cube
  • \(N_k^n\) le nombre de \(k\)-voisins pour le \(n\)-cube.

On a :

\(U_k^n = U_{k-1}^{n-1} + 2\,U_k^{n-1}\)

\(U_k^n = \binom{n}{k}\,2^{n-k}\)   [Berger 1990]

\(N_k^n = U_k^n + \ldots + U_{n-1}^n\)   avec \(N_0^n = 3^n -1\)

2.4 Définitions

Pour une connexité \(n\)

Un chemin de \(p_0\) à \(p_k\) est une suite de points \(p_0, p_1, \ldots, p_k\) telle que \(p_i\) est voisin de \(p_{i-1}\) pour \(1 \leq i \leq k\).

Un arc est un chemin tel que chaque point a exactement 2 voisins, sauf les extrémités qui n'en n'ont qu'un.

Une courbe est un arc fermé (chaque point a exactement 2 voisins).

Deux points reliés par un chemin sont connectés.

Un objet dans une image est un ensemble de points connectés 2 à 2.

2.5 Dualité des connexités

Exemples

  1. Courbe 4-connexe et intérieur 8-connexe
  2. Courbe 8-connexe et intérieur 4-connexe

Théorème de Jordan continu : le complémentaire d'une courbe fermée simple est formée de 2 parties disjointes : l'intérieur et l'extérieur.

Est-ce vrai dans l'espace discret ?

Théorème de Jordan discret : le complémentaire d'une courbe discrète \(n\)-connexe est formé de 2 composantes \(n'\)-connexes (l'intérieur et l'extérieur) :

  • En 2D :

    \(n = 4 \; \longrightarrow n' = 8\)

    \(n = 8 \; \longrightarrow n' = 4\)

    \(n = 6 \; \longrightarrow n' = 6\)   (maillage hexagonal)

  • En 3D :

    6/18 ou 6/26

  • En dimension supérieure : problème ouvert

Voir [Kong et Rosenfeld 1989]

2.6 Points contour

Étant donné un objet, on veut déterminer les points de contour = les points de l'objet qui touchent le fond.

Définition : les points du contour d'un objet sont les points de l'objet qui sont voisins du fond, pour la connexité ... du fond !

Propriété : le contour n'est (en général) pas une courbe.

2.7 Algorithme de numérotation des contours par balayage et fusion des labels

Version améliorée de l'algorithme séquentiel de [Rosenfeld et Pfaltz 1966] 1 avec des listes circulaires d'indice.

Étant donnée une connexité \((n, n')\) :

  1. Un pixel \(p\) balaye l'image ligne à ligne :

    • si \(p\) est un point de contour (pour le \(n'\)-voisinage) :
      soit \(L\) l'ensemble des labels des \(n\)-voisins de \(p\) déjà marqués dans la forme ;
      • si \(L\) est vide, on marque \(p\) avec un nouveau label (le premier label étant 1) ;
      • sinon, si la taille de \(L\) est 1, alors on marque \(p\) avec le label de \(L\) ;
      • sinon, on marque \(p\) avec l'un des labels de \(L\), et on mémorise les autres labels de \(L\) dans un groupe d'équivalence au label recopié.

    Exemple : (. fond, + forme) 

      . . 1 1 1 1 . . 2 2 2 2 2 .
  . 1 + + + + 1 1 + + + + 2 .  -> groupe d'équivalence [1, 2]
  . 1 1 + + + + + + 5 5 2 . .  -> groupe d'équivalence [1, 2, 5]
  . . . + + + + + + . . . . .

  2. Pour chaque groupe d'équivalence on choisit un label final (ce sera le numéro du contour).

  3. Étape de fusion : on re-balaye l'image ligne à ligne, et on remplace pour chaque pixel marqué son label par son label final.

Pour gérer efficacement les groupes d'équivalence, on les mémorise par des listes circulaires d'indices dans un simple tableau.

Exemple pour coder le groupe [1, 2, 5], et le groupe [3, 8, 10, 9] :

    i :  0  1  2  3  4  5  6  7  8  9  10  11  12
 s[i] : -1  2  5  8 -1  1 -1 -1 10  3   9  -1  -1

  1. Voir sections 3.2 et 3.3. Attention, dans cet article le fond est à 1 et la forme à 0 ; la valeur d'un pixel de coordonnées \(x,y\) dans une image \(a\) est notée \(a_{y,x}\) (notation matricielle ligne,colonne). ↩