Project 2 – DCT Bit Plane Coder

Objectives

• Learn how to implement an embedded image compression algorithm using bit plane coding.
• Learn how choosing proper contexts can improve image quality for the same bit rate.

 

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

 

2. 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.

 

 

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

 

3. Split the transformed blocks into bit planes.

 

4. 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

2. 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.
3. 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.

• BitPlaneEncoder.java -- the encode method. You’ll want to use the isSig[][] data structure, the method currentBpp(), Tools.SIGNIFICANT
• BitPlaneDecoder.java -- the decode method
• DiscreteCosineTransform -- forwardTransform and inverseTransform.

 

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

• BitPlaneCoder.java – the main class
• BitPlaneEndec.java – the parent class of BitPlaneEncoder and BitPlaneDecoder, methods that are used by both Encoder and Decoder are in here
• DoublyLinkedList.java and ListNode.java – self-explanatory
• Tools.java – provides constants and static methods shared amongst classes.
• ArithmeticCoder.class – the compiled version of an arithmetic coder that you can use. You can see the methods you will need because they are called from BitPlaneEncoder.java and BitPlaneDecoder.java.

 

 

Other methods you may optionally want to modify:

• BitPlaneEndec.findContext( ) to set up your own contexts.

 

 

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 9^th, at 9 pm. Turn in your code here. Report is due Friday, March 10^th in class.