Sommaire
Page
Sommaire
1
Introduction Générale
6
Chapitre l : Etudes préliminaires
8
LI Traitement d'informations graphiques
8
1. 2 Classification et segmentation cl ïnw,gcs
9
1.3 Segmentation d'images: Généralitt's ct rnéthoclcs'
9
1.3.1 Détection des contours
10
1.3.2 Segmentation en régions
11
1.3.2.1 Regroupement par classe
11
1.3.2.2 La croissance des régions
12
1.3.2.3 Split and merge
12
1.3.2.4 Approche région-contour
13
1.4 Concept de la reconnaissance des formes
13
1.5 Reconnaissance structurelle
15
Chapitre II : Représentation Quaternaire et structure de l'Image
16
11.1 Graphes et arbres
16
11.2 Les arbres 2n -aires (n = 1,2)
16
11.2.1 Les arbres binaires (2-aires)
16
II.2.2 Décomposition binaire d'tl1l signall-D
18
11.2.3 Les arbres quaternaires (4-aircs )
18
11.3 Filiation sur une arborescence
19
11.3.1 Généralités
19
11.3.2 Arborescence Quaternaire
20
lIA Représentation de l'image
20
IIA.1 Représentation en mode linéaire
20
IIA.2 Représentation quaternaire
21
11.5 Représentation physique d'une image par une structure quaternaire
1



Je dédie cette thèse
A A-ug1lstine pOUT son courage
A KuTl et Dominique pour leur patience
A mes pu'rents pou',' leur confiance
.4 'Tnt" u.'m.i;, pO'nT lf.lI:r 3o'utien

REMERCIEMENTS
Je remercie :Ylessieurs Claude DELLACHERIE et Gérard GRANCHER Responsables
du Laboratoire d'Analyses et Modèles Stochastiques qui m'ont acceuilli dans le laboratoire et
n'ont jamais ménagé leurs efforts pour mettre à ma disposition le nécessaire pour effectuer
cetravail.
Je remercie également le C.I.E.S ( Centre Illtt'l1latiollal des Etudiants et Stagiaires)
pour son soutien matériel.
Je tiens à exprimer mes remecicmellts ct ma plus "i,'c gratitude à :vlessieurs Jean-Pierre
PEClJCHET et Jean-:\\Iarc CHA:\\,IPARXAl"D IJour lïntérêt. les remarques et l'attention
qu'ils m'ont portés à l'examen de cette thèse en tant que Rapporteurs.
Que ylonsieur Georges HA~SEL "cuille biell accepter ici l'expression de ma profonde
reconnalssance pour m'avoir fait l'hoIlIleur de diriger ces travaux et présider le jury de
soutenance.
Je tiens également à remerCler tout particulièrement ~Ionsieur Alain LEDUC pour
m'avoir soutenu, aussi bien sur le plan scientifique que sur le plan moral, tout au long de
la réalisation de ce travail.
Mes remerciements vont également à :\\,Iollsieur Pierre :\\IICHE qUi a accepté de
participer au jury de soutenance de <.:ette thèse.
Que les membres du Laboratoire d'Analyses et Modèles Stochastiq'ues, Madame LERE-
TOUR et tous ceux qui, par leurs conseils ou lem attention. ont contribué de près ou de
loin à l'élaboration de ce travail de recherche. trouvent ici l'expression de ma profonde
gratitude.
Enfin, je SUlS très reconnaissant envers :\\Ionsieur :\\Iarc JOLLY et :'vladame Régine
DEBEl'RRE pour le soiIl et la patienœ quïls ont apportés à l'impression de cette thèse.

SOl\\IIl\\IIAIRE

Sommaire
Page
Sommaire
1
Introduction Générale
6
Chapitre 1 : Etudes préliminaires
8
LI Traitement d'informations graplüques
8
1.2 Classification et segmentatioll cl "images
9
1.3 Segmentation d'images: Généralités ct méthodes'
9
1.3.1 Détection des contours
10
1.3.2 Segmentation en régions
11
1.3.2.1 Regroupement par classe
11
1.3.2.2 La croissance des régions
1:2
1.3.2.3 Split and merge
12
1.3.2.4 Approche région-contour
13
1.4 Concept de la reconnaissance des formes
13
1.5 Reconnaissance structurelle
15
Chapitre II : Représentation Quaternaire et structure de l'Image
16
11.1 Graphes et arbres
16
11.2 Les arbres 2n -aires (n = 1,2)
16
11.2.1 Les arbres binaires (2-aires)
16
IL 2.2 Décomposi tion binaire cl \\lll signal 1- D
18
11.2.3 Les arbres quaternaires (4-aircs)
18
11.3 Filiation sur une arborescence
19
11.3.1 Généralités
19
11.3.2 Arborescence Quaternaire
20
lIA Représentation de l'image
20
1104.1 Représentation en mode linéaire
20
11.4.2 Représentation quaternaire
21
11.5 Représentation physique d'une image par llne structure quaternaire
22
1

Sommaire
Chapitre III : Manipulation Syntaxiq ue en Représentation
Quaternaire d'une Image
24
III.1 Généralités
24
III.2 Le codage
25
III. 2.1 Le p-codage
25
III.2.2 le q-codage
26
III.3 Relations de voisinages
29
III.3.1 Voisinage entre deux sites
30
III.3.2 Adressage par p-code des voisins d'un site
30
IIIA Système de réécriture associé à la recherche du ct-code du voisin d'un noeud
31
IIIA.1 Généralités
31
Proposition 11.1 (Algorithme de l'opùateur Est)
,
31
Proposition II.2 (Algorithme de 1'0pératclU' Sud)
32
Proposition 11.3 (Algorithme de l'opéraccur OllL'SC)
33
Proposition lIA (Algorithme de l'opé'raccm :Jord)
34
III.4.2 Notations
34
11.5 Détermination syntaxique des voisins d'ull bloc
36
III.5.1 Le bloc
35
III.5.2 Voisins de tailles identiques ù celle du hloe
36
IIL5.3 Voisins de tailles différentes à celle du bloc
36
IIL6 Relation d'adjacence
39
IIL6.1 Adjacence de deux régions
39
IIL6.2 Adjacence de deux blocs de tailles différentes
39
III. ï Algorithme de détermination des voisins d'un bloc 39
III.7 1 Père d'un bloc
39
III.7.2 Fils d'un bloc
40
III. 7.3 Algorithme de détermination des \\'oisins
40
!IL7A Exemple de détermination de voisins
41
Chapitre IV : Analyse M ulti-échelle et Transtormation de Haar
44
IV.1 Transformation pyramidale
44
l'V. 1. 1 Transformation pyramidale 1- D
44
IV.1.1.1 Codage des indices
45
IV. 1. 1.:2 Algorithmes de transformations
46
IV 1.1.3 Complexité algorithmique de la transformation pyramidale P
46
IV.1.2 Transformation pyramidale 2-D
47
IV.1.:2.1 Produit tensoriel d'isométries
47
IV.1.:2.2 Produit tensoriel de transformations pyramidales
48
2

Sommaire
IV.2 Représentation pyramidale 2-D
49
IV.2.1 Cas Continu
50
IV.2.2 Cas discret
50
IV.2.3 Image-blocs
50
IV.3 Fonctions de Haar
51
IV.3.1 Définitions
51
IV.3.2 Indexation canonique de Hf..:
52
IV.4 Analyse pyramidale de Haar
55
IV.4.1 Base orthogonale de Haar
56
IV.4.2 .-\\.lgorithme d'Analyse deHaa.r
58
IV.5 Synthèse pyramidale de Haar
59
IV.5.1 .-\\'lgorithme de transformation réciproque de Haar
60
V1.6 Complexité algorithmique des transformées de Haar
61
V1.7 Interpretation statistique des coefficients de Fourier-Haar
63
IV.8 Analyse multi-échelle d'images
63
IV.8.1 Transformation d ïmage par annula tion de faibles coefficients
64
IV.3.1.1 Algorithme de compression pa.r annulation de faibles coefficients
64
1\\'.3.1.2 Implémentation de l'a.lgorithme
65
IV.8.1.3 Compression de l'image en terme de bi ts
65
IV.8.2 Filtrage d'image
66
IV.8.3 Algorithme de détection des hlocs carrés homogénes maximaux
72
Chapitre V : Un Algorithme pyramidal de Segmentation
cl 'images en régions
73
V.1 La segmentation
73
V.1.1 Région
73
V.1.2 Prédicat d'homogénéité
74
V.1.3 Régions adjacentes
74
V.1.4 Définition ( segmentation)
74
V.2 Algorithme pyramidal
75
V.2.1 Description de la méthode utilisée
75
·V.2.2 Structure de l'arbre quaternaire de l'image
75
V.2.2.2
.-\\'lgorithme de construction du tableau de correspondances
des blocs dans l'arbre quaternaire
76
\\".2.3 Fusion de l'arbre qURtcma.irc de l'image
, 1

Sommaire
V.:2.3.1 Structure d'un bloc carré
ï8
V.2.4 Construction des segments
78
V.3 Implémentation
78
V.3.1 Algorithme de construction des blocs carrés
79
V.3.2 Algorithme de calcul du père d'un noeud
80
V.3.3 Construction de la matrice d'adjaccllce
81
V.3A Présentation du résultat théorique
81
VA Problèmatique du calcul de l'adjacence de deux blocs
82
V.4.1 Implémentation des algorithmes dl' calcul syntaxique des voisins
83
VA.1.1 Algorithme de calcul des voisins de taille supérieure
83
V.4.1.:2 Algorithme de calcul des "oisins de taille inférieure
84
Chapitre VI : Une Base d'Images Segmentées
91
V1.1 Structure de la base
91
V1.2 Rappels sur les bases de données
92
V1.2.1 Introduction
92
V1.2.2 Le modèle relationnel
92
V1.3 Structures de données spatiales
93
V1.3.1 Conception logique des structures de données spatiales
93
V1.3.2 Quelques variantes des strucr.ures de données géographiques
94
VIA Description de la base d'images orientée 2k x 2k
97
V1.4.1 Différentes relations constituant la base
98
V1.4.2 Algorithmes de création et d'exploitation de la base
98
\\'1.4.2.1 Création de la base
98
V1.4.2.2 Extraction des attributs
99
\\"1.4.2.3 Fusion de région dans la base
100
VI.4.3.4 Classification des régions ct reconnaissance syntaxique des formes
100
V1.5 Un algorithme de detection de contours cl 'uIle région
obtenue par segmentation pyramidale
101
V1.5.1 Structure du contour
101
V1.5.2 Principe de recherche des contours
102
V1.5.3 Algorithme de détermination de contour
102
V1.5.3.1 Détermination préliminaire des contours
102
4

Sornmalre
'/1.5.3.2 Chainage des SOIlllllets pour la fonuatioll des polygones
104
V1.5.3.3 LUT du parcours du voisinagl' d\\lll contour
104
VI.5.3.4 Algorithme de chainage quaternaire des contours
104
V1.5.3.5
Compression des données quaternaires pa.r accolage des droites
contigües de même direction
107
Conclusion Générale
109
Bibliographie
110
5

INTRODUCTION GÉNÉRALE
j
1
1

Introduction Générale
Le traitement automatique de l'informatioll a eu Ull essor considérable pendant les deux
dernières décennies; le signal et l'image constituent des interfaces naturels et obligés entre
le monde physique et l'homme ou l'ordinateur qui l'interpretent. Si l'homme est capable de
pouvoir distinguer sans difficulté un objet parmi plusieurs objets. on a par contre encore
beaucoup de mal à pom'oir mettre au point des processus permettant d'imiter les animaux
les plus simples.
Du perceptron au robot intelligent capable de modifier son comportement en fonction
de son euvironement. l'homme a fnit bl'aUcotlp dl' progrès daus le domaine de la vision
par ordinateur [AYA 89]: mais que Cl.' :soit il l:"use des capteurs ou des procédures de
traitement des scènes déjà saisies. bCillH.'OUP reste encore à faire; la seule étape qui consiste
Ft mettre en évidence les éléments à n:'l.'üunaîuc dans IUle scène est encore sujette à beaucoup
dïnterrogat ions.
Pour reconnaître un objet, il est necessaire de le dissocier des autres afin de pouvoir
mieux l'analyser. La segmentation a pour objectif de résoudre ce problème. Beaucoup de
méthodes ont été déjà proposées [HAR 84]. [~IAI 85]. Le grand défaut de ces méthodes
est qu'il n'en existe pas qui s'adapte à tous les cas de figures, ceci est en partie dû à leur
caractère heuristique et à la diversité des problèmes. Il existe des méthodes d'extraction
des contours. de segmentation en régions et de plus en plus des approches région-contour.
Autant les méthodes de segmentation en régions sont gourmandes en espace et trés liées
au critère d'homogénéïté, autant les méthodes de segmentation de contours ne sont pas
fiables parce que trop sensibles aux bruits.
La représentation des résultats d'une segmentation est toujours restée liée au problème
à résoudre. nous allons tenter dans ce travail de néer un concept topologique informatique
qui nous permettra de manipuler les images. :\\üus proposons aussi. un algorithme de
segmentation pyramidal d'images et une l"cprc'sL'l1tatioIl du résultat d'une segmentation.
:\\0\\15 concevons une base d'images scglllCllt(·C'S pl'nlll'ttallt d\\'xtraire les connaissances se
trOU\\'émt sur la. scène collsidérée.
Nous commençons par donner un aperçu général sur la segmentation d'images, la
classification automatique. et la recollllaissaw:e des formes; le tra\\"ail étant en grande partie
É'tabli sur les décompositions pyramidales, au chapitre:2 nous parlerons de la représentation
quaternaire des images. C'est l'occa.sion pour nous de faire quelques rappels sur la théorie
6

Introduction Générale
des graphes et d'introduire un nouveau fOl'lnalisrne :;yntaxiquc de représentation et de
manipulation de l'information graphiquc qui fera l'objet du chapitre 3 : en effet nous allons
considérer qu'une image est un langage sur unalphabet de quatre lettres. L'analyse multi-
résolution connaît une activité de recherche considérable [MEY 86], [MAL 87a], [MAL 87b]
et le chapitre 4 nous permet à partir de différents travaux de construire une base de Haar
qui nous permettra grâce à. l'anal:yse c·tjou la. syuthèse dc cumpresser, de filtrer et préparer
une segmentation d'images. :\\ous propusons au chapitre 5 un algorithme pyramidal de
segmentation d'images qui s'inspire du split and merge [HüR 76]. Au chapitre 6, nous
construisons une base d'images segmentées qui nous permet tra de gérer les données d'une
segmentation et d'envisager la créatiun cl 'une base de connaissances pouvant être utilisées
pour interpreter une scène.
-,

CII,\\I'ITHE 1
/
/
ETUDES PRELIMINAIRES

chapit-re [
Etudes Préliminaires
INTRODUCTIOI\\l
Que ce soit en classification, en segmentation ou en reconnaissance des formes, il y a
un soucis de mise en évidence ou d'interpretation. Les problèmes rencontrés en visionique
dépendent très souvent du domaine d'application, d'où la multiplicité des méthodes de
modélisation due au caractère heuristique de l'es dernières. Très souvent on est amené à
analyser des images des scènes et d'y reconnaître des formes, une des étapes fondamentales
est la segmentation des images. Nous allons avant de parler de la segmentation étudier les
liens qui existent entre les différents processus (l'analyse. cl Ïnterpretation et de synthèse
d'images.
1.1 TRAITEMENT D'INFORMATIONS GRAPHIQUES
Le traitement d'informations graphiquC's par l'ordinateur est assez diversifié selon
les domaines d'applications auxquels il est destiné. On distingue trois catégories de
manipulation d'informations visuelles: L"infog-raphie qui est la génération des images à
partir des données symboliques; la synthèse d'images a connu ces dernières années beaucoup
de progrès tant dans le domaine théorique que pratique, ce qui a donné lieu à plusieurs
publications et de multiples réalisations pratiques [ROG 88], [PAV 82], [MAR 84], [CAR
83]. La XAO et l'animation par ordinateur en sont des domaines d'applications courants,
c'est ainsi que l'on voit de plus en plus leur utilisation en gestion, médécine, publicité, et
en industrie du spectacle.
L'Analyse d'images est un ensemblc de proccssus appliqués à l'image afin d'en tirer
le grand parti et mieux l'interpreter. L'entrée est une image et la sortie est une image
ou un ensemble de symboles. La conception des calculateurs de plus en plus puissants a
permis une évolution en traitement de l'information et notamment en vision automatique,
mais beaucoup reste encore à faire. L'objectif principal ici serait de préparer une bonne
interpretation après une analyse. au micux de pouvoir à partir des symboles déduits, faire
une synthèse de l'image de départ.
La reconnaissance des formes consiste l'I1 des méthodes permettant de produire une
description de l'image en entrée ou d'affecter l'objet d'une image à une classe donnée. Dans
ce cas la reconnaissance est le problème inverse du graphisme. L'entrée est une image et
le procedé est de la transformer en une structure abstraite: un ensemble de nombres, une
chaîne de symboles ou un graphe.
s

chapitre [
On peut établir des relations entre les trois processus parce qu'il est possible de
transformer une image de telle manière lplC' le problème de classification devienne facile.
Une des classes de problèmes très interessants est la représentation interne des images dans
l'ordinateur: structure des données, stockage et restitution, compression. En traitement
d'images on a très souvent besoin d'extraire les contours et en graphisme on peut avoir envie
de remplir les contours, cette dualité nous amt'ne très souvent à tenir compte du graphisme
lorsqu'on fait du traitement d"images. li Ill' étape fondamentale de la reconaissance des
formes étant la mise en é\\'iclenLe des fOrIlleS 3 reconnaître. La segmentation de l'image
résoud en partie ce problème, nous montrons ci-dessous le lien entre la segmentation et la
classification [PAV El, [PAV 82].
1.2 CLASSIFICATION ET SEGMENTATION D'IMAGES
La Classification des données est une opératioll 4.ui COllsiste à arranger en catégories,
une catégorie étant une collection de [Ol'llll:s ayallt les mêmes propriétés [FAU 85]. En
classification le nombre d'individus l'st rl'streillt. t'ntre 1000 et 10000 contrairement à
l'imagerie où nous avons UIl nombre important de pixels 100
à 106 ; en traitement
\\
d'images les sites (pixels) sont pauvres l'Il informations, alors que les individus étudiés
en classification sont riches en informations. En Classification il n'y a pas de relation à
priori entre les individus, sauf peut-être une distance sur Rd, contrairement à l'imagerie où
étant donné P.i.V! = {(i, Xi), i E I} [MON S8], Xi est le poids du pixel et i son emplacement.
On peut définir deux relations: La relation de proximité spatiale entre Pi = (i, xd et
PJ = (j,Xj) à partir de la distance ddpi,Pj) = 5(i,j) où 8 est la distance métrique, et
la relation de proximité de valeurs relativement à la distance d2 (Pi,Pj) = IXi - xjl. Une
segmentation peut donc être considéré comme une classification, à la seule différence qu'en
segmentation on utilise en même temps la proximité spatiale et la proximité des valeurs.
1.3 SEGMENTATION D'IMAGES: GEI\\JERALITES ET METHODES.
La segmentation d'images peut prl'Ildre diffé'n:llts aspeLts selon le problème à traiter
ou le cadre dans lequel on se trouve. k pn:lllit.'l" collsiste l'Il la c1ivision d'un objet en un
certain nombrc de primiti\\'cs (Pl LE! qui :-JOU( li('c;; enrrl' dIes pi1r des relations (Rj)jE)'
9

chapllre [
Etudes Préliminaires
Si nous prenons l'exemple d'un carré qui est une figure géométrique possèdant quatre
côtés égaux et quatre angles droits illustré par la figure LI.
R l = R =
=
=
l
R3
R.I
relation de perpendicularité
Pl
R l
RZ
p..
P2
1
R4
Rj
1
1
1
P3
l'
figure I. 1 : Représelltatioll structurelle d'un carré
Le second aspect, celui sur lequel nous allons le plus insister dans notre travail est la
segmentation d'une image en régions homogènes. c'est-à. -dire étant donné une image on
cherchera à identifier les zones (ZdiEJ qui sont homogènes et maximales comme l'indique
la figure 1.2.
figure I. 2 : Représentation d'une segmentation en zones homogènes
La segmentation d'images sous le dernier aspect évoqué est l'un des domaines de
recherche en analyse d'images qui a suscité beaucoup la curiosité des chercheurs que ce
soit par détection des contours ou par détcctioll des régions.
1.3.1 Détection des contours.
Elle consiste en l'extraction des contours sur l'ima.ge d'une scène: c'est généralement
des méthodes très facile à mettre en oeuvre ct qui ll\\~voluent pas rapidement. compte tenu
de leurs dépendences aux types de probkl1les d images traités.
10

chapitre 1
Etudes Prélimmaires
On peut utiliser la méthode du gradient 4U1 consiste en un filtrage passe-haut sur
une image pour augmenter la visibilité des contours, ensuite on effectue un seuillage
ou une recherche le long des crêtes; les méthodes les plus conseillées sont les méthodes
par convolution et les plus fréquemment utilisée sont SOBEL, ROBERTS, GRADIENTS,
PREvVITT, MCLEOD [MAI 85] et_de plus en plus l'opérateur de DERICHE [DER 83].
Il est aussi possible de réaliser des circuits VLSI, mais ceci n'étant pas notre
préoccupation nous finirons cette partie cn rappellant que l'on peut aussi extraire les
contours en utilisant le passage par Zéro des dérivées secondes ou, par masquage adapté
qui consiste à rechercher en chaque poim de l'image la pd'scnce d'une configuration con-
forme à un gabarit appartenant à un dictionaire; ,\\!;abarit qui varie d'une application à une
autre [MAI 85] [CaC 84]. Pour affiner ces C'OutOlll'S. il faut effectuer une poursuite et une
fermeture des contours.
Plusieurs méthodes Ollt dejà été propmJ:es ponr extraire k,s contours, mais ces dernières
ne diffèrent pour la plupart que dans la partie post-traitement qui est la fermeture des
contours [GIR 87], [COC 84], [CaC 85].
1.3.2 Segmentation en régions
Les méthodes de segmentation d'images en régions peuvent être divisées en trois grands
groupes: le regroupement par classe, la croissance des régions, le split and merge.
1.3.2.1 Regroupement par classe.
Cette technique consiste en l'attributioll à chaque pixel d'une étiquette correspondant
au numéro de segment auquel il appartient, dOlH: les segments de l'image sont des
composantes connexes de pixels ayant la même étiqette [HAR 84] en comparant les pixels
deux à deux. cela demande Ulle complt.:xir.0 très ,\\!;randtc' L'n remps. compte tenu du nombre
très grand de pixels. Le regroupement par classe peut ('tre réalisé par la détermination
des vallées dans un histogramme et en prenant le groupe comme étant des intervalles des
valeurs entre les vallées. Tout pixel dont la \\'aleur est dans lÏnten'alle i est d'étiquette i et
le segment auquel il appartient est la composante connexe de tous les pixels d'étiquette i.
Donc en définitive chaque région Ri sera représentée par une classe Ct.
11

Etudes PréliminaIres
1.3.2.2 La croissance des régions
C'est des méthodes qui permettent (l pareir de tluc1qlll'S germes choisis sur l'image,
d'effectuer une segmentation de l'image tout ellrière. On distingue plusieurs approches:
- La première consiste à considérer que tout pixel Je l"image est un noeud du graphe
et chaque pixel voisin dont les propriétés sOllt similaires sont mis en relation par un
arc, un segment sera alors un ensemble maximal de pixels appartenant tous à une même
composante connexe. Beaucoup de propositions ont été faites pour caractériser la similarité
de deux pixels: le seuillage de la valeur absolue de la différence de deux pixels est l'un des
exemples.
Une autre approche serait axée sur l'attriburion d'un vecteur de propriété à chaque
pixel où le vecteur propriété dépend cl 'un \\'oisillagc 1.. x I.~ du pixel. Les pixels seront
donc semblables si leurs voisinages sont :'j<'llll>lnl!lcs sui\\'aIlt 111l critère spécifique. Donc la
similarité est fonction du voisinage du pixel cr ceci marche bien pour les images bruitées.
Une troisième approche consiste à parcourir l'image sui vant un sens prédéterminé et la
valeur du pixel est comparée à la moyenne au voisinage du segment déjà existant. Si la
valeur et la moyenne sont proches alors le pixel est additionné au segment et la moyenne
du segment est mise à jour. s'il y a plus d'ulle ré'gion qui sont proches du pixels alors on
l'additionne à la région la plus proche. Si les régions en compétitions sont proches alors on
fusionne les deux régions et le pixel est aùditionné à la résultante: mais si aucune région
n'a une moyenne proche du pixel alors un nouveau segment est créé [HAR 84].
O. Monga dans [MON 88], utilise une technique de croissance de régions dont
l'originalité réside dans l'utilisation optimisée d'une suite de critères d'homogenéïté. Dans
[HOU 9:1.] la méthode proposée consiste dans un premier temps en l'apprentissage d'un
modéle de manière automatique et fait croître ensuite les régions tant que les transitions
de niveaux de gris suivent le modèle.
1.3.2.3 Le split and merge
("est une méthode qui commence avec l'image toute cntière comme segment initial:
ensuite successivement éclate les segments s'ils ne sont pas homogènes (suivant un critère
d'homogenéïté donné). Et enfin suivant un crirère d'homogenéïté fusionne deux à deux les
zones voisines [PA.V il].
1:2

chapllre /
Eludes Prélimi.naires
1.3.2.5 Approche régions contours
En étudiant simultanément la segmentation en régions ct en contours, nous constatons
des anomalies trés prononcées dans chacune des deux approches. L'extraction des contours
daus la première partie (Détection des ZOlle:i de..' courras te) L'st très rapide mais l'étape
sui vante (la fermeture des contours) cs t laborieuse ou conllue nous r avons constaté peut
déboucher sur des résultats assez loill dl' la l\\':alité. l'Olnpte tenu du choix quelque fois
hasardeux du contour à retenir. La seglllentatioll des ré'gions est rigide et requiert beaucoup
d'espace mémoire, car si le critère d'uniforlllité est très strict on risque de produire
de faux contours compte tenu du fait que les régions 'sont étroitement liées au critère
d'homogenéïté choisi [HOR 76], [PAV IÎ]. Dans [MON 88] une méthode optimisant les
critères d'homogenéïté est proposée. Devant ces problèmes spécifiques à chaque approche,
l'idée d'une coopération région -contour a l,té é'vO(Ll.l~'e l't l'une des plus récentes publications
à ce sujet es t [PAV 90J, .\\:lais cet te apPl'Oche appone des améliorations sans résoudre
totalement le problème et l'auteur propose l'utilisation cl 'une base de connaissance haut
niveau sur les scènes étudiées.
Nous venons de présenter les méthodes de segmentation d'images. Notre objectif dans
ce travail est de définir un modèle de repr(~sentation d'image à partir d'une segmentation,
afin de mieux préparer l'interpretation des formes qui se trouvent dans l'image. Dans le
paragraphe suivant nous faisons un rappel sur la reconnaissance des formes.
1.4 CONCEPT DE LA RECONNAISSANCE DES FORMES
La reconnalssance des formes est un ensemble de méthodes qui permettent d'extraire
des informations d'un signal observé. Ce siganl peut être un signal de parole, un
électroencéphalogramme, un signal raclaI', ou encore une image numérique ou analogique
prOVf.'nant de source de capteurs (satdirc. Images médicales. images agricoles, images in-
dustrielles) [F.-\\C 85],
~lathématiquement, identifier équivaut ù trom'er une application E d'un espace de
représentation X \\'Crs un espace dïmerpretation S1 qui ù chaque représentation X =
(XI,1'2, ...... x n ) Xl
est un attribut résultat d'une mesure, associe un élément des
interpretations U' i En. n = {tu 1
((1 n } .
E :x~n
.ti~tl·i

clwp/,t,.e [
Etudes Préliminalres
Sortie
Ehtréa
~ntU
" mtrai.telnlnt
:-- ' ~gmt'i'ttalion
h
pnl'l'Ut/.vps et
7 Inwtpt'ttation
/(f/m ./
Image
rflalions
dyn
(J1I.f~~
Analyse d'lm8!Jes
Figure I, 3
Schéma du système de reconnaiss<lllce structurelle de formes
Une phase très importante en reconnaissa'rlce des formes est la représentation de la
forme. Un capteur ne reproduit d'ulle part que ses propres sensations, et est conçu pour
s'adapter à une certaine représentation rcconllue pour vraie pour le sujet d'observation. On
peut vérifier que nous n'appréhendons pa.s uu objl't CIl lui-même mais plutôt un concept
concret lié à la représentation de celui-ci. cette représentation correspond à un ensemble de
propriétés intimement liées à l'objet, et différent éventuellement suivant les observateurs
[FAU S5], [PA\\' ïï], [CON ïS], d'où la nécessité J'une représentation adéquate.
Les méthodes de reconnaissance des formes permettront de développer une
représentation. qui ne sera pas forcc'lllclH ,df"l'[('s d\\m nom. surtout si l'affectation
est pathologique et iIlconnue. L' affecrarioll d 'lUl nom il. la représentation est l'étape
ci 'identification qui n'est pas forcément inciispcIlsable.
Les méthodes de reconnaissance de formes peUYèllt être classées en deux grands
groupes : la reconnaissallCt' paramétrique ('t la. reconnaissance syntaxique. Nous IlOUS
intéressons dans ce travail à la méthode syntaxique, compte tenu du fait que nous voulons
faire une reconaissance structurelle. qui est la conséquence directe d'une segmentation
d'image.
1-1

chap~lre 1
Eludes Pré{imma~'res
1.5 RECONNAISSANCE STRUCTURELLE
Les êtres vi\\'ants utilisent, pour la communication d'informations, un véhicule privilégié
qui est le langage naturel [FAU 85]. La reconnaissance syntaxique des formes a pour
objectif de pouvoir utiliser la théorie des langages formels et la théorie des automates
pour la modélisation et la description des relations daus les classes de formes [GüNZ ïS].
Xotre objectif dans ce travail c'est de pouvoir à. partir d'images en niveaux de gris ou
couleurs extraire des structures qui permettront une bonne reconnaissance des formes. en
d'autres termes concevoir une modelisation adéquate de l'image pour une bonne analyse
et une meilleure interpretatioll. La grande difficulté t'n ~'econnaissance structurelle est la
représentation des primitives et des rclar.ions qui les lient: heaucoup de travaux ont été
faits en ce sens dont l'un des plus imeressélnts l'sr la rcpresenration par un arbre cyclique.
Cette représentation est une structurl' qui dl'nit \\111 objet glë\\CC à. un arbre dont les arcs
et les noeuds sont cycliques [5 A\\" S9].
CONCLUSION
Nous venons d'étudier les liens entre le graphisme, la reconnaissance des formes et le
traitement d'images, et nous avons fait le point sur la segmentation d'images. Un problème
qui apparemment n'est pas une préoccupation de la. segmentation telle que présenté plus
haut, est qu'au lieu de fusionner dt'ux régions en fonction de la distribution des niveaux
de gris. le faire à base des objets y'ue représente la scène, cela signifie la connaissance du
milieu sur lequel on travaille, on pourra donc faire appel ù une base de connaissances du
milieu [HAR 84], [PAV 90]. L'utilisation de cette information sémantique en segmentation
d'images est essentielle à la reconnaissance d'images haut niveau et mérite des recherches
sérieuses: notre but ici n'est pas d'apporter une solution immédiate à ce problème: nous
nous préoccupons de faire ressortir les formes de chaque région en utilisant des structures
de données particulières. Pour modcliser les formes no ilS utilisons des structures d'arbres
2n-aires qui est l'objet du chapitre suin1llr.
15

CI L\\ l' 1'1' lU': II
/
REPR.ESENT.ATION QUATERNAIRE
ET
STRUCTURE D'IMAGE

C/La.pltre [[
Hepré:;erLlattorL Q'uaternatre et structu're d'[ma.ge
INTRODUCTION
L'image d'une scène est un ensemble de pixels ayant chacun un niveau de gris et ou une
couleur, information qui généralement ne suffit pas, ou plus exactement n'est pas adapté à
certains traitements et algorithmes tels que ceux figurant dans les méthodes pyramidales.
~ous nous proposons dans cette partie dH travail d'étudier une modélisation quaternaire
de l'image qui découle de la théorie des graphes.
;\\Tous parlerons d'abord des graphes et des arbres ce qui. llOUS prernettra de faire quelques
rappels sur cette théorie dans un cadre un peu plus général. Nous aborderons ensuite les
arbres 2n (n = 1. 2, 3) et nous finirons l~n parlallt dl' la manipulation des arbres quaternaires
auquels nous portons un interêt particulier l'll raisoll de son utilité dans ce travail.
11.1 GRAPHES ET ARBRES
Définitions:
- UIl graphe est un ensemble de nownd,j connectés par des arc.>.
- Un chemin du noeud A à B est une suite d'arcs allant de A à B.
- Un cycle est une suite d'arcs dont le début et la fin sont les mêmes.
- Un arbre est un graphe connexe sans cycle.
Nous nous en tiendrons à ces quelques rappels, notre prétention n'étant pas de faire un
exposé sur la théorie des graphes et des arbres compte tenu de la très bonne littérature
sur ce sujet dans [PAV 77], [PAV 82 J, [BOU 8-1], [HARA 69], [SAI\\: 84a], [SAI< 84b].
Grâce à leurs régularités et leurs adaptatiolls aux signaux 1-D. aux images 2-D et 3D,
nous allons consacrer le paragraphe sui nUit aux arbres binaires, quaternaires et octenaires.
:\\ous les décrirons syntaxiquement par des lallgages définis sur un alphabet à deux lettres
pour les arbres binaires, ct à quatre lcttrL's pour les arhres qURternaires et à huit lettres
pour les arbres octenaires [HOP 69].
16

Chapllre Il
Ilepré.'ienlatto'/L Quaternaire et stru.cture d'Image
11.2 LES ARBRES 2n -aires (n = 1, 2)
11.2.1 Les arbres binaires (2-aire)
Ce sont des arbres dont chaque noeud a zero un ou deux fils; cette structure de
données est d'une très grande utilité en traitement de l'information. Notre intérêt se
porte particulièrement sur la modelisation du signal. Pour des raisons de traitement,
nous modéliserons tous les signaux sur llll intl'n'cllle d'amplitude 2r . Nous ferons donc
llne décomposition binaire récursive sur lUll' version discrète de 5 = [0.1], Soit alphabet
.-1 = {0.1} . pour chaque noeud le premier fils sera. étiquetté 0 et le second 1. :.Tous pouvons
considérer toutes les feuilles et les chemins de la racillc à chaque feuille. le langage associé
peut alors représenter le signal.
Exemple:
E
------------
o
1
~
~
o
1
0
1
À
o
1
figure II. 1 : Représentation du langage L
Le langage associé à cet arbre est clone L = {OO. 01, la. 110. Ill}.
Définition:
Nous appellerons arbre k - aire complet de c1egré n l'arbre représenté par de le langage
Ln = A. n où .-1 est un alphabet de cardinal l:.
Exemple:
o
1
/~
~~
o
1
o
1
A
~
A
/ \\
0 1 0
1
0 1 0
1
figure II. 2 : arbre biliaire complet de degré 3


Chap'itrc [[
/?cpré.ît:lLlaltu'IL Q'u.aternatre et stru.ctu.re d'[mage
L =
3
{OOO,OOl,OI0.011,100, 101,110,111}
Il.2.2 Décomposition binaire d'un signal 1-0
Elle consiste en la décomposition renlrSIYL' du signal en deux sIgnaux egaux dont
l'algorithme est le suivant:
Decomp (S)
Entrer
les ignal S
tant Que(signal décomposable)
51 *- pre'tn'I:ère partit d,li. signal
52 ~ Jcu;nl:lnl; jJu.rtù~ du. .>i.ynu.l
Decomp(Sl)
Oecomp(S2)
fintantQue
finOecomp
figure II. 3 : algorithme de décomposition récursive d'un signal 1-0
La condition signal décomposable est liée à l'uniformité du signal sur l'intervalle
considérée: si le signal est uniforme on ne le décompose pas. sinon on le décompose.
Les (5il i EA k forment une parti tion de 5 et 5;: = 5
(ê est le mot vide)
11.2.3 Les Arbres Quaternaires (4-aire)
Ce sont des arbres dont chaque noeud a au plus quatre fils ou pas de fils du
tout. :\\otre modelisation se fera sur des grilles pavées sur Y x :Y qui représelltent
le signal échantiollonné. elle image sera dOlle 1111 signal bidimentionnel représenté sur
5 = [0.1] x [0.1]. L'algorithme de décompositioIl lpHuernaire est donc le suivant:
18

ChaIntre Il
/{epni"e'ILtl1.twf' Quaternat're et st'ructu're d'Image
oecomp(5)
Entrer
du signal S
tantque (decomposabl e)
51 ;-- Cadran 3"lLpérienr ga'lLche de 5: Decomp( 51) ;
52 ;-- Cadran s'upé-r'ie'u'f droit de 5; Decomp( 52) ;
-53 ...-- Cadran inférie'ur ga-uche de 5; Decomp( 53) ;
54 ;-- Cadran inférie'lLT dro'it de 5; Decomp( 54) ;
fintantque
finoecomp
figure II. 4 : Algorithme de décomposition récursive d'un signal 2-D
Remarque: Les (5;)iEAk kEN forment une partition cIe 5 et 5~ = 5
La condition signal décomposable est la même qu'a.u 11.2.1.
11.3 FILIATION SUR UNE ARBORESCENCE.
11.3.1 Généralités.
Une arborescence est un graphe orienté connexe, sans cycle qui a un noeud particulier
appelé racine.
Soit.4 un alphabet, on donne l'application r qui à tout l' de.4* = {€} UA 1 U ... UAku ...
associe l'ensemble des préfixes de .r.
r : .4. ---" .4 *
.1' 1----->
Y
Y = {u E .4* jum = x et lU E A*} I;rll?st la longueur du mot ,C [BER 79].
on dira que x est père de y si et seulemeIlt si .1' E f(y) ct Ix[ + 1 = Iyli y sera alors le
fils de x. on notera .r r y. 011 note p la ferrneturl? transiti\\"C~ de la relation r c'est-à-dire xpy
si et seulement si 3(.Lt)I=I .... n r.el que.r = ·1'1 r .r! r ·1"3", r .l·fI = Y ou encore x est préfixe
de y [SAK S4a].
19

Chapllre l!
f(cp"é;;entaL10IL Q'uater-naire et structure d'Image
Remarque:
xpy si et seulement si 3z, y = xz L.(-lucl-tre dl' !J et - note'. !J Il 1\\ :;, est le plus grand x
tel que .rpy et .l'p:.
le père de l
sera noté r.
11.3.1 Arborescence Qua tern<lire
On peut définir une arborescence quaternaire à partir d'un alphabet \\'
{a,1,2,3}
par:
10)1~EX=>X'EX
2°).r EX=> l"O.rl.r2 . .f'3 E X ce cpli eIltl"aine ~ EX. ("est cl dire ~ == racine. Nous
allons chercher à décrire le langage L formé par les feuilles d'un arbre quaternaire. Notre
objectif est de trouver des propriétés nous penw:ttam de mieux exploiter, à partir d'une
décomposition quaternaire, les informatioIls coHtC'Ilues dans l'image d'une scène.
Il.4 REPRESENTATION DE L'IMAGE
Les structures de données hiérarchiques sont de plus en plus importantes dans les
techniques de représentation en infographie. traitement cl "images, géométrie algorithmique,
système d'information géographique. robor,iqut' ctc ... Elles sont essentiellement établies sur
la décomposition récursive [SA:\\I 54].
L'arbre quaternaire rentre dans cette classe de structure de données, il est lié à un mode
de génération selon lequel chaque noeud a quatre fils ou pas du tout, ce qui nous procure
une structure de donnée agréable à manipuler.
IIA.1 Représentation en mode liné<lire
Le mode linéaire est celui qui nous permet de représenter l'image comme étant un
élément de \\:'Z2, soit I.U une image. I.I! == (.r, LE! Ott J est une partie de 2'1 et Xi un
élément de .V pour tout i élément de J.
Soit à représenter une image disCl'l,tisL'c sur \\lUL' grille SxS nous aurons la représentation
suivante:
20

Chaptlre Il
llepré,;(;ntatlOlL Quaterna-ire el slructure d '[mage
0
1
2
3
4
,)
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
'J-
-1
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

48
49
50
51
52
53
54
55
56
57
58
59
GO
G1
62
63
Figure II. 5 : Représell tation linéaire.
cette figure représente l'adressage en mode linéaire des cellulesde l'image, ce qui ne
permet pas le plus souvent de mieux exploiter les illfonnations contenues dans celle-ci
à cause de la pauvreté, c'est pourquoi dans le paragraphe suivant nous décrivons une
représentation quaternaire de l'image.
1/.4.2 Représentation quaternaire
Pour éviter des problèmes liés à la décomposition récursive nous allons considérer qu'une
image est représentée par une matrice LarTl~c de dimension 21.: ;< 2k . D.T .. Abel [ABE 84]
considère que l'arbre quaternaire représente uue région comme un ensemble de cadrans
générés par décompositions régulières de la région. La décomposition de la région est
constituée de quatre cadrans de coté 2k 1
-
, ensuite la deuxième étape divise chaque cadrans
en quatre cadrans de coté 2k 2
-
ainsi de suite. La décomposition peut donc être représentée
par un arbre quaternaire, où la racine (niveau 0) représente toute la région et chaque
noeud (niveau i) un cadran de côté 21.:-[, Les fils d\\m IlOt.'uel sont étiquetés 0, 1,2,3 comme
l'indique la figure I1.6.
00
01
10
11
02
03
12
13
20
21
30
31
22
23
32
33
a : q-codes
21

C:h(lplLr~ II
Ilq)f'é,,~nttLLw IL q'/luternUtre et str'ueture d'image
f.
a
~
a
l
2
3
a
l
3
o
l
3
l
2
3
b : schéma d'arbre
figure II. 6 : q-codage ( codage (j'uatemaire)
Le codage q'u.aternaire d'un arbre se fait en prenant- pour adresse d'un noeud le mot
formé par les étiquettes du chemin allant de la racillL' (\\U noen<.l. On obtient un mot porteur
des infomations très importantes. car à parrir de cc mot un peut retrouver le cadran père,
les voisins ct les cacirans fils. ce qui sera l'objet (ks prudw,ins développements.
11.5 Représentation physique d'une image par ulle struCture I.jua[ernaire
Nous venons de décrire le modèle théorique nous permettant de représenter une image
sur arbre quaternaire mais cela ne suffit pas pour pouvoir effectuer le traitement. C'est
la raison pour laquelle nous allons présenter l'occupation en mémoire de la représentation
quaternaire proposée. La figure 11.5 nous présente comment sont réparties les adresses des
pixels en mémoire. mais en considérant les représentations décrites dans [PAY 82], [PAY
in, [GARG 82], [SA);! 84], [SAM 82] il est possible de concevoir une autre représentation
des images par les blocs carrés maximaux où chacun de ces blocs sera représenté par
l'adresse absolue du premier pixel en représentation linéaire et du niveau du noeud sur
l'arbre quaternaire. Comme l'indique la figure 11.6 notre représentation s'appuie sur une
structure linéaire faisant suite aux travaux de 1. Gargantini [GARG 82].
Notre représentation utilise une image discretisée sur Ilne grille:23 x2 3 et cette restriction
n'affecte en rien la généralité des COIlCepts ici exposés sauf dans les cas de depassement de
capacité mémoire,
22

Chap'iLre f /
!lepréj(mLaLlo'IL QuaLernai're et structu.re d'Image
0
1
4
5
:2
3
G
T
S
0
12
13
10
11
1-1:
15
a. : q-codage d'une image de dimeflsion 4x4
20
0
16 0
7
8
9
x
x est l'adresse du reglstre en mémoire
~
y est l'adresse effective des blocs sur l'image
b : arbre quaternaire d'une im<lge de dimension 4x4
figure II, 7 : Représentation quaternaire linéaire
Nous avons donc dans la représentation de la figure 11.6 chaque groupe de quatre fils
accolés. L'information visuelle étam au déparr, enregistrée en mode linéaire, il faudra
d'abord faire la transformation avant de passer au traitement. En figure 11.7 nous
présentons la table de transformation du mode linéa.ire à la représentation quaternaire
linéaire, l'algorithme de cette transformation sera présenté au chapitre V.
figure II. 8 : LUT de la représentation Quaternaire
LUT = Look- Up- Table (Table de co·ITf..)pondance)
CONCLUSION
.:'-Jous venons d'introduire la représem([Tion syntaxique d'un arbre quaternaire: du fait
de l'ensemble des traitements à effectuer snI' uut' image pour des fins d'interpretation,le
prochain chapitre sera consacré à. la manipulation syntaxique des arbres quaternaires.
Ce qui nous permettra de déduire des algorithmes efficaces de gestion des informations
contenues dans une image.
23

Ci l ,\\ Il lT lU:: II l
NIANIPULATIONS SYNTAXIQUES
EN
/
REPRESENTATION QUATERNAIRE D'UNE IMAGE

Chapllre If[
Al ampulaliolLii Synla:nq-u.e;; en Repré;;enlalio Tl Quaternaire d'une Image
II\\JTRODUCTION
La représentation des régions est primordiale en traitement et sythèse d'images. Dans
cette partie nous exposons essentiellement ltll formalisme Je la représentation par les
arbres quaternaires, ce qui nous permettra de traiter les informations visuelles. Les arbres
quaternaires ont donné lieu à plusieurs tnn-aux dl' recherche que ce soit en représentation
ou en manipulation ( constructioll d'arbres quaternaires, recherche de voisins d'un noeud
etc ... ) [GARG 82]. [SA:vI 82], [ABE 83]. [SA:'I 84]. [S.~~I 90]. :'J'ous proposons ici une
approche syntaxique de la manipulation des arbres quaternaires.
111.1 GENERALITES
La représentation des images par les arbre::; quateruaires [GARG 82], [SAM 82], [SAM
84] utilise une terminologie essentiellement basée sur les images binaires: les noeuds noirs
(black nodes) sont des noeuds appartenant aux objets de la scène, les noeuds blancs
(white nodes) sont ceux appartenaut au substrat et les noeuds gris (grey nodes) sont
ceux appartenant en même r,emps au substrat l'r aux ubjets de la scène comme l'illustre la
figure II1.1.
La représentation des informations visuelles par les arbres quaternaires demande un
espace mémoire important, c'est ainsi que [ABE 83] propose une représentation par les
B-arbres, dans laquelle la structure de liste Jes valeurs des clés des noeuds noirs peut être
consultée séquentiellement par ordre croissant ou en accès dÎrect. L'avantage ici est de
pouvoir utiliser des arbres quaternaires pour des applications requerant beaucoup d'espace
supplémentaire.
Dans [GARG 82], il est exposé une représentation linéaire qui permet de recupérer 66%
d'espace mémoire généralement utilisé puur la représentation par arbre quaternaÎre. Il y
est aussi montré que les algorithmes peuvent être cxé'cutés en temps logarithmique. Nous
décrivons une représentation linéaire des arbrt's lluaternaires que nous allons manipuler
à. partir du codage quaternaire [SA\\I 84] et d 'un arbre quaternaire qui ne contient que
les adresses des enregistrements contenant les informa tions sur les blocs maximaux et
homogènes.
24

Chapitre [II
Ma.,npu/aLiolLs SynLaxlq'u.es en ReprésenLaLwn QuaLernaire d'une [mage
1
1
a a
1
1
1
1
a
0
1
1
a
a 0
0
a
Image binaire
Niveau 2
Niveau l
Niveau 0
1
2
3
4
5
6
1
8

: Noeud Noir'D : Noeud Blallc, 0 :Noeud Gris.
b : représentation schématique
figure III. 1 : Représentation quaternaire d'une image binaire
111.2 LE CODAGE
:-;ous venons de présenter en figure III.l Ulle représention par les arbres quatenaires
d'une image binaire. Nous donnons ici une représentation linéaire par la même structure
de données des images grisées. les images ont n niveaux de gris. Nous représentons en fait
cet arbre par un ensemble de registres contigus. chaque noeud contient l'adresse du bloc
carré maximum qu'il représente. L'image est décomposée sur un arbre quaternaire complet
de profondeur k et tous les autres noeuds contiennent un indicateur particulier que l'on
choisit de tel manière qu'il ne coincide pas avec l'adresse d'un bloc carré homogène et
maximal (Exemple -l:k.
:-;ous obtenons une structure de données telle que. d'une part on a.it un arbre dont les
feuilles sont les blocs carrés homogènes et maximaux et d'autres part une structure qui
contiendra les informations sur les feuilles alors la. fig'UTt:: III. 3 illustre cette représentation.

Chapitre III
M (L"lLlP'U/lLl'lOll" SYllla:nq"lLe.; Cil nepré"enlalwn Qualernaire d'une Image
1.1 Le p-codage.
Le p-codage d'une image sur 2k x 2k sera l'indexation des sites de a à 4k - 1
lié au mode linéaire, le p-code d'un site est donc un mot binaire de 2k bits. Le p-code
sur 2k bits se décompose en 2 mots de k bits. Soit Ull site s le p-code de s sera noté p(s).
Sur 2k bits nous aurons donc la représentation interne suivante.
2k-l
k
k-l
a
_
_
_, - - - 1
,
p[.(s)
pe( .,)
indice de ligne
illdin.' cle col0l1lle
figure III.2
Représel\\[~[ioll interne d'ull p-code
1.2 Le q-codage
Le q-codage d'une image est l'indexation liée à la représentation par un arbre quaternaire
Soient s un site et q( s) son q-code , les q-codes sur une image 21" x 21" admettent trois
représentations :
une représentation littérale qui correspond au mot de k lettres sur l'alphabet S =
1"
{a,b,c,d} m = ala2 ... ak, m EL
-
une représentation numérique en base quatre où on a les correspondances suivantes
a -
0, b -
1, c -
2, d -
3 d'où m = mlm2 ... mk et mE {0,1,2,3}k,
une représentation numérique en base deux où on a les correspondances a -
00,
b -
01, c -
la, d -
11 d'où m = ml m2 ... m'2k qui correspond bijectivement à un
mot de 2k bits est un élément de {O.l}2k.
En considérant intuitivement la reprl'sematioll littérale du q-code, chaque lettre (de
gauche à droite) correspond à une subdivision en quatre comme l'indique la figure III.3.
Concrètement soit m = ml '11'2 .,. ml; llll q-code. chaque lettre ml, m2,.'" ml" correspond
il Ull décalage dïndex. ct par consl'qllem illdique lUle dc:colllposition additive du p-code :
a
a
b
2k - 1
lettre mi
= { --,> decalage { ')2k-i
C
d
22k
i
- i + 2k -
26

ChapÜre /1/
Exemple: si k = 4, on a une image de 16 x 16 bits soit 256 bits
q(,,) = abcc/
p(3) = (0) + (28 2
1
1
-
) + (2-1-3) + (2 1-
+ 28 - )
= 0 + 2ô + 21 + 2u + 2.1
= 83 (en base dix)
= 01010011 (en base deux)
= 1103 (en base quatre)
·r
_1

Chapitre { rr
J'vI !.LlLlputlll1.on.s Synta,CI'lu.r;.s en Il,,!, ré"enta/LOn Q'uaternaire d'une Image
1
1
1
0
:2
2
a
a
2
2
1
3
.)
:2
-l:
5
fi
: Image en gris
1
Niveau 0
" /
~~
Niveau l
Li~~
Niveau 2
arbre quaternnÎl'e des adl'essès des blocs carrés
no
L
c
0
a
0
0
1
0
1
0
:2
1
0
a
3
1
1
0
4
0
2
0
!:"lFOIU1:\\TIONS
5
0
3
0
1
6
1
2
0
1
1
3
0
s L: I~ u:s
1
8
:2
:2
0
1
9
:2
3
0
1
BLOCS C\\RRES
1
10
3
2
0
11
3
3
0
12
.)
0
1
1
L :représente la ligne du premier pixel du bloc C :représente 1J. colollne du premier pixel du blocN : représente le
niveau du bloc dans l'arbre qua.ternaire, et le q,cQck ~e retrouve eu ulili~,Lnt l'algorithme décrit dans [GARG 32]
b :Table de corl'espondance
figure III. 3 : Représentation linéaire d'une image grisée
28

CIWfiLl"~ fil
l'lIu.1L11JnI1l.L1.0n.; SynL'LLi'I'J.<:·; I;IL 1~<:frr':'.;r.nLul~on qualCTTLalTe ri. 'une fTTLage
Théorème
Sur une image 2k x 2k sices, pour tous les sices s et t tels que:
p(s) = P2k-l .,. PIPO (p-code en base cieux)
q( t) = q2k-l ... ql qo (q-code en base cleux)
(1:ii = O.... ,1-: -1)
Démonstration: si rni est la ierne lettre du q-code 011 a la la table de décomposition suivante:
If I,
(t2J,:+ 1 -:!.j
Ij:!. k -2 J
jJ'2k-j
Pk-j
a
0
0
0
0
a
0
1
0
1
b
1
0
1
0
c
1
1
1
1
figure IlIA: table de transcodage p-code/ Q-code
c'est-à-dire que q2k+ 1-'2j = PU- j l'Il posalH 2/; - j = i + 1.: nous avons) = k - i et
2k - 2j + 1 = 2k - 2(k - i) + 1 = 2i + 1 (rOÙ i]2i+l = Pi+k.
q2k-2j = Pk- j en posant i = k - j on a j = 1.: - i ct 2/..: - 2J' = 2i et donc q2i = Pi et nous
avons le théorème.
1/1.3 RELATIONS DE VOISII\\lAGES
Chaque site sur une image a une position :;pôcifi4Uè par ra.pport aux autres sites que
l'on caractérise le plus souvent par les relations géographiques Nord, Sud, Est, Ouest notées
respectivement N. S. E, W.
29

C/ta.pLl rt: !I /
Théorème
Sur une image 2k x 2k sites. pour tous les sites s et t tels que:
p(s) = P2k-I" ·PIPa (p-code en base cleux)
q(t) = q]k-l ... qlqo (Cf-code en base cieux)
(\\:Ii=O .... ,I;;-l)
Démonstration: si mi est la i eme lettre du ([-cod" on a la la table de décomposition suivante:
/11 1
(jlk·~
-, )
!j'LI. -1 )
fJ'lk-j
Pk - j
a
0
0
0
0
a
0
1
0
1
b
1
0
1
0
c
1
1
1
1
figure IIIA : table de transcodage p-codejq-code
c'est-à-dire que q2 k+ 1-'2) = P'lk - j Cil posanr 2/.' - ) = i + h: nous avons} = k - i et
2k - 2) + 1 = 2k - 2(k - i) + 1 = 2i + 1 d'où 1]21+[ = jJi+k.
q2k-2j = pk-) en posant i = k - ) on a) = h: - i ct 21..: - 2j = 'li et donc q2i = Pi et nous
avons le théorème.
111.3 RELATIONS DE VOISII\\lAGES
Chaque site sur une image a une position ,,;pécifiyue par ra.pport aux autres sites que
l'on caractérise le plus souvent par les relations géographiques .:Jdrd. Sud. Est. Ouest notées
respectivement N. S. E. W.
29

C/wpllre 1fi
M LLIUP'Il/<Llum., Synla.l:l,/(LC., CiL /l':f1ré8CnllLllOlL qtwlernal're d 'une Image
Les relations précédentes ne s'appliquent que dans le cas du traitement d'images en
réseau carré. ~[ais si le traitement se fait en réseau octogonal, il est nécessaire de définir
des relations supplémentaires NE, XiV, SE, Sn" ce qui correspond respectivement aux 4-
voisins et aux 8-voisins dans la litterature habituelle [PAV 77], [PA\\' 82]. Etant donné un
pixel p, les figures III.5.a et III.5.b illW3tt"Cllt t"l':;peetivcment les relations de voisinage en
réseau carré et octogonal.
N
NvV ,N NE
vV
p
E
vV
p
E
S
S'V
S
SE
b : Ré.~eu.1L octogonal
figure III. 5 : Relations de voisinage du pixel p
111.3.1 Voisinage entre deux sites.
Soient deux sites s et t de 5 (*) et p E R = {N, S, E, 0, N E, NvV, SE, SW} on dira
que test 'Uoisin.p de s si t est au p de s et on notera t = p( s); à partir de cela nous pouvons
définir ~P telle que
111.3.2 Adressage par p-code des voisins des sites
Soit s un site donné sur une image, le tableau suivant donne le p-code du voisin-p de
s, p est élément de {N, S, E, ~r,.v E, .v~.v, SE, SvV} en fonction du p-code de s. Nous
aurons t = p(s) p(s) est le p-code du sites
S
:\\(5 )
S( s)
E(s)
YV(Si
:"E(s)
:'J\\V( 5)
SE( s)
SvV( s)
,
t _:J k
, +1 k
, +~ù
(_ :.!J
r -
'l'" ... 1
1 _
2 k _ 1
,+zk +1
'+2 k _ 1
figure III. 6 : Table de détermination des adresses des voisins d'un site.
(,,)
S c'est l'ensemble des sites d'une image, si l'on représente une image par un arbre
quaternaire on pourra indentifier S à LI.: Olt L = {a. b, c, cl}
:30

Chapitre III
!vi a'fl~pu.latio".'i :3Y'Lt(U:H/U.C:., elL Représenlatzon Quaternaire d'une Image
par exemple nous aurons s ~ Er ...... p( r) = p(.:;) + 2°
111.4 SYSTEME DE REECRITURE ASSOCIE A LA RECHERCHE DU Q - CODE DU VOISIN D'UN
NOEUD.
Avec la représentation par les pointeurs H. S.-\\).IET [S.-\\).1 S2] nous présente les tech-
niques de recherche des voisins dans le:; arhres quatenuüres qui permettent de determiner
l'adjacence en direction horizontale, verticale et diagomrle et il y étudie aussi la complexité
temporelle des algorithmes utilisés. D.J ..-\\bel [.-\\BE 83] nous propose une manipulation
de la représentation des arbres quatemaircs par les B-arbres; ).I.H. Loew et LI Shu-Xiang
[LüE 86] présentent une méthode de recherche des voisins d'un noeud basée sur la position
et la taille du noeud déduit du q-code. :.'\\ous utilisons ici nos règles de production appliquées
aux q-codes pour déterminer les voisins, père, fils ou mures relations d'un noeud dans un
arbre quaternaire. Celles-ci reposent sur quatre proposirions.
Definition :
En faisant une addition binaire sur k bics, si IHI bic de poids fort (bit 0) nous obtenons
la retenue 1, nous aurons un débordement que nous désignons par *, et on l'appelera
indicateur de débordement
Proposition 111.1 (Algorithme de l'opérateur Est)
Si s -- s' = E( s) et si p, p', q, q' désignent respccch'cment les p-code et q-code de s et
s'et * designe l'indicateur de déborclemcm
si p' est le p-code du uoi"in - E de s il correspond à l'incrémentation du registre
PC = Pk-l ... Po
- si q' est le q-code du uoi.:;in - E de s il concspolld à llne E-incrementation du mot
q = q(I) .•. q(k) suivant les régIe...,' suivanres :
CL - . b. b ~ HL. c - . d. cl -
*c
31

C/wptlre III
il;( lllLl.p·/I./all.()n., SYILtlL.I"I.I/ne., "n Repré"entatL07l Quaternaire cl 'une Image
Démonstration:
Cet te démonstration utilise l' algori t hll1e cl 'incrémentation en base deux
(p'C
-
PC + 1etp' L = PL)
pc = Pl.:-IP~·-l" 'Plpa ël':eC q(l.:) = fJUJ{).qiJ.. - 1 ) = IJk+IPI .etc .. , on a successi\\'ement:
p' 1.: = P + 1 dOllC qdl.:) = q(l.:) + 1 c'est ù. dire a' = b. h' = a. c' = d. d' = c
ceci est dü au fait <IU'OU ne challge <pie k' dC'llxil'llll' digit dc a.b.c,d en base :2, mais il
y a report (drapeau *) si p = 1 C'CST, ù dire q(l.:) = /) ou cl t<tr b = 01 donc on al + 1 donne
oavec un report de 1 d = Il dOI1l: ou a 1 + 1 douue 0 an'c uu report de 1 ce qui implique
les règles
Cl - - b. b -- '1«1. C ~ cl. d -- *c
- si pas de report l'opérateur est tenniné.1es autres registres restant inchangés
-si report (*)
il faut faire P'i = PI + 1. c'est-ù-dirc E-illcreulemer le registre q(I.:-2) avec les memes
règles.
-si pas report 1'opération est terminée.
-sinon faire P'2 = P2 + 1 c'est-à-dire E-incrementater q(I.:-2)
-L'opération se termine normalement sauf s'il y Cl. report après incrementation du
régistre q(l) = P2k-lPk-l ce cas se produit si et seulement si Pk-I = 1 avec P'k-I = a :il y
a donc débordement du registre pc ;cc' qlli (.qui\\·;Hlt au passage à la ligne en mode linéaire.
Dans ce cas le site s n'a pas de l'oisin - E.
Proposition Il 1.2 (Algorithme de l'opéra teur 5ud)
Si .s -- s' = S( s) et si P, p'. q, q' cl(~signent respecci\\'ement les p-cade et q-cade de s et
~' et 'fC clesigne l'indicateur de déborclement
- si p' est le p-code du l'oisin - S de s il correspond à lïncrémentation du registre
PL = P21.:-1 ... PI.:
si q' est le q-code du l'oisin - S cie ,'j il correspond a une S-incrementation du mot
q = q( 1) ••• q(l.:) suivant les régIes sui\\'i:Jntcs :
a ---+ c. b ---+ cl, C -- *Cl, cl -- *b
3:2

ChaptLre III
M amp.,LiallOn.; Synlaxz'i"ILe.; en Uepni8enlallOn qualernaire d'une Image
Démonst ra tion
cette démonstration utilise l'algorithme d'inl'rémentation en base deux
(p' L = PL +
1etp' c = P )
PL = P2k-lP2k-'1·· .Pk+lPk avec q(k) = PkPü,q(k-l) = Pk+lPl ,etc
on a successivement: p' k = [Jk + 1 donc qd!.:) = q(!.:) + 1, c'est-à-dire a' = c, b' = d, c' =
a, d' = b ceci est dü au fait qu 'on lle change que le deuxième digit de a, b, c, d en base 2,
mais de plus il y a report (indicateur "'j si p = 1 c'est à. dire q(k) = C ou d car c = la donc
on a 1+ 1 donne a avec un report de 1, ri = 11 on a 1 + r donne a avec un report de 1 ce
qui implique les règles
- si pas de report l'opération est terminé.1es autres registres restant inchangés
si report (*)
il faut faire p' k+ 1 = Pk+ f + 1, c'est-il-dire S-incrémenter le registre q avec les memes
règles.
-si pas report l'opération est t('rIl1iu<~e.
-sinon faire p' k+'2 = Pk+'1 + 1 c'est-il-dire S-inerc'lllenter q(!.:-'l.)
-L'opération se termine normalement sauf si il y a report après incrémentation du
régistre q(l) =P2k-1Pk-l ce cas se produit si et seulement si P2k-l = 1 avec pl 2k-1 = a :il
y a donc débordement du registre PL :ce qui équivaut au passage à la colonne suivante en
mode linéaire: Dans ce cas le site s n'a pas deuoisin - S.
Proposition 111.3 (Algorithme de l'opérateur Ouest)
Si s -. s' = 11"( s) ct si p, p'. q, q' désignent n:specriVCIIlcIlt les p-code et q-code de s et
s' et * désigne findicateur de débordement
- si p' est le p-code du voisin - 11' cic s il correspond à la décrementation du registre
PL = Pk-l
po
o
• •
si q' est le q-code du UOISln - 1V cle s. il corresponcl cl lIne H:-incrémentation du mot
q = q( 1)
q\\k) 3uiranr les régIes Slli";111tC'-; :
o
• •
33

Chapitre f1/
M amp'I.liat'ions Syntaxtctues en Représentation Quaternaire d'une Ima.ge
Démonstration:
Elle utilise l'algorithme de décremcntatioll en base deux (p' L = PL + l, p' c = pc ) et
la suite de la démonstration est analogue à celle de la proposition II1.1
Proposition 111.4 (Algorithme de l'opérateur Nord)
Si.:> -->./ = N(.:» ec si p,p'.q,q' désignent respectivement les code et q-code de.s et s'
et * designe l'indicaceur de débordemenc
-
si p' est le p-code du L'oi.:>in - S de s il COITcspuncl él la décrementation du registre
Pc = Pk-I '" po
- si q' est le q-code du voisin - E de .:i. il wITcs]Jond fi une S -incrémentation du mot
q = q(l) '" q(k) suivant les régIes suinlfltcs :
Démonstration :
Elle utilise l'algorithme de décrl'lllcntation L'll base deux (p' c = Pc - l,p' L = PL ) et
la suite de la démonstration est analogue à l'elle de la proposition 11.2.
Remarque :Les relacions NE, NH', SE, SH" sone des relacions composées des relations
N,S,E,~V. Ainsi soient fI et f'2 éléments de {N,S,E,HT} pour tout.s élément de S,
nous aurons:
V.2 Notations
Soient .s et t deux sites de S. ql et t]2 leurs q-codes respectifs, nous pouvons écrire sans
ambiguité :
où r est élément de R. En utilisant la forme postfixée nous aurons:
Désormais nous utiliserons récriture (1) pour signifier <ptc .j :::rj t. Soient al et a2 éléments
de S et fI élément de R \\ious utiliserolls
34

Chapilre [[[
M ampdalwn.~ Synlu.;I:'l,/IU3 ,m llepré8enlalion Qualernaire d. 'u.ne {mage
Nous obtenons les règles de production suivantes
aE -. b
aS -. e
aH' -. IVb
aN -. Ne
bE-. Ea
bS -. d
bH' -. a
bN -. Nd
cE -. d
cS -. Sa
cH' -- H' d
cN -. a
dE-..Ec
dS -. Sb
dB:' -. c
dN -.. b
PE
Ps
p~\\/
p.v
en posant P = PEUPSUPSUP\\\\' IlOUS POt\\\\'OIb déotinir Lill système de réécriture permettant
de générer grâce à P les voisins d'lm site.
Exemple de génération du uoisin - E de (Lcb(La pour k = .)
si I..~ = .). la. génération du t'oi.,ill - E dL' Ut'iJUli L·:-,t : ucbuaE = acbab
111.5 DETERMINATION SYNTAXIQUE DES VOISII\\lS D'UI\\l BLOC
VU Le Bloc
Un bloc est un cadran dans la décomposition récursive d'une région, donc un noeud
de l'arbre quaternaire.
Dans ce qui précède nous avons identifié un site à son q-code , le q-code d'un bloc sera
le mot formé par les étiquettes du chemin de la racine au noeud correspondant au bloc
dans l'arbre quaternaire; on pourra donc identifier un bloc à son q-code.
Pour une scène 5 de 2k x 2k sites. on cOllsidère le langa.ge
I:(k) = L O U Liu ... :LI> = {.r E L:* / l.rl S; q
Un bloc peut donc étre considéré comme UIl élément de L( k). une partie de 5 donnée
par l'application.r E :L(k) -. B(.r) E PIS) (ensemble des parties de 5) avec
B(:r) = {s E 5 / .r T q(,,)}
T est la fermeture transiti\\'e de la relation f-
B(x) sera le bloc de q-code l'
- liB) = !.rI est la longueur du mot .r élément de L:(k)
- niB) = 1..: - liB) est le niveau du hloc B.
- d(B) = 2n (B) est la dimension du bloc B.
- t(B) = d2(B) est la taille du bloc B.
35

Chapttre 1/1
kt (~mpulat101L~ S'1ILIu.;T.'/.lrue.~ en Uepré.ïeILlalto'IL Quaternatre d 'une Image
- Ô(B) est la base du bloc et a pour q-code .ral/(·-l)
La base du bloc est donc le premier site de B pour l'ordre de balayage lexicographique
donné par le q-code.
111.5.2 Voisins de identique à celle du bloc
Théorème 111.2
Soient A(al) et B(b l ) deux blocs. OH dira que ,1. est adjacent à B si et seulement si il
existe une relation p E {S, S. E, W. -" E. srr. SE. SIl'} telle que al = blP. l(Al = l(E).
Démonstration
Dans ce qui précède nous avons utilise- la notatioll al = blP pour exprimer le voisinage
par la relation p des sites de q-codes al ct bl • nO\\1S la conserverons ici pour exprimer le
voisinage de B( b1 ) et A( al) par la relation p. Sans nuire à la générali té, considérerons que
l'on a une image de 2k x 2k ce qui nOllS a.rnèm' il cOllsidércr .1.(al) et B(b)) comme des
pseudo-sites qui seront voisins si et seulement si al = b1P et on a le théorème.
En considérant le système de r('écriture décrit cn IlIA on peut générer tous les voisins
de même taille d'un bloc.
Exemple: Soit abc le q-code d'un bloc sur une image 27 x 27 on aura abcN = aba et aba
sera donc le voisin - N de abc
Remarque: Soit P E R et x E L:( n) où n est la profondeur de l'arbre quaternaire complet
associé à la scène, J' n'a pas de l'oi.,in - p de 11l(~11lC taille si et seulement si rp = py
r
" ' ( n)
'\\"' -
{
b
l}
Y ~ G
'L..J -
a. ,c. ( .
111.5.3 Voisins de tailles différentes d' uIl bloc
Dans cet te partie nous \\'mt!oIlS déterminer les \\'OISmS cl \\m bloc qui ont des tailles
différentes de celle du bloc considérer~onsuppose dans la suite que les blocs sont disjoints.
36

Chapitre [If
M <l.mp-ulatwIL., 3YILta.nq·u.i~;:; ~H [l~pré;:;t;Htation Qu.aternaire d'une Image
Théorème 111.3
Soient B un bloc de q-code x EL, Sl n = n( B) et :3 = xa rl est le q-eode de la base
cIe B alors B = {t E Sjq(t) = .ranEISJ.O::; i < 2/1,0::; j < 2} . où zEiSj est la relation
posrfixée de SJ(E i (::)) ec E' esr la COI1l[)()S(~C 1 fujs dt.: l'ojJuraceur est (E).
Démonstration
La propriété énoncée dans le théorème ('::lt tri\\'inle dans les cas suivants:
Il = 0 car B = {:3} = {.r}
n = 1 car B = {xa, l'b. x·c ..rd}
[~.
.ra.
.rh
si
15
E
.re
:I.'d
La démonstration du théorème repose sur la définition même du q-codage, soit q le
q-code de la base ,8 = .1~Y
Xl
XI
YI=a
Yn_l=a Yn=a
...-----A-.
,.....".....,
,.....".....,
A
,.....".....,
q = 1}2k-IQ2k-2·,· Q2k-21+IQ2k-'2Î 00
00
00
L'opérateur El correspond à l'addition (sans débordement)
Pk-.rl ... PljJ() + 1
l'opérateur SJ correspond à. l'addition (sans débordement)
P2l.;-1 ···Pk-t-ljJk +)
37

ChapItre [[1
en conséquence. tant que i a au maximum n chiffres 1 (cadrés à droite) dans sa
représentation binaire, ;JEt est de la forme Xll'Z ... X II .1)IYZ ... y" ce qui ne peut avoir lieu
que si: i S 2n 1
2
-
+ 2n -
+ ... + 21 + 2° = 2n - 1 résultat identique pour bEl; on a donc
démontré que:
{t E Sjq(t) = 3E';O Si.) < 2"} C B
réciproquement. l'unicité du q-code (ou p-code) nSSUl'L' y.uc l'application:
Corol/aire 11/03.1
Un bloc B de niveau Il est UIl
carre
cIe 211 X 2n sites et par suite connexe pour les
relations de voisinage ,:::P p E R.
Corol/aire 1" 03.2
La base J( B) d'un bloc est le "premier" (=lc plus perit )pour les ordres totaux suivants:
- l'ordre de balayage lexico-numérique du p-code M:d ,..... p(,j) S p( t)
- l'ordre lexicographique du q-code en coIlveIlanc que (l < b < c < d
- l'ordre numérique du Cf-code.
Corol/aire 111.3.3
Remarque: Soit B( x) un bloè et LI:. J. f. Ô représentées comme sur la figure III. i" représentant
le bloc alors ex = xbn; ,3 = .ra n
Il
; 1 = IC ; Ô = l'd", olt n = i(B).
38

Clw{rilre 1//
.3
figure III.7
Représent;]tion des q-codes des quatre coins d'un bloc
111.6 RELATION D'ADJACENCE
111.6.1 Adjacence de deux régions
Deux régions ri et "2 sont d.i tes adj ilCCll rC''; :ii il l'xi,; re dellx si tes "1 E rI et 82 E2 r tels
que SI -:::::.IJ 82
pour un r E {N,S.E. H·.~VE.XTF.SE.Sn·}= R
Remarque: Soient A. = A(ar) et B = B(b l ) tels que 11,(04.) = 11,(B) A. et B sont adjacents si
et seulement si A. -:::::.P B pour un p E R.
111.6.2 Adjacence de deux blocs de tailles différentes.
Soient A. = A( al) et B = B( bl ) avec n( a) t= n( B) on dira que A est adjacent à B :
(')
.
(1·)
·B):J
",n(B)-n(A)
l
1
1
sl11,:1.
<11,(
:JE,L
te
quefll,r=JIP
") .
(B)
' I : J
~n( 4)-n(l.J)
l
b
(11
5111,
< 11,(."1) :J E ~ .
te que
I,r = (lIP
pour p ER.
111.7 ALGORITHME DE DETERMINATION DES VOISINS D'UN BLOC.
En considéram l'ensemble des q-codes l'Cprl'selltam l'arhre quaternaire associé à une
information visuelle sur une grille 21. x 21.' llOllS pruPOSOW.i nn algorithme original permettant
de décrire le voisinage ci 'un noeud.
:39

Chapllre III
AIllltLp'lL/al'iùn.; Synla.:r.zque,.; en Repré.;enlalzon. Quaternaire d'une Image
111.7.1 Père d'un Bloc
Le père d'un bloc B(.r) est un bloc B(y) tel que' y r .r d'où IJ est le préfixe de x de taille
I.rl - 1. nous noterons donc pere(x).
VII1.2 Fils d'un Bloc
Tout bloc a éventuellement quatre fils et k::; fib ::;ont dL' types sl·V,.v E, SW. SE en
conséquence pour déterminer un fils, il faut :i<1xoir quel type de fils on veut trouver. la
fonction qui détermine le fils de B(.r) ::;era UllL' fonction de deux variables que l'on notera
fils(:r, T) 0\\1 T est le type de fils. COIllIlle nO\\ls Ln'oIls vu précédl'mment XIV, NE, SIY, SE
sont codés respectivement 0.1. 2, 3. Fils(.L'. T) est dUlll': la concatenation de x et du code
de T.
Exemple:
Si
.r = 1023
pere(.r) = 102
fils(x, ~VI'l") = 12030
111.7.3 ALgorithme de détermination des voisins.
Soit LFQ le langage des feuilles de l'arbre quaternaire associé à une scène. L'algorithme
a trois étapes. Soit B = B(x) un bloc .les étapes sont les suivantes:
Etapd
Elle permet de generer les \\'01S111S éventuels de memes tailles s'ils existent, soient
.V =
B(n).S =
B(.3),E = B(e).lr =
B(w),.VIV =
B(r),~VE = B(q),SE =
B(:::), sn' = B(t) ceci grâce à P(:iystèmc de rt::écriture) décrit plus haut .système qui
génère le langage L(.r) = ({U,.rC,} )rllFq ott Ci E R qui est l'ensemble des voisins de
même taille.
-tG

Chapdre III
M ampU/lLlw IL.'> SYlL/cl.l:L'i ue,; ~IL Ilcp.,.,;"enlalwn Q'ualernalTe d'une Image
Etape2
- Elle consiste à utiliser les voisins calculés à l'étape 1 pour déterminer les voisins de
tailles plus petites que l'elle ùu bloc considé'rl',
Lp('l') c'est le langage des \\'oisins de I3(X) dL' taille' inférieure' il I(B) et au Re du bloc
B(.r) p E R. posons fit = 1/ - n( B) où Il est la profondeur de l'arbre.
si n E LFQ alors L;v(.l.') = {y E n{c.il}tlll).y E LFq} sillon Ls(x) = 0
si s E LFQ alors Ls(:r) = {y E s{a.b}(IIIJ.,y E LFQ} sinon Ls(x) = 0
si e E LFQ alors Ld:!.') = {y E e{a.c}(Ill J • y E LFQ} sinon LE(X) = 0
si LU E LFq alors L\\y(.r) = {y E n{b.d}llllJ . .I} E LFQ} sinon Lw(x) = 0
si q E LFQ alors L.vEl:L') = {y E q{b}lIllJ.,Ij E LFQ} sinon L.vE(l·) = 0
si r E LFQ alors LN\\Y(.I.') = {y E r{a}(m).y E LFQ} sinon L:v~'V(x) = 0
si:: E LFQ alors LSE(l') = {y E ::{d}(ml. y E LFQ} sinon LsE(.r) = 0
si t E LFQ alors Lsw(:r) = {y E t{C}lllli. y E LFQ} sillon LsH'(r) = 0
Etape3
- Elle consiste à utiliser le résultat de l'éwpe 1 pour déterminer les voisins de tailles
supérieures à t(B). Soit 1 = l(x),nous posons:
n
= nl ... nl,S = ,sl ... SI,e = tl ... e/,W = Wl ... W/.q = ql ... ql,t = tl ... tl,:: =
::1 ... ::/,1' = 1'1 ... 1'/ ;soit L:(x) le langage des voisins de l,à (J qui ont une taille plus
grande, l'algorithme suivant nous permet de l'obtenir.
Debut
L:(x!i- 0
Dx
-
pere
(.rI' )
Dy
pere
(.r!
0 -
Tantque
(Dx
=;f
Dy)
faire
debut
Si
Dy
E
LFQ
alors L~(x) i-
Dy
sinon debut
Dx
pere(Dx)
Dy
i -
pere (Dy)
fin
fintantque
Fin
figure III. 8
Algorithme de déterminJtion des voisins de taille supérieur d'un bloc
':1:1

ChufHLre III
Ma"'I,pu/,Llw /1.., SynLiL.J:i.I/ILe., CIL 1l(;présenLaüon QuaLernaire d'une [mage
L'ensemble des voisins d'un noeud x sera donc L(.r) U L~(x) U Lp(x).
III. 7.4 Exemple de détermination de voisins
::-Jous voulons déterminer l'ensemhle Jes voisins de x de la figure III.5.2 par l'algorithme
précédent.
LFQ = {O. 10. 11, 13.20.22,30,31. :3:2. 33.120.121. 122.123,210.211,212, 213}.
1
1
1
1
0
U
0
0
1
1
1
1
U
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
ull U 0 1
0
()
0 ~ 1 1 0 0
')(
0
0
0
0
1
1
0
0
~ o o o o o o
o o o o o o
~
1
1
figure III. 9 : Représentation du noeud x
Eta.pe] ,
30.V = 3.Y2 = 12 tj. LFQ
30S E = 12E = 13 E LFQ
x = 03
305 = 32 E L FQ
30SH" = 32H" = 3vV3 = 23 E LFQ
{ 30E = 31 E LFQ
:30SE = :32E = :3:3 E LFQ
30n: = 3rV1 = 21 'i LFQ
:3USH" = 12H" = 1rV3 = 03 1. LFQ
12. 21. ct 03 Ile sont pas démcm de LFQ clOtH' ilc'.,;t possiLle quïl existe des voisins de x
qui sont plus petits ou plus grands.

Chapttre [[1
Ma.mp,ûlLlwlL., Sy,tllL:nqu<:" en Ilcpré,,<::nllLlwn Qualernaire d'une Image
Etape2.
12{2.3}(ll = {l22.123}
TI = 12 {
LN(.!') = {122,123}
21{1.3}ll) = {211.213}
X2 = 21 {
L~v(x) = {211.213}
03 {0}(1) = {030}
X3 = 03 {
L.\\'\\\\"(.r) = 0 030 t$ LFq
Eta.pe:J .
il ne reste plus que 03 qui n'a pas de fils qui soit de taille plus petite, ni voisin de
même taille: il existe donc u ancêtre de 03 qui soit voisin de x, Donc en appliquant
l'algorithme de l'étape 3 on trouve u = 0: d'où l'ensemhle des voisins de ~. est
{32.31,12.23.33.122.123.211.213.0}
CONCLUSION
Nous venons de présenter une méthode syncaxique de détermination des voisins d'un
noeud da.ns un arbre quaternaire. ce qui nOllS permettra. de représenter une région
d'une scène comme un langage. :.Jous axons défini des règles qui sont susceptibles de
développements et de résultats syntaxiques. mais dans notre travail nous nous sommes
simplement limités à leur utilisation dans la description du voisinage d'un noeud; cela nous
permettra de proposer dans le chapitre sui\\'ant un a.lgorithme pyramidal de segmentation
d'images.

C Il,\\ PIT lU: 1\\"
/
ANALYSE WIULTI-ECHELLE
ET
TRANSFCIRWIATION DE HAAR

Clwp,ttre 1V
illw.I!},;.; Mu/tt- ~che/le et Transformation de Haar
INTRODUCTION
De nombreuses applications en reconnaissance des formes exigent une représentation
et un traitement à plusieurs échelles. En effet l'analyse multi-échelle est de plus en plus
importante en traitement des images et du signal; plusieurs travaux ont été consacrés
à ce sujet [~vIEY 85], [:"IE\\" 86], [LE~I 86]. S. G. ~Iallat dans [:vIAL 8i] et [MAL 89]
étudie les propriétés de l'opérateur qui donne l'approximation du signal à une résolution
donnée; il montre également la différence cl 'infonuation entre l'approximation du signal à
la résolution '2.1 et 21+ 1 en décomposant le signal sur une base orthogonale de L2( Rn) et
appelle cette décomposition une décomposition en ondelettes: cette décomposition s'appuie
sur un algorithme pyramidal. Il montre égn1c'nH.'nt comment cela peut ètre appliqué à la
compn.'ssioIl cr. au codage cl 'images. ~l la cliscriIlliuClriüll de texture et à l'analyse fractale.
Dans cette partie de notre travail en nous appuyant sur la représentation en arbre
quaternaire d'une image [SAM 84] et [SAM 90] et à la manipulation syntaxique d'une image
représentée par un ensemble discret 5 de sites, nous considérons une base particulière dans
L2 ([0, 1] x [0,1]), ce qui nous permettra à partir des algorithmes pyramidaux de faire du
filtrage dynamique, de faire de la compressioll d'images et d'envisager une segmentation
d'images.
IV.1- TRANSFORMATION PYRAMIDALE
IV.1.1 Transformation pyramidale 1-0
Pn est une isométrie de Rn (où En espace euclidien) de dimension n = 2k définie par
l'algorithme suivant
Entrée: vecteur .r = (.1', J'E[n] E En [II] = {O. L .... Il - l} )
.
[ ]
(TtJÜ
~Iatnce 2 >< :2 T = T
Ttll) avec T*T. = l )
ab
=
T

Til
Sortie: vecteur ~ = (Çi LE[nj E Rn
Pour décrire l' algori thme on formalise le diagramme sui vant

Chap'ltre IV
.\\ /La/y.,,: M·U./tl.o ..fclw/le et Transformatzon de Haar
x=
Ixooo IXOO1 Ix010 IX011 Ix100 IX10l Ix110 IXlll
1
1
l
l
l
1
l
l
l
1
1POO
(Paal IpOl
(POll Ip lO
!P 1Ol !pu
[P 11l 1
l
l
l
l
Ipo
IpOOl !POl
Ipoll \\P l
]P 1Ol jP ll
IP 111 1
l
l
~ =
P
poollpOl
Po 11
Pl
1
PlOlr11
P11l )
1
1
figure IV.l
Diagramme de transformation pyramydale !-D
IV.!.l.! Codage des indices
On appelle p - code la représentation binaire d'un inùice i E ln] avec k lettres 0 et l.
On appelle t - code un p - code privé des zéros ùe queue, Pour tout i E [n], on note p( i) le
p _ code de i dans I{ = {D, 1} k, et q(i) le t - code associé à p( i) dans L Lest l'ensemble
des mots sur {D, 1} de longueur inférieure à k et se treminant pad.
On a card(L) = 1 +2 + .,. +2 k 1
-
= 1 + 22k~11 = 2k
A. chaque étape de calcul, on effectue une isométrie partielle sur 2 valeurs:
T (P":ll) = ( p- )
p..; 1
fJ..: 1
fJ..; est l'approximation et fJ_l le dér.ail dUciig,llal ;\\ ['étape 1.;- : ,-,-' 1·
L'application «troncacure »)p E 1\\ -
q E L est une injection, clonc une bijeccion puisque
card(K) = card(L). L'algorithme sera décrit sur ks q - codes, on tiendra donc compte des
bijections entre ln], 1\\, L. Il s'agit d'un algorithme «sur piace », c\\.'st à dire n'utilisant pas
de "ariables pour les calculs inrermédiaires: .r l'r ~ peuvent donc être implémentés sur le
même tableau de données.
45

Chapttre ! V
il ",dy.,e 1vIu./l,-échelle et Transfo-rrnatton de Haar
IV.l.l.2 Algorithmes de transformations
Algorithme DIRECT
'ri w E L ç...., -
.c..., (* initialisation *)
Pour 1 -- 1 à ~: faire
pour tout ,-,-' E L avec
1 ...., 1 =
~: - 1 faire
C - I;lOClJ + I;JIC,!
Ç....,I ;- T!uClJ + TIICI
fin pour tout
fin Pour
Fin algorithme
figure IV. 2
Algorithme direct
Algorithme INVERSE
'rIw EL X
-ç...., (* initialisation *)
W
Pour i - k à 1 pas (-1) f<lire
pour tout w E L avec !w 1 -
~; - 1 faire
X w -
T;o·c..;o + TO'"l X-'I
Xwl
-
Tto·l: ....u + T I'"\\·1"-'1
fin pour tout
fin Pour
Fin algorithme
figure IV. 3 : Algorithme Inverse
IV.l.l.3 Complexité de la transformation pyramidale Pn
Nous avons toujours n = '2 k
- Le total d'isométries à effectuer est 1 + '2 + -t + ... -;- 2k 1
-
soit 2k - l, c'est à dire n - 1
et c'est la même chose pour la transformation inverse) d 'Ol! une complexité algorithmique
en O( n).
- Il n'existe pas de pénalité de stockage des calculs intermédiaires. sauf celle qui résulte
de l'indexation par les t- codes.
Le calcul d'une transformation élémenta.ire ne demande que 4 multiplications et .)
additions en virgule flottante, soit un total de 6( Il - 1) opérations en virgule flottante.
Proposition 1.1
P n nécessire llne cmoplexicé algorichmique de O( 11).

Chapdre 1V
:\\ [uLly,,; .H'fLUz-JclLclle et Tran;:;formal1on de Haar
Proposition 1.2 Pn est une isométrie et en particulier nous avons:
IV.1.2 Transformation pyramidale 2-D
Dans la suite T P signifiera transformation pyramidale, La généralisation de la transfor-
mation pyramidale de Haar précédemment clénite ne présente pas de difficulté pour une
.
Rnxn
"1.:
Image .r E
avec Il == :.: .
Il suffit d'utiliser Ulle isométrie T == [Tabj",bEI où ,-\\. L':'it llIl alphabet à quatre lettres, et
de réécrire les formules déjà citées plus haut. :'\\OllS Il'allons pas reprendre ce formalisme,
mais résumer la complexité algorithmique cl 'une: T P cn 2 - D, .-\\. vec n2 données, il n'existe
que k == log2(n) niveaux pyramidaux, Pour chaque niveau 1 (1 == 1,2" .. ,/;;), la TP
nécessite 1 + .:1: + 42 + ' , ,41.: - 1 transformations élémentaires, La complexité est donc de
0(4 k ) == 0(n 2 ), c'est à dire linéaire par rapport au Ilombre de données (n 2 pixels).
A titre de comparaison, rappelons que la complexité de la Transformée de Fourier
rapide (dans Cv), comme des transformations en cosinus (dans RN), est en O(N log2(N))
avec N == n 2 , On peut aussi remarquer qu \\me transformation pyramidale en 2 - D : - ne
nécessite pas de stockage intermédiaire
- nécessite au maximum 28n'2 opérations cn "irgu1cs ftottanres
-est isométrique (T*T == [
- est bien adapté l'analyse multi-résolucion,
Nous allons maintenant étudier la construction tensorielle d'isométries 2 - D à partir
d'isométries 1 - D afin de généraliser les T P en dimension quelconque et d'examiner la
décomposition ligne x colonne
IV.1.2.1 Produit rensoriel d'isométries
a) Soient X == EP et }- = Er, clenx espaces ,'ectoriels euclidiens de dimensions p ey q
respecti,'ement, Z == X:=, }' est un espal'e \\'l'l'wricl Je dimension pq, correspondant aux
signaux échantillonnés sur une grille p x q,
Soient {al, i E [pl} et {b i , i E [ql} deux bases orthonormées de X et y,
Par exemple :ai == bi == signal de Dirac en position i dans RP

C/wp'ilre rv
il/L.dy"," MuItL- ric/Lel/c el Transformalion de Haar
bJ = r5) = signal de Dirac cn positiou J claus R(I On sait que Z est isomorphe à Epq , avec
la base al (] bJ égal au signal de Dirac cu positiou(i.j). Par définition, on prendra donc le
produit scalaire de Z correspondant au fait que {ai 'J b) / i E [pl, j E [q]} soit une base
orthonormée.
b) On considére mainteuant RUIle isométrie de X et 5 une isométrie de Y, alorsR 05
le produit tensoriel Je RetS est par définitioIl Ltll cuclornorphisme de Z = X G Y, donné
sur la base de Z par la formule
avec la structure métrique précédcrnrncm donnée sur Z, R:::: 5 estb aussi une isométrie
de Z. En effet:
Ra, = ~ Rk/ul.;
~
k
Sli) = L Sljbl
1
Rai':) Rb) = L L Rl.:iSIJlal.: (] bt)
1.:
1
on vérifie facilement que IIRaiJ Sb) Il = 1.
c) On posera T = R x 5 isométrie de Z = X2 y
IV.1.2.2 Produit tensoriel de Transformations pyramidales
On suppose ici que X = RP et Y = R" avec p = 2.1.: et q = 2.k' k =f=. k' en général
et on appelle Px et Py les T P sur X et Y associées aux matrices R et 5 respectivement.
Par abus de langage, on pourra supposer que R opère sur X et 5 sur Y en les prolongeant
par l'identité en dehors des sous-espaces vectoriels de dimension 2. sur lesquels ils opèrent
dans l'algorithme pyramidal.
T engendré par {(Ll .:::' bl • Il) C DI.;. (L):::-, bl.;. (I) =' li{} . Sans perdre de généralité, on notera:
0.0 = Il,,(LI = (l).IJU = Ok. 01 = bl
(rOll le calcul dérnclltaire suivant
Rao = Rooll u + Rloul
Sbo = SIJObu T Slob l
Ra 1 = Ra 10.0 + R l 1a1
Sb l = SOlbo + S11 b1
48

Cha.pItre [1/
i\\ nll./Ysc M'lllli· échelle el Transformation de H aur
La matrice de T = R (j S dans la base:
sera [T ,ll
a
donnée par:
RIOSOO
RooSol
fT
'
RilSan
R,oSIlI
L
( j J J =
ROIS lli
RoliS 11
R,ISIO
R lo S1l
-1
+1
-1
1
(+1
+1)
Exemple: R = S = fi
+1
-1
RCS=~n; +1 +1 +1)
+1
-1
-1
-1
-1
+1
Dans le cas où dim(X) = clirn(Y) = Il = 21.: Oll a introc1uit les q-codes correspondant
aux indices (i,}) E ln] x[n], dans les IlotatiollS du langage associé L = {w E .4.*/1 w 1:::; k
ct -,-' ne se terminant pas par un D} ail.-1.* =.-tu U .-1. 1 u ... U.-ll.: U ... , avec A. = {D, 1,2,3}.
On obtient ainsi l'algorithme pyramidal suinlllt, paraml'tre. par la matrice orthogonale
[Tao] avec o.,] E {D,1,2,3}
Algorithme PYRAMIDAL
'rI:..J E L '''-1 t- J.:""
(* initialisation
*)
Pour 1 t- 1 à k faire
pour tout ..JJ E L avec
1 .....,
1
t - 1.: -
1 faire
'''-1
LJ
t -
ToJ'-,J
!:.Ja t - LJ TaJ-"-,J
fin pour tout
fin Pour
Fin algorithme
figure i v .4 : Algorithme de tr31lsformation pyramidale 2- 0
IV.2 REPRÉSENTATION PYRAMIDALE 2-D
Dans cette représentation, on peut considérer le cas continu et le cas discret.
-1:9

C'hap'ilre ! V
/llwly.,e A1-ultt-échelle el Transformalion de Haar
IV.2.1 Cas continu
Nous considérons le support d'une image comme étant 5 = [0,1] x [0,1]. Nous
interprétons le q-code de s E 5 comme llIl é16ment de .-1.* n.\\'ec .-l. = {O, 1, 2, 3}. A chaque
q-code q sera associ(' Url pavé de 5, dit hlol' de q - code l! nor.é Bq.
Par définition Bq = [a,a + 6[x[b.1J + d[ avcc () = 2/(11 Aire (Bq) = -llql où a et b sont
les coordonnées du premier pixel de Bq L't som dOllllées par la transformation inverse de
la transformation de la représentatioll liw:'aire <\\. la rcpn:'scutation en q-code décrite par
I.Gargantini dans [GARG 82].
IV.2.2 Cas discret
Le traitement par ordinateur étant lilLlitl~ au cas discret. on restreint l'échantillonage
de l'image à une profondeur ~~. c'est-à-llire on se limite aux blocs Bq avec
q /::; k soÎt
1
I( Bq) = 2k . Chaque site correspond il un bloc élémentaire. Comme par exemple la cellule
d'une grille de CCD.
On notera A.(k) =.4.0 u.4. 1 U ... U .-1. k .
Remarque
On particularise l'exposé a.u plan (dont dimension d = 2). mais cette étude reste valable
pour toute dimension dEN - {ü}.
IV.2.3 Images-blocs
A chaque bloc pyramidal Bq est associé sa fonction indicatrice bq = 1Bq appartenant â
2s . On considère alors les fonctiolls simples (E {-1. O.I} s) données par
avec q E A * . a E A , et ai donné par le tablea.u SUivûllt :
50

Chapûre IV
:\\ /tcl./y.;c Mu/Il-échelle el Transformalion de ffaar
a
a ü
CLI
a]
CL]
a
+1
+1
+1
+1
1
+1
+1
-1
-1
.)
+1
-1
+1
-1
3
+1
-1
-1
+1
figure iV.5: Tableau de détermin'ltioll des (rt,ll=I,2,3,4
Par définition. on pose ° = Ô = 0, = ls Ollél
Définition l'éC'ul'si've
:1
0'lu. = LU/J'Il
i=il
La tra.nsformation rùip'('()({tl.e t:.,t Jon:nù pal' :
:.1
()qa = ~ CLi9rfl
~
i=O
IV.3 FONCTIONS DE HAAR
Les fonctions de Haar que nous introduisons ici ne correspondent pas aux méthodes
analytiques des ondelettes régulières [ERO 87]. [:\\IAL 89], [DAU IN], [MAL Si]. La
deuxième différence que l'on introduit est de Illcrtn_' l'n oeu':re directement le concept
pyramidal. ce qui entraine une économie de calcul de la transformation de Haar.
IV.3.1 Définitions
Le système de Haar est l'ensemble H des fDI1erions appartenëtnt à {-1, O. 1} S
51

ChapItre [V
Il/HL/Y"," Mu/tl-échelle et Transformation de Haar
Le système de Haar à profonde1L'r k est l'ensemble HI.: = {Og E HI 1q 1$ k}.
Remarque
Le Système de Haar s ïmerprète dir<.'C(l'llll'It[ UJlllllll' des images sur 5. Cependant sur
5 discret de la forme :zn X :zn. seuls les SYStèllll'~ HI.: <ln'(' k $ Il sont interprétables.
Exemple:
H'!.
{o.ol.o'!. ..... o:Jd
, card(Hd = 4", Jonc
, Ainsi card( HI.:) = dim( RS ). cc qui est iwlispl'llsabll' il la rt'?\\'crsibilité de la transformation
de Haar sur image discrète.
IV.3.2 Indexation canonique de Hk
La remarque ci-dessus montre que H k est ('Il bijection avec A k, donc avec 5
[:2k] x [2 k]. Pour ce faire, on associe bijectivemellt tout Oq élément de Hk au site de q-
code q = wOlk-[w[).
Dans le cas continu S = [0.1]
S
x :0.1] un pose pour ,c, y E X = R
< .r,y >= J~.r(s)Yls)ds ( où d8 est la mesure Lebesgue)
en supposant x et y continus, ou bien .r.!J éléments de L 2(5). Dans le cas discret
5 = [2"] X [2"]. On pourrait plonger 5 dans [0,1]2. mais pour définir le produit scalaire on
préfèrera ici respecter les habituJes algorithmiques Cll prenant la mesure de dénombrement
et poser
« .1) > = L .r, 1),
Dans le cas discret on plonge 51.; = [2"] ;<. [21.:] daus le réseau Z2 muni de la mesure de
dénombrement 1/.
32

Chapitre IV
/Inaly.se Mull'L-échelle et Transformation de Haar
On peut alors écrire:
< .r.y >= j',r(c)) .1)(:,;) I/(cl,j)
.S
En particulier on remarque que:
j '., .k-Iql . k j .cl
oq L V = 4,
= 4,
() If' /\\
Sk
5
avec 5 = [0.1]< [0.1] et /\\ la rncsul'l' de lcl)L'~gul',
Pour des rai~ons de sim plificêI [iuu des t"ni [ures. ou s·;\\ u rol'i~lTa cl rem placer 5 k par 5
lorsque le COll texte le permettra.
Théorème IV.l :
Dans le cas discret 5 = [2 k ]x[2 k ], H k est une base orthogonale de X - RS . De plus.
pour tout Oq élément de HI.: on Cl
si Iql = 0
si Iql ~ 1
On utilise deux lemmes pour démontrer œ théorème'.
Lemme IV.l.l
'rj Oq
:;: HI.: tel que Iql on a r ol/dv = O.
• If
Démonstration
Elle repose sur la définition de la. base cle Haar:
si q = LW Oq = L~ a;bui avec Lai = 0 ec l b
=
Ul
4,k-Iql alors l 0 q dl/ = 0
J' '\\"'..'
'\\" J' . i
k-Iqi ",3 .
0 i' '1
.
l
car
~ lI,OUI = L
bULL 1/ = -1:
2.....nll, =
l ou e reSLl tac.

Chapttre {V
/\\ 'wlY,H~ M'u,lt~-échelle et Tran.:;formation de Haar
Lemme IV.1.2
Soient Bu et B v cieux blocs cie q-cocles u et u respectivement avec lui < Ivl. alors:
si ::Jw (J == U U'
smon
Démonstration
Remarque :Les blocs calTés d'uIl méIlle llin.'éHI de 1'<11'/)1'C' quaternaire complet forment une
parti tion cie la région décomposée.
i) si ::lw l' == U tU alors u r u donc Bue Bu L'f llOllS pouvons donc conclure que
Bu U Bl' == B t •.
ii) si 'iw. u 1= llW a.lors il existe U', ct (('2 tels L1Ul: (' == (LI, W'2 avec lU! 1= u et /w21 == lui
donc B" U BI' == 0: or B
ç
WI
B w, W2 == BI' d'où B" U BI' == 0.
Démonstration du théorème IV.1
Soient cD q et (J)r éléments de Hk avec q 1= r
1er cas: Iql == Irl et Iql 2 1
soit q == ua et r == vb avec lu == lui 2 0
1
- si Il 1= li l1> q 6 r l :S 5ubv == III == 0 d'après le lemme III.l.2 donc <Pq<Pr == 0
- si IL == v donc a 1= b on vérifie que d>uaOuu == Oue (a, b, c) est une permutation de
(1.2.3) comme JcDuedv == 0 on a bien < 0a ", 0 ub >== 0
2eme ca.:> : Iql =F Iri supposons que Iql :S Irl
- si Iql == O. on a. QqOr == bO r avec l ordv == 0 alors < Og: 0 r >== 0
- si Iql > 0 on pose q == (w l' == ub avec lui < lui
si tl n'est pa.s préfixe de l' :
OqOr == OuaoutL.b8ull' car le support de OUll'U L'st BaU' COlllIne Iwl > lOua est constante
sur Bull" cette constante notée CI valant +1 ou -l; alors:
<
j
J'
Og: Or >== Ct
OUll'U == Cl
(])uwb == 0
13 IJ..J)
. ce qui termine la démonstration du fa.it que HI.- est un système orthogonal
54

Cftaptlre 1V
:Inuly.>c Mult'L-ùhdle el Transformaüon de Haar
, et par suite libre, de X = RS . On a vu ci-dessus que:
cionc Hk est une base de l'espace vectoriel X = RS' . 011 \\'üit de plus que:
SlLpp( d:>q) désigne le support de Oq
.. si Iql = aalors 0,( = 0 = 6' et 1I0li 2 = card(S) =-il.:
.. si iql 2: 1 alors q = IW ,1\\"ec IILI 2: ü o<~ = Ou et Ilo((W~
card( Bu)
4"
~ donc
iloqll = 2k-1ul = 21.:+1-lql.
IV.4 ANALYSE PYRAMIDALE DE HAAR
Le but de cette partie est de concevoir U11 algorithme pyramidal de la décomposition de
Fourier des images échantillonnées par rapport à la base de Haar définie précédemment .
.-l = {a, 1.2,3} avec .-l+ = .-l- {D} = {1.2.:3}.S = [21.:] x [21.:],k étant un entier fixe.
Tout élément S de 5 peut être représeuté par sou 4. - code q(.-;) E .-lk et les bq(s)(s E 5)
donnent la base initiale (canonique) de l'espace X = RS des images de dimension 4k . Afin
d'établir les formules de passage aux coefficients de Fourier, on identifiera 5 à .-l k = J et
on notera toute l'image .r par:
.r =
2:= I q5q
qE.-\\'
6q étant la fonction indicatrice du bloc Bq. ici réduit il Ull site.
On pose J = .-lu U {.-lu U .-ll u ... U .-ll.-I }.-L.. : 011 ;1 vu que tara(J) = -il.: et qu'il existe
une bijection canonique entre J et .-ll.: par ';l/.pprr:.î.îi.un / adjonction des lettres 0 en fin de
mot: Cf E .-lI.: --- ü E J avec q = üü(I.:-IÛ'i)
00

Chapztre 1 V
1\\ /La/y"," M,L/IL- oichelle d
Tr'ansformalzon de Haar
le système de Haar H =
k
{<Pa/o. E J} est une famille d'images définies par:
Or = 6, = 1(,·
0 1L1a =
L ((l.b )Owb, et E .-\\.+
bE.V
ou (l.b désigne le produit «(scalaire »Sl.Ü\\Oallt :
< IL. b >
0
1
.)
3
0
+1
+1
+1
+1
1
+1
+1
-1
-1
2
-1
-1
+1
-1
3
+1
-1
-1
+1
figure iV.6
Table du produit sC<Jlaire
la structure euclidienne sur X est :
< .r. y > = / .f, y, U \\ cL) = L .f '1 Yq
'/E.·\\k
IV.4.1 Base Orthogonale de Haar
La normalisatioll de la base onhogollalc Hk dOllIlL' la ba;;c :
.
('rk+i LU 1) ' (
b)-
= -
1\\ {('Ol
L
Il.
Ù'l'b
bE .\\
5C

Clwpllre 1V
;\\IL,dlj"t: MuftL-échelLe et Transformation de Haar
en particulier si qi =
1
1.: - 1
Pour toute image J: E X on introduit les coefficients de Fourier: -:'0 = Îo(x) =< X, ""0 >
pour tout CI: E J d'où la représentation
Le problème est d'obtenir Ull aigorir.llllle de calcul des Î ù (.1'), ce calcul étant la base de ce
que nous appellerons A. nQ,(If.>e. de. H 0.0."": de !l11::'III L' !lOIIS ('ruc1icrons un algori thme pyramidal
de reconstitution de ./.' à panir de ses codficil'll[:i Îc, \\Symltè.·se de Haar). En remarquant
que .r E X est donné par une matrice .c = (.c q )'/é.-\\I.: l't que l'analyse de Haar donne une
matrice 1 = ho )oEl où J est en bijection callollique avec .-l.", donc avec S = [2 k ] X [2"],
il en découle deux applications:
A.nalyse de Haar = Transformation directe: .l' = (l'.1)"ES -- 1 = (r")"ES
Synthèse de Haar = Transformation inverse: : = h.> )1ES' -- X = (x" )"ES
On montrera que les transformations directes et inverses peuvent effectivement être
calculés en utilisant une seule structure de dOll!lés qui est un tableau 2" x 2k et quatre
variables auxilliaires, ce calcul étant de complicité inférieure à l'algorithme de Transformée
de Fourier Rapide (discret),
Proposition IV.I :
La transformation direcre de Hi:lélr
.r- R·J est calculable au moyen d'une variable
<:lllxiliairc fJq U{Jt~t: 1fl iS Lddillic pnr :
.r,/
:il lql = k
Pq = { lIL Pqb 51 Iql < k
et par les formules:
1 '\\"'"'
l '
..J.. 0
:) L ((L.u JP1L'b pour a T
5i'

Chap-itre IV
1\\lLl!ly.,e M·Il.ni-échelle et Transformalton de Haar
Remarque: on peut écrire {lq = t 2'J 0.& )Pq& ' ct voir ainsi que les quantités auxiliaires
correspondent à la formule: Pq = Îwu mais ce n'est pas un coefficient de Fourier (sauf pour
1q 1= 0).
Démonstration
a) un calcul direct donne: (JE =< .c, l'" = 2-" LlrJl=".L'q
or on peut vérifier que
1
1
PE = 2' LPb =
1
22 LP&I&"2 = ...
donc ÎE = Pt = 2".1' où x est la lIloycnllC: dcs niveaux d'intensité gris de l'image x.
b) Si 0: E J - {f.}, on peut écrirc Cl = ((1(1. avec E {l, 2n:3}, par calcul direct on a :
Îwa =< .r, !{,'l'(1 > = '_)-"-t-I"'I L IL.b(
~
~
IJE.-\\
lœbu 1="
,
.
l '\\'"
on peut ecnre pwb = ï L... fJlL'bUl
d'où /wa = t Lb a.bpwb
IV.4.2 Aigorihme d'analyse de Haar
On utilise une seule matrice m E Jln . (R) avec
Il
ft
= 2" . En entrée de l'algorithme,
m contient l'image originale .r: en sortie, m contient 1 = (,0) qui est la famille des
coefficients de Fourier. Le calcul d'adresse (accès aux cases de m(.,.) ) se fait simplement
par l'intermédiaire du calcul des q - codes des sites.
.
5
(")
[,)k1
slte s E
--+ z, ]
E _ l X [')k]
-
--+ q-code q élément de .-:l.k
index 0: E.J
--+q-code o:O(k-lol)
La proposition IV.l s'interprète alors directement, COLnnH:' \\lU calcul pyramidal ascendant
des quantités
~'Il'O = Pli" ÎU'I' ~'w2, Î1L'~ pour 1 iL'
dl'croissant de k - 1 à 0
1
On remarque de plus que, si 1 Wl 1=1 LU 1 -1
le calcul de bw'i; i = 0.1.2,3) ne
fait intervenir que les Pw = r wO sans modifier les quamités Î'wl ,/w2, /w3 déjà calculées et
stockées dans la rnatrice m. Comme ,'c ca!cuille' pone que sur /l",'o, pw'l, Pw'2, Pw'3, on en
déduit qu'il suffit de 4 variables L'a, Ul, 1'2. l'J
58

Chapilre ! V
1\\/Lldy.,e ,'v/uill-ùhelle el Transformalion de Haar
en plus pour actualiser le tableau m à chaque itération de l'algorithme. Cet algorithme est
donc typiquement pyramidal.
algorithme ANALYSE
'ï/ q E .-l1.' faire m'l -
.l"i
Pour 1 \\- (1. - 1) il Upas (-1) faire
pour tout q-code q de luruju.tïLF 1 faire
pour a ~ U, 1 , ~,:J faire l'" -
"'qa
pour a \\- 0,1,2,3
faire fft qa -
tLba.b'Ub
fin pour tout
fin Pour
Fin algorithme
figure i v. 7 : Algorithme d'analyse de Haar
Compte tenu de l'indépendance des structures des -± blocs associés à qO, ql, q2, q3; il
n'est pas nécessaire dans l'algorithme ci-dessus de procéder à un décodage complet des
q - codes: un simple calcul de décalage d'adresse suffit.
IV.S SYNTHÈSE PYRAMIDALE DE HAAR
:-\\vant d'examiner les implications ct les applications de la décomposition de Haar, nous
allons étudier la synthèse de Haar, c'est il, dire la traIlsformation réciproque:
ho)J -
(.r, )s. avec 5 = [21.'] x [:21.']
On sait que cette synthèse est donnée par le llén.'loppcmcnt de Fourier: x = I: J loK. o
Nous allons examiner plus précisément le calcul pyramidal associé a cette synthèse,
calcul qui présente de grandes similitudes ayec l·analyse.
Proposition V.2
La [ransforrnarion réciproque de Haar: 1 E RJ -, .r E RS es[ calculable au moyen des
\\'ariables auxiliaires Pq( avec 1q 1::; ~:) définies i:11a proposirion n',1 par les formules:
Pq = Îq si 1q 1= 0
'ï/a E .-\\. Pwa = t L( a" b)Î Il'b (Î ",0 = jl", par convention)
{ I q = Pq si 1q 1= ~,
59

C'fLapl.lre / V
. \\ Il,1(1).'': MIl.il'·,'chelle cl Trcm-,/oTmal201l de Haar
Démonstration
Remarquons dans cet énoncé que (Jq = 1(( si Iql = 0, et que la convention IWO = Pw ne
signifie pas que pU' soit un coefficient de Fourier.
La démonstration découle du théorèmc 11.1 en remarquant simplement que la matrice
.:1: x 4 donnée pHr :
1
_
1 r 1 1 1
1
1
-1
-1
)Ol"l (u E A../)E A)
T(l,b = -:da.bJ -}
~ -1
1
1
-1
-1
1
est sa propre inverse :2)a.c)(c.b) = 4 si I.L = b l't a si CL f. b. et n'est pas décomposable
en proc1ltit R - 5
La différence entre l'analyse (proposition IV.1) et la synthèse (proposition IV.2) provient
uniquement de la récurrence sur Iql : ascendente dans l'analyse, mais descendente dans la
synthèse.
IV.S.I Algorithme de transformation réciproque de Haar
les formules de récurrence de la proposition i\\'.2 montrent que cet algorithme est très
voisin de l'algorithme de transformation directe. 5"lIlf qll'il faut utiliser una recrrence
descendente au lieu d'une récurrence ascendcl1tc COlllIne le cas précédent.
Ici encore, on utilise une seule matrice rn de dimension 2k x 2k .
en entrée: m contient Î = (r~) J c'cst-à-uin:, les cewfficients de Fourier,
en sortie: III contient l'imager recon5titu~'l', le calcul :-iC fait séquentiel1ement sur m,
sans Il r,iliscr de :-it ruct ure de données auxiliaires ~ l'exccp tion des .:1: scalaires Vo, VI , V2, V3 et
on aura l'algorithme sui\\'ant :
60

Chap7.lre 1V
.\\ 1Ll/.L'J.,," M-u.Ll1-(:chelle el Transformation de Haar
algorithme SYNTHESE
'ï/ q E A.I.: faire m q .- ICI
Pour l.- 0 à (k-l) faire
pour tout q-code q de longueur 1 faire
pour u. .- U. 1,2,:J f~jre ('r{ ~ 11/(1"
pour u. ~ U.1.2,:1 f;)ire rll,/" ~ ~ Lb U.. bVl'b
fin pour tout
fin Pour
Fin algorithme
figure iV.7
Algorithme de synthèse de Haar
IV.6 COMPLEXITÉ ALGORITHMIQUE DES TRANSFORMÉES DE HAAR
Proposition IV.3 : Une TP:2 - D SIII' Rn X R" ilVCC Il =:21.: est de complexité O(n 2 ).
Preuve:
Le calcul d'un T nécessite 16 multiplications et 1:2 additions et est repété :2 + ~: +
... +
2
1 = n -1 fois, soit 28 (n 2 - 1) opérations flottantes.
3
3
La réputation du caractère t1LstiqlLe de la transformée de Haar reste à démontrer aux
niveaux des applications pratiques. :\\Iais ce caractère doit être mis en comparaison avec
des transformations plus nobles en cc qui conceme la complexité algorithmique, pour cela
nous allons les règles de complexité des transformations unitaires Tn des signaux discrets
échantillonnés sur n points: .c = (Xl, .1''2,.'' .L',,).
Les transformations globales qui nous intéressent sont des applications
Tn : Rn --> Rn ou (C n ---. Cn , vérifiant Tnt = T;:l
(T~ = T 1 dans le cas complexe).
n-
Cn algorithme direct montre ({ue Î = T"x est calculé en n 2 multiplications et n(n - 1)
addi tions, soit Ulle complexité \\'oisillc dc 21/ 2 floLJ"; dalls le cas réel (Sn 2 flops dans le cas
complexe).
Dans le cas des signaux 1-D. pour ln plupart des transfonnations unitaires couramment
urilisl's, on connaît les algorithmes dirs rapidL's Id" TFR par exemple). réduisent le calcul
dc ~. = T".!' L'Il lOg2(1I) étapes utili";<lllt ~ u'.\\Il::,forllwtions unitaires d'ordre 2, soit une
complexité \\'oisine de :
61

ChapItre 1 V
IllL<L[Y.s~ M'I./.[h-éch~[[e et Transformation de Haar
:'lais la transformation de Haar, et les transformations du même type qui permettent
l'usage d'un algorithme pyramidal utilisent toujours log2( n) étapes, d'où par exemple pour
n = 102..1:. un calcul 4 fois plus rapide CplC la transformation rapide de Fourier, et 256 fois
plus rapide que par calcul direct.
Remarque
Cne l,tude plus précise 11l0lltreraïr. qu '\\l11l' tl"êlnSf0l111ar.ion de Haar ne nécessite que 3'11
fiops, tandis qu'une transformation de Fomicr rapide (C11 11,Olnbres complexes) nécssite près
de 16nloY2(n) flops, et près de 4nlog'2(n) fiops pour Ulle trallsformation en cosinus.
D
1
l
,
')
D
" ,
.
R N : \\ T
'}
ans e cas ces slgna.ux :.. -
, 011 S lnteresse aux nuages J; E
avec 1 v = '11 - et
n = 2k , Cne transformation (unitaire) par calcul discret nécessite à priori 2N = 2'11 2
fiops. Cependant. si cette transformation est à noyau séparable, le calcul peut se faire à
raide de n + n transformations d'ordre H, soit environ 4n J flops, Toujours dans le cas
à noyau séparable, mais en supposant de plus l'existcnce d'un algorithme rapide pour les
transformations d'ordre n, on obtient UIle complexité voisine de: Sn2 10g (n) = 4Nlog
1
2 (N)
flops,
Enfin, en supposant la possibilité d\\lll algorithme pyramidaL cette complexité devient:
v
N
J? .

(4" + ï6 +.,. + 4 + 1) x 32 = )- N fiops (::: 10.\\ fiops).
Exemple Comparaison pour des images 256 x 256 (sans tenir compte des optimisations
complémentaires)
- Transformation Fourier Rapide (C : G3 \\lfiops
.. Transformation directe en cosinus (R) : Ci \\lfiops .
.. TransformatioIl rapide en wsinus : 4,2 \\Ifiops
- Transformation pyramidale de Haar: 0.35 ~lfiops.
\\'ous obsen'ons donc que la transformations ue Haar est 12 fois plus rapide que la
transformation rapide en cosinus et lS0 fois plus rapide que la transformation de Fourier
Rapide.
IV.7 INTERPRETATION STATISTIQUE DES CDEFICIENTS DE FOURIER-HAAR
\\'ous allons examiner plus précis6rllCllt le lien entre la transformation de Haar et la
décorrelation du signal image .r. Il s';"lgit d'une ilHcl'prcration dc type L l , c"est-à-dire en
termes de moyenlle et de covariance de l'image .1'. :\\'ous axons les résultats suivants:
62

Chap1.lre IV
JllLtl.l-Ij,'f: /vfulil-ùhelle et Transforma/ton de If aar
Proposition VILI
Si -( = ha)) est la rransforrnée de Haar de l'image r = (rj)s alors:
E(x) = la moyenne de .r est '2-k,~
. V(x) = et la variance de ,r est 4- k Llol:;::o ,~
Preuve
2
On utilise la relation de Bessel-Parscval :11.1'11
= LI l't
(lui done :)' .r~ = ",2 + '\\'
_'2
........<
I (
L-o:;éO 10
av"'c _. - o)-k < ... ,; >- .)-k ' \\ ' . - O)kE( v)
(.'-
1 ( - -
,<-,u(
- -
Ls'L.,--
"
donc l'(:r) = -1: -k 2.: ,1'~ - E2(.r) = -1: -J..; LI Î~ - -1: -k Î /
IV.a L'ANALYSE MULTI-ÉCHELLE D'IMAGES
Par analyse de Haar d 'une image '2 - D 1:, nous obtenons une matrice de coefficients
hdiEJ, la moyenne de l'image x est donnée par la formule E(x) = '2- k 'E et la variance par
V(x) = 4- k Lla:;éO ,.; L'homogénéité d'un bloc pouvant être caractérisé par la variance de
ce dernier, et les propriétés d'une image étant applicables à toute partie de cette image,
nous allons montrer comment utiliser la transformée de Haar pour filtrer, compresser et
segmenter l'image.
IV.a.1 Transformation de l'image par annulation de faibles coefficients de Fourier
Après le calcul des coefficients de Fourier-Haar ils som classés par ordre croissant et on
élimine les plus petits coefficieIlts au fur ct ft mesure
63

Chapitre f V
1\\ "tL/y",; i\\4n/l1.-échelle et Tra.nsformahon de fi aar
Jusqu'à ce que le taux de compressioll at [cigne un pourccIHage choisi.
Soit T :::: LJ lol\\.(} la représentation de .r clau:'> le système normalisé de Haar (K:o)oEJ.
Si on annule certains coefficients (roo )00 E Jo C) où
Jo :::: {Ct E .1/ 1~IQ 1< s}, ct .1' devient 1~' :::: ~ ~(OrKo
~
}\\lo
La valeur Î:::: ['(.r')/l'(.1:') l'sr appelé le tau],' de cu/f/,jJn;""iun en terme d'énergie,
IV,B.l.l Algorithme de compreSSlO1l p;Jr Allllubtioll de faibles coefficients
algorithme COMPRESSION
Tri JJU:/, ûTdre c/'ûi.:;.wnt de (Îo JoE)
/* cu.lC'nl de 1/(.1:)*/
1'(.1') i- 0:
pou r Ct: i- 1 à 1 .1 1 fa ire F (.1' ) i- l' (.r) + Î';;
V I i - V (.1'); V'2 i - l' (.1' )
ind f-uraie
Tant que ind =uraie faire
Si .!::.l. > T alors faire
t'2
')
VI ~ VI + i;
10 i- 0; Ct: i- Q + 1 ,. ind i- vraze
Sinon
Î
::::
.!::.l. " ind
i -
fu.'l/.x
1.''2
fin Si
fin Tant que
fin algorithme
figure i v. 9
: Algorithme de compressIOn
Si au départ nous fixons le taux de l'oIllpn'ssioll -:-. L'C[ algorithme nous donne une
matrice de coefficients privée des plus pe[its codficiems, cC' qui nous donne la possibilité
de représenter l'image en utilisant moins d'espace IllL'moire.
64

Chaptlre IV
fi 1LU./y.>e Mu/il-échelle el Transformailon de Haar
IV.B.l.2 Implémentation de l'algorithme.
Soit l = L Îc>"~o la représentation de l'image après Lmalyse( calcul des coefficients de
Fourier). :-ious ne considérolls que les coefficiellts 11011 lluls, ce qui nous amène à consti tuer
une structure comme l'indique la figure iv.1D. où n est le nombre de coefficients non nuls
et ar/d(i) est l'adresse réelle de ,(i) sur la matrice Jes coefficients. La transformation de
l'image l'ollsistcra en un balayage du tableau par onln.' croissant et l'annulation des ,(i)
tant que u( J..I) / u(:r) n 'est pas proche ou égal él u pourcentage de compression recherché
enterme d'énergie; donc à la sortie de cet algorithme on aura un tableau de dimension
m ~ n.
.-l.drcs,j(
Va!eur du coefjïcit.nt
culrlr( 1)
'/ (1 )
addr( i)
Î'( i )
addr( Tt)
Î'( n)
figure iv. 10 : Table de stockage du rsultat d'une compression
IV.B.l.3 Compression de l'image en terme de bits
Pour des besoins de régularité dans la décomposition. nous avons au départ choisi de
faire notre traitement sur un espace 2/.: x 2/.: h élément Je N. pour être satisfait en terme de
compression nous avons besoin d'obtenir Ulle UllL' représentation de l'image qui occupe un
espace inférieur à 4/.: ;pour l'obtenir il faut que d 'apr&s la représentation choisie, un assez
grand nombre de coefficients de Haar soient égal il zéro. nous avons en IV.8.1.1 proposé un
algorithme qui compresse le nombre de coefficients après l'cmalyse de Haar, mais cela ne
nous assure pas la compression en terme de bits. car pour certaines images il est impossible
de compresser le nombre de coefficient sans perdre lUI llombre important d'informations.
Les calculs suinmts nous
65

ChtlpÜre IV
/Irwly.,c M·u.ILL·échelle et Transformation de Haar
donnent le taux de compression en fonction de la profondeur de l'arbre quaternaire complet
de l'image et le nombre d 'enregistrellleIlts après l'analyse de Haar:
Soit .\\"Bü le nombre de bits occupé pal' l'image au départ. NEF le nombre de bits
occuper par la représentation de l'image par les coefficicnts de Haar, et n le nombre de
coefficients différents de 0 après l'analysl' de Haar.
.V BO = 41.: x S bits .
.vBF = n( 16 -+- 32) bits = 4Sn bits.
or le taux de compression en terme dc bits l'st T = .vB F /.V BD
donc le ta.ux dt compre88ion en tenne de ua., = 6114 -1.::
IV.8.2 Filtrage d'image
La transformation de Haar est un prototype de transformation discrète par on-
delettes( dans le cas discret). et par suite se prête bien aux possibilités d'analyse multi-
résolution. En particulier. il est relativement facile d'établir différents filtres (passe-haut.
passe-bas ou passe-bande), sur les différentes frt'quenccs spatiales, Le principe général de
filtrage est le sui \\'ant :
Image
) T~p (Coefficient) -S
TIIR
Image)
( Originale x
de Ha.ar /
-- ( filtreé x'
figure i v. 11 : Schém~ géllér~1 du filtrage
TH D : TraI1,Jol"rnù de Haa:,. di.,.edt.
TH R : Tra.n4ormét': dt': Ha.ar InueT.';e,
F : Filtre
Pour conce\\'oir de tels filtrages. il suffit de remarquer que les coefficients de Fourier-
Haar (0 (0: E J) autres que "/0 sont de la forme /wa =< .L,w.r\\./J./(' > (a = 1,2.3). et par
suite détecte des \\'ariations du signal .r sur le l)loc B w .
IL'l
= gradient bas / haut de .r'"
w2 = gradient clroi te / gauche de .r rL'
GG

Chapitre fV
Il/W/Y.,,, M/J./lt-,ichcl/e et Tran.>formaiton de Haar
W
/w3
= distorsion de .C
par rapport il. la diagonale.
')
')
2
"
J

l
ur
/~, 1 + l'~'2 + l'11'3 est un lll(llCatcur (Le \\'anallCC ( e .C
Les filtres linéaires que l'on peut concevoir :>ont donc de la forme:
CI' E J -+ COl E R
a.vec lOt -+ l'Il = CrxÎOt ( ces filtres saut réversibles si et sculement si les COt sont non nuls)
De plus on peut concevoir des filtres nOll-linéaires par différentes a.pproches heuristiques,
comme par exemple : I~ = a si I,Ot 1est inférieur à Ull seuil donné.
Exemple: Pour illustrer ce propos, examinons l'image suiva.nte :
3
1
- _ , 0
03 ;,).)111 D'l'III) c~~ 0 .) ~
0
-1.0
-<0)
00.0
--+
04.':'
0
- , J , ;j
03.0
00,0
0
-l.0
-2.0
Pour filtrer complètement un gradient Haut-bas. on peut annuler brutalement les
coefficients Il,101, 111,,21, 131 (q-code terminé par 1). On obtient alors:
15.5
a 00,0
a
3,6
3,9
3,' 6
4,9)
00,0
a
4,9
-1.0
00)
00
~ (~:~~ a -1.0
3.6
3,6
3,9
( 04,5
a -5.5 00
8,25
a 3.25
( 4.1
4,1
0,1
6, 1
00.0
a -La _.)
0.00
o -1.0
4.1
4,1
2.1
0,6
figure iV.12
Exemple de filtrOJge

Chapt/Te 1V
il lLaly~ e Mu./h·.:ch elle el Tran.J/ormation de Hcar
Figure llJ.13
Inuge origill:lle (Muscle)
GS

Cnap1lre IV
Il HU/Y'>';: ,''11 ull't· échelle d
Transforma.tlon de Haa.
Figure 1'1.14
Image Filtré par seuill::lge des coefficients
ANALYSE :Moyenne :1JJ,14; Vu:rw1Lce :J~IO.7.r.-Eca.rt·t'Ype :56.66
FILTRAGE :Seuil=12
SYNTHESE :Moyenne :133.14; VO:f"ia'l~ce :J191.86;Eca-rt.type :56.50
69

Chaptl re 1V
1\\ "a/y.; e M'ullt- deite/le el Tran5foTTTlaiton de Haar
Figure iV.1S
Image originale (Angiographie)

Cha.pilre f V
IIILili!!.'!.: M'ulll-échei/e el TraTI.!J[ormalton de Haar
Figure iv. 16 : Image synthétisée après compression
ANALYSE :l'l1oyenne :58.89: Variance :1140.2J:Ecart-tvpe :33.77
FILTRAGE: Tav,x de comprt.BtOn :1 û%
SYNTHESE :Mùyenne :58.89; Variance :1124.87;Eca.,.t.type :;]3.. 53
i"l

CIIAPITHE V
ALGO RITHrvIE PYRArvIIDAL
DE
,-
SEGlVIENTATION D'INIAGES EN REGIONS

Chaptlre IV
/1 Ilil./y.,.: Mu/lt- .!.chelle el Transfo'rmaltOn de Haar
IV.8.3 Algorithme de détection des blocs C<lrres homogènes maxImaux
Pour ce qui est de l'algorithme descendant on COllunence par l'image toute entière qui
a pour q - code le mot vide et on décompose suivallt l'algorithme de la figure IIA jusqu'à
l'obtention des blocs cmrés homogc'lll'S l'r 111l1xinuulx.
L'algorithme descendant aura le SChl'Ill,lSui\\',1llt :
Algorithme DESCENDANT
DEBUT
i f- 0 /* i represente le nombre de blocs detectes */
Pour 1 -- (À: - 1) à 0 pas (-1) f<lire
début
pour tout q
de longueur
faire
si
F (B( q)) < CI' <llors début
i--i+1
bloc(i).vari f- V(B(q))
bloc( i ),adr f- q
fin
finpour
FIN
figure i v .17 Algorithme ascendant de détection de blocs carrés homogènes.
CONCLUSION
La transformation de Haar nous promet ue tr('s bonnes perspectives;nous \\'enons
d'étudier ses capacités en filtrage et en t:ompression. la TH fait ressortir deux aspects qui
ont un très grand intérêt l'Il segmentation cl 'images: la représentation par arbre quaternaire
et le critère d 'homogenéi té qui est donné par le::; trois coefficients de détails Î'w l, -fw2, -fw2
du bloc de q - code LU • .\\'ous allons partir de la transfonnation de Haar et proposer une
segmentation d'images.
-.)
1-

1
!
Chapüre V
Un I\\lgor'ithm~ F>yru/lndul de Seg'mentation d'Images en Régions
t1j
INTRODUCTION
Dans le premier chapitre nous avons passé en revue un certain nombre de méthodes
de segmentation d'images; dans cette partie du travail nous présentons un algorithme qui
est inspiré de la méthode du SPLIT and ivIERGE [PAV Ti] [HOR 76]pour segmenter une
image en régions. Cet algorithme a deux points forts:
Dans un premier temps nous procédons à la construction de l'arbre quaternaire de
l'image, qui consiste en la partition de l'image, ce 4ui nous permet d'obtenir une pré-
segmentation en blocs carrés homogènes.
En deuxième partie nous parcourons la structure linéaire de l'arbre quaternaire pour
obtenir les segments de l'image.
Cne image étant un élément de N N 2, c'est-à-dire 4ue si nous considérons que l'image
est représentée par JAl = (1'1 LEI J est llll sous ensemble de N 2 et Xi un élément
de N
pour tout i élément de J; cette nnage peut aussi ètre définie par son graphe
PAl = {(i,xj),i E I}.
~otre objectif est donc de trouver une partition de JAl en reglOns (Rk)kEli: de PlvI
où les Rk sont des régions homogènes maximales, et même aller plus loin en donnant
une structure des segments plus exploitables par des processus d'interpretation d'images,
l'originalité ici c'est d'utiliser la manipulation syntaxique dans la segmentation.
V.1 SEGMENTATION
Intuitivement nous voulons diviser une image en régions homogènes, homogénéité qui
est traduite par un certain nombre de conditions à remplir; avant de décrire la segmentation
nous allons d'abord définir un certain nombre de termes.
V.l.I Région
Une région R de l'image JAl est un sous-ensemble de
P ~VI = {( i, x d, i E I}
Pk = (i, lOi) i est le pixel et 'C la \\-;llcm Ju lliw~au de gris en ce site [GAG 85]
l
73

Chapitre V
Un li 19onthme Pymmtdal de Segmentation d'Images en Régions
V.l.2 Prédicat d'homogenéi1:é
Les algorithmes de segmentation utilisent le plus souvent un prédicat d'uniformité P
comme critère de partitionnement. On dira qu'une région est homogène relativement à un
prédicat d'uniformité P si P(R) = 1 ( ce qui signifie que la région est homogène suivant le
prédicat P). Un pédicat d'uniforrn'ité est une fonction sur les caractéristiques d'une région
R de l'image telle que P(Caractéristiques de R) = 1 si C(R) < s et P(Caractéristiques
de R) = a si C( R) > = s; où C est un critère de dispersion et s un seuil convenablement
choisi ..
Gn exemple de critère de partitionnement serait la variance.
n
1
'"'
')
C (R) =
l R
/.' (.r i - JI t
c(tJ'( (
)
~
1=1
1
:.....
JI =
'x.
car'd( R) L
~
1=1
R = {Pl' P2 , , Pi, , Pn} et Pi = (i, :r i )
P(Caractéristiques de R) sera desormais noté P( R).
V.l.3 Régions adjacentes
Soit (RdkE l,' une partition en régions connexes Ri ct R) sont adjacentes si 3Pi E Ri et
3pj E R} telles que dl (Pi. Pl) = 1
V.l.4 Définition: Segmentation [PAV 77][HOR 76]
Une segmentation d'une image PJf = (i,x;),i E l et liée à un prédicat d'homogenéité
P est une partition en régions (Rk )kEK de PAf vérifiant:
(i) P(Rk) = 1 pour tout 1.; E K
(ii) Rk connexe (*) pour tout k E I{
(iii) Vk E !\\' et Vi E !{ avec k ~ i P(Rk u Rd = a
(iv) Vk E K la frontière ÔRk est régulière.
(*)
connexité.' soit la relation a
définie s'ur 'une regwn R par Vp. q E R paq - -
dl (p. q) = 1. la région R sera connexe si Vp. q E R -il existe 'Un chemin entre p et q
(BOU 84/

74

Chapitre V
Un Illgonthm.: l'1j{"(LHLI.dal cie Segmentation d '[mages en Régions
V.2 ALGORITHME PYRAMIDAL
V.2.1 Description de la méthode utilisée
La méthode que nous utilisolls est illspirée de la fusiou des régions utilisant un prédicat
d'homogenéité P. Dans un premier temps nous faisous une segmentation en utilisant
un algorithme ascendant pour fusionner l'arbre quaternaire de l'image [PAV ïï],[MON
88], [HOR 16] de ce processus on obtiemlra un ensemble {X t ,X2 ,
,Xn } de blocs
carrés homogènes et une mise à jour de l'arbre quaternaire. mais qui n'est pas encore une
segmentation voulue de l'image. Dans cet te étape tous les pixels singuliers ne sont pas pris
en compte. cc qui pourrait correspondre .l uue élilUination grossière des contours.
L'étape sui\\'éHlte consistera à. fusionuer les blocs carr{'s Xl' Xi, .... , Xi pour lesquels
i j E {1,:2, .... , n} j = l, ..... , p et \\fXii 0 etXiii avec j 0 et j 1 E {l, .... , p}
il existe un chemin entre Xi' et Xi' dans le sous 2:ra.phe de noeuds XiI' '\\i , ••••• , .Yi .
J O ] l
~
2
fi
pour parfaire la segmentation une dernière étape uous permettra d'éliminer les petites
régions ( en général des régions de moins de 10 pixels).
V.2.2 Structure de l'arbre quaternaire
A tout père on associe quatre fils, le problème pour nous ici c'est de pouvoir représenter
la structure arborescente en mémoire séquentielle, étant donné que le arbre quaternaire
complet a une structure assez régulière nous allons pour la représenter, prendre une image
discretisée sur une grille 2k x :2 k
1
, les 4k pixels comme les feuilles, les 4 k -
cellules suivantes
comme les parents de ces feuilles, et au rang i les 4i -1 cellules comme les parents des 4i
cellules précédcntes, donc nons m'ous besoin pour illlp1nut('r l'arbre quaternaire d'une grille
de dimension 2k x 2k d'un tableau de 2:7:04'
Pour pouvoir retrouver l'adresse absolue d'un bloc. c'est à dire l'adresse du premier pixel
dans la représentation en mode linéaire, nous a.vons besoin d'une table de correspondance
dont l'algorithme de construction est le suivant.
15

Chap1tre V
UTt ALgorithme j'YllLTfLLaaL lLe Seymentation d'Images en Régions
V.2.2.1 Algorithme de construction du tableau de correspondance des adresses
des blocs dans l'arbre Quaternaire
charger(:r l, .r2, X3, .LI )
début
pour i <- 0 à .l'2 - 1 faire
pour j -
a à X2 - 1 faire
imaqpt((i+xJ) x 2n 1
1
-
+j +.1'4) -in~aqpt(i x 2n - +j)+XI
imqptl(imaqpt(i x 2(1-1 + j + ,ri) -
(i + ,r3) x 2n l
-
+ j + i 4
fin
figure v. 1 : procedure chargement des cellules de la table de correspondance.
Début
Imaqpt(O) -
0
pour i -
0 à n - 1 faire
dé but
b _ 2n
CLI _
b2
(12 -
0: CL] -
b; CL -
al; charger(a,b,a2.a.3)
a2 -
b; a3 -
0; CL -
al * 2; charger( a. b. a2, a3)
a2 -
b; a3 -
b; a -
al * 3; charger( a. b, a2, a3)
fin
Fin
figure V.2
algorithme de construction de la table de correspondance
Où imqptl est le tableau de t:orrespolldance et Il la profondeur de l'arbre. et imaqpt
une memOlre campon
ï6

Chapzlre V
Un i1l.qol"ithmt: Vy.,.amùial de Segmentation d'Images en Régions
0
0
.)
:2
4:
1
:2
3
3
1
.J
4
1
:2
4
S
a :Image représentée en mode linéaire
cellules
o21
de
mémoires
111=0
17 18
conti gues
figure v.3 : Représentation quaternaire linéaire interne
V.2.3 Fusion de l'arbre quaternaire de l'image
Les pixels de l'image à segmenter sont placés sur les feuilles d'un arbre quaternaire
complet comme l'indique la figure V.3: En l'ntrée nous avons un arbre quaternaire
(quadtree) dom les feuilles représentent les pixl'1s de l'image. en utilisant un algorithme
ascendant, on part des feuilles à la racine ct on fusionne quatre fils d'un même noeud de
l'arbre pour former un bloc quand c'est possible et quand ce n'est pas possible, on fait
de chaque fils un bloc et cette fusion continue- jusqu'à ce qu'il n'y ait plus de groupe de
quatre fils d'un même père qui forme un bloc homogène. On obtient alors X 1 ,X2 , ..... ,Xn
qui sont des blocs carrés et homogènes.
I l

Chapttre V
(j'IL I1lqorl.lhme PyrrL/ludal de Segmentation d'Images en Régions
V.2.3.1 Structure des données d'un bloc Carré.
l'enregistrement bloc comprend six rubriques
1- Adresse absolue du bloc
2- Niveau de gris minimum
3- Niveau de gris maximum
4- Moyenne de niveau de gris
5- ),fovenne des carrés de niveau de OTis
.
~
6- Niveau du bloc dans l'arbre quaternaire
V.2.4 Construction des segments
Ü n segment est un ensemble de blocs canes homogènes Xii' X i2 , .••• , Xi" tels que
P( UJ= 1 )-\\ i) = 1 et VX
il
1j 1
et X
existe un chemin entre eux. Constituer les segments
1j2
consisterait donc à construire un vecteur SEG = (SEGdi=I ....n SEGi = m si le
bloc carré d'indice i appartient au segment de numéro m et n le nombre de blocs carrés
homogènes.
Parallèlement à la construction du segment fil on construit le vecteur CONT R( k, *) qui
est le vecteur contenant les blocs carrés voisins du segment k (k = 1, ... , m) CONTR(k,O)
contient le nombre de blocs carrés voisins [PAV ÎÎ]. Le plus important dans notre
travail c'est que nous utilisons la structure linéaire de l'arbre quaternaire pour réaliser
nos implémentations ce qui nous fait un gain d'espace et une facilité de modelisation
quaternaire.
V.3 IMPLEMENTATION
Dans cette partie du travail nous allons présenter les algorithmes qui nous permettent
de réaliser une segmentation pyramidale il partir de la stucture. L'originalité se trouve
dans la manière particulière de représenter les noeuds de l'arbre quaternaire et la nouvelle
méthode d'exploitation des arbres quternaires (lui permet d'obtenir directement après une
segmentation, une structure d'information plus aisément exploitable.
Nous n'utilisons pas directement la méthode syntaxique pour explorer notre arbre, mais
une méthode purement algébrique pour faire la première segmentation afin d'obtenir les
blocs carrés homogènes et maximaux. ensuite la manipulation syntaxique nous nous permet
d'explorer l'arbre quaternaire de l'image, et de constituer les segments de l'image.
;8

Chapltre V
Un Illgorûhme fOynwL1.J.al cie :iegmentcLtion cl. 'Images en Réglons
V.3.1 Algorithmes de construction des blocs carrés
C'est l'ensemble des algorithmes qui pennetteIlt li 'obtenir une pré-segmentation en
blocs carrés homogènes et maximaux, nons èn"ons refenll dans notre travail trois approches
concurrentes :
- Une approche ascendante comme décrite en 1V.8.3
- une approche descendente qui s'inspire du paragraphe 11.2.2
- Une approche directe qui est donnée par l'algorithme suivant.
Début
Tai! -
0; j t- 0 :
pour i t- n à 1 au pas -1 faire
début
tail2 +- tail1 + 4'
pour k +- tail1 à tail2 au pas 4 faire
début
si
les
4
noeuds
L1.:+L/~+2_k+3
ne forment pas un bloc homogène
alors
début
pour 12 - 1.: à 1.: + 3 faire
si le noeud 12
es"t homogène
alors
début j .- j + 1 ;
créer
le bloc
X)
f
fin
t
fin
sinon
1
début
calculer les caractéristique du père de
k
}
(* k
a le même père que le + l, k + 2, k + 3 *)
~ pereCk)
est homogène il est marqué
sinon pour 1 +- 1.: à 1.- + 3 faire
1
début j +- j + 1 créer
le bloc
X) fin
t
fin
fin
!
fin
1
Fin
1
figure V. 4
Algorithme direct de construction des blocs carrés
1
1
ï9
f
1
f
~:

Chapllre V
Un ;llgonthme /'!Jf'/Il/wLa.L de Segmenlallon d'Images en Régwns
pour calculer père( k) nous utilisons aussi une méthode algébrique.
V.3.2 Algorithme de calcul du père d'un noeud k
pour calculer le père de k il faut cOllnaÎtrc ln profondeur de l'arbre et le niveau auquel
on se trouve dans l'arbre.
Début
Si niveau = 0 alors le noeud n'a pas de, père
sinon début
pour JI"- niveau â profondeur f<lire
II ..- /1 + 4)1 finf<lire
/.2 -
il -
4/1il'eclU ; /'.[ ~ 1.' - i'2: 1'2 ..- 13/ 4 : /2 ..- II +i3 :
fin
pere( I.~) ..-i 1
Fin
figure v.S
Algorithme de recherche du père.
Après l'obtention des blocs carrés hornogèllL's ct maximaux [PAV ïï] propose la
construction d'un graphe d'adjacence. dans notre illlplémelltation nous avons expérimenté
cette méthode en utilisant une matrice triangulaire supérieure pour le faire.
so

j
!l
Chapitre V
1
UrL IllqoTtthme VynumJ.al de 3egmentation d '[mages en Régions
j
l
,
V.3.4 Construction de la matrice d'adjacence
La matrice d'adjacence est une matrice triangulaire supérieure qui permet de repertorier
l'ensemble des couples de blocs (Xi. X j ) qui sont adjacents.
Soi t (adi . . ). .
b
d
bl
'JI)
I . ] = l ...... ,nom
re
e
ocs
8i Xi et X
.wnt a.dja.cent.~
J
.~znon
CT n algorithme naif consisterait à lmlayer WllS les blocs carrés pour remplir la matrice
d'adjacence et après quoi nous construisons les ::-icgrncnts qui seront les agrégats de blocs
ce qui veut dire la construction du vecteur
v = (l'i)i=I .... fl
n est le nombre de blocs carrés maximaux ct homogènes. et si Vi = m le bloc carré i
d'adresse i appartient à la région d'indice m.
V.3.5 Présentation du résultat théorique
Soit à segmenter l'image de la figure V.3.1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
U
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
a : Image origin<lle
après la fusion de l'arbre quaternaire de l'image nous obtenons ï blocs carrés maximaux
et homogènes.
31
t1

Chapllre V
V,L II/gonlhm" Pyra'lluda/ de Seqmenlalion d'Images en Régions
5
6
/
1
2
3
4
b : segmentation en bloc carrés homogènes
figure v. 6 : Segmentation pyramidale
Ensuite après la fusion des blocs carrés adjacents formant ensemble une reglOn ho-
mogène le ,'ecteur u aura les valeurs sui vantes : v( 1) == 1; v( 2) == 2; v( 3) == 2; v( 4) ==
2: v(5) == 1:v(6) == 2:v(7) == 2:
V.4 Problèmatique du calcul de l'adjacence de deux blocs
En s'en tenant à la représentation des blocs telle que décrite en V.2.3.1 il serait
théoriquement facile de calculer l'adjacence de deux blocs Xi et X j soit adri et ti
respectivement l'adresse et le côté du bloc ."C soit adrj et tj respectivement l'adresse
et le côté du bloc Xl et 2n x 211 la taille de l'image Ci == adri/2 n et li le reste de la division
de adri par 2n • di == Ci + ti et ki == li + ti, Xi et Xj seront adjacents si et seulement si
IIi - kjl <= ti + tj et ICi - djj <= ti + tj
La complexité algorithmique en temps est de l'ordre de O(k 2 ), k étant le nombre de
blocs carrés homogènes, ce qui est encore acceptable pour des images dont la segmentation
initiale a un nombre réduit de blocs de l'ordre de 20: mais quand le nombre devient
important l'implémentation des algorithmes post segmentation initiale devient caduque.
Dans [SA:\\1 S2], [GARG 82], [ABE 3:3] des méthodes et algorithmes sont proposés
mais qui sont liés à des représentations des arbres quaternaires à l'aide des pointeurs. Nous
proposons dans la suite des a.lgorithmes s'appuyant sur les méthodes syntaxiques proposées
au chapitre III.
Pour mettre en oeuvre les méthodes syntaxillucS nous incorporons dans la structure de
chaque bloc carré son q-code pour éviter de le recalculer à
S2

Chapitre V
V'IL
A iyonthmc VyrallL1du.l de S egmentatiolL d '[rn.'(J.ije;, en Régions
chaque fois ce qui augmenterait le temps decalcnl.
V.4.1 Implémentation des algorithmesâe calcul sYII(a~ique des voisins":
Nous avons au chàpitre III proposé une nll:.tlwde syntaxique de cal'cul des voisins dans un
arbre quaternaire (quadtree) utilisant les q-codes:ci-dessous nous déol"ivons les algorithmes
nous permettant de les mettre en oeuvre.
";'"
V.4.1.1 Algorithme de calcul des voisins de taille supérieuf'ê
C'est un algorithme qui dépend esselltiellt.'luelit dù ct-code du noeud dont 'on vel
calculer les voisins. soit E l'ensemble denmt contenir les voisins.
Début
q
~
le q-code du noeud
indicateur+-
vraie
tantque
indicateur +- vraie
faire
début
si le noeud de q-code q nI est pas une feuille
alors q +- pere( q)
sinon début
indicateur
+-
faux
E +-
le noeud de q-code q
fin
tin
Fin
figure v.7
algorithme de calcul des voisins dé taillesupérieure
83
r
i

C'hapllre V
U" /\\l.'/()nl1tl"" V!Jl'illll.idal ,1" 3eqlllelllalw"fl d'Images en Région.s
V.4.1.2 Algorithme de calcul de voisins de taille inférieure
C'est un algorithme qui dépend de 2 ou 3 paramètres selon que l'on veut chercher un
voisin dans les directions diagonales ou que l'on veut le faire dans les directions verticales
ou horizontales,
a) Dans la recherche daus les directiolls horizolltales ou verticales on aura t 1 et t2 les
codes possibles selon la direction choisi(~ et le q-code du noeud dont on veut chercher les
voisins. Soit l'ensemble contenant les \\'oisins.
Début
4. i-
le q-code de du noeud
1 i -
la longueur de q
ql -
concatenation de q ett l
tantque la longueur de ql of. i fJire
début
tantque le noeud de q-code
ql
nI est pas une feuille faire
ql -
concatenation de
q et
t l fintantque
E -
le noeud de q-code ql
1 Si le suff ixe de longueur 1
de
ql = t2
2 Alors ql -
concatenation de
ql
et
t2
fin
Fin
figure v.8
Algorithme de calcul des voisins de taille inférieure
b) Dans le cas de la recherche des \\'Olsms diagonaux soit t 1 le code de la direction
choisie.
L'algorithme sera le même que précédemn1l'nt à la seule différence qu'il faut supprimer
les instructions 1 et 2. Nous pouvons aillsi Lalculer cn temps linéaire O(k) les voisins des
noeuds dans un arbre quaternaire d'une scène. où l.: est le nombre de feuilles.
L'algorithme de fusion des blocs adjacents formant des régions homogènes proposé dan
[PAV 77]. [BOR 76] nous permet d'obtenir des segments.
S-!

Chapilr~ V
U'/~ /llyorilhllLI: PynUluJ.ul de Segml:nlal~o'n d. '{mages en Réglowi
Figure v.7-a
1môlge originille
Figure v. 7-b : Contours des segments délectés
seml EWTt· typr'. S = 0
s.s

Chapitrt V
Un Algo'rllh'me PyrwMd'al de SegmimfaLtoit d'Images <:~ Régions
F.igure v, a-a : Image loriginare
Figure v. 8-b
Contours des segments dét1ectés
.H~'lLil Eca.rt· ty}J/~ S = 16
SG

Chapli7'e' '1
U7~ l1igonlh-me Pyru.7IL't(J.(i.J d.e SegmeTlialioTl d'lma!le~ en Régio-ns
figure v.9-a
Image originale
Figure v,9-b
Contours des segments dé,tectés
seuil Ecart- type S = 10
Si"

Chapitre V
VIL ltlgortlhme PyramldaL de Seg11Lcntatio·fL d'fmages en Réglons
Figure v.l0-a
Image originale
Figure v. lO-b : Contours des segments détectés
.H~u.il Ecart-type S = 0
88

Chapitre V
UfI Il Igontltme Py-ro.midal de Segmenlalio-'l d 'jmages efl Régtons
Figure v. i 1- a
Image originale
•• : ; .,"
.
......J
Figure v. 11- b
Con tours des seg men ts détectés
seuil Ecart.type S =1U
S9
1

Chapltfe V
CONCLUSION
Nous venons de présenter une méthode de segmentation d'images en reglons qui
intègre complètement la structure linéaire des arbres quaternaires et utilise une méthode
syntaxique pour explorer le voisinage des noeuds, ce qui nous a permis cl 'améliorer le
temps de segmelltation; car la recherche des blocs adjacents se fait en temps linéaire, nous
avons aussi proposé une représentation des régions sous forme d'agrégats de blocs carrés.
Ce qui nous permettra dans le chapi tre sui VeUlt de proposer un modèle de base cl 'images
segmentées basé sur la représentation quaternaire.
90

CHA PI'l'IU: VI
"
UNE BASE D1INIAGES SEGNIENTEES
f1

ChapItre V
UIL Illgurll1lllLe Pyra.tmdu.i ,Le S egmenlal10n d'Images en Réglons
CONCLUSION
Nous venons de présenter une méthode de segmentation d'images en reglOns qui
intègre complètement la structure linéaire des arbres quaternaires et utilise une méthode
syntaxique pour explorer le voisinage des noeuds, ce qui nous a permis d'améliorer le
temps de segmentation; car la recherche des blocs adjacents se fait en temps linéaire, nous
avons aussi proposé une représentation des régions sous forme d'agrégats de blocs carrés.
Ce qui nous permettra dans le chapitre suivant de proposer un modèle de base d'images
segmentées basé sur la représentation quaternaire.
90

Chapitre VI
Une Base d'Image$ segmentées
INTRODUCTION
Le véritable prohlème d'analyse cl ïrnag;e ct dt' la recorumissaw.:e des formes est de traiter
automatiquement des informations qui ne soil:llC pas rédui tes ;\\. une simple expression
logique séquentielle et défiIlie à l'a.vaIlcc, ni reprèsellCées analogiquement par des grandeurs
physiques continues, mais qui sont comme représentées claus la nature. D'où la nécessité
de mettre au point des techniques permer,tam de représenter de manière symbolique une
image, ce qui permettra de mettre eIl évidente les primitives et les relations qui les lient. La
description d'une image en régions n'est pas seulement un-soucis de compression mais aussi
la recherche d'une représencation facile à exploiter. .\\près la segmentation d'une image il
faut extraire des informations qui seront r.rès lIll!JOrf.êtIlCèS pour faire la différence entre les
régions [GONZ ïï]. Il exisr,e plusieurs rwmicTl's de dl'nirc' les régions.
La description de Fourier étant basée sur la Cüllnaissauce à priori de points frontières de
la région. Quelques fois la région pcut l'trc <lonuée p;-\\r les points intérieurs si l'on s'interesse
à chercher les descripteurs qui sont illvariallts par trauslatiün. rotation et par changement
d'échelle. On peut aussi parler des descripteurs topologiques qui utilisent des propriétés sur
:es formes pour faire Ulle description globale des régious dans les images pianes ( nombre
de trous, nombre de composantes connexes).
f
Dans cette partie de notre travail nous \\"oulOllS fournir des outils permettant à partir
cl 'une segmentation pyrarniuale en régions. tIc rl'aliser Irne bn.sc cl 'informations permettant
t
de mieux exploiter les images cl 'une scène.
VI.l- STRUCTURE DE LA BASE
Il existe de nombreux modèles de représentation des objets chacun adapté à une
application d.onnée. Dans ces mod~les, on distill~~;ue g;énéralement deux grands types de
représentation: les représentations surfaciques et les représentations volumiques. Nous
1
a.llons dans le cas présent utilisé un modèle proposé par Shapiro ct Haralick [SH.-\\ Sa] pour

réaliser notre base d 'images segment<~l's .• [ans lequel l'atome sera le bloc carré homogène.
En s'inspirant de la structure de dOllnée décritl' par D ('ruse. c.,J. Oddy et A. Wrigth
[CRU 84], nous allons réaliser une base de dOllllées J Ïnfonnations spatiales. :\\Tous allons
dans la suite définir logiquement et physiquernem, CClllmem sont constituées les différentes
parties de cette base. :vIais nous ferons craborJ un rappel sur les bases de données et les
1
structures de données spatiales.
1
~1
91

t
1
if~

Chapitre VI
UILe Ba,;e li 'Images segmentées
VI.2 RAPPELS SUR LES BASES DE DONNEES
VI.2.1 Introduction
Notre SOUCIS ici n'étant pas sl'ulemem de stocker les infonnations. rnals aussi de les
retrouver plus facilement et de penllettrc lllll' nrilisiltiuu plus cOIl\\"iviale. il est nécessaire
de concevoir une structure intégrant le type Je traitclllellt que llOUS ayons fait au préalable.
Ceci ne signifie pas que notre base doit l'tre cU-pendante (rUn type d'application ou d'un
support physique quelconque. mais de proposer une solution au problème de stockage
de régions d'une scène, tout en maiutcml.1lt le lllode de stockage des structures filiformes
proposé dans [CRU 84].
Plusieurs modèles de base de donn~'es om é,té proposés dépuis leur avènement, nous
avons en l'occurence les modèles réseaux ct lliérarclriqul's llui utilisent plusieurs langages
pour les fonctions de ddinition. manipulation et contrôle de la ba.se. Les inconvénients de
ces modèles [DEL 82J, [CAR So] nous amène Aporter notre choix sur le modèle relationnel.
V1.2.2 Le modèle relationnel
Le modèle relationnel tire son fondement dans la notion mathématique de relation.
une relation étant une partie du produit cRrtésiell d'une liste de domaines. Soit donc
(Ddi= I. ... ,n l'ensemble des domaines. R sera uue relation sur les Di i = 1, ... , n si Rest
un sous ensemble du produit cartésien Dl x D2 X " . x DI! .
Nous faisons ici abstraction de certains tenues. tau t simplement parce qu 'on en trouvera
une bonne littérature dans [CAR 84], [DEL S2], Il est nécesaire que nous puissions nous
attarder un moment sur d'autres à cause de leur pertinence dans ce travail.
La manipulation des données est réalisée par l'utilisation élémentaire des manipulations
des relations, Ces opérations et leurs propriétés composent l'algèbre relationnelle. Pour une
bonne gestion de cette base de données. il faut UUl' couception solide. Après la segmentation
nous avons plusieurs informations sur chaque région de chaque image d'une scène que l'on
peut rassembler en une seule relation appelée relationuni"Ue·r.~elle.
92

ChapIt're VI
Une Base d'Images segmentées
Nous utiliserons donc l'approche par décomposition [GAR 85] , [DEL 82], [ULL 80].
Pour concevoir les schémas relationnels qui consiste à décomposer la relation universelle
en sous relations qui répondraient aux carences dans les modèles réseaux et hiérarchiques.
Ceci doit être fait par un algorithme qui permet une bonne intégration des propriétés
sémantiques des données.
~
j
La manipulation des relations s'appuit sur la pTOjection qui est un opérateur qui consiste
l
1
à supprimer les attributs d'une relatioll ct à l,li miner les mples en double qui risquent
1
d'apparaître dans la nouvclle relation ohr,cnue. Xous Je\\'OllS donc remplacer une relation
j.,
R par une collection de relations RI. R'L . ..... Rn obtenues 'par des projections de R et telle
')1
1
que la relation résultat de la jointure de RI, R'L' ...... Rn ai t le même schéma que R. La
l
joint'u're nai'tLTelle étant l'inverse de la projection.
Le soucis majeur est de décomposer sans pl'rte d'informations. Pour cela la notion de
1
dépendance fonctionnelle [GAR 85] nous permet. ,\\ partir des formes normales de concevoir
!
la base d'images segmentées orienté'es 2k x 2k
j
.
1
;
1
j
VI.3 STRUCTURES DE DONNEES SPATIALES
cl
La représentation des données spatiales est assez délicate, compte tenu des moyens
actuels de collecte des données visuelles, ceci a donné lieu à des conceptions des données
diverses qui reposent presque toutes sur les tables attribut·'ualeu'r (A./V).
VI.3.1 Conception logique des structures de données spatiales
Cette partie décrit une structure de données spatiales qui permettra de représenter toute
information spatiale ou une donnée relationnelle en mode linéaire , vectoriel ou tabulaire,
lTn atome est l'unité indivisible de donnée. Les entiers et les chaînes de caractères sont des
exemples d'atomes. On appelle A/V un ensemhle de pairs A/Y' = {(a. v)/a est un attribut
et t' la uale'ur a..~,'j(Jcié à Il}. Cl et li pcu\\'cnt être des atoull'S Ott des structures très complexes.
Une structure de données spatiales D est un ensemble D =
{R1, ...... ,Rd de re-
lations. Chaque relation R k a une dimension .Vk et la suite d'ensemble de domaines
S(l,k), ....... ,S(Nk,k) et pour k = 1...... 1\\:
R
ç
k
S(Lh:) x ... x S(Nk,k). Les éléments
des ensembles des domaines sont des atomes ou des structures de données spatiales, nous
avons donc une structure récursive [SHA 80], [VAl 82].
93

ChaptLre VI
UILe Base ci 'Images segmentées
Une structure de donnée spatiale représente une entité géographique, qui peut être
unpoint ou la totalité d'un espace complexe. Chaque entité a des propriétés globales, des
composantes et des entités de rclatious géograpltiques [SR.-\\. SOl.
VI.3.2 Quelques variantes des structures de données géographiques.
La plupart des structures sont établies :-iur la repr6scntation des régions par des
polygones.
SHAPIRO et HARALICK [SHA SOl ont fait allusion à. des réprésentations dont les
régions sont représenter par des polygones daus lesquels deux fichiers sont utilisés: l'un
contient l'ensemble des données de l'image qui cOlltient les segments qui définissent les
polygones. Chaque segment pointe sur sou Imly!!;ouC' de gauche et de droite.
Une autre représentation éVOqlll'C prl'wl pOllr dé11lCllt de base le segment de droite.
Chaque segment de droite est défini par deux llOt'tH!sfinaux plus des codes pour le polygâne
de droite et de gauche du segment de droite. C'L'st IUle structure suffisante pour représenter
toutes les relations topologiques entre les régions. Cn système similaire au précédent est
aussi décrit à la seule différence que l'llnité de \\>(lse est une liste de points qui peut être
utilisée pour déterminer le polygone entier.
Dans [SHA 80] la structure de donnée spatiale conçue est logiquement identique à la
précédente, le point est l'atome qui est constitué de ses coordonnées (x, y), une chaîne c
est une structure de données spatiales C = {AIVC. LP} LP est une liste ordonnée de
points de la chaîne. La table attribut-valeur contient le polygone de gauche, le polygone
de droite, la chaîne gauche suivante et la chaine droite suivante. Cn polygone P est une
structure de données spatiales simple P = {AIV P}. La table attribut-valeur contient
la première chaine du polygone et la position du polygone par rapport à cette première
chaîne qui indique s'il est à droite ou à gauche. Les attributs globaux de la région tels
que la surface ou le centre de gravité sont aussi représentés; la figure VI.1 illustre cette
représentation.
94

Chapitre VI
Une Base d'Images segmentées
}
Ji,
, .WP
1
1
1
CHAINll
(Cl)
,
lAJVP
1
CHAINll
(Cl)
1
POSmON CAUCHE
posmON DROm
5tJRPAC!
mR(Pl)
SURFACE
5UR(PZ)
CCRAVDI
CDC(Pl)
CCKAvrœ
CDC(P'Z')
Cl
Cz
A/YC
REGION-G
(Pl)
AlYC
REGiON-G
.111
LP
LP
DQON-P
(Pl )
UQON-D
(Pl)
CJLmŒ.5-C:
(~)
ClfAlNF,S-c:
.111
CBAJrŒ.5-D
( 0 )
CJIAl1Œ.$.D
(Cl)
-3 1-.-
-1 1-, 1
1~la71 ~la9f.I~!&% 1aJ~
LONCtlDIR
l.I. . (CI)
LONCUlVR
Lmc«(
~
f1
AlYC
REGION-G
(P2;)
1
LP
UQ,ON-D
Jl.II1
CHAINE-5-C:
(Cl)
CBAJ1"Œ.S-D
.111
., 1-11 -111-121-131 1.31
LOl'fcmml
laac(CJ)
figure vi.(,: représentation d'une région formée de deux polygônes
95

ChapitTe VI
Une Hase d. 'Images segmentées
Une autre structure de données spatiales décri te dans [5HA SOl est la la structure de
données triangulaires qui est utilisée pour reprt'~l'uter des données surfaciques et un triangle
représente une partie de la surface 3 - D. Dans la structure de données triangulaires, chaque
triangle pointe sur ses vecteurs et sur les triangles adjacents. Un triangle sera donc une
structure de données spatiales T = {L V. AT} L V est une liste de vecteurs et AT une
liste de triangles adjacents et chaque vecteur l" est une sturcture de données spatiales
F = {.-ljVl"} .-J.jFF contient les attributs BASE, HA.TT E[~R et autre information.
Hanan SA),IET et al ont dans [SAM 84] utilisl's les a.rbres quaternaires pour développer
un système dïnformations géograpllÏc(llC's. lïlllpkllll'UUltion l'st faite en utilisant les B-
arbres [DEL S:2] pour organiser les feuilles dl' l'arbre quaternaire et la représentation utilise
un code linéaire. L'arbre quaternaire est fait Je quatre parties. La première de taille fixe
contient les informations ::lur la taille du rrcLiLT ,ot ciL- la stl"Ut:ture du B·arbre, le second est
composé de blocs de taille fixe. la troisième partil' contient une liste de commentaires, ces
commentaires sont générés par les fonctions de bases de données quand un nouvel espace
est créé ou inséré à la demande de l'utilisateur. le <..{uëltrième contient la liste des pages du
B-arbre qui contiennent les noeuds de l'arbre qUëltenaire.
En nous inspirant de [CRU 83] et [SA\\1 8-!] nous allons concevoir une base d'images
segmentées établie sur les blocs carrés homogènes maximaux. L'atome dans ce cas sera
le bloc carré qui aura pour données la base du bloc et le niveau du noeud dans l'arbre
quaternaire.
96

Chapllre V[
U/~e Ba..,e d '[mages segmentées
VI.4 DESCRIPTION DE LA BASE D'IMAGES SEGMENTEES ORIENTEE 2k X 2k
L'analyse d'image haut lllveau demande un acres rapide aux informations sur les
régions comme les attributs, les codl?s frollti~rl':i et autres informations. Nous présentons
ici une approche qui stocke les blocs carrés homogéul's et par un ensemble d'algorithmes
permettant de retrouver tous les autres éléments de la région tels que la surface, le polygone
représentant la région, le centre de gravité ou encore l'axe médian [SAM 83]. Notre base
stocke toute information indépendcmment de la scène. Comme dans [CRU 84] l'index
région contient toutes les régions de l'image et c11aque région est identifiée par un unique
identificateur de règiou, pOUl' dmqUl'régioll les illfül'lllëltious sont stockées dans les attributs
de région. Une relation spécifique uous permet de décrire les adjacences. L'originalité
ici c'est qu'au lieu d'utiliser les frontières pour l'l'présenter les régions nous utilisons les
blocs carrés homogènes et maximaux. L'index des blocs ca.rrés contient les blocs carrés qui
constituent les régions et qui peuvent permet ne de retroun.'r les frontières sans difficultés.
Chaque bloc carré a un seul identificateur. LL's rdatious du paragraphe suivant vont nous
décrire l'uni"ers des images.
VI.4.1 Différentes relations constituant la base
Dans notre travail nous considérons que les objets du monde réel peuvent être modelisés
par des blocs carrés homogènes. En considérant que les objets sont définis par des régions,
nous pouvons décrire la scène comme suit: Une Image est un ensemble de régions qui sont
elles même composées de blocs carrés homogène.'J et des blocs qui sont définis par leur base
et leur niveau dans l'arbre quaternaire.
Nous allons utiliser un modèle entité relation [DEL 82] [GAR 85] pour définir nos
relations. D'où la définition des relations qui décrivent les entités présentes dans le schéma
et les relations qui décri"ent les diverses associations entre entités.
;.rous avons donc les relations suivantes:
REGION (Id-de-Région, forme. Intérieur)
. Id-de-Région représente l'identificateur de région
- Intérieur est l'adresse d'un enrégistrement Qui contient les attributs de la région
- forme représente ((.r l, yll; (x .. , Y2 )) Olt (.l~I.!l1! est la base du bloc le plus à gauche et le
plus en haut et (.T2. Y2 ) le coin le plus en bas le plus à droite.
97

Chaptl-re V[
Une Base d'Images segmentées
ADJACENCE (Id-de-regionL Id-de-region2, \\·aleur-acljacen<.:e) Id-de-regionl et Id..,.de-
region2 nous permet de détecter l'adjacetlce des deux régiolls ct valeur-adjacence le dégré
d'adjacence.
BLOC( );O-bloc,Id-de-image,id-de-region, adresse-bloc, niveau-bloc)
ATTRIBUT (Id-attribut, Id-de-region, < vcctenr atcributs>. <Longueur attributs»
Conceptuellement notre base cliffère des a.utres bases de données spatiales évoquées
dans notre travail par le fait que l'élément fondallleutai c'est le bloc carré homogène, mais
nous allons à partir des algorithmes décrits plus bas, retrouver tous les autres éléments
caractéristiques de la scène décrits dans les autres conceptions. Les principales tâches qui
sont la création de la base à. partir de la segmentation pyramidale qui nous permet d'établir
des relations entre blocs carrés et de donner des adresses aux régions. Nous pouvons
aussi extraire des attribms d'une région, fusiouuer des régions. Il est possible de classifier
des régions suivant des critc'res donnés. Nous pouvons aussi faire de la reconnaissance
syntaxique de structure en utilisant les contours d'une région à. partir des segments de droite
composant le polygône représentant la région ou l'ensemble des blocs carrés composant
l'intérieur de la région ce qui est une originalité dans notre travail.
V1.4.3 Algorithmes de création et d'exploitation de la base
V1.4.3.1 Création de la base
Après la segmentation de l'image en régions homogènes nous avons un ensemble de
données stockées dans différents tableaux, pour sauvegarder ces résultats dans la base
nous allons d'abord trier les blocs par ordre croissant des bases des blocs considérés et
stocker chaque région aux endroits appropriés dans la base. Soit V(i)
i = 1, ...... , Nb/oc
.Vbloc est le nombre de blocs carrés homogènes, la matrice représentant les segments.
98

.~
j
i
J
Chaplt"re VI
Une Ba:ie d'Images segmentées
\\ij
}
~
}
Chaque cellule contient le numero du segment auquel il appartient. GONT R(I, *)
~1
contient les blocs contours du segment de label i et GONTR(i,O) contient le nombre
i11
de blocs contours du segment i; on parcoure CO STR( i, *) et à chaque élément on fai t
j
correspondre un enregistrement d'adresse qui serait fonction de i et l l est le label du
segment auquel appartient le bloc de rang l~.
L'algori t hme es t le sui vant.
Début
Pour i ;- 1 à Nb:,egment faire
Pour j ;- 1 à CONTR(i,O) faire
début
Créer
l'enregistrement d'adresse seg(i)
Créer
l'enregistrement les relations d'adjacence correspondant à
tous les voisins du segment d'adresse seg(i)
fin
fin
figure vi. 2
création d' un enregistrement.
VI.4.3.2 Extraction des attributs.
Nous avons la possibilité à partir de la base d'images segmentées créée de calculer un
certain nombre d'attributs; comme la surface de la région, le centre de gravité, le périmètre;
avant cela il nous faut d'abord concevoir un algorithme de suivi de contour à partir de la
représentation de l'arbre quaternaire.
VI.4.3.3 Fusion des régions dans la base
Pendant la segmentation, à cause des bruits ou tout autre problème, des régions très
petites sont détectées et qui réellement ne représentent pas grand chose, compte tenu de la
richesse des informations qui se trouvent dans notre base, il nous est possible de savoir si
oui ou non cela est possible de fusionner deux régions. Une première approche consisterait
à chercher toutes les régions qui ont une surface inférieur à dix pixels et d'examiner leur
voisinage afin de détecter pour chacun quelle serait la région voisine qui
99
f1

Chap·dre VI
U ILe Ha.ie d '{mages .iegTTLenlées
aurait le plus clé chance à être fusionnée; la fusioll <.:n clle même doit se faire en balayant
les blocs carrés des régions cn vue d'une insertion ou d'unc fusion de bloc pour former de
nouveaux, Après la fusion des régions il faut mettre à jour les adjacences. En entrée pour
l'algorithme de fusion de régions nous avons les blocs de la première Ri et la deuxième
région Rj .
Début
Initialiser LUAQPT
Pour 1.. -1 à m faire [jI.-!qPT(.-!<if'{;;,,;c-(R,J.:J) i- 1
Pour 1.';- 1 à Il faire IJIAqPT(Adn.'i,'ic(RJJ.:!);- 1
Fu~onner les blocs.
Modifier
le fichier d'adjacence pour les enregistre ments
relatifs à Ri
et R j .
Fin
figure vi. 3
Algorithme de Fusion de deux régions
VI.4.3.4 Classification des régions et reconnaissance syntaxique des formes
A un certain moment la nécessité de reconnaître une région pem s'imposer; c'est-à-dire
au vu d'un certain nombre de caractéristiques d'affecter une région à une classe donnée, on
peut par exemple utiliser la distance euclidienne sur l'espace des paramètres pour évaluer
l'appartenance d'une région à une classe.
Les régions représentées par des blocs carres peuvent t-trc utilisées pour faire de la
reconnaissance des formes en utilisant les mér.hodcs syntaxiques. pour cela on peut chercher
tout d'abord à obtenir une représentation polygonale telle que définie au V1.3.2. On pourra
ainsi mettre les régions da.ns Ull analyseur. afin dl? dé'finir les formes qui peuvent être des
("carré", "cercle·'.1osange, etc) comme da.llS [CRe 84].
100

Chapitre VI
Ulle Base d'images segmentées
,
f
J
VI.5 UN ALGORITHME DE DETECTION DES CONTOURS D'UNE REGION OBTENUE PAR
!
SEGMEI\\JTATION PYRAMIDALE
1
La segmentation pyramidale IlOUS permet cl 'olJtenir des segments( régions) d'une image
1
décrite par des agrégats de blocs carrés maxiruaux(Iloeuds de l'arbre quaternaire), mais
1
dans certaines applicatioIls, il est lll'c'ssain: dl' rL'prc'sL'lHer l ïmage par un polygone des
î1
contours, d'où la nécessité de passer cle la reprl'sentatioIl t'Il agrégats de blocs à une
î
1
représentation en polygone de comours. Nous allons décrire d'abord les structures finales
"'l
à obtenir et ensuite le procédé d'obtention du résultat, en 'nous inspirant de [DYE 80],
1
1
1
1
V1.5.1 Structure du contour
t
]
Nous allons utiliser la structure décrite au \\"1.:3.2, mais les segments utilisés n'auront
pas la même signification, car pour chaque segmeIlt il y a.ura quatre directions possibles
pour la 4-connexité et huit directions possibles pour la S-connexité et ceci suivant le code
1
de Freemann ; un segment aura la structure suinmw :
J
ADRESSE
DIRECTION
TAILLE
--------
figure vi.4
structure d'un segment dans un modèle quaternaire
où ADRESSE représente l'adresse du premier point du segment , DIRECTION la
direction du segment qui varie de 1 à -4: eIl réseau carré et de 1 à 8 en réseau octoganal et
T.-\\.ILLE représente la longueur du segment.
ün polygome (contour d'une région) sera clollc représenté par une suite
a = (al,a2, ........ ,a'1) où l'adresse du premier pixc1 de al est l'adresse du dernier pixel
de an dans le cas d'une région pleine; mais si la région a des trous avec t le nombre de
trous alors la région sera décrite par t + 1 polygones contour.
1
101

C/wp'L/re VI
Une Ba;;e d 'Fmages !legmentées
V1.5.2 Principes de recherche des contours
La région est représentée par une suite de blocs carrés homogènes, nous nous proposons
d'en extraire les contours, nous allons, sans que cela modifie le cas général, travailler sur un
réseau carré; nous avons pour chaque bloc la possibilité d'avoir quatre voisins N, S, E, vV
et il peut pour chaque direl~tion choisie' sC' produire quatre possibilités: un bloc peut avoir
pour la direction D :
1- Cn voisin de même taille
2- des voisins de taille plus petites
3- un \\'oisin de taille pius grandi.'
-±- :\\c pas a\\'oir de voisin
et pour chacun de ces cas, il faudrai t chuisir s'il faut ou pas représenter une portion ou
la frontière toute entière. Quand le voisill existe et qual1ll il a une taille supérieure ou égale
à celle du bloc considéré on ne retieut pas la froutière . et si elle est de taille inférieure on
représente la frontière non commune aux deux \\'oisins dans la direction choisie. Si le voisin
n'existe pas on représente toute la frontière.
V1.5.3 Algorithme de détermination de contour
VI.5.3.1 Détermination préliminaire des contours
Soit D la direction choisie. B le bloc et V oisin( D. B) le voisin de B dans la direction D
F RO .:VT[i, j] est le tableau contenant les SL'~lllemS contours
FRO.YT[*.1] contient l'ad.resse
FRO.VT[*, 2] contient la direction
F RONT[*, 3] contient la taille
La variable compteur nous permettra d'incrementer le tableau F RO NT
102

j
1
~
UrLe Base d '[mages segmeTdées
1
Chapdre VI
le
\\
j
1
1
1
Début
1
compteur ...... 0
Pour B ...... 1 à nb/oc faire
1
début
j
pour D = 1 à 4 faire
t1.
début
si voi.sin(B,D)
existe alors
Début
Si Taille(B) ~ taille(voisin(B.d)) alors
Pour tout voi.sin(B,D)
de taille = Tl < taillc(B)
qui n J appart iennent pas à la région faire
Début
compteur ...... cO'lnptcul" + l
FRONT(co7lt]Jteul",I)""" ltd"C:jM.. (V()i~inlB,D)
de taille
Tl)
F RONT( compteur, 2) .....-- L UT( D )
FRONT(comptew', 3) - - Tl
fin
fin
Sinon
dé but
compteur ...... compteur + 1
FRONT(compteur, 1)
A.dresse(B)
F RONT(compteur, 2)
LUT(D)
1
FRONT(compte-ur,3)
Taile(B)
f
fin
1
fin
fin
Fin
figure vi.5
Algorithme préliminaire de détermination de contours
103
t
f
1

Chapitre VI
Une Base d'Images segme''l.tées
LUT D( D) est 'Une table qni no'Us pe'rmettra de calcule'!' la direction d'U segment à partir de
la position dit 'uozsm.
N
E
s
w
1
2
3
4
VI.5.3.2 Chainage des sommets pour la formation des polygolles
Pour faire le chainage des sommets nous allol1s utiliser Ulle colonne supplémentaire qui
nous permettra de loger l'adresse du prochain SOIllmet, et nous permettra si l'on entre à
partir de n'importe quel élément de pouvoir parcourir totalement le contour.
VI.5.3.3 LUT du parcours du voisinage d'un bloc COl/tour
Quand nous avons une direction dans laquelle on construit le chainage, il faut éviter de
tourner en rond, pour cela nous avons conçu une L"UT qui résoudra le problème
Lurl
1
2
D = 1
2
4
D = 2
3
1
D = 3
4
2
D = 4
1
3
LUT1( i, j) contient la je direction qu'il faut exploirer après la direction Z:.
VI.5.3.4 Algorithme de chaînage quaternaire des contours
Une matrice [.11.-1 nous permet d'enregistrer les points pivots ues contours qui sont des
bases des blocs carrés contours et [Jf.-l( i. j) Lulrl'sse du segment de droite qui sont les
coordonnées (:r. y) de son premier point.
D représentera sa direction et t sa taille.
104

CheLp'itre VI
Li ne Ba.se d'Images segmentées
DEBUT
1nitialiser LH.-1..
ET.-1..Tl ;- Vraie
D ;- Dl; (J:, y) ;- (l' ( 1), y ( 1)); T = T (1) ;
Faire
cas D de
début
1 : yI ;- !J -t- T
:2 : .rl ;- .r T T
:3: .Ill ~ U - T
-l::.d ;-.l' - T
fin
Si IJI.-l.(.d, yI) = 0 Jlors bire
cas D de

début
l : y'2 .- y 1 + l
:2 : .7:2 ;- .rl + l
3 : y2 ;- yI - l
.:J: : x? ;- .1' 1 - l
fin
Si IJfA.(T'2, y'2) =1= a alors faire
début
(:c, y) ;- (x'2, y'2)
D;- FRONT(fJl.'{(.l',Y),'2)
T;- FRO.VT(lJIA.(.l',y),3)
fin
Sinon
début
Etat ~ urai: 1 ~ l
tant que etat et i ~ :2 faire
début
cas LUT(D, i) de
début
l : y 1 ;- y2 + 1
:2 : .rl ~ .r2 + l
3 : y l ~ y'2 - l
-l: : .rl .- 1'2 - l
fin
105

Chap'Llre 'II
Une Base d 'lmages segmentées
Si IAJ.-l.(xl,yl) i- 0 alors faire
Début
k f- LH .-i(:r. v); 1 .- JAJA(.r 1. VI)
FRO:VT(J.-.3) f- T + 1: FRO.vT(l,:.3) f- FRONT(L.3) + 1;
IJJ.-i(J:2.y2) f- LH.-i(.r1.yl):
L\\1A(1:I,V1).- 0
etat f- faLLx
fin
if-i+l
fintantque
Sinon faire
si (l'LvI) = (.r.!}) alors ETATI ~ fULL./';
sinon (l', v) f- (J·1.u1)
Tantque( ET.-iTl!
FIN
figure vi. 6
Algorithme de chanage quaternaire des contours
initialiser JAJ.-l.
debut
Pour if-> 1 'a .Y ombr front faire LH.-l.( F RD NT( i, 1)) f- i
fin
figure vi. 7
Initialisation de IMA
106

Chapltre VI
Une Ba.se d'Images segmentée.5
1,
:1
J
1
V1.5.3 5 Compression des données quaternaires par accolages des droites contigues de même direction
!
1
Après le chainage des éléments frontières cl 'uue région , il est possible de réunir dans
une même structure plusieurs éléments contigus ayant la même direction de manière à
récuperer de l'espace et cela grâce ci l'algorithme suivant:
1
J
t
F RO NT( i. *) contient les données sur la je droite
!
J
tl
DEBUT
l
!
l <- F RONT('i, 1)
t
etat <- vraie
tantque (etat) faire
1
début si FRONT(i. 2) = FRONT(l.2) alors faire
1
t
début
FRONT(i,3) <- FRUNT(i.3) + FRO.YT(l,3)
1
l <- FROXT(l.'-t)
fin
sinon
début
FRONT(i,4) <- l
i <- l;
tin
si l = 1 alors etat <- faLLJ.:;
fintanque
FIN
figure V.S
Algorithme de compression des contours
Nous obtenons donc Ulle structure chainée représentant le polygone contour de la zone
considérée, ce qui nous permet d'envisager la. représentation proposée dans [SHA Sa].
lOï

Chapltre VI
Une Base d'Images segmentées
CONCLUSION
~ous venons de présenter la conception J'ulle base dïlllRgcs segmentées. Nous avons
donné une représentation spatiale dont l"awlllL' L'st le bloc carré homogène. Ceci est dû à
la structure du résultat de notre segmentation, :\\ous ,1\\"ons aussi proposé des algorithmes
permettant de passer de cette structure à des structLu'CS de donllées spatiales ayant pour
atome le point. :\\"ous espérons que cette conception aura des dé\\"eloppements futurs.
lOS

/
/
CONCLUSION GENERALE
1

Conclusion Générale
Les arbres quaternaires sont une structure Je données bien adaptée au traitement
d'images et à la reconnaissance des formes g;rap hiq nes, Nons venons de présenter un
formalisme syntaxique qui représentc unc image comme Ull langage sur un alphabet à
quatre lettres, nons définissons aussi uu systèmc de réécriture qui permet de retrouver tous
les voisins d'Ull noeud (bloc carré) sur un arbre 4uaterllaire ce qui noùs évite d'utiliser les
pointeurs comme c'est le cas dans la plupart des travaux précédents,
:\\ous avons construit une base de Haar qui uous il. permis par analyse et/ou synthèse
de faire de l'analyse multi-échelle d'ima.ges gnll'c Ù, l'adé4uatioll parfaite de cette base et
de la structure d'arbre quaternaire, nous ayons donc l~té amené à comparer ne serait ce
qu'expérimentalement la transformatioll dc Hilar "yel.: d'autres transformations comme la
transformation cle fourier, Il en sort que l'ctte tr<'l.llfonnation promet à une très bonne
utilisation compte tenu des temps de calcul obtenus,
~ous avons aussi pu vérifier les capacités de la transformation de Haar en filtrage
dynamique,
:.Jous discutons aussi dans notre travail de la compression d'images, ce qui nous permet
de montrer que la compression en termc dl' bits n'est possihle que pour des images ayant
un nombre important de grandes zones homogènes.
Un autre aspect avantageux de cette transformation est le fait qu'elle nous permet de
préparer une segmentation d'image en utilisant un algorithme ascendant ou descendant.
;-;ous proposons aussi une segmentation pyramidale d'image. Ce qui est l'occasion pour
nous d'exploiter non seulement la manipulation syntaxique des informations graphiques
mais aussi d'utiliser les données de la pré-segmentatioIl fournie par l'analyse de Haar,
~ous proposons aussi la conception d \\lIle base cl 'images segmentées avec pour atome le
bloc carré homogène qui nous permet de stocker les résultats d'une segmentation d'images,
?'Tous venons d'étudier un formalisme topologique syntaxique permettant de manipuler
les informations visuelles à partir d'un alphabet à quatre lettres et d'un système de
réécriture, il serait interessaut de pouvoir ù partir de ces données concevoir une grammaire
d'étude des \\'oisinages dans la manipulatioll syntaxique des informations spatiales,
109

\\ ",
J
.
~l
1
i
1
!
1
,
1
1
BIBLIOGRAPHIE

81bllographie
[ABE 84] D. J. ABEL
A B+ -Tree structure for large Quadtrees
Computer Graphics and Ima.ge PTOcessing 27, pp. 19-31. 1984
[A~T 82] H.J. A::\\TONISSE
Image segmentation in pyramids
Computer Oraphics and Ima.ge Pro(;e.;,~in9 19, pp. 367-:383, 1982
[AYA 89] N. AYACHE
Vision stéréoscopiq'ue et perr:eption nwltisen::;orielle
InterEditions, 1989
[BER 79] J. BERSTEL
Transd'uctions and context-free la:ngaQ.ye"
Stuttgart Teubner, 1979
[BOU 84] J.C. BOUSSARD R. }"'1AHL
Algorithmiq'ue et structure des don'ILte_~
Eyrolles, 1984
[BOUT 88] P. BOUTHEMY
:"Iodèles et méthodes pour l'analyse du mouvement dans une synthèse d'images
Technique et Science Informatiques, \\'ol 7, no 6, 1988
[BRE 87] F. BRETAUDEAU,C. ENAULT,P. SECCHI
Segmentation d'images texturées: Application à des images de télédétection
in proc 6e Congrès RFIA, pp. 1ï7-19L Antibes, ~ov 1987
[CAM 85] J. CAMILLERAPP, P. LEBELLEGARD
Détection de contour par coopération d'une analyse
syntaxique ligne et d'une analyse syntaxique colonne
in proc 5e Congrès RFIA, pp. 187-199. Grenoble. 1985
[CHAN 91] C. C. CHANG. S. Y. LEE
Retrieval of similar pictures on pictorial Databases
Pattern Recognition, vol 24. no 7, pp. 675-680. 1991
110

[CHA 84] J.M. CHASSERY, C. GARBAY
An iterative method based on a. contextual color and shape criterion
IEEE Tmns. on Pait. Anal. M(J.ch. Intdl., vol PA:\\H-6, no 6. Nov 1984
[CHO 90] W.-S. CHOU, C.-0:I. VVU, Y.-C. CHE:..r, K.-S. HSIEH
Detecting myocardial bouncleries of Idt n.'rltricule from a single frame 2DE Image
Pattern Recogn'ition, vol 23, no ï , pp. ï99-S0G. 1990
[CL! 86] .-\\. S.CL!FFORT, H. SA:\\JET
An optimal quadtree construction Algorithm
in Proc IAPR-8, pp. 31ï-319, Paris, 1936
[COC 84] J. P. COCQCEREZ
Analyse d'images aériennes: extraction de prim-itives rectilignes et antiparallèles
Thèse de Doctorat d'Etat, Paris-Sud ORSAY, 1984
[COC 85] J. P. COCQCEREZ, J. DEVARS
Détection de contours dans les images aériennes : nouveaux opérateurs
Traitement du signal 2-1, pp 45-46, 1985
[COS 85] :\\rI. COSTER. J. 1. CHER!YL-\\\\'T
Précis d'ana.lyse d'ima.ges
Editions du CNRS, 1985
[CRU 84] D. CRUSE, C.J. ODDY, A. \\,VRIGTH
A segmented image data base (SID) for image Analysis
in Proc lAP R·7, pp. 493-496. ~vIontréal, 1984
[DAN 81] A. J DANKER & A. ROSE:\\"FELD
Blob Detection by relaxation
IEEE Trans. on Pait. Anal. Mach. lntell.. \\'01 PA?vII-3, no 1 ,Jan 1981
[DAC IN] 1. DAUBECHIES
The wavelet transform, time-frequency localisation and signal analysis
AT&T Bell Laboratories 600 .\\tlo'{{,ntain. Aven'ue Murray hill. N.! 07974
I I I

BIbliographIe
[DEL 82] C. DELOBEL, M. ADIBA
Les bases de données et systèmes relationnels
Dunod informatique, 1982
[DER 83] F. DERAVI et S.1\\:. PAL
Grey Level Thresholding using second-order statistics
pattern recognition letters 1. pp. 41 7--122. 1983
[DER 83] R. DERICHE
Optimal Edge Detection using recursi\\'e filterring
IEEE Trans. on Patt. AnaL Mach. Intdl.. pp. 501-505,1987
[DEV 86] P. A. DEVIJVER
Segmentation of binary Images \\lsill~ r hirel-order lllarkov mesh models
i.n Proc IAPR-S. pp. 259-2Gl, Paris. 19SG
[DEV 87] P. DEVIJVER, !l.LDEKESEL
Algorithmes d'apprentissage d'un modèle ~Iarkovien d'images
in Proc 6e CongTès RFIA, pp. 195-207. Antibes, ~ov 1987
[DON 85] H.-S DON and I\\:.-S FU
A syntactic method for image segmentation and objet recognition
Pattern recognition. vol 18, no 1. pp. 73-87. 1985
[DUO 73] R. O. DUDA, P. E. HART
Pattern Classification and scène analysis
",,"iley, Ne\\'.· York 1973.
[DYE 80] R. DYER. A. ROSENFELD. H. SA\\IET
Region Representation: Boumlary l'odes from Quadtrees.
Communica,tions of the A CM. \\'01 23. IlO :3. 1980
[FAU 85] A. FAURE
Perception et reconnaissa.nct dt;; forintS
Editests. 1985
112

Bibl-iograpIH~
[FRE 61] H. FREE~IAN
On the encoding of arbitrary geull~l'tric cOlâiguratiull
IRE Trans, vol 10, pp. 260-268, June 1961
[FRE ï4] H. FREEMAN
Computer processing on line-drawillg images
ACM Computing s'urveys 6, pp. 5ï-9ï. \\Inr 19ï4
[GAB 86] R. GABRIEL
Et'Il.de de t'ransfonnées fonctionntlle" applùjuù,.3 il. la r:ompression d'images
(Algo1'ithmes,A rchiteetures a:;sociùs)
Thèse 3e cycle, Université J'Aix \\Iarscille. 1986
[GAG 85] A.GAGALO\\VICZ, O. MO:\\TGA.
CT n algorithme de segmentation lliél'arc1âqtlL,
in Pme 5e Con,lJTès RFIA. pp, 1C:3-1 ïï. Cl'('llOhlc. 1985
[GAG 86] A. GAGALO"VICZ, O. ~vIOi\\GA
A New approch for image segmclHariul1
in Proc IAPR-8, pp. 265-26ï, Paris. 1086
[GAM 85] J. P. GAMBOTTO
Estimation récursive de la moyenne de signaux bidimensionnels:
vers une approche parallèle de la segmentation cl 'images.
2e Colloque s'ur le traitement dit ::;ignal id st,~ applications, :'Ji ce, 1985
[GAR 83] Y. GARDAN et M. LUCAS
Techniques graphiques et Intemctives et C.A.O
Hermes, 1983
[GARD 85] G. GARDARIN
Ba..se.s de données. les .sy.sthne8 d lenr.' lu:ngage$
Eyrolles. 1985
[GARG 82] I. GARGA:\\TTINI
An effective way ta represcnt quadtrcC's
Computer Graphies and Im(J.g(~ fJ'f'Oct:",n:ng. \\'01 25. nu 1:2, dec 1082
113

[GIR 3ï] G. GIRAUDON
Chainage efficace des contours
MARI 87. Cognitiva 87(CESTA). Paris. pp. 29-35. 18-20 mai 198ï
[GRO I:-J] A. GROSS:-'IAf-;"
\\Va\\'elet Transform and cdgc dC'rcnioll
Centre rie phy:;ifJ.'((.(: théo'l'ùjl/c ..;u:i'lin II. CNRS L'llminy w.;e 907
[GO\\" ïï] R. C. GO\\"ZALEZ, P. \\\\'I\\"TZ
Dig'ital Image Proccss'ing
Addison- Wesley, 19ïï
[GO.:i ï8] R.C. GO:-;ZALEZ. :\\'1. G. THO:\\IASO\\'
Syntacûc Pa.ttern Recognii'i.o{l : An /.t/,tTuJlI.ctimi
Addison- \\Vcsley. 19ï3
[GRO 84] A.GROSS:\\IAi\\. J. :-'IORLET
Decomposition of Hardy fllncriulls illro ;1 SllllilI'C inwgrahle
wavelets of constant shape.
SIAM Journal Math. Anal, Vol 15. 110 4. Jlll ElS4
[H.-\\.C 38] F. HACHOUF
Télédétection de conto'urs linéa1.'l'(:'s
Thèse 3e cycle, Universit<~ de ROllel!. 10SS
[HA:\\S 32] F.R. HA:\\'SE\\" , H. ELLIOT
Image segmentation using simple :\\Iarl~()\\' Field :\\fodcls
Comp'uter gTaphics and image:; [J'roce.;.>mg 20. pp. 101-132. 1982
[HAR 34a] R.:YLHARALICh:, L.G. SHAPIRO
SURVEY in image segmentation techniques
Comp'litcr gmphic.3 a.nd 'irnalJc pToce3.;in.IJ 29. pp. 100-1:32, 19S5
[HOP 69] J. E. HOPCROFT
Form al la:ny·/I. (J..IJ t.> (J.Ull th eil' re!u.tùm, t Il 11./1. i{)fil Il. t (J.
Addition-wesley. 1969
114

[HOR 76] S. L HORO\\VITZ. T. PAVLIDIS
Picture segmentatioll by a trcl' trawrsal algoritlull
Jo'nrna.l of the A CM, vol 2:3. llO :2, pp. 3GS-:3SS. April 19ï6
[HOS 85) :VLHOSPITAL, M. RICHE LI:\\' . J. GALLICE
Segmentation en bandes d'images grises par segmenta tion
polygonale des contours binaires orientl's
in proc 5e CongTès RFlA. pp. 1i9-1Se. Grenoble. 19S5
[HOU 91] S. HOCZELLE. G. GIRArDO\\"
Segmentation des rt'gions ]l'U' lllUddisi 1riOil des 111.1 (ri(",',~
de co-occnfcnce
,in pme RFIA-S. pp. 117i-llS:3. \\ïlknrkllllll" :\\'0\\' 1991
[JAL 91] A. E ..JAIN. F. FARROI~H\\T-\\
Cnsuperviseu Texture scgnH'tlCH(ioll nsillg G",hor filcers
Pattern Recognition, vol 2-L 110 12. jJjJ, 11Gï-llSG. 1991
[KHO 90] A. KHOTHANZAD. A, BOe A[tF.-\\
Image segmcntation by pnrallcL llOll-P<ll'èllllC(ric histogram based
clustering algorithrn
Pa.ttern Recognition, vol 23, no 9. pp. 961-9ï:3, 1990
[KRO Si] R. KRONLAND-~L\\RTE\\ET.J. \\IORLET. A. GROSS?vL-\\N
Analysis of sound through wawlet trallsfonns
Centre de physiqne théo/1.1{UC ..<u:tion II. CNRS-Lu,'rn.my-ca.se 907, 1987
[LAU Sa] ~vI. LACG
Traitement optiq'ue d1L szgna.l d Je,;wwyt.<
CER_-\\PUES EDITIO!\\'S. 19S0
[LOE 86] :"1. H. LOE\\V. S.-X LI
Adjacenty Detection using Quadcodcs
in Proc. lCP R-8, Paris, ocrober 19SG
[LE:"I 85) P.G LE:\\L-\\RIE. '{ ..\\IEYER
Oneielet tes et Bases Hilbertienllcs
Centre de ivfathéma.tiq·lLe.~ de l'ecole polytf:chnùj'llc
U ..-\\ CNRS no 169. 1985
115

Flibliogmphzc
[LCT 90] E. LCTTO~
Re.connai.s;wnce du point de p.,..i,;t: del/({.I; d'/me photofj'raphie
Ù. P(J,Tt?T d ·({.n modèle de ,;(;f~'fI,(;
Thèse de Doctorat ENST p<lri:i. lllai 1990
[:--I.-\\L Sial S.G. ~vI.-\\LLAT
A theory for multiresolution signal de('~)lnposition :
the wavelet representation
IEEE Tm;n". on Patt. Anal. M(u:h. [nteU.. Vol 11, no l, .Jul1989
[:--I.-\\L Slh] S. G }IALL.-\\T
:--Iultiresolution approxillla,tiùu aud wan:lc[s
• idS·CIS 87·87. GRASP LAB SO
[\\I.-\\R 84] F. :--I.-\\RT1NEZ
Lu. -,ynthèse. d "image" : Concept.;.lv[a.t{n:d:; d lUlJicid,;
Editests. 198'-1
[:--1.-\\1 S5] H. :--I.-\\1TRE
Lu. SI~{j'lnent(J,tion des II/LaiJl~,; : Elu.JI. 11I:;J!;lJYTplllll""~
SCP TELECO:"!. Sept 1985
[:\\IEY 85] Y. \\tIEYER
De la recherche pétrolière à la géométrie des espaces de Banach
en passant par les paraproduits
Centre de Ma.thématiq'UEs de l'ecole pulytechniq'U.e
Sem7:naire. équation" a'ux diT·l'Vie.; partielles 1985·1986.
[\\IEY 86] Y. \\IEYER
Les ondelettes
Cniversité de Paris ·Dauphine (Cl'rl'made), 198G
[:--IIC 35] 1. \\IICLET
At/éthude3 stnLetuTelles ponT 1(J. rer:urmu.i.;,w:nCt~ de.; forme"
Edi tion Eyrolles. 1985
[:--IO\\" S8) o.:--ro\\"G.-\\
Seyrnent(J.tlon ri "image pa.T C'l'Ol.;,w'fI,a hdral'('I/I(l({.l~ d(~,) régions
Thèse de doctorat université dl' P"ri:i ORS AY. 19.38
116

1j
[~IONT 87] A. ?\\'lONTANVERT
1
Fi1ta.rge et décomposition Je formes par manipulation des régions
in pmc 6e congrès RFIA. pp. 2:33-241. Amibes, 19Sï
l
1
[~IONT 91] A. ~dONTANVERT, P. ?\\'IEER. A. ROSE;{FELD
Hierachical Image Anulysis Vsing Inegular Tessclations
IEEE Trans. on Patt. Anal. NIach. [nteU., vol 13, no 4. April 1991
1
1
[ODD S3] C.,J. ODDY, A.J. R'{E
Segmenta.tion of SAR images using ,1 local similarity nde
Pa.ttern recognition lette'!'" 1. ~p. 44:3-449. 1983
[OGO'86] 1. O'GOrUv'IAN. G. l "VEIL
An approch toward segmeming cunwur line régions
in Proc IAP R·B, pp. 254-258. Paris, 1986
[OHL 78] R. OHLANDER, K. PRIeE anJ D. Il. RED DY
Picture segmentation Vsing a recursive region spliting method
Comp'/l.te'f· Gmphic:; l1:nd Irrwy!: pToce.i.;1:ng 8. pp. :313-3:33. 1978
[PAV '17] T. PAVLIDIS
Str'(f.dnra.l PrLtte'rn Recognitùm
Springer- Verlag, 1977
[PA.\\' 82] T. PAVLlDIS
Algorithms fO'r graphics and image pToce,,:;inq
Springer- Verlag, 1982
[PAV 90] T. P.\\VLlDIS. YUH-T.-\\Y L10\\V
InteoTatinl)' reo'ion oTowino' and ('(ke detection
o
'-'
0
0
0
.
· 0
IEEE Trans. on Patttm ArwlV.,is Machine Intell.. \\"0112, no 3, march 1990
[PEu 75] T.K. PEliKER, N. CHRISTI.-\\~
Cartographie data structures
The Ame'fican caTtogmphf..'t. '-01 2. no 1. pp. 55-69. 1975
[QuI 86] S. Ql~IG- yeN
Image Proccssing operations using CD l'epresentation
in Proc IAPR-S. pp. :320-:322. Paris. 1986
117

l:hbltlJgmpfue
[REE 90] T. R. REED . H. \\VECHSLER . }'I. WER\\L-\\.);
Texture segmentation USillg a diffu:oiiull regioll growing technique
Pa.ttern Recognition, vol :23. 110 9, pp. 95:3-900, 1990
[RE~1 8S] Y. REr..HüN
Stéréo'uislOn pa.r zone.., O'l/.til., d ,-;trl/.dl/.Tf~c'i ri·l/.'ft "y.,t(~rn.t expeTt.
Thèse de docteur-Ingenieur E:\\"ST Pali~. 1033
[ROG SS] D. F. ROGERS
Algorithme:> pU·l/.T info!J'f'a.phu~
\\1a~ GIL-\\.\\V-HILL, 1988
[ROS 66] .-\\.. ROSE::\\FELD . .J.L. PFALTZ
Sequelltial operations ill digital pin\\ll'c pr()l'C~,.;illg
./o·urnal of A CM 13, pp. 471-494. 0('[ 19GG
[SAI\\: S4a] :"1. SAI\\:AROVITC'H
PTo!JTamuwtion d'iscret(~
Hermann. 1984
[SAI\\: S~lb] ~1.S.-\\I\\:.-\\ROVITCH
Gmphes et Programnwtio'f/, hnr:(J:i'f'e
Hermann, 1984
[SA:"·1 SO] H. SA:v1ET
Region represcntatio!l : Quadr.n·(·s from Bounda.ry codes
comuniea.tions of the A CM. \\'01 :2:3. !lU :3. lllarch 1980
[S.-\\.:"1 8:2] H. SA:vIET
)Jcighbor finding techniques for images l'l'presentations
by quadtrees
Computer Graphies an !-rna..IJt: P'/"(lct.,.,iny 105. pp. :37-01. 198:2
[S.-\\:"1 83] H. SA:v1ET
A quadtree ~dedial Axis Transfol'm
Com'fTwnica.tions of the A CM. \\'ol :26. nu 9. Sept 1983
118

1
8LulHigrafJlne
1
[S.-\\.:\\I 8-1a] H. S.-\\.~vIET
Tile quadt.rel~ aud relntcd itin,11Tllil',I! dar'i c;rl'llt'tllres
i
Comp I/.ting ;;·I/.(,IIf.y.'. \\'01 1G. uu 2. .J lllll' 19:3-!
J
[S.-\\.:\\I84b] H. SAMET, A. ROSE\\TFELD. C.A. SHAFFER, H.E. \\VEBER
1
Ageographie information system llsing quadtn.'cs
Pa.ttern recognition, Vol l'l, 110 G. pp. G-1ï-G;jG. 198-1
J
[SA:\\I 85] H. S.-\\.:-VIET
1
A top-Down Quadtree Traversa! Algoridlln
IEEE Trans. un Patt. Anal. Nlu.ch. Intd!.. \\'01 P.-\\.:\\II·i. no L jan 1985
1
[SA\\I90] H. SA:\\IET
The Dr:,,'/.gn (j,nd A.1J.u.ly.<n:" uf Sll/J.tilll Datu. Strl/r:fll'l'l:.;
j
Addisou- Wesley, 1990
t
[S.-\\.)[ 89] .-\\.. SA.\\'FELIC
i
:\\Iar.ching Lomplex strw;turvs :
the Lydie- tree representa tiOll ."dll'l1h·
1
W/ild Sr;ùnt·i.fi:r: PI/.bl. Cil .. pp. G7-9:3. 19039
1
[SHA 80] LG. SHAPIRO. R.:\\,J, HAR.-\\.LIC'I\\
A spatial data structure
Geo·pToce.;sin L 1980
[SHE 85] J. SHEN, S. CASTAN
Un nnouvel algorithme de dèteetioll des contours
in Pme. Se Congres RFIA., pp. :201-:21:3, Grenoble. 1985
[SED 91] R. SEDGE\\VICI\\
AlgoTdhmes en La.ngu,l}f. C
ImerEditions, 1991
[SER 8:2] J, SERRA
Image a:nalY8i" and !V[u.thr~."wtiwl ;,l,t/uTp!wlul/Y
Academie Press. 1982
1
1
[T.-\\'P 89] J .R, T.-\\.PA:\\IO
Algorithme pyramidal de seglllclltariou d'images en régions
Swm.inaiTe" du LAMS URA U78 CNRS. peR. 1989
119
1
f

Bibliogmphie
'.
[TAP 92] J.R. TA.PAMO
Analyse multi-échelle ùes ima.ges pal' algoritluHcs pyramiùaux
in PTOe CARI92 (INRIA). Ynolludl" 12-20 oLt 1992 (article accepté).
[TOC 74] J. T. TOU, R. C. GO~ZALEZ
Pa.tte-T'n Recogmtion PnftC'ipk,
Addison-wesley. 1974
[ULL 80] J.D. ULLMAN
Pr-inciples of database sy;;krns
Computer Sciellce Press. 1080
[V:\\.1 32] P.D. V.-\\IDYA. L.G. SHAPIRO. IL:\\l. HARALICI":. G.J. ~\\'lI~DEX
Design and architectural Illlplicatiolls of a spatial Information system
IEEE transactions on comp'ld(~'''.,. \\"()l c-31. uo 10. ocr 1982
[\\VA:0I 90] 1. \\\\TANG. D.-C. HE
l
Texture cla.ssification usiug texture spennUll
j
Pa.ttern recognition. Vol 2:3. !lO S. pp. 005-010. 1990
~j
1j
['.NEB 89] R. B. \\VEBBER. ~vI. B. DILLEXCOCRT
1
Compressing quadtrees via COllllUOU ,;u!Jrl"l,'e lUcrging
Pa.ttent Recugnition Lette-r.i 9, pp. 193-200. 1989
1j
l
[\\VIL 92] S. S. WILSON
1
Theory of Matrix Morphology
1
j
IEEE Trans. on Patt. Ana.l. Ma.ch. Irdell.. \\'01 14. no 6, 1992
1
1
[Y.-\\:.'J 86] J.Y. YANG. 1\\. LIU
A segmentation algorithm of polyhl.'dral scène Ilsing three
dimentional informa.tioll
in Proc IAP R-S, pp. 268-270. Paris. 1986
[YOX 90] \\V. 1. YOCNG, U. 1. SA::;G
On the color image segmeuration .-\\lgorithlll Based on the thresholding
and the fuzzy c-means tL'c1miqlll's
Pa.ttern recognition. Vol 21. lW 9. pp. 033-9;:)2. 1990
120

L
RéSU111é:
:\\'OllS étudio11:-i dam; cc tl<l.\\ï\\il Iii llluclé'lisarioll pal' codage quaternaire des
formes se trouvant sur l'image d'ullt: sn"Ile.
Un noU\\'eau modèle de reprèsentation syntaxillue des images est proposé grâce à un
alphabet de quatre lettres. Nous préSl'ntoll::> l.'ll:mitc des aigoritlllnes de détermination des
\\'oisins d'un noeud dans un arbre quaternaire à l'aide d\\1Il systl'llle de réécriture.
Nous avons grâce à ce modèle, étudié la tnmsfol'lnatio11 pyramidale de Haar, ce qui nous
n permis cl'établir un lien entre cette transformation et la structure d'arbre quaternaire.
::\\ous présentons des applicatiolls dl' l.'l'ttt' trall::>fonnatÎon eu compression d'images
('t en filtrage dynamique. Ccci 110\\lS il jh.'l'llllS dL' proposer llll nlgoritbme pyramidal de
segmenta tion cl ïmages en régiolls.
::\\ous prOpU:-iOllS à partir dl.' ('L'f rv ~l'~l1wj1f;, f lull IiI ('l)lll'l 'j)[ 1011 d' \\lue base d'ima.ges
segment.ées,
:Ylots clés: Segmelltatio11 cl'images. nl'('olHlais:-iilllCe des fOl'lll('S, Transformation pyrami-
dale. 13asl' dl' Ham. Ar1lI"l:' q\\lareI11"irc. [b"l' d'ila'l'l;l':-' :-'l'~llll'l.rl·'('~, B.l.'gleS de rél'criture,
Abstract : We are studied in this thesis t!Je lllodelisation by lluadcode of the patterns
lying in the image of the scene.
A ne\\v syntactic representatioIl 11l0dd i,.., proposed rllrough a.n a.lphabet of four letters.
We then present the algorithms of c1ctcl'lniwlrioll of neighbors of n. node in quadtree \\\\"ith
the llelp of rewriting rules.
\\Ve study, \\Vith this mode!. the Haar pyrillllid,d [l(lll.~,;ful'1llilrioll \\vhich permits us ta
l'stablish the bond bet",een this traIlsfol111arioll ,\\11(1 rhl' quadtrce structure.
Vv'(' present applications of this tran:-ifornwrioll iu image compression and clynamint!
filtering. In addition this allows us tu givl' au pyramidal ,11gorir11111 of image segmentation
,
.
III reglOll:->.
\\Ve then propose a d.esign of seglllcnr cd il1lil \\LL' hase,
Keywords : Image Segmentation. Pattelll B.l'(·uguitioll. PyrHmidal Trallsformation. Haar
Base. Segmemed Image Base. Quadtrel'. Rl'wririug B.uk:;.

~>i

\\.
[YC 91] X. \\T, Y.-J. JCHA. B. \\TA:\\
A IlCW Algoritlllll for text.Ul'L' SL'~l1h'll[<l[ioll ba::icd Oll l'dge detection
i
Pa.ttern recognition, Vol :24, LW 1L pp. 110;)-111:2. 1991

1
j
[ZAG 90] ?\\I.R. ZAGLIA. :\\1. :'1. CECCHI
La détection des régions lo~iqlH~S pnr la cOlllclll'
f
AFCET/INTERFACES. lW SS. [lp. 1:2-:2:2. Fc\\' 1000
f
l
,
1
1
~
f
1
1
1
1
j
1
1
!
l
1
1
1f
1
121