Prediction with Partial Match using two-dimensional approximate contexts

The Prediction with Partial Match (PPM) is a context-based lossless compression scheme developed in the mid 80´s. Originally it was targeted towards compressing text that can be viewed as a one-dimensional sequence of symbols. When compressing digital images, PPM usually breaks the two-dimensional data into a one-dimensional raster scan form. This paper extends PPM in order to take full advantage of the two-dimensional nature of digital images. Unlike the traditional two-dimensional raster scan contexts (i.e. concerning upper pixels and pixels to the left), the proposed context is determined using pixels from all directions, including pixels to the right and the lower pixels. Results show that this type of context yields a significant improvement over the traditional raster scan context.