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 partial differential equations (PDEs) 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, PDE-based approaches consider a few well-chosen data points of the spatial domain and reconstruct the image when decoding by means of PDE-based interpolation.

(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. Inwe 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

Inwe 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 inis 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.

Inwe 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, 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 inand.

Ideas for the selection of interpolation points for homogeneous diffusion are transferred to interpolation with edge-enhancing anisotropic diffusion in. Here, we consider probabilistic data sparsification with quadrixels as interpolation data instead of scattered independent points.

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. 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. Inwe 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 ofto store pixels with large modulus of the Laplacian.

Inwe 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.

(a) Test image Svalbard |
(b) JPEG (approx. 1:100) |

(c) JPEG2000 (approx. 1:100) | (d) PDE-based (approx. 1:100) (Mainberger and Weickert 2009) |

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.). Inwe 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. For high compression rates it yields already far better results than the widely- used JPEG standard.

Our researchdemonstrates that it is even possible to beat the quality of the much more advanced JPEG 2000 standard (see comparison of images below). This latest approach involves a number of advanced optimisations such as improved entropy coding, brightness rescaling, diffusivity optimisation, and interpolation swapping.

Our latest worknot 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.

(a) Test image Trui |
(b) JPEG (1:54.5) |

(c) JPEG2000 (1:57.2) | (d) PDE-based (1:57.6) (Schmaltz et. al 2009) |

PDE-based Compression of Higher-Dimensional Data

PDE-based image-compression is also well-suited for data with more than two dimensions. Inwe examine how well the edge-based approachcan 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).

Tree-based methods using edge-enhancing diffusion (EED) can be successfully extended to both 3-D spatial and spatiotemporal data. Inwe combine the PDE-based image compression method based on triangulation and B-tree coding (see) withoptic flow methods to obtain a low bit rate video compression routine. Inandwe show that all the concepts for optimisation of our most recent 2-D EED-based compression method fromare well-suited for 3-D volumetric data, in particular medical images.

(a) Original Brain CRT |
(b) Interpolation points | (c) Reconstruction 100:1 (Peter) |

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). 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 | (c) Reconstruction (Bae and Weickert) |

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. Inwe 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**.

To appear in A. Pinz, T. Pock, H. Bischof, F. Leberl (Eds.): Pattern Recognition. Lecture Notes in Computer Science, 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. - 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.