Normal offsets for digital image compression

The wavelet transform is well suited for approximation of two dimensional functions with certain smoothness character-istics. Also point singularities, e.g. texture-like structures, can be compactly represented by wavelet methods. However, when representing line singularities following a smooth curve in the domain – and should therefore be characterizes by a few parameters – the number of needed wavelet coefficients rises dramatically since fine scale tensor product wavelets, catching these steep transitions, have small local support. Nonetheless, for images consisting of smoothly colored regions separated by smooth contours most of the information is comprised in line singularities (e.g. sketches). For this class of images, wavelet methods have a suboptimal approximation rate due to their inability to take advantage of the way those point singularities are placed to form up the smooth line singularity. To compensate for the shortcomings of tensor product wavelets there have already been developed several schemes like curvelets,2 ridgelets,4 bandelets10 and so on. This paper proposes a nonlinear normal offset decomposition method which partitions the domain such that line singularities are ap-proximated by piecewise curves made up of borders of the subdomains resulting from the domain partitioning. Although more general domain partitions are possible, we chose for a triangulation of the domain which approximates the contours by polylines formed by triangle edges. The nonlinearity lies in the fact that the normal offset method searches from the midpoint of the edges of a coarse mesh along the normal direction until it pierces the image. These piercing points have the property of being attracted towards steep color value transitions. As a consequence triangular edges are attracted to line up against the contours