Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Compression

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 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.

This content is ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
  • IEEE-SPS display tagshide tags

    This module is included inLens: IEEE Signal Processing Society Lens
    By: IEEE Signal Processing SocietyAs a part of collection: "Concise Signal Models"

    Comments:

    "A resource on sparse, compressible, and manifold signal models for signals processing and compressed sensing."

    Click the "IEEE-SPS" link to see all content they endorse.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This module is included inLens: UniqU's lens
    By: UniqU, LLCAs a part of collection: "Concise Signal Models"

    Click the "UniqU content" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Compression

Module by: Michael Wakin. E-mail the author

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.

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^Lpf-fR^Lp as RR. The metric entropy [9] for a class FF gives the best decay rate that can be achieved uniformly over all functions fFfF. 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 (H2H2 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

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

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

| A lens I own (?)

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 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