new_neighbor.c

feret人脸图象数据库处理代码

/*-----------------------------------------------------
  
  PROGRAM : new_neighbor.c
  DATE    : 6/15/94
  AUTHOR  : Wasiuddin Wahid, [e-mail]

  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) {