A Caltech Library Service

Representation and Compression of Multidimensional Piecewise Functions Using Surflets

Chandrasekaran, Venkat and Wakin, Michael B. and Baron, Dror and Baraniuk, Richard G. (2009) Representation and Compression of Multidimensional Piecewise Functions Using Surflets. IEEE Transactions on Information Theory, 55 (1). pp. 374-400. ISSN 0018-9448.

PDF - Submitted Version
See Usage Policy.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We study the representation, approximation, and compression of functions in M dimensions that consist of constant or smooth regions separated by smooth (M-1)-dimensional discontinuities. Examples include images containing edges, video sequences of moving objects, and seismic data containing geological horizons. For both function classes, we derive the optimal asymptotic approximation and compression rates based on Kolmogorov metric entropy. For piecewise constant functions, we develop a multiresolution predictive coder that achieves the optimal rate-distortion performance; for piecewise smooth functions, our coder has near-optimal rate-distortion performance. Our coder for piecewise constant functions employs surflets, a new multiscale geometric tiling consisting of M-dimensional piecewise constant atoms containing polynomial discontinuities. Our coder for piecewise smooth functions uses surfprints, which wed surflets to wavelets for piecewise smooth approximation. Both of these schemes achieve the optimal asymptotic approximation performance. Key features of our algorithms are that they carefully control the potential growth in surflet parameters at higher smoothness and do not require explicit estimation of the discontinuity. We also extend our results to the corresponding discrete function spaces for sampled data. We provide asymptotic performance results for both discrete function spaces and relate this asymptotic performance to the sampling rate and smoothness orders of the underlying functions and discontinuities. For approximation of discrete data, we propose a new scale-adaptive dictionary that contains few elements at coarse and fine scales, but many elements at medium scales. Simulation results on synthetic signals provide a comparison between surflet-based coders and previously studied approximation schemes based on wedgelets and wavelets.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle
Baraniuk, Richard G.0000-0002-0721-8999
Additional Information:© 2009 IEEE. Manuscript received March 22, 2006; revised April 15, 2008. Current version published December 24, 2008. This work was supported by the NSF under Grant CCF-0431150, ONR under Grant N00014-02-1-0353, AFOSR under Grant FA9550-04-0148, AFRL under Grant FA8650-051850, and the Texas Instruments Leadership University Program. The material in this paper was presented in part the 38th Annual Conference on Information Sciences and Systems Princeton, NJ, March 2004 and the IEEE International Symposium on Information Theory, Chicago, IL, June/July 2004. The authors wish to thank Justin Romberg, Ron DeVore, Hyeokho Choi, Mark Embree, and Rebecca Willett for enlightening discussions; Peter Jones for inspiring conversations on β-numbers; and Emmanuel Candès and David Donoho for helpful questions.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-02-1-0353
Air Force Office of Scientific Research (AFOSR)FA9550-04-0148
Air Force Research Laboratory (AFRL)FA8650-051850
Texas InstrumentsUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number10370506
Record Number:CaltechAUTHORS:20121004-161000948
Persistent URL:
Official Citation:Chandrasekaran, V.; Wakin, M.B.; Baron, D.; Baraniuk, R.G.; , "Representation and Compression of Multidimensional Piecewise Functions Using Surflets," Information Theory, IEEE Transactions on , vol.55, no.1, pp.374-400, Jan. 2009 doi: 10.1109/TIT.2008.2008153 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34691
Deposited By: Tony Diaz
Deposited On:04 Oct 2012 23:58
Last Modified:07 Apr 2017 19:28

Repository Staff Only: item control page