Optimal construction of reduced pyramids for lossless and progressive image coding

Reduced pyramids, including in particular pyramids without analysis filters , are known to produce excellent results when used for Lossless signal and image compression. The present paper presents a methodology for the optimal construction of such pyramids by selecting the interpolation synthesis pos t-filters so as to minimize the error variance at each level of the pyramid . This establishes optimally efficient interpolative pyramidal lossless com pression, it also has the added advantage of producing lossy replicas of th e original which, at Lower resolutions, retain as much similarity to the or iginal as possible. This is highly useful for the progressive coding of sig nals or images needed for many applications such as fast browsing through i mage databases or hybrid lossless/lossy medical image coding. The general o ptimization methodology is developed first, for a general family of reduced pyramids. Subsequently, this is applied to the optimization of pyramids in this family formed using separable, two-dimensional (2-D) quincunx and thr ee-dimensional (3-D) face-centered orthorhombic lattice sampling matrices. It is shown that this family includes in particular the well known 2-D and 3-D "hierarchiclal interpolation" (HINT) techniques which have been particu larly popular for the lossless compression of medical records. Optimal vers ions of these techniques are determined for 2-D and 3-D images characterize d by separable or isotropic correlation functions. The advantages of the de veloped methods are demonstrated by experimental evaluation. It is shown th at the method outperforms the HINT method for the lossless compression of 3 -D images. It is also shown to outperform all other known interpolative cod ers and to produce results comparable to the best predictive lossless coder of 2-D images.