tesseract  v4.0.0-17-g361f3264
Open Source OCR Engine
blobs.h
1 /* -*-C-*-
2  ********************************************************************************
3  *
4  * File: blobs.h (Formerly blobs.h)
5  * Description: Blob definition
6  * Author: Mark Seaman, OCR Technology
7  * Created: Fri Oct 27 15:39:52 1989
8  * Modified: Thu Mar 28 15:33:38 1991 (Mark Seaman) marks@hpgrlt
9  * Language: C
10  * Package: N/A
11  * Status: Experimental (Do Not Distribute)
12  *
13  * (c) Copyright 1989, Hewlett-Packard Company.
14  ** Licensed under the Apache License, Version 2.0 (the "License");
15  ** you may not use this file except in compliance with the License.
16  ** You may obtain a copy of the License at
17  ** http://www.apache.org/licenses/LICENSE-2.0
18  ** Unless required by applicable law or agreed to in writing, software
19  ** distributed under the License is distributed on an "AS IS" BASIS,
20  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21  ** See the License for the specific language governing permissions and
22  ** limitations under the License.
23  *
24  *********************************************************************************/
25 
26 #ifndef BLOBS_H
27 #define BLOBS_H
28 
29 /*----------------------------------------------------------------------
30  I n c l u d e s
31 ----------------------------------------------------------------------*/
32 #include <cstdint> // for int16_t
33 #include <cstring> // for memcpy, memset
34 #include "clst.h" // for CLIST_ITERATOR, CLISTIZEH
35 #include "genericvector.h" // for GenericVector
36 #include "normalis.h" // for DENORM
37 #include "points.h" // for FCOORD, ICOORD
38 #include "publictypes.h" // for OcrEngineMode
39 #include "rect.h" // for TBOX
40 #include "scrollview.h" // for ScrollView, ScrollView::Color
41 #include "vecfuncs.h" // for CROSS
42 
43 class BLOCK;
44 class C_BLOB;
45 class C_OUTLINE;
46 class LLSQ;
47 class ROW;
48 class WERD;
49 
50 struct Pix;
51 
52 /*----------------------------------------------------------------------
53  T y p e s
54 ----------------------------------------------------------------------*/
55 #define EDGEPTFLAGS 4 /*concavity,length etc. */
56 
57 struct TPOINT {
58  TPOINT(): x(0), y(0) {}
59  TPOINT(int16_t vx, int16_t vy) : x(vx), y(vy) {}
60  TPOINT(const ICOORD &ic) : x(ic.x()), y(ic.y()) {}
61 
62  void operator+=(const TPOINT& other) {
63  x += other.x;
64  y += other.y;
65  }
66  void operator/=(int divisor) {
67  x /= divisor;
68  y /= divisor;
69  }
70  bool operator==(const TPOINT& other) const {
71  return x == other.x && y == other.y;
72  }
73  // Returns true when the two line segments cross each other.
74  // (Moved from outlines.cpp).
75  static bool IsCrossed(const TPOINT& a0, const TPOINT& a1, const TPOINT& b0,
76  const TPOINT& b1);
77 
78  int16_t x; // absolute x coord.
79  int16_t y; // absolute y coord.
80 };
81 using VECTOR = TPOINT; // structure for coordinates.
82 
83 struct EDGEPT {
85  : next(nullptr), prev(nullptr), src_outline(nullptr), start_step(0), step_count(0) {
86  memset(flags, 0, EDGEPTFLAGS * sizeof(flags[0]));
87  }
88  EDGEPT(const EDGEPT& src) : next(nullptr), prev(nullptr) {
89  CopyFrom(src);
90  }
91  EDGEPT& operator=(const EDGEPT& src) {
92  CopyFrom(src);
93  return *this;
94  }
95  // Copies the data elements, but leaves the pointers untouched.
96  void CopyFrom(const EDGEPT& src) {
97  pos = src.pos;
98  vec = src.vec;
99  memcpy(flags, src.flags, EDGEPTFLAGS * sizeof(flags[0]));
100  src_outline = src.src_outline;
101  start_step = src.start_step;
102  step_count = src.step_count;
103  }
104  // Returns the squared distance between the points, with the x-component
105  // weighted by x_factor.
106  int WeightedDistance(const EDGEPT& other, int x_factor) const {
107  int x_dist = pos.x - other.pos.x;
108  int y_dist = pos.y - other.pos.y;
109  return x_dist * x_dist * x_factor + y_dist * y_dist;
110  }
111  // Returns true if the positions are equal.
112  bool EqualPos(const EDGEPT& other) const { return pos == other.pos; }
113  // Returns the bounding box of the outline segment from *this to *end.
114  // Ignores hidden edge flags.
115  TBOX SegmentBox(const EDGEPT* end) const {
116  TBOX box(pos.x, pos.y, pos.x, pos.y);
117  const EDGEPT* pt = this;
118  do {
119  pt = pt->next;
120  if (pt->pos.x < box.left()) box.set_left(pt->pos.x);
121  if (pt->pos.x > box.right()) box.set_right(pt->pos.x);
122  if (pt->pos.y < box.bottom()) box.set_bottom(pt->pos.y);
123  if (pt->pos.y > box.top()) box.set_top(pt->pos.y);
124  } while (pt != end && pt != this);
125  return box;
126  }
127  // Returns the area of the outline segment from *this to *end.
128  // Ignores hidden edge flags.
129  int SegmentArea(const EDGEPT* end) const {
130  int area = 0;
131  const EDGEPT* pt = this->next;
132  do {
133  TPOINT origin_vec(pt->pos.x - pos.x, pt->pos.y - pos.y);
134  area += CROSS(origin_vec, pt->vec);
135  pt = pt->next;
136  } while (pt != end && pt != this);
137  return area;
138  }
139  // Returns true if the number of points in the outline segment from *this to
140  // *end is less that min_points and false if we get back to *this first.
141  // Ignores hidden edge flags.
142  bool ShortNonCircularSegment(int min_points, const EDGEPT* end) const {
143  int count = 0;
144  const EDGEPT* pt = this;
145  do {
146  if (pt == end) return true;
147  pt = pt->next;
148  ++count;
149  } while (pt != this && count <= min_points);
150  return false;
151  }
152 
153  // Accessors to hide or reveal a cut edge from feature extractors.
154  void Hide() {
155  flags[0] = true;
156  }
157  void Reveal() {
158  flags[0] = false;
159  }
160  bool IsHidden() const {
161  return flags[0] != 0;
162  }
163  void MarkChop() {
164  flags[2] = true;
165  }
166  bool IsChopPt() const {
167  return flags[2] != 0;
168  }
169 
170  TPOINT pos; // position
171  VECTOR vec; // vector to next point
172  // TODO(rays) Remove flags and replace with
173  // is_hidden, runlength, dir, and fixed. The only use
174  // of the flags other than is_hidden is in polyaprx.cpp.
175  char flags[EDGEPTFLAGS]; // concavity, length etc
176  EDGEPT* next; // anticlockwise element
177  EDGEPT* prev; // clockwise element
178  C_OUTLINE* src_outline; // Outline it came from.
179  // The following fields are not used if src_outline is nullptr.
180  int start_step; // Location of pos in src_outline.
181  int step_count; // Number of steps used (may wrap around).
182 };
183 
184 // For use in chop and findseam to keep a list of which EDGEPTs were inserted.
185 CLISTIZEH(EDGEPT)
186 
187 struct TESSLINE {
188  TESSLINE() : is_hole(false), loop(nullptr), next(nullptr) {}
189  TESSLINE(const TESSLINE& src) : loop(nullptr), next(nullptr) {
190  CopyFrom(src);
191  }
193  Clear();
194  }
195  TESSLINE& operator=(const TESSLINE& src) {
196  CopyFrom(src);
197  return *this;
198  }
199  // Consume the circular list of EDGEPTs to make a TESSLINE.
200  static TESSLINE* BuildFromOutlineList(EDGEPT* outline);
201  // Copies the data and the outline, but leaves next untouched.
202  void CopyFrom(const TESSLINE& src);
203  // Deletes owned data.
204  void Clear();
205  // Normalize in-place using the DENORM.
206  void Normalize(const DENORM& denorm);
207  // Rotates by the given rotation in place.
208  void Rotate(const FCOORD rotation);
209  // Moves by the given vec in place.
210  void Move(const ICOORD vec);
211  // Scales by the given factor in place.
212  void Scale(float factor);
213  // Sets up the start and vec members of the loop from the pos members.
214  void SetupFromPos();
215  // Recomputes the bounding box from the points in the loop.
216  void ComputeBoundingBox();
217  // Computes the min and max cross product of the outline points with the
218  // given vec and returns the results in min_xp and max_xp. Geometrically
219  // this is the left and right edge of the outline perpendicular to the
220  // given direction, but to get the distance units correct, you would
221  // have to divide by the modulus of vec.
222  void MinMaxCrossProduct(const TPOINT vec, int* min_xp, int* max_xp) const;
223 
224  TBOX bounding_box() const;
225  // Returns true if *this and other have equal bounding boxes.
226  bool SameBox(const TESSLINE& other) const {
227  return topleft == other.topleft && botright == other.botright;
228  }
229  // Returns true if the given line segment crosses any outline of this blob.
230  bool SegmentCrosses(const TPOINT& pt1, const TPOINT& pt2) const {
231  if (Contains(pt1) && Contains(pt2)) {
232  EDGEPT* pt = loop;
233  do {
234  if (TPOINT::IsCrossed(pt1, pt2, pt->pos, pt->next->pos)) return true;
235  pt = pt->next;
236  } while (pt != loop);
237  }
238  return false;
239  }
240  // Returns true if the point is contained within the outline box.
241  bool Contains(const TPOINT& pt) const {
242  return topleft.x <= pt.x && pt.x <= botright.x &&
243  botright.y <= pt.y && pt.y <= topleft.y;
244  }
245 
246  #ifndef GRAPHICS_DISABLED
247  void plot(ScrollView* window, ScrollView::Color color,
248  ScrollView::Color child_color);
249  #endif // GRAPHICS_DISABLED
250 
251  // Returns the first outline point that has a different src_outline to its
252  // predecessor, or, if all the same, the lowest indexed point.
253  EDGEPT* FindBestStartPt() const;
254 
255 
256  int BBArea() const {
257  return (botright.x - topleft.x) * (topleft.y - botright.y);
258  }
259 
260  TPOINT topleft; // Top left of loop.
261  TPOINT botright; // Bottom right of loop.
262  TPOINT start; // Start of loop.
263  bool is_hole; // True if this is a hole/child outline.
264  EDGEPT *loop; // Edgeloop.
265  TESSLINE *next; // Next outline in blob.
266 }; // Outline structure.
267 
268 struct TBLOB {
269  TBLOB() : outlines(nullptr) {}
270  TBLOB(const TBLOB& src) : outlines(nullptr) {
271  CopyFrom(src);
272  }
273  ~TBLOB() {
274  Clear();
275  }
276  TBLOB& operator=(const TBLOB& src) {
277  CopyFrom(src);
278  return *this;
279  }
280  // Factory to build a TBLOB from a C_BLOB with polygonal approximation along
281  // the way. If allow_detailed_fx is true, the EDGEPTs in the returned TBLOB
282  // contain pointers to the input C_OUTLINEs that enable higher-resolution
283  // feature extraction that does not use the polygonal approximation.
284  static TBLOB* PolygonalCopy(bool allow_detailed_fx, C_BLOB* src);
285  // Factory builds a blob with no outlines, but copies the other member data.
286  static TBLOB* ShallowCopy(const TBLOB& src);
287  // Normalizes the blob for classification only if needed.
288  // (Normally this means a non-zero classify rotation.)
289  // If no Normalization is needed, then nullptr is returned, and the input blob
290  // can be used directly. Otherwise a new TBLOB is returned which must be
291  // deleted after use.
292  TBLOB* ClassifyNormalizeIfNeeded() const;
293 
294  // Copies the data and the outlines, but leaves next untouched.
295  void CopyFrom(const TBLOB& src);
296  // Deletes owned data.
297  void Clear();
298  // Sets up the built-in DENORM and normalizes the blob in-place.
299  // For parameters see DENORM::SetupNormalization, plus the inverse flag for
300  // this blob and the Pix for the full image.
301  void Normalize(const BLOCK* block,
302  const FCOORD* rotation,
303  const DENORM* predecessor,
304  float x_origin, float y_origin,
305  float x_scale, float y_scale,
306  float final_xshift, float final_yshift,
307  bool inverse, Pix* pix);
308  // Rotates by the given rotation in place.
309  void Rotate(const FCOORD rotation);
310  // Moves by the given vec in place.
311  void Move(const ICOORD vec);
312  // Scales by the given factor in place.
313  void Scale(float factor);
314  // Recomputes the bounding boxes of the outlines.
315  void ComputeBoundingBoxes();
316 
317  // Returns the number of outlines.
318  int NumOutlines() const;
319 
320  TBOX bounding_box() const;
321 
322  // Returns true if the given line segment crosses any outline of this blob.
323  bool SegmentCrossesOutline(const TPOINT& pt1, const TPOINT& pt2) const {
324  for (const TESSLINE* outline = outlines; outline != nullptr;
325  outline = outline->next) {
326  if (outline->SegmentCrosses(pt1, pt2)) return true;
327  }
328  return false;
329  }
330  // Returns true if the point is contained within any of the outline boxes.
331  bool Contains(const TPOINT& pt) const {
332  for (const TESSLINE* outline = outlines; outline != nullptr;
333  outline = outline->next) {
334  if (outline->Contains(pt)) return true;
335  }
336  return false;
337  }
338 
339  // Finds and deletes any duplicate outlines in this blob, without deleting
340  // their EDGEPTs.
341  void EliminateDuplicateOutlines();
342 
343  // Swaps the outlines of *this and next if needed to keep the centers in
344  // increasing x.
345  void CorrectBlobOrder(TBLOB* next);
346 
347  const DENORM& denorm() const {
348  return denorm_;
349  }
350 
351  #ifndef GRAPHICS_DISABLED
352  void plot(ScrollView* window, ScrollView::Color color,
353  ScrollView::Color child_color);
354  #endif // GRAPHICS_DISABLED
355 
356  int BBArea() const {
357  int total_area = 0;
358  for (TESSLINE* outline = outlines; outline != nullptr; outline = outline->next)
359  total_area += outline->BBArea();
360  return total_area;
361  }
362 
363  // Computes the center of mass and second moments for the old baseline and
364  // 2nd moment normalizations. Returns the outline length.
365  // The input denorm should be the normalizations that have been applied from
366  // the image to the current state of this TBLOB.
367  int ComputeMoments(FCOORD* center, FCOORD* second_moments) const;
368  // Computes the precise bounding box of the coords that are generated by
369  // GetEdgeCoords. This may be different from the bounding box of the polygon.
370  void GetPreciseBoundingBox(TBOX* precise_box) const;
371  // Adds edges to the given vectors.
372  // For all the edge steps in all the outlines, or polygonal approximation
373  // where there are no edge steps, collects the steps into x_coords/y_coords.
374  // x_coords is a collection of the x-coords of vertical edges for each
375  // y-coord starting at box.bottom().
376  // y_coords is a collection of the y-coords of horizontal edges for each
377  // x-coord starting at box.left().
378  // Eg x_coords[0] is a collection of the x-coords of edges at y=bottom.
379  // Eg x_coords[1] is a collection of the x-coords of edges at y=bottom + 1.
380  void GetEdgeCoords(const TBOX& box,
381  GenericVector<GenericVector<int> >* x_coords,
382  GenericVector<GenericVector<int> >* y_coords) const;
383 
384  TESSLINE *outlines; // List of outlines in blob.
385 
386  private: // TODO(rays) Someday the data members will be private too.
387  // For all the edge steps in all the outlines, or polygonal approximation
388  // where there are no edge steps, collects the steps into the bounding_box,
389  // llsq and/or the x_coords/y_coords. Both are used in different kinds of
390  // normalization.
391  // For a description of x_coords, y_coords, see GetEdgeCoords above.
392  void CollectEdges(const TBOX& box,
393  TBOX* bounding_box, LLSQ* llsq,
394  GenericVector<GenericVector<int> >* x_coords,
395  GenericVector<GenericVector<int> >* y_coords) const;
396 
397  private:
398  // DENORM indicating the transformations that this blob has undergone so far.
400 }; // Blob structure.
401 
402 struct TWERD {
403  TWERD() : latin_script(false) {}
404  TWERD(const TWERD& src) {
405  CopyFrom(src);
406  }
407  ~TWERD() {
408  Clear();
409  }
410  TWERD& operator=(const TWERD& src) {
411  CopyFrom(src);
412  return *this;
413  }
414  // Factory to build a TWERD from a (C_BLOB) WERD, with polygonal
415  // approximation along the way.
416  static TWERD* PolygonalCopy(bool allow_detailed_fx, WERD* src);
417  // Baseline normalizes the blobs in-place, recording the normalization in the
418  // DENORMs in the blobs.
419  void BLNormalize(const BLOCK* block, const ROW* row, Pix* pix, bool inverse,
420  float x_height, float baseline_shift, bool numeric_mode,
422  const TBOX* norm_box,
423  DENORM* word_denorm);
424  // Copies the data and the blobs, but leaves next untouched.
425  void CopyFrom(const TWERD& src);
426  // Deletes owned data.
427  void Clear();
428  // Recomputes the bounding boxes of the blobs.
429  void ComputeBoundingBoxes();
430 
431  // Returns the number of blobs in the word.
432  int NumBlobs() const {
433  return blobs.size();
434  }
435  TBOX bounding_box() const;
436 
437  // Merges the blobs from start to end, not including end, and deletes
438  // the blobs between start and end.
439  void MergeBlobs(int start, int end);
440 
441  void plot(ScrollView* window);
442 
443  GenericVector<TBLOB*> blobs; // Blobs in word.
444  bool latin_script; // This word is in a latin-based script.
445 };
446 
447 /*----------------------------------------------------------------------
448  F u n c t i o n s
449 ----------------------------------------------------------------------*/
450 // TODO(rays) Make divisible_blob and divide_blobs members of TBLOB.
451 bool divisible_blob(TBLOB *blob, bool italic_blob, TPOINT* location);
452 
453 void divide_blobs(TBLOB *blob, TBLOB *other_blob, bool italic_blob,
454  const TPOINT& location);
455 
456 #endif
EDGEPT * prev
Definition: blobs.h:177
bool Contains(const TPOINT &pt) const
Definition: blobs.h:331
bool SegmentCrossesOutline(const TPOINT &pt1, const TPOINT &pt2) const
Definition: blobs.h:323
Definition: werd.h:59
int step_count
Definition: blobs.h:181
void set_right(int x)
Definition: rect.h:82
TESSLINE * next
Definition: blobs.h:265
TPOINT topleft
Definition: blobs.h:260
int16_t right() const
Definition: rect.h:79
TESSLINE & operator=(const TESSLINE &src)
Definition: blobs.h:195
int BBArea() const
Definition: blobs.h:356
Definition: blobs.h:83
DENORM denorm_
Definition: blobs.h:399
bool SegmentCrosses(const TPOINT &pt1, const TPOINT &pt2) const
Definition: blobs.h:230
TPOINT start
Definition: blobs.h:262
TWERD & operator=(const TWERD &src)
Definition: blobs.h:410
void operator/=(int divisor)
Definition: blobs.h:66
VECTOR vec
Definition: blobs.h:171
char flags[4]
Definition: blobs.h:175
~TBLOB()
Definition: blobs.h:273
TESSLINE(const TESSLINE &src)
Definition: blobs.h:189
Color
Definition: scrollview.h:105
bool EqualPos(const EDGEPT &other) const
Definition: blobs.h:112
Definition: rect.h:34
bool Contains(const TPOINT &pt) const
Definition: blobs.h:241
void set_left(int x)
Definition: rect.h:75
TBLOB(const TBLOB &src)
Definition: blobs.h:270
bool operator==(const TPOINT &other) const
Definition: blobs.h:70
static bool IsCrossed(const TPOINT &a0, const TPOINT &a1, const TPOINT &b0, const TPOINT &b1)
Definition: blobs.cpp:72
EDGEPT * next
Definition: blobs.h:176
int16_t x
Definition: blobs.h:78
C_OUTLINE * src_outline
Definition: blobs.h:178
int start_step
Definition: blobs.h:180
void Reveal()
Definition: blobs.h:157
TBLOB & operator=(const TBLOB &src)
Definition: blobs.h:276
int BBArea() const
Definition: blobs.h:256
bool SameBox(const TESSLINE &other) const
Definition: blobs.h:226
TPOINT botright
Definition: blobs.h:261
TPOINT()
Definition: blobs.h:58
bool latin_script
Definition: blobs.h:444
int16_t bottom() const
Definition: rect.h:65
void operator+=(const TPOINT &other)
Definition: blobs.h:62
TPOINT(int16_t vx, int16_t vy)
Definition: blobs.h:59
TWERD()
Definition: blobs.h:403
GenericVector< TBLOB * > blobs
Definition: blobs.h:443
void MarkChop()
Definition: blobs.h:163
Definition: blobs.h:187
Definition: blobs.h:402
int NumBlobs() const
Definition: blobs.h:432
Definition: scrollview.h:102
Definition: ocrblock.h:30
TWERD(const TWERD &src)
Definition: blobs.h:404
~TWERD()
Definition: blobs.h:407
TESSLINE * outlines
Definition: blobs.h:384
void CopyFrom(const EDGEPT &src)
Definition: blobs.h:96
Definition: baseapi.h:37
Definition: stepblob.h:37
void Hide()
Definition: blobs.h:154
EDGEPT()
Definition: blobs.h:84
int WeightedDistance(const EDGEPT &other, int x_factor) const
Definition: blobs.h:106
bool IsChopPt() const
Definition: blobs.h:166
TBOX SegmentBox(const EDGEPT *end) const
Definition: blobs.h:115
TPOINT(const ICOORD &ic)
Definition: blobs.h:60
void set_top(int y)
Definition: rect.h:61
bool ShortNonCircularSegment(int min_points, const EDGEPT *end) const
Definition: blobs.h:142
bool is_hole
Definition: blobs.h:263
integer coordinate
Definition: points.h:32
Definition: ocrrow.h:36
int16_t top() const
Definition: rect.h:58
Definition: normalis.h:50
Definition: linlsq.h:28
const DENORM & denorm() const
Definition: blobs.h:347
EDGEPT(const EDGEPT &src)
Definition: blobs.h:88
EDGEPT & operator=(const EDGEPT &src)
Definition: blobs.h:91
int16_t left() const
Definition: rect.h:72
TESSLINE()
Definition: blobs.h:188
TPOINT pos
Definition: blobs.h:170
bool IsHidden() const
Definition: blobs.h:160
TBLOB()
Definition: blobs.h:269
Definition: blobs.h:268
OcrEngineMode
Definition: publictypes.h:268
void set_bottom(int y)
Definition: rect.h:68
Definition: blobs.h:57
int16_t y
Definition: blobs.h:79
Definition: points.h:189
EDGEPT * loop
Definition: blobs.h:264
int SegmentArea(const EDGEPT *end) const
Definition: blobs.h:129
~TESSLINE()
Definition: blobs.h:192
Definition: coutln.h:72