Lossless image compression based on a generalized recursive interpolation

A variety of image compression algorithms exists for applications where reconstruction errors are tolerated. When lossless coding is mandatory, compression ratios greater than 2 or 3 are hard to obtain. DPCM techniques can be implemented in a hierarchical way, thus producing high-quality intermediate versions (tokens) of the input images at increasing spatial resolutions. Data retrieval and transmission can be achieved in a progressive fashion, either by stopping the process at the requested resolution level, or by recognizing that the image being retrieved is no longer of interest. However, progressiveness is usually realized with a certain performance penalty with respect to the reference DPCM (i.e., 4-pel optimum causal AR prediction). A generalized recursive interpolation (GRINT) algorithm is proposed and shown to be the most effective progressive technique for compression of still images. The main advantage of the novel scheme with respect to the standard hierarchical interpolation (HINT) is that interpolation is performed in a separable fashion from all error-free values, thereby reducing the variance of interpolation errors. Moreover, the introduction of a parametric half-band interpolation filter produces further benefits and allows generalized interpolation. An adaptive strategy consists of measuring image correlation both along rows and along columns and interpolating first along the direction of minimum correlation. The statistics of the different subband-like sets of interpolation errors are modeled as generalized Gaussian PDFs, and individual codebooks are fitted for variable length coding. The estimate of the shape factor of the PDF is based on a novel criterion matching the entropy of the theoretical and actual distributions. Performances are evaluated by comparing GRINT with HINT, and a variety of other multiresolution techniques. Optimum 4-pel causal DPCM and lossless JPEG are also considered for completeness of comparisons, although they are not progressive. For the examined images GRINT is always superior. Only optimum DPCM provides comparable results; GRINT is, however, progressive and yields error-free tokens at any resolution level.