Teasing

Tweet battle

Petite taquinade sur Twitter aujourd’hui avec Igor Carron, le rédacteur du blog Nuit Blanche. Igor¹ vantait les mérites d’un article intéressant à partir d’un des résultats présentés : une reconstruction d’image à partir d’une image ayant perdu (aléatoirement) 90% de ses pixels.

Mais.. attendez… ne serait-ce pas là un problème d’inpainting ? Si fait !

C’était donc l’occasion rêvée pour reparler du code de ce blog récemment arrivé sur Github. Surtout que d’après nos expériences l’algorithme de reconstruction se comportait encore relativement bien en supprimant 80-90% des pixels.

Money time

Donc, pour répondre à la requête d’Igor, here is the money :

L’image ci-dessus représente la fameuse Lena”), reconstruite à partir de 10% de ses pixels d’origine (choisis aléatoirement, c’est important).

Quelques remarques

• La fonctionnelle utilisée ici n’a rien de remarquable : il s’agit de la fameuse ROF, à savoir $\operatorname{argmin} \frac{1}{2}| Ax - y|_2^2 + \lambda |x|_\text{TV} $, où $A$ est le masque aléatoire. $y$ l’observation et TV la Variation Totale.
• L’implémentation est légèrement modifiée pour simuler un paramètre $\lambda$ infini là où le masque est non-nul, et 0 sinon.
• L’algorithme utilisé est dit primal-dual, c’est l’algorithme 1 de cet article⁰.
• J’avais écrit une démo qui utilisait le flux vidéo d’une webcam sur Mac, qui avait eu pas mal de succès lors des portes ouvertes de on labo (et pas juste auprès du grand public), et dont mon chef se sert régulièrement quand il veut impressionner quelqu’un. L’algorithme utilisé était cette fois FISTA (à découvrir ici) (Ref. 2), qui converge un peu plus vite, donc on mettait moins d’itérations.
• La démo avait été écrite à l’époque de Mac OS X 1.5 Leopard, avec OpenCV en version 1.0. Les changements apportés depuis à QuickTime et à OpenCV la rendent quasi-obsolète, donc je vous invite à la place à aller voir la version du code sur Github.

La morale de l’histoire

L’inpainting de pixels à partir d’un masque aléatoire n’est pas une tâche si difficile que ça, puisqu’un algorithme assez bête le résout de façon déjà intéressante.

Le vrai challenge est désormais dans la suppression de morceaux d’images plus structurés. Par exemple, dans Ref. 1, les auteurs enlèvent des lignes plutôt que des pixels, et on voit déjà de grosses différences entre la contrainte TV et les curvelets. Ceci n’enlève rien au mérite de l’article de départ, cité par Igor Carron, juste pour signifier qu’il faut bien choisir ses exemples d’illustration.

Références

Ref. 1 : A first-order primal-dual algorithm for convex problems with applications to imaging. Antonin Chambolle et Thomas Pock Journal of Mathematical Imaging and Vision, 2011, Volume 40, Number 1, Pages 120-145

Ref. 2 : A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems. Amir Beck and Marc Teboulle, SIAM J. Imaging Sci. 2, 183 (2009)

*[Rudin-Osher-Fatemi]