An efficient coding method for spatial data: The rotating, hierarchical, overlapping representation

A new, efficient image compression algorithm based on a rotating, overlapping, hierarchical representation (ROHR) is presented. This algorithm first decomposes the spatial image data into a hierarchical coordinate space, composed of interconnected nodes. The surprise of each node represents the entropy of the corresponding image area, and determines its significance in reconstructing the image. Surprises are ordered and transmitted in decreasing order of magnitude with a bucket encoding method, yielding an embedded code. ROHR allows for either lossless compression, or for termination of the encoding or decoding at any point to meet a target compression ratio or distortion metric. In the latter; image reconstruction from the transmitted data occurs without the introduction of artifacts that would indicate where the truncation occurred. Moreover, the procedures allow for real-time video encoding or decoding operations on color images of 256 x 192 pixels on current PC architectures, considerably faster than equivalent software JPEG codecs.