Sélection du multi-ensemble à découper

La stratégie la plus simple pour sélectionner le multi-ensemble à découper a été énoncée par Heckbert [Hec82]. Elle consiste à découper le multi-ensemble de plus grand cardinal. Cette stratégie peut être grandement améliorée en utilisant l'erreur de la partition (voir définition 6). Wan et al. [WWP88] ont proposé de sélectionner le multi-ensemble d'erreur quadratique maximale. Cette stratégie repose sur le fait que l'erreur quadratique de la partition est définie comme la somme des erreurs quadratiques des multi-ensembles formant cette partition. Donc en découpant le multi-ensemble dont la contribution à la somme est la plus importante, on espère faire diminuer celle-ci. Une stratégie légèrement différente a été proposée par Wu [WZ91]. Celui-ci découpe le multi-ensemble dont la partition va entraîner la plus grande diminution de l'erreur quadratique. Cette stratégie repose sur le raisonnement suivant :

Supposons que le multi-ensemble contenant l'ensemble des couleurs de l'image ait été découpé $k$ fois en $k+1$ multi-ensembles  $\{\multip{0},\dots,\multip{k}\}$. L'erreur $\E(C)$ associée à la partition est alors égale à $\sum_{i=0}^{k}\ERROR(C_i)$. Supposons à présent que le prochain multi-ensemble à découper soit $C_i$ et considérons $C_i^1$ et $C_i^2$ les deux multi-ensembles issus du découpage de $C_i$. L'erreur associée à la partition après le découpage est alors égale à :

$$E(C) = \ERROR(C^1_i)+\ERROR(C^2_i) + \sum_{j=0,j\neq i} ^{k} \ERROR(C_j).$$

Le découpage du multi-ensemble i a donc modifié $\E(C)$ de $\ERROR(C^1_i)+\ERROR(C^2_i)-\ERROR(C_i)$. On peut remarquer que le théorème 2 assure que $\ERROR(C^1_i)+\ERROR(C^2_i)-\ERROR(C_i)$ est négatif et donc que l'erreur de la partition est effectivement décroissante. L'heuristique consistant à couper le multi-ensemble dont le découpage entraînera une décroissance maximum de l'erreur de la partition est donc a priori meilleure que celle consistant à couper le multi-ensemble d'erreur quadratique maximale. Toutefois cette heuristique impose de couper à chaque itération chaque multi-ensemble afin de détecter celui qui réduira l'erreur au maximum. Cela implique que l'on va générer plus de multi-ensembles que nécessaire. De plus, selon Wu, cette heuristique ne fait diminuer l'erreur quadratique globale que de façon marginale.

Il apparaît ainsi que découper le multi-ensemble d'erreur quadratique maximum à chaque étape soit une bonne heuristique permettant de réaliser un bon compromis entre le temps de calcul et la diminution de l'erreur de la partition.

De plus, cette stratégie peut s'implémenter de manière très efficace en utilisant l'arbre de découpe. Il suffit d'associer à chaque noeud de l'arbre un pointeur sur la branche comportant la feuille d'erreur quadratique maximale. A chaque découpe de multi-ensemble, deux fils sont rajoutés au noeud correspondant et le pointeur est mis à jour le long du chemin menant de ce noeud à la racine de l'arbre. Cette méthode permet donc de retrouver rapidement, à chaque étape de l'algorithme, le multi-ensemble d'erreur maximum. Des études expérimentales nous ont montré que bien que l'arbre produit par les stratégies de Wan [WWP88] et Wu [WZ91] ne soit pas parfaitement équilibré, le temps de recherche du multi-ensemble à découper est quasiment logarithmique.