Chapitre 3. Reconstruction des Images Binaires par
recherche Taboue
2
1
3
1
Projections (H,V) Matrice initiale
(Approche Tabou) (b)
|
0
|
0
|
0
|
1
|
|
0
|
0
|
1
|
0
|
|
1
|
1
|
1
|
0
|
|
1
|
0
|
1
|
0
|
Image Reconstruite : Image Application GIMP 2
a) : Reconstruction d'une matrice binaire (solution
initiale) en utilisant l'approche
FIG. 3.2 -Principe de reconstruction d'une image binaire
ver pendant un moment la trace des dernières meilleures
solutions déjà visitées. Ces solutions sont
déclarées tabou, d'où le nom de la méthode. Elles
sont stockées dans une liste de longueur L donnée,
appelée liste taboue. Une nouvelle solution n'est
acceptée que si elle n'appartient pas à cette liste taboue. Ce
critère d'acceptation d'une nouvelle solution évite le
cyclage de l'algorithme, durant la visite d'un nombre de solutions au
moins égal à la longueur de la liste tabou, et il dirige
l'exploration de la méthode vers des régions du domaine de
solutions non encore visitées.
La liste taboue est généralement
gérée comme une liste "circulaire" : on élimine
à chaque itération la solution taboue la plus ancienne, en la
remplaçant par la nouvelle solution retenue. Mais le codage d'une telle
liste est encombrant, car il faudrait garder en mémoire tous les
éléments qui définissent une solution. Pour pallier cette
contrainte, on remplace la liste taboue de solutions interdites par une liste
de "transformations interdites", en interdisant la transformation
inverse d'une transformation faite récemment.
Concernant le critère d'aspiration, le remplacement de
la liste tabou des solutions visitées par la liste des transformations
élémentaires {x, s(x)}
Abdessalem DAKHLI 24
Chapitre 3. Reconstruction des Images Binaires par
recherche Taboue
conduit non seulement à l'interdiction de revenir vers
des solutions
précédentes (on évite le cyclage court),
mais aussi vers un ensemble de solutions dont plusieurs peuvent ne pas avoir
été visitées jusqu'ici. Il est donc primordial de corriger
ce défaut et de trouver un moyen de lever l'interdiction de
l'acceptation d'une transformation élémentaire {x, s(x)}
déjà effectuée (donc appartenant à la liste tabou),
sous un certain critère, appelé critère d'aspiration.
Cette correction permet aussi de revenir à une solution
déjà visitée et de redémarrer la recherche dans une
autre direction. Cette idée est développée dans [1]. On a
fait plusieurs exécutions de l'algorithme, afin de démontrer la
polyvalence de cet algorithme dans la reconstruction des images hv-convexes.
Les résultats expérimentaux sont prévus
pour démontrer la praticabilité et la flexibilité de
l'approche considérée.
Les tests sont exécutés par un pc Pentium IV,
2800 MHz et 512 Mb de mémoire.
3.2.1 Reconstruction des images HV-CONVEXES par la
recherche taboue sans amélioration
L'application de l'algorithme sur la première classe de
test image concernant les images hv-convexe de taille 40 x 40, les images
hv-convexe obtenues est constituée par deux ou plusieurs 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.
Dans l'algorithme on a utilisé le nombre
d'itération égale 100 et la taille de la liste taboue est
égale à 7 mouvements interdits pour éviter le cyclage
pendant la recherche des solutions.
Les résultats de l'application de cet algorithme sont
illustrés dans la table ci-dessous. La reconstruction est parfaite
lorsque le taux de reconstruction est faible c'est-à-dire la
différence entre l'image reconstruite et image originale est faible. La
table ci-dessous visualise les résultats d'exécution concernant
les images hv-convexe de taille 40*40. Le temps d'exécution des
programmes est exprimé en secondes avant de retrouver la solution
optimale c'est -à-dire la meilleure reconstruction.
Test image :Taille 40x40
Abdessalem DAKHLI 25
Chapitre 3. Reconstruction des Images Binaires par recherche
Taboue
TAB. 3.1 -Résultat de Reconstruction des
images hv-convexe
|
Image
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
Nombre
de '1' ad-
jacents de
l'image originale
|
842
|
560
|
684
|
644
|
364
|
384
|
784
|
1564
|
526
|
296
|
|
Nombre
de '1' ad-
jacents de
l'image obtenue par l'algorithme glouton
|
736
|
458
|
601
|
558
|
257
|
271
|
645
|
1508
|
432
|
191
|
|
Temps
|
0,0
|
0,0
|
0,0
|
0,0
|
0,0
|
0,0
|
0,0
|
0,0
|
0,0
|
0,0
|
|
d'exécu-
tion (en
seconde) concernant
la solution
gloutonne..
|
|
|
|
|
|
|
|
|
|
|
|
Nombre
de '1' ad-
jacents de
l'image Reconstruite par Tabou
|
761
|
477
|
618
|
562
|
275
|
292
|
680
|
1518
|
438
|
200
|
|
Temps
|
10,8
|
4,6
|
8,7
|
6,3
|
2,7
|
3,1
|
8,5
|
3,3
|
4,6
|
1,9
|
|
d'exécu-
tion (en
seconde)
|
|
|
|
|
|
|
|
|
|
|
|
Taux de
|
0,761
|
1,484
|
1,298
|
0,906
|
1,7
|
1,578
|
1,225
|
0,351
|
1,644
|
1,702
|
Reconstruction
Abdessalem DAKHLI 26
| 
