Image Compression Using Human Visual System Models, Wavelet Transform Coding, and Massively Parallelizable Algorithms

NASA Grant NAG 5-2200

Principal investigator:

The objective of this Guest Computational Investigator Project was to develop image compression systems that employ subband/ wavelet transform coding as well as models of human visual system models. Many of the algorithms were developed on a MasPar system, a massively parallel computer located at GSFC, NASA.

Approach

Subband Coding (Wavelet transform coding can be considered as a special case of subband coding) and vector quantization are powerful, but computationally complex techniques for data compression. In many applications involving image compression, the final judge of quality of compressed data is the human observer. A good understanding of how the human visual system works is important in the development of image compression systems that aim to minimize the subjective distortions in the compressed images. Our approach to image compression involves developing a method that combines subband coding and vector quantization. Furthermore, subjective quality improvements are achieved by using appropriate vision models in the development of the system. In order to maximize the coding gains of the system, each of its components is optimized to provide the best possible quality for the input images. The resulting algorithms tend to be computationally complex and therefore, efficient parallel algorithms are required for their implementation.

Significance of the Work

With the advent of the information super highway, the amount of digital data that are transmitted and stored in the form of digital images has been increasing in an exponential manner. Some form of compression has become mandatory in most applications since storage and transmission bandwidths are finite quantities. Our method, adds significantly to the current state-of-the-art in image compression technology. Application areas include storage, browsing and remote retrieval of vast amounts of earth and space science data generated by NASA missions, HDTV, video phones as well as other video communication systems, storage of medical image data, etc.

Accomplishments of the Project

• An algorithm for designing filter banks that provide the least overall distortion for given input images and quantizers have been developed. This work formed the basis of a Master's thesis written by B. K. Dharia.

• An algorithm that incorporates visual detection threshold models in vector quantizers have been developed. The threshold models predict the amount of distortion in any image that is not noticed by human viewers. If the quantization errors are kept below the threshold values, the resulting image should look identical to the original image, even though it requires fewer bits to transmit or store the quantized images. This work is the basis of the Ph. D. research work of P. J. Hahn. The following papers that describes some of our work in this area may be downloaded in postscript form.

  • V. J. Mathews, ``Vector quantization of images using the $L_\infty$ distortion measure," Proceedings of the IEEE International Conference on Image Processing, Washington, D. C., October 1995. (Postscript)

  • P. J. Hahn and V. J. Mathews, ``Distortion-limited vector quantization," Proceedings of the Data Compression Conference, Snowbird, Utah, April 1996. (Postscript)

  • V. J. Mathews and P. J. Hahn, ``Vector quantization using the $L_\infty$ distortion measure," submitted to IEEE Signal Processing Letters. (Postscript)

• A new visual detection threshold model has been developed. This model appears to be superior to other models that are available in the literature. The superiority is in the sense that the new model allows larger threshold values than previously developed models. This in turn allows higher compression capabilities. K. S. Prashant wrote his Master's thesis in this area. The work was also presented in the following paper.

  • K. S. Prashant, V. J. Mathews and P. J. Hahn, ``A New Model of Perceptual Threshold Functions for Application in Image Compression Systems," Proceedings of the IEEE Data Compression Workshop, Snowbird, Utah, March 1995. (Postscript)

• Programs have been written on MasPar to implement the following systems.

  • A vector quantizer encoder We believe that this program is among the most efficient written for the MasPar system located at GSFC.

  • A codebook generator for vector quantizers. The algorithms for vector quantization and its performance evaluation have been documented in

    • K. S. Prashant and V. J. Mathews, ``A Massively Parallel Algorithm for Vector Quantization," Proc. of the 1995 NASA Space and Earth Sciences Workshop, Salt Lake City, Utah, March 1995. (Postscript)

    MasPar programs for Vector Quantization can be downloaded by clicking here.

  • Algorithms for subband decomposition and synthesis

  • A subbad vector quantizer system

  • An algorithm for computing the Gabor transform of images. This program was used for developing vision models.

  • The new model of visual detection threshold functions.

Refereed Publications Resulting from Work on the Project

• K. S. Prashant, V. J. Mathews and P. J. Hahn, ``A New Model of Perceptual Threshold Functions for Application in Image Compression Systems," Proceedings of the IEEE Data Compression Workshop, Snowbird, Utah, March 1995. (Postscript)

• K. S. Prashant and V. J. Mathews, ``A Massively Parallel Algorithm for Vector Quantization," Proc. of the 1995 NASA Space and Earth Sciences Workshop, Salt Lake City, Utah, March 1995. (Postscript)

• V. J. Mathews, ``Vector quantization of images using the $L_\infty$ distortion measure," Proceedings of the IEEE International Conference on Image Processing, Washington, D. C., October 1995. (Postscript)

• P. J. Hahn and V. J. Mathews, ``Distortion-limited vector quantization," Proceedings of the Data Compression Conference, Snowbird, Utah, April 1996. (Postscript)

• V. J. Mathews and P. J. Hahn, ``Vector quantization using the $L_\infty$ distortion measure," submitted to IEEE Signal Processing Letters. (Postscript)

Graduate Students Who Worked on this Project

• B. K. Dharia, ``Design of filter banks for subband coding systems," M. S. Thesis, University of Utah, March 1994.

• K. S. Prashant, ``Design of a perceptual threshold model and parallel algorithms for image compression," M. S. Thesis, University of Utah, August 1995.

• P. J. Hahn, ``Perceptually lossless image compression," Ph. D. Dissertation, University of Utah, Expected date of completion - June 1997.