tsvqlib.c

weilevoy算法实现纹理合成,分带与不带加速两个版本

	printf("retry failed\n");
#endif
	return 0;
      }
    }

    //Recalculate the centroids
    FindCentroidF(pix, numpix, flags, 1, p);
    for(k=0; k<SIZE; k++){
      cen1[k] = p[k];
    }

    FindCentroidF(pix, numpix, flags, 2, p);
    for(k=0; k<SIZE; k++){
      cen2[k] = p[k];
    } 
  }
  
  return 1;
}
/***************************************************************************
 * RecurseLeft(curr, cen1, pix, numpix, flags, depth, maxdepth)
 * Inputs:         curr - the current node in the tree
 *                 cen1 - the centroid for the new left child of curr
 *                 pix - the vectors associated with curr
 *                 numpix - the number of pixels in pix
 *                 flags - information about the clustering of pix
 *                 depth - the current tree depth
 *                 maxdepth - the maximum tree depth
 *
 * Description: This fuction creates a new left child and assigns it the 
 * proper centroid.  It then collects all vectors associated with the left
 * child in preparation for a call to AddLevel on the left child
 ***************************************************************************/
void RecurseLeft(node *curr, Vector cen1, Vector pix[], int numpix, 
		 int flags[], int depth, int maxdepth){
  int i, j, count, c=0;
  Vector *leftpix;
  
  //Create the left child
  makeLeftChild(cen1, curr);
  
#ifdef DEBUG
  printf("Made left child...\n");
#endif

  //Count the number of pixels in this cluster
  for(i=0; i<numpix; i++)
    if(flags[i] == 1) c++;
  
  if(c > 1){
    //Create the list of vectors that go with the left child
    leftpix = (Vector *)malloc(c*sizeof(Vector));
    count = 0;
    for(i=0; i<numpix; i++){
      if(flags[i] == 1){
	for(j=0; j<SIZE; j++)
	  leftpix[count][j] = pix[i][j];
	count++;
      }
    }
    //Make a call to AddLevel using the left child
    AddLevel(leftpix, c, curr->left, depth+1, maxdepth);
  }
}

/***************************************************************************
 * RecurseRight(curr, cen2, pix, numpix, flags, depth, maxdepth)
 * Inputs:         curr - the current node in the tree
 *                 cen2 - the centroid for the new right child of curr
 *                 pix - the vectors associated with curr
 *                 numpix - the number of pixels in pix
 *                 flags - information about the clustering of pix
 *                 depth - the current tree depth
 *                 maxdepth - the maximum tree depth
 *
 * Description: This fuction creates a new right child and assigns it the 
 * proper centroid.  It then collects all vectors associated with the right
 * child in preparation for a call to AddLevel on the right child
 ***************************************************************************/
void RecurseRight(node *curr, Vector cen2, Vector pix[], int numpix, 
		 int flags[], int depth, int maxdepth){
  int i, j, count, c=0;
  Vector *rightpix;

  //Create the right child
  makeRightChild(cen2, curr);
#ifdef DEBUG
  printf("Made right child...\n");
#endif

  //Count the number of pixels in this cluster
  for(i=0; i<numpix; i++)
    if(flags[i] == 2) c++;

  if(c > 1){
    //Create the list of vectors that go with the right child
    rightpix = (Vector *)malloc(c*sizeof(Vector));
    count = 0;
    for(i=0; i<numpix; i++){
      if(flags[i] == 2){
	for(j=0; j<SIZE; j++)
	  rightpix[count][j] = pix[i][j];
	count++;
      }
    }  
    //Make a call to AddLevel using the right child
    AddLevel(rightpix, c, curr->right, depth+1, maxdepth);
  }
}

/***************************************************************************
 * GetDist(a, b)
 * Inputs:  vectors a and b
 *
 * Description: Calculates the L2 distance between two vectors
 ***************************************************************************/
int GetDist(Vector a, Vector b){
  int dist=0;
  int temp;
  int i;

  for(i=0; i<SIZE-1; i++){
    temp = abs(a[i].r-b[i].r) + abs(a[i].g-b[i].g) + abs(a[i].b-b[i].b);
    dist += temp*temp;
  }
  
  return dist;
}

/***************************************************************************
 * FindCentroid(image, tsize, output)
 * Inputs:         image - a set of vectors
 *                 tsize - the number of vectors in image
 *                 output - the centroid of the vectors
 *
 * Description: Given a set of vectors, this function calculates their 
 * centroid.
 ***************************************************************************/
void FindCentroid(Vector image[], int tsize, Vector output){
  int i, j;
  int rsum, gsum, bsum;

  for(j=0; j<SIZE; j++){
    rsum = gsum = bsum = 0;
    for(i=0; i<tsize; i++){
      rsum += image[i][j].r;
      gsum += image[i][j].g;
      bsum += image[i][j].b;   
    } 
    output[j].r = rsum / tsize;
    output[j].g = gsum / tsize;
    output[j].b = bsum / tsize;
  }
}

/***************************************************************************
 * FindCentroidF(image, tsize, flags, choice, output)
 * Inputs:         image - a set of vectors
 *                 tsize - the number of vectors in image
 *                 flags - the clustering information about the vectors 
 *                         in image
 *                 choice - the flag value that corresponds to this cluster
 *                 output - the centroid of the vectors
 *
 * Description: Given a set of vectors, this function calculates the 
 * centroid of the ones belonging to the selected cluster.
 ***************************************************************************/
void FindCentroidF(Vector image[], int tsize, int flags[], 
		     int choice, Vector output){
  int i, j;
  int rsum, gsum, bsum;
  int count;

  count = 0;
  for(j=0; j<SIZE; j++){
    rsum = gsum = bsum = 0;
    count = 0;
    for(i=0; i<tsize; i++){
      if(flags[i] == choice){
	rsum += image[i][j].r;
	gsum += image[i][j].g;
	bsum += image[i][j].b;
	count++;
      }
    } 
    output[j].r = rsum / count;
    output[j].g = gsum / count;
    output[j].b = bsum / count;
  }
}

/***************************************************************************
 * makeLeftChild(data, parent)
 * Inputs:         data - the centroid of the left child's vectors
 *                 parent - the parent of the left child
 *
 * Description: This function creates a new left child for parent given 
 * a pointer to the parent and the data vector of the new child.
 ***************************************************************************/
void makeLeftChild(Vector data, node *parent){
  node *child;
  int i;

  child = (node *)malloc(sizeof(node));
  
  for(i=0; i<SIZE; i++)
    child->data[i] = data[i];

  child->right = NULL;
  child->left = NULL;

  parent->left = child;
}

/***************************************************************************
 * makeRightChild(data, parent)
 * Inputs:         data - the centroid of the right child's vectors
 *                 parent - the parent of the right child
 *
 * Description: This function creates a new right child for parent given 
 * a pointer to the parent and the data vector of the new child.
 ***************************************************************************/
void makeRightChild(Vector data, node *parent){
  node *child;
  int i;

  child = (node *)malloc(sizeof(node));
  
  for(i=0; i<SIZE; i++)
    child->data[i] = data[i];

  child->right = NULL;
  child->left = NULL;

  parent->right = child;
}

/***************************************************************************
 ***********************Search the Tree for a Match*************************
 ***************************************************************************/

/*****************************************************************************
 * FindMatch(point)
 * Inputs:     point - the pixel neighborhood in the target image that is 
 * being processed
 * Output: a pixel value containg the best match from the tree
 *
 * Description: Given a pixel neighborhood, FindMatch traverses the tree to 
 * find the best match for that neighborhood
 ****************************************************************************/ 

Pixel FindMatch(Vector point){
  //Start at the root of the tree
  return FindMatchHelper(point, root);
}

Pixel FindMatchHelper(Vector point, node *curr){
  int left, right;
  
  //If this node has no children, stop recursing because a match has been
  //found.
  if(curr->left == NULL && curr->right == NULL)
    return curr->data[SIZE-1];

  //Otherwise, see if this point is closer to the left or right child and 
  //follow the appropriate one.
  else{
    left = GetDist(point, curr->left->data);
    right = GetDist(point, curr->right->data);
    
    if(left < right){
#ifdef DEBUG
      printf("Going left...\n");
#endif
      return FindMatchHelper(point, curr->left);
    }
    else{
#ifdef DEBUG
      printf("Going right...\n");
#endif
      return FindMatchHelper(point, curr->right);
    }
  }
}