---
title: I4 Traitement d'images
tags: ESIEE
---

I4 Traitement d'images
===

:::spoiler

function res = appli(im, l)
    res = im;
    for i=1: size(im,1),
        for j=1: size(im, 2),
            res(i,j)=l(im(i,j)+1)*255
        end
    end
end

    T=zeros(256,1);
    for i=0:255
        T=

a=imred('cameraman.gif')
imshow(a)
[b,c] = histeq(a,256)
d=fcumul(a);
e=appli(a,d);

figure; imshow(e);
figure; imshow(b);

function h = hcumul(im)
    v=zeros(256,1)
    for i=1:size(im,1),
        for j=1:size(im,2),
            v(im(i,j)+1) = v(im(i,j)+1)+1;
        end
    end
    h=v;
    for i=2:256,
        h(i)=h(i)+h(i-1)
    end
    for i=1:256,
        h(i)=h(i)/h(256);
    end
end

:::

# Approfondissement

[e-mail]
- Diplomé à Ensimag
- Doctorat à l'UTC
- Enseignant à l'UPJV, IUT Amiens
- Membre du laboratoire LTI
- Equipe Systemes Intelligents
- Analyse de données
- Statistiques avancées

## Méthode d'Otsu
*cf poly Traitement d'images*

Cas particulier de l'analyse de variance (ANOVA)


image en **niveau de gris** chaque pixel $(x,y) \rightarrow G(x,y)$ entre 0 et 255.

Création d'un "histogramme":


But:
Trouver $k$ qui sépare "statistiquement" les "gris foncé" des "gris clairs".

**Critère d'Otsu**
Calculer $$
s^{2}(k) = \frac{[mu_{t}w(k) - mu(k)]^{2}}{w(k)[1-w(k)]}
$$
pour $k$ de 1 à 255 et retenir $k_{opti}$ maximisant $S^{2}(k)$ (critère de séparation)
Il y a une "récurrence" pour $k \rightarrow k+1$

$w(k) = \sum_{i=0}^{k}p_{i}$ où $p_{i}$ est le % de pixel tel que $G(x,y) = i$
$w(k) =$ % de pixel tel que $G(x,y) \leq k$

$mu_{k} = \sum_{i=0}^{k}i.p_{i}$
Multiplie chaque valeur de gris à son pourcentage. Cela ressemble au calcul d'une moyenne pondérée. Facile à mettre à jour.

**Remarque :** $\frac{mu(k)}{w(k)} =$ moyenne des $G(x,y)$ tel que $G(x,y) \leq k$

$mu_{T} = mu(255) \Rightarrow$ Calculé une seule fois

### Définition

C'est une analyse de variance avec 2 classes ( $\leq k$ vs $>k$)et données en 1 dimension (ici l'intervale des niveaux de gris).

ANOVA peut gérer plus de 2 classes. En revanche la gestion de plusieurs dimensions complexifie grandements son exploitation. Pour les couleurs RGB, se sont des données en 3 dimensions on devra utiliser une autre méthode.

:::warning
Les notations suivantes sont différentes. Certaines lettres peuvent être pareilles mais ne représentent plus la même chose
:::

#### Notation

ANOVA : notation classique ($\neq$ Otsu)

**ex-aquo autorisé**

Potentiellement, chaque $x_{i}$ est dans une classe (différente) $C_{j}$. Par exemple en fonction de la source de données.
- $i \in [1,n]$
- $j \in [1,J]$

#### Classe

Chaque classe $C_{j}$ est un sous-ensemble de $x_{i}$. Les $C_{j}$ partionnent les données. Chaque $x_{i}$ est dans une classe $C_{j}$ unique.
Pour chaque classe, on peut calculer 3 choses :
- effectif : $n_{j} =$ nombre de $i$ tq $x_{i} \in C_{j}$
- moyenne : $m_{j} = \frac{1}{n_{j}} \sum_{i \in C_{j}} x_{i}$
- variance : $V_{j} = \frac{1}{n_{j}} \sum_{i \in C_{j}} (x_{i} - m_{j})^{2}$

#### Population

On a aussi les mêmes indicateurs sur la population entière :
- effectif : $n$
- moyenne : $m = \frac{1}{n} \sum_{i = 0}^{n} x_{i}$
- variance : $V = \frac{1}{n} \sum_{i=0}^{n} (x_{i} - m)^{2}$

#### Relation entre classes et population

Relation entre ces indicateurs

- effectif : $n = \sum_{j=1}^{J} n_{j}$
- moyenne : $m = \frac{1}{n} \sum_{j=1}^{J}n_{j}.m_{j}$

**Formule de décomposition de la variance**
variance : $V = \frac{1}{n}(SSW + SSB)$
- **SSW** : *Sum of Square Within* (classes) ~= "intra classes"
$SSW = \sum_{j\in C_{j}}\sum_{x_{i}\in C_{j}}(x_{i} - m_{j})^{2}$ où $\sum_{x_{i}\in C_{j}}(x_{i} - m_{j})^{2} = n_{i}.V_{j}$
On utilise ainsi la moyenne de classe au lieu de la moyenne générale.
- **SSB** : *Sum of Square Between* (classes) ~= "inter classes"
$SSB = \sum_{j\in C_{j}}n_{j}(m_{j} - m)^{2}$

**Exemple visuel où $SSW >> SSB$**


**Exemple visuel où $SSW << SSB$**


Si SSB est "grand", les classes sont bien "séparées".

**Otsu**


Cette valeur de $k$ sépare *mal* esl classes. SSB est "petit".

alors que:

Cette valeur de $k$ sépare *mieux* les classes.

Le $S^{2}(k)$ de Otsu est en fait $\frac{SSB}{n}$. $k$ change les classes SSB et SSW mais **pas V** (ni $n$ ni $m$).

Dernier avantage : Pas besoin de calculer les $v_{j}$ ni $V \rightarrow$ seulement les moyennes SSB sont calculable et "SSW le compense" (SSB + SSW = constante)

**Otsu** : On cherche $k$ qui maximise $\frac{SSB}{n}$.

#### Démonstration de la formule de décomposition de la variance (générale)

$$
V = \frac{1}{N} \sum_{i=1}{n}\Big((x_{i}-m_{classe})(m_{classe}-m)\Big)^{2}
$$

Vérification de $S^{2}(k) = \frac{SSB}{n}$

avec $p_{i} =$ % de pixel $= i$

- classe 1 :
- effectif $n_{1} = w(k) * n$
- moyenne $m_{1} = \frac{mu(k)}{w(k)}
- classe 2 :
- effectif $n_{2} = n - n_{1}$
- moyenne $m_{2} = \frac{n.m - n_{1}.m_{1}}{n_{2}}$
Car $m = \frac{1}{n}(n_{1}.m_{1}+n_{2}.m_{2})$

$\frac{SSB}{n} = \frac{n_{1}}{n}(m_{1}-m)^{2}+\frac{n_{2}}{n}(m_{2}-m)^{2}$
où $\frac{n_{1}}{n} = w(k)$ et $\frac{n_{2}}{n} = 1 - w(k)$
On montre que :
- $m_{1}-m = \frac{mu(k)-mu_{T}.w(k)}{w(k)}$
- $m_{2}-m = \frac{mu_{T}.w(k) - mu(k)}{1-w(k)}$

Avec $C_{1},C_{2}...C_{J}$ imposées
"**Y a-t-il une différence significative entre au moins certaines classes ?**"
**Otsu :** Reprend ce critère pour comparer des classifications ($C_{1},C_{2}$) nombreuses. Pour les niveaux de gris, il y a environ 254 possibilités pour $k$.

C'est la différence entre:
- la méthode **supervisée**: On connait les classes. Dont fait partie la **classification supervisée**. On connait les classes et on cherche à les reproduire pour les généraliser et pouvoir traiter des nouvelles données non-classifiées.
- la méthode **non-supervisée**: On cherche les classes. Dont fait partie le **clustering**

## Algorithme des $k$ moyens (KMEANS)
*Cas particulier de clustering*

### Définition

**Données :** $n$ points en dimension $d$.
Exemple: $d = 2$. Objectif: Définir les classes.


Les classes doivent regrouper les "points proches" et séparer les "points éloignées".

K-MEANS raisonne avec $K$ (fixé) = nombre de classes représentées par leur centre = moyenne des coordonnées (barycentre = centre de gravité)

*Algorithmique*:
- Initialiser les $K$ centres : $M_{1}, M_{2}...M_{K}$
- Répeter jusqu'à stabilisation

$\Rightarrow$ Classification: Chaque point $X_{i}$ est classé dans $C_{j}$ tel que $M_{j}$ est le centre **le plus proche** de $X_{i}$.
$\Rightarrow$ Mise à jour chaque $M_{j}$ est écrasé par le centre de la classe $C_{j}$.

### Exemple numérique $1~d$


#### Fonctionnement

- $k = 2$
- Initialisation au hasard: $M_{1} = 9$ et $M_{2} = 14$.

$\Rightarrow$ Premier passage dans la boucle : Calcul de distances

| | $x_{1}$ | $x_{2}$ | ... | $x_{16}$ |
| ------- | ---- | -------- | - | - |
| $M_{1}$ | 8 | 7 | | 5 |
| $M_{2}$ | 13 | 12 | | 2 |

$C_{1} = \{1;2;3;4;10;11\}$
$C_{2} = \{15;16\}$

Mise à jour :
- $M_{1}=moy(C_{1}) = \frac{32}{6} = 5$
- $M_{2} = moy(C_{2}) = \frac{31}{2} = 15$

:::info
Les centres $M_{x}$ ne doivent pas être arrondis. Dans l'exemple, c'est pour un soucis de facilité.
:::

$\Rightarrow$ Deuxième passage dans la boucle : Calcul de distances

| | $x_{1}$ | $x_{2}$ | ... | $x_{16}$ |
| ------- | ---- | -------- | - | - |
| $M_{1}$ | 4 | 3 | | 11 |
| $M_{2}$ | 14 | 13 | | 1 |

$C_{1} = \{1;2;3;4\}$
$C_{2} = \{10;11;15;16\}$

Mise à jour :
- $M_{1}=moy(C_{1}) = \frac{10}{4} = 2$
- $M_{2} = moy(C_{2}) = \frac{52}{4} = 13$

Lorsque les centres ne bougent (presque) plus, l'algorithme se termine.

#### Avantages

- Rapide (cas général)
- Fonctionne en dimension $d$ quelconque (contrairement à V, SSW, SSB... deviennent des matrices de dimension $d*d$)

ex: pixels couleurs
$(x,y) \rightarrow \Big(R(x,y),V(x,y),B(x,y)\Big)$ qui est un clusteur 5D de zones dans l'images avec :
$R(x,y),V(x,y),B(x,y)$ un clusteur 3D de couleurs

#### Limitations

1. Le calcul de distance en dim $d$ peut être "perturbé" si les dimensions sont dans des échelles différentes.

ex: $(x,y,R,V,B)$ avec
- $(x,y) \in \mathbb{N}^{2}$
- $(R,V,B) \in \{0,255\}^{3}$

**Solution**: Faire un prétraitement = Changement d'échelle pour "homogénéiser".

ex:
- Centrer et réduire chaque axe ($\mu$ et $\sigma$)
- Ramener à $[0,1]$ avec min et max

2. Dans l'exemple précédent, $x_{10}$ est équidistant de $M_{1}$ et $M_{2}$. Dans quelle classe mettre $x_{10}$ ?

**Solutions:**
- Tirage au sort (peut perturber la convergence)
- Appartenance partielle (ici 50/50) avec une moyenne pondérée

$\Rightarrow x_{10}$ sera dans $M_{1}$ et $M_{2}$ mais avec un coeficient de $\frac{1}{2}$

3. L'initialisation peut avoir une influence importante
**Stratégie classique :**
- Tirer au sort les $M_{j}$ initiaux parmi les $x_{i}$
- Faire plusieurs essais de ce type + un critère de selection

4. Si une classe $C_{j}$ est vide, $mxy$ de $M_{j}$ ?
**Solution :** $M_{j}$ reste identique avec "warning". (peut-être que $K$ est trop grand)

5. **La plus importante:** $K$ est fixé à l'avance, l'algo ne peut pas le modifier.
Il faut donc avoir une idée fiable de la valeur de $K$ "approximative" mais si la dimension est grande, il sera difficile de le visualiser.
**Stratégie classique:** Essayer avec $k=2$, puis $k=3$... (rester "raisonnable" + critère de sélection).
Variante **complexe** qui modifie $K$ "en cours de route". (Xmeans 2000-2005)

### Généralisation

Chaque classe $C_{j}$ représentée par la loi normale multidimensionnelle :
$$
N_{d} = \Big(M_{j}; \sum j)
$$
où $\sum j$ est la matrice de variance et de covariance

Il s'agit du **Modèle de mélange gaussien** (*Gaussian Mixture Model* + algorithme EM)