Embed Size (px)
Citation preview
Table des matières 1
Université Sidi Mohamed Ben Abdellah 2008/2009
Faculté des Sciences DM Fès
LESSI
Methode des Moments en Traitement et
Analyse d’Images
Master M3I
Pr. H. QJIDAA
Table des matières 2
Table des matières
Chapitre I Théorie des Moments 6
1 Introduction 6
2 Les Moments : définitions et propriétés 7
2.1 Les moments multidimensionnels 7
2.2 Les moments tridimensionnels 9
2.3 Moments orthogonaux et analyse d’image. 10
2.4 Reconstruction d’image par la méthode des moments. 13
2.5 Algorithmes rapide de calcul des moments 14
3 Types d’erreur du processus de reconstruction 17
3.1 Erreur d’échantillonnage 17
3.2 Erreur de quantification 17
3.3 Erreur de troncature à un ordre θ 17
3.4 Erreur d’approximation de l’intégrale 19
4 Conclusion 28
Chapitre II Reconstruction d’image par chevauchement de blocks via la méthode des
moments optimisés par le PME 30
1 Introduction 30
2 Problématique 31
3 Méthode de reconstruction globale 34
4 Reconstruction d’image par Block (Block Based Reconstruction Method : BBRM) 35
4.1 Reconstruction par moments de Legendre 36
4.2 Reconstruction par Moments de Zernike 37
4.3 Sélection de l’Ordre optimale des moments via PME 39
4.4 Algorithme de reconstruction par block utilisant le PME 41
5 La méthode de reconstruction basée sur les blocks chevauchés (Lapped Block Based
Reconstruction Method :LBBRM) 42
1.1 Elimination de l’effet de block 42
5.1 Algorithme de reconstruction par block chevauchées utilisant le PME 43
Table des matières 3
5.2 Comparaison entre le chevauchement par les moments de Legendre et Zernike 47
6 Résultats Expérimentaux 47
7 Conclusion et perspective 57
Chapitre III Squelettisation des Images Binaires bruitée par la méthode des moments 58
1 Introduction 58
2 Espace continu : notion topologique 59
2.1 Distance 59
2.2 Norme euclidienne 60
2.3 Boule ouverte 60
2.4 Ensemble ouvert, fermé 61
2.5 Ensemble borné 61
2.6 Notion d’intérieur et de fermeture 61
2.7 Notion de contour 61
2.8 Notion de forme 62
3 Définitions du squelette 63
3.1 Squelette par feu de prairie 63
3.2 Squelette par boule maximal 64
3.3 Squelette pondéré (Transformé de l’Axe Médian) 65
4 Propriétés des Squelettes 67
4.1 Invariance 67
4.2 Unicité et réversibilité 67
4.3 Description hiérarchique 68
4.4 Epaisseur 68
4.5 Homotopique 69
4.6 Tolérance au bruit 70
5 Espace discret : Notion de topologie pour les images binaire. 70
5.1 Notion de Topologie 71
5.2 Discrétisation des images, choix du maillage 71
5.3 Définitions fondamentales de l’espace discret 72
6 Methodes de squelettisation 80
Table des matières 4
6.1 Méthodes continue 80
6.2 Méthodes Discrètes. 83
Bibliographie 101
Chapitre II 5
Chapitre II 6
Chapitre I Théorie des Moments
1 Introduction
Depuis son introduction en 1962 pa Hu [62], la théorie des moments a été utilisée comme
descripteur de forme dans une variété d’application concernant l’analyse de l’image, a savoir
reconnaissance de forme [Belkasim 91], [Flusser 93], classification [Heywood 95], détection
de contour [Ghosal 93], vision par ordinateur [Markandey 92], et en fin la compression de
donnée [Hsu 93]. Dans toute ces applications les moments géométrique ainsi leurs extensions
dans la forme radial et complexe, joue un rôle très important dans la caractérisation des
formes, et dans l’extraction des attributs.
Historiquement, le premier papier significatif utilisant la théorie des moments invariants, dans
la reconnaissance de forme, a été publié par Hu [Hu 62]. Dans cette étude, Hu génère un
ensemble de moments invariants à partir des moments géométriques. Ces moments invariants
sont utilisés comme attributs globaux pour la reconnaissance automatique des caractères. Par
la suite, la méthode basée sur les moments géométrique invariant, a été appliquée à la
reconnaissances des formes par Alt [Alt 62], l’identification des avions par Dudani [Dudani
77], l’identification des navires par Smith [Smith 71], analyse des scènes par Wong [Wong
78]. En 1980 , Sadjadi [Sadjadi 80] étend la définition des moments en trois dimensions, et
génère les moments invariant correspondants. Teague [Teague 80] a étendu l’idée de Hu au
concept des bases des moment orthogonaux. Abu-mustapha [Abu-mustapha 85] introduit la
notion des moments complexes pour obtenir de manière simple les moments invariant. Teh et
Chin [Teh 88] exposent une étude détaillée sur différents type de moments dont :
géométrique, Legendre, Zernike, Pseudo-Zernike, Rotationelle et Complexe. Une
comparaison a ensuite été établie en terme de qualité de représentation, redondance de
l’information et sensibilité au bruit, avec des résultats analytiques et expérimentaux.
Récemment, une étude faite par Liao et Pawlack [Liao 96] et [Liao 98] a mis en examen
Chapitre II 7
l’analyse de l’erreur de reconstruction, où plusieurs techniques on été utilisés pour augmenter
la précision d’approximation. Mukundan et al dans [Mukundan 01] utilisent les moments de
tchybechev pour des applications d’analyse d’images.
Dans ce chapitre, nous allons exposer la théorie des moments à travers quelques définitions et
propriétés des différentes bases. En suite, nous allons développer une nouvelle méthode
d’estimation des moments de Zernike basée sur l’intégration par la méthode Simpson.
2 Les Moments : définitions et propriétés
Nous allons définir, dans un premier temps, les moments multidimensionnels. Ensuite, nous
donnons la définition des moments tridimensionnels. Les moments orthogonaux seront définis
dans le quatrième paragraphe.
2.1 Les moments multidimensionnels
Soit ),...,(1 n
xxρ une densité définie dans un espace n
R=Ω où chaque point X de cet espace a
pour composante ),...,(1 n
xx .
Les moments d’ordre )...(21 n
NNN +++ de la densité ),...,(1 n
xxρ , supposée presque continue à
support borné sont définis par :
nn
N
n
N
n
nNN dxdxxxxx
NNM n
n...)...(......
2
)12)....(12(111
1,...,
1
1ρ∫ ∫
+∞
∞−
+∞
∞−
++= (2.1)
Où ∞= ,.......,1,0)...(21 n
NNN
Fonction caractéristique
la fonction caractéristique d’une densité ),...,( 1 nxxρ est donnée par :
321321332211321 ),,()exp(),,( dxdxdxxxxxuxuxuuuuM ρ++= ∫ ∫ ∫+∞
∞−
+∞
∞−
+∞
∞−
(2.2)
Chapitre II 8
qui peut être développé en série sous la forme :
321321332211
0321
),,()(!
),,( dxdxdxxxxxuxuxupiuuuM
pp
p
ρ++= ∫ ∫ ∫ ∑+∞
∞−
+∞
∞−
+∞
∞−
∞
=
(2.3)
Moments centraux
les moments centraux multidimensionnels n
NN ,.....,1
Γ d’ordre n
NN ++...1
sont définis par :
nn
N
nn
N
NN dxdxxxxxxx n
n...)...().(...).(... 1111,...,
1
1ρ−−=Γ ∫ ∫
+∞
∞−
+∞
∞−
(2.4)
où
0,...,0
1,....,0,0
0,...,0
0,....,1,02
0,...,0
0,....,0,11 .....;;;
M
Mx
M
Mx
M
Mx n ===
0,...,0M : est le moment d’ordre zéro obtenu pour 0...21 ==== nNNN
0,...,1M : est le moment d’ordre un obtenu pour 0...1 21 ==== nNNetN
0...,1,0M : est le moment d’ordre un obtenu pour 0...1,0321
=====n
NNetNN
1,...,0M : est le moment d’ordre un obtenu pour 10... 11 ==== − nn NetNN
les moments centraux ne changent pas par translation des coordonnées. En effet, considérons
la translation linéaire de vecteur T
n)...(
1αα qui transforme ),...,(
1 nxx en ),...,( ''
1 nxx suivant le
système :
+=
+=
nnn xx
xx
α
α
'
11'1
.
.
.
Chapitre II 9
étant donné que :
−=+−+=−
−=+−+=−
nnnnnnnn xxxxxx
xxxxxx
)()(
.
.
.
)()(
''
111111
'
1'1
αα
αα
Alors, les moments centraux nNN ,.....,
'1Γ calculés après transformation en utilisant les
coordonnées ),...,( ''
1 nxx sont égaux à ceux calculés en utilisant les coordonnées ),...,(
1 nxx
notés n
NN ,.....,1
Γ .
Vue cette propriété d’invariance, les moments centraux seront souvent utilisés en prenant
comme origine des coordonnés, le centroide de la densité donné par T
nxx ),....,( 1 .
2.2 Les moments tridimensionnels
Les moments tridimensionnels d’ordre (321
NNN ++ ) d’une densité ),,(321
xxxρ sont définis en
termes d’intégrale de Riemann :
321321321,, ),,(321
321dxdxdxxxxxxxM
NNN
NNN ρ∫ ∫ ∫+∞
∞−
+∞
∞−
+∞
∞−
= (2.5)
où ),,(321
xxxρ est continue par morceaux et bornée dans une région de R3.
Fonction caractéristique
La fonction caractéristique de la densité ),,(321
xxxρ est définie par :
321321332211321 ),,()exp(),,( dxdxdxxxxxuxuxuuuuM ρ++= ∫ ∫ ∫+∞
∞−
+∞
∞−
+∞
∞−
(2.6)
en développant l’exponentielle en série, nous aurons :
Chapitre II 10
3213213322110
321 ),,()(!
),,( dxdxdxxxxxuxuxup
iuuuM
pp
p
ρ++= ∫ ∫ ∫∑+∞
∞−
+∞
∞−
+∞
∞−
∞
=
(2.7)
En interchangeant l’intégration et la sommation, et en utilisant la définition des moments,
nous pouvons exprimer la fonction caractéristique comme étant une série de
polynômes homogènes:
),,(!
),,( 3210
321 uuuHp
juuuM p
p
p
∑∞
=
= (2.8)
321
321 321,,321
321 !!!
!),,( NNN
NNNp uuuMNNN
puuuH ∑∑∑= (2.9)
Les moments centraux
Les moments centraux tridimensionnels d’ordre 321 NNN ++ sont définis par :
321321332211,, ),,()()()( 321
321dxdxdxxxxxxxxxx
NNN
NNN ρ−−−=Γ ∫ ∫ ∫+∞
∞−
+∞
∞−
+∞
∞−
(2.10)
Où
0,0,0
1,0,03
0,0,0
0,1,02
0,0,0
0,0,11 ;;
M
Mx
M
Mx
M
Mx ===
Donnent le centroide de la fonction densité ρ . Ces moments centraux sont aussi invariants par
translation.
2.3 Moments orthogonaux et analyse d’image.
C’est Teague [Teague 80] qui introduit les moments orthogonaux, avec une propriété
supplémentaire qui est le minimum de redondance d’information dans un ensemble de
moments. Dans le même axe, des recherche considérable ont été réalisé sur les moments de
Legendre est de Zernike [Mukundan 95], [Teh 88].
Chapitre II 11
Etant donné que nous ne nous intéresserons qu’à l’image de dimension deux, seuls les
moments bidimensionnels seront traités par la suite. Nous commençons par définir quelques
bases orthogonales génératrices de moments orthogonaux. Avant d’aborder leurs différents
types d’erreur de reconstructions.
2.3.1 Moments géométriques
Les moments géométriques ne sont pas des moments orthogonaux, étant donnée que la base
génératrice des monômes ne sont pas orthogonaux.
Les moments géométriques d’ordre (p+q) d’une fonction f(x,y) sont définis par :
∫ ∫+∞
∞−
+∞
∞−
= dxdyyxfyxMqp
qp ),(, (2.11)
où ∞= ,...,2,1,0,qp
on suppose que f(x,y) est une fonction continue par morceaux à support borné.
L’expression (2.43) a la forme d’une projection de la fonction f(x,y) sur le monôme qp
yx . la
base des monômes qp
yx est complète, mais elle n’est pas orthogonale.
2.3.2 Moments de Legendre
Les moments de Legendre d’ordre (p+q) sont définis par :
∫ ∫+∞
∞−
+∞
∞−
=λ dxdyyxfyPxPqpqp
),()()(,
(2.12)
où ∞= ,...,2,1,0,qp les polynômes de Legendre )(xPp
forment une base complète orthogonale
dans l’intervalle [-1,1] [Teh-88] :
pqqpp
yPxP δ12
2)()(
1
1 +=∫
−
(2.213)
Chapitre II 12
le polynôme de Legendre d’ordre p est donné par :
p
p
p
pp xdx
d
pxP )1(
!2
1)( 2 −= (2.14)
Les moments de Legendre et les moments géométriques sont reliés par :
jijq
p
i
q
jipqp
Maa,,
0 0,, ∑∑
= =
=λ (2.15)
2.3.3 Moments de Zernike
La fonction de Zernike d’ordre (p,q) est définie par
1,)exp()(),( 22,, ≤+= yxjqRyxV qpqp φρ (2.16)
Où p=0,1,…., ∞
q prend des valeurs positives ou négatives telles que qp − pair et pq ≤ .
ρ : Longueur du vecteur à partir de l’origine.
φ : Angle entre ρ et l’axe des x.
la forme des polynômes de Zernike est
∑−
=
−
−−
−+
−−=
2/
0
2
,
)2
()!2
(!
)!()1()(
qp
s
sps
qp
sqp
sqp
s
spR ρρ (2.17)
Ces polynômes sont orthogonaux et satisfont à la relation::
',',',',
*
)1(),(),( qqpp
D
qpqp pdxdyyxVyxV δδ
π
+=∫∫ (2.18)
Avec ba
Sinonba
== 10,δ
Les moments de Zernike sont alors la projection de la fonction image sur ces fonctions orthogonales:
dydxyxfp
A
yx
qpqp V∫∫≤+
+=
1,
*
,22
),(),()1(
φρπ
(2.19)
Chapitre II 13
2.4 Reconstruction d’image par la méthode des moments.
2.4.1 Moment de Legendre
Par principe d’orthogonalité, la fonction image f(x,y) peut être développé en série infinie en
termes de polynômes de Legendre dans le carré [-1,1]:
)()(4
)12)(12(),( ,
0 0
yPxPqp
yxf qpqp
p q
λ∑∑∞
=
∞
=
++= (2.20)
Les moments de Legendre qp ,λ sont calculés sur le même carré.
si ces moments sont calculés à un ordre θ≤ sont donnés, la fonction image f(x,y) peut être
estimé par une fonction continue qui n’est qu’une série tronquée :
)()(),(0 0
yPxPyxf qqp
p
p
q
qp −= =
−∑∑=θ
θ λ (2.21)
2.4.2 Moment de Zernike
Grâce au principe d’orthogonalité, la fonction image f(x,y) peut être développé en série infinie
en termes de polynômes de Zernike dans le cercle unité:
evenqpVAyxfp
qp
p
pq
qp −= ∑ ∑∞
= −=
,),(),(0
,, φρ (2.22)
où les moments de Zernike sont évalué sur le disque unité.
Si le développement en série set tronqué à un certain ordreθ , l’approximation de la fonction
image f(x,y) sera donnée par :
evenqpVAyxfp
p
pq
qpqp∑ ∑= −=
−=θ
θ φρ0
,, ,),(),( (5.23)
Chapitre II 14
2.5 Algorithmes rapide de calcul des moments
2.5.1 Moments de Legendre
Dans cette section on présente la méthode de calcul rapide des moments de Legendre
[Mukundan 98]
Cas images binaires
Pour les images binaires l’intégrale double donnant les moments de Legendre peut être
convertit en une intégrale au long du contour en utilisant le théorème de green [Mukundan-
98], les moments de Legendre définis dans (2.44) deviennent :
dyyPxPxxPp
qpq
C
ppqpC )())()((
)1(4
)12)(12(1, ∫ −−
+
++=λ (2.46)
on obtient finalement
∑−
=++
−+
++=
1
11, )(
)1)(1(4
)12)(12( n
k
kkqpC TT
Np
qpλ (2.48)
où )]()()()()[( 11112122 kpkpkkpkpkkqk xPxPxxPxPxyPT −− +−−= et N étant le nombre de pixels
suivant l’axe des x.
cas des images niveaux de gris
L’algorithme rapide de calcul des moments de Legendre en utilisant la formule de récurrence
est donné par [Mukundan 95]:
Chapitre II 15
Algorithme 1.1 : Algorithme rapide de calcul de Moment de Legendre
1) calcul et sauvegarde des polynômes de Legendre
pour i= 1…N
x=(2i/N)-1
P(0,i)=1
P(1,i)=x
Pour p=2…max
P(p,i)=(2p-1) x P(p-1,i)-(p-1) P(p-2,i)/p
Fin
Fin
2) calcul des moments de Legendre
pour p= 0…max
pour q=0…max
somme=∑∑i j
jifjqPipP ),(),(),(
2, )1/()12)(12( −++= Nsommeqpqpλ
Fin
Fin
Avec max l’ordre maximum des moments à calculer
N la taille de l’image
2.5.2 Moments de Zernike
Cas binaire
Cette méthode utilise l’intégration sur le contour au long des points de bord de l’objet. En
coordonnés polaires les points de bord de l’image peuvent être représentés
par πφφ 20: ≤≤r . La formule obtenue est [Mukundan 95]:
Chapitre II 16
∑∑=
+
=
∆−+
+=
π
φφ φφφ
π
2
0
2,, ))sin()(cos()
2(
1mimr
k
BpA
kn
mk
mknC
qp (2.48)
où φ∆ est la différence entre points de bord successifs, avec
)!
2()!
2()!
2(
)!2
()1( 2/)(
,, mkmkkn
kn
B
kn
kmn −+−
+−
=
−
(2.49)
Cas multi-niveaux
Dans [Mukundan 95], les auteurs utilisent une transformation des coordonnés rectangulaires
en coordonnés circulaires (rectangulaire - circulaire). Cette transformation est définie par
deux variables γ (rayon du cercle) et ς (l’indice de la position du pixel sur le cercle) tel que :
yximum ,max=γ
Si γ=x , alors γ
γςxy
y
yx +−= )(2
Si γ=y , alors γ
ςxy
y −= 2
En utilisant cette transformation les deux composantes réelle (R) et imaginaire (I) des
moments de Zernike sont données par :
),(4
cos222 8
1
2/
1,2
)(, φ
γ
ςπγ γ
ςγ
rfq
NR
N
pA
N
qp
R
qp ∑∑==
+= (2.50)
),(4
sin2)22( 8
1
2/
1,2
)(, φ
γ
ςπγ γ
ςγ
rfq
NR
N
pA
N
qp
I
qp ∑∑==
+−= (2.51)
La méthode circulaire permet de calculer qpR , (N/2) fois, alors qu’elle nécessite (N2)
opérations dans le cas rectangulaire.
Chapitre II 17
3 Types d’erreur du processus de reconstruction
3.1 Erreur d’échantillonnage
La définition des moments suppose un espace de coordonnées continu, dans la pratique
l’espace des coordonnées image est échantillonné en un ensemble discret de points sur le plan
image
Une étude de cette erreur, pour les moments géométriques, a été réalisée par Teh [Teh 86] où
l’auteur utilise deux type mailles hexagonale et rectangulaire
3.2 Erreur de quantification
La définition des moments suppose également une fonction intensité image f(x,y) continu,
cependant les données images consistent en des valeurs niveaux de gris quantifiées
généralement de 0 à 255, pour les moments géométriques invariants Teh et Chin dans [Teh
86] ont réalisé une comparaison des erreurs de quantification obtenue avec différents niveaux
de quantification (2, 4, 8, et 16 niveaux de gris).
3.3 Erreur de troncature à un ordre θ
Teh et chin dans [Teh 88] ont exprimé l’erreur normalisée due à un ordre θ comme étant
∑∑
∑∑ θ
∧
−
=θ
i j
i j
jif
jifjif
e 2
2
2
]),([
)],(),([)( (2.38)
Avec 1)(02
≤θ≤ e
Chapitre II 18
Cas non bruité
Pour les moments de Legendre, (2.70) devient
∑∑∫ ∫= = ++−
−=θ λ
θ0 0
,2
22
)12)(122(
4)],([)(
p
p
q
qp
Lqqp
dxdyyxfe (2.39)
Pour les moments de Zernike
∑ ∑∫ ∫=
≤
−
+−=
θπ πθθθ
0
2
,2
0
21
0
2
)1()],([)(
p
pq
qp
Z
ql
paireqp
p
Adrdrrfe (2.40)
les auteurs ont utilisé pour l’étude de l’erreur de reconstruction un champ aléatoire homogène
de moyenne nulle. Les résultats obtenus montre que l’erreur de reconstruction d’une fonction
image décroît avec l’augmentation de l’ordre θ .
Cas bruité
Dans le cas d’un champ aléatoire homogène corrompu par un bruit blanc additif de moyenne
nul non corrélé avec f(x,y) , l’erreur de troncature s’exprime par :
222 )()( σθεθζ totalN+= (2.41)
où 2
σ est la variance du bruit , )(2
θε est l’erreur de reconstruction dans le cas non bruité
totalN nombre de moments utilisé
Pour les moments de Legendre :
2
)2)(1( ++=
θθtotalN (2.42)
Pour les moments de Zernike [Zenkouar 99] :
pairestSiN θθ
θ4
)2( 2+= (2.44)
Chapitre II 19
impairestSiN θθθ
θ 4
)3)(1( ++= (2.45)
Les résultats montrent que l’erreur de reconstruction pour les images bruitées atteint une
valeur minimale pour un ordre donné puis l’erreur commence à croître en fonction de l’ordre.
Cette étude permet de conclure que les moments d’ordre élevé sont plus vulnérables au bruit
additif. Cependant aucune étude n’a été faite concernant les bruits non additifs à savoir les
bruits contextuels et les bruits dépendant du signal
3.4 Erreur d’approximation de l’intégrale
Cas des Moments de Legendre
Si on considère le cas discret de la fonction intensité image donnant lieu aux échantillons
),(ji
yxf répartis selon une maille rectangulaire de taille (M,N) de pixels, alors l’équation
(2.12) représentant les moments de la fonction continue f(x,y) peut être approchée en terme de
sommation par la formule [Liao 96] :
yxyxfyPxPqp
jijq
M
i
N
jip
qp ∆∆++
=λ ∑∑= =
),()()(4
)12)(12(
1 1,
~
(2.24)
avec 1−
−=∆ii
xxx et 1−
−=∆jj
yyy sont les intervalles d’échantillonnage suivant les directions x
et y.
d’après [Liao-96] qp,
~
λ n’est pas une bonne approximation de qp,λ , en particulier pour les
ordres (p+q) élevés, ce qui implique tout naturellement une mauvaise approximation de la
fonction de densité lors de la reconstruction. Une approximation qui apporte plus de précision
par discrétisation de l’espace d’intégration lors du calcul du moment et qui suppose que f(x,y)
est constante par morceau sur l’intervalle ]2[,2[]2[,2[ yy
yyxxxxx jjii
∆−∆−∆+∆− est
donnée par la formule
Chapitre II 20
),(),(1 1
,, ji
M
i
N
j
jiqpqp yxfyxH∑∑= =
∧
=λ (2.25)
où dydxyPxPqp
yxH
xx
xx
yy
yy
qpjiqp
i
i
j
j
)()(4
)12)(12(),(
2
2
2
2
, ∫ ∫∆+
∆−
∆+
∆−
++= (2.26)
représente l’intégration du polynôme autour du pixel ),( ji yx
cas des Moments de Zernike
Dans le cas d’une image discrète l’intégrale représentant les moments de Zernike q,p
A est
remplacée par une sommation [Liao 98]
∑∑+
=x y
qpqp Vyxfp
A ),(),()1( *
,,
~
φρπ
, )1( 22 ≤+ yx (2.27)
dans une étude faite par Liao et Pawlak dans [Liao 98], on a montré que l’approximation
qpA
,
~
n’est pas une bonne estimation de qp
A,
, les auteurs ont donc proposé une nouvelle
approximation se basant sur la méthode d’intégration cubature, la version modifiée des
moment de Zernike est donnée par :
1,),(),(1 22
,, ≤++
= ∑∑∧
jijiqp
x y
jiqp yxyxHyxfp
Ai j
π (2.28)
Avec dydxVyxH
xx
xx
yy
yy
qpjiqp
i
i
j
j
∫ ∫∆+
∆−
∆+
∆−
=
2/
2/
2/
2/
,*
, ),(),( φρ (2.29)
Contrairement aux polynômes de Legendre qui sont separables vis a vis de leurs variables.
Les polynôme de Zernike sont des fonctions bidimensionnelles non separables en ρ et φ .
Par conséquent réduire l’erreur d’approximation lors du calcul des moments de Zernike est
une tache plus difficile par rapport à celle des moments de legendre. Pour le calcul de
l’intégrale double dans (2.29) Liao et Pawlak utilisent une formule de cubature
Chapitre II 21
multidimensionnelle. Pour avoir une bonne précision de l’estimation, on doit théoriquement
incrémenter le nombre de nœuds dans chaque pixel afin de réduire l’erreur d’approximation
lors du calcul de ),(, jiqp yxH [Engles 80].
3.4.1 Approximation par méthode de cubature
La formule de cubature n-dimensionnelle utilisant le développement de Taylor de la
fonction ),( yxf est donné par :
])()()(
)([)!1(
1
.......)()()()()()(
1
11
11
0
1
11 1
∑∑
∑∑ ∑
=
−−
−−
−−
=
−
== =
−−∂∂
∂
−
+−+−+=
n
i
jjn
iijjn
nn
j
n
j
n
i
iiy
n
i
n
i
iixin
byaxAyx
f
n
byAfaxAfAffC
α
ααα
(2.30)
où Ω∈= ),( baTα
les poids i
A , pour tous les nœuds à l’intérieur de chaque pixel, peuvent être obtenus par
résolution du système d’équations linaires :
nkjyxIyxAn
i
j
i
jkj
i
jk
ii ≤==∑=
−Ω
− ,.....,1,0,1
(2.31)
où n est le nombre de nœuds dans Ω et ∫Ω
Ω Ω= dyxfI ),(
On peut ainsi obtenir la formule de cubature 5-dimensionnelle (Figure 2.1a) par le
système d’équation (2.31) en prenant 2≤j
))0,5.0()5.0,0()0,5.0()5.0,0()0,0((3
4)(5 −+−+++−= ffffffC (2.32)
le nombre de nœuds dans chaque pixel peut être incrémenté d’avantage pour réaliser une
meilleure précision, on peut utiliser par exemple la formule cubature 13-dimensionnelle
[Liao 93] [Liao 98] (Figure 2.1b) :
Chapitre II 22
[ ](
[ ] [ ]))1,1()1,1()1,1()1,1(8)0,1()1,0()0,1()1,0(9
)5.0,5.0()5.0,5.0()5.0,5.0()5.0,5.0(16)0,0(12045
1)(13
−+−−+−++−+−++
−−+−−+−++=
ffffffff
ffffffC (2.33)
Figure 2.1 : Représentation de deux différentes formule de cubature. (a) 5-dimensionnelle. (b) 13- dimensionnelle.
Les inconvénients majeurs de cette méthode d’approximation sont :
1- Le choix de la position des nœuds à utiliser pour approximer l’intégration
double.
2- Pour avoir une précision suffisante on doit théoriquement incrémenter le
nombre de nœuds dans chaque pixel. Cependant la complexité de l’algorithme
de calcul des poids d’intégration i
A par résolution du système d’équation
augmente en fonction du nombre de nœuds utilisés.
Pour remédier à ces problèmes, nous allons présenter dans la section suivante, une nouvelle
approche de calcul des moments de Zernike basée sur l’intégration par la méthode de
simpson.
3.4.2 Approximation des moments de Zernike par la méthode de Simpson 2D [Zenkouar
01]
Supposons que l’on veuille évaluer l’intégrale :
∫∫=R
R dydxyxfI ),( sur un domaine Byb;Axa ≤≤≤≤=R
Chapitre II 23
Définissons une maille rectangulaire sur R par division de l’intervalle [a,A] et [b,B] en deux
segment (Figure 2.2a) où :
Ahaxhaxax =+=+== 2,, 210 et Bhbyhbyby =+=+== 2,, 210
Avec 2
,2
bBk
aAh
−=
−=
Figure 2.2 : Illustration de la méthode Simpson. (a) division de R en rectangles (2x2). (b) division de R en rectangles (2nx2m).
On obtient :
∫∫ ∫ ∫=R
A
a
B
b
dyyxfdxdydxyxf ),(),( (2.34)
Utilisant la formule de quadrature de Simpson [Demidovitch 87], la relation (2.29) devient :
Chapitre II 24
∫∫ ∫ ++=R
A
a
dxdydxyxf ))yf(x,)y4f(x,)yf(x,(3
k),( 210
]dy)yf(x,dx)yf(x,4)yf(x,[3 2
A
a
10∫ ∫∫ ++=A
a
A
a
dxk
Par application de la formule de Simpson pour chaque intégrale, on obtient
])y,f(x16]),()y,f(x)y,f(x)y,4[f(x
)y,f(x)y,f(x)y,f(x)y,f(x[9
),(
1121121001
22200100
++++
++++=∫∫
yxf
hkdxdyyxf
R (2.35)
L’approximation obtenue dans (2.35) est appelée formule de Simpson de dimension 2D. Pour
permettre un meilleur niveau d’approximation on peut incrémenter le nombre de points de la
maille rectangulaire en divisant R en un système de rectangles (Figure 2.3b) où (2.35) est
appliquée pour chacun d’eux avec:
mbBk
naAh
2,
2−=−=
Finalement on obtient [Zenkouar 01]
∑∑= =
++++ ++++=n
i
m
j
jijijijiR ffffhk
I0 0
22,222,222,222,2 )[(9
]16)(4 12,1222,222,1212,222,12 ++++++++ ++++ jijijijiji fffff
où jiji fyxf ,),( = , )2.......0,(00
niaxhixxi
==+= et )2.......0,( 00 mjbykjyyi ==+=
Résultats expérimentaux.
Pour montrer l’apport de l’utilisation de l’approximation par méthode de Simpson en terme de
la réduction d’erreur d’approximation. Nous considérons une image constance ayxf =),( .
Chapitre II 25
Dans ce cas, tout les moments de Zernike sont nulles sauf aA =0,0 . La mesure suivante peut
être utilisée pour évaluer l’erreur d’approximation des moments de Zernike.
0,max
,max ≠== ∑∑∧
qpAEn
P q
qpn (2.36)
Une étude comparative est réalisée entre l’approximation proposée par la méthode de
Simpson et l’approximation par la méthode de cubature multidimensionnelle décrite dans
[Liao 98] et donnée par (2.33). Les résultats de la comparaison sont illustrés dans la figure
2.4 où les facteurs d’intégration numérique sont tels que n=m.
Figure 2.4. Erreur d’approximation normalisée obtenue par application de la méthode de cubature 13-dimensionnelles (a) et la méthode de Simpson avec n=5 (b) pour une image constante de taille (24x24).
Chapitre II 26
Figure 2.5 Erreurs d’approximation obtenue par application de la méthode de Simpson avec trois règles d’intégration n=5 (a), n=7 (b), n=10 (c) pour une image constante de taille (24x24).
Les figures 2.4 et 2.5 illustrent clairement la réduction significative de l‘erreur
d’approximation apportée par notre approche, comparée à la méthode de cubature.
Pour voir l’impact de cette nouvelle approximation sur la reconstruction, une comparaison est
effectuée en utilisant une image binaire représentant le caractère ‘0’ de taille (100x100) (Cf.
figure 2.6)
Figure 2.6. Image originale utilisée pour la reconstruction
La figure 2.7 montre la comparaison de la méthode Simpson proposée ayant les règles
d’intégration numérique n=5, n=10 avec la méthode de cubature en terme d’erreur moyenne
de reconstruction définie comme étant
∑∑= =
∧
−=M
i
N
j
jiji yxfyxfNM
MSE1 1
),(),(.
1 (2.37)
Chapitre II 27
Cette figure montre clairement la réduction de l’erreur de reconstruction ce qui implique une
meilleure approximation des moments de Zernike.
Figure 2.7. Erreurs de reconstruction obtenues par application de la méthode de Simpson avec deux facteurs d’intégration numérique n=5 (b), n=10 (c), et la méthode de cubature 13-Dimentionnelle (a).
Les figures 2.8 et 2.9 montrent les images reconstruites avec deux règles d’intégration
numérique ayant n=5 et n=10 respectivement. De gauche à droite les deux rangées montrent
la reconstruction du caractère ‘0’ pour les ordres 2, 4, 6, 8,10, 12, 14, 16, 18 et 20
respectivement.
Figure 2.8 : Images reconstruites utilisant la méthode Simpson avec la règle d’intégration numérique n=5.
Chapitre II 28
Figure 2.9 Images reconstruites utilisant la méthode Simpson avec la règle d’intégration
numérique n=10.
Les résultats obtenus par notre méthode, montre l’efficacité de la méthode proposé par rapport
à la méthode de cubature proposée par Liao [Liao98]. Ainsi, l’erreur d’estimation des
moments de Zernike est faible. Entraînant ainsi, une bonne qualité d’image lors du processus
de reconstruction.
4 Conclusion
Dans ce chapitre, nous avons introduit les concepts de base de la théorie des moments. En
suite, nous avons proposé une nouvelle méthode d’estimation des moments de Zernike basée
sur l’intégration par la méthode de Simpson. Cette méthode augmente la précision
d’approximation, ainsi que l’efficacité des moments de Zernike a généré une bonne qualité
des images reconstruites.
Cependant, la grande complexité des calculs des moments, et le temps de calcul qui croit
exponentiellement avec l’ordre des moments, rendent l’utilisation des moments pour des
applications en temps réelle très difficile. Dans le chapitre suivant, nous allons développer une
nouvelle méthode de reconstruction pour surmonter ce problème.
Chapitre III 29
Chapitre III 30
Chapitre II Reconstruction d’image par
chevauchement de blocks via la méthode des moments
optimisés par le PME
1 Introduction
Le problème majeur de l’utilisation des moments dans le cadre de l’analyse d’images, surtout
pour la reconstruction, est la grande complexité du calculs des moments et le temps de calcul
qui croit exponentiellement avec l’ordre des moments. Ce qui rend l’utilisation des moments
pour des applications en temps réelle très difficile.
Pour résoudre ce problème, nous proposons dans ce chapitre une nouvelle méthode, qui
s’articule sur la reconstruction d’images par blocks utilisant les moments orthogonaux
(Legendre et Zernike). L’utilisation de cette technique de block entraîne un phénomène
appelé : effet de block (artefact). Pour palier ce problème, on propose une nouvelle technique
basée sur une reconstruction par blocks chevauchés (lapped block reconstruction). Enfin, pour
le problème de la sélection de l’ordre optimale de reconstruction d’image, on propose le
Principe du Maximum d’Entropie (PME) comme critère de sélection. Notre principale
motivation de cette approche est de permettre la réalisation d’un algorithme de reconstruction
rapide et efficace applicable pour les problèmes réels d’analyse d’image.
Dans ce chapitre, premièrement, nous illustrons le dilemme lié au calcul des moments et nous
présentons les problèmes causés par la méthode de reconstruction globale (GRM). Puis nous
présentons la méthode de reconstruction par block contrôlée par le PME. Nous détaillons
ensuite la méthode LBBRM basée sur la notion du chevauchement des blocks. Finalement,
pour montrer les performances de notre algorithme de reconstruction, des résultats de
Chapitre III 31
simulation seront appliqués a deux type d’image binaire (clés de sol) et niveaux de gris
(LENA).
2 Problématique
Dans les dernières décennies, Les moments et fonction de moments ont été utilisés comme
attributs globaux invariants dans plusieurs champs d’application à savoir : la classification,
l’identification et l’analyse de scènes complexes ([Hu 61], [Hu 62], [Alt 62] [Prokop 92],
[Chong 03]).
Cependant, peu d’études on été menés pour des applications liée à la reconstruction des
images via les moments orthogonaux. Teh et Chin était parmi les pionniers dans l’utilisation
des moments pour la reconstruction, ils exposent dans [Teh 88] une étude détaillée sur
différents type de moments dont : géométrique, Legendre, Zernike, Pseudo-Zernike,
Rotationelle et Complexe. Une comparaison a ensuite été établie en terme de qualité de
représentation, redondance de l’information et sensibilité au bruit, avec des résultats
analytiques et expérimentaux. La conclusion tirée par les auteurs lors de cette étude est que en
général les moments orthogonaux sont bien meilleurs que les autres moments en terme de
qualité de reconstruction et redondance d’information.
Récemment une importante étude portant sur les moments, effectuée par Liao et Pawlak dans
[Liao 96] et [Liao 98] a mis en examen l’analyse de l’erreur de reconstruction. Dans cette
etude, plusieurs techniques on été utilisés pour augmenter la précision d’approximation, ainsi
que l’efficacité des différents moments en terme de reconstruction.
Cependant, on remarque que dans la plupart de ces études seules des images binaires et de
petites tailles sont utilisées pour illustrer les performances des algorithmes de reconstruction
utilisés. En effet, dans [Teh 88] Teh et Chin utilisent des images binaires de taille (64x64) et
dans [Liao 96] Liao et Pawlack utilisent des images de taille (24x24).
Si on utilise des images multi-niveaux et de taille plus importante, comme celles requises
dans des applications réelles, alors les moments d’ordre élevés seront nécessaires pour avoir
Chapitre III 32
une bonne reconstruction, ce qui impliquerait un très grand temps de calcul, et une erreur de
reconstruction élevée.
Nous constatons que le problème majeur lié a l’utilisation des moments pour la reconstruction
est le dilemme suivant : plus la taille des images multi-niveaux à reconstruire est grande, plus
le temps de calcul augmente et la complexité des calculs des polynômes de Legendre et de
Zernike croit de manière exponentielle avec l’ordre des moments [Mukundan 01].
Ce dilemme pose une limitation cruciale à l’utilisation de la théorie des moments pour des
exemples d’images réelles.
Afin de résoudre ce problème, nous proposons une approche permettant d’établir un
algorithme de reconstruction rapide et efficace dans le cas des images multi-niveaux de
grandes tailles, l’idée de base est d’avoir une bonne qualité de reconstruction par utilisation
seulement des moments d’ordre faible, et donc un nombre réduit de ces derniers. Cette
stratégie réside dans l’utilisation de polynômes d’ordre faible sur de petits intervalles, plutôt
que des ordres élevés sur un très grand intervalle.
Ainsi, l’image à reconstruire est partionnée en plusieurs ‘blocks’ de pixels qui seront ensuite
reconstruits séparément. C’est une approche purement locale, ce qui garantit une
reconstruction rapide et efficace avec une qualité supérieure.
Cette méthode garantit que si un block de reconstruction est affecté par une erreur de
reconstruction les blocks voisins ne le sont pas, ceci rend le traitement de l’erreur purement
local, ce qui préserve l’intégrité de l’image reconstruite. Cependant si des blocks adjacents
possèdent des erreurs de reconstruction de valeurs différentes, les bords des blocks deviennent
visibles, ce qui produit des lignes verticales et horizontales, affectant ainsi la qualité
subjective de l’image de sortie. C’est ce qu’on appelle dans la littérature l’effet de block
‘artifact‘ [Malvar 89]. Cet effet de block est d’autant plus visible pour les ordres de
reconstruction faibles, car l’erreur de reconstruction est très importante pour les moments
d’ordres faibles.
Chapitre III 33
Nous proposons ensuite une nouvelle approche pour éliminer l’effet de bord par utilisation
d’une méthode de reconstruction basée sur le chevauchement de blocks. Cette méthode
produit une qualité d’image objectivement et subjectivement élevée.
Pour le problème de sélection du nombre de moments optimal utilisé pour la reconstruction,
on introduit, comme critère de sélection, le principe de maximum d’entropie PME. Cette
technique automatique permet l’estimation de l’ordre optimale des moments directement à
partir de l’image reconstruite sans avoir besoin d’une connaissance à priori sur l’image
originale [Qjidaa 99a], [Robert 91].
En résumé, l’approche proposée dans le cadre de notre étude est une combinaison de la
méthode de reconstruction par blocks chevauchés avec le principe PME comme critère de
sélection.
Les plus important avantages qu’apporte notre méthode sont les suivants :
La réduction de l’espace de reconstruction, et donc de la quantité
d’information à traiter, ce qui implique une grande fiabilité au cours du
processus de reconstruction où seules les moments d’ordre faibles sont
utilisées.
La facilité de calcul des moments au sein de chaque de chaque block
constituant l’image globale, induisant une amélioration significative du temps
de calcul.
La robustesse contre l’erreur de reconstruction qui devient local ce qui rend les
blocks voisins insensibles à cette erreur
Le PME nous garantit une automatisation de l’algorithme proposé ne
nécessitant aucune information à priori
Dans cette étude, nous nous sommes limités aux moments de Legendre et Zernike qui sont
efficaces en terme du pouvoir de reconstruction par rapport aux moments géométrique avec
Chapitre III 34
une mesure de redondance nulle [Teh 88], [Abu-mustafa 84], [Pawlack 92] et [Teage 80].
Toutefois les résultats obtenus peuvent être directement généralisés pour d’autres types de
moments orthogonaux [Teh 88], [Teage 80].
3 Méthode de reconstruction globale
Soit la fonction f(x,y) à support borné, la reconstruction globale de la version numérisée de
f(x,y) donnant lieu à la fonction intensité image ),(ji
yxf est une approximation, par troncature
jusqu’à l’ordre θ , de cette fonction réelle :
)()(),(0 0
jqiqpp
p
qqpji
yPxPyxf−
θ
= =−θ ∑∑λ≈ (3.1)
qp,λ étant approché par sa version numérique. Nous adopterons dans la suite de cette section,
l’approximation obtenue dans les travaux de Liao et Pawlak [Liao 96] :
),(),(1 1
,,
ji
M
i
N
jjiqp
qp yxfyxH∑∑= =
∧
=λ (3.2)
Tel que ( )yxf , est constante par morceau sur l’intervalle ]2
,2
[ xxxxii
∆+∆− × ]2
,2
[y
yy
yjj
∆+
∆− .
Et la quantité
∫ ∫
∆+
∆−
∆+
∆−
++=
2
2
2
2
, )()(4
)12)(12(),(
xx
xx
yy
yy
qpjiqp
i
i
j
j
dxdyyPxPqp
yxH (3.3)
Représentant l’intégration des polynômes )()( yPxP qp au voisinage du pixel ),(ji
yx .
De la même manière est définie la reconstruction par moments de Zernike sur le disque
unité [Liao 98]:
Chapitre III 35
pairqpVAyxfp
p
q
qpqp −=∑∑= =
∧∧ θ
θ φρ0 0
,, ,),(),( (3.4)
ces deux types de reconstruction sont appelés « global », car elles consistent en un traitement
de l‘image entière allant du calcul des moments au calcul de la fonction reconstruite, ce qui
rend le calcul des moment complexe et très coûteux en temps de calcul.
Effectivement, la méthode de reconstruction globale (GRM) présente des difficultés majeur
pour la reconstructions des images multi-niveaux de grande taille, et que malgré, les efforts de
minimisation de l’erreur menés par Liao et Pawlak [liao 96] [Liao 98].
La méthode GRM s’avère plutôt complexe en temps de calcul. En effet, pour avoir une bonne
qualité de l’image, le processus de reconstruction introduit lors des calculs les moments
d’ordre élevés, entraînant une consommation en temps de calcul très importante. Ce
problème, rend l’utilisation de cette méthode pour des applications en temps réelle presque
impossible.
Pour palier à ce problème, on propose dans la section suivante une approche basée sur un
partitionnement de la taille globale de l’image en plusieurs petites zones appelées ‘block’.
Cette technique est purement locale, car chaque block est traité d’une manière indépendante.
Ainsi, la réduction de l’espace image permet l’utilisation des moments d’ordres faibles lors du
processus de reconstruction, ceci implique une consommation réduite en temps de calcul et
des erreurs de reconstruction très faibles.
4 Reconstruction d’image par Block (Block Based Reconstruction
Method : BBRM)
L’idée de base de la méthode proposée réside dans l’utilisation de polynômes d’ordre faible
sur de petits intervalles, plutôt que des ordres élevés sur un seul intervalle [Baranger 91].
Ainsi, l’image à reconstruire est partitionnée en plusieurs blocks de taille (k,l) produisant un
nombre de sous-images qui seront ensuite reconstruits séparément.
Chapitre III 36
Soit (M,N) la taille de l’image initiale et (k,l) la taille du block de partitionnement. En
introduisant les variables:
k
Ms =1 et
l
Ns =2 .
le nombre total de blocks de l’image s’exprime alors par : 21. ssNb = .
Sachant que l’espace image est donné par:
NyMxyx jiji ≤≤≤≤=Ω 0,0/, (3.5)
Nous définissons le sous-espace block Ω⊂21 ,nnD comme étant:
lnylnknxknyxD jiji
nn )1(,)1(/, 1122, 21 +≤≤+≤≤= (3.6)
Il est à noter que l’espace image globale Ω peut s’exprimer en terme des sous-espaces blocks
par la relation:
212
2
1
1
,)1(
0
)1(
0
nns
n
s
n
D−
=
−
==Ω UU (3.7)
Alors la fonction image associée à chaque sous-espace 21n,n
D est définit par:
2121 ,, ,/),(),( nn
jiji
nnDyxyxfyxf ∈= (3.8)
Ce qui implique que:
),(),( 212
2
1
1
,)1(
0
)1(
0yxfyxf
nns
n
s
n
−
=
−
== UU (3.9)
4.1 Reconstruction par moments de Legendre
A partir de ces définitions, nous définissons les moments de Legendre calculés pour chaque
sous-espace block :
Chapitre III 37
),(),( 21
2
2
1
1
21
21,
)1( )1(,
,
,
, ji
nn
kn
kni
ln
lnj
ji
nn
qp
nn
qp yxfyxH∑ ∑+
=
+
=
∧
=λ (3.10)
Avec
dydxyPxPyxH
xx
xx
yy
yy
qpji
nn
qp
i
i
j
j
∫ ∫∆+
∆−
∆+
∆−
=
2/
2/
2/
2/
,, )()(),(21 (3.11)
La fonction sous-image block reconstruite à partir de 21 n,nq,pλ pour un ordre θ est définie par:
∑∑ −−
∧
=θ
θ λp
m
q
jqiqp
nn
qqpji
nn
yPxPyxf )()(),( 21
21,
,
,
(3.12)
Finalement, la fonction image pour un ordre θ est obtenue par l’union des sous-images
reconstruites dans chaque sous-espace block (figure 3.1):
),(),(21
1
,
2
yxfyxfnn
nn
θθ
∧
= UU (3.13)
(a) (b) (c)
Figure. 3.1 : Illustration de la méthode BBRM par moment de legendre. (a) partitionnement de l’image initiale en bN sous-images, (b) extraction de moments pour chaque block, (c)
reconstruction et fusion des bN blocks.
4.2 Reconstruction par Moments de Zernike
De la même manière les moments de Zernike pour chaque block ont la forme suivante :
Chapitre III 38
),(),( 21
2
2
1
1
21
21,
)1( )1(,
,
,
, ji
nn
kn
kni
ln
lnj
ji
nn
qp
nn
qp yxfyxHA ∑ ∑+
=
+
=
∧
= (3.14)
Où dydxVyxH
xx
xx
yy
yy
qpji
nn
qp
i
i
j
j
∫ ∫∆+
∆−
∆+
∆−
=
2/
2/
2/
2/
,*,
, ),(),(21 θρ
avec les conditions suivantes: 2,1
22
,
1
nnji
ji
Dyx
yx
∈
≤+
La fonction image reconstruite au sein du block à partir des moments 21 ,,
nn
qpA pour un ordre θ :
∑∑ −=∧∧ θ
θ φρp
p
q
qp
nn
qpji
nn
pairqpVAyxf ,),(),( ,
,
,
, 2121
(3.15)
Avec 2,1
22
,
1
nnji
ji
Dyx
yx
∈
≤+
La fonction image peut être obtenue pour un ordre donné par fusion (l’équation (3.13)).
Figure 3.2 : Illustration de la méthode BBRM par moment de Zernike. (a) partitionnement de l’image initiale en bN sous-images, (b) extraction de moments pour chaque block, (c)
reconstruction et fusion des bN blocks.
La reconstruction par les moments de Zernike est définie sur le disque unité, en conséquence,
cette caractéristique nous complexe la tache lorsque on veut partitionner l’image d’entrée en
plusieurs blocks rectangulaire figure 3.2a. En effet, comme illustre la figure 3.2c il existe des
régions de l’image finale non reconstruites (non reconstructed regions : NRR) au sein de
chaque sous espace block 21 ,nnD .
Chapitre III 39
Pour résoudre ce problème dû à la reconstruction circulaire au sien de chaque sous espace
block 21 ,nnD . et l’effet de block relié à la reconstruction par moments de Zernike, nous
proposerons dans la section 5.1 une solution de chevauchement qui consiste en
l’élargissement du rayon du disque de reconstruction (Figure. 3.5(a)), le nouveau rayon du
block circulaire 2r est donc égale à 1r2 .
4.3 Sélection de l’Ordre optimale des moments via PME
Pour le problème de sélection du nombre de moments optimale utilisé pour la reconstruction,
Teh et chin [Teh 88], ont utilisés l’erreur quadratique moyenne entre l’image initiale et celle
reconstruite comme mesure objective du pouvoir de reconstruction. Cependant cette méthode
suppose la connaissance à priori de l’image originale ce qui limite l’application de ce critère
dans les cas pratique ou cette image n’est pas disponible. Pour résoudre ce problème Liao et
pawlak [Liao 96], [Liao 93]. Suggèrent d’utiliser une méthode statistique appelé cross-
validation. L’absence d’une étude détaillée sur cette méthode pose des problèmes
d’implémentation.
Dans ce chapitre, on introduit comme critère de sélection le principe de maximum d’entropie
PME. Cette technique est automatique car elle permet l’estimation de l’ordre optimale des
moments directement de l’image reconstruire sans avoir besoin d’une connaissance à priori
sur l’image originale [Qjidaa 99a], [Rober 91]. La solution du problème du choix de l’ordre
de développement des moments est mathématiquement très complexe, car on ignore l’ordre
de troncature de la fonction image ),( yxf , assurant une bonne qualité de reconstruction.
On introduit le principe du maximum d’entropie, cette technique automatique permet
l’estimation du nombre optimale des moments nécessaire à la reconstruction directement à
partir des données disponibles sans avoir besoin d’information à priori sur l’image initiale
Soit ),( ji yxp∧
la fonction de densité de probabilité obtenue par normalisation de ),( ji yxf∧
[Qjidaa 99a]:
Chapitre III 40
∑∈
∧
∧
∧
=
Ω,
),(
),(),(
ji yx
ji
ji
ji
yxf
yxfyxp (3.16)
avec
1),(Ω,
=∑∈
∧
ji yx
ji yxp (3.17)
et 1),(0 ≤≤∧
ji yxp , Ω est l’espace image.
Et soit wG l’ensemble des fonctions de probabilité pour différents ordres θ :
........1/),( ωθθ ==∧
jiw yxpG (3.18)
En appliquant le PME pour des images bruitées, il existe une et une seule densité de
probabilité ),( ji yxp∗∧
θ pour laquelle l’entropie est maximale [Qjidaa 99a], [Zhunang 91] qui
représente la fonction densité de probabilité optimale, l’ordre correspondant est appelé ordre
optimale. Pour les images non bruitées la fonction entropie est croissante jusqu'à un certain
ordre optimale où le maximum d’information est recrée, au delà de cet ordre cette fonction
devient relativement constante.
L’entropie de Shannon de ),( ji yxpθ
∧
est définie dans [Robert 91] par:
∑Ω∈
∧∧∧
−=ji yx
jijiji yxpyxpyxpS,
)),(log(),()),(( θθθ (3.19)
La fonction de densité optimale ),( ji yxp∗∧
θ est telle que :
),(/)),(S()),(( Wjijiji GyxpyxpMAXyxpS ∈=∧∧∗∧
θθθ (3.20)
Chapitre III 41
4.4 Algorithme de reconstruction par block utilisant le PME
La méthode de reconstruction et de représentation par block se base sur le même principe que
celui décrit dans la section 3, sauf que dans ce cas l’algorithme procède par un traitement
local au sein de chaque block. L’ordre de reconstruction optimale contrôlé par PME sera
calculé après la fusion de tous les blocks constituant l’image entière.
On présente les étapes de l’algorithme de reconstruction par block utilisant le PME .
Algorithme 3.1 : Algorithme de reconstruction par block (BBRM) utilisant le PME
Partitionner l’image originale en blocks de taille (k x l).
initialiser θ .
Répéter
(1) Evaluer les moments de chaque block utilisant (3.10) (ou 3.14).
(2) Estimer la fonction reconstruite de chaque block utilisant (3.12) (ou 3.15).
(3) Fusion des blocks estimés pour former une estimation ),( ji yxf θ
∧
pour un ordre θ
utilisant (3.13).
(4) Evaluer l’entropie de Shannon correspondante: )S( θ
∧
p .
(5) Incrémenter θ .
Jusqu'à ce que ε+≤ θ
∧
θ
∧
)S()S( pp .
L’ordre θ obtenu est appelé l’ordre optimal et ),( ji yxf θ
∧
la fonction de densité reconstruite
optimale.
Pour évaluer expérimentalement la valeur de ε , l’algorithme a été appliqué pour différentes
tailles de blocks (4 x 4), (8 x 8), (16 x 16) et (32 x 32). L’algorithme produit de très bons
résultats en terme de qualité de reconstruction si ε vérifie la condition suivante :
ε <1
Chapitre III 42
Les valeurs de ε obtenus lors de ces simulations sont données dans la section 5.
5 La méthode de reconstruction basée sur les blocks chevauchés
(Lapped Block Based Reconstruction Method :LBBRM)
1.1 Elimination de l’effet de block
La reconstruction d’image par block utilisant la méthode des moments offre un bon
compromis entre le temps de calcul et la qualité subjective de l’image. Malheureusement, si
des blocks adjacents ont des erreurs de reconstruction différentes, les bords des blocks en
question deviennent visibles ( En plus, pour la reconstruction par moments de Zernike il y a
apparition des zones non reconstruites (cf. figure 3.2c). Cet effet appelé effet de bord ou
artefact (artifact en anglais) est plus important sur des images reconstruites pour des ordres
faibles.
Une des techniques utilisées, dans les traitements par block, pour résoudre ce problème
consiste en un traitement à posteriori des images reconstruites. Cependant ces méthodes
permettent une réduction de l’effet de block au prix d’une augmentation de l’erreur moyenne
de reconstruction [Malvar 89] et un surcroît de temps de calcul.
La solution apportée par notre approche pour surmonter cet effet de block, résulte de l’idée
que l’effet de block est du à la non exploitation de la corrélation inter-block durant le
processus de reconstruction, car chaque block est traité comme une entité indépendante. Il est
donc utile d’utiliser cette corrélation pour réduire les dégradations dus à l’effet de bord. Pour
notre méthode l’information du voisinage est prise en considération lors de l’étape de calcul
des moments. Cette méthode donne des résultats remarquables pour l’élimination de l’effet de
bord en évitant les traitements à posteriori consistant en la restauration ou l’amélioration
d’image.
Par conséquent, dans notre méthode l’élimination de l’effet de block est inclut lors du calcul
des moments et du processus de reconstruction par une technique de chevauchement de block.
Chapitre III 43
Cette technique permet également dans le cas de moments de Zernike de recouvrir les régions
non reconstruites (Figure3.2(c))
La méthode proposée intitulée LBBRM passe par deux étapes:
le calcul des moments qui extraits l’information du voisinage en
utilisant le chevauchement des blocks.
Le processus de reconstruction qui traite chaque block de sortie
séparément et ensuite fait une fusion pour reconstruire l’image
finale.
5.1 Algorithme de reconstruction par block chevauchées utilisant le PME
L’algorithme LBBRM contrôlé par le PME est le même que celui décrit dans le section
précédente excepté que les moments sont calculés pour les blocks chevauchés constituant
l’image initiale comme définie dans la formule (3.7) et en accord avec les figures 3.4 et 3.5.
Finalement, la fonction image est obtenu par fusion des blocks comme définit dans (3.13).
L’utilisation du PME comme mécanisme de contrôle au sein du LBBRM assure l’estimation
du nombre optimale des moments directement à partir des données disponibles. Par
conséquent aucune information à priori à propos de l’image initiale n’est requise.
Figure 3.3 : illustration de l’étape de chevauchement d’un seul block.
Chapitre III 44
La figure 3.3 montre le processus de chevauchement d’un seul block. En effet, on évalue les
moments de chaque block chevauché pour une taille (k’ x l’) avec k’=k+2c et l’=l+2c, c : est
le facteur de chevauchement, (k x l) est la taille du block à reconstruire.
Les grandes lignes de l’algorithme de reconstruction par block chevauchés utilisant le PME
comme critère de sélection est donné par :
Algorithme 3.2 : Algorithme de reconstruction par block chevauchés (LBBRM) utilisant le
PME
Partitionner l’image originale en blocks chevauchés de taille (k’ x l’) (Figure 4).
initialiser θ .
Répéter
(1) Evaluer les moments de chaque block chevauchement de taille (k’xl’) utilisant (3.10)
(ou 3.14).
(2) Estimer la fonction de reconstruction de chaque block reconstruction de taille (k,l)
utilisant (3.12) (ou 3.15).
(3) Fusion des blocks estimés pour former une estimation ),( ji yxf θ
∧
pour un ordre θ
utilisant (3.13).
(4) Evaluer l’entropie de Shannon correspondante: )S( θ
∧
p .
(5) Incrémenterθ .
Jusqu'à ce que εθθ +≤∧∧
)S()S( pp .
Chapitre III 45
Figure 3.4 : Illustration des différentes étapes de l’approche LBBRM utilisant la méthode des moments de Legendre, a) processus de chevauchement de plusieurs blocks, b) chevauchement d’un seul block dans le cas des moments de Legendre.
Figure 3.5 : Illustration des différentes étapes de l’approche LBBRM utilisant la méthode des moments de Zernike, a) chevauchement d’un seul block dans le cas des moments de Zernike, b) processus de chevauchement de plusieurs blocks.
Chapitre III 46
La figure 3.6 montre un résultat de simulation utilisant la méthode LBBRM par moment de
Legendre. On voit clairement après reconstruction l’élimination de l’effet de block avec une
amélioration significative en terme de qualité subjective et objective de l’image reconstruite.
Figure 3.6 : Elimination de l’effet de block par la méthode LBBRM : (a) l’image originale ‘‘LENA’’, (b) ‘‘LENA’’reconstruite via BBRM (image gauche) et via LBBRM (image droite) par utilisation des moments de Legendre avec la taille de block (4x4) pour l’ordre de reconstruction 0, (c) l’image reconstruite via BBRM (image gauche) et LBBRM (image droite) par des blocks (4x4) pour l’ordre 4.
En résumé la méthode LBBRM permet des améliorations sur deux niveaux :
éliminer l’effet de block par l’exploitation de l’information des
blocks adjacents durant l’étape de calcul des moments, évitant
l’utilisation des techniques de post-traitement (restauration,
amélioration) qui alourdissent le temps de calcul.
L’estimation automatique de l’ordre optimale sans avoir besoin
de l’information à priori à propos de l’image initiale.
Chapitre III 47
5.2 Comparaison entre le chevauchement par les moments de Legendre et
Zernike
Contrairement au moment de Legendre, on remarque dans le cas de la reconstruction par
blocks chevauchés via les moments de Zernike, que le chevauchement interblock n’est pas
uniforme, cela et dû a l’utilisation des cercles. On obtient alors un chevauchement maximal au
centre du block et il devient faible plus on s’éloigne du centre comme illustre la figure 3.7.
Une étude est en phase de réalisation pour voir l’impact de cette remarque sur la qualité de
l’image reconstruite et la capacité du chevauchement par cercle d’éliminer l’effet de bord.
Figure 3.7 : Comparaison entre le chevauchement proposé par moments de Zernike (a) et
moments de Legendre (b)
6 Résultats Expérimentaux
Notons que les résultats de simulation ont été réalisé seulement pour la méthode de
reconstruction utilisant les moments de Legendre avec une comparaison des différentes
performances obtenu. Une autre étude est en phase de réalisation pour le cas des moments de
Zernike.
Pour illustrer les performances de l’approche proposée, notre algorithme de reconstruction
LBBRM est testé sur deux types d’images ; binaire et nivaux de gris. Dans ce qui suit, on
définit des critères objectifs communément utilisés dans la littérature pour mesurer la qualité
des images reconstruites.
Chapitre III 48
a) Erreur Quadratique Moyenne (MSE)
L’erreur quadratique moyenne est définit pour une image de taille )N,M( comme suit:
∑∑= =
∧
−=M
i
N
j
jiji yxfyxfNM
MSE1
2
1
),(),(.
1 (3.21)
Avec ),( ji yxf∧
la version reconstruite de la fonction image originale ),( ji yxf pour chaque
pixel ),( ji yx .
b) Le rapport Peak Signal-To-Noise Ratio (PSNR)
Dans [Jain 89], le rapport Peak Signal-To-Noise Ratio est définie en décibels ( Bd ) comme
étant:
=
MSE
kPSNR
2
10log10 (3.22)
k : est la valeur maximale des niveaux de gris de l’image originale.
Exemple 1
Pour illustrer les performances de l’approche utilisée, notre algorithme est testé sur une image
binaire de taille 128x128 pixels représentant une note musicale ‘Clé de Sol’ scannée et
binarisée figure 3.8 (a).
La figure 3.8 illustre la méthode de reconstruction globale (GRM) de la note musicale à partir
des moments de Legendre. Pour avoir les détails fins de l’image, on remarque que la méthode
GRM entraîne l’utilisation des moments d’ordre élevé.
La figure 3.9 représente la fonction d’entropie du caractère musicale, on déduit à partir de la
courbe que l’ordre optimal =80.
Chapitre III 49
Figure 3.8 : La reconstruction globale de l’image ‘Clef de Sol’ par les moments de Legendre, (a)image originale ; de (b) à (l) les images reconstruites pour différents ordres 10, 20, 30, 40, 50, 60, 70, 80 et 90 respectivement.
Figure 3.9 : La fonction entropie de la reconstruction de la note ‘clef de sol’ par la méthode GRM, l’ordre optimale de reconstruction est 80, avec PSNR: 24.08.
La figure 3.10 illustre la reconstruction de la note musicale par notre approche LBBRM en
utilisant les tailles de block (4x4) et (8x8). On remarque qu’un nombre fini et restreint des
moments a pu reconstruire d’une façon efficace l’image initiale sans inclure les moments de
Legendre d’ordre élevés.
Chapitre III 50
Figure3.10 : La reconstruction de l’image ‘Clef de Sol’ via LBBRM utilisant les moments de Legendre, (A) image originale, (B) LBBRM avec les blocks de taille (4x4), de (a) à (g) les images reconstruites de l’ordre 0 à 6, (h) l‘image reconstruite pour l’ordre 7 où l’erreur de reconstruction est nulle (C) LBBRM avec les blocks de taille (8x8), de (a) à (m) les images reconstruites de l’ordre 1 à 12, (n) l‘image reconstruite pour l’ordre 13 où une reconstruction parfaite est obtenue.
Chapitre III 51
Effectivement, la courbe qui décrit la variation du MSE en fonction de l’ordre de
reconstruction (Figure 3.11), montre clairement la supériorité de notre approche LBBRM par
rapport à laméthode de reconstruction globale GRM. Aussi, on remarque que plus la taille des
blocks de reconstruction est faible plus la réduction de l’erreur de reconstruction est
importante.
Figure 3.11 : Comparaison de la LBBRM utilisant différentes tailles des block avec la GRM, en terme de la MSE pour la note musicale.
La courbe de l’entropie (Figure 3.12), justifie l’utilisation du critère de sélection PME
comme critère de sélection. L’entropie augmente au fur et a mesure que l’ordre de moment
augmente. La variation de l’entropie est grande pour des ordres inférieurs et elle devient
négligeable pour des ordres supérieurs. En effet, à partir d’un certain ordre, appelé ordre
optimal, toute l’information utile est extraite et le fait d’augmenter encore l’ordre n’améliore
guerre la qualité de reconstruction.
Cet ordre optimal coïncide avec celui donné par la variation de la MSE. Ce qui affirme
l’utilisation du principe du maximum d’entropie dans la détermination de l’ordre optimal de
reconstruction.
Chapitre III 52
Figure 3.12 : La courbe de la fonction entropie pour l’image ‘clef de sol’ reconstruite via LBBRM avec différentes tailles de blocks.
Le tableau 3.1 résume les ordres optimaux obtenus pour chaque taille de block utilisée, avec
le PSNR correspondant. Il est clair, à partir des résultats, que l’ordre optimal augmente au fur
et a mesure que la taille des blocks augmentent.
Les valeurs de ε obtenus lors des résultats du tableau 3.1 montrent clairement que cette
valeur doit être inférieur à 1 pour avoir une bonne qualité de reconstruction.
Tableau 3.1 : Les ordres optimaux obtenus pour la ‘clé de sol’ par PME pour chaque taille de block utilisée dans la LBBRM et la méthode GRM, avec les PSNR correspondantes.
LBBRM GRM
Taille du block 4x4 8x8 16x16 32x32
ordre optimal 4 8 13 25 80
PSNR(db) 32.67 36.19 29.20 26.12 24.08
ε 0.70 0.85 0.91 0.93
Chapitre III 53
Exemple 2
Pour démontrer l’efficacité de l’algorithme proposé LBBRM en terme de qualité de
reconstruction et temps de calcul par rapport à la méthode de reconstruction traditionnelle
GRM. Notre approche est appliquée sur une image niveaux de gris ‘LENA’ de taille 128x128
pixels.
La Figure 3.13 montre que la reconstruction d’une image niveaux de gris ‘LENA’ par la
méthode GRM implique l’utilisation des ordres élevés, ce qui génère une qualité d’image
inférieur.
Figure 3.13 : la reconstruction de l’image “LENA” par la méthode GRM, (a) image originale; de (b) à (l) les images reconstruites pour les ordres 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 et 110 respectivement.
Chapitre III 54
Les figures 3.14 et 3.15 illustrent la reconstruction de ‘LENA’ par notre approche LBBRM en
utilisant les tailles de block (4x4) et (8x8) respectivement. On remarque qu’un nombre fini et
restreint des moments a pu reconstruire d’une façon efficace l’image initiale sans inclure les
moments de Legendre d’ordre élevés. Cela, nous permet d’avoir une bonne qualité de
reconstruction d’image avec un temps de calcul réduit.
Figure 3.14 : La reconstruction de l’image “LENA” par la méthode LBBRM (a) image originale, de (b) à (l) les images reconstruites en utilisant des blocks de taille (4x4) avec les ordre de 0 à 10 respectivement.
Figure 3.15 : La reconstruction de l’image “LENA” par la méthode LBBRM (a) image originale, de (b) à (h) les images reconstruites en utilisant des blocks de taille (8x8) avec les ordres 1, 10, 15, 20, 25, 30 et 35.respectivement
Chapitre III 55
La courbe de la MSE (Figure 3.16) montre efficacité de notre approche en terme de qualité de
reconstruction. En effet, plus la taille des blocks est faible plus la réduction de l’erreur de
reconstruction est importante.
0 20 40 60 80 100 120 140 160
0
500
1000
1500
2000
2500
3000
GRM
4x4
8x8
16x16
32x32
MSE
order
Figure 3.16 : Comparaison de la LBBRM utilisant différentes tailles block avec la GRM, en terme de la MSE pour l’image multi-niveaux “LENA”.
Chapitre III 56
Le tableau 3.2 montre que notre méthode proposée LBBRM peut recréer de bonne qualité
d’image avec des moments d’ordre très faible comparé à la méthode GRM.
Tableau 3.2 :Valeurs des PSNR(db) pour des images reconstruites de “LENA” via la méthode LBBRM utilisant différentes tailles de blocks, en comparaison avec la méthode GRM,
PSNR avec LBBRM
PSNR avec
GRM
Taille du
block 4x4 8x8 16x16 32x32
ordre
0 21.91 18.56 15.96 13.45 11.21
5 28.98 22.62 21.72 19.55 16.24
10 35.32 25.36 24.86 22.15 17.42
15 36.22 34.38 25.95 24.12 18.32
20 37.11 34.81 27.70 25.59 19.34
25 38.94 31.91 32.95 26.85 20.35
30 35.22 32.68 33.64 28.25 21.19
35 38.00 36.91 35.83 29.58 21.89
40 39.24 38.64 37.47 31.16 22.70
45 41.77 38.23 35.18 32.56 23.28
50 40.38 39.52 33.66 33.54 23.66
Le tableau 3.3 illustre la réduction importante en temps de calcul par l’utilisation de notre approche LBBRM en comparaison avec GRM pour un PSNR= 26. Tableau 3.3 : Les rapports de réduction du temps de calcul de la méthode LBBRM, en comparaison avec la GRM, pour un PSNR: 26
LBBRM
Taille du block (4 x 4) (8 x 8) (16 x 16) (32 x 32)
Caractère musical 80.23% 86.61% 86.45% 81.66%
Ordre correspondant 1 3 6 13
LENA 82.26% 88.26% 87.94% 84.62%
Ordre correspondant 3 11 16 25
Chapitre III 57
7 Conclusion et perspective
Dans ce chapitre, nous avons proposé une nouvelle technique basée sur la reconstruction
d’image par block utilisant la théorie des moments. Pour le problème de la sélection de l’ordre
optimale, nous avons utilisé le principe du maximum d’entropie, totalement automatique car
aucune information à priori n’est requise.
Le traitement de l’image par différentes tailles de block (4x4), (8x8), (16x16), et (32x32)
entraîne une réduction considérable de l’erreur de reconstruction, ainsi qu’un grand gain en
temps de calcul en comparaison avec la méthode de reconstruction globale (GRM). On
obtient ainsi des qualités de reconstruction bien meilleurs avec des moments d’ordre faible.
Cette nouvelle méthode peut entraîner des dégradations dues à l’effet de blocks, surtout pour
des ordres de reconstruction faibles.
Pour surmonter cet effet de bord, nous proposons une nouvelle méthode utilisant la technique
du chevauchement de block (lapped block based reconstruction method LBBRM) lors du
calcul des moments et de la reconstruction profitant ainsi de l’information du voisinage
Cette approche donne des améliorations objective et subjective de la qualité des images
reconstruites, comme en témoignent les résultats exposés pour les images binaires et multi-
niveaux.
L’approche proposée qui est une combinaison da le méthode (LBBRM) avec le PME comme
critère de sélection, permet à la fois l’amélioration de la qualité de l’image reconstruite et
l’accélération du processus de reconstruction ( tableau 3.3).
Notre future travaille est la réalisation d’une étude plus complète sur la reconstruction par
blocks chevauchés utilisant les moments de Zernike. Afin d’établir en suite une comparaison
avec les performances obtenus par la méthode utilisant les moments de Legendre en terme de
complexité, temps de calcul et d’erreur de reconstruction.
Conclusion générale 58
Chapitre III Squelettisation des Images Binaires bruitée
par la méthode des moments
1 Introduction
La squelettisation d’une image est une technique qui extrait ce que l’on appelle le ‘squelette’.
Le squelette est un ensemble de lignes fin et centré par rapport à l’objet. Ainsi, il représente la
quantité d’information minimale qui décrit un objet de façon compact.
Historiquement, la première définition a été introduite par Blum en 1964 [Blum 64] grâce à la
métaphore des feux de prairie. Il définit le squelette comme lieu des points où les fronts de
propagation de feu s’évanouissent. Ces points sont appelés points d’extinction. Toujours dans
le but de formaliser la notion de squelette, L. Calabi et Hartnett [Calabi 65][Calabi 68]
[Hartnett 65] considèrent le problème de point de vue topologique. Ils donnent une autre
définition du squelette qui est basée sur le concept des boules maximales. Ils démontrent que
les notions des points d’extinction et le centre de boule maximale sont équivalentes. Dés
1978, Blum et Nagel [Blum 78] proposent d’utiliser le squelette afin de décomposer les
formes et de les classer. Par la suite, l’engouement pour le squelette comme descripteur de
forme ne s’est pas démenti. De nombreux travaux ont été et continuent d’être publiés tant sur
les propriétés que sur les méthodes de calcul ou les applications du squelette [Dokladal 00]
[Ogniewicz 93a [Serra 82] [Schmitt 93] [Lam 92].
Cependant, Toutes les méthodes de squelettisations qui ont été portées à notre connaissance
sont applicables uniquement pour des images binaires non bruitées. Cela nous a conduit à
développer une nouvelle approche de squelettisation applicable à des images binaires bruitées.
L’approche statistique proposée est basée sur la théorie des moments contrôlée par le Principe
de Maximum d’Entropie (PEM)[Zenkouar 05a] [Zenkouar 05b].
Conclusion générale 59
Dans ce chapitre, nous allons d’abord établir un état de l’art des différentes approches de
squelettisations existantes. Nous rappelons dans un premier temps les définitions des
différentes caractéristiques topologiques des objets dans l’espace continu et discret. Ensuite,
nous commencerons par définir ce qu’est un squelette et présenter ses propriétés. Nous
passerons en revue les méthodes de squelettisation, nous présenterons à cette occasion les
avantages et les limitations de chacune d’entre elles. Finalement, les approches proposées
seront présentées ainsi que les résultats obtenus en simulation.
2 Espace continu : notion topologique
Il existe plusieurs définitions équivalentes du squelette dans l’espace continu, néanmoins, ces
définitions nécessitent de définir certaines notions topologiques.
La compréhension des formes, nécessite de définir certaines notions étudiées en topologie.
Ainsi, la notion de forme peut se définir au moyen de la notion de distance. Bien que les
formes que nous étudierons soient des éléments du plan discret (appartenant 2Z ), leurs
modèles sont des éléments du plan continu (appartenant 2R ).
Par la suite, il sera souvent question de distance. Nous en donnons ci-dessous une définition
générale.
2.1 Distance
Définition 4.1 : Soit E un ensemble non vide et F un sous-ensemble de R . Une distance d sue
E à valeur dans F est une application FEE:d →× vérifiant les propriété suivate : positivité,
définition, symétrie et inégalité triangulaire définie ci-dessous :
Eqp ∈∀ , 0),( ≥qpd ; (4.1)
Eqp ∈∀ , qpqpd =⇔= 0),( ; (4.2)
Eq,p ∈∀ )p,q(d)q,p(d = ; (4.4)
Conclusion générale 60
( Erqp ∈∀ ,, ),(),(),,( qrdrpdrqpd +≤ ; (4.4)
2.2 Norme euclidienne
Dans le plan continu, la distance entre les éléments se base généralement sur la norme
euclidienne : pour tout point ),( yxp de 2R , la norme euclidienne, notée . ou 2L , est une
application de R
22 RR → définie par :
22yxp += (4.5)
2.2.1 Distance euclidienne
Pour tous points ),( pp yxp et ),( qq yxq de 2R , la distance (ou métrique) euclidienne est
l'application RRxRqpdE →22:),( _ définie par
22 )()(),( pqpqE yyxxpqqpd −+−=−= (4.6)
Où qp− représente le vecteur de p à q. Si Ω est un ensemble de points de _
2R et p un point de
_
2R , ),p(d
EΩ est la plus courte distance entre p et Ω :
),(min),(),( qpdpdpd Eq
EEΩ∈
=Ω=Ω (4.7)
2.3 Boule ouverte
Définition 4.2 : Soient p un point de2
R , r un réel positif et d une distance. La boule ouverte
),( rpBd de centre p et de rayon r est l'ensemble des points q tel que la distance )q,p(d soit
inférieure à r :
rqpdRqrpBd <∈= ),(/),( 2 (4.8)
nous noterons la boule euclidienne EB , définie par EdE BB ≡
Conclusion générale 61
Une boule fermée est définie par rqpdRqrpBd ≤∈= ),(/),( 2
2.4 Ensemble ouvert, fermé
Définition 4.3 : Un ensemble de Ω de 2
R est dit ouvert si pour tout point p de Ω il existe un
réel positif r tel que la boule ouverte ),( rpBE soit entièrement contenue dans Ω .
Soit Ω un ensemble de 2R . Le complémentaire de Ω dans
2R , noté CΩ , est l'ensemble des
points p de 2R qui ne sont pas Eléments de Ω ( Ω∉∈=Ω pRpC /2 ).
Définition 4.4: Un ensemble Φ de 2
R est dit fermé si son complémentaire est un ouvert.
2.5 Ensemble borné
Définition 4.5: Un ensemble Ω de points de 2
R est dit borné si et seulement si il existe un
point p de 2
R 2 et un réel positif r suffisamment grand pour que Ω soit un sous-ensemble
de ),( rpBE .
2.6 Notion d’intérieur et de fermeture
Définition 4.6 : On appelle intérieur d'un ensemble de points Ω de 2
R , l'ensemble
)int(Ω défini par l'union de tous les ouverts contenus dans Ω .
Définition 4.7 : La fermeture d'un ensemble de points Ω de 2
R est l'ensemble Ω défini par
l'intersection des fermés contenant Ω .
2.7 Notion de contour
Définition 4.8 : Soit un ensemble Ω de2
R , le contour de Ω , noté Ω∂ , est défini par
l'intersection entre la fermeture de Ω et la fermeture de son complémentaire :
CΩ∩Ω=Ω∂ (4.9)
Conclusion générale 62
2.7.1 Différence entre : intérieur, fermeture et contour
La différence entre les notions d'intérieur, de fermeture et de contour est illustrée dans la
figure 4.1. L'intérieur représente seulement la zone grisée, le contour représente seulement la
courbe fermée en noir et la fermeture correspond à la fois à la zone grisée et au contour noir.
A cela, nous pouvons ajouter que le complémentaire de l'intérieur correspond au reste du plan,
le contour inclus, le complémentaire de la fermeture correspond au reste du plan, le contour
exclu, et le complémentaire du contour correspond à l'union entre le reste du plan et
l'intérieur.
Figure 4.1 : Différence entre SetS)int( et S∂ .
2.8 Notion de forme
Définition 4.9 : Un ensemble de points Ω de 2
R est une forme s'il possède les deux
caractéristiques suivantes :
1. Ω est la fermeture d'un sous-ensemble de2
R ouvert et borné ))int(( Ω=Ω ;
2. le contour Ω∂ de Ω consiste en un nombre fini de courbes fermées.
Cette définition de la forme est relativement simple et permet de discerner distinctement cette
notion à partir d'un ensemble de points.
Conclusion générale 63
3 Définitions du squelette
La squelettisation est le processus permettant d'obtenir des squelettes des formes. Elle
consiste à convertir une forme en un ensemble de lignes centrées à l'intérieur et à l'extérieur
du contour de la forme, possèdent une structure en branches liée à la topologie de la forme
[Folleymarie03]. Le squelette connu aussi sous le non ‘axe médian’ possède des propriétés
intéressantes dans le cadre de l'analyse des formes.
3.1 Squelette par feu de prairie
Définition 4.10 : Soit un plan couvert de manière homogène par de l'herbe sèche et Ω un
ensemble de points de ce plan. A l'instant initial0
t , tous les points du contour de Ω sont
enflammés simultanément. Le feu se propage de manière homogène et s'étend à travers
l'herbe à vitesse constante. Le squelette de l'ensemble de points Ω (noté MA( Ω )) est défini
comme le lieu des points où les fronts enflammés se sont rencontrés.
La définition ci-dessus est connue sous le nom d'analogie du feu de prairie [Blum 67]
[Dimitrov 03] [Ogniewicz 94]. Elle offre une définition intuitive des squelettes tels que Blum
les a conçus.
La figure 4.2 illustre la squelettisation par la méthode du feu de prairie. La forme contient de
l’herbe sèche répartie sur la surface d’une façon uniforme. Ensuite, le feu est allumé sur tout
le contour, il se propage vers l’intérieur de la forme. A certains endroits, deux fronts se
rencontre et s’éteignent en laissant une trace. A la fin du processus, le feu s’éteint et il ne reste
plus que les traces des fronts qui se sont rencontrés, formant ainsi le squelette.
Conclusion générale 64
Figure 4.2 : Squelettisation d'un rectangle selon l'analogie du feu de prairie. (a) l'Etat initial, (b) Le feu se propage vers l'intérieur de la forme. (c) squelette obtenu après extinction du feu
3.2 Squelette par boule maximal
La notion de squelette est souvent définie en termes de boules maximales comme illustre la
figure 4.3 [Choi 02] [Shmitt 93] [Thiel 94]. Calabit et Hartnet ont montré dans [Calabi 68] La
preuve de l'equivalence entre cette définition et celle de Blum [Blum 67].
Figure 4.3 : Squelette et boules maximales
Définition 4.11 : Soient p un point de 2
R et r un réel positif, une boule )r,p(Bd
est dite
inscrite dans la forme S de 2
R si et seulement si elle est entièrement contenue dans S (si et
seulement si S)r,p(Bd
⊆ . La boule )r,p(Bd
est dite maximale dans S (ou inscrite et maximale)
Conclusion générale 65
si elle est inscrite dans S et si elle n'est pas entièrement contenue dans une autre boule
inscrite dans S.
Définition 4.12 : Le squelette, ou axe médian, MA(S) d'une forme S de 2
R est le lieu des
centres des boules maximales de S. Autrement dit, un point p de S appartient à MA(S) si et
seulement si p est le centre d'une boule maximale de S.
3.3 Squelette pondéré (Transformé de l’Axe Médian)
Avant de définir le squelette pondéré, nous allons tout d’abord définir la notion de la carte de
distance.
Carte de distance (Transformé Distance)
Dans la figure 4.2, nous pouvons imaginer que les points à l'intérieur de la forme sont
progressivement atteints par un front enflammé au cours du temps, en commençant par le
périmètre et en s'avançant vers le centre de la forme. Si nous associons à chaque point de
l'intérieur de la forme le moment auquel il a été atteint par le front, nous obtenons sa distance
par rapport au point du périmètre qui lui est le plus proche. Cette association est appelée carte
de distances ou transformé de distance
Définition 4.13 : Soit une forme S et d une distance. A chaque point p de S nous associons la
valeur )p(DMS
définie par :
),(min)( qpdpDMSq
d
S∉
= (4.10)
où d est une distance. L'ensemble de tous les )( pDM S est appelé la carte de distances
SDM de S.
DM est aussi appelée fonction d'étanchéité.
La carte de distances peut être définie en terme de boules maximales :
Conclusion générale 66
Définition 4.14 : Soit S une forme, p un point de S et r un réel positif, la boule ),( rpBd est
dite maximale dans S pour p si elle n'est pas entièrement contenue dans une boule inscrite
dans S et centrée en p. Si ),( rpBd est maximale dans S pour p, alors rpDM d
S =)( .
La figure 4.4 montre deux cartes de distances pour deux formes. Ces cartes de distances se
basent sur la distance euclidienne quadratique2
Ed . Les positions de la carte de distance sont
représentées alternativement par les courbes noires et les courbes blanches. Le squelette est
formé par l’ensemble des coins obtenus dans la carte de distance.
Figure 4.4 : Carte de distances de deux formes en utilisant la distance euclidienne quadratique.
Squelette pondéré
Définition 4.15 : Le squelette pondéré, ou la Transformée de l'Axe Médian, MAT(S) d'une
forme S de 2
R est l'ensemble des couples formés par le centre des boules maximales de S et
leur rayon.
Autrement dit, un couple (p; r), avec p point de S, appartient à MAT(S) si et seulement si la
boule ),( rpBd est maximale dans S.
Il est possible d'associer à chaque point p d'un squelette la valeur )( pDM S (4.10). Ceci forme
un autre objet nommé squelette pondéré, noté MAT, défini par
Conclusion générale 67
)(/)(),()( pDMrRxSMArpSMAT S=∈= + (4.11)
on peut définir les squelettes pondérés de cette manière, sachant que la distance )( pDM S
représente le rayon de la boule maximale en p.
4 Propriétés des Squelettes
La squelettisation doit tenir compte d’un certain nombre de propriétés [Hilditch 69b] [Jang
90]. Le squelette doit respecter ces propriétés surtout s’il est utilisé dans la reconnaissance de
forme.
Nous allons énoncer dans cette section diffèrent propriétés communes aux squelettes [Atalli
95] [Chassery 91] [Folleymarie 03] [Ogniewicz 93].
4.1 Invariance
Le squelette est invariant par transformation géométrique (rotation, translation et homothétie).
Soit une transformation géométrique. Alors, T n'affecte pas la structure du squelette :
22: ZZT →
))(())(( STMATSMATT =
4.2 Unicité et réversibilité
La squelettisation est une transformation réversible, pour peu que chaque point p du squelette
soit associé à la valeur )p(DMS
. En effet, une forme S peut être définie comme l'union de ses
boules maximales :
USp
pSBS∈
= )( (4.12)
L'ensemble des points p du squelette d'une forme S est suffisant pour reconstruire S [Serra 82]
[Schmitt 93] :
Conclusion générale 68
UUU)()()(
),())(,()(SMATpSMAp
S
SMAp
S rpBpDMpBpBS∈∈∈
=== (4.13)
Plus de détails pour reconstruire une forme à partir de son squelette sont donnés par Dimitrov
[Dimitrov 03].
La réversibilité satisfait les critères d'unicité et de conservation de l'information. Cependant,
cette propriété semble relativement simple à mettre en place dès lors que les distances des
points du squelette au bord de l’objet sont préservées. Cela est probablement vrai pour des
objets avec des formes simples, mais cela est beaucoup plus compliqué pour des objets avec
des formes complexes (zones étroites, petites déconnexions, etc.)
4.3 Description hiérarchique
La valeur des informations des points du squelette dépend de la position du point dans la
forme. Plus le point du squelette est proche du contour de la forme, plus il représentera une
information locale.
Inversement, plus un point squelette est éloigné du contour, plus il représentera une
information globale. La squelettisation propose ainsi une description hiérarchique de la forme
incluant à la fois des informations globales et locales.
4.4 Epaisseur
Un squelette a une épaisseur d'un point. Autrement dit, son intérieur est vide. Soit S une
forme, alors
( ) φ=)(int SMA (4.14)
Une preuve de cette propriété a été donnée par Dimitrov [Dimitrov 03].
Conclusion générale 69
4.5 Homotopique
Une transformation est dite homotopique si elle ne modifie pas le nombre de connexité. Ainsi,
la propriété d'homotopie est très importante car elle permet d'assurer qu'un squelette à le
même nombre de composantes connexes et le même nombre de trous que la forme à partir de
laquelle il a été généré.
Toutefois, dans le cas générale un objet connexe n’a pas forcement un squelette connexe
[Schmitt 93]. Comme le montre la figure 4.5, bien que la forme possède une composante
connexe, deux disques qui se rencontre en p, le squelette de cette forme est représenté par
deux points 1
q et 2q . Cet exemple montre bien qu’il existe des cas où le squelette et non
homotope à la forme. Cependant, il faut bien faire attention au fait que l'intérieur de la forme
de la figure 4.5 contienne deux composantes connexes. Si nous considérons la condition 1 de
la définition 4.9 de la forme, la propriété d'homotopie entre la forme et son squelette reste
vrai.
Figure 4.5 : exemple de squelette non homotope à la forme initiale
La propriété de l’homotopie est fondamentale car elle garantit que l’objet et son squelette ont
même aspect et justifie l’utilisation du squelette comme descripteur de forme. Le non respect
de cette propriété peut entraîner des erreurs d’interprétation, par exemple pour une image
médicale un trou signal la présence d’une pathologie
Conclusion générale 70
4.6 Tolérance au bruit
Le squelette est en effet sensible à la moindre perturbation dans le contour et le contenu de la
forme. Il est donc difficile de satisfaire le critère de tolérance au bruit. Cependant, pour que
cette propriété puisse exister, il est important de définir ce qu’est un bruit.
Un bruit est par définition un point ou une partie de l’objet qui en réalité n’appartient pas à
l’objet. Une petite bosse sur un objet peut engendrer une branche (aussi appelée barbule) dans
le squelette. La difficulté est de dissocier une branche liée à un bruit ou bien une branche qui
en réalité est tout à fait caractéristique de l’objet. Deux solutions sont possibles.
Soit un pré-traitement sur l’objet binaire de départ pour
supprimer le bruit.
Soit un post-traitement sur le squelette résultant pour
supprimer les barbules indésirables [Arcelli 85].
La sensibilité du squelette face aux perturbations dépend de la distance des points par rapport
au contour de la forme. Plus les points du squelette sont proches du contour, plus ils sont
sensibles aux perturbations.
Bien que ces propriétés soient clairement explicitées, il subsiste un désaccord important quant
à l’interprétation précise de ces concepts et leur relative importance. Dans certains cas, ils
peuvent même devenir incompatibles [Verwer 88] [Davies 82]. Il est important de noter qu’il
s’agit là de propriétés théoriques, et qu’il n’existe pas à ce jour une méthode capable de
considérer dans un même algorithme l’ensemble de ces propriétés.
5 Espace discret : Notion de topologie pour les images binaire.
La géométrie discrète a été crée pour les besoins de l’analyse d’image. Les notions
fondamentales en géométrie discrète s’élaborent sur la représentation discrète du support de
l’image. Ces notions permettent d’accéder aux concepts élémentaires utilisables en géométrie
Conclusion générale 71
à savoir les concepts de courbe et d’objet. Tout comme dans le cas continu, de tels concepts
nécessitent l’introduire une notion de distance, la notion de voisinage et de connexité.
5.1 Notion de Topologie
La topologie est par définition la connaissance des lieux. C’est initialement une branche des
mathématiques qui étudie les propriétés des êtres géométriques subsistants après une
transformation continue, et qui fait abstraction de la notion de distance.
C’est Bernhard Riemann, mathématicien allemand, qui est le précurseur du domaine. Ses
théories tiennent désormais une place considérable dans les mathématiques modernes. Ses
travaux sur la théorie des fonctions et la théorie des surfaces peuvent être considérées comme
les fondements de la topologie. Son traité « Uber die Hypothesen, die der Geometrie zugrund
liegen » (1854) a inspiré un grand nombre de travaux entrepris dans le domaine des
géométries non euclidiennes, et la géométrie discrète en particulier [Yokoi 73] [Rosenfeld
79] [Kong 89].
5.2 Discrétisation des images, choix du maillage
Le choix du maillage est important car il définit l’espace discret de représentation. La notion
de voisinage et de distance varie selon le maillage utilisé. Différents maillages peuvent définir
l’espace discret. Par exemple, le maillage carré ou bien le maillage hexagonal. Les images sur
lesquels nous travaillons ont été discrétisées avec un maillage carré (Figure 4.6) en 2D. Il
s’agit du maillage le plus utilisé car il correspond au codage fourni par la plupart des capteurs,
et il coïncide exactement avec la structure de données d’une matrice. Nous ne présenterons
que les notions associées au maillage carré en 2D.
Conclusion générale 72
Figure 4.6 : Maillage carré
5.3 Définitions fondamentales de l’espace discret
Rappelons tout d’abord que les points obtenus par l’étape de discrétisation sont appelés pixels
en 2D. Mais quand la dimension ne sera pas précisée, ou qu’il n’y aura au contraire aucune
ambiguïté sur l’espace, nous reprendrons le terme de points, pour désigner indifféremment les
pixels.
5.3.1 Image discrète
Une image est une fonction d’un support dans un domaine de valeurs. Le support est un sous-
ensemble de l’espace Z2 en 2D, qui est défini par le produit cartésien de segments appartenant
a Z. la matrice [0..i],[0..j] en 2D est un exemple de support dans Z2. Les notions présentées
n’aborderont que les traitements appliqués aux images binaires dont le support est un sous-
ensemble de Z2 en 2D, et dont le domaine de valeurs est l’ensemble 0,1. Les points de
valeur 0 sont appelés points du fond et les points de valeur 1 sont appelés points de l’objet
5.3.2 Distances
La distance euclidienne provient du monde continu, mais n’est plus du tout adaptée à l’espace
discret. L’étude des distances est un volet très important de la géométrie discrète. Elle
mobilise un grand nombre de chercheurs dont le but est de trouver des masques de distances
pouvant se rapprocher le plus possible de la distance euclidienne. Nous donnons ici les
définitions de base, et les distances les plus utilisées en imagerie.
Si deux points x et y ∈ Zn sont définis respectivement par (a1,a2,...an) et (b1,b2,...bn) avec ai et
bi ∈ Z alors la distance qui les sépare est égale à :
∑=
−=n
i
ii abBAd1
1 ),( (4.15)
aibiBAdni
−==
∞..1
max),( (4.16)
Conclusion générale 73
d1 représente les distances directes, et d∞ les distances indirectes
En 2D, deux distances sont utilisées :
La distance directe devient la distance d4 aussi appelée
City Bloc Distance ou Manhattan, définie par
d4(x,y)=|y1-x1|+|y2-x2|.
La distance indirecte devient la distance d8 aussi appelée
Chessboard Distance, définie par d8(x,y)=max|y1-x1|,|y2-
x2|).
Bien que ces distances semblent caractériser au mieux la notion de voisinage dans la maille
carrée les valeurs fournies par ces métriques sont fort différentes du résultat associé au calcul
de la distance euclidienne. On peut ainsi remarquer (Figure 4.7) l'erreur que l'on commet
lorsqu'on calcule pour tout point Q du plan sa distance par rapport à P (P étant le point
courant). Cet ensemble définit un disque pour la distance euclidienne. La distance d4 ou d8
modifie considérablement ce disque qui devient un losange (d4) et un carré (d8).
(a) (b)
Figure 4.7 : Approximation de la distance euclidienne pour un disque de rayon 3 par la metrique, (a) distance d4 (b) distance d8
La définition de d4 et d8 revient à associer un coût de 1 aux déplacements directs (d4) ou
directs et indirects (d8) comme le montre la (Figure 4.7). Associer un coût de 1 aux voisins
indirects ne correspond pas à la valeur réelle du déplacement euclidien. Il serait plus naturel
Conclusion générale 74
d’associer un coût égal à 2 (Figure 4.8a). Mais cela n’est pas suffisant car si l’erreur est
nulle suivant les directions multiples de 90°, atténuée suivant les directions multiples de 45°,
elle reste conséquente pour les autres directions.
Montanarie [Montanari 68] propose de pondérer d’autres déplacements dans des voisinages
plus grands avec par exemple (1, 2 , 5 ) (Figure 4.8b).
Comme ces distances ne sont pas entières, Hilditch [Hilditch 69a] propose d’utiliser des poids
(2,3) qu’il associe respectivement aux voisins directs et indirects (Figure 4.9c). Cette
manœuvre permet d’approcher (1, 2 ) lorsque l’on divise chaque poids par 2 soit (1,3/2).
Cette proposition est la définition de ce qui est appelé distance du chanfrein 2-3 notée d2-3.
C’est Borgefors qui popularise ces distances du chanfrein [Borgefors 84] [Borgefors 86]. Elle
préconise et justifie l’approximation de (1, 2 ) par (1,4/3) (Figure 4.9d) et celle de (1,
2 , 5 ) par (1,7/5,11/5) (Figure 4.9e). Les distances résultantes sont le chanfrein 3-4 noté d3-
4, et le chanfrein 5-7-11 noté d5-7-11.
(a) (b)
Figure 4.8 : Masques illustrant la distance euclidienne distance euclidienne dE dans le 8-voisinage du point P (a). distance de Montanari dM (b)
Conclusion générale 75
(a) (b) (c) (d) (e)
Figure 4.9 : Masques d’approximation de la distance euclidienne (a) city block distance : d4
(b) chess board distance : d8 (c) distance du chanfrein 2-3 : d2-3 (d) distance du chanfrein 3-4 : d3-4 (e) distance du chanfrein 5-7-11 : d5-7-11
Les taux d’erreur relativement à la distance euclidienne vont de 41% pour d4 à 2% pour d5,7,11,
il est possible d’approcher plus finement encore la distance euclidienne [Thiel 94].
5.3.3 Voisinages
La définition du voisinage d’un point est obtenu à partir de la définition des distances. En 2D
un point y de coordonnées (y1,y2) est dit 4-voisin ou 4-adjacent à un point x de coordonnée
(x1,x2) si d1(x,y)=1. De même qu’un point z de coordonnées (z1,z2) est dit 8-voisin ou 8-
adjacent ou bien encore appartenant au 8 voisinage d’un point x de coordonnées (x1,x2) si
d∞(x,z)≤1:
Vr
1 (x)=y | d1(x,y)≤r (4.17)
Vr
∞ (x)=y | dn(x,y) ≤r (4.18)
V1 et V∞ définissent respectivement les voisinages directes et indirectes, et r le rayon dans
lequel se situe le voisinage.
Les voisinages V41 et V8
1 sont illustrés dans la figure 4.10. V4 est appelé voisinage direct. Les
points n’appartenant pas à ce voisinage sont appelés voisins indirects.
(a) (b)
Conclusion générale 76
Figure 4.10 : Voisinage d’un point P en 2D dans un rayon de r=1 (points noirs), (a) 4-voisinage du point P dans un rayon de 1, (b) 8-voisinage du point P dans un rayon de 1
5.3.4 Paradoxe topologique
Une seule distance pour décrire les points du fond et les points objets d’une image, ne peut
être utilisée sans créer des paradoxes topologiques [Rosenfeld 66] [Hilditch 69b]. Prenons un
exemple simple : supposons un objet 2D dont les points qui le composent sont noirs, et les
points du fond sont laissés blancs (Figure 4.11).
Figure 4.11 : Paradoxe de connexité
Si on ne considère que la 4-adjacence pour les points de l’objet et pour les points du fond :
Les points noirs sont entièrement déconnectés. Il n’existe pas de point de
l’objet dans le 4-voisinage de chaque point de l’objet.
L’ensemble des points blancs est séparé en deux composantes : deux objets
distincts au sens qu’ils ne sont pas liés dans leur 4-voisinage.
Si on considère maintenant la 8-adjacence pour les points de l’objet et pour les points du
fond :
Les points noirs constituent une courbe fermée discrète. Il est possible de
parcourir l’ensemble des points objets sans passer par un point du fond.
Les points blancs ne sont pas séparés. Ils forment une seule composante.
Conclusion générale 77
Pour ne pas créer de paradoxe topologique, il faut et il suffit d’utiliser des distances
différentes pour le fond et pour l’objet [Kong 89]. Généralement, en 2D la distance d4 est
utilisée pour les points du fond, et la distance d8 pour les points de l’objet. Nous adopterons
ces distances dans la suite de cette présentation.
5.3.5 Chemin connexe et longueur d’un chemin
La définition du voisinage permet de définir ce qu’est un chemin, ainsi que sa longueur.
Définition 4.16 : Un chemin n-connexe entre deux points P et Q est une liste ordonnée de
points P0, P1, ..., Pm, telle que P=P0, Q=Pm et Pi est n-adjacent à Pi+1 avec 0≤i≤m-1.
La composante m définit la longueur du chemin. Par exemple, dans un chemin connexe direct,
Pi et Pi+1 sont voisins directs. La figure 4.12 illustre différents chemins pour la 2D.
(a) (b)
Figure 4.12 : Exemple de chemins en 2D, (a) chemin 4-connecté, (b) chemin 8-connecté
5.3.5.1 Ensemble connexe
Un ensemble n-connexe O est un sous-ensemble de points tels qu’un chemin n-connexe de
points de O existe entre toute paire de points de O. S’il existe un n-chemin p0,..,pk entre P et
Q totalement inclus dans S, on dit que les deux points P,Q sont n-connectés dans S. S est une
n-composante connexe si toute paire de points p,q ∈ S est n-connectée dans S.
5.3.5.2 Composantes connexes
Conclusion générale 78
La notion de composantes connexes est très utilisé pour caractériser les squelettes des objets
binaires. Il existe un certain nombre de règle pour la notation, et nous tacherons de les
respecter. Par exemple, l’ensemble de toutes les composantes n-connexes de X est noté Cn(x),
et l’ensemble de toutes les composantes n-connexes de X adjacentes au point x est noté
C Xnx ( ) .
Compte tenu des distances définies dans le paragraphe 5.3.2, nous parlerons d’objets pour
décrire des composantes objets 8-connexes, et de fond pour décrire des composantes du fond
4-connexes en 2D.
5.3.6 Carte de distances
Définition 4.17 : On appelle alors carte de distances, l’image telle que la valeur attribuée en
tout point P (point quelconque de l’image) est égale à la distance entre P et le point de
référence le plus proche.
La notion de distance fait référence à un point de départ (source) et à un point d’arrivée
(destination). La distance proprement dite étant la somme des unités de mesure (pixel par
exemple) qui séparent ces deux points. Plus généralement, on exprime la distance comme
étant la valeur qui sépare le point source (point référence) du point destination. Dans une
image, les références de départ peuvent être des points du fond, ou un centre de gravité, ou
tout autre point particulier.
La carte de distances est très utilisée pour calculer le squelette d’un objet. Elle est construite
en affectant à chaque point de l’objet la distance qui le sépare du fond. Nous appellerons
indifféremment le résultat de cette transformation Carte de Distances ou Transformé
Distance.
Pour réaliser une image de distances il faut utiliser un masque de distances qui peut être de
taille 3x3 , 5x5, ou plus grand si l’on souhaite approximer davantage la distance euclidienne
(Figure 4.9).
Conclusion générale 79
Deux parcours sont nécessaires pour réaliser une image de distances, dans le but de séparer
les points déjà traités des points qui n’ont pas encore été traités :
un parcours avant de l’image de (x0,y0) vers (x1,y1)
un parcours arrière de (x1,y1) vers (x0,y0).
La position de (x0,y0) va conditionner la forme du masque. Supposons que x0=1 et y0=1, sont
les coordonnées du bas de l’écran à gauche. Dans ce cas x1=n-1 et y1=n-1, ce qui correspond
aux coordonnées du coin supérieur droit de l’écran (Figure 4.13). Le parcours avant et le
parcours arrière s’effectueront par l’intermédiaire de deux demi-masques comme le montre la
(Figure 4.14) pour un masque de taille 3x3.
Figure 4.13 : Parcours d’une image, du coin inférieur gauche vers le coin supérieur droit
(a) (b)
Figure 4.14 : Masques de distances 3x3 pour les parcours avant et arrière d’une image 2D, (a) Masque pour parcours arrière, (b) Masque pour parcours avant
Lors du parcours avant de l’image, le point considéré P est remplacé par le minimum de ses
voisins additionnés aux points du demi-masque. Lors du parcours arrière, si l’un des quatre
voisins additionnés au demi-masque est inférieur au point P, alors le point P devient égal à
cette valeur
Conclusion générale 80
6 Methodes de squelettisation
De nombreuses méthodes ont été proposées pour construire un squelette à partir d'une forme
quelconque [Atalli 95] [Folleymarie 03] [Ogniewicz 93] [Serra 82] [Siddiqi 02] [Thiel 94]. Il
existe actuellement un grand nombre de références sur les méthodes de squelettisation
[Floleymarie 03] [Loncaric 98] [Pizer 03] et leur classement [Kimia 03] [Atalli 95]
[Folleymarie 03] [Ogniewicz 93] [Tek 99] [Thiel 94].
Dans la plupart de ces publications scientifiques, les méthodes de squelettisations sont
réparties en deux classes :
méthodes continues.
méthodes discrètes.
6.1 Méthodes continue
L’objet est représente par un ensemble de points échantillonnant sa frontière, ou par une
approximation polygonale. Des travaux récent ont montrée la possibilité d’approcher le
squelette a l’aide du graphe de Voronoi [Attali 94] [Brandt 94].
6.1.1 Squelette à partir du Diagramme de Voronoï
Le point de départ de cette approche est donné par Kirkpatrick dans [Kirkpatrick 79], où il
postule que le squelette d'une forme polygonale est un sous-ensemble du diagramme de
Voronoï de cette forme. Cette idée est mise en oeuvre par Lee [Lee 82]. Il calcule d'abord le
diagramme de Voronoï du polygone et ensuite il supprime les arêtes partant des sommets des
parties concaves de ce polygone. Mais l'utilisation de cette idée pour trouver les squelettes des
objets ayant une forme arbitraire est fort difficile. D'une part, l'approximation polygonale
d'une forme quelconque est un problème assez difficile, et d'autre part le calcul du diagramme
de Voronoï est complexe (surtout lorsqu'il y a des trous dans l'objet), long, et produit un très
grand nombre de barbules.
Conclusion générale 81
Récemment des approches sont apparues [Ogniewicz 92] [Goldak 91] [Attali 94]. Ils calculent
le squelette à partir du diagramme de Voronoï (DV) d'un ensemble de points. Cet ensemble
étant un échantillonnage discret du contour (continu) de l'objet (Figure 4.15b). Les
diagrammes de Voronoï, et les squelettes trouvés via ces approches convergent vers le cas
idéal au fur et à mesure qu'on augmente la densité de l'échantillonnage.
Donc, dans ces approches, le problème principal est de trouver un échantillonnage discret qui
approxime au mieux la forme de l'objet.
Dans Brandt [Brandt 92b], propose une méthode pour trouver un bon échantillonnage du
contour. Il calcule le DV(Diagramme de Voronoi) de la forme, et conclut que le squelette de
l'objet est la partie du DV qui est totalement à l'intérieur de l'objet. Sur le squelette ainsi
trouvé, il propose une technique de "pruning" pour supprimer de nombreuses branches
fictives. Il donne des preuves de convergence et de continuité de son approche [Brandt 94],.
Ogniewicz et al. [Ogniewicz 92] agissent de la même façon. Ils appellent Voronoï Medial
Axis le squelette calculé à partir du DV. Ils simplifient le squelette obtenu à l'aide de critères
caractérisant la robustesse des branches du squelette dans l'objet.
Conclusion générale 82
Figure 4.15 : Construction du squelette `a partir du diagramme de Voronoi¨des points du contour de l’objet. (a) Image binaire. (b) On choisit les points du contour de l’objet. (c) Diagramme de Voronoi DV des points de contour. (d) Le squelette est u, sous graphe du diagramme de Voronoi entièrement contenu dans l’objet
Conclusion générale 83
6.2 Méthodes Discrètes.
Définition 4.18 : On appelle squelette discret tous ensemble de points de la grille discrète qui
est mince, centré dans la forme, homotope et réversible.
Cette définition n’est pas entièrement satisfaisante, car il est parfois impossible d’avoir
simultanément un squelette mince et réversible.
On appelle axe médian la version discrétisée du squelette continu. C’est l’ensemble des points
du maillage discret qui sont aux centres de boules maximale discrète. La forme de ces boules
(et par conséquent la forme de l’axe médian) dépend de la distance utilisée. La distance
euclidienne est généralement délaissée au profit des distances discrète ( ,d,d84
..) (Paragraphe
5.3.2) qui permettent de manipuler uniquement des entiers naturels, et qui sont simples et
rapides à calculer.
Pour calculer le squelette discret, trois techniques différentes ont été proposées :
l’amincissement homotopique.
Extraction de la carte de distances.
Simulation du front enflammé.
6.2.1 Simulation de la propagation de feu de prairie.
La premiere approche est la simulation de la propagation de feu de prairie à partir des
contours vers l'intérieur de l’objet (dans le domaine discret [Arcelli 81] [Xia 89] [Vincent 90]
[Talbot 92], ou analytique [Montanari 69]). On détecte les intersections (points d'extinction)
des fronts de ces feux au fur et à mesure qu'ils se propagent.
Xia [Xia 89] détermine le nouveau front à l'aide d'une technique de suivi de contour. Chaque
pixel du contour courant est considéré émetteur d'une onde secondaire (un disque, ou boule
Conclusion générale 84
digitale, 4-disque), le nouveau front est l'enveloppe de toutes ces ondes. Pour chaque pixel, il
marque les pixels voisins qui font partie de l'onde dont il est émetteur. Les pixels du nouveau
front qui ont été marqués plus d'une fois sont des points d'extinction. Dans cette simulation il
peut y avoir certaines anomalies. Par exemple, les fronts peuvent s'intersecter aux pixels qui
ne sont pas points d'extinction ("artifcial intersections").
Une étude vraiment très intéressante, qui porte sur l'application de l'analogie de feu de prairie
au calcul du squelette, est fait par Meyer dans [Meyer 79]. Il s'y intéresse à la vitesse de
propagation du feu le long du squelette. En utilisant ce concept, il donne une nouvelle
définition du squelette, et propose des méthodes itératives, utilisant des outils de morphologie
mathématique.
Vincent [Vincent 90] propose un algorithme qui est un mélange des approches par
amincissements successifs et des approches utilisant la carte de distance. Il est utilisé pour
trouver les centres de boules maximales, qu'il appelle points d'ancrage. Ensuite, il fait de
l'amincissement successif par suivi de contour à l'aide de files d'attente. Selon la trame utilisée
(hexagonale, carrée, etc), il crée des tableaux avec toutes les configurations de voisinage
possibles, en différenciant celles qui sont homotopiques de celles qui ne le sont pas. Tous les
pixels du contour sont mis dans la file d'attente, sauf ceux qui sont des points d'ancrage. Pour
chaque pixel dans la file d'attente on examine son voisinage, et on ajoute dans la file d'attente
ceux qui sont à l'intérieur du contour courant. Ensuite, on regarde si la configuration de
voisinage est homotopique. Si elle ne l'est pas, le pixel ne peut pas être enlevé de l'objet (à cet
instant) et on le remet sur la file d'attente. Il se peut que par la suite la configuration de ce
pixel change, et devienne homotopique.
Une variation de cette dernière méthode est proposée par Talbot [Talbot 92], où les points
d'ancrage (centres de boules maximales) sont calculés d'une façon plus précise, non pas via
les maxima locaux de la carte de distance, mais en faisant usage de la définition de f-
bissectrice conditionnelle, celle-ci étant calculée à l'aide de la carte de distance.
Conclusion générale 85
6.2.2 Squelette par amincissement homotopique
L’amincissement homotopique consiste à éroder peu à peu des objets jusqu'à obtenir une
figure mince et centrée [Tsao 81][Gong 90][Kong 89].
Un point du contour est supprimé s’il vérifie les conditions suivantes:
D’une part, sa suppression ne modifie pas l’homotopie ; (il ne doit pas
apparaître de trous dans l’objet, et l’objet ne peut pas être coupé).
D’autre part, ce point n’est pas une extrémité de l’ensemble courant (il faut
préserver les branches qui apparaissent).
Finalement, les point que l’on peut supprimer sont appelés des points simples non terminaux.
Pour déterminer si un point doit être supprimé ou non, il suffit d’examiner son voisinage
immédiat. C’est un traitement purement local [Tsao 81] [Tsao82].
6.2.2.1 Notion de point simple
La notion de point simple [Chassery 91] [Lam 92] est une notion clé pour l’étude des
algorithmes d’amincissement. Un point simple est défini comme un point non-essentiel à la
topologie d’une image.
Soit2
ZX⊂ . Un point x dont l’appartenance a l’ensemble X est indifférente pour la topologie
de X est appelé un point simple pour X. La suppression de ce type de point permet de
simplifier l’objet X tout en préservant sa topologie d’origine ainsi que celle de son
complémentaire
Définition 4.19 : Un point p est dit simple, s’il a au mois un 0 dans son voisinage en 4-
connexite. Mais ceci n’est pas suffisant, il faut en plus que l’ensemble des 1 du voisinage en
8-connexite soit 8-connexe et l’ensemble des 0 du voisinage en 8-connexite soit 4-connexe
Les 16 configuration suivantes (Figure 4.16) résume l’ensemble de toutes les configurations
possibles où p est simple (non-essentiel)
Conclusion générale 86
Figure 4.16 : ensemble de points non-essentiels
Notons bien que La suppression massive de points simples amènerait tout objet simplement
connexe à se réduire à un point unique. Pour obtenir le squelette de l’objet, il faut introduire
une propriété supplémentaire. La notion de point terminal doit permettre de conserver les
parties allongées de l’objet.
Définition 4.20 : Un point terminal est un point qui ne possède qu’un seul point objet dans
son voisinage.
L’obtention d’un squelette par amincissement est donc le résultat de la suppression des points
simples non terminaux de l’objet.
Dans une image, un point isolé ou un point intérieur n’est pas un point simple. Cette remarque
est intéressante pour construire un processus de calcul d’un squelette puisqu’il suffit de
s’intéresser aux points de la frontière de l’objet en cours de squelettisation, composé des seuls
susceptibles d’être supprimés.
Conclusion générale 87
Beaucoup de chercheurs se sont intéressés à cette technique. Il existe plus de 300 référence
sur le sujet qu’il est impossible de récapituler : Luisa Lam recense dans [Lam 92] plus de 150
méthodes différentes d’amincissement. La base commune de toutes ces méthodes est la
morphologie mathématique. L’idée est d’amincir l’objet en retirant successivement tous les
points simples de l’objet si cela ne nuit pas à la topologie de l’objet.
La suppression d’un point a lieu sous trois conditions :
ne pas crée de trou dans l’objet.
ne pas coupé d’objet.
ne pas supprimé un point s’il constitue une extrémité de l’ensemble de points
courants (cela afin de préserver les branches du squelette).
Cette reconstruction du squelette possède les qualités suivante : elle conserve l’homotopie
(par construction) et elle travaille entièrement dans l’espace discret.
Les défauts importants sont : d’une part le squelette n’est pas réversible puisque aucune
information de distance n’est jamais conservée, et d’autre part, que les amincissement
successifs lient directement le temps de calcul à l’épaisseur de l’objet.
6.2.2.2 Algorithmes d’amincissement
Un algorithme d’amincissement (ou shrinking algorithm) consiste en la suppression jusqu’à
stabilité de points simples, le résultat obtenu s’appelle un noyau homotopique. Si la
suppression est réalisée de façon séquentielle alors la topologie est préservée ; cela par la
définition même d’un point simple. Si le processus est modifié de façon à ce que certains
points simples soient préservés durant le processus de suppression, il est alors possible de
conserver des caractéristiques géométriques.
Un tel processus s’appelle algorithme de squelettisation (ou thinning algorithm), et le résultat
est appelé squelette. Les points à préserver sont appelés points terminaux ou points
extrémités.
Conclusion générale 88
Etant donné qu’une courbe simple n’est constituée que de points non simples à l’exception de
ses points extrémités, la préservation de ces derniers (points extrémités (ou terminaux) de
courbe) durant un processus de suppression de points simples, préserve les courbes et les
parties de courbes.
Il existe un grand nombre d’algorithmes d’amincissement, chacun produit son squelette avec
des propriétés géométriques spécifiques, souvent lié à une application particulière. Quelques
uns de ces algorithmes sont présents dans [Kong 89] et [Lam 92]. Plusieurs stratégies sont
possibles : séquentielles et parallèles [Chassery 91] [Lam 92].
6.2.2.3 Approche séquentielle
Supposons que la suppression de point simple se fait de manière séquentielle. Alors on teste la
simplicité des points de l’image à squelettiser :
si x est non simple, nous considérons un autre point si x est simple, nous
l’éliminons et obtenons un objet Y. La simplicité du point suivant Y va être
examiné, elle dépend totalement de l’objet courant et du point supprimé
précédemment.
Cette itération est répétée jusqu’à stabilité, i.e. jusqu’à ce qu’il n’y ait plus de
point simple.
Un tel algorithme est décrit par :
Algorithme 4.1 : Schème séquentiel de squelettisation
Repeter
Pour tout point de l’image déterminié selon un balayage séquentiel faire
Si le point est simple alors il est supprimé
(Sinon examiner le point suivant, déterminer par le balayage)
Jusqu’à ce qu’il n’y ait plus de suppression de point durant un balayage complet de l’image.
Conclusion générale 89
Conclusion générale 90
L’approche résultant d’un tel processus de suppression séquentiel de point simple offre
comme avantages la préservation de la topologie (par la définition même d’un point simple),
et la minceur des squelettes (dans le sens qu’ils ne contiennent plus de point simple).
Malheureusement, les algorithmes séquentiels ne sont guère utilisés du fait de leur lenteur par
rapport aux algorithmes parallèles, ou du mauvais centrage des squelettes obtenus [Lohou
02a] [Lam 92].
6.2.2.4 Approche parallèle.
Intuitivement, afin d’être efficace, un algorithme doit être conçu de façon à supprimer en
parallèle plusieurs points [Tsao 81] [Gong 90] [Palagyi 99a] [Palagyi 99b] [Ma 00] [Lohou
02b]. Mais la suppression en parallèle de points simples peut ne pas préserver la topologie
(Figure 4.17) [Lohou 04].Il faut alors mettre en œuvre des stratégies permettant l’élection des
points qu’un algorithme va pouvoir supprimer en parallèle.
Figure. 4.17 : Exemple de suppression parallèle des points simples de l’objet
Nous allons voir avec plus de détail quelques algorithmes qui utilisent l’approche parallèle.
Conclusion générale 91
a) Algorithme de Zhang et Suen [Zhang 84]
C’est un algorithme qui sera utilisé comme une base de comparaison pour les algorithmes de
squelettisation pendant plusieurs années. Cela est dû à sa rapidité et à simplicité. C’est un
algorithme d’abord parallèle de type deux sous-itération. Zhang et Suen introduisent d’autres
critères pour décider si un point P sera éliminé. Le schéma est décrit par l’algorithme 4.2 ci
dessous
Figure 4.18 : Le pixel (i,j) et ses 8 proche voisins
Algorithmes 4.2 : Algorithme de squelettisation Zhang et Suen
Soit le pixel courant P(i,j) figure 4.18.
1) Premiere iteration : le pixel est mis à zero si les cinq conditions suivantes sont satisfaites :
P(i,j) ne doit pas être un pixel de fin de segment
P(i,j) est de connectivité égale à 1.
P(i,j) à au mois 2 voisins et au plus 6 voisins non nuls.
Au moins un des P(i,j+1), P(i-1,j) et P(i,j-1) est nul.
Au moins un des P(i-1,j), P(i+1,j) et P(i,j-1) est nul.
2) Seconde itération : seules les deux dernières conditions changent par rapport à l’étape précédente :
Au moins un des P(i-1,j), P(i,j+1) et P(i+1,j) est nul.
Au moins un des P(i,j+1), P(i+1,j) et P(i,j-1) est nul
Conclusion générale 92
Le nombre de connexité nC d’un pixel P(i,j) peut être défini comme le nombre de transition
d’un pixel black (qui représente l’objet) à un pixel blanc ( fond de l’image) à l’intérieur des 8-
voisin (Figure 4.17)
Malheureusement, cet algorithme comporte des imperfections, relevées par H.E. Lü et P.S.P.
Wang [Lü 86].
PROB1 : si on considère un petit bruit, celui-là peut empêcher une
squelettisation “homogène” et être la cause de la préservation de branches non
désirées.
PROB2 : un deuxième problème est la réduction excessive des lignes obliques
d’épaisseur 2, en 2 points (Figure 4.20b).
PROB3 : le troisième problème, et non le moindre, est la disparition de certains
motifs : par exemple, le carré de 2×2 points disparaît au bout d’une itération.
Cette remarque intervient également pour des objets de plus grande taille se
réduisant, avec cet algorithme, en un carré de 2×2 points à une certaine
itération ; et disparaissant alors lors de l’itération suivante (Figure 4.20b).
c) Algorithme de Wu et Tsai (WT) [Wu 92]
C’est un algorithme de type fortement parallèle d’un support de 15 points. Le schéma est
décrit par l’algorithme 4.3. Cet algorithme utilise trois séries de templates :
La première permet l’amincissement des rubans horizontaux ou verticaux.
La deuxième permet celui des rubans diagonaux.
La dernière réalise un filtrage intégré, et permet l’élimination de bruit
apparaissant au voisinage de morceaux de lignes droites.
Conclusion générale 93
Malheureusement, comme on le remarque dans la figure 4.20c, le carré 2×2 n’est pas
préservé (PROB3), A. Stewart [Stewart 94] a montré que ce problème provient des motifs (e),
(f), (h), (i).
Algorithme 4.3 : Algorithme de Wu et Tsai (WT)
Répéter
Supprimer en parallèle les points P de l’objet qui vérifient
au moins l’un des motifs suivants :
Le symbole “x” signifie “appartient ou non à l’objet”, au moins l’un des deux symboles “y”
apparaissant dans un motif doit être un point du complémentaire de l’objet.
Jusqu’à ce qu’il n’y ait plus de point supprimé durant une itération.
d) Algorithme de Huang & al [Huang 03]
Huang et al. [Huang 2003] ont proposé un algorithme d'amincissement fortement parallèle, en
une seule itération. C’est un algorithme purement local, pour les règles de suppression de
point il emploie un masque de taille 3×3 (Figure 4.18). Il utilise des masques de taille 3x4,
Conclusion générale 94
4x3 et 4x4 pour préserver la connectivité. cet algorithme est plus efficace que ceux de Zhang
et Wu comme illustre la figure 4.20.
Figure 4.19 : Règles de suppression des points par l’algorithmes de Huang
Conclusion générale 95
Algorithme4.4 : Algorithme d’amincissement de Huang et al.
répéter
1) Supprimer en parallèle les points P de l’objet qui vérifient au moins l’un des
motifs représenté dans la figure 4.19
2) Le point P est conservé, s’il ne correspond à aucun des motifs suivant :
Jusqu’à ce qu’il n’y ait plus de point supprimé durant une itération
Figure 4.20 : Application des algorithmes d’amincissement parallèle à une image contenant des modèles géométriques simples, a) image initiale, b) Squelette utilisant l’algorithme Zhang et Suen, c) Squelette utilisant l’algorithme Wu et Tsai, d) Squelette utilisant l’algorithme Huang et al.
Conclusion générale 96
6.2.3 Squelette à partir de la carte de distance (Transforme de Distance)
La squelettisation à partir de la carte de distance consiste à rechercher, parmi les points d'une
forme, ceux qui sont les plus éloignés du contour. Si pour chaque point de la forme, nous
associons la distance au point du périmètre le plus proche, nous obtenons la carte de distances.
Dans cette représentation, en interprètent la valeur d'un point de la carte de distances comme
l'altitude du point dans un relief topographique (figure 4.21), le squelette correspond à
l'ensemble des points positionnés sur des crêtes. Les points d'une crête sont en effet des
maxima locaux et sont équidistants à deux points au moins du contour. Rechercher ces points
revient donc à rechercher les points du squelette.
Figure 4.21 : Transformé Distance de la forme T
Le problème posé est donc de calculer correctement la carte des distances et de rechercher les
maxima locaux.
Dans ce cas, le squelette est défini comme le lieu des maxima locaux des cartes de distance
[Calabi 68] [Malandain 98]. L’extraction du squelette se fait en deux temps :
Conclusion générale 97
1. On cherche l’axe médian grâce aux maxima locaux de la carte de distance. Ce
sous-ensemble est fin, mais généralement non connexe. Il peut aussi servir de
sous-ensemble initial à partir duquel on peut reconstruire un squelette.
2. On essaie de rendre ce sous-ensemble connexe, en cherchant des
configurations de voisinage dans la carte de distance afin de retrouver des
lignes de crête ou des arêtes de la surface associée [Niblack 92], ou encore
des chemins [Zhou 98] qui vont connecter l’ensemble des maxima locaux.
Les squelettes calculés à partir de la carte de distances sont aussi appelés lignes médianes
[Chassery 91], ou bien encore squelettes pondérés [Sanniti 94a]. Pour obtenir le squelette, il
est possible d’utiliser différents types de distances, capables d’approximer plus ou moins bien
la distance euclidienne. L’utilisation de différentes cartes de distances nécessite l’emploi
d’algorithmes spécifiques pour chacune des métriques.
Arcelli propose une méthode pour calculer un squelette avec la distance d4 [Arcelli 89], avec
la distance d5,7,11 [Arcelli 92], Montanvert avec la distance d8 [Montanvert 87], Saniti Di Baja
avec la distance d3,4 [Sanniti 94a], enfin, Arcelli [Arcelli 93] propose un algorithme pour
calculer le squelette à partir de la distance euclidienne (dE).
L’idéal est de réussir à trouver une méthode capable de trouver le squelette, quelque soit la
distance employée. Dorst [Dorst 86], propose une approche multi-distance pour d4, d8, d2,3,
d5,7,11 et Saniti Di Baja et Thiel [Sanniti 94b] pour d4, d8, d3,4, et d5,7,11.
L’inconvénient de ces approches basées sur la carte de distance est :
la génération d’un nombre assez important de barbules [Arcelli 85]
le squelette résultant n’est pas nécessairement homotope suivant le méthode
de reconstruction et la distance utilise [Fernandez 96].
N’est pas nécessairement fin : suivant le choix du seuil et des méthodes de
reconnections des maxima locaux), Mais selon la distance utilisée, le
Conclusion générale 98
squelette peut être d’une épaisseur supérieure à 1 en certains endroits [Dorst
86].
Sensibilité au bruit : l’emploi des maxima locaux de la carte des distances
crée des squelettes sensibles aux bruits ce qui exige un post-traitement qui
consiste a éliminé les barbules [Arcelli 85] [Fernandez 96].
e) Algorithme de Transforme de Distance [Arcelli 88]
L'image est décrite en utilisant un système de coordonné intrinsèque, chaque pixel est spécifié
en donnant sa distance par rapport à ces plus proches voisins. Le squelette est défini comme
un ensemble de point dont la distance par rapport à ces proches voisins est un maxima local.
Un tel squelette est décrit par l’algorithme suivant :
Algorithme 4.5 : Algorithmes de la Transformé Distance
1) Transforme de distance
)1),;,((;),(Immin),(Im),(Im 1),;,(
0 ≤∆+= −∆
nmjinmajiajia knmji
k
,.....2,1),(Im),(Im 0 ==∆
kjiajia
ou )n,m;j,i(∆ est la distance entre le pixel (i,j) et (m,n)
la transformer est obtenu quand k équivaut à l'épaisseur maximum de la forme
2) le squelette est l’ensemble des points qui vérifie
)1)n,m;j,i((;)m,n(aIm)j,i(aIm:)j,i(kk
≤∆≥
Conclusion générale 99
Les figures 4.22 et 4.23 montrent des exemples qui illustrent l’algorithme de squelettisation
par la méthode de transforme de distance,
Figure 4.22 : Squelettisation par l’algorithme de transformé distance, (a) forme initiale, (b), (c) et (d) calcul de la transformée de la Distance de a, e) maxima locaux de la Transformée Distance , f) squelette
Figure 4.23 : Squelette obtenu par transformé de distance, (a) formes initial, (b) transformé de distance, (c) maxima locaux de la Transformée Distance
Conclusion générale 100
Conclusion
Dans les sections précédentes, nous avons introduit la notion de squelette autour de laquelle
s’organise la deuxième partie du présent mémoire. Nous avons montré son intérêt en analyse
d’images et énuméré ses propriétés les plus connues. Le squelette défini dans le plan continu
est mince, centré dans la forme et homotope
Ensuite, Nous avons présenté les différentes techniques d’extraction du squelette, parmi
lesquelles nous avons distingué les méthodes continues et discrètes. Nous avons passé en revu
plusieurs algorithmes pour les deux grande classes de squeletissation, à savoir l’algorithme
Transformé Distance et les algorithmes d’amincissement parallèle. Retenons également que
c’est à partir de petits objets synthétiques et simple (par exemple, un carré 2x2 pixels, un
ruban d’epaisseur 2) qu’a été mise en évidence la plupart des critères permettant d’évaluer un
algorithme de squelettisation.
En conclusion, aucune classe ne prévaut ; les avantages de l’une sont les inconvénients
d’une autre, au niveau soit de l’algorithme en lui même, soit des points qu’il supprime. En
plus, on remarque que tous les algorithmes de squelettisation sont applicables pour des images
binaires non bruitée uniquement. C’est ce qui a motivé notre recherche d’une méthode de
squelettisation dans un autre cadre mathématique : l’approche statistique.
Bibliographie 101
Bibliographie
[Abu- mostafa 84] Y. S. Abu-mostafa and D. Psaltis, “Recognitive aspects of moment invariants”, IEEE Trans. Pattern Analysis Machine Intelligence, vol. 6, pp. 698-706, Nov. 1984.
[Abu-Mustapha 85] Y. S. Abu-Mustapha and D. Psaltis,” Image Normalization by Complex Moments,” IEEE Trans. Patt. Anal. Matchine Intell., vol PAMI-7, pp. 46-55, Jan 1985
[Alt 62] F. L. Alt, “Digital pattern recognition by moments,“ Jnl. Of the Ass. For Computing Machinery, Vol. 9, No. 2, pp. 240-258, 1962.
[Arcelli 81] C. Arcelli, l.P. Cordella, and S. Levialdi.” From local maxima to connected skeletons, ” IEEE Transactions on pattern analysis and machine intelligence, PAMI, vol. 3, no. 2, pp. 134-142, 1981
[Arcelli 85] C. Arcelli and G. Sanniti Di Baja.” A width-independent fast thinning algorithm,”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 7, pp. 463-474, 1985.
[Arcelli 88] C. Arcelli and G. S. Di Baja, “Feeding local maxima in a pseudo-Euclidian distance transform,” Computer Graphics Vision and Image Processing, vol. 43, pp. 361-367, 1988.
[Arcelli 89] C. Arcelli and G. Sanniti di Baja.” A one-pass two-operation process to detect the skeletal pixels on the 4-distance transform,” IEEE Trans. On PAMI, vol 11, no. 4:pp. 411-414, 1989.
[Arcelli 92] C. Arcelli and G. Sanniti di Baja.” Ridge points in Euclidean distance maps,” Pattern Recognition Letters. Vol. 13, pp. 237-243. 1992
[Arcelli 93] C. Arcelli and G. Sanniti di Baja.” Euclidean skeleton via centre-of-maximal-disc extraction,” Image and Vision Computing, vol. 11, no. 3, pp. 163-173, 1993
[Arcelli 95] C. Arcelli and G. Ramella.’’ Finding grey-skeletons by iterated pixel removal,’’ Image and Vision Computing, Vol. 13, no. 3, pp. 2033-2045, 1995
[Arcelli 96] C. Arcelli and G. Ramella.’’ Sketching a grey-tone pattern from its distance transform,’’ Pattern Recognition, Vol. 29, no. 12, pp. 2003-2045, 1996
Bibliographie 102
[Arcelli 98] C. Arcelli and L. Serino. Parallel lowering of digital pictures by topology preserving operations. In Proceedings Fourteenth International Conference on Pattern Recognition, pp. 1601–1603, Brisbane, Australia, August 1998.
[Arcelli 99] C. Arcelli.” Topological changes in grey-tone digital pictures,” Pattern
Recognition, vol. 32, pp. 1019–1023, 1999.
[Attali 94] D. Attali, P. Bertolino, and A. Montanvert.” Using polyballs to approximate shapes and skeletons,” In International Conference on Pattern Recognition, Jerusalem, Israël, October 1994.
[Attali 95] D. Attali.” Squelettes et graphes de Voronoi 2D et 3D,” Thèse de doctorat, Université Joseph Fourier Grenoble I, octobre 1995.
[Bailey 96] P. R. Bailey and Srinath, “Orthogonal moment feature for use with parametric classifiers,” IEEE Trans. Pattern Anal. Machine Intell., vol. 18, pp. 359-396, 1996.
[Baranger -91] J. Baranger, “Analyse Numerique”, Hermann, Editeurs des Sciences et des Arts pp. 47-90, 1991.
[Belkasim 91] S. O. Belkasim, “Pattern recognition with moment invariants—A comparative study and new results,” Pattern Recognition., vol. 24, no. 12, pp. 1117–1138, 1991.
[Bertrand 96] G. Bertrand, J. C. Everat, and M. Couprie.” Topological approach to imagesegmentation,’’ In SPIE Vision Geometry V, Vol. 2826, pp. 65-76, 1996
[Bertrand 97] G. Bertrand, J.-C. Everat, and M. Couprie.” Image segmentation through operators based upon topology,” Journal of Electronic Imaging, vol. 6, no. 4, pp. 395–405, 1997.
[Beucher 90] S. Beucher.’’ Segmentation d’images et morphologie mathématique,’’ PhD thesis, Ecole Nationale des Mines de Paris, 1990.
[Bezerra 00] F. N. Bezerra and M. Couprie.” Reducing anisotropy of topological operators for grayscale images,” In Proceedings of Vision Geometry IX, vol. 4117, pp. 46–57. SPIE, San Diego, USA, July 2000.
[Blum 64] H Blum.” A transformation for extracting new descriptors of shape,” Symposiun on Models for the Perception of Speech and Visual Form, November 1964.
[Blum 67] H. Blum.” A transformation for extracting new descriptors of shape,” In Wathen Dunn, editor, Proceedings of Models for the Perception of Speech and Visual Form, pp. 362-380. MIT Press, 1967.
[Blum 78] H. Blum and R. N. Nagel;” Shape description using weighted symmetric axis features,” Pattern Recognition, Vol. 10 pp. 167-180, 1978.
Bibliographie 103
[Borgefors 84] G. Borgefors.” Distance transformations in arbitrary dimensions,” Computer Vision, Graphics and Image Processing, vol. 27, pp. 321-345, 1984.
[Brandt 92a] J. W. Brandt.” Describing a solid with the three-dimensional skeleton,” SPIE, Curves and Surfaces in Computer Vision and Graphics III, vol. 1830, pp. 258-269, 1992.
[Brandt 92b] J. W. Brandt and V. Ralph Algazi.” Continuous skeleton computation by voronoi diagram,” CGVIP: Image Understanding, vol. 3, no. 3, pp. 329-338, 1992.
[Brandt 94a] J. W. Brandt.” Convergence and continuity criteria for discrete approximations of the continuous planar skeleton,” CGVIP: Image Understanding, vol. 59, no. 1, pp. 116-124, 1994.
[Brandt 94b] J. W. Brandt and V. Ralph Algazi.” Continuous skeleton computation by voronoi diagram,” CGVIP: Image Understanding, vol. 3, no. 3, pp. 329-338, 1992.
[Calabi 65] L. Calabi.” A study of the skeleton of plane gures” Technical Report 60429,sr-2, Parke Mathematical Laboratories, December 1965.
[Calabi 68] L Calabi and W. E. Hartnett.” Shape recognition, pairie fires, convex deficiencies and skeletons,” The American Mathematical Monthly, vol. 75, no. 4, pp. 335-342, 1968.
[Campenout 88] J. M. Van Campenout, and T. Cover, “Maximum entropy and conditional probability,” IEEE trans. on Information theory, II, vol. 27, no. 4, Jul. 1988.
[Chassery 91] J.M. Chassery and A. Montanvert.” Géométrie discrète en analyse d'images,” Hermès, 1991.
[Choi 02] S. W. Choi and H. Seidel.” Linear one-sided stability of mat for weakly injective 3d domain,” In 7th ACM symposium on solid modeling and applications, Saarbrcken, Germany, 2002.
[Chuang 91] J.-H. Chuang and N. Ahuja.” Skeletonization using a generalized potential-field model,” Proc. Artificial Intelligence and Computer Vision , AICV, pp. 223-237, 1991.
[Coeurjolly 03] D. Coeurjolly.” d-dimensional reverse Euclidean distance transformation and Euclidean medial axis extraction in optimal time,” In Proceedings of DGCI, LNCS, Springer Verlag, vol. 2886, pp. 327-337, 2003.
[Couprie 99] M. Couprie, F. N. Bezerra, and G. Bertrand.” Grayscale image processing using topological operators,” In Proceedings of Vision Geometry VIII, vol. 3811, pp. 261–272. SPIE, Denver, USA, July 1999.
[Danielsson 80] P.E. Danielsson.” Euclidean distance mapping,” Computer Graphics and Image Processing, vol. 14, pp. 227-248, 1980.
Bibliographie 104
[Davies 82] E. R. Davies and A. P. N. Plummer, “Thinning algorithms: A critique and a new methodology,” Pattern Recognition., vol. 14, no. 1, pp. 53-63, 1981.
[Dawoud 03] A. Dawoud, M. Kamel, “New Approach for the Skeletonization of Handwritten Characters in Gray-Level Images,” ICDAR, vol. 2, no. 2, pp. 1233-1237, 2003.
[Dawoud 05] A. Dawoud, M. Kamel, ”Natural Skeletonization: New Approach For The Skeletonization Of Handwritten Characters,”. Int. J. Image Graphics, vol. 5, no. 2, pp. 267-280, 2005.
[Dimitrov 03] P. Dimitrov.” Flux invariants for shape. Master's thesis,” McGill University, Montréal, Québec, Canada, July 2003.
[Djafari 90] A. M. Djafari and G. Demoment,” Estimating priors in maximum entropy image processing,” Proc. of ICASSP 1990, pp:2069-2072, 1990.
[Djafari 94] A. M. Djafari,“ Maximum d’entropie et problemes inverses en imagerie” Traitement du Signal, Vol. 11, No. 2, pp. 87-116, 1994.
[Dokladal 00] P. Dokladal.” Grey-Scale Image Segmentation: a Topological Approach,” PhD thesis, University of Marne-la-Vallée, France and University of Technology of Brno, Czech Republic, January 2000.
[Dorst 86] L. Dorst.“ Pseudo-euclidean skeletons,” In Eighth International conference on Pattern Recognition, Paris, pp. 286-288. IEEE Computer Society Press, 1986.
[Dudani 77] S. A. Dudani “Aircraft identification by moment invariants,” IEEE Trans. On Computers, Vol. 26, No. 1, pp. 39-45, 1977.
[Dunn-74] J. Dunn, “A fuzzy relative to the ISODATA Process and ist use in detecting compact well-separated clusters”, J. cybernetics, vol. 3, pp. 32-75, 1974.
[Dyer 79] C.R. Dyer and A. Rosenfeld.” Thinning algorithms for gray-scale pictures,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 1, no. 1, pp. 88–89, 1979.
[Ellis-85] R. S. Ellis, “Entropie, Large Deviations and Statistical Mechanics”, Springer Verglas, 1985.
[Everat 96] J.-C. Everat G. Bertrand and M. Couprie.” Topological approach to image segmentation,” In Proceedings of Vision Geometry V, vol. 2826, pp. 65–76. SPIE, Denver, USA, 1996.
[Everat 97a] J. C. Everat and G. Bertrand.” New topological operators for segmentation,” In Proceedings of ICIP’96, IEEE Signal Processing Society, vol. III, pp. 45–48, Lausanne, Switzerland, 1997.
Bibliographie 105
[Everat 97b] J.-C. Everat, G. Bertrand, and M. Couprie.” Reconstruction operators for image segmentation,” In Proceedings of 3rd International Workshop on Vision Form., IAPR, Capri, Italy, 1997.
[Everat 97b] J.-C. Everat, G. Bertrand, and M. Couprie.” Reconstruction operators for image segmentation,” In Proceedings of 3rd International Workshop on Vision Form., IAPR, Capri, Italy, 1997.
[Everat 97c] J.-C. Everat. “ Topologie des coupes et segmentation d’images par extraction de minima,” PhD thesis, Université Paris 7, 1997.
[Fernandez 96] S. Fernández-Vidal.” Squelettes et autres outils de topologie discrète; applications à l'imagerie médicale 3D,” PhD thesis , l’ESSI ,Septembre 1996
[Flusser 93] J. Flusser, “Pattern recognition by affine moment invariants,” Pattern Recognition., vol. 26, no. 1, pp. 167–174, 1993.
[Fol-Leymarie 03] F. Fol-Leymarie.” Three-dimensional shape representation via schock flows,” PhD thesis, Brown University, Providence, Rhode Island, USA, May 2003.
[franti-95] P. Franti and O. Nevalainen, “Block truncation coding with entropy coding”, IEEE Trans. Communication, Vol. 43, n. 2, pp. 1677-1695, 1995.
[Fritsch 94] D. S. Fritsch, S. M. Pizer, B. S. Morse, D. H. Eberly, and A. Liu.“ The multiscale medial axis and ist applications in image registration,” PatternRecognition Letters, vol. 15, pp. 445-452, May 1994
[Gerardo 94] B. Gerardo and X. Liu, “A Least biased fuzzy clustering method,” IEEE Trans. Pattern. Anal. Machine. Intell, vol. 16, no. 9, pp. 954-960, Sept 1994
[Gerardo-94] B. Gerardo and X. Liu, “A least biaised fuzzy clustering method”, IEEE trans. Patt. Anal. Machine intell., vol. 16, n. 9, pp. 954-960, sept. 1994.
[Ghosal 93] S. Ghosal and R. Mehrotra, “Orthogonal moment operators for subpixel edge detection,” Pattern Recognition, vol. 26, no. 2, pp. 295–306, 1993.
[Giasu-77] S. Giasu, “information theory with applications”, Mc-Graw Hill, 1977.
[Giblin 02] P. Giblin and B. B. Kimia.” Transitions of the 3D medial axis under a one-parameter family of deformations,” In Proceedings of European Conference Computer Vision (ECCV 2002), volume LNCS 2351, pages 719-734, Copenhagen, Denmark, May 2002. Springer Verlag.
[Goldak 91] J. A. Goldak, Xinhua Yu, Alan Knight, and Lingxian Dong.” Constructing discrete medial axis of 3-d objects,” International Journal of Computational Geometry and Applications, vol. 1, no. 3, pp. 327-339, 1991.
Bibliographie 106
[Gong 90] W. Gong and G. Bertrand.” A simple parallel 3D thinning algorithm,” In International Conference on Pattern Recognition, pp. 188–190, 1990.
[Goshtasby 85] A. Goshtasby, “Template matching in rotated images,” IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-7, pp. 338–344, Mar. 1985.
[Han 97] N. H. Han, C. W. La, and P. K. Rhee, “An Efficient Fully Parallel Thinning Algorithm,” in Proc. IEEE Int. Conf. Document Analysis and Recognition, vol. 1, pp. 137-141, 1997.
[Hartnett 65] W.E. Hartnett.“ Plane gures: Their skeletons and quench functions,” Technical Report 60429, sr-3, Parke Mathematical Laboratories, October 1965.
[Heywood 95] M. I. Heywood, “Fractional central moment method for moment-invariant object classification,” Proc. Inst. Elect. Eng., vol. 142, no. 4, pp. 213–219, 1995.
[Hilditch 69a] J. Hilditch and D. Rutovitz.” Chromosome recognition,” Ann. New York Acad. Sci., vo1. 57, pp. 339-364, 1969.
[Hilditch 69b] C.J. Hilditch.” Machine Intelligence,” chapter Linear skeletons from square cupboards, vol. 4, pp. 403–420. Edinburgh University Press, 1969.
[Hilditch 83] C.J. Hilditch. “Comparison of thinning algorithms on a parallel processor,” Image Vision Computing, Vol. 1, pp.115-132, 1983.
[Hsu 93] H. S. Hsu,” Moment preserving edge detection and its application to image data compression,” Opt. Eng., vol. 32, no. 7, pp. 1596–1608, 1993.
[Hu 61] M. K. Hu, “Pattern recognition by moment invariants, ” Proc. IRE, vol. 49, p. 1428, Sept. 1961.
[Hu 62] M. K. Hu, “Visual pattern recognition by moment invariants, ” IRE Trans. Inform.
Theory, vol. IT-8, pp. 179-187, Feb.1962.
[Huang 03] L. Huang, G. Wan, and C. Liu, “ An Improved Parallel Thinnig Algorithm,” ICDAR, pp. 780-783, 2003.
[Jain 89] A. K. Jain, “Fundamentals Of Digital Image Processing,” Prentice Hall Information And Series 1989.
[jan 01] J.H. Jan and K.S. Hong, “A Pseudo-distance Map Segmentation-freeSkeletonization of Gray-scale Images,” Proc. Int’l Conf. Computer Vision, pp. 18-23, 2001
[Jang 90] B.-K. Jang and R.T. Chin.” Analysis of thinning algorithms using mathematical morphology,” IEEE Trans. of PAMI, vol. 12, no. 6, 1990.
[Jaynes 68] E. T. Jaynes “ Prior probabilities,” IEEE Trans., Vol. SSC-4, pp. 227-241, 1968.
Bibliographie 107
[jaynes 82] E. T. jaynes, “On the rationale of maximum entropy methods,” Proceedings of the IEEE, vol. 70, no. 9, Sept. 1982.
[Jaynes 85] E. T Jaynes “Where do we go from here? Maximum entropy and Bayesian methods in inverse problems,” Vol C.R. Smith and T. Grandy, Jr. (eds.) pp. 21-58, 1985
[Jolion 91] J. M. Jolion, P. Meer, and S. Bataouche, “Robust clustering with application in computer vision,” IEEE Trans. Pattern Anal. Machine Intell., vol. 13, no. 8, pp. 791-802, Aug. 1991.
[Khotanzad 90] A. Khotanzad and Y. H. Hong, Invariant image recognition by Zernike moments, IEEE Trans. Pattern Anal. Machine Intell., vol. 12, pp. 489-498, 1990.
[Kimia 03] B. B. Kimia.” On the role of medial geometry in human vision,” journal of physiology Neurogeometry and visual perception. ;.Vol. 97, Issues 2-3, pp. 155-190, 2003.
[Kirkpatrick 79] D.G. Kirkpatrick.“ Efficient computation of continuous skeletons,” IEEE 20th Annual Symposium on Foundations of Computer Science, pp. 18-27, 1979.
[Kong 89] T. Y. Kong and A. Rosenfeld.” Digital topology : introduction and survey,” Proceedings of Computer Vision, Graphics and Image, vol. 48, pp. 357-393, 1989.
[Kovacs 98] I. Kovacs, A. Fehér, and B. Julesz.” Medial-point description of shape: a representation for action coding and its psychophysical correlates,” Vision Research, vol. 38, pp. 2323-2333, 1998.
[Kundu 91] M.K. Kundu, B.B. Chaudhuri, and D. Dutta Majumder.” A parallel graytone thinning algorithm,” Pattern Recognition Letters, vol. 12, pp. 491–496, 1991.
[Lam 92] L. Lam, S.W. Lee, and C.Y. Suen.” Thinning methodologies - A comprehensive survey,” IEEE Trans. on PAMI, vol. 14, no. 9, pp. 869-885, 1992.
[Lee 82] D. Lee.” Medial axis transformation of a planar shape,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 4, pp. 363-369, 1982.
[Liao 93] S. X. Liao, “Image analysis by moments”, PhD dissertation, University of Manitoba, 1993.
[Liao 96] S. X. Liao and M. Pawlak,” On Image Analysis by Moments,” IEEE Trans. Patt. Anal. Machine Intell., Vol. 18, No 3, pp. 254-266, Mar 1996
[Liao 98]S. X. Liao and M. Pawlak, "On the Accuracy of Zernike Moments for Image Analysis", IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, pp. 1358-1364, 1998
Bibliographie 108
[Liu 93] Y. Liu, R. Fenrich, and S.N. Srihari.“ An Object Attribute Thresholding Algorithm for Document Image Binarization,” Actes de la 2nd Int. Conf. on Document Analysis and Recognition, pp 278-281, Tsukuba, Japon, Octobre 1993
[Lohou 02a] C. Lohou.“ Contribution à l’analyse topologique des images: études d’algorithmes de squelettisation pour des images 2D et 3D selon une approche topologie digitale ou topologie discrète,“ Thèse de doctorat, Université de Marne-la-Vallée, décembre 2001
[Lohou 02b] C. Lohou and G. Bertrand.” A new 3D 6-subiteration thinning algorithm based on p-simple points,” In Achille J.-P. Braquelaire, Jacques-Olivier Lachaud, and Anne Vialard, editors, Discrete Geometry for Computer Imagery (DGCI), vol. 2301, pp. 102–113. Springer, 2002.
[Lohou 04] C. Lohou and G. Bertrand.” A 3-D 12-subiteration thinning algorithm based on p-simple points,” Discrete Applied Mathematics, vol. 139(1–3), pp. 171–195, April 2004.
[Loncaric 98] S. Loncaric.” A survey of shape analysis techniques,” Pattern Recognition, vol. 31, no. 8, pp. 983-1001, 1998.
[Lü 86] H.E. Lü and P.S.P. Wang.” A comment on "a fast parallel algorithm for digital patterns”. Comm. ACM, vol. 29, no. 3, pp. 239–242, March 1986.
[Ma 00] C.M. Ma and S.Y. Wan.“ Parallel thinning algorithms on 3D (18, 6) binary images,” Computer Vision and Image Understanding, vol. 80, pp. 364–378, 2000.
[Maitre-94] H. Maitre, I. Bloch and M. Sigelle, “Spatial entropy : a Tool for controling contexual classification convergence”, IEEE International conference on image processing, vol. II, pp. 212-216, 1994.
[Malandain 98] G. Malandain and S. Fernandez-Vidal.” Euclidean skeletons,” Image and Vision Computing, vol. 16, no. 5, pp. 317–327, April 1998.
[Malvar 89] H. S. Malvar, the LOT: transform coding without blocking effects”, IEEE Trans.
Acoust. Speech, Signal Processing, vol. 37, pp. 553-559, Apr. 1989.
[Markandey 92] V. Markandey and R. J. P. Figueiredo, “Robot sensing techniques based on high dimensional moment invariants and tensors,” IEEE Trans. Robot. Automat., vol. 8, pp. 186–195, Feb. 1992.
[Matheron 88] G. Matheron.” Image Analysis and Mathematical Morphology,” Academic Press, vol. 2, chapter 11 & 12, pp. 217-256. 1988.
[Meyer 79] F. Meyer.” Cytologie quantitative et morphologie Mathématique,” PhD thesis, École des Mines, May 1979.
Bibliographie 109
[Meyer 89] F. Meyer.” Skeletons and perceptual graphs,” Signal Processing, vol. 16, pp. 335-363, 1989.
[Montanari 68] U. Montanari.” A method for obtaining skeletons using a quasi-euclidean distance,” Journal of ACM, vol. 15, pp. 600-624, 1968.
[Montanari 69] U. Montanari.” Continuous skeletons from digitized images” JACM, vol. 16, no. 4, pp. 534-549, 1969.
[Montanvert 87] A. Montanvert.” Contribution au traitement de formes discrètes : squelettes et codage par graphe de la ligne médiane,” PhD thesis, USTMG and INPG, Grenoble, 1987.
[Mukundan 01] R. Mukundan , S.H. Ong and P. Lee, “Image analysis by Tchebechef moments”, IEEE Trans. Image Processing, V. 10, N. 9, PP. 1357-1364, 2001
[Mukundan 92] R. Mukundan, “Estimation of quaternion parameters from two dimensional image moments,” Graph. Models Image Process., vol. 54, no. 4, pp. 345–350, 1992.
[Mukundan 95] R. Mukundan and K. R. Ramakrishnan, “Fast computation of Legendre and Zernike moments,” Pattern Recognit., vol. 28, no. 9, pp. 1433–1442, Sept. 1995.
[Mukundan-98] R. Mukundan and K. R. Ramakrishnan, “Moment functions in image analysis: theory and applications,” World Scientific Publication Co., Singapore, 1998.
[Narayan 86] R. Narayan and R. Nityananda,”Maximum entropy image restoration in astronomy,” Ann. Rev. Astron, Astrophys, Vol. 24, pp. 127-170, 1986.
[Nguyen 94] M. K. Nguyen and A. M. Djafari,” Bayesian approach with the maximum entropy principale in image reconstruction from microwave scattered field data,” IEEE Trans. on Medical Imaging, Vol 13, No. 2, pp. 254-262, 1994.
[Niblack 92] C. W. Niblack, P B. Gibbons, and David W. Capson.” Generating skeletons and centerlines from the distance transform,” Computer Vision, Graphics, and Image Processing, vol. 54, no. 5, pp. 420-437, September 1992.
[Niblak 86] W. Niblack,” A introduction to Digital Image Processing,” Englewood Cliffs, N. J., Prentice Hall, pp. 115-116, 1986
[Ogniewicz 92] R. Ogniewicz and M. Ilg.” Voronoi skeletons: Theory and applications,” In ComputerVision and Pattern Recognition, IEEE Computer Society Press, pp. 63-69. 1992.
[Ogniewicz 93a] R. L. Ogniewicz, G. Székely, M. Naf, and Olaf Kubler.” Medial manifolds and hierarchical description of 2d and 3d objects with applications to MRI data of the human brain,” In Proceedings of the 8th Scandinavian Conference on Image Analysis (SCIA'93), pp. 875-883, Tromso, Norway, May 1993.
Bibliographie 110
[Ogniewicz 93b] Robert L. Ogniewicz.“ Discrete Voronoi skeletons,” PhD thesis, ETH-Zurich, Switzerland, 1993.
[Ogniewicz 94] Robert L. Ogniewicz.“ Skeleton-space: a multiscale shape description combining region and boundary information,” In Proceedings of Computer Vision and Pattern Recognition, pp. 746-751, Seattle, WA, june 1994.
[Ogniewicz 95] R.L. Ogniewicz and O. Kubler, “Hierarchic Voronoi Skeletons,” Pattern
[Pal 89] S. K. Pal.” Fuzzy skeletonization of an image,” Pattern Recognition Letters, vol. 10, pp. 17– 23, 1989.
[Palagyi 99a] K. Palagyi and A. Kuba.” Directional 3D thinning using 8subiterations,” In Discrete Geometry for Computer Imagery (DGCI), vol. 1568, pp. 325–336. Springer, 1999.
[Palagyi 99b] K. Palagyi and A. Kuba.” A parallel 3D 12-subiteration thinning algorithm,” Graphical Models and Image Processing, vol. 61, pp. 199–221, 1999.
[Parker 93] J.R. Parker, C. Jennings, and A.G. Salkauskas.“ Thresolding Using an Illumination Model,” Actes de la 2nd Int. Conf. on Document Analysis and Recognition, pp 270-273, Tsukuba, Japon, Octobre 1993
[Pavlidis 93] T. Pavlidis.” Threshold Selection Using Second Derivatives of the Gray Scale Image,” Actes de la 2nd Int. Conf. on Document Analysis and Recognition, pp 274-277,Tsukuba, Japon, Octobre 1993
[Pawlak 92] M. Pawlak, “On the reconstruction aspects of Moment descriptors”, IEEE Trans.
Information Theory, vol. 38, no. 6, pp. 1,698-1,708, Nov 1992.
[Pizer 03] S. M. Pizer, K. Siddiqi, G. Szekely, J. M. Damon, and S.W. Zucker.” Multiscale medial loci and their properties,” International Journal of Computer Vision, vol. 55, no.2, pp. 155-179, 2003.
[Prockop 92] R. J. Prockop and A. P. Reeves, “ A survey of moment-based techniques for unoccluded object representation and recognition,” Graphical Models and Image Processing, vol. 54, no. 5, pp. 438-460, Sept. 1992.
[Qjidaa 99a] H. Qjidaa and L. Radouane, “Robust line fitting in a noisy image by the method of moments,” IEEE Trans. Pattern. Anal. Machine Intell., vol. 21, pp. 1216-1223, 1999.
[Qjidaa 99b] H. Qjidaa.“Optimisation de la méthode des moments par le principe du maximum d’entropie : applications en traitement d’images et en analyse des données,“ Thèse de Doctorat, Faculté des science Dhar El Mehrez Fes.
Bibliographie 111
[Remy 03] E. Remy and E. Thiel.” Look-up tables for medial axis on squared Euclidean distance transform,” In Proceedings of DGCI, LNCS, Springer Verlag, vol. 2886, pp. 224-235, 2003.
[Robert 91] C. Robert, “Modèles statistiques pour l’intelligence artificielle”, collection techniques stochastiques Masson, Paris, 1991.
[Rosenfeld 66] A. Rosenfeld and J.L. Pfaltz.” Sequential operations in digital picture processing,” Journal of the Association for Computing Machinery, vol. 13, no. 4, pp. 471–494, 1966.
[Rosenfeld 79] A. Rosenfeld, “Digital topology,” American Mathematical Monthly, Vol. 86, pp.621-630, 1979.
[Rosenfeld 82] A. Rosenfeld and A. C. Kak.” Digital image processing,” Academic Press, second edition, 1982
[Rosenfeld 84] A. Rosenfeld.” The fuzzy geometry of image subsets,” Pattern Recognition Letters, vol. 2, pp. 311–317, 1984.
[Ruspini-69] E. H. Ruspini, “A new approach to clustering”, Information and control, vol. 15, n. 1, pp. 22-32, 1969.
[Ruspini-70] E. H. Ruspini, “Numerical method for fuzzy clustering”, information sciences, vol. 2, n. 3, pp. 319-350, 1970.
[Sadjadi 80] F. A. Sadjadi, “Three dimensional moment invariants,” IEEE Trans. On PAMI, Vol. 2, No. 2, pp. 127-136, 1980
[Sanniti 94a] G. Sanniti di Baja.” Well-shaped, stable and reversible skeletons from the (3,4)-distance transform,” Journal of Visual Communication and Image Representation, vol. 5, pp. 107-115, 1994.
[Sanniti 94b] G. Sanniti di Baja and E. Thiel.” Computing and comparing distance-driven skeletons,” In C. Arcelli et al., editors, Aspects of Visual Form Processing, pp. 465-486. World Scientific, Singapore, 1994.
[Schmitt 93] M. Schmitt and Juliette Mattioli.“ Morphologie mathématique,” Collection logique mathématiques informatique. Masson, 1993.
[Serra 82] J. Serra.” Image analysis and mathematical morphology,” Academic Press, London, 1982.
[Serra 92] J. Serra. Skeleton decompositions. SPIE,” Image Algebra and Morphological," Image Processing III, vol. 1769, pp. 376-386, 1992.
Bibliographie 112
[Shannon 48] C. E. Shannon et W. Weaver,“ The mathematical theory of communication,” Bell System Technical Journal, Vol. 27, pp. 379-423, 1948.
[Shih 91] F. Y. Shih and Christopher C. Pu.” A maxima-tracking method for skeletonization from euclidean distance function,” In IEEE Int. Conf. on Tools for AI, vol. 4, pp. 246-253, 1991.
[Siddiqi 02] K. Siddiqi, S. Bouix, Allen Tannenbaum, and Steven W. Zucker.” Hamilton-jacobi skeletons, “ International Journal of Computer Vision, vol. 48, no. 3, pp. 215-231, 2002.
[Smith 71] F. W Smith and M. H. Wright,” Automatic ship photo interpretation by the method of moments,” IEEE Trans. On Computers, Vol. 20, No. 9, pp. 1089-1095, 1971.
[Stewart 94] A. Stewart.” A one-pass thinning algorithm with interference guards,” Pattern Recognition Letters, vol. 15, pp. 825–832, August 1994.
[Svensson 99] S. Svensson, I. Nystrom, G. Borgefors, “On reversible skeletonization using anchor points from distance transforms,” Int. Journal of Visual Communication and Image Representation, vol. 10, pp.379-397, 1999.
[Székely 92] G. Székely, Ch. Brechbuhler, R. Ogniewicz, and T. Budinger.“ Mapping the human cerebral cortex using medial manifolds,” Visualization in Biomedical Computing, vol. 1808, pp. 130-144, Chapel Hill, North Carolina (USA). SPIE, 1992.
[Talbot 92] H. Talbot and L. Vincent.” Euclidean skeletons and conditional bisectors,” SPIE Visual Communications and Image Processing, vol. 1818, pp. 862-876, 1992.
[Teage 80] M. R. Teage,” Image Analysis via the General Theory of Moments,” J. opt. Soc. Amer., vol 70, pp. 920-930, 1980
[Teh 86] C. H. Teh and R.T. Chin, “On digital approximation of moment invariants,” Comput. Vision, Graphics, Image Processing, vol. 33, pp. 318-326, 1986.
[Teh 88] C. H. Teh and R.T. Chin, “On image analysis by the methods of moments,” IEEE
Trans. Pattern Anal. Machine Intell., vol. 10, pp. 496-512, July 1988.
[Tek 99] H. Tek and B. B. Kimia.” Symmetry maps of free-form curve segments via wave propagation,” In Proceedings of the Fifth International Conference on Computer Vision (ICCV'99), vol. 1, pp. 362-369, Corfu, Greece, September 1999.
[Thiel 94] E. Thiel. ” Les distances de chanfrein en analyse d'images : fondements et applications, ” PhD thesis, Université Joseph Fourier (Grenoble I), 1994.
[Trier 95] O. D. Trier, A. K. Jan,” Goal-Directed Evaluation of Binarization Methods,” IEEE Trans. On Patt. Anal. And Match. Intell., vol. 17, no. 12, pp 1191-1201, 1995
Bibliographie 113
[Tsao 81] Y.F. Tsao and K.S. Fu.” A parallel thinning algorithm for 3d pictures,” Computer Graphics and Image Processing, vol. 17, pp. 315-331, 1981.
[Tsao 82] Y.F. Tsao and K.S. Fu.” A general scheme for constructing skeleton models,” Inform. Sci., pp. 53–87, 1982.
[Verwer 88] B. H. Verwer.“ Improved metrics in image processing applied to the Hilditch skeleton,” In Ninth International Conference on Pattern Recognition, Washington, DC, Computer Society Press, pp. 137-142, 1988
[Verwer 93] B. Verwer, L. Van Vliet and P. Verbeek., “ Binary and Grey-Value skeletons,” International Journal of Pattern Recognition and Artificial Intelligence, vol. 7, pp. 1287-1308, 1993.
[Vincent 90] L. Vincent. ” Algorithmes morphologiques à base de files d'attente et de lacets. Extension aux graphes, ” PhD thesis, Ecole nationale supérieure des mines de Paris, 1990.
[Whitaker 94] R. Whitaker and G. Gerig. Vector-valued diffusion. In Bart M. ter Haar Romeny, editor,” Geometry-Driven Diffusion in Computer Vision,” of Series on Computational Imaging and Vision, vol. 1, pp. 93-134. Kluwer Academic Publishers, October 1994
[Wong 78] R. Y. Wong and E. L. Hall “Scene matching with invariant moments,” Computer Vision Graphics and Image Processing, Vol. 8, No. 1, pp. 16-24, 1978.
[Wu 92] R.-Y. Wu and W.-H. Tsai.“ A new one-pass parallel thinning algorithm for binary images,” Pattern Recognition Letters, vol. 13, pp. 715–723, October 1992.
[Xia 89] I. Xia.” Skeletonization via the realisation of the _re front's propagation and extintion in digital binary shapes,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 10, pp.1076-1086, 1989.
[Yokoi 73] S. Yokoi, J. Toriwaki, and T. Fukumura,” Topological properties in digitized binary pictures,” Systems Computer Controls, vol.4, pp. 32-39, 1973
[Yu 90] Shiaw-Shian Yu and Wen-Hsiang Tsai.” Anew thinning algorithm for gray-scale images by the relaxation technique,” Pattern Recognition, Vol 23 , no. 10 , pp. 1067-1076, 1990
[Zenkouar 01] K. Zenkouar, H. El Fadili and H. Qjidaa, “The accuracy of Zernike moment computing”, Conference Internationale Telecom 2001, Casablanca, pp.488-495, 2001.
[Zenkouar 03] H. El Fadili, K. Zenkouar and H. Qjidaa, “Lapped Block Image Analysis Via the Method of Legendre Moments,” EURASIP Journal on Applied Signal Processing, vol. 2003, no. 9, pp. 902-913, 2003.
Bibliographie 114
[Zenkouar 05a] K. Zenkouar, H. El Fadili, and H. Qjidaa, "Skeletonization of Noisy Images via the Method of Legendre Moments", Advanced Concepts for Intelligent Vision Systems, springer Verglas, vol. 3708, pp.452-495, September 2005
[Zenkouar 05b] K. Zenkouar , H. EL fadili, H. Qjidaa,” Robust Skeletonization of Handwritten Characters Using Legendre Moment” submitted to in International journal of computational intelligence, International academy of sciences, 2005
[Zenkouar 05c] K. Zenkouar , H. EL fadili, H. Qjidaa,” Novel Method Of Skeletonization Based On Zernike Moment " In Proceedings of the International Conference on Signal and Image Processing IASTED (SIP), Hawaii, USA 2005.
[Zenkouar 05d] K. Zenkouar, H. El Fadili, and H. Qjidaa “Robust Skeletonization of handwritten characters using Zernike Moments,” accepted to International journal on Computer Science and Engineering, vol. 21, n. 1, November 2005.
[Zenkouar 99] K. Zenkouar, “Reconstruction et Compression des Images Binaires et Multiniveaux par la Méthode des Moments Optimisée par Utilisation du Principe de Maximum d’Entropie,” Mémoire DESA, LESSI, Université Sidi Mohamed Ben Abdellah Fès, 1999.
[Zernike 34] F. Zernike, Beugungstheorie des Schneidenverfahrens und seinerverbesserten Form, der Phasenkontrastmethode, Physica, vol. 1, pp. 689-701, 1934.
[Zeyun 04] Y. Zeyun and C. Bajaj, ”A segmentation-free approach for Skeletonization of gray-scale images via anisotropic vector diffusion” Proceedings IEEE International Conference on Copmuter Vision and Pattern Recognition (CVPR), Vol. 1, pp.415-420, Washington, 2004.
[Zhang 84] T.Y. Zhang and C.Y. Suen.” A fast parallel algorithm for digital patterns.,” Comm. ACM, vol. 27, no. 3, pp. 236–239, March 1984.
[Zhou 98] Y. Zhou, A. Kaufman, and A. W. Toga.” 3D skeleton and centerline generation based on an approximate minimum distance field,” International Journal of Visual Computer, vol. 14, no. 7, pp. 303–314, 1998.
[Zhuang 87] X. Zhuang, K. B. Yu and R. M. Haralick,” A differencial equation approach to maximum entropy image reconstruction,” IEEE Trans. on Acoustics Sounds and Signal Processing, Vol. ASSP-35. pp. 208-217, 1987
[Zhuang 91] X. Zhuang, R. M. Haralick and Y. Zhao, “Maximum entropy image reconstruction,” IEEE Trans. On Signal Processing. vol. 39, no. 6, pp. 1478-1480, Jun. 1991.
[Lam 95] L. Lam and C. Y. Suen,”An evaluation of parallel thinning algorithms for character recognition,” IEEE, TPAMI, Vol. 17, No. 9, pp. 914-919,1995
115
![C] Vérificat'on urnquement pour les flèches po sitwes C ... · 26.09.2014 · Redistribution des moments dÉppui Réduire les moments d Sppu de pourELU.ACC 10 qchler Autodesk Robot](https://img.pdfslide.fr/doc/110x75/5b9a0b3d09d3f294728d09f7/c-verificaton-urnquement-pour-les-fleches-po-sitwes-c-26092014.jpg)
