Scenario

Image compression is a critical application that seeks to reduce the storage space required for images without losing significant information. Let’s represent the image to be compressed as I. The objective of image compression is to find an integer coef- ficient matrix, C, that requires less storage than I, but still allows the reconstructed image from C to closely resemble I. An effective strategy for achieving compression is to identify a matrix C where most of its values are zero.  In this project, we will simulate a simplied version of practical image compression, without using any coding scheme.

In this project, the term  “compression ratio”, denoted by r, refers to the ratio of the total number of the pixels of the image I to the the numbers of non-zero entries of C. Taking r = 10 and an image of size 256 × 256 = 2562  for example.  The compression ratio is then 10 : 1, which means the number of non-zero entries of C is no large than (0.1 ∗ 2562 ) ≈ 6553.

Procedure and implementation

In this project,  we will  simulate  a simplified version of one popular compression technique, namely JPEG. The process for JPEG image compression in this project is outlined below.

1.  Divide an image I ∈ RM×N  into non-overlapping image patches of size 8 × 8, denoted by {Pm,n } ⊂ R8×8 .  .

2.  Perform a 2D Discrete Cosine Transform (DCT) on each image patch Pm,n   ∈ R8×8. The resulting coefficient matrix for each patch is denoted as Cm,n  ∈ R8×8 .

3.  Assemble all 8 × 8 coefficient matrices Cm,n  ∈ R8×8  to form a larger coefficient matrix C ∈ RM×N .

4. Retain only the MN (rounded to the nearest integer) entries of the coefficient matrix C untouched with the largest magnitude, and set all other entries to 0.

The procedure of image de-compression is described as follows. Note that this proce- dure will depend on how the larger matrix C is formed in the compression process.

Figure  1:  Dividing the  image,  applying  DCT on  each patch,  assembling  coefficient matrix

1.  Segment the coefficient matrix C ∈ RM×N  into non-overlapping sub-matrices of size 8×8, denoted by Cm,n  ⊂ R8×8 . The total number of such sub-matrices will  .

2.  For every coefficient sub-matrices Cm,n , generate an image patch of size 8 × 8 by applying a 2D inverse Discrete Cosine Transform (iDCT) to it, and rounding all entries to the integer within the range [0, 255], The resulting image patch is denoted as Qm,n  ∈ N8×8 .

3.  Constructing the image J  ∈ ZM×N   by joining all the 8 × 8 converted image patches {Qm,n  ∈ N8×8}

[Remark 1].  The reconstructed image  J will be an approximation to the oriental image I. A lower compression ratio r will yield a smaller difference between J and I. When r = 1, the difference between two is negligible.

[Remark 2] In the procedures for compression and decompression, it’s assumed that the image data extracted from the file are the integers in the range [0 , 255]. If the data retrieved from the image file are floating-point numbers, ensure they are converted to integers within the range [0, 255].

Functions to be implemented.

The project need to be programmed in Python,  and the following 4 routines are expected.

dct2d(im)

Computing 2D discrete Cosine transform of a given ndarray im

Parameters: im:  ndarray

An array representing image

Returns:        out:  ndarray

An array representing the resulting DCT coefficients with the same shape as im

idct2d(coef)

Computing a ndarray from the ndarray coef which represents its DCT coefficients

Parameters: coef:  ndarray

An array representing 2D DCT coefficients

Returns:        out:  ndarray

An array representing the reconstructed image

imcompress(im, r)

Compress the input ndarray  im with input compression ratio  r.   and returning  a coefficient ndarray with many entries being zero.

Parameters: coef:  ndarray

An array representing image for compression

r: float

A scalar number representing compression ratio.

out:  ndarray

An array representing the coefficients after compression

imdecomp(coef)

Reconstructing an image from the compressed coefficient ndarray coef

Parameters: coef:  ndarray

An array representing compressed coefficients

Returns:        out:  ndarray

An array representing the reconstructed image

Data for testing

Use the grey-scale image provided in the project, or use your own with image size that can be divided by 8.