lvq_pak.cpp

face recognition test source code

/************************************************************************
 *                                                                      *
 *  Program packages 'lvq_pak' and 'som_pak' :                          *
 *                                                                      *
 *  lvq_pak.c                                                           *
 *   -very general routines needed in many places                       *
 *                                                                      *
 *  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 <string.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>
#include "lvq_pak.h"
#include "tools.h"

/* find_winner_euc - finds the winning entry (1 nearest neighbour) in
   codebook using euclidean distance. Information about the winning
   entry is saved in the winner_info structure. Return 1 (the number
   of neighbours) when successful and 0 when winner could not be found
   (for example, all components of data vector have been masked off) */

int find_winner_euc(struct entries *codes, struct data_entry *sample, 
			struct winner_info *win, int knn)
{
  struct data_entry *codetmp;
  int dim, i, masked;
  float diffsf, diff, difference;
  eptr p;

  dim = codes->dimension;
  win->index = -1;
  win->winner = NULL;
  win->diff = -1.0;
  
  /* Go through all code vectors */
  codetmp = rewind_entries(codes, &p);
  diffsf = FLT_MAX;
  
  while (codetmp != NULL) {
    difference = 0.0;
    masked = 0;

    /* Compute the distance between codebook and input entry */
    for (i = 0; i < dim; i++)
      {
	if ((sample->mask != NULL) && (sample->mask[i] != 0))
	  {
	    masked++;
	    continue; /* ignore vector components that have 1 in mask */
	  }
	diff = codetmp->points[i] - sample->points[i];
	difference += diff * diff;
	if (difference > diffsf) break;
      }
    
    if (masked == dim)
      return 0; /* can't calculate winner, empty data vector */
    
    /* If distance is smaller than previous distances */
    if (difference < diffsf) {
      win->winner = codetmp;
      win->index = p.index;
      win->diff = difference;
      diffsf = difference;
    }
    
    codetmp = next_entry(&p);
  }
  
  if (win->index < 0)
    ifverbose(3)
      Msg(0, "find_winner_euc: can't find winner\n");

  return 1; /* number of neighbours */
}

/* find_winner_knn - finds the winning entrys (k nearest neighbours)
   in codebook using euclidean distance. Information about the winning
   entry is saved in the winner_info structures provided by the
   caller. Return k (the number of neighbours) when successful and 0
   when winner could not be found (for example, all components of data
   vector have been masked off) */

int find_winner_knn(struct entries *codes, struct data_entry *sample, 
		    struct winner_info *win, int knn)
{
  struct data_entry *codetmp;
  int dim, i, j, masked;
  float difference, diff;
  eptr p;

  if (knn == 1) /* might be a little faster */
    return find_winner_euc(codes, sample, win, 1);

  dim = codes->dimension;
  
  for (i = 0; i < knn; i++)
    {
      win[i].index = -1;
      win[i].winner = NULL;
      win[i].diff = FLT_MAX;
    }
  /* Go through all code vectors */

  codetmp = rewind_entries(codes, &p);
  
  while (codetmp != NULL) {
    difference = 0.0;
    
    masked = 0;
    /* Compute the distance between codebook and input entry */
    for (i = 0; i < dim; i++)
      {
	/* pitaisiko ottaa huomioon myos codebookissa olevat?? */
	if ((sample->mask != NULL) && (sample->mask[i] != 0))
	  {
	    masked++;
	    continue; /* ignore vector components that have 1 in mask */
	  }
	diff = codetmp->points[i] - sample->points[i];
	difference += diff * diff;
	if (difference > win[knn-1].diff) break;
      }

    if (masked == dim)
      return 0;
    
    /* If distance is smaller than previous distances */
    for (i = 0; (i < knn) && (difference > win[i].diff); i++);

    if (i < knn) 
      {
	for (j = knn - 1; j > i; j--)
	  {
	    win[j].diff = win[j - 1].diff;
	    win[j].index = win[j - 1].index;
	    win[j].winner = win[j - 1].winner;
	  }

	win[i].diff = difference;
	win[i].index = p.index;
	win[i].winner = codetmp;
      }
    
    codetmp = next_entry(&p);
  }
  
  if (win->index < 0)
    ifverbose(3)
      Msg(0, "find_winner_knn: can't find winner\n");

  return knn; /* number of neighbours */
}

/* vector_dist_euc - compute distance between two vectors is euclidean
   metric. Returns < 0 if distance couldn't be calculated (all components
   were masked off */

float vector_dist_euc(struct data_entry *v1, struct data_entry *v2, int dim)
{
  float diff, difference;
  int i, masked = 0;

  difference = 0.0;
  for (i = 0; i < dim; i++)
    {
      if (((v1->mask != NULL) && (v1->mask[i] != 0)) ||
	  ((v2->mask != NULL) && (v2->mask[i] != 0)))
	{
	  masked++;
	  /* ignore vector components that have 1 in mask */
	}
      else
	{
	  diff = v1->points[i] - v2->points[i];
	  difference += diff * diff;
	}
    }

  if (masked == dim)
    return -1;

  return sqrt(difference);
}

/* adapt_vector - move a codebook vector towards another vector */

void adapt_vector(struct data_entry *codetmp, struct data_entry *sample, 
		  int dim, float alpha)
{
  int i;

  for (i = 0; i < dim; i++) 
    if ((sample->mask != NULL) && (sample->mask[i] != 0))
      continue; /* ignore vector components that have 1 in mask */
    else
      codetmp->points[i] += alpha *
	(sample->points[i] - codetmp->points[i]);
  
}

/******************************************************************* 
 * Routines for general usage                                      * 
 *******************************************************************/

/* package errors */

int lvq_errno;

void errormsg(char *msg)
{
  Msg(0, "%s", msg);
}

/* My own free routine */
void ofree(void *data)
{
  if (data != NULL)
    free(data);
}

/* oalloc - my malloc allocation routine with some error checking. Not
   used much any more as it exits if an error occurs. */

void *oalloc(unsigned int len)
{
  void *tmp;

  if ((tmp = malloc(len)) == NULL) 
  {
    Msg(0, "Can't allocate memory");
    Fail(-1);/*THROW(NULL);*/
  }

  return(tmp);
}

/* orealloc - my realloc allocation routine with some error
   checking. Not used much any more as it exits if an error occurs. */

void *orealloc(void *po, unsigned int len)
{
  void *tmp;

  if ((tmp = realloc(po, len)) == NULL) 
  	{
   Msg(0, "Can't reallocate memory");
   Fail(-1);
  	}

  return(tmp);
}


/* Print dots indicating that a job is in progress */
void mprint(long rlen)
{
#if 0

#ifndef time_t
#define time_t long
#endif
  static time_t startt, prevt;
  time_t currt;
  static long totlen = 0;
  long t1, t2;
  int i;

  currt=time(NULL);

  if (!totlen) {
    totlen=rlen;
    startt=currt;
    fprintf(stderr, "               ");
    for (i=0; i<10; i++) fprintf(stderr, "------");
  }

  if (currt!=prevt || !rlen) {
    t1=currt-startt;
    if (rlen!=totlen) t2=(currt-startt)*(float)totlen/(totlen-rlen);
    else t2=0;
    if (t2>9999) {
      t1/=60;
      t2/=60;
      i=0;
    } else i=1;
    fprintf(stderr, "\r%4u/%4u %4s ", (int)t1, (int)t2, i?"sec.":"min.");
    if (totlen) {
      i=(int) (60*(float)(totlen-rlen)/totlen);
      while (i--) fprintf(stderr, ".");
    }
    fflush(stderr);
    prevt=currt;
  }
  if (!rlen) totlen=0;

#endif
}


static unsigned long next = 1;
#define RND_MAX 32767L

/* May define my own random generator */
void osrand(int i)
{