Progressive image coding by hierarchical linear approximation

Progressive image coding is a useful feature for image databases, image communications, and multimedia information systems. Central to progressive image coding is a multiresolution image pyramid. Quadtree-based recursive regular tessellation is a popular form of image pyramid. But regular tessellation is often too rigid to capture the scene structure of an image; consequently, it may not generate a compact image representation. This paper proposes a scheme of hierarchical piecewise linear approximation as an adaptive image pyramid. A progressive segmentation-based image coder comes naturally from the proposed image pyramid. The new image pyramid is semantically more powerful than regular tessellation while syntactically simpler than free segmentation. This good compromise between the adaptability and complexity of image segmentation contributes to high compression ratios achieved by our progressive image coder. In addition to its advantages in data compression and progressive transmission, our image coder also facilitates many other image manipulations.