Darbon, Jérôme (2005) Composants logiciels et algorithmes de minimisation exacte d'énergies dédiés au traitement des images. PhD thesis Informatique, ENST - INFRES Informatique et Réseaux, ENST.

Full text available as: - these_darbon.pdf ( 7511 Kb )

Licence: Copyright

Abstract

Cette thèse traite principalement de l'optimisation exacte et rapide d'énergies utilisées pour résoudre des problèmes de traitement des images ou de vision par ordinateur. En fonction du type d'énergies considérées, différentes approches sont retenues. Le calcul de coupures minimales, vu comme technique d'optimisation, est la souche commune aux méthodes d'optimisation proposées dans ce manuscrit.
Nous présentons tout d'abord un algorithme de minimisation exacte de la variation totale avec une attache aux données modélisée par une fonction convexe. L'idée de notre approche consiste à reformuler cette énergie avec des champs de Markov binaires associés à chaque ensemble de niveaux d'une image. Nous généralisons ensuite cette approche aux cas des énergies dites "nivellées". Une seconde généralisation, différente de la précédente, considère le cas où les termes de régularisation sont convexes. Nous présentons ensuite un algorithme original et rapide pour le cas des modèles dont les attaches aux données et les termes de régularisation sont des fonctions convexes.
Le cas particulier de la variation totale avec une attache aux données de type $L^1$ est étudié en détail. Nous montrons en particulier que sa minimisation conduit à un filtre invariant par changement de contraste. Cette invariance est une propriété fondamentale des filtres morphologiques. Ce modèle est alors utilisé pour définir un filtre morphologique vectoriel auto-dual.

Table of content

Préambule 1
1 Partie I: algorithmes de minimisation exacte d'une énergie - 1
2 Partie II: Annexes - 2
I Algorithmes de minimisation exacte d'une énergie 5
1 Minimisation exacte de la variation totale 9
1.1 Présentation du problème - 10
1.2 Reformulation en terme d'ensemble de niveaux et de champs de Markov - 11
1.2.1 Reformulation en ensembles de niveaux - 12
1.2.2 Optimisations indépendantes de champs de Markov - 13
1.3 Reconstruction de la solution - 13
1.3.1 Un résultat sur les chaînes de Markov couplées - 14
1.3.2 Condition de convexité pour la reconstruction - 16
1.4 Algorithmes de minimisation - 17
1.4.1 Un algorithme séquentiel - 18
1.4.2 Un algorithme de type "diviser pour régner" - 18
1.4.3 Complexité en temps - 20
1.5 Résultats - 23
1.5.1 Cas d'école - 23
1.5.2 Cas L2 - 23
1.5.3 Cas L1 - 29
1.6 Conclusion - 29
2 Les fonctions nivelées: propriétés et minimisation exacte 33
2.1 Énergies nivelées - 34
2.1.1 Décomposition sur les ensembles de niveaux - 34
2.1.2 Structure des énergies nivelées markoviennes - 39
2.1.3 Quelques propriétés - 40
2.2 Algorithmes de minimisation et expériences - 41
2.2.1 Cas convexe - 42
2.2.2 Reformulation énergétique et représentation par graphe - 42
2.2.3 Satisfaction de la propriété de monotonie - 43
2.2.4 Remarques sur le graphe construit - 45
2.3 Application au débruitage - 46
2.3.1 Le cas du bruit impulsionnel - 46
2.3.2 Le cas d'une loi de Nakagami - 48
2.4 Étude théorique du modèle L1 + TV - 53
2.4.1 Filtres invariants par changement de contraste - 53
2.4.2 Unicité versus non unicité des solutions - 61
2.5 Conclusion - 62
3 Champs de Markov avec des régularisations convexes: propriétés et minimisation exacte 65
3.1 Quelques propriétés des fonctions convexes discrètes - 65
3.2 Champs de Markov avec des a priori convexes - 68
3.2.1 Reformulation énergétique - 68
3.2.2 Représentation par graphe - 70
3.2.3 Optimisation stochastique - 71
3.3 Champs de Markov convexes - 72
3.3.1 Théorème de proximité du minimiseur - 72
3.3.2 Algorithme de calcul de la plus grande pente locale - 75
3.3.3 Premier algorithme de minimisation - 78
3.3.4 Deuxième algorithme: amélioration des performances par un changement d'échelle - 79
3.3.5 Expériences - 81
3.4 Conclusion - 83
4 Retours sur le modèle L1 + TV et la Morphologie Mathématique 85
4.1 Champs de Markov sur les ensembles de niveaux - 86
4.1.1 L'arbre de la "Fast Level Set Transform" - 86
4.1.2 Reformulation markovienne de L1 + TV sur l'arbre de la FLST - 88
4.1.3 Algorithme de minimisation et résultats - 89
4.2 Un filtre morphologique vectoriel - 90
4.2.1 Notre approche à base du modèle L1 + TV - 96
4.2.2 Algorithme de minimisation et résultats - 97
4.2.3 Résultats - 99
4.3 Conclusion - 100
5 Algorithmes rapides pour les filtres morphologiques connectés et attribués 103
5.1 Introduction - 104
5.1.1 Algorithme à base de queue - 105
5.1.2 L'approche par union-find - 107
5.1.3 L'approche par Max-Tree - 110
5.2 Notre algorithme à base de propagation - 111
5.2.1 La phase de propagation - 111
5.2.2 Le canevas pour un filtrage direct - 112
5.3 Complexités théoriques et expériences - 114
5.3.1 Complexité en mémoire - 114
5.3.2 Complexité en temps - 114
5.4 Conclusion - 119
Conclusion 123
II Annexes 127
A Publications 129
B Algorithmes de minimisation de la variation totale 133
B.1 Algorithme par descente de gradient - 133
B.2 Algorithme de projection de Chambolle - 133
C Minimisation de Champs de Markov binaires par coupure minimale 135
D Un cadre générique pour le traitement des images 137
D.1 Introduction - 138
D.1.1 Généricité vis-à-vis des types de données - 139
D.2 Les paradigmes classiques - 140
D.2.1 Matlab et Le langage C avec un type de données universel - 140
D.2.2 Le langage C avec différents types de données - 141
D.2.3 Le langage C avec des macros - 143
D.3 Vers d'autres paradigmes en utilisant C++ - 144
D.3.1 Le mécanisme des patrons de conception - 144
D.3.2 Le modèle à la STL: Vigra - 146
D.3.3 Horus - 148
D.3.4 Olena - 148
D.4 Composition d'algorithmes - 149
D.4.1 Contraintes du praticien et du développeur - 150
D.4.2 Chaîne de traitements - 150
D.4.3 Compositions d'algorithmes - 150
D.5 Les solutions classiques - 152
D.5.1 Les fonctions "templates" - 152
D.5.2 Le codage à la "STL" - 153
D.5.3 Les foncteurs polymorphes directs - 153
D.6 Notre solution à base de déduction de type et de classe imbriquée - 155
D.6.1 Le cas d'une fonction simple - 156
D.6.2 Composition et algorithmes avec variations - 156
D.6.3 Objets pratiques dédiés au traitement des images - 158
D.7 Canevas classiques en traitement des images - 159
D.7.1 Canevas d'algorithmes parallèles - 159
D.7.2 Canevas de convolution généralisée - 160
D.7.3 Canevas d'opérations sur voisinage - 160
D.7.4 Canevas d'opérations séquentielles - 161
D.7.5 Canevas d'opérations à base de queue - 163
D.8 Conclusion - 164
Bibliographie 165

Statistiques de consultation

Repository Staff Only: edit this item