Class DCT

Class DCT 

java.lang.Object
   |
   +----DCT
public class DCT
extends Object

DCT - A Java implementation of the Discreet Cosine Transform



The discreet cosine transform converts spatial information to "frequency" or spectral information, with the X and Y axes representing frequencies of the signal in different dimensions. This allows for "lossy" compression of image data by determining which information can be thrown away without compromising the image.

The DCT is used in many compression and transmission codecs, such as JPEG, MPEG and others. The pixels when transformed are arraged from the most signifigant pixel to the least signifigant pixel. The DCT functions themselves are lossless. Pixel loss occurs when the least signifigant pixels are quantitized to 0.

This is NOT a JPEG or JFIF compliant implementation however it could be with very little extra work. (i.e. A huffman encoding stage needs to be added.) I am making this source availible in the hopes that someone will add this functionality to the class, if you do, please email me! As always, if you have any problems feel free to contact me. (Or comments, or praise, etc..)

Keep in mind that when compressing color images with this, you will need to break the image up into it's R G B components and preform the calculations three times!!

A general algorithim for DCT compression with this class:

1) Create a DCT Object.
2) Set up your program to read pixel information in 8*8 blocks. See example.
3) Run the forwardDCT() on all blocks.
4) Run the quantitizeImage() on all blocks.
5) If you want, send the information to the imageCompressor().

A general algorithim for DCT decompression with this class:

1) Create a DCT Object.
2) Set up the program to convert compressed data in 8*8 blocks. (if compressed)
3) Run the data through dequantitizeImage().
4) Run the data through inverseDCT().


A complete implementation of an image compressor which compares the quality of the two images is also availible. See the JEncode/Decode source code. The DCT.java source code is also availible. The implementation is also handy for seeing how to break the image down, read in 8x8 blocks, and reconstruct it. The sample graphic is handy to have too. (Bad pic of me) The best way to get ahold of me is through my homepage. There's lots of goodies there too.

Note: You need GrafixTools compiled to use the JEncoder.java file. !! GrafixTools is a collection of handy graphics algos I keep around.
Version:
1.0.1 August 22nd 1996
1.0.2 January 5th 2004 - Removed deprecated API, fixed size bug.
Author:
Stephen Manley - smanley@nyx.net

Variable Index

o c
Cosine matrix.
o COLS
Image height - must correspond to imageArray bounds - default 200
o cT
Transformed cosine matrix, N*N.
o N
DCT Block Size - default 8
o QUALITY
Image Quality (0-25) - default 25 (worst image / best compression)
o quantum
Quantitization Matrix.
o resultDCT
DCT Result Matrix
o ROWS
Image width - must correspond to imageArray bounds - default 320
o zigZag
The ZigZag matrix.

Constructor Index

o DCT(int)
Constructs a new DCT object.

Method Index

o compressImage(int[], boolean)


This does not huffman code, it uses a minimal run-length encoding scheme.
o decompressImage(int[], boolean)
This method determines the runs in the input data, decodes it and then returnss the corrected matrix.
o dequantitizeImage(int[][], boolean)
This method reads in DCT codes dequanitizes them and places them in the correct location.
o forwardDCT(char[][])
This method preforms a matrix multiplication of the input pixel data matrix by the transposed cosine matrix and store the result in a temporary N * N matrix.
o inverseDCT(int[][])
This method is preformed using the reverse of the operations preformed in the DCT.
o quantitizeImage(int[][], boolean)
This method orders the DCT result matrix into a zigzag pattern and then quantitizes the data.

Variables

o N 
  public int N
DCT Block Size - default 8
o QUALITY 
  public int QUALITY
Image Quality (0-25) - default 25 (worst image / best compression)
o ROWS 
  public int ROWS
Image width - must correspond to imageArray bounds - default 320
o COLS 
  public int COLS
Image height - must correspond to imageArray bounds - default 200
o zigZag 
  public int zigZag[][]
The ZigZag matrix.
o c 
  public double c[][]
Cosine matrix. N * N.
o cT 
  public double cT[][]
Transformed cosine matrix, N*N.
o quantum 
  public int quantum[][]
Quantitization Matrix.
o resultDCT 
  public int resultDCT[][]
DCT Result Matrix

Constructors

o DCT 
  public DCT(int QUALITY)
Constructs a new DCT object. Initializes the cosine transform matrix these are used when computing the DCT and it's inverse. This also initializes the run length counters and the ZigZag sequence. Note that the image quality can be worse than 25 however the image will be extemely pixelated, usually to a block size of N.
Parameters:
QUALITY - The quality of the image (0 best - 25 worst)

Methods

o forwardDCT 
  public int[][] forwardDCT(char input[][])
This method preforms a matrix multiplication of the input pixel data matrix by the transposed cosine matrix and store the result in a temporary N * N matrix. This N * N matrix is then multiplied by the cosine matrix and the result is stored in the output matrix.
Parameters:
input - The Input Pixel Matrix
Returns:
s output The DCT Result Matrix
o dequantitizeImage 
  public int[][] dequantitizeImage(int inputData[][],
                                   boolean zigzag)
This method reads in DCT codes dequanitizes them and places them in the correct location. The codes are stored in the zigzag format so they need to be redirected to a N * N block through simple table lookup. After dequantitization the data needs to be run through an inverse DCT.
Parameters:
inputData - 8x8 Array of quantitized image data
zigzag - Boolean switch to enable/disable zigzag path.
Returns:
s outputData A N * N array of de-quantitized data
o quantitizeImage 
  public int[][] quantitizeImage(int inputData[][],
                                 boolean zigzag)
This method orders the DCT result matrix into a zigzag pattern and then quantitizes the data. The quantitized value is rounded to the nearest integer. Pixels which round or divide to zero are the loss associated with quantitizing the image. These pixels do not display in the AWT. (null) Long runs of zeros and the small ints produced through this technique are responsible for the small image sizes. For block sizes < or > 8, disable the zigzag optimization. If zigzag is disabled on encode it must be disabled on decode as well.
Parameters:
inputData - 8x8 array of DCT image data.
zigzag - Boolean switch to enable/disable zigzag path.
Returns:
s outputData The quantitized output data
o compressImage 
  public int[] compressImage(int QDCT[],
                             boolean log)


This does not huffman code, it uses a minimal run-length encoding scheme. Huffman, Adaptive Huffman or arithmetic encoding will give much better preformance. The information accepted is quantitized DCT data. The output array should be scanned to determine where the end is.
Parameters:
image - Quantitized image data.
Returns:
s The string representation of the image. (Compressed)
o decompressImage 
  public int[] decompressImage(int DCT[],
                               boolean log)
This method determines the runs in the input data, decodes it and then returnss the corrected matrix. It is used to decode the data from the compressImage method. Huffman encoding, Adaptive Huffman or Arithmetic will give much better compression.
Parameters:
DCT - Compressed DCT int array (Expands to whole image).
Returns:
s The decompressed one dimensional array.
o inverseDCT 
  public int[][] inverseDCT(int input[][])
This method is preformed using the reverse of the operations preformed in the DCT. This restores a N * N input block to the corresponding output block with values scaled to 0 to 255 and then stored in the input block of pixels.
Parameters:
input - N * N input block
Returns:
s output The pixel array output