lvq_rout.cpp

face recognition test source code

/************************************************************************
 *                                                                      *
 *  Program package 'lvq_pak':                                          *
 *                                                                      *
 *  lvq_rout.c                                                          *
 *  -routines needed in some programs                                   *
 *    -training routines                                                *
 *    -classification routines                                          *
 *    -etc.                                                             *
 *                                                                      *
 *  Version 3.0                                                         *
 *  Date: 1 Mar 1995                                                    *
 *                                                                      *
 *  NOTE: This program package is copyrighted in the sense that it      *
 *  may be used for scientific purposes. The package as a whole, or     *
 *  parts thereof, cannot be included or used in any commercial         *
 *  application without written permission granted by its producents.   *
 *  No programs contained in this package may be copied for commercial  *
 *  distribution.                                                       *
 *                                                                      *
 *  All comments  concerning this program package may be sent to the    *
 *  e-mail address '[e-mail]'.                                *
 *                                                                      *
 ************************************************************************/

#include <header.h>
#include <stdio.h>
#include <float.h>
#include <math.h>
#include <stdlib.h>
#include "lvq_pak.h"
#include "lvq_rout.h"
#include "tools.h"
#include "sammon.h"

/* Check whether the vector 'code' (codebook vector) is correctly
   classified by knn-classification with respect to the codebook
   'data'.  Return 1 if correct, 0 if incorrect, -1 on error */

int correct_by_knn(struct entries *data, struct data_entry *code, int knn, 
		   WINNER_FUNCTION *find_knn)
{
  int corr = 0;
  int i;
  int codelabel;
  struct winner_info *winners;
  struct hitlist *hits;

  hits = new_hitlist();
  if (hits == NULL)
    return -1;

  if (knn < 1) knn = 1;
  winners = (struct winner_info *)malloc(sizeof(struct winner_info) * knn);
  if (winners == NULL)
    {
      Msg(0, "correct_by_knn");
      free_hitlist(hits);
      return -1;
    }

  /* Find nearest neighbours. Note: data is codebook, code is sample */
  if (find_knn(data, code, winners, knn) != knn)
    {
      Msg(0, "correct_by_knn: can't find winners");
      corr = -1;
      goto end;
    }

  for (i = 0; i < knn; i++) 
    add_hit(hits, get_entry_label(winners[i].winner));

  codelabel = get_entry_label(code);

  if (hits->head)
    if (hits->head->label == codelabel)
      corr = 1;
 end:
  free_hitlist(hits);
  free(winners);
  return(corr);
}


/* Pick a given number of entries from the beginning of the entry list */

struct entries *pick_codes(int num, struct entries *data)
{
  struct entries *datac;
  struct data_entry *prev, *loca, tmp;
  eptr p;

  datac = copy_entries(data);
  if (datac == NULL)
    {
      Msg(0, "extract_codes: can't copy entries structure");
      return NULL;
    }
  /* Pick (at most) 'num' entries from beginning */

  if ((loca = rewind_entries(data, &p)) == NULL)
    {
      Msg(0, "pick_codes: can't get data");
      close_entries(datac);
      return NULL;
    }
  prev = &tmp;
  tmp.next = NULL;
  while ((loca != NULL) && (num--)) {
    prev->next = copy_entry(data, loca);
    prev = prev->next;
    datac->num_entries++;
    loca = next_entry(&p);
  }

  datac->entry = tmp.next;
  datac->num_loaded = datac->num_entries;
  datac->flags.totlen_known = 1;

  return(datac);
}

/* Pick a given number of entries of given Class from entry list */

struct data_entry *pick_known_codes(int num, struct entries *data, int label)
{
  struct data_entry *prev, *loca, tmp;
  eptr p;

  if ((loca = rewind_entries(data, &p)) == NULL)
    {
      Msg(0, "pick_known_codes: can't get data");
      return NULL;
    }
  prev = &tmp;
  tmp.next = NULL;
  while ((loca != NULL) && (num)) {
    if (get_entry_label(loca) == label) {
      prev->next = copy_entry(data, loca);
      prev = prev->next;
      num--;
    }
    loca = next_entry(&p);
  }

  return(tmp.next);
}

/* Pick a given number of entries of each Class from entry list. The
   numbers of entries are given in an array. The selected entries
   should fall inside Class borders */

struct data_entry *pick_inside_codes(struct hitlist *classes, 
				     struct entries *data, int knn, 
				     WINNER_FUNCTION *find_knn)
{
  int still, datalabel;
  long total = 0;
  struct data_entry *prev, *loca, tmp;
  struct hit_entry *Class;
  eptr p;

  /* Pick (at most) 'topick' entries from the beginning of each Class
     so that they are also correctly classified by KNN */

  for (Class = classes->head, total = 0; Class != NULL; Class = Class->next) 
    total += Class->freq;

  if ((loca = rewind_entries(data, &p)) == NULL)
    {
      Msg(0, "pick_inside_codes: can't get data");
      return NULL;
    }
  prev = &tmp;
  tmp.next = NULL;
  still = 1;

  ifverbose(1)
    mprint((long) total);

  while ((total) && (loca != NULL)) {
    datalabel = get_entry_label(loca);
    Class = find_hit(classes, datalabel);
    if (Class)
      if (Class->freq > 0) {
	/* test if it is correctly classified */
	if (correct_by_knn(data, loca, knn, find_knn))
	  { 
	    ifverbose(1)
	      mprint((long) total);
	    total--;
	    prev->next = copy_entry(data, loca);
	    if (prev->next == NULL)
	      {
		Msg(0, "pick_inside_codes: can't copy entry");
		return tmp.next;
	      }
	    prev = prev->next;
	    
	    Class->freq--;
	  }
      }
    loca = next_entry(&p);
  }
  
  ifverbose(1)
    {
      mprint((long) 0);
      Msg(0, "");
    }

  return(tmp.next);
}

/* Pick one entry from a given Class. */

struct data_entry *force_pick_code(struct entries *data, int ind)
{
  struct data_entry *prev, *loca, tmp;
  eptr p;

  /* pick one entry from a given Class */

  if ((loca = rewind_entries(data, &p)) == NULL)
    {
      Msg(0, "force_pick_codes: can't get data");
      return NULL;
    }
  prev = &tmp;
  tmp.next = NULL;
  while (loca != NULL) {
    if (get_entry_label(loca) == ind) {
      prev->next = copy_entry(data, loca);
      prev = prev->next;
      break;
    }
    loca = next_entry(&p);
  }

  return(tmp.next);
}

struct mindists *alloc_mindists(void)
{
  struct mindists *md;

  if ((md = (struct mindists *)malloc(sizeof(struct mindists))) == NULL)
    return NULL;
  md->num_classes = 0;
  md->Class = NULL;
  md->dists = NULL;
  md->devs = NULL;
  md->noe = NULL;
  if ((md->classes = new_hitlist()) == NULL)
    {
      free(md);
      return NULL;
    }
  return md;
}

void free_mindists(struct mindists *md)
{
  if (md)
    {
      if (md->classes)
	free_hitlist(md->classes);
      if (md->Class)
	free(md->Class);
      if (md->dists)
	free(md->dists);
      if (md->devs)
	free(md->devs);
      if (md->noe)
	free(md->noe);
      free(md);
    }
}

/* Compute the average shortest distances */

struct mindists *min_distances(struct entries *codes, DIST_FUNCTION *distance)
{

  long nol, i;
  int note, fou, dim;
  float *dists;
  int *Class, *noe;
  float dissf, dist;
  struct data_entry *entr, *ensu, *d;
  eptr p, p2;
  struct hitlist *classes;
  struct hit_entry *h;
  struct mindists *md;

  if (distance == NULL)
    distance = vector_dist_euc;

  if ((md = alloc_mindists()) == NULL)
    return NULL;
  classes = md->classes;
  
  for (d = rewind_entries(codes, &p); d != NULL; d = next_entry(&p))
    add_hit(classes, get_entry_label(d));

  nol = classes->entries; /* number of classes */
  md->num_classes = nol;

  Class = (int*)calloc(nol, sizeof(int));
  if ((md->Class = Class) == NULL)
    {
      free_mindists(md);
      return NULL;
    }
  noe = (int*)calloc(nol, sizeof(int));
  if ((md->noe = noe) == NULL)
    {
      free_mindists(md);
      return NULL;
    }
  dists = (float*)calloc(nol, sizeof(float));
  if ((md->dists = dists) == NULL)
    {
      free_mindists(md);
      return NULL;
    }
  
  dim = codes->dimension;

  for (i = 0, h = classes->head; i < nol; i++, h = h->next) 
    {
      dists[i] = 0.0;
      Class[i] = h->label;
      noe[i] = h->freq;
      entr = rewind_entries(codes, &p);
      p2.parent = p.parent;
      note = 0;
      while (entr != NULL) 
	{
	  if (get_entry_label(entr) == Class[i]) {
	    p2.current = p.current;
	    p2.index = p.index;
	    ensu = next_entry(&p2);
	    dissf = FLT_MAX;
	    fou = 0;
	    while (ensu != NULL)
	      {
		if (get_entry_label(ensu) == Class[i])
		  {
		    fou = 1;
		    dist = distance(ensu, entr, dim);
		    if (dist < dissf)
		      dissf = dist;
		    
		  }
		ensu = next_entry(&p2);
	      }
	    if (fou) 
	      {
		dists[i] += dissf;
		note++;
	      }
	  }
	  entr = next_entry(&p);
	}
      if (note > 0)
	dists[i] /= note;
    }
  
  return(md);
}

/* Comparison routine for the distances (used in qsort) */

int compar(const void *a, const void *b)
{
  if (*(float *)a < *(float *)b)
    return(-1);
  if (*(float *)a > *(float *)b)
    return(1);
  return(0);
}

/* Compute the median of shortest distances */

struct mindists *med_distances(struct entries *codes, DIST_FUNCTION *distance)
{
  long i, nol;
  int not, mnoe, fou, dim;
  int *Class, *noe;
  float *dists;
  float dissf, dist;
  float *meds;
  struct data_entry *entr, *ensu, *d;
  struct hitlist *classes;
  struct hit_entry *h;
  struct mindists *md;
  eptr p, p2;

  dim = codes->dimension;

  if (distance == NULL)
    distance = vector_dist_euc;

  if ((md = alloc_mindists()) == NULL)
    return NULL;
  classes = md->classes;
  
  /* find out number of labels in each Class */
  for (d = rewind_entries(codes, &p); d != NULL; d = next_entry(&p))
    add_hit(classes, get_entry_label(d));

  nol = classes->entries; /* number of classes */
  md->num_classes = nol;

  Class = (int*)calloc(nol, sizeof(int));
  if ((md->Class = Class) == NULL)
    {
      free_mindists(md);
      return NULL;
    }
  noe = (int*)calloc(nol, sizeof(int));
  if ((md->noe = noe) == NULL)
    {
      free_mindists(md);
      return NULL;
    }
  dists = (float*)calloc(nol, sizeof(float));
  if ((md->dists = dists) == NULL)
    {
      free_mindists(md);
      return NULL;
    }
#if 0
  devs = calloc(nol, sizeof(float));
  if ((md->devs = devs) == NULL)
    {
      free_mindists(md);
      return NULL;
    }
#endif

  for (i = 0; i < nol; i++)
    dists[i] = 0.0;

  /* Find the max number of entries in one Class */
  mnoe = classes->head->freq;

  /* Allocate space for the distances (to find the median) */
  meds = (float *) oalloc(sizeof(float) * mnoe);
  
  for (i = 0, h = classes->head; i < nol; i++, h = h->next) 
    {
      dists[i] = 0.0;
      Class[i] = h->label;
      noe[i] = h->freq;
      not = 0;
      entr = rewind_entries(codes, &p);
      p2.parent = p.parent;
      while (entr != NULL) {
	if (get_entry_label(entr) == Class[i]) {
	  p2.current = p.current;
	  p2.index = p.index;
	  ensu = next_entry(&p2);
	  dissf = FLT_MAX;
	  fou = 0;
	  while (ensu != NULL) {
	    if (get_entry_label(ensu) == Class[i])
	      {
		dist = 0.0;
		fou = 1;
		dist = distance(ensu, entr, dim);
		if (dist < dissf) {
		  dissf = dist;
		}
	      }
	    ensu = next_entry(&p2);
	  }
	  if (fou)
	    meds[not++] = dissf;
	}
	entr = next_entry(&p);
      }
      if (not > 0) {
	/* find the median */
	qsort((void *) meds, not, sizeof(float), compar);
	dists[i] = meds[not/2];
      }
    }
  
  ofree(meds);

  return(md);
}

/* Train by lvq1; the nearest codebook vector is modified.  If
   classification is correct, move it towards the input entry; if
   classification is incorrect, move it away from the input entry */

struct entries *lvq1_training(struct teach_params *teach)
{

  long le, total_length, length = teach->length;
  int label, dim;
  int numofe;
  float shortest;
  float talpha;
  struct data_entry *datatmp, *best;
  struct winner_info win;
  VECTOR_ADAPT *adapt_vector = teach->vector_adapt;
  WINNER_FUNCTION *find_winner = teach->winner;
  ALPHA_FUNC *get_alpha = teach->alpha_func;
  struct entries *data = teach->data;
  struct entries *codes = teach->codes;
  struct snapshot_info *snap = teach->snapshot;
  float alpha = teach->alpha;
  eptr p;
  long lensam;
  CSammon *sammon = teach->sammon;

  total_length = length;
  
  dim = codes->dimension;

  if ((datatmp = rewind_entries(data, &p)) == NULL)
    {
      Msg(0, "lvq1_training: can't get data");
      return NULL;
    }

  numofe = data->flags.totlen_known ? data->num_entries : 0;

	if (sammon != NULL)
  		{