Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
commontraining.cpp
Go to the documentation of this file.
1 // Copyright 2008 Google Inc. All Rights Reserved.
2 // Author: scharron@google.com (Samuel Charron)
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 // http://www.apache.org/licenses/LICENSE-2.0
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #include "commontraining.h"
15 
16 #ifndef USE_STD_NAMESPACE
17 #include "base/init_google.h"
18 #include "base/commandlineflags.h"
19 #endif
20 #include "allheaders.h"
21 #include "ccutil.h"
22 #include "classify.h"
23 #include "oldlist.h"
24 #include "globals.h"
25 #include "mf.h"
26 #include "clusttool.h"
27 #include "cluster.h"
28 #include "tessopt.h"
29 #include "efio.h"
30 #include "emalloc.h"
31 #include "featdefs.h"
32 #include "fontinfo.h"
33 #include "intfeaturespace.h"
34 #include "mastertrainer.h"
35 #include "tessdatamanager.h"
36 #include "tprintf.h"
37 #include "freelist.h"
38 #include "params.h"
39 #include "shapetable.h"
40 #include "unicity_table.h"
41 
42 #include <math.h>
43 
44 using tesseract::CCUtil;
49 
50 // Global Variables.
51 // global variable to hold configuration parameters to control clustering
52 // -M 0.625 -B 0.05 -I 1.0 -C 1e-6.
53 CLUSTERCONFIG Config = { elliptical, 0.625, 0.05, 1.0, 1e-6, 0 };
54 
55 INT_PARAM_FLAG(debug_level, 0, "Level of Trainer debugging");
56 INT_PARAM_FLAG(load_images, 0, "Load images with tr files");
57 STRING_PARAM_FLAG(configfile, "", "File to load more configs from");
58 STRING_PARAM_FLAG(D, "", "Directory to write output files to");
59 STRING_PARAM_FLAG(F, "font_properties", "File listing font properties");
60 STRING_PARAM_FLAG(X, "", "File listing font xheights");
61 STRING_PARAM_FLAG(U, "unicharset", "File to load unicharset from");
62 STRING_PARAM_FLAG(O, "", "File to write unicharset to");
63 STRING_PARAM_FLAG(input_trainer, "", "File to load trainer from");
64 STRING_PARAM_FLAG(output_trainer, "", "File to write trainer to");
65 STRING_PARAM_FLAG(test_ch, "", "UTF8 test character string");
66 
67 // The usage strings are different as the DEFINE_* flags are available on
68 // the command line, but the *_VAR flags are set through a config file with
69 // some of them available through special command-line args.
70 #ifndef USE_STD_NAMESPACE
71 const char* kUsage = "[flags] [ .tr files ... ]\n";
72 #else
73 const char* kUsage = "[-c configfile]\n"
74  "\t[-D Directory]\n"
75  "\t[-M MinSamples] [-B MaxBad] [-I Independence] [-C Confidence]\n"
76  "\t[-U InputUnicharset]\n"
77  "\t[-O OutputUnicharset]\n"
78  "\t[-F FontInfoFile]\n"
79  "\t[-X InputXHeightsFile]\n"
80  "\t[-S InputShapeTable]\n"
81  "\t[ .tr files ... ]\n";
82 #endif
83 
86 
87 /*---------------------------------------------------------------------------*/
88 void ParseArguments(int* argc, char ***argv) {
89 /*
90  ** Parameters:
91  ** argc number of command line arguments to parse
92  ** argv command line arguments
93  ** Globals:
94  ** ShowSignificantProtos flag controlling proto display
95  ** ShowInsignificantProtos flag controlling proto display
96  ** Config current clustering parameters
97  ** tessoptarg, tessoptind defined by tessopt sys call
98  ** Argc, Argv global copies of argc and argv
99  ** Operation:
100  ** This routine parses the command line arguments that were
101  ** passed to the program. The legal arguments are shown in the usage
102  ** message below:
103 
104  ** Return: none
105  ** Exceptions: Illegal options terminate the program.
106  ** History: 7/24/89, DSJ, Created.
107  */
108 #ifndef USE_STD_NAMESPACE
109  InitGoogle(kUsage, argc, argv, true);
110  tessoptind = 1;
111 #else
112  int Option;
113  int ParametersRead;
114  BOOL8 Error;
115 
116  Error = FALSE;
117  while ((Option = tessopt(*argc, *argv, "F:O:U:D:C:I:M:B:S:X:c:")) != EOF) {
118  switch (Option) {
119  case 'C':
120  ParametersRead = sscanf(tessoptarg, "%lf", &(Config.Confidence) );
121  if ( ParametersRead != 1 ) Error = TRUE;
122  else if ( Config.Confidence > 1 ) Config.Confidence = 1;
123  else if ( Config.Confidence < 0 ) Config.Confidence = 0;
124  break;
125  case 'I':
126  ParametersRead = sscanf(tessoptarg, "%f", &(Config.Independence) );
127  if ( ParametersRead != 1 ) Error = TRUE;
128  else if ( Config.Independence > 1 ) Config.Independence = 1;
129  else if ( Config.Independence < 0 ) Config.Independence = 0;
130  break;
131  case 'M':
132  ParametersRead = sscanf(tessoptarg, "%f", &(Config.MinSamples) );
133  if ( ParametersRead != 1 ) Error = TRUE;
134  else if ( Config.MinSamples > 1 ) Config.MinSamples = 1;
135  else if ( Config.MinSamples < 0 ) Config.MinSamples = 0;
136  break;
137  case 'B':
138  ParametersRead = sscanf(tessoptarg, "%f", &(Config.MaxIllegal) );
139  if ( ParametersRead != 1 ) Error = TRUE;
140  else if ( Config.MaxIllegal > 1 ) Config.MaxIllegal = 1;
141  else if ( Config.MaxIllegal < 0 ) Config.MaxIllegal = 0;
142  break;
143  case 'c':
144  FLAGS_configfile.set_value(tessoptarg);
145  break;
146  case 'D':
147  FLAGS_D.set_value(tessoptarg);
148  break;
149  case 'U':
150  FLAGS_U.set_value(tessoptarg);
151  break;
152  case 'O':
153  FLAGS_O.set_value(tessoptarg);
154  break;
155  case 'F':
156  FLAGS_F.set_value(tessoptarg);
157  break;
158  case 'X':
159  FLAGS_X.set_value(tessoptarg);
160  break;
161  case '?':
162  Error = TRUE;
163  break;
164  }
165  if (Error) {
166  fprintf(stderr, "Usage: %s %s\n", (*argv)[0], kUsage);
167  exit(2);
168  }
169  }
170 #endif
171  // Set additional parameters from config file if specified.
172  if (!FLAGS_configfile.empty()) {
174  FLAGS_configfile.c_str(),
176  ccutil.params());
177  }
178 } // ParseArguments
179 
180 namespace tesseract {
181 
182 // Helper loads shape table from the given file.
183 ShapeTable* LoadShapeTable(const STRING& file_prefix) {
184  ShapeTable* shape_table = NULL;
185  STRING shape_table_file = file_prefix;
186  shape_table_file += kShapeTableFileSuffix;
187  FILE* shape_fp = fopen(shape_table_file.string(), "rb");
188  if (shape_fp != NULL) {
189  shape_table = new ShapeTable;
190  if (!shape_table->DeSerialize(false, shape_fp)) {
191  delete shape_table;
192  shape_table = NULL;
193  tprintf("Error: Failed to read shape table %s\n",
194  shape_table_file.string());
195  } else {
196  int num_shapes = shape_table->NumShapes();
197  tprintf("Read shape table %s of %d shapes\n",
198  shape_table_file.string(), num_shapes);
199  }
200  fclose(shape_fp);
201  } else {
202  tprintf("Warning: No shape table file present: %s\n",
203  shape_table_file.string());
204  }
205  return shape_table;
206 }
207 
208 // Helper to write the shape_table.
209 void WriteShapeTable(const STRING& file_prefix, const ShapeTable& shape_table) {
210  STRING shape_table_file = file_prefix;
211  shape_table_file += kShapeTableFileSuffix;
212  FILE* fp = fopen(shape_table_file.string(), "wb");
213  if (fp != NULL) {
214  if (!shape_table.Serialize(fp)) {
215  fprintf(stderr, "Error writing shape table: %s\n",
216  shape_table_file.string());
217  }
218  fclose(fp);
219  } else {
220  fprintf(stderr, "Error creating shape table: %s\n",
221  shape_table_file.string());
222  }
223 }
224 
225 // Creates a MasterTraininer and loads the training data into it:
226 // Initializes feature_defs and IntegerFX.
227 // Loads the shape_table if shape_table != NULL.
228 // Loads initial unicharset from -U command-line option.
229 // If FLAGS_input_trainer is set, loads the majority of data from there, else:
230 // Loads font info from -F option.
231 // Loads xheights from -X option.
232 // Loads samples from .tr files in remaining command-line args.
233 // Deletes outliers and computes canonical samples.
234 // If FLAGS_output_trainer is set, saves the trainer for future use.
235 // Computes canonical and cloud features.
236 // If shape_table is not NULL, but failed to load, make a fake flat one,
237 // as shape clustering was not run.
238 MasterTrainer* LoadTrainingData(int argc, const char* const * argv,
239  bool replication,
240  ShapeTable** shape_table,
241  STRING* file_prefix) {
242  InitFeatureDefs(&feature_defs);
243  InitIntegerFX();
244  *file_prefix = "";
245  if (!FLAGS_D.empty()) {
246  *file_prefix += FLAGS_D.c_str();
247  *file_prefix += "/";
248  }
249  // If we are shape clustering (NULL shape_table) or we successfully load
250  // a shape_table written by a previous shape clustering, then
251  // shape_analysis will be true, meaning that the MasterTrainer will replace
252  // some members of the unicharset with their fragments.
253  bool shape_analysis = false;
254  if (shape_table != NULL) {
255  *shape_table = LoadShapeTable(*file_prefix);
256  if (*shape_table != NULL)
257  shape_analysis = true;
258  } else {
259  shape_analysis = true;
260  }
262  shape_analysis,
263  replication,
264  FLAGS_debug_level);
265  if (FLAGS_input_trainer.empty()) {
266  trainer->LoadUnicharset(FLAGS_U.c_str());
267  // Get basic font information from font_properties.
268  if (!FLAGS_F.empty()) {
269  if (!trainer->LoadFontInfo(FLAGS_F.c_str())) {
270  delete trainer;
271  return NULL;
272  }
273  }
274  if (!FLAGS_X.empty()) {
275  if (!trainer->LoadXHeights(FLAGS_X.c_str())) {
276  delete trainer;
277  return NULL;
278  }
279  }
280  IntFeatureSpace fs;
282  trainer->SetFeatureSpace(fs);
283  const char* page_name;
284  // Load training data from .tr files on the command line.
285  while ((page_name = GetNextFilename(argc, argv)) != NULL) {
286  tprintf("Reading %s ...\n", page_name);
287  FILE* fp = Efopen(page_name, "rb");
288  trainer->ReadTrainingSamples(fp, feature_defs, false);
289  fclose(fp);
290 
291  // If there is a file with [lang].[fontname].exp[num].fontinfo present,
292  // read font spacing information in to fontinfo_table.
293  int pagename_len = strlen(page_name);
294  char *fontinfo_file_name = new char[pagename_len + 7];
295  strncpy(fontinfo_file_name, page_name, pagename_len - 2); // remove "tr"
296  strcpy(fontinfo_file_name + pagename_len - 2, "fontinfo"); // +"fontinfo"
297  trainer->AddSpacingInfo(fontinfo_file_name);
298  delete[] fontinfo_file_name;
299 
300  // Load the images into memory if required by the classifier.
301  if (FLAGS_load_images) {
302  STRING image_name = page_name;
303  // Chop off the tr and replace with tif. Extension must be tif!
304  image_name.truncate_at(image_name.length() - 2);
305  image_name += "tif";
306  trainer->LoadPageImages(image_name.string());
307  }
308  }
309  trainer->PostLoadCleanup();
310  // Write the master trainer if required.
311  if (!FLAGS_output_trainer.empty()) {
312  FILE* fp = fopen(FLAGS_output_trainer.c_str(), "wb");
313  if (fp == NULL) {
314  tprintf("Can't create saved trainer data!\n");
315  } else {
316  trainer->Serialize(fp);
317  fclose(fp);
318  }
319  }
320  } else {
321  bool success = false;
322  tprintf("Loading master trainer from file:%s\n",
323  FLAGS_input_trainer.c_str());
324  FILE* fp = fopen(FLAGS_input_trainer.c_str(), "rb");
325  if (fp == NULL) {
326  tprintf("Can't read file %s to initialize master trainer\n",
327  FLAGS_input_trainer.c_str());
328  } else {
329  success = trainer->DeSerialize(false, fp);
330  fclose(fp);
331  }
332  if (!success) {
333  tprintf("Deserialize of master trainer failed!\n");
334  delete trainer;
335  return NULL;
336  }
337  }
338  trainer->PreTrainingSetup();
339  if (!FLAGS_O.empty() &&
340  !trainer->unicharset().save_to_file(FLAGS_O.c_str())) {
341  fprintf(stderr, "Failed to save unicharset to file %s\n", FLAGS_O.c_str());
342  delete trainer;
343  return NULL;
344  }
345  if (shape_table != NULL) {
346  // If we previously failed to load a shapetable, then shape clustering
347  // wasn't run so make a flat one now.
348  if (*shape_table == NULL) {
349  *shape_table = new ShapeTable;
350  trainer->SetupFlatShapeTable(*shape_table);
351  tprintf("Flat shape table summary: %s\n",
352  (*shape_table)->SummaryStr().string());
353  }
354  (*shape_table)->set_unicharset(trainer->unicharset());
355  }
356  return trainer;
357 }
358 
359 } // namespace tesseract.
360 
361 /*---------------------------------------------------------------------------*/
362 const char *GetNextFilename(int argc, const char* const * argv) {
363  /*
364  ** Parameters: none
365  ** Globals:
366  ** tessoptind defined by tessopt sys call
367  ** Operation:
368  ** This routine returns the next command line argument. If
369  ** there are no remaining command line arguments, it returns
370  ** NULL. This routine should only be called after all option
371  ** arguments have been parsed and removed with ParseArguments.
372  ** Return: Next command line argument or NULL.
373  ** Exceptions: none
374  ** History: Fri Aug 18 09:34:12 1989, DSJ, Created.
375  */
376  if (tessoptind < argc)
377  return argv[tessoptind++];
378  else
379  return NULL;
380 } /* GetNextFilename */
381 
382 
383 
384 /*---------------------------------------------------------------------------*/
386  LIST List,
387  char *Label)
388 
389 /*
390  ** Parameters:
391  ** List list to search
392  ** Label label to search for
393  ** Globals: none
394  ** Operation:
395  ** This routine searches thru a list of labeled lists to find
396  ** a list with the specified label. If a matching labeled list
397  ** cannot be found, NULL is returned.
398  ** Return: Labeled list with the specified Label or NULL.
399  ** Exceptions: none
400  ** History: Fri Aug 18 15:57:41 1989, DSJ, Created.
401  */
402 
403 {
404  LABELEDLIST LabeledList;
405 
406  iterate (List)
407  {
408  LabeledList = (LABELEDLIST) first_node (List);
409  if (strcmp (LabeledList->Label, Label) == 0)
410  return (LabeledList);
411  }
412  return (NULL);
413 
414 } /* FindList */
415 
416 /*---------------------------------------------------------------------------*/
418  const char *Label)
419 
420 /*
421  ** Parameters:
422  ** Label label for new list
423  ** Globals: none
424  ** Operation:
425  ** This routine allocates a new, empty labeled list and gives
426  ** it the specified label.
427  ** Return: New, empty labeled list.
428  ** Exceptions: none
429  ** History: Fri Aug 18 16:08:46 1989, DSJ, Created.
430  */
431 
432 {
433  LABELEDLIST LabeledList;
434 
435  LabeledList = (LABELEDLIST) Emalloc (sizeof (LABELEDLISTNODE));
436  LabeledList->Label = (char*)Emalloc (strlen (Label)+1);
437  strcpy (LabeledList->Label, Label);
438  LabeledList->List = NIL_LIST;
439  LabeledList->SampleCount = 0;
440  LabeledList->font_sample_count = 0;
441  return (LabeledList);
442 
443 } /* NewLabeledList */
444 
445 /*---------------------------------------------------------------------------*/
446 // TODO(rays) This is now used only by cntraining. Convert cntraining to use
447 // the new method or get rid of it entirely.
448 void ReadTrainingSamples(const FEATURE_DEFS_STRUCT& feature_defs,
449  const char *feature_name, int max_samples,
450  UNICHARSET* unicharset,
451  FILE* file, LIST* training_samples) {
452 /*
453 ** Parameters:
454 ** file open text file to read samples from
455 ** Globals: none
456 ** Operation:
457 ** This routine reads training samples from a file and
458 ** places them into a data structure which organizes the
459 ** samples by FontName and CharName. It then returns this
460 ** data structure.
461 ** Return: none
462 ** Exceptions: none
463 ** History: Fri Aug 18 13:11:39 1989, DSJ, Created.
464 ** Tue May 17 1998 simplifications to structure, illiminated
465 ** font, and feature specification levels of structure.
466 */
467  char buffer[2048];
468  char unichar[UNICHAR_LEN + 1];
469  LABELEDLIST char_sample;
470  FEATURE_SET feature_samples;
471  CHAR_DESC char_desc;
472  int i;
473  int feature_type = ShortNameToFeatureType(feature_defs, feature_name);
474  // Zero out the font_sample_count for all the classes.
475  LIST it = *training_samples;
476  iterate(it) {
477  char_sample = reinterpret_cast<LABELEDLIST>(first_node(it));
478  char_sample->font_sample_count = 0;
479  }
480 
481  while (fgets(buffer, 2048, file) != NULL) {
482  if (buffer[0] == '\n')
483  continue;
484 
485  sscanf(buffer, "%*s %s", unichar);
486  if (unicharset != NULL && !unicharset->contains_unichar(unichar)) {
487  unicharset->unichar_insert(unichar);
488  if (unicharset->size() > MAX_NUM_CLASSES) {
489  tprintf("Error: Size of unicharset in training is "
490  "greater than MAX_NUM_CLASSES\n");
491  exit(1);
492  }
493  }
494  char_sample = FindList(*training_samples, unichar);
495  if (char_sample == NULL) {
496  char_sample = NewLabeledList(unichar);
497  *training_samples = push(*training_samples, char_sample);
498  }
499  char_desc = ReadCharDescription(feature_defs, file);
500  feature_samples = char_desc->FeatureSets[feature_type];
501  if (char_sample->font_sample_count < max_samples || max_samples <= 0) {
502  char_sample->List = push(char_sample->List, feature_samples);
503  char_sample->SampleCount++;
504  char_sample->font_sample_count++;
505  } else {
506  FreeFeatureSet(feature_samples);
507  }
508  for (i = 0; i < char_desc->NumFeatureSets; i++) {
509  if (feature_type != i)
510  FreeFeatureSet(char_desc->FeatureSets[i]);
511  }
512  free(char_desc);
513  }
514 } // ReadTrainingSamples
515 
516 
517 /*---------------------------------------------------------------------------*/
518 void FreeTrainingSamples(LIST CharList) {
519 /*
520  ** Parameters:
521  ** FontList list of all fonts in document
522  ** Globals: none
523  ** Operation:
524  ** This routine deallocates all of the space allocated to
525  ** the specified list of training samples.
526  ** Return: none
527  ** Exceptions: none
528  ** History: Fri Aug 18 17:44:27 1989, DSJ, Created.
529  */
530  LABELEDLIST char_sample;
531  FEATURE_SET FeatureSet;
532  LIST FeatureList;
533 
534 
535  iterate(CharList) { /* iterate thru all of the fonts */
536  char_sample = (LABELEDLIST) first_node(CharList);
537  FeatureList = char_sample->List;
538  iterate(FeatureList) { /* iterate thru all of the classes */
539  FeatureSet = (FEATURE_SET) first_node(FeatureList);
540  FreeFeatureSet(FeatureSet);
541  }
542  FreeLabeledList(char_sample);
543  }
544  destroy(CharList);
545 } /* FreeTrainingSamples */
546 
547 /*---------------------------------------------------------------------------*/
548 void FreeLabeledList(LABELEDLIST LabeledList) {
549 /*
550  ** Parameters:
551  ** LabeledList labeled list to be freed
552  ** Globals: none
553  ** Operation:
554  ** This routine deallocates all of the memory consumed by
555  ** a labeled list. It does not free any memory which may be
556  ** consumed by the items in the list.
557  ** Return: none
558  ** Exceptions: none
559  ** History: Fri Aug 18 17:52:45 1989, DSJ, Created.
560  */
561  destroy(LabeledList->List);
562  free(LabeledList->Label);
563  free(LabeledList);
564 } /* FreeLabeledList */
565 
566 /*---------------------------------------------------------------------------*/
568  LABELEDLIST char_sample,
569  const char* program_feature_type) {
570 /*
571  ** Parameters:
572  ** char_sample: LABELEDLIST that holds all the feature information for a
573  ** given character.
574  ** Globals:
575  ** None
576  ** Operation:
577  ** This routine reads samples from a LABELEDLIST and enters
578  ** those samples into a clusterer data structure. This
579  ** data structure is then returned to the caller.
580  ** Return:
581  ** Pointer to new clusterer data structure.
582  ** Exceptions:
583  ** None
584  ** History:
585  ** 8/16/89, DSJ, Created.
586  */
587  uinT16 N;
588  int i, j;
589  FLOAT32 *Sample = NULL;
590  CLUSTERER *Clusterer;
591  inT32 CharID;
592  LIST FeatureList = NULL;
593  FEATURE_SET FeatureSet = NULL;
594 
595  int desc_index = ShortNameToFeatureType(FeatureDefs, program_feature_type);
596  N = FeatureDefs.FeatureDesc[desc_index]->NumParams;
597  Clusterer = MakeClusterer(N, FeatureDefs.FeatureDesc[desc_index]->ParamDesc);
598 
599  FeatureList = char_sample->List;
600  CharID = 0;
601  iterate(FeatureList) {
602  FeatureSet = (FEATURE_SET) first_node(FeatureList);
603  for (i = 0; i < FeatureSet->MaxNumFeatures; i++) {
604  if (Sample == NULL)
605  Sample = (FLOAT32 *)Emalloc(N * sizeof(FLOAT32));
606  for (j = 0; j < N; j++)
607  Sample[j] = FeatureSet->Features[i]->Params[j];
608  MakeSample (Clusterer, Sample, CharID);
609  }
610  CharID++;
611  }
612  if ( Sample != NULL ) free( Sample );
613  return( Clusterer );
614 
615 } /* SetUpForClustering */
616 
617 /*------------------------------------------------------------------------*/
618 void MergeInsignificantProtos(LIST ProtoList, const char* label,
619  CLUSTERER *Clusterer, CLUSTERCONFIG *Config) {
620  PROTOTYPE *Prototype;
621  bool debug = strcmp(FLAGS_test_ch.c_str(), label) == 0;
622 
623  LIST pProtoList = ProtoList;
624  iterate(pProtoList) {
625  Prototype = (PROTOTYPE *) first_node (pProtoList);
626  if (Prototype->Significant || Prototype->Merged)
627  continue;
628  FLOAT32 best_dist = 0.125;
629  PROTOTYPE* best_match = NULL;
630  // Find the nearest alive prototype.
631  LIST list_it = ProtoList;
632  iterate(list_it) {
633  PROTOTYPE* test_p = (PROTOTYPE *) first_node (list_it);
634  if (test_p != Prototype && !test_p->Merged) {
635  FLOAT32 dist = ComputeDistance(Clusterer->SampleSize,
636  Clusterer->ParamDesc,
637  Prototype->Mean, test_p->Mean);
638  if (dist < best_dist) {
639  best_match = test_p;
640  best_dist = dist;
641  }
642  }
643  }
644  if (best_match != NULL && !best_match->Significant) {
645  if (debug)
646  tprintf("Merging red clusters (%d+%d) at %g,%g and %g,%g\n",
647  best_match->NumSamples, Prototype->NumSamples,
648  best_match->Mean[0], best_match->Mean[1],
649  Prototype->Mean[0], Prototype->Mean[1]);
650  best_match->NumSamples = MergeClusters(Clusterer->SampleSize,
651  Clusterer->ParamDesc,
652  best_match->NumSamples,
653  Prototype->NumSamples,
654  best_match->Mean,
655  best_match->Mean, Prototype->Mean);
656  Prototype->NumSamples = 0;
657  Prototype->Merged = 1;
658  } else if (best_match != NULL) {
659  if (debug)
660  tprintf("Red proto at %g,%g matched a green one at %g,%g\n",
661  Prototype->Mean[0], Prototype->Mean[1],
662  best_match->Mean[0], best_match->Mean[1]);
663  Prototype->Merged = 1;
664  }
665  }
666  // Mark significant those that now have enough samples.
667  int min_samples = (inT32) (Config->MinSamples * Clusterer->NumChar);
668  pProtoList = ProtoList;
669  iterate(pProtoList) {
670  Prototype = (PROTOTYPE *) first_node (pProtoList);
671  // Process insignificant protos that do not match a green one
672  if (!Prototype->Significant && Prototype->NumSamples >= min_samples &&
673  !Prototype->Merged) {
674  if (debug)
675  tprintf("Red proto at %g,%g becoming green\n",
676  Prototype->Mean[0], Prototype->Mean[1]);
677  Prototype->Significant = true;
678  }
679  }
680 } /* MergeInsignificantProtos */
681 
682 /*-----------------------------------------------------------------------------*/
684  LIST ProtoList)
685 {
686  PROTOTYPE* Prototype;
687 
688  iterate(ProtoList)
689  {
690  Prototype = (PROTOTYPE *) first_node (ProtoList);
691  if(Prototype->Variance.Elliptical != NULL)
692  {
693  memfree(Prototype->Variance.Elliptical);
694  Prototype->Variance.Elliptical = NULL;
695  }
696  if(Prototype->Magnitude.Elliptical != NULL)
697  {
698  memfree(Prototype->Magnitude.Elliptical);
699  Prototype->Magnitude.Elliptical = NULL;
700  }
701  if(Prototype->Weight.Elliptical != NULL)
702  {
703  memfree(Prototype->Weight.Elliptical);
704  Prototype->Weight.Elliptical = NULL;
705  }
706  }
707 }
708 
709 /*------------------------------------------------------------------------*/
711  LIST ProtoList,
712  BOOL8 KeepSigProtos,
713  BOOL8 KeepInsigProtos,
714  int N)
715 
716 {
717  LIST NewProtoList = NIL_LIST;
718  LIST pProtoList;
719  PROTOTYPE* Proto;
720  PROTOTYPE* NewProto;
721  int i;
722 
723  pProtoList = ProtoList;
724  iterate(pProtoList)
725  {
726  Proto = (PROTOTYPE *) first_node (pProtoList);
727  if ((Proto->Significant && KeepSigProtos) ||
728  (!Proto->Significant && KeepInsigProtos))
729  {
730  NewProto = (PROTOTYPE *)Emalloc(sizeof(PROTOTYPE));
731 
732  NewProto->Mean = (FLOAT32 *)Emalloc(N * sizeof(FLOAT32));
733  NewProto->Significant = Proto->Significant;
734  NewProto->Style = Proto->Style;
735  NewProto->NumSamples = Proto->NumSamples;
736  NewProto->Cluster = NULL;
737  NewProto->Distrib = NULL;
738 
739  for (i=0; i < N; i++)
740  NewProto->Mean[i] = Proto->Mean[i];
741  if (Proto->Variance.Elliptical != NULL)
742  {
743  NewProto->Variance.Elliptical = (FLOAT32 *)Emalloc(N * sizeof(FLOAT32));
744  for (i=0; i < N; i++)
745  NewProto->Variance.Elliptical[i] = Proto->Variance.Elliptical[i];
746  }
747  else
748  NewProto->Variance.Elliptical = NULL;
749  //---------------------------------------------
750  if (Proto->Magnitude.Elliptical != NULL)
751  {
752  NewProto->Magnitude.Elliptical = (FLOAT32 *)Emalloc(N * sizeof(FLOAT32));
753  for (i=0; i < N; i++)
754  NewProto->Magnitude.Elliptical[i] = Proto->Magnitude.Elliptical[i];
755  }
756  else
757  NewProto->Magnitude.Elliptical = NULL;
758  //------------------------------------------------
759  if (Proto->Weight.Elliptical != NULL)
760  {
761  NewProto->Weight.Elliptical = (FLOAT32 *)Emalloc(N * sizeof(FLOAT32));
762  for (i=0; i < N; i++)
763  NewProto->Weight.Elliptical[i] = Proto->Weight.Elliptical[i];
764  }
765  else
766  NewProto->Weight.Elliptical = NULL;
767 
768  NewProto->TotalMagnitude = Proto->TotalMagnitude;
769  NewProto->LogMagnitude = Proto->LogMagnitude;
770  NewProtoList = push_last(NewProtoList, NewProto);
771  }
772  }
773  FreeProtoList(&ProtoList);
774  return (NewProtoList);
775 } /* RemoveInsignificantProtos */
776 
777 /*----------------------------------------------------------------------------*/
779  LIST List,
780  const char *Label)
781 {
782  MERGE_CLASS MergeClass;
783 
784  iterate (List)
785  {
786  MergeClass = (MERGE_CLASS) first_node (List);
787  if (strcmp (MergeClass->Label, Label) == 0)
788  return (MergeClass);
789  }
790  return (NULL);
791 
792 } /* FindClass */
793 
794 /*---------------------------------------------------------------------------*/
796  const char *Label)
797 {
798  MERGE_CLASS MergeClass;
799 
800  MergeClass = new MERGE_CLASS_NODE;
801  MergeClass->Label = (char*)Emalloc (strlen (Label)+1);
802  strcpy (MergeClass->Label, Label);
803  MergeClass->Class = NewClass (MAX_NUM_PROTOS, MAX_NUM_CONFIGS);
804  return (MergeClass);
805 
806 } /* NewLabeledClass */
807 
808 /*-----------------------------------------------------------------------------*/
810  LIST ClassList)
811 
812 /*
813  ** Parameters:
814  ** FontList list of all fonts in document
815  ** Globals: none
816  ** Operation:
817  ** This routine deallocates all of the space allocated to
818  ** the specified list of training samples.
819  ** Return: none
820  ** Exceptions: none
821  ** History: Fri Aug 18 17:44:27 1989, DSJ, Created.
822  */
823 
824 {
825  MERGE_CLASS MergeClass;
826 
827  iterate (ClassList) /* iterate thru all of the fonts */
828  {
829  MergeClass = (MERGE_CLASS) first_node (ClassList);
830  free (MergeClass->Label);
831  FreeClass(MergeClass->Class);
832  delete MergeClass;
833  }
834  destroy (ClassList);
835 
836 } /* FreeLabeledClassList */
837 
840  LIST LabeledClassList) {
841  MERGE_CLASS MergeClass;
842  CLASS_TYPE Class;
843  int NumProtos;
844  int NumConfigs;
845  int NumWords;
846  int i, j;
847  float Values[3];
848  PROTO NewProto;
849  PROTO OldProto;
850  BIT_VECTOR NewConfig;
851  BIT_VECTOR OldConfig;
852 
853  // printf("Float2Int ...\n");
854 
855  CLASS_STRUCT* float_classes = new CLASS_STRUCT[unicharset.size()];
856  iterate(LabeledClassList)
857  {
858  UnicityTableEqEq<int> font_set;
859  MergeClass = (MERGE_CLASS) first_node (LabeledClassList);
860  Class = &float_classes[unicharset.unichar_to_id(MergeClass->Label)];
861  NumProtos = MergeClass->Class->NumProtos;
862  NumConfigs = MergeClass->Class->NumConfigs;
863  font_set.move(&MergeClass->Class->font_set);
864  Class->NumProtos = NumProtos;
865  Class->MaxNumProtos = NumProtos;
866  Class->Prototypes = (PROTO) Emalloc (sizeof(PROTO_STRUCT) * NumProtos);
867  for(i=0; i < NumProtos; i++)
868  {
869  NewProto = ProtoIn(Class, i);
870  OldProto = ProtoIn(MergeClass->Class, i);
871  Values[0] = OldProto->X;
872  Values[1] = OldProto->Y;
873  Values[2] = OldProto->Angle;
874  Normalize(Values);
875  NewProto->X = OldProto->X;
876  NewProto->Y = OldProto->Y;
877  NewProto->Length = OldProto->Length;
878  NewProto->Angle = OldProto->Angle;
879  NewProto->A = Values[0];
880  NewProto->B = Values[1];
881  NewProto->C = Values[2];
882  }
883 
884  Class->NumConfigs = NumConfigs;
885  Class->MaxNumConfigs = NumConfigs;
886  Class->font_set.move(&font_set);
887  Class->Configurations = (BIT_VECTOR*) Emalloc (sizeof(BIT_VECTOR) * NumConfigs);
888  NumWords = WordsInVectorOfSize(NumProtos);
889  for(i=0; i < NumConfigs; i++)
890  {
891  NewConfig = NewBitVector(NumProtos);
892  OldConfig = MergeClass->Class->Configurations[i];
893  for(j=0; j < NumWords; j++)
894  NewConfig[j] = OldConfig[j];
895  Class->Configurations[i] = NewConfig;
896  }
897  }
898  return float_classes;
899 } // SetUpForFloat2Int
900 
901 /*--------------------------------------------------------------------------*/
902 void Normalize (
903  float *Values)
904 {
905  register float Slope;
906  register float Intercept;
907  register float Normalizer;
908 
909  Slope = tan (Values [2] * 2 * PI);
910  Intercept = Values [1] - Slope * Values [0];
911  Normalizer = 1 / sqrt (Slope * Slope + 1.0);
912 
913  Values [0] = Slope * Normalizer;
914  Values [1] = - Normalizer;
915  Values [2] = Intercept * Normalizer;
916 } // Normalize
917 
918 /*-------------------------------------------------------------------------*/
920  LIST CharList)
921 
922 {
923  LABELEDLIST char_sample;
924 
925  iterate (CharList) /* iterate thru all of the fonts */
926  {
927  char_sample = (LABELEDLIST) first_node (CharList);
928  FreeLabeledList (char_sample);
929  }
930  destroy (CharList);
931 
932 } // FreeNormProtoList
933 
934 /*---------------------------------------------------------------------------*/
936  LIST* NormProtoList,
937  LIST ProtoList,
938  char* CharName)
939 {
940  PROTOTYPE* Proto;
941  LABELEDLIST LabeledProtoList;
942 
943  LabeledProtoList = NewLabeledList(CharName);
944  iterate(ProtoList)
945  {
946  Proto = (PROTOTYPE *) first_node (ProtoList);
947  LabeledProtoList->List = push(LabeledProtoList->List, Proto);
948  }
949  *NormProtoList = push(*NormProtoList, LabeledProtoList);
950 }
951 
952 /*---------------------------------------------------------------------------*/
954  LIST ProtoList,
955  BOOL8 CountSigProtos,
956  BOOL8 CountInsigProtos)
957 {
958  int N = 0;
959  PROTOTYPE *Proto;
960 
961  iterate(ProtoList)
962  {
963  Proto = (PROTOTYPE *) first_node ( ProtoList );
964  if (( Proto->Significant && CountSigProtos ) ||
965  ( ! Proto->Significant && CountInsigProtos ) )
966  N++;
967  }
968  return(N);
969 }