Géométrie Discrète - CM séance 01
0. Description de l'UE
Présentation :
- UE SINCB8BL - "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
MCC :
- Note finale = notes de TP 50% + examen 50%
- à l'examen : notes de cours et TP autorisées ; dispositifs électroniques interdits.
- TP : utilisation d'IAs génératives interdite.
- Présence aux CM et TP obligatoire.
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
- wrappers en C et en python
Tutorial : https://docs.opencv.org/master/d9/df8/tutorial_root.html / Core / Mat
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
Grille discrète = réseau fondamental de
- 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
- la grille discrète
- les points à valeur entière
2.2 Voisinages et connexité
En 2D :
- 4-voisinage de
= voisins directs de - 8-voisinage de
= voisins directs + indirects de
En 3D :
- 6-voisinage de
= voisins directs de - 18-voisinage de
: voisins directs + adjacents par une arête - 26-voisinage de
: voisins directs + adjacents par un sommet ou une arête
On dit que 2 points
2.3 Cas général
Une
Deux voxels sont
Formellement :
soit
Combinatoire : on note
le nombre de -faces du -cube le nombre de -voisins pour le -cube.
On a :
2.4 Définitions
Pour une connexité
Un chemin de
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
- Courbe 4-connexe et intérieur 8-connexe
- 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
-
- En 2D :
-
-
-
(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é
-
Un pixel
balaye l'image ligne à ligne :- si
est un point de contour (pour le -voisinage) :
soit l'ensemble des labels des -voisins de déjà marqués dans la forme ;- si
est vide, on marque avec un nouveau label (le premier label étant 1) ; - sinon, si la taille de
est 1, alors on marque avec le label de ; - sinon, on marque
avec l'un des labels de , et on mémorise les autres labels de dans un groupe d'équivalence au label recopié.
- si
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] . . . + + + + + + . . . . .
- si
-
Pour chaque groupe d'équivalence on choisit un label final (ce sera le numéro du contour).
-
É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
-
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
dans une image est notée (notation matricielle ligne,colonne). ↩