mem_tsvqe.c

这是TSVQ的经典实现

static char license[16][70] = {
    "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. government 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."
};

/******************************************************************************

 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 1994.

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

 DESCRIPTION

    This program should 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, tsvqe prints the following information 
    to stdout: average rate per vector, average distortion per vector, 
    entropy of the vectors, and maximum codeword length.  Type "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

 CALLS
    create_root(), construct_tree(), P2I_image_encode(), I2P_image_decode(),
    write_stat(), empirical_entropy()

****************************************************************************/
#include <sys/types.h>		/* these two are for the "stat()" function */
#include <sys/stat.h>
#include <limits.h>
#include <assert.h>
#include "protect.h"
#include "tsvq.h"

FILE *inputfile;
FILE *outputfile;
FILE *ratefile;

char inputname[NAME_MAX];
char outputname[NAME_MAX];
char ratename[NAME_MAX];

char *programname;
int  dim;

BOOLEAN  printrate;

/* ---------------------------------------- */

#if 0
static int pt_node_count;

static void print_tree0(TreeNode *node)
{
  int i;

  if (node == 0)
    return;

  printf("%d: ", pt_node_count++);
  for (i = 0; i < dim; i++)
    printf("%g ", node->data[i]);
  printf("\n");

  print_tree0(node->right_child);
  print_tree0(node->left_child);
}

static void print_tree(TreeNode *node)
{
  pt_node_count = 0;
  print_tree0(node);
}
#endif

/* ---------------------------------------- */

int main(argc, argv)
     int argc;
     char *argv[];
{
  TreeNode  *root;      /* root of the codebook tree */
  char      *cp;        /* character pointer */
  char      option;     /* used for command line interpretation */
  char      codebookname[NAME_MAX];
  char      statname[NAME_MAX];
  FILE      *codebookfile;          
  FILE      *statfile;          
  long      numnodes;   /* number of nodes in the tree */
  long      bits;       /* total number of bits used to encode image */
  int       maxbits;    /* length of the longest index used to encode image */
  long      numpixels;  /* the number of pixels encoded */
  DISTTYPE  rate,distortion; /* encoding rate and distortion (squared error) */
  double    entropy;    /* empirical entropy */
  BOOLEAN   statflag;   /* flag to create a statistics file */
  char      mode;	/* how input is transformed to create output */
  int       num_in;     /* the number of vectors in the input file */
  DATATYPE  *image_vectors;  /* (image_vectors + i*dim) points to the ith
				vector */
  uchar     *rate_image;   /* rate_image[i] is the length of the ith index */
  uchar     *code_bits;    /* pointer to the encoded image */
  int       RI_len;	   /* the length of a restart interval */

  
  /* assign default values */
  strcpy(codebookname, DEF_codebookname);
  strcpy(inputname, DEF_inputname);
  strcpy(outputname, DEF_outputname);
  strcpy(ratename, DEF_ratename);
  strcpy(statname, DEF_statname);
  
  dim = DEF_dim;
  programname = *argv;
  printrate = FALSE;
  statflag = FALSE;
  mode = DEF_mode;
  RI_len = 0;
  
  /* if no options entered, list all of the defaults */
  if (argc == 1) {
    printf("%s %s %s\n",USAGE,programname,HOWTOUSE_TSVQE);
    printf("\nOPTIONS   DESCRIPTIONS                         DEFAULTS\n");
    printf("-c        codebook                             %s\n",codebookname);
    printf("-i        input data file                      %s\n",inputname);
    printf("-o        output data file                     %s\n",outputname);
    printf("-R        output a rate file\n");
    printf("-D        output a count and distortion file\n");
    printf("-m        mode = compress or decompress?       C\n");
    printf("-r        restart interval length              %d\n", RI_len);
    printf("\n");
    fflush(stdout);
    exit(0);
  }

  /* read and interpret command line arguments */
  while (--argc && ++argv) {
    if (*argv[0]=='-' && strlen(*argv)==2) { /* each option has 1 letter */
      option = *++argv[0];
      if (option == 'R') {printrate = TRUE;}     /* examine the flag */
      else if (option == 'D') {statflag = TRUE;} /* examine the flag */
      else if (--argc && ++argv) {               /* examine the option */
        switch(option) {                         /* examine the option letter*/
        case 'c':
          strncpy(codebookname,*argv,NAME_MAX);
          break;
        case 'i':
          strncpy(inputname,*argv,NAME_MAX);
          break;
        case 'o':
          strncpy(outputname,*argv,NAME_MAX);
          break;
	case 'm':		/* D = decompression, C = compression */
	  if (**argv == 'D' || **argv == 'C')
	    mode = **argv;
	  else {
	    fprintf(stderr,"%s: %c: %s\n",programname,**argv,INVALID_PARAM);
	    exit(1);
	  }
	  break;
	case 'r':
	  RI_len = atoi(*argv);
	  break;
        default:
          fprintf(stderr,"%s: %c: %s\n",programname,option,NOTOPTION);
          exit(1);
          break;
        }
      }
      else {
        fprintf(stderr,"%s %s %s\n",USAGE,programname,HOWTOUSE_TSVQE);
        exit(2);
      }
    }

    else if (*argv[0] == '-') { /* user entered unknown option */
      ++argv[0];
      fprintf(stderr,"%s: %s: %s\n",programname,*argv,NOTOPTION);
      exit(3);
    }
    else { /* user entered unknown string */
      fprintf(stderr,"%s: %s: %s\n",programname,*argv,NOTOPTION);
      exit(4);
    }
  }
  
  /* user did not enter an input file name */
  if (strlen(codebookname) == 0 || strlen(inputname) == 0) {
    fprintf(stderr,"%s %s %s\n",USAGE,programname,HOWTOUSE_TSVQE);
    exit(5);
  }
  
  /* user entered an input name which is the same as the output name */
  if (strncmp(cp = codebookname,outputname,NAME_MAX) == 0 ||
      strncmp(cp = inputname,outputname,NAME_MAX) == 0) {
    fprintf(stderr,"%s: %s %s %s %s: %s\n",
	    programname,cp,AND,outputname,ARESAME,ABORT_TSVQE);
    exit(6);
  }
  
  /* user entered the same input names */
  if (strncmp(inputname,codebookname,NAME_MAX) == 0) {
    fprintf(stderr,"%s: %s %s %s %s: %s\n",
	    programname,inputname,AND,codebookname,ARESAME,ABORT_TSVQE);
    exit(7);
  }
  
  /* assign the default output names if necessary */
  if (strlen(outputname) == 0) {
    sprintf(outputname,"%s%s",inputname,DEF_APPEND_TSVQ);
  }
  
  /*  open the files */
  if(!(codebookfile = fopen(cp = codebookname,"r")) ||
     !(inputfile = fopen(cp = inputname,"r")) ||
     !(outputfile = fopen(cp = outputname, "w"))) {
    fprintf(stderr,"%s: %s: %s\n",programname,cp,NOTFOUND);
    exit(8);
  }
    
  if (printrate) {
    if(!(ratefile = fopen(cp = ratename,"w"))) {
      fprintf(stderr,"%s: %s: %s\n",programname,cp,NOTFOUND);
      exit(9);
    }
  }

  /* find the number of nodes */
  if (fread((char *) &numnodes,sizeof(long),1,codebookfile) != 1) {
    fprintf(stderr,"%s: %s: %s\n",programname,codebookname,NOREAD);
    exit(10);
  }

  /* find the dimension */
  if (fread((char *) &dim,sizeof(int),1,codebookfile) != 1) {
    fprintf(stderr,"%s: %s: %s\n",programname,codebookname,NOREAD);
    exit(11);
  }

  /* construct the tree */
  if(!(root = create_root())) {
    exit(12);
  }
  if(!construct_tree(root,numnodes,codebookfile,codebookname)) {
    exit(13);
  }

/*  print_tree(root); */
  
  fclose(codebookfile);


  /* Compress the image: */
  if (mode == 'C') {
    struct stat buf;

    /* Get the image size and check it: */
    if (stat(inputname, &buf) != 0)
      pr_error("having touble reading inputname");
    num_in = buf.st_size/(dim*sizeof(DATATYPE));
    if(num_in*(dim*sizeof(DATATYPE)) != buf.st_size)
      pr_error("the input file must have an integer number of vectors");

    /* Get room to hold it and then read it in: */
    image_vectors = pr_alloc(buf.st_size, NOF);
    pr_fread((void *)image_vectors, sizeof(char), buf.st_size, inputfile);

    rate_image = pr_alloc(num_in*sizeof(uchar), NOF);

    distortion = P2I_image_encode(root, &bits, &maxbits, &numpixels,
				  image_vectors, &code_bits, num_in,
				  rate_image, RI_len);
    if(numpixels == 0) {
      fprintf(stderr,"%s: %s: %s\n",programname,inputname,NODATA);
      exit(15);
    }
    assert(distortion >= 0.0);
    
    /* Save the output and the rates: */
    pr_fwrite((void *)&num_in, sizeof(int), 1, outputfile);
    pr_fwrite((void *)&bits,   sizeof(int), 1, outputfile);
    pr_fwrite((void *)&dim,    sizeof(int), 1, outputfile);
    pr_fwrite((void *)&RI_len, sizeof(int), 1, outputfile);
    pr_fwrite((void *)code_bits,  sizeof(uchar),
	      (size_t)ceil((double)bits/CHAR_BIT),  outputfile);
    if (printrate) pr_fwrite((void *)rate_image, sizeof(uchar), num_in,
			     ratefile);
    free(rate_image);
  } else {
    /* Get the input data: */
    pr_fread((void *)&num_in, sizeof(int), 1, inputfile);
    pr_fread((void *)&bits,   sizeof(int), 1, inputfile);
    pr_fread((void *)&dim,    sizeof(int), 1, inputfile);
    pr_fread((void *)&RI_len, sizeof(int), 1, inputfile);
    code_bits = pr_alloc(sizeof(uchar) * ceil((double)bits/CHAR_BIT), NOF);
    pr_fread((void *)code_bits,  sizeof(uchar),
	     (size_t)ceil((double)bits/CHAR_BIT),  inputfile);

    image_vectors = I2P_image_decode(root, code_bits, num_in, RI_len, bits);

    /* Save the output. */
    pr_fwrite((void *)image_vectors, sizeof(DATATYPE), dim * num_in,
	      outputfile);
  }
  free(code_bits);
  free(image_vectors);


  if (mode == 'C') {
    /* write the counts and distortion if requested */
    if (statflag) {
      /* assign the default output names if necessary */
      if (strlen(statname) == 0) {
	sprintf(statname,"%s%s",outputname,DEF_APPEND_STAT);
      }
      if(!(statfile = fopen(cp = statname,"w"))) {
	fprintf(stderr,"%s: %s: %s\n",programname,cp,NOTFOUND);
	exit(16);
      }
      if(!(write_stat(root,numnodes,statfile,statname))) {
	exit(17);
      }
    }

    /* compute the distortion and rate */
    distortion /= ((DISTTYPE) numpixels / dim);
    /* Originally rate also had  "/ dim" tacked on at the end of it. */
    rate = (DISTTYPE) bits / (DISTTYPE) numpixels;
    if( (entropy = empirical_entropy(root,numnodes)) < 0) {
      exit(18);
    }

    /* output statistics */
    printf("\n");
    printf("Codebook file:             %s\n", codebookname);
    printf("Vector dimension:          %d\n",dim);
    printf("Number of Nodes:           %ld\n",numnodes);
    printf("Image to encode:           %s\n", inputname);
    printf("Encoded file:              %s\n", outputname);
    printf("Number of pixels encoded:  %ld\n",numpixels);
    printf("Average rate (in bpp):     %f\n",rate);
    printf("Empirical entropy:         %f\n",entropy);
    printf("Average distortion:        %f\n",distortion);
    printf("Maximum codeword length:   %d\n",maxbits);
    if(printrate) {
      printf("Rate file:                 %s\n",ratename);
    }
    if(statflag) {
      printf("Statistics file:           %s\n",statname);
    }
    printf("\n");

    if (printrate) CLOSE(ratefile);
  }
  CLOSE(inputfile);
  CLOSE(outputfile);

  exit(0);
}