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. Wellestablished image compression
standards such as JPEG or JPEG 2000 rely on basis transforms and
frequency quantisation. In contrast, inpaintingbased approaches consider a
few wellchosen 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
exemplarbased 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 TensorValued Images
Our PDEbased compression research is founded on interpolation of
images. In [2] we present a unified framework for
interpolation and regularisation of scalar and tensorvalued
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 edgeenhancing anisotropic diffusion
in [14]. Here, we consider probabilistic data
sparsification with quadrixels as interpolation data instead of
scattered independent points. In general, PDEbased 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 edgeenhancing 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 clusteringbased quantisation techniques has
been investigated in [34].
PDEbased 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 PDEbased image compression in
[4]. For image sparsification, we use the
Förstner/Harris corner detector and store a small 4neighbourhood
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
PDEbased inpainting approach, namley homogeneous diffusion. For
cartoonlike 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 maximumminimum 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 realtime. A realtime
demonstration for reconstruction from edgeinformation 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) PDEbased (approx. 1:100)
(Mainberger and Weickert 2009 [10]) 
Homogeneous diffusion is also wellsuited 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 nonoverlapping
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) PDEbased 180:1 (Hoffmann [21]) 
PDEbased Image Compression using Tree Structures
In our research on PDEbased image compression we have identified
edgeenhancing 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 Btree
coding for removing less significant pixels from the image. Due to the
Btree 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.
Treebased approaches are also particularly wellsuited 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) PDEbased (1:57.6)
(Schmaltz et. al 2009 [9]) 
Dedicated Compression of Multichannel 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 lumapreference (LP) extension of our treebased 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 PDEbased inpainting with patchbased interpolation could
be a remedy for this issue. Patchbased approaches fill in missing image
parts according to neighbourhood similarity and are therefore successful
in reconstructing regular textures. With blockdecomposition schemes that
reconstruct cartoonlike image parts with EED inpainting and textured regions
with patchbased interpolation can improve the reconstruction quality signifcantly
on images with high amounts of texture.
While colour images are the most popular type of multichannel images,
spectral data can carry even more redundancies over a large number
of channels. As shown in [33], PDEbased 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) PDEbased (120:1)
(Peter et. al [32]) 
PDEbased Compression of HigherDimensional Data
PDEbased imagecompression is also wellsuited for data with more
than two dimensions. In [12] we examine how well
the edgebased approach [10] can be applied to
cartoonlike image sequences. In particular, interpolation with
homogeneous diffusion is combined with treebased 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 treebased concepts of our most recent 2D
EEDbased compression method from [9] are
wellsuited for 3D volumetric data, in particular medical images.
(a) Original Brain CRT 
(b) Interpolation points 
(c) Reconstruction 100:1 (Peter [17]) 
PDEbased Video Compression
Treebased methods using edgeenhancing diffusion (EED) can be
successfully extended to spatiotemporal
data. In [7] we combine the PDEbased image
compression method based on triangulation and Btree 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 PDEbased compression can be combined with object tracking
to high quality videos at very low compression rates.
Realtime 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 flowfield 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 3D 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 
(c) Reconstruction (Bae and Weickert [8]) 
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 diffusionbased 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 wellsuited for uncensoring applications. A web
demonstrator for hiding as well as one for censoring is available
at
http://stego.mia.unisaarland.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 PDEbased 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, 3748, 2005.

J. Weickert, M. Welk:
Tensor field interpolation with PDEs.
In J. Weickert, H. Hagen (Eds.):
Visualization and Processing of Tensor Fields, 315325,
Springer, Berlin, 2006.
Revised version of
Technical Report No. 142, Department of Mathematics,
Saarland University, Saarbrücken, Germany, 2005.

H. Dell:
Seed points in PDEdriven interpolation
Bachelor's Thesis, Dept. of Informatics and Mathematics, Saarland University,
2006.

H. Zimmer:
PDEbased 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, 333352, 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, 114, 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, 452461,
Springer, Berlin, 2009

M. Mainberger and J. Weickert:
Edgebased 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, 476483, 2009.

M. Mainberger, A. Bruhn, J. Weickert, S. Forchhammer:
Edgebased compression of cartoonlike images with homogeneous
diffusion.
Pattern Recognition, Vol. 44, No. 9, 18591873, September 2011.
Also available as
Technical Report No. 269, Department of Mathematics,
Saarland University, Saarbrücken, Germany, August 2010.

R. Lund:
3D Data Compression with Homogeneous Diffusion.
M.Sc. thesis in Mathematics, Saarland University,
Saarbrücken, Germany, 2011.

L. Keller:
PDEBased 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 QuadrixelSubstrukturRestriktion.
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, 2637,
2012.

M. Mainberger, C. Schmaltz, M. Berg, J. Weickert, M. Backes:
Diffusionbased 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, 219228, Springer, Berlin, 2012.

P. Peter:
Threedimensional data compression with anisotropic diffusion.
In Proc. DAGMOAGM 2012 Symposium for Pattern Recognition,
Young Researchers Forum. Graz, Austria, August 2831, 2012.

C. Schmaltz, J. Weickert:
Video compression with 3D pose tracking, PDEbased image coding,
and electrostatic halftoning.
In A. Pinz, T. Pock, H. Bischof, F. Leberl (Eds.):
Pattern Recognition.
Lecture Notes in Computer Science, Vol. 7476, 438447, 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, 151164, Springer, Berlin,
2013.

S. Hoffmann, M. Mainberger, J. Weickert, M. Puhl:
Compression of depth maps with segmentbased homogeneous diffusion.
In A. Kuijper, K. Bredies, T. Pock, H. Bischof (Eds.):
ScaleSpace and Variational Methods in Computer Vision.
Lecture Notes in Computer Science, Vol. 7893, 319330, Springer, Berlin,
2013.

C. Schmaltz, N. Mach, M. Mainberger, J. Weickert:
Progressive modes in PDEbased image compression.
Proc. 30th Picture Coding Symposium (PCS 2013, San Jose, CA, Dec. 2013,
San Jose, CA), pp. 233236, 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), 48224826, 2014.

L. Hoeltgen, J. Weickert:
Why does nonbinary mask optimisation work for diffusionbased
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, 8598, Berlin,
2015.

P. Peter, J. Weickert:
Compressing images with diffusion and exemplarbased 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, 154165, 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 PDEbased image compression.
Journal of Visual Communication and Image Representation, Vol. 31,
253265, 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, 6374,
Springer, Cham, 2016.

P. Peter, S. Hoffmann, F. Nedwed, L. Hoeltgen, J. Weickert:
Evaluating the true potential of diffusionbased inpainting in
a compression context.
Signal Processing: Image Communication, Vol. 46, 4053, 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 MeinhardtLlopis:
Gradients versus grey values for sparse image reconstruction and
inpaintingbased compression.
In J. BlancTalon, C. Distante, W. Philips, D. Popescu, P. Scheunders (Eds.):
Advanced Concepts for Intelligent Vision Systems.
Lecture Notes in Computer Science, Vol. 10016, 113, Springer, Cham,
2016.

S. Andris, P. Peter, J. Weickert:
A proofofconcept framework for PDEbased 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 PDEbased inpainting.
In M. Bergounioux, G. Peyré, C. Schnörr,
J.P. Caillau, T. Haberkorn (Eds.):
Variational Methods in Imaging and Geometric Control.
Pages 3583, De Gruyter, Berlin, 2017.
Also available as
arXiv:1506.04566 [cs.CV], June 2015.
 P. Peter, L. Kaufhold, J. Weickert:
Turning Diffusionbased Image Colorization into Efficient Color Compression.
IEEE Transactions on Image Processing, Vol. 26, No. 2, 860869, February
2017.
Revised version of
Technical Report No. 370, Department of Mathematics,
Saarland University, Saarbrücken, Germany, December 2015.

N. Amrani, J. SerraSagrista, P. Peter, J. Weickert:
Diffusionbased inpainting for coding remotesensing data.
IEEE Geoscience and Remote Sensing Letters, Vol. 14, No. 8, 12031207,
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ß:
Clusteringbased quantisation for PDEbased image compression.
Signal, Image and Video Processing, Vol. 12, No. 3, 411419, Vol. 12,
No. 3, 411419 March 2018.
Revised version of
arXiv:1706.06347 [cs.CV], June 2017.
