Vocabulaire

On note S l'ensemble des sites (une matrice de pixels).

Image :

Une image (ou configuration) x est une fonction de S dans l'ensemble des teintes de gris E : x = { x(s), s dans S} x est une réalisation du champ aléatoire X= {X(s), s dans S}.

Ensemble des teintes de gris :

E peut être aussi bien un ensemble discret à deux éléments qu'un ensemble continu :
  • [0, 1]
  • [0, 255]
  • IR

    Voisinages :

    On note V(s), l'ensemble des voisins du site s et V le système de voisinage qui en découle, V = {V(s), s dans S}.

    Cliques :

    Un sous-ensemble C de S est une clique relative à V si et seulement si :
  • card(C) = 1 (C = {s})
  • card(C) >= 2 et deux éléments distincts de C sont voisins pour V

    Champ de Markov

    Définition :

    Soit X = {X(s), s dans S}, un champ aléatoire. X est un champ de Markov si et seulement si :
  • P(X = x) > 0, pour tout x de l'espace des réalisations possibles.
  • P(X(s) = x(s)/ X(r) = x(r), r<>s) = P(X(s) = x(s)/ X(r) = x(r), r dans V(s))

    Théorème d'Hammersley- Clifford (1974) :

    Un champ aléatoire de portée bornée (taille des voisinages finie) dans un espace des teintes de gris discret, sur un ensemble de sites fini ou dénombrable est un champ de Markov si et seulement si :

    P(X = x) = 1/Z* exp(-U(x))

    où U(x) est la somme sur toutes les cliques des énergies de clique. Cette distribution est appelée distribution de Gibbs.

    La régularisation par champ de Markov

    Pour présenter les possibilités des champs de Markov en restauration, nous allons construire une image bruitée grâce à un bruit blanc gaussien additif. L'image d'origine est très célèbre puisqu'il s'agit de Lenna. Par addition d'un bruit blanc gaussien on obtient lennabruitée.

    La régularisation consiste, grâce à une modélisation par champ de Markov, à restaurer, segmenter ou détecter les contours dans une image. Pour le débruitage, il s'agit de trouver le niveau de gris qui a la probabilité d'apparition maximale connaissant les niveaux des pixels voisins. On choisit un potentiel pour chacune des cliques de l'image. Pour simplifier, nous avons attribué le même potentiel pour toute les cliques d'un même ordre.

    Pour les cliques d'ordre 2 :

    pot(x, y) = 1/(1 + |x - y|/delta)

    où x et y représente les niveaux de gris de deux pixels appartenant à la même clique.

    La probabilité d'apparition du niveau de gris s'exprime alors par la fonction suivante :

    P(X=x / V(X)) = (exp(-(y-x)^2/2*sigma^2 + beta * (somme(pot(cliques)))))/Z

    où sigma et beta sont des paramètres de régularisation et Z un facteur de normalisation. L'exponentielle étant croissante, il suffit de maximiser :

    -(y-x)^2/2*sigma^2 + beta * (somme(pot(cliques)))

    (ou de minimiser l'opposé).

    On a utilisé l'algorithme du gradient pour effectuer les modifications sur l'image. Cet algorithme consiste à parcourir l'image pixel par pixel, à chaque pixel on parcourt tous les niveaux de gris et finalement, on garde le niveau pour lequel on a une fonction de coût minimale. Cet algorithme converge en une dizaine de tours.

    En ne considérant que les cliques horizontales, on voit nettement l'apparition d'une structure lignée horizontale sur Lenna.

    De même, si on ne considère que les cliques verticales, on voit apparaître une structure verticale sur Lenna. Pareil avec seulement les cliques diagonales dans une seule direction.

    Finalement, en combinant toutes les cliques d'ordre 2 en 8-connexité, on obtient une image un peu debruitée (les paramètres ne sont pas bien réglés, mais ce n'était pas le but de l'exercice).

    A propos des cliques d'ordre supérieur...

    Dans la pratique, on n'utilise pas les cliques d'ordre 3 et plus car les programmes deviennent très lourds et elles n'apportent pas grand chose à la régularisation. Voilà ce que l'on peut obtenir en n'utilisant que les cliques d'ordre 3 : Lenna3. Il n'y a pas beaucoup de différences avec l'image bruitée d'origine, n'est-ce pas?

    Pour avoir le programme...