/********************************************************************
* *
* THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. *
- * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
- * THE GNU LESSER/LIBRARY PUBLIC LICENSE, WHICH IS INCLUDED WITH *
- * THIS SOURCE. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
+ * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS *
+ * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
+ * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
* *
- * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2000 *
- * by Monty <monty@xiph.org> and the XIPHOPHORUS Company *
- * http://www.xiph.org/ *
+ * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001 *
+ * by the Xiph.Org Foundation http://www.xiph.org/ *
* *
********************************************************************
- function: train a VQ codebook
- last mod: $Id: vqgen.c,v 1.37 2000/12/21 21:04:49 xiphmont Exp $
+ function: train a VQ codebook
********************************************************************/
#include "vqgen.h"
#include "bookutil.h"
-/* Codebook generation happens in two steps:
+/* Codebook generation happens in two steps:
1) Train the codebook with data collected from the encoder: We use
one of a few error metrics (which represent the distance between a
given data point and a candidate point in the training set) to
divide the training set up into cells representing roughly equal
- probability of occurring.
+ probability of occurring.
2) Generate the codebook and auxiliary data from the trained data set
*/
int directdsort(const void *a, const void *b){
float av=*((float *)a);
float bv=*((float *)b);
- if(av>bv)return(-1);
- return(1);
+ return (av<bv)-(av>bv);
}
void vqgen_cellmetric(vqgen *v){
for(k=0;k<v->entries;k++){
if(j!=k){
- float 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;
- }
- }
+ float 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;
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;
}
fprintf(stderr,"cell diameter: %.03g::%.03g::%.03g (%ld unused/%ld dup)\n",
- min,mean/acc,max,unused,dup);
+ min,mean/acc,max,unused,dup);
#ifdef NOISY
qsort(spacings,count,sizeof(float),directdsort);
for(i=0;i<count;i++)
fprintf(cells,"%g\n",spacings[i]);
fclose(cells);
-#endif
+#endif
}
int j,k;
mindel=maxdel=_now(v,0)[0];
-
+
for(j=0;j<v->entries;j++){
float last=0.f;
for(k=0;k<v->elements;k++){
for(k=0;k<v->elements;k++){
float val=_now(v,j)[k];
float now=rint((val-last-mindel)/delta);
-
+
_now(v,j)[k]=now;
if(now<0){
- /* be paranoid; this should be impossible */
- fprintf(stderr,"fault; quantized value<0\n");
- exit(1);
+ /* be paranoid; this should be impossible */
+ fprintf(stderr,"fault; quantized value<0\n");
+ exit(1);
}
if(now>maxquant){
- /* be paranoid; this should be impossible */
- fprintf(stderr,"fault; quantized value>max\n");
- exit(1);
+ /* be paranoid; this should be impossible */
+ fprintf(stderr,"fault; quantized value>max\n");
+ exit(1);
}
if(q->sequencep)last=(now*delta)+mindel+last;
}
}
void vqgen_init(vqgen *v,int elements,int aux,int entries,float mindist,
- float (*metric)(vqgen *,float *, float *),
- float *(*weight)(vqgen *,float *),int centroid){
+ float (*metric)(vqgen *,float *, float *),
+ float *(*weight)(vqgen *,float *),int centroid){
memset(v,0,sizeof(vqgen));
v->centroid=centroid;
if(v->points>=v->allocated){
v->allocated*=2;
v->pointlist=_ogg_realloc(v->pointlist,v->allocated*(v->elements+v->aux)*
- sizeof(float));
+ sizeof(float));
}
memcpy(_point(v,v->points),p,sizeof(float)*v->elements);
if(v->aux)memcpy(_point(v,v->points)+v->elements,a,sizeof(float)*v->aux);
-
+
/* quantize to the density mesh if it's selected */
if(v->mindist>0.f){
/* quantize to the mesh */
for(k=0;k<v->elements+v->aux;k++)
_point(v,v->points)[k]=
- rint(_point(v,v->points)[k]/v->mindist)*v->mindist;
+ rint(_point(v,v->points)[k]/v->mindist)*v->mindist;
}
v->points++;
if(!(v->points&0xff))spinnit("loading... ",v->points);
/* now march through and eliminate dupes */
for(i=1;i<v->points;i++){
if(memcmp(_point(v,i),_point(v,i-1),sortsize)){
- /* a new, unique entry. march it down */
- if(i>march)memcpy(_point(v,march),_point(v,i),sortsize);
- march++;
+ /* a new, unique entry. march it down */
+ if(i>march)memcpy(_point(v,march),_point(v,i),sortsize);
+ march++;
}
spinnit("eliminating density... ",v->points-i);
}
/* we're done */
fprintf(stderr,"\r%ld training points remining out of %ld"
- " after density mesh (%ld%%)\n",march,v->points,march*100/v->points);
+ " after density mesh (%ld%%)\n",march,v->points,march*100/v->points);
v->points=march;
}
sprintf(buff,"bias%d.m",v->it);
bias=fopen(buff,"w");
#endif
-
+
if(v->entries<2){
fprintf(stderr,"generation requires at least two entries\n");
float secondmetric=v->metric_func(v,_now(v,1),ppt)+v->bias[1];
long firstentry=0;
long secondentry=1;
-
+
if(!(i&0xff))spinnit("biasing... ",v->points+v->points+v->entries-i);
-
+
if(firstmetric>secondmetric){
- float temp=firstmetric;
- firstmetric=secondmetric;
- secondmetric=temp;
- firstentry=1;
- secondentry=0;
+ float temp=firstmetric;
+ firstmetric=secondmetric;
+ secondmetric=temp;
+ firstentry=1;
+ secondentry=0;
}
-
+
for(j=2;j<v->entries;j++){
- float thismetric=v->metric_func(v,_now(v,j),ppt)+v->bias[j];
- if(thismetric<secondmetric){
- if(thismetric<firstmetric){
- secondmetric=firstmetric;
- secondentry=firstentry;
- firstmetric=thismetric;
- firstentry=j;
- }else{
- secondmetric=thismetric;
- secondentry=j;
- }
- }
+ float thismetric=v->metric_func(v,_now(v,j),ppt)+v->bias[j];
+ if(thismetric<secondmetric){
+ if(thismetric<firstmetric){
+ secondmetric=firstmetric;
+ secondentry=firstentry;
+ firstmetric=thismetric;
+ firstentry=j;
+ }else{
+ secondmetric=thismetric;
+ secondentry=j;
+ }
+ }
}
-
+
j=firstentry;
for(j=0;j<v->entries;j++){
-
- float thismetric,localmetric;
- float *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-localmetric;
- }else{
- /* use the primary entry as the threshhold */
- thismetric=firstmetric-localmetric;
- }
-
- /* 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) */
-
- /* 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(float),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(float),directdsort);
- k=desired;
- }
- }
- nearcount[j]=k;
+
+ float thismetric,localmetric;
+ float *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-localmetric;
+ }else{
+ /* use the primary entry as the threshhold */
+ thismetric=firstmetric-localmetric;
+ }
+
+ /* 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) */
+
+ /* 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(float),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(float),directdsort);
+ k=desired;
+ }
+ }
+ nearcount[j]=k;
}
}
-
+
/* inflate/deflate */
-
+
for(i=0;i<v->entries;i++){
float *nearbiasptr=nearbias+desired2*i;
-
+
spinnit("biasing... ",v->points+v->entries-i);
-
+
/* due to the delayed sorting, we likely need to finish it off....*/
if(nearcount[i]>desired)
- qsort(nearbiasptr,nearcount[i],sizeof(float),directdsort);
+ qsort(nearbiasptr,nearcount[i],sizeof(float),directdsort);
v->bias[i]=nearbiasptr[desired-1];
}
- }else{
+ }else{
memset(v->bias,0,v->entries*sizeof(float));
}
for(j=0;j<v->entries;j++){
float thismetric=v->metric_func(v,_now(v,j),ppt)+v->bias[j];
if(thismetric<firstmetric){
- firstmetric=thismetric;
- firstentry=j;
+ firstmetric=thismetric;
+ firstentry=j;
}
}
j=firstentry;
-
+
#ifdef NOISY
fprintf(cells,"%g %g\n%g %g\n\n",
_now(v,j)[0],_now(v,j)[1],
if(v->centroid==0){
/* set up midpoints for next iter */
if(v->assigned[j]++){
- for(k=0;k<v->elements;k++)
- vN(new,j)[k]+=ppt[k];
- if(firstmetric>v->max[j])v->max[j]=firstmetric;
+ for(k=0;k<v->elements;k++)
+ vN(new,j)[k]+=ppt[k];
+ if(firstmetric>v->max[j])v->max[j]=firstmetric;
}else{
- for(k=0;k<v->elements;k++)
- vN(new,j)[k]=ppt[k];
- v->max[j]=firstmetric;
+ for(k=0;k<v->elements;k++)
+ vN(new,j)[k]=ppt[k];
+ v->max[j]=firstmetric;
}
}else{
/* centroid */
if(v->assigned[j]++){
- for(k=0;k<v->elements;k++){
- if(vN(new,j)[k]>ppt[k])vN(new,j)[k]=ppt[k];
- if(vN(new2,j)[k]<ppt[k])vN(new2,j)[k]=ppt[k];
- }
- if(firstmetric>v->max[firstentry])v->max[j]=firstmetric;
+ for(k=0;k<v->elements;k++){
+ if(vN(new,j)[k]>ppt[k])vN(new,j)[k]=ppt[k];
+
if(vN(new2,j)[k]<ppt[k])vN(new2,j)[k]=ppt[k];
+ }
+ if(firstmetric>v->max[firstentry])v->max[j]=firstmetric;
}else{
- for(k=0;k<v->elements;k++){
- vN(new,j)[k]=ppt[k];
- vN(new2,j)[k]=ppt[k];
- }
- v->max[firstentry]=firstmetric;
+ for(k=0;k<v->elements;k++){
+ vN(new,j)[k]=ppt[k];
+ vN(new2,j)[k]=ppt[k];
+ }
+ v->max[firstentry]=firstmetric;
}
}
}
asserror+=fabs(v->assigned[j]-fdesired);
if(v->assigned[j]){
if(v->centroid==0){
- for(k=0;k<v->elements;k++)
- _now(v,j)[k]=vN(new,j)[k]/v->assigned[j];
+ for(k=0;k<v->elements;k++)
+ _now(v,j)[k]=vN(new,j)[k]/v->assigned[j];
}else{
- for(k=0;k<v->elements;k++)
- _now(v,j)[k]=(vN(new,j)[k]+vN(new2,j)[k])/2.f;
+ for(k=0;k<v->elements;k++)
+ _now(v,j)[k]=(vN(new,j)[k]+vN(new2,j)[k])/2.f;
}
}
}
fprintf(stderr,"Pass #%d... ",v->it);
fprintf(stderr,": dist %g(%g) metric error=%g \n",
- asserror,fdesired,meterror/v->points);
+ asserror,fdesired,meterror/v->points);
v->it++;
-
+
free(new);
free(nearcount);
free(nearbias);
projects / platform / upstream / libvorbis.git / blobdiff