Lossy and lossless image encoding using multi-scale recurrent pattern matching

In this study, the authors investigate the use of multi-scale recurrent pattern matching paradigm for lossless image compression. The multi-scale multidimensional parser (MMP) algorithm is a successful implementation of this paradigm for lossy image compression, and can naturally perform lossless compression since it was first derived from a Lempel-Ziv lossless scheme. However, neither its recently adopted coding tools had been adapted for lossless coding nor a thorough analysis of its performance had been carried out. In this work, the authors evaluate MMP´s lossless compression capability, proposing modifications for some of its predictions modes, as well as the inclusion of an adaptive prediction mode based on least squares. The residual information is also coded with well-known techniques used in lossless compression. Experimental results for MMP show that the algorithm achieves a good performance for images such as computed generated graphics and scanned documents, whereas keeping a competitive performance for natural images. Since the algorithm´s structure is exactly the same for lossless and lossy compression, the obtained results suggest that MMP is able to achieve a high compression performance for a wide range of images and rates, from lossy to lossless, without any prior analysis of the image to be coded.