Progressive image coding is a useful feature for image databases, imag
e communications, and multimedia information systems. Central to progr
essive image coding is a multiresolution image pyramid. Quadtree-based
recursive regular tessellation is a popular form of image pyramid. Bu
t regular tessellation is often too rigid to capture the scene structu
re of an image; consequently, it may not generate a compact image repr
esentation. This paper proposes a scheme of hierarchical piecewise lin
ear approximation as an adaptive image pyramid. A progressive segmenta
tion-based image coder comes naturally from the proposed image pyramid
. The new image pyramid is semantically more powerful than regular tes
sellation while syntactically simpler than free segmentation. This goo
d compromise between the adaptability and complexity of image segmenta
tion contributes to high compression ratios achieved by our progressiv
e image coder. In addition to its advantages in data compression and p
rogressive transmission, our image coder also facilitates many other i
mage manipulations.