/*-----------------------------------------------------    PROGRAM : new_neighbor.c  DATE    : 6/15/94  AUTHOR  : Wasiuddin Wahid, wasi@media.mit.edu  NOTE    : Baback added Bayesian Similarity Metric (7/23/96)  _____________________________________________________  PROGRAM DESCRIPTION HERE  ____________________________________________________*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#include <float.h>#include "util.h"#include "io.h"#define OPTIONS "m:x:k:l:o:n:t:c:a:b:z:p:s:"#define MAX_CHARS 1024#define MAX_NDIM  1024  /* for static storage in bayesian_distance() */char *usage = "\t-m dir_known_faces -x dir_test_faces\n\t\\t\t-k list_known_faces -l list_test_faces\n\t\\t\t-o output_file -t threshold [-n top_n_matches]\n\t\\t\t[-c conf] [-a lower coeff] [-b upper coeff]\n\t\\t\t[-z intra/extra_dir] [-p P0] [-s sigmoid_scale]";char *help = " Nearest Neighbor Pattern Matching\n-m dir_known_faces  \t directory of  known faces \n\-x dir_test_faces   \t directory of test faces \n\-k list_known_faces \t list file of known faces \n\-l list_test_faces  \t list file of test faces\n\-o output_dir       \t output directory\n\-n top_n_matches    \t print out top N matches only (default: print all)\n\-t threshold        \t found flag threshold(default: 10)\n\-c conf             \t confidence factor (default: 1000)\n\-a lower coeff      \t lower coefficient (default: first)\n\-b upper coeff      \t upper coefficient (default: last)\n\-z intra_extra_dir  \t Bayesian metric with intra/extra_kl.bf in dir\n\-p P0               \t intra prior P0  (default = 0.5)\n\-s sigmoid_scale    \t sigmoid scale factor for Bayesian (default = 1.0)\n\n";extern int optind;extern char *optarg;/*------- command line defaults ------- */float conf_factor = 1e3;float sigmoid_scale = 1.0;/* Definition of the structures I will be using :   A tface(test_face) consists of the name of file    containing the test face and a pointer to the    structure the test face and a pointer to the    structure "match"   A match is a structure containing the name of the file   to which the test face is similar, the distance from   that face and a pointer to the next matched face */typedef struct match *Matchptr;typedef struct match{  char *name;  float distance;  Matchptr next;} Match;typedef struct tface {  char *name;  Matchptr similar;} Tface;typedef struct kface{  char *name;  float *coeffs;} Kface;typedef struct bstruct{  float **intra_kl;  float **extra_kl;  float logP0;  float logP1;  float logD0;  float logD1;  int   N;  int   a,b;} Bayesian;  int number_files(char list[]);float find_distance(float *test, float *known, int no);Matchptr add_match(Matchptr root, Matchptr new, int n);void print_match(Tface *faces, int n, int no_files, char out[], float thres, char comline[]);void kill_list(Matchptr list);int empty_list(Matchptr list);int print_file(Tface tfaces, int n, char out[], float thres, int count);float bayesian_distance(float *test, float *known, int N, Bayesian *B);/* globals */int do_bayesian = 0;/*char *strdup(char *s);*//*______________________MAIN____________________________*/main(int argc, char **argv){  int no_files, no_kfiles, total_no_points, no_points;  int file_no, point, i,j, c, n=10, rec, a=1, b=0, count =0;  char *progname, comline[MAX_CHARS];    char known_dir[MAX_CHARS];  char test_dir[MAX_CHARS];  char klist[MAX_CHARS];  char tlist[MAX_CHARS];  char out_file[MAX_CHARS];  char line[MAX_CHARS];  char kfile[MAX_CHARS];  char tfile[MAX_CHARS];  char the_kfile[MAX_CHARS];  FILE *fknown, *ftest, *fklist, *ftlist;  Tface *faces;  Kface *kfaces;  Matchptr a_match;  float *t_points, a_point, dist, thres, *weights, weight;  char intra_extra_dir[MAX_CHARS];  char filename[MAX_CHARS];  Bayesian B_struct;  float P0 = 0.5;  float P1 = 0.5;   /* default equal priors */  float fval; /* Required input flags */  int errflag  = 0;  int inflag   = 0;  int testflag = 0;  int kflag    = 0;  int tflag    = 0;  int outflag  = 0;  int nflag    = 0;  int thresflag= 0;    progname = argv[0];  for (i=0; i<argc; i++){    strcat(comline, argv[i]), strcat(comline, " ");  }  while ( (c = getopt(argc, argv, OPTIONS)) != EOF)    switch(c){    case 'm':      strcpy(known_dir, optarg);      inflag = 1;      break;          case 'x':      strcpy(test_dir, optarg);      testflag = 1;      break;    case 'k':      strcpy(klist, optarg);      kflag = 1;      break;    case 'l':      strcpy(tlist, optarg);      tflag = 1;      break;          case 'o':      strcpy(out_file, optarg);      outflag = 1;      break;    case 'n':      n = atoi(optarg);      nflag = 1;      break;          case 't':      thres = atof(optarg);      thresflag = 1;      break;    case 'c':      conf_factor = atof(optarg);      break;          case 'a':      a = atoi(optarg);      break;          case 'b':      b = atoi(optarg);      break;     case 'z':      strcpy(intra_extra_dir, optarg);      do_bayesian = 1;      break;    case 's':      sigmoid_scale = atof(optarg);      break;         case 'p':      P0 = atof(optarg);      if (P0>1) {	fprintf(stderr,		"ERROR: Prior P0 (%f) must be less than 1\n\n", P0);	exit(0);      }      P1 = 1.0 - P0;      break;    case '?':      errflag = 1;      break;      } /* switch (c){ */    /* Command line check */  if (errflag || !inflag || !testflag || !thresflag || !kflag || !tflag || !outflag){    fprintf(stderr, "\nUSAGE: %s %s\n %s\n\n", progname, usage, help);    exit(1);  }    /* fprintf(stderr, "the n is %i", n); */  /* Calculate no. of test and known faces */  no_files = number_files(tlist);  no_kfiles = number_files(klist);  /* -- default printout is all --- */  if (nflag==0)    n = no_kfiles;    faces = (Tface *) calloc(no_files, sizeof(Tface));  if (faces == NULL){    fprintf(stderr, "\nERROR: Memory cannot be allocated\n\n");    exit(3);  }  kfaces = (Kface *) calloc(no_kfiles, sizeof(Kface));  if (kfaces == NULL) {    fprintf(stderr, "\nERROR: Memory cannot be allocated\n\n");    exit(3);  }  /* Calculate the total_no of eigenvectors & create array of points */   if ( (ftlist = fopen(tlist, "r")) == NULL){    fprintf(stderr, "\nERROR: Input file %s cannot be opened \n\n", tlist);    exit(2);  }  fscanf(ftlist, "%s", line);    while ( ! ( (strncmp(line, "#", 1) !=0) && (strlen(line) > 1) )){    fscanf(ftlist, "%s", line);  }    sprintf(tfile, "%s/%s", test_dir, line);  if ( (ftest = fopen(tfile, "r")) == NULL){    fprintf(stderr, "\nERROR: Input file %s cannot be opened\n\n", tfile);    exit(2);  }  no_points = 0;  while ( (fscanf(ftest, "%s", line)) != EOF){    no_points++;  }  total_no_points = no_points;  t_points=(float *) calloc(no_points, sizeof(float));  if (t_points == NULL){    fprintf(stderr, "\nERROR: Memory could not be allocated\n\n");    exit(3);  }  /*Read in all the known data into the array of kfaces */  if ( (fklist = fopen(klist, "r")) == NULL){    fprintf(stderr, "\nERROR: Input file %s cannot be opene\n\n", klist);    exit(2);  }  file_no = 0;  while ( (fscanf(fklist, "%s", line)) != EOF){    if ( (strncmp(line, "#", 1) != 0) || (strlen(line) > 1)){      kfaces[file_no].name = strdup(line);      kfaces[file_no].coeffs = (float *) calloc(no_points, sizeof(float));      sprintf(kfile, "%s/%s", known_dir, line);      point = 0;      if ( (fknown = fopen(kfile, "r")) == NULL){	fprintf(stderr, "\nERROR: Input file %s cannot be opened", kfile);	exit(2);      }      while ( (fscanf(fknown, "%f", &a_point) != EOF)){	kfaces[file_no].coeffs[point] = a_point;	point++;      }      file_no++;      fclose(fknown);    }  }  fclose(fklist);       /*  If b hasn't been specified then it defaults to the end */  /* i.e. b = no_points                                      */  if (!b){    b = total_no_points;  }    /* the no of points relevant in the distance calculation is */  /* difference between a & b                                 */  /* setup range for bayesian */  if (do_bayesian) {     B_struct.a     = a;      B_struct.b     = b;  }  else     no_points = b-a+1;  /* setup intra_extra stuff */  if (do_bayesian) {        int m,n;    float fval=0;    P0 = P0/(P0+P1);    P1 = P1/(P0+P1); /* make sure priors are ok */    B_struct.logP0 = log(P0);    B_struct.logP1 = log(P1);    /* intra/extra_kl.bf files are MxN matrices with format       1st row is the transpose of the Xmean       rows [2,N+1] are the transpose of eigenvectors U       last row (N+2) is the corresponding eigenvalues  */        /* read intra_kl file */    sprintf(filename, "%s/intra_kl.bf", intra_extra_dir);    B_struct.intra_kl = read_BIN(filename, &m, &n);    B_struct.N = n;    if ((m != n+2)) {      fprintf(stderr,	      "intra_kl.bf dimensions [%d,%d] are not correct, should be [%d,%d]\n\n", m, n, n+2, n);      exit(1);    }    if ((b > n)) {      fprintf(stderr,	      "intra_kl.bf dimensions [%d,%d] don't match range [%d,%d]!\n\n", m, n, a, b);      exit(1);    }    /* read extra_kl file */    sprintf(filename,"%s/extra_kl.bf", intra_extra_dir);    B_struct.extra_kl = read_BIN(filename, &m, &n);    if ((m != n+2)) {      fprintf(stderr,	      "extra_kl.bf dimensions [%d,%d] are not correct, should be [%d,%d]\n\n", m, n, n+2, n);      exit(1);    }    if ((n != B_struct.N)) {      fprintf(stderr,	      "extra_kl.bf dimensions [%d,%d] don't match intra_kl.bf [%d,%d]\n\n", m, n, m, B_struct.N);      exit(2);    }    if ((total_no_points != B_struct.N)) {      fprintf(stderr,	      "intra/extra_kl.bf dimensionality (%d) doesn't match data dimensionality (%d)\n\n", B_struct.N, total_no_points);      exit(3);    }    /* compute log of the denominators (over [a,b] range only!) */    fval = 0;    for (i=B_struct.a; i<=B_struct.b; i++)      fval += log(B_struct.intra_kl[B_struct.N+2][i]);    B_struct.logD0 = 0.5 * fval;    fval = 0;    for (i=B_struct.a; i<=B_struct.b; i++)      fval += log(B_struct.extra_kl[B_struct.N+2][i]);    B_struct.logD1 = 0.5 * fval;      }  a = a-1;     /* To compensate for arrays indexing from zero */  /* For each face in the test_dir, find it's neighbors in the known_dir */  file_no = 0;  rewind(ftlist);  while ( (fscanf(ftlist, "%s", line) != EOF)){    if ( (strncmp(line, "#", 1) != 0) || (strlen(line) > 1)){            /* Initialize face array */      faces[file_no].name = strdup(line);      faces[file_no].similar = NULL;            /* Read coeffs from the test faces */      sprintf(tfile, "%s/%s", test_dir, line);      if ( (ftest = fopen(tfile, "r")) == NULL) {