Optimal piecewise linear image coding

Dietmar Saupe

doi:10.1117/12.298387

9 January 1998 Optimal piecewise linear image coding

Dietmar Saupe

Proceedings Volume 3309, Visual Communications and Image Processing '98; (1998) https://doi.org/10.1117/12.298387
Event: Photonics West '98 Electronic Imaging, 1998, San Jose, CA, United States

Abstract

Piecewise linear (PL) image coding proceeds in three steps: 1) a digital image is converted into a 1D-signal using a scanning procedure, for example by scanning lines in a zig- zag or Hilbert order. 2) The signal is approximated by the graph of a piecewise linear function, which consists of a finite number connected line segments. 3) Entropy encoding of the sequence of the segment end points. In this step differential coding can be used for one or both coordinate sequences of the end points. In this step differential coding can be used for one or both coordinate sequences of the end points. To ensure a desired approximation quality a constraint is imposed, e.g., on the root-mean-square error of the PL signal. In this paper we consider uniform approximation. Two problems are addressed: first, an optimal PL approximation in the sense of a minimal number of segments is to be obtained. Second, when entropy coding of the segments is used, how can one jointly optimize the variable length code and the PL approximation yielding a better or even minimal rate without violating the uniform error bound. The first problem is solved by dynamic programing, the second is approached by using Huffman coding and an annealing procedure in which the design of the Huffman tables and the dynamic programming is alternately iterated using a cost function that reflects the codework lengths of the current variable length code. This algorithm is guaranteed to converge to a minimum length code. We describe the algorithms, implementation issues, compare two different scanning procedures, the zig-zag line scan and the Hilbert scan, and report results for encoding various test images.

Citation Download Citation

Dietmar Saupe "Optimal piecewise linear image coding", Proc. SPIE 3309, Visual Communications and Image Processing '98, (9 January 1998); https://doi.org/10.1117/12.298387

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available