La Séparation Aveugle de Sources (SAS)

Télécharger le fichier original (Mémoire de fin d’études)

La SAS en pratique

Idéalement, le but de la SAS est de retrouver avec exactitude les signaux sources à l’origine des observations que l’on a à disposition. En réalité, le problème posé induit l’estimation des sources avec quelques degrés d’incertitude, qui dépendent du modèle de mélange et des hypo-thèses possibles sur les sources (propriétés des sources), ainsi que de la méthode utilisée. On appelle ces incertitudes des « indéterminations ».
Très souvent, les sources sont estimées avec les indéterminations suivantes :
– une possible permutation dans l’ordre des signaux sources retrouvés,
– un facteur d’échelle sur les signaux sources.
Ces indéterminations peuvent être mises en évidence facilement dans le cas du mélange linéaire instantané. On voit bien, en eﬀet, sur le modèle défini par l’équation (2), que si l’ordre des sources (et des coeﬃcients associés) est inversé cela donne le même résultat pour les observa-tions. Il en est de même si on multiplie une source sj par un facteur d’échelle et qu’on divise son coeﬃcient aij par ce même facteur.
Néanmoins, ces indéterminations peuvent être dans certains cas réduites (essentiellement celle liée au facteur d’échelle) en ajoutant à la méthode de SAS des contraintes supplémentaires [5].
Le nombre N de sources présentes dans les mélanges joue aussi un rôle important. Il est souvent supposé connu, mais peut aussi, suivant les applications, être estimé en amont (par exemple par Analyse en Composantes Principales, ACP) ou en parallèle avec l’extraction des sources (c’est par exemple le cas de certaines méthodes en télédétection comme on le verra au chapitre suivant). Suivant la valeur de N, par rapport au nombre d’observations M, on a trois configurations diﬀérentes du problème de SAS, qui peuvent nécessiter des méthodes diﬀérentes :
– Lorsque N est égal à M, on parle de mélanges « déterminés ».
– Si N est inférieur à M, on a plus d’observations que de sources pour résoudre le problème, on est donc au moins dans un cas équivalent au précédent, si ce n’est plus avantageux. On parle dans ce cas de mélanges « sur-déterminés ».
– Si N est supérieur à M, on se retrouve avec plus de signaux inconnus que de données, on est alors dans le cas « sous-déterminé ». La résolution du problème est dans ce cas-là plus diﬃcile et nécessite des contraintes supplémentaires.
Dans tous les cas, le nombre d’inconnues est souvent supérieur aux données, car en plus des sources il y a aussi les paramètres de mélange à estimer. Les méthodes de SAS nécessitent donc des contraintes supplémentaires sur les sources et/ou paramètres de mélange pour diminuer le champ des solutions possibles au problème. Ce sont les diﬀérentes natures de contraintes impo-sées qui ont donné lieu aux diﬀérentes familles de méthodes de SAS existantes. Ces contraintes ou hypothèses dépendent bien sûr du type de données que l’on désire traiter et donc de l’ap-plication.
Il est possible de trouver plus d’informations sur les méthodes de SAS en général ainsi qu’un panorama des méthodes dans [3, 4, 5, 6, 7, 8].
On s’intéresse dans la suite aux méthodes de SAS les plus répandues dans la littérature, mais uniquement en rapport avec les modèles de mélange qui nous intéressent : le cas des mélanges linéaires instantanés et le cas des mélanges linéaires quadratiques. On présentera les classes de méthodes de SAS les plus connues dans le cadre général. Le cas particulier de la télédétection où des hypothèses supplémentaires sur les données peuvent intervenir, sera présenté dans la partie télédétection. Notons ici, que le terme « démélange » est aussi parfois utilisé en télédétection pour désigner la séparation de sources.

Méthodes pour les mélanges linéaires instantanés

Méthodes basées sur l’ICA

Les premières méthodes de SAS ont été des méthodes basées sur l’Analyse en Composantes Indépendantes ou l’ICA (pour Independent Component Analysis, en anglais). Cette famille de méthodes englobe les méthodes exploitant l’indépendance statistique des signaux sources entre eux. Ces méthodes ne pourront pas être utilisées dans les deux problématiques qui nous intéressent, car comme on le verra nos sources dans les deux cas sont corrélées. Néanmoins, il nous paraît important de présenter cette classe de méthodes avec laquelle est née la SAS et qui est très utilisée.
En ICA, les signaux sources sont supposés aléatoires, mais les signaux vérifiant à la fois les trois propriétés suivantes ne peuvent être séparés :
– pour chaque signal source, les variables aléatoires associées aux échantillons du signal sont statistiquement indépendantes,
– le signal est « identiquement distribué » et donc stationnaire,
– la loi de probabilité associée au signal est gaussienne.
Il a, en eﬀet, été démontré, que séparer des signaux i.i.d. (indépendants et identiquement distribués) gaussiens est impossible [9]. Les méthodes ICA sont donc généralement basées sur la non vérification de l’une de ces propriétés, ce qui donne principalement deux classes [10]. La première correspond aux méthodes exploitant la non gaussianité et la deuxième aux méthodes exploitant la structure des signaux (sources non i.i.d.) :
Méthodes basées sur la non gaussianité Cette classe de méthodes suppose donc les si-gnaux non gaussiens et peut alors être appliquée à des sources i.i.d., c.à.d. les signaux réunissant les deux premières caractéristiques citées plus haut. Ces méthodes sont les plus utilisées dans la littérature. Elles exploitent les statistiques d’ordre supérieur à deux, et sont donc dites méthodes statistiques d’ordre supérieur. Sans l’hypothèse de non gaussianité des signaux, les statistiques d’ordre supérieur à deux n’apporteraient aucune information supplémentaire.
Il existe parmi cette classe de méthodes des approches variées suivant les statistiques uti-lisées, les plus simples sont fondées sur les moments ou cumulants d’ordre supérieur.
L’une des premières méthodes d’ICA proposée par C. Jutten et J. Hérault dans les années 80 (méthode détaillée dans [11]) est d’ailleurs basée sur des statistiques d’ordre supérieur. La méthode utilise un algorithme adaptatif de type réseau de neurones et est basée sur l’annulation des moments croisés généralisés des sorties du réseau.
Depuis, diﬀérentes approches ont été proposées, les plus répandues peuvent être classées comme suit :
• Maximisation de la non-gaussianité : Cette approche est l’une des plus utilisées en ICA. Le principe est de forcer les signaux en sortie de la méthode (les sources estimées) à être les plus non-gaussiens possible. Le principe découle du théorème de la limite centrale, selon lequel les combinaisons des sources (donc les observations) tendent vers des gaussiennes. L’un des critères les plus utilisés pour mesurer la gaussianité est le kurtosis ou auto-cumulant d’ordre 4 [12]. On trouve aussi des mesures de non gaussianité basées sur l’entropie : l’entropie diﬀérentielle ou la néguentropie.
Parmi les méthodes les plus connues basées sur la maximisation de la non-gaussianité, on trouve FastICA [13].
• Estimation du maximum de vraisemblance : Maximiser la vraisemblance permet de trouver les sources et paramètres du mélange qui maximisent la densité de probabilité des observations. Les premières méthodes ont été proposées dans [14]. On peut aussi citer comme exemples de travaux [15] et [16].
• Minimisation de l’information mutuelle : Cette approche, dérivée de la théorie de l’in-formation, est basée sur la minimisation de l’Information Mutuelle (IM) entre les sorties (sources recherchées), ce qui consiste à maximiser l’indépendance entre elles. En eﬀet l’IM est nulle si et seulement si les sources estimées sont statistiquement indépendantes. Cette approche a été utilisée pour la première fois dans [9]. On peut aussi citer [17] et [18] comme exemples de travaux utilisant ce critère.
• Approches tensorielles : Ces approches sont basées sur l’utilisation de cumulants d’ordre supérieur, généralement d’ordre 4. Un tenseur de cumulants d’ordre 4 est un opérateur linéaire défini par les cumulants croisés d’ordre 4 des données. Comme exemple de ce type d’approche on peut citer la méthode JADE (Joint Approximate Diagonalization of Eigenmatrices) [19].
Méthodes exploitant la structure des signaux Ce sont des méthodes supposant les sources non i.i.d. (et pouvant être gaussiennes). On retrouve au sein de cette classe deux sortes de méthodes :
• On trouve les méthodes exploitant la non indépendance des échantillons au sein d’un même signal source. Les valeurs de chaque signal à diﬀérents échantillons ne sont pas supposées statistiquement indépendantes. Diﬀérents algorithmes ont été proposés dans ce cadre comme la méthode SOBI (Second-Order Blind Identification) pour signaux stationnaires présentée dans [20], qui est une méthode beaucoup utilisée.
• La deuxième catégorie concerne les méthodes exploitant l’hypothèse de non stationnarité des sources. Voir par exemple [21].
Ces deux approches sont généralement basées sur l’utilisation des matrices de covariance. Elles ont donc l’avantage d’utiliser uniquement les statistiques d’ordre 2 et permettent de relâcher l’hypothèse d’indépendance et de la remplacer par une hypothèse de non corrélation. Elles permettent de séparer aussi bien des sources gaussiennes que non gaussiennes.
Pour plus de détails sur toutes ces méthodes ICA il est possible de se référer à [4, 5, 7, 8] et aux références qui y sont citées.

Méthodes basées sur la parcimonie (SCA)

L’Analyse en Composantes Parcimonieuses ou SCA (pour Sparse Component Analysis, en anglais) est une classe de méthodes de SAS apparue il y a tout juste une dizaine d’années [22], [23]. Elle s’appuie sur l’hypothèse que les sources sont parcimonieuses soit dans leur repré-sentation originale soit après décomposition sur un dictionnaire. Un signal est dit parcimonieux si la plupart de ses coeﬃcients dans un domaine de représentation donné sont nuls.
Dans le cas de la séparation de sources, on a besoin plus particulièrement de représenta-tions parcimonieuses « conjointes » des sources [24], c.à.d que le fait que les sources aient des représentations où la plupart des coeﬃcients sont nuls ne suﬃt pas. Pour pouvoir exploiter la parcimonie dans la séparation de sources, l’approche la plus simple est d’isoler chacune de ces sources individuellement dans des zones des signaux observés. L’idéal est alors d’avoir un dictionnaire de représentation pour lequel les sources ont des supports disjoints. Mais dans certaines méthodes il suﬃt d’avoir, pour chaque source du mélange, une zone dans les signaux observés sur laquelle elle est seule à être non nulle (dans le cas de signaux spectraux par exemple, il s’agirait d’avoir une zone spectrale sur laquelle une seule des sources est non nulle ; dans le cas d’images, cela correspondrait à avoir une zone de pixels où une seule source est présente). Selon les hypothèses qu’on fait au départ sur les sources, il y a donc, dans le cadre de la SCA, trois catégories de méthodes :
• Méthodes basées sur l’hypothèse de fortes conditions de parcimonie, appelées WDO (pour W-Disjoint-Orthogonality en anglais). Des sources sont dites WDO si, dans chaque point du domaine d’analyse, une seule de ces sources est active. Cette hypothèse suppose donc que les sources sont de supports complètement disjoints. L’avantage de la WDO est qu’elle permet de séparer les sources dans les cas dits « sous-déterminés » (cas où le nombre de sources est supérieur au nombre d’observations) par simple « masquage » du domaine d’analyse [25], [26].
• Méthodes « quasi-non-parcimonieuses » pour lesquelles il suﬃt que chaque source soit iso-lée dans certaines petites zones du domaine d’analyse, et peu importe s’il y a recouvre-ment des sources ailleurs. Ces méthodes commencent généralement par détecter les zones mono-sources (où une seule source est présente) dans les observations, afin de les utiliser pour estimer la matrice de mélange. Les sources peuvent ensuite être déduites facilement (par simple inversion de la matrice de mélange dans le cas de mélanges déterminés). On peut citer dans ce cadre les méthodes LI-TEMPROM et LI-TIFROM [27] qui utilisent les variances des rapports d’observations pour détecter les zones mono-sources. D’autres méthodes comme LI-TEMPCORR et LI-TIFCORR [28] utilisent plutôt la corrélation pour la détection des zones. Dans [29] c’est une ACP qui est utilisée pour détecter les zones mono-sources.
• Approches « hybrides » se situant entre les deux catégories de méthodes précédentes. Certaines relâchent l’hypothèse de WDO dans des cas particuliers, d’autres utilisent une mesure de confiance sur la « qualité mono-source » des points du domaine d’analyse mais nécessitent quand même une forte parcimonie pour pouvoir estimer le mélange ou reconstruire les sources [29] [30].
Cette classe de méthodes sera diﬃcilement applicable à nos problématiques car cette hy-pothèse de parcimonie « conjointe » n’est a priori pas vérifiée par nos données.

Méthodes bayésiennes

Des approches bayésiennes ont aussi été proposées dans le cadre de la séparation de sources. Ce genre d’approches est basé sur l’utilisation de la règle de Bayes. Le principe de ces méthodes, qui repose sur l’attribution de lois de probabilités aux données recherchées, est le suivant (en considérant la définition matricielle (4) du modèle de mélange auquel on rajoute une matrice pour modéliser un bruit additif) :
– Ecrire la vraisemblance des inconnues p(X | A, S)
– Attribuer des lois a priori aux inconnues du problème : p(S) et p(A). Cela permet de décrire la connaissance a priori que l’on a du problème, mais aussi de restreindre l’espace des solutions possibles.
– La loi de Bayes permet alors de déduire la loi a posteriori p(A, S | X), qui est utilisée pour estimer les inconnues. Des estimateurs sont alors utilisés tels que le maximum a posteriori (MAP) ou la moyenne a posteriori (MP).
Ces méthodes font ensuite appel à un algorithme d’optimisation et intégration itératif tel que l’algorithme EM (Expectation Maximization) ou des modélisations par chaînes de Markov ca-chées. On peut citer comme exemples de travaux [31], [32]. D’autres exemples de travaux seront cités dans les problématiques de télédétection et d’astrophysique (chapitre 1 de la partie 1 et chapitre 1 de la partie 2). L’approche bayésienne peut donner des résultats intéressants mais a l’inconvénient de souvent demander un grand coût calculatoire. Pour plus de références et de détails sur ces approches il est possible de se référer à [3] et [4].

Méthodes basées sur la NMF

Les méthodes de Factorisation en Matrices Non-négatives ou NMF (pour Non-negative Matrix Factorization, en anglais) sont des méthodes basées sur la positivité ou non négativité (les deux sont équivalents et veulent dire positif ou nul) des données. Par données on entend les observations, les sources et les coeﬃcients de mélange. Un intérêt particulier est accordé à ces méthodes qu’on détaille ici un peu plus que les autres, car étant donné la positivité de nos données, elles vont être celles qui seront les plus exploitées dans notre travail.
Initialement proposée par Paatero et Tapper [33][34], la NMF a surtout été beaucoup étudiée dans la littérature depuis les travaux de Lee et Seung [35][36].
Le principe de base est le suivant : Etant donné une matrice non négative W ∈ RP+×L, et une dimension réduite K (avec souvent K ≤ min(P, L)), la NMF consiste à trouver deux matrices non négatives Z ∈ RP+×K et V ∈ RK+×L, qui factorisent le mieux W , c-à-d telles que W =ZV (9) à une erreur d’approximation près.
Souvent la dimension réduite K dépend de l’application et est imposée par le problème que l’on cherche à résoudre. Il en est de même pour le contenu des matrices produit qui varient aussi suivant l’application et les données traitées et peuvent avoir des significations physiques diﬀérentes.
La NMF a été utilisée pour trouver une représentation qui met en évidence de l’information cachée (dans le cas de la séparation de sources cette information est constituée des sources). Appliquée initialement pour décrire une image représentant un visage comme une combinaison linéaire d’images représentant ses diﬀérentes composantes (nez, bouche..), elle a depuis été exploitée pour diﬀérentes applications : classification d’images, débruitage, extraction de texte (text mining en anglais), séparation de sources…[37][38].
En termes de séparation de sources, Z est alors ici la matrice de mélange et V contient les sources, dans ce cas-là K correspond au nombre de sources que l’on cherche à séparer. Néanmoins, l’hypothèse de positivité étant appliquée aux deux matrices produit, le problème est ici symétrique (contrairement aux méthodes ICA par exemple) et on peut facilement écrire W t = V tZt, ce qui mène à inverser les rôles de matrice « source » et « mélange », sans rien changer au problème ni à sa résolution.
Les algorithmes de NMF sont des algorithmes itératifs qui consistent généralement à mini-miser un critère, ou fonction coût choisie. Il s’agit de trouver les matrices produit qui permettent de minimiser la « distance » entre la matrice des observations et le produit des facteurs estimés, sous les contraintes de positivité : min D(W ||ZV ), avec Z ≥ 0, V ≥ 0 (10) Z,V où la notation D(.||.) désigne la mesure de distance (ou de divergence, de similarité…) entre deux matrices ou vecteurs.

Table des matières

INTRODUCTION GENERALE
1 Présentation du travail et contexte
2 Plan du manuscrit
Etat de l’art en SAS
1 La Séparation Aveugle de Sources (SAS)
1.1 Présentation
1.2 Types de mélanges usuels
1.2.1 Mélanges linéaires
1.2.2 Mélanges non linéaires
1.3 La SAS en pratique..
2 Méthodes pour les mélanges linéaires instantanés
2.1 Méthodes basées sur l’ICA
2.2 Méthodes basées sur la parcimonie (SCA)
2.3 Méthodes bayésiennes
2.4 Méthodes basées sur la NMF
2.4.1 Convergence et unicité de la solution
2.4.2 Quelques algorithmes de type NMF
3 Méthodes pour les mélanges linéaires quadratiques
4 Conclusion et Positionnement de la thèse
Partie 1 : Télédétection
Glossaire
Introduction
1 Le démélange spectral
1.1 Méthodes linéaires
1.1.1 Méthodes supervisées
1.1.2 Méthodes non supervisées
1.2 Méthodes non linéaires
1.2.1 Sans modèle de mélange défini
1.2.2 Avec modèle spécifique : linéaire-quadratique ou bilinéaire
1.3 Conclusion
2 Modèle de mélange physique
Introduction
2.1 Le modèle de mélange physique
2.1.1 Présentation de la méthode aboutissant au modèle
2.1.2 Luminance au niveau du sol à fine résolution
2.1.3 Luminance au niveau de la surface équivalente
2.1.4 Identification donnant le modèle de mélange
2.2 Validation du modèle de mélange
2.2.1 Description d’AMARTIS
2.2.2 Méthodologie
2.2.3 Description des données
2.2.3.1 Scènes simples géométriques
2.2.3.2 Scène urbaine
2.2.4 Résultats et discussions
2.2.4.1 Analyse globale
2.2.4.2 Analyse des différents termes
2.2.4.3 Vérification de la propriété de conservation du flux
2.3 Simplification du modèle de mélange
2.3.1 Résultats
2.3.1.1 Termes ED,k
2.3.1.2 Termes Ediff,m
2.3.2 Simplifications et modèle obtenu
2.3.3 Obtention du modèle linéaire quadratique invariant
2.4 Vers le démélange spectral
2.4.1 Modèle de mélange final adapté au démélange spectral
2.4.2 Hypothèse possibles sur les coefficients de mélange ?
Conclusion
3 Méthodes de démélange spectral
Introduction
3.1 Problématique
3.2 Vers l’exploitation de la positivité
3.2.1 Pourquoi la positivité ?
3.2.2 Première méthode : NMF linéaire multiplicative étendue
3.3 Première méthode proposée : NMF LQ Gradient
3.3.1 Cas de 2 sources (M = 2)
3.3.1.1 Ecriture du critère
3.3.1.2 Calcul des gradients
3.3.1.3 Les mises à jour
3.3.1.4 Algorithme final
3.3.2 Cas général de M sources
3.4 Deuxième méthode : NMF LQ Gradient-Newton
3.5 Troisième méthode proposée : NMF LQ Multiplicative
Conclusion
4 Tests et performances
Introduction
4.1 Critères de performances
4.2 Conditions de test
4.2.1 Méthodes testées
4.2.2 Initialisation des algorithmes
4.2.2.1 Initialisations sans information a priori : init 1 et init 2
4.2.2.2 Initialisation avec information a priori sur les coefficients : init 3
4.2.3 Présentation des données synthétiques
4.2.3.1 Génération des images
4.2.3.2 Matériaux utilisés
4.2.3.3 Cas étudiés
4.3 Performances globales des 5 algorithmes
4.3.1 Cas 1 : Mélanges de 2 matériaux
4.3.1.1 Comparaison des 5 algorithmes
4.3.1.2 Analyse des résultats à travers l’algorithme LQ mult
4.3.2 Cas 2 : Mélanges de 3 matériaux
4.3.2.1 Comparaison des 5 algorithmes
4.3.2.2 Analyse des résultats à travers l’algorithme LQ mult
4.3.2.3 Synthèse préliminaire
4.3.3 Cas 3 : Mélanges de 3 matériaux, sans contribution s1 ⊙ s2
4.3.4 Cas 4 : Mélanges de 3 matériaux, sans s1 ⊙ s2 et sans s3
4.3.4.1 Résultats des différents algorithmes
4.3.4.2 Analyse des résultats avec l’algorithme LQ Grd-Newt
4.3.4.3 Tests avec init 3
4.4 Performances en fonction du nombre de pixels
4.5 Première tentative avec des images réelles
4.5.1 Description des données
4.5.2 Comment interpréter les résultats ?
4.5.3 Présentation des résultats
4.5.3.1 Imagette 1
4.5.3.2 Imagette 2
4.5.3.3 Imagette 3
4.5.3.4 Imagette 4
4.5.4 Conclusion sur les résultats avec données réelles
Conclusion
Conclusion et perspectives
Partie 2 : Astrophysique
Introduction
1 Méthodes de SAS en astrophysique
1.1 Méthodes ICA
1.2 Méthodes bayésiennes
1.3 Autres types de méthodes
2 Présentation des données et modèle de mélange
Introduction
2.1 Mécanisme de formation des données
2.2 Hypothèses sur la PSF et les données
2.3 Modèle de mélange
2.4 Présentation des données
2.5 Etude des données MUSE et choix méthodologique
Conclusion
3 Première approche de séparation de sources
Introduction
3.1 Présentation de la méthode : LSQ-NMF
3.1.1 Application de la NMF à notre problématique
3.1.2 Initialisation : moindres carrés (LSQ) avec FSF partiellement connue
3.2 Critères de performances utilisés
3.3 Tests préliminaires pour étudier les données
3.3.1 Rôle des étoiles dans le voisinage du champ étudié
3.3.2 Etude en fonction de la longueur d’onde
3.4 Cas de test 1 : erreur sur FSF simulée par du bruit
3.5 Cas de test 2 : erreur sur FSF plus réaliste
3.5.1 Modèle de la FSF
3.5.2 Tests et résultats
Conclusion
4 Deuxième approche de séparation de sources
Introduction
4.1 Présentation de la méthode : LSQ-Grd
4.1.1 Principe de la méthode
4.1.1.1 Idée
4.1.1.2 Critère minimisé
4.1.1.3 Hypothèses
4.1.1.4 Algorithme proposé
4.1.1.5 Initialisation
4.1.2 Calcul du gradient pour l’estimation de (α, β)
4.1.3 Cas bruité
4.2 Critères de performances utilisés
4.3 Premiers tests et résultats
4.3.1 Cas sans bruit
4.3.2 Cas avec bruit
4.3.2.1 (α, β) connus
4.3.2.2 (α, β) inconnus
4.4 Version accélérée de la méthode
4.5 Résultats de tests de la version accélérée
4.5.1 Cas sans bruit
4.5.2 Cas avec bruit
Conclusion
Conclusion et perspectives
CONCLUSION GENERALE
Bibliographie
Publications scientifiques de l’auteur 189