CS 6604, Assignment 5 - Due April 30, 2008

The Karhounen-Loéve Expansion

The big advantage of the KL transform is that it decorrelates data with the result that lossy data compression can often be achieved by encoding only the high variance transform coefficients. The identification of those high variance coefficients is a natural byproduct of the transform. The disadvantage of the transform is that it is data-dependent. In order to wring as much compression as possible out of the data, the transform must be computed for each data set.

To demonstrate the KL transform we compute the transform for a 3-band color image, treating the 3-component RGB pixels as an ensemble of data vectors to be encoded. The specific goal here is to compute the principal component image, which is a single band image that contains most of the variance. This is an excellent method for computing a black-and-white image from a color image, in contrast to simply averaging the three spectral bands.

Data:

Although you may use any additional images you wish, I would like you to process and submit the 640 × 476 pixel island.jpg image whose RGB component images are given on the class website:

Discussion:

To do this we use the K-L expansion. Suppose that the pixel triples form an oval cluster in 3-space. Then by computing the principal engenvector of the scatter matrix (actually the covariance matrix for the 3D pixels) we can determine that linear combination of images that generates the principal component. Be careful to use signed, floating point arithmetic... consider what to do if some of the pixels in the component images should have negative values or positive values in excess of 255.

Generate the other components, too, just to determine how much less information they really contain.

Submission:

I would like to two things by the due date:
  1. A very brief report giving the covariance matrix, the eigenvalues and corresponding eigenvectors, and an explanation of how you did the normalizations necessary to obtain the viewable images you are submitting.

  2. A zip file emailed to me containing:

    1. A viewable .raw format principle component image
    2. A viewable .raw format image formed by averaging the RGB bands
    3. The RGB bands reconstructed from the principle component image alone. Just form a single .raw image with the R, G, and B images concatenated, one after the other. Photoshop and Paintshop Pro will both read .raw color images in that format.