Inpainting using perfect patch graph


  • Validate our idea before trying to retrieve the graph


  1. Create patch graph from the original image
  2. Mask image
  3. Diffusion on patch graph (TV or Thikonov prior)

Large surface inpainting

  • Observed image error (L2-norm) : 6512
  • Reconstruction error : TV 250, Thikonov 246

Small surfaces inpainting

  • Observed image error (L2-norm) : 9584
  • Reconstruction error : TV 321, Thikonov 312



  • TV and Thikonov priors work equally well for large or small holes
  • Thikonov is however much faster (3s for 88 iterations vs 22s for 200 iterations for large hole)


The Graph Signal Processing toolbox is a matlab toolbox that performs a wide variety of filtering on graphs. It can create all sorts of filterbanks including wavelets and Gabor. It is based on spectral graph theory and can scale to very large graphs thanks to the use of Chebysheff polynomial approximations. The toolbox is developed by LTS2 under the GPLv3.

I’ll use (and maybe even develop) this toolbox as part of my attempt to perform image inpainting using graphs (the GIIN semester project).