tesseract  3.04.00
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
cluster.h File Reference
#include "kdtree.h"
#include "oldlist.h"

Go to the source code of this file.

Classes

struct  sample
 
struct  CLUSTERCONFIG
 
union  FLOATUNION
 
struct  PROTOTYPE
 
struct  CLUSTERER
 
struct  SAMPLELIST
 

Macros

#define MINBUCKETS   5
 
#define MAXBUCKETS   39
 
#define InitSampleSearch(S, C)   (((C)==NULL)?(S=NIL_LIST):(S=push(NIL_LIST,(C))))
 
#define ALREADYCLUSTERED   4000
 

Typedefs

typedef struct sample CLUSTER
 
typedef CLUSTER SAMPLE
 

Enumerations

enum  PROTOSTYLE { spherical, elliptical, mixed, automatic }
 
enum  DISTRIBUTION { normal, uniform, D_random, DISTRIBUTION_COUNT }
 

Functions

CLUSTERERMakeClusterer (inT16 SampleSize, const PARAM_DESC ParamDesc[])
 
SAMPLEMakeSample (CLUSTERER *Clusterer, const FLOAT32 *Feature, inT32 CharID)
 
LIST ClusterSamples (CLUSTERER *Clusterer, CLUSTERCONFIG *Config)
 
void FreeClusterer (CLUSTERER *Clusterer)
 
void FreeProtoList (LIST *ProtoList)
 
void FreePrototype (void *arg)
 
CLUSTERNextSample (LIST *SearchState)
 
FLOAT32 Mean (PROTOTYPE *Proto, uinT16 Dimension)
 
FLOAT32 StandardDeviation (PROTOTYPE *Proto, uinT16 Dimension)
 
inT32 MergeClusters (inT16 N, PARAM_DESC ParamDesc[], inT32 n1, inT32 n2, FLOAT32 m[], FLOAT32 m1[], FLOAT32 m2[])
 

Macro Definition Documentation

#define ALREADYCLUSTERED   4000

Definition at line 133 of file cluster.h.

#define InitSampleSearch (   S,
 
)    (((C)==NULL)?(S=NIL_LIST):(S=push(NIL_LIST,(C))))

Definition at line 105 of file cluster.h.

#define MAXBUCKETS   39

Definition at line 27 of file cluster.h.

#define MINBUCKETS   5

Definition at line 26 of file cluster.h.

Typedef Documentation

typedef struct sample CLUSTER
typedef CLUSTER SAMPLE

Definition at line 42 of file cluster.h.

Enumeration Type Documentation

Enumerator
normal 
uniform 
D_random 
DISTRIBUTION_COUNT 

Definition at line 58 of file cluster.h.

enum PROTOSTYLE
Enumerator
spherical 
elliptical 
mixed 
automatic 

Definition at line 44 of file cluster.h.

44  {
46 } PROTOSTYLE;
Definition: cluster.h:45
PROTOSTYLE
Definition: cluster.h:44

Function Documentation

LIST ClusterSamples ( CLUSTERER Clusterer,
CLUSTERCONFIG Config 
)

ClusterSamples *********************************************************** Parameters: Clusterer data struct containing samples to be clustered Config parameters which control clustering process Operation: This routine first checks to see if the samples in this clusterer have already been clustered before; if so, it does not bother to recreate the cluster tree. It simply recomputes the prototypes based on the new Config info. If the samples have not been clustered before, the samples in the KD tree are formed into a cluster tree and then the prototypes are computed from the cluster tree. In either case this routine returns a pointer to a list of prototypes that best represent the samples given the constraints specified in Config. Return: Pointer to a list of prototypes Exceptions: None History: 5/29/89, DSJ, Created.

Definition at line 508 of file cluster.cpp.

508  {
509  //only create cluster tree if samples have never been clustered before
510  if (Clusterer->Root == NULL)
511  CreateClusterTree(Clusterer);
512 
513  //deallocate the old prototype list if one exists
514  FreeProtoList (&Clusterer->ProtoList);
515  Clusterer->ProtoList = NIL_LIST;
516 
517  //compute prototypes starting at the root node in the tree
518  ComputePrototypes(Clusterer, Config);
519  return (Clusterer->ProtoList);
520 } // ClusterSamples
void FreeProtoList(LIST *ProtoList)
Definition: cluster.cpp:564
CLUSTER * Root
Definition: cluster.h:91
LIST ProtoList
Definition: cluster.h:92
void ComputePrototypes(CLUSTERER *Clusterer, CLUSTERCONFIG *Config)
Definition: cluster.cpp:931
#define NIL_LIST
Definition: oldlist.h:126
void CreateClusterTree(CLUSTERER *Clusterer)
Definition: cluster.cpp:698
#define NULL
Definition: host.h:144
void FreeClusterer ( CLUSTERER Clusterer)

FreeClusterer ************************************************************* Parameters: Clusterer pointer to data structure to be freed Operation: This routine frees all of the memory allocated to the specified data structure. It will not, however, free the memory used by the prototype list. The pointers to the clusters for each prototype in the list will be set to NULL to indicate that the cluster data structures no longer exist. Any sample lists that have been obtained via calls to GetSamples are no longer valid. Return: None Exceptions: None History: 6/6/89, DSJ, Created.

Definition at line 536 of file cluster.cpp.

536  {
537  if (Clusterer != NULL) {
538  memfree (Clusterer->ParamDesc);
539  if (Clusterer->KDTree != NULL)
540  FreeKDTree (Clusterer->KDTree);
541  if (Clusterer->Root != NULL)
542  FreeCluster (Clusterer->Root);
543  // Free up all used buckets structures.
544  for (int d = 0; d < DISTRIBUTION_COUNT; ++d) {
545  for (int c = 0; c < MAXBUCKETS + 1 - MINBUCKETS; ++c)
546  if (Clusterer->bucket_cache[d][c] != NULL)
547  FreeBuckets(Clusterer->bucket_cache[d][c]);
548  }
549 
550  memfree(Clusterer);
551  }
552 } // FreeClusterer
void FreeBuckets(BUCKETS *Buckets)
Definition: cluster.cpp:2252
#define MINBUCKETS
Definition: cluster.h:26
void FreeCluster(CLUSTER *Cluster)
Definition: cluster.cpp:2266
BUCKETS * bucket_cache[DISTRIBUTION_COUNT][MAXBUCKETS+1-MINBUCKETS]
Definition: cluster.h:95
KDTREE * KDTree
Definition: cluster.h:90
void FreeKDTree(KDTREE *Tree)
Definition: kdtree.cpp:346
CLUSTER * Root
Definition: cluster.h:91
PARAM_DESC * ParamDesc
Definition: cluster.h:88
#define MAXBUCKETS
Definition: cluster.h:27
void memfree(void *element)
Definition: freelist.cpp:30
#define NULL
Definition: host.h:144
void FreeProtoList ( LIST ProtoList)

FreeProtoList ************************************************************ Parameters: ProtoList pointer to list of prototypes to be freed Operation: This routine frees all of the memory allocated to the specified list of prototypes. The clusters which are pointed to by the prototypes are not freed. Return: None Exceptions: None History: 6/6/89, DSJ, Created.

Definition at line 564 of file cluster.cpp.

564  {
565  destroy_nodes(*ProtoList, FreePrototype);
566 } // FreeProtoList
void destroy_nodes(LIST list, void_dest destructor)
Definition: oldlist.cpp:204
void FreePrototype(void *arg)
Definition: cluster.cpp:579
void FreePrototype ( void *  arg)

FreePrototype ************************************************************ Parameters: Prototype prototype data structure to be deallocated Operation: This routine deallocates the memory consumed by the specified prototype and modifies the corresponding cluster so that it is no longer marked as a prototype. The cluster is NOT deallocated by this routine. Return: None Exceptions: None History: 5/30/89, DSJ, Created.

Definition at line 579 of file cluster.cpp.

579  { //PROTOTYPE *Prototype)
580  PROTOTYPE *Prototype = (PROTOTYPE *) arg;
581 
582  // unmark the corresponding cluster (if there is one
583  if (Prototype->Cluster != NULL)
584  Prototype->Cluster->Prototype = FALSE;
585 
586  // deallocate the prototype statistics and then the prototype itself
587  if (Prototype->Distrib != NULL)
588  memfree (Prototype->Distrib);
589  if (Prototype->Mean != NULL)
590  memfree (Prototype->Mean);
591  if (Prototype->Style != spherical) {
592  if (Prototype->Variance.Elliptical != NULL)
593  memfree (Prototype->Variance.Elliptical);
594  if (Prototype->Magnitude.Elliptical != NULL)
595  memfree (Prototype->Magnitude.Elliptical);
596  if (Prototype->Weight.Elliptical != NULL)
597  memfree (Prototype->Weight.Elliptical);
598  }
599  memfree(Prototype);
600 } // FreePrototype
DISTRIBUTION * Distrib
Definition: cluster.h:77
FLOATUNION Variance
Definition: cluster.h:81
FLOAT32 * Mean
Definition: cluster.h:78
FLOATUNION Weight
Definition: cluster.h:83
FLOATUNION Magnitude
Definition: cluster.h:82
FLOAT32 * Elliptical
Definition: cluster.h:64
CLUSTER * Cluster
Definition: cluster.h:76
unsigned Prototype
Definition: cluster.h:34
#define FALSE
Definition: capi.h:29
unsigned Style
Definition: cluster.h:74
void memfree(void *element)
Definition: freelist.cpp:30
#define NULL
Definition: host.h:144
CLUSTERER* MakeClusterer ( inT16  SampleSize,
const PARAM_DESC  ParamDesc[] 
)

MakeClusterer ********************************************************** Parameters: SampleSize number of dimensions in feature space ParamDesc description of each dimension Operation: This routine creates a new clusterer data structure, initializes it, and returns a pointer to it. Return: pointer to the new clusterer data structure Exceptions: None History: 5/29/89, DSJ, Created.

Definition at line 399 of file cluster.cpp.

399  {
400  CLUSTERER *Clusterer;
401  int i;
402 
403  // allocate main clusterer data structure and init simple fields
404  Clusterer = (CLUSTERER *) Emalloc (sizeof (CLUSTERER));
405  Clusterer->SampleSize = SampleSize;
406  Clusterer->NumberOfSamples = 0;
407  Clusterer->NumChar = 0;
408 
409  // init fields which will not be used initially
410  Clusterer->Root = NULL;
411  Clusterer->ProtoList = NIL_LIST;
412 
413  // maintain a copy of param descriptors in the clusterer data structure
414  Clusterer->ParamDesc =
415  (PARAM_DESC *) Emalloc (SampleSize * sizeof (PARAM_DESC));
416  for (i = 0; i < SampleSize; i++) {
417  Clusterer->ParamDesc[i].Circular = ParamDesc[i].Circular;
418  Clusterer->ParamDesc[i].NonEssential = ParamDesc[i].NonEssential;
419  Clusterer->ParamDesc[i].Min = ParamDesc[i].Min;
420  Clusterer->ParamDesc[i].Max = ParamDesc[i].Max;
421  Clusterer->ParamDesc[i].Range = ParamDesc[i].Max - ParamDesc[i].Min;
422  Clusterer->ParamDesc[i].HalfRange = Clusterer->ParamDesc[i].Range / 2;
423  Clusterer->ParamDesc[i].MidRange =
424  (ParamDesc[i].Max + ParamDesc[i].Min) / 2;
425  }
426 
427  // allocate a kd tree to hold the samples
428  Clusterer->KDTree = MakeKDTree (SampleSize, ParamDesc);
429 
430  // Initialize cache of histogram buckets to minimize recomputing them.
431  for (int d = 0; d < DISTRIBUTION_COUNT; ++d) {
432  for (int c = 0; c < MAXBUCKETS + 1 - MINBUCKETS; ++c)
433  Clusterer->bucket_cache[d][c] = NULL;
434  }
435 
436  return Clusterer;
437 } // MakeClusterer
FLOAT32 Min
Definition: ocrfeatures.h:49
#define MINBUCKETS
Definition: cluster.h:26
BUCKETS * bucket_cache[DISTRIBUTION_COUNT][MAXBUCKETS+1-MINBUCKETS]
Definition: cluster.h:95
KDTREE * KDTree
Definition: cluster.h:90
FLOAT32 HalfRange
Definition: ocrfeatures.h:52
inT32 NumberOfSamples
Definition: cluster.h:89
FLOAT32 MidRange
Definition: ocrfeatures.h:53
CLUSTER * Root
Definition: cluster.h:91
inT8 NonEssential
Definition: ocrfeatures.h:48
inT32 NumChar
Definition: cluster.h:93
inT8 Circular
Definition: ocrfeatures.h:47
LIST ProtoList
Definition: cluster.h:92
void * Emalloc(int Size)
Definition: emalloc.cpp:35
#define NIL_LIST
Definition: oldlist.h:126
PARAM_DESC * ParamDesc
Definition: cluster.h:88
FLOAT32 Range
Definition: ocrfeatures.h:51
#define MAXBUCKETS
Definition: cluster.h:27
#define NULL
Definition: host.h:144
KDTREE * MakeKDTree(inT16 KeySize, const PARAM_DESC KeyDesc[])
Definition: kdtree.cpp:184
inT16 SampleSize
Definition: cluster.h:87
FLOAT32 Max
Definition: ocrfeatures.h:50
SAMPLE* MakeSample ( CLUSTERER Clusterer,
const FLOAT32 Feature,
inT32  CharID 
)

MakeSample *********************************************************** Parameters: Clusterer clusterer data structure to add sample to Feature feature to be added to clusterer CharID unique ident. of char that sample came from Operation: This routine creates a new sample data structure to hold the specified feature. This sample is added to the clusterer data structure (so that it knows which samples are to be clustered later), and a pointer to the sample is returned to the caller. Return: Pointer to the new sample data structure Exceptions: ALREADYCLUSTERED MakeSample can't be called after ClusterSamples has been called History: 5/29/89, DSJ, Created.

Definition at line 454 of file cluster.cpp.

455  {
456  SAMPLE *Sample;
457  int i;
458 
459  // see if the samples have already been clustered - if so trap an error
460  if (Clusterer->Root != NULL)
462  "Can't add samples after they have been clustered");
463 
464  // allocate the new sample and initialize it
465  Sample = (SAMPLE *) Emalloc (sizeof (SAMPLE) +
466  (Clusterer->SampleSize -
467  1) * sizeof (FLOAT32));
468  Sample->Clustered = FALSE;
469  Sample->Prototype = FALSE;
470  Sample->SampleCount = 1;
471  Sample->Left = NULL;
472  Sample->Right = NULL;
473  Sample->CharID = CharID;
474 
475  for (i = 0; i < Clusterer->SampleSize; i++)
476  Sample->Mean[i] = Feature[i];
477 
478  // add the sample to the KD tree - keep track of the total # of samples
479  Clusterer->NumberOfSamples++;
480  KDStore (Clusterer->KDTree, Sample->Mean, (char *) Sample);
481  if (CharID >= Clusterer->NumChar)
482  Clusterer->NumChar = CharID + 1;
483 
484  // execute hook for monitoring clustering operation
485  // (*SampleCreationHook)( Sample );
486 
487  return (Sample);
488 } // MakeSample
struct sample * Left
Definition: cluster.h:36
float FLOAT32
Definition: host.h:111
unsigned Clustered
Definition: cluster.h:33
unsigned SampleCount
Definition: cluster.h:35
struct sample * Right
Definition: cluster.h:37
KDTREE * KDTree
Definition: cluster.h:90
inT32 NumberOfSamples
Definition: cluster.h:89
void DoError(int Error, const char *Message)
Definition: danerror.cpp:32
FLOAT32 Mean[1]
Definition: cluster.h:39
CLUSTER * Root
Definition: cluster.h:91
#define ALREADYCLUSTERED
Definition: cluster.h:133
inT32 NumChar
Definition: cluster.h:93
void KDStore(KDTREE *Tree, FLOAT32 *Key, void *Data)
Definition: kdtree.cpp:209
void * Emalloc(int Size)
Definition: emalloc.cpp:35
unsigned Prototype
Definition: cluster.h:34
#define FALSE
Definition: capi.h:29
Definition: cluster.h:32
inT32 CharID
Definition: cluster.h:38
#define NULL
Definition: host.h:144
inT16 SampleSize
Definition: cluster.h:87
FLOAT32 Mean ( PROTOTYPE Proto,
uinT16  Dimension 
)

Mean *********************************************************** Parameters: Proto prototype to return mean of Dimension dimension whose mean is to be returned Operation: This routine returns the mean of the specified prototype in the indicated dimension. Return: Mean of Prototype in Dimension Exceptions: none History: 7/6/89, DSJ, Created.

Definition at line 643 of file cluster.cpp.

643  {
644  return (Proto->Mean[Dimension]);
645 } // Mean
FLOAT32 * Mean
Definition: cluster.h:78
inT32 MergeClusters ( inT16  N,
PARAM_DESC  ParamDesc[],
inT32  n1,
inT32  n2,
FLOAT32  m[],
FLOAT32  m1[],
FLOAT32  m2[] 
)

MergeClusters ************************************************************ Parameters: N # of dimensions (size of arrays) ParamDesc array of dimension descriptions n1, n2 number of samples in each old cluster m array to hold mean of new cluster m1, m2 arrays containing means of old clusters Operation: This routine merges two clusters into one larger cluster. To do this it computes the number of samples in the new cluster and the mean of the new cluster. The ParamDesc information is used to ensure that circular dimensions are handled correctly. Return: The number of samples in the new cluster. Exceptions: None History: 5/31/89, DSJ, Created.

Definition at line 886 of file cluster.cpp.

891  {
892  inT32 i, n;
893 
894  n = n1 + n2;
895  for (i = N; i > 0; i--, ParamDesc++, m++, m1++, m2++) {
896  if (ParamDesc->Circular) {
897  // if distance between means is greater than allowed
898  // reduce upper point by one "rotation" to compute mean
899  // then normalize the mean back into the accepted range
900  if ((*m2 - *m1) > ParamDesc->HalfRange) {
901  *m = (n1 * *m1 + n2 * (*m2 - ParamDesc->Range)) / n;
902  if (*m < ParamDesc->Min)
903  *m += ParamDesc->Range;
904  }
905  else if ((*m1 - *m2) > ParamDesc->HalfRange) {
906  *m = (n1 * (*m1 - ParamDesc->Range) + n2 * *m2) / n;
907  if (*m < ParamDesc->Min)
908  *m += ParamDesc->Range;
909  }
910  else
911  *m = (n1 * *m1 + n2 * *m2) / n;
912  }
913  else
914  *m = (n1 * *m1 + n2 * *m2) / n;
915  }
916  return n;
917 } // MergeClusters
int inT32
Definition: host.h:102
CLUSTER* NextSample ( LIST SearchState)

NextSample ************************************************************ Parameters: SearchState ptr to list containing clusters to be searched Operation: This routine is used to find all of the samples which belong to a cluster. It starts by removing the top cluster on the cluster list (SearchState). If this cluster is a leaf it is returned. Otherwise, the right subcluster is pushed on the list and we continue the search in the left subcluster. This continues until a leaf is found. If all samples have been found, NULL is returned. InitSampleSearch() must be called before NextSample() to initialize the search. Return: Pointer to the next leaf cluster (sample) or NULL. Exceptions: None History: 6/16/89, DSJ, Created.

Definition at line 618 of file cluster.cpp.

618  {
619  CLUSTER *Cluster;
620 
621  if (*SearchState == NIL_LIST)
622  return (NULL);
623  Cluster = (CLUSTER *) first_node (*SearchState);
624  *SearchState = pop (*SearchState);
625  while (TRUE) {
626  if (Cluster->Left == NULL)
627  return (Cluster);
628  *SearchState = push (*SearchState, Cluster->Right);
629  Cluster = Cluster->Left;
630  }
631 } // NextSample
struct sample * Left
Definition: cluster.h:36
#define first_node(l)
Definition: oldlist.h:139
struct sample * Right
Definition: cluster.h:37
#define NIL_LIST
Definition: oldlist.h:126
Definition: cluster.h:32
#define TRUE
Definition: capi.h:28
LIST push(LIST list, void *element)
Definition: oldlist.cpp:323
#define NULL
Definition: host.h:144
LIST pop(LIST list)
Definition: oldlist.cpp:305
FLOAT32 StandardDeviation ( PROTOTYPE Proto,
uinT16  Dimension 
)

StandardDeviation ************************************************* Parameters: Proto prototype to return standard deviation of Dimension dimension whose stddev is to be returned Operation: This routine returns the standard deviation of the prototype in the indicated dimension. Return: Standard deviation of Prototype in Dimension Exceptions: none History: 7/6/89, DSJ, Created.

Definition at line 657 of file cluster.cpp.

657  {
658  switch (Proto->Style) {
659  case spherical:
660  return ((FLOAT32) sqrt ((double) Proto->Variance.Spherical));
661  case elliptical:
662  return ((FLOAT32)
663  sqrt ((double) Proto->Variance.Elliptical[Dimension]));
664  case mixed:
665  switch (Proto->Distrib[Dimension]) {
666  case normal:
667  return ((FLOAT32)
668  sqrt ((double) Proto->Variance.Elliptical[Dimension]));
669  case uniform:
670  case D_random:
671  return (Proto->Variance.Elliptical[Dimension]);
672  case DISTRIBUTION_COUNT:
673  ASSERT_HOST(!"Distribution count not allowed!");
674  }
675  }
676  return 0.0f;
677 } // StandardDeviation
float FLOAT32
Definition: host.h:111
DISTRIBUTION * Distrib
Definition: cluster.h:77
FLOAT32 Spherical
Definition: cluster.h:63
FLOATUNION Variance
Definition: cluster.h:81
Definition: cluster.h:59
#define ASSERT_HOST(x)
Definition: errcode.h:84
FLOAT32 * Elliptical
Definition: cluster.h:64
Definition: cluster.h:45
unsigned Style
Definition: cluster.h:74