\chapter{L'éditeur de Poisson}
\setcounter{exo}{0}
\def\bv{{\bf v}}
 
  On note pour une fonction $C^2$ de deux variables $\Delta u(x,y)=\frac{\partial^2u}{\partial x^2}+\frac{\partial^2u}{\partial y^2}.$ C'est le Laplacien de $u$. 
L'équation de Poisson s'écrit  
\begin{equation}\label{Poisson}
 \left\{\begin{array}{ll}
\Delta u(x)= f   & \hbox{ si } x\in \Omega   \\
 u(x) = g(x)      & \hbox{ si } x\in \partial \Omega.
\end{array}\right.
\end{equation}


L'équation est universelle en physique (électrostatique, mécanique des fluides, chaleur, membranes minces, ...). Ici, nous allons l'appliquer à un problème nouveau, la manipulation des images que l'on appelle en anglais "editing" et que nous appellerons faute de mieux ``édition'' d'image. Le but est de manipuler localement une image ou les images successives d'un film en  corrigeant localement la couleur, en ajoutant ou enlevant des détails, en les rehaussant, etc.
Ce chapitre suit de près la méthode présentée par trois chercheurs du laboratoire anglais de Microsoft, Patrick Pérez, Michel Gangnet, et Andrew Blake, publiée en 2003. 
Ces auteurs partent d'observations psychophysiques qui suggèrent que notre vision perçoit le Laplacien des images, plutôt que les images elles-mêmes.  Puis ils remarquent que ce n'est pas un problème puisqu'une fonction définie sur un domaine $\Omega$ peut être reconstruite à partir de son Laplacien, et de valeurs spécifiées sur le bord du domaine $\partial \Omega$.

Pour résoudre ce problème, on peut lui donner une forme {\it variationnelle}. L'interprétation dite de la membrane mince considère que le plus simple interpolant possible de $g(x)$ connue uniquement sur le contour $\partial \Omega$ est obtenu en minimisant l'énergie d'une membrane élastique s'appuyant sur $g$:
%\begin{figure}
\begin{center}
 \includegraphics[width=10cm]{Figures/Figure4PerezJoconde.eps}
%\caption{}
\end{center}
%\end{figure}

 \begin{equation}\label{variationnelPoisson}
\left\{\begin{array}{ll}
\min_u\int_\Omega |Du|^2(x)dx  &  \\
u(x)= g(x)  &  \hbox{ si } x\in \partial \Omega.
\end{array}\right.
\end{equation}
Alors le minimiseur $u$ satisfera ``l'équation de Laplace avec condition de bord de type Dirichlet'':

\begin{equation}\label{Poissonmembrane}
\left\{\begin{array}{ll}
(\Delta u)(x)= 0  & \hbox{ si } x\in \Omega,     \\
 u(x)  = g(x) &  \hbox{ si } x\in \partial \Omega. 
\end{array}\right.
\end{equation}
Les auteurs remarquent que si on applique cette solution pour interpoler une image dans une région $\Omega$ de l'image où on a supprimé un objet, l'interpolation donnera un effet visuel brouillé, flou. L'interpolant est trop régulier.  Il ne faut donc pas juste rendre l'image harmonique dans le sous-domaine (une fonction dont le laplacien est nulle est appelée {\it harmonique}). Il faut donner à cette fonction un gradient, et les auteurs proposent donc de donner à l'image ce qu'ils appellent un ``guidance fied'' $v$, c'est à dire un champ de vecteur défini sur $\Omega$ dont le gradient de $u$ devra être le plus proche possible.

Cela conduit à résoudre:

\begin{equation}\label{guidanceequation}
\left\{\begin{array}{ll}
\min_u\int_\Omega |Du-v|^2(x)dx   &  \\
 u(x)  = g(x)  &  \hbox{ si } x\in \partial \Omega,
\end{array}\right.
\end{equation}
%\begin{figure}
\begin{center}
 \includegraphics[width=8cm]{Figures/Figure6PerezGraffity.eps}
%\caption{}
\end{center}
%\end{figure}
dont  le minimum $u$ est l'unique solution de

\begin{equation}\label{Poissonmembraneavecpoids}
\left\{\begin{array}{ll}
(\Delta u)(x)= div(\bv)  & \hbox{ si } x\in \Omega \\
 u(x)  = g(x) &  \hbox{ si } x\in \partial \Omega,
\end{array}\right.
\end{equation}
où on note $div(\bv)=\frac{\partial v_1}{\partial x}+\frac{\partial v_2}{\partial y}.$
Cette dernière équation donne selon les auteurs toute la machinerie pour faire de l'édition d'images, mais il va falloir bien spécifier selon les applications la forme de $\bv$!

Commençons par regarder le cas où $\bv=Dw$ est lui même le gradient d'une fonction $w$. Alors on a $div(\bv)=\Delta w$, et en posant $z=u-w$, l'équation peut se réécrire comme une équation de Poisson:

\begin{equation}\label{Poissonmembrane}
\left\{\begin{array}{ll}
(\Delta z)(x)= 0 & \hbox{ si }  x\in \Omega \\
 z(x)  = (g-w)(x) & \hbox{ si } x\in \partial \Omega,
\end{array}\right.
\end{equation}
% \begin{figure}
\begin{center}
 \includegraphics[width=9cm]{Figures/Figure2PerezRides.eps}
%\caption{}
\end{center}
%\end{figure}


\subsection{Résolution discrète}
On suppose que les images sont en fait définies sur une grille discrète $\Omega_d.$ On note $\partial \Omega_d$ l'ensemble des pixels bordant $\Omega_d$. Plus précisément on note
pour tout pixel $x=(i,j)$ son voisinage discret $\mathcal N(x)=\{(i-1,j), \;(i+1,j), \;
(i,j-1),\; (i,j+1)\}$. Un point $x$ est dans le bord de $\Omega_d$ s'il n'est pas dans $\Omega_d$, mais si $\mathcal N(x)\cap \Omega_d\neq \emptyset.$  Quand la forme du domaine discret $\Omega_d$ n'est pas rectangulaire, la technique de Fourier ne marche plus. On résoud donc directement le problème variationnel (\ref{guidanceequation}) sous forme discrète:
\begin{equation}\label{variationaldiscrete}
\left\{\begin{array}{ll}
\min_u\sum_{x\in\Omega_d,\;y\in\mathcal N(x)} \left(u(x)-u(y)-v_{i(x,y)}(\frac{x+y}2) \right)^2 &  \\
 u(x)  = g(x) &\hbox{ si } x\in \partial \Omega_d,
\end{array}\right.
\end{equation}
%\begin{figure}
\begin{center}
 \includegraphics[width=9cm]{Figures/Figure7PerezArcenCiel.eps}
%\caption{}
\end{center}
%\end{figure}
où $i(x,y)=1$ si $y=x\pm (1,0)$, et $i=2$ si $y=x\pm (0,1).$ La solution de cette minimization d'une forme   quadratique en dimension finie donne en dérivant:
\begin{equation}\label{equationsdePoissondiscret}
\forall x\in\Omega_d, \;\;|\mathcal N(x)|u(x)-\sum_{y\in\mathcal N(x)\cap\Omega_d}u(y)=\sum_{y\in\mathcal N(x)\cap\partial\Omega_d}g(y)+\sum_{y\in\mathcal N(x)}\nu(x,y),
\end{equation}
où $\nu(x,y)=,v_{i(x,y)}(\frac{x+y}2)$. $|\mathcal N(x)|$ est le cardinal de $\mathcal N(x)$, qui vaut entre 1 et 4 (on suppose que $\Omega_d$ est connexe discret, à savoir que tout point de $\Omega_d$ a au moins un voisin dans $\Omega_d$).
 Dans le cas où $x$ est dans l'intérieur de $\Omega_d$, c'est-à-dire que $\mathcal N(x)\subset \Omega_d$, (\ref{equationsdePoissondiscret}) devient

\begin{equation}\label{equationsdePoissondiscretalinterieur}
|\mathcal N(x)|u(x)-\sum_{y\in\mathcal N(x)}u(y)= \sum_{y\in\mathcal N(x)}\nu(x,y).
\end{equation}
Le système d'équations (\ref{equationsdePoissondiscret}) est un système linéaire dont la matrice est symétrique et définie positive. Le système a beaucoup d'inconnues, autant que de pixels dans $\Omega_d$, mais la matrice est ``creuse'', c'est-à-dire qu'elle a beaucoup de zéros. On peut donc résoudre le système par une méthode classique, telle que la méthode itérative de Gauss-Seidel.
%\begin{figure}
\begin{center}
 \includegraphics[width=9cm]{Figures/Figure8PerezAvion.eps}
%\caption{}
\end{center}
%\end{figure}
\subsection{Clonage}
La première application est l'insertion d'un morceau d'une image $v_0$ dans une image $u_0$. Le domaine de collage est $\Omega_d$.  Si on fait un simple copier-coller des valeurs des pixels de $v_0$ dans une image $u$,  le bord de $\Omega_d$ sera visible car il y aura en général un fort  contraste, les anciennes couleurs de $u$  sur le bord extérieur de $\Omega_d$ contrastant avec les nouvelles couleurs rapportées de $v_0$ sur bord intérieur. Donc pour le clonage soit efficace, il faut en quelque sorte adapter harmonieusement le morceau de $v_0$ à son nouvel environnement dans $u$. Ici, la remarque  que  l'essentiel de l'information perceptive d'une image est contenue dans son laplacien est cruciale. On ne  va pas cloner $v_0$, on va se contenter de cloner son laplacien!
Donc on pose $\bv=Dv_0$. On a $div(\bv)=\Delta v_0$, et donc l'équation (\ref{Poissonmembraneavecpoids}) devient
\begin{equation}\label{Poissonclonage}
\left\{\begin{array}{ll}
\Delta u(x)= \Delta v_0(x)  & \hbox{ si } x\in \Omega\\
 u(x)  = u_0(x) &\hbox{ si } x\in \partial \Omega.
\end{array}\right.
\end{equation}
En discret, cela donne donc à nouveau l'équation (\ref{equationsdePoissondiscret}), avec 
\begin{equation}\label{Clonagediscretequations}
\nu(x,y)=(v_0(x)-v_0(y))(\frac{x+y}2).
\end{equation}
Voyons les choses encore un peu plus simplement. Le clonage consiste à reconstruire une image qui  soit semblable à $v_0$ dans $\Omega$, et semblable à $u_0$ à l'extérieur de $\Omega$. Considérons maintenant le domaine rectangulaire de l'image $R$. Dans le modèle précédent, on ne garde que le laplacien du clône $v_0$, mais on garde intégralement $u_0$ à l'extérieur de $\Omega$.  Si nous nous autorisons des modifications (qui seront visuellement peu perceptibles) de $u_0$ aussi à l'extérieur, si nous voulons traiter les deux images à fusionner de manière symétrique, il est logique de garder que le laplacien de l'une et de l'autre. On est alors amenés à chercher une image $u$ dont le laplacien est celui de $u_0$ dans $\Omega^c$, et celui de $v_0$ dans $\Omega$. Posons donc

$$
\delta (x)=
\left\{\begin{array}{ll} \Delta v_0(x)  & \hbox{ si  }x\in \Omega\\
                          \Delta u_0(x)  & \hbox{ si } x\in \Omega^c.
\end{array}\right.
$$
Alors le problème de clonage se ramène à résoudre
\begin{equation}\label{clonagefusion}
\Delta u(x)=\delta(x), \;\; x\in R
\end{equation}
Cette équation est indéterminée si on ne fixe pas ce qui se passe sur le bord, et on doit  donc spécifier par exemple que $u(x)$ sera périodique, ou symétrique-périodique. On voit alors que l'équation précédente va pouvoir se résoudre par Fourier, ou encore mieux par DCT.
%\begin{figure}
\begin{center}
 \includegraphics[width=8cm]{Figures/Figure10PerezContrasteCouleur.eps}
%\caption{}
\end{center}
%\end{figure}

\subsection{Surimpression}
Nous allons maintenant jouer à un jeu encore plus subtil proposé par Patrick Pérez et ses collaborateurs, la surimpression. Il s'agit encore de cloner une partie d'une image $v_0$ dans l'image $u_0$,  mais cette fois-ci on veut que les détails de l'image $u_0$ continuent de se voir en fond. On veut donc que les deux images se voient l'une à travers l'autre, donc un effet de transparence. L'idée la plus simple est de faire bêtement $\frac {u_0+v_0}2$ dans le domaine $\Omega$, mais alors on verra une brusque transition au bord du domaine. L'idée que  l'on va appliquer est que pour voir à la fois $u_0$ et $v_0$ il  suffit de voir leurs contours quand ils sont nets. On définit donc un nouveau champ de vecteurs $\bv$ (qui va devenir en quelque sorte le nouveau gradient) par
$$
\bv (x)=
\left\{\begin{array}{ll} D v_0(x)  & \hbox{ si }|Dv_0(x)|\geq |Du_0(x)| \hbox{ et } x\in \Omega\\
 Du_0(x) & \hbox{ sinon}.
\end{array}\right.
$$
En discret avec  l'équation (\ref{variationaldiscrete}), cela donne

$$
\nu(x,y)
=\left\{\begin{array}{ll} v_0(x)-v_0(y)  & \hbox { si }|v_0(x)-v_0(y)|\geq |u_0(x)-v_0(y)| \hbox{ et }x\in \Omega\\  
  u_0(x)-u_0(y) &\hbox{ sinon}.
\end{array}\right.
$$
Là encore, on peut choisir de résoudre le problème sur un domaine rectangulaire, pour profiter d'une éventuelle implémentation en Fourier.

\subsection{Edition sélective}
%\begin{figure}
\begin{center}
 \includegraphics[width=8cm]{Figures/Figure11PerezDecolorisationFond.eps}
%\caption{}
\end{center}
%\end{figure}
L'édition sélective consiste à modifier le champ de gradient de l'image, de manière par exemple à ne garder que les gradients qui intéressent l'éditeur. Par exemple, on ne voudra garder que les bords les plus marquants de l'image, auquel cas on pose
$$\forall x\in R,\; \bv(x)=M(x)Du_0(x),$$
où $M(x)$ est masque binaire qui vaut 1 sur les bords de l'image (les points à fort gradient) et zéro ailleurs. Cette opération a été proposée par plusieurs auteurs pour expliquer notre perception de la couleur indépendamment des phénomènes d'ombrage. Ainsi Blake a-t-il proposé de prendre
$$\bv(x)=h(|Du_0(x)|)Du_0(x),$$
où $h(s)=1$  si $s\geq \delta$ est supérieure à un seuil fixé, et $h(s)=0$ sinon.  
\dexer Proposer un calcul discret pour le $\bv(x)$ proposé par Blake, et donner l'équation (\ref{equationsdePoissondiscret}) correspondante.
\fexer
La méthode proposée par les auteurs de ``Poisson editing'' est légèrement différente. Ils disposent d'un masque $M(x,y)$ qui décide si entre $x$ et $y$ il  passe (ou non) un bord de l'image, selon que $M(x,y)=1$ ou 0. Donc ils  posent
simplement $\nu(x,y)=M(x,y)(u(x)-u(y)).$
En d'autres termes, les faibles gradients (provoqués par les dégradés et les ombres) seraient supprimés. Seuls resteraient les forts gradients, correspondant aux contrastes de couleur entre les différents objets de la scène. La conséquence en serait que l'image ainsi reconstruite a pour ainsi dire éliminé les ombres. L'équation expliquerait donc la ``constance de couleur'' de notre perception en effet largement indépendante des ombres.

Une autre possibilité, somme toute inverse, sera de rehausser les faibles contrastes de l'image, de manière à voir mieux les textures et  les parties sombres. Pour cela on va au contraire favoriser les petits gradients par rapport aux grand, en leur appliquant une loi concave
$$\bv(x)=g(Du_0(x)),$$ où $g(\bv)=|\bv|^{-\alpha}\bv$, $0<\alpha<1$. La méthode peut être appliquée globalement, mais il est plus malin de l'appliquer localement en détourant une région de l'image sombre ou peu contrastée, et donc les  petits gradients sont ainsi rehaussés.

\dexer Proposer une méthode simple dans l'esprit précédent qui transforme l'image de manière que dans une sous-région les couleurs soient gardées, mais que le reste de l'image devienne gris. (Un pixel est gris quand ses trois composantes de couleur sont égales).
\fexer

La dernière application que nous allons considérer est la périodisation d'une image. Ce problème se pose notamment dans les éditeurs d'images des jeux électroniques, on l'on veut être capables de paver une surface avec un morceau de texture rectangulaire. Si on pave directement en reproduisant périodiquement le morceau de texture, on verra les bords des pavés. Pour atténuer cet effet, il faut que le morceau  $u_0$ soit rendu périodique. Pour cela, on résoud à nouveau l'équation de Poisson
\begin{equation}\label{deltaegaledelta}\Delta u=\Delta u_0,\end{equation} mais en forçant la solution $u$ à être périodique. Notons $R=[0,a]\times[0,b].$ On fixera donc  une condition de Dirichlet $u(x)=g(x)$ sur $\partial R$, où $g(x,0)=g(x,b)=(u_0(x,0)+u_0(x,b))/2$, et $g(0,y)=g(a,y)=(u_0(0,y)+u_0(a,y))/2$.  On pourra aussi  simplement chercher l'unique solution périodique de (\ref{deltaegaledelta}) dont la moyenne sur $R$ est égale à la moyenne de $u_0$ sur $R$. L'intérêt est que cette deuxième solution a une solution facile par Fourier. Toutefois, il faut bien préciser ce qu'on entend par $\Delta u_0$. En effet, on peut bien sûr considérer $u_0$ comme périodique, mais son laplacien au bord sera alors très singulier. Donc si on calcule $\Delta u_0$ par la méthode de Fourier, qui suppose implicitement l'image $u_0$ périodique, les valeurs de $\Delta u_0$ au bord seront aberrantes et de toutes façons résoudre (\ref{deltaegaledelta}) ne donnera rien de nouveau: on trouvera $u=u_0$.


\begin{figure}
\begin{center}
 \includegraphics[width=12cm]{Figures/Figure12PerezPavagePeriodique.eps}
\caption{}
\end{center}
\end{figure}
