From 199022815ab4ba696b5cdb2b0844eb77125f481f Mon Sep 17 00:00:00 2001
From: Monty <xiphmont@xiph.org>
Date: Wed, 16 Feb 2000 16:18:42 +0000
Subject: [PATCH] Enhancements (added cell spacing metrics and minimum cell
 distances to trainer) Bugfixes (fence straddling problem in the splitter,
 other fixes)

Monty

svn path=/trunk/vorbis/; revision=261
---
 vq/Makefile.in   |   9 ++-
 vq/bookutil.c    |  12 +---
 vq/build.c       |  10 ++--
 vq/genericdata.c |   7 ++-
 vq/lspdata.c     |   7 ++-
 vq/metrics.c     |  51 ++++++++++++++++-
 vq/residuedata.c | 100 +++++++++++++++++++++++++++++++++
 vq/train.c       |  18 ++++--
 vq/vqext.h       |   5 +-
 vq/vqgen.c       | 165 ++++++++++++++++++++++++++++++++++++++++++-------------
 vq/vqgen.h       |   9 ++-
 vq/vqsplit.c     |  68 +++++++++++++++++++++--
 12 files changed, 389 insertions(+), 72 deletions(-)
 create mode 100644 vq/residuedata.c

diff --git a/vq/Makefile.in b/vq/Makefile.in
index 45a56a0..3b07ccd 100644
--- a/vq/Makefile.in
+++ b/vq/Makefile.in
@@ -1,4 +1,4 @@
-# $Id: Makefile.in,v 1.8 2000/01/28 14:31:29 xiphmont Exp $
+# $Id: Makefile.in,v 1.9 2000/02/16 16:18:32 xiphmont Exp $
 
 ###############################################################################
 #                                                                             #
@@ -29,7 +29,7 @@ HFILES =	../include/vorbis/codebook.h vqgen.h vqext.h bookutil.h
 
 OFILES = 	vqgen.o vqsplit.o bookutil.o
 ALLOFILES = 	$(OFILES) lspdata.o genericdata.o train.o build.o run.o\
-		cascade.o partition.o metrics.o
+		cascade.o partition.o metrics.o residuedata.o
 
 all:
 	$(MAKE) target CFLAGS="$(OPT)"
@@ -40,11 +40,14 @@ debug:
 profile: 
 	$(MAKE) target CFLAGS="$(PROFILE)"
 
-target:	lspvqtrain genericvqtrain vqbuild vqcascade vqpartition vqmetrics
+target:	lspvqtrain genericvqtrain residuevqtrain vqbuild vqcascade vqpartition vqmetrics
 
 lspvqtrain:	$(OFILES) lspdata.o train.o
 	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
 
+residuevqtrain:	$(OFILES) residuedata.o train.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
 genericvqtrain:	$(OFILES) genericdata.o train.o
 	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
 
diff --git a/vq/bookutil.c b/vq/bookutil.c
index c4de2c0..cf21804 100644
--- a/vq/bookutil.c
+++ b/vq/bookutil.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: utility functions for loading .vqh and .vqd files
- last mod: $Id: bookutil.c,v 1.9 2000/02/13 10:23:50 xiphmont Exp $
+ last mod: $Id: bookutil.c,v 1.10 2000/02/16 16:18:33 xiphmont Exp $
 
  ********************************************************************/
 
@@ -298,16 +298,6 @@ codebook *codebook_load(char *filename){
   return(b);
 }
 
-static double _dist(int el,double *a, double *b){
-  int i;
-  double acc=0.;
-  for(i=0;i<el;i++){
-    double val=(a[i]-b[i]);
-    acc+=val*val;
-  }
-  return acc;
-}
-
 int codebook_entry(codebook *b,double *val){
   const static_codebook *c=b->c;
   encode_aux *t=c->encode_tree;
diff --git a/vq/build.c b/vq/build.c
index 5e074e5..eb15d00 100644
--- a/vq/build.c
+++ b/vq/build.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: utility main for building codebooks from training sets
- last mod: $Id: build.c,v 1.11 2000/02/07 19:49:56 xiphmont Exp $
+ last mod: $Id: build.c,v 1.12 2000/02/16 16:18:34 xiphmont Exp $
 
  ********************************************************************/
 
@@ -131,7 +131,7 @@ int main(int argc,char *argv[]){
   }
   
   /* just use it to allocate mem */
-  vqgen_init(&v,dim,0,entries,NULL,NULL);
+  vqgen_init(&v,dim,0,entries,0.,NULL,NULL);
   
   /* quant */
   line=rline(in,out);
@@ -210,7 +210,7 @@ int main(int argc,char *argv[]){
   /* quantlist */
   fprintf(out,"static long _vq_quantlist_%s[] = {\n",name);
   i=0;
-  for(j=0;j<entries;j++){
+  for(j=0;j<c.entries;j++){
     fprintf(out,"\t");
     for(k=0;k<dim;k++)
       fprintf(out,"%5ld, ",c.quantlist[i++]);
@@ -220,9 +220,9 @@ int main(int argc,char *argv[]){
 
   /* lengthlist */
   fprintf(out,"static long _vq_lengthlist_%s[] = {\n",name);
-  for(j=0;j<entries;){
+  for(j=0;j<c.entries;){
     fprintf(out,"\t");
-    for(k=0;k<16 && j<entries;k++,j++)
+    for(k=0;k<16 && j<c.entries;k++,j++)
       fprintf(out,"%2ld,",c.lengthlist[j]);
     fprintf(out,"\n");
   }
diff --git a/vq/genericdata.c b/vq/genericdata.c
index d6dbbed..37416fb 100644
--- a/vq/genericdata.c
+++ b/vq/genericdata.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: generic euclidian distance metric for VQ codebooks
- last mod: $Id: genericdata.c,v 1.2 2000/01/05 15:04:57 xiphmont Exp $
+ last mod: $Id: genericdata.c,v 1.3 2000/02/16 16:18:35 xiphmont Exp $
 
  ********************************************************************/
 
@@ -26,6 +26,11 @@ char *vqext_booktype="GENERICdata";
 int vqext_aux=0;                
 quant_meta q={0,0,0,0};          /* non sequence data; each scalar 
 				    independent */
+double vqext_mindist=0.;
+
+void vqext_quantize(vqgen *v,quant_meta *q){
+  vqgen_quantize(v,q);
+}
 
 double *vqext_weight(vqgen *v,double *p){
   /*noop*/
diff --git a/vq/lspdata.c b/vq/lspdata.c
index bc6a771..bd839b8 100644
--- a/vq/lspdata.c
+++ b/vq/lspdata.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: metrics and quantization code for LSP VQ codebooks
- last mod: $Id: lspdata.c,v 1.9 2000/01/10 10:42:03 xiphmont Exp $
+ last mod: $Id: lspdata.c,v 1.10 2000/02/16 16:18:36 xiphmont Exp $
 
  ********************************************************************/
 
@@ -25,6 +25,11 @@
 char *vqext_booktype="LSPdata";  
 quant_meta q={0,0,0,1};          /* set sequence data */
 int vqext_aux=1;
+double vqext_mindist=0.;
+
+void vqext_quantize(vqgen *v,quant_meta *q){
+  vqgen_quantize(v,q);
+}
 
 /* LSP training metric.  We weight error proportional to distance
    *between* LSP vector values.  The idea of this metric is not to set
diff --git a/vq/metrics.c b/vq/metrics.c
index a8c6204..5b55595 100644
--- a/vq/metrics.c
+++ b/vq/metrics.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: function calls to collect codebook metrics
- last mod: $Id: metrics.c,v 1.5 2000/01/28 09:05:20 xiphmont Exp $
+ last mod: $Id: metrics.c,v 1.6 2000/02/16 16:18:37 xiphmont Exp $
 
  ********************************************************************/
 
@@ -43,6 +43,10 @@ int books=0;
 int dim=-1;
 double *work;
 
+static double *_now(codebook *c, int i){
+  return c->valuelist+i*c->c->dim;
+}
+
 int histerrsort(const void *a, const void *b){
   double av=histogram_distance[*((long *)a)];
   double bv=histogram_distance[*((long *)b)];
@@ -79,6 +83,47 @@ void process_preprocess(codebook **bs,char *basename){
   }
 }
 
+static double _dist(int el,double *a, double *b){
+  int i;
+  double acc=0.;
+  for(i=0;i<el;i++){
+    double val=(a[i]-b[i]);
+    acc+=val*val;
+  }
+  return acc;
+}
+
+void cell_spacing(codebook **b){
+  int i,j,k;
+  for(i=0;i<books;i++){
+    double min,max,mean=0.,meansq=0.;
+    codebook *c=b[i];
+
+    fprintf(stderr,"\nCell spacing for book %d:\n",i);
+    
+    /* minimum, maximum, mean, ms cell spacing */
+    for(j=0;j<c->c->entries;j++){
+      double localmin=-1.;
+      for(k=0;k<c->c->entries;k++){
+	double this=_dist(c->c->dim,_now(c,j),_now(c,k));
+	if(j!=k &&
+	   (localmin==-1 || this<localmin))
+	  localmin=this;
+      }
+      
+      if(j==0 || localmin<min)min=localmin;
+      if(j==0 || localmin>max)max=localmin;
+      mean+=sqrt(localmin);
+      meansq+=localmin;
+    }
+
+    fprintf(stderr,"\tminimum cell spacing (closest side): %g\n",sqrt(min));
+    fprintf(stderr,"\tmaximum cell spacing (closest side): %g\n",sqrt(max));
+    fprintf(stderr,"\tmean closest side spacing: %g\n",mean/c->c->entries);
+    fprintf(stderr,"\tmean sq closest side spacing: %g\n",sqrt(meansq/c->c->entries));
+  }
+}
+
 void process_postprocess(codebook **b,char *basename){
   int i,j,k;
   char *buffer=alloca(strlen(basename)+80);
@@ -97,6 +142,9 @@ void process_postprocess(codebook **b,char *basename){
 	  sqrt(meanerrorsq_acc/(count*dim)));
   fprintf(stderr,"\tglobal mean deviation: %g\n",
 	  meandev_acc/(count*dim));
+
+  cell_spacing(b);
+
   {
     FILE *out;
 
@@ -172,7 +220,6 @@ void process_postprocess(codebook **b,char *basename){
     fclose(out);
 		
   }
-
 }
 
 void process_vector(codebook **bs,double *a){
diff --git a/vq/residuedata.c b/vq/residuedata.c
new file mode 100644
index 0000000..2c75f68
--- /dev/null
+++ b/vq/residuedata.c
@@ -0,0 +1,100 @@
+/********************************************************************
+ *                                                                  *
+ * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE.  *
+ * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
+ * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE.    *
+ * PLEASE READ THESE TERMS DISTRIBUTING.                            *
+ *                                                                  *
+ * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000             *
+ * by Monty <monty@xiph.org> and The XIPHOPHORUS Company            *
+ * http://www.xiph.org/                                             *
+ *                                                                  *
+ ********************************************************************
+
+ function: metrics and quantization code for residue VQ codebooks
+ last mod: $Id: residuedata.c,v 1.1 2000/02/16 16:18:38 xiphmont Exp $
+
+ ********************************************************************/
+
+#include <stdlib.h>
+#include <math.h>
+#include <stdio.h>
+#include "vqgen.h"
+#include "bookutil.h"
+#include "vqext.h"
+
+char *vqext_booktype="RESdata";  
+quant_meta q={0,0,0,0};          /* set sequence data */
+int vqext_aux=0;
+
+double vqext_mindist=.7; /* minimum desired cell radius */
+
+/* LSP training metric.  We weight error proportional to distance
+   *between* LSP vector values.  The idea of this metric is not to set
+   final cells, but get the midpoint spacing into a form conducive to
+   what we want, which is weighting toward preserving narrower
+   features. */
+
+double *vqext_weight(vqgen *v,double *p){
+  return p;
+}
+
+/* quantize aligned on unit boundaries */
+void vqext_quantize(vqgen *v,quant_meta *q){
+  int i,j,k;
+  double min,max,delta=1.;
+  int vals=(1<<q->quant);
+
+  min=max=_now(v,0)[0];
+  for(i=0;i<v->entries;i++)
+    for(j=0;j<v->elements;j++){
+      if(max<_now(v,i)[j])max=_now(v,i)[j];
+      if(min>_now(v,i)[j])min=_now(v,i)[j];
+    }
+
+  /* roll the delta */
+  while(1){
+    double qmax=rint(max/delta);
+    double qmin=rint(min/delta);
+    int qvals=rint(qmax-qmin)+1;
+
+    if(qvals>vals){
+      delta*=2;
+    }else if(qvals*2<=vals){
+      delta*=.5;
+    }else{
+      min=qmin*delta;
+      q->min=float24_pack(qmin*delta);
+      q->delta=float24_pack(delta);
+      break;
+    }
+  }
+
+  for(j=0;j<v->entries;j++){
+    for(k=0;k<v->elements;k++){
+      double val=_now(v,j)[k];
+      double now=rint((val-min)/delta);
+      _now(v,j)[k]=now;
+    }
+  }
+}
+
+/* this should probably go to a x^6/4 error metric */
+
+                            /* candidate,actual */
+double vqext_metric(vqgen *v,double *e, double *p){
+  int i;
+  double acc=0.;
+  for(i=0;i<v->elements;i++){
+    double val=p[i]-e[i];
+    acc+=val*val;
+  }
+  return sqrt(acc);
+}
+
+void vqext_addpoint_adj(vqgen *v,double *b,int start,int dim,int cols){
+  vqgen_addpoint(v,b+start,NULL);
+}
+
+void vqext_preprocess(vqgen *v){
+}
diff --git a/vq/train.c b/vq/train.c
index d95d6fa..2f99c93 100644
--- a/vq/train.c
+++ b/vq/train.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: utility main for training codebooks
- last mod: $Id: train.c,v 1.14 2000/01/10 10:42:06 xiphmont Exp $
+ last mod: $Id: train.c,v 1.15 2000/02/16 16:18:38 xiphmont Exp $
 
  ********************************************************************/
 
@@ -128,7 +128,8 @@ int main(int argc,char *argv[]){
 	exit(1);
       }
       
-      vqgen_init(&v,dim,vqext_aux,entries,vqext_metric,vqext_weight);
+      vqgen_init(&v,dim,vqext_aux,entries,vqext_mindist,
+		 vqext_metric,vqext_weight);
       init=1;
       
       /* quant setup */
@@ -223,7 +224,8 @@ int main(int argc,char *argv[]){
 	  fprintf(stderr,"-p required when training a new set\n");
 	  exit(1);
 	}
-	vqgen_init(&v,dim,vqext_aux,entries,vqext_metric,vqext_weight);
+	vqgen_init(&v,dim,vqext_aux,entries,vqext_mindist,
+		   vqext_metric,vqext_weight);
 	init=1;
       }
 
@@ -289,9 +291,12 @@ int main(int argc,char *argv[]){
 
   for(i=0;i<iter && !exiting;i++){
     double result;
-    if(i!=0)vqgen_unquantize(&v,&q);
+    if(i!=0){
+      vqgen_unquantize(&v,&q);
+      vqgen_cellmetric(&v);
+    }
     result=vqgen_iterate(&v);
-    vqgen_quantize(&v,&q);
+    vqext_quantize(&v,&q);
     if(result<desired)break;
   }
 
@@ -321,6 +326,9 @@ int main(int argc,char *argv[]){
       fprintf(out,"%f\n",v.pointlist[i++]);
 
   fclose(out);
+
+  vqgen_unquantize(&v,&q);
+  vqgen_cellmetric(&v);
   exit(0);
 
   syner:
diff --git a/vq/vqext.h b/vq/vqext.h
index c370d16..ba3c2b7 100644
--- a/vq/vqext.h
+++ b/vq/vqext.h
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: prototypes for extermal metrics specific to data type
- last mod: $Id: vqext.h,v 1.6 1999/12/30 07:27:03 xiphmont Exp $
+ last mod: $Id: vqext.h,v 1.7 2000/02/16 16:18:39 xiphmont Exp $
 
  ********************************************************************/
 
@@ -24,10 +24,13 @@
 extern char *vqext_booktype;
 extern quant_meta q;
 extern int vqext_aux;
+extern double vqext_mindist;
 
 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);
+extern void vqext_quantize(vqgen *v,quant_meta *);
+
 
 #endif
diff --git a/vq/vqgen.c b/vq/vqgen.c
index 610df4b..4f042da 100644
--- a/vq/vqgen.c
+++ b/vq/vqgen.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: train a VQ codebook 
- last mod: $Id: vqgen.c,v 1.28 2000/01/06 13:57:13 xiphmont Exp $
+ last mod: $Id: vqgen.c,v 1.29 2000/02/16 16:18:40 xiphmont Exp $
 
  ********************************************************************/
 
@@ -80,6 +80,73 @@ void _vqgen_seed(vqgen *v){
     memcpy(_now(v,i),_point(v,i),sizeof(double)*v->elements);
 }
 
+int directdsort(const void *a, const void *b){
+  double av=*((double *)a);
+  double bv=*((double *)b);
+  if(av>bv)return(-1);
+  return(1);
+}
+
+void vqgen_cellmetric(vqgen *v){
+  int i,j,k;
+  double min=-1.,max=-1.,mean=0.,acc=0.;
+  long dup=0,unused=0;
+ #ifdef NOISY
+   char buff[80];
+   double spacings[v->entries];
+   int count=0;
+   FILE *cells;
+   sprintf(buff,"cellspace%d.m",v->it);
+   cells=fopen(buff,"w");
+#endif
+
+  /* minimum, maximum, cell spacing */
+  for(j=0;j<v->entries;j++){
+    double localmin=-1.;
+
+    for(k=0;k<v->entries;k++){
+      if(j!=k){
+	double this=_dist(v,_now(v,j),_now(v,k));
+	if(this>0){
+	  if(v->assigned[k] && (localmin==-1 || this<localmin))
+	    localmin=this;
+	}else{	
+	  if(k<j){
+	    dup++;
+	    break;
+	  }
+	}
+      }
+    }
+    if(k<v->entries)continue;
+
+    if(v->assigned[j]==0){
+      unused++;
+      continue;
+    }
+    
+    localmin=v->max[j]+localmin/2; /* this gives us rough diameter */
+    if(min==-1 || localmin<min)min=localmin;
+    if(max==-1 || localmin>max)max=localmin;
+    mean+=localmin;
+    acc++;
+#ifdef NOISY
+    spacings[count++]=localmin;
+#endif
+  }
+
+  fprintf(stderr,"cell diameter: %.03g::%.03g::%.03g (%d unused/%d dup)\n",
+	  min,mean/acc,max,unused,dup);
+
+#ifdef NOISY
+  qsort(spacings,count,sizeof(double),directdsort);
+  for(i=0;i<count;i++)
+    fprintf(cells,"%g\n",spacings[i]);
+  fclose(cells);
+#endif	    
+
+}
+
 /* External calls *******************************************************/
 
 /* We have two forms of quantization; in the first, each vector
@@ -166,13 +233,14 @@ void vqgen_unquantize(vqgen *v,quant_meta *q){
   }
 }
 
-void vqgen_init(vqgen *v,int elements,int aux,int entries,
+void vqgen_init(vqgen *v,int elements,int aux,int entries,double mindist,
 		double  (*metric)(vqgen *,double *, double *),
 		double *(*weight)(vqgen *,double *)){
   memset(v,0,sizeof(vqgen));
 
   v->elements=elements;
   v->aux=aux;
+  v->mindist=mindist;
   v->allocated=32768;
   v->pointlist=malloc(v->allocated*(v->elements+v->aux)*sizeof(double));
 
@@ -180,6 +248,7 @@ void vqgen_init(vqgen *v,int elements,int aux,int entries,
   v->entrylist=malloc(v->entries*v->elements*sizeof(double));
   v->assigned=malloc(v->entries*sizeof(long));
   v->bias=calloc(v->entries,sizeof(double));
+  v->max=calloc(v->entries,sizeof(double));
   if(metric)
     v->metric_func=metric;
   else
@@ -202,20 +271,17 @@ void vqgen_addpoint(vqgen *v, double *p,double *a){
   if(v->aux)memcpy(_point(v,v->points)+v->elements,a,sizeof(double)*v->aux);
   v->points++;
   if(v->points==v->entries)_vqgen_seed(v);
-}
-
-int directdsort(const void *a, const void *b){
-  double av=*((double *)a);
-  double bv=*((double *)b);
-  if(av>bv)return(-1);
-  return(1);
+  if(!(v->points&0xff))spinnit("loading... ",v->points);
 }
 
 double vqgen_iterate(vqgen *v){
   long   i,j,k;
+  long   biasable;
+
   double fdesired=(double)v->points/v->entries;
   long  desired=fdesired;
   long  desired2=desired*2;
+
   double asserror=0.;
   double meterror=0.;
   double *new=malloc(sizeof(double)*v->entries*v->elements);
@@ -244,14 +310,16 @@ double vqgen_iterate(vqgen *v){
   /*memset(v->bias,0,sizeof(double)*v->entries);*/
   memset(nearcount,0,sizeof(long)*v->entries);
   memset(v->assigned,0,sizeof(long)*v->entries);
+  biasable=0;
   for(i=0;i<v->points;i++){
     double *ppt=v->weight_func(v,_point(v,i));
     double firstmetric=v->metric_func(v,_now(v,0),ppt)+v->bias[0];
     double secondmetric=v->metric_func(v,_now(v,1),ppt)+v->bias[1];
     long   firstentry=0;
     long   secondentry=1;
+    int    biasflag=1;
 
-    if(i%100)spinnit("biasing... ",v->points+v->points+v->entries-i);
+    if(!(i&0xff))spinnit("biasing... ",v->points+v->points+v->entries-i);
 
     if(firstmetric>secondmetric){
       double temp=firstmetric;
@@ -279,43 +347,54 @@ double vqgen_iterate(vqgen *v){
     j=firstentry;
     for(j=0;j<v->entries;j++){
       
-      double thismetric;
+      double thismetric,localmetric;
       double *nearbiasptr=nearbias+desired2*j;
       long k=nearcount[j];
       
+      localmetric=v->metric_func(v,_now(v,j),ppt);
       /* 'thismetric' is to be the bias value necessary in the current
 	 arrangement for entry j to capture point i */
       if(firstentry==j){
 	/* use the secondary entry as the threshhold */
-	thismetric=secondmetric-v->metric_func(v,_now(v,j),ppt);
+	thismetric=secondmetric-localmetric;
       }else{
 	/* use the primary entry as the threshhold */
-	thismetric=firstmetric-v->metric_func(v,_now(v,j),ppt);
+	thismetric=firstmetric-localmetric;
       }
 
-      /* a cute two-stage delayed sorting hack */
-      if(k<desired){
-	nearbiasptr[k]=thismetric;
-	k++;
-	if(k==desired){
-	  spinnit("biasing... ",v->points+v->points+v->entries-i);
-	  qsort(nearbiasptr,desired,sizeof(double),directdsort);
-	}
-	
-      }else if(thismetric>nearbiasptr[desired-1]){
-	nearbiasptr[k]=thismetric;
-	k++;
-	if(k==desired2){
-	  spinnit("biasing... ",v->points+v->points+v->entries-i);
-	  qsort(nearbiasptr,desired2,sizeof(double),directdsort);
-	  k=desired;
+      /* support the idea of 'minimum distance'... if we want the
+         cells in a codebook to be roughly some minimum size (as with
+         the low resolution residue books) */
+      
+      if(localmetric>=v->mindist){
+
+	/* a cute two-stage delayed sorting hack */
+	if(k<desired){
+	  nearbiasptr[k]=thismetric;
+	  k++;
+	  if(k==desired){
+	    spinnit("biasing... ",v->points+v->points+v->entries-i);
+	    qsort(nearbiasptr,desired,sizeof(double),directdsort);
+	  }
+	  
+	}else if(thismetric>nearbiasptr[desired-1]){
+	  nearbiasptr[k]=thismetric;
+	  k++;
+	  if(k==desired2){
+	    spinnit("biasing... ",v->points+v->points+v->entries-i);
+	    qsort(nearbiasptr,desired2,sizeof(double),directdsort);
+	    k=desired;
+	  }
 	}
-      }
-      nearcount[j]=k;
+	nearcount[j]=k;
+      }else
+	biasflag=0;
     }
+    biasable+=biasflag;
   }
   
   /* inflate/deflate */
+
   for(i=0;i<v->entries;i++){
     double *nearbiasptr=nearbias+desired2*i;
 
@@ -325,7 +404,16 @@ double vqgen_iterate(vqgen *v){
     if(nearcount[i]>desired)
       qsort(nearbiasptr,nearcount[i],sizeof(double),directdsort);
 
-    v->bias[i]=nearbiasptr[desired-1];
+    /* desired is the *maximum* bias queue size.  If we're using
+       minimum distance, we're not interested in the max size... we're
+       interested in the biasable number of points */
+    {
+      long localdesired=(double)biasable/v->entries;
+      if(localdesired)
+	v->bias[i]=nearbiasptr[localdesired-1];
+      else
+	v->bias[i]=nearbiasptr[0];
+    }
   }
 
   /* Now assign with new bias and find new midpoints */
@@ -334,7 +422,7 @@ double vqgen_iterate(vqgen *v){
     double firstmetric=v->metric_func(v,_now(v,0),ppt)+v->bias[0];
     long   firstentry=0;
 
-    if(i%100)spinnit("centering... ",v->points-i);
+    if(!(i&0xff))spinnit("centering... ",v->points-i);
 
     for(j=0;j<v->entries;j++){
       double thismetric=v->metric_func(v,_now(v,j),ppt)+v->bias[j];
@@ -352,15 +440,18 @@ double vqgen_iterate(vqgen *v){
           ppt[0],ppt[1]);
 #endif
 
-    meterror+=firstmetric-v->bias[firstentry];
+    firstmetric-=v->bias[firstentry];
+    meterror+=firstmetric;
     /* set up midpoints for next iter */
-    if(v->assigned[j]++)
+    if(v->assigned[j]++){
       for(k=0;k<v->elements;k++)
 	vN(new,j)[k]+=ppt[k];
-    else
+      if(firstmetric>v->max[firstentry])v->max[firstentry]=firstmetric;
+    }else{
       for(k=0;k<v->elements;k++)
 	vN(new,j)[k]=ppt[k];
-
+      v->max[firstentry]=firstmetric;
+    }
   }
 
   /* assign midpoints */
diff --git a/vq/vqgen.h b/vq/vqgen.h
index 8d5a1b4..9c78c7d 100644
--- a/vq/vqgen.h
+++ b/vq/vqgen.h
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: build a VQ codebook 
- last mod: $Id: vqgen.h,v 1.10 2000/01/06 13:57:14 xiphmont Exp $
+ last mod: $Id: vqgen.h,v 1.11 2000/02/16 16:18:41 xiphmont Exp $
 
  ********************************************************************/
 
@@ -22,7 +22,9 @@
 typedef struct vqgen{
   int it;
   int elements;
+
   int aux;
+  double mindist;
 
   /* point cache */
   double *pointlist; 
@@ -34,6 +36,8 @@ typedef struct vqgen{
   long   *assigned;
   double *bias;
   long   entries;
+  double *max;
+  
 
   double  (*metric_func) (struct vqgen *v,double *entry,double *point);
   double *(*weight_func) (struct vqgen *v,double *point);
@@ -58,7 +62,8 @@ static inline double *_now(vqgen *v,long ptr){
   return v->entrylist+(v->elements*ptr);
 }
 
-extern void vqgen_init(vqgen *v,int elements,int aux,int entries,
+extern void vqgen_init(vqgen *v,
+		       int elements,int aux,int entries,double mindist,
 		       double  (*metric)(vqgen *,double *, double *),
 		       double *(*weight)(vqgen *,double *));
 extern void vqgen_addpoint(vqgen *v, double *p,double *aux);
diff --git a/vq/vqsplit.c b/vq/vqsplit.c
index bf4e8c4..1a28df4 100644
--- a/vq/vqsplit.c
+++ b/vq/vqsplit.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: build a VQ codebook and the encoding decision 'tree'
- last mod: $Id: vqsplit.c,v 1.15 2000/02/13 10:23:51 xiphmont Exp $
+ last mod: $Id: vqsplit.c,v 1.16 2000/02/16 16:18:42 xiphmont Exp $
 
  ********************************************************************/
 
@@ -156,6 +156,12 @@ int lp_split(vqgen *v,codebook *b,
 
   char spinbuf[80];
   sprintf(spinbuf,"splitting [%ld left]... ",v->points-*pointsofar);
+
+  if(depth==22 && points==9 && entries==2 && *pointsofar==252935){
+    fprintf(stderr,"HERE\n");
+
+  }
+
   
   /* which cells do points belong to?  Do this before n^2 best pair chooser. */
 
@@ -168,7 +174,7 @@ int lp_split(vqgen *v,codebook *b,
 
     for(j=1;j<entries;j++){
       double thismetric=_dist(v,_now(v,entryindex[j]),ppt);
-      if(thismetric<firstmetric){
+      if(thismetric<=firstmetric){ /* Not <; on the line goes to higher number */
 	firstmetric=thismetric;
 	firstentry=j;
       }
@@ -250,7 +256,7 @@ int lp_split(vqgen *v,codebook *b,
       for(j=0;j<entries;j++){
 	if(j!=i){
 	  double this=_dist(v,q,_now(v,entryindex[j]));
-	  if(ref_j==-1 || this<ref_best){
+	  if(ref_j==-1 || this<=ref_best){ /* <=, not <; very important */
 	    ref_best=this;
 	    ref_j=entryindex[j];
 	  }
@@ -396,6 +402,60 @@ void vqsp_book(vqgen *v, codebook *b, long *quantlist){
   b->c=c;
   t=c->encode_tree=calloc(1,sizeof(encode_aux));
 
+  /* make sure there are no duplicate entries and that every 
+     entry has points */
+
+  for(i=0;i<v->entries;){
+    /* duplicate? if so, eliminate */
+    for(j=0;j<i;j++){
+      if(_dist(v,_now(v,i),_now(v,j))==0.){
+	fprintf(stderr,"found a duplicate entry!  removing...\n");
+	v->entries--;
+	memcpy(_now(v,i),_now(v,v->entries),sizeof(double)*v->elements);
+	memcpy(quantlist+i*v->elements,quantlist+v->entries*v->elements,
+	       sizeof(long)*v->elements);
+	break;
+      }
+    }
+    if(j==i)i++;
+  }
+
+  {
+    v->assigned=calloc(v->entries,sizeof(long));
+    for(i=0;i<v->points;i++){
+      double *ppt=_point(v,i);
+      double firstmetric=_dist(v,_now(v,0),ppt);
+      long   firstentry=0;
+
+      if(!(i&0xff))spinnit("checking... ",v->points-i);
+
+      for(j=0;j<v->entries;j++){
+	double thismetric=_dist(v,_now(v,j),ppt);
+	if(thismetric<firstmetric){
+	  firstmetric=thismetric;
+	  firstentry=j;
+	}
+      }
+      
+      v->assigned[firstentry]++;
+    }
+
+    for(j=0;j<v->entries;){
+      if(v->assigned[j]==0){
+	fprintf(stderr,"found an unused entry!  removing...\n");
+	v->entries--;
+	memcpy(_now(v,j),_now(v,v->entries),sizeof(double)*v->elements);
+	v->assigned[j]=v->assigned[v->elements];
+	memcpy(quantlist+j*v->elements,quantlist+v->entries*v->elements,
+	       sizeof(long)*v->elements);
+	continue;
+      }
+      j++;
+    }
+  }
+
+  fprintf(stderr,"Building a book with %d unique entries...\n",v->entries);
+
   for(i=0;i<v->entries;i++)entryindex[i]=i;
   for(i=0;i<v->points;i++)pointindex[i]=i;
   
@@ -409,7 +469,7 @@ void vqsp_book(vqgen *v, codebook *b, long *quantlist){
   t->p=malloc(sizeof(long)*t->alloc);
   t->q=malloc(sizeof(long)*t->alloc);
   
-  /* first, generate the encoding decision heirarchy */
+  /* generate the encoding decision heirarchy */
   {
     long pointsofar=0;
     fprintf(stderr,"Total leaves: %d            \n",
-- 
2.7.4