La méthode de Brun

Nous avons vu dans la section 6.4.5 que le calcul de la fonction pouvait être réalisé à l'aide d'un diagramme de Voronoi 3D discret. Les principales limitations de cette méthode viennent du pré-calcul de la couleur représentative de chaque couleur de l'espace . Les travaux menés par Otha [OKS80] et confirmés par nos propres expérimentations montrent que l'essentiel de l'information d'une image naturelle (par opposition à une image de synthèse) est contenu dans le plan vectoriel $P_{princ}$ défini par les deux premiers vecteurs propres de la matrice de covariance de l'image. Le plan $P_{princ}$ nous permet donc d'approximer efficacement l'ensemble des couleurs de l'image. De plus, la matrice de passage de l'espace de couleurs à l'espace des vecteurs propres étant une matrice orthogonale, les calculs de distances effectués dans l'espace des vecteurs propres seront similaires aux calculs de distances effectués dans l'espace de couleur initial. Il est donc possible d'approximer de manière efficace le diagramme de Voronoi 3D discret de centres $\{c_1,\dots,c_K\}$ par un diagramme de Voronoi 2D discret défini par les centres $\{p(c_1),\dots,p(c_K)\}$ où $p(c_i)$ représente la projection de la couleur représentative $c_i$ sur le plan $P_{princ}$. Cette projection est définie par les équations suivantes :

$$\left\{ \begin{array}{lll} p(c)_{v_1} &=& v_1\bullet c \\ p(c)_{v_2} &=& v_2\bullet c \\ \end{array}\right.$$

où $v_1$ et $v_2$ représentent les deux premiers vecteurs propres de la matrice de covariance et $\bullet$ le produit scalaire.

L'utilisation d'un diagramme de Voronoi 2D discret impose de délimiter le domaine sur lequel les calculs de distances d'un point $p(c)$ aux centres $\{p(c_1),\dots,p(c_K)\}$ seront effectués. A cette fin, nous calculons la boite englobante des projections $p(c)$ des couleurs de l'image sur le plan $P_{princ}$. Le calcul de cette boite englobante s'effectue en déterminant les valeurs $max_1, max_2$ et $min_1, min_2$ définies par :

$$\forall i \in \{1,2\} \left\{ \begin{array}{lll} min_i &=& M... ...i}\\ max_i &=& Max_{c \in C}~p(c)_{v_i}\\ \end{array}\right.$$

où $C$ désigne l'ensemble des couleurs de l'image.

Le calcul du diagramme de Voronoi 2D discret peut alors s'effectuer en allouant une image de taille $(max_1-min_1)\star (max_2-min_2)$ et en affectant à chaque point discret de l'image l'indice de son centre le plus proche parmis les points $\{p(c_1),\dots,p(c_K)\}$. Cette initialisation du diagramme de Voronoi 2D discret est effectuée grâce à la méthode incrémentale de Danielson [Dan80] de complexité |V_I| où $\vert V_I\vert$ représente la taille du diagramme de Voronoi 2D discret associé à I.

Le calcul du diagramme $V_I$ impose donc de parcourir une fois l'image pour calculer les deux vecteurs propres $v_1$ et $v_2$, puis de reparcourir celle ci afin de déterminer les points $(min_1,min_2)$ et $(max_1,max_2)$. La compléxité totale du calcul du diagramme $V_I$ est donc égale à 2|I| + |V_I|.

Le diagramme de Voronoi $V_I$ associé à une image $I$ nous permet donc d'approximer le calcul de la fonction définie dans la section 6.4.1. Un algorithme utilisant cette approximation pour réaliser l'inversion de la table de couleurs est donné sur la figure 4.

L'utilisation d'un diagramme de Voronoi 2D discret induit deux types d'approximation : Une approximation due à la projection de l'ensemble des donnés 3D de l'image sur le plan $P_{princ}$ et une approximation due à la discrétisation du plan $P_{princ}$ pour calculer le diagramme de Voronoi 2D. Du fait de ces deux approximations l'algorithme 4 est suceptible de renvoyer un indice différent de celui fourni par la fonction . Toutefois, les erreurs dues aux approximations induisant de petites erreurs pour le calcul des distances, les erreurs commises par l'algorithme 4 se situent souvent entre deux indices dont les cellules sont adjacentes. Afin de supprimer ce type d'erreur nous déterminons durant le calcul de $V_I$ le diagramme de Delaunay $D_I$ associé à $V_I$. Ces deux structures sont alors combinées de la façon suivante. Soit $V_I[p(c)]$ l'indice de la cellule contenant la projection de $c$. L'utilisation du diagramme de Delaunay nous permet d'acceder à la structure $D_I[V_I[p(c)]]$ contenant l'ensemble des cellules adjacentes à $V_I[p(c)]$. L'utilisation du nouveau diagramme $D_I$ nous permet d'affecter à $c$ la couleur la plus proche de celui-ci parmis l'ensemble des couleurs représentatives dont l'indice appartient à $D_I[V_I[p(c)]]$. Ceci définit une nouvelle fonction ${\bf q}$ donnée par l'équation :

$${\bf q }(c) = Arg Min_{i\in D_I[V_I[p(c)]]} \Vert c_i -c\Vert$$

où $V_I(p(c))$ représente l'indice de la cellule contenant $c$ et $D_I(k)$ l'ensemble des indices dont les cellules sont adjacentes à la cellule d'indice $k$.

Un algorithme utilisant le diagramme de Delaunay $D_I$ et la fonction ${\bf q}$ pour inverser la table de couleurs d'une image est représenté sur la figure 5.

La complexité moyenne de la fonction ${\bf q}$ est déterminée par le nombre moyen de cellules adjacentes à une cellule donnée. Les travaux d'Etienne Bertin [Ber94] ont montré que le nombre moyen d'arrêtes d'une cellule de Voronoi est indépendant du nombre de germes et approximativement égal à $6$. algo-inv1Premier approche pour l'inversion de la tables de couleurs. Les symboles $I(P)$ et $V_I[proj]$ représentent respectivement la couleur du pixel $P$ et l'indice de la cellule de Voronoï contenant $proj$. La projection sur le plan $P_{princ}$ est notée $p$. algo-inv2Second algorithme d'inversion de tables de couleurs. Les symboles $I(P)$ et $V_I[proj]$ représentent respectivement la couleur du pixel $P$ et l'indice de la cellule de Voronoi contenant $proj$.La projection sur le plan $P_{princ}$ est notée $p$.