Faster inpainting

[samverstocken]

Hi,

I was wondering whether there are developments to make the biharmonic inpainting algorithm any faster (e.g. with a Cython implementation) or more scalable for larger inpainting masks? On some astronomical images, I've seen it perform well for smaller masks but I had to abort the code once I was trying to remove somewhat larger sources from my images since it was running for more than an hour (on one single source) and I had to revert to an inferior inpainting method for that purpose. On the bright side, the biharmonic inpainting produces really good results for me.

Thanks,
Sam

[soupault]

Hi Sam!
Thank you very much for your interest and feedback!

Indeed, the implementation of biharmonic inpainting is quite far from optimal in the sense of performance. Current version is pretty straightforward due to the fact that it was written focusing nD-input support as the main target.

Possible improvements to the implementation include, but not limited to:

1. Pre-generating of bilaplacians (atm it is computed for each masked pixel separately);
2. Mask partitioning into independent connected regions (atm single huge matrix is built);
3. Cythonization (not sure if I'm able to write nD code in Cython atm);
4. Faster linsolve;
5. Parallel implementation.

As a intermediate solution, one can try to implement faster Cythonized version for 2D(+color) (taking into consideration also other points above), as it is expected to be the most common use case.

We're always happy to see PRs! If you are ready to face the challenge, don't hesitate to create one!

[stefanv]

Feel free to discuss further, but I'm closing this issue as it is not a bug report.

[soupault]

@samverstocken hi! Could you, please, elaborate on your use case: do you have many tiny regions to inpaint / several large regions / combination of two?

[samuelstjean]

I think you have summoned the wrong person by mistake, maybe @samverstocken is more knowledgeable about inpainting than me though.

[soupault]

@samuelstjean of course, of course, my sincere apologies about that (I've got brain-DDoSed). Always happy to see you here, though 😉.

[CMCDragonkai]

I'm running the algorithm on (4165, 4744) image with 338477 pixels masked as true, and it's taking more than 2 hrs and still hasn't finished. Although I noticed that there's been some performance improvements since 0.12.3?

[soupault]

@CMCDragonkai thanks for your input. Yes, I've made some trivial changes to speedup the algorithm on images with several separate inpainting domains (see #2234).
Occasionally, the changes from #2008 (comment) will be implemented, but unfortunately I don't have much time to work on them at the moment.

[grlee77]

I reopened this because I am working on a PR now that makes inpainting much faster (no changes to the algorithm itself, just a number of efficiency improvements).