Basant Kumar Dwivedi and Anup Gangwar
(2000RCS004 & 2000RCS005)
Department of Computer Science and Engineering, IIT Delhi


  • We have developed the tool primarily in C++. The compiler used was gcc-2.95.3. The only interface to ImageMagick has been tested on ImageMagick Vercion-5.2.7, this has been written in C. The segmentation part has been written entirely in Java. It is upwards compatible with Sun JDK1.2. A README for the tools can be found here.

Our work at a glance


Introduction :
Image compression is an important problem in image processing. The image compression methods can be broadly divided into lossy and lossless types. However it is widely accepted that lossless image compression methods donot lead to very good compression, but are unavoidable for certain types of images. The present work focussed on implementing a new lossless image compression technique using a mixture of segmentation, predictive and huffman coding.


Motivation :
A large number of images can be divided into very few number of segments within which the pixels have similar properties. However traditional methods rely on global properties. The idea here is to capture the uniformity within a segment. If somehow it is possible to represent a segment using very little overhead (in terms of image size) this similarity within a segment can be efficiently utilized for image compression.


Problem Breakup :
On both the encoder as well as the decoder side the problems which need to be addressed are as follows,

  1. Image Segmentation : The entire image needs to be subdivided into a number of segments. We use a simple region growing algorithm for this. Since it is not possible to non-interactively segment an image efficiently we have developed a Java GUI to do the task interactively. The Java GUI outputs a data file containing a list of pixels along with their greyscale values and segment numbers. As it is not possible to entirely segment an image interactively, we assign the pixels which have remained after interactive segmentation to a new segment. This segment also included the boundary of the image.
     
  2. Region Representation :A number of techniques could be used for region representation. Our C++ class hierarchy reflects this by abstracting out the interface to the various representation techniques. We have used contours represented using chain codes to demostrate the usability of this method of image compression. However chain coding is very susceptible to noise and this creates a lot of problems. Another potential source of trouble apart from noise is the arbitrary shapes which a contour might take. A segment will not always be convex shaped, this questions ones ability to appropriately form a region without looking ahead at a number of pixels. We have partially solved this problem by using two heuristics.
     
    1. We include a new point in the chain code only if it does not lie inside the region. This can be checked very simply looking at the 8-neighbors of a pixel. If even one of them belongs to a different segment we are sure that this does not lie completely inside a region.
    2. Out of a set of possible moves we choose only that which maximizes the angle between previous and current direction of movements measure counter-clockwise from the current direction of motion.
    We would however like to point out that our heuristics occassionally fail and we are unable to form a contour even after walking for the entire size of image.
     
  3. Lossless Predictive Coding : We exploit the property of uniformity within a segment by using lossless predictive coding for pixel data within a segment. Since difference in the pixel intensities are within a certain threshold and this happens for all the segment, we expect small size of Huffman coding table and corresponding code sizes for symbol encoding.
     
  4. Huffman Coding : We use Huffman variable length encoding for symbol encoding. The Huffman table is dynamically computed using the chain code and predictive coded values for the entire image.

Encoding and Decoding :
  • ENCODING
    1. Values of predictive coeff. No. = m = 3
    2. Push special value -511 (Start Code for Contour) in vect.
    3. Push the chain code values in a vector.
    4. Push special value -512 (Start Code for Data)
    5. Pass raster values for each region as int *.
    6. Push the returned values returned by predictive skipping *m* in vect. also save these values.
    7. Repeat the steps 2 - 6 for each region
    8. Create int * from vect
    9. Pass int 8 to Huff constructor -->>BitStream filling starts here
    10. Append the image size and the *3* float coeff. values using union in BitStream.
    11. Append the size of HuffTable first. Append HuffTable calculated, in BitStream.
    12. Parse Huff Table and get code-values for and
    13. Append in BitStream
    14. Append the start coordinates (2 values) in BitStream.
    15. Create an int * using and pass to the HuffCodec.
    16. Append the Huff codes found for in BitStream.
    17. Append in BitStream.
    18. Append the first 3 rasterized values in BitStream.
    19. Create an int * from the values.
    20. Append the in Bitstream.
    21. Repeat for all regions.

     
  • DECODING
    1. Read the image size and the three floats using union.
    2. Read the size of the HuffTable SHORT.
    3. Iterate the above number of times and read the three values of the Huffman table, obtain SCC code and SCD code size.
    4. Set region count = 0. Start iteration.
    5. Get code SCC.
    6. Get the two start coordinates (short).
    7. Feed the full BitStream to the decoder and get the set of contour symbols.
    8. getCode( SCD ) and assert that it is indeed correct.
    9. getCode( ) three unsigned chars, these are the first three values for the predictor.
    10. Feed the full BitStream to the decoder and obtain rest of the data.
    11. Feed the data to the predictive decoder including the first three and obtain the decoded values.
    12. Copy the chain code and predictor values to the appropriate vectors.
    13. Create a new representation obj and append to repres.
    14. Increment region_count.
    15. Repeat 4-12 till BitStream is finished.

 

Implementation Details :
The entire tool set basically has three parts. The part which does image segmentation, this has been written in Java mainly to support GUI and keep the thing simple. The second part is our main module which we refer to as SEBIC (Segmentation Based Image Compression). This has been written entirely in C++ with a very keen eye on portability and flexibility for experimentation. We have abstracted out the interfaces to all the important modules using abstract classes. This removes any presumptions on the part of other modules about a particular implementation. For example it is very simple to plug out the current representation technique and plug in a new representation technique by simply implementing all the virtual methods of the SebicAbstractRepres class. We have also put considerable effort on the coding style involved. The full design documentation is generated automatically using Doxygen. This tool creates a browsable html hierarchy of files. The Java documentation has also been automatically generated using JavaDoc. Finally we have written a converter in C which takes the output uncompressed data file generated by SEBIC and creates the image.

 
  Results


Input ImageJPEGGIFSEBIC
Input Image (8x8) 220 Bytes 903 Bytes 24 Bytes (Output Image)
Input Image (51x46) 674 Bytes 181 Bytes 334 Bytes (Output Image)
Input Image (189x69) 1643 Bytes 11869 Bytes 2072 Bytes (Output Image)

 
  Acknowledgements



We acknowlege the time, effort and ideas of Subhajit Sanyal and S. Nachiappan without whom we could not have accomplished the above. We would also like to thank S. Nachiappan for integrating his Huffman tree code generator in SEBIC.
 
 
 


Last Updated November 19, 2001 Basant Kumar Dwivedi & AnupGangwar