Embed Size (px)
Citation preview
RECONNAISSANCE DE FORMES
IAR-6002
Extraction des caractéristiques
Introduction Extraction des caractéristiques
Introduction
L’extraction consiste à trouver un espace des caractéristiques de dimension d à partir d’un espace original de D caractéristiques
La compression de l’information est accomplie par la projection des caractéristiques originales dans un espace de dimension inférieure et ce en éliminant la redondance de l’information
Cette projection prend la forme:
x = A(y)
Introduction
Processus de projection de l’ensemble des caractéristiques originales dans un autre espace de caractéristiques de dimension inférieure
Introduction
Si la fonction de projection A est linéaire, nous cherchons alors un extracteur de caractéristiques où A est une matrice D X d, permettant la projec-tion d’un vecteur y (dimension D) sur un vecteur x (dimension d) et dont la forme est:
yAx T
Extraction des caractéristiques
Analyse en composante principale– Ce type de méthode est aussi appelée
• Transformée discrète de Karhunen-Loève
• Transformée de Hotelling
• Transformée en vecteurs propres
– Cette méthode permet de déduire une transforma-tion linéaire permettant d’éliminer la corrélation entre les composantes d’un vecteur de variables aléatoires
Extraction des caractéristiques
Analyse en composante principale– Si nous avons une population (n observations) de
vecteurs aléatoires (D dimensions) de la forme:
Dy
y
y
y2
1
• Avec comme vecteur moyenne
n
iiy y
nyEm
1
1
• Avec une matrice de covariance
Tyy
n
i
Tii
Tyxy mmyy
nmymyEC
1
1
Extraction des caractéristiques
Analyse en composante principale– Si nous avons une matrice A définissant une trans-
formation linéaire pouvant générer un nouveau vecteur x à partir d’un vecteur y par:
)( ymyAx
– A est construite de telle façon que ses rangées sont les vecteurs propres de Cy
Extraction des caractéristiques
Analyse en composante principale
– Le vecteur x est aléatoire de moyenne 0 (mx = 0)
– La matrice de covariance de x découle de:
D
Tyx AACC
0
01
• Le vecteur x est donc composé de variables aléatoires non corrélées
– La transformation A élimine donc la corrélation entre les composantes du vecteur y
• k est la variance de xk
Extraction des caractéristiques
Analyse en composante principale– Cette transformation est aussi réversible:
xAxAy T 1 • A est symétrique
Extraction des caractéristiques
Diminution de la dimension du vecteur y– Nous pouvons réduire la dimension du vecteur y de
D-M (nombre de caractéristiques) en ignorant les vecteurs propres correspondant aux D-M plus faibles valeurs propres
– Si nous avons la matrice B de M X D (M < D) découlant de l’élimination des D-M rangées inféri-eures (classée en ordre croissant d’importance) de A
Extraction des caractéristiques
Réduction de la dimension du vecteur y– En guise de simplification nous supposons que m =
0
– Le vecteur x transformé est alors donné par:
Byx ˆ– Le vecteur y est reconstitué approximativement par:
xBy T ˆˆ
Extraction des caractéristiques
Réduction de la dimension du vecteur y– L’erreur quadratique moyenne de l’approximation
est:
D
Mii
MD
ii
D
iiMSE
111
Extraction des caractéristiques
Recherche des valeurs et vecteurs propres– Cherchons les valeurs et les vecteurs propres associés
à une matrice Cy (matrice variance-covariance)
– Si nous avons une matrice Cy de D x D nous pouvons écrire
vvCy – Où v est un vecteur propre de Cy et une valeur propre de Cy
Extraction des caractéristiques
Recherche des valeurs et vecteurs propres
– Si nous avons une matrice Cy de D x D nous pouvons écrire
0)(
vIC
IvvC
vvC
y
y
y
– Par définition, pour que soit une valeur propre il faut que la solution v de la dernière équation soit non nulle. Pour que v soit non nulle il faut que
0 ICy
Extraction des caractéristiques
Recherche des valeurs et vecteurs propres– Si nous considérons un cas d’ordre 3, nous obtenons
0
333231
232221
131211
ccc
ccc
ccc
ICy
– Le déterminant donne
0
0)(
)(
))((
012
23
3122322113
3123332112
3223332211
bbb
ccccc
ccccc
ccccc
Extraction des caractéristiques
Recherche des valeurs et vecteurs propres– Lorsque nous avons les valeurs propres, nous les
substituons une à une dans
(Cy-I) v = 0
pour trouver les vecteurs propres v
Extraction des caractéristiques
Recherche des valeurs et vecteurs propres– Exemple
146.000
020
00854.6
00
00
00
742.0634.0217.0
667.0667.0333.0
067.0392.0918.0
742.0
634.0
217.0
667.0
667.0
333.0
067.0
392.0
918.0
146.0
2
854.6
110
122
026
3
2
1
321
Tyx
y
AACC
A
vvv
C
Extraction des caractéristiques (principes)
Extraction des caractéristiques (exemple en télédétection)
Extraction des caractéristiques (exemple en télédétection)
Extraction des caractéristiques (exemple en télédétection)
40.13
00.64
88.83
5.118
4.931
3210
2
1
D
• Les 2 premières composan- tes contribuent pour 94 % de la variance totale
