wpt_util.c

Vector Quantization压缩算法

/******************************************************************************
 *
 * Copyright Jill R. Goldschneider, 1998
 *
 * This work was partially supported by a NASA Graduate Student
 * Fellowship in Global Change Research, an NSF Young Investigator Award,
 * and U.~S. Army Research Grant DAAH004-96-1-0255.
 *
 *****************************************************************************/

/******************************************************************************
 *
 * FILE          wpt_util.c
 * AUTHOR        Jill R. Goldschneider
 * DATE          February 1997
 * REVISIONS     February 1998 - update documentation
 * DESCRIPTION   WPT tree construction functions
 *               BOOLEAN  construct_tree(TreeNode *node, char *codebookname)
 *               void     map_tree(TreeNode *node, FILE *outputfile,
 *                                 char *codebookname)
 *               void     encode_tree(TreeNode *node, FILE *outputfile,
 *                                    char *codebookname)
 *               void unblock_tree(TreeNode *node, FILE *outputfile)
 *               void rebuild_tree(TreeNode *node, FILE *outputfile)
 *
 *****************************************************************************/
#include "wpt.h"

static BOOLEAN read_data(TreeNode *node, char *codebookname);

/******************************************************************************
 * DOCUMENTATION ********************************************************
 ******************************************************************************
   NAME construct_tree

   DESCRIPTION This routine creates the data structure needed for WPT
   systematic joint best-basis selection and optimal bit allocation.
   It also inserts all of the PTSVQ data into the structure.

   ARGUMENTS
      IOARG node           the root of the tree
      IARG  codebookname   the prefix name of the files for each node

   RETURN If successful construct_tree returns TRUE.  If unable to
   allocated memory for the quantizer data or for the WPT tree
   structure, it returns FALSE.

   ALGORITHM For each node in the tree (simple recursion), the
   contents of the file called codebookname are inserted into the data
   structure in node$\rightarrow$data.  A call to read_data does the
   actual data processing.

   NOTE The codebook file names should be
   codebookfilename.$i$.$j$.$k$...  where codebookfilename is used for
   the 0 level codebook, and $i$ is the $i$th subband of the
   decomposition of the original data, and $j$ is the $j$th subband of
   the decomposition of the $i$th subband, and so on.

   AUTHOR Jill R. Goldschneider

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

BOOLEAN construct_tree(TreeNode *node, char *codebookname)
{
  char    tempname[NAME_MAX + 10]; /* current codebook name */
  int     i;            /* counter */

  /* load the data into the node */
  if (!(read_data(node, codebookname))) return(FALSE);

  /* If not at bottom of tree, continue growing */
  if (node->depth < treelevel) {
    if (!(node->child = (TreeNode **) calloc(treedim, sizeof(TreeNode *)))) {
      fprintf(stderr, "%s: %s\n", programname, NOMEMORY);
      return(FALSE);
    }

    for (i = 0; i < treedim; i++) {
      if (!(node->child[i] = newchild(node, (i+1)))) {
	fprintf(stderr, "%s: %s\n", programname, NOMEMORY);
	return(FALSE);
      }
      sprintf(tempname, "%s.%d", codebookname, (i+1));
      if (!(construct_tree(node->child[i], tempname))) {
	return(FALSE);
      }
    }
  }
  return(TRUE);
}

/******************************************************************************
 * DOCUMENTATION ********************************************************
 ******************************************************************************
   NAME read_data

   DESCRIPTION This will read the ascii output of the prune program from
   the tsvq code.

   ARGUMENTS
      IOARG node           the node to initialize
      IARG  codebookname   the name of the file associated with the node

   RETURN If successful read_data returns TRUE.  If unable to
   allocated memory, it returns FALSE.

   ALGORITHM

   AUTHOR Jill R. Goldschneider

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

static BOOLEAN read_data(TreeNode *node, char *codebookname)
{
  FILE        *codebookfile;
  SubtreeList *current_element, *new_element;
  int         vq_dim;      /* dimension of VQ */
  int         scale;       /* scaling factor */
  int         i;
  char        cp[200], cp0[100], cp1[100], cp2[100], cp3[100], cp4[100];

  /* open file */
  if (!(codebookfile = fopen(codebookname, "r"))) {
    fprintf(stderr, "%s: %s: %s\n", programname, codebookname, NOTFOUND);
    return(FALSE);
  }

  if (!(node->data = (SubtreeList *) calloc(1, sizeof(SubtreeList)))) {
    fprintf(stderr, "%s: %s\n", programname, NOMEMORY);
    return(FALSE);
  }

  if (!(current_element = (SubtreeList *) calloc(1, sizeof(SubtreeList)))) {
    fprintf(stderr, "%s: %s\n", programname, NOMEMORY);
    return(FALSE);
  }
  current_element->next = NULL;
  node->data = current_element;

  /* read in first lines  and get vector dimension */
  rewind(codebookfile);
  for (i = 0; i < 8; i++) {
    if (!(fgets(cp, sizeof(cp), codebookfile))) {
      fprintf(stderr, "%s: %s: %s\n", programname, codebookname, NOREAD);
      return(FALSE);
    }
  }
  /* read dimension data */
  sscanf(cp, "%s %s %s\n", cp0, cp1, cp2);
  vq_dim = atoi(cp2);
  scale = (int) pow((double) treedim, (double) node->depth) * vq_dim;

  /* pass over last unneeded lines */
  for (i = 0; i < 2; i++) {
    if (!(fgets(cp, sizeof(cp), codebookfile))) {
      fprintf(stderr, "%s: %s: %s\n", programname, codebookname, NOREAD);
      return(FALSE);
    }
  }

  /* test read routine
  printf("file = %s, vector dimension = %d, scale = %d \n",
	 codebookname, vq_dim, scale); */

  /* read data into first node, assumes GBFOS nodes only */
  if (!(fgets(cp, sizeof(cp), codebookfile))) {
    fprintf(stderr, "%s: %s: %s\n", programname, codebookname, NOREAD);
    return(FALSE);
  }
  sscanf(cp, "%s %s %s %s %s\n", cp0, cp1, cp2, cp3, cp4);
  /* make the proper adjustment to lambda, rate, and distortion */
  current_element->subtree_number = atoi(cp0);
  current_element->lambda = atof(cp1);
  current_element->rate = atof(cp2);
  current_element->distortion = atof(cp3);
  current_element->nodes = atoi(cp4);

  /* test read routine
  printf("  %7d %15f %15f %15f %7d\n", current_element->subtree_number,
	 current_element->lambda, current_element->rate,
	 current_element->distortion, current_element->nodes); */

  /* make proper adjustment to rate and distortion */
  if (current_element->rate < 0.0) current_element->rate = 0.0;
  if (current_element->distortion < 0.0) current_element->distortion = 0.0;
  /* get rate and distortion in bpp */
  current_element->rate /= scale;
  current_element->distortion /= scale;

  /* read data into the rest of the nodes */
  while (fgets(cp, sizeof(cp), codebookfile)) {

    /* add a node to the list */
    if (!(new_element = (SubtreeList *) calloc(1, sizeof(SubtreeList)))) {
      fprintf(stderr, "%s: %s\n", programname, NOMEMORY);
      return(FALSE);
    }
    current_element->next = new_element;
    current_element = new_element;

    sscanf(cp, "%s %s %s %s %s\n", cp0, cp1, cp2, cp3, cp4);
    /* make the proper adjustment to lambda, rate, and distortion */
    current_element->subtree_number = atoi(cp0);
    current_element->lambda = atof(cp1);
    current_element->rate = atof(cp2);
    current_element->distortion = atof(cp3);
    current_element->nodes = atoi(cp4);

    /* test read routine
    printf("  %7d %15f %15f %15f %7d\n", current_element->subtree_number,
	   current_element->lambda, current_element->rate,
	   current_element->distortion, current_element->nodes); */

    /* make proper adjustment to rate and distortion */
    if (current_element->rate < 0.0) current_element->rate = 0.0;
    if (current_element->distortion < 0.0) current_element->distortion = 0.0;

    /* get rate and distortion in bpp */
    current_element->rate /= scale;
    current_element->distortion /= scale;
  }

  return(TRUE);
}

/******************************************************************************
 * DOCUMENTATION ********************************************************
 ******************************************************************************
   NAME map_tree

   DESCRIPTION map_tree outputs a script to select the correct
   multiresolution codebook.  The script uses the select program from
   the tsvq code.  The script is an {\em example}, the user should
   change this routine to make it work for their own data.

   ARGUMENTS
      IARG  node            the root of the tree
      IARG  outputfile      pointer to the open script file
      IARG  codebookname    the prefix name of the files for each node

   RETURN

   ALGORITHM

   AUTHOR Jill R. Goldschneider

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

void map_tree(TreeNode *node, FILE *outputfile, char *codebookname)
{
  int       i;
  char      extension[NAME_MAX];
  char      temp_str[NAME_MAX];
  char      temp_str2[NAME_MAX];
  TreeNode *tempnode;

  /* if this node is best, use it and return */
  if (node->split == FALSE) {

    /* find the extension number */
    tempnode = node;
    strcpy(temp_str, "");
    if (tempnode->depth == 0) {
      strcpy(extension, temp_str);
    }

    else {
      sprintf(temp_str, ".%d", node->child_id);

      while (tempnode->depth > 1) {
	tempnode = tempnode->parent;
	sprintf(temp_str2, ".%d%s", tempnode->child_id, temp_str);
        strcpy(temp_str, temp_str2);
      }
      strcpy(extension, temp_str);
    }