next up previous contents index
suivant: Structures de données monter: Histogramme d'images couleurs précédent: Histogramme d'images couleurs   Table des matières   Index


Multi-ensembles

De façon très générale, un multi-ensemble est un élément de $ {\cal P}(\RRn)\times {\cal F}(\RRn,\RR)$, où $ {\cal P}(\RRn)$ désigne l'ensemble des parties de $ \RRn$ et $ {\cal F}(\RRn,\RR)$ l'ensemble des applications de $ \RRn$ dans $ \RR$. Un multi-ensemble est donc un couple $ (C,f)$$ C$ est un sous-ensemble de $ \RRn$ et $ f$ une application de $ \RRn$ dans $ \RR$. Cette définition étant un peu trop générale pour nos besoins, nous avons adopté la définition suivante :
\begin{definition}
Soit ${\cal PB}(\RRn)$\ l'ensemble des parties born{\'e}es de...
...{\cal F}(\RRn,\RRp) /
f_{\vert\RRn-C} == 0\}.
\end{displaymath}\end{definition}
En d'autres termes, un multi-ensemble est la donnée d'un ensemble borné et d'une application réelle positive nulle hors de cet ensemble. Sauf mention contraire, tous les ensembles considérés dans ce chapitre seront des ensembles discrets. D'un point de vue informatique, les multi-ensembles peuvent être vus comme une extension de la notion d'histogramme à des espaces de dimension $ n$. La fonction associée à un ensemble est souvent appelée la fonction de fréquence ou de distribution. L'application de ce concept à l'image est assez immédiate. En effet, si nous considérons une image $ I$, on peut y associer un ensemble $ C$, égal à l'ensemble de valeurs $ v$ associées aux pixels de l'image. Nous pouvons alors définir $ f(v)$ comme le nombre de fois où le n-uplet $ (v_1,\dots,v_n)$ apparaît dans l'image. Par exemple, dans le cas d'une image couleur, $ f(0,0,0)$ représente le nombre de pixels noirs contenus dans l'image. La fonction de fréquence associe un poids à chaque élément du multi-ensemble. Ces poids peuvent être utilisés pour définir les moments, la moyenne ou la variance d'un multi-ensemble.


\begin{definition}
\index{Moments}
\par Soit \multn{} l'ensemble des multi-ensem...
...,f)}{\sum_{\col\in\C}f(\col)\col.\col^t}
\end{displaymath}
\par\end{definition}

Il est bien sûr possible de définir des moments d'ordres supérieurs, mais les ordres 0, 1 et 2 seront suffisants pour notre étude. Afin d'alléger les notations, on omettra généralement la fonction de fréquence lors du calcul de l'image d'un multi-ensemble. L'image de par , $ \Mze\left(\multi{}\right)$, sera donc notée plus simplement $ \Mze(C)$. On peut remarquer que (C) également noté $ \vert C\vert$ représente un scalaire alors que (C) et (C) sont des vecteurs de $ \RRn$$ n$ est la dimension de l'espace dans lequel est plongé l'ensemble $ C$. Usuellement, cette dimension est égale à 1 pour les images en niveaux de gris et 3 pour les images couleur. À partir des moments, on définit la moyenne, les variances et la matrice de covariance d'un multi-ensemble de la façon suivante :


\begin{definition}
Avec les notations pr{\'e}c{\'e}dentes, les fonctions {\bf mo...
...vement la
$i^{eme}$\ coordonn{\'e}e de \Mde(C) et $\mu(C)$.
\par\end{definition}

La fonction $ var_i$ nous permet de mesurer la variance d'un multi-ensemble le long d'un axe et peut servir à mesurer l'homogénéité d'un multi-ensemble. La mesure d'homogénéité que nous allons utiliser, appelée erreur quadratique, peut être vue comme une extension de la variance pour les dimensions supérieures à 1.


\begin{definition}
\index{Erreur!Quadratique}
L'{\bf erreur quadratique} d'un mu...
...) = \sum_{v\in C} f(v)\Vert v-\mu(C) \Vert^2 .
\end{displaymath}\end{definition}
L'erreur quadratique d'un multi-ensemble $ (C,f)$ est donc une mesure de l'écart des éléments de $ C$ par rapport à la moyenne $ \mu(C)$. Si nous appliquons ce concept à l'image, la moyenne $ \mu(C)$ représente le niveau de gris moyen (ou la couleur moyenne) de l'image et $ \ERROR(C)$ représente l'écart de l'ensemble des couleurs de l'image par rapport à cette moyenne.

Des calculs relativement simples montrent que l'erreur quadratique peut s'exprimer en fonction des moments et des variances. De fait, nous avons pour un multi-ensemble $ (C,f)$ donné :

$\displaystyle \ERROR(C) = \sum_{i=1}^{n}\Mde(C)_i - \frac{\Mun(C)_i^2}{\Mze(C)} = \Mze(C)\sum_{i=1}^{n} var_i(C).$ (5.1)

L'erreur quadratique d'un multi-ensemble $ (C,f)$ peut donc également être vue comme la somme de ses variances pondérées par le cardinal de $ (C,f)$. Cette pondération permet de tenir compte du fait qu'une même erreur est a priori plus importante si elle se produit sur un grand ensemble que sur un petit.

Jusqu'à présent, nous avons vu la définition d'un multi-ensemble et les différentes mesures que l'on peut associer à celui-ci. Les multi-ensembles peuvent également être combinés pour créer de nouveaux multi-ensembles.


\begin{definition}
Soit $(C_1,f_1)$\ et $(C_2,f_2)$\ deux {\'e}l{\'e}ments de \m...
...) - (C_2,f_2) &=& (C_1 - C_2,\max(0,f_1-f_2))\\
\end{eqnarray*}\end{definition}

La combinaison de plusieurs multi-ensembles prend tout son intérêt en segmentation lorsque l'on manipule une image partitionnée en régions. Supposons par exemple que l'on désire fusionner deux régions $ R_1$ et $ R_2$ adjacentes dans l'image. Les multi-ensembles $ (C_1,f_1)$ et $ (C_2,f_2)$ correspondant à $ R_1$ et $ R_2$ ne sont a priori pas distincts. Le multi-ensemble correspondant à la fusion des régions $ R_1$ et $ R_2$ est alors égal à la somme des multi-ensembles $ (C_1,f_1)$ et $ (C_2,f_2)$. Inversement, si on désire partitionner une région $ R$ en deux sous-régions $ R_1$ et $ R_2$, nous avons la relation : $ (C,f)-(C_1,f_1) = (C_2,f_2)$$ (C,f)$ désigne le multi-ensemble associé à $ R$. Le problème est alors d'évaluer l'erreur quadratique de l'union ou de la différence de deux multi-ensembles. Un premier pas vers l'évaluation de l'erreur quadratique est donné par la proposition suivante:


\begin{proposition}
Soient $\{(C_1,f_1),\dots,(C_p,f_p)\}$\ un ensemble de multi...
...}~~\MInd{i}(C) = \sum_{j=1}^{p} \MInd{i}(C_j)
\end{displaymath}\end{proposition}

\begin{preuve}
Nous allons {\'e}tablir la propri{\'e}t{\'e} pour le cas $p=2$, l...
...{i}(C) &=& \MInd{i}(C_1) +\MInd{i}(C_2)
\end{array}\end{displaymath}\end{preuve}

Une propriété importante de la moyenne se déduit trivialement de l'additivité des moments :
\begin{lemme}
Soient \multi{1} et \multi{2} deux {\'e}l{\'e}ments de \multn{}. O...
...C_2\vert\mu(C_{2})}{\vert C_1\vert+\vert C_2\vert}.
\end{displaymath}\end{lemme}


\begin{corollaire}
Soient \multi{1}, \multi{2} et $\multi{}=\multi{1}+\multi{2}$...
...}{\vert C_1\vert}\left(\mu(C)-\mu(C_2)\right).
\end{displaymath}\end{corollaire}

\begin{preuve}
% latex2html id marker 8901En utilisant le lemme~\ref{moy-somme...
...\vert}{\vert C_1\vert}\left(\mu(C)-\mu(C_2)\right)
\end{displaymath}\end{preuve}

L'additivité des moments et le lemme précédent nous permettent de définir un théorème important permettant d'exprimer l'erreur quadratique de la somme de deux multi-ensembles.
\begin{theoreme}
Soient \multi{1} et \multi{2} deux multi-ensembles de \multn{}....
...t+\vert C_2\vert}\Vert\mu(C_{1})-\mu(C_{2})\Vert^2.
\end{equation}\end{theoreme}

\begin{preuve}
% latex2html id marker 8938Si nous utilisons l'{\'e}quation~\re...
...ert+\vert C_2\vert}\Vert\mu(C_{1})-\mu(C_{2})\Vert^2
\end{eqnarray*}\end{preuve}

Comme nous l'avons vu, l'erreur quadratique $ \ERROR(C)$ mesure l'homogénéité de l'ensemble $ C$. Afin de mesurer l'homogénéité d'une partition, $ \{C_1,\dots,C_n\}$, on définit l'erreur quadratique d'une partition de la façon suivante :
\begin{definition}
\index{Erreur!De partition}
Soient $(C_1,f),\dots,(C_p,f)$\ d...
...splaymath}
\E(C) = \sum_{i=1}^{p} \ERROR(C_i).
\end{displaymath}\end{definition}

La partition de $ C$ en sous-ensembles minimisant $ \E(C)$ est un problème complet pour des espaces de dimension supérieure à 1 [WZ91]. Dans le cas mono-dimensionnel, donc pour des images en niveaux de gris, Wong, Wan et Prusinkiewicz ont élaboré un algorithme permettant de trouver la partition optimale avec une complexité en $ O(NlogN)$ [WWP89].

Le découpage d'un multi-ensemble s'effectue souvent en considérant un de ses sous-ensembles et en faisant croître celui-ci jusqu'à obtenir une partition qui induit une erreur quadratique minimale. Du fait de la complexité du problème on ne choisit généralement pas la partition qui minimise globalement l'erreur quadratique, mais plus simplement la partition induisant une erreur quadratique minimale sur un ensemble de partitions envisagées. La partition la plus couramment utilisée est la partition par plans. Le multi-ensemble est alors découpé en deux sous-ensembles de par et d'autre du plan. Le nombre de plans susceptibles de couper un multi-ensemble étant encore trop grand, on restreint les possibilités en fixant la normale à celui-ci. L'ensemble des partitionnements possibles est alors égal au nombre de plans parallèles susceptibles de couper le multi-ensemble. Ce type de découpe utilise la projection d'un multi-ensemble définie de la façon suivante :
\begin{definition}
Soit \multi{} un {\'e}l{\'e}ment de \multn{}. La {\bf project...
...aymath}
C_t = \{v \in C~/~ v.\vec{n} \leq t \}
\end{displaymath}\end{definition}
$ v.\vec{n}$ désigne le produit scalaire des vecteurs $ v$ et $ \vec{n}$. La variable $ t$ joue dans ce cadre le rôle d'une abscisse le long de la direction $ \vec{n}$.


next up previous contents index
suivant: Structures de données monter: Histogramme d'images couleurs précédent: Histogramme d'images couleurs   Table des matières   Index
Brun Luc 2004-03-25