Discrete Cosine Transform Encoding Package

[Greg Cockroft]

The code contained in this directory implements Discrete Cosine Transform
Encoding of 24 bit sun rasterfiles.  The file format dependencies have
been isolated, so it should be trivial to add additional file types. 

The purpose is to compress large images to very small sizes without loss
of substantial picture quality. A full size NTSC 24 bit video test frame
is included.  Its a boring snapshot from a cheer commericial.  I figured
they wouldn't sue me.  It has been compressed to 45K from 900K.  The args
used for compression were "8 .2 8 .1 16 .05 16" (If this code comes in a
mail package the test frame will be not be in the final state. To get it
to its smallest size "compress frame", after extracting the tarfile)

[[Ed's Note: Place in archives - rest of readme follows.

FTP:	Hostname : titan.rice.edu (128.42.1.30)
	Directory: sun-source
	Filename : transform.tar.Z.uu

Archive Server Address: archive-server at rice.edu
Archive Server Command: send sun-source transform.tar.Z.uu

Unpack by (1) uudecode (2) uncompress (3) tar -xf. -bdg]]

If you just want to get started:
	make
	cat frame.Z | uncompress | transform >sunrasterfile

To compress your own frames
	cat sunrasterfile | transform "8 .25 8 .1 16 .1 16" | compress >foo

This code doesn't attempt to efficiently code the output coefficients,
it requires compress or pack to finish the job.

Here is a description of the input args for compression

	"N YT YQ IT IQ QT QQ"

	N -- is matrix size   8-32

Execution time increases in proportion to N^2 because simple matrix 
multiplication is used to compute the DCT.

YT -- is ratio of Y coefficients to keep 0-1.0
IT -- is ratio of I coefficients to keep 0-1.0
QT -- is ratio of Q coefficients to keep 0-1.0
YQ -- control the coarseness of Y quantization
IQ -- control the coarseness of I quantization
QQ -- control the coarseness of Q quantization

As you lower *T and raise *Q the compression rate goes up.
As you lower *T too low, your image will start to get blurry. 
As you raise *Q too high you will start noticing blockiness in the image.


OPERATION
----------
Compression is accomplished by first reading in the entire image into
memory. The image is compressed in YIQ space. The 3 three components are
handled in separate passes. The Y for the image is calculated. NbyN arrays
of pixel are filled and transformed. The Mean Square Values and Absolute
values of the transformed coefficients are calculated and kept around for
later. 

The number of coefficients to keep for Y is YT*N*N.  The largest MSV
values are found and the number of bytes to code each is found from the
Max Absolute values.  Bookkeeping info is written out, followed by the
coeffiecients.  Same for I & Q.

STANDARDS
---------
A standard for DCT image compression should be public this spring.
Created by the JPEG committee. It differs from this code in the way the
coefficients are quantized and packed. It also processes a block at a
time, so that large images can be processed. I'll put out an updated
version when the public draft is available.

PERFORMANCE
-----------
The current implementation uses floating point throughout. Some machines
would get a big gain from using fixed point. 

The convertion from RGB to YIQ could be implemented with integer math.

In an 8by8 DCT matrix, there are only 7 unique values if you discount 
the sign differences. Table lookups could be used instead of multiplications 
in the matrix multiplication.

There are faster ways to compute the DCT transform. 
	1. A Fast DCT can be calculated using FFT. 
	2. A WHT transform followed by a sparse matrix multiplication.


BOOKS
-----
Digital Pictures   Arun N. Netravali and Barry G. Haskell
	Great book on video compression.

Text Compression  Timothy C Bell, John G. Cleary, Ian H. Witten
	Good book on information theory and entropy encoding.

Greg Cockroft
Cockroft & Beach Computing
410 Riverside Court #105
Santa Clara, CA 95054
glc at frame.com