Soutenance mémoire
Analyse en Composantes Indépendantes
Au début des années 90, le problème de séparation aveugle de sources a été formalisé dans le cas des mélanges linéaires instantanés ; c’est-à-dire dans le cas où le système A est un opérateur linéaire correspondant à la multiplication par une matrice A. Les premières contributions ont donné naissance au modèle d’Analyse en Composantes Indépendantes. Ce modèle est, en fait, une méthode d’analyse de données permettant d’exprimer un vecteur multidimensionnel en terme de composantes statistiquement indépendantes [36]. Dans le contexte de la séparation aveugle de sources, l’analyse en composantes indépendantes peut se définir comme l’ensemble des méthodes de séparation de sources basées sur l’hypothèse d’indépendance [21, 22]. Celle-ci permet l’estimation de la matrice de séparation B = A−1 qui maximise un critère d’indépendance [23–26]. L’équation de mélange spécifique aux mélanges linéaires est la suivante : xt = Ast (1.2) telle que,
• A est une matrice fixée
• pour tout t, st est un vecteur aléatoire à composantes statistiquement indépendantes
• toutes les composantes du vecteur sources st sont non gaussiennes sauf éventuellement une [37].
Dès lors que ces hypothèses sont vérifiées, la séparation est théoriquement possible [21, 37]. Dans le cadre aveugle, la matrice A est inconnue. D’autre part, lorsque A est de taille N ×Q nous pouvons alors distinguer trois types de mélanges selon les valeurs de N et Q :
– Mélanges déterminés (N = Q) : un mélange pour lequel il y a autant de sources que de capteurs ; pour la séparation d’un tel mélange, identifier la matrice de mélange A ou son inverse B fournit directement les sources à condition que la matrice A soit inversible (régulière).
– Mélanges sous-déterminés (N < Q) : Ici, le nombre de capteurs N est inférieur au nombre de sources Q. Dans ce cas, la matrice de mélange A est non inversible à gauche, et même en ayant A la déduction des sources s n’est pas simple. Nous avons alors un problème à double complexité : d’abord il faut identifier la matrice de mélange A et ensuite il faut restaurer les sources s. Sans a priori suffisamment informatif, la solution est impossible. Dans le cas de mélange linéaire, lorsque la matrice A est connue, le problème se résout à un vecteur aléatoire près [38]. Si la matrice A est inconnue et les sources sont discrètes ou parcimonieuses, une solution est possible.
– Mélanges sur-déterminés (N > Q) : dans un mélange sur-déterminé le nombre d’observations N est supérieur aux nombres de sources Q.
Dans ce cas, la séparation peut se faire en se ramenant au cas déterminé. En effet, à condition que la matrice de mélange soit de rang plein, on peut réduire la dimension des observations à l’aide d’un blanchiment ou d’une analyse en composantes principales. Dans ce travail, nous allons nous limiter au cas déterminé N = Q. Dans le cadre aveugle, des indéterminations de permutations et de facteurs d’échelles sont indissociables de la séparation par les méthodes d’analyse en composantes indépendantes. à cause de ces indéterminations, l’estimation de la puissance et de l’ordre des sources est impossible. Toutefois, des contraintes imposées permettent de remédier à ces ambiguïtés : on peut imposer l’unicité des éléments diagonaux de la matrice du mélange A ou fixer arbitrairement la puissance des sources estimées par normalisation ou pré-blanchiment. En se basant sur le modèle d’analyse en composantes indépendantes, de nombreux algorithmes ont été proposés [33]. Nous citons, l’algorithme JADE [39] dont le nom vient de l’acronyme anglais de « Joint Approximation Diagonalization of Eigenmatrices ». Son principe est basé sur la diagonalisation d’un tenseur de cumulants d’ordre quatre. En effet, la séparation est atteinte lorsque le critère d’indépendance est maximisé c’est-à-dire lorsque les éléments non diagonaux du tenseur tendent vers zéro. Nous citons aussi l’algorithme CoM2 qui maximise une fonction de contraste basée sur les cumulants d’ordre quatre [21] : le contraste dans cet algorithme correspond à la somme des modules carrés des cumulants marginaux des sorties. Aussi, l’algorithme Fast-ICA a été ensuite proposé [40].
Parcours de Hilbert-Peano
L’application des modèles de chaînes de Markov dans la segmentation ou la séparation d’images nécessite la transformation d’une image (bidimensionnelle) en une chaîne monodimensionnelle, ce qui peut être réalisé avec un parcours de Hilbert—Peano représenté sur la figure 3.1. Ce parcours fractal est obtenu en reproduisant un élément de base, dit « générateur ». Conformément à la figure 3.1, le premier instant de la chaîne de Markov correspond au pixel de la dernière ligne et première colonne, le deuxième instant correspond au pixel de l’avant dernière ligne et première colonne, le troisième instant correspond au pixel de l’avant dernière ligne et deuxième colonne et ainsi de suite. Nous rappelons qu’il existe d’autres types de parcours, à titre d’exemple, le parcours « ligne par ligne » ou « colonne par colonne » qui sont aussi simples et faciles à réaliser. Néanmoins, le parcours d’Hilbert-Peano donne des meilleurs résultats, en segmentation d’images. En effet, avec une courbe d’Hilbert-Peano, les pixels appartenant à la même région de l’image restent, globalement, voisins dans la chaîne [61,87], ce qui constitue l’intérêt principal de ce parcours par rapport aux parcours simples de type « ligne par ligne » ou « colonne par colonne ». Chaque image est balayée et transformée en chaîne monodimensionnelle. L’ensemble des chaînes obtenues est considéré comme une réalisation multidimensionnelle bruitée d’une chaîne de Markov. Dans ce qui suit, nous proposons donc de comparer les performances des algorithmes fondés sur les modèles CMCouples-BI et CMT avec celles d’un algorithme basé sur le modèle CMC-BI. Nous considérons en premier, des chaînes simulées, nous enchaînerons avec des images réelles bruitées synthétiquement. Nous allons ensuite appliquer nos algorithmes aux images issues de manuscrits scannées. Ces simulations valident l’efficacité de nos algorithmes par rapport à ceux fondé sur un modèle CMC-BI.
Chaînes synthétiques : séparation non supervisée
Notre méthode de séparation pour le cas de données à états discrets consiste à effectuer une segmentation non supervisée par un algorithme basé sur le modèle CMCouple-BI. Nous comparons ses performances par rapport à l’algorithme basé sur le modèle CMC-BI. Pour les deux algorithmes la segmentation est réalisée au sens du MPM. L’estimation des paramètres est réalisée avec les algorithmes EM et ICE adaptés à chaque modèle. Nous présentons les résultats de la manière suivante : pour chaque structure temporelle des sources nous comparons les performances des modèles CMCouples-BI et CMC-BI selon la nature du bruit. Les observations sont indépendantes temporellement conditionnellement aux sources ; de plus, à tout instant t le vecteur observation xt dépend seulement de st. Et d’autre part, une chaîne vérifiant le modèle 3 : les sources sont i.i.d tandis que le bruit est un « bruit CMCouple-BI ». Dans le tableau 3.2, les sources sont générées selon une distribution markovienne, les deux types de bruits (i.i.d et “bruit CMCouple-BI ») sont considérés. Notons que malgré la structure du “bruit CMCouple » inspiré du modèle des CMCouples, le processus Z généré n’est pas une CMCouple-BI. En effet, dans une CMCouple-BI le processus S ne doit pas être une chaîne de Markov. Or, dans nos données considérées le processus S est soit de Markov soit i.i.d qui est un cas particulier de chaînes de Markov. Nous allons, dans ce qui suit, comparer d’une part, les performances de l’algorithme EM par rapport à l’algorithme ICE dans le cadre du modèle de CMCouple-BI. Et d’autre part, nous comparerons les taux de composantes mal segmentées dans le modèle CMCouple-BI par rapport au modèle CMCBI. La restauration est complètement non supervisée, tous les paramètres sont considérés inconnus. Les résultats sont présentés dans les tableaux 3.1 et 3.2 pour des échantillons de taille T = 2000 et pour 25 itérations. Les paramètres des modèles ont été choisis aléatoirement. Pour les Données 1, les taux de sites mal classés obtenus avec un modèle CMCouple-BI et CMC-BI sont comparables (environ 20%). En effet, les sources et le bruit sont i.i.id, aucune corrélation temporelle n’est présente. Nous remarquons que malgré la complexité de l’étape de l’estimation de paramètres dans la segmentation avec les CMCouples-BI par rapport aux CMC-BI (le nombre de paramètres à estimer pour les CMCouples-BI est plus important que dans les CMC-BI), le modèle CMCouple-BI permet une bonne estimation de paramètres. Il est ainsi plus riche que les CMC-BI. D’autre part, dans l’expérimentation avec les Données 3 le bruit est « CMCoupleBI ». La segmentation par les CMCouple-BI est plus avantageuse (environ 32%) par rapport aux CMC-BI (environ 36%) qui ne permet pas de prendre compte de la complexité du bruit. Notons que les taux de sites mal classés dans les Données 3 sont globalement plus élevés que pour un bruit i.i.d, ceci est dû à la nature complexe du bruit : nous rappelons que le « bruit CMCouple-BI » dans le cas gaussien est un mélange d’un grand nombre de gaussiennes. Nous remarquons aussi les performances des algorithmes basés sur le modèle CMCouple-BI avec l’algorithme EM et ICE sont comparables. Pour les résultats présentés dans le tableau 3.2, les sources sont de Markov. Et pour les Données 2 le bruit est i.i.d, le processus simulé est une CMC-BI. Nous remarquons que les taux de sites mal classés obtenus par les modèles CMCouple-BI et CMC-BI sont quasiment identiques (environ 11%) malgré le nombre important de paramètres à estimer pour les CMCouples-BI. Ce modèle est alors riche et robuste, il généralise le modèle des CMC-BI [54] et permet une bonne estimation de paramètres ainsi qu’une bonne qualité de segmentation. La richesse du modèle CMCouple-BI par rapport aux CMC-BI se manifeste remarquablement lorsque le bruit n’est plus simple. En effet, pour les Données 4 dans lesquels nous avons un « bruit CMCouple-BI » le taux de sites mal classés avec un modèle CMC-BI est plus important (environ 38%) qu’avec le modèle CMCouple-BI (environ 31%), qui permet une meilleure modélisation.
|
Table des matières
Introduction
1 Contexte et généralités
1.1 Séparation de sources
1.1.1 Analyse en Composantes Indépendantes
1.1.2 Mélanges bruités
1.2 La segmentation
1.3 Séparation et segmentation
1.3.1 Chaînes de Markov
1.3.2 Chaînes de Markov cachées
1.4 La segmentation par chaînes de Markov cachées
1.4.1 Approche supervisée
1.4.2 Estimation des paramètres
a L’algorithme EM
b L’algorithme ICE
c L’algorithme SEM
2 Les chaînes de Markov couples et triplets
2.1 Chaînes de Markov Couples
2.1.1 CMCouple : approche supervisée
2.1.2 CMCouple-BI : le modèle
2.1.3 Estimation des paramètres
a Estimation EM
b Estimation ICE
2.2 Chaînes de Markov Triplets
2.2.1 CMT : le modèle
2.2.2 Approche supervisée
2.2.3 Estimation des paramètres
3 Application des CMCouple-BI et CMT à la séparation de sources
3.1 Modèle du mélange
3.2 Parcours de Hilbert-Peano
3.3 Applications des CMCouples
3.3.1 Application aux chaînes synthétiques
3.3.2 Séparation d’images réelles bruitées synthétiquement
3.4 Applications des CMT aux chaînes synthétiques
3.5 Séparation des images réelles
3.5.1 Séparation de documents manuscrits
3.5.2 Séparation d’images photographiques
4 Extension du Modèle d’Analyse en Composantes Indépendantes
4.1 Variables latentes
4.1.1 Modèle des sources étudiées
a Modèle de données : Exemple 1
b Modèle de données : Exemple 2
4.2 Méthode de séparation, le modèle d’ACI étendu
4.2.1 Données complètes et incomplètes
4.2.2 Estimation conditionnelle itérative
4.2.3 Applicabilité d’ICE et distributions supposées
a Distribution P(st| rt) supposée dans ICE
b Distribution P(rt; η) supposée dans ICE
b.1 Processus latent i.i.d
b.2 Processus latent de Markov
4.3 Algorithme de séparation
4.3.1 Algorithme ACI/ICE
4.3.2 Précisions dans le cas d’un processus latent i.i.d
4.3.3 Processus latent de Markov
4.4 Résultats de simulations
4.4.1 Processus latent i.i.d et η connu
a Résultats de l’Exemple 1
b Résultats de l’Exemple 2
4.4.2 Processus latent i.i.d et η inconnu
4.4.3 Processus latent de Markov
5 Conclusion
Télécharger le rapport complet
