2D-Pattern Matching Image and Video Compression

Personnel: , Marc Alzina, Ananth Grama Wojciech Szpankowski

The central theme of a lossy extension of Lempel-Ziv algorithm is the notion of approximate repetitiveness. If a portion of data recurs in an approximate sense, then subsequent occurrences can be stored as direct or indirect references to the first occurrence. This approximate recurrence of data may not be contiguous. Somewhat surprisingly, this theme of exploiting approximate repetitiveness is uniformly applicable to multimedia data from various sources such as text, images, video, and even audio. However, approximate repetitiveness can be hidden in various forms for different types of media. Therefore, one must consider different distortion measures. This is in contrast with current state-of-the-art, where a different approach is used for compressing each of these types of data. Using the theoretical underpinning of Luczak and Szpankowski " A Suboptimal Lossy Data Compression Based on Approximate Pattern Matching, Atallah, G\'{e}nin and Szpankowski implemented a lossy scheme for image compression. This scheme, called Pattern Matching Image Compression was based on one-dimensional pattern matching enhanced with some salient features. It was shown that for high quality images PMIC scheme is competitive with JPEG and wavelet image compression up to 1 bpp. However, the superiority of PMIC for decompression (PMIC does not require any computation since it basically only reads data) may turn out to be a crucial advantage in practice where asymmetric compression/decompression is a desirable feature (e.g., video). However, a bit rate of 1 bpp is not that interesting from a practical point of view since most image compression applications require bit rates of 0.5 bpp to 0.25 bpp. In 2D-Pattern Matching Image and Video Compression: Preliminary Results , we describe a new implementation based on two-dimensional approximate pattern matching that achieves compression of up to 0.25 bpp for images while preserving other desirable properties of PMIC. We call this scheme 2D-PMIC. You can view some 2D-PMIC still images on this page (see below). We also use this idea to develop a new compression scheme for video data that uses the previous (coded) frame in the group of frames (GOP) as a database. Our preliminary experimental results (view them below) exceed even our expectations: we obtain high quality video with bit rates of $0.15-0.4$ Mbps (without the first frame). Theoretical underpinning of these results as well as algorithms and experimental studies can be found in 2D-Pattern Matching Image and Video Compression: Theory, Algorithms, and Experiments

Implementation Algorihmic Challenge:

Compression Results for Still Images

Compression Results for Video Streams