Reconstruction des images hv-convexes par la recherche taboue

Chapitre 1. Reconstruction des images binaires

1.2 Problème de la reconstruction d'une image binaire

Le problème de la reconstruction des images binaires consiste à trouver une image binaire respectant certaines contraintes, par exemple la projection dans plusieurs directions. Les problèmes peuvent être classés suivant le nombre de directions et les propriétés géométriques des objets (convexité, connexité, périodicité, etc), c'est à dire selon la projection horizontale et verticale de l'image on essayera de l'élaborer sa matrice binaire.

Soit A une matrice binaire :A = ( _a11...a1n ) avec aii 2 {f; 1} , on définit :

hi = _Xn

i=1

am1...amn

aii : la projection horizontale de la lignei_; i = 1_; :::; n. Elle donne

le nombre des '1'de chaque ligne.

H = (h1;::: ; h_n) : la projection horizontale de la matrice binaire A:

vi = _Xm

i=1

aii la projection verticale de la colonne j_; j = 1_;::::_; m; Elle

donne le nombre des '1'de chaque colonne.

V = (v1;::: ; v_m) : la projection de la matrice binaire A.

Exemple : soient H = (1_; 3_; 3_; 3_; 3) et V = (2_;3_; 1_;4_; 3) les projections horizontale et verticale de la matrice suivante :

FIG. 1.1 - Projection orthogonales (horizontale et verticale) d'une matrice binaire

1.3 Problème standard de reconstruction de l'image binaire

Le problème de reconstruction d'une matrice binaire à partir des ses projections orthogonales (H_; V ), noté MB(H_; V ), consiste à trouver une matrice binaire A de projection horizontale H et de projection verticale V . On note

Abdessalem DAKHLI 3

Chapitre 1. Reconstruction des images binaires

par R(H, V ) la classe des matrices binaires m * n de projection orthogonales (H,V ).

Il est couramment admis que le premier problème de tomographie discret, étudié par H.Ryser[6] à la fin des années 50 est la reconstruction d'une matrice. La projection horizontale d'une matrice binaire est le vecteur H = (h1;... ; h_n) où hi est la somme des éléments de la ligne j. De façon analogue, la projection verticale est le vecteur : V = (v1;... ; v_m) où les sommes sont calculées par colonne.

Plusieurs types de problèmes peuvent être définis : existence, reconstruction et unicité.

1.3.1 Existence d'une solution

Données H = (h1;... ; h_n) et V = (v1;... ; v_m) deux vecteurs à coordonnées entières positives.

Question Existe-il une matrice binaire M ayant pour projections H et

V ?

Le théorème 1 [6] suivant est fondamental et donne, sous l'hypothèse de la décroissance de la projection verticale, des conditions nécessaires et suffisantes pour l'existence d'une matrice binaire à partir des projections orthogonales sous la forme de deux vecteurs décroissante. En effet, une vecteur V de dimension m est décroissante si t1 ~ t2 ~ ..... ~ t_m.

Theorem 1 (Ryser) :

Si V est décroissante (V est décroissante si v1 ~ v2 ~ .... = v_m) alors le problème MB(H, V ) a pour réponse 'oui'si et seulement si :

_Xk j=1

hi =

vj et

v j >

_Xm
i=1

_Xn j=1

_Xk j=1

vj ; k = 1,....,n - 1

Avec ...

v j désigne le nombre de projections horizontales supérieure ou égales à j.