Les choses compliquées sérieuses commencent.

Après avoir vu grosso modo quel était le problème, on va tenter de le formaliser mathématiquement. Attention : les équations s’affichent correctement grâce à MathJax. Si ce n’est pas le cas, soit j’ai raté l’intégration avec ce blog, soit vous avez désactivé Javascript.

Définition plus formelle

Mathématiquement, on va supposer qu’on dispose d’une image $u$ définie sur $\Omega \subset R^2$. Les valeurs de $u$ (niveau de gris, couleur…) sont supposées inconnues sur un sous-domaine $I \subset \Omega$ quelconque (avec des trous, non convexe, en plusieurs partie disjointes…) et parfaitement connues ailleurs. Tout ceci est résumé sur le schéma suivant :

Et comment on remplit les trous ?

Schématiquement, deux grandes familles d’algorithmes cohabitent :

• les approches faisant diffuser à l’intérieur des trous l’information disponible autour (couleurs, contours…) (approches variationnelles, parce qu’on cherche plus ou moins explicitement une fonction solution) ;
• les approches où l’on va remplir les trous avec des par un patchwork d’éléments pris çà et là dans l’image (approches basées sur les exemples, car on vient copier-coller des bouts d’images connus).

Bien sûr, le monde n’étant pas binaire, il existe des méthodes hybrides empruntant un peu aux deux familles…

Pour décrire en gros la différence entre ces deux approches, on peut dire que la diffusion s’apparente à barbouiller avec son doigt mouillé la peinture des bords du trou pour aller le remplir et le camoufler, alors que les méthodes d’exemples consisteraient à photocopier l’image, la découper en petits morceaux, et remplir le trou avec ces morceaux découpés.

Avantages et inconvénients

On peut faire remonter la célébrité de l’inpainting (même si c’était déjà un problème étudié avant !) à un article intitulé… Image inpainting¹, qui emploie une méthode variationnelle (diffusion). Ces approches ont logiquement été favorisées dans un premier temps. Toutefois, elles ont du mal à prendre en compte la texture et les bords des objets, et conduisent fréquemment é des résultats flous.

C’est alors que les approches par exemples ont fait un retour remarqué² avec cette publication: Criminisi, A., Perez, P., & Toyama, K. (2003). Object removal by exemplar-based inpainting. Computer Vision and Pattern Recognition, 2003. L’avantage de cette méthode est d’être très simple à implémenter, pour des résultats impressionnants de qualité. Par contre, l’ordre de remplissage des pixels est à choisir soigneusement pour éviter les artefacts (voir l’article).

Et nous ?

On va quand même parler dans les billets suivant de méthodes variationnelles, parce qu’il y a 2 ou 3 choses intéressantes et rigolotes à en dire.

Lectures conseillées

A tout seigneur, tout honneur. Guillermo et Sapiro ont chacun une page web dédiée à l’inpainting qu’il est bien sûr intéressant de visiter : ici pour Guillermo Sapiro et là pour Marcelo Bertalmio.

Comme on va causer de méthodes variationnelles, une petite visite à la page dédiée à UCLA sera utile pour ceux qui veulent aller plus loin et voir des choses compliquées. Et parce qu’il n’y a pas que les méthodes variationnelles, un tour sur la page d’Antonio Criminisi dédiée aux approches “patches” (exemples) s’impose !