Quantification par fusion

Si $N=2^{3p}$, il faudra partitionner chaque axe en $2^p$ intervalles. La longueur de chaque intervalle est alors égale au côté d'un sous cube et est égale à: $\alpha=2^{8-p}$.

La quantité $\frac{R}{\alpha}$ nous donne le numéro de l'intervalle sur l'axe $R$. De même, les quantités $\frac{G}{\alpha}$ et $\frac{B}{\alpha}$ nous donnent respectivement les numéros d'intervalles sur les axes $G$ et $B$. Compte tenu de notre numérotation et sachant que le plan $R-G$ comporte $2^{2p}$ carrés, le numéro d'un sous cube est:

$$\begin{array}{lll} ind &=& B.2^{p-8}.2^{2p}+G.2^{p-8}.2^{p}+R.2^{p-8}\\ &=& B.2^{3p-8}+G.2^{2p-8}+R.2^{p-8}\\ \end{array}$$

Notez que ce calcul peut s'effectuer efficacement avec des décalages.

init_partition(const image &I, int p)
{
        unsigned char couleur[3];
        int N=(1<<3*p);
        sous_cube * tab_cube = new sous_cube[N];

        I.debut();
        do
        {
                I.lire_pixel(couleur);
                int ind =couleur[2]*2^(3*p-8)+couleur[1]*2^(2*p-8)+couleur[0]*2^(p-8)
                tab_cube[ind].M0++;
                for(int i =0;i<3;i++)
                {
                        tab_cube[ind].M1[i] += couleur[i];
                        tab_cube[ind].M2[i] += couleur[i]*couleur[i];
                }
        }
        while(I.suivant());
}

Le nombre de couleurs de l'image résultat sera égal à $N$ si tous les sous cubes contiennent au moins une couleur. En pratique, on trouve généralement des valeurs bien inférieures à $N$.

L'expression de l'erreur quadratique du cluster $k$ se trouve dans le cours et est égale à:

$$\sum_{i=0}^2 tab\_cube[k].M_2[i]^2-\frac{tab\_cube[k].M_1[i]^2}{tab\_cube[k].M_0}$$

L'erreur quadratique de partition avant la fusion est donnée par:

$$E = \sum_{i=1}^N SE_i$$

où $N$ représente le nombre de sous cubes et $SE_i$ l'erreur quadratique du sous cube $i$. La fusion de deux sous cubes $m$ et $n$ crée un multi-ensemble d'erreur quadratique:

$$SE = SE_m +SE_n+\frac{M_{0m}M_{0n}}{M_{0m}+M_{0n}}\Vert \mu_m-\mu_n\Vert^2$$

où $M_{0m}$, $M_{0n}$, $\mu_m$ et $\mu_n$ représentent respectivement les moments d'ordres 0 et les moyennes des sous-cubes $m$ et $n$.

L'erreur quadratique de partition après la fusion est donc égale à:

$$\begin{array}{lll} E' &=& \sum_{i=1,i\not\in\{m,n\}}^N SE_i ... ...m}M_{0n}}{M_{0m}+M_{0n}}\Vert \mu_m-\mu_n\Vert^2\\ \end{array}$$

L'augmentation de l'erreur quadratique de partition est donc de : $\frac{M_{0m}M_{0n}}{M_{0m}+M_{0n}}\Vert \mu_m-\mu_n\Vert^2$. Il convient donc de fusionner à chaque étape les deux sous-cubes qui induisent une augmentation minimum de l'erreur quadratique de partition. L'augmentation induite par la fusion étant décrite plus haut.

void merge_sous_cubes(sous_cube * tab_cube, int i,int j)
{
        int max = MAX(i,j);
        int min = MIN(i,j);

        tab_cube[min].pere = max;

        tab_cube[max].MO+=tab_cube[min].MO;
        for(int i=0;i<3;i++)
        {
                tab_cube[max].M1[i] += tab_cube[min].M1[i];
                tab_cube[max].M2[i] += tab_cube[min].M2[i];
        }
}

void give_mean(sous_cube * tab_cube, unsigned int* color,unsigned int* moyenne,int p)
{
        int ind =couleur[2]<<(3*p-8)+couleur[1]<<(2*p-8)+couleur[0]<<(p-8);
        
        while (ind != tab_cube[ind].pere)
                ind = tab_cube[ind].pere;
        for(int i=0;i<3;i++)
                moyenne[i] = tab_cube[ind].M1[i]/tab_cube.M0;
}

La suppression des indirections peut s'effectuer grâce à une simple boucle descendante du type suivant:

        for(int i=N-1;i>0;i--)
        {
                int ind =tab_cube[i].pere;
                tab_cube[i].pere= tab_cube[ind].pere;
        }

qui positionne le père de chaque sous cube au père de son père. Etant donné que les relations père-fils vont toujours de l'indice le plus petit vers l'indice le plus grand, la boucle descendante supprime toutes les indirections en une passe.