www.pudn.com > Mean-Shift.rar > fams.h
/////////////////////////////////////////////////////////////////////////////
// Name: fams.h
// Purpose: fast adaptive meanshift class and struct
// Author: Ilan Shimshoni
// Modified by: Bogdan Georgescu
// Created: 08/14/2003
// Version: v0.1
/////////////////////////////////////////////////////////////////////////////
#ifndef _FAMS_H
#define _FAMS_H
#ifndef UNIX
#define drand48() (rand()*1.0/RAND_MAX)
#endif
// Algorithm constants
/* Find K L */
// number of points on which test is run
#define FAMS_FKL_NEL 500
// number of times on which same test is run
#define FAMS_FKL_TIMES 10
/* FAMS main algorithm */
// maximum valid K
#define FAMS_MAX_K 70
// maximum valid L
#define FAMS_MAX_L 500
// first hash table block size
#define FAMS_BLOCKSIZE 4096
// second hash table block size
#define FAMS_BLOCKSIZE2 256
// do speedup or not
#define FAMS_DO_SPEEDUP 1
// maximum MS iterations
#define FAMS_MAXITER 100
// weight power
#define FAMS_ALPHA 1.0
/* Prune Modes */
// window size (in 2^16 units) in which modes are joined
#define FAMS_PRUNE_WINDOW 3000
// min number of points assoc to a reported mode
#define FAMS_PRUNE_MINN 40
// max number of modes
#define FAMS_PRUNE_MAXM 100
// max points when considering modes
#define FAMS_PRUNE_MAXP 10000
// divison of mode h
#define FAMS_PRUNE_HDIV 1
#define FAMS_FLOAT_SHIFT 100000.0
void bgLog(const char *varStr, ...)
{
//obtain argument list using ANSI standard...
va_list argList;
va_start(argList, varStr);
//print the output string to stderr using
vfprintf(stdout, varStr, argList);
va_end(argList);
//done.
return;
}
inline int MyMin(int i,int j)
{
return (i>j) ? j : i;
}
inline int MyMax(int i,int j)
{
return (i>j) ? i : j;
}
static time_t timestart;
static time_t timeend;
static void timer_start()
{
timestart = clock();
}
static double timer_stop()
{
timeend = clock();
unsigned long seconds, milliseconds;
seconds = (timeend-timestart)/CLOCKS_PER_SEC;
milliseconds = ((1000*(timeend-timestart))/CLOCKS_PER_SEC) - 1000*seconds;
return seconds + milliseconds/1000.0;
}
static double timer_elapsed(int prnt)
{
timeend = clock();
unsigned long hours=0, minutes=0, seconds=0, milliseconds=0;
seconds = (timeend-timestart)/CLOCKS_PER_SEC;
milliseconds = ((1000*(timeend-timestart))/CLOCKS_PER_SEC) - 1000*seconds;
minutes = seconds/60;
if (minutes == 0)
if (prnt)
printf("elapsed %lu.%03lu seconds. \n", seconds, milliseconds);
else
{
hours = minutes/60;
seconds = seconds - minutes*60;
if (hours == 0)
{
if (prnt)
printf("elapsed %lum%lus%lums\n", minutes, seconds, milliseconds);
}
else
{
minutes = minutes - hours*60;
if (prnt)
printf("elapsed %luh%lum%lus%lums\n", hours, minutes, seconds, milliseconds);
}
}
return hours*3600 + minutes*60 + seconds + milliseconds/1000.0;
}
void bgSort(double* ra, int nVec)
{
unsigned long n, l, ir, i, j;
n = nVec;
double rra;
if (n<2)
return;
l = (n>>1)+1;
ir = n;
for (;;)
{
if (l>1)
{
rra = ra[(--l)-1];
}
else
{
rra = ra[ir-1];
ra[ir-1] = ra[1-1];
if (--ir==1)
{
ra[1-1] = rra;
break;
}
}
i = l;
j = l+l;
while (j<=ir)
{
if (j>1)+1;
ir = n;
for (;;)
{
if (l>1)
{
irra = ira[(--l)-1];
rra = ra[l-1];
}
else
{
irra = ira[ir-1];
rra = ra[ir-1];
ira[ir-1] = ira[1-1];
ra[ir-1] = ra[1-1];
if (--ir==1)
{
ira[1-1] = irra;
ra[1-1] = rra;
break;
}
}
i = l;
j = l+l;
while (j<=ir)
{
if (jj) ? j : i;
}
inline int fams_Max(int i,int j)
{
return (i>j) ? i : j;
}
typedef fams_hash_entry block[Bs];
typedef fams_hash_entry2 block2[Bs2];
class FAMS
{
public:
FAMS(int no_lsh);
~FAMS();
int LoadPoints(char* filename);
void CleanData();
void CleanPoints();
void CleanSelected();
void CleanPrunedModes();
void CleanHash();
void SelectMsPoints(double percent,int jump);
int RunFAMS(int K, int L, int k, double percent, int jump, float width, char* pilot_fn);
void MakeCuts(fams_partition* cuts);
void MakeCutL(fams_partition& cut);
void InitHash(int nk);
int HashFunction(int *cutVals, int whichPartition, int kk,int M=0,int *hjump=NULL);
void AddDataToHash(block HT[],int hs[],fams_point& pt,int where,int Bs,int M,int which,int which2,
int hjump);
void ComputePilot(block *HT,int *hs, fams_partition *cuts, char* pilot_fn);
void GetNearestNeighbours(fams_point& who,block *HT, int *hs,
fams_partition *cuts, fams_res_cont& res, int print,int num_l[]);
void AddDataToRes(block HT[],int hs[],fams_res_cont& res,int where,
int Bs,int M,int which, unsigned short nnres, int which2, int hjump);
unsigned short* FindInHash(block2* HT2,int *hs2,int where,int which,int M2,int hjump);
void InsertIntoHash(block2* HT2,int *hs2,int where,int which,
unsigned short **solution,int M,int hjump);
unsigned short* GetNearestNeighbours2H(unsigned short *who, block*HT, int *hs,
fams_partition* cuts, fams_res_cont& res,
unsigned short **solution, block2 *HT2, int *hs2);
void DoFAMS(block *HT,int *hs, fams_partition *cuts,
block2* HT2, int *hs2);
unsigned int DoMeanShiftAdaptiveIteration(fams_res_cont& res,
unsigned short *old, unsigned short *ret);
void SaveModes(char* fn);
int LoadBandwidths(char* fn);
void SaveBandwidths(char* fn);
int FindKL(int Kmin, int Kmax, int Kjump, int Lmax, int k_neigh, float width, float epsilon, int &K, int &L);
void ComputeRealBandwidths(unsigned int h);
double DoFindKLIteration(int K,int L, float* scores);
void ComputeScores(block *HT,int *hs, fams_partition *cuts, float* scores);
int PruneModes(int hprune, int npmin);
void SavePrunedModes(char* fn);
//Produce the boolean vector of a data point with a partition
inline void EvalCutRes(fams_point& in_pt, fams_partition& in_part,int in_cut_res[])
{
for(int in_i=0; in_i= in_part[in_i].where_;
}
//Produce the boolean vector of a ms data point with a partition
inline void EvalCutRes(unsigned short *in_dat, fams_partition& in_part,int in_cut_res[])
{
for(int in_i=0; in_i= in_part[in_i].where_;
}
// return a prime number greater than minp
static int GetPrime(int minp)
{
int i,j;
for(i=minp%2==0? minp+1 :minp; ; i+=2)
{
int sqt = (int)sqrt(i);
if(i % 2==0)
continue;
for(j=3; j= sqt)
return i;
}
return -1;
};
// distance in L1 between two data elements
inline unsigned int DistL1(fams_point& in_pt1, fams_point& in_pt2)
{
int in_i;
unsigned int in_res=0;
for(in_i=0; in_i