From 89ba7eb6dea930a4ec684d201b0d6db0027f8a23 Mon Sep 17 00:00:00 2001
From: Monty <xiphmont@xiph.org>
Date: Tue, 28 Dec 1999 03:41:58 +0000
Subject: [PATCH] Incremental update, seperated weighting from the metric
 (optimization), added auxiliary point data to the training sets.

Monty

svn path=/trunk/vorbis/; revision=211
---
 vq/Makefile.in |  4 +++-
 vq/build.c     |  8 +++----
 vq/lspdata.c   | 70 ++++++++++++++++++++++++++++++++++++----------------------
 vq/train.c     | 21 +++++++++---------
 vq/vqext.h     |  6 +++--
 vq/vqgen.c     | 28 +++++++++++++++++------
 vq/vqgen.h     | 20 +++++++++++------
 7 files changed, 99 insertions(+), 58 deletions(-)

diff --git a/vq/Makefile.in b/vq/Makefile.in
index 137f8cd..5833cbf 100644
--- a/vq/Makefile.in
+++ b/vq/Makefile.in
@@ -1,4 +1,4 @@
-# $Id: Makefile.in,v 1.2 1999/12/17 13:19:30 xiphmont Exp $
+# $Id: Makefile.in,v 1.3 1999/12/28 03:41:52 xiphmont Exp $
 
 ###############################################################################
 #                                                                             #
@@ -52,6 +52,8 @@ $(ALLOFILES): 	$(HFILES)
 .c.o:
 	$(CC) $(CFLAGS) -c $<
 
+$(OFILES):	$(HFILES)
+
 clean:
 	-rm -f *.o *.a test* *~ *.out *.m config.* \
 		lspvqtrain
diff --git a/vq/build.c b/vq/build.c
index 33530ea..3269923 100644
--- a/vq/build.c
+++ b/vq/build.c
@@ -78,7 +78,7 @@ int main(int argc,char *argv[]){
   quant_meta q;
   int *quantlist=NULL;
 
-  int entries=-1,dim=-1;
+  int entries=-1,dim=-1,dummy;
   FILE *out=NULL;
   FILE *in=NULL;
   char *line,*name;
@@ -122,13 +122,13 @@ int main(int argc,char *argv[]){
   line=rline(in,out,1);
   
   line=rline(in,out,1);
-  if(sscanf(line,"%d %d",&entries,&dim)!=2){
+  if(sscanf(line,"%d %d %d",&entries,&dim,&dummy)!=2){
     fprintf(stderr,"Syntax error reading book file\n");
     exit(1);
   }
   
   /* just use it to allocate mem */
-  vqgen_init(&v,dim,entries,NULL);
+  vqgen_init(&v,dim,0,entries,NULL,NULL);
   
   /* quant */
   line=rline(in,out,1);
@@ -170,7 +170,7 @@ int main(int argc,char *argv[]){
 	sscanf(line,"%lf",b+k);
       }
       if(feof(in))break;
-      vqgen_addpoint(&v,b);
+      vqgen_addpoint(&v,b,NULL);
     }
     v.entries=entries;
   }
diff --git a/vq/lspdata.c b/vq/lspdata.c
index 14275cb..0914b05 100644
--- a/vq/lspdata.c
+++ b/vq/lspdata.c
@@ -18,6 +18,7 @@
 
  ********************************************************************/
 
+#include <stdlib.h>
 #include <math.h>
 #include <stdio.h>
 #include "vqgen.h"
@@ -25,6 +26,7 @@
 
 char *vqext_booktype="LSPdata";  
 quant_meta q={0,0,0,1};          /* set sequence data */
+int vqext_aux=1;
 
 /* LSP training metric.  We weight error proportional to distance
    *between* LSP vector values.  The idea of this metric is not to set
@@ -33,41 +35,54 @@ quant_meta q={0,0,0,1};          /* set sequence data */
    features. */
 
 double global_maxdel=M_PI;
-#define FUDGE ((global_maxdel*2.0)-testdist)
+#define FUDGE ((global_maxdel*2.0)-weight[i])
+double *weight=NULL;
+
+double *vqext_weight(vqgen *v,double *p){
+  int i;
+  int el=v->elements;
+  double lastp=0.;
+  for(i=0;i<el;i++){
+    double predist=(p[i]-lastp);
+    double postdist=(p[i+1]-p[i]);
+    weight[i]=(predist<postdist?predist:postdist);
+    lastp=p[i];
+  }
+  return p;
+}
 
                             /* candidate,actual */
-double vqext_metric(vqgen *v,double *b, double *a){
+double vqext_metric(vqgen *v,double *e, double *p){
   int i;
   int el=v->elements;
   double acc=0.;
-  /*double lasta=0.;*/
-  double lastb=0.;
   for(i=0;i<el;i++){
-
-    /*    double needdist=(a[i]-lastb);
-	  double actualdist=(a[i]-lasta);*/
-    double testdist=(b[i]-lastb);
-
-    double val=(a[i]-b[i])*FUDGE;
-
+    double val=(p[i]-e[i])*FUDGE;
     acc+=val*val;
-
-    /*lasta=a[i];*/
-    lastb=b[i];
   }
   return acc;
 }
 
 /* Data files are line-vectors, starting with zero.  If we want to
    train on a subvector starting in the middle, we need to adjust the
-   data as if it was starting at zero */
+   data as if it was starting at zero.  we also need to add the 'aux'
+   value, which is an extra point at the end so we have leading and
+   trailing space */
 
-void vqext_adjdata(double *b,int start,int dim){
-  if(start>0){
-    int i;
-    double base=b[start-1];
-    for(i=start;i<start+dim;i++)b[i]-=base;
-  }
+/* assume vqext_aux==1 */
+void vqext_addpoint_adj(vqgen *v,double *b,int start,int dim,int cols){
+  double *a=alloca(sizeof(double)*(dim+1)); /* +aux */
+  double base=0;
+  int i;
+
+  if(start>0)base=b[start-1];
+  for(i=0;i<dim;i++)a[i]=b[i+start]-base;
+  if(start+dim+1>cols) /* +aux */
+    a[i]=M_PI-base;
+  else
+    a[i]=b[i+start]-base;
+  
+  vqgen_addpoint(v,a,a+dim);
 }
 
 /* we just need to calc the global_maxdel from the training set */
@@ -75,12 +90,15 @@ void vqext_preprocess(vqgen *v){
   long j,k;
 
   global_maxdel=0.;
-  for(j=0;j<v->entries;j++){
+  for(j=0;j<v->points;j++){
     double last=0.;
-    for(k=0;k<v->elements;k++){
-      double now=_now(v,j)[k];
-      if(now-last>global_maxdel)global_maxdel=now-last;
-      last=now;
+    for(k=0;k<v->elements+v->aux;k++){
+      double p=_point(v,j)[k];
+      if(p-last>global_maxdel)global_maxdel=p-last;
+      last=p;
     }
   }
+
+  weight=malloc(sizeof(double)*v->elements);
 }
+
diff --git a/vq/train.c b/vq/train.c
index 8f982b4..c67e4e7 100644
--- a/vq/train.c
+++ b/vq/train.c
@@ -156,12 +156,12 @@ int main(int argc,char *argv[]){
       } 
       
       line=rline(in,out,1);
-      if(sscanf(line,"%d %d",&entries,&dim)!=2){
+      if(sscanf(line,"%d %d %d",&entries,&dim,&vqext_aux)!=3){
 	fprintf(stderr,"Syntax error reading book file\n");
 	exit(1);
       }
       
-      vqgen_init(&v,dim,entries,vqext_metric);
+      vqgen_init(&v,dim,vqext_aux,entries,vqext_metric,vqext_weight);
       init=1;
       
       /* quant setup */
@@ -196,13 +196,13 @@ int main(int argc,char *argv[]){
 	i=0;
 	v.entries=0; /* hack to avoid reseeding */
 	while(1){
-	  for(k=0;k<dim;k++){
+	  for(k=0;k<dim+vqext_aux;k++){
 	    line=rline(in,out,0);
 	    if(!line)break;
 	    sscanf(line,"%lf",b+k);
 	  }
 	  if(feof(in))break;
-	  vqgen_addpoint(&v,b);
+	  vqgen_addpoint(&v,b,b+dim);
 	}
 	v.entries=entries;
       }
@@ -256,7 +256,7 @@ int main(int argc,char *argv[]){
 	  fprintf(stderr,"-p required when training a new set\n");
 	  exit(1);
 	}
-	vqgen_init(&v,dim,entries,vqext_metric);
+	vqgen_init(&v,dim,vqext_aux,entries,vqext_metric,vqext_weight);
 	init=1;
       }
 
@@ -300,10 +300,9 @@ int main(int argc,char *argv[]){
 	    while(*line==' ')line++;
 	  }
 	  if(num<=0)num=(cols-start)/dim;
-	  for(i=0;i<num;i++){
-	    vqext_adjdata(b,start+i*dim,dim);
-	    vqgen_addpoint(&v,b+start+i*dim);
-	  }
+	  for(i=0;i<num;i++)
+	    vqext_addpoint_adj(&v,b,start+i*dim,dim,cols);
+
 	  free(b);
 	}
       }
@@ -334,7 +333,7 @@ int main(int argc,char *argv[]){
 
   fprintf(out,"# OggVorbis VQ codebook trainer, intermediate file\n");
   fprintf(out,"%s\n",vqext_booktype);
-  fprintf(out,"%d %d\n",entries,dim);
+  fprintf(out,"%d %d %d\n",entries,dim,vqext_aux);
   fprintf(out,"%ld %ld %d %d\n",q.min,q.delta,q.quant,q.sequencep);
 
   /* quantized entries */
@@ -352,7 +351,7 @@ int main(int argc,char *argv[]){
   fprintf(out,"# points---\n");
   i=0;
   for(j=0;j<v.points;j++)
-    for(k=0;k<dim && k<80;k++)
+    for(k=0;k<dim+vqext_aux;k++)
       fprintf(out,"%f\n",v.pointlist[i++]);
 
   fclose(out);
diff --git a/vq/vqext.h b/vq/vqext.h
index fb850bb..445a7e7 100644
--- a/vq/vqext.h
+++ b/vq/vqext.h
@@ -22,9 +22,11 @@
 
 extern char *vqext_booktype;
 extern quant_meta q;
+extern int vqext_aux;
 
-extern double vqext_metric(vqgen *v,double *b, double *a);
-extern void vqext_adjdata(double *b,int start,int dim);
+extern double vqext_metric(vqgen *v,double *e, double *p);
+extern double *vqext_weight(vqgen *v,double *p);
+extern void vqext_addpoint_adj(vqgen *v,double *b,int start,int dim,int cols);
 extern void vqext_preprocess(vqgen *v);
 
 #endif
diff --git a/vq/vqgen.c b/vq/vqgen.c
index 60a24e6..919d0d2 100644
--- a/vq/vqgen.c
+++ b/vq/vqgen.c
@@ -14,7 +14,7 @@
  function: build a VQ codebook 
  author: Monty <xiphmont@mit.edu>
  modifications by: Monty
- last modification date: Dec 10 1999
+ last modification date: Dec 27 1999
 
  ********************************************************************/
 
@@ -69,9 +69,15 @@ double _dist_sq(vqgen *v,double *a, double *b){
   return acc;
 }
 
+double *_weight_null(vqgen *v,double *a){
+  return a;
+}
+
 /* *must* be beefed up. */
 void _vqgen_seed(vqgen *v){
-  memcpy(v->entrylist,v->pointlist,sizeof(double)*v->entries*v->elements);
+  long i;
+  for(i=0;i<v->entries;i++)
+    memcpy(_now(v,i),_point(v,i),sizeof(double)*v->elements);
 }
 
 /* External calls *******************************************************/
@@ -187,13 +193,14 @@ void vqgen_unquantize(vqgen *v,quant_meta *q){
   }
 }
 
-void vqgen_init(vqgen *v,int elements,int entries,
-		double (*metric)(vqgen *,double *, double *)){
+void vqgen_init(vqgen *v,int elements,int aux,int entries,
+		double  (*metric)(vqgen *,double *, double *),
+		double *(*weight)(vqgen *,double *)){
   memset(v,0,sizeof(vqgen));
 
   v->elements=elements;
   v->allocated=32768;
-  v->pointlist=malloc(v->allocated*v->elements*sizeof(double));
+  v->pointlist=malloc(v->allocated*(v->elements+v->aux)*sizeof(double));
 
   v->entries=entries;
   v->entrylist=malloc(v->entries*v->elements*sizeof(double));
@@ -203,15 +210,22 @@ void vqgen_init(vqgen *v,int elements,int entries,
     v->metric_func=metric;
   else
     v->metric_func=_dist_sq;
+  if(weight)
+    v->weight_func=weight;
+  else
+    v->weight_func=_weight_null;
+
 }
 
-void vqgen_addpoint(vqgen *v, double *p){
+void vqgen_addpoint(vqgen *v, double *p,double *a){
   if(v->points>=v->allocated){
     v->allocated*=2;
-    v->pointlist=realloc(v->pointlist,v->allocated*v->elements*sizeof(double));
+    v->pointlist=realloc(v->pointlist,v->allocated*(v->elements+v->aux)*
+			 sizeof(double));
   }
   
   memcpy(_point(v,v->points),p,sizeof(double)*v->elements);
+  if(v->aux)memcpy(_point(v,v->points)+v->elements,p,sizeof(double)*v->aux);
   v->points++;
   if(v->points==v->entries)_vqgen_seed(v);
 }
diff --git a/vq/vqgen.h b/vq/vqgen.h
index fafaf5f..a305659 100644
--- a/vq/vqgen.h
+++ b/vq/vqgen.h
@@ -17,6 +17,7 @@
 typedef struct vqgen{
   int it;
   int elements;
+  int aux;
 
   /* point cache */
   double *pointlist; 
@@ -29,7 +30,8 @@ typedef struct vqgen{
   double *bias;
   long   entries;
 
-  double (*metric_func)   (struct vqgen *v,double *a,double *b);
+  double  (*metric_func) (struct vqgen *v,double *entry,double *point);
+  double *(*weight_func) (struct vqgen *v,double *point);
 } vqgen;
 
 typedef struct vqbook{
@@ -67,19 +69,23 @@ typedef struct {
 } quant_meta;
 
 static inline double *_point(vqgen *v,long ptr){
-  return v->pointlist+(v->elements*ptr);
+  return v->pointlist+((v->elements+v->aux)*ptr);
+}
+
+static inline double *_aux(vqgen *v,long ptr){
+  return _point(v,ptr)+v->aux;
 }
 
 static inline double *_now(vqgen *v,long ptr){
   return v->entrylist+(v->elements*ptr);
 }
 
-extern void vqgen_init(vqgen *v,int elements,int entries,
-		       double (*metric)(vqgen *,double *, double *));
-extern void vqgen_addpoint(vqgen *v, double *p);
-extern double *vqgen_midpoint(vqgen *v);
-extern double vqgen_iterate(vqgen *v);
+extern void vqgen_init(vqgen *v,int elements,int aux,int entries,
+		       double  (*metric)(vqgen *,double *, double *),
+		       double *(*weight)(vqgen *,double *));
+extern void vqgen_addpoint(vqgen *v, double *p,double *aux);
 
+extern double vqgen_iterate(vqgen *v);
 extern void vqgen_unquantize(vqgen *v,quant_meta *q);
 extern void vqgen_quantize(vqgen *v,quant_meta *q);
 
-- 
2.7.4