École Généraliste

Université
Institut Fresnel d’Ingénieurs de
d’Aix-Marseille III
Marseille

Rapport de DEA
présenté par

Julien Marot

DEA Optique Image et Signal

Option traitement d’images
Caractérisation d’objets dans les images par des
méthodes haute résolution.

soutenu le 2 juillet 2004

DEA Optique, Image et Signal

Option Traitement d’Images

Sous la direction de : M. Stéphane Derrode , M. Salah Bourennane

Année 2003/2004
Groupe Signaux Multidimensionnels
 Résumé

Ce stage de DEA mené au sein de l’équipe "Groupe Signaux Multidimensionnels" de

l’institut Fresnel m’a permis d’utiliser des techniques de traitement du signal appliquées au
traitement d’images. L’objectif du stage était de montrer qu’il est possible de transposer un
problème de traitement d’images à un problème de traitement d’antenne, et de mettre en
valeur les apports des méthodes issues de ce domaine du traitement du signal.
La mise en oeuvre de méthodes dites "Haute Résolution" appliquées à des modèles de signaux
issus du traitement d’antenne a débouché sur la création d’un outil appelé "Haute Résolution
et Schéma de Propagation" (HRSP). Mon but était de montrer qu’un ensemble cohérent de
méthodes fondées sur des techniques de traitement d’antenne permet de détecter et caractéri-
ser des droites dans une image. Les procédures qui constituent cet outil ont été étudiées d’un
point de vue théorique et par l’expérience. HRSP a été appliqué à des images en niveaux de
gris, à la détection d’objets isolés dans des images, et à des images couleur.

Mots clés : Traitement du signal, traitement d’images, schéma de propagation, traitement

d’antenne, méthode Haute Résolution, analyse spectrale paramétrique.
 Abstract

This project lead within the team "Multidimensionnal Signals Group" of the Fresnel ins-
titute allowed me to create signal processing techniques applied to image processing. The
purpose of the project was to show that it is possible to transpose an image processing pro-
blem to an array processing problem, and to emphasize on the contributions of the methods
coming from this field of signal processing.
The application of "Super Resolution" methods applied to signal models coming from array
processing resulted on a coherent set of procedures. My goal with this set of methods called
"Super Resolution by Propagation Scheme" was to show that a coherent group of methods
based on array processing techniques is able to detect and characterize straight lines in an
image. The procedures that form this tool were studied from a theoretical and experimental
point of view. This set of methods was applied to grey level images, to the detection of isolated
objects, and to color images.

Key words : Signal processing, image processing, propagation scheme, array processing,
Super Resolution method, parametric spectral analysis.
 Remerciements

Je tiens à remercier toutes les personnes qui ont contribué à la réussite de ce stage.
Tout d’abord les membres de l’équipe Groupe Signaux Multidimensionnels, pour leur aide
au quotidien tant au niveau théorique que pour résoudre des soucis pratiques. Dans l’équipe
GSM travaillent notamment M. Jean-Michel Gaucel, dont le travail de thèse consiste en la
caractérisation de signaux par des méthodes algébriques multilinéaires, M. Cyril Carincotte,
qui réalise une thèse portant sur les méthodes de traitement d’images par des modèles de
Markov, M. Damien Muti, dont le sujet de thèse porte sur l’estimation multidimensionnelle
basée sur la décomposition tensorielle.
J’exprime avec insistance ma gratitude à mes responsables de stage M. Salah Bourennane et M.
Stéphane Derrode, ainsi qu’à M. Thierry Gaidon pour leur disponibilité. Leur investissement
personnel et leur intérêt pour le sujet de mon stage m’a permis de choisir judicieusement mes
voies de recherche.
Je dédie ce rapport
à toute ma famille.
 Table des matières

Résumé i

Abstract ii

Remerciements iii

Introduction 1

1 Les méthodes haute résolution du traitement d’antenne, application au trai-

tement d’images 3
1.1 Le Traitement d’antenne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Le modèle de signal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Application au traitement d’images, obtention des signaux . . . . . . . . . . . 5
1.2.1 Analogies entre le modèle classique employé en traitement d’antenne et
celui employé dans le cadre du traitement d’images . . . . . . . . . . . 5
1.2.2 Les signaux reçus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Les méthodes haute résolution du traitement d’antenne . . . . . . . . . . . . . 8
1.3.1 Définition générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.2 La méthode MUSIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 La méthode "Haute Résolution par Schéma de Propagation" (HRSP) . . . . . 10
1.4.1 Estimation des orientations : schéma de propagation à vitesse constante 11
1.4.2 Estimation du décalage des lignes (offsets x0 ) . . . . . . . . . . . . . . 14
1.4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5 Choix des paramètres, premières expériences . . . . . . . . . . . . . . . . . . . 18
1.5.1 Choix des paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5.2 Première mise en oeuvre des méthodes . . . . . . . . . . . . . . . . . . 20
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
TABLE DES MATIÈRES vi

2 Application de "Haute Résolution et Schéma de Propagation" à divers cas

pratiques 23
2.1 Les aptitudes de la méthode HRSP face à des cas difficiles . . . . . . . . . . . 23
2.1.1 Le cas des droites parallèles . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.2 Une image bruitée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.3 Cas des droites ne traversant qu’une partie de l’image . . . . . . . . . 26
2.1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2 Etude quantitative des performances de l’algorithme HRSP . . . . . . . . . . 31
2.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.2 Cas particuliers et temps de calcul des algorithmes . . . . . . . . . . . 31
2.2.3 Série de tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.4 Etude quantitative : bilan . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3 Mise en oeuvre de l’algorithme : application aux images en niveaux de gris . . 36
2.3.1 Le modèle utilisé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3.3 Images réelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3.4 Les images en niveaux de gris : un bilan . . . . . . . . . . . . . . . . . 41
2.4 Détection de contours d’objets . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.2 Détection de segments de droites dans des images . . . . . . . . . . . . 41
2.4.3 Détection de contours d’objets . . . . . . . . . . . . . . . . . . . . . . 42
2.4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.5 Adaptation de l’algorithme HRSP à des images couleur . . . . . . . . . . . . . 44
2.5.1 Quelques précisions théoriques . . . . . . . . . . . . . . . . . . . . . . 44
2.5.2 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Conclusion et perspectives 48

A Titre de l’annexe 1 49
A.1 Organigramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
A.2 Glossaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

B Méthodes ESPRIT, extension de la transformée de Hough et Modified Ba-

ckward Forward Linear Prediction 51
B.1 La méthode ESPRIT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
B.2 Les méthodes relatives à la détermination des offsets . . . . . . . . . . . . . . 52
B.2.1 Extension de la transformée de Hough . . . . . . . . . . . . . . . . . . 52
TABLE DES MATIÈRES vii

B.2.2 La méthode MFBLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Liste des figures 57

Bibliographie 59
 Introduction

Contexte scientifique et cadre théorique

Le sujet qui m’a été confié s’inscrit dans un vaste cadre : le traitement des signaux multidi-
mensionnels. Ce stage est mené au sein de l’équipe "Groupe signaux multidimensionnels" dont
le thème de recherche général est le traitement de signal multidimensionnel par des méthodes
de traitement du signal. Les sujets traités par cette équipe sont notamment la caractérisation
de signaux par des méthodes algébriques multilinéaires, les méthodes de traitement d’image
par des modèles de Markov, l’estimation multidimensionnelle basée sur la décomposition ten-
sorielle.
Ce thème qui concerne les méthodes de traitement du signal est en accord avec l’orienta-
tion professionnelle que j’ai choisie lors de ma troisième année de formation d’ingénieur ; mon
projet de fin d’études notamment consistait à traiter des signaux d’electrocardiogramme en
développeant un algorithme de type "ForWard", combinaison d’un traitement par filtrage de
Wiener après transformée de Fourier et après transformée en ondelettes.
L’un des grands domaines du traitement du signal est le traitement d’antenne. Les méthodes
de traitement d’antenne ont pour but de déterminer les valeurs de paramètres associés à
des sources d’émission. C’est par le traitement du signal reçu par une antenne constituée
de plusieurs capteurs que l’on estime le nombre de sources qui émettent, leurs coordonnées
dans l’espace, leurs fréquences d’émission. Historiquement ces méthodes avaient une résolu-
tion spatiale limitée par les composants physiques. Des méthodes, dites "Haute Résolution"
ont permis d’améliorer la résolution spatiale en localisation [6, 8].

Démarche adoptée et organisation du rapport

L’objectif de ce stage est de développer et d’adapter des méthodes haute résolution en

traitement d’antenne dans le cadre de la détection de points quasiment alignés dans une image.
Il est possible d’appliquer des méthodes de traitement du signal au traitement d’images : la
transposition d’un domaine à l’autre peut être assimilée à un problème de traitement d’antenne
lorsque l’on applique un formalisme particulier à la représentation d’une image. Le formalisme
suivant est retenu : on associe à chacune des lignes d’une image un capteur, l’ensemble des
capteurs formant une antenne. Le contenu de chacune des lignes est transcrit en un signal au
niveau du capteur correspondant par ce que l’on nomme un "schéma de propagation". Une
fois cette transcription réalisée on applique des méthodes d’analyse spectrale paramétrique,
c’est-à-dire des méthodes aboutissant à la détermination d’un nombre connu de fréquences
INTRODUCTION 2

présentes dans un signal, afin de retrouver les caractéristiques des objets présents dans l’image.
L’objectif que l’on s’est fixé est donc de développer la méthode " Haute Résolution et Schéma
de Propagation" (HRSP), de valider la méthode imaginée en comparant ses performances à
celles d’une méthode déjà existante, d’adapter la méthode à des conditions expérimentales
diverses.
Ce rapport est agencé en deux chapitres. Le premier est axé sur la théorie mais contient
quelques résultats expérimentaux ; le second concerne la mise en oeuvre de la méthode HRSP
tout en laissant la place aux commentaires qui donnent le principe des traitements appliqués
et permettent de comprendre les résultats obtenus.
 1
CHAPITRE

Les méthodes haute

résolution du traitement
d’antenne, application au
traitement d’images

Introduction

Le traitement d’antenne est employé dans divers domaines tels que l’acoustique, la sis-
mique, pour caractériser des sources d’émission d’ondes. Il a donné lieu à des méthodes qui
ont connu des améliorations constantes, et qui donnent de bons résultats. Parmi ces méthodes,
celles dites "à haute résolution" fournissent de très bons résultats, même dans des cas difficiles
tels que celui des sources corrélées -reliées par un décalage temporel par exemple-. Elles sont
apparues pour remplacer des méthodes classiques qui sont limitées par les caractéristiques non
idéales du diagramme en puissance d’une antenne. La méthode dénommée MUSIC (MUltiple
SIgnal Characterization) [8] est la première d’entre elles.
L’objectif de ce chapitre est de transposer le problème de la caractérisation de droites dans
une image au problème du traitement d’antenne, et de proposer une procédure qui emploie
des méthodes Haute Résolution qui sont d’usage en traitement d’antenne.
On décrira un modèle de problème de traitement d’antenne, on transposera ce modèle au
traitement d’images. On montrera comment une droite dans une image peut être assimilée à
un front d’onde figé, dont on peut simuler le déplacement à une vitesse qui peut être constante
ou variable. Des signaux sont donc obtenus au niveau des capteurs de l’antenne par ce que
l’on appelle un "schéma de propagation".
Une fois cette transposition réalisée, on s’intéressera aux méthodes qui permettent d’extraire
des signaux reçus les valeurs des paramètres que l’on désire estimer. Les méthodes Haute
Résolution seront définies et introduites au travers de la méthode MUSIC. Cette méthode
a inspiré plusieurs autres procédés fondés sur la séparation dans le signal reçu par l’antenne
d’un "sous-espace signal" et d’un "sous-espace bruit". On emploiera ce type de méthodes pour
créer l’ensemble "Haute Résolution et Schéma de Propagation" (HRSP).
L’objectif est de rechercher et caractériser les droites présentes dans l’image. Une droite dans
une image peut être caractérisée par deux paramètres : sa "pente" (nommée aussi angle
ou orientation) et son "offset". Deux étapes composent donc HRSP : la détermination des
pentes des droites par schéma de propagation à vitesse constante et l’estimation des offsets
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 4

des droites par schéma de propagation à vitesse variable. En présentant HRSP on montrera
qu’un ensemble cohérent de méthodes liées au traitement d’antenne permet de caractériser
entièrement des droites dans une image. On présentera aussi la méthode dite de "l’extension
de la transformée de Hough" qui permet également d’estimer les offsets des droites, une fois
leur orientation connue. Celle-ci constitue en effet une référence à laquelle le schéma de pro-
pagation à vitesse variable peut être comparé.
Une première série d’expériences permettra de fixer les principaux paramètres intervenant
dans les algorithmes et de donner quelques pistes à l’extension de la méthode HRSP.

1.1 Le Traitement d’antenne

Dans cette section on rappelle les éléments qui constituent un problème de traitement
d’antenne et on présente le modèle de signal adopté.

1.1.1 Définitions

L’objectif du traitement d’antenne est de déterminer les caractéristiques (orientation, puis-

sance) de sources d’émission. Le signal dont on fait l’acquisition dépend de l’antenne, du
milieu, et des sources :
– L’antenne de réception est constituée de N capteurs identiques alignés qui servent à la
réception de signaux émis par des émetteurs indépendants.
– Le milieu contient des sources d’onde, situées assez loin de l’antenne pour que les ondes
reçues soient planes. Il est supposé linéaire, homogène et isotrope.
– Le nombre de sources est inférieur au nombre de capteurs.
Ces éléments sont schématisés sur la figure 1.1.

Figure 1.1 — Modèle du dispositif en traitement d’antenne

CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 5

1.1.2 Le modèle de signal

L’antenne est constituée de N capteurs indicés par l = 0...N − 1.

En fixant à zéro la phase du signal reçu par le premier capteur (d’indice zéro) et en no-
tant s l’amplitude du signal émis par la source, le signal reçu par le premier capteur est z0 = s.

Pour une source placée en un azimut θ donné le délai de réception td de l’onde plane
correspondante entre deux capteurs est : td = a ∗ sin(θ)/c où a est la distance intercapteur, c
la célérité des ondes. Cette durée correspond à un déphasage de ϕ = 2 ∗ π ∗ f ∗ td où f est la
fréquence de rayonnement de la source.
Un capteur d’indice l reçoit le signal :

zl = [Link](jlϕ) pour l = 0...N − 1. (1.1)

Lorsque d sources sont présentes et que l’on prend en compte un bruit additif le signal
reçu prend la forme vectorielle suivante :

    
1 1 ... 1 s1 b0
 exp(jϕ 1 ) exp(jϕ 2) ... exp(jϕd )   s2   b1 
Z=  + 
 ... ... ... ...   ...   ... 
exp(j(N − 1) ∗ ϕ1 ) exp(j(N − 1) ∗ ϕ2 ) ... exp(j(N − 1) ∗ ϕd ) sd bN −1
(1.2)
En définissant al (ϕk ) = exp(jl ∗ ϕk ), on a alors, sous une forme plus synthétique :

zl = Σdk=1 al (ϕk ).sk + nl pour l = 0...N − 1. (1.3)

Cela constitue un modèle du signal reçu par une antenne de N capteurs pour d sources.
On peut représenter les signaux reçus par l’ensemble des capteurs sous forme vectorielle :

z = A(Φ).s + n (1.4)

1.2 Application au traitement d’images, obtention des signaux

1.2.1 Analogies entre le modèle classique employé en traitement d’antenne

et celui employé dans le cadre du traitement d’images

Dans le cadre du traitement d’images la figure 1.1 évoque une image contenant une droite,
et dont l’un des côtés est constituée par l’antenne. Cette droite peut être vue comme un front
d’onde figé. Le problème de caractérisation de cette droite dans une image peut donc être
résolu par une méthode de traitement d’antenne, il suffit de simuler le mode de propagation
du front d’onde correspondant à cette droite [1, 5, 9]. La figure 1.2 illustre le problème de la
détection de droites dans une image et représente les paramètres qui caractérisent une droite.
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 6

Ces paramètres sont l’orientation θ et l’offset x0 (abscisse de l’intersection de la droite avec

le côté adjacent au premier capteur de l’antenne).

Figure 1.2 — Droite dans une image

[Link] Le formalisme du traitement d’antenne adapté au traitement d’images

Un côté de l’image est assimilé à une rangée de capteurs.

Les N lignes de l’image peuvent être considérées comme une antenne de N capteurs ou bien
une série d’antennes décalées de M capteurs, avec M inférieur à N. Dans ce cas cela permet
d’obtenir plusieurs réalisations d’un signal : une réalisation donnée correspond à une position
de sous-antenne.
Une méthode proposée dans [9] consiste à utiliser successivement plusieurs positions d’antenne
(comme le montre la figure 1.3) et à combiner les résultats obtenus. Cela permet de traiter
des cas difficiles tels que celui d’une droite horizontale.

[Link] Propagation selon les lignes de l’image

En traitement d’antenne classique le milieu est isotrope, la direction de propagation des

ondes peut être quelconque.
Dans le cas des images binaires un formalisme légèrement modifié permet d’associer à chacun
des capteurs une ligne donnée dans l’image.
Les signaux ont une amplitude égale à 1. Les ondes émises par les pixels à 1 ne peuvent se
propager que sur la ligne où se trouve le pixel et dans le sens des x ≤ 0, comme le montre la
figure 1.4.
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 7

Figure 1.3 — Choix de la position d’antenne

Remarque : Cette convention exige pour les images binaires de droites noires sur fond blanc
une inversion des valeurs de pixel : Un logiciel de traitement classique donne à de telles images
la valeur 1 pour les pixels de fond et 0 pour les pixels des droites. Le prétraitement nécessaire
consiste à fixer à 1 les valeurs des pixels qui sont nulles et à 0 toutes les autres. Les pixels de
valeur 1 sont appelés pixels "utiles" de l’image (constituant les droites et éventuellement des
pixels supplémentaires correspondant à du "bruit").
De plus, la vitesse de propagation peut être considérée comme constante (µ constante) ou
variable (τ variable) selon les lignes (schémas de propagation à vitesse constante ou variable
respectivement). Ces deux possibilités seront utilisées par la suite, pour la recherche des angles,
puis des offsets.

1.2.2 Les signaux reçus

Le côté de l’image est assimilé à une antenne de réception. A une ligne correspond un
capteur de l’antenne. Dans un schéma de propagation à µ constant chaque pixel de l’image
dans une ligne contribue à un signal reçu au niveau d’un récepteur situé en face de cette
ligne. Les ondes issues des pixels d’une ligne ne se propagent que sur cette ligne. Si la ligne l
contient p pixels qui ne sont pas à 0 le récepteur correspondant à la ligne l recevra le signal :
zl = Σpi=1 exp(−jµqi ). On a noté q la distance de propagation entre un pixel situé sur la ligne
l et le capteur correspondant. Si ce pixel est situé sur une droite de paramètres θ et x0 donnés
sur la figure 1.2 cette distance de propagation vaut :

ql = x0 − ltan(θ), l = 0...N − 1.

S’il existe une seule droite dans l’image chaque récepteur de l’antenne virtuelle reçoit :
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 8

Figure 1.4 — Modèle de propagation

zl = exp(−jµx0 ).exp(jµltan(θ)) pour l = 0...N − 1. (1.5)

Dans un cas plus général s’il existe d lignes droites et des pixels de bruit le signal reçu
devient [2, 5] :

zl = Σdk=1 exp(−jµx0k ).exp(jµltan(θk )) + nl pour l = 0...N − 1. (1.6)

Définissons al (θk ) = exp(jµltan(θk )), sk = exp(−jµx0k ). On a alors :

zl = Σdk=1 al (θk ).sk + nl . (1.7)

Sous forme vectorielle :

z = A(Θ).s + n (1.8)

Cette modélisation nous rapproche de la forme de signal obtenue en 1.1.2. Le modèle de

signal à analyser étant posé, on peut alors s’intéresser aux méthodes de traitement qui per-
mettent d’extraire de ces signaux les paramètres caractéristiques des sources, plus précisément
ici les angles et les offsets.

1.3 Les méthodes haute résolution du traitement d’antenne

1.3.1 Définition générale

Les méthodes à haute résolution du traitement d’antenne sont appliquées aux problèmes
de localisation de sources émettant de l’énergie dans un milieu de propagation à partir d’ob-
servations mesurées sur une antenne. A l’origine le qualificatif "haute résolution" a été donné
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 9

aux méthodes de traitement d’antenne qui ont une meilleure résolution que des techniques
plus conventionnelles (formation de voies).

1.3.2 La méthode MUSIC

[Link] Principe

Le goniomètre (MUSIC, MUltiple SIgnal Characterization) est le premier traitement

HR [6, 8]. Il exploite les signaux reçus par les N capteurs d’une antenne. Les paramètres
intervenant sont les suivants : l’antenne comporte N capteurs qui reçoivent les signaux émis
par d sources indépendantes et un bruit n. L’observation est constituée des N signaux reçus.
Ces signaux peuvent s’écrire sous la forme vectorielle : x = A(Θ).s + n

Afin de retrouver les paramètres du problème on utilise la matrice interspectrale des

signaux reçus, qui est donnée par le modèle physique suivant :
Γ = A(Θ)Γs AH (Θ) + σb2 I

Θ désigne l’ensemble des directions d’arrivée, ”H” signifie transposé conjugué et I est la
matrice identité.
Γs est la matrice interspectrale des signaux émis par les sources, σb2 la densité spectrale du
bruit seul, σb2 I la matrice interspectrale du bruit.

En pratique la matrice interspectrale est estimée à partir de la suite de vecteurs indépen-

dants {xp }p=1,P , et peut s’exprimer selon le modèle matriciel suivant :

1 P H
Γ̂ = P Σp=1 xp xp

La matrice interspectrale peut se décomposer de la sorte :

   H 
H

Λs 0 Us
Γ̂ = U ΛU = Us Ub . .
0 Λb UbH

Cela permet de décomposer l’ensemble des vecteurs propres de la matrice interspectrale en

un sous-espace signal et un sous-espace bruit. Les vecteurs colonne de Us recouvrent le même
espace que les vecteurs colonne de A(Θ). On note cette relation : span(A(Θ)) = span(Us ). Une
matrice interspectrale étant hermitienne ses vecteurs sont orthogonaux entre eux. Notamment
les vecteurs de l’espace signal sont orthogonaux aux vecteurs de l’espace bruit. On en déduit :
uH H
i uj = 0 et ai (θ) uj = 0, pour tout i dans {1; d} et tout j dans {d + 1; N }.
La résolution du problème comprend donc deux étapes : la recherche de la dimension d de
l’espace signal (le nombre de sources), puis l’estimation des directions d’arrivée des sources.
Le nombre de sources est estimé par le nombre de valeurs propres dominantes de la matrice
interspectrale. Les orientations sont déterminées par la méthode suivante : Lorsque le modèle
de propagation est connu on connaît la forme des vecteurs a(θ). Dans le modèle donné en 1.2
ils prennent la forme exp(jθk ) où k renvoie à la source considérée. Il est possible de tester les
valeurs du produit scalaire a(θ)H uj . En pratique on trace en fonction de toutes les valeurs
possibles de θ la fonction
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 10

1
F (θ) = (1.9)
ΣN H
n=d+1 |a(θ) un |
2

Les maxima de cette fonction ont pour antécédents les valeurs de θ correspondant aux d
sources (figure 1.5).

29 Music
x 10
14

12

10

Fonction de localisation
8

0
−20 −15 −10 −5 0 5 10 15 20
Azimut(°)

Figure 1.5 — Pseudospectre de Music

[Link] Critique du goniomètre

Dans quelques cas particuliers cette méthode ne peut pas être utilisée. En effet la méthode
suppose que les sources n’ont pas la même puissance. Autrement le sous-espace source serait
de dimension 1, et le nombre de sources serait alors impossible à déterminer car le rang de la
matrice interspectrale des signaux serait égal à un.
La seconde difficulté provient de la connaissance de la variété d’antenne : la projection des
vecteurs directionnels sur l’espace bruit ne peut être réalisée que si chacune des composantes
du vecteur directionnel est connue. On doit donc connaître le délai correspondant à chacun
des capteurs. Il existe des méthodes qui sont moins dépendantes de la structure de l’antenne.
La méthode ESPRIT est fondée sur une antenne en deux parties identiques translatées -seule
la valeur de cette translation doit être connue-.

1.4 La méthode "Haute Résolution par Schéma de Propaga-

tion" (HRSP)

La procédure HRSP se décompose en deux étapes. On estime dans un premier temps

les orientations des droites grâce à un schéma de propagation à vitesse constante [2, 5, 9].
Ces valeurs estimées sont utilisées ensuite pour déterminer la valeur des offsets des droites.
C’est un schéma de propagation dit à "vitesse variable" qui est alors utilisé pour générer les
signaux dans ce cas-là ; on présente également la méthode d’estimation des offsets dite de
l’"extension de la transformée de Hough" [9] pour comparaison.

La méthode HRSP peut être résumée par l’organigramme suivant :

CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 11

Estimation des orientations : Schéma de propagation à vitesse constante

Obtention des signaux
↓
Calcul d’une matrice interspectrale
↓
Estimation du nombre de droites
↓
Méthode TLS-ESPRIT qui aboutit aux valeurs d’orientation.

Estimation des offsets : Schéma de propagation à vitesse variable

Obtention des signaux
↓
Pour chaque valeur d’angle : Application de la méthode Modified Forward Backward Linear
Prediction (MFBLP) qui aboutit aux valeurs d’offsets x0 .

1.4.1 Estimation des orientations : schéma de propagation à vitesse

constante

[Link] Obtention des signaux

Les signaux employés pour la détermination des orientations sont obtenus selon un
schéma de propagation à vitesse constante, tel que cela a été décrit en 1.2.2. On rappelle que
ces signaux sont, sous forme vectorielle :

z = A(Θ).s + n (1.10)

Ces signaux sont traités par la méthode ESPRIT afin d’aboutir à la valeur des orientations
des droites. Le principe de la méthode est donné ci-dessous, un organigramme fourni en annexe
donne de façon synthétique les étapes de la méthode.

[Link] La méthode ESPRIT

Lissage spatial et obtention de la matrice interspectrale

Lissage spatial L’estimation de la matrice interspectrale requiert la connaissance de P

vecteurs de réalisation du signal z. A partir du vecteur-signal z on construit P vecteurs-signal
de longueur M , avec d < M < N − d + 1. Un vecteur-signal correspond à une position
de sous-antenne. d représente ici le nombre de droites contenues dans l’image. L’intérêt de
l’utilisation de ces diverses positions d’antenne est de simuler des observations à des temps ti
réguliers sur une antenne fictive de M capteurs. On nomme la réalisation d’indice i du signal
zi . La réalisation d’indice i du bruit est ni .

zi = [zi , ..., zi+M −1 ]T , ni = [ni , ..., ni+M −1 ]T pour i = 0...P − 1

On forme une matrice d’observation Z, de dimension M×P, avec P=N+1-M.

CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 12

En une écriture synthétique : ZP = A(Θ).SP + NP où une colonne de la matrice A(Θ)

correspond à une ligne droite donnée dans l’image et une ligne de A(Θ) correspond à un
élément de la fenêtre de mesure (un capteur).
Le lissage spatial est une technique de décorrélation [4] pour éviter une dégradation des
performances des étapes ultérieures. Cette dégradation peut se produire lorsque la corrélation
entre les sources est importante. Pour réaliser le lissage
√ spatial il importe de choisir convena-
blement M et P. En pratique M est choisi proche de N , N étant la taille d’un côté de l’image.

Décomposition de la matrice interspectrale La matrice interspectrale est définie

d’après les paramètres physiques du problème par :

Rzz = lim (1/P )ZP ZPH = lim (1/P )ΣPp=1 zp .zpH = A(Θ)Rss A(Θ)H + σ 2 .I
p→∞ p→∞

La décomposition en valeurs propres de Rzz peut mettre en valeur une distinction entre
le sous-espace signal et le sous-espace bruit :
Rzz = ΣM H H H
i=1 λi ei .ei = Es Λs Es + En Λn En

Il existe un lien entre Es et A(Θ), qui peut être exploité si on connaît le nombre de droites
d.
Rzz et A(Θ)Rss A(Θ)H ont mêmes valeurs propres et spanEs = spanA(Θ). Le sous-espace
associé à Es est donc appelé sous-espace signal. L’étude de A(Θ) peut donc se ramener à celle
de Es . Il est donc crucial d’obtenir une bonne estimation de la dimension d du sous-espace
signal -nombre de colonnes de Es -, c’est-à-dire concrètement le nombre de droites dans l’image.
Cette information est considérée comme étant connue a priori, d’où le caractère paramétrique
de la méthode.
En notant pour l’estimée de la matrice de covariance Rˆzz = Ê Λ̂Ê H , l’estimée Ês de Es est
obtenue en prenant les d premières colonnes de Ê. Les colonnes de cette matrice recouvrent
l’ensemble des parties signal utile et bruit.

Estimation du nombre de droites

L’ensemble des valeurs propres de la matrice interspectrale permettent de déterminer une

estimation du nombre de sources. Les d valeurs propres de plus grande valeur correspondent
au sous-espace signal, les autres au sous-espace bruit, qui est orthogonal au sous-espace signal.
L’estimé du nombre de sources est l’argument minimum de la fonction MDL (minimum
description length) suivante :

QM 1
M −k
i=k+1 λi k
M DL(k) = −log{ 1 M
}(M −k)P + (2M − k)log(P )
Σ
M −k i=k+1 λ i 2

Les valeurs propres étant ordonnées, cette quantité est fonction de la différence entre une
valeur propre donnée de la matrice interspectrale et la valeur propre suivante.
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 13

Méthode TLS-ESPRIT

On a montré en [Link] qu’il est possible d’étudier la matrice directionnelle par le biais
de l’estimée de la matrice des vecteurs propres associés à l’espace signal Ês . Reste à savoir
comment exploiter Ês pour aboutir à la valeur des angles des droites.
ESPRIT, pour Estimation of Signal Parameters via Rotational Invariance Techniques, est
appliquée dans le cas particulier de d’un réseau d’antennes constitué de deux sous-antennes
identiques [2]. TLS-ESPRIT en est une version étendue efficace. Le principe de l’algorithme
TLS-ESPRIT repose sur la séparation de l’antenne en deux sous-antennes. Les deux sous-
antennes sont décalées de ∆. Les directions d’arrivée des signaux ne dépendent que du délai de
propagation entre les deux sous-antennes, et pas du délai de propagation entre deux capteurs
de l’antenne. Bien qu’à l’origine, dans l’algorithme ESPRIT, aucune géométrie spécifique n’est
supposée pour chacune des sous-antennes [8], on se place dans le cas où celles-ci sont identiques
et périodiques.
Connaissant l’écart δ entre deux capteurs d’une antenne on peut poser ∆ = δ. Cela
permet de créer artificiellement deux antennes de taille M-1 qui se superposent partiellement,
tout en conservant le formalisme du traitement d’antenne adapté au traitement d’image. On
ne pourrait pas par exemple espacer les deux sous-antennes d’une distance inférieure à celle
existant entre deux lignes.

On définit Ê1 comme la sous matrice de Ês formée par les lignes 1 à M-1, et Ê2 comme
la sous matrice de Ês formée par les lignes 2 à M. On choisit comme déplacement ∆ = 1. Il
existe un opérateur unitaire qui relie les matrices directionnelles associées à chacune des deux
sous-antennes. C’est cette relation qui est exploitée dans la méthode TLS-ESPRIT. Formons
la décomposition en valeurs propres de la matrice 2d × 2d :

Ê1H
 
H
 
F ΛF = Ê1 Ê2 .
Ê2H

La matrice F est partitionnée en blocs de sous-matrices d × d,

F11 F12
F =[ ]
F21 F22

−1
En posant λk , k = 1, 2...d les valeurs propres de la matrice −F12 F22 , les angles sont
donnés par [9] :
1 λk
θ̂k = tan−1 [ Im(ln( ))]
(µ∆) |λk |

On a donc déterminé la valeur de d (nombre de droites) et les valeurs θk (orientation des

droites).

[Link] Complexité du schéma de propagation à vitesse constante

On note Np le nombre de pixels utiles dans l’image. On rappelle que P est le nombre et M
la longueur des vecteurs-signal, d le nombre de droites à détecter. La complexité du schéma
de propagation à vitesse constante est donnée par :
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 14

– O(Np ) pour créer le signal z ;

– O(P ∗ M 2 ) pour calculer Rzz ;
– O(M 2 ∗ d) pour la décomposition en valeurs propres.
√
En prenant par exemple M = N la complexité globale en est : O(Np + N ∗ (N + d)).
En considérant que le nombre de droites est faible devant la taille de l’image, la complexité
devient : O(Np + N 2 ).

1.4.2 Estimation du décalage des lignes (offsets x0 )

L’objectif de cette partie est de présenter deux méthodes qui aboutissent à l’estimation des
offsets des droites [3], lorsque leur valeur d’orientation est connue. Une méthode est celle dite
de "l’extension de la transformée de Hough". Afin de se placer dans le cadre de l’application
des principes du traitement d’antenne au traitement d’image, on désire établir un procédé
d’obtention des signaux par un schéma de propagation. On se penchera sur les avantages
qu’apporte ce procédé.

[Link] La méthode dite de l’extension de la transformée de Hough

Principe de la méthode L’image que l’on considère est munie d’un système de coordon-
nées polaires θ et r. L’origine du repère est placée au coin supérieur gauche de l’image.

L’annexe décrit en détail la méthode dont les principaux éléments sont les suivants :
On appelle sinogramme la représentation des valeurs prises par la transformée de Hough pour
toutes les valeurs de θ et r considérées. Pour une orientation θ fixée, le sinogramme ne dépend
que de la coordonnée radiale. Il est construit et exploité de la façon suivante :
– Sommation des valeurs de pixels selon cette orientation (figure 1.6). Les valeurs de
sommation pour toutes les valeurs de la coordonnée radiale constituent le sinogramme.
– Détermination du maximum du sinogramme. (figure 1.7)
– Détermination des offsets
x0k = ρk /cos(θk )

Complexité de l’extension de la transformée de Hough Le coût numérique de l’al-

gorithme est assez élevé. Ce coût est dû à la procédure de calcul des valeurs du sinogramme
qui pour un angle donné est réalisée exhaustivement pour toutes les valeurs de distance à
l’origine.
Pour chacune des d valeurs d’orientation : √
1
– Pour chaque valeur de coordonnée radiale ( δρ ∗ 2 ∗ N ≃ 10 ∗ N valeurs) : somme de
Np valeurs.
– Recherche du maximum de la somme.
La complexité de la méthode est donc de : O(d∗(10∗N ∗Np +10∗N )) ≃ O(d∗10∗N ∗Np ).
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 15

Figure 1.6 — Création du sinogramme

Figure 1.7 — Valeurs du sinogramme

Avantages et inconvénients de la méthode L’avantage de cette méthode est que son

principe est relativement simple puisqu’il s’agit de compter le nombre de pixels selon une
orientation donnée. L’inconvénient majeur de la méthode est son coût numérique dans les cas
où le nombre de pixels de valeur non nulle dans l’image est important. On remarquera que
le cas de droites parallèles peut être traité si plusieurs maxima relatifs du sinogramme sont
sélectionnés pour conduire à des valeurs d’offset.

[Link] Le schéma de propagation à vitesse variable

Génération des signaux Dans le cas de l’estimation de l’orientation des droites l’existence
de différentes valeurs d’orientation était envisagée ; le formalisme aboutissant au signal reçu
par l’antenne, dans le cas de l’estimation du décalage des lignes, est différent en deux points
par rapport au schéma de propagation à vitesse variable : la partie signal correspond à une
seule valeur d’orientation, et la vitesse de propagation est variable. Le signal reçu au capteur
l est alors, lorsque la première valeur d’orientation est considérée :
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 16

zl = Σdk=1
1
exp(−jτ x0k ).exp(jτ ltan(θ1 )) + nl pour l = 0...N − 1
d1 est le nombre de droites d’orientation θ1 et d’offsets différents.
Lorsque τ varie linéairement en fonction de l’indice des lignes le vecteur de mesures z
contient un terme à fréquence modulée. Si on pose τ = αl, alors :
zl = Σdk=1
1
exp(−jαlx0k ).exp(jαl2 tan(θ1 )) + nl
C’est une somme de d1 signaux qui ont un terme de phase quadratique en commun mais
différents termes linéaires. Le premier traitement de ce signal consiste à obtenir une expression
ne contenant que les termes linéaires en l. Cette procédure consiste en une division de zl par
le terme non nul al (θ1 ) = exp(jαl2 tan(θ1 )) -ou une multiplication par le conjugué de cette
expression-.
On obtient alors :
wl = Σdk=1
′
1
exp(−jαlx0k ) + nl pour l = 0...N − 1.
Le problème de l’estimation du décalage est donc ramené à la détermination de valeurs
de fréquences. On remarque que cette procédure permet de différencier plusieurs droites de
même orientation mais d’offsets différents. Dans un cas plus général une image peut contenir
des lignes parallèles et non parallèles. L’obtention du signal w est alors réalisée pour chacun
des angles. Pour chacun des angles une méthode d’estimation de fréquence est employée.

Remarque :
Les sources étant de puissances identiques et égales à 1 on ne peut pas utiliser une méthode
fondée sur la séparation d’un sous-espace source et du sous-espace bruit après calcul d’une
matrice de covariance (technique employée en [Link]). La matrice de covariance des signaux
w a la forme suivante :

Rww = AJAH + Rn′ n′

A = exp(−jαlx0k )l=0...N −1,k=1...d1

J = (1)l=1...d1 ,k=1...d1 , Rn′ n′ est la matrice interspectrale du bruit.

La matrice J est de rang 1. Cela provoque une indétermination sur la dimension du sous-
espace signal, autrement dit le nombre de valeurs d’offset.
De plus le sous-espace correspondant à la valeur propre dominante ne représente n’est que de
dimension 1 et ne représente plus le sous-espace signal.

La méthode "Modified Backward Forward Linear Prediction"

On propose dans cette étude la méthode modified forward-backward linear prediction [10].
Elle passe par le biais de la séparation d’une partie signal et d’une partie bruit, mais pas par
le calcul d’une matrice interspectrale. On se rapportera à l’annexe afin de se renseigner sur
la partie calculatoire de cette méthode. Certains commentaires apparaissent également dans
cette annexe. On en donne ci-dessous les principales étapes. On nomme L l’un des paramètres
de la méthode. Celui-ci est proche de N , taille de l’image.
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 17

– 1) Formation d’une matrice issue de la donnée du signal w :

On forme la matrice Q de taille 2 × (N − L) × L :

 
WL−1 WL−2 ... W0

 W L W L−1 ... W1


 W WL ... W2 
 L+1 

 . . . . 


 . . . . 


 . . . . 

 WN −2 WN −3 ... WN −L−1
 
Q=

W1∗ W2∗ ... WL∗

 
W2∗ W3∗ ... ∗
WL+1
 
 

 W3∗ ∗
W4 ... ∗
WL+2


. . . .
 
 
 

 . . . . 

 . . . . 
∗ ∗
WN −L WN −L+1 ... ∗
WN −1
– 2) Calcul d’une décomposition en valeurs singulières.
Former la décomposition en valeurs singulières de Q :
Q = U ΛV H
– 3) Sélection du sous-espace propre correspondant au signal : obtention de la matrice Σ.
– 4) Formation -faisant intervenir la matrice Σ- des coefficients d’un polynôme de degré
élevé, puisqu’égal à L.
– 5) Parmi les zéros du polynôme calculé certains sont placés sur le cercle unité, ils sont
sélectionnés (figure 1.8).

90
1
120 60
0.8

0.6
150 30
0.4

0.2

180 0

210 330

240 300

270

Figure 1.8 — Sélection de zéros

– 6) Les valeurs des offsets sont proportionnelles aux arguments des zéros sélectionnés :
exp(−jαx0k ) → x0k .
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 18

Complexité du schéma de propagation à vitesse variable On rappelle que N est la

taille d’un côté de l’image, L est un paramètre choisi proche de N (cf B.2.2). Les opérations
successives et leur complexité respective sont les suivantes :
– Génération des signaux en O(Np ).
Pour chacune des d directions trouvées par le schéma de propagation à vitesse constante :
– Création de la matrice Q en O(2 ∗ (N − L) ∗ L) = O(N ) car N ≈ L,
– Décomposition en valeurs singulières de la matrice Q en O((N − L)3 + N 3 ) = O(N 3 ).
– Création de la matrice Σ en O(L) = O(N )
– Création du vecteur g : Deux produits matriciels de complexité en O(L) et un décalage
des valeurs de g en O(L) donnent une complexité en O(L + L + L) = O(N )
– Création du polynôme H en O(L) = O(N ).
– Recherche des zéros : La procédure "roots" de matlab comprend une diagonalisation
d’une matrice de taille L par L. La complexité vaut donc O(N 3 ).
La complexité globale de la méthode est finalement O(Np + d ∗ N 3 ) ≃ O(d ∗ N 3 ).

Propriétés principales de la méthode La complexité du schéma de propagation à vitesse

variable est moindre que celle de l’extension de la transformée de Hough dès que le nombre de
pixels de valeur non nulle dans l’image est important. Une propriété de la méthode provient
aussi du fait qu’elle s’applique aux cas où les sources ont mêmes puissances, et qu’elle permet
de traiter le cas de droites parallèles. Les difficultés qui lui sont liées sont dues aux erreurs de
calcul numériques lors des calculs matriciels.

1.4.3 Conclusion

La méthode HRSP, qui constitue le coeur de ce rapport, est une méthode de caractérisa-
tion de droites dans une image, la première étape consistant à déterminer les orientations des
droites, la seconde à en estimer les offsets. Deux algorithmes ont été décrits pour la déter-
mination des offsets ; une importance particulière a été accordée au schéma de propagation à
vitesse variable car il constitue une méthode innovante et mettant en oeuvre des techniques
de traitement d’antenne. La cohérence de l’ensemble HRSP tient à l’emploi, dans chacune des
étapes, de méthodes issues du traitement d’antenne.

1.5 Choix des paramètres, premières expériences

1.5.1 Choix des paramètres

[Link] Les paramètres importants

Trois paramètres se dégagent des méthodes présentées de par leur importance particulière.
Se distinguent dans le schéma de propagation à vitesse constante la vitesse de propagation
µ et la longueur des vecteurs-signal M . Le paramètre le plus important dans le schéma de
propagation à vitesse variable est la constante de propagation α. On peut se demander quels
sont les ordres de grandeur correspondant à ces paramètres. Concernant l’extension de la
transformée de Hough les paramètres sont le pas choisi pour ρ, et la largeur R de la fonction
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 19

c permettant de réaliser les sommes de valeurs de pixels (se référer à B pour la signification
précise des paramètres).

[Link] Influence des paramètres et valeurs optimales

La taille M de la sous-antenne Le rang de la matrice interspectrale Rzz devant être

supérieur au nombre maximal de droites dans l’image l’inégalité suivante doit être respectée :
d < M < N − d + 1. Une trop grande valeur de M détériore l’estimation de la matrice
interspectrale car le nombre de vecteurs-signal est faible. Cependant, une grande valeur de M
réduit dans la matrice de covariance l’influence du bruit. Un √compromis doit être trouvé. La
valeur qui donne les meilleurs résultats pour M est EN T ( N ) où N est la taille d’un côté
de l’image, EN T représente la partie entière. Pour une image 200 pixels par 200 on choisira
M = 14.

La vitesse de propagation µ Il existe des valeurs limites pour µ, que l’on déduit de
l’expression donnant la valeur des orientations des droites. On montre en [Link] que les
valeurs estimées des angles sont données par :
1 λk
θ̂k = tan−1 [ Im(ln( ))]
(µ∆) |λk |
La partie utile des signaux obtenus par schéma de propagation à vitesse constante est compo-
sée d’exponentielles complexes dont on veut retrouver l’argument. L’intervalle pour les valeurs
non ambiguës des angles est de longueur 2π :

−π < µ∆tan(θk ) ≤ π

On doit donc choisir :

π
|µ| ≤
∆tan(θk )
pour tout k.
En considérant par exemple ∆ = 1 et θk = 45˚,

|µ| ≤≃ 3

Le paramètre de propagation α
On montre en B.2.2 que les valeurs d’offset sont déduites des valeurs des arguments de
zéros placés sur le cercle unité : exp(−jαx0k ) → x0k . Afin d’obtenir des zéros répartis sur
un intervalle donné en argument, il convient de fixer correctement α. Si l’on souhaite que ces
arguments soient compris dans [− π4 ; π4 ], pour des valeurs maximales d’offset x0 autour de X0,
on obtient la condition :

π
|α| =
4 ∗ X0
En considérant par exemple X0 = 300,

|α| ≈ 2.5 ∗ 10−3

CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 20

1.5.2 Première mise en oeuvre des méthodes

[Link] Simulations

On présentera lors de ces simulations les résultats obtenus sur une image binaire simple,
non bruitée puis bruitée. Le bruit considéré est une distribution aléatoire de pixels "noirs".
Le bruit est caractérisé par la donnée suivante : un pourcentage représente la proportion de
pixels noircis -dans ce cas précis on a fixé un bruit à 5 pour cent-. Les résultats présentés sont
obtenus par le schéma de propagation à vitesse constante, et par l’extension de la transformée
de Hough (figure 1.9) puis le schéma de propagation à vitesse variable respectivement
(figure 1.10).

On choisit dans tous les cas la première position d’antenne, selon le formalisme présenté
en [Link]. Les paramètres liés à l’extension de la transformée de Hough sont les suivants : la
largeur R est fixée à trois pixels, le pas δρ est de 17 .

Image à traiter Superposition de l’image de départ et de l’estimation par hrsp

20 20

40 40

60 60

80 80

100 100

120 120

140 140

160 160

180 180

200 200
20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image départ superposition image départ et estimation

Image à traiter Superposition de l’image de départ et de l’estimation par hrsp

20 20

40 40

60 60

80 80

100 100

120 120

140 140

160 160

180 180

200 200
20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image départ superposition image départ et estimation

Figure 1.9 — Méthode extension de la transformée de Hough
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 21

Image à traiter Superposition de l’image de départ et de l’estimation par hrsp

20 20

40 40

60 60

80 80

100 100

120 120

140 140

160 160

180 180

200 200
20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image départ superposition image départ et estimation

Image à traiter Superposition de l’image de départ et de l’estimation par hrsp

20 20

40 40

60 60

80 80

100 100

120 120

140 140

160 160

180 180

200 200
20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image départ superposition image départ et estimation

Figure 1.10 — Méthode schéma de propagation à vitesse variable

[Link] Analyse des résultats

Dans le cas des images non bruitées les trois droites estimées sont parfaitement superposées
aux droites de départ. Leur estimation est correcte également dans le cas d’une image bruitée.
L’optimalité des paramètres étudiés est établie selon le critère du biais moyen obtenu entre
les valeurs vraies et estimées des paramètres. On constate que les valeurs optimales de µ sont
autour de 1, à 0.1 près, qu’une valeur de M fixée à 15 donne de bons résultats. La valeur
optimale de α est 2.5 ∗ 10−3 .

[Link] bilan

La lourdeur constatée de la méthode extension de la transformée de Hough justifie une

étude approfondie du schéma de propagation à vitesse variable, avec lequel des résultats
similaires -en première approximation- sont obtenus pour une complexité moindre. On note
que les valeurs des paramètres choisis expérimentalement sont en accord avec celles qui étaient
prévues en [Link]. Les images utilisées jusqu’à présent étant binaires, on peut penser à une
adaptation aux images en niveaux de gris comme première extension de la méthode HRSP.

1.6 Conclusion
Les fondements du traitement d’antenne ont été décrits et rapprochés du traitement
d’image. On a en effet montré qu’un formalisme particulier permet d’associer à un côté d’une
image une série de capteurs correspondant chacun à une ligne. Les signaux reçus par ces
capteurs sont générés par ce qu’on appelle un "schéma de propagation". Une droite dans une
image est assimilée à un front d’onde figé dont on simule la propagation. Ce rapprochement
CHAPITRE 1. LES MÉTHODES HAUTE RÉSOLUTION DU TRAITEMENT
D’ANTENNE, APPLICATION AU TRAITEMENT D’IMAGES 22

permet d’appliquer au traitement d’image les méthodes Haute Résolution employées en traite-
ment d’antenne. Les méthodes Haute Résolution ont été introduites au travers de la méthode
MUSIC, fondée sur la distinction entre un sous-espace signal et un sous-espace bruit. C’est
dans cette catégorie de méthodes que l’on a choisi celles employées dans la procédure "Haute
Résolution et Schéma de Propagation". Cette procédure utilise un schéma de propagation à
vitesse constante pour estimer la valeur des orientations des droites et un schéma de propa-
gation à vitesse variable pour déterminer la valeur des offsets. On a pris soin de décrire la
méthode "extension de la transformée de Hough" afin de la comparer à la méthode innovante
que constitue le schéma de propagation à vitesse variable. Les premières simulations ont per-
mis de fixer la valeur des paramètres importants intervenant dans les procédures, notamment
les paramètres liés à la vitesse dans les schémas de propagation.
Ces simulations ont également débouché sur des perspectives d’applications : les performances
du schéma de propagation à vitesse variable méritent d’être étudiées de façon approfondie ;
les images utilisées jusqu’à présent étant binaires, on peut envisager une déclinaison de HRSP
adaptée à des images en niveaux de gris, des images couleur...
 2
CHAPITRE

Application de "Haute
Résolution et Schéma de
Propagation" à divers cas
pratiques

Introduction

Lors de l’étude théorique et des premières expériences exposées au premier chapitre on

a montré que la méthode Haute Résolution et Schéma de Propagation s’applique bien à la
recherche et la caractérisation des droites dans une image. On étudiera en détail les aptitudes
de la méthode HRSP face à des cas difficiles ; une étude quantitative permettra d’évaluer
précisément dans différentes conditions les performances de la méthode HRSP, y compris du
point de vue de la complexité ; la méthode HRSP sera ensuite adaptée à divers cas pratiques.
On montrera qu’un prétraitement par gradient permet d’adapter la procédure aux images en
niveaux de gris. La complexité relativement faible du schéma de propagation à vitesse variable
permettra une adaptation aux images réelles.
On s’intéressera ensuite à la détection de contours d’objets et aux images couleur.

2.1 Les aptitudes de la méthode HRSP face à des cas difficiles

On se penchera ici sur certains cas difficiles : on expliquera pourquoi certains d’entre
eux peuvent parfois donner lieu à des résultats biaisés et comment surmonter les difficultés
rencontrées.
On rappelle que le schéma de propagation à vitesse variable est utilisé pour estimer la valeur
des offsets des droites présentes dans une image. Il est adapté à la résolution du cas particulier
que constitue les droites parallèles, c’est-à-dire qui correspondent à une seule valeur d’angle
mais plusieurs valeurs d’offset. On s’intéressera au cas d’une image bruitée et à une image qui
contient des droites ne la traversant que partiellement.
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 24

2.1.1 Le cas des droites parallèles

L’objectif est de montrer que le schéma de propagation à vitesse variable est capable
de résoudre le cas de droites parallèles, c’est-à-dire de trouver des droites de même pente
mais d’offset différent. La figure 2.1 montre que cette propriété de la méthode est vérifiée. La
méthode de l’extension de la transformée de Hough est également capable de résoudre ce cas
particulier : deux maxima du sinogramme [Link] sont alors sélectionnés. Les deux antécédants
de ces maxima conduisent chacun à une valeur d’offset.

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image départ schéma de propagation Transformée de Hough

Figure 2.1 — Droites parallèles : superposition de l’image de départ et du résultat obtenu

Le tableau suivant donne pour les valeurs d’orientation et d’offset des droites les valeurs
réelles, les valeurs obtenues par la méthode schéma de propagation à vitesse variable, et par
l’extension de la transformée de Hough.
Pente Offset1 Offset2
Valeur réelle 20 80 140
Schéma de propagation à vitesse variable 20.01 80.75 140.85
Extension de la transformée de Hough 20.01 80.88 140.78
Les méthodes schéma de propagation à vitesse variable et extension de la transformée de
Hough parviennent à retrouver les deux droites parallèles avec une erreur de moins d’un pixel
sur les valeurs d’offset.

2.1.2 Une image bruitée

Une image bruitée peut aboutir à une valeur d’angle biaisée, l’exemple d’un tel cas est
donné par la figure 2.2. L’image est bruitée avec un pourcentage de bruit de 20 pour cent.
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 25

20

40

60

80

100

120

140

160

180

200
20 40 60 80 100 120 140 160 180 200

Figure 2.2 — Image bruitée de départ et estimation

[Link] Les limites de la méthode TLS-ESPRIT

La détermination du sous-espace signal dans la matrice E passe par la sélection des d

valeurs propres de plus grande valeur de la matrice de covariance estimée. Dans le cas d’une
image bruitée une valeur propre due au bruit peut prendre une valeur proche de celle d’une
valeur propre due au signal. Cela rend difficile l’estimation de la dimension du sous-espace
signal et la distinction entre sous-espace signal et sous-espace bruit est moins nette que dans
un cas non bruité. La matrice Ês est alors mal estimée. Cela aboutit à un biais sur les angles
estimés.

[Link] Solution apportée et illustration

Dans un cas bruité on choisira de préférence une valeur élevée de la taille de sous-antenne
M , ce qui permet de réduire la valeur des valeurs propres dues au bruit dans la matrice de
covariance estimée. La figure 2.3 présente les résultats obtenus avec respectivement une petite
et une grande taille de sous-antenne.
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 26

20

40

60

80

100

120

140

160

180

200
20 40 60 80 100 120 140 160 180 200

20

40

60

80

100

120

140

160

180

200
20 40 60 80 100 120 140 160 180 200

Figure 2.3 — Estimations réalisées : avec une petite valeur de M, avec une grande valeur
de M

Dans le premier cas on a fixé une taille de sous-antenne de 15, dans le second cas une taille
de sous-antenne de 30.

2.1.3 Cas des droites ne traversant qu’une partie de l’image

On se penche ici sur le cas où une droite de l’image ne traverse qu’une partie de l’image.
La figure 2.4 donne l’exemple d’une telle image et le résultat de l’estimation. On note qu’il
existe une biais sur l’une des valeurs d’offset.
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 27

20

40

60

80

100

120

140

160

180

200
20 40 60 80 100 120 140 160 180 200

Figure 2.4 — Une image conduisant à une valeur d’offset biaisée

[Link] Les limites de la méthode MFBLP

La méthode nécessite le calcul d’un polynôme de degré élevé [Link], dont on détermine
les zéros. Le nombre de zéros situés sur le cercle unité est théoriquement égal au nombre de
valeurs d’offsets pour une orientation donnée. Cependant les erreurs d’arrondi inhérents au
calcul matriciel éloignent ces zéros du cercle unité. On attribue donc au signal les zéros les plus
proches du cercle unité. Un zéro dû au bruit peut cependant être plus proche du cercle unité
qu’un zéro dû au signal tout en ayant un module très proche et un argument très différent.
Cela explique l’obtention occasionnelle d’une grande valeur de biais sur l’offset.
Les figures 2.5 et 2.6 donnent une illustration graphique de ce choix de zéros :

racines méthode MFBLP

90
1
120 60
0.8

0.6
150 30
0.4

0.2

180 0

210 330

240 300

270

Figure 2.5 — Zéros du polynôme

CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 28

30
racines méthode MFBLP

330

Figure 2.6 — Zoom sur certains zéros

CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 29

[Link] Solution apportée

Une valeur d’offset biaisée peut être obtenue lorsque les droites ne traversent pas toute
l’image. Dans ce cas-là la partie du signal reçue sur certains des capteurs est nulle. L’observa-
tion des signaux obtenus à partir de l’image à traiter permet de repérer cette situation. Une
solution à ce type de problème est de changer la position d’antenne. Si le signal est non nul
sur l’ensemble de l’antenne, les résultats obtenus seront meilleurs. Une illustration est donnée
par les figures suivantes. La figure 2.7 montre une image de deux droites ayant conduit à
l’estimation biaisée d’un offset lorsque la position d’antenne 4 (voir [Link]) est utilisée. La
droite d’offset égal à 160 conduit à une valeur d’offset supérieure à 200. La figure 2.8 montre
un signal reçu. On remarque que la partie du signal correspondant aux derniers capteurs est
nulle. La figure 2.9 donne le signal obtenu lorsque la position d’antenne 1 est utilisée. Cette
figure montre que tous les capteurs reçoivent un signal non nul. L’utilisateur de la méthode
donnera donc la préférence à cette configuration. L’exploitation de ce signal conduit à un
résultat non biaisé. Ceci est visible sur la figure 2.10.

20

40

60

80

100

120

140

160

180

200
20 40 60 80 100 120 140 160 180 200

Figure 2.7 — Image de départ et estimation par la position d’antenne 4

1
Partie réelle du signal

−1

−2

−3
0 20 40 60 80 100 120 140 160 180 200
Numéro de ligne

Figure 2.8 — Signal obtenu sur l’antenne 4 : le dernier capteur correspond au coin inférieur
droit
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 30

1.5

Partie réelle du signal

0.5

−0.5

−1

−1.5

−2
0 20 40 60 80 100 120 140 160 180 200
Numéro de ligne

Figure 2.9 — Signal obtenu sur l’antenne 1

20

40

60

80

100

120

140

160

180

200
20 40 60 80 100 120 140 160 180 200

Figure 2.10 — Image de départ et estimation par la position d’antenne 1

CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 31

2.1.4 Conclusion

La méthode du schéma de propagation à vitesse variable aboutit à de bons résultats

dans le cas du traitement des droites parallèles, plusieurs valeurs d’offset sont alors prises en
compte pour une valeur d’angle. Les méthodes TLS-ESPRIT et "Modified Forward Backward
Linear Prediction" présentent dans des cas difficiles des limites qui peuvent conduire à un
biais sur la valeur des pentes et/ou des offsets des droites. Ces limites peuvent cependant être
contournées en adaptant un paramètre ou en choisissant une configuration d’antenne adéquate
pour la réception des signaux. Ces choix seront faits en fonction des conditions d’obtention de
l’image (image pouvant être bruitée par exemple) ou en fonction de l’allure du signal obtenu
à partir de l’image.

2.2 Etude quantitative des performances de l’algorithme HRSP

2.2.1 Introduction

L’étude du schéma de propagation à vitesse variable a montré que de bons résultats sont
obtenus dans le cas de droites parallèles, et que des cas difficiles pouvaient être surmontés.
Les constats qui ont été faits restent cependant qualitatifs et il est nécessaire de caractériser
quantitativement les performances de l’algorithme HRSP, à la fois sur quelques cas particu-
liers et par une série de tests sur un grand nombre d’images. Cette étude concerne à la fois la
méthode de détermination des angles et les méthodes de détermination des offsets. Elle a pour
support des images binaires. L’algorithme utilisé pour l’estimation des angles est le schéma
de propagation à vitesse constante. Les algorithmes disponibles pour la détermination des
offsets - celui de l’extension de la transformée de Hough et celui du schéma de propagation
à vitesse variable- seront comparés en terme de rapidité et de fiabilité. Plus précisément les
objectifs de cette étude quantitative seront les suivants : montrer que les résultats obtenus
sont stables pour une image donnée -c’est-à-dire que l’on obtient toujours les mêmes résultats
quand la méthode est appliquée plusieurs fois à la même image-, déterminer la rapidité
des algorithmes, déterminer le biais sur l’estimation des angles et des offsets -les valeurs de
biais données pour chaque image représentent les valeurs moyennes sur toutes les droites- ;
généraliser ces résultats moyens obtenus sur quelques images par une série de tests menée
dans différentes conditions expérimentales et à chaque fois pour un grand nombre d’images.

2.2.2 Cas particuliers et temps de calcul des algorithmes

Les images sont de taille 200 par 200 pixels. C’est un paramètre qui influe sur la rapidité
de l’algorithme. Afin de ne pas encombrer le compte-rendu on ne donnera les valeurs d’angles
et d’offsets que pour une seule image et on se concentrera sur les valeurs de biais sur chacune
des images ainsi que sur leur valeur moyenne prise sur plusieurs images. Les images utilisées
dans 2.2.2 ont typiquement l’allure de celle représentée en figure 2.11. On rapelle que le
pourcentage de bruit désigne le pourcentage de pixels de bruit dans l’image.
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 32

20

40

60

80

100

120

140

160

180

200
20 40 60 80 100 120 140 160 180 200

Figure 2.11 — Un exemple typique d’image utilisée

[Link] Temps de calcul

L’image considérée est constituée de trois droites, on considérera successivement les cas
d’une image non bruitée et bruitée. La valeur numérique donnée correspond au temps total
nécessité pour dix simulations.

Cas non bruité :

Schéma de propagation à vitesse constante (estimation des angles) : 0,9 s.
Extension de la transformée de Hough (Première méthode d’estimation des offsets) : 60
secondes.
Schéma de propagation à vitesse variable (Seconde méthode d’estimation des offsets) : 50
secondes.

Cas bruité (pourcentage de bruit 5 pour cent) :

Schéma de propagation à vitesse constante : 0,9 s.
Extension de la transformée de Hough : 180 secondes.
Schéma de propagation à vitesse variable : 50 secondes.
Pour un pourcentage de 20 pour cent de bruit le temps nécessaire pour dix simulations
est de 1200 secondes pour l’extension de la transformée de Hough, le temps de calcul restant
le même pour les deux autres méthodes.

Par conséquent la méthode de l’extension de la transformée de Hough est moins rapide

que le schéma de propagation à vitesse variable dans un cas non bruité. Ce dernier est plus de
trois fois plus rapide dans un cas bruité. De plus sa complexité ne varie pas entre le cas non
bruité et le cas bruité. Cela rejoint les commentaires concernant la complexité des méthodes
émis en 1.4.
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 33

[Link] Etude quantitative

Définitions Nous considérons que les résultats obtenus par la méthode proposée qu’ils sont
stables sous la condition suivante : les valeurs estimées ne changent pas quand la méthode
est appliquée plusieurs fois sur la même image.
Soit p un paramètre, p̂ la valeur estimée de ce paramètre. On définit le biais b sur l’estimation
de ce paramètre par :

b = |p − p̂|

Lorsque K valeurs pk de ce paramètre sont estimées on définit le biais moyen b̄ par :

1 K
b̄ = Σ |pk − p̂k |
K k=1
Nous avons recherché les paramètres des droites sur une image test plusieurs fois, dans la
même configuration. Les valeurs estimées présentées ont été obtenues vingt fois à partir de
la même image.

Valeurs réelles et estimées Méthode de détermination des angles : Les valeurs réelles et
les valeurs obtenues sont :

Valeurs réelles -20 15 35

Valeurs estimées -20.0175 15.0383 35.0311

Méthodes de détermination des offsets : Les valeurs reelles, et obtenues par le schéma de
propagation à vitesse variable et l’extension de la transformée de Hough sont respectivement :

Valeurs réelles d’offset 30 190 150

Valeurs estimées par le schéma de propagation à vitesse variable 27.5393 191.9911 151.9839
Valeurs estimées par l’extension de la transformée de Hough 30.1044 190.8209 151.0848

valeurs de biais On considère quatre images, comportant chacune trois droites. Les valeurs
d’angles et d’offsets considérées sont par exemple pour la première image : [-10 20 30]˚, [70 100
130] pixels. Le tableau suivant donne pour chacune des images les valeurs moyennes de biais
sur toutes les droites de l’image, ainsi que la moyenne de ces valeurs. Les lignes du tableau
concernent respectivement l’estimation des angles, l’estimation des offsets par le schéma de
propagation à vitesse variable et par l’extension de la transformée de Hough.

Valeurs moyennes de biais Im1 Im2 Im3 Im4 Moyenne

angle 0.2184 0.1050 0.0331 0.0175 0.0935
Offsets schéma vitesse variable 2.2295 1.0398 2.2820 1.4948 1.7615
Offsets Extension Hough 1.0973 0.7330 0.8538 0.9185 0.9007
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 34

On note tout d’abord que la méthode employée sur l’extension de la transformée de

Hough est plus lente que le schéma de propagation à vitesse variable. La valeur moyenne de
biais sur les offsets est inférieure à deux pixels lorsque le schéma de propagation à vitesse
variable est utilisé.

Les biais observés sur les valeurs obtenues par le schéma de propagation à vitesse variable
proviennent des étapes de calcul matriciel de la méthode MFBLP. L’argument des zéros du
polynôme calculé est légèrement biaisé à cause des erreurs de calcul numérique. Cet argument
conduisant à la valeur des offsets, ceux-ci sont également biaisés.

[Link] Analyse qualitative des résultats

L’algorithme d’estimation des angles n’a pas d’influence globale sur la rapidité de la mé-
thode. On préfèrera le schéma de propagation à vitesse variable si le critère de rapidité prime
sur celui de la précision sur la valeur d’offset.

2.2.3 Série de tests

On a remarqué en début de ce chapitre que les valeurs d’angle et d’offset estimées peuvent
parfois être biaisées, c’est-à-dire qu’une mauvaise valeur de pente ou d’offset peut être attri-
buée à une droite. Il est donc nécessaire de réaliser une série de tests, recouvrant des condi-
tions expérimentales -valeurs d’orientation et d’offset- représentatives et relativement difficiles
(images bruitées, images contenant un grand nombre de droites). L’objectif est de déterminer
la proportion de valeurs pour lesquelles l’estimation n’est pas correcte. Le critère de décision
employé est un seuil sur le biais entre la valeur réelle et la valeur estimée. Les résultats obtenus
consisteront en une proportion de valeurs estimées non acceptables, c’est-à-dire le rapport du
nombre de valeurs estimées non acceptables au nombre total de valeurs estimées. Une valeur
d’angle est considérée comme acceptable si le biais obtenu sur cette valeur est inférieur à 2
degrés. Une valeur d’offset est considérée comme acceptable si le biais obtenu sur cette valeur
est inférieur à 2 pixels.
Dans un premier temps on réalisera une étude relative au schéma de propagation à vitesse
constante, en fixant des valeurs d’offsets. Dans un second temps les proportions de valeurs
d’offsets non acceptables seront déterminées pour les méthodes de l’extension de la transformée
de Hough et du schéma de propagation à vitesse variable, en fixant des valeurs d’orientation.
Chacune des séries de tests est réalisée sur un ensemble de vingt images. Sauf indication
contraire les images comportent deux droites. Pour chacun des paramètres on s’intéressera
à cinq ensembles de conditions expérimentales différents. Ces conditions seront présentées et
illustrées : Un exemple d’ensemble de paramètres correspondant à une image sera donné.

[Link] Etude relative aux angles

Des valeurs quelconques d’offsets seront choisies lors de cette étude. Les valeurs d’orien-
tation sont choisies successivement de la façon suivante :
– a) les valeurs d’angles sont grandes tout en étant inférieures à la valeur maximale ac-
ceptable, par exemple [15 35]˚.
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 35

– b) Les valeurs d’angles sont petites, par exemple [1 4]˚

– c) Les valeurs d’angles sont grandes (par exemple [60 40]˚) et l’image est bruitée par un
pourcentage de 5 pour cent.
– d) L’image comporte quatre droites, les valeurs d’angle sont grandes.
– e) L’image comporte trois droites -les valeurs d’angle étant grandes- et est bruitée par
un pourcentage de 5 pour cent.
Le tableau suivant donne la proportion de valeurs d’angle estimées non acceptables pour
a b c d e
chacun des cas d’étude :
0 0.08 0.20 0.13 0.19

[Link] Etude relative aux offsets

Les valeurs d’offset seront choisies successivement de la façon suivante :

– a) Valeurs d’offsets uniformément réparties, par exemple [100 150].
– b) Valeurs d’offsets proches (valeurs d’offsets séparées de 5 pixels ou moins), par exemple
[25 30]
– c) Image bruitée à 5 pour cent, avec les conditions du a).
– d) Grand nombre de droites (4 droites dans l’image), et valeurs d’offsets uniformément
réparties, par exemple [20 50 100 150].
– e) Nombre important de droites (3) et pourcentage de bruit de 5 pour cent. Les valeurs
d’offsets uniformément réparties, par exemple [100 150 180].
On se penchera successivement sur le cas de l’utilisation de l’extension de la transformée
de Hough, puis sur l’utilisation du schéma de propagation à vitesse variable.

Méthode extension de la transformée de Hough

Le tableau suivant donne la proportion de valeurs d’offset estimées non acceptables pour
a b c d e
chacun des cas d’étude :
0 0 0.43 0.59 0.38

Méthode schéma de propagation à vitesse variable

Le tableau suivant donne la proportion de valeurs d’offset estimées non acceptables pour
a b c d e
chacun des cas d’étude :
0.29 0.28 0.62 0.65 0.63

[Link] Commentaires des résultats et conclusion

L’estimation des valeurs d’orientation est réalisée correctement lorsque l’image est non
bruitée, même lorsqu’elle contient un grand nombre de droites ou que les valeurs des angles
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 36

sont petites. La proportion de valeurs non acceptables est nulle ou inférieure à quinze pour
cent dans ces cas-là. Le pourcentage de valeurs non acceptables (20 pour cent) reste correct
pour des images bruitées.
Les performances des méthodes de détermination des offsets sont bonnes pour les cas les moins
difficiles. Pour les conditions a) et b) la proportion de valeurs non acceptables est nulle lorsque
l’extension de la transformée de Hough est utilisée, et inférieure à 0.3 lorsque le schéma de
propagation à vitesse variable est utilisé. Dans des cas difficiles les proportions de valeurs non
acceptables sont plus élevées pour l’une et l’autre méthode.
Il est nécessire de prendre en compte dans le cas de la transformée de Hough la place mémoire
nécessaire au stockage des coordonnées des pixels "utiles". La donnée de ces coordonnées est
nécessaire au calcul des valeurs du sinnogramme. Ce problème n’apparaît pas pour la méthode
du schéma de propagation à vitesse variable.

2.2.4 Etude quantitative : bilan

La première partie de l’étude, donnant les résultats numériques correspondant à quelques

images, a permis de mettre en valeur la rapidité de l’algorithme du schéma de propagation
à vitesse variable, notamment dans des cas bruités. A suivi une série de tests qui se veut
exhaustive car traitant plusieurs situations classiques que l’on peut rencontrer lorsque une
image est traversée par quelques droites. Il en découle que si l’on s’en tient à la probabilité
d’obtention d’une valeur d’offset non acceptable, il est préférable d’utiliser l’extension de la
transformée de Hough dans les cas les moins difficiles. Tout en sachant cependant que des
résultats acceptables sont obtenus avec le schéma de propagation.

2.3 Mise en oeuvre de l’algorithme : application aux images en

niveaux de gris

D’après les conventions utilisées pour adapter le traitement d’images au traitement d’an-
tenne, le fond blanc d’une image binaire ne contribue pas aux signaux obtenus par les capteurs,
car les valeurs de pixel correspondantes sont nulles. Dans le cas d’une image à niveaux de gris
tous les niveaux sont pris en compte et il est nécessaire de supprimer les zones de fond continu
quel que soit leur niveau de gris. L’image est donc prétraitée par un opérateur gradient [3]. On
montrera l’influence de cette opération sur l’estimation des angles par la méthode du schéma
de propagation à vitesse constante, et sur les méthodes d’estimation des offsets. Une mise en
oeuvre comprenant le schéma de propagation à vitesse variable permettra d’apprécier la qua-
lité de l’amélioration qui découle de ce prétraitement. Des images réelles seront notamment
exploitées.

2.3.1 Le modèle utilisé

[Link] Influence sur la méthode de détermination des angles

Le formalisme adopté dans le schéma de propagation à vitesse constante peut être

généralisé au problème des images en niveaux de gris. On propose une extension simple du
modèle : un pixel d’une ligne contribue au signal reçu par le capteur associé à la ligne par la
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 37

valeur du gradient en ce pixel.

D’un point de vue qualitatif une procédure de gradient ou de rehaussement de contour

atténue la contribution du fond continu, les signaux obtenus ne dépendent donc que des
ruptures de niveaux de gris dans l’image. D’un point de vue mathématique, on montre que
lorsque l’image considérée n’est pas binaire on peut retrouver pour les signaux une forme
similaire à ceux obtenus dans un cas binaire.
Considérons une image traversée par une droite d’offset x0 . Si la valeur du gradient dans
la première ligne est représentée par la fonction f (x), on pose f (x) = g(x − x0 ), g est une
fonction obtenue à partir de f par décalage qu’il est judicieux d’introduire. Le capteur en face
de la première ligne recevra :
N
X −1
z(0) = exp(−jµx)f (x)
x=0

N
X −1
= exp(−jµx)g(x − x0 )
x=0
N
X −1
= exp(−jµx0 ) exp(−jµx)g(x)
x=0

Le terme somme nous invite à introduire une transformée de Fourier dans l’expression de z(0).

N −1 N −1
X 1 X 2 ∗ π µN x µN
exp(−jµx)g(x) = N ∗ ∗ exp(−j ∗ )g(x) = N ∗ G( )
N N 2∗π 2∗π
x=0 x=0

Où G est tel que (G(0), G(1), .., G(N − 1)) constitue la transformée de Fourier discrète
de la suite (g(0), g(1), .., g(N − 1)).

Finalement
µN
z(0) = exp(−jµx0 ) ∗ N ∗ G( )
2∗π
Pour une valeur de µ fixée, on pose

µN
C(µ) = N ∗ G( )
2∗π
On obtient :
z(0) = C(µ) ∗ exp(−jµx0 )

La valeur du gradient à la ligne y peut être représentée par g(x − x0 + ytan(θ)), et le

capteur en face de cette ligne recevra :

N
X −1
z(y) = exp(−jµx)g(x − x0 + ytan(θ))
x=0
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 38

N
X −1
= exp(−jµx0 )exp(jµytan(θ)) exp(−jµx)g(x)
x=0

= exp(−jµx0 )exp(jµytan(θ))C(µ)
La seule différence entre cette équation et celle obtenue dans le cas des images binaires est
l’apparition du facteur constant C(µ) comme amplitude du signal reçu. Ce constat montre que
des procédures identiques à celles utilisées pour les images binaires peuvent être employées
pour des images à niveaux de gris rehaussées par un opérateur gradient. Une variante de la
méthode consiste à utiliser un opérateur Laplacien au lieu d’un gradient simple. C’est un
prétraitement qui ne supprime pas les droites horizontales et verticales.

[Link] Influence sur la méthode de détermination des offsets

L’influence de l’application du gradient sur le schéma de propagation à vitesse variable est

analogue à celle de son application au schéma de propagation à vitesse constante. L’application
du gradient permet par la méthode de l’extension de la transformée de Hough de ne dénombrer
que les pixels correspondant à une rupture de niveau de gris, donc à une ligne dans l’image
quelle que soit la différence de niveau de gris entre les deux régions délimitées.

2.3.2 Simulations

Nous avons utilisé des images dont les niveaux de gris sont codés sur huit bits (256 niveaux
de gris), de taille 200 par 200 pixels. Les deux premières images en niveaux de gris qui ont été
traitées par la méthode HRSP adaptée aux niveaux de gris présentent des régions uniformes.
Dans chacun des cas seront présentées l’image de départ, l’image gradient, le résultat de
l’estimation. Deux images différentes sont employées. Elles sont dans un premier temps non
bruitées, puis bruitées (cinq pourcent des pixels de l’image sont noircis aléatoirement).
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 39

Image à traiter Image à traiter apres gradient Estimation obtenue par hrsp

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image départ image gradient estimation

Figure 2.12 — Première image en niveaux de gris

Image à traiter Estimation obtenue par hrsp

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image départ image gradient estimation

Figure 2.13 — Première image bruitée en niveaux de gris

Image à traiter Image à traiter apres gradient Estimation obtenue par hrsp

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image départ image gradient estimation

Figure 2.14 — Seconde image en niveaux de gris
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 40

Image à traiter Estimation obtenue par hrsp

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image départ image gradient estimation

Figure 2.15 — Seconde image bruitée en niveaux de gris

Les résultats obtenus sur des images non bruitées montrent que les droites sont retracées
quel que soit leur niveau de gris. Dans le cas des images bruitées le gradient appliqué entraîne
une extension des pixels de bruit, ce qui n’empêche pas la méthode de retrouver correctement
les droites. La segmentation de ces images par recherche de droites a donc donné des résultats
de bonne qualité, ce qui est conforme aux résultats déjà présentés sur des images binaires.

2.3.3 Images réelles

[Link] Introduction

Un avantage de la méthode du schéma de propagation provient des caractéristiques de sa

complexité. Celle-ci ne dépend que linéairement du nombre de pixels de valeur non nulle dans
l’image. De plus cette méthode ne pose pas de problèmes de place mémoire. Elle peut donc
être appliquée à des images réelles.

[Link] Résultats obtenus

La méthode a été appliquée sur des images réelles de voie ferrée (figure 2.16). L’objectif
de cette partie est de montrer que la méthode créée peut répondre à des besoins pratiques en
suivi automatique de trajectoire par exemple. En l’occurrence l’objectif est de rechercher la
position des rails.

Image à traiter Image à traiter apres gradient Superposition de l’image de départ et de l’estimation par hrsp

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image départ image gradient superposition estimation et image de départ

Figure 2.16 — Voie ferrée

CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 41

L’image est prétraitée par un gradient horizontal, puis les méthodes d’estimation des
angles et des offsets est mise en oeuvre. La figure 2.16 montre que les deux rails de la voie
sont retracés correctement. La méthode est donc valide sur un tel type d’images.

2.3.4 Les images en niveaux de gris : un bilan

Les procédures fondées sur un schéma de propagation à vitesse constante ou variable

sont donc opérationnelles sur des images en niveaux de gris lorsqu’un formalisme légèrement
différent de celui donné en [Link] est choisi pour représenter les images. Toutes les valeurs de
niveau de gris doivent en effet être retenues afin que les droites noires (correspondant à un
niveau de gris nul) ne soient pas les seules détectées. La complexité numérique du schéma de
propagation à vitesse variable restant relativement faible pour des images ne comportant pas
des zones de fond uniformes, des images réelles ont été traitées.

2.4 Détection de contours d’objets

2.4.1 Introduction

L’objectif de cette section est de montrer que HRSP est capable de segmenter des objets
de forme géométrique par la caractérisation de segments de droites. Dans un premier temps
on montre que l’on peut caractériser des segments de droites dans l’image, dans un second
temps on applique la méthode à la segmentation d’objets.

2.4.2 Détection de segments de droites dans des images

[Link] Méthode

La technique employée repose sur l’utilisation de plusieurs positions d’antenne (se reporter
à [Link]). Pour une position d’antenne donnée, les étapes suivantes permettent de se placer
dans un contexte favorable à l’application de la méthode :
– On recale l’image de façon à ce que l’une des droites touche le côté de l’image adjacent et
supérieur à l’antenne. Le recalage est effectué en détectant le pixel de l’objet à détecter
qui est le plus proche de ce côté.
– La méthode HRSP est appliquée, en prenant en compte le nombre total de droites
présentes dans l’image (non pas seulement celle qui touche un des côtés de l’image).
– L’image estimée est recalée d’après la valeur du premier décalage.
Cette procédure est répétée pour plusieurs positions d’antenne, de façon à ce que chacune
des droites intersecte pour l’une des positions d’antenne un côté de l’image.

[Link] Résultats obtenus :

Pour une image contenant deux et trois droites (figure 2.17) on a utilisé deux positions
d’antenne dans le cas de la première image, trois positions dans le cas de la seconde.
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 42

Superposition de l’image de départ et de l’estimation par hrsp

20 20

40 40

60 60

80 80

100 100

120 120

140 140

160 160

180 180

200 200
20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

Superposition de l’image de départ et de l’estimation par hrsp

20 20

40 40

60 60

80 80

100 100

120 120

140 140

160 160

180 180

200 200
20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image départ estimation

Figure 2.17 — Deux et trois droites isolées

Toutes les droites sont retrouvées, les droites excédentaires sont dues à la redondance
des positions d’antenne pour certaines droites, qui peuvent être trouvées pour chacune des
positions d’antenne employées.

2.4.3 Détection de contours d’objets

[Link] Méthode

Le principe de la méthode de caractérisation d’objets est analogue à celui de la méthode de

détection de droites. L’utilisation successive des quatre positions d’antenne permet de couvrir
tous les côtés de l’objet. Lorsque plusieurs objets sont présents dans l’image celle-ci est divisée
en plusieurs sous-images qui sont traitées indépendamment.
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 43

[Link] Résultats obtenus

Superposition de l’image de départ et de l’estimation par hrsp Superposition de l’image de départ et de l’estimation par hrsp

20 20

40 40

60 60

80 80

100 100

120 120

140 140

160 160

180 180

200 200
20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

Figure 2.18 — Un objet et deux objets isolés

Image à traiter par hrsp Superposition de l’image de départ et de l’estimation par hrsp

20 20

40 40

60 60

80 80

100 100

120 120

140 140

160 160

180 180

200 200
20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

Figure 2.19 — Un objet isolé, superposition de l’objet et du résultat de la segmentation

Comme le montre les figures 2.18 et 2.19 chacun des côtés de la forme géométrique
considérée est retrouvé, ce qui permet de carctériser entièrement l’objet à segmenter.
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 44

2.4.4 Conclusion

On a créé une technique permettant d’adapter la méthode HRSP au cas des objets isolés.
Cette méthode repose sur un prétraitement de l’image par translation. Les résultats obtenus
sur des segments de droites et des objets isolés montrent que cet algorithme est performant.
Cette méthode permet de réaliser une détection de contours d’objets isolés de bonne qualité.

2.5 Adaptation de l’algorithme HRSP à des images couleur

Dans le cadre de l’adaptation des méthodes de traitement d’antenne au traitement d’image

on a souhaité montrer que la méthode HRSP peut être étendue à des images couleur. Quelques
précisions théoriques concernant la représentation des images couleur et le principe de la
méthode utilisée seront donnés avant d’être détaillés et adaptés à des cas complexes dans une
partie expérimentale.

2.5.1 Quelques précisions théoriques

[Link] Introduction

Le mode de représentation des images couleur employé par défaut par le logiciel de trai-
tement est celui de la décomposition RGB (Red Green Blue). C’est un système trichromique,
c’est-à-dire que trois matrices correspondant chacune à une couleur sont utilisées pour définir
l’image. C’est celle qui servira lors de cette application aux images couleur.

Les objectifs de la version adaptée de l’algorithme HRSP sont donc de retrouver des droites
dans une image couleur, quelle que soit la couleur de ces droites. Cette version doit également
être capable de retracer les droites obtenues dans une couleur aussi proche que possible de
leur couleur originale.

[Link] Description de la méthode

L’image couleur de départ est décomposée en ses trois composantes dans la base RGB.
L’algorithme HRSP est ensuite appliqué à chacune de ces trois composantes et l’image estimée
est reconstruite à partir du résultat obtenu sur les trois composantes.

2.5.2 Résultats expérimentaux

[Link] Plan d’étude

Il est important de comprendre le mode de représentation d’une image couleur et d’adapter

les conventions de l’algorithme à ce mode de représentation, en l’occurrence on a choisi le
mode RGB. On s’intéressera aux conventions qu’il est nécessaire d’adopter en fonction du
type d’image couleur que l’on souhaite traiter ; on illustrera les résultats obtenus grâce à la
méthode par des estimations obtenues à partir de différents types d’images couleur.
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 45

[Link] Conventions et représentation des images

La modification des valeurs de pixels qui permet de satisfaire aux conventions adoptées
(voir [Link]) est éventuellement réalisée sur chacune des composantes de couleur. Dans le
cas d’une image à fond noir la valeur des pixels n’a pas à être modifiée pour satisfaire aux
conventions de la méthode. Ce type d’image donne un résultat parfait quant à la conservation
de la couleur des droites, comme le montre la figure 2.20. Or par souci de cohérence avec le
traitement des images binaires et en niveaux de gris on souhaite utiliser des images à fond
blanc. Le prétraitement consistant à prendre le négatif de l’image est alors appliqué. On
note qu’alors une droite de couleur primaire (dont deux composantes de couleur sont nulles)
correspondra à deux droites à détecter, dans les composantes complémentaires à sa couleur.
Ce cas est illustré par la figure 2.21. Une droite de couleur secondaire (correspondant à des
valeurs non nulles sur deux composante) donne lieu après prétraitement à la présence d’une
droite dans une seule composante. Ce cas est illustré par la figure 2.22.

image de départ résultat obtenu superposition image de départ et résultat obtenu

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image de départ estimation superposition image de départ et estimation

Figure 2.20 — Image couleur à fond noir

image de départ résultat obtenu superposition image de départ et résultat obtenu

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image de départ estimation superposition image de départ et estimation

Figure 2.21 — Image couleur à fond blanc et droites de couleur primaire

CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 46

image de départ résultat obtenu superposition image de départ et résultat obtenu

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image de départ estimation superposition image de départ et estimation

Figure 2.22 — Image couleur à fond blanc

[Link] Application de la méthode à divers cas pratiques

L’objectif est ici de présenter les résultats obtenus sur des cas qui peuvent être rencontrés,
et de préciser le cas échéant les prétraitements qui leur correspondent. Dans chaque exemple
une composante estimée est une matrice-image binaire. Les droites, dans les images estimées,
sont donc de couleur noire, secondaire, ou primaire.
La première image (figure 2.23) contient des droites de couleur tertiaire (correspondant à des
valeurs non nulles sur chaque composante). Chacune des composantes couleur présente alors
trois droites.
La seconde image (figure 2.24) présente un fond coloré. Dans ce cas-là un gradient est appliqué
à chaque composante couleur, tel que pour une image à niveaux de gris.
La troisième image (figure 2.25) est bruitée. Le bruit a dans ce cas moins d’influence sur
le traitement que dans une image binaire : Les pixels de couleur primaire ou secondaire ne
donnent pas lieu à des pixels de bruit sur toutes les composantes.

image de départ résultat obtenu superposition image de départ et résultat obtenu

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image de départ estimation superposition image de départ et estimation

Figure 2.23 — Image couleur à fond blanc et droites de couleur quelconque

Lors de cette adaptation de HRSP à des images couleur, le choix d’un mode de représen-
tation des images est une première étape cruciale. Lors de la mise en oeuvre des méthodes il
CHAPITRE 2. APPLICATION DE "HAUTE RÉSOLUTION ET SCHÉMA DE
PROPAGATION" À DIVERS CAS PRATIQUES 47

image de départ résultat obtenu superposition image de départ et résultat obtenu

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image de départ estimation superposition image de départ et estimation

Figure 2.24 — Image couleur à fond coloré

image de départ résultat obtenu superposition image de départ et résultat obtenu

20 20 20

40 40 40

60 60 60

80 80 80

100 100 100

120 120 120

140 140 140

160 160 160

180 180 180

200 200 200

20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200

image de départ estimation superposition image de départ et estimation

Figure 2.25 — Image couleur bruitée

est nécessaire de comprendre que le respect des conventions établies implique un changement
dans la répartition d’une droite selon les composantes couleur. Les résultats obtenus peuvent
être meilleurs que dans le cas des images binaires, notamment dans le cas des images bruitées.
Le mode de représentation adopté est celui des composantes RGB. Il pourrait être intéressant
d’étudier un autre mode de représentation des images couleur.

Conclusion
Ce chapitre a été dédié à la mise en oeuvre de la méthode HRSP, et plus particulièrement
à l’étude des performances du schéma de propagation à vitesse variable. On a montré que
cette méthode permet de résoudre le cas des droites parallèles, on a expliqué comment faire
face à certains cas difficiles. On a déterminé expérimentalement la rapidité des algorithmes
dans les cas non bruité et bruité. Une étude numérique a permis de déterminer par une
série de tests les performances des procédures d’estimation des orientations et des offsets des
droites. La méthode HRSP incluant le schéma de propagation à vitesse variable a ensuite été
adaptée. Un prétraitement par gradient a permis d’appliquer la méthode HRSP aux images
en niveaux de gris. La complexité numérique du schéma de propagation à vitesse variable
n’est pas conditionnée par le nombre de pixels de valeur non nulle dans l’image. Cela a
permis son adaptation à des images réelles de texture complexe. On s’est intéressé ensuite
à la caractérisation d’objets isolés dans des images ; puis, en adoptant la représentation Red
Green Blue et en appliquant la méthode à chacune des composantes, HRSP a été appliquée
à des images couleur.
 Conclusion et perspectives

L’objectif de ce stage de DEA était de montrer que l’on peut appliquer des méthodes
de traitement d’antenne au problème de l’estimation de droites dans une image. Lors de ce
stage, la mise en oeuvre de méthodes originales et l’élaboration de ce rapport ont été motivées
par le désir de comprendre des techniques de traitement d’antenne et de les appliquer à un
problème de traitement d’images. La description d’un problème de traitement d’antenne et
de son application à la détection de droites dans des images, la présentation du principe de
plusieurs méthodes Haute Résolution, ont permis d’aboutir à l’ensemble "Haute Résolution
et Schéma de Propagation". Les fondements théoriques de cet ensemble de méthodes ont été
expliqués. Des algorithmes appliqués aux signaux obtenus par deux schémas de propagation
différents fournissent respectivement la valeur des orientations et des offsets des droites. On
a expliqué le "schéma de propagation à vitesse constante"- et l’"extension de la transformée
de Hough". Une importance particulière a été accordée au "schéma de propagation à vitesse
variable". On s’est ainsi intéressé aux apports de cette méthode du traitement d’antenne.
Le deuxième chapitre présente les diverses applications et extensions de la méthode HRSP.
Celle-ci a été adaptée à différents types d’images. L’application d’un gradient et du schéma
de propagation à vitesse variable a permis le traitement d’images réelles. La recherche de
droites pour la segmentation par régions a donné sous certaines configurations des résultats
qui sont comparables à des méthodes de segmentation classiques. L’ensemble HRSP incluant
cette méthode a également été adapté à la caractérisation d’objets isolés et à des images
couleur.

La méthode "schéma de propagation à vitesse variable" qui a été créée est performante
au regard de son aptitude à traiter un cas difficile tel que celui des droites parallèles, et de sa
rapidité dans le cas où la texture de l’image est complexe. De nouvelles solutions pourraient
être trouvées pour faire face à des cas difficiles ; l’ensemble HRSP pourrait être adapté à un
traitement d’images en temps réel. Une adaptation à la 3D est également envisageable.
 A
ANNEXE

Titre de l’annexe 1

A.1 Organigramme
La figure A.1 représente de façon synthétique les fonctions de l’ensemble HRSP.

A.2 Glossaire
Antenne : ensemble de capteurs qui peuvent être agencés selon une géométrie particulière.
Méthode haute résolution : Les méthodes à haute résolution en traitement d’antenne et
en analyse spectrale traitent les problèmes de localisation de sources émettant de l’énergie
dans un milieu de propagation à partir d’observations mesurées sur un réseau de capteurs
et les problèmes de détection et d’estimation des composantes fréquentielles d’un signal,
elles conduisent à une certaine amélioration par rapport aux méthodes traditionnelles.
Méthode d’analyse spectrale paramétrique : méthode de détermination du contenu
spectral d’un signal, prenant en compte une information à priori telle que le nombre
de fréquences pures dans le signal.
Schémas de propagation à vitesse constante et variable : formalisme selon lequel on
fait l’acquisition de signaux par une antenne fictive placée sur le côté d’une image.
Méthode ESPRIT : Estimation of Signal Parameters by Rotationnal Invariance Tech-
niques. La méthode TLS-ESPRIT propose une solution à l’estimation de paramètres
en employant un critère des moindres carrés.
Modified Forward Backward Linear Prediction : Méthode de prédiction linéaire modi-
fiée directe rétrograde. Procédure haute résolution de détermination de fréquence adaptée
aux données de longueur courte.
ANNEXE A. TITRE DE L’ANNEXE 1 50

Figure A.1 — Organigramme de HRSP

 B
ANNEXE

Méthodes ESPRIT,
extension de la
transformée de Hough et
Modified Backward
Forward Linear Prediction

Cette annexe présente un organigramme de la méthode ESPRIT incluse dans le schéma de

propagation à vitesse constante ; cette annexe détaille les procédures liées à la détermination
des offsets : l’extension de la transformée de Hough, et de la méthode "Modified Backward
Forward Linear Prediction" incluse dans le schéma de propagation à vitesse variable.

B.1 La méthode ESPRIT

Lissage spatial : création de P vecteurs-signal, P = N + 1 − M .↓
Matrice d’observation
ZP = A(Θ).SP + NP
↓
Calcul d’une matrice de covariance
Rzz
↓
SVD
Rzz = Es Λs EsH + En Λn EnH = EΛE H
↓
Estimation de la dimension du sous-espace signal par critère MDL (figure B.1).↓

Application de la méthode TLS-ESPRIT :

ANNEXE B. MÉTHODES ESPRIT, EXTENSION DE LA TRANSFORMÉE DE HOUGH
ET MODIFIED BACKWARD FORWARD LINEAR PREDICTION 52

Figure B.1 — Critère MDL

– Sélection des d premiers vecteurs colonne de E, ils correspondent au signal : estimation

de Ês .
– Exploitation de la structure "double-antenne" : formation de Ê1 , Ê2 : M-1 premières
(resp. dernières) lignes de E.
– Détermination d’une solution "moindres carrés totaux" pour les délais de propagation
entre les deux sous-antennes. La valeur des orientations θk est déduite des valeurs de
délai de propagation : On forme la décomposition en valeurs propres de la matrice
2d × 2d :

Ê1H
 
F ΛF H =
 
Ê1 Ê2 .
Ê2H
F est partitionnée en sous matrices d × d,

F11 F12
F =[ ]
F21 F22

−1
Soient λk , k=1,2...d les valeurs propres de −F12 F22 . Les angles sont donnés par :

1 λk
θ̂k = tan−1 [ Im(ln( ))]
(µ∆) |λk |

B.2 Les méthodes relatives à la détermination des offsets

On rappelle que l’on dispose après application du schéma de propagation à vitesse variable
des valeurs d’orientation θk des droites de l’image.

B.2.1 Extension de la transformée de Hough

Les paramètres ρk associés aux valeurs d’orientation θk sont estimés en projetant l’image
selon la direction θk et en recherchant un maximum :
ANNEXE B. MÉTHODES ESPRIT, EXTENSION DE LA TRANSFORMÉE DE HOUGH
ET MODIFIED BACKWARD FORWARD LINEAR PREDICTION 53

i=Np
X
ρk = argmax
√
c (ρ − xi cos θk − yi sin θk ) k = 1, . . . , d (B.1)
ρ≤ 2N i=1

Où d est le nombre total de droites, Np le nombre de pixels à 1 contenus dans l’image et

c est la fonction réelle définie par :

cos(π/2 ∗ r/R) si|r| < R;


c(r) =
1 sinon.

Où R est un paramètre de largeur. On remarque que la fonction c a une forme proche de

la fonction delta de Dirac qui n’existe que d’un point de vue conceptuel.

On obtient les offsets d’après la connaissance des angles, par la relation

ρk = x0k cosθk

La dénomination "extension" de la transformée de Hough est apparue pour la raison

suivante : La transformée de Hough revient à détecter les intersections de courbes dans un
plan (ρ, θ). Son extension revient à détecter des maxima dans un graphe à trois dimensions.
Ces maxima sont ceux de la fonction de sommation des valeurs de pixel, tracée pour toutes
les valeurs de ρ et θ. Dans le cas précis de l’application considérée les valeurs des pentes des
droites sont connues donc on ne considère la valeur des sommations qu’en fonction des valeurs
de la coordonnée radiale, et pour une valeur de θ fixée.

B.2.2 La méthode MFBLP

Un schéma de propagation à vitesse variable et une opération de division ont permis

d’obtenir les signaux notés w contenant l’information relative aux offsets des droites.
Cette méthode est applicable dans le cas où les signaux sont reçus par une antenne linéaire
uniforme. Si N est le nombre de capteurs le vecteur des signaux reçus est de la forme :

 
1

 exp(jωk ) 

 exp(j ∗ 2ωk ) 
W = 

 exp(j ∗ 3ωk ) 

 . 
exp(j ∗ (N − 1)ωk )

où ωk est la fréquence à déterminer. Dans le cas où il existe plusieurs fréquences (c’est le cas
s’il existe plusieurs valeurs d’offsets pour une direction donnée), le vecteur signal reçu est de
la forme :
ANNEXE B. MÉTHODES ESPRIT, EXTENSION DE LA TRANSFORMÉE DE HOUGH
ET MODIFIED BACKWARD FORWARD LINEAR PREDICTION 54

     
1 1 1

 exp(jω1 )  
  exp(jω2 ) 


 exp(jωP ) 

 exp(j ∗ 2ω1 )   exp(j ∗ 2ω2 )   exp(j ∗ 2ωP ) 
W = +  + ... +  

 exp(j ∗ 3ω1 )  
  exp(j ∗ 3ω2 ) 


 exp(j ∗ 3ωP ) 

 .   .   . 
exp(j ∗ (N − 1)ω1 ) exp(j ∗ (N − 1)ω2 ) exp(j ∗ (N − 1)ωP )

Où P est le nombre total de sources (en l’occurrence dk droites d’une direction d’indice
k donnée). En appliquant une méthode d’analyse spectrale on peut retrouver la valeur des
fréquences. Il est difficile d’appliquer une transformée de Fourier discrète car la longueur
du signal est insuffisante pour aboutir à une bonne résolution en fréquence, en revanche la
méthode MFBLP est une méthode Haute Résolution adaptée. Les étapes de la méthode sont
les suivantes :

1)Pour un vecteur donnée W on forme la matrice Q de taille 2 × (N − L) × L :

 
WL−1 WL−2 ... W0

 WL WL−1 ... W1 


 WL+1 WL ... W2 


 . . . . 


 . . . . 


 . . . . 

WN −2 WN −3 ... WN −L−1
 
Q=
 
W1∗ W2∗ ... WL∗

 

 W2∗ W3∗ ... ∗
WL+1



 W3∗ W4∗ ... ∗
WL+2


. . . .
 
 
 

 . . . . 

 . . . . 
WN∗ −L WN∗ −L+1 ... WN∗ −1

La création de cette matrice revient à ordonner la donnée du signal W d’une façon particulière,
remontant selon les colonnes des derniers aux premiers échantillons du signal dans le haut de
la matrice, et descendant des premiers aux derniers échantillons du signal dans le bas de la
matrice.
On construit aussi le vecteur de taille 2 × (N − L) × 1 :
ANNEXE B. MÉTHODES ESPRIT, EXTENSION DE LA TRANSFORMÉE DE HOUGH
ET MODIFIED BACKWARD FORWARD LINEAR PREDICTION 55

 
WL

 WL+1 


 . 


 . 


 . 

WN −1
 
h=
 
W0∗

 
W1∗
 
 
.
 
 
.
 
 
 
 . 
WN∗ −L−1

L doit être choisi pour satisfaire à l’inégalité :

P ≤ L ≤ N − P/2

2)Former la décomposition en valeurs singulières de Q :

Q = U ΛV H

3)On forme la matrice Σ en fixant à 0 les L-P plus petites valeurs singulières contenues dans
Λ.

λ1 0 ... 0 0 ... 0
 

 0 λ2 ... 0 0 ... 0 


 0 0 ... 0 0 ... 0 

 0 0 ... λP 0 ... 0 
Σ= 

 0 0 ... 0 0 ... 0 


 . . . . . 

 
0 0 0 0 0

4)On forme le vecteur g d’après le calcul matriciel suivant :

 
g1

 g2 

 .  = −V ∗ Σ′ ∗ U H h

g=

 . 

 . 
gL
′
La pseudo-inverse de Σ, notée Σ , est obtenue en inversant les éléments non nuls qu’elle
contient et en la transposant.
ANNEXE B. MÉTHODES ESPRIT, EXTENSION DE LA TRANSFORMÉE DE HOUGH
ET MODIFIED BACKWARD FORWARD LINEAR PREDICTION 56

5)On détermine les racines du polynôme H, où

H(z) = 1 + g1 z −1 + g2 z −2 + ... + gL z −L

6)Les P zéros de H qui sont situés sur le cercle unité ont pour argument les valeurs
des fréquences, qui sont proportionnelles aux arguments de ces zéros, le coefficient de
proportionnalité étant −α.
 Liste des figures

1.1 Modèle du dispositif en traitement d’antenne . . . . . . . . . . . . . . . . . . 4

1.2 Droite dans une image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Choix de la position d’antenne . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Modèle de propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Pseudospectre de Music . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Création du sinogramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7 Valeurs du sinogramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.8 Sélection de zéros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.9 Méthode extension de la transformée de Hough . . . . . . . . . . . . . . . . . 20
1.10 Méthode schéma de propagation à vitesse variable . . . . . . . . . . . . . . . 21

2.1 Droites parallèles : superposition de l’image de départ et du résultat obtenu . 24

2.2 Image bruitée de départ et estimation . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Estimations réalisées : avec une petite valeur de M, avec une grande valeur de M 26
2.4 Une image conduisant à une valeur d’offset biaisée . . . . . . . . . . . . . . . 27
2.5 Zéros du polynôme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Zoom sur certains zéros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.7 Image de départ et estimation par la position d’antenne 4 . . . . . . . . . . . 29
2.8 Signal obtenu sur l’antenne 4 : le dernier capteur correspond au coin inférieur
droit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.9 Signal obtenu sur l’antenne 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.10 Image de départ et estimation par la position d’antenne 1 . . . . . . . . . . . 30
2.11 Un exemple typique d’image utilisée . . . . . . . . . . . . . . . . . . . . . . . 32
2.12 Première image en niveaux de gris . . . . . . . . . . . . . . . . . . . . . . . . 39
2.13 Première image bruitée en niveaux de gris . . . . . . . . . . . . . . . . . . . . 39
2.14 Seconde image en niveaux de gris . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.15 Seconde image bruitée en niveaux de gris . . . . . . . . . . . . . . . . . . . . . 40
LISTE DES FIGURES 58

2.16 Voie ferrée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.17 Deux et trois droites isolées . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.18 Un objet et deux objets isolés . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.19 Un objet isolé, superposition de l’objet et du résultat de la segmentation . . . 43
2.20 Image couleur à fond noir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.21 Image couleur à fond blanc et droites de couleur primaire . . . . . . . . . . . 45
2.22 Image couleur à fond blanc . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.23 Image couleur à fond blanc et droites de couleur quelconque . . . . . . . . . . 46
2.24 Image couleur à fond coloré . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.25 Image couleur bruitée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

A.1 Organigramme de HRSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

B.1 Critère MDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

 Bibliographie

[1] H. K. Aghajan et T. Kailath, A subspace fitting approach to super resolution multi-

line fitting and straight edge detection, vol. 3, pp. 121–124, 1992.
[2] H. K. Aghajan et T. Kailath, Sensor array processing techniques for super resolution
multi-line-fitting and straight edge detection, IEEE trans. on Image Processing, vol. 2,
pp. 454–465, 1993.
[3] H. K. Aghajan et T. Kailath, Application of antenna array processing to problems in
image understanding, IEEE trans. on Image Processing, 1995.
[4] S. Bourennane, Décorrélation de sources en acoustique sous-marine, JEASM, 1995.
[5] S. Bourennane et A. Bendjama, Méthodes de traitement d’antenne pour la caracté-
risation d’objets en mouvement à partir d’une séquence d’images, CD GRETSI, 2001.
[6] S. Bourennane, B. Faure et J.-L. Lacoume, Traitement d’antenne pour des sources
large bande, Annales des télécommunications, vol. 45, 1990.
[7] S. Bourennane, J.-D. Techer et J. Marot, Estimation de contours par les méthodes
haute résolution, soumis, Traitement du Signal, 2004.
[8] S. Marcos, Les méthodes Haute Résolution, traitement d’antenne et analyse spectrale,
Hermes, Paris(Fr.), 1998.
[9] J. Techer, Rapport de DEA, sous la direction de S. Bourennane : Méthodes de traite-
ment d’antennes appliquées à l’imagerie, Université de Montpellier 2, 2002.
[10] N. Yuen et B. Friedlander, Doa estimation in multipath : An approach using fourth-
order cumulants, IEEE trans. on Signal Processing, vol. 45, 1997.