Chapitre 1. Reconstruction des images binaires
plus prioritaires. Si le nombre de lignes disponibles est
inférieur à v alors l'algorithme s'arrête et il n'y a pas
de solution au problème. La ligne i est dite disponible à
l'étape j lorsque ai > 0. ai étant le nombre
des '1' non encore placés à l'étape j de l'algorithme.
Les lignes les plus prioritaires sont celles qui ont les plus
grandes valeurs
ai.
Pseudo Code de l'algorithme glouton:
1 - ai = hi; i =
1;::::; m;
2 - pour j = 1 à n
Faire
2.1 - s'il n'existe pas v ligne disponible alors
fin;
2.2 - placer v '1' sur les lignes disponibles les plus
priotaires;
2.3 - si un '1' est placé sur la ligne i
alors ai -p i1;
Fin Faire.
i : étant le nombre des '1'non encore
placés à l'étape j de l'algorithme.
FIG. 1.2 -Reconstruction d'une matrice binaire par l'algorithme
glouton
1.3.3 Unicité et Equivalence entre les solutions
Bascule
Une bascule est un ensemble de quatre cellules (i ;j), (i
;j+k), (i+h ;j) et (i+h ;j+k) tel que les cellules (i ;j) et (i+h ;j+k) sont de
valeur 1 et les cellules (i+h ;j) et (i ;j+k) sont de valeur 0.
L'opération de bascule consiste à
échanger les 1 et 0 pour ces quatre cellules. Les projections
orthogonales d'une matrice binaire demeurent inchangées après les
opérations de bascules.
Ryser [6] a montré que les solutions sont
équivalentes dans le sens où l'on peut passer d'une solution
à une autre par une suite finie de bascules, comme le
théorème 2.
Théorem 2 :
Si A; A' 2 R(H; V ) alors se transforme en A'
à l'aide d'une suite finie d'opérations de bascules.
Chapitre 1. Reconstruction des images binaires
FIG. 1.3 -Illustration d'une bascule
De ce théorème, on déduit que les
éléments de la classe R(H, V ) sont
représentés par un graphe fortement connexe. Les sommets sont
associés aux matrices et les arcs traduisent les opérations de
bascules de passage d'une solution à une autre.
Wang et Zhang [2] ont calculé le nombre de solutions
équivalentes. Par exemple, lorsque les projections orthogonales sont
unitaires (V est unitaire si v = 1, j = 1, : : : in) , il
existe n! matrices équivalentes.
Remarque deux matrice binaires sont voisines
si l'on peut passer de l'une à l'autre avec une transformation
élémentaire ou une opération de bascule.
FIG. 1.4 -Voisinage à l'aide d'une
opération Bascule
Unicité de la solution
La solution MB(H, V ) C R(H, V
) est-elle unique?
Existe-il une autre solution MBI(H, V ) C R(H, V
), qui est tomo-graphiquemnt équivalent à MB(H, V )
c'est-à-dire respecte projection orthogonales (H, V ).
D'après le théorème 2, une matrice est invariante
(solution unique) si et seulement si elle n'a pas de bascules. Par
conséquent, tester l'unicité de la matrice, revient à
tester si toutes les cellules sont invariantes. Haber [9] a donné les
conditions nécessaires et
Abdessalem DAKHLI 5
Abdessalem DAKHLI 6
Chapitre 1. Reconstruction des images binaires
suffisantes pour qu'une cellule soit invariante. En effet, Une
cellule (i, j) est invariante si elle est 1- invariante lorsque
A(i, j) = 1 ou 0-invariante si A(i, j) = 0
pour toute A c R(H, V ).
| 
