gvq_engi.c

VQ压缩算法

/*==================================================*/
/* This is the GVQ algorithm proposed by Jialong HE */
/* It minimizes the error rate for vector goupes.   */
/*--------------------------------------------------*/
/*                                                  */
/* Author : Jialong He                              */
/* Date   : March 3, 1996                           */
/* Modify : April 25, 1998                          */
/*                                                  */
/* Note: window size is important   (win = 1)       */
/* First != DataID is better than Second == DataID  */
/*==================================================*/
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "vq_model.h"
#define  MaxOptN 100

extern   int verbose;

/*--------------------------------------------*/
/* train the codebook with the GVQ algorithm  */
/*--------------------------------------------*/
void GVQ_engine (DType *DataHead, DType *CodeHead, int TotalClass,
		 float alpha, float WinSize, int epoch, int OptN, int SeqSel) {

     int Loops, DataClass, CodeClass;
     int CodeCnt, DimCnt, EpochCnt = 1;
     int VecUpdate_1 = 0, VecUpdate_2 = 0;
     float *AccuDis, shortest, nshortest;
     float talpha, Ratio, Total_Loops, CurrWin, TmpFloat;
     int First, IndCnt;
     int ClsCnt, **NCode;     /* index of nearest codes, */
     int IndArr[MaxOptN];               /* Indices of a group optimized vectors */
     int DataID, VecDim;

     int TotalCode = 0, TotalVector = 0;

     /*---------------------------------------*/
     /* Total Code and Training vector number */
     /*---------------------------------------*/
     for (ClsCnt=0; ClsCnt< TotalClass; ClsCnt++) {
       TotalCode   += CodeHead[ClsCnt].VecNum;
       TotalVector += DataHead[ClsCnt].VecNum;
     }

     MArray_1D(AccuDis, TotalClass, float, "AccuDis");
     MArray_2D(NCode,   TotalClass, OptN, int, "NCode");

     VecDim = DataHead[0].VecDim;
     Loops = epoch * TotalVector;
     Total_Loops = Loops;
     while (Loops--) {

       /*--------------------------------------*/
       /* One Epoch finished                   */
       /*--------------------------------------*/
       if ((Loops % TotalVector) == 0) {
	fprintf(stderr, "Epoch %d, Vector Updated %d %d\n", EpochCnt++, VecUpdate_1, VecUpdate_2);
	VecUpdate_1  = 0;
	VecUpdate_2  = 0;
       }

       /*---------------------------*/
       /* randomly select a speaker */
       /*---------------------------*/
       DataClass = my_random() % TotalClass;

       /*---------------------------------------------------*/
       /* find CodeClass which has the same ID as DataClass */
       /* Usually, CodeClass == DataClass                   */
       /*---------------------------------------------------*/
       for (ClsCnt=0; ClsCnt< TotalClass; ClsCnt++) {
	 if (DataHead[DataClass].ID == CodeHead[ClsCnt].ID) {
	   CodeClass = ClsCnt;
	   break;
         }
       }

       if (SeqSel) {
	 DataID =  my_random() % (DataHead[DataClass].VecNum-OptN);
	 for (IndCnt=0; IndCnt<OptN; IndCnt++)
	   IndArr[IndCnt] = DataID+IndCnt;
       }
       else {             /* randomly select vectors */
	 for (IndCnt=0; IndCnt<OptN; IndCnt++)
	   IndArr[IndCnt] = my_random() % DataHead[DataClass].VecNum;
       }

       /*-------------------------------------------------*/
       /* learning rate and window size linearly decrease */
       /*-------------------------------------------------*/
       talpha  = alpha * Loops / Total_Loops;
       CurrWin = WinSize * Loops / Total_Loops + 0.1;

       /*----------------------------------------------*/
       /* Accumulated Euclidean distance to each code  */
       /*----------------------------------------------*/
       for (ClsCnt=0; ClsCnt< TotalClass; ClsCnt++) {  /* each code class */
	 AccuDis[ClsCnt] = 0.0;
	 for (IndCnt=0; IndCnt<OptN; IndCnt++) {  /* for vectors in a group */
	    shortest = LARGE; First = 0;
	    for (CodeCnt=0; CodeCnt<CodeHead[ClsCnt].VecNum; CodeCnt++) {
	      DIST_VEC(CodeHead[ClsCnt].Mat[CodeCnt], DataHead[DataClass].Mat[IndArr[IndCnt]],
		       TmpFloat, VecDim, float, float);
	      if (TmpFloat < shortest) {
		shortest = TmpFloat;
		First    = CodeCnt;
              }
	    }  /* for (CodeCnt) */

	    AccuDis[ClsCnt] += shortest;
	    NCode[ClsCnt][IndCnt] = First;

	 }  /* for (IndCnt) */
       }  /* for (ClsCnt) */


       /*-----------------------------------------------*/
       /* find out code class with min average distance */
       /*-----------------------------------------------*/
       shortest = LARGE;
       First = 0;
       for (DimCnt=0; DimCnt<TotalClass; DimCnt++) {
	  if (AccuDis[DimCnt] < shortest) {
	     shortest = AccuDis[DimCnt];
	     First = DimCnt;
	  }
       }

       if (AccuDis[CodeClass] != 0)
	  Ratio = (AccuDis[CodeClass] - AccuDis[First]) / AccuDis[CodeClass];

       /*-------------------------------------------------------*/
       /* if nearest class is not the class of vectors, learn   */
       /*-------------------------------------------------------*/
       if ((DataHead[DataClass].ID != CodeHead[First].ID) && (Ratio < CurrWin)) {

	 VecUpdate_1++;
	 for (IndCnt=0; IndCnt<OptN; IndCnt++) {
	   /*----------------------------------------------------*/
	   /* for each data vector, find out distance to nearest */
	   /* code vectors of class First/DataID		 */
	   /*----------------------------------------------------*/
	   DIST_VEC(CodeHead[First].Mat[ NCode[First][IndCnt]], DataHead[DataClass].Mat[IndArr[IndCnt] ],
		       shortest, VecDim, float, float);

	   DIST_VEC(CodeHead[DataClass].Mat[ NCode[DataClass][IndCnt]], DataHead[DataClass].Mat[IndArr[IndCnt] ],
		       nshortest, VecDim, float, float);

	   /*-----------------------------------------*/
	   /* adjust only misclassified vectors       */
	   /* First is wrong code, DataID is correct  */
	   /*-----------------------------------------*/
	   if  (shortest<nshortest) {
	      for (DimCnt = 0; DimCnt < VecDim; DimCnt++) {
		CodeHead[First].Mat[ NCode[First][IndCnt] ][DimCnt] -= talpha * (DataHead[DataClass].Mat[IndArr[IndCnt]][DimCnt] -
			    CodeHead[First].Mat[ NCode[First][IndCnt] ][DimCnt]);

		CodeHead[CodeClass].Mat[ NCode[CodeClass][IndCnt] ][DimCnt] += talpha * (DataHead[DataClass].Mat[IndArr[IndCnt]][DimCnt] -
			    CodeHead[CodeClass].Mat[ NCode[CodeClass][IndCnt] ][DimCnt]);

	      }
	   }  /* if shortest */
	 }    /* for IndCnt */
       }    /* if (First != DataID) */

       /*----------------------------------------------------------*/
       /* keep the codebook approximate density                    */
       /*----------------------------------------------------------*/
       else {
	if (DataHead[DataClass].ID == CodeHead[First].ID)  {
	  for (IndCnt=0; IndCnt<OptN; IndCnt++) {
	   for (DimCnt = 0; DimCnt < VecDim; DimCnt++)
		CodeHead[First].Mat[ NCode[First][IndCnt] ][DimCnt] += 0.1 * talpha * (DataHead[DataClass].Mat[IndArr[IndCnt]][DimCnt] -
			    CodeHead[First].Mat[ NCode[First][IndCnt] ][DimCnt]);
	  }
	  VecUpdate_2++;
	}
       }  /* else */
     }   /* while (Loops--) */

     MFree_1D(AccuDis);
     MFree_2D(NCode);
}