Présentation des Algorithmesde compression

encadré par Alexandrina Rogozan

Soizic Geslin

Samy Fouilleux

Minh Le Hoai

Maxime Chambreuil

UV de Statistiques – ASI 3 – Année 2002

Isabelle Bondoux

Céline Capron

Ugo Campiglio

Florian Boitrel

Déroulement

• Objectifs du projet

• Algorithme ACP

• Algorithme LDA

• Spécifications

• Conclusion

UV de Statistiques – ASI 3 – Année 2002

Objectifs

• Prendre une image en entrée

• Extraire des coefficients qui la décrivent

• Appliquer l’algorithme

• Récupérer les coefficients en sortie de l’algorithme ( 9 par défaut )

• Recomposer l’image avec ces coefficients

UV de Statistiques – ASI 3 – Année 2002

UV de Statistiques – ASI 3 – Année 2002

Algorithmed’Analyse en Composantes

Principales

Exemple d’une image satellite

Principe

Algorithme ACP 1 / 6

UV de Statistiques – ASI 3 – Année 2002

Dans l'exemple suivant, l’ACP a porté sur les canaux vert, rouge et proche-infrarouge d'une image SPOT, afin de générer les trois canaux ACP1, ACP2 et ACP3. Canal vert Canal rouge Canal infrarouge

Algorithme ACP 2 / 6

UV de Statistiques – ASI 3 – Année 2002

Le premier canal (ACP1), le plus intéressant, présente la brillance globale de l’image, améliorant considérablement les contrastes. Ce canal d’une grande richesse thématique est une bonne représentation synthétique de l’image.

Algorithme ACP 3 / 6

UV de Statistiques – ASI 3 – Année 2002

Le deuxième (ACP2), rend compte des principales différences spectrales entre les canaux sources. Il est en général très bien adapté à l’étude de la végétation et est assez fortement corrélé avec le canal proche infrarouge et dans une moindre mesure avec l’indice de végétation normalisé.

Algorithme ACP 4 / 6

UV de Statistiques – ASI 3 – Année 2002

Le troisième (ACP3) est généralement constitué du bruit résiduel, et ne présente que rarement de l’intérêt. Les pixels aberrants ou les défauts des capteurs, qui apparaissent sur ce canal, sont ainsi absents des deux autres.

Algorithme ACP 5 / 6

UV de Statistiques – ASI 3 – Année 2002

La composition colorée de plusieurs canaux ACP est toujours très intéressante et fortement contrastée. Dans l'exemple ci-dessous, le codage est le suivant :

RVB = ACP1 / ACP2 / ACP3

Algorithme ACP 6 / 6

UV de Statistiques – ASI 3 – Année 2002

La mise en oeuvre mathématique de l'ACP peut être divisée en 6 étapes principales :

1. Préparer les données pour le traitement2. Calculer la matrice des coefficients de corrélations des variables3. Extraire les valeurs et vecteurs propres de cette matrice4. Classer les vecteurs propres dans l'ordre décroissant des valeurs

propres associées5. Calculer la matrice des composantes principales6. Fournir une ou plusieurs représentations graphiques 

UV de Statistiques – ASI 3 – Année 2002

Algorithmed’Analyse Discriminante

Linéaire

Algorithme LDA (1/4)

•On cherche à réduire le nombre de coefficient de l’image

•On cherche ΘTp tel que:

yp =ΘTp.x

Ou yp est le vecteur de dimension p que l’on cherche, ΘT

p une matrice n*p, et x le vecteur des données.

UV de Statistiques – ASI 3 – Année 2002

Algorithme LDA(2/4)

Première étape:

On calcule:

X= (1/N) Σ1..Nxi (Moyenne sur l’ensemble des données)

T=(1/N) Σ1..N(xi-X)(xi-X)T (variance sur l’ensemble des

données)

Puis on calcule ces mêmes vecteurs mais sur les j premières valeurs du vecteur de données.( respectivement Xj et W)

UV de Statistiques – ASI 3 – Année 2002

Algorithme LDA(3/4)•Enfin on calcule

W= (1/N) Σ1..NWi

La méthode de l’analyse Discriminante linéaire utilise une projection simple qui maximise le rapport T/W

Θp=argmax Θp(| ΘpT.T. Θp|/| Θp

T.W. Θp|)On peut montrer que les p solutions de cette équations sont les vecteurs propres de W-1.T qui ont les valeurs propres les plus grandes.

UV de Statistiques – ASI 3 – Année 2002

Algorithme LDA(4/4)

•On obtient ainsi la matrice Θp qui nous permet de calculer le vecteur solution:

yp= Θp.x

UV de Statistiques – ASI 3 – Année 2002

Spécifications

• Format de l’image en entrée

• Nombre de coefficients en entrée et en sortie des algorithmes

UV de Statistiques – ASI 3 – Année 2002

Conclusion

• Les algorithmes seront appliqués à la lecture sur les lèvres

• Ils doivent donc être rapides

• Ils seront développés en C

UV de Statistiques – ASI 3 – Année 2002