balance.cpp

face recognition test source code

/************************************************************************
 *                                                                      *
 *  Program package 'lvq_pak':                                          *
 *                                                                      *
 *  balance.c                                                           *
 *  -balances the number of entries in codebook by shortest distances   *
 *                                                                      *
 *  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 "lvq_pak.h"
#include "lvq_rout.h"
#include "tools.h"
#include "labels.h"
      
#include "lvq.h"
#include "matlvq.h"

#define BAL 1.3

static char *usage[] = {
  "balance - balances the number of entries in codebook by shortest distances\n",
  "Required parameters:\n",
  "  -cin filename         input codebook file\n",
  "  -din filename         input data\n",
  "  -cout filename        output codebook filename\n",
  "Optional parameters:\n",
  "  -knn N                use N nearest neighbours\n", 
  "  -rand integer         seed for random number generator. 0 is current time\n",
  NULL};

struct entries *balance_codes(struct teach_params *teach, char *outfile)
{
  long nod, nol, i;
  int label;
  int *noe, *diff, *Class;
  int note, knn = teach->knn;
  float aver;
  float *dists;
  struct data_entry *entr, *tlab, tmp, *prev;
  struct entries *red_codes;
  struct entries *codes = teach->codes, *data = teach->data;
  struct mindists *md = NULL;
  DIST_FUNCTION *distance = teach->dist;
  struct hitlist *more;
  WINNER_FUNCTION *find_knn = teach->winner;
  eptr p;

  nol = number_of_labels();

  /* Compute the medians of the shortest distances from each entry to
     its nearest entry of the same Class */

  ifverbose(2)
    Msg(0, "Medians of the shortest distances are computed");
  md = med_distances(codes, distance);

  /* If serious imbalance exists, add entries to Classes where
     distances are large, and remove them from Classes where distances
     are small */

  nol = md->num_classes;
  noe = md->noe;
  dists = md->dists;
  Class = md->Class;

  diff = (int *) oalloc(sizeof(int) * nol);
  for (i = 0; i < nol; i++) {
    diff[i] = 0;
  }

  aver = 0.0;
  note = 0;
  for (i = 0; i < nol; i++) {
    if (noe[i] > 1) {
      aver += dists[i];
      note++;
    }
  }
  aver /= note;

  note = 0;
  ifverbose(2)
    Msg(0, "Medians of different classes are compared");
  for (i = 0; i < nol; i++) {
    if ((aver > BAL * dists[i]) && (noe[i] > 1)) {
      diff[i]--;
      note++;
    }
    if (BAL * aver < dists[i]) {
      diff[i]++;
      note--;
    }
  }

  /* Force-pick one codebook vector for each missing Class */
  for (i = 0; i < nol; i++) {
    if (noe[i] == 0) {
      entr = force_pick_code(data, i);

      tlab = codes->entry;
      while (tlab->next != NULL)
        tlab = tlab ->next;
      tlab->next = entr;
      codes->num_entries++;
      noe[i] = 1;
      note--;
    }
  }

  /* If there was net increase or decrease in number of entry */
  for (i = 0; i < nol; i++) {
    if ((aver > BAL * dists[i]) && ((noe[i]+diff[i]) > 1)) {
      if (note < 0) {
        diff[i]--;
        note++;
      }
    }
    if (BAL * aver < dists[i]) {
      if (note > 0) {
        diff[i]++;
        note--;
      }
    }
  }

  ifverbose(1)
    Msg(0, "Some codebook vectors are removed");
  /* Now remove entry from those classes where diff shows negative */

  entr = codes->entry;
  tmp.next = entr;
  prev = &tmp;
  while (entr != NULL) {

    label = get_entry_label(entr);
    for (i = 0; i < nol; i++)
      if (Class[i] == label)
	break;

    if (diff[i] < 0) {
      diff[i]++;
      tlab = entr;
      entr = entr->next;
      prev->next = entr;
      tlab->next = NULL;
      free_entry(tlab);
      codes->num_entries--;
    }
    else
      {
	prev = entr;
	entr = entr->next;
      }
  }

  codes->entry = tmp.next;

  ifverbose(1)
    Msg(0, "Some new codebook vectors are picked");
  /* Pick the requested number of additional codes for each Class */

  more = new_hitlist();
  for (i = 0; i < nol; i++)
    {
      while (diff[i] > 0)
	{
	  add_hit(more, Class[i]); 
	  diff[i]--;
	}
    }
  
  entr = pick_inside_codes(more, data, knn, find_knn);
  free_hitlist(more);

  /* Add new entries to the list */
  tlab = codes->entry;
  while (tlab->next != NULL)
    tlab = tlab->next;
  tlab->next = entr;
  /* laske montako uutta */

  ifverbose(1)
    Msg(0, "Codebook vectors are redistributed");

  rewind_entries(data, &p);
  nod = data->num_entries; /* number of data vectors */
  teach->length = nod;
  teach->alpha = 0.3;
  red_codes = olvq1_training(teach, NULL, outfile);
  if (red_codes == NULL)
    return NULL;

  /* Display the medians of the shortest distances */
  ifverbose(2)
    Msg(0, "Medians of the shortest distances are computed");

  free_mindists(md); /* free old information */
  md = med_distances(red_codes, distance);
  nol = md->num_classes;
  noe = md->noe;
  dists = md->dists;
  Class = md->Class;

  for (i = 0; i < nol; i++) {
    if (verbose(1) > 0)
      Msg(0, "In Class %9s %3d units, min dist.: %.3f",
	     find_conv_to_lab(Class[i]), noe[i], dists[i]);
  }

  if (md)
    free_mindists(md);

  return(red_codes);
}

/*********************************************************************************************
* The function balance adjusts the numbers of codebook vectors so that the medians of the 
* shortest distances between the codebook vectors in all classes are equalized.
*
* This function needs : pdata, pcode, knn, and randomize
* Its output is pcode.
*********************************************************************************************/
int balance(PLVQPARAMS params)
	{
	struct teach_params tparams;
	struct entries *pdata, *pcode;
	int ret;
	
	init_random(params->randomize);
	
	ret = MattoEntries(&pdata, params->pdata);
	if (ret < 0)
		return ret;

	ret = MattoEntries(&pcode, params->pcode);
	if (ret < 0)
		return ret;

	tparams.knn = params->knn;
	set_teach_params(&tparams, pcode, pdata, 0);
	tparams.winner = find_winner_knn;
	
	pcode = balance_codes(&tparams, NULL/*does not write the result ionto any file*/);
	if (pcode == NULL)
		{
		Msg(0, "Failed to initialize codes");
		return -1;
		}
	
	DeleteEntries(pdata);

	ret = EntriestoMat(&(params->pcode), pcode);
	if (ret < 0)
		{
		DeleteEntries(pcode);
		return ret;
		}
	DeleteEntries(pcode);
	
	return 0;
	}