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:

The implementation of 2D-PMIC is a challenging problem from the algorithmic standpoint. Finding an efficient data structure for approximate search of multidimensional sets in a huge multidimensional database, is an interesting problem in itself. We use a set of modified k-d trees enhanced by generalized run length coding for approximate search. A key issue for high quality image and video compression is the design of an adaptive distortion measure that automatically adjusts its maximum distortion to produce perceptually high quality results. We propose a few solutions and examine their performance in 2D-Pattern Matching Image and Video Compression: Theory, Algorithms, and Experiments

Compression Results for Still Images

A summary of the performance of Comprime and its comparison to JPEG is as follows (images will open in new browser window):

original 0.25bpp 0.5bpp 1bpp 2bpp
Banner view view view view
Basselope view view view view
Lena view view view view
San Francisco view view view view

Compression Results for Video Streams

As mentioned above, in the case of video streams, the database corresponds to an image in the past. Tbale below summarizes our results that can be viewed below (to view them you need to have Avi or QuickTime software installed).

Claire_High Quality 0.14 33.7
Claire_Low Quality 0.07 31.0
Ping Pong_High Quality 0.40 24.0
Ping Pong_Low Quality 0.26 22.6

To see more video clips click here .