Abstract
Digital image inpainting refers to techniques used to reconstruct a damaged or incomplete image by exploiting available image information. The main goal of this work is to perform the image inpainting process from a set of sparsely distributed image samples with the Smoothed Particle Hydrodynamics (SPH) technique. As, in its naive formulation, the SPH technique is not even capable of reproducing constant functions, we modify the approach to obtain an approximation which can reproduce constant and linear functions. Furthermore, we examine the use of Voronoi tessellation for defining the necessary parameters in the SPH method as well as selecting optimally located image samples. In addition to this spatial optimization, optimization of data values is also implemented in order to further improve the results. Apart from a traditional Gaussian smoothing kernel, we assess the performance of other kernels on both random and spatially optimized masks. Since the use of isotropic smoothing kernels is not optimal in the presence of objects with a clear preferred orientation in the image, we also examine anisotropic smoothing kernels. Our final algorithm can compete with well-performing sparse inpainting techniques based on homogeneous or anisotropic diffusion processes as well as with exemplar-based approaches.
Introduction
Image inpainting is the process of reconstructing missing or damaged regions of an image. A particularly challenging variant is sparse inpainting, where the goal is to rebuild an entire image from a very small fraction (e.g., 5%) of its original pixels. This has significant implications for image compression, as storing only a few "important" pixels can lead to massive space savings if the reconstruction is accurate.
While traditional methods rely on Partial Differential Equations (PDEs) or exemplar-based patch copying, this research explores Smoothed Particle Hydrodynamics (SPH). Originally a meshless Lagrangian method used in astrophysics and fluid simulations, SPH is naturally suited for handling irregular data distributions. However, its "naive" formulation is mathematically inconsistent for image data, failing to correctly reproduce even a flat, constant color. This paper introduces several innovations to adapt SPH into a robust tool for image reconstruction.
The SPH Framework for Images
The core of SPH is the approximation of a function at any point by summing the contributions of nearby "particles" (pixels), weighted by a smoothing kernel.
To make SPH viable for image processing, the following methodological improvements were implemented:
- Restoring Consistency: The authors implement Shepard interpolation to achieve "zero-order consistency," ensuring the ability to reproduce constant functions. They further extend this by solving a $3 \times 3$ linear system at each pixel to achieve "first-order consistency," allowing for the accurate representation of linear gradients.
- Voronoi-Based Parameters: Instead of a fixed grid, Voronoi tessellation is used to define the "area of influence" ($V_j$) for each pixel. This allows the method to adapt dynamically to irregular pixel distributions.
- Mixed Order Consistency: To prevent "overshooting" artifacts common in first-order methods on random masks, a Mixed Consistency Algorithm is used. It computes both zero- and first-order results and selects the one with the lower reconstruction error.
- Anisotropic Kernels: To better preserve sharp boundaries, smoothing kernels are allowed to "stretch" along edges rather than remaining isotropic (circular), aligning with the image's structural orientation.
Optimization Strategies
The quality of sparse inpainting depends heavily on the selection and values of the sample points. The authors employ two main optimization strategies:
- Spatial Optimization: A "densification" strategy that iteratively adds mask points to regions exhibiting the highest reconstruction error.
- Tonal Optimization: A least-squares approach using the CGNR method to fine-tune the color values of the sparse pixels, minimizing global reconstruction error.
Experimental Results
The SPH-based approach was evaluated against standard benchmarks (e.g., "trui", "peppers", "baboon") and compared to state-of-the-art PDE methods.
- Performance vs. PDEs: On the "trui" image with 5% optimized data, the Mixed SPH method achieved a Mean Square Error (MSE) of 9.95, significantly outperforming Harmonic Inpainting (17.17) and Biharmonic Inpainting (15.00).
- Texture Handling: For the "baboon" image, which is rich in texture, SPH reduced the error of traditional diffusion methods by over 34%.
- Qualitative Quality: Compared to exemplar-based methods like Criminisi’s algorithm, SPH produced smoother reconstructions in gradient areas (like skin or sky) with fewer patchy artifacts.
Conclusion
By adapting SPH with consistency corrections and Voronoi-based optimization, this work demonstrates a powerful alternative to traditional inpainting methods. While SPH excels at sparse data reconstruction, future work will focus on improving anisotropy calculations and reducing the storage overhead required for compression tasks. Currently, SPH is most effective for sparse reconstruction rather than "dense" tasks like large object removal, where specialized diffusion methods still hold an advantage.
Summary updated