/****************************************************************************** * * 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);    }