Skip to content Skip to navigation

Connexions

You are here: Home » Content » Compression

Navigation

Recently Viewed

This feature requires Javascript to be enabled.

Compression

Module by: Michael Wakin. E-mail the author

User rating (How does the rating system work?)
Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

:
(0 ratings)

Summary: This collection reviews fundamental concepts underlying the use of concise models for signal processing. Topics are presented from a geometric perspective and include low-dimensional linear, sparse, and manifold-based signal models, approximation, compression, dimensionality reduction, and Compressed Sensing.

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

Transform coding

In Nonlinear Approximation from Approximation, we measured the quality of a dictionary in terms of its KK-term approximations to signals drawn from some class. One reason that such approximations are desirable is that they provide concise descriptions of the signal that can be easily stored, processed, etc. There is even speculation and evidence that neurons in the human visual system may use sparse coding to represent a scene [13].

For data compression, conciseness is often exploited in a popular technique known as transform coding. Given a signal ff (for which a concise description may not be readily apparent in its native domain), the idea is simply to use the dictionary ΨΨ to transform ff to its coefficients αα, which can then be efficiently and easily described. As discussed above, perhaps the simplest strategy for summarizing a sparse αα is simply to threshold, keeping the KK largest coefficients and discarding the rest. A simple encoder would then just encode the positions and quantized values of these KK coefficients.

Metric entropy

Suppose ff is a function and let fR^fR^ be an approximation to ff encoded using RR bits. To evaluate the quality of a coding strategy, it is common to consider the asymptotic rate-distortion (R-D) performance, which measures the decay rate of ∥f-fR^∥Lp∥f-fR^∥Lp as R→∞R→∞. The metric entropy [9] for a class FF gives the best decay rate that can be achieved uniformly over all functions f∈Ff∈F. We note that this is a true measure for the complexity of a class and is tied to no particular dictionary or encoding strategy. The metric entropy also has a very geometric interpretation, as it relates to the smallest radius possible for a covering of 2R2R balls over the set FF.

Metric entropies are known for certain signal classes. For example, the results of Clements [7] (extending those of Kolmogorov and Tihomirov [9]) regarding metric entropy give bounds on the optimal achievable asymptotic rate-distortion performance for DD-dimensional CHCH-smooth functions ff (see also [5]):

f - f R ^ L p ≲ 1 R H D . f - f R ^ L p ≲ 1 R H D . (1)
Rate-distortion performance measures the complexity of a representation and encoding strategy. In the case of transform coding, for example, R-D results account for the bits required to encode both the values of the significant coefficients and their locations. Nonetheless, in many cases transform coding is indeed an effective strategy for encoding signals that have sparse representations [6]. For example, in [5] Cohen et al. propose a wavelet-domain coder that uses a connected-tree structure to efficiently encode the positions of the significant coefficients and prove that this encoding strategy achieves the optimal rate
f - f R ^ L p ≲ 1 R H D . f - f R ^ L p ≲ 1 R H D . (2)

Compression of piecewise smooth images

In some cases, however, the sparsity of the wavelet transform may not reflect the true underlying structure of a signal. Examples are 2-D piecewise smooth signals with a smooth edge discontinuity separating the smooth regions. As we discussed in Nonlinear Approximation from Approximation, wavelets fail to sparsely represent these functions, and so the R-D performance for simple thresholding-based coders will suffer as well. In spite of all of the benefits of wavelet representations for signal processing (low computational complexity, tree structure, sparse approximations for smooth signals), this failure to efficiently represent edges is a significant drawback. In many images, edges carry some of the most prominent and important information [12], and so it is desirable to have a representation well-suited to compressing edges in images.

To address this concern, recent work in harmonic analysis has focused on developing representations that provide sparse decompositions for certain geometric image classes. Examples include curvelets [4], [3] and contourlets [8], slightly redundant tight frames consisting of anisotropic, “needle-like” atoms. In [11], bandelets are formed by warping an orthonormal wavelet basis to conform to the geometrical structure in the image. A nonlinear multiscale transform that adapts to discontinuities (and can represent a “clean” edge using very few coarse scale coefficients) is proposed in [2]. Each of these new representations has been shown to achieve near-optimal asymptotic approximation and R-D performance for piecewise smooth images consisting of CHCH regions separated by discontinuities along CHCH curves, with H=2H=2 (H≥2H≥2 for bandelets). Some have also found use in specialized compression applications such as identification photos [10].

In [1], we have presented a scheme that is based on the simple yet powerful observation that geometric features can be efficiently approximated using local, geometric atoms in the spatial domain, and that the projection of these geometric primitives onto wavelet subspaces can therefore approximate the corresponding wavelet coefficients. We prove that the resulting dictionary achieves the optimal nonlinear approximation rates for piecewise smooth signal classes. To account for the added complexity of this encoding strategy, we also consider R-D results and prove that this scheme comes within a logarithmic factor of the optimal performance rate. Unlike the techniques mentioned above, our method also generalizes to arbitrary orders of smoothness and arbitrary signal dimension.

References

  1. V. Chandrasekaran and M. B. Wakin and D. Baron and R. Baraniuk. Representation and Compression of Multi-Dimensional Piecewise Functions Using Surflets. [to appear in {\em IEEE Trans. Inf. Theory}, 2008].
  2. Arandiga, F. and Cohen, A. and Doblas, M. and Donat, R. and Matei, B. (2003, Sept.). Sparse representations of images by edge adapted nonlinear multiscale transforms. In Proc. IEEE Int. Conf. Image Proc. (ICIP). Barcelona, Spain
  3. Candès, E. and Donoho, D. L. (2004). New tight frames of curvelets and optimal representations of objects with piecewise singularities. Comm. on Pure and Applied Math., 57, 219-266.
  4. Candès, E. J. and Donoho, D. L. (1999). Curvelets — A suprisingly effective nonadaptive representation for objects with edges. In Cohen, A. and Rabut, C. and Schumaker, L. L. (Eds.), Curve and Surface Fitting. Vanderbilt University Press.
  5. Cohen, A. and Dahmen, W. and Daubechies, I. and DeVore, R. (2001). Tree Approximation and Optimal Encoding. Appl. Comput. Harmon. Anal., 11, 192-226.
  6. Cohen, A. and Daubechies, I. and Guleryuz, O. G. and Orchard, M. T. (2002, July). On the importance of combining wavelet-based nonlinear approximation with coding strategies. IEEE Trans. Inform. Theory, 48(7), 1895-1921.
  7. Clements, G. F. (1963). Entropies of Several Sets of Real Valued Functions. Pacific J. Math., 13, 1085-1095.
  8. Do, M. N. and Vetterli, M. (2005). The contourlet transform: An efficient directional multiresolution image representation. [To appear]. IEEE Trans. Image Processing.
  9. Kolmogorov, A. N. and Tihomirov, V. M. (1961). -entropy and -capacity of sets in functional spaces. Amer. Math. Soc. Transl. (Ser. 2), 17, 277-364.
  10. Let it Wave. [www.letitwave.fr].
  11. Le Pennec, E. and Mallat, S. (2005, April). Sparse Geometric Image Representations with Bandelets. IEEE Trans. Image Processing, 14(4), 423-438.
  12. Marr, D. (1982). Vision. San Francisco: W. H. Freeman and Company.
  13. Olshausen, B. and Field, D. (1997). Sparse coding with an overcomplete basis set: A strategy employed by V1? Vision Res., 37, 311-3325.

Content actions

Give Feedback:

E-mail the module author | Rate module ( How does the rating system work?)

Rating system

Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

(0 ratings)

Download:

Module PDF

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.

| A lens (?)

Definition of a lens

Lenses

A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual Connexions member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks