PDE-Based Image Compression

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.

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 [12] 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 demonstartes that a thorough data optimisation can compensate for most deficiencies of a suboptimal PDE interpolant, such as homogeneous diffusion inpainting.

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 motivated us to investigate the usefulness of corners for PDE-based image compression in [4]. For image sparsification, we used the Förstner/Harris corner detector and stored 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.
So 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. When 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 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) Test image Svalbard	(b) JPEG (approx. 1:100)
(c) JPEG2000 (approx. 1:100)	(d) PDE-based (approx. 1:100) (Mainberger and Weickert 2009 [10])

PDE-based Image Compression using Tree Structures

In our research on PDE-based image compression we 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 used 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 was further analysed and improved in [5]. For high compression rates it gives already far better results than the widely- used JPEG standard.
In [7] we combined this PDE-based image compression method with optic flow methods to obtain a low bit rate video compression routine.
Our latest 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 latest approach involves a number of advanced optimisations, such as improved entropy coding, brightness rescaling, diffusivity optimisation, and interpolation swapping.

(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])

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

(c) Reconstruction (Bae and Weickert [8])

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


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


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


4. H. Zimmer:
   PDE-based image compression using corner information.
   Master's Thesis, Dept. of Informatics and Mathematics, Saarland University, 2007.


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


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


7. Q. Gao:
   Low bit rate video compression using inpainting PDEs and optic flow.
   Master's Thesis, Dept. of Informatics and Mathematics, Saarland University, 2008.


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


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


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


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


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

MIA Group
©2001-2012
The author is not
responsible for
the content of
external pages.