L'Histogramme de Brun et Braquelaire

Le but de cette structure de données est de permettre un accès rapide au nombre de pixels dans l'image possédant une composant de valeur donnée, i.e. vérifiant l'équation 5.3 :

$$c_i = \alpha \left\{ \begin{array}{l} m_j \leq c_j < M_j\\ m_k \leq c_k < M_k \end{array} \right. ~~ ~ i,j,k \in \{1,2,3\}$$ (5.2)

où :

•   $[m_i,M_i[\times[m_j,M_j[\times[m_k,M_k[$ définit les interalles de variations des couleurs de l'image.
•   $\alpha \in [m_i,M_i[$

Résoudre (5.3) consiste à trouver le nombre de pixels de coordonnée $\alpha$ sur l'axe i dans l'ensemble C des couleurs de l'image.

On sent intuitivement assez bien que des données triées résoudraient le problème. Partant de cette idée, Brun et Braquelaire reprennent la structure de données utilisée par les méthodes de quantification descendantes en y adjoignant des tableaux d'index $tab_{c_1}$, $tab_{c_2}$ et $tab_{c_3}$ triés suivant chacune des composantes. Chacun de ces vecteurs est lui même indexé par un autre tableau permettant d'accéder rapidement au nombre de couleurs dans l'image dont la projection selon un des trois axes est supérieure à une valeur donnée (voir Figure 5.7).

histo_brunTableaux utilisés pour stocker l'histogramme par Braquelaire et Brun

Plus précisément, on utilise les constructions suivantes :

• Un tableau V contenant l'ensemble des triplets de couleurs contenus dans l'image et pour chaque triplet le nombre de pixels correspondant à ce triplet.
• Trois vecteurs $tab_{c_1}$, $tab_{c_2}$, $tab_{c_3}$ triant les valeurs de V suivant ${c_1},{c_2}$ et ${c_3}$
  • les valeurs constantes de ${c_1}$ dans $tab_{c_1}$ sont triées suivant ${c_2}$,
  • les valeurs constantes de ${c_2}$ dans $tab_{c_2}$ sont triées suivant ${c_1}$,
  • les valeurs constantes de ${c_3}$ dans $tab_{c_3}$ sont triées suivant ${c_1}$.
  Les plages grisées sur la Figure 5.7 visualisent des zones référençant des triplets ayant une même valeur de ${c_1}$ dans le premier cas, de ${c_2}$ dans le second et de ${c_3}$ dans le troisième.
• Trois vecteurs entrée_${c_1}$, entrée_${c_2}$ et entrée_${c_3}$ référençant les tableaux tab_${c_1}$, tab_${c_2}$,tab_${c_3}$ et vérifiant la propriété suivante :
  $$\forall j \in \{1,2,3\}~~\forall k \in [Min_j,Max_j]~~\forall ~l\geq entre\_c_j[k]~~ V[tab\_c_j[l]].c_j \geq k.$$
  Ils permettent donc d'accéder directement à l'ensemble des couleurs dont la composante $c_j$ choisie est supérieure à k.

La résolution de l'équation 5.3 s'effectue alors en trois temps (posons pour fixer les idées i=1, j=2 et k=3)

1. Trouver l'ensemble des couleurs vérifiant ( ${c_1} = \alpha$) à l'aide de entrée_${c_1}$. Cet ensemble est codé de façon continue dans tab_${c_1}$.
2. Chercher par dichotomie dans la partie de tab_${c_1}$ définie précédemment les indices vérifiant $m_2 \leq V[j].{c_2} < M_2$. Ces indices sont stockés de façon continue dans tab_${c_1}$.
3. Parcourir l'ensemble des indices trouvés dans (2) pour ne retenir que ceux vérifiant $m_3~\leq~V[j].{c_3}~<~M_3$.

Cette structure de données permet donc :

• de stocker uniquement les couleurs effectivement présentes dans l'image,
• de supprimer l'étape de préquantification.

Notons toutefois que cette structure de données relativement complexe est assez peu adaptée à tout autre requête que celle exprimée par l'équation 5.3. Son utilisation reste donc assez limitée.