Chapitre 2. Etat de l'art sur la reconstruction des
images hv-convexes
Appliquer l'opération de bascule.
Fin
L'application de l'algorithme évolutionnaire [25] sur
la première classe de test image concernant les images hv-convexe de
taille 40 * 40, a généré 10 images hv-convexe et chaque
image est constituée par trois ou quatre objets hv-convexe. Dans cette
classe image, la fonction d'évaluation est le nombre de '1'adjacents et
le test d'essai est fait sur 10 images, Les résultats de l'application
de cet algorithme sont illustrés dans la table ci-dessous, La
reconstruction est parfaite lorsqu'il y a reconstruction de la même image
origine. La table visualise aussi le nombre d'exécutions concernant la
reconstruction parfaite, le temps moyen d'exécution des programmes est
exprimé en minutes et le nombre moyen de générations avant
de retrouver la solution optimale c'est à dire la meilleure
reconstruction.
Lorsque l'algorithme qui ne donne pas une reconstruction
parfaite c'est-à-dire très différente à l'image
originale. Cette reconstruction est une solution de mauvaise qualité.
TAB. 2.1 -Résultat de Reconstruction
des images hv-convexe
|
Image
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
Parfait
|
9
|
5
|
8
|
8
|
9
|
6
|
6
|
6
|
6
|
6
|
|
Temps exécution
|
25.6
|
16.6
|
15.5
|
8.8
|
8.5
|
10.8
|
17.7
|
17.7
|
8.8
|
15.7
|
|
Moyenne
|
|
|
|
|
|
|
|
|
|
|
|
Nombre moyenne de génération
|
24.6
|
17.3
|
18.5
|
14.8
|
15.8
|
18.5
|
30.2
|
15.0
|
21.0
|
23.6
|
Cet algorithme ne donne pas une solution optimale qui converge
vers un optimum locale. En effet les difficultés dans l'optimisation de
problème est expliqué par exemple par l'existence d'une solution
quelconque et d'une solution obtenu dans un optimum local qui ont les
même projections orthogonales et verticales et qui ont des nombres des
'1'voisin différents. Ce problème est dû à
l'existence d'un grand nombre de blocs de composants de bascules.
Abdessalem DAKHLI 16
Chapitre 2. Etat de l'art sur la reconstruction des
images hv-convexes
2.3 Conclusion
Ce tour d'horizon nous montre bien qu'il y a peu de
résultats dans le domaine de la tomographie discrète. Dans ce
chapitre, on a décrit le problème de reconstruction des images
binaires sous contraintes de convexité. La matrice binaire à
reconstruire doit respecter les projections orthogonales et la convexité
de l'image. On a constaté que le principe de reconstruction est simple
et facile mais la difficulté réside dans la résolution
pratique de problème. D'après ce tour d'horizon on a
constaté aussi que dans certain cas la reconstruction d'une image
hv-convexe est un problème NP-complet et dans d'autre cas redevient
NP-difficile selon la taille de matrice qui représente l'image et selon
le type d'image convexe à reconstruire. Et on a constaté aussi
l'existence des méthodes heuristiques qui sont algorithmes du temps
polynomial qui donnent une image hv-convex parfait c'est-à-dire presque
l'image réelle concernant les images de petites taille et pour les
autres instances (image de grande taille) la solution est approximative avec un
nombre d'adjacent maximal, en respectant les projections orthogonales. Dans ce
chapitre on a signalé aussi les résultats théoriques et
pratiques de l'utilisation de l'algorithme génétique pour
reconstruire des images convexes. Ces résultats démontrent que
l'algorithme est efficace pour plusieurs différentes fonctions
d'évaluation, correspondant à la reconstruction de plusieurs
problèmes. Ils démontrent aussi une caractéristique
principale de cette approche et sa capacité d'incorporer de diverses
formes de l'information à priori dans la fonction d'évaluation.
Pour mieux améliorer la solution il y a utilisation de
l'opérateur de hillclimb. Cet opérateur permet d'améliorer
la complexité. En effet, lorsque l'algorithme est limité à
une image de la taille réduite cette type d'image rend
l'opération de hillclimb moins approfondie a pu avoir comme
conséquence la complexité améliorée de temps de
l'opération.
On a constaté que le traitement de toutes les
opérations de bascules, se trouvant d'une image, est de
O((mm)2) opération, et aussi le nombre des
applications des opérations bascules est
O((mm)2).
Les résultats montrent aussi que les algorithmes
génétiques sont coûteux en temps de calcul, puisqu'ils
manipulent plusieurs solutions simultanément. C'est le calcul de la
fonction de performance qui est le plus pénalisant, et on optimise
généralement l'algorithme de façon à éviter
d'évaluer trop souvent cette fonction.
De même l'ajustement d'un algorithme
génétique est délicat. L'un des problèmes les plus
caractéristiques est celui de la dérive
génétique, qui fait qu'un bon individu se met, en l'espace
de quelques générations, à envahir toute la population. On
parle dans ce cas de convergence prématurée, qui revient à
lancer à une recherche locale autour d'un minimum... qui n'est pas
Abdessalem DAKHLI 17
| 
