TY - JOUR

T1 - Multiscale approximation of piecewise smooth two-dimensional functions using normal triangulated meshes

AU - Jansen, Maarten

AU - Baraniuk, Richard

AU - Lavu, Sridhar

N1 - Funding Information:
* Corresponding author. E-mail addresses: [email protected] (M. Jansen), [email protected] (R. Baraniuk), [email protected] (S. Lavu). 1 Supported by NSF, ONR, AFOSR, DARPA, and the Texas Instruments Leadership University Program.

PY - 2005/7

Y1 - 2005/7

N2 - Multiresolution triangulation meshes are widely used in computer graphics for representing three-dimensional (3-d) shapes. We propose to use these tools to represent 2-d piecewise smooth functions such as grayscale images, because triangles have potential to more efficiently approximate the discontinuities between the smooth pieces than other standard tools like wavelets. We show that normal mesh subdivision is an efficient triangulation, thanks to its local adaptivity to the discontinuities. Indeed, we prove that, within a certain function class, the normal mesh representation has an optimal asymptotic error decay rate as the number of terms in the representation grows. This function class is the so-called horizon class comprising constant regions separated by smooth discontinuities, where the line of discontinuity is C2 continuous. This optimal decay rate is possible because normal meshes automatically generate a polyline (piecewise linear) approximation of each discontinuity, unlike the blocky piecewise constant approximation of tensor product wavelets. In this way, the proposed nonlinear multiscale normal mesh decomposition is an anisotropic representation of the 2-d function. The same idea of anisotropic representations lies at the basis of decompositions such as wedgelet and curvelet transforms, but the proposed normal mesh approach has a unique construction.

AB - Multiresolution triangulation meshes are widely used in computer graphics for representing three-dimensional (3-d) shapes. We propose to use these tools to represent 2-d piecewise smooth functions such as grayscale images, because triangles have potential to more efficiently approximate the discontinuities between the smooth pieces than other standard tools like wavelets. We show that normal mesh subdivision is an efficient triangulation, thanks to its local adaptivity to the discontinuities. Indeed, we prove that, within a certain function class, the normal mesh representation has an optimal asymptotic error decay rate as the number of terms in the representation grows. This function class is the so-called horizon class comprising constant regions separated by smooth discontinuities, where the line of discontinuity is C2 continuous. This optimal decay rate is possible because normal meshes automatically generate a polyline (piecewise linear) approximation of each discontinuity, unlike the blocky piecewise constant approximation of tensor product wavelets. In this way, the proposed nonlinear multiscale normal mesh decomposition is an anisotropic representation of the 2-d function. The same idea of anisotropic representations lies at the basis of decompositions such as wedgelet and curvelet transforms, but the proposed normal mesh approach has a unique construction.

KW - Approximation

KW - Image

KW - Mesh

KW - Multiresolution

KW - Normal offsets

KW - Wavelet

UR - http://www.scopus.com/inward/record.url?scp=20144372379&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=20144372379&partnerID=8YFLogxK

U2 - 10.1016/j.acha.2005.02.006

DO - 10.1016/j.acha.2005.02.006

M3 - Article

AN - SCOPUS:20144372379

SN - 1063-5203

VL - 19

SP - 92

EP - 130

JO - Applied and Computational Harmonic Analysis

JF - Applied and Computational Harmonic Analysis

IS - 1

ER -