Mathematical Image Analysis Group, Saarland University

Inpainting-Based Image Compression

Motivation

The goal of image compression is to reduce redundancy of the image data in order to be able to store or transmit the image in an efficient form. Image compression methods that base on image inpainting constitute a relatively novel class of lossy image compression methods. Well-established image compression standards such as JPEG or JPEG 2000 rely on basis transforms and frequency quantisation. In contrast, inpainting-based approaches consider a few well-chosen data points of the spatial domain and reconstruct the image when decoding by means of interpolation. Inpainting strategies based on partial differential equations (PDEs) have so far been applied in most of the existing codecs. Recent work on texture compression [25] implies that also other inpainting methods like exemplar-based interpolation can be viable.

(a) Zoom (140 x 140 pixels) into test image Lena	(b) Two percent of all pixels, chosen randomly	(c) Linear diffusion
(d) Biharmonic Smoothing	(e) Nonlinear isotropic diffusion	(f) Edge enhancing diffusion (EED)

Above, you see a zoom (140 x 140 pixels) into the test image Lena (a). About 98 percent of all pixels have been removed (b). From this sparse information missing image content can be reconstructed by interpolation. The images (c)-(f) show different interpolation approaches. They clearly show that it is possible to approximate the original image from a few data points only. This motivates to exploit this idea for image compression.

Our Contributions

Framework for Interpolation of Scalar- and Tensor-Valued Images

Our PDE-based compression research is founded on interpolation of images. In [2] we present a unified framework for interpolation and regularisation of scalar- and tensor-valued images. It allows rotationally invariant models and can be used for scattered data interpolation and inpainting. There already, experiments have shown that the interpolation techniques based on nonlinear anisotropic diffusion should be favoured over interpolants with radial basis functions.

How to Choose Interpolation Data in Images

In [3] we provide our first, mainly experimental approach to determine good interpolation data for inpainting based on homogeneous diffusion. According to a significance measure, two greedy thinning algorithms are presented that remove image data up to a desired percentage.
Our approach in [6] is more of analytic nature. We introduce and discuss shape based models for finding the best interpolation data with respect to homogeneous diffusion. This is done by investigating a number of shape optimisation approaches, a level set approach and an approximation theoretic reasoning. All these approaches suggest for the continous setting to choose the interpolation data according to the modulus of the Laplacian.
In [15] we consider the discrete setting and investigate again heuristic methods to optimise the spatial data for homogeneous diffusion inpainting. We apply a probabilistic data sparsification, similar to the one presented in [3], followed by a nonlocal pixel exchange. Moreover, we present a method to determine the exact optimal tonal data for a given inpainting pixel mask. The combination of optimising spatial and tonal data allows almost perfect reconstructions with only 5% of all pixels. This demonstrates that a thorough data optimisation can compensate for most deficiencies of a suboptimal PDE interpolant, such as homogeneous diffusion inpainting. Recent advances in the determination of optimal data have also been published in [20], [24], and [31].
Ideas for the selection of interpolation points for homogeneous diffusion are transferred to interpolation with edge-enhancing anisotropic diffusion in [14]. Here, we consider probabilistic data sparsification with quadrixels as interpolation data instead of scattered independent points. In general, PDE-based image compression is very flexible and can work with many other features than just sparse pixel data. For instance, first experiments in [29] show that storing gradient data could also be useful for compression. However, these investigations also reveal that the cost of the features that are stored needs to be taken into account, since a gain in reconstruction quality can be negated by an increased cost. This important fact is discussed in more detail in [27] and [28]: We found that homogeneous inpainting is sensitive to suboptimal locations of known data that are cheaper to store. The quality of biharmonic inpainting suffers under coarse quantisation of the stored grey values, while edge-enhancing anisotropic diffusion inpainting is robust under both compression techniques. This shows that lossy compression steps need to be considered when selecting inpainting operators for compression. To this end, the effect of clustering-based quantisation techniques has been investigated in [34].

PDE-based Image Compression using Semantic Image Features

Corners are considered as salient image features. Corner detection algorithms have been thoroughly studied, are easy to implement and fast. This is the motivation for our investigation the usefulness of corners for PDE-based image compression in [4]. For image sparsification, we use the Förstner/Harris corner detector and store a small 4-neighbourhood around each detected corner point. This provides the interpolation data when decoding. However, since corners are a rather seldom image feature it is hard to obtain reasonable interpolation results.
Therefore we decided to investigate in edges instead of corners. In [10] we present a lossy compression method that exploits information at image edges: The edges of an image are detected and stored together with the grey/colour values at both sides of each edge. For decoding, missing data between the edges is interpolated by the simplest and computationally most favourable PDE-based inpainting approach, namley homogeneous diffusion. For cartoon-like images this approach is able to outperform JPEG and even JPEG2000 (see comparison of images below). Note that for such piecewise constant images this approach corresponds to the proposal of [6] to store pixels with large modulus of the Laplacian.
In [11] we prove existence and uniqueness and establish a maximum-minimum principle for the discrete reconstruction problem with homogeneous diffusion. Furthermore, we describe an efficient multigrid algorithm. The result is a simple codec that is able to encode and decode in real-time. A real-time demonstration for reconstruction from edge-information with homogeneous diffusion for the iPhone4 has been developed in [13].

(a) Test image Svalbard	(b) JPEG (approx. 1:100)
(c) JPEG2000 (approx. 1:100)	(d) PDE-based (approx. 1:100) (Mainberger and Weickert 2009 [10])

Homogeneous diffusion is also well-suited for depth map compression because this type of data is naturally composed of piecewise smooth image regions. To this end, we go beyond pure storage of edge data in [21] and partition the depth map into non-overlapping regions. By enforcing Neumann boundary conditions on the segment boundaries, the reconstruction can contain sharp edges without the need to store all pixel values left and right of the edges as in cartoon compression. Instead, known data is given on a regular, hexagonal grid which requires to store no positional data except for the grid size. Since carefully chosen known pixels can significantly increase the reconstruction quality of linear diffusion, we also choose and store additional free points with the stochastic approach from [15].

(a) Original Depth Map	(b) JPEG 180:1
(c) JPEG2000 180:1	(d) PDE-based 180:1 (Hoffmann [21])

PDE-based Image Compression using Tree Structures

In our research on PDE-based image compression we have identified edge-enhancing diffusion (EED), an anisotropic nonlinear diffusion filter with a diffusion tensor, to be one of the most favourable methods for scattered data interpolation (cf. [2]). In [1] we suggested to exploit this for image compression. We use an adaptive triangulation method based on B-tree coding for removing less significant pixels from the image. Due to the B-tree structure, the remaining points can be encoded in a compact and elegant way. When decoding, missing information is filled in by EED interpolation. This approach is further analysed and improved in [5]. For high compression rates it yields already far better results than the widely- used JPEG standard.
Our research [9] demonstrates that it is even possible to beat the quality of the much more advanced JPEG 2000 standard (see comparison of images below). This approach involves a number of advanced optimisations such as improved entropy coding, brightness rescaling, diffusivity optimisation, and interpolation swapping. Our work [19] not only explains all these steps in more detail, but also demonstrates possible extensions of this approach, e.g. for shape coding. Additionally, it sheds light on the favourable propoerties of EED for image compression.
Tree-based approaches are also particularly well-suited for the integration of common features for compression codecs due to the hierarchy that is provided by the subdivision tree. For instance, progressive modes [22,26] and region of interest coding [26] have been integrated efficiently.

(a) Test image Trui	(b) JPEG (1:54.5)
(c) JPEG2000 (1:57.2)	(d) PDE-based (1:57.6) (Schmaltz et. al 2009 [9])

Dedicated Compression of Multi-channel Images with PDEs

All of the aforementioned methods can be extedended in a straightforward way to colour images by simply compressing all three channels in the RGB colour space. However, in [23] and [32] we have shown that even better results can be achieved by respecting the fact that the human visual system values structurural information higher than colour.
To this end, we use a YCbCr colour space and dedicate a larger fraction of our overall bit budget to the image structure in the luma channel Y than to the chroma channels Cb and Cr. While this concept seems similar to chroma subsampling in JPEG and JPEG2000, it goes beyond a pure preference of brightness data: We guide the EED inpainting in the chroma channels by our accurate edges of the luma channel, thus reusing already encoded information to improve colour reconstruction. With this luma-preference (LP) extension of our tree-based methods, we can beat both JPEG and JPEG2000 on images with low and moderate amounts of texture.
For highly textured images, the LP mode helps to come closer to the performance of JPEG2000, but is not quite able to close the gap completely. First results in [25] indicate that hybrid codecs that combine PDE-based inpainting with patch-based interpolation could be a remedy for this issue. Patch-based approaches fill in missing image parts according to neighbourhood similarity and are therefore successful in reconstructing regular textures. With block-decomposition schemes that reconstruct cartoon-like image parts with EED inpainting and textured regions with patch-based interpolation can improve the reconstruction quality signifcantly on images with high amounts of texture.
While colour images are the most popular type of multi-channel images, spectral data can carry even more redundancies over a large number of channels. As shown in [33], PDE-based inpainting provides a significant potential for new codecs that are specifically tailored to spectral imaging applications.

(a) Test image Kodak15	(b) JPEG (120:1)
(c) JPEG2000 (120:1)	(d) PDE-based (120:1) (Peter et. al [32])

PDE-based Compression of Higher-Dimensional Data

PDE-based image-compression is also well-suited for data with more than two dimensions. In [12] we examine how well the edge-based approach [10] can be applied to cartoon-like image sequences. In particular, interpolation with homogeneous diffusion is combined with tree-based location coding or, alternatively, dithering approaches using the Laplacian magnitude as a density function (see [6]).
Moreover, we show in [17] and [19] that all the tree-based concepts of our most recent 2-D EED-based compression method from [9] are well-suited for 3-D volumetric data, in particular medical images.

(a) Original Brain CRT

(b) Interpolation points

PDE-based Video Compression

Tree-based methods using edge-enhancing diffusion (EED) can be successfully extended to spatiotemporal data. In [7] we combine the PDE-based image compression method based on triangulation and B-tree coding (see [1]) with optic flow methods to obtain a low bit rate video compression routine. Based on this combination of inpainting and optic flow for motion compensation, a sophisticated framework for video compression is proposed in [30]. For scenes with a static background, we have shown in [18] that PDE-based compression can be combined with object tracking to high quality videos at very low compression rates. Real-time video playback is even possible with the most sophisticated inpainting PDEs, namely EED, as demonstrated in [26].

(a) compressed frame of the movie Sintel (Andris et. al [30])

(b) corresponding subsampled flow-field for motion compensation (Andris et. al [30])
Each colour in the image represents a direction according to the corresponding colour on the frame.

Interpolation and Compression of Surfaces

PDEs can also be used for interpolation and approximation of triangulated surfaces and thus as well for compression of surfaces (see [8]). Analogously to homogeneous diffusion for images a geometric diffusion equation for surfaces can be deduced. As in our previous work, only a few relevant 3-D data points need then to be stored. When decoding, missing vertices are reconstructed by solving the geometric diffusion equation without any need of information on surface normals. A Hopscotch like approach improves the the results further.

(a) Original Max Planck

(b) Interpolation points

Steganography

Steganography is the art of hiding the presence of an embedded message (called secret) within a seemingly harmless message (called cover). It can be seen as the complement of cryptography, whose goal is to hide the content of a message. In [16] we demonstrate that one can adapt our diffusion-based image compression techniques such that they become ideally suited for steganographic applications. The resulting method, which we call Stenography with Diffusion Inpainting (SDI), even allows to embed large colour images into small grayscale images. Moreover, our approach is well-suited for uncensoring applications. A web demonstrator for hiding as well as one for censoring is available at http://stego.mia.uni-saarland.de.

Cover image

Stego image, i.e.
cover containing a secret.

Publications

I. Galić, J. Weickert, M. Welk, A. Bruhn, A. Belyaev, H.-P. Seidel:
Towards PDE-based image compression.
In N. Paragios, O. Faugeras, T. Chan, C. Schnörr (Eds.): Variational, Geometric, and Level Set Methods in Computer Vision. Lecture Notes in Computer Science, Vol. 3752, Springer, Berlin, 37-48, 2005.
J. Weickert, M. Welk:
Tensor field interpolation with PDEs.
In J. Weickert, H. Hagen (Eds.): Visualization and Processing of Tensor Fields, 315-325, Springer, Berlin, 2006.
Revised version of Technical Report No. 142, Department of Mathematics, Saarland University, Saarbrücken, Germany, 2005.
H. Dell:
Seed points in PDE-driven interpolation
Bachelor's Thesis, Dept. of Informatics and Mathematics, Saarland University, 2006.
H. Zimmer:
PDE-based image compression using corner information.
Master's Thesis, Dept. of Informatics and Mathematics, Saarland University, 2007.
I. Galić, J. Weickert, M. Welk, A. Bruhn, A. Belyaev, H.-P. Seidel:
Image compression with anisotropic diffusion.
Journal of Mathematical Imaging and Vision, Vol. 31, 255–269, 2008. Invited Paper.
Z. Belhachmi, D. Bucur, B. Burgeth, J. Weickert:
How to choose interpolation data in images.
SIAM Journal on Applied Mathematics, Vol. 70, No. 1, 333-352, 2009.
Revised version of Technical Report No. 205, Department of Mathematics, Saarland University, Saarbrücken, Germany, 2008.
Q. Gao:
Low bit rate video compression using inpainting PDEs and optic flow.
Master's Thesis, Dept. of Informatics and Mathematics, Saarland University, 2008.
E. Bae, J. Weickert:
Partial differential equations for interpolation and compression of surfaces.
In M. Daehlen, M. Floater, T. Lyche, J.-L. Merrien, K. Mørken, L. L. Schumaker (Eds.): Mathematical Methods for Curves and Surfaces. Lecture Notes in Computer Science, Vol. 5862, 1-14, Springer, Berlin, 2010.
C. Schmaltz, J. Weickert, and A. Bruhn:
Beating the quality of JPEG 2000 with anisotropic diffusion.
In J. Denzler, G. Notni, H.Süße (Eds.): Pattern Recognition. Lecture Notes in Computer Science, Vol. 5748, 452-461, Springer, Berlin, 2009
M. Mainberger and J. Weickert:
Edge-based image compression with homogeneous diffusion.
In X. Jiang, N. Petkov (Eds.): Computer Analysis of Images and Patterns. Lecture Notes in Computer Science, Vol. 5702, Springer, Berlin, 476-483, 2009.
M. Mainberger, A. Bruhn, J. Weickert, S. Forchhammer:
Edge-based compression of cartoon-like images with homogeneous diffusion.
Pattern Recognition, Vol. 44, No. 9, 1859-1873, September 2011.
Also available as Technical Report No. 269, Department of Mathematics, Saarland University, Saarbrücken, Germany, August 2010.
R. Lund:
3-D Data Compression with Homogeneous Diffusion.
M.Sc. thesis in Mathematics, Saarland University, Saarbrücken, Germany, 2011.
L. Keller:
PDE-Based Image Reconstruction on the iPhone 4.
B.Sc. thesis in Mathematics, Saarland University, Saarbrücken, Germany, 2011.
K. Baum:
Stützstellen Auswahl für diffusionsbasierte Bildkompression unter Berücksichtigung einer Quadrixel-Substruktur-Restriktion.
B.Sc. thesis in Mathematics, Saarland University, Saarbrücken, Germany, 2011.
M. Mainberger, S. Hoffmann, J. Weickert, C. H. Tang, D. Johannsen, F. Neumann, B. Doerr:
Optimising spatial and tonal data for homogeneous diffusion inpainting.
In A. M. Bruckstein, B. ter Haar Romeny, A. M. Bronstein, M. M. Bronstein (Eds.): Scale Space and Variational Methods in Computer Vision. Lecture Notes in Computer Science, Vol. 6667, Springer, Berlin, 26-37, 2012.
M. Mainberger, C. Schmaltz, M. Berg, J. Weickert, M. Backes:
Diffusion-based image compression in steganography.
In G. Bebis, R. Boyle, B. Parvin, D. Koracin, C. Fowlkes, S. Wang, M.-H. Choi, S. Mantler, J. Schulze, D. Acevedo, K. Mueller, M. Papka (Eds.): Advances in Visual Computing, Part II. Lecture Notes in Computer Science, Vol. 7432, 219-228, Springer, Berlin, 2012.
P. Peter:
Three-dimensional data compression with anisotropic diffusion.
In Proc. DAGM-OAGM 2012 Symposium for Pattern Recognition, Young Researchers Forum. Graz, Austria, August 28-31, 2012.
C. Schmaltz, J. Weickert:
Video compression with 3-D pose tracking, PDE-based image coding, and electrostatic halftoning.
In A. Pinz, T. Pock, H. Bischof, F. Leberl (Eds.): Pattern Recognition. Lecture Notes in Computer Science, Vol. 7476, 438-447, Springer, Berlin, 2012.
C. Schmaltz, P. Peter, M. Mainberger, F. Ebel, J. Weickert, A. Bruhn:
Understanding, optimising, and extending data compression with anisotropic diffusion.
International Journal of Computer Vision, in press.
Revised version of Technical Report No. 329, Department of Mathematics, Saarland University, Saarbrücken, Germany, March 2013.
L. Hoeltgen, S. Setzer, J. Weickert:
An optimal control approach to find sparse data for Laplace interpolation.
In A. Heyden, F. Kahl, C. Olsson, M. Oskarsson, X.-C. Tai (Eds.): Energy Minimization Methods in Computer Vision and Pattern Recognition. Lecture Notes in Computer Science, Vol. 8081, 151-164, Springer, Berlin, 2013.
S. Hoffmann, M. Mainberger, J. Weickert, M. Puhl:
Compression of depth maps with segment-based homogeneous diffusion.
In A. Kuijper, K. Bredies, T. Pock, H. Bischof (Eds.): Scale-Space and Variational Methods in Computer Vision. Lecture Notes in Computer Science, Vol. 7893, 319-330, Springer, Berlin, 2013.
C. Schmaltz, N. Mach, M. Mainberger, J. Weickert:
Progressive modes in PDE-based image compression.
Proc. 30th Picture Coding Symposium (PCS 2013, San Jose, CA, Dec. 2013, San Jose, CA), pp. 233-236, IEEE, Piscataway, 2013.
P. Peter, J. Weickert:
Colour image compression with anisotropic diffusion.
Proc. 21st IEEE International Conference on Image Processing (ICIP 2014, Paris, France, October 2014), 4822-4826, 2014.
L. Hoeltgen, J. Weickert:
Why does non-binary mask optimisation work for diffusion-based image compression?.
In X.-C. Tai, E. Bae, T. F. Chan, M. Lysaker (Eds.): Energy Minimization Methods in Computer Vision and Pattern Recognition. Lecture Notes in Computer Science, Springer, Vol. 8932, 85-98, Berlin, 2015.
P. Peter, J. Weickert:
Compressing images with diffusion- and exemplar-based inpainting.
In J.-F. Aujol, M. Nikolova, N. Papadakis (Eds.): Scale Space and Variational Methods in Computer Vision. Lecture Notes in Computer Science, Vol. 9087, 154-165, Springer, Berlin, 2015.
P. Peter, C. Schmaltz, N. Mach, M. Mainberger, J. Weickert:
Beyond pure quality: Progressive modes, region of interest coding, and real time video decoding for PDE-based image compression.
Journal of Visual Communication and Image Representation, Vol. 31, 253-265, August 2015.
Revised version of Technical Report No. 354, Department of Mathematics, Saarland University, Saarbrücken, Germany, January 2015.
P. Peter, S. Hoffmann, F. Nedwed, L. Hoeltgen, J. Weickert:
From optimised inpainting with linear PDEs towards competitive image compression codecs.
In T. Bräunl, B. McCane, M. Rivera, X. Yu (Eds.): Image and Video Technology. Lecture Notes in Computer Science, Vol. 9431, 63-74, Springer, Cham, 2016.
P. Peter, S. Hoffmann, F. Nedwed, L. Hoeltgen, J. Weickert:
Evaluating the true potential of diffusion-based inpainting in a compression context.
Signal Processing: Image Communication, Vol. 46, 40-53, August 2016.
Revised version of Technical Report No. 373, Department of Mathematics, Saarland University, Saarbrücken, Germany, January 2016.
M. Schneider, P. Peter, S. Hoffmann, J. Weickert, Enric Meinhardt-Llopis:
Gradients versus grey values for sparse image reconstruction and inpainting-based compression.
In J. Blanc-Talon, C. Distante, W. Philips, D. Popescu, P. Scheunders (Eds.): Advanced Concepts for Intelligent Vision Systems. Lecture Notes in Computer Science, Vol. 10016, 1-13, Springer, Cham, 2016.
S. Andris, P. Peter, J. Weickert:
A proof-of-concept framework for PDE-based video compression.
Proc. 32nd Picture Coding Symposium, Nuremberg, Germany, December 2016.
PCS 2016 Best Poster Award.
L. Hoeltgen, M. Mainberger, S. Hoffmann, J. Weickert, C. H. Tang, S. Setzer, D. Johannsen, F. Neumann, B. Doerr:
Optimising spatial and tonal data for PDE-based inpainting.
In M. Bergounioux, G. Peyré, C. Schnörr, J.-P. Caillau, T. Haberkorn (Eds.): Variational Methods in Imaging and Geometric Control. Pages 35-83, De Gruyter, Berlin, 2017.
Also available as arXiv:1506.04566 [cs.CV], June 2015.

P. Peter, L. Kaufhold, J. Weickert:
Turning Diffusion-based Image Colorization into Efficient Color Compression.
IEEE Transactions on Image Processing, Vol. 26, No. 2, 860-869, February 2017.
Revised version of Technical Report No. 370, Department of Mathematics, Saarland University, Saarbrücken, Germany, December 2015.
N. Amrani, J. Serra-Sagrista, P. Peter, J. Weickert:
Diffusion-based inpainting for coding remote-sensing data.
IEEE Geoscience and Remote Sensing Letters, Vol. 14, No. 8, 1203-1207, August 2017.
Also available as Technical Report, Universitat Autonoma de Barcelona, Spain, March 2017, http://ddd.uab.cat/record/174184.
L. Hoeltgen, P. Peter, M. Breuß:
Clustering-based quantisation for PDE-based image compression.
Signal, Image and Video Processing, Vol. 12, No. 3, 411-419, Vol. 12, No. 3, 411-419 March 2018.
Revised version of arXiv:1706.06347 [cs.CV], June 2017.