Géométrie Discrète - CM séance 06
6. Distances pondérées (suite)
6.4 Propriétés des distances de chanfrein
Définitions :
-
pondération : vecteur \(\vec{v}\) + poids \(w > 0\), notée \((\vec{v}, w)\) ;
-
masque : \(\mathcal{M} = \big\{ (\vec{v}_i, w_i)\,,\, 1 \leq i \leq m \big\}\) un ensemble de \(m\) pondérations ;
-
chemin : \(\mathcal{P}_{A,B} = \lambda_1.\vec{v}_1 +...+ \lambda_m.\vec{v}_m\) , \(\lambda_i \geq 0\) ;
-
coût du chemin : \(W(\mathcal{P}_{A,B}) = \lambda_1.w_1 +...+ \lambda_m.w_m\) ;
-
distance pour le masque \(\mathcal{M}\) :
\[ \begin{array}{ll} d_\mathcal{M}(A,B) \!\! & = \text{min}_{\,\displaystyle\mathcal{P}_{A,B}}\, \big\{\, W(\mathcal{P}_{A,B}) \,\big\} \\ & = \text{min}\,\big\{ \lambda_1.w1 +...+ \lambda_m.w_m \,:\, \lambda_1.\vec{v}_1 +...+ \lambda_m.\vec{v}_m = \overrightarrow{AB},\, \lambda_i \geq 0 \big\} \end{array} \] -
Masque de chanfrein : masque central-symétrique, de poids strictement positifs et de déplacements non nuls, qui contient au moins une base de \(\Bbb{Z}^n\).
- Théorème 1 : [Verver 1991]
- Tout masque de chanfrein induit une distance.
On s'intéresse maintenant à la classe particulière des masques qui définissent une norme.
- Définition d'une norme discrète :
-
application \(g\,:\, \Bbb{Z}^n \longrightarrow \Bbb{Z}\), vérifiant pour tous vecteurs \(\vec{x}, \vec{y} \in \Bbb{Z}^n\), et \(\forall \lambda \in \Bbb{Z}\) :
- (1) positive : \(g(\vec{x}) \geq 0\)
- (2) définie : \(g(\vec{x}) = 0 \,\Leftrightarrow\,\vec{x} = \vec{0}\)
- (3) triangulaire : \(g(\vec{x}+\vec{y}) \leq g(\vec{x})+g(\vec{y})\)
- (4) homogène : \(g(\lambda.\vec{x}) = |\lambda|.g(\vec{x})\)
- Relation entre distance et norme discrète :
-
soit \(g\) une norme discrète, alors \(d(p,q) = g(q-p)\) est une distance, qui de plus vérifie :
- (5) invariante par translation : \(d(p+\vec{r},q+\vec{r}) = d(p,q) \,,\;\; \forall r \in \Bbb{Z}^n\)
- (6) homogène : \(d(\lambda.p,\lambda.q) = |\lambda|.d(p,q) \,,\;\;\forall \lambda \in \Bbb{Z}\)
Dans quel cas un masque de chanfrein induit-il une norme ?
On appelle boule rationnelle équivalente du masque \(\mathcal{M}\) l'enveloppe convexe suivante : [Remy 2001]
Cette boule est un polyèdre dont chaque facette est délimitée par des pondérations.
Si une facette a plus de \(n\) pondérations, on peut la trianguler pour obtenir des sous-facettes de \(n\) pondérations (elles seront co-planaires).
- Théorème 2 : [Thiel 2001] [Hulin 2009] [Normand 2012]
- un masque de chanfrein \(\mathcal{M}\) induit une norme ssi pour chaque facette \(F\) de \(\text{BRE}_\mathcal{M}\), il existe une triangulation de \(F\) en sous-facettes unimodulaires.
Dans ce cas la boule de chanfrein a exactement la même géométrie que la BRE.
Chaque facette délimite un cône à l'origine, dont les distances à l'origine ne dépendent que de ses pondérations (tous les points du cône sont atteints puisque la facette est unimodulaire).
- Théorème 3: [Thiel 2001]
- soit \(\mathcal{M}\) un masque de chanfrein induisant une norme ;
soit \(F\) une facette de \(BRE_\mathcal{M}\), de pondérations
\((\vec{v}_1,w_1), \ldots, (\vec{v}_n,w_n)\).
Soit \(p(y_1,\ldots,y_n) \in F\), alors on a \(d_\mathcal{M}(O,p) = y_1.\delta_1 + ... + y_n.\delta_n\) , où
Remarques :
- le premier det est \(\pm 1\) ; le deuxième det est le mineur en enlevant la coordonnée \(i\).
- le vecteur (\(\delta_1, ..., \delta_n)\) est normal à la facette ;
- les scalaires \(\delta_1, ..., \delta_n\) sont constants dans tout le cône \(\widehat{(O,F)}\) ; on les appelle les déplacements élémentaires dans le cône.
Exemple avec \(\langle 5, 7, 11 \rangle\), boule de rayon 35 dans le premier octant :
| | |
+---+---+---+-
6 | | | |
+---+---+---+---+-
5 | | | | |
+---+---+---+---+---+-
4 | | | | | |
+---+---+---+---+---+---+-
3 | | | | | | |
+---+---+---+---+---+---+---+-
2 | | | | | | | |
+---+---+---+---+---+---+---+---+-
1 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+-
0 | O | | | | | | | | |
+---+---+---+---+---+---+---+---+---+-
0 1 2 3 4 5 6 7 8
Est-ce une norme ? Quelles sont les facettes de BRE, les déplacements élémentaires dans les cônes ?
6.5 Axe médian
Ancètre du squelette d'une forme : lieu de rencontre d'un "feu de prairie" allumé simultanément sur le bord de la forme. [Blum 1964]
Il s'agit concrètement sur une image de distance, du lieu de rencontre des courbes de niveaux → lieu des maximums locaux sur une DT (détectés en TP).
Par la suite [Pfaltz et Rosenfeld 1967] l'ont redéfini de manière équivalente comme le lieu des boules maximales dans la forme :
- en chaque pixel \(p\) d'une forme, \(\text{DT}[p]\) est le rayon de la plus grande boule centrée en \(p\) et entièrement incluse dans la forme ;
- une boule est dite maximale dans la forme si elle n'est incluse dans aucune une autre boule incluse dans la forme.
L'axe médian constitue un recouvrement de la forme par les boules maximales, et est donc réversible (avec une RDT).
Pour \(d_4\) et \(d_8\), l'axe médian coïncide avec les maximums locaux ; pour les distances de chanfrein, l'axe médian est inclus dans l'ensemble des maximums locaux (il y a des points en trop).
[Remy 2002] a montré que le voisinage de détection (appelé \(\mathcal{M}_\text{LUT}\)) sur une DT, qui coïncide avec le masque de chanfrein pour les masques "simples", peut être très différent pour d'autres masques, et a donné un algorithme de calcul.
[Normand, Evenou 2008] ont donné un algorithme plus efficace de calcul de \(\mathcal{M}_\text{LUT}\) en 2D et 3D, utilisant des "H-polytopes".
Un boule maximale peut être incluse dans l'union de plusieurs boules ; on peut donc supprimer certaines boules en conservant la réversibilité. [Coeurjolly, Hulin, Sivignon 2008] ont montré que trouver un sous-ensemble minimal réversible de l'axe médian est NP-difficile.
7. Transformation de distance Euclidienne
Très nombreux algorithmes de calculs depuis [Danielsson 1980]. Souvent erronés, ou lents, ou complexes. Voir la thèse [Cuisenaire 1999].
Premier algorithme exact, efficace et simple : SEDT de [Saito et Toriwaki 1994]
- calcule \(d_E^2\) ;
- valable en toute dimension ;
- utilise le fait que \(d_E\) est séparable en dimension : on peut faire les calculs dimension par dimension ;
- est naturellement parallélisable.
- Premier passage : dimension \(x\)
- pour chaque ligne, on marque les pixels de la forme à leur distance \(d_E^2\) aux 0 de la ligne (il suffit de faire un aller-retour et calculer le min).
Exemple :
0 0 0 0 0 0 0 0 0 0 0 0
+---+---+---+---+---+---+---+
0 0 0 | | | | | | | | 0 0
+---+---+---+---+---+---+---+
0 0 0 | | | | | | | | 0 0
+---+---+---+---+---+---+---+---+---+
0 | | | | | 0 | | | | | 0 0
+---+---+---+---+---+---+---+---+---+---+
0 | | | | | | | | | | | 0
+---+---+---+---+---+---+---+---+---+---+
0 0 0 | | | | | | | | | 0
+---+---+---+---+---+---+---+---+
0 0 0 0 | | | | | | | 0 0
+---+---+---+---+---+---+---+
0 0 0 0 0 | | | | | | | 0
+---+---+---+---+---+---+
0 0 0 0 0 0 0 0 0 0 0 0
- Deuxième passage : dimension \(y\)
-
pour chaque colonne,
- on recopie la colonne courante ;
- pour chaque case de la colonne,
on cherche le min dans la colonne en rajoutant +1, +4, +9, etc
(incrément de distance verticale au carré),
puis on l'enregistre dans l'image résultat.
Et ainsi de suite pour les dimensions suivantes.
On utilise donc le fait que : (\(F\) désignant le fond)
Complexité : pour une image \(n \times n\)
- dim \(x\) : \(O(n^2)\)
- dim \(y\) : \(O(n^3)\)
→ \(O(n^3)\)
En réalité, dans une colonne on peut s'arrêter dès que l'incrément de distance verticale au carré excède le min courant → plus la case à calculer est proche d'un bord, plus tôt on s'arrête.
→ la complexité est \(O(n^2.m)\) où \(m\) est l'épaisseur moyenne de la forme.
Il existe une RSEDT [Coeujolly 2003] : même principe avec des max.
Amélioration : [Kato, Hirata et al 1996] on calcule l'enveloppe inférieure de paraboles avec un algorithme glouton. En \(O(n^2)\) (temps linéaire en le nombre de pixels), mais il ne "bat" Saito et Toriwaki qu'à partir d'une certaine taille d'image.
Axe médian :
- On peut le détecter sur SEDT de manière exacte, avec l'algorithme de calcul de \(\mathcal{M}_\text{LUT}\) [Rémy 2005].
- Théorème : \(\mathcal{M}_\text{LUT}\) tend vers l'ensemble des points visibles [Hulin 2009].