TY - JOUR
T1 - Representation and compression of multidimensional piecewise functions using surflets
AU - Chandrasekaran, Venkat
AU - Wakin, Michael B.
AU - Baron, Dror
AU - Baraniuk, Richard G.
N1 - Funding Information:
Dr. Baraniuk has been a Guest Editor of special issues for the IEEE Signal Processing Magazine on “Signal Processing and Networks” in 2002 and “Compressive Sampling” in 2008 and for the PROCEEDINGS OF THE IEEE on “Educational Technology” in 2008. He is currently an Associate Editor for the ACM Transactions on Sensor Networks and Applied and Computational Harmonic Analysis. He was Co-Technical Program Chair for the 2007 IEEE Statistical Signal Processing Workshop. He received a NATO postdoctoral fellowship from NSERC in 1992, the National Young Investigator award from the National Science Foundation in 1994, a Young Investigator Award from the Office of Naval Research in 1995, the Rosenbaum Fellowship from the Isaac Newton Institute of Cambridge University in 1998, the C. Holmes MacDonald National Outstanding Teaching Award from Eta Kappa Nu in 1999, the Charles Duncan Junior Faculty Achievement Award from Rice in 2000, the University of Illinois ECE Young Alumni Achievement Award in 2000, the George R. Brown Award for Superior Teaching at Rice in 2001, 2003, and 2006, the Hershel M. Rich Invention Award from Rice in 2007, the Wavelet Pioneer Award from SPIE in 2008, and the Internet Pioneer Award from the Berkman Center for Internet and Society at Harvard Law School in 2008. He was selected as one of Edutopia Magazine’s Daring Dozen educators in 2007. Connexions received the Tech Museum Laureate Award from the Tech Museum of Innovation in 2006. His work with Kevin Kelly on the Rice single-pixel compressive camera was selected by MIT Technology Review Magazine as a TR10 Top 10 Emerging Technology in 2007. He was coauthor on a paper with Matthew Crouse and Robert Nowak that won the IEEE Signal Processing Society Junior Paper Award in 2001 and another with Vinay Ribeiro and Rolf Riedi that won the Passive and Active Measurement (PAM) Workshop Best Student Paper Award in 2003. He was elected a Fellow of the IEEE in 2001 and a Plus Member of AAA in 1986.
Funding Information:
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.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
KW - Compression
KW - Discontinuities
KW - Metric entropy
KW - Multidimensional signals
KW - Multiscale representations
KW - Nonlinear approximation
KW - Rate-distortion
KW - Sparse representations
KW - Surflets
KW - Wavelets
UR - http://www.scopus.com/inward/record.url?scp=58249141985&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58249141985&partnerID=8YFLogxK
U2 - 10.1109/TIT.2008.2008153
DO - 10.1109/TIT.2008.2008153
M3 - Article
AN - SCOPUS:58249141985
VL - 55
SP - 374
EP - 400
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
SN - 0018-9448
IS - 1
ER -