Quantification par fusion

On suppose que l'espace $RGB$ est contenu dans un cube de taille $256\times 256\times 256$. On désire partionner ce cube en $N=2^{3p}$ (avec $p<8$) sous-cube de tailles égales.

1. En combien d'intervalles faut il partionner chaque axe ? Quelle est la taille de chaque sous-cube ?

   Les cubes sont numérotés dans le sens des $R$, puis des $G$, puis des $B$. Ainsi, si $\alpha$ représente le coté de chaque sous-cube, le cube $[0,\alpha]\times [0,\alpha]\times [0,\alpha]$ aura le numéro 0, puis le cube, $[\alpha,2\alpha]\times [0,\alpha]\times [0,\alpha]$ aura le numéro 1 et ainsi de suite (faire un dessin dans le plan $R-G$).

2. Donnez la formule donnant le numéro du cube contenant un triplet $(R,G,B)$ donné.

3. Étant donnée une image couleur codée en $RGB$, on désire associer à chaque sous-cube les moments d'ordre 0, 1 et 2 des couleurs contenues dans ce sous cube. Ecrire la procédure qui réalise cette opération. On supposera pour cela que l'on possède les classes suivantes:
   • La classe image avec les méthodes:
     • debut(): positionne un pointeur courant en haut, à gauche de l'image.

     • lire_pixel(unsigned char*) : rempli le tableau de taille 3 passé en paramètre avec la valeur du pixel.
     • suivant(), avance le pointeur courant vers la droite, puis vers le bas, renvoie faux lorsqu'il arrive en bas à droite de l'image vrai sinon.

   • Une classe sous_cube contenant les champs publics:
     • $M_0$, $M_1$ et $M_2$ qui correpondent aux moments d'ordre 0, 1 et 2. Le constructeur par défaut initialise ces champs à 0. $M_0$ sera considéré comme un float, alors que $M_1$ et $M_2$ seront considérés comme des tableaux de float de taille 3.

     • Un champ entier père qui sera utilisé plus tard.
   N'oubliez pas d'allouer le tableau de sous-cubes.

4. Si l'on associe à chaque couleur de l'image la moyenne du sous cube qui le contient, combien de couleurs (au maximum) seront présentes dans l'image résultat ?

5. Donnez la formule indiquant l'erreur quadratique d'un sous cube, d'indice $k$. On notera le tableau de sous cubes $tab\_cube$. Indiquez l'augmentation de l'erreur quadratique de partition provoquée par la fusion de deux sous cube.

6. On suppose que l'on a fusionné des sous-cubes de façon à se ramener à un nombre $K<N$ fixé de sous-cubes. Si l'on effectue les fusions deux à deux quels sont selon vous les deux sous-cubes qu'il convient de fusionner à chaque étape ?

7. A chaque étape de fusion entre deux sous-cubes, le sous-cube d'indice minimum est invalidé et on positionne son champ père à l'indice du sous-cube d'indice maximum. Les moments de celui-ci sont mis à jour. Ecrire la fonction $void~merge\_sous\_cubes(sous\_cubes *, int ~i,int ~j)$ qui réalise cette opération. On supposera que le champ père est initialisé à l'indice du sous-cube.

8. Notez qu'apres plusieurs fusions, les sous-cubes deviennent des multi-ensembles quelconques. Ecrivez la procédure
   $give\_mean( sous\_cube*,unsigned int* color,unsigned int* moyenne,int p)$ qui recopie dans le tableau de taille 3 moyenne la moyenne du multi-ensemble contenant $color$.

9. Supposons que l'on fusionne le sous-cube 3 avec le sous-cube 5, puis le sous-cube 5 le sous-cube 10. Combien d'indirections doit effectuer la procédure give_mean ? Proposez une méthode pour supprimer ces multiples indirections.