Géométrie Discrète - CM séance 02
2. Notions de topologie discrète (suite)
2.8 Codes de Freeman
2.8.1 Introduction
[Herbert Freeman 1974] Computer Processing of Line-Drawing Images. Computing Surveys.
Idées pour la compression de formes binaires :
- ne mémoriser que le contour ;
- à partir d'un point de départ du contour, on le parcourt en tournant autour de la forme ;
- on ne mémorise pour chaque point que la direction pour passer au suivant.
Directions de Freeman :
O --> x
| 5 6 7 3
v 4 P 0 2 P 0
y 3 2 1 1
Connexité : C8 C4
Exemple : A = point de départ
A X X X . . 2 4 4 4 . . 1 2 2 2 . .
X X X X X X -> 2 X X X 5 4 1 X X 3 2 2
X X X X X X 1 X X X 0 6 0 1 X 0 0 3
. X X X . . . 0 0 7 . . . 0 0 3 . .
On obtient une chaîne de Freeman s à partir du point de départ A :
- C8 : s = { 2, 2, 1, 0, 0, 7, 0, 6, 4, 5, 4, 4, 4 }
- C4 : s = { 1, 1, 0, 1, 0, 0, 3, 0, 0, 3, 2, 2, 3, 2, 2, 2 }
Compression :
- pour C8 : 3 bits/direction : ici 13*3 = 39 bits
- pour C4 : 2 bits/direction : ici 16*2 = 32 bits
On note : \(N_k(P,d)\) le \(k\)-voisin de \(P\) (\(k\) = 4 ou 8) dans la direction de Freeman \(d\).
Tourner dans le sens croissant à partir de la direction j pour C8 :
pour i = 0 .. 7 : d = (j+i) % 8
idem dans le sens décroissant :
pour i = 0 .. 7 : d = (j+8-i) % 8
Calculer les coordonnées des voisins parcourus en tournant à partir
de la direction j pour C8 :
int nx8[] = { 1, 1, 0, -1, -1, -1, 0, 1},
ny8[] = { 0, 1, 1, 1, 0, -1, -1, -1};
for (int i = 0; i < 8 ; i++) {
int d = (j+i) % 8;
int xV = xP + nx8[d],
yV = yP + ny8[d];
...
}
2.8.2 Reconstruction d'un contour
Donnée : une chaîne de Freeman s
Pour C8 dans une image I :
int nx8[] = { 1, 1, 0, -1, -1, -1, 0, 1},
ny8[] = { 0, 1, 1, 1, 0, -1, -1, -1};
x = xA, y = yA; // P : (x,y)
pour i de 0 à longueur(s)-1 :
marquer I(x,y)
x += nx8[s[i]], y += ny8[s[i]] // P := N8(P,s[i])
- Assertion :
- Après la boucle on a
x == xAety == yA.
On peut donc vérifier que s représente un contour fermé sans utiliser d'image.
Pour C4 : idem avec
nx4[] = { 1, 0, -1, 0},
ny4[] = { 0, 1, 0, -1};
2.8.3 Opérations
-
translation : translater le point de départ A ; s inchangé
-
rotation à 90° :
r[i] = (s[i] +2) % 8 pour C8 r[i] = (s[i] +1) % 4 pour C4 -
rotation à -90° :
r[i] = (s[i] +8-2) % 8 pour C8 r[i] = (s[i] +4-1) % 4 pour C4 -
symétries :
pour C8 pour C4 centrale r[i] = (s[i]+4) % 8 r[i] = (s[i]+2) % 4 horizontale r[i] = (8-s[i]) % 8 r[i] = (4-s[i]) % 4 verticale r[i] = (8+4-s[i]) % 8 r[i] = (4+2-s[i]) % 4 -
inversion de s = parcours dans le sens inverse :
m = longueur(s) r[i] = (s[m-i] +4) % 8 pour C8 r[i] = (s[m-i] +2) % 4 pour C4
2.8.4 Périmètre et aire
On note Pol(s) le polygone dont les sommets sont générés par la chaîne de Freeman s pour la connexité choisie.
Sommets centrés sur les pixels → résultat \(\neq\) nombre de pixels de la forme
L'aire et le périmètre de Pol(s) sont indépendants du point de départ.
-
Périmètre de Pol(s) pour C4 :
chaque déplacement a une longueur de 1 → périmètre = longueur(s) -
Périmètre de Pol(s) pour C8 :
longueur déplacement horizontaux et verticaux = 1
longueur déplacement diagonaux = \(\sqrt 2\)
→ périmètre = \(\#\{\) s[i] pair \(\} + \#\{\) s[i] impair \(\}\times\sqrt 2\) -
Aire de Pol(s) pour C4 : algorithme de [Ballard et Brown 1982, p.236] (en Python)
def calculer_aire_c4 (s) : a = 0 ; y = 0 for d in s: if d == 0 : a += y elif d == 1 : y += 1 elif d == 2 : a -= y elif d == 3 : y -= 1 print("d =", d, " a ->", a, " y ->", y) return aExemple : 1 2 2 2 . . 1 X X 3 2 2 0 1 X 0 0 3 . 0 0 3 . . >>> s = [ 1, 1, 0, 1, 0, 0, 3, 0, 0, 3, 2, 2, 3, 2, 2, 2 ] >>> calculer_aire_c4 (s) -
Aire de Pol(s) pour C8 : algorithme de [Trouillot 2008, p.35] (en Python)
def calculer_aire_c8 (s) : a = 0 ; y = 0 for d in s: if d == 0 : a += y elif d == 1 : a += y +1/2 ; y += 1 elif d == 2 : y += 1 elif d == 3 : a -= y +1/2 ; y += 1 elif d == 4 : a -= y elif d == 5 : a -= y -1/2 ; y -= 1 elif d == 6 : y -= 1 elif d == 7 : a += y -1/2 ; y -= 1 print("d =", d, " a ->", a, " y ->", y) return aExemple : 2 4 4 4 . . 2 X X X 5 4 1 X X X 0 6 . 0 0 7 . . >>> s = [ 2, 2, 1, 0, 0, 7, 0, 6, 4, 5, 4, 4, 4] >>> calculer_aire_c8 (s)
2.8.5 Autres opérations
- calcul d'intégrale, de moments d'inertie, de résidus (chemin minimal)
- distances
- centre de masse
- diamètres apparents maximal, minimal et moyen
- rectangle englobant d'aire minimale
- dimension fractale
- coefficients de symétrie ou d'asymétrie
- axes principaux d'inertie
- homothéties, rotations
- appartenance d'un point à un forme
- intersection et union de formes
- comparaison de formes : distance de Hausdorff, de Asplünd
- morphologie mathématique : dilatation, érosion
- etc
- Voir :
- [Trouillot 2008] : "Étude de paramètres géométriques à partir du code de Freeman", Xavier Trouillot, Thèse École des mines de St-Étienne, 2008.
2.9 Suivi de contour
Algorithme de suivi de contour :
- détecte tous les contours dans une image
- marque chaque point de contour avec le numéro de son contour
- calcule les codes de Freeman de chaque contour
Valeurs des pixels :
I[x,y] = 0 : fond
255 : forme, non encore traité
!= : forme, contour détecté, numéro du contour
Algorithme (pour C8) :
effectuer_suivi_contours_c8 (I) :
num_contour = 1
pour chaque ligne y : 0 .. nlig-1
pour chaque colonne x : 0 .. ncol-1
// recherche du premier point du prochain contour
// = un point à 255 avec un 4-voisin à 0 ou situé au bord
// la direction de départ dir sera en direction du 0 ou du bord
si I[x,y] == 255 :
dir = -1 // pas trouvé
si x == ncol-1 ou I[x+1,y] == 0 : dir = 0
sinon si y == nlig-1 ou I[x,y+1] == 0 : dir = 2
sinon si x == 0 ou I[x-1,y] == 0 : dir = 4
sinon si y == 0 ou I[x,y-1] == 0 : dir = 6
si dir >= 0 : // trouvé -> point du contour
suivre_un_contour_c8 (I, x, y, dir, num_contour)
num_contour++
si num_contour == 255 : num_contour++ // saute 255
// sinon c'est un point intérieur
suivre_un_contour_c8 (I, xA, yA, dirA, num_contour) :
// 1) recherche de la direction d'arrivée sur xA,yA :
// on tourne autour de xA,yA dans le sens croissant à partir de dirA
pour i = 0 .. 7 :
d = (dirA+i) % 8
si N8(A,d) est dans l'image et > 0 :
dir_finale = (d+4)%8 ; stop
// 2) suivi et marquage du contour
x = xA, y = yA, dir = dir_finale
faire
I[x,y] = num_contour
// direction de départ pour chercher le point suivant
dir = (dir+4-1) % 8
// on tourne autour de x,y dans le sens décroissant à partir de dir
pour i = 0 .. 7 :
d = (dir+8-i) % 8
Q = N8((x,y),d)
si Q est dans l'image et > 0 :
x,y = Q ; dir = d
// emplacement pour mémoriser d dans la chaîne de Freeman
stop
si i == 8 : retour // aucun point trouvé -> point isolé
tant que non (x == xA et y == yA et dir == dir_finale)
Remarques :
-
ça marche aussi sur les trous : le contour sera orienté dans le sens inverse
X X X X X X X X X X X X B C X X X X X X X . . X X X X X X A . . D E X X X X . . . . . X X -> X M . . . . . F X X X X . . . . X X X X L . . . . G X X X X X X X X X X X X X K J I H X X -
des points peuvent être parcourus plusieurs fois dans un même contour
-
des points peuvent être communs à plusieurs contours (extérieur et trou qui se touchent)
→ les points seront renumérotés avec le dernier contour traité