Papillonnage et mathématiques des images

Piste bleue 28 janvier 2011  - Ecrit par  Agnès Desolneux, Julie Delon Voir les commentaires (3)

Les vieux films présentent de nombreux défauts. L’un d’entre eux est le papillonnage (appelé « flicker » en anglais) qui est visible sous forme de fluctuations importantes de contraste d’une image du film à l’autre. Le but de cet article est de montrer comment les images peuvent se modéliser comme des objets mathématiques, et comment manipuler ces objets de façon à modifier les contrastes et corriger le papillonnage.

Les vieux films présentent de nombreux défauts : des rayures, des taches, mais aussi des défauts de luminosité qui se traduisent par des variations non naturelles de contraste dans le film. Ce sont ces défauts de luminosité qui sont désignés par le terme papillonnage (ou flicker pour reprendre le terme anglais).
Ces défauts de contraste peuvent être dus à la fois à la dégradation chimique du support du film (qui crée alors des zones plus sombres ou plus claires lors du visionnage), mais aussi à des problèmes de temps d’exposition variables d’une image à l’autre. Ceci est en particulier vrai pour les films tournés à l’époque où la pellicule était entraînée manuellement.

Ci-dessous, la vidéo un court extrait du film Les Aventures des Pieds Nickelés (Emile Cohl/Eclair, 1917-1918, copyright Marc Sandberg). Dans cet extrait, on se rend bien compte de la présence de papillonnage, qui donne l’impression que le film « clignote ».

Le papillonnage se rencontre également dans des films plus récents, comme dans certaines vidéos de type vidéo-surveillance ou vidéo-amateur.
Contrairement à d’autres défauts couramment observés dans les films (rayures,
poussières, etc.), le papillonnage ne fait pas apparaître de nouvelles structures dans les images. Sa particularité est donc d’être transparent, voire
quasiment « invisible » sur une image isolée. Seul le visionnage des images successives du film permet de se rendre compte de sa présence.

Image extraite du film Les Aventures des Pieds Nickelés (Emile Cohl/Eclair, 1917-1918) copyright Marc Sandberg. Le papillonnage d’un film est un défaut qui ne se voit pas sur une seule image.

Comment les mathématiques peuvent-elles intervenir pour éliminer ce type de défaut ? Tout d’abord, les films sont numérisés, ce qui veut dire que la pellicule est scannée, image par image, et que cette suite d’images numériques est stockée sur un ordinateur.
En général, une seconde de film comporte 24 images. Un film d’une heure, une fois scanné, contient donc 86400 images numériques.
Une image numérique en « noir et blanc » [1] est modélisée mathématiquement comme une fonction définie sur une grille rectangulaire de carrés (appelés pixels pour la contraction de « picture elements ») et à valeur dans l’ensemble des nombres positifs. La valeur de l’image en un pixel est appelée le niveau de gris de ce pixel.
Introduisons quelques notations utiles pour la suite de l’exposé. Si $v$ désigne une image numérique, définie sur une grille de $N\times M$ pixels, pour un pixel $(x,y)$, la valeur $v(x,y)$ est son niveau de gris. Dans ce texte, on considèrera que les niveaux de gris sont des valeurs entières comprises entre $0$ et $L$. Dans les images que l’on manipule tous les jours (photos numériques), les niveaux de gris prennent généralement des valeurs entières entre $0$ (noir) et $L=255$ (blanc). Des valeurs de $L$ beaucoup plus grandes sont utilisées dans des domaines plus pointus (comme en imagerie satellitaire par exemple).

A gauche, une image numérique qui contient $486 \times 324$ pixels. A droite, un extrait de l’image, de taille $10 \times 10$ pixels, avec quelques-uns de ces niveaux de gris indiqués en jaune.

Pour éliminer le papillonnage dans un film, on applique à toutes ses images numérisées des changements de contraste (nous verrons plus loin comment les construire).
Dire qu’une image $v$ subit un changement de contraste veut dire
qu’elle est transformée en $g(v)$ où $g$ est une fonction croissante : chaque pixel $(x,y)$ voit son niveau de gris
$v(x,y)$ devenir $g(v(x,y))$. L’intérêt d’utiliser une fonction $g$ croissante est qu’elle conserve l’ordre des niveaux de gris : si le pixel $(x_1,y_1)$ est plus sombre que le pixel $(x_2,y_2)$ dans l’image $v$, cette propriété reste vraie dans l’image $g(v)$.
En conséquence, un changement de contraste ne modifie pas le
contenu géométrique d’une image, c’est-à-dire qu’on voit la même chose dans l’image avant et après un changement de contraste. Il n’y a pas d’apparitions de nouveaux objets dans l’image.

Comment mesurer le contenu géométrique d’une image ? Ceci peut se faire à l’aide de ce qu’on appelle la carte topographique de l’image. Pour la définir, on commence par regarder les ensembles de niveau supérieur de l’image : on fixe un niveau de gris $n$ et on regarde l’ensemble des pixels ayant leur niveau de gris supérieur ou égal à $n$. La frontière de cet ensemble s’appelle alors une ligne de niveau. Ceci est illustré sur la figure ci-dessous.
Lors d’un changement de contraste, les ensembles de niveau sont préservés dans leur ensemble (un ensemble de niveau $n$ pour $v$ devient un ensemble de niveau $g(n)$ pour $g(v)$).

A gauche, l’image d’une porte de Sidi Bou Said (Tunisie). Au milieu, la même image ayant subi un changement de contraste. A droite, quelques lignes de niveau de cette image.

Le nom de carte topographique vient de l’analogie avec la géographie, où on peut voir $v(x,y)$ comme la mesure de l’altitude du terrain (niveau au dessus de la mer) au point de coordonnées $(x,y)$.

L’image de la porte de Sidi Bou Said (Tunisie), vue comme une carte topographique. Le niveau de gris en chaque point représente l’altitude de ce point.

Avant de s’attaquer à la restauration des films, commençons par étudier le cas de deux images.
Etant données deux images, on veut appliquer à chacune un changement de contraste tel que les deux images aient la même distribution de niveaux de gris. On dira alors qu’on a effectué une égalisation de contraste entre les deux images,
Pour formaliser tout cela, on commence par définir pour une image $v$ (de taille $N\times M$ pixels), son histogramme de niveaux de gris noté $h$ : c’est une fonction qui mesure le nombre de fois où chaque niveau de gris $n$ apparait dans l’image $v$. Ce qui peut s’écrire :
\[h(n)= \# \{ (x,y) \text{ tel que } v(x,y)=n \}, \]
où la notation $\#$ désigne le nombre d’éléments d’un ensemble.
On peut ensuite définir l’histogramme cumulé de l’image $v$ par
\[H(n)=\# \{ (x,y) \text{ tel que } v(x,y) \leq n \} = h(0)+h(1)+\ldots + h(n).\]
L’histogramme cumulé $H$ est une fonction croissante de $n$.
L’histogramme $h$ peut être reconstruit à partir de l’histogramme cumulé $H$ en remarquant que $h(n) = H(n) - H(n-1)$.

JPEG - 139.5 ko
De gauche à droite : une image, son histogramme cumulé H et son histogramme
h. En première approximation, la première « bosse » de l’histogramme h correspond à la zone sombre en bas de l’image, alors que la deuxième « bosse » correspond au ciel clair en haut de l’image.

Que devient l’histogramme cumulé d’une image $v$ lorsqu’elle subit un changement de contraste ?
Si on applique à $v$ un changement de contraste $g$, comme expliqué plus haut, alors l’histogramme cumulé de $g(v)$ est $H(g^{-1})$, où $H$ est l’histogramme cumulé de $v$, et où $g^{-1}$ est l’inverse de la fonction croissante $g$ [2]. En effet, pour un niveau de gris $n$ donné, le nombre de pixels $(x,y)$ tels que $g(v(x,y))$ est inférieur à $n$ est égal au nombre de pixels $(x,y)$ tels que $v(x,y)$ est inférieur à $g^{-1}(n)$, et ce nombre est par définition $H(g^{-1}(n))$.

En conséquence, en choisissant bien le changement de contraste $g$, on peut rapprocher la distribution de niveaux de gris de l’image $v$ de n’importe quelle autre distribution de niveaux de gris. Plus précisément, soit $G$ une fonction discrète strictement croissante sur $\{0,\dots ,L\}$, alors $G^{-1} \left( H(v)\right)$ est une image dont l’histogramme cumulé est donné par la fonction $H((G^{-1}(H))^{-1})=G$ (c’est la formule du paragraphe précédent avec $g=G^{-1}(H)$). Nous allons utiliser cette propriété dans ce qui suit pour donner à deux images une distribution de niveaux de gris commune.

En effet, on vient de voir que si on a deux images $v_1$ et $v_2$ d’histogrammes cumulés respectifs $H_1$ et $H_2$, alors pour n’importe quelle fonction $G$ discrète et croissante sur $\{0,\dots ,L\}$, les images $G^{-1} \left( H_1(v_1)\right)$ et
$G^{-1} \left( H_2(v_2)\right)$ ont même histogramme cumulé $G$. On est donc amené à répondre à la question : comment « bien » choisir $G$ ?
La réponse à cette question (voir le paragraphe déroulant ci-dessous pour les explications de cette réponse) est qu’il faut prendre $G=H_{1/2}$, où $H_{1/2}$ est appelée distribution mi-chemin ou midway entre $H_1$ et $H_2$ et est donnée par
\[H_{1/2}=\left(\frac{H_1^{-1}+H_2^{-1}}{2}\right)^{-1} .\]

Deux images et leurs histogrammes cumulés respectifs.

Les mêmes images qu’au-dessus après égalisation mi-chemin (midway) et leurs histogrammes cumulés.

Dans la formule ci-dessus, $H_{1/2}$ est définie comme étant la moyenne harmonique des histogrammes cumulés $H_1$ et $H_2$.

Pourquoi est-ce le « bon » choix pour $G$ ?

Pour bien choisir $G$, on veut qu’il vérifie un critère simple, à savoir : si $v_1$ et $v_2$ sont deux images provenant d’une même image $u$ par deux changements de contraste différents $g_1$ et $g_2$ (c’est-à-dire que $v_1=g_1(u)$ et $v_2=g_2(u)$) alors on veut que $G$ vérifie $G^{-1} \left( H_1(v_1)\right) = G^{-1} \left( H_2(v_2)\right)= \frac{v_1+v_2}{2}$. Et ceci est satisfait pour $G=H_{1/2}$ où $H_{1/2}$ est défini comme ci-dessus par la moyenne harmonique de $H_1$ et $H_2$.

D’autres choix pour $G$ non seulement ne vérifient pas le critère énoncé ci-dessus mais ont aussi, dans certains cas, l’inconvénient de créer des artefacts. C’est ce qui se passe par exemple si on applique à chaque image un changement de contraste qui amène son histogramme cumulé sur l’histogramme cumulé moyen
$(H_1+H_2)/2$. Ceci n’est pas satisfaisant, comme le montre l’exemple ci-dessous.

(a) Image d’un dégradé sombre, avec son histogramme et son histogramme cumulé. (b) Image d’un dégradé clair, avec son histogramme et son histogramme cumulé. (c) Image obtenue si on avait utilisé la moyenne arithmétique pour changer le contraste : on a ici créé une discontinuité dans le dégradé. (d) Image obtenue avec la moyenne harmonique des histogrammes cumulés : le résultat est conforme à ce qu’on attend - c’est un dégradé de niveau de gris « moyen ».

L’égalisation de contraste expliquée ci-dessus pour deux images peut se généraliser à un plus grand nombre d’images, et permet en particulier de restaurer un vieux film qui papillonne.
On note $(u_t)_{t=1,2,...,T}$ le film, c’est-à-dire que chaque $u_t$ est une image numérique, et $T$ est un entier qui désigne le nombre total d’images du film. Pour chaque $t$, on désigne par $H_t$ l’histogramme cumulé de $u_t$. La restauration consiste ici à modifier le contraste de chaque image $u_t$ de façon à lui donner le même contraste moyen que les $r$ images qui la suivent et les $r$ images qui la précèdent dans le film (en prenant par exemple $r=5$).
En d’autres termes, on restaure simplement le film en changeant chaque image $u_t$ en $\widetilde{u}_t$, qui est donnée par
\[\widetilde{u}_t (x,y)= \frac{1}{2r+1} \sum_{s=t-r}^{t+r} H_{s}^{-1} ( H_{t} (u_t(x,y))) .\]
Plus $r$ est grand, plus on prend en compte un grand nombre d’images dans le film pour restaurer $u_t$, et plus on élimine les fluctuations dues au papillonnage. En contrepartie, prendre une valeur de $r$ trop grande n’a pas forcément de sens si le film comporte beaucoup de mouvements de caméra ou d’objets qui se déplacent.

Voici pour finir quelques résultats.
La première vidéo montre l’effet de cette restauration sur l’extrait du film Les aventures des Pieds Nickelés, avec à gauche le film original et à droite le film corrigé. On voit que l’effet de papillonnage a globalement disparu : les différentes images du film ont maintenant des contrastes similaires.

Ci-dessous un deuxième exemple sur un extrait du court-métrage The Cure, de Charlie Chaplin, 1917.

Post-scriptum :

La rédaction d’Images des maths, ainsi que l’auteur, remercient pour leur relecture attentive,
les relecteurs dont le pseudonyme est le suivant : Yoann, tumiac et Anne-Laure Dalibard.

Notes

[1On parle généralement de films en « noir et blanc », pour les distinguer des films en couleur, mais dans l’absolu il faudrait plutôt parler de films en nuances de gris !

[2Comment est défini l’inverse ? Pour une valeur $n$ donnée, on a une valeur $k$ telle que $g(k)=n$, et c’est alors cette valeur $k$ qui est appelée l’inverse de $n$ par la fonction $g$ et qui est noté $k=g^{-1}(n)$. Si de plus on a deux fonctions croissantes $g_1$ et $g_2$, alors on a la propriété que $(g_1(g_2))^{-1}=g_2^{-1}(g_1^{-1})$.

Partager cet article

Pour citer cet article :

Agnès Desolneux, Julie Delon — «Papillonnage et mathématiques des images » — Images des Mathématiques, CNRS, 2011

Crédits image :

img_5174 - Julie Delon
img_5186 - Julie Delon
img_5179 - Julie Delon
img_5185 - Julie Delon
img_5253 - Julie Delon
img_5252 - Julie Delon
img_5254 - Julie Delon
img_5256 - Julie Delon

Commentaire sur l'article

  • Papillonnage et mathématiques des images

    le 28 janvier 2011 à 21:41, par Bruno Duchesne

    Merci pour cet article intéressant. Le « bon choix » pour G illustre parfaitement l’article de Benoît Kloeckner : http://images.math.cnrs.fr/Moyennes-I.html

    Répondre à ce message
  • Moyenne harmonique

    le 31 janvier 2011 à 15:29, par Rémi Peyre

    Bonjour,

    Je ne suis pas sûr d’avoir bien compris la formule définissant H_1/2 : les inverses qui apparaissent dans cette formule sont-ils des inverses de réels ou des inverses de fonctions ? J’ai en effet l’impression qu’on a des inverses de fonction, mais je n’ai jamais vu l’expression « moyenne harmonique » utilisée dans ce sens...

    Répondre à ce message
    • Moyenne harmonique

      le 1er février 2011 à 08:53, par Agnès Desolneux

      En effet, il s’agit bien d’inverses de fonctions. Peut-etre le terme de « moyenne harmonique » est-il du coup utilisé un peu abusivement dans ce cas. Il veut dire « fonction inverse de la moyenne (arithmétique) des inverses des fonctions ». Ce H_1/2 est aussi appelé la « distribution mi-chemin ».

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM