Géométrie Discrète - CM séance 05
5. Transformations de distances (suite)
5.3 Calcul efficace : algos de Rosenfeld
5.3.1 Principe
- deux balayages séquentiels sur l'image, avec deux demi-masques
- indépendendant de l'épaisseur de la forme
- adaptable en toute dimension
Balayage avant : de haut en bas, de gauche à droite
1 -------------->
2 -------------->
3 -------------->
...
Balayage arrière : de bas en haut, de droite à gauche
...
<-------------- 3
<-------------- 2
<-------------- 1
Balayage avant :
+----------------------------------+
| |
| Points déjà marqués | Demi-masque avant pour N4 :
| | 1
| +---+--------------| +---+---
| | P | | --> 1 | P |
|---------------+---+ | ---+---+
| |
| Points pas encore marqués |
| |
+----------------------------------+
Balayage arrière :
+----------------------------------+
| |
| Points pas encore marqués | Demi-masque arrière pour N4 :
| |
| +---+--------------| +---+---
| | P | | --> | P | 1
|---------------+---+ | ---+---+
| | 1
| Points déjà marqués |
| |
+----------------------------------+
5.3.2 DT de Rosenfeld
Algorithme pour \(d_4\) :
Balayage avant : de haut en bas, de gauche à droite
si I[x,y] != 0 :
I[x,y] = MIN { I[x ,y-1] + 1, // 1
I[x-1,y ] + 1 } // 1 P
Balayage arrière : de bas en haut, de droite à gauche
si I[x,y] != 0 :
I[x,y] = MIN { I[x,y],
I[x+1,y ] + 1, // P 1
I[x ,y+1] + 1 } // 1
Exemple :
+---+---+ +---+---+
. . | | | . . . . . . . | | | . . . . .
+---+---+---+---+---+---+ +---+---+---+---+---+---+
. | | | | | | | . . . | | | | | | | . .
+---+---+---+---+---+---+ +---+---+---+---+---+---+
. | | | | | | | . . . | | | | | | | . .
+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+
| | | | | | | | . . | | | | | | | | . .
+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+
| | | | | | | | . . | | | | | | | | . .
+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+
| | . . | | | | . . . | | . . | | | | . . .
+---+ +---+---+---+ +---+ +---+---+---+
balayage avant balayage arrière
Propagation des distances :
= distances au bord = corrections distances
0
^ P------->0
| |
| |
0<---------P v
0
Algorithme pour \(d_8\) :
1 1 1
demi-masque +---+--- demi-masque +---+---
avant : 1 | P | arrière : | P | 1
---+---+ ---+---+
1 1 1
Balayage avant : de haut en bas, de gauche à droite
si I[x,y] != 0 :
I[x,y] = MIN { I[x ,y-1] + 1,
I[x-1,y ] + 1,
I[x-1,y-1] + 1, // rajouté
I[x+1,y-1] + 1 } // rajouté
Balayage arrière : de bas en haut, de droite à gauche
si I[x,y] != 0 :
I[x,y] = MIN { I[x,y],
I[x+1,y ] + 1,
I[x ,y+1] + 1,
I[x+1,y+1] + 1, // rajouté
I[x-1,y+1] + 1 } // rajouté
Propagation des distances :
= distances au bord = corrections distances
0
0 ^ 0 P------->0
\ | / /|\
\|/ / | \
0<---------P 0 v 0
0
5.3.3 RDT de Rosenfeld
Même principe avec des Max :
Balayage avant : de haut en bas, de gauche à droite
I[x,y] = MAX { I[x,y],
I[x ,y-1] - 1,
I[x-1,y ] - 1,
I[x-1,y-1] - 1, // pour d8
I[x+1,y-1] - 1 } // pour d8
Balayage arrière : de bas en haut, de droite à gauche
I[x,y] = MAX { I[x,y],
I[x+1,y ] - 1,
I[x ,y+1] - 1,
I[x+1,y+1] - 1, // pour d8
I[x-1,y+1] - 1 } // pour d8
Exemple avec \(d_4\) :
+---+---+ +---+---+
. . | | | . . . . . . . | | | . . . . .
+---+---+---+---+---+---+ +---+---+---+---+---+---+
. | | | | | | | . . . | | | | | | | . .
+---+---+---+---+---+---+ +---+---+---+---+---+---+
. | | | | | | | . . . | | | | | | | . .
+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+
| | | | | | | | . . | | | | | | | | . .
+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+
| | | | | | | | . . | | | | | | | | . .
+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+
| | . . | | | | . . . | | . . | | | | . . .
+---+ +---+---+---+ +---+ +---+---+---+
balayage avant balayage arrière
5.3.4 Généralisation avec des poids a,b
b a b
demi-masque +---+--- demi-masque +---+---
avant : a | P | arrière : | P | a
---+---+ ---+---+
b a b
Algorithme DT :
Balayage avant : de haut en bas, de gauche à droite
si I[x,y] != 0 :
I[x,y] = MIN { I[x ,y-1] + a,
I[x-1,y ] + a,
I[x-1,y-1] + b,
I[x+1,y-1] + b }
Balayage arrière : de bas en haut, de droite à gauche
si I[x,y] != 0 :
I[x,y] = MIN { I[x,y],
I[x+1,y ] + a,
I[x ,y+1] + a,
I[x+1,y+1] + b,
I[x-1,y+1] + b }
Exemple avec \(a = 2\), \(b = 3\) [Hilditch 1969]
+---+---+ +---+---+
. . | | | . . . . . . . | | | . . . . .
+---+---+---+---+---+---+ +---+---+---+---+---+---+
. | | | | | | | . . . | | | | | | | . .
+---+---+---+---+---+---+ +---+---+---+---+---+---+
. | | | | | | | . . . | | | | | | | . .
+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+
| | | | | | | | . . | | | | | | | | . .
+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+
| | | | | | | | . . | | | | | | | | . .
+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+
| | . . | | | | . . . | | . . | | | | . . .
+---+ +---+---+---+ +---+ +---+---+---+
balayage avant balayage arrière
Autres poids dans la littérature :
- \(a = 3, b = 4\) [Borgefors 1984]
- \(a = 5, b = 7\)
6. Distances pondérées
Inconvénients des distances précédentes :
- varient selon orientation des formes : "anisotropie" ;
- "erreur" max par rapport à la distance euclidienne : \(d_4 \simeq 41\%\) ; \(d_8 \simeq 29\%\).
6.1 Distances de Montanari
Principe :
- choisir une taille de voisinage \((2n+1) \times (2n+1)\) ;
- pondérer certains déplacements \((x,y)\) avec la distance euclidienne \(\sqrt{x^2+y^2}\).
- La distance entre 2 points est le coût du chemin minimal entre ces deux points, parmi les chemins utilisant cette famille de déplacements.
Exemple : voisinage \(5 \times 5\)
poids : \(1\) pour \((1,0)\), \(\sqrt{2}\) pour \((1,1)\), \(\sqrt{5}\) pour \((2,1)\), etc.
distance de A à H :
√5 √5 A-B-C-D-E-F-G-H =
A-J-K-L + L-M-H =
√5 √2 1 √2 √5 A-I-G + G-H =
+---+--------
1 | P | 1 C---D---E---F---G---H
--------+---+ | /
√5 √2 1 √2 √5 B . I . M .
| /
√5 √5 A---J---K---L . .
Les algorithmes DT et RDT de Rosenfeld sont utilisables.
Les distances de Montanari sont toujours des distances ; formules closes.
Erreur max par rapport à \(d_E\) :
\(3 \times 3 \simeq 3.95\%\) ; \(5 \times 5 \simeq 1.35\%\).
Inconvénient : valeurs réelles.
6.2 Distances de chanfrein
[Borgefors 1984 et 1986]
Principe : approximer les distances de Montanari par des entiers
√5 √5 c c
√5 √2 1 √2 √5 c b a b c
+---+-------- +---+--------
1 | P | 1 a | P | a
--------+---+ --------+---+
√5 √2 1 √2 √5 c b a b c
√5 √5 c c
en choisissant des poids tels que \(b/a \simeq \sqrt{2}\), \(c/a \simeq \sqrt{5}\), etc.
Pour l'erreur max on divise tout par \(a\) :
- \(\langle a=3, b=4 \rangle \simeq 5\%\)
- \(\langle a=5, b=7, c=11 \rangle \simeq 2\%\)
Exemple avec \(\langle 5, 7, 11 \rangle\) :
distance de A à H :
A-B-C-D-E-F-G-H =
A-J-K-L + L-M-H =
A-I-G + G-H =
C---D---E---F---G---H
| /
B . I . M .
| /
A---J---K---L . .
Généralisation :
- Les algorithmes DT et RDT de Rosenfeld sont utilisables.
- Les distances de chanfrein sont toujours des distances [Verver 1991].
Questions :
- choix des déplacements ?
- choix des pondérations ?
- définition formelle ?
- formule directe ?
- norme ?
- géométrie des boules ?
6.3 Notions de géométrie des nombres
6.3.1 Points visibles
Un point \(P(x_1,..., x_n) \in \Bbb{Z}^n\) est visible (depuis l'origine) s'il n'y a aucun point de \(\Bbb{Z}^n\) sur la droite réelle \((OP)\) entre \(O\) et \(P\).
Condition nécessaire et suffisante : \(\text{pgcd}(x_1,..., x_n) = 1\)
Intérêt pour la construction des masques : ne pondérer que des points visibles \(P\) puisque les périodes \(k.P\) auront pour distance \(k.d(O,P)\).
Symétries dans \(\Bbb{Z}^2\) : les points visibles sont symétriques par rapport à \(O\) et aux axes → on peut restreindre leur étude au premier octant \(0 \leq y \leq x\)
Détermination des points visibles avec un crible :
- on marque toutes les cases à 1, sauf \(O\) à 0 ;
- on parcourt colonne par colonne : si une case est à 1, on marque toutes ses périodes à 0.
Premiers points visibles :
+---+
6 | |
+---+---+
5 | | |
+---+---+---+
4 | | | |
+---+---+---+---+
3 | | | | |
+---+---+---+---+---+
2 | | | | | |
+---+---+---+---+---+---+
1 | | | | | | |
+---+---+---+---+---+---+---+
0 | O | | | | | | |
+---+---+---+---+---+---+---+
0 1 2 3 4 5 6
Propriété : si \(k > 1\), le nombre de points visibles de la colonne \(k\) = le nombre d'entiers \(< k\) premiers avec \(k\), qui est \(\phi(k)\) (l'indicatrice phi d'Euler).
6.3.2 Suites de Farey
- Découvertes par Haros en 1802
- redécouvertes par Sir John Farey en 1816 (géologue)
- puis étudiées par Cauchy
Définition : les suites de Farey \(F_k\) d'ordre \(k\) sont les séries croissantes de fractions irréductibles entre 0 et 1, dont le dénominateur n'excède pas \(k\).
Donc \(y/x \in F_k\) ssi \(0 \leq y \leq x \leq k\) et \(\text{pgcd}(x,y) = 1\).
Construction :
- \(F_1\) : \(0/1 < 1/1\)
- \(F_2\) : \(0/1 < 1/2 < 1/1\)
- \(F_3\) : \(0/1 < 1/3 < 1/2 < 2/3 < 1/1\)
Médian de deux fractions : \(y/x \oplus y'/x' = \frac{y+y'}{x+x'}\)
Théorème 1 : si \(y/x < y''/x'' < x'/y'\) sont trois termes successifs d'une suite de Farey, alors \(y''/x'' = y/x \oplus y'/x'\).
Construction automatique de \(F_k\) :
- init : \(F_1 = 0/1 < 1/1\)
- connaissant \(F_{k-1}\), on obtient \(F_k\) en intercalant entre chaque couple successif \(y/x < y'/x'\) leur médian, si son dénominateur est \(\leq k\).
Exemple :
- \(F_4 : 0/1 < 1/4 < 1/3 < 1/2 < 2/3 < 3/4 < 1/1\)
- \(F_5 : 0/1 < 1/5 < 1/4 < 1/3 < 2/5 < 1/2 < 3/5 < 2/3 < 3/4 < 4/5 < 1/1\)
Théorème 2 : si \(y/x < x'/y'\) sont deux termes successifs d'une suite de Farey, alors
6.3.3 Réseaux
Réseau = points disposés régulièrement :
+ + + +
+ + + +
/
+ +-------+ +
+ + + + +
Définitions :
-
\(L \subset \Bbb{Z}^n\) est un réseau ssi \(L\) est un sous-groupe additif.
-
\(V = \{\vec{v_1}, \ldots, \vec{v_n}\}\) est une base de \(L\) ssi \(\forall \vec{v} \in L\), \(\exists\) un système unique d'entiers \(b_1,\ldots, b_m\) tq \(\vec{v} = b_1.\vec{v_1} + \ldots + b_m.\vec{v_m}\).
Tout réseau possède une base ; toutes les bases d'un réseau ont même cardinal = dimension du réseau.
Parallélotope fondamental d'un réseau = parallélogramme défini par la base.
Déterminant d'un réseau = déterminant \(\text{det}(V)\) des vecteurs de la base = aire du parallélotope fondamental.
- Cas particulier : \(|\text{det}(V)| = 1\)
- → réseau unimodulaire, \(L = \Bbb{Z}^n\)
Autrement dit, tous les points de \(\Bbb{Z}^n\) sont atteints par la base \(V\)
ou encore, le parallélotope fondamental ne contient aucun point discret.
6.3.4 Liens entre points visibles, suites de Farey et réseaux
\((x,y)\) point visible de \(0 \leq y \leq x \leq k\) \(\;\Leftrightarrow\;\) \(y/x \in F_k\) .
À quoi correspond l'ordre de \(F_k\) ?
\(F_5 : 0/1 < 1/5 < 1/4 < 1/3 < 2/5 < 1/2 < 3/5 < 2/3 < 3/4 < 4/5 < 1/1\)
+---+
5 | |
+---+---+
4 | | k |
+---+---+---+
3 | | g | j |
+---+---+---+---+
2 | | e | | i |
+---+---+---+---+---+
1 | b | c | d | f | h |
+---+---+---+---+---+---+
0 | O | a | | | | |
+---+---+---+---+---+---+
0 1 2 3 4 5
Réponse
\(a < h < f < d < i < c < j < e < g < k < b\)
C'est l'ordre angulaire autour de O par rapport à l'horizontale !
- Lien avec les réseaux :
- Soit \(U(x_U,y_U)\) et \(V(x_V,y_V)\) deux points visibles tq
\(y_U/x_U < y_V/x_V\) sont consécutifs dans une suite de Farey.
→ théorème 2 : \(|\text{det}| = 1\)
→ \(U\) et \(V\) forment une base d'un réseau unimodulaire
→ dans le cône \(\widehat{U,O,V}\), tous les points sont atteints par une combinaison linéaire de \(U\) et \(V\).