Share Email Print

Proceedings Paper

Optimal piecewise linear image coding
Author(s): Dietmar Saupe
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 9 January 1998
PDF: 14 pages
Proc. SPIE 3309, Visual Communications and Image Processing '98, (9 January 1998); doi: 10.1117/12.298387
Show Author Affiliations
Dietmar Saupe, Univ. Freiburg (Germany)

Published in SPIE Proceedings Vol. 3309:
Visual Communications and Image Processing '98
Sarah A. Rajala; Majid Rabbani, Editor(s)

© SPIE. Terms of Use
Back to Top