CSE logo University of Washington Computer Science & Engineering
 Project 2
  CSE Home   About Us    Search    Contact Info 

Project 2 – DCT Bit Plane Coder

Objectives

 

Overview

You will be using your arithmetic coder from project 1 to build a bit plane arithmetic coder for grayscale images that uses the discrete cosine transform. It’s highly recommended that you read section 2.2 of PACW for a more detailed description of bit plane coding.

 

Assignment

 

Algorithmic overview

 

 

Encoding :

  1. Perform a discrete cosine transform on the image
    1. break the image into 4x4 or 8x8 pixel blocks

 

    1. Perform a discrete cosine transform on each block

 

 

If you use a 4x4 transform then the result will look like the Block View on the left, with the circle being the DC coefficient. We can conceptually reorder the coefficients on the left into subbands, shown on the right Subband View. There is a subband for each of the 16 coordinates of a 4 x 4 block, and the number of coefficients in each subband is equal to the number of blocks in the original image. With discrete cosine transform, most of the energy of the image is collected in the upper left subband in the Subband View. The nearer the other subbands are to the upper left subband, the more important they are to the encoding of the image.

 

 

  1. Subtract off the average of the DC subband. The average will be transmitted to the decoder.

 

  1. Split the transformed blocks into bit planes.

 

  1. Code bit planes until target bbp is reached.
    1. to code a bit plane using an arithmetic coder.

                                                               i.      perform significance pass transmitting the sign as needed.

                                                             ii.      perform refinement pass

    1. Choosing the context for the arithmetic coder is up to you. The contexts used in your project 1 are probably not good for this, but several ideas in class were given for decent contexts.
    2. The order of transmission of the bits is up to you. However, transmitting the DC subband first is a good idea. The remainder of the subands can be send in zig-zag order. Other possibilities are using a priority queue as described in the PACW paper.

 

 

 

Decoding:

The decoder will know the order that the bits are sent by being synchronized with the encoder. As an example suppose we send the bits in a particular 3x3 subband which is indexed as follows.

 

1 2 3

4 5 6

7 8 9

 

All the coordinates will be insignificant in the beginning. Suppose 4 and 7 become significant on the first significance pass. Then the decoder can mark 4 and 7 as being significant. On the first refinement pass, there will be nothing to refine since everything was insignificant before this bit plane was received. On the second significance pass, the decoder will know that 4 and 7 are already significant and will expect the bits in the significance pass to refer only to the still insignificant bits (1, 2, 3, 5, 6, 8, 9). The decoder will also expect the bits in the refinement pass to refer to the bits that have become significant before this bit plane (bits 4 and 7).

 

 

The Code

Download it here

We’ve provided forward and inverse discrete cosine transform methods that are actually just the identity transform. You will need to implement the forward and inverse discrete cosine transforms. We’ve also provided a bit plane coder that codes by bit planes in a na´ve way. It just sends one bit plane at a time to the arithmetic coder in a single pass (without separating the data into a significance pass and a refinement pass). It sends the sign plane first, then sends the rest of the bit planes in subband raster order (and coefficient raster order within each subband). You will need to replace the current implementation to perform a significance pass and a refinement pass for each bit plane up to the target bpp. In addition, you will have to choose contexts and ordering to send the bits.

 

At 3 bbp, the provided code compresses barbara.bmp (using default context) to:

 

 

At 3 bbp, a bit plane coder with significance and refinement passes and discrete cosine transform compresses barbara.bmp to:

 

You will need to modify four methods. Look for the TODO: labels in the comments of the code.

 

Some of the other classes (the rest are the same/very similar as Project 1):

 

 

Other methods you may optionally want to modify:

 

 

The Report

When you are done implementing DCT and bit plane coding, experiment with different block sizes, different contexts, and different orderings to see what works better/worse on different images. What happens to the compression rate? The PSNR? The visual quality? Are there any patterns to your observations? Remember that your image height and width must be a multiple of the block size. Explain what decisions you made in your final coder and why you made them.

 

Compare your compression algorithm to JPEG and JPEG 2000. Make a plot showing the PSNR of each of the methods for at least 20 different bpps.

In the project2.zip archive are two little java programs to compress bmp images using JPEG and JPEG2000 and report back the PSNR. The arguments for JPEG and JPEG2000 are : (input bmp file) (output jpg [2k] file) (desired bbp)

To compile and run JPEG2000.java, you will need to download the java medio i/o package and put jai_imageio-1_0_01/lib/jai_imageio.jar in your classpath.

I downloaded the Linux CLASSPATH install, gunzip'ped and untar'ed it in the same directory as JPEG2000.java, and compiled and ran JPEG2000 with the following commands:

% javac -cp "jai_imageio-1_0_01/lib/jai_imageio.jar:." JPEG2000.java
% java -cp "jai_imageio-1_0_01/lib/jai_imageio.jar:." JPEG2000 (arguments go here)

 

Your report should be less than 4 pages.

 

The Contest

We will test your coder at about .5 bpp on some new images. The winner is the one with the highest PSNR.

Due Date

 

Code is due Thursday, March 9th, at 9 pm. Turn in your code here. Report is due Friday, March 10th in class.

 


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to Jenny Liu]