|CSE Home||About Us||Search||Contact Info|
Project 2 DCT Bit Plane Coder
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. Its highly recommended that you read section 2.2 of PACW for a more detailed description of bit plane coding.
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.
i. perform significance pass transmitting the sign as needed.
ii. perform refinement pass
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).
Weve 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. Weve 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:
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.
We will test your coder at about .5 bpp on some new images. The winner is the one with the highest PSNR.
Code is due Thursday, March 9th, at 9 pm. Turn in your code here. Report is due Friday, March 10th in class.
Computer Science & Engineering|
University of Washington
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to Jenny Liu]