Recursive rectilinear tessellations like quadtree are widely used in i
mage coding, but a regular tessellation, despite its simple geometry,
may not suit image compression because it is too rigid to reflect the
scene structure of an image. This paper presents a new image pyramid f
ormed by adaptive, tree-structured segmentation to be a framework of a
predictive multiresolution image coder. Subjectively appealing compre
ssion results are obtained at different resolutions by scene-adaptive,
tree-structured segmentation and by exploiting the statistical depend
ency between the layers of the image pyramid. The adaptive segmentatio
n-based image coder is constructed by recursive, least-squares piecewi
se functional approximation. The seemingly expensive encoding process
can be made efficient by an incremental least-squares computation tech
nique. The decoding is simple and can be done in real time if assisted
by existing hardware technology.