readme

这是TSVQ的经典实现

README File for indices_08_19_96
--------------------------------

The files in indices_08_19_96 plus Jill Goldschneider's
TSVQ code (*) will compile into a program called
mem_tsvqe. mem_tsvqe is based on tsvqe, which inputs a
sequence of data samples and a tsvq codebook, and
outputs codebook vectors that're close to the data
samples in a squared-error sense. It does not produce a
sequence of indices; it is not a compressor but a way
to examine the effects of lossy compression.

mem_tsvqe will either compress sampled data to produce
indices, or will decompress indices to produce a
reproduction of the data. The index sequence is
somewhat robust to channel errors, meaning that the
decoder should not lose its place in the sequence even
if the sequence gets corrupted a little. Unfortunately
the system is not as robust as I would like -- more
work is needed on this capability.

Another difference is that the routines that underlie
mem_tsvqe compress and decompress to and from memory,
as opposed to disk. This is a disadvantage if a lot of
data need to be processed, but it makes interfacing to
external I/O libraries (such as the one in Khoros)
possible. It also makes the resynchronization
capabilities described above easier to implement.

Further details about mem_tsvqe are given in Section I
below.  Instructions on how to make and test mem_tsvqe
are given in Section II. Section III contains the terms
under which this program may be used.

                              Marko Slyz
                              [e-mail]

(*) http://isdl.ee.washington.edu/COMPRESSION/homepage.html

------------------------------------------------------------
I. PROGRAM DESCRIPTIONS

 Name:   mem_tsvqe.c
 Date:   Jan. 31, 1996

 Marko Slyz created mem_tsvqe.c by modifying a version of tsvqe.c,
 which was written by Jill Goldschneider and last revised in February
 of 1994.

 SYNOPSIS
    mem_tsvqe -c codebook -i inputfile -o outputfile -R -D -m [C|D] -r #

 DESCRIPTION

    This program can be used to encode a blocked raw image using a
    tree-structured VQ. If the "-m C" switch is used, the inputs are the input
    image and the codebook. The output is a file containing a stream of
    indices that describe the image (the index file). If the "-m D" switch is
    used, the inputs are the index file and the codebook. The output is the
    decoded image.

    When the "-m C" switch is used there are three optional outputs.  A rate
    image can be created by using the -R flag, and the counts and distortions
    can be written using the -D flag. The counts and distortions file has the
    same format as the statistics file produced by tsvq.c. Finally "-r #",
    where # is a positive integer, determines the length of the restart
    intervals, with "-r 0" decreeing no restart markers whatsoever. See the
    comment at the beginning of mem_tsvqe_util.c for a complete explanation of
    restart intervals.

    The format of the codebook is:
        TYPE       SIZE          DESCRIPTION
        long       1             number of nodes in the tree (numnodes)
        integer    1             vector dimension (dim)
        short      numnodes      tree description array
        DISTTYPE   numnodes*dim  codewords
    The format of the tree description array is that a 1 is a node that
    is not a terminal node and a 0 is a terminal node. The array is a 
    preorder list.  In addition, mem_tsvqe prints the following information 
    to stdout: average rate per vector, average distortion per vector, 
    entropy of the vectors, and maximum codeword length.  Type "mem_tsvqe"
    to see default values.

 OPTIONS
    -c  codebook file                        DEF_codebookname
    -i  input image file                     DEF_inputname
    -o  output image file                    DEF_outputname
    -R  output a rate file                   DEF_ratename
    -D  output a stat file                   DEF_statname
    -m  mode = compress or decompress?       C
    -r  restart interval length              0


----------------------------------------


 Name:   mem_tsvqe_util.c
 Date:   Jan. 31, 1996

 Marko Slyz created mem_tsvqe_util.c by modifying a version of tsvqe_util.c,
 which was written by Jill Goldschneider and last revised in February 1994.

 The routines in mem_tsvqe_util have the following features:

 1) The encoder generates an actual compressed bit stream, which consists of
    indices. The decoder uses these indices to construct an approximation to
    the original data. Calling P2I_image_encode() and then feeding the
    resulting output to I2P_image_decode() should give the same result as a
    single call to tsvqe_util.c's image_encode().
 2) They compress and decompress to and from memory instead of disk.
 3) The encoder can insert restart markers in the output bit stream. Then, if
    that bit stream becomes corrupted, the decoder uses these restart markers
    to recover at least some of the original data.


    DESCRIPTION OF THE BASIC TECHNIQUE

    The restart marker scheme is similar to the one in the JPEG standard [1,
    Section 7.4]. Start by picking some natural number RI_len, then take the
    stream of (possibly variable-length) indices and put a marker after every
    RI_len of them. A marker consists of two bytes. The first is always
    7F. The second is a number that cycles through markers[] (which is defined
    in mem_bits.c). The entire first marker is (7F markers[1]), the
    (NUM_MARKERS-1)th is (7F markers[NUM_MARKERS - 1]) and the NUM_MARKERSth
    marker is (7F markers[1]) again.

    At the receiver, parse the data into segments delimited by markers. Each
    segment's marker determines the location in the image to begin placing the
    pixels corresponding to that segment's indices. This will work perfectly
    if the markers never get corrupted.

    One complication is that 7F's, which indicate markers, can also appear
    naturally in the bits composing the indices. This is bypassed by stuffing
    a 00 byte after each natural occurrence of 7F. The receiver will then need
    to remember that 7F 00 needs to be translated to just 7F before the
    decompressor sees it.

    WHAT HAPPENS WHEN SUBSTITUTION AND INSERTION/DELETION ERRORS OCCUR

    Unfortunately, the markers can get corrupted. One coping strategy is to
    remember the index (i.e. the position in markers[]) of the last decoded
    marker. Then look for the next marker whose index is greater. If its index
    isn't exactly one greater then the receiver knows that an error has been
    made, but for simplicity doesn't try to estimate the missing marker's
    location.

    With this strategy, if an error occurs in a marker then the entire segment
    corresponding to that marker is lost. Also, if an error occurs in the
    indices, then at most the rest of the segment is lost.

    COMPARISONS WITH EXISTING TECHNIQUES

    7F is used instead of the FF used in the JPEG scheme because, no matter
    what bits surround 7F, it is always possible to tell where the 7F
    starts. This is not true for FF; consider the bits stream "01" as an
    example. Suppose that an FF marker code was appended at the end of the bit
    stream to produce: "0111111111". The decoder would not be able to tell
    whether the marker begins at bit position 2 or 3, since FF's start at both
    positions.

    The rationale for using markers[] -- as opposed to the numbers from 1 to
    NUM_MARKERS-1 -- arises from choosing the codes in markers[] such that no
    single insertion, deletion or substitution error can create another valid
    entry in markers[]. So any single error in a marker will create an invalid
    codeword. This is useful since it's better to have a codeword that's known
    to be wrong than to have a codeword that's wrong but is thought to be ok;
    the latter can screw-up not just the current interval but the succeeding
    ones as well.

    The restart marker scheme used here is also similar to comma codes, which
    are discussed in, for example, [2, Section 12.5].


    REFERENCES

    [1] Pennebaker, Mitchell, _JPEG_Still_Image_Data_compression_Standard_,
        Van Nostrand Reinhold, New York, 1993.

    [2] J. Stiffler, "Theory of Synchronous Communication", Prentice-Hall,
        Englewood Cliffs, 1971.

------------------------------------------------------------


II. HOW TO MAKE AND TEST MEM_TSVQE

1) Get J.R. Goldschneider's tsvq and vq code from
      ftp://isdl.ee.washington.edu/pub/VQ/code/VQcode.tar.Z
  and extract it from its tar file.

2) Make the code in stdvq.

3) Assuming that indices_08_19_96 and tsvq are sibling
   directories, go to the tsvq directory and type:

	 cp node_util.c prune.c prune_util.c read_util.c select.c slope_util.c tsvq.c tsvq_util.c tsvqe.c tsvqe_util.c voronoi_ts.c voronoi_util.c write_util.c ../indices_08_19_96/
         cd ../indices_08_19_96/
         make

4) Now test it:

   FIRST CREATE A CODEBOOK (this assumes that stdvq/
      is a sibling of indices_08_19_96/ and that the
      headerless image lena is in indices_08_19_96/):
   %../stdvq/block -i lena -r 512 -l 512 -h 2 -w 2 -o training_data.TS
   %tsvq -t training_data.TS -c codebook -d 4 -r 8.0 -s stats

   OPTIONS   DESCRIPTIONS                         SETTINGS
   -t        blocked training sequence            training_data.TS
   -c        codebook                             codebook
   -s        codebook statistics                  stats
   -d        vector dimension                     4
   -r        stopping rate                        8
   -m        multiplicative offset                0.01
   -h        convergence threshold                0
	     number of training vectors           65536

	      RATE          DISTORTION
	  0.000000         6892.439899
	  1.000000         2107.234555
	  1.389694         1479.296612
	  2.000000          632.053132
		    .....
	  7.989685           33.383129
	  7.989716           33.380520
	  7.989792           33.378260
	  8.000000           33.251329

   The number of nodes is 6855
   The empirical entropy is 6.883374

   %prune -c codebook -s stats -o nested > list_of_subtrees
   %select -c codebook -s nested -n 1463 -o codebook.1463

   OPTIONS   DESCRIPTIONS                       SETTINGS
   -c        codebook file                      codebook
   -s        nested subtree file                nested
   -n        subtree number                     1463
   -o        output codebook file               codebook.1463
	     number of nodes                    143


   SIMULATE THE EFFECTS OF COMPRESSING THE DATA WITHOUT
   PRODUCING AN INDEX STREAM:
   %tsvqe -c codebook.1463 -i training_data.TS -o lena.TS.encoded_tsvq -R

   Codebook file:             codebook.1463
   Vector dimension:          4
   Number of Nodes:           143
   Image to encode:           training_data.TS
   Encoded file:              lena.TS.encoded_tsvq
   Number of pixels encoded:  262144
   Average rate:              3.992752
   Empirical entropy:         3.825776
   Average distortion:        160.804966
   Maximum codeword length:   14
   Rate file:                 rate.dat

   NOW SEE IF THE SAME THING RESULTS IF ONE FIRST COMPRESSES
   THE DATA TO AN INDEX STREAM....
   %mem_tsvqe -m C -c codebook.1463 -i training_data.TS -o lena.TS.encoded_mem -R

   Codebook file:             codebook.1463
   Vector dimension:          4
   Number of Nodes:           143
   Image to encode:           training_data.TS
   Encoded file:              lena.TS.encoded_mem
   Number of pixels encoded:  262144
   Average rate (in bpp):     0.998188
   Empirical entropy:         3.825776
   Average distortion:        160.804966
   Maximum codeword length:   14
   Rate file:                 rate.dat

   ....AND THEN DECOMPRESSES IT:
   %mem_tsvqe -m D -c codebook.1463 -i lena.TS.encoded_mem -o lena.TS.unencoded_mem
   %cmp -l lena.TS.encoded_tsvq lena.TS.unencoded_mem

   REPEAT THE SAME EXPERIMENT BUT WITH RESTART MARKERS:
   %mem_tsvqe -m C -c codebook.1463 -i training_data.TS -o lena.TS.encoded_mem -R -r 10

   Codebook file:             codebook.1463
   Vector dimension:          4
   Number of Nodes:           143
   Image to encode:           training_data.TS
   Encoded file:              lena.TS.encoded_mem
   Number of pixels encoded:  262144
   Average rate (in bpp):     1.410297
   Empirical entropy:         3.825776
   Average distortion:        160.804966
   Maximum codeword length:   14
   Rate file:                 rate.dat

   %mem_tsvqe -m D -c codebook.1463 -i lena.TS.encoded_mem -o lena.TS.unencoded_mem
   %cmp -l lena.TS.encoded_tsvq lena.TS.unencoded_mem

------------------------------------------------------------

III.  LICENSE NOTICE AND DISCLAIMER

    This is a modified version of software provided by Jill
    Goldschneider at the University of Washington Data Compression
    Lab. The modifications were made by the

	   Environmental Research Institute of Michigan
	   1975 Green Road
	   Ann Arbor, Michigan 48107
	   Telephone: [phone]

    under U.S. gov't contract DLA900-88-D-0392.

    There is no warranty, either express or implied, for these
    modifications and documentation, including, without limitation,
    warranty of merchantibility and warranty of fitness for a 
    particular purpose.

    These modifications may be used for any non-commercial
    purpose, such as research, provided this notice is kept
    intact.

----------------------------------------