Progressive lossless image coding via self-referential partitions

In a given binary image, we identify two disjoint sets of image subblocks of varying size which we call range blocks and domain blocks. The range blocks form a partition of the image called a self-referential partition because each range block is represented via a pointer to a matching domain block. The encoder transmits encoded versions of these pointers together with one pixel from each domain block. This information, when decoded, allows progressive reconstruction of the image. On several archival images, our progressive lossless image coder gave better compression performance than that provided by the 2-D Lempel-Ziv algorithm, multi-window quadtree coding, and Huffman coding of runlengths. The progressive image coder is fast and has a worst-case redundancy performance better than the best currently known worst-case redundancy upper bound for the 2-D Lempel-Ziv algorithm.