  In recent years inpainting-based compression methods have been shown to be a
viable alternative to classical codecs such as JPEG and JPEG2000. Unlike
transform-based codecs, which store coefficients in the transform domain,
inpainting-based approaches store a small subset of the original image pixels
and reconstruct the image from those by using a suitable inpainting operator. A
good candidate for such an inpainting operator is homogeneous diffusion
inpainting, as it is simple, theoretically well-motivated, and can achieve good
reconstruction quality for optimized data. However, a major challenge has been
to design fast solvers for homogeneous diffusion inpainting that scale to 4K
image resolution ($3840 \times 2160$ pixels) and are real-time capable. We
overcome this with a careful adaptation and fusion of two of the most efficient
concept from numerical analysis: multigrid and domain decomposition. Our domain
decomposition algorithm efficiently utilizes GPU parallelism by solving
inpainting problems on small overlapping blocks. Unlike simple block
decomposition strategies such as the ones in JPEG, our approach yields block
artifact-free reconstructions. Furthermore, embedding domain decomposition in a
full multigrid scheme provides global interactions and allows us to achieve
optimal convergence by reducing both low- and high-frequency errors at the same
rate. We are able to achieve 4K color image reconstruction at more than $60$
frames per second even from very sparse data - something which has been
previously unfeasible.
