CS 6604, Project -
Due April 28, 2008
Data Compression Projects
Your project report will be completed in two stages as described below and
should consist of the particulars of your design in enough detail that others
could reconstruct your work. It should include your code and performance
evaluation such as timings, space requirements. The projects may be done
individually or jointly by agreement in advance. Proposals for interesting
projects not listed below are also invited.
Possible Projects:
- Implement and test an adaptive Huffman encoder and decoder.
- Implement and test an adaptive binary Q-coder/decoder (Pennebaker, et al.,
IBM J. Res. Devel., November 1988).
- Implement and test a FELICS encoder/decoder for lossless 8-bit greyscale
image compression
(Howard, 1993) and Howard and Vitter, Proc. DCC 1993, pp. 351-360.
- Implement and test a PNG encoder/decoder for 8-bit greyscale images.
- Implement a TIFF Group 4 to PNG converter for bilevel images.
- Implement a Karhounen-Loéve encoder/decoder for color images, experimenting with
coefficient quantization and compression.
- Implement and test the performance of a greyscale DCT compressor like JPEG but with
nonstandard block sizes instead of the usual 8 × 8 blocks.
- Implement and test the "Fast PPM" encoder/decoder (Howard and Vitter,
Proc. DCC 1993, pp. 98-107.
- Implement and test a lossy color quantization algorithm similar to the Heckbert
algorithm (Heckbert, ACM Computer Graphics 16(3), pp. 297-307, July 1982.
- Design and test a lossless encoder/decoder for halftones as in the JBIG2 standard.
This will require some image analysis to determine the halftone periodicity.
Implemenation Notes
All code is expected to be original code, except where an arithmetic coder is
required, in which case existing code can be used. In order to maximize
performance, c or c++ is recommended so that pointers and storage issues can
be explicitly managed.
The compression algorithms should be implemented as functions so that they
can be reused. These should be called by a short main program that handles
data input and output and performance evaluation. Be very careful not to make
function calls in the innermost loops, since these would seriously degrade
performance.
Code should be documented, especially at the conceptual level. Variables should
be explicitly declared LONG, SHORT, or BYTE, according to whether their length is
intended to be 32, 16, or 8 bits.
CPU timings are easy to make with the clock function. Include <time.h>
and declare a couple of variables, like start and finish, to be of type clock_t.
At the beginning of the timing interval call start = clock ( ), and at the end call
finish = clock ( ). Then the time in seconds is (finish - start) / CLOCKS_PER_SEC.
Submission
- The first step is to select a project and thoroughly research it to get a
clear understanding of the technnology and the project scope. A project proposal
describing the project is due March 31, 2008. This proposal should
include
- A detailed presentation of the algorithms to be implemented.
- A bibliography containing the necessary technical information.
- The data corpus that will be used to test its performance.
- Existing algorithms against which performance will be compared.
- Due on the final due date is a project report describing the implementation,
the compression results, the speed of the technique, the processor on which tests
are run, and (if applicable as in the case of lossy compression) an evaluation of
the quality of the results. When evaluating the quality of reconstructed grescale
images using lossy compression, the normal quality metric is PSNR as given on the
6604 homepage.