Chapitre 2. Etat de l'art sur la reconstruction des
images hv-convexes
construction qui restera également hv-convexe. De
même, il a remarqué que le problème de reconstruction des
images à partir de plusieurs projections, est NP- difficile [22]. Ce
problème a un codage binaire naturel d'ou l'application de l'algorithme
génétique classique [26], en utilisant une représentation
bit string.
Il a appliqué l'algorithme génétique sur
des matrices binaires construites à partir des projections horizontale
et verticale. En effet, une matrice binaire A construite à partir de
deux vecteurs non négatifs V et H.
Avec H = (h1; . . . ; hn) et V = (v1;.
. . ; vm) sont respectivement
la projection horizontale et verticale de la matrice binaire A.
La construction de la matrice A = (aij) doit
satisfaire à la contrainte suivante : il faut que
n
X aij = vi, i = 1, ...m
J=1
Xm aij = hj,j = 1,...m
i=1
Le choix de cette configuration due au tomographie discret qui
est fortement lié au traitement d'image digitale, c'est-à-dire
des matrices binaires comme des images, dont la matrice binaire le noir pour
les valeurs (1) et blanc pour les valeurs (0) on l'appelle aussi les pixel
d'entrées de matrice [18]. La contrainte qu'il faut respecter au cours
de la reconstruction des images binaires selon la projection verticale et
horizontale [27], il faut que :
Xn aij = Xm aij
J=1 i=1
Les principaux problèmes de la tomographie discret, il
faut que les deux vecteurs V et H soient données pour
construire la matrice binaire A E A(V, H). Et pour limiter le
nombre de solutions à élaborer, il faut ajouter des autres
propriétés supplémentaires concernant les solutions
souhaitées.
K.J. Bateleur a ajouté que la fonction objectif
f : A(V, H) --p Z, sera
évalué pour chaque solution A E A(V, H)
élaborée pour prendre la valeur maximale de f.
C'est-à-dire que la fonction f a un domaine d'étude
limité concernant la classe A(V, H).
K.J. Bateleur [16] a signalé aussi que la notion de
bascule joue un rôle très important dans les
caractéristiques de classe A(V, H) de solution
élaborée. Une bascule est un sous matrice qui se trouve dans une
solution A E A(V, H) sous la forme suivante :
L'opération de bascule consiste à
échanger les 1 et 0 pour ces quatre cellules et les
projections orthogonales d'une matrice binaire demeurent in-
Chapitre 2. Etat de l'art sur la reconstruction des
images hv-convexes
Abdessalem DAKHLI 13
FIG. 2.3 -Opération bascule
changées après les opérations de
bascules. Cette opération est élémentaire dans la classe
de solution A(V, H) selon Ryser[15,20].
C'est-à-dire, l'opération d'une bascule joue une
rôle très important pour élaborer une solution
équivalente B 2 A(V, H) avec B =6 A.
Cette solution élaborée a la même projection que la
solution A. Donc l'algorithme génétique doit utiliser
les opérations de bascules d'une façon très importante
pour faire apparaître d'autres solutions (d'autres individus).
K.J. Bateleur a montré que le nombre des matrices (ou
les solutions) est une opération très importante à faire
pour l'algorithme à utiliser. Il a signalé 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).
K.J. Bateleur a évoqué que l'algorithme
génétique est insatisfaisants pour plusieurs raisons, en premier
lieu, l'opérateur de croisement a habituellement comme
conséquence les solutions de candidat qui deviennent
considérablement des projections prescrites de même lorsque les
deux solutions parents ont plusieurs différences, ce comportement rend
l'opérateur de croisement inefficace. Pour cette raison l'algorithme
recourt à l'opérateur de mutation pour améliorer la
solution. En deuxième lieu l'opérateur de croisement quelque soit
son type ne tient pas compte de la structure spatiale bidimensionnelle des
solutions de candidat [16].
K.J. Bateleur a conçu un algorithme
évolutionnaire [24] spécifique au problème pour surmonter
les inconvénients de l'algorithme génétique classique.
Afin d'exploiter entièrement la puissance de
l'opérateur de crossover, la procédure de hillclimb augmente la
qualité de solution. L'importance des opérateurs de croisement
crossover et de mutation explique la raison de choix de cette approche.
K.J. Bateleur a définit l'opérateur de crossover
comme étant une des parties principales dans cet algorithme, son
entrée se compose de deux images de parent et sa sortie une image enfant
qui a certains dispositifs des deux
Abdessalem DAKHLI 14
Chapitre 2. Etat de l'art sur la reconstruction des images
hv-convexes
L'algorithme évolutionnaire
Générer une population initiale P0 de
la taille À composée par des matrices
E A(V,H).
Effectuer une opération de hillclimb
sur chaque matrice dans P0.
t 4--0
TANT QUE (Non condition d'arrêt)
FAIRE
Début
P t ' = ~
Pour ide 1 à Faire // le nombre des
enfants qui sont créés dans chaque
génération.
Début
Générer une matrice C d'enfant par
l'opérateur de crossover ou mutation
Effectuer une opération de hillclimb
sur C
P t '=P t
'u{C}
Fin
Choisir la nouvelle population
P't+4 à partir Pt u
P't
t 4--t + 1
FIN TANT QUE
Produire le meilleur individu trouvé.
Toutes les images dans la population sont des membres de
classe
A(V, H), et chaque image résultante devrait
avoir les projections prescrites, de même il a définit
l'opérateur de Hillclimb, comme étant un opérateur qui
permet d'appliquer une petite modification pour augmenter la fonction objective
jusqu'à l'optimum local et pour conserver l'appartenance de solution
à la classe A(H, V ).
Cette approche exige que l'opération d'une bascule soit
élémentaire comme étape locale. Et le choix
d'opération de bascule se fait d'une façon arbitraire bien
sûr l'opération qui augmente la fonction objective.
L'exécution l'opération de hillclimb offre
plusieurs défis informatiques. En effet, L'opération hillclimb
est très efficace pour améliorer la fonction d'évaluation.
Dans l'algorithme existe des boucles qui permettent de mieux évaluer les
opérations des bascules pour avoir à la fin une fonction
objective maximale.
Contour de la procédure de Hillclimb
TANT QUE (il n'existe pas une
opération de bascule qui permet d'améliorer la fonction
objective) FAIRE
Début
Choisir aléatoirement une telle opération de
bascule.
Abdessalem DAKHLI 15
| 
