lbg_engi.c

VQ压缩算法

/*==============================================================*/
/* This is the engine of LBG algorithm                          */
/*                                                              */
/* Author : Jialong He                                          */
/* Date   : Aug. 16, 1995                                       */
/* Modify : April 25, 1998, change to linked list               */
/*==============================================================*/
#include <stdlib.h>
#include <time.h>
#include "vq_model.h"

#define  MaxIter 100
extern int verbose;

/*
 *==========================================================
 *  find centroid for a code vector from specified data
 *==========================================================
 */

void centroid (float **data, float *centvec, int *LabelVec,
	       int numdata, int dimension, int Label)
{
  int VecCnt, DimCnt;
  int numlabel = 0;
  float *AvgBuf;

  MArray_1D(AvgBuf, dimension, float, "AvgBuf");
  /*--------------*/
  /* Clear buffer */
  /*--------------*/
  for (DimCnt=0; DimCnt< dimension; DimCnt++)
	  AvgBuf[DimCnt] = 0.0;

  /*------------------------------------------------*/
  /* Accumulate vectors belong to this code vector  */
  /*------------------------------------------------*/
  for (VecCnt=0; VecCnt<numdata; VecCnt++)
    if (LabelVec[VecCnt] == Label) {
      for (DimCnt=0; DimCnt<dimension; DimCnt++)
	AvgBuf[DimCnt] += data[VecCnt][DimCnt];
      numlabel++;          /* Vector counter increase */
    }

  if (numlabel == 0)
/*    fprintf(stderr, "Warning: Splitting caused an outlier!\n") */;
  else for (DimCnt=0; DimCnt<dimension; DimCnt++)
    centvec[DimCnt] = AvgBuf[DimCnt] / numlabel;

  free(AvgBuf);
}

/*
 *==================================================
 *  Find out nearest code vector for given OneVec
 *  Return the index of this code vector
 *==================================================
 */
int winning_cell(float **CodeBook, float *OneVec, int numcv, int dimension, float *Dist)
{
  int   CodeCnt, DimCnt, Nearest=0;
  float EucliDist,  MinError=LARGE;

  for (CodeCnt = 0; CodeCnt < numcv; CodeCnt++) {
    EucliDist = 0.0;
    for (DimCnt = 0; DimCnt < dimension; ++DimCnt)
       EucliDist += (CodeBook[CodeCnt][DimCnt] - OneVec[DimCnt]) *
	       (CodeBook[CodeCnt][DimCnt] - OneVec[DimCnt]);
    if (EucliDist < MinError) {
       MinError = EucliDist;
       Nearest  = CodeCnt;
    }
  }    /* CodeCnt */

  (*Dist) = MinError;
  return (Nearest);
}
 
/*-----------------------------------------------*/
/*-----------------------------------------------*/
float LBG_Codebook(float **codebook, float **data, int numcodes,
		  int numdata, int dimension)
{
  int   CodeCnt, VecCnt;        /* loop counter variables      */
  int   count = 0;
  int   *Labels;
  float ThisError, LastError=LARGE;
  float Dist;


  MArray_1D(Labels, numdata, int, "labels");

  /*------------------------------------*/
  /* loop until splitting is sufficient */
  /*------------------------------------*/
  while (count<MaxIter) {

    ThisError = 0.0;
    /*------------------------*/
    /* computer winning cells */
    /*------------------------*/
    for (VecCnt=0; VecCnt<numdata; VecCnt++) {
      Labels[VecCnt] = winning_cell(codebook, data[VecCnt], numcodes, dimension, &Dist);
      ThisError += Dist * Dist;
    }

    ThisError /= ((float) numdata)*((float) dimension);
    if ((LastError - ThisError) / LastError < 0.001) break;

    for (CodeCnt=0; CodeCnt<numcodes ; CodeCnt++)
      centroid(data, codebook[CodeCnt], Labels, numdata, dimension, CodeCnt);

    count++;
    LastError = ThisError;
    if (verbose) fprintf (stderr, "VQ error %f\n", ThisError);
  }

  free(Labels);
  return(ThisError);
}


void LBG_engine (DType *DataHead, DType *CodeHead, int ClassCnt) {

  int   VecCnt, DimCnt;        /* loop counter variables      */
  int   DataLen, CodeLen, VecDim;
  int   CdCnt, CurrCode;
  float Orig, Sum;
  float **OneBook, **OneData;

  OneData = DataHead[ClassCnt].Mat;
  OneBook = CodeHead[ClassCnt].Mat;
  VecDim  = DataHead[ClassCnt].VecDim;
  DataLen  = DataHead[ClassCnt].VecNum;
  CodeLen = CodeHead[ClassCnt].VecNum;

  /*----------------------------------------------*/
  /* First code vector is centroid of all vectors */
  /*----------------------------------------------*/
  for (DimCnt=0; DimCnt<VecDim; DimCnt++) {
    Sum = 0.0;
    for (VecCnt=0; VecCnt<DataLen; VecCnt++)
       Sum += OneData[VecCnt][DimCnt];
    OneBook[0][DimCnt] = Sum / DataLen;
  }

  CurrCode = 1;  /* this one code vector */
  /*------------------------------------*/
  /* loop until splitting is sufficient */
  /*------------------------------------*/
  while (CurrCode * 2 <= CodeLen) {

    /*-----------------------------*/
    /* split codes by perturbation */
    /*-----------------------------*/
    for (CdCnt=0; CdCnt<CurrCode; CdCnt++)
      for (DimCnt=0; DimCnt<VecDim; DimCnt++) {
	 Orig = OneBook[CdCnt][DimCnt];
	 OneBook[CdCnt + CurrCode][DimCnt] = Orig + 0.00001 * Orig;
	 OneBook[CdCnt][DimCnt] = Orig - 0.00001 * Orig;
      }

    CurrCode *= 2;    /* double code book size */

    fprintf (stderr, "Current codebook size: %d\n", CurrCode);

    LBG_Codebook(OneBook, OneData, CurrCode, DataLen, VecDim);
  } /* while */
}