Reconstruction des images hv-convexes par la recherche taboue

i

Table des matières

Table des matières i

Table des figures iii

Liste des tableaux v

Remerciements vi

Introduction vii

1	Reconstruction des images binaires		1
	1.1	Définition	1
	1.2	Problème de la reconstruction d'une image binaire	2
	1.3	Problème standard de reconstruction de l'image binaire . . . .	2
		1.3.1 Existence d'une solution	3
		1.3.2 Reconstruction d'une solution	3
		1.3.3 Unicité et Equivalence entre les solutions	4
	1.4	Etat de l'art	6
	1.5	Conclusion	6
2	Etat de l'art sur la reconstruction des images hv-convexes		7
	2.1	Définition	7
	2.2	Etat de l'art sur la reconstruction des images hv-convexe . . .	8
	2.3	Conclusion	16
3	Reconstruction des Images Binaires par recherche Taboue		18
	3.1	Paramétrage de l'algorithme Tabou	18
		3.1.1 Définition du voisinage	19
		3.1.2 Liste tabou	20

Abdessalem DAKHLI ii

Table des matières

3.1.3 Condition d'arrêt 20

3.1.4 Fonction d'évaluation 20

3.2 L'application de la recherche taboue pour reconstruire des

images hv-convexe 21
3.2.1 Reconstruction des images 11V-CONVEXES par la re-

cherche taboue sans amélioration 24
3.2.2 Reconstruction des images 11V-CONVEXES par la re-

cherche taboue avec amélioration 30

3.3 Conclusion et interprétations des résultats 33

Conclusion et pérspectives 35

Annexe 36

Bibliographie 49

iii

Table des figures

1.1	Projection orthogonales (horizontale et verticale) d'une ma-
	trice binaire	2
1.2	Reconstruction d'une matrice binaire par l'algorithme glouton	4
1.3	Illustration d'une bascule	5
1.4	Voisinage à l'aide d'une opération Bascule	5
2.1	Définition d'une matrice convexe	8
2.2	Principe de reconstruction d'une image binaire	9
2.3	Opération bascule	13
3.1	Modélisation de la mémoire dans la recherche Tabou	22
3.2	Principe de reconstruction d'une image binaire	23

iv

Liste des tableaux

2.1	Résultat de Reconstruction des images hv-convexe	25
3.1	Résultat de Reconstruction des images hv-convexe	37
3.2	Résultat de Reconstruction des images70x70 hv-convexe . . . .	38
3.3	Résultat de Reconstruction des images100x100 hv-convexe . .	39
3.4	Résultat de Reconstruction des images 40x40 hv-convexe en
	appliquant le principe d'intensification	44
3.5	Résultat de Reconstruction des images 70x70 hv-convexe en
	appliquant le principe d'intensification	45
3.6	Résultat de Reconstruction des images 40x40 hv-convexe en
	appliquant le principe de diversification	46

v

Remerciements

Je tiens tout d'abord à remercier mon encadreur Mr. Fethi jarray pour sa disponibilité et ses conseils avisés. Mais aussi pour sa bonne humeur et sa franchise qui ont donné une ambiance de travail stimulante et productive.

Je remercie bien évidement mes parents, mes grands parents et ma famille pour m'avoir soutenu, aimé et permis de faire ces longues études qui je l'espère seront payante. Merci de m'avoir fait confiance et j'espère avoir pu faire votre fierté.

Je tiens à remercier très sincèrement l'ensemble des membres du jury qui me font le grand honneur d'avoir accepté de juger mon travail.

Je tiens également à remercier tous mes amis et mes enseignants qui ont encouragé dans mes études. Vous l'avez tous fait à votre manière et je vous en suis extrement reconnaissant

vi

Introduction

La tomographie discrète ou reconstruction d'images discrètes à partir de certaines de leurs projections est un sujet en pleine expansion et souvent on fait une tomographie dès qu'une image n'est pas comprise ou de mauvaise qualité d'incidence ou de contraste.

Ses applications industrielles en cristallographie et en imagerie médicale font de ce sujet une source importante de problèmes algorithmiques. Cette discipline consiste à reconstruire un sous-ensemble à partir d'un ensemble de projections. Ces sous-ensembles reconstruits peuvent correspondre à des images monochromatiques, des images en couleur, des emplois de temps,.. .

Les problèmes traités peuvent être formulés comme suit : étant donnés H = (h1, ... , h_m) et V = (v1, ... , v_n) deux vecteurs à coordonnées entières positives, est-ll possible de reconstruire un matrice m*n éléments qui respecte les projections (H, V ) ? Le plus souvent les projections donnent le nombre des éléments dans chacune des lignes et des colonnes. Ces éléments se fixent selon la nature de problème.

Notre travail se situe dans le cadre de reconstruction des images binaires monochromatiques. Le problème qu'on traite est la reconstruction des images binaires étant données ses projections orthogonales (H, V ). Pour résoudre ce problème on doit utiliser la recherche taboue.

Le présent rapport est composé de trois chapitres. Le premier chapitre traite essentiellement le problème de reconstruction des images binaires et introduit certaines notions fondamentales en reconstruction d'images, le deuxième chapitre s'adresse à l'état de l'art conçernant la reconstruction des images hv-convexe et le troisième chapitre présente les résultats pratiques et théoriques informatiques d'algorithme tabou concernant la reconstruction des images hv-convexe.

1