of 17 /17
Formation et Analyse d'Images James L. Crowley ENSIMAG 3 2009/2010 Séance 12 18 janvier 2010 PCA, Mélange de Gaussiennes et L'Algorithme EM (Expectation-Maximization) La Reconnaissance de Visage ........................................... 2 L'Analyse en Composantes Principales ............................. 4 Exemple : ....................................................................................... 8 Reconstruction ................................................................................ 11 Mélange de Gaussiens. .................................................... 12 Ebauche de l'Algorithme EM .......................................................... 12 L'Algorithme EM (Expectation-Maximization)............... 14 L'etape E ......................................................................................... 15 L'etape M........................................................................................ 16 Sources Bibliographiques : "Neural Networks for Pattern Recognition", C. M. Bishop, Oxford Univ. Press, 1995. "Pattern Recognition and Scene Analysis", R. E. Duda and P. E. Hart, Wiley, 1973.

Formation et Analyse d'Images - Pervasive Interaction · Les probabilités, h(m, n) donne des facteurs de Mélange, αn, ainsi que les µn,Cn. Soit une ensemble ("training set") de

Embed Size (px)

Text of Formation et Analyse d'Images - Pervasive Interaction · Les probabilités, h(m, n) donne des...

  • Formation et Analyse d'Images

    James L. Crowley ENSIMAG 3 2009/2010 Sance 12 18 janvier 2010

    PCA, Mlange de Gaussiennes et L'Algorithme EM (Expectation-Maximization)

    La Reconnaissance de Visage ...........................................2

    L'Analyse en Composantes Principales .............................4 Exemple : ....................................................................................... 8 Reconstruction................................................................................ 11

    Mlange de Gaussiens. ....................................................12 Ebauche de l'Algorithme EM.......................................................... 12

    L'Algorithme EM (Expectation-Maximization)...............14 L'etape E......................................................................................... 15 L'etape M........................................................................................ 16

    Sources Bibliographiques : "Neural Networks for Pattern Recognition", C. M. Bishop, Oxford Univ. Press, 1995. "Pattern Recognition and Scene Analysis", R. E. Duda and P. E. Hart, Wiley, 1973.

  • PCA et le Mlange de Gaussiennes Sance 12

    12-2

    La Reconnaissance de Visage Ayant dtect et normalis les imagettes de visages en position et taille (sance 11), il est possible de construire un systme de reconnaissance Baysienne. Pour cela nous allons utiliser l'Analyse en Composants Principales (ACP ou PCA en Anglais) et une Mlange de Gaussiennes. (GMM pour Gaussian Mixture Model en Anglais) Il nous faut une ensemble d'apprentissage. Soit M imagettes normaliss, {Wm} composes de K ensembles

    !

    Wmk{ } de Mk imagettes pour K personnes.

    !

    Wm{ } = Wmk{ }k! ,

    !

    M = Mkk"

    Notre problme : Ayant un nouveaux imagette (normalis) W, dterminer son identit, k. k W est une imagette du face de la personne k. k = arg-max

    k {p(k |W) }

    Pour faire cette estimation, nous allons utiliser la rgle de Bayes :

    !

    p(" k |W ) =p(W |" k )p(" k )

    p(W )

    Mais nous avons deux problmes : 1) Quel vecteur de caractristique, X

    , doit en utiliser pour reprsenter W

    2) Comment dterminer (estimer) p(k | X

    ) et P(X

    ). Solutions propose 1) Quel vecteur de caracteristiques X

    d'utiliser ?

    Pour le premier problme, nous allons utiliser une analyse en composants principales pour construire un "sous-espace" de l'espace de W. Avec une espace de composant principales

  • PCA et le Mlange de Gaussiennes Sance 12

    12-3

    !

    ! X = W ,

    " "

    2) Comment representer p(k | X

    ) et P(X

    ) ?

    Pour le 2ieme problme nous allons construire un mlange de Gaussiennes avec l'algorithme EM. Mlange de Gaussians. (GMM) Nous allons representer P(X

    ) par :

    P(X

    ) = n=1

    N nN(X ; n ,Cn )

    et

    P(X

    |k) = n=1

    N nN(X ; kn ,Ckn )

  • PCA et le Mlange de Gaussiennes Sance 12

    12-4

    L'Analyse en Composantes Principales

    L'analyse en composant principales d'un signal est une mthode de dterminer un sous-espace "optimale" pour la reconstruction. Elle est parfois utilise pour dfinir un espace de caractristiques pour la reconnaissance. Soit une ensemble de M imagettes normaliss en position et taille compos de N pixels : Wm(i, j) Wm(i, j) pour tel que i [1, I], j [1, J], Nous allons les exprimer en vecteur de N = I x J : Wm(n) ou n = j*I + i : Wm(n) = Wm(i, j) Il serait possible d'utiliser le les pixels directement comme caractristiques. Par exemple, pour des imagettes de taille 32 x 32, Wm(n) est une vecteur de de 1K caractrisitique. Mais il est prferable d'avoir un espace de dimension D < K < M (K est le nombre de classes, M est le nombre d'exemplaires). Dans ce cas, nous pouvons dterminer une sous-espace de dimension rduite par l'ACP. On cherche une base orthogonale (n)= {d(n)} d = 1, 2, ... D pour reprsenter les X(n). telles que D

  • PCA et le Mlange de Gaussiennes Sance 12

    12-5

    Les bases {d(n)} sont les vecteur propres du {Vm(n)} : Sa covariance, C, est compose de N x N = N2 termes Soit le matrice V :

    !

    V = V1(n)V1(n)...Vm (N)[ ] =

    V1(1) V2(1) ... VM (1)V1(2) V2(2) ... VM (2).... ... ... ...

    V1(n) V2(n) ... VM (n)

    "

    #

    $ $ $ $

    %

    &

    ' ' ' '

    V est N par M. Chaque colonne de V est une image.

    C V VT =

    !

    C = E{Vm (n)Vm (n)T}

    Les termes de C sont les covariances pour des pairs de pixels i et j.

    ij2 = 1M

    m=1

    M (Vm(i) Vm(j))

    Pour une imagette de taille N pixels, il y a N2 termes dans la covariance. Chaque coefficient, ij2, est une covariance de la pixel i et j pour l'ensemble de M images. Par exemple, pour une imagette de 32 x 32, le matrice C= VVT est de taille 1024 x 1024. Les vecteurs propres de C sont des vecteurs orthogonales (n) = {m(n)} tels que :

    !

    "TC" ="TVVT" = # o n est un matrice diagonal de N termes n des valeurs principales de C. Chaque m(n) est un vecteur de direction. L'ensemble {m(n)} est orthogonal.

  • PCA et le Mlange de Gaussiennes Sance 12

    12-6

    Une telle matrice de rotation est fournie par une d'analyse en composants principales. (Voir Recettes Numrique en C pour les procdures programmes). ( m(n), n) PCA(C).

    Pour une imagette de 32 x 32, le matrice C= V VT est de taille 210 x 210 = 220. Pour une image de 512 x 512, le matrice C= V VT est de taille 218 x 218 = 236. Les plupart des procdures PCA exige que N < 1024. Mais, il y a une astuce pour viter le calcule d'une matrice de covariance de N x N coefficients. Les algorithmes PCA fournissent les vecteurs propres {m(n)} dans l'ordre dcroissante de n . Ors, pour une ensemble de M image M

  • PCA et le Mlange de Gaussiennes Sance 12

    12-7

    Pour M < 1024 on peut facilement calculer une matrice R de rotation tels que chaque colonne est un vecteur directeur orthogonal. RT V

    TV R = m

    On multiplie les deux cots par R : R RT V

    TV R = R m On note que RTR = I. donc : V

    TV R = R m

    Maintenant on multiplie par V

    V VTV R = V R m

    = (VVT )(V R) = (V R) m

    Mais T (VVT) = N donc (VV

    T) = N

    est le m est un MxM sous matrice de N m= N pour les premier m terms. Donc (VV

    T) = n =(V R)

    m pour les premier m terms

    !

    "m (n) = Vl (n)R(l,m)l=1

    M

    #

  • PCA et le Mlange de Gaussiennes Sance 12

    12-8

    =

    Raison : Les mmes images ont t utilis pour et pour R. Les premiers M vecteurs propres de VTV sont aussi les premiers M vecteurs propres de VVT, le Rank de est le mme que R, et b sont les premiers M valeurs propre de c et Donc, les vecteurs propres : d(n) = V R tris par b = VR Chaque colonne est un vecteur dans une base orthogonale.

    (n) = m-1

    M Vm(n) R(m,n)

    (n) fournit une base orthogonal pour Wm(n) . Une imagette (normalise) peut tre projett sur (n) Nous pouvons mme utiliser une sous ensemble de D composants.

    !

    xd = V ,"d = V (n)n=1

    N

    # "d (n)

    Les valeurs xd sont un "code" qui reprsente V(n) pour la reconnaissance ou la reconstruction.

    Exemple : 16 images prise au hasard dans une squence de 2 minutes. (F. Brard, 1995).

  • PCA et le Mlange de Gaussiennes Sance 12

    12-9

    Average Image

  • PCA et le Mlange de Gaussiennes Sance 12

    12-10

    Components Principales :

    Eigen Values.

    -5.0000E+060.0000E+005.0000E+061.0000E+071.5000E+072.0000E+072.5000E+073.0000E+073.5000E+07

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  • PCA et le Mlange de Gaussiennes Sance 12

    12-11

    Reconstruction Image Reconstructed image (120 bytes) Error Image.

    Reconstruction (120 bytes)

    Image Error

  • PCA et le Mlange de Gaussiennes Sance 12

    12-12

    Mlange de Gaussiens.

    Pour la reconnaissance, nous avons besoin :

    !

    p(" k |! X ) = p(

    ! X |" k )p(" k )

    p(! X )

    Si les imagettes de personne k sont issus d'une composition de "N" phnomnes, la densit

    !

    p(! X |" k ) prendra la forme d'une composition de N lois Normales. Pour les

    visages, il peut s'agit des variations dans l'angle de l'clairage, l'angle de vue, ou les expressions. Dans un tel cas, on peut approximer par une somme pondre de densits Normales.

    !

    P(! X ) = "n

    n =1

    N

    # N(! X ;! n,Cn ) et

    !

    P(! X |" k ) = #n

    n

    N

    $ N(! X ;! nk,Cnk )

    De telle somme est connue par le terme "mlange de Gaussiens" Pour chaque Gaussien il faut estimer trois paramtres :

    !

    ! " = (#n ,

    ! n,Cn )

    Pour une vecteur X de D dimensions En total il y a N(1+D+D2) coefficient estimer. Pour simplifier, nous pouvons remplacer Cn par une matrice diagonal de variances : dn

    2

    Ca donnerait : N(1+2D) parametres. En tout cas, les parametres

    !

    ! " = (#n ,

    ! n,Cn ) sont les paramtres cachs des sources

    cachs des donnes. L'algorithme d'Expectation Maximasation permettre d'estimer les parametres caches.

    Ebauche de l'Algorithme EM On suppose chaque evennement Em est issu d'un des N sources. Nous allons construire une table de probabilits. h(m, n)

  • PCA et le Mlange de Gaussiennes Sance 12

    12-13

    h(m, n) = Pr{l'vnement Em est issu de la source N} Les probabilits, h(m, n) donne des facteurs de Mlange, n, ainsi que les n,Cn. Soit une ensemble ("training set") de M observations T = {Xm}. Fait une premiere estimation des paramtres, (0). Ensuite l'algorithme vas les rafinner par altenance des tapes "E" et "M". E: Faire une estimation des valeurs manquantes, h(m, n), pour les vnements. h(m, n)(i)= p(hm |X1, X2, ..., XM,

    (i)) pour chaque terme "n".

    h(m, n)(i) = n(i)N(Xm; n(i),n(i))

    j=1

    N j(i)N(Xm; j(i),j(i))

    M: Recalculer (i+1) avec p(hm | X1, X2, ..., XM,

    (i))

    Sn(i+1)= m=1

    M h(m,n)(i)

    n(i+1) = 1M Sn(i+1) =

    1M

    m=1

    M h(m,n)(i)

    n(i+1)= 1

    Sn(i+1) m=1

    M h(m,n)(i) Xm

    2n(i+1) = 1

    Sn(i+1) m=1

    M h(m,n)(i) (Xm n(i+1))2

    Pour la drivation l'algorithme EM, il faut introduire le concept de "likelihood" (vraisemblance) .

  • PCA et le Mlange de Gaussiennes Sance 12

    12-14

    L'Algorithme EM (Expectation-Maximization)

    L'algorithme EM s'applique lestimation de donnes cachs. Il est utilis notamment pour l'estimation des Modles de Markov Caches (HMM's) et pour l'estimation des Mlanges de Gaussiens. Pour un mlange de Gaussiens, les variables caches sont les sources des vnements. On suppose que chaque vnement est produit par un des N sources. Pour chaque vnement Em On dfinit la variable "cache" hm hm = N si l'vnement Em (avec caractristique Xm) est issu de la source N. Nous cherchons estimer

    !

    P(! X ) = "n

    n

    N

    # N(! X ;! n,Cn ) tels que

    n=1

    N n = 1.

    ou

    !

    ! " = (#n ,

    ! n,Cn )

    Il faut estimer

    !

    ! " = (#n ,

    ! n,Cn )

    Le likelihood de {Xm} est

    !

    L(! " |{Xm}) = P(Xmm=1

    M

    # | ! " )

    Le Log-likelihood est

    = Log (L(

    | X1, X2, ..., XM)) =

    !

    Log P(Xmm=1

    M

    " | ! # )$

    % &

    '

    ( )

    = m=1

    M Log {p(Xm|

    ) )}

    = m=1

    M Log (

    !

    "nn =1

    N

    # N(! X ;! n ,Cn ))

    Il faut

    !

    " = arg#max"

    L(! " |{Xm}){ }

  • PCA et le Mlange de Gaussiennes Sance 12

    12-15

    Il n'y pas de solution analytique, parce qu'il n'y est pas une driv pour la logarithme de la somme. Soit T = {Xm} h(m,n) le donne Complt. On vas maximiser une mesure de qualit Q( (i)) dfinit par une esperence conditionnel

    Q( (i)) = E{ l( (i) ) | T)} = Log { m=1

    M p(Xm|

    ) }

    L'etape E Pour chaque vnement Em avec caractristique Xm, On suppose qu'il manque l'information: hm hm = n, la source de l'vnement Em. On ne connat pas hm, mais on peut estimer les probabilits P(hm= n). par une table h(m,n). Pour chaque Xm, et son source cach hm

    !

    p(hm ,Xm |! " ) = p(hm | Xm ,

    ! " )p(Xm |

    ! " )

    donc

    !

    p(hm | Xm ,! " ) = p(hm ,Xm |

    ! " )

    p(Xm |! " )

    d'o p(hm=n, Xm |

    ) = nN(Xm; n,n)

    p(Xm |

    ) = n=1

    N nN(xm; n,n)

    Donc

  • PCA et le Mlange de Gaussiennes Sance 12

    12-16

    p(hm=n | X1, X2, ..., XM, ) =

    nN(Xm; n,n)

    j=1

    N jN(Xm; j,j)

    Donc pour chaque itration (i) le premier tape E est :

    h(m, n)(i) = n(i)N(Xm; n(i),n(i))

    j=1

    N j(i)N(Xm; j(i),j(i))

    L'etape M Pour le deuxime tape, M, nous allons maximiser le "likelihood" Log{p( Xm |

    )} On dfini la "Expected Complete Data Log Likelihood" pour T. = {Xm} U h(m,n) Q = Q(

    (i)) Q( (i1))

    Pour chaque cycle dans l'itration nous allons chercher :

    (i+1) = argmax

    {Q(

    | (i)))

    Ce maximum est donn par :

    Sn(i+1) = m=1

    M p(hm=n | Xm,

    (i))) = m=1

    M h(m, n)

    n(i+1) =

    !

    1M

    P(hm = n | Xm ,! " (i)

    m=1

    M

    # )= 1M Sn(i+1)

    n(i+1) = 1

    Sn(i) m=1

    M p(hm=n | Xm,

    (i)) Xm = 1

    Sn(i+1) m=1

    M h(m,.n) Xm

    2n(i+1) = 1

    Sn(i) m=1

    M p(hm=n | Xm,

    (i)) (Xm n(i+1))2.

    = 1Sn(i+1) m=1

    M h(m,n) (Xm n(i+1))2

  • PCA et le Mlange de Gaussiennes Sance 12

    12-17

    Avec notre table de probabilits h(m, n) h(m, n) = P(hm=n | Xm,

    (i)) E (Expectation) :

    h(m, n)(i) : = n(i)N(Xm; n(i),n(i))

    j=1

    N j(i)N(Xm; j(i),j(i))

    M: (Maximisation)

    Sn(i+1) := m=1

    M h(m, n)(i)

    n(i+1) := 1M Sn(i+1)

    n(i+1) := 1

    Sn(i+1) m=1

    M h(m,.n)(i) Xm

    2n(i+1) : = 1

    Sn(i+1) m=1

    M h(m,n)(i) (Xm n(i+1))2

    Dans le cas Multivariate (D> 1) la covariance C est compose de jk2:

    2jkn(i+1) : = 1

    Sn(i+1) m=1

    M h(m,n)(i) (Xjm jn(i+1))(Xkm kn(i+1))