tsvqlib.c

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

/***************************************************************************
 * tsvqlib.c
 * written by: Stephanie Wojtkowski
 *
 * Description: The implementation of tsvqlib: a library that provides
 * tree-structured VQ tools for performing the Wei-Levoy texture synthesis 
 * method.
 ***************************************************************************/
#include "tsvqlib.h"

#define DEBUG

/*  Any function prototypes with the //Fine comment before them have been 
    thoroughly tested and shown to be correct. */

//Fine
int GetDist(Vector a, Vector b);
//Fine
void FindCentroid(Vector image[], int size, Vector output);
//Fine
void FindCentroidF(Vector image[], int tsize, int flags[], 
		   int choice, Vector output);
//Fine
void InitializeTree(Vector image[], int tsize);
//Fine
void Vectorize(Pixel *image, int rows, int cols, Vector pix[]);
void AddLevel(Vector pix[], int numpix, node *curr, int depth, 
	      int maxdepth);
//Fine
void makeLeftChild(Vector data, node *parent);
//Fine
void makeRightChild(Vector data, node *parent);

Pixel FindMatchHelper(Vector point, node *curr);
//Fine
void PerturbCentroids(Vector c1, Vector c2, Vector c3);
//Fine
int ClusterVectors(Vector cen1, Vector cen2, Vector pix[], int numpix, 
		    int flags[], Vector original);
void RecurseLeft(node *curr, Vector cen1, Vector pix[], int numpix, 
		 int flags[], int depth, int maxdepth);
void RecurseRight(node *curr, Vector cen2, Vector pix[], int numpix, 
		 int flags[], int depth, int maxdepth);
/***************************************************************************
 *****************************Create TSVQ Tree******************************
 ***************************************************************************/

/***************************************************************************
 * BuildTree(image, rows, cols, maxdepth)
 * Input:      image - the input image from which a new texture will be 
 *                     generated
 *             rows - the number of rows in the image
 *             cols - the number of columns in the image
 *             maxdepth - the maximum depth of the VQ tree
 *
 * Description: This function creates a vector-quantized tree of pixel
 * neighborhoods based on the input image.
 ***************************************************************************/
void BuildTree(Pixel *image, int rows, int cols, int maxdepth){
  Vector pix[rows*cols];
  
  //Turn the image into a collection of image neighborhoods
  Vectorize(image, rows, cols, pix);
  printf("Vectorized image...\n");

  //Create the root of the tree and put the centroid in it
  InitializeTree(pix, rows*cols);
  printf("Initialized tree...\n");
  
  //Initialize random number generator for perturbing centroids
  srand((int) time(NULL));

  //Build the tree
  AddLevel(pix, rows*cols, root, 1, maxdepth);
  printf("Completed tree...\n");
}

/***************************************************************************
 * AddLevel(pix, numpix, curr, depth, maxdepth)
 * Inputs:        pix - the vectors in this cluster
 *                numpix - the number of vectors in pix
 *                curr - the current node in the tree
 *                depth - the current depth
 *                maxdepth - the maximum tree depth
 *
 * Description: AddLevel implements the building of a new level along the
 * current path.  It perturbs the centroids, clusters the input vectors, 
 * and then recurses right and left to build this node's children.
 ***************************************************************************/
void AddLevel(Vector pix[], int numpix, node *curr, int depth, 
	      int maxdepth){
  int success;
  Vector cen1, cen2;
  int flags[numpix];

  //Check if the computation has gone past the maximum depth
  if(depth > maxdepth) return;
  
  //Randomly perturb current centroid to make 2 new centroids
  PerturbCentroids(curr->data, cen1, cen2);
  
  //Cluster the vectors, then recalculate the centroids
  success = ClusterVectors(cen1, cen2, pix, numpix, flags, curr->data);
  
  //Check if the clustering worked.  If not, the vectors are all the
  //same, so stop subdividing them
  if(success == 0) return;
#ifdef DEBUG
  printf("Recursing left...\n");
#endif
  RecurseLeft(curr, cen1, pix, numpix, flags, depth, maxdepth);
#ifdef DEBUG
  printf("Recursing right...\n");
#endif
  RecurseRight(curr, cen2, pix, numpix, flags, depth, maxdepth);
}

/***************************************************************************
 * Perturb Centroids(c1,c2, c3)
 * Inputs:       c1 - the centroid to be perturbed
 *               c2 - the first perturbed result
 *               c3 - the second perturbed result
 *
 *  Description: This function takes in a vector of Pixels that represent 
 * the centroid of a set of pixels.  It perturbs the centroid by +- 1 
 * along each color axis and returns the two results.
 ***************************************************************************/

void PerturbCentroids(Vector c1, Vector c2, Vector c3){
  int i, r;
  double rtemp;
  
  //For each pixel in the input vector
  for(i=0; i<SIZE-1; i++){
    //Initialize centroids
    c2[i] = c1[i];
    c3[i] = c1[i];

    //Perturb r
    rtemp = (double) rand() /((double) RAND_MAX + 1); 
    r = ((int)(rtemp*2))*2 - 1;
    if(!((c2[i].r==255 && r==1) || (c3[i].r==255 && r==-1) ||
	 (c2[i].r==0 && r==-1) || (c3[i].r==0 && r==1))){
      c2[i].r += r;
      c3[i].r -= r;
    }
    //Perturb g
    rtemp = (double) rand() /((double) RAND_MAX + 1); 
    r = ((int)(rtemp*2))*2 - 1;
    if(!((c2[i].g==255 && r==1) || (c3[i].g==255 && r==-1) ||
	 (c2[i].g==0 && r==-1) || (c3[i].g==0 && r==1))){
      c2[i].g += r;
      c3[i].g -= r;
    }
    //Perturb b
    rtemp = (double) rand() /((double) RAND_MAX + 1); 
    r = ((int)(rtemp*2))*2 - 1;
    if(!((c2[i].b==255 && r==1) || (c3[i].b==255 && r==-1) ||
	 (c2[i].b==0 && r==-1) || (c3[i].b==0 && r==1))){
      c2[i].b += r;
      c3[i].b -= r;
    }
  }

  //Set the last pixel to the original value  
  c2[SIZE-1] = c1[SIZE-1];
  c3[SIZE-1] = c1[SIZE-1];
}

//Redefining the modulo function to properly handle negative numbers
int mod(int a, int b){
  if(a < 0)
    while(a < 0) a += b;
  else if(a >= b)
    a = a % b;

  return a;
}

/***************************************************************************
 * Vectorize(image, rows, cols, pix)
 * Inputs:       image - a texture image
 *               rows - the number of rows in the image
 *               cols - the number of columns in the image
 *               pix - an array in which to store the vectorized result
 *
 * Description: This function takes in an image and calculates the pixel
 * neighborhoods (vectors) based on the predefined neighborhood radius NRAD.
 ***************************************************************************/
void Vectorize(Pixel *image, int rows, int cols, Vector pix[]){
  int i, j, k;
  int x, y;
  int count;

  for(i=0; i<rows*cols; i++){
    count = 0;
    for(j=-NRAD; j<=0; j++){
      for(k=-NRAD; k<=NRAD; k++){
	x = mod(mod(i, rows) + k, cols);
	y = mod((((i-mod(i, cols)) / cols) + j), rows);
	pix[i][count] = image[y*cols+x];

	count++;
	if(count > SIZE) goto DONE;
      }
    }
  DONE:
  }
}
/***************************************************************************
 * InitializeTree(image, tsize)
 * Inputs:     image - the input image
 *             tsize - the number of pixels in the image
 *
 * Description: This function initializes the root of the tree by setting 
 * its value to the centroid of all image neighborhoods.
 ***************************************************************************/
void InitializeTree(Vector image[], int tsize){
  int i;
  Vector p;

  root = (node *)malloc(sizeof(node));
  
  FindCentroid(image, tsize, p);

  for(i=0; i<SIZE; i++)
    root->data[i] = p[i];

  root->left = NULL;
  root->right = NULL;
}

/***************************************************************************
 * ClusterVectors(cen1, cen2, pix, numpix, flags, original)
 * Inputs:       cen1 - the first perturbed centroid
 *               cen2 - the second perturbed centroid
 *               pix - the set of vectors to be clustered
 *               numpix - the number of vectors in pix
 *               flags - an array in which the clustering information 
 *                       will be stored
 *               original - the original centroid (in case cen1 and cen2 must
 *                          be reperturbed)
 *
 * Description: Given a set of vectors and two centroids, this function
 * clusters the vectors around the centroids.  The centroids are then 
 * recalculated and the vectors reclustered for 5 iterations to achieve
 * a stable clustering.
 ***************************************************************************/
int ClusterVectors(Vector cen1, Vector cen2, Vector pix[], int numpix, 
		    int flags[], Vector original){
  int i, j, k;
  int c1, c2; 
  int d1, d2;
  Vector p;
  int retried = 0;
  
		    RESTART:
  
  for(j=0; j<5; j++){
    c1 = c2 = 0;
    for(i=0; i<numpix; i++){
      d1 = GetDist(cen1, pix[i]);
      d2 = GetDist(cen2, pix[i]);
      
      //Assign this vector to the closest centroid
      if(d1 < d2){
	flags[i] = 1;
	c1++;
      }
      else{
	flags[i] = 2;
	c2++;
      }
    }

    //If this was a bad clustering and all vectors went into one cluster
    if(c1 == 0 || c2 == 0){
      //Try again
      if(retried == 0){
	retried = 1;
	PerturbCentroids(original, cen1, cen2);
	goto RESTART;
      }
      //Otherwise, stop the recursion - all the vectors must be the same
      else{
#ifdef DEBUG