tesseract  v4.0.0-17-g361f3264
Open Source OCR Engine
shapetable.h
1 // Copyright 2010 Google Inc. All Rights Reserved.
2 // Author: rays@google.com (Ray Smith)
4 // File: shapetable.h
5 // Description: Class to map a classifier shape index to unicharset
6 // indices and font indices.
7 // Author: Ray Smith
8 // Created: Thu Oct 28 17:46:32 PDT 2010
9 //
10 // (C) Copyright 2010, Google Inc.
11 // Licensed under the Apache License, Version 2.0 (the "License");
12 // you may not use this file except in compliance with the License.
13 // You may obtain a copy of the License at
14 // http://www.apache.org/licenses/LICENSE-2.0
15 // Unless required by applicable law or agreed to in writing, software
16 // distributed under the License is distributed on an "AS IS" BASIS,
17 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 // See the License for the specific language governing permissions and
19 // limitations under the License.
20 //
22 
23 #ifndef TESSERACT_CLASSIFY_SHAPETABLE_H_
24 #define TESSERACT_CLASSIFY_SHAPETABLE_H_
25 
26 #include "bitvector.h"
27 #include "fontinfo.h"
28 #include "genericheap.h"
29 #include "genericvector.h"
30 #include "intmatcher.h"
31 
32 class STRING;
33 class UNICHARSET;
34 
35 namespace tesseract {
36 
37 class ShapeTable;
38 
39 // Simple struct to hold a single classifier unichar selection, a corresponding
40 // rating, and a list of appropriate fonts.
41 struct UnicharRating {
43  : unichar_id(0), rating(0.0f), adapted(false), config(0),
44  feature_misses(0) {}
45  UnicharRating(int u, float r)
46  : unichar_id(u), rating(r), adapted(false), config(0), feature_misses(0) {}
47 
48  // Print debug info.
49  void Print() const {
50  tprintf("Unichar-id=%d, rating=%g, adapted=%d, config=%d, misses=%d,"
51  " %d fonts\n", unichar_id, rating, adapted, config, feature_misses,
52  fonts.size());
53  }
54 
55  // Sort function to sort ratings appropriately by descending rating.
56  static int SortDescendingRating(const void* t1, const void* t2) {
57  const UnicharRating* a = static_cast<const UnicharRating*>(t1);
58  const UnicharRating* b = static_cast<const UnicharRating*>(t2);
59  if (a->rating > b->rating) {
60  return -1;
61  } else if (a->rating < b->rating) {
62  return 1;
63  } else {
64  return a->unichar_id - b->unichar_id;
65  }
66  }
67  // Helper function to get the index of the first result with the required
68  // unichar_id. If the results are sorted by rating, this will also be the
69  // best result with the required unichar_id.
70  // Returns -1 if the unichar_id is not found
71  static int FirstResultWithUnichar(const GenericVector<UnicharRating>& results,
72  UNICHAR_ID unichar_id);
73 
74  // Index into some UNICHARSET table indicates the class of the answer.
75  UNICHAR_ID unichar_id;
76  // Rating from classifier with 1.0 perfect and 0.0 impossible.
77  // Call it a probability if you must.
78  float rating;
79  // True if this result is from the adaptive classifier.
80  bool adapted;
81  // Index of best matching font configuration of result.
82  uint8_t config;
83  // Number of features that were total misses - were liked by no classes.
84  uint16_t feature_misses;
85  // Unsorted collection of fontinfo ids and scores. Note that a raw result
86  // from the IntegerMatch will contain config ids, that require transforming
87  // to fontinfo ids via fontsets and (possibly) shapetable.
89 };
90 
91 // Classifier result from a low-level classification is an index into some
92 // ShapeTable and a rating.
93 struct ShapeRating {
95  : shape_id(0), rating(0.0f), raw(0.0f), font(0.0f),
96  joined(false), broken(false) {}
97  ShapeRating(int s, float r)
98  : shape_id(s), rating(r), raw(1.0f), font(0.0f),
99  joined(false), broken(false) {}
100 
101  // Sort function to sort ratings appropriately by descending rating.
102  static int SortDescendingRating(const void* t1, const void* t2) {
103  const ShapeRating* a = static_cast<const ShapeRating*>(t1);
104  const ShapeRating* b = static_cast<const ShapeRating*>(t2);
105  if (a->rating > b->rating) {
106  return -1;
107  } else if (a->rating < b->rating) {
108  return 1;
109  } else {
110  return a->shape_id - b->shape_id;
111  }
112  }
113  // Helper function to get the index of the first result with the required
114  // unichar_id. If the results are sorted by rating, this will also be the
115  // best result with the required unichar_id.
116  // Returns -1 if the unichar_id is not found
117  static int FirstResultWithUnichar(const GenericVector<ShapeRating>& results,
118  const ShapeTable& shape_table,
119  UNICHAR_ID unichar_id);
120 
121  // Index into some shape table indicates the class of the answer.
122  int shape_id;
123  // Rating from classifier with 1.0 perfect and 0.0 impossible.
124  // Call it a probability if you must.
125  float rating;
126  // Subsidiary rating that a classifier may use internally.
127  float raw;
128  // Subsidiary rating that a classifier may use internally.
129  float font;
130  // Flag indicating that the input may be joined.
131  bool joined;
132  // Flag indicating that the input may be broken (a fragment).
133  bool broken;
134 };
135 
136 // Simple struct to hold an entry for a heap-based priority queue of
137 // ShapeRating.
139  ShapeQueueEntry() : result(ShapeRating(0, 0.0f)), level(0) {}
140  ShapeQueueEntry(const ShapeRating& rating, int level0)
141  : result(rating), level(level0) {}
142 
143  // Sort by decreasing rating and decreasing level for equal rating.
144  bool operator<(const ShapeQueueEntry& other) const {
145  if (result.rating > other.result.rating) return true;
146  if (result.rating == other.result.rating)
147  return level > other.level;
148  return false;
149  }
150 
151  // Output from classifier.
153  // Which level in the tree did this come from?
154  int level;
155 };
157 
158 // Simple struct to hold a set of fonts associated with a single unichar-id.
159 // A vector of UnicharAndFonts makes a shape.
162  }
163  UnicharAndFonts(int uni_id, int font_id) : unichar_id(uni_id) {
164  font_ids.push_back(font_id);
165  }
166 
167  // Writes to the given file. Returns false in case of error.
168  bool Serialize(FILE* fp) const;
169  // Reads from the given file. Returns false in case of error.
170  bool DeSerialize(TFile* fp);
171 
172  // Sort function to sort a pair of UnicharAndFonts by unichar_id.
173  static int SortByUnicharId(const void* v1, const void* v2);
174 
176  int32_t unichar_id;
177 };
178 
179 // A Shape is a collection of unichar-ids and a list of fonts associated with
180 // each, organized as a vector of UnicharAndFonts. Conceptually a Shape is
181 // a classifiable unit, and represents a group of characters or parts of
182 // characters that have a similar or identical shape. Shapes/ShapeTables may
183 // be organized hierarchically from identical shapes at the leaves to vaguely
184 // similar shapes near the root.
185 class Shape {
186  public:
187  Shape() : destination_index_(-1) {}
188 
189  // Writes to the given file. Returns false in case of error.
190  bool Serialize(FILE* fp) const;
191  // Reads from the given file. Returns false in case of error.
192  bool DeSerialize(TFile* fp);
193 
194  int destination_index() const {
195  return destination_index_;
196  }
197  void set_destination_index(int index) {
198  destination_index_ = index;
199  }
200  int size() const {
201  return unichars_.size();
202  }
203  // Returns a UnicharAndFonts entry for the given index, which must be
204  // in the range [0, size()).
205  const UnicharAndFonts& operator[](int index) const {
206  return unichars_[index];
207  }
208  // Sets the unichar_id of the given index to the new unichar_id.
209  void SetUnicharId(int index, int unichar_id) {
210  unichars_[index].unichar_id = unichar_id;
211  }
212  // Adds a font_id for the given unichar_id. If the unichar_id is not
213  // in the shape, it is added.
214  void AddToShape(int unichar_id, int font_id);
215  // Adds everything in other to this.
216  void AddShape(const Shape& other);
217  // Returns true if the shape contains the given unichar_id, font_id pair.
218  bool ContainsUnicharAndFont(int unichar_id, int font_id) const;
219  // Returns true if the shape contains the given unichar_id, ignoring font.
220  bool ContainsUnichar(int unichar_id) const;
221  // Returns true if the shape contains the given font, ignoring unichar_id.
222  bool ContainsFont(int font_id) const;
223  // Returns true if the shape contains the given font properties, ignoring
224  // unichar_id.
225  bool ContainsFontProperties(const FontInfoTable& font_table,
226  uint32_t properties) const;
227  // Returns true if the shape contains multiple different font properties,
228  // ignoring unichar_id.
229  bool ContainsMultipleFontProperties(const FontInfoTable& font_table) const;
230  // Returns true if this shape is equal to other (ignoring order of unichars
231  // and fonts).
232  bool operator==(const Shape& other) const;
233  // Returns true if this is a subset (including equal) of other.
234  bool IsSubsetOf(const Shape& other) const;
235  // Returns true if the lists of unichar ids are the same in this and other,
236  // ignoring fonts.
237  // NOT const, as it will sort the unichars on demand.
238  bool IsEqualUnichars(Shape* other);
239 
240  private:
241  // Sorts the unichars_ vector by unichar.
242  void SortUnichars();
243 
244  // Flag indicates that the unichars are sorted, allowing faster set
245  // operations with another shape.
247  // If this Shape is part of a ShapeTable the destiation_index_ is the index
248  // of some other shape in the ShapeTable with which this shape is merged.
250  // Array of unichars, each with a set of fonts. Each unichar has at most
251  // one entry in the vector.
253 };
254 
255 // ShapeTable is a class to encapsulate the triple indirection that is
256 // used here.
257 // ShapeTable is a vector of shapes.
258 // Each shape is a vector of UnicharAndFonts representing the set of unichars
259 // that the shape represents.
260 // Each UnicharAndFonts also lists the fonts of the unichar_id that were
261 // mapped to the shape during training.
262 class ShapeTable {
263  public:
264  ShapeTable();
265  // The UNICHARSET reference supplied here, or in set_unicharset below must
266  // exist for the entire life of the ShapeTable. It is used only by DebugStr.
267  explicit ShapeTable(const UNICHARSET& unicharset);
268 
269  // Writes to the given file. Returns false in case of error.
270  bool Serialize(FILE* fp) const;
271  // Reads from the given file. Returns false in case of error.
272  bool DeSerialize(TFile* fp);
273 
274  // Accessors.
275  int NumShapes() const {
276  return shape_table_.size();
277  }
278  const UNICHARSET& unicharset() const {
279  return *unicharset_;
280  }
281  // Returns the number of fonts used in this ShapeTable, computing it if
282  // necessary.
283  int NumFonts() const;
284  // Shapetable takes a pointer to the UNICHARSET, so it must persist for the
285  // entire life of the ShapeTable.
286  void set_unicharset(const UNICHARSET& unicharset) {
287  unicharset_ = &unicharset;
288  }
289  // Re-indexes the class_ids in the shapetable according to the given map.
290  // Useful in conjunction with set_unicharset.
291  void ReMapClassIds(const GenericVector<int>& unicharset_map);
292  // Returns a string listing the classes/fonts in a shape.
293  STRING DebugStr(int shape_id) const;
294  // Returns a debug string summarizing the table.
295  STRING SummaryStr() const;
296 
297  // Adds a new shape starting with the given unichar_id and font_id.
298  // Returns the assigned index.
299  int AddShape(int unichar_id, int font_id);
300  // Adds a copy of the given shape unless it is already present.
301  // Returns the assigned index or index of existing shape if already present.
302  int AddShape(const Shape& other);
303  // Removes the shape given by the shape index. All indices above are changed!
304  void DeleteShape(int shape_id);
305  // Adds a font_id to the given existing shape index for the given
306  // unichar_id. If the unichar_id is not in the shape, it is added.
307  void AddToShape(int shape_id, int unichar_id, int font_id);
308  // Adds the given shape to the existing shape with the given index.
309  void AddShapeToShape(int shape_id, const Shape& other);
310  // Returns the id of the shape that contains the given unichar and font.
311  // If not found, returns -1.
312  // If font_id < 0, the font_id is ignored and the first shape that matches
313  // the unichar_id is returned.
314  int FindShape(int unichar_id, int font_id) const;
315  // Returns the first unichar_id and font_id in the given shape.
316  void GetFirstUnicharAndFont(int shape_id,
317  int* unichar_id, int* font_id) const;
318 
319  // Accessors for the Shape with the given shape_id.
320  const Shape& GetShape(int shape_id) const {
321  return *shape_table_[shape_id];
322  }
323  Shape* MutableShape(int shape_id) {
324  return shape_table_[shape_id];
325  }
326 
327  // Expands all the classes/fonts in the shape individually to build
328  // a ShapeTable.
329  int BuildFromShape(const Shape& shape, const ShapeTable& master_shapes);
330 
331  // Returns true if the shapes are already merged.
332  bool AlreadyMerged(int shape_id1, int shape_id2) const;
333  // Returns true if any shape contains multiple unichars.
334  bool AnyMultipleUnichars() const;
335  // Returns the maximum number of unichars over all shapes.
336  int MaxNumUnichars() const;
337  // Merges shapes with a common unichar over the [start, end) interval.
338  // Assumes single unichar per shape.
339  void ForceFontMerges(int start, int end);
340  // Returns the number of unichars in the master shape.
341  int MasterUnicharCount(int shape_id) const;
342  // Returns the sum of the font counts in the master shape.
343  int MasterFontCount(int shape_id) const;
344  // Returns the number of unichars that would result from merging the shapes.
345  int MergedUnicharCount(int shape_id1, int shape_id2) const;
346  // Merges two shape_ids, leaving shape_id2 marked as merged.
347  void MergeShapes(int shape_id1, int shape_id2);
348  // Swaps two shape_ids.
349  void SwapShapes(int shape_id1, int shape_id2);
350  // Appends the master shapes from other to this.
351  // Used to create a clean ShapeTable from a merged one, or to create a
352  // copy of a ShapeTable.
353  // If not nullptr, shape_map is set to map other shape_ids to this's shape_ids.
354  void AppendMasterShapes(const ShapeTable& other,
355  GenericVector<int>* shape_map);
356  // Returns the number of master shapes remaining after merging.
357  int NumMasterShapes() const;
358  // Returns the destination of this shape, (if merged), taking into account
359  // the fact that the destination may itself have been merged.
360  // For a non-merged shape, returns the input shape_id.
361  int MasterDestinationIndex(int shape_id) const;
362 
363  // Returns false if the unichars in neither shape is a subset of the other..
364  bool SubsetUnichar(int shape_id1, int shape_id2) const;
365  // Returns false if the unichars in neither shape is a subset of the other..
366  bool MergeSubsetUnichar(int merge_id1, int merge_id2, int shape_id) const;
367  // Returns true if the unichar sets are equal between the shapes.
368  bool EqualUnichars(int shape_id1, int shape_id2) const;
369  bool MergeEqualUnichars(int merge_id1, int merge_id2, int shape_id) const;
370  // Returns true if there is a common unichar between the shapes.
371  bool CommonUnichars(int shape_id1, int shape_id2) const;
372  // Returns true if there is a common font id between the shapes.
373  bool CommonFont(int shape_id1, int shape_id2) const;
374 
375  // Adds the unichars of the given shape_id to the vector of results. Any
376  // unichar_id that is already present just has the fonts added to the
377  // font set for that result without adding a new entry in the vector.
378  // NOTE: it is assumed that the results are given to this function in order
379  // of decreasing rating.
380  // The unichar_map vector indicates the index of the results entry containing
381  // each unichar, or -1 if the unichar is not yet included in results.
382  void AddShapeToResults(const ShapeRating& shape_rating,
383  GenericVector<int>* unichar_map,
384  GenericVector<UnicharRating>* results) const;
385 
386  private:
387  // Adds the given unichar_id to the results if needed, updating unichar_map
388  // and returning the index of unichar in results.
389  int AddUnicharToResults(int unichar_id, float rating,
390  GenericVector<int>* unichar_map,
391  GenericVector<UnicharRating>* results) const;
392 
393  // Pointer to a provided unicharset used only by the Debugstr member.
395  // Vector of pointers to the Shapes in this ShapeTable.
397 
398  // Cached data calculated on demand.
399  mutable int num_fonts_;
400 };
401 
402 } // namespace tesseract.
403 
404 #endif // TESSERACT_CLASSIFY_SHAPETABLE_H_
Definition: genericheap.h:58
UnicharAndFonts(int uni_id, int font_id)
Definition: shapetable.h:163
Definition: shapetable.h:138
const UnicharAndFonts & operator[](int index) const
Definition: shapetable.h:205
Definition: shapetable.h:185
float font
Definition: shapetable.h:129
int num_fonts_
Definition: shapetable.h:399
GenericVector< UnicharAndFonts > unichars_
Definition: shapetable.h:252
static int SortDescendingRating(const void *t1, const void *t2)
Definition: shapetable.h:56
UnicharRating()
Definition: shapetable.h:42
ShapeQueueEntry(const ShapeRating &rating, int level0)
Definition: shapetable.h:140
int level
Definition: shapetable.h:154
Definition: unicharset.h:146
Definition: shapetable.h:160
Shape()
Definition: shapetable.h:187
static int SortDescendingRating(const void *t1, const void *t2)
Definition: shapetable.h:102
Definition: serialis.h:77
const UNICHARSET & unicharset() const
Definition: shapetable.h:278
Definition: baseapi.cpp:94
int destination_index() const
Definition: shapetable.h:194
UNICHAR_ID unichar_id
Definition: shapetable.h:75
ShapeRating(int s, float r)
Definition: shapetable.h:97
static int FirstResultWithUnichar(const GenericVector< UnicharRating > &results, UNICHAR_ID unichar_id)
Definition: shapetable.cpp:58
bool operator<(const ShapeQueueEntry &other) const
Definition: shapetable.h:144
bool broken
Definition: shapetable.h:133
UnicharRating(int u, float r)
Definition: shapetable.h:45
void SetUnicharId(int index, int unichar_id)
Definition: shapetable.h:209
Definition: shapetable.h:93
PointerVector< Shape > shape_table_
Definition: shapetable.h:396
UnicharAndFonts()
Definition: shapetable.h:161
float rating
Definition: shapetable.h:125
int size() const
Definition: shapetable.h:200
int NumShapes() const
Definition: shapetable.h:275
bool Serialize(FILE *fp, const char *data, size_t n)
Definition: serialis.cpp:59
const UNICHARSET * unicharset_
Definition: shapetable.h:394
GenericVector< int32_t > font_ids
Definition: shapetable.h:175
Definition: strngs.h:45
bool adapted
Definition: shapetable.h:80
Definition: shapetable.h:262
int shape_id
Definition: shapetable.h:122
void set_unicharset(const UNICHARSET &unicharset)
Definition: shapetable.h:286
ShapeRating result
Definition: shapetable.h:152
ShapeRating()
Definition: shapetable.h:94
Definition: fontinfo.h:146
Definition: genericvector.h:457
const Shape & GetShape(int shape_id) const
Definition: shapetable.h:320
float raw
Definition: shapetable.h:127
GenericVector< ScoredFont > fonts
Definition: shapetable.h:88
bool joined
Definition: shapetable.h:131
void Print() const
Definition: shapetable.h:49
int destination_index_
Definition: shapetable.h:249
int32_t unichar_id
Definition: shapetable.h:176
Shape * MutableShape(int shape_id)
Definition: shapetable.h:323
float rating
Definition: shapetable.h:78
ShapeQueueEntry()
Definition: shapetable.h:139
void set_destination_index(int index)
Definition: shapetable.h:197
bool unichars_sorted_
Definition: shapetable.h:246
bool DeSerialize(FILE *fp, char *data, size_t n)
Definition: serialis.cpp:27
Definition: shapetable.h:41
uint8_t config
Definition: shapetable.h:82
uint16_t feature_misses
Definition: shapetable.h:84